osgEarth 2.1.1
Classes | Typedefs | Functions

anonymous_namespace{MeshSubdivider.cpp} Namespace Reference

Classes

struct  Triangle
struct  TriangleData
struct  Edge
struct  Line
struct  LineData

Typedefs

typedef std::queue< TriangleTriangleQueue
typedef std::vector< TriangleTriangleVector
typedef std::map< Edge, GLuint > EdgeMap
typedef std::queue< LineLineQueue
typedef std::vector< LineLineVector

Functions

osg::Vec3d bisector (const osg::Vec3d &v0, const osg::Vec3d &v1)
void geocentricToGeodetic (const osg::Vec3d &g, osg::Vec2d &out_geod)
void geodeticMidpoint (const osg::Vec2d &g0, const osg::Vec2d &g1, osg::Vec2d &out_mid)
osg::Vec3d geocentricMidpoint (const osg::Vec3d &v0, const osg::Vec3d &v1, GeoInterpolation interp)
double geocentricSurfaceDistance (const osg::Vec3d &v0, const osg::Vec3d &v1)
double angleBetween (const osg::Vec3d &v0, const osg::Vec3d &v1)
template<typename ETYPE , typename VTYPE >
void populateTriangles (osg::Geometry &geom, const TriangleVector &tris, unsigned int maxElementsPerEBO)
template<typename ETYPE , typename VTYPE >
void populateLines (osg::Geometry &geom, const LineVector &lines, unsigned int maxElementsPerEBO)
static const osg::Vec3d s_pole (0, 0, 1)
static const double s_maxLatAdjustment (0.75)
void subdivideLines (double granularity, GeoInterpolation interp, osg::Geometry &geom, const osg::Matrixd &W2L, const osg::Matrixd &L2W, unsigned int maxElementsPerEBO)
void subdivideTriangles (double granularity, GeoInterpolation interp, osg::Geometry &geom, const osg::Matrixd &W2L, const osg::Matrixd &L2W, unsigned int maxElementsPerEBO)
void subdivide (double granularity, GeoInterpolation interp, osg::Geometry &geom, const osg::Matrixd &W2L, const osg::Matrixd &L2W, unsigned int maxElementsPerEBO)

Typedef Documentation

typedef std::map<Edge,GLuint> anonymous_namespace{MeshSubdivider.cpp}::EdgeMap

Definition at line 214 of file MeshSubdivider.cpp.

typedef std::queue<Line> anonymous_namespace{MeshSubdivider.cpp}::LineQueue

Definition at line 267 of file MeshSubdivider.cpp.

typedef std::vector<Line> anonymous_namespace{MeshSubdivider.cpp}::LineVector

Definition at line 268 of file MeshSubdivider.cpp.

typedef std::queue<Triangle> anonymous_namespace{MeshSubdivider.cpp}::TriangleQueue

Definition at line 127 of file MeshSubdivider.cpp.

typedef std::vector<Triangle> anonymous_namespace{MeshSubdivider.cpp}::TriangleVector

Definition at line 128 of file MeshSubdivider.cpp.


Function Documentation

double anonymous_namespace{MeshSubdivider.cpp}::angleBetween ( const osg::Vec3d &  v0,
const osg::Vec3d &  v1 
)

Definition at line 110 of file MeshSubdivider.cpp.

    {
        osg::Vec3d v0n = v0; v0n.normalize();
        osg::Vec3d v1n = v1; v1n.normalize();
        return fabs( acos( v0n * v1n ) );
    }

Here is the caller graph for this function:

osg::Vec3d anonymous_namespace{MeshSubdivider.cpp}::bisector ( const osg::Vec3d &  v0,
const osg::Vec3d &  v1 
)

Definition at line 40 of file MeshSubdivider.cpp.

    {
        osg::Vec3d f = (v0+v1)*0.5;
        f.normalize();
        return f * 0.5*(v0.length() + v1.length());
    }

Here is the caller graph for this function:

osg::Vec3d anonymous_namespace{MeshSubdivider.cpp}::geocentricMidpoint ( const osg::Vec3d &  v0,
const osg::Vec3d &  v1,
GeoInterpolation  interp 
)

Definition at line 74 of file MeshSubdivider.cpp.

    {
        if ( interp == GEOINTERP_GREAT_CIRCLE )
        {
            return bisector(v0, v1);
        }
        else
        {
            // geocentric to spherical:
            osg::Vec2d g0, g1;
            geocentricToGeodetic(v0, g0);
            geocentricToGeodetic(v1, g1);

            osg::Vec2d mid;
            geodeticMidpoint(g0, g1, mid);

            double size = 0.5*(v0.length() + v1.length());

            // spherical to geocentric:
            double sin_lat = sin(mid.y());
            return osg::Vec3d( cos(mid.x())*sin_lat, sin(mid.x())*sin_lat, cos(mid.y()) ) * size;
        }
    }

Here is the call graph for this function:

Here is the caller graph for this function:

double anonymous_namespace{MeshSubdivider.cpp}::geocentricSurfaceDistance ( const osg::Vec3d &  v0,
const osg::Vec3d &  v1 
)

Definition at line 100 of file MeshSubdivider.cpp.

    {
        osg::Vec2d g0, g1;
        geocentricToGeodetic(v0, g0);
        geocentricToGeodetic(v1, g1);
        return GeoMath::distance( v0.y(), v0.x(), v1.y(), v1.x() );
    }

Here is the call graph for this function:

void anonymous_namespace{MeshSubdivider.cpp}::geocentricToGeodetic ( const osg::Vec3d &  g,
osg::Vec2d &  out_geod 
)

Definition at line 49 of file MeshSubdivider.cpp.

    {
        double r = g.length();
        out_geod.set( atan2(g.y(),g.x()), acos(g.z()/r) );
    }

Here is the caller graph for this function:

void anonymous_namespace{MeshSubdivider.cpp}::geodeticMidpoint ( const osg::Vec2d &  g0,
const osg::Vec2d &  g1,
osg::Vec2d &  out_mid 
)

Definition at line 58 of file MeshSubdivider.cpp.

    {
        if ( fabs(g0.x()-g1.x()) < osg::PI )
            out_mid.set( 0.5*(g0.x()+g1.x()), 0.5*(g0.y()+g1.y()) );
        else if ( g1.x() > g0.x() )
            out_mid.set( 0.5*((g0.x()+2*osg::PI)+g1.x()), 0.5*(g0.y()+g1.y()) );
        else
           out_mid.set( 0.5*(g0.x()+(g1.x()+2*osg::PI)), 0.5*(g0.y()+g1.y()) );

        //GeoMath::midpoint(g0.y(), g0.x(), g1.y(), g1.x(), out_mid.y(), out_mid.x());
    }

Here is the caller graph for this function:

template<typename ETYPE , typename VTYPE >
void anonymous_namespace{MeshSubdivider.cpp}::populateLines ( osg::Geometry &  geom,
const LineVector &  lines,
unsigned int  maxElementsPerEBO 
)

Populates the geometry object with a collection of index elements primitives.

Definition at line 308 of file MeshSubdivider.cpp.

    {
        unsigned int totalLines = lines.size();
        unsigned int totalLinesWritten = 0;
        unsigned int numElementsInCurrentEBO = maxElementsPerEBO;

        ETYPE* ebo = 0L;

        for( LineVector::const_iterator i = lines.begin(); i != lines.end(); ++i )
        {
            if ( numElementsInCurrentEBO+2 >= maxElementsPerEBO )
            {
                if ( ebo )
                {
                    geom.addPrimitiveSet( ebo );
                }

                ebo = new ETYPE( GL_LINES );

                unsigned int linesRemaining = totalLines - totalLinesWritten;
                ebo->reserve( osg::minimum( linesRemaining*2, maxElementsPerEBO ) );

                numElementsInCurrentEBO = 0;
            }
            ebo->push_back( static_cast<VTYPE>( i->_i0 ) );
            ebo->push_back( static_cast<VTYPE>( i->_i1 ) );

            numElementsInCurrentEBO += 3;
            ++totalLinesWritten;
        }

        if ( ebo && ebo->size() > 0 )
        {
            geom.addPrimitiveSet( ebo );
        }
    }
template<typename ETYPE , typename VTYPE >
void anonymous_namespace{MeshSubdivider.cpp}::populateTriangles ( osg::Geometry &  geom,
const TriangleVector &  tris,
unsigned int  maxElementsPerEBO 
)

Populates the geometry object with a collection of index elements primitives.

Definition at line 220 of file MeshSubdivider.cpp.

    {
        unsigned int totalTris = tris.size();
        unsigned int totalTrisWritten = 0;
        unsigned int numElementsInCurrentEBO = maxElementsPerEBO;

        ETYPE* ebo = 0L;

        for( TriangleVector::const_iterator i = tris.begin(); i != tris.end(); ++i )
        {
            if ( numElementsInCurrentEBO+2 >= maxElementsPerEBO )
            {
                if ( ebo )
                {
                    geom.addPrimitiveSet( ebo );
                }

                ebo = new ETYPE( GL_TRIANGLES );

                unsigned int trisRemaining = totalTris - totalTrisWritten;
                ebo->reserve( osg::minimum( trisRemaining*3, maxElementsPerEBO ) );

                numElementsInCurrentEBO = 0;
            }
            ebo->push_back( static_cast<VTYPE>( i->_i0 ) );
            ebo->push_back( static_cast<VTYPE>( i->_i1 ) );
            ebo->push_back( static_cast<VTYPE>( i->_i2 ) );

            numElementsInCurrentEBO += 3;
            ++totalTrisWritten;
        }

        if ( ebo && ebo->size() > 0 )
        {
            geom.addPrimitiveSet( ebo );
        }
    }
static const double anonymous_namespace{MeshSubdivider.cpp}::s_maxLatAdjustment ( 0.  75) [static]
static const osg::Vec3d anonymous_namespace{MeshSubdivider.cpp}::s_pole ( ,
,
 
) [static]
void anonymous_namespace{MeshSubdivider.cpp}::subdivide ( double  granularity,
GeoInterpolation  interp,
osg::Geometry &  geom,
const osg::Matrixd &  W2L,
const osg::Matrixd &  L2W,
unsigned int  maxElementsPerEBO 
)

Definition at line 561 of file MeshSubdivider.cpp.

    {
        GLenum mode = geom.getPrimitiveSet(0)->getMode();

        if ( mode == GL_POINTS )
            return;

        if ( mode == GL_LINES || mode == GL_LINE_STRIP || mode == GL_LINE_LOOP )
        {
            subdivideLines( granularity, interp, geom, W2L, L2W, maxElementsPerEBO );
        }
        else
        {
            subdivideTriangles( granularity, interp, geom, W2L, L2W, maxElementsPerEBO );

            //osgUtil::VertexCacheVisitor cacheOptimizer;
            //cacheOptimizer.optimizeVertices( geom );
        }
        
        //osgUtil::VertexAccessOrderVisitor orderOptimizer;
        //orderOptimizer.optimizeOrder( geom );
    }

Here is the call graph for this function:

Here is the caller graph for this function:

void anonymous_namespace{MeshSubdivider.cpp}::subdivideLines ( double  granularity,
GeoInterpolation  interp,
osg::Geometry &  geom,
const osg::Matrixd &  W2L,
const osg::Matrixd &  L2W,
unsigned int  maxElementsPerEBO 
)

Collects all the line segments from the geometry, coalesces them into a single line set, subdivides it according to the granularity threshold, and replaces the data in the Geometry object with the new vertex and primitive data.

Definition at line 353 of file MeshSubdivider.cpp.

    {
        // collect all the line segments in the geometry.
        LineFunctor<LineData> data;
        geom.accept( data );
    
        int numLinesIn = data._lines.size();

        LineVector done;
        done.reserve( 2 * data._lines.size() );

        // Subdivide lines until we run out.
        while( data._lines.size() > 0 )
        {
            Line line = data._lines.front();
            data._lines.pop();

            osg::Vec3d v0_w = (*data._verts)[line._i0] * L2W;
            osg::Vec3d v1_w = (*data._verts)[line._i1] * L2W;

            double g0 = angleBetween(v0_w, v1_w);

            if ( g0 > granularity )
            {
                data._verts->push_back( geocentricMidpoint(v0_w, v1_w, interp) * W2L );
                GLuint i = data._verts->size()-1;

                data._lines.push( Line( line._i0, i ) );
                data._lines.push( Line( i, line._i1 ) );
            }
            else
            {
                // line is small enough- put it on the "done" list.
                done.push_back( line );
            }
        }

        if ( done.size() > 0 )
        {
            while( geom.getNumPrimitiveSets() > 0 )
                geom.removePrimitiveSet(0);

            // set the new VBO.
            geom.setVertexArray( data._verts );

            if ( data._verts->size() < 256 )
                populateLines<osg::DrawElementsUByte,GLubyte>( geom, done, maxElementsPerEBO );
            else if ( data._verts->size() < 65536 )
                populateLines<osg::DrawElementsUShort,GLushort>( geom, done, maxElementsPerEBO );
            else
                populateLines<osg::DrawElementsUInt,GLuint>( geom, done, maxElementsPerEBO );
        }
    }

Here is the call graph for this function:

Here is the caller graph for this function:

void anonymous_namespace{MeshSubdivider.cpp}::subdivideTriangles ( double  granularity,
GeoInterpolation  interp,
osg::Geometry &  geom,
const osg::Matrixd &  W2L,
const osg::Matrixd &  L2W,
unsigned int  maxElementsPerEBO 
)

Collects all the triangles from the geometry, coalesces them into a single triangle set, subdivides them according to the granularity threshold, and replaces the data in the Geometry object with the new vertex and primitive data.

The subdivision algorithm is adapted from http://bit.ly/dTIagq (c) Copyright 2010 Patrick Cozzi and Deron Ohlarik, MIT License.

Definition at line 425 of file MeshSubdivider.cpp.

    {
        
        // collect all the triangled in the geometry.
        osg::TriangleIndexFunctor<TriangleData> data;;
        data.setSourceVerts(dynamic_cast<osg::Vec3Array*>(geom.getVertexArray()));
        data.setSourceTexCoords(dynamic_cast<osg::Vec2Array*>(geom.getTexCoordArray(0)));
        geom.accept( data );

        
        int numTrisIn = data._tris.size();        

        TriangleVector done;
        done.reserve(2.0 * data._tris.size());

        // Used to make sure shared edges are not split more than once.
        EdgeMap edges;

        // Subdivide triangles until we run out
        while( data._tris.size() > 0 )
        {
            Triangle tri = data._tris.front();
            data._tris.pop();

            osg::Vec3d v0_w = (*data._verts)[tri._i0] * L2W;
            osg::Vec3d v1_w = (*data._verts)[tri._i1] * L2W;
            osg::Vec3d v2_w = (*data._verts)[tri._i2] * L2W;

            osg::Vec2  t0 = (*data._texcoords)[tri._i0];
            osg::Vec2  t1 = (*data._texcoords)[tri._i1];
            osg::Vec2  t2 = (*data._texcoords)[tri._i2];

            double g0 = angleBetween(v0_w, v1_w);
            double g1 = angleBetween(v1_w, v2_w);
            double g2 = angleBetween(v2_w, v0_w);
            double max = osg::maximum( g0, osg::maximum(g1, g2) );

            if ( max > granularity )
            {
                if ( g0 == max )
                {
                    Edge edge( osg::minimum(tri._i0, tri._i1), osg::maximum(tri._i0, tri._i1) );
                    
                    EdgeMap::iterator ei = edges.find(edge);
                    GLuint i;
                    if ( ei == edges.end() )
                    {
                        data._verts->push_back( geocentricMidpoint(v0_w, v1_w, interp) * W2L );
                        data._texcoords->push_back( (t0 + t1) / 2.0f );
                        i = data._verts->size() - 1;
                        edges[edge] = i;
                    }
                    else
                    {
                        i = ei->second;
                    }

                    data._tris.push( Triangle(tri._i0, i, tri._i2) );
                    data._tris.push( Triangle(i, tri._i1, tri._i2) );
                }
                else if ( g1 == max )
                {
                    Edge edge( osg::minimum(tri._i1, tri._i2), osg::maximum(tri._i1,tri._i2) );

                    EdgeMap::iterator ei = edges.find(edge);
                    GLuint i;
                    if ( ei == edges.end() )
                    {
                        data._verts->push_back( geocentricMidpoint(v1_w, v2_w, interp) * W2L );
                        data._texcoords->push_back( (t1 + t2) / 2.0f );
                        i = data._verts->size() - 1;
                        edges[edge] = i;
                    }
                    else
                    {
                        i = ei->second;
                    }

                    data._tris.push( Triangle(tri._i1, i, tri._i0) );
                    data._tris.push( Triangle(i, tri._i2, tri._i0) );
                }
                else if ( g2 == max )
                {
                    Edge edge( osg::minimum(tri._i2, tri._i0), osg::maximum(tri._i2,tri._i0) );

                    EdgeMap::iterator ei = edges.find(edge);
                    GLuint i;
                    if ( ei == edges.end() )
                    {
                        data._verts->push_back( geocentricMidpoint(v2_w, v0_w, interp) * W2L );
                        data._texcoords->push_back( (t2 + t0) / 2.0f );
                        i = data._verts->size() - 1;
                        edges[edge] = i;
                    }
                    else
                    {
                        i = ei->second;
                    }

                    data._tris.push( Triangle(tri._i2, i, tri._i1) );
                    data._tris.push( Triangle(i, tri._i0, tri._i1) );
                }
            }
            else
            {
                // triangle is small enough- put it on the "done" list.
                done.push_back(tri);
            }
        }

        if ( done.size() > 0 )
        {
            // first, remove the old primitive sets.
            while( geom.getNumPrimitiveSets() > 0 )
                geom.removePrimitiveSet( 0 );

            // set the new VBO.
            geom.setVertexArray( data._verts.get() );

            geom.setTexCoordArray(0, data._texcoords.get() );

            if ( data._verts->size() < 256 )
                populateTriangles<osg::DrawElementsUByte,GLubyte>( geom, done, maxElementsPerEBO );
            else if ( data._verts->size() < 65536 )
                populateTriangles<osg::DrawElementsUShort,GLushort>( geom, done, maxElementsPerEBO );
            else
                populateTriangles<osg::DrawElementsUInt,GLuint>( geom, done, maxElementsPerEBO );
        }
    }

Here is the call graph for this function:

Here is the caller graph for this function:

 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines