31:T4c7,demo = { reset; let dsp = new Display(); let bodies = []; function refresh() { dsp.clear(); for (let body of bodies) { dsp.drawPolygon(body.worldShape); } } dsp.canvas.onclick = e => { bodies.push( new Body( regularPolygonPoints([0, 0], 40, ~~(Math.random() * 3 + 3)), [e.offsetX, e.offsetY], Math.PI / 4 ) ); }; function physics() { // Integrate bodies.forEach(body => body.timeStep()); // Project collisions among objects and with world box for (let irelax = 0; irelax < 10; irelax++) { bodies.forEach(body => body.projectWalls([0, 0], [dsp.canvas.width, dsp.canvas.height]) ); bodies.forEach(body => body.shapeMatch()); let pairs = sap(bodies.map(body => body.worldShape), [1, 0]); bodies.forEach((body, i) => { pairs[i].forEach(j => body.projectCollision(bodies[j]), irelax); }); bodies.forEach(body => body.shapeMatch()); } bodies.forEach(body => { if (body.collisionShape) body.updateFromShape(body.collisionShape); }); } for (let frame = 0; ; frame++) { await visibility(); physics(); refresh(); yield dsp.canvas; } }32:T182a,class Body { // Constructor. Shape is an array of 2d points constructor(shape, pos = [0, 0], ang = 0, mass = 1) { this.mass = mass; this.pos = this.oldPos = pos; this.ang = this.oldAng = ang; let center = centerOfMass(shape); this.shape = shape.map(p => [p[0] - center[0], p[1] - center[1]]); this.dirty = true; // Tells if worldShape must be recomputed this.collisionShape = null; // Non-null if collision was detected } // Verlet integration timeStep() { let vel = vec2.sub([], this.pos, this.oldPos); vel[1] += g; // Add gravity to velocity this.oldPos = this.pos; this.pos = vec2.add([], this.pos, vec2.scale([], vel, timeStepAttenuation)); let angVel = this.ang - this.oldAng; this.oldAng = this.ang; this.ang += angVel * timeStepAttenuation; this.dirty = true; } // Returns the shape points in world space get worldShape() { if (this.dirty) { // Memoization of the result let [c, s] = [Math.cos(this.ang), Math.sin(this.ang)]; let transf = mat2d.fromValues(c, s, -s, c, this.pos[0], this.pos[1]); this.curWorldShape = transformPoints(this.shape, transf); this.dirty = false; } return this.curWorldShape; } //===================================================================== // Methods for collision response with shape matching // // Projects points of worldShape onto the walls of a rectangle projectWalls(min, max) { let projected = false; let poly = this.collisionShape || this.worldShape.slice(); poly.forEach((p, i) => { for (let [a, b, c] of [ [-1, 0, min[0]], [1, 0, -max[0]], [0, -1, min[1]], [0, 1, -max[1]] ]) { if (a * p[0] + b * p[1] + c >= 0) { p = projectPointLine(p, a, b, c); projected = true; } } poly[i] = p; }); if (projected) this.collisionShape = poly; } // Tests for collision between this body and other, and if true, // performs a projection this object's collisionShape by computing a contact point // using the collision geometry. Updates other as well projectCollision(other, gravityBias = 0) { let a = this.collisionShape || this.worldShape.slice(); let b = other.collisionShape || other.worldShape.slice(); let hit = gjk(a, b); if (hit) { let { p, q, n } = epa(a, b, ...hit); let aPoints = supportEdge(a, n); let bPoints = supportEdge(b, [-n[0], -n[1]]); let [massA, massB] = [this.mass, other.mass]; if (gravityBias) { if (this.pos[1] > other.pos[1]) massA += massB * gravityBias; else massB += massA * gravityBias; } let aContact, bContact, aContactDisplaced, bContactDisplaced, penetration; if (aPoints.length + bPoints.length == 4) { // Edge-edge collision let center = centerOfMass([...aPoints, ...bPoints]); aContact = closestSegmentPoint(center, ...aPoints); bContact = closestSegmentPoint(center, ...bPoints); penetration = vec2.dist(aContact, bContact); aContactDisplaced = vec2.add( [], aContact, vec2.scale([], n, (-penetration * massA) / (massA + massB)) ); bContactDisplaced = vec2.add( [], bContact, vec2.scale([], n, (penetration * massB) / (massA + massB)) ); this.curWorldShape.push(aContact); a.push(aContactDisplaced); other.curWorldShape.push(bContact); b.push(bContactDisplaced); } else { // Vertex-edge collision if (aPoints.length + bPoints.length != 3) { console.log({ aPoints, bPoints }); throw "Weird collision"; } if (aPoints.length == 2) { aContact = closestSegmentPoint(bPoints[0], ...aPoints); penetration = vec2.dist(aContact, bPoints[0]); aContactDisplaced = vec2.add( [], aContact, vec2.scale([], n, (-penetration * massA) / (massA + massB)) ); this.curWorldShape.push(aContact); a.push(aContactDisplaced); bContactDisplaced = vec2.add( [], bPoints[0], vec2.scale([], n, (penetration * massB) / (massA + massB)) ); b.splice(b.lastIndexOf(bPoints[0]), 1, bContactDisplaced); } else { // bPoints.length == 2! bContact = closestSegmentPoint(aPoints[0], ...bPoints); penetration = vec2.dist(aPoints[0], bContact); bContactDisplaced = vec2.add( [], bContact, vec2.scale([], n, (penetration * massB) / (massA + massB)) ); other.curWorldShape.push(bContact); b.push(bContactDisplaced); aContactDisplaced = vec2.add( [], aPoints[0], vec2.scale([], n, (-penetration * massA) / (massA + massB)) ); a.splice(a.lastIndexOf(aPoints[0]), 1, aContactDisplaced); } } this.collisionShape = a; other.collisionShape = b; } } // Shape matches collision shape with the original shape and applies // the resulting rigid transformation to collisionShape shapeMatch() { if (this.collisionShape) { let M = shapeMatch(this.worldShape, this.collisionShape); this.dirty = true; this.collisionShape = transformPoints(this.worldShape, M); } } // Updates rotation and position from the given shape updateFromShape(shape) { // New center of mass let center = centerOfMass(shape); // Rotation component let rot = shapeMatchRotation( this.worldShape.map(p => vec2.sub([], p, this.pos)), shape.map(p => vec2.sub([], p, center)) ); if (!Number.isNaN(rot[0][0])) { // Avoid degenerate projections let dang = Math.atan2(rot[0][1], rot[0][0]); this.ang += dang * shapeMatchAttenuation; } // Translation component this.pos = vec2.lerp([], this.pos, center, shapeMatchAttenuation); // This is the new worldShape this.curWorldShape = shape; this.collisionShape = null; this.dirty = false; } }33:T41b,// // Given an array of source points and an array of destination points as in Fig 3 // of the paper, returns a rigid transformation matrix that best approximates the // transformation from source to destination points. // function shapeMatch (srcPoints, dstPoints) { // The center of mass of the src points let srcCenter = centerOfMass(srcPoints) // src displacement vectors wrt center of mass let srcVectors = srcPoints.map (p => vec2.sub([],p,srcCenter)) // destination points center of mass let dstCenter = centerOfMass(dstPoints) // dst displacement vectors wrt center of mass let dstVectors = dstPoints.map (p => vec2.sub([],p,dstCenter)) // Compute rotation and compose with the two translations let [[a,b],[c,d]] = shapeMatchRotation (srcVectors,dstVectors); return mat2d.mul([], mat2d.fromValues(a,b, c,d, dstCenter[0],dstCenter[1]), mat2d.fromTranslation([],[-srcCenter[0],-srcCenter[1]])) } 34:T549,// Tests collisions among polygons and returns projected points for those // in collision. Returns an array 'newPolygons' where newPolygons [i] is a // projected copy of polygons[i] if it is in collision or null otherwise. function projectCollisions(polygons) { let npoly = polygons.length; let newPolygons = []; // Enhance performance using sweep and prune let pairs = sap(polygons, [1, 0]); for (let i = 0; i < npoly; i++) { let a = polygons[i]; //for (let j = i + 1; j < npoly; j++) { for (let j of pairs[i]) { let b = polygons[j]; let hit = gjk(a, b); if (hit) { let { p, q, n } = epa(a, b, ...hit); let ptsA = supportEdge(a, n); let ptsB = supportEdge(b, [-n[0], -n[1]]); let center = centerOfMass(ptsA.concat(ptsB)); let [ha, hb, hc] = halfSpace(center, n); let acopy = newPolygons[i] || a.slice(); acopy.forEach((pt, i) => { if (ha * pt[0] + hb * pt[1] + hc > 0) acopy[i] = projectPointLine(pt, ha, hb, hc); }); newPolygons[i] = acopy; let bcopy = newPolygons[j] || b.slice(); bcopy.forEach((pt, i) => { if (ha * pt[0] + hb * pt[1] + hc < 0) bcopy[i] = projectPointLine(pt, ha, hb, hc); }); newPolygons[j] = bcopy; } } } return newPolygons; }35:T585,class Display { constructor (w = 640, h = 480) { [this.w,this.h] = [w,h]; this.canvas = html`