www.xbdev.net
xbdev - software development
Saturday April 19, 2025
Home | Contact | Support | JavaScript... so much power in such a few lines of code..
<<
 

Books
Simulations take your GPU on the web to a whole new level! Don't just think about pixels and graphics! Your GPU can simulate thousand of interacting rigid bodies, ragdolls, fluid simulations and more! Learn about simulation wiht the WebGPU and WGSL. You have to learn about rendering! It's a must! You have to agree rendering is at the heart of modern computer graphics, driving everything from immersive video games and visual effects to simulations and virtual environments. Taking WebGPU and WGSL concepts and building things! Not just a theoretical text that repeats the online documentation - but shows you how to build some really cool things, like animations, interacting and games.
Amazon



 
     
 

JavaScript...

so much power in such a few lines of code..

  


Minkowski Collision Detection Demo (2D Boxes)


I've written lots of collision detection algorithms using lots of different techniques - however, the Minkowski is one of the best - it's very flexible easy to understand (especially in 2d).

The following gives a tutorial/visualization for working with the Minkowski algorithm.

While the algorithm can work with any 'convex' shapes - this demo focuses on 'boxes'.



Screenshot of the test demo of the minkowski different for collision detection and feature extraction demo.
Screenshot of the test demo of the minkowski different for collision detection and feature extraction demo.



The demo is interactive and runs in a web-browser - you can drag your mouse around and it displays the minkowski information (and the collision feature data).







Complete Code


<html><head></head>
<body>

<style>
body {  min-height: 700px;  }

* { margin: 0;
    padding: 0; 
}

.grid {
    height: 100%;
    width: 100%;
    margin: 0;
}
.grid {
    background-image:
      repeating-linear-gradient(#ccc 0 1px, transparent 1px 100%),
      repeating-linear-gradient(90deg, #ccc 0 1px, transparent 1px 100%);
    background-size: 71px 71px;
}
</style>

<div class="grid"></div>

<div id='hit' style="font-size:20pt;position:absolute;left:10px;top:20px;"></div>

<div style="font-size:10pt;position:absolute;width:480px;left:10px;bottom:20px;">
A robust 2D collision detection demo with feature extraction information, such as, 
contact points, penetration depth and hit (true/false).
Minkowski difference for 2d boxes and shortest distance algorithms.
Demo shows the Minkowski points (A-B), box A, box B and calculation features (educational purposes). Author: Kenwright (www.xbdev.net)
</div>

<script>
function vec2(x, y)
{
  this.x = x;
  this.y = y;
  
  this.set = function(x, y)
  {
    this.x = x;
    this.y = y;
  }
};

vec2.add    = function(v0, v1){  return new vec2(v0.x+v1.x, v0.y+v1.y);    }
vec2.sub    = function(v0, v1){  return new vec2(v0.x-v1.x, v0.y-v1.y);    }
vec2.scale  = function(v0, s ){ return new vec2(v0.x*s, v0.y*s);          }
vec2.mul    = function(v0, v1){ return new vec2(v0.x*v1.x, v0.y*v1.y);    }
vec2.cross  = function(v0,v1) { return (v0.x*v1.y - v0.y*v1.x);   }
vec2.dot    = function(v0, v1){  return (v0.x*v1.x + v0.y*v1.y);            }
// note you can't use 'length' word
//vec2.length = function(v0    ){ return Math.sqrt( v0.x*v0.x + v0.y*v0.y); }
vec2.dist = function(v0) { return Math.sqrt( v0.x*v0.x + v0.y*v0.y); }
vec2.norm   = function(v0    )
{ 
  let ln = Math.sqrt( v0.x*v0.x + v0.y*v0.y);
  return vec2.scale( v0, 1.0/ln );
}
vec2.perp   = function(n     ){ return new vec2(n.y, -n.x);                }


let off = new vec2(300,300);

const maxobjs = 1000;
var numobjs2 = 0;
var objs = [];


function cleardraw2()
{
  numobjs2 = 0;
  for (let i=0; i<objs.length; i++)
  {
    objs[i].style.left = '-1000px';
  }  
}
function setupdraw()
{
  numobjs2 = 0;
  for (let i=0; i<maxobjs; i++)
  {
    let div = document.createElement('div');
    document.body.appendChild( div );
    objs.push( div );
  }
}

setupdraw();

/*
  helper function for drawing lines using 'div'
  elements (use a bit of trigonometry to set the size
  and orientation to create a line)
*/
function drawLine(s0, s1, col='blue')
{
  let ax = s0.x + off.x;
  let ay = s0.y + off.y;
  let bx = s1.x + off.x;
  let by = s1.y + off.y;
  //console.log( numobjs2 );
  console.assert( numobjs2 < maxobjs );
  let div = objs[numobjs2];
  numobjs2++;
  //if ( div == 0 )
  {
    //div = document.createElement('div');
    //document.body.appendChild( div );
  }
  div.style.position = 'absolute';
  
    if(ay>by)
    {
        bx=ax+bx;  
        ax=bx-ax;
        bx=bx-ax;
        by=ay+by;  
        ay=by-ay;  
        by=by-ay;
    }
    
    let calc   = Math.atan((ax-bx)/(by-ay));
    calc       = calc*180.0/Math.PI;
    let length = Math.sqrt((ax-bx)*(ax-bx)+(ay-by)*(ay-by));
    div.style.height         = length + "px";
  div.style.width          = 2 + "px";
  div.style.left           = ax + "px";
  div.style.top            = ay + "px";
  div.style.transform      = 'rotate(' + calc + 'deg)';
  div.style.transformOrigin="0 0";
  div.style.backgroundColor=col;//"blue";
}

function drawCross( v0, s, col='black' )
{
  let x = new vec2(s,0);
  let y = new vec2(0,s);
  
  drawLine( vec2.sub(v0,x), vec2.add(v0,x), col );
  drawLine( vec2.sub(v0,y), vec2.add(v0,y), col );  
}

function drawArrow(v0, v1, s, color='blue')
{
  drawLine( v0, v1, color );
  
    // Calculate the direction of the line
    const direction = vec2.norm( new vec2(v1.x - v0.x, v1.y - v0.y) );

    // Perpendicular vectors for the arrowhead
    const perp1 = vec2.scale( new vec2(-direction.y, direction.x), s);
    const perp2 = vec2.scale( new vec2(direction.y, -direction.x), s);

    // Calculate the end points of the arrowhead
    const arrowHeadPoint1 = new vec2(v1.x - direction.x * s + perp1.x, v1.y - direction.y * s + perp1.y);
    const arrowHeadPoint2 = new vec2(v1.x - direction.x * s + perp2.x, v1.y - direction.y * s + perp2.y);

    // Draw the arrowhead
    drawLine(v1, arrowHeadPoint1, color);
    drawLine(v1, arrowHeadPoint2, color);
  
}

function drawCircle(s0, r, col='red')
{
  let ax = s0.x + off.x;
  let ay = s0.y + off.y;
  
  console.assert( numobjs2 < maxobjs );
  let div = objs[numobjs2];
  numobjs2++;

  div.style.position = 'absolute';
    div.style.height         = r*2 + "px";
  div.style.width          = r*2 + "px";
  div.style.left           = (ax-r) + "px";
  div.style.top            = (ay-r) + "px";
  div.style['border-radius'] =  '50%';
  div.style.backgroundColor=col;
}

function drawBox(p0, s0, angle, col='red')
{
  const halfWidth  = s0.x;
  const halfHeight = s0.y;

  // Calculate the rotated corner points
  const cos = Math.cos(angle);
  const sin = Math.sin(angle);

  // Calculate the positions of the four corners
  const topLeft = {
    x: p0.x + (-halfWidth * cos - -halfHeight * sin),
    y: p0.y + (-halfWidth * sin + -halfHeight * cos)
  };
  const topRight = {
    x: p0.x + (halfWidth * cos - -halfHeight * sin),
    y: p0.y + (halfWidth * sin + -halfHeight * cos)
  };
  const bottomRight = {
    x: p0.x + (halfWidth * cos - halfHeight * sin),
    y: p0.y + (halfWidth * sin + halfHeight * cos)
  };
  const bottomLeft = {
    x: p0.x + (-halfWidth * cos - halfHeight * sin),
    y: p0.y + (-halfWidth * sin + halfHeight * cos)
  };

  // Draw the square
    /*
  ctx.beginPath();
  ctx.moveTo(topLeft.x, topLeft.y);
  ctx.lineTo(topRight.x, topRight.y);
  ctx.lineTo(bottomRight.x, bottomRight.y);
  ctx.lineTo(bottomLeft.x, bottomLeft.y);
  ctx.closePath();
  ctx.stroke();
    */

    drawLine( topLeft,     topRight    );
    drawLine( topRight,    bottomRight );
    drawLine( bottomRight, bottomLeft  );
    drawLine( bottomLeft,  topLeft     );
}
  
function drawShape( s )
{
  for (let i=1; i<s.length; i++)
  {
    drawLine(s[i-1], s[i]);
    drawCircle( s[i-1], 5 );
  }
  drawLine(s[0], s[s.length-1]);
  drawCircle( s[s.length-1], 5 );
}

function shape()
{
  this.points = [];
  this.addPoint = function( v )
  {
    this.points.push( new vec2(v.x, v.y) );
  }
  this.draw = function()
  {
    drawShape( this.points );
  }
  /*
  this.drawPoints = function()
  {  
    for (let i=1; i<this.points.length; i++)
    {
      drawCircle( this.points[i-1], 6, 'green' );
    }
    drawCircle( this.points[this.points.length-1], 6, 'green' );
  }
  */

  this.getCentroid = function()
  {
    let v = new vec2(0,0);
    for (let i=0; i<this.points.length; i++)
    {
      v = vec2.add( v, this.points[i] );
    }
    
    v = vec2.scale( v, 1/this.points.length );
    return v;
  }
}


let boxA = { p: new vec2(100,100),
             s: new vec2(100, 50),
             a: 0.6 };

let boxB = { p: new vec2(200,50),
             s: new vec2(60, 120),
             a: 1.1 };


function rotatePoint( point, angle )
{
    let c = Math.cos(angle);
    let s = Math.sin(angle);
    return new vec2(
        point.x * c - point.y * s,
        point.x * s + point.y * c
    );
}

function stHit() {
  var  pen    = 0.0; 
  var  normal = new vec2(0,0);
  var  point  = new vec2(0,0);
};


let cur = new vec2(0,0); // mouse position

function closestPoint( pA, pB, pX )
{
  let b = vec2.dist( vec2.sub(pB,pA) );
  if ( b < 0.0001 )
  {
    return pA;
  }
  let n = vec2.norm( vec2.sub(pB,pA) );
  let pAX = vec2.sub(pX, pA);
  let s = vec2.dot( n, pAX );
  let a = vec2.dist( vec2.scale(n,s) );
  
  let t = a/b;
  if ( t <= 0 ) return pA;
  if ( t >= 1 ) return pB;
  
  let pT = vec2.add( pA, vec2.scale( vec2.sub(pB,pA), t ) );
  return pT;
}

// order points for a triangle are in a
// clockwise or counterclockwise direction

function getCW(v1,v2,v3)
{
  let n1 = vec2.norm( vec2.sub(v2,v1) );
  let n2 = vec2.norm( vec2.sub(v3,v1) );
  let d = vec2.cross(n1,n2);
  if ( d < 0 ) return -1;
  return 1;
}
  
  
function MinkowskiBox(boxA, boxB)
{
  this.shapeA  = [];
  this.shapeB  = [];
  this.shapeBA = [];
  
    let corners =  [ new vec2( -1, -1 ), 
                     new vec2(  1, -1 ), 
                     new vec2(  1,  1 ),
                     new vec2( -1,  1 ) ];
  
    for (let i=0; i<4; i++)
    {
        this.shapeA.push( vec2.add( rotatePoint( vec2.mul(corners[i], boxA.s) , boxA.a ), boxA.p ) );
        this.shapeB.push( vec2.add( rotatePoint( vec2.mul(corners[i], boxB.s) , boxB.a ), boxB.p ) );
    }
      
  let c = 0;
  for (let i=0; i<this.shapeA.length; i++)
  {
    let pA = this.shapeA[i];
    for (let k=0; k<this.shapeB.length; k++)
    {
      let pB = this.shapeB[k];  
      let pBA = vec2.sub( pB, pA );
      this.shapeBA.push( { p:pBA, a:pA, i:c, b:pB, ai:i, bi:k } );
      c++;
    }
  }
  
  this.getNumPoints = function()
  {
    return this.shapeA.length * 
         this.shapeB.length;
  }
  
  this.drawPoints = function()
  {
        drawShape( this.shapeA );
        drawShape( this.shapeB );
    for (let i=1; i<this.shapeBA; i++)
    {
      drawCircle( this.shapeBA[i-1].p, 6, 'green' );
    }
    drawCircle( this.shapeBA[this.shapeBA.length-1].p, 6, 'green' );
  }
  
  this.getSupport = function( dir )
  {
    let n = vec2.norm( dir );
    let d = vec2.dot( this.shapeBA[0].p, n );
    let h = 0;
    for (let i=0; i<this.shapeBA.length; i++)
    {
      let t = vec2.dot( this.shapeBA[i].p, n );
      if ( t > d )
      {
        d = t;
        h = i;
      }
    }
    return this.shapeBA[h];  
  }  
  
    this.collision = function()
    {
        let v1 = this.getSupport( new vec2(0, 1) );
        let v2 = this.getSupport( new vec2(1, 0) );
        let v3 = this.getSupport( new vec2(0,-1) );

        if ( v2.i == v1.i || v2.i == v3.i )
        {
            // swap them around to keep things ordered clockwise
            v2 = v3;
            v3 = this.getSupport( new vec2(-1, 0) );
        }

        console.assert( v1.i != v2.i);
        console.assert( v2.i != v3.i);


        let edges = [];
        edges.push( [v1, v2] );
        edges.push( [v2, v3] );
        edges.push( [v3, v1] );

        let hullEdges = [];

        let check = 0;
        while ( edges.length > 0 )
        {
            let edge = edges.pop();

            let n = vec2.norm( vec2.perp( vec2.sub( edge[0].p, edge[1].p ) ) );

            let v4 = this.getSupport( n );

            if ( v4.i == edge[0].i ||
                 v4.i == edge[1].i )
            {
                // save edge 
                hullEdges.push( edge );
            }
            else 
            {
                edges.push( [ edge[0], v4      ] );
                edges.push( [ v4     , edge[1] ] );
            }

            console.assert( edges.length < 100 );
            check++;
            console.assert(check<100);
        }

        let sdist = 10000;
        let indx  = 0;

        for (let i=0; i<hullEdges.length; i++)
        {
            let edge = hullEdges[i];
            drawLine( edge[0].p, edge[1].p, 'orange' );

            let cp = closestPoint( edge[0].p, edge[1].p, new vec2(0,0) );
            //drawCircle( cp, 4, 'yellow' );

            let d = vec2.dist( vec2.sub( cp, new vec2(0,0) ) );
            if ( d < sdist )
            {
                sdist = d;
                indx  = i;
            }
        }

        let inside = getCW( new vec2(0,0),
                            hullEdges[indx][ 0 ].p,
                            hullEdges[indx][ 1 ].p );

        let best = closestPoint( hullEdges[indx][ 0 ].p, 
                                 hullEdges[indx][ 1 ].p, 
                                 new vec2(0,0) );
        drawCircle( best, 6, 'yellow' );


        let df = vec2.dist( vec2.sub(hullEdges[indx][ 0 ].p,
                                     hullEdges[indx][ 1 ].p) );
        let d1 = vec2.dist( vec2.sub(hullEdges[indx][ 0 ].p,
                                                       best) );
      
         let t = d1/df;
        //console.log( 't:' + t + ', df:' + df + ', d1: ' + d1 );

        console.assert( t >=0 && t <= 1 );

        let a0 = hullEdges[indx][ 0 ].a;
        let a1 = hullEdges[indx][ 1 ].a;
        let x = vec2.add( a0, vec2.scale(vec2.sub( a1,a0 ), t ) );
        drawCross( x, 40, 'orange' );

        let b0 = hullEdges[indx][ 0 ].b;
        let b1 = hullEdges[indx][ 1 ].b;
        let y = vec2.add( b0, vec2.scale(vec2.sub( b1,b0 ), t ) );
        drawCross( y, 40, 'orange' );

        drawLine( x, y, 'red' );

        let pen = vec2.dist( vec2.sub( x, y ) );
        let nor = vec2.norm( vec2.sub( x, y ) );

        let data = {hit:false,
                    p: pen,
                    n: nor };

        if ( inside <= 0 )
        {
            data.hit = true;
        }
      
        var hit = new stHit();
        hit.pen    = pen  * (inside<=0 ? -1 : 1);
        hit.point  = x;
        hit.normal = nor;
        return hit; // return collision data

    }// end collision function
}



document.onmousemove = function(e)
{  
  cur.x = e.pageX;
  cur.y = e.pageY;
  
  
  cleardraw2();
  
  drawCircle(new vec2(0,0), 8, 'black'); // origin
  drawCross( new vec2(0,0), 20 ); // draw origin
  
    //drawBox( boxA.p, boxA.s, boxA.a );
    //drawBox( boxB.p, boxB.s, boxB.a );
  
    drawCircle( cur, 3, 'orange' );
  
    boxA.p = vec2.sub(cur,off);
  
  
    let mink = new MinkowskiBox(boxA, boxB);
  mink.drawPoints();
  
    let hit = mink.collision();
  
    /*
  // get mouse position and offset the origin - debugging/visualization
  // purposes
  let cA = shapeA.getCentroid();
  let delta = vec2.sub( vec2.sub(cur,off), cA );
  for (let i=0; i<shapeA.points.length; i++)
  {
    shapeA.points[i] = vec2.add( shapeA.points[i], delta );
  }
  */
  
    let h0 = hit.point;
    let h1 = vec2.add( hit.point, vec2.scale( hit.normal, -50.0 ) );
  
    h0.y += 0;
    h1.y += 0;
  
    drawArrow( h0, 
               h1, 
               20.0, 'blue' );
  
  let div = document.getElementById('hit');
  div.innerHTML = 'Hit: ' + hit.pen.toFixed(2) + ( hit.pen < 0 ? ' <b>(HIT)</b>' : '' );
}
document.onmousemove( {pageX:100, pageY:100} );
</script>

</body>
</html>


The code is actually quiet elegant and compact - the code draws the lines and points using 'pure' html elements (no canvas drawing).

Just manipulates the html elements (div) so they can be used for drawing (of course combined with JavaScript).




Resources and Links


• Current Page (Share) [LINK]

• 2d 'any' convex shape demo version [LINK]

• Tutorial on the Minkowski algorithm (2d and 3d) [LINK]

• Other physics tutorials [LINK]

• Notebook Test Code [LINK]

• WebGPU Version (WebGPU Lab) - [LINK]




























101 WebGPU Programming Projects. WebGPU Development Pixels - coding fragment shaders from post processing to ray tracing! WebGPU by Example: Fractals, Image Effects, Ray-Tracing, Procedural Geometry, 2D/3D, Particles, Simulations WebGPU Games WGSL 2d 3d interactive web-based fun learning WebGPU Compute WebGPU API - Owners WebGPU Development Cookbook - coding recipes for all your webgpu needs! WebGPU & WGSL Essentials: A Hands-On Approach to Interactive Graphics, Games, 2D Interfaces, 3D Meshes, Animation, Security and Production Kenwright graphics and animations using the webgpu api 12 week course kenwright learn webgpu api kenwright programming compute and graphics applications with html5 and webgpu api kenwright real-time 3d graphics with webgpu kenwright webgpu for dummies kenwright webgpu wgsl compute graphics all in one kenwright webgpu api develompent a quick start guide kenwright webgpu by example 2022 kenwright webgpu gems kenwright webgpu interactive compute and graphics visualization cookbook kenwright wgsl webgpu shading language cookbook kenwright WebGPU Shader Language Development: Vertex, Fragment, Compute Shaders for Programmers Kenwright WGSL Fundamentals book kenwright WebGPU Data Visualization Cookbook kenwright Special Effects Programming with WebGPU kenwright WebGPU Programming Guide: Interactive Graphics and Compute Programming with WebGPU & WGSL kenwright Ray-Tracing with WebGPU kenwright



 
Advert (Support Website)

 
 Visitor:
Copyright (c) 2002-2025 xbdev.net - All rights reserved.
Designated articles, tutorials and software are the property of their respective owners.