1use super::gregory::{corner_span, is_edge_singular, vertex_rule, CornerSpan, SparsePoint};
44use crate::sdc::{Crease, Rule};
45use crate::vtr::Level;
46use crate::{Index, INDEX_INVALID};
47
48const MONOMIALS: [(u32, u32); 15] = [
54 (0, 0),
55 (0, 1),
56 (0, 2),
57 (0, 3),
58 (0, 4),
59 (1, 0),
60 (1, 1),
61 (1, 2),
62 (1, 3),
63 (2, 0),
64 (2, 1),
65 (2, 2),
66 (3, 0),
67 (3, 1),
68 (4, 0),
69];
70
71const BOX_SPLINE_COEFFS: [[i8; 15]; 12] = [
74 [1, -4, 6, -4, 1, -2, 6, -6, 2, 0, 0, 0, 2, -2, -1],
75 [1, -2, 0, 2, -1, 2, -6, 6, -2, 0, 0, 0, -4, 4, 2],
76 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, -2, -1],
77 [1, -2, 0, 2, -1, -4, 6, 0, -2, 6, -6, 0, -4, 2, 1],
78 [6, 0, -12, 8, -1, 0, -12, 12, -2, -12, 12, 0, 8, -2, -1],
79 [1, 2, 0, -4, 2, 4, 6, -12, 4, 6, -6, 0, -4, -2, -1],
80 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1],
81 [1, 2, 0, -4, 2, -2, -6, 0, 4, 0, 6, 0, 2, -2, -1],
82 [1, 4, 6, -4, -1, 2, 6, -6, -2, 0, -12, 0, -4, 4, 2],
83 [0, 0, 0, 2, -1, 0, 0, 6, -2, 0, 6, 0, 2, -2, -1],
84 [0, 0, 0, 2, -1, 0, 0, 0, -2, 0, 0, 0, 0, 0, 0],
85 [0, 0, 0, 0, 1, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0],
86];
87
88pub(crate) fn box_spline_basis(s: f32, t: f32) -> ([f32; 12], [f32; 12], [f32; 12]) {
92 let (s, t) = (f64::from(s), f64::from(t));
93 let mut pow_s = [1.0f64; 5];
94 let mut pow_t = [1.0f64; 5];
95 for k in 1..5 {
96 pow_s[k] = pow_s[k - 1] * s;
97 pow_t[k] = pow_t[k - 1] * t;
98 }
99 let mut w = [0.0f32; 12];
100 let mut ws = [0.0f32; 12];
101 let mut wt = [0.0f32; 12];
102 for (slot, coeffs) in BOX_SPLINE_COEFFS.iter().enumerate() {
103 let mut value = 0.0f64;
104 let mut ds = 0.0f64;
105 let mut dt = 0.0f64;
106 for (&c, &(i, j)) in coeffs.iter().zip(&MONOMIALS) {
107 if c == 0 {
108 continue;
109 }
110 let c = f64::from(c) / 12.0;
111 let (i, j) = (i as usize, j as usize);
112 value += c * pow_s[i] * pow_t[j];
113 if i > 0 {
114 ds += c * i as f64 * pow_s[i - 1] * pow_t[j];
115 }
116 if j > 0 {
117 dt += c * j as f64 * pow_s[i] * pow_t[j - 1];
118 }
119 }
120 w[slot] = value as f32;
121 ws[slot] = ds as f32;
122 wt[slot] = dt as f32;
123 }
124 (w, ws, wt)
125}
126
127#[allow(dead_code)] const SLOT_POSITIONS: [(i8, i8); 12] = [
143 (0, -1),
144 (1, -1),
145 (2, -1),
146 (-1, 0),
147 (0, 0),
148 (1, 0),
149 (2, 0),
150 (-1, 1),
151 (0, 1),
152 (1, 1),
153 (-1, 2),
154 (0, 2),
155];
156
157const RING_SLOTS: [[usize; 6]; 3] = [[5, 8, 7, 3, 0, 1], [8, 4, 1, 2, 6, 9], [4, 5, 9, 11, 10, 7]];
160
161#[cfg(test)]
164const EDGE_WALL_SLOTS: [[usize; 3]; 3] = [[0, 1, 2], [6, 9, 11], [3, 7, 10]];
165
166#[cfg(test)]
171const VERTEX_WALL_SLOTS: [[usize; 2]; 3] = [[0, 3], [2, 6], [10, 11]];
172
173fn is_corner_regular(level: &Level, face: usize, corner: usize) -> bool {
185 let v = level.face_vertices(face)[corner] as usize;
186 let edges = level.vertex_edges(v);
187 let num_faces = level.vertex_faces(v).len();
188 let vertex_sharpness = level.vertex_sharpness(v);
189
190 if Crease::is_semi_sharp(vertex_sharpness)
191 || edges
192 .iter()
193 .any(|&e| Crease::is_semi_sharp(level.edge_sharpness(e as usize)))
194 {
195 return false;
196 }
197 let inf_edges = edges
198 .iter()
199 .filter(|&&e| Crease::is_infinite(level.edge_sharpness(e as usize)))
200 .count();
201 let boundary = level.is_vertex_boundary(v);
202 let span_faces = || corner_span(level, face, corner, true).map(|span| span.num_faces());
203
204 match vertex_rule(vertex_sharpness, inf_edges) {
205 Rule::Smooth => !boundary && edges.len() == 6 && num_faces == 6,
206 Rule::Dart => false,
207 Rule::Crease => {
208 if boundary {
209 num_faces == 3 && edges.len() == 4
210 } else {
211 span_faces() == Some(3)
212 }
213 }
214 Rule::Corner => inf_edges > 0 && span_faces() == Some(1),
215 Rule::Unknown => false,
216 }
217}
218
219pub(crate) fn gather_regular_patch(level: &Level, face: usize) -> Option<[Index; 12]> {
225 let fv = level.face_vertices(face);
226 if fv.len() != 3 {
227 return None;
228 }
229 for corner in 0..3 {
230 if !is_corner_regular(level, face, corner) {
231 return None;
232 }
233 }
234
235 let mut cvs = [INDEX_INVALID; 12];
236 let mut set = |slot: usize, v: Index| -> Option<()> {
237 if cvs[slot] != INDEX_INVALID && cvs[slot] != v {
238 return None; }
240 cvs[slot] = v;
241 Some(())
242 };
243 for (corner, ring) in RING_SLOTS.iter().enumerate() {
244 let span = corner_span(level, face, corner, true)?;
245 if !span.boundary {
246 if span.edges.len() != 6 {
247 return None;
248 }
249 for (m, &slot) in ring.iter().enumerate() {
250 set(slot, span.edge_end(level, m))?;
251 }
252 } else {
253 let num_edges = span.edges.len();
254 if num_edges > 6 {
255 return None;
256 }
257 for m in 0..num_edges {
258 let r = (m + 6 - span.face_in_span) % 6;
259 set(ring[r], span.edge_end(level, m))?;
260 }
261 }
262 }
263
264 for slot in 0..12 {
268 if cvs[slot] == INDEX_INVALID {
269 let rule = phantom_rule(&cvs, slot)?;
270 if rule.iter().any(|&(target, _)| cvs[target] == INDEX_INVALID) {
271 return None;
272 }
273 }
274 }
275 Some(cvs)
276}
277
278fn walls(cvs: &[Index; 12]) -> ([bool; 3], [bool; 3]) {
285 let phantom = |slot: usize| cvs[slot] == INDEX_INVALID;
286 let edge = [phantom(1), phantom(9), phantom(7)];
287 let vertex = [
288 !edge[0] && !edge[2] && phantom(0),
289 !edge[0] && !edge[1] && phantom(2),
290 !edge[1] && !edge[2] && phantom(10),
291 ];
292 (edge, vertex)
293}
294
295fn phantom_rule(cvs: &[Index; 12], slot: usize) -> Option<[(usize, f32); 3]> {
301 let (e, v) = walls(cvs);
302 let parallelogram = |a: usize, b: usize, c: usize| Some([(a, 1.0), (b, 1.0), (c, -1.0)]);
303 let point = |v: usize, n: usize| Some([(v, 2.0), (n, -1.0), (n, 0.0)]);
304 match slot {
305 1 if e[0] => parallelogram(4, 5, 8),
307 0 if e[0] && e[2] => point(4, 8),
308 0 if e[0] => parallelogram(3, 4, 7),
309 0 if v[0] => parallelogram(4, 1, 5),
310 2 if e[0] && e[1] => point(5, 8),
311 2 if e[0] => parallelogram(5, 6, 9),
312 2 if v[1] => parallelogram(5, 1, 4),
313 9 if e[1] => parallelogram(5, 8, 4),
315 6 if e[1] && e[0] => point(5, 4),
316 6 if e[1] => parallelogram(5, 2, 1),
317 6 if v[1] => parallelogram(5, 9, 8),
318 11 if e[1] && e[2] => point(8, 4),
319 11 if e[1] => parallelogram(8, 10, 7),
320 11 if v[2] => parallelogram(8, 9, 5),
321 7 if e[2] => parallelogram(4, 8, 5),
323 3 if e[2] && e[0] => point(4, 5),
324 3 if e[2] => parallelogram(0, 4, 1),
325 3 if v[0] => parallelogram(4, 7, 8),
326 10 if e[2] && e[1] => point(8, 5),
327 10 if e[2] => parallelogram(8, 11, 9),
328 10 if v[2] => parallelogram(8, 7, 4),
329 _ => None,
330 }
331}
332
333pub(crate) fn fold_phantom_weights(cvs: &[Index; 12], weights: &mut [f32; 12]) {
337 for slot in 0..12 {
338 if cvs[slot] != INDEX_INVALID || weights[slot] == 0.0 {
339 continue;
340 }
341 let w = weights[slot];
342 weights[slot] = 0.0;
343 let rule = phantom_rule(cvs, slot).expect("gathered patches have valid phantoms");
344 for (target, factor) in rule {
345 debug_assert!(cvs[target] != INDEX_INVALID);
346 weights[target] += factor * w;
347 }
348 }
349}
350
351pub(crate) const NUM_GREGORY_TRI_POINTS: usize = 18;
357
358pub(crate) type GregoryTriPoints = [SparsePoint; NUM_GREGORY_TRI_POINTS];
363
364fn loop_beta(valence: usize) -> f32 {
366 let inv = 1.0 / valence as f32;
367 let t = 0.375 + 0.25 * (std::f32::consts::TAU * inv).cos();
368 (0.625 - t * t) * inv
369}
370
371const INTERIOR_TANGENT_SCALE: f32 = 1.0 / 3.0;
378
379const BOUNDARY_TANGENT_SCALE: f32 = 2.0 / 3.0;
383
384struct CornerPoints {
387 p: SparsePoint,
388 ep: SparsePoint,
389 em: SparsePoint,
390 child: SparsePoint,
391}
392
393fn interior_points(level: &Level, span: &CornerSpan) -> CornerPoints {
399 let n = span.edges.len();
400 let nf = n as f32;
401 let beta = loop_beta(n);
402 let omega = 3.0 / (8.0 * beta);
403 let e_weight = 1.0 / (omega + nf);
404 let mut p = SparsePoint::of(&[(span.vertex, omega * e_weight)]);
405 let mut child = SparsePoint::of(&[(span.vertex, 1.0 - nf * beta)]);
406 for i in 0..n {
407 p.add(span.edge_end(level, i), e_weight);
408 child.add(span.edge_end(level, i), beta);
409 }
410
411 let theta = std::f32::consts::TAU / nf;
412 let tangent = |j: usize| -> SparsePoint {
413 let mut t = SparsePoint::default();
414 for i in 0..n {
415 t.add(
416 span.edge_end(level, i),
417 INTERIOR_TANGENT_SCALE * ((i as f32 - j as f32) * theta).cos(),
418 );
419 }
420 t
421 };
422 let mut ep = p.clone();
423 ep.add_scaled(&tangent(0), 0.25);
424 let mut em = p.clone();
425 em.add_scaled(&tangent(1), 0.25);
426 CornerPoints { p, ep, em, child }
427}
428
429fn boundary_points(level: &Level, span: &CornerSpan) -> CornerPoints {
437 let k = span.num_faces();
438 debug_assert!(span.boundary && k >= 1);
439 let v = span.vertex;
440 let e0 = span.edge_end(level, 0);
441 let ek = span.edge_end(level, k);
442
443 let p = SparsePoint::of(&[(v, 2.0 / 3.0), (e0, 1.0 / 6.0), (ek, 1.0 / 6.0)]);
444 let child = SparsePoint::of(&[(v, 0.75), (e0, 0.125), (ek, 0.125)]);
445 let t_boundary = SparsePoint::of(&[(e0, 0.5), (ek, -0.5)]);
446
447 let kf = k as f32;
448 let theta = std::f32::consts::PI / kf;
449 let c = theta.cos();
450 let s = theta.sin();
451 let ring_sum = (1.0 + c) / s;
453 let w_v = (3.0 * (1.0 - 2.0 * c) * ring_sum - 8.0 * s) / (5.0 + 8.0 * c - 4.0 * c * c);
454 let w_0 = -(3.0 - 2.0 * c) / 8.0 * w_v - 3.0 / 8.0 * ring_sum;
455 let scale = BOUNDARY_TANGENT_SCALE;
456 let mut t_interior = SparsePoint::of(&[(v, scale * w_v), (e0, scale * w_0), (ek, scale * w_0)]);
457 for i in 1..k {
458 t_interior.add(span.edge_end(level, i), scale * (theta * i as f32).sin());
459 }
460
461 let along = |angle: f32| -> SparsePoint {
462 let mut e = p.clone();
463 e.add_scaled(&t_boundary, 0.25 * angle.cos());
464 e.add_scaled(&t_interior, 0.25 * angle.sin());
465 e
466 };
467 let f = span.face_in_span;
468 let ep = along(theta * f as f32);
469 let em = along(theta * (f + 1) as f32);
470 CornerPoints { p, ep, em, child }
471}
472
473struct Corner {
475 span: CornerSpan,
476 cos_angle: f32,
478 points: CornerPoints,
479}
480
481fn wrap(span: &CornerSpan, r: isize) -> usize {
484 if span.boundary {
485 (r + span.face_in_span as isize) as usize
486 } else {
487 r.rem_euclid(span.edges.len() as isize) as usize
488 }
489}
490
491impl Corner {
492 fn ring(&self, level: &Level, r: isize) -> SparsePoint {
497 let span = &self.span;
498 let v = span.vertex;
499 let e = |i: usize| span.edge_end(level, i);
500 if !span.boundary {
501 let n = span.edges.len() as isize;
502 return SparsePoint::of(&[(e(r.rem_euclid(n) as usize), 1.0)]);
503 }
504 let k = span.num_faces() as isize;
505 let r = r + span.face_in_span as isize;
506 if (0..=k).contains(&r) {
507 SparsePoint::of(&[(e(r as usize), 1.0)])
508 } else if r == -1 || r == k + 2 {
509 SparsePoint::of(&[(v, 1.0), (e(0), 1.0), (e(1), -1.0)])
510 } else {
511 debug_assert!(r == -2 || r == k + 1);
512 SparsePoint::of(&[(v, 1.0), (e(k as usize), 1.0), (e(k as usize - 1), -1.0)])
513 }
514 }
515}
516
517fn face_point(
525 level: &Level,
526 near: &Corner,
527 far: &Corner,
528 mid: &SparsePoint,
529 plus: bool,
530) -> SparsePoint {
531 let (e_near, sign) = if plus {
532 (&near.points.ep, 1.0)
533 } else {
534 (&near.points.em, -1.0)
535 };
536 let (c_near, c_far) = (near.cos_angle, far.cos_angle);
537
538 let mut f = e_near.scaled(1.0 - c_near + (c_far - c_near) / 3.0);
540 f.add_scaled(mid, c_near);
541 f.add_scaled(&near.points.p, -(c_far - c_near) / 3.0);
542
543 let m: isize = if plus { 0 } else { 1 };
545 f.add_scaled(&near.ring(level, m + 1), sign * 5.0 / 48.0);
546 f.add_scaled(&near.ring(level, m - 1), -sign * 5.0 / 48.0);
547 f.add_scaled(&near.ring(level, m + 2), sign / 48.0);
548 f.add_scaled(&near.ring(level, m - 2), -sign / 48.0);
549 f
550}
551
552pub(crate) fn build(level: &Level, face: usize) -> Option<GregoryTriPoints> {
556 let fv = level.face_vertices(face);
557 if fv.len() != 3 {
558 return None;
559 }
560 let fe = level.face_edges(face);
561
562 let mut corners = Vec::with_capacity(3);
563 for k in 0..3 {
564 let v = fv[k];
565 let next = fv[(k + 1) % 3];
566 let prev = fv[(k + 2) % 3];
567
568 let vertex_sharpness = level.vertex_sharpness(v as usize);
572 let inf_vertex = Crease::is_infinite(vertex_sharpness);
573 let inf_edges = level
574 .vertex_edges(v as usize)
575 .iter()
576 .filter(|&&e| Crease::is_infinite(level.edge_sharpness(e as usize)))
577 .count();
578 let inf_rule = vertex_rule(if inf_vertex { vertex_sharpness } else { 0.0 }, inf_edges);
579 let split_at_inf_sharp = inf_edges > 0 && inf_rule != Rule::Dart;
580 let span = corner_span(level, face, k, split_at_inf_sharp)?;
581
582 if span.boundary {
586 let smooth_boundary = |&e: &Index| {
587 level.is_edge_boundary(e as usize)
588 && !Crease::is_infinite(level.edge_sharpness(e as usize))
589 };
590 if [span.edges[0], span.edges[span.edges.len() - 1]]
591 .iter()
592 .any(smooth_boundary)
593 {
594 return None;
595 }
596 }
597
598 let sharp = if split_at_inf_sharp {
599 inf_rule != Rule::Crease
600 } else {
601 inf_vertex
602 };
603 let full = if span.boundary {
604 std::f32::consts::PI
605 } else {
606 std::f32::consts::TAU
607 };
608 let cos_angle = (full / span.num_faces() as f32).cos();
609
610 let points = if sharp {
611 CornerPoints {
612 p: SparsePoint::of(&[(v, 1.0)]),
613 ep: SparsePoint::of(&[(v, 0.75), (next, 0.25)]),
614 em: SparsePoint::of(&[(v, 0.75), (prev, 0.25)]),
615 child: SparsePoint::of(&[(v, 1.0)]),
616 }
617 } else if !span.boundary {
618 interior_points(level, &span)
619 } else {
620 boundary_points(level, &span)
621 };
622 corners.push(Corner {
623 span,
624 cos_angle,
625 points,
626 });
627 }
628
629 let mut mids: [SparsePoint; 3] = Default::default();
638 for (edge, mid) in mids.iter_mut().enumerate() {
639 let a = fv[edge];
640 let b = fv[(edge + 1) % 3];
641 if is_edge_singular(level, fe[edge], true) {
642 *mid = SparsePoint::of(&[(a, 0.5), (b, 0.5)]);
643 continue;
644 }
645 let ca = &corners[edge];
646 let cb = &corners[(edge + 1) % 3];
647 let mut mid_edge = SparsePoint::of(&[(a, 0.375), (b, 0.375)]);
652 mid_edge.add_scaled(&ca.ring(level, 1), 0.125);
653 mid_edge.add_scaled(&ca.ring(level, -1), 0.125);
654 let side = |corner: &Corner, near: isize, far: isize| -> SparsePoint {
658 let e = corner.span.edges[wrap(&corner.span, near)];
659 let mut child = SparsePoint::of(&[(corner.span.vertex, 0.5)]);
660 if is_edge_singular(level, e, true) {
661 child.add_scaled(&corner.ring(level, near), 0.5);
662 } else {
663 child.add(corner.span.vertex, -0.125);
664 child.add_scaled(&corner.ring(level, near), 0.375);
665 child.add_scaled(&corner.ring(level, far), 0.125);
666 child.add_scaled(&corner.ring(level, 2 * near - far), 0.125);
667 }
668 child
669 };
670 let mut limit = mid_edge.scaled(0.5);
671 for neighbor in [
672 &ca.points.child,
673 &cb.points.child,
674 &side(ca, 1, 0), &side(cb, 0, 1), &side(cb, 2, 1), &side(ca, -1, 0), ] {
679 limit.add_scaled(neighbor, 1.0 / 12.0);
680 }
681 let mut m = limit.scaled(16.0 / 6.0);
684 m.add_scaled(&ca.points.p, -1.0 / 6.0);
685 m.add_scaled(&cb.points.p, -1.0 / 6.0);
686 m.add_scaled(&ca.points.ep, -4.0 / 6.0);
687 m.add_scaled(&cb.points.em, -4.0 / 6.0);
688 *mid = m;
689 }
690
691 let mut points: GregoryTriPoints = Default::default();
692 for k in 0..3 {
693 let next = (k + 1) % 3;
694 let prev = (k + 2) % 3;
695 let c = &corners[k];
696 let span = &c.span;
697
698 let (fp, fm) = if span.boundary && span.num_faces() == 1 {
703 let f = SparsePoint::of(&[(fv[k], 0.5), (fv[next], 0.25), (fv[prev], 0.25)]);
704 (f.clone(), f)
705 } else {
706 let ep_on_wall = span.boundary && span.face_in_span == 0;
707 let em_on_wall = span.boundary && span.face_in_span + 1 == span.num_faces();
708 let fp = (!ep_on_wall).then(|| face_point(level, c, &corners[next], &mids[k], true));
709 let fm =
710 (!em_on_wall).then(|| face_point(level, c, &corners[prev], &mids[prev], false));
711 match (fp, fm) {
712 (Some(fp), Some(fm)) => (fp, fm),
713 (Some(fp), None) => (fp.clone(), fp),
714 (None, Some(fm)) => (fm.clone(), fm),
715 (None, None) => unreachable!("a span with two walls has a single face"),
716 }
717 };
718
719 points[5 * k] = c.points.p.clone();
720 points[5 * k + 1] = c.points.ep.clone();
721 points[5 * k + 2] = c.points.em.clone();
722 points[5 * k + 3] = fp;
723 points[5 * k + 4] = fm;
724 }
725 points[15..18].clone_from_slice(&mids);
726 Some(points)
727}
728
729const DIRECT_SLOTS: [((usize, usize, usize), usize); 12] = [
736 ((4, 0, 0), 0), ((3, 1, 0), 1), ((3, 0, 1), 2), ((0, 4, 0), 5), ((0, 3, 1), 6), ((1, 3, 0), 7), ((0, 0, 4), 10), ((1, 0, 3), 11), ((0, 1, 3), 12), ((2, 2, 0), 15), ((0, 2, 2), 16), ((2, 0, 2), 17), ];
749
750fn bernstein_tri(i: usize, j: usize, k: usize, u: f32, s: f32, t: f32) -> (f32, f32, f32) {
753 const FACT: [f32; 5] = [1.0, 1.0, 2.0, 6.0, 24.0];
754 let c = 24.0 / (FACT[i] * FACT[j] * FACT[k]);
755 let p = |x: f32, n: usize| x.powi(n as i32);
756 let dp = |x: f32, n: usize| if n == 0 { 0.0 } else { n as f32 * p(x, n - 1) };
757 let value = c * p(u, i) * p(s, j) * p(t, k);
758 let ds = c * (-dp(u, i) * p(s, j) * p(t, k) + p(u, i) * dp(s, j) * p(t, k));
759 let dt = c * (-dp(u, i) * p(s, j) * p(t, k) + p(u, i) * p(s, j) * dp(t, k));
760 (value, ds, dt)
761}
762
763pub(crate) fn evaluate_basis(s: f32, t: f32) -> ([f32; 18], [f32; 18], [f32; 18]) {
766 let u = 1.0 - s - t;
767 let mut w = [0.0f32; 18];
768 let mut ws = [0.0f32; 18];
769 let mut wt = [0.0f32; 18];
770
771 for &((i, j, k), point) in &DIRECT_SLOTS {
772 let (b, bs, bt) = bernstein_tri(i, j, k, u, s, t);
773 w[point] += b;
774 ws[point] += bs;
775 wt[point] += bt;
776 }
777
778 struct InteriorSlot {
785 ijk: (usize, usize, usize),
786 p: usize,
787 q: usize,
788 x: f32,
789 y: f32,
790 x_grad: [f32; 2],
791 y_grad: [f32; 2],
792 }
793 let interior = [
794 InteriorSlot {
795 ijk: (2, 1, 1),
796 p: 3,
797 q: 4,
798 x: s,
799 y: t,
800 x_grad: [1.0, 0.0],
801 y_grad: [0.0, 1.0],
802 },
803 InteriorSlot {
804 ijk: (1, 2, 1),
805 p: 8,
806 q: 9,
807 x: t,
808 y: u,
809 x_grad: [0.0, 1.0],
810 y_grad: [-1.0, -1.0],
811 },
812 InteriorSlot {
813 ijk: (1, 1, 2),
814 p: 13,
815 q: 14,
816 x: u,
817 y: s,
818 x_grad: [-1.0, -1.0],
819 y_grad: [1.0, 0.0],
820 },
821 ];
822 for slot in &interior {
823 let (i, j, k) = slot.ijk;
824 let (b, b_ds, b_dt) = bernstein_tri(i, j, k, u, s, t);
825 let d = slot.x + slot.y;
826 if d < 1e-5 {
827 w[slot.p] += 0.5 * b;
830 w[slot.q] += 0.5 * b;
831 ws[slot.p] += 0.5 * b_ds;
832 ws[slot.q] += 0.5 * b_ds;
833 wt[slot.p] += 0.5 * b_dt;
834 wt[slot.q] += 0.5 * b_dt;
835 continue;
836 }
837 let wp = slot.x / d;
838 let wq = slot.y / d;
839 w[slot.p] += b * wp;
840 w[slot.q] += b * wq;
841 let apply = |arr: &mut [f32; 18], bd: f32, axis: usize| {
842 let d_sum = slot.x_grad[axis] + slot.y_grad[axis];
843 let dwp = (slot.x_grad[axis] - wp * d_sum) / d;
844 let dwq = (slot.y_grad[axis] - wq * d_sum) / d;
845 arr[slot.p] += bd * wp + b * dwp;
846 arr[slot.q] += bd * wq + b * dwq;
847 };
848 apply(&mut ws, b_ds, 0);
849 apply(&mut wt, b_dt, 1);
850 }
851 (w, ws, wt)
852}
853
854#[cfg(test)]
855mod tests {
856 use super::*;
857
858 #[test]
859 fn box_spline_basis_is_a_partition_of_unity_with_limit_masks() {
860 for &(s, t) in &[(0.0f32, 0.0f32), (0.3, 0.2), (0.5, 0.5), (0.1, 0.85)] {
861 let (w, ws, wt) = box_spline_basis(s, t);
862 assert!((w.iter().sum::<f32>() - 1.0).abs() < 1e-6);
863 assert!(ws.iter().sum::<f32>().abs() < 1e-6);
864 assert!(wt.iter().sum::<f32>().abs() < 1e-6);
865 }
866 let (w, ws, _) = box_spline_basis(0.0, 0.0);
869 assert!((w[4] - 0.5).abs() < 1e-6);
870 for &slot in &RING_SLOTS[0] {
871 assert!((w[slot] - 1.0 / 12.0).abs() < 1e-6, "slot {slot}");
872 }
873 for (m, &slot) in RING_SLOTS[0].iter().enumerate() {
876 let expected = (m as f32 * std::f32::consts::FRAC_PI_3).cos() / 3.0;
877 assert!((ws[slot] - expected).abs() < 1e-6, "slot {slot}");
878 }
879 }
880
881 #[test]
882 fn slot_layout_is_consistent() {
883 let dirs = [(1, 0), (0, 1), (-1, 1), (-1, 0), (0, -1), (1, -1)];
887 for corner in 0..3 {
888 let (cx, cy) = SLOT_POSITIONS[[4, 5, 8][corner]];
889 for (m, &slot) in RING_SLOTS[corner].iter().enumerate() {
890 let (x, y) = SLOT_POSITIONS[slot];
891 let dir = dirs[(m + 2 * corner) % 6];
892 assert_eq!((x - cx, y - cy), dir, "corner {corner} ring {m}");
893 }
894 }
895 for (slot, &(x, y)) in SLOT_POSITIONS.iter().enumerate() {
899 let beyond_edge = [y < 0, x + y > 1, x < 0];
900 for (edge, slots) in EDGE_WALL_SLOTS.iter().enumerate() {
901 assert_eq!(
902 slots.contains(&slot),
903 beyond_edge[edge],
904 "edge {edge} slot {slot}"
905 );
906 }
907 let beyond_corner = [x + y < 0, x > 1, y > 1];
908 for (corner, slots) in VERTEX_WALL_SLOTS.iter().enumerate() {
909 assert_eq!(
910 slots.contains(&slot),
911 beyond_corner[corner],
912 "corner {corner} slot {slot}"
913 );
914 }
915 }
916 let patterns: Vec<Vec<usize>> = vec![
920 EDGE_WALL_SLOTS[0].to_vec(),
921 EDGE_WALL_SLOTS[1].to_vec(),
922 EDGE_WALL_SLOTS[2].to_vec(),
923 VERTEX_WALL_SLOTS[0].to_vec(),
924 VERTEX_WALL_SLOTS[1].to_vec(),
925 VERTEX_WALL_SLOTS[2].to_vec(),
926 [EDGE_WALL_SLOTS[0], EDGE_WALL_SLOTS[1]].concat(),
927 [EDGE_WALL_SLOTS[1], EDGE_WALL_SLOTS[2]].concat(),
928 [EDGE_WALL_SLOTS[2], EDGE_WALL_SLOTS[0]].concat(),
929 EDGE_WALL_SLOTS.concat(),
930 [&VERTEX_WALL_SLOTS[0][..], &EDGE_WALL_SLOTS[1][..]].concat(),
931 ];
932 for pattern in patterns {
933 let mut cvs = [0 as Index; 12];
934 for &slot in &pattern {
935 cvs[slot] = INDEX_INVALID;
936 }
937 for &slot in &pattern {
938 let rule = phantom_rule(&cvs, slot).unwrap_or_else(|| panic!("{pattern:?} {slot}"));
939 assert!(
940 rule.iter().all(|&(t, _)| cvs[t] != INDEX_INVALID),
941 "{pattern:?} {slot}"
942 );
943 assert!((rule.iter().map(|&(_, f)| f).sum::<f32>() - 1.0).abs() < 1e-6);
944 }
945 let mut weights = [1.0f32; 12];
946 fold_phantom_weights(&cvs, &mut weights);
947 assert!((weights.iter().sum::<f32>() - 12.0).abs() < 1e-5);
948 }
949 }
950
951 #[test]
952 fn gregory_tri_basis_is_a_partition_of_unity() {
953 for &(s, t) in &[
954 (0.0f32, 0.0f32),
955 (0.3, 0.2),
956 (0.5, 0.5),
957 (0.0, 1.0),
958 (0.25, 0.7),
959 ] {
960 let (w, ws, wt) = evaluate_basis(s, t);
961 assert!((w.iter().sum::<f32>() - 1.0).abs() < 1e-5, "({s},{t})");
962 assert!(ws.iter().sum::<f32>().abs() < 1e-4, "({s},{t})");
963 assert!(wt.iter().sum::<f32>().abs() < 1e-4, "({s},{t})");
964 }
965 assert!((evaluate_basis(0.0, 0.0).0[0] - 1.0).abs() < 1e-6);
967 assert!((evaluate_basis(1.0, 0.0).0[5] - 1.0).abs() < 1e-6);
968 assert!((evaluate_basis(0.0, 1.0).0[10] - 1.0).abs() < 1e-6);
969 }
970
971 use crate::far::{
972 PatchMap, PatchTable, PatchTableFactory, PatchType, PrimvarRefiner, TopologyDescriptor,
973 TopologyRefiner, TopologyRefinerFactory, UniformOptions,
974 };
975 use crate::sdc;
976
977 fn jittered_tri_grid(w: u32, h: u32) -> (Vec<usize>, Vec<u32>, Vec<[f32; 3]>) {
981 let mut seed = 0x12345678u32;
982 let mut rand = move || {
983 seed = seed.wrapping_mul(1664525).wrapping_add(1013904223);
984 (seed >> 8) as f32 / (1u32 << 24) as f32
985 };
986 let positions = (0..w * h)
987 .map(|k| {
988 [
989 (k % w) as f32 + rand() * 0.4,
990 (k / w) as f32 + rand() * 0.4,
991 rand(),
992 ]
993 })
994 .collect();
995 let mut verts_per_face = Vec::new();
996 let mut face_verts = Vec::new();
997 for j in 0..h - 1 {
998 for i in 0..w - 1 {
999 let v = j * w + i;
1000 verts_per_face.push(3usize);
1001 face_verts.extend_from_slice(&[v, v + 1, v + w + 1]);
1002 verts_per_face.push(3usize);
1003 face_verts.extend_from_slice(&[v, v + w + 1, v + w]);
1004 }
1005 }
1006 (verts_per_face, face_verts, positions)
1007 }
1008
1009 fn assert_gregory_matches_box_spline_patches(
1017 refiner: &TopologyRefiner,
1018 table: &PatchTable,
1019 positions: &[[f32; 3]],
1020 ) -> usize {
1021 assert_eq!(refiner.max_level(), 0, "oracle expects base-level patches");
1022 let level = refiner.level(0).inner();
1023 let samples = [
1024 (0.0f32, 0.0f32),
1025 (1.0, 0.0),
1026 (0.0, 1.0),
1027 (0.5, 0.5),
1028 (0.15, 0.6),
1029 (0.7, 0.2),
1030 (0.35, 0.05),
1031 (0.3, 0.3),
1032 ];
1033 let mut compared = 0;
1034 for patch in 0..table.num_patches() {
1035 if table.patch_type(patch) != PatchType::Loop {
1036 continue;
1037 }
1038 let face = table.patch_face(patch) as usize;
1039 assert_eq!(table.patch_param(patch).depth, 0);
1040 let points = build(level, face).expect("every sharpened triangle builds");
1041 for &(s, t) in &samples {
1042 let (w, ws, wt) = evaluate_basis(s, t);
1043 let mut g = [[0.0f32; 3]; 3];
1044 for (pt, stencil) in points.iter().enumerate() {
1045 for &(cv, sw) in &stencil.0 {
1046 for c in 0..3 {
1047 g[0][c] += w[pt] * sw * positions[cv as usize][c];
1048 g[1][c] += ws[pt] * sw * positions[cv as usize][c];
1049 g[2][c] += wt[pt] * sw * positions[cv as usize][c];
1050 }
1051 }
1052 }
1053 let (bp, bdu, bdv) = table.evaluate(patch, s, t, positions);
1054 for c in 0..3 {
1055 assert!(
1056 (g[0][c] - bp[c]).abs() < 2e-4,
1057 "face {face}: position mismatch at ({s},{t}): gregory {:?} vs box spline {:?}",
1058 g[0],
1059 bp
1060 );
1061 assert!(
1062 (g[1][c] - bdu[c]).abs() < 2e-3,
1063 "face {face}: du mismatch at ({s},{t}): gregory {:?} vs box spline {:?}",
1064 g[1],
1065 bdu
1066 );
1067 assert!(
1068 (g[2][c] - bdv[c]).abs() < 2e-3,
1069 "face {face}: dv mismatch at ({s},{t}): gregory {:?} vs box spline {:?}",
1070 g[2],
1071 bdv
1072 );
1073 }
1074 }
1075 compared += 1;
1076 }
1077 compared
1078 }
1079
1080 #[test]
1081 fn gregory_triangle_reproduces_box_spline_on_regular_faces() {
1082 let (verts_per_face, face_verts, positions) = jittered_tri_grid(6, 5);
1086 let options = sdc::Options::default()
1087 .with_vtx_boundary_interpolation(sdc::VtxBoundaryInterpolation::EdgeAndCorner);
1088 let descriptor = TopologyDescriptor::new(30, &verts_per_face, &face_verts);
1089 let refiner =
1090 TopologyRefinerFactory::create(descriptor, sdc::SchemeType::Loop, options).unwrap();
1091 let table = PatchTableFactory::create(&refiner).unwrap();
1092 assert_eq!(
1093 assert_gregory_matches_box_spline_patches(&refiner, &table, &positions),
1094 36
1095 );
1096 }
1097
1098 #[test]
1099 fn gregory_triangle_reproduces_box_spline_along_infinitely_sharp_creases() {
1100 let (verts_per_face, face_verts, positions) = jittered_tri_grid(7, 7);
1106 let mut creases = Vec::new();
1107 for i in 0..6u32 {
1108 creases.push([21 + i, 22 + i]); }
1110 for j in 0..6u32 {
1111 creases.push([3 + 7 * j, 10 + 7 * j]); }
1113 let weights = vec![sdc::SHARPNESS_INFINITE; creases.len()];
1114 let options = sdc::Options::default()
1115 .with_vtx_boundary_interpolation(sdc::VtxBoundaryInterpolation::EdgeAndCorner);
1116 let descriptor = TopologyDescriptor::new(49, &verts_per_face, &face_verts)
1117 .with_creases(&creases, &weights);
1118 let refiner =
1119 TopologyRefinerFactory::create(descriptor, sdc::SchemeType::Loop, options).unwrap();
1120 let table = PatchTableFactory::create(&refiner).unwrap();
1121 assert_eq!(
1127 assert_gregory_matches_box_spline_patches(&refiner, &table, &positions),
1128 72 - 16
1129 );
1130 }
1131
1132 fn fan(n: u32) -> (Vec<usize>, Vec<u32>, Vec<[f32; 3]>) {
1135 let mut faces = Vec::new();
1136 let r = |i: u32| 1 + i % n;
1137 let o = |i: u32| 1 + n + i % (2 * n);
1138 for i in 0..n {
1139 faces.extend_from_slice(&[0, r(i), r(i + 1)]);
1140 faces.extend_from_slice(&[r(i), o(2 * i), o(2 * i + 1)]);
1141 faces.extend_from_slice(&[r(i), o(2 * i + 1), r(i + 1)]);
1142 faces.extend_from_slice(&[r(i + 1), o(2 * i + 1), o(2 * i + 2)]);
1143 }
1144 let mut pos = vec![[0.0, 0.0, 1.0f32]];
1145 let sph =
1146 |polar: f32, az: f32| [polar.sin() * az.cos(), polar.sin() * az.sin(), polar.cos()];
1147 for i in 0..n {
1148 pos.push(sph(0.7, std::f32::consts::TAU * i as f32 / n as f32));
1149 }
1150 for i in 0..2 * n {
1151 let az = std::f32::consts::TAU * (i as f32 + 0.5) / (2.0 * n as f32);
1152 pos.push(sph(1.4, az));
1153 }
1154 (vec![3; faces.len() / 3], faces, pos)
1155 }
1156
1157 fn half_fan(k: u32) -> (Vec<usize>, Vec<u32>, Vec<[f32; 3]>) {
1160 let mut faces = Vec::new();
1161 let r = |i: u32| 1 + i;
1162 let o = |i: u32| 2 + k + i;
1163 for i in 0..k {
1164 faces.extend_from_slice(&[0, r(i), r(i + 1)]);
1165 faces.extend_from_slice(&[r(i), o(2 * i), o(2 * i + 1)]);
1166 faces.extend_from_slice(&[r(i), o(2 * i + 1), r(i + 1)]);
1167 faces.extend_from_slice(&[r(i + 1), o(2 * i + 1), o(2 * i + 2)]);
1168 }
1169 let mut pos = vec![[0.0, 0.0, 1.0f32]];
1170 let sph =
1171 |polar: f32, az: f32| [polar.sin() * az.cos(), polar.sin() * az.sin(), polar.cos()];
1172 for i in 0..=k {
1173 pos.push(sph(0.7, std::f32::consts::PI * i as f32 / k as f32));
1174 }
1175 for i in 0..=2 * k {
1176 pos.push(sph(1.4, std::f32::consts::PI * i as f32 / (2.0 * k as f32)));
1177 }
1178 (vec![3; faces.len() / 3], faces, pos)
1179 }
1180
1181 fn cap_error(
1185 verts_per_face: &[usize],
1186 face_verts: &[u32],
1187 positions: &[[f32; 3]],
1188 num_faces: usize,
1189 ) -> f32 {
1190 let descriptor = TopologyDescriptor::new(positions.len(), verts_per_face, face_verts);
1191 let build = |levels: usize| {
1192 let mut refiner = TopologyRefinerFactory::create(
1193 descriptor,
1194 sdc::SchemeType::Loop,
1195 sdc::Options::default(),
1196 )
1197 .unwrap();
1198 refiner.refine_uniform(UniformOptions::new(levels));
1199 let mut controls = positions.to_vec();
1200 for level in PrimvarRefiner::new(&refiner).interpolate_all(positions) {
1201 controls.extend(level);
1202 }
1203 (PatchTableFactory::create(&refiner).unwrap(), controls)
1204 };
1205 let (coarse, coarse_controls) = build(1);
1206 let (fine, fine_controls) = build(5);
1207 let (coarse_map, fine_map) = (PatchMap::new(&coarse), PatchMap::new(&fine));
1208 let mut max = 0.0f32;
1209 let n = 24;
1210 for ptex in 0..num_faces {
1211 for i in 0..=n {
1212 for j in 0..=(n - i) {
1213 let (u, v) = (i as f32 / n as f32, j as f32 / n as f32);
1214 let a = coarse_map.find_patch(ptex, u, v).unwrap();
1215 let b = fine_map.find_patch(ptex, u, v).unwrap();
1216 let (pa, _, _) = coarse.evaluate(a, u, v, &coarse_controls);
1217 let (pb, _, _) = fine.evaluate(b, u, v, &fine_controls);
1218 let d: f32 = (0..3).map(|c| (pa[c] - pb[c]).powi(2)).sum::<f32>().sqrt();
1219 max = max.max(d);
1220 }
1221 }
1222 }
1223 max
1224 }
1225
1226 #[test]
1227 fn caps_stay_close_to_the_limit_surface_at_extraordinary_vertices() {
1228 for n in [3u32, 4, 5, 7, 8, 10, 12] {
1233 let (verts_per_face, face_verts, positions) = fan(n);
1234 let error = cap_error(&verts_per_face, &face_verts, &positions, n as usize);
1235 assert!(error < 0.011, "valence {n}: cap error {error}");
1236 }
1237 for k in [1u32, 2, 3, 4, 5, 6] {
1240 let (verts_per_face, face_verts, positions) = half_fan(k);
1241 let error = cap_error(&verts_per_face, &face_verts, &positions, k as usize);
1242 let bound = if k == 1 || k == 3 { 1e-4 } else { 0.018 };
1243 assert!(error < bound, "{k} faces: cap error {error}");
1244 }
1245 }
1246}