OpenMesh
ModHausdorffT_impl.hh
Go to the documentation of this file.
1/* ========================================================================= *
2 * *
3 * OpenMesh *
4 * Copyright (c) 2001-2025, RWTH-Aachen University *
5 * Department of Computer Graphics and Multimedia *
6 * All rights reserved. *
7 * www.openmesh.org *
8 * *
9 *---------------------------------------------------------------------------*
10 * This file is part of OpenMesh. *
11 *---------------------------------------------------------------------------*
12 * *
13 * Redistribution and use in source and binary forms, with or without *
14 * modification, are permitted provided that the following conditions *
15 * are met: *
16 * *
17 * 1. Redistributions of source code must retain the above copyright notice, *
18 * this list of conditions and the following disclaimer. *
19 * *
20 * 2. Redistributions in binary form must reproduce the above copyright *
21 * notice, this list of conditions and the following disclaimer in the *
22 * documentation and/or other materials provided with the distribution. *
23 * *
24 * 3. Neither the name of the copyright holder nor the names of its *
25 * contributors may be used to endorse or promote products derived from *
26 * this software without specific prior written permission. *
27 * *
28 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS *
29 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED *
30 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A *
31 * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER *
32 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, *
33 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, *
34 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR *
35 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF *
36 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING *
37 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS *
38 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. *
39 * *
40 * ========================================================================= */
41
42
47//=============================================================================
48//
49// CLASS ModHausdorffT - IMPLEMENTATION
50//
51//=============================================================================
52
53#define OPENMESH_DECIMATER_MODHAUSDORFFT_C
54
55
56//== INCLUDES =================================================================
57
58#include "ModHausdorffT.hh"
59
60
61//== NAMESPACES ===============================================================
62
63namespace OpenMesh {
64namespace Decimater {
65
66//== IMPLEMENTATION ==========================================================
67
68template <class MeshT>
69typename ModHausdorffT<MeshT>::Scalar
70ModHausdorffT<MeshT>::
71distPointTriangleSquared( const Point& _p,
72 const Point& _v0,
73 const Point& _v1,
74 const Point& _v2 )
75{
76 const Point v0v1 = _v1 - _v0;
77 const Point v0v2 = _v2 - _v0;
78 const Point n = v0v1 % v0v2; // not normalized !
79 const Scalar d = sqrnorm(n);
80
81
82 // Check if the triangle is degenerated
83 if (d < FLT_MIN && d > -FLT_MIN) {
84 return -1.0;
85 }
86 const Scalar invD = static_cast<Scalar>(1.0) / d;
87
88 // these are not needed for every point, should still perform
89 // better with many points against one triangle
90 const Point v1v2 = _v2 - _v1;
91 const Scalar inv_v0v2_2 = static_cast<Scalar>(1.0) / sqrnorm(v0v2);
92 const Scalar inv_v0v1_2 = static_cast<Scalar>(1.0) / sqrnorm(v0v1);
93 const Scalar inv_v1v2_2 = static_cast<Scalar>(1.0) / sqrnorm(v1v2);
94
95
96 Point v0p = _p - _v0;
97 Point t = v0p % n;
98 typename Point::value_type s01, s02, s12;
99 const Scalar a = (t | v0v2) * -invD;
100 const Scalar b = (t | v0v1) * invD;
101
102 if (a < 0)
103 {
104 // Calculate the distance to an edge or a corner vertex
105 s02 = ( v0v2 | v0p ) * inv_v0v2_2;
106 if (s02 < 0.0)
107 {
108 s01 = ( v0v1 | v0p ) * inv_v0v1_2;
109 if (s01 <= 0.0) {
110 v0p = _v0;
111 } else if (s01 >= 1.0) {
112 v0p = _v1;
113 } else {
114 v0p = _v0 + v0v1 * s01;
115 }
116 } else if (s02 > 1.0) {
117 s12 = ( v1v2 | ( _p - _v1 )) * inv_v1v2_2;
118 if (s12 >= 1.0) {
119 v0p = _v2;
120 } else if (s12 <= 0.0) {
121 v0p = _v1;
122 } else {
123 v0p = _v1 + v1v2 * s12;
124 }
125 } else {
126 v0p = _v0 + v0v2 * s02;
127 }
128 } else if (b < 0.0) {
129 // Calculate the distance to an edge or a corner vertex
130 s01 = ( v0v1 | v0p ) * inv_v0v1_2;
131 if (s01 < 0.0)
132 {
133 // const Point n = v0v1 % v0v2; // not normalized !
134 s02 = ( v0v2 | v0p ) * inv_v0v2_2;
135 if (s02 <= 0.0) {
136 v0p = _v0;
137 } else if (s02 >= 1.0) {
138 v0p = _v2;
139 } else {
140 v0p = _v0 + v0v2 * s02;
141 }
142 } else if (s01 > 1.0) {
143 s12 = ( v1v2 | ( _p - _v1 )) * inv_v1v2_2;
144 if (s12 >= 1.0) {
145 v0p = _v2;
146 } else if (s12 <= 0.0) {
147 v0p = _v1;
148 } else {
149 v0p = _v1 + v1v2 * s12;
150 }
151 } else {
152 v0p = _v0 + v0v1 * s01;
153 }
154 } else if (a+b > 1.0) {
155 // Calculate the distance to an edge or a corner vertex
156 s12 = ( v1v2 | ( _p - _v1 )) * inv_v1v2_2;
157 if (s12 >= 1.0) {
158 s02 = ( v0v2 | v0p ) * inv_v0v2_2;
159 if (s02 <= 0.0) {
160 v0p = _v0;
161 } else if (s02 >= 1.0) {
162 v0p = _v2;
163 } else {
164 v0p = _v0 + v0v2*s02;
165 }
166 } else if (s12 <= 0.0) {
167 s01 = ( v0v1 | v0p ) * inv_v0v1_2;
168 if (s01 <= 0.0) {
169 v0p = _v0;
170 } else if (s01 >= 1.0) {
171 v0p = _v1;
172 } else {
173 v0p = _v0 + v0v1 * s01;
174 }
175 } else {
176 v0p = _v1 + v1v2 * s12;
177 }
178 } else {
179 // Calculate the distance to an interior point of the triangle
180 return sqrnorm( (_p - n*((n|v0p) * invD)) - _p);
181 }
182
183 return sqrnorm(v0p - _p);
184}
185
186
187template <class MeshT>
188void
191{
192 typename Mesh::FIter f_it(mesh_.faces_begin()), f_end(mesh_.faces_end());
193
194 for (; f_it!=f_end; ++f_it)
195 mesh_.property(points_, *f_it).clear();
196}
197
198
199//-----------------------------------------------------------------------------
200
201
202template <class MeshT>
203float
206{
207 std::vector<FaceHandle> faces; faces.reserve(20);
208 typename Mesh::VertexFaceIter vf_it;
209 typename Mesh::FaceHandle fh;
210 const typename Mesh::Scalar sqr_tolerace = tolerance_*tolerance_;
211 typename Mesh::CFVIter fv_it;
212 bool ok;
213
214 // Clear the temporary point storage
215 tmp_points_.clear();
216
217 // collect all points to be tested
218 // collect all faces to be tested against
219 for (vf_it=mesh_.vf_iter(_ci.v0); vf_it.is_valid(); ++vf_it) {
220 fh = *vf_it;
221
222 if (fh != _ci.fl && fh != _ci.fr)
223 faces.push_back(fh);
224
225 Points& pts = mesh_.property(points_, fh);
226 std::copy(pts.begin(), pts.end(), std::back_inserter(tmp_points_));
227 }
228
229 // add point to be removed
230 tmp_points_.push_back(_ci.p0);
231
232 // setup iterators
233 typename std::vector<FaceHandle>::iterator fh_it, fh_end(faces.end());
234 typename Points::const_iterator p_it, p_end(tmp_points_.end());
235
236 // simulate collapse
237 mesh_.set_point(_ci.v0, _ci.p1);
238
239 // for each point: try to find a face such that error is < tolerance
240 ok = true;
241
242 for (p_it=tmp_points_.begin(); ok && p_it!=p_end; ++p_it) {
243 ok = false;
244
245 for (fh_it=faces.begin(); !ok && fh_it!=fh_end; ++fh_it) {
246 fv_it=mesh_.cfv_iter(*fh_it);
247 const Point& p0 = mesh_.point(*fv_it);
248 const Point& p1 = mesh_.point(*(++fv_it));
249 const Point& p2 = mesh_.point(*(++fv_it));
250
251 if ( distPointTriangleSquared(*p_it, p0, p1, p2) <= sqr_tolerace)
252 ok = true;
253 }
254 }
255
256 // undo simulation changes
257 mesh_.set_point(_ci.v0, _ci.p0);
258
259 return ( ok ? static_cast<float>(Base::LEGAL_COLLAPSE) : static_cast<float>(Base::ILLEGAL_COLLAPSE) );
260}
261
262//-----------------------------------------------------------------------------
263
264template<class MeshT>
266 if (_factor >= 0.0 && _factor <= 1.0) {
267 // the smaller the factor, the smaller tolerance gets
268 // thus creating a stricter constraint
269 // division by error_tolerance_factor_ is for normalization
270 Scalar new_tolerance = tolerance_ * Scalar(_factor / this->error_tolerance_factor_);
271 set_tolerance(new_tolerance);
272 this->error_tolerance_factor_ = _factor;
273 }
274}
275
276//-----------------------------------------------------------------------------
277
278template <class MeshT>
279void
282{
283 typename Mesh::VertexFaceIter vf_it;
284 FaceHandle fh;
285 std::vector<FaceHandle> faces;
286
287
288 // collect points & neighboring triangles
289
290 tmp_points_.clear();
291 faces.reserve(20);
292
293 // collect active faces and their points
294 for (vf_it=mesh_.vf_iter(_ci.v1); vf_it.is_valid(); ++vf_it) {
295 fh = *vf_it;
296 faces.push_back(fh);
297
298 Points& pts = mesh_.property(points_, fh);
299 std::copy(pts.begin(), pts.end(), std::back_inserter(tmp_points_));
300 pts.clear();
301 }
302 if (faces.empty()) return; // should not happen anyway...
303
304
305 // collect points of the 2 deleted faces
306 if ((fh=_ci.fl).is_valid()) {
307 Points& pts = mesh_.property(points_, fh);
308 std::copy(pts.begin(), pts.end(), std::back_inserter(tmp_points_));
309 pts.clear();
310 }
311 if ((fh=_ci.fr).is_valid()) {
312 Points& pts = mesh_.property(points_, fh);
313 std::copy(pts.begin(), pts.end(), std::back_inserter(tmp_points_));
314 pts.clear();
315 }
316
317 // add the deleted point
318 tmp_points_.push_back(_ci.p0);
319
320
321 // setup iterators
322 typename std::vector<FaceHandle>::iterator fh_it, fh_end(faces.end());
323 typename Points::const_iterator p_it, p_end(tmp_points_.end());
324
325 // re-distribute points
326 Scalar emin, e;
327 typename Mesh::CFVIter fv_it;
328
329 for (p_it=tmp_points_.begin(); p_it!=p_end; ++p_it) {
330 emin = FLT_MAX;
331
332 for (fh_it=faces.begin(); fh_it!=fh_end; ++fh_it) {
333 fv_it=mesh_.cfv_iter(*fh_it);
334 const Point& p0 = mesh_.point(*fv_it);
335 const Point& p1 = mesh_.point(*(++fv_it));
336 const Point& p2 = mesh_.point(*(++fv_it));
337
338 e = distPointTriangleSquared(*p_it, p0, p1, p2);
339 if (e < emin) {
340 emin = e;
341 fh = *fh_it;
342 }
343
344 }
345
346 mesh_.property(points_, fh).push_back(*p_it);
347 }
348}
349
350
351//-----------------------------------------------------------------------------
352
353
354template <class MeshT>
355typename ModHausdorffT<MeshT>::Scalar
357compute_sqr_error(FaceHandle _fh, const Point& _p) const
358{
359 typename Mesh::CFVIter fv_it = mesh_.cfv_iter(_fh);
360 const Point& p0 = mesh_.point(fv_it);
361 const Point& p1 = mesh_.point(++fv_it);
362 const Point& p2 = mesh_.point(++fv_it);
363
364 const Points& points = mesh_.property(points_, _fh);
365 typename Points::const_iterator p_it = points.begin();
366 typename Points::const_iterator p_end = points.end();
367
368 Point dummy;
369 Scalar e;
370 Scalar emax = distPointTriangleSquared(_p, p0, p1, p2);
371
372
373
374 for (; p_it!=p_end; ++p_it) {
375 e = distPointTriangleSquared(*p_it, p0, p1, p2);
376 if (e > emax)
377 emax = e;
378 }
379
380 return emax;
381}
382
383
384//=============================================================================
385}
386}
387//=============================================================================
Contains all the mesh ingredients like the polygonal mesh, the triangle mesh, different mesh kernels ...
Definition: MeshItems.hh:59
Handle for a face entity.
Definition: Handles.hh:142
Kernel::Scalar Scalar
Scalar type.
Definition: PolyMeshT.hh:110
Kernel::VertexFaceIter VertexFaceIter
Circulator.
Definition: PolyMeshT.hh:166
Stores information about a halfedge collapse.
Definition: CollapseInfoT.hh:74
Mesh::FaceHandle fr
Right face.
Definition: CollapseInfoT.hh:87
Mesh::Point p0
Position of removed vertex.
Definition: CollapseInfoT.hh:84
Mesh::VertexHandle v1
Remaining vertex.
Definition: CollapseInfoT.hh:83
Mesh::Point p1
Positions of remaining vertex.
Definition: CollapseInfoT.hh:85
Mesh::VertexHandle v0
Vertex to be removed.
Definition: CollapseInfoT.hh:82
Mesh::FaceHandle fl
Left face.
Definition: CollapseInfoT.hh:86
Use Hausdorff distance to control decimation.
Definition: ModHausdorffT.hh:79
virtual float collapse_priority(const CollapseInfo &_ci) override
compute Hausdorff error for one-ring
Definition: ModHausdorffT_impl.hh:205
virtual void postprocess_collapse(const CollapseInfo &_ci) override
re-distribute points
Definition: ModHausdorffT_impl.hh:281
virtual void initialize() override
reset per-face point lists
Definition: ModHausdorffT_impl.hh:190
void set_error_tolerance_factor(double _factor) override
set the percentage of tolerance
Definition: ModHausdorffT_impl.hh:265

Project OpenMesh, ©  Visual Computing Institute, RWTH Aachen. Documentation generated using doxygen .