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

   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  *                                                                           *
  16  * This library is free software; you can redistribute it and/or modify it   *
  17  * under the terms of the GNU Library General Public License as published    *
  18  * by the Free Software Foundation, version 2.                               *
  19  *                                                                           *
  20  * This library is distributed in the hope that it will be useful, but       *
  21  * WITHOUT ANY WARRANTY; without even the implied warranty of                *
  22  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU         *
  23  * Library General Public License for more details.                          *
  24  *                                                                           *
  25  * You should have received a copy of the GNU Library General Public         *
  26  * License along with this library; if not, write to the Free Software       *
  27  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.                 *
  28  *                                                                           *
  29  *                                                                           *
  30 \*---------------------------------------------------------------------------*/
  31 /*---------------------------------------------------------------------------*\
  32  *                                Changes                                    *
  33  *                                                                           *
  34  *                                                                           *
  35  *                                                                           *
  36  *                                                                           *
  37  *                                                                           *
  38  *                                                                           *
  39 \*---------------------------------------------------------------------------*/
  40
  41 OSG_BEGIN_NAMESPACE
  42
  43 // HalfEdge
  44
  45 inline
  46 void StriperHalfEdgeGraph::HalfEdge::setVertex(
  47     StriperHalfEdgeGraph::IndexT startVertexIndex,
  48     StriperHalfEdgeGraph::IndexT
  49     OSG_CHECK_ARG(endVertexIndex))
  50 {
  51     _vertexIndex = startVertexIndex;
  52 }
  53
  54 inline
  55 StriperHalfEdgeGraph::IndexT StriperHalfEdgeGraph::HalfEdge::vertexStart(void)
  56 {
  57     return _vertexIndex;
  58 }
  59
  60 inline
  61 StriperHalfEdgeGraph::IndexT StriperHalfEdgeGraph::HalfEdge::vertexEnd(void)
  62 {
  63     return next->_vertexIndex;
  64 }
  65
  66 // Triangle
  67
  68 inline
  69 void StriperHalfEdgeGraph::Triangle::init(void)
  70 {
  71     state = DEGREE_0;
  72     next = prev = 0;
  73     halfEdgeVec[0].next = &(halfEdgeVec[1]);
  74     halfEdgeVec[0].triangle = this;
  75     halfEdgeVec[1].next = &(halfEdgeVec[2]);
  76     halfEdgeVec[1].triangle = this;
  77     halfEdgeVec[2].next = &(halfEdgeVec[0]);
  78     halfEdgeVec[2].triangle = this;
  79 }
  80
  81 inline
  82 bool StriperHalfEdgeGraph::Triangle::valid (void)
  83 {
  84     return (state >= DEGREE_0) ? true : false;
  85 }
  86
  87 inline
  88 void StriperHalfEdgeGraph::Triangle::resetDegreeState(const Int32 type)
  89 {
  90     state = (halfEdgeVec[0].twin &&
  91             (halfEdgeVec[0].twin->triangle->state >= type) ? 1 : 0) +
  92             (halfEdgeVec[1].twin &&
  93             (halfEdgeVec[1].twin->triangle->state >= type) ? 1 : 0) +
  94             (halfEdgeVec[2].twin &&
  95             (halfEdgeVec[2].twin->triangle->state >= type) ? 1 : 0);
  96 }
  97
  98 inline
  99 void StriperHalfEdgeGraph::Triangle::drop(void)
 100 {
 101     if(halfEdgeVec[0].twin && (halfEdgeVec[0].twin->triangle->state > 0))
 102         halfEdgeVec[0].twin->triangle->state--;
 103     if(halfEdgeVec[1].twin && (halfEdgeVec[1].twin->triangle->state > 0))
 104         halfEdgeVec[1].twin->triangle->state--;
 105     if(halfEdgeVec[2].twin && (halfEdgeVec[2].twin->triangle->state > 0))
 106         halfEdgeVec[2].twin->triangle->state--;
 107 }
 108
 109 // TriangleList
 110
 111 inline
 112 StriperHalfEdgeGraph::TriangleList::TriangleList(void)
 113     : first(0), last(0)
 114     {
 115     }
 116
 117 inline
 118 void StriperHalfEdgeGraph::TriangleList::reset(void)
 119 {
 120     first = 0; last = 0;
 121 }
 122
 123 inline
 124 bool StriperHalfEdgeGraph::TriangleList::empty(void)
 125 {
 126     return first ? false : true;
 127 }
 128
 129 inline
 130 UInt32 StriperHalfEdgeGraph::TriangleList::countElem(void)
 131 {
 132     UInt32 count = 0;
 133     for(Triangle *f = first; f; f = f->next)
 134         ++count;
 135     return count;
 136 }
 137
 138 inline
 139 void StriperHalfEdgeGraph::TriangleList::release(Triangle &node)
 140 {
 141     if(node.next)
 142     {
 143         if(node.prev)
 144         {
 145             node.next->prev = node.prev;
 146             node.prev->next = node.next;
 147         }
 148         else
 149         {
 150             node.next->prev = 0;
 151             this->first = node.next;
 152         }
 153     }
 154     else
 155     {
 156         if(node.prev)
 157         {
 158             node.prev->next = 0;
 159             this->last = node.prev;
 160         }
 161         else
 162         {
 163             this->first = 0;
 164             this->last = 0;
 165         }
 166     }
 167     node.next = node.prev = 0;
 168 }
 169
 170 inline
 171 void StriperHalfEdgeGraph::TriangleList::add(Triangle &triangle)
 172 {
 173     if(last)
 174     {
 175         last->next = &triangle;
 176         triangle.prev = last;
 177         last = &triangle;
 178     }
 179     else
 180     {
 181         last = &triangle;
 182         first = &triangle;
 183     }
 184 }
 185
 186 inline
 187 void StriperHalfEdgeGraph::TriangleList::paste(TriangleList &list)
 188 {
 189     if(&list != this)
 190     {
 191         if(empty())
 192         {
 193             first = list.first;
 194             last  = list.last;
 195         }
 196         else
 197         {
 198             if(list.first)
 199             {
 200                 last->next = list.first;
 201                 list.first->prev = last;
 202                 last = list.last;
 203             }
 204         }
 205         list.first = 0;
 206         list.last  = 0;
 207     }
 208 }
 209
 210 // TrianglePool::Chunk
 211
 212 inline
 213 StriperHalfEdgeGraph::TrianglePool::Chunk::Chunk(const UInt32 size)
 214     : _size(size), _freeElem(size), _next(0), _data(0)
 215 {
 216     _data = new Triangle[size];
 217 }
 218
 219 inline
 220 StriperHalfEdgeGraph::TrianglePool::Chunk::~Chunk(void)
 221 {
 222     delete [] _data;
 223     delete _next;
 224 }
 225
 226 inline
 227 UInt32 StriperHalfEdgeGraph::TrianglePool::Chunk::countElem(void)
 228 {
 229     return ((_size - _freeElem) + (_next ? _next->countElem() : 0));
 230 }
 231
 232 // TrianglePool
 233
 234 inline
 235 StriperHalfEdgeGraph::TrianglePool::TrianglePool(UInt32 chunkSize)
 236     : _defaultChunkSize(chunkSize), _first(0), _last(0)
 237 {
 238 }
 239
 240 inline
 241 StriperHalfEdgeGraph::TrianglePool::~TrianglePool(void)
 242 {
 243     clear();
 244 }
 245
 246 inline
 247 StriperHalfEdgeGraph::Triangle *StriperHalfEdgeGraph::TrianglePool::createTriangle(void)
 248 {
 249     if(!_first)
 250     {
 251         _first = _last = new Chunk(_defaultChunkSize);
 252     }
 253     else
 254     {
 255         if(_last->_freeElem == 0)
 256             _last = _last->_next = new Chunk(_defaultChunkSize);
 257     }
 258     return &(_last->_data[_last->_size - _last->_freeElem--]);
 259 }
 260
 261 inline
 262 void StriperHalfEdgeGraph::TrianglePool::clear(void)
 263 {
 264     delete _first;
 265     _first = _last = 0;
 266 }
 267
 268 inline
 269 UInt32 StriperHalfEdgeGraph::TrianglePool::countElem(void)
 270 {
 271     return (_first ? _first->countElem() : 0);
 272 }
 273
 274 inline
 275 void StriperHalfEdgeGraph::TrianglePool::setChunkSize(UInt32 chunkSize)
 276 {
 277     _defaultChunkSize = chunkSize;
 278 }
 279
 280 // HalfEdgeGraph
 281
 282 inline
 283 void StriperHalfEdgeGraph::dropOutTriangle(Triangle &triangle,
 284                                            TriangleList *degreeBag)
 285 {
 286     HalfEdge *twin;
 287     degreeBag[triangle.state].release(triangle);
 288     triangle.state = STRIP_PART;
 289
 290     if((twin = triangle.halfEdgeVec[0].twin) && (twin->triangle->state > 0))
 291     {
 292         degreeBag[twin->triangle->state--].release(*twin->triangle);
 293         degreeBag[twin->triangle->state].add(*twin->triangle);
 294     }
 295
 296     if((twin = triangle.halfEdgeVec[1].twin) && (twin->triangle->state > 0))
 297     {
 298         degreeBag[twin->triangle->state--].release(*twin->triangle);
 299         degreeBag[twin->triangle->state].add(*twin->triangle);
 300     }
 301
 302     if((twin = triangle.halfEdgeVec[2].twin) && (twin->triangle->state > 0))
 303     {
 304         degreeBag[twin->triangle->state--].release(*twin->triangle);
 305         degreeBag[twin->triangle->state].add(*twin->triangle);
 306     }
 307 }
 308
 309 inline
 310 StriperHalfEdgeGraph::HalfEdge *StriperHalfEdgeGraph::getHalfEdge(
 311     UInt32 startVertexIndex,
 312     UInt32 endVertexIndex)
 313 {
 314     UInt32 i, n = UInt32(_edgeLinkVec.size());
 315     const HalfEdgeLink *edgeLink((startVertexIndex < n) ?
 316         &_edgeLinkVec[startVertexIndex] : 0);
 317
 318     HalfEdge *halfEdge = 0;
 319
 320     if (edgeLink && (n = UInt32(edgeLink->size())))
 321     {
 322         for (i = 0; i < n; ++i)
 323         {
 324             if ((*edgeLink)[i].first == endVertexIndex)
 325             {
 326                 halfEdge = (*edgeLink)[i].second;
 327                 break;
 328             }
 329         }
 330     }
 331
 332     return halfEdge;
 333 }
 334
 335 inline
 336 void StriperHalfEdgeGraph::addHalfEdge(HalfEdge &halfEdge,
 337                                        UInt32 startVertexIndex,
 338                                        UInt32 endVertexIndex)
 339 {
 340     UInt32 n = UInt32(_edgeLinkVec.size());
 341     bool     validIndex(startVertexIndex < n);
 342     HalfEdge *twin(validIndex ?
 343         getHalfEdge(endVertexIndex, startVertexIndex) : 0);
 344
 345     halfEdge.setVertex(startVertexIndex,endVertexIndex);
 346
 347     if(validIndex == false)
 348         _edgeLinkVec.resize(startVertexIndex * 2);
 349
 350     _edgeLinkVec[startVertexIndex].
 351         push_back(std::pair<StriperHalfEdgeGraph::IndexT,HalfEdge*>(
 352                       endVertexIndex,
 353                       &halfEdge));
 354
 355     if((halfEdge.twin = twin))
 356     {
 357         twin->twin = &halfEdge;
 358         halfEdge.triangle->state++;
 359         twin->triangle->state++;
 360     }
 361 }
 362
 363 inline
 364 StriperHalfEdgeGraph::HalfEdge *StriperHalfEdgeGraph::findGateEdge(
 365     Triangle *triangleOut,
 366     Triangle *triangleIn)
 367 {
 368     StriperHalfEdgeGraph::HalfEdge *halfEdge = 0;
 369
 370     if(triangleOut && triangleIn)
 371         if(!(halfEdge = triangleOut->halfEdgeVec[0].twin) ||
 372             (halfEdge->triangle != triangleIn))
 373             if(!(halfEdge = triangleOut->halfEdgeVec[1].twin) ||
 374                 (halfEdge->triangle != triangleIn))
 375                 if(!(halfEdge = triangleOut->halfEdgeVec[2].twin) ||
 376                     (halfEdge->triangle != triangleIn))
 377                     halfEdge = 0;
 378
 379     return halfEdge ? halfEdge->twin : 0;
 380 }
 381
 382 inline
 383 bool StriperHalfEdgeGraph::addTriangle(StriperHalfEdgeGraph::IndexT v0,
 384                                        StriperHalfEdgeGraph::IndexT v1,
 385                                        StriperHalfEdgeGraph::IndexT v2)
 386 {
 387     Triangle *triangle = 0;
 388
 389     if ((v0 != v1) && (v0 != v2) && (v2 != v1))
 390     {
 391         // create new triangle
 392         triangle = _trianglePool.createTriangle();
 393         triangle->init();
 394
 395         // reg edges
 396         if (!getHalfEdge(v0,v1) && !getHalfEdge(v1,v2) && !getHalfEdge(v2,v0))
 397         {
 398             addHalfEdge(triangle->halfEdgeVec[0],v0,v1);
 399             addHalfEdge(triangle->halfEdgeVec[1],v1,v2);
 400             addHalfEdge(triangle->halfEdgeVec[2],v2,v0);
 401             _validTriangleBag.add(*triangle);
 402             return true;
 403         }
 404         else
 405         {
 406             triangle->halfEdgeVec[0].setVertex(v0,v1);
 407             triangle->halfEdgeVec[1].setVertex(v1,v2);
 408             triangle->halfEdgeVec[2].setVertex(v2,v0);
 409             triangle->state = INVALID;
 410             _invalidTriangleBag.add(*triangle);
 411             return false;
 412         }
 413     }
 414     return false;
 415 }
 416
 417 inline
 418 UInt32 StriperHalfEdgeGraph::triangleCount(void)
 419 {
 420     return _trianglePool.countElem();
 421 }
 422
 423 inline
 424 UInt32 StriperHalfEdgeGraph::primitiveCount(void)
 425 {
 426     return UInt32(_stripBag.size() + _fanBag.size() + _triBag.size());
 427 }
 428
 429 OSG_END_NAMESPACE