Developer Documentation
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Modules Pages
StripifierT.cc
1 /* ========================================================================= *
2  * *
3  * OpenMesh *
4  * Copyright (c) 2001-2015, 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  * $Revision$ *
45  * $Date$ *
46  * *
47 \*===========================================================================*/
48 
49 //=============================================================================
50 //
51 // CLASS StripifierT - IMPLEMENTATION
52 //
53 //=============================================================================
54 
55 #define OPENMESH_STRIPIFIERT_C
56 
57 //== INCLUDES =================================================================
58 
59 #include <OpenMesh/Tools/Utils/StripifierT.hh>
60 #include <list>
61 
62 
63 //== NAMESPACES ===============================================================
64 
65 namespace OpenMesh {
66 
67 
68  //== IMPLEMENTATION ==========================================================
69 
70 template <class Mesh>
71 StripifierT<Mesh>::
72 StripifierT(Mesh& _mesh) :
73  mesh_(_mesh)
74 {
75 
76 }
77 
78 template <class Mesh>
79 StripifierT<Mesh>::
80 ~StripifierT() {
81 
82 }
83 
84 template <class Mesh>
85 size_t
86 StripifierT<Mesh>::
87 stripify()
88 {
89  // preprocess: add new properties
90  mesh_.add_property( processed_ );
91  mesh_.add_property( used_ );
92  mesh_.request_face_status();
93 
94  // build strips
95  clear();
96  build_strips();
97 
98  // postprocess: remove properties
99  mesh_.remove_property(processed_);
100  mesh_.remove_property(used_);
101  mesh_.release_face_status();
102 
103  return n_strips();
104 }
105 
106 
107 //-----------------------------------------------------------------------------
108 
109 
110 template <class Mesh>
111 void
112 StripifierT<Mesh>::
113 build_strips()
114 {
115  Strip experiments[3];
116  typename Mesh::HalfedgeHandle h[3];
117  FaceHandles faces[3];
118  typename FaceHandles::iterator fh_it, fh_end;
119  typename Mesh::FaceIter f_it, f_end=mesh_.faces_end();
120 
121 
122 
123  // init faces to be un-processed and un-used
124  // deleted or hidden faces are marked processed
125  if (mesh_.has_face_status())
126  {
127  for (f_it=mesh_.faces_begin(); f_it!=f_end; ++f_it)
128  if (mesh_.status(*f_it).hidden() || mesh_.status(*f_it).deleted())
129  processed(*f_it) = used(*f_it) = true;
130  else
131  processed(*f_it) = used(*f_it) = false;
132  }
133  else
134  {
135  for (f_it=mesh_.faces_begin(); f_it!=f_end; ++f_it)
136  processed(*f_it) = used(*f_it) = false;
137  }
138 
139 
140 
141  for (f_it=mesh_.faces_begin(); true; )
142  {
143  // find start face
144  for (; f_it!=f_end; ++f_it)
145  if (!processed(*f_it))
146  break;
147  if (f_it==f_end) break; // stop if all have been processed
148 
149 
150  // collect starting halfedges
151  h[0] = mesh_.halfedge_handle(*f_it);
152  h[1] = mesh_.next_halfedge_handle(h[0]);
153  h[2] = mesh_.next_halfedge_handle(h[1]);
154 
155 
156  // build 3 strips, take best one
157  size_t best_length = 0;
158  size_t best_idx = 0;
159 
160  for (size_t i=0; i<3; ++i)
161  {
162  build_strip(h[i], experiments[i], faces[i]);
163 
164  const size_t length = experiments[i].size();
165  if ( length > best_length)
166  {
167  best_length = length;
168  best_idx = i;
169  }
170 
171  for (fh_it=faces[i].begin(), fh_end=faces[i].end();
172  fh_it!=fh_end; ++fh_it)
173  used(*fh_it) = false;
174  }
175 
176 
177  // update processed status
178  fh_it = faces[best_idx].begin();
179  fh_end = faces[best_idx].end();
180  for (; fh_it!=fh_end; ++fh_it)
181  processed(*fh_it) = true;
182 
183 
184 
185  // add best strip to strip-list
186  strips_.push_back(experiments[best_idx]);
187  }
188 }
189 
190 
191 //-----------------------------------------------------------------------------
192 
193 
194 template <class Mesh>
195 void
196 StripifierT<Mesh>::
197 build_strip(typename Mesh::HalfedgeHandle _start_hh,
198  Strip& _strip,
199  FaceHandles& _faces)
200 {
201  std::list<unsigned int> strip;
202  typename Mesh::HalfedgeHandle hh;
203  typename Mesh::FaceHandle fh;
204 
205 
206  // reset face list
207  _faces.clear();
208 
209 
210  // init strip
211  strip.push_back(mesh_.from_vertex_handle(_start_hh).idx());
212  strip.push_back(mesh_.to_vertex_handle(_start_hh).idx());
213 
214 
215  // walk along the strip: 1st direction
216  hh = mesh_.prev_halfedge_handle(mesh_.opposite_halfedge_handle(_start_hh));
217  while (1)
218  {
219  // go right
220  hh = mesh_.next_halfedge_handle(hh);
221  hh = mesh_.opposite_halfedge_handle(hh);
222  hh = mesh_.next_halfedge_handle(hh);
223  if (mesh_.is_boundary(hh)) break;
224  fh = mesh_.face_handle(hh);
225  if (processed(fh) || used(fh)) break;
226  _faces.push_back(fh);
227  used(fh) = true;
228  strip.push_back(mesh_.to_vertex_handle(hh).idx());
229 
230  // go left
231  hh = mesh_.opposite_halfedge_handle(hh);
232  hh = mesh_.next_halfedge_handle(hh);
233  if (mesh_.is_boundary(hh)) break;
234  fh = mesh_.face_handle(hh);
235  if (processed(fh) || used(fh)) break;
236  _faces.push_back(fh);
237  used(fh) = true;
238  strip.push_back(mesh_.to_vertex_handle(hh).idx());
239  }
240 
241 
242  // walk along the strip: 2nd direction
243  bool flip(false);
244  hh = mesh_.prev_halfedge_handle(_start_hh);
245  while (1)
246  {
247  // go right
248  hh = mesh_.next_halfedge_handle(hh);
249  hh = mesh_.opposite_halfedge_handle(hh);
250  hh = mesh_.next_halfedge_handle(hh);
251  if (mesh_.is_boundary(hh)) break;
252  fh = mesh_.face_handle(hh);
253  if (processed(fh) || used(fh)) break;
254  _faces.push_back(fh);
255  used(fh) = true;
256  strip.push_front(mesh_.to_vertex_handle(hh).idx());
257  flip = true;
258 
259  // go left
260  hh = mesh_.opposite_halfedge_handle(hh);
261  hh = mesh_.next_halfedge_handle(hh);
262  if (mesh_.is_boundary(hh)) break;
263  fh = mesh_.face_handle(hh);
264  if (processed(fh) || used(fh)) break;
265  _faces.push_back(fh);
266  used(fh) = true;
267  strip.push_front(mesh_.to_vertex_handle(hh).idx());
268  flip = false;
269  }
270 
271  if (flip) strip.push_front(strip.front());
272 
273 
274 
275  // copy final strip to _strip
276  _strip.clear();
277  _strip.reserve(strip.size());
278  std::copy(strip.begin(), strip.end(), std::back_inserter(_strip));
279 }
280 
281 
282 //=============================================================================
283 } // namespace OpenMesh
284  //=============================================================================
OpenMesh::StripifierT::~StripifierT
~StripifierT()
Destructor.
Definition: StripifierT.cc:80
OpenMesh::StripifierT::build_strips
void build_strips()
this method does the main work
Definition: StripifierT.cc:113
OpenMesh::StripifierT::stripify
size_t stripify()
Compute triangle strips, returns number of strips.
Definition: StripifierT.cc:87
OpenMesh::StripifierT::StripifierT
StripifierT(Mesh &_mesh)
Default constructor.
Definition: StripifierT.cc:72
OpenMesh::StripifierT::build_strip
void build_strip(typename Mesh::HalfedgeHandle _start_hh, Strip &_strip, FaceHandles &_faces)
build a strip from a given halfedge (in both directions)
Definition: StripifierT.cc:197