www.xbdev.net
xbdev - software development
Tuesday April 29, 2025
Home | Contact | Support | WebGPU Graphics and Compute ... | WebGPU 'Compute'.. Compute, Algorithms, and Code.....
     
 

WebGPU 'Compute'..

Compute, Algorithms, and Code.....

 

Minkowski 2d (boxes)


The demo focuses on implementing a 2d Minkowski difference algorithm with feature extraction. The program is a prototype for both helping understand the Minkowski algorithm and a springboard for larger projects.


Screenshot of the Minkowski 2d demo.
Screenshot of the Minkowski 2d demo.


Functions Used: requestAdapter(), getPreferredCanvasFormat(), createCommandEncoder(), beginRenderPass(), setPipeline(), draw(), end(), submit(), getCurrentTexture(), createView(), createShaderModule()


The demo only runs on a single thread with 2 shapes (i.e., 2 boxes) which can be dragged around with the mouse. As one box is dragged around with the cursor the contact feature data is drawn on the screen (send back from the compute shader).

The WGSL compute shader is quiet complex and helps demonstrate the power and flexiblity for implementing complex algorithms on the GPU.




Complete Code


let div document.createElement('div');
document.body.appendChilddiv );
div.style['font-size'] = '20pt';
function 
log)
{
  
console.log);
  
let args = [...arguments].join(' ');
  
div.innerHTML += args '<br>';
}

log('WebGPU Compute Example');

if (!
navigator.gpu) { log("WebGPU is not supported (or is it disabled? flags/settings)"); return; }

const 
adapter await navigator.gpu.requestAdapter();
const 
device  await adapter.requestDevice();


let canvas document.createElement('canvas');
canvas.id 'canvas';
canvas.style.border '1px solid orange';
document.body.appendChildcanvas ); canvas.height canvas.width 600;


// -------------------------------------------------------------------

function rand(lohi)
{
   return 
lo Math.random() * (hi lo);
}

// -------------------------------------------------------------------

// Grouped data into vec4 groups - help with alignment/packing
const NUMBER_OBJECTS   2;
const 
SIZE_EACH_OBJECT 7;   // Number floats for each object structure (vel, pos, size, ..)

const objectArray0 = new Float32ArrayNUMBER_OBJECTS SIZE_EACH_OBJECT );

const 
objectBuffer0 device.createBuffer({ sizeobjectArray0.byteLengthusageGPUBufferUsage.STORAGE GPUBufferUsage.COPY_DST  GPUBufferUsage.COPY_SRC });
device.queue.writeBuffer(objectBuffer00objectArray0);

const 
objectBufferTmp device.createBuffer({ sizeobjectArray0.byteLengthusageGPUBufferUsage.COPY_DST GPUBufferUsage.MAP_READ });

// ----------------------------------------------------------------

const timestep  = new Float32Array( [0.0] );
const 
timerUniformBuffer device.createBuffer({ sizetimestep.byteLength,  usageGPUBufferUsage.UNIFORM GPUBufferUsage.COPY_DST });
device.queue.writeBuffer(timerUniformBuffer,   0timestep );

// ----------------------------------------------------------------

const mouse  = new Float32Array( [0.00.0] );
const 
mouseUniformBuffer device.createBuffer({ sizemouse.byteLength,  usageGPUBufferUsage.UNIFORM GPUBufferUsage.COPY_DST });
device.queue.writeBuffer(mouseUniformBuffer,   0mouse );

// ----------------------------------------------------------


// Bind group layout and bind group
const bindGroupLayout device.createBindGroupLayout({
  
entries: [  
    {
binding0visibilityGPUShaderStage.COMPUTEbuffer: { type"uniform" }   },
    {
binding1visibilityGPUShaderStage.COMPUTEbuffer: { type"uniform" }   },
    {
binding2visibilityGPUShaderStage.COMPUTEbuffer: { type"storage" }   }
           ]
});

const 
bindGroup0 device.createBindGroup({ layoutbindGroupLayout,
                                            
entries: [  { binding0,  resource: { buffertimerUniformBuffer     } },
                                                       { 
binding1,  resource: { buffermouseUniformBuffer     } },
                                                        { 
binding2,  resource: { bufferobjectBuffer0          } }
                                                    ] });

// Compute shader code
const computeShader = ` 
struct stObject {  
    // object data
    p      : vec4<f32>, // position and rotation (xy position, z angle)
    s      : vec4<f32>, // size
    // collision features
    pen    : vec4<f32>,
    normal : vec4<f32>,
    point  : vec4<f32>,
    b      : vec4<f32>,
    ids    : vec4<f32>
}


struct stObjectDiff {
    // object data
    p      : vec2<f32>, 
    a      : vec2<f32>,
    b      : vec2<f32>,
    i      : u32,
    ai     : u32,
    bi     : u32
}
struct stHit {
  pen        : f32,
  normal     : vec2<f32>,
  point      : vec2<f32>,
  otherpoint : vec2<f32>,
  b0: vec2<f32>,
  b1: vec2<f32>,
  ids: vec4<f32>
};



@binding(0) @group(0) var<uniform>            mytimer  : f32;
@binding(1) @group(0) var<uniform>            mymouse  : vec2<f32>;
@binding(2) @group(0) var<storage,read_write> objects  : array< stObject  , 
${NUMBER_OBJECTS} >;  


fn rotatePoint(point: vec2<f32>, angle: f32) -> vec2<f32> {
    let c = cos(angle);
    let s = sin(angle);
    return vec2<f32>(
        point.x * c - point.y * s,
        point.x * s + point.y * c
    );
}

fn cross2D(a: vec2<f32>, b: vec2<f32>) -> f32 {
    return a.x * b.y - a.y * b.x;
}

fn perp( n:vec2<f32> ) -> vec2<f32> { 
    return vec2<f32>(n.y, -n.x);                
}

fn closestPoint( pA:vec2<f32>, pB:vec2<f32>, pX:vec2<f32> ) -> vec2<f32>
{
    let b = length( pB - pA );
    if ( b < 0.0001 )
    {
        return pA;
    }
    let n = normalize( pB - pA );
    let pAX = pX - pA;
    let s = dot( n, pAX );
    let a = length( n * s );
    
    let t = a/b;
    if ( t <= 0 ) { return pA; }
    if ( t >= 1 ) { return pB; }
    
    let pT = pA + (pB - pA) * t;
    return pT;
}


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

fn getCW( v1:vec2<f32>, v2:vec2<f32>, v3:vec2<f32> ) -> f32
{
    let n1 = normalize( v2 - v1 );
    let n2 = normalize( v3 - v1 );
    let d = cross2D(n1, n2);
    if ( d < 0.0 ) { return -1.0; }
    return 1.0;
}


struct stMinkowskiData 
{
    shapeA  : array< vec2<f32>,       4  >,
    shapeB  : array< vec2<f32>,       4  >,
    shapeBA : array< stObjectDiff,    16 >
};

fn MinkowskiBox(boxA:stObject, boxB:stObject) -> stMinkowskiData
{
    var md : stMinkowskiData;
    
    let corners =  array< vec2<f32>, 4 >(vec2<f32>( -1, -1 ), 
                                         vec2<f32>(  1, -1 ), 
                                         vec2<f32>(  1,  1 ),
                                         vec2<f32>( -1,  1 ) );
  
    for (var i=0; i<4; i++)
    {
        md.shapeA[i] = rotatePoint( corners[i] * boxA.s.xy , boxA.p.z ) + boxA.p.xy;
        md.shapeB[i] = rotatePoint( corners[i] * boxB.s.xy , boxB.p.z ) + boxB.p.xy;
    }
      
    var c:u32 = 0;
    for (var i:u32=0; i< 4;  i++)
    {
      let pA = md.shapeA[i];
      for (var k:u32=0; k< 4;  k++)
      {
        let pB  = md.shapeB[k];  
        let pBA = pB - pA;
        md.shapeBA[c].p  = pBA;
        md.shapeBA[c].a  = pA;
        md.shapeBA[c].b  = pB;
        md.shapeBA[c].i  = c;
        md.shapeBA[c].ai = i;
        md.shapeBA[c].bi = k;
        c++;
      }
    }
    return md;
}

fn getSupport( md:stMinkowskiData, dir:vec2<f32> ) -> stObjectDiff
{
    let n = normalize( dir );
    var d = dot( md.shapeBA[0].p, n );
    var h:u32 = 0;
    for (var i:u32=0; i< 16; i++)
    {
        let t = dot( md.shapeBA[i].p, n );
        if ( t > d )
        {
            d = t;
            h = i;
        }
    }
    return md.shapeBA[h];  


struct stEdge {
    e0 : stObjectDiff,
    e1 : stObjectDiff
}

fn collision( md:stMinkowskiData ) -> stHit
{
    var hit : stHit;
    hit.pen = 9999.9;
    
    
    var v1 = getSupport( md, vec2<f32>(0, 1) );
    var v2 = getSupport( md, vec2<f32>(1, 0) );
    var v3 = getSupport( md, vec2<f32>(0,-1) );

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

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

    var edges = array< stEdge , 5 >();
    var numEdges:u32 = 0;
    
    edges[numEdges].e0 = v1;   edges[numEdges].e1 = v2;        numEdges++;
    edges[numEdges].e0 = v2;   edges[numEdges].e1 = v3;        numEdges++;
    edges[numEdges].e0 = v3;   edges[numEdges].e1 = v1;        numEdges++;
    edges[numEdges].e0 = v3;   edges[numEdges].e1 = v1;        numEdges++;
    edges[numEdges].e0 = v3;   edges[numEdges].e1 = v1;        numEdges++;

    
    

    var hullEdges   = array< stEdge , 16 >();
    var numHullEdges = 0;
    
    var docheck0:f32 = 0;
    var docheck1:f32 = 0;
    var docheck2:f32 = 0;
    var docheck3:f32 = 0;
    
    //docheck = f32( getSupport( md, vec2(1.2,0.5 ) ).i );
    
    var dodo = 0;
    
    var check = 0;
    while ( numEdges > 0 )
    {
        var eedge = edges[numEdges-1];
        numEdges--;

        let n = normalize( perp( eedge.e0.p - eedge.e1.p ) );

        let v4 = getSupport( md, n );
        

        if ( v4.i == eedge.e0.i ||
             v4.i == eedge.e1.i )
        {  
            // save edge 
            
            hullEdges[ numHullEdges ] = stEdge();
            hullEdges[ numHullEdges ] = eedge;
            numHullEdges++;
        }
        else 
        {
            numEdges++;
            edges[ numEdges-1 ] = stEdge();
            edges[ numEdges-1 ].e0 = eedge.e0;
            edges[ numEdges-1 ].e1 = v4; 
            
            numEdges++;
            edges[ numEdges-1 ] = stEdge();
            edges[ numEdges-1 ].e0 = v4;
            edges[ numEdges-1 ].e1 = eedge.e1;

            
            //edges[ numEdges-1 ].e0.i = 7;
        }
        
        if ( check == 0 ) // i32( mytimer*2.1 )  )
        {
            docheck0 = f32(eedge.e0.i);
            docheck1 = f32(eedge.e1.i);
            docheck2 = f32(v4.i);
            docheck3 = f32( edges[ numEdges-1 ].e0.i );
        }
        
        
        //if ( check == 2 && numEdges > 2)
        //{
            //docheck2 = f32( numEdges );
            //docheck3 = f32( edges[3].e0.i );
        //}

        //console.assert( edges.length < 100 );
        check++;
        //console.assert(check<100);
        if ( check > 100 ) 
        { 
            hit.pen = 99999.9; // f32(edge.e1.i);
            hit.ids.x = f32(docheck0);
            hit.ids.y = f32(docheck1);
            hit.ids.z = f32(docheck2);
            hit.ids.w = f32(docheck3);
            return hit; 
        }
    }
    
    //docheck3 = f32( numHullEdges );
    
    var sdist = 10000.0;
    var indx  = 0;

    var best = vec2<f32>(0.0);
    
    for (var i=0; i<numHullEdges; i++)
    {
        let edge = hullEdges[i];
        //drawLine( edge.e0.p, edge.e1.p, 'orange' );

        let cp = closestPoint( edge.e0.p, edge.e1.p, vec2<f32>(0,0) );
        //drawCircle( cp, 4, 'yellow' );

        let d = length( cp - vec2<f32>(0.0,0.0) );
        if ( d < sdist )
        {
            sdist = d;
            indx  = i;
            best  = cp;
        }
    }

    let inside = getCW( vec2<f32>(0,0),
                        hullEdges[indx].e0.p,
                        hullEdges[indx].e1.p );

    //let best = closestPoint( hullEdges[indx].e0.p, 
    //                         hullEdges[indx].e1.p, 
    //                         vec2<f32>(0,0) );
    
    //drawCircle( best, 6, 'yellow' );

    let df = length( hullEdges[indx].e0.p - hullEdges[indx].e1.p );
                                 
    let d1 = length( hullEdges[indx].e0.p - best );

     let t = d1/df;
    //console.log( 't:' + t + ', df:' + df + ', d1: ' + d1 );

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

    let a0 = hullEdges[indx].e0.a;
    let a1 = hullEdges[indx].e1.a;
    let x  = a0 + ( a1 - a0 ) * t;
    // drawCross( x, 40, 'orange' );

    let b0 = hullEdges[indx].e0.b;
    let b1 = hullEdges[indx].e1.b;
    let y  = b0 + ( b1 - b0 ) * t;
    //drawCross( y, 40, 'orange' );

    //drawLine( x, y, 'red' );

    let pen = length( x - y );
    let nor = normalize( x - y );

    
    hit.pen    = pen;
    if ( inside <= 0.0 ) { hit.pen = pen * -1.0; }
    hit.point      = x;
    hit.otherpoint = y;
    hit.normal     = nor;
    hit.b0         = b0;
    hit.b1         = b1;
    hit.ids.x = f32(docheck0);
    hit.ids.y = f32(docheck1);
    hit.ids.z = f32(docheck2);
    hit.ids.w = f32(docheck3);
    
    return hit; // return collision data

}// end collision function


// Parameters
const NUMBER_OBJECTS:  u32 = 
${NUMBER_OBJECTS};


// Main compute shader function
@compute @workgroup_size(1, 1)
fn main(
    @builtin(global_invocation_id) globalId: vec3<u32>,
    @builtin(local_invocation_id) localId: vec3<u32>,
    @builtin(workgroup_id) workgroupId: vec3<u32>,
    @builtin(num_workgroups) workgroupSize: vec3<u32>
) {
    // Read the current state of flock agent
    var cp = objects[globalId.x].p.xy; // position
    var ca = objects[globalId.x].p.z;  // angle
    var cs = objects[globalId.x].s.xy;
        
    objects[0].p.x = mymouse.x;
    objects[0].p.y = mymouse.y;
    
    // Initialization step
    if ( mytimer == 0.0 )
    {
        objects[0].p = vec4<f32>(100.0-200, 100.0-200, 0.6, 0.0);
        objects[0].s = vec4<f32>(100.0, 50.0,  0.0, 0.0);
        objects[0].pen    = vec4<f32>(0);
        objects[0].normal = vec4<f32>(0);
        objects[0].point  = vec4<f32>(0);
        
        objects[1].p = vec4<f32>(200.0, 50.0,   1.1, 0.0);
        objects[1].s = vec4<f32>(60.0,  120.0,  0.0, 0.0);
        objects[1].pen    = vec4<f32>(0);
        objects[1].normal = vec4<f32>(0);
        objects[1].point  = vec4<f32>(0);
             
           //return;
    }

    let md = MinkowskiBox( objects[0], objects[1] );

    let hit = collision( md );
    

    // Write output state of flock agent to flockOut
    //objects[globalId.x].p = vec4<f32>( cp, ca, 0);
    //objects[globalId.x].s = vec4<f32>( cs, 0, 0);
    
    objects[globalId.x].pen    = vec4<f32>(hit.pen,    0, 0, 0);
    objects[globalId.x].normal = vec4<f32>(hit.normal.xy, 0, 0);
    objects[globalId.x].point  = vec4<f32>(hit.point.xy,  hit.otherpoint.xy);
    objects[globalId.x].b      = vec4<f32>(hit.b0.xy, hit.b1.xy);
    objects[globalId.x].ids    = hit.ids;
}

`;
  

// Pipeline setup
const computePipeline device.createComputePipeline({
    
layout :   device.createPipelineLayout({bindGroupLayouts: [bindGroupLayout]}),
    
compute: { module    device.createShaderModule({code:computeShader}),
               
entryPoint"main" }
});


let off = {x:200y:200};
let cur = {x:0y:0};

async function drawCircle(ctxpxpyrcolor='blue')
{
    
// Draw circle
    
ctx.strokeStyle color;
    
ctx.beginPath();
    
ctx.arc(off.x+pxoff.y+pyr0Math.PI 2);
    
ctx.stroke(); // Draw outline
    
ctx.closePath();
}

async function drawLine(ctxp0p1color='green' )
{
      
ctx.strokeStyle color;
    
ctx.beginPath();
    
ctx.moveTo(off.x+p0.xoff.y+p0.y);
    
ctx.lineTo(off.x+p1.xoff.y+p1.y);
    
ctx.closePath();
    
ctx.stroke();
}

function 
rotatePointpointangle )
{
    
let c Math.cos(angle);
    
let s Math.sin(angle);
    return new 
vec2(
        
point.point.s,
        
point.point.c
    
);
}

function 
vec2(xy)
{
  
this.x;
  
this.y;
  
  
this.set = function(xy)
  {
    
this.x;
    
this.y;
  }
};

vec2.add    = function(v0v1){  return new vec2(v0.x+v1.xv0.y+v1.y);    }
vec2.sub    = function(v0v1){  return new vec2(v0.x-v1.xv0.y-v1.y);    }
vec2.scale  = function(v0){ return new vec2(v0.x*sv0.y*s);          }
vec2.mul    = function(v0v1){ return new vec2(v0.x*v1.xv0.y*v1.y);    }


async function frame()
{
  
// Commands submission
  
const commandEncoder device.createCommandEncoder();

  {
  const 
passEncoder commandEncoder.beginComputePass();
  
passEncoder.setPipeline(computePipeline);
  
passEncoder.setBindGroup(0bindGroup0);
  
// workgroup size on the wgsl shader
  
passEncoder.dispatchWorkgroups);
  
await passEncoder.end();
  }

  
// Encode commands for copying buffer to buffer.
  
await
  commandEncoder
.copyBufferToBuffer(
      
objectBuffer0,      // source buffer
      
0,                  // source offset
      
objectBufferTmp,    // destination buffer
      
0,                  // destination offset
      
objectArray0.byteLength  // size
  
);
                                
  
// Submit GPU commands.
  
const gpuCommands commandEncoder.finish();
  
await device.queue.submit([gpuCommands]);
 
  
// Read buffer.
  
await objectBufferTmp.mapAsync(GPUMapMode.READ);
  const 
arrayBuffer objectBufferTmp.getMappedRange();
  const array = new 
Float32ArrayarrayBuffer );
  const 
outputArray = Array.from( array );
  
//const arr = Array.from( array );
  
objectBufferTmp.unmap();
  
  
//console.log('outputArray:', outputArray );

  //log('Collision data:')
  
  //for (let i=0; i<arr.length; i++)
  //{
      // display over multiple lines
      //log( arr.splice( 0, 4 ) );  
  //}
  
  
  // Extract the positions and velocities
  
const ctx canvas.getContext('2d');
  
ctx.clearRect(00canvas.widthcanvas.height);
  
//console.log( 'outputArray.length:', outputArray.length );
  
  
drawCirclectx005'black' );
  
  
drawLine(ctx, {x:0,y:0}, {x:50,y:}, 'red' );
  
drawLine(ctx, {x:0,y:0}, {x:00,y:50}, 'green' );
  
  
  
  
  for (var 
02++ )
  {
      
let stride 4*7;
         
//console.log( i ); 
      
     
      // position
      
var px outputArray[i*stride+0];
      var 
py outputArray[i*stride+1];
    
      
//console.log( px, py );
        
      
var angle    outputArray[i*stride+2];
    
      
//var vx = outputArray[i+4];
      //var vy = outputArray[i+5];
    
      
var sx outputArray[i*stride+4];
      var 
sy outputArray[i*stride+5];
    
      var 
pen outputArray[i*stride+8]; 
    
      var 
nx outputArray[i*stride+12];
      var 
ny outputArray[i*stride+13];
    
      var 
hx outputArray[i*stride+16];
      var 
hy outputArray[i*stride+17]; 
      var 
hx2 outputArray[i*stride+18];
      var 
hy2 outputArray[i*stride+19];
    
    
      var 
b0x outputArray[i*stride+20];
      var 
b0y outputArray[i*stride+21];
      var 
b1x outputArray[i*stride+22];
      var 
b1y outputArray[i*stride+23];
    
      if ( 
pen )
      {
          
ctx.font "20px Arial";
          
ctx.fillText'Collision' ,10,40);
      }
    
      
drawCircle(ctxb0x,  b0y+10,  5'blue' );
      
drawCircle(ctxb1x,  b1y-10,  5'blue' );
    
      
drawCircle(ctxhx,  hy,  5'purple' );
      
drawCircle(ctxhx2hy25'orange' );
    
      
//console.log(px, py, sx, sy, angle);

      
      
pen Math.abspen );
      
drawLinectx, {x:hx,y:hy}, {x:hx-nx*pen,y:hy-ny*pen}, 'purple' );
    
    
      {
      
      
let corners =  [ new vec2( -1, -), 
                       new 
vec2(  1, -), 
                       new 
vec2(  1,  ),
                       new 
vec2( -1,  ) ];
  
      
      for (
let g=0g<4g++)
      {
          
let p0 vec2.addrotatePointvec2.mulcorners[g],       new vec2(sx,sy)) , angle ), new vec2(px,py) );
          
let p1 vec2.addrotatePointvec2.mulcorners[(g+1)%4], new vec2(sx,sy)) , angle ), new vec2(px,py) );
        
          
drawLinectxp0p1'black' );
      }
        
      }
      
      
// draw square
      
ctx.strokeStyle 'black';
      
ctx.save();
      
ctx.translate(off.x+pxoff.y+py);
      
ctx.rotate(angle);
      
ctx.beginPath();
      
ctx.rect(   -2*sx/2,   -2*sy/2
                   
2*sx,      2*sy);
      
ctx.stroke();
      
ctx.restore();
  }

  
timestep[0] = timestep[0] + 0.01;
  
device.queue.writeBuffer(timerUniformBuffer,   0timestep );
  
  
mouse[0] = cur.x;
  
mouse[1] = cur.y;
  
device.queue.writeBuffer(mouseUniformBuffer,   0mouse );
  
  
  
  
requestAnimationFrame(frame);
}
// end frame(..)


document.onmousemove = function(e)
{  
  
cur.e.pageX off.x;
  
cur.e.pageY off.y;
}
document.onmousemove( {pageX:450pageY:450} );

frame();




Resources and Links


• WebGPU Lab Demo [LINK]

• Box demo (2d minkowski) [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]














WebGPU by Example: Fractals, Image Effects, Ray-Tracing, Procedural Geometry, 2D/3D, Particles, Simulations WebGPU Compute 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 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 wgsl webgpugems shading language cookbook 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.