draco_oxide_core/codec/attribute/
sequence.rs

1use crate::corner_table::GenericCornerTable;
2use crate::types::{CornerIdx, VertexIdx};
3
4#[derive(Debug, Clone)]
5pub struct Traverser<'ct, CornerTableType>
6where
7    CornerTableType: GenericCornerTable,
8{
9    corner_table: &'ct CornerTableType,
10    visited_vertices: Vec<bool>,
11    visited_faces: Vec<bool>,
12    corner_traversal_stack: Vec<CornerIdx>,
13    out: Vec<CornerIdx>,
14}
15
16impl<'ct, T> Traverser<'ct, T>
17where
18    T: GenericCornerTable,
19{
20    /// Creates a new `Traverser` instance.
21    /// # Arguments
22    /// * `corner_table` - A reference to the corner table to traverse.
23    /// * `corners_of_edgebreaker_traversal` - A vector of corner indices
24    ///   representing the last-encoded corners for connected components in encoded order.
25    pub fn new(corner_table: &'ct T, corners_of_edgebreaker_traversal: Vec<CornerIdx>) -> Self {
26        Self {
27            visited_vertices: vec![false; corner_table.num_vertices()],
28            visited_faces: vec![false; corner_table.num_faces()],
29            corner_table,
30            corner_traversal_stack: corners_of_edgebreaker_traversal, // The last encoded connected component gets decoded first
31            out: Vec::with_capacity(corner_table.num_corners()),
32        }
33    }
34
35    pub fn is_vertex_visited(&self, v: VertexIdx) -> bool {
36        self.visited_vertices[usize::from(v)]
37    }
38
39    pub fn visit(&mut self, v: VertexIdx, c: CornerIdx) {
40        if !self.visited_vertices[usize::from(v)] {
41            self.out.push(c);
42        }
43        self.visited_vertices[usize::from(v)] = true;
44    }
45
46    pub fn compute_seqeunce(mut self) -> Vec<CornerIdx> {
47        while let Some(curr_corner) = self.corner_traversal_stack.pop() {
48            // If the face has not yet been visited, then the
49            // other vertices of the face are not visited yet either. If this is the case, then
50            // we need to store them in self.next_outputs_stack so that they will get processed first.
51            let v = self.corner_table.vertex_idx(curr_corner);
52            if self.visited_faces[usize::from(self.corner_table.face_idx_containing(curr_corner))] {
53                continue;
54            }
55            let next_c = self.corner_table.next(curr_corner);
56            let next_v = self.corner_table.vertex_idx(next_c);
57            let prev_c = self.corner_table.previous(curr_corner);
58            let prev_v = self.corner_table.vertex_idx(prev_c);
59            if !self.is_vertex_visited(next_v) || !self.is_vertex_visited(prev_v) {
60                // We need to return the next corner first, then the previous corner, and finally the current corner.
61                // This order is determined by the draco library.
62                self.visit(next_v, next_c);
63                self.visit(prev_v, prev_c);
64                self.corner_traversal_stack.push(curr_corner);
65                continue;
66            }
67
68            // Coming here means that we are visiting a new face.
69            let face_idx = self.corner_table.face_idx_containing(curr_corner);
70            self.visited_faces[usize::from(face_idx)] = true;
71            // Once a face is marked visited it is never unmarked, and the pop
72            // loop above skips any corner whose face is already visited. So stale
73            // corners of this face still left on the stack (the handle case) are
74            // harmlessly skipped when popped; we no longer scan-and-remove them.
75
76            // If we have not yet visited the vertex of the current corner and if it is not on a boundary then we can simply return it.
77            if !self.is_vertex_visited(v) {
78                self.visit(v, curr_corner);
79                if !self.corner_table.is_on_boundary(v) {
80                    self.corner_traversal_stack.push(
81                        self.corner_table.get_right_corner(curr_corner).unwrap(), // It is guaranteed to exist because the current corner is unvisited and not on a boundary
82                    );
83                    continue;
84                }
85            }
86
87            self.visit(v, curr_corner);
88
89            let right_corner = self.corner_table.get_right_corner(curr_corner);
90            let left_corner = self.corner_table.get_left_corner(curr_corner);
91            let right_face = right_corner.map(|c| self.corner_table.face_idx_containing(c));
92            let left_face = left_corner.map(|c| self.corner_table.face_idx_containing(c));
93
94            if right_face.is_some() && self.visited_faces[usize::from(right_face.unwrap())] {
95                // Right face has been visited
96                if left_face.is_some() && self.visited_faces[usize::from(left_face.unwrap())] {
97                    // Both neighboring faces are visited, we can continue traversing. No update to the stack.
98                } else {
99                    // Left face is unvisited or does not exist.
100                    // We need to traverse the left face if it exists.
101                    if let Some(lc) = left_corner {
102                        self.corner_traversal_stack.push(lc);
103                    }
104                }
105            } else {
106                // Right face is unvisited or does not exist.
107                if left_face.is_some() && self.visited_faces[usize::from(left_face.unwrap())] {
108                    // Left face is visited.
109                    // we need to traverse the right face if it exists.
110                    if let Some(rc) = right_corner {
111                        self.corner_traversal_stack.push(rc);
112                    }
113                } else {
114                    // Both neighboring faces are unvisited, or the neighborig faces may not exist.
115                    // If there are neighboring faces, then we need to traverse them.
116                    // The right corner must be traversed first.
117                    if let Some(lc) = left_corner {
118                        self.corner_traversal_stack.push(lc);
119                    }
120                    if let Some(rc) = right_corner {
121                        self.corner_traversal_stack.push(rc);
122                    }
123                }
124            }
125        }
126        self.out
127    }
128}
draco_oxide_core/codec/attribute/sequence.rs

draco_oxide_core/codec/attribute/
sequence.rs
