chull_adapt/common/
convex_hull.rs

1// Copyright (C) 2020-2025 phys-convex-hull authors. All Rights Reserved.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15use glam_det::{Point3, UnitVec3, Vec3};
16
17pub struct ConvexHull {
18    pub points: Vec<Point3>,
19    pub bounding_planes: Vec<HalfPlane>,
20    pub face_indices_start: Vec<u32>,
21    pub face_vertex_indices: Vec<u32>,
22    pub center: Vec3,
23    pub volume: f32,
24    pub total_area: f32,
25    /// The offset vector applied to all points if align-to-center is enabled.
26    ///
27    /// - If `None`, align-to-center is disabled, and points remain at their original positions.
28    /// - If `Some(Vec3)`, align-to-center is enabled, and points are shifted by the given vector,
29    ///   meaning the original positions are at `pos + shift_center`.
30    pub shift_center: Option<Vec3>,
31    pub debug: Option<ConvexHullDebugInfo>,
32}
33
34impl<'a> ConvexHull {
35    #[inline]
36    #[must_use]
37    pub fn get_vertex_indices(&self, face_index: usize) -> &[u32] {
38        let start = self.face_indices_start[face_index] as usize;
39        let next_index = face_index + 1;
40        let end = if next_index < self.face_indices_start.len() {
41            self.face_indices_start[next_index] as usize
42        } else {
43            self.face_vertex_indices.len()
44        };
45        &self.face_vertex_indices[start..end]
46    }
47
48    pub fn triangle_index_iter(&self) -> impl Iterator<Item = [usize; 3]> + '_ {
49        ConvexHullTriangleIndexIter::new(self)
50    }
51
52    pub fn face_iter(&'a self) -> impl Iterator<Item = &'a [u32]> {
53        ConvexHullFaceIter::new(self)
54    }
55}
56
57/// An iterator over each triangle index in the convex hull.
58pub struct ConvexHullTriangleIndexIter<'a> {
59    hull: &'a ConvexHull,
60    face_index: usize,
61    sub_triangle_index: usize,
62}
63impl<'a> ConvexHullTriangleIndexIter<'a> {
64    #[inline]
65    #[must_use]
66    pub fn new(hull: &'a ConvexHull) -> Self {
67        Self {
68            hull,
69            face_index: 0,
70            sub_triangle_index: 2,
71        }
72    }
73}
74
75impl Iterator for ConvexHullTriangleIndexIter<'_> {
76    type Item = [usize; 3];
77
78    #[inline]
79    fn next(&mut self) -> Option<Self::Item> {
80        if self.face_index < self.hull.face_indices_start.len() {
81            let faces = self.hull.get_vertex_indices(self.face_index);
82            let mut triangle = [usize::MAX; 3];
83            triangle[0] = faces[0] as usize;
84            triangle[1] = faces[self.sub_triangle_index - 1] as usize;
85            triangle[2] = faces[self.sub_triangle_index] as usize;
86
87            self.sub_triangle_index += 1;
88            if self.sub_triangle_index == faces.len() {
89                self.face_index += 1;
90                self.sub_triangle_index = 2;
91            }
92            Some(triangle)
93        } else {
94            None
95        }
96    }
97}
98
99pub struct ConvexHullFaceIter<'a> {
100    hull: &'a ConvexHull,
101    face_index: usize,
102}
103impl<'a> ConvexHullFaceIter<'a> {
104    #[inline]
105    #[must_use]
106    pub fn new(hull: &'a ConvexHull) -> Self {
107        Self {
108            hull,
109            face_index: 0,
110        }
111    }
112}
113
114impl<'a> Iterator for ConvexHullFaceIter<'a> {
115    type Item = &'a [u32];
116
117    #[inline]
118    fn next(&mut self) -> Option<Self::Item> {
119        if self.face_index < self.hull.face_indices_start.len() {
120            let faces = self.hull.get_vertex_indices(self.face_index);
121            self.face_index += 1;
122            Some(faces)
123        } else {
124            None
125        }
126    }
127}
128
129/// n⋅x≤d
130/// n is the normal of the plane
131/// d is the offset of the plane
132/// x is the point on the plane
133/// so the normal of the plane is toward the outside of the convex hull
134pub struct HalfPlane {
135    pub center: Point3,
136    pub normal: UnitVec3,
137    pub offset: f32,
138}
139
140#[derive(Default)]
141pub struct ConvexHullDebugInfo {
142    pub neighbours_index: Vec<u32>,
143    /// every face is represented in `face_indices_start`,and it's neighbours represented in
144    /// `neighbours_index_start` and `neighbours_index`
145    pub neighbours_index_start: Vec<u32>,
146}
147
148#[derive(Default)]
149pub struct ConvexMesh {
150    pub vertices: Vec<Point3>,
151    pub triangles: Vec<u32>,
152}
153
154impl ConvexMesh {
155    #[must_use]
156    #[inline]
157    pub fn num_triangles(&self) -> u32 {
158        let triangles = self.triangles.len();
159        (triangles / 3) as u32
160    }
161
162    #[must_use]
163    #[inline]
164    pub fn num_vertices(&self) -> u32 {
165        self.vertices.len() as u32
166    }
167
168    #[must_use]
169    #[inline]
170    pub fn vertices(&self) -> &[Point3] {
171        &self.vertices
172    }
173
174    #[must_use]
175    #[inline]
176    pub fn triangles(&self) -> &[u32] {
177        &self.triangles
178    }
179}
chull_adapt/common/convex_hull.rs

chull_adapt/common/
convex_hull.rs
