OpenMesh
StripifierT_impl.hh
1 /* ========================================================================= *
2  * *
3  * OpenMesh *
4  * Copyright (c) 2001-2022, RWTH-Aachen University *
5  * Department of Computer Graphics and Multimedia *
6  * All rights reserved. *
7  * www.openmesh.org *
8  * *
9  *---------------------------------------------------------------------------*
10  * This file is part of OpenMesh. *
11  *---------------------------------------------------------------------------*
12  * *
13  * Redistribution and use in source and binary forms, with or without *
14  * modification, are permitted provided that the following conditions *
15  * are met: *
16  * *
17  * 1. Redistributions of source code must retain the above copyright notice, *
18  * this list of conditions and the following disclaimer. *
19  * *
20  * 2. Redistributions in binary form must reproduce the above copyright *
21  * notice, this list of conditions and the following disclaimer in the *
22  * documentation and/or other materials provided with the distribution. *
23  * *
24  * 3. Neither the name of the copyright holder nor the names of its *
25  * contributors may be used to endorse or promote products derived from *
26  * this software without specific prior written permission. *
27  * *
28  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS *
29  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED *
30  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A *
31  * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER *
32  * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, *
33  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, *
34  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR *
35  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF *
36  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING *
37  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS *
38  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. *
39  * *
40  * ========================================================================= */
41 
42 
43 
44 //=============================================================================
45 //
46 // CLASS StripifierT - IMPLEMENTATION
47 //
48 //=============================================================================
49 
50 #define OPENMESH_STRIPIFIERT_C
51 
52 //== INCLUDES =================================================================
53 
54 #include <OpenMesh/Tools/Utils/StripifierT.hh>
55 #include <list>
56 
57 
58 //== NAMESPACES ===============================================================
59 
60 namespace OpenMesh {
61 
62 
63  //== IMPLEMENTATION ==========================================================
64 
65 template <class Mesh>
66 StripifierT<Mesh>::
67 StripifierT(Mesh& _mesh) :
68  mesh_(_mesh)
69 {
70 
71 }
72 
73 template <class Mesh>
74 StripifierT<Mesh>::
75 ~StripifierT() {
76 
77 }
78 
79 template <class Mesh>
80 size_t
81 StripifierT<Mesh>::
82 stripify()
83 {
84  // preprocess: add new properties
85  mesh_.add_property( processed_ );
86  mesh_.add_property( used_ );
87  mesh_.request_face_status();
88 
89  // build strips
90  clear();
91  build_strips();
92 
93  // postprocess: remove properties
94  mesh_.remove_property(processed_);
95  mesh_.remove_property(used_);
96  mesh_.release_face_status();
97 
98  return n_strips();
99 }
100 
101 
102 //-----------------------------------------------------------------------------
103 
104 
105 template <class Mesh>
106 void
107 StripifierT<Mesh>::
108 build_strips()
109 {
110  Strip experiments[3];
111  typename Mesh::HalfedgeHandle h[3];
112  FaceHandles faces[3];
113  typename FaceHandles::iterator fh_it, fh_end;
114  typename Mesh::FaceIter f_it, f_end=mesh_.faces_end();
115 
116 
117 
118  // init faces to be un-processed and un-used
119  // deleted or hidden faces are marked processed
120  if (mesh_.has_face_status())
121  {
122  for (f_it=mesh_.faces_begin(); f_it!=f_end; ++f_it)
123  if (mesh_.status(*f_it).hidden() || mesh_.status(*f_it).deleted())
124  processed(*f_it) = used(*f_it) = true;
125  else
126  processed(*f_it) = used(*f_it) = false;
127  }
128  else
129  {
130  for (f_it=mesh_.faces_begin(); f_it!=f_end; ++f_it)
131  processed(*f_it) = used(*f_it) = false;
132  }
133 
134 
135 
136  for (f_it=mesh_.faces_begin(); true; )
137  {
138  // find start face
139  for (; f_it!=f_end; ++f_it)
140  if (!processed(*f_it))
141  break;
142  if (f_it==f_end) break; // stop if all have been processed
143 
144 
145  // collect starting halfedges
146  h[0] = mesh_.halfedge_handle(*f_it);
147  h[1] = mesh_.next_halfedge_handle(h[0]);
148  h[2] = mesh_.next_halfedge_handle(h[1]);
149 
150 
151  // build 3 strips, take best one
152  size_t best_length = 0;
153  size_t best_idx = 0;
154 
155  for (size_t i=0; i<3; ++i)
156  {
157  build_strip(h[i], experiments[i], faces[i]);
158 
159  const size_t length = experiments[i].size();
160  if ( length > best_length)
161  {
162  best_length = length;
163  best_idx = i;
164  }
165 
166  for (fh_it=faces[i].begin(), fh_end=faces[i].end();
167  fh_it!=fh_end; ++fh_it)
168  used(*fh_it) = false;
169  }
170 
171 
172  // update processed status
173  fh_it = faces[best_idx].begin();
174  fh_end = faces[best_idx].end();
175  for (; fh_it!=fh_end; ++fh_it)
176  processed(*fh_it) = true;
177 
178 
179 
180  // add best strip to strip-list
181  strips_.push_back(experiments[best_idx]);
182  }
183 }
184 
185 
186 //-----------------------------------------------------------------------------
187 
188 
189 template <class Mesh>
190 void
191 StripifierT<Mesh>::
192 build_strip(typename Mesh::HalfedgeHandle _start_hh,
193  Strip& _strip,
194  FaceHandles& _faces)
195 {
196  std::list<unsigned int> strip;
197  typename Mesh::HalfedgeHandle hh;
198  typename Mesh::FaceHandle fh;
199 
200 
201  // reset face list
202  _faces.clear();
203 
204 
205  // init strip
206  strip.push_back(mesh_.from_vertex_handle(_start_hh).idx());
207  strip.push_back(mesh_.to_vertex_handle(_start_hh).idx());
208 
209 
210  // walk along the strip: 1st direction
211  hh = mesh_.prev_halfedge_handle(mesh_.opposite_halfedge_handle(_start_hh));
212  while (1)
213  {
214  // go right
215  hh = mesh_.next_halfedge_handle(hh);
216  hh = mesh_.opposite_halfedge_handle(hh);
217  hh = mesh_.next_halfedge_handle(hh);
218  if (mesh_.is_boundary(hh)) break;
219  fh = mesh_.face_handle(hh);
220  if (processed(fh) || used(fh)) break;
221  _faces.push_back(fh);
222  used(fh) = true;
223  strip.push_back(mesh_.to_vertex_handle(hh).idx());
224 
225  // go left
226  hh = mesh_.opposite_halfedge_handle(hh);
227  hh = mesh_.next_halfedge_handle(hh);
228  if (mesh_.is_boundary(hh)) break;
229  fh = mesh_.face_handle(hh);
230  if (processed(fh) || used(fh)) break;
231  _faces.push_back(fh);
232  used(fh) = true;
233  strip.push_back(mesh_.to_vertex_handle(hh).idx());
234  }
235 
236 
237  // walk along the strip: 2nd direction
238  bool flip(false);
239  hh = mesh_.prev_halfedge_handle(_start_hh);
240  while (1)
241  {
242  // go right
243  hh = mesh_.next_halfedge_handle(hh);
244  hh = mesh_.opposite_halfedge_handle(hh);
245  hh = mesh_.next_halfedge_handle(hh);
246  if (mesh_.is_boundary(hh)) break;
247  fh = mesh_.face_handle(hh);
248  if (processed(fh) || used(fh)) break;
249  _faces.push_back(fh);
250  used(fh) = true;
251  strip.push_front(mesh_.to_vertex_handle(hh).idx());
252  flip = true;
253 
254  // go left
255  hh = mesh_.opposite_halfedge_handle(hh);
256  hh = mesh_.next_halfedge_handle(hh);
257  if (mesh_.is_boundary(hh)) break;
258  fh = mesh_.face_handle(hh);
259  if (processed(fh) || used(fh)) break;
260  _faces.push_back(fh);
261  used(fh) = true;
262  strip.push_front(mesh_.to_vertex_handle(hh).idx());
263  flip = false;
264  }
265 
266  if (flip) strip.push_front(strip.front());
267 
268 
269 
270  // copy final strip to _strip
271  _strip.clear();
272  _strip.reserve(strip.size());
273  std::copy(strip.begin(), strip.end(), std::back_inserter(_strip));
274 }
275 
276 
277 //=============================================================================
278 } // namespace OpenMesh
279  //=============================================================================
OpenMesh
Contains all the mesh ingredients like the polygonal mesh, the triangle mesh, different mesh kernels ...
Definition: MeshItems.hh:59
OpenMesh::PolyMeshT::FaceIter
Kernel::FaceIter FaceIter
Scalar type.
Definition: PolyMeshT.hh:146
OpenMesh::PolyMeshT::HalfedgeHandle
Kernel::HalfedgeHandle HalfedgeHandle
Scalar type.
Definition: PolyMeshT.hh:137
OpenMesh::StripifierT
This class decomposes a triangle mesh into several triangle strips.
Definition: StripifierT.hh:80
OpenMesh::StripifierT::stripify
size_t stripify()
Compute triangle strips, returns number of strips.
Definition: StripifierT_impl.hh:82
OpenMesh::StripifierT::~StripifierT
~StripifierT()
Destructor.
Definition: StripifierT_impl.hh:75
OpenMesh::StripifierT::StripifierT
StripifierT(Mesh &_mesh)
Default constructor.
Definition: StripifierT_impl.hh:67
Project OpenMesh, ©  Visual Computing Institute, RWTH Aachen. Documentation generated using doxygen .