Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages
osg::HalfEdgeGraph

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

typedef std::vector< std::pair<
UInt32, HalfEdge * > > 		HalfEdgeLink
typedef std::pair< IndexT,
TriangleList * > 		Primitive
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 }

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.

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

enum osg::HalfEdgeGraph::WalkCase [private]
 

Enumerator:
START 
LEFT 
RIGHT 
FINISH 

Definition at line 71 of file OSGHalfEdgeGraph.h.

00071 { START, LEFT, RIGHT, FINISH };

Constructor & Destructor Documentation

HalfEdgeGraph::HalfEdgeGraph (  void   ) 
 

Definition at line 70 of file OSGHalfEdgeGraph.cpp.

00071 {
00072 }

HalfEdgeGraph::HalfEdgeGraph (  const HalfEdgeGraph &  obj  ) 
 

Definition at line 81 of file OSGHalfEdgeGraph.cpp.

References SWARNING.

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

HalfEdgeGraph::~HalfEdgeGraph (  void   )  [virtual]
 

Definition at line 93 of file OSGHalfEdgeGraph.cpp.

References clear().

00094 {
00095     clear();
00096 }

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().

00289 {
00290     HalfEdge *twin;
00291     degreeBag[triangle.state].release(triangle);
00292     triangle.state = STRIP_PART;
00293 
00294     if((twin = triangle.halfEdgeVec[0].twin) && (twin->triangle->state > 0))
00295     {
00296         degreeBag[twin->triangle->state--].release(*twin->triangle);
00297         degreeBag[twin->triangle->state].add(*twin->triangle);
00298     }
00299 
00300     if((twin = triangle.halfEdgeVec[1].twin) && (twin->triangle->state > 0))
00301     {
00302         degreeBag[twin->triangle->state--].release(*twin->triangle);
00303         degreeBag[twin->triangle->state].add(*twin->triangle);
00304     }
00305 
00306     if((twin = triangle.halfEdgeVec[2].twin) && (twin->triangle->state > 0))
00307     {
00308         degreeBag[twin->triangle->state--].release(*twin->triangle);
00309         degreeBag[twin->triangle->state].add(*twin->triangle);
00310     }
00311 }

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().

00316 {
00317     UInt32 i, n = _edgeLinkVec.size();
00318     const HalfEdgeLink *edgeLink((startVertexIndex < n) ?
00319         &_edgeLinkVec[startVertexIndex] : 0);
00320 
00321     HalfEdge *halfEdge = 0;
00322 
00323     if (edgeLink && (n = edgeLink->size()))
00324     {
00325         for (i = 0; i < n; ++i)
00326         {
00327             if ((*edgeLink)[i].first == endVertexIndex)
00328             {
00329                 halfEdge = (*edgeLink)[i].second;
00330                 break;
00331             }
00332         }
00333     }
00334 
00335     return halfEdge;
00336 }

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().

00341 {
00342     UInt32 n(_edgeLinkVec.size());
00343     bool     validIndex(startVertexIndex < n);
00344     HalfEdge *twin(validIndex ?
00345         getHalfEdge(endVertexIndex, startVertexIndex) : 0);
00346 
00347     halfEdge.setVertex(startVertexIndex,endVertexIndex);
00348 
00349     if(validIndex == false)
00350         _edgeLinkVec.resize(startVertexIndex * 2);
00351 
00352     _edgeLinkVec[startVertexIndex].
00353         push_back(std::pair<HalfEdgeGraph::IndexT,HalfEdge*>(endVertexIndex,
00354                                                              &halfEdge));
00355 
00356     if((halfEdge.twin = twin))
00357     {
00358         twin->twin = &halfEdge;
00359         halfEdge.triangle->state++;
00360         twin->triangle->state++;
00361     }
00362 }

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().

00367 {
00368     HalfEdgeGraph::HalfEdge *halfEdge = 0;
00369 
00370     if(triangleOut && triangleIn)
00371         if(!(halfEdge = triangleOut->halfEdgeVec[0].twin) || 
00372             (halfEdge->triangle != triangleIn))
00373             if(!(halfEdge = triangleOut->halfEdgeVec[1].twin) || 
00374                 (halfEdge->triangle != triangleIn))
00375                 if(!(halfEdge = triangleOut->halfEdgeVec[2].twin) || 
00376                     (halfEdge->triangle != triangleIn))
00377                     halfEdge = 0;
00378 
00379     return halfEdge ? halfEdge->twin : 0;
00380 }

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().

00656 {
00657     Triangle *triangle = rev ? strip.last : strip.first, *nextTriangle;
00658     HalfEdge /* *firstEdge, */ *halfEdge, *gate;
00659     WalkCase walkCase;
00660     Int32 cost = 0;
00661 
00662     if (triangle)
00663     {
00664         cost = 3;
00665         if ((nextTriangle = rev ? triangle->prev : triangle->next))
00666         {
00667             gate = findGateEdge(triangle,nextTriangle);
00668             //firstEdge = gate->next->next;
00669             ++cost;
00670             walkCase = LEFT;
00671             for(triangle = nextTriangle; 
00672                 (nextTriangle = (rev ? triangle->prev : triangle->next));
00673                 triangle = nextTriangle)
00674             {
00675                 halfEdge = gate->twin;
00676                 gate = findGateEdge(triangle,nextTriangle); 
00677                 if (walkCase == RIGHT)
00678                 {
00679                     // RIGHT
00680                     if(halfEdge->next == gate)
00681                     {
00682                         ++cost;
00683                         walkCase = LEFT;
00684                     }
00685                     else
00686                     {
00687                         // swap; walkCase stays RIGHT;
00688                         cost += 2;
00689                     }
00690                 }
00691                 else
00692                 {
00693                     // LEFT
00694                     if(halfEdge->next->next == gate)
00695                     {
00696                         ++cost;
00697                         walkCase = RIGHT;
00698                     }
00699                     else
00700                     {
00701                         // swap; walkCase stays LEFT;
00702                         cost += 2;
00703                     }
00704                 }
00705             }
00706         }
00707     }
00708 
00709     return cost;
00710 }

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().

00176 {
00177     UInt32 i;
00178 
00179     _trianglePool.setChunkSize(triangleNum);
00180     _edgeLinkVec.resize(vertexNum); 
00181 
00182     if(reserveEdges > 0)
00183     {
00184         for(i = 0; i < vertexNum; ++i)
00185             _edgeLinkVec[i].reserve(reserveEdges);
00186     }
00187 }

bool osg::HalfEdgeGraph::addTriangle (  IndexT  v0,
IndexT  v1,
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().

00386 {
00387     Triangle *triangle = 0;
00388     
00389     if ((v0 != v1) && (v0 != v2) && (v2 != v1))
00390     {
00391         // create new triangle
00392         triangle = _trianglePool.createTriangle();
00393         triangle->init();
00394         
00395         // reg edges
00396         if (!getHalfEdge(v0,v1) && !getHalfEdge(v1,v2) && !getHalfEdge(v2,v0))
00397         {
00398             addHalfEdge(triangle->halfEdgeVec[0],v0,v1);
00399             addHalfEdge(triangle->halfEdgeVec[1],v1,v2);
00400             addHalfEdge(triangle->halfEdgeVec[2],v2,v0);
00401             _validTriangleBag.add(*triangle);
00402             return true;
00403         }
00404         else
00405         {
00406             triangle->halfEdgeVec[0].setVertex(v0,v1);
00407             triangle->halfEdgeVec[1].setVertex(v1,v2);
00408             triangle->halfEdgeVec[2].setVertex(v2,v0);
00409             triangle->state = INVALID;
00410             _invalidTriangleBag.add(*triangle);
00411             return false;
00412         }
00413     }
00414     return false;
00415 }

UInt32 osg::HalfEdgeGraph::triangleCount (  void   )  [inline]
 

Definition at line 418 of file OSGHalfEdgeGraph.inl.

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

00419 {
00420     return _trianglePool.countElem();
00421 }

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::HalfEdge::triangle, and osg::HalfEdgeGraph::HalfEdge::twin.

Referenced by osg::createOptimizedPrimitives().

00197 {
00198     bool retCode = true;
00199     UInt32 i, n;
00200     Triangle *triangle, *nt0, *nt1, *nt2;
00201     Int32 triangleState[4];
00202     Int32 invalidTriangles = 0;
00203     Int32 halfEdgeCount = 0;
00204     map< Int32, Int32 > connectionMap;
00205     map< Int32, Int32 >::iterator connectionI;
00206     Int32 connectionCount;
00207     bool validTri = false;
00208 
00209     for(i = 0; i < 4; ++i)
00210         triangleState[i] = 0;
00211 
00212     for( i = 0, triangle = _validTriangleBag.first; 
00213          triangle; 
00214          i++, triangle = triangle->next)
00215     {
00216         if(triangle->verify() && 
00217            (triangle->state >= 0) || (triangle->state <= 3))
00218         {
00219             triangleState[triangle->state]++;
00220             validTri = true;
00221         }
00222         else
00223         {
00224             ++invalidTriangles;
00225             validTri = false;
00226         }
00227 
00228         if ( verbose ) 
00229         {
00230             nt0 = triangle->halfEdgeVec[0].twin ? 
00231               triangle->halfEdgeVec[0].twin->triangle : 0;
00232             nt1 = triangle->halfEdgeVec[1].twin ? 
00233               triangle->halfEdgeVec[1].twin->triangle : 0;
00234             nt2 = triangle->halfEdgeVec[2].twin ? 
00235               triangle->halfEdgeVec[2].twin->triangle : 0;
00236             
00237             FINFO ( ( "HEG: Triangle %p: %d %d %d, %p %p %p: %s\n",
00238                       triangle, 
00239                       triangle->halfEdgeVec[0].vertexStart(),
00240                       triangle->halfEdgeVec[1].vertexStart(),
00241                       triangle->halfEdgeVec[2].vertexStart(),
00242                       nt0, nt1, nt2,
00243                       (validTri ? "VALID" : "INVALID" ) ) );
00244         }
00245     }
00246 
00247     SINFO << "HEG: linked triangle count " << _validTriangleBag.countElem()
00248           << endl;
00249     SINFO << "HEG: invalid triangle " << invalidTriangles 
00250           << endl;
00251     SINFO << "HEG: nonmanifold split: " << _invalidTriangleBag.countElem() 
00252           << endl;
00253 
00254     SINFO << "HEG: triangle state: "
00255           << triangleState[0]
00256           << "/"
00257           << triangleState[1]
00258           << "/"
00259           << triangleState[2]
00260           << "/"
00261           << triangleState[3]
00262           << endl;
00263     
00264     n = _edgeLinkVec.size();
00265     halfEdgeCount = 0;
00266     for (i = 0; i < n; ++i)
00267     {
00268         connectionCount = _edgeLinkVec[i].size();
00269 
00270         halfEdgeCount += connectionCount;
00271         if (connectionMap.find(connectionCount) == connectionMap.end())
00272             connectionMap[connectionCount] = 1;
00273         else
00274             connectionMap[connectionCount]++;
00275 
00276         if (verbose) 
00277         {
00278             HalfEdgeLink::iterator lI;
00279             for ( lI = _edgeLinkVec[i].begin(); 
00280                   lI != _edgeLinkVec[i].end(); ++lI )
00281             {  
00282               FINFO (( "HEG: HalfEdge %p: %d to %d, twin: %p\n",
00283                        lI->second,
00284                        lI->second->vertexStart(),
00285                        lI->second->vertexEnd(),
00286                        lI->second->twin));
00287             }
00288         }
00289     }
00290     for(connectionI = connectionMap.begin();
00291         connectionI != connectionMap.end(); ++connectionI)
00292     {
00293       SINFO << "HEG: Connection: " << connectionI->first << '/' 
00294             << connectionI->second << ' ' << std::endl;
00295     }
00296 
00297     SINFO << "HEG: HalfEdgeCount: " << halfEdgeCount << endl;
00298 
00299     return retCode;
00300 }

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(), osg::HalfEdgeGraph::TriangleList::empty(), 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().

00312 {
00313     Int32 iteration = extIteration;
00314     bool sample = iteration > 1 ? true : false;
00315     bool checkRevOrder = sample;
00316     TriangleList degreeBag[4];
00317     TriangleList *fList = 0;
00318     Int32 cost = 0, sampleCost = 0;
00319     Int32 stripCost = 0, revCost = 0, fanCost = 0, triCost = 0;
00320     Int32 bestCost = 0, worstCost = 0, lowDegree;
00321     UInt32 i, n;
00322     WalkCase walkCase = START;
00323     Triangle *triangle, *next;
00324     HalfEdge *twin = 0, *gateEdge = 0, *halfEdge = 0;
00325     bool doMainLoop = true;
00326     UInt32 seed = 1, bestSeed = 1;
00327     Int32 mostDegree = 3;
00328     UInt32 triangleLeft = _trianglePool.countElem();
00329     srand(1);
00330 
00331     if(doFan)
00332     {
00333         n = _edgeLinkVec.size();
00334         fanCost = 0;
00335 
00336         // find fans 
00337         for(i = 0; i < n; ++i)
00338         {
00339             if((_edgeLinkVec[i].size() >= minFanTriangles) &&
00340                (gateEdge = _edgeLinkVec[i][0].second) &&
00341                (gateEdge->triangle->valid()))
00342             {
00343                 for(halfEdge = gateEdge->next->next->twin;
00344                     (halfEdge && halfEdge->triangle->valid() &&
00345                     (halfEdge != gateEdge));
00346                     halfEdge = halfEdge->next->next->twin)
00347                     ;
00348                 if(halfEdge == gateEdge)
00349                 {
00350                     // fan is closed; mark every triangle          
00351                     triangle = 0;
00352                     fList = new TriangleList;
00353                     for(halfEdge = gateEdge;
00354                         !triangle || (halfEdge != gateEdge);
00355                         halfEdge = halfEdge->next->next->twin)
00356                     {
00357                         triangle = halfEdge->triangle;
00358                         _validTriangleBag.release(*triangle);
00359                         triangle->drop();
00360                         triangle->state = FAN_PART;
00361                         fList->add(*triangle);
00362                     }
00363                     _fanBag.push_back(Primitive(i,fList));
00364                     fanCost += (_edgeLinkVec[i].size() + 2);
00365                     triangleLeft -= _edgeLinkVec[i].size();
00366                 }
00367             }
00368         }
00369     }
00370 
00371     if(doStrip && iteration)
00372     {
00373         // push every triangle into the according degree bag
00374         degreeBag[mostDegree].paste(_validTriangleBag);
00375         for(triangle = degreeBag[mostDegree].first; triangle; triangle = next)
00376         {
00377             next = triangle->next;
00378             if(triangle->valid())
00379             {
00380                 if(triangle->state != mostDegree)
00381                 {
00382                     degreeBag[mostDegree].release(*triangle);
00383                     _validTriangleBag.release(*triangle);
00384                     degreeBag[triangle->state].add( *triangle);
00385                 }
00386             }
00387             else
00388             {
00389                 SWARNING << "INVALID TRIANGLE IN VALID TRIANGLE BAG\n" << endl;
00390             }
00391         }
00392 
00393         for(iteration--; iteration >= 0; iteration--)
00394         {
00395             seed = iteration ? rand() : bestSeed;
00396             srand (seed);
00397 
00398             fList = 0;
00399             cost = 0;
00400             doMainLoop = true;
00401             walkCase = START;
00402 
00403             // run the main loop
00404             while(doMainLoop)
00405             {
00406                 switch(walkCase)
00407                 {
00408                     case START:
00409                         stripCost = 0;
00410                         triangle = 0;
00411 
00412                         for(lowDegree = 1; lowDegree < 4; ++lowDegree)
00413                         {
00414                             if((degreeBag[lowDegree].empty() == false))
00415                             {
00416                                 if(sample)
00417                                 {
00418                                     // pick a random triangle
00419                                     n = degreeBag[lowDegree].countElem() - 1;
00420                                     i = Int32(float(n)*rand()/float(RAND_MAX));
00421                                     triangle = degreeBag[lowDegree].first;
00422                                     while (i--) 
00423                                         triangle = triangle->next;
00424                                 }
00425                                 else
00426                                 {
00427                                     // pick the first triangle
00428                                     triangle = degreeBag[lowDegree].first;
00429                                 }
00430                                 break;
00431                             }
00432                         }
00433 
00434                         if(triangle)
00435                         {
00436                             // create the new list
00437                             fList = new TriangleList;
00438 
00439                             // find the best neighbour
00440                             gateEdge = 0;
00441                             for (i = 0; i < 3; ++i)
00442                             {
00443                                 if((twin = triangle->halfEdgeVec[i].twin) && 
00444                                     (twin->triangle->state > 0))
00445                                 {
00446                                     if(twin->next->next->twin &&
00447                                        (twin->next->next->twin->triangle->state > 0))
00448                                     {
00449                                         gateEdge = &triangle->halfEdgeVec[i];
00450                                         break;
00451                                     }
00452                                     else
00453                                     {
00454                                         if(twin->next->twin &&
00455                                            (twin->next->twin->triangle->state > 0))
00456                                         {
00457                                             gateEdge = &triangle->halfEdgeVec[i];
00458                                         }
00459                                         else
00460                                         {
00461                                             if((twin->triangle->state > 0))
00462                                                 gateEdge = &triangle->halfEdgeVec[i];
00463                                         }
00464                                     }
00465                                 }
00466                             }
00467 
00468                             // release and store the first triangle
00469                             dropOutTriangle (*triangle,degreeBag);
00470                             fList->add(*triangle);
00471                             stripCost += 3;
00472 
00473                             // set the next step
00474                             if(gateEdge)
00475                             {
00476                                 walkCase = LEFT;
00477                                 ++stripCost;
00478                             }
00479                             else
00480                             {
00481                                 walkCase = FINISH;
00482                             }
00483                         }
00484                         else
00485                         {
00486                             doMainLoop = false;
00487                         }
00488                     break;
00489 
00490                     case LEFT:
00491                         gateEdge = gateEdge->twin;
00492                         triangle = gateEdge->triangle;
00493 
00494                         // find the next gate
00495                         if(triangle->state == DEGREE_0)
00496                         {
00497                             gateEdge = 0;
00498                             walkCase = FINISH;
00499                         }
00500                         else
00501                         {
00502                             if((twin = gateEdge->next->next->twin) && 
00503                                (twin->triangle->state > 0))
00504                             {
00505                                 gateEdge = gateEdge->next->next;
00506                                 ++stripCost;
00507                                 walkCase = RIGHT;
00508                             }
00509                             else
00510                             {
00511                                 gateEdge = gateEdge->next;
00512                                 stripCost += 2;
00513                                 walkCase = LEFT;
00514                             }
00515                         }
00516                         // store the current triangle
00517                         dropOutTriangle (*triangle,degreeBag);
00518                         fList->add(*triangle);
00519                     break;
00520 
00521                     case RIGHT:
00522                         gateEdge = gateEdge->twin;
00523                         triangle = gateEdge->triangle;
00524 
00525                         // find the next gate
00526                         if(triangle->state == DEGREE_0)
00527                         {
00528                             gateEdge = 0;
00529                             walkCase = FINISH;
00530                         }
00531                         else
00532                         {
00533                             if((twin = gateEdge->next->twin) &&
00534                                (twin->triangle->state > 0))
00535                             {
00536                                 gateEdge = gateEdge->next;
00537                                 ++stripCost;
00538                                 walkCase = LEFT;
00539                             }
00540                             else
00541                             {
00542                                 gateEdge = gateEdge->next->next;
00543                                 stripCost += 2;
00544                                 walkCase = RIGHT;
00545                             }
00546                         }
00547                         // store the current triangle
00548                         dropOutTriangle (*triangle,degreeBag);
00549                         fList->add(*triangle);
00550                     break;
00551 
00552                     case FINISH:
00553                         // try to reverse the strip
00554                         if(checkRevOrder &&
00555                            (revCost = calcStripCost(*fList,true)) &&
00556                            (revCost < stripCost))
00557                         {
00558                             _stripBag.push_back(Primitive(1,fList));
00559                             cost += revCost;
00560                         }
00561                         else
00562                         {
00563                             _stripBag.push_back(Primitive(0,fList));
00564                             cost += stripCost;
00565                         }
00566                         walkCase = START;
00567                         fList = 0;
00568                     break;
00569                 }
00570             }
00571 
00572             if(sample)
00573             {
00574                 sampleCost = cost + (degreeBag[0].countElem() * 3) + fanCost;
00575                 if(!bestCost || (sampleCost < bestCost))
00576                 {
00577                     bestCost = sampleCost;
00578                     bestSeed = seed;
00579                 }
00580                 if(sampleCost > worstCost)
00581                     worstCost = sampleCost;
00582 
00583                 SINFO << " cost/best/worst: " 
00584                       << sampleCost << '/' << bestCost << '/' << worstCost
00585                       << endl;
00586             }
00587 
00588             if(iteration)
00589             {
00590                 // reinit the four degree bags
00591                 degreeBag[mostDegree].paste(degreeBag[0]);
00592                 n = _stripBag.size();
00593                 for(i = 0; i < n; ++i)
00594                 {
00595                     degreeBag[mostDegree].paste(*_stripBag[i].second);
00596                     delete _stripBag[i].second;
00597                 }
00598                 _stripBag.clear();
00599                 for(triangle = degreeBag[mostDegree].first; triangle; 
00600                     triangle = next)
00601                 {
00602                     next = triangle->next;
00603                     triangle->resetDegreeState(STRIP_PART);
00604                     if (triangle->valid())
00605                     {
00606                         if(triangle->state != mostDegree)
00607                         {
00608                             degreeBag[mostDegree].release(*triangle);
00609                             degreeBag[triangle->state].add(*triangle);
00610                         }
00611                     }
00612                     else
00613                     {
00614                         SWARNING << "INVALID TRIANGLE IN REINIT\n" << endl;
00615                         SWARNING << triangle->state << endl;
00616                     }
00617                 }
00618             }
00619         }
00620     }
00621     else
00622     {
00623         // push every valid triangle in degree 0; we don't strip anything
00624         degreeBag[0].paste(_validTriangleBag);
00625     }
00626 
00627     if(sample)
00628     {
00629         SWARNING << "range: " 
00630              << bestCost << '/' << worstCost << ' '
00631              << float(100 * (worstCost-bestCost))/float(bestCost) << '%'
00632              << endl;
00633     }
00634 
00635     // collect isolated triangles  
00636     degreeBag[0].paste(_invalidTriangleBag);  
00637     triCost = degreeBag[0].countElem() * 3;
00638     if(triCost)
00639     {
00640         fList = new TriangleList;  
00641         fList->paste(degreeBag[0]);
00642         _triBag.push_back(Primitive(0,fList));
00643     }
00644 
00645     return (cost + fanCost + triCost);
00646 }

UInt32 osg::HalfEdgeGraph::primitiveCount (  void   )  [inline]
 

Definition at line 424 of file OSGHalfEdgeGraph.inl.

References _fanBag, _stripBag, and _triBag.

Referenced by osg::createOptimizedPrimitives().

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

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().

00958 {
00959     UInt32 i,n;
00960     
00961     _edgeLinkVec.clear();
00962     _trianglePool.clear();
00963     
00964     n = _stripBag.size();
00965     for(i = 0; i < n; ++i)
00966         delete _stripBag[i].second;
00967     _stripBag.clear();
00968     
00969     n = _fanBag.size();
00970     for(i = 0; i < n; ++i)
00971         delete _fanBag[i].second;
00972     _fanBag.clear();
00973     
00974     n = _triBag.size();
00975     for(i = 0; i < n; ++i)
00976         delete _triBag[i].second;
00977     _triBag.clear();
00978 }

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