qchull 2.0.1-beta.0

// Copyright (C) 2020-2025 qchull authors. All Rights Reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

use std::cmp::Ordering;

use glam_det::{Cross, Dot, Point3, UnitVec3, Vec3};
use smallvec::SmallVec;
use vslab::{new_type_id, Slab};

use crate::common::normalize_and_len;
use crate::half_edge::{EdgeMap, HalfEdge, HalfEdgeKey};
use crate::quick_hull_3d::MAX_POINT_COUNT;

new_type_id!(FaceKey);
pub(crate) type FaceMap = Slab<FaceKey, Face>;
pub(crate) type FaceIndexSmallVec = SmallVec<[FaceKey; 16]>;
pub(crate) type ConflictPointIndexSmallVec = SmallVec<[usize; 16]>;

/// the vertex of the face is in clockwise order in right-hand coordinate system
/// and counter-clockwise order in left-hand coordinate system.
///
/// the normal is toward the outside of the convex hull.
pub struct Face {
    pub edge_index: HalfEdgeKey,
    pub normal: UnitVec3,
    pub center: Point3,
    pub area: f32,
    pub(crate) visited: bool,
    pub(crate) conflict_points: ConflictPointIndexSmallVec,
    pub(crate) mark: FaceState,
    pub num_points: u32,
    pub max_distance_for_expand: f32,
    #[cfg(any(test, feature = "safe_check", feature = "dump"))]
    pub vertex: Vec<usize>,
}

#[derive(PartialEq, Clone, Copy, Debug)]
pub enum FaceState {
    Visible,
    NonConvex,
    Delete,
}

impl Face {
    #[inline]
    pub(crate) fn new(
        edge_index: HalfEdgeKey,
        center: Point3,
        normal: UnitVec3,
        area: f32,
        num_points: u32,
    ) -> Self {
        Self {
            edge_index,
            normal,
            center,
            area,
            visited: false,
            conflict_points: ConflictPointIndexSmallVec::default(),
            mark: FaceState::Visible,
            num_points,
            max_distance_for_expand: 0.0,
            #[cfg(any(test, feature = "safe_check", feature = "dump"))]
            vertex: vec![],
        }
    }

    pub(crate) fn update_normal_and_center(&mut self, edges: &EdgeMap, points: &[Point3]) {
        if self.mark == FaceState::Delete {
            return;
        }
        #[cfg(any(test, feature = "safe_check", feature = "dump"))]
        self.vertex.clear();
        let edge_iter = &mut FaceEdgeIter::new(self.edge_index, edges);
        let mut normal = Vec3::ZERO;
        let mut center = Vec3::ZERO;
        let mut count = 0_u32;
        let mut first_iter = edge_iter.take(1);
        let (_, first_edge) = first_iter
            .next()
            .expect("the face has no edge,it should not happen");
        let a = points[first_edge.origin];
        center += a.as_vec3();
        count += 1;
        #[cfg(any(test, feature = "safe_check", feature = "dump"))]
        self.vertex.push(first_edge.origin);
        let mut last_vector = points[first_edge.destination] - a;
        for (_, edge) in edge_iter {
            #[cfg(any(test, feature = "safe_check", feature = "dump"))]
            self.vertex.push(edge.origin);
            let b = points[edge.destination];
            let this_vector = b - a;
            let cross = this_vector.cross(last_vector);
            normal += cross;
            center += points[edge.origin].as_vec3();
            count += 1;

            debug_assert!(count < MAX_POINT_COUNT, "face point count overflow");
            last_vector = this_vector;
        }
        //if a,b,c is collinear, let the normal be unit x-axis, this will merge after create
        // new faces
        (self.normal, self.area) = normalize_and_len(normal, 0.0);
        self.num_points = count;
        self.center = Point3::from_vec3(center / count as f32);
    }

    /// # Panics
    ///
    /// Panic if the edge count is 0 or less than 2
    ///
    /// if edge count is less than 3,  no triangle will be created
    pub fn get_face_triangles(&self, edges: &EdgeMap, triangles: &mut Vec<usize>) {
        let mut iter = FaceEdgeIter::new(self.edge_index, edges);
        let first_point = iter.next().expect("the face has no edge").1.origin;
        let mut prev = iter.next().expect("the face has only one edge");
        for current in iter {
            let edge = prev.1;
            triangles.push(first_point);
            triangles.push(edge.destination);
            triangles.push(edge.origin);
            prev = current;
        }
    }

    #[cfg(feature = "safe_check")]
    #[inline]
    pub(crate) fn first_vertex_index(&self, edges: &EdgeMap) -> usize {
        edges[self.edge_index].origin
    }

    #[inline]
    pub(crate) fn distance(&self, point: Point3) -> f32 {
        let self_point = self.center;
        let offset = point - self_point;
        offset.dot(self.normal)
    }

    #[inline]
    pub(crate) fn remove_conflict_point(&mut self, point_index: usize) {
        self.conflict_points.retain(|&mut x| x != point_index);
    }

    #[inline]
    pub(crate) fn get_max_distance_conflict_index(&self, points: &[Point3]) -> Option<&usize> {
        self.conflict_points.iter().max_by(|&&x, &&y| {
            let distance_x = self.distance(points[x]);
            let distance_y = self.distance(points[y]);
            if distance_x > distance_y {
                Ordering::Greater
            } else {
                Ordering::Less
            }
        })
    }
}

pub struct FaceEdgeIterInv<'a> {
    init_edge_index: HalfEdgeKey,
    edges: &'a EdgeMap,
    now_edge_index: HalfEdgeKey,
    end: bool,
}

pub struct FaceEdgeIter<'a> {
    init_edge_index: HalfEdgeKey,
    edges: &'a EdgeMap,
    now_edge_index: HalfEdgeKey,
    end: bool,
}
impl<'a> FaceEdgeIter<'a> {
    #[inline]
    #[must_use]
    pub fn new(init_edge_index: HalfEdgeKey, edges: &'a EdgeMap) -> Self {
        Self {
            init_edge_index,
            edges,
            now_edge_index: init_edge_index,
            end: false,
        }
    }
}

impl<'a> Iterator for FaceEdgeIter<'a> {
    type Item = (HalfEdgeKey, &'a HalfEdge);

    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        if self.end {
            return None;
        }
        let key = self.now_edge_index;
        let edge = &self.edges[key];
        // every edge is in a Linked List Cycle，so the next edge must exist
        self.now_edge_index = edge.next();
        self.end = self.now_edge_index == self.init_edge_index;
        Some((key, edge))
    }
}

impl<'a> FaceEdgeIterInv<'a> {
    #[inline]
    #[must_use]
    pub fn new(init_edge_index: HalfEdgeKey, edges: &'a EdgeMap) -> Self {
        Self {
            init_edge_index,
            edges,
            now_edge_index: init_edge_index,
            end: false,
        }
    }
}
impl<'a> Iterator for FaceEdgeIterInv<'a> {
    type Item = (HalfEdgeKey, &'a HalfEdge);

    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        if self.end {
            return None;
        }
        let key = self.now_edge_index;
        let edge = &self.edges[key];
        // every edge is in a Linked List Cycle，so the prev edge must exist
        self.now_edge_index = edge.prev();
        self.end = self.now_edge_index == self.init_edge_index;
        Some((key, edge))
    }
}