root/OpenSceneGraph/trunk/src/osgUtil/MeshOptimizers.cpp @ 13041

Revision 13041, 36.1 kB (checked in by robert, 2 years ago)

Ran script to remove trailing spaces and tabs

  • Property svn:eol-style set to native
Line 
1/* -*-c++-*- OpenSceneGraph - Copyright (C) 1998-2006 Robert Osfield
2 * Copyright (C) 2010 Tim Moore
3 *
4 * This library is open source and may be redistributed and/or modified under
5 * the terms of the OpenSceneGraph Public License (OSGPL) version 0.0 or
6 * (at your option) any later version.  The full license is in LICENSE file
7 * included with this distribution, and on the openscenegraph.org website.
8 *
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12 * OpenSceneGraph Public License for more details.
13*/
14
15#include <cassert>
16#include <limits>
17
18#include <algorithm>
19#include <utility>
20#include <vector>
21
22#include <iostream>
23
24#include <osg/Geometry>
25#include <osg/Math>
26#include <osg/PrimitiveSet>
27#include <osg/TriangleIndexFunctor>
28
29#include <osgUtil/MeshOptimizers>
30
31using namespace std;
32using namespace osg;
33
34namespace osgUtil
35{
36
37void GeometryCollector::reset()
38{
39    _geometryList.clear();
40}
41
42void GeometryCollector::apply(Geode& geode)
43{
44    for(unsigned int i = 0; i < geode.getNumDrawables(); ++i )
45    {
46        osg::Geometry* geom = dynamic_cast<osg::Geometry*>(geode.getDrawable(i));
47        if (geom) _geometryList.insert(geom);
48    }
49}
50
51namespace
52{
53typedef std::vector<unsigned int> IndexList;
54
55// A helper class that gathers up all the attribute arrays of an
56// osg::Geometry object that are BIND_PER_VERTEX and runs an
57// ArrayVisitor on them.
58struct GeometryArrayGatherer
59{
60    typedef std::vector<osg::Array*> ArrayList;
61
62    GeometryArrayGatherer(osg::Geometry& geometry)
63        : _useDrawElements(true)
64    {
65        add(geometry.getVertexArray(),osg::Geometry::BIND_PER_VERTEX);
66        add(geometry.getNormalArray(),geometry.getNormalBinding());
67        add(geometry.getColorArray(),geometry.getColorBinding());
68        add(geometry.getSecondaryColorArray(),geometry.getSecondaryColorBinding());
69        add(geometry.getFogCoordArray(),geometry.getFogCoordBinding());
70        unsigned int i;
71        for(i=0;i<geometry.getNumTexCoordArrays();++i)
72        {
73            add(geometry.getTexCoordArray(i),osg::Geometry::BIND_PER_VERTEX);
74        }
75        for(i=0;i<geometry.getNumVertexAttribArrays();++i)
76        {
77            add(geometry.getVertexAttribArray(i),geometry.getVertexAttribBinding(i));
78        }
79    }
80
81    void add(osg::Array* array, osg::Geometry::AttributeBinding binding)
82    {
83        if (binding == osg::Geometry::BIND_PER_VERTEX)
84        {
85            if (array)
86                _arrayList.push_back(array);
87        }
88        else if (binding == osg::Geometry::BIND_PER_PRIMITIVE)
89            _useDrawElements = false;
90    }
91
92    void accept(osg::ArrayVisitor& av)
93    {
94        for(ArrayList::iterator itr=_arrayList.begin();
95            itr!=_arrayList.end();
96            ++itr)
97        {
98            (*itr)->accept(av);
99        }
100    }
101
102    ArrayList _arrayList;
103    // True if geometry contains bindings that are compatible with
104    // DrawElements.
105    bool _useDrawElements;
106};
107
108// Compare vertices in a mesh using all their attributes. The vertices
109// are identified by their index. Extracted from TriStripVisitor.cpp
110struct VertexAttribComparitor : public GeometryArrayGatherer
111{
112    VertexAttribComparitor(osg::Geometry& geometry)
113        : GeometryArrayGatherer(geometry)
114    {
115    }
116
117    bool operator() (unsigned int lhs, unsigned int rhs) const
118    {
119        for(ArrayList::const_iterator itr=_arrayList.begin();
120            itr!=_arrayList.end();
121            ++itr)
122        {
123            int compare = (*itr)->compare(lhs,rhs);
124            if (compare==-1) return true;
125            if (compare==1) return false;
126        }
127        return false;
128    }
129
130    int compare(unsigned int lhs, unsigned int rhs)
131    {
132        for(ArrayList::iterator itr=_arrayList.begin();
133            itr!=_arrayList.end();
134            ++itr)
135        {
136            int compare = (*itr)->compare(lhs,rhs);
137            if (compare==-1) return -1;
138            if (compare==1) return 1;
139        }
140        return 0;
141    }
142
143protected:
144    VertexAttribComparitor& operator = (const VertexAttribComparitor&) { return *this; }
145
146};
147
148// Compact the vertex attribute arrays. Also stolen from TriStripVisitor
149class RemapArray : public osg::ArrayVisitor
150{
151    public:
152        RemapArray(const IndexList& remapping):_remapping(remapping) {}
153
154        const IndexList& _remapping;
155
156        template<class T>
157        inline void remap(T& array)
158        {
159            for(unsigned int i=0;i<_remapping.size();++i)
160            {
161                if (i!=_remapping[i])
162                {
163                    array[i] = array[_remapping[i]];
164                }
165            }
166            array.erase(array.begin()+_remapping.size(),array.end());
167        }
168
169        virtual void apply(osg::Array&) {}
170        virtual void apply(osg::ByteArray& array) { remap(array); }
171        virtual void apply(osg::ShortArray& array) { remap(array); }
172        virtual void apply(osg::IntArray& array) { remap(array); }
173        virtual void apply(osg::UByteArray& array) { remap(array); }
174        virtual void apply(osg::UShortArray& array) { remap(array); }
175        virtual void apply(osg::UIntArray& array) { remap(array); }
176        virtual void apply(osg::FloatArray& array) { remap(array); }
177        virtual void apply(osg::DoubleArray& array) { remap(array); }
178
179        virtual void apply(osg::Vec2Array& array) { remap(array); }
180        virtual void apply(osg::Vec3Array& array) { remap(array); }
181        virtual void apply(osg::Vec4Array& array) { remap(array); }
182
183        virtual void apply(osg::Vec4ubArray& array) { remap(array); }
184
185        virtual void apply(osg::Vec2bArray& array) { remap(array); }
186        virtual void apply(osg::Vec3bArray& array) { remap(array); }
187        virtual void apply(osg::Vec4bArray& array) { remap(array); }
188
189        virtual void apply(osg::Vec2sArray& array) { remap(array); }
190        virtual void apply(osg::Vec3sArray& array) { remap(array); }
191        virtual void apply(osg::Vec4sArray& array) { remap(array); }
192
193        virtual void apply(osg::Vec2dArray& array) { remap(array); }
194        virtual void apply(osg::Vec3dArray& array) { remap(array); }
195        virtual void apply(osg::Vec4dArray& array) { remap(array); }
196
197        virtual void apply(osg::MatrixfArray& array) { remap(array); }
198protected:
199
200        RemapArray& operator = (const RemapArray&) { return *this; }
201};
202
203
204// Construct an index list of triangles for DrawElements for any input
205// primitives.
206struct MyTriangleOperator
207{
208
209    IndexList _remapIndices;
210    IndexList _in_indices;
211
212    inline void operator()(unsigned int p1, unsigned int p2, unsigned int p3)
213    {
214        if (_remapIndices.empty())
215        {
216            _in_indices.push_back(p1);
217            _in_indices.push_back(p2);
218            _in_indices.push_back(p3);
219        }
220        else
221        {
222            _in_indices.push_back(_remapIndices[p1]);
223            _in_indices.push_back(_remapIndices[p2]);
224            _in_indices.push_back(_remapIndices[p3]);
225        }
226    }
227
228};
229typedef osg::TriangleIndexFunctor<MyTriangleOperator> MyTriangleIndexFunctor;
230}
231
232void IndexMeshVisitor::makeMesh(Geometry& geom)
233{
234        if (geom.getNormalBinding()==osg::Geometry::BIND_PER_PRIMITIVE ||
235        geom.getNormalBinding()==osg::Geometry::BIND_PER_PRIMITIVE_SET) return;
236
237    if (geom.getColorBinding()==osg::Geometry::BIND_PER_PRIMITIVE ||
238        geom.getColorBinding()==osg::Geometry::BIND_PER_PRIMITIVE_SET) return;
239
240    if (geom.getSecondaryColorBinding()==osg::Geometry::BIND_PER_PRIMITIVE ||
241        geom.getSecondaryColorBinding()==osg::Geometry::BIND_PER_PRIMITIVE_SET) return;
242
243    if (geom.getFogCoordBinding()==osg::Geometry::BIND_PER_PRIMITIVE ||
244        geom.getFogCoordBinding()==osg::Geometry::BIND_PER_PRIMITIVE_SET) return;
245
246    // no point optimizing if we don't have enough vertices.
247    if (!geom.getVertexArray() || geom.getVertexArray()->getNumElements()<3) return;
248
249    // check for the existence of surface primitives
250    unsigned int numSurfacePrimitives = 0;
251    unsigned int numNonIndexedPrimitives = 0;
252    Geometry::PrimitiveSetList& primitives = geom.getPrimitiveSetList();
253    Geometry::PrimitiveSetList::iterator itr;
254    for(itr=primitives.begin();
255        itr!=primitives.end();
256        ++itr)
257    {
258        switch((*itr)->getMode())
259        {
260            case(PrimitiveSet::TRIANGLES):
261            case(PrimitiveSet::TRIANGLE_STRIP):
262            case(PrimitiveSet::TRIANGLE_FAN):
263            case(PrimitiveSet::QUADS):
264            case(PrimitiveSet::QUAD_STRIP):
265            case(PrimitiveSet::POLYGON):
266                ++numSurfacePrimitives;
267                break;
268            default:
269                // For now, only deal with polygons
270                return;
271        }
272        PrimitiveSet::Type type = (*itr)->getType();
273        if (!(type == PrimitiveSet::DrawElementsUBytePrimitiveType
274              || type == PrimitiveSet::DrawElementsUShortPrimitiveType
275              || type == PrimitiveSet::DrawElementsUIntPrimitiveType))
276            numNonIndexedPrimitives++;
277    }
278
279    // nothing to index
280    if (!numSurfacePrimitives || !numNonIndexedPrimitives) return;
281
282    // check to see if vertex attributes indices exists, if so expand them to remove them
283    if (geom.suitableForOptimization())
284    {
285        // removing coord indices
286        OSG_INFO<<"TriStripVisitor::stripify(Geometry&): Removing attribute indices"<<std::endl;
287        geom.copyToAndOptimize(geom);
288    }
289
290
291    // compute duplicate vertices
292
293    typedef std::vector<unsigned int> IndexList;
294    unsigned int numVertices = geom.getVertexArray()->getNumElements();
295    IndexList indices(numVertices);
296    unsigned int i,j;
297    for(i=0;i<numVertices;++i)
298    {
299        indices[i] = i;
300    }
301
302    VertexAttribComparitor arrayComparitor(geom);
303    std::sort(indices.begin(),indices.end(),arrayComparitor);
304
305    unsigned int lastUnique = 0;
306    unsigned int numUnique = 1;
307    for(i=1;i<numVertices;++i)
308    {
309        if (arrayComparitor.compare(indices[lastUnique],indices[i]) != 0)
310        {
311            lastUnique = i;
312            ++numUnique;
313        }
314
315    }
316    IndexList remapDuplicatesToOrignals(numVertices);
317    lastUnique = 0;
318    for(i=1;i<numVertices;++i)
319    {
320        if (arrayComparitor.compare(indices[lastUnique],indices[i])!=0)
321        {
322            // found a new vertex entry, so previous run of duplicates needs
323            // to be put together.
324            unsigned int min_index = indices[lastUnique];
325            for(j=lastUnique+1;j<i;++j)
326            {
327                min_index = osg::minimum(min_index,indices[j]);
328            }
329            for(j=lastUnique;j<i;++j)
330            {
331                remapDuplicatesToOrignals[indices[j]]=min_index;
332            }
333            lastUnique = i;
334        }
335
336    }
337    unsigned int min_index = indices[lastUnique];
338    for(j=lastUnique+1;j<i;++j)
339    {
340        min_index = osg::minimum(min_index,indices[j]);
341    }
342    for(j=lastUnique;j<i;++j)
343    {
344        remapDuplicatesToOrignals[indices[j]]=min_index;
345    }
346
347
348    // copy the arrays.
349    IndexList finalMapping(numVertices);
350    IndexList copyMapping;
351    copyMapping.reserve(numUnique);
352    unsigned int currentIndex=0;
353    for(i=0;i<numVertices;++i)
354    {
355        if (remapDuplicatesToOrignals[i]==i)
356        {
357            finalMapping[i] = currentIndex;
358            copyMapping.push_back(i);
359            currentIndex++;
360        }
361    }
362
363    for(i=0;i<numVertices;++i)
364    {
365        if (remapDuplicatesToOrignals[i]!=i)
366        {
367            finalMapping[i] = finalMapping[remapDuplicatesToOrignals[i]];
368        }
369    }
370
371
372    MyTriangleIndexFunctor taf;
373    taf._remapIndices.swap(finalMapping);
374
375    Geometry::PrimitiveSetList new_primitives;
376    new_primitives.reserve(primitives.size());
377
378    for(itr=primitives.begin();
379        itr!=primitives.end();
380        ++itr)
381    {
382        // For now we only have primitive sets that play nicely with
383        // the TriangleIndexFunctor.
384        (*itr)->accept(taf);
385    }
386
387    // remap any shared vertex attributes
388    RemapArray ra(copyMapping);
389    arrayComparitor.accept(ra);
390    if (taf._in_indices.size() < 65536)
391    {
392        osg::DrawElementsUShort* elements = new DrawElementsUShort(GL_TRIANGLES);
393        for (IndexList::iterator itr = taf._in_indices.begin(),
394                 end = taf._in_indices.end();
395             itr != end;
396            ++itr)
397        {
398            elements->push_back((GLushort)(*itr));
399        }
400        new_primitives.push_back(elements);
401    }
402    else
403    {
404        osg::DrawElementsUInt* elements
405            = new DrawElementsUInt(GL_TRIANGLES, taf._in_indices.begin(),
406                                   taf._in_indices.end());
407        new_primitives.push_back(elements);
408    }
409    geom.setPrimitiveSetList(new_primitives);
410}
411
412void IndexMeshVisitor::makeMesh()
413{
414    for(GeometryList::iterator itr=_geometryList.begin();
415        itr!=_geometryList.end();
416        ++itr)
417    {
418        makeMesh(*(*itr));
419    }
420}
421
422namespace
423{
424// A simulation of a Least Recently Used cache. Position in the cache
425// corresponds to when the vertex was used i.e., 0 is the most
426// recently used.
427struct LRUCache
428{
429    LRUCache(size_t maxSize_) : maxSize(maxSize_)
430    {
431        entries.reserve(maxSize_ + 3);
432    }
433    vector<unsigned> entries;
434    size_t maxSize;
435
436    // Add a list of values to the cache
437    void addEntries(unsigned* begin, unsigned* end)
438    {
439        // If any of the new vertices are already in the cache, remove
440        // them, leaving some room at the front of the cache.
441        vector<unsigned>::reverse_iterator validEnd = entries.rend();
442        for (unsigned* pent = begin; pent != end; ++pent)
443        {
444            validEnd = remove(entries.rbegin(), validEnd, *pent);
445        }
446        // Now make room still needed for new cache entries
447        size_t newEnts = end - begin;
448        int spaceNeeded = newEnts - (entries.rend() - validEnd);
449        if (spaceNeeded > 0)
450        {
451            if (maxSize - entries.size() >= static_cast<unsigned>(spaceNeeded))
452                entries.resize(entries.size() + spaceNeeded);
453            else if (entries.size() < maxSize)
454                entries.resize(maxSize);
455            copy_backward(entries.begin() + newEnts - spaceNeeded,
456                          entries.end() - spaceNeeded, entries.end());
457        }
458        copy(begin, end, entries.begin());
459    }
460
461    bool empty()
462    {
463        return entries.empty();
464    }
465};
466
467// A list of triangles that use a vertex is associated with the Vertex
468// structure in another array.
469struct Vertex
470{
471    int cachePosition;
472    float score;
473    int trisUsing;
474    int numActiveTris;          // triangles left to process
475    size_t triList;             // index to start of triangle storage
476    Vertex()
477        : cachePosition(-1), score(0.0f), trisUsing(0), numActiveTris(0), triList(0)
478    {
479    }
480};
481
482// Code from Tom Forsyth's article. The algorithm is described in
483// detail at
484// http://home.comcast.net/~tom_forsyth/papers/fast_vert_cache_opt.html.
485// In summary, vertices are assigned a score based on the number of
486// triangles that use it (valence) and the vertex's position in the
487// model of the vertex cache, if any. Triangles are also given a
488// score, which is the sum of the scores of its vertices. The triangle
489// with the best score is added to the draw list, its vertices are
490// added and / or moved in the cache, the scores of vertices in the
491// cache and ejected from the cache are updated. Then the scores of
492// triangles that use those vertices are updated.
493//
494// Unless the cache is empty, the "best" triangle is found by
495// searching triangles that use vertices in the cache, not the whole
496// mesh. This keeps the algorithm running in time proportional to the
497// size of the mesh.
498
499// The "magic" scoring functions are described in the paper.
500const float cacheDecayPower = 1.5f;
501const float lastTriScore = 0.75f;
502const float valenceBoostScale = 2.0f;
503const float valenceBoostPower = 0.5f;
504
505const int maxCacheSize = 32;
506
507float findVertexScore (Vertex& vert)
508{
509
510    if (vert.numActiveTris == 0)
511    {
512        // No tri needs this vertex!
513        return -1.0f;
514    }
515    float score = 0.0f;
516    int cachePosition = vert.cachePosition;
517
518    if (cachePosition < 0)
519    {
520        // Vertex is not in FIFO cache - no score.
521    }
522    else
523    {
524        if (cachePosition < 3)
525        {
526            // This vertex was used in the last triangle,
527            // so it has a fixed score, whichever of the three
528            // it's in. Otherwise, you can get very different
529            // answers depending on whether you add
530            // the triangle 1,2,3 or 3,1,2 - which is silly.
531            score = lastTriScore;
532        }
533        else
534        {
535            assert (cachePosition < maxCacheSize);
536            // Points for being high in the cache.
537            const float scaler = 1.0f / (maxCacheSize - 3);
538            score = 1.0f - (cachePosition - 3 ) * scaler;
539            score = powf(score, cacheDecayPower);
540        }
541    }
542    // Bonus points for having a low number of tris still to
543    // use the vert, so we get rid of lone verts quickly.
544    float valenceBoost = powf(vert.numActiveTris, -valenceBoostPower);
545    score += valenceBoostScale * valenceBoost;
546    return score;
547}
548
549
550typedef vector<Vertex> VertexList;
551
552struct Triangle
553{
554    float score;
555    unsigned verts[3];
556};
557
558typedef vector<Triangle> TriangleList;
559
560inline float findTriangleScore(Triangle& tri, const VertexList& vertices)
561{
562    float result = 0.0f;
563    for (int i = 0; i < 3; ++i)
564        result += vertices[tri.verts[i]].score;
565    return result;
566}
567
568typedef std::pair<unsigned, float> TriangleScore;
569
570TriangleScore computeTriScores(Vertex& vert, const VertexList& vertices,
571                               TriangleList& triangles, vector<unsigned>& triStore)
572{
573    float bestScore = 0.0;
574    unsigned bestTri = 0;
575    for (size_t i = vert.triList;
576         i < vert.triList + vert.numActiveTris;
577         ++i)
578    {
579        unsigned tri = triStore[i];
580        float score = triangles[tri].score = findTriangleScore(triangles[tri],
581                                                               vertices);
582        if (score > bestScore)
583        {
584            bestScore = score;
585            bestTri = tri;
586        }
587    }
588    return make_pair(bestTri, bestScore);
589}
590
591typedef vector<Triangle> TriangleList;
592
593struct TriangleCounterOperator
594{
595    VertexList* vertices;
596    int triangleCount;
597    TriangleCounterOperator() : vertices(0), triangleCount(0) {}
598
599    void doVertex(unsigned p)
600    {
601        if (vertices->size() <= p)
602            vertices->resize(p + 1);
603        (*vertices)[p].trisUsing++;
604    }
605
606    void operator() (unsigned int p1, unsigned int p2, unsigned int p3)
607    {
608        if (p1 == p2 || p2 == p3 || p1 == p3)
609            return;
610        doVertex(p1);
611        doVertex(p2);
612        doVertex(p3);
613        triangleCount++;
614    }
615};
616
617struct TriangleCounter : public TriangleIndexFunctor<TriangleCounterOperator>
618{
619    TriangleCounter(vector<Vertex>* vertices_)
620    {
621        vertices = vertices_;
622    }
623};
624
625// Initialize the vertex triangle lists and the triangle data structures
626struct TriangleAddOperator
627{
628    VertexList* vertices;
629    vector<unsigned>* vertexTris;
630    TriangleList* triangles;
631    int triIdx;
632    TriangleAddOperator() : vertices(0), triIdx(0) {}
633
634    void doVertex(unsigned p)
635    {
636        (*vertexTris)[(*vertices)[p].triList + (*vertices)[p].numActiveTris++]
637            = triIdx;
638    }
639
640    void operator() (unsigned int p1, unsigned int p2, unsigned int p3)
641    {
642        if (p1 == p2 || p2 == p3 || p1 == p3)
643            return;
644        doVertex(p1);
645        doVertex(p2);
646        doVertex(p3);
647    (*triangles)[triIdx].verts[0] = p1;
648    (*triangles)[triIdx].verts[1] = p2;
649    (*triangles)[triIdx].verts[2] = p3;
650    triIdx++;
651    }
652};
653
654struct TriangleAdder : public TriangleIndexFunctor<TriangleAddOperator>
655{
656    TriangleAdder(VertexList* vertices_, vector<unsigned>* vertexTris_,
657                  TriangleList* triangles_)
658    {
659        vertices = vertices_;
660        vertexTris = vertexTris_;
661        triangles = triangles_;
662    }
663};
664
665struct CompareTriangle
666{
667    bool operator()(const Triangle& lhs, const Triangle& rhs)
668    {
669        return lhs.score < rhs.score;
670    }
671};
672}
673
674void VertexCacheVisitor::optimizeVertices(Geometry& geom)
675{
676    Array* vertArray = geom.getVertexArray();
677    if (!vertArray)
678        return;
679    unsigned vertArraySize = vertArray->getNumElements();
680    // If all the vertices fit in the cache, there's no point in
681    // doing this optimization.
682    if (vertArraySize <= 16)
683        return;
684    Geometry::PrimitiveSetList& primSets = geom.getPrimitiveSetList();
685    for (Geometry::PrimitiveSetList::iterator itr = primSets.begin(),
686             end = primSets.end();
687         itr != end;
688         ++itr)
689    {
690        // Can only deal with polygons.
691        switch ((*itr)->getMode())
692        {
693        case(PrimitiveSet::TRIANGLES):
694        case(PrimitiveSet::TRIANGLE_STRIP):
695        case(PrimitiveSet::TRIANGLE_FAN):
696        case(PrimitiveSet::QUADS):
697        case(PrimitiveSet::QUAD_STRIP):
698        case(PrimitiveSet::POLYGON):
699            break;
700        default:
701            return;
702        }
703        PrimitiveSet::Type type = (*itr)->getType();
704        if (type != PrimitiveSet::DrawElementsUBytePrimitiveType
705            && type != PrimitiveSet::DrawElementsUShortPrimitiveType
706            && type != PrimitiveSet::DrawElementsUIntPrimitiveType)
707            return;
708    }
709#if 0
710    VertexCacheMissVisitor missv;
711    missv.doGeometry(geom);
712    cout << "Before optimization: misses: " << missv.misses
713         << " triangles: " << missv.triangles << " acmr: ";
714    if (missv.triangles > 0.0)
715        cout << (double)missv.misses / (double)missv.triangles << "\n";
716    else
717        cout << "0.0\n";
718    missv.reset();
719#endif
720    vector<unsigned> newVertList;
721    doVertexOptimization(geom, newVertList);
722    Geometry::PrimitiveSetList newPrims;
723    if (vertArraySize < 65536)
724    {
725        osg::DrawElementsUShort* elements = new DrawElementsUShort(GL_TRIANGLES);
726        elements->reserve(newVertList.size());
727        for (vector<unsigned>::iterator itr = newVertList.begin(),
728                 end = newVertList.end();
729             itr != end;
730             ++itr)
731            elements->push_back((GLushort)*itr);
732        if (geom.getUseVertexBufferObjects())
733        {
734            elements->setElementBufferObject(new ElementBufferObject);
735        }
736        newPrims.push_back(elements);
737    }
738    else
739    {
740        osg::DrawElementsUInt* elements
741            = new DrawElementsUInt(GL_TRIANGLES, newVertList.begin(),
742                                   newVertList.end());
743        if (geom.getUseVertexBufferObjects())
744        {
745            elements->setElementBufferObject(new ElementBufferObject);
746        }
747        newPrims.push_back(elements);
748    }
749
750    geom.setPrimitiveSetList(newPrims);
751#if 0
752    missv.doGeometry(geom);
753    cout << "After optimization: misses: " << missv.misses
754         << " triangles: " << missv.triangles << " acmr: ";
755    if (missv.triangles > 0.0)
756        cout << (double)missv.misses / (double)missv.triangles << "\n";
757    else
758        cout << "0.0\n";
759#endif
760    geom.dirtyDisplayList();
761}
762
763// The main optimization loop
764void VertexCacheVisitor::doVertexOptimization(Geometry& geom,
765                                              vector<unsigned>& vertDrawList)
766{
767    Geometry::PrimitiveSetList& primSets = geom.getPrimitiveSetList();
768    // lists for all the vertices and triangles
769    VertexList vertices;
770    TriangleList triangles;
771    TriangleCounter triCounter(&vertices);
772    for (Geometry::PrimitiveSetList::iterator itr = primSets.begin(),
773             end = primSets.end();
774         itr != end;
775         ++itr)
776        (*itr)->accept(triCounter);
777    triangles.resize(triCounter.triangleCount);
778    // Get total of triangles used by all the vertices
779    size_t vertTrisSize = 0;
780    for (VertexList::iterator itr = vertices.begin(), end = vertices.end();
781         itr != end;
782         ++itr)
783    {
784        itr->triList = vertTrisSize;
785        vertTrisSize += itr->trisUsing;
786    }
787    // Store for lists of triangles (indices) used by the vertices
788    vector<unsigned> vertTriListStore(vertTrisSize);
789    TriangleAdder triAdder(&vertices, &vertTriListStore, &triangles);
790    for (Geometry::PrimitiveSetList::iterator itr = primSets.begin(),
791             end = primSets.end();
792         itr != end;
793         ++itr)
794        (*itr)->accept(triAdder);
795    // Set up initial scores for vertices and triangles
796    for (VertexList::iterator itr = vertices.begin(), end = vertices.end();
797         itr != end;
798         ++itr)
799        itr->score = findVertexScore(*itr);
800    for (TriangleList::iterator itr = triangles.begin(), end = triangles.end();
801         itr != end;
802         ++itr)
803    {
804        itr->score = 0.0f;
805        for (int i = 0; i < 3; ++i)
806            itr->score += vertices[itr->verts[i]].score;
807    }
808    // Add Triangles to the draw list until there are no more.
809    unsigned trisLeft = triangles.size();
810    vertDrawList.reserve(trisLeft * 3);
811    LRUCache cache(maxCacheSize);
812    while (trisLeft-- > 0)
813    {
814        Triangle* triToAdd = 0;
815        float bestScore = 0.0;
816        for (vector<unsigned>::const_iterator itr = cache.entries.begin(),
817                 end = cache.entries.end();
818             itr != end;
819             ++itr)
820        {
821            TriangleScore tscore =  computeTriScores(vertices[*itr], vertices,
822                                                     triangles, vertTriListStore);
823            if (tscore.second > bestScore)
824            {
825                bestScore = tscore.second;
826                triToAdd = &triangles[tscore.first];
827            }
828        }
829        if (!triToAdd)
830        {
831            // The cache was empty, or all the triangles that use
832            // vertices in the cache have already been added.
833            OSG_DEBUG << "VertexCacheVisitor searching all triangles" << std::endl;
834            TriangleList::iterator maxItr
835                = max_element(triangles.begin(), triangles.end(),
836                              CompareTriangle());
837            triToAdd = &(*maxItr);
838        }
839        assert(triToAdd != 0 && triToAdd->score > 0.0);
840        // Add triangle vertices, and remove triangle from the
841        // vertices that use it.
842        triToAdd->score = -1.0f;
843        unsigned triToAddIdx = triToAdd - &triangles[0];
844        for (unsigned i = 0; i < 3; ++i)
845        {
846            unsigned vertIdx = triToAdd->verts[i];
847            Vertex* vert = &vertices[vertIdx];
848            vertDrawList.push_back(vertIdx);
849            remove(vertTriListStore.begin() + vert->triList,
850                   vertTriListStore.begin() + vert->triList
851                   + vert->numActiveTris,
852                   triToAddIdx);
853            vert->numActiveTris--;
854        }
855        // Assume that the three oldest cache entries will get kicked
856        // out, so reset their scores and those of their
857        // triangles. Otherwise we'll "lose" them and not be able to
858        // change their scores.
859        if (cache.maxSize - cache.entries.size() < 3)
860        {
861            for (vector<unsigned>::iterator itr = cache.entries.end() - 3,
862                     end = cache.entries.end();
863                 itr != end;
864                ++itr)
865            {
866                vertices[*itr].cachePosition = -1;
867                vertices[*itr].score = findVertexScore(vertices[*itr]);
868            }
869            for (vector<unsigned>::iterator itr = cache.entries.end() - 3,
870                     end = cache.entries.end();
871                 itr != end;
872                ++itr)
873                computeTriScores(vertices[*itr], vertices, triangles,
874                                 vertTriListStore);
875        }
876        cache.addEntries(&triToAdd->verts[0], &triToAdd->verts[3]);
877        for (vector<unsigned>::const_iterator itr = cache.entries.begin(),
878                 end = cache.entries.end();
879             itr != end;
880             ++itr)
881        {
882            unsigned vertIdx = *itr;
883            vertices[vertIdx].cachePosition = itr - cache.entries.begin();
884            vertices[vertIdx].score = findVertexScore(vertices[vertIdx]);
885        }
886     }
887}
888
889void VertexCacheVisitor::optimizeVertices()
890{
891    for(GeometryList::iterator itr=_geometryList.begin();
892        itr!=_geometryList.end();
893        ++itr)
894    {
895        optimizeVertices(*(*itr));
896    }
897}
898
899VertexCacheMissVisitor::VertexCacheMissVisitor(unsigned cacheSize)
900    : osg::NodeVisitor(NodeVisitor::TRAVERSE_ALL_CHILDREN), misses(0),
901      triangles(0), _cacheSize(cacheSize)
902{
903}
904
905void VertexCacheMissVisitor::reset()
906{
907    misses = 0;
908    triangles = 0;
909}
910
911void VertexCacheMissVisitor::apply(Geode& geode)
912{
913    for(unsigned int i = 0; i < geode.getNumDrawables(); ++i )
914    {
915        osg::Geometry* geom = dynamic_cast<osg::Geometry*>(geode.getDrawable(i));
916        if (geom)
917            doGeometry(*geom);
918    }
919}
920
921namespace
922{
923// The cache miss algorithm models an LRU cache because it results in an
924// order that is insensitive to the actual cache size of the GPU. Real
925// GPUs use a FIFO cache, so the statistics gatherer simulates that.
926struct FIFOCache
927{
928    FIFOCache(size_t maxSize_) : maxSize(maxSize_)
929    {
930        entries.reserve(maxSize_);
931    }
932    vector<unsigned> entries;
933    size_t maxSize;
934
935    // Add a list of values to the cache
936    void addEntries(unsigned* begin, unsigned* end)
937    {
938        // Make room for new cache entries
939        size_t newEnts = end - begin;
940        if (entries.size() < maxSize)
941            entries.resize(osg::minimum(entries.size() + newEnts, maxSize));
942        vector<unsigned>::iterator copyEnd = entries.end() - newEnts;
943        copy_backward(entries.begin(), copyEnd, entries.end());
944        copy(begin, end, entries.begin());
945    }
946
947    bool empty()
948    {
949        return entries.empty();
950    }
951};
952
953// Insert vertices in a cache and record cache misses
954struct CacheRecordOperator
955{
956    CacheRecordOperator() : cache(0), misses(0), triangles(0) {}
957    FIFOCache* cache;
958    unsigned misses;
959    unsigned triangles;
960    void operator()(unsigned p1, unsigned p2, unsigned p3)
961    {
962        unsigned verts[3];
963        verts[0] = p1;
964        verts[1] = p2;
965        verts[2] = p3;
966        triangles++;
967        for (int i = 0; i < 3; ++i)
968        {
969            if (find(cache->entries.begin(), cache->entries.end(), verts[i])
970                == cache->entries.end())
971                misses++;
972        }
973        cache->addEntries(&verts[0], &verts[3]);
974    }
975};
976
977struct CacheRecorder : public TriangleIndexFunctor<CacheRecordOperator>
978{
979    CacheRecorder(unsigned cacheSize)
980    {
981        cache = new FIFOCache(cacheSize);
982    }
983
984    ~CacheRecorder()
985    {
986        delete cache;
987    }
988};
989}
990
991void VertexCacheMissVisitor::doGeometry(Geometry& geom)
992{
993    Array* vertArray = geom.getVertexArray();
994    if (!vertArray)
995        return;
996    Geometry::PrimitiveSetList& primSets = geom.getPrimitiveSetList();
997    CacheRecorder recorder(_cacheSize);
998    for (Geometry::PrimitiveSetList::iterator itr = primSets.begin(),
999             end = primSets.end();
1000         itr != end;
1001         ++itr)
1002    {
1003        (*itr)->accept(recorder);
1004    }
1005    misses += recorder.misses;
1006    triangles += recorder.triangles;
1007}
1008
1009namespace
1010{
1011// Move the values in an array to new positions, based on the
1012// remapping table. remapping[i] contains element i's new position, if
1013// any.  Unlike RemapArray in TriStripVisitor, this code doesn't
1014// assume that elements only move downward in the array.
1015class Remapper : public osg::ArrayVisitor
1016{
1017public:
1018    static const unsigned invalidIndex;
1019    Remapper(const vector<unsigned>& remapping)
1020        : _remapping(remapping), _newsize(0)
1021    {
1022        for (vector<unsigned>::const_iterator itr = _remapping.begin(),
1023                 end = _remapping.end();
1024             itr != end;
1025             ++itr)
1026            if (*itr != invalidIndex)
1027                ++_newsize;
1028    }
1029
1030    const vector<unsigned>& _remapping;
1031    size_t _newsize;
1032
1033    template<class T>
1034    inline void remap(T& array)
1035    {
1036        ref_ptr<T> newarray = new T(_newsize);
1037        T* newptr = newarray.get();
1038        for (size_t i = 0; i < array.size(); ++i)
1039            if (_remapping[i] != invalidIndex)
1040                (*newptr)[_remapping[i]] = array[i];
1041        array.swap(*newptr);
1042
1043    }
1044
1045    virtual void apply(osg::Array&) {}
1046    virtual void apply(osg::ByteArray& array) { remap(array); }
1047    virtual void apply(osg::ShortArray& array) { remap(array); }
1048    virtual void apply(osg::IntArray& array) { remap(array); }
1049    virtual void apply(osg::UByteArray& array) { remap(array); }
1050    virtual void apply(osg::UShortArray& array) { remap(array); }
1051    virtual void apply(osg::UIntArray& array) { remap(array); }
1052    virtual void apply(osg::FloatArray& array) { remap(array); }
1053    virtual void apply(osg::DoubleArray& array) { remap(array); }
1054
1055    virtual void apply(osg::Vec2Array& array) { remap(array); }
1056    virtual void apply(osg::Vec3Array& array) { remap(array); }
1057    virtual void apply(osg::Vec4Array& array) { remap(array); }
1058
1059    virtual void apply(osg::Vec4ubArray& array) { remap(array); }
1060
1061    virtual void apply(osg::Vec2bArray& array) { remap(array); }
1062    virtual void apply(osg::Vec3bArray& array) { remap(array); }
1063    virtual void apply(osg::Vec4bArray& array) { remap(array); }
1064
1065    virtual void apply(osg::Vec2sArray& array) { remap(array); }
1066    virtual void apply(osg::Vec3sArray& array) { remap(array); }
1067    virtual void apply(osg::Vec4sArray& array) { remap(array); }
1068
1069    virtual void apply(osg::Vec2dArray& array) { remap(array); }
1070    virtual void apply(osg::Vec3dArray& array) { remap(array); }
1071    virtual void apply(osg::Vec4dArray& array) { remap(array); }
1072
1073    virtual void apply(osg::MatrixfArray& array) { remap(array); }
1074};
1075
1076const unsigned Remapper::invalidIndex = std::numeric_limits<unsigned>::max();
1077
1078// Record the order in which vertices in a Geometry are used.
1079struct VertexReorderOperator
1080{
1081    unsigned seq;
1082    vector<unsigned> remap;
1083
1084    VertexReorderOperator() : seq(0)
1085    {
1086    }
1087
1088    void inline doVertex(unsigned v)
1089    {
1090        if (remap[v] == Remapper::invalidIndex)
1091            remap[v] = seq++;
1092    }
1093    void operator()(unsigned p1, unsigned p2, unsigned p3)
1094    {
1095        doVertex(p1);
1096        doVertex(p2);
1097        doVertex(p3);
1098    }
1099};
1100
1101struct VertexReorder : public TriangleIndexFunctor<VertexReorderOperator>
1102{
1103    VertexReorder(unsigned numVerts)
1104    {
1105        remap.resize(numVerts, Remapper::invalidIndex);
1106    }
1107
1108};
1109}
1110
1111void VertexAccessOrderVisitor::optimizeOrder()
1112{
1113    for (GeometryList::iterator itr = _geometryList.begin(), end = _geometryList.end();
1114         itr != end;
1115         ++itr)
1116    {
1117        optimizeOrder(*(*itr));
1118    }
1119}
1120
1121template<typename DE>
1122inline void reorderDrawElements(DE& drawElements,
1123                                const vector<unsigned>& reorder)
1124{
1125    for (typename DE::iterator itr = drawElements.begin(), end = drawElements.end();
1126         itr != end;
1127         ++itr)
1128    {
1129        *itr = static_cast<typename DE::value_type>(reorder[*itr]);
1130    }
1131}
1132
1133void VertexAccessOrderVisitor::optimizeOrder(Geometry& geom)
1134{
1135    Array* vertArray = geom.getVertexArray();
1136    if (!vertArray)
1137        return;
1138    Geometry::PrimitiveSetList& primSets = geom.getPrimitiveSetList();
1139    GeometryArrayGatherer gatherer(geom);
1140    if (!gatherer._useDrawElements)
1141        return;
1142    VertexReorder vr(vertArray->getNumElements());
1143    for (Geometry::PrimitiveSetList::iterator itr = primSets.begin(),
1144             end = primSets.end();
1145         itr != end;
1146         ++itr)
1147    {
1148        PrimitiveSet* ps = itr->get();
1149        PrimitiveSet::Type type = ps->getType();
1150        if (type != PrimitiveSet::DrawElementsUBytePrimitiveType
1151            && type != PrimitiveSet::DrawElementsUShortPrimitiveType
1152            && type != PrimitiveSet::DrawElementsUIntPrimitiveType)
1153            return;
1154        ps->accept(vr);
1155    }
1156    Remapper remapper(vr.remap);
1157    gatherer.accept(remapper);
1158    for (Geometry::PrimitiveSetList::iterator itr = primSets.begin(),
1159             end = primSets.end();
1160         itr != end;
1161         ++itr)
1162    {
1163        PrimitiveSet* ps = itr->get();
1164        switch (ps->getType())
1165        {
1166        case PrimitiveSet::DrawElementsUBytePrimitiveType:
1167            reorderDrawElements(*static_cast<DrawElementsUByte*>(ps), vr.remap);
1168            break;
1169        case PrimitiveSet::DrawElementsUShortPrimitiveType:
1170            reorderDrawElements(*static_cast<DrawElementsUShort*>(ps), vr.remap);
1171            break;
1172        case PrimitiveSet::DrawElementsUIntPrimitiveType:
1173            reorderDrawElements(*static_cast<DrawElementsUInt*>(ps), vr.remap);
1174            break;
1175        default:
1176            break;
1177        }
1178    }
1179    geom.dirtyDisplayList();
1180}
1181}
Note: See TracBrowser for help on using the browser.