Visualization Library v1.0.3A lightweight C++ OpenGL middleware for 2D/3D graphics |
[Download] [Tutorials] [All Classes] [Grouped Classes] |
00001 /**************************************************************************************/ 00002 /* */ 00003 /* Visualization Library */ 00004 /* http://visualizationlibrary.org */ 00005 /* */ 00006 /* Copyright (c) 2005-2010, Michele Bosi */ 00007 /* All rights reserved. */ 00008 /* */ 00009 /* Redistribution and use in source and binary forms, with or without modification, */ 00010 /* are permitted provided that the following conditions are met: */ 00011 /* */ 00012 /* - Redistributions of source code must retain the above copyright notice, this */ 00013 /* list of conditions and the following disclaimer. */ 00014 /* */ 00015 /* - Redistributions in binary form must reproduce the above copyright notice, this */ 00016 /* list of conditions and the following disclaimer in the documentation and/or */ 00017 /* other materials provided with the distribution. */ 00018 /* */ 00019 /* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND */ 00020 /* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED */ 00021 /* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE */ 00022 /* DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR */ 00023 /* ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES */ 00024 /* (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; */ 00025 /* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON */ 00026 /* ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT */ 00027 /* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS */ 00028 /* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ 00029 /* */ 00030 /**************************************************************************************/ 00031 00032 #ifndef PolygonSimplifier_INCLUDE_ONCE 00033 #define PolygonSimplifier_INCLUDE_ONCE 00034 00035 #include <vlGraphics/link_config.hpp> 00036 #include <vlCore/Object.hpp> 00037 #include <vlCore/Vector3.hpp> 00038 #include <vlCore/glsl_math.hpp> 00039 #include <vector> 00040 #include <algorithm> 00041 00042 namespace vl 00043 { 00044 class Geometry; 00045 //----------------------------------------------------------------------------- 00046 // PolygonSimplifier 00047 //----------------------------------------------------------------------------- 00052 class VLGRAPHICS_EXPORT PolygonSimplifier: public Object 00053 { 00054 VL_INSTRUMENT_CLASS(vl::PolygonSimplifier, Object) 00055 00056 public: 00057 class Vertex; 00058 //----------------------------------------------------------------------------- 00059 // QErr 00060 //----------------------------------------------------------------------------- 00062 class QErr 00063 { 00064 public: 00065 QErr() 00066 { 00067 a2 = 0.0; 00068 ab = 0.0; 00069 ac = 0.0; 00070 ad = 0.0; 00071 b2 = 0.0; 00072 bc = 0.0; 00073 bd = 0.0; 00074 c2 = 0.0; 00075 cd = 0.0; 00076 d2 = 0.0; 00077 } 00078 00079 QErr(const dvec3& n, double d, double w = 1.0) 00080 { 00081 a2 = w * n.x() * n.x(); 00082 ab = w * n.x() * n.y(); 00083 ac = w * n.x() * n.z(); 00084 ad = w * n.x() * d; 00085 b2 = w * n.y() * n.y(); 00086 bc = w * n.y() * n.z(); 00087 bd = w * n.y() * d; 00088 c2 = w * n.z() * n.z(); 00089 cd = w * n.z() * d; 00090 d2 = w * d*d; 00091 00092 // indeterminate cases 00093 VL_CHECK( d2 == d2 ) 00094 } 00095 00096 dmat3 matrix() const 00097 { 00098 return dmat3( 00099 a2, ab, ac, 00100 ab, b2, bc, 00101 ac, bc, c2 ); 00102 } 00103 00104 dvec3 vector() const 00105 { 00106 return dvec3( ad, bd, cd ); 00107 } 00108 00109 double offset() const 00110 { 00111 return d2; 00112 } 00113 00114 double evaluate(const dvec3& v) const 00115 { 00116 return v.x()*v.x()*a2 + 2*v.x()*v.y()*ab + 2*v.x()*v.z()*ac + 2*v.x()*ad 00117 + v.y()*v.y()*b2 + 2*v.y()*v.z()*bc + 2*v.y()*bd 00118 + v.z()*v.z()*c2 + 2*v.z()*cd 00119 + d2; 00120 } 00121 00122 bool analyticSolution(dvec3& v) const 00123 { 00124 #if 0 00125 dmat3 Ainv; 00126 double det = matrix().getInverse(Ainv); 00127 if (!det) 00128 return false; 00129 v = -(Ainv*vector()); 00130 return true; 00131 #else 00132 double A = c2*b2-bc*bc; 00133 double B = bc*ac-c2*ab; 00134 double C = bc*ab-b2*ac; 00135 double det = a2*(A)+ab*(B)+ac*(C); 00136 if (fabs(det) < 0.0000001) 00137 return false; 00138 else 00139 { 00140 double inv_det = 1.0 / det; 00141 dmat3 Ainv( A*inv_det, B*inv_det, C*inv_det, 00142 (ac*bc-c2*ab)*inv_det, (c2*a2-ac*ac)*inv_det, (ab*ac-bc*a2)*inv_det, 00143 (bc*ab-ac*b2)*inv_det, (ac*ab-bc*a2)*inv_det, (b2*a2-ab*ab)*inv_det ); 00144 v = Ainv * dvec3( -ad, -bd, -cd ); 00145 return true; 00146 } 00147 #endif 00148 } 00149 00150 QErr operator+(const QErr& other) 00151 { 00152 QErr q = *this; 00153 q.a2 += other.a2; 00154 q.ab += other.ab; 00155 q.ac += other.ac; 00156 q.ad += other.ad; 00157 q.b2 += other.b2; 00158 q.bc += other.bc; 00159 q.bd += other.bd; 00160 q.c2 += other.c2; 00161 q.cd += other.cd; 00162 q.d2 += other.d2; 00163 return q; 00164 } 00165 00166 const QErr& operator+=(const QErr& other) 00167 { 00168 a2 += other.a2; 00169 ab += other.ab; 00170 ac += other.ac; 00171 ad += other.ad; 00172 b2 += other.b2; 00173 bc += other.bc; 00174 bd += other.bd; 00175 c2 += other.c2; 00176 cd += other.cd; 00177 d2 += other.d2; 00178 return *this; 00179 } 00180 00181 protected: 00182 // coefficients 00183 double a2, ab, ac, ad; 00184 double b2, bc, bd; 00185 double c2, cd; 00186 double d2; 00187 }; 00188 //----------------------------------------------------------------------------- 00189 // Triangle 00190 //----------------------------------------------------------------------------- 00192 class Triangle 00193 { 00194 friend class PolygonSimplifier; 00195 friend class Vertex; 00196 public: 00197 Triangle(): mRemoved(false) 00198 { 00199 mVertices[0] = NULL; 00200 mVertices[1] = NULL; 00201 mVertices[2] = NULL; 00202 } 00203 00204 inline void replaceVertex( Vertex* oldv, Vertex* newv ); 00205 inline void computeNormal(); 00206 inline float computeArea() const; 00207 inline float computePotentialArea(const Vertex* oldv, const Vertex* newv) const; 00208 inline fvec3 computePotentialNormal(const Vertex* oldv, const Vertex* newv) const; 00209 inline bool hasVertex(const Vertex*v) const; 00210 inline bool checkTriangle() const; 00211 // inline float computeDistance(const fvec3&) const; 00212 inline QErr computeQErr() const; 00213 00215 const Vertex* vertex(int index) const { return mVertices[index]; } 00216 Vertex* vertex(int index) { return mVertices[index]; } 00218 const fvec3& normal() const { return mNormal; } 00220 // float area() const { return mArea; } 00222 bool removed() const { return mRemoved; } 00224 00225 protected: 00227 Vertex* mVertices[3]; 00229 fvec3 mNormal; 00231 // float mArea; 00233 bool mRemoved; 00234 }; 00235 //----------------------------------------------------------------------------- 00236 // Vertex 00237 //----------------------------------------------------------------------------- 00239 class Vertex 00240 { 00241 friend class Triangle; 00242 friend class PolygonSimplifier; 00243 public: 00244 Vertex(): mCollapseCost(0.0f), mOriginalIndex(-1) , mSimplifiedIndex(-1), mRemoveOrder(-1), 00245 mRemoved(false), mProtected(false), mAlreadyProcessed(false) 00246 { 00247 } 00248 00249 inline void addAdjacentVertex(Vertex* v); 00250 inline void removeAdjacentVertex(Vertex* v); 00251 inline void computeAdjacentVertices(); 00252 inline bool checkConnectivity(); 00253 inline bool isAdjacentVertex(Vertex*) const; 00254 inline bool isIncidentTriangle(Triangle*) const; 00255 inline void discardRemovedTriangles(); 00256 inline void removeIncidentTriangle(const Triangle*); 00257 inline bool checkTriangles() const; 00258 inline void computeEdgePenalty(); 00259 00261 const fvec3& position() const { return mPosition; } 00263 int adjacentVerticesCount() const { return (int)mAdjacentVerts.size(); } 00264 Vertex* adjacentVertex(int index) const { return mAdjacentVerts[index]; } 00266 int incidentTrianglesCount() const { return (int)mIncidentTriangles.size(); } 00267 Triangle* incidentTriangle(int index) const { return mIncidentTriangles[index]; } 00269 Vertex* collapseVertex() const { return mCollapseVertex; } 00271 float collapseCost() const { return mCollapseCost; } 00273 const fvec3& collapsePosition() const { return mCollapsePosition; } 00274 void setCollapsePosition(const fvec3& pos) { mCollapsePosition = pos; } 00276 int removeOrder() const { return mRemoveOrder; } 00278 bool removed() const { return mRemoved; } 00280 bool isProtected() const { return mProtected; } 00282 int originalIndex() const { return mOriginalIndex; } 00284 int simplifiedIndex() const { return mSimplifiedIndex; } 00286 bool alreadyProcessed() const { return mAlreadyProcessed; } 00288 const QErr& qerr() const { return mQErr; } 00289 void setQErr(const QErr& qerr) { mQErr = qerr; } 00290 void addQErr(const QErr& qerr) { mQErr += qerr; } 00291 00292 protected: 00293 QErr mQErr; 00295 fvec3 mPosition; 00297 std::vector< Vertex* > mAdjacentVerts; 00299 std::vector< Triangle* > mIncidentTriangles; 00301 Vertex* mCollapseVertex; 00303 float mCollapseCost; 00305 fvec3 mCollapsePosition; 00307 int mOriginalIndex; 00309 int mSimplifiedIndex; 00311 int mRemoveOrder; 00313 bool mRemoved; 00315 bool mProtected; 00317 bool mAlreadyProcessed; 00318 }; 00319 00320 public: 00321 PolygonSimplifier(): mRemoveDoubles(false), mVerbose(true), mQuick(true) {} 00322 00323 void simplify(); 00324 void simplify(const std::vector<fvec3>& in_verts, const std::vector<int>& in_tris); 00325 00326 void setIntput(Geometry* geom) { mInput = geom; } 00327 Geometry* input() { return mInput.get(); } 00328 const Geometry* input() const { return mInput.get(); } 00329 00330 std::vector< u32 >& targets() { return mTargets; } 00331 const std::vector< u32 >& targets() const { return mTargets; } 00332 00333 std::vector< ref<Geometry> >& output() { return mOutput; } 00334 const std::vector< ref<Geometry> >& output() const { return mOutput; } 00335 00336 void setProtectedVertices(const std::vector<int>& protected_verts) { mProtectedVerts = protected_verts; } 00337 00338 int simplifiedVerticesCount() const { return (int)mSimplifiedVertices.size(); } 00339 Vertex* simplifiedVertices(int index) const { return mSimplifiedVertices[index]; } 00340 00341 int simplifiedTrianglesCount() const { return (int)mSimplifiedTriangles.size(); } 00342 Triangle* simplifiedTriangles(int index) const { return mSimplifiedTriangles[index]; } 00343 00344 void clearTrianglesAndVertices(); 00345 00346 bool removeDoubles() const { return mRemoveDoubles; } 00347 void setRemoveDoubles(bool remove_doubles) { mRemoveDoubles = remove_doubles; } 00348 00349 bool verbose() const { return mVerbose; } 00350 void setVerbose(bool verbose) { mVerbose = verbose; } 00351 00352 bool quick() const { return mQuick; } 00353 void setQuick(bool quick) { mQuick = quick; } 00354 00355 protected: 00356 void outputSimplifiedGeometry(); 00357 inline void collapse(Vertex* v); 00358 inline void computeCollapseInfo(Vertex* v); 00359 00360 protected: 00361 ref<Geometry> mInput; 00362 std::vector< ref<Geometry> > mOutput; 00363 std::vector< u32 > mTargets; 00364 std::vector<Vertex*> mSimplifiedVertices; 00365 std::vector<Triangle*> mSimplifiedTriangles; 00366 std::vector<int> mProtectedVerts; 00367 bool mRemoveDoubles; 00368 bool mVerbose; 00369 bool mQuick; 00370 00371 private: 00372 std::vector<Triangle> mTriangleLump; 00373 std::vector<Vertex> mVertexLump; 00374 }; 00375 //----------------------------------------------------------------------------- 00376 // Vertex 00377 //----------------------------------------------------------------------------- 00378 inline void PolygonSimplifier::Vertex::addAdjacentVertex(Vertex* v) 00379 { 00380 if( v != this ) 00381 { 00382 for(int i=0; i<adjacentVerticesCount(); ++i) 00383 if (mAdjacentVerts[i] == v) 00384 return; 00385 mAdjacentVerts.push_back(v); 00386 } 00387 } 00388 //----------------------------------------------------------------------------- 00389 inline void PolygonSimplifier::Vertex::removeAdjacentVertex(Vertex* v) 00390 { 00391 VL_CHECK( v != this ) 00392 VL_CHECK( std::find(mAdjacentVerts.begin(), mAdjacentVerts.end(), v) != mAdjacentVerts.end() ) 00393 for(int i=0; i<adjacentVerticesCount(); ++i) 00394 if (mAdjacentVerts[i] == v) 00395 { 00396 mAdjacentVerts.erase(mAdjacentVerts.begin() + i); 00397 return; 00398 } 00399 } 00400 //----------------------------------------------------------------------------- 00401 inline void PolygonSimplifier::Vertex::computeAdjacentVertices() 00402 { 00403 mAdjacentVerts.clear(); 00404 for(int itri=0; itri<incidentTrianglesCount(); ++itri) 00405 { 00406 VL_CHECK(!mIncidentTriangles[itri]->mRemoved) 00407 addAdjacentVertex( mIncidentTriangles[itri]->mVertices[0] ); 00408 addAdjacentVertex( mIncidentTriangles[itri]->mVertices[1] ); 00409 addAdjacentVertex( mIncidentTriangles[itri]->mVertices[2] ); 00410 } 00411 mRemoved = mAdjacentVerts.empty(); 00412 } 00413 //----------------------------------------------------------------------------- 00414 inline bool PolygonSimplifier::Vertex::checkTriangles() const 00415 { 00416 for(int itri=incidentTrianglesCount(); itri--; ) 00417 if ( !incidentTriangle(itri)->checkTriangle() ) 00418 return false; 00419 return true; 00420 } 00421 //----------------------------------------------------------------------------- 00422 inline void PolygonSimplifier::Vertex::computeEdgePenalty() 00423 { 00424 for(int ivert=0; ivert<adjacentVerticesCount(); ++ivert) 00425 { 00426 int edge_count = 0; 00427 int border_tri = -1; 00428 for(int itri=0; itri<incidentTrianglesCount() && edge_count<=1; ++itri) 00429 { 00430 if ( incidentTriangle(itri)->hasVertex( adjacentVertex(ivert) ) ) 00431 { 00432 border_tri = itri; 00433 ++edge_count; 00434 } 00435 } 00436 if ( edge_count == 1 ) 00437 { 00438 fvec3 edge = position() - adjacentVertex(ivert)->position(); 00439 dvec3 n = (dvec3)cross(incidentTriangle(border_tri)->normal(), edge ); 00440 n.normalize(); 00441 double d = -dot(n,(dvec3)position()); 00442 mQErr += QErr( n, d, dot(edge, edge) * 1.0 ); 00443 } 00444 } 00445 } 00446 inline void PolygonSimplifier::Vertex::removeIncidentTriangle(const Triangle* tri) 00447 { 00448 for(int itri=incidentTrianglesCount(); itri--; ) 00449 { 00450 if (mIncidentTriangles[itri] == tri) 00451 { 00452 mIncidentTriangles.erase( mIncidentTriangles.begin() + itri ); 00453 break; 00454 } 00455 } 00456 } 00457 //----------------------------------------------------------------------------- 00458 inline void PolygonSimplifier::Vertex::discardRemovedTriangles() 00459 { 00460 for(int itri=incidentTrianglesCount(); itri--; ) 00461 { 00462 if (mIncidentTriangles[itri]->mRemoved) 00463 mIncidentTriangles.erase( mIncidentTriangles.begin() + itri ); 00464 } 00465 } 00466 //----------------------------------------------------------------------------- 00467 inline bool PolygonSimplifier::Vertex::isAdjacentVertex(Vertex* v) const 00468 { 00469 for(int i=0; i<adjacentVerticesCount(); ++i) 00470 if ( adjacentVertex(i) == v ) 00471 return true; 00472 return false; 00473 } 00474 //----------------------------------------------------------------------------- 00475 inline bool PolygonSimplifier::Vertex::isIncidentTriangle(Triangle* t) const 00476 { 00477 for(int i=0; i<incidentTrianglesCount(); ++i) 00478 if ( incidentTriangle(i) == t ) 00479 return true; 00480 return false; 00481 } 00482 //----------------------------------------------------------------------------- 00483 inline bool PolygonSimplifier::Vertex::checkConnectivity() 00484 { 00485 VL_CHECK( mCollapseVertex ) 00486 VL_CHECK( !mCollapseVertex->removed() ) 00487 // check connectivity consistency 00488 for(int ivert=0; ivert<adjacentVerticesCount(); ++ivert) 00489 { 00490 Vertex* adj = mAdjacentVerts[ivert]; 00491 if ( adj->removed() ) 00492 return false; 00493 if( std::find(adj->mAdjacentVerts.begin(), adj->mAdjacentVerts.end(), this) == adj->mAdjacentVerts.end() ) 00494 return false; 00495 } 00496 return true; 00497 } 00498 //----------------------------------------------------------------------------- 00499 // Triangle 00500 //----------------------------------------------------------------------------- 00501 inline PolygonSimplifier::QErr PolygonSimplifier::Triangle::computeQErr() const 00502 { 00503 dvec3 n = (dvec3)normal(); 00504 double d = -dot((dvec3)vertex(0)->position(), n); 00505 QErr qerr(n, d, computeArea() * (1.0 / 3.0) ); 00506 return qerr; 00507 } 00508 //----------------------------------------------------------------------------- 00509 inline fvec3 PolygonSimplifier::Triangle::computePotentialNormal(const Vertex* oldv, const Vertex* newv) const 00510 { 00511 fvec3 a = (mVertices[0]->mPosition == oldv->mPosition ? newv->mPosition : mVertices[0]->mPosition); 00512 fvec3 b = (mVertices[1]->mPosition == oldv->mPosition ? newv->mPosition : mVertices[1]->mPosition) - a; 00513 fvec3 c = (mVertices[2]->mPosition == oldv->mPosition ? newv->mPosition : mVertices[2]->mPosition) - a; 00514 00515 fvec3 n = cross(b,c); 00516 n.normalize(); 00517 return n; 00518 } 00519 //----------------------------------------------------------------------------- 00520 inline bool PolygonSimplifier::Triangle::checkTriangle() const 00521 { 00522 bool ok = true; 00523 ok &= !mVertices[0]->removed(); VL_CHECK(ok) 00524 ok &= !mVertices[1]->removed(); VL_CHECK(ok) 00525 ok &= !mVertices[2]->removed(); VL_CHECK(ok) 00526 ok &= mVertices[0] != mVertices[1]; VL_CHECK(ok) 00527 ok &= mVertices[0] != mVertices[2]; VL_CHECK(ok) 00528 ok &= mVertices[1] != mVertices[2]; VL_CHECK(ok) 00529 return ok; 00530 } 00531 //----------------------------------------------------------------------------- 00532 inline bool PolygonSimplifier::Triangle::hasVertex(const Vertex*v) const 00533 { 00534 return mVertices[0] == v || mVertices[1] == v || mVertices[2] == v; 00535 } 00536 //----------------------------------------------------------------------------- 00537 inline float PolygonSimplifier::Triangle::computePotentialArea(const Vertex* oldv, const Vertex* newv) const 00538 { 00539 fvec3 A = (mVertices[0]->mPosition == oldv->mPosition ? newv->mPosition : mVertices[0]->mPosition); 00540 fvec3 B = (mVertices[1]->mPosition == oldv->mPosition ? newv->mPosition : mVertices[1]->mPosition) - A; 00541 fvec3 C = (mVertices[2]->mPosition == oldv->mPosition ? newv->mPosition : mVertices[2]->mPosition) - A; 00542 00543 float base = 0.0f; 00544 float height = 0.0f; 00545 fvec3 AC = C-A; 00546 fvec3 AB = B-A; 00547 base = AB.length(); 00548 AB = AB * (1.0f / base); // normalize 00549 fvec3 h = vl::dot(AC,AB) * AB + A; 00550 height = (C-h).length(); 00551 00552 return base * height * 0.5f; 00553 } 00554 //----------------------------------------------------------------------------- 00555 inline float PolygonSimplifier::Triangle::computeArea() const 00556 { 00557 const fvec3& A = mVertices[0]->mPosition; 00558 const fvec3& B = mVertices[1]->mPosition; 00559 const fvec3& C = mVertices[2]->mPosition; 00560 00561 float base = 0.0f; 00562 float height = 0.0f; 00563 fvec3 AC = C-A; 00564 fvec3 AB = B-A; 00565 base = AB.length(); 00566 if (!base) 00567 return 0; 00568 AB = AB * (1.0f / base); // normalize 00569 fvec3 h = vl::dot(AC,AB) * AB + A; 00570 height = (C-h).length(); 00571 // indeterminate cases 00572 VL_CHECK( base == base ) 00573 VL_CHECK( height == height ) 00574 return base * height * 0.5f; 00575 } 00576 //----------------------------------------------------------------------------- 00577 inline void PolygonSimplifier::Triangle::computeNormal() 00578 { 00579 const fvec3& a = mVertices[0]->mPosition; 00580 fvec3 b = mVertices[1]->mPosition - a; 00581 fvec3 c = mVertices[2]->mPosition - a; 00582 mNormal = cross(b,c); 00583 mNormal.normalize(); 00584 } 00585 //----------------------------------------------------------------------------- 00586 inline void PolygonSimplifier::Triangle::replaceVertex( Vertex* oldv, Vertex* newv ) 00587 { 00588 // becomes a degenerate triangle if "newv" is already here 00589 mRemoved = hasVertex(newv); 00590 if (mRemoved) 00591 { 00592 //mVertices[0]->removeIncidentTriangle(this); 00593 //mVertices[1]->removeIncidentTriangle(this); 00594 //mVertices[2]->removeIncidentTriangle(this); 00595 } 00596 else 00597 { 00598 if (mVertices[0] == oldv) mVertices[0] = newv; 00599 if (mVertices[1] == oldv) mVertices[1] = newv; 00600 if (mVertices[2] == oldv) mVertices[2] = newv; 00601 VL_CHECK( !mVertices[0]->mRemoved ) 00602 VL_CHECK( !mVertices[1]->mRemoved ) 00603 VL_CHECK( !mVertices[2]->mRemoved ) 00604 } 00605 } 00606 //----------------------------------------------------------------------------- 00607 inline void PolygonSimplifier::collapse(Vertex* v) 00608 { 00609 VL_CHECK(!v->mRemoved) 00610 VL_CHECK(v->mCollapseVertex) 00611 VL_CHECK( !v->mCollapseVertex->mRemoved ) 00612 #ifndef NDEBUG 00613 v->checkConnectivity(); 00614 // check connectivity consistency 00615 for(int ivert=0; ivert<v->adjacentVerticesCount(); ++ivert) 00616 { 00617 VL_CHECK( v->mAdjacentVerts[ivert]->checkConnectivity() ) 00618 } 00619 #endif 00620 00621 v->mRemoved = true; 00622 00623 v->mCollapseVertex->mPosition = v->mCollapsePosition; 00624 v->mCollapseVertex->mQErr += v->mQErr; 00625 00626 for(int itri=0; itri<v->incidentTrianglesCount(); ++itri) 00627 { 00628 VL_CHECK(!v->mIncidentTriangles[itri]->mRemoved) 00629 00630 // - point the triangle to use the new mCollapseVertex instead of "this" 00631 // - flags for removal 00632 v->mIncidentTriangles[itri]->replaceVertex( v, v->mCollapseVertex ); 00633 00634 // pass this's adjacent triangles to mCollapseVertex 00635 if (!v->mIncidentTriangles[itri]->mRemoved) 00636 { 00637 // check that it does not have it already, the ones in common have been marked as "removed" 00638 VL_CHECK( !v->mCollapseVertex->isIncidentTriangle( v->mIncidentTriangles[itri] ) ) 00639 v->mCollapseVertex->mIncidentTriangles.push_back( v->mIncidentTriangles[itri] ); 00640 } 00641 } 00642 00643 // erase removed triangles from its adjacent vertices (including mCollapseVertex) 00644 for(int ivert=0; ivert<v->adjacentVerticesCount(); ++ivert) 00645 v->mAdjacentVerts[ivert]->discardRemovedTriangles(); 00646 00647 // update adjacent vertices of all the vertices adjacent to this (including mCollapseVertex) 00648 for(int ivert=0; ivert<v->adjacentVerticesCount(); ++ivert) 00649 { 00650 #if 1 00651 // this is correct and more robust since marks as removed the vertices with 0 triangles 00652 v->mAdjacentVerts[ivert]->computeAdjacentVertices(); 00653 #else 00654 ... this is not correct since does not mark as removed the vertices that remain without triangles ... 00655 mAdjacentVerts[ivert]->removeAdjacentVertex(this); 00656 mAdjacentVerts[ivert]->addAdjacentVertex(mCollapseVertex); 00657 mCollapseVertex->addAdjacentVertex(mAdjacentVerts[ivert]); 00658 #endif 00659 } 00660 00661 #ifndef NDEBUG 00662 for(int ivert=0; ivert<v->mCollapseVertex->adjacentVerticesCount(); ++ivert) 00663 { 00664 VL_CHECK( v->mCollapseVertex->adjacentVertex(ivert)->checkTriangles() ) 00665 } 00666 00667 // and outside even this vertex is removed. 00668 if ( v->mCollapseVertex->removed() ) 00669 { 00670 VL_CHECK( v->mCollapseVertex->mIncidentTriangles.empty() ) 00671 VL_CHECK( v->mCollapseVertex->mAdjacentVerts.empty() ) 00672 } 00673 #endif 00674 00675 // --- now we work on mCollapseVertex --- 00676 00677 if ( !quick() ) 00678 { 00679 // update the normals, used to compute anti-folding 00680 for(int itri=0; itri<v->mCollapseVertex->incidentTrianglesCount(); ++itri) 00681 { 00682 VL_CHECK( !v->mCollapseVertex->mIncidentTriangles[itri]->removed() ) 00683 VL_CHECK( v->mCollapseVertex->mIncidentTriangles[itri]->checkTriangle() ) 00684 v->mCollapseVertex->mIncidentTriangles[itri]->computeNormal(); 00685 } 00686 } 00687 00688 VL_CHECK( !v->mCollapseVertex->isAdjacentVertex(v) ) 00689 00690 // disconnect this vertex 00691 v->mIncidentTriangles.clear(); 00692 v->mAdjacentVerts.clear(); 00693 } 00694 //----------------------------------------------------------------------------- 00695 // compute collapse cost and vertex 00696 inline void PolygonSimplifier::computeCollapseInfo(Vertex* v) 00697 { 00698 VL_CHECK(!v->mRemoved) 00699 if(v->mRemoved) 00700 return; 00701 00702 // choose the edge with minimum cost 00703 00704 // intialize with a very high cost 00705 v->mCollapseCost = 1.0e+38f; 00706 v->mCollapseVertex = NULL; 00707 VL_CHECK( v->adjacentVerticesCount() ) 00708 for(int ivert=0; ivert<v->adjacentVerticesCount(); ++ivert) 00709 { 00710 VL_CHECK(!v->mAdjacentVerts[ivert]->mRemoved) 00711 00712 double cost = 0.0; 00713 dvec3 solution; 00714 if (quick()) 00715 { 00716 QErr qe = v->qerr(); 00717 qe += v->mAdjacentVerts[ivert]->qerr(); 00718 // find the best solution 00719 solution = (dvec3)v->position(); 00720 solution += (dvec3)v->mAdjacentVerts[ivert]->position(); 00721 solution *= 0.5; 00722 cost = qe.evaluate( solution ); 00723 } 00724 else 00725 { 00726 QErr qe = v->qerr(); 00727 qe += v->mAdjacentVerts[ivert]->qerr(); 00728 bool analytic_ok = qe.analyticSolution(solution); 00729 if ( analytic_ok ) 00730 { 00731 cost = qe.evaluate(solution); 00732 VL_CHECK(cost < 1e+38) 00733 } 00734 else 00735 { 00736 dvec3 a = (dvec3)v->position(); 00737 dvec3 b = (dvec3)v->mAdjacentVerts[ivert]->position(); 00738 dvec3 c = (a+b) * 0.5; 00739 double ae = qe.evaluate(a); 00740 double be = qe.evaluate(b); 00741 double ce = qe.evaluate(c); 00742 if (ae < be && ae < ce) 00743 { 00744 solution = a; 00745 cost = ae; 00746 } 00747 else 00748 if (be < ae && be < ce) 00749 { 00750 solution = b; 00751 cost = be; 00752 } 00753 else 00754 { 00755 solution = c; 00756 cost = ce; 00757 } 00758 VL_CHECK(cost < 1e+38) 00759 } 00760 00761 int degenerate_count = 0; 00762 for( int itri=0; itri<v->incidentTrianglesCount() && !degenerate_count; ++itri ) 00763 { 00764 // triangle to be removed 00765 if ( v->incidentTriangle(itri)->hasVertex(v->mAdjacentVerts[ivert]) ) 00766 continue; 00767 00768 Vertex* edgev[] = { NULL, NULL }; 00769 if ( v == v->incidentTriangle(itri)->vertex(0) ) 00770 { 00771 edgev[0] = v->incidentTriangle(itri)->vertex(1); 00772 edgev[1] = v->incidentTriangle(itri)->vertex(2); 00773 } 00774 else 00775 if ( v == v->incidentTriangle(itri)->vertex(1) ) 00776 { 00777 edgev[0] = v->incidentTriangle(itri)->vertex(0); 00778 edgev[1] = v->incidentTriangle(itri)->vertex(2); 00779 } 00780 else 00781 if ( v == v->incidentTriangle(itri)->vertex(2) ) 00782 { 00783 edgev[0] = v->incidentTriangle(itri)->vertex(0); 00784 edgev[1] = v->incidentTriangle(itri)->vertex(1); 00785 } 00786 00787 fvec3 edge = (edgev[1]->position() - edgev[0]->position()); 00788 fvec3 n = cross( edge, v->incidentTriangle(itri)->normal() ); 00789 n.normalize(); 00790 float d1 = dot( v->position() - edgev[0]->position(), n ); 00791 float d2 = dot( (fvec3)solution - edgev[0]->position(), n ); 00792 00793 if (d1 * d2 < 0) 00794 ++degenerate_count; 00795 } 00796 00797 // controlla i triangoli intorno a v->mAdjacentVerts[ivert] 00798 Vertex* u = v->mAdjacentVerts[ivert]; 00799 for( int itri=0; itri<u->incidentTrianglesCount() && !degenerate_count; ++itri ) 00800 { 00801 // triangle to be removed 00802 if ( u->incidentTriangle(itri)->hasVertex(v) ) 00803 continue; 00804 00805 Vertex* edgev[] = { NULL, NULL }; 00806 if ( u == u->incidentTriangle(itri)->vertex(0) ) 00807 { 00808 edgev[0] = u->incidentTriangle(itri)->vertex(1); 00809 edgev[1] = u->incidentTriangle(itri)->vertex(2); 00810 } 00811 else 00812 if ( u == u->incidentTriangle(itri)->vertex(1) ) 00813 { 00814 edgev[0] = u->incidentTriangle(itri)->vertex(0); 00815 edgev[1] = u->incidentTriangle(itri)->vertex(2); 00816 } 00817 else 00818 if ( u == u->incidentTriangle(itri)->vertex(2) ) 00819 { 00820 edgev[0] = u->incidentTriangle(itri)->vertex(0); 00821 edgev[1] = u->incidentTriangle(itri)->vertex(1); 00822 } 00823 00824 fvec3 edge = (edgev[1]->position() - edgev[0]->position()); 00825 fvec3 n = cross( edge, u->incidentTriangle(itri)->normal() ); 00826 n.normalize(); 00827 float d1 = dot( u->position() - edgev[0]->position(), n ); 00828 float d2 = dot( (fvec3)solution - edgev[0]->position(), n ); 00829 00830 if (d1 * d2 < 0) 00831 ++degenerate_count; 00832 } 00833 00834 // non acceptable solution, assign very high cost 00835 if (degenerate_count) 00836 cost = 1.0e+37f; 00837 } 00838 00839 // to correctly simplify planar and cylindrical regions 00840 cost += ((dvec3)v->position() - solution).length() * 1.0e-12; 00841 00842 // check indeterminate case 00843 VL_CHECK( cost == cost ) 00844 if ( cost < v->mCollapseCost ) 00845 { 00846 v->mCollapseCost = (float)cost; 00847 v->mCollapseVertex = v->mAdjacentVerts[ivert]; 00848 v->mCollapsePosition = (fvec3)solution; 00849 } 00850 } 00851 00852 VL_CHECK( v->mCollapseVertex ) 00853 } 00854 //----------------------------------------------------------------------------- 00855 } 00856 00857 #endif