OpenMesh
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_(NULL)
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) {
151 
152  if (!this->is_initialized())
153  return 0;
154 
155  typename Mesh::VertexIter v_it, v_end(mesh_.vertices_end());
156  typename Mesh::VertexHandle vp;
157  typename Mesh::HalfedgeHandle v0v1;
158  typename Mesh::VertexVertexIter vv_it;
159  typename Mesh::VertexFaceIter vf_it;
160  unsigned int n_collapses(0);
161 
162  typedef std::vector<typename Mesh::VertexHandle> Support;
163  typedef typename Support::iterator SupportIterator;
164 
165  Support support(15);
166  SupportIterator s_it, s_end;
167 
168  // check _n_collapses
169  if (!_n_collapses)
170  _n_collapses = mesh_.n_vertices();
171 
172  // initialize heap
173  HeapInterface HI(mesh_, priority_, heap_position_);
174 
175 #if (defined(_MSC_VER) && (_MSC_VER >= 1800)) || __cplusplus > 199711L || defined( __GXX_EXPERIMENTAL_CXX0X__ )
176  heap_ = std::unique_ptr<DeciHeap>(new DeciHeap(HI));
177 #else
178  heap_ = std::auto_ptr<DeciHeap>(new DeciHeap(HI));
179 #endif
180 
181 
182  heap_->reserve(mesh_.n_vertices());
183 
184  for (v_it = mesh_.vertices_begin(); v_it != v_end; ++v_it) {
185  heap_->reset_heap_position(*v_it);
186  if (!mesh_.status(*v_it).deleted())
187  heap_vertex(*v_it);
188  }
189 
190  const bool update_normals = mesh_.has_face_normals();
191 
192  // process heap
193  while ((!heap_->empty()) && (n_collapses < _n_collapses)) {
194  // get 1st heap entry
195  vp = heap_->front();
196  v0v1 = mesh_.property(collapse_target_, vp);
197  heap_->pop_front();
198 
199  // setup collapse info
200  CollapseInfo ci(mesh_, v0v1);
201 
202  // check topological correctness AGAIN !
203  if (!this->is_collapse_legal(ci))
204  continue;
205 
206  // store support (= one ring of *vp)
207  vv_it = mesh_.vv_iter(ci.v0);
208  support.clear();
209  for (; vv_it.is_valid(); ++vv_it)
210  support.push_back(*vv_it);
211 
212  // pre-processing
213  this->preprocess_collapse(ci);
214 
215  // perform collapse
216  mesh_.collapse(v0v1);
217  ++n_collapses;
218 
219  if (update_normals)
220  {
221  // update triangle normals
222  vf_it = mesh_.vf_iter(ci.v1);
223  for (; vf_it.is_valid(); ++vf_it)
224  if (!mesh_.status(*vf_it).deleted())
225  mesh_.set_normal(*vf_it, mesh_.calc_face_normal(*vf_it));
226  }
227 
228  // post-process collapse
229  this->postprocess_collapse(ci);
230 
231  // update heap (former one ring of decimated vertex)
232  for (s_it = support.begin(), s_end = support.end(); s_it != s_end; ++s_it) {
233  assert(!mesh_.status(*s_it).deleted());
234  heap_vertex(*s_it);
235  }
236 
237  // notify observer and stop if the observer requests it
238  if (!this->notify_observer(n_collapses))
239  return n_collapses;
240  }
241 
242  // delete heap
243  heap_.reset();
244 
245 
246 
247  // DON'T do garbage collection here! It's up to the application.
248  return n_collapses;
249 }
250 
251 //-----------------------------------------------------------------------------
252 
253 template<class Mesh>
254 size_t DecimaterT<Mesh>::decimate_to_faces(size_t _nv, size_t _nf) {
255 
256  if (!this->is_initialized())
257  return 0;
258 
259  if (_nv >= mesh_.n_vertices() || _nf >= mesh_.n_faces())
260  return 0;
261 
262  typename Mesh::VertexIter v_it, v_end(mesh_.vertices_end());
263  typename Mesh::VertexHandle vp;
264  typename Mesh::HalfedgeHandle v0v1;
265  typename Mesh::VertexVertexIter vv_it;
266  typename Mesh::VertexFaceIter vf_it;
267  size_t nv = mesh_.n_vertices();
268  size_t nf = mesh_.n_faces();
269  unsigned int n_collapses = 0;
270 
271  typedef std::vector<typename Mesh::VertexHandle> Support;
272  typedef typename Support::iterator SupportIterator;
273 
274  Support support(15);
275  SupportIterator s_it, s_end;
276 
277  // initialize heap
278  HeapInterface HI(mesh_, priority_, heap_position_);
279  #if (defined(_MSC_VER) && (_MSC_VER >= 1800)) || __cplusplus > 199711L || defined( __GXX_EXPERIMENTAL_CXX0X__ )
280  heap_ = std::unique_ptr<DeciHeap>(new DeciHeap(HI));
281  #else
282  heap_ = std::auto_ptr<DeciHeap>(new DeciHeap(HI));
283  #endif
284  heap_->reserve(mesh_.n_vertices());
285 
286  for (v_it = mesh_.vertices_begin(); v_it != v_end; ++v_it) {
287  heap_->reset_heap_position(*v_it);
288  if (!mesh_.status(*v_it).deleted())
289  heap_vertex(*v_it);
290  }
291 
292  const bool update_normals = mesh_.has_face_normals();
293 
294  // process heap
295  while ((!heap_->empty()) && (_nv < nv) && (_nf < nf)) {
296  // get 1st heap entry
297  vp = heap_->front();
298  v0v1 = mesh_.property(collapse_target_, vp);
299  heap_->pop_front();
300 
301  // setup collapse info
302  CollapseInfo ci(mesh_, v0v1);
303 
304  // check topological correctness AGAIN !
305  if (!this->is_collapse_legal(ci))
306  continue;
307 
308  // store support (= one ring of *vp)
309  vv_it = mesh_.vv_iter(ci.v0);
310  support.clear();
311  for (; vv_it.is_valid(); ++vv_it)
312  support.push_back(*vv_it);
313 
314  // adjust complexity in advance (need boundary status)
315  ++n_collapses;
316  --nv;
317  if (mesh_.is_boundary(ci.v0v1) || mesh_.is_boundary(ci.v1v0))
318  --nf;
319  else
320  nf -= 2;
321 
322  // pre-processing
323  this->preprocess_collapse(ci);
324 
325  // perform collapse
326  mesh_.collapse(v0v1);
327 
328  // update triangle normals
329  if (update_normals)
330  {
331  vf_it = mesh_.vf_iter(ci.v1);
332  for (; vf_it.is_valid(); ++vf_it)
333  if (!mesh_.status(*vf_it).deleted())
334  mesh_.set_normal(*vf_it, mesh_.calc_face_normal(*vf_it));
335  }
336 
337  // post-process collapse
338  this->postprocess_collapse(ci);
339 
340  // update heap (former one ring of decimated vertex)
341  for (s_it = support.begin(), s_end = support.end(); s_it != s_end; ++s_it) {
342  assert(!mesh_.status(*s_it).deleted());
343  heap_vertex(*s_it);
344  }
345 
346  // notify observer and stop if the observer requests it
347  if (!this->notify_observer(n_collapses))
348  return n_collapses;
349  }
350 
351  // delete heap
352  heap_.reset();
353 
354 
355  // DON'T do garbage collection here! It's up to the application.
356  return n_collapses;
357 }
358 
359 //=============================================================================
360 }// END_NS_DECIMATER
361 } // END_NS_OPENMESH
362 //=============================================================================
363 
An efficient, highly customizable heap.
Definition: HeapT.hh:138
size_t decimate_to_faces(size_t _n_vertices=0, size_t _n_faces=0)
Attempts to decimate the mesh until a desired vertex or face complexity is achieved.
Definition: DecimaterT_impl.hh:254
Mesh::HalfedgeHandle v0v1
Halfedge to be collapsed.
Definition: CollapseInfoT.hh:89
Kernel::VertexFaceIter VertexFaceIter
Circulator.
Definition: PolyMeshT.hh:166
Kernel::VertexOHalfedgeIter VertexOHalfedgeIter
Circulator.
Definition: PolyMeshT.hh:163
Definition: BaseDecimaterT.hh:85
Mesh::HalfedgeHandle v1v0
Reverse halfedge.
Definition: CollapseInfoT.hh:90
size_t decimate(size_t _n_collapses=0)
Perform a number of collapses on the mesh.
Definition: DecimaterT_impl.hh:150
float collapse_priority(const CollapseInfo &_ci)
Calculate priority of an halfedge collapse (using the modules)
Definition: BaseDecimaterT_impl.hh:154
DecimaterT(Mesh &_mesh)
Constructor.
Definition: DecimaterT_impl.hh:72
Contains all the mesh ingredients like the polygonal mesh, the triangle mesh, different mesh kernels ...
Definition: MeshItems.hh:59
Kernel::VertexVertexIter VertexVertexIter
Circulator.
Definition: PolyMeshT.hh:162
Decimater framework.
Definition: DecimaterT.hh:78
Mesh::VertexHandle v1
Remaining vertex.
Definition: CollapseInfoT.hh:92
bool is_collapse_legal(const CollapseInfo &_ci)
Is an edge collapse legal? Performs topological test only.
Definition: BaseDecimaterT_impl.hh:100
void preprocess_collapse(CollapseInfo &_ci)
Pre-process a collapse.
Definition: BaseDecimaterT_impl.hh:179
Stores information about a halfedge collapse.
Definition: CollapseInfoT.hh:74
bool notify_observer(size_t _n_collapses)
returns false, if abort requested by observer
Definition: BaseDecimaterT.hh:191
void postprocess_collapse(CollapseInfo &_ci)
Post-process a collapse.
Definition: BaseDecimaterT_impl.hh:167
Heap interface.
Definition: DecimaterT.hh:145
Mesh::VertexHandle v0
Vertex to be removed.
Definition: CollapseInfoT.hh:91
bool is_initialized() const
Returns whether decimater has been successfully initialized.
Definition: BaseDecimaterT.hh:111
~DecimaterT()
Destructor.
Definition: DecimaterT_impl.hh:92

Project OpenMesh, ©  Computer Graphics Group, RWTH Aachen. Documentation generated using doxygen .