OpenMesh
StripifierT_impl.hh
1/* ========================================================================= *
2 * *
3 * OpenMesh *
4 * Copyright (c) 2001-2023, 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
60namespace OpenMesh {
61
62
63 //== IMPLEMENTATION ==========================================================
64
65template <class Mesh>
66StripifierT<Mesh>::
67StripifierT(Mesh& _mesh) :
68 mesh_(_mesh)
69{
70
71}
72
73template <class Mesh>
74StripifierT<Mesh>::
75~StripifierT() {
76
77}
78
79template <class Mesh>
80size_t
81StripifierT<Mesh>::
82stripify()
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
105template <class Mesh>
106void
107StripifierT<Mesh>::
108build_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
189template <class Mesh>
190void
191StripifierT<Mesh>::
192build_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::FaceHandle
Kernel::FaceHandle FaceHandle
Scalar type.
Definition: PolyMeshT.hh:139
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 .