Developer Documentation
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 
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>
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>
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, 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 
225 template<class Mesh>
226 size_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 
368 template<class Mesh>
369 size_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 
bool is_initialized() const
Returns whether decimater has been successfully initialized.
Mesh::HalfedgeHandle v0v1
Halfedge to be collapsed.
void preprocess_collapse(CollapseInfo &_ci)
Pre-process a collapse.
Kernel::VertexFaceIter VertexFaceIter
Circulator.
Definition: PolyMeshT.hh:166
bool is_collapse_legal(const CollapseInfo &_ci)
void postprocess_collapse(CollapseInfo &_ci)
Post-process a collapse.
Mesh::HalfedgeHandle v1v0
Reverse halfedge.
float collapse_priority(const CollapseInfo &_ci)
Calculate priority of an halfedge collapse (using the modules)
size_t decimate(size_t _n_collapses, bool _only_selected=false)
Decimate (perform _n_collapses collapses). Return number of performed collapses. If _n_collapses is n...
size_t decimate_constraints_only(float _factor, bool _only_selected=false)
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.
bool notify_observer(size_t _n_collapses)
returns false, if abort requested by observer
Mesh::VertexHandle v1
Remaining vertex.
McDecimaterT(Mesh &_mesh)
Constructor.