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
https://observablehq.com/@esperanc/shape-matching (has full Javascript code)
Comments