1 // Copyright 2017 The Draco Authors.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 //      http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 //
15 #include "draco/mesh/mesh_stripifier.h"
16 
17 namespace draco {
18 
GenerateStripsFromCorner(int local_strip_id,CornerIndex ci)19 void MeshStripifier::GenerateStripsFromCorner(int local_strip_id,
20                                               CornerIndex ci) {
21   // Clear the storage for strip faces.
22   strip_faces_[local_strip_id].clear();
23   // Start corner of the strip (where the strip starts).
24   CornerIndex start_ci = ci;
25   FaceIndex fi = corner_table_->Face(ci);
26   // We need to grow the strip both forward and backward (2 passes).
27   // Note that the backward pass can change the start corner of the strip (the
28   // start corner is going to be moved to the end of the backward strip).
29   for (int pass = 0; pass < 2; ++pass) {
30     if (pass == 1) {
31       // Backward pass.
32       // Start the traversal from the B that is the left sibling of the next
33       // corner to the start corner C = |start_ci|.
34       //
35       //      *-------*-------*-------*
36       //     / \     / \C    / \     /
37       //    /   \   /   \   /   \   /
38       //   /     \ /    B\ /     \ /
39       //  *-------*-------*-------*
40       //
41       // Perform the backward pass only when there is no attribute seam between
42       // the initial face and the first face of the backward traversal.
43       if (GetOppositeCorner(corner_table_->Previous(start_ci)) ==
44           kInvalidCornerIndex) {
45         break;  // Attribute seam or a boundary.
46       }
47 
48       ci = corner_table_->Next(start_ci);
49       ci = corner_table_->SwingLeft(ci);
50       if (ci == kInvalidCornerIndex) {
51         break;
52       }
53 
54       fi = corner_table_->Face(ci);
55     }
56     int num_added_faces = 0;
57     while (!is_face_visited_[fi]) {
58       is_face_visited_[fi] = true;
59       strip_faces_[local_strip_id].push_back(fi);
60       ++num_added_faces;
61       if (num_added_faces > 1) {
62         // Move to the correct source corner to traverse to the next face.
63         if (num_added_faces & 1) {
64           // Odd number of faces added.
65           ci = corner_table_->Next(ci);
66         } else {
67           // Even number of faces added.
68           if (pass == 1) {
69             // If we are processing the backward pass, update the start corner
70             // of the strip on every even face reached (we cannot use odd faces
71             // for start of the strip as the strips would start in a wrong
72             // direction).
73             start_ci = ci;
74           }
75           ci = corner_table_->Previous(ci);
76         }
77       }
78       ci = GetOppositeCorner(ci);
79       if (ci == kInvalidCornerIndex) {
80         break;
81       }
82       fi = corner_table_->Face(ci);
83     }
84     // Strip end reached.
85     if (pass == 1 && (num_added_faces & 1)) {
86       // If we processed the backward strip and we add an odd number of faces to
87       // the strip, we need to remove the last one as it cannot be used to start
88       // the strip (the strip would start in a wrong direction from that face).
89       is_face_visited_[strip_faces_[local_strip_id].back()] = false;
90       strip_faces_[local_strip_id].pop_back();
91     }
92   }
93   strip_start_corners_[local_strip_id] = start_ci;
94 
95   // Reset all visited flags for all faces (we need to process other strips from
96   // the given face before we choose the final strip that we are going to use).
97   for (int i = 0; i < strip_faces_[local_strip_id].size(); ++i) {
98     is_face_visited_[strip_faces_[local_strip_id][i]] = false;
99   }
100 }
101 
102 }  // namespace draco
103