← Back to branch summary

~ubuntu-branches/ubuntu/trusty/openscenegraph/trusty

« back to all changes in this revision

Viewing changes to OpenSceneGraph/src/osgUtil/EdgeCollector.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Cyril Brulebois
  • Date: 2008-07-29 04:34:38 UTC
  • mfrom: (1.1.6 upstream) (2.1.3 lenny)
  • Revision ID: james.westby@ubuntu.com-20080729043438-no1h9h0dpsrlzp1y
http://bugs.debian.org/477353
http://bugs.debian.org/482239
* Non-maintainer upload.
* No longer try to detect (using /proc/cpuinfo when available) how many
  CPUs are available, fixing the FTBFS (due to -j0) on various platforms
  (Closes: #477353). The right way to do it is to support parallel=n in
  DEB_BUILD_OPTIONS (see Debian Policy §4.9.1), and adequate support has
  been implemented.
* Add patch to fix FTBFS due to the build system now refusing to handle
  whitespaces (Policy CMP0004 say the logs), thanks to Andreas Putzo who
  provided it (Closes: #482239):
   - debian/patches/fix-cmp0004-build-failure.dpatch
* Remove myself from Uploaders, as requested a while ago, done by Luk in
  his 2.2.0-2.1 NMU, which was never acknowledged.

Show diffs side-by-side

added added

removed removed

Lines of Context:
OpenSceneGraph/src/osgUtil/EdgeCollector.cpp
 
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
 
 
19
namespace osgUtil
 
20
{
 
21
 
 
22
bool 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
 
 
40
void EdgeCollector::Edge::clear()
 
41
{
 
42
    _p1 = 0;
 
43
    _p2 = 0;
 
44
    _op1 = 0;
 
45
    _op2 = 0;
 
46
    _triangles.clear();
 
47
}
 
48
 
 
49
        
 
50
        
 
51
bool 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
 
 
59
bool 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
 
 
67
bool 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
 
 
75
void 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
 
 
89
void 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
 
 
104
bool 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
 
 
123
void 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
            
 
146
osg::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
    
 
158
EdgeCollector::Triangle* EdgeCollector::addTriangle(unsigned int p1, unsigned int p2, unsigned int p3)
 
159
{
 
160
    //osg::notify(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
 
 
181
EdgeCollector::Triangle* EdgeCollector::addTriangle(Point* p1, Point* p2, Point* p3)
 
182
{
 
183
    // osg::notify(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
   
 
205
EdgeCollector::Edge* EdgeCollector::addEdge(Triangle* triangle, Point* p1, Point* p2)
 
206
{
 
207
        // osg::notify(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::notify(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::notify(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
 
 
231
EdgeCollector::Point* EdgeCollector::addPoint(Triangle* triangle, Point* point)
 
232
{
 
233
    
 
234
    PointSet::iterator itr = _pointSet.find(point);
 
235
    if (itr==_pointSet.end())
 
236
    {
 
237
        //osg::notify(osg::NOTICE)<<"  addPoint("<<point.get()<<")"<<std::endl;
 
238
        _pointSet.insert(point);
 
239
    }
 
240
    else
 
241
    {
 
242
        point = const_cast<Point*>(itr->get());
 
243
        //osg::notify(osg::NOTICE)<<"  reusePoint("<<point.get()<<")"<<std::endl;
 
244
    }
 
245
 
 
246
    point->_triangles.insert(triangle);
 
247
    
 
248
    return point;
 
249
}
 
250
 
 
251
void 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
 
 
259
bool 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::notify(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
 
 
306
bool 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
 
 
326
struct 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
 
 
344
typedef osg::TriangleIndexFunctor<CollectTriangleOperator> CollectTriangleIndexFunctor;
 
345
 
 
346
class 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
 
 
433
EdgeCollector::~EdgeCollector()
 
434
{
 
435
    std::for_each(_edgeSet.begin(),_edgeSet.end(),dereference_clear());
 
436
 
 
437
    std::for_each(_triangleSet.begin(),_triangleSet.end(),dereference_clear());
 
438
    std::for_each(_pointSet.begin(),_pointSet.end(),dereference_clear());
 
439
    std::for_each(_originalPointList.begin(),_originalPointList.end(),dereference_clear());
 
440
}
 
441
 
 
442
 
 
443
void EdgeCollector::setGeometry(osg::Geometry* geometry)
 
444
{
 
445
    _geometry = geometry;
 
446
    
 
447
    // check to see if vertex attributes indices exists, if so expand them to remove them
 
448
    if (_geometry->suitableForOptimization())
 
449
    {
 
450
        // removing coord indices
 
451
        osg::notify(osg::INFO)<<"EdgeCollector::setGeometry(..): Removing attribute indices"<<std::endl;
 
452
        _geometry->copyToAndOptimize(*_geometry);
 
453
    }
 
454
 
 
455
    unsigned int numVertices = geometry->getVertexArray()->getNumElements();
 
456
        
 
457
    _originalPointList.resize(numVertices);
 
458
    
 
459
    // copy vertices across to local point list
 
460
    CopyVertexArrayToPointsVisitor copyVertexArrayToPoints(_originalPointList);
 
461
    _geometry->getVertexArray()->accept(copyVertexArrayToPoints);
 
462
 
 
463
    CollectTriangleIndexFunctor collectTriangles;
 
464
    collectTriangles.setEdgeCollector(this);
 
465
    
 
466
    _geometry->accept(collectTriangles);
 
467
}
 
468
 
 
469
// ** search BoundaryEdgeloop in the geometry, extrude this loop
 
470
// **  and create primitiveSet to link original loop and extruded loop
 
471
void EdgeCollector::getEdgeloopIndexList(IndexArrayList & ial)
 
472
{   
 
473
    // ** collect Boundary Edge
 
474
    EdgeList edgeList;
 
475
    getBoundaryEdgeList(edgeList);
 
476
    
 
477
    // ** collect Edgeloop
 
478
    EdgeloopList edgeloopList;
 
479
    if (extractBoundaryEdgeloopList(edgeList, edgeloopList) == false)
 
480
    {
 
481
        osg::notify(osg::WARN) << "EdgeCollector: fail to collect Edgeloop.\n\n\n" << std::endl;
 
482
        return;
 
483
    }
 
484
    
 
485
    // ** get IndexArray of each Edgeloop
 
486
    EdgeloopList::iterator elIt, elEnd = edgeloopList.end();
 
487
    for (elIt = edgeloopList.begin(); elIt != elEnd; ++elIt)
 
488
    {
 
489
        ial.push_back((*elIt)->toIndexArray());
 
490
    }
 
491
}
 
492
 
 
493
} // end of osgUtil namespace