HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
ImathFrustumTest.h
Go to the documentation of this file.
1 ///////////////////////////////////////////////////////////////////////////
2 //
3 // Copyright (c) 2011-2012, Industrial Light & Magic, a division of Lucas
4 // Digital Ltd. LLC
5 //
6 // All rights reserved.
7 //
8 // Redistribution and use in source and binary forms, with or without
9 // modification, are permitted provided that the following conditions are
10 // met:
11 // * Redistributions of source code must retain the above copyright
12 // notice, this list of conditions and the following disclaimer.
13 // * Redistributions in binary form must reproduce the above
14 // copyright notice, this list of conditions and the following disclaimer
15 // in the documentation and/or other materials provided with the
16 // distribution.
17 // * Neither the name of Industrial Light & Magic nor the names of
18 // its contributors may be used to endorse or promote products derived
19 // from this software without specific prior written permission.
20 //
21 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
27 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
28 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
29 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
30 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
31 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 //
33 ///////////////////////////////////////////////////////////////////////////
34 
35 
36 #ifndef INCLUDED_IMATHFRUSTUMTEST_H
37 #define INCLUDED_IMATHFRUSTUMTEST_H
38 
39 //-------------------------------------------------------------------------
40 //
41 // This file contains algorithms applied to or in conjunction with
42 // Frustum visibility testing (Imath::Frustum).
43 //
44 // Methods for frustum-based rejection of primitives are contained here.
45 //
46 //-------------------------------------------------------------------------
47 
48 #include "ImathFrustum.h"
49 #include "ImathBox.h"
50 #include "ImathSphere.h"
51 #include "ImathMatrix.h"
52 #include "ImathVec.h"
53 #include "ImathNamespace.h"
54 
56 
57 /////////////////////////////////////////////////////////////////
58 // FrustumTest
59 //
60 // template class FrustumTest<T>
61 //
62 // This is a helper class, designed to accelerate the case
63 // where many tests are made against the same frustum.
64 // That's a really common case.
65 //
66 // The acceleration is achieved by pre-computing the planes of
67 // the frustum, along with the ablsolute values of the plane normals.
68 //
69 
70 
71 
72 //////////////////////////////////////////////////////////////////
73 // How to use this
74 //
75 // Given that you already have:
76 // Imath::Frustum myFrustum
77 // Imath::Matrix44 myCameraWorldMatrix
78 //
79 // First, make a frustum test object:
80 // FrustumTest myFrustumTest(myFrustum, myCameraWorldMatrix)
81 //
82 // Whenever the camera or frustum changes, call:
83 // myFrustumTest.setFrustum(myFrustum, myCameraWorldMatrix)
84 //
85 // For each object you want to test for visibility, call:
86 // myFrustumTest.isVisible(myBox)
87 // myFrustumTest.isVisible(mySphere)
88 // myFrustumTest.isVisible(myVec3)
89 // myFrustumTest.completelyContains(myBox)
90 // myFrustumTest.completelyContains(mySphere)
91 //
92 
93 
94 
95 
96 //////////////////////////////////////////////////////////////////
97 // Explanation of how it works
98 //
99 //
100 // We store six world-space Frustum planes (nx, ny, nz, offset)
101 //
102 // Points: To test a Vec3 for visibility, test it against each plane
103 // using the normal (v dot n - offset) method. (the result is exact)
104 //
105 // BBoxes: To test an axis-aligned bbox, test the center against each plane
106 // using the normal (v dot n - offset) method, but offset by the
107 // box extents dot the abs of the plane normal. (the result is NOT
108 // exact, but will not return false-negatives.)
109 //
110 // Spheres: To test a sphere, test the center against each plane
111 // using the normal (v dot n - offset) method, but offset by the
112 // sphere's radius. (the result is NOT exact, but will not return
113 // false-negatives.)
114 //
115 //
116 // SPECIAL NOTE: "Where are the dot products?"
117 // Actual dot products are currently slow for most SIMD architectures.
118 // In order to keep this code optimization-ready, the dot products
119 // are all performed using vector adds and multipies.
120 //
121 // In order to do this, the plane equations are stored in "transpose"
122 // form, with the X components grouped into an X vector, etc.
123 //
124 
125 
126 template <class T>
127 class FrustumTest
128 {
129 public:
131  {
132  Frustum<T> frust;
134  cameraMat.makeIdentity();
135  setFrustum(frust, cameraMat);
136  }
137  FrustumTest(const Frustum<T> &frustum, const Matrix44<T> &cameraMat)
138  {
139  setFrustum(frustum, cameraMat);
140  }
141 
142  ////////////////////////////////////////////////////////////////////
143  // setFrustum()
144  // This updates the frustum test with a new frustum and matrix.
145  // This should usually be called just once per frame.
146  void setFrustum(const Frustum<T> &frustum, const Matrix44<T> &cameraMat);
147 
148  ////////////////////////////////////////////////////////////////////
149  // isVisible()
150  // Check to see if shapes are visible.
151  bool isVisible(const Sphere3<T> &sphere) const;
152  bool isVisible(const Box<Vec3<T> > &box) const;
153  bool isVisible(const Vec3<T> &vec) const;
154 
155  ////////////////////////////////////////////////////////////////////
156  // completelyContains()
157  // Check to see if shapes are entirely contained.
158  bool completelyContains(const Sphere3<T> &sphere) const;
159  bool completelyContains(const Box<Vec3<T> > &box) const;
160 
161  // These next items are kept primarily for debugging tools.
162  // It's useful for drawing the culling environment, and also
163  // for getting an "outside view" of the culling frustum.
164  IMATH_INTERNAL_NAMESPACE::Matrix44<T> cameraMat() const {return cameraMatrix;}
165  IMATH_INTERNAL_NAMESPACE::Frustum<T> currentFrustum() const {return currFrustum;}
166 
167 protected:
168  // To understand why the planes are stored this way, see
169  // the SPECIAL NOTE above.
170  Vec3<T> planeNormX[2]; // The X compunents from 6 plane equations
171  Vec3<T> planeNormY[2]; // The Y compunents from 6 plane equations
172  Vec3<T> planeNormZ[2]; // The Z compunents from 6 plane equations
173 
174  Vec3<T> planeOffsetVec[2]; // The distance offsets from 6 plane equations
175 
176  // The absolute values are stored to assist with bounding box tests.
177  Vec3<T> planeNormAbsX[2]; // The abs(X) compunents from 6 plane equations
178  Vec3<T> planeNormAbsY[2]; // The abs(X) compunents from 6 plane equations
179  Vec3<T> planeNormAbsZ[2]; // The abs(X) compunents from 6 plane equations
180 
181  // These are kept primarily for debugging tools.
184 };
185 
186 
187 ////////////////////////////////////////////////////////////////////
188 // setFrustum()
189 // This should usually only be called once per frame, or however
190 // often the camera moves.
191 template<class T>
193  const Matrix44<T> &cameraMat)
194 {
195  Plane3<T> frustumPlanes[6];
196  frustum.planes(frustumPlanes, cameraMat);
197 
198  // Here's where we effectively transpose the plane equations.
199  // We stuff all six X's into the two planeNormX vectors, etc.
200  for (int i = 0; i < 2; ++i)
201  {
202  int index = i * 3;
203 
204  planeNormX[i] = Vec3<T>(frustumPlanes[index + 0].normal.x,
205  frustumPlanes[index + 1].normal.x,
206  frustumPlanes[index + 2].normal.x);
207  planeNormY[i] = Vec3<T>(frustumPlanes[index + 0].normal.y,
208  frustumPlanes[index + 1].normal.y,
209  frustumPlanes[index + 2].normal.y);
210  planeNormZ[i] = Vec3<T>(frustumPlanes[index + 0].normal.z,
211  frustumPlanes[index + 1].normal.z,
212  frustumPlanes[index + 2].normal.z);
213 
214  planeNormAbsX[i] = Vec3<T>(IMATH_INTERNAL_NAMESPACE::abs(planeNormX[i].x),
215  IMATH_INTERNAL_NAMESPACE::abs(planeNormX[i].y),
216  IMATH_INTERNAL_NAMESPACE::abs(planeNormX[i].z));
217  planeNormAbsY[i] = Vec3<T>(IMATH_INTERNAL_NAMESPACE::abs(planeNormY[i].x),
218  IMATH_INTERNAL_NAMESPACE::abs(planeNormY[i].y),
219  IMATH_INTERNAL_NAMESPACE::abs(planeNormY[i].z));
220  planeNormAbsZ[i] = Vec3<T>(IMATH_INTERNAL_NAMESPACE::abs(planeNormZ[i].x),
221  IMATH_INTERNAL_NAMESPACE::abs(planeNormZ[i].y),
222  IMATH_INTERNAL_NAMESPACE::abs(planeNormZ[i].z));
223 
224  planeOffsetVec[i] = Vec3<T>(frustumPlanes[index + 0].distance,
225  frustumPlanes[index + 1].distance,
226  frustumPlanes[index + 2].distance);
227  }
228  currFrustum = frustum;
229  cameraMatrix = cameraMat;
230 }
231 
232 
233 ////////////////////////////////////////////////////////////////////
234 // isVisible(Sphere)
235 // Returns true if any part of the sphere is inside
236 // the frustum.
237 // The result MAY return close false-positives, but not false-negatives.
238 //
239 template<typename T>
240 bool FrustumTest<T>::isVisible(const Sphere3<T> &sphere) const
241 {
242  Vec3<T> center = sphere.center;
243  Vec3<T> radiusVec = Vec3<T>(sphere.radius, sphere.radius, sphere.radius);
244 
245  // This is a vertical dot-product on three vectors at once.
246  Vec3<T> d0 = planeNormX[0] * center.x
247  + planeNormY[0] * center.y
248  + planeNormZ[0] * center.z
249  - radiusVec
250  - planeOffsetVec[0];
251 
252  if (d0.x >= 0 || d0.y >= 0 || d0.z >= 0)
253  return false;
254 
255  Vec3<T> d1 = planeNormX[1] * center.x
256  + planeNormY[1] * center.y
257  + planeNormZ[1] * center.z
258  - radiusVec
259  - planeOffsetVec[1];
260 
261  if (d1.x >= 0 || d1.y >= 0 || d1.z >= 0)
262  return false;
263 
264  return true;
265 }
266 
267 ////////////////////////////////////////////////////////////////////
268 // completelyContains(Sphere)
269 // Returns true if every part of the sphere is inside
270 // the frustum.
271 // The result MAY return close false-negatives, but not false-positives.
272 //
273 template<typename T>
275 {
276  Vec3<T> center = sphere.center;
277  Vec3<T> radiusVec = Vec3<T>(sphere.radius, sphere.radius, sphere.radius);
278 
279  // This is a vertical dot-product on three vectors at once.
280  Vec3<T> d0 = planeNormX[0] * center.x
281  + planeNormY[0] * center.y
282  + planeNormZ[0] * center.z
283  + radiusVec
284  - planeOffsetVec[0];
285 
286  if (d0.x >= 0 || d0.y >= 0 || d0.z >= 0)
287  return false;
288 
289  Vec3<T> d1 = planeNormX[1] * center.x
290  + planeNormY[1] * center.y
291  + planeNormZ[1] * center.z
292  + radiusVec
293  - planeOffsetVec[1];
294 
295  if (d1.x >= 0 || d1.y >= 0 || d1.z >= 0)
296  return false;
297 
298  return true;
299 }
300 
301 ////////////////////////////////////////////////////////////////////
302 // isVisible(Box)
303 // Returns true if any part of the axis-aligned box
304 // is inside the frustum.
305 // The result MAY return close false-positives, but not false-negatives.
306 //
307 template<typename T>
308 bool FrustumTest<T>::isVisible(const Box<Vec3<T> > &box) const
309 {
310  if (box.isEmpty())
311  return false;
312 
313  Vec3<T> center = (box.min + box.max) / 2;
314  Vec3<T> extent = (box.max - center);
315 
316  // This is a vertical dot-product on three vectors at once.
317  Vec3<T> d0 = planeNormX[0] * center.x
318  + planeNormY[0] * center.y
319  + planeNormZ[0] * center.z
320  - planeNormAbsX[0] * extent.x
321  - planeNormAbsY[0] * extent.y
322  - planeNormAbsZ[0] * extent.z
323  - planeOffsetVec[0];
324 
325  if (d0.x >= 0 || d0.y >= 0 || d0.z >= 0)
326  return false;
327 
328  Vec3<T> d1 = planeNormX[1] * center.x
329  + planeNormY[1] * center.y
330  + planeNormZ[1] * center.z
331  - planeNormAbsX[1] * extent.x
332  - planeNormAbsY[1] * extent.y
333  - planeNormAbsZ[1] * extent.z
334  - planeOffsetVec[1];
335 
336  if (d1.x >= 0 || d1.y >= 0 || d1.z >= 0)
337  return false;
338 
339  return true;
340 }
341 
342 ////////////////////////////////////////////////////////////////////
343 // completelyContains(Box)
344 // Returns true if every part of the axis-aligned box
345 // is inside the frustum.
346 // The result MAY return close false-negatives, but not false-positives.
347 //
348 template<typename T>
350 {
351  if (box.isEmpty())
352  return false;
353 
354  Vec3<T> center = (box.min + box.max) / 2;
355  Vec3<T> extent = (box.max - center);
356 
357  // This is a vertical dot-product on three vectors at once.
358  Vec3<T> d0 = planeNormX[0] * center.x
359  + planeNormY[0] * center.y
360  + planeNormZ[0] * center.z
361  + planeNormAbsX[0] * extent.x
362  + planeNormAbsY[0] * extent.y
363  + planeNormAbsZ[0] * extent.z
364  - planeOffsetVec[0];
365 
366  if (d0.x >= 0 || d0.y >= 0 || d0.z >= 0)
367  return false;
368 
369  Vec3<T> d1 = planeNormX[1] * center.x
370  + planeNormY[1] * center.y
371  + planeNormZ[1] * center.z
372  + planeNormAbsX[1] * extent.x
373  + planeNormAbsY[1] * extent.y
374  + planeNormAbsZ[1] * extent.z
375  - planeOffsetVec[1];
376 
377  if (d1.x >= 0 || d1.y >= 0 || d1.z >= 0)
378  return false;
379 
380  return true;
381 }
382 
383 
384 ////////////////////////////////////////////////////////////////////
385 // isVisible(Vec3)
386 // Returns true if the point is inside the frustum.
387 //
388 template<typename T>
389 bool FrustumTest<T>::isVisible(const Vec3<T> &vec) const
390 {
391  // This is a vertical dot-product on three vectors at once.
392  Vec3<T> d0 = (planeNormX[0] * vec.x)
393  + (planeNormY[0] * vec.y)
394  + (planeNormZ[0] * vec.z)
395  - planeOffsetVec[0];
396 
397  if (d0.x >= 0 || d0.y >= 0 || d0.z >= 0)
398  return false;
399 
400  Vec3<T> d1 = (planeNormX[1] * vec.x)
401  + (planeNormY[1] * vec.y)
402  + (planeNormZ[1] * vec.z)
403  - planeOffsetVec[1];
404 
405  if (d1.x >= 0 || d1.y >= 0 || d1.z >= 0)
406  return false;
407 
408  return true;
409 }
410 
411 
414 
416 
417 #endif // INCLUDED_IMATHFRUSTUMTEST_H
#define IMATH_INTERNAL_NAMESPACE_HEADER_EXIT
Vec3< T > planeNormY[2]
T z
Definition: ImathVec.h:275
#define IMATH_INTERNAL_NAMESPACE_HEADER_ENTER
GLdouble GLdouble GLdouble z
Definition: glcorearb.h:847
FrustumTest(const Frustum< T > &frustum, const Matrix44< T > &cameraMat)
GLint y
Definition: glcorearb.h:102
FrustumTest< float > FrustumTestf
png_uint_32 i
Definition: png.h:2877
T distance
Definition: ImathPlane.h:68
void makeIdentity()
Definition: ImathMatrix.h:2187
bool completelyContains(const Sphere3< T > &sphere) const
Vec3< T > planeOffsetVec[2]
T x
Definition: ImathVec.h:275
IMATH_INTERNAL_NAMESPACE_HEADER_ENTER T abs(T a)
Definition: ImathFun.h:55
Vec3< T > planeNormZ[2]
Vec3< T > center
Definition: ImathSphere.h:58
bool isVisible(const Sphere3< T > &sphere) const
Vec3< T > planeNormAbsX[2]
Vec3< T > planeNormAbsZ[2]
Vec3< T > planeNormX[2]
void setFrustum(const Frustum< T > &frustum, const Matrix44< T > &cameraMat)
FrustumTest< double > FrustumTestd
GLuint index
Definition: glcorearb.h:785
GLint GLenum GLint x
Definition: glcorearb.h:408
T y
Definition: ImathVec.h:275
Definition: ImathBox.h:72
Matrix44< T > cameraMatrix
IMATH_INTERNAL_NAMESPACE::Matrix44< T > cameraMat() const
Vec3< T > normal
Definition: ImathPlane.h:67
IMATH_INTERNAL_NAMESPACE::Frustum< T > currentFrustum() const
void planes(Plane3< T > p[6]) const
Definition: ImathFrustum.h:648
Vec3< T > planeNormAbsY[2]
Frustum< T > currFrustum