rust_3d/
unify_faces.rs

1/*
2Copyright 2019 Martin Buck
3
4Permission is hereby granted, free of charge, to any person obtaining a copy
5of this software and associated documentation files (the "Software"),
6to deal in the Software without restriction, including without limitation the
7rights to use, copy, modify, merge, publish, distribute, sublicense,
8and/or sell copies of the Software, and to permit persons to whom the Software
9is furnished to do so, subject to the following conditions:
10
11The above copyright notice and this permission notice shall
12be included all copies or substantial portions of the Software.
13
14THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
15EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
16MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
17IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
18DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
19TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE
20OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
21*/
22
23//! Algorithm to unifiy the face orientation within a mesh
24
25use crate::*;
26use bitvec::bitvec;
27use fnv::FnvHashSet;
28
29//------------------------------------------------------------------------------
30
31//@todo consider rewrite to mutate the input instead
32
33/// Algorithm to unifiy the face orientation within a mesh
34pub fn unify_faces<P, M>(mesh: &M) -> Result<M>
35where
36    M: IsFaceEditableMesh<P, Face3> + IsVertexEditableMesh<P, Face3> + Default,
37    P: IsBuildable3D,
38{
39    let v_to_f = vertex_to_face(mesh);
40    let n_f_total = mesh.num_faces();
41    let n_v_total = mesh.num_vertices();
42    let mut checked = bitvec![0; n_f_total];
43    let mut must_flip = bitvec![0; n_f_total];
44    let mut frontier = Vec::new();
45    let mut checked_lowest = 0;
46    let mut neighbour_buffer = Vec::new();
47
48    loop {
49        if checked_lowest == n_f_total {
50            break;
51        }
52
53        while checked_lowest < n_f_total {
54            let mut found = false;
55            if !checked[checked_lowest] {
56                frontier.push(checked_lowest);
57                checked.set(checked_lowest, true);
58                found = true;
59            }
60            checked_lowest += 1;
61            if found {
62                break;
63            }
64        }
65
66        while let Some(this) = frontier.pop() {
67            neighbour_buffer.clear();
68            collect_neighbour_faces(mesh, &v_to_f, FId { val: this }, &mut neighbour_buffer)?;
69
70            let [v1, v2, v3] = mesh.face_vertices(FId { val: this }).unwrap(); // safe since index is safe
71            let n_this = normal_of_face(&v1, &v2, &v3);
72
73            for neighbour in neighbour_buffer.iter() {
74                if checked[neighbour] {
75                    continue;
76                }
77
78                let [v1n, v2n, v3n] = mesh.face_vertices(FId { val: neighbour }).unwrap(); // safe since index is safe
79                let n_neighbour = normal_of_face(&v1n, &v2n, &v3n);
80
81                let are_different = n_this.dot(&n_neighbour) < 0.0;
82                let flip_this = must_flip[this];
83                must_flip.set(
84                    neighbour,
85                    if flip_this {
86                        !are_different
87                    } else {
88                        are_different
89                    },
90                );
91                frontier.push(neighbour);
92                checked.set(neighbour, true);
93            }
94        }
95    }
96
97    let mut result = M::default();
98    result.reserve_vertices(n_v_total);
99    result.reserve_faces(n_f_total);
100    for i in 0..n_v_total {
101        result.add_vertex(mesh.vertex(VId { val: i }).unwrap()); // safe since index safe
102    }
103
104    for i in 0..n_f_total {
105        let f = mesh.face_vertex_ids(FId { val: i }).unwrap(); // safe since index safe
106        if must_flip[i] {
107            //println!("add normal");
108            result.try_add_connection(f.a, f.c, f.b).unwrap(); // safe assuming original mesh was valid
109        } else {
110            //println!("add flipped");
111            result.try_add_connection(f.a, f.b, f.c).unwrap(); // safe assuming original mesh was valid
112        }
113    }
114
115    Ok(result)
116}
117
118//------------------------------------------------------------------------------
119
120fn vertex_to_face<P, M>(mesh: &M) -> Vec<FnvHashSet<usize>>
121where
122    M: IsMesh<P, Face3> + Default,
123    P: Is3D,
124{
125    let nv = mesh.num_vertices();
126    let nf = mesh.num_faces();
127    let mut v_to_f = vec![FnvHashSet::default(); nv];
128
129    for i in 0..nf {
130        let f = mesh.face_vertex_ids(FId { val: i }).unwrap(); // safe
131        v_to_f[f.a.val].insert(i);
132        v_to_f[f.b.val].insert(i);
133        v_to_f[f.c.val].insert(i);
134    }
135
136    v_to_f
137}
138
139//------------------------------------------------------------------------------
140
141fn collect_neighbour_faces<P, M>(
142    mesh: &M,
143    v_to_f: &Vec<FnvHashSet<usize>>,
144    fid: FId,
145    neighbours: &mut Vec<usize>,
146) -> Result<()>
147where
148    M: IsMesh<P, Face3> + Default,
149    P: Is3D,
150{
151    let f = mesh.face_vertex_ids(fid)?;
152    neighbours.extend(v_to_f[f.a.val].iter());
153    neighbours.extend(v_to_f[f.b.val].iter());
154    neighbours.extend(v_to_f[f.c.val].iter());
155    neighbours.sort();
156    neighbours.dedup();
157    neighbours.retain(|x| *x != fid.val);
158    Ok(())
159}
rust_3d/unify_faces.rs

rust_3d/
unify_faces.rs
