meshlite/

mesh.rs

use cgmath::Point3;
use cgmath::Vector3;
use cgmath::prelude::*;
use cgmath::Matrix4;
use std::option::Option;
use std::io;
use std::vec::Vec;
use std::collections::HashMap;
use std::collections::HashSet;
use fnv::FnvHashSet;
use fnv::FnvHashMap;
use iterator::FaceHalfedgeIterator;
use iterator::FaceIterator;
use util::*;
use smallvec::SmallVec;
use std::ops::Add;
use std::ops::AddAssign;
use std::f32;

pub type Id = usize;

// Optimized for quad meshes, since that is very common in high-poly models
// during editing. By subdividing some lower resolution model, pure quad models
// are produced. It could be worth tweaking this constant for other use-cases
// though, triangulation will create more halfedges for many vertices and would
// benefit from a higher number, but that would consume more memory for all
// meshes which would not be ideal. It could be worth having completely separate
// implementations for quad, tri and polygon meshes at later time? Or maybe use
// generics and/or macros to specialize some parts of the implementation?
const VERTEX_HALFEDGE_INLINE_COUNT: usize = 4;

#[derive(Debug)]
pub struct Vertex {
    pub id: Id,
    pub position: Point3<f32>,

    /// This is at the time of writing used as a set but is implemented using a
    /// SmallVec. Finding or implementing something like a "SmallSet" could
    /// provide a better API.
    pub halfedges: SmallVec<[Id; VERTEX_HALFEDGE_INLINE_COUNT]>,

    pub prev: Id,
    pub next: Id,
    pub alive: bool,
    pub source: i32,
}

#[derive(Debug)]
pub struct Face {
    pub id: Id,
    pub halfedge: Id,
    pub prev: Id,
    pub next: Id,
    pub alive: bool,
}

#[derive(Debug)]
pub struct Halfedge {
    pub id: Id,
    pub vertex: Id,
    pub face: Id,
    pub prev: Id,
    pub next: Id,
    pub opposite: Id,
    pub alive: bool,
}

#[derive(Hash, Eq, PartialEq, Debug, Clone)]
pub struct Point3Key {
    x: u32,
    y: u32,
    z: u32,
}

impl Point3Key {
    pub fn new(point: Point3<f32>) -> Self {
        Point3Key {
            x: (point.x * 1000.0).round() as u32,
            y: (point.y * 1000.0).round() as u32,
            z: (point.z * 1000.0).round() as u32,
        }
    }
}

#[derive(Hash, Eq, PartialEq, Debug, Clone)]
pub struct EdgeEndpoints {
    pub low: Id,
    pub high: Id,
}

impl EdgeEndpoints {
    pub fn new(first: Id, second: Id) -> Self {
        if first < second {
            EdgeEndpoints {
                low: first,
                high: second
            }
        } else {
            EdgeEndpoints {
                low: second,
                high: first
            }
        }
    }
}

pub type FacePair = EdgeEndpoints;

#[derive(Debug)]
pub struct Mesh {
    pub vertices: Vec<Vertex>,
    pub vertex_count: usize,
    pub faces: Vec<Face>,
    pub face_count: usize,
    pub halfedges: Vec<Halfedge>,
    pub halfedge_count: usize,
    pub edges: FnvHashMap<EdgeEndpoints, Id>
}

impl Mesh {
    pub fn new() -> Self {
        Mesh {
            vertices: Vec::new(),
            vertex_count: 0,
            faces: Vec::new(),
            face_count: 0,
            halfedges: Vec::new(),
            halfedge_count: 0,
            edges: FnvHashMap::default()
        }
    }

    pub fn vertex(&self, id: Id) -> Option<&Vertex> {
        if 0 == id {
            return None;
        }
        {
            let vertex = &self.vertices[id - 1];
            if !vertex.alive {
                return None;
            }
        }
        Some(&self.vertices[id - 1])
    }

    pub fn vertex_mut(&mut self, id: Id) -> Option<&mut Vertex> {
        if 0 == id {
            return None;
        }
        {
            let vertex = &self.vertices[id - 1];
            if !vertex.alive {
                return None;
            }
        }
        Some(&mut self.vertices[id - 1])
    }

    pub fn peek_same_halfedge(&self, any_paired_id: Id) -> Id {
        let halfedge = self.halfedge(any_paired_id).unwrap();
        if halfedge.opposite > 0 && halfedge.opposite < any_paired_id {
            return halfedge.opposite;
        }
        any_paired_id
    }

    pub fn edge_center(&self, id: Id) -> Point3<f32> {
        let halfedge = self.halfedge(id).unwrap();
        let next = self.halfedge(halfedge.next).unwrap();
        Point3::midpoint(self.vertex(halfedge.vertex).unwrap().position,
            self.vertex(next.vertex).unwrap().position)
    }

    pub fn face_center(&self, id: Id) -> Point3<f32> {
        let face = self.face(id).unwrap();
        let mut points = SmallVec::<[Point3<f32>; 4]>::new();
        for halfedge_id in FaceHalfedgeIterator::new(self, face.halfedge) {
            let halfedge = self.halfedge(halfedge_id).unwrap();
            let vertex = self.vertex(halfedge.vertex).unwrap();
            points.push(vertex.position);
        }
        Point3::centroid(&points)
    }

    pub fn face_norm(&self, id: Id) -> Vector3<f32> {
        let face = self.face(id).unwrap();
        let mut points = Vec::new();
        for halfedge_id in FaceHalfedgeIterator::new(self, face.halfedge) {
            let halfedge = self.halfedge(halfedge_id).unwrap();
            let vertex = self.vertex(halfedge.vertex).unwrap();
            points.push(vertex.position);
        }
        if points.len() < 3 {
            return Vector3::zero();
        } else if points.len() == 3 {
            return norm(points[0], points[1], points[2]);
        }
        let mut total = Vector3::zero();
        for i in 0..points.len() {
            let n = norm(points[i], points[(i + 1) % points.len()], points[(i + 2) % points.len()]);
            total += n;
        }
        total.normalize()
    }

    pub fn face(&self, id: Id) -> Option<&Face> {
        if 0 == id {
            return None;
        }
        {
            let face = &self.faces[id - 1];
            if !face.alive {
                return None;
            }
        }
        Some(&self.faces[id - 1])
    }

    pub fn face_adj_id(&self, id: Id) -> Option<Id> {
        self.face(id)
            .and_then(|f: &Face| self.halfedge(f.halfedge))
            .and_then(|h: &Halfedge| self.halfedge(h.opposite))
            .and_then(|o: &Halfedge| if 0 != o.face { Some(o.face) } else { None })
    }

    pub fn face_adj(&self, id: Id) -> Option<&Face> {
        self.face_adj_id(id).and_then(|id: Id| self.face(id))
    }

    pub fn halfedge_next_id(&self, id: Id) -> Option<Id> {
        self.halfedge(id)
            .and_then(|h: &Halfedge| if 0 != h.next { Some(h.next) } else { None })
    }

    pub fn halfedge_prev_id(&self, id: Id) -> Option<Id> {
        self.halfedge(id)
            .and_then(|h: &Halfedge| if 0 != h.prev { Some(h.prev) } else { None })
    }

    pub fn halfedge_opposite_id(&self, id: Id) -> Option<Id> {
        self.halfedge(id)
            .and_then(|h: &Halfedge| if 0 != h.opposite { Some(h.opposite) } else { None })
    }

    pub fn face_first_halfedge_id(&self, id: Id) -> Option<Id> {
        self.face(id)
            .and_then(|f: &Face| if 0 != f.halfedge { Some(f.halfedge) } else { None })
    }

    pub fn halfedge_start_vertex_id(&self, id: Id) -> Option<Id> {
        self.halfedge(id)
            .and_then(|h: &Halfedge| if 0 != h.vertex { Some(h.vertex) } else { None })
    }

    pub fn halfedge_face_id(&self, id: Id) -> Option<Id> {
        self.halfedge(id)
            .and_then(|h: &Halfedge| if 0 != h.face { Some(h.face) } else { None })
    }

    pub fn halfedge_opposite_face_id(&self, id: Id) -> Option<Id> {
        let opposite_id = self.halfedge_opposite_id(id);
        if opposite_id.is_none() {
            return None;
        }
        self.halfedge_face_id(opposite_id.unwrap())
    }

    pub fn halfedge_direct(&self, id: Id) -> Vector3<f32> {
        let begin_pos = self.halfedge_start_vertex(id).unwrap().position;
        let end_pos = self.halfedge_start_vertex(self.halfedge_next_id(id).unwrap()).unwrap().position;
        end_pos - begin_pos
    }

    pub fn set_halfedge_start_vertex_id(&mut self, halfedge_id: Id, vertex_id: Id) {
        self.halfedge_mut(halfedge_id).unwrap().vertex = vertex_id;
    }

    pub fn halfedge_start_vertex_mut(&mut self, id: Id) -> Option<&mut Vertex> {
        let vertex_id = self.halfedge_start_vertex_id(id)?;
        self.vertex_mut(vertex_id)
    }

    pub fn halfedge_start_vertex(&self, id: Id) -> Option<&Vertex> {
        let vertex_id = self.halfedge_start_vertex_id(id)?;
        self.vertex(vertex_id)
    }

    pub fn set_halfedge_opposite_id(&mut self, halfedge_id: Id, opposite_id: Id) {
        let halfedge = self.halfedge_mut(halfedge_id);
        if halfedge.is_none() {
            return;
        }
        halfedge.unwrap().opposite = opposite_id;
    }

    fn remove_halfedges_from_edges(&mut self, halfedges: &Vec<Id>) {
        for &halfedge_id in halfedges {
            let opposite = self.halfedge_opposite_id(halfedge_id);
            let next_halfedge_id = self.halfedge_next_id(halfedge_id).unwrap();
            let endpoints = EdgeEndpoints::new(self.halfedge_start_vertex_id(halfedge_id).unwrap(), 
                self.halfedge_start_vertex_id(next_halfedge_id).unwrap());
            if let Some(&id) = self.edges.get(&endpoints) {
                if id == halfedge_id {
                    if !opposite.is_none() {
                        *self.edges.get_mut(&endpoints).unwrap() = opposite.unwrap();
                    } else {
                        self.edges.remove(&endpoints);
                    }
                }
            }
        }
    }

    pub fn halfedge_start_vertex_alt_halfedge_id(&self, halfedge_id: Id) -> Option<Id> {
        let opposite = self.halfedge_opposite_id(halfedge_id);
        if !opposite.is_none() {
            let next_id = self.halfedge_next_id(opposite.unwrap());
            if next_id.is_some() {
                return next_id;
            }
        }
        let prev = self.halfedge_prev_id(halfedge_id);
        if !prev.is_none() {
            return self.halfedge_opposite_id(prev.unwrap());
        }
        None
    }

    pub fn remove_face(&mut self, id: Id) {
        let halfedge_collection = FaceHalfedgeIterator::new(self, self.face_first_halfedge_id(id).unwrap()).into_vec();
        self.remove_halfedges_from_edges(&halfedge_collection);
        for &halfedge_id in halfedge_collection.iter() {
            let vertex_count_need_reduce = {
                let vertex = self.halfedge_start_vertex_mut(halfedge_id).unwrap();
                for i in 0..vertex.halfedges.len() {
                    if halfedge_id == vertex.halfedges[i] {
                        vertex.halfedges.remove(i);
                        break;
                    }
                }
                if vertex.halfedges.is_empty() {
                    vertex.alive = false;
                    true
                } else {
                    false
                }
            };
            if vertex_count_need_reduce {
                self.vertex_count -= 1;
            }
        }
        for &halfedge_id in halfedge_collection.iter() {
            let opposite = self.halfedge_opposite_id(halfedge_id);
            if !opposite.is_none() {
                self.set_halfedge_opposite_id(opposite.unwrap(), 0);
            }
            self.halfedge_mut(halfedge_id).unwrap().alive = false;
            self.halfedge_count -= 1;
        }
        self.face_mut(id).unwrap().alive = false;
        self.face_count -= 1;
    }

    pub fn face_mut(&mut self, id: Id) -> Option<&mut Face> {
        if 0 == id {
            return None;
        }
        {
            let face = &self.faces[id - 1];
            if !face.alive {
                return None;
            }
        }
        Some(&mut self.faces[id - 1])
    }

    pub fn halfedge(&self, id: Id) -> Option<&Halfedge> {
        if 0 == id {
            return None;
        }
        {
            let halfedge = &self.halfedges[id - 1];
            if !halfedge.alive {
                return None;
            }
        }
        Some(&self.halfedges[id - 1])
    }

    pub fn halfedge_mut(&mut self, id: Id) -> Option<&mut Halfedge> {
        if 0 == id {
            return None;
        }
        {
            let halfedge = &self.halfedges[id - 1];
            if !halfedge.alive {
                return None;
            }
        }
        Some(&mut self.halfedges[id - 1])
    }

    pub fn add_vertex(&mut self, position: Point3<f32>) -> usize {
        let new_id = self.vertices.len() + 1;
        self.vertices.push(Vertex {
            id: new_id,
            halfedges: SmallVec::<[Id; VERTEX_HALFEDGE_INLINE_COUNT]>::new(),
            prev: 0,
            next: 0,
            position : position,
            alive: true,
            source: -1,
        });
        self.vertex_count += 1;
        new_id
    }

    pub fn add_halfedge(&mut self) -> Id {
        let new_id = self.halfedges.len() + 1;
        self.halfedges.push(Halfedge {
            id: new_id,
            vertex: 0,
            face: 0,
            prev: 0,
            next: 0,
            opposite: 0,
            alive: true,
        });
        self.halfedge_count += 1;
        new_id
    }

    pub fn pair_halfedges(&mut self, first: Id, second: Id) {
        self.halfedge_mut(first).unwrap().opposite = second;
        self.halfedge_mut(second).unwrap().opposite = first;
    }

    pub fn unpair_halfedges(&mut self, first: Id, second: Id) {
        self.halfedge_mut(first).unwrap().opposite = 0;
        self.halfedge_mut(second).unwrap().opposite = 0;
    }

    pub fn link_halfedges(&mut self, first: Id, second: Id) {
        self.halfedge_mut(first).unwrap().next = second;
        self.halfedge_mut(second).unwrap().prev = first;
        let endpoints = EdgeEndpoints::new(self.halfedge(first).unwrap().vertex,
            self.halfedge(second).unwrap().vertex);
        match self.edges.get(&endpoints) {
            Some(&halfedge) => self.pair_halfedges(first, halfedge),
            _ => {
                self.edges.insert(endpoints, first);
            }
        };
    }

    pub fn add_face(&mut self) -> Id {
        let new_id = self.faces.len() + 1;
        self.faces.push(Face {
            id: new_id,
            halfedge: 0,
            prev: 0,
            next: 0,
            alive: true,
        });
        self.face_count += 1;
        new_id
    }

    pub fn add_linked_vertices(&mut self, linked_vertices: &mut HashMap<Id, Id>) -> Id {
        if linked_vertices.len() == 0 {
            return 0;
        }
        let (&first_id, _) = linked_vertices.iter().next().unwrap();
        let mut vert = first_id;
        let mut visited_sets = FnvHashSet::default();
        let mut added_vertices = Vec::new();
        added_vertices.push(first_id);
        visited_sets.insert(first_id);
        //println!("first_id {:?}", first_id);
        while linked_vertices.contains_key(&vert) && linked_vertices[&vert] != first_id {
            vert = linked_vertices[&vert];
            //println!("vert {:?}", vert);
            if visited_sets.contains(&vert) {
                //println!("visited_sets.contains {:?}", vert);
                return 0;
            }
            visited_sets.insert(vert);
            added_vertices.push(vert);
        }
        for vert_id in added_vertices.iter() {
            linked_vertices.remove(vert_id);
        }
        self.add_vertices(added_vertices)
    }

    pub fn add_vertices(&mut self, added_vertices : Vec<Id>) -> Id {
        assert!(added_vertices.len() < 1000);
        if added_vertices.is_empty() {
            return 0;
        }
        let mut added_halfedges : Vec<(Id, Id)> = Vec::new();
        for i in 0..added_vertices.len() {
            if self.vertex(added_vertices[i]).is_none() {
                return 0;
            }
        }
        for i in 0..added_vertices.len() {
            added_halfedges.push((self.add_halfedge(), added_vertices[i]));
        }
        self.add_halfedges_and_vertices(&added_halfedges)
    }

    pub fn add_positions(&mut self, added_positions : Vec<Point3<f32>>) -> Id {
        if added_positions.is_empty() {
            return 0;
        }
        let mut added_vertices : Vec<Id> = Vec::new();
        for i in 0..added_positions.len() {
            added_vertices.push(self.add_vertex(added_positions[i]));
        }
        self.add_vertices(added_vertices)
    }

    pub fn add_halfedges_and_vertices(&mut self, added_halfedges: &[(Id, Id)]) -> Id {
        assert!(added_halfedges.len() < 1000);
        if added_halfedges.is_empty() {
            return 0;
        }
        let added_face_id = self.add_face();
        for &(added_halfedge_id, added_vertex_id) in added_halfedges.iter() {
            {
                let vert = self.vertex_mut(added_vertex_id).unwrap();
                let halfedges = &mut vert.halfedges;
                if !halfedges.contains(&added_halfedge_id) {
                    halfedges.push(added_halfedge_id);
                }
            }
            self.halfedge_mut(added_halfedge_id).unwrap().face = added_face_id;
            self.halfedge_mut(added_halfedge_id).unwrap().vertex = added_vertex_id;
        }
        self.face_mut(added_face_id).unwrap().halfedge = added_halfedges[0].0;
        for i in 0..added_halfedges.len() {
            let first = added_halfedges[i].0;
            let second = added_halfedges[(i + 1) % added_halfedges.len()].0;
            self.link_halfedges(first, second);
        }
        added_face_id
    }

    pub fn extrude_halfedges(&mut self, halfedges: &Vec<Id>, normal: Vector3<f32>, amount: f32) {
        let mut downside_halfedges: Vec<Id> = Vec::new();
        let mut downside_vertices: Vec<Id> = Vec::new();
        let direct = normal * amount;
        let mut need_fill_downside = false;
        for &halfedge_id in halfedges {
            let opposite = self.halfedge_opposite_id(halfedge_id);
            if opposite.is_none() {
                let old_position = {
                    let mut vertex = self.halfedge_start_vertex_mut(halfedge_id).unwrap();
                    let position = vertex.position;
                    vertex.position += direct;
                    position
                };
                downside_vertices.push(self.add_vertex(old_position));
                downside_halfedges.push(self.add_halfedge());
                need_fill_downside = true;
            } else {
                let old_vertex_id = self.halfedge_start_vertex_id(halfedge_id).unwrap();
                let copy_position = self.halfedge_start_vertex(halfedge_id).unwrap().position;
                let copy_vertex = self.add_vertex(copy_position);
                {
                    let vertex_count_need_reduce = {
                        let vertex = self.halfedge_start_vertex_mut(old_vertex_id).unwrap();
                        for i in 0..vertex.halfedges.len() {
                            if vertex.halfedges[i] == halfedge_id {
                                vertex.halfedges.remove(i);
                                break;
                            }
                        }
                        if vertex.halfedges.is_empty() {
                            vertex.alive = false;
                            true
                        } else {
                            false
                        }
                    };
                    if vertex_count_need_reduce {
                        self.vertex_count -= 1;
                    }
                }
                self.set_halfedge_start_vertex_id(halfedge_id, copy_vertex);
                self.unpair_halfedges(halfedge_id, opposite.unwrap());
                downside_vertices.push(old_vertex_id);
                downside_halfedges.push(opposite.unwrap());
            }
        }
        for i in 0..halfedges.len() {
            let halfedge_id = halfedges[i];
            let i_next = (i + 1) % halfedges.len();
            let next_halfedge_id = halfedges[i_next];
            let mut added_halfedges : Vec<(Id, Id)> = Vec::new();
            let left_bottom = downside_vertices[i];
            let right_bottom = downside_vertices[i_next];
            let right_top = self.halfedge_start_vertex_id(next_halfedge_id).unwrap();
            let left_top = self.halfedge_start_vertex_id(halfedge_id).unwrap();
            added_halfedges.push((self.add_halfedge(), left_bottom));
            added_halfedges.push((self.add_halfedge(), right_bottom));
            added_halfedges.push((self.add_halfedge(), right_top));
            added_halfedges.push((self.add_halfedge(), left_top));
            self.add_halfedges_and_vertices(&added_halfedges);
        }
        if need_fill_downside {
            let mut added_halfedges : Vec<(Id, Id)> = Vec::new();
            for i in 0..halfedges.len() {
                let j = (halfedges.len() - i) % halfedges.len();
                added_halfedges.push((downside_halfedges[j], downside_vertices[j]));
            }
            self.add_halfedges_and_vertices(&added_halfedges);
        }
    }

    pub fn extrude_face(&mut self, face_id: Id, normal: Vector3<f32>, amount: f32) -> &mut Self {
        let mut new_halfedges : Vec<Id> = Vec::new();
        for halfedge_id in FaceHalfedgeIterator::new(self, face_id) {
            new_halfedges.push(halfedge_id);
        }
        self.extrude_halfedges(&new_halfedges, normal, amount);
        self
    }

    pub fn add_plane(&mut self, width: f32, depth: f32) -> Id {
        let x = width / 2.0;
        let y = depth / 2.0;
        let points = vec![Point3 {x: -x, y: -y, z: 0.0},
            Point3 {x: x, y: -y, z: 0.0},
            Point3 {x: x, y: y, z: 0.0},
            Point3 {x: -x, y: y, z: 0.0}];
        let mut added_halfedges : Vec<(Id, Id)> = Vec::new();
        for i in 0..points.len() {
            added_halfedges.push((self.add_halfedge(), self.add_vertex(points[i])));
        }
        self.add_halfedges_and_vertices(&added_halfedges)
    }

    pub fn transform(&mut self, mat: &Matrix4<f32>) -> &mut Self {
        for vertex in self.vertices.iter_mut() {
            vertex.position = mat.transform_point(vertex.position);
        }
        self
    }

    pub fn translate(&mut self, x: f32, y: f32, z: f32) -> &mut Self {
        let mat = Matrix4::from_translation(Vector3::new(x, y, z));
        self.transform(&mat)
    }

    pub fn scale(&mut self, value: f32) -> &mut Self {
        let mat = Matrix4::from_scale(value);
        self.transform(&mat)
    }

    pub fn weld(&self) -> Self {
        let mut new_mesh = Mesh::new();
        let mut vertices_set : HashMap<Point3Key, Id> = HashMap::new();
        for face_id in FaceIterator::new(&self) {
            let face = self.face(face_id).unwrap();
            let mut key_set : HashSet<Point3Key> = HashSet::new();
            let mut positions : Vec<(Point3<f32>, i32)> = Vec::new();
            for halfedge_id in FaceHalfedgeIterator::new(&self, face.halfedge) {
                let vertex = self.halfedge_start_vertex(halfedge_id).unwrap();
                let key = Point3Key::new(vertex.position);
                if key_set.contains(&key) {
                    continue;
                }
                key_set.insert(key);
                positions.push((vertex.position, vertex.source));
            }
            if positions.len() < 3 {
                continue;
            }
            let mut added_vertices : Vec<Id> = Vec::new();
            for &(pos, source) in positions.iter() {
                let key = Point3Key::new(pos);
                let new_vert_id = *vertices_set.entry(key).or_insert_with(|| {
                    let new_added_vert_id = new_mesh.add_vertex(pos);
                    new_mesh.vertex_mut(new_added_vert_id).unwrap().source = source;
                    new_added_vert_id
                });
                added_vertices.push(new_vert_id);
            }
            new_mesh.add_vertices(added_vertices);
        }
        new_mesh
    }

    pub fn add_mesh(&mut self, other: &Mesh) {
        let mut vertices_set : HashMap<Id, Id> = HashMap::new();
        for face_id in FaceIterator::new(&other) {
            let face = other.face(face_id).unwrap();
            let mut added_halfedges : Vec<(Id, Id)> = Vec::new();
            for halfedge_id in FaceHalfedgeIterator::new(&other, face.halfedge) {
                let vertex = other.halfedge_start_vertex(halfedge_id).unwrap();
                let key = vertex.id;
                if let Some(&new_vertex_id) = vertices_set.get(&key) {
                    added_halfedges.push((self.add_halfedge(), new_vertex_id));
                } else {
                    let new_vertex_id = self.add_vertex(vertex.position);
                    self.vertex_mut(new_vertex_id).unwrap().source = vertex.source;
                    vertices_set.insert(key, new_vertex_id);
                    added_halfedges.push((self.add_halfedge(), new_vertex_id));
                }
            }
            self.add_halfedges_and_vertices(&added_halfedges);
        }
    }

    pub fn flip_mesh(&self) -> Mesh {
        let mut new_mesh = Mesh::new();
        let mut new_vert_map = HashMap::new();
        for face_id in FaceIterator::new(self) {
            let mut verts = Vec::new();
            for halfedge_id in FaceHalfedgeIterator::new(self, self.face_first_halfedge_id(face_id).unwrap()) {
                let old_vert = self.halfedge_start_vertex(halfedge_id).unwrap();
                let new_vert_id = new_vert_map.entry(old_vert.id).or_insert_with(|| {
                    let new_added_vert_id = new_mesh.add_vertex(old_vert.position);
                    new_mesh.vertex_mut(new_added_vert_id).unwrap().source = old_vert.source;
                    new_added_vert_id
                });
                verts.push(*new_vert_id);
            }
            let mut added_halfedges : Vec<(Id, Id)> = Vec::new();
            for new_vert_id in verts.iter().rev() {
                added_halfedges.push((new_mesh.add_halfedge(), *new_vert_id));
            }
            new_mesh.add_halfedges_and_vertices(&added_halfedges);
        }
        new_mesh
    }

    pub fn split_mesh_by_other(&self, other: &Mesh) -> (Mesh, Mesh) {
        let mut inner_mesh = Mesh::new();
        let mut outter_mesh = Mesh::new();
        inner_mesh.add_mesh(self);
        for face_id in FaceIterator::new(other) {
            let norm = other.face_norm(face_id);
            let point = other.halfedge_start_vertex(other.face_first_halfedge_id(face_id).unwrap()).unwrap().position;
            let (sub_front, sub_back) = inner_mesh.split_mesh_by_plane(point, norm, false);
            inner_mesh = sub_back;
            outter_mesh.add_mesh(&sub_front);
        }
        (outter_mesh, inner_mesh)
    }

    pub fn union_convex_mesh(&self, other: &Mesh) -> Mesh {
        let (other_outter, _) = other.split_mesh_by_other(self);
        let (my_outter, _) = self.split_mesh_by_other(other);
        let mesh = other_outter + my_outter;
        mesh.weld().fix_tjunction().combine_adj_faces()
    }

    pub fn diff_convex_mesh(&self, other: &Mesh) -> Mesh {
        let (_, other_inner) =  other.split_mesh_by_other(self);
        let (my_outter, _) = self.split_mesh_by_other(other);
        let mesh = other_inner.flip_mesh() + my_outter;
        mesh.weld().fix_tjunction().combine_adj_faces()
    }

    pub fn intersect_convex_mesh(&self, other: &Mesh) -> Mesh {
        let (_, other_inner) =  other.split_mesh_by_other(self);
        let (_, my_inner) = self.split_mesh_by_other(other);
        let mesh = other_inner + my_inner;
        mesh.weld().fix_tjunction().combine_adj_faces()
    }

    pub fn split_mesh_by_plane(&self, pt_on_plane: Point3<f32>, norm: Vector3<f32>, fill_cut: bool) -> (Mesh, Mesh) { 
        let mut vert_side_map : HashMap<Id, PointSide> = HashMap::new();
        for face_id in FaceIterator::new(self) {
            for halfedge_id in FaceHalfedgeIterator::new(self, self.face_first_halfedge_id(face_id).unwrap()) {
                let vert = self.halfedge_start_vertex(halfedge_id).unwrap();
                vert_side_map.entry(vert.id).or_insert(point_side_on_plane(vert.position, pt_on_plane, norm));
            }
        }
        let mut front_mesh = Mesh::new();
        let mut back_mesh = Mesh::new();
        let mut front_vert_map : HashMap<Id, Id> = HashMap::new();
        let mut back_vert_map : HashMap<Id, Id> = HashMap::new();
        let mut intersect_map : HashMap<EdgeEndpoints, SegmentPlaneIntersect> = HashMap::new();
        let mut front_intersect_map : HashMap<EdgeEndpoints, Id> = HashMap::new();
        let mut back_intersect_map : HashMap<EdgeEndpoints, Id> = HashMap::new();
        let mut front_cut_map : HashMap<Id, Id> = HashMap::new();
        let mut back_cut_map : HashMap<Id, Id> = HashMap::new();
        for face_id in FaceIterator::new(self) {
            let mut front_new_verts = Vec::new();
            let mut back_new_verts = Vec::new();
            let mut front_new_vert_set = HashSet::new();
            let mut back_new_vert_set = HashSet::new();
            let mut front_intersects = vec![0, 0];
            let mut back_intersects = vec![0, 0];
            for halfedge_id in FaceHalfedgeIterator::new(self, self.face_first_halfedge_id(face_id).unwrap()) {
                let from_vert_id = self.halfedge_start_vertex_id(halfedge_id).unwrap();
                let to_vert_id = self.halfedge_start_vertex_id(self.halfedge_next_id(halfedge_id).unwrap()).unwrap();
                let from_is_front = vert_side_map[&from_vert_id] != PointSide::Back;
                let to_is_front = vert_side_map[&to_vert_id] != PointSide::Back;
                let from_is_back = vert_side_map[&from_vert_id] != PointSide::Front;
                let to_is_back = vert_side_map[&to_vert_id] != PointSide::Front;
                let edge = EdgeEndpoints::new(from_vert_id, to_vert_id);
                if from_is_front {
                    let new_vert_id = *front_vert_map.entry(from_vert_id).or_insert_with(|| {
                        front_mesh.add_vertex(self.vertex(from_vert_id).unwrap().position)
                    });
                    if front_new_vert_set.insert(new_vert_id) {
                        front_new_verts.push(new_vert_id);
                    }
                }
                if from_is_back {
                    let new_vert_id = *back_vert_map.entry(from_vert_id).or_insert_with(|| {
                        back_mesh.add_vertex(self.vertex(from_vert_id).unwrap().position)
                    });
                    if back_new_vert_set.insert(new_vert_id) {
                        back_new_verts.push(new_vert_id);
                    }
                }
                if (from_is_front && to_is_back) || (from_is_back && to_is_front) {
                    let intersect = intersect_map.entry(edge.clone()).or_insert_with(|| {
                        let p0 = self.vertex(from_vert_id).unwrap().position;
                        let p1 = self.vertex(to_vert_id).unwrap().position;
                        intersect_of_segment_and_plane(p0, p1, pt_on_plane, norm)
                    });
                    if let SegmentPlaneIntersect::Intersection(intersect_pt) = *intersect {
                        if from_is_front || to_is_front {
                            let new_vert_id = *front_intersect_map.entry(edge.clone()).or_insert_with(|| {
                                front_mesh.add_vertex(intersect_pt)
                            });
                            if front_new_vert_set.insert(new_vert_id) {
                                front_new_verts.push(new_vert_id);
                            }
                            if from_is_front {
                                front_intersects[0] = new_vert_id;
                            }
                            if to_is_front {
                                front_intersects[1] = new_vert_id;
                            }
                        }
                        if from_is_back || to_is_back {
                            let new_vert_id = *back_intersect_map.entry(edge.clone()).or_insert_with(|| {
                                back_mesh.add_vertex(intersect_pt)
                            });
                            if back_new_vert_set.insert(new_vert_id) {
                                back_new_verts.push(new_vert_id);
                            }
                            if from_is_front {
                                back_intersects[0] = new_vert_id;
                            }
                            if to_is_front {
                                back_intersects[1] = new_vert_id;
                            }
                        }
                    }
                }
                if to_is_front {
                    let new_vert_id = *front_vert_map.entry(to_vert_id).or_insert_with(|| {
                        front_mesh.add_vertex(self.vertex(to_vert_id).unwrap().position)
                    });
                    if front_new_vert_set.insert(new_vert_id) {
                        front_new_verts.push(new_vert_id);
                    }
                }
                if to_is_back {
                    let new_vert_id = *back_vert_map.entry(to_vert_id).or_insert_with(|| {
                        back_mesh.add_vertex(self.vertex(to_vert_id).unwrap().position)
                    });
                    if back_new_vert_set.insert(new_vert_id) {
                        back_new_verts.push(new_vert_id);
                    }
                }
            }
            if front_new_verts.len() >= 3 {
                front_mesh.add_vertices(front_new_verts);
            }
            if back_new_verts.len() >= 3 {
                back_mesh.add_vertices(back_new_verts);
            }
            if front_intersects[0] > 0 && front_intersects[1] > 0 {
                front_cut_map.insert(front_intersects[1], front_intersects[0]);
            }
            if back_intersects[0] > 0 && back_intersects[1] > 0 {
                back_cut_map.insert(back_intersects[0], back_intersects[1]);
            }
        }
        if fill_cut {
            if front_cut_map.len() >= 3 {
                while front_mesh.add_linked_vertices(&mut front_cut_map) > 0 {};
            }
            if back_cut_map.len() >= 3 {
                while back_mesh.add_linked_vertices(&mut back_cut_map) > 0 {};
            }
        }
        (front_mesh, back_mesh)
    }

    fn split_halfedge(&mut self, halfedge_id: Id, vertex_id: Id) -> Id {
        let (face_id, next_halfedge_id) = {
            let halfedge = self.halfedge(halfedge_id).unwrap();
            (halfedge.face, halfedge.next)
        };
        let new_halfedge_id = self.add_halfedge();
        {
            let new_halfedge = self.halfedge_mut(new_halfedge_id).unwrap();
            new_halfedge.vertex = vertex_id;
            new_halfedge.face = face_id;
        }
        self.link_halfedges(new_halfedge_id, next_halfedge_id);
        self.link_halfedges(halfedge_id, new_halfedge_id);
        new_halfedge_id
    }

    pub fn fix_tjunction(&mut self) -> &mut Self {
        let mut may_broken_halfedges = Vec::new();
        for face_id in FaceIterator::new(self) {
            for halfedge_id in FaceHalfedgeIterator::new(self, self.face_first_halfedge_id(face_id).unwrap()) {
                if self.halfedge_opposite_id(halfedge_id).is_none() {
                    may_broken_halfedges.push(halfedge_id);
                }
            }
        }
        let mut i = 0;
        'outer: while i < may_broken_halfedges.len() {
            'inner: for j in 0..may_broken_halfedges.len() {
                let long_id = may_broken_halfedges[i];
                let short_id = may_broken_halfedges[j];
                if long_id == short_id {
                    continue;
                }
                if !self.halfedge_opposite_id(long_id).is_none() {
                    continue;
                }
                let long_begin = self.halfedge_start_vertex(long_id).unwrap().position;
                let long_end = self.halfedge_start_vertex(self.halfedge_next_id(long_id).unwrap()).unwrap().position;
                
                let (short_begin_pos, short_begin_vert_id) = {
                    let vert = self.halfedge_start_vertex(short_id).unwrap();
                    (vert.position, vert.id)
                };
                if is_point_on_segment(short_begin_pos, long_begin, long_end) {
                    may_broken_halfedges.push(self.split_halfedge(long_id, short_begin_vert_id));
                    continue 'outer;
                }

                let (short_end_pos, short_end_vert_id) = {
                    let vert = self.halfedge_start_vertex(self.halfedge_next_id(short_id).unwrap()).unwrap();
                    (vert.position, vert.id)
                };
                if is_point_on_segment(short_end_pos, long_begin, long_end) {
                    may_broken_halfedges.push(self.split_halfedge(long_id, short_end_vert_id));
                    continue 'outer;
                }
            }
            i += 1;
        }
        self
    }

    pub fn remove_extra_vertices(&self) -> Self {
        let from_mesh = self;
        let mut to_mesh = Mesh::new();
        let mut extra_vertices : HashSet<Id> = HashSet::new();
        for (_, &halfedge_id) in from_mesh.edges.iter() {
            let vert_id = from_mesh.halfedge_start_vertex_id(halfedge_id).unwrap();
            let prev_id = from_mesh.halfedge_prev_id(halfedge_id).unwrap();
            let prev_opposite_id = from_mesh.halfedge_opposite_id(prev_id);
            let opposite_id = from_mesh.halfedge_opposite_id(halfedge_id);
            if opposite_id.is_none() && prev_opposite_id.is_none() {
                extra_vertices.insert(vert_id);
            } else if let Some(opposite_id_val) = opposite_id {
                if from_mesh.halfedge_next_id(opposite_id_val) == prev_opposite_id {
                    extra_vertices.insert(vert_id);
                }
            }
        }
        let mut new_vert_map : HashMap<Id, Id> = HashMap::new();
        for face_id in FaceIterator::new(from_mesh) {
            let mut added_vertices : Vec<Id> = Vec::new();
            for halfedge_id in FaceHalfedgeIterator::new(from_mesh, from_mesh.face_first_halfedge_id(face_id).unwrap()) {
                let vert_id = from_mesh.halfedge_start_vertex_id(halfedge_id).unwrap();
                if extra_vertices.contains(&vert_id) {
                    continue;
                }
                let new_vert_id = *new_vert_map.entry(vert_id).or_insert_with(|| {
                    let new_added_vertex_id = to_mesh.add_vertex(from_mesh.vertex(vert_id).unwrap().position);
                    to_mesh.vertex_mut(new_added_vertex_id).unwrap().source = from_mesh.vertex(vert_id).unwrap().source;
                    new_added_vertex_id
                });
                added_vertices.push(new_vert_id);
            }
            to_mesh.add_vertices(added_vertices);
        }
        to_mesh
    }

    pub fn combine_coplanar_faces(&self) -> Self {
        let from_mesh = self;
        let mut to_mesh = Mesh::new();
        let mut coplanar_edges = HashSet::new();
        let mut coplanar_faces = HashSet::new();
        let mut coplanar_halfedge_link : HashMap<Id, Id> = HashMap::new();
        let mut face_norm_map : HashMap<Id, Vector3<f32>> = HashMap::new();
        for (edge, &halfedge_id) in from_mesh.edges.iter() {
            let face_id = from_mesh.halfedge_face_id(halfedge_id).unwrap();
            let face_norm = *face_norm_map.entry(face_id).or_insert_with(|| from_mesh.face_norm(face_id));
            if let Some(opposite_id) = from_mesh.halfedge_opposite_id(halfedge_id) {
                let opposite_face_id = from_mesh.halfedge_face_id(opposite_id).unwrap();
                let opposite_face_norm = *face_norm_map.entry(opposite_face_id).or_insert_with(|| from_mesh.face_norm(opposite_face_id));
                if almost_eq(face_norm, opposite_face_norm) {
                    let prev_id = from_mesh.halfedge_prev_id(halfedge_id);
                    let next_id = from_mesh.halfedge_next_id(halfedge_id);
                    let opposite_prev_id = from_mesh.halfedge_prev_id(opposite_id);
                    let opposite_next_id = from_mesh.halfedge_next_id(opposite_id);
                    if prev_id.is_none() || next_id.is_none() || opposite_prev_id.is_none() || opposite_next_id.is_none() {
                        continue;
                    }
                    let mut dir1 = from_mesh.halfedge_direct(prev_id.unwrap()).normalize().cross(from_mesh.halfedge_direct(opposite_next_id.unwrap()).normalize());
                    let mut dir2 = from_mesh.halfedge_direct(opposite_prev_id.unwrap()).normalize().cross(from_mesh.halfedge_direct(next_id.unwrap()).normalize());
                    if dir1.is_zero() {
                        dir1 = face_norm;
                    }
                    if dir2.is_zero() {
                        dir2 = face_norm;
                    }
                    if dir1.dot(dir2) < 0.0 {
                        continue;
                    }
                    coplanar_halfedge_link.insert(halfedge_id, opposite_id);
                    coplanar_halfedge_link.insert(opposite_id, halfedge_id);
                    coplanar_edges.insert(edge);
                    coplanar_faces.insert(face_id);
                    coplanar_faces.insert(opposite_face_id);
                }
            }
        }
        let mut new_vert_map : HashMap<Id, Id> = HashMap::new();
        for face_id in FaceIterator::new(from_mesh) {
            if !coplanar_faces.contains(&face_id) {
                let mut added_vertices : Vec<Id> = Vec::new();
                for halfedge_id in FaceHalfedgeIterator::new(from_mesh, from_mesh.face_first_halfedge_id(face_id).unwrap()) {
                    let vert_id = from_mesh.halfedge_start_vertex_id(halfedge_id).unwrap();
                    let new_vert_id = *new_vert_map.entry(vert_id).or_insert_with(|| {
                        let new_added_vert_id = to_mesh.add_vertex(from_mesh.vertex(vert_id).unwrap().position);
                        to_mesh.vertex_mut(new_added_vert_id).unwrap().source = from_mesh.vertex(vert_id).unwrap().source;
                        new_added_vert_id
                    });
                    added_vertices.push(new_vert_id);
                }
                to_mesh.add_vertices(added_vertices);
            }
        }
        let mut used_halfedges : HashSet<Id> = HashSet::new();
        for face_id in FaceIterator::new(from_mesh) {
            if coplanar_faces.contains(&face_id) {
                for halfedge_id in FaceHalfedgeIterator::new(from_mesh, from_mesh.face_first_halfedge_id(face_id).unwrap()) {
                    if coplanar_halfedge_link.contains_key(&halfedge_id) {
                        continue;
                    }
                    if used_halfedges.contains(&halfedge_id) {
                        continue;
                    }
                    used_halfedges.insert(halfedge_id);
                    let mut loop_halfedge_id = halfedge_id;
                    let mut loop_back = false;
                    let mut loop_halfedges : Vec<Id> = Vec::new();
                    for _i in 0..100 {
                        if coplanar_halfedge_link.contains_key(&loop_halfedge_id) {
                            loop_halfedge_id = from_mesh.halfedge_next_id(coplanar_halfedge_link[&loop_halfedge_id]).unwrap();
                        } else {
                            loop_halfedges.push(loop_halfedge_id);
                            loop_halfedge_id = from_mesh.halfedge_next_id(loop_halfedge_id).unwrap();
                        }
                        if halfedge_id == loop_halfedge_id {
                            loop_back = true;
                            break;
                        }
                    }
                    if loop_back && loop_halfedges.len() >= 3 {
                        let mut added_vertices : Vec<Id> = Vec::new();
                        for &loop_halfedge_id in loop_halfedges.iter() {
                            used_halfedges.insert(loop_halfedge_id);
                            let vert_id = from_mesh.halfedge_start_vertex_id(loop_halfedge_id).unwrap();
                            let new_vert_id = *new_vert_map.entry(vert_id).or_insert_with(|| {
                                let new_added_vert_id = to_mesh.add_vertex(from_mesh.vertex(vert_id).unwrap().position);
                                to_mesh.vertex_mut(new_added_vert_id).unwrap().source = from_mesh.vertex(vert_id).unwrap().source;
                                new_added_vert_id
                            });
                            added_vertices.push(new_vert_id);
                        }
                        to_mesh.add_vertices(added_vertices);
                    }
                }
            }
        }
        to_mesh.remove_extra_vertices().weld()
    }

    pub fn combine_adj_faces_round(&self) -> (bool, Self) {
        let from_mesh = self;
        let mut to_mesh = Mesh::new();
        let mut ignore_faces = HashSet::new();
        let mut new_vert_map : HashMap<Id, Id> = HashMap::new();
        let mut ignore_vert_ids : HashSet<Id> = HashSet::new();
        let mut pending_old_verts : Vec<Vec<Id>> = Vec::new();
        let mut face_pair_map : HashSet<FacePair> = HashSet::new();
        for (_, &halfedge_id) in from_mesh.edges.iter() {
            let face_id = from_mesh.halfedge_face_id(halfedge_id).unwrap();
            if ignore_faces.contains(&face_id) {
                continue;
            }
            if let Some(opposite_id) = from_mesh.halfedge_opposite_id(halfedge_id) {
                let opposite_face_id = from_mesh.halfedge_face_id(opposite_id).unwrap();
                if ignore_faces.contains(&opposite_face_id) {
                    continue;
                }
                let prev_id = from_mesh.halfedge_prev_id(halfedge_id).unwrap();
                let next_id = from_mesh.halfedge_next_id(halfedge_id).unwrap();
                let opposite_prev_id = from_mesh.halfedge_prev_id(opposite_id).unwrap();
                let opposite_next_id = from_mesh.halfedge_next_id(opposite_id).unwrap();
                if !almost_eq(from_mesh.halfedge_direct(prev_id).normalize(), from_mesh.halfedge_direct(opposite_next_id).normalize()) {
                    continue;
                }
                if !almost_eq(from_mesh.halfedge_direct(opposite_prev_id).normalize(), from_mesh.halfedge_direct(next_id).normalize()) {
                    continue;
                }
                let first_face_id = from_mesh.halfedge_opposite_face_id(prev_id);
                let second_face_id = from_mesh.halfedge_opposite_face_id(opposite_next_id);
                if (first_face_id == second_face_id) || 
                        (!first_face_id.is_none() && !second_face_id.is_none() && 
                            face_pair_map.contains(&FacePair::new(first_face_id.unwrap(), second_face_id.unwrap()))) {
                    ignore_vert_ids.insert(from_mesh.halfedge_start_vertex_id(halfedge_id).unwrap());
                }
                let first_face_id = from_mesh.halfedge_opposite_face_id(opposite_prev_id);
                let second_face_id = from_mesh.halfedge_opposite_face_id(next_id);
                if (first_face_id == second_face_id) || 
                        (!first_face_id.is_none() && !second_face_id.is_none() && 
                            face_pair_map.contains(&FacePair::new(first_face_id.unwrap(), second_face_id.unwrap()))) {
                    ignore_vert_ids.insert(from_mesh.halfedge_start_vertex_id(opposite_id).unwrap());
                }
                ignore_faces.insert(face_id);
                ignore_faces.insert(opposite_face_id);
                face_pair_map.insert(FacePair::new(face_id, opposite_face_id));
                let mut old_vertices = Vec::new();
                let mut loop_id = next_id;
                while loop_id != halfedge_id {
                    old_vertices.push(from_mesh.halfedge_start_vertex_id(loop_id).unwrap());
                    loop_id = from_mesh.halfedge_next_id(loop_id).unwrap();
                }
                loop_id = opposite_next_id;
                while loop_id != opposite_id {
                    old_vertices.push(from_mesh.halfedge_start_vertex_id(loop_id).unwrap());
                    loop_id = from_mesh.halfedge_next_id(loop_id).unwrap();
                }
                pending_old_verts.push(old_vertices);
            }
        }
        for face_id in FaceIterator::new(from_mesh) {
            if ignore_faces.contains(&face_id) {
                continue;
            }
            let mut old_vertices = Vec::new();
            for halfedge_id in FaceHalfedgeIterator::new(from_mesh, from_mesh.face_first_halfedge_id(face_id).unwrap()) {
                old_vertices.push(from_mesh.halfedge_start_vertex_id(halfedge_id).unwrap());
            }
            pending_old_verts.push(old_vertices);
        }
        for verts in pending_old_verts.iter() {
            let mut added_vertices = Vec::new();
            for old_vert_id in verts.iter() {
                if !ignore_vert_ids.contains(old_vert_id) {
                    let new_vert_id = new_vert_map.entry(*old_vert_id).or_insert_with(|| {
                        let new_added_vert_id = to_mesh.add_vertex(from_mesh.vertex(*old_vert_id).unwrap().position);
                        to_mesh.vertex_mut(new_added_vert_id).unwrap().source = from_mesh.vertex(*old_vert_id).unwrap().source;
                        new_added_vert_id
                    });
                    added_vertices.push(*new_vert_id);
                }
            }
            to_mesh.add_vertices(added_vertices);
        }
        (!ignore_faces.is_empty(), to_mesh)
    }

    pub fn combine_adj_faces(&self) -> Self {
        let mut from_mesh = self.clone();
        let mut combined = true;
        let mut to_mesh = Mesh::new();
        while combined {
            let (sub_combined, sub_to_mesh) = from_mesh.combine_adj_faces_round();
            combined = sub_combined;
            from_mesh = sub_to_mesh.clone();
            to_mesh = sub_to_mesh;
        }
        to_mesh
    }

    pub fn trim(&self, normalize: bool) -> Self {
        let mut to_mesh = Mesh::new();
        to_mesh.add_mesh(self);
        let mut x_low = f32::MAX;
        let mut x_high = f32::MIN;
        let mut y_low = f32::MAX;
        let mut y_high = f32::MIN;
        let mut z_low = f32::MAX;
        let mut z_high = f32::MIN;
        for vert in self.vertices.iter() {
            if vert.position.x < x_low {
                x_low = vert.position.x;
            } else if vert.position.x > x_high {
                x_high = vert.position.x;
            }
            if vert.position.y < y_low {
                y_low = vert.position.y;
            } else if vert.position.y > y_high {
                y_high = vert.position.y;
            }
            if vert.position.z < z_low {
                z_low = vert.position.z;
            } else if vert.position.z > z_high {
                z_high = vert.position.z;
            }
        }
        let x_middle = (x_high + x_low) / 2.0;
        let y_middle = (y_high + y_low) / 2.0;
        let z_middle = (z_high + z_low) / 2.0;
        if normalize {
            let x_size = x_high - x_low;
            let y_size = y_high - y_low;
            let z_size = z_high - z_low;
            let mut long_size = y_size;
            if x_size > long_size {
                long_size = x_size;
            }
            if z_size > long_size {
                long_size = z_size;
            }
            for vert in to_mesh.vertices.iter_mut() {
                vert.position.x = (vert.position.x - x_middle) / long_size;
                vert.position.y = (vert.position.y - y_middle) / long_size;
                vert.position.z = (vert.position.z - z_middle) / long_size;
            }
        } else {
            for vert in to_mesh.vertices.iter_mut() {
                vert.position.x -= x_middle;
                vert.position.y -= y_middle;
                vert.position.z -= z_middle;
            }
        }
        to_mesh
    }

    // The test method (V + F - E = 2) describled by Tobias Gurdan from
    // https://gamedev.stackexchange.com/questions/61878/how-check-if-an-arbitrary-given-mesh-is-a-single-closed-mesh
    pub fn is_triangulated_mesh_manifold(&self) -> bool {
        let mut edges : HashSet<EdgeEndpoints> = HashSet::new();
        let mut verts : HashSet<Id> = HashSet::new();
        let mut faces : HashSet<Id> = HashSet::new();
        for face_id in FaceIterator::new(self) {
            let mut face_verts = Vec::new();
            for halfedge_id in FaceHalfedgeIterator::new(self, self.face_first_halfedge_id(face_id).unwrap()) {
                let vert_id = self.halfedge_start_vertex_id(halfedge_id);
                if vert_id.is_none() {
                    return false;
                }
                let opposite_id = self.halfedge_opposite_id(halfedge_id);
                if opposite_id.is_none() {
                    return false;
                }
                face_verts.push(vert_id.unwrap());
            }
            if face_verts.len() < 3 {
                return false;
            } else {
                for i in 0..face_verts.len() {
                    let first_vert_id = face_verts[i];
                    let second_vert_id = face_verts[(i + 1) % face_verts.len()];
                    let key = EdgeEndpoints::new(first_vert_id, second_vert_id);
                    edges.insert(key);
                }
                verts.extend(face_verts.iter().cloned());
            }
            faces.insert(face_id);
        }
        verts.len() as isize + faces.len() as isize - edges.len() as isize == 2
    }

    pub fn broken_face_set(&self) -> HashSet<Id> {
        let mut broken_face_set = HashSet::new();
        let mut endpoints : HashMap<EdgeEndpoints, Vec<Id>> = HashMap::new();
        for face_id in FaceIterator::new(self) {
            let mut verts = Vec::new();
            for halfedge_id in FaceHalfedgeIterator::new(self, self.face_first_halfedge_id(face_id).unwrap()) {
                let vert_id = self.halfedge_start_vertex_id(halfedge_id);
                if vert_id.is_none() {
                    broken_face_set.insert(face_id);
                    break;
                }
                verts.push(vert_id.unwrap());
            }
            if verts.len() < 3 {
                broken_face_set.insert(face_id);
            } else {
                for i in 0..verts.len() {
                    let first_vert_id = verts[i];
                    let second_vert_id = verts[(i + 1) % verts.len()];
                    let key = EdgeEndpoints::new(first_vert_id, second_vert_id);
                    endpoints.entry(key).or_insert(Vec::new()).push(face_id);
                }
            }
        }
        for (_key, face_list) in endpoints {
            if face_list.len() != 2 {
                for face_id in face_list {
                    broken_face_set.insert(face_id);
                }
            }
        }
        broken_face_set
    }

    pub fn mirror_in_x(&self, center_x: f32) -> Self {
        let mut new_mesh = Mesh::new();
        new_mesh.add_mesh(self);
        for vert in new_mesh.vertices.iter_mut() {
            vert.position.x = center_x - vert.position.x;
        }
        new_mesh.flip_mesh()
    }

    pub fn mirror_in_z(&self, center_z: f32) -> Self {
        let mut new_mesh = Mesh::new();
        new_mesh.add_mesh(self);
        for vert in new_mesh.vertices.iter_mut() {
            vert.position.z = center_z - vert.position.z;
        }
        new_mesh.flip_mesh()
    }

    pub fn fix_hole(&self) -> Self {
        let mut new_mesh = Mesh::new();
        let mut border_map : HashMap<Id, Id> = HashMap::new();
        new_mesh.add_mesh(self);
        {
            for face_id in FaceIterator::new(&new_mesh) {
                for halfedge_id in FaceHalfedgeIterator::new(&new_mesh, new_mesh.face_first_halfedge_id(face_id).unwrap()) {
                    if new_mesh.halfedge_opposite_id(halfedge_id).is_none() {
                        let next_halfedge_id = new_mesh.halfedge_next_id(halfedge_id);
                        if next_halfedge_id.is_some() {
                            let vertex_id = new_mesh.halfedge_start_vertex_id(halfedge_id);
                            let next_vertex_id = new_mesh.halfedge_start_vertex_id(next_halfedge_id.unwrap());
                            if vertex_id.is_some() && next_vertex_id.is_some() {
                                border_map.insert(next_vertex_id.unwrap(), vertex_id.unwrap());
                            }
                        }
                    }
                }
            }
        }
        while new_mesh.add_linked_vertices(&mut border_map) > 0 {};
        new_mesh
    }

    pub fn smooth(&mut self, factor: f32, limit_vertices: Option<&HashSet<usize>>) {
        let mut neighbor_position_sum_map : HashMap<Id, (Point3<f32>, usize)> = HashMap::new();
        let mut face_norm_map : HashMap<Id, Vector3<f32>> = HashMap::new();
        for face_id in FaceIterator::new(self) {
            for halfedge_id in FaceHalfedgeIterator::new(self, self.face_first_halfedge_id(face_id).unwrap()) {
                let from_vert = self.halfedge_start_vertex(halfedge_id);
                if from_vert.is_some() {
                    let next_halfedge_id = self.halfedge_next_id(halfedge_id);
                    if next_halfedge_id.is_some() {
                        let to_vert = self.halfedge_start_vertex(next_halfedge_id.unwrap());
                        if to_vert.is_some() {
                            if limit_vertices.is_none() || limit_vertices.unwrap().contains(&to_vert.unwrap().id) {
                                let item = &mut neighbor_position_sum_map.entry(to_vert.unwrap().id).or_insert((Point3 {x:0.0, y:0.0, z:0.0}, 0));
                                item.0 += from_vert.unwrap().position.to_vec();
                                item.1 += 1;
                                face_norm_map.entry(face_id).or_insert_with(|| self.face_norm(face_id));
                            }
                        }
                    }
                }
            }
        }
        let self_factor = 1.0 - factor;
        let mut old_position_map: HashMap<Id, Point3<f32>> = HashMap::new();
        for vert in self.vertices.iter_mut() {
            match neighbor_position_sum_map.get(&vert.id) {
                Some(&sum_and_count) => {
                    if sum_and_count.1 > 0 {
                        let old_position = vert.position;
                        old_position_map.entry(vert.id).or_insert(old_position);
                        vert.position = (sum_and_count.0 / sum_and_count.1 as f32) * factor + old_position.to_vec() * self_factor;
                    }
                },
                _ => {}
            }
        }
        let mut change_back_pairs : Vec<(Id, Point3<f32>)> = Vec::new();
        for (face_id, face_normal) in face_norm_map {
            if face_normal.dot(self.face_norm(face_id)) <= 0.0 {
                for halfedge_id in FaceHalfedgeIterator::new(self, self.face_first_halfedge_id(face_id).unwrap()) {
                    let from_vert = self.halfedge_start_vertex(halfedge_id);
                    if from_vert.is_some() {
                        match old_position_map.get(&from_vert.unwrap().id) {
                            Some(&old_position) => {
                                change_back_pairs.push((from_vert.unwrap().id, old_position));
                            },
                            _ => {}
                        }
                    }
                }
            }
        }
        for (vert_id, old_position) in change_back_pairs {
            self.vertex_mut(vert_id).unwrap().position = old_position;
        }
    }
}

impl Add for Mesh {
    type Output = Mesh;

    fn add(self, other: Mesh) -> Mesh {
        let mut new_mesh = Mesh::new();
        new_mesh.add_mesh(&self);
        new_mesh.add_mesh(&other);
        new_mesh
    }
}

impl AddAssign for Mesh {
    fn add_assign(&mut self, other: Mesh) {
        self.add_mesh(&other);
    }
}

pub trait Export {
    fn export(&self, filename: &str) -> io::Result<()>;
}

pub trait Import {
    fn import(&mut self, filename: &str) -> io::Result<()>;
}

impl Clone for Mesh {
    fn clone(&self) -> Self {
        let mut mesh = Mesh::new();
        mesh.add_mesh(self);
        mesh
    }
}