openscenegraph
Polytope
Go to the documentation of this file.
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#ifndef OSG_POLYTOPE
15#define OSG_POLYTOPE 1
16
17#include <osg/Plane>
18#include <osg/fast_back_stack>
19
20namespace osg {
21
22
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
26{
27
28 public:
29
30 typedef unsigned int ClippingMask;
31 typedef std::vector<Plane> PlaneList;
32 typedef std::vector<Vec3> VertexList;
33 typedef fast_back_stack<ClippingMask> MaskStack;
34
35 inline Polytope() {setupMask();}
36
37 inline Polytope(const Polytope& cv) :
38 _maskStack(cv._maskStack),
39 _resultMask(cv._resultMask),
40 _planeList(cv._planeList),
41 _referenceVertexList(cv._referenceVertexList) {}
42
43 inline Polytope(const PlaneList& pl) : _planeList(pl) {setupMask();}
44
45 inline ~Polytope() {}
46
47 inline void clear() { _planeList.clear(); setupMask(); }
48
49 inline Polytope& operator = (const Polytope& cv)
50 {
51 if (&cv==this) return *this;
52 _maskStack = cv._maskStack;
53 _resultMask = cv._resultMask;
54 _planeList = cv._planeList;
55 _referenceVertexList = cv._referenceVertexList;
56 return *this;
57 }
58
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)
61 {
62 _planeList.clear();
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
69 setupMask();
70 }
71
72 /** Create a Polytope which is a equivalent to BoundingBox.*/
73 void setToBoundingBox(const BoundingBox& bb)
74 {
75 _planeList.clear();
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
82 setupMask();
83 }
84
85 inline void setAndTransformProvidingInverse(const Polytope& pt, const osg::Matrix& matrix)
86 {
87 _referenceVertexList = pt._referenceVertexList;
88
89 unsigned int resultMask = pt._maskStack.back();
90 if (resultMask==0)
91 {
92 _maskStack.back() = 0;
93 _resultMask = 0;
94 _planeList.clear();
95 return;
96 }
97
98 ClippingMask selector_mask = 0x1;
99
100 unsigned int numActivePlanes = 0;
101
102 // count number of active planes.
103 PlaneList::const_iterator itr;
104 for(itr=pt._planeList.begin();
105 itr!=pt._planeList.end();
106 ++itr)
107 {
108 if (resultMask&selector_mask) ++numActivePlanes;
109 selector_mask <<= 1;
110 }
111
112 _planeList.resize(numActivePlanes);
113 _resultMask = 0;
114 selector_mask = 0x1;
115 unsigned int index = 0;
116 for(itr=pt._planeList.begin();
117 itr!=pt._planeList.end();
118 ++itr)
119 {
120 if (resultMask&selector_mask)
121 {
122 _planeList[index] = *itr;
123 _planeList[index++].transformProvidingInverse(matrix);
124 _resultMask = (_resultMask<<1) | 1;
125 }
126 selector_mask <<= 1;
127 }
128
129 _maskStack.back() = _resultMask;
130 }
131
132 inline void set(const PlaneList& pl) { _planeList = pl; setupMask(); }
133
134
135 inline void add(const osg::Plane& pl) { _planeList.push_back(pl); setupMask(); }
136
137 /** flip/reverse the orientation of all the planes.*/
138 inline void flip()
139 {
140 for(PlaneList::iterator itr=_planeList.begin();
141 itr!=_planeList.end();
142 ++itr)
143 {
144 itr->flip();
145 }
146 }
147
148 inline bool empty() const { return _planeList.empty(); }
149
150 inline PlaneList& getPlaneList() { return _planeList; }
151
152 inline const PlaneList& getPlaneList() const { return _planeList; }
153
154
155 inline void setReferenceVertexList(VertexList& vertices) { _referenceVertexList=vertices; }
156
157 inline VertexList& getReferenceVertexList() { return _referenceVertexList; }
158
159 inline const VertexList& getReferenceVertexList() const { return _referenceVertexList; }
160
161
162 inline void setupMask()
163 {
164 _resultMask = 0;
165 for(unsigned int i=0;i<_planeList.size();++i)
166 {
167 _resultMask = (_resultMask<<1) | 1;
168 }
169 _maskStack.push_back(_resultMask);
170 }
171
172 inline ClippingMask& getCurrentMask() { return _maskStack.back(); }
173
174 inline ClippingMask getCurrentMask() const { return _maskStack.back(); }
175
176 inline void setResultMask(ClippingMask mask) { _resultMask=mask; }
177
178 inline ClippingMask getResultMask() const { return _resultMask; }
179
180 MaskStack& getMaskStack() { return _maskStack; }
181
182 const MaskStack& getMaskStack() const { return _maskStack; }
183
184
185 inline void pushCurrentMask()
186 {
187 _maskStack.push_back(_resultMask);
188 }
189
190 inline void popCurrentMask()
191 {
192 _maskStack.pop_back();
193 }
194
195 /** Check whether a vertex is contained within clipping set.*/
196 inline bool contains(const osg::Vec3& v) const
197 {
198 if (!_maskStack.back()) return true;
199
200 unsigned int selector_mask = 0x1;
201 for(PlaneList::const_iterator itr=_planeList.begin();
202 itr!=_planeList.end();
203 ++itr)
204 {
205 if ((_maskStack.back()&selector_mask) && (itr->distance(v)<0.0f)) return false;
206 selector_mask <<= 1;
207 }
208 return true;
209 }
210
211 /** Check whether any part of vertex list is contained within clipping set.*/
212 inline bool contains(const std::vector<Vec3>& vertices)
213 {
214 if (!_maskStack.back()) return true;
215
216 _resultMask = _maskStack.back();
217
218 for(std::vector<Vec3>::const_iterator vitr = vertices.begin();
219 vitr != vertices.end();
220 ++vitr)
221 {
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;
227 ++itr)
228 {
229 if ((_maskStack.back()&selector_mask) && (itr->distance(v)<0.0f)) outside = true;
230 selector_mask <<= 1;
231 }
232
233 if (!outside) return true;
234 }
235 return false;
236 }
237
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)
244 {
245 if (!_maskStack.back()) return true;
246
247 _resultMask = _maskStack.back();
248 ClippingMask selector_mask = 0x1;
249
250 for(PlaneList::const_iterator itr=_planeList.begin();
251 itr!=_planeList.end();
252 ++itr)
253 {
254 if (_resultMask&selector_mask)
255 {
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.
259 }
260 selector_mask <<= 1;
261 }
262 return true;
263 }
264
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)
271 {
272 if (!_maskStack.back()) return true;
273
274 _resultMask = _maskStack.back();
275 ClippingMask selector_mask = 0x1;
276
277 for(PlaneList::const_iterator itr=_planeList.begin();
278 itr!=_planeList.end();
279 ++itr)
280 {
281 if (_resultMask&selector_mask)
282 {
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.
286 }
287 selector_mask <<= 1;
288 }
289 return true;
290 }
291
292 /** Check whether all of vertex list is contained with clipping set.*/
293 inline bool containsAllOf(const std::vector<Vec3>& vertices)
294 {
295 if (!_maskStack.back()) return false;
296
297 _resultMask = _maskStack.back();
298 ClippingMask selector_mask = 0x1;
299
300 for(PlaneList::const_iterator itr=_planeList.begin();
301 itr!=_planeList.end();
302 ++itr)
303 {
304 if (_resultMask&selector_mask)
305 {
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.
309 }
310 selector_mask <<= 1;
311 }
312 return true;
313 }
314
315 /** Check whether the entire bounding sphere is contained within clipping set.*/
316 inline bool containsAllOf(const osg::BoundingSphere& bs)
317 {
318 if (!_maskStack.back()) return false;
319
320 _resultMask = _maskStack.back();
321 ClippingMask selector_mask = 0x1;
322
323 for(PlaneList::const_iterator itr=_planeList.begin();
324 itr!=_planeList.end();
325 ++itr)
326 {
327 if (_resultMask&selector_mask)
328 {
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.
332 }
333 selector_mask <<= 1;
334 }
335 return true;
336 }
337
338 /** Check whether the entire bounding box is contained within clipping set.*/
339 inline bool containsAllOf(const osg::BoundingBox& bb)
340 {
341 if (!_maskStack.back()) return false;
342
343 _resultMask = _maskStack.back();
344 ClippingMask selector_mask = 0x1;
345
346 for(PlaneList::const_iterator itr=_planeList.begin();
347 itr!=_planeList.end();
348 ++itr)
349 {
350 if (_resultMask&selector_mask)
351 {
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.
355 }
356 selector_mask <<= 1;
357 }
358 return true;
359 }
360
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;
363
364
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)
372 {
373 osg::Matrix inverse;
374 inverse.invert(matrix);
375 transformProvidingInverse(inverse);
376 }
377
378 /** Transform the clipping set by provide a pre inverted matrix.
379 * see transform for details. */
380 inline void transformProvidingInverse(const osg::Matrix& matrix)
381 {
382 if (!_maskStack.back()) return;
383
384 _resultMask = _maskStack.back();
385 ClippingMask selector_mask = 0x1;
386 for(PlaneList::iterator itr=_planeList.begin();
387 itr!=_planeList.end();
388 ++itr)
389 {
390 if (_resultMask&selector_mask)
391 {
392 itr->transformProvidingInverse(matrix);
393 }
394 selector_mask <<= 1;
395 }
396 }
397
398 protected:
399
400
401 MaskStack _maskStack;
402 ClippingMask _resultMask;
403 PlaneList _planeList;
404 VertexList _referenceVertexList;
405
406};
407
408} // end of namespace
409
410#endif