use crate::sdc::{self, Crease, Rule};
use crate::vtr::Level;
use crate::Index;
#[derive(Debug, Clone, Default)]
pub(crate) struct SparsePoint(pub(crate) Vec<(Index, f32)>);
impl SparsePoint {
pub(super) fn of(entries: &[(Index, f32)]) -> SparsePoint {
let mut p = SparsePoint::default();
for &(i, w) in entries {
p.add(i, w);
}
p
}
pub(super) fn add(&mut self, index: Index, weight: f32) {
match self.0.iter_mut().find(|(i, _)| *i == index) {
Some((_, w)) => *w += weight,
None => self.0.push((index, weight)),
}
}
pub(super) fn add_scaled(&mut self, other: &SparsePoint, scale: f32) {
for &(i, w) in &other.0 {
self.add(i, w * scale);
}
}
pub(super) fn scaled(&self, scale: f32) -> SparsePoint {
SparsePoint(self.0.iter().map(|&(i, w)| (i, w * scale)).collect())
}
}
pub(crate) const NUM_POINTS: usize = 20;
pub(crate) type GregoryPoints = [SparsePoint; NUM_POINTS];
pub(super) fn is_edge_singular(level: &Level, edge: Index, inf_sharp: bool) -> bool {
let e = edge as usize;
level.edge_faces(e).len() != 2 || (inf_sharp && Crease::is_infinite(level.edge_sharpness(e)))
}
pub(super) struct CornerSpan {
pub(super) vertex: Index,
pub(super) edges: Vec<Index>,
pub(super) faces: Vec<Index>,
pub(super) face_in_span: usize,
pub(super) boundary: bool,
}
impl CornerSpan {
pub(super) fn num_faces(&self) -> usize {
self.faces.len()
}
fn valence(&self) -> usize {
self.edges.len()
}
pub(super) fn edge_end(&self, level: &Level, i: usize) -> Index {
level.edge_opposite_vertex(self.edges[i] as usize, self.vertex)
}
fn diagonal(&self, level: &Level, i: usize) -> Index {
let fv = level.face_vertices(self.faces[i] as usize);
debug_assert_eq!(fv.len(), 4);
let k = fv
.iter()
.position(|&v| v == self.vertex)
.expect("span faces are incident the corner vertex");
fv[(k + 2) % 4]
}
}
fn other_face_of_edge(level: &Level, edge: Index, face: Index) -> Option<Index> {
let faces = level.edge_faces(edge as usize);
if faces.len() != 2 {
return None;
}
Some(if faces[0] == face { faces[1] } else { faces[0] })
}
fn other_edge_at_vertex(level: &Level, face: Index, vertex: Index, edge: Index) -> Option<Index> {
let fv = level.face_vertices(face as usize);
let fe = level.face_edges(face as usize);
let n = fv.len();
let i = fv.iter().position(|&x| x == vertex)?;
let leading = fe[i];
let trailing = fe[(i + n - 1) % n];
if leading == edge {
Some(trailing)
} else if trailing == edge {
Some(leading)
} else {
None
}
}
pub(super) fn corner_span(
level: &Level,
face: usize,
corner: usize,
inf_sharp_singular: bool,
) -> Option<CornerSpan> {
let fv = level.face_vertices(face);
let fe = level.face_edges(face);
let vertex = fv[corner];
let size = fv.len();
let num_faces = level.vertex_faces(vertex as usize).len();
let singular = |e: Index| is_edge_singular(level, e, inf_sharp_singular);
let face = face as Index;
let e_lead = fe[corner];
let mut start_face = face;
let mut start_edge = e_lead;
let mut periodic = false;
let mut steps = 0;
loop {
if singular(start_edge) {
break;
}
let next = other_face_of_edge(level, start_edge, start_face)?;
if next == face {
periodic = true;
break;
}
if level.face_vertices(next as usize).len() != size {
return None;
}
start_edge = other_edge_at_vertex(level, next, vertex, start_edge)?;
start_face = next;
steps += 1;
if steps > num_faces {
return None;
}
}
if periodic {
start_face = face;
start_edge = e_lead;
}
let mut edges = vec![start_edge];
let mut faces = vec![start_face];
let mut current_face = start_face;
let mut current_edge = other_edge_at_vertex(level, start_face, vertex, start_edge)?;
loop {
if periodic && current_edge == e_lead {
break;
}
if !periodic && singular(current_edge) {
edges.push(current_edge);
break;
}
edges.push(current_edge);
let next = other_face_of_edge(level, current_edge, current_face)?;
if level.face_vertices(next as usize).len() != size {
return None;
}
faces.push(next);
current_edge = other_edge_at_vertex(level, next, vertex, current_edge)?;
current_face = next;
if faces.len() > num_faces {
return None;
}
}
let face_in_span = faces.iter().position(|&f| f == face)?;
Some(CornerSpan {
vertex,
edges,
faces,
face_in_span,
boundary: !periodic,
})
}
pub(super) fn vertex_rule(vertex_sharpness: f32, sharp_edges: usize) -> Rule {
Crease::new(sdc::Options::default()).determine_vertex_vertex_rule(vertex_sharpness, sharp_edges)
}
fn edge_factor(valence: usize) -> f32 {
let inv = 1.0 / valence as f64;
let cos_t = (2.0 * std::f64::consts::PI * inv).cos();
let divisor = (cos_t + 5.0) + ((cos_t + 9.0) * (cos_t + 1.0)).sqrt();
(16.0 * inv / divisor) as f32
}
fn interior_points(level: &Level, span: &CornerSpan) -> (SparsePoint, SparsePoint, SparsePoint) {
let n = span.valence();
let nf = n as f32;
let p_coeff = 1.0 / (nf * (nf + 5.0));
let mut p = SparsePoint::of(&[(span.vertex, nf / (nf + 5.0))]);
for i in 0..n {
p.add(span.edge_end(level, i), 4.0 * p_coeff);
p.add(span.diagonal(level, i), p_coeff);
}
let tan_coeff = edge_factor(n) * 0.5 / (nf + 5.0);
let theta = std::f32::consts::TAU / nf;
let tangent = |j: usize| -> SparsePoint {
let mut t = SparsePoint::default();
for i in 0..n {
let a = (i as f32 - j as f32) * theta;
t.add(
span.edge_end(level, i),
tan_coeff * (2.0 * (a + theta).cos() + 4.0 * a.cos() + 2.0 * (a - theta).cos()),
);
t.add(
span.diagonal(level, i),
tan_coeff * (a.cos() + (a + theta).cos()),
);
}
t
};
let mut ep = p.clone();
ep.add_scaled(&tangent(0), 1.0);
let mut em = p.clone();
em.add_scaled(&tangent(1), 1.0);
(p, ep, em)
}
fn boundary_points(level: &Level, span: &CornerSpan) -> (SparsePoint, SparsePoint, SparsePoint) {
let k = span.num_faces();
debug_assert!(span.boundary && k > 1);
let v = span.vertex;
let e0 = span.edge_end(level, 0);
let ek = span.edge_end(level, k);
let p = SparsePoint::of(&[(v, 4.0 / 6.0), (e0, 1.0 / 6.0), (ek, 1.0 / 6.0)]);
let t_boundary = SparsePoint::of(&[(e0, 1.0 / 6.0), (ek, -1.0 / 6.0)]);
let kf = k as f32;
let theta = std::f32::consts::PI / kf;
let c = theta.cos();
let s = theta.sin();
let div3 = 1.0 / 3.0;
let div3kc = 1.0 / (3.0 * kf + c);
let gamma = -4.0 * s * div3kc;
let alpha_0k = -((1.0 + 2.0 * c) * (1.0 + c).sqrt()) * div3kc / (1.0 - c).sqrt();
let beta_0 = s * div3kc;
let mut t_interior = SparsePoint::of(&[
(v, gamma * div3),
(e0, alpha_0k * div3),
(ek, alpha_0k * div3),
(span.diagonal(level, 0), beta_0 * div3),
]);
for i in 1..k {
let sin_i = (theta * i as f32).sin();
let sin_i1 = (theta * (i + 1) as f32).sin();
t_interior.add(span.edge_end(level, i), 4.0 * sin_i * div3kc * div3);
t_interior.add(span.diagonal(level, i), (sin_i + sin_i1) * div3kc * div3);
}
let along = |angle: f32| -> SparsePoint {
let mut e = p.clone();
e.add_scaled(&t_boundary, angle.cos());
e.add_scaled(&t_interior, angle.sin());
e
};
let f = span.face_in_span;
let ep = if f == 0 {
SparsePoint::of(&[(v, 2.0 / 3.0), (e0, 1.0 / 3.0)])
} else {
along(theta * f as f32)
};
let em = if f + 1 == k {
SparsePoint::of(&[(v, 2.0 / 3.0), (ek, 1.0 / 3.0)])
} else {
along(theta * (f + 1) as f32)
};
(p, ep, em)
}
struct Corner {
span: CornerSpan,
regular: bool,
cos_angle: f32,
ep_on_boundary: bool,
em_on_boundary: bool,
p: SparsePoint,
ep: SparsePoint,
em: SparsePoint,
}
fn irregular_face_point(level: &Level, near: &Corner, far: &Corner, plus: bool) -> SparsePoint {
let (e_near, e_far, edge, sign) = if plus {
(&near.ep, &far.em, near.span.face_in_span, 1.0)
} else {
(&near.em, &far.ep, near.span.face_in_span + 1, -1.0)
};
let cos_near = near.cos_angle;
let cos_far = far.cos_angle;
let mut f = near.p.scaled(cos_far / 3.0);
f.add_scaled(e_near, (3.0 - 2.0 * cos_near - cos_far) / 3.0);
f.add_scaled(e_far, 2.0 * cos_near / 3.0);
let span = &near.span;
let valence = span.valence();
let prev = (edge + valence - 1) % valence;
let next = (edge + 1) % valence;
debug_assert!(prev < span.num_faces() && edge < span.num_faces());
f.add(span.edge_end(level, prev), -sign / 9.0);
f.add(span.diagonal(level, prev), -sign / 18.0);
f.add(span.diagonal(level, edge), sign / 18.0);
f.add(span.edge_end(level, next), sign / 9.0);
f
}
pub(crate) fn build(level: &Level, face: usize) -> Option<GregoryPoints> {
let fv = level.face_vertices(face);
if fv.len() != 4 {
return None;
}
let mut corners = Vec::with_capacity(4);
for k in 0..4 {
let v = fv[k];
let next = fv[(k + 1) % 4];
let prev = fv[(k + 3) % 4];
let vertex_sharpness = level.vertex_sharpness(v as usize);
let inf_vertex = Crease::is_infinite(vertex_sharpness);
let inf_edges = level
.vertex_edges(v as usize)
.iter()
.filter(|&&e| Crease::is_infinite(level.edge_sharpness(e as usize)))
.count();
let inf_rule = vertex_rule(if inf_vertex { vertex_sharpness } else { 0.0 }, inf_edges);
let split_at_inf_sharp = inf_edges > 0 && inf_rule != Rule::Dart;
let span = corner_span(level, face, k, split_at_inf_sharp)?;
if span.boundary {
let smooth_boundary = |&e: &Index| {
level.is_edge_boundary(e as usize)
&& !Crease::is_infinite(level.edge_sharpness(e as usize))
};
if [span.edges[0], span.edges[span.valence() - 1]]
.iter()
.any(smooth_boundary)
{
return None;
}
}
let sharp = if split_at_inf_sharp {
inf_rule != Rule::Crease
} else {
inf_vertex
};
let num_faces = span.num_faces();
let boundary = span.boundary;
let regular = !sharp && (num_faces << (boundary as usize)) == 4;
let cos_angle = if regular {
0.0
} else {
let full = if boundary {
std::f32::consts::PI
} else {
std::f32::consts::TAU
};
(full / num_faces as f32).cos()
};
let f = span.face_in_span;
let ep_on_boundary = boundary && f == 0;
let em_on_boundary = boundary && f + 1 == num_faces;
let (p, ep, em) = if sharp {
(
SparsePoint::of(&[(v, 1.0)]),
SparsePoint::of(&[(v, 2.0 / 3.0), (next, 1.0 / 3.0)]),
SparsePoint::of(&[(v, 2.0 / 3.0), (prev, 1.0 / 3.0)]),
)
} else if !boundary {
interior_points(level, &span)
} else if num_faces > 1 {
boundary_points(level, &span)
} else {
(
SparsePoint::of(&[(v, 4.0 / 6.0), (next, 1.0 / 6.0), (prev, 1.0 / 6.0)]),
SparsePoint::of(&[(v, 2.0 / 3.0), (next, 1.0 / 3.0)]),
SparsePoint::of(&[(v, 2.0 / 3.0), (prev, 1.0 / 3.0)]),
)
};
corners.push(Corner {
span,
regular,
cos_angle,
ep_on_boundary,
em_on_boundary,
p,
ep,
em,
});
}
let regular_face_point = |k: usize| -> SparsePoint {
SparsePoint::of(&[
(fv[k], 4.0 / 9.0),
(fv[(k + 3) % 4], 2.0 / 9.0),
(fv[(k + 1) % 4], 2.0 / 9.0),
(fv[(k + 2) % 4], 1.0 / 9.0),
])
};
let mut points: GregoryPoints = Default::default();
for k in 0..4 {
let next = (k + 1) % 4;
let prev = (k + 3) % 4;
let c = &corners[k];
let mut fp_regular = c.regular && corners[next].regular;
let mut fm_regular = c.regular && corners[prev].regular;
let mut fp_copied = false;
let mut fm_copied = false;
if c.span.boundary {
if c.span.num_faces() > 1 {
if c.ep_on_boundary {
fp_regular = fm_regular;
fp_copied = !fp_regular;
}
if c.em_on_boundary {
fm_regular = fp_regular;
fm_copied = !fm_regular;
}
} else {
fp_regular = true;
fm_regular = true;
}
}
let fp = if fp_regular {
regular_face_point(k)
} else if fp_copied {
SparsePoint::default()
} else {
irregular_face_point(level, c, &corners[next], true)
};
let fm = if fm_regular {
regular_face_point(k)
} else if fm_copied {
SparsePoint::default()
} else {
irregular_face_point(level, c, &corners[prev], false)
};
let (fp, fm) = if fp_copied {
(fm.clone(), fm)
} else if fm_copied {
(fp.clone(), fp)
} else {
(fp, fm)
};
points[5 * k] = c.p.clone();
points[5 * k + 1] = c.ep.clone();
points[5 * k + 2] = c.em.clone();
points[5 * k + 3] = fp;
points[5 * k + 4] = fm;
}
Some(points)
}
fn bernstein(t: f32) -> ([f32; 4], [f32; 4]) {
let s = 1.0 - t;
let basis = [s * s * s, 3.0 * t * s * s, 3.0 * t * t * s, t * t * t];
let deriv = [
-3.0 * s * s,
3.0 * s * s - 6.0 * t * s,
6.0 * t * s - 3.0 * t * t,
3.0 * t * t,
];
(basis, deriv)
}
const DIRECT_SLOTS: [(usize, usize, usize); 12] = [
(0, 0, 0), (3, 0, 5), (3, 3, 10), (0, 3, 15), (1, 0, 1), (0, 1, 2), (3, 1, 6), (2, 0, 7), (2, 3, 11), (3, 2, 12), (0, 2, 16), (1, 3, 17), ];
pub(crate) fn evaluate_basis(s: f32, t: f32) -> ([f32; 20], [f32; 20], [f32; 20]) {
let (bs, dbs) = bernstein(s);
let (bt, dbt) = bernstein(t);
let mut w = [0.0f32; 20];
let mut ws = [0.0f32; 20];
let mut wt = [0.0f32; 20];
for &(i, j, point) in &DIRECT_SLOTS {
w[point] += bs[i] * bt[j];
ws[point] += dbs[i] * bt[j];
wt[point] += bs[i] * dbt[j];
}
struct InteriorSlot {
i: usize,
j: usize,
p: usize, q: usize, x: fn(f32, f32) -> f32,
y: fn(f32, f32) -> f32,
x_grad: [f32; 2],
y_grad: [f32; 2],
}
let interior = [
InteriorSlot {
i: 1,
j: 1,
p: 3,
q: 4,
x: |s, _| s,
y: |_, t| t,
x_grad: [1.0, 0.0],
y_grad: [0.0, 1.0],
},
InteriorSlot {
i: 2,
j: 1,
p: 9,
q: 8,
x: |s, _| 1.0 - s,
y: |_, t| t,
x_grad: [-1.0, 0.0],
y_grad: [0.0, 1.0],
},
InteriorSlot {
i: 2,
j: 2,
p: 13,
q: 14,
x: |s, _| 1.0 - s,
y: |_, t| 1.0 - t,
x_grad: [-1.0, 0.0],
y_grad: [0.0, -1.0],
},
InteriorSlot {
i: 1,
j: 2,
p: 19,
q: 18,
x: |s, _| s,
y: |_, t| 1.0 - t,
x_grad: [1.0, 0.0],
y_grad: [0.0, -1.0],
},
];
for slot in &interior {
let x = (slot.x)(s, t);
let y = (slot.y)(s, t);
let d = x + y;
let b = bs[slot.i] * bt[slot.j];
let b_ds = dbs[slot.i] * bt[slot.j];
let b_dt = bs[slot.i] * dbt[slot.j];
if d < 1e-5 {
w[slot.p] += 0.5 * b;
w[slot.q] += 0.5 * b;
ws[slot.p] += 0.5 * b_ds;
ws[slot.q] += 0.5 * b_ds;
wt[slot.p] += 0.5 * b_dt;
wt[slot.q] += 0.5 * b_dt;
continue;
}
let wp = x / d;
let wq = y / d;
w[slot.p] += b * wp;
w[slot.q] += b * wq;
let apply = |arr: &mut [f32; 20], bd: f32, axis: usize| {
let d_sum = slot.x_grad[axis] + slot.y_grad[axis];
let dwp = (slot.x_grad[axis] - wp * d_sum) / d;
let dwq = (slot.y_grad[axis] - wq * d_sum) / d;
arr[slot.p] += bd * wp + b * dwp;
arr[slot.q] += bd * wq + b * dwq;
};
apply(&mut ws, b_ds, 0);
apply(&mut wt, b_dt, 1);
}
(w, ws, wt)
}
#[cfg(test)]
mod tests {
use super::*;
use crate::far::{
PatchTable, PatchTableFactory, PatchType, TopologyDescriptor, TopologyRefiner,
TopologyRefinerFactory,
};
use crate::sdc;
fn jittered_grid(w: usize, h: usize) -> Vec<[f32; 3]> {
let mut seed = 0x12345678u32;
let mut rand = move || {
seed = seed.wrapping_mul(1664525).wrapping_add(1013904223);
(seed >> 8) as f32 / (1u32 << 24) as f32
};
(0..w * h)
.map(|k| {
[
(k % w) as f32 + rand() * 0.4,
(k / w) as f32 + rand() * 0.4,
rand(),
]
})
.collect()
}
fn grid_faces(w: u32, h: u32) -> (Vec<usize>, Vec<u32>) {
let mut verts_per_face = Vec::new();
let mut face_verts = Vec::new();
for j in 0..h - 1 {
for i in 0..w - 1 {
verts_per_face.push(4usize);
let v = j * w + i;
face_verts.extend_from_slice(&[v, v + 1, v + w + 1, v + w]);
}
}
(verts_per_face, face_verts)
}
fn assert_gregory_matches_regular_patches(
refiner: &TopologyRefiner,
table: &PatchTable,
positions: &[[f32; 3]],
) -> usize {
assert_eq!(refiner.max_level(), 0, "oracle expects base-level patches");
let level = refiner.level(0).inner();
let samples = [
(0.0f32, 0.0f32),
(1.0, 1.0),
(0.5, 0.5),
(0.15, 0.85),
(0.9, 0.2),
(0.35, 0.05),
(0.65, 0.45),
];
let mut compared = 0;
for patch in 0..table.num_patches() {
if table.patch_type(patch) != PatchType::Regular {
continue;
}
let face = table.patch_face(patch) as usize;
let param = table.patch_param(patch);
assert_eq!(param.depth, 0);
assert_eq!(param.rotation, 0);
let points = build(level, face).expect("every sharpened quad face builds");
for &(s, t) in &samples {
let (w, ws, wt) = evaluate_basis(s, t);
let mut g = [[0.0f32; 3]; 3];
for (pt, stencil) in points.iter().enumerate() {
for &(cv, sw) in &stencil.0 {
for c in 0..3 {
g[0][c] += w[pt] * sw * positions[cv as usize][c];
g[1][c] += ws[pt] * sw * positions[cv as usize][c];
g[2][c] += wt[pt] * sw * positions[cv as usize][c];
}
}
}
let (bp, bdu, bdv) = table.evaluate(patch, s, t, positions);
for c in 0..3 {
assert!(
(g[0][c] - bp[c]).abs() < 2e-4,
"face {face}: position mismatch at ({s},{t}): gregory {:?} vs bspline {:?}",
g[0],
bp
);
assert!(
(g[1][c] - bdu[c]).abs() < 2e-3,
"face {face}: du mismatch at ({s},{t}): gregory {:?} vs bspline {:?}",
g[1],
bdu
);
assert!(
(g[2][c] - bdv[c]).abs() < 2e-3,
"face {face}: dv mismatch at ({s},{t}): gregory {:?} vs bspline {:?}",
g[2],
bdv
);
}
}
compared += 1;
}
compared
}
#[test]
fn gregory_reproduces_bspline_on_interior_and_boundary_faces() {
let (verts_per_face, face_verts) = grid_faces(6, 6);
let positions = jittered_grid(6, 6);
let descriptor = TopologyDescriptor::new(36, &verts_per_face, &face_verts);
let refiner = TopologyRefinerFactory::create(
descriptor,
sdc::SchemeType::Catmark,
sdc::Options::default(),
)
.unwrap();
let table = PatchTableFactory::create(&refiner).unwrap();
assert_eq!(
assert_gregory_matches_regular_patches(&refiner, &table, &positions),
21
);
}
#[test]
fn gregory_reproduces_bspline_on_boundary_and_corner_faces() {
let (verts_per_face, face_verts) = grid_faces(5, 5);
let positions = jittered_grid(5, 5);
let options = sdc::Options::default()
.with_vtx_boundary_interpolation(sdc::VtxBoundaryInterpolation::EdgeAndCorner);
let descriptor = TopologyDescriptor::new(25, &verts_per_face, &face_verts);
let refiner =
TopologyRefinerFactory::create(descriptor, sdc::SchemeType::Catmark, options).unwrap();
let table = PatchTableFactory::create(&refiner).unwrap();
assert_eq!(
assert_gregory_matches_regular_patches(&refiner, &table, &positions),
16
);
}
#[test]
fn gregory_reproduces_bspline_along_infinitely_sharp_creases() {
let (verts_per_face, face_verts) = grid_faces(6, 6);
let positions = jittered_grid(6, 6);
let mut creases = Vec::new();
for i in 0..5u32 {
creases.push([18 + i, 19 + i]); }
for j in 0..5u32 {
creases.push([2 + 6 * j, 8 + 6 * j]); }
let weights = vec![sdc::SHARPNESS_INFINITE; creases.len()];
let options = sdc::Options::default()
.with_vtx_boundary_interpolation(sdc::VtxBoundaryInterpolation::EdgeAndCorner);
let descriptor = TopologyDescriptor::new(36, &verts_per_face, &face_verts)
.with_creases(&creases, &weights);
let refiner =
TopologyRefinerFactory::create(descriptor, sdc::SchemeType::Catmark, options).unwrap();
let table = PatchTableFactory::create(&refiner).unwrap();
assert_eq!(
assert_gregory_matches_regular_patches(&refiner, &table, &positions),
25
);
}
#[test]
fn edge_factor_matches_reference_table() {
let expected = [
(3, 8.128_157_290_637_231e-1),
(4, 0.5),
(5, 3.636_440_632_914_28e-1),
(6, 2.875_137_970_607_708_5e-1),
(7, 2.386_878_668_585_167_8e-1),
(12, 1.312_756_841_588_301_7e-1),
(29, 5.296_209_143_379_613_4e-2),
];
for (valence, value) in expected {
assert!(
(edge_factor(valence) as f64 - value).abs() < 1e-7,
"valence {valence}"
);
}
}
#[test]
fn corner_spans_follow_boundaries_and_creases() {
let (verts_per_face, face_verts) = grid_faces(4, 4);
let creases = [[1u32, 5], [5, 9], [9, 13]];
let weights = [sdc::SHARPNESS_INFINITE; 3];
let descriptor = TopologyDescriptor::new(16, &verts_per_face, &face_verts)
.with_creases(&creases, &weights);
let refiner = TopologyRefinerFactory::create(
descriptor,
sdc::SchemeType::Catmark,
sdc::Options::default(),
)
.unwrap();
let level = refiner.level(0).inner();
let span = corner_span(level, 4, 0, true).unwrap();
assert!(span.boundary);
assert_eq!(span.num_faces(), 2);
assert_eq!(span.edges.len(), 3);
assert!(level.edge_vertices(span.edges[0] as usize).contains(&1));
assert!(level.edge_vertices(span.edges[2] as usize).contains(&9));
assert_eq!(span.face_in_span, 1);
assert_eq!(span.faces[1], 4);
let ring = corner_span(level, 4, 0, false).unwrap();
assert!(!ring.boundary);
assert_eq!(ring.num_faces(), 4);
assert_eq!(ring.faces[0], 4);
assert_eq!(ring.face_in_span, 0);
assert!(level.edge_vertices(ring.edges[0] as usize).contains(&6));
assert!(level.edge_vertices(ring.edges[1] as usize).contains(&9));
let span = corner_span(level, 0, 1, true).unwrap();
assert!(span.boundary);
assert_eq!(span.num_faces(), 1);
assert_eq!(span.face_in_span, 0);
}
}