Visualization Library 2.1.0

A lightweight C++ OpenGL middleware for 2D/3D graphics

VL     Star     Watch     Fork     Issue

[Download] [Tutorials] [All Classes] [Grouped Classes]
PolygonSimplifier.hpp
Go to the documentation of this file.
1 /**************************************************************************************/
2 /* */
3 /* Visualization Library */
4 /* http://visualizationlibrary.org */
5 /* */
6 /* Copyright (c) 2005-2020, Michele Bosi */
7 /* All rights reserved. */
8 /* */
9 /* Redistribution and use in source and binary forms, with or without modification, */
10 /* are permitted provided that the following conditions are met: */
11 /* */
12 /* - Redistributions of source code must retain the above copyright notice, this */
13 /* list of conditions and the following disclaimer. */
14 /* */
15 /* - Redistributions in binary form must reproduce the above copyright notice, this */
16 /* list of conditions and the following disclaimer in the documentation and/or */
17 /* other materials provided with the distribution. */
18 /* */
19 /* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND */
20 /* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED */
21 /* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE */
22 /* DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR */
23 /* ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES */
24 /* (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; */
25 /* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON */
26 /* ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT */
27 /* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS */
28 /* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */
29 /* */
30 /**************************************************************************************/
31 
32 #ifndef PolygonSimplifier_INCLUDE_ONCE
33 #define PolygonSimplifier_INCLUDE_ONCE
34 
36 #include <vlCore/Object.hpp>
37 #include <vlCore/Vector3.hpp>
38 #include <vlCore/glsl_math.hpp>
39 #include <vector>
40 #include <algorithm>
41 
42 namespace vl
43 {
44  class Geometry;
45 //-----------------------------------------------------------------------------
46 // PolygonSimplifier
47 //-----------------------------------------------------------------------------
53  {
55 
56  public:
57  class Vertex;
58  //-----------------------------------------------------------------------------
59  // QErr
60  //-----------------------------------------------------------------------------
62  class QErr
63  {
64  public:
65  QErr()
66  {
67  a2 = 0.0;
68  ab = 0.0;
69  ac = 0.0;
70  ad = 0.0;
71  b2 = 0.0;
72  bc = 0.0;
73  bd = 0.0;
74  c2 = 0.0;
75  cd = 0.0;
76  d2 = 0.0;
77  }
78 
79  QErr(const dvec3& n, double d, double w = 1.0)
80  {
81  a2 = w * n.x() * n.x();
82  ab = w * n.x() * n.y();
83  ac = w * n.x() * n.z();
84  ad = w * n.x() * d;
85  b2 = w * n.y() * n.y();
86  bc = w * n.y() * n.z();
87  bd = w * n.y() * d;
88  c2 = w * n.z() * n.z();
89  cd = w * n.z() * d;
90  d2 = w * d*d;
91 
92  // indeterminate cases
93  VL_CHECK( d2 == d2 )
94  }
95 
96  dmat3 matrix() const
97  {
98  return dmat3(
99  a2, ab, ac,
100  ab, b2, bc,
101  ac, bc, c2 );
102  }
103 
104  dvec3 vector() const
105  {
106  return dvec3( ad, bd, cd );
107  }
108 
109  double offset() const
110  {
111  return d2;
112  }
113 
114  double evaluate(const dvec3& v) const
115  {
116  return v.x()*v.x()*a2 + 2*v.x()*v.y()*ab + 2*v.x()*v.z()*ac + 2*v.x()*ad
117  + v.y()*v.y()*b2 + 2*v.y()*v.z()*bc + 2*v.y()*bd
118  + v.z()*v.z()*c2 + 2*v.z()*cd
119  + d2;
120  }
121 
122  bool analyticSolution(dvec3& v) const
123  {
124 #if 0
125  dmat3 Ainv;
126  double det = matrix().getInverse(Ainv);
127  if (!det)
128  return false;
129  v = -(Ainv*vector());
130  return true;
131 #else
132  double A = c2*b2-bc*bc;
133  double B = bc*ac-c2*ab;
134  double C = bc*ab-b2*ac;
135  double det = a2*(A)+ab*(B)+ac*(C);
136  if (fabs(det) < 0.0000001)
137  return false;
138  else
139  {
140  double inv_det = 1.0 / det;
141  dmat3 Ainv( A*inv_det, B*inv_det, C*inv_det,
142  (ac*bc-c2*ab)*inv_det, (c2*a2-ac*ac)*inv_det, (ab*ac-bc*a2)*inv_det,
143  (bc*ab-ac*b2)*inv_det, (ac*ab-bc*a2)*inv_det, (b2*a2-ab*ab)*inv_det );
144  v = Ainv * dvec3( -ad, -bd, -cd );
145  return true;
146  }
147 #endif
148  }
149 
150  QErr operator+(const QErr& other)
151  {
152  QErr q = *this;
153  q.a2 += other.a2;
154  q.ab += other.ab;
155  q.ac += other.ac;
156  q.ad += other.ad;
157  q.b2 += other.b2;
158  q.bc += other.bc;
159  q.bd += other.bd;
160  q.c2 += other.c2;
161  q.cd += other.cd;
162  q.d2 += other.d2;
163  return q;
164  }
165 
166  const QErr& operator+=(const QErr& other)
167  {
168  a2 += other.a2;
169  ab += other.ab;
170  ac += other.ac;
171  ad += other.ad;
172  b2 += other.b2;
173  bc += other.bc;
174  bd += other.bd;
175  c2 += other.c2;
176  cd += other.cd;
177  d2 += other.d2;
178  return *this;
179  }
180 
181  protected:
182  // coefficients
183  double a2, ab, ac, ad;
184  double b2, bc, bd;
185  double c2, cd;
186  double d2;
187  };
188  //-----------------------------------------------------------------------------
189  // Triangle
190  //-----------------------------------------------------------------------------
192  class Triangle
193  {
194  friend class PolygonSimplifier;
195  friend class Vertex;
196  public:
197  Triangle(): mRemoved(false)
198  {
199  mVertices[0] = NULL;
200  mVertices[1] = NULL;
201  mVertices[2] = NULL;
202  }
203 
204  inline void replaceVertex( Vertex* oldv, Vertex* newv );
205  inline void computeNormal();
206  inline float computeArea() const;
207  inline float computePotentialArea(const Vertex* oldv, const Vertex* newv) const;
208  inline fvec3 computePotentialNormal(const Vertex* oldv, const Vertex* newv) const;
209  inline bool hasVertex(const Vertex*v) const;
210  inline bool checkTriangle() const;
211  // inline float computeDistance(const fvec3&) const;
212  inline QErr computeQErr() const;
213 
215  const Vertex* vertex(int index) const { return mVertices[index]; }
216  Vertex* vertex(int index) { return mVertices[index]; }
218  const fvec3& normal() const { return mNormal; }
220  // float area() const { return mArea; }
222  bool removed() const { return mRemoved; }
224 
225  protected:
227  Vertex* mVertices[3];
231  // float mArea;
233  bool mRemoved;
234  };
235  //-----------------------------------------------------------------------------
236  // Vertex
237  //-----------------------------------------------------------------------------
239  class Vertex
240  {
241  friend class Triangle;
242  friend class PolygonSimplifier;
243  public:
244  Vertex(): mCollapseCost(0.0f), mOriginalIndex(-1) , mSimplifiedIndex(-1), mRemoveOrder(-1),
245  mRemoved(false), mProtected(false), mAlreadyProcessed(false)
246  {
247  }
248 
249  inline void addAdjacentVertex(Vertex* v);
250  inline void removeAdjacentVertex(Vertex* v);
251  inline void computeAdjacentVertices();
252  inline bool checkConnectivity();
253  inline bool isAdjacentVertex(Vertex*) const;
254  inline bool isIncidentTriangle(Triangle*) const;
255  inline void discardRemovedTriangles();
256  inline void removeIncidentTriangle(const Triangle*);
257  inline bool checkTriangles() const;
258  inline void computeEdgePenalty();
259 
261  const fvec3& position() const { return mPosition; }
263  int adjacentVerticesCount() const { return (int)mAdjacentVerts.size(); }
264  Vertex* adjacentVertex(int index) const { return mAdjacentVerts[index]; }
266  int incidentTrianglesCount() const { return (int)mIncidentTriangles.size(); }
267  Triangle* incidentTriangle(int index) const { return mIncidentTriangles[index]; }
269  Vertex* collapseVertex() const { return mCollapseVertex; }
271  float collapseCost() const { return mCollapseCost; }
273  const fvec3& collapsePosition() const { return mCollapsePosition; }
274  void setCollapsePosition(const fvec3& pos) { mCollapsePosition = pos; }
276  int removeOrder() const { return mRemoveOrder; }
278  bool removed() const { return mRemoved; }
280  bool isProtected() const { return mProtected; }
282  int originalIndex() const { return mOriginalIndex; }
284  int simplifiedIndex() const { return mSimplifiedIndex; }
286  bool alreadyProcessed() const { return mAlreadyProcessed; }
288  const QErr& qerr() const { return mQErr; }
289  void setQErr(const QErr& qerr) { mQErr = qerr; }
290  void addQErr(const QErr& qerr) { mQErr += qerr; }
291 
292  protected:
297  std::vector< Vertex* > mAdjacentVerts;
299  std::vector< Triangle* > mIncidentTriangles;
313  bool mRemoved;
318  };
319 
320  public:
321  PolygonSimplifier(): mRemoveDoubles(false), mVerbose(true), mQuick(true) {}
322 
323  void simplify();
324  void simplify(const std::vector<fvec3>& in_verts, const std::vector<int>& in_tris);
325 
326  void setIntput(Geometry* geom) { mInput = geom; }
327  Geometry* input() { return mInput.get(); }
328  const Geometry* input() const { return mInput.get(); }
329 
330  std::vector< u32 >& targets() { return mTargets; }
331  const std::vector< u32 >& targets() const { return mTargets; }
332 
333  std::vector< ref<Geometry> >& output() { return mOutput; }
334  const std::vector< ref<Geometry> >& output() const { return mOutput; }
335 
336  void setProtectedVertices(const std::vector<int>& protected_verts) { mProtectedVerts = protected_verts; }
337 
338  int simplifiedVerticesCount() const { return (int)mSimplifiedVertices.size(); }
339  Vertex* simplifiedVertices(int index) const { return mSimplifiedVertices[index]; }
340 
341  int simplifiedTrianglesCount() const { return (int)mSimplifiedTriangles.size(); }
342  Triangle* simplifiedTriangles(int index) const { return mSimplifiedTriangles[index]; }
343 
344  void clearTrianglesAndVertices();
345 
346  bool removeDoubles() const { return mRemoveDoubles; }
347  void setRemoveDoubles(bool remove_doubles) { mRemoveDoubles = remove_doubles; }
348 
349  bool verbose() const { return mVerbose; }
350  void setVerbose(bool verbose) { mVerbose = verbose; }
351 
352  bool quick() const { return mQuick; }
353  void setQuick(bool quick) { mQuick = quick; }
354 
355  protected:
356  void outputSimplifiedGeometry();
357  inline void collapse(Vertex* v);
358  inline void computeCollapseInfo(Vertex* v);
359 
360  protected:
362  std::vector< ref<Geometry> > mOutput;
363  std::vector< u32 > mTargets;
364  std::vector<Vertex*> mSimplifiedVertices;
365  std::vector<Triangle*> mSimplifiedTriangles;
366  std::vector<int> mProtectedVerts;
368  bool mVerbose;
369  bool mQuick;
370 
371  private:
372  std::vector<Triangle> mTriangleLump;
373  std::vector<Vertex> mVertexLump;
374  };
375  //-----------------------------------------------------------------------------
376  // Vertex
377  //-----------------------------------------------------------------------------
379  {
380  if( v != this )
381  {
382  for(int i=0; i<adjacentVerticesCount(); ++i)
383  if (mAdjacentVerts[i] == v)
384  return;
385  mAdjacentVerts.push_back(v);
386  }
387  }
388  //-----------------------------------------------------------------------------
390  {
391  VL_CHECK( v != this )
392  VL_CHECK( std::find(mAdjacentVerts.begin(), mAdjacentVerts.end(), v) != mAdjacentVerts.end() )
393  for(int i=0; i<adjacentVerticesCount(); ++i)
394  if (mAdjacentVerts[i] == v)
395  {
396  mAdjacentVerts.erase(mAdjacentVerts.begin() + i);
397  return;
398  }
399  }
400  //-----------------------------------------------------------------------------
402  {
403  mAdjacentVerts.clear();
404  for(int itri=0; itri<incidentTrianglesCount(); ++itri)
405  {
406  VL_CHECK(!mIncidentTriangles[itri]->mRemoved)
407  addAdjacentVertex( mIncidentTriangles[itri]->mVertices[0] );
408  addAdjacentVertex( mIncidentTriangles[itri]->mVertices[1] );
409  addAdjacentVertex( mIncidentTriangles[itri]->mVertices[2] );
410  }
411  mRemoved = mAdjacentVerts.empty();
412  }
413  //-----------------------------------------------------------------------------
415  {
416  for(int itri=incidentTrianglesCount(); itri--; )
417  if ( !incidentTriangle(itri)->checkTriangle() )
418  return false;
419  return true;
420  }
421  //-----------------------------------------------------------------------------
423  {
424  for(int ivert=0; ivert<adjacentVerticesCount(); ++ivert)
425  {
426  int edge_count = 0;
427  int border_tri = -1;
428  for(int itri=0; itri<incidentTrianglesCount() && edge_count<=1; ++itri)
429  {
430  if ( incidentTriangle(itri)->hasVertex( adjacentVertex(ivert) ) )
431  {
432  border_tri = itri;
433  ++edge_count;
434  }
435  }
436  if ( edge_count == 1 )
437  {
438  fvec3 edge = position() - adjacentVertex(ivert)->position();
439  dvec3 n = (dvec3)cross(incidentTriangle(border_tri)->normal(), edge );
440  n.normalize();
441  double d = -dot(n,(dvec3)position());
442  mQErr += QErr( n, d, dot(edge, edge) * 1.0 );
443  }
444  }
445  }
447  {
448  for(int itri=incidentTrianglesCount(); itri--; )
449  {
450  if (mIncidentTriangles[itri] == tri)
451  {
452  mIncidentTriangles.erase( mIncidentTriangles.begin() + itri );
453  break;
454  }
455  }
456  }
457  //-----------------------------------------------------------------------------
459  {
460  for(int itri=incidentTrianglesCount(); itri--; )
461  {
462  if (mIncidentTriangles[itri]->mRemoved)
463  mIncidentTriangles.erase( mIncidentTriangles.begin() + itri );
464  }
465  }
466  //-----------------------------------------------------------------------------
468  {
469  for(int i=0; i<adjacentVerticesCount(); ++i)
470  if ( adjacentVertex(i) == v )
471  return true;
472  return false;
473  }
474  //-----------------------------------------------------------------------------
476  {
477  for(int i=0; i<incidentTrianglesCount(); ++i)
478  if ( incidentTriangle(i) == t )
479  return true;
480  return false;
481  }
482  //-----------------------------------------------------------------------------
484  {
485  VL_CHECK( mCollapseVertex )
486  VL_CHECK( !mCollapseVertex->removed() )
487  // check connectivity consistency
488  for(int ivert=0; ivert<adjacentVerticesCount(); ++ivert)
489  {
490  Vertex* adj = mAdjacentVerts[ivert];
491  if ( adj->removed() )
492  return false;
493  if( std::find(adj->mAdjacentVerts.begin(), adj->mAdjacentVerts.end(), this) == adj->mAdjacentVerts.end() )
494  return false;
495  }
496  return true;
497  }
498  //-----------------------------------------------------------------------------
499  // Triangle
500  //-----------------------------------------------------------------------------
502  {
503  dvec3 n = (dvec3)normal();
504  double d = -dot((dvec3)vertex(0)->position(), n);
505  QErr qerr(n, d, computeArea() * (1.0 / 3.0) );
506  return qerr;
507  }
508  //-----------------------------------------------------------------------------
510  {
511  fvec3 a = (mVertices[0]->mPosition == oldv->mPosition ? newv->mPosition : mVertices[0]->mPosition);
512  fvec3 b = (mVertices[1]->mPosition == oldv->mPosition ? newv->mPosition : mVertices[1]->mPosition) - a;
513  fvec3 c = (mVertices[2]->mPosition == oldv->mPosition ? newv->mPosition : mVertices[2]->mPosition) - a;
514 
515  fvec3 n = cross(b,c);
516  n.normalize();
517  return n;
518  }
519  //-----------------------------------------------------------------------------
521  {
522  bool ok = true;
523  ok &= !mVertices[0]->removed(); VL_CHECK(ok)
524  ok &= !mVertices[1]->removed(); VL_CHECK(ok)
525  ok &= !mVertices[2]->removed(); VL_CHECK(ok)
526  ok &= mVertices[0] != mVertices[1]; VL_CHECK(ok)
527  ok &= mVertices[0] != mVertices[2]; VL_CHECK(ok)
528  ok &= mVertices[1] != mVertices[2]; VL_CHECK(ok)
529  return ok;
530  }
531  //-----------------------------------------------------------------------------
533  {
534  return mVertices[0] == v || mVertices[1] == v || mVertices[2] == v;
535  }
536  //-----------------------------------------------------------------------------
537  inline float PolygonSimplifier::Triangle::computePotentialArea(const Vertex* oldv, const Vertex* newv) const
538  {
539  fvec3 A = (mVertices[0]->mPosition == oldv->mPosition ? newv->mPosition : mVertices[0]->mPosition);
540  fvec3 B = (mVertices[1]->mPosition == oldv->mPosition ? newv->mPosition : mVertices[1]->mPosition) - A;
541  fvec3 C = (mVertices[2]->mPosition == oldv->mPosition ? newv->mPosition : mVertices[2]->mPosition) - A;
542 
543  float base = 0.0f;
544  float height = 0.0f;
545  fvec3 AC = C-A;
546  fvec3 AB = B-A;
547  base = AB.length();
548  AB = AB * (1.0f / base); // normalize
549  fvec3 h = vl::dot(AC,AB) * AB + A;
550  height = (C-h).length();
551 
552  return base * height * 0.5f;
553  }
554  //-----------------------------------------------------------------------------
556  {
557  const fvec3& A = mVertices[0]->mPosition;
558  const fvec3& B = mVertices[1]->mPosition;
559  const fvec3& C = mVertices[2]->mPosition;
560 
561  float base = 0.0f;
562  float height = 0.0f;
563  fvec3 AC = C-A;
564  fvec3 AB = B-A;
565  base = AB.length();
566  if (!base)
567  return 0;
568  AB = AB * (1.0f / base); // normalize
569  fvec3 h = vl::dot(AC,AB) * AB + A;
570  height = (C-h).length();
571  // indeterminate cases
572  VL_CHECK( base == base )
573  VL_CHECK( height == height )
574  return base * height * 0.5f;
575  }
576  //-----------------------------------------------------------------------------
578  {
579  const fvec3& a = mVertices[0]->mPosition;
580  fvec3 b = mVertices[1]->mPosition - a;
581  fvec3 c = mVertices[2]->mPosition - a;
582  mNormal = cross(b,c);
583  mNormal.normalize();
584  }
585  //-----------------------------------------------------------------------------
587  {
588  // becomes a degenerate triangle if "newv" is already here
589  mRemoved = hasVertex(newv);
590  if (mRemoved)
591  {
592  //mVertices[0]->removeIncidentTriangle(this);
593  //mVertices[1]->removeIncidentTriangle(this);
594  //mVertices[2]->removeIncidentTriangle(this);
595  }
596  else
597  {
598  if (mVertices[0] == oldv) mVertices[0] = newv;
599  if (mVertices[1] == oldv) mVertices[1] = newv;
600  if (mVertices[2] == oldv) mVertices[2] = newv;
601  VL_CHECK( !mVertices[0]->mRemoved )
602  VL_CHECK( !mVertices[1]->mRemoved )
603  VL_CHECK( !mVertices[2]->mRemoved )
604  }
605  }
606  //-----------------------------------------------------------------------------
608  {
609  VL_CHECK(!v->mRemoved)
612 #ifndef NDEBUG
613  v->checkConnectivity();
614  // check connectivity consistency
615  for(int ivert=0; ivert<v->adjacentVerticesCount(); ++ivert)
616  {
617  VL_CHECK( v->mAdjacentVerts[ivert]->checkConnectivity() )
618  }
619 #endif
620 
621  v->mRemoved = true;
622 
624  v->mCollapseVertex->mQErr += v->mQErr;
625 
626  for(int itri=0; itri<v->incidentTrianglesCount(); ++itri)
627  {
628  VL_CHECK(!v->mIncidentTriangles[itri]->mRemoved)
629 
630  // - point the triangle to use the new mCollapseVertex instead of "this"
631  // - flags for removal
632  v->mIncidentTriangles[itri]->replaceVertex( v, v->mCollapseVertex );
633 
634  // pass this's adjacent triangles to mCollapseVertex
635  if (!v->mIncidentTriangles[itri]->mRemoved)
636  {
637  // check that it does not have it already, the ones in common have been marked as "removed"
639  v->mCollapseVertex->mIncidentTriangles.push_back( v->mIncidentTriangles[itri] );
640  }
641  }
642 
643  // erase removed triangles from its adjacent vertices (including mCollapseVertex)
644  for(int ivert=0; ivert<v->adjacentVerticesCount(); ++ivert)
645  v->mAdjacentVerts[ivert]->discardRemovedTriangles();
646 
647  // update adjacent vertices of all the vertices adjacent to this (including mCollapseVertex)
648  for(int ivert=0; ivert<v->adjacentVerticesCount(); ++ivert)
649  {
650 #if 1
651  // this is correct and more robust since marks as removed the vertices with 0 triangles
652  v->mAdjacentVerts[ivert]->computeAdjacentVertices();
653 #else
654  ... this is not correct since does not mark as removed the vertices that remain without triangles ...
655  mAdjacentVerts[ivert]->removeAdjacentVertex(this);
656  mAdjacentVerts[ivert]->addAdjacentVertex(mCollapseVertex);
657  mCollapseVertex->addAdjacentVertex(mAdjacentVerts[ivert]);
658 #endif
659  }
660 
661 #ifndef NDEBUG
662  for(int ivert=0; ivert<v->mCollapseVertex->adjacentVerticesCount(); ++ivert)
663  {
665  }
666 
667  // and outside even this vertex is removed.
668  if ( v->mCollapseVertex->removed() )
669  {
672  }
673 #endif
674 
675  // --- now we work on mCollapseVertex ---
676 
677  if ( !quick() )
678  {
679  // update the normals, used to compute anti-folding
680  for(int itri=0; itri<v->mCollapseVertex->incidentTrianglesCount(); ++itri)
681  {
682  VL_CHECK( !v->mCollapseVertex->mIncidentTriangles[itri]->removed() )
683  VL_CHECK( v->mCollapseVertex->mIncidentTriangles[itri]->checkTriangle() )
684  v->mCollapseVertex->mIncidentTriangles[itri]->computeNormal();
685  }
686  }
687 
689 
690  // disconnect this vertex
691  v->mIncidentTriangles.clear();
692  v->mAdjacentVerts.clear();
693  }
694  //-----------------------------------------------------------------------------
695  // compute collapse cost and vertex
697  {
698  VL_CHECK(!v->mRemoved)
699  if(v->mRemoved)
700  return;
701 
702  // choose the edge with minimum cost
703 
704  // intialize with a very high cost
705  v->mCollapseCost = 1.0e+38f;
706  v->mCollapseVertex = NULL;
708  for(int ivert=0; ivert<v->adjacentVerticesCount(); ++ivert)
709  {
710  VL_CHECK(!v->mAdjacentVerts[ivert]->mRemoved)
711 
712  double cost = 0.0;
713  dvec3 solution;
714  if (quick())
715  {
716  QErr qe = v->qerr();
717  qe += v->mAdjacentVerts[ivert]->qerr();
718  // find the best solution
719  solution = (dvec3)v->position();
720  solution += (dvec3)v->mAdjacentVerts[ivert]->position();
721  solution *= 0.5;
722  cost = qe.evaluate( solution );
723  }
724  else
725  {
726  QErr qe = v->qerr();
727  qe += v->mAdjacentVerts[ivert]->qerr();
728  bool analytic_ok = qe.analyticSolution(solution);
729  if ( analytic_ok )
730  {
731  cost = qe.evaluate(solution);
732  VL_CHECK(cost < 1e+38)
733  }
734  else
735  {
736  dvec3 a = (dvec3)v->position();
737  dvec3 b = (dvec3)v->mAdjacentVerts[ivert]->position();
738  dvec3 c = (a+b) * 0.5;
739  double ae = qe.evaluate(a);
740  double be = qe.evaluate(b);
741  double ce = qe.evaluate(c);
742  if (ae < be && ae < ce)
743  {
744  solution = a;
745  cost = ae;
746  }
747  else
748  if (be < ae && be < ce)
749  {
750  solution = b;
751  cost = be;
752  }
753  else
754  {
755  solution = c;
756  cost = ce;
757  }
758  VL_CHECK(cost < 1e+38)
759  }
760 
761  int degenerate_count = 0;
762  for( int itri=0; itri<v->incidentTrianglesCount() && !degenerate_count; ++itri )
763  {
764  // triangle to be removed
765  if ( v->incidentTriangle(itri)->hasVertex(v->mAdjacentVerts[ivert]) )
766  continue;
767 
768  Vertex* edgev[] = { NULL, NULL };
769  if ( v == v->incidentTriangle(itri)->vertex(0) )
770  {
771  edgev[0] = v->incidentTriangle(itri)->vertex(1);
772  edgev[1] = v->incidentTriangle(itri)->vertex(2);
773  }
774  else
775  if ( v == v->incidentTriangle(itri)->vertex(1) )
776  {
777  edgev[0] = v->incidentTriangle(itri)->vertex(0);
778  edgev[1] = v->incidentTriangle(itri)->vertex(2);
779  }
780  else
781  if ( v == v->incidentTriangle(itri)->vertex(2) )
782  {
783  edgev[0] = v->incidentTriangle(itri)->vertex(0);
784  edgev[1] = v->incidentTriangle(itri)->vertex(1);
785  }
786 
787  fvec3 edge = (edgev[1]->position() - edgev[0]->position());
788  fvec3 n = cross( edge, v->incidentTriangle(itri)->normal() );
789  n.normalize();
790  float d1 = dot( v->position() - edgev[0]->position(), n );
791  float d2 = dot( (fvec3)solution - edgev[0]->position(), n );
792 
793  if (d1 * d2 < 0)
794  ++degenerate_count;
795  }
796 
797  // controlla i triangoli intorno a v->mAdjacentVerts[ivert]
798  Vertex* u = v->mAdjacentVerts[ivert];
799  for( int itri=0; itri<u->incidentTrianglesCount() && !degenerate_count; ++itri )
800  {
801  // triangle to be removed
802  if ( u->incidentTriangle(itri)->hasVertex(v) )
803  continue;
804 
805  Vertex* edgev[] = { NULL, NULL };
806  if ( u == u->incidentTriangle(itri)->vertex(0) )
807  {
808  edgev[0] = u->incidentTriangle(itri)->vertex(1);
809  edgev[1] = u->incidentTriangle(itri)->vertex(2);
810  }
811  else
812  if ( u == u->incidentTriangle(itri)->vertex(1) )
813  {
814  edgev[0] = u->incidentTriangle(itri)->vertex(0);
815  edgev[1] = u->incidentTriangle(itri)->vertex(2);
816  }
817  else
818  if ( u == u->incidentTriangle(itri)->vertex(2) )
819  {
820  edgev[0] = u->incidentTriangle(itri)->vertex(0);
821  edgev[1] = u->incidentTriangle(itri)->vertex(1);
822  }
823 
824  fvec3 edge = (edgev[1]->position() - edgev[0]->position());
825  fvec3 n = cross( edge, u->incidentTriangle(itri)->normal() );
826  n.normalize();
827  float d1 = dot( u->position() - edgev[0]->position(), n );
828  float d2 = dot( (fvec3)solution - edgev[0]->position(), n );
829 
830  if (d1 * d2 < 0)
831  ++degenerate_count;
832  }
833 
834  // non acceptable solution, assign very high cost
835  if (degenerate_count)
836  cost = 1.0e+37f;
837  }
838 
839  // to correctly simplify planar and cylindrical regions
840  cost += ((dvec3)v->position() - solution).length() * 1.0e-12;
841 
842  // check indeterminate case
843  VL_CHECK( cost == cost )
844  if ( cost < v->mCollapseCost )
845  {
846  v->mCollapseCost = (float)cost;
847  v->mCollapseVertex = v->mAdjacentVerts[ivert];
848  v->mCollapsePosition = (fvec3)solution;
849  }
850  }
851 
853  }
854  //-----------------------------------------------------------------------------
855 }
856 
857 #endif
int incidentTrianglesCount() const
adjacent triangles
int simplifiedIndex() const
Internally used to regenerated the index buffer.
const Vector3 & normalize(T_Scalar *len=NULL)
Definition: Vector3.hpp:228
Vector3< float > fvec3
A 3 components vector with float precision.
Definition: Vector3.hpp:253
bool mAlreadyProcessed
internally used
float mCollapseCost
cost of the collapse
fvec3 mCollapsePosition
the collapse position
std::vector< int > mProtectedVerts
QErr operator+(const QErr &other)
const T_Scalar & z() const
Definition: Vector3.hpp:92
std::vector< Vertex * > mSimplifiedVertices
A Triangle as defined by PolygonSimplifier.
void setRemoveDoubles(bool remove_doubles)
Vertex * mCollapseVertex
vertex to which collapse
bool removed() const
has the vertex been removed
T_Scalar getInverse(Matrix3 &dest) const
Definition: Matrix3.hpp:617
const fvec3 & collapsePosition() const
collapse position
int mRemoveOrder
when the vertex has collapsed
std::vector< ref< Geometry > > & output()
void removeIncidentTriangle(const Triangle *)
const Vertex * vertex(int index) const
vertices of the triangle
fvec3 cross(const fvec3 &v1, const fvec3 &v2)
Definition: Vector3.hpp:278
const Geometry * input() const
std::vector< Vertex *> mAdjacentVerts
ajacent vertices
const QErr & qerr() const
Accumulated vertex error.
Vertex * collapseVertex() const
vertex to which collapse
bool isProtected() const
is the vertex protected?
#define VL_INSTRUMENT_CLASS(ClassName, BaseClass)
Definition: TypeInfo.hpp:122
Triangle * simplifiedTriangles(int index) const
bool analyticSolution(dvec3 &v) const
The Geometry class is a Renderable that implements a polygonal mesh made of polygons, lines and points.
Definition: Geometry.hpp:66
void setVerbose(bool verbose)
Visualization Library main namespace.
int mOriginalIndex
original index of this vertex
float dot(float a, float b)
Definition: glsl_math.hpp:1111
The Matrix3 class is a template class that implements a generic 3x3 matrix, see also vl::dmat3...
Definition: Matrix3.hpp:48
bool mProtected
is the vertex protected?
const std::vector< ref< Geometry > > & output() const
bool removed() const
ara of the triangle
std::vector< u32 > & targets()
The Vector3 class is a template class that implements a generic 3 components vector, see also vl::fvec3, vl::dvec3, vl::uvec3, vl::ivec3, vl::svec3, vl::usvec3, vl::bvec3, vl::ubvec3.
Definition: Vector3.hpp:44
const std::vector< u32 > & targets() const
bool mRemoved
has the vertex been removed
The base class for all the reference counted objects.
Definition: Object.hpp:158
const fvec3 & normal() const
normal of the triangle
Matrix3< double > dmat3
A 3x3 matrix using double precision.
Definition: Matrix3.hpp:656
Implements the OpenGL Shading Language convenience functions for scalar and vector operations...
Vertex * simplifiedVertices(int index) const
The PolygonSimplifier class reduces the amount of polygons present in a Geometry using a quadric erro...
int originalIndex() const
original index of this vertex
void replaceVertex(Vertex *oldv, Vertex *newv)
Vector3< double > dvec3
A 3 components vector with double precision.
Definition: Vector3.hpp:255
std::vector< Triangle *> mIncidentTriangles
adjacent triangles
T_Scalar length() const
Definition: Vector3.hpp:225
Triangle * incidentTriangle(int index) const
const T_Scalar & y() const
Definition: Vector3.hpp:91
A Vertex as defined by PolygonSimplifier.
float collapseCost() const
cost of the collapse
void setQErr(const QErr &qerr)
void computeCollapseInfo(Vertex *v)
int adjacentVerticesCount() const
ajacent vertices
#define NULL
Definition: OpenGLDefs.hpp:81
int simplifiedTrianglesCount() const
fvec3 computePotentialNormal(const Vertex *oldv, const Vertex *newv) const
std::vector< u32 > mTargets
const QErr & operator+=(const QErr &other)
const fvec3 & position() const
the position
int removeOrder() const
when the vertex has collapsed
float computePotentialArea(const Vertex *oldv, const Vertex *newv) const
std::vector< Triangle * > mSimplifiedTriangles
The quadric error metric as defined by PolygonSimplifier.
std::vector< ref< Geometry > > mOutput
int mSimplifiedIndex
only used during index buffer regeneration
const T_Scalar & x() const
Definition: Vector3.hpp:90
bool isAdjacentVertex(Vertex *) const
void setCollapsePosition(const fvec3 &pos)
The ref<> class is used to reference-count an Object.
Definition: Object.hpp:55
bool isIncidentTriangle(Triangle *) const
bool mRemoved
ara of the triangle
T length(T v)
Definition: glsl_math.hpp:1084
void setProtectedVertices(const std::vector< int > &protected_verts)
bool hasVertex(const Vertex *v) const
QErr(const dvec3 &n, double d, double w=1.0)
#define VL_CHECK(expr)
Definition: checks.hpp:73
void addQErr(const QErr &qerr)
double evaluate(const dvec3 &v) const
void setIntput(Geometry *geom)
bool alreadyProcessed() const
Internally used.
Vertex * adjacentVertex(int index) const
fvec3 mNormal
normal of the triangle