Index: /OpenSceneGraph/trunk/include/osgUtil/MeshOptimizers =================================================================== --- /OpenSceneGraph/trunk/include/osgUtil/MeshOptimizers (revision 11204) +++ /OpenSceneGraph/trunk/include/osgUtil/MeshOptimizers (revision 11204) @@ -0,0 +1,101 @@ +/* -*-c++-*- OpenSceneGraph - Copyright (C) 1998-2006 Robert Osfield + * + * This library is open source and may be redistributed and/or modified under + * the terms of the OpenSceneGraph Public License (OSGPL) version 0.0 or + * (at your option) any later version. The full license is in LICENSE file + * included with this distribution, and on the openscenegraph.org website. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * OpenSceneGraph Public License for more details. +*/ + +#ifndef OSGUTIL_MESHOPTIMIZERS +#define OSGUTIL_MESHOPTIMIZERS 1 + +#include +#include + +#include +#include +#include + +#include + +namespace osgUtil +{ +// Helper that collects all the unique Geometry objects in a subgraph. +class OSGUTIL_EXPORT GeometryCollector : public BaseOptimizerVisitor +{ +public: + GeometryCollector(Optimizer* optimizer, + Optimizer::OptimizationOptions options) + : BaseOptimizerVisitor(optimizer, options) {} + void reset(); + void apply(osg::Geode& geode); + typedef std::set GeometryList; + GeometryList& getGeometryList() { return _geometryList; }; +protected: + GeometryList _geometryList; +}; + +// Convert geometry that uses DrawArrays to DrawElements i.e., +// construct a real mesh. This removes duplicate vertices. +class OSGUTIL_EXPORT IndexMeshVisitor : public GeometryCollector +{ +public: + IndexMeshVisitor(Optimizer* optimizer = 0) + : GeometryCollector(optimizer, Optimizer::INDEX_MESH) + { + } + void makeMesh(osg::Geometry& geom); + void makeMesh(); +}; + +// Optimize the triangle order in a mesh for best use of the GPU's +// post-transform cache. This uses Tom Forsyth's algorithm described +// at http://home.comcast.net/~tom_forsyth/papers/fast_vert_cache_opt.html +class OSGUTIL_EXPORT VertexCacheVisitor : public GeometryCollector +{ +public: + VertexCacheVisitor(Optimizer* optimizer = 0) + : GeometryCollector(optimizer, Optimizer::VERTEX_POSTTRANSFORM) + { + } + + void optimizeVertices(osg::Geometry& geom); + void optimizeVertices(); +private: + void doVertexOptimization(osg::Geometry& geom, + std::vector& vertDrawList); +}; + +// Gather statistics on post-transform cache misses for geometry +class OSGUTIL_EXPORT VertexCacheMissVisitor : public osg::NodeVisitor +{ +public: + VertexCacheMissVisitor(unsigned cacheSize = 16); + void reset(); + virtual void apply(osg::Geode& geode); + void doGeometry(osg::Geometry& geom); + unsigned misses; + unsigned triangles; +protected: + const unsigned _cacheSize; +}; + +// Optimize the use of the GPU pre-transform cache by arranging vertex +// attributes in the order they are used. +class OSGUTIL_EXPORT VertexAccessOrderVisitor : public GeometryCollector +{ +public: + VertexAccessOrderVisitor(Optimizer* optimizer = 0) + : GeometryCollector(optimizer, Optimizer::VERTEX_PRETRANSFORM) + { + } + void optimizeOrder(); + void optimizeOrder(osg::Geometry& geom); +}; +} +#endif Index: /OpenSceneGraph/trunk/include/osgUtil/Optimizer =================================================================== --- /OpenSceneGraph/trunk/include/osgUtil/Optimizer (revision 9886) +++ /OpenSceneGraph/trunk/include/osgUtil/Optimizer (revision 11204) @@ -86,4 +86,7 @@ STATIC_OBJECT_DETECTION = (1 << 16), FLATTEN_STATIC_TRANSFORMS_DUPLICATING_SHARED_SUBGRAPHS = (1 << 17), + INDEX_MESH = (1 << 18), + VERTEX_POSTTRANSFORM = (1 << 19), + VERTEX_PRETRANSFORM = (1 << 20), DEFAULT_OPTIMIZATIONS = FLATTEN_STATIC_TRANSFORMS | REMOVE_REDUNDANT_NODES | Index: /OpenSceneGraph/trunk/src/osgUtil/Optimizer.cpp =================================================================== --- /OpenSceneGraph/trunk/src/osgUtil/Optimizer.cpp (revision 11131) +++ /OpenSceneGraph/trunk/src/osgUtil/Optimizer.cpp (revision 11204) @@ -40,4 +40,5 @@ #include #include +#include #include @@ -55,5 +56,5 @@ } -static osg::ApplicationUsageProxy Optimizer_e0(osg::ApplicationUsage::ENVIRONMENTAL_VARIABLE,"OSG_OPTIMIZER \" []\"","OFF | DEFAULT | FLATTEN_STATIC_TRANSFORMS | FLATTEN_STATIC_TRANSFORMS_DUPLICATING_SHARED_SUBGRAPHS | REMOVE_REDUNDANT_NODES | COMBINE_ADJACENT_LODS | SHARE_DUPLICATE_STATE | MERGE_GEOMETRY | MERGE_GEODES | SPATIALIZE_GROUPS | COPY_SHARED_NODES | TRISTRIP_GEOMETRY | OPTIMIZE_TEXTURE_SETTINGS | REMOVE_LOADED_PROXY_NODES | TESSELLATE_GEOMETRY | CHECK_GEOMETRY | FLATTEN_BILLBOARDS | TEXTURE_ATLAS_BUILDER | STATIC_OBJECT_DETECTION"); +static osg::ApplicationUsageProxy Optimizer_e0(osg::ApplicationUsage::ENVIRONMENTAL_VARIABLE,"OSG_OPTIMIZER \" []\"","OFF | DEFAULT | FLATTEN_STATIC_TRANSFORMS | FLATTEN_STATIC_TRANSFORMS_DUPLICATING_SHARED_SUBGRAPHS | REMOVE_REDUNDANT_NODES | COMBINE_ADJACENT_LODS | SHARE_DUPLICATE_STATE | MERGE_GEOMETRY | MERGE_GEODES | SPATIALIZE_GROUPS | COPY_SHARED_NODES | TRISTRIP_GEOMETRY | OPTIMIZE_TEXTURE_SETTINGS | REMOVE_LOADED_PROXY_NODES | TESSELLATE_GEOMETRY | CHECK_GEOMETRY | FLATTEN_BILLBOARDS | TEXTURE_ATLAS_BUILDER | STATIC_OBJECT_DETECTION | INDEX_MESH | VERTEX_POSTTRANSFORM | VERTEX_PRETRANSFORM"); void Optimizer::optimize(osg::Node* node) @@ -126,4 +127,13 @@ else if(str.find("STATIC_OBJECT_DETECTION")!=std::string::npos) options |= STATIC_OBJECT_DETECTION; + if(str.find("~INDEX_MESH")!=std::string::npos) options ^= INDEX_MESH; + else if(str.find("INDEX_MESH")!=std::string::npos) options |= INDEX_MESH; + + if(str.find("~VERTEX_POSTTRANSFORM")!=std::string::npos) options ^= VERTEX_POSTTRANSFORM; + else if(str.find("VERTEX_POSTTRANSFORM")!=std::string::npos) options |= VERTEX_POSTTRANSFORM; + + if(str.find("~VERTEX_PRETRANSFORM")!=std::string::npos) options ^= VERTEX_PRETRANSFORM; + else if(str.find("VERTEX_PRETRANSFORM")!=std::string::npos) options |= VERTEX_PRETRANSFORM; + } else @@ -346,4 +356,28 @@ node->accept(sv); sv.divide(); + } + + if (options & INDEX_MESH) + { + OSG_NOTIFY(osg::INFO)<<"Optimizer::optimize() doing INDEX_MESH"<accept(imv); + imv.makeMesh(); + } + + if (options & VERTEX_POSTTRANSFORM) + { + OSG_NOTIFY(osg::INFO)<<"Optimizer::optimize() doing VERTEX_POSTTRANSFORM"<accept(vcv); + vcv.optimizeVertices(); + } + + if (options & VERTEX_PRETRANSFORM) + { + OSG_NOTIFY(osg::INFO)<<"Optimizer::optimize() doing VERTEX_PRETRANSFORM"<accept(vaov); + vaov.optimizeOrder(); } Index: /OpenSceneGraph/trunk/src/osgUtil/CMakeLists.txt =================================================================== --- /OpenSceneGraph/trunk/src/osgUtil/CMakeLists.txt (revision 10894) +++ /OpenSceneGraph/trunk/src/osgUtil/CMakeLists.txt (revision 11204) @@ -25,4 +25,5 @@ ${HEADER_PATH}/IncrementalCompileOperation ${HEADER_PATH}/LineSegmentIntersector + ${HEADER_PATH}/MeshOptimizers ${HEADER_PATH}/OperationArrayFunctor ${HEADER_PATH}/Optimizer @@ -68,4 +69,5 @@ IncrementalCompileOperation.cpp LineSegmentIntersector.cpp + MeshOptimizers.cpp Optimizer.cpp PlaneIntersector.cpp Index: /OpenSceneGraph/trunk/src/osgUtil/MeshOptimizers.cpp =================================================================== --- /OpenSceneGraph/trunk/src/osgUtil/MeshOptimizers.cpp (revision 11204) +++ /OpenSceneGraph/trunk/src/osgUtil/MeshOptimizers.cpp (revision 11204) @@ -0,0 +1,1148 @@ +/* -*-c++-*- OpenSceneGraph - Copyright (C) 1998-2006 Robert Osfield + * Copyright (C) 2010 Tim Moore + * + * This library is open source and may be redistributed and/or modified under + * the terms of the OpenSceneGraph Public License (OSGPL) version 0.0 or + * (at your option) any later version. The full license is in LICENSE file + * included with this distribution, and on the openscenegraph.org website. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * OpenSceneGraph Public License for more details. +*/ + +#include +#include + +#include +#include +#include + +#include + +#include +#include +#include +#include + +#include + +using namespace std; +using namespace osg; + +namespace osgUtil +{ + +void GeometryCollector::reset() +{ + _geometryList.clear(); +} + +void GeometryCollector::apply(Geode& geode) +{ + for(unsigned int i = 0; i < geode.getNumDrawables(); ++i ) + { + osg::Geometry* geom = dynamic_cast(geode.getDrawable(i)); + if (geom) _geometryList.insert(geom); + } +} + +namespace +{ +typedef std::vector IndexList; + +// A helper class that gathers up all the attribute arrays of an +// osg::Geometry object that are BIND_PER_VERTEX and runs an +// ArrayVisitor on them. +struct GeometryArrayGatherer +{ + typedef std::vector ArrayList; + + GeometryArrayGatherer(osg::Geometry& geometry) + : _useDrawElements(true) + { + add(geometry.getVertexArray(),osg::Geometry::BIND_PER_VERTEX); + add(geometry.getNormalArray(),geometry.getNormalBinding()); + add(geometry.getColorArray(),geometry.getColorBinding()); + add(geometry.getSecondaryColorArray(),geometry.getSecondaryColorBinding()); + add(geometry.getFogCoordArray(),geometry.getFogCoordBinding()); + unsigned int i; + for(i=0;iaccept(av); + } + } + + ArrayList _arrayList; + // True if geometry contains bindings that are compatible with + // DrawElements. + bool _useDrawElements; +}; + +// Compare vertices in a mesh using all their attributes. The vertices +// are identified by their index. Extracted from TriStripVisitor.cpp +struct VertexAttribComparitor : public GeometryArrayGatherer +{ + VertexAttribComparitor(osg::Geometry& geometry) + : GeometryArrayGatherer(geometry) + { + } + + bool operator() (unsigned int lhs, unsigned int rhs) const + { + for(ArrayList::const_iterator itr=_arrayList.begin(); + itr!=_arrayList.end(); + ++itr) + { + int compare = (*itr)->compare(lhs,rhs); + if (compare==-1) return true; + if (compare==1) return false; + } + return false; + } + + int compare(unsigned int lhs, unsigned int rhs) + { + for(ArrayList::iterator itr=_arrayList.begin(); + itr!=_arrayList.end(); + ++itr) + { + int compare = (*itr)->compare(lhs,rhs); + if (compare==-1) return -1; + if (compare==1) return 1; + } + return 0; + } + +protected: + VertexAttribComparitor& operator = (const VertexAttribComparitor&) { return *this; } + +}; + +// Compact the vertex attribute arrays. Also stolen from TriStripVisitor +class RemapArray : public osg::ArrayVisitor +{ + public: + RemapArray(const IndexList& remapping):_remapping(remapping) {} + + const IndexList& _remapping; + + template + inline void remap(T& array) + { + for(unsigned int i=0;i<_remapping.size();++i) + { + if (i!=_remapping[i]) + { + array[i] = array[_remapping[i]]; + } + } + array.erase(array.begin()+_remapping.size(),array.end()); + } + + virtual void apply(osg::Array&) {} + virtual void apply(osg::ByteArray& array) { remap(array); } + virtual void apply(osg::ShortArray& array) { remap(array); } + virtual void apply(osg::IntArray& array) { remap(array); } + virtual void apply(osg::UByteArray& array) { remap(array); } + virtual void apply(osg::UShortArray& array) { remap(array); } + virtual void apply(osg::UIntArray& array) { remap(array); } + virtual void apply(osg::Vec4ubArray& array) { remap(array); } + virtual void apply(osg::FloatArray& array) { remap(array); } + virtual void apply(osg::Vec2Array& array) { remap(array); } + virtual void apply(osg::Vec3Array& array) { remap(array); } + virtual void apply(osg::Vec4Array& array) { remap(array); } + +protected: + + RemapArray& operator = (const RemapArray&) { return *this; } +}; + + +// Construct an index list of triangles for DrawElements for any input +// primitives. +struct MyTriangleOperator +{ + + IndexList _remapIndices; + IndexList _in_indices; + + inline void operator()(unsigned int p1, unsigned int p2, unsigned int p3) + { + if (_remapIndices.empty()) + { + _in_indices.push_back(p1); + _in_indices.push_back(p2); + _in_indices.push_back(p3); + } + else + { + _in_indices.push_back(_remapIndices[p1]); + _in_indices.push_back(_remapIndices[p2]); + _in_indices.push_back(_remapIndices[p3]); + } + } + +}; +typedef osg::TriangleIndexFunctor MyTriangleIndexFunctor; +} + +void IndexMeshVisitor::makeMesh(Geometry& geom) +{ + if (geom.getNormalBinding()==osg::Geometry::BIND_PER_PRIMITIVE || + geom.getNormalBinding()==osg::Geometry::BIND_PER_PRIMITIVE_SET) return; + + if (geom.getColorBinding()==osg::Geometry::BIND_PER_PRIMITIVE || + geom.getColorBinding()==osg::Geometry::BIND_PER_PRIMITIVE_SET) return; + + if (geom.getSecondaryColorBinding()==osg::Geometry::BIND_PER_PRIMITIVE || + geom.getSecondaryColorBinding()==osg::Geometry::BIND_PER_PRIMITIVE_SET) return; + + if (geom.getFogCoordBinding()==osg::Geometry::BIND_PER_PRIMITIVE || + geom.getFogCoordBinding()==osg::Geometry::BIND_PER_PRIMITIVE_SET) return; + + // no point optimizing if we don't have enough vertices. + if (!geom.getVertexArray() || geom.getVertexArray()->getNumElements()<3) return; + + // check for the existence of surface primitives + unsigned int numSurfacePrimitives = 0; + unsigned int numNonIndexedPrimitives = 0; + Geometry::PrimitiveSetList& primitives = geom.getPrimitiveSetList(); + Geometry::PrimitiveSetList::iterator itr; + for(itr=primitives.begin(); + itr!=primitives.end(); + ++itr) + { + switch((*itr)->getMode()) + { + case(PrimitiveSet::TRIANGLES): + case(PrimitiveSet::TRIANGLE_STRIP): + case(PrimitiveSet::TRIANGLE_FAN): + case(PrimitiveSet::QUADS): + case(PrimitiveSet::QUAD_STRIP): + case(PrimitiveSet::POLYGON): + ++numSurfacePrimitives; + break; + default: + // For now, only deal with polygons + return; + } + PrimitiveSet::Type type = (*itr)->getType(); + if (!(type == PrimitiveSet::DrawElementsUBytePrimitiveType + || type == PrimitiveSet::DrawElementsUShortPrimitiveType + || type == PrimitiveSet::DrawElementsUIntPrimitiveType)) + numNonIndexedPrimitives++; + } + + // nothing to index + if (!numSurfacePrimitives || !numNonIndexedPrimitives) return; + + // check to see if vertex attributes indices exists, if so expand them to remove them + if (geom.suitableForOptimization()) + { + // removing coord indices + osg::notify(osg::INFO)<<"TriStripVisitor::stripify(Geometry&): Removing attribute indices"< IndexList; + unsigned int numVertices = geom.getVertexArray()->getNumElements(); + IndexList indices(numVertices); + unsigned int i,j; + for(i=0;iaccept(taf); + } + + // remap any shared vertex attributes + RemapArray ra(copyMapping); + arrayComparitor.accept(ra); + if (taf._in_indices.size() < 65536) + { + osg::DrawElementsUShort* elements = new DrawElementsUShort(GL_TRIANGLES); + for (IndexList::iterator itr = taf._in_indices.begin(), + end = taf._in_indices.end(); + itr != end; + ++itr) + { + elements->push_back((GLushort)(*itr)); + } + new_primitives.push_back(elements); + } + else + { + osg::DrawElementsUInt* elements + = new DrawElementsUInt(GL_TRIANGLES, taf._in_indices.begin(), + taf._in_indices.end()); + new_primitives.push_back(elements); + } + geom.setPrimitiveSetList(new_primitives); +} + +void IndexMeshVisitor::makeMesh() +{ + for(GeometryList::iterator itr=_geometryList.begin(); + itr!=_geometryList.end(); + ++itr) + { + makeMesh(*(*itr)); + } +} + +namespace +{ +// A simulation of a Least Recently Used cache. Position in the cache +// corresponds to when the vertex was used i.e., 0 is the most +// recently used. +struct LRUCache +{ + LRUCache(size_t maxSize_) : maxSize(maxSize_) + { + entries.reserve(maxSize_ + 3); + } + vector entries; + size_t maxSize; + + // Add a list of values to the cache + void addEntries(unsigned* begin, unsigned* end) + { + // If any of the new vertices are already in the cache, remove + // them, leaving some room at the front of the cache. + vector::reverse_iterator validEnd = entries.rend(); + for (unsigned* pent = begin; pent != end; ++pent) + { + validEnd = remove(entries.rbegin(), validEnd, *pent); + } + // Now make room still needed for new cache entries + size_t newEnts = end - begin; + ssize_t spaceNeeded = newEnts - (entries.rend() - validEnd); + if (spaceNeeded > 0) + { + if (maxSize - entries.size() >= static_cast(spaceNeeded)) + entries.resize(entries.size() + spaceNeeded); + else if (entries.size() < maxSize) + entries.resize(maxSize); + copy_backward(entries.begin() + newEnts - spaceNeeded, + entries.end() - spaceNeeded, entries.end()); + } + copy(begin, end, entries.begin()); + } + + bool empty() + { + return entries.empty(); + } +}; + +// A list of triangles that use a vertex is associated with the Vertex +// structure in another array. +struct Vertex +{ + int cachePosition; + float score; + int trisUsing; + int numActiveTris; // triangles left to process + size_t triList; // index to start of triangle storage + Vertex() + : cachePosition(-1), score(0.0f), trisUsing(0), numActiveTris(0), triList(0) + { + } +}; + +// Code from Tom Forsyth's article. The algorithm is described in +// detail at +// http://home.comcast.net/~tom_forsyth/papers/fast_vert_cache_opt.html. +// In summary, vertices are assigned a score based on the number of +// triangles that use it (valence) and the vertex's position in the +// model of the vertex cache, if any. Triangles are also given a +// score, which is the sum of the scores of its vertices. The triangle +// with the best score is added to the draw list, its vertices are +// added and / or moved in the cache, the scores of vertices in the +// cache and ejected from the cache are updated. Then the scores of +// triangles that use those vertices are updated. +// +// Unless the cache is empty, the "best" triangle is found by +// searching triangles that use vertices in the cache, not the whole +// mesh. This keeps the algorithm running in time proportional to the +// size of the mesh. + +// The "magic" scoring functions are described in the paper. +const float cacheDecayPower = 1.5f; +const float lastTriScore = 0.75f; +const float valenceBoostScale = 2.0f; +const float valenceBoostPower = 0.5f; + +const int maxCacheSize = 32; + +float findVertexScore (Vertex& vert) +{ + + if (vert.numActiveTris == 0) + { + // No tri needs this vertex! + return -1.0f; + } + float score = 0.0f; + int cachePosition = vert.cachePosition; + + if (cachePosition < 0) + { + // Vertex is not in FIFO cache - no score. + } + else + { + if (cachePosition < 3) + { + // This vertex was used in the last triangle, + // so it has a fixed score, whichever of the three + // it's in. Otherwise, you can get very different + // answers depending on whether you add + // the triangle 1,2,3 or 3,1,2 - which is silly. + score = lastTriScore; + } + else + { + assert (cachePosition < maxCacheSize); + // Points for being high in the cache. + const float scaler = 1.0f / (maxCacheSize - 3); + score = 1.0f - (cachePosition - 3 ) * scaler; + score = powf(score, cacheDecayPower); + } + } + // Bonus points for having a low number of tris still to + // use the vert, so we get rid of lone verts quickly. + float valenceBoost = powf(vert.numActiveTris, -valenceBoostPower); + score += valenceBoostScale * valenceBoost; + return score; +} + + +typedef vector VertexList; + +struct Triangle +{ + float score; + unsigned verts[3]; +}; + +typedef vector TriangleList; + +inline float findTriangleScore(Triangle& tri, const VertexList& vertices) +{ + float result = 0.0f; + for (int i = 0; i < 3; ++i) + result += vertices[tri.verts[i]].score; + return result; +} + +typedef std::pair TriangleScore; + +TriangleScore computeTriScores(Vertex& vert, const VertexList& vertices, + TriangleList& triangles, vector& triStore) +{ + float bestScore = 0.0; + unsigned bestTri; + for (size_t i = vert.triList; + i < vert.triList + vert.numActiveTris; + ++i) + { + unsigned tri = triStore[i]; + float score = triangles[tri].score = findTriangleScore(triangles[tri], + vertices); + if (score > bestScore) + { + bestScore = score; + bestTri = tri; + } + } + return make_pair(bestTri, bestScore); +} + +typedef vector TriangleList; + +struct TriangleCounterOperator +{ + VertexList* vertices; + int triangleCount; + TriangleCounterOperator() : vertices(0), triangleCount(0) {} + + void doVertex(unsigned p) + { + if (vertices->size() <= p) + vertices->resize(p + 1); + (*vertices)[p].trisUsing++; + } + + void operator() (unsigned int p1, unsigned int p2, unsigned int p3) + { + if (p1 == p2 || p2 == p3 || p1 == p3) + return; + doVertex(p1); + doVertex(p2); + doVertex(p3); + triangleCount++; + } +}; + +struct TriangleCounter : public TriangleIndexFunctor +{ + TriangleCounter(vector* vertices_) + { + vertices = vertices_; + } +}; + +// Initialize the vertex triangle lists and the triangle data structures +struct TriangleAddOperator +{ + VertexList* vertices; + vector* vertexTris; + TriangleList* triangles; + int triIdx; + TriangleAddOperator() : vertices(0), triIdx(0) {} + + void doVertex(unsigned p) + { + (*vertexTris)[(*vertices)[p].triList + (*vertices)[p].numActiveTris++] + = triIdx; + } + + void operator() (unsigned int p1, unsigned int p2, unsigned int p3) + { + if (p1 == p2 || p2 == p3 || p1 == p3) + return; + doVertex(p1); + doVertex(p2); + doVertex(p3); + (*triangles)[triIdx].verts[0] = p1; + (*triangles)[triIdx].verts[1] = p2; + (*triangles)[triIdx].verts[2] = p3; + triIdx++; + } +}; + +struct TriangleAdder : public TriangleIndexFunctor +{ + TriangleAdder(VertexList* vertices_, vector* vertexTris_, + TriangleList* triangles_) + { + vertices = vertices_; + vertexTris = vertexTris_; + triangles = triangles_; + } +}; + +struct CompareTriangle +{ + bool operator()(const Triangle& lhs, const Triangle& rhs) + { + return lhs.score < rhs.score; + } +}; +} + +void VertexCacheVisitor::optimizeVertices(Geometry& geom) +{ + Array* vertArray = geom.getVertexArray(); + if (!vertArray) + return; + unsigned vertArraySize = vertArray->getNumElements(); + // If all the vertices fit in the cache, there's no point in + // doing this optimization. + if (vertArraySize <= 16) + return; + Geometry::PrimitiveSetList& primSets = geom.getPrimitiveSetList(); + for (Geometry::PrimitiveSetList::iterator itr = primSets.begin(), + end = primSets.end(); + itr != end; + ++itr) + { + // Can only deal with polygons. + switch ((*itr)->getMode()) + { + case(PrimitiveSet::TRIANGLES): + case(PrimitiveSet::TRIANGLE_STRIP): + case(PrimitiveSet::TRIANGLE_FAN): + case(PrimitiveSet::QUADS): + case(PrimitiveSet::QUAD_STRIP): + case(PrimitiveSet::POLYGON): + break; + default: + return; + } + PrimitiveSet::Type type = (*itr)->getType(); + if (type != PrimitiveSet::DrawElementsUBytePrimitiveType + && type != PrimitiveSet::DrawElementsUShortPrimitiveType + && type != PrimitiveSet::DrawElementsUIntPrimitiveType) + return; + } +#if 0 + VertexCacheMissVisitor missv; + missv.doGeometry(geom); + cout << "Before optimization: misses: " << missv.misses + << " triangles: " << missv.triangles << " acmr: "; + if (missv.triangles > 0.0) + cout << (double)missv.misses / (double)missv.triangles << "\n"; + else + cout << "0.0\n"; + missv.reset(); +#endif + vector newVertList; + doVertexOptimization(geom, newVertList); + Geometry::PrimitiveSetList newPrims; + if (vertArraySize < 65536) + { + osg::DrawElementsUShort* elements = new DrawElementsUShort(GL_TRIANGLES); + elements->reserve(newVertList.size()); + for (vector::iterator itr = newVertList.begin(), + end = newVertList.end(); + itr != end; + ++itr) + elements->push_back((GLushort)*itr); + if (geom.getUseVertexBufferObjects()) + { + elements->setElementBufferObject(new ElementBufferObject); + } + newPrims.push_back(elements); + } + else + { + osg::DrawElementsUInt* elements + = new DrawElementsUInt(GL_TRIANGLES, newVertList.begin(), + newVertList.end()); + if (geom.getUseVertexBufferObjects()) + { + elements->setElementBufferObject(new ElementBufferObject); + } + newPrims.push_back(elements); + } + + geom.setPrimitiveSetList(newPrims); +#if 0 + missv.doGeometry(geom); + cout << "After optimization: misses: " << missv.misses + << " triangles: " << missv.triangles << " acmr: "; + if (missv.triangles > 0.0) + cout << (double)missv.misses / (double)missv.triangles << "\n"; + else + cout << "0.0\n"; +#endif + geom.dirtyDisplayList(); +} + +// The main optimization loop +void VertexCacheVisitor::doVertexOptimization(Geometry& geom, + vector& vertDrawList) +{ + Geometry::PrimitiveSetList& primSets = geom.getPrimitiveSetList(); + // lists for all the vertices and triangles + VertexList vertices; + TriangleList triangles; + TriangleCounter triCounter(&vertices); + for (Geometry::PrimitiveSetList::iterator itr = primSets.begin(), + end = primSets.end(); + itr != end; + ++itr) + (*itr)->accept(triCounter); + triangles.resize(triCounter.triangleCount); + // Get total of triangles used by all the vertices + size_t vertTrisSize = 0; + for (VertexList::iterator itr = vertices.begin(), end = vertices.end(); + itr != end; + ++itr) + { + itr->triList = vertTrisSize; + vertTrisSize += itr->trisUsing; + } + // Store for lists of triangles (indices) used by the vertices + vector vertTriListStore(vertTrisSize); + TriangleAdder triAdder(&vertices, &vertTriListStore, &triangles); + for (Geometry::PrimitiveSetList::iterator itr = primSets.begin(), + end = primSets.end(); + itr != end; + ++itr) + (*itr)->accept(triAdder); + // Set up initial scores for vertices and triangles + for (VertexList::iterator itr = vertices.begin(), end = vertices.end(); + itr != end; + ++itr) + itr->score = findVertexScore(*itr); + for (TriangleList::iterator itr = triangles.begin(), end = triangles.end(); + itr != end; + ++itr) + { + itr->score = 0.0f; + for (int i = 0; i < 3; ++i) + itr->score += vertices[itr->verts[i]].score; + } + // Add Triangles to the draw list until there are no more. + unsigned trisLeft = triangles.size(); + vertDrawList.reserve(trisLeft * 3); + LRUCache cache(maxCacheSize); + while (trisLeft-- > 0) + { + Triangle* triToAdd = 0; + float bestScore = 0.0; + for (vector::const_iterator itr = cache.entries.begin(), + end = cache.entries.end(); + itr != end; + ++itr) + { + TriangleScore tscore = computeTriScores(vertices[*itr], vertices, + triangles, vertTriListStore); + if (tscore.second > bestScore) + { + bestScore = tscore.second; + triToAdd = &triangles[tscore.first]; + } + } + if (!triToAdd) + { + // The cache was empty, or all the triangles that use + // vertices in the cache have already been added. + OSG_NOTIFY(osg::DEBUG_INFO) << "VertexCacheVisitor searching all triangles" << std::endl; + TriangleList::iterator maxItr + = max_element(triangles.begin(), triangles.end(), + CompareTriangle()); + triToAdd = &(*maxItr); + } + assert(triToAdd != 0 && triToAdd->score > 0.0); + // Add triangle vertices, and remove triangle from the + // vertices that use it. + triToAdd->score = -1.0f; + unsigned triToAddIdx = triToAdd - &triangles[0]; + for (unsigned i = 0; i < 3; ++i) + { + unsigned vertIdx = triToAdd->verts[i]; + Vertex* vert = &vertices[vertIdx]; + vertDrawList.push_back(vertIdx); + remove(vertTriListStore.begin() + vert->triList, + vertTriListStore.begin() + vert->triList + + vert->numActiveTris, + triToAddIdx); + vert->numActiveTris--; + } + // Assume that the three oldest cache entries will get kicked + // out, so reset their scores and those of their + // triangles. Otherwise we'll "lose" them and not be able to + // change their scores. + if (cache.maxSize - cache.entries.size() < 3) + { + for (vector::iterator itr = cache.entries.end() - 3, + end = cache.entries.end(); + itr != end; + ++itr) + { + vertices[*itr].cachePosition = -1; + vertices[*itr].score = findVertexScore(vertices[*itr]); + } + for (vector::iterator itr = cache.entries.end() - 3, + end = cache.entries.end(); + itr != end; + ++itr) + computeTriScores(vertices[*itr], vertices, triangles, + vertTriListStore); + } + cache.addEntries(&triToAdd->verts[0], &triToAdd->verts[3]); + for (vector::const_iterator itr = cache.entries.begin(), + end = cache.entries.end(); + itr != end; + ++itr) + { + unsigned vertIdx = *itr; + vertices[vertIdx].cachePosition = itr - cache.entries.begin(); + vertices[vertIdx].score = findVertexScore(vertices[vertIdx]); + } + } +} + +void VertexCacheVisitor::optimizeVertices() +{ + for(GeometryList::iterator itr=_geometryList.begin(); + itr!=_geometryList.end(); + ++itr) + { + optimizeVertices(*(*itr)); + } +} + +VertexCacheMissVisitor::VertexCacheMissVisitor(unsigned cacheSize) + : osg::NodeVisitor(NodeVisitor::TRAVERSE_ALL_CHILDREN), misses(0), + triangles(0), _cacheSize(cacheSize) +{ +} + +void VertexCacheMissVisitor::reset() +{ + misses = 0; + triangles = 0; +} + +void VertexCacheMissVisitor::apply(Geode& geode) +{ + for(unsigned int i = 0; i < geode.getNumDrawables(); ++i ) + { + osg::Geometry* geom = dynamic_cast(geode.getDrawable(i)); + if (geom) + doGeometry(*geom); + } +} + +namespace +{ +// The cache miss algorithm models an LRU cache because it results in an +// order that is insensitive to the actual cache size of the GPU. Real +// GPUs use a FIFO cache, so the statistics gatherer simulates that. +struct FIFOCache +{ + FIFOCache(size_t maxSize_) : maxSize(maxSize_) + { + entries.reserve(maxSize_); + } + vector entries; + size_t maxSize; + + // Add a list of values to the cache + void addEntries(unsigned* begin, unsigned* end) + { + // Make room for new cache entries + size_t newEnts = end - begin; + if (entries.size() < maxSize) + entries.resize(osg::minimum(entries.size() + newEnts, maxSize)); + vector::iterator copyEnd = entries.end() - newEnts; + copy_backward(entries.begin(), copyEnd, entries.end()); + copy(begin, end, entries.begin()); + } + + bool empty() + { + return entries.empty(); + } +}; + +// Insert vertices in a cache and record cache misses +struct CacheRecordOperator +{ + CacheRecordOperator() : cache(0), misses(0), triangles(0) {} + FIFOCache* cache; + unsigned misses; + unsigned triangles; + void operator()(unsigned p1, unsigned p2, unsigned p3) + { + unsigned verts[3]; + verts[0] = p1; + verts[1] = p2; + verts[2] = p3; + triangles++; + for (int i = 0; i < 3; ++i) + { + if (find(cache->entries.begin(), cache->entries.end(), verts[i]) + == cache->entries.end()) + misses++; + } + cache->addEntries(&verts[0], &verts[3]); + } +}; + +struct CacheRecorder : public TriangleIndexFunctor +{ + CacheRecorder(unsigned cacheSize) + { + cache = new FIFOCache(cacheSize); + } + + ~CacheRecorder() + { + delete cache; + } +}; +} + +void VertexCacheMissVisitor::doGeometry(Geometry& geom) +{ + Array* vertArray = geom.getVertexArray(); + if (!vertArray) + return; + Geometry::PrimitiveSetList& primSets = geom.getPrimitiveSetList(); + CacheRecorder recorder(_cacheSize); + for (Geometry::PrimitiveSetList::iterator itr = primSets.begin(), + end = primSets.end(); + itr != end; + ++itr) + { + (*itr)->accept(recorder); + } + misses += recorder.misses; + triangles += recorder.triangles; +} + +namespace +{ +// Move the values in an array to new positions, based on the +// remapping table. remapping[i] contains element i's new position, if +// any. Unlike RemapArray in TriStripVisitor, this code doesn't +// assume that elements only move downward in the array. +class Remapper : public osg::ArrayVisitor +{ +public: + static const unsigned invalidIndex; + Remapper(const vector& remapping) + : _remapping(remapping), _newsize(0) + { + for (vector::const_iterator itr = _remapping.begin(), + end = _remapping.end(); + itr != end; + ++itr) + if (*itr != invalidIndex) + ++_newsize; + } + + const vector& _remapping; + size_t _newsize; + + template + inline void remap(T& array) + { + ref_ptr newarray = new T(_newsize); + T* newptr = newarray.get(); + for (size_t i = 0; i < array.size(); ++i) + if (_remapping[i] != invalidIndex) + (*newptr)[_remapping[i]] = array[i]; + array.swap(*newptr); + + } + + virtual void apply(osg::Array&) {} + virtual void apply(osg::ByteArray& array) { remap(array); } + virtual void apply(osg::ShortArray& array) { remap(array); } + virtual void apply(osg::IntArray& array) { remap(array); } + virtual void apply(osg::UByteArray& array) { remap(array); } + virtual void apply(osg::UShortArray& array) { remap(array); } + virtual void apply(osg::UIntArray& array) { remap(array); } + virtual void apply(osg::Vec4ubArray& array) { remap(array); } + virtual void apply(osg::FloatArray& array) { remap(array); } + virtual void apply(osg::Vec2Array& array) { remap(array); } + virtual void apply(osg::Vec3Array& array) { remap(array); } + virtual void apply(osg::Vec4Array& array) { remap(array); } +}; + +const unsigned Remapper::invalidIndex = std::numeric_limits::max(); + +// Record the order in which vertices in a Geometry are used. +struct VertexReorderOperator +{ + unsigned seq; + vector remap; + + VertexReorderOperator() : seq(0) + { + } + + void inline doVertex(unsigned v) + { + if (remap[v] == Remapper::invalidIndex) + remap[v] = seq++; + } + void operator()(unsigned p1, unsigned p2, unsigned p3) + { + doVertex(p1); + doVertex(p2); + doVertex(p3); + } +}; + +struct VertexReorder : public TriangleIndexFunctor +{ + VertexReorder(unsigned numVerts) + { + remap.resize(numVerts, Remapper::invalidIndex); + } + +}; +} + +void VertexAccessOrderVisitor::optimizeOrder() +{ + for (GeometryList::iterator itr = _geometryList.begin(), end = _geometryList.end(); + itr != end; + ++itr) + { + optimizeOrder(*(*itr)); + } +} + +template +inline void reorderDrawElements(DE& drawElements, + const vector& reorder) +{ + for (typename DE::iterator itr = drawElements.begin(), end = drawElements.end(); + itr != end; + ++itr) + { + *itr = static_cast(reorder[*itr]); + } +} + +void VertexAccessOrderVisitor::optimizeOrder(Geometry& geom) +{ + Array* vertArray = geom.getVertexArray(); + if (!vertArray) + return; + Geometry::PrimitiveSetList& primSets = geom.getPrimitiveSetList(); + GeometryArrayGatherer gatherer(geom); + if (!gatherer._useDrawElements) + return; + VertexReorder vr(vertArray->getNumElements()); + for (Geometry::PrimitiveSetList::iterator itr = primSets.begin(), + end = primSets.end(); + itr != end; + ++itr) + { + PrimitiveSet* ps = itr->get(); + PrimitiveSet::Type type = ps->getType(); + if (type != PrimitiveSet::DrawElementsUBytePrimitiveType + && type != PrimitiveSet::DrawElementsUShortPrimitiveType + && type != PrimitiveSet::DrawElementsUIntPrimitiveType) + return; + ps->accept(vr); + } + Remapper remapper(vr.remap); + gatherer.accept(remapper); + for (Geometry::PrimitiveSetList::iterator itr = primSets.begin(), + end = primSets.end(); + itr != end; + ++itr) + { + PrimitiveSet* ps = itr->get(); + switch (ps->getType()) + { + case PrimitiveSet::DrawElementsUBytePrimitiveType: + reorderDrawElements(*static_cast(ps), vr.remap); + break; + case PrimitiveSet::DrawElementsUShortPrimitiveType: + reorderDrawElements(*static_cast(ps), vr.remap); + break; + case PrimitiveSet::DrawElementsUIntPrimitiveType: + reorderDrawElements(*static_cast(ps), vr.remap); + break; + default: + break; + } + } + geom.dirtyDisplayList(); +} +}