use super::corner_table::{CornerTable, INVALID_CORNER, INVALID_VERTEX};
use super::rans::BitDecoder;
use super::DracoError;
#[derive(Debug, Clone, Default)]
pub struct AttributeCornerTable {
is_edge_on_seam: Vec<bool>,
is_vertex_on_seam: Vec<bool>,
corner_to_vertex: Vec<u32>,
vertex_to_leftmost_corner: Vec<u32>,
pub no_interior_seams: bool,
}
impl AttributeCornerTable {
pub fn new(base: &CornerTable) -> Self {
AttributeCornerTable {
is_edge_on_seam: vec![false; base.num_corners() as usize],
is_vertex_on_seam: vec![false; base.num_vertices() as usize],
corner_to_vertex: vec![INVALID_VERTEX; base.num_corners() as usize],
vertex_to_leftmost_corner: Vec::new(),
no_interior_seams: true,
}
}
pub fn add_seam_edge(&mut self, base: &CornerTable, corner: u32) -> Result<(), DracoError> {
self.mark_edge(corner)?;
self.mark_ends(base, corner)?;
let opp = base.opposite(corner);
if opp != INVALID_CORNER {
self.no_interior_seams = false;
self.mark_edge(opp)?;
self.mark_ends(base, opp)?;
}
Ok(())
}
fn mark_edge(&mut self, corner: u32) -> Result<(), DracoError> {
*self
.is_edge_on_seam
.get_mut(corner as usize)
.ok_or(DracoError::Corrupt)? = true;
Ok(())
}
fn mark_ends(&mut self, base: &CornerTable, corner: u32) -> Result<(), DracoError> {
for c in [base.next(corner), base.previous(corner)] {
let v = base.vertex(c);
if v == INVALID_VERTEX {
return Err(DracoError::Corrupt);
}
*self
.is_vertex_on_seam
.get_mut(v as usize)
.ok_or(DracoError::Corrupt)? = true;
}
Ok(())
}
pub fn is_corner_opposite_to_seam_edge(&self, corner: u32) -> bool {
if corner == INVALID_CORNER {
return false;
}
self.is_edge_on_seam
.get(corner as usize)
.copied()
.unwrap_or(false)
}
pub fn is_corner_on_seam(&self, base: &CornerTable, corner: u32) -> bool {
let v = base.vertex(corner);
if v == INVALID_VERTEX {
return false;
}
self.is_vertex_on_seam
.get(v as usize)
.copied()
.unwrap_or(false)
}
pub fn opposite(&self, base: &CornerTable, corner: u32) -> u32 {
if corner == INVALID_CORNER || self.is_corner_opposite_to_seam_edge(corner) {
return INVALID_CORNER;
}
base.opposite(corner)
}
pub fn swing_left(&self, base: &CornerTable, corner: u32) -> u32 {
base.next(self.opposite(base, base.next(corner)))
}
pub fn swing_right(&self, base: &CornerTable, corner: u32) -> u32 {
base.previous(self.opposite(base, base.previous(corner)))
}
pub fn vertex(&self, corner: u32) -> u32 {
if corner == INVALID_CORNER {
return INVALID_VERTEX;
}
self.corner_to_vertex
.get(corner as usize)
.copied()
.unwrap_or(INVALID_VERTEX)
}
pub fn num_vertices(&self) -> u32 {
self.vertex_to_leftmost_corner.len() as u32
}
pub fn leftmost_corner(&self, vert: u32) -> u32 {
self.vertex_to_leftmost_corner
.get(vert as usize)
.copied()
.unwrap_or(INVALID_CORNER)
}
pub fn recompute_vertices(&mut self, base: &CornerTable) -> Result<(), DracoError> {
self.vertex_to_leftmost_corner.clear();
let mut num_new_vertices = 0u32;
for v in 0..base.num_vertices() {
let c = base.leftmost_corner(v);
if c == INVALID_CORNER {
continue; }
let mut vert_id = num_new_vertices;
num_new_vertices += 1;
let mut first_c = c;
if self.is_vertex_on_seam.get(v as usize).copied().unwrap_or(false) {
let mut act_c = self.swing_left(base, first_c);
let mut steps = 0u32;
while act_c != INVALID_CORNER {
first_c = act_c;
act_c = self.swing_left(base, act_c);
if act_c == c {
return Err(DracoError::Corrupt);
}
steps += 1;
if steps > base.num_corners() {
return Err(DracoError::Corrupt);
}
}
}
self.set_vertex(first_c, vert_id)?;
self.vertex_to_leftmost_corner.push(first_c);
let mut act_c = base.swing_right(first_c);
let mut steps = 0u32;
while act_c != INVALID_CORNER && act_c != first_c {
if self.is_corner_opposite_to_seam_edge(base.next(act_c)) {
vert_id = num_new_vertices;
num_new_vertices += 1;
self.vertex_to_leftmost_corner.push(act_c);
}
self.set_vertex(act_c, vert_id)?;
act_c = base.swing_right(act_c);
steps += 1;
if steps > base.num_corners() {
return Err(DracoError::Corrupt);
}
}
}
Ok(())
}
fn set_vertex(&mut self, corner: u32, vert: u32) -> Result<(), DracoError> {
*self
.corner_to_vertex
.get_mut(corner as usize)
.ok_or(DracoError::Corrupt)? = vert;
Ok(())
}
}
pub fn decode_attribute_seams(
base: &CornerTable,
seams: &mut [BitDecoder<'_>],
) -> Result<Vec<AttributeCornerTable>, DracoError> {
let mut seam_corners: Vec<Vec<u32>> = vec![Vec::new(); seams.len()];
let mut face_start = 0u32;
while face_start < base.num_corners() {
let src_face = base.face(face_start);
for corner in [face_start, base.next(face_start), base.previous(face_start)] {
let opp = base.opposite(corner);
if opp == INVALID_CORNER {
for list in seam_corners.iter_mut() {
list.push(corner);
}
continue;
}
if base.face(opp) < src_face {
continue; }
for (list, decoder) in seam_corners.iter_mut().zip(seams.iter_mut()) {
if decoder.bit() != 0 {
list.push(corner);
}
}
}
face_start += 3;
}
let mut tables = Vec::with_capacity(seams.len());
for corners in seam_corners {
let mut table = AttributeCornerTable::new(base);
for c in corners {
table.add_seam_edge(base, c)?;
}
table.recompute_vertices(base)?;
tables.push(table);
}
Ok(tables)
}
pub fn assign_points_to_corners(
base: &CornerTable,
tables: &[AttributeCornerTable],
is_vert_hole: &[bool],
num_connectivity_verts: u32,
) -> Result<(Vec<u32>, Vec<u32>, u32), DracoError> {
if tables.is_empty() {
let corner_to_point: Vec<u32> = (0..base.num_corners()).map(|c| base.vertex(c)).collect();
return Ok((corner_to_point, Vec::new(), num_connectivity_verts));
}
let mut corner_to_point = vec![0u32; base.num_corners() as usize];
let mut point_to_corner: Vec<u32> = Vec::new();
for v in 0..base.num_vertices() {
let c = base.leftmost_corner(v);
if c == INVALID_CORNER {
continue;
}
let mut dedup_first = c;
let on_boundary = is_vert_hole.get(v as usize).copied().unwrap_or(false);
if !on_boundary {
for table in tables {
if !table.is_corner_on_seam(base, c) {
continue;
}
let vert_id = table.vertex(c);
let mut act_c = base.swing_right(c);
let mut seam_found = false;
let mut steps = 0u32;
while act_c != c {
if act_c == INVALID_CORNER {
return Err(DracoError::Corrupt);
}
if table.vertex(act_c) != vert_id {
dedup_first = act_c;
seam_found = true;
break;
}
act_c = base.swing_right(act_c);
steps += 1;
if steps > base.num_corners() {
return Err(DracoError::Corrupt);
}
}
if seam_found {
break;
}
}
}
let mut prev_c = dedup_first;
corner_to_point[dedup_first as usize] = point_to_corner.len() as u32;
point_to_corner.push(dedup_first);
let mut act_c = base.swing_right(dedup_first);
let mut steps = 0u32;
while act_c != INVALID_CORNER && act_c != dedup_first {
let changed = tables
.iter()
.any(|t| t.vertex(act_c) != t.vertex(prev_c));
if changed {
corner_to_point[act_c as usize] = point_to_corner.len() as u32;
point_to_corner.push(act_c);
} else {
corner_to_point[act_c as usize] = corner_to_point[prev_c as usize];
}
prev_c = act_c;
act_c = base.swing_right(act_c);
steps += 1;
if steps > base.num_corners() {
return Err(DracoError::Corrupt);
}
}
}
let num_points = point_to_corner.len() as u32;
Ok((corner_to_point, point_to_corner, num_points))
}
#[cfg(test)]
mod tests {
use super::*;
use crate::loaders::draco::edgebreaker_connectivity;
const SPHERE: &[u8] = include_bytes!("testdata/sphere.drc");
const BUNNY: &[u8] = include_bytes!("testdata/bunny.drc");
fn fnv1a(indices: &[u32]) -> u64 {
let mut h: u64 = 0xcbf2_9ce4_8422_2325;
for v in indices {
for byte in v.to_le_bytes() {
h = (h ^ byte as u64).wrapping_mul(0x0000_0100_0000_01b3);
}
}
h
}
#[test]
fn the_sphere_index_buffer_matches_the_reference_decoder() {
let d = edgebreaker_connectivity(SPHERE).expect("connectivity");
assert_eq!(d.num_points, 423, "points, as draco3d reports them");
let idx = d.indices();
assert_eq!(idx.len(), 720 * 3);
assert_eq!(
&idx[..30],
&[
0, 1, 2, 3, 2, 4, 2, 1, 4, 4, 1, 5, 6, 5, 7, 5, 1, 7, 7, 1, 8, 1, 0, 8, 8, 0, 9,
10, 9, 11
]
);
assert_eq!(fnv1a(&idx), 11727646580840884174, "all 2160 indices");
assert!(idx.iter().all(|i| *i < d.num_points), "an index past the points");
}
#[test]
fn the_bunny_index_buffer_matches_the_reference_decoder() {
let d = edgebreaker_connectivity(BUNNY).expect("connectivity");
assert_eq!(d.num_points, 34834);
let idx = d.indices();
assert_eq!(idx.len(), 69451 * 3);
assert_eq!(
&idx[..30],
&[
15922, 0, 1, 0, 2, 1, 1, 2, 3, 4, 5, 6, 5, 7, 6, 6, 7, 8, 9, 10, 11, 11, 10, 12,
10, 8, 12, 8, 7, 12
]
);
assert_eq!(fnv1a(&idx), 5786114087933875773, "all 208353 indices");
assert!(idx.iter().all(|i| *i < d.num_points));
}
#[test]
fn the_point_and_corner_maps_agree() {
for bytes in [SPHERE, BUNNY] {
let d = edgebreaker_connectivity(bytes).expect("connectivity");
assert_eq!(d.point_to_corner.len(), d.num_points as usize);
for (point, corner) in d.point_to_corner.iter().enumerate() {
assert_eq!(
d.corner_to_point[*corner as usize], point as u32,
"point {point} does not round-trip through its corner"
);
}
let used: std::collections::HashSet<u32> = d.corner_to_point.iter().copied().collect();
assert_eq!(used.len(), d.num_points as usize, "an unused point id");
}
}
#[test]
fn the_sphere_seams_fall_on_the_texture_coordinates() {
let d = edgebreaker_connectivity(SPHERE).expect("connectivity");
assert_eq!(d.attribute_tables.len(), 2, "normals and texture coordinates");
let normals = &d.attribute_tables[0];
let uvs = &d.attribute_tables[1];
assert!(
normals.no_interior_seams,
"a smooth sphere's normals are continuous"
);
assert_eq!(normals.num_vertices(), 362, "one per position");
assert!(!uvs.no_interior_seams, "a UV chart has to be cut");
assert_eq!(uvs.num_vertices(), 423, "one per point");
assert_eq!(d.num_points, uvs.num_vertices());
}
#[test]
fn a_cut_edge_has_no_opposite_in_the_attribute_table() {
let d = edgebreaker_connectivity(SPHERE).expect("connectivity");
let base = &d.replay.table;
let uvs = &d.attribute_tables[1];
let is_cut = |c: u32| {
base.opposite(c) != INVALID_CORNER && uvs.opposite(base, c) == INVALID_CORNER
};
let cut: Vec<u32> = (0..base.num_corners()).filter(|c| is_cut(*c)).collect();
assert!(!cut.is_empty(), "the UV seam cuts no interior edge");
for c in &cut {
assert!(
is_cut(base.opposite(*c)),
"corner {c} is cut but the corner facing it is not"
);
}
let mut per_vertex: std::collections::HashMap<u32, std::collections::HashSet<u32>> =
std::collections::HashMap::new();
for c in 0..base.num_corners() {
per_vertex.entry(base.vertex(c)).or_default().insert(uvs.vertex(c));
}
let total: usize = per_vertex.values().map(|s| s.len()).sum();
assert_eq!(total, 423, "attribute vertices, summed over positions");
let split = per_vertex.values().filter(|s| s.len() > 1).count();
assert!(split > 0, "no position was split by the seam");
assert_eq!(
total - per_vertex.len(),
423 - 362,
"the extra points are exactly the extra arcs"
);
}
}