three_rs/extras/shape_path.rs
1//! Port of `three.js/src/extras/core/ShapePath.js`.
2
3use super::curve::Curve;
4use super::path::Path;
5use super::shape::Shape;
6use super::shape_utils;
7use crate::math::{Box2, Color, Vector2};
8
9/// The SVG fill rule [`ShapePath::to_shapes`] resolves nesting with; three.js
10/// reads it from `userData.style.fillRule`, a string, and falls back to
11/// `'nonzero'` (with a warning) for anything else. An enum has no "anything
12/// else", so the fallback has nothing to do here.
13#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
14pub enum FillRule {
15 /// `'nonzero'`, the default.
16 #[default]
17 NonZero,
18 /// `'evenodd'`.
19 EvenOdd,
20}
21
22/// `ShapePath`: a set of sub-paths, drawn with a canvas-like API, that
23/// [`to_shapes`](Self::to_shapes) resolves into [`Shape`]s with holes.
24#[derive(Clone, Debug, Default)]
25pub struct ShapePath {
26 /// The color of the shape.
27 pub color: Color,
28 /// The paths.
29 pub sub_paths: Vec<Path>,
30 /// Index into `sub_paths` of the path being drawn — three.js'
31 /// `currentPath`, a reference to the last `moveTo`'s path.
32 current_path: Option<usize>,
33 /// `userData.style.fillRule`.
34 pub fill_rule: FillRule,
35}
36
37impl ShapePath {
38 /// `new ShapePath()`.
39 pub fn new() -> Self {
40 Self::default()
41 }
42
43 /// `ShapePath.type`.
44 pub fn type_name(&self) -> &'static str {
45 "ShapePath"
46 }
47
48 /// three.js' `currentPath`. Panics where three.js would throw on `null`: a
49 /// drawing call before the first `moveTo`.
50 fn current_path(&mut self) -> &mut Path {
51 let index = self
52 .current_path
53 .expect("three-rs: ShapePath: a drawing call before moveTo (three.js throws on the null currentPath)");
54 &mut self.sub_paths[index]
55 }
56
57 /// `ShapePath.moveTo( x, y )`: starts a new sub-path.
58 pub fn move_to(&mut self, x: f64, y: f64) -> &mut Self {
59 let mut path = Path::new();
60 path.move_to(x, y);
61 self.sub_paths.push(path);
62 self.current_path = Some(self.sub_paths.len() - 1);
63
64 self
65 }
66
67 /// `ShapePath.lineTo( x, y )`.
68 pub fn line_to(&mut self, x: f64, y: f64) -> &mut Self {
69 self.current_path().line_to(x, y);
70
71 self
72 }
73
74 /// `ShapePath.quadraticCurveTo( aCPx, aCPy, aX, aY )`.
75 pub fn quadratic_curve_to(
76 &mut self,
77 a_c_px: f64,
78 a_c_py: f64,
79 a_x: f64,
80 a_y: f64,
81 ) -> &mut Self {
82 self.current_path()
83 .quadratic_curve_to(a_c_px, a_c_py, a_x, a_y);
84
85 self
86 }
87
88 /// `ShapePath.bezierCurveTo( aCP1x, aCP1y, aCP2x, aCP2y, aX, aY )`.
89 pub fn bezier_curve_to(
90 &mut self,
91 a_cp1x: f64,
92 a_cp1y: f64,
93 a_cp2x: f64,
94 a_cp2y: f64,
95 a_x: f64,
96 a_y: f64,
97 ) -> &mut Self {
98 self.current_path()
99 .bezier_curve_to(a_cp1x, a_cp1y, a_cp2x, a_cp2y, a_x, a_y);
100
101 self
102 }
103
104 /// `ShapePath.splineThru( pts )`.
105 pub fn spline_thru(&mut self, pts: &[Vector2]) -> &mut Self {
106 self.current_path().spline_thru(pts);
107
108 self
109 }
110
111 /// `ShapePath.toShapes()`: classifies every sub-path as an outer shape, a
112 /// hole in one, or a redundant overlap, by winding number under
113 /// [`fill_rule`](Self::fill_rule), and builds the shapes.
114 pub fn to_shapes(&self) -> Vec<Shape> {
115 // Point-in-polygon test using the even-odd ray-casting rule. Valid for
116 // simple (non self-intersecting) polygons.
117
118 fn point_in_polygon(p: &Vector2, polygon: &[Vector2]) -> bool {
119 let mut inside = false;
120 let n = polygon.len();
121
122 let mut j = n.wrapping_sub(1);
123 for i in 0..n {
124 let a = &polygon[i];
125 let b = &polygon[j];
126
127 if (a.y > p.y) != (b.y > p.y) && p.x < (b.x - a.x) * (p.y - a.y) / (b.y - a.y) + a.x
128 {
129 inside = !inside;
130 }
131
132 j = i;
133 }
134
135 inside
136 }
137
138 // Returns a point guaranteed to be strictly inside the given simple
139 // polygon. First tries the bounding-box center; if that falls outside
140 // the polygon, casts a horizontal ray at the center's y and picks the
141 // midpoint between the first two sorted intercepts.
142 //
143 // Port of paper.js' Path#getInteriorPoint()
144 // https://github.com/paperjs/paper.js/blob/develop/src/path/PathItem.Boolean.js
145
146 fn get_interior_point(polygon: &[Vector2], bounding_box: &Box2) -> Vector2 {
147 let mut point = bounding_box.get_center();
148
149 if point_in_polygon(&point, polygon) {
150 return point;
151 }
152
153 let y = point.y;
154 let mut intercepts: Vec<f64> = Vec::new();
155 let n = polygon.len();
156
157 for i in 0..n {
158 let a = &polygon[i];
159 let b = &polygon[(i + 1) % n];
160
161 // Half-open crossing rule — counts each vertex exactly once and
162 // skips horizontal edges.
163 if (a.y > y) != (b.y > y) {
164 let x = a.x + (y - a.y) * (b.x - a.x) / (b.y - a.y);
165 intercepts.push(x);
166 }
167 }
168
169 if intercepts.len() > 1 {
170 intercepts.sort_by(|a, b| js_compare(a - b));
171 point.x = (intercepts[0] + intercepts[1]) / 2.0;
172 }
173
174 point
175 }
176
177 // Predicate that decides whether a winding number falls inside the fill
178 // region, per the SVG fill-rule spec. Works for negative windings too,
179 // because two's complement AND preserves odd/even.
180
181 let fill_rule = self.fill_rule;
182 let is_inside = |w: i64| match fill_rule {
183 FillRule::NonZero => w != 0,
184 FillRule::EvenOdd => (w & 1) != 0,
185 };
186
187 // Build an entry per usable subpath. Self-winding follows the standard
188 // convention used by ShapeUtils: counter-clockwise (signed area > 0)
189 // contributes +1 to the winding number at an interior point,
190 // clockwise contributes -1.
191
192 #[derive(Clone, Copy, PartialEq)]
193 enum Role {
194 Outer,
195 Hole,
196 }
197
198 struct Entry<'a> {
199 sub_path: &'a Path,
200 points: Vec<Vector2>,
201 bounding_box: Box2,
202 interior_point: Vector2,
203 abs_area: f64,
204 winding: i64,
205 container: Option<usize>,
206 exclude: bool,
207 role: Option<Role>,
208 }
209
210 let mut entries: Vec<Entry> = Vec::new();
211
212 for sub_path in &self.sub_paths {
213 // `subPath.getPoints()`: `CurvePath.getPoints`' default of 12.
214 let points = sub_path.get_points(12);
215 if points.len() < 3 {
216 continue;
217 }
218
219 let area = shape_utils::area(&points);
220 if area == 0.0 {
221 continue;
222 }
223
224 let mut bounding_box = Box2::default();
225 for point in &points {
226 bounding_box.expand_by_point(point);
227 }
228
229 let interior_point = get_interior_point(&points, &bounding_box);
230
231 entries.push(Entry {
232 sub_path,
233 points,
234 bounding_box,
235 interior_point,
236 abs_area: area.abs(),
237 winding: if area < 0.0 { -1 } else { 1 },
238 container: None,
239 exclude: false,
240 role: None,
241 });
242 }
243
244 // Sort by area descending. This guarantees that any subpath that could
245 // contain `entries[i]` is located at a smaller index and has already
246 // been processed when it's entries[i]'s turn. Port of paper.js'
247 // reorientPaths() algorithm. (`Array.prototype.sort` is stable, as
248 // `sort_by` is.)
249
250 entries.sort_by(|a, b| js_compare(b.abs_area - a.abs_area));
251
252 // Walk already-processed entries from closest-in-size to largest,
253 // stopping at the innermost container. Accumulate the container's
254 // cumulative winding into this entry's winding so that the final value
255 // equals the winding number at this entry's interior point.
256 //
257 // A subpath only contributes to the fill boundary when crossing it
258 // actually flips the "insideness" per the fill rule; otherwise it's a
259 // redundant overlap and gets excluded to avoid double-counting.
260
261 for i in 0..entries.len() {
262 let mut container_winding = 0;
263
264 for j in (0..i).rev() {
265 let candidate = &entries[j];
266
267 if !candidate
268 .bounding_box
269 .contains_box(&entries[i].bounding_box)
270 {
271 continue;
272 }
273 if !point_in_polygon(&entries[i].interior_point, &candidate.points) {
274 continue;
275 }
276
277 let container = if candidate.exclude {
278 candidate.container
279 } else {
280 Some(j)
281 };
282 container_winding = candidate.winding;
283
284 let entry = &mut entries[i];
285 entry.container = container;
286 entry.winding += container_winding;
287 break;
288 }
289
290 if is_inside(entries[i].winding) == is_inside(container_winding) {
291 entries[i].exclude = true;
292 }
293 }
294
295 // Classify retained entries. An entry is an outer shape if it has no
296 // container or if its container is itself a hole (a solid nested inside
297 // a hole becomes a new top-level shape); otherwise it's a hole in its
298 // container. Entries were already sorted outermost-first, so each
299 // container's role is known by the time we look at it.
300
301 for i in 0..entries.len() {
302 if entries[i].exclude {
303 continue;
304 }
305
306 let role = match entries[i].container {
307 None => Role::Outer,
308 Some(c) if entries[c].role == Some(Role::Hole) => Role::Outer,
309 Some(_) => Role::Hole,
310 };
311 entries[i].role = Some(role);
312 }
313
314 // Build Shapes for outers first, then attach holes to their container's
315 // Shape. (`shape.curves = entry.subPath.curves` shares the curves;
316 // sharing the `Rc`s is the same thing.)
317
318 let mut shapes: Vec<Shape> = Vec::new();
319 let mut shape_by_entry: Vec<Option<usize>> = vec![None; entries.len()];
320
321 for (i, entry) in entries.iter().enumerate() {
322 if entry.exclude || entry.role != Some(Role::Outer) {
323 continue;
324 }
325
326 let mut shape = Shape::new();
327 shape.curves = entry.sub_path.curves.clone();
328 shapes.push(shape);
329 shape_by_entry[i] = Some(shapes.len() - 1);
330 }
331
332 for entry in &entries {
333 if entry.exclude || entry.role != Some(Role::Hole) {
334 continue;
335 }
336
337 let Some(shape) = entry.container.and_then(|c| shape_by_entry[c]) else {
338 continue;
339 };
340
341 let mut hole = Path::new();
342 hole.curves = entry.sub_path.curves.clone();
343 shapes[shape].holes.push(hole);
344 }
345
346 shapes
347 }
348}
349
350/// A JS comparator's return value as an `Ordering`: negative is less,
351/// positive greater, and zero or `NaN` equal.
352fn js_compare(result: f64) -> std::cmp::Ordering {
353 if result < 0.0 {
354 std::cmp::Ordering::Less
355 } else if result > 0.0 {
356 std::cmp::Ordering::Greater
357 } else {
358 std::cmp::Ordering::Equal
359 }
360}