McDecimaterT.cc 9.91 KB
Newer Older
1
2
3
4
5
6
/*===========================================================================*\
 *                                                                           *
 *                               OpenMesh                                    *
 *      Copyright (C) 2001-2011 by Computer Graphics Group, RWTH Aachen      *
 *                           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
 *                                                                           *
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
 *   $Revision: 460 $                                                         *
 *   $Date: 2011-11-16 10:45:08 +0100 (Mi, 16 Nov 2011) $                   *
 *                                                                           *
 \*===========================================================================*/

/** \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

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

namespace OpenMesh {
namespace Decimater {

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

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

  // 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) {

101
  if (!this->is_initialized())
102
103
104
105
106
107
108
109
110
111
112
113
114
115
    return 0;

  unsigned int n_collapses(0);

  while ( n_collapses <  _n_collapses) {

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

    // Generate random samples for collapses
    for ( unsigned int i = 0; i < randomSamples_; ++i) {

      // Random halfedge handle
Matthias Möller's avatar
Matthias Möller committed
116
      typename Mesh::HalfedgeHandle tmpHandle = typename Mesh::HalfedgeHandle((static_cast<double>(rand()) / RAND_MAX) * (mesh_.n_halfedges()-1) );
117
118
119
120
121
122
123

      // 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
124
125
        if (this->is_collapse_legal(ci)) {
          double energy = this->collapse_priority(ci);
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145

          // Check if the current samples energy is better than any energy before
          if ( energy < bestEnergy ) {
            bestEnergy = energy;
            bestHandle = tmpHandle;
          }
        } else {
          continue;
        }
      }

    }

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

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

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

      // pre-processing
150
      this->preprocess_collapse(ci);
151
152
153
154
155
156
157
158
159
160
161
162

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

      // 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
163
      this->postprocess_collapse(ci);
164
165
166
167
168
169
170
171
172
173
174
175
176

    }

  }

  // 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) {
177
  if (!this->is_initialized())
178
179
180
181
182
183
    return 0;

  unsigned int nv = mesh_.n_vertices();
  unsigned int nf = mesh_.n_faces();
  unsigned int n_collapses(0);

184
185
186
187
188
189
190
191
192
193
194
195

  // check if no vertex or face contraints were set
  bool contraintsOnly = (_nv == 0) && (_nf == 1);

  // check if no legal collapses were found three times in a row
  // for the sampled halfedges
  bool foundNoLegalCollapsesThrice = false;

  // store the last two amount of legal collapses found
  int lastLegalCollapses = -1;
  int beforeLastLegalCollapses = -1;

Isaak Lim's avatar
Isaak Lim committed
196
  while ( !foundNoLegalCollapsesThrice && (_nv < nv) && (_nf < nf) ) {
197
198
199
200
201
202

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

    // Generate random samples for collapses
203
    unsigned int legalCollapses = 0;
204
205
206
    for ( unsigned int i = 0; i < randomSamples_; ++i) {

      // Random halfedge handle
Matthias Möller's avatar
Matthias Möller committed
207
      typename Mesh::HalfedgeHandle tmpHandle = typename Mesh::HalfedgeHandle((static_cast<double>(rand()) / RAND_MAX) * (mesh_.n_halfedges()-1) );
208
209
210
211
212
213
214

      // 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
Matthias Möller's avatar
Matthias Möller committed
215
        if (this->is_collapse_legal(ci)) {
216
          ++legalCollapses;
Matthias Möller's avatar
Matthias Möller committed
217
          double energy = this->collapse_priority(ci);
218
219
220
221
222
223
224
225
226
227
228
229
230

          // Check if the current samples energy is better than any energy before
          if ( energy < bestEnergy ) {
            bestEnergy = energy;
            bestHandle = tmpHandle;
          }
        } else {
          continue;
        }
      }

    }

231
232
233
234
235
236
237
238
239
    if (contraintsOnly) {
      // check if no legal collapses were found three times in a row
      foundNoLegalCollapsesThrice = (beforeLastLegalCollapses == 0) && (lastLegalCollapses == 0) && (legalCollapses == 0);

      // store amount of last legal collapses found
      beforeLastLegalCollapses = lastLegalCollapses;
      lastLegalCollapses = legalCollapses;
    }

240
241
242
243
244
245
246
    // 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
247
      if (!this->is_collapse_legal(ci))
248
249
250
251
252
253
254
255
256
257
258
259
260
261
        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;

262

263
      // pre-processing
Matthias Möller's avatar
Matthias Möller committed
264
      this->preprocess_collapse(ci);
265
266
267
268
269
270
271
272
273
274
275
276

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

      // 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
277
      this->postprocess_collapse(ci);
278
279
280
281
282
283
284
285
286
287
288
289
290
291

    }

  }

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

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