OpenMesh
McDecimaterT_impl.hh
Go to the documentation of this file.
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
46//=============================================================================
47//
48// CLASS McDecimaterT - IMPLEMENTATION
49//
50//=============================================================================
51#define OPENMESH_MULTIPLE_CHOICE_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#ifdef WIN32
65# include <OpenMesh/Core/Utils/RandomNumberGenerator.hh>
66#endif
67
68//== NAMESPACE ===============================================================
69
70namespace OpenMesh {
71namespace Decimater {
72
73//== IMPLEMENTATION ==========================================================
74
75template<class Mesh>
77 BaseDecimaterT<Mesh>(_mesh),
78 mesh_(_mesh), randomSamples_(10) {
79
80 // default properties
81 mesh_.request_vertex_status();
82 mesh_.request_halfedge_status();
83 mesh_.request_edge_status();
84 mesh_.request_face_status();
85
86}
87
88//-----------------------------------------------------------------------------
89
90template<class Mesh>
92 // default properties
93 mesh_.release_vertex_status();
94 mesh_.release_edge_status();
95 mesh_.release_halfedge_status();
96 mesh_.release_face_status();
97
98}
99
100//-----------------------------------------------------------------------------
101template<class Mesh>
102size_t McDecimaterT<Mesh>::decimate(size_t _n_collapses, bool _only_selected) {
103
104 if (!this->is_initialized())
105 return 0;
106
107 unsigned int n_collapses(0);
108
109 bool collapsesUnchanged = false;
110 // old n_collapses in order to check for convergence
111 unsigned int oldCollapses = 0;
112 // number of iterations where no new collapses where
113 // performed in a row
114 unsigned int noCollapses = 0;
115
116#ifdef WIN32
117 RandomNumberGenerator randGen(mesh_.n_halfedges());
118#endif
119
120 const bool update_normals = mesh_.has_face_normals();
121
122 while ( n_collapses < _n_collapses) {
123
124 if (noCollapses > 20) {
125 omlog() << "[McDecimater] : no collapses performed in over 20 iterations in a row\n";
126 break;
127 }
128
129 // Optimal id and value will be collected during the random sampling
130 typename Mesh::HalfedgeHandle bestHandle(-1);
131 typename Mesh::HalfedgeHandle tmpHandle(-1);
132 double bestEnergy = FLT_MAX;
133 double energy = FLT_MAX;
134
135 // Generate random samples for collapses
136 for ( int i = 0; i < (int)randomSamples_; ++i) {
137
138 // Random halfedge handle
139#ifdef WIN32
140 tmpHandle = typename Mesh::HalfedgeHandle(int(randGen.getRand() * double(mesh_.n_halfedges() - 1.0)) );
141#else
142 tmpHandle = typename Mesh::HalfedgeHandle( (double(rand()) / double(RAND_MAX) ) * double(mesh_.n_halfedges()-1) );
143#endif
144
145 // if it is not deleted, we analyze it
146 if ( ! mesh_.status(tmpHandle).deleted() && (!_only_selected || mesh_.status(tmpHandle).selected() ) ) {
147
148 CollapseInfo ci(mesh_, tmpHandle);
149
150 // Check if legal we analyze the priority of this collapse operation
151 if (this->is_collapse_legal(ci)) {
152 energy = this->collapse_priority(ci);
153
154 if (energy != ModBaseT<Mesh>::ILLEGAL_COLLAPSE) {
155 // Check if the current samples energy is better than any energy before
156 if ( energy < bestEnergy ) {
157 bestEnergy = energy;
158 bestHandle = tmpHandle;
159 }
160 }
161 } else {
162 continue;
163 }
164 }
165
166 }
167
168 // Found the best energy?
169 if ( bestEnergy != FLT_MAX ) {
170
171 // setup collapse info
172 CollapseInfo ci(mesh_, bestHandle);
173
174 // check topological correctness AGAIN !
175 if (!this->is_collapse_legal(ci))
176 continue;
177
178 // pre-processing
179 this->preprocess_collapse(ci);
180
181 // perform collapse
182 mesh_.collapse(bestHandle);
183 ++n_collapses;
184
185 // store current collapses state
186 oldCollapses = n_collapses;
187 noCollapses = 0;
188 collapsesUnchanged = false;
189
190 // update triangle normals
191 if (update_normals)
192 {
193 typename Mesh::VertexFaceIter vf_it = mesh_.vf_iter(ci.v1);
194 for (; vf_it.is_valid(); ++vf_it)
195 if (!mesh_.status(*vf_it).deleted())
196 mesh_.set_normal(*vf_it, mesh_.calc_face_normal(*vf_it));
197 }
198
199 // post-process collapse
200 this->postprocess_collapse(ci);
201
202 // notify observer and stop if the observer requests it
203 if (!this->notify_observer(n_collapses))
204 return n_collapses;
205
206 } else {
207 if (oldCollapses == n_collapses) {
208 if (collapsesUnchanged == false) {
209 noCollapses = 1;
210 collapsesUnchanged = true;
211 } else {
212 noCollapses++;
213 }
214 }
215 }
216
217 }
218
219 // DON'T do garbage collection here! It's up to the application.
220 return n_collapses;
221}
222
223//-----------------------------------------------------------------------------
224
225template<class Mesh>
226size_t McDecimaterT<Mesh>::decimate_to_faces(size_t _nv, size_t _nf, bool _only_selected) {
227
228 if (!this->is_initialized())
229 return 0;
230
231 // check if no vertex or face contraints were set
232 if ( (_nv == 0) && (_nf == 1) )
233 return decimate_constraints_only(1.0);
234
235 size_t nv = mesh_.n_vertices();
236 size_t nf = mesh_.n_faces();
237 unsigned int n_collapses(0);
238
239
240 bool collapsesUnchanged = false;
241 // old n_collapses in order to check for convergence
242 unsigned int oldCollapses = 0;
243 // number of iterations where no new collapses where
244 // performed in a row
245 unsigned int noCollapses = 0;
246
247#ifdef WIN32
248 RandomNumberGenerator randGen(mesh_.n_halfedges());
249#endif
250
251 const bool update_normals = mesh_.has_face_normals();
252
253 while ((_nv < nv) && (_nf < nf)) {
254
255 if (noCollapses > 20) {
256 omlog() << "[McDecimater] : no collapses performed in over 20 iterations in a row\n";
257 break;
258 }
259
260 // Optimal id and value will be collected during the random sampling
261 typename Mesh::HalfedgeHandle bestHandle(-1);
262 typename Mesh::HalfedgeHandle tmpHandle(-1);
263 double bestEnergy = FLT_MAX;
264 double energy = FLT_MAX;
265
266 // Generate random samples for collapses
267 for (int i = 0; i < (int) randomSamples_; ++i) {
268
269 // Random halfedge handle
270#ifdef WIN32
271 tmpHandle = typename Mesh::HalfedgeHandle(int(randGen.getRand() * double(mesh_.n_halfedges() - 1.0)) );
272#else
273 tmpHandle = typename Mesh::HalfedgeHandle( ( double(rand()) / double(RAND_MAX) ) * double(mesh_.n_halfedges() - 1));
274#endif
275
276 // if it is not deleted, we analyze it
277 if ( ! mesh_.status(tmpHandle).deleted() && (!_only_selected || mesh_.status(tmpHandle).selected() ) ) {
278
279 CollapseInfo ci(mesh_, tmpHandle);
280
281 // Check if legal we analyze the priority of this collapse operation
282 if (this->is_collapse_legal(ci)) {
283 energy = this->collapse_priority(ci);
284
285 if (energy != ModBaseT<Mesh>::ILLEGAL_COLLAPSE) {
286 // Check if the current samples energy is better than any energy before
287 if (energy < bestEnergy) {
288 bestEnergy = energy;
289 bestHandle = tmpHandle;
290 }
291 }
292 } else {
293 continue;
294 }
295 }
296
297 }
298
299 // Found the best energy?
300 if ( bestEnergy != FLT_MAX ) {
301
302 // setup collapse info
303 CollapseInfo ci(mesh_, bestHandle);
304
305 // check topological correctness AGAIN !
306 if (!this->is_collapse_legal(ci))
307 continue;
308
309 // adjust complexity in advance (need boundary status)
310
311 // One vertex is killed by the collapse
312 --nv;
313
314 // If we are at a boundary, one face is lost,
315 // otherwise two
316 if (mesh_.is_boundary(ci.v0v1) || mesh_.is_boundary(ci.v1v0))
317 --nf;
318 else
319 nf -= 2;
320
321 // pre-processing
322 this->preprocess_collapse(ci);
323
324 // perform collapse
325 mesh_.collapse(bestHandle);
326 ++n_collapses;
327
328 // store current collapses state
329 oldCollapses = n_collapses;
330 noCollapses = 0;
331 collapsesUnchanged = false;
332
333 if (update_normals)
334 {
335 // update triangle normals
336 typename Mesh::VertexFaceIter vf_it = mesh_.vf_iter(ci.v1);
337 for (; vf_it.is_valid(); ++vf_it)
338 if (!mesh_.status(*vf_it).deleted())
339 mesh_.set_normal(*vf_it, mesh_.calc_face_normal(*vf_it));
340 }
341
342 // post-process collapse
343 this->postprocess_collapse(ci);
344
345 // notify observer and stop if the observer requests it
346 if (!this->notify_observer(n_collapses))
347 return n_collapses;
348
349 } else {
350 if (oldCollapses == n_collapses) {
351 if (collapsesUnchanged == false) {
352 noCollapses = 1;
353 collapsesUnchanged = true;
354 } else {
355 noCollapses++;
356 }
357 }
358 }
359
360 }
361
362 // DON'T do garbage collection here! It's up to the application.
363 return n_collapses;
364}
365
366//-----------------------------------------------------------------------------
367
368template<class Mesh>
369size_t McDecimaterT<Mesh>::decimate_constraints_only(float _factor, bool _only_selected) {
370
371 if (!this->is_initialized())
372 return 0;
373
374 if (_factor < 1.0)
375 this->set_error_tolerance_factor(_factor);
376
377 unsigned int n_collapses(0);
378 size_t nv = mesh_.n_vertices();
379 size_t nf = mesh_.n_faces();
380
381 bool lastCollapseIllegal = false;
382 // number of illegal collapses that occurred in a row
383 unsigned int illegalCollapses = 0;
384
385 bool collapsesUnchanged = false;
386 // old n_collapses in order to check for convergence
387 unsigned int oldCollapses = 0;
388 // number of iterations where no new collapses where
389 // performed in a row
390 unsigned int noCollapses = 0;
391
392 double energy = FLT_MAX;
393 double bestEnergy = FLT_MAX;
394
395#ifdef WIN32
396 RandomNumberGenerator randGen(mesh_.n_halfedges());
397#endif
398
399 while ((noCollapses <= 50) && (illegalCollapses <= 50) && (nv > 0) && (nf > 1)) {
400
401 // Optimal id and value will be collected during the random sampling
402 typename Mesh::HalfedgeHandle bestHandle(-1);
403 typename Mesh::HalfedgeHandle tmpHandle(-1);
404 bestEnergy = FLT_MAX;
405
406
407#ifndef WIN32
408 const double randomNormalizer = (1.0 / RAND_MAX) * (mesh_.n_halfedges() - 1);
409#endif
410
411 // Generate random samples for collapses
412 for (int i = 0; i < (int) randomSamples_; ++i) {
413
414 // Random halfedge handle
415#ifdef WIN32
416 tmpHandle = typename Mesh::HalfedgeHandle(int(randGen.getRand() * double(mesh_.n_halfedges() - 1.0)) );
417#else
418 tmpHandle = typename Mesh::HalfedgeHandle(int(rand() * randomNormalizer ) );
419#endif
420
421 // if it is not deleted, we analyze it
422 if (!mesh_.status(mesh_.edge_handle(tmpHandle)).deleted() &&
423 (!_only_selected || ( mesh_.status(mesh_.to_vertex_handle(tmpHandle)).selected() && mesh_.status(mesh_.from_vertex_handle(tmpHandle)).selected() ) ) ) {
424
425 CollapseInfo ci(mesh_, tmpHandle);
426
427 // Check if legal we analyze the priority of this collapse operation
428 if (this->is_collapse_legal(ci)) {
429
430 energy = this->collapse_priority(ci);
431
432 if (energy == ModBaseT<Mesh>::ILLEGAL_COLLAPSE) {
433 if (lastCollapseIllegal) {
434 illegalCollapses++;
435 } else {
436 illegalCollapses = 1;
437 lastCollapseIllegal = true;
438 }
439 } else {
440
441 illegalCollapses = 0;
442 lastCollapseIllegal = false;
443
444 // Check if the current samples energy is better than any energy before
445 if (energy < bestEnergy) {
446 bestEnergy = energy;
447 bestHandle = tmpHandle;
448 }
449 }
450 } else {
451
452 continue;
453 }
454 }
455
456 }
457
458
459
460 // Found the best energy?
461 if ( bestEnergy != FLT_MAX ) {
462
463 // setup collapse info
464 CollapseInfo ci(mesh_, bestHandle);
465
466 // check topological correctness AGAIN !
467 if (!this->is_collapse_legal(ci))
468 continue;
469
470 // adjust complexity in advance (need boundary status)
471
472 // One vertex is killed by the collapse
473 --nv;
474
475 // If we are at a boundary, one face is lost,
476 // otherwise two
477 if (mesh_.is_boundary(ci.v0v1) || mesh_.is_boundary(ci.v1v0))
478 --nf;
479 else
480 nf -= 2;
481
482 // pre-processing
483 this->preprocess_collapse(ci);
484
485 // perform collapse
486 mesh_.collapse(bestHandle);
487 ++n_collapses;
488
489 // store current collapses state
490 oldCollapses = n_collapses;
491 noCollapses = 0;
492 collapsesUnchanged = false;
493
494
495 // update triangle normals
496 typename Mesh::VertexFaceIter vf_it = mesh_.vf_iter(ci.v1);
497 for (; vf_it.is_valid(); ++vf_it)
498 if (!mesh_.status(*vf_it).deleted())
499 mesh_.set_normal(*vf_it, mesh_.calc_face_normal(*vf_it));
500
501 // post-process collapse
502 this->postprocess_collapse(ci);
503
504 // notify observer and stop if the observer requests it
505 if (!this->notify_observer(n_collapses))
506 return n_collapses;
507
508 } else {
509 if (oldCollapses == n_collapses) {
510 if (collapsesUnchanged == false) {
511 noCollapses = 1;
512 collapsesUnchanged = true;
513 } else {
514 noCollapses++;
515 }
516 }
517 }
518
519 }
520
521 if (_factor < 1.0)
522 this->set_error_tolerance_factor(1.0);
523
524 // DON'T do garbage collection here! It's up to the application.
525 return n_collapses;
526
527}
528
529//=============================================================================
530}// END_NS_MC_DECIMATER
531} // END_NS_OPENMESH
532//=============================================================================
533
Contains all the mesh ingredients like the polygonal mesh, the triangle mesh, different mesh kernels ...
Definition: MeshItems.hh:59
Kernel::VertexFaceIter VertexFaceIter
Circulator.
Definition: PolyMeshT.hh:166
Kernel::HalfedgeHandle HalfedgeHandle
Scalar type.
Definition: PolyMeshT.hh:137
Generate a random number between 0.0 and 1.0 with a guaranteed resolution ( Number of possible values...
Definition: RandomNumberGenerator.hh:78
double getRand() const
returns a random double between 0.0 and 1.0 with a guaranteed resolution
Definition: RandomNumberGenerator.cc:82
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
size_t decimate_constraints_only(float _factor, bool _only_selected=false)
Decimate only with constraints, while _factor gives the percentage of the constraints that should be ...
Definition: McDecimaterT_impl.hh:369
~McDecimaterT()
Destructor.
Definition: McDecimaterT_impl.hh:91
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: McDecimaterT_impl.hh:226
size_t decimate(size_t _n_collapses, bool _only_selected=false)
Decimate (perform _n_collapses collapses).
Definition: McDecimaterT_impl.hh:102
McDecimaterT(Mesh &_mesh)
Constructor.
Definition: McDecimaterT_impl.hh:76
Base class for all decimation modules.
Definition: ModBaseT.hh:193

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