Source/System/NodeCores/Drawables/Geometry/Util/OSGStriperHalfEdgeGraph.h

   1 /*---------------------------------------------------------------------------*\
   2  *                                OpenSG                                     *
   3  *                                                                           *
   4  *                                                                           *
   5  *             Copyright (C) 2000-2002 by the OpenSG Forum                   *
   6  *                                                                           *
   7  *                            www.opensg.org                                 *
   8  *                                                                           *
   9  *   contact: dirk@opensg.org, gerrit.voss@vossg.org, jbehr@zgdv.de          *
  10  *                                                                           *
  11  \*---------------------------------------------------------------------------*/
  12 /*---------------------------------------------------------------------------*\
  13  *                                License                                    *
  14  *                                                                           *
  15  * This library is free software; you can redistribute it and/or modify it   *
  16  * under the terms of the GNU Library General Public License as published    *
  17  * by the Free Software Foundation, version 2.                               *
  18  *                                                                           *
  19  * This library is distributed in the hope that it will be useful, but       *
  20  * WITHOUT ANY WARRANTY; without even the implied warranty of                *
  21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU         *
  22  * Library General Public License for more details.                          *
  23  *                                                                           *
  24  * You should have received a copy of the GNU Library General Public         *
  25  * License along with this library; if not, write to the Free Software       *
  26  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.                 *
  27  *                                                                           *
  28  \*---------------------------------------------------------------------------*/
  29 /*---------------------------------------------------------------------------*\
  30  *                                Changes                                    *
  31  *                                                                           *
  32  *                                                                           *
  33  *                                                                           *
  34  *                                                                           *
  35  *                                                                           *
  36  *                                                                           *
  37  \*---------------------------------------------------------------------------*/
  38
  39 #ifndef _OSGSTRIPERHALFEDGEGRAPH_H_
  40 #define _OSGSTRIPERHALFEDGEGRAPH_H_
  41 #ifdef __sgi
  42 #pragma once
  43 #endif
  44
  45 #include <vector>
  46 #include <iterator>
  47
  48 #include "OSGDrawableDef.h"
  49 #include "OSGBaseTypes.h"
  50 #include "OSGLog.h"
  51
  52 OSG_BEGIN_NAMESPACE
  53
  54 /*! \ingroup GrpDrawablesGeometryUtils
  55     \nohierarchy
  56  */
  57 class OSG_DRAWABLE_DLLMAPPING StriperHalfEdgeGraph
  58 {
  59   public:
  60
  61     typedef UInt32 IndexT;
  62
  63   private:
  64
  65     enum TriangleState
  66     {
  67         INVALID    = -30,
  68         FAN_PART   = -20,
  69         STRIP_PART = -10,
  70         DEGREE_0   =   0,
  71         DEGREE_1   =   1,
  72         DEGREE_2   =   2,
  73         DEGREE_3   =   3
  74     };
  75
  76     enum WalkCase { START, LEFT, RIGHT, FINISH };
  77
  78     class HalfEdge;
  79     class Triangle;
  80     class TriangleList;
  81     class TrianglePool;
  82
  83     friend class HalfEdge;
  84     friend class Triangle;
  85     friend class TriangleList;
  86     friend class TrianglePool;
  87
  88     /*! \nohierarchy
  89      */
  90     class HalfEdge
  91     {
  92         IndexT _vertexIndex;
  93
  94       public:
  95
  96         Triangle *triangle;
  97         HalfEdge *twin;
  98         HalfEdge *next;
  99
 100         inline void     setVertex(IndexT startVertexIndex,
 101                                   IndexT endVertexIndex);
 102         inline IndexT   vertexStart(void);
 103         inline IndexT   vertexEnd(void);
 104     };
 105
 106     /*! \nohierarchy
 107      */
 108     class Triangle
 109     {
 110       public:
 111
 112         Int32 state;
 113         Triangle *next;
 114         Triangle *prev;
 115         HalfEdge halfEdgeVec[3];
 116
 117         inline void init(void);
 118         inline bool valid (void);
 119         inline void resetDegreeState (const Int32 type);
 120         inline void drop(void);
 121         bool verify (void);
 122     };
 123
 124     /*! \nohierarchy
 125      */
 126     class TriangleList
 127     {
 128
 129       public:
 130
 131         Triangle *first;
 132         Triangle *last;
 133
 134         inline TriangleList(void);
 135
 136         inline void     reset(void);
 137         inline bool     empty(void);
 138         inline UInt32 countElem(void);
 139
 140         inline void     release(Triangle &node);
 141         inline void     add (Triangle &triangle);
 142         inline void     paste (TriangleList &list);
 143     };
 144
 145     void dropOutTriangle(Triangle &triangle,
 146                          TriangleList *degreeBag);
 147
 148     /*! \nohierarchy
 149      */
 150     class TrianglePool
 151     {
 152       public:
 153
 154         class Chunk;
 155
 156         inline TrianglePool (UInt32 chunkSize = DEFAULT_CHUNK_SIZE);
 157         inline ~TrianglePool(void);
 158
 159         inline Triangle *createTriangle(void);
 160         inline void clear(void);
 161         inline UInt32 countElem (void);
 162         inline void setChunkSize(UInt32 chunkSize = DEFAULT_CHUNK_SIZE);
 163
 164       private:
 165
 166         enum { DEFAULT_CHUNK_SIZE = 2048 };
 167
 168         UInt32 _defaultChunkSize;
 169         Chunk *_first;
 170         Chunk *_last;
 171
 172         TrianglePool(const TrianglePool &other);
 173         void operator =(const TrianglePool &rhs);
 174     };
 175
 176     friend class TrianglePool::Chunk;
 177
 178     // temporary vector data structure
 179     typedef std::vector < std::pair<UInt32,HalfEdge *> > HalfEdgeLink;
 180     std::vector<HalfEdgeLink> _edgeLinkVec;
 181
 182     // Triangle Data Pool
 183     TrianglePool _trianglePool;
 184
 185     // Input
 186     TriangleList _validTriangleBag;
 187     TriangleList _invalidTriangleBag;
 188
 189     // Output
 190     typedef std::pair<IndexT,TriangleList*> Primitive;
 191     std::vector<Primitive> _stripBag;
 192     std::vector<Primitive> _fanBag;
 193     std::vector<Primitive> _triBag;
 194
 195   protected:
 196
 197     inline HalfEdge *getHalfEdge(UInt32 startVertexIndex,
 198                                  UInt32 endVertexIndex);
 199     inline void     addHalfEdge(HalfEdge &halfEdge, UInt32 startVertexIndex,
 200                                 UInt32 endVertexIndex);
 201     inline HalfEdge *findGateEdge(Triangle *triangleOut,
 202                                   Triangle *triangleIn);
 203
 204     Int32 calcStripCost     (TriangleList &strip, bool reverse);
 205     Int32 fillIndexFromFan  (std::vector<IndexT> &indexVec,
 206                              HalfEdge &firstEdge);
 207     Int32 fillIndexFromStrip(std::vector<IndexT> &indexVec,
 208                              TriangleList &strip,
 209                              bool reverse );
 210
 211  public:
 212
 213     StriperHalfEdgeGraph(void);
 214
 215     StriperHalfEdgeGraph(const StriperHalfEdgeGraph &obj);
 216
 217     virtual ~StriperHalfEdgeGraph (void);
 218
 219     void reserve(UInt32 vertexNum, UInt32 triangleNum,
 220                  UInt32 reserveEdges = 8 );
 221
 222     inline bool     addTriangle(IndexT v0, IndexT v1, IndexT v2);
 223     inline UInt32 triangleCount(void);
 224
 225     bool verify (bool verbose = false);
 226
 227     UInt32 calcOptPrim(UInt32 iteration = 1, bool doStrip = true,
 228                        bool doFan = true, UInt32 minFanTriangleCount = 16);
 229
 230     inline UInt32 primitiveCount(void);
 231
 232     Int32 getPrimitive(std::vector<IndexT> & indexVec, Int32 type = 0);
 233     Int32 calcEgdeLines(std::vector<IndexT> & indexVec, bool codeBorder = false);
 234
 235     void clear(void);
 236
 237 };
 238
 239 /*! \ingroup GrpDrawablesGeometryUtils
 240     \nohierarchy
 241  */
 242
 243 class StriperHalfEdgeGraph::TrianglePool::Chunk
 244 {
 245   public:
 246     const UInt32 _size;
 247     UInt32 _freeElem;
 248     Chunk *_next;
 249     Triangle *_data;
 250
 251     inline Chunk (const UInt32 size);
 252     inline ~Chunk (void);
 253     inline UInt32 countElem(void);
 254
 255   private:
 256
 257     Chunk(const Chunk &other);
 258     void operator =(const Chunk &rhs);
 259 };
 260
 261 /*! \ingroup GrpDrawablesGeometryUtils
 262  */
 263
 264 typedef StriperHalfEdgeGraph* StriperHalfEdgeGraphP;
 265
 266 OSG_END_NAMESPACE
 267
 268 #include "OSGStriperHalfEdgeGraph.inl"
 269
 270 #endif // _OSGSTRIPERHALFEDGEGRAPH_H_