| OpenMesh

ModHausdorffT_impl.hh
Go to the documentation of this file.
1 /* ========================================================================= *
2 * *
3 * OpenMesh *
4 * Copyright (c) 2001-2015, 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
63 namespace OpenMesh {
64 namespace Decimater {
65
66 //== IMPLEMENTATION ==========================================================
67
68 template <class MeshT>
69 typename ModHausdorffT<MeshT>::Scalar
70 ModHausdorffT<MeshT>::
71 distPointTriangleSquared( 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 = n.sqrnorm();
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) / v0v2.sqrnorm();
92 const Scalar inv_v0v1_2 = static_cast<Scalar>(1.0) / v0v1.sqrnorm();
93 const Scalar inv_v1v2_2 = static_cast<Scalar>(1.0) / v1v2.sqrnorm();
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 ( (_p - n*((n|v0p) * invD)) - _p).sqrnorm();
181 }
182
183 return (v0p - _p).sqrnorm();
184 }
185
186
187 template <class MeshT>
188 void
189 ModHausdorffT<MeshT>::
190 initialize()
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
202 template <class MeshT>
203 float
204 ModHausdorffT<MeshT>::
205 collapse_priority(const CollapseInfo& _ci)
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 ? Base::LEGAL_COLLAPSE : Base::ILLEGAL_COLLAPSE );
260 }
261
262 //-----------------------------------------------------------------------------
263
264 template<class MeshT>
265 void ModHausdorffT<MeshT>::set_error_tolerance_factor(double _factor) {
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 tolerance = tolerance_ * Scalar(_factor / this->error_tolerance_factor_);
271 set_tolerance(tolerance);
272 this->error_tolerance_factor_ = _factor;
273 }
274 }
275
276 //-----------------------------------------------------------------------------
277
278 template <class MeshT>
279 void
280 ModHausdorffT<MeshT>::
281 postprocess_collapse(const CollapseInfo& _ci)
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
354 template <class MeshT>
355 typename ModHausdorffT<MeshT>::Scalar
356 ModHausdorffT<MeshT>::
357 compute_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 //=============================================================================
OpenMesh::PolyMeshT::Scalar
Kernel::Scalar Scalar
Scalar type.
Definition: PolyMeshT.hh:110
OpenMesh::PolyMeshT::VertexFaceIter
Kernel::VertexFaceIter VertexFaceIter
Circulator.
Definition: PolyMeshT.hh:166
OpenMesh::Decimater::ModHausdorffT::set_error_tolerance_factor
void set_error_tolerance_factor(double _factor)
set the percentage of tolerance
Definition: ModHausdorffT_impl.hh:265
OpenMesh::Decimater::CollapseInfoT::p0
Mesh::Point p0
Position of removed vertex.
Definition: CollapseInfoT.hh:93
OpenMesh::Decimater::ModHausdorffT::postprocess_collapse
virtual void postprocess_collapse(const CollapseInfo &_ci)
re-distribute points
Definition: ModHausdorffT_impl.hh:281
ModHausdorffT.hh
OpenMesh::Decimater::CollapseInfoT::fr
Mesh::FaceHandle fr
Right face.
Definition: CollapseInfoT.hh:96
OpenMesh::Decimater::ModHausdorffT
Use Hausdorff distance to control decimation.
Definition: ModHausdorffT.hh:79
OpenMesh
Contains all the mesh ingredients like the polygonal mesh, the triangle mesh, different mesh kernels ...
Definition: MeshItems.hh:59
OpenMesh::Decimater::CollapseInfoT::p1
Mesh::Point p1
Positions of remaining vertex.
Definition: CollapseInfoT.hh:94
OpenMesh::Decimater::CollapseInfoT::v1
Mesh::VertexHandle v1
Remaining vertex.
Definition: CollapseInfoT.hh:92
OpenMesh::Decimater::CollapseInfoT::fl
Mesh::FaceHandle fl
Left face.
Definition: CollapseInfoT.hh:95
OpenMesh::Decimater::CollapseInfoT
Stores information about a halfedge collapse.
Definition: CollapseInfoT.hh:74
OpenMesh::Decimater::ModHausdorffT::initialize
virtual void initialize()
reset per-face point lists
Definition: ModHausdorffT_impl.hh:190
OpenMesh::Decimater::ModHausdorffT::collapse_priority
virtual float collapse_priority(const CollapseInfo &_ci)
compute Hausdorff error for one-ring
Definition: ModHausdorffT_impl.hh:205
OpenMesh::Decimater::CollapseInfoT::v0
Mesh::VertexHandle v0
Vertex to be removed.
Definition: CollapseInfoT.hh:91