| 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
55 #include <OpenMesh/Tools/Decimater/DecimaterT.hh>
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>
72 DecimaterT<Mesh>::DecimaterT(Mesh& _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>
92 DecimaterT<Mesh>::~DecimaterT() {
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
OpenMesh::Utils::HeapT
An efficient, highly customizable heap.
Definition: HeapT.hh:138
OpenMesh::Decimater::DecimaterT::decimate_to_faces
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
OpenMesh::Decimater::CollapseInfoT::v0v1
Mesh::HalfedgeHandle v0v1
Halfedge to be collapsed.
Definition: CollapseInfoT.hh:89
DecimaterT.hh
OpenMesh::PolyMeshT::VertexFaceIter
Kernel::VertexFaceIter VertexFaceIter
Circulator.
Definition: PolyMeshT.hh:166
OpenMesh::PolyMeshT::VertexOHalfedgeIter
Kernel::VertexOHalfedgeIter VertexOHalfedgeIter
Circulator.
Definition: PolyMeshT.hh:163
OpenMesh::Decimater::BaseDecimaterT
Definition: BaseDecimaterT.hh:85
OpenMesh::Decimater::CollapseInfoT::v1v0
Mesh::HalfedgeHandle v1v0
Reverse halfedge.
Definition: CollapseInfoT.hh:90
OpenMesh::Decimater::DecimaterT::decimate
size_t decimate(size_t _n_collapses=0)
Perform a number of collapses on the mesh.
Definition: DecimaterT_impl.hh:150
OpenMesh::Decimater::BaseDecimaterT::collapse_priority
float collapse_priority(const CollapseInfo &_ci)
Calculate priority of an halfedge collapse (using the modules)
Definition: BaseDecimaterT_impl.hh:154
OpenMesh::Decimater::DecimaterT::DecimaterT
DecimaterT(Mesh &_mesh)
Constructor.
Definition: DecimaterT_impl.hh:72
OpenMesh
Contains all the mesh ingredients like the polygonal mesh, the triangle mesh, different mesh kernels ...
Definition: MeshItems.hh:59
OpenMesh::PolyMeshT::VertexVertexIter
Kernel::VertexVertexIter VertexVertexIter
Circulator.
Definition: PolyMeshT.hh:162
OpenMesh::Decimater::DecimaterT
Decimater framework.
Definition: DecimaterT.hh:78
OpenMesh::Decimater::CollapseInfoT::v1
Mesh::VertexHandle v1
Remaining vertex.
Definition: CollapseInfoT.hh:92
OpenMesh::Decimater::BaseDecimaterT::is_collapse_legal
bool is_collapse_legal(const CollapseInfo &_ci)
Is an edge collapse legal? Performs topological test only.
Definition: BaseDecimaterT_impl.hh:100
OpenMesh::Decimater::BaseDecimaterT::preprocess_collapse
void preprocess_collapse(CollapseInfo &_ci)
Pre-process a collapse.
Definition: BaseDecimaterT_impl.hh:179
OpenMesh::Decimater::CollapseInfoT
Stores information about a halfedge collapse.
Definition: CollapseInfoT.hh:74
OpenMesh::Decimater::BaseDecimaterT::notify_observer
bool notify_observer(size_t _n_collapses)
returns false, if abort requested by observer
Definition: BaseDecimaterT.hh:191
OpenMesh::Decimater::BaseDecimaterT::postprocess_collapse
void postprocess_collapse(CollapseInfo &_ci)
Post-process a collapse.
Definition: BaseDecimaterT_impl.hh:167
OpenMesh::Decimater::DecimaterT::HeapInterface
Heap interface.
Definition: DecimaterT.hh:145
OpenMesh::Decimater::CollapseInfoT::v0
Mesh::VertexHandle v0
Vertex to be removed.
Definition: CollapseInfoT.hh:91
OpenMesh::Decimater::BaseDecimaterT::is_initialized
bool is_initialized() const
Returns whether decimater has been successfully initialized.
Definition: BaseDecimaterT.hh:111
OpenMesh::Decimater::DecimaterT::~DecimaterT
~DecimaterT()
Destructor.
Definition: DecimaterT_impl.hh:92