DecimaterT.cc 10.4 KB
Newer Older
1
2
3
/*===========================================================================*\
 *                                                                           *
 *                               OpenMesh                                    *
Jan Möbius's avatar
Jan Möbius committed
4
 *      Copyright (C) 2001-2011 by Computer Graphics Group, RWTH Aachen      *
5
6
 *                           www.openmesh.org                                *
 *                                                                           *
7
 *---------------------------------------------------------------------------*
8
9
 *  This file is part of OpenMesh.                                           *
 *                                                                           *
10
 *  OpenMesh is free software: you can redistribute it and/or modify         *
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 *  it under the terms of the GNU Lesser General Public License as           *
 *  published by the Free Software Foundation, either version 3 of           *
 *  the License, or (at your option) any later version with the              *
 *  following exceptions:                                                    *
 *                                                                           *
 *  If other files instantiate templates or use macros                       *
 *  or inline functions from this file, or you compile this file and         *
 *  link it with other files to produce an executable, this file does        *
 *  not by itself cause the resulting executable to be covered by the        *
 *  GNU Lesser General Public License. This exception does not however       *
 *  invalidate any other reasons why the executable file might be            *
 *  covered by the GNU Lesser General Public License.                        *
 *                                                                           *
 *  OpenMesh is distributed in the hope that it will be useful,              *
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of           *
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the            *
 *  GNU Lesser General Public License for more details.                      *
 *                                                                           *
 *  You should have received a copy of the GNU LesserGeneral Public          *
 *  License along with OpenMesh.  If not,                                    *
 *  see <http://www.gnu.org/licenses/>.                                      *
 *                                                                           *
33
 \*===========================================================================*/
34
35

/*===========================================================================*\
36
 *                                                                           *
37
38
39
 *   $Revision$                                                         *
 *   $Date$                   *
 *                                                                           *
40
 \*===========================================================================*/
Jan Möbius's avatar
Jan Möbius committed
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

/** \file DecimaterT.cc
 */

//=============================================================================
//
//  CLASS DecimaterT - IMPLEMENTATION
//
//=============================================================================
#define OPENMESH_DECIMATER_DECIMATERT_CC

//== INCLUDES =================================================================

#include <OpenMesh/Tools/Decimater/DecimaterT.hh>

#include <vector>
#if defined(OM_CC_MIPS)
#  include <float.h>
#else
#  include <cfloat>
#endif

//== NAMESPACE ===============================================================

65
namespace OpenMesh {
Jan Möbius's avatar
Jan Möbius committed
66
67
68
69
namespace Decimater {

//== IMPLEMENTATION ==========================================================

70
71
template<class Mesh>
DecimaterT<Mesh>::DecimaterT(Mesh& _mesh) :
72
73
  BaseDecimaterT<Mesh>(_mesh),
    mesh_(_mesh), heap_(NULL) {
Jan Möbius's avatar
Jan Möbius committed
74
75

  // private vertex properties
76
77
78
  mesh_.add_property(collapse_target_);
  mesh_.add_property(priority_);
  mesh_.add_property(heap_position_);
Jan Möbius's avatar
Jan Möbius committed
79
80
81
82
}

//-----------------------------------------------------------------------------

83
84
template<class Mesh>
DecimaterT<Mesh>::~DecimaterT() {
Jan Möbius's avatar
Jan Möbius committed
85
86
87
88
89
90
91
92
93
94

  // private vertex properties
  mesh_.remove_property(collapse_target_);
  mesh_.remove_property(priority_);
  mesh_.remove_property(heap_position_);

}

//-----------------------------------------------------------------------------

95
96
template<class Mesh>
void DecimaterT<Mesh>::heap_vertex(VertexHandle _vh) {
Jan Möbius's avatar
Jan Möbius committed
97
98
  //   std::clog << "heap_vertex: " << _vh << std::endl;

99
100
  float prio, best_prio(FLT_MAX);
  typename Mesh::HalfedgeHandle heh, collapse_target;
Jan Möbius's avatar
Jan Möbius committed
101
102
103

  // find best target in one ring
  typename Mesh::VertexOHalfedgeIter voh_it(mesh_, _vh);
104
  for (; voh_it; ++voh_it) {
Jan Möbius's avatar
Jan Möbius committed
105
    heh = voh_it.handle();
106
    CollapseInfo ci(mesh_, heh);
Jan Möbius's avatar
Jan Möbius committed
107

108
109
    if (this->is_collapse_legal(ci)) {
      prio = this->collapse_priority(ci);
110
111
112
      if (prio >= 0.0 && prio < best_prio) {
        best_prio = prio;
        collapse_target = heh;
Jan Möbius's avatar
Jan Möbius committed
113
114
115
116
117
      }
    }
  }

  // target found -> put vertex on heap
118
  if (collapse_target.is_valid()) {
Jan Möbius's avatar
Jan Möbius committed
119
120
    //     std::clog << "  added|updated" << std::endl;
    mesh_.property(collapse_target_, _vh) = collapse_target;
121
    mesh_.property(priority_, _vh) = best_prio;
Jan Möbius's avatar
Jan Möbius committed
122

123
124
125
126
    if (heap_->is_stored(_vh))
      heap_->update(_vh);
    else
      heap_->insert(_vh);
Jan Möbius's avatar
Jan Möbius committed
127
128
129
  }

  // not valid -> remove from heap
130
  else {
Jan Möbius's avatar
Jan Möbius committed
131
    //     std::clog << "  n/a|removed" << std::endl;
132
133
    if (heap_->is_stored(_vh))
      heap_->remove(_vh);
Jan Möbius's avatar
Jan Möbius committed
134
135

    mesh_.property(collapse_target_, _vh) = collapse_target;
136
    mesh_.property(priority_, _vh) = -1;
Jan Möbius's avatar
Jan Möbius committed
137
138
139
  }
}

140
//-----------------------------------------------------------------------------
141
142
template<class Mesh>
size_t DecimaterT<Mesh>::decimate(size_t _n_collapses) {
143
  if (!this->is_initialized())
Jan Möbius's avatar
Jan Möbius committed
144
145
    return 0;

146
147
148
149
150
151
  typename Mesh::VertexIter v_it, v_end(mesh_.vertices_end());
  typename Mesh::VertexHandle vp;
  typename Mesh::HalfedgeHandle v0v1;
  typename Mesh::VertexVertexIter vv_it;
  typename Mesh::VertexFaceIter vf_it;
  unsigned int n_collapses(0);
Jan Möbius's avatar
Jan Möbius committed
152

153
154
  typedef std::vector<typename Mesh::VertexHandle> Support;
  typedef typename Support::iterator SupportIterator;
Jan Möbius's avatar
Jan Möbius committed
155

156
157
  Support support(15);
  SupportIterator s_it, s_end;
Jan Möbius's avatar
Jan Möbius committed
158
159

  // check _n_collapses
160
161
  if (!_n_collapses)
    _n_collapses = mesh_.n_vertices();
Jan Möbius's avatar
Jan Möbius committed
162
163

  // initialize heap
164
  HeapInterface HI(mesh_, priority_, heap_position_);
Jan Möbius's avatar
Jan Möbius committed
165
166
167
  heap_ = std::auto_ptr<DeciHeap>(new DeciHeap(HI));
  heap_->reserve(mesh_.n_vertices());

168
169
  for (v_it = mesh_.vertices_begin(); v_it != v_end; ++v_it) {
    heap_->reset_heap_position(v_it.handle());
Jan Möbius's avatar
Jan Möbius committed
170
    if (!mesh_.status(v_it).deleted())
171
      heap_vertex(v_it.handle());
Jan Möbius's avatar
Jan Möbius committed
172
173
174
  }

  // process heap
175
  while ((!heap_->empty()) && (n_collapses < _n_collapses)) {
Jan Möbius's avatar
Jan Möbius committed
176
    // get 1st heap entry
177
    vp = heap_->front();
Jan Möbius's avatar
Jan Möbius committed
178
179
180
181
182
183
184
    v0v1 = mesh_.property(collapse_target_, vp);
    heap_->pop_front();

    // setup collapse info
    CollapseInfo ci(mesh_, v0v1);

    // check topological correctness AGAIN !
185
    if (!this->is_collapse_legal(ci))
Jan Möbius's avatar
Jan Möbius committed
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
      continue;

    // store support (= one ring of *vp)
    vv_it = mesh_.vv_iter(ci.v0);
    support.clear();
    for (; vv_it; ++vv_it)
      support.push_back(vv_it.handle());

    // perform collapse
    mesh_.collapse(v0v1);
    ++n_collapses;

    // update triangle normals
    vf_it = mesh_.vf_iter(ci.v1);
    for (; vf_it; ++vf_it)
      if (!mesh_.status(vf_it).deleted())
202
        mesh_.set_normal(vf_it, mesh_.calc_face_normal(vf_it.handle()));
Jan Möbius's avatar
Jan Möbius committed
203
204

    // post-process collapse
205
    this->postprocess_collapse(ci);
Jan Möbius's avatar
Jan Möbius committed
206
207

    // update heap (former one ring of decimated vertex)
208
    for (s_it = support.begin(), s_end = support.end(); s_it != s_end; ++s_it) {
Jan Möbius's avatar
Jan Möbius committed
209
210
211
212
213
214
215
216
      assert(!mesh_.status(*s_it).deleted());
      heap_vertex(*s_it);
    }
  }

  // delete heap
  heap_.reset();

217

Jan Möbius's avatar
Jan Möbius committed
218
219
220
221
  // DON'T do garbage collection here! It's up to the application.
  return n_collapses;
}

222
223
//-----------------------------------------------------------------------------

224
225
template<class Mesh>
size_t DecimaterT<Mesh>::decimate_to_faces(size_t _nv, size_t _nf) {
226
  if (!this->is_initialized())
227
228
229
230
231
    return 0;

  if (_nv >= mesh_.n_vertices() || _nf >= mesh_.n_faces())
    return 0;

232
233
234
235
236
237
238
239
  typename Mesh::VertexIter v_it, v_end(mesh_.vertices_end());
  typename Mesh::VertexHandle vp;
  typename Mesh::HalfedgeHandle v0v1;
  typename Mesh::VertexVertexIter vv_it;
  typename Mesh::VertexFaceIter vf_it;
  unsigned int nv = mesh_.n_vertices();
  unsigned int nf = mesh_.n_faces();
  unsigned int n_collapses = 0;
240

241
242
  typedef std::vector<typename Mesh::VertexHandle> Support;
  typedef typename Support::iterator SupportIterator;
243

244
245
  Support support(15);
  SupportIterator s_it, s_end;
246
247

  // initialize heap
248
  HeapInterface HI(mesh_, priority_, heap_position_);
249
250
251
  heap_ = std::auto_ptr<DeciHeap>(new DeciHeap(HI));
  heap_->reserve(mesh_.n_vertices());

252
253
  for (v_it = mesh_.vertices_begin(); v_it != v_end; ++v_it) {
    heap_->reset_heap_position(v_it.handle());
254
    if (!mesh_.status(v_it).deleted())
255
      heap_vertex(v_it.handle());
256
257
258
  }

  // process heap
259
  while ((!heap_->empty()) && (_nv < nv) && (_nf < nf)) {
260
    // get 1st heap entry
261
    vp = heap_->front();
262
263
264
265
266
267
268
    v0v1 = mesh_.property(collapse_target_, vp);
    heap_->pop_front();

    // setup collapse info
    CollapseInfo ci(mesh_, v0v1);

    // check topological correctness AGAIN !
Jan Möbius's avatar
Jan Möbius committed
269
    if (!this->is_collapse_legal(ci))
270
271
272
273
274
275
276
277
278
279
280
      continue;

    // store support (= one ring of *vp)
    vv_it = mesh_.vv_iter(ci.v0);
    support.clear();
    for (; vv_it; ++vv_it)
      support.push_back(vv_it.handle());

    // adjust complexity in advance (need boundary status)
    ++n_collapses;
    --nv;
281
    if (mesh_.is_boundary(ci.v0v1) || mesh_.is_boundary(ci.v1v0))
282
      --nf;
283
284
    else
      nf -= 2;
285
286

    // pre-processing
Jan Möbius's avatar
Jan Möbius committed
287
    this->preprocess_collapse(ci);
288
289
290
291
292
293
294
295

    // perform collapse
    mesh_.collapse(v0v1);

    // update triangle normals
    vf_it = mesh_.vf_iter(ci.v1);
    for (; vf_it; ++vf_it)
      if (!mesh_.status(vf_it).deleted())
296
        mesh_.set_normal(vf_it, mesh_.calc_face_normal(vf_it.handle()));
297
298

    // post-process collapse
Jan Möbius's avatar
Jan Möbius committed
299
    this->postprocess_collapse(ci);
300
301

    // update heap (former one ring of decimated vertex)
302
    for (s_it = support.begin(), s_end = support.end(); s_it != s_end; ++s_it) {
303
304
305
306
307
308
309
310
      assert(!mesh_.status(*s_it).deleted());
      heap_vertex(*s_it);
    }
  }

  // delete heap
  heap_.reset();

311

312
313
314
315
  // DON'T do garbage collection here! It's up to the application.
  return n_collapses;
}

Jan Möbius's avatar
Jan Möbius committed
316
//=============================================================================
317
}// END_NS_DECIMATER
Jan Möbius's avatar
Jan Möbius committed
318
319
320
} // END_NS_OPENMESH
//=============================================================================