top of page
Search
cedarcantab

Shapematching [WIP]

Updated: Mar 22

The shape matching problem

Consider a point set (the black points below) that defines a certain rigid shape. Suppose you move these points to someplace else (blue circles) but you still want to reconstruct the shape as best as possible. What you need then is to compute the rigid transformation that maps the black points to the closest (red) points respecting as well as possible the original constraints (blue points).


Main Simulation Loop


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;

}

}


  //
// 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);
    let det = mat2.determinant([a, b, c, d]);
    if (isNaN(det) || det < 0.9 || det > 1.1) {
      console.log("BUG shapeMatch", { det, a, b, c, d, srcPoints, dstPoints });
      a = d = 1;
      b = c = 0;
      //throw "BUG shapeMatch";
    }
  
    return mat2d.mul(
      [],
      mat2d.fromValues(a, b, c, d, dstCenter[0], dstCenter[1]),
      mat2d.fromTranslation([], [-srcCenter[0], -srcCenter[1]])
    );
  }


Rotation Matrix



  // Solves the rotation part of the shapeMatching problem.
// Given the source and destination vectors, i.e., the points with the translation
// factored out, returns the rotation transformation (a 2x2 matrix)
function shapeMatchRotation (srcVectors, dstVectors) {
  
    // function that computes p x q^T
    let pqT = (p,q) => [[p[0]*q[0],p[0]*q[1]],
                        [p[1]*q[0],p[1]*q[1]]];
    
    // Eq 7
    let Apq = srcVectors.map((p,i) => pqT(p,dstVectors[i])).reduce(mat2sum)
    let ApqTxApq = mat2mul(mat2transpose(Apq),Apq);
    let S = mat2sqrt(ApqTxApq)
    let Sinv = mat2inv(S);
    return mat2mul(Apq,Sinv)
  }




Useful References












1 view0 comments

Recent Posts

See All

p2 naive broadphase

var Broadphase = require('../collision/Broadphase'); module.exports = NaiveBroadphase; /** * Naive broadphase implementation. Does N^2...

sopiro motor constranit

import { Matrix2, Vector2 } from "./math.js"; import { RigidBody } from "./rigidbody.js"; import { Settings } from "./settings.js";...

Comments


記事: Blog2_Post
bottom of page