1/* -*-c++-*- OpenSceneGraph - Copyright (C) 1998-2006 Robert Osfield
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.
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.
18#include <osg/fast_back_stack>
23/** A Polytope class for representing convex clipping volumes made up of a set of planes.
24 * When adding planes, their normals should point inwards (into the volume) */
25class OSG_EXPORT Polytope
30 typedef unsigned int ClippingMask;
31 typedef std::vector<Plane> PlaneList;
32 typedef std::vector<Vec3> VertexList;
33 typedef fast_back_stack<ClippingMask> MaskStack;
35 inline Polytope() {setupMask();}
37 inline Polytope(const Polytope& cv) :
38 _maskStack(cv._maskStack),
39 _resultMask(cv._resultMask),
40 _planeList(cv._planeList),
41 _referenceVertexList(cv._referenceVertexList) {}
43 inline Polytope(const PlaneList& pl) : _planeList(pl) {setupMask();}
47 inline void clear() { _planeList.clear(); setupMask(); }
49 inline Polytope& operator = (const Polytope& cv)
51 if (&cv==this) return *this;
52 _maskStack = cv._maskStack;
53 _resultMask = cv._resultMask;
54 _planeList = cv._planeList;
55 _referenceVertexList = cv._referenceVertexList;
59 /** Create a Polytope which is a cube, centered at 0,0,0, with sides of 2 units.*/
60 void setToUnitFrustum(bool withNear=true, bool withFar=true)
63 _planeList.push_back(Plane(1.0,0.0,0.0,1.0)); // left plane.
64 _planeList.push_back(Plane(-1.0,0.0,0.0,1.0)); // right plane.
65 _planeList.push_back(Plane(0.0,1.0,0.0,1.0)); // bottom plane.
66 _planeList.push_back(Plane(0.0,-1.0,0.0,1.0)); // top plane.
67 if (withNear) _planeList.push_back(Plane(0.0,0.0,1.0,1.0)); // near plane
68 if (withFar) _planeList.push_back(Plane(0.0,0.0,-1.0,1.0)); // far plane
72 /** Create a Polytope which is a equivalent to BoundingBox.*/
73 void setToBoundingBox(const BoundingBox& bb)
76 _planeList.push_back(Plane(1.0,0.0,0.0,-bb.xMin())); // left plane.
77 _planeList.push_back(Plane(-1.0,0.0,0.0,bb.xMax())); // right plane.
78 _planeList.push_back(Plane(0.0,1.0,0.0,-bb.yMin())); // bottom plane.
79 _planeList.push_back(Plane(0.0,-1.0,0.0,bb.yMax())); // top plane.
80 _planeList.push_back(Plane(0.0,0.0,1.0,-bb.zMin())); // near plane
81 _planeList.push_back(Plane(0.0,0.0,-1.0,bb.zMax())); // far plane
85 inline void setAndTransformProvidingInverse(const Polytope& pt, const osg::Matrix& matrix)
87 _referenceVertexList = pt._referenceVertexList;
89 unsigned int resultMask = pt._maskStack.back();
92 _maskStack.back() = 0;
98 ClippingMask selector_mask = 0x1;
100 unsigned int numActivePlanes = 0;
102 // count number of active planes.
103 PlaneList::const_iterator itr;
104 for(itr=pt._planeList.begin();
105 itr!=pt._planeList.end();
108 if (resultMask&selector_mask) ++numActivePlanes;
112 _planeList.resize(numActivePlanes);
115 unsigned int index = 0;
116 for(itr=pt._planeList.begin();
117 itr!=pt._planeList.end();
120 if (resultMask&selector_mask)
122 _planeList[index] = *itr;
123 _planeList[index++].transformProvidingInverse(matrix);
124 _resultMask = (_resultMask<<1) | 1;
129 _maskStack.back() = _resultMask;
132 inline void set(const PlaneList& pl) { _planeList = pl; setupMask(); }
135 inline void add(const osg::Plane& pl) { _planeList.push_back(pl); setupMask(); }
137 /** flip/reverse the orientation of all the planes.*/
140 for(PlaneList::iterator itr=_planeList.begin();
141 itr!=_planeList.end();
148 inline bool empty() const { return _planeList.empty(); }
150 inline PlaneList& getPlaneList() { return _planeList; }
152 inline const PlaneList& getPlaneList() const { return _planeList; }
155 inline void setReferenceVertexList(VertexList& vertices) { _referenceVertexList=vertices; }
157 inline VertexList& getReferenceVertexList() { return _referenceVertexList; }
159 inline const VertexList& getReferenceVertexList() const { return _referenceVertexList; }
162 inline void setupMask()
165 for(unsigned int i=0;i<_planeList.size();++i)
167 _resultMask = (_resultMask<<1) | 1;
169 _maskStack.push_back(_resultMask);
172 inline ClippingMask& getCurrentMask() { return _maskStack.back(); }
174 inline ClippingMask getCurrentMask() const { return _maskStack.back(); }
176 inline void setResultMask(ClippingMask mask) { _resultMask=mask; }
178 inline ClippingMask getResultMask() const { return _resultMask; }
180 MaskStack& getMaskStack() { return _maskStack; }
182 const MaskStack& getMaskStack() const { return _maskStack; }
185 inline void pushCurrentMask()
187 _maskStack.push_back(_resultMask);
190 inline void popCurrentMask()
192 _maskStack.pop_back();
195 /** Check whether a vertex is contained within clipping set.*/
196 inline bool contains(const osg::Vec3& v) const
198 if (!_maskStack.back()) return true;
200 unsigned int selector_mask = 0x1;
201 for(PlaneList::const_iterator itr=_planeList.begin();
202 itr!=_planeList.end();
205 if ((_maskStack.back()&selector_mask) && (itr->distance(v)<0.0f)) return false;
211 /** Check whether any part of vertex list is contained within clipping set.*/
212 inline bool contains(const std::vector<Vec3>& vertices)
214 if (!_maskStack.back()) return true;
216 _resultMask = _maskStack.back();
218 for(std::vector<Vec3>::const_iterator vitr = vertices.begin();
219 vitr != vertices.end();
222 const osg::Vec3& v = *vitr;
223 bool outside = false;
224 ClippingMask selector_mask = 0x1;
225 for(PlaneList::const_iterator itr=_planeList.begin();
226 itr!=_planeList.end() && !outside;
229 if ((_maskStack.back()&selector_mask) && (itr->distance(v)<0.0f)) outside = true;
233 if (!outside) return true;
238 /** Check whether any part of a bounding sphere is contained within clipping set.
239 Using a mask to determine which planes should be used for the check, and
240 modifying the mask to turn off planes which wouldn't contribute to clipping
241 of any internal objects. This feature is used in osgUtil::CullVisitor
242 to prevent redundant plane checking.*/
243 inline bool contains(const osg::BoundingSphere& bs)
245 if (!_maskStack.back()) return true;
247 _resultMask = _maskStack.back();
248 ClippingMask selector_mask = 0x1;
250 for(PlaneList::const_iterator itr=_planeList.begin();
251 itr!=_planeList.end();
254 if (_resultMask&selector_mask)
256 int res=itr->intersect(bs);
257 if (res<0) return false; // outside clipping set.
258 else if (res>0) _resultMask ^= selector_mask; // subsequent checks against this plane not required.
265 /** Check whether any part of a bounding box is contained within clipping set.
266 Using a mask to determine which planes should be used for the check, and
267 modifying the mask to turn off planes which wouldn't contribute to clipping
268 of any internal objects. This feature is used in osgUtil::CullVisitor
269 to prevent redundant plane checking.*/
270 inline bool contains(const osg::BoundingBox& bb)
272 if (!_maskStack.back()) return true;
274 _resultMask = _maskStack.back();
275 ClippingMask selector_mask = 0x1;
277 for(PlaneList::const_iterator itr=_planeList.begin();
278 itr!=_planeList.end();
281 if (_resultMask&selector_mask)
283 int res=itr->intersect(bb);
284 if (res<0) return false; // outside clipping set.
285 else if (res>0) _resultMask ^= selector_mask; // subsequent checks against this plane not required.
292 /** Check whether all of vertex list is contained with clipping set.*/
293 inline bool containsAllOf(const std::vector<Vec3>& vertices)
295 if (!_maskStack.back()) return false;
297 _resultMask = _maskStack.back();
298 ClippingMask selector_mask = 0x1;
300 for(PlaneList::const_iterator itr=_planeList.begin();
301 itr!=_planeList.end();
304 if (_resultMask&selector_mask)
306 int res=itr->intersect(vertices);
307 if (res<1) return false; // intersects, or is below plane.
308 _resultMask ^= selector_mask; // subsequent checks against this plane not required.
315 /** Check whether the entire bounding sphere is contained within clipping set.*/
316 inline bool containsAllOf(const osg::BoundingSphere& bs)
318 if (!_maskStack.back()) return false;
320 _resultMask = _maskStack.back();
321 ClippingMask selector_mask = 0x1;
323 for(PlaneList::const_iterator itr=_planeList.begin();
324 itr!=_planeList.end();
327 if (_resultMask&selector_mask)
329 int res=itr->intersect(bs);
330 if (res<1) return false; // intersects, or is below plane.
331 _resultMask ^= selector_mask; // subsequent checks against this plane not required.
338 /** Check whether the entire bounding box is contained within clipping set.*/
339 inline bool containsAllOf(const osg::BoundingBox& bb)
341 if (!_maskStack.back()) return false;
343 _resultMask = _maskStack.back();
344 ClippingMask selector_mask = 0x1;
346 for(PlaneList::const_iterator itr=_planeList.begin();
347 itr!=_planeList.end();
350 if (_resultMask&selector_mask)
352 int res=itr->intersect(bb);
353 if (res<1) return false; // intersects, or is below plane.
354 _resultMask ^= selector_mask; // subsequent checks against this plane not required.
361 /** Check whether any part of a triangle is contained within the polytope.*/
362 bool contains(const osg::Vec3f& v0, const osg::Vec3f& v1, const osg::Vec3f& v2) const;
365 /** Transform the clipping set by matrix. Note, this operations carries out
366 * the calculation of the inverse of the matrix since a plane must
367 * be multiplied by the inverse transposed to transform it. This
368 * makes this operation expensive. If the inverse has been already
369 * calculated elsewhere then use transformProvidingInverse() instead.
370 * See http://www.worldserver.com/turk/computergraphics/NormalTransformations.pdf*/
371 inline void transform(const osg::Matrix& matrix)
374 inverse.invert(matrix);
375 transformProvidingInverse(inverse);
378 /** Transform the clipping set by provide a pre inverted matrix.
379 * see transform for details. */
380 inline void transformProvidingInverse(const osg::Matrix& matrix)
382 if (!_maskStack.back()) return;
384 _resultMask = _maskStack.back();
385 ClippingMask selector_mask = 0x1;
386 for(PlaneList::iterator itr=_planeList.begin();
387 itr!=_planeList.end();
390 if (_resultMask&selector_mask)
392 itr->transformProvidingInverse(matrix);
401 MaskStack _maskStack;
402 ClippingMask _resultMask;
403 PlaneList _planeList;
404 VertexList _referenceVertexList;