1use crate::mesh::*;
4use std::collections::HashSet;
5
6impl Mesh {
7 pub fn merge_overlapping_primitives(&mut self) {
11 let set_of_vertices_to_merge = self.find_overlapping_vertices();
12 let set_of_edges_to_merge = self.find_overlapping_edges(&set_of_vertices_to_merge);
13 let set_of_faces_to_merge = self.find_overlapping_faces(&set_of_vertices_to_merge);
14
15 for faces_to_merge in set_of_faces_to_merge {
16 let mut iter = faces_to_merge.iter();
17 iter.next();
18 for face_id2 in iter {
19 self.remove_face_unsafe(*face_id2);
20 }
21 }
22
23 for vertices_to_merge in set_of_vertices_to_merge {
24 let mut iter = vertices_to_merge.iter();
25 let mut vertex_id1 = *iter.next().unwrap();
26 for vertex_id2 in iter {
27 vertex_id1 = self.merge_vertices(vertex_id1, *vertex_id2);
28 }
29 }
30
31 for edges_to_merge in set_of_edges_to_merge {
32 let mut iter = edges_to_merge.iter();
33 let mut edge_id1 = *iter.next().unwrap();
34 for edge_id2 in iter {
35 if let Some(e) = self.merge_halfedges(edge_id1, *edge_id2) {
36 edge_id1 = e;
37 }
38 }
39 }
40
41 self.fix_orientation();
42 }
43
44 fn merge_halfedges(
45 &mut self,
46 halfedge_id1: HalfEdgeID,
47 halfedge_id2: HalfEdgeID,
48 ) -> Option<HalfEdgeID> {
49 let mut walker1 = self.walker_from_halfedge(halfedge_id1);
50 let mut walker2 = self.walker_from_halfedge(halfedge_id2);
51
52 let edge1_alone = walker1.face_id().is_none() && walker1.as_twin().face_id().is_none();
53 let edge1_interior = walker1.face_id().is_some() && walker1.as_twin().face_id().is_some();
54 let edge1_boundary = !edge1_alone && !edge1_interior;
55
56 let edge2_alone = walker2.face_id().is_none() && walker2.as_twin().face_id().is_none();
57 let edge2_interior = walker2.face_id().is_some() && walker2.as_twin().face_id().is_some();
58 let edge2_boundary = !edge2_alone && !edge2_interior;
59
60 if edge1_interior && !edge2_alone || edge2_interior && !edge1_alone {
61 return None;
63 }
64
65 let mut halfedge_to_remove1 = None;
66 let mut halfedge_to_remove2 = None;
67 let mut halfedge_to_survive1 = None;
68 let mut halfedge_to_survive2 = None;
69 let mut vertex_id1 = None;
70 let mut vertex_id2 = None;
71
72 if edge1_boundary {
73 if walker1.face_id().is_none() {
74 walker1.as_twin();
75 };
76 halfedge_to_remove1 = walker1.twin_id();
77 halfedge_to_survive1 = walker1.halfedge_id();
78 vertex_id1 = walker1.vertex_id();
79 }
80 if edge2_boundary {
81 if walker2.face_id().is_none() {
82 walker2.as_twin();
83 };
84 halfedge_to_remove2 = walker2.twin_id();
85 halfedge_to_survive2 = walker2.halfedge_id();
86 vertex_id2 = walker2.vertex_id();
87 }
88 if edge1_alone {
89 if edge2_interior {
90 halfedge_to_remove1 = walker1.twin_id();
91 halfedge_to_remove2 = walker1.halfedge_id();
92
93 halfedge_to_survive1 = walker2.halfedge_id();
94 vertex_id1 = walker2.vertex_id();
95 walker2.as_twin();
96 halfedge_to_survive2 = walker2.halfedge_id();
97 vertex_id2 = walker2.vertex_id();
98 } else {
99 if vertex_id2 == walker1.vertex_id() {
100 walker1.as_twin();
101 }
102 halfedge_to_remove1 = walker1.twin_id();
103 halfedge_to_survive1 = walker1.halfedge_id();
104 vertex_id1 = walker1.vertex_id();
105 }
106 }
107 if edge2_alone {
108 if edge1_interior {
109 halfedge_to_remove1 = walker2.twin_id();
110 halfedge_to_remove2 = walker2.halfedge_id();
111
112 halfedge_to_survive1 = walker1.halfedge_id();
113 vertex_id1 = walker1.vertex_id();
114 walker1.as_twin();
115 halfedge_to_survive2 = walker1.halfedge_id();
116 vertex_id2 = walker1.vertex_id();
117 } else {
118 if vertex_id1 == walker2.vertex_id() {
119 walker2.as_twin();
120 }
121 halfedge_to_remove2 = walker2.twin_id();
122 halfedge_to_survive2 = walker2.halfedge_id();
123 vertex_id2 = walker2.vertex_id();
124 }
125 }
126
127 self.connectivity_info
128 .remove_halfedge(halfedge_to_remove1.unwrap());
129 self.connectivity_info
130 .remove_halfedge(halfedge_to_remove2.unwrap());
131 self.connectivity_info
132 .set_halfedge_twin(halfedge_to_survive1.unwrap(), halfedge_to_survive2.unwrap());
133 self.connectivity_info
134 .set_vertex_halfedge(vertex_id1.unwrap(), halfedge_to_survive2);
135 self.connectivity_info
136 .set_vertex_halfedge(vertex_id2.unwrap(), halfedge_to_survive1);
137 Some(halfedge_to_survive1.unwrap())
138 }
139
140 fn merge_vertices(&mut self, vertex_id1: VertexID, vertex_id2: VertexID) -> VertexID {
141 for halfedge_id in self.halfedge_iter() {
142 let walker = self.walker_from_halfedge(halfedge_id);
143 if walker.vertex_id().unwrap() == vertex_id2 {
144 self.connectivity_info
145 .set_halfedge_vertex(walker.halfedge_id().unwrap(), vertex_id1);
146 }
147 }
148 self.connectivity_info.remove_vertex(vertex_id2);
149
150 vertex_id1
151 }
152
153 fn find_overlapping_vertices(&self) -> Vec<Vec<VertexID>> {
154 let mut to_check = HashSet::new();
155 self.vertex_iter().for_each(|v| {
156 to_check.insert(v);
157 });
158
159 let mut set_to_merge = Vec::new();
160 while !to_check.is_empty() {
161 let id1 = *to_check.iter().next().unwrap();
162 to_check.remove(&id1);
163
164 let mut to_merge = Vec::new();
165 for id2 in to_check.iter() {
166 if (self.vertex_position(id1) - self.vertex_position(*id2)).magnitude() < 0.00001 {
167 to_merge.push(*id2);
168 }
169 }
170 if !to_merge.is_empty() {
171 for id in to_merge.iter() {
172 to_check.remove(id);
173 }
174 to_merge.push(id1);
175 set_to_merge.push(to_merge);
176 }
177 }
178 set_to_merge
179 }
180
181 fn find_overlapping_faces(
182 &self,
183 set_of_vertices_to_merge: &Vec<Vec<VertexID>>,
184 ) -> Vec<Vec<FaceID>> {
185 let vertices_to_merge = |vertex_id| {
186 set_of_vertices_to_merge
187 .iter()
188 .find(|vec| vec.contains(&vertex_id))
189 };
190 let mut to_check = HashSet::new();
191 self.face_iter().for_each(|id| {
192 to_check.insert(id);
193 });
194
195 let mut set_to_merge = Vec::new();
196 while !to_check.is_empty() {
197 let id1 = *to_check.iter().next().unwrap();
198 to_check.remove(&id1);
199
200 let (v0, v1, v2) = self.face_vertices(id1);
201 if let Some(vertices_to_merge0) = vertices_to_merge(v0) {
202 if let Some(vertices_to_merge1) = vertices_to_merge(v1) {
203 if let Some(vertices_to_merge2) = vertices_to_merge(v2) {
204 let mut to_merge = Vec::new();
205 for id2 in to_check.iter() {
206 let (v3, v4, v5) = self.face_vertices(*id2);
207 if (vertices_to_merge0.contains(&v3)
208 || vertices_to_merge0.contains(&v4)
209 || vertices_to_merge0.contains(&v5))
210 && (vertices_to_merge1.contains(&v3)
211 || vertices_to_merge1.contains(&v4)
212 || vertices_to_merge1.contains(&v5))
213 && (vertices_to_merge2.contains(&v3)
214 || vertices_to_merge2.contains(&v4)
215 || vertices_to_merge2.contains(&v5))
216 {
217 to_merge.push(*id2);
218 }
219 }
220 if !to_merge.is_empty() {
221 for id in to_merge.iter() {
222 to_check.remove(id);
223 }
224 to_merge.push(id1);
225 set_to_merge.push(to_merge);
226 }
227 }
228 }
229 }
230 }
231 set_to_merge
232 }
233
234 fn find_overlapping_edges(
235 &self,
236 set_of_vertices_to_merge: &Vec<Vec<VertexID>>,
237 ) -> Vec<Vec<HalfEdgeID>> {
238 let vertices_to_merge = |vertex_id| {
239 set_of_vertices_to_merge
240 .iter()
241 .find(|vec| vec.contains(&vertex_id))
242 };
243 let mut to_check = HashSet::new();
244 self.edge_iter().for_each(|e| {
245 to_check.insert(e);
246 });
247
248 let mut set_to_merge = Vec::new();
249 while !to_check.is_empty() {
250 let id1 = *to_check.iter().next().unwrap();
251 to_check.remove(&id1);
252
253 let (v0, v1) = self.edge_vertices(id1);
254 if let Some(vertices_to_merge0) = vertices_to_merge(v0) {
255 if let Some(vertices_to_merge1) = vertices_to_merge(v1) {
256 let mut to_merge = Vec::new();
257 for id2 in to_check.iter() {
258 let (v0, v1) = self.edge_vertices(*id2);
259 if vertices_to_merge0.contains(&v0) && vertices_to_merge1.contains(&v1)
260 || vertices_to_merge1.contains(&v0) && vertices_to_merge0.contains(&v1)
261 {
262 to_merge.push(*id2);
263 }
264 }
265 if !to_merge.is_empty() {
266 for id in to_merge.iter() {
267 to_check.remove(id);
268 }
269 to_merge.push(id1);
270 set_to_merge.push(to_merge);
271 }
272 }
273 }
274 }
275 set_to_merge
276 }
277}
278
279#[cfg(test)]
280mod tests {
281 use super::*;
282 use three_d_asset::{Indices, Positions, TriMesh};
283
284 #[test]
285 fn test_remove_lonely_vertices() {
286 let mut mesh = crate::test_utility::subdivided_triangle();
287 let mut iter = mesh.face_iter();
288 let face_id1 = iter.next().unwrap();
289 let face_id2 = iter.next().unwrap();
290 mesh.remove_face_unsafe(face_id1);
291 mesh.remove_face_unsafe(face_id2);
292
293 mesh.remove_lonely_primitives();
294
295 assert_eq!(3, mesh.no_vertices());
296 assert_eq!(6, mesh.no_halfedges());
297 assert_eq!(1, mesh.no_faces());
298 mesh.is_valid().unwrap();
299 }
300
301 #[test]
302 fn test_merge_overlapping_primitives() {
303 let positions = vec![
304 vec3(0.0, 0.0, 0.0),
305 vec3(1.0, 0.0, -0.5),
306 vec3(-1.0, 0.0, -0.5),
307 vec3(0.0, 0.0, 0.0),
308 vec3(-1.0, 0.0, -0.5),
309 vec3(0.0, 0.0, 1.0),
310 vec3(0.0, 0.0, 0.0),
311 vec3(0.0, 0.0, 1.0),
312 vec3(1.0, 0.0, -0.5),
313 ];
314
315 let mut mesh: Mesh = TriMesh {
316 positions: Positions::F64(positions),
317 ..Default::default()
318 }
319 .into();
320 mesh.merge_overlapping_primitives();
321
322 assert_eq!(4, mesh.no_vertices());
323 assert_eq!(12, mesh.no_halfedges());
324 assert_eq!(3, mesh.no_faces());
325 mesh.is_valid().unwrap();
326 }
327
328 #[test]
329 fn test_merge_overlapping_primitives_of_cube() {
330 let mut mesh: Mesh = TriMesh::cube().into();
331 mesh.merge_overlapping_primitives();
332
333 assert_eq!(8, mesh.no_vertices());
334 assert_eq!(36, mesh.no_halfedges());
335 assert_eq!(12, mesh.no_faces());
336 mesh.is_valid().unwrap();
337 }
338
339 #[test]
340 fn test_merge_overlapping_individual_faces() {
341 let mut mesh: Mesh = TriMesh {
342 positions: Positions::F64(vec![
343 vec3(0.0, 0.0, 0.0),
344 vec3(1.0, 0.0, -0.5),
345 vec3(-1.0, 0.0, -0.5),
346 vec3(0.0, 0.0, 0.0),
347 vec3(-1.0, 0.0, -0.5),
348 vec3(0.0, 0.0, 1.0),
349 vec3(0.0, 0.0, 0.0),
350 vec3(-1.0, 0.0, -0.5),
351 vec3(0.0, 0.0, 1.0),
352 ]),
353 ..Default::default()
354 }
355 .into();
356 mesh.merge_overlapping_primitives();
357
358 assert_eq!(4, mesh.no_vertices());
359 assert_eq!(10, mesh.no_halfedges());
360 assert_eq!(2, mesh.no_faces());
361 mesh.is_valid().unwrap();
362 }
363
364 #[test]
365 fn test_merge_two_overlapping_faces() {
366 let mut mesh: Mesh = TriMesh {
367 indices: Indices::U8(vec![0, 1, 2, 1, 3, 2, 4, 6, 5, 6, 7, 5]),
368 positions: Positions::F64(vec![
369 vec3(0.0, 0.0, 0.0),
370 vec3(-1.0, 0.0, 0.0),
371 vec3(-0.5, 0.0, 1.0),
372 vec3(-1.5, 0.0, 1.0),
373 vec3(-1.0, 0.0, 0.0),
374 vec3(-0.5, 0.0, 1.0),
375 vec3(-1.5, 0.0, 1.0),
376 vec3(-1.0, 0.0, 1.5),
377 ]),
378 ..Default::default()
379 }
380 .into();
381 mesh.merge_overlapping_primitives();
382
383 assert_eq!(5, mesh.no_vertices());
384 assert_eq!(14, mesh.no_halfedges());
385 assert_eq!(3, mesh.no_faces());
386 mesh.is_valid().unwrap();
387 }
388
389 #[test]
390 fn test_merge_three_overlapping_faces() {
391 let mut mesh: Mesh = TriMesh {
392 indices: Indices::U8(vec![0, 1, 2, 1, 3, 2, 4, 6, 5, 6, 7, 5, 8, 10, 9]),
393 positions: Positions::F64(vec![
394 vec3(0.0, 0.0, 0.0),
395 vec3(-1.0, 0.0, 0.0),
396 vec3(-0.5, 0.0, 1.0),
397 vec3(-1.5, 0.0, 1.0),
398 vec3(-1.0, 0.0, 0.0),
399 vec3(-0.5, 0.0, 1.0),
400 vec3(-1.5, 0.0, 1.0),
401 vec3(-1.0, 0.0, 1.5),
402 vec3(-1.0, 0.0, 0.0),
403 vec3(-0.5, 0.0, 1.0),
404 vec3(-1.5, 0.0, 1.0),
405 ]),
406 ..Default::default()
407 }
408 .into();
409 mesh.merge_overlapping_primitives();
410
411 assert_eq!(5, mesh.no_vertices());
412 assert_eq!(14, mesh.no_halfedges());
413 assert_eq!(3, mesh.no_faces());
414 mesh.is_valid().unwrap();
415 }
416
417 #[test]
418 fn test_merge_vertices() {
419 let mut mesh: Mesh = TriMesh {
420 positions: Positions::F64(vec![
421 vec3(0.0, 0.0, 0.0),
422 vec3(1.0, 0.0, -0.5),
423 vec3(-1.0, 0.0, -0.5),
424 vec3(0.0, 0.0, 0.0),
425 vec3(-1.0, 0.0, -0.5),
426 vec3(0.0, 0.0, 1.0),
427 ]),
428 ..Default::default()
429 }
430 .into();
431
432 let mut vertex_id1 = None;
433 for vertex_id in mesh.vertex_iter() {
434 if mesh.vertex_position(vertex_id) == vec3(0.0, 0.0, 0.0) {
435 if vertex_id1.is_none() {
436 vertex_id1 = Some(vertex_id);
437 } else {
438 mesh.merge_vertices(vertex_id1.unwrap(), vertex_id);
439 break;
440 }
441 }
442 }
443
444 assert_eq!(5, mesh.no_vertices());
445 assert_eq!(12, mesh.no_halfedges());
446 assert_eq!(2, mesh.no_faces());
447 }
448
449 #[test]
450 fn test_merge_halfedges() {
451 let mut mesh: Mesh = TriMesh {
452 positions: Positions::F64(vec![
453 vec3(1.0, 0.0, 0.0),
454 vec3(0.0, 0.0, 0.0),
455 vec3(0.0, 0.0, -1.0),
456 vec3(0.0, 0.0, 0.0),
457 vec3(1.0, 0.0, 0.0),
458 vec3(0.0, 0.0, 1.0),
459 ]),
460 ..Default::default()
461 }
462 .into();
463
464 let mut heid1 = None;
465 for halfedge_id in mesh.edge_iter() {
466 let (v0, v1) = mesh.edge_vertices(halfedge_id);
467 if mesh.vertex_position(v0)[2] == 0.0 && mesh.vertex_position(v1)[2] == 0.0 {
468 let halfedge_id = mesh.connecting_edge(v0, v1).unwrap();
469 if heid1.is_none() {
470 heid1 = Some((halfedge_id, v0, v1));
471 } else {
472 let (halfedge_id1, v10, v11) = heid1.unwrap();
473 mesh.merge_vertices(v0, v11);
474 mesh.merge_vertices(v1, v10);
475 mesh.merge_halfedges(halfedge_id1, halfedge_id).unwrap();
476 break;
477 }
478 }
479 }
480
481 assert_eq!(4, mesh.no_vertices());
482 assert_eq!(10, mesh.no_halfedges());
483 assert_eq!(2, mesh.no_faces());
484 }
485
486 #[test]
487 fn test_merge_overlapping_primitives_with_cube() {
488 let mut mesh: Mesh = TriMesh::cube().into();
489 mesh.merge_overlapping_primitives();
490 assert_eq!(mesh.no_faces(), 12);
491 assert_eq!(mesh.no_vertices(), 8);
492 mesh.is_valid().unwrap();
493 }
494}