packages/core/src/lib/geometry/transform-guide.ts
This is the source snapshot used to build these API details. View this revision on GitHub.
1 import type { MeshTransformOptions } from './transform-mesh.js';
2 import type { EnvelopeGuide, EnvelopeTransformOptions } from './path-transforms.js';
3 import { PathGeometry } from './path-geometry.js';
4 import {
5 bendSpans,
6 bendSpanPoint,
7 bendSpanBounds,
8 splitBendSpan,
9 type BendSpan,
10 type BendPoint,
11 } from './path-bend-spans.js';
12 import {
13 type Jet,
14 type Pair,
15 type Interval,
16 mulI,
17 addI,
18 interval,
19 } from './transform-math.js';
20
21 /**
22 * A station mapping normalized guide position to normalized arc-length distance along its path.
23 *
24 * @see {@link PathGuideOptions}
25 */
26 export interface PathGuideStation {
27 /** Normalized station position. See {@link PathGuideStation}. */
28 readonly at: number;
29 /** Normalized arc-length distance from 0 to 1. See {@link PathGuideStation}. */
30 readonly distance: number;
31 }
32 /**
33 * Geometry and stations that define how a transformation samples a guide.
34 *
35 * @see {@link PathGeometry}
36 * @see {@link PathGuideStation}
37 * @see {@link PathGuide}
38 */
39 export interface PathGuideOptions {
40 /** Path geometry used by this operation. See {@link PathGeometry}. */
41 readonly path: PathGeometry;
42 /** Whether to reverse the direction of the mapping or guide. See {@link PathGuideOptions}. */
43 readonly reverse?: boolean;
44 /**
45 * Explicit correspondence between normalized stations and guide distance. See
46 * {@link PathGuideStation}.
47 */
48 readonly stations?: readonly PathGuideStation[];
49 }
50 /**
51 * A geometry path or a path with explicit guide-sampling configuration.
52 *
53 * @see {@link PathGeometry}
54 * @see {@link PathGuideOptions}
55 * @see {@link MeshTransformOptions}
56 * @see {@link EnvelopeTransformOptions}
57 * @see {@link EnvelopeGuide}
58 */
59 export type PathGuide = PathGeometry | PathGuideOptions;
60 export interface GuideSnapshot {
61 readonly spans: readonly BendSpan[];
62 readonly reverse: boolean;
63 readonly stations: readonly PathGuideStation[];
64 }
65 export interface SampledGuide {
66 readonly error: number;
67 readonly length: number;
68 evaluate(t: Jet): Pair;
69 }
70 export function snapshotGuide(input: PathGuide): GuideSnapshot {
71 const options = input instanceof PathGeometry ? { path: input } : input;
72 if (!(options?.path instanceof PathGeometry))
73 throw new TypeError('A guide requires PathGeometry.');
74 if (options.reverse !== undefined && typeof options.reverse !== 'boolean')
75 throw new TypeError('reverse must be boolean.');
76 const spans: BendSpan[] = [];
77 let moves = 0;
78 for (const item of bendSpans(options.path)) {
79 if (item.type === 'move') moves++;
80 else if (item.type === 'close')
81 throw new RangeError('A guide must be one open contour.');
82 else spans.push(item.span);
83 }
84 if (moves !== 1 || !spans.length)
85 throw new RangeError('A guide must be one nonempty open contour.');
86 const stations = (
87 options.stations ?? [
88 { at: 0, distance: 0 },
89 { at: 1, distance: 1 },
90 ]
91 ).map((s) => ({ at: s.at, distance: s.distance }));
92 if (
93 stations.length < 2 ||
94 stations[0].at !== 0 ||
95 stations[0].distance !== 0 ||
96 stations.at(-1)!.at !== 1 ||
97 stations.at(-1)!.distance !== 1 ||
98 stations.some(
99 (s, i) =>
100 !Number.isFinite(s.at) ||
101 !Number.isFinite(s.distance) ||
102 (i > 0 &&
103 (s.at <= stations[i - 1].at ||
104 s.distance <= stations[i - 1].distance)),
105 )
106 ) {
107 throw new RangeError(
108 'Guide stations must strictly increase from (0,0) to (1,1).',
109 );
110 }
111 return { spans, reverse: options.reverse ?? false, stations };
112 }
113
114 interface Leaf {
115 span: BendSpan;
116 a: BendPoint;
117 b: BendPoint;
118 chord: number;
119 gap: number;
120 sag: number;
121 }
122 function leaf(span: BendSpan): Leaf {
123 const a = bendSpanPoint(span, 0),
124 b = bendSpanPoint(span, 1),
125 chord = Math.hypot(b[0] - a[0], b[1] - a[1]);
126 let upper: number;
127 if ('points' in span)
128 upper = span.points
129 .slice(1)
130 .reduce(
131 (n, p, i) =>
132 n + Math.hypot(p[0] - span.points[i][0], p[1] - span.points[i][1]),
133 0,
134 );
135 else {
136 const arc = span.arc,
137 mid = arc.startAngle + arc.sweep / 2;
138 const speed =
139 Math.abs(arc.sweep) *
140 Math.hypot(
141 -arc.ux * Math.sin(mid) + arc.vx * Math.cos(mid),
142 -arc.uy * Math.sin(mid) + arc.vy * Math.cos(mid),
143 );
144 const bounds = bendSpanBounds(span);
145 upper = speed + Math.hypot(bounds.ddx, bounds.ddy) / 4;
146 }
147 const gap = Math.max(0, upper - chord);
148 // Every point lies in the ellipse with these endpoints and total distance <= upper.
149 const sag = Math.sqrt(gap * (upper + chord)) / 2;
150 return { span, a, b, chord, gap, sag };
151 }
152
153 export function sampleGuide(
154 snapshot: GuideSnapshot,
155 accuracy: number,
156 ): SampledGuide {
157 let leaves = snapshot.spans.map(leaf);
158 let gap: number, sag: number;
159 for (let depth = 0; ; depth++) {
160 gap = leaves.reduce((sum, p) => sum + p.gap, 0);
161 sag = leaves.reduce((max, p) => Math.max(max, p.sag), 0);
162 if (sag + 3 * gap <= accuracy) break;
163 if (depth >= 30 || leaves.length > 32768)
164 throw new RangeError('Guide approximation exceeded its work limit.');
165 const share = accuracy / (12 * leaves.length);
166 leaves = leaves.flatMap((p) =>
167 p.gap > share || p.sag > accuracy / 4
168 ? splitBendSpan(p.span).map(leaf)
169 : [p],
170 );
171 }
172 const length = leaves.reduce((sum, p) => sum + p.chord, 0);
173 if (!(length > 0) || !Number.isFinite(length))
174 throw new RangeError('Guide length must be finite and nonzero.');
175 let distance = 0;
176 const points: BendPoint[] = [leaves[0].a],
177 knots = [0];
178 for (const p of leaves) {
179 if (!p.chord) continue;
180 distance += p.chord;
181 points.push(p.b);
182 knots.push(distance / length);
183 }
184 knots[knots.length - 1] = 1;
185 if (snapshot.reverse) {
186 points.reverse();
187 knots.reverse();
188 for (let i = 0; i < knots.length; i++) knots[i] = 1 - knots[i];
189 }
190 const stations = snapshot.stations;
191 const remap = (d: number) => {
192 let i = 0;
193 while (i < stations.length - 2 && d > stations[i + 1].distance) i++;
194 const a = stations[i],
195 b = stations[i + 1];
196 return (
197 a.at + ((d - a.distance) * (b.at - a.at)) / (b.distance - a.distance)
198 );
199 };
200 // Include correspondence breaks, not just geometric polyline vertices.
201 const parameters = [...knots.map(remap), ...stations.map((s) => s.at)]
202 .sort((a, b) => a - b)
203 .filter((v, i, a) => !i || v !== a[i - 1]);
204 const values = parameters.map((t) => {
205 let j = 0;
206 while (j < stations.length - 2 && t > stations[j + 1].at) j++;
207 const a = stations[j],
208 b = stations[j + 1];
209 const d =
210 a.distance + ((t - a.at) * (b.distance - a.distance)) / (b.at - a.at);
211 const i = locate(knots, d),
212 f = (d - knots[i]) / (knots[i + 1] - knots[i]);
213 return [
214 points[i][0] + (points[i + 1][0] - points[i][0]) * f,
215 points[i][1] + (points[i + 1][1] - points[i][1]) * f,
216 ] as BendPoint;
217 });
218 return {
219 error: sag + 3 * gap,
220 length,
221 evaluate: (t) => evaluatePolyline(parameters, values, t),
222 };
223 }
224 function locate(knots: readonly number[], t: number): number {
225 let lo = 0,
226 hi = knots.length - 1;
227 while (hi - lo > 1) {
228 const mid = (lo + hi) >>> 1;
229 if (knots[mid] <= t) lo = mid;
230 else hi = mid;
231 }
232 return Math.min(lo, knots.length - 2);
233 }
234 export function evaluatePolyline(
235 knots: readonly number[],
236 points: readonly BendPoint[],
237 t: Jet,
238 ): Pair {
239 const first = locate(knots, t.v[0]),
240 last = locate(knots, t.v[1]);
241 return [0, 1].map((axis) => {
242 let low = Infinity,
243 high = -Infinity,
244 slopeLow = Infinity,
245 slopeHigh = -Infinity;
246 for (let i = first; i <= last; i++) {
247 const slope =
248 (points[i + 1][axis] - points[i][axis]) / (knots[i + 1] - knots[i]);
249 const a = i === first ? t.v[0] : knots[i],
250 b = i === last ? t.v[1] : knots[i + 1];
251 const va = points[i][axis] + (a - knots[i]) * slope,
252 vb = points[i][axis] + (b - knots[i]) * slope;
253 low = Math.min(low, va, vb);
254 high = Math.max(high, va, vb);
255 slopeLow = Math.min(slopeLow, slope);
256 slopeHigh = Math.max(slopeHigh, slope);
257 }
258 const slopes: Interval = [slopeLow, slopeHigh];
259 return {
260 v: [low, high] as Interval,
261 d: mulI(slopes, t.d),
262 dd: addI(
263 mulI(slopes, t.dd),
264 first === last || slopeLow === slopeHigh
265 ? interval(0)
266 : [-Infinity, Infinity],
267 ),
268 };
269 }) as unknown as Pair;
270 }
271 Documentation version
Section titled “Documentation version”Documentation built with @pibbl/core 0.0.2, revision 272a94a. ALPHA — NOT FOR PRODUCTION USE.