1 /*---------------------------------------------------------------------------*\
5 * Copyright(C) 2000-2002 by the OpenSG Forum *
9 * contact: dirk@opensg.org, gerrit.voss@vossg.org, jbehr@zgdv.de *
11 \*---------------------------------------------------------------------------*/
12 /*---------------------------------------------------------------------------*\
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. *
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. *
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. *
30 \*---------------------------------------------------------------------------*/
31 /*---------------------------------------------------------------------------*\
39 \*---------------------------------------------------------------------------*/
46 void StriperHalfEdgeGraph::HalfEdge::setVertex(
47 StriperHalfEdgeGraph::IndexT startVertexIndex,
48 StriperHalfEdgeGraph::IndexT
49 OSG_CHECK_ARG(endVertexIndex))
51 _vertexIndex = startVertexIndex;
55 StriperHalfEdgeGraph::IndexT StriperHalfEdgeGraph::HalfEdge::vertexStart(void)
61 StriperHalfEdgeGraph::IndexT StriperHalfEdgeGraph::HalfEdge::vertexEnd(void)
63 return next->_vertexIndex;
69 void StriperHalfEdgeGraph::Triangle::init(void)
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;
82 bool StriperHalfEdgeGraph::Triangle::valid (void)
84 return (state >= DEGREE_0) ? true : false;
88 void StriperHalfEdgeGraph::Triangle::resetDegreeState(const Int32 type)
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);
99 void StriperHalfEdgeGraph::Triangle::drop(void)
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--;
112 StriperHalfEdgeGraph::TriangleList::TriangleList(void)
118 void StriperHalfEdgeGraph::TriangleList::reset(void)
124 bool StriperHalfEdgeGraph::TriangleList::empty(void)
126 return first ? false : true;
130 UInt32 StriperHalfEdgeGraph::TriangleList::countElem(void)
133 for(Triangle *f = first; f; f = f->next)
139 void StriperHalfEdgeGraph::TriangleList::release(Triangle &node)
145 node.next->prev = node.prev;
146 node.prev->next = node.next;
151 this->first = node.next;
159 this->last = node.prev;
167 node.next = node.prev = 0;
171 void StriperHalfEdgeGraph::TriangleList::add(Triangle &triangle)
175 last->next = ▵
176 triangle.prev = last;
187 void StriperHalfEdgeGraph::TriangleList::paste(TriangleList &list)
200 last->next = list.first;
201 list.first->prev = last;
210 // TrianglePool::Chunk
213 StriperHalfEdgeGraph::TrianglePool::Chunk::Chunk(const UInt32 size)
214 : _size(size), _freeElem(size), _next(0), _data(0)
216 _data = new Triangle[size];
220 StriperHalfEdgeGraph::TrianglePool::Chunk::~Chunk(void)
227 UInt32 StriperHalfEdgeGraph::TrianglePool::Chunk::countElem(void)
229 return ((_size - _freeElem) + (_next ? _next->countElem() : 0));
235 StriperHalfEdgeGraph::TrianglePool::TrianglePool(UInt32 chunkSize)
236 : _defaultChunkSize(chunkSize), _first(0), _last(0)
241 StriperHalfEdgeGraph::TrianglePool::~TrianglePool(void)
247 StriperHalfEdgeGraph::Triangle *StriperHalfEdgeGraph::TrianglePool::createTriangle(void)
251 _first = _last = new Chunk(_defaultChunkSize);
255 if(_last->_freeElem == 0)
256 _last = _last->_next = new Chunk(_defaultChunkSize);
258 return &(_last->_data[_last->_size - _last->_freeElem--]);
262 void StriperHalfEdgeGraph::TrianglePool::clear(void)
269 UInt32 StriperHalfEdgeGraph::TrianglePool::countElem(void)
271 return (_first ? _first->countElem() : 0);
275 void StriperHalfEdgeGraph::TrianglePool::setChunkSize(UInt32 chunkSize)
277 _defaultChunkSize = chunkSize;
283 void StriperHalfEdgeGraph::dropOutTriangle(Triangle &triangle,
284 TriangleList *degreeBag)
287 degreeBag[triangle.state].release(triangle);
288 triangle.state = STRIP_PART;
290 if((twin = triangle.halfEdgeVec[0].twin) && (twin->triangle->state > 0))
292 degreeBag[twin->triangle->state--].release(*twin->triangle);
293 degreeBag[twin->triangle->state].add(*twin->triangle);
296 if((twin = triangle.halfEdgeVec[1].twin) && (twin->triangle->state > 0))
298 degreeBag[twin->triangle->state--].release(*twin->triangle);
299 degreeBag[twin->triangle->state].add(*twin->triangle);
302 if((twin = triangle.halfEdgeVec[2].twin) && (twin->triangle->state > 0))
304 degreeBag[twin->triangle->state--].release(*twin->triangle);
305 degreeBag[twin->triangle->state].add(*twin->triangle);
310 StriperHalfEdgeGraph::HalfEdge *StriperHalfEdgeGraph::getHalfEdge(
311 UInt32 startVertexIndex,
312 UInt32 endVertexIndex)
314 UInt32 i, n = UInt32(_edgeLinkVec.size());
315 const HalfEdgeLink *edgeLink((startVertexIndex < n) ?
316 &_edgeLinkVec[startVertexIndex] : 0);
318 HalfEdge *halfEdge = 0;
320 if (edgeLink && (n = UInt32(edgeLink->size())))
322 for (i = 0; i < n; ++i)
324 if ((*edgeLink)[i].first == endVertexIndex)
326 halfEdge = (*edgeLink)[i].second;
336 void StriperHalfEdgeGraph::addHalfEdge(HalfEdge &halfEdge,
337 UInt32 startVertexIndex,
338 UInt32 endVertexIndex)
340 UInt32 n = UInt32(_edgeLinkVec.size());
341 bool validIndex(startVertexIndex < n);
342 HalfEdge *twin(validIndex ?
343 getHalfEdge(endVertexIndex, startVertexIndex) : 0);
345 halfEdge.setVertex(startVertexIndex,endVertexIndex);
347 if(validIndex == false)
348 _edgeLinkVec.resize(startVertexIndex * 2);
350 _edgeLinkVec[startVertexIndex].
351 push_back(std::pair<StriperHalfEdgeGraph::IndexT,HalfEdge*>(
355 if((halfEdge.twin = twin))
357 twin->twin = &halfEdge;
358 halfEdge.triangle->state++;
359 twin->triangle->state++;
364 StriperHalfEdgeGraph::HalfEdge *StriperHalfEdgeGraph::findGateEdge(
365 Triangle *triangleOut,
366 Triangle *triangleIn)
368 StriperHalfEdgeGraph::HalfEdge *halfEdge = 0;
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))
379 return halfEdge ? halfEdge->twin : 0;
383 bool StriperHalfEdgeGraph::addTriangle(StriperHalfEdgeGraph::IndexT v0,
384 StriperHalfEdgeGraph::IndexT v1,
385 StriperHalfEdgeGraph::IndexT v2)
387 Triangle *triangle = 0;
389 if ((v0 != v1) && (v0 != v2) && (v2 != v1))
391 // create new triangle
392 triangle = _trianglePool.createTriangle();
396 if (!getHalfEdge(v0,v1) && !getHalfEdge(v1,v2) && !getHalfEdge(v2,v0))
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);
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);
418 UInt32 StriperHalfEdgeGraph::triangleCount(void)
420 return _trianglePool.countElem();
424 UInt32 StriperHalfEdgeGraph::primitiveCount(void)
426 return UInt32(_stripBag.size() + _fanBag.size() + _triBag.size());