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.
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
<?php
let div = document.createElement('div');
document.body.appendChild( div );
div.style['font-size'] = '20pt';
function log( s )
{
console.log( s );
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.appendChild( canvas ); canvas.height = canvas.width = 600;
// -------------------------------------------------------------------
function rand(lo, hi)
{
return lo + Math.random() * (hi - lo);
}
// -------------------------------------------------------------------
// Grouped data into vec4 groups - help with alignment/packing
const NUMBER_OBJECTS = 2;
const SIZE_EACH_OBJECT = 4 * 4 * 7; // Number floats for each object structure (vel, pos, size, ..)
const objectArray0 = new Float32Array( NUMBER_OBJECTS * SIZE_EACH_OBJECT );
const objectBuffer0 = device.createBuffer({ size: objectArray0.byteLength, usage: GPUBufferUsage.STORAGE | GPUBufferUsage.COPY_DST | GPUBufferUsage.COPY_SRC });
device.queue.writeBuffer(objectBuffer0, 0, objectArray0);
const objectBufferTmp = device.createBuffer({ size: objectArray0.byteLength, usage: GPUBufferUsage.COPY_DST | GPUBufferUsage.MAP_READ });
// ----------------------------------------------------------------
const timestep = new Float32Array( [0.0] );
const timerUniformBuffer = device.createBuffer({ size: timestep.byteLength, usage: GPUBufferUsage.UNIFORM | GPUBufferUsage.COPY_DST });
device.queue.writeBuffer(timerUniformBuffer, 0, timestep );
// ----------------------------------------------------------------
const mouse = new Float32Array( [0.0, 0.0] );
const mouseUniformBuffer = device.createBuffer({ size: mouse.byteLength, usage: GPUBufferUsage.UNIFORM | GPUBufferUsage.COPY_DST });
device.queue.writeBuffer(mouseUniformBuffer, 0, mouse );
// ----------------------------------------------------------
// Bind group layout and bind group
const bindGroupLayout = device.createBindGroupLayout({
entries: [
{binding: 0, visibility: GPUShaderStage.COMPUTE, buffer: { type: "uniform" } },
{binding: 1, visibility: GPUShaderStage.COMPUTE, buffer: { type: "uniform" } },
{binding: 2, visibility: GPUShaderStage.COMPUTE, buffer: { type: "storage" } }
]
});
const bindGroup0 = device.createBindGroup({ layout: bindGroupLayout,
entries: [ { binding: 0, resource: { buffer: timerUniformBuffer } },
{ binding: 1, resource: { buffer: mouseUniformBuffer } },
{ binding: 2, resource: { buffer: objectBuffer0 } }
] });
// 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:200, y:200};
let cur = {x:0, y:0};
async function drawCircle(ctx, px, py, r, color='blue')
{
// Draw circle
ctx.strokeStyle = color;
ctx.beginPath();
ctx.arc(off.x+px, off.y+py, r, 0, Math.PI * 2);
ctx.stroke(); // Draw outline
ctx.closePath();
}
async function drawLine(ctx, p0, p1, color='green' )
{
ctx.strokeStyle = color;
ctx.beginPath();
ctx.moveTo(off.x+p0.x, off.y+p0.y);
ctx.lineTo(off.x+p1.x, off.y+p1.y);
ctx.closePath();
ctx.stroke();
}
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 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); }
async function frame()
{
// Commands submission
const commandEncoder = device.createCommandEncoder();
{
const passEncoder = commandEncoder.beginComputePass();
passEncoder.setPipeline(computePipeline);
passEncoder.setBindGroup(0, bindGroup0);
// workgroup size on the wgsl shader
passEncoder.dispatchWorkgroups( 1 );
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 Float32Array( arrayBuffer );
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(0, 0, canvas.width, canvas.height);
//console.log( 'outputArray.length:', outputArray.length );
drawCircle( ctx, 0, 0, 5, 'black' );
drawLine(ctx, {x:0,y:0}, {x:50,y:0 }, 'red' );
drawLine(ctx, {x:0,y:0}, {x:00,y:50}, 'green' );
for (var i = 0; i < 2; i ++ )
{
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 < 0 )
{
ctx.font = "20px Arial";
ctx.fillText( 'Collision' ,10,40);
}
drawCircle(ctx, b0x, b0y+10, 5, 'blue' );
drawCircle(ctx, b1x, b1y-10, 5, 'blue' );
drawCircle(ctx, hx, hy, 5, 'purple' );
drawCircle(ctx, hx2, hy2, 5, 'orange' );
//console.log(px, py, sx, sy, angle);
pen = Math.abs( pen );
drawLine( ctx, {x:hx,y:hy}, {x:hx-nx*pen,y:hy-ny*pen}, 'purple' );
{
let corners = [ new vec2( -1, -1 ),
new vec2( 1, -1 ),
new vec2( 1, 1 ),
new vec2( -1, 1 ) ];
for (let g=0; g<4; g++)
{
let p0 = vec2.add( rotatePoint( vec2.mul( corners[g], new vec2(sx,sy)) , angle ), new vec2(px,py) );
let p1 = vec2.add( rotatePoint( vec2.mul( corners[(g+1)%4], new vec2(sx,sy)) , angle ), new vec2(px,py) );
drawLine( ctx, p0, p1, 'black' );
}
}
// draw square
ctx.strokeStyle = 'black';
ctx.save();
ctx.translate(off.x+px, off.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, 0, timestep );
mouse[0] = cur.x;
mouse[1] = cur.y;
device.queue.writeBuffer(mouseUniformBuffer, 0, mouse );
requestAnimationFrame(frame);
}// end frame(..)
document.onmousemove = function(e)
{
cur.x = e.pageX - off.x;
cur.y = e.pageY - off.y;
}
document.onmousemove( {pageX:450, pageY:450} );
frame();
