mesh_graph/ops/
subdivide.rs

1use hashbrown::{HashMap, HashSet};
2
3use crate::{HalfedgeId, MeshGraph, Selection, SelectionOps, VertexId};
4
5#[cfg(feature = "rerun")]
6use crate::utils::vec3_array;
7
8impl MeshGraph {
9    /// Subdivides an edge by computing it's center vertex. This also subdivides any adjacent triangles and
10    /// makes sure everything is properly reconnected. Works only on triangle meshes.
11    ///
12    /// Returns the id of the new halfedge which goes from the center vertex to the original edge's end vertex.
13    /// And also return the halfedges that are created by subdividing the adjacent faces. Only one of the two twin
14    /// halfedges per face subdivision is returned. In total the number `n` of halfedges returned is `1 <= n <= 3`.
15    /// (The one from dividing the halfedge and at most 2 from dividing the two adjacent faces).
16    pub fn subdivide_edge(&mut self, halfedge_id: HalfedgeId) -> Vec<HalfedgeId> {
17        let he = &self.halfedges[halfedge_id];
18        let twin_id = he.twin();
19
20        let start_v = he.start_vertex(self);
21        let end_v = he.end_vertex;
22
23        let start_pos = self.positions[start_v];
24        let end_pos = self.positions[end_v];
25
26        let center_pos = (start_pos + end_pos) * 0.5;
27
28        #[cfg(feature = "rerun")]
29        {
30            crate::RR
31                .log(
32                    "meshgraph/subdivide/edge",
33                    &rerun::Arrows3D::from_vectors([vec3_array(end_pos - start_pos)])
34                        .with_origins([vec3_array(start_pos)]),
35                )
36                .unwrap();
37
38            crate::RR
39                .log(
40                    "meshgraph/subdivide/center",
41                    &rerun::Points3D::new([vec3_array(center_pos)]),
42                )
43                .unwrap();
44        }
45
46        let center_v = self.insert_vertex(center_pos);
47        if let Some(normals) = &mut self.vertex_normals {
48            normals[center_v] = (normals[start_v] + normals[end_v]).normalize();
49        }
50
51        let new_he = self.insert_halfedge(end_v);
52        self.vertices[center_v].outgoing_halfedge = Some(new_he);
53
54        let mut new_halfedges = Vec::with_capacity(3);
55        new_halfedges.push(new_he);
56
57        if let Some(new_face_he) = self.subdivide_face(halfedge_id, new_he, center_v) {
58            new_halfedges.push(new_face_he);
59        }
60
61        let new_twin = self.insert_halfedge(start_v);
62
63        if let Some(new_face_he) = self.subdivide_face(twin_id, new_twin, center_v) {
64            new_halfedges.push(new_face_he);
65        }
66
67        self.halfedges[new_he].twin = Some(twin_id);
68        self.halfedges[twin_id].twin = Some(new_he);
69
70        self.halfedges[halfedge_id].twin = Some(new_twin);
71        self.halfedges[new_twin].twin = Some(halfedge_id);
72
73        // self.vertices[end_v].outgoing_halfedge = Some(new_twin);
74        // self.vertices[start_v].outgoing_halfedge = Some(new_he);
75
76        new_halfedges
77    }
78
79    /// Subdivides a triangle into two halves. Used in [Self::subdivide_edge].
80    fn subdivide_face(
81        &mut self,
82        existing_halfedge_id: HalfedgeId,
83        new_halfedge_id: HalfedgeId,
84        center_v: VertexId,
85    ) -> Option<HalfedgeId> {
86        let he = &self.halfedges[existing_halfedge_id];
87
88        let face_id = he.face?;
89        self.faces[face_id].halfedge = existing_halfedge_id;
90
91        let next_he = self.halfedges[existing_halfedge_id].next.unwrap();
92        let last_he = self.halfedges[next_he].next.unwrap();
93
94        // rewire existing face
95        let new_he = self.insert_halfedge(self.halfedges[next_he].end_vertex);
96
97        self.halfedges[existing_halfedge_id].next = Some(new_he);
98        self.halfedges[new_he].next = Some(last_he);
99        self.halfedges[new_he].face = Some(face_id);
100
101        // insert new face
102        let new_face_id = self.insert_face(new_halfedge_id);
103
104        self.qbvh.pre_update_or_insert(self.faces[face_id]);
105        self.qbvh.pre_update_or_insert(self.faces[new_face_id]);
106
107        let new_twin = self.insert_halfedge(center_v);
108
109        self.halfedges[new_twin].next = Some(new_halfedge_id);
110        self.halfedges[new_twin].face = Some(new_face_id);
111        self.halfedges[new_twin].twin = Some(new_he);
112        self.halfedges[new_he].twin = Some(new_twin);
113
114        self.halfedges[new_halfedge_id].next = Some(next_he);
115        self.halfedges[new_halfedge_id].face = Some(new_face_id);
116
117        self.halfedges[next_he].next = Some(new_twin);
118        self.halfedges[next_he].face = Some(new_face_id);
119
120        self.halfedges[existing_halfedge_id].end_vertex = center_v;
121
122        #[cfg(feature = "rerun")]
123        {
124            self.log_he_rerun("subdivide/new_he", new_he);
125            self.log_he_rerun("subdivide/new_twin", new_twin);
126        }
127
128        Some(new_he)
129    }
130
131    /// Subdivide all edges in the selection until all of them are <= max_length.
132    /// Please note that you have to provide the squared value of max_length.
133    /// All new edges created during this process are added to the selection.
134    ///
135    /// This will schedule necessary updates to the QBVH but you have to call
136    /// `refit()` and maybe `rebalance()` after the operation.
137    pub fn subdivide_until_edges_below_max_length(
138        &mut self,
139        max_length_squared: f32,
140        selection: &mut Selection,
141    ) {
142        let mut dedup_halfedges = HashSet::new();
143
144        for he in selection.resolve_to_halfedges(self) {
145            let twin = self.halfedges[he].twin;
146            let twin_already_in = twin
147                .map(|twin| dedup_halfedges.contains(&twin))
148                .unwrap_or_default();
149
150            if !twin_already_in {
151                dedup_halfedges.insert(he);
152            }
153        }
154
155        let mut halfedges_to_subdivide = dedup_halfedges
156            .into_iter()
157            .filter_map(|he| {
158                let len = self.halfedges[he].length_squared(self);
159                (len > max_length_squared).then_some((he, len))
160            })
161            .collect::<HashMap<_, _>>();
162
163        while !halfedges_to_subdivide.is_empty() {
164            let mut max_len = 0.0;
165            let mut max_he = HalfedgeId::default();
166
167            for (&he, &len) in &halfedges_to_subdivide {
168                if len > max_len {
169                    max_len = len;
170                    max_he = he;
171                }
172            }
173
174            halfedges_to_subdivide.remove(&max_he);
175
176            let new_edges = self.subdivide_edge(max_he);
177
178            #[cfg(feature = "rerun")]
179            {
180                crate::RR
181                    .log("meshgraph/subdivide", &rerun::Clear::recursive())
182                    .unwrap();
183                crate::RR
184                    .log("meshgraph/halfedge/subdivide", &rerun::Clear::recursive())
185                    .unwrap();
186                crate::RR
187                    .log("meshgraph/face/subdivide", &rerun::Clear::recursive())
188                    .unwrap();
189                self.log_rerun();
190            }
191
192            for new_edge in new_edges {
193                selection.insert(new_edge);
194                if let Some(new_twin) = self.halfedges[new_edge].twin {
195                    selection.insert(new_twin);
196                }
197
198                let len_sqr = self.halfedges[new_edge].length_squared(self);
199                if len_sqr > max_length_squared {
200                    #[cfg(feature = "rerun")]
201                    {
202                        self.log_he_rerun("/subdivide/new_edge", new_edge);
203                    }
204                    halfedges_to_subdivide.insert(new_edge, len_sqr);
205                }
206            }
207
208            let len_sqr = self.halfedges[max_he].length_squared(self);
209            if len_sqr > max_length_squared {
210                #[cfg(feature = "rerun")]
211                {
212                    self.log_he_rerun("/subdivide/prev_edge", max_he);
213                }
214                halfedges_to_subdivide.insert(max_he, len_sqr);
215            }
216        }
217    }
218}
219
220#[cfg(test)]
221mod tests {}
mesh_graph/ops/subdivide.rs

mesh_graph/ops/
subdivide.rs
