DecimaterT_impl.hh 11.6 KB
Newer Older
Jan Möbius's avatar
Jan Möbius committed
1
/* ========================================================================= *
2 3
 *                                                                           *
 *                               OpenMesh                                    *
Jan Möbius's avatar
Jan Möbius committed
4
 *           Copyright (c) 2001-2015, RWTH-Aachen University                 *
Jan Möbius's avatar
Typo  
Jan Möbius committed
5
 *           Department of Computer Graphics and Multimedia                  *
Jan Möbius's avatar
Jan Möbius committed
6 7
 *                          All rights reserved.                             *
 *                            www.openmesh.org                               *
8
 *                                                                           *
9
 *---------------------------------------------------------------------------*
Jan Möbius's avatar
Jan Möbius committed
10 11
 * This file is part of OpenMesh.                                            *
 *---------------------------------------------------------------------------*
12
 *                                                                           *
Jan Möbius's avatar
Jan Möbius committed
13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
 * Redistribution and use in source and binary forms, with or without        *
 * modification, are permitted provided that the following conditions        *
 * are met:                                                                  *
 *                                                                           *
 * 1. Redistributions of source code must retain the above copyright notice, *
 *    this list of conditions and the following disclaimer.                  *
 *                                                                           *
 * 2. Redistributions in binary form must reproduce the above copyright      *
 *    notice, this list of conditions and the following disclaimer in the    *
 *    documentation and/or other materials provided with the distribution.   *
 *                                                                           *
 * 3. Neither the name of the copyright holder nor the names of its          *
 *    contributors may be used to endorse or promote products derived from   *
 *    this software without specific prior written permission.               *
 *                                                                           *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS       *
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED *
 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A           *
 * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER *
 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,  *
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,       *
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR        *
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF    *
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING      *
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS        *
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.              *
Jan Möbius's avatar
Jan Möbius committed
39 40
 *                                                                           *
 * ========================================================================= */
41

Jan Möbius's avatar
Jan Möbius committed
42

43
/** \file DecimaterT_impl.hh
Jan Möbius's avatar
Jan Möbius committed
44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65
 */

//=============================================================================
//
//  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 ===============================================================

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

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

71 72
template<class Mesh>
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 77 78 79 80 81
  heap_(nullptr)
#else
  heap_(NULL)
#endif

{
Jan Möbius's avatar
Jan Möbius committed
82 83

  // private vertex properties
84 85 86
  mesh_.add_property(collapse_target_);
  mesh_.add_property(priority_);
  mesh_.add_property(heap_position_);
Jan Möbius's avatar
Jan Möbius committed
87 88 89 90
}

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

91 92
template<class Mesh>
DecimaterT<Mesh>::~DecimaterT() {
Jan Möbius's avatar
Jan Möbius committed
93 94 95 96 97 98 99 100 101 102

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

}

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

103 104
template<class Mesh>
void DecimaterT<Mesh>::heap_vertex(VertexHandle _vh) {
Jan Möbius's avatar
Jan Möbius committed
105 106
  //   std::clog << "heap_vertex: " << _vh << std::endl;

107 108
  float prio, best_prio(FLT_MAX);
  typename Mesh::HalfedgeHandle heh, collapse_target;
Jan Möbius's avatar
Jan Möbius committed
109 110 111

  // find best target in one ring
  typename Mesh::VertexOHalfedgeIter voh_it(mesh_, _vh);
Jan Möbius's avatar
Jan Möbius committed
112
  for (; voh_it.is_valid(); ++voh_it) {
113
    heh = *voh_it;
114
    CollapseInfo ci(mesh_, heh);
Jan Möbius's avatar
Jan Möbius committed
115

116 117
    if (this->is_collapse_legal(ci)) {
      prio = this->collapse_priority(ci);
118 119 120
      if (prio >= 0.0 && prio < best_prio) {
        best_prio = prio;
        collapse_target = heh;
Jan Möbius's avatar
Jan Möbius committed
121 122 123 124 125
      }
    }
  }

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

131 132 133 134
    if (heap_->is_stored(_vh))
      heap_->update(_vh);
    else
      heap_->insert(_vh);
Jan Möbius's avatar
Jan Möbius committed
135 136 137
  }

  // not valid -> remove from heap
138
  else {
Jan Möbius's avatar
Jan Möbius committed
139
    //     std::clog << "  n/a|removed" << std::endl;
140 141
    if (heap_->is_stored(_vh))
      heap_->remove(_vh);
Jan Möbius's avatar
Jan Möbius committed
142 143

    mesh_.property(collapse_target_, _vh) = collapse_target;
144
    mesh_.property(priority_, _vh) = -1;
Jan Möbius's avatar
Jan Möbius committed
145 146
  }
}
147 148 149 150 151 152 153

//-----------------------------------------------------------------------------
template<class Mesh>
size_t DecimaterT<Mesh>::decimate(size_t _n_collapses) {

  if (!this->is_initialized())
    return 0;
Jan Möbius's avatar
Jan Möbius committed
154

155 156 157 158 159 160
  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
161

162 163
  typedef std::vector<typename Mesh::VertexHandle> Support;
  typedef typename Support::iterator SupportIterator;
Jan Möbius's avatar
Jan Möbius committed
164

165 166
  Support support(15);
  SupportIterator s_it, s_end;
Jan Möbius's avatar
Jan Möbius committed
167 168

  // check _n_collapses
169 170
  if (!_n_collapses)
    _n_collapses = mesh_.n_vertices();
Jan Möbius's avatar
Jan Möbius committed
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 177
  heap_ = std::unique_ptr<DeciHeap>(new DeciHeap(HI));
#else
Jan Möbius's avatar
Jan Möbius committed
178
  heap_ = std::auto_ptr<DeciHeap>(new DeciHeap(HI));
179 180 181
#endif


Jan Möbius's avatar
Jan Möbius committed
182 183
  heap_->reserve(mesh_.n_vertices());

184
  for (v_it = mesh_.vertices_begin(); v_it != v_end; ++v_it) {
Jan Möbius's avatar
Jan Möbius committed
185
    heap_->reset_heap_position(*v_it);
Jan Möbius's avatar
Jan Möbius committed
186 187
    if (!mesh_.status(*v_it).deleted())
      heap_vertex(*v_it);
Jan Möbius's avatar
Jan Möbius committed
188 189
  }

190 191
  const bool update_normals = mesh_.has_face_normals();

Jan Möbius's avatar
Jan Möbius committed
192
  // process heap
193
  while ((!heap_->empty()) && (n_collapses < _n_collapses)) {
Jan Möbius's avatar
Jan Möbius committed
194
    // get 1st heap entry
195
    vp = heap_->front();
Jan Möbius's avatar
Jan Möbius committed
196 197 198 199 200 201 202
    v0v1 = mesh_.property(collapse_target_, vp);
    heap_->pop_front();

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

    // check topological correctness AGAIN !
203
    if (!this->is_collapse_legal(ci))
Jan Möbius's avatar
Jan Möbius committed
204 205 206 207 208
      continue;

    // store support (= one ring of *vp)
    vv_it = mesh_.vv_iter(ci.v0);
    support.clear();
Jan Möbius's avatar
Jan Möbius committed
209
    for (; vv_it.is_valid(); ++vv_it)
210
      support.push_back(*vv_it);
Jan Möbius's avatar
Jan Möbius committed
211

212 213 214
    // pre-processing
    this->preprocess_collapse(ci);

Jan Möbius's avatar
Jan Möbius committed
215 216 217 218
    // perform collapse
    mesh_.collapse(v0v1);
    ++n_collapses;

219 220 221 222 223 224 225 226
    if (update_normals)
    {
      // update triangle normals
      vf_it = mesh_.vf_iter(ci.v1);
      for (; vf_it.is_valid(); ++vf_it)
        if (!mesh_.status(*vf_it).deleted())
          mesh_.set_normal(*vf_it, mesh_.calc_face_normal(*vf_it));
    }
Jan Möbius's avatar
Jan Möbius committed
227 228

    // post-process collapse
229
    this->postprocess_collapse(ci);
Jan Möbius's avatar
Jan Möbius committed
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 234 235 236 237 238 239 240 241 242
      assert(!mesh_.status(*s_it).deleted());
      heap_vertex(*s_it);
    }

    // notify observer and stop if the observer requests it
    if (!this->notify_observer(n_collapses))
        return n_collapses;
  }

  // delete heap
Jan Möbius's avatar
Jan Möbius committed
243 244
  heap_.reset();

245

Jan Möbius's avatar
Jan Möbius committed
246

Jan Möbius's avatar
Jan Möbius committed
247 248 249 250
  // DON'T do garbage collection here! It's up to the application.
  return n_collapses;
}

251 252 253 254 255 256 257
//-----------------------------------------------------------------------------

template<class Mesh>
size_t DecimaterT<Mesh>::decimate_to_faces(size_t _nv, size_t _nf) {

  if (!this->is_initialized())
    return 0;
258 259 260 261

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

262 263 264 265 266
  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;
267 268
  size_t nv = mesh_.n_vertices();
  size_t nf = mesh_.n_faces();
269
  unsigned int n_collapses = 0;
270

271 272
  typedef std::vector<typename Mesh::VertexHandle> Support;
  typedef typename Support::iterator SupportIterator;
273

274 275
  Support support(15);
  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 281 282 283
    heap_ = std::unique_ptr<DeciHeap>(new DeciHeap(HI));
  #else
    heap_ = std::auto_ptr<DeciHeap>(new DeciHeap(HI));
  #endif
284 285
  heap_->reserve(mesh_.n_vertices());

286
  for (v_it = mesh_.vertices_begin(); v_it != v_end; ++v_it) {
Jan Möbius's avatar
Jan Möbius committed
287
    heap_->reset_heap_position(*v_it);
288
    if (!mesh_.status(*v_it).deleted())
Jan Möbius's avatar
Jan Möbius committed
289
      heap_vertex(*v_it);
290 291
  }

292 293
  const bool update_normals = mesh_.has_face_normals();

294
  // process heap
295
  while ((!heap_->empty()) && (_nv < nv) && (_nf < nf)) {
296
    // get 1st heap entry
297
    vp = heap_->front();
298 299 300 301 302 303 304
    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
305
    if (!this->is_collapse_legal(ci))
306 307 308 309 310
      continue;

    // store support (= one ring of *vp)
    vv_it = mesh_.vv_iter(ci.v0);
    support.clear();
311
    for (; vv_it.is_valid(); ++vv_it)
312
      support.push_back(*vv_it);
313 314 315 316

    // adjust complexity in advance (need boundary status)
    ++n_collapses;
    --nv;
317
    if (mesh_.is_boundary(ci.v0v1) || mesh_.is_boundary(ci.v1v0))
318
      --nf;
319 320
    else
      nf -= 2;
321 322

    // pre-processing
Jan Möbius's avatar
Jan Möbius committed
323
    this->preprocess_collapse(ci);
324 325 326 327 328

    // perform collapse
    mesh_.collapse(v0v1);

    // update triangle normals
329 330 331 332 333 334 335
    if (update_normals)
    {
      vf_it = mesh_.vf_iter(ci.v1);
      for (; vf_it.is_valid(); ++vf_it)
        if (!mesh_.status(*vf_it).deleted())
          mesh_.set_normal(*vf_it, mesh_.calc_face_normal(*vf_it));
    }
336 337

    // post-process collapse
Jan Möbius's avatar
Jan Möbius committed
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 343 344 345 346 347 348 349 350 351
      assert(!mesh_.status(*s_it).deleted());
      heap_vertex(*s_it);
    }

    // notify observer and stop if the observer requests it
    if (!this->notify_observer(n_collapses))
        return n_collapses;
  }

  // delete heap
352 353
  heap_.reset();

354

355 356 357 358
  // DON'T do garbage collection here! It's up to the application.
  return n_collapses;
}

Jan Möbius's avatar
Jan Möbius committed
359
//=============================================================================
360
}// END_NS_DECIMATER
Jan Möbius's avatar
Jan Möbius committed
361 362 363
} // END_NS_OPENMESH
//=============================================================================