Hi Tim,
If I understand correctly how the sky dome mesh is constructed, there
was a lot of duplication of vertices in the triangle strip arrays, and
this has been carried forward into your indexed mesh approach. The
INDEX_MESH optimizer would remove these duplicates. The order of the
triangles in the output of INDEX_MESH should be the same as the input
order, but it might be tricky to pick corresponding triangles out of the
new mesh. Since this is such a regular mesh, the vertex cache optimizers
would make a small difference; however, you would totally lose the order
of the mesh.
Incidentally, I tried running the INDEX_MESH optimizer on the created
subgraph (at the end of the constructor in the file I attached in my
previous post) but it would crash in MyTriangleOperator::operator() - it
goes out of bounds on the _remapIndices list. The other two optimizers
also go out of bounds in similar ways.
Here's a modified Sphere.cpp with the code from the MeshOptimizers
simply copied into it (for simplicity of testing) if you want to have a
look.
I'm still not sure the order of the mesh is really important. I said
that before because it would have explained why the strips were arranged
like that, but I'm not sure now. So if I could get the INDEX_MESH
optimizer not to crash, I think using that and the other two (post/pre
transform) would probably work well. I could test it and see at least.
What was the actual performance difference?
With only the skydome in the scene, Draw went from about 0.45 to 0.4 on
my i7 920 + GTX 260. However it made the number of batches (draw calls)
go way down, of course - replacing 768 draw calls by 16 is good, but I
guess we could do better.
Thanks,
J-S
--
______________________________________________________
Jean-Sebastien Guay [email protected]
http://www.cm-labs.com/
http://whitestar02.webhop.org/
/*
-------------------------------------------------------------------------------
| osgEphemeris - Copyright (C) 2007 Don Burns |
| |
| This library is free software; you can redistribute it and/or modify |
| it under the terms of the GNU Lesser General Public License as published |
| by the Free Software Foundation; either version 3 of the License, or |
| (at your option) any later version. |
| |
| 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 GNU Lesser General Public |
| License for more details. |
| |
| You should have received a copy of the GNU Lesser General Public License |
| along with this software; if not, write to the Free Software Foundation, |
| Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA. |
| |
-------------------------------------------------------------------------------
*/
#include <osg/Geometry>
#include <osgEphemeris/Sphere.h>
#include <osgUtil/Optimizer>
#include <osg/TriangleIndexFunctor>
#include <algorithm>
#include <limits>
#include <cassert>
using namespace osgEphemeris;
namespace
{
// Optimization options that were added to osgUtil::Optimizer in 2.9.8+
// Note: We keep the same enum values so it stays consistent.
enum NewOptimizationOptions
{
INDEX_MESH = (1 << 18),
VERTEX_POSTTRANSFORM = (1 << 19),
VERTEX_PRETRANSFORM = (1 << 20),
};
// Helper that collects all the unique Geometry objects in a subgraph.
class GeometryCollector : public osgUtil::BaseOptimizerVisitor
{
public:
GeometryCollector(osgUtil::Optimizer* optimizer,
NewOptimizationOptions options)
: osgUtil::BaseOptimizerVisitor(optimizer, options) {}
void reset();
void apply(osg::Geode& geode);
typedef std::set<osg::Geometry*> 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 IndexMeshVisitor : public GeometryCollector
{
public:
IndexMeshVisitor(osgUtil::Optimizer* optimizer = 0)
: GeometryCollector(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 VertexCacheVisitor : public GeometryCollector
{
public:
VertexCacheVisitor(osgUtil::Optimizer* optimizer = 0)
: GeometryCollector(optimizer, VERTEX_POSTTRANSFORM)
{
}
void optimizeVertices(osg::Geometry& geom);
void optimizeVertices();
private:
void doVertexOptimization(osg::Geometry& geom,
std::vector<unsigned>& vertDrawList);
};
// Gather statistics on post-transform cache misses for geometry
class 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 VertexAccessOrderVisitor : public GeometryCollector
{
public:
VertexAccessOrderVisitor(osgUtil::Optimizer* optimizer = 0)
: GeometryCollector(optimizer, VERTEX_PRETRANSFORM)
{
}
void optimizeOrder();
void optimizeOrder(osg::Geometry& geom);
};
void GeometryCollector::reset()
{
_geometryList.clear();
}
void GeometryCollector::apply(osg::Geode& geode)
{
for(unsigned int i = 0; i < geode.getNumDrawables(); ++i )
{
osg::Geometry* geom =
dynamic_cast<osg::Geometry*>(geode.getDrawable(i));
if (geom) _geometryList.insert(geom);
}
}
namespace
{
typedef std::vector<unsigned int> 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<osg::Array*> 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;i<geometry.getNumTexCoordArrays();++i)
{
add(geometry.getTexCoordArray(i),osg::Geometry::BIND_PER_VERTEX);
}
for(i=0;i<geometry.getNumVertexAttribArrays();++i)
{
add(geometry.getVertexAttribArray(i),geometry.getVertexAttribBinding(i));
}
}
void add(osg::Array* array, osg::Geometry::AttributeBinding binding)
{
if (binding == osg::Geometry::BIND_PER_VERTEX)
{
if (array)
_arrayList.push_back(array);
}
else if (binding == osg::Geometry::BIND_PER_PRIMITIVE)
_useDrawElements = false;
}
void accept(osg::ArrayVisitor& av)
{
for(ArrayList::iterator itr=_arrayList.begin();
itr!=_arrayList.end();
++itr)
{
(*itr)->accept(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<class T>
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<MyTriangleOperator> MyTriangleIndexFunctor;
}
void IndexMeshVisitor::makeMesh(osg::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;
osg::Geometry::PrimitiveSetList& primitives = geom.getPrimitiveSetList();
osg::Geometry::PrimitiveSetList::iterator itr;
for(itr=primitives.begin();
itr!=primitives.end();
++itr)
{
switch((*itr)->getMode())
{
case(osg::PrimitiveSet::TRIANGLES):
case(osg::PrimitiveSet::TRIANGLE_STRIP):
case(osg::PrimitiveSet::TRIANGLE_FAN):
case(osg::PrimitiveSet::QUADS):
case(osg::PrimitiveSet::QUAD_STRIP):
case(osg::PrimitiveSet::POLYGON):
++numSurfacePrimitives;
break;
default:
// For now, only deal with polygons
return;
}
osg::PrimitiveSet::Type type = (*itr)->getType();
if (!(type == osg::PrimitiveSet::DrawElementsUBytePrimitiveType
|| type == osg::PrimitiveSet::DrawElementsUShortPrimitiveType
|| type == osg::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"<<std::endl;
geom.copyToAndOptimize(geom);
}
// compute duplicate vertices
typedef std::vector<unsigned int> IndexList;
unsigned int numVertices = geom.getVertexArray()->getNumElements();
IndexList indices(numVertices);
unsigned int i,j;
for(i=0;i<numVertices;++i)
{
indices[i] = i;
}
VertexAttribComparitor arrayComparitor(geom);
std::sort(indices.begin(),indices.end(),arrayComparitor);
unsigned int lastUnique = 0;
unsigned int numUnique = 1;
for(i=1;i<numVertices;++i)
{
if (arrayComparitor.compare(indices[lastUnique],indices[i]) != 0)
{
lastUnique = i;
++numUnique;
}
}
IndexList remapDuplicatesToOrignals(numVertices);
lastUnique = 0;
for(i=1;i<numVertices;++i)
{
if (arrayComparitor.compare(indices[lastUnique],indices[i])!=0)
{
// found a new vertex entry, so previous run of duplicates needs
// to be put together.
unsigned int min_index = indices[lastUnique];
for(j=lastUnique+1;j<i;++j)
{
min_index = osg::minimum(min_index,indices[j]);
}
for(j=lastUnique;j<i;++j)
{
remapDuplicatesToOrignals[indices[j]]=min_index;
}
lastUnique = i;
}
}
unsigned int min_index = indices[lastUnique];
for(j=lastUnique+1;j<i;++j)
{
min_index = osg::minimum(min_index,indices[j]);
}
for(j=lastUnique;j<i;++j)
{
remapDuplicatesToOrignals[indices[j]]=min_index;
}
// copy the arrays.
IndexList finalMapping(numVertices);
IndexList copyMapping;
copyMapping.reserve(numUnique);
unsigned int currentIndex=0;
for(i=0;i<numVertices;++i)
{
if (remapDuplicatesToOrignals[i]==i)
{
finalMapping[i] = currentIndex;
copyMapping.push_back(i);
currentIndex++;
}
}
for(i=0;i<numVertices;++i)
{
if (remapDuplicatesToOrignals[i]!=i)
{
finalMapping[i] = finalMapping[remapDuplicatesToOrignals[i]];
}
}
MyTriangleIndexFunctor taf;
taf._remapIndices.swap(finalMapping);
osg::Geometry::PrimitiveSetList new_primitives;
new_primitives.reserve(primitives.size());
for(itr=primitives.begin();
itr!=primitives.end();
++itr)
{
// For now we only have primitive sets that play nicely with
// the TriangleIndexFunctor.
(*itr)->accept(taf);
}
// remap any shared vertex attributes
RemapArray ra(copyMapping);
arrayComparitor.accept(ra);
if (taf._in_indices.size() < 65536)
{
osg::DrawElementsUShort* elements = new
osg::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 osg::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);
}
std::vector<unsigned> 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.
std::vector<unsigned>::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;
int spaceNeeded = newEnts - (entries.rend() - validEnd);
if (spaceNeeded > 0)
{
if (maxSize - entries.size() >= static_cast<unsigned>(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 std::vector<Vertex> VertexList;
struct Triangle
{
float score;
unsigned verts[3];
};
typedef std::vector<Triangle> 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<unsigned, float> TriangleScore;
TriangleScore computeTriScores(Vertex& vert, const VertexList& vertices,
TriangleList& triangles, std::vector<unsigned>&
triStore)
{
float bestScore = 0.0;
unsigned bestTri = 0;
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 std::make_pair(bestTri, bestScore);
}
typedef std::vector<Triangle> 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
osg::TriangleIndexFunctor<TriangleCounterOperator>
{
TriangleCounter(std::vector<Vertex>* vertices_)
{
vertices = vertices_;
}
};
// Initialize the vertex triangle lists and the triangle data structures
struct TriangleAddOperator
{
VertexList* vertices;
std::vector<unsigned>* 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 osg::TriangleIndexFunctor<TriangleAddOperator>
{
TriangleAdder(VertexList* vertices_, std::vector<unsigned>* 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(osg::Geometry& geom)
{
osg::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;
osg::Geometry::PrimitiveSetList& primSets = geom.getPrimitiveSetList();
for (osg::Geometry::PrimitiveSetList::iterator itr = primSets.begin(),
end = primSets.end();
itr != end;
++itr)
{
// Can only deal with polygons.
switch ((*itr)->getMode())
{
case(osg::PrimitiveSet::TRIANGLES):
case(osg::PrimitiveSet::TRIANGLE_STRIP):
case(osg::PrimitiveSet::TRIANGLE_FAN):
case(osg::PrimitiveSet::QUADS):
case(osg::PrimitiveSet::QUAD_STRIP):
case(osg::PrimitiveSet::POLYGON):
break;
default:
return;
}
osg::PrimitiveSet::Type type = (*itr)->getType();
if (type != osg::PrimitiveSet::DrawElementsUBytePrimitiveType
&& type != osg::PrimitiveSet::DrawElementsUShortPrimitiveType
&& type != osg::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
std::vector<unsigned> newVertList;
doVertexOptimization(geom, newVertList);
osg::Geometry::PrimitiveSetList newPrims;
if (vertArraySize < 65536)
{
osg::DrawElementsUShort* elements = new
osg::DrawElementsUShort(GL_TRIANGLES);
elements->reserve(newVertList.size());
for (std::vector<unsigned>::iterator itr = newVertList.begin(),
end = newVertList.end();
itr != end;
++itr)
elements->push_back((GLushort)*itr);
if (geom.getUseVertexBufferObjects())
{
elements->setElementBufferObject(new osg::ElementBufferObject);
}
newPrims.push_back(elements);
}
else
{
osg::DrawElementsUInt* elements
= new osg::DrawElementsUInt(GL_TRIANGLES, newVertList.begin(),
newVertList.end());
if (geom.getUseVertexBufferObjects())
{
elements->setElementBufferObject(new osg::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(osg::Geometry& geom,
std::vector<unsigned>&
vertDrawList)
{
osg::Geometry::PrimitiveSetList& primSets = geom.getPrimitiveSetList();
// lists for all the vertices and triangles
VertexList vertices;
TriangleList triangles;
TriangleCounter triCounter(&vertices);
for (osg::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
std::vector<unsigned> vertTriListStore(vertTrisSize);
TriangleAdder triAdder(&vertices, &vertTriListStore, &triangles);
for (osg::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 (std::vector<unsigned>::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_FP) << "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 (std::vector<unsigned>::iterator itr = cache.entries.end() - 3,
end = cache.entries.end();
itr != end;
++itr)
{
vertices[*itr].cachePosition = -1;
vertices[*itr].score = findVertexScore(vertices[*itr]);
}
for (std::vector<unsigned>::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 (std::vector<unsigned>::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(osg::Geode& geode)
{
for(unsigned int i = 0; i < geode.getNumDrawables(); ++i )
{
osg::Geometry* geom =
dynamic_cast<osg::Geometry*>(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_);
}
std::vector<unsigned> 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));
std::vector<unsigned>::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 osg::TriangleIndexFunctor<CacheRecordOperator>
{
CacheRecorder(unsigned cacheSize)
{
cache = new FIFOCache(cacheSize);
}
~CacheRecorder()
{
delete cache;
}
};
}
void VertexCacheMissVisitor::doGeometry(osg::Geometry& geom)
{
osg::Array* vertArray = geom.getVertexArray();
if (!vertArray)
return;
osg::Geometry::PrimitiveSetList& primSets = geom.getPrimitiveSetList();
CacheRecorder recorder(_cacheSize);
for (osg::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 std::vector<unsigned>& remapping)
: _remapping(remapping), _newsize(0)
{
for (std::vector<unsigned>::const_iterator itr = _remapping.begin(),
end = _remapping.end();
itr != end;
++itr)
if (*itr != invalidIndex)
++_newsize;
}
const std::vector<unsigned>& _remapping;
size_t _newsize;
template<class T>
inline void remap(T& array)
{
osg::ref_ptr<T> 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<unsigned>::max();
// Record the order in which vertices in a Geometry are used.
struct VertexReorderOperator
{
unsigned seq;
std::vector<unsigned> 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 osg::TriangleIndexFunctor<VertexReorderOperator>
{
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<typename DE>
inline void reorderDrawElements(DE& drawElements,
const std::vector<unsigned>& reorder)
{
for (typename DE::iterator itr = drawElements.begin(), end =
drawElements.end();
itr != end;
++itr)
{
*itr = static_cast<typename DE::value_type>(reorder[*itr]);
}
}
void VertexAccessOrderVisitor::optimizeOrder(osg::Geometry& geom)
{
osg::Array* vertArray = geom.getVertexArray();
if (!vertArray)
return;
osg::Geometry::PrimitiveSetList& primSets = geom.getPrimitiveSetList();
GeometryArrayGatherer gatherer(geom);
if (!gatherer._useDrawElements)
return;
VertexReorder vr(vertArray->getNumElements());
for (osg::Geometry::PrimitiveSetList::iterator itr = primSets.begin(),
end = primSets.end();
itr != end;
++itr)
{
osg::PrimitiveSet* ps = itr->get();
osg::PrimitiveSet::Type type = ps->getType();
if (type != osg::PrimitiveSet::DrawElementsUBytePrimitiveType
&& type != osg::PrimitiveSet::DrawElementsUShortPrimitiveType
&& type != osg::PrimitiveSet::DrawElementsUIntPrimitiveType)
return;
ps->accept(vr);
}
Remapper remapper(vr.remap);
gatherer.accept(remapper);
for (osg::Geometry::PrimitiveSetList::iterator itr = primSets.begin(),
end = primSets.end();
itr != end;
++itr)
{
osg::PrimitiveSet* ps = itr->get();
switch (ps->getType())
{
case osg::PrimitiveSet::DrawElementsUBytePrimitiveType:
reorderDrawElements(*static_cast<osg::DrawElementsUByte*>(ps),
vr.remap);
break;
case osg::PrimitiveSet::DrawElementsUShortPrimitiveType:
reorderDrawElements(*static_cast<osg::DrawElementsUShort*>(ps),
vr.remap);
break;
case osg::PrimitiveSet::DrawElementsUIntPrimitiveType:
reorderDrawElements(*static_cast<osg::DrawElementsUInt*>(ps),
vr.remap);
break;
default:
break;
}
}
geom.dirtyDisplayList();
}
}
const double Sphere::_defaultRadius = 3476000.0 * 0.5; // diameter of moon
* 0.5 = radius of moon
Sphere::Sphere( double radius,
Sphere::TesselationResolution tr,
Sphere::Orientation orientation,
Sphere::Hemisphere whichHemisphere,
bool stc
)
{
_skyTexCoords = stc;
unsigned int nsectors = 4;
double latStep =
( tr == TessHigh ) ? 1.875 :
( tr == TessLow ) ? 15 : 7.5;
osg::ref_ptr<osg::Vec3Array> v = new osg::Vec3Array;
int R = 0;
for( unsigned int sector = 0; sector < nsectors; sector++ )
{
double off = double(sector) * 360.0/(double)(nsectors);
int div = 1;
v->push_back( osg::Vec3(0,0,radius));
for( double lat = latStep; lat <= 91.0; lat += latStep )
{
double dd = (360.0/double(nsectors))/(double)(div);
for( int i = 0; i <= div; i++ )
{
double lon = off + double(i) * dd;
double x = radius * cos(osg::DegreesToRadians(lon)) *
sin(osg::DegreesToRadians(lat));
double y = radius * sin(osg::DegreesToRadians(lon)) *
sin(osg::DegreesToRadians(lat));
double z = radius * cos(osg::DegreesToRadians(lat));
v->push_back( osg::Vec3(x,y,z));
}
div++;
if( sector == 0 )
R++;
}
}
for( int hemisphere = 0; hemisphere < 2; hemisphere++ )
{
if( !((1<<hemisphere) & whichHemisphere) )
continue;
osg::Geode *geode = new osg::Geode;
int iii = 0;
osg::ref_ptr<osg::Vec3Array> coords = new osg::Vec3Array;
osg::ref_ptr<osg::Vec3Array> normals = new osg::Vec3Array;
osg::ref_ptr<osg::Vec2Array> tcoords = new osg::Vec2Array;
for( unsigned int sector = 0; sector < nsectors; sector++ )
{
int len = 3;
int ii[] = { 1, 0 };
int toggle = 0;
for( int j = 0; j < R; j++ )
{
osg::ref_ptr<osg::Vec3Array> tarray = new osg::Vec3Array;
for( int i = 0; i < len; i++ )
{
int index = iii + ii[toggle];
tarray->push_back( (*v)[index] );
ii[toggle]++;
toggle = 1 - toggle;
}
if( hemisphere == 0 )
{
if( orientation == InnerOrientation )
{
for( unsigned int n = 0; n < tarray->size(); n++ )
{
osg::Vec3 v = (*tarray)[n];
coords->push_back( v );
v.normalize();
v *= -1;
normals->push_back( v );
tcoords->push_back( makeTexCoord(v, sector) );
}
}
else
{
for( int n = tarray->size() - 1; n >= 0 ; n-- )
{
osg::Vec3 v = (*tarray)[n];
coords->push_back( v );
v.normalize();
normals->push_back( v );
tcoords->push_back( makeTexCoord(v, sector) );
}
}
}
else
{
if( orientation == InnerOrientation )
{
for( int n = tarray->size() - 1; n >= 0 ; n-- )
{
osg::Vec3 v = (*tarray)[n];
v[2] *= -1.0;
coords->push_back( v );
v.normalize();
v *= -1;
normals->push_back( v );
tcoords->push_back( makeTexCoord(v, sector) );
}
}
else
{
for( unsigned int n = 0; n < tarray->size(); n++ )
{
osg::Vec3 v = (*tarray)[n];
v[2] *= -1.0;
coords->push_back( v );
v.normalize();
normals->push_back( v );
tcoords->push_back( makeTexCoord(v, sector) );
}
}
}
toggle = 1 - toggle;
len += 2;
}
iii += ii[0];
}
int index = 0;
for( unsigned int sector = 0; sector < nsectors; sector++ )
{
osg::ref_ptr<osg::Vec4Array> colors = new osg::Vec4Array;
colors->push_back( osg::Vec4( 1.0, 1.0, 1.0,1.0 ));
osg::ref_ptr<osg::Geometry> geometry = new osg::Geometry;
geometry->setVertexArray( coords.get() );
geometry->setTexCoordArray( 0, tcoords.get() );
geometry->setNormalArray( normals.get() );
geometry->setNormalBinding( osg::Geometry::BIND_PER_VERTEX );
geometry->setColorArray( colors.get() );
geometry->setColorBinding( osg::Geometry::BIND_OVERALL );
int len = 3;
for( int i = 0; i < R; i++ )
{
geometry->addPrimitiveSet( new
osg::DrawArrays(osg::PrimitiveSet::TRIANGLE_STRIP, index, len ));
index += len;
len += 2;
}
geode->addDrawable( geometry.get() );
}
if( hemisphere == 0 )
{
_northernHemisphere = geode;
addChild( _northernHemisphere.get() );
}
else
{
_southernHemisphere = geode;
addChild( _southernHemisphere.get() );
}
}
osgUtil::Optimizer optimizer;
IndexMeshVisitor imv(&optimizer);
this->accept(imv);
imv.makeMesh();
VertexCacheVisitor vcv;
this->accept(vcv);
vcv.optimizeVertices();
VertexAccessOrderVisitor vaov;
this->accept(vaov);
vaov.optimizeOrder();
}
osg::Vec2 Sphere::makeTexCoord(osg::Vec3 &normal, unsigned int sector)
{
double s = 0.0;
{
double a = atan2( normal[1], normal[0] );
if( a < 0.0 )
a += osg::PI*2;
a /= (2*osg::PI);
// Prevent wrapping of texcoord, which creates ugly seam
if(sector == 2 && a > 0.999)
a = 0.0;
s = a;
}
double t;
if( _skyTexCoords )
t = (1.0 + ((asin(normal[2]))/(osg::PI_2)));
else
t = (0.5 + ((asin(normal[2]))/(osg::PI)));
return osg::Vec2( s, t );
}
double Sphere::getDefaultRadius()
{
return _defaultRadius;
}
SphereLOD::SphereLOD( double radius,
Sphere::Orientation orientation,
Sphere::Hemisphere hemisphere )
{
addChild( new Sphere( radius, Sphere::TessHigh, orientation, hemisphere ) );
addChild( new Sphere( radius, Sphere::TessNormal, orientation, hemisphere )
);
addChild( new Sphere( radius, Sphere::TessLow, orientation, hemisphere ) );
setRange( 0, 0.0, 10*radius );
setRange( 1, 10*radius, 50*radius );
setRange( 2, 50*radius, 1e12*radius );
}
_______________________________________________
osg-users mailing list
[email protected]
http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org
