Warping points based on two corresponding sets of four corners, based on Projective Mappings for Image Warping by Paul Heckbert.
I had first tried a version that pre-solves the system of equations. It seems to work but the unreduced arithmetic from inverting an 8x8 matrix is... long.
| <!DOCTYPE html> | |
| <html lang="en"> | |
| <head> | |
| <meta charset="utf-8" /> | |
| <style> | |
| path { | |
| fill: none; | |
| stroke-width: 3px; | |
| stroke: #000; | |
| stroke-linejoin: round; | |
| } | |
| circle { | |
| fill: #0eb8ba; | |
| stroke: none; | |
| } | |
| </style> | |
| </head> | |
| <body> | |
| <div></div> | |
| <script src="https://cdnjs.cloudflare.com/ajax/libs/d3/3.5.17/d3.min.js"></script> | |
| <script src="warper.js"></script> | |
| <script> | |
| var width = 500, | |
| height = 500; | |
| var svg = d3.select("body").append("svg") | |
| .attr("width", 960) | |
| .attr("height", 500) | |
| .append("g") | |
| .attr("transform", "translate(180)"); | |
| var points = d3.range(225).map(function(i){ | |
| return [ | |
| width / 4 + (i % 15 + 1) * width / 32, | |
| height / 4 + (Math.floor(i / 15) + 1) * height / 32 | |
| ] | |
| }); | |
| var square = getCorners(true); | |
| var quad = svg.append("path") | |
| .datum(square) | |
| .call(updateQuad); | |
| var circles = svg.selectAll("circle") | |
| .data(points) | |
| .enter() | |
| .append("circle") | |
| .attr("r", 2) | |
| .call(updatePoint); | |
| warp(); | |
| function warp() { | |
| var current = quad.datum(), | |
| next = current === square ? getCorners() : square, | |
| projection = warper(current,next); | |
| circles.data(circles.data().map(projection)) | |
| .transition() | |
| .delay(100) | |
| .duration(750) | |
| .call(updatePoint); | |
| quad.datum(next) | |
| .transition() | |
| .delay(100) | |
| .duration(750) | |
| .call(updateQuad) | |
| .each("end",warp); | |
| } | |
| function updateQuad(sel) { | |
| sel.attr("d",function(d){ | |
| return "M" + d.join("L") + "Z"; | |
| }); | |
| } | |
| function updatePoint(sel) { | |
| sel.attr("cx",function(d){ | |
| return d[0]; | |
| }) | |
| .attr("cy",function(d){ | |
| return d[1]; | |
| }); | |
| } | |
| function getCorners(sq) { | |
| return d3.range(4).map(function(i){ | |
| return [ | |
| ((i % 3 ? 1 : 0) + (sq ? 0.5 : 0.1 + Math.random() * 0.8)) * width / 2, | |
| (Math.floor(i / 2) + (sq ? 0.5 : 0.1 + Math.random() * 0.8)) * height / 2 | |
| ]; | |
| }); | |
| } | |
| </script> | |
| </body> | |
| </html> |
| function warper(start,end) { | |
| var u0 = start[0][0], | |
| v0 = start[0][1], | |
| u1 = start[1][0], | |
| v1 = start[1][1], | |
| u2 = start[2][0], | |
| v2 = start[2][1], | |
| u3 = start[3][0], | |
| v3 = start[3][1], | |
| x0 = end[0][0], | |
| y0 = end[0][1], | |
| x1 = end[1][0], | |
| y1 = end[1][1], | |
| x2 = end[2][0], | |
| y2 = end[2][1], | |
| x3 = end[3][0], | |
| y3 = end[3][1]; | |
| var square = [ | |
| [u0,v0,1,0,0,0,-u0 * x0,-v0 * x0], | |
| [u1,v1,1,0,0,0,-u1 * x1,-v1 * x1], | |
| [u2,v2,1,0,0,0,-u2 * x2,-v2 * x2], | |
| [u3,v3,1,0,0,0,-u3 * x3,-v3 * x3], | |
| [0,0,0,u0,v0,1,-u0 * y0,-v0 * y0], | |
| [0,0,0,u1,v1,1,-u1 * y1,-v1 * y1], | |
| [0,0,0,u2,v2,1,-u2 * y2,-v2 * y2], | |
| [0,0,0,u3,v3,1,-u3 * y3,-v3 * y3] | |
| ]; | |
| var inverted = invert(square); | |
| var s = multiply(inverted,[x0,x1,x2,x3,y0,y1,y2,y3]); | |
| return function(p) { | |
| return [ | |
| (s[0] * p[0] + s[1] * p[1] + s[2]) / (s[6] * p[0] + s[7] * p[1] + 1), | |
| (s[3] * p[0] + s[4] * p[1] + s[5]) / (s[6] * p[0] + s[7] * p[1] + 1) | |
| ]; | |
| }; | |
| } | |
| function multiply(matrix,vector) { | |
| return matrix.map(function(row){ | |
| var sum = 0; | |
| row.forEach(function(c,i){ | |
| sum += c * vector[i]; | |
| }); | |
| return sum; | |
| }); | |
| } | |
| function invert(matrix) { | |
| var size = matrix.length, | |
| base, | |
| swap, | |
| augmented; | |
| // Augment w/ identity matrix | |
| augmented = matrix.map(function(row,i){ | |
| return row.slice(0).concat(row.slice(0).map(function(d,j){ | |
| return j === i ? 1 : 0; | |
| })); | |
| }); | |
| // Process each row | |
| for (var r = 0; r < size; r++) { | |
| base = augmented[r][r]; | |
| // Zero on diagonal, swap with a lower row | |
| if (!base) { | |
| for (var rr = r + 1; rr < size; rr++) { | |
| if (augmented[rr][r]) { | |
| // swap | |
| swap = augmented[rr]; | |
| augmented[rr] = augmented[r]; | |
| augmented[r] = swap; | |
| base = augmented[r][r]; | |
| break; | |
| } | |
| } | |
| if (!base) { | |
| throw new Error("Not invertable :("); | |
| } | |
| } | |
| // 1 on the diagonal | |
| for (var c = 0; c < size * 2; c++) { | |
| augmented[r][c] = augmented[r][c] / base; | |
| } | |
| // Zeroes elsewhere | |
| for (var q = 0; q < size; q++) { | |
| if (q !== r) { | |
| base = augmented[q][r]; | |
| for (var p = 0; p < size * 2; p++) { | |
| augmented[q][p] -= base * augmented[r][p]; | |
| } | |
| } | |
| } | |
| } | |
| return augmented.map(function(row){ | |
| return row.slice(size); | |
| }); | |
| } |
