pasture_algorithms/
convexhull.rs

1use anyhow::{anyhow, Result};
2use pasture_core::containers::{BorrowedBuffer, BorrowedBufferExt};
3use pasture_core::{layout::attributes::POSITION_3D, nalgebra::Vector3};
4use std::collections::{HashMap, HashSet};
5use std::hash::{Hash, Hasher};
6use std::usize;
7
8#[derive(Clone, Copy)]
9struct Triangle {
10    a: usize,
11    b: usize,
12    c: usize,
13    normal: Vector3<f64>,
14}
15
16#[derive(Eq, Clone, Copy)]
17struct Edge {
18    a: usize,
19    b: usize,
20}
21
22impl PartialEq for Edge {
23    fn eq(&self, other: &Self) -> bool {
24        self.a == other.a && self.b == other.b || self.a == other.b && self.b == other.a
25    }
26}
27
28impl Hash for Edge {
29    fn hash<H: Hasher>(&self, state: &mut H) {
30        (self.a * self.b).hash(state);
31    }
32}
33
34/// Convex Hull generation as triangle mesh
35/// Returns the convex hull as a vector of tuples of size 3 that contains the indices of the triangle vertices within the input buffer that form a convex hull around all input points
36/// or an error if less than 3 linearily independent points were given in the input buffer.
37///
38/// #Panics
39///
40/// If the PointBuffer doesn't cointain a POSITION_3D attribute.
41pub fn convex_hull_as_triangle_mesh<'a, T: BorrowedBuffer<'a>>(
42    buffer: &'a T,
43) -> Result<Vec<Vector3<usize>>> {
44    let triangles = create_convex_hull(buffer);
45    if triangles.len() < 2 {
46        return Err(anyhow!(
47            "input buffer cointains too few linearly independent points"
48        ));
49    }
50    let mut triangle_indices = Vec::new();
51    for tri in triangles {
52        triangle_indices.push(Vector3::new(tri.a, tri.b, tri.c));
53    }
54    Ok(triangle_indices)
55}
56
57/// Convex Hull generation as points
58/// Returns the convex hull as an unsorted vector that contains the indices the points forming a convex hull around all input points.
59///
60/// #Panics
61///
62/// If the PointBuffer doesn't cointain a POSITION_3D attribute.
63pub fn convex_hull_as_points<'a, T: BorrowedBuffer<'a>>(buffer: &'a T) -> Vec<usize> {
64    let triangles = create_convex_hull(buffer);
65    let mut points = HashSet::new();
66    if triangles.len() > 1 {
67        for tri in triangles {
68            points.insert(tri.a);
69            points.insert(tri.b);
70            points.insert(tri.c);
71        }
72    } else {
73        let tri = triangles[0];
74        points.insert(tri.a);
75        points.insert(tri.b);
76        if tri.c != 0 {
77            points.insert(tri.c);
78        }
79    }
80    let point_indices: Vec<usize> = points.into_iter().collect();
81    point_indices
82}
83
84fn create_convex_hull<'a, T: BorrowedBuffer<'a>>(buffer: &'a T) -> Vec<Triangle> {
85    let mut triangles: Vec<Triangle> = Vec::new();
86    let position_attribute = match buffer
87        .point_layout()
88        .get_attribute_by_name(POSITION_3D.name())
89    {
90        Some(a) => a,
91        None => {
92            panic!("point buffer contains no position attribute")
93        }
94    };
95
96    let mut pointid: usize = 0;
97    if position_attribute.datatype() == POSITION_3D.datatype() {
98        for point in buffer.view_attribute::<Vector3<f64>>(&POSITION_3D) {
99            iteration(buffer, pointid, point, &mut triangles);
100            pointid += 1;
101        }
102    } else {
103        for point in buffer
104            .view_attribute_with_conversion::<Vector3<f64>>(&POSITION_3D)
105            .expect("Can't convert POSITION_3D attribute")
106        {
107            iteration(buffer, pointid, point, &mut triangles);
108            pointid += 1;
109        }
110    };
111    triangles
112}
113
114/// Performs a single iteration of the cunvex hull algorithm.
115/// `pointid`: current index within the buffer
116/// `point`: current point to be checked against the convex hull, possibly extends the convex hull
117/// `triangles`: the set of triangles forming the convex hull
118/// Each iteration receives a convex hull and checks it against the current point within the buffer.
119/// If the point lies within the current convex hull no changes have to be made.
120/// If the point lies outside of the current convex hull the hull has to be extended to include the current point.
121/// If 'triangles' contain only one entry: no full triangle has been found yet. In case of linearily dependant points no second triangle is added.
122/// If all 'triangles' are in a plane with 'point' a special triangulation procedure is needed to prevent a degenerated triangle mesh.
123fn iteration<'a, T: BorrowedBuffer<'a>>(
124    buffer: &'a T,
125    pointid: usize,
126    point: Vector3<f64>,
127    triangles: &mut Vec<Triangle>,
128) {
129    if pointid == 0 {
130        triangles.push(Triangle {
131            a: 0,
132            b: 0,
133            c: 0,
134            normal: point,
135        })
136    } else if triangles.len() == 1 {
137        let first = &mut triangles[0];
138        if pointid == 1 {
139            first.b = pointid;
140        } else {
141            let first_a = buffer.view_attribute(&POSITION_3D).at(first.a);
142            let first_b = buffer.view_attribute(&POSITION_3D).at(first.b);
143            let ab: Vector3<f64> = first_b - first_a;
144            let ab_mag_sqr = ab.magnitude_squared();
145            if ab_mag_sqr == 0.0 {
146                first.b = pointid;
147            } else {
148                let ac: Vector3<f64> = point - first_a;
149                let ab_norm = ab.normalize();
150                let ac_ab_projected_length = ac.dot(&ab_norm);
151                if f64::abs(ac_ab_projected_length) == ac.magnitude() {
152                    if ac_ab_projected_length >= 0.0 {
153                        if ac.magnitude_squared() > ab_mag_sqr {
154                            first.b = pointid;
155                        }
156                    } else {
157                        first.a = pointid;
158                    }
159                } else {
160                    first.c = pointid;
161                    first.normal = calc_normal(first_a, first_b, point);
162
163                    let first = triangles[0];
164                    triangles.push(Triangle {
165                        a: first.a,
166                        b: first.c,
167                        c: first.b,
168                        normal: -first.normal,
169                    })
170                }
171            }
172        }
173    } else {
174        let mut outer_edges = HashSet::new();
175        let mut inner_edges = HashSet::new();
176        let mut planar_triangles = Vec::new();
177
178        triangles.retain(|tri| {
179            let tri_a: Vector3<f64> = buffer.view_attribute(&POSITION_3D).at(tri.a);
180            let pa: Vector3<f64> = tri_a - point;
181            let dot = pa.dot(&tri.normal);
182            if dot < 0.0 {
183                add_edge_to_outer_or_inner_edges(tri.a, tri.b, &mut outer_edges, &mut inner_edges);
184                add_edge_to_outer_or_inner_edges(tri.b, tri.c, &mut outer_edges, &mut inner_edges);
185                add_edge_to_outer_or_inner_edges(tri.c, tri.a, &mut outer_edges, &mut inner_edges);
186                return false;
187            } else if dot == 0.0 {
188                planar_triangles.push(*tri);
189            }
190            true
191        });
192
193        if !outer_edges.is_empty() || !inner_edges.is_empty() {
194            for edge in outer_edges.iter() {
195                let edge_a: Vector3<f64> = buffer.view_attribute(&POSITION_3D).at(edge.a);
196                let edge_b: Vector3<f64> = buffer.view_attribute(&POSITION_3D).at(edge.b);
197                triangles.push(Triangle {
198                    a: edge.a,
199                    b: edge.b,
200                    c: pointid,
201                    normal: calc_normal(edge_a, edge_b, point),
202                });
203            }
204        } else {
205            // Find all edges of the triangle of which the edge-normal is facing the point.
206            let mut edges_facing_point = Vec::new();
207            let mut edge_triangle_id = Vec::new();
208            let position_view = buffer.view_attribute(&POSITION_3D);
209            for (i, pt) in planar_triangles.iter().enumerate() {
210                let planar_a = position_view.at(pt.a);
211                let planar_b = position_view.at(pt.b);
212                let planar_c = position_view.at(pt.c);
213                let dist_ab = dist_point_to_edge(point, planar_a, planar_b, pt.normal);
214                if dist_ab >= 0.0 {
215                    edges_facing_point.push(Edge { a: pt.a, b: pt.b });
216                    edge_triangle_id.push(i);
217                }
218                let dist_bc = dist_point_to_edge(point, planar_b, planar_c, pt.normal);
219                if dist_bc >= 0.0 {
220                    edges_facing_point.push(Edge { a: pt.b, b: pt.c });
221                    edge_triangle_id.push(i);
222                }
223                let dist_ca = dist_point_to_edge(point, planar_c, planar_a, pt.normal);
224                if dist_ca >= 0.0 {
225                    edges_facing_point.push(Edge { a: pt.c, b: pt.a });
226                    edge_triangle_id.push(i);
227                }
228                if dist_ab < 0.0 && dist_bc < 0.0 && dist_ca < 0.0 {
229                    edges_facing_point.clear();
230                    break;
231                }
232            }
233
234            // Remove all edges occluded by other edges.
235            let mut edge_triangle_normals = Vec::new();
236            for i in (0..edges_facing_point.len()).rev() {
237                let edg = edges_facing_point[i];
238                let edg_a: Vector3<f64> = position_view.at(edg.a);
239                let edg_b: Vector3<f64> = position_view.at(edg.b);
240                let dist_edg_a_p = (edg_a - point).magnitude_squared();
241                let dist_edg_b_p = (edg_b - point).magnitude_squared();
242                let dist_edg_p = dist_point_to_line_segment(point, edg_a, edg_b);
243                let edg_triangle_normal: Vector3<f64> =
244                    planar_triangles[edge_triangle_id[i]].normal;
245                let mut remove = false;
246                for other_edge_id in 0..edges_facing_point.len() {
247                    if other_edge_id != i {
248                        let other_edg_triangle_normal =
249                            planar_triangles[edge_triangle_id[other_edge_id]].normal;
250                        if edg_triangle_normal.dot(&other_edg_triangle_normal) > 0.0 {
251                            let other_edg = edges_facing_point[other_edge_id];
252                            let other_edg_a: Vector3<f64> = position_view.at(other_edg.a);
253                            let other_edg_b: Vector3<f64> = position_view.at(other_edg.b);
254                            let point_other_edg_a = other_edg_a - point;
255                            let point_other_edg_b = other_edg_b - point;
256                            let point_other_edg_a_norm =
257                                other_edg_triangle_normal.cross(&point_other_edg_a);
258                            let point_other_edg_b_norm =
259                                other_edg_triangle_normal.cross(&point_other_edg_b);
260                            let edg_a_other_edg_a = edg_a - other_edg_a;
261                            let edg_a_other_edg_b = edg_a - other_edg_b;
262                            let edg_b_other_edg_a = edg_b - other_edg_a;
263                            let edg_b_other_edg_b = edg_b - other_edg_b;
264                            let ea_oea_dot_border_a =
265                                point_other_edg_a_norm.dot(&edg_a_other_edg_a);
266                            let eb_oea_dot_border_a =
267                                point_other_edg_a_norm.dot(&edg_b_other_edg_a);
268                            let ea_oeb_dot_border_b =
269                                point_other_edg_b_norm.dot(&edg_a_other_edg_b);
270                            let eb_oeb_dot_border_b =
271                                point_other_edg_b_norm.dot(&edg_b_other_edg_b);
272                            if ea_oea_dot_border_a < 0.0 && ea_oeb_dot_border_b > 0.0 {
273                                let dist_other_edg_p = f64::min(
274                                    point_other_edg_a.magnitude_squared(),
275                                    point_other_edg_b.magnitude_squared(),
276                                );
277                                if dist_edg_a_p > dist_other_edg_p {
278                                    remove = true;
279                                    break;
280                                }
281                            }
282                            if eb_oea_dot_border_a < 0.0 && eb_oeb_dot_border_b > 0.0 {
283                                let dist_other_edg_p = f64::min(
284                                    point_other_edg_a.magnitude_squared(),
285                                    point_other_edg_b.magnitude_squared(),
286                                );
287                                if dist_edg_b_p > dist_other_edg_p {
288                                    remove = true;
289                                    break;
290                                }
291                            }
292                            if (ea_oea_dot_border_a < 0.0 && eb_oeb_dot_border_b > 0.0)
293                                || (eb_oea_dot_border_a < 0.0 && ea_oeb_dot_border_b > 0.0)
294                            {
295                                let dist_other_edg_p =
296                                    dist_point_to_line_segment(point, other_edg_a, other_edg_b);
297                                if dist_edg_p > dist_other_edg_p {
298                                    remove = true;
299                                    break;
300                                }
301                            }
302                        }
303                    }
304                }
305                if remove {
306                    edges_facing_point.remove(i);
307                    edge_triangle_id.remove(i);
308                } else {
309                    edge_triangle_normals.insert(0, -edg_triangle_normal);
310                }
311            }
312
313            // Remove all triangles with vertices that are contained in two edges facing point
314            let edgenum = edges_facing_point.len();
315            if edgenum > 2 {
316                let mut edges_to_remove = HashSet::new();
317                let mut vertices_on_one_edge_start = HashMap::new();
318                let mut vertices_on_one_edge_end = HashMap::new();
319                let mut vertices_on_two_edges = HashMap::new();
320                for facing_edge in edges_facing_point.iter() {
321                    let res_a = vertices_on_one_edge_start
322                        .insert(facing_edge.a, (facing_edge.b, *facing_edge));
323                    if let Some(res_a) = res_a {
324                        if res_a.0 != facing_edge.b {
325                            vertices_on_one_edge_start.remove(&facing_edge.a);
326                            vertices_on_two_edges.insert(facing_edge.a, (res_a.1, *facing_edge));
327                        }
328                    }
329                    let res_b = vertices_on_one_edge_end
330                        .insert(facing_edge.b, (facing_edge.a, *facing_edge));
331                    if let Some(res_b) = res_b {
332                        if res_b.0 != facing_edge.a {
333                            vertices_on_one_edge_end.remove(&facing_edge.b);
334                            vertices_on_two_edges.insert(facing_edge.b, (res_b.1, *facing_edge));
335                        }
336                    }
337                }
338                let mut triangles_to_remove = Vec::new();
339                for t_id in 0..triangles.len() {
340                    let tri = triangles.get(t_id).unwrap();
341                    let res_a = vertices_on_two_edges.get(&tri.a);
342                    let res_b = vertices_on_two_edges.get(&tri.b);
343                    let res_c = vertices_on_two_edges.get(&tri.c);
344                    let a_on_two_edges = res_a.is_some();
345                    let b_on_two_edges = res_b.is_some();
346                    let c_on_two_edges = res_c.is_some();
347                    if a_on_two_edges || b_on_two_edges || c_on_two_edges {
348                        triangles_to_remove.push(t_id);
349                        if c_on_two_edges {
350                            edges_facing_point.push(Edge { a: tri.a, b: tri.b });
351                            edges_to_remove.insert(Edge { a: tri.b, b: tri.c });
352                            edges_to_remove.insert(Edge { a: tri.c, b: tri.a });
353                            edge_triangle_normals.push(tri.normal);
354                        }
355                        if b_on_two_edges {
356                            edges_facing_point.push(Edge { a: tri.c, b: tri.a });
357                            edges_to_remove.insert(Edge { a: tri.a, b: tri.b });
358                            edges_to_remove.insert(Edge { a: tri.b, b: tri.c });
359                            edge_triangle_normals.push(tri.normal);
360                        }
361                        if a_on_two_edges {
362                            edges_facing_point.push(Edge { a: tri.b, b: tri.c });
363                            edges_to_remove.insert(Edge { a: tri.c, b: tri.a });
364                            edges_to_remove.insert(Edge { a: tri.a, b: tri.b });
365                            edge_triangle_normals.push(tri.normal);
366                        }
367                    }
368                }
369                for t_id_remove in triangles_to_remove.iter().rev() {
370                    triangles.remove(*t_id_remove);
371                }
372                for efp in (0..edges_facing_point.len()).rev() {
373                    if edges_to_remove.contains(edges_facing_point.get(efp).unwrap()) {
374                        edges_facing_point.remove(efp);
375                        edge_triangle_normals.remove(efp);
376                    }
377                }
378            }
379
380            for i in 0..edges_facing_point.len() {
381                let edg = edges_facing_point[i];
382                triangles.push(Triangle {
383                    a: edg.a,
384                    b: edg.b,
385                    c: pointid,
386                    normal: edge_triangle_normals[i],
387                });
388            }
389        }
390    }
391}
392
393/// Calculates the distance of a point to an edge of a triangle. Assumes the point to be in the same plane as the triangle.
394/// `point`: the point that lies in the same plane as the edge
395/// `edge_a`: first vertex of the edge
396/// `edge_b`: second vertex of the edge
397/// 'triangle_normal': the normal of the triangle the edge belongs to
398fn dist_point_to_edge(
399    point: Vector3<f64>,
400    edge_a: Vector3<f64>,
401    edge_b: Vector3<f64>,
402    triangle_normal: Vector3<f64>,
403) -> f64 {
404    let pa = edge_a - point;
405    let edge_ab: Vector3<f64> = edge_b - edge_a;
406    let edge_ab_normal = triangle_normal.cross(&edge_ab);
407    edge_ab_normal.dot(&pa)
408}
409
410/// Calculates the distance of a point to a line segment.
411/// `point`: the point that lies in the same plane as the edge
412/// `line_a`: first vertex of the line segment
413/// `line_b`: second vertex of the line segment
414fn dist_point_to_line_segment(
415    point: Vector3<f64>,
416    segment_a: Vector3<f64>,
417    segment_b: Vector3<f64>,
418) -> f64 {
419    let ab: Vector3<f64> = segment_b - segment_a;
420    let ap: Vector3<f64> = point - segment_a;
421
422    if ap.dot(&ab) <= 0.0 {
423        return ap.magnitude();
424    }
425
426    let bp = point - segment_b;
427    if bp.dot(&ab) >= 0.0 {
428        return bp.magnitude();
429    }
430
431    ab.cross(&ap).magnitude() / ab.magnitude()
432}
433
434/// Adds the given edge to the set of outer edges. If the given edge is already contained in the set of outer edges it is removed and added to the set of inner edges.
435/// `a`: first vertex of the edge
436/// `b`: second vertex of the edge
437/// `outer_edges`: the set of outer edges
438/// `inner_edges`: the set of inner edges
439fn add_edge_to_outer_or_inner_edges(
440    a: usize,
441    b: usize,
442    outer_edges: &mut HashSet<Edge>,
443    inner_edges: &mut HashSet<Edge>,
444) {
445    let e = Edge { a, b };
446    if !outer_edges.insert(e) {
447        outer_edges.remove(&e);
448        inner_edges.insert(e);
449    }
450}
451
452/// Calculates the normal of a triangle formed b three points.
453/// `a`: first vertex of the triangle
454/// `b`: second vertex of the triangle
455/// `c`: third vertex of the triangle
456fn calc_normal(a: Vector3<f64>, b: Vector3<f64>, c: Vector3<f64>) -> Vector3<f64> {
457    let ab: Vector3<f64> = b - a;
458    let ac: Vector3<f64> = c - a;
459    ab.cross(&ac)
460}
461
462#[cfg(test)]
463mod tests {
464    use crate::convexhull;
465    use anyhow::Result;
466    use pasture_core::{
467        containers::{BorrowedBuffer, BorrowedBufferExt, BorrowedMutBufferExt, HashMapBuffer},
468        layout::attributes::POSITION_3D,
469        layout::PointType,
470        nalgebra::Vector3,
471    };
472    use pasture_derive::PointType;
473    use rand::{distributions::Uniform, thread_rng, Rng};
474
475    #[derive(
476        PointType, Default, Copy, Clone, Debug, bytemuck::AnyBitPattern, bytemuck::NoUninit,
477    )]
478    #[repr(C)]
479    struct TestPointTypeSmall {
480        #[pasture(BUILTIN_POSITION_3D)]
481        pub position: Vector3<f64>,
482    }
483
484    // Internal Tests
485    fn test_normals_for_triangles(triangles: &[convexhull::Triangle], normals: &Vec<Vector3<f64>>) {
486        for n in normals {
487            let mut found = false;
488            for t in triangles.iter() {
489                if f64::abs(t.normal.normalize().dot(n) - 1.0) < 0.0001 {
490                    found = true;
491                    break;
492                }
493            }
494            assert!(found);
495        }
496    }
497
498    fn test_all_points_inside_hull<'a, T: BorrowedBuffer<'a>>(
499        buffer: &'a T,
500        triangles: &[convexhull::Triangle],
501    ) {
502        let position_attribute = buffer
503            .point_layout()
504            .get_attribute_by_name(POSITION_3D.name())
505            .unwrap();
506        if position_attribute.datatype() == POSITION_3D.datatype() {
507            for point in buffer.view_attribute::<Vector3<f64>>(&POSITION_3D) {
508                for t in triangles.iter() {
509                    let a: Vector3<f64> = buffer.view_attribute(&POSITION_3D).at(t.a);
510                    let pa = a - point;
511                    assert!(pa.dot(&t.normal) >= -0.0000001);
512                }
513            }
514        } else {
515            let position_view = buffer
516                .view_attribute_with_conversion::<Vector3<f64>>(&POSITION_3D)
517                .expect("Can't convert POSITION_3D to Vector3<f64>");
518            for idx in 0..buffer.len() {
519                let point = position_view.at(idx);
520                for t in triangles.iter() {
521                    let a: Vector3<f64> = position_view.at(t.a);
522                    let pa = a - point;
523                    assert!(pa.dot(&t.normal) >= -0.0000001);
524                }
525            }
526        };
527    }
528
529    #[test]
530    fn test_convex_simple_triangle() -> Result<()> {
531        let mut buffer = HashMapBuffer::with_capacity(3, TestPointTypeSmall::layout());
532        buffer.view_mut().push_point(TestPointTypeSmall {
533            position: Vector3::new(0.0, 0.0, 0.0),
534        });
535        buffer.view_mut().push_point(TestPointTypeSmall {
536            position: Vector3::new(1.0, 0.0, 0.0),
537        });
538        buffer.view_mut().push_point(TestPointTypeSmall {
539            position: Vector3::new(0.0, 0.0, 1.0),
540        });
541        let result = convexhull::create_convex_hull(&buffer);
542
543        assert_eq!(result.len(), 2);
544        let normals = vec![Vector3::new(0.0, 1.0, 0.0), Vector3::new(0.0, -1.0, 0.0)];
545        test_normals_for_triangles(&result, &normals);
546
547        Ok(())
548    }
549
550    #[test]
551    fn test_convex_simple_tet_4_points() -> Result<()> {
552        let mut buffer = HashMapBuffer::with_capacity(4, TestPointTypeSmall::layout());
553        buffer.view_mut().push_point(TestPointTypeSmall {
554            position: Vector3::new(0.0, 0.0, 0.0),
555        });
556        buffer.view_mut().push_point(TestPointTypeSmall {
557            position: Vector3::new(1.0, 0.0, 0.0),
558        });
559        buffer.view_mut().push_point(TestPointTypeSmall {
560            position: Vector3::new(0.0, 0.0, 1.0),
561        });
562        buffer.view_mut().push_point(TestPointTypeSmall {
563            position: Vector3::new(0.0, 1.0, 0.0),
564        });
565        let result = convexhull::create_convex_hull(&buffer);
566
567        assert_eq!(result.len(), 4);
568        let normals = vec![
569            Vector3::new(-1.0, 0.0, 0.0),
570            Vector3::new(0.0, -1.0, 0.0),
571            Vector3::new(0.0, 0.0, -1.0),
572            Vector3::new(1.0, 1.0, 1.0).normalize(),
573        ];
574        test_normals_for_triangles(&result, &normals);
575        test_all_points_inside_hull(&buffer, &result);
576
577        Ok(())
578    }
579
580    #[test]
581    fn test_convex_simple_tet_5_points() -> Result<()> {
582        let mut buffer = HashMapBuffer::with_capacity(5, TestPointTypeSmall::layout());
583        buffer.view_mut().push_point(TestPointTypeSmall {
584            position: Vector3::new(0.0, 0.0, 0.0),
585        });
586        buffer.view_mut().push_point(TestPointTypeSmall {
587            position: Vector3::new(1.0, 0.0, 0.0),
588        });
589        buffer.view_mut().push_point(TestPointTypeSmall {
590            position: Vector3::new(0.0, 0.0, 1.0),
591        });
592        buffer.view_mut().push_point(TestPointTypeSmall {
593            position: Vector3::new(0.0, 1.0, 0.0),
594        });
595        buffer.view_mut().push_point(TestPointTypeSmall {
596            position: Vector3::new(-1.0, -1.0, -1.0),
597        });
598        let result = convexhull::create_convex_hull(&buffer);
599
600        assert_eq!(result.len(), 4);
601        let normals = vec![
602            Vector3::new(1.0, 1.0, 1.0).normalize(),
603            Vector3::new(1.0, 1.0, -3.0).normalize(),
604            Vector3::new(1.0, -3.0, 1.0).normalize(),
605            Vector3::new(-3.0, 1.0, 1.0).normalize(),
606        ];
607        test_normals_for_triangles(&result, &normals);
608        test_all_points_inside_hull(&buffer, &result);
609
610        Ok(())
611    }
612
613    #[test]
614    fn test_convex_1_point() -> Result<()> {
615        let mut buffer = HashMapBuffer::with_capacity(1, TestPointTypeSmall::layout());
616        buffer.view_mut().push_point(TestPointTypeSmall {
617            position: Vector3::new(0.0, 0.0, 0.0),
618        });
619        let result = convexhull::create_convex_hull(&buffer);
620
621        assert_eq!(result.len(), 1);
622        assert_eq!(result[0].a, 0);
623
624        Ok(())
625    }
626
627    #[test]
628    fn test_convex_line_2_points() -> Result<()> {
629        let mut buffer = HashMapBuffer::with_capacity(2, TestPointTypeSmall::layout());
630        buffer.view_mut().push_point(TestPointTypeSmall {
631            position: Vector3::new(0.0, 0.0, 0.0),
632        });
633        buffer.view_mut().push_point(TestPointTypeSmall {
634            position: Vector3::new(1.0, 0.0, 0.0),
635        });
636        let result = convexhull::create_convex_hull(&buffer);
637
638        assert_eq!(result.len(), 1);
639        assert_eq!(result[0].a, 0);
640        assert_eq!(result[0].b, 1);
641
642        Ok(())
643    }
644
645    #[test]
646    fn test_convex_line_3_points() -> Result<()> {
647        let mut buffer = HashMapBuffer::with_capacity(3, TestPointTypeSmall::layout());
648        buffer.view_mut().push_point(TestPointTypeSmall {
649            position: Vector3::new(0.0, 0.0, 0.0),
650        });
651        buffer.view_mut().push_point(TestPointTypeSmall {
652            position: Vector3::new(1.0, 0.0, 0.0),
653        });
654        buffer.view_mut().push_point(TestPointTypeSmall {
655            position: Vector3::new(2.0, 0.0, 0.0),
656        });
657        let result = convexhull::create_convex_hull(&buffer);
658
659        assert_eq!(result.len(), 1);
660        assert_eq!(result[0].a, 0);
661        assert_eq!(result[0].b, 2);
662
663        Ok(())
664    }
665
666    #[test]
667    fn test_convex_line_4_points() -> Result<()> {
668        let mut buffer = HashMapBuffer::with_capacity(4, TestPointTypeSmall::layout());
669        buffer.view_mut().push_point(TestPointTypeSmall {
670            position: Vector3::new(0.0, 0.0, 0.0),
671        });
672        buffer.view_mut().push_point(TestPointTypeSmall {
673            position: Vector3::new(1.0, 0.0, 0.0),
674        });
675        buffer.view_mut().push_point(TestPointTypeSmall {
676            position: Vector3::new(2.0, 0.0, 0.0),
677        });
678        buffer.view_mut().push_point(TestPointTypeSmall {
679            position: Vector3::new(-1.0, 0.0, 0.0),
680        });
681        let result = convexhull::create_convex_hull(&buffer);
682
683        assert_eq!(result.len(), 1);
684        assert_eq!(result[0].a, 3);
685        assert_eq!(result[0].b, 2);
686
687        Ok(())
688    }
689
690    #[test]
691    fn test_convex_plane_4_points() -> Result<()> {
692        let mut buffer = HashMapBuffer::with_capacity(4, TestPointTypeSmall::layout());
693        buffer.view_mut().push_point(TestPointTypeSmall {
694            position: Vector3::new(0.0, 0.0, 0.0),
695        });
696        buffer.view_mut().push_point(TestPointTypeSmall {
697            position: Vector3::new(0.0, 0.0, 1.0),
698        });
699        buffer.view_mut().push_point(TestPointTypeSmall {
700            position: Vector3::new(1.0, 0.0, 0.0),
701        });
702        buffer.view_mut().push_point(TestPointTypeSmall {
703            position: Vector3::new(1.0, 0.0, 1.0),
704        });
705        let result = convexhull::create_convex_hull(&buffer);
706
707        assert_eq!(result.len(), 4);
708        let normals = vec![Vector3::new(0.0, 1.0, 0.0), Vector3::new(0.0, -1.0, 0.0)];
709        test_normals_for_triangles(&result, &normals);
710        test_all_points_inside_hull(&buffer, &result);
711
712        Ok(())
713    }
714
715    #[test]
716    fn test_convex_2d_point_in_square() -> Result<()> {
717        let mut buffer = HashMapBuffer::with_capacity(5, TestPointTypeSmall::layout());
718        buffer.view_mut().push_point(TestPointTypeSmall {
719            position: Vector3::new(0.0, 0.0, 0.0),
720        });
721        buffer.view_mut().push_point(TestPointTypeSmall {
722            position: Vector3::new(-1.0, -1.0, 0.0),
723        });
724        buffer.view_mut().push_point(TestPointTypeSmall {
725            position: Vector3::new(1.0, -1.0, 0.0),
726        });
727        buffer.view_mut().push_point(TestPointTypeSmall {
728            position: Vector3::new(1.0, 1.0, 0.0),
729        });
730        buffer.view_mut().push_point(TestPointTypeSmall {
731            position: Vector3::new(-1.0, 1.0, 0.0),
732        });
733        let result = convexhull::create_convex_hull(&buffer);
734
735        assert_eq!(result.len(), 4);
736        let normals = vec![Vector3::new(0.0, 0.0, 1.0), Vector3::new(0.0, 0.0, -1.0)];
737        test_normals_for_triangles(&result, &normals);
738        test_all_points_inside_hull(&buffer, &result);
739
740        Ok(())
741    }
742
743    #[test]
744    fn test_convex_2d_point_next_to_square_1() -> Result<()> {
745        let mut buffer = HashMapBuffer::with_capacity(5, TestPointTypeSmall::layout());
746        buffer.view_mut().push_point(TestPointTypeSmall {
747            position: Vector3::new(-1.0, -1.0, 0.0),
748        });
749        buffer.view_mut().push_point(TestPointTypeSmall {
750            position: Vector3::new(1.0, -1.0, 0.0),
751        });
752        buffer.view_mut().push_point(TestPointTypeSmall {
753            position: Vector3::new(1.0, 1.0, 0.0),
754        });
755        buffer.view_mut().push_point(TestPointTypeSmall {
756            position: Vector3::new(-1.0, 1.0, 0.0),
757        });
758        buffer.view_mut().push_point(TestPointTypeSmall {
759            position: Vector3::new(2.0, 0.0, 0.0),
760        });
761        let result = convexhull::create_convex_hull(&buffer);
762
763        assert_eq!(result.len(), 6);
764        let normals = vec![Vector3::new(0.0, 0.0, 1.0), Vector3::new(0.0, 0.0, -1.0)];
765        test_normals_for_triangles(&result, &normals);
766        test_all_points_inside_hull(&buffer, &result);
767
768        Ok(())
769    }
770
771    #[test]
772    fn test_convex_2d_point_next_to_square_2() -> Result<()> {
773        let mut buffer = HashMapBuffer::with_capacity(5, TestPointTypeSmall::layout());
774        buffer.view_mut().push_point(TestPointTypeSmall {
775            position: Vector3::new(-1.0, -1.0, 0.0),
776        });
777        buffer.view_mut().push_point(TestPointTypeSmall {
778            position: Vector3::new(1.0, -1.0, 0.0),
779        });
780        buffer.view_mut().push_point(TestPointTypeSmall {
781            position: Vector3::new(1.0, 1.0, 0.0),
782        });
783        buffer.view_mut().push_point(TestPointTypeSmall {
784            position: Vector3::new(-1.0, 1.0, 0.0),
785        });
786        buffer.view_mut().push_point(TestPointTypeSmall {
787            position: Vector3::new(0.0, 2.0, 0.0),
788        });
789        let result = convexhull::create_convex_hull(&buffer);
790
791        assert_eq!(result.len(), 6);
792        let normals = vec![Vector3::new(0.0, 0.0, 1.0), Vector3::new(0.0, 0.0, -1.0)];
793        test_normals_for_triangles(&result, &normals);
794        test_all_points_inside_hull(&buffer, &result);
795
796        Ok(())
797    }
798
799    #[test]
800    fn test_convex_2d_point_next_to_square_3() -> Result<()> {
801        let mut buffer = HashMapBuffer::with_capacity(5, TestPointTypeSmall::layout());
802        buffer.view_mut().push_point(TestPointTypeSmall {
803            position: Vector3::new(-1.0, -1.0, 0.0),
804        });
805        buffer.view_mut().push_point(TestPointTypeSmall {
806            position: Vector3::new(1.0, -1.0, 0.0),
807        });
808        buffer.view_mut().push_point(TestPointTypeSmall {
809            position: Vector3::new(1.0, 1.0, 0.0),
810        });
811        buffer.view_mut().push_point(TestPointTypeSmall {
812            position: Vector3::new(-1.0, 1.0, 0.0),
813        });
814        buffer.view_mut().push_point(TestPointTypeSmall {
815            position: Vector3::new(2.0, 2.0, 0.0),
816        });
817        let result = convexhull::create_convex_hull(&buffer);
818
819        assert_eq!(result.len(), 4);
820        let normals = vec![Vector3::new(0.0, 0.0, 1.0), Vector3::new(0.0, 0.0, -1.0)];
821        test_normals_for_triangles(&result, &normals);
822        test_all_points_inside_hull(&buffer, &result);
823
824        Ok(())
825    }
826
827    #[test]
828    fn test_convex_2d_point_next_to_square_4() -> Result<()> {
829        let mut buffer = HashMapBuffer::with_capacity(5, TestPointTypeSmall::layout());
830        buffer.view_mut().push_point(TestPointTypeSmall {
831            position: Vector3::new(-1.0, -1.0, 0.0),
832        });
833        buffer.view_mut().push_point(TestPointTypeSmall {
834            position: Vector3::new(1.0, -1.0, 0.0),
835        });
836        buffer.view_mut().push_point(TestPointTypeSmall {
837            position: Vector3::new(1.0, 1.0, 0.0),
838        });
839        buffer.view_mut().push_point(TestPointTypeSmall {
840            position: Vector3::new(-1.0, 1.0, 0.0),
841        });
842        buffer.view_mut().push_point(TestPointTypeSmall {
843            position: Vector3::new(-2.0, 2.0, 0.0),
844        });
845        let result = convexhull::create_convex_hull(&buffer);
846
847        assert_eq!(result.len(), 4);
848        let normals = vec![Vector3::new(0.0, 0.0, 1.0), Vector3::new(0.0, 0.0, -1.0)];
849        test_normals_for_triangles(&result, &normals);
850        test_all_points_inside_hull(&buffer, &result);
851
852        Ok(())
853    }
854
855    #[test]
856    fn test_convex_random_1d_points_in_box_create_box_first() -> Result<()> {
857        let mut buffer = HashMapBuffer::with_capacity(22, TestPointTypeSmall::layout());
858        buffer.view_mut().push_point(TestPointTypeSmall {
859            position: Vector3::new(-1.0, 0.0, 0.0),
860        });
861        buffer.view_mut().push_point(TestPointTypeSmall {
862            position: Vector3::new(1.0, 0.0, 0.0),
863        });
864        let mut rng = thread_rng();
865        for _ in 0..20 {
866            buffer.view_mut().push_point(TestPointTypeSmall {
867                position: Vector3::new(rng.sample(Uniform::new(-0.9, 0.9)), 0.0, 0.0),
868            });
869        }
870        let result = convexhull::convex_hull_as_points(&buffer);
871
872        assert_eq!(result.len(), 2);
873        assert!(result.contains(&0));
874        assert!(result.contains(&1));
875
876        Ok(())
877    }
878
879    #[test]
880    fn test_convex_random_1d_points_in_box_create_box_last() -> Result<()> {
881        let mut buffer = HashMapBuffer::with_capacity(22, TestPointTypeSmall::layout());
882        let mut rng = thread_rng();
883        for _ in 0..20 {
884            buffer.view_mut().push_point(TestPointTypeSmall {
885                position: Vector3::new(rng.sample(Uniform::new(-0.9, 0.9)), 0.0, 0.0),
886            });
887        }
888        buffer.view_mut().push_point(TestPointTypeSmall {
889            position: Vector3::new(-1.0, 0.0, 0.0),
890        });
891        buffer.view_mut().push_point(TestPointTypeSmall {
892            position: Vector3::new(1.0, 0.0, 0.0),
893        });
894        let result = convexhull::convex_hull_as_points(&buffer);
895
896        assert_eq!(result.len(), 2);
897        assert!(result.contains(&20));
898        assert!(result.contains(&21));
899
900        Ok(())
901    }
902
903    #[test]
904    fn test_convex_random_2d_points_in_box_create_box_first() -> Result<()> {
905        let mut buffer = HashMapBuffer::with_capacity(24, TestPointTypeSmall::layout());
906        buffer.view_mut().push_point(TestPointTypeSmall {
907            position: Vector3::new(-1.0, -1.0, 0.0),
908        });
909        buffer.view_mut().push_point(TestPointTypeSmall {
910            position: Vector3::new(1.0, -1.0, 0.0),
911        });
912        buffer.view_mut().push_point(TestPointTypeSmall {
913            position: Vector3::new(1.0, 1.0, 0.0),
914        });
915        buffer.view_mut().push_point(TestPointTypeSmall {
916            position: Vector3::new(-1.0, 1.0, 0.0),
917        });
918        let mut rng = thread_rng();
919        for _ in 0..20 {
920            buffer.view_mut().push_point(TestPointTypeSmall {
921                position: Vector3::new(
922                    rng.sample(Uniform::new(-0.9, 0.9)),
923                    rng.sample(Uniform::new(-0.9, 0.9)),
924                    0.0,
925                ),
926            });
927        }
928        let result = convexhull::create_convex_hull(&buffer);
929
930        assert_eq!(result.len(), 4);
931        let normals = vec![Vector3::new(0.0, 0.0, 1.0), Vector3::new(0.0, 0.0, -1.0)];
932        test_normals_for_triangles(&result, &normals);
933        test_all_points_inside_hull(&buffer, &result);
934
935        Ok(())
936    }
937
938    #[test]
939    fn test_convex_2d_points_in_box_create_box_last_case_1() -> Result<()> {
940        let mut buffer = HashMapBuffer::with_capacity(6, TestPointTypeSmall::layout());
941        buffer.view_mut().push_point(TestPointTypeSmall {
942            position: Vector3::new(0.5, 0.2, 0.0),
943        });
944        buffer.view_mut().push_point(TestPointTypeSmall {
945            position: Vector3::new(-0.5, -0.3, 0.0),
946        });
947        buffer.view_mut().push_point(TestPointTypeSmall {
948            position: Vector3::new(-1.0, -1.0, 0.0),
949        });
950        buffer.view_mut().push_point(TestPointTypeSmall {
951            position: Vector3::new(1.0, -1.0, 0.0),
952        });
953        buffer.view_mut().push_point(TestPointTypeSmall {
954            position: Vector3::new(1.0, 1.0, 0.0),
955        });
956        buffer.view_mut().push_point(TestPointTypeSmall {
957            position: Vector3::new(-1.0, 1.0, 0.0),
958        });
959        let result = convexhull::create_convex_hull(&buffer);
960
961        assert_eq!(result.len(), 4);
962        let normals = vec![Vector3::new(0.0, 0.0, 1.0), Vector3::new(0.0, 0.0, -1.0)];
963        test_normals_for_triangles(&result, &normals);
964        test_all_points_inside_hull(&buffer, &result);
965
966        Ok(())
967    }
968
969    #[test]
970    fn test_convex_2d_points_in_box_create_box_last_case_2() -> Result<()> {
971        let mut buffer = HashMapBuffer::with_capacity(6, TestPointTypeSmall::layout());
972        buffer.view_mut().push_point(TestPointTypeSmall {
973            position: Vector3::new(0.2, 0.1, 0.0),
974        });
975        buffer.view_mut().push_point(TestPointTypeSmall {
976            position: Vector3::new(-0.9, 0.3, 0.0),
977        });
978        buffer.view_mut().push_point(TestPointTypeSmall {
979            position: Vector3::new(-1.0, -1.0, 0.0),
980        });
981        buffer.view_mut().push_point(TestPointTypeSmall {
982            position: Vector3::new(1.0, -1.0, 0.0),
983        });
984        buffer.view_mut().push_point(TestPointTypeSmall {
985            position: Vector3::new(1.0, 1.0, 0.0),
986        });
987        buffer.view_mut().push_point(TestPointTypeSmall {
988            position: Vector3::new(-1.0, 1.0, 0.0),
989        });
990        let result = convexhull::create_convex_hull(&buffer);
991
992        assert_eq!(result.len(), 4);
993        let normals = vec![Vector3::new(0.0, 0.0, 1.0), Vector3::new(0.0, 0.0, -1.0)];
994        test_normals_for_triangles(&result, &normals);
995        test_all_points_inside_hull(&buffer, &result);
996
997        Ok(())
998    }
999
1000    #[test]
1001    fn test_convex_2d_points_in_box_create_box_last_case_3() -> Result<()> {
1002        let mut buffer = HashMapBuffer::with_capacity(7, TestPointTypeSmall::layout());
1003        buffer.view_mut().push_point(TestPointTypeSmall {
1004            position: Vector3::new(-0.3, -0.3, 0.0),
1005        });
1006        buffer.view_mut().push_point(TestPointTypeSmall {
1007            position: Vector3::new(0.9, -0.4, 0.0),
1008        });
1009        buffer.view_mut().push_point(TestPointTypeSmall {
1010            position: Vector3::new(0.2, 0.1, 0.0),
1011        });
1012        buffer.view_mut().push_point(TestPointTypeSmall {
1013            position: Vector3::new(-1.0, -1.0, 0.0),
1014        });
1015        buffer.view_mut().push_point(TestPointTypeSmall {
1016            position: Vector3::new(1.0, -1.0, 0.0),
1017        });
1018        buffer.view_mut().push_point(TestPointTypeSmall {
1019            position: Vector3::new(1.0, 1.0, 0.0),
1020        });
1021        buffer.view_mut().push_point(TestPointTypeSmall {
1022            position: Vector3::new(-1.0, 1.0, 0.0),
1023        });
1024        let result = convexhull::create_convex_hull(&buffer);
1025
1026        assert_eq!(result.len(), 4);
1027        let normals = vec![Vector3::new(0.0, 0.0, 1.0), Vector3::new(0.0, 0.0, -1.0)];
1028        test_normals_for_triangles(&result, &normals);
1029        test_all_points_inside_hull(&buffer, &result);
1030
1031        Ok(())
1032    }
1033
1034    #[test]
1035    fn test_convex_random_points_in_box_create_box_first() -> Result<()> {
1036        let mut buffer = HashMapBuffer::with_capacity(28, TestPointTypeSmall::layout());
1037        buffer.view_mut().push_point(TestPointTypeSmall {
1038            position: Vector3::new(-1.0, -1.0, -1.0),
1039        });
1040        buffer.view_mut().push_point(TestPointTypeSmall {
1041            position: Vector3::new(-1.0, -1.0, 1.0),
1042        });
1043        buffer.view_mut().push_point(TestPointTypeSmall {
1044            position: Vector3::new(-1.0, 1.0, -1.0),
1045        });
1046        buffer.view_mut().push_point(TestPointTypeSmall {
1047            position: Vector3::new(-1.0, 1.0, 1.0),
1048        });
1049        buffer.view_mut().push_point(TestPointTypeSmall {
1050            position: Vector3::new(1.0, -1.0, -1.0),
1051        });
1052        buffer.view_mut().push_point(TestPointTypeSmall {
1053            position: Vector3::new(1.0, -1.0, 1.0),
1054        });
1055        buffer.view_mut().push_point(TestPointTypeSmall {
1056            position: Vector3::new(1.0, 1.0, -1.0),
1057        });
1058        buffer.view_mut().push_point(TestPointTypeSmall {
1059            position: Vector3::new(1.0, 1.0, 1.0),
1060        });
1061        let mut rng = thread_rng();
1062        for _ in 0..20 {
1063            buffer.view_mut().push_point(TestPointTypeSmall {
1064                position: Vector3::new(
1065                    rng.sample(Uniform::new(-0.9, 0.9)),
1066                    rng.sample(Uniform::new(-0.9, 0.9)),
1067                    rng.sample(Uniform::new(-0.9, 0.9)),
1068                ),
1069            });
1070        }
1071        let result = convexhull::create_convex_hull(&buffer);
1072
1073        assert_eq!(result.len(), 12);
1074        let normals = vec![
1075            Vector3::new(1.0, 0.0, 0.0),
1076            Vector3::new(0.0, 1.0, 0.0),
1077            Vector3::new(0.0, 0.0, 1.0),
1078            Vector3::new(-1.0, 0.0, 0.0),
1079            Vector3::new(0.0, -1.0, 0.0),
1080            Vector3::new(0.0, 0.0, -1.0),
1081        ];
1082        test_normals_for_triangles(&result, &normals);
1083        test_all_points_inside_hull(&buffer, &result);
1084
1085        Ok(())
1086    }
1087
1088    #[test]
1089    fn test_convex_random_points_in_box_create_box_last() -> Result<()> {
1090        let mut buffer = HashMapBuffer::with_capacity(28, TestPointTypeSmall::layout());
1091        let mut rng = thread_rng();
1092        for _ in 0..20 {
1093            buffer.view_mut().push_point(TestPointTypeSmall {
1094                position: Vector3::new(
1095                    rng.sample(Uniform::new(-0.9, 0.9)),
1096                    rng.sample(Uniform::new(-0.9, 0.9)),
1097                    rng.sample(Uniform::new(-0.9, 0.9)),
1098                ),
1099            });
1100        }
1101        buffer.view_mut().push_point(TestPointTypeSmall {
1102            position: Vector3::new(-1.0, -1.0, -1.0),
1103        });
1104        buffer.view_mut().push_point(TestPointTypeSmall {
1105            position: Vector3::new(-1.0, -1.0, 1.0),
1106        });
1107        buffer.view_mut().push_point(TestPointTypeSmall {
1108            position: Vector3::new(-1.0, 1.0, -1.0),
1109        });
1110        buffer.view_mut().push_point(TestPointTypeSmall {
1111            position: Vector3::new(-1.0, 1.0, 1.0),
1112        });
1113        buffer.view_mut().push_point(TestPointTypeSmall {
1114            position: Vector3::new(1.0, -1.0, -1.0),
1115        });
1116        buffer.view_mut().push_point(TestPointTypeSmall {
1117            position: Vector3::new(1.0, -1.0, 1.0),
1118        });
1119        buffer.view_mut().push_point(TestPointTypeSmall {
1120            position: Vector3::new(1.0, 1.0, -1.0),
1121        });
1122        buffer.view_mut().push_point(TestPointTypeSmall {
1123            position: Vector3::new(1.0, 1.0, 1.0),
1124        });
1125        let result = convexhull::create_convex_hull(&buffer);
1126
1127        assert_eq!(result.len(), 12);
1128        let normals = vec![
1129            Vector3::new(1.0, 0.0, 0.0),
1130            Vector3::new(0.0, 1.0, 0.0),
1131            Vector3::new(0.0, 0.0, 1.0),
1132            Vector3::new(-1.0, 0.0, 0.0),
1133            Vector3::new(0.0, -1.0, 0.0),
1134            Vector3::new(0.0, 0.0, -1.0),
1135        ];
1136        test_normals_for_triangles(&result, &normals);
1137        test_all_points_inside_hull(&buffer, &result);
1138
1139        Ok(())
1140    }
1141
1142    #[test]
1143    fn test_convex_random_points() -> Result<()> {
1144        let mut buffer = HashMapBuffer::with_capacity(100, TestPointTypeSmall::layout());
1145        let mut rng = thread_rng();
1146        for _ in 0..100 {
1147            buffer.view_mut().push_point(TestPointTypeSmall {
1148                position: Vector3::new(
1149                    rng.sample(Uniform::new(-100.0, 100.0)),
1150                    rng.sample(Uniform::new(-100.0, 100.0)),
1151                    rng.sample(Uniform::new(-100.0, 100.0)),
1152                ),
1153            });
1154        }
1155        let result = convexhull::create_convex_hull(&buffer);
1156
1157        test_all_points_inside_hull(&buffer, &result);
1158
1159        Ok(())
1160    }
1161
1162    // Interface Tests
1163    #[test]
1164    fn test_convex_0_point_output_mesh_error() -> Result<()> {
1165        let buffer = HashMapBuffer::with_capacity(0, TestPointTypeSmall::layout());
1166        let result = convexhull::convex_hull_as_triangle_mesh(&buffer);
1167
1168        assert_eq!(
1169            result.unwrap_err().to_string(),
1170            "input buffer cointains too few linearly independent points"
1171        );
1172
1173        Ok(())
1174    }
1175
1176    #[test]
1177    fn test_convex_1_point_output_mesh_error() -> Result<()> {
1178        let mut buffer = HashMapBuffer::with_capacity(1, TestPointTypeSmall::layout());
1179        buffer.view_mut().push_point(TestPointTypeSmall {
1180            position: Vector3::new(0.0, 0.0, 0.0),
1181        });
1182        let result = convexhull::convex_hull_as_triangle_mesh(&buffer);
1183
1184        assert_eq!(
1185            result.unwrap_err().to_string(),
1186            "input buffer cointains too few linearly independent points"
1187        );
1188
1189        Ok(())
1190    }
1191
1192    #[test]
1193    fn test_convex_2_point_output_mesh_error() -> Result<()> {
1194        let mut buffer = HashMapBuffer::with_capacity(2, TestPointTypeSmall::layout());
1195        buffer.view_mut().push_point(TestPointTypeSmall {
1196            position: Vector3::new(0.0, 0.0, 0.0),
1197        });
1198        buffer.view_mut().push_point(TestPointTypeSmall {
1199            position: Vector3::new(1.0, 0.0, 0.0),
1200        });
1201        let result = convexhull::convex_hull_as_triangle_mesh(&buffer);
1202
1203        assert_eq!(
1204            result.unwrap_err().to_string(),
1205            "input buffer cointains too few linearly independent points"
1206        );
1207
1208        Ok(())
1209    }
1210
1211    #[test]
1212    fn test_convex_3_point_output_mesh_error_same_point() -> Result<()> {
1213        let mut buffer = HashMapBuffer::with_capacity(3, TestPointTypeSmall::layout());
1214        buffer.view_mut().push_point(TestPointTypeSmall {
1215            position: Vector3::new(0.0, 0.0, 0.0),
1216        });
1217        buffer.view_mut().push_point(TestPointTypeSmall {
1218            position: Vector3::new(0.0, 0.0, 0.0),
1219        });
1220        buffer.view_mut().push_point(TestPointTypeSmall {
1221            position: Vector3::new(0.0, 0.0, 0.0),
1222        });
1223        let result = convexhull::convex_hull_as_triangle_mesh(&buffer);
1224
1225        assert_eq!(
1226            result.unwrap_err().to_string(),
1227            "input buffer cointains too few linearly independent points"
1228        );
1229
1230        Ok(())
1231    }
1232
1233    #[test]
1234    fn test_convex_3_point_output_mesh_error_line() -> Result<()> {
1235        let mut buffer = HashMapBuffer::with_capacity(3, TestPointTypeSmall::layout());
1236        buffer.view_mut().push_point(TestPointTypeSmall {
1237            position: Vector3::new(0.0, 0.0, 0.0),
1238        });
1239        buffer.view_mut().push_point(TestPointTypeSmall {
1240            position: Vector3::new(1.0, 0.0, 0.0),
1241        });
1242        buffer.view_mut().push_point(TestPointTypeSmall {
1243            position: Vector3::new(2.0, 0.0, 0.0),
1244        });
1245        let result = convexhull::convex_hull_as_triangle_mesh(&buffer);
1246
1247        assert_eq!(
1248            result.unwrap_err().to_string(),
1249            "input buffer cointains too few linearly independent points"
1250        );
1251
1252        Ok(())
1253    }
1254
1255    #[test]
1256    fn test_convex_3_point_output_mesh_no_error() -> Result<()> {
1257        let mut buffer = HashMapBuffer::with_capacity(3, TestPointTypeSmall::layout());
1258        buffer.view_mut().push_point(TestPointTypeSmall {
1259            position: Vector3::new(0.0, 0.0, 0.0),
1260        });
1261        buffer.view_mut().push_point(TestPointTypeSmall {
1262            position: Vector3::new(1.0, 0.0, 0.0),
1263        });
1264        buffer.view_mut().push_point(TestPointTypeSmall {
1265            position: Vector3::new(0.0, 1.0, 0.0),
1266        });
1267        let result = convexhull::convex_hull_as_triangle_mesh(&buffer);
1268        let result_unwrapped = result.unwrap();
1269
1270        assert_eq!(result_unwrapped.len(), 2);
1271        assert!(result_unwrapped.contains(&Vector3::new(0, 1, 2)));
1272        assert!(result_unwrapped.contains(&Vector3::new(0, 2, 1)));
1273
1274        Ok(())
1275    }
1276
1277    #[test]
1278    fn test_convex_3_point_output_points_line() -> Result<()> {
1279        let mut buffer = HashMapBuffer::with_capacity(3, TestPointTypeSmall::layout());
1280        buffer.view_mut().push_point(TestPointTypeSmall {
1281            position: Vector3::new(0.0, 0.0, 0.0),
1282        });
1283        buffer.view_mut().push_point(TestPointTypeSmall {
1284            position: Vector3::new(1.0, 0.0, 0.0),
1285        });
1286        buffer.view_mut().push_point(TestPointTypeSmall {
1287            position: Vector3::new(2.0, 0.0, 0.0),
1288        });
1289        let result = convexhull::convex_hull_as_points(&buffer);
1290
1291        assert_eq!(result.len(), 2);
1292        assert!(result.contains(&0));
1293        assert!(result.contains(&2));
1294
1295        Ok(())
1296    }
1297
1298    #[test]
1299    fn test_convex_4_point_output_point_in_triangle() -> Result<()> {
1300        let mut buffer = HashMapBuffer::with_capacity(4, TestPointTypeSmall::layout());
1301        buffer.view_mut().push_point(TestPointTypeSmall {
1302            position: Vector3::new(0.0, 0.0, 0.0),
1303        });
1304        buffer.view_mut().push_point(TestPointTypeSmall {
1305            position: Vector3::new(-1.0, -1.0, 0.0),
1306        });
1307        buffer.view_mut().push_point(TestPointTypeSmall {
1308            position: Vector3::new(1.0, -1.0, 0.0),
1309        });
1310        buffer.view_mut().push_point(TestPointTypeSmall {
1311            position: Vector3::new(0.0, 1.0, 0.0),
1312        });
1313        let result = convexhull::convex_hull_as_points(&buffer);
1314
1315        assert_eq!(result.len(), 3);
1316        assert!(result.contains(&1));
1317        assert!(result.contains(&2));
1318        assert!(result.contains(&3));
1319
1320        Ok(())
1321    }
1322
1323    #[derive(
1324        PointType, Default, Copy, Clone, Debug, bytemuck::AnyBitPattern, bytemuck::NoUninit,
1325    )]
1326    #[repr(C)]
1327    struct TestPointTypeNoPositions {
1328        #[pasture(BUILTIN_INTENSITY)]
1329        pub intensity: u16,
1330    }
1331
1332    #[test]
1333    #[should_panic(expected = "point buffer contains no position attribute")]
1334    fn test_convex_no_positions_panic() {
1335        let mut buffer = HashMapBuffer::with_capacity(1, TestPointTypeNoPositions::layout());
1336        buffer
1337            .view_mut()
1338            .push_point(TestPointTypeNoPositions { intensity: 1 });
1339        let _result = convexhull::convex_hull_as_triangle_mesh(&buffer);
1340    }
1341}
pasture_algorithms/convexhull.rs

pasture_algorithms/
convexhull.rs
