// Ported from Draco 1.5.7 (compression/mesh/mesh_edgebreaker_decoder_impl.cc): Apache License 2.0,
// Copyright 2016 The Draco Authors. See NOTICE.
///|
/// The edgebreaker symbols as Draco's `EdgebreakerTopologyBitPattern` numbers them.
const TOPOLOGY_C = 0
///|
const TOPOLOGY_S = 1
///|
const TOPOLOGY_L = 3
///|
const TOPOLOGY_R = 5
///|
const TOPOLOGY_E = 7
///|
const TOPOLOGY_INVALID = 9
///|
let symbol_to_topology : FixedArray[Int32] = [
TOPOLOGY_C,
TOPOLOGY_S,
TOPOLOGY_L,
TOPOLOGY_R,
TOPOLOGY_E,
]
///|
/// An attribute's seams (`AttributeData` of the edgebreaker decoder).
priv struct AttributeData {
mut decoder_id : Int32
mut table : AttrTable?
mut connectivity_used : Bool
enc : EncodingData
seams : Array[Int32]
}
///|
/// The edgebreaker decoder's state (`MeshEdgebreakerDecoderImpl`).
priv struct Edgebreaker {
ct : CornerTable
version : Int32
traversal : Traversal
split_source : Array[Int32]
split_target : Array[Int32]
split_edge : Array[Int32]
hole : FixedArray[Bool]
attribute_data : Array[AttributeData]
pos : EncodingData
mut pos_decoder_id : Int32
}
///|
fn Edgebreaker::set_opposites(self : Edgebreaker, a : Int32, b : Int32) -> Bool {
guard a >= 0 && b >= 0 else { return false }
self.ct.opp[a] = b
self.ct.opp[b] = a
true
}
///|
/// `IsTopologySplit`: 0 no split, 1 a split (its edge and symbol in `out`), -1 a bad one.
fn Edgebreaker::topology_split(
self : Edgebreaker,
encoder_symbol_id : Int32,
out : FixedArray[Int32],
) -> Int32 {
let n = self.split_source.length()
if n == 0 {
return 0
}
let source = self.split_source[n - 1]
if ult(encoder_symbol_id, source) {
return -1
}
if source != encoder_symbol_id {
return 0
}
out[0] = self.split_edge[n - 1]
out[1] = self.split_target[n - 1]
self.split_source.truncate(n - 1)
self.split_target.truncate(n - 1)
self.split_edge.truncate(n - 1)
1
}
///|
/// `DecodeHoleAndTopologySplitEvents`: the bytes read, or -1.
fn Edgebreaker::decode_events(self : Edgebreaker, b : Buffer) -> Int32 {
let version = self.version
let num_splits = b.varint()
guard !b.failed else { return -1 }
if num_splits != 0 {
guard !ult(self.ct.face_count(), num_splits) else { return -1 }
let mut last_source = 0
for _ in 0.. Int32 {
let ct = self.ct
let tr = self.traversal
let stack : Array[Int32] = []
let split_corners = FixedArray::make(num_symbols, -1)
let invalid_vertices : Array[Int32] = []
let remove_invalid = self.attribute_data.length() == 0
let max_vertices = self.hole.length()
let split = FixedArray::make(2, 0)
let limit = ct.c2v.length() + 1
let mut num_faces = 0
for symbol_id in 0.. 0 else { return -1 }
let corner_a = stack[stack.length() - 1]
let vertex_x = ct.vertex(next(corner_a))
let corner_b = next(ct.left_most(vertex_x))
guard corner_a != corner_b else { return -1 }
guard ct.opposite(corner_a) < 0 && ct.opposite(corner_b) < 0 else {
return -1
}
let corner = 3 * face
guard self.set_opposites(corner_a, corner + 1) else { return -1 }
guard self.set_opposites(corner_b, corner + 2) else { return -1 }
let vert_a_prev = ct.vertex(previous(corner_a))
let vert_b_next = ct.vertex(next(corner_b))
guard vertex_x != vert_a_prev && vertex_x != vert_b_next else {
return -1
}
ct.c2v[corner] = vertex_x
ct.c2v[corner + 1] = vert_b_next
ct.c2v[corner + 2] = vert_a_prev
ct.set_left_most(vert_a_prev, corner + 2)
self.hole[vertex_x] = false
stack[stack.length() - 1] = corner
} else if symbol == TOPOLOGY_R || symbol == TOPOLOGY_L {
guard stack.length() > 0 else { return -1 }
let corner_a = stack[stack.length() - 1]
guard ct.opposite(corner_a) < 0 else { return -1 }
let corner = 3 * face
let (opp_corner, corner_l, corner_r) = if symbol == TOPOLOGY_R {
(corner + 2, corner + 1, corner)
} else {
(corner + 1, corner, corner + 2)
}
guard self.set_opposites(opp_corner, corner_a) else { return -1 }
let new_vert = ct.add_vertex()
guard ct.vertex_count() <= max_vertices else { return -1 }
ct.c2v[opp_corner] = new_vert
ct.set_left_most(new_vert, opp_corner)
let vertex_r = ct.vertex(previous(corner_a))
ct.c2v[corner_r] = vertex_r
ct.set_left_most(vertex_r, corner_r)
ct.c2v[corner_l] = ct.vertex(next(corner_a))
stack[stack.length() - 1] = corner
check_split = true
} else if symbol == TOPOLOGY_S {
guard stack.length() > 0 else { return -1 }
let corner_b = stack.unsafe_pop()
if split_corners[symbol_id] >= 0 {
stack.push(split_corners[symbol_id])
}
guard stack.length() > 0 else { return -1 }
let corner_a = stack[stack.length() - 1]
guard corner_a != corner_b else { return -1 }
guard ct.opposite(corner_a) < 0 && ct.opposite(corner_b) < 0 else {
return -1
}
let corner = 3 * face
guard self.set_opposites(corner_a, corner + 2) else { return -1 }
guard self.set_opposites(corner_b, corner + 1) else { return -1 }
let vertex_p = ct.vertex(previous(corner_a))
ct.c2v[corner] = vertex_p
ct.c2v[corner + 1] = ct.vertex(next(corner_a))
let vert_b_prev = ct.vertex(previous(corner_b))
ct.c2v[corner + 2] = vert_b_prev
ct.set_left_most(vert_b_prev, corner + 2)
let mut corner_n = next(corner_b)
let vertex_n = ct.vertex(corner_n)
guard vertex_p >= 0 && vertex_n >= 0 else { return -1 }
tr.merge_vertices(vertex_p, vertex_n)
ct.set_left_most(vertex_p, ct.left_most(vertex_n))
let first_corner = corner_n
while corner_n >= 0 {
ct.c2v[corner_n] = vertex_p
corner_n = ct.swing_left(corner_n)
guard corner_n != first_corner else { return -1 }
}
ct.vcorners[vertex_n] = -1
if remove_invalid {
invalid_vertices.push(vertex_n)
}
stack[stack.length() - 1] = corner
} else if symbol == TOPOLOGY_E {
let corner = 3 * face
let first_vert = ct.add_vertex()
ct.c2v[corner] = first_vert
ct.c2v[corner + 1] = ct.add_vertex()
ct.c2v[corner + 2] = ct.add_vertex()
guard ct.vertex_count() <= max_vertices else { return -1 }
ct.set_left_most(first_vert, corner)
ct.set_left_most(first_vert + 1, corner + 1)
ct.set_left_most(first_vert + 2, corner + 2)
stack.push(corner)
check_split = true
} else {
return -1
}
tr.new_active_corner(ct, stack[stack.length() - 1])
if check_split {
let encoder_symbol_id = num_symbols - symbol_id - 1
while true {
let r = self.topology_split(encoder_symbol_id, split)
if r == 0 {
break
}
guard r > 0 && split[1] >= 0 else { return -1 }
let top = stack[stack.length() - 1]
let new_active = if split[0] == 1 { next(top) } else { previous(top) }
let decoder_split = num_symbols - split[1] - 1
split_corners[decoder_split] = new_active
}
}
}
guard ct.vertex_count() <= max_vertices else { return -1 }
while stack.length() > 0 {
let corner = stack.unsafe_pop()
if tr.start_face_configuration() {
guard num_faces < ct.face_count() else { return -1 }
let vert_n = ct.vertex(next(corner))
let corner_b = next(ct.left_most(vert_n))
let vert_x = ct.vertex(next(corner_b))
let corner_c = next(ct.left_most(vert_x))
guard corner != corner_b && corner != corner_c && corner_b != corner_c else {
return -1
}
guard ct.opposite(corner) < 0 &&
ct.opposite(corner_b) < 0 &&
ct.opposite(corner_c) < 0 else {
return -1
}
let vert_p = ct.vertex(next(corner_c))
let new_corner = 3 * num_faces
num_faces += 1
guard self.set_opposites(new_corner, corner) else { return -1 }
guard self.set_opposites(new_corner + 1, corner_b) else { return -1 }
guard self.set_opposites(new_corner + 2, corner_c) else { return -1 }
ct.c2v[new_corner] = vert_x
ct.c2v[new_corner + 1] = vert_p
ct.c2v[new_corner + 2] = vert_n
for k in 0..<3 {
let v = ct.c2v[new_corner + k]
guard v >= 0 else { return -1 }
self.hole[v] = false
}
}
}
guard num_faces == ct.face_count() else { return -1 }
let mut num_vertices = ct.vertex_count()
for invalid_vert in invalid_vertices {
let mut src_vert = num_vertices - 1
while src_vert >= 0 && ct.vcorners[src_vert] < 0 {
num_vertices -= 1
src_vert = num_vertices - 1
}
guard src_vert >= 0 else { return -1 }
if src_vert < invalid_vert {
continue
}
let start = ct.vcorners[src_vert]
let mut c = start
let mut left = true
let mut steps = 0
while c >= 0 {
guard ct.c2v[c] == src_vert else { return -1 }
ct.c2v[c] = invalid_vert
if left {
c = ct.swing_left(c)
if c < 0 {
c = ct.swing_right(start)
left = false
} else if c == start {
c = -1
}
} else {
c = ct.swing_right(c)
}
steps += 1
guard steps <= limit else { return -1 }
}
ct.vcorners[invalid_vert] = ct.vcorners[src_vert]
ct.vcorners[src_vert] = -1
self.hole[invalid_vert] = self.hole[src_vert]
self.hole[src_vert] = false
num_vertices -= 1
}
num_vertices
}
///|
fn Edgebreaker::attribute_connectivity(
self : Edgebreaker,
corner : Int32,
) -> Unit {
let ct = self.ct
let corners = [corner, next(corner), previous(corner)]
let src_face = corner / 3
for c in corners {
let opp = ct.opposite(c)
if opp < 0 {
for d in self.attribute_data {
d.seams.push(c)
}
continue
}
if self.version >= bitstream(2, 1) && opp / 3 < src_face {
continue
}
for i, d in self.attribute_data {
if self.traversal.seams[i].bit() {
d.seams.push(c)
}
}
}
}
///|
/// `AssignPointsToCorners`: the mesh's faces as point ids and the number of points, or None.
fn Edgebreaker::assign_points(
self : Edgebreaker,
num_connectivity_verts : Int32,
) -> (FixedArray[Int32], Int32)? {
let ct = self.ct
let num_corners = ct.c2v.length()
if self.attribute_data.length() == 0 {
return Some(
(
FixedArray::makei(num_corners, fn(c) { ct.c2v[c] }),
num_connectivity_verts,
),
)
}
let tables = self.attribute_data.map(fn(d) { d.table.unwrap() })
let corner_to_point = FixedArray::make(num_corners, 0)
let limit = num_corners + 1
let mut num_points = 0
for v in 0..= 0 else { return None }
if t.c2v[act] != vert {
first = act
found = true
break
}
act = ct.swing_right(act)
steps += 1
guard steps <= limit else { return None }
}
if found {
break
}
}
}
c = first
corner_to_point[c] = num_points
num_points += 1
let mut prev = c
c = ct.swing_right(c)
let mut steps = 0
while c >= 0 && c != first {
let mut seam = false
for t in tables {
if t.c2v[c] != t.c2v[prev] {
seam = true
break
}
}
if seam {
corner_to_point[c] = num_points
num_points += 1
} else {
corner_to_point[c] = corner_to_point[prev]
}
prev = c
c = ct.swing_right(c)
steps += 1
guard steps <= limit else { return None }
}
}
Some((corner_to_point, num_points))
}
///|
/// `MeshEdgebreakerDecoderImpl::DecodeConnectivity`: the faces as point ids and the number of
/// points, or None.
fn decode_edgebreaker(
b : Buffer,
kind : Int32,
) -> (Edgebreaker, FixedArray[Int32], Int32)? {
let version = b.version
if version < bitstream(2, 2) {
let _ = b.varint()
guard !b.failed else { return None }
}
let num_encoded_vertices = b.varint()
guard !b.failed else { return None }
let num_faces = b.varint()
guard !b.failed else { return None }
guard !ult(0x55555555, num_faces) else { return None }
guard !ult(num_faces * 3, num_encoded_vertices) else { return None }
let min_face_edges = (3 * num_faces).reinterpret_as_uint() / 2
let nv = num_encoded_vertices.reinterpret_as_uint().to_uint64()
guard nv * (nv - 1) / 2 >= min_face_edges.to_uint64() else { return None }
let num_attribute_data = b.u8()
guard !b.failed else { return None }
let num_symbols = b.varint()
guard !b.failed else { return None }
guard !ult(num_faces, num_symbols) else { return None }
guard !ult(
(num_symbols.reinterpret_as_uint() + num_symbols.reinterpret_as_uint() / 3).reinterpret_as_int(),
num_faces,
) else {
return None
}
let num_split_symbols = b.varint()
guard !b.failed else { return None }
guard !ult(num_symbols, num_split_symbols) else { return None }
guard num_faces <= MAX_FACES else { return None }
let num_vertices = num_encoded_vertices + num_split_symbols
guard num_vertices >= 0 && num_vertices <= 3 * MAX_FACES else { return None }
let ct = CornerTable::new(num_faces)
let eb : Edgebreaker = {
ct,
version,
traversal: Traversal::new(kind, b),
split_source: [],
split_target: [],
split_edge: [],
hole: FixedArray::make(num_vertices, true),
attribute_data: Array::makei(num_attribute_data, fn(_) {
{
decoder_id: -1,
table: None,
connectivity_used: true,
enc: EncodingData::new(),
seams: [],
}
}),
pos: EncodingData::new(),
pos_decoder_id: -1,
}
let mut split_bytes = -1
if version < bitstream(2, 2) {
let size = b.varint()
guard !b.failed else { return None }
guard size != 0 && b.fits(size.reinterpret_as_uint().to_uint64()) else {
return None
}
let events = b.copy()
events.init(b.head() + size, b.remaining() - size, version)
split_bytes = eb.decode_events(events)
guard split_bytes != -1 else { return None }
} else {
guard eb.decode_events(b) != -1 else { return None }
}
let tr = eb.traversal
tr.buffer.init(b.head(), b.remaining(), version)
tr.num_vertices = num_vertices
tr.num_attribute_data = num_attribute_data
let end = b.copy()
guard tr.start(end, num_faces) else { return None }
let num_connectivity_verts = eb.decode_connectivity(num_symbols)
guard num_connectivity_verts != -1 else { return None }
b.init(end.head(), end.remaining(), version)
if version < bitstream(2, 2) {
b.pos += split_bytes
}
if eb.attribute_data.length() > 0 {
let mut c = 0
while c < ct.c2v.length() {
eb.attribute_connectivity(c)
c += 3
}
}
for d in eb.attribute_data {
let t = AttrTable::new(ct)
for c in d.seams {
t.add_seam_edge(c)
}
guard t.recompute_vertices() else { return None }
d.table = Some(t)
}
eb.pos.vertex_values = FixedArray::make(ct.vertex_count(), 0)
for d in eb.attribute_data {
let n = d.table.unwrap().entries.length()
d.enc.vertex_values = FixedArray::make(
if n < ct.vertex_count() {
ct.vertex_count()
} else {
n
},
0,
)
}
guard eb.assign_points(num_connectivity_verts) is Some((faces, num_points)) else {
return None
}
Some((eb, faces, num_points))
}