← Back to branch summary

~ubuntu-branches/debian/sid/osgearth/sid

« back to all changes in this revision

Viewing changes to src/osgEarthUtil/SpatialData.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Pirmin Kalberer
  • Date: 2011-07-14 22:13:36 UTC
  • Revision ID: james.westby@ubuntu.com-20110714221336-94igk9rskxveh794
Tags: upstream-2.0+dfsg
Import upstream version 2.0+dfsg

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/osgEarthUtil/SpatialData.cpp
 
1
/* -*-c++-*- */
 
2
/* osgEarth - Dynamic map generation toolkit for OpenSceneGraph
 
3
 * Copyright 2008-2010 Pelican Mapping
 
4
 * http://osgearth.org
 
5
 *
 
6
 * osgEarth is free software; you can redistribute it and/or modify
 
7
 * it under the terms of the GNU Lesser General Public License as published by
 
8
 * the Free Software Foundation; either version 2 of the License, or
 
9
 * (at your option) any later version.
 
10
 *
 
11
 * This program is distributed in the hope that it will be useful,
 
12
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 
13
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
14
 * GNU Lesser General Public License for more details.
 
15
 *
 
16
 * You should have received a copy of the GNU Lesser General Public License
 
17
 * along with this program.  If not, see <http://www.gnu.org/licenses/>
 
18
 */
 
19
#include <osgEarthUtil/SpatialData>
 
20
#include <osgUtil/CullVisitor>
 
21
#include <osg/PolygonOffset>
 
22
#include <osg/Polytope>
 
23
#include <osg/Geometry>
 
24
#include <osg/Depth>
 
25
#include <osgText/Text>
 
26
 
 
27
#define LC "[GeoGraph] "
 
28
 
 
29
using namespace osgEarth;
 
30
using namespace osgEarth::Util;
 
31
 
 
32
//------------------------------------------------------------------------
 
33
 
 
34
namespace
 
35
{
 
36
    unsigned getIndex( const GeoExtent& cellExtent, const osg::Vec3d& point, unsigned xdim, unsigned ydim )
 
37
    {
 
38
        unsigned col = osg::clampBelow( (unsigned)((double)xdim * ((point.x() - cellExtent.xMin()) / cellExtent.width())), xdim-1 );
 
39
        unsigned row = osg::clampBelow( (unsigned)((double)ydim * ((point.y() - cellExtent.yMin()) / cellExtent.height())), ydim-1 );
 
40
        return row*xdim + col;
 
41
    }
 
42
 
 
43
    static osgText::Font* s_font = 0L;
 
44
 
 
45
    osg::Geode* makeClusterGeode( const GeoExtent& cellExtent, unsigned num )
 
46
    {
 
47
        osgText::Text* t = new osgText::Text();
 
48
 
 
49
        double clat, clon;
 
50
        cellExtent.getCentroid( clon, clat );
 
51
        osg::Vec3d xyz;        
 
52
        cellExtent.getSRS()->getEllipsoid()->convertLatLongHeightToXYZ(
 
53
            osg::DegreesToRadians( clat ), osg::DegreesToRadians( clon ), 0, xyz.x(), xyz.y(), xyz.z() );
 
54
        t->setPosition( xyz );
 
55
        
 
56
        std::stringstream buf;
 
57
        buf << num;
 
58
        t->setText( buf.str() );
 
59
        t->setCharacterSizeMode( osgText::TextBase::SCREEN_COORDS );
 
60
        t->setCharacterSize( 22.0f );
 
61
        t->setAutoRotateToScreen( true );
 
62
 
 
63
        if ( !s_font )
 
64
            s_font = osgText::readFontFile( "arialbd.ttf" );
 
65
        t->setFont( s_font );
 
66
 
 
67
        t->setBackdropType( osgText::Text::OUTLINE );
 
68
        t->setColor( osg::Vec4(1,1,1,1) );
 
69
        t->setBackdropColor( osg::Vec4(0,0,0,1) );
 
70
 
 
71
        osg::Geode* geode = new osg::Geode();
 
72
        geode->addDrawable( t );
 
73
 
 
74
        osg::StateSet* s = geode->getOrCreateStateSet();
 
75
        s->setAttributeAndModes( new osg::Depth(osg::Depth::ALWAYS) );
 
76
 
 
77
        t->setDataVariance( osg::Object::DYNAMIC );
 
78
 
 
79
        return geode;
 
80
    }
 
81
 
 
82
    GeoObjectCollection::iterator
 
83
    findObject( GeoObjectCollection& objects, GeoObject* object )
 
84
    {
 
85
        float key = object->getPriority();
 
86
        GeoObjectCollection::iterator first = objects.find(key);
 
87
        if ( first == objects.end() )
 
88
            return objects.end();
 
89
 
 
90
        GeoObjectCollection::iterator last = objects.upper_bound(key);
 
91
        for( ; first != last; ++first )
 
92
            if ( first->second.get() == object )
 
93
                return first;
 
94
 
 
95
        return objects.end();
 
96
    }
 
97
}
 
98
 
 
99
//------------------------------------------------------------------------
 
100
 
 
101
GeoObject::GeoObject()
 
102
{
 
103
    //NOP
 
104
}
 
105
 
 
106
//------------------------------------------------------------------------
 
107
 
 
108
GeoGraph::GeoGraph(const GeoExtent& extent, float maxRange, unsigned maxObjects,
 
109
                   unsigned splitDim, float splitRangeFactor,
 
110
                   unsigned rootWidth, unsigned rootHeight ) :
 
111
GeoCell( extent, maxRange, maxObjects, splitDim, splitRangeFactor, 0 )
 
112
{
 
113
    _rootWidth = osg::maximum( rootWidth, (unsigned)2 );
 
114
    _rootHeight = osg::maximum( rootHeight, (unsigned)2 );
 
115
 
 
116
    if ( _depth == 0 )
 
117
    {
 
118
        double xinterval = extent.width() / (double)_rootWidth;
 
119
        double yinterval = extent.height() / (double)_rootHeight;
 
120
 
 
121
        for( unsigned y=0; y<_rootHeight; ++y )
 
122
        {
 
123
            for( unsigned x=0; x<_rootWidth; ++x )
 
124
            {
 
125
                GeoExtent cellExtent(
 
126
                    _extent.getSRS(),
 
127
                    _extent.xMin() + xinterval*(double)x,
 
128
                    _extent.yMin() + yinterval*(double)y,
 
129
                    _extent.xMin() + xinterval*(double)(x+1),
 
130
                    _extent.yMin() + yinterval*(double)(y+1) );
 
131
 
 
132
                GeoCell * child = new GeoCell(
 
133
                    cellExtent,
 
134
                    _maxRange,
 
135
                    _maxObjects,
 
136
                    _splitDim,
 
137
                    _splitRangeFactor,
 
138
                    1 );
 
139
 
 
140
                this->addChild( child, 0, maxRange ); //FLT_MAX );
 
141
            }
 
142
        }                    
 
143
    }
 
144
}
 
145
 
 
146
bool
 
147
GeoGraph::insertObject( GeoObject* object )
 
148
{
 
149
    osg::Vec3d loc;
 
150
    if ( object->getLocation(loc) )
 
151
    {
 
152
        unsigned index = getIndex( _extent, loc, _rootWidth, _rootHeight );
 
153
        return static_cast<GeoCell*>(getChild(index))->insertObject( object );
 
154
    }
 
155
    else
 
156
    {
 
157
        return false;
 
158
    }
 
159
}
 
160
 
 
161
//------------------------------------------------------------------------
 
162
 
 
163
GeoCell::GeoCell(const GeoExtent& extent, float maxRange, unsigned maxObjects,
 
164
                 unsigned splitDim, float splitRangeFactor, unsigned depth ) :
 
165
_extent( extent ),
 
166
_maxRange( maxRange ),
 
167
_maxObjects( maxObjects ),
 
168
_splitDim( splitDim ),
 
169
_splitRangeFactor( splitRangeFactor ),
 
170
_depth( depth ),
 
171
_minObjects( (maxObjects/10)*8 ), // 80%
 
172
_count( 0 ),
 
173
_boundaryPoints( 10 ),
 
174
_frameStamp( 0 )
 
175
{
 
176
    generateBoundaries();
 
177
    //generateBoundaryGeometry();
 
178
 
 
179
    // Disable OSG's culling so we can do our own custom culling.
 
180
    this->setCullingActive( false );
 
181
}
 
182
 
 
183
void
 
184
GeoCell::generateBoundaries()
 
185
{
 
186
    const osg::EllipsoidModel* em = _extent.getSRS()->getEllipsoid();
 
187
    static const double hae =  1e6;
 
188
    static const double hbe = -1e5;
 
189
 
 
190
    // find the geodetic center:
 
191
    osg::Vec3d gcenter;
 
192
    _extent.getCentroid( gcenter.x(), gcenter.y() );
 
193
 
 
194
    // convert to a geocentric vector:
 
195
    osg::Vec3d center;
 
196
    em->convertLatLongHeightToXYZ(
 
197
        osg::DegreesToRadians(gcenter.y()), osg::DegreesToRadians(gcenter.x()), 0.0, center.x(), center.y(), center.z());
 
198
 
 
199
    osg::Vec3d centerVec = center;
 
200
    centerVec.normalize();
 
201
 
 
202
    // find the 4 geodetic corners:
 
203
    osg::Vec3d gcorner[4];
 
204
    gcorner[0].set( _extent.xMin(), _extent.yMin(), 0.0 );
 
205
    gcorner[1].set( _extent.xMin(), _extent.yMax(), 0.0 );
 
206
    gcorner[2].set( _extent.xMax(), _extent.yMax(), 0.0 );
 
207
    gcorner[3].set( _extent.xMax(), _extent.yMin(), 0.0 );
 
208
 
 
209
    // and convert those to geocentric vectors:
 
210
    osg::Vec3d corner[4];
 
211
    osg::Vec3d cornerVec[4];
 
212
    for(unsigned i=0; i<4; ++i )
 
213
    {
 
214
        em->convertLatLongHeightToXYZ(
 
215
            osg::DegreesToRadians(gcorner[i].y()), osg::DegreesToRadians(gcorner[i].x()), 0.0,
 
216
            corner[i].x(), corner[i].y(), corner[i].z() );
 
217
        cornerVec[i] = corner[i];
 
218
        cornerVec[i].normalize();
 
219
    }   
 
220
    
 
221
    // now extrude the center and corners up and down to get the boundary points:
 
222
    unsigned p = 0;
 
223
    _boundaryPoints[p++] = center + centerVec*hae;
 
224
    _boundaryPoints[p++] = center +centerVec*hbe;
 
225
    for( unsigned i=0; i<4; ++i )
 
226
    {
 
227
        _boundaryPoints[p++] = corner[i] + cornerVec[i]*hae;
 
228
        _boundaryPoints[p++] = corner[i] + cornerVec[i]*hbe;
 
229
    }
 
230
}
 
231
 
 
232
osg::BoundingSphere
 
233
GeoCell::computeBound() const
 
234
{
 
235
    osg::BoundingSphere bs;
 
236
    for( unsigned i=0; i<10; ++i )
 
237
        bs.expandBy( _boundaryPoints[i] );
 
238
    return bs;
 
239
}
 
240
 
 
241
void
 
242
GeoCell::generateBoundaryGeometry()
 
243
{
 
244
    osg::Geometry* g = new osg::Geometry();
 
245
 
 
246
    osg::Vec3dArray* v = new osg::Vec3dArray(10);
 
247
    for( unsigned i=0; i<10; ++i )
 
248
        (*v)[i] = _boundaryPoints[i];
 
249
    g->setVertexArray( v );
 
250
 
 
251
    osg::DrawElementsUByte* el = new osg::DrawElementsUByte( GL_QUADS );
 
252
    el->push_back( 7 ); el->push_back( 5 ); el->push_back( 4 ); el->push_back( 6 );
 
253
    el->push_back( 9 ); el->push_back( 7 ); el->push_back( 6 ); el->push_back( 8 );
 
254
    el->push_back( 3 ); el->push_back( 9 ); el->push_back( 8 ); el->push_back( 2 );
 
255
    el->push_back( 5 ); el->push_back( 3 ); el->push_back( 2 ); el->push_back( 4 );
 
256
    //el->push_back( 2 ); el->push_back( 8 ); el->push_back( 6 ); el->push_back( 4 ); //top
 
257
    //el->push_back( 9 ); el->push_back( 3 ); el->push_back( 5 ); el->push_back( 7 ); // bottom
 
258
    g->addPrimitiveSet( el );
 
259
 
 
260
    osg::Vec4Array* c = new osg::Vec4Array(1);
 
261
    (*c)[0].set( 1, 1, 1, 0.25 );
 
262
    g->setColorArray( c );
 
263
    g->setColorBinding( osg::Geometry::BIND_OVERALL );
 
264
 
 
265
    _boundaryColor = c;
 
266
 
 
267
    g->setDataVariance( osg::Object::DYNAMIC );
 
268
    g->setUseDisplayList( false );
 
269
    g->setUseVertexBufferObjects( true );
 
270
 
 
271
    osg::StateSet* set = g->getOrCreateStateSet();
 
272
    set->setMode( GL_BLEND, 1 );
 
273
    set->setRenderingHint( osg::StateSet::TRANSPARENT_BIN );
 
274
    set->setAttribute( new osg::PolygonOffset(1,1), 1 );
 
275
 
 
276
    _boundaryGeode = new osg::Geode();
 
277
    _boundaryGeode->addDrawable( g );
 
278
}
 
279
 
 
280
bool
 
281
GeoCell::intersects( const osg::Polytope& tope ) const
 
282
{
 
283
    const osg::Polytope::PlaneList& planes = tope.getPlaneList();
 
284
    for( osg::Polytope::PlaneList::const_iterator i = planes.begin(); i != planes.end(); ++i )
 
285
    {
 
286
        if ( i->intersect( _boundaryPoints ) < 0 )
 
287
            return false;
 
288
    }
 
289
    return true;
 
290
}
 
291
 
 
292
void
 
293
GeoCell::traverse( osg::NodeVisitor& nv )
 
294
{
 
295
    bool isCull = nv.getVisitorType() == osg::NodeVisitor::CULL_VISITOR;
 
296
 
 
297
    if ( _depth > 0 )
 
298
    {
 
299
        if ( isCull )
 
300
        {
 
301
            // process boundary geometry, if present.
 
302
            if ( _boundaryGeode.valid() ) 
 
303
            {
 
304
                if ( _count > 0 )
 
305
                    (*_boundaryColor)[0].set(1,0,0,0.35);
 
306
                else
 
307
                    (*_boundaryColor)[0].set(1,1,1,0.25);
 
308
                _boundaryColor->dirty();
 
309
 
 
310
                _boundaryGeode->accept( nv );
 
311
            }
 
312
 
 
313
            // custom BSP culling function. this checks that the set of boundary points
 
314
            // for this cell intersects the viewing frustum.
 
315
            osgUtil::CullVisitor* cv = dynamic_cast<osgUtil::CullVisitor*>( &nv );
 
316
            if ( cv && !intersects( cv->getCurrentCullingSet().getFrustum() ) )
 
317
            {
 
318
                return;
 
319
            }
 
320
 
 
321
            // passed cull, so record the framestamp.
 
322
            _frameStamp = cv->getFrameStamp()->getFrameNumber();
 
323
        }
 
324
 
 
325
        if ( _objects.size() > 0 )
 
326
        {
 
327
            for( GeoObjectCollection::iterator i = _objects.begin(); i != _objects.end(); ++i )
 
328
            {
 
329
                osg::Node* node = i->second->getNode();
 
330
                if ( node )
 
331
                    node->accept( nv );
 
332
            }
 
333
        }
 
334
 
 
335
        if ( _clusterGeode.valid() )
 
336
            _clusterGeode->accept( nv );
 
337
    }
 
338
 
 
339
    else
 
340
    {
 
341
        if ( isCull )
 
342
            _frameStamp = nv.getFrameStamp()->getFrameNumber();
 
343
    }
 
344
 
 
345
    osg::LOD::traverse( nv );
 
346
}
 
347
 
 
348
void
 
349
GeoCell::adjustCount( int delta )
 
350
{
 
351
    _count += delta;
 
352
 
 
353
    if ( _depth > 0 && getNumParents() > 0 )
 
354
    {
 
355
        static_cast<GeoCell*>(getParent(0))->adjustCount( delta );        
 
356
 
 
357
#if 0
 
358
        if ( !_clusterGeode.valid() )
 
359
        {
 
360
            _clusterGeode = makeClusterGeode( _extent, _count );
 
361
        }
 
362
        else
 
363
        {
 
364
            osgText::Text* t = static_cast<osgText::Text*>( _clusterGeode->getDrawable(0) );
 
365
            std::stringstream buf;
 
366
            buf << _count;
 
367
            t->setText( buf.str() );
 
368
        }
 
369
#endif
 
370
    }
 
371
}
 
372
 
 
373
bool
 
374
GeoCell::insertObject( GeoObject* object )
 
375
{
 
376
    osg::Vec3d location;
 
377
    if ( object->getLocation(location) && _extent.contains(location.x(), location.y()) )
 
378
    {
 
379
        object->_cell = this;
 
380
        _objects.insert( std::make_pair(object->getPriority(), object) );
 
381
 
 
382
        if ( _objects.size() > _maxObjects )
 
383
        {
 
384
            GeoObjectCollection::iterator low = _objects.begin();
 
385
            GeoObject* lowPriObject = low->second.get();
 
386
            
 
387
            if ( getNumChildren() == 0 )
 
388
                split();
 
389
 
 
390
            lowPriObject->getLocation(location);
 
391
            unsigned index = getIndex(_extent, location, _splitDim, _splitDim);
 
392
            bool insertedOK = static_cast<GeoCell*>(getChild(index))->insertObject( lowPriObject );
 
393
            if ( insertedOK )
 
394
            {
 
395
                // remove it from this cell.
 
396
                _objects.erase( low );
 
397
            }
 
398
            else
 
399
            {
 
400
                // should never ever happen..
 
401
                OE_WARN << LC << "Object insertion failed" << std::endl;
 
402
            }
 
403
        }
 
404
        return true;
 
405
    }
 
406
    else
 
407
    {
 
408
        return false;
 
409
    }
 
410
}
 
411
 
 
412
void
 
413
GeoCell::split()
 
414
{
 
415
    // the max LOD range for children of this cell:
 
416
    float newRange = _maxRange * _splitRangeFactor;
 
417
 
 
418
    // first create all the child cells:
 
419
    double xInterval = _extent.width() / (double)_splitDim;
 
420
    double yInterval = _extent.height() / (double)_splitDim;
 
421
 
 
422
    for( unsigned row=0; row<_splitDim; ++row )
 
423
    {
 
424
        for( unsigned col=0; col<_splitDim; ++col )
 
425
        {
 
426
            GeoExtent cellExtent(
 
427
                _extent.getSRS(),
 
428
                _extent.xMin() + xInterval*(double)col,
 
429
                _extent.yMin() + yInterval*(double)row,
 
430
                _extent.xMin() + xInterval*(double)(col+1),
 
431
                _extent.yMin() + yInterval*(double)(row+1) );
 
432
 
 
433
            this->addChild(
 
434
                new GeoCell(cellExtent, newRange, _maxObjects, _splitDim, _splitRangeFactor, _depth+1),
 
435
                0.0f,
 
436
                newRange );
 
437
        }
 
438
    }
 
439
}
 
440
 
 
441
bool
 
442
GeoCell::removeObject( GeoObject* object )
 
443
{
 
444
    if ( object->_cell.get() == this )
 
445
    {
 
446
        object->_cell = 0L;
 
447
        _objects.erase( findObject(_objects, object) );
 
448
        adjustCount( -1 );
 
449
 
 
450
        // if we just fell beneath the threshold, pull one up from below.
 
451
        if ( _objects.size() == _minObjects-1 )
 
452
        {
 
453
            //TODO.
 
454
        }
 
455
 
 
456
        // TODO: rebalance, merge the tree, etc.
 
457
        return true;
 
458
    }
 
459
    else
 
460
    {
 
461
        for( unsigned i=0; i<getNumChildren(); ++i )
 
462
        {
 
463
            if ( static_cast<GeoCell*>(getChild(i))->removeObject( object ) )
 
464
                return true;
 
465
        }
 
466
    }
 
467
    return false;
 
468
}
 
469
 
 
470
void
 
471
GeoCell::merge()
 
472
{
 
473
    //NYI //TODO
 
474
}
 
475
 
 
476
bool
 
477
GeoCell::reindexObject( GeoObject* object )
 
478
{
 
479
    GeoCell* owner = object->getGeoCell();
 
480
    if ( owner )
 
481
    {
 
482
        osg::Vec3d location;
 
483
        if ( object->getLocation(location) && !owner->_extent.contains(location.x(), location.y()) )
 
484
        {
 
485
            // first remove from its current cell
 
486
            owner->removeObject( object );
 
487
            //object->_cell = 0L;
 
488
            //owner->_objects.erase( findObject(owner->_objects, object) );
 
489
            //owner->adjustCount( -1 );
 
490
 
 
491
            GeoCell* cell = dynamic_cast<GeoCell*>( owner->getParent(0) );
 
492
            while( cell )
 
493
            {
 
494
                if ( cell->getExtent().contains(location.x(), location.y()) )
 
495
                {
 
496
                    if ( cell->insertObject( object ) )
 
497
                        return true;
 
498
                }
 
499
                cell = dynamic_cast<GeoCell*>( cell->getParent(0) );
 
500
            }
 
501
        }
 
502
 
 
503
        // no change
 
504
        return true;
 
505
    }
 
506
    else
 
507
    {
 
508
        return insertObject( object );
 
509
    }
 
510
}
 
511
 
 
512
#if 0
 
513
bool
 
514
GeoCell::reindex( GeoObject* object )
 
515
{
 
516
    osg::Vec3d location;
 
517
    if ( object->getLocation(location) && !_extent.contains(location.x(), location.y()) )
 
518
    {
 
519
        // first remove from its current cell
 
520
        osg::ref_ptr<GeoCell> safeCell = object->_cell.get();
 
521
        if ( safeCell.valid() )
 
522
        {
 
523
            object->_cell = 0L;
 
524
            safeCell->_objects.erase( findObject(safeCell->_objects, object) );
 
525
            //safeCell->_objects.erase( std::find( _objects.begin(), _objects.end(), std::make_pair(object->getPriority(),object) ) );
 
526
            //safeCell->_objects.erase( std::find( safeCell->_objects.begin(), safeCell->_objects.end(), object ) );
 
527
            safeCell->adjustCount( -1 );
 
528
            //safeCell->removeObject( object );
 
529
        }
 
530
 
 
531
        GeoCell* cell = dynamic_cast<GeoCell*>( this->getParent(0) );
 
532
        while( cell )
 
533
        {
 
534
            if ( cell->getExtent().contains(location.x(), location.y()) )
 
535
            {
 
536
                if ( cell->insertObject( object ) )
 
537
                    return true;
 
538
            }
 
539
            cell = dynamic_cast<GeoCell*>( cell->getParent(0) );
 
540
        }
 
541
    }
 
542
 
 
543
    return true;
 
544
}
 
545
#endif