McDecimaterT.cc 10.1 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
 *   $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

63
64
65
66
#ifdef USE_OPENMP
#include <omp.h>
#endif

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
110
111
112
113
114
115
116
    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
117
118
119
#ifdef USE_OPENMP
#pragma omp parallel for shared(bestEnergy, bestHandle)
#endif
120
121
122
    for ( unsigned int i = 0; i < randomSamples_; ++i) {

      // Random halfedge handle
Matthias Möller's avatar
Matthias Möller committed
123
      typename Mesh::HalfedgeHandle tmpHandle = typename Mesh::HalfedgeHandle((static_cast<double>(rand()) / RAND_MAX) * (mesh_.n_halfedges()-1) );
124
125
126
127
128
129
130

      // 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
131
132
        if (this->is_collapse_legal(ci)) {
          double energy = this->collapse_priority(ci);
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152

          // 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 !
153
      if (!this->is_collapse_legal(ci))
154
155
156
        continue;

      // pre-processing
157
      this->preprocess_collapse(ci);
158
159
160
161
162
163
164
165
166
167
168
169

      // 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
170
      this->postprocess_collapse(ci);
171
172
173
174
175
176
177
178
179
180
181
182
183

    }

  }

  // 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) {
184
  if (!this->is_initialized())
185
186
187
188
189
190
    return 0;

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

191
192
193
194
195
196
197
198
199
200
201
202

  // 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
203
  while ( !foundNoLegalCollapsesThrice && (_nv < nv) && (_nf < nf) ) {
204
205
206
207
208
209

    // 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
210
    unsigned int legalCollapses = 0;
211
212
213
#ifdef USE_OPENMP
#pragma omp parallel for shared(bestEnergy, bestHandle, legalCollapses)
#endif
214
215
216
    for ( unsigned int i = 0; i < randomSamples_; ++i) {

      // Random halfedge handle
Matthias Möller's avatar
Matthias Möller committed
217
      typename Mesh::HalfedgeHandle tmpHandle = typename Mesh::HalfedgeHandle((static_cast<double>(rand()) / RAND_MAX) * (mesh_.n_halfedges()-1) );
218
219
220
221
222
223
224

      // 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
225
        if (this->is_collapse_legal(ci)) {
226
          ++legalCollapses;
Matthias Möller's avatar
Matthias Möller committed
227
          double energy = this->collapse_priority(ci);
228
229
230
231
232
233
234
235
236
237
238
239
240

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

    }

241
242
243
244
245
246
247
248
249
    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;
    }

250
251
252
253
254
255
256
    // 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
257
      if (!this->is_collapse_legal(ci))
258
259
260
261
262
263
264
265
266
267
268
269
270
271
        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;

272

273
      // pre-processing
Matthias Möller's avatar
Matthias Möller committed
274
      this->preprocess_collapse(ci);
275
276
277
278
279
280
281
282
283
284
285
286

      // 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
287
      this->postprocess_collapse(ci);
288
289
290
291
292
293
294
295
296
297
298
299
300
301

    }

  }

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

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