1mod elements;
50pub mod integrations;
51mod ops;
52pub mod primitives;
53mod selection;
54#[cfg(feature = "rerun")]
55pub mod utils;
56
57pub use elements::*;
58pub use selection::*;
59
60use hashbrown::HashMap;
61use itertools::Itertools;
62use parry3d::{
63 math::Point,
64 partitioning::{Qbvh, QbvhUpdateWorkspace},
65 shape::Triangle,
66};
67
68use glam::Vec3;
69use slotmap::{SecondaryMap, SlotMap};
70
71#[cfg(feature = "rerun")]
72lazy_static::lazy_static! {
73 pub static ref RR: rerun::RecordingStream = rerun::RecordingStreamBuilder::new("mesh_graph").spawn().unwrap();
74}
75
76#[derive(Clone)]
80#[cfg_attr(feature = "bevy", derive(bevy::prelude::Component))]
81#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
82pub struct MeshGraph {
83 #[cfg_attr(feature = "serde", serde(skip))]
85 pub qbvh: Qbvh<Face>,
86 #[cfg_attr(feature = "serde", serde(skip))]
88 pub qbvh_workspace: QbvhUpdateWorkspace,
89 #[cfg_attr(feature = "serde", serde(skip))]
91 pub index_to_face_id: Vec<FaceId>,
92
93 pub vertices: SlotMap<VertexId, Vertex>,
95 pub halfedges: SlotMap<HalfedgeId, Halfedge>,
97 pub faces: SlotMap<FaceId, Face>,
99
100 pub positions: SecondaryMap<VertexId, Vec3>,
102 pub vertex_normals: Option<SecondaryMap<VertexId, Vec3>>,
104}
105
106impl MeshGraph {
107 pub fn triangles(vertex_positions: &[Vec3]) -> Self {
112 assert!(
113 vertex_positions.len() % 3 == 0,
114 "Number of vertex positions should be a multiple of 3"
115 );
116
117 let mut unique_positions: Vec<Vec3> = Vec::with_capacity(vertex_positions.len() / 3);
119 let mut face_indices = Vec::with_capacity(vertex_positions.len());
120
121 for vertex_pos in vertex_positions {
122 let mut idx = None;
124 for (j, pos) in unique_positions.iter().enumerate() {
125 const EPSILON: f32 = 1e-5;
126
127 if pos.distance_squared(*vertex_pos) < EPSILON {
128 idx = Some(j);
129 break;
130 }
131 }
132
133 let vertex_idx = if let Some(idx) = idx {
135 idx
136 } else {
137 let new_idx = unique_positions.len();
138 unique_positions.push(*vertex_pos);
139 new_idx
140 };
141
142 face_indices.push(vertex_idx);
144 }
145
146 Self::indexed_triangles(&unique_positions, &face_indices)
148 }
149
150 pub fn indexed_triangles(vertex_positions: &[Vec3], face_indices: &[usize]) -> Self {
153 let mut graph = Self {
154 qbvh: Qbvh::new(),
155 qbvh_workspace: QbvhUpdateWorkspace::default(),
156 index_to_face_id: Vec::with_capacity(face_indices.len() / 3),
157
158 vertices: SlotMap::with_capacity_and_key(vertex_positions.len()),
159 halfedges: SlotMap::with_capacity_and_key(face_indices.len()),
160 faces: SlotMap::with_capacity_and_key(face_indices.len() / 3),
161
162 positions: SecondaryMap::with_capacity(vertex_positions.len()),
163 vertex_normals: None,
164 };
165
166 let mut vertex_ids = Vec::with_capacity(vertex_positions.len());
167
168 for pos in vertex_positions {
169 vertex_ids.push(graph.insert_vertex(*pos));
170 }
171
172 let mut start_end_vertex_to_halfedge =
173 HashMap::<(VertexId, VertexId), HalfedgeId>::default();
174
175 for chunk in face_indices.chunks_exact(3) {
176 let a = vertex_ids[chunk[0]];
177 let b = vertex_ids[chunk[1]];
178 let c = vertex_ids[chunk[2]];
179
180 let he_a_id = graph.insert_halfedge(b);
181 let he_b_id = graph.insert_halfedge(c);
182 let he_c_id = graph.insert_halfedge(a);
183
184 start_end_vertex_to_halfedge.insert((b, c), he_b_id);
185 start_end_vertex_to_halfedge.insert((c, a), he_c_id);
186
187 let face_id = graph.insert_face(he_a_id);
188
189 let he_a = &mut graph.halfedges[he_a_id];
190 he_a.next = Some(he_b_id);
191 he_a.face = Some(face_id);
192
193 if let Some(twin_a_id) = start_end_vertex_to_halfedge.get(&(b, a)) {
194 he_a.twin = Some(*twin_a_id);
195 graph.halfedges[*twin_a_id].twin = Some(he_a_id);
196 } else {
197 start_end_vertex_to_halfedge.insert((a, b), he_a_id);
198 }
199
200 let he_b = &mut graph.halfedges[he_b_id];
201 he_b.next = Some(he_c_id);
202 he_b.face = Some(face_id);
203
204 if let Some(twin_b_id) = start_end_vertex_to_halfedge.get(&(c, b)) {
205 he_b.twin = Some(*twin_b_id);
206 graph.halfedges[*twin_b_id].twin = Some(he_b_id);
207 } else {
208 start_end_vertex_to_halfedge.insert((b, c), he_b_id);
209 }
210
211 let he_c = &mut graph.halfedges[he_c_id];
212 he_c.next = Some(he_a_id);
213 he_c.face = Some(face_id);
214
215 if let Some(twin_c_id) = start_end_vertex_to_halfedge.get(&(a, c)) {
216 he_c.twin = Some(*twin_c_id);
217 graph.halfedges[*twin_c_id].twin = Some(he_c_id);
218 } else {
219 start_end_vertex_to_halfedge.insert((c, a), he_c_id);
220 }
221
222 graph.vertices[a].outgoing_halfedge = Some(he_a_id);
223 graph.vertices[b].outgoing_halfedge = Some(he_b_id);
224 graph.vertices[c].outgoing_halfedge = Some(he_c_id);
225 }
226
227 graph.rebuild_qbvh();
228
229 graph
230 }
231
232 pub fn compute_vertex_normals(&mut self) {
234 let mut normals = SecondaryMap::with_capacity(self.vertices.len());
235
236 for face in self.faces.values() {
237 let ha_a_id = face.halfedge;
238 let he_a = self.halfedges[ha_a_id];
239
240 let he_b_id = he_a
241 .next
242 .expect("Halfedge has definitely a face and thus a next halfedge");
243 let he_b = self.halfedges[he_b_id];
244
245 let a = he_a.start_vertex(self);
246 let b = he_a.end_vertex;
247 let c = he_b.end_vertex;
248
249 let diff_a = self.positions[c] - self.positions[a];
250 let diff_b = self.positions[c] - self.positions[b];
251
252 let face_normal = diff_a.cross(diff_b);
254
255 *normals.entry(a).unwrap().or_default() += face_normal;
256 *normals.entry(b).unwrap().or_default() += face_normal;
257 *normals.entry(c).unwrap().or_default() += face_normal;
258 }
259
260 self.vertex_normals = Some(normals);
261 self.normalize_vertex_normals();
262 }
263
264 pub fn normalize_vertex_normals(&mut self) {
266 if let Some(normals) = &mut self.vertex_normals {
267 for normal in normals.values_mut() {
268 *normal = normal.normalize();
269 }
270 }
271 }
272
273 pub fn rebalance_qbvh(&mut self) {
274 self.qbvh.rebalance(0.0, &mut self.qbvh_workspace);
275 }
276
277 pub fn refit_qbvh(&mut self) {
281 let mesh_graph = self.clone();
282
283 self.qbvh.refit(0.0, &mut self.qbvh_workspace, |face| {
284 let pos = face
285 .vertices(&mesh_graph)
286 .into_iter()
287 .map(|v| {
288 let Vec3 { x, y, z } = mesh_graph.positions[v];
289 Point::new(x, y, z)
290 })
291 .collect_vec();
292
293 Triangle::new(pos[0], pos[1], pos[2]).local_aabb()
294 });
295 }
296
297 fn recount_faces(&mut self) {
298 self.index_to_face_id.clear();
299 for (id, face) in &mut self.faces {
300 face.index = self.index_to_face_id.len();
301 self.index_to_face_id.push(id);
302 }
303 }
304
305 pub fn rebuild_qbvh(&mut self) {
307 self.recount_faces();
308
309 let data = self
310 .faces
311 .values()
312 .map(|face| {
313 let pos = face
314 .vertices(self)
315 .into_iter()
316 .map(|v| {
317 let Vec3 { x, y, z } = self.positions[v];
318 Point::new(x, y, z)
319 })
320 .collect_vec();
321
322 (*face, Triangle::new(pos[0], pos[1], pos[2]).local_aabb())
323 })
324 .collect_vec();
325
326 self.qbvh.clear_and_rebuild(data.into_iter(), 0.0);
327 }
328}
329
330#[cfg(feature = "rerun")]
331impl MeshGraph {
332 pub fn log_selection_rerun(&self, name: &str, selection: &Selection) {
333 use crate::RR;
334 use crate::utils::*;
335
336 RR.log(
337 format!("meshgraph/selection/{name}/points"),
338 &rerun::Points3D::new(
339 selection
340 .vertices
341 .iter()
342 .map(|v| vec3_array(self.positions[*v]))
343 .collect_vec(),
344 ),
345 )
346 .unwrap();
347
348 self.log_hes_rerun_with_name(
349 format!("meshgraph/selection/{name}/halfedges"),
350 &selection.halfedges.iter().copied().collect::<Vec<_>>(),
351 );
352
353 let face_centers = selection
354 .faces
355 .iter()
356 .map(|face_id| {
357 let face = self.faces[*face_id];
358
359 let center = face
360 .vertices(self)
361 .into_iter()
362 .map(|v_id| self.positions[v_id])
363 .reduce(|acc, p| acc + p)
364 .unwrap()
365 / 3.0;
366
367 vec3_array(center)
368 })
369 .collect_vec();
370
371 RR.log(
372 format!("meshgraph/selection/{name}/faces"),
373 &rerun::Points3D::new(face_centers),
374 )
375 .unwrap();
376 }
377
378 pub fn log_vert_rerun(&self, name: &str, vert: VertexId) {
379 use crate::RR;
380 use crate::utils::*;
381
382 let pos = self.positions[vert];
383
384 RR.log(
385 format!("meshgraph/vertex/{name}"),
386 &rerun::Points3D::new(vec![vec3_array(pos)]),
387 )
388 .unwrap();
389 }
390
391 pub fn log_he_rerun(&self, name: &str, halfedge: HalfedgeId) {
392 use crate::RR;
393 use crate::utils::*;
394
395 let he = self.halfedges[halfedge];
396
397 let start = self.positions[he.start_vertex(self)];
398 let end = self.positions[he.end_vertex];
399
400 RR.log(
401 format!("meshgraph/halfedge/{name}"),
402 &rerun::Arrows3D::from_vectors([vec3_array(end - start)])
403 .with_origins([vec3_array(start)]),
404 )
405 .unwrap();
406 }
407
408 pub fn log_hes_rerun(&self, name: &str, halfedges: &[HalfedgeId]) {
409 self.log_hes_rerun_with_name(format!("meshgraph/halfedge/{name}"), halfedges);
410 }
411
412 fn log_hes_rerun_with_name(&self, name: String, halfedges: &[HalfedgeId]) {
413 use crate::RR;
414 use crate::utils::*;
415
416 let mut origins = Vec::with_capacity(halfedges.len());
417 let mut vectors = Vec::with_capacity(halfedges.len());
418
419 for &he_id in halfedges {
420 let he = self.halfedges[he_id];
421
422 let start = self.positions[he.start_vertex(self)];
423 let end = self.positions[he.end_vertex];
424
425 origins.push(vec3_array(start));
426 vectors.push(vec3_array(end - start));
427 }
428
429 RR.log(
430 name,
431 &rerun::Arrows3D::from_vectors(vectors).with_origins(origins),
432 )
433 .unwrap();
434 }
435
436 pub fn log_face_rerun(&self, name: &str, face: FaceId) {
437 use crate::RR;
438 use crate::utils::*;
439
440 let mut origins = Vec::with_capacity(3);
441 let mut vectors = Vec::with_capacity(3);
442
443 let face = self.faces[face];
444
445 let pos = face
446 .vertices(self)
447 .iter()
448 .map(|v| self.positions[*v])
449 .collect::<Vec<_>>();
450
451 let center = pos.iter().copied().reduce(|a, b| a + b).unwrap() / pos.len() as f32;
452
453 let pos = face
454 .vertices(self)
455 .into_iter()
456 .zip(pos)
457 .map(|(v, p)| (v, center * 0.1 + p * 0.9))
458 .collect::<HashMap<_, _>>();
459
460 for he_id in face.halfedges(self) {
461 let he = self.halfedges[he_id];
462
463 let start = pos[&he.start_vertex(self)];
464 let end = pos[&he.end_vertex];
465
466 origins.push(vec3_array(start));
467 vectors.push(vec3_array(end - start));
468 }
469
470 #[cfg(feature = "rerun")]
471 {
472 RR.log(
473 format!("meshgraph/face/{name}"),
474 &rerun::Arrows3D::from_vectors(vectors).with_origins(origins),
475 )
476 .unwrap();
477 }
478 }
479
480 pub fn log_rerun(&self) {
481 use crate::RR;
482 use crate::utils::*;
483
484 let buffers = crate::integrations::VertexIndexBuffers::from(self.clone());
485 RR.log(
486 "meshgraph/mesh",
487 &rerun::Mesh3D::new(
488 buffers
489 .positions
490 .into_iter()
491 .zip(buffers.normals.iter().cloned())
492 .map(|(pos, norm)| vec3_array(pos - norm * 0.1)),
493 )
494 .with_triangle_indices(
495 buffers
496 .indices
497 .chunks(3)
498 .map(|chunk| rerun::datatypes::UVec3D::new(chunk[0], chunk[1], chunk[2])),
499 )
500 .with_vertex_colors(
501 buffers
502 .normals
503 .into_iter()
504 .map(|v| {
505 [
506 (100.0 + v.x * 100.0) as u8,
507 (100.0 + v.y * 100.0) as u8,
508 (100.0 + v.z * 100.0) as u8,
509 ]
510 })
511 .collect::<Vec<_>>(),
512 ),
513 )
514 .unwrap();
515
516 RR.log(
517 "meshgraph/positions",
518 &rerun::Points3D::new(self.positions.values().map(vec3_array))
519 .with_radii(self.positions.iter().map(|_| 0.01)),
520 )
521 .unwrap();
522
523 let mut origins = Vec::with_capacity(self.faces.len() * 3);
524 let mut vectors = Vec::with_capacity(self.faces.len() * 3);
525
526 let mut he_to_pos = HashMap::<HalfedgeId, (Vec3, Vec3)>::default();
527
528 for face in self.faces.values() {
529 let pos = face
530 .vertices(self)
531 .iter()
532 .map(|v| self.positions[*v])
533 .collect::<Vec<_>>();
534
535 let center = pos.iter().copied().reduce(|a, b| a + b).unwrap() / pos.len() as f32;
536
537 let pos = face
538 .vertices(self)
539 .into_iter()
540 .zip(pos)
541 .map(|(v, p)| (v, center * 0.1 + p * 0.9))
542 .collect::<HashMap<_, _>>();
543
544 for he_id in face.halfedges(self) {
545 let he = self.halfedges[he_id];
546
547 let start = pos[&he.start_vertex(self)];
548 let end = pos[&he.end_vertex];
549
550 he_to_pos.insert(he_id, (start, end));
551
552 origins.push(vec3_array(start));
553 vectors.push(vec3_array(end - start));
554 }
555 }
556
557 for (he_id, he) in &self.halfedges {
558 if he.is_boundary() {
559 let start_vertex = he.start_vertex(self);
560 let end_vertex = he.end_vertex;
561
562 let start = self.positions[start_vertex];
563 let end = self.positions[end_vertex];
564
565 let offset = if let Some(normals) = self.vertex_normals.as_ref() {
566 normals[start_vertex]
567 .lerp(normals[end_vertex], 0.5)
568 .cross(end - start)
569 .normalize()
570 * 0.1
571 } else {
572 Vec3::ZERO
573 };
574
575 let (start, end) = (start.lerp(end, 0.1) + offset, end.lerp(start, 0.1) + offset);
576
577 he_to_pos.insert(he_id, (start, end));
578
579 origins.push(vec3_array(start));
580 vectors.push(vec3_array(end - start));
581 }
582 }
583
584 RR.log(
585 "meshgraph/halfedges",
586 &rerun::Arrows3D::from_vectors(&vectors).with_origins(&origins),
587 )
588 .unwrap();
589
590 origins.clear();
591 vectors.clear();
592
593 for (he_id, he) in &self.halfedges {
594 let twin = he.twin();
595
596 let (he_start, he_end) = he_to_pos[&he_id];
597 let (tw_start, tw_end) = he_to_pos[&twin];
598
599 let start = he_start * 0.8 + he_end * 0.2;
600 let end = tw_start * 0.2 + tw_end * 0.8;
601
602 origins.push(vec3_array(start));
603 vectors.push(vec3_array(end - start));
604 }
605
606 RR.log(
607 "meshgraph/twins",
608 &rerun::Arrows3D::from_vectors(&vectors).with_origins(&origins),
609 )
610 .unwrap();
611
612 origins.clear();
613 vectors.clear();
614
615 for (v_id, v) in &self.vertices {
616 if let Some(he) = v.outgoing_halfedge.as_ref() {
617 let start = self.positions[v_id];
618
619 RR.log(
620 "meshgraph/the_vertex",
621 &rerun::Points3D::new([vec3_array(start)]),
622 )
623 .unwrap();
624
625 let (start_he, end_he) = he_to_pos[he];
626
627 let end = start_he.lerp(end_he, 0.05);
628
629 origins.push(vec3_array(start));
630 vectors.push(vec3_array(end - start));
631 }
632 }
633
634 RR.log(
635 "meshgraph/outgoing_halfedges",
636 &rerun::Arrows3D::from_vectors(&vectors).with_origins(&origins),
637 )
638 .unwrap();
639
640 origins.clear();
641 vectors.clear();
642
643 for face in self.faces.values() {
644 let start = face.center(self);
645
646 let (he_start, he_end) = he_to_pos[&face.halfedge];
647 let end = he_start * 0.6 + he_end * 0.4;
648
649 origins.push(vec3_array(start));
650 vectors.push(vec3_array(end - start));
651 }
652
653 RR.log(
654 "meshgraph/face_halfedges",
655 &rerun::Arrows3D::from_vectors(&vectors).with_origins(&origins),
656 )
657 .unwrap();
658
659 origins.clear();
660 vectors.clear();
661
662 for (he_id, he) in &self.halfedges {
663 if let Some(face_id) = he.face {
664 let (he_start, he_end) = he_to_pos[&he_id];
665 let start = he_start * 0.4 + he_end * 0.6;
666
667 let end = self.faces[face_id].center(self);
668
669 origins.push(vec3_array(start));
670 vectors.push(vec3_array((end - start) * 0.9));
671 }
672 }
673
674 RR.log(
675 "meshgraph/halfedge_faces",
676 &rerun::Arrows3D::from_vectors(&vectors).with_origins(&origins),
677 )
678 .unwrap();
679
680 origins.clear();
681 vectors.clear();
682
683 for (he_id, he) in &self.halfedges {
684 if let Some(next_id) = he.next {
685 let (he_start, he_end) = he_to_pos[&he_id];
686 let start = he_start * 0.15 + he_end * 0.85;
687
688 let (next_start, next_end) = he_to_pos[&next_id];
689 let end = next_start * 0.85 + next_end * 0.15;
690
691 origins.push(vec3_array(start));
692 vectors.push(vec3_array(end - start));
693 }
694 }
695
696 RR.log(
697 "meshgraph/halfedge_next",
698 &rerun::Arrows3D::from_vectors(&vectors).with_origins(&origins),
699 )
700 .unwrap();
701 }
702}