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

Revision 13488, 35.8 kB (checked in by robert, 9 hours ago)

Added NodeVisitor::INTERSECTION_VISITOR VisitorType?

  • 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    // compute duplicate vertices
283    typedef std::vector<unsigned int> IndexList;
284    unsigned int numVertices = geom.getVertexArray()->getNumElements();
285    IndexList indices(numVertices);
286    unsigned int i,j;
287    for(i=0;i<numVertices;++i)
288    {
289        indices[i] = i;
290    }
291
292    VertexAttribComparitor arrayComparitor(geom);
293    std::sort(indices.begin(),indices.end(),arrayComparitor);
294
295    unsigned int lastUnique = 0;
296    unsigned int numUnique = 1;
297    for(i=1;i<numVertices;++i)
298    {
299        if (arrayComparitor.compare(indices[lastUnique],indices[i]) != 0)
300        {
301            lastUnique = i;
302            ++numUnique;
303        }
304
305    }
306    IndexList remapDuplicatesToOrignals(numVertices);
307    lastUnique = 0;
308    for(i=1;i<numVertices;++i)
309    {
310        if (arrayComparitor.compare(indices[lastUnique],indices[i])!=0)
311        {
312            // found a new vertex entry, so previous run of duplicates needs
313            // to be put together.
314            unsigned int min_index = indices[lastUnique];
315            for(j=lastUnique+1;j<i;++j)
316            {
317                min_index = osg::minimum(min_index,indices[j]);
318            }
319            for(j=lastUnique;j<i;++j)
320            {
321                remapDuplicatesToOrignals[indices[j]]=min_index;
322            }
323            lastUnique = i;
324        }
325
326    }
327    unsigned int min_index = indices[lastUnique];
328    for(j=lastUnique+1;j<i;++j)
329    {
330        min_index = osg::minimum(min_index,indices[j]);
331    }
332    for(j=lastUnique;j<i;++j)
333    {
334        remapDuplicatesToOrignals[indices[j]]=min_index;
335    }
336
337
338    // copy the arrays.
339    IndexList finalMapping(numVertices);
340    IndexList copyMapping;
341    copyMapping.reserve(numUnique);
342    unsigned int currentIndex=0;
343    for(i=0;i<numVertices;++i)
344    {
345        if (remapDuplicatesToOrignals[i]==i)
346        {
347            finalMapping[i] = currentIndex;
348            copyMapping.push_back(i);
349            currentIndex++;
350        }
351    }
352
353    for(i=0;i<numVertices;++i)
354    {
355        if (remapDuplicatesToOrignals[i]!=i)
356        {
357            finalMapping[i] = finalMapping[remapDuplicatesToOrignals[i]];
358        }
359    }
360
361
362    MyTriangleIndexFunctor taf;
363    taf._remapIndices.swap(finalMapping);
364
365    Geometry::PrimitiveSetList new_primitives;
366    new_primitives.reserve(primitives.size());
367
368    for(itr=primitives.begin();
369        itr!=primitives.end();
370        ++itr)
371    {
372        // For now we only have primitive sets that play nicely with
373        // the TriangleIndexFunctor.
374        (*itr)->accept(taf);
375    }
376
377    // remap any shared vertex attributes
378    RemapArray ra(copyMapping);
379    arrayComparitor.accept(ra);
380    if (taf._in_indices.size() < 65536)
381    {
382        osg::DrawElementsUShort* elements = new DrawElementsUShort(GL_TRIANGLES);
383        for (IndexList::iterator itr = taf._in_indices.begin(),
384                 end = taf._in_indices.end();
385             itr != end;
386            ++itr)
387        {
388            elements->push_back((GLushort)(*itr));
389        }
390        new_primitives.push_back(elements);
391    }
392    else
393    {
394        osg::DrawElementsUInt* elements
395            = new DrawElementsUInt(GL_TRIANGLES, taf._in_indices.begin(),
396                                   taf._in_indices.end());
397        new_primitives.push_back(elements);
398    }
399    geom.setPrimitiveSetList(new_primitives);
400}
401
402void IndexMeshVisitor::makeMesh()
403{
404    for(GeometryList::iterator itr=_geometryList.begin();
405        itr!=_geometryList.end();
406        ++itr)
407    {
408        makeMesh(*(*itr));
409    }
410}
411
412namespace
413{
414// A simulation of a Least Recently Used cache. Position in the cache
415// corresponds to when the vertex was used i.e., 0 is the most
416// recently used.
417struct LRUCache
418{
419    LRUCache(size_t maxSize_) : maxSize(maxSize_)
420    {
421        entries.reserve(maxSize_ + 3);
422    }
423    vector<unsigned> entries;
424    size_t maxSize;
425
426    // Add a list of values to the cache
427    void addEntries(unsigned* begin, unsigned* end)
428    {
429        // If any of the new vertices are already in the cache, remove
430        // them, leaving some room at the front of the cache.
431        vector<unsigned>::reverse_iterator validEnd = entries.rend();
432        for (unsigned* pent = begin; pent != end; ++pent)
433        {
434            validEnd = remove(entries.rbegin(), validEnd, *pent);
435        }
436        // Now make room still needed for new cache entries
437        size_t newEnts = end - begin;
438        int spaceNeeded = newEnts - (entries.rend() - validEnd);
439        if (spaceNeeded > 0)
440        {
441            if (maxSize - entries.size() >= static_cast<unsigned>(spaceNeeded))
442                entries.resize(entries.size() + spaceNeeded);
443            else if (entries.size() < maxSize)
444                entries.resize(maxSize);
445            copy_backward(entries.begin() + newEnts - spaceNeeded,
446                          entries.end() - spaceNeeded, entries.end());
447        }
448        copy(begin, end, entries.begin());
449    }
450
451    bool empty()
452    {
453        return entries.empty();
454    }
455};
456
457// A list of triangles that use a vertex is associated with the Vertex
458// structure in another array.
459struct Vertex
460{
461    int cachePosition;
462    float score;
463    int trisUsing;
464    int numActiveTris;          // triangles left to process
465    size_t triList;             // index to start of triangle storage
466    Vertex()
467        : cachePosition(-1), score(0.0f), trisUsing(0), numActiveTris(0), triList(0)
468    {
469    }
470};
471
472// Code from Tom Forsyth's article. The algorithm is described in
473// detail at
474// http://home.comcast.net/~tom_forsyth/papers/fast_vert_cache_opt.html.
475// In summary, vertices are assigned a score based on the number of
476// triangles that use it (valence) and the vertex's position in the
477// model of the vertex cache, if any. Triangles are also given a
478// score, which is the sum of the scores of its vertices. The triangle
479// with the best score is added to the draw list, its vertices are
480// added and / or moved in the cache, the scores of vertices in the
481// cache and ejected from the cache are updated. Then the scores of
482// triangles that use those vertices are updated.
483//
484// Unless the cache is empty, the "best" triangle is found by
485// searching triangles that use vertices in the cache, not the whole
486// mesh. This keeps the algorithm running in time proportional to the
487// size of the mesh.
488
489// The "magic" scoring functions are described in the paper.
490const float cacheDecayPower = 1.5f;
491const float lastTriScore = 0.75f;
492const float valenceBoostScale = 2.0f;
493const float valenceBoostPower = 0.5f;
494
495const int maxCacheSize = 32;
496
497float findVertexScore (Vertex& vert)
498{
499
500    if (vert.numActiveTris == 0)
501    {
502        // No tri needs this vertex!
503        return -1.0f;
504    }
505    float score = 0.0f;
506    int cachePosition = vert.cachePosition;
507
508    if (cachePosition < 0)
509    {
510        // Vertex is not in FIFO cache - no score.
511    }
512    else
513    {
514        if (cachePosition < 3)
515        {
516            // This vertex was used in the last triangle,
517            // so it has a fixed score, whichever of the three
518            // it's in. Otherwise, you can get very different
519            // answers depending on whether you add
520            // the triangle 1,2,3 or 3,1,2 - which is silly.
521            score = lastTriScore;
522        }
523        else
524        {
525            assert (cachePosition < maxCacheSize);
526            // Points for being high in the cache.
527            const float scaler = 1.0f / (maxCacheSize - 3);
528            score = 1.0f - (cachePosition - 3 ) * scaler;
529            score = powf(score, cacheDecayPower);
530        }
531    }
532    // Bonus points for having a low number of tris still to
533    // use the vert, so we get rid of lone verts quickly.
534    float valenceBoost = powf(vert.numActiveTris, -valenceBoostPower);
535    score += valenceBoostScale * valenceBoost;
536    return score;
537}
538
539
540typedef vector<Vertex> VertexList;
541
542struct Triangle
543{
544    float score;
545    unsigned verts[3];
546};
547
548typedef vector<Triangle> TriangleList;
549
550inline float findTriangleScore(Triangle& tri, const VertexList& vertices)
551{
552    float result = 0.0f;
553    for (int i = 0; i < 3; ++i)
554        result += vertices[tri.verts[i]].score;
555    return result;
556}
557
558typedef std::pair<unsigned, float> TriangleScore;
559
560TriangleScore computeTriScores(Vertex& vert, const VertexList& vertices,
561                               TriangleList& triangles, vector<unsigned>& triStore)
562{
563    float bestScore = 0.0;
564    unsigned bestTri = 0;
565    for (size_t i = vert.triList;
566         i < vert.triList + vert.numActiveTris;
567         ++i)
568    {
569        unsigned tri = triStore[i];
570        float score = triangles[tri].score = findTriangleScore(triangles[tri],
571                                                               vertices);
572        if (score > bestScore)
573        {
574            bestScore = score;
575            bestTri = tri;
576        }
577    }
578    return make_pair(bestTri, bestScore);
579}
580
581typedef vector<Triangle> TriangleList;
582
583struct TriangleCounterOperator
584{
585    VertexList* vertices;
586    int triangleCount;
587    TriangleCounterOperator() : vertices(0), triangleCount(0) {}
588
589    void doVertex(unsigned p)
590    {
591        if (vertices->size() <= p)
592            vertices->resize(p + 1);
593        (*vertices)[p].trisUsing++;
594    }
595
596    void operator() (unsigned int p1, unsigned int p2, unsigned int p3)
597    {
598        if (p1 == p2 || p2 == p3 || p1 == p3)
599            return;
600        doVertex(p1);
601        doVertex(p2);
602        doVertex(p3);
603        triangleCount++;
604    }
605};
606
607struct TriangleCounter : public TriangleIndexFunctor<TriangleCounterOperator>
608{
609    TriangleCounter(vector<Vertex>* vertices_)
610    {
611        vertices = vertices_;
612    }
613};
614
615// Initialize the vertex triangle lists and the triangle data structures
616struct TriangleAddOperator
617{
618    VertexList* vertices;
619    vector<unsigned>* vertexTris;
620    TriangleList* triangles;
621    int triIdx;
622    TriangleAddOperator() : vertices(0), triIdx(0) {}
623
624    void doVertex(unsigned p)
625    {
626        (*vertexTris)[(*vertices)[p].triList + (*vertices)[p].numActiveTris++]
627            = triIdx;
628    }
629
630    void operator() (unsigned int p1, unsigned int p2, unsigned int p3)
631    {
632        if (p1 == p2 || p2 == p3 || p1 == p3)
633            return;
634        doVertex(p1);
635        doVertex(p2);
636        doVertex(p3);
637    (*triangles)[triIdx].verts[0] = p1;
638    (*triangles)[triIdx].verts[1] = p2;
639    (*triangles)[triIdx].verts[2] = p3;
640    triIdx++;
641    }
642};
643
644struct TriangleAdder : public TriangleIndexFunctor<TriangleAddOperator>
645{
646    TriangleAdder(VertexList* vertices_, vector<unsigned>* vertexTris_,
647                  TriangleList* triangles_)
648    {
649        vertices = vertices_;
650        vertexTris = vertexTris_;
651        triangles = triangles_;
652    }
653};
654
655struct CompareTriangle
656{
657    bool operator()(const Triangle& lhs, const Triangle& rhs)
658    {
659        return lhs.score < rhs.score;
660    }
661};
662}
663
664void VertexCacheVisitor::optimizeVertices(Geometry& geom)
665{
666    Array* vertArray = geom.getVertexArray();
667    if (!vertArray)
668        return;
669    unsigned vertArraySize = vertArray->getNumElements();
670    // If all the vertices fit in the cache, there's no point in
671    // doing this optimization.
672    if (vertArraySize <= 16)
673        return;
674    Geometry::PrimitiveSetList& primSets = geom.getPrimitiveSetList();
675    for (Geometry::PrimitiveSetList::iterator itr = primSets.begin(),
676             end = primSets.end();
677         itr != end;
678         ++itr)
679    {
680        // Can only deal with polygons.
681        switch ((*itr)->getMode())
682        {
683        case(PrimitiveSet::TRIANGLES):
684        case(PrimitiveSet::TRIANGLE_STRIP):
685        case(PrimitiveSet::TRIANGLE_FAN):
686        case(PrimitiveSet::QUADS):
687        case(PrimitiveSet::QUAD_STRIP):
688        case(PrimitiveSet::POLYGON):
689            break;
690        default:
691            return;
692        }
693        PrimitiveSet::Type type = (*itr)->getType();
694        if (type != PrimitiveSet::DrawElementsUBytePrimitiveType
695            && type != PrimitiveSet::DrawElementsUShortPrimitiveType
696            && type != PrimitiveSet::DrawElementsUIntPrimitiveType)
697            return;
698    }
699#if 0
700    VertexCacheMissVisitor missv;
701    missv.doGeometry(geom);
702    cout << "Before optimization: misses: " << missv.misses
703         << " triangles: " << missv.triangles << " acmr: ";
704    if (missv.triangles > 0.0)
705        cout << (double)missv.misses / (double)missv.triangles << "\n";
706    else
707        cout << "0.0\n";
708    missv.reset();
709#endif
710    vector<unsigned> newVertList;
711    doVertexOptimization(geom, newVertList);
712    Geometry::PrimitiveSetList newPrims;
713    if (vertArraySize < 65536)
714    {
715        osg::DrawElementsUShort* elements = new DrawElementsUShort(GL_TRIANGLES);
716        elements->reserve(newVertList.size());
717        for (vector<unsigned>::iterator itr = newVertList.begin(),
718                 end = newVertList.end();
719             itr != end;
720             ++itr)
721            elements->push_back((GLushort)*itr);
722        if (geom.getUseVertexBufferObjects())
723        {
724            elements->setElementBufferObject(new ElementBufferObject);
725        }
726        newPrims.push_back(elements);
727    }
728    else
729    {
730        osg::DrawElementsUInt* elements
731            = new DrawElementsUInt(GL_TRIANGLES, newVertList.begin(),
732                                   newVertList.end());
733        if (geom.getUseVertexBufferObjects())
734        {
735            elements->setElementBufferObject(new ElementBufferObject);
736        }
737        newPrims.push_back(elements);
738    }
739
740    geom.setPrimitiveSetList(newPrims);
741#if 0
742    missv.doGeometry(geom);
743    cout << "After optimization: misses: " << missv.misses
744         << " triangles: " << missv.triangles << " acmr: ";
745    if (missv.triangles > 0.0)
746        cout << (double)missv.misses / (double)missv.triangles << "\n";
747    else
748        cout << "0.0\n";
749#endif
750    geom.dirtyDisplayList();
751}
752
753// The main optimization loop
754void VertexCacheVisitor::doVertexOptimization(Geometry& geom,
755                                              vector<unsigned>& vertDrawList)
756{
757    Geometry::PrimitiveSetList& primSets = geom.getPrimitiveSetList();
758    // lists for all the vertices and triangles
759    VertexList vertices;
760    TriangleList triangles;
761    TriangleCounter triCounter(&vertices);
762    for (Geometry::PrimitiveSetList::iterator itr = primSets.begin(),
763             end = primSets.end();
764         itr != end;
765         ++itr)
766        (*itr)->accept(triCounter);
767    triangles.resize(triCounter.triangleCount);
768    // Get total of triangles used by all the vertices
769    size_t vertTrisSize = 0;
770    for (VertexList::iterator itr = vertices.begin(), end = vertices.end();
771         itr != end;
772         ++itr)
773    {
774        itr->triList = vertTrisSize;
775        vertTrisSize += itr->trisUsing;
776    }
777    // Store for lists of triangles (indices) used by the vertices
778    vector<unsigned> vertTriListStore(vertTrisSize);
779    TriangleAdder triAdder(&vertices, &vertTriListStore, &triangles);
780    for (Geometry::PrimitiveSetList::iterator itr = primSets.begin(),
781             end = primSets.end();
782         itr != end;
783         ++itr)
784        (*itr)->accept(triAdder);
785    // Set up initial scores for vertices and triangles
786    for (VertexList::iterator itr = vertices.begin(), end = vertices.end();
787         itr != end;
788         ++itr)
789        itr->score = findVertexScore(*itr);
790    for (TriangleList::iterator itr = triangles.begin(), end = triangles.end();
791         itr != end;
792         ++itr)
793    {
794        itr->score = 0.0f;
795        for (int i = 0; i < 3; ++i)
796            itr->score += vertices[itr->verts[i]].score;
797    }
798    // Add Triangles to the draw list until there are no more.
799    unsigned trisLeft = triangles.size();
800    vertDrawList.reserve(trisLeft * 3);
801    LRUCache cache(maxCacheSize);
802    while (trisLeft-- > 0)
803    {
804        Triangle* triToAdd = 0;
805        float bestScore = 0.0;
806        for (vector<unsigned>::const_iterator itr = cache.entries.begin(),
807                 end = cache.entries.end();
808             itr != end;
809             ++itr)
810        {
811            TriangleScore tscore =  computeTriScores(vertices[*itr], vertices,
812                                                     triangles, vertTriListStore);
813            if (tscore.second > bestScore)
814            {
815                bestScore = tscore.second;
816                triToAdd = &triangles[tscore.first];
817            }
818        }
819        if (!triToAdd)
820        {
821            // The cache was empty, or all the triangles that use
822            // vertices in the cache have already been added.
823            OSG_DEBUG << "VertexCacheVisitor searching all triangles" << std::endl;
824            TriangleList::iterator maxItr
825                = max_element(triangles.begin(), triangles.end(),
826                              CompareTriangle());
827            triToAdd = &(*maxItr);
828        }
829        assert(triToAdd != 0 && triToAdd->score > 0.0);
830        // Add triangle vertices, and remove triangle from the
831        // vertices that use it.
832        triToAdd->score = -1.0f;
833        unsigned triToAddIdx = triToAdd - &triangles[0];
834        for (unsigned i = 0; i < 3; ++i)
835        {
836            unsigned vertIdx = triToAdd->verts[i];
837            Vertex* vert = &vertices[vertIdx];
838            vertDrawList.push_back(vertIdx);
839            remove(vertTriListStore.begin() + vert->triList,
840                   vertTriListStore.begin() + vert->triList
841                   + vert->numActiveTris,
842                   triToAddIdx);
843            vert->numActiveTris--;
844        }
845        // Assume that the three oldest cache entries will get kicked
846        // out, so reset their scores and those of their
847        // triangles. Otherwise we'll "lose" them and not be able to
848        // change their scores.
849        if (cache.maxSize - cache.entries.size() < 3)
850        {
851            for (vector<unsigned>::iterator itr = cache.entries.end() - 3,
852                     end = cache.entries.end();
853                 itr != end;
854                ++itr)
855            {
856                vertices[*itr].cachePosition = -1;
857                vertices[*itr].score = findVertexScore(vertices[*itr]);
858            }
859            for (vector<unsigned>::iterator itr = cache.entries.end() - 3,
860                     end = cache.entries.end();
861                 itr != end;
862                ++itr)
863                computeTriScores(vertices[*itr], vertices, triangles,
864                                 vertTriListStore);
865        }
866        cache.addEntries(&triToAdd->verts[0], &triToAdd->verts[3]);
867        for (vector<unsigned>::const_iterator itr = cache.entries.begin(),
868                 end = cache.entries.end();
869             itr != end;
870             ++itr)
871        {
872            unsigned vertIdx = *itr;
873            vertices[vertIdx].cachePosition = itr - cache.entries.begin();
874            vertices[vertIdx].score = findVertexScore(vertices[vertIdx]);
875        }
876     }
877}
878
879void VertexCacheVisitor::optimizeVertices()
880{
881    for(GeometryList::iterator itr=_geometryList.begin();
882        itr!=_geometryList.end();
883        ++itr)
884    {
885        optimizeVertices(*(*itr));
886    }
887}
888
889VertexCacheMissVisitor::VertexCacheMissVisitor(unsigned cacheSize)
890    : osg::NodeVisitor(NodeVisitor::TRAVERSE_ALL_CHILDREN), misses(0),
891      triangles(0), _cacheSize(cacheSize)
892{
893}
894
895void VertexCacheMissVisitor::reset()
896{
897    misses = 0;
898    triangles = 0;
899}
900
901void VertexCacheMissVisitor::apply(Geode& geode)
902{
903    for(unsigned int i = 0; i < geode.getNumDrawables(); ++i )
904    {
905        osg::Geometry* geom = dynamic_cast<osg::Geometry*>(geode.getDrawable(i));
906        if (geom)
907            doGeometry(*geom);
908    }
909}
910
911namespace
912{
913// The cache miss algorithm models an LRU cache because it results in an
914// order that is insensitive to the actual cache size of the GPU. Real
915// GPUs use a FIFO cache, so the statistics gatherer simulates that.
916struct FIFOCache
917{
918    FIFOCache(size_t maxSize_) : maxSize(maxSize_)
919    {
920        entries.reserve(maxSize_);
921    }
922    vector<unsigned> entries;
923    size_t maxSize;
924
925    // Add a list of values to the cache
926    void addEntries(unsigned* begin, unsigned* end)
927    {
928        // Make room for new cache entries
929        size_t newEnts = end - begin;
930        if (entries.size() < maxSize)
931            entries.resize(osg::minimum(entries.size() + newEnts, maxSize));
932        vector<unsigned>::iterator copyEnd = entries.end() - newEnts;
933        copy_backward(entries.begin(), copyEnd, entries.end());
934        copy(begin, end, entries.begin());
935    }
936
937    bool empty()
938    {
939        return entries.empty();
940    }
941};
942
943// Insert vertices in a cache and record cache misses
944struct CacheRecordOperator
945{
946    CacheRecordOperator() : cache(0), misses(0), triangles(0) {}
947    FIFOCache* cache;
948    unsigned misses;
949    unsigned triangles;
950    void operator()(unsigned p1, unsigned p2, unsigned p3)
951    {
952        unsigned verts[3];
953        verts[0] = p1;
954        verts[1] = p2;
955        verts[2] = p3;
956        triangles++;
957        for (int i = 0; i < 3; ++i)
958        {
959            if (find(cache->entries.begin(), cache->entries.end(), verts[i])
960                == cache->entries.end())
961                misses++;
962        }
963        cache->addEntries(&verts[0], &verts[3]);
964    }
965};
966
967struct CacheRecorder : public TriangleIndexFunctor<CacheRecordOperator>
968{
969    CacheRecorder(unsigned cacheSize)
970    {
971        cache = new FIFOCache(cacheSize);
972    }
973
974    ~CacheRecorder()
975    {
976        delete cache;
977    }
978};
979}
980
981void VertexCacheMissVisitor::doGeometry(Geometry& geom)
982{
983    Array* vertArray = geom.getVertexArray();
984    if (!vertArray)
985        return;
986    Geometry::PrimitiveSetList& primSets = geom.getPrimitiveSetList();
987    CacheRecorder recorder(_cacheSize);
988    for (Geometry::PrimitiveSetList::iterator itr = primSets.begin(),
989             end = primSets.end();
990         itr != end;
991         ++itr)
992    {
993        (*itr)->accept(recorder);
994    }
995    misses += recorder.misses;
996    triangles += recorder.triangles;
997}
998
999namespace
1000{
1001// Move the values in an array to new positions, based on the
1002// remapping table. remapping[i] contains element i's new position, if
1003// any.  Unlike RemapArray in TriStripVisitor, this code doesn't
1004// assume that elements only move downward in the array.
1005class Remapper : public osg::ArrayVisitor
1006{
1007public:
1008    static const unsigned invalidIndex;
1009    Remapper(const vector<unsigned>& remapping)
1010        : _remapping(remapping), _newsize(0)
1011    {
1012        for (vector<unsigned>::const_iterator itr = _remapping.begin(),
1013                 end = _remapping.end();
1014             itr != end;
1015             ++itr)
1016            if (*itr != invalidIndex)
1017                ++_newsize;
1018    }
1019
1020    const vector<unsigned>& _remapping;
1021    size_t _newsize;
1022
1023    template<class T>
1024    inline void remap(T& array)
1025    {
1026        ref_ptr<T> newarray = new T(_newsize);
1027        T* newptr = newarray.get();
1028        for (size_t i = 0; i < array.size(); ++i)
1029            if (_remapping[i] != invalidIndex)
1030                (*newptr)[_remapping[i]] = array[i];
1031        array.swap(*newptr);
1032
1033    }
1034
1035    virtual void apply(osg::Array&) {}
1036    virtual void apply(osg::ByteArray& array) { remap(array); }
1037    virtual void apply(osg::ShortArray& array) { remap(array); }
1038    virtual void apply(osg::IntArray& array) { remap(array); }
1039    virtual void apply(osg::UByteArray& array) { remap(array); }
1040    virtual void apply(osg::UShortArray& array) { remap(array); }
1041    virtual void apply(osg::UIntArray& array) { remap(array); }
1042    virtual void apply(osg::FloatArray& array) { remap(array); }
1043    virtual void apply(osg::DoubleArray& array) { remap(array); }
1044
1045    virtual void apply(osg::Vec2Array& array) { remap(array); }
1046    virtual void apply(osg::Vec3Array& array) { remap(array); }
1047    virtual void apply(osg::Vec4Array& array) { remap(array); }
1048
1049    virtual void apply(osg::Vec4ubArray& array) { remap(array); }
1050
1051    virtual void apply(osg::Vec2bArray& array) { remap(array); }
1052    virtual void apply(osg::Vec3bArray& array) { remap(array); }
1053    virtual void apply(osg::Vec4bArray& array) { remap(array); }
1054
1055    virtual void apply(osg::Vec2sArray& array) { remap(array); }
1056    virtual void apply(osg::Vec3sArray& array) { remap(array); }
1057    virtual void apply(osg::Vec4sArray& array) { remap(array); }
1058
1059    virtual void apply(osg::Vec2dArray& array) { remap(array); }
1060    virtual void apply(osg::Vec3dArray& array) { remap(array); }
1061    virtual void apply(osg::Vec4dArray& array) { remap(array); }
1062
1063    virtual void apply(osg::MatrixfArray& array) { remap(array); }
1064};
1065
1066const unsigned Remapper::invalidIndex = std::numeric_limits<unsigned>::max();
1067
1068// Record the order in which vertices in a Geometry are used.
1069struct VertexReorderOperator
1070{
1071    unsigned seq;
1072    vector<unsigned> remap;
1073
1074    VertexReorderOperator() : seq(0)
1075    {
1076    }
1077
1078    void inline doVertex(unsigned v)
1079    {
1080        if (remap[v] == Remapper::invalidIndex)
1081            remap[v] = seq++;
1082    }
1083    void operator()(unsigned p1, unsigned p2, unsigned p3)
1084    {
1085        doVertex(p1);
1086        doVertex(p2);
1087        doVertex(p3);
1088    }
1089};
1090
1091struct VertexReorder : public TriangleIndexFunctor<VertexReorderOperator>
1092{
1093    VertexReorder(unsigned numVerts)
1094    {
1095        remap.resize(numVerts, Remapper::invalidIndex);
1096    }
1097
1098};
1099}
1100
1101void VertexAccessOrderVisitor::optimizeOrder()
1102{
1103    for (GeometryList::iterator itr = _geometryList.begin(), end = _geometryList.end();
1104         itr != end;
1105         ++itr)
1106    {
1107        optimizeOrder(*(*itr));
1108    }
1109}
1110
1111template<typename DE>
1112inline void reorderDrawElements(DE& drawElements,
1113                                const vector<unsigned>& reorder)
1114{
1115    for (typename DE::iterator itr = drawElements.begin(), end = drawElements.end();
1116         itr != end;
1117         ++itr)
1118    {
1119        *itr = static_cast<typename DE::value_type>(reorder[*itr]);
1120    }
1121}
1122
1123void VertexAccessOrderVisitor::optimizeOrder(Geometry& geom)
1124{
1125    Array* vertArray = geom.getVertexArray();
1126    if (!vertArray)
1127        return;
1128    Geometry::PrimitiveSetList& primSets = geom.getPrimitiveSetList();
1129    GeometryArrayGatherer gatherer(geom);
1130    if (!gatherer._useDrawElements)
1131        return;
1132    VertexReorder vr(vertArray->getNumElements());
1133    for (Geometry::PrimitiveSetList::iterator itr = primSets.begin(),
1134             end = primSets.end();
1135         itr != end;
1136         ++itr)
1137    {
1138        PrimitiveSet* ps = itr->get();
1139        PrimitiveSet::Type type = ps->getType();
1140        if (type != PrimitiveSet::DrawElementsUBytePrimitiveType
1141            && type != PrimitiveSet::DrawElementsUShortPrimitiveType
1142            && type != PrimitiveSet::DrawElementsUIntPrimitiveType)
1143            return;
1144        ps->accept(vr);
1145    }
1146    Remapper remapper(vr.remap);
1147    gatherer.accept(remapper);
1148    for (Geometry::PrimitiveSetList::iterator itr = primSets.begin(),
1149             end = primSets.end();
1150         itr != end;
1151         ++itr)
1152    {
1153        PrimitiveSet* ps = itr->get();
1154        switch (ps->getType())
1155        {
1156        case PrimitiveSet::DrawElementsUBytePrimitiveType:
1157            reorderDrawElements(*static_cast<DrawElementsUByte*>(ps), vr.remap);
1158            break;
1159        case PrimitiveSet::DrawElementsUShortPrimitiveType:
1160            reorderDrawElements(*static_cast<DrawElementsUShort*>(ps), vr.remap);
1161            break;
1162        case PrimitiveSet::DrawElementsUIntPrimitiveType:
1163            reorderDrawElements(*static_cast<DrawElementsUInt*>(ps), vr.remap);
1164            break;
1165        default:
1166            break;
1167        }
1168    }
1169    geom.dirtyDisplayList();
1170}
1171}
Note: See TracBrowser for help on using the browser.