packages/core/src/lib/geometry/path-warp.ts
This is the source snapshot used to build these API details. View this revision on GitHub.
1 import { arcPoint } from './path-arc.js';
2 import { PathGeometry } from './path-geometry.js';
3 import { emitSpan, endpoint, product, type WarpPoint, type WarpSpan, type WarpWork } from './path-warp-bezier.js';
4
5 export interface PathWarpPoint { readonly x: number; readonly y: number }
6 export interface PathWarpRect { readonly x: number; readonly y: number; readonly width: number; readonly height: number }
7 export interface PathWarpCorners {
8 readonly topLeft: PathWarpPoint;
9 readonly topRight: PathWarpPoint;
10 readonly bottomLeft: PathWarpPoint;
11 readonly bottomRight: PathWarpPoint;
12 }
13 export type PathWarpMode = 'bilinear' | 'perspective';
14 export interface WarpPathOptions {
15 readonly source: PathWarpRect;
16 readonly destination: PathWarpCorners;
17 readonly mode?: PathWarpMode;
18 readonly tolerance: number;
19 readonly maxSegments?: number;
20 }
21
22 function number(value: unknown, name: string): number {
23 if (typeof value !== 'number') throw new TypeError(`warpPath ${name} must be a number.`);
24 if (!Number.isFinite(value)) throw new RangeError(`warpPath ${name} must be finite.`);
25 return value;
26 }
27 function point(value: PathWarpPoint | undefined, name: string): WarpPoint {
28 return [number(value?.x, `${name}.x`), number(value?.y, `${name}.y`)];
29 }
30 function polynomial(points: readonly WarpPoint[]): WarpSpan {
31 return { x: points.map(p => p[0]), y: points.map(p => p[1]), w: points.map(() => 1) };
32 }
33
34 /** Normalize destination coordinates before solving the unit-square homography. */
35 function perspective(corners: readonly WarpPoint[]): (span: WarpSpan) => WarpSpan {
36 const scale = Math.max(...corners.flatMap(p => [Math.abs(p[0]), Math.abs(p[1])]));
37 if (scale === 0) throw new RangeError('Perspective warp requires a strictly convex quadrilateral.');
38 const normalized = corners.map(p => [p[0] / scale, p[1] / scale] as const);
39 const origin = normalized[0];
40 const extent = Math.max(...normalized.flatMap(p => [Math.abs(p[0] - origin[0]), Math.abs(p[1] - origin[1])]));
41 if (extent === 0) throw new RangeError('Perspective destination is degenerate.');
42 const q = normalized.map(p => [(p[0] - origin[0]) / extent, (p[1] - origin[1]) / extent] as const);
43 const perimeter = [q[0], q[1], q[3], q[2]];
44 let orientation = 0;
45 for (let i = 0; i < 4; i++) {
46 const a = perimeter[i], b = perimeter[(i + 1) % 4], c = perimeter[(i + 2) % 4];
47 const p = (b[0] - a[0]) * (c[1] - b[1]), r = (b[1] - a[1]) * (c[0] - b[0]);
48 const cross = p - r;
49 if (Math.abs(cross) <= 32 * Number.EPSILON * (Math.abs(p) + Math.abs(r)) ||
50 (orientation !== 0 && Math.sign(cross) !== orientation)) {
51 throw new RangeError('Perspective warp requires a strictly convex, nondegenerate quadrilateral.');
52 }
53 orientation = Math.sign(cross);
54 }
55 const [a, b, c, d] = q;
56 const dx1 = b[0] - d[0], dx2 = c[0] - d[0], dx3 = a[0] - b[0] - c[0] + d[0];
57 const dy1 = b[1] - d[1], dy2 = c[1] - d[1], dy3 = a[1] - b[1] - c[1] + d[1];
58 const determinant = dx1 * dy2 - dx2 * dy1;
59 if (Math.abs(determinant) <= 32 * Number.EPSILON * (Math.abs(dx1 * dy2) + Math.abs(dx2 * dy1))) {
60 throw new RangeError('Perspective mapping is numerically singular.');
61 }
62 const g = (dx3 * dy2 - dx2 * dy3) / determinant;
63 const h = (dx1 * dy3 - dx3 * dy1) / determinant;
64 if ([1 + g, 1 + h, 1 + g + h].some(w => w <= 64 * Number.EPSILON * (1 + Math.abs(g) + Math.abs(h)))) {
65 throw new RangeError('Perspective mapping cannot certify a finite source rectangle.');
66 }
67 const xx = b[0] - a[0] + g * b[0], xy = c[0] - a[0] + h * c[0];
68 const yx = b[1] - a[1] + g * b[1], yy = c[1] - a[1] + h * c[1];
69 return span => {
70 const w = span.w.map((weight, i) => g * span.x[i] + h * span.y[i] + weight);
71 const x = w.map((weight, i) => ((xx * span.x[i] + xy * span.y[i] + a[0] * span.w[i]) * extent + origin[0] * weight) * scale);
72 const y = w.map((weight, i) => ((yx * span.x[i] + yy * span.y[i] + a[1] * span.w[i]) * extent + origin[1] * weight) * scale);
73 return { x, y, w };
74 };
75 }
76
77 /** Approximate a four-corner warp in destination units, returning independent line geometry. */
78 export function warpPath(path: PathGeometry, options: Readonly<WarpPathOptions>): PathGeometry {
79 if (!(path instanceof PathGeometry)) throw new TypeError('warpPath requires PathGeometry.');
80 const source = options?.source, destination = options?.destination;
81 const sx = number(source?.x, 'source.x'), sy = number(source?.y, 'source.y');
82 const width = number(source?.width, 'source.width'), height = number(source?.height, 'source.height');
83 const tolerance = number(options?.tolerance, 'tolerance');
84 const requestedLimit = options?.maxSegments;
85 const maxSegments = number(requestedLimit === undefined ? 1_000_000 : requestedLimit, 'maxSegments');
86 if (width <= 0 || height <= 0 || tolerance <= 0 || !Number.isSafeInteger(maxSegments) || maxSegments <= 0) {
87 throw new RangeError('warpPath requires positive dimensions, tolerance, and a positive safe-integer maxSegments.');
88 }
89 const requestedMode = options?.mode;
90 const mode = requestedMode === undefined ? 'bilinear' : requestedMode;
91 if (mode !== 'bilinear' && mode !== 'perspective') throw new TypeError('Unknown warpPath mode.');
92 const corners = [point(destination?.topLeft, 'topLeft'), point(destination?.topRight, 'topRight'),
93 point(destination?.bottomLeft, 'bottomLeft'), point(destination?.bottomRight, 'bottomRight')];
94 const project = mode === 'perspective' ? perspective(corners) : undefined;
95 const map = (span: WarpSpan): WarpSpan => {
96 const u = span.x.map((x, i) => (x - sx * span.w[i]) / width);
97 const v = span.y.map((y, i) => (y - sy * span.w[i]) / height);
98 if (project) return project({ x: u, y: v, w: span.w });
99 const wu = span.w.map((w, i) => w - u[i]), wv = span.w.map((w, i) => w - v[i]);
100 const weights = [product(wu, wv), product(u, wv), product(wu, v), product(u, v)];
101 const w = product(span.w, span.w);
102 const x = w.map((_, i) => weights.reduce((sum, ws, j) => sum + ws[i] * corners[j][0], 0));
103 const y = w.map((_, i) => weights.reduce((sum, ws, j) => sum + ws[i] * corners[j][1], 0));
104 return { x, y, w };
105 };
106 const output = new PathGeometry();
107 let count = 0, closed = false;
108 const reserve = () => {
109 if (++count > maxSegments) throw new RangeError('warpPath exceeded maxSegments.');
110 };
111 const line = (x: number, y: number) => { reserve(); output.lineTo(x, y); closed = false; };
112 // At most 4M subdivision visits per call, even for a pole with no output.
113 const work: WarpWork = { remaining: Math.min(4_000_000, 2 * maxSegments + 53), pool: [], depths: [], scratch: [] };
114 const emit = (span: WarpSpan) => {
115 if (count >= maxSegments) throw new RangeError('warpPath exceeded maxSegments.');
116 emitSpan(map(span), tolerance, work, line);
117 };
118 let current: WarpPoint = [0, 0], start: WarpPoint = current;
119 for (const segment of path) {
120 switch (segment.type) {
121 case 'move': {
122 current = start = [segment.x, segment.y];
123 const p = endpoint(map(polynomial([current])), 0);
124 reserve(); output.moveTo(p[0], p[1]); closed = false;
125 break;
126 }
127 case 'line': {
128 const end: WarpPoint = [segment.x, segment.y];
129 emit(polynomial([current, end])); current = end; break;
130 }
131 case 'quadratic': {
132 const end: WarpPoint = [segment.x, segment.y];
133 emit(polynomial([current, [segment.cpx, segment.cpy], end])); current = end; break;
134 }
135 case 'cubic': {
136 const end: WarpPoint = [segment.x, segment.y];
137 emit(polynomial([current, [segment.cp1x, segment.cp1y], [segment.cp2x, segment.cp2y], end]));
138 current = end; break;
139 }
140 case 'arc': {
141 const first = arcPoint(segment, segment.startAngle);
142 if (current[0] !== first[0] || current[1] !== first[1]) emit(polynomial([current, first]));
143 const pieces = Math.max(1, Math.ceil(Math.abs(segment.sweep) / (Math.PI / 2)));
144 for (let i = 0; i < pieces; i++) {
145 const a = segment.startAngle + segment.sweep * i / pieces;
146 const b = segment.startAngle + segment.sweep * (i + 1) / pieces;
147 const mid = (a + b) / 2, weight = Math.cos((b - a) / 2);
148 const p = arcPoint(segment, a), q = arcPoint(segment, b);
149 emit({
150 x: [p[0], segment.cx * weight + segment.ux * Math.cos(mid) + segment.vx * Math.sin(mid), q[0]],
151 y: [p[1], segment.cy * weight + segment.uy * Math.cos(mid) + segment.vy * Math.sin(mid), q[1]],
152 w: [1, weight, 1],
153 });
154 }
155 current = arcPoint(segment, segment.startAngle + segment.sweep);
156 break;
157 }
158 case 'close':
159 if (current[0] !== start[0] || current[1] !== start[1]) emit(polynomial([current, start]));
160 if (!closed) { reserve(); output.closePath(); closed = true; }
161 current = start; break;
162 }
163 }
164 return output;
165 }
166 Documentation version
Section titled “Documentation version”Documentation built with @pibbl/core 0.0.2, revision 272a94a. ALPHA — NOT FOR PRODUCTION USE.