Developer Documentation
DecimaterT_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 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 
66 namespace OpenMesh {
67 namespace Decimater {
68 
69 //== IMPLEMENTATION ==========================================================
70 
71 template<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 
91 template<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 
103 template<class Mesh>
104 void DecimaterT<Mesh>::heap_vertex(VertexHandle _vh) {
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 //-----------------------------------------------------------------------------
149 template<class Mesh>
150 size_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 
258 template<class Mesh>
259 size_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 
Kernel::VertexVertexIter VertexVertexIter
Circulator.
Definition: PolyMeshT.hh:162
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
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.
DecimaterT(Mesh &_mesh)
Constructor.
bool is_collapse_legal(const CollapseInfo &_ci)
void postprocess_collapse(CollapseInfo &_ci)
Post-process a collapse.
Kernel::VertexOHalfedgeIter VertexOHalfedgeIter
Circulator.
Definition: PolyMeshT.hh:163
size_t decimate(size_t _n_collapses=0, bool _only_selected=false)
Perform a number of collapses on the mesh.
Mesh::HalfedgeHandle v1v0
Reverse halfedge.
void heap_vertex(VertexHandle _vh)
Insert vertex in heap.
float collapse_priority(const CollapseInfo &_ci)
Calculate priority of an halfedge collapse (using the modules)
bool notify_observer(size_t _n_collapses)
returns false, if abort requested by observer
Mesh::VertexHandle v0
Vertex to be removed.
Mesh::VertexHandle v1
Remaining vertex.
Kernel::VertexHandle VertexHandle
Handle for referencing the corresponding item.
Definition: PolyMeshT.hh:136