Visualization Library

A lightweight C++ OpenGL middleware for 2D/3D graphics
[Home] [Tutorials] [All Classes] [Grouped Classes]

X:/dropbox/visualizationlibrary/src/vlGraphics/PolygonSimplifier.cpp

Go to the documentation of this file.
00001 /**************************************************************************************/
00002 /*                                                                                    */
00003 /*  Visualization Library                                                             */
00004 /*  http://www.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 #include <vlGraphics/PolygonSimplifier.hpp>
00033 #include <vlGraphics/DoubleVertexRemover.hpp>
00034 #include <vlCore/Time.hpp>
00035 #include <vlCore/Log.hpp>
00036 #include <vlCore/Say.hpp>
00037 #include <set>
00038 
00039 using namespace vl;
00040 
00041 //-----------------------------------------------------------------------------
00042 namespace
00043 {
00044   class VertexPtrWrapper
00045   {
00046   public:
00047     VertexPtrWrapper(PolygonSimplifier::Vertex* ptr=NULL): mVertex(ptr) {}
00048 
00049     bool operator==(const VertexPtrWrapper& other) const
00050     {
00051       return mVertex == other.mVertex;
00052     }
00053 
00054     bool operator!=(const VertexPtrWrapper& other) const
00055     {
00056       return mVertex == other.mVertex;
00057     }
00058 
00059     bool operator<(const VertexPtrWrapper& other) const
00060     {
00061       if ( mVertex->collapseCost() != other.mVertex->collapseCost() )
00062         return mVertex->collapseCost() < other.mVertex->collapseCost();
00063       else
00064         return mVertex < other.mVertex;
00065     }
00066     PolygonSimplifier::Vertex* mVertex;
00067   };
00068 }
00069 //-----------------------------------------------------------------------------
00070 void PolygonSimplifier::simplify()
00071 {
00072   if (!mInput)
00073   {
00074     Log::error("PolygonSimplifier::simplify() : no input Geometry specified.\n");
00075     return;
00076   }
00077 
00078   // we don't support vertex attributes of any kind yet
00079   #ifndef NDEBUG
00080     bool problem = mInput->normalArray() != NULL || mInput->colorArray() != NULL || mInput->secondaryColorArray() != NULL || mInput->fogCoordArray() != NULL;
00081     for( int i=0; i<VL_MAX_TEXTURE_UNITS; ++i)
00082       problem |= mInput->texCoordArray(i) != NULL;
00083     problem |= mInput->vertexAttribArrays()->size() > 0 && !(!mInput->vertexArray() && mInput->vertexAttribArray(VA_Position) && mInput->vertexAttribArrays()->size() == 1);
00084     if (problem)
00085       Log::warning("PolygonSimplifier::simplify() simplifies only the position array of a Geometry, the other attibutes will be discarded.\n");
00086   #endif
00087 
00088   Time timer;
00089   timer.start();
00090 
00091   if ( removeDoubles() )
00092   {
00093     DoubleVertexRemover remover;
00094     remover.removeDoubles( mInput.get() );
00095   }
00096 
00097   std::vector<fvec3> verts;
00098   std::vector<int> indices;
00099   indices.reserve(1000);
00100 
00101   // merge all triangles in a single DrawElementsUInt
00102   ref<DrawElementsUInt> pint = new DrawElementsUInt(PT_TRIANGLES, 1);
00103   for( int i=0; i<mInput->drawCalls()->size(); ++i )
00104   {
00105     DrawCall* prim = mInput->drawCalls()->at(i);
00106     for(TriangleIterator trit = prim->triangleIterator(); trit.hasNext(); trit.next())
00107     {
00108       indices.push_back( trit.a() );
00109       indices.push_back( trit.b() );
00110       indices.push_back( trit.c() );
00111     }
00112   }
00113   
00114   if (indices.empty())
00115   {
00116     Log::warning("PolygonSimplifier::simplify() : no triangles found in input Geometry.\n");
00117     return;
00118   }
00119 
00120   ArrayAbstract* posarr = mInput->vertexArray() ? mInput->vertexArray() : mInput->vertexAttribArray(vl::VA_Position) ? mInput->vertexAttribArray(vl::VA_Position)->data() : NULL;
00121 
00122   if (!posarr)
00123   {
00124     Log::warning("PolygonSimplifier::simplify() : no vertices found in input Geometry.\n");
00125     return;
00126   }
00127 
00128   // fill vertices
00129   verts.resize( posarr->size() );
00130   for( size_t i=0; i< posarr->size(); ++i )
00131     verts[i] = (fvec3)posarr->getAsVec3(i);
00132 
00133   if (verts.empty())
00134   {
00135     Log::warning("PolygonSimplifier::simplify() : no vertices found in input Geometry.\n");
00136     return;
00137   }
00138 
00139   simplify(verts, indices);
00140 
00141   if (verbose())
00142     Log::print( Say("PolygonSimplifier::simplify() done in %.3ns\n") << timer.elapsed() );
00143 }
00144 //-----------------------------------------------------------------------------
00145 void PolygonSimplifier::simplify(const std::vector<fvec3>& in_verts, const std::vector<int>& in_tris)
00146 {
00147   if (verbose())
00148     Log::print("PolygonSimplifier::simplify() starting ... \n");
00149 
00150   Time timer;
00151   timer.start();
00152 
00153   // sort simplification targets 1.0 -> 0.0
00154   std::sort(mTargets.begin(), mTargets.end());
00155   std::reverse(mTargets.begin(), mTargets.end());
00156 
00157   mSimplifiedVertices.clear();
00158   mSimplifiedTriangles.clear();
00159   mProtectedVerts.clear();
00160   mTriangleLump.clear();
00161   mVertexLump.clear(); // mic fixme: this is the one taking time.
00162 
00163   // preallocate vertices and triangles in one chunk
00164   mTriangleLump.resize(in_tris.size()/3);
00165   mVertexLump.resize(in_verts.size());
00166 
00167   int polys_before = (int)in_tris.size() / 3;
00168   int verts_before = (int)in_verts.size();
00169 
00170   mSimplifiedTriangles.resize( in_tris.size() / 3 );
00171   mSimplifiedVertices.resize( in_verts.size() );
00172 
00173 #define SHUFFLE_VERTICES 0
00174 
00175 #if SHUFFLE_VERTICES
00176   std::vector<Vertex*> vertex_pool;
00177   vertex_pool.resize( in_verts.size() );
00178   for(int i=0; i<(int)mVertexLump.size(); ++i)
00179     vertex_pool[i] = &mVertexLump[i];
00180 
00181   // shuffle the vertices
00182   for(int i=0; i<(int)vertex_pool.size(); ++i)
00183   {
00184     int a = int( (float)rand() / (RAND_MAX+1) * vertex_pool.size() );
00185     int b = int( (float)rand() / (RAND_MAX+1) * vertex_pool.size() );
00186     Vertex* tmp = vertex_pool[a];
00187     vertex_pool[a] = vertex_pool[b];
00188     vertex_pool[b] = tmp;
00189   }
00190 #endif
00191 
00192   // initialize vertices
00193   for(int ivert=0; ivert<(int)in_verts.size(); ++ivert)
00194   {
00195 #if SHUFFLE_VERTICES
00196     mSimplifiedVertices[ivert] = vertex_pool[ivert];
00197 #else
00198     mSimplifiedVertices[ivert] = &mVertexLump[ivert];
00199 #endif
00200     mSimplifiedVertices[ivert]->mPosition = in_verts[ivert];
00201     // so that the user knows which vertex is which and can regenerate per-vertex
00202     // information like textures coordinates, colors etc.
00203     mSimplifiedVertices[ivert]->mOriginalIndex = ivert;
00204 
00205     // unprotect the vertex
00206     mSimplifiedVertices[ivert]->mProtected = false;
00207 
00208     // reserve the memory for quicker allocation
00209     mSimplifiedVertices[ivert]->mIncidentTriangles.reserve(12);
00210     mSimplifiedVertices[ivert]->mAdjacentVerts.reserve(12);
00211   }
00212 
00213   // initialize triangles
00214   for(int idx=0, itri=0; idx<(int)in_tris.size(); idx+=3, ++itri)
00215   {
00216     mSimplifiedTriangles[itri] = &mTriangleLump[itri];
00217     mSimplifiedTriangles[itri]->mVertices[0] = mSimplifiedVertices[ in_tris[idx+0] ];
00218     mSimplifiedTriangles[itri]->mVertices[1] = mSimplifiedVertices[ in_tris[idx+1] ];
00219     mSimplifiedTriangles[itri]->mVertices[2] = mSimplifiedVertices[ in_tris[idx+2] ];
00220   }
00221 
00222   // compute vertex/vertex and vertex/triangle connectivity
00223   for(int itri=0; itri<(int)mSimplifiedTriangles.size(); ++itri)
00224   {
00225     // add this triangle to all its vertices
00226     mSimplifiedTriangles[itri]->mVertices[0]->mIncidentTriangles.push_back( mSimplifiedTriangles[itri] );
00227     mSimplifiedTriangles[itri]->mVertices[1]->mIncidentTriangles.push_back( mSimplifiedTriangles[itri] );
00228     mSimplifiedTriangles[itri]->mVertices[2]->mIncidentTriangles.push_back( mSimplifiedTriangles[itri] );
00229     // add adjacent vertices
00230     mSimplifiedTriangles[itri]->mVertices[0]->addAdjacentVertex( mSimplifiedTriangles[itri]->mVertices[1] ); // vertex 0
00231     mSimplifiedTriangles[itri]->mVertices[0]->addAdjacentVertex( mSimplifiedTriangles[itri]->mVertices[2] );
00232     mSimplifiedTriangles[itri]->mVertices[1]->addAdjacentVertex( mSimplifiedTriangles[itri]->mVertices[0] ); // vertex 1
00233     mSimplifiedTriangles[itri]->mVertices[1]->addAdjacentVertex( mSimplifiedTriangles[itri]->mVertices[2] );
00234     mSimplifiedTriangles[itri]->mVertices[2]->addAdjacentVertex( mSimplifiedTriangles[itri]->mVertices[0] ); // vertex 2
00235     mSimplifiedTriangles[itri]->mVertices[2]->addAdjacentVertex( mSimplifiedTriangles[itri]->mVertices[1] );
00236     // compute normal
00237     mSimplifiedTriangles[itri]->computeNormal();
00238     // error
00239     QErr qerr = mSimplifiedTriangles[itri]->computeQErr();
00240     mSimplifiedTriangles[itri]->mVertices[0]->addQErr(qerr);
00241     mSimplifiedTriangles[itri]->mVertices[1]->addQErr(qerr);
00242     mSimplifiedTriangles[itri]->mVertices[2]->addQErr(qerr);
00243   }
00244 
00245   // - remove vertices without triangles
00246   // - compute edge penalties
00247   // - initialize the collapse info of each vertex
00248   for( int ivert=(int)mSimplifiedVertices.size(); ivert--; )
00249   {
00250     if ( mSimplifiedVertices[ivert]->incidentTrianglesCount() == 0 )
00251       mSimplifiedVertices.erase( mSimplifiedVertices.begin() + ivert );
00252     else
00253     {
00254       mSimplifiedVertices[ivert]->computeEdgePenalty();
00255       computeCollapseInfo( mSimplifiedVertices[ivert] );
00256     }
00257   }
00258 
00259   // sets the protected vertices
00260   for(int i=0; i<(int)mProtectedVerts.size(); ++i)
00261   {
00262     VL_CHECK(mProtectedVerts[i] < (int)mSimplifiedVertices.size() )
00263     mSimplifiedVertices[ mProtectedVerts[i] ]->mProtected = true;
00264   }
00265 
00266   if (verbose())
00267     Log::print(Say("database setup = %.3n\n") << timer.elapsed() );
00268 
00269   std::set<VertexPtrWrapper> vertex_set;
00270   for(int ivert=0; ivert<(int)mSimplifiedVertices.size(); ++ivert)
00271     if ( !mSimplifiedVertices[ivert]->mProtected )
00272       vertex_set.insert( mSimplifiedVertices[ivert] );
00273 
00274   if (verbose())
00275     Log::print(Say("heap setup = %.3n\n") << timer.elapsed() );
00276 
00277   // loop through the simplification targets
00278   for(size_t itarget=0, remove_order=0; itarget<mTargets.size(); ++itarget)
00279   {
00280     const int target_vertex_count = mTargets[itarget];
00281 
00282     if (target_vertex_count < 3)
00283     {
00284       Log::print(Say("Invalid target_vertex_count = %n\n") << target_vertex_count);
00285       return;
00286     }
00287 
00288     timer.start(1);
00289 
00290     std::vector< PolygonSimplifier::Vertex* > adj_verts;
00291     for( ; (int)vertex_set.size()>target_vertex_count; ++remove_order )
00292     {
00293       std::set<VertexPtrWrapper>::iterator it = vertex_set.begin();
00294       PolygonSimplifier::Vertex* v = it->mVertex;
00295       v->mRemoveOrder = (int)remove_order;
00296       vertex_set.erase(it);
00297 
00298       // remove the adjacent vertices to v and v->collapseVert()
00299       adj_verts.clear();
00300       for(int i=0; i<v->adjacentVerticesCount(); ++i)
00301       {
00302         VL_CHECK( v != v->adjacentVertex(i) )
00303         VL_CHECK( !v->adjacentVertex(i)->mAlreadyProcessed )
00304 
00305         adj_verts.push_back( v->adjacentVertex(i) );
00306         adj_verts.back()->mAlreadyProcessed = true;
00307         vertex_set.erase( v->adjacentVertex(i) );
00308       }
00309       for(int i=0; i<v->collapseVertex()->adjacentVerticesCount(); ++i)
00310       {
00311         if ( !v->collapseVertex()->adjacentVertex(i)->mAlreadyProcessed )
00312         {
00313           adj_verts.push_back( v->collapseVertex()->adjacentVertex(i) );
00314           vertex_set.erase( v->collapseVertex()->adjacentVertex(i) );
00315         }
00316       }
00317 
00318       VL_CHECK(!v->removed())
00319       VL_CHECK(v->collapseVertex())
00320       VL_CHECK(!v->collapseVertex()->removed())
00321 
00322       collapse( v );
00323 
00324       // reinsert the adj_verts if not removed
00325       // NOTE: v->collapseVertex() might have been also removed
00326       for( int i=(int)adj_verts.size(); i--; )
00327       {
00328         adj_verts[i]->mAlreadyProcessed = false;
00329 
00330         if ( adj_verts[i]->removed() )
00331           continue;
00332 
00333         computeCollapseInfo( adj_verts[i] );
00334 
00335         VL_CHECK( adj_verts[i]->checkTriangles() )
00336         VL_CHECK( adj_verts[i]->collapseVertex() != v )
00337         VL_CHECK( !adj_verts[i]->collapseVertex()->removed() )
00338 
00339         vertex_set.insert( adj_verts[i] );
00340       }
00341     }
00342 
00343     if (verbose())
00344       Log::print(Say("simplification = %.3ns (%.3ns)\n") << timer.elapsed() << timer.elapsed(1) );
00345 
00346     outputSimplifiedGeometry();
00347   }
00348 
00349   if (verbose() && !output().empty())
00350   {
00351     float elapsed = (float)timer.elapsed();
00352     int polys_after = output().back()->drawCalls()->at(0)->countTriangles();
00353     int verts_after = output().back()->vertexArray() ? (int)output().back()->vertexArray()->size() : (int)output().back()->vertexAttribArray(VA_Position)->data()->size();
00354     Log::print(Say("POLYS: %n -> %n, %.2n%%, %.1nT/s\n") << polys_before << polys_after << 100.0f*verts_after/verts_before << (polys_before - polys_after)/elapsed );
00355     Log::print(Say("VERTS: %n -> %n, %.2n%%, %.1nV/s\n") << verts_before << verts_after << 100.0f*verts_after/verts_before << (verts_before - verts_after)/elapsed );
00356   }
00357 }
00358 //-----------------------------------------------------------------------------
00359 void PolygonSimplifier::outputSimplifiedGeometry()
00360 {
00361   // count vertices required
00362   size_t vert_count = 0;
00363   for(int i=0; i<(int)mSimplifiedVertices.size(); ++i)
00364     vert_count += mSimplifiedVertices[i]->mRemoved ? 0 : 1;
00365 
00366   // regenerate vertex buffer & generate indices for index buffer
00367   ref<ArrayFloat3> arr_f3 = new ArrayFloat3;
00368   arr_f3->resize(vert_count);
00369   for(int i=0, vert_index=0; i<(int)mSimplifiedVertices.size(); ++i)
00370   {
00371     if (!mSimplifiedVertices[i]->mRemoved)
00372     {
00373       arr_f3->at(vert_index) = mSimplifiedVertices[i]->mPosition;
00374       mSimplifiedVertices[i]->mSimplifiedIndex = vert_index++;
00375     }
00376   }
00377 
00378   // count indices required
00379   size_t index_count = 0;
00380   for(size_t i=0; i<mSimplifiedTriangles.size(); ++i)
00381     index_count += mSimplifiedTriangles[i]->mRemoved ? 0 : 3;
00382 
00383   // regenerate index buffer
00384   ref<DrawElementsUInt> de = new DrawElementsUInt(PT_TRIANGLES);
00385   de->indexBuffer()->resize(index_count);
00386   DrawElementsUInt::index_type* ptr = de->indexBuffer()->begin();
00387   for(size_t i=0; i<mSimplifiedTriangles.size(); ++i)
00388   {
00389     if(!mSimplifiedTriangles[i]->mRemoved)
00390     {
00391       VL_CHECK( !mSimplifiedTriangles[i]->mVertices[0]->mRemoved )
00392       VL_CHECK( !mSimplifiedTriangles[i]->mVertices[1]->mRemoved )
00393       VL_CHECK( !mSimplifiedTriangles[i]->mVertices[2]->mRemoved )
00394 
00395       ptr[0] = mSimplifiedTriangles[i]->mVertices[0]->mSimplifiedIndex;
00396       ptr[1] = mSimplifiedTriangles[i]->mVertices[1]->mSimplifiedIndex;
00397       ptr[2] = mSimplifiedTriangles[i]->mVertices[2]->mSimplifiedIndex;
00398       ptr+=3;
00399     }
00400   }
00401   VL_CHECK(ptr == de->indexBuffer()->end());
00402 
00403   // output geometry
00404   mOutput.push_back( new Geometry );
00405   if (mInput->vertexArray())
00406     mOutput.back()->setVertexArray( arr_f3.get() );
00407   else
00408     mOutput.back()->setVertexAttribArray( vl::VA_Position, arr_f3.get() );
00409   mOutput.back()->drawCalls()->push_back( de.get() );
00410 }
00411 //-----------------------------------------------------------------------------
00412 void PolygonSimplifier::clearTrianglesAndVertices()
00413 {
00414   mSimplifiedVertices.clear();
00415   mSimplifiedTriangles.clear();
00416   mProtectedVerts.clear();
00417   mTriangleLump.clear();
00418   mVertexLump.clear();
00419 }
00420 //-----------------------------------------------------------------------------

Visualization Library 2011.09.1160 Reference Documentation
Copyright 2005-2011 Michele Bosi. All rights reserved.
Updated on Thu May 2 2013 13:40:39.
Permission is granted to use this page to write and publish articles regarding Visualization Library.