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