HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
ImathFrustumTest.h
Go to the documentation of this file.
1 //
2 // SPDX-License-Identifier: BSD-3-Clause
3 // Copyright Contributors to the OpenEXR Project.
4 //
5 
6 //
7 // A viewing frustum class
8 //
9 // This file contains algorithms applied to or in conjunction with
10 // Frustum visibility testing (Imath::Frustum).
11 //
12 // Methods for frustum-based rejection of primitives are contained here.
13 //
14 
15 #ifndef INCLUDED_IMATHFRUSTUMTEST_H
16 #define INCLUDED_IMATHFRUSTUMTEST_H
17 
18 #include "ImathExport.h"
19 #include "ImathNamespace.h"
20 
21 #include "ImathBox.h"
22 #include "ImathFrustum.h"
23 #include "ImathMatrix.h"
24 #include "ImathSphere.h"
25 #include "ImathVec.h"
26 
27 IMATH_INTERNAL_NAMESPACE_HEADER_ENTER
28 
29 ///
30 /// template class FrustumTest<T>
31 ///
32 /// This is a helper class, designed to accelerate the case
33 /// where many tests are made against the same frustum.
34 /// That's a really common case.
35 ///
36 /// The acceleration is achieved by pre-computing the planes of
37 /// the frustum, along with the ablsolute values of the plane normals.
38 ///
39 /// How to use this
40 ///
41 /// Given that you already have:
42 /// Imath::Frustum myFrustum
43 /// Imath::Matrix44 myCameraWorldMatrix
44 ///
45 /// First, make a frustum test object:
46 /// FrustumTest myFrustumTest(myFrustum, myCameraWorldMatrix)
47 ///
48 /// Whenever the camera or frustum changes, call:
49 /// myFrustumTest.setFrustum(myFrustum, myCameraWorldMatrix)
50 ///
51 /// For each object you want to test for visibility, call:
52 /// myFrustumTest.isVisible(myBox)
53 /// myFrustumTest.isVisible(mySphere)
54 /// myFrustumTest.isVisible(myVec3)
55 /// myFrustumTest.completelyContains(myBox)
56 /// myFrustumTest.completelyContains(mySphere)
57 ///
58 /// Explanation of how it works
59 ///
60 /// We store six world-space Frustum planes (nx, ny, nz, offset)
61 ///
62 /// Points: To test a Vec3 for visibility, test it against each plane
63 /// using the normal (v dot n - offset) method. (the result is exact)
64 ///
65 /// BBoxes: To test an axis-aligned bbox, test the center against each plane
66 /// using the normal (v dot n - offset) method, but offset by the
67 /// box extents dot the abs of the plane normal. (the result is NOT
68 /// exact, but will not return false-negatives.)
69 ///
70 /// Spheres: To test a sphere, test the center against each plane
71 /// using the normal (v dot n - offset) method, but offset by the
72 /// sphere's radius. (the result is NOT exact, but will not return
73 /// false-negatives.)
74 ///
75 ///
76 /// SPECIAL NOTE: "Where are the dot products?"
77 /// Actual dot products are currently slow for most SIMD architectures.
78 /// In order to keep this code optimization-ready, the dot products
79 /// are all performed using vector adds and multipies.
80 ///
81 /// In order to do this, the plane equations are stored in "transpose"
82 /// form, with the X components grouped into an X vector, etc.
83 ///
84 
85 template <class T> class IMATH_EXPORT_TEMPLATE_TYPE FrustumTest
86 {
87  public:
88  /// @{
89  /// @name Constructors
90 
91  /// Initialize camera matrix to identity
93  {
94  Frustum<T> frust;
95  Matrix44<T> cameraMat;
96  cameraMat.makeIdentity();
97  setFrustum (frust, cameraMat);
98  }
99 
100  /// Initialize to a given frustum and camera matrix.
101  FrustumTest (const Frustum<T>& frustum, const Matrix44<T>& cameraMat) IMATH_NOEXCEPT
102  {
103  setFrustum (frustum, cameraMat);
104  }
105 
106  /// @}
107 
108  /// @{
109  /// @name Set Value
110 
111  /// Update the frustum test with a new frustum and matrix.
112  /// This should usually be called just once per frame, or however
113  /// often the camera moves.
114  void setFrustum (const Frustum<T>& frustum, const Matrix44<T>& cameraMat) IMATH_NOEXCEPT;
115 
116  /// @}
117 
118  /// @{
119  /// @name Query
120 
121  /// Return true if any part of the sphere is inside the frustum.
122  /// The result MAY return close false-positives, but not false-negatives.
123  bool isVisible (const Sphere3<T>& sphere) const IMATH_NOEXCEPT;
124 
125  /// Return true if any part of the box is inside the frustum.
126  /// The result MAY return close false-positives, but not false-negatives.
127  bool isVisible (const Box<Vec3<T>>& box) const IMATH_NOEXCEPT;
128 
129  /// Return true if the point is inside the frustum.
130  bool isVisible (const Vec3<T>& vec) const IMATH_NOEXCEPT;
131 
132  /// Return true if every part of the sphere is inside the frustum.
133  /// The result MAY return close false-negatives, but not false-positives.
134  bool completelyContains (const Sphere3<T>& sphere) const IMATH_NOEXCEPT;
135 
136  /// Return true if every part of the box is inside the frustum.
137  /// The result MAY return close false-negatives, but not false-positives.
138  bool completelyContains (const Box<Vec3<T>>& box) const IMATH_NOEXCEPT;
139 
140  /// Return the camera matrix (primarily for debugging)
141  IMATH_INTERNAL_NAMESPACE::Matrix44<T> cameraMat() const IMATH_NOEXCEPT { return cameraMatrix; }
142 
143  /// Return the viewing frustum (primarily for debugging)
144  IMATH_INTERNAL_NAMESPACE::Frustum<T> currentFrustum() const IMATH_NOEXCEPT { return currFrustum; }
145 
146  /// @}
147 
148  protected:
149 
150  // To understand why the planes are stored this way, see
151  // the SPECIAL NOTE above.
152 
153  /// @cond Doxygen_Suppress
154 
155  Vec3<T> planeNormX[2]; // The X components from 6 plane equations
156  Vec3<T> planeNormY[2]; // The Y components from 6 plane equations
157  Vec3<T> planeNormZ[2]; // The Z components from 6 plane equations
158 
159  Vec3<T> planeOffsetVec[2]; // The distance offsets from 6 plane equations
160 
161  // The absolute values are stored to assist with bounding box tests.
162  Vec3<T> planeNormAbsX[2]; // The abs(X) components from 6 plane equations
163  Vec3<T> planeNormAbsY[2]; // The abs(X) components from 6 plane equations
164  Vec3<T> planeNormAbsZ[2]; // The abs(X) components from 6 plane equations
165 
166  // These are kept primarily for debugging tools.
167  Frustum<T> currFrustum;
168  Matrix44<T> cameraMatrix;
169 
170  /// @endcond
171 };
172 
173 template <class T>
174 void
176 {
177  Plane3<T> frustumPlanes[6];
178  frustum.planes (frustumPlanes, cameraMat);
179 
180  // Here's where we effectively transpose the plane equations.
181  // We stuff all six X's into the two planeNormX vectors, etc.
182  for (int i = 0; i < 2; ++i)
183  {
184  int index = i * 3;
185 
186  planeNormX[i] = Vec3<T> (frustumPlanes[index + 0].normal.x,
187  frustumPlanes[index + 1].normal.x,
188  frustumPlanes[index + 2].normal.x);
189  planeNormY[i] = Vec3<T> (frustumPlanes[index + 0].normal.y,
190  frustumPlanes[index + 1].normal.y,
191  frustumPlanes[index + 2].normal.y);
192  planeNormZ[i] = Vec3<T> (frustumPlanes[index + 0].normal.z,
193  frustumPlanes[index + 1].normal.z,
194  frustumPlanes[index + 2].normal.z);
195 
196  planeNormAbsX[i] = Vec3<T> (std::abs (planeNormX[i].x),
197  std::abs (planeNormX[i].y),
198  std::abs (planeNormX[i].z));
199  planeNormAbsY[i] = Vec3<T> (std::abs (planeNormY[i].x),
200  std::abs (planeNormY[i].y),
201  std::abs (planeNormY[i].z));
202  planeNormAbsZ[i] = Vec3<T> (std::abs (planeNormZ[i].x),
203  std::abs (planeNormZ[i].y),
204  std::abs (planeNormZ[i].z));
205 
206  planeOffsetVec[i] = Vec3<T> (frustumPlanes[index + 0].distance,
207  frustumPlanes[index + 1].distance,
208  frustumPlanes[index + 2].distance);
209  }
210  currFrustum = frustum;
211  cameraMatrix = cameraMat;
212 }
213 
214 template <typename T>
215 bool
217 {
218  Vec3<T> center = sphere.center;
219  Vec3<T> radiusVec = Vec3<T> (sphere.radius, sphere.radius, sphere.radius);
220 
221  // This is a vertical dot-product on three vectors at once.
222  Vec3<T> d0 = planeNormX[0] * center.x + planeNormY[0] * center.y + planeNormZ[0] * center.z -
223  radiusVec - planeOffsetVec[0];
224 
225  if (d0.x >= 0 || d0.y >= 0 || d0.z >= 0)
226  return false;
227 
228  Vec3<T> d1 = planeNormX[1] * center.x + planeNormY[1] * center.y + planeNormZ[1] * center.z -
229  radiusVec - planeOffsetVec[1];
230 
231  if (d1.x >= 0 || d1.y >= 0 || d1.z >= 0)
232  return false;
233 
234  return true;
235 }
236 
237 template <typename T>
238 bool
240 {
241  Vec3<T> center = sphere.center;
242  Vec3<T> radiusVec = Vec3<T> (sphere.radius, sphere.radius, sphere.radius);
243 
244  // This is a vertical dot-product on three vectors at once.
245  Vec3<T> d0 = planeNormX[0] * center.x + planeNormY[0] * center.y + planeNormZ[0] * center.z +
246  radiusVec - planeOffsetVec[0];
247 
248  if (d0.x >= 0 || d0.y >= 0 || d0.z >= 0)
249  return false;
250 
251  Vec3<T> d1 = planeNormX[1] * center.x + planeNormY[1] * center.y + planeNormZ[1] * center.z +
252  radiusVec - planeOffsetVec[1];
253 
254  if (d1.x >= 0 || d1.y >= 0 || d1.z >= 0)
255  return false;
256 
257  return true;
258 }
259 
260 template <typename T>
261 bool
263 {
264  if (box.isEmpty())
265  return false;
266 
267  Vec3<T> center = (box.min + box.max) / 2;
268  Vec3<T> extent = (box.max - center);
269 
270  // This is a vertical dot-product on three vectors at once.
271  Vec3<T> d0 = planeNormX[0] * center.x + planeNormY[0] * center.y + planeNormZ[0] * center.z -
272  planeNormAbsX[0] * extent.x - planeNormAbsY[0] * extent.y -
273  planeNormAbsZ[0] * extent.z - planeOffsetVec[0];
274 
275  if (d0.x >= 0 || d0.y >= 0 || d0.z >= 0)
276  return false;
277 
278  Vec3<T> d1 = planeNormX[1] * center.x + planeNormY[1] * center.y + planeNormZ[1] * center.z -
279  planeNormAbsX[1] * extent.x - planeNormAbsY[1] * extent.y -
280  planeNormAbsZ[1] * extent.z - planeOffsetVec[1];
281 
282  if (d1.x >= 0 || d1.y >= 0 || d1.z >= 0)
283  return false;
284 
285  return true;
286 }
287 
288 template <typename T>
289 bool
291 {
292  if (box.isEmpty())
293  return false;
294 
295  Vec3<T> center = (box.min + box.max) / 2;
296  Vec3<T> extent = (box.max - center);
297 
298  // This is a vertical dot-product on three vectors at once.
299  Vec3<T> d0 = planeNormX[0] * center.x + planeNormY[0] * center.y + planeNormZ[0] * center.z +
300  planeNormAbsX[0] * extent.x + planeNormAbsY[0] * extent.y +
301  planeNormAbsZ[0] * extent.z - planeOffsetVec[0];
302 
303  if (d0.x >= 0 || d0.y >= 0 || d0.z >= 0)
304  return false;
305 
306  Vec3<T> d1 = planeNormX[1] * center.x + planeNormY[1] * center.y + planeNormZ[1] * center.z +
307  planeNormAbsX[1] * extent.x + planeNormAbsY[1] * extent.y +
308  planeNormAbsZ[1] * extent.z - planeOffsetVec[1];
309 
310  if (d1.x >= 0 || d1.y >= 0 || d1.z >= 0)
311  return false;
312 
313  return true;
314 }
315 
316 template <typename T>
317 bool
319 {
320  // This is a vertical dot-product on three vectors at once.
321  Vec3<T> d0 = (planeNormX[0] * vec.x) + (planeNormY[0] * vec.y) + (planeNormZ[0] * vec.z) -
322  planeOffsetVec[0];
323 
324  if (d0.x >= 0 || d0.y >= 0 || d0.z >= 0)
325  return false;
326 
327  Vec3<T> d1 = (planeNormX[1] * vec.x) + (planeNormY[1] * vec.y) + (planeNormZ[1] * vec.z) -
328  planeOffsetVec[1];
329 
330  if (d1.x >= 0 || d1.y >= 0 || d1.z >= 0)
331  return false;
332 
333  return true;
334 }
335 
336 /// FrustymTest of type float
338 
339 /// FrustymTest of type double
341 
342 IMATH_INTERNAL_NAMESPACE_HEADER_EXIT
343 
344 #endif // INCLUDED_IMATHFRUSTUMTEST_H
GLint GLenum GLsizei GLsizei GLsizei GLsizei extent
Definition: glew.h:15877
T z
Definition: ImathVec.h:310
#define IMATH_NOEXCEPT
Definition: ImathConfig.h:72
#define IMATH_INTERNAL_NAMESPACE
Definition: ImathConfig.h:36
Definition: ImathVec.h:32
IMATH_INTERNAL_NAMESPACE::Frustum< T > currentFrustum() const IMATH_NOEXCEPT
Return the viewing frustum (primarily for debugging)
FrustumTest< float > FrustumTestf
FrustymTest of type float.
T distance
The distance from the origin to the plane.
Definition: ImathPlane.h:42
GLint GLenum GLint x
Definition: glcorearb.h:409
FrustumTest() IMATH_NOEXCEPT
Initialize camera matrix to identity.
T x
Definition: ImathVec.h:310
FrustumTest(const Frustum< T > &frustum, const Matrix44< T > &cameraMat) IMATH_NOEXCEPT
Initialize to a given frustum and camera matrix.
GLdouble GLdouble GLdouble z
Definition: glcorearb.h:848
bool isVisible(const Sphere3< T > &sphere) const IMATH_NOEXCEPT
GLsizei const GLint box[]
Definition: glew.h:11654
FrustumTest< double > FrustumTestd
FrustymTest of type double.
GLuint index
Definition: glcorearb.h:786
#define IMATH_EXPORT_TEMPLATE_TYPE
Definition: ImathExport.h:60
T y
Definition: ImathVec.h:310
IMATH_INTERNAL_NAMESPACE_HEADER_ENTER IMATH_HOSTDEVICE constexpr T abs(T a) IMATH_NOEXCEPT
Definition: ImathFun.h:26
Definition: ImathBox.h:37
bool completelyContains(const Sphere3< T > &sphere) const IMATH_NOEXCEPT
#define const
Definition: zconf.h:214
Vec3< T > normal
The normal to the plane.
Definition: ImathPlane.h:39
GLint y
Definition: glcorearb.h:103
IMATH_HOSTDEVICE void makeIdentity() IMATH_NOEXCEPT
Set to the identity matrix.
Definition: ImathMatrix.h:3274
void setFrustum(const Frustum< T > &frustum, const Matrix44< T > &cameraMat) IMATH_NOEXCEPT