| license: MIT | |
| height: 960 | |
| border: no | |
| scroll: no |
Folding a 1-dimensional line with a random crease pattern (mountains and valleys).
It is not guaranteed that every crease pattern is flat-foldable, but it is possible to turn a pattern that is not flat-foldable into one that is by adding creases.
| (function(self) { | |
| // Creases are implicitly stored as elements in the given array that lie | |
| // at indices greater than zero and less than length - 1. The first and last | |
| // elements are the endpoints of a finite line with creases. The length of the | |
| // creases array is 2 less than the length of the line. | |
| function FlatFold(line, creases) { | |
| // Precondition: all points on the line where creases occur are unique. | |
| // No folds required if there are no creases. | |
| if (line.length <= 2) return []; | |
| // Unspecified crease pattern: we only have the locations of folds. | |
| if (creases === undefined) { | |
| // Alternating pattern, traverse the segment from one end to the other. | |
| return line.slice(1, line.length).map((d, i) => line.length - 2 - i); | |
| } | |
| line = line.slice(0); | |
| creases = creases.slice(0); | |
| // Mapping merged index -> original line index. | |
| let m = []; | |
| // Delta encoding of the line segments. | |
| let merged = line.map((d, i, arr) => { | |
| m[i] = i; | |
| return (i === 0) | |
| ? d | |
| : d - arr[i - 1]; | |
| }); | |
| let mergedCreases = [undefined].concat(creases).concat([undefined]); | |
| creases = mergedCreases.slice(0); | |
| let order = (new Array(line.length)).fill(Infinity); | |
| let orderIndex = 0; | |
| while (merged.length > 2) { | |
| let c = findCrimp(merged); | |
| // Crimp. | |
| if (c > -1) { | |
| let x = merged[c], | |
| y = merged[c + 1], | |
| z = merged[c + 2], | |
| newPoint = x - y + z; | |
| order[m[c]] = orderIndex; | |
| order[m[c + 1]] = orderIndex++; | |
| merged.splice(c, 3, newPoint); | |
| mergedCreases.splice(c, 2); | |
| m.splice(c, 2); | |
| continue; | |
| } | |
| // Flat fold. | |
| if (isLeftEndFoldable(merged)) { | |
| merged.splice(0, 1); | |
| mergedCreases.splice(0, 1); | |
| order[m[1]] = orderIndex++; | |
| m.splice(0, 1); | |
| continue; | |
| } | |
| if (isRightEndFoldable(merged)) { | |
| merged.splice(-1, 1); | |
| mergedCreases.splice(-1, 1); | |
| order[m[m.length - 2]] = orderIndex++; | |
| m.splice(-1, 1); | |
| continue; | |
| } | |
| // Add a crease. | |
| let b = findBadCrimp(merged); | |
| if (b > -1) { | |
| q = merged[b + 1]; | |
| line.splice(m[b + 1], 0, line[m[b]] + q / 3); | |
| creases.splice(m[b + 1], 0, !creases[m[b]]); | |
| merged.splice(b + 1, 1, q / 3, q * 2 / 3); | |
| mergedCreases.splice(b + 1, 0, !mergedCreases[b]); | |
| m.splice(b + 1, 0, m[b] + 1); | |
| order.splice(m[b + 1], 0, Infinity); | |
| // Shift mapping indices. | |
| for (let i = b + 2; i < m.length; i++) { | |
| m[i] += 1; | |
| } | |
| continue; | |
| } | |
| // We should never get here. The while loop ensures flat-foldability. | |
| break; | |
| } | |
| return { | |
| line: () => line, | |
| creases: () => creases.slice(1, creases.length - 1), | |
| order: () => order.slice(1, order.length - 1) | |
| } | |
| function findBadCrimp(segment) { | |
| if (segment.length < 4) return -1; | |
| for (let k = 1, n = segment.length - 2; k < n; k++) { | |
| // A crimp requires a M-V or V-M crease pattern. | |
| if ((mergedCreases[k] && mergedCreases[k + 1]) | |
| || (!mergedCreases[k] && !mergedCreases[k + 1]) | |
| && segment[k] > segment[k + 1] | |
| && segment[k + 1] < segment[k + 2]) { | |
| return k; | |
| } | |
| } | |
| return -1; | |
| } | |
| function isLeftEndFoldable(segment) { | |
| if (segment.length < 3) return false; | |
| return segment[1] <= segment[2]; | |
| } | |
| function isRightEndFoldable(segment) { | |
| if (segment.length < 3) return false; | |
| return segment[segment.length - 1] <= segment[segment.length - 2]; | |
| } | |
| function findCrimp(segment) { | |
| if (segment.length < 4) return -1; | |
| for (let k = 1, n = segment.length - 2; k < n; k++) { | |
| // A crimp requires a M-V or V-M crease pattern. | |
| if (!!(mergedCreases[k] ^ mergedCreases[k + 1]) | |
| && segment[k] > segment[k + 1] | |
| && segment[k + 1] < segment[k + 2]) { | |
| return k; | |
| } | |
| } | |
| return -1; | |
| } | |
| } | |
| self.FlatFold = FlatFold; | |
| })(self); |
| <!DOCTYPE html> | |
| <meta charset="utf-8"> | |
| <style> | |
| line { | |
| stroke: rgba(0, 0, 0, 0.2); | |
| fill: none; | |
| stroke-width: 3px; | |
| stroke-linecap: round; | |
| } | |
| circle { | |
| stroke-width: 0.5px; | |
| stroke: rgb(0, 0, 0); | |
| } | |
| </style> | |
| <script src="https://d3js.org/d3.v4.min.js" charset="utf-8"></script> | |
| <script src="flat-fold.js" charset="utf-8"></script> | |
| <body> | |
| <svg width="960px" height="960px"></svg> | |
| </body> | |
| <script> | |
| var svg = d3.select("svg"), | |
| margin = { top: 100, left: 100, right: 100, bottom: 100}, | |
| width = 960, | |
| height = 960, | |
| radius = 3, | |
| seedLo = 7, | |
| seedHi = 12; | |
| svg = svg.append("g") | |
| .attr("transform", translate(margin.left, height / 2)); | |
| var X = d3.scaleLinear() | |
| .domain([0, 1]) | |
| .range([0, width - margin.left - margin.right]); | |
| // Create random creases in a unit interval [0, 1]. | |
| var data = d3.range(d3.randomUniform(seedLo, seedHi)() | 0).map((d, i, arr) => { | |
| return d3.randomUniform()(); | |
| }).sort((a, b) => a - b).filter((d, i, arr) => { | |
| // Ensure minimum distance between creases to avoid vertex overlaps. | |
| return i === 0 || (X(d) - X(arr[i - 1]) > 4 * radius); | |
| }); | |
| // True for mountain fold; false for valley fold. | |
| var creases = data.map((d, i) => d3.randomUniform()() >= 0.2); | |
| data = [0].concat(data).concat([1]); | |
| var chain = svg; | |
| var folding = FlatFold(data, creases); | |
| var foldedOrder = folding.order(); | |
| var foldedLine = folding.line(); | |
| var foldedCreases = folding.creases(); | |
| var max = d3.max(foldedOrder); | |
| var lastIndex = foldedOrder.indexOf(max); | |
| // Create nested chain of groups. | |
| for (let i = 0; i < foldedLine.length - 1; i++) { | |
| chain = chain.selectAll("g") | |
| .data([foldedLine[i]]) | |
| .enter().append("g") | |
| .attr("transform", translate((i > 0 | |
| ? X(foldedLine[i] - foldedLine[i - 1]) | |
| : X(foldedLine[i])), 0)); | |
| chain.append("line") | |
| .attr("x1", 0) | |
| .attr("y1", 0) | |
| .attr("y2", 0) | |
| .attr("x2", X(foldedLine[i + 1]) - X(foldedLine[i])); | |
| // The endpoints are not creases. | |
| if (i > 0 && i < foldedLine.length - 1) { | |
| chain.append("circle") | |
| .attr("cx", 0) | |
| .attr("cy", 0) | |
| .attr("r", radius); | |
| } | |
| } | |
| var stopped = false; | |
| // Keep the segments centered in the viewport. | |
| var timer = d3.timer(function(elapsed) { | |
| let bbox = svg.node().getBBox(), | |
| center = [bbox.x + bbox.width / 2, bbox.y + bbox.height / 2], | |
| dx = width / 2 - center[0], | |
| dy = height / 2 - center[1]; | |
| svg.transition() | |
| .ease(d3.easeLinear) | |
| // Provide a little hysteresis. | |
| .duration(500) | |
| .attr("transform", (d, i) => { | |
| return translate(dx, dy); | |
| }); | |
| if (stopped) timer.stop(); | |
| }); | |
| svg.select("g").selectAll("g") | |
| .style("fill", (d, i) => { | |
| if (data.indexOf(foldedLine[i]) === -1) return "#00FF00"; | |
| return (foldedCreases[i]) ? "#FF0000" : "#0000FF"; | |
| }) | |
| .transition() | |
| .duration(2500) | |
| .delay((d, i) => 2500 * foldedOrder[i]) | |
| .attr("transform", (d, i) => { | |
| let dx = i > 0 ? X(foldedLine[i + 1] - foldedLine[i]) : X(foldedLine[i + 1]); | |
| return translate(dx, 0) + rotate(180 * ((foldedCreases[i]) ? 1 : -1)); | |
| }) | |
| .style("fill", "#000000") | |
| .on("end", function(d, i) { | |
| // The last crease has finished folding. | |
| if (i === lastIndex) { | |
| window.setTimeout(() => { stopped = true; }, 1000); | |
| } | |
| }); | |
| svg.select("g").selectAll("circle") | |
| .transition() | |
| .duration(2500) | |
| .delay((d, i) => 2500 * foldedOrder[i]) | |
| .attr("r", radius / 2); | |
| function translate(x, y) { | |
| return "translate(" + x + "," + y + ")"; | |
| } | |
| function rotate(degrees) { | |
| return "rotate(" + degrees + ")"; | |
| } | |
| </script> |
TODO