/** * @file llvieweroctree.cpp * @brief LLViewerOctreeGroup class implementation and supporting functions * * $LicenseInfo:firstyear=2003&license=viewerlgpl$ * Second Life Viewer Source Code * Copyright (C) 2010, Linden Research, Inc. * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public * License as published by the Free Software Foundation; * version 2.1 of the License only. * * This library is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public * License along with this library; if not, write to the Free Software * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA * * Linden Research, Inc., 945 Battery Street, San Francisco, CA 94111 USA * $/LicenseInfo$ */ #include "llviewerprecompiledheaders.h" #include "llvieweroctree.h" #include "llviewerregion.h" #include "pipeline.h" #include "llviewercontrol.h" #include "llappviewer.h" #include "llglslshader.h" #include "llviewershadermgr.h" #include "lldrawpoolwater.h" //----------------------------------------------------------------------------------- //static variables definitions //----------------------------------------------------------------------------------- U32 LLViewerOctreeEntryData::sCurVisible = 10; //reserve the low numbers for special use. bool LLViewerOctreeDebug::sInDebug = false; static LLTrace::CountStatHandle<S32> sOcclusionQueries("occlusion_queries", "Number of occlusion queries executed"), sNumObjectsOccluded("occluded_objects", "Count of objects being occluded by a query"), sNumObjectsUnoccluded("unoccluded_objects", "Count of objects being unoccluded by a query"); //----------------------------------------------------------------------------------- //some global functions definitions //----------------------------------------------------------------------------------- typedef enum { b000 = 0x00, b001 = 0x01, b010 = 0x02, b011 = 0x03, b100 = 0x04, b101 = 0x05, b110 = 0x06, b111 = 0x07, } eLoveTheBits; //contact Runitai Linden for a copy of the SL object used to write this table //basically, you give the table a bitmask of the look-at vector to a node and it //gives you a triangle fan index array static U16 sOcclusionIndices[] = { //000 b111, b110, b010, b011, b001, b101, b100, b110, //001 b011, b010, b000, b001, b101, b111, b110, b010, //010 b101, b100, b110, b111, b011, b001, b000, b100, //011 b001, b000, b100, b101, b111, b011, b010, b000, //100 b110, b000, b010, b011, b111, b101, b100, b000, //101 b010, b100, b000, b001, b011, b111, b110, b100, //110 b100, b010, b110, b111, b101, b001, b000, b010, //111 b000, b110, b100, b101, b001, b011, b010, b110, }; U32 get_box_fan_indices(LLCamera* camera, const LLVector4a& center) { LLVector4a origin; origin.load3(camera->getOrigin().mV); S32 cypher = center.greaterThan(origin).getGatheredBits() & 0x7; return cypher*8; } U8* get_box_fan_indices_ptr(LLCamera* camera, const LLVector4a& center) { LLVector4a origin; origin.load3(camera->getOrigin().mV); S32 cypher = center.greaterThan(origin).getGatheredBits() & 0x7; return (U8*) (sOcclusionIndices+cypher*8); } //create a vertex buffer for efficiently rendering cubes LLVertexBuffer* ll_create_cube_vb(U32 type_mask) { LLVertexBuffer* ret = new LLVertexBuffer(type_mask); ret->allocateBuffer(8, 64); LLStrider<LLVector3> pos; LLStrider<U16> idx; ret->getVertexStrider(pos); ret->getIndexStrider(idx); pos[0] = LLVector3(-1,-1,-1); pos[1] = LLVector3(-1,-1, 1); pos[2] = LLVector3(-1, 1,-1); pos[3] = LLVector3(-1, 1, 1); pos[4] = LLVector3( 1,-1,-1); pos[5] = LLVector3( 1,-1, 1); pos[6] = LLVector3( 1, 1,-1); pos[7] = LLVector3( 1, 1, 1); for (U32 i = 0; i < 64; i++) { idx[i] = sOcclusionIndices[i]; } ret->unmapBuffer(); return ret; } #define LL_TRACK_PENDING_OCCLUSION_QUERIES 0 const F32 SG_OCCLUSION_FUDGE = 0.25f; #define SG_DISCARD_TOLERANCE 0.01f S32 AABBSphereIntersect(const LLVector3& min, const LLVector3& max, const LLVector3 &origin, const F32 &rad) { return AABBSphereIntersectR2(min, max, origin, rad*rad); } S32 AABBSphereIntersectR2(const LLVector3& min, const LLVector3& max, const LLVector3 &origin, const F32 &r) { F32 d = 0.f; F32 t; if ((min-origin).magVecSquared() < r && (max-origin).magVecSquared() < r) { return 2; } for (U32 i = 0; i < 3; i++) { if (origin.mV[i] < min.mV[i]) { t = min.mV[i] - origin.mV[i]; d += t*t; } else if (origin.mV[i] > max.mV[i]) { t = origin.mV[i] - max.mV[i]; d += t*t; } if (d > r) { return 0; } } return 1; } S32 AABBSphereIntersect(const LLVector4a& min, const LLVector4a& max, const LLVector3 &origin, const F32 &rad) { return AABBSphereIntersectR2(min, max, origin, rad*rad); } S32 AABBSphereIntersectR2(const LLVector4a& min, const LLVector4a& max, const LLVector3 &origin, const F32 &r) { F32 d = 0.f; F32 t; LLVector4a origina; origina.load3(origin.mV); LLVector4a v; v.setSub(min, origina); if (v.dot3(v) < r) { v.setSub(max, origina); if (v.dot3(v) < r) { return 2; } } for (U32 i = 0; i < 3; i++) { if (origin.mV[i] < min[i]) { t = min[i] - origin.mV[i]; d += t*t; } else if (origin.mV[i] > max[i]) { t = origin.mV[i] - max[i]; d += t*t; } if (d > r) { return 0; } } return 1; } //----------------------------------------------------------------------------------- //class LLViewerOctreeEntry definitions //----------------------------------------------------------------------------------- LLViewerOctreeEntry::LLViewerOctreeEntry() : mGroup(NULL), mBinRadius(0.f), mBinIndex(-1), mVisible(0) { mPositionGroup.clear(); mExtents[0].clear(); mExtents[1].clear(); for(S32 i = 0; i < NUM_DATA_TYPE; i++) { mData[i] = NULL; } } LLViewerOctreeEntry::~LLViewerOctreeEntry() { llassert(!mGroup); } void LLViewerOctreeEntry::addData(LLViewerOctreeEntryData* data) { //llassert(mData[data->getDataType()] == NULL); llassert(data != NULL); mData[data->getDataType()] = data; } void LLViewerOctreeEntry::removeData(LLViewerOctreeEntryData* data) { //llassert(data->getDataType() != LLVOCACHEENTRY); //can not remove VOCache entry if(!mData[data->getDataType()]) { return; } if(mData[data->getDataType()] != data) { return; } mData[data->getDataType()] = NULL; if(mGroup != NULL && !mData[LLDRAWABLE]) { LLViewerOctreeGroup* group = mGroup; mGroup = NULL; group->removeFromGroup(data); llassert(mBinIndex == -1); } } //called by group handleDestruction() ONLY when group is destroyed by octree. void LLViewerOctreeEntry::nullGroup() { mGroup = NULL; } void LLViewerOctreeEntry::setGroup(LLViewerOctreeGroup* group) { if(mGroup == group) { return; } if(mGroup) { LLViewerOctreeGroup* old_group = mGroup; mGroup = NULL; old_group->removeFromGroup(this); llassert(mBinIndex == -1); } mGroup = group; } //----------------------------------------------------------------------------------- //class LLViewerOctreeEntryData definitions //----------------------------------------------------------------------------------- LLViewerOctreeEntryData::~LLViewerOctreeEntryData() { if(mEntry) { mEntry->removeData(this); } } LLViewerOctreeEntryData::LLViewerOctreeEntryData(LLViewerOctreeEntry::eEntryDataType_t data_type) : mDataType(data_type), mEntry(NULL) { } //virtual void LLViewerOctreeEntryData::setOctreeEntry(LLViewerOctreeEntry* entry) { llassert_always(mEntry.isNull()); if(mEntry.notNull()) { return; } if(!entry) { mEntry = new LLViewerOctreeEntry(); } else { mEntry = entry; } mEntry->addData(this); } void LLViewerOctreeEntryData::removeOctreeEntry() { if(mEntry) { mEntry->removeData(this); mEntry = NULL; } } void LLViewerOctreeEntryData::setSpatialExtents(const LLVector3& min, const LLVector3& max) { mEntry->mExtents[0].load3(min.mV); mEntry->mExtents[1].load3(max.mV); } void LLViewerOctreeEntryData::setSpatialExtents(const LLVector4a& min, const LLVector4a& max) { mEntry->mExtents[0] = min; mEntry->mExtents[1] = max; } void LLViewerOctreeEntryData::setPositionGroup(const LLVector4a& pos) { mEntry->mPositionGroup = pos; } const LLVector4a* LLViewerOctreeEntryData::getSpatialExtents() const { return mEntry->getSpatialExtents(); } //virtual void LLViewerOctreeEntryData::setGroup(LLViewerOctreeGroup* group) { mEntry->setGroup(group); } void LLViewerOctreeEntryData::shift(const LLVector4a &shift_vector) { mEntry->mExtents[0].add(shift_vector); mEntry->mExtents[1].add(shift_vector); mEntry->mPositionGroup.add(shift_vector); } LLViewerOctreeGroup* LLViewerOctreeEntryData::getGroup()const { return mEntry.notNull() ? mEntry->mGroup : NULL; } const LLVector4a& LLViewerOctreeEntryData::getPositionGroup() const { return mEntry->getPositionGroup(); } //virtual bool LLViewerOctreeEntryData::isVisible() const { if(mEntry) { return mEntry->mVisible == sCurVisible; } return false; } //virtual bool LLViewerOctreeEntryData::isRecentlyVisible() const { if(!mEntry) { return false; } if(isVisible()) { return true; } if(getGroup() && getGroup()->isRecentlyVisible()) { setVisible(); return true; } return false; } void LLViewerOctreeEntryData::setVisible() const { if(mEntry) { mEntry->mVisible = sCurVisible; } } void LLViewerOctreeEntryData::resetVisible() const { if(mEntry) { mEntry->mVisible = 0; } } //----------------------------------------------------------------------------------- //class LLViewerOctreeGroup definitions //----------------------------------------------------------------------------------- LLViewerOctreeGroup::~LLViewerOctreeGroup() { //empty here } LLViewerOctreeGroup::LLViewerOctreeGroup(OctreeNode* node) : mOctreeNode(node), mAnyVisible(0), mState(CLEAN) { LLVector4a tmp; tmp.splat(0.f); mExtents[0] = mExtents[1] = mObjectBounds[0] = mObjectBounds[1] = mObjectExtents[0] = mObjectExtents[1] = tmp; mBounds[0] = node->getCenter(); mBounds[1] = node->getSize(); mOctreeNode->addListener(this); } bool LLViewerOctreeGroup::hasElement(LLViewerOctreeEntryData* data) { if(!data->getEntry()) { return false; } return std::find(getDataBegin(), getDataEnd(), data->getEntry()) != getDataEnd(); } bool LLViewerOctreeGroup::removeFromGroup(LLViewerOctreeEntryData* data) { return removeFromGroup(data->getEntry()); } bool LLViewerOctreeGroup::removeFromGroup(LLViewerOctreeEntry* entry) { llassert(entry != NULL); llassert(!entry->getGroup()); if(isDead()) //group is about to be destroyed, not need to double delete the entry. { entry->setBinIndex(-1); return true; } unbound(); setState(OBJECT_DIRTY); if (mOctreeNode) { if (!mOctreeNode->remove(entry)) //this could cause *this* pointer to be destroyed, so no more function calls after this. { OCT_ERRS << "Could not remove LLVOCacheEntry from LLVOCacheOctreeGroup" << LL_ENDL; return false; } } return true; } //virtual void LLViewerOctreeGroup::unbound() { LL_PROFILE_ZONE_SCOPED; if (isDirty()) { return; } setState(DIRTY); //all the parent nodes need to rebound this child if (mOctreeNode) { OctreeNode* parent = (OctreeNode*) mOctreeNode->getParent(); while (parent != NULL) { LLViewerOctreeGroup* group = (LLViewerOctreeGroup*) parent->getListener(0); if (!group || group->isDirty()) { return; } group->setState(DIRTY); parent = (OctreeNode*) parent->getParent(); } } } //virtual void LLViewerOctreeGroup::rebound() { LL_PROFILE_ZONE_SCOPED_CATEGORY_OCTREE; if (!isDirty()) { return; } if (mOctreeNode->getChildCount() == 1 && mOctreeNode->getElementCount() == 0) { LLViewerOctreeGroup* group = (LLViewerOctreeGroup*) mOctreeNode->getChild(0)->getListener(0); group->rebound(); //copy single child's bounding box mBounds[0] = group->mBounds[0]; mBounds[1] = group->mBounds[1]; mExtents[0] = group->mExtents[0]; mExtents[1] = group->mExtents[1]; group->setState(SKIP_FRUSTUM_CHECK); } else if (mOctreeNode->getChildCount() == 0) { //copy object bounding box if this is a leaf boundObjects(true, mExtents[0], mExtents[1]); mBounds[0] = mObjectBounds[0]; mBounds[1] = mObjectBounds[1]; } else { LLVector4a& newMin = mExtents[0]; LLVector4a& newMax = mExtents[1]; LLViewerOctreeGroup* group = (LLViewerOctreeGroup*) mOctreeNode->getChild(0)->getListener(0); group->clearState(SKIP_FRUSTUM_CHECK); group->rebound(); //initialize to first child newMin = group->mExtents[0]; newMax = group->mExtents[1]; //first, rebound children for (U32 i = 1; i < mOctreeNode->getChildCount(); i++) { group = (LLViewerOctreeGroup*) mOctreeNode->getChild(i)->getListener(0); group->clearState(SKIP_FRUSTUM_CHECK); group->rebound(); const LLVector4a& max = group->mExtents[1]; const LLVector4a& min = group->mExtents[0]; newMax.setMax(newMax, max); newMin.setMin(newMin, min); } boundObjects(false, newMin, newMax); mBounds[0].setAdd(newMin, newMax); mBounds[0].mul(0.5f); mBounds[1].setSub(newMax, newMin); mBounds[1].mul(0.5f); } clearState(DIRTY); return; } //virtual void LLViewerOctreeGroup::handleInsertion(const TreeNode* node, LLViewerOctreeEntry* obj) { obj->setGroup(this); unbound(); setState(OBJECT_DIRTY); } //virtual void LLViewerOctreeGroup::handleRemoval(const TreeNode* node, LLViewerOctreeEntry* obj) { unbound(); setState(OBJECT_DIRTY); obj->setGroup(NULL); //this could cause *this* pointer to be destroyed. So no more function calls after this. } //virtual void LLViewerOctreeGroup::handleDestruction(const TreeNode* node) { if (isDead()) { return; } setState(DEAD); for (OctreeNode::element_iter i = mOctreeNode->getDataBegin(); i != mOctreeNode->getDataEnd(); ++i) { LLViewerOctreeEntry* obj = *i; if (obj && obj->getGroup() == this) { obj->nullGroup(); } } mOctreeNode = NULL; } //virtual void LLViewerOctreeGroup::handleStateChange(const TreeNode* node) { //drop bounding box upon state change if (mOctreeNode != node) { mOctreeNode = (OctreeNode*) node; } unbound(); } //virtual void LLViewerOctreeGroup::handleChildAddition(const OctreeNode* parent, OctreeNode* child) { if (child->getListenerCount() == 0) { new LLViewerOctreeGroup(child); } else { OCT_ERRS << "LLViewerOctreeGroup redundancy detected." << LL_ENDL; } unbound(); ((LLViewerOctreeGroup*)child->getListener(0))->unbound(); } //virtual void LLViewerOctreeGroup::handleChildRemoval(const OctreeNode* parent, const OctreeNode* child) { unbound(); } LLViewerOctreeGroup* LLViewerOctreeGroup::getParent() { if (isDead()) { return NULL; } if(!mOctreeNode) { return NULL; } OctreeNode* parent = mOctreeNode->getOctParent(); if (parent) { return (LLViewerOctreeGroup*) parent->getListener(0); } return NULL; } //virtual bool LLViewerOctreeGroup::boundObjects(bool empty, LLVector4a& minOut, LLVector4a& maxOut) { const OctreeNode* node = mOctreeNode; if (node->isEmpty()) { //don't do anything if there are no objects if (empty && mOctreeNode->getParent()) { //only root is allowed to be empty OCT_ERRS << "Empty leaf found in octree." << LL_ENDL; } return false; } LLVector4a& newMin = mObjectExtents[0]; LLVector4a& newMax = mObjectExtents[1]; if (hasState(OBJECT_DIRTY)) { //calculate new bounding box clearState(OBJECT_DIRTY); //initialize bounding box to first element OctreeNode::const_element_iter i = node->getDataBegin(); LLViewerOctreeEntry* entry = *i; const LLVector4a* minMax = entry->getSpatialExtents(); newMin = minMax[0]; newMax = minMax[1]; for (++i; i != node->getDataEnd(); ++i) { entry = *i; minMax = entry->getSpatialExtents(); update_min_max(newMin, newMax, minMax[0]); update_min_max(newMin, newMax, minMax[1]); } mObjectBounds[0].setAdd(newMin, newMax); mObjectBounds[0].mul(0.5f); mObjectBounds[1].setSub(newMax, newMin); mObjectBounds[1].mul(0.5f); } if (empty) { minOut = newMin; maxOut = newMax; } else { minOut.setMin(minOut, newMin); maxOut.setMax(maxOut, newMax); } return true; } //virtual bool LLViewerOctreeGroup::isVisible() const { return mVisible[LLViewerCamera::sCurCameraID] >= LLViewerOctreeEntryData::getCurrentFrame(); } //virtual bool LLViewerOctreeGroup::isRecentlyVisible() const { return false; } void LLViewerOctreeGroup::setVisible() { mVisible[LLViewerCamera::sCurCameraID] = LLViewerOctreeEntryData::getCurrentFrame(); if(LLViewerCamera::sCurCameraID < LLViewerCamera::CAMERA_WATER0) { mAnyVisible = LLViewerOctreeEntryData::getCurrentFrame(); } } void LLViewerOctreeGroup::checkStates() { #if LL_OCTREE_PARANOIA_CHECK //LLOctreeStateCheck checker; //checker.traverse(mOctreeNode); #endif } //------------------------------------------------------------------------------------------- //occulsion culling functions and classes //------------------------------------------------------------------------------------------- std::set<U32> LLOcclusionCullingGroup::sPendingQueries; static std::queue<GLuint> sFreeQueries; #define QUERY_POOL_SIZE 1024 U32 LLOcclusionCullingGroup::getNewOcclusionQueryObjectName() { LL_PROFILE_ZONE_SCOPED; if (sFreeQueries.empty()) { //seed 1024 query names into the free query pool GLuint queries[1024]; glGenQueries(1024, queries); for (int i = 0; i < 1024; ++i) { sFreeQueries.push(queries[i]); } } // pull from pool GLuint ret = sFreeQueries.front(); sFreeQueries.pop(); return ret; } void LLOcclusionCullingGroup::releaseOcclusionQueryObjectName(GLuint name) { if (name != 0) { LL_PROFILE_ZONE_SCOPED; sFreeQueries.push(name); } } //===================================== // Occlusion State Set/Clear //===================================== class LLSpatialSetOcclusionState : public OctreeTraveler { public: U32 mState; LLSpatialSetOcclusionState(U32 state) : mState(state) { } virtual void visit(const OctreeNode* branch) { LLOcclusionCullingGroup* group = (LLOcclusionCullingGroup*)branch->getListener(0); if(group) { group->setOcclusionState(mState); } } }; class LLSpatialSetOcclusionStateDiff : public LLSpatialSetOcclusionState { public: LLSpatialSetOcclusionStateDiff(U32 state) : LLSpatialSetOcclusionState(state) { } virtual void traverse(const OctreeNode* n) { LLOcclusionCullingGroup* group = (LLOcclusionCullingGroup*) n->getListener(0); if (group && !group->isOcclusionState(mState)) { OctreeTraveler::traverse(n); } } }; LLOcclusionCullingGroup::LLOcclusionCullingGroup(OctreeNode* node, LLViewerOctreePartition* part) : LLViewerOctreeGroup(node), mSpatialPartition(part) { part->mLODSeed = (part->mLODSeed+1)%part->mLODPeriod; mLODHash = part->mLODSeed; OctreeNode* oct_parent = node->getOctParent(); LLOcclusionCullingGroup* parent = oct_parent ? (LLOcclusionCullingGroup*) oct_parent->getListener(0) : NULL; for (U32 i = 0; i < LLViewerCamera::NUM_CAMERAS; i++) { mOcclusionQuery[i] = 0; mOcclusionCheckCount[i] = 0; mOcclusionIssued[i] = 0; mOcclusionState[i] = parent ? SG_STATE_INHERIT_MASK & parent->mOcclusionState[i] : 0; mVisible[i] = 0; } } LLOcclusionCullingGroup::~LLOcclusionCullingGroup() { releaseOcclusionQueryObjectNames(); } bool LLOcclusionCullingGroup::needsUpdate() { return LLDrawable::getCurrentFrame() % mSpatialPartition->mLODPeriod == mLODHash; } bool LLOcclusionCullingGroup::isRecentlyVisible() const { const S32 MIN_VIS_FRAME_RANGE = 2; return (LLDrawable::getCurrentFrame() - mVisible[LLViewerCamera::sCurCameraID]) < MIN_VIS_FRAME_RANGE ; } bool LLOcclusionCullingGroup::isAnyRecentlyVisible() const { const S32 MIN_VIS_FRAME_RANGE = 2; return (LLDrawable::getCurrentFrame() - mAnyVisible) < MIN_VIS_FRAME_RANGE ; } //virtual void LLOcclusionCullingGroup::handleChildAddition(const OctreeNode* parent, OctreeNode* child) { if (!child->hasListeners()) { new LLOcclusionCullingGroup(child, mSpatialPartition); } else { OCT_ERRS << "LLOcclusionCullingGroup redundancy detected." << LL_ENDL; } unbound(); ((LLViewerOctreeGroup*)child->getListener(0))->unbound(); } void LLOcclusionCullingGroup::releaseOcclusionQueryObjectNames() { for (U32 i = 0; i < LLViewerCamera::NUM_CAMERAS; ++i) { if (mOcclusionQuery[i]) { releaseOcclusionQueryObjectName(mOcclusionQuery[i]); mOcclusionQuery[i] = 0; } } } void LLOcclusionCullingGroup::setOcclusionState(U32 state, S32 mode /* = STATE_MODE_SINGLE */ ) { switch (mode) { case STATE_MODE_SINGLE: if (state & OCCLUDED) { add(sNumObjectsOccluded, 1); } mOcclusionState[LLViewerCamera::sCurCameraID] |= state; if ((state & DISCARD_QUERY) && mOcclusionQuery[LLViewerCamera::sCurCameraID]) { releaseOcclusionQueryObjectName(mOcclusionQuery[LLViewerCamera::sCurCameraID]); mOcclusionQuery[LLViewerCamera::sCurCameraID] = 0; } break; case STATE_MODE_DIFF: if (mOctreeNode) { LLSpatialSetOcclusionStateDiff setter(state); setter.traverse(mOctreeNode); } break; case STATE_MODE_BRANCH: if (mOctreeNode) { LLSpatialSetOcclusionState setter(state); setter.traverse(mOctreeNode); } break; case STATE_MODE_ALL_CAMERAS: for (U32 i = 0; i < LLViewerCamera::NUM_CAMERAS; i++) { mOcclusionState[i] |= state; if ((state & DISCARD_QUERY) && mOcclusionQuery[i]) { releaseOcclusionQueryObjectName(mOcclusionQuery[i]); mOcclusionQuery[i] = 0; } } break; default: break; } } class LLSpatialClearOcclusionState : public OctreeTraveler { public: U32 mState; LLSpatialClearOcclusionState(U32 state) : mState(state) { } virtual void visit(const OctreeNode* branch) { LLOcclusionCullingGroup* group = (LLOcclusionCullingGroup*)branch->getListener(0); if(group) { group->clearOcclusionState(mState); } } }; class LLSpatialClearOcclusionStateDiff : public LLSpatialClearOcclusionState { public: LLSpatialClearOcclusionStateDiff(U32 state) : LLSpatialClearOcclusionState(state) { } virtual void traverse(const OctreeNode* n) { LLOcclusionCullingGroup* group = (LLOcclusionCullingGroup*) n->getListener(0); if (group && group->isOcclusionState(mState)) { OctreeTraveler::traverse(n); } } }; void LLOcclusionCullingGroup::clearOcclusionState(U32 state, S32 mode /* = STATE_MODE_SINGLE */) { switch (mode) { case STATE_MODE_SINGLE: if (state & OCCLUDED) { add(sNumObjectsUnoccluded, 1); } mOcclusionState[LLViewerCamera::sCurCameraID] &= ~state; break; case STATE_MODE_DIFF: if (mOctreeNode) { LLSpatialClearOcclusionStateDiff clearer(state); clearer.traverse(mOctreeNode); } break; case STATE_MODE_BRANCH: if (mOctreeNode) { LLSpatialClearOcclusionState clearer(state); clearer.traverse(mOctreeNode); } break; case STATE_MODE_ALL_CAMERAS: for (U32 i = 0; i < LLViewerCamera::NUM_CAMERAS; i++) { mOcclusionState[i] &= ~state; } break; default: break; } } bool LLOcclusionCullingGroup::earlyFail(LLCamera* camera, const LLVector4a* bounds) { LL_PROFILE_ZONE_SCOPED_CATEGORY_OCTREE; if (camera->getOrigin().isExactlyZero()) { return false; } const F32 vel = SG_OCCLUSION_FUDGE*2.f; LLVector4a fudge; fudge.splat(vel); const LLVector4a& c = bounds[0]; LLVector4a r; r.setAdd(bounds[1], fudge); /*if (r.magVecSquared() > 1024.0*1024.0) { return true; }*/ LLVector4a e; e.load3(camera->getOrigin().mV); LLVector4a min; min.setSub(c,r); LLVector4a max; max.setAdd(c,r); S32 lt = e.lessThan(min).getGatheredBits() & 0x7; if (lt) { return false; } S32 gt = e.greaterThan(max).getGatheredBits() & 0x7; if (gt) { return false; } return true; } U32 LLOcclusionCullingGroup::getLastOcclusionIssuedTime() { return mOcclusionIssued[LLViewerCamera::sCurCameraID]; } void LLOcclusionCullingGroup::checkOcclusion() { if (LLPipeline::sUseOcclusion < 2) return; // 0 - NoOcclusion, 1 = ReadOnly, 2 = ModifyOcclusionState TODO: DJH 11-2021 ENUM this LL_PROFILE_ZONE_SCOPED_CATEGORY_OCTREE; LLOcclusionCullingGroup* parent = (LLOcclusionCullingGroup*)getParent(); if (parent && parent->isOcclusionState(LLOcclusionCullingGroup::OCCLUDED)) { //if the parent has been marked as occluded, the child is implicitly occluded clearOcclusionState(QUERY_PENDING | DISCARD_QUERY); return; } if (mOcclusionQuery[LLViewerCamera::sCurCameraID] && isOcclusionState(QUERY_PENDING)) { if (isOcclusionState(DISCARD_QUERY)) { // delete the query to avoid holding onto hundreds of pending queries releaseOcclusionQueryObjectName(mOcclusionQuery[LLViewerCamera::sCurCameraID]); mOcclusionQuery[LLViewerCamera::sCurCameraID] = 0; // mark non-occluded clearOcclusionState(LLOcclusionCullingGroup::OCCLUDED, LLOcclusionCullingGroup::STATE_MODE_DIFF); clearOcclusionState(QUERY_PENDING | DISCARD_QUERY); } else { GLuint available; { LL_PROFILE_ZONE_NAMED_CATEGORY_OCTREE("co - query available"); glGetQueryObjectuiv(mOcclusionQuery[LLViewerCamera::sCurCameraID], GL_QUERY_RESULT_AVAILABLE, &available); mOcclusionCheckCount[LLViewerCamera::sCurCameraID]++; } static LLCachedControl<U32> occlusion_timeout(gSavedSettings, "RenderOcclusionTimeout", 4); if (available || mOcclusionCheckCount[LLViewerCamera::sCurCameraID] > occlusion_timeout) { mOcclusionCheckCount[LLViewerCamera::sCurCameraID] = 0; GLuint query_result; // Will be # samples drawn, or a boolean depending on mHasOcclusionQuery2 (both are type GLuint) { LL_PROFILE_ZONE_NAMED_CATEGORY_OCTREE("co - query result"); glGetQueryObjectuiv(mOcclusionQuery[LLViewerCamera::sCurCameraID], GL_QUERY_RESULT, &query_result); } #if LL_TRACK_PENDING_OCCLUSION_QUERIES sPendingQueries.erase(mOcclusionQuery[LLViewerCamera::sCurCameraID]); #endif if (query_result > 0) { clearOcclusionState(LLOcclusionCullingGroup::OCCLUDED, LLOcclusionCullingGroup::STATE_MODE_DIFF); } else { setOcclusionState(LLOcclusionCullingGroup::OCCLUDED, LLOcclusionCullingGroup::STATE_MODE_DIFF); } clearOcclusionState(QUERY_PENDING); } } } else if (mSpatialPartition->isOcclusionEnabled() && isOcclusionState(LLOcclusionCullingGroup::OCCLUDED)) { //check occlusion has been issued for occluded node that has not had a query issued assert_states_valid(this); //clearOcclusionState(LLOcclusionCullingGroup::OCCLUDED, LLOcclusionCullingGroup::STATE_MODE_DIFF); assert_states_valid(this); } } void LLOcclusionCullingGroup::doOcclusion(LLCamera* camera, const LLVector4a* shift) { LL_PROFILE_ZONE_SCOPED_CATEGORY_OCTREE; if (mSpatialPartition->isOcclusionEnabled() && LLPipeline::sUseOcclusion > 1) { //move mBounds to the agent space if necessary LLVector4a bounds[2]; bounds[0] = mBounds[0]; bounds[1] = mBounds[1]; if(shift != NULL) { bounds[0].add(*shift); } F32 OCCLUSION_FUDGE_Z = SG_OCCLUSION_FUDGE; //<-- #Solution #2 if (LLPipeline::RENDER_TYPE_VOIDWATER == mSpatialPartition->mDrawableType) { OCCLUSION_FUDGE_Z = 1.; } if (earlyFail(camera, bounds)) { LL_PROFILE_ZONE_NAMED_CATEGORY_OCTREE("doOcclusion - early fail"); setOcclusionState(LLOcclusionCullingGroup::DISCARD_QUERY); assert_states_valid(this); clearOcclusionState(LLOcclusionCullingGroup::OCCLUDED, LLOcclusionCullingGroup::STATE_MODE_DIFF); assert_states_valid(this); } else { if (!isOcclusionState(QUERY_PENDING) || isOcclusionState(DISCARD_QUERY)) { { //no query pending, or previous query to be discarded LL_PROFILE_ZONE_NAMED_CATEGORY_OCTREE("doOcclusion - render"); if (!mOcclusionQuery[LLViewerCamera::sCurCameraID]) { mOcclusionQuery[LLViewerCamera::sCurCameraID] = getNewOcclusionQueryObjectName(); } // Depth clamp all water to avoid it being culled as a result of being // behind the far clip plane, and in the case of edge water to avoid // it being culled while still visible. bool const use_depth_clamp = (mSpatialPartition->mDrawableType == LLPipeline::RENDER_TYPE_WATER || mSpatialPartition->mDrawableType == LLPipeline::RENDER_TYPE_VOIDWATER); LLGLEnable clamp(use_depth_clamp ? GL_DEPTH_CLAMP : 0); U32 mode = gGLManager.mGLVersion >= 3.3f ? GL_ANY_SAMPLES_PASSED : GL_SAMPLES_PASSED; #if LL_TRACK_PENDING_OCCLUSION_QUERIES sPendingQueries.insert(mOcclusionQuery[LLViewerCamera::sCurCameraID]); #endif add(sOcclusionQueries, 1); { LL_PROFILE_ZONE_NAMED_CATEGORY_OCTREE("doOcclusion - push"); //store which frame this query was issued on mOcclusionIssued[LLViewerCamera::sCurCameraID] = gFrameCount; { LL_PROFILE_ZONE_NAMED("glBeginQuery"); //get an occlusion query that hasn't been used in awhile releaseOcclusionQueryObjectName(mOcclusionQuery[LLViewerCamera::sCurCameraID]); mOcclusionQuery[LLViewerCamera::sCurCameraID] = getNewOcclusionQueryObjectName(); glBeginQuery(mode, mOcclusionQuery[LLViewerCamera::sCurCameraID]); } LLGLSLShader* shader = LLGLSLShader::sCurBoundShaderPtr; llassert(shader); shader->uniform3fv(LLShaderMgr::BOX_CENTER, 1, bounds[0].getF32ptr()); shader->uniform3f(LLShaderMgr::BOX_SIZE, bounds[1][0]+SG_OCCLUSION_FUDGE, bounds[1][1]+SG_OCCLUSION_FUDGE, bounds[1][2]+OCCLUSION_FUDGE_Z); if (!use_depth_clamp && mSpatialPartition->mDrawableType == LLPipeline::RENDER_TYPE_VOIDWATER) { LL_PROFILE_ZONE_NAMED_CATEGORY_OCTREE("doOcclusion - draw water"); LLGLSquashToFarClip squash; if (camera->getOrigin().isExactlyZero()) { //origin is invalid, draw entire box gPipeline.mCubeVB->drawRange(LLRender::TRIANGLE_FAN, 0, 7, 8, 0); gPipeline.mCubeVB->drawRange(LLRender::TRIANGLE_FAN, 0, 7, 8, b111*8); } else { gPipeline.mCubeVB->drawRange(LLRender::TRIANGLE_FAN, 0, 7, 8, get_box_fan_indices(camera, bounds[0])); } } else { LL_PROFILE_ZONE_NAMED_CATEGORY_OCTREE("doOcclusion - draw"); if (camera->getOrigin().isExactlyZero()) { //origin is invalid, draw entire box gPipeline.mCubeVB->drawRange(LLRender::TRIANGLE_FAN, 0, 7, 8, 0); gPipeline.mCubeVB->drawRange(LLRender::TRIANGLE_FAN, 0, 7, 8, b111*8); } else { gPipeline.mCubeVB->drawRange(LLRender::TRIANGLE_FAN, 0, 7, 8, get_box_fan_indices(camera, bounds[0])); } } { LL_PROFILE_ZONE_NAMED("glEndQuery"); glEndQuery(mode); } } } { LL_PROFILE_ZONE_NAMED_CATEGORY_OCTREE("doOcclusion - set state"); setOcclusionState(LLOcclusionCullingGroup::QUERY_PENDING); clearOcclusionState(LLOcclusionCullingGroup::DISCARD_QUERY); } } } } } //------------------------------------------------------------------------------------------- //end of occulsion culling functions and classes //------------------------------------------------------------------------------------------- //----------------------------------------------------------------------------------- //class LLViewerOctreePartition definitions //----------------------------------------------------------------------------------- LLViewerOctreePartition::LLViewerOctreePartition() : mRegionp(NULL), mOcclusionEnabled(true), mDrawableType(0), mLODSeed(0), mLODPeriod(1) { LLVector4a center, size; center.splat(0.f); size.splat(1.f); mOctree = new OctreeRoot(center,size, NULL); } LLViewerOctreePartition::~LLViewerOctreePartition() { cleanup(); } void LLViewerOctreePartition::cleanup() { delete mOctree; mOctree = nullptr; } bool LLViewerOctreePartition::isOcclusionEnabled() { return mOcclusionEnabled || LLPipeline::sUseOcclusion > 2; } //----------------------------------------------------------------------------------- //class LLViewerOctreeCull definitions //----------------------------------------------------------------------------------- //virtual bool LLViewerOctreeCull::earlyFail(LLViewerOctreeGroup* group) { return false; } //virtual void LLViewerOctreeCull::traverse(const OctreeNode* n) { LLViewerOctreeGroup* group = (LLViewerOctreeGroup*) n->getListener(0); if (earlyFail(group)) { return; } if (mRes == 2 || (mRes && group->hasState(LLViewerOctreeGroup::SKIP_FRUSTUM_CHECK))) { //fully in, just add everything OctreeTraveler::traverse(n); } else { mRes = frustumCheck(group); if (mRes) { //at least partially in, run on down OctreeTraveler::traverse(n); } mRes = 0; } } //------------------------------------------ //agent space group culling S32 LLViewerOctreeCull::AABBInFrustumNoFarClipGroupBounds(const LLViewerOctreeGroup* group) { return mCamera->AABBInFrustumNoFarClip(group->mBounds[0], group->mBounds[1]); } S32 LLViewerOctreeCull::AABBSphereIntersectGroupExtents(const LLViewerOctreeGroup* group) { return AABBSphereIntersect(group->mExtents[0], group->mExtents[1], mCamera->getOrigin(), mCamera->mFrustumCornerDist); } S32 LLViewerOctreeCull::AABBInFrustumGroupBounds(const LLViewerOctreeGroup* group) { return mCamera->AABBInFrustum(group->mBounds[0], group->mBounds[1]); } //------------------------------------------ //------------------------------------------ //agent space object set culling S32 LLViewerOctreeCull::AABBInFrustumNoFarClipObjectBounds(const LLViewerOctreeGroup* group) { return mCamera->AABBInFrustumNoFarClip(group->mObjectBounds[0], group->mObjectBounds[1]); } S32 LLViewerOctreeCull::AABBSphereIntersectObjectExtents(const LLViewerOctreeGroup* group) { return AABBSphereIntersect(group->mObjectExtents[0], group->mObjectExtents[1], mCamera->getOrigin(), mCamera->mFrustumCornerDist); } S32 LLViewerOctreeCull::AABBInFrustumObjectBounds(const LLViewerOctreeGroup* group) { return mCamera->AABBInFrustum(group->mObjectBounds[0], group->mObjectBounds[1]); } //------------------------------------------ //------------------------------------------ //local regional space group culling S32 LLViewerOctreeCull::AABBInRegionFrustumNoFarClipGroupBounds(const LLViewerOctreeGroup* group) { return mCamera->AABBInRegionFrustumNoFarClip(group->mBounds[0], group->mBounds[1]); } S32 LLViewerOctreeCull::AABBInRegionFrustumGroupBounds(const LLViewerOctreeGroup* group) { return mCamera->AABBInRegionFrustum(group->mBounds[0], group->mBounds[1]); } S32 LLViewerOctreeCull::AABBRegionSphereIntersectGroupExtents(const LLViewerOctreeGroup* group, const LLVector3& shift) { return AABBSphereIntersect(group->mExtents[0], group->mExtents[1], mCamera->getOrigin() - shift, mCamera->mFrustumCornerDist); } //------------------------------------------ //------------------------------------------ //local regional space object culling S32 LLViewerOctreeCull::AABBInRegionFrustumObjectBounds(const LLViewerOctreeGroup* group) { return mCamera->AABBInRegionFrustum(group->mObjectBounds[0], group->mObjectBounds[1]); } S32 LLViewerOctreeCull::AABBInRegionFrustumNoFarClipObjectBounds(const LLViewerOctreeGroup* group) { return mCamera->AABBInRegionFrustumNoFarClip(group->mObjectBounds[0], group->mObjectBounds[1]); } S32 LLViewerOctreeCull::AABBRegionSphereIntersectObjectExtents(const LLViewerOctreeGroup* group, const LLVector3& shift) { return AABBSphereIntersect(group->mObjectExtents[0], group->mObjectExtents[1], mCamera->getOrigin() - shift, mCamera->mFrustumCornerDist); } //------------------------------------------ //check if the objects projection large enough bool LLViewerOctreeCull::checkProjectionArea(const LLVector4a& center, const LLVector4a& size, const LLVector3& shift, F32 pixel_threshold, F32 near_radius) { LLVector3 local_orig = mCamera->getOrigin() - shift; LLVector4a origin; origin.load3(local_orig.mV); LLVector4a lookAt; lookAt.setSub(center, origin); F32 distance = lookAt.getLength3().getF32(); if(distance <= near_radius) { return true; //always load close-by objects } // treat object as if it were near_radius meters closer than it actually was. // this allows us to get some temporal coherence on visibility...objects that can be reached quickly will tend to be visible distance -= near_radius; F32 squared_rad = size.dot3(size).getF32(); return squared_rad / distance > pixel_threshold; } //virtual bool LLViewerOctreeCull::checkObjects(const OctreeNode* branch, const LLViewerOctreeGroup* group) { if (branch->getElementCount() == 0) //no elements { return false; } else if (branch->getChildCount() == 0) //leaf state, already checked tightest bounding box { return true; } else if (mRes == 1 && !frustumCheckObjects(group)) //no objects in frustum { return false; } return true; } //virtual void LLViewerOctreeCull::preprocess(LLViewerOctreeGroup* group) { } //virtual void LLViewerOctreeCull::processGroup(LLViewerOctreeGroup* group) { } //virtual void LLViewerOctreeCull::visit(const OctreeNode* branch) { LLViewerOctreeGroup* group = (LLViewerOctreeGroup*) branch->getListener(0); preprocess(group); if (checkObjects(branch, group)) { processGroup(group); } } //-------------------------------------------------------------- //class LLViewerOctreeDebug //virtual void LLViewerOctreeDebug::visit(const OctreeNode* branch) { #if 0 LL_INFOS() << "Node: " << (U32)branch << " # Elements: " << branch->getElementCount() << " # Children: " << branch->getChildCount() << LL_ENDL; for (U32 i = 0; i < branch->getChildCount(); i++) { LL_INFOS() << "Child " << i << " : " << (U32)branch->getChild(i) << LL_ENDL; } #endif LLViewerOctreeGroup* group = (LLViewerOctreeGroup*) branch->getListener(0); processGroup(group); } //virtual void LLViewerOctreeDebug::processGroup(LLViewerOctreeGroup* group) { #if 0 const LLVector4a* vec4 = group->getBounds(); LLVector3 vec[2]; vec[0].set(vec4[0].getF32ptr()); vec[1].set(vec4[1].getF32ptr()); LL_INFOS() << "Bounds: " << vec[0] << " : " << vec[1] << LL_ENDL; vec4 = group->getExtents(); vec[0].set(vec4[0].getF32ptr()); vec[1].set(vec4[1].getF32ptr()); LL_INFOS() << "Extents: " << vec[0] << " : " << vec[1] << LL_ENDL; vec4 = group->getObjectBounds(); vec[0].set(vec4[0].getF32ptr()); vec[1].set(vec4[1].getF32ptr()); LL_INFOS() << "ObjectBounds: " << vec[0] << " : " << vec[1] << LL_ENDL; vec4 = group->getObjectExtents(); vec[0].set(vec4[0].getF32ptr()); vec[1].set(vec4[1].getF32ptr()); LL_INFOS() << "ObjectExtents: " << vec[0] << " : " << vec[1] << LL_ENDL; #endif } //--------------------------------------------------------------