use cgmath::Point3;
use cgmath::Vector3;
use cgmath::prelude::*;
use cgmath::Deg;
use std::collections::HashMap;
use std::collections::LinkedList;
use iterator::FaceHalfedgeIterator;
use mesh::Id;
use mesh::Mesh;
use util::*;
#[derive(Hash, Eq, PartialEq, Debug)]
struct WrapItemKey {
p1: usize,
p2: usize,
}
#[derive(Clone)]
pub struct WrapItem {
base_normal: Vector3<f32>,
pub p1: usize,
pub p2: usize,
pub p3: usize,
processed: bool,
}
pub struct Face3 {
pub p1: usize,
pub p2: usize,
pub p3: usize,
pub norm: Vector3<f32>,
pub index: usize,
}
pub struct Face4 {
pub p1: usize,
pub p2: usize,
pub p3: usize,
pub p4: usize,
}
#[derive(Clone)]
pub struct SourceVertex {
pub position: Point3<f32>,
pub source_plane: Id,
pub index: usize,
pub tag: Id,
}
pub struct GiftWrapper {
items: Vec<WrapItem>,
items_map: HashMap<WrapItemKey, usize>,
items_list: LinkedList<usize>,
candidates: Vec<usize>,
pub source_vertices: Vec<SourceVertex>,
pub generated_faces: Vec<Face3>,
generated_face_edges_map: HashMap<WrapItemKey, Option<usize>>,
generated_vertex_edges_map: HashMap<usize, Vec<usize>>,
finalize_finished: bool,
}
impl GiftWrapper {
pub fn new() -> Self {
GiftWrapper {
items: Vec::new(),
items_map: HashMap::new(),
items_list: LinkedList::new(),
source_vertices: Vec::new(),
candidates: Vec::new(),
generated_faces: Vec::new(),
generated_face_edges_map: HashMap::new(),
generated_vertex_edges_map: HashMap::new(),
finalize_finished: false,
}
}
pub fn add_source_vertex(&mut self, position: Point3<f32>, source_plane: Id, tag: Id) -> usize {
let added_index = self.source_vertices.len();
self.source_vertices.push(SourceVertex {position: position, source_plane: source_plane, tag: tag, index: added_index});
self.candidates.push(added_index);
added_index
}
fn calculate_face_vector(&self, p1: usize, p2: usize, base_normal: Vector3<f32>) -> Vector3<f32> {
let v1 = &self.source_vertices[p1];
let v2 = &self.source_vertices[p2];
let seg = v2.position - v1.position;
seg.cross(base_normal)
}
fn add_item(&mut self, p1: usize, p2: usize, base_normal: Vector3<f32>) {
{
let v1 = &self.source_vertices[p1];
let v2 = &self.source_vertices[p2];
if !self.items.is_empty() && v1.source_plane == v2.source_plane {
return;
}
}
if !self.find_item(p1, p2).is_none() || !self.find_item(p2, p1).is_none() {
return;
}
if self.is_edge_generated(p1, p2) || self.is_edge_generated(p2, p1) {
return;
}
let index = self.items.len();
self.items.push(WrapItem {p3: 0, p1: p1, p2: p2, base_normal: base_normal, processed: false});
self.items_map.insert(WrapItemKey {p1: p1, p2: p2}, index);
self.items_list.push_front(index);
}
pub fn find_item(&self, p1: usize, p2: usize) -> Option<&usize> {
let key = WrapItemKey {p1: p1, p2: p2};
self.items_map.get(&key)
}
pub fn add_startup(&mut self, p1: usize, p2: usize, base_normal: Vector3<f32>) {
if self.items.len() == 0 {
self.add_item(p1, p2, base_normal);
}
self.generated_face_edges_map.insert(WrapItemKey {p1: p2, p2: p1}, None);
}
fn is_edge_generated(&self, p1: usize, p2: usize) -> bool {
let key = WrapItemKey {p1: p1, p2: p2};
if self.generated_face_edges_map.get(&key).is_none() {
return false;
}
true
}
fn angle_of_base_face_and_point(&self, item_index: usize, vertex_index: usize) -> f32 {
let item = &self.items[item_index].clone();
if item.p1 == vertex_index || item.p2 == vertex_index {
return 0.0;
}
let v1 = &self.source_vertices[item.p1].clone();
let v2 = &self.source_vertices[item.p2].clone();
let vp = &self.source_vertices[vertex_index].clone();
if v1.source_plane == v2.source_plane && v1.source_plane == vp.source_plane {
return 0.0;
}
let vd1 = self.calculate_face_vector(item.p1, item.p2, item.base_normal);
let normal = norm(v2.position, v1.position, vp.position);
let vd2 = self.calculate_face_vector(item.p1, item.p2, normal);
let angle = Deg::from(vd2.angle(vd1));
angle.0
}
pub fn finished(&mut self) -> bool {
if !self.finalize_finished {
return false;
}
if self.candidates.is_empty() {
return true;
}
let mut rm_vec : Vec<usize> = Vec::new();
for (i, &it) in self.candidates.iter().enumerate() {
if self.is_vertex_closed(it) {
rm_vec.push(i);
}
}
for &i in rm_vec.iter().rev() {
self.candidates.swap_remove(i);
}
self.candidates.is_empty()
}
fn find_best_vertex_on_the_left(&mut self, item_index: usize) -> Option<usize> {
let p1 = self.items[item_index].p1;
let p2 = self.items[item_index].p2;
let mut max_angle = 0 as f32;
let mut choosen_it = None;
let mut rm_vec : Vec<usize> = Vec::new();
for (i, &it) in self.candidates.iter().enumerate() {
if self.is_vertex_closed(it) {
rm_vec.push(i);
continue;
}
if self.is_edge_closed(p1, it) || self.is_edge_closed(p2, it) {
continue;
}
let mut angle = self.angle_of_base_face_and_point(item_index, it);
if angle > max_angle {
max_angle = angle;
choosen_it = Some(it);
}
}
for &i in rm_vec.iter().rev() {
self.candidates.swap_remove(i);
}
choosen_it
}
pub fn peek_item(&self) -> Option<usize> {
for &item_index in self.items_list.iter() {
if !self.items[item_index].processed {
return Some(item_index);
}
}
None
}
fn is_edge_closed(&self, p1: usize, p2: usize) -> bool {
self.generated_face_edges_map.contains_key(&WrapItemKey {p1: p1, p2: p2}) &&
self.generated_face_edges_map.contains_key(&WrapItemKey {p1: p2, p2: p1})
}
fn is_vertex_closed(&self, vertex_index: usize) -> bool {
let map = self.generated_vertex_edges_map.get(&vertex_index);
if map.is_none() {
return false;
}
for &other_index in map.unwrap() {
if !self.is_edge_closed(vertex_index, other_index) {
return false;
}
}
true
}
fn generate(&mut self) {
while let Some(item_index) = self.peek_item() {
self.items[item_index].processed = true;
let p1 = self.items[item_index].p1;
let p2 = self.items[item_index].p2;
if self.is_edge_closed(p1, p2) {
continue;
}
let p3 = self.find_best_vertex_on_the_left(item_index);
if !p3.is_none() {
let p3 = p3.unwrap();
self.items[item_index].p3 = p3;
let base_normal = norm(self.source_vertices[p1].position,
self.source_vertices[p2].position,
self.source_vertices[p3].position);
let face_index = self.generated_faces.len();
self.generated_faces.push(Face3 {p1: p1, p2: p2, p3: p3, norm: base_normal, index: face_index});
self.add_item(p3, p2, base_normal);
self.add_item(p1, p3, base_normal);
self.generated_face_edges_map.insert(WrapItemKey {p1: p1, p2: p2}, Some(face_index));
self.generated_face_edges_map.insert(WrapItemKey {p1: p2, p2: p3}, Some(face_index));
self.generated_face_edges_map.insert(WrapItemKey {p1: p3, p2: p1}, Some(face_index));
self.generated_vertex_edges_map.entry(p1).or_insert(Vec::new()).push(p2);
self.generated_vertex_edges_map.entry(p1).or_insert(Vec::new()).push(p3);
self.generated_vertex_edges_map.entry(p2).or_insert(Vec::new()).push(p3);
self.generated_vertex_edges_map.entry(p2).or_insert(Vec::new()).push(p1);
self.generated_vertex_edges_map.entry(p3).or_insert(Vec::new()).push(p1);
self.generated_vertex_edges_map.entry(p3).or_insert(Vec::new()).push(p2);
}
}
}
fn add_candidate_vertices(&mut self, mesh: &mut Mesh, vertices: &Vec<Id>, plane_norm: Vector3<f32>, plane_id: usize) {
let mut vertices_index_set : HashMap<Id, usize> = HashMap::new();
for &old_vert_id in vertices {
let vertex = mesh.vertex(old_vert_id).unwrap();
vertices_index_set.entry(vertex.id).or_insert(self.add_source_vertex(vertex.position, plane_id, vertex.id));
}
for i in 0..vertices.len() {
let old_vert_id = vertices[i];
let old_next_vert_id = vertices[(i + 1) % vertices.len()];
let &vertex_index = vertices_index_set.get(&old_vert_id).unwrap();
let &next_vertex_index = vertices_index_set.get(&old_next_vert_id).unwrap();
self.add_startup(next_vertex_index,
vertex_index,
plane_norm);
}
}
fn add_candidate_face(&mut self, mesh: &mut Mesh, face_id: Id, reverse: bool) {
let mut vertices_index_set : HashMap<Id, usize> = HashMap::new();
for halfedge_id in FaceHalfedgeIterator::new(mesh, mesh.face_first_halfedge_id(face_id).unwrap()) {
let vertex = mesh.halfedge_start_vertex(halfedge_id).unwrap();
vertices_index_set.entry(vertex.id).or_insert(self.add_source_vertex(vertex.position, face_id, vertex.id));
}
let plane_norm = mesh.face_norm(face_id);
for halfedge_id in FaceHalfedgeIterator::new(mesh, mesh.face_first_halfedge_id(face_id).unwrap()) {
let halfedge_next_id = mesh.halfedge_next_id(halfedge_id).unwrap();
let next_vertex_id = mesh.halfedge_start_vertex_id(halfedge_next_id).unwrap();
let &next_vertex_index = vertices_index_set.get(&next_vertex_id).unwrap();
let vertex_id = mesh.halfedge_start_vertex_id(halfedge_id).unwrap();
let &vertex_index = vertices_index_set.get(&vertex_id).unwrap();
if reverse {
self.add_startup(vertex_index,
next_vertex_index,
-plane_norm);
} else {
self.add_startup(next_vertex_index,
vertex_index,
plane_norm);
}
}
}
fn another_vertex_index_of_face3(&self, f: &Face3, p1: usize, p2: usize) -> usize {
let indices = vec![f.p1, f.p2, f.p3];
for index in indices {
if index != p1 && index != p2 {
return index;
}
}
0
}
fn find_pair_face3(&self, f: &Face3, used_ids: &HashMap<usize, bool>, q: &mut Vec<Face4>) -> Option<usize> {
let indices = vec![f.p1, f.p2, f.p3];
for i in 0..indices.len() {
let next_i = (i + 1) % indices.len();
let next_next_i = (i + 2) % indices.len();
let paired_face3_id = self.generated_face_edges_map.get(&WrapItemKey {p1: indices[next_i], p2: indices[i]});
if !paired_face3_id.is_none() && !paired_face3_id.unwrap().is_none() {
let paired_face3_id = paired_face3_id.unwrap().unwrap();
if used_ids.contains_key(&paired_face3_id) {
continue;
}
let paired_face3 = &self.generated_faces[paired_face3_id];
if !almost_eq(paired_face3.norm, f.norm) {
continue;
}
let another_index = self.another_vertex_index_of_face3(paired_face3, indices[next_i], indices[i]);
let merged_f = Face4 {p1: indices[i], p2: another_index, p3: indices[next_i], p4: indices[next_next_i]};
q.push(merged_f);
return Some(paired_face3_id);
}
}
None
}
fn finalize(&mut self, mesh: &mut Mesh) {
let mut quards : Vec<Face4> = Vec::new();
let mut used_ids: HashMap<usize, bool> = HashMap::new();
self.finalize_finished = true;
for f in self.generated_faces.iter() {
if used_ids.contains_key(&f.index) {
continue;
}
used_ids.insert(f.index, true);
let paired = self.find_pair_face3(&f, &used_ids, &mut quards);
if !paired.is_none() {
used_ids.insert(paired.unwrap(), true);
continue;
}
let mut added_vertices = Vec::new();
added_vertices.push(self.source_vertices[f.p1].tag);
added_vertices.push(self.source_vertices[f.p2].tag);
added_vertices.push(self.source_vertices[f.p3].tag);
if 0 == mesh.add_vertices(added_vertices) {
self.finalize_finished = false;
}
}
for f in quards.iter() {
let mut added_vertices = Vec::new();
added_vertices.push(self.source_vertices[f.p1].tag);
added_vertices.push(self.source_vertices[f.p2].tag);
added_vertices.push(self.source_vertices[f.p3].tag);
added_vertices.push(self.source_vertices[f.p4].tag);
if 0 == mesh.add_vertices(added_vertices) {
self.finalize_finished = false;
}
}
}
pub fn stitch_two_faces(&mut self, mesh: &mut Mesh, face1: Id, face2: Id) {
let mut remove_faces = Vec::new();
self.add_candidate_face(mesh, face1, false);
if !mesh.face_adj_id(face1).is_none() {
remove_faces.push(face1);
}
self.add_candidate_face(mesh, face2, false);
if !mesh.face_adj_id(face2).is_none() {
remove_faces.push(face2);
}
self.generate();
for face_id in remove_faces {
mesh.remove_face(face_id);
}
self.finalize(mesh);
}
pub fn wrap_faces(&mut self, mesh: &mut Mesh, faces: &Vec<Id>) {
for &face_id in faces {
self.add_candidate_face(mesh, face_id, true);
}
self.generate();
self.finalize(mesh);
}
pub fn wrap_vertices(&mut self, mesh: &mut Mesh, vertices: &Vec<(Vec<Id>, Vector3<f32>)>) {
let mut next_plane_id = 1;
for vert in vertices {
self.add_candidate_vertices(mesh, &vert.0, vert.1, next_plane_id);
next_plane_id += 1;
}
self.generate();
self.finalize(mesh);
}
}