OpenMesh
DecimaterT_impl.hh
Go to the documentation of this file.
1/* ========================================================================= *
2 * *
3 * OpenMesh *
4 * Copyright (c) 2001-2025, 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
46//=============================================================================
47//
48// CLASS DecimaterT - IMPLEMENTATION
49//
50//=============================================================================
51#define OPENMESH_DECIMATER_DECIMATERT_CC
52
53//== INCLUDES =================================================================
54
56
57#include <vector>
58#if defined(OM_CC_MIPS)
59# include <float.h>
60#else
61# include <cfloat>
62#endif
63
64//== NAMESPACE ===============================================================
65
66namespace OpenMesh {
67namespace Decimater {
68
69//== IMPLEMENTATION ==========================================================
70
71template<class Mesh>
73 BaseDecimaterT<Mesh>(_mesh),
74 mesh_(_mesh),
75#if (defined(_MSC_VER) && (_MSC_VER >= 1800)) || __cplusplus > 199711L || defined( __GXX_EXPERIMENTAL_CXX0X__ )
76 heap_(nullptr)
77#else
78 heap_(nullptr)
79#endif
80
81{
82
83 // private vertex properties
84 mesh_.add_property(collapse_target_);
85 mesh_.add_property(priority_);
86 mesh_.add_property(heap_position_);
87}
88
89//-----------------------------------------------------------------------------
90
91template<class Mesh>
93
94 // private vertex properties
95 mesh_.remove_property(collapse_target_);
96 mesh_.remove_property(priority_);
97 mesh_.remove_property(heap_position_);
98
99}
100
101//-----------------------------------------------------------------------------
102
103template<class Mesh>
105 // std::clog << "heap_vertex: " << _vh << std::endl;
106
107 float prio, best_prio(FLT_MAX);
108 typename Mesh::HalfedgeHandle heh, collapse_target;
109
110 // find best target in one ring
111 typename Mesh::VertexOHalfedgeIter voh_it(mesh_, _vh);
112 for (; voh_it.is_valid(); ++voh_it) {
113 heh = *voh_it;
114 CollapseInfo ci(mesh_, heh);
115
116 if (this->is_collapse_legal(ci)) {
117 prio = this->collapse_priority(ci);
118 if (prio >= 0.0 && prio < best_prio) {
119 best_prio = prio;
120 collapse_target = heh;
121 }
122 }
123 }
124
125 // target found -> put vertex on heap
126 if (collapse_target.is_valid()) {
127 // std::clog << " added|updated" << std::endl;
128 mesh_.property(collapse_target_, _vh) = collapse_target;
129 mesh_.property(priority_, _vh) = best_prio;
130
131 if (heap_->is_stored(_vh))
132 heap_->update(_vh);
133 else
134 heap_->insert(_vh);
135 }
136
137 // not valid -> remove from heap
138 else {
139 // std::clog << " n/a|removed" << std::endl;
140 if (heap_->is_stored(_vh))
141 heap_->remove(_vh);
142
143 mesh_.property(collapse_target_, _vh) = collapse_target;
144 mesh_.property(priority_, _vh) = -1;
145 }
146}
147
148//-----------------------------------------------------------------------------
149template<class Mesh>
150size_t DecimaterT<Mesh>::decimate(size_t _n_collapses, bool _only_selected) {
151
152 if (!this->is_initialized())
153 return 0;
154
155 typename Mesh::VertexHandle vp;
156 typename Mesh::HalfedgeHandle v0v1;
157 typename Mesh::VertexVertexIter vv_it;
158 typename Mesh::VertexFaceIter vf_it;
159 unsigned int n_collapses(0);
160
161 typedef std::vector<typename Mesh::VertexHandle> Support;
162 typedef typename Support::iterator SupportIterator;
163
164 Support support(15);
165 SupportIterator s_it, s_end;
166
167 // check _n_collapses
168 if (!_n_collapses)
169 _n_collapses = mesh_.n_vertices();
170
171 // initialize heap
172 HeapInterface HI(mesh_, priority_, heap_position_);
173
174#if (defined(_MSC_VER) && (_MSC_VER >= 1800)) || __cplusplus > 199711L || defined( __GXX_EXPERIMENTAL_CXX0X__ )
175 heap_ = std::unique_ptr<DeciHeap>(new DeciHeap(HI));
176#else
177 heap_ = std::auto_ptr<DeciHeap>(new DeciHeap(HI));
178#endif
179
180
181 heap_->reserve(mesh_.n_vertices());
182
183 for ( auto v_it : mesh_.vertices() ) {
184 heap_->reset_heap_position(v_it);
185
186 if (!mesh_.status(v_it).deleted()) {
187 if (!_only_selected || mesh_.status(v_it).selected() ) {
188 heap_vertex(v_it);
189 }
190 }
191
192 }
193
194 const bool update_normals = mesh_.has_face_normals();
195
196 // process heap
197 while ((!heap_->empty()) && (n_collapses < _n_collapses)) {
198 // get 1st heap entry
199 vp = heap_->front();
200 v0v1 = mesh_.property(collapse_target_, vp);
201 heap_->pop_front();
202
203 // setup collapse info
204 CollapseInfo ci(mesh_, v0v1);
205
206 // check topological correctness AGAIN !
207 if (!this->is_collapse_legal(ci))
208 continue;
209
210 // store support (= one ring of *vp)
211 vv_it = mesh_.vv_iter(ci.v0);
212 support.clear();
213 for (; vv_it.is_valid(); ++vv_it)
214 support.push_back(*vv_it);
215
216 // pre-processing
217 this->preprocess_collapse(ci);
218
219 // perform collapse
220 mesh_.collapse(v0v1);
221 ++n_collapses;
222
223 if (update_normals)
224 {
225 // update triangle normals
226 vf_it = mesh_.vf_iter(ci.v1);
227 for (; vf_it.is_valid(); ++vf_it)
228 if (!mesh_.status(*vf_it).deleted())
229 mesh_.set_normal(*vf_it, mesh_.calc_face_normal(*vf_it));
230 }
231
232 // post-process collapse
233 this->postprocess_collapse(ci);
234
235 // update heap (former one ring of decimated vertex)
236 for (s_it = support.begin(), s_end = support.end(); s_it != s_end; ++s_it) {
237 assert(!mesh_.status(*s_it).deleted());
238 if (!_only_selected || mesh_.status(*s_it).selected() )
239 heap_vertex(*s_it);
240 }
241
242 // notify observer and stop if the observer requests it
243 if (!this->notify_observer(n_collapses))
244 return n_collapses;
245 }
246
247 // delete heap
248 heap_.reset();
249
250
251
252 // DON'T do garbage collection here! It's up to the application.
253 return n_collapses;
254}
255
256//-----------------------------------------------------------------------------
257
258template<class Mesh>
259size_t DecimaterT<Mesh>::decimate_to_faces(size_t _nv, size_t _nf, bool _only_selected) {
260
261 if (!this->is_initialized())
262 return 0;
263
264 if (_nv >= mesh_.n_vertices() || _nf >= mesh_.n_faces())
265 return 0;
266
267 typename Mesh::VertexHandle vp;
268 typename Mesh::HalfedgeHandle v0v1;
269 typename Mesh::VertexVertexIter vv_it;
270 typename Mesh::VertexFaceIter vf_it;
271 size_t nv = mesh_.n_vertices();
272 size_t nf = mesh_.n_faces();
273 unsigned int n_collapses = 0;
274
275 typedef std::vector<typename Mesh::VertexHandle> Support;
276 typedef typename Support::iterator SupportIterator;
277
278 Support support(15);
279 SupportIterator s_it, s_end;
280
281 // initialize heap
282 HeapInterface HI(mesh_, priority_, heap_position_);
283 #if (defined(_MSC_VER) && (_MSC_VER >= 1800)) || __cplusplus > 199711L || defined( __GXX_EXPERIMENTAL_CXX0X__ )
284 heap_ = std::unique_ptr<DeciHeap>(new DeciHeap(HI));
285 #else
286 heap_ = std::auto_ptr<DeciHeap>(new DeciHeap(HI));
287 #endif
288 heap_->reserve(mesh_.n_vertices());
289
290 for ( auto v_it : mesh_.vertices() ) {
291 heap_->reset_heap_position(v_it);
292 if (!mesh_.status(v_it).deleted()) {
293 if (!_only_selected || mesh_.status(v_it).selected() ) {
294 heap_vertex(v_it);
295 }
296 }
297 }
298
299 const bool update_normals = mesh_.has_face_normals();
300
301 // process heap
302 while ((!heap_->empty()) && (_nv < nv) && (_nf < nf)) {
303 // get 1st heap entry
304 vp = heap_->front();
305 v0v1 = mesh_.property(collapse_target_, vp);
306 heap_->pop_front();
307
308 // setup collapse info
309 CollapseInfo ci(mesh_, v0v1);
310
311 // check topological correctness AGAIN !
312 if (!this->is_collapse_legal(ci))
313 continue;
314
315 // store support (= one ring of *vp)
316 vv_it = mesh_.vv_iter(ci.v0);
317 support.clear();
318 for (; vv_it.is_valid(); ++vv_it)
319 support.push_back(*vv_it);
320
321 // adjust complexity in advance (need boundary status)
322 ++n_collapses;
323 --nv;
324 if (mesh_.is_boundary(ci.v0v1) || mesh_.is_boundary(ci.v1v0))
325 --nf;
326 else
327 nf -= 2;
328
329 // pre-processing
330 this->preprocess_collapse(ci);
331
332 // perform collapse
333 mesh_.collapse(v0v1);
334
335 // update triangle normals
336 if (update_normals)
337 {
338 vf_it = mesh_.vf_iter(ci.v1);
339 for (; vf_it.is_valid(); ++vf_it)
340 if (!mesh_.status(*vf_it).deleted())
341 mesh_.set_normal(*vf_it, mesh_.calc_face_normal(*vf_it));
342 }
343
344 // post-process collapse
345 this->postprocess_collapse(ci);
346
347 // update heap (former one ring of decimated vertex)
348 for (s_it = support.begin(), s_end = support.end(); s_it != s_end; ++s_it) {
349 assert(!mesh_.status(*s_it).deleted());
350 if (!_only_selected || mesh_.status(*s_it).selected() )
351 heap_vertex(*s_it);
352 }
353
354 // notify observer and stop if the observer requests it
355 if (!this->notify_observer(n_collapses))
356 return n_collapses;
357 }
358
359 // delete heap
360 heap_.reset();
361
362
363 // DON'T do garbage collection here! It's up to the application.
364 return n_collapses;
365}
366
367//=============================================================================
368}// END_NS_DECIMATER
369} // END_NS_OPENMESH
370//=============================================================================
371
Contains all the mesh ingredients like the polygonal mesh, the triangle mesh, different mesh kernels ...
Definition: MeshItems.hh:59
Handle for a vertex entity.
Definition: Handles.hh:121
Kernel::VertexFaceIter VertexFaceIter
Circulator.
Definition: PolyMeshT.hh:166
Kernel::VertexOHalfedgeIter VertexOHalfedgeIter
Circulator.
Definition: PolyMeshT.hh:163
Kernel::HalfedgeHandle HalfedgeHandle
Scalar type.
Definition: PolyMeshT.hh:137
Kernel::VertexVertexIter VertexVertexIter
Circulator.
Definition: PolyMeshT.hh:162
Definition: BaseDecimaterT.hh:86
Stores information about a halfedge collapse.
Definition: CollapseInfoT.hh:74
Mesh::HalfedgeHandle v0v1
Halfedge to be collapsed.
Definition: CollapseInfoT.hh:80
Mesh::HalfedgeHandle v1v0
Reverse halfedge.
Definition: CollapseInfoT.hh:81
Mesh::VertexHandle v1
Remaining vertex.
Definition: CollapseInfoT.hh:83
Mesh::VertexHandle v0
Vertex to be removed.
Definition: CollapseInfoT.hh:82
Decimater framework.
Definition: DecimaterT.hh:79
size_t decimate(size_t _n_collapses=0, bool _only_selected=false)
Perform a number of collapses on the mesh.
Definition: DecimaterT_impl.hh:150
size_t decimate_to_faces(size_t _n_vertices=0, size_t _n_faces=0, bool _only_selected=false)
Attempts to decimate the mesh until a desired vertex or face complexity is achieved.
Definition: DecimaterT_impl.hh:259
~DecimaterT()
Destructor.
Definition: DecimaterT_impl.hh:92
DecimaterT(Mesh &_mesh)
Constructor.
Definition: DecimaterT_impl.hh:72
Heap interface.
Definition: DecimaterT.hh:149
An efficient, highly customizable heap.
Definition: HeapT.hh:139

Project OpenMesh, ©  Visual Computing Institute, RWTH Aachen. Documentation generated using doxygen .