mesh_graph/
lib.rs

1//! MeshGraph is a halfedge data structure for representing triangle meshes.
2//! It uses parry3d's Qbvh to implement some of parry3d's spatial queries.
3//! It also uses slotmap to manage the graph nodes.
4//!
5//! This is heavily inspired by [SMesh](https://github.com/Bendzae/SMesh) and
6//! [OpenMesh](https://gitlab.vci.rwth-aachen.de:9000/OpenMesh/OpenMesh).
7//!
8//! ## Features
9//!
10//! - Fast spatial queries using parry3d's Qbvh
11//! - High performance using slotmap
12//! - Easy integration with Bevy game engine using the `bevy` Cargo feature
13//! - Good debugging using `rerun` Cargo feature to enable the Rerun integration
14//! - Nice documentation with illustrations
15//!
16//! ## Usage
17//!
18//! ```
19//! use mesh_graph::{MeshGraph, primitives::IcoSphere};
20//!
21//! // Create a new mesh
22//! let mesh_graph = MeshGraph::from(IcoSphere { radius: 10.0, subdivisions: 2 });
23//!
24//! // Get some vertex ID and its vertex node
25//! let (vertex_id, vertex) = mesh_graph.vertices.iter().next().unwrap();
26//!
27//! // Iterate over all outgoing halfedges of the vertex
28//! for halfedge_id in vertex.outgoing_halfedges(&mesh_graph) {
29//!     // do sth
30//! }
31//!
32//! // Get the position of the vertex
33//! let position = mesh_graph.positions[vertex_id];
34//! ```
35//!
36//! Check out the crate [freestyle-sculpt](https://github.com/Synphonyte/freestyle-sculpt) for
37//! a heavy duty example.
38//!
39//! ## Connectivity
40//!
41//! ### Halfedge
42//!
43//! <img src="https://raw.githubusercontent.com/Synphonyte/mesh-graph/refs/heads/main/docs/halfedge/all.svg" alt="Connectivity" style="max-width: 28em" />
44//!
45//! ### Vertex
46//!
47//! <img src="https://raw.githubusercontent.com/Synphonyte/mesh-graph/refs/heads/main/docs/vertex/all.svg" alt="Connectivity" style="max-width: 50em" />
48
49mod 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/// Halfedge data structure for representing triangle meshes.
77///
78/// Please see the [crate documentation](crate) for more information.
79#[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    /// Acceleration structure for fast spatial queries. Uses parry3d's Qbvh to implement some of parry3d's spatial queries.
84    #[cfg_attr(feature = "serde", serde(skip))]
85    pub qbvh: Qbvh<Face>,
86    /// Used in conjunction with the QBVH to accelerate spatial queries.
87    #[cfg_attr(feature = "serde", serde(skip))]
88    pub qbvh_workspace: QbvhUpdateWorkspace,
89    /// Used to map indices stored in the QBVH to face IDs.
90    #[cfg_attr(feature = "serde", serde(skip))]
91    pub index_to_face_id: Vec<FaceId>,
92
93    /// Maps vertex IDs to their corresponding graph node
94    pub vertices: SlotMap<VertexId, Vertex>,
95    /// Maps halfedge IDs to their corresponding graph node
96    pub halfedges: SlotMap<HalfedgeId, Halfedge>,
97    /// Maps face IDs to their corresponding graph node
98    pub faces: SlotMap<FaceId, Face>,
99
100    /// Maps vertex IDs to their corresponding positions
101    pub positions: SecondaryMap<VertexId, Vec3>,
102    /// Maps vertex IDs to their corresponding normals
103    pub vertex_normals: Option<SecondaryMap<VertexId, Vec3>>,
104}
105
106impl MeshGraph {
107    /// Create a triangle mesh graph from vertex positions.
108    /// Every three positions represent a triangle.
109    ///
110    /// Vertices with the same position are merged into a single vertex.
111    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        // Create a map to track unique vertices
118        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            // Check if we've seen this position before using a fuzzy float comparison
123            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            // Use the existing index or add a new vertex
134            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            // Add to face indices
143            face_indices.push(vertex_idx);
144        }
145
146        // Use indexed_triangles to create the mesh
147        Self::indexed_triangles(&unique_positions, &face_indices)
148    }
149
150    /// Create a triangle mesh graph from vertex positions and face indices.
151    /// Every chunk of three indices represents a triangle.
152    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    /// Computes the vertex normals by averaging over the computed face normals
233    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            // TODO : normalizing necessary here?
253            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    /// Ensures that the vertex normals are all normalized
265    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    /// Recomputes the bounding boxes of the QBVH. This is necessary when the mesh is modified.
278    ///
279    /// It does not no change the topology of the QBVH. Call `rebalance_qbvh` to to that.
280    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    /// Clear and rebuild the QBVH.
306    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}