// Ported from Draco 1.5.7 (compression/mesh/traverser/*, compression/attributes/linear_sequencer.h,
// mesh_attribute_indices_encoding_data.h): Apache License 2.0, Copyright 2016 The Draco Authors.
// See NOTICE.
///|
/// `MeshAttributeIndicesEncodingData`: `corners` is `encoded_attribute_value_index_to_corner_map`,
/// `vertex_values` `vertex_to_encoded_attribute_value_index_map`.
priv struct EncodingData {
corners : Array[Int32]
mut vertex_values : FixedArray[Int32]
mut num_values : Int32
}
///|
fn EncodingData::new() -> EncodingData {
{ corners: [], vertex_values: [], num_values: 0, }
}
///|
/// A `PointsSequencer`: `Linear` numbers the points in order, the others traverse the mesh
/// (`MeshTraversalSequencer` with a depth-first or a max-prediction-degree traverser).
priv enum Sequencer {
Linear(Int32)
DepthFirst(Table, EncodingData)
Degree(CornerTable, EncodingData)
}
///|
/// The visited flags and outputs a traversal shares with `MeshAttributeIndicesEncodingObserver`.
priv struct Visit {
faces : FixedArray[Bool]
vertices : FixedArray[Bool]
enc : EncodingData
mesh_faces : FixedArray[Int32]
points : Array[Int32]
}
///|
fn Visit::new(
t : Table,
enc : EncodingData,
mesh_faces : FixedArray[Int32],
points : Array[Int32],
) -> Visit {
{
faces: FixedArray::make(t.face_count(), false),
vertices: FixedArray::make(t.vertex_count(), false),
enc,
mesh_faces,
points,
}
}
///|
fn Visit::face_visited(self : Visit, c : Int32) -> Bool {
c < 0 || self.faces[c / 3]
}
///|
fn Visit::vertex_visited(self : Visit, v : Int32) -> Bool {
v < 0 || v >= self.vertices.length() || self.vertices[v]
}
///|
/// Marks `v` visited and records it as the observer does; false where Draco would index out of
/// bounds.
fn Visit::visit(self : Visit, v : Int32, c : Int32) -> Bool {
guard v >= 0 &&
v < self.vertices.length() &&
v < self.enc.vertex_values.length() &&
c >= 0 &&
c < self.mesh_faces.length() else {
return false
}
self.vertices[v] = true
self.points.push(self.mesh_faces[c])
self.enc.corners.push(c)
self.enc.vertex_values[v] = self.enc.num_values
self.enc.num_values += 1
true
}
///|
fn depth_first(t : Table, visit : Visit) -> Bool {
let stack : Array[Int32] = []
for f in 0..= 0 && prev_vert >= 0 else { return false }
if !visit.vertex_visited(next_vert) {
guard visit.visit(next_vert, next(start)) else { return false }
}
if !visit.vertex_visited(prev_vert) {
guard visit.visit(prev_vert, previous(start)) else { return false }
}
while stack.length() > 0 {
let mut corner = stack[stack.length() - 1]
if corner < 0 || visit.faces[corner / 3] {
let _ = stack.pop()
continue
}
while true {
guard corner >= 0 else { return false }
visit.faces[corner / 3] = true
let vert = t.vertex(corner)
guard vert >= 0 else { return false }
if !visit.vertex_visited(vert) {
let boundary = t.on_boundary(vert)
guard visit.visit(vert, corner) else { return false }
if !boundary {
corner = t.opposite(next(corner))
continue
}
}
let right = t.opposite(next(corner))
let left = t.opposite(previous(corner))
if visit.face_visited(right) {
if visit.face_visited(left) {
let _ = stack.pop()
break
}
corner = left
} else if visit.face_visited(left) {
corner = right
} else {
stack[stack.length() - 1] = left
stack.push(right)
break
}
}
}
}
true
}
///|
fn max_degree(t : CornerTable, visit : Visit) -> Bool {
let degrees = FixedArray::make(t.vertex_count(), 0)
if degrees.length() == 0 {
return true
}
let stacks : FixedArray[Array[Int32]] = [[], [], []]
let mut best = 0
let priority = fn(c : Int32) -> Int32 {
let tip = t.vertex(c)
if visit.vertex_visited(tip) {
0
} else {
degrees[tip] += 1
if degrees[tip] > 1 {
1
} else {
2
}
}
}
for f in 0.. 0 {
corner = stacks[i].unsafe_pop()
best = i
break
}
}
if corner < 0 {
break
}
if visit.faces[corner / 3] {
continue
}
while true {
visit.faces[corner / 3] = true
let vert = t.vertex(corner)
if !visit.vertex_visited(vert) {
guard visit.visit(vert, corner) else { return false }
}
let right = t.opposite(next(corner))
let left = t.opposite(previous(corner))
let right_visited = visit.face_visited(right)
let left_visited = visit.face_visited(left)
if !left_visited {
let p = priority(left)
if right_visited && p <= best {
corner = left
continue
}
stacks[p].push(left)
if p < best {
best = p
}
}
if !right_visited {
let p = priority(right)
if p <= best {
corner = right
continue
}
stacks[p].push(right)
if p < best {
best = p
}
}
break
}
}
}
true
}
///|
/// `GenerateSequence`: the point ids in the order their values are stored.
fn Sequencer::generate(
self : Sequencer,
mesh_faces : FixedArray[Int32],
) -> Array[Int32]? {
match self {
Linear(n) => {
guard n >= 0 else { return None }
Some(Array::makei(n, fn(i) { i }))
}
DepthFirst(t, enc) => {
let points = []
guard depth_first(t, Visit::new(t, enc, mesh_faces, points)) else {
return None
}
Some(points)
}
Degree(t, enc) => {
let points = []
guard max_degree(t, Visit::new(Main(t), enc, mesh_faces, points)) else {
return None
}
Some(points)
}
}
}
///|
fn traversal_mapping(
t : Table,
enc : EncodingData,
mesh_faces : FixedArray[Int32],
num_points : Int32,
) -> FixedArray[Int32]? {
let map = FixedArray::make(num_points, -1)
for c in 0..= 0 && vert < enc.vertex_values.length() else { return None }
let entry = enc.vertex_values[vert]
guard ult(point, num_points) && ult(entry, num_points) else { return None }
map[point] = entry
}
Some(map)
}
///|
/// `UpdatePointToAttributeIndexMapping`: None for the identity mapping, else each point's value.
fn Sequencer::mapping(
self : Sequencer,
mesh_faces : FixedArray[Int32],
num_points : Int32,
) -> FixedArray[Int32]?? {
match self {
Linear(_) => Some(None)
DepthFirst(t, enc) =>
traversal_mapping(t, enc, mesh_faces, num_points).map(fn(m) { Some(m) })
Degree(t, enc) =>
traversal_mapping(Main(t), enc, mesh_faces, num_points).map(fn(m) {
Some(m)
})
}
}