rust_3d/
half_edge.rs

1/*
2Copyright 2017 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//! HalfEdge, the half edge data structure
24
25use crate::*;
26
27//------------------------------------------------------------------------------
28
29#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
30/// HalfEdge, the half edge data structure
31pub struct HalfEdge<IC>
32where
33    IC: IsIndexContainer,
34{
35    tails: IC,
36    twins: Vec<Option<EId>>,
37    vertices_start_edges: Vec<IC>,
38}
39
40impl<IC> HalfEdge<IC>
41where
42    IC: IsIndexContainer,
43{
44    /// Creates a new HalfEdge3D for the given IsMesh3D
45    /// This only stays valid if IMesh3D is not changed after creation
46    /// The mesh must be manifold
47    pub fn new<T, M>(mesh: &M) -> Self
48    where
49        M: IsMesh<T, Face3>,
50    {
51        let n_vertices = mesh.num_vertices();
52        let n_faces = mesh.num_faces();
53        let n_edges = 3 * n_faces;
54
55        let mut tails = IC::with_capacity_and_support_for(n_edges, n_vertices);
56
57        let twins = vec![None; 3 * n_faces];
58        let mut vertices_start_edges = Vec::with_capacity(n_vertices);
59        let estimated_edges_per_vertex = 6; // true for all vertices within regular meshes, possibly best estimate
60
61        for i in 0..n_faces {
62            match mesh.face_vertex_ids(FId { val: i }) {
63                Err(_) => {}
64                Ok(face) => {
65                    tails.push(face.a.val);
66                    tails.push(face.b.val);
67                    tails.push(face.c.val);
68
69                    safe_append_at(
70                        &mut vertices_start_edges,
71                        estimated_edges_per_vertex,
72                        n_edges,
73                        face.a.val,
74                        i * 3 + 0,
75                    );
76                    safe_append_at(
77                        &mut vertices_start_edges,
78                        estimated_edges_per_vertex,
79                        n_edges,
80                        face.b.val,
81                        i * 3 + 1,
82                    );
83                    safe_append_at(
84                        &mut vertices_start_edges,
85                        estimated_edges_per_vertex,
86                        n_edges,
87                        face.c.val,
88                        i * 3 + 2,
89                    );
90                }
91            }
92        }
93
94        let mut result = HalfEdge {
95            tails,
96            twins,
97            vertices_start_edges,
98        };
99
100        // For each edge, get tail of next
101        // Of this get all edges originating
102        // Of these the one where next has the same tail must be the twin
103        // @todo could let this fail if there is more than one valid candidate (not manifold)
104        let mut cache = Vec::new();
105        for i in 0..result.tails.len() {
106            cache.clear();
107            let _ = result.next(EId { val: i }).and_then(&mut |next_id: EId| {
108                result.edges_originating(
109                    VId {
110                        val: result.tails.get(next_id.val),
111                    },
112                    &mut cache,
113                )
114            });
115            for originating_id in cache.iter() {
116                let _ = result.next(*originating_id).map(|candidate_id| {
117                    if result.tails.get(candidate_id.val) == result.tails.get(i) {
118                        result.twins[i] = Some(candidate_id)
119                    }
120                });
121            }
122        }
123        result
124    }
125    /// Returns the ID of the vertex the edge originates from (error if id out of bounds)
126    pub fn tail(&self, id: EId) -> Result<VId> {
127        self.ensure_edge_id(id)?;
128        Ok(VId {
129            val: self.tails.get(id.val),
130        })
131    }
132    /// Returns the ID of the face the edge belongs to (error if id out of bounds)
133    pub fn face(&self, id: EId) -> Result<FId> {
134        self.ensure_edge_id(id)?;
135        Ok(FId { val: id.val / 3 })
136    }
137    /// Returns the ID of the twin edge (None if there isn't any) (error if id out of bounds)
138    pub fn twin(&self, id: EId) -> Result<Option<EId>> {
139        self.ensure_edge_id(id)?;
140        Ok(self.twins[id.val])
141    }
142    /// Returns the ID of the edge after this edge (error if id out of bounds)
143    pub fn next(&self, id: EId) -> Result<EId> {
144        self.ensure_edge_id(id)?;
145        if Self::last_in_face(id) {
146            return Ok(EId { val: id.val - 2 });
147        }
148        Ok(EId { val: id.val + 1 })
149    }
150    /// Returns the ID of the edge before this edge (error if id out of bounds)
151    pub fn prev(&self, id: EId) -> Result<EId> {
152        self.ensure_edge_id(id)?;
153        if Self::first_in_face(id) {
154            return Ok(EId { val: id.val + 2 });
155        }
156        Ok(EId { val: id.val - 1 })
157    }
158    /// Appends all edges originating (pointing away) from the given vertex (error if id out of bounds)
159    pub fn edges_originating(&self, id: VId, result: &mut Vec<EId>) -> Result<()> {
160        self.ensure_vertex_id(id)?;
161        result.extend(
162            self.vertices_start_edges[id.val]
163                .iter()
164                .map(|x| EId { val: x }),
165        );
166        Ok(())
167    }
168    /// Appends all edges ending (pointing at) the given vertex (error if id out of bounds)
169    /// cache is used to avoid allocations, pass any Vec
170    pub fn edges_ending(&self, id: VId, cache: &mut Vec<EId>, result: &mut Vec<EId>) -> Result<()> {
171        cache.clear();
172        self.edges_originating(id, cache)?;
173        for edge in cache {
174            match self.prev(*edge) {
175                Err(_) => {}
176                Ok(id) => result.push(id),
177            }
178        }
179        Ok(())
180    }
181    /// Appends all edges connected to the vertex (both originating and ending) (error if id out of bounds)
182    /// cache is used to avoid allocations, pass any Vec
183    pub fn edges_all(&self, id: VId, cache: &mut Vec<EId>, result: &mut Vec<EId>) -> Result<()> {
184        cache.clear();
185        self.edges_originating(id, cache)?;
186        for edge in cache {
187            result.push(*edge);
188            match self.prev(*edge) {
189                Err(_) => {}
190                Ok(id) => result.push(id),
191            }
192        }
193        Ok(())
194    }
195    /// Appends all faces a vertex is part of (error if id out of bounds)
196    /// cache is used to avoid allocations, pass any Vec
197    pub fn faces(&self, id: VId, cache: &mut Vec<EId>, result: &mut Vec<FId>) -> Result<()> {
198        cache.clear();
199        self.edges_originating(id, cache)?;
200        for edge in cache {
201            match self.face(*edge) {
202                Err(_) => {}
203                Ok(id) => result.push(id),
204            }
205        }
206        Ok(())
207    }
208    /// Returns true if the give edge is the first within a face
209    fn first_in_face(id: EId) -> bool {
210        id.val % 3 == 0
211    }
212    /// Returns true if the give edge is the last within a face
213    fn last_in_face(id: EId) -> bool {
214        id.val % 3 == 2
215    }
216    /// Fails if the edge ID is out of bounds
217    pub fn ensure_edge_id(&self, id: EId) -> Result<()> {
218        if id.val >= self.tails.len() {
219            return Err(ErrorKind::IncorrectEdgeID);
220        }
221        Ok(())
222    }
223    /// Fails if the vertex ID is out of bounds
224    pub fn ensure_vertex_id(&self, id: VId) -> Result<()> {
225        if id.val >= self.vertices_start_edges.len() {
226            return Err(ErrorKind::IncorrectVertexID);
227        }
228        Ok(())
229    }
230}
231
232//------------------------------------------------------------------------------
233
234impl<IC> From<(IC, Vec<Option<EId>>, Vec<IC>)> for HalfEdge<IC>
235where
236    IC: IsIndexContainer,
237{
238    fn from(ev: (IC, Vec<Option<EId>>, Vec<IC>)) -> Self {
239        Self {
240            tails: ev.0,
241            twins: ev.1,
242            vertices_start_edges: ev.2,
243        }
244    }
245}
246
247impl<IC> Into<(IC, Vec<Option<EId>>, Vec<IC>)> for HalfEdge<IC>
248where
249    IC: IsIndexContainer,
250{
251    fn into(self) -> (IC, Vec<Option<EId>>, Vec<IC>) {
252        (self.tails, self.twins, self.vertices_start_edges)
253    }
254}
255
256impl<IC> Into<(IC, Vec<Option<EId>>)> for HalfEdge<IC>
257where
258    IC: IsIndexContainer,
259{
260    fn into(self) -> (IC, Vec<Option<EId>>) {
261        (self.tails, self.twins)
262    }
263}
264
265impl<IC> Into<Vec<IC>> for HalfEdge<IC>
266where
267    IC: IsIndexContainer,
268{
269    fn into(self) -> Vec<IC> {
270        self.vertices_start_edges
271    }
272}
273
274//------------------------------------------------------------------------------
275
276fn safe_append_at<IC>(vec: &mut Vec<IC>, capacity: usize, support: usize, i: usize, val: usize)
277where
278    IC: IsIndexContainer,
279{
280    if i >= vec.len() {
281        vec.resize(i + 1, IC::with_capacity_and_support_for(capacity, support));
282    }
283
284    vec[i].push(val);
285}
rust_3d/half_edge.rs

rust_3d/
half_edge.rs
