1use super::level::{Level, TopologyError};
8use crate::sdc::{Crease, Scheme, Split};
9use crate::{Index, INDEX_INVALID};
10
11#[derive(Debug, Clone)]
19pub struct Refinement {
20 split: Split,
21 face_child_vert: Vec<Index>,
25 edge_child_vert: Vec<Index>,
27 vert_child_vert: Vec<Index>,
29 child_face_parent: Vec<Index>,
31}
32
33impl Refinement {
34 pub fn split(&self) -> Split {
36 self.split
37 }
38
39 pub fn face_child_vertex(&self, face: usize) -> Index {
42 self.face_child_vert[face]
43 }
44
45 pub fn edge_child_vertex(&self, edge: usize) -> Index {
48 self.edge_child_vert[edge]
49 }
50
51 pub fn vertex_child_vertex(&self, vertex: usize) -> Index {
54 self.vert_child_vert[vertex]
55 }
56
57 pub fn child_face_parent_face(&self, child_face: usize) -> Index {
59 self.child_face_parent[child_face]
60 }
61
62 pub fn refine(parent: &Level, scheme: &Scheme) -> Result<(Level, Refinement), TopologyError> {
70 Self::refine_selected(parent, scheme, None)
71 }
72
73 pub fn refine_selected(
79 parent: &Level,
80 scheme: &Scheme,
81 selection: Option<&[bool]>,
82 ) -> Result<(Level, Refinement), TopologyError> {
83 match selection {
84 None => Self::refine_included(parent, scheme, &vec![true; parent.num_faces()]),
85 Some(selected) => {
86 Self::refine_included(parent, scheme, &Self::expand_selection(parent, selected))
87 }
88 }
89 }
90
91 pub fn expand_selection(parent: &Level, selected: &[bool]) -> Vec<bool> {
96 assert_eq!(selected.len(), parent.num_faces());
97 let mut vertex_marked = vec![false; parent.num_vertices()];
98 for (f, &sel) in selected.iter().enumerate() {
99 if sel {
100 for &v in parent.face_vertices(f) {
101 vertex_marked[v as usize] = true;
102 }
103 }
104 }
105 (0..parent.num_faces())
106 .map(|f| {
107 parent
108 .face_vertices(f)
109 .iter()
110 .any(|&v| vertex_marked[v as usize])
111 })
112 .collect()
113 }
114
115 pub fn refine_included(
124 parent: &Level,
125 scheme: &Scheme,
126 included: &[bool],
127 ) -> Result<(Level, Refinement), TopologyError> {
128 assert_eq!(included.len(), parent.num_faces());
129 match scheme.scheme_type().topological_split_type() {
130 Split::ToQuads => Self::refine_quads(parent, scheme, included),
131 Split::ToTris => Self::refine_tris(parent, scheme, included),
132 Split::Hybrid => unimplemented!("hybrid splits are not used by any scheme"),
133 }
134 }
135
136 fn refine_quads(
137 parent: &Level,
138 scheme: &Scheme,
139 included: &[bool],
140 ) -> Result<(Level, Refinement), TopologyError> {
141 let (num_faces, num_edges, num_verts) = (
142 parent.num_faces(),
143 parent.num_edges(),
144 parent.num_vertices(),
145 );
146
147 let mut face_child_vert = vec![INDEX_INVALID; num_faces];
151 let mut edge_child_vert = vec![INDEX_INVALID; num_edges];
152 let mut vert_child_vert = vec![INDEX_INVALID; num_verts];
153
154 let mut edge_has_child = vec![false; num_edges];
155 let mut vert_has_child = vec![false; num_verts];
156 for (f, &inc) in included.iter().enumerate() {
157 if inc {
158 for &e in parent.face_edges(f) {
159 edge_has_child[e as usize] = true;
160 }
161 for &v in parent.face_vertices(f) {
162 vert_has_child[v as usize] = true;
163 }
164 }
165 }
166
167 let mut next = 0 as Index;
168 for (f, fcv) in face_child_vert.iter_mut().enumerate() {
169 if included[f] {
170 *fcv = next;
171 next += 1;
172 }
173 }
174 for (e, ecv) in edge_child_vert.iter_mut().enumerate() {
175 if edge_has_child[e] {
176 *ecv = next;
177 next += 1;
178 }
179 }
180 for (v, vcv) in vert_child_vert.iter_mut().enumerate() {
181 if vert_has_child[v] {
182 *vcv = next;
183 next += 1;
184 }
185 }
186 let num_child_verts = next as usize;
187
188 let mut verts_per_face = Vec::new();
191 let mut child_face_verts = Vec::new();
192 let mut child_face_parent = Vec::new();
193 for (f, &inc) in included.iter().enumerate() {
194 if !inc {
195 continue;
196 }
197 let center = face_child_vert[f];
198 let fv = parent.face_vertices(f);
199 let fe = parent.face_edges(f);
200 let n = fv.len();
201 for i in 0..n {
202 let prev = (i + n - 1) % n;
203 verts_per_face.push(4);
204 child_face_verts.extend_from_slice(&[
205 vert_child_vert[fv[i] as usize],
206 edge_child_vert[fe[i] as usize],
207 center,
208 edge_child_vert[fe[prev] as usize],
209 ]);
210 child_face_parent.push(f as Index);
211 }
212 }
213
214 let refinement = Refinement {
215 split: Split::ToQuads,
216 face_child_vert,
217 edge_child_vert,
218 vert_child_vert,
219 child_face_parent,
220 };
221 let child = refinement.finalize_child_level(
222 parent,
223 scheme,
224 num_child_verts,
225 &verts_per_face,
226 &child_face_verts,
227 )?;
228 Ok((child, refinement))
229 }
230
231 fn refine_tris(
232 parent: &Level,
233 scheme: &Scheme,
234 included: &[bool],
235 ) -> Result<(Level, Refinement), TopologyError> {
236 let (num_faces, num_edges, num_verts) = (
237 parent.num_faces(),
238 parent.num_edges(),
239 parent.num_vertices(),
240 );
241
242 let face_child_vert: Vec<Index> = vec![INDEX_INVALID; num_faces];
246 let mut edge_child_vert = vec![INDEX_INVALID; num_edges];
247 let mut vert_child_vert = vec![INDEX_INVALID; num_verts];
248
249 let mut edge_has_child = vec![false; num_edges];
250 let mut vert_has_child = vec![false; num_verts];
251 for (f, &inc) in included.iter().enumerate() {
252 if inc {
253 for &e in parent.face_edges(f) {
254 edge_has_child[e as usize] = true;
255 }
256 for &v in parent.face_vertices(f) {
257 vert_has_child[v as usize] = true;
258 }
259 }
260 }
261
262 let mut next = 0 as Index;
263 for (e, ecv) in edge_child_vert.iter_mut().enumerate() {
264 if edge_has_child[e] {
265 *ecv = next;
266 next += 1;
267 }
268 }
269 for (v, vcv) in vert_child_vert.iter_mut().enumerate() {
270 if vert_has_child[v] {
271 *vcv = next;
272 next += 1;
273 }
274 }
275 let num_child_verts = next as usize;
276
277 let mut verts_per_face = Vec::new();
287 let mut child_face_verts = Vec::new();
288 let mut child_face_parent = Vec::new();
289 for (f, &inc) in included.iter().enumerate() {
290 if !inc {
291 continue;
292 }
293 let fv = parent.face_vertices(f);
294 let fe = parent.face_edges(f);
295 debug_assert_eq!(fv.len(), 3, "tri split requires a triangulated level");
296 let v = |i: usize| vert_child_vert[fv[i] as usize];
297 let e = |i: usize| edge_child_vert[fe[i] as usize];
298 let children = [
299 [v(0), e(0), e(2)],
300 [e(0), v(1), e(1)],
301 [e(2), e(1), v(2)],
302 [e(1), e(2), e(0)],
303 ];
304 for child in &children {
305 verts_per_face.push(3);
306 child_face_verts.extend_from_slice(child);
307 child_face_parent.push(f as Index);
308 }
309 }
310
311 let refinement = Refinement {
312 split: Split::ToTris,
313 face_child_vert,
314 edge_child_vert,
315 vert_child_vert,
316 child_face_parent,
317 };
318 let child = refinement.finalize_child_level(
319 parent,
320 scheme,
321 num_child_verts,
322 &verts_per_face,
323 &child_face_verts,
324 )?;
325 Ok((child, refinement))
326 }
327
328 fn finalize_child_level(
338 &self,
339 parent: &Level,
340 scheme: &Scheme,
341 num_child_verts: usize,
342 verts_per_face: &[usize],
343 child_face_verts: &[Index],
344 ) -> Result<Level, TopologyError> {
345 let mut child =
346 Level::from_face_vertices(num_child_verts, verts_per_face, child_face_verts)?;
347 let crease = scheme.crease();
348
349 for v in 0..parent.num_vertices() {
352 let cv = self.vert_child_vert[v];
353 if cv == INDEX_INVALID {
354 continue;
355 }
356 let s = crease.subdivide_vertex_sharpness(parent.vertex_sharpness(v));
357 if Crease::is_sharp(s) {
358 child.set_vertex_sharpness(cv as usize, s);
359 }
360 }
361
362 let mut incident = Vec::new();
367 for e in 0..parent.num_edges() {
368 let mid = self.edge_child_vert[e];
369 if mid == INDEX_INVALID {
370 continue;
371 }
372 let sharpness = parent.edge_sharpness(e);
373 if !Crease::is_sharp(sharpness) {
374 continue;
375 }
376 for &end in &parent.edge_vertices(e) {
377 parent.gather_vertex_edge_sharpness(end as usize, &mut incident);
378 let child_sharpness =
379 crease.subdivide_edge_sharpness_at_vertex(sharpness, &incident);
380 if Crease::is_sharp(child_sharpness) {
381 let child_edge = child
382 .find_edge(self.vert_child_vert[end as usize], mid)
383 .expect("child of a parent edge must exist in the child level");
384 child.set_edge_sharpness(child_edge as usize, child_sharpness);
385 }
386 }
387 }
388
389 for (cf, &pf) in self.child_face_parent.iter().enumerate() {
391 if parent.is_face_hole(pf as usize) {
392 child.set_face_hole(cf, true);
393 }
394 }
395
396 Ok(child)
397 }
398}
399
400#[cfg(test)]
401mod tests {
402 use super::*;
403 use crate::sdc::{Options, SchemeType};
404
405 #[test]
406 fn quad_refinement_counts() {
407 let level = Level::from_face_vertices(4, &[4], &[0, 1, 2, 3]).unwrap();
409 let scheme = Scheme::new(SchemeType::Catmark, Options::default());
410 let (child, refinement) = Refinement::refine(&level, &scheme).unwrap();
411
412 assert_eq!(child.num_vertices(), 1 + 4 + 4);
413 assert_eq!(child.num_faces(), 4);
414 assert_eq!(child.num_edges(), 12);
415 assert_eq!(refinement.face_child_vertex(0), 0);
416 assert_eq!(refinement.edge_child_vertex(0), 1);
417 assert_eq!(refinement.vertex_child_vertex(0), 5);
418 }
419
420 #[test]
421 fn tri_refinement_counts() {
422 let level = Level::from_face_vertices(3, &[3], &[0, 1, 2]).unwrap();
424 let scheme = Scheme::new(SchemeType::Loop, Options::default());
425 let (child, _) = Refinement::refine(&level, &scheme).unwrap();
426
427 assert_eq!(child.num_vertices(), 3 + 3);
428 assert_eq!(child.num_faces(), 4);
429 assert_eq!(child.num_edges(), 9);
430 }
431
432 #[test]
433 fn sharpness_propagates() {
434 let level = {
435 let mut l = Level::from_face_vertices(4, &[4], &[0, 1, 2, 3]).unwrap();
436 let e = l.find_edge(0, 1).unwrap();
437 l.set_edge_sharpness(e as usize, 2.0);
438 l.set_vertex_sharpness(0, 3.0);
439 l
440 };
441 let options = Options::default()
444 .with_vtx_boundary_interpolation(crate::sdc::VtxBoundaryInterpolation::None);
445 let scheme = Scheme::new(SchemeType::Catmark, options);
446 let (child, refinement) = Refinement::refine(&level, &scheme).unwrap();
447
448 assert_eq!(
450 child.vertex_sharpness(refinement.vertex_child_vertex(0) as usize),
451 2.0
452 );
453 let e01 = level.find_edge(0, 1).unwrap() as usize;
456 let mid = refinement.edge_child_vertex(e01);
457 for corner in [0usize, 1] {
458 let half = child
459 .find_edge(refinement.vertex_child_vertex(corner), mid)
460 .unwrap();
461 assert_eq!(child.edge_sharpness(half as usize), 1.0);
462 }
463 }
464
465 #[test]
466 fn sparse_refinement_includes_one_ring() {
467 let mut verts_per_face = Vec::new();
470 let mut face_verts: Vec<Index> = Vec::new();
471 for j in 0..5u32 {
472 for i in 0..5u32 {
473 verts_per_face.push(4);
474 let v = j * 6 + i;
475 face_verts.extend_from_slice(&[v, v + 1, v + 7, v + 6]);
476 }
477 }
478 let level = Level::from_face_vertices(36, &verts_per_face, &face_verts).unwrap();
479 let scheme = Scheme::new(SchemeType::Catmark, Options::default());
480
481 let mut selected = vec![false; 25];
482 selected[12] = true; let (child, refinement) =
484 Refinement::refine_selected(&level, &scheme, Some(&selected)).unwrap();
485
486 assert_eq!(child.num_faces(), 36);
489 assert_eq!(child.num_vertices(), 9 + 24 + 16);
491 assert_eq!(refinement.face_child_vertex(0), crate::INDEX_INVALID);
493 assert_ne!(refinement.face_child_vertex(12), crate::INDEX_INVALID);
494 }
495}