| OpenMesh

McDecimaterT_impl.hh
Go to the documentation of this file.
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
46 //=============================================================================
47 //
48 // CLASS McDecimaterT - IMPLEMENTATION
49 //
50 //=============================================================================
51 #define OPENMESH_MULTIPLE_CHOICE_DECIMATER_DECIMATERT_CC
52
53 //== INCLUDES =================================================================
54
55 #include <OpenMesh/Tools/Decimater/McDecimaterT.hh>
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
70 namespace OpenMesh {
71 namespace Decimater {
72
73 //== IMPLEMENTATION ==========================================================
74
75 template<class Mesh>
76 McDecimaterT<Mesh>::McDecimaterT(Mesh& _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
90 template<class Mesh>
91 McDecimaterT<Mesh>::~McDecimaterT() {
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 //-----------------------------------------------------------------------------
101 template<class Mesh>
102 size_t McDecimaterT<Mesh>::decimate(size_t _n_collapses) {
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 analyse it
146 if ( ! mesh_.status(tmpHandle).deleted() ) {
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
225 template<class Mesh>
226 size_t McDecimaterT<Mesh>::decimate_to_faces(size_t _nv, size_t _nf) {
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 analyse it
277 if (!mesh_.status(tmpHandle).deleted()) {
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
368 template<class Mesh>
369 size_t McDecimaterT<Mesh>::decimate_constraints_only(float _factor) {
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
424 CollapseInfo ci(mesh_, tmpHandle);
425
426 // Check if legal we analyze the priority of this collapse operation
427 if (this->is_collapse_legal(ci)) {
428
429 energy = this->collapse_priority(ci);
430
431 if (energy == ModBaseT<Mesh>::ILLEGAL_COLLAPSE) {
432 if (lastCollapseIllegal) {
433 illegalCollapses++;
434 } else {
435 illegalCollapses = 1;
436 lastCollapseIllegal = true;
437 }
438 } else {
439
440 illegalCollapses = 0;
441 lastCollapseIllegal = false;
442
443 // Check if the current samples energy is better than any energy before
444 if (energy < bestEnergy) {
445 bestEnergy = energy;
446 bestHandle = tmpHandle;
447 }
448 }
449 } else {
450
451 continue;
452 }
453 }
454
455 }
456
457
458
459 // Found the best energy?
460 if ( bestEnergy != FLT_MAX ) {
461
462 // setup collapse info
463 CollapseInfo ci(mesh_, bestHandle);
464
465 // check topological correctness AGAIN !
466 if (!this->is_collapse_legal(ci))
467 continue;
468
469 // adjust complexity in advance (need boundary status)
470
471 // One vertex is killed by the collapse
472 --nv;
473
474 // If we are at a boundary, one face is lost,
475 // otherwise two
476 if (mesh_.is_boundary(ci.v0v1) || mesh_.is_boundary(ci.v1v0))
477 --nf;
478 else
479 nf -= 2;
480
481 // pre-processing
482 this->preprocess_collapse(ci);
483
484 // perform collapse
485 mesh_.collapse(bestHandle);
486 ++n_collapses;
487
488 // store current collapses state
489 oldCollapses = n_collapses;
490 noCollapses = 0;
491 collapsesUnchanged = false;
492
493
494 // update triangle normals
495 typename Mesh::VertexFaceIter vf_it = mesh_.vf_iter(ci.v1);
496 for (; vf_it.is_valid(); ++vf_it)
497 if (!mesh_.status(*vf_it).deleted())
498 mesh_.set_normal(*vf_it, mesh_.calc_face_normal(*vf_it));
499
500 // post-process collapse
501 this->postprocess_collapse(ci);
502
503 // notify observer and stop if the observer requests it
504 if (!this->notify_observer(n_collapses))
505 return n_collapses;
506
507 } else {
508 if (oldCollapses == n_collapses) {
509 if (collapsesUnchanged == false) {
510 noCollapses = 1;
511 collapsesUnchanged = true;
512 } else {
513 noCollapses++;
514 }
515 }
516 }
517
518 }
519
520 if (_factor < 1.0)
521 this->set_error_tolerance_factor(1.0);
522
523 // DON'T do garbage collection here! It's up to the application.
524 return n_collapses;
525
526 }
527
528 //=============================================================================
529 }// END_NS_MC_DECIMATER
530 } // END_NS_OPENMESH
531 //=============================================================================
532
McDecimaterT.hh
OpenMesh::Decimater::ModBaseT
Base class for all decimation modules.
Definition: ModBaseT.hh:192
OpenMesh::Decimater::CollapseInfoT::v0v1
Mesh::HalfedgeHandle v0v1
Halfedge to be collapsed.
Definition: CollapseInfoT.hh:89
OpenMesh::PolyMeshT::VertexFaceIter
Kernel::VertexFaceIter VertexFaceIter
Circulator.
Definition: PolyMeshT.hh:166
OpenMesh::Decimater::McDecimaterT::~McDecimaterT
~McDecimaterT()
Destructor.
Definition: McDecimaterT_impl.hh:91
OpenMesh::Decimater::McDecimaterT::decimate
size_t decimate(size_t _n_collapses)
Decimate (perform _n_collapses collapses).
Definition: McDecimaterT_impl.hh:102
OpenMesh::Decimater::BaseDecimaterT
Definition: BaseDecimaterT.hh:85
OpenMesh::Decimater::CollapseInfoT::v1v0
Mesh::HalfedgeHandle v1v0
Reverse halfedge.
Definition: CollapseInfoT.hh:90
OpenMesh::Decimater::BaseDecimaterT::set_error_tolerance_factor
void set_error_tolerance_factor(double _factor)
This provides a function that allows the setting of a percentage of the original constraint of the mo...
Definition: BaseDecimaterT_impl.hh:191
OpenMesh::Decimater::BaseDecimaterT::collapse_priority
float collapse_priority(const CollapseInfo &_ci)
Calculate priority of an halfedge collapse (using the modules)
Definition: BaseDecimaterT_impl.hh:154
OpenMesh::Decimater::McDecimaterT::McDecimaterT
McDecimaterT(Mesh &_mesh)
Constructor.
Definition: McDecimaterT_impl.hh:76
OpenMesh::Decimater::McDecimaterT::decimate_to_faces
size_t decimate_to_faces(size_t _n_vertices=0, size_t _n_faces=0)
Decimate to target complexity (vertices and faces).
Definition: McDecimaterT_impl.hh:226
OpenMesh
Contains all the mesh ingredients like the polygonal mesh, the triangle mesh, different mesh kernels ...
Definition: MeshItems.hh:59
OpenMesh::RandomNumberGenerator
Generate a random number between 0.0 and 1.0 with a guaranteed resolution ( Number of possible values...
Definition: RandomNumberGenerator.hh:77
OpenMesh::Decimater::CollapseInfoT::v1
Mesh::VertexHandle v1
Remaining vertex.
Definition: CollapseInfoT.hh:92
OpenMesh::Decimater::BaseDecimaterT::is_collapse_legal
bool is_collapse_legal(const CollapseInfo &_ci)
Is an edge collapse legal? Performs topological test only.
Definition: BaseDecimaterT_impl.hh:100
OpenMesh::Decimater::BaseDecimaterT::preprocess_collapse
void preprocess_collapse(CollapseInfo &_ci)
Pre-process a collapse.
Definition: BaseDecimaterT_impl.hh:179
OpenMesh::Decimater::McDecimaterT::decimate_constraints_only
size_t decimate_constraints_only(float _factor)
Decimate only with constraints, while _factor gives the percentage of the constraints that should be ...
Definition: McDecimaterT_impl.hh:369
OpenMesh::Decimater::CollapseInfoT
Stores information about a halfedge collapse.
Definition: CollapseInfoT.hh:74
OpenMesh::Decimater::BaseDecimaterT::notify_observer
bool notify_observer(size_t _n_collapses)
returns false, if abort requested by observer
Definition: BaseDecimaterT.hh:191
OpenMesh::Decimater::BaseDecimaterT::postprocess_collapse
void postprocess_collapse(CollapseInfo &_ci)
Post-process a collapse.
Definition: BaseDecimaterT_impl.hh:167
OpenMesh::Decimater::BaseDecimaterT::is_initialized
bool is_initialized() const
Returns whether decimater has been successfully initialized.
Definition: BaseDecimaterT.hh:111