root/OpenSceneGraph/branches/OpenSceneGraph-2.8/src/osgUtil/Optimizer.cpp @ 11208

Revision 11208, 155.6 kB (checked in by paulmartz, 5 years ago)

Merge 10664 to 2.8 branch (MSFBO workaround for OS X).

  • Property svn:mergeinfo set to
    /OpenSceneGraph/branches/OpenSceneGraph-2.8.2/src/osgUtil/Optimizer.cpp:10664
    /OpenSceneGraph/trunk/include/osg/src/osgUtil/Optimizer.cpp:9882
    /OpenSceneGraph/trunk/src/osgUtil/Optimizer.cpp:9902,9920,9987,10480
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
Line 
1/* -*-c++-*- OpenSceneGraph - Copyright (C) 1998-2006 Robert Osfield
2 *
3 * This library is open source and may be redistributed and/or modified under 
4 * the terms of the OpenSceneGraph Public License (OSGPL) version 0.0 or
5 * (at your option) any later version.  The full license is in LICENSE file
6 * included with this distribution, and on the openscenegraph.org website.
7 *
8 * This library is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11 * OpenSceneGraph Public License for more details.
12*/
13#include <stdlib.h>
14#include <string.h>
15
16#include <osgUtil/Optimizer>
17
18#include <osg/ApplicationUsage>
19#include <osg/Transform>
20#include <osg/MatrixTransform>
21#include <osg/PositionAttitudeTransform>
22#include <osg/LOD>
23#include <osg/Billboard>
24#include <osg/Geometry>
25#include <osg/Notify>
26#include <osg/OccluderNode>
27#include <osg/Sequence>
28#include <osg/Switch>
29#include <osg/Texture>
30#include <osg/PagedLOD>
31#include <osg/ProxyNode>
32#include <osg/ImageStream>
33#include <osg/Timer>
34#include <osg/TexMat>
35#include <osg/io_utils>
36
37#include <osgUtil/TransformAttributeFunctor>
38#include <osgUtil/TriStripVisitor>
39#include <osgUtil/Tessellator>
40#include <osgUtil/Statistics>
41
42#include <typeinfo>
43#include <algorithm>
44#include <numeric>
45#include <sstream>
46
47using namespace osgUtil;
48
49
50void Optimizer::reset()
51{
52}
53
54static osg::ApplicationUsageProxy Optimizer_e0(osg::ApplicationUsage::ENVIRONMENTAL_VARIABLE,"OSG_OPTIMIZER \"<type> [<type>]\"","OFF | DEFAULT | FLATTEN_STATIC_TRANSFORMS | FLATTEN_STATIC_TRANSFORMS_DUPLICATING_SHARED_SUBGRAPHS | REMOVE_REDUNDANT_NODES | COMBINE_ADJACENT_LODS | SHARE_DUPLICATE_STATE | MERGE_GEOMETRY | MERGE_GEODES | SPATIALIZE_GROUPS  | COPY_SHARED_NODES  | TRISTRIP_GEOMETRY | OPTIMIZE_TEXTURE_SETTINGS | REMOVE_LOADED_PROXY_NODES | TESSELLATE_GEOMETRY | CHECK_GEOMETRY |  FLATTEN_BILLBOARDS | TEXTURE_ATLAS_BUILDER | STATIC_OBJECT_DETECTION");
55
56void Optimizer::optimize(osg::Node* node)
57{
58    unsigned int options = 0;
59   
60   
61    const char* env = getenv("OSG_OPTIMIZER");
62    if (env)
63    {
64        std::string str(env);
65
66        if(str.find("OFF")!=std::string::npos) options = 0;
67
68        if(str.find("~DEFAULT")!=std::string::npos) options ^= DEFAULT_OPTIMIZATIONS;
69        else if(str.find("DEFAULT")!=std::string::npos) options |= DEFAULT_OPTIMIZATIONS;
70
71        if(str.find("~FLATTEN_STATIC_TRANSFORMS")!=std::string::npos) options ^= FLATTEN_STATIC_TRANSFORMS;
72        else if(str.find("FLATTEN_STATIC_TRANSFORMS")!=std::string::npos) options |= FLATTEN_STATIC_TRANSFORMS;
73
74        if(str.find("~FLATTEN_STATIC_TRANSFORMS_DUPLICATING_SHARED_SUBGRAPHS")!=std::string::npos) options ^= FLATTEN_STATIC_TRANSFORMS_DUPLICATING_SHARED_SUBGRAPHS;
75        else if(str.find("FLATTEN_STATIC_TRANSFORMS_DUPLICATING_SHARED_SUBGRAPHS")!=std::string::npos) options |= FLATTEN_STATIC_TRANSFORMS_DUPLICATING_SHARED_SUBGRAPHS;
76
77        if(str.find("~REMOVE_REDUNDANT_NODES")!=std::string::npos) options ^= REMOVE_REDUNDANT_NODES;
78        else if(str.find("REMOVE_REDUNDANT_NODES")!=std::string::npos) options |= REMOVE_REDUNDANT_NODES;
79
80        if(str.find("~REMOVE_LOADED_PROXY_NODES")!=std::string::npos) options ^= REMOVE_LOADED_PROXY_NODES;
81        else if(str.find("REMOVE_LOADED_PROXY_NODES")!=std::string::npos) options |= REMOVE_LOADED_PROXY_NODES;
82
83        if(str.find("~COMBINE_ADJACENT_LODS")!=std::string::npos) options ^= COMBINE_ADJACENT_LODS;
84        else if(str.find("COMBINE_ADJACENT_LODS")!=std::string::npos) options |= COMBINE_ADJACENT_LODS;
85
86        if(str.find("~SHARE_DUPLICATE_STATE")!=std::string::npos) options ^= SHARE_DUPLICATE_STATE;
87        else if(str.find("SHARE_DUPLICATE_STATE")!=std::string::npos) options |= SHARE_DUPLICATE_STATE;
88
89        if(str.find("~MERGE_GEODES")!=std::string::npos) options ^= MERGE_GEODES;
90        else if(str.find("MERGE_GEODES")!=std::string::npos) options |= MERGE_GEODES;
91
92        if(str.find("~MERGE_GEOMETRY")!=std::string::npos) options ^= MERGE_GEOMETRY;
93        else if(str.find("MERGE_GEOMETRY")!=std::string::npos) options |= MERGE_GEOMETRY;
94
95        if(str.find("~SPATIALIZE_GROUPS")!=std::string::npos) options ^= SPATIALIZE_GROUPS;
96        else if(str.find("SPATIALIZE_GROUPS")!=std::string::npos) options |= SPATIALIZE_GROUPS;
97
98        if(str.find("~COPY_SHARED_NODES")!=std::string::npos) options ^= COPY_SHARED_NODES;
99        else if(str.find("COPY_SHARED_NODES")!=std::string::npos) options |= COPY_SHARED_NODES;
100
101        if(str.find("~TESSELLATE_GEOMETRY")!=std::string::npos) options ^= TESSELLATE_GEOMETRY;
102        else if(str.find("TESSELLATE_GEOMETRY")!=std::string::npos) options |= TESSELLATE_GEOMETRY;
103
104        if(str.find("~TRISTRIP_GEOMETRY")!=std::string::npos) options ^= TRISTRIP_GEOMETRY;
105        else if(str.find("TRISTRIP_GEOMETRY")!=std::string::npos) options |= TRISTRIP_GEOMETRY;
106
107        if(str.find("~OPTIMIZE_TEXTURE_SETTINGS")!=std::string::npos) options ^= OPTIMIZE_TEXTURE_SETTINGS;
108        else if(str.find("OPTIMIZE_TEXTURE_SETTINGS")!=std::string::npos) options |= OPTIMIZE_TEXTURE_SETTINGS;
109
110        if(str.find("~CHECK_GEOMETRY")!=std::string::npos) options ^= CHECK_GEOMETRY;
111        else if(str.find("CHECK_GEOMETRY")!=std::string::npos) options |= CHECK_GEOMETRY;
112       
113        if(str.find("~FLATTEN_BILLBOARDS")!=std::string::npos) options ^= FLATTEN_BILLBOARDS;
114        else if(str.find("FLATTEN_BILLBOARDS")!=std::string::npos) options |= FLATTEN_BILLBOARDS;
115       
116        if(str.find("~TEXTURE_ATLAS_BUILDER")!=std::string::npos) options ^= TEXTURE_ATLAS_BUILDER;
117        else if(str.find("TEXTURE_ATLAS_BUILDER")!=std::string::npos) options |= TEXTURE_ATLAS_BUILDER;
118       
119        if(str.find("~STATIC_OBJECT_DETECTION")!=std::string::npos) options ^= STATIC_OBJECT_DETECTION;
120        else if(str.find("STATIC_OBJECT_DETECTION")!=std::string::npos) options |= STATIC_OBJECT_DETECTION;
121
122    }
123    else
124    {
125        options = DEFAULT_OPTIMIZATIONS;
126    }
127
128    optimize(node,options);
129
130}
131
132void Optimizer::optimize(osg::Node* node, unsigned int options)
133{
134    StatsVisitor stats;
135   
136    if (osg::getNotifyLevel()>=osg::INFO)
137    {
138        node->accept(stats);
139        stats.totalUpStats();
140        osg::notify(osg::NOTICE)<<std::endl<<"Stats before:"<<std::endl;
141        stats.print(osg::notify(osg::NOTICE));
142    }
143
144    if (options & STATIC_OBJECT_DETECTION)
145    {
146        StaticObjectDetectionVisitor sodv;
147        node->accept(sodv);
148    }
149
150    if (options & TESSELLATE_GEOMETRY)
151    {
152        osg::notify(osg::INFO)<<"Optimizer::optimize() doing TESSELLATE_GEOMETRY"<<std::endl;
153
154        TessellateVisitor tsv;
155        node->accept(tsv);       
156    }
157   
158    if (options & REMOVE_LOADED_PROXY_NODES)
159    {
160        osg::notify(osg::INFO)<<"Optimizer::optimize() doing REMOVE_LOADED_PROXY_NODES"<<std::endl;
161
162        RemoveLoadedProxyNodesVisitor rlpnv(this);
163        node->accept(rlpnv);
164        rlpnv.removeRedundantNodes();
165
166    }
167
168    if (options & COMBINE_ADJACENT_LODS)
169    {
170        osg::notify(osg::INFO)<<"Optimizer::optimize() doing COMBINE_ADJACENT_LODS"<<std::endl;
171
172        CombineLODsVisitor clv(this);
173        node->accept(clv);       
174        clv.combineLODs();
175    }
176   
177    if (options & OPTIMIZE_TEXTURE_SETTINGS)
178    {
179        osg::notify(osg::INFO)<<"Optimizer::optimize() doing OPTIMIZE_TEXTURE_SETTINGS"<<std::endl;
180
181        TextureVisitor tv(true,true, // unref image
182                          false,false, // client storage
183                          false,1.0, // anisotropic filtering
184                          this );
185        node->accept(tv);
186    }
187
188    if (options & SHARE_DUPLICATE_STATE)
189    {
190        osg::notify(osg::INFO)<<"Optimizer::optimize() doing SHARE_DUPLICATE_STATE"<<std::endl;
191
192        bool combineDynamicState = false;
193        bool combineStaticState = true;
194        bool combineUnspecifiedState = true;
195
196        StateVisitor osv(combineDynamicState, combineStaticState, combineUnspecifiedState, this);
197        node->accept(osv);
198        osv.optimize();
199    }
200   
201    if (options & TEXTURE_ATLAS_BUILDER)
202    {
203        osg::notify(osg::INFO)<<"Optimizer::optimize() doing TEXTURE_ATLAS_BUILDER"<<std::endl;
204       
205        // traverse the scene collecting textures into texture atlas.
206        TextureAtlasVisitor tav(this);
207        node->accept(tav);
208        tav.optimize();
209
210        // now merge duplicate state, that may have been introduced by merge textures into texture atlas'
211        bool combineDynamicState = false;
212        bool combineStaticState = true;
213        bool combineUnspecifiedState = true;
214
215        StateVisitor osv(combineDynamicState, combineStaticState, combineUnspecifiedState, this);
216        node->accept(osv);
217        osv.optimize();
218    }
219   
220    if (options & COPY_SHARED_NODES)
221    {
222        osg::notify(osg::INFO)<<"Optimizer::optimize() doing COPY_SHARED_NODES"<<std::endl;
223
224        CopySharedSubgraphsVisitor cssv(this);
225        node->accept(cssv);
226        cssv.copySharedNodes();
227    }
228   
229    if (options & FLATTEN_STATIC_TRANSFORMS)
230    {
231        osg::notify(osg::INFO)<<"Optimizer::optimize() doing FLATTEN_STATIC_TRANSFORMS"<<std::endl;
232
233        int i=0;
234        bool result = false;
235        do
236        {
237            osg::notify(osg::DEBUG_INFO) << "** RemoveStaticTransformsVisitor *** Pass "<<i<<std::endl;
238            FlattenStaticTransformsVisitor fstv(this);
239            node->accept(fstv);
240            result = fstv.removeTransforms(node);
241            ++i;
242        } while (result);
243
244        // no combine any adjacent static transforms.
245        CombineStaticTransformsVisitor cstv(this);
246        node->accept(cstv);
247        cstv.removeTransforms(node);
248    }
249
250    if (options & FLATTEN_STATIC_TRANSFORMS_DUPLICATING_SHARED_SUBGRAPHS)
251    {
252        osg::notify(osg::INFO)<<"Optimizer::optimize() doing FLATTEN_STATIC_TRANSFORMS_DUPLICATING_SHARED_SUBGRAPHS"<<std::endl;
253
254        // no combine any adjacent static transforms.
255        FlattenStaticTransformsDuplicatingSharedSubgraphsVisitor fstdssv(this);
256        node->accept(fstdssv);
257
258    }
259
260    if (options & MERGE_GEODES)
261    {
262        osg::notify(osg::INFO)<<"Optimizer::optimize() doing MERGE_GEODES"<<std::endl;
263
264        osg::Timer_t startTick = osg::Timer::instance()->tick();
265
266        MergeGeodesVisitor visitor;
267        node->accept(visitor);
268
269        osg::Timer_t endTick = osg::Timer::instance()->tick();
270       
271        osg::notify(osg::INFO)<<"MERGE_GEODES took "<<osg::Timer::instance()->delta_s(startTick,endTick)<<std::endl;
272    }
273
274    if (options & CHECK_GEOMETRY)
275    {
276        osg::notify(osg::INFO)<<"Optimizer::optimize() doing CHECK_GEOMETRY"<<std::endl;
277
278        CheckGeometryVisitor mgv(this);
279        node->accept(mgv);
280    }
281
282    if (options & MERGE_GEOMETRY)
283    {
284        osg::notify(osg::INFO)<<"Optimizer::optimize() doing MERGE_GEOMETRY"<<std::endl;
285
286        osg::Timer_t startTick = osg::Timer::instance()->tick();
287
288        MergeGeometryVisitor mgv(this);
289        mgv.setTargetMaximumNumberOfVertices(10000);
290        node->accept(mgv);
291
292        osg::Timer_t endTick = osg::Timer::instance()->tick();
293
294        osg::notify(osg::INFO)<<"MERGE_GEOMETRY took "<<osg::Timer::instance()->delta_s(startTick,endTick)<<std::endl;
295    }
296   
297    if (options & TRISTRIP_GEOMETRY)
298    {
299        osg::notify(osg::INFO)<<"Optimizer::optimize() doing TRISTRIP_GEOMETRY"<<std::endl;
300
301        TriStripVisitor tsv(this);
302        node->accept(tsv);
303        tsv.stripify();
304    }
305
306    if (options & REMOVE_REDUNDANT_NODES)
307    {
308        osg::notify(osg::INFO)<<"Optimizer::optimize() doing REMOVE_REDUNDANT_NODES"<<std::endl;
309
310        RemoveEmptyNodesVisitor renv(this);
311        node->accept(renv);
312        renv.removeEmptyNodes();
313
314        RemoveRedundantNodesVisitor rrnv(this);
315        node->accept(rrnv);
316        rrnv.removeRedundantNodes();
317
318    }
319   
320    if (options & FLATTEN_BILLBOARDS)
321    {
322        FlattenBillboardVisitor fbv(this);
323        node->accept(fbv);
324        fbv.process();
325    }
326
327    if (options & SPATIALIZE_GROUPS)
328    {
329        osg::notify(osg::INFO)<<"Optimizer::optimize() doing SPATIALIZE_GROUPS"<<std::endl;
330
331        SpatializeGroupsVisitor sv(this);
332        node->accept(sv);
333        sv.divide();
334    }
335
336    if (osg::getNotifyLevel()>=osg::INFO)
337    {
338        stats.reset();
339        node->accept(stats);
340        stats.totalUpStats();
341        osg::notify(osg::NOTICE)<<std::endl<<"Stats after:"<<std::endl;
342        stats.print(osg::notify(osg::NOTICE));
343    }
344}
345
346
347////////////////////////////////////////////////////////////////////////////
348// Tessellate geometry - eg break complex POLYGONS into triangles, strips, fans..
349////////////////////////////////////////////////////////////////////////////
350void Optimizer::TessellateVisitor::apply(osg::Geode& geode)
351{
352    for(unsigned int i=0;i<geode.getNumDrawables();++i)
353    {
354        osg::Geometry* geom = dynamic_cast<osg::Geometry*>(geode.getDrawable(i));
355        if (geom) {
356            osgUtil::Tessellator Tessellator;
357            Tessellator.retessellatePolygons(*geom);
358        }
359    }
360    traverse(geode);
361}
362
363
364////////////////////////////////////////////////////////////////////////////
365// Optimize State Visitor
366////////////////////////////////////////////////////////////////////////////
367
368template<typename T>
369struct LessDerefFunctor
370{
371    bool operator () (const T* lhs,const T* rhs) const
372    {
373        return (*lhs<*rhs);
374    }
375};
376
377struct LessStateSetFunctor
378{
379    bool operator () (const osg::StateSet* lhs,const osg::StateSet* rhs) const
380    {
381        return (*lhs<*rhs);
382    }
383};
384
385
386
387void Optimizer::StateVisitor::reset()
388{
389    _statesets.clear();
390}
391
392void Optimizer::StateVisitor::addStateSet(osg::StateSet* stateset,osg::Object* obj)
393{
394    _statesets[stateset].insert(obj);
395}
396
397void Optimizer::StateVisitor::apply(osg::Node& node)
398{
399   
400    osg::StateSet* ss = node.getStateSet();
401    if (ss && ss->getDataVariance()==osg::Object::STATIC)
402    {
403        if (isOperationPermissibleForObject(&node) &&
404            isOperationPermissibleForObject(ss))
405        {
406            addStateSet(ss,&node);
407        }
408    }
409
410    traverse(node);
411}
412
413void Optimizer::StateVisitor::apply(osg::Geode& geode)
414{
415    if (!isOperationPermissibleForObject(&geode)) return;
416
417    osg::StateSet* ss = geode.getStateSet();
418   
419   
420    if (ss && ss->getDataVariance()==osg::Object::STATIC)
421    {
422        if (isOperationPermissibleForObject(ss))
423        {
424            addStateSet(ss,&geode);
425        }
426    }
427    for(unsigned int i=0;i<geode.getNumDrawables();++i)
428    {
429        osg::Drawable* drawable = geode.getDrawable(i);
430        if (drawable)
431        {
432            ss = drawable->getStateSet();
433            if (ss && ss->getDataVariance()==osg::Object::STATIC)
434            {
435                if (isOperationPermissibleForObject(drawable) &&
436                    isOperationPermissibleForObject(ss))
437                {
438                    addStateSet(ss,drawable);
439                }
440            }
441        }
442    }
443}
444
445void Optimizer::StateVisitor::optimize()
446{
447    osg::notify(osg::INFO) << "Num of StateSet="<<_statesets.size()<< std::endl;
448
449    {
450        // create map from state attributes to stateset which contain them.
451        typedef std::pair<osg::StateSet*,unsigned int>      StateSetUnitPair;
452        typedef std::set<StateSetUnitPair>                  StateSetList;
453        typedef std::map<osg::StateAttribute*,StateSetList> AttributeToStateSetMap;
454        AttributeToStateSetMap attributeToStateSetMap;
455
456        // create map from uniforms to stateset when contain them.
457        typedef std::set<osg::StateSet*>                    StateSetSet;
458        typedef std::map<osg::Uniform*,StateSetSet>         UniformToStateSetMap;
459       
460        const unsigned int NON_TEXTURE_ATTRIBUTE = 0xffffffff;
461       
462        UniformToStateSetMap  uniformToStateSetMap;
463
464        // NOTE - TODO will need to track state attribute override value too.
465
466        for(StateSetMap::iterator sitr=_statesets.begin();
467            sitr!=_statesets.end();
468            ++sitr)
469        {
470            osg::StateSet::AttributeList& attributes = sitr->first->getAttributeList();
471            for(osg::StateSet::AttributeList::iterator aitr= attributes.begin();
472                aitr!=attributes.end();
473                ++aitr)
474            {
475                if (optimize(aitr->second.first->getDataVariance()))
476                {
477                    attributeToStateSetMap[aitr->second.first.get()].insert(StateSetUnitPair(sitr->first,NON_TEXTURE_ATTRIBUTE));
478                }
479            }
480
481
482            osg::StateSet::TextureAttributeList& texAttributes = sitr->first->getTextureAttributeList();
483            for(unsigned int unit=0;unit<texAttributes.size();++unit)
484            {
485                osg::StateSet::AttributeList& attributes = texAttributes[unit];
486                for(osg::StateSet::AttributeList::iterator aitr= attributes.begin();
487                    aitr!=attributes.end();
488                    ++aitr)
489                {
490                    if (optimize(aitr->second.first->getDataVariance()))
491                    {
492                        attributeToStateSetMap[aitr->second.first.get()].insert(StateSetUnitPair(sitr->first,unit));
493                    }
494                }
495            }
496
497
498            osg::StateSet::UniformList& uniforms = sitr->first->getUniformList();
499            for(osg::StateSet::UniformList::iterator uitr= uniforms.begin();
500                uitr!=uniforms.end();
501                ++uitr)
502            {
503                if (optimize(uitr->second.first->getDataVariance()))
504                {
505                    uniformToStateSetMap[uitr->second.first.get()].insert(sitr->first);
506                }
507            }
508
509        }
510
511        if (attributeToStateSetMap.size()>=2)
512        {
513            // create unique set of state attribute pointers.
514            typedef std::vector<osg::StateAttribute*> AttributeList;
515            AttributeList attributeList;
516
517            for(AttributeToStateSetMap::iterator aitr=attributeToStateSetMap.begin();
518                aitr!=attributeToStateSetMap.end();
519                ++aitr)
520            {
521                attributeList.push_back(aitr->first);
522            }
523
524            // sort the attributes so that equal attributes sit along side each
525            // other.
526            std::sort(attributeList.begin(),attributeList.end(),LessDerefFunctor<osg::StateAttribute>());
527
528            osg::notify(osg::INFO) << "state attribute list"<< std::endl;
529            for(AttributeList::iterator aaitr = attributeList.begin();
530                aaitr!=attributeList.end();
531                ++aaitr)
532            {
533                osg::notify(osg::INFO) << "    "<<*aaitr << "  "<<(*aaitr)->className()<< std::endl;
534            }
535
536            osg::notify(osg::INFO) << "searching for duplicate attributes"<< std::endl;
537            // find the duplicates.
538            AttributeList::iterator first_unique = attributeList.begin();
539            AttributeList::iterator current = first_unique;
540            ++current;
541            for(; current!=attributeList.end();++current)
542            {
543                if (**current==**first_unique)
544                {
545                    osg::notify(osg::INFO) << "    found duplicate "<<(*current)->className()<<"  first="<<*first_unique<<"  current="<<*current<< std::endl;
546                    StateSetList& statesetlist = attributeToStateSetMap[*current];
547                    for(StateSetList::iterator sitr=statesetlist.begin();
548                        sitr!=statesetlist.end();
549                        ++sitr)
550                    {
551                        osg::notify(osg::INFO) << "       replace duplicate "<<*current<<" with "<<*first_unique<< std::endl;
552                        osg::StateSet* stateset = sitr->first;
553                        unsigned int unit = sitr->second;
554                        if (unit==NON_TEXTURE_ATTRIBUTE) stateset->setAttribute(*first_unique);
555                        else stateset->setTextureAttribute(unit,*first_unique);
556                    }
557                }
558                else first_unique = current;
559            }
560        }
561       
562               
563        if (uniformToStateSetMap.size()>=2)
564        {
565            // create unique set of uniform pointers.
566            typedef std::vector<osg::Uniform*> UniformList;
567            UniformList uniformList;
568
569            for(UniformToStateSetMap::iterator aitr=uniformToStateSetMap.begin();
570                aitr!=uniformToStateSetMap.end();
571                ++aitr)
572            {
573                uniformList.push_back(aitr->first);
574            }
575
576            // sort the uniforms so that equal uniforms sit along side each
577            // other.
578            std::sort(uniformList.begin(),uniformList.end(),LessDerefFunctor<osg::Uniform>());
579
580            osg::notify(osg::INFO) << "state uniform list"<< std::endl;
581            for(UniformList::iterator uuitr = uniformList.begin();
582                uuitr!=uniformList.end();
583                ++uuitr)
584            {
585                osg::notify(osg::INFO) << "    "<<*uuitr << "  "<<(*uuitr)->getName()<< std::endl;
586            }
587
588            osg::notify(osg::INFO) << "searching for duplicate uniforms"<< std::endl;
589            // find the duplicates.
590            UniformList::iterator first_unique_uniform = uniformList.begin();
591            UniformList::iterator current_uniform = first_unique_uniform;
592            ++current_uniform;
593            for(; current_uniform!=uniformList.end();++current_uniform)
594            {
595                if ((**current_uniform)==(**first_unique_uniform))
596                {
597                    osg::notify(osg::INFO) << "    found duplicate uniform "<<(*current_uniform)->getName()<<"  first_unique_uniform="<<*first_unique_uniform<<"  current_uniform="<<*current_uniform<< std::endl;
598                    StateSetSet& statesetset = uniformToStateSetMap[*current_uniform];
599                    for(StateSetSet::iterator sitr=statesetset.begin();
600                        sitr!=statesetset.end();
601                        ++sitr)
602                    {
603                        osg::notify(osg::INFO) << "       replace duplicate "<<*current_uniform<<" with "<<*first_unique_uniform<< std::endl;
604                        osg::StateSet* stateset = *sitr;
605                        stateset->addUniform(*first_unique_uniform);
606                    }
607                }
608                else first_unique_uniform = current_uniform;
609            }
610        }
611
612    }
613   
614    // duplicate state attributes removed.
615    // now need to look at duplicate state sets.
616    if (_statesets.size()>=2)
617    {
618        // create the list of stateset's.
619        typedef std::vector<osg::StateSet*> StateSetSortList;
620        StateSetSortList statesetSortList;
621        for(StateSetMap::iterator ssitr=_statesets.begin();
622            ssitr!=_statesets.end();
623            ++ssitr)
624        {
625            statesetSortList.push_back(ssitr->first);
626        }
627
628
629        // sort the StateSet's so that equal StateSet's sit along side each
630        // other.
631        std::sort(statesetSortList.begin(),statesetSortList.end(),LessDerefFunctor<osg::StateSet>());
632
633        osg::notify(osg::INFO) << "searching for duplicate attributes"<< std::endl;
634        // find the duplicates.
635        StateSetSortList::iterator first_unique = statesetSortList.begin();
636        StateSetSortList::iterator current = first_unique; ++current;
637        for(; current!=statesetSortList.end();++current)
638        {
639            if (**current==**first_unique)
640            {
641                osg::notify(osg::INFO) << "    found duplicate "<<(*current)->className()<<"  first="<<*first_unique<<"  current="<<*current<< std::endl;
642                ObjectSet& objSet = _statesets[*current];
643                for(ObjectSet::iterator sitr=objSet.begin();
644                    sitr!=objSet.end();
645                    ++sitr)
646                {
647                    osg::notify(osg::INFO) << "       replace duplicate "<<*current<<" with "<<*first_unique<< std::endl;
648                    osg::Object* obj = *sitr;
649                    osg::Drawable* drawable = dynamic_cast<osg::Drawable*>(obj);
650                    if (drawable)
651                    {
652                        drawable->setStateSet(*first_unique);
653                    }
654                    else 
655                    {
656                        osg::Node* node = dynamic_cast<osg::Node*>(obj);
657                        if (node)
658                        {
659                            node->setStateSet(*first_unique);
660                        }
661                    }
662                }
663            }
664            else first_unique = current;
665        }
666    }
667   
668}
669
670////////////////////////////////////////////////////////////////////////////
671// Flatten static transforms
672////////////////////////////////////////////////////////////////////////////
673
674class CollectLowestTransformsVisitor : public BaseOptimizerVisitor
675{
676    public:
677
678
679        CollectLowestTransformsVisitor(Optimizer* optimizer=0):
680                    BaseOptimizerVisitor(optimizer,Optimizer::FLATTEN_STATIC_TRANSFORMS),
681                    _transformFunctor(osg::Matrix())
682        {
683            setTraversalMode(osg::NodeVisitor::TRAVERSE_PARENTS);
684        }
685
686        virtual void apply(osg::Node& node)
687        {
688            if (node.getNumParents())
689            {
690                traverse(node);
691            }
692            else
693            {
694                // for all current objects mark a NULL transform for them.
695                registerWithCurrentObjects(0);
696            }
697        }
698
699        virtual void apply(osg::LOD& lod)
700        {
701            _currentObjectList.push_back(&lod);
702
703            traverse(lod);
704
705            _currentObjectList.pop_back();
706        }
707
708        virtual void apply(osg::Transform& transform)
709        {
710            // for all current objects associated this transform with them.
711            registerWithCurrentObjects(&transform);
712        }
713       
714        virtual void apply(osg::Geode& geode)
715        {
716            traverse(geode);
717        }
718       
719        virtual void apply(osg::Billboard& geode)
720        {
721            traverse(geode);
722        }
723       
724
725        void collectDataFor(osg::Node* node)
726        {
727            _currentObjectList.push_back(node);
728           
729            node->accept(*this);
730           
731            _currentObjectList.pop_back();
732        }
733
734        void collectDataFor(osg::Billboard* billboard)
735        {
736            _currentObjectList.push_back(billboard);
737           
738            billboard->accept(*this);
739           
740            _currentObjectList.pop_back();
741        }
742       
743        void collectDataFor(osg::Drawable* drawable)
744        {
745            _currentObjectList.push_back(drawable);
746
747            const osg::Drawable::ParentList& parents = drawable->getParents();
748            for(osg::Drawable::ParentList::const_iterator itr=parents.begin();
749                itr!=parents.end();
750                ++itr)
751            {
752                (*itr)->accept(*this);
753            }
754
755            _currentObjectList.pop_back();
756        }
757
758        void setUpMaps();
759        void disableTransform(osg::Transform* transform);
760        bool removeTransforms(osg::Node* nodeWeCannotRemove);
761
762        inline bool isOperationPermissibleForObject(const osg::Object* object) const
763        {
764            const osg::Drawable* drawable = dynamic_cast<const osg::Drawable*>(object);
765            if (drawable) return isOperationPermissibleForObject(drawable);
766           
767            const osg::Node* node = dynamic_cast<const osg::Node*>(object);
768            if (node) return isOperationPermissibleForObject(node);
769
770            return true;
771        }
772
773        inline bool isOperationPermissibleForObject(const osg::Drawable* drawable) const
774        {
775            // disable if cannot apply transform functor.
776            if (drawable && !drawable->supports(_transformFunctor)) return false;
777            return BaseOptimizerVisitor::isOperationPermissibleForObject(drawable);
778        }
779           
780        inline bool isOperationPermissibleForObject(const osg::Node* node) const
781        {
782            // disable if object is a light point node.
783            if (strcmp(node->className(),"LightPointNode")==0) return false;
784            if (dynamic_cast<const osg::ProxyNode*>(node)) return false;
785            if (dynamic_cast<const osg::PagedLOD*>(node)) return false;
786            return BaseOptimizerVisitor::isOperationPermissibleForObject(node);
787        }
788
789    protected:       
790
791        struct TransformStruct
792        {
793            typedef std::set<osg::Object*> ObjectSet;
794
795            TransformStruct():_canBeApplied(true) {}
796
797            void add(osg::Object* obj)
798            {
799                _objectSet.insert(obj);
800            }
801
802            bool        _canBeApplied;
803            ObjectSet   _objectSet;
804        };
805
806        struct ObjectStruct
807        {
808            typedef std::set<osg::Transform*> TransformSet;
809
810            ObjectStruct():_canBeApplied(true),_moreThanOneMatrixRequired(false) {}
811
812            void add(osg::Transform* transform)
813            {
814                if (transform)
815                {
816                    if (transform->getDataVariance()!=osg::Transform::STATIC) _moreThanOneMatrixRequired=true;
817                    else if (transform->getReferenceFrame()!=osg::Transform::RELATIVE_RF) _moreThanOneMatrixRequired=true;
818                    else
819                    {
820                        if (_transformSet.empty()) transform->computeLocalToWorldMatrix(_firstMatrix,0);
821                        else
822                        {
823                            osg::Matrix matrix;
824                            transform->computeLocalToWorldMatrix(matrix,0);
825                            if (_firstMatrix!=matrix) _moreThanOneMatrixRequired=true;
826                        }
827                    }
828                }
829                else
830                {
831                    if (!_transformSet.empty())
832                    {
833                        if (!_firstMatrix.isIdentity()) _moreThanOneMatrixRequired=true;
834                    }
835
836                }
837                _transformSet.insert(transform);
838            }
839
840            bool            _canBeApplied;
841            bool            _moreThanOneMatrixRequired;
842            osg::Matrix     _firstMatrix;
843            TransformSet    _transformSet;
844        };   
845
846
847        void registerWithCurrentObjects(osg::Transform* transform)
848        {
849            for(ObjectList::iterator itr=_currentObjectList.begin();
850                itr!=_currentObjectList.end();
851                ++itr)
852            {
853                _objectMap[*itr].add(transform);
854            }
855        }
856
857        typedef std::map<osg::Transform*,TransformStruct>   TransformMap;
858        typedef std::map<osg::Object*,ObjectStruct>         ObjectMap;
859        typedef std::vector<osg::Object*>                   ObjectList;
860
861        void disableObject(osg::Object* object)
862        {
863            disableObject(_objectMap.find(object));
864        }
865
866        void disableObject(ObjectMap::iterator itr);
867        void doTransform(osg::Object* obj,osg::Matrix& matrix);
868       
869        osgUtil::TransformAttributeFunctor _transformFunctor;
870        TransformMap    _transformMap;
871        ObjectMap       _objectMap;
872        ObjectList      _currentObjectList;
873
874};
875
876
877void CollectLowestTransformsVisitor::doTransform(osg::Object* obj,osg::Matrix& matrix)
878{
879    osg::Drawable* drawable = dynamic_cast<osg::Drawable*>(obj);
880    if (drawable)
881    {
882        osgUtil::TransformAttributeFunctor tf(matrix);
883        drawable->accept(tf);
884        drawable->dirtyBound();
885        drawable->dirtyDisplayList();
886
887        return;
888    }
889
890    osg::LOD* lod = dynamic_cast<osg::LOD*>(obj);
891    if (lod)
892    {
893        osg::Matrix matrix_no_trans = matrix;
894        matrix_no_trans.setTrans(0.0f,0.0f,0.0f);
895       
896        osg::Vec3 v111(1.0f,1.0f,1.0f);
897        osg::Vec3 new_v111 = v111*matrix_no_trans;
898        float ratio = new_v111.length()/v111.length();
899
900        // move center point.
901        lod->setCenter(lod->getCenter()*matrix);
902       
903        // adjust ranges to new scale.
904        for(unsigned int i=0;i<lod->getNumRanges();++i)
905        {
906            lod->setRange(i,lod->getMinRange(i)*ratio,lod->getMaxRange(i)*ratio);
907        }
908       
909        lod->dirtyBound();
910        return;
911    }
912
913    osg::Billboard* billboard = dynamic_cast<osg::Billboard*>(obj);
914    if (billboard)
915    {
916        osg::Matrix matrix_no_trans = matrix;
917        matrix_no_trans.setTrans(0.0f,0.0f,0.0f);
918 
919        osgUtil::TransformAttributeFunctor tf(matrix_no_trans);
920
921        osg::Vec3 axis = osg::Matrix::transform3x3(tf._im,billboard->getAxis());
922        axis.normalize();
923        billboard->setAxis(axis);
924
925        osg::Vec3 normal = osg::Matrix::transform3x3(tf._im,billboard->getNormal());
926        normal.normalize();
927        billboard->setNormal(normal);
928
929
930        for(unsigned int i=0;i<billboard->getNumDrawables();++i)
931        {
932            billboard->setPosition(i,billboard->getPosition(i)*matrix);
933            billboard->getDrawable(i)->accept(tf);
934            billboard->getDrawable(i)->dirtyBound();
935        }
936       
937        billboard->dirtyBound();
938
939        return;
940    }
941}
942
943void CollectLowestTransformsVisitor::disableObject(ObjectMap::iterator itr)
944{
945    if (itr==_objectMap.end())
946    {
947        return;
948    }   
949
950    if (itr->second._canBeApplied)
951    {
952        // we havn't been disabled yet so we need to disable,
953        itr->second._canBeApplied = false;
954
955        // and then inform everybody we have been disabled.
956        for(ObjectStruct::TransformSet::iterator titr = itr->second._transformSet.begin();
957            titr != itr->second._transformSet.end();
958            ++titr)
959        {
960            disableTransform(*titr);
961        }
962    }
963}
964
965void CollectLowestTransformsVisitor::disableTransform(osg::Transform* transform)
966{
967    TransformMap::iterator itr=_transformMap.find(transform);
968    if (itr==_transformMap.end())
969    {
970        return;
971    }   
972
973    if (itr->second._canBeApplied)
974    {
975   
976        // we havn't been disabled yet so we need to disable,
977        itr->second._canBeApplied = false;
978        // and then inform everybody we have been disabled.
979        for(TransformStruct::ObjectSet::iterator oitr = itr->second._objectSet.begin();
980            oitr != itr->second._objectSet.end();
981            ++oitr)
982        {
983            disableObject(*oitr);
984        }
985    }
986}
987
988void CollectLowestTransformsVisitor::setUpMaps()
989{
990    // create the TransformMap from the ObjectMap
991    ObjectMap::iterator oitr;
992    for(oitr=_objectMap.begin();
993        oitr!=_objectMap.end();
994        ++oitr)
995    {
996        osg::Object* object = oitr->first;
997        ObjectStruct& os = oitr->second;
998       
999        for(ObjectStruct::TransformSet::iterator titr = os._transformSet.begin();
1000            titr != os._transformSet.end();
1001            ++titr)
1002        {
1003            _transformMap[*titr].add(object);
1004        }
1005    }
1006
1007    // disable all the objects which have more than one matrix associated
1008    // with them, and then disable all transforms which have an object associated
1009    // them that can't be applied, and then disable all objects which have
1010    // disabled transforms associated, recursing until all disabled
1011    // associativity.
1012    // and disable all objects that the operation is not permisable for)
1013    for(oitr=_objectMap.begin();
1014        oitr!=_objectMap.end();
1015        ++oitr)
1016    {
1017        osg::Object* object = oitr->first;
1018        ObjectStruct& os = oitr->second;
1019        if (os._canBeApplied)
1020        {
1021            if (os._moreThanOneMatrixRequired || !isOperationPermissibleForObject(object))
1022            {
1023                disableObject(oitr);
1024            }
1025        }
1026    }
1027
1028}
1029
1030bool CollectLowestTransformsVisitor::removeTransforms(osg::Node* nodeWeCannotRemove)
1031{
1032    // transform the objects that can be applied.
1033    for(ObjectMap::iterator oitr=_objectMap.begin();
1034        oitr!=_objectMap.end();
1035        ++oitr)
1036    {
1037        osg::Object* object = oitr->first;
1038        ObjectStruct& os = oitr->second;
1039        if (os._canBeApplied)
1040        {
1041            doTransform(object,os._firstMatrix);
1042        }
1043    }
1044
1045
1046    bool transformRemoved = false;
1047
1048    // clean up the transforms.
1049    for(TransformMap::iterator titr=_transformMap.begin();
1050        titr!=_transformMap.end();
1051        ++titr)
1052    {
1053        if (titr->second._canBeApplied)
1054        {
1055            if (titr->first!=nodeWeCannotRemove)
1056            {
1057                transformRemoved = true;
1058
1059                osg::ref_ptr<osg::Transform> transform = titr->first;
1060                osg::ref_ptr<osg::Group>     group = new osg::Group;
1061                group->setName( transform->getName() );
1062                group->setDataVariance(osg::Object::STATIC);
1063                group->setNodeMask(transform->getNodeMask());
1064                group->setStateSet(transform->getStateSet());
1065                for(unsigned int i=0;i<transform->getNumChildren();++i)
1066                {
1067                    for(unsigned int j=0;j<transform->getNumParents();++j)
1068                    {
1069                        group->addChild(transform->getChild(i));
1070                    }
1071                }
1072
1073                for(int i2=transform->getNumParents()-1;i2>=0;--i2)
1074                {
1075                    transform->getParent(i2)->replaceChild(transform.get(),group.get());
1076                }
1077            }
1078            else
1079            {
1080                osg::MatrixTransform* mt = dynamic_cast<osg::MatrixTransform*>(titr->first);
1081                if (mt) mt->setMatrix(osg::Matrix::identity());
1082                else
1083                {
1084                    osg::PositionAttitudeTransform* pat = dynamic_cast<osg::PositionAttitudeTransform*>(titr->first);
1085                    if (pat)
1086                    {
1087                        pat->setPosition(osg::Vec3(0.0f,0.0f,0.0f));
1088                        pat->setAttitude(osg::Quat());
1089                        pat->setPivotPoint(osg::Vec3(0.0f,0.0f,0.0f));
1090                    }
1091                    else
1092                    {
1093                        osg::notify(osg::WARN)<<"Warning:: during Optimize::CollectLowestTransformsVisitor::removeTransforms(Node*)"<<std::endl;
1094                        osg::notify(osg::WARN)<<"          unhandled of setting of indentity matrix on "<< titr->first->className()<<std::endl;
1095                        osg::notify(osg::WARN)<<"          model will appear in the incorrect position."<<std::endl;
1096                    }
1097                }
1098               
1099            }               
1100        }
1101    }
1102    _objectMap.clear();
1103    _transformMap.clear();
1104   
1105    return transformRemoved;
1106}
1107
1108void Optimizer::FlattenStaticTransformsVisitor::apply(osg::Node& node)
1109{
1110    if (strcmp(node.className(),"LightPointNode")==0)
1111    {
1112        _excludedNodeSet.insert(&node);
1113    }
1114    traverse(node);
1115}
1116
1117
1118void Optimizer::FlattenStaticTransformsVisitor::apply(osg::ProxyNode& node)
1119{
1120    _excludedNodeSet.insert(&node);
1121
1122    traverse(node);
1123}
1124
1125void Optimizer::FlattenStaticTransformsVisitor::apply(osg::PagedLOD& node)
1126{
1127    _excludedNodeSet.insert(&node);
1128
1129    traverse(node);
1130}
1131
1132
1133void Optimizer::FlattenStaticTransformsVisitor::apply(osg::Geode& geode)
1134{
1135    if (!_transformStack.empty())
1136    {
1137        for(unsigned int i=0;i<geode.getNumDrawables();++i)
1138        {
1139            osg::Geometry *geometry = geode.getDrawable(i)->asGeometry();
1140            if((geometry) && (isOperationPermissibleForObject(&geode)) && (isOperationPermissibleForObject(geometry)))
1141            {
1142                if(geometry->getVertexArray() && geometry->getVertexArray()->referenceCount() > 1) {
1143                    geometry->setVertexArray(dynamic_cast<osg::Array*>(geometry->getVertexArray()->clone(osg::CopyOp::DEEP_COPY_ALL)));
1144                }
1145                if(geometry->getNormalArray() && geometry->getNormalArray()->referenceCount() > 1) {
1146                    geometry->setNormalArray(dynamic_cast<osg::Array*>(geometry->getNormalArray()->clone(osg::CopyOp::DEEP_COPY_ALL)));
1147                }
1148            }
1149            _drawableSet.insert(geode.getDrawable(i));
1150        }
1151    }
1152}
1153
1154void Optimizer::FlattenStaticTransformsVisitor::apply(osg::Billboard& billboard)
1155{
1156    if (!_transformStack.empty())
1157    {
1158        _billboardSet.insert(&billboard);
1159    }
1160}
1161
1162void Optimizer::FlattenStaticTransformsVisitor::apply(osg::Transform& transform)
1163{
1164    if (!_transformStack.empty())
1165    {
1166        // we need to disable any transform higher in the list.
1167        _transformSet.insert(_transformStack.back());
1168    }
1169
1170    _transformStack.push_back(&transform);
1171
1172    // simple traverse the children as if this Transform didn't exist.
1173    traverse(transform);
1174
1175    _transformStack.pop_back();
1176}
1177
1178bool Optimizer::FlattenStaticTransformsVisitor::removeTransforms(osg::Node* nodeWeCannotRemove)
1179{
1180    CollectLowestTransformsVisitor cltv(_optimizer);
1181
1182    for(NodeSet::iterator nitr=_excludedNodeSet.begin();
1183        nitr!=_excludedNodeSet.end();
1184        ++nitr)
1185    {
1186        cltv.collectDataFor(*nitr);
1187    }
1188
1189    for(DrawableSet::iterator ditr=_drawableSet.begin();
1190        ditr!=_drawableSet.end();
1191        ++ditr)
1192    {
1193        cltv.collectDataFor(*ditr);
1194    }
1195
1196    for(BillboardSet::iterator bitr=_billboardSet.begin();
1197        bitr!=_billboardSet.end();
1198        ++bitr)
1199    {
1200        cltv.collectDataFor(*bitr);
1201    }
1202   
1203    cltv.setUpMaps();
1204   
1205    for(TransformSet::iterator titr=_transformSet.begin();
1206        titr!=_transformSet.end();
1207        ++titr)
1208    {
1209        cltv.disableTransform(*titr);
1210    }
1211   
1212
1213    return cltv.removeTransforms(nodeWeCannotRemove);
1214}
1215
1216////////////////////////////////////////////////////////////////////////////
1217// CombineStatucTransforms
1218////////////////////////////////////////////////////////////////////////////
1219
1220void Optimizer::CombineStaticTransformsVisitor::apply(osg::MatrixTransform& transform)
1221{
1222    if (transform.getDataVariance()==osg::Object::STATIC &&
1223        transform.getNumChildren()==1 &&
1224        transform.getChild(0)->asTransform()!=0 &&
1225        transform.getChild(0)->asTransform()->asMatrixTransform()!=0 &&
1226        transform.getChild(0)->asTransform()->getDataVariance()==osg::Object::STATIC &&
1227        isOperationPermissibleForObject(&transform) && isOperationPermissibleForObject(transform.getChild(0)))
1228    {
1229        _transformSet.insert(&transform);
1230    }
1231   
1232    traverse(transform);
1233}
1234
1235bool Optimizer::CombineStaticTransformsVisitor::removeTransforms(osg::Node* nodeWeCannotRemove)
1236{
1237    if (nodeWeCannotRemove && nodeWeCannotRemove->asTransform()!=0 && nodeWeCannotRemove->asTransform()->asMatrixTransform()!=0)
1238    {
1239        // remove topmost node if it exists in the transform set.
1240        TransformSet::iterator itr = _transformSet.find(nodeWeCannotRemove->asTransform()->asMatrixTransform());
1241        if (itr!=_transformSet.end()) _transformSet.erase(itr);
1242    }
1243   
1244    bool transformRemoved = false;
1245
1246    while (!_transformSet.empty())
1247    {
1248        // get the first available transform to combine.
1249        osg::ref_ptr<osg::MatrixTransform> transform = *_transformSet.begin();
1250        _transformSet.erase(_transformSet.begin());
1251       
1252        if (transform->getNumChildren()==1 &&
1253            transform->getChild(0)->asTransform()!=0 &&
1254            transform->getChild(0)->asTransform()->asMatrixTransform()!=0 &&
1255            transform->getChild(0)->asTransform()->getDataVariance()==osg::Object::STATIC)
1256        {
1257            // now combine with its child.
1258            osg::MatrixTransform* child = transform->getChild(0)->asTransform()->asMatrixTransform();
1259           
1260            osg::Matrix newMatrix = child->getMatrix()*transform->getMatrix();
1261            child->setMatrix(newMatrix);
1262            if (transform->getStateSet())
1263            {
1264                if(child->getStateSet()) child->getStateSet()->merge(*transform->getStateSet());
1265                else child->setStateSet(transform->getStateSet());
1266            }
1267           
1268            transformRemoved = true;
1269
1270            osg::Node::ParentList parents = transform->getParents();
1271            for(osg::Node::ParentList::iterator pitr=parents.begin();
1272                pitr!=parents.end();
1273                ++pitr)
1274            {
1275                (*pitr)->replaceChild(transform.get(),child);
1276            }
1277           
1278        }
1279       
1280    }
1281    return transformRemoved;
1282}
1283
1284////////////////////////////////////////////////////////////////////////////
1285// RemoveEmptyNodes.
1286////////////////////////////////////////////////////////////////////////////
1287
1288void Optimizer::RemoveEmptyNodesVisitor::apply(osg::Geode& geode)
1289{
1290    for(int i=geode.getNumDrawables()-1;i>=0;--i)
1291    {
1292        osg::Geometry* geom = geode.getDrawable(i)->asGeometry();
1293        if (geom && geom->empty() && isOperationPermissibleForObject(geom))
1294        {
1295           geode.removeDrawables(i,1);
1296        }
1297    }
1298
1299    if (geode.getNumParents()>0)
1300    {
1301        if (geode.getNumDrawables()==0 && isOperationPermissibleForObject(&geode)) _redundantNodeList.insert(&geode);
1302    }
1303}
1304
1305void Optimizer::RemoveEmptyNodesVisitor::apply(osg::Group& group)
1306{
1307    if (group.getNumParents()>0)
1308    {
1309        // only remove empty groups, but not empty occluders.
1310        if (group.getNumChildren()==0 && isOperationPermissibleForObject(&group) &&
1311            (typeid(group)==typeid(osg::Group) || dynamic_cast<osg::Transform*>(&group)))
1312        {
1313            _redundantNodeList.insert(&group);
1314        }
1315    }
1316    traverse(group);
1317}
1318
1319void Optimizer::RemoveEmptyNodesVisitor::removeEmptyNodes()
1320{
1321
1322    NodeList newEmptyGroups;
1323
1324    // keep iterator through until scene graph is cleaned of empty nodes.
1325    while (!_redundantNodeList.empty())
1326    {
1327        for(NodeList::iterator itr=_redundantNodeList.begin();
1328            itr!=_redundantNodeList.end();
1329            ++itr)
1330        {
1331           
1332            osg::ref_ptr<osg::Node> nodeToRemove = (*itr);
1333           
1334            // take a copy of parents list since subsequent removes will modify the original one.
1335            osg::Node::ParentList parents = nodeToRemove->getParents();
1336
1337            for(osg::Node::ParentList::iterator pitr=parents.begin();
1338                pitr!=parents.end();
1339                ++pitr)
1340            {
1341                osg::Group* parent = *pitr;
1342                if (!dynamic_cast<osg::Sequence*>(parent) &&
1343                    !dynamic_cast<osg::Switch*>(parent) &&
1344                    strcmp(parent->className(),"MultiSwitch")!=0)
1345                {
1346                    parent->removeChild(nodeToRemove.get());
1347                    if (parent->getNumChildren()==0) newEmptyGroups.insert(*pitr);
1348                }
1349            }               
1350        }
1351
1352        _redundantNodeList.clear();
1353        _redundantNodeList.swap(newEmptyGroups);
1354    }
1355}
1356
1357
1358////////////////////////////////////////////////////////////////////////////
1359// RemoveRedundantNodes.
1360////////////////////////////////////////////////////////////////////////////
1361
1362bool Optimizer::RemoveRedundantNodesVisitor::isOperationPermissible(osg::Node& node)
1363{
1364    return node.getNumParents()>0 &&
1365           !node.getStateSet() &&
1366           !node.getUserData() &&
1367           !node.getUpdateCallback() &&
1368           !node.getEventCallback() &&
1369           !node.getUpdateCallback() &&
1370           node.getDescriptions().empty() &&
1371           isOperationPermissibleForObject(&node);   
1372}
1373
1374void Optimizer::RemoveRedundantNodesVisitor::apply(osg::Group& group)
1375{
1376    if (group.getNumChildren()==1 &&
1377        typeid(group)==typeid(osg::Group) &&
1378        isOperationPermissible(group))
1379    {
1380        _redundantNodeList.insert(&group);
1381    }
1382
1383    traverse(group);
1384}
1385
1386
1387
1388void Optimizer::RemoveRedundantNodesVisitor::apply(osg::Transform& transform)
1389{
1390    if (transform.getDataVariance()==osg::Object::STATIC &&
1391        isOperationPermissible(transform))
1392    {
1393        osg::Matrix matrix;
1394        transform.computeWorldToLocalMatrix(matrix,NULL);
1395        if (matrix.isIdentity())
1396        {
1397            _redundantNodeList.insert(&transform);
1398        }
1399    }
1400    traverse(transform);
1401}
1402
1403
1404void Optimizer::RemoveRedundantNodesVisitor::removeRedundantNodes()
1405{
1406
1407    for(NodeList::iterator itr=_redundantNodeList.begin();
1408        itr!=_redundantNodeList.end();
1409        ++itr)
1410    {
1411        osg::ref_ptr<osg::Group> group = dynamic_cast<osg::Group*>(*itr);
1412        if (group.valid())
1413        {
1414            // take a copy of parents list since subsequent removes will modify the original one.
1415            osg::Node::ParentList parents = group->getParents();
1416
1417            if (group->getNumChildren()==1)
1418            {
1419                osg::Node* child = group->getChild(0);
1420                for(osg::Node::ParentList::iterator pitr=parents.begin();
1421                    pitr!=parents.end();
1422                    ++pitr)
1423                {
1424                    (*pitr)->replaceChild(group.get(),child);
1425                }
1426
1427            }
1428
1429        }
1430        else
1431        {
1432            osg::notify(osg::WARN)<<"Optimizer::RemoveRedundantNodesVisitor::removeRedundantNodes() - failed dynamic_cast"<<std::endl;
1433        }                               
1434    }
1435    _redundantNodeList.clear();
1436}
1437
1438
1439////////////////////////////////////////////////////////////////////////////
1440// RemoveLoadedProxyNodesVisitor.
1441////////////////////////////////////////////////////////////////////////////
1442
1443void Optimizer::RemoveLoadedProxyNodesVisitor::apply(osg::ProxyNode& proxyNode)
1444{
1445    if (proxyNode.getNumParents()>0 && proxyNode.getNumFileNames()==proxyNode.getNumChildren())
1446    {
1447        if (isOperationPermissibleForObject(&proxyNode))
1448        {
1449            _redundantNodeList.insert(&proxyNode);
1450        }
1451    }
1452    traverse(proxyNode);
1453}
1454
1455void Optimizer::RemoveLoadedProxyNodesVisitor::removeRedundantNodes()
1456{
1457
1458    for(NodeList::iterator itr=_redundantNodeList.begin();
1459        itr!=_redundantNodeList.end();
1460        ++itr)
1461    {
1462        osg::ref_ptr<osg::Group> group = dynamic_cast<osg::Group*>(*itr);
1463        if (group.valid())
1464        {
1465           
1466            // first check to see if data was attached to the ProxyNode that we need to keep.
1467            bool keepData = false;
1468            if (!group->getName().empty()) keepData = true;
1469            if (!group->getDescriptions().empty()) keepData = true;
1470            if (group->getNodeMask()) keepData = true;
1471            if (group->getUpdateCallback()) keepData = true;
1472            if (group->getEventCallback()) keepData = true;
1473            if (group->getCullCallback()) keepData = true;
1474
1475            if (keepData)
1476            {
1477                // create a group to store all proxy's children and data.
1478                osg::ref_ptr<osg::Group> newGroup = new osg::Group(*group,osg::CopyOp::SHALLOW_COPY);
1479               
1480
1481                // take a copy of parents list since subsequent removes will modify the original one.
1482                osg::Node::ParentList parents = group->getParents();
1483
1484                for(osg::Node::ParentList::iterator pitr=parents.begin();
1485                    pitr!=parents.end();
1486                    ++pitr)
1487                {
1488                    (*pitr)->replaceChild(group.get(),newGroup.get());
1489                }
1490
1491            }
1492            else
1493            {
1494                // take a copy of parents list since subsequent removes will modify the original one.
1495                osg::Node::ParentList parents = group->getParents();
1496
1497                for(osg::Node::ParentList::iterator pitr=parents.begin();
1498                    pitr!=parents.end();
1499                    ++pitr)
1500                {
1501                    (*pitr)->removeChild(group.get());
1502                    for(unsigned int i=0;i<group->getNumChildren();++i)
1503                    {
1504                        osg::Node* child = group->getChild(i);
1505                        (*pitr)->addChild(child);
1506                    }
1507
1508                }
1509            }
1510        }
1511        else
1512        {
1513            osg::notify(osg::WARN)<<"Optimizer::RemoveLoadedProxyNodesVisitor::removeRedundantNodes() - failed dynamic_cast"<<std::endl;
1514        }                               
1515    }
1516    _redundantNodeList.clear();
1517}
1518
1519
1520
1521////////////////////////////////////////////////////////////////////////////
1522// combine LOD's.
1523////////////////////////////////////////////////////////////////////////////
1524void Optimizer::CombineLODsVisitor::apply(osg::LOD& lod)
1525{
1526    if (dynamic_cast<osg::PagedLOD*>(&lod)==0)
1527    {   
1528        for(unsigned int i=0;i<lod.getNumParents();++i)
1529        {
1530            if (typeid(*lod.getParent(i))==typeid(osg::Group))
1531            {
1532                if (isOperationPermissibleForObject(&lod))
1533                {
1534                    _groupList.insert(lod.getParent(i));
1535                }
1536            }
1537        }
1538    }
1539    traverse(lod);
1540}
1541
1542
1543void Optimizer::CombineLODsVisitor::combineLODs()
1544{
1545    for(GroupList::iterator itr=_groupList.begin();
1546        itr!=_groupList.end();
1547        ++itr)
1548    {
1549        osg::Group* group = *itr;
1550
1551        typedef std::set<osg::LOD*>  LODSet;
1552
1553        LODSet    lodChildren;
1554
1555        for(unsigned int i=0;i<group->getNumChildren();++i)
1556        {
1557            osg::Node* child = group->getChild(i);
1558            osg::LOD* lod = dynamic_cast<osg::LOD*>(child);
1559            if (lod)
1560            {
1561                lodChildren.insert(lod);
1562            }
1563        }
1564
1565        if (lodChildren.size()>=2)
1566        {
1567            osg::BoundingBox bb;
1568            LODSet::iterator lod_itr;
1569            float smallestRadius=FLT_MAX;
1570            for(lod_itr=lodChildren.begin();
1571                lod_itr!=lodChildren.end();
1572                ++lod_itr)
1573            {
1574                float r = (*lod_itr)->getBound().radius();
1575                if (r>=0 && r<smallestRadius) smallestRadius = r;
1576                bb.expandBy((*lod_itr)->getCenter());
1577            }
1578            if (bb.radius()<smallestRadius*0.1f)
1579            {
1580                typedef std::pair<float,float> RangePair;
1581                typedef std::multimap<RangePair,osg::Node*> RangeMap;
1582                RangeMap rangeMap;
1583                for(lod_itr=lodChildren.begin();
1584                    lod_itr!=lodChildren.end();
1585                    ++lod_itr)
1586                {
1587
1588                    osg::LOD* lod = *lod_itr;
1589                    for(unsigned int i=0;i<lod->getNumRanges();++i)
1590                    {
1591                        rangeMap.insert(RangeMap::value_type(RangePair(lod->getMinRange(i),lod->getMaxRange(i)),lod->getChild(i)));
1592                    }
1593
1594                }
1595
1596                // create new LOD containing all other LOD's children.
1597                osg::LOD* newLOD = new osg::LOD;
1598                newLOD->setName("newLOD");
1599                newLOD->setCenter(bb.center());
1600
1601                int i=0;
1602                for(RangeMap::iterator c_itr=rangeMap.begin();
1603                    c_itr!=rangeMap.end();
1604                    ++c_itr,++i)
1605                {
1606                    newLOD->setRange(i,c_itr->first.first,c_itr->first.second);
1607                    newLOD->addChild(c_itr->second);
1608                }
1609
1610                // add LOD into parent.
1611                group->addChild(newLOD);
1612
1613                // remove all the old LOD's from group.
1614                for(lod_itr=lodChildren.begin();
1615                    lod_itr!=lodChildren.end();
1616                    ++lod_itr)
1617                {
1618                    group->removeChild(*lod_itr);
1619                }
1620
1621            }
1622
1623        }
1624    }
1625    _groupList.clear();
1626}
1627
1628////////////////////////////////////////////////////////////////////////////
1629// code to merge geometry object which share, state, and attribute bindings.
1630////////////////////////////////////////////////////////////////////////////
1631
1632struct LessGeometry
1633{
1634    bool operator() (const osg::Geometry* lhs,const osg::Geometry* rhs) const
1635    {
1636        if (lhs->getStateSet()<rhs->getStateSet()) return true;
1637        if (rhs->getStateSet()<lhs->getStateSet()) return false;
1638       
1639        if (rhs->getVertexIndices()) { if (!lhs->getVertexIndices()) return true; }
1640        else if (lhs->getVertexIndices()) return false;
1641       
1642        if (lhs->getNormalBinding()<rhs->getNormalBinding()) return true;
1643        if (rhs->getNormalBinding()<lhs->getNormalBinding()) return false;
1644
1645        if (rhs->getNormalIndices()) { if (!lhs->getNormalIndices()) return true; }
1646        else if (lhs->getNormalIndices()) return false;
1647
1648        if (lhs->getColorBinding()<rhs->getColorBinding()) return true;
1649        if (rhs->getColorBinding()<lhs->getColorBinding()) return false;
1650       
1651        if (rhs->getColorIndices()) { if (!lhs->getColorIndices()) return true; }
1652        else if (lhs->getColorIndices()) return false;
1653
1654        if (lhs->getSecondaryColorBinding()<rhs->getSecondaryColorBinding()) return true;
1655        if (rhs->getSecondaryColorBinding()<lhs->getSecondaryColorBinding()) return false;
1656
1657        if (rhs->getSecondaryColorIndices()) { if (!lhs->getSecondaryColorIndices()) return true; }
1658        else if (lhs->getSecondaryColorIndices()) return false;
1659
1660        if (lhs->getFogCoordBinding()<rhs->getFogCoordBinding()) return true;
1661        if (rhs->getFogCoordBinding()<lhs->getFogCoordBinding()) return false;
1662
1663        if (rhs->getFogCoordIndices()) { if (!lhs->getFogCoordIndices()) return true; }
1664        else if (lhs->getFogCoordIndices()) return false;
1665
1666        if (lhs->getNumTexCoordArrays()<rhs->getNumTexCoordArrays()) return true;
1667        if (rhs->getNumTexCoordArrays()<lhs->getNumTexCoordArrays()) return false;
1668   
1669        // therefore lhs->getNumTexCoordArrays()==rhs->getNumTexCoordArrays()
1670       
1671        unsigned int i;
1672        for(i=0;i<lhs->getNumTexCoordArrays();++i)
1673        {
1674            if (rhs->getTexCoordArray(i))
1675            {
1676                if (!lhs->getTexCoordArray(i)) return true;
1677            }
1678            else if (lhs->getTexCoordArray(i)) return false;
1679
1680            if (rhs->getTexCoordIndices(i)) { if (!lhs->getTexCoordIndices(i)) return true; }
1681            else if (lhs->getTexCoordIndices(i)) return false;
1682        }
1683       
1684        for(i=0;i<lhs->getNumVertexAttribArrays();++i)
1685        {
1686            if (rhs->getVertexAttribArray(i))
1687            {
1688                if (!lhs->getVertexAttribArray(i)) return true;
1689            }
1690            else if (lhs->getVertexAttribArray(i)) return false;
1691
1692            if (rhs->getVertexAttribIndices(i)) { if (!lhs->getVertexAttribIndices(i)) return true; }
1693            else if (lhs->getVertexAttribIndices(i)) return false;
1694        }
1695       
1696       
1697        if (lhs->getNormalBinding()==osg::Geometry::BIND_OVERALL)
1698        {
1699            // assumes that the bindings and arrays are set up correctly, this
1700            // should be the case after running computeCorrectBindingsAndArraySizes();
1701            const osg::Array* lhs_normalArray = lhs->getNormalArray();
1702            const osg::Array* rhs_normalArray = rhs->getNormalArray();
1703            if (lhs_normalArray->getType()<rhs_normalArray->getType()) return true;
1704            if (rhs_normalArray->getType()<lhs_normalArray->getType()) return false;
1705            switch(lhs_normalArray->getType())
1706            {
1707            case(osg::Array::Vec3bArrayType):
1708                if ((*static_cast<const osg::Vec3bArray*>(lhs_normalArray))[0]<(*static_cast<const osg::Vec3bArray*>(rhs_normalArray))[0]) return true;
1709                if ((*static_cast<const osg::Vec3bArray*>(rhs_normalArray))[0]<(*static_cast<const osg::Vec3bArray*>(lhs_normalArray))[0]) return false;
1710                break;
1711            case(osg::Array::Vec3sArrayType):
1712                if ((*static_cast<const osg::Vec3sArray*>(lhs_normalArray))[0]<(*static_cast<const osg::Vec3sArray*>(rhs_normalArray))[0]) return true;
1713                if ((*static_cast<const osg::Vec3sArray*>(rhs_normalArray))[0]<(*static_cast<const osg::Vec3sArray*>(lhs_normalArray))[0]) return false;
1714                break;
1715            case(osg::Array::Vec3ArrayType):
1716                if ((*static_cast<const osg::Vec3Array*>(lhs_normalArray))[0]<(*static_cast<const osg::Vec3Array*>(rhs_normalArray))[0]) return true;
1717                if ((*static_cast<const osg::Vec3Array*>(rhs_normalArray))[0]<(*static_cast<const osg::Vec3Array*>(lhs_normalArray))[0]) return false;
1718                break;
1719            default:
1720                break;
1721            }
1722        }
1723       
1724        if (lhs->getColorBinding()==osg::Geometry::BIND_OVERALL)
1725        {
1726            const osg::Array* lhs_colorArray = lhs->getColorArray();
1727            const osg::Array* rhs_colorArray = rhs->getColorArray();
1728            if (lhs_colorArray->getType()<rhs_colorArray->getType()) return true;
1729            if (rhs_colorArray->getType()<lhs_colorArray->getType()) return false;
1730            switch(lhs_colorArray->getType())
1731            {
1732                case(osg::Array::Vec4ubArrayType):
1733                    if ((*static_cast<const osg::Vec4ubArray*>(lhs_colorArray))[0]<(*static_cast<const osg::Vec4ubArray*>(rhs_colorArray))[0]) return true;
1734                    if ((*static_cast<const osg::Vec4ubArray*>(rhs_colorArray))[0]<(*static_cast<const osg::Vec4ubArray*>(lhs_colorArray))[0]) return false;
1735                    break;
1736                case(osg::Array::Vec3ArrayType):
1737                    if ((*static_cast<const osg::Vec3Array*>(lhs_colorArray))[0]<(*static_cast<const osg::Vec3Array*>(rhs_colorArray))[0]) return true;
1738                    if ((*static_cast<const osg::Vec3Array*>(rhs_colorArray))[0]<(*static_cast<const osg::Vec3Array*>(lhs_colorArray))[0]) return false;
1739                    break;
1740                case(osg::Array::Vec4ArrayType):
1741                    if ((*static_cast<const osg::Vec4Array*>(lhs_colorArray))[0]<(*static_cast<const osg::Vec4Array*>(rhs_colorArray))[0]) return true;
1742                    if ((*static_cast<const osg::Vec4Array*>(rhs_colorArray))[0]<(*static_cast<const osg::Vec4Array*>(lhs_colorArray))[0]) return false;
1743                    break;
1744                default:
1745                    break;
1746            }
1747           
1748        }
1749
1750        return false;
1751
1752    }
1753};
1754
1755struct LessGeometryPrimitiveType
1756{
1757    bool operator() (const osg::Geometry* lhs,const osg::Geometry* rhs) const
1758    {
1759        for(unsigned int i=0;
1760            i<lhs->getNumPrimitiveSets() && i<rhs->getNumPrimitiveSets();
1761            ++i)
1762        {
1763            if (lhs->getPrimitiveSet(i)->getType()<rhs->getPrimitiveSet(i)->getType()) return true;
1764            else if (rhs->getPrimitiveSet(i)->getType()<lhs->getPrimitiveSet(i)->getType()) return false;
1765
1766            if (lhs->getPrimitiveSet(i)->getMode()<rhs->getPrimitiveSet(i)->getMode()) return true;
1767            else if (rhs->getPrimitiveSet(i)->getMode()<lhs->getPrimitiveSet(i)->getMode()) return false;
1768
1769        }
1770        return lhs->getNumPrimitiveSets()<rhs->getNumPrimitiveSets();
1771    }
1772};
1773
1774void Optimizer::CheckGeometryVisitor::checkGeode(osg::Geode& geode)
1775{
1776    if (isOperationPermissibleForObject(&geode))
1777    {
1778        for(unsigned int i=0;i<geode.getNumDrawables();++i)
1779        {
1780            osg::Geometry* geom = geode.getDrawable(i)->asGeometry();
1781            if (geom && isOperationPermissibleForObject(geom))
1782            {
1783                geom->computeCorrectBindingsAndArraySizes();
1784            }
1785        }
1786    }
1787}
1788
1789bool Optimizer::MergeGeometryVisitor::mergeGeode(osg::Geode& geode)
1790{
1791    if (!isOperationPermissibleForObject(&geode)) return false;
1792
1793    if (geode.getNumDrawables()>=2)
1794    {
1795   
1796        // osg::notify(osg::NOTICE)<<"Before "<<geode.getNumDrawables()<<std::endl;
1797   
1798        typedef std::vector<osg::Geometry*>                         DuplicateList;
1799        typedef std::map<osg::Geometry*,DuplicateList,LessGeometry> GeometryDuplicateMap;
1800
1801        typedef std::vector<DuplicateList> MergeList;
1802
1803        GeometryDuplicateMap geometryDuplicateMap;
1804        osg::Geode::DrawableList standardDrawables;
1805
1806        unsigned int i;
1807        for(i=0;i<geode.getNumDrawables();++i)
1808        {
1809            osg::Geometry* geom = geode.getDrawable(i)->asGeometry();
1810            if (geom)
1811            {
1812                //geom->computeCorrectBindingsAndArraySizes();
1813
1814                if (!geometryContainsSharedArrays(*geom) &&
1815                      geom->getDataVariance()!=osg::Object::DYNAMIC &&
1816                      isOperationPermissibleForObject(geom))
1817                {
1818                    geometryDuplicateMap[geom].push_back(geom);
1819                }
1820                else
1821                {
1822                    standardDrawables.push_back(geode.getDrawable(i));
1823                }
1824            }
1825            else
1826            {           
1827                standardDrawables.push_back(geode.getDrawable(i));
1828            }
1829        }
1830
1831#if 1
1832        bool needToDoMerge = false;
1833        MergeList mergeList;
1834        for(GeometryDuplicateMap::iterator itr=geometryDuplicateMap.begin();
1835            itr!=geometryDuplicateMap.end();
1836            ++itr)
1837        {
1838            mergeList.push_back(DuplicateList());
1839            DuplicateList* duplicateList = &mergeList.back();
1840           
1841            if (itr->second.size()>1)
1842            {
1843                std::sort(itr->second.begin(),itr->second.end(),LessGeometryPrimitiveType());
1844                osg::Geometry* lhs = itr->second[0];
1845
1846                duplicateList->push_back(lhs);
1847               
1848                unsigned int numVertices = lhs->getVertexArray() ? lhs->getVertexArray()->getNumElements() : 0;
1849
1850                for(DuplicateList::iterator dupItr=itr->second.begin()+1;
1851                    dupItr!=itr->second.end();
1852                    ++dupItr)
1853                {
1854               
1855                    osg::Geometry* rhs = *dupItr;
1856                   
1857                    unsigned int numRhsVertices = rhs->getVertexArray() ? rhs->getVertexArray()->getNumElements() : 0;
1858
1859                    if (numVertices+numRhsVertices < _targetMaximumNumberOfVertices)
1860                    {
1861                        duplicateList->push_back(rhs);
1862                        numVertices += numRhsVertices;
1863                        needToDoMerge = true;
1864                    }
1865                    else
1866                    {
1867                        numVertices = numRhsVertices;
1868                        mergeList.push_back(DuplicateList());
1869                        duplicateList = &mergeList.back();
1870                        duplicateList->push_back(rhs);
1871                    }
1872
1873                }
1874            }
1875            else if (itr->second.size()>0)
1876            {
1877                duplicateList->push_back(itr->second[0]);
1878            }
1879        }
1880       
1881        if (needToDoMerge)
1882        {
1883            // first take a reference to all the drawables to prevent them being deleted prematurely
1884            osg::Geode::DrawableList keepDrawables;
1885            keepDrawables.resize(geode.getNumDrawables());
1886            for(i=0; i<geode.getNumDrawables(); ++i)
1887            {
1888                keepDrawables[i] = geode.getDrawable(i);
1889            }
1890           
1891            // now clear the drawable list of the Geode so we don't have to remove items one by one (which is slow)
1892            geode.removeDrawables(0, geode.getNumDrawables());
1893           
1894            // add back in the standard drawables which arn't possible to merge.
1895            for(osg::Geode::DrawableList::iterator sitr = standardDrawables.begin();
1896                sitr != standardDrawables.end();
1897                ++sitr)
1898            {
1899                geode.addDrawable(sitr->get());
1900            }
1901               
1902            // now do the merging of geometries
1903            for(MergeList::iterator mitr = mergeList.begin();
1904                mitr != mergeList.end();
1905                ++mitr)
1906            {
1907                DuplicateList& duplicateList = *mitr;
1908                if (duplicateList.size()>1)
1909                {
1910                    osg::Geometry* lhs = duplicateList.front();
1911                    geode.addDrawable(lhs);
1912                    for(DuplicateList::iterator ditr = duplicateList.begin()+1;
1913                        ditr != duplicateList.end();
1914                        ++ditr)
1915                    {
1916                        mergeGeometry(*lhs,**ditr);
1917                    }
1918                }
1919                else if (duplicateList.size()>0)
1920                {
1921                    geode.addDrawable(duplicateList.front());
1922                }
1923            }
1924        }
1925
1926#else
1927        // don't merge geometry if its above a maximum number of vertices.
1928        for(GeometryDuplicateMap::iterator itr=geometryDuplicateMap.begin();
1929            itr!=geometryDuplicateMap.end();
1930            ++itr)
1931        {
1932            if (itr->second.size()>1)
1933            {
1934                std::sort(itr->second.begin(),itr->second.end(),LessGeometryPrimitiveType());
1935                osg::Geometry* lhs = itr->second[0];
1936                for(DuplicateList::iterator dupItr=itr->second.begin()+1;
1937                    dupItr!=itr->second.end();
1938                    ++dupItr)
1939                {
1940               
1941                    osg::Geometry* rhs = *dupItr;
1942                   
1943                    if (lhs->getVertexArray() && lhs->getVertexArray()->getNumElements()>=_targetMaximumNumberOfVertices)
1944                    {
1945                        lhs = rhs;
1946                        continue;
1947                    }
1948
1949                    if (rhs->getVertexArray() && rhs->getVertexArray()->getNumElements()>=_targetMaximumNumberOfVertices)
1950                    {
1951                        continue;
1952                    }
1953                   
1954                    if (lhs->getVertexArray() && rhs->getVertexArray() &&
1955                        (lhs->getVertexArray()->getNumElements()+rhs->getVertexArray()->getNumElements())>=_targetMaximumNumberOfVertices)
1956                    {
1957                        continue;
1958                    }
1959                   
1960                    if (mergeGeometry(*lhs,*rhs))
1961                    {
1962                        geode.removeDrawable(rhs);
1963
1964                        static int co = 0;
1965                        osg::notify(osg::INFO)<<"merged and removed Geometry "<<++co<<std::endl;
1966                    }
1967                }
1968            }
1969        }
1970#endif
1971
1972        // osg::notify(osg::NOTICE)<<"After "<<geode.getNumDrawables()<<std::endl;
1973
1974    }
1975
1976
1977    // convert all polygon primitives which has 3 indices into TRIANGLES, 4 indices into QUADS.
1978    unsigned int i;
1979    for(i=0;i<geode.getNumDrawables();++i)
1980    {
1981        osg::Geometry* geom = dynamic_cast<osg::Geometry*>(geode.getDrawable(i));
1982        if (geom)
1983        {
1984            osg::Geometry::PrimitiveSetList& primitives = geom->getPrimitiveSetList();
1985            for(osg::Geometry::PrimitiveSetList::iterator itr=primitives.begin();
1986                itr!=primitives.end();
1987                ++itr)
1988            {
1989                osg::PrimitiveSet* prim = itr->get();
1990                if (prim->getMode()==osg::PrimitiveSet::POLYGON)
1991                {
1992                    if (prim->getNumIndices()==3)
1993                    {
1994                        prim->setMode(osg::PrimitiveSet::TRIANGLES);
1995                    }
1996                    else if (prim->getNumIndices()==4)
1997                    {
1998                        prim->setMode(osg::PrimitiveSet::QUADS);
1999                    }
2000                }
2001            }
2002        }
2003    }
2004
2005    // now merge any compatible primitives.
2006    for(i=0;i<geode.getNumDrawables();++i)
2007    {
2008        osg::Geometry* geom = dynamic_cast<osg::Geometry*>(geode.getDrawable(i));
2009        if (geom)
2010        {
2011            if (geom->getNumPrimitiveSets()>0 &&
2012                geom->getNormalBinding()!=osg::Geometry::BIND_PER_PRIMITIVE_SET &&
2013                geom->getColorBinding()!=osg::Geometry::BIND_PER_PRIMITIVE_SET &&
2014                geom->getSecondaryColorBinding()!=osg::Geometry::BIND_PER_PRIMITIVE_SET &&
2015                geom->getFogCoordBinding()!=osg::Geometry::BIND_PER_PRIMITIVE_SET)
2016            {
2017           
2018#if 1
2019                bool doneCombine = false;
2020
2021                osg::Geometry::PrimitiveSetList& primitives = geom->getPrimitiveSetList();
2022                unsigned int lhsNo=0;
2023                unsigned int rhsNo=1;
2024                while(rhsNo<primitives.size())
2025                {
2026                    osg::PrimitiveSet* lhs = primitives[lhsNo].get();
2027                    osg::PrimitiveSet* rhs = primitives[rhsNo].get();
2028 
2029                    bool combine = false;
2030
2031                    if (lhs->getType()==rhs->getType() &&
2032                        lhs->getMode()==rhs->getMode())
2033                    {
2034
2035                        switch(lhs->getMode())
2036                        {
2037                        case(osg::PrimitiveSet::POINTS):
2038                        case(osg::PrimitiveSet::LINES):
2039                        case(osg::PrimitiveSet::TRIANGLES):
2040                        case(osg::PrimitiveSet::QUADS):
2041                            combine = true;       
2042                            break;
2043                        }
2044                       
2045                    }
2046
2047                    if (combine)
2048                    {
2049                   
2050                        switch(lhs->getType())
2051                        {
2052                        case(osg::PrimitiveSet::DrawArraysPrimitiveType):
2053                            combine = mergePrimitive(*(static_cast<osg::DrawArrays*>(lhs)),*(static_cast<osg::DrawArrays*>(rhs)));
2054                            break;
2055                        case(osg::PrimitiveSet::DrawArrayLengthsPrimitiveType):
2056                            combine = mergePrimitive(*(static_cast<osg::DrawArrayLengths*>(lhs)),*(static_cast<osg::DrawArrayLengths*>(rhs)));
2057                            break;
2058                        case(osg::PrimitiveSet::DrawElementsUBytePrimitiveType):
2059                            combine = mergePrimitive(*(static_cast<osg::DrawElementsUByte*>(lhs)),*(static_cast<osg::DrawElementsUByte*>(rhs)));
2060                            break;
2061                        case(osg::PrimitiveSet::DrawElementsUShortPrimitiveType):
2062                            combine = mergePrimitive(*(static_cast<osg::DrawElementsUShort*>(lhs)),*(static_cast<osg::DrawElementsUShort*>(rhs)));
2063                            break;
2064                        case(osg::PrimitiveSet::DrawElementsUIntPrimitiveType):
2065                            combine = mergePrimitive(*(static_cast<osg::DrawElementsUInt*>(lhs)),*(static_cast<osg::DrawElementsUInt*>(rhs)));
2066                            break;
2067                        default:
2068                            combine = false;
2069                            break;
2070                        }
2071                    }
2072
2073                    if (combine)
2074                    {
2075                        // make this primitive set as invalid and needing cleaning up.
2076                        rhs->setMode(0xffffff);
2077                        doneCombine = true;
2078                        ++rhsNo;
2079                    }
2080                    else
2081                    {
2082                        lhsNo = rhsNo;
2083                        ++rhsNo;
2084                    }
2085                }
2086
2087    #if 1               
2088                if (doneCombine)
2089                {
2090                    // now need to clean up primitiveset so it no longer contains the rhs combined primitives.
2091
2092                    // first swap with a empty primitiveSet to empty it completely.
2093                    osg::Geometry::PrimitiveSetList oldPrimitives;
2094                    primitives.swap(oldPrimitives);
2095                   
2096                    // now add the active primitive sets
2097                    for(osg::Geometry::PrimitiveSetList::iterator pitr = oldPrimitives.begin();
2098                        pitr != oldPrimitives.end();
2099                        ++pitr)
2100                    {
2101                        if ((*pitr)->getMode()!=0xffffff) primitives.push_back(*pitr);
2102                    }
2103                }
2104    #endif
2105
2106#else           
2107
2108                osg::Geometry::PrimitiveSetList& primitives = geom->getPrimitiveSetList();
2109                unsigned int primNo=0;
2110                while(primNo+1<primitives.size())
2111                {
2112                    osg::PrimitiveSet* lhs = primitives[primNo].get();
2113                    osg::PrimitiveSet* rhs = primitives[primNo+1].get();
2114 
2115                    bool combine = false;
2116
2117                    if (lhs->getType()==rhs->getType() &&
2118                        lhs->getMode()==rhs->getMode())
2119                    {
2120
2121                        switch(lhs->getMode())
2122                        {
2123                        case(osg::PrimitiveSet::POINTS):
2124                        case(osg::PrimitiveSet::LINES):
2125                        case(osg::PrimitiveSet::TRIANGLES):
2126                        case(osg::PrimitiveSet::QUADS):
2127                            combine = true;       
2128                            break;
2129                        }
2130                       
2131                    }
2132
2133                    if (combine)
2134                    {
2135                   
2136                        switch(lhs->getType())
2137                        {
2138                        case(osg::PrimitiveSet::DrawArraysPrimitiveType):
2139                            combine = mergePrimitive(*(static_cast<osg::DrawArrays*>(lhs)),*(static_cast<osg::DrawArrays*>(rhs)));
2140                            break;
2141                        case(osg::PrimitiveSet::DrawArrayLengthsPrimitiveType):
2142                            combine = mergePrimitive(*(static_cast<osg::DrawArrayLengths*>(lhs)),*(static_cast<osg::DrawArrayLengths*>(rhs)));
2143                            break;
2144                        case(osg::PrimitiveSet::DrawElementsUBytePrimitiveType):
2145                            combine = mergePrimitive(*(static_cast<osg::DrawElementsUByte*>(lhs)),*(static_cast<osg::DrawElementsUByte*>(rhs)));
2146                            break;
2147                        case(osg::PrimitiveSet::DrawElementsUShortPrimitiveType):
2148                            combine = mergePrimitive(*(static_cast<osg::DrawElementsUShort*>(lhs)),*(static_cast<osg::DrawElementsUShort*>(rhs)));
2149                            break;
2150                        case(osg::PrimitiveSet::DrawElementsUIntPrimitiveType):
2151                            combine = mergePrimitive(*(static_cast<osg::DrawElementsUInt*>(lhs)),*(static_cast<osg::DrawElementsUInt*>(rhs)));
2152                            break;
2153                        default:
2154                            break;
2155                        }
2156                    }
2157                    if (combine)
2158                    {
2159                        primitives.erase(primitives.begin()+primNo+1);
2160                    }
2161
2162                    if (!combine)
2163                    {
2164                        primNo++;
2165                    }
2166                }
2167#endif
2168            }
2169        }
2170
2171
2172    }
2173
2174//    geode.dirtyBound();
2175
2176
2177    return false;
2178}
2179
2180bool Optimizer::MergeGeometryVisitor::geometryContainsSharedArrays(osg::Geometry& geom)
2181{
2182    if (geom.getVertexArray() && geom.getVertexArray()->referenceCount()>1) return true;
2183    if (geom.getNormalArray() && geom.getNormalArray()->referenceCount()>1) return true;
2184    if (geom.getColorArray() && geom.getColorArray()->referenceCount()>1) return true;
2185    if (geom.getSecondaryColorArray() && geom.getSecondaryColorArray()->referenceCount()>1) return true;
2186    if (geom.getFogCoordArray() && geom.getFogCoordArray()->referenceCount()>1) return true;
2187   
2188
2189    for(unsigned int unit=0;unit<geom.getNumTexCoordArrays();++unit)
2190    {
2191        osg::Array* tex = geom.getTexCoordArray(unit);
2192        if (tex && tex->referenceCount()>1) return true;
2193    }
2194   
2195    // shift the indices of the incoming primitives to account for the pre existing geometry.
2196    for(osg::Geometry::PrimitiveSetList::iterator primItr=geom.getPrimitiveSetList().begin();
2197        primItr!=geom.getPrimitiveSetList().end();
2198        ++primItr)
2199    {
2200        if ((*primItr)->referenceCount()>1) return true;
2201    }
2202   
2203   
2204    return false;
2205}
2206
2207
2208class MergeArrayVisitor : public osg::ArrayVisitor
2209{
2210    public:
2211   
2212        osg::Array* _lhs;
2213        int         _offset;
2214   
2215        MergeArrayVisitor() :
2216            _lhs(0),
2217            _offset(0) {}
2218           
2219           
2220        void merge(osg::Array* lhs,osg::Array* rhs, int offset=0)
2221        {
2222            if (lhs==0 || rhs==0) return;
2223            if (lhs->getType()!=rhs->getType()) return;
2224           
2225            _lhs = lhs;
2226            _offset = offset;
2227           
2228            rhs->accept(*this);
2229        }
2230       
2231        template<typename T>
2232        void _merge(T& rhs)
2233        {
2234            T* lhs = static_cast<T*>(_lhs);
2235            lhs->insert(lhs->end(),rhs.begin(),rhs.end());
2236        }
2237       
2238        template<typename T>
2239        void _mergeAndOffset(T& rhs)
2240        {
2241            T* lhs = static_cast<T*>(_lhs);
2242
2243            typename T::iterator itr;
2244            for(itr = rhs.begin();
2245                itr != rhs.end();
2246                ++itr)
2247            {
2248                lhs->push_back(*itr + _offset);
2249            }
2250        }
2251           
2252        virtual void apply(osg::Array&) { osg::notify(osg::WARN) << "Warning: Optimizer's MergeArrayVisitor cannot merge Array type." << std::endl; }
2253
2254        virtual void apply(osg::ByteArray& rhs) { if (_offset) _mergeAndOffset(rhs); else  _merge(rhs); }
2255        virtual void apply(osg::ShortArray& rhs) { if (_offset) _mergeAndOffset(rhs); else  _merge(rhs); }
2256        virtual void apply(osg::IntArray& rhs) { if (_offset) _mergeAndOffset(rhs); else  _merge(rhs); }
2257        virtual void apply(osg::UByteArray& rhs) { if (_offset) _mergeAndOffset(rhs); else  _merge(rhs); }
2258        virtual void apply(osg::UShortArray& rhs) { if (_offset) _mergeAndOffset(rhs); else  _merge(rhs); }
2259        virtual void apply(osg::UIntArray& rhs) { if (_offset) _mergeAndOffset(rhs); else  _merge(rhs); }
2260
2261        virtual void apply(osg::Vec4ubArray& rhs) { _merge(rhs); }
2262        virtual void apply(osg::FloatArray& rhs) { _merge(rhs); }
2263        virtual void apply(osg::Vec2Array& rhs) { _merge(rhs); }
2264        virtual void apply(osg::Vec3Array& rhs) { _merge(rhs); }
2265        virtual void apply(osg::Vec4Array& rhs) { _merge(rhs); }
2266       
2267        virtual void apply(osg::DoubleArray& rhs) { _merge(rhs); }
2268        virtual void apply(osg::Vec2dArray& rhs) { _merge(rhs); }
2269        virtual void apply(osg::Vec3dArray& rhs) { _merge(rhs); }
2270        virtual void apply(osg::Vec4dArray& rhs) { _merge(rhs); }
2271       
2272        virtual void apply(osg::Vec2bArray&  rhs) { _merge(rhs); }
2273        virtual void apply(osg::Vec3bArray&  rhs) { _merge(rhs); }
2274        virtual void apply(osg::Vec4bArray&  rhs) { _merge(rhs); }       
2275        virtual void apply(osg::Vec2sArray& rhs) { _merge(rhs); }
2276        virtual void apply(osg::Vec3sArray& rhs) { _merge(rhs); }
2277        virtual void apply(osg::Vec4sArray& rhs) { _merge(rhs); }
2278};
2279
2280bool Optimizer::MergeGeometryVisitor::mergeGeometry(osg::Geometry& lhs,osg::Geometry& rhs)
2281{
2282
2283    MergeArrayVisitor merger;
2284 
2285    unsigned int base = 0;
2286    unsigned int vbase = lhs.getVertexArray() ? lhs.getVertexArray()->getNumElements() : 0;
2287    if (lhs.getVertexArray() && rhs.getVertexArray())
2288    {
2289
2290        base = lhs.getVertexArray()->getNumElements();
2291        merger.merge(lhs.getVertexArray(),rhs.getVertexArray());
2292
2293    }
2294    else if (rhs.getVertexArray())
2295    {
2296        base = 0;
2297        lhs.setVertexArray(rhs.getVertexArray());
2298    }
2299   
2300    if (lhs.getVertexIndices() && rhs.getVertexIndices())
2301    {
2302
2303        base = lhs.getVertexIndices()->getNumElements();
2304        merger.merge(lhs.getVertexIndices(),rhs.getVertexIndices(),vbase);
2305
2306    }
2307    else if (rhs.getVertexIndices())
2308    {
2309        base = 0;
2310        lhs.setVertexIndices(rhs.getVertexIndices());
2311    }
2312   
2313
2314    unsigned int nbase = lhs.getNormalArray() ? lhs.getNormalArray()->getNumElements() : 0;
2315    if (lhs.getNormalArray() && rhs.getNormalArray() && lhs.getNormalBinding()!=osg::Geometry::BIND_OVERALL)
2316    {
2317        merger.merge(lhs.getNormalArray(),rhs.getNormalArray());
2318    }
2319    else if (rhs.getNormalArray())
2320    {
2321        lhs.setNormalArray(rhs.getNormalArray());
2322    }
2323
2324    if (lhs.getNormalIndices() && rhs.getNormalIndices() && lhs.getNormalBinding()!=osg::Geometry::BIND_OVERALL)
2325    {
2326        merger.merge(lhs.getNormalIndices(),rhs.getNormalIndices(),nbase);
2327    }
2328    else if (rhs.getNormalIndices())
2329    {
2330        // this assignment makes the assumption that lhs.NormalArray is empty as well and NormalIndices
2331        lhs.setNormalIndices(rhs.getNormalIndices());
2332    }
2333
2334
2335    unsigned int cbase = lhs.getColorArray() ? lhs.getColorArray()->getNumElements() : 0;
2336    if (lhs.getColorArray() && rhs.getColorArray() && lhs.getColorBinding()!=osg::Geometry::BIND_OVERALL)
2337    {
2338        merger.merge(lhs.getColorArray(),rhs.getColorArray());
2339    }
2340    else if (rhs.getColorArray())
2341    {
2342        lhs.setColorArray(rhs.getColorArray());
2343    }
2344   
2345    if (lhs.getColorIndices() && rhs.getColorIndices() && lhs.getColorBinding()!=osg::Geometry::BIND_OVERALL)
2346    {
2347        merger.merge(lhs.getColorIndices(),rhs.getColorIndices(),cbase);
2348    }
2349    else if (rhs.getColorIndices())
2350    {
2351        // this assignment makes the assumption that lhs.ColorArray is empty as well and ColorIndices
2352        lhs.setColorIndices(rhs.getColorIndices());
2353    }
2354
2355    unsigned int scbase = lhs.getSecondaryColorArray() ? lhs.getSecondaryColorArray()->getNumElements() : 0;
2356    if (lhs.getSecondaryColorArray() && rhs.getSecondaryColorArray() && lhs.getSecondaryColorBinding()!=osg::Geometry::BIND_OVERALL)
2357    {
2358        merger.merge(lhs.getSecondaryColorArray(),rhs.getSecondaryColorArray());
2359    }
2360    else if (rhs.getSecondaryColorArray())
2361    {
2362        lhs.setSecondaryColorArray(rhs.getSecondaryColorArray());
2363    }
2364   
2365    if (lhs.getSecondaryColorIndices() && rhs.getSecondaryColorIndices() && lhs.getSecondaryColorBinding()!=osg::Geometry::BIND_OVERALL)
2366    {
2367        merger.merge(lhs.getSecondaryColorIndices(),rhs.getSecondaryColorIndices(),scbase);
2368    }
2369    else if (rhs.getSecondaryColorIndices())
2370    {
2371        // this assignment makes the assumption that lhs.SecondaryColorArray is empty as well and SecondaryColorIndices
2372        lhs.setSecondaryColorIndices(rhs.getSecondaryColorIndices());
2373    }
2374
2375    unsigned int fcbase = lhs.getFogCoordArray() ? lhs.getFogCoordArray()->getNumElements() : 0;
2376    if (lhs.getFogCoordArray() && rhs.getFogCoordArray() && lhs.getFogCoordBinding()!=osg::Geometry::BIND_OVERALL)
2377    {
2378        merger.merge(lhs.getFogCoordArray(),rhs.getFogCoordArray());
2379    }
2380    else if (rhs.getFogCoordArray())
2381    {
2382        lhs.setFogCoordArray(rhs.getFogCoordArray());
2383    }
2384
2385    if (lhs.getFogCoordIndices() && rhs.getFogCoordIndices() && lhs.getFogCoordBinding()!=osg::Geometry::BIND_OVERALL)
2386    {
2387        merger.merge(lhs.getFogCoordIndices(),rhs.getFogCoordIndices(),fcbase);
2388    }
2389    else if (rhs.getFogCoordIndices())
2390    {
2391        // this assignment makes the assumption that lhs.FogCoordArray is empty as well and FogCoordIndices
2392        lhs.setFogCoordIndices(rhs.getFogCoordIndices());
2393    }
2394
2395
2396    unsigned int unit;
2397    for(unit=0;unit<lhs.getNumTexCoordArrays();++unit)
2398    {
2399        unsigned int tcbase = lhs.getTexCoordArray(unit) ? lhs.getTexCoordArray(unit)->getNumElements() : 0;
2400        merger.merge(lhs.getTexCoordArray(unit),rhs.getTexCoordArray(unit));
2401       
2402        if (lhs.getTexCoordIndices(unit) && rhs.getTexCoordIndices(unit))
2403        {
2404            merger.merge(lhs.getTexCoordIndices(unit),rhs.getTexCoordIndices(unit),tcbase);
2405        }
2406    }
2407   
2408    for(unit=0;unit<lhs.getNumVertexAttribArrays();++unit)
2409    {
2410        unsigned int vabase = lhs.getVertexAttribArray(unit) ? lhs.getVertexAttribArray(unit)->getNumElements() : 0;
2411        merger.merge(lhs.getVertexAttribArray(unit),rhs.getVertexAttribArray(unit));
2412       
2413        if (lhs.getVertexAttribIndices(unit) && rhs.getVertexAttribIndices(unit))
2414        {
2415            merger.merge(lhs.getVertexAttribIndices(unit),rhs.getVertexAttribIndices(unit),vabase);
2416        }
2417    }
2418
2419
2420    // shift the indices of the incoming primitives to account for the pre existing geometry.
2421    osg::Geometry::PrimitiveSetList::iterator primItr;
2422    for(primItr=rhs.getPrimitiveSetList().begin(); primItr!=rhs.getPrimitiveSetList().end(); ++primItr)
2423    {
2424        osg::PrimitiveSet* primitive = primItr->get();
2425       
2426        switch(primitive->getType())
2427        {
2428        case(osg::PrimitiveSet::DrawElementsUBytePrimitiveType):
2429            {
2430                osg::DrawElementsUByte* primitiveUByte = static_cast<osg::DrawElementsUByte*>(primitive);
2431                unsigned int currentMaximum = 0;
2432                for(osg::DrawElementsUByte::iterator eitr=primitiveUByte->begin();
2433                    eitr!=primitiveUByte->end();
2434                    ++eitr)
2435                {
2436                    currentMaximum = osg::maximum(currentMaximum,(unsigned int)*eitr);
2437                }
2438                if ((base+currentMaximum)>=65536)
2439                {
2440                    // must promote to a DrawElementsUInt
2441                    osg::DrawElementsUInt* new_primitive = new osg::DrawElementsUInt(primitive->getMode());
2442                    std::copy(primitiveUByte->begin(),primitiveUByte->end(),std::back_inserter(*new_primitive));
2443                    new_primitive->offsetIndices(base);
2444                    (*primItr) = new_primitive;
2445                } else if ((base+currentMaximum)>=256)
2446                {
2447                    // must promote to a DrawElementsUShort
2448                    osg::DrawElementsUShort* new_primitive = new osg::DrawElementsUShort(primitive->getMode());
2449                    std::copy(primitiveUByte->begin(),primitiveUByte->end(),std::back_inserter(*new_primitive));
2450                    new_primitive->offsetIndices(base);
2451                    (*primItr) = new_primitive;
2452                }
2453                else
2454                {
2455                    primitive->offsetIndices(base);
2456                }
2457            }
2458            break;
2459
2460        case(osg::PrimitiveSet::DrawElementsUShortPrimitiveType):
2461            {
2462                osg::DrawElementsUShort* primitiveUShort = static_cast<osg::DrawElementsUShort*>(primitive);
2463                unsigned int currentMaximum = 0;
2464                for(osg::DrawElementsUShort::iterator eitr=primitiveUShort->begin();
2465                    eitr!=primitiveUShort->end();
2466                    ++eitr)
2467                {
2468                    currentMaximum = osg::maximum(currentMaximum,(unsigned int)*eitr);
2469                }
2470                if ((base+currentMaximum)>=65536)
2471                {
2472                    // must promote to a DrawElementsUInt
2473                    osg::DrawElementsUInt* new_primitive = new osg::DrawElementsUInt(primitive->getMode());
2474                    std::copy(primitiveUShort->begin(),primitiveUShort->end(),std::back_inserter(*new_primitive));
2475                    new_primitive->offsetIndices(base);
2476                    (*primItr) = new_primitive;
2477                }
2478                else
2479                {
2480                    primitive->offsetIndices(base);
2481                }
2482            }
2483            break;
2484
2485        case(osg::PrimitiveSet::DrawArraysPrimitiveType):
2486        case(osg::PrimitiveSet::DrawArrayLengthsPrimitiveType):
2487        case(osg::PrimitiveSet::DrawElementsUIntPrimitiveType):
2488        default:
2489            primitive->offsetIndices(base);
2490            break;
2491        }
2492    }
2493   
2494    for(primItr=rhs.getPrimitiveSetList().begin(); primItr!=rhs.getPrimitiveSetList().end(); ++primItr)
2495    {
2496        lhs.addPrimitiveSet(primItr->get());
2497    }
2498
2499    lhs.dirtyBound();
2500    lhs.dirtyDisplayList();
2501   
2502    return true;
2503}
2504
2505bool Optimizer::MergeGeometryVisitor::mergePrimitive(osg::DrawArrays& lhs,osg::DrawArrays& rhs)
2506{
2507    if (lhs.getFirst()+lhs.getCount()==rhs.getFirst())
2508    {
2509        lhs.setCount(lhs.getCount()+rhs.getCount());
2510        return true;
2511    }
2512    return false;
2513}
2514
2515bool Optimizer::MergeGeometryVisitor::mergePrimitive(osg::DrawArrayLengths& lhs,osg::DrawArrayLengths& rhs)
2516{
2517    int lhs_count = std::accumulate(lhs.begin(),lhs.end(),0);
2518
2519    if (lhs.getFirst()+lhs_count==rhs.getFirst())
2520    {
2521        lhs.insert(lhs.end(),rhs.begin(),rhs.end());
2522        return true;
2523    }
2524    return false;
2525}
2526
2527bool Optimizer::MergeGeometryVisitor::mergePrimitive(osg::DrawElementsUByte& lhs,osg::DrawElementsUByte& rhs)
2528{
2529    lhs.insert(lhs.end(),rhs.begin(),rhs.end());
2530    return true;
2531}
2532
2533bool Optimizer::MergeGeometryVisitor::mergePrimitive(osg::DrawElementsUShort& lhs,osg::DrawElementsUShort& rhs)
2534{
2535    lhs.insert(lhs.end(),rhs.begin(),rhs.end());
2536    return true;
2537}
2538
2539bool Optimizer::MergeGeometryVisitor::mergePrimitive(osg::DrawElementsUInt& lhs,osg::DrawElementsUInt& rhs)
2540{
2541    lhs.insert(lhs.end(),rhs.begin(),rhs.end());
2542    return true;
2543}
2544
2545
2546////////////////////////////////////////////////////////////////////////////////////////////
2547//
2548//  Spatialize the scene to accelerate culling
2549//
2550
2551void Optimizer::SpatializeGroupsVisitor::apply(osg::Group& group)
2552{
2553    if (typeid(group)==typeid(osg::Group) || group.asTransform())
2554    {
2555        if (isOperationPermissibleForObject(&group))
2556        {
2557            _groupsToDivideList.insert(&group);
2558        }
2559    }
2560    traverse(group);
2561}
2562
2563void Optimizer::SpatializeGroupsVisitor::apply(osg::Geode& geode)
2564{
2565    if (typeid(geode)==typeid(osg::Geode))
2566    {
2567        if (isOperationPermissibleForObject(&geode))
2568        {
2569            _geodesToDivideList.insert(&geode);
2570        }
2571    }
2572    traverse(geode);
2573}
2574
2575bool Optimizer::SpatializeGroupsVisitor::divide(unsigned int maxNumTreesPerCell)
2576{
2577    bool divided = false;
2578    for(GroupsToDivideList::iterator itr=_groupsToDivideList.begin();
2579        itr!=_groupsToDivideList.end();
2580        ++itr)
2581    {
2582        if (divide(*itr,maxNumTreesPerCell)) divided = true;
2583    }
2584   
2585    for(GeodesToDivideList::iterator geode_itr=_geodesToDivideList.begin();
2586        geode_itr!=_geodesToDivideList.end();
2587        ++geode_itr)
2588    {
2589        if (divide(*geode_itr,maxNumTreesPerCell)) divided = true;
2590    }
2591   
2592    return divided;
2593}
2594
2595bool Optimizer::SpatializeGroupsVisitor::divide(osg::Group* group, unsigned int maxNumTreesPerCell)
2596{
2597    if (group->getNumChildren()<=maxNumTreesPerCell) return false;
2598   
2599    // create the original box.
2600    osg::BoundingBox bb;
2601    unsigned int i;
2602    for(i=0;i<group->getNumChildren();++i)
2603    {
2604        bb.expandBy(group->getChild(i)->getBound().center());
2605    }
2606   
2607    float radius = bb.radius();
2608    float divide_distance = radius*0.7f;
2609    bool xAxis = (bb.xMax()-bb.xMin())>divide_distance;
2610    bool yAxis = (bb.yMax()-bb.yMin())>divide_distance;
2611    bool zAxis = (bb.zMax()-bb.zMin())>divide_distance;
2612
2613    osg::notify(osg::INFO)<<"Dividing "<<group->className()<<"  num children = "<<group->getNumChildren()<<"  xAxis="<<xAxis<<"  yAxis="<<yAxis<<"   zAxis="<<zAxis<<std::endl;
2614   
2615    if (!xAxis && !yAxis && !zAxis)
2616    {
2617        osg::notify(osg::INFO)<<"  No axis to divide, stopping division."<<std::endl;
2618        return false;
2619    }
2620   
2621    unsigned int numChildrenOnEntry = group->getNumChildren();
2622   
2623    typedef std::pair< osg::BoundingBox, osg::ref_ptr<osg::Group> > BoxGroupPair;
2624    typedef std::vector< BoxGroupPair > Boxes;
2625    Boxes boxes;
2626    boxes.push_back( BoxGroupPair(bb,new osg::Group) );
2627
2628    // divide up on each axis   
2629    if (xAxis)
2630    {
2631        unsigned int numCellsToDivide=boxes.size();
2632        for(unsigned int i=0;i<numCellsToDivide;++i)
2633        {
2634            osg::BoundingBox& orig_cell = boxes[i].first;
2635            osg::BoundingBox new_cell = orig_cell;
2636
2637            float xCenter = (orig_cell.xMin()+orig_cell.xMax())*0.5f;
2638            orig_cell.xMax() = xCenter;
2639            new_cell.xMin() = xCenter;
2640
2641            boxes.push_back(BoxGroupPair(new_cell,new osg::Group));
2642        }
2643    }
2644
2645    if (yAxis)
2646    {
2647        unsigned int numCellsToDivide=boxes.size();
2648        for(unsigned int i=0;i<numCellsToDivide;++i)
2649        {
2650            osg::BoundingBox& orig_cell = boxes[i].first;
2651            osg::BoundingBox new_cell = orig_cell;
2652
2653            float yCenter = (orig_cell.yMin()+orig_cell.yMax())*0.5f;
2654            orig_cell.yMax() = yCenter;
2655            new_cell.yMin() = yCenter;
2656
2657            boxes.push_back(BoxGroupPair(new_cell,new osg::Group));
2658        }
2659    }
2660
2661    if (zAxis)
2662    {
2663        unsigned int numCellsToDivide=boxes.size();
2664        for(unsigned int i=0;i<numCellsToDivide;++i)
2665        {
2666            osg::BoundingBox& orig_cell = boxes[i].first;
2667            osg::BoundingBox new_cell = orig_cell;
2668
2669            float zCenter = (orig_cell.zMin()+orig_cell.zMax())*0.5f;
2670            orig_cell.zMax() = zCenter;
2671            new_cell.zMin() = zCenter;
2672
2673            boxes.push_back(BoxGroupPair(new_cell,new osg::Group));
2674        }
2675    }
2676
2677
2678    // create the groups to drop the children into
2679   
2680
2681    // bin each child into associated bb group
2682    typedef std::vector< osg::ref_ptr<osg::Node> > NodeList;
2683    NodeList unassignedList;
2684    for(i=0;i<group->getNumChildren();++i)
2685    {
2686        bool assigned = false;
2687        osg::Vec3 center = group->getChild(i)->getBound().center();
2688        for(Boxes::iterator itr=boxes.begin();
2689            itr!=boxes.end() && !assigned;
2690            ++itr)
2691        {
2692            if (itr->first.contains(center))
2693            {
2694                // move child from main group into bb group.
2695                (itr->second)->addChild(group->getChild(i));
2696                assigned = true;
2697            }
2698        }
2699        if (!assigned)
2700        {
2701            unassignedList.push_back(group->getChild(i));
2702        }
2703    }
2704
2705
2706    // now transfer nodes across, by :
2707    //      first removing from the original group,
2708    //      add in the bb groups
2709    //      add then the unassigned children.
2710   
2711   
2712    // first removing from the original group,
2713    group->removeChildren(0,group->getNumChildren());
2714   
2715    // add in the bb groups
2716    typedef std::vector< osg::ref_ptr<osg::Group> > GroupList;
2717    GroupList groupsToDivideList;
2718    for(Boxes::iterator itr=boxes.begin();
2719        itr!=boxes.end();
2720        ++itr)
2721    {
2722        // move child from main group into bb group.
2723        osg::Group* bb_group = (itr->second).get();
2724        if (bb_group->getNumChildren()>0)
2725        {
2726            if (bb_group->getNumChildren()==1)
2727            {
2728                group->addChild(bb_group->getChild(0));
2729            }
2730            else
2731            {
2732                group->addChild(bb_group);
2733                if (bb_group->getNumChildren()>maxNumTreesPerCell)
2734                {
2735                    groupsToDivideList.push_back(bb_group);
2736                }
2737            }
2738        }
2739    }
2740   
2741   
2742    // add then the unassigned children.
2743    for(NodeList::iterator nitr=unassignedList.begin();
2744        nitr!=unassignedList.end();
2745        ++nitr)
2746    {
2747        group->addChild(nitr->get());
2748    }
2749
2750    // now call divide on all groups that require it.
2751    for(GroupList::iterator gitr=groupsToDivideList.begin();
2752        gitr!=groupsToDivideList.end();
2753        ++gitr)
2754    {
2755        divide(gitr->get(),maxNumTreesPerCell);
2756    }
2757
2758    return (numChildrenOnEntry<group->getNumChildren());
2759   
2760}
2761
2762bool Optimizer::SpatializeGroupsVisitor::divide(osg::Geode* geode, unsigned int maxNumTreesPerCell)
2763{
2764
2765    if (geode->getNumDrawables()<=maxNumTreesPerCell) return false;
2766   
2767    // create the original box.
2768    osg::BoundingBox bb;
2769    unsigned int i;
2770    for(i=0; i<geode->getNumDrawables(); ++i)
2771    {
2772        bb.expandBy(geode->getDrawable(i)->getBound().center());
2773    }
2774   
2775    float radius = bb.radius();
2776    float divide_distance = radius*0.7f;
2777    bool xAxis = (bb.xMax()-bb.xMin())>divide_distance;
2778    bool yAxis = (bb.yMax()-bb.yMin())>divide_distance;
2779    bool zAxis = (bb.zMax()-bb.zMin())>divide_distance;
2780
2781    osg::notify(osg::INFO)<<"INFO "<<geode->className()<<"  num drawables = "<<geode->getNumDrawables()<<"  xAxis="<<xAxis<<"  yAxis="<<yAxis<<"   zAxis="<<zAxis<<std::endl;
2782   
2783    if (!xAxis && !yAxis && !zAxis)
2784    {
2785        osg::notify(osg::INFO)<<"  No axis to divide, stopping division."<<std::endl;
2786        return false;
2787    }
2788   
2789    osg::Node::ParentList parents = geode->getParents();
2790    if (parents.empty())
2791    {
2792        osg::notify(osg::INFO)<<"  Cannot perform spatialize on root Geode, add a Group above it to allow subdivision."<<std::endl;
2793        return false;
2794    }
2795
2796    osg::ref_ptr<osg::Group> group = new osg::Group;
2797    group->setName(geode->getName());
2798    group->setStateSet(geode->getStateSet());
2799    for(i=0; i<geode->getNumDrawables(); ++i)
2800    {
2801        osg::Geode* newGeode = new osg::Geode;
2802        newGeode->addDrawable(geode->getDrawable(i));
2803        group->addChild(newGeode);
2804    }
2805   
2806    divide(group.get(), maxNumTreesPerCell);
2807   
2808    // keep reference around to prevent it being deleted.
2809    osg::ref_ptr<osg::Geode> keepRefGeode = geode;
2810   
2811    for(osg::Node::ParentList::iterator itr = parents.begin();
2812        itr != parents.end();
2813        ++itr)
2814    {
2815        (*itr)->replaceChild(geode, group.get());
2816    }
2817   
2818    return true;
2819}
2820
2821////////////////////////////////////////////////////////////////////////////////////////////
2822//
2823//  Duplicated subgraphs which are shared
2824//
2825
2826void Optimizer::CopySharedSubgraphsVisitor::apply(osg::Node& node)
2827{
2828    if (node.getNumParents()>1 && isOperationPermissibleForObject(&node))
2829    {
2830        _sharedNodeList.insert(&node);
2831    }
2832    traverse(node);
2833}
2834
2835void Optimizer::CopySharedSubgraphsVisitor::copySharedNodes()
2836{
2837    osg::notify(osg::INFO)<<"Shared node "<<_sharedNodeList.size()<<std::endl;
2838    for(SharedNodeList::iterator itr=_sharedNodeList.begin();
2839        itr!=_sharedNodeList.end();
2840        ++itr)
2841    {
2842        osg::notify(osg::INFO)<<"   No parents "<<(*itr)->getNumParents()<<std::endl;
2843        osg::Node* node = *itr;
2844        for(unsigned int i=node->getNumParents()-1;i>0;--i)
2845        {
2846            // create a clone.
2847            osg::ref_ptr<osg::Object> new_object = node->clone(osg::CopyOp::DEEP_COPY_NODES |
2848                                                          osg::CopyOp::DEEP_COPY_DRAWABLES);
2849            // cast it to node.                                             
2850            osg::Node* new_node = dynamic_cast<osg::Node*>(new_object.get());
2851
2852            // replace the node by new_new
2853            if (new_node) node->getParent(i)->replaceChild(node,new_node);
2854        }
2855    }
2856}
2857
2858
2859////////////////////////////////////////////////////////////////////////////////////////////
2860//
2861//  Set the attributes of textures up.
2862//
2863
2864
2865void Optimizer::TextureVisitor::apply(osg::Node& node)
2866{
2867   
2868    osg::StateSet* ss = node.getStateSet();
2869    if (ss &&
2870        isOperationPermissibleForObject(&node) &&
2871        isOperationPermissibleForObject(ss))
2872    {
2873        apply(*ss);
2874    }
2875
2876    traverse(node);
2877}
2878
2879void Optimizer::TextureVisitor::apply(osg::Geode& geode)
2880{
2881    if (!isOperationPermissibleForObject(&geode)) return;
2882
2883    osg::StateSet* ss = geode.getStateSet();
2884   
2885    if (ss && isOperationPermissibleForObject(ss))
2886    {
2887        apply(*ss);
2888    }
2889
2890    for(unsigned int i=0;i<geode.getNumDrawables();++i)
2891    {
2892        osg::Drawable* drawable = geode.getDrawable(i);
2893        if (drawable)
2894        {
2895            ss = drawable->getStateSet();
2896            if (ss &&
2897               isOperationPermissibleForObject(drawable) &&
2898               isOperationPermissibleForObject(ss))
2899            {
2900                apply(*ss);
2901            }
2902        }
2903    }
2904}
2905
2906void Optimizer::TextureVisitor::apply(osg::StateSet& stateset)
2907{
2908    for(unsigned int i=0;i<stateset.getTextureAttributeList().size();++i)
2909    {
2910        osg::StateAttribute* sa = stateset.getTextureAttribute(i,osg::StateAttribute::TEXTURE);
2911        osg::Texture* texture = dynamic_cast<osg::Texture*>(sa);
2912        if (texture && isOperationPermissibleForObject(texture))
2913        {
2914            apply(*texture);
2915        }
2916    }
2917}
2918
2919void Optimizer::TextureVisitor::apply(osg::Texture& texture)
2920{
2921    if (_changeAutoUnRef)
2922    {
2923        unsigned numImageStreams = 0;
2924        for (unsigned int i=0; i<texture.getNumImages(); ++i)
2925        {
2926            osg::ImageStream* is = dynamic_cast<osg::ImageStream*>(texture.getImage(i));
2927            if (is) ++numImageStreams;
2928        }
2929       
2930        if (numImageStreams==0)
2931        {
2932            texture.setUnRefImageDataAfterApply(_valueAutoUnRef);
2933        }
2934    }
2935   
2936    if (_changeClientImageStorage)
2937    {
2938        texture.setClientStorageHint(_valueClientImageStorage);
2939    }
2940   
2941    if (_changeAnisotropy)
2942    {
2943        texture.setMaxAnisotropy(_valueAnisotropy);
2944    }
2945
2946}
2947
2948////////////////////////////////////////////////////////////////////////////
2949// Merge geodes
2950////////////////////////////////////////////////////////////////////////////
2951
2952void Optimizer::MergeGeodesVisitor::apply(osg::Group& group)
2953{
2954    if (typeid(group)==typeid(osg::Group)) mergeGeodes(group);
2955    traverse(group);
2956}
2957
2958struct LessGeode
2959{
2960    bool operator() (const osg::Geode* lhs,const osg::Geode* rhs) const
2961    {
2962        if (lhs->getNodeMask()<rhs->getNodeMask()) return true;
2963        if (lhs->getNodeMask()>rhs->getNodeMask()) return false;
2964
2965        return (lhs->getStateSet()<rhs->getStateSet());
2966    }
2967};
2968
2969bool Optimizer::MergeGeodesVisitor::mergeGeodes(osg::Group& group)
2970{
2971    if (!isOperationPermissibleForObject(&group)) return false;
2972
2973    typedef std::vector< osg::Geode* >                      DuplicateList;
2974    typedef std::map<osg::Geode*,DuplicateList,LessGeode>   GeodeDuplicateMap;
2975
2976    unsigned int i;
2977    osg::NodeList children;
2978    children.resize(group.getNumChildren());
2979    for (i=0; i<group.getNumChildren(); ++i)
2980    {
2981        // keep a reference to this child so we can safely clear the group of all children
2982        // this is done so we don't have to do a search and remove from the list later on.
2983        children[i] = group.getChild(i);
2984    }
2985   
2986    // remove all children
2987    group.removeChildren(0,group.getNumChildren());
2988
2989    GeodeDuplicateMap geodeDuplicateMap;
2990    for (i=0; i<children.size(); ++i)
2991    {
2992        osg::Node* child = children[i].get();
2993
2994        if (typeid(*child)==typeid(osg::Geode))
2995        {
2996            osg::Geode* geode = static_cast<osg::Geode*>(child);
2997            geodeDuplicateMap[geode].push_back(geode);
2998        }
2999        else
3000        {
3001            // not a geode so just add back into group as its a normal child
3002            group.addChild(child);
3003        }
3004    }
3005
3006    // if no geodes then just return.
3007    if (geodeDuplicateMap.empty()) return false;
3008   
3009    osg::notify(osg::INFO)<<"mergeGeodes in group '"<<group.getName()<<"' "<<geodeDuplicateMap.size()<<std::endl;
3010   
3011    // merge
3012    for(GeodeDuplicateMap::iterator itr=geodeDuplicateMap.begin();
3013        itr!=geodeDuplicateMap.end();
3014        ++itr)
3015    {
3016        if (itr->second.size()>1)
3017        {
3018            osg::Geode* lhs = itr->second[0];
3019
3020            // add geode back into group
3021            group.addChild(lhs);
3022           
3023            for(DuplicateList::iterator dupItr=itr->second.begin()+1;
3024                dupItr!=itr->second.end();
3025                ++dupItr)
3026            {
3027                osg::Geode* rhs = *dupItr;
3028                mergeGeode(*lhs,*rhs);
3029            }
3030        }
3031        else
3032        {
3033            osg::Geode* lhs = itr->second[0];
3034
3035            // add geode back into group
3036            group.addChild(lhs);
3037        }
3038    }
3039
3040    return true;
3041}
3042
3043bool Optimizer::MergeGeodesVisitor::mergeGeode(osg::Geode& lhs, osg::Geode& rhs)
3044{
3045    for (unsigned int i=0; i<rhs.getNumDrawables(); ++i)
3046    {
3047        lhs.addDrawable(rhs.getDrawable(i));
3048    }
3049
3050    return true;
3051}
3052
3053
3054
3055////////////////////////////////////////////////////////////////////////////
3056// FlattenBillboardVisitor
3057////////////////////////////////////////////////////////////////////////////
3058void Optimizer::FlattenBillboardVisitor::reset()
3059{
3060    _billboards.clear();
3061}
3062
3063void Optimizer::FlattenBillboardVisitor::apply(osg::Billboard& billboard)
3064{
3065    _billboards[&billboard].push_back(getNodePath());
3066}
3067
3068void Optimizer::FlattenBillboardVisitor::process()
3069{
3070    for(BillboardNodePathMap::iterator itr = _billboards.begin();
3071        itr != _billboards.end();
3072        ++itr)
3073    {
3074        bool mergeAcceptable = true;   
3075
3076        osg::ref_ptr<osg::Billboard> billboard = itr->first;
3077
3078        NodePathList& npl = itr->second;
3079        osg::Group* mainGroup = 0;
3080        if (npl.size()>1)
3081        {       
3082            for(NodePathList::iterator nitr = npl.begin();
3083                nitr != npl.end();
3084                ++nitr)
3085            {
3086                osg::NodePath& np = *nitr;
3087                if (np.size()>=3)
3088                {
3089                    osg::Group* group = dynamic_cast<osg::Group*>(np[np.size()-3]);
3090                    if (mainGroup==0) mainGroup = group;
3091
3092                    osg::MatrixTransform* mt = dynamic_cast<osg::MatrixTransform*>(np[np.size()-2]);
3093
3094                    if (group == mainGroup &&
3095                        np[np.size()-1]==billboard.get() &&
3096                        mt && mt->getDataVariance()==osg::Object::STATIC &&
3097                        mt->getNumChildren()==1)
3098                    {
3099                        const osg::Matrix& m = mt->getMatrix();
3100                        mergeAcceptable = (m(0,0)==1.0 && m(0,1)==0.0 && m(0,2)==0.0 && m(0,3)==0.0 &&
3101                                           m(1,0)==0.0 && m(1,1)==1.0 && m(1,2)==0.0 && m(1,3)==0.0 &&
3102                                           m(2,0)==0.0 && m(2,1)==0.0 && m(2,2)==1.0 && m(2,3)==0.0 &&
3103                                           m(3,3)==1.0);
3104                    }
3105                    else
3106                    {
3107                       mergeAcceptable = false;
3108                    }
3109                }
3110                else
3111                {
3112                    mergeAcceptable = false;
3113                }
3114            }
3115        }
3116        else
3117        {
3118            mergeAcceptable = false;
3119        }
3120
3121        if (mergeAcceptable)
3122        {
3123            osg::Billboard* new_billboard = new osg::Billboard;
3124            new_billboard->setMode(billboard->getMode());
3125            new_billboard->setAxis(billboard->getAxis());
3126            new_billboard->setStateSet(billboard->getStateSet());
3127            new_billboard->setName(billboard->getName());               
3128
3129            mainGroup->addChild(new_billboard);
3130
3131            typedef std::set<osg::MatrixTransform*> MatrixTransformSet;
3132            MatrixTransformSet mts;
3133
3134            for(NodePathList::iterator nitr = npl.begin();
3135                nitr != npl.end();
3136                ++nitr)
3137            {
3138                osg::NodePath& np = *nitr;
3139                osg::MatrixTransform* mt = dynamic_cast<osg::MatrixTransform*>(np[np.size()-2]);
3140                mts.insert(mt);
3141            }
3142
3143            for(MatrixTransformSet::iterator mitr = mts.begin();
3144                mitr != mts.end();
3145                ++mitr)
3146            {
3147                osg::MatrixTransform* mt = *mitr;
3148                for(unsigned int i=0; i<billboard->getNumDrawables(); ++i)
3149                {
3150                    new_billboard->addDrawable(billboard->getDrawable(i),
3151                                               billboard->getPosition(i)*mt->getMatrix());
3152                }
3153                mainGroup->removeChild(mt);
3154            }
3155        }
3156    }
3157
3158}
3159
3160
3161
3162////////////////////////////////////////////////////////////////////////////
3163// TextureAtlasBuilder
3164////////////////////////////////////////////////////////////////////////////
3165
3166Optimizer::TextureAtlasBuilder::TextureAtlasBuilder():
3167    _maximumAtlasWidth(2048),
3168    _maximumAtlasHeight(2048),
3169    _margin(8)
3170{
3171}
3172
3173void Optimizer::TextureAtlasBuilder::reset()
3174{
3175    _sourceList.clear();
3176    _atlasList.clear();
3177}
3178
3179void Optimizer::TextureAtlasBuilder::setMaximumAtlasSize(unsigned int width, unsigned int height)
3180{
3181    _maximumAtlasWidth = width;
3182    _maximumAtlasHeight = height;
3183}
3184
3185void Optimizer::TextureAtlasBuilder::setMargin(unsigned int margin)
3186{
3187    _margin = margin;
3188}
3189
3190void Optimizer::TextureAtlasBuilder::addSource(const osg::Image* image)
3191{
3192    if (!getSource(image)) _sourceList.push_back(new Source(image));
3193}
3194
3195void Optimizer::TextureAtlasBuilder::addSource(const osg::Texture2D* texture)
3196{
3197    if (!getSource(texture)) _sourceList.push_back(new Source(texture));
3198}
3199
3200void Optimizer::TextureAtlasBuilder::buildAtlas()
3201{
3202    // assign the source to the atlas
3203    _atlasList.clear();
3204    for(SourceList::iterator sitr = _sourceList.begin();
3205        sitr != _sourceList.end();
3206        ++sitr)
3207    {
3208        Source* source = sitr->get();
3209        if (source->suitableForAtlas(_maximumAtlasWidth,_maximumAtlasHeight,_margin))
3210        {
3211            bool addedSourceToAtlas = false;
3212            for(AtlasList::iterator aitr = _atlasList.begin();
3213                aitr != _atlasList.end() && !addedSourceToAtlas;
3214                ++aitr)
3215            {
3216                osg::notify(osg::INFO)<<"checking source "<<source->_image->getFileName()<<" to see it it'll fit in atlas "<<aitr->get()<<std::endl;
3217                if ((*aitr)->doesSourceFit(source))
3218                {
3219                    addedSourceToAtlas = true;
3220                    (*aitr)->addSource(source);
3221                }
3222                else
3223                {
3224                    osg::notify(osg::INFO)<<"source "<<source->_image->getFileName()<<" does not fit in atlas "<<aitr->get()<<std::endl;
3225                }
3226            }
3227
3228            if (!addedSourceToAtlas)
3229            {
3230                osg::notify(osg::INFO)<<"creating new Atlas for "<<source->_image->getFileName()<<std::endl;
3231
3232                osg::ref_ptr<Atlas> atlas = new Atlas(_maximumAtlasWidth,_maximumAtlasHeight,_margin);
3233                _atlasList.push_back(atlas.get());
3234               
3235                atlas->addSource(source);
3236            }
3237        }
3238    }
3239   
3240    // build the atlas which are suitable for use, and discard the rest.
3241    AtlasList activeAtlasList;
3242    for(AtlasList::iterator aitr = _atlasList.begin();
3243        aitr != _atlasList.end();
3244        ++aitr)
3245    {
3246        Atlas* atlas = aitr->get();
3247
3248        if (atlas->_sourceList.size()==1)
3249        {
3250            // no point building an atlas with only one entry
3251            // so disconnect the source.
3252            Source* source = atlas->_sourceList[0].get();
3253            source->_atlas = 0;
3254            atlas->_sourceList.clear();
3255        }
3256       
3257        if (!(atlas->_sourceList.empty()))
3258        {
3259            std::stringstream ostr;
3260            ostr<<"atlas_"<<activeAtlasList.size()<<".rgb";
3261            atlas->_image->setFileName(ostr.str());
3262       
3263            activeAtlasList.push_back(atlas);
3264            atlas->clampToNearestPowerOfTwoSize();
3265            atlas->copySources();
3266           
3267        }
3268    }
3269   
3270    // keep only the active atlas'
3271    _atlasList.swap(activeAtlasList);
3272
3273}
3274
3275osg::Image* Optimizer::TextureAtlasBuilder::getImageAtlas(unsigned int i)
3276{
3277    Source* source = _sourceList[i].get();
3278    Atlas* atlas = source ? source->_atlas : 0;
3279    return atlas ? atlas->_image.get() : 0;
3280}
3281
3282osg::Texture2D* Optimizer::TextureAtlasBuilder::getTextureAtlas(unsigned int i)
3283{
3284    Source* source = _sourceList[i].get();
3285    Atlas* atlas = source ? source->_atlas : 0;
3286    return atlas ? atlas->_texture.get() : 0;
3287}
3288
3289osg::Matrix Optimizer::TextureAtlasBuilder::getTextureMatrix(unsigned int i)
3290{
3291    Source* source = _sourceList[i].get();
3292    return source ? source->computeTextureMatrix() : osg::Matrix();
3293}
3294
3295osg::Image* Optimizer::TextureAtlasBuilder::getImageAtlas(const osg::Image* image)
3296{
3297    Source* source = getSource(image);
3298    Atlas* atlas = source ? source->_atlas : 0;
3299    return atlas ? atlas->_image.get() : 0;
3300}
3301
3302osg::Texture2D* Optimizer::TextureAtlasBuilder::getTextureAtlas(const osg::Image* image)
3303{
3304    Source* source = getSource(image);
3305    Atlas* atlas = source ? source->_atlas : 0;
3306    return atlas ? atlas->_texture.get() : 0;
3307}
3308
3309osg::Matrix Optimizer::TextureAtlasBuilder::getTextureMatrix(const osg::Image* image)
3310{
3311    Source* source = getSource(image);
3312    return source ? source->computeTextureMatrix() : osg::Matrix();
3313}
3314
3315osg::Image* Optimizer::TextureAtlasBuilder::getImageAtlas(const osg::Texture2D* texture)
3316{
3317    Source* source = getSource(texture);
3318    Atlas* atlas = source ? source->_atlas : 0;
3319    return atlas ? atlas->_image.get() : 0;
3320}
3321
3322osg::Texture2D* Optimizer::TextureAtlasBuilder::getTextureAtlas(const osg::Texture2D* texture)
3323{
3324    Source* source = getSource(texture);
3325    Atlas* atlas = source ? source->_atlas : 0;
3326    return atlas ? atlas->_texture.get() : 0;
3327}
3328
3329osg::Matrix Optimizer::TextureAtlasBuilder::getTextureMatrix(const osg::Texture2D* texture)
3330{
3331    Source* source = getSource(texture);
3332    return source ? source->computeTextureMatrix() : osg::Matrix();
3333}
3334
3335Optimizer::TextureAtlasBuilder::Source* Optimizer::TextureAtlasBuilder::getSource(const osg::Image* image)
3336{
3337    for(SourceList::iterator itr = _sourceList.begin();
3338        itr != _sourceList.end();
3339        ++itr)
3340    {
3341        if ((*itr)->_image == image) return itr->get();
3342    }
3343    return 0;
3344}
3345
3346Optimizer::TextureAtlasBuilder::Source* Optimizer::TextureAtlasBuilder::getSource(const osg::Texture2D* texture)
3347{
3348    for(SourceList::iterator itr = _sourceList.begin();
3349        itr != _sourceList.end();
3350        ++itr)
3351    {
3352        if ((*itr)->_texture == texture) return itr->get();
3353    }
3354    return 0;
3355}
3356
3357bool Optimizer::TextureAtlasBuilder::Source::suitableForAtlas(unsigned int maximumAtlasWidth, unsigned int maximumAtlasHeight, unsigned int margin)
3358{
3359    if (!_image) return false;
3360   
3361    // size too big?
3362    if (_image->s()+margin*2 > maximumAtlasWidth) return false;
3363    if (_image->t()+margin*2 > maximumAtlasHeight) return false;
3364   
3365    switch(_image->getPixelFormat())
3366    {
3367        case(GL_COMPRESSED_ALPHA_ARB):
3368        case(GL_COMPRESSED_INTENSITY_ARB):
3369        case(GL_COMPRESSED_LUMINANCE_ALPHA_ARB):
3370        case(GL_COMPRESSED_LUMINANCE_ARB):
3371        case(GL_COMPRESSED_RGBA_ARB):
3372        case(GL_COMPRESSED_RGB_ARB):
3373        case(GL_COMPRESSED_RGB_S3TC_DXT1_EXT):
3374        case(GL_COMPRESSED_RGBA_S3TC_DXT1_EXT):
3375        case(GL_COMPRESSED_RGBA_S3TC_DXT3_EXT):
3376        case(GL_COMPRESSED_RGBA_S3TC_DXT5_EXT):
3377            // can't handle compressed textures inside an atlas
3378            return false;
3379        default:
3380            break;
3381    }
3382
3383    if ((_image->getPixelSizeInBits() % 8) != 0)
3384    {
3385        // pixel size not byte aligned so report as not suitable to prevent other atlas code from having problems with byte boundaries.
3386        return false;
3387    }
3388
3389    if (_texture.valid())
3390    {
3391
3392        if (_texture->getWrap(osg::Texture2D::WRAP_S)==osg::Texture2D::REPEAT ||
3393            _texture->getWrap(osg::Texture2D::WRAP_S)==osg::Texture2D::MIRROR)
3394        {
3395            // can't support repeating textures in texture atlas
3396            return false;
3397        }
3398
3399        if (_texture->getWrap(osg::Texture2D::WRAP_T)==osg::Texture2D::REPEAT ||
3400            _texture->getWrap(osg::Texture2D::WRAP_T)==osg::Texture2D::MIRROR)
3401        {
3402            // can't support repeating textures in texture atlas
3403            return false;
3404        }
3405
3406        if (_texture->getReadPBuffer()!=0)
3407        {
3408            // pbuffer textures not suitable
3409            return false;
3410        }
3411    }
3412   
3413    return true;
3414}
3415
3416osg::Matrix Optimizer::TextureAtlasBuilder::Source::computeTextureMatrix() const
3417{
3418    if (!_atlas) return osg::Matrix();
3419    if (!_image) return osg::Matrix();
3420    if (!(_atlas->_image)) return osg::Matrix();
3421   
3422    return osg::Matrix::scale(float(_image->s())/float(_atlas->_image->s()), float(_image->t())/float(_atlas->_image->t()), 1.0)*
3423           osg::Matrix::translate(float(_x)/float(_atlas->_image->s()), float(_y)/float(_atlas->_image->t()), 0.0);
3424}
3425
3426bool Optimizer::TextureAtlasBuilder::Atlas::doesSourceFit(Source* source)
3427{
3428    // does the source have a valid image?
3429    const osg::Image* sourceImage = source->_image.get();
3430    if (!sourceImage) return false;
3431   
3432    // does pixel format match?
3433    if (_image.valid())
3434    {
3435        if (_image->getPixelFormat() != sourceImage->getPixelFormat()) return false;
3436        if (_image->getDataType() != sourceImage->getDataType()) return false;
3437    }
3438   
3439    const osg::Texture2D* sourceTexture = source->_texture.get();
3440    if (sourceTexture)
3441    {
3442        if (sourceTexture->getWrap(osg::Texture2D::WRAP_S)==osg::Texture2D::REPEAT ||
3443            sourceTexture->getWrap(osg::Texture2D::WRAP_S)==osg::Texture2D::MIRROR)
3444        {
3445            // can't support repeating textures in texture atlas
3446            return false;
3447        }
3448
3449        if (sourceTexture->getWrap(osg::Texture2D::WRAP_T)==osg::Texture2D::REPEAT ||
3450            sourceTexture->getWrap(osg::Texture2D::WRAP_T)==osg::Texture2D::MIRROR)
3451        {
3452            // can't support repeating textures in texture atlas
3453            return false;
3454        }
3455
3456        if (sourceTexture->getReadPBuffer()!=0)
3457        {
3458            // pbuffer textures not suitable
3459            return false;
3460        }
3461
3462        if (_texture.valid())
3463        {
3464
3465            bool sourceUsesBorder = sourceTexture->getWrap(osg::Texture2D::WRAP_S)==osg::Texture2D::CLAMP_TO_BORDER ||
3466                                    sourceTexture->getWrap(osg::Texture2D::WRAP_T)==osg::Texture2D::CLAMP_TO_BORDER;
3467
3468            bool atlasUsesBorder = sourceTexture->getWrap(osg::Texture2D::WRAP_S)==osg::Texture2D::CLAMP_TO_BORDER ||
3469                                   sourceTexture->getWrap(osg::Texture2D::WRAP_T)==osg::Texture2D::CLAMP_TO_BORDER;
3470
3471            if (sourceUsesBorder!=atlasUsesBorder)
3472            {
3473                // border wrapping does not match
3474                return false;
3475            }
3476
3477            if (sourceUsesBorder)
3478            {
3479                // border colours don't match
3480                if (_texture->getBorderColor() != sourceTexture->getBorderColor()) return false;
3481            }
3482           
3483            if (_texture->getFilter(osg::Texture2D::MIN_FILTER) != sourceTexture->getFilter(osg::Texture2D::MIN_FILTER))
3484            {
3485                // inconsitent min filters
3486                return false;
3487            }
3488 
3489            if (_texture->getFilter(osg::Texture2D::MAG_FILTER) != sourceTexture->getFilter(osg::Texture2D::MAG_FILTER))
3490            {
3491                // inconsitent mag filters
3492                return false;
3493            }
3494           
3495            if (_texture->getMaxAnisotropy() != sourceTexture->getMaxAnisotropy())
3496            {
3497                // anisotropy different.
3498                return false;
3499            }
3500           
3501            if (_texture->getInternalFormat() != sourceTexture->getInternalFormat())
3502            {
3503                // internal formats inconistent
3504                return false;
3505            }
3506           
3507            if (_texture->getShadowCompareFunc() != sourceTexture->getShadowCompareFunc())
3508            {
3509                // shadow functions inconsitent
3510                return false;
3511            }
3512               
3513            if (_texture->getShadowTextureMode() != sourceTexture->getShadowTextureMode())
3514            {
3515                // shadow texture mode inconsitent
3516                return false;
3517            }
3518
3519            if (_texture->getShadowAmbient() != sourceTexture->getShadowAmbient())
3520            {
3521                // shadow ambient inconsitent
3522                return false;
3523            }
3524        }
3525    }
3526   
3527    if (sourceImage->s() + 2*_margin > _maximumAtlasWidth)
3528    {
3529        // image too big for Atlas
3530        return false;
3531    }
3532   
3533    if (sourceImage->t() + 2*_margin > _maximumAtlasHeight)
3534    {
3535        // image too big for Atlas
3536        return false;
3537    }
3538
3539    if ((_y + sourceImage->t() + 2*_margin) > _maximumAtlasHeight)
3540    {
3541        // image doesn't have up space in height axis.
3542        return false;
3543    }
3544
3545    // does the source fit in the current row?
3546    if ((_x + sourceImage->s() + 2*_margin) <= _maximumAtlasWidth)
3547    {
3548        // yes it fits :-)
3549        osg::notify(osg::INFO)<<"Fits in current row"<<std::endl;
3550        return true;
3551    }
3552
3553    // does the source fit in the new row up?
3554    if ((_height + sourceImage->t() + 2*_margin) <= _maximumAtlasHeight)
3555    {
3556        // yes it fits :-)
3557        osg::notify(osg::INFO)<<"Fits in next row"<<std::endl;
3558        return true;
3559    }
3560   
3561    // no space for the texture
3562    return false;
3563}
3564
3565bool Optimizer::TextureAtlasBuilder::Atlas::addSource(Source* source)
3566{
3567    // double check source is compatible
3568    if (!doesSourceFit(source))
3569    {
3570        osg::notify(osg::INFO)<<"source "<<source->_image->getFileName()<<" does not fit in atlas "<<this<<std::endl;
3571        return false;
3572    }
3573   
3574    const osg::Image* sourceImage = source->_image.get();
3575    const osg::Texture2D* sourceTexture = source->_texture.get();
3576
3577    if (!_image)
3578    {
3579        // need to create an image of the same pixel format to store the atlas in
3580        _image = new osg::Image;
3581        _image->setPixelFormat(sourceImage->getPixelFormat());
3582        _image->setDataType(sourceImage->getDataType());
3583    }
3584   
3585    if (!_texture && sourceTexture)
3586    {
3587        _texture = new osg::Texture2D(_image.get());
3588
3589        _texture->setWrap(osg::Texture2D::WRAP_S, sourceTexture->getWrap(osg::Texture2D::WRAP_S));
3590        _texture->setWrap(osg::Texture2D::WRAP_T, sourceTexture->getWrap(osg::Texture2D::WRAP_T));
3591       
3592        _texture->setBorderColor(sourceTexture->getBorderColor());
3593        _texture->setBorderWidth(0);
3594           
3595        _texture->setFilter(osg::Texture2D::MIN_FILTER, sourceTexture->getFilter(osg::Texture2D::MIN_FILTER));
3596        _texture->setFilter(osg::Texture2D::MAG_FILTER, sourceTexture->getFilter(osg::Texture2D::MAG_FILTER));
3597
3598        _texture->setMaxAnisotropy(sourceTexture->getMaxAnisotropy());
3599
3600        _texture->setInternalFormat(sourceTexture->getInternalFormat());
3601
3602        _texture->setShadowCompareFunc(sourceTexture->getShadowCompareFunc());
3603        _texture->setShadowTextureMode(sourceTexture->getShadowTextureMode());
3604        _texture->setShadowAmbient(sourceTexture->getShadowAmbient());
3605
3606    }
3607
3608    // now work out where to fit it, first try current row.
3609    if ((_x + sourceImage->s() + 2*_margin) <= _maximumAtlasWidth)
3610    {
3611        // yes it fits, so add the source to the atlas's list of sources it contains
3612        _sourceList.push_back(source);
3613
3614        osg::notify(osg::INFO)<<"current row insertion, source "<<source->_image->getFileName()<<" "<<_x<<","<<_y<<" fits in row of atlas "<<this<<std::endl;
3615
3616        // set up the source so it knows where it is in the atlas
3617        source->_x = _x + _margin;
3618        source->_y = _y + _margin;
3619        source->_atlas = this;
3620       
3621        // move the atlas' cursor along to the right
3622        _x += sourceImage->s() + 2*_margin;
3623       
3624        if (_x > _width) _width = _x;
3625       
3626        unsigned int localTop = _y + sourceImage->t() + 2*_margin;
3627        if ( localTop > _height) _height = localTop;
3628
3629        return true;
3630    }
3631
3632    // does the source fit in the new row up?
3633    if ((_height + sourceImage->t() + 2*_margin) <= _maximumAtlasHeight)
3634    {
3635        // now row so first need to reset the atlas cursor
3636        _x = 0;
3637        _y = _height;
3638
3639        // yes it fits, so add the source to the atlas' list of sources it contains
3640        _sourceList.push_back(source);
3641
3642        osg::notify(osg::INFO)<<"next row insertion, source "<<source->_image->getFileName()<<" "<<_x<<","<<_y<<" fits in row of atlas "<<this<<std::endl;
3643
3644        // set up the source so it knows where it is in the atlas
3645        source->_x = _x + _margin;
3646        source->_y = _y + _margin;
3647        source->_atlas = this;
3648       
3649        // move the atlas' cursor along to the right
3650        _x += sourceImage->s() + 2*_margin;
3651
3652        if (_x > _width) _width = _x;
3653
3654        _height = _y + sourceImage->t() + 2*_margin;
3655
3656        osg::notify(osg::INFO)<<"source "<<source->_image->getFileName()<<" "<<_x<<","<<_y<<" fits in row of atlas "<<this<<std::endl;
3657
3658        return true;
3659    }
3660
3661    osg::notify(osg::INFO)<<"source "<<source->_image->getFileName()<<" does not fit in atlas "<<this<<std::endl;
3662
3663    // shouldn't get here, unless doesSourceFit isn't working...
3664    return false;
3665}
3666
3667void Optimizer::TextureAtlasBuilder::Atlas::clampToNearestPowerOfTwoSize()
3668{
3669    unsigned int w = 1;
3670    while (w<_width) w *= 2;
3671
3672    unsigned int h = 1;
3673    while (h<_height) h *= 2;
3674   
3675    osg::notify(osg::INFO)<<"Clamping "<<_width<<", "<<_height<<" to "<<w<<","<<h<<std::endl;
3676   
3677    _width = w;
3678    _height = h;
3679}
3680
3681
3682void Optimizer::TextureAtlasBuilder::Atlas::copySources()
3683{
3684    osg::notify(osg::INFO)<<"Allocated to "<<_width<<","<<_height<<std::endl;
3685    _image->allocateImage(_width,_height,1,
3686                          _image->getPixelFormat(),_image->getDataType(),
3687                          _image->getPacking());
3688                         
3689    {
3690        // clear memory
3691        unsigned int size = _image->getTotalSizeInBytes();
3692        unsigned char* str = _image->data();
3693        for(unsigned int i=0; i<size; ++i) *(str++) = 0;
3694    }       
3695
3696    osg::notify(osg::INFO)<<"Atlas::copySources() "<<std::endl;
3697    for(SourceList::iterator itr = _sourceList.begin();
3698        itr !=_sourceList.end();
3699        ++itr)
3700    {
3701        Source* source = itr->get();
3702        Atlas* atlas = source->_atlas;
3703
3704        if (atlas)
3705        {
3706            osg::notify(osg::INFO)<<"Copying image "<<source->_image->getFileName()<<" to "<<source->_x<<" ,"<<source->_y<<std::endl;
3707            osg::notify(osg::INFO)<<"        image size "<<source->_image->s()<<","<<source->_image->t()<<std::endl;
3708
3709            const osg::Image* sourceImage = source->_image.get();
3710            osg::Image* atlasImage = atlas->_image.get();
3711
3712            unsigned int rowSize = sourceImage->getRowSizeInBytes();
3713            unsigned int pixelSizeInBits = sourceImage->getPixelSizeInBits();
3714            unsigned int pixelSizeInBytes = pixelSizeInBits/8;
3715            unsigned int marginSizeInBytes = pixelSizeInBytes*_margin;
3716
3717            unsigned int x = source->_x;
3718            unsigned int y = source->_y;
3719
3720            int t;
3721            for(t=0; t<sourceImage->t(); ++t, ++y)
3722            {
3723                unsigned char* destPtr = atlasImage->data(x, y);
3724                const unsigned char* sourcePtr = sourceImage->data(0, t);
3725                for(unsigned int i=0; i<rowSize; i++)
3726                {
3727                    *(destPtr++) = *(sourcePtr++);
3728                }
3729            }
3730           
3731            // copy top row margin
3732            y = source->_y + sourceImage->t();
3733            unsigned int m;
3734            for(m=0; m<_margin; ++m, ++y)
3735            {
3736                unsigned char* destPtr = atlasImage->data(x, y);
3737                const unsigned char* sourcePtr = sourceImage->data(0, sourceImage->t()-1);
3738                for(unsigned int i=0; i<rowSize; i++)
3739                {
3740                    *(destPtr++) = *(sourcePtr++);
3741                }
3742               
3743            }
3744           
3745
3746
3747            // copy bottom row margin
3748            y = source->_y-1;
3749            for(m=0; m<_margin; ++m, --y)
3750            {
3751                unsigned char* destPtr = atlasImage->data(x, y);
3752                const unsigned char* sourcePtr = sourceImage->data(0, 0);
3753                for(unsigned int i=0; i<rowSize; i++)
3754                {
3755                    *(destPtr++) = *(sourcePtr++);
3756                }
3757               
3758            }
3759
3760            // copy left column margin
3761            y = source->_y;
3762            for(t=0; t<sourceImage->t(); ++t, ++y)
3763            {
3764                x = source->_x-1;
3765                for(m=0; m<_margin; ++m, --x)
3766                {
3767                    unsigned char* destPtr = atlasImage->data(x, y);
3768                    const unsigned char* sourcePtr = sourceImage->data(0, t);
3769                    for(unsigned int i=0; i<pixelSizeInBytes; i++)
3770                    {
3771                        *(destPtr++) = *(sourcePtr++);
3772                    }
3773                }
3774            }           
3775
3776            // copy right column margin
3777            y = source->_y;
3778            for(t=0; t<sourceImage->t(); ++t, ++y)
3779            {
3780                x = source->_x + sourceImage->s();
3781                for(m=0; m<_margin; ++m, ++x)
3782                {
3783                    unsigned char* destPtr = atlasImage->data(x, y);
3784                    const unsigned char* sourcePtr = sourceImage->data(sourceImage->s()-1, t);
3785                    for(unsigned int i=0; i<pixelSizeInBytes; i++)
3786                    {
3787                        *(destPtr++) = *(sourcePtr++);
3788                    }
3789                }
3790            }           
3791
3792            // copy top left corner margin
3793            y = source->_y + sourceImage->t();
3794            for(m=0; m<_margin; ++m, ++y)
3795            {
3796                unsigned char* destPtr = atlasImage->data(source->_x - _margin, y);
3797                unsigned char* sourcePtr = atlasImage->data(source->_x - _margin, y-1); // copy from row below
3798                for(unsigned int i=0; i<marginSizeInBytes; i++)
3799                {
3800                    *(destPtr++) = *(sourcePtr++);
3801                }
3802            }
3803
3804            // copy top right corner margin
3805            y = source->_y + sourceImage->t();
3806            for(m=0; m<_margin; ++m, ++y)
3807            {
3808                unsigned char* destPtr = atlasImage->data(source->_x + sourceImage->s(), y);
3809                unsigned char* sourcePtr = atlasImage->data(source->_x + sourceImage->s(), y-1); // copy from row below
3810                for(unsigned int i=0; i<marginSizeInBytes; i++)
3811                {
3812                    *(destPtr++) = *(sourcePtr++);
3813                }
3814            }
3815
3816            // copy bottom left corner margin
3817            y = source->_y - 1;
3818            for(m=0; m<_margin; ++m, --y)
3819            {
3820                unsigned char* destPtr = atlasImage->data(source->_x - _margin, y);
3821                unsigned char* sourcePtr = atlasImage->data(source->_x - _margin, y+1); // copy from row below
3822                for(unsigned int i=0; i<marginSizeInBytes; i++)
3823                {
3824                    *(destPtr++) = *(sourcePtr++);
3825                }
3826            }
3827
3828            // copy bottom right corner margin
3829            y = source->_y - 1;
3830            for(m=0; m<_margin; ++m, --y)
3831            {
3832                unsigned char* destPtr = atlasImage->data(source->_x + sourceImage->s(), y);
3833                unsigned char* sourcePtr = atlasImage->data(source->_x + sourceImage->s(), y+1); // copy from row below
3834                for(unsigned int i=0; i<marginSizeInBytes; i++)
3835                {
3836                    *(destPtr++) = *(sourcePtr++);
3837                }
3838            }
3839
3840        }
3841    }
3842}
3843
3844
3845void Optimizer::TextureAtlasVisitor::reset()
3846{
3847    _statesetMap.clear();
3848    _statesetStack.clear();
3849    _textures.clear();
3850    _builder.reset();
3851}
3852
3853bool Optimizer::TextureAtlasVisitor::pushStateSet(osg::StateSet* stateset)
3854{
3855    osg::StateSet::TextureAttributeList& tal = stateset->getTextureAttributeList();
3856   
3857    // if no textures ignore
3858    if (tal.empty()) return false;
3859   
3860    bool pushStateState = false;
3861
3862    // if already in stateset list ignore
3863    if (_statesetMap.count(stateset)>0)
3864    {
3865        pushStateState = true;
3866    }
3867    else
3868    {
3869        bool containsTexture2D = false;
3870        for(unsigned int unit=0; unit<tal.size(); ++unit)
3871        {
3872            osg::Texture2D* texture2D = dynamic_cast<osg::Texture2D*>(stateset->getTextureAttribute(unit,osg::StateAttribute::TEXTURE));
3873            if (texture2D)
3874            {
3875                containsTexture2D = true;
3876                _textures.insert(texture2D);
3877            }
3878        }
3879
3880        if (containsTexture2D)
3881        {
3882            _statesetMap[stateset];
3883            pushStateState = true;
3884        }
3885    }
3886   
3887    if (pushStateState)
3888    {
3889        _statesetStack.push_back(stateset);
3890    }
3891
3892   
3893    return pushStateState; 
3894}
3895
3896void Optimizer::TextureAtlasVisitor::popStateSet()
3897{
3898    _statesetStack.pop_back();
3899}
3900
3901void Optimizer::TextureAtlasVisitor::apply(osg::Node& node)
3902{
3903    bool pushedStateState = false;
3904   
3905    osg::StateSet* ss = node.getStateSet();
3906    if (ss && ss->getDataVariance()==osg::Object::STATIC)
3907    {
3908        if (isOperationPermissibleForObject(&node) &&
3909            isOperationPermissibleForObject(ss))
3910        {
3911            pushedStateState = pushStateSet(ss);
3912        }
3913    }
3914
3915    traverse(node);
3916   
3917    if (pushedStateState) popStateSet();
3918}
3919
3920void Optimizer::TextureAtlasVisitor::apply(osg::Geode& geode)
3921{
3922    if (!isOperationPermissibleForObject(&geode)) return;
3923
3924    osg::StateSet* ss = geode.getStateSet();
3925   
3926   
3927    bool pushedGeodeStateState = false;
3928
3929    if (ss && ss->getDataVariance()==osg::Object::STATIC)
3930    {
3931        if (isOperationPermissibleForObject(ss))
3932        {
3933            pushedGeodeStateState = pushStateSet(ss);
3934        }
3935    }
3936    for(unsigned int i=0;i<geode.getNumDrawables();++i)
3937    {
3938
3939        osg::Drawable* drawable = geode.getDrawable(i);
3940        if (drawable)
3941        {
3942            bool pushedDrawableStateState = false;
3943
3944            ss = drawable->getStateSet();
3945            if (ss && ss->getDataVariance()==osg::Object::STATIC)
3946            {
3947                if (isOperationPermissibleForObject(drawable) &&
3948                    isOperationPermissibleForObject(ss))
3949                {
3950                    pushedDrawableStateState = pushStateSet(ss);
3951                }
3952            }
3953           
3954            if (!_statesetStack.empty())
3955            {
3956                for(StateSetStack::iterator ssitr = _statesetStack.begin();
3957                    ssitr != _statesetStack.end();
3958                    ++ssitr)
3959                {
3960                    _statesetMap[*ssitr].insert(drawable);
3961                }
3962            }
3963
3964            if (pushedDrawableStateState) popStateSet();
3965        }
3966       
3967    }
3968   
3969    if (pushedGeodeStateState) popStateSet();
3970}
3971
3972void Optimizer::TextureAtlasVisitor::optimize()
3973{
3974    _builder.reset();
3975   
3976    if (_textures.size()<2)
3977    {
3978        // nothing to optimize
3979        return;
3980    }
3981
3982    Textures texturesThatRepeat;
3983    Textures texturesThatRepeatAndAreOutOfRange;
3984
3985    StateSetMap::iterator sitr;
3986    for(sitr = _statesetMap.begin();
3987        sitr != _statesetMap.end();
3988        ++sitr)
3989    {
3990        osg::StateSet* stateset = sitr->first;
3991        Drawables& drawables = sitr->second;
3992
3993        osg::StateSet::TextureAttributeList& tal = stateset->getTextureAttributeList();
3994        for(unsigned int unit=0; unit<tal.size(); ++unit)
3995        {
3996            osg::Texture2D* texture = dynamic_cast<osg::Texture2D*>(stateset->getTextureAttribute(unit,osg::StateAttribute::TEXTURE));
3997            if (texture)
3998            {
3999                bool s_repeat = texture->getWrap(osg::Texture2D::WRAP_S)==osg::Texture2D::REPEAT ||
4000                                texture->getWrap(osg::Texture2D::WRAP_S)==osg::Texture2D::MIRROR;
4001
4002                bool t_repeat = texture->getWrap(osg::Texture2D::WRAP_T)==osg::Texture2D::REPEAT ||
4003                                texture->getWrap(osg::Texture2D::WRAP_T)==osg::Texture2D::MIRROR;
4004                               
4005                if (s_repeat || t_repeat)
4006                {
4007                    texturesThatRepeat.insert(texture);
4008               
4009                    bool s_outOfRange = false;
4010                    bool t_outOfRange = false;
4011 
4012                    float s_min = -0.001;
4013                    float s_max = 1.001;
4014
4015                    float t_min = -0.001;
4016                    float t_max = 1.001;
4017                   
4018                    for(Drawables::iterator ditr = drawables.begin();
4019                        ditr != drawables.end();
4020                        ++ditr)
4021                    {
4022                        osg::Geometry* geom = (*ditr)->asGeometry();
4023                        osg::Vec2Array* texcoords = geom ? dynamic_cast<osg::Vec2Array*>(geom->getTexCoordArray(unit)) : 0;
4024                        if (texcoords && !texcoords->empty())
4025                        {
4026                            for(osg::Vec2Array::iterator titr = texcoords->begin();
4027                                titr != texcoords->end() /*&& !s_outOfRange && !t_outOfRange*/;
4028                                ++titr)
4029                            {
4030                                osg::Vec2 tc = *titr;
4031                                if (tc[0]<s_min) { s_min = tc[0]; s_outOfRange = true; }
4032                                if (tc[0]>s_max) { s_max = tc[0]; s_outOfRange = true; }
4033
4034                                if (tc[1]<t_min) { t_min = tc[1]; t_outOfRange = true; }
4035                                if (tc[1]>t_max) { t_max = tc[1]; t_outOfRange = true; }
4036                            }
4037                        }
4038                        else
4039                        {
4040                            // if no texcoords then texgen must be being used, therefore must assume that texture is truely repeating
4041                            s_outOfRange = true;
4042                            t_outOfRange = true;
4043                        }                       
4044                    }
4045
4046                    if (s_outOfRange || t_outOfRange)
4047                    {                   
4048                        texturesThatRepeatAndAreOutOfRange.insert(texture);
4049                    }
4050
4051                }
4052            }
4053        }
4054    }
4055
4056    // now change any texture that repeat but all texcoords to them
4057    // are in 0 to 1 range than converting the to CLAMP mode, to allow them
4058    // to be used in an atlas.
4059    Textures::iterator titr;
4060    for(titr = texturesThatRepeat.begin();
4061        titr != texturesThatRepeat.end();
4062        ++titr)
4063    {
4064        osg::Texture2D* texture = *titr;
4065        if (texturesThatRepeatAndAreOutOfRange.count(texture)==0)
4066        {
4067            // safe to convert into CLAMP wrap mode.
4068            osg::notify(osg::INFO)<<"Changing wrap mode to CLAMP"<<std::endl;
4069            texture->setWrap(osg::Texture2D::WRAP_S, osg::Texture::CLAMP);
4070            texture->setWrap(osg::Texture2D::WRAP_T, osg::Texture::CLAMP);
4071        }
4072    }
4073
4074    // add the textures as sources for the TextureAtlasBuilder
4075    for(titr = _textures.begin();
4076        titr != _textures.end();
4077        ++titr)
4078    {
4079        osg::Texture2D* texture = *titr;
4080
4081        bool s_repeat = texture->getWrap(osg::Texture2D::WRAP_S)==osg::Texture2D::REPEAT ||
4082                        texture->getWrap(osg::Texture2D::WRAP_S)==osg::Texture2D::MIRROR;
4083
4084        bool t_repeat = texture->getWrap(osg::Texture2D::WRAP_T)==osg::Texture2D::REPEAT ||
4085                        texture->getWrap(osg::Texture2D::WRAP_T)==osg::Texture2D::MIRROR;
4086
4087        if (!s_repeat && !t_repeat)
4088        {
4089            _builder.addSource(*titr);
4090        }
4091    }
4092   
4093    // build the atlas'
4094    _builder.buildAtlas();
4095
4096
4097    typedef std::set<osg::StateSet*> StateSetSet;
4098    typedef std::map<osg::Drawable*, StateSetSet> DrawableStateSetMap;
4099    DrawableStateSetMap dssm;
4100    for(sitr = _statesetMap.begin();
4101        sitr != _statesetMap.end();
4102        ++sitr)
4103    {
4104        Drawables& drawables = sitr->second;
4105        for(Drawables::iterator ditr = drawables.begin();
4106            ditr != drawables.end();
4107            ++ditr)
4108        {
4109            dssm[(*ditr)->asGeometry()].insert(sitr->first);
4110        }
4111    }
4112   
4113    Drawables drawablesThatHaveMultipleTexturesOnOneUnit;
4114    for(DrawableStateSetMap::iterator ditr = dssm.begin();
4115        ditr != dssm.end();
4116        ++ditr)
4117    {
4118        osg::Drawable* drawable = ditr->first;
4119        StateSetSet& ssm = ditr->second;
4120        if (ssm.size()>1)
4121        {
4122            typedef std::map<unsigned int, Textures> UnitTextureMap;
4123            UnitTextureMap unitTextureMap;
4124            for(StateSetSet::iterator ssm_itr = ssm.begin();
4125                ssm_itr != ssm.end();
4126                ++ssm_itr)
4127            {
4128                osg::StateSet* ss = *ssm_itr;
4129                unsigned int numTextureUnits = ss->getTextureAttributeList().size();
4130                for(unsigned int unit=0; unit<numTextureUnits; ++unit)
4131                {
4132                    osg::Texture2D* texture = dynamic_cast<osg::Texture2D*>(ss->getTextureAttribute(unit, osg::StateAttribute::TEXTURE));
4133                    if (texture) unitTextureMap[unit].insert(texture);
4134                }
4135            }
4136            bool drawablesHasMultiTextureOnOneUnit = false;
4137            for(UnitTextureMap::iterator utm_itr = unitTextureMap.begin();
4138                utm_itr != unitTextureMap.end() && !drawablesHasMultiTextureOnOneUnit;
4139                ++utm_itr)
4140            {
4141                if (utm_itr->second.size()>1)
4142                {
4143                    drawablesHasMultiTextureOnOneUnit = true;
4144                }
4145            }
4146            if (drawablesHasMultiTextureOnOneUnit)
4147            {
4148                drawablesThatHaveMultipleTexturesOnOneUnit.insert(drawable);
4149            }
4150
4151        }
4152    }
4153       
4154    // remap the textures in the StateSet's
4155    for(sitr = _statesetMap.begin();
4156        sitr != _statesetMap.end();
4157        ++sitr)
4158    {
4159        osg::StateSet* stateset = sitr->first;
4160        osg::StateSet::TextureAttributeList& tal = stateset->getTextureAttributeList();
4161        for(unsigned int unit=0; unit<tal.size(); ++unit)
4162        {
4163            osg::Texture2D* texture = dynamic_cast<osg::Texture2D*>(stateset->getTextureAttribute(unit,osg::StateAttribute::TEXTURE));
4164            if (texture)
4165            {
4166                bool s_repeat = texture->getWrap(osg::Texture2D::WRAP_S)==osg::Texture2D::REPEAT ||
4167                                texture->getWrap(osg::Texture2D::WRAP_S)==osg::Texture2D::MIRROR;
4168
4169                bool t_repeat = texture->getWrap(osg::Texture2D::WRAP_T)==osg::Texture2D::REPEAT ||
4170                                texture->getWrap(osg::Texture2D::WRAP_T)==osg::Texture2D::MIRROR;
4171
4172                osg::Texture2D* newTexture = _builder.getTextureAtlas(texture);
4173                if (newTexture && newTexture!=texture)
4174                {
4175                    if (s_repeat || t_repeat)
4176                    {
4177                        osg::notify(osg::NOTICE)<<"Warning!!! shouldn't get here"<<std::endl;
4178                    }
4179
4180                    stateset->setTextureAttribute(unit, newTexture);
4181                   
4182                    Drawables& drawables = sitr->second;
4183                   
4184                    osg::Matrix matrix = _builder.getTextureMatrix(texture);
4185                   
4186                    // first check to see if all drawables are ok for applying texturematrix to.
4187                    bool canTexMatBeFlattenedToAllDrawables = true;
4188                    for(Drawables::iterator ditr = drawables.begin();
4189                        ditr != drawables.end() && canTexMatBeFlattenedToAllDrawables;
4190                        ++ditr)
4191                    {
4192                        osg::Geometry* geom = (*ditr)->asGeometry();
4193                        osg::Vec2Array* texcoords = geom ? dynamic_cast<osg::Vec2Array*>(geom->getTexCoordArray(unit)) : 0;
4194
4195                        if (!texcoords)
4196                        {
4197                            canTexMatBeFlattenedToAllDrawables = false;
4198                        }
4199                       
4200                        if (drawablesThatHaveMultipleTexturesOnOneUnit.count(*ditr)!=0)
4201                        {
4202                            canTexMatBeFlattenedToAllDrawables = false;
4203                        }
4204                    }
4205
4206                    if (canTexMatBeFlattenedToAllDrawables)
4207                    {
4208                        // osg::notify(osg::NOTICE)<<"All drawables can be flattened "<<drawables.size()<<std::endl;
4209                        for(Drawables::iterator ditr = drawables.begin();
4210                            ditr != drawables.end();
4211                            ++ditr)
4212                        {
4213                            osg::Geometry* geom = (*ditr)->asGeometry();
4214                            osg::Vec2Array* texcoords = geom ? dynamic_cast<osg::Vec2Array*>(geom->getTexCoordArray(unit)) : 0;
4215                            if (texcoords)
4216                            {
4217                                for(osg::Vec2Array::iterator titr = texcoords->begin();
4218                                    titr != texcoords->end();
4219                                    ++titr)
4220                                {
4221                                    osg::Vec2 tc = *titr;
4222                                    (*titr).set(tc[0]*matrix(0,0) + tc[1]*matrix(1,0) + matrix(3,0),
4223                                              tc[0]*matrix(0,1) + tc[1]*matrix(1,1) + matrix(3,1));
4224                                }
4225                            }
4226                            else
4227                            {
4228                                osg::notify(osg::NOTICE)<<"Error, Optimizer::TextureAtlasVisitor::optimize() shouldn't ever get here..."<<std::endl;
4229                            }                       
4230                        }
4231                    }
4232                    else
4233                    {
4234                        // osg::notify(osg::NOTICE)<<"Applying TexMat "<<drawables.size()<<std::endl;
4235                        stateset->setTextureAttribute(unit, new osg::TexMat(matrix));
4236                    }
4237                }
4238            }
4239        }
4240
4241    }
4242}
4243
4244
4245
4246
4247////////////////////////////////////////////////////////////////////////////
4248// StaticObjectDectionVisitor
4249////////////////////////////////////////////////////////////////////////////
4250
4251void Optimizer::StaticObjectDetectionVisitor::apply(osg::Node& node)
4252{
4253    if (node.getStateSet()) applyStateSet(*node.getStateSet());
4254
4255    traverse(node);
4256}
4257
4258void Optimizer::StaticObjectDetectionVisitor::apply(osg::Geode& geode)
4259{
4260    if (geode.getStateSet()) applyStateSet(*geode.getStateSet());
4261
4262    for(unsigned int i=0; i<geode.getNumDrawables(); ++i)
4263    {
4264        applyDrawable(*geode.getDrawable(i));
4265    }
4266}
4267
4268void Optimizer::StaticObjectDetectionVisitor::applyStateSet(osg::StateSet& stateset)
4269{
4270    stateset.computeDataVariance();
4271}
4272
4273
4274void Optimizer::StaticObjectDetectionVisitor::applyDrawable(osg::Drawable& drawable)
4275{   
4276   
4277    if (drawable.getStateSet()) applyStateSet(*drawable.getStateSet());
4278   
4279    drawable.computeDataVariance();
4280}
4281
4282
4283
4284////////////////////////////////////////////////////////////////////////////
4285// FlattenStaticTransformsDuplicatingSharedSubgraphsVisitor
4286////////////////////////////////////////////////////////////////////////////
4287
4288void Optimizer::FlattenStaticTransformsDuplicatingSharedSubgraphsVisitor::reset()
4289{
4290    _matrixStack.clear();
4291}
4292
4293void Optimizer::FlattenStaticTransformsDuplicatingSharedSubgraphsVisitor::apply(osg::Group& group)
4294{
4295    // only continue if there is a parent
4296    const unsigned int nodepathsize = _nodePath.size();
4297    if(!_matrixStack.empty() && group.getNumParents() > 1 && nodepathsize > 1)
4298    {
4299        // copy this Group
4300        osg::ref_ptr<osg::Object> new_obj = group.clone(osg::CopyOp::DEEP_COPY_NODES | osg::CopyOp::DEEP_COPY_DRAWABLES | osg::CopyOp::DEEP_COPY_ARRAYS);
4301        osg::Group* new_group = dynamic_cast<osg::Group*>(new_obj.get());
4302
4303        // New Group should only be added to parent through which this Group
4304        // was traversed, not to all parents of this Group.
4305        osg::Group* parent_group = dynamic_cast<osg::Group*>(_nodePath[nodepathsize-2]);
4306        if(parent_group)
4307        {
4308            parent_group->replaceChild(&group, new_group);
4309            // traverse the new Group
4310            traverse(*(new_group));
4311        }
4312        else
4313        {
4314            osg::notify(osg::NOTICE) << "No parent for this Group" << std::endl;
4315        }
4316    }
4317    else
4318    {
4319        // traverse original node
4320        traverse(group);
4321    }
4322}
4323
4324
4325void Optimizer::FlattenStaticTransformsDuplicatingSharedSubgraphsVisitor::apply(osg::Transform& transform)
4326{
4327    bool pushed = false;
4328
4329    // only continue if there is a parent and this is a STATIC transform
4330    const unsigned int nodepathsize = _nodePath.size();
4331    if(transform.getDataVariance() == osg::Object::STATIC && nodepathsize > 1)
4332    {
4333        osg::Matrix matrix;
4334        if(!_matrixStack.empty())
4335            matrix = _matrixStack.back();
4336        transform.computeLocalToWorldMatrix(matrix, this);
4337        _matrixStack.push_back(matrix);
4338        pushed = true;
4339   
4340        // convert this Transform to a Group
4341        osg::ref_ptr<osg::Group> group = new osg::Group(dynamic_cast<osg::Group&>(transform),
4342            osg::CopyOp::DEEP_COPY_NODES | osg::CopyOp::DEEP_COPY_DRAWABLES | osg::CopyOp::DEEP_COPY_ARRAYS);
4343
4344        // New Group should only be added to parent through which this Transform
4345        // was traversed, not to all parents of this Transform.
4346        osg::Group* parent_group = dynamic_cast<osg::Group*>(_nodePath[nodepathsize-2]);
4347        if(parent_group)
4348        {
4349            parent_group->replaceChild(&transform, group.get());
4350            // traverse the new Group
4351            traverse(*(group.get()));
4352        }
4353        else
4354        {
4355            osg::notify(osg::NOTICE) << "No parent for this Group" << std::endl;
4356        }
4357    }
4358    else
4359    {
4360        // traverse original node
4361        traverse(transform);
4362    }
4363
4364    // pop matrix off of stack
4365    if(pushed)
4366        _matrixStack.pop_back();
4367}
4368
4369
4370void Optimizer::FlattenStaticTransformsDuplicatingSharedSubgraphsVisitor::apply(osg::LOD& lod)
4371{
4372    const unsigned int nodepathsize = _nodePath.size();
4373    if(!_matrixStack.empty() && lod.getNumParents() > 1 && nodepathsize > 1)
4374    {
4375        osg::ref_ptr<osg::LOD> new_lod = new osg::LOD(lod,
4376            osg::CopyOp::DEEP_COPY_NODES | osg::CopyOp::DEEP_COPY_DRAWABLES | osg::CopyOp::DEEP_COPY_ARRAYS);
4377
4378        // New LOD should only be added to parent through which this LOD
4379        // was traversed, not to all parents of this LOD.
4380        osg::Group* parent_group = dynamic_cast<osg::Group*>(_nodePath[nodepathsize-2]);
4381        if(parent_group)
4382        {
4383            parent_group->replaceChild(&lod, new_lod.get());
4384
4385            // move center point
4386            if(!_matrixStack.empty())
4387                new_lod->setCenter(new_lod->getCenter() * _matrixStack.back());
4388
4389            // traverse the new Group
4390            traverse(*(new_lod.get()));
4391        }
4392        else
4393            osg::notify(osg::NOTICE) << "No parent for this LOD" << std::endl;
4394    }
4395    else
4396    {
4397        // move center point
4398        if(!_matrixStack.empty())
4399            lod.setCenter(lod.getCenter() * _matrixStack.back());
4400
4401        traverse(lod);
4402    }
4403}
4404
4405
4406void Optimizer::FlattenStaticTransformsDuplicatingSharedSubgraphsVisitor::apply(osg::Geode& geode)
4407{
4408    if(!_matrixStack.empty())
4409    {
4410        // If there is only one parent, just transform all vertices and normals
4411        if(geode.getNumParents() == 1)
4412        {
4413            transformGeode(geode);
4414        }   
4415        else
4416        {
4417            // Else make a copy and then transform
4418            const unsigned int nodepathsize = _nodePath.size();
4419            if(nodepathsize > 1)
4420            {
4421                // convert this Transform to a Group
4422                osg::ref_ptr<osg::Geode> new_geode = new osg::Geode(geode,
4423                    osg::CopyOp::DEEP_COPY_NODES | osg::CopyOp::DEEP_COPY_DRAWABLES | osg::CopyOp::DEEP_COPY_ARRAYS);
4424
4425                // New Group should only be added to parent through which this Transform
4426                // was traversed, not to all parents of this Transform.
4427                osg::Group* parent_group = dynamic_cast<osg::Group*>(_nodePath[nodepathsize-2]);
4428                if(parent_group)
4429                    parent_group->replaceChild(&geode, new_geode.get());
4430                else
4431                    osg::notify(osg::NOTICE) << "No parent for this Geode" << std::endl;
4432
4433                transformGeode(*(new_geode.get()));
4434            }
4435        }
4436    }
4437}
4438
4439
4440void Optimizer::FlattenStaticTransformsDuplicatingSharedSubgraphsVisitor::apply(osg::Billboard& billboard)
4441{
4442    if(!_matrixStack.empty())
4443    {
4444        // If there is only one parent, just transform this Billboard
4445        if(billboard.getNumParents() == 1)
4446        {
4447            transformBillboard(billboard);
4448        }
4449        else
4450        {
4451            // Else make a copy and then transform
4452            const unsigned int nodepathsize = _nodePath.size();
4453            if(nodepathsize > 1)
4454            {
4455                // convert this Transform to a Group
4456                osg::ref_ptr<osg::Billboard> new_billboard = new osg::Billboard(billboard,
4457                    osg::CopyOp::DEEP_COPY_NODES | osg::CopyOp::DEEP_COPY_DRAWABLES | osg::CopyOp::DEEP_COPY_ARRAYS);
4458
4459                // New Billboard should only be added to parent through which this Billboard
4460                // was traversed, not to all parents of this Billboard.
4461                osg::Group* parent_group = dynamic_cast<osg::Group*>(_nodePath[nodepathsize-2]);
4462                if(parent_group)
4463                    parent_group->replaceChild(&billboard, new_billboard.get());
4464                else
4465                    osg::notify(osg::NOTICE) << "No parent for this Billboard" << std::endl;
4466
4467                transformBillboard(*(new_billboard.get()));
4468            }
4469        }
4470    }
4471}
4472
4473
4474void Optimizer::FlattenStaticTransformsDuplicatingSharedSubgraphsVisitor::transformGeode(osg::Geode& geode)
4475{
4476    for(unsigned int i=0; i<geode.getNumDrawables(); i++)
4477    {
4478        transformDrawable(*geode.getDrawable(i));
4479    }
4480
4481    geode.dirtyBound();
4482}
4483
4484
4485void Optimizer::FlattenStaticTransformsDuplicatingSharedSubgraphsVisitor::transformDrawable(osg::Drawable& drawable)
4486{
4487    osg::Geometry* geometry = drawable.asGeometry();
4488    if(geometry)
4489    {
4490        // transform all geometry
4491        osg::Vec3Array* verts = dynamic_cast<osg::Vec3Array*>(geometry->getVertexArray());
4492        if(verts)
4493        {
4494            for(unsigned int j=0; j<verts->size(); j++)
4495            {
4496                (*verts)[j] = (*verts)[j] * _matrixStack.back();
4497            }
4498        }
4499        else
4500        {
4501            osg::Vec4Array* verts = dynamic_cast<osg::Vec4Array*>(geometry->getVertexArray());
4502            if(verts)
4503            {
4504                for(unsigned int j=0; j<verts->size(); j++)
4505                {
4506                    (*verts)[j] = _matrixStack.back() * (*verts)[j];
4507                }
4508            }
4509        }
4510        osg::Vec3Array* normals = dynamic_cast<osg::Vec3Array*>(geometry->getNormalArray());
4511        if(normals)
4512        {
4513            for(unsigned int j=0; j<normals->size(); j++)
4514                (*normals)[j] = osg::Matrix::transform3x3((*normals)[j], _matrixStack.back());
4515        }
4516
4517        geometry->dirtyBound();
4518        geometry->dirtyDisplayList();
4519    }
4520}
4521
4522
4523void Optimizer::FlattenStaticTransformsDuplicatingSharedSubgraphsVisitor::transformBillboard(osg::Billboard& billboard)
4524{
4525    osg::Vec3 axis = osg::Matrix::transform3x3(billboard.getAxis(), _matrixStack.back());
4526    axis.normalize();
4527    billboard.setAxis(axis);
4528
4529    osg::Vec3 normal = osg::Matrix::transform3x3(billboard.getNormal(), _matrixStack.back());
4530    normal.normalize();
4531    billboard.setNormal(normal);
4532
4533    for(unsigned int i=0; i<billboard.getNumDrawables(); i++)
4534    {
4535        osg::Vec3 originalBillboardPosition = billboard.getPosition(i);
4536        billboard.setPosition(i, originalBillboardPosition * _matrixStack.back());
4537
4538        osg::Matrix matrixForDrawable = _matrixStack.back();
4539        matrixForDrawable.preMult(osg::Matrix::translate(originalBillboardPosition));
4540        matrixForDrawable.postMult(osg::Matrix::translate(-billboard.getPosition(i)));
4541
4542        _matrixStack.push_back(matrixForDrawable);
4543        transformDrawable(*billboard.getDrawable(i));
4544        _matrixStack.pop_back();
4545    }
4546
4547    billboard.dirtyBound();
4548}
4549
4550
Note: See TracBrowser for help on using the browser.