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
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
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>
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
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
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 //=============================================================================
Kernel::Scalar Scalar
Scalar type.
Definition: PolyMeshT.hh:110
Kernel::VertexFaceIter VertexFaceIter
Circulator.
Definition: PolyMeshT.hh:166
void set_error_tolerance_factor(double _factor)
set the percentage of tolerance
Definition: ModHausdorffT_impl.hh:265
Mesh::Point p0
Position of removed vertex.
Definition: CollapseInfoT.hh:93
virtual void postprocess_collapse(const CollapseInfo &_ci)
re-distribute points
Definition: ModHausdorffT_impl.hh:281
Mesh::FaceHandle fr
Right face.
Definition: CollapseInfoT.hh:96
Use Hausdorff distance to control decimation.
Definition: ModHausdorffT.hh:79
Contains all the mesh ingredients like the polygonal mesh, the triangle mesh, different mesh kernels ...
Definition: MeshItems.hh:59
Mesh::Point p1
Positions of remaining vertex.
Definition: CollapseInfoT.hh:94
Mesh::VertexHandle v1
Remaining vertex.
Definition: CollapseInfoT.hh:92
Mesh::FaceHandle fl
Left face.
Definition: CollapseInfoT.hh:95
Stores information about a halfedge collapse.
Definition: CollapseInfoT.hh:74
virtual void initialize()
reset per-face point lists
Definition: ModHausdorffT_impl.hh:190
virtual float collapse_priority(const CollapseInfo &_ci)
compute Hausdorff error for one-ring
Definition: ModHausdorffT_impl.hh:205
Mesh::VertexHandle v0
Vertex to be removed.
Definition: CollapseInfoT.hh:91

Project OpenMesh, ©  Computer Graphics Group, RWTH Aachen. Documentation generated using doxygen .