parry3d/shape/polyline.rs
1use crate::bounding_volume::Aabb;
2use crate::math::{Pose, Vector};
3use crate::partitioning::{Bvh, BvhBuildStrategy};
4use crate::query::{PointProjection, PointQueryWithLocation};
5use crate::shape::composite_shape::CompositeShape;
6use crate::shape::{
7 FeatureId, Segment, SegmentPointLocation, SegmentPseudoNormals, Shape, SubShapeId,
8 TypedCompositeShape,
9};
10#[cfg(feature = "alloc")]
11use alloc::vec::Vec;
12
13use crate::query::details::NormalConstraints;
14
15#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
16#[cfg_attr(
17 feature = "rkyv",
18 derive(rkyv::Archive, rkyv::Deserialize, rkyv::Serialize)
19)]
20#[repr(C)]
21#[derive(Clone, Copy, Debug, Default, Eq, Hash, Ord, PartialEq, PartialOrd)]
22/// Controls how a [`Polyline`] is loaded.
23pub struct PolylineFlags(u8);
24
25bitflags::bitflags! {
26 impl PolylineFlags: u8 {
27 /// If set, the polyline is treated as one-sided: a pseudo-normal is computed at every
28 /// vertex and contact normals are clamped to the outward side, the *right* of each
29 /// segment's direction. The solid must be wound counter-clockwise, so the outward side is
30 /// on the right. This removes the spurious sideways push a body gets at a convex corner of
31 /// a double-sided polyline. This one flag covers what `TriMesh` splits across
32 /// `TriMeshFlags::ORIENTED` (compute pseudo-normals) and `TriMeshFlags::FIX_INTERNAL_EDGES`
33 /// (use them to clamp contacts).
34 #[cfg(feature = "dim2")]
35 const ORIENTED = 1;
36 /// If set, the vertices of this polyline are expected to move between queries while its
37 /// pose stays fixed (see [`Polyline::set_vertices`]).
38 ///
39 /// The contact-manifold queries then never reuse cached contact points (see
40 /// [`CompositeShape::is_deformable`]).
41 const DEFORMABLE = 1 << 1;
42 }
43}
44
45#[derive(Clone, Debug)]
46#[cfg_attr(feature = "serde-serialize", derive(Serialize, Deserialize))]
47#[cfg_attr(
48 feature = "rkyv",
49 derive(rkyv::Archive, rkyv::Deserialize, rkyv::Serialize)
50)]
51/// A polyline shape formed by connected line segments.
52///
53/// A polyline is a sequence of line segments (edges) connecting vertices. It can be open
54/// (not forming a closed loop) or closed (where the last vertex connects back to the first).
55/// Polylines are commonly used for paths, boundaries, and 2D/3D curves.
56///
57/// # Structure
58///
59/// A polyline consists of:
60/// - **Vertices**: Vectors in 2D or 3D space
61/// - **Indices**: Pairs of vertex indices defining each segment
62/// - **BVH**: Bounding Volume Hierarchy for fast spatial queries
63///
64/// # Properties
65///
66/// - **Composite shape**: Made up of multiple segments
67/// - **1-dimensional**: Has length but no volume
68/// - **Flexible topology**: Can be open or closed, branching or linear
69/// - **Accelerated queries**: Uses BVH for efficient collision detection
70///
71/// # Use Cases
72///
73/// Polylines are ideal for:
74/// - **Paths and roads**: Navigation paths, road networks
75/// - **Terrain boundaries**: Cliff edges, coastlines, level boundaries
76/// - **Outlines**: 2D shape outlines, contours
77/// - **Wire frames**: Simplified representations of complex shapes
78/// - **Motion paths**: Character movement paths, camera rails
79///
80/// # Example
81///
82/// ```rust
83/// # #[cfg(all(feature = "dim3", feature = "f32"))] {
84/// use parry3d::shape::Polyline;
85/// use parry3d::math::Vector;
86///
87/// // Create a simple L-shaped polyline
88/// let vertices = vec![
89/// Vector::ZERO,
90/// Vector::new(1.0, 0.0, 0.0),
91/// Vector::new(1.0, 1.0, 0.0),
92/// ];
93///
94/// // Indices are automatically generated to connect consecutive vertices
95/// let polyline = Polyline::new(vertices, None);
96///
97/// // The polyline has 2 segments: (0,1) and (1,2)
98/// assert_eq!(polyline.num_segments(), 2);
99/// assert_eq!(polyline.vertices().len(), 3);
100/// # }
101/// ```
102///
103/// # Custom Connectivity
104///
105/// You can provide custom indices to create non-sequential connections:
106///
107/// ```rust
108/// # #[cfg(all(feature = "dim2", feature = "f32"))] {
109/// use parry2d::shape::Polyline;
110/// use parry2d::math::Vector;
111///
112/// // Create a triangle polyline (closed loop)
113/// let vertices = vec![
114/// Vector::ZERO,
115/// Vector::new(1.0, 0.0),
116/// Vector::new(0.5, 1.0),
117/// ];
118///
119/// // Manually specify edges to create a closed triangle
120/// let indices = vec![
121/// [0, 1], // Bottom edge
122/// [1, 2], // Right edge
123/// [2, 0], // Left edge (closes the loop)
124/// ];
125///
126/// let polyline = Polyline::new(vertices, Some(indices));
127/// assert_eq!(polyline.num_segments(), 3);
128/// # }
129/// ```
130pub struct Polyline {
131 bvh: Bvh,
132 vertices: Vec<Vector>,
133 indices: Vec<[u32; 2]>,
134 /// Per-vertex outward pseudo-normals, present when [`PolylineFlags::ORIENTED`] is set; contact
135 /// normals are then clamped to one side so the polyline acts as a one-sided surface.
136 #[cfg(feature = "dim2")]
137 pseudo_normals: Option<Vec<Vector>>,
138 flags: PolylineFlags,
139}
140
141impl Polyline {
142 /// Creates a new polyline from a vertex buffer and an optional index buffer.
143 ///
144 /// This is the main constructor for creating a polyline. If no indices are provided,
145 /// the vertices will be automatically connected in sequence (vertex 0 to 1, 1 to 2, etc.).
146 ///
147 /// # Arguments
148 ///
149 /// * `vertices` - A vector of points defining the polyline vertices
150 /// * `indices` - Optional vector of `[u32; 2]` pairs defining which vertices connect.
151 /// If `None`, vertices are connected sequentially.
152 ///
153 /// # Returns
154 ///
155 /// A new `Polyline` with an internal BVH for accelerated queries.
156 ///
157 /// # Example
158 ///
159 /// ```
160 /// # #[cfg(all(feature = "dim3", feature = "f32"))] {
161 /// use parry3d::shape::Polyline;
162 /// use parry3d::math::Vector;
163 ///
164 /// // Create a zigzag path with automatic sequential connections
165 /// let vertices = vec![
166 /// Vector::ZERO,
167 /// Vector::new(1.0, 1.0, 0.0),
168 /// Vector::new(2.0, 0.0, 0.0),
169 /// Vector::new(3.0, 1.0, 0.0),
170 /// ];
171 /// let polyline = Polyline::new(vertices, None);
172 /// assert_eq!(polyline.num_segments(), 3);
173 /// # }
174 /// ```
175 ///
176 /// # Custom Connectivity Example
177 ///
178 /// ```
179 /// # #[cfg(all(feature = "dim2", feature = "f32"))] {
180 /// use parry2d::shape::Polyline;
181 /// use parry2d::math::Vector;
182 ///
183 /// // Create a square with custom indices
184 /// let vertices = vec![
185 /// Vector::ZERO,
186 /// Vector::new(1.0, 0.0),
187 /// Vector::new(1.0, 1.0),
188 /// Vector::new(0.0, 1.0),
189 /// ];
190 ///
191 /// // Define edges to form a closed square
192 /// let indices = vec![
193 /// [0, 1], [1, 2], [2, 3], [3, 0]
194 /// ];
195 ///
196 /// let square = Polyline::new(vertices, Some(indices));
197 /// assert_eq!(square.num_segments(), 4);
198 ///
199 /// // Each segment connects the correct vertices
200 /// let first_segment = square.segment(0);
201 /// assert_eq!(first_segment.a, Vector::ZERO);
202 /// assert_eq!(first_segment.b, Vector::new(1.0, 0.0));
203 /// # }
204 /// ```
205 pub fn new(vertices: Vec<Vector>, indices: Option<Vec<[u32; 2]>>) -> Self {
206 // Index from 1 so empty input produces no segments instead of underflowing on `len - 1`.
207 let indices =
208 indices.unwrap_or_else(|| (1..vertices.len() as u32).map(|i| [i - 1, i]).collect());
209 let leaves = indices.iter().enumerate().map(|(i, idx)| {
210 let aabb =
211 Segment::new(vertices[idx[0] as usize], vertices[idx[1] as usize]).local_aabb();
212 (i, aabb)
213 });
214
215 // NOTE: we apply no dilation factor because we won't
216 // update this tree dynamically.
217 let bvh = Bvh::from_iter(BvhBuildStrategy::Binned, leaves);
218
219 Self {
220 bvh,
221 vertices,
222 indices,
223 #[cfg(feature = "dim2")]
224 pseudo_normals: None,
225 flags: PolylineFlags::empty(),
226 }
227 }
228
229 /// Creates a new polyline with the given [`PolylineFlags`] controlling its optional associated
230 /// data, e.g. orientation via `PolylineFlags::ORIENTED` (2D only).
231 ///
232 /// # Example
233 ///
234 /// ```
235 /// # #[cfg(all(feature = "dim2", feature = "f32"))] {
236 /// use parry2d::shape::{Polyline, PolylineFlags};
237 /// use parry2d::math::Vector;
238 ///
239 /// // A unit square wound counter-clockwise, so the solid is inside and outward points away.
240 /// let vertices = vec![
241 /// Vector::new(-1.0, -1.0),
242 /// Vector::new(1.0, -1.0),
243 /// Vector::new(1.0, 1.0),
244 /// Vector::new(-1.0, 1.0),
245 /// ];
246 /// let indices = vec![[0, 1], [1, 2], [2, 3], [3, 0]];
247 /// let polyline = Polyline::with_flags(vertices, Some(indices), PolylineFlags::ORIENTED);
248 ///
249 /// // The bottom edge's outward normal points down, away from the interior.
250 /// let bottom = polyline.segment_normal_constraints(0).unwrap();
251 /// assert!(bottom.face.abs_diff_eq(Vector::new(0.0, -1.0), 1.0e-5));
252 /// # }
253 /// ```
254 pub fn with_flags(
255 vertices: Vec<Vector>,
256 indices: Option<Vec<[u32; 2]>>,
257 flags: PolylineFlags,
258 ) -> Self {
259 let mut result = Self::new(vertices, indices);
260 result.set_flags(flags);
261 result
262 }
263
264 /// Sets the [`PolylineFlags`], computing or discarding the polyline's optional associated data.
265 pub fn set_flags(&mut self, flags: PolylineFlags) {
266 self.flags = flags;
267
268 #[cfg(feature = "dim2")]
269 if flags.contains(PolylineFlags::ORIENTED) {
270 self.compute_pseudo_normals();
271 } else {
272 self.pseudo_normals = None;
273 }
274 }
275
276 /// The [`PolylineFlags`] controlling this polyline's optional associated data.
277 pub fn flags(&self) -> PolylineFlags {
278 self.flags
279 }
280
281 /// Replaces the vertex positions in place, keeping the index buffer.
282 ///
283 /// The BVH is refitted (not rebuilt) and the pseudo-normals, if any, are recomputed. This
284 /// is the update path of a deformable polyline: `vertices.len()` must equal
285 /// [`Self::vertices`]`.len()`.
286 ///
287 /// # Panics
288 ///
289 /// Panics if `vertices.len()` differs from the current number of vertices.
290 ///
291 /// # Example
292 ///
293 /// ```
294 /// # #[cfg(all(feature = "dim2", feature = "f32"))] {
295 /// use parry2d::shape::{Polyline, PolylineFlags};
296 /// use parry2d::math::Vector;
297 ///
298 /// let vertices = vec![Vector::ZERO, Vector::new(1.0, 0.0), Vector::new(2.0, 0.0)];
299 /// let mut polyline = Polyline::with_flags(vertices, None, PolylineFlags::DEFORMABLE);
300 ///
301 /// // Lift the middle vertex.
302 /// polyline.set_vertices(&[Vector::ZERO, Vector::new(1.0, 1.0), Vector::new(2.0, 0.0)]);
303 /// assert_eq!(polyline.local_aabb().maxs, Vector::new(2.0, 1.0));
304 /// # }
305 /// ```
306 pub fn set_vertices(&mut self, vertices: &[Vector]) {
307 assert_eq!(
308 vertices.len(),
309 self.vertices.len(),
310 "Polyline::set_vertices: the number of vertices must not change."
311 );
312 self.update_vertices(|vtx| vtx.copy_from_slice(vertices));
313 }
314
315 /// Modifies the vertex positions in place through `f`, then refits the BVH and recomputes
316 /// the pseudo-normals, if any (see [`Self::set_vertices`]).
317 pub fn update_vertices(&mut self, f: impl FnOnce(&mut [Vector])) {
318 f(&mut self.vertices);
319
320 for (i, idx) in self.indices.iter().enumerate() {
321 let aabb = Segment::new(
322 self.vertices[idx[0] as usize],
323 self.vertices[idx[1] as usize],
324 )
325 .local_aabb();
326 let _ = self.bvh.insert_or_update_partially(aabb, i as u32, 0.0);
327 }
328 self.bvh.refit_without_opt();
329
330 #[cfg(feature = "dim2")]
331 if self.pseudo_normals.is_some() {
332 self.compute_pseudo_normals();
333 }
334 }
335
336 /// Computes the outward pseudo-normal at every vertex (the normalized sum of its incident
337 /// segments' outward normals) for the one-sided behavior of [`PolylineFlags::ORIENTED`].
338 #[cfg(feature = "dim2")]
339 fn compute_pseudo_normals(&mut self) {
340 let mut vertex_normals = Vec::new();
341 vertex_normals.resize(self.vertices.len(), Vector::ZERO);
342
343 // A 2D vertex has at most two incident segments, so the normalized sum is their exact
344 // bisector -- no angle weighting (unlike the 3D `TrianglePseudoNormals`).
345 for idx in &self.indices {
346 let a = idx[0] as usize;
347 let b = idx[1] as usize;
348 let normal = crate::utils::ccw_face_normal([self.vertices[a], self.vertices[b]])
349 .unwrap_or(Vector::ZERO);
350 vertex_normals[a] += normal;
351 vertex_normals[b] += normal;
352 }
353
354 for normal in &mut vertex_normals {
355 *normal = normal.normalize_or_zero();
356 }
357
358 self.pseudo_normals = Some(vertex_normals);
359 }
360
361 /// The outward pseudo-normal of every vertex, if they have been computed (i.e. if this
362 /// polyline was built with [`PolylineFlags::ORIENTED`]).
363 ///
364 /// The returned slice is indexed by vertex index, like [`Self::vertices`].
365 #[cfg(feature = "dim2")]
366 pub fn pseudo_normals(&self) -> Option<&[Vector]> {
367 self.pseudo_normals.as_deref()
368 }
369
370 /// Returns the [`SegmentPseudoNormals`] for the segment with index `i`, or `None` unless this
371 /// polyline was built with [`PolylineFlags::ORIENTED`].
372 ///
373 /// # Example
374 ///
375 /// ```
376 /// # #[cfg(all(feature = "dim2", feature = "f32"))] {
377 /// use parry2d::shape::{Polyline, PolylineFlags};
378 /// use parry2d::math::Vector;
379 ///
380 /// let vertices = vec![Vector::new(0.0, 0.0), Vector::new(2.0, 0.0), Vector::new(2.0, 2.0)];
381 /// let mut polyline = Polyline::new(vertices, Some(vec![[0, 1], [1, 2]]));
382 ///
383 /// // A double-sided polyline has no constraints...
384 /// assert!(polyline.segment_normal_constraints(0).is_none());
385 ///
386 /// // ...until it is oriented.
387 /// polyline.set_flags(PolylineFlags::ORIENTED);
388 /// assert!(polyline.segment_normal_constraints(0).is_some());
389 /// # }
390 /// ```
391 #[cfg(feature = "dim2")]
392 pub fn segment_normal_constraints(&self, i: u32) -> Option<SegmentPseudoNormals> {
393 let pseudo_normals = self.pseudo_normals.as_ref()?;
394 let idx = self.indices[i as usize];
395 let a = idx[0] as usize;
396 let b = idx[1] as usize;
397 let face = crate::utils::ccw_face_normal([self.vertices[a], self.vertices[b]])?;
398 Some(SegmentPseudoNormals {
399 face,
400 edges: [pseudo_normals[a], pseudo_normals[b]],
401 })
402 }
403
404 /// Pseudo-normals are a 2D-only feature; in 3D there are no segment normal constraints. 3D stub
405 /// so the composite-shape impls compile; mirrors `TriMesh::triangle_normal_constraints`'s dim2
406 /// stub.
407 #[cfg(feature = "dim3")]
408 #[doc(hidden)]
409 pub fn segment_normal_constraints(&self, _i: u32) -> Option<SegmentPseudoNormals> {
410 None
411 }
412
413 /// Computes the axis-aligned bounding box of this polyline in world space.
414 ///
415 /// The AABB is the smallest box aligned with the world axes that fully contains
416 /// the polyline after applying the given position/rotation transformation.
417 ///
418 /// # Arguments
419 ///
420 /// * `pos` - The position and orientation (isometry) of the polyline in world space
421 ///
422 /// # Returns
423 ///
424 /// An `Aabb` that bounds the transformed polyline
425 ///
426 /// # Example
427 ///
428 /// ```
429 /// # #[cfg(all(feature = "dim3", feature = "f32"))] {
430 /// use parry3d::shape::Polyline;
431 /// use parry3d::math::{Vector, Pose};
432 ///
433 /// // Create a polyline along the X axis
434 /// let vertices = vec![
435 /// Vector::ZERO,
436 /// Vector::new(2.0, 0.0, 0.0),
437 /// ];
438 /// let polyline = Polyline::new(vertices, None);
439 ///
440 /// // Compute AABB at the origin
441 /// let identity = Pose::identity();
442 /// let aabb = polyline.aabb(&identity);
443 /// assert_eq!(aabb.mins.x, 0.0);
444 /// assert_eq!(aabb.maxs.x, 2.0);
445 ///
446 /// // Compute AABB after translating by (10, 5, 0)
447 /// let translated = Pose::translation(10.0, 5.0, 0.0);
448 /// let aabb_translated = polyline.aabb(&translated);
449 /// assert_eq!(aabb_translated.mins.x, 10.0);
450 /// assert_eq!(aabb_translated.maxs.x, 12.0);
451 /// # }
452 /// ```
453 pub fn aabb(&self, pos: &Pose) -> Aabb {
454 self.bvh.root_aabb().transform_by(pos)
455 }
456
457 /// Gets the local axis-aligned bounding box of this polyline.
458 ///
459 /// This returns the AABB in the polyline's local coordinate system (before any
460 /// transformation is applied). It's more efficient than `aabb()` when you don't
461 /// need to transform the polyline.
462 ///
463 /// # Returns
464 ///
465 /// An `Aabb` that bounds the polyline in local space
466 ///
467 /// # Example
468 ///
469 /// ```
470 /// # #[cfg(all(feature = "dim2", feature = "f32"))] {
471 /// use parry2d::shape::Polyline;
472 /// use parry2d::math::Vector;
473 ///
474 /// // Create a rectangular polyline
475 /// let vertices = vec![
476 /// Vector::new(-1.0, -2.0),
477 /// Vector::new(3.0, -2.0),
478 /// Vector::new(3.0, 4.0),
479 /// Vector::new(-1.0, 4.0),
480 /// ];
481 /// let polyline = Polyline::new(vertices, None);
482 ///
483 /// // Get the local AABB
484 /// let aabb = polyline.local_aabb();
485 ///
486 /// // The AABB should contain all vertices
487 /// assert_eq!(aabb.mins.x, -1.0);
488 /// assert_eq!(aabb.mins.y, -2.0);
489 /// assert_eq!(aabb.maxs.x, 3.0);
490 /// assert_eq!(aabb.maxs.y, 4.0);
491 /// # }
492 /// ```
493 pub fn local_aabb(&self) -> Aabb {
494 self.bvh.root_aabb()
495 }
496
497 /// The BVH acceleration structure for this polyline.
498 pub fn bvh(&self) -> &Bvh {
499 &self.bvh
500 }
501
502 /// Returns the number of segments (edges) in this polyline.
503 ///
504 /// Each segment connects two vertices. For a polyline with `n` vertices and
505 /// sequential connectivity, there are `n-1` segments. For custom connectivity,
506 /// the number of segments equals the number of index pairs.
507 ///
508 /// # Returns
509 ///
510 /// The total number of line segments
511 ///
512 /// # Example
513 ///
514 /// ```
515 /// # #[cfg(all(feature = "dim3", feature = "f32"))] {
516 /// use parry3d::shape::Polyline;
517 /// use parry3d::math::Vector;
518 ///
519 /// // Sequential polyline: 5 vertices -> 4 segments
520 /// let vertices = vec![
521 /// Vector::ZERO,
522 /// Vector::new(1.0, 0.0, 0.0),
523 /// Vector::new(2.0, 0.0, 0.0),
524 /// Vector::new(3.0, 0.0, 0.0),
525 /// Vector::new(4.0, 0.0, 0.0),
526 /// ];
527 /// let polyline = Polyline::new(vertices.clone(), None);
528 /// assert_eq!(polyline.num_segments(), 4);
529 ///
530 /// // Custom connectivity: can have different number of segments
531 /// let indices = vec![[0, 4], [1, 3]]; // Only 2 segments
532 /// let custom = Polyline::new(vertices, Some(indices));
533 /// assert_eq!(custom.num_segments(), 2);
534 /// # }
535 /// ```
536 pub fn num_segments(&self) -> usize {
537 self.indices.len()
538 }
539
540 /// Returns an iterator over all segments in this polyline.
541 ///
542 /// Each segment is returned as a [`Segment`] object with two endpoints.
543 /// The iterator yields exactly `num_segments()` items.
544 ///
545 /// # Returns
546 ///
547 /// An exact-size iterator that yields `Segment` instances
548 ///
549 /// # Example
550 ///
551 /// ```
552 /// # #[cfg(all(feature = "dim2", feature = "f32"))] {
553 /// use parry2d::shape::Polyline;
554 /// use parry2d::math::Vector;
555 ///
556 /// // Create a triangle
557 /// let vertices = vec![
558 /// Vector::ZERO,
559 /// Vector::new(1.0, 0.0),
560 /// Vector::new(0.5, 1.0),
561 /// ];
562 /// let polyline = Polyline::new(vertices, None);
563 ///
564 /// // Iterate over all segments
565 /// let mut total_length = 0.0;
566 /// for segment in polyline.segments() {
567 /// total_length += segment.length();
568 /// }
569 ///
570 /// // Calculate expected perimeter (not closed, so 2 sides only)
571 /// assert!(total_length > 2.0);
572 ///
573 /// // Collect all segments into a vector
574 /// let segments: Vec<_> = polyline.segments().collect();
575 /// assert_eq!(segments.len(), 2);
576 /// # }
577 /// ```
578 pub fn segments(&self) -> impl ExactSizeIterator<Item = Segment> + '_ {
579 self.indices.iter().map(move |ids| {
580 Segment::new(
581 self.vertices[ids[0] as usize],
582 self.vertices[ids[1] as usize],
583 )
584 })
585 }
586
587 /// Returns the segment at the given index.
588 ///
589 /// This retrieves a specific segment by its index. Indices range from `0` to
590 /// `num_segments() - 1`. If you need to access multiple segments, consider
591 /// using the `segments()` iterator instead.
592 ///
593 /// # Arguments
594 ///
595 /// * `i` - The index of the segment to retrieve (0-based)
596 ///
597 /// # Returns
598 ///
599 /// A `Segment` representing the edge at index `i`
600 ///
601 /// # Panics
602 ///
603 /// Panics if `i >= num_segments()`
604 ///
605 /// # Example
606 ///
607 /// ```
608 /// # #[cfg(all(feature = "dim3", feature = "f32"))] {
609 /// use parry3d::shape::Polyline;
610 /// use parry3d::math::Vector;
611 ///
612 /// let vertices = vec![
613 /// Vector::ZERO,
614 /// Vector::new(1.0, 0.0, 0.0),
615 /// Vector::new(2.0, 1.0, 0.0),
616 /// ];
617 /// let polyline = Polyline::new(vertices, None);
618 ///
619 /// // Get the first segment (connects vertex 0 to vertex 1)
620 /// let seg0 = polyline.segment(0);
621 /// assert_eq!(seg0.a, Vector::ZERO);
622 /// assert_eq!(seg0.b, Vector::new(1.0, 0.0, 0.0));
623 /// assert_eq!(seg0.length(), 1.0);
624 ///
625 /// // Get the second segment (connects vertex 1 to vertex 2)
626 /// let seg1 = polyline.segment(1);
627 /// assert_eq!(seg1.a, Vector::new(1.0, 0.0, 0.0));
628 /// assert_eq!(seg1.b, Vector::new(2.0, 1.0, 0.0));
629 /// # }
630 /// ```
631 pub fn segment(&self, i: u32) -> Segment {
632 let idx = self.indices[i as usize];
633 Segment::new(
634 self.vertices[idx[0] as usize],
635 self.vertices[idx[1] as usize],
636 )
637 }
638
639 /// Converts a FeatureId of the segment `segment` into a FeatureId of the whole polyline.
640 ///
641 /// An endpoint becomes the polyline vertex it indexes, so the two segments meeting at a corner
642 /// agree on it. In 2D a segment has a side facing each way, and they are numbered like the
643 /// segments themselves: the second side of segment `i` is `i + self.indices().len()`.
644 pub fn segment_feature_to_polyline_feature(
645 &self,
646 segment: SubShapeId,
647 feature: FeatureId,
648 ) -> FeatureId {
649 match feature {
650 FeatureId::Vertex(endpoint) => {
651 FeatureId::Vertex(self.indices[segment as usize][endpoint as usize])
652 }
653 #[cfg(feature = "dim2")]
654 FeatureId::Face(side) => FeatureId::Face(segment + side * self.indices.len() as u32),
655 #[cfg(feature = "dim3")]
656 FeatureId::Edge(_) => FeatureId::Edge(segment),
657 _ => FeatureId::Unknown,
658 }
659 }
660
661 /// Returns a slice containing all vertices of this polyline.
662 ///
663 /// Vertices are the points that define the polyline. Segments connect
664 /// pairs of these vertices according to the index buffer.
665 ///
666 /// # Returns
667 ///
668 /// A slice of all vertex points
669 ///
670 /// # Example
671 ///
672 /// ```
673 /// # #[cfg(all(feature = "dim2", feature = "f32"))] {
674 /// use parry2d::shape::Polyline;
675 /// use parry2d::math::Vector;
676 ///
677 /// let vertices = vec![
678 /// Vector::ZERO,
679 /// Vector::new(1.0, 0.0),
680 /// Vector::new(1.0, 1.0),
681 /// ];
682 /// let polyline = Polyline::new(vertices.clone(), None);
683 ///
684 /// // Access all vertices
685 /// let verts = polyline.vertices();
686 /// assert_eq!(verts.len(), 3);
687 /// assert_eq!(verts[0], Vector::ZERO);
688 /// assert_eq!(verts[1], Vector::new(1.0, 0.0));
689 /// assert_eq!(verts[2], Vector::new(1.0, 1.0));
690 ///
691 /// // You can iterate over vertices
692 /// for (i, vertex) in polyline.vertices().iter().enumerate() {
693 /// println!("Vertex {}: {:?}", i, vertex);
694 /// }
695 /// # }
696 /// ```
697 pub fn vertices(&self) -> &[Vector] {
698 &self.vertices[..]
699 }
700
701 /// Returns a slice containing all segment indices.
702 ///
703 /// Each index is a pair `[u32; 2]` representing a segment connecting two vertices.
704 /// The first element is the index of the segment's start vertex, and the second
705 /// is the index of the end vertex.
706 ///
707 /// # Returns
708 ///
709 /// A slice of all segment index pairs
710 ///
711 /// # Example
712 ///
713 /// ```
714 /// # #[cfg(all(feature = "dim3", feature = "f32"))] {
715 /// use parry3d::shape::Polyline;
716 /// use parry3d::math::Vector;
717 ///
718 /// let vertices = vec![
719 /// Vector::ZERO,
720 /// Vector::new(1.0, 0.0, 0.0),
721 /// Vector::new(2.0, 0.0, 0.0),
722 /// ];
723 ///
724 /// // With automatic indices
725 /// let polyline = Polyline::new(vertices.clone(), None);
726 /// let indices = polyline.indices();
727 /// assert_eq!(indices.len(), 2);
728 /// assert_eq!(indices[0], [0, 1]); // First segment: vertex 0 -> 1
729 /// assert_eq!(indices[1], [1, 2]); // Second segment: vertex 1 -> 2
730 ///
731 /// // With custom indices
732 /// let custom_indices = vec![[0, 2], [1, 0]];
733 /// let custom = Polyline::new(vertices, Some(custom_indices));
734 /// assert_eq!(custom.indices()[0], [0, 2]);
735 /// assert_eq!(custom.indices()[1], [1, 0]);
736 /// # }
737 /// ```
738 pub fn indices(&self) -> &[[u32; 2]] {
739 &self.indices
740 }
741
742 /// A flat view of the index buffer of this mesh.
743 pub fn flat_indices(&self) -> &[u32] {
744 unsafe {
745 let len = self.indices.len() * 2;
746 let data = self.indices.as_ptr() as *const u32;
747 core::slice::from_raw_parts(data, len)
748 }
749 }
750
751 /// Computes a scaled version of this polyline.
752 ///
753 /// This consumes the polyline and returns a new one with all vertices scaled
754 /// component-wise by the given scale vector. The connectivity (indices) remains
755 /// unchanged, but the BVH is rebuilt to reflect the new geometry.
756 ///
757 /// # Arguments
758 ///
759 /// * `scale` - The scaling factors for each axis
760 ///
761 /// # Returns
762 ///
763 /// A new polyline with scaled vertices
764 ///
765 /// # Example
766 ///
767 /// ```
768 /// # #[cfg(all(feature = "dim2", feature = "f32"))] {
769 /// use parry2d::shape::Polyline;
770 /// use parry2d::math::Vector;
771 ///
772 /// let vertices = vec![
773 /// Vector::new(1.0, 2.0),
774 /// Vector::new(3.0, 4.0),
775 /// ];
776 /// let polyline = Polyline::new(vertices, None);
777 ///
778 /// // Scale by 2x in X and 3x in Y
779 /// let scaled = polyline.scaled(Vector::new(2.0, 3.0));
780 ///
781 /// // Check scaled vertices
782 /// assert_eq!(scaled.vertices()[0], Vector::new(2.0, 6.0));
783 /// assert_eq!(scaled.vertices()[1], Vector::new(6.0, 12.0));
784 /// # }
785 /// ```
786 ///
787 /// # Note
788 ///
789 /// This method consumes `self`. If you need to keep the original polyline,
790 /// clone it first:
791 ///
792 /// ```
793 /// # #[cfg(all(feature = "dim3", feature = "f32"))] {
794 /// use parry3d::shape::Polyline;
795 /// use parry3d::math::Vector;
796 ///
797 /// let vertices = vec![Vector::ZERO, Vector::new(1.0, 0.0, 0.0)];
798 /// let original = Polyline::new(vertices, None);
799 ///
800 /// // Clone before scaling if you need to keep the original
801 /// let scaled = original.clone().scaled(Vector::new(2.0, 2.0, 2.0));
802 ///
803 /// // Both polylines still exist
804 /// assert_eq!(original.vertices()[1].x, 1.0);
805 /// assert_eq!(scaled.vertices()[1].x, 2.0);
806 /// # }
807 /// ```
808 pub fn scaled(mut self, scale: Vector) -> Self {
809 self.vertices.iter_mut().for_each(|pt| *pt *= scale);
810 let mut bvh = self.bvh.clone();
811 bvh.scale(scale);
812
813 #[cfg(feature = "dim2")]
814 {
815 let mut result = Self {
816 bvh,
817 vertices: self.vertices,
818 indices: self.indices,
819 pseudo_normals: None,
820 flags: PolylineFlags::empty(),
821 };
822 // Recompute the pseudo-normals from the scaled geometry.
823 result.set_flags(self.flags);
824 result
825 }
826 #[cfg(feature = "dim3")]
827 {
828 Self {
829 bvh,
830 vertices: self.vertices,
831 indices: self.indices,
832 flags: self.flags,
833 }
834 }
835 }
836
837 /// Reverses the orientation of this polyline.
838 ///
839 /// This operation:
840 /// 1. Swaps the start and end vertex of each segment (reversing edge direction)
841 /// 2. Reverses the order of segments in the index buffer
842 /// 3. Rebuilds the BVH to maintain correct acceleration structure
843 ///
844 /// After reversing, traversing the polyline segments in order will visit
845 /// the same geometry but in the opposite direction.
846 ///
847 /// # Example
848 ///
849 /// ```
850 /// # #[cfg(all(feature = "dim2", feature = "f32"))] {
851 /// use parry2d::shape::Polyline;
852 /// use parry2d::math::Vector;
853 ///
854 /// let vertices = vec![
855 /// Vector::ZERO,
856 /// Vector::new(1.0, 0.0),
857 /// Vector::new(2.0, 0.0),
858 /// ];
859 /// let mut polyline = Polyline::new(vertices, None);
860 ///
861 /// // Original: segment 0 goes from vertex 0 to 1, segment 1 from 1 to 2
862 /// assert_eq!(polyline.indices()[0], [0, 1]);
863 /// assert_eq!(polyline.indices()[1], [1, 2]);
864 ///
865 /// // Reverse the polyline
866 /// polyline.reverse();
867 ///
868 /// // After reversing: order is flipped and directions are swapped
869 /// // The last segment becomes first, with swapped endpoints
870 /// assert_eq!(polyline.indices()[0], [2, 1]);
871 /// assert_eq!(polyline.indices()[1], [1, 0]);
872 /// # }
873 /// ```
874 ///
875 /// # Use Cases
876 ///
877 /// This is useful for:
878 /// - Correcting winding order for 2D shapes
879 /// - Reversing path direction for navigation
880 /// - Ensuring consistent edge orientation in connected components
881 pub fn reverse(&mut self) {
882 for idx in &mut self.indices {
883 idx.swap(0, 1);
884 }
885
886 self.indices.reverse();
887
888 // Rebuild the bvh since the segment indices no longer map to the correct element.
889 // TODO PERF: should the Bvh have a function for efficient leaf index remapping?
890 // Probably not worth it unless this function starts showing up as a
891 // bottleneck for someone.
892 let leaves = self.segments().map(|seg| seg.local_aabb()).enumerate();
893 let bvh = Bvh::from_iter(BvhBuildStrategy::Binned, leaves);
894 self.bvh = bvh;
895
896 // Reversing flips the winding, so recompute the outward side.
897 #[cfg(feature = "dim2")]
898 if self.flags.contains(PolylineFlags::ORIENTED) {
899 self.compute_pseudo_normals();
900 }
901 }
902
903 /// Extracts the connected components of this polyline, consuming `self`.
904 ///
905 /// This method is currently quite restrictive on the kind of allowed input. The polyline
906 /// represented by `self` must already have an index buffer sorted such that:
907 /// - Each connected component appears in the index buffer one after the other, i.e., a
908 /// connected component of this polyline must be a contiguous range of this polyline’s
909 /// index buffer.
910 /// - Each connected component is closed, i.e., each range of this polyline index buffer
911 /// `self.indices[i_start..=i_end]` forming a complete connected component, we must have
912 /// `self.indices[i_start][0] == self.indices[i_end][1]`.
913 /// - The indices for each component must already be in order, i.e., if the segments
914 /// `self.indices[i]` and `self.indices[i + 1]` are part of the same connected component then
915 /// we must have `self.indices[i][1] == self.indices[i + 1][0]`.
916 ///
917 /// # Output
918 /// Returns the set of polylines. If the inputs fulfill the constraints mentioned above, each
919 /// polyline will be a closed loop with consistent edge orientations, i.e., for all indices `i`,
920 /// we have `polyline.indices[i][1] == polyline.indices[i + 1][0]`.
921 ///
922 /// The orientation of each closed loop (clockwise or counterclockwise) are identical to their
923 /// original orientation in `self`.
924 pub fn extract_connected_components(&self) -> Vec<Polyline> {
925 let vertices = self.vertices();
926 let indices = self.indices();
927
928 if indices.is_empty() {
929 // Polyline is empty, return empty Vec
930 Vec::new()
931 } else {
932 let mut components = Vec::new();
933
934 let mut start_i = 0; // Start position of component
935 let mut start_node = indices[0][0]; // Start vertex index of component
936
937 let mut component_vertices = Vec::new();
938 let mut component_indices: Vec<[u32; 2]> = Vec::new();
939
940 // Iterate over indices, building polylines as we go
941 for (i, idx) in indices.iter().enumerate() {
942 component_vertices.push(vertices[idx[0] as usize]);
943
944 if idx[1] != start_node {
945 // Keep scanning and adding data
946 component_indices.push([(i - start_i) as u32, (i - start_i + 1) as u32]);
947 } else {
948 // Start node reached: build polyline and start next component
949 component_indices.push([(i - start_i) as u32, 0]);
950 components.push(Polyline::new(
951 core::mem::take(&mut component_vertices),
952 Some(core::mem::take(&mut component_indices)),
953 ));
954
955 if i + 1 < indices.len() {
956 // More components to find
957 start_node = indices[i + 1][0];
958 start_i = i + 1;
959 }
960 }
961 }
962
963 components
964 }
965 }
966
967 /// Perform a point projection assuming a solid interior based on a counter-clock-wise orientation.
968 ///
969 /// This is similar to `self.project_local_point_and_get_location` except that the resulting
970 /// `PointProjection::is_inside` will be set to true if the point is inside of the area delimited
971 /// by this polyline, assuming that:
972 /// - This polyline isn’t self-crossing.
973 /// - This polyline is closed with `self.indices[i][1] == self.indices[(i + 1) % num_indices][0]` where
974 /// `num_indices == self.indices.len()`.
975 /// - This polyline is oriented counter-clockwise.
976 /// - In 3D, the polyline is assumed to be fully coplanar, on a plane with normal given by
977 /// `axis`.
978 ///
979 /// These properties are not checked.
980 pub fn project_local_point_assuming_solid_interior_ccw(
981 &self,
982 point: Vector,
983 #[cfg(feature = "dim3")] axis: u8,
984 ) -> (PointProjection, (u32, SegmentPointLocation)) {
985 let mut proj = self.project_local_point_and_get_location(point, false);
986 let segment1 = self.segment((proj.1).0);
987
988 #[cfg(feature = "dim2")]
989 let normal1 = segment1.normal();
990 #[cfg(feature = "dim3")]
991 let normal1 = segment1.planar_normal(axis);
992
993 if let Some(normal1) = normal1 {
994 proj.0.is_inside = match proj.1 .1 {
995 SegmentPointLocation::OnVertex(i) => {
996 let dir2 = if i == 0 {
997 let adj_seg = if proj.1 .0 == 0 {
998 self.indices().len() as u32 - 1
999 } else {
1000 proj.1 .0 - 1
1001 };
1002
1003 assert_eq!(segment1.a, self.segment(adj_seg).b);
1004 -self.segment(adj_seg).scaled_direction()
1005 } else {
1006 assert_eq!(i, 1);
1007 let adj_seg = (proj.1 .0 + 1) % self.indices().len() as u32;
1008 assert_eq!(segment1.b, self.segment(adj_seg).a);
1009
1010 self.segment(adj_seg).scaled_direction()
1011 };
1012
1013 let dot = normal1.dot(dir2);
1014 // TODO: is this threshold too big? This corresponds to an angle equal to
1015 // abs(acos(1.0e-3)) = (90 - 0.057) degrees.
1016 // We did encounter some cases where this was needed, but perhaps the
1017 // actual problem was an issue with the SegmentPointLocation (which should
1018 // perhaps have been Edge instead of Vertex)?
1019 let threshold = 1.0e-3 * dir2.length();
1020 if dot.abs() > threshold {
1021 // If the vertex is a reentrant vertex, then the point is
1022 // inside. Otherwise, it is outside.
1023 dot >= 0.0
1024 } else {
1025 // If the two edges are collinear, we can’t classify the vertex.
1026 // So check against the edge’s normal instead.
1027 (point - proj.0.point).dot(normal1) <= 0.0
1028 }
1029 }
1030 SegmentPointLocation::OnEdge(_) => (point - proj.0.point).dot(normal1) <= 0.0,
1031 };
1032 }
1033
1034 proj
1035 }
1036}
1037
1038impl CompositeShape for Polyline {
1039 fn map_part_at(
1040 &self,
1041 i: u32,
1042 f: &mut dyn FnMut(Option<&Pose>, &dyn Shape, Option<&dyn NormalConstraints>),
1043 ) {
1044 let seg = self.segment(i);
1045 let normals = self.segment_normal_constraints(i);
1046 f(
1047 None,
1048 &seg,
1049 normals.as_ref().map(|n| n as &dyn NormalConstraints),
1050 )
1051 }
1052
1053 fn bvh(&self) -> &Bvh {
1054 &self.bvh
1055 }
1056
1057 fn is_deformable(&self) -> bool {
1058 self.flags.contains(PolylineFlags::DEFORMABLE)
1059 }
1060}
1061
1062impl TypedCompositeShape for Polyline {
1063 type PartShape = Segment;
1064 type PartNormalConstraints = SegmentPseudoNormals;
1065
1066 #[inline(always)]
1067 fn map_typed_part_at<T>(
1068 &self,
1069 i: u32,
1070 mut f: impl FnMut(Option<&Pose>, &Self::PartShape, Option<&Self::PartNormalConstraints>) -> T,
1071 ) -> Option<T> {
1072 let seg = self.segment(i);
1073 let normals = self.segment_normal_constraints(i);
1074 Some(f(None, &seg, normals.as_ref()))
1075 }
1076
1077 #[inline(always)]
1078 fn map_untyped_part_at<T>(
1079 &self,
1080 i: u32,
1081 mut f: impl FnMut(Option<&Pose>, &dyn Shape, Option<&dyn NormalConstraints>) -> T,
1082 ) -> Option<T> {
1083 let seg = self.segment(i);
1084 let normals = self.segment_normal_constraints(i);
1085 Some(f(
1086 None,
1087 &seg,
1088 normals.as_ref().map(|n| n as &dyn NormalConstraints),
1089 ))
1090 }
1091}
1092
1093#[cfg(test)]
1094#[cfg(all(feature = "dim2", feature = "alloc"))]
1095mod pseudo_normal_tests {
1096 use crate::math::Vector;
1097 use crate::shape::{Polyline, PolylineFlags};
1098
1099 fn ccw_square() -> Polyline {
1100 // CCW unit square: solid inside, outward away from the center.
1101 let vertices = vec![
1102 Vector::new(-1.0, -1.0),
1103 Vector::new(1.0, -1.0),
1104 Vector::new(1.0, 1.0),
1105 Vector::new(-1.0, 1.0),
1106 ];
1107 Polyline::new(vertices, Some(vec![[0, 1], [1, 2], [2, 3], [3, 0]]))
1108 }
1109
1110 #[test]
1111 fn not_oriented_by_default() {
1112 assert!(ccw_square().segment_normal_constraints(0).is_none());
1113 }
1114
1115 #[test]
1116 fn face_and_edge_normals_are_unit_and_outward() {
1117 let mut polyline = ccw_square();
1118 polyline.set_flags(PolylineFlags::ORIENTED);
1119
1120 for i in 0..polyline.num_segments() as u32 {
1121 let segment = polyline.segment(i);
1122 let constraints = polyline.segment_normal_constraints(i).unwrap();
1123
1124 assert!((constraints.face.length() - 1.0).abs() < 1.0e-5);
1125 for edge in constraints.edges {
1126 assert!((edge.length() - 1.0).abs() < 1.0e-5);
1127 }
1128
1129 // The square is centered on the origin, so a midpoint doubles as its outward direction.
1130 let midpoint = (segment.a + segment.b) * 0.5;
1131 assert!(constraints.face.dot(midpoint) > 0.0);
1132 }
1133 }
1134
1135 #[test]
1136 fn corner_pseudo_normal_bisects_its_two_faces() {
1137 let mut polyline = ccw_square();
1138 polyline.set_flags(PolylineFlags::ORIENTED);
1139
1140 // Vertex 1's pseudo-normal bisects the bottom edge (-Y) and right edge (+X): (1, -1) normalized.
1141 let bottom = polyline.segment_normal_constraints(0).unwrap();
1142 assert!(bottom.edges[1].abs_diff_eq(Vector::new(1.0, -1.0).normalize(), 1.0e-5));
1143 }
1144
1145 #[test]
1146 fn degenerate_input_yields_no_segments() {
1147 // Auto-generated indices must not underflow `len - 1` on 0- or 1-vertex input.
1148 assert_eq!(Polyline::new(vec![], None).num_segments(), 0);
1149 assert_eq!(Polyline::new(vec![Vector::ZERO], None).num_segments(), 0);
1150 }
1151
1152 #[test]
1153 fn oriented_point_query_treats_interior_as_inside() {
1154 use crate::query::{PointQuery, PointQueryWithLocation};
1155
1156 let mut polyline = ccw_square();
1157 polyline.set_flags(PolylineFlags::ORIENTED);
1158 let inside = Vector::new(0.25, -0.5);
1159
1160 // Solid: an inside point is its own projection.
1161 let solid = polyline.project_local_point(inside, true);
1162 assert!(solid.is_inside);
1163 assert!(solid.point.abs_diff_eq(inside, 1.0e-5));
1164
1165 // Non-solid: still inside, but projected to the boundary.
1166 let hollow = polyline.project_local_point(inside, false);
1167 assert!(hollow.is_inside);
1168 assert!(!hollow.point.abs_diff_eq(inside, 1.0e-5));
1169
1170 assert!(polyline.contains_local_point(inside));
1171 assert!(
1172 polyline
1173 .project_local_point_and_get_location(inside, false)
1174 .0
1175 .is_inside
1176 );
1177 assert!(
1178 polyline
1179 .project_local_point_and_get_feature(inside)
1180 .0
1181 .is_inside
1182 );
1183 }
1184
1185 #[test]
1186 fn oriented_point_query_leaves_exterior_outside() {
1187 use crate::query::PointQuery;
1188
1189 let mut polyline = ccw_square();
1190 polyline.set_flags(PolylineFlags::ORIENTED);
1191 let outside = Vector::new(2.0, 0.0);
1192
1193 let proj = polyline.project_local_point(outside, true);
1194 assert!(!proj.is_inside);
1195 assert!(proj.point.abs_diff_eq(Vector::new(1.0, 0.0), 1.0e-5));
1196 assert!(!polyline.contains_local_point(outside));
1197 }
1198
1199 #[test]
1200 fn unoriented_polyline_has_no_interior() {
1201 use crate::query::PointQuery;
1202
1203 // Unoriented: a hollow wireframe with no interior.
1204 let polyline = ccw_square();
1205 let center = Vector::ZERO;
1206
1207 assert!(!polyline.project_local_point(center, true).is_inside);
1208 assert!(!polyline.contains_local_point(center));
1209 }
1210}