Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
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
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
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
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
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();
00162
00163
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
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
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
00202
00203 mSimplifiedVertices[ivert]->mOriginalIndex = ivert;
00204
00205
00206 mSimplifiedVertices[ivert]->mProtected = false;
00207
00208
00209 mSimplifiedVertices[ivert]->mIncidentTriangles.reserve(12);
00210 mSimplifiedVertices[ivert]->mAdjacentVerts.reserve(12);
00211 }
00212
00213
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
00223 for(int itri=0; itri<(int)mSimplifiedTriangles.size(); ++itri)
00224 {
00225
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
00230 mSimplifiedTriangles[itri]->mVertices[0]->addAdjacentVertex( mSimplifiedTriangles[itri]->mVertices[1] );
00231 mSimplifiedTriangles[itri]->mVertices[0]->addAdjacentVertex( mSimplifiedTriangles[itri]->mVertices[2] );
00232 mSimplifiedTriangles[itri]->mVertices[1]->addAdjacentVertex( mSimplifiedTriangles[itri]->mVertices[0] );
00233 mSimplifiedTriangles[itri]->mVertices[1]->addAdjacentVertex( mSimplifiedTriangles[itri]->mVertices[2] );
00234 mSimplifiedTriangles[itri]->mVertices[2]->addAdjacentVertex( mSimplifiedTriangles[itri]->mVertices[0] );
00235 mSimplifiedTriangles[itri]->mVertices[2]->addAdjacentVertex( mSimplifiedTriangles[itri]->mVertices[1] );
00236
00237 mSimplifiedTriangles[itri]->computeNormal();
00238
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
00246
00247
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
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
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
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
00325
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
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
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
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
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
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