root/OpenSceneGraph/trunk/src/osgUtil/EdgeCollector.cpp @ 13041

Revision 13041, 13.7 kB (checked in by robert, 2 years ago)

Ran script to remove trailing spaces and tabs

  • Property svn:eol-style set to native
Line 
1/* -*-c++-*- OpenSceneGraph - Copyright (C) 1998-2006 Robert Osfield
2 *
3 * This library is open source and may be redistributed and/or modified under
4 * the terms of the OpenSceneGraph Public License (OSGPL) version 0.0 or
5 * (at your option) any later version.  The full license is in LICENSE file
6 * included with this distribution, and on the openscenegraph.org website.
7 *
8 * This library is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11 * OpenSceneGraph Public License for more details.
12*/
13
14#include <osgUtil/EdgeCollector>
15#include <osgUtil/ConvertVec>
16
17#include <osg/TriangleIndexFunctor>
18
19namespace osgUtil
20{
21
22bool EdgeCollector::Point::isBoundaryPoint() const
23{
24    if (_protected) return true;
25
26    for(TriangleSet::const_iterator itr=_triangles.begin();
27        itr!=_triangles.end();
28        ++itr)
29    {
30        const Triangle* triangle = itr->get();
31        if ((triangle->_e1->_p1==this || triangle->_e1->_p2==this) && triangle->_e1->isBoundaryEdge()) return true;
32        if ((triangle->_e2->_p1==this || triangle->_e2->_p2==this) && triangle->_e2->isBoundaryEdge()) return true;
33        if ((triangle->_e3->_p1==this || triangle->_e3->_p2==this) && triangle->_e3->isBoundaryEdge()) return true;
34
35        //if ((*itr)->isBoundaryTriangle()) return true;
36    }
37    return false;
38}
39
40void EdgeCollector::Edge::clear()
41{
42    _p1 = 0;
43    _p2 = 0;
44    _op1 = 0;
45    _op2 = 0;
46    _triangles.clear();
47}
48
49
50
51bool EdgeCollector::Edge::operator < ( const Edge& rhs) const
52{
53    if (dereference_check_less(_p1,rhs._p1)) return true;
54    if (dereference_check_less(rhs._p1,_p1)) return false;
55
56    return dereference_check_less(_p2,rhs._p2);
57}
58
59bool EdgeCollector::Edge::operator == ( const Edge& rhs) const
60{
61    if (&rhs==this) return true;
62    if (*this<rhs) return false;
63    if (rhs<*this) return false;
64    return true;
65}
66
67bool EdgeCollector::Edge::operator != ( const Edge& rhs) const
68{
69    if (&rhs==this) return false;
70    if (*this<rhs) return true;
71    if (rhs<*this) return true;
72    return false;
73}
74
75void EdgeCollector::Edge::setOrderedPoints(Point* p1, Point* p2)
76{
77    if (dereference_check_less(p1, p2))
78    {
79        _p1 = _op1 = p1;
80        _p2 = _op2 = p2;
81    }
82    else
83    {
84        _p1 = _op2 = p2;
85        _p2 = _op1 = p1;
86    }
87}
88
89void EdgeCollector::Triangle::clear()
90{
91    _p1 = 0;
92    _p2 = 0;
93    _p3 = 0;
94
95    _op1 = 0;
96    _op2 = 0;
97    _op3 = 0;
98
99    _e1 = 0;
100    _e2 = 0;
101    _e3 = 0;
102}
103
104bool EdgeCollector::Triangle::operator < (const Triangle& rhs) const
105{
106    if (dereference_check_less(_p1,rhs._p1)) return true;
107    if (dereference_check_less(rhs._p1,_p1)) return false;
108
109
110    const Point* lhs_lower = dereference_check_less(_p2,_p3) ? _p2.get() : _p3.get();
111    const Point* rhs_lower = dereference_check_less(rhs._p2,rhs._p3) ? rhs._p2.get() : rhs._p3.get();
112
113    if (dereference_check_less(lhs_lower,rhs_lower)) return true;
114    if (dereference_check_less(rhs_lower,lhs_lower)) return false;
115
116    const Point* lhs_upper = dereference_check_less(_p2,_p3) ? _p3.get() : _p2.get();
117    const Point* rhs_upper = dereference_check_less(rhs._p2,rhs._p3) ? rhs._p3.get() : rhs._p2.get();
118
119    return dereference_check_less(lhs_upper,rhs_upper);
120}
121
122
123void EdgeCollector::Triangle::setOrderedPoints(Point* p1, Point* p2, Point* p3)
124{
125    Point* points[3];
126
127    _op1 = points[0] = p1;
128    _op2 = points[1] = p2;
129    _op3 = points[2] = p3;
130
131    // find the lowest value point in the list.
132    unsigned int lowest = 0;
133    if (dereference_check_less(points[1],points[lowest])) lowest = 1;
134    if (dereference_check_less(points[2],points[lowest])) lowest = 2;
135
136    _p1 = points[lowest];
137    _p2 = points[(lowest+1)%3];
138    _p3 = points[(lowest+2)%3];
139
140    _plane.set(_op1->_vertex,_op2->_vertex,_op3->_vertex);
141}
142
143
144
145
146osg::UIntArray * EdgeCollector::Edgeloop::toIndexArray() const
147{
148    osg::UIntArray * indexArray = new osg::UIntArray;
149
150    EdgeList::const_iterator it = _edgeList.begin(), end = _edgeList.end();
151
152    for (;it != end; ++it)
153        indexArray->push_back((*it)->_op1->_index);
154
155    return indexArray;
156}
157
158EdgeCollector::Triangle* EdgeCollector::addTriangle(unsigned int p1, unsigned int p2, unsigned int p3)
159{
160    //OSG_NOTICE<<"addTriangle("<<p1<<","<<p2<<","<<p3<<")"<<std::endl;
161
162    // detect if triangle is degenerate.
163    if (p1==p2 || p2==p3 || p1==p3) return 0;
164    if ((_originalPointList[p1]->_vertex == _originalPointList[p2]->_vertex) ||
165        (_originalPointList[p2]->_vertex == _originalPointList[p3]->_vertex) ||
166        (_originalPointList[p3]->_vertex == _originalPointList[p1]->_vertex)) return 0;
167
168    Triangle* triangle = new Triangle;
169
170    triangle->setOrderedPoints(addPoint(triangle, p1), addPoint(triangle, p2), addPoint(triangle, p3));
171
172    triangle->_e1 = addEdge(triangle, triangle->_op1.get(), triangle->_op2.get());
173    triangle->_e2 = addEdge(triangle, triangle->_op2.get(), triangle->_op3.get());
174    triangle->_e3 = addEdge(triangle, triangle->_op3.get(), triangle->_op1.get());
175
176    _triangleSet.insert(triangle);
177
178    return triangle;
179}
180
181EdgeCollector::Triangle* EdgeCollector::addTriangle(Point* p1, Point* p2, Point* p3)
182{
183    // OSG_NOTICE<<"      addTriangle("<<p1<<","<<p2<<","<<p3<<")"<<std::endl;
184
185    // detect if triangle is degenerate.
186    if (p1==p2 || p2==p3 || p1==p3) return 0;
187    if ((p1->_vertex == p2->_vertex) ||
188        (p2->_vertex == p3->_vertex) ||
189        (p3->_vertex == p1->_vertex)) return 0;
190
191        Triangle* triangle = new Triangle;
192
193        triangle->setOrderedPoints(addPoint(triangle, p1), addPoint(triangle, p2), addPoint(triangle, p3));
194
195        triangle->_e1 = addEdge(triangle, triangle->_op1.get(), triangle->_op2.get());
196        triangle->_e2 = addEdge(triangle, triangle->_op2.get(), triangle->_op3.get());
197        triangle->_e3 = addEdge(triangle, triangle->_op3.get(), triangle->_op1.get());
198
199        _triangleSet.insert(triangle);
200
201        return triangle;
202    }
203
204
205EdgeCollector::Edge* EdgeCollector::addEdge(Triangle* triangle, Point* p1, Point* p2)
206{
207        // OSG_NOTICE<<"        addEdge("<<p1<<","<<p2<<")"<<std::endl;
208    osg::ref_ptr<Edge> edge = new Edge;
209    edge->setOrderedPoints(p1,p2);
210
211    EdgeSet::iterator itr = _edgeSet.find(edge);
212    if (itr==_edgeSet.end())
213    {
214        // OSG_NOTICE<<"          addEdge("<<edge.get()<<") edge->_p1="<<edge->_p1.get()<<" _p2="<<edge->_p2.get()<<std::endl;
215        _edgeSet.insert(edge);
216    }
217    else
218    {
219        // OSG_NOTICE<<"          reuseEdge("<<edge.get()<<") edge->_p1="<<edge->_p1.get()<<" _p2="<<edge->_p2.get()<<std::endl;
220        edge = *itr;
221    }
222
223    edge->addTriangle(triangle);
224
225    return edge.get();
226}
227
228
229
230
231EdgeCollector::Point* EdgeCollector::addPoint(Triangle* triangle, Point* point)
232{
233
234    PointSet::iterator itr = _pointSet.find(point);
235    if (itr==_pointSet.end())
236    {
237        //OSG_NOTICE<<"  addPoint("<<point.get()<<")"<<std::endl;
238        _pointSet.insert(point);
239    }
240    else
241    {
242        point = const_cast<Point*>(itr->get());
243        //OSG_NOTICE<<"  reusePoint("<<point.get()<<")"<<std::endl;
244    }
245
246    point->_triangles.insert(triangle);
247
248    return point;
249}
250
251void EdgeCollector::getBoundaryEdgeList(EdgeList & el)
252{
253    for (EdgeSet::iterator it = _edgeSet.begin(), end = _edgeSet.end(); it != end; ++it)
254    {
255        if ((*it)->isBoundaryEdge()) el.push_back(*it);
256    }
257}
258
259bool EdgeCollector::extractBoundaryEdgeloop(EdgeList & el, Edgeloop & edgeloop)
260{
261    if (el.empty()) return false;
262
263
264    osg::ref_ptr<Edge> current = el.back();
265    el.pop_back();
266
267    // ** init the Edgeloop
268    edgeloop._edgeList.push_back(current.get());
269
270
271
272    bool done = false;
273    while (!done)
274    {
275        bool found = false;
276        EdgeList::iterator it = el.begin(), end = el.end();
277        while (it != end && !found)
278        {
279            if (current->endConnected(*(it->get())))
280            {
281                found = true;
282            }
283            else
284            {
285                ++it;
286            }
287        }
288
289        if (!found)
290        {
291            OSG_WARN << "extractBoundaryEdgeloop : unable to close edge loop" << std::endl;
292            return false;
293        }
294        else
295        {
296            edgeloop._edgeList.push_back(it->get());
297            current = it->get();
298            el.erase(it);
299
300            if (edgeloop.isClosed()) done = true;
301        }
302    }
303    return true;
304}
305
306bool EdgeCollector::extractBoundaryEdgeloopList(EdgeList & el, EdgeloopList & edgeloopList)
307{
308    while (!el.empty())
309    {
310        osg::ref_ptr<Edgeloop> edgeloop(new Edgeloop);
311
312        if (extractBoundaryEdgeloop(el, *edgeloop))
313            edgeloopList.push_back(edgeloop);
314        else
315            return false;
316    }
317    return true;
318}
319
320
321
322
323
324
325
326struct CollectTriangleOperator
327{
328
329    CollectTriangleOperator():_ec(0) {}
330
331    void setEdgeCollector(EdgeCollector* ec) { _ec = ec; }
332
333    EdgeCollector* _ec;
334
335    // for use  in the triangle functor.
336    inline void operator()(unsigned int p1, unsigned int p2, unsigned int p3)
337    {
338        _ec->addTriangle(p1,p2,p3);
339    }
340
341};
342
343
344typedef osg::TriangleIndexFunctor<CollectTriangleOperator> CollectTriangleIndexFunctor;
345
346class CopyVertexArrayToPointsVisitor : public osg::ArrayVisitor
347{
348    public:
349        CopyVertexArrayToPointsVisitor(EdgeCollector::PointList& pointList):
350            _pointList(pointList) {}
351
352        virtual void apply(osg::Vec2Array& array)
353        {
354            if (_pointList.size()!=array.size()) return;
355
356            for(unsigned int i=0;i<_pointList.size();++i)
357            {
358                _pointList[i] = new EdgeCollector::Point;
359                _pointList[i]->_index = i;
360
361                osgUtil::ConvertVec<osg::Vec2, osg::Vec3d>::convert(array[i], _pointList[i]->_vertex);
362            }
363        }
364
365        virtual void apply(osg::Vec3Array& array)
366        {
367            if (_pointList.size()!=array.size()) return;
368
369            for(unsigned int i=0;i<_pointList.size();++i)
370            {
371                _pointList[i] = new EdgeCollector::Point;
372                _pointList[i]->_index = i;
373
374                _pointList[i]->_vertex = array[i];
375            }
376        }
377
378        virtual void apply(osg::Vec4Array& array)
379        {
380            if (_pointList.size()!=array.size()) return;
381
382            for(unsigned int i=0;i<_pointList.size();++i)
383            {
384                _pointList[i] = new EdgeCollector::Point;
385                _pointList[i]->_index = i;
386
387                osgUtil::ConvertVec<osg::Vec4, osg::Vec3d>::convert(array[i], _pointList[i]->_vertex);
388            }
389        }
390
391        virtual void apply(osg::Vec2dArray& array)
392        {
393            if (_pointList.size()!=array.size()) return;
394
395            for(unsigned int i=0;i<_pointList.size();++i)
396            {
397                _pointList[i] = new EdgeCollector::Point;
398                _pointList[i]->_index = i;
399
400                osgUtil::ConvertVec<osg::Vec2d, osg::Vec3d>::convert(array[i], _pointList[i]->_vertex);
401            }
402        }
403
404        virtual void apply(osg::Vec3dArray& array)
405        {
406            if (_pointList.size()!=array.size()) return;
407
408            for(unsigned int i=0;i<_pointList.size();++i)
409            {
410                _pointList[i] = new EdgeCollector::Point;
411                _pointList[i]->_index = i;
412
413                _pointList[i]->_vertex = array[i];
414            }
415        }
416
417        virtual void apply(osg::Vec4dArray& array)
418        {
419            if (_pointList.size()!=array.size()) return;
420
421            for(unsigned int i=0;i<_pointList.size();++i)
422            {
423                _pointList[i] = new EdgeCollector::Point;
424                _pointList[i]->_index = i;
425
426                osgUtil::ConvertVec<osg::Vec4d, osg::Vec3d>::convert(array[i], _pointList[i]->_vertex);
427            }
428        }
429
430        EdgeCollector::PointList& _pointList;
431
432    protected:
433
434        CopyVertexArrayToPointsVisitor& operator = (const CopyVertexArrayToPointsVisitor&) { return *this; }
435};
436
437EdgeCollector::~EdgeCollector()
438{
439    std::for_each(_edgeSet.begin(),_edgeSet.end(),dereference_clear());
440
441    std::for_each(_triangleSet.begin(),_triangleSet.end(),dereference_clear());
442    std::for_each(_pointSet.begin(),_pointSet.end(),dereference_clear());
443    std::for_each(_originalPointList.begin(),_originalPointList.end(),dereference_clear());
444}
445
446
447void EdgeCollector::setGeometry(osg::Geometry* geometry)
448{
449    _geometry = geometry;
450
451    // check to see if vertex attributes indices exists, if so expand them to remove them
452    if (_geometry->suitableForOptimization())
453    {
454        // removing coord indices
455        OSG_INFO<<"EdgeCollector::setGeometry(..): Removing attribute indices"<<std::endl;
456        _geometry->copyToAndOptimize(*_geometry);
457    }
458
459    unsigned int numVertices = geometry->getVertexArray()->getNumElements();
460
461    _originalPointList.resize(numVertices);
462
463    // copy vertices across to local point list
464    CopyVertexArrayToPointsVisitor copyVertexArrayToPoints(_originalPointList);
465    _geometry->getVertexArray()->accept(copyVertexArrayToPoints);
466
467    CollectTriangleIndexFunctor collectTriangles;
468    collectTriangles.setEdgeCollector(this);
469
470    _geometry->accept(collectTriangles);
471}
472
473// ** search BoundaryEdgeloop in the geometry, extrude this loop
474// **  and create primitiveSet to link original loop and extruded loop
475void EdgeCollector::getEdgeloopIndexList(IndexArrayList & ial)
476{
477    // ** collect Boundary Edge
478    EdgeList edgeList;
479    getBoundaryEdgeList(edgeList);
480
481    // ** collect Edgeloop
482    EdgeloopList edgeloopList;
483    if (extractBoundaryEdgeloopList(edgeList, edgeloopList) == false)
484    {
485        OSG_WARN << "EdgeCollector: fail to collect Edgeloop.\n\n\n" << std::endl;
486        return;
487    }
488
489    // ** get IndexArray of each Edgeloop
490    EdgeloopList::iterator elIt, elEnd = edgeloopList.end();
491    for (elIt = edgeloopList.begin(); elIt != elEnd; ++elIt)
492    {
493        ial.push_back((*elIt)->toIndexArray());
494    }
495}
496
497} // end of osgUtil namespace
Note: See TracBrowser for help on using the browser.