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)19void 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