bevy_copperfield 0.2.2

use crate::uvmesh::{
    create_charts, least_squares_conformal_maps, primitive_mapping, ProjectionMethod,
};
use attributes::{
    AttributeKind, AttributeStore, AttributeValues, Attributes, SelectionQueries, TraversalQueries,
};
use glam::{Vec2, Vec3};
use bevy_transform::components::Transform;
use bevy_utils::hashbrown::HashSet;
use bevy_render::{mesh::{Indices, Mesh as BevyMesh, PrimitiveTopology}, render_asset::RenderAssetUsages};
use itertools::Itertools;
use selection::Selection;
use slotmap::{SecondaryMap, SlotMap};
use smallvec::SmallVec;
use traversal::{Traversal, VertexFlow};

pub mod attributes;
pub mod edge_ops;
pub mod face_ops;
pub mod mesh_ops;
mod selection;
pub(crate) mod traversal;
pub mod vertex_ops;

use crate::OPTIMIZE_FOR_NGONS_UNDER_SIZE;

pub type StackVec<T> = SmallVec<[T; OPTIMIZE_FOR_NGONS_UNDER_SIZE]>;

#[derive(Copy, Clone, PartialEq, Eq)]
/// A single position on a mesh. An edge, a vertex, or a face
pub enum MeshPosition {
    Vertex(VertexId),
    HalfEdge(HalfEdgeId),
    Face(FaceId),
}


/// Trait that lets us convert some value to a specific HalfEdgeId
/// Useful to let rays target exact part of the mesh
pub trait Targettable {
    /// Convert self to a [`HalfEdgeId`]. For example if a ray
    /// points to this mesh this method is how you could aim at
    /// specific parts of a mesh
    fn get_mesh_halfedge(self, mesh: &HalfEdgeMesh) -> HalfEdgeId;
    fn get_mesh_position(self, mesh: &HalfEdgeMesh) -> MeshPosition;
}

slotmap::new_key_type! {
    /// Index of a given [`HalfEdge`] in the staging slotmap
    /// [`HalfEdgeMesh`] assumes [`HalfEdgeId::default()`] is equivalent to a NULL pointer
    pub struct HalfEdgeId;

    /// Index of a given [`Vertex`] in the staging slotmap
    pub struct VertexId;

    /// Index of a given [`Face`] in the staging slotmap
    pub struct FaceId;
}

impl HalfEdgeId {
    #[cfg(test)]
    #[allow(dead_code)]
    /// Lets the crate create custom Id. Only used for unit-tests
    pub(crate) fn from_ffi(ffi: u64) -> Self {
        Self(slotmap::KeyData::from_ffi(ffi))
    }
}

impl VertexId {
    #[cfg(test)]
    #[allow(dead_code)]
    /// Lets the crate create custom Id. Only used for unit-tests
    pub(crate) fn from_ffi(ffi: u64) -> Self {
        Self(slotmap::KeyData::from_ffi(ffi))
    }
}

impl FaceId {
    #[cfg(test)]
    #[allow(dead_code)]
    /// Lets the crate create custom Id. Only used for unit-tests
    pub fn from_ffi(ffi: u64) -> Self {
        Self(slotmap::KeyData::from_ffi(ffi))
    }
}

impl Targettable for HalfEdgeId {
    #[inline]
    fn get_mesh_position(self, _: &HalfEdgeMesh) -> MeshPosition {
        self.into()
    }

    fn get_mesh_halfedge(self, _: &HalfEdgeMesh) -> HalfEdgeId {
        self
    }
}

impl Targettable for VertexId {
    #[inline]
    fn get_mesh_position(self, _mesh: &HalfEdgeMesh) -> MeshPosition {
        self.into()
    }

    fn get_mesh_halfedge(self, mesh: &HalfEdgeMesh) -> HalfEdgeId {
        mesh[self].halfedge
    }
}

impl Targettable for FaceId {
    #[inline]
    fn get_mesh_position(self, _mesh: &HalfEdgeMesh) -> MeshPosition {
        self.into()
    }
    fn get_mesh_halfedge(self, mesh: &HalfEdgeMesh) -> HalfEdgeId {
        mesh[self].halfedge
    }
}

impl Targettable for Vec3 {
    fn get_mesh_position(self, mesh: &HalfEdgeMesh) -> MeshPosition {
        if let Some(attr) = mesh.attribute(&AttributeKind::Positions) {
            // TODO: Allow aiming at edges and faces too
            let (vertex, _) =
                attr.as_vertices_vec3()
                    .iter()
                    .fold((VertexId::default(), f32::MAX), |acc, p| {
                        let distance = (*p.1 - self).length();
                        if distance < acc.1 {
                            (p.0, distance)
                        } else {
                            acc
                        }
                    });
            vertex.into()
        } else {
            MeshPosition::HalfEdge(HalfEdgeId::default())
        }
    }

    fn get_mesh_halfedge(self, mesh: &HalfEdgeMesh) -> HalfEdgeId {
        if let Some(attr) = mesh.attribute(&AttributeKind::Positions) {
            let (vertex, _) =
                attr.as_vertices_vec3()
                    .iter()
                    .fold((VertexId::default(), f32::MAX), |acc, p| {
                        let distance = (*p.1 - self).length();
                        if distance < acc.1 {
                            (p.0, distance)
                        } else {
                            acc
                        }
                    });
            mesh[vertex].halfedge
        } else {
            HalfEdgeId::default()
        }
    }
}

impl std::fmt::Debug for MeshPosition {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            Self::Vertex(arg0) => f.write_fmt(format_args!("{:?}", arg0)),
            Self::HalfEdge(arg0) => f.write_fmt(format_args!("{:?}", arg0)),
            Self::Face(arg0) => f.write_fmt(format_args!("{:?}", arg0)),
        }
    }
}

impl MeshPosition {
    pub fn is_valid(&self, mesh: &HalfEdgeMesh) -> bool {
        match *self {
            MeshPosition::Vertex(vertex_id) => mesh.vertices.contains_key(vertex_id),
            MeshPosition::HalfEdge(half_edge_id) => mesh.halfedges.contains_key(half_edge_id),
            MeshPosition::Face(face_id) => mesh.faces.contains_key(face_id),
        }
    }
}

impl Targettable for MeshPosition {
    #[inline]
    fn get_mesh_halfedge(self, mesh: &HalfEdgeMesh) -> HalfEdgeId {
        match self {
            MeshPosition::Vertex(vertex_id) => mesh[vertex_id].halfedge,
            MeshPosition::HalfEdge(half_edge_id) => half_edge_id,
            MeshPosition::Face(face_id) => mesh[face_id].halfedge,
        }
    }
    fn get_mesh_position(self, _mesh: &HalfEdgeMesh) -> MeshPosition {
        self
    }
}

impl From<VertexId> for MeshPosition {
    #[inline]
    fn from(value: VertexId) -> Self {
        Self::Vertex(value)
    }
}

impl From<HalfEdgeId> for MeshPosition {
    #[inline]
    fn from(value: HalfEdgeId) -> Self {
        Self::HalfEdge(value)
    }
}

impl From<FaceId> for MeshPosition {
    #[inline]
    fn from(value: FaceId) -> Self {
        Self::Face(value)
    }
}

#[derive(Default, Clone, Copy)]
/// A common way to represent a polygon mesh is a shared list of vertices and a list of faces storing pointers for its vertices.
/// This representation is both convenient and efficient for many purposes, however in some domains it proves ineffective.
/// Write up about Half-Edge Data structure can be found [here](https://www.flipcode.com/archives/The_Half-Edge_Data_Structure.shtml)
/// And [Here](https://jerryyin.info/geometry-processing-algorithms/half-edge/)
pub struct HalfEdge {
    pub twin: HalfEdgeId,
    pub next: HalfEdgeId,
    pub vertex: VertexId,
    pub face: Option<FaceId>,
}

impl std::fmt::Debug for HalfEdge {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        let mut output = f.debug_struct("");
        if self.twin != HalfEdgeId::default() {
            output.field("twin", &self.twin);
        }
        if self.next != HalfEdgeId::default() {
            output.field("next", &self.next);
        }
        output.field("vertex", &self.vertex);
        if self.face.is_some() {
            output.field("face", &self.face.unwrap());
        }
        output.finish()
    }
}

#[derive(Debug, Clone, Copy, Default)]
/// Vertex stored a pointer to exactly one of the half-edges which uses the vertex as its starting point.
/// At any given vertex there will be more than one half-edge we could choose for this,
/// but we only need one and it doesn't matter which one it is.
pub struct Vertex {
    pub halfedge: HalfEdgeId,
}

#[derive(Debug, Clone, Copy, Default)]
/// The half-edge pointer in the face is similar to the pointer in the vertex structure in that although
/// there are multiple half-edges bordering each face, we only need to store one of them, and it doesn't matter which one.
pub struct Face {
    pub halfedge: HalfEdgeId,
}

/// Editable Mesh based on Half-Edge data structure. The half-edge data structure is called that because instead of
/// storing the edges of the mesh, we store half-edges. As the name implies, a half-edge is a half of an edge and
/// is constructed by splitting an edge down its length. We'll call the two half-edges that make up an edge a pair.
/// Half-edges are directed and the two edges of a pair have opposite directions.
pub struct HalfEdgeMesh {
    vertices: SlotMap<VertexId, Vertex>,
    faces: SlotMap<FaceId, Face>,
    halfedges: SlotMap<HalfEdgeId, HalfEdge>,
    /// Shade smooth or sharp. Default - true (smooth)
    pub is_smooth: bool,
    /// Which UV-Projection method to use to generate UV coordinates.
    /// Default - Cube mapping with Cube sides of 1.0 at the origin.
    pub uv_projection: ProjectionMethod,
    attributes: Attributes,
}

macro_rules! index_mesh_with {
    ($id_type:ty, $output_type:ty, $property:ident) => {
        impl std::ops::Index<$id_type> for HalfEdgeMesh {
            type Output = $output_type;

            fn index(&self, index: $id_type) -> &Self::Output {
                match self.$property.get(index) {
                    Some(value) => value,
                    None => panic!(
                        "Broken {} pointer while reading a mesh.",
                        stringify!($id_type)
                    ),
                }
            }
        }

        impl std::ops::IndexMut<$id_type> for HalfEdgeMesh {
            fn index_mut(&mut self, index: $id_type) -> &mut Self::Output {
                match self.$property.get_mut(index) {
                    Some(value) => value,
                    None => panic!(
                        "Broken {} pointer while writing a mesh.",
                        stringify!($id_type)
                    ),
                }
            }
        }
    };
}

index_mesh_with!(VertexId, Vertex, vertices);
index_mesh_with!(FaceId, Face, faces);
index_mesh_with!(HalfEdgeId, HalfEdge, halfedges);

impl Default for HalfEdgeMesh {
    fn default() -> Self {
        Self {
            vertices: SlotMap::with_key(),
            faces: SlotMap::with_key(),
            halfedges: SlotMap::with_key(),
            attributes: Attributes::new(),
            uv_projection: ProjectionMethod::Cube {
                center: Vec3::ZERO,
                scale: Vec3::ONE,
            },
            is_smooth: true,
        }
    }
}

impl HalfEdgeMesh {
    pub fn new() -> Self {
        Self::default()
    }

    #[inline]
    /// Initiate traversal of the mesh starting at a given edge
    pub fn goto(&self, pos: impl Targettable) -> Traversal<'_> {
        Traversal::new(self, pos.get_mesh_halfedge(self))
    }

    #[inline]
    /// Go to a position and select it, allowing you to select more items to later act on as a group
    pub fn select(&self, pos: impl Targettable + Copy) -> Selection<'_> {
        let position = pos.get_mesh_position(self);
        Selection::new(self, position)
    }

    #[inline]
    pub fn new_vertex(&mut self) -> VertexId {
        self.vertices.insert(Vertex::default())
    }

    #[inline]
    pub fn new_edge(&mut self, edge: HalfEdge, mut twin: HalfEdge) -> (HalfEdgeId, HalfEdgeId) {
        let edge = self.halfedges.insert(edge);
        twin.twin = edge;
        let twin = self.halfedges.insert(twin);
        self[edge].twin = twin;
        (edge, twin)
    }

    /// Connect the mesh such that `edge_previous` will point to newly created edge and newly created `edge.next` will point to `edge_next`
    /// At the same time, create a twin such that whatever `edge_previous.next` was pointing to will end up being `twin.next` and the previous of `edge_next`
    /// will become `twin.previous` pointing to the newly created twin.
    /// `face` argument is used to constrain the flow of edges to a face (or boundary edges if face is None)
    /// ```text
    ///twin_vertex(w) /twin_previous
    ///  __________./    twin_next
    ///  edge_next  \twin /
    ///          edge\   /
    ///                . - edge_vertex(v)
    ///              /   \
    ///edge_previous/     \
    /// ```
    pub fn attach_edge(
        &mut self,
        edge_previous: HalfEdgeId,
        edge_next: HalfEdgeId,
    ) -> (HalfEdgeId, HalfEdgeId) {
        let edge_next = self.goto(edge_next);
        let edge_previous = self.goto(edge_previous);
        let twin_next = edge_previous.next_or_twin(); // twins will be used when both are boundary edges and we're just constructing a face
        let twin_previous = edge_next.previous_or_twin().halfedge();
        let twin_vertex = edge_next.vertex();
        let edge_vertex = twin_next.vertex();
        let edge_face = edge_previous.face();
        let twin_face = twin_next.face();

        let edge_next = edge_next.halfedge();
        let edge_previous = edge_previous.halfedge();
        let twin_next = twin_next.halfedge();
        let (edge, twin) = self.new_edge(
            HalfEdge {
                next: edge_next,
                vertex: edge_vertex,
                face: edge_face,
                ..HalfEdge::default()
            },
            HalfEdge {
                next: twin_next,
                vertex: twin_vertex,
                face: twin_face,
                ..HalfEdge::default()
            },
        );
        if let Some(edge_previous) = self.halfedges.get_mut(edge_previous) {
            edge_previous.next = edge;
        }
        if let Some(twin_previous) = self.halfedges.get_mut(twin_previous) {
            twin_previous.next = twin;
        }
        self[edge_vertex].halfedge = edge;
        self[twin_vertex].halfedge = twin;
        (edge, twin)
    }

    /// Create a new face and attach it to correct twin edges.
    /// This method does not modify twin edges if they already exist
    pub fn new_face(&mut self, face: &[VertexId]) -> FaceId {
        let face_id = self.faces.insert(Face {
            halfedge: HalfEdgeId::default(),
        });
        let mut face_edges: StackVec<HalfEdgeId> = StackVec::new();
        let mut start_flows: StackVec<VertexFlow> = StackVec::new();
        let mut end_flows: StackVec<VertexFlow> = StackVec::new();
        for (&start, &end) in face.iter().circular_tuple_windows() {
            start_flows.clear();
            end_flows.clear();
            if self.halfedges.contains_key(self[start].halfedge) {
                start_flows.extend(self.goto(start).get_flow(None));
            };
            if self.halfedges.contains_key(self[end].halfedge) {
                end_flows.extend(self.goto(end).get_flow(None));
            };
            let mut selected_start_flow: Option<VertexFlow> = None;
            let mut selected_end_flow: Option<VertexFlow> = None;
            let mut is_existing_edge = false;
            // cross-compare possible edge flows and prefer already-connected edges
            // or edges that we previously created for this face
            for start_flow in &start_flows {
                for end_flow in &end_flows {
                    if start_flow.outgoing == end_flow.incoming
                        && self.halfedges.contains_key(start_flow.outgoing)
                    {
                        is_existing_edge = true;
                        face_edges.push(start_flow.outgoing);
                        break;
                    }
                    // if end_flow.outgoing == start_flow.incoming && self.halfedges.contains_key(end_flow.outgoing) {
                    //     // Shouldn't do anything here because this will happen when we are filling holes.
                    // }
                    if let Some(&first_face_edge) = face_edges.first() {
                        if end_flow.outgoing == first_face_edge {
                            selected_end_flow = Some(*end_flow);
                        }
                    }
                }
                if let Some(&last_face_edge) = face_edges.last() {
                    if start_flow.incoming == last_face_edge {
                        selected_start_flow = Some(*start_flow);
                    }
                }
                if is_existing_edge {
                    break;
                }
            }
            if is_existing_edge {
                // face_edges.push already happened above when is_existing_edge was toggled.
                continue;
            } else {
                if selected_start_flow.is_none() && !start_flows.is_empty() {
                    selected_start_flow = Some(start_flows[0]);
                }
                if selected_end_flow.is_none() && !end_flows.is_empty() {
                    selected_end_flow = Some(end_flows[0]);
                }
                let edge = match (selected_start_flow, selected_end_flow) {
                    (Some(start_flow), Some(end_flow)) => {
                        let (edge, _) = self.attach_edge(start_flow.incoming, end_flow.outgoing);
                        edge
                    }
                    (Some(start_flow), None) => {
                        // == * == *
                        let (edge, twin) = self.new_edge(
                            HalfEdge {
                                vertex: start,
                                face: self[start_flow.incoming].face,
                                ..HalfEdge::default()
                            },
                            HalfEdge {
                                next: start_flow.outgoing,
                                vertex: end,
                                face: self[start_flow.outgoing].face,
                                ..HalfEdge::default()
                            },
                        );
                        #[cfg(test)]
                        assert_eq!(self[start_flow.incoming].face, None);
                        self[start_flow.incoming].next = edge;
                        self[end].halfedge = twin;
                        edge
                    }
                    (None, Some(end_flow)) => {
                        // * == * ==
                        let (edge, twin) = self.new_edge(
                            HalfEdge {
                                next: end_flow.outgoing,
                                vertex: start,
                                face: self[end_flow.outgoing].face,
                                ..HalfEdge::default()
                            },
                            HalfEdge {
                                vertex: end,
                                face: self[end_flow.incoming].face,
                                ..HalfEdge::default()
                            },
                        );
                        self[end_flow.incoming].next = twin;
                        self[start].halfedge = edge;
                        edge
                    }
                    (None, None) => {
                        if self.halfedges.contains_key(self[start].halfedge)
                            && self[self[start].halfedge].vertex == start
                            || self.halfedges.contains_key(self[end].halfedge)
                                && self[self[end].halfedge].vertex == end
                        {
                            panic!("No boundary edges found but vertices {start:?} or {end:?} contain non-boundary edges. You're trying to create a non-manifold. Unable to continue.");
                        }
                        let (edge, twin) = self.new_edge(
                            HalfEdge {
                                vertex: start,
                                ..HalfEdge::default()
                            },
                            HalfEdge {
                                vertex: end,
                                ..HalfEdge::default()
                            },
                        );
                        self[start].halfedge = edge;
                        self[end].halfedge = twin;
                        edge
                    }
                };
                face_edges.push(edge);
            }
        }

        self[face_id].halfedge = face_edges[0];
        for edge in face_edges {
            self[edge].face = Some(face_id);
        }
        face_id
    }

    pub fn calculate_uvs(&mut self) {
        match self.uv_projection {
            ProjectionMethod::LSCM => {
                let charts = create_charts(self);
                least_squares_conformal_maps::project(self, charts);
            }
            ProjectionMethod::Cube { center, scale } => {
                primitive_mapping::cube(self, Transform::from_translation(center).with_scale(scale))
            }
            ProjectionMethod::Sphere { center, radius } => {
                primitive_mapping::sphere(self, center, radius)
            }
        }
        let values = self
            .attribute(&AttributeKind::UVs)
            .expect("Vertices don't have UV attribute.")
            .as_edge_vec2();
        let empty_edges = self
            .edge_keys()
            .filter(|&e| !values.contains_key(e))
            .collect::<StackVec<_>>();
        let values = self
            .attribute_mut(&AttributeKind::UVs)
            .expect("Vertices don't have UV attribute.")
            .as_edge_vec2_mut();
        for v in empty_edges {
            values.insert(v, Vec2::ZERO);
        }
    }

    /// How many faces are currently allocated
    pub fn face_count(&self) -> usize {
        self.faces.len()
    }

    /// How many vertices are currently allocated
    pub fn vertex_count(&self) -> usize {
        self.vertices.len()
    }

    /// How many halfedges are currently allocated
    pub fn halfedge_count(&self) -> usize {
        self.halfedges.len()
    }

    pub fn face_keys(&self) -> slotmap::basic::Keys<FaceId, Face> {
        self.faces.keys()
    }

    pub fn vertex_keys(&self) -> slotmap::basic::Keys<VertexId, Vertex> {
        self.vertices.keys()
    }

    pub fn edge_keys(&self) -> slotmap::basic::Keys<HalfEdgeId, HalfEdge> {
        self.halfedges.keys()
    }

    /// Insert attributes into mesh. Faces, Edges, and Vertices can have their own attribute data
    pub fn add_attribute(
        &mut self,
        kind: AttributeKind,
        store: impl Into<AttributeValues>,
    ) -> Option<AttributeValues> {
        self.attributes.insert(kind, store.into())
    }

    /// Get an attribute
    pub fn attribute(&self, kind: &AttributeKind) -> Option<&AttributeValues> {
        self.attributes.get(kind)
    }

    /// Get an attribute
    pub fn attribute_mut(&mut self, kind: &AttributeKind) -> Option<&mut AttributeValues> {
        self.attributes.get_mut(kind)
    }

    /// Get a sum of all face-edges (usefull for checks)
    pub fn count_face_edges(&self) -> usize {
        let mut count: usize = 0;
        for face in self.faces.keys() {
            count += self.goto(face).iter_loop().count();
        }
        count
    }

    /// Count mesh islands (unconnected meshes)
    pub fn count_islands(&self) -> usize {
        let mut unvisited_vertices: HashSet<_> = self.vertices.keys().collect();
        let mut island_count = 0;
        fn remove_visited(set: &mut HashSet<VertexId>, mesh: &HalfEdgeMesh, init: VertexId) {
            if set.remove(&init) {
                for visited in mesh.goto(init).iter_incoming().map(|t| t.vertex()) {
                    remove_visited(set, mesh, visited);
                }
            }
        }
        while let Some(&init_vertex) = unvisited_vertices.iter().next() {
            island_count += 1;
            remove_visited(&mut unvisited_vertices, self, init_vertex);
        }

        island_count
    }

    /// The count of outgoing edges in a vertex
    pub fn vertex_degree(&self, vertex: VertexId) -> usize {
        self.goto(vertex).iter_outgoing().count()
    }

    pub(crate) fn print_mesh(&self) {
        println!("Mesh:");
        for (id, Vertex { halfedge }) in &self.vertices {
            println!("\t{id:?} -> {halfedge:?}");
        }
        for (id, Face { halfedge }) in &self.faces {
            println!("\t{id:?} -> {halfedge:?}");
        }
        for (
            id,
            HalfEdge {
                twin,
                next,
                vertex,
                face,
            },
        ) in &self.halfedges
        {
            println!("\t{id:?} -> twin:{twin:?} next:{next:?} {vertex:?} {face:?}");
        }
    }

    pub fn join(&mut self, other: &HalfEdgeMesh) {
        let mut edge_map: SecondaryMap<HalfEdgeId, HalfEdgeId> = SecondaryMap::new();
        let mut face_map: SecondaryMap<FaceId, FaceId> = SecondaryMap::new();
        let mut vertex_map: SecondaryMap<VertexId, VertexId> = SecondaryMap::new();

        for face_id in other.face_keys() {
            face_map.insert(face_id, self.faces.insert(Face::default()));
        }
        for vertex_id in other.vertex_keys() {
            vertex_map.insert(vertex_id, self.vertices.insert(Vertex::default()));
        }
        for edge_id in other.edge_keys() {
            let mut halfedge = other.halfedges[edge_id];
            halfedge.vertex = vertex_map[halfedge.vertex];
            halfedge.face.iter_mut().for_each(|f| *f = face_map[*f]);
            let new_id = self.halfedges.insert(halfedge);
            self.vertices[halfedge.vertex].halfedge = new_id;
            if let Some(f) = halfedge.face { self.faces[f].halfedge = new_id; }
            edge_map.insert(edge_id, new_id);
        }
        for edge_id in other.edge_keys() {
            let new_id = edge_map[edge_id];
            self[new_id].next = edge_map[self[new_id].next];
            self[new_id].twin = edge_map[self[new_id].twin];
        }
        for (kind, values) in &other.attributes {
            let store = self
                .attributes
                .entry(*kind)
                .or_insert_with(|| match values {
                    AttributeValues::VertexU32(_) => {
                        AttributeValues::VertexU32(SecondaryMap::new())
                    }
                    AttributeValues::VertexVec2(_) => {
                        AttributeValues::VertexVec2(SecondaryMap::new())
                    }
                    AttributeValues::VertexVec3(_) => {
                        AttributeValues::VertexVec3(SecondaryMap::new())
                    }
                    AttributeValues::VertexBool(_) => {
                        AttributeValues::VertexBool(SecondaryMap::new())
                    }
                    AttributeValues::EdgeVec2(_) => AttributeValues::EdgeVec2(SecondaryMap::new()),
                    AttributeValues::EdgeVec3(_) => AttributeValues::EdgeVec3(SecondaryMap::new()),
                    AttributeValues::EdgeBool(_) => AttributeValues::EdgeBool(SecondaryMap::new()),
                });
            match values {
                AttributeValues::VertexU32(secondary_map) => {
                    for (old_key, &value) in secondary_map {
                        store
                            .as_vertices_u32_mut()
                            .insert(vertex_map[old_key], value);
                    }
                }
                AttributeValues::VertexVec2(secondary_map) => {
                    for (old_key, &value) in secondary_map {
                        store
                            .as_vertices_vec2_mut()
                            .insert(vertex_map[old_key], value);
                    }
                }
                AttributeValues::VertexVec3(secondary_map) => {
                    for (old_key, &value) in secondary_map {
                        store
                            .as_vertices_vec3_mut()
                            .insert(vertex_map[old_key], value);
                    }
                }
                AttributeValues::VertexBool(secondary_map) => {
                    for (old_key, &value) in secondary_map {
                        store
                            .as_vertices_bool_mut()
                            .insert(vertex_map[old_key], value);
                    }
                }
                AttributeValues::EdgeVec2(secondary_map) => {
                    for (old_key, &value) in secondary_map {
                        store.as_edge_vec2_mut().insert(edge_map[old_key], value);
                    }
                }
                AttributeValues::EdgeVec3(secondary_map) => {
                    for (old_key, &value) in secondary_map {
                        store.as_edge_vec3_mut().insert(edge_map[old_key], value);
                    }
                }
                AttributeValues::EdgeBool(secondary_map) => {
                    for (old_key, &value) in secondary_map {
                        store.as_edge_bool_mut().insert(edge_map[old_key], value);
                    }
                }
            }
        }
        if self.is_smooth != other.is_smooth {
            todo!("Can't join two meshes with different smoothing settings.")
        }
    }
}

impl TryFrom<BevyMesh> for HalfEdgeMesh {
    type Error = ();
    fn try_from(bevy_mesh: BevyMesh) -> Result<Self, Self::Error> {
        if let (Some(positions), Some(indices)) = (
            bevy_mesh.attribute(BevyMesh::ATTRIBUTE_POSITION),
            bevy_mesh.indices(),
        ) {
            if let Some(positions) = positions.as_float3() {
                let mut mesh = HalfEdgeMesh::new();
                let mut index_to_vertex_map: Vec<Option<VertexId>> =
                    (0..positions.len()).map(|_| None).collect();
                let mut position_attribute: AttributeStore<VertexId, Vec3> = AttributeStore::new();
                for triangle in
                    indices
                        .iter()
                        .batching(|it| match (it.next(), it.next(), it.next()) {
                            (Some(a), Some(b), Some(c)) => Some([a, b, c]),
                            _ => None,
                        })
                {
                    let face = triangle.map(|idx| match index_to_vertex_map[idx] {
                        Some(v) => v,
                        None => {
                            let v = mesh.new_vertex();
                            index_to_vertex_map[idx] = Some(v);
                            v
                        }
                    });
                    mesh.new_face(&face);
                    triangle.iter().zip(face).for_each(|(&idx, vertex)| {
                        _ = position_attribute.insert(vertex, positions[idx].into())
                    });
                }
                mesh.add_attribute(AttributeKind::Positions, position_attribute);
                Ok(mesh)
            } else {
                todo!("Only indexed [f32;3] format supported for now");
            }
        } else {
            todo!("Only indexed [f32;3] format supported for now");
        }
    }
}

impl From<&HalfEdgeMesh> for BevyMesh {
    fn from(mesh: &HalfEdgeMesh) -> Self {
        let mut positions = Vec::new();
        let mut normals = Vec::new();
        let mut uvs = Vec::new();
        let mut indices = Vec::new();
        // values in vertex_index map are vectors of (uv coordinates, index) to allow re-using vertices with
        // the same uv-coordinates
        let mut vertex_index_map: SecondaryMap<VertexId, Vec<(Vec2, u32)>> = SecondaryMap::new();
        // TODO: Check if traversing adjacent faces first is better.
        // Down side - checking adjacency now is slower on CPU
        // But having indices with better locality might be better on GPU
        for face in mesh.faces.keys() {
            let f = mesh.goto(face);
            for (idx, (vertex, next)) in f
                .triangulate()
                .into_iter()
                .circular_tuple_windows()
                .enumerate()
            {
                let t = mesh.goto(vertex);
                let edge_to = if idx % 3 == 2 {
                    None
                } else {
                    t.find_halfedge_to(next).filter(|t| t.face() == Some(face))
                };
                let uv = edge_to
                    .unwrap_or_else(|| t.iter_outgoing().find(|e| e.face() == Some(face)).unwrap())
                    .uv();
                let mut is_new_output = true;
                if let Some(known_indices) = vertex_index_map.get(vertex) {
                    let index = known_indices
                        .iter()
                        .find(|(e_uv, _)| *e_uv == uv)
                        .map(|(_, idx)| *idx);
                    if t.is_smooth_normals() && index.is_some() {
                        is_new_output = false;
                        indices.push(index.unwrap());
                    }
                }
                if is_new_output {
                    let index = positions.len() as u32;
                    indices.push(index);
                    positions.push(t.position().to_array());
                    if t.is_smooth_normals() {
                        normals.push(
                            t.select_vertex()
                                .select_faces()
                                .calculate_normal()
                                .unwrap()
                                .to_array(),
                        );
                    } else {
                        let n = f.calculate_normal().unwrap();
                        normals.push(n.to_array());
                    }
                    uvs.push(uv);
                    let known_indices = vertex_index_map.entry(vertex).unwrap().or_default();
                    known_indices.push((uv, index));
                }
            }
        }

        let indices = Indices::U32(indices);
        BevyMesh::new(
            PrimitiveTopology::TriangleList,
            RenderAssetUsages::default(),
        )
        .with_inserted_attribute(BevyMesh::ATTRIBUTE_POSITION, positions)
        .with_inserted_attribute(BevyMesh::ATTRIBUTE_NORMAL, normals)
        .with_inserted_attribute(BevyMesh::ATTRIBUTE_UV_0, uvs)
        .with_inserted_indices(indices)
    }
}

#[cfg(test)]
mod tests {
    use bevy_math::prelude::Cuboid;
    use bevy_render::mesh::{MeshBuilder, Meshable};
    use glam::Vec3;
    use slotmap::{KeyData, SecondaryMap};
    use smallvec::SmallVec;

    use crate::mesh::{FaceId, HalfEdgeMesh, VertexId};

    use super::{attributes::AttributeKind, HalfEdgeId};

    #[test]
    fn test_new_face() {
        let mut mesh = HalfEdgeMesh::new();
        let face = [mesh.new_vertex(), mesh.new_vertex(), mesh.new_vertex()];
        let _face_id = mesh.new_face(&face);
        assert_eq!(mesh.vertex_count(), 3);
        assert_eq!(mesh.count_islands(), 1);
        assert_eq!(mesh.count_face_edges(), 3);
        assert_eq!(mesh.halfedges.len(), 6);
        assert_eq!(
            HalfEdgeId(KeyData::from_ffi(5)),
            mesh.goto(HalfEdgeId(KeyData::from_ffi(1))).previous().halfedge()
        );
        assert_eq!(
            HalfEdgeId(KeyData::from_ffi(4)),
            mesh.goto(HalfEdgeId(KeyData::from_ffi(2))).previous().halfedge()
        );
    }

    #[test]
    fn test_two_disjoint_faces() {
        let mut mesh = HalfEdgeMesh::new();
        let face = [mesh.new_vertex(), mesh.new_vertex(), mesh.new_vertex()];
        let _face_id = mesh.new_face(&face);
        let face = [mesh.new_vertex(), mesh.new_vertex(), mesh.new_vertex()];
        let _face_id = mesh.new_face(&face);

        assert_eq!(mesh.vertex_count(), 6);
        assert_eq!(mesh.count_islands(), 2);
        assert_eq!(mesh.count_face_edges(), 6);
        assert_eq!(mesh.halfedges.len(), 12);
    }

    #[test]
    fn test_two_attached_faces() {
        let mut mesh = HalfEdgeMesh::new();
        let face = [mesh.new_vertex(), mesh.new_vertex(), mesh.new_vertex()];
        let _face_id = mesh.new_face(&face);
        let face = [face[1], face[0], mesh.new_vertex()];
        let _face_id = mesh.new_face(&face);
        assert_eq!(mesh.vertex_count(), 4);
        assert_eq!(mesh.count_islands(), 1);
        assert_eq!(mesh.count_face_edges(), 6);
        assert_eq!(mesh.halfedges.len(), 6 + 4);
    }

    #[test]
    fn from_bevy_mesh() {
        let bevy_mesh = Cuboid::new(1.0, 1.0, 1.0).mesh().build();
        let mesh: HalfEdgeMesh = bevy_mesh.try_into().unwrap();
        assert_eq!(mesh.faces.len(), 12);
        assert_eq!(mesh.vertices.len(), 24);
        assert_eq!(mesh.count_islands(), 6);
        assert_eq!(mesh.count_face_edges(), 36);
        assert_eq!(mesh.halfedges.len(), 36 + 4 * 6);
    }

    /// Returns a mesh in the form
    /// ```text
    /// indices    VertexId    FaceId
    /// 0--3--5    1--4--6     +--+--+
    /// |  |  |    |  |  |     |1 |2 |
    /// 1--2--4    2--3--5     +--+--+
    /// |  |  |    |  |  |     |3 |4 |
    /// 6--7--8    7--8--9     +--+--+
    /// ```
    pub fn sample_mesh() -> HalfEdgeMesh {
        let mut mesh = HalfEdgeMesh::new();
        let v: SmallVec<[_; 9]> = (0..9).map(|_| mesh.new_vertex()).collect();
        mesh.new_face(&[v[0], v[1], v[2], v[3]]);
        mesh.new_face(&[v[3], v[2], v[4], v[5]]);
        mesh.new_face(&[v[1], v[6], v[7], v[2]]);
        mesh.new_face(&[v[2], v[7], v[8], v[4]]);
        let positions = SecondaryMap::from_iter([
            (v[0], -Vec3::X - Vec3::Z),
            (v[3], -Vec3::Z + 0.5 * Vec3::Y),
            (v[5], Vec3::X - Vec3::Z),
            (v[1], -Vec3::X + 0.5 * Vec3::Y),
            (v[2], Vec3::Y),
            (v[4], Vec3::X + 0.5 * Vec3::Y),
            (v[6], -Vec3::X + Vec3::Z),
            (v[7], Vec3::Z + 0.5 * Vec3::Y),
            (v[8], Vec3::X + Vec3::Z),
        ]);
        mesh.add_attribute(AttributeKind::Positions, positions);
        mesh
    }

    #[test]
    fn test_sample_mesh() {
        let mesh = sample_mesh();
        assert_eq!(mesh.count_face_edges(), 16);
        assert_eq!(mesh.face_count(), 4);
        assert_eq!(mesh.vertex_count(), 9);
        assert_eq!(mesh.count_islands(), 1);
        for i in 1..(mesh.face_count() + 1) {
            assert_eq!(
                mesh[mesh[FaceId(KeyData::from_ffi(i as u64))].halfedge].face,
                Some(FaceId(KeyData::from_ffi(i as u64)))
            );
        }
        for i in 1..(mesh.vertex_count() + 1) {
            assert_eq!(
                mesh.vertex_degree(VertexId(KeyData::from_ffi(i as u64))),
                mesh.goto(VertexId(KeyData::from_ffi(i as u64)))
                    .adjacent_faces()
                    .count()
                    + if i == 3 { 0 } else { 1 }
            );
        }
    }
}