bsp_tree/
polygon.rs

1//! Generic polygon representation for BSP trees.
2
3use nalgebra::{Point3, Vector3};
4
5use crate::{Classification, Plane3D, PlaneSide, Rectangle, Triangle};
6
7/// A convex polygon in 3D space, defined by an ordered list of vertices.
8///
9/// Vertices should be coplanar and in counter-clockwise winding order
10/// when viewed from the front (the direction the normal points).
11#[derive(Debug, Clone, PartialEq)]
12pub struct Polygon {
13    vertices: Vec<Point3<f32>>,
14}
15
16impl Polygon {
17    /// Creates a new polygon from a list of vertices.
18    ///
19    /// # Panics (debug builds only)
20    /// - Panics if fewer than 3 vertices are provided.
21    /// - Panics if vertices are not coplanar.
22    pub fn new(vertices: Vec<Point3<f32>>) -> Self {
23        debug_assert!(
24            vertices.len() >= 3,
25            "Polygon must have at least 3 vertices"
26        );
27        debug_assert!(
28            Self::are_coplanar(&vertices),
29            "Polygon vertices must be coplanar"
30        );
31        Self { vertices }
32    }
33
34    /// Checks if all vertices lie on the same plane.
35    fn are_coplanar(vertices: &[Point3<f32>]) -> bool {
36        if vertices.len() <= 3 {
37            return true;
38        }
39
40        let plane = Plane3D::from_three_points(vertices[0], vertices[1], vertices[2]);
41        vertices[3..]
42            .iter()
43            .all(|v| plane.classify_point(*v) == PlaneSide::OnPlane)
44    }
45
46    /// Returns the vertices of the polygon.
47    #[inline]
48    pub fn vertices(&self) -> &[Point3<f32>] {
49        &self.vertices
50    }
51
52    /// Returns the number of vertices.
53    #[inline]
54    pub fn len(&self) -> usize {
55        self.vertices.len()
56    }
57
58    /// Returns true if the polygon has no vertices (always false for valid polygons).
59    #[inline]
60    pub fn is_empty(&self) -> bool {
61        self.vertices.is_empty()
62    }
63
64    /// Computes the (unnormalized) normal vector of the polygon.
65    ///
66    /// Uses the first three vertices to compute the normal via cross product.
67    /// The direction follows the right-hand rule based on vertex winding.
68    pub fn normal(&self) -> Vector3<f32> {
69        let a = &self.vertices[0];
70        let b = &self.vertices[1];
71        let c = &self.vertices[2];
72        let ab = b - a;
73        let ac = c - a;
74        ab.cross(&ac)
75    }
76
77    /// Computes the unit normal vector of the polygon.
78    ///
79    /// Returns `None` if the first three vertices are collinear.
80    pub fn unit_normal(&self) -> Option<Vector3<f32>> {
81        let n = self.normal();
82        let len = n.norm();
83        if len > f32::EPSILON {
84            Some(n / len)
85        } else {
86            None
87        }
88    }
89
90    /// Returns the plane that this polygon lies on.
91    ///
92    /// # Panics
93    /// Panics if the first three vertices are collinear.
94    pub fn plane(&self) -> Plane3D {
95        Plane3D::from_three_points(self.vertices[0], self.vertices[1], self.vertices[2])
96    }
97
98    /// Computes the centroid (center of mass) of the polygon.
99    pub fn centroid(&self) -> Point3<f32> {
100        let sum: Vector3<f32> = self.vertices.iter().map(|p| p.coords).sum();
101        Point3::from(sum / self.vertices.len() as f32)
102    }
103
104    /// Classifies this polygon relative to a plane.
105    ///
106    /// Returns:
107    /// - `Front` if all vertices are in front of the plane
108    /// - `Back` if all vertices are behind the plane
109    /// - `Coplanar` if all vertices lie on the plane
110    /// - `Spanning` if vertices are on both sides
111    pub fn classify(&self, plane: &Plane3D) -> Classification {
112        let mut front = 0;
113        let mut back = 0;
114        let mut on_plane = 0;
115
116        for vertex in &self.vertices {
117            match plane.classify_point(*vertex) {
118                PlaneSide::Front => front += 1,
119                PlaneSide::Back => back += 1,
120                PlaneSide::OnPlane => on_plane += 1,
121            }
122        }
123
124        if on_plane == self.vertices.len() {
125            Classification::Coplanar
126        } else if back == 0 {
127            Classification::Front
128        } else if front == 0 {
129            Classification::Back
130        } else {
131            Classification::Spanning
132        }
133    }
134}
135
136impl From<Triangle> for Polygon {
137    fn from(triangle: Triangle) -> Self {
138        Self {
139            vertices: triangle.vertices().to_vec(),
140        }
141    }
142}
143
144impl From<&Triangle> for Polygon {
145    fn from(triangle: &Triangle) -> Self {
146        Self {
147            vertices: triangle.vertices().to_vec(),
148        }
149    }
150}
151
152impl From<Rectangle> for Polygon {
153    fn from(rectangle: Rectangle) -> Self {
154        Self {
155            vertices: rectangle.vertices().to_vec(),
156        }
157    }
158}
159
160impl From<&Rectangle> for Polygon {
161    fn from(rectangle: &Rectangle) -> Self {
162        Self {
163            vertices: rectangle.vertices().to_vec(),
164        }
165    }
166}
167
168impl From<Polygon> for Plane3D {
169    fn from(polygon: Polygon) -> Self {
170        polygon.plane()
171    }
172}
173
174impl From<&Polygon> for Plane3D {
175    fn from(polygon: &Polygon) -> Self {
176        polygon.plane()
177    }
178}
bsp_tree/polygon.rs

bsp_tree/
polygon.rs
