OpenSG: OSGNodeGraph.h Source File

00001 /*---------------------------------------------------------------------------*\
00002  *                                OpenSG                                     *
00003  *                                                                           *
00004  *                                                                           *
00005  *             Copyright (C) 2000-2002 by the OpenSG Forum                   *
00006  *                                                                           *
00007  *                            www.opensg.org                                 *
00008  *                                                                           *
00009  *   contact: dirk@opensg.org, gerrit.voss@vossg.org, jbehr@zgdv.de          *
00010  *                                                                           *
00011 \*---------------------------------------------------------------------------*/
00012 /*---------------------------------------------------------------------------*\
00013  *                                License                                    *
00014  *                                                                           *
00015  * This library is free software; you can redistribute it and/or modify it   *
00016  * under the terms of the GNU Library General Public License as published    *
00017  * by the Free Software Foundation, version 2.                               *
00018  *                                                                           *
00019  * This library is distributed in the hope that it will be useful, but       *
00020  * WITHOUT ANY WARRANTY; without even the implied warranty of                *
00021  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU         *
00022  * Library General Public License for more details.                          *
00023  *                                                                           *
00024  * You should have received a copy of the GNU Library General Public         *
00025  * License along with this library; if not, write to the Free Software       *
00026  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.                 *
00027  *                                                                           *
00028 \*---------------------------------------------------------------------------*/
00029 /*---------------------------------------------------------------------------*\
00030  *                                Changes                                    *
00031  *                                                                           *
00032  *                                                                           *
00033  *                                                                           *
00034  *                                                                           *
00035  *                                                                           *
00036  *                                                                           *
00037 \*---------------------------------------------------------------------------*/
00038 
00039 
00040 #ifndef _OSGNODEGRAPH_H_
00041 #define _OSGNODEGRAPH_H_
00042 #ifdef __sgi
00043 #pragma once
00044 #endif
00045 
00046 #include <list>
00047 #include <vector>
00048 #include <map>
00049 #include <iterator>
00050 
00051 #include <OSGConfig.h>
00052 #include <OSGLog.h>
00053 
00054 OSG_BEGIN_NAMESPACE
00055 
00056 
00057 #if !defined(OSG_DO_DOC) || defined(OSG_DOC_DEV)
00058 
00059 class NodeGraph
00060 {
00061     /*==========================  PRIVATE  ================================*/
00062   private:
00063 
00064     enum WalkCase { START = -2, NEW = -1, LEFT = 0, RIGHT = 1, FINISH = 10 };
00065 
00066     class Edge;
00067     friend class Edge;
00068 
00069     class NodeList;
00070     friend class NodeList;
00071 
00072     class Node;
00073     friend class Node;
00074 
00075     class Edge
00076     {
00077         /*========================  PUBLIC  ===============================*/
00078       public:
00079         int     vertexStart;
00080         int     vertexEnd;
00081         Node   *node;
00082         Edge   *brotherEdge;
00083         int     edgeSide;
00084         
00085         /*-----------------------------------------------------------------*/
00089         Edge (void) {;}
00090         Edge (int vS, int vE, Node &n, int eS)
00091             : vertexStart(vS), vertexEnd(vE), node(&n), 
00092               brotherEdge(0), edgeSide(eS) {;}
00094         /*-----------------------------------------------------------------*/
00098         inline void set (int vS, int vE, Node &n, int eS) 
00099         {
00100             vertexStart = vS; vertexEnd = vE; node = &n; edgeSide = eS;
00101             brotherEdge = 0;
00102         }
00104     };
00105 
00106     class NodeList
00107     {
00108         friend class Node;
00109         
00110         int           _degree;
00111         Node         *_first;
00112         Node         *_last;
00113         int           _size;
00114         NodeList     *_down;
00115         
00116         /*========================  PUBLIC  ===============================*/
00117       public:
00118         /*-----------------------------------------------------------------*/
00122         NodeList (void)
00123             : _degree(0), _first(0), _last(0), _size(0), _down(0) {;}
00124       
00126         /*-----------------------------------------------------------------*/
00130         inline int          size        (void)           { return _size; }
00131         inline bool         empty       (void)           { return _size ? 
00132                                                            false : true; }
00133         inline NodeList    *down        (void)           { return _down; }
00134         inline void         setDown     (NodeList *down) { _down = down; }
00135         inline int          degree      (void)           { return _degree; }
00136         inline void         setDegree   (int degree)     { _degree = degree; }
00137         inline Node        *first       (void)           { return _first; }
00138         inline Node        *last        (void)           { return _last; }
00139         
00140         inline void push_back (Node &node)
00141         {
00142             node.release();
00143             if (_last) 
00144             {
00145                 _last->next = &node;
00146                 node.prev = _last;
00147                 _last = &node;
00148             }
00149             else 
00150             {
00151                 _last = &node;
00152                 _first = &node;
00153             }
00154             _size++;
00155             node.list = this;
00156         }
00157         void push_front (Node &node)
00158         {
00159             node.release();
00160             if (_first)
00161             {
00162                 _first->prev = &node;
00163                 node.next = _first;
00164                 _first = &node;
00165             }
00166             else
00167             {
00168                 _last = &node;
00169                 _first = &node;
00170             }
00171             _size++;
00172             node.list = this;
00173         }
00174         inline void add (Node &node, bool back)
00175             { back ? push_back(node) : push_front(node); }
00177     };
00178 
00179     class Node 
00180     {
00181         /*========================  PUBLIC  ===============================*/
00182       public:
00183         int       index;      
00184         int       degree;     
00185         Node     *next;
00186         Node     *prev;
00187         NodeList *list;
00188         Edge     *edgeVec[3];
00189         int       vertex[3];  
00190         
00191         /*-----------------------------------------------------------------*/
00195         Node(void) : index(-1), degree(0), next(0), prev(0), list(0)
00196         {
00197             vertex[0] = vertex[1] = vertex[2] = 0;
00198             edgeVec[0] = edgeVec[1] = edgeVec[2] = 0;
00199         }
00201         /*-----------------------------------------------------------------*/
00206         inline void init (int i, int d, int v0, int v1, int v2)
00207         {
00208             index = i;
00209             degree = d;
00210             vertex[0] = v0;
00211             vertex[1] = v1;
00212             vertex[2] = v2;
00213         }
00214         
00216         /*-----------------------------------------------------------------*/
00220         inline void release(void)
00221         {
00222             if (list)
00223             {
00224                 if (next)
00225                 {
00226                     if (prev)
00227                     {
00228                         next->prev = prev;
00229                         prev->next = next;
00230                     }
00231                     else
00232                     {
00233                         next->prev = 0;
00234                         list->_first = next;
00235                     }
00236                 }
00237                 else
00238                 {
00239                     if (prev)
00240                     {
00241                         prev->next = 0;
00242                         list->_last = prev;
00243                     }
00244                     else
00245                     {
00246                         list->_first = 0;
00247                         list->_last = 0;
00248                     }
00249                 }
00250                 list->_size--;
00251                 next = prev = 0;
00252                 list = 0;
00253             }
00254         }
00255         inline void drop (bool back)
00256         {
00257             if (list && list->_down)
00258                 list->_down->add(*this,back);
00259         }
00260         inline void dropNeighbors (bool back)
00261         {
00262             int i;
00263             Edge *edge;
00264             for (i = 0; i < 3; i++)
00265                 if ((edge = edgeVec[i]->brotherEdge))
00266                     edge->node->drop(back);
00267         };
00269     };
00270 
00271     typedef std::vector<Edge *> EdgeMap;
00272 
00273     std::vector<Node> _nodeVec;
00274     std::vector<EdgeMap> _edgeMapVec;
00275     
00276     /*=========================  PROTECTED  ===============================*/
00277   protected:
00278 
00279     /*---------------------------------------------------------------------*/
00283     inline Edge * getEdge (int vS, int vE)
00284     {
00285         EdgeMap &edgeMap = _edgeMapVec[vS];
00286         EdgeMap::iterator eI;
00287         Edge *edge = 0;
00288 
00289         for (eI = edgeMap.begin(); eI != edgeMap.end(); eI++)
00290             if ((*eI)->vertexEnd == vE)
00291             {
00292                 edge = *eI;
00293                 break;
00294             }
00295 
00296         return edge;
00297     }
00298 
00299     inline Edge & addEdge (int vS, int vE, Node &node, int eS )
00300     {
00301         Edge *edge = new Edge (vS,vE,node,eS);
00302         Edge *brotherEdge = getEdge(vE, vS);
00303 
00304         _edgeMapVec[vS].push_back(edge);
00305 
00306         if (brotherEdge)
00307         {
00308             edge->brotherEdge = brotherEdge;
00309             edge->node->degree++;
00310             brotherEdge->brotherEdge = edge;
00311             brotherEdge->node->degree++;
00312         }
00313         return *edge;
00314      }
00315      
00317     /*==========================  PUBLIC  =================================*/
00318   public:
00319 
00320     /*---------------------------------------------------------------------*/
00324     NodeGraph (void);
00325     NodeGraph (const NodeGraph &obj);
00326     
00328     /*---------------------------------------------------------------------*/
00332     virtual ~NodeGraph (void);
00333     
00335     /*---------------------------------------------------------------------*/
00338     void init(int vertexNum, int nodeNum, int reserveEdges );
00339 
00340     inline
00341     bool setNode (int index, int v0, int v1, int v2)
00342     {
00343         if (v0 != v1 && v1 != v2 && v2 != v0)
00344         {
00345             if (!getEdge(v0,v1) && !getEdge(v1,v2) && !getEdge(v2,v0))
00346             {                
00347                 _nodeVec[index].init(index,0,v0,v1,v2);
00348                 _nodeVec[index].edgeVec[0] = &addEdge(v0,v1,_nodeVec[index],0);
00349                 _nodeVec[index].edgeVec[1] = &addEdge(v1,v2,_nodeVec[index],1);
00350                 _nodeVec[index].edgeVec[2] = &addEdge(v2,v0,_nodeVec[index],2);
00351             }
00352             else 
00353             {
00354                 _nodeVec[index].init(index,-1,v0,v1,v2);
00355             }
00356             return true;
00357         }
00358         else
00359         {
00360             return false;
00361         }
00362     }
00365     bool verify (bool printNotice = false );
00366 
00367     class Path
00368     {
00369         /*========================  PUBLIC  ===============================*/
00370       public:
00371         int            type;
00372         bool           flip;
00373         std::list<int> path;
00374         
00375         /*-----------------------------------------------------------------*/
00379         inline Path(void)
00380             : type(0), flip(false) {;}
00381         inline Path(const Path &obj)
00382             : type(obj.type),flip(obj.flip),path(obj.path) {;}
00383 
00385         /*-----------------------------------------------------------------*/
00389         inline void add( int elem)
00390             { flip ? path.push_front(elem) : path.push_back(elem); }
00391         inline void clear (void)
00392             { path.clear(); flip = false; type = 0;}
00393         inline void operator= (const Path &obj)
00394             { type = obj.type; flip = obj.flip; path = obj.path; }
00396     };
00397 
00398     /*---------------------------------------------------------------------*/
00402     int createPathVec (std::vector<Path> &stripVec,
00403                        bool createStrips = true, bool createFans = true,
00404                        int minFanEdgeCount = 8);
00405     
00408     class IndexEdge
00409     {
00410         /*========================  PUBLIC  ===============================*/        
00411       public:
00412         int v1;
00413         int v2;
00414         
00415         /*-----------------------------------------------------------------*/
00419         IndexEdge  ( void) : v1(0), v2(0) {;}
00420         IndexEdge  ( int iv1, int iv2) : v1(iv1), v2(iv2) {;}
00421         IndexEdge  ( const IndexEdge &obj) : v1(obj.v1), v2(obj.v2) {;}
00422         
00424         /*-----------------------------------------------------------------*/
00428         ~IndexEdge ( void) {;}
00429         
00431     };
00432 
00433     /*---------------------------------------------------------------------*/
00437     int getPrimitive  (     Path               &path, 
00438                        std::vector <int      > &primitive );        
00439     int getEdges      (std::list   <IndexEdge> &edgeList  );
00440     int getStartOfEdge(     int                 index, 
00441                             int                 side      )
00442     { 
00443         return _nodeVec[index].edgeVec[side]->vertexStart; 
00444     }
00445     int getEndOfEdge  (     int                 index, 
00446                             int                 side      )
00447     {
00448         return _nodeVec[index].edgeVec[side]->vertexEnd; 
00449     }
00450     
00453     void clear        (void                               );
00454 };
00455 
00456 typedef NodeGraph* NodeGraphP;
00457 
00458 #endif  // remove from all but dev docs
00459 
00460 OSG_END_NAMESPACE
00461 
00462 #endif // _OSGNODEGRAPH_H_