1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
use crate::mesh::*;
impl Mesh {
pub fn flip_orientation(&mut self) {
for face_id in self.face_iter() {
self.flip_orientation_of_face(face_id);
}
}
pub fn fix_orientation(&mut self) {
let mut visited_faces = std::collections::HashMap::new();
for face_id in self.face_iter() {
self.find_faces_to_flip_orientation(face_id, &mut visited_faces, false);
}
for (face_id, should_flip) in visited_faces {
if should_flip {
self.flip_orientation_of_face(face_id)
}
}
}
fn flip_orientation_of_face(&mut self, face_id: FaceID) {
let mut update_list = [(None, None, None); 3];
let mut i = 0;
for halfedge_id in self.face_halfedge_iter(face_id) {
let mut walker = self.walker_from_halfedge(halfedge_id);
let vertex_id = walker.vertex_id();
walker.as_previous();
update_list[i] = (Some(halfedge_id), walker.vertex_id(), walker.halfedge_id());
i += 1;
self.connectivity_info
.set_vertex_halfedge(walker.vertex_id().unwrap(), walker.halfedge_id());
walker.as_next().as_twin();
if walker.face_id().is_none() {
self.connectivity_info
.set_vertex_halfedge(walker.vertex_id().unwrap(), walker.halfedge_id());
self.connectivity_info
.set_halfedge_vertex(walker.halfedge_id().unwrap(), vertex_id.unwrap());
}
}
for (halfedge_id, new_vertex_id, new_next_id) in update_list.iter() {
self.connectivity_info
.set_halfedge_vertex(halfedge_id.unwrap(), new_vertex_id.unwrap());
self.connectivity_info
.set_halfedge_next(halfedge_id.unwrap(), *new_next_id);
}
}
fn find_faces_to_flip_orientation(
&self,
face_id: FaceID,
visited_faces: &mut std::collections::HashMap<FaceID, bool>,
should_flip: bool,
) {
if !visited_faces.contains_key(&face_id) {
visited_faces.insert(face_id, should_flip);
for halfedge_id in self.face_halfedge_iter(face_id) {
let mut walker = self.walker_from_halfedge(halfedge_id);
let vertex_id = walker.vertex_id();
if let Some(face_id_to_test) = walker.as_twin().face_id() {
let is_opposite = vertex_id == walker.vertex_id();
self.find_faces_to_flip_orientation(
face_id_to_test,
visited_faces,
is_opposite && !should_flip || !is_opposite && should_flip,
);
}
}
}
}
}
#[cfg(test)]
mod tests {
use super::*;
use three_d_asset::TriMesh;
#[test]
fn test_fix_orientation() {
let mut mesh = crate::test_utility::subdivided_triangle();
mesh.flip_orientation_of_face(mesh.face_iter().next().unwrap());
mesh.fix_orientation();
mesh.is_valid().unwrap();
}
#[test]
fn test_flip_orientation() {
let mut mesh: Mesh = TriMesh::sphere(4).into();
let mut map = std::collections::HashMap::new();
for face_id in mesh.face_iter() {
map.insert(face_id, mesh.face_normal(face_id));
}
mesh.flip_orientation();
mesh.is_valid().unwrap();
for face_id in mesh.face_iter() {
assert!((mesh.face_normal(face_id) - -*map.get(&face_id).unwrap()).magnitude() < 0.001);
}
}
}