Developer Documentation

- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files

- File List
- File Members

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Modules Pages
DecimaterT.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 DecimaterT - IMPLEMENTATION
55 //
56 //=============================================================================
57 #define OPENMESH_DECIMATER_DECIMATERT_CC
58
59 //== INCLUDES =================================================================
60
61 #include <OpenMesh/Tools/Decimater/DecimaterT.hh>
62
63 #include <vector>
64 #if defined(OM_CC_MIPS)
65 # include <float.h>
66 #else
67 # include <cfloat>
68 #endif
69
70 //== NAMESPACE ===============================================================
71
72 namespace OpenMesh {
73 namespace Decimater {
74
75 //== IMPLEMENTATION ==========================================================
76
77 template<class Mesh>
78 DecimaterT<Mesh>::DecimaterT(Mesh& _mesh) :
79 BaseDecimaterT<Mesh>(_mesh),
80 mesh_(_mesh),
81 #if _MSC_VER >= 1900 || __cplusplus > 199711L || defined( __GXX_EXPERIMENTAL_CXX0X__ )
82 heap_(nullptr)
83 #else
84 heap_(NULL)
85 #endif
86
87 {
88
89 // private vertex properties
90 mesh_.add_property(collapse_target_);
91 mesh_.add_property(priority_);
92 mesh_.add_property(heap_position_);
93 }
94
95 //-----------------------------------------------------------------------------
96
97 template<class Mesh>
98 DecimaterT<Mesh>::~DecimaterT() {
99
100 // private vertex properties
101 mesh_.remove_property(collapse_target_);
102 mesh_.remove_property(priority_);
103 mesh_.remove_property(heap_position_);
104
105 }
106
107 //-----------------------------------------------------------------------------
108
109 template<class Mesh>
110 void DecimaterT<Mesh>::heap_vertex(VertexHandle _vh) {
111 // std::clog << "heap_vertex: " << _vh << std::endl;
112
113 float prio, best_prio(FLT_MAX);
114 typename Mesh::HalfedgeHandle heh, collapse_target;
115
116 // find best target in one ring
117 typename Mesh::VertexOHalfedgeIter voh_it(mesh_, _vh);
118 for (; voh_it.is_valid(); ++voh_it) {
119 heh = *voh_it;
120 CollapseInfo ci(mesh_, heh);
121
122 if (this->is_collapse_legal(ci)) {
123 prio = this->collapse_priority(ci);
124 if (prio >= 0.0 && prio < best_prio) {
125 best_prio = prio;
126 collapse_target = heh;
127 }
128 }
129 }
130
131 // target found -> put vertex on heap
132 if (collapse_target.is_valid()) {
133 // std::clog << " added|updated" << std::endl;
134 mesh_.property(collapse_target_, _vh) = collapse_target;
135 mesh_.property(priority_, _vh) = best_prio;
136
137 if (heap_->is_stored(_vh))
138 heap_->update(_vh);
139 else
140 heap_->insert(_vh);
141 }
142
143 // not valid -> remove from heap
144 else {
145 // std::clog << " n/a|removed" << std::endl;
146 if (heap_->is_stored(_vh))
147 heap_->remove(_vh);
148
149 mesh_.property(collapse_target_, _vh) = collapse_target;
150 mesh_.property(priority_, _vh) = -1;
151 }
152 }
153
154 //-----------------------------------------------------------------------------
155 template<class Mesh>
156 size_t DecimaterT<Mesh>::decimate(size_t _n_collapses) {
157
158 if (!this->is_initialized())
159 return 0;
160
161 typename Mesh::VertexIter v_it, v_end(mesh_.vertices_end());
162 typename Mesh::VertexHandle vp;
163 typename Mesh::HalfedgeHandle v0v1;
164 typename Mesh::VertexVertexIter vv_it;
165 typename Mesh::VertexFaceIter vf_it;
166 unsigned int n_collapses(0);
167
168 typedef std::vector<typename Mesh::VertexHandle> Support;
169 typedef typename Support::iterator SupportIterator;
170
171 Support support(15);
172 SupportIterator s_it, s_end;
173
174 // check _n_collapses
175 if (!_n_collapses)
176 _n_collapses = mesh_.n_vertices();
177
178 // initialize heap
179 HeapInterface HI(mesh_, priority_, heap_position_);
180
181 #if _MSC_VER >= 1900 || __cplusplus > 199711L || defined( __GXX_EXPERIMENTAL_CXX0X__ )
182 heap_ = std::unique_ptr<DeciHeap>(new DeciHeap(HI));
183 #else
184 heap_ = std::auto_ptr<DeciHeap>(new DeciHeap(HI));
185 #endif
186
187
188 heap_->reserve(mesh_.n_vertices());
189
190 for (v_it = mesh_.vertices_begin(); v_it != v_end; ++v_it) {
191 heap_->reset_heap_position(*v_it);
192 if (!mesh_.status(*v_it).deleted())
193 heap_vertex(*v_it);
194 }
195
196 const bool update_normals = mesh_.has_face_normals();
197
198 // process heap
199 while ((!heap_->empty()) && (n_collapses < _n_collapses)) {
200 // get 1st heap entry
201 vp = heap_->front();
202 v0v1 = mesh_.property(collapse_target_, vp);
203 heap_->pop_front();
204
205 // setup collapse info
206 CollapseInfo ci(mesh_, v0v1);
207
208 // check topological correctness AGAIN !
209 if (!this->is_collapse_legal(ci))
210 continue;
211
212 // store support (= one ring of *vp)
213 vv_it = mesh_.vv_iter(ci.v0);
214 support.clear();
215 for (; vv_it.is_valid(); ++vv_it)
216 support.push_back(*vv_it);
217
218 // pre-processing
219 this->preprocess_collapse(ci);
220
221 // perform collapse
222 mesh_.collapse(v0v1);
223 ++n_collapses;
224
225 if (update_normals)
226 {
227 // update triangle normals
228 vf_it = mesh_.vf_iter(ci.v1);
229 for (; vf_it.is_valid(); ++vf_it)
230 if (!mesh_.status(*vf_it).deleted())
231 mesh_.set_normal(*vf_it, mesh_.calc_face_normal(*vf_it));
232 }
233
234 // post-process collapse
235 this->postprocess_collapse(ci);
236
237 // update heap (former one ring of decimated vertex)
238 for (s_it = support.begin(), s_end = support.end(); s_it != s_end; ++s_it) {
239 assert(!mesh_.status(*s_it).deleted());
240 heap_vertex(*s_it);
241 }
242
243 // notify observer and stop if the observer requests it
244 if (!this->notify_observer(n_collapses))
245 return n_collapses;
246 }
247
248 // delete heap
249 heap_.reset();
250
251
252
253 // DON'T do garbage collection here! It's up to the application.
254 return n_collapses;
255 }
256
257 //-----------------------------------------------------------------------------
258
259 template<class Mesh>
260 size_t DecimaterT<Mesh>::decimate_to_faces(size_t _nv, size_t _nf) {
261
262 if (!this->is_initialized())
263 return 0;
264
265 if (_nv >= mesh_.n_vertices() || _nf >= mesh_.n_faces())
266 return 0;
267
268 typename Mesh::VertexIter v_it, v_end(mesh_.vertices_end());
269 typename Mesh::VertexHandle vp;
270 typename Mesh::HalfedgeHandle v0v1;
271 typename Mesh::VertexVertexIter vv_it;
272 typename Mesh::VertexFaceIter vf_it;
273 size_t nv = mesh_.n_vertices();
274 size_t nf = mesh_.n_faces();
275 unsigned int n_collapses = 0;
276
277 typedef std::vector<typename Mesh::VertexHandle> Support;
278 typedef typename Support::iterator SupportIterator;
279
280 Support support(15);
281 SupportIterator s_it, s_end;
282
283 // initialize heap
284 HeapInterface HI(mesh_, priority_, heap_position_);
285 #if _MSC_VER >= 1900 || __cplusplus > 199711L || defined( __GXX_EXPERIMENTAL_CXX0X__ )
286 heap_ = std::unique_ptr<DeciHeap>(new DeciHeap(HI));
287 #else
288 heap_ = std::auto_ptr<DeciHeap>(new DeciHeap(HI));
289 #endif
290 heap_->reserve(mesh_.n_vertices());
291
292 for (v_it = mesh_.vertices_begin(); v_it != v_end; ++v_it) {
293 heap_->reset_heap_position(*v_it);
294 if (!mesh_.status(*v_it).deleted())
295 heap_vertex(*v_it);
296 }
297
298 const bool update_normals = mesh_.has_face_normals();
299
300 // process heap
301 while ((!heap_->empty()) && (_nv < nv) && (_nf < nf)) {
302 // get 1st heap entry
303 vp = heap_->front();
304 v0v1 = mesh_.property(collapse_target_, vp);
305 heap_->pop_front();
306
307 // setup collapse info
308 CollapseInfo ci(mesh_, v0v1);
309
310 // check topological correctness AGAIN !
311 if (!this->is_collapse_legal(ci))
312 continue;
313
314 // store support (= one ring of *vp)
315 vv_it = mesh_.vv_iter(ci.v0);
316 support.clear();
317 for (; vv_it.is_valid(); ++vv_it)
318 support.push_back(*vv_it);
319
320 // adjust complexity in advance (need boundary status)
321 ++n_collapses;
322 --nv;
323 if (mesh_.is_boundary(ci.v0v1) || mesh_.is_boundary(ci.v1v0))
324 --nf;
325 else
326 nf -= 2;
327
328 // pre-processing
329 this->preprocess_collapse(ci);
330
331 // perform collapse
332 mesh_.collapse(v0v1);
333
334 // update triangle normals
335 if (update_normals)
336 {
337 vf_it = mesh_.vf_iter(ci.v1);
338 for (; vf_it.is_valid(); ++vf_it)
339 if (!mesh_.status(*vf_it).deleted())
340 mesh_.set_normal(*vf_it, mesh_.calc_face_normal(*vf_it));
341 }
342
343 // post-process collapse
344 this->postprocess_collapse(ci);
345
346 // update heap (former one ring of decimated vertex)
347 for (s_it = support.begin(), s_end = support.end(); s_it != s_end; ++s_it) {
348 assert(!mesh_.status(*s_it).deleted());
349 heap_vertex(*s_it);
350 }
351
352 // notify observer and stop if the observer requests it
353 if (!this->notify_observer(n_collapses))
354 return n_collapses;
355 }
356
357 // delete heap
358 heap_.reset();
359
360
361 // DON'T do garbage collection here! It's up to the application.
362 return n_collapses;
363 }
364
365 //=============================================================================
366 }// END_NS_DECIMATER
367 } // END_NS_OPENMESH
368 //=============================================================================
369
OpenMesh::Decimater::CollapseInfoT::v1
Mesh::VertexHandle v1
Remaining vertex.
Definition: CollapseInfoT.hh:98
DecimaterT.hh
OpenMesh::Decimater::CollapseInfoT::v0
Mesh::VertexHandle v0
Vertex to be removed.
Definition: CollapseInfoT.hh:97
OpenMesh
Definition: MeshItems.hh:64
OpenMesh::Decimater::DecimaterT::decimate_to_faces
size_t decimate_to_faces(size_t _n_vertices=0, size_t _n_faces=0)
Definition: DecimaterT.cc:260
OpenMesh::PolyMeshT::VertexVertexIter
Kernel::VertexVertexIter VertexVertexIter
Circulator.
Definition: PolyMeshT.hh:165
OpenMesh::Decimater::DecimaterT::DecimaterT
DecimaterT(Mesh &_mesh)
Constructor.
Definition: DecimaterT.cc:78
OpenMesh::Decimater::DecimaterT::decimate
size_t decimate(size_t _n_collapses=0)
Definition: DecimaterT.cc:156
OpenMesh::Decimater::DecimaterT::~DecimaterT
~DecimaterT()
Destructor.
Definition: DecimaterT.cc:98
OpenMesh::Decimater::CollapseInfoT::v1v0
Mesh::HalfedgeHandle v1v0
Reverse halfedge.
Definition: CollapseInfoT.hh:96
OpenMesh::Decimater::CollapseInfoT
Definition: CollapseInfoT.hh:80
OpenMesh::PolyMeshT::VertexOHalfedgeIter
Kernel::VertexOHalfedgeIter VertexOHalfedgeIter
Circulator.
Definition: PolyMeshT.hh:166
OpenMesh::Decimater::BaseDecimaterT
Definition: BaseDecimaterT.hh:90
OpenMesh::Decimater::DecimaterT::heap_vertex
void heap_vertex(VertexHandle _vh)
Insert vertex in heap.
Definition: DecimaterT.cc:110
OpenMesh::PolyMeshT::VertexHandle
Kernel::VertexHandle VertexHandle
Handle for referencing the corresponding item.
Definition: PolyMeshT.hh:139
OpenMesh::TriMeshT::calc_face_normal
Normal calc_face_normal(FaceHandle _fh) const
Definition: TriMeshT.cc:79
OpenMesh::Decimater::DecimaterT::HeapInterface
Heap interface.
Definition: DecimaterT.hh:128
OpenMesh::Utils::HeapT
Definition: HeapT.hh:143
OpenMesh::PolyMeshT::VertexFaceIter
Kernel::VertexFaceIter VertexFaceIter
Circulator.
Definition: PolyMeshT.hh:169
OpenMesh::Decimater::CollapseInfoT::v0v1
Mesh::HalfedgeHandle v0v1
Halfedge to be collapsed.
Definition: CollapseInfoT.hh:95