1 /////////////////////////////////////////////////////////////////////////// 2 // 3 // Copyright (c) 2011, 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 54 namespace Imath { 55 56 ///////////////////////////////////////////////////////////////// 57 // FrustumTest 58 // 59 // template class FrustumTest<T> 60 // 61 // This is a helper class, designed to accelerate the case 62 // where many tests are made against the same frustum. 63 // That's a really common case. 64 // 65 // The acceleration is achieved by pre-computing the planes of 66 // the frustum, along with the ablsolute values of the plane normals. 67 // 68 69 70 71 ////////////////////////////////////////////////////////////////// 72 // How to use this 73 // 74 // Given that you already have: 75 // Imath::Frustum myFrustum 76 // IMath::Matrix44 myCameraWorldMatrix 77 // 78 // First, make a frustum test object: 79 // FrustumTest myFrustumTest(myFrustum, myCameraWorldMatrix) 80 // 81 // Whenever the camera or frustum changes, call: 82 // myFrustumTest.setFrustum(myFrustum, myCameraWorldMatrix) 83 // 84 // For each object you want to test for visibility, call: 85 // myFrustumTest.isVisible(myBox) 86 // myFrustumTest.isVisible(mySphere) 87 // myFrustumTest.isVisible(myVec3) 88 // myFrustumTest.completelyContains(myBox) 89 // myFrustumTest.completelyContains(mySphere) 90 // 91 92 93 94 95 ////////////////////////////////////////////////////////////////// 96 // Explanation of how it works 97 // 98 // 99 // We store six world-space Frustum planes (nx, ny, nz, offset) 100 // 101 // Points: To test a Vec3 for visibility, test it against each plane 102 // using the normal (v dot n - offset) method. (the result is exact) 103 // 104 // BBoxes: To test an axis-aligned bbox, test the center against each plane 105 // using the normal (v dot n - offset) method, but offset by the 106 // box extents dot the abs of the plane normal. (the result is NOT 107 // exact, but will not return false-negatives.) 108 // 109 // Spheres: To test a sphere, test the center against each plane 110 // using the normal (v dot n - offset) method, but offset by the 111 // sphere's radius. (the result is NOT exact, but will not return 112 // false-negatives.) 113 // 114 // 115 // SPECIAL NOTE: "Where are the dot products?" 116 // Actual dot products are currently slow for most SIMD architectures. 117 // In order to keep this code optimization-ready, the dot products 118 // are all performed using vector adds and multipies. 119 // 120 // In order to do this, the plane equations are stored in "transpose" 121 // form, with the X components grouped into an X vector, etc. 122 // 123 124 125 template <class T> 126 class FrustumTest 127 { 128 public: 129 FrustumTest() 130 { 131 Frustum<T> frust; 132 Matrix44<T> cameraMat; 133 cameraMat.makeIdentity(); 134 setFrustum(frust, cameraMat); 135 } 136 FrustumTest(Frustum<T> &frustum, const Matrix44<T> &cameraMat) 137 { 138 setFrustum(frustum, cameraMat); 139 } 140 141 //////////////////////////////////////////////////////////////////// 142 // setFrustum() 143 // This updates the frustum test with a new frustum and matrix. 144 // This should usually be called just once per frame. 145 void setFrustum(Frustum<T> &frustum, const Matrix44<T> &cameraMat); 146 147 //////////////////////////////////////////////////////////////////// 148 // isVisible() 149 // Check to see if shapes are visible. 150 bool isVisible(const Sphere3<T> &sphere) const; 151 bool isVisible(const Box<Vec3<T> > &box) const; 152 bool isVisible(const Vec3<T> &vec) const; 153 154 //////////////////////////////////////////////////////////////////// 155 // completelyContains() 156 // Check to see if shapes are entirely contained. 157 bool completelyContains(const Sphere3<T> &sphere) const; 158 bool completelyContains(const Box<Vec3<T> > &box) const; 159 160 // These next items are kept primarily for debugging tools. 161 // It's useful for drawing the culling environment, and also 162 // for getting an "outside view" of the culling frustum. 163 Imath::Matrix44<T> cameraMat() const {return cameraMatrix;} 164 Imath::Frustum<T> currentFrustum() const {return currFrustum;} 165 166 protected: 167 // To understand why the planes are stored this way, see 168 // the SPECIAL NOTE above. 169 Vec3<T> planeNormX[2]; // The X compunents from 6 plane equations 170 Vec3<T> planeNormY[2]; // The Y compunents from 6 plane equations 171 Vec3<T> planeNormZ[2]; // The Z compunents from 6 plane equations 172 173 Vec3<T> planeOffsetVec[2]; // The distance offsets from 6 plane equations 174 175 // The absolute values are stored to assist with bounding box tests. 176 Vec3<T> planeNormAbsX[2]; // The abs(X) compunents from 6 plane equations 177 Vec3<T> planeNormAbsY[2]; // The abs(X) compunents from 6 plane equations 178 Vec3<T> planeNormAbsZ[2]; // The abs(X) compunents from 6 plane equations 179 180 // These are kept primarily for debugging tools. 181 Frustum<T> currFrustum; 182 Matrix44<T> cameraMatrix; 183 }; 184 185 186 //////////////////////////////////////////////////////////////////// 187 // setFrustum() 188 // This should usually only be called once per frame, or however 189 // often the camera moves. 190 template<class T> 191 void FrustumTest<T>::setFrustum(Frustum<T> &frustum, 192 const Matrix44<T> &cameraMat) 193 { 194 Plane3<T> frustumPlanes[6]; 195 frustum.planes(frustumPlanes, cameraMat); 196 197 // Here's where we effectively transpose the plane equations. 198 // We stuff all six X's into the two planeNormX vectors, etc. 199 for (int i = 0; i < 2; ++i) 200 { 201 int index = i * 3; 202 203 planeNormX[i] = Vec3<T>(frustumPlanes[index + 0].normal.x, 204 frustumPlanes[index + 1].normal.x, 205 frustumPlanes[index + 2].normal.x); 206 planeNormY[i] = Vec3<T>(frustumPlanes[index + 0].normal.y, 207 frustumPlanes[index + 1].normal.y, 208 frustumPlanes[index + 2].normal.y); 209 planeNormZ[i] = Vec3<T>(frustumPlanes[index + 0].normal.z, 210 frustumPlanes[index + 1].normal.z, 211 frustumPlanes[index + 2].normal.z); 212 213 planeNormAbsX[i] = Vec3<T>(Imath::abs(planeNormX[i].x), 214 Imath::abs(planeNormX[i].y), 215 Imath::abs(planeNormX[i].z)); 216 planeNormAbsY[i] = Vec3<T>(Imath::abs(planeNormY[i].x), 217 Imath::abs(planeNormY[i].y), 218 Imath::abs(planeNormY[i].z)); 219 planeNormAbsZ[i] = Vec3<T>(Imath::abs(planeNormZ[i].x), 220 Imath::abs(planeNormZ[i].y), 221 Imath::abs(planeNormZ[i].z)); 222 223 planeOffsetVec[i] = Vec3<T>(frustumPlanes[index + 0].distance, 224 frustumPlanes[index + 1].distance, 225 frustumPlanes[index + 2].distance); 226 } 227 currFrustum = frustum; 228 cameraMatrix = cameraMat; 229 } 230 231 232 //////////////////////////////////////////////////////////////////// 233 // isVisible(Sphere) 234 // Returns true if any part of the sphere is inside 235 // the frustum. 236 // The result MAY return close false-positives, but not false-negatives. 237 // 238 template<typename T> 239 bool FrustumTest<T>::isVisible(const Sphere3<T> &sphere) const 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 246 + planeNormY[0] * center.y 247 + planeNormZ[0] * center.z 248 - radiusVec 249 - planeOffsetVec[0]; 250 251 if (d0.x >= 0 || d0.y >= 0 || d0.z >= 0) 252 return false; 253 254 Vec3<T> d1 = planeNormX[1] * center.x 255 + planeNormY[1] * center.y 256 + planeNormZ[1] * center.z 257 - radiusVec 258 - planeOffsetVec[1]; 259 260 if (d1.x >= 0 || d1.y >= 0 || d1.z >= 0) 261 return false; 262 263 return true; 264 } 265 266 //////////////////////////////////////////////////////////////////// 267 // completelyContains(Sphere) 268 // Returns true if every part of the sphere is inside 269 // the frustum. 270 // The result MAY return close false-negatives, but not false-positives. 271 // 272 template<typename T> 273 bool FrustumTest<T>::completelyContains(const Sphere3<T> &sphere) const 274 { 275 Vec3<T> center = sphere.center; 276 Vec3<T> radiusVec = Vec3<T>(sphere.radius, sphere.radius, sphere.radius); 277 278 // This is a vertical dot-product on three vectors at once. 279 Vec3<T> d0 = planeNormX[0] * center.x 280 + planeNormY[0] * center.y 281 + planeNormZ[0] * center.z 282 + radiusVec 283 - planeOffsetVec[0]; 284 285 if (d0.x >= 0 || d0.y >= 0 || d0.z >= 0) 286 return false; 287 288 Vec3<T> d1 = planeNormX[1] * center.x 289 + planeNormY[1] * center.y 290 + planeNormZ[1] * center.z 291 + radiusVec 292 - planeOffsetVec[1]; 293 294 if (d1.x >= 0 || d1.y >= 0 || d1.z >= 0) 295 return false; 296 297 return true; 298 } 299 300 //////////////////////////////////////////////////////////////////// 301 // isVisible(Box) 302 // Returns true if any part of the axis-aligned box 303 // is inside the frustum. 304 // The result MAY return close false-positives, but not false-negatives. 305 // 306 template<typename T> 307 bool FrustumTest<T>::isVisible(const Box<Vec3<T> > &box) const 308 { 309 Vec3<T> center = (box.min + box.max) / 2; 310 Vec3<T> extent = (box.max - center); 311 312 // This is a vertical dot-product on three vectors at once. 313 Vec3<T> d0 = planeNormX[0] * center.x 314 + planeNormY[0] * center.y 315 + planeNormZ[0] * center.z 316 - planeNormAbsX[0] * extent.x 317 - planeNormAbsY[0] * extent.y 318 - planeNormAbsZ[0] * extent.z 319 - planeOffsetVec[0]; 320 321 if (d0.x >= 0 || d0.y >= 0 || d0.z >= 0) 322 return false; 323 324 Vec3<T> d1 = planeNormX[1] * center.x 325 + planeNormY[1] * center.y 326 + planeNormZ[1] * center.z 327 - planeNormAbsX[1] * extent.x 328 - planeNormAbsY[1] * extent.y 329 - planeNormAbsZ[1] * extent.z 330 - planeOffsetVec[1]; 331 332 if (d1.x >= 0 || d1.y >= 0 || d1.z >= 0) 333 return false; 334 335 return true; 336 } 337 338 //////////////////////////////////////////////////////////////////// 339 // completelyContains(Box) 340 // Returns true if every part of the axis-aligned box 341 // is inside the frustum. 342 // The result MAY return close false-negatives, but not false-positives. 343 // 344 template<typename T> 345 bool FrustumTest<T>::completelyContains(const Box<Vec3<T> > &box) const 346 { 347 Vec3<T> center = (box.min + box.max) / 2; 348 Vec3<T> extent = (box.max - center); 349 350 // This is a vertical dot-product on three vectors at once. 351 Vec3<T> d0 = planeNormX[0] * center.x 352 + planeNormY[0] * center.y 353 + planeNormZ[0] * center.z 354 + planeNormAbsX[0] * extent.x 355 + planeNormAbsY[0] * extent.y 356 + planeNormAbsZ[0] * extent.z 357 - planeOffsetVec[0]; 358 359 if (d0.x >= 0 || d0.y >= 0 || d0.z >= 0) 360 return false; 361 362 Vec3<T> d1 = planeNormX[1] * center.x 363 + planeNormY[1] * center.y 364 + planeNormZ[1] * center.z 365 + planeNormAbsX[1] * extent.x 366 + planeNormAbsY[1] * extent.y 367 + planeNormAbsZ[1] * extent.z 368 - planeOffsetVec[1]; 369 370 if (d1.x >= 0 || d1.y >= 0 || d1.z >= 0) 371 return false; 372 373 return true; 374 } 375 376 377 //////////////////////////////////////////////////////////////////// 378 // isVisible(Vec3) 379 // Returns true if the point is inside the frustum. 380 // 381 template<typename T> 382 bool FrustumTest<T>::isVisible(const Vec3<T> &vec) const 383 { 384 // This is a vertical dot-product on three vectors at once. 385 Vec3<T> d0 = (planeNormX[0] * vec.x) 386 + (planeNormY[0] * vec.y) 387 + (planeNormZ[0] * vec.z) 388 - planeOffsetVec[0]; 389 390 if (d0.x >= 0 || d0.y >= 0 || d0.z >= 0) 391 return false; 392 393 Vec3<T> d1 = (planeNormX[1] * vec.x) 394 + (planeNormY[1] * vec.y) 395 + (planeNormZ[1] * vec.z) 396 - planeOffsetVec[1]; 397 398 if (d1.x >= 0 || d1.y >= 0 || d1.z >= 0) 399 return false; 400 401 return true; 402 } 403 404 405 typedef FrustumTest<float> FrustumTestf; 406 typedef FrustumTest<double> FrustumTestd; 407 408 } //namespace Imath 409 410 #endif 411