sceneCullingState.cpp 32 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940
  1. //-----------------------------------------------------------------------------
  2. // Copyright (c) 2012 GarageGames, LLC
  3. //
  4. // Permission is hereby granted, free of charge, to any person obtaining a copy
  5. // of this software and associated documentation files (the "Software"), to
  6. // deal in the Software without restriction, including without limitation the
  7. // rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
  8. // sell copies of the Software, and to permit persons to whom the Software is
  9. // furnished to do so, subject to the following conditions:
  10. //
  11. // The above copyright notice and this permission notice shall be included in
  12. // all copies or substantial portions of the Software.
  13. //
  14. // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  15. // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  16. // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  17. // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  18. // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  19. // FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
  20. // IN THE SOFTWARE.
  21. //-----------------------------------------------------------------------------
  22. #include "platform/platform.h"
  23. #include "scene/culling/sceneCullingState.h"
  24. #include "scene/sceneManager.h"
  25. #include "scene/sceneObject.h"
  26. #include "scene/zones/sceneZoneSpace.h"
  27. #include "math/mathUtils.h"
  28. #include "platform/profiler.h"
  29. #include "terrain/terrData.h"
  30. #include "util/tempAlloc.h"
  31. #include "gfx/sim/debugDraw.h"
  32. extern bool gEditingMission;
  33. bool SceneCullingState::smDisableTerrainOcclusion = false;
  34. bool SceneCullingState::smDisableZoneCulling = false;
  35. U32 SceneCullingState::smMaxOccludersPerZone = 4;
  36. F32 SceneCullingState::smOccluderMinWidthPercentage = 0.1f;
  37. F32 SceneCullingState::smOccluderMinHeightPercentage = 0.1f;
  38. //-----------------------------------------------------------------------------
  39. SceneCullingState::SceneCullingState( SceneManager* sceneManager, const SceneCameraState& viewState )
  40. : mSceneManager( sceneManager ),
  41. mCameraState( viewState ),
  42. mDisableZoneCulling( smDisableZoneCulling ),
  43. mDisableTerrainOcclusion( smDisableTerrainOcclusion )
  44. {
  45. AssertFatal( sceneManager->getZoneManager(), "SceneCullingState::SceneCullingState - SceneManager must have a zone manager!" );
  46. VECTOR_SET_ASSOCIATION( mZoneStates );
  47. VECTOR_SET_ASSOCIATION( mAddedOccluderObjects );
  48. // Allocate zone states.
  49. const U32 numZones = sceneManager->getZoneManager()->getNumZones();
  50. mZoneStates.setSize( numZones );
  51. dMemset( mZoneStates.address(), 0, sizeof( SceneZoneCullingState ) * numZones );
  52. // Allocate the zone visibility flags.
  53. mZoneVisibilityFlags.setSize( numZones );
  54. mZoneVisibilityFlags.clear();
  55. // Culling frustum
  56. mCullingFrustum = mCameraState.getFrustum();
  57. mCullingFrustum.bakeProjectionOffset();
  58. // Construct the root culling volume from
  59. // the culling frustum. Omit the frustum's
  60. // near and far plane so we don't test it repeatedly.
  61. PlaneF* planes = allocateData< PlaneF >( 4 );
  62. planes[ 0 ] = mCullingFrustum.getPlanes()[ Frustum::PlaneLeft ];
  63. planes[ 1 ] = mCullingFrustum.getPlanes()[ Frustum::PlaneRight ];
  64. planes[ 2 ] = mCullingFrustum.getPlanes()[ Frustum::PlaneTop];
  65. planes[ 3 ] = mCullingFrustum.getPlanes()[ Frustum::PlaneBottom ];
  66. mRootVolume = SceneCullingVolume(
  67. SceneCullingVolume::Includer,
  68. PlaneSetF( planes, 4 )
  69. );
  70. }
  71. //-----------------------------------------------------------------------------
  72. bool SceneCullingState::isWithinVisibleZone( SceneObject* object ) const
  73. {
  74. for( SceneObject::ZoneRef* ref = object->_getZoneRefHead();
  75. ref != NULL; ref = ref->nextInObj )
  76. if( mZoneVisibilityFlags.test( ref->zone ) )
  77. return true;
  78. return false;
  79. }
  80. //-----------------------------------------------------------------------------
  81. void SceneCullingState::addOccluder( SceneObject* object )
  82. {
  83. PROFILE_SCOPE( SceneCullingState_addOccluder );
  84. // If the occluder is itself occluded, don't add it.
  85. //
  86. // NOTE: We do allow near plane intersections here. Silhouette extraction
  87. // should take that into account.
  88. if( cullObjects( &object, 1, DontCullRenderDisabled ) != 1 )
  89. return;
  90. // If the occluder has already been added, do nothing. Check this
  91. // after the culling check since the same occluder can be added by
  92. // two separate zones and not be visible in one yet be visible in the
  93. // other.
  94. if( mAddedOccluderObjects.contains( object ) )
  95. return;
  96. mAddedOccluderObjects.push_back( object );
  97. // Let the object build a silhouette. If it doesn't
  98. // return one, abort.
  99. Vector< Point3F > silhouette;
  100. object->buildSilhouette( getCameraState(), silhouette );
  101. if( silhouette.empty() || silhouette.size() < 3 )
  102. return;
  103. // Generate the culling volume.
  104. SceneCullingVolume volume;
  105. if( !createCullingVolume(
  106. silhouette.address(),
  107. silhouette.size(),
  108. SceneCullingVolume::Occluder,
  109. volume ) )
  110. return;
  111. // Add the frustum to all zones that the object is assigned to.
  112. for( SceneObject::ZoneRef* ref = object->_getZoneRefHead(); ref != NULL; ref = ref->nextInObj )
  113. addCullingVolumeToZone( ref->zone, volume );
  114. }
  115. //-----------------------------------------------------------------------------
  116. bool SceneCullingState::addCullingVolumeToZone( U32 zoneId, const SceneCullingVolume& volume )
  117. {
  118. PROFILE_SCOPE( SceneCullingState_addCullingVolumeToZone );
  119. AssertFatal( zoneId < mZoneStates.size(), "SceneCullingState::addCullingVolumeToZone - Zone ID out of range" );
  120. SceneZoneCullingState& zoneState = mZoneStates[ zoneId ];
  121. // [rene, 07-Apr-10] I previously used to attempt to merge things here and detect whether
  122. // the visibility state of the zone has changed at all. Since we allow polyhedra to be
  123. // degenerate here and since polyhedra cannot be merged easily like frustums, I have opted
  124. // to remove this for now. I'm also convinced that with the current traversal system it
  125. // adds little benefit.
  126. // Link the volume to the zone state.
  127. typedef SceneZoneCullingState::CullingVolumeLink LinkType;
  128. LinkType* link = reinterpret_cast< LinkType* >( allocateData( sizeof( LinkType ) ) );
  129. link->mVolume = volume;
  130. link->mNext = zoneState.mCullingVolumes;
  131. zoneState.mCullingVolumes = link;
  132. if( volume.isOccluder() )
  133. zoneState.mHaveOccluders = true;
  134. else
  135. zoneState.mHaveIncluders = true;
  136. // Mark sorting state as dirty.
  137. zoneState.mHaveSortedVolumes = false;
  138. // Set the visibility flag for the zone.
  139. if( volume.isIncluder() )
  140. mZoneVisibilityFlags.set( zoneId );
  141. return true;
  142. }
  143. //-----------------------------------------------------------------------------
  144. bool SceneCullingState::addCullingVolumeToZone( U32 zoneId, SceneCullingVolume::Type type, const AnyPolyhedron& polyhedron )
  145. {
  146. // Allocate space on our chunker.
  147. const U32 numPlanes = polyhedron.getNumPlanes();
  148. PlaneF* planes = allocateData< PlaneF >( numPlanes );
  149. // Copy the planes over.
  150. dMemcpy( planes, polyhedron.getPlanes(), numPlanes * sizeof( planes[ 0 ] ) );
  151. // Create a culling volume.
  152. SceneCullingVolume volume(
  153. type,
  154. PlaneSetF( planes, numPlanes )
  155. );
  156. // And add it.
  157. return addCullingVolumeToZone( zoneId, volume );
  158. }
  159. //-----------------------------------------------------------------------------
  160. bool SceneCullingState::createCullingVolume( const Point3F* vertices, U32 numVertices, SceneCullingVolume::Type type, SceneCullingVolume& outVolume )
  161. {
  162. const Point3F& viewPos = getCameraState().getViewPosition();
  163. const Point3F& viewDir = getCameraState().getViewDirection();
  164. const bool isOrtho = getCullingFrustum().isOrtho();
  165. //TODO: check if we need to handle penetration of the near plane for occluders specially
  166. // Allocate space for the clipping planes we generate. Assume the worst case
  167. // of every edge generating a plane and, for includers, all edges meeting at
  168. // steep angles so we need to insert extra planes (the latter is not possible,
  169. // of course, but it makes things less complicated here). For occluders, add
  170. // an extra plane for the near cap.
  171. const U32 maxPlanes = ( type == SceneCullingVolume::Occluder ? numVertices + 1 : numVertices * 2 );
  172. PlaneF* planes = allocateData< PlaneF >( maxPlanes );
  173. // Keep track of the world-space bounds of the polygon. We use this later
  174. // to derive some metrics.
  175. Box3F wsPolyBounds;
  176. wsPolyBounds.minExtents = Point3F( TypeTraits< F32 >::MAX, TypeTraits< F32 >::MAX, TypeTraits< F32 >::MAX );
  177. wsPolyBounds.maxExtents = Point3F( TypeTraits< F32 >::MIN, TypeTraits< F32 >::MIN, TypeTraits< F32 >::MIN );
  178. // For occluders, also keep track of the nearest, and two farthest silhouette points. We use
  179. // this later to construct a near capping plane.
  180. F32 minVertexDistanceSquared = TypeTraits< F32 >::MAX;
  181. U32 leastDistantVert = 0;
  182. F32 maxVertexDistancesSquared[ 2 ] = { TypeTraits< F32 >::MIN, TypeTraits< F32 >::MIN };
  183. U32 mostDistantVertices[ 2 ] = { 0, 0 };
  184. // Generate the extrusion volume. For orthographic projections, extrude
  185. // parallel to the view direction whereas for parallel projections, extrude
  186. // from the viewpoint.
  187. U32 numPlanes = 0;
  188. U32 lastVertex = numVertices - 1;
  189. bool invert = false;
  190. for( U32 i = 0; i < numVertices; lastVertex = i, ++ i )
  191. {
  192. AssertFatal( numPlanes < maxPlanes, "SceneCullingState::createCullingVolume - Did not allocate enough planes!" );
  193. const Point3F& v1 = vertices[ i ];
  194. const Point3F& v2 = vertices[ lastVertex ];
  195. // Keep track of bounds.
  196. wsPolyBounds.minExtents.setMin( v1 );
  197. wsPolyBounds.maxExtents.setMax( v1 );
  198. // Skip the edge if it's length is really short.
  199. const Point3F edgeVector = v2 - v1;
  200. const F32 edgeVectorLenSquared = edgeVector.lenSquared();
  201. if( edgeVectorLenSquared < 0.025f )
  202. continue;
  203. //TODO: might need to do additional checks here for non-planar polygons used by occluders
  204. //TODO: test for colinearity of edge vector with view vector (occluders only)
  205. // Create a plane for the edge.
  206. if( isOrtho )
  207. {
  208. // Compute a plane through the two edge vertices and one
  209. // of the vertices extended along the view direction.
  210. if( !invert )
  211. planes[ numPlanes ] = PlaneF( v1, v1 + viewDir, v2 );
  212. else
  213. planes[ numPlanes ] = PlaneF( v2, v1 + viewDir, v1 );
  214. }
  215. else
  216. {
  217. // Compute a plane going through the viewpoint and the two
  218. // edge vertices.
  219. if( !invert )
  220. planes[ numPlanes ] = PlaneF( v1, viewPos, v2 );
  221. else
  222. planes[ numPlanes ] = PlaneF( v2, viewPos, v1 );
  223. }
  224. numPlanes ++;
  225. // If this is the first plane that we have created, find out whether
  226. // the vertex ordering is giving us the plane orientations that we want
  227. // (facing inside). If not, invert vertex order from now on.
  228. if( numPlanes == 1 )
  229. {
  230. Point3F center( 0, 0, 0 );
  231. for( U32 n = 0; n < numVertices; ++ n )
  232. center += vertices[n];
  233. center /= numVertices;
  234. if( planes[numPlanes - 1].whichSide( center ) == PlaneF::Back )
  235. {
  236. invert = true;
  237. planes[ numPlanes - 1 ].invert();
  238. }
  239. }
  240. // For occluders, keep tabs of the nearest, and two farthest vertices.
  241. if( type == SceneCullingVolume::Occluder )
  242. {
  243. const F32 distSquared = ( v1 - viewPos ).lenSquared();
  244. if( distSquared < minVertexDistanceSquared )
  245. {
  246. minVertexDistanceSquared = distSquared;
  247. leastDistantVert = i;
  248. }
  249. if( distSquared > maxVertexDistancesSquared[ 0 ] )
  250. {
  251. // Move 0 to 1.
  252. maxVertexDistancesSquared[ 1 ] = maxVertexDistancesSquared[ 0 ];
  253. mostDistantVertices[ 1 ] = mostDistantVertices[ 0 ];
  254. // Replace 0.
  255. maxVertexDistancesSquared[ 0 ] = distSquared;
  256. mostDistantVertices[ 0 ] = i;
  257. }
  258. else if( distSquared > maxVertexDistancesSquared[ 1 ] )
  259. {
  260. // Replace 1.
  261. maxVertexDistancesSquared[ 1 ] = distSquared;
  262. mostDistantVertices[ 1 ] = i;
  263. }
  264. }
  265. }
  266. // If the extrusion produced no useful result, abort.
  267. if( numPlanes < 3 )
  268. return false;
  269. // For includers, test the angle of the edges at the current vertex.
  270. // If too steep, add an extra plane to improve culling efficiency.
  271. if( false )//type == SceneCullingVolume::Includer )
  272. {
  273. const U32 numOriginalPlanes = numPlanes;
  274. U32 lastPlaneIndex = numPlanes - 1;
  275. for( U32 i = 0; i < numOriginalPlanes; lastPlaneIndex = i, ++ i )
  276. {
  277. const PlaneF& currentPlane = planes[ i ];
  278. const PlaneF& lastPlane = planes[ lastPlaneIndex ];
  279. // Compute the cosine of the angle between the two plane normals.
  280. const F32 cosAngle = mFabs( mDot( currentPlane, lastPlane ) );
  281. // The planes meet at increasingly steep angles the more they point
  282. // in opposite directions, i.e the closer the angle of their normals
  283. // is to 180 degrees. Skip any two planes that don't get near that.
  284. if( cosAngle > 0.1f )
  285. continue;
  286. //TODO
  287. const Point3F addNormals = currentPlane + lastPlane;
  288. const Point3F crossNormals = mCross( currentPlane, lastPlane );
  289. Point3F newNormal = currentPlane + lastPlane;//addNormals - mDot( addNormals, crossNormals ) * crossNormals;
  290. //
  291. planes[ numPlanes ] = PlaneF( currentPlane.getPosition(), newNormal );
  292. numPlanes ++;
  293. }
  294. }
  295. // Compute the metrics of the culling volume in relation to the view frustum.
  296. //
  297. // For this, we are short-circuiting things slightly. The correct way (other than doing
  298. // full screen projections) would be to transform all the polygon points into camera
  299. // space, lay an AABB around those points, and then find the X and Z extents on the near plane.
  300. //
  301. // However, while not as accurate, a faster way is to just project the axial vectors
  302. // of the bounding box onto both the camera right and up vector. This gives us a rough
  303. // estimate of the camera-space size of the polygon we're looking at.
  304. const MatrixF& cameraTransform = getCameraState().getViewWorldMatrix();
  305. const Point3F cameraRight = cameraTransform.getRightVector();
  306. const Point3F cameraUp = cameraTransform.getUpVector();
  307. const Point3F wsPolyBoundsExtents = wsPolyBounds.getExtents();
  308. F32 widthEstimate =
  309. getMax( mFabs( wsPolyBoundsExtents.x * cameraRight.x ),
  310. getMax( mFabs( wsPolyBoundsExtents.y * cameraRight.y ),
  311. mFabs( wsPolyBoundsExtents.z * cameraRight.z ) ) );
  312. F32 heightEstimate =
  313. getMax( mFabs( wsPolyBoundsExtents.x * cameraUp.x ),
  314. getMax( mFabs( wsPolyBoundsExtents.y * cameraUp.y ),
  315. mFabs( wsPolyBoundsExtents.z * cameraUp.z ) ) );
  316. // If the current camera is a perspective one, divide the two estimates
  317. // by the distance of the nearest bounding box vertex to the camera
  318. // to account for perspective distortion.
  319. if( !isOrtho )
  320. {
  321. const Point3F nearestVertex = wsPolyBounds.computeVertex(
  322. Box3F::getPointIndexFromOctant( - viewDir )
  323. );
  324. const F32 distance = ( nearestVertex - viewPos ).len();
  325. widthEstimate /= distance;
  326. heightEstimate /= distance;
  327. }
  328. // If we are creating an occluder, check to see if the estimates fit
  329. // our minimum requirements.
  330. if( type == SceneCullingVolume::Occluder )
  331. {
  332. const F32 widthEstimatePercentage = widthEstimate / getCullingFrustum().getWidth();
  333. const F32 heightEstimatePercentage = heightEstimate / getCullingFrustum().getHeight();
  334. if( widthEstimatePercentage < smOccluderMinWidthPercentage ||
  335. heightEstimatePercentage < smOccluderMinHeightPercentage )
  336. return false; // Reject.
  337. }
  338. // Use the area estimate as the volume's sort point.
  339. const F32 sortPoint = widthEstimate * heightEstimate;
  340. // Finally, if it's an occluder, compute a near cap. The near cap prevents objects
  341. // in front of the occluder from testing positive. The same could be achieved by
  342. // manually comparing distances before testing objects but since that would amount
  343. // to the same checks the plane/AABB tests do, it's easier to just add another plane.
  344. // Additionally, it gives the benefit of being able to create more precise culling
  345. // results by angling the plane.
  346. //NOTE: Could consider adding a near cap for includers too when generating a volume
  347. // for the outdoor zone as that may prevent quite a bit of space from being included.
  348. // However, given that this space will most likely just be filled with interior
  349. // stuff anyway, it's probably not worth it.
  350. if( type == SceneCullingVolume::Occluder )
  351. {
  352. const U32 nearCapIndex = numPlanes;
  353. planes[ nearCapIndex ] = PlaneF(
  354. vertices[ mostDistantVertices[ 0 ] ],
  355. vertices[ mostDistantVertices[ 1 ] ],
  356. vertices[ leastDistantVert ] );
  357. // Invert the plane, if necessary.
  358. if( planes[ nearCapIndex ].whichSide( viewPos ) == PlaneF::Front )
  359. planes[ nearCapIndex ].invert();
  360. numPlanes ++;
  361. }
  362. // Create the volume from the planes.
  363. outVolume = SceneCullingVolume(
  364. type,
  365. PlaneSetF( planes, numPlanes )
  366. );
  367. outVolume.setSortPoint( sortPoint );
  368. // Done.
  369. return true;
  370. }
  371. //-----------------------------------------------------------------------------
  372. namespace {
  373. struct ZoneArrayIterator
  374. {
  375. U32 mCurrent;
  376. U32 mNumZones;
  377. const U32* mZones;
  378. ZoneArrayIterator( const U32* zones, U32 numZones )
  379. : mCurrent( 0 ),
  380. mNumZones( numZones ),
  381. mZones( zones ) {}
  382. bool isValid() const
  383. {
  384. return ( mCurrent < mNumZones );
  385. }
  386. ZoneArrayIterator& operator ++()
  387. {
  388. mCurrent ++;
  389. return *this;
  390. }
  391. U32 operator *() const
  392. {
  393. return mZones[ mCurrent ];
  394. }
  395. };
  396. }
  397. template< typename T, typename Iter >
  398. inline SceneZoneCullingState::CullingTestResult SceneCullingState::_testOccludersOnly( const T& bounds, Iter zoneIter ) const
  399. {
  400. // Test the culling states of all zones that the object
  401. // is assigned to.
  402. for( ; zoneIter.isValid(); ++ zoneIter )
  403. {
  404. const SceneZoneCullingState& zoneState = getZoneState( *zoneIter );
  405. // Skip zone if there are no occluders.
  406. if( !zoneState.hasOccluders() )
  407. continue;
  408. // If the object's world bounds overlaps any of the volumes
  409. // for this zone, it's rendered.
  410. if( zoneState.testVolumes( bounds, true ) == SceneZoneCullingState::CullingTestPositiveByOcclusion )
  411. return SceneZoneCullingState::CullingTestPositiveByOcclusion;
  412. }
  413. return SceneZoneCullingState::CullingTestNegative;
  414. }
  415. template< typename T, typename Iter >
  416. inline SceneZoneCullingState::CullingTestResult SceneCullingState::_test( const T& bounds, Iter zoneIter,
  417. const PlaneF& nearPlane, const PlaneF& farPlane ) const
  418. {
  419. // Defer test of near and far plane until we've hit a zone
  420. // which actually has visible space. This prevents us from
  421. // doing near/far tests on objects that were included in the
  422. // potential render list but aren't actually in any visible
  423. // zone.
  424. bool haveTestedNearAndFar = false;
  425. // Test the culling states of all zones that the object
  426. // is assigned to.
  427. for( ; zoneIter.isValid(); ++ zoneIter )
  428. {
  429. const SceneZoneCullingState& zoneState = getZoneState( *zoneIter );
  430. // Skip zone if there are no positive culling volumes.
  431. if( !zoneState.hasIncluders() )
  432. continue;
  433. // If we haven't tested the near and far plane yet, do so
  434. // now.
  435. if( !haveTestedNearAndFar )
  436. {
  437. // Test near plane.
  438. PlaneF::Side nearSide = nearPlane.whichSide( bounds );
  439. if( nearSide == PlaneF::Back )
  440. return SceneZoneCullingState::CullingTestNegative;
  441. // Test far plane.
  442. PlaneF::Side farSide = farPlane.whichSide( bounds );
  443. if( farSide == PlaneF::Back )
  444. return SceneZoneCullingState::CullingTestNegative;
  445. haveTestedNearAndFar = true;
  446. }
  447. // If the object's world bounds overlaps any of the volumes
  448. // for this zone, it's rendered.
  449. SceneZoneCullingState::CullingTestResult result = zoneState.testVolumes( bounds );
  450. if( result == SceneZoneCullingState::CullingTestPositiveByInclusion )
  451. return result;
  452. else if( result == SceneZoneCullingState::CullingTestPositiveByOcclusion )
  453. return result;
  454. }
  455. return SceneZoneCullingState::CullingTestNegative;
  456. }
  457. //-----------------------------------------------------------------------------
  458. template< bool OCCLUDERS_ONLY, typename T >
  459. inline SceneZoneCullingState::CullingTestResult SceneCullingState::_test( const T& bounds, const U32* zones, U32 numZones ) const
  460. {
  461. // If zone culling is disabled, only test against
  462. // the root frustum.
  463. if( disableZoneCulling() )
  464. {
  465. if( !OCCLUDERS_ONLY && !getCullingFrustum().isCulled( bounds ) )
  466. return SceneZoneCullingState::CullingTestPositiveByInclusion;
  467. return SceneZoneCullingState::CullingTestNegative;
  468. }
  469. // Otherwise test each of the zones.
  470. if( OCCLUDERS_ONLY )
  471. {
  472. return _testOccludersOnly(
  473. bounds,
  474. ZoneArrayIterator( zones, numZones )
  475. );
  476. }
  477. else
  478. {
  479. const PlaneF* frustumPlanes = getCullingFrustum().getPlanes();
  480. return _test(
  481. bounds,
  482. ZoneArrayIterator( zones, numZones ),
  483. frustumPlanes[ Frustum::PlaneNear ],
  484. frustumPlanes[ Frustum::PlaneFar ]
  485. );
  486. }
  487. }
  488. //-----------------------------------------------------------------------------
  489. bool SceneCullingState::isCulled( const Box3F& aabb, const U32* zones, U32 numZones ) const
  490. {
  491. SceneZoneCullingState::CullingTestResult result = _test< false >( aabb, zones, numZones );
  492. return ( result == SceneZoneCullingState::CullingTestNegative ||
  493. result == SceneZoneCullingState::CullingTestPositiveByOcclusion );
  494. }
  495. //-----------------------------------------------------------------------------
  496. bool SceneCullingState::isCulled( const OrientedBox3F& obb, const U32* zones, U32 numZones ) const
  497. {
  498. SceneZoneCullingState::CullingTestResult result = _test< false >( obb, zones, numZones );
  499. return ( result == SceneZoneCullingState::CullingTestNegative ||
  500. result == SceneZoneCullingState::CullingTestPositiveByOcclusion );
  501. }
  502. //-----------------------------------------------------------------------------
  503. bool SceneCullingState::isCulled( const SphereF& sphere, const U32* zones, U32 numZones ) const
  504. {
  505. SceneZoneCullingState::CullingTestResult result = _test< false >( sphere, zones, numZones );
  506. return ( result == SceneZoneCullingState::CullingTestNegative ||
  507. result == SceneZoneCullingState::CullingTestPositiveByOcclusion );
  508. }
  509. //-----------------------------------------------------------------------------
  510. bool SceneCullingState::isOccluded( SceneObject* object ) const
  511. {
  512. if( disableZoneCulling() )
  513. return false;
  514. CullingTestResult result = _testOccludersOnly(
  515. object->getWorldBox(),
  516. SceneObject::ObjectZonesIterator( object )
  517. );
  518. return ( result == SceneZoneCullingState::CullingTestPositiveByOcclusion );
  519. }
  520. //-----------------------------------------------------------------------------
  521. bool SceneCullingState::isOccluded( const Box3F& aabb, const U32* zones, U32 numZones ) const
  522. {
  523. return ( _test< true >( aabb, zones, numZones ) == SceneZoneCullingState::CullingTestPositiveByOcclusion );
  524. }
  525. //-----------------------------------------------------------------------------
  526. bool SceneCullingState::isOccluded( const OrientedBox3F& obb, const U32* zones, U32 numZones ) const
  527. {
  528. return ( _test< true >( obb, zones, numZones ) == SceneZoneCullingState::CullingTestPositiveByOcclusion );
  529. }
  530. //-----------------------------------------------------------------------------
  531. bool SceneCullingState::isOccluded( const SphereF& sphere, const U32* zones, U32 numZones ) const
  532. {
  533. return ( _test< true >( sphere, zones, numZones ) == SceneZoneCullingState::CullingTestPositiveByOcclusion );
  534. }
  535. //-----------------------------------------------------------------------------
  536. U32 SceneCullingState::cullObjects( SceneObject** objects, U32 numObjects, U32 cullOptions ) const
  537. {
  538. PROFILE_SCOPE( SceneCullingState_cullObjects );
  539. U32 numRemainingObjects = 0;
  540. // We test near and far planes separately in order to not do the tests
  541. // repeatedly, so fetch the planes now.
  542. const PlaneF& nearPlane = getCullingFrustum().getPlanes()[ Frustum::PlaneNear ];
  543. const PlaneF& farPlane = getCullingFrustum().getPlanes()[ Frustum::PlaneFar ];
  544. for( U32 i = 0; i < numObjects; ++ i )
  545. {
  546. SceneObject* object = objects[ i ];
  547. bool isCulled = true;
  548. // If we should respect editor overrides, test that now.
  549. if( !( cullOptions & CullEditorOverrides ) &&
  550. gEditingMission &&
  551. ( ( object->isCullingDisabledInEditor() && object->isRenderEnabled() ) || object->isSelected() ) )
  552. {
  553. isCulled = false;
  554. }
  555. // If the object is render-disabled, it gets culled. The only
  556. // way around this is the editor override above.
  557. else if( !( cullOptions & DontCullRenderDisabled ) &&
  558. !object->isRenderEnabled() )
  559. {
  560. isCulled = true;
  561. }
  562. // Global bounds objects are never culled. Note that this means
  563. // that if these objects are to respect zoning, they need to manually
  564. // trigger the respective culling checks for whatever they want to
  565. // batch.
  566. else if( object->isGlobalBounds() )
  567. isCulled = false;
  568. // If terrain occlusion checks are enabled, run them now.
  569. else if( !mDisableTerrainOcclusion &&
  570. object->getWorldBox().minExtents.x > -1e5 &&
  571. isOccludedByTerrain( object ) )
  572. {
  573. // Occluded by terrain.
  574. isCulled = true;
  575. }
  576. // If the object shouldn't be subjected to more fine-grained culling
  577. // or if zone culling is disabled, just test against the root frustum.
  578. else if( !( object->getTypeMask() & CULLING_INCLUDE_TYPEMASK ) ||
  579. ( object->getTypeMask() & CULLING_EXCLUDE_TYPEMASK ) ||
  580. disableZoneCulling() )
  581. {
  582. isCulled = getCullingFrustum().isCulled( object->getWorldBox() );
  583. }
  584. // Go through the zones that the object is assigned to and
  585. // test the object against the frustums of each of the zones.
  586. else
  587. {
  588. CullingTestResult result = _test(
  589. object->getWorldBox(),
  590. SceneObject::ObjectZonesIterator( object ),
  591. nearPlane,
  592. farPlane
  593. );
  594. isCulled = ( result == SceneZoneCullingState::CullingTestNegative ||
  595. result == SceneZoneCullingState::CullingTestPositiveByOcclusion );
  596. }
  597. if( !isCulled )
  598. objects[ numRemainingObjects ++ ] = object;
  599. }
  600. return numRemainingObjects;
  601. }
  602. //-----------------------------------------------------------------------------
  603. bool SceneCullingState::isOccludedByTerrain( SceneObject* object ) const
  604. {
  605. PROFILE_SCOPE( SceneCullingState_isOccludedByTerrain );
  606. // Don't try to occlude globally bounded objects.
  607. if( object->isGlobalBounds() )
  608. return false;
  609. const Vector< SceneObject* >& terrains = getSceneManager()->getContainer()->getTerrains();
  610. const U32 numTerrains = terrains.size();
  611. for( U32 terrainIdx = 0; terrainIdx < numTerrains; ++ terrainIdx )
  612. {
  613. TerrainBlock* terrain = dynamic_cast< TerrainBlock* >( terrains[ terrainIdx ] );
  614. if( !terrain )
  615. continue;
  616. MatrixF terrWorldTransform = terrain->getWorldTransform();
  617. Point3F localCamPos = getCameraState().getViewPosition();
  618. terrWorldTransform.mulP(localCamPos);
  619. F32 height;
  620. terrain->getHeight( Point2F( localCamPos.x, localCamPos.y ), &height );
  621. bool aboveTerrain = ( height <= localCamPos.z );
  622. // Don't occlude if we're below the terrain. This prevents problems when
  623. // looking out from underground bases...
  624. if( !aboveTerrain )
  625. continue;
  626. const Box3F& oBox = object->getObjBox();
  627. F32 minSide = getMin(oBox.len_x(), oBox.len_y());
  628. if (minSide > 85.0f)
  629. continue;
  630. const Box3F& rBox = object->getWorldBox();
  631. Point3F ul(rBox.minExtents.x, rBox.minExtents.y, rBox.maxExtents.z);
  632. Point3F ur(rBox.minExtents.x, rBox.maxExtents.y, rBox.maxExtents.z);
  633. Point3F ll(rBox.maxExtents.x, rBox.minExtents.y, rBox.maxExtents.z);
  634. Point3F lr(rBox.maxExtents.x, rBox.maxExtents.y, rBox.maxExtents.z);
  635. terrWorldTransform.mulP(ul);
  636. terrWorldTransform.mulP(ur);
  637. terrWorldTransform.mulP(ll);
  638. terrWorldTransform.mulP(lr);
  639. Point3F xBaseL0_s = ul - localCamPos;
  640. Point3F xBaseL0_e = lr - localCamPos;
  641. Point3F xBaseL1_s = ur - localCamPos;
  642. Point3F xBaseL1_e = ll - localCamPos;
  643. static F32 checkPoints[3] = {0.75, 0.5, 0.25};
  644. RayInfo rinfo;
  645. for( U32 i = 0; i < 3; i ++ )
  646. {
  647. Point3F start = (xBaseL0_s * checkPoints[i]) + localCamPos;
  648. Point3F end = (xBaseL0_e * checkPoints[i]) + localCamPos;
  649. if (terrain->castRay(start, end, &rinfo))
  650. continue;
  651. terrain->getHeight(Point2F(start.x, start.y), &height);
  652. if ((height <= start.z) == aboveTerrain)
  653. continue;
  654. start = (xBaseL1_s * checkPoints[i]) + localCamPos;
  655. end = (xBaseL1_e * checkPoints[i]) + localCamPos;
  656. if (terrain->castRay(start, end, &rinfo))
  657. continue;
  658. Point3F test = (start + end) * 0.5;
  659. if (terrain->castRay(localCamPos, test, &rinfo) == false)
  660. continue;
  661. return true;
  662. }
  663. }
  664. return false;
  665. }
  666. //-----------------------------------------------------------------------------
  667. void SceneCullingState::debugRenderCullingVolumes() const
  668. {
  669. const ColorI occluderColor( 255, 0, 0, 255 );
  670. const ColorI includerColor( 0, 255, 0, 255 );
  671. const PlaneF& nearPlane = getCullingFrustum().getPlanes()[ Frustum::PlaneNear ];
  672. const PlaneF& farPlane = getCullingFrustum().getPlanes()[ Frustum::PlaneFar ];
  673. DebugDrawer* drawer = DebugDrawer::get();
  674. const SceneZoneSpaceManager* zoneManager = mSceneManager->getZoneManager();
  675. bool haveDebugZone = false;
  676. const U32 numZones = mZoneStates.size();
  677. for( S32 zoneId = numZones - 1; zoneId >= 0; -- zoneId )
  678. {
  679. if( !zoneManager->isValidZoneId( zoneId ) )
  680. continue;
  681. const SceneZoneCullingState& zoneState = mZoneStates[ zoneId ];
  682. if( !zoneManager->getZoneOwner( zoneId )->isSelected() && ( zoneId != SceneZoneSpaceManager::RootZoneId || haveDebugZone ) )
  683. continue;
  684. haveDebugZone = true;
  685. for( SceneZoneCullingState::CullingVolumeIterator iter( zoneState );
  686. iter.isValid(); ++ iter )
  687. {
  688. // Temporarily add near and far plane to culling volume so that
  689. // no matter how it is defined, it has a chance of being properly
  690. // capped.
  691. const U32 numPlanes = iter->getPlanes().getNumPlanes();
  692. const PlaneF* planes = iter->getPlanes().getPlanes();
  693. TempAlloc< PlaneF > tempPlanes( numPlanes + 2 );
  694. tempPlanes[ 0 ] = nearPlane;
  695. tempPlanes[ 1 ] = farPlane;
  696. dMemcpy( &tempPlanes[ 2 ], planes, numPlanes * sizeof( PlaneF ) );
  697. // Build a polyhedron from the plane set.
  698. Polyhedron polyhedron;
  699. polyhedron.buildFromPlanes(
  700. PlaneSetF( tempPlanes, numPlanes + 2 )
  701. );
  702. // If the polyhedron has any renderable data,
  703. // hand it over to the debug drawer.
  704. if( polyhedron.getNumEdges() )
  705. drawer->drawPolyhedron( polyhedron, iter->isOccluder() ? occluderColor : includerColor );
  706. }
  707. }
  708. }