osg::HalfEdgeGraph Class Reference

#include <OSGHalfEdgeGraph.h>

List of all members.

Public Types
typedef UInt32	IndexT
Public Member Functions
	HalfEdgeGraph (void)
	HalfEdgeGraph (const HalfEdgeGraph &obj)
virtual	~HalfEdgeGraph (void)
void	reserve (UInt32 vertexNum, UInt32 triangleNum, UInt32 reserveEdges=8)
bool	addTriangle (IndexT v0, IndexT v1, IndexT v2)
UInt32	triangleCount (void)
bool	verify (bool verbose=false)
UInt32	calcOptPrim (UInt32 iteration=1, bool doStrip=true, bool doFan=true, UInt32 minFanTriangleCount=16)
UInt32	primitiveCount (void)
Int32	getPrimitive (std::vector< IndexT > &indexVec, Int32 type=0)
Int32	calcEgdeLines (std::vector< IndexT > &indexVec, bool codeBorder=false)
void	clear (void)
Protected Member Functions
HalfEdge *	getHalfEdge (UInt32 startVertexIndex, UInt32 endVertexIndex)
void	addHalfEdge (HalfEdge &halfEdge, UInt32 startVertexIndex, UInt32 endVertexIndex)
HalfEdge *	findGateEdge (Triangle *triangleOut, Triangle *triangleIn)
Int32	calcStripCost (TriangleList &strip, bool reverse)
Int32	fillIndexFromFan (std::vector< IndexT > &indexVec, HalfEdge &firstEdge)
Int32	fillIndexFromStrip (std::vector< IndexT > &indexVec, TriangleList &strip, bool reverse)
Private Types
enum	TriangleState {   INVALID = -30, FAN_PART = -20, STRIP_PART = -10, DEGREE_0 = 0,   DEGREE_1 = 1, DEGREE_2 = 2, DEGREE_3 = 3 }
enum	WalkCase { START, LEFT, RIGHT, FINISH }
typedef std::vector< std::pair < UInt32, HalfEdge * > >	HalfEdgeLink
typedef std::pair< IndexT, TriangleList * >	Primitive
Private Member Functions
void	dropOutTriangle (Triangle &triangle, TriangleList *degreeBag)
Private Attributes
std::vector< HalfEdgeLink >	_edgeLinkVec
TrianglePool	_trianglePool
TriangleList	_validTriangleBag
TriangleList	_invalidTriangleBag
std::vector< Primitive >	_stripBag
std::vector< Primitive >	_fanBag
std::vector< Primitive >	_triBag
Friends
class	HalfEdge
class	Triangle
class	TriangleList
class	TrianglePool
class	TrianglePool::Chunk
Classes
class	HalfEdge
class	Triangle
class	TriangleList
class	TrianglePool

---

Detailed Description

Definition at line 59 of file OSGHalfEdgeGraph.h.

---

Member Typedef Documentation

typedef UInt32 osg::HalfEdgeGraph::IndexT

Definition at line 63 of file OSGHalfEdgeGraph.h.

typedef std::vector< std::pair<UInt32,HalfEdge *> > osg::HalfEdgeGraph::HalfEdgeLink [private]

Definition at line 165 of file OSGHalfEdgeGraph.h.

typedef std::pair<IndexT,TriangleList*> osg::HalfEdgeGraph::Primitive [private]

Definition at line 176 of file OSGHalfEdgeGraph.h.

---

Member Enumeration Documentation

enum osg::HalfEdgeGraph::TriangleState [private]

Enumerator:

INVALID
FAN_PART
STRIP_PART
DEGREE_0
DEGREE_1
DEGREE_2
DEGREE_3

Definition at line 67 of file OSGHalfEdgeGraph.h.

                       { INVALID = -30, FAN_PART = -20, STRIP_PART = -10,
                         DEGREE_0 = 0, DEGREE_1 = 1, DEGREE_2 = 2,
                         DEGREE_3 = 3 };

enum osg::HalfEdgeGraph::WalkCase [private]

Enumerator:

START
LEFT
RIGHT
FINISH

Definition at line 71 of file OSGHalfEdgeGraph.h.

{ START, LEFT, RIGHT, FINISH };

---

Constructor & Destructor Documentation

HalfEdgeGraph::HalfEdgeGraph

(

void

)

Definition at line 70 of file OSGHalfEdgeGraph.cpp.

{
}

HalfEdgeGraph::HalfEdgeGraph

(

const HalfEdgeGraph &

obj

)

Definition at line 81 of file OSGHalfEdgeGraph.cpp.

References SWARNING.

{
    SWARNING << "Run HalfEdgeGraph copy constructor; not impl.\n" << endl;
}

HalfEdgeGraph::~HalfEdgeGraph

(

void

)

[virtual]

Definition at line 93 of file OSGHalfEdgeGraph.cpp.

References clear().

{
    clear();
}

---

Member Function Documentation

void osg::HalfEdgeGraph::dropOutTriangle	(	Triangle &	triangle,
		TriangleList *	degreeBag
	)			[inline, private]

Definition at line 287 of file OSGHalfEdgeGraph.inl.

References osg::HalfEdgeGraph::TriangleList::add(), osg::HalfEdgeGraph::Triangle::halfEdgeVec, osg::HalfEdgeGraph::TriangleList::release(), osg::HalfEdgeGraph::Triangle::state, STRIP_PART, osg::HalfEdgeGraph::HalfEdge::triangle, and osg::HalfEdgeGraph::HalfEdge::twin.

Referenced by calcOptPrim().

{
    HalfEdge *twin;
    degreeBag[triangle.state].release(triangle);
    triangle.state = STRIP_PART;

    if((twin = triangle.halfEdgeVec[0].twin) && (twin->triangle->state > 0))
    {
        degreeBag[twin->triangle->state--].release(*twin->triangle);
        degreeBag[twin->triangle->state].add(*twin->triangle);
    }

    if((twin = triangle.halfEdgeVec[1].twin) && (twin->triangle->state > 0))
    {
        degreeBag[twin->triangle->state--].release(*twin->triangle);
        degreeBag[twin->triangle->state].add(*twin->triangle);
    }

    if((twin = triangle.halfEdgeVec[2].twin) && (twin->triangle->state > 0))
    {
        degreeBag[twin->triangle->state--].release(*twin->triangle);
        degreeBag[twin->triangle->state].add(*twin->triangle);
    }
}

HalfEdgeGraph::HalfEdge * osg::HalfEdgeGraph::getHalfEdge	(	UInt32	startVertexIndex,
		UInt32	endVertexIndex
	)			[inline, protected]

Definition at line 314 of file OSGHalfEdgeGraph.inl.

References _edgeLinkVec.

Referenced by addHalfEdge(), and addTriangle().

{
    UInt32 i, n = _edgeLinkVec.size();
    const HalfEdgeLink *edgeLink((startVertexIndex < n) ?
        &_edgeLinkVec[startVertexIndex] : 0);

    HalfEdge *halfEdge = 0;

    if (edgeLink && (n = edgeLink->size()))
    {
        for (i = 0; i < n; ++i)
        {
            if ((*edgeLink)[i].first == endVertexIndex)
            {
                halfEdge = (*edgeLink)[i].second;
                break;
            }
        }
    }

    return halfEdge;
}

void osg::HalfEdgeGraph::addHalfEdge	(	HalfEdge &	halfEdge,
		UInt32	startVertexIndex,
		UInt32	endVertexIndex
	)			[inline, protected]

Definition at line 339 of file OSGHalfEdgeGraph.inl.

References _edgeLinkVec, getHalfEdge(), osg::HalfEdgeGraph::HalfEdge::setVertex(), osg::HalfEdgeGraph::Triangle::state, osg::HalfEdgeGraph::HalfEdge::triangle, and osg::HalfEdgeGraph::HalfEdge::twin.

Referenced by addTriangle().

{
    UInt32 n(_edgeLinkVec.size());
    bool     validIndex(startVertexIndex < n);
    HalfEdge *twin(validIndex ?
        getHalfEdge(endVertexIndex, startVertexIndex) : 0);

    halfEdge.setVertex(startVertexIndex,endVertexIndex);

    if(validIndex == false)
        _edgeLinkVec.resize(startVertexIndex * 2);

    _edgeLinkVec[startVertexIndex].
        push_back(std::pair<HalfEdgeGraph::IndexT,HalfEdge*>(endVertexIndex,
                                                             &halfEdge));

    if((halfEdge.twin = twin))
    {
        twin->twin = &halfEdge;
        halfEdge.triangle->state++;
        twin->triangle->state++;
    }
} 

HalfEdgeGraph::HalfEdge * osg::HalfEdgeGraph::findGateEdge	(	Triangle *	triangleOut,
		Triangle *	triangleIn
	)			[inline, protected]

Definition at line 365 of file OSGHalfEdgeGraph.inl.

References osg::HalfEdgeGraph::Triangle::halfEdgeVec, osg::HalfEdgeGraph::HalfEdge::triangle, and osg::HalfEdgeGraph::HalfEdge::twin.

Referenced by calcStripCost().

{
    HalfEdgeGraph::HalfEdge *halfEdge = 0;

    if(triangleOut && triangleIn)
        if(!(halfEdge = triangleOut->halfEdgeVec[0].twin) || 
            (halfEdge->triangle != triangleIn))
            if(!(halfEdge = triangleOut->halfEdgeVec[1].twin) || 
                (halfEdge->triangle != triangleIn))
                if(!(halfEdge = triangleOut->halfEdgeVec[2].twin) || 
                    (halfEdge->triangle != triangleIn))
                    halfEdge = 0;

    return halfEdge ? halfEdge->twin : 0;
}

Int32 HalfEdgeGraph::calcStripCost	(	TriangleList &	strip,
		bool	reverse
	)			[protected]

Definition at line 655 of file OSGHalfEdgeGraph.cpp.

References findGateEdge(), osg::HalfEdgeGraph::TriangleList::first, osg::HalfEdgeGraph::TriangleList::last, LEFT, osg::HalfEdgeGraph::HalfEdge::next, osg::HalfEdgeGraph::Triangle::next, osg::HalfEdgeGraph::Triangle::prev, RIGHT, and osg::HalfEdgeGraph::HalfEdge::twin.

Referenced by calcOptPrim().

{
    Triangle *triangle = rev ? strip.last : strip.first, *nextTriangle;
    HalfEdge /* *firstEdge, */ *halfEdge, *gate;
    WalkCase walkCase;
    Int32 cost = 0;

    if (triangle)
    {
        cost = 3;
        if ((nextTriangle = rev ? triangle->prev : triangle->next))
        {
            gate = findGateEdge(triangle,nextTriangle);
            //firstEdge = gate->next->next;
            ++cost;
            walkCase = LEFT;
            for(triangle = nextTriangle; 
                (nextTriangle = (rev ? triangle->prev : triangle->next));
                triangle = nextTriangle)
            {
                halfEdge = gate->twin;
                gate = findGateEdge(triangle,nextTriangle); 
                if (walkCase == RIGHT)
                {
                    // RIGHT
                    if(halfEdge->next == gate)
                    {
                        ++cost;
                        walkCase = LEFT;
                    }
                    else
                    {
                        // swap; walkCase stays RIGHT;
                        cost += 2;
                    }
                }
                else
                {
                    // LEFT
                    if(halfEdge->next->next == gate)
                    {
                        ++cost;
                        walkCase = RIGHT;
                    }
                    else
                    {
                        // swap; walkCase stays LEFT;
                        cost += 2;
                    }
                }
            }
        }
    }

    return cost;
}

Int32 osg::HalfEdgeGraph::fillIndexFromFan	(	std::vector< IndexT > &	indexVec,
		HalfEdge &	firstEdge
	)			[protected]

Int32 osg::HalfEdgeGraph::fillIndexFromStrip	(	std::vector< IndexT > &	indexVec,
		TriangleList &	strip,
		bool	reverse
	)			[protected]

void HalfEdgeGraph::reserve	(	UInt32	vertexNum,
		UInt32	triangleNum,
		UInt32	reserveEdges = 8
	)

Definition at line 174 of file OSGHalfEdgeGraph.cpp.

References _edgeLinkVec, _trianglePool, and osg::HalfEdgeGraph::TrianglePool::setChunkSize().

Referenced by osg::createOptimizedPrimitives().

{
    UInt32 i;

    _trianglePool.setChunkSize(triangleNum);
    _edgeLinkVec.resize(vertexNum); 

    if(reserveEdges > 0)
    {
        for(i = 0; i < vertexNum; ++i)
            _edgeLinkVec[i].reserve(reserveEdges);
    }
}

bool osg::HalfEdgeGraph::addTriangle	(	HalfEdgeGraph::IndexT	v0,
		HalfEdgeGraph::IndexT	v1,
		HalfEdgeGraph::IndexT	v2
	)			[inline]

Definition at line 383 of file OSGHalfEdgeGraph.inl.

References _invalidTriangleBag, _trianglePool, _validTriangleBag, osg::HalfEdgeGraph::TriangleList::add(), addHalfEdge(), osg::HalfEdgeGraph::TrianglePool::createTriangle(), getHalfEdge(), osg::HalfEdgeGraph::Triangle::halfEdgeVec, osg::HalfEdgeGraph::Triangle::init(), INVALID, osg::HalfEdgeGraph::HalfEdge::setVertex(), and osg::HalfEdgeGraph::Triangle::state.

Referenced by osg::createOptimizedPrimitives().

{
    Triangle *triangle = 0;
    
    if ((v0 != v1) && (v0 != v2) && (v2 != v1))
    {
        // create new triangle
        triangle = _trianglePool.createTriangle();
        triangle->init();
        
        // reg edges
        if (!getHalfEdge(v0,v1) && !getHalfEdge(v1,v2) && !getHalfEdge(v2,v0))
        {
            addHalfEdge(triangle->halfEdgeVec[0],v0,v1);
            addHalfEdge(triangle->halfEdgeVec[1],v1,v2);
            addHalfEdge(triangle->halfEdgeVec[2],v2,v0);
            _validTriangleBag.add(*triangle);
            return true;
        }
        else
        {
            triangle->halfEdgeVec[0].setVertex(v0,v1);
            triangle->halfEdgeVec[1].setVertex(v1,v2);
            triangle->halfEdgeVec[2].setVertex(v2,v0);
            triangle->state = INVALID;
            _invalidTriangleBag.add(*triangle);
            return false;
        }
    }
    return false;
}

UInt32 osg::HalfEdgeGraph::triangleCount

(

void

)

[inline]

Definition at line 418 of file OSGHalfEdgeGraph.inl.

References _trianglePool, and osg::HalfEdgeGraph::TrianglePool::countElem().

{
    return _trianglePool.countElem();
}

bool HalfEdgeGraph::verify

(

bool

verbose = false

)

Definition at line 196 of file OSGHalfEdgeGraph.cpp.

References _edgeLinkVec, _invalidTriangleBag, _validTriangleBag, osg::HalfEdgeGraph::TriangleList::countElem(), FINFO, osg::HalfEdgeGraph::TriangleList::first, osg::HalfEdgeGraph::Triangle::halfEdgeVec, osg::HalfEdgeGraph::Triangle::next, SINFO, osg::HalfEdgeGraph::Triangle::state, osg::HalfEdgeGraph::HalfEdge::triangle, osg::HalfEdgeGraph::HalfEdge::twin, osg::HalfEdgeGraph::Triangle::verify(), and osg::HalfEdgeGraph::HalfEdge::vertexStart().

Referenced by osg::createOptimizedPrimitives().

{
    bool retCode = true;
    UInt32 i, n;
    Triangle *triangle, *nt0, *nt1, *nt2;
    Int32 triangleState[4];
    Int32 invalidTriangles = 0;
    Int32 halfEdgeCount = 0;
    map< Int32, Int32 > connectionMap;
    map< Int32, Int32 >::iterator connectionI;
    Int32 connectionCount;
    bool validTri = false;

    for(i = 0; i < 4; ++i)
        triangleState[i] = 0;

    for( i = 0, triangle = _validTriangleBag.first; 
         triangle; 
         i++, triangle = triangle->next)
    {
        if(triangle->verify() && 
           (triangle->state >= 0) || (triangle->state <= 3))
        {
            triangleState[triangle->state]++;
            validTri = true;
        }
        else
        {
            ++invalidTriangles;
            validTri = false;
        }

        if ( verbose ) 
        {
            nt0 = triangle->halfEdgeVec[0].twin ? 
              triangle->halfEdgeVec[0].twin->triangle : 0;
            nt1 = triangle->halfEdgeVec[1].twin ? 
              triangle->halfEdgeVec[1].twin->triangle : 0;
            nt2 = triangle->halfEdgeVec[2].twin ? 
              triangle->halfEdgeVec[2].twin->triangle : 0;
            
            FINFO ( ( "HEG: Triangle %p: %d %d %d, %p %p %p: %s\n",
                      triangle, 
                      triangle->halfEdgeVec[0].vertexStart(),
                      triangle->halfEdgeVec[1].vertexStart(),
                      triangle->halfEdgeVec[2].vertexStart(),
                      nt0, nt1, nt2,
                      (validTri ? "VALID" : "INVALID" ) ) );
        }
    }

    SINFO << "HEG: linked triangle count " << _validTriangleBag.countElem()
          << endl;
    SINFO << "HEG: invalid triangle " << invalidTriangles 
          << endl;
    SINFO << "HEG: nonmanifold split: " << _invalidTriangleBag.countElem() 
          << endl;

    SINFO << "HEG: triangle state: "
          << triangleState[0]
          << "/"
          << triangleState[1]
          << "/"
          << triangleState[2]
          << "/"
          << triangleState[3]
          << endl;
    
    n = _edgeLinkVec.size();
    halfEdgeCount = 0;
    for (i = 0; i < n; ++i)
    {
        connectionCount = _edgeLinkVec[i].size();

        halfEdgeCount += connectionCount;
        if (connectionMap.find(connectionCount) == connectionMap.end())
            connectionMap[connectionCount] = 1;
        else
            connectionMap[connectionCount]++;

        if (verbose) 
        {
            HalfEdgeLink::iterator lI;
            for ( lI = _edgeLinkVec[i].begin(); 
                  lI != _edgeLinkVec[i].end(); ++lI )
            {  
              FINFO (( "HEG: HalfEdge %p: %d to %d, twin: %p\n",
                       lI->second,
                       lI->second->vertexStart(),
                       lI->second->vertexEnd(),
                       lI->second->twin));
            }
        }
    }
    for(connectionI = connectionMap.begin();
        connectionI != connectionMap.end(); ++connectionI)
    {
      SINFO << "HEG: Connection: " << connectionI->first << '/' 
            << connectionI->second << ' ' << std::endl;
    }

    SINFO << "HEG: HalfEdgeCount: " << halfEdgeCount << endl;

    return retCode;
}

UInt32 HalfEdgeGraph::calcOptPrim	(	UInt32	iteration = 1,
		bool	doStrip = true,
		bool	doFan = true,
		UInt32	minFanTriangleCount = 16
	)

Definition at line 309 of file OSGHalfEdgeGraph.cpp.

References _edgeLinkVec, _fanBag, _invalidTriangleBag, _stripBag, _trianglePool, _triBag, _validTriangleBag, osg::HalfEdgeGraph::TriangleList::add(), calcStripCost(), osg::HalfEdgeGraph::TriangleList::countElem(), osg::HalfEdgeGraph::TrianglePool::countElem(), DEGREE_0, osg::HalfEdgeGraph::Triangle::drop(), dropOutTriangle(), FAN_PART, FINISH, osg::HalfEdgeGraph::TriangleList::first, osg::HalfEdgeGraph::Triangle::halfEdgeVec, LEFT, osg::HalfEdgeGraph::HalfEdge::next, osg::HalfEdgeGraph::Triangle::next, next(), osg::HalfEdgeGraph::TriangleList::paste(), osg::HalfEdgeGraph::TriangleList::release(), osg::HalfEdgeGraph::Triangle::resetDegreeState(), RIGHT, SINFO, START, osg::HalfEdgeGraph::Triangle::state, STRIP_PART, SWARNING, osg::HalfEdgeGraph::HalfEdge::triangle, osg::HalfEdgeGraph::HalfEdge::twin, and osg::HalfEdgeGraph::Triangle::valid().

Referenced by osg::createOptimizedPrimitives().

{
    Int32 iteration = extIteration;
    bool sample = iteration > 1 ? true : false;
    bool checkRevOrder = sample;
    TriangleList degreeBag[4];
    TriangleList *fList = 0;
    Int32 cost = 0, sampleCost = 0;
    Int32 stripCost = 0, revCost = 0, fanCost = 0, triCost = 0;
    Int32 bestCost = 0, worstCost = 0, lowDegree;
    UInt32 i, n;
    WalkCase walkCase = START;
    Triangle *triangle, *next;
    HalfEdge *twin = 0, *gateEdge = 0, *halfEdge = 0;
    bool doMainLoop = true;
    UInt32 seed = 1, bestSeed = 1;
    Int32 mostDegree = 3;
    UInt32 triangleLeft = _trianglePool.countElem();
    srand(1);

    if(doFan)
    {
        n = _edgeLinkVec.size();
        fanCost = 0;

        // find fans 
        for(i = 0; i < n; ++i)
        {
            if((_edgeLinkVec[i].size() >= minFanTriangles) &&
               (gateEdge = _edgeLinkVec[i][0].second) &&
               (gateEdge->triangle->valid()))
            {
                for(halfEdge = gateEdge->next->next->twin;
                    (halfEdge && halfEdge->triangle->valid() &&
                    (halfEdge != gateEdge));
                    halfEdge = halfEdge->next->next->twin)
                    ;
                if(halfEdge == gateEdge)
                {
                    // fan is closed; mark every triangle          
                    triangle = 0;
                    fList = new TriangleList;
                    for(halfEdge = gateEdge;
                        !triangle || (halfEdge != gateEdge);
                        halfEdge = halfEdge->next->next->twin)
                    {
                        triangle = halfEdge->triangle;
                        _validTriangleBag.release(*triangle);
                        triangle->drop();
                        triangle->state = FAN_PART;
                        fList->add(*triangle);
                    }
                    _fanBag.push_back(Primitive(i,fList));
                    fanCost += (_edgeLinkVec[i].size() + 2);
                    triangleLeft -= _edgeLinkVec[i].size();
                }
            }
        }
    }

    if(doStrip && iteration)
    {
        // push every triangle into the according degree bag
        degreeBag[mostDegree].paste(_validTriangleBag);
        for(triangle = degreeBag[mostDegree].first; triangle; triangle = next)
        {
            next = triangle->next;
            if(triangle->valid())
            {
                if(triangle->state != mostDegree)
                {
                    degreeBag[mostDegree].release(*triangle);
                    _validTriangleBag.release(*triangle);
                    degreeBag[triangle->state].add( *triangle);
                }
            }
            else
            {
                SWARNING << "INVALID TRIANGLE IN VALID TRIANGLE BAG\n" << endl;
            }
        }

        for(iteration--; iteration >= 0; iteration--)
        {
            seed = iteration ? rand() : bestSeed;
            srand (seed);

            fList = 0;
            cost = 0;
            doMainLoop = true;
            walkCase = START;

            // run the main loop
            while(doMainLoop)
            {
                switch(walkCase)
                {
                    case START:
                        stripCost = 0;
                        triangle = 0;

                        for(lowDegree = 1; lowDegree < 4; ++lowDegree)
                        {
                            if((degreeBag[lowDegree].empty() == false))
                            {
                                if(sample)
                                {
                                    // pick a random triangle
                                    n = degreeBag[lowDegree].countElem() - 1;
                                    i = Int32(float(n)*rand()/float(RAND_MAX));
                                    triangle = degreeBag[lowDegree].first;
                                    while (i--) 
                                        triangle = triangle->next;
                                }
                                else
                                {
                                    // pick the first triangle
                                    triangle = degreeBag[lowDegree].first;
                                }
                                break;
                            }
                        }

                        if(triangle)
                        {
                            // create the new list
                            fList = new TriangleList;

                            // find the best neighbour
                            gateEdge = 0;
                            for (i = 0; i < 3; ++i)
                            {
                                if((twin = triangle->halfEdgeVec[i].twin) && 
                                    (twin->triangle->state > 0))
                                {
                                    if(twin->next->next->twin &&
                                       (twin->next->next->twin->triangle->state > 0))
                                    {
                                        gateEdge = &triangle->halfEdgeVec[i];
                                        break;
                                    }
                                    else
                                    {
                                        if(twin->next->twin &&
                                           (twin->next->twin->triangle->state > 0))
                                        {
                                            gateEdge = &triangle->halfEdgeVec[i];
                                        }
                                        else
                                        {
                                            if((twin->triangle->state > 0))
                                                gateEdge = &triangle->halfEdgeVec[i];
                                        }
                                    }
                                }
                            }

                            // release and store the first triangle
                            dropOutTriangle (*triangle,degreeBag);
                            fList->add(*triangle);
                            stripCost += 3;

                            // set the next step
                            if(gateEdge)
                            {
                                walkCase = LEFT;
                                ++stripCost;
                            }
                            else
                            {
                                walkCase = FINISH;
                            }
                        }
                        else
                        {
                            doMainLoop = false;
                        }
                    break;

                    case LEFT:
                        gateEdge = gateEdge->twin;
                        triangle = gateEdge->triangle;

                        // find the next gate
                        if(triangle->state == DEGREE_0)
                        {
                            gateEdge = 0;
                            walkCase = FINISH;
                        }
                        else
                        {
                            if((twin = gateEdge->next->next->twin) && 
                               (twin->triangle->state > 0))
                            {
                                gateEdge = gateEdge->next->next;
                                ++stripCost;
                                walkCase = RIGHT;
                            }
                            else
                            {
                                gateEdge = gateEdge->next;
                                stripCost += 2;
                                walkCase = LEFT;
                            }
                        }
                        // store the current triangle
                        dropOutTriangle (*triangle,degreeBag);
                        fList->add(*triangle);
                    break;

                    case RIGHT:
                        gateEdge = gateEdge->twin;
                        triangle = gateEdge->triangle;

                        // find the next gate
                        if(triangle->state == DEGREE_0)
                        {
                            gateEdge = 0;
                            walkCase = FINISH;
                        }
                        else
                        {
                            if((twin = gateEdge->next->twin) &&
                               (twin->triangle->state > 0))
                            {
                                gateEdge = gateEdge->next;
                                ++stripCost;
                                walkCase = LEFT;
                            }
                            else
                            {
                                gateEdge = gateEdge->next->next;
                                stripCost += 2;
                                walkCase = RIGHT;
                            }
                        }
                        // store the current triangle
                        dropOutTriangle (*triangle,degreeBag);
                        fList->add(*triangle);
                    break;

                    case FINISH:
                        // try to reverse the strip
                        if(checkRevOrder &&
                           (revCost = calcStripCost(*fList,true)) &&
                           (revCost < stripCost))
                        {
                            _stripBag.push_back(Primitive(1,fList));
                            cost += revCost;
                        }
                        else
                        {
                            _stripBag.push_back(Primitive(0,fList));
                            cost += stripCost;
                        }
                        walkCase = START;
                        fList = 0;
                    break;
                }
            }

            if(sample)
            {
                sampleCost = cost + (degreeBag[0].countElem() * 3) + fanCost;
                if(!bestCost || (sampleCost < bestCost))
                {
                    bestCost = sampleCost;
                    bestSeed = seed;
                }
                if(sampleCost > worstCost)
                    worstCost = sampleCost;

                SINFO << " cost/best/worst: " 
                      << sampleCost << '/' << bestCost << '/' << worstCost
                      << endl;
            }

            if(iteration)
            {
                // reinit the four degree bags
                degreeBag[mostDegree].paste(degreeBag[0]);
                n = _stripBag.size();
                for(i = 0; i < n; ++i)
                {
                    degreeBag[mostDegree].paste(*_stripBag[i].second);
                    delete _stripBag[i].second;
                }
                _stripBag.clear();
                for(triangle = degreeBag[mostDegree].first; triangle; 
                    triangle = next)
                {
                    next = triangle->next;
                    triangle->resetDegreeState(STRIP_PART);
                    if (triangle->valid())
                    {
                        if(triangle->state != mostDegree)
                        {
                            degreeBag[mostDegree].release(*triangle);
                            degreeBag[triangle->state].add(*triangle);
                        }
                    }
                    else
                    {
                        SWARNING << "INVALID TRIANGLE IN REINIT\n" << endl;
                        SWARNING << triangle->state << endl;
                    }
                }
            }
        }
    }
    else
    {
        // push every valid triangle in degree 0; we don't strip anything
        degreeBag[0].paste(_validTriangleBag);
    }

    if(sample)
    {
        SWARNING << "range: " 
             << bestCost << '/' << worstCost << ' '
             << float(100 * (worstCost-bestCost))/float(bestCost) << '%'
             << endl;
    }

    // collect isolated triangles  
    degreeBag[0].paste(_invalidTriangleBag);  
    triCost = degreeBag[0].countElem() * 3;
    if(triCost)
    {
        fList = new TriangleList;  
        fList->paste(degreeBag[0]);
        _triBag.push_back(Primitive(0,fList));
    }

    return (cost + fanCost + triCost);
}

UInt32 osg::HalfEdgeGraph::primitiveCount

(

void

)

[inline]

Definition at line 424 of file OSGHalfEdgeGraph.inl.

References _fanBag, _stripBag, and _triBag.

Referenced by osg::createOptimizedPrimitives().

{
    return (_stripBag.size() + _fanBag.size() + _triBag.size());
}

Int32 osg::HalfEdgeGraph::getPrimitive	(	std::vector< IndexT > &	indexVec,
		Int32	type = 0
	)

Referenced by osg::createOptimizedPrimitives().

Int32 osg::HalfEdgeGraph::calcEgdeLines	(	std::vector< IndexT > &	indexVec,
		bool	codeBorder = false
	)

void HalfEdgeGraph::clear

(

void

)

Definition at line 957 of file OSGHalfEdgeGraph.cpp.

References _edgeLinkVec, _fanBag, _stripBag, _trianglePool, _triBag, and osg::HalfEdgeGraph::TrianglePool::clear().

Referenced by ~HalfEdgeGraph().

{
    UInt32 i,n;
    
    _edgeLinkVec.clear();
    _trianglePool.clear();
    
    n = _stripBag.size();
    for(i = 0; i < n; ++i)
        delete _stripBag[i].second;
    _stripBag.clear();
    
    n = _fanBag.size();
    for(i = 0; i < n; ++i)
        delete _fanBag[i].second;
    _fanBag.clear();
    
    n = _triBag.size();
    for(i = 0; i < n; ++i)
        delete _triBag[i].second;
    _triBag.clear();
}

---

Friends And Related Function Documentation

friend class HalfEdge [friend]

Definition at line 76 of file OSGHalfEdgeGraph.h.

friend class Triangle [friend]

Definition at line 79 of file OSGHalfEdgeGraph.h.

friend class TriangleList [friend]

Definition at line 80 of file OSGHalfEdgeGraph.h.

friend class TrianglePool [friend]

Definition at line 81 of file OSGHalfEdgeGraph.h.

friend class TrianglePool::Chunk [friend]

Definition at line 162 of file OSGHalfEdgeGraph.h.

---

Member Data Documentation

std::vector<HalfEdgeLink> osg::HalfEdgeGraph::_edgeLinkVec [private]

Definition at line 166 of file OSGHalfEdgeGraph.h.

Referenced by addHalfEdge(), calcOptPrim(), clear(), getHalfEdge(), reserve(), and verify().

TrianglePool osg::HalfEdgeGraph::_trianglePool [private]

Definition at line 169 of file OSGHalfEdgeGraph.h.

Referenced by addTriangle(), calcOptPrim(), clear(), reserve(), and triangleCount().

TriangleList osg::HalfEdgeGraph::_validTriangleBag [private]

Definition at line 172 of file OSGHalfEdgeGraph.h.

Referenced by addTriangle(), calcOptPrim(), and verify().

TriangleList osg::HalfEdgeGraph::_invalidTriangleBag [private]

Definition at line 173 of file OSGHalfEdgeGraph.h.

Referenced by addTriangle(), calcOptPrim(), and verify().

std::vector<Primitive> osg::HalfEdgeGraph::_stripBag [private]

Definition at line 177 of file OSGHalfEdgeGraph.h.

Referenced by calcOptPrim(), clear(), and primitiveCount().

std::vector<Primitive> osg::HalfEdgeGraph::_fanBag [private]

Definition at line 178 of file OSGHalfEdgeGraph.h.

Referenced by calcOptPrim(), clear(), and primitiveCount().

std::vector<Primitive> osg::HalfEdgeGraph::_triBag [private]

Definition at line 179 of file OSGHalfEdgeGraph.h.

Referenced by calcOptPrim(), clear(), and primitiveCount().

---

The documentation for this class was generated from the following files:

• OSGHalfEdgeGraph.h
• OSGHalfEdgeGraph.cpp
• OSGHalfEdgeGraph.inl