McDecimaterT.cc 15.4 KB
Newer Older
1
2
3
/*===========================================================================*\
 *                                                                           *
 *                               OpenMesh                                    *
Jan Möbius's avatar
Jan Möbius committed
4
 *      Copyright (C) 2001-2012 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
33
34
35
 *  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/>.                                      *
 *                                                                           *
 \*===========================================================================*/

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

/** \file McDecimaterT.cc
 */

//=============================================================================
//
//  CLASS McDecimaterT - IMPLEMENTATION
//
//=============================================================================
#define OPENMESH_MULTIPLE_CHOICE_DECIMATER_DECIMATERT_CC

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

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

#include <vector>
#if defined(OM_CC_MIPS)
#  include <float.h>
#else
#  include <cfloat>
#endif
Jan Möbius's avatar
Jan Möbius committed
62

63
64
65
#ifdef WIN32
# include <OpenMesh/Core/Utils/RandomNumberGenerator.hh>
#endif
66
67
68
69
70
71
72
73
74
75

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

namespace OpenMesh {
namespace Decimater {

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

template<class Mesh>
McDecimaterT<Mesh>::McDecimaterT(Mesh& _mesh) :
76
77
  BaseDecimaterT<Mesh>(_mesh),
    mesh_(_mesh), randomSamples_(10) {
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104

  // default properties
  mesh_.request_vertex_status();
  mesh_.request_halfedge_status();
  mesh_.request_edge_status();
  mesh_.request_face_status();
  mesh_.request_face_normals();

}

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

template<class Mesh>
McDecimaterT<Mesh>::~McDecimaterT() {
  // default properties
  mesh_.release_vertex_status();
  mesh_.release_edge_status();
  mesh_.release_halfedge_status();
  mesh_.release_face_status();
  mesh_.release_face_normals();

}

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

105
  if (!this->is_initialized())
106
107
108
109
    return 0;

  unsigned int n_collapses(0);

110
111
112
113
114
115
116
  bool collapsesUnchanged = false;
  // old n_collapses in order to check for convergence
  unsigned int oldCollapses = 0;
  // number of iterations where no new collapses where
  // performed in a row
  unsigned int noCollapses = 0;

117
118
119
120
#ifdef WIN32
  RandomNumberGenerator randGen(mesh_.n_halfedges());
#endif

121
  while ( n_collapses <  _n_collapses) {
Jan Möbius's avatar
Jan Möbius committed
122

123
124
125
126
    if (noCollapses > 20) {
      omlog() << "[McDecimater] : no collapses performed in over 20 iterations in a row\n";
      break;
    }
127
128
129

    // Optimal id and value will be collected during the random sampling
    typename Mesh::HalfedgeHandle bestHandle(-1);
130
    typename Mesh::HalfedgeHandle tmpHandle(-1);
131
    double bestEnergy = FLT_MAX;
132
    double energy = FLT_MAX;
133
134

    // Generate random samples for collapses
Isaak Lim's avatar
Isaak Lim committed
135
    for ( int i = 0; i < (int)randomSamples_; ++i) {
136
137

      // Random halfedge handle
138
#ifdef WIN32
Isaak Lim's avatar
Isaak Lim committed
139
      tmpHandle = typename Mesh::HalfedgeHandle(int(randGen.getRand() * double(mesh_.n_halfedges() - 1.0)) );
140
#else
141
      tmpHandle = typename Mesh::HalfedgeHandle( (double(rand()) / double(RAND_MAX) ) * double(mesh_.n_halfedges()-1) );
142
#endif
143
144
145
146
147
148
149

      // if it is not deleted, we analyse it
      if ( ! mesh_.status(tmpHandle).deleted()  ) {

        CollapseInfo ci(mesh_, tmpHandle);

        // Check if legal we analyze the priority of this collapse operation
150
        if (this->is_collapse_legal(ci)) {
Jan Möbius's avatar
Jan Möbius committed
151
152
153
154
155
156
157
158
            energy = this->collapse_priority(ci);

            if (energy != ModBaseT<Mesh>::ILLEGAL_COLLAPSE) {
              // Check if the current samples energy is better than any energy before
              if ( energy < bestEnergy ) {
                bestEnergy = energy;
                bestHandle = tmpHandle;
              }
159
            }
160
161
162
163
164
165
166
167
168
169
170
171
172
173
        } else {
          continue;
        }
      }

    }

    // Found the best energy?
    if ( bestEnergy != FLT_MAX ) {

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

      // check topological correctness AGAIN !
174
      if (!this->is_collapse_legal(ci))
175
176
177
        continue;

      // pre-processing
178
      this->preprocess_collapse(ci);
179
180
181
182
183

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

184
185
186
187
188
      // store current collapses state
      oldCollapses = n_collapses;
      noCollapses = 0;
      collapsesUnchanged = false;

189
190
191
192
193
194
195
      // update triangle normals
      typename Mesh::VertexFaceIter vf_it = mesh_.vf_iter(ci.v1);
      for (; vf_it; ++vf_it)
        if (!mesh_.status(vf_it).deleted())
          mesh_.set_normal(vf_it, mesh_.calc_face_normal(vf_it.handle()));

      // post-process collapse
196
      this->postprocess_collapse(ci);
197

198
199
200
201
202
203
204
205
206
    } else {
      if (oldCollapses == n_collapses) {
        if (collapsesUnchanged == false) {
          noCollapses = 1;
          collapsesUnchanged = true;
        } else {
          noCollapses++;
        }
      }
207
208
209
210
211
212
213
214
215
216
217
218
    }

  }

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

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

template<class Mesh>
size_t McDecimaterT<Mesh>::decimate_to_faces(size_t _nv, size_t _nf) {
Jan Möbius's avatar
Jan Möbius committed
219

220
  if (!this->is_initialized())
221
222
    return 0;

223
224
225
226
  // check if no vertex or face contraints were set
  if ( (_nv == 0) && (_nf == 1) )
    return decimate_constraints_only(1.0);

227
228
  size_t nv = mesh_.n_vertices();
  size_t nf = mesh_.n_faces();
229
230
  unsigned int n_collapses(0);

231

232
233
234
235
236
237
  bool collapsesUnchanged = false;
  // old n_collapses in order to check for convergence
  unsigned int oldCollapses = 0;
  // number of iterations where no new collapses where
  // performed in a row
  unsigned int noCollapses = 0;
238

239
240
241
242
#ifdef WIN32
  RandomNumberGenerator randGen(mesh_.n_halfedges());
#endif

Jan Möbius's avatar
Jan Möbius committed
243
  while ((_nv < nv) && (_nf < nf)) {
Jan Möbius's avatar
Jan Möbius committed
244

245
246
247
248
    if (noCollapses > 20) {
      omlog() << "[McDecimater] : no collapses performed in over 20 iterations in a row\n";
      break;
    }
249
250
251

    // Optimal id and value will be collected during the random sampling
    typename Mesh::HalfedgeHandle bestHandle(-1);
252
    typename Mesh::HalfedgeHandle tmpHandle(-1);
253
    double bestEnergy = FLT_MAX;
254
255
    double energy = FLT_MAX;

256
    // Generate random samples for collapses
Jan Möbius's avatar
Jan Möbius committed
257
    for (int i = 0; i < (int) randomSamples_; ++i) {
258
259

      // Random halfedge handle
260
#ifdef WIN32
Isaak Lim's avatar
Isaak Lim committed
261
      tmpHandle = typename Mesh::HalfedgeHandle(int(randGen.getRand() * double(mesh_.n_halfedges() - 1.0)) );
262
#else
263
      tmpHandle = typename Mesh::HalfedgeHandle( ( double(rand()) / double(RAND_MAX) ) * double(mesh_.n_halfedges() - 1));
264
#endif
265
266

      // if it is not deleted, we analyse it
Jan Möbius's avatar
Jan Möbius committed
267
      if (!mesh_.status(tmpHandle).deleted()) {
268
269
270
271

        CollapseInfo ci(mesh_, tmpHandle);

        // Check if legal we analyze the priority of this collapse operation
Matthias Möller's avatar
Matthias Möller committed
272
        if (this->is_collapse_legal(ci)) {
Jan Möbius's avatar
Jan Möbius committed
273
274
275
276
277
278
279
280
            energy = this->collapse_priority(ci);

            if (energy != ModBaseT<Mesh>::ILLEGAL_COLLAPSE) {
              // Check if the current samples energy is better than any energy before
              if (energy < bestEnergy) {
                bestEnergy = energy;
                bestHandle = tmpHandle;
              }
281
            }
282
283
284
285
286
287
288
        } else {
          continue;
        }
      }

    }

289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
    // Found the best energy?
    if ( bestEnergy != FLT_MAX ) {

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

      // check topological correctness AGAIN !
      if (!this->is_collapse_legal(ci))
        continue;

      // adjust complexity in advance (need boundary status)

      // One vertex is killed by the collapse
      --nv;

      // If we are at a boundary, one face is lost,
      // otherwise two
      if (mesh_.is_boundary(ci.v0v1) || mesh_.is_boundary(ci.v1v0))
        --nf;
      else
        nf -= 2;

      // pre-processing
      this->preprocess_collapse(ci);

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

      // store current collapses state
      oldCollapses = n_collapses;
      noCollapses = 0;
      collapsesUnchanged = false;

      // update triangle normals
      typename Mesh::VertexFaceIter vf_it = mesh_.vf_iter(ci.v1);
      for (; vf_it; ++vf_it)
        if (!mesh_.status(vf_it).deleted())
          mesh_.set_normal(vf_it, mesh_.calc_face_normal(vf_it.handle()));

      // post-process collapse
      this->postprocess_collapse(ci);

    } else {
      if (oldCollapses == n_collapses) {
        if (collapsesUnchanged == false) {
          noCollapses = 1;
          collapsesUnchanged = true;
        } else {
          noCollapses++;
        }
      }
    }

  }

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

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

template<class Mesh>
size_t McDecimaterT<Mesh>::decimate_constraints_only(float _factor) {
Jan Möbius's avatar
Jan Möbius committed
353

354
355
356
357
358
359
360
  if (!this->is_initialized())
    return 0;

  if (_factor < 1.0)
    this->set_error_tolerance_factor(_factor);

  unsigned int n_collapses(0);
Jan Möbius's avatar
Jan Möbius committed
361
362
  size_t       nv = mesh_.n_vertices();
  size_t       nf = mesh_.n_faces();
363
364

  bool lastCollapseIllegal = false;
Jan Möbius's avatar
Jan Möbius committed
365
  // number of illegal collapses that occurred in a row
366
367
368
369
370
371
372
373
374
  unsigned int illegalCollapses = 0;

  bool collapsesUnchanged = false;
  // old n_collapses in order to check for convergence
  unsigned int oldCollapses = 0;
  // number of iterations where no new collapses where
  // performed in a row
  unsigned int noCollapses = 0;

Jan Möbius's avatar
Jan Möbius committed
375
376
  double energy     = FLT_MAX;
  double bestEnergy = FLT_MAX;
377

378
379
380
381
#ifdef WIN32
  RandomNumberGenerator randGen(mesh_.n_halfedges());
#endif

Jan Möbius's avatar
Jan Möbius committed
382
  while ((noCollapses <= 50) && (illegalCollapses <= 50) && (nv > 0) && (nf > 1)) {
383
384
385
386

    // Optimal id and value will be collected during the random sampling
    typename Mesh::HalfedgeHandle bestHandle(-1);
    typename Mesh::HalfedgeHandle tmpHandle(-1);
Jan Möbius's avatar
Jan Möbius committed
387
388
    bestEnergy = FLT_MAX;

389
390

#ifndef WIN32
Jan Möbius's avatar
Jan Möbius committed
391
    const double randomNormalizer = (1.0 / RAND_MAX) * (mesh_.n_halfedges() - 1);
392
#endif
393
394

    // Generate random samples for collapses
Jan Möbius's avatar
Jan Möbius committed
395
    for (int i = 0; i < (int) randomSamples_; ++i) {
396
397

      // Random halfedge handle
398
#ifdef WIN32
Isaak Lim's avatar
Isaak Lim committed
399
      tmpHandle = typename Mesh::HalfedgeHandle(int(randGen.getRand()  * double(mesh_.n_halfedges() - 1.0)) );
400
#else
Jan Möbius's avatar
Jan Möbius committed
401
      tmpHandle = typename Mesh::HalfedgeHandle(int(rand() * randomNormalizer ) );
402
#endif
403

Jan Möbius's avatar
Jan Möbius committed
404
405
      // if it is not deleted, we analyze it
      if (!mesh_.status(mesh_.edge_handle(tmpHandle)).deleted()) {
406
407
408
409
410
411

        CollapseInfo ci(mesh_, tmpHandle);

        // Check if legal we analyze the priority of this collapse operation
        if (this->is_collapse_legal(ci)) {

Jan Möbius's avatar
Jan Möbius committed
412
            energy = this->collapse_priority(ci);
413

Jan Möbius's avatar
Jan Möbius committed
414
415
416
417
418
419
420
            if (energy == ModBaseT<Mesh>::ILLEGAL_COLLAPSE) {
              if (lastCollapseIllegal) {
                illegalCollapses++;
              } else {
                illegalCollapses = 1;
                lastCollapseIllegal = true;
              }
421
            } else {
Jan Möbius's avatar
Jan Möbius committed
422

Jan Möbius's avatar
Jan Möbius committed
423
424
425
426
427
428
429
430
              illegalCollapses = 0;
              lastCollapseIllegal = false;

              // Check if the current samples energy is better than any energy before
              if (energy < bestEnergy) {
                bestEnergy = energy;
                bestHandle = tmpHandle;
              }
431
432
            }
        } else {
Jan Möbius's avatar
Jan Möbius committed
433

434
435
436
          continue;
        }
      }
437
438
439

    }

Jan Möbius's avatar
Jan Möbius committed
440
441


442
443
444
445
446
447
448
    // Found the best energy?
    if ( bestEnergy != FLT_MAX ) {

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

      // check topological correctness AGAIN !
Matthias Möller's avatar
Matthias Möller committed
449
      if (!this->is_collapse_legal(ci))
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
        continue;

      // adjust complexity in advance (need boundary status)

      // One vertex is killed by the collapse
      --nv;

      // If we are at a boundary, one face is lost,
      // otherwise two
      if (mesh_.is_boundary(ci.v0v1) || mesh_.is_boundary(ci.v1v0))
        --nf;
      else
        nf -= 2;

      // pre-processing
Matthias Möller's avatar
Matthias Möller committed
465
      this->preprocess_collapse(ci);
466
467
468
469
470

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

471
472
473
474
475
476
      // store current collapses state
      oldCollapses = n_collapses;
      noCollapses = 0;
      collapsesUnchanged = false;


477
478
479
480
481
482
483
      // update triangle normals
      typename Mesh::VertexFaceIter vf_it = mesh_.vf_iter(ci.v1);
      for (; vf_it; ++vf_it)
        if (!mesh_.status(vf_it).deleted())
          mesh_.set_normal(vf_it, mesh_.calc_face_normal(vf_it.handle()));

      // post-process collapse
Matthias Möller's avatar
Matthias Möller committed
484
      this->postprocess_collapse(ci);
485

486
487
488
489
490
491
492
493
494
    } else {
      if (oldCollapses == n_collapses) {
        if (collapsesUnchanged == false) {
          noCollapses = 1;
          collapsesUnchanged = true;
        } else {
          noCollapses++;
        }
      }
495
496
497
498
    }

  }

499
500
501
  if (_factor < 1.0)
    this->set_error_tolerance_factor(1.0);

502
503
  // DON'T do garbage collection here! It's up to the application.
  return n_collapses;
504

505
506
507
508
509
510
511
}

//=============================================================================
}// END_NS_MC_DECIMATER
} // END_NS_OPENMESH
//=============================================================================