sceneZoneCullingState.cpp
Engine/source/scene/culling/sceneZoneCullingState.cpp
Detailed Description
1 2//----------------------------------------------------------------------------- 3// Copyright (c) 2012 GarageGames, LLC 4// 5// Permission is hereby granted, free of charge, to any person obtaining a copy 6// of this software and associated documentation files (the "Software"), to 7// deal in the Software without restriction, including without limitation the 8// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or 9// sell copies of the Software, and to permit persons to whom the Software is 10// furnished to do so, subject to the following conditions: 11// 12// The above copyright notice and this permission notice shall be included in 13// all copies or substantial portions of the Software. 14// 15// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 16// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 17// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 18// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 19// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 20// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS 21// IN THE SOFTWARE. 22//----------------------------------------------------------------------------- 23 24#include "platform/platform.h" 25#include "scene/culling/sceneZoneCullingState.h" 26 27#include "scene/culling/sceneCullingState.h" 28#include "platform/profiler.h" 29 30 31//----------------------------------------------------------------------------- 32 33template< typename T > 34inline SceneZoneCullingState::CullingTestResult SceneZoneCullingState::_testVolumes( T bounds, bool occludersOnly ) const 35{ 36 // If we are testing for occlusion only and we don't have any 37 // occlusion volumes, we can early out here. 38 39 if( occludersOnly && !mHaveOccluders ) 40 return CullingTestNegative; 41 42 // If we haven't sorted the volumes on this zone state yet, 43 // do so now. 44 45 if( !mHaveSortedVolumes ) 46 _sortVolumes(); 47 48 // Now go through the volumes in this zone and test them 49 // against the bounds. 50 51 for( CullingVolumeLink* link = mCullingVolumes; link != NULL; link = link->mNext ) 52 { 53 const SceneCullingVolume& volume = link->mVolume; 54 55 if( volume.isOccluder() ) 56 { 57 if( volume.test( bounds ) ) 58 return CullingTestPositiveByOcclusion; 59 } 60 else 61 { 62 // If we are testing for occlusion only, we can early out as soon 63 // as we have reached the first non-inverted volume. 64 if( occludersOnly ) 65 return CullingTestNegative; 66 67 if( volume.test( bounds ) ) 68 return CullingTestPositiveByInclusion; 69 } 70 } 71 72 return CullingTestNegative; 73} 74 75//----------------------------------------------------------------------------- 76 77SceneZoneCullingState::CullingTestResult SceneZoneCullingState::testVolumes( const Box3F& aabb, bool invertedOnly ) const 78{ 79 PROFILE_SCOPE( SceneZoneCullingState_testVolumes ); 80 return _testVolumes( aabb, invertedOnly ); 81} 82 83//----------------------------------------------------------------------------- 84 85SceneZoneCullingState::CullingTestResult SceneZoneCullingState::testVolumes( const OrientedBox3F& obb, bool invertedOnly ) const 86{ 87 PROFILE_SCOPE( SceneZoneCullingState_testVolumes_OBB ); 88 return _testVolumes( obb, invertedOnly ); 89} 90 91//----------------------------------------------------------------------------- 92 93SceneZoneCullingState::CullingTestResult SceneZoneCullingState::testVolumes( const SphereF& sphere, bool invertedOnly ) const 94{ 95 PROFILE_SCOPE( SceneZoneCullingState_testVolumes_Sphere ); 96 return _testVolumes( sphere, invertedOnly ); 97} 98 99//----------------------------------------------------------------------------- 100 101void SceneZoneCullingState::_sortVolumes() const 102{ 103 // First do a pass to gather all occlusion volumes. These must be put on the 104 // list in front of all inclusion volumes. Otherwise, an inclusion volume 105 // may test positive when in fact an occlusion volume would reject the object. 106 107 CullingVolumeLink* occluderHead = NULL; 108 CullingVolumeLink* occluderTail = NULL; 109 110 if( mHaveOccluders ) 111 { 112 U32 numOccluders = 0; 113 114 for( CullingVolumeLink* current = mCullingVolumes, *prev = NULL; current != NULL; ) 115 { 116 CullingVolumeLink* next = current->mNext; 117 118 if( !current->mVolume.isOccluder() ) 119 prev = current; 120 else 121 { 122 // Unlink from list. 123 124 if( prev ) 125 prev->mNext = next; 126 else 127 mCullingVolumes = next; 128 129 // Sort into list. 130 131 _insertSorted( occluderHead, occluderTail, current ); 132 ++ numOccluders; 133 } 134 135 current = next; 136 } 137 138 // If we ended up with more inverted (occlusion) volumes than we want, 139 // chop off any but the first N volumes. Since we have sorted the volumes 140 // by screen coverage, this will get rid of smallest occlusion volumes. 141 142 if( numOccluders > SceneCullingState::smMaxOccludersPerZone ) 143 { 144 CullingVolumeLink* last = occluderHead; 145 for( U32 i = 0; i < ( SceneCullingState::smMaxOccludersPerZone - 1 ); ++ i ) 146 last = last->mNext; 147 148 // Chop off rest. The links are allocated on the chunker 149 // and thus will simply disappear when the state gets deleted. 150 151 last->mNext = NULL; 152 occluderTail = last; 153 } 154 } 155 156 // Now, do a second pass to sort all includer volumes by decreasing screen 157 // real estate so that when testing against them, we test the larger volumes first 158 // and the smaller ones later. 159 160 CullingVolumeLink* includerHead = NULL; 161 CullingVolumeLink* includerTail = NULL; 162 163 while( mCullingVolumes ) 164 { 165 CullingVolumeLink* current = mCullingVolumes; 166 167 AssertFatal( !current->mVolume.isOccluder(), 168 "SceneCullingState::ZoneState::_sortFrustums - Occluders must have been filtered out at this point" ); 169 170 // Unlink from list. 171 172 mCullingVolumes = current->mNext; 173 174 // Sort into list. 175 176 _insertSorted( includerHead, includerTail, current ); 177 } 178 179 // Merge the two lists. Put inverted volumes first and 180 // non-inverted volumes second. 181 182 if( occluderHead != NULL ) 183 { 184 mCullingVolumes = occluderHead; 185 occluderTail->mNext = includerHead; 186 } 187 else 188 mCullingVolumes = includerHead; 189 190 // Done. 191 192 mHaveSortedVolumes = true; 193} 194 195//----------------------------------------------------------------------------- 196 197void SceneZoneCullingState::_insertSorted( CullingVolumeLink*& head, CullingVolumeLink*& tail, CullingVolumeLink* link ) 198{ 199 // If first element, just put it in the list 200 // and return. 201 202 if( !head ) 203 { 204 head = link; 205 tail = link; 206 link->mNext = NULL; 207 208 return; 209 } 210 211 // Otherwise, search for where to put it. 212 213 F32 sortPoint = link->mVolume.getSortPoint(); 214 215 for( CullingVolumeLink* current = head, *prev = NULL; current != NULL; prev = current, current = current->mNext ) 216 { 217 F32 currentSortPoint = current->mVolume.getSortPoint(); 218 if( currentSortPoint > sortPoint ) 219 continue; 220 221 if( !prev ) 222 head = link; 223 else 224 prev->mNext = link; 225 226 link->mNext = current; 227 return; 228 } 229 230 // Smallest frustum in list. Append to end. 231 232 tail->mNext = link; 233 link->mNext = NULL; 234 235 tail = link; 236} 237