1 /* 2 ----------------------------------------------------------------------------- 3 This source file is part of OGRE 4 (Object-oriented Graphics Rendering Engine) 5 For the latest info, see http://www.ogre3d.org/ 6 7 Copyright (c) 2000-2013 Torus Knot Software Ltd 8 9 Permission is hereby granted, free of charge, to any person obtaining a copy 10 of this software and associated documentation files (the "Software"), to deal 11 in the Software without restriction, including without limitation the rights 12 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 13 copies of the Software, and to permit persons to whom the Software is 14 furnished to do so, subject to the following conditions: 15 16 The above copyright notice and this permission notice shall be included in 17 all copies or substantial portions of the Software. 18 19 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 20 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 21 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 22 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 23 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 24 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 25 THE SOFTWARE. 26 ----------------------------------------------------------------------------- 27 OgrePCZFrustum.cpp - PCZ Supplemental culling Frustum 28 29 This isn't really a traditional "frustum", but more a collection of 30 extra culling planes used by the PCZ Scene Manager for supplementing 31 the camera culling and light zone culling by creating extra culling 32 planes from visible portals. Since portals are 4 sided, the extra 33 culling planes tend to form frustums (pyramids) but nothing in the 34 code really assumes that the culling planes are frustums. They are 35 just treated as planes. 36 37 The "originPlane" is a culling plane which passes through the origin 38 point specified. It is used to cull portals which are close to, but 39 behind the camera view. (the nature of the culling routine doesn't 40 give correct results if you just use the "near" plane of the standard 41 camera frustum (unless that near plane distance is 0.0, but that is 42 highly not recommended for other reasons having to do with having a 43 legal view frustum). 44 45 ----------------------------------------------------------------------------- 46 begin : Tue May 29 2007 47 author : Eric Cha 48 email : ericc@xenopi.com 49 ----------------------------------------------------------------------------- 50 */ 51 52 #include "OgrePCZFrustum.h" 53 #include "OgreAntiPortal.h" 54 #include "OgrePortal.h" 55 56 namespace Ogre 57 { 58 PCZFrustum()59 PCZFrustum::PCZFrustum() : 60 mUseOriginPlane(false), mProjType(PT_PERSPECTIVE) 61 { } 62 ~PCZFrustum()63 PCZFrustum::~PCZFrustum() 64 { 65 removeAllCullingPlanes(); 66 // clear out the culling plane reservoir 67 PCPlaneList::iterator pit = mCullingPlaneReservoir.begin(); 68 while ( pit != mCullingPlaneReservoir.end() ) 69 { 70 PCPlane * plane = *pit; 71 // go to next entry 72 pit++; 73 //delete the entry in the list 74 OGRE_DELETE_T(plane, PCPlane, MEMCATEGORY_SCENE_CONTROL); 75 } 76 mCullingPlaneReservoir.clear(); 77 } 78 isVisible(const AxisAlignedBox & bound) const79 bool PCZFrustum::isVisible( const AxisAlignedBox & bound) const 80 { 81 // Null boxes are always invisible 82 if (bound.isNull()) return false; 83 84 // Infinite boxes are always visible 85 if (bound.isInfinite()) return true; 86 87 // Get centre of the box 88 Vector3 centre = bound.getCenter(); 89 // Get the half-size of the box 90 Vector3 halfSize = bound.getHalfSize(); 91 92 // Check originplane if told to 93 if (mUseOriginPlane) 94 { 95 Plane::Side side = mOriginPlane.getSide(centre, halfSize); 96 if (side == Plane::NEGATIVE_SIDE) 97 { 98 return false; 99 } 100 } 101 102 // For each extra active culling plane, see if the entire aabb is on the negative side 103 // If so, object is not visible 104 PCPlaneList::const_iterator pit = mActiveCullingPlanes.begin(); 105 while ( pit != mActiveCullingPlanes.end() ) 106 { 107 PCPlane * plane = *pit; 108 Plane::Side xside = plane->getSide(centre, halfSize); 109 if (xside == Plane::NEGATIVE_SIDE) 110 { 111 return false; 112 } 113 pit++; 114 } 115 return true; 116 } 117 isVisible(const Sphere & bound) const118 bool PCZFrustum::isVisible( const Sphere & bound) const 119 { 120 // Check originplane if told to 121 if (mUseOriginPlane) 122 { 123 Plane::Side side = mOriginPlane.getSide(bound.getCenter()); 124 if (side == Plane::NEGATIVE_SIDE) 125 { 126 Real dist = mOriginPlane.getDistance(bound.getCenter()); 127 if (dist > bound.getRadius()) 128 { 129 return false; 130 } 131 } 132 } 133 134 // For each extra active culling plane, see if the entire sphere is on the negative side 135 // If so, object is not visible 136 PCPlaneList::const_iterator pit = mActiveCullingPlanes.begin(); 137 while ( pit != mActiveCullingPlanes.end() ) 138 { 139 PCPlane * plane = *pit; 140 Plane::Side xside = plane->getSide(bound.getCenter()); 141 if (xside == Plane::NEGATIVE_SIDE) 142 { 143 Real dist = plane->getDistance(bound.getCenter()); 144 if (dist > bound.getRadius()) 145 { 146 return false; 147 } 148 } 149 pit++; 150 } 151 return true; 152 } 153 154 /* isVisible() function for portals */ 155 // NOTE: Everything needs to be updated spatially before this function is 156 // called including portal corners, frustum planes, etc. isVisible(const PortalBase * portal) const157 bool PCZFrustum::isVisible(const PortalBase* portal) const 158 { 159 // if portal isn't enabled, it's not visible 160 if (!portal->getEnabled()) return false; 161 162 // if the frustum has no planes, just return true 163 if (mActiveCullingPlanes.empty()) 164 { 165 return true; 166 } 167 // check if this portal is already in the list of active culling planes (avoid 168 // infinite recursion case) 169 PCPlaneList::const_iterator pit = mActiveCullingPlanes.begin(); 170 while ( pit != mActiveCullingPlanes.end() ) 171 { 172 PCPlane * plane = *pit; 173 if (plane->getPortal() == portal) 174 { 175 return false; 176 } 177 pit++; 178 } 179 // if portal is of type AABB or Sphere, then use simple bound check against planes 180 if (portal->getType() == PortalBase::PORTAL_TYPE_AABB) 181 { 182 AxisAlignedBox aabb; 183 aabb.setExtents(portal->getDerivedCorner(0), portal->getDerivedCorner(1)); 184 return isVisible(aabb); 185 } 186 else if (portal->getType() == PortalBase::PORTAL_TYPE_SPHERE) 187 { 188 return isVisible(portal->getDerivedSphere()); 189 } 190 191 // only do this check if it's a portal. (anti portal doesn't care about facing) 192 if (portal->getTypeFlags() == PortalFactory::FACTORY_TYPE_FLAG) 193 { 194 // check if the portal norm is facing the frustum 195 Vector3 frustumToPortal = portal->getDerivedCP() - mOrigin; 196 Vector3 portalDirection = portal->getDerivedDirection(); 197 Real dotProduct = frustumToPortal.dotProduct(portalDirection); 198 if ( dotProduct > 0 ) 199 { 200 // portal is faced away from Frustum 201 return false; 202 } 203 } 204 205 // check against frustum culling planes 206 bool visible_flag; 207 208 // Check originPlane if told to 209 if (mUseOriginPlane) 210 { 211 // set the visible flag to false 212 visible_flag = false; 213 // we have to check each corner of the portal 214 for (int corner = 0; corner < 4; corner++) 215 { 216 Plane::Side side = mOriginPlane.getSide(portal->getDerivedCorner(corner)); 217 if (side != Plane::NEGATIVE_SIDE) 218 { 219 visible_flag = true; 220 break; 221 } 222 } 223 // if the visible_flag is still false, then the origin plane 224 // culled all the portal points 225 if (visible_flag == false) 226 { 227 // ALL corners on negative side therefore out of view 228 return false; 229 } 230 } 231 232 // For each active culling plane, see if all portal points are on the negative 233 // side. If so, the portal is not visible 234 pit = mActiveCullingPlanes.begin(); 235 while ( pit != mActiveCullingPlanes.end() ) 236 { 237 PCPlane * plane = *pit; 238 // set the visible flag to false 239 visible_flag = false; 240 // we have to check each corner of the portal 241 for (int corner = 0; corner < 4; corner++) 242 { 243 Plane::Side side =plane->getSide(portal->getDerivedCorner(corner)); 244 if (side != Plane::NEGATIVE_SIDE) 245 { 246 visible_flag = true; 247 break; 248 } 249 } 250 // if the visible_flag is still false, then this plane 251 // culled all the portal points 252 if (visible_flag == false) 253 { 254 // ALL corners on negative side therefore out of view 255 return false; 256 } 257 pit++; 258 } 259 // no plane culled all the portal points and the norm 260 // was facing the frustum, so this portal is visible 261 return true; 262 263 } 264 265 /* special function that returns true only when aabb fully fits inside the frustum. */ isFullyVisible(const AxisAlignedBox & bound) const266 bool PCZFrustum::isFullyVisible(const AxisAlignedBox& bound) const 267 { 268 // Null boxes are always invisible 269 if (bound.isNull()) return false; 270 271 // Infinite boxes are never fully visible 272 if (bound.isInfinite()) return false; 273 274 // Get centre of the box 275 Vector3 centre = bound.getCenter(); 276 // Get the half-size of the box 277 Vector3 halfSize = bound.getHalfSize(); 278 279 // Check originplane if told to 280 if (mUseOriginPlane) 281 { 282 Plane::Side side = mOriginPlane.getSide(centre, halfSize); 283 if (side != Plane::POSITIVE_SIDE) return false; 284 } 285 286 // For each extra active culling plane, 287 // see if the aabb is not on the positive side 288 // If so, object is not fully visible 289 PCPlaneList::const_iterator pit = mActiveCullingPlanes.begin(); 290 while ( pit != mActiveCullingPlanes.end() ) 291 { 292 PCPlane * plane = *pit; 293 Plane::Side xside = plane->getSide(centre, halfSize); 294 if (xside != Plane::POSITIVE_SIDE) 295 { 296 return false; 297 } 298 pit++; 299 } 300 return true; 301 } 302 303 /* special function that returns true only when sphere fully fits inside the frustum. */ isFullyVisible(const Sphere & bound) const304 bool PCZFrustum::isFullyVisible(const Sphere& bound) const 305 { 306 // Check originplane if told to 307 if (mUseOriginPlane) 308 { 309 if (mOriginPlane.getDistance(bound.getCenter()) <= bound.getRadius() || 310 mOriginPlane.getSide(bound.getCenter()) != Plane::POSITIVE_SIDE) 311 { 312 return false; 313 } 314 } 315 316 // For each extra active culling plane, 317 // see if the sphere is not on the positive side 318 // If so, object is not fully visible 319 PCPlaneList::const_iterator pit = mActiveCullingPlanes.begin(); 320 while ( pit != mActiveCullingPlanes.end() ) 321 { 322 PCPlane* plane = *pit; 323 324 if (plane->getDistance(bound.getCenter()) <= bound.getRadius() || 325 plane->getSide(bound.getCenter()) != Plane::POSITIVE_SIDE) 326 { 327 return false; 328 } 329 330 pit++; 331 } 332 return true; 333 } 334 335 /* special function that returns true only when portal fully fits inside the frustum. */ isFullyVisible(const PortalBase * portal) const336 bool PCZFrustum::isFullyVisible(const PortalBase* portal) const 337 { 338 // if portal isn't enabled, it's not visible 339 if (!portal->getEnabled()) return false; 340 341 // if the frustum has no planes, just return true 342 if (mActiveCullingPlanes.empty()) 343 { 344 return true; 345 } 346 // check if this portal is already in the list of active culling planes (avoid 347 // infinite recursion case) 348 PCPlaneList::const_iterator pit = mActiveCullingPlanes.begin(); 349 while ( pit != mActiveCullingPlanes.end() ) 350 { 351 PCPlane * plane = *pit; 352 if (plane->getPortal() == portal) 353 { 354 return false; 355 } 356 pit++; 357 } 358 // if portal is of type AABB or Sphere, then use simple bound check against planes 359 if (portal->getType() == PortalBase::PORTAL_TYPE_AABB) 360 { 361 AxisAlignedBox aabb; 362 aabb.setExtents(portal->getDerivedCorner(0), portal->getDerivedCorner(1)); 363 return isFullyVisible(aabb); 364 } 365 else if (portal->getType() == PortalBase::PORTAL_TYPE_SPHERE) 366 { 367 return isFullyVisible(portal->getDerivedSphere()); 368 } 369 370 // only do this check if it's a portal. (anti portal doesn't care about facing) 371 if (portal->getTypeFlags() == PortalFactory::FACTORY_TYPE_FLAG) 372 { 373 // check if the portal norm is facing the frustum 374 Vector3 frustumToPortal = portal->getDerivedCP() - mOrigin; 375 Vector3 portalDirection = portal->getDerivedDirection(); 376 Real dotProduct = frustumToPortal.dotProduct(portalDirection); 377 if ( dotProduct > 0 ) 378 { 379 // portal is faced away from Frustum 380 return false; 381 } 382 } 383 384 // Check originPlane if told to 385 if (mUseOriginPlane) 386 { 387 // we have to check each corner of the portal 388 for (int corner = 0; corner < 4; corner++) 389 { 390 Plane::Side side = mOriginPlane.getSide(portal->getDerivedCorner(corner)); 391 if (side == Plane::NEGATIVE_SIDE) return false; 392 } 393 } 394 395 // For each active culling plane, see if any portal points are on the negative 396 // side. If so, the portal is not fully visible 397 pit = mActiveCullingPlanes.begin(); 398 while ( pit != mActiveCullingPlanes.end() ) 399 { 400 PCPlane * plane = *pit; 401 // we have to check each corner of the portal 402 for (int corner = 0; corner < 4; corner++) 403 { 404 Plane::Side side =plane->getSide(portal->getDerivedCorner(corner)); 405 if (side == Plane::NEGATIVE_SIDE) return false; 406 } 407 pit++; 408 } 409 // no plane culled all the portal points and the norm 410 // was facing the frustum, so this portal is fully visible 411 return true; 412 } 413 414 /* A 'more detailed' check for visibility of an AAB. This function returns 415 none, partial, or full for visibility of the box. This is useful for 416 stuff like Octree leaf culling */ getVisibility(const AxisAlignedBox & bound)417 PCZFrustum::Visibility PCZFrustum::getVisibility( const AxisAlignedBox &bound ) 418 { 419 420 // Null boxes always invisible 421 if ( bound.isNull() ) 422 return NONE; 423 424 // Get centre of the box 425 Vector3 centre = bound.getCenter(); 426 // Get the half-size of the box 427 Vector3 halfSize = bound.getHalfSize(); 428 429 bool all_inside = true; 430 431 // Check originplane if told to 432 if (mUseOriginPlane) 433 { 434 Plane::Side side = mOriginPlane.getSide(centre, halfSize); 435 if (side == Plane::NEGATIVE_SIDE) 436 { 437 return NONE; 438 } 439 // We can't return now as the box could be later on the negative side of another plane. 440 if(side == Plane::BOTH_SIDE) 441 { 442 all_inside = false; 443 } 444 } 445 446 // For each active culling plane, see if the entire aabb is on the negative side 447 // If so, object is not visible 448 PCPlaneList::iterator pit = mActiveCullingPlanes.begin(); 449 while ( pit != mActiveCullingPlanes.end() ) 450 { 451 PCPlane * plane = *pit; 452 Plane::Side xside = plane->getSide(centre, halfSize); 453 if(xside == Plane::NEGATIVE_SIDE) 454 { 455 return NONE; 456 } 457 // We can't return now as the box could be later on the negative side of a plane. 458 if(xside == Plane::BOTH_SIDE) 459 { 460 all_inside = false; 461 break; 462 } 463 pit++; 464 } 465 466 if ( all_inside ) 467 return FULL; 468 else 469 return PARTIAL; 470 471 } 472 473 // calculate culling planes from portal and frustum 474 // origin and add to list of culling planes 475 // NOTE: returns 0 if portal was completely culled by existing planes 476 // returns > 0 if culling planes are added (# is planes added) addPortalCullingPlanes(PortalBase * portal)477 int PCZFrustum::addPortalCullingPlanes(PortalBase* portal) 478 { 479 int addedcullingplanes = 0; 480 481 // If portal is of type aabb or sphere, add a plane which is same as frustum 482 // origin plane (ie. redundant). We do this because we need the plane as a flag 483 // to prevent infinite recursion 484 if (portal->getType() == PortalBase::PORTAL_TYPE_AABB || 485 portal->getType() == PortalBase::PORTAL_TYPE_SPHERE) 486 { 487 PCPlane * newPlane = getUnusedCullingPlane(); 488 newPlane->setFromOgrePlane(mOriginPlane); 489 newPlane->setPortal(portal); 490 mActiveCullingPlanes.push_front(newPlane); 491 addedcullingplanes++; 492 return addedcullingplanes; 493 } 494 495 // only do this check if it's an anti portal since it's double facing. 496 bool flipPlane = false; 497 if (portal->getTypeFlags() == AntiPortalFactory::FACTORY_TYPE_FLAG) 498 { 499 // check if the portal norm is facing the frustum 500 Vector3 frustumToPortal = portal->getDerivedCP() - mOrigin; 501 Vector3 portalDirection = portal->getDerivedDirection(); 502 Real dotProduct = frustumToPortal.dotProduct(portalDirection); 503 504 // it's facing away from the frustum. Flip the planes. 505 if (dotProduct > 0) flipPlane = true; 506 } 507 508 // For portal Quads: Up to 4 planes can be added by the sides of a portal quad. 509 // Each plane is created from 2 corners (world space) of the portal and the 510 // frustum origin (world space). 511 int i,j; 512 Plane::Side pt0_side, pt1_side; 513 bool visible; 514 PCPlaneList::iterator pit; 515 for (i=0;i<4;i++) 516 { 517 // first check if both corners are outside of one of the existing planes 518 j = i+1; 519 if (j > 3) 520 { 521 j = 0; 522 } 523 visible = true; 524 pit = mActiveCullingPlanes.begin(); 525 while ( pit != mActiveCullingPlanes.end() ) 526 { 527 PCPlane * plane = *pit; 528 pt0_side = plane->getSide(portal->getDerivedCorner(i)); 529 pt1_side = plane->getSide(portal->getDerivedCorner(j)); 530 if (pt0_side == Plane::NEGATIVE_SIDE && 531 pt1_side == Plane::NEGATIVE_SIDE) 532 { 533 // the portal edge was actually completely culled by one of culling planes 534 visible = false; 535 break; 536 } 537 pit++; 538 } 539 if (visible) 540 { 541 // add the plane created from the two portal corner points and the frustum location 542 // to the culling plane 543 PCPlane * newPlane = getUnusedCullingPlane(); 544 if (mProjType == PT_ORTHOGRAPHIC) // use camera direction if projection is orthographic. 545 { 546 if (flipPlane) 547 { 548 newPlane->redefine(portal->getDerivedCorner(j) + mOriginPlane.normal, 549 portal->getDerivedCorner(i), portal->getDerivedCorner(j)); 550 } 551 else 552 { 553 newPlane->redefine(portal->getDerivedCorner(j) + mOriginPlane.normal, 554 portal->getDerivedCorner(j), portal->getDerivedCorner(i)); 555 } 556 } 557 else 558 { 559 if (flipPlane) 560 { 561 newPlane->redefine(mOrigin, 562 portal->getDerivedCorner(i), 563 portal->getDerivedCorner(j)); 564 } 565 else 566 { 567 newPlane->redefine(mOrigin, 568 portal->getDerivedCorner(j), 569 portal->getDerivedCorner(i)); 570 } 571 } 572 newPlane->setPortal(portal); 573 mActiveCullingPlanes.push_front(newPlane); 574 addedcullingplanes++; 575 } 576 } 577 // if we added ANY planes from the quad portal, we should add the plane of the 578 // portal itself as an additional culling plane. 579 if (addedcullingplanes > 0) 580 { 581 PCPlane * newPlane = getUnusedCullingPlane(); 582 583 if (flipPlane) 584 { 585 newPlane->redefine( 586 portal->getDerivedCorner(2), 587 portal->getDerivedCorner(0), 588 portal->getDerivedCorner(1)); 589 } 590 else 591 { 592 newPlane->redefine( 593 portal->getDerivedCorner(2), 594 portal->getDerivedCorner(1), 595 portal->getDerivedCorner(0)); 596 } 597 598 newPlane->setPortal(portal); 599 mActiveCullingPlanes.push_back(newPlane); 600 addedcullingplanes++; 601 } 602 return addedcullingplanes; 603 } 604 605 // remove culling planes created from the given portal removePortalCullingPlanes(PortalBase * portal)606 void PCZFrustum::removePortalCullingPlanes(PortalBase* portal) 607 { 608 PCPlaneList::iterator pit = mActiveCullingPlanes.begin(); 609 while ( pit != mActiveCullingPlanes.end() ) 610 { 611 PCPlane * plane = *pit; 612 if (plane->getPortal() == portal) 613 { 614 // put the plane back in the reservoir 615 mCullingPlaneReservoir.push_front(plane); 616 // erase the entry from the active culling plane list 617 pit = mActiveCullingPlanes.erase(pit); 618 } 619 else 620 { 621 pit++; 622 } 623 } 624 625 } 626 627 // remove all active extra culling planes 628 // NOTE: Does not change the use of the originPlane! removeAllCullingPlanes(void)629 void PCZFrustum::removeAllCullingPlanes(void) 630 { 631 PCPlaneList::iterator pit = mActiveCullingPlanes.begin(); 632 while ( pit != mActiveCullingPlanes.end() ) 633 { 634 PCPlane * plane = *pit; 635 // put the plane back in the reservoir 636 mCullingPlaneReservoir.push_front(plane); 637 // go to next entry 638 pit++; 639 } 640 mActiveCullingPlanes.clear(); 641 } 642 643 // set the origin plane setOriginPlane(const Vector3 & rkNormal,const Vector3 & rkPoint)644 void PCZFrustum::setOriginPlane(const Vector3 &rkNormal, const Vector3 &rkPoint) 645 { 646 mOriginPlane.redefine(rkNormal, rkPoint); 647 } 648 649 // get an unused PCPlane from the CullingPlane Reservoir 650 // note that this removes the PCPlane from the reservoir! getUnusedCullingPlane(void)651 PCPlane * PCZFrustum::getUnusedCullingPlane(void) 652 { 653 PCPlane * plane = 0; 654 if (mCullingPlaneReservoir.size() > 0) 655 { 656 PCPlaneList::iterator pit = mCullingPlaneReservoir.begin(); 657 plane = *pit; 658 mCullingPlaneReservoir.erase(pit); 659 return plane; 660 } 661 // no available planes! create one 662 plane = OGRE_NEW_T(PCPlane, MEMCATEGORY_SCENE_CONTROL); 663 return plane; 664 } 665 666 } 667