Debian Codegraph @

src/Imath/ImathFrustumTest.h

raw
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
92 FrustumTest() IMATH_NOEXCEPT
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
175 FrustumTest<T>::setFrustum (const Frustum<T>& frustum, const Matrix44<T>& cameraMat) IMATH_NOEXCEPT
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
216 FrustumTest<T>::isVisible (const Sphere3<T>& sphere) const IMATH_NOEXCEPT
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
239 FrustumTest<T>::completelyContains (const Sphere3<T>& sphere) const IMATH_NOEXCEPT
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
262 FrustumTest<T>::isVisible (const Box<Vec3<T>>& box) const IMATH_NOEXCEPT
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
290 FrustumTest<T>::completelyContains (const Box<Vec3<T>>& box) const IMATH_NOEXCEPT
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
318 FrustumTest<T>::isVisible (const Vec3<T>& vec) const IMATH_NOEXCEPT
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
337 typedef FrustumTest<float> FrustumTestf;
338
339 /// FrustymTest of type double
340 typedef FrustumTest<double> FrustumTestd;
341
342 IMATH_INTERNAL_NAMESPACE_HEADER_EXIT
343
344 #endif // INCLUDED_IMATHFRUSTUMTEST_H