diff options
Diffstat (limited to 'indra/newview/llspatialpartition.cpp')
| -rw-r--r-- | indra/newview/llspatialpartition.cpp | 2255 |
1 files changed, 2255 insertions, 0 deletions
diff --git a/indra/newview/llspatialpartition.cpp b/indra/newview/llspatialpartition.cpp new file mode 100644 index 0000000000..8b5db02c85 --- /dev/null +++ b/indra/newview/llspatialpartition.cpp @@ -0,0 +1,2255 @@ +/** + * @file llspatialpartition.cpp + * @brief LLSpatialGroup class implementation and supporting functions + * + * Copyright (c) 2003-$CurrentYear$, Linden Research, Inc. + * $License$ + */ + +#include "llviewerprecompiledheaders.h" + +#include "llspatialpartition.h" + +#include "llglheaders.h" + +#include "llviewerobjectlist.h" +#include "llvovolume.h" +#include "llviewercamera.h" +#include "llface.h" +#include "viewer.h" + +#include "llcamera.h" +#include "pipeline.h" + +static BOOL sIgnoreOcclusion = TRUE; +static GLuint sBoxList = 0; + +const S32 SG_LOD_SWITCH_STAGGER = 4; +const F32 SG_MAX_OBJ_RAD = 1.f; +const F32 SG_OCCLUSION_FUDGE = 1.1f; +const S32 SG_MOVE_PERIOD = 32; +const S32 SG_LOD_PERIOD = 16; + +#define SG_DISCARD_TOLERANCE 0.25f + +#if LL_OCTREE_PARANOIA_CHECK +#define assert_octree_valid(x) x->validate() +#else +#define assert_octree_valid(x) +#endif + +static F32 sLastMaxTexPriority = 1.f; +static F32 sCurMaxTexPriority = 1.f; + +//static counter for frame to switch LOD on +S32 LLSpatialGroup::sLODSeed = 0; + +void sg_assert(BOOL expr) +{ +#if LL_OCTREE_PARANOIA_CHECK + if (!expr) + { + llerrs << "Octree invalid!" << llendl; + } +#endif +} + +#if !LL_RELEASE_FOR_DOWNLOAD +void validate_drawable(LLDrawable* drawablep) +{ + F64 rad = drawablep->getBinRadius(); + const LLVector3* ext = drawablep->getSpatialExtents(); + + if (rad < 0 || rad > 4096 || + (ext[1]-ext[0]).magVec() > 4096) + { + llwarns << "Invalid drawable found in octree." << llendl; + } +} +#else +#define validate_drawable(x) +#endif + +BOOL earlyFail(LLCamera* camera, LLSpatialGroup* group); + +BOOL LLLineSegmentAABB(const LLVector3& start, const LLVector3& end, const LLVector3& center, const LLVector3& size) +{ + float fAWdU[3]; + LLVector3 dir; + LLVector3 diff; + + for (U32 i = 0; i < 3; i++) + { + dir.mV[i] = 0.5f * (end.mV[i] - start.mV[i]); + diff.mV[i] = (0.5f * (end.mV[i] + start.mV[i])) - center.mV[i]; + fAWdU[i] = fabsf(dir.mV[i]); + if(fabsf(diff.mV[i])>size.mV[i] + fAWdU[i]) return false; + } + + float f; + f = dir.mV[1] * diff.mV[2] - dir.mV[2] * diff.mV[1]; if(fabsf(f)>size.mV[1]*fAWdU[2] + size.mV[2]*fAWdU[1]) return false; + f = dir.mV[2] * diff.mV[0] - dir.mV[0] * diff.mV[2]; if(fabsf(f)>size.mV[0]*fAWdU[2] + size.mV[2]*fAWdU[0]) return false; + f = dir.mV[0] * diff.mV[1] - dir.mV[1] * diff.mV[0]; if(fabsf(f)>size.mV[0]*fAWdU[1] + size.mV[1]*fAWdU[0]) return false; + + return true; +} + +//returns: +// 0 if sphere and AABB are not intersecting +// 1 if they are +// 2 if AABB is entirely inside sphere + +S32 LLSphereAABB(const LLVector3& center, const LLVector3& size, const LLVector3& pos, const F32 &rad) +{ + S32 ret = 2; + + LLVector3 min = center - size; + LLVector3 max = center + size; + for (U32 i = 0; i < 3; i++) + { + if (min.mV[i] > pos.mV[i] + rad || + max.mV[i] < pos.mV[i] - rad) + { //totally outside + return 0; + } + + if (min.mV[i] < pos.mV[i] - rad || + max.mV[i] > pos.mV[i] + rad) + { //intersecting + ret = 1; + } + } + + return ret; +} + +LLSpatialGroup::~LLSpatialGroup() +{ + LLMemType mt(LLMemType::MTYPE_SPACE_PARTITION); + if (!safeToDelete()) + { +#ifdef LL_RELEASE_FOR_DOWNLOAD + llwarns << "Spatial Group deleted while being tracked " << ((void*) mState) << llendl; +#else + llerrs << "Spatial Group deleted while being tracked " << ((void*) mState) << llendl; +#endif + } + +#if LL_OCTREE_PARANOIA_CHECK + for (U32 i = 0; i < mSpatialPartition->mOccludedList.size(); i++) + { + if (mSpatialPartition->mOccludedList[i] == this) + { + llerrs << "Spatial Group deleted while being tracked STATE ERROR " << ((void*) mState) << llendl; + } + } +#endif +} + +BOOL LLSpatialGroup::safeToDelete() +{ + return gQuit || !isState(IN_QUEUE | ACTIVE_OCCLUSION | RESHADOW_QUEUE); +} + +class LLRelightPainter : public LLSpatialGroup::OctreeTraveler +{ +public: + LLVector3 mOrigin, mDir; + F32 mRadius; + + LLRelightPainter(LLVector3 origin, LLVector3 dir, F32 radius) + : mOrigin(origin), mDir(dir), mRadius(radius) + { } + + virtual void traverse(const LLSpatialGroup::TreeNode* n) + { + LLSpatialGroup::OctreeNode* node = (LLSpatialGroup::OctreeNode*) n; + + LLSpatialGroup* group = (LLSpatialGroup*) node->getListener(0); + group->setState(LLSpatialGroup::RESHADOW); + + for (U32 i = 0; i < node->getChildCount(); i++) + { + const LLSpatialGroup::OctreeNode* child = node->getChild(i); + LLSpatialGroup* group = (LLSpatialGroup*) child->getListener(0); + + LLVector3 res; + + LLVector3 center, size; + + center = group->mBounds[0]; + size = group->mBounds[1]; + + if (child->isInside(LLVector3d(mOrigin)) || LLRayAABB(center, size, mOrigin, mDir, res, mRadius)) + { + traverse(child); + } + } + } + + virtual void visit(const LLSpatialGroup::OctreeState* branch) { } + +}; + +BOOL LLSpatialGroup::isVisible() +{ + if (sIgnoreOcclusion) + { + return !isState(CULLED); + } + else + { + return !isState(CULLED | OCCLUDED); + } +} + +void LLSpatialGroup::validate() +{ +#if LL_OCTREE_PARANOIA_CHECK + + sg_assert(!isState(DIRTY)); + + LLVector3 myMin = mBounds[0] - mBounds[1]; + LLVector3 myMax = mBounds[0] + mBounds[1]; + + for (U32 i = 0; i < mOctreeNode->getChildCount(); ++i) + { + LLSpatialGroup* group = (LLSpatialGroup*) mOctreeNode->getChild(i)->getListener(0); + + group->validate(); + + //ensure all children are enclosed in this node + LLVector3 center = group->mBounds[0]; + LLVector3 size = group->mBounds[1]; + + LLVector3 min = center - size; + LLVector3 max = center + size; + + for (U32 j = 0; j < 3; j++) + { + sg_assert(min.mV[j] >= myMin.mV[j]-0.02f); + sg_assert(max.mV[j] <= myMax.mV[j]+0.02f); + } + } + +#endif +} + +BOOL LLSpatialGroup::updateInGroup(LLDrawable *drawablep, BOOL immediate) +{ + LLMemType mt(LLMemType::MTYPE_SPACE_PARTITION); + + drawablep->updateSpatialExtents(); + validate_drawable(drawablep); + + if (mOctreeNode->isInside(drawablep) && mOctreeNode->contains(drawablep)) + { + unbound(); + setState(OBJECT_DIRTY); + validate_drawable(drawablep); + return TRUE; + } + + return FALSE; +} + + +BOOL LLSpatialGroup::addObject(LLDrawable *drawablep, BOOL add_all, BOOL from_octree) +{ + LLMemType mt(LLMemType::MTYPE_SPACE_PARTITION); + if (!from_octree) + { + mOctreeNode->insert(drawablep); + } + else + { + drawablep->setSpatialGroup(this, 0); + validate_drawable(drawablep); + } + + return TRUE; +} + +BOOL LLSpatialGroup::boundObjects(BOOL empty, LLVector3& minOut, LLVector3& maxOut) +{ + const OctreeState* node = mOctreeNode->getOctState(); + + if (node->getData().empty()) + { //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." << llendl; + } + return FALSE; + } + + LLVector3& newMin = mObjectExtents[0]; + LLVector3& newMax = mObjectExtents[1]; + + if (isState(OBJECT_DIRTY)) + { //calculate new bounding box + clearState(OBJECT_DIRTY); + + //initialize bounding box to first element + OctreeState::const_element_iter i = node->getData().begin(); + LLDrawable* drawablep = *i; + const LLVector3* minMax = drawablep->getSpatialExtents(); + + newMin.setVec(minMax[0]); + newMax.setVec(minMax[1]); + + for (++i; i != node->getData().end(); ++i) + { + drawablep = *i; + minMax = drawablep->getSpatialExtents(); + + //bin up the object + for (U32 i = 0; i < 3; i++) + { + if (minMax[0].mV[i] < newMin.mV[i]) + { + newMin.mV[i] = minMax[0].mV[i]; + } + if (minMax[1].mV[i] > newMax.mV[i]) + { + newMax.mV[i] = minMax[1].mV[i]; + } + } + } + + mObjectBounds[0] = (newMin + newMax) * 0.5f; + mObjectBounds[1] = (newMax - newMin) * 0.5f; + } + + if (empty) + { + minOut = newMin; + maxOut = newMax; + } + else + { + for (U32 i = 0; i < 3; i++) + { + if (newMin.mV[i] < minOut.mV[i]) + { + minOut.mV[i] = newMin.mV[i]; + } + if (newMax.mV[i] > maxOut.mV[i]) + { + maxOut.mV[i] = newMax.mV[i]; + } + } + } + + return TRUE; +} + +void LLSpatialGroup::unbound() +{ + if (isState(DIRTY)) + { + return; + } + + setState(DIRTY); + + //all the parent nodes need to rebound this child + if (mOctreeNode) + { + OctreeNode* parent = (OctreeNode*) mOctreeNode->getParent(); + while (parent != NULL) + { + LLSpatialGroup* group = (LLSpatialGroup*) parent->getListener(0); + if (group->isState(DIRTY)) + { + return; + } + + group->setState(DIRTY); + parent = (OctreeNode*) parent->getParent(); + } + } +} + +BOOL LLSpatialGroup::removeObject(LLDrawable *drawablep, BOOL from_octree) +{ + LLMemType mt(LLMemType::MTYPE_SPACE_PARTITION); + unbound(); + if (!from_octree) + { + if (!mOctreeNode->remove(drawablep)) + { + OCT_ERRS << "Could not remove drawable from spatial group" << llendl; + } + } + else + { + drawablep->setSpatialGroup(NULL, -1); + } + return TRUE; +} + +void LLSpatialGroup::shift(const LLVector3 &offset) +{ + LLMemType mt(LLMemType::MTYPE_SPACE_PARTITION); + LLVector3d offsetd(offset); + mOctreeNode->setCenter(mOctreeNode->getCenter()+offsetd); + mOctreeNode->updateMinMax(); + mBounds[0] += offset; + mExtents[0] += offset; + mExtents[1] += offset; + mObjectBounds[0] += offset; + mObjectExtents[0] += offset; + mObjectExtents[1] += offset; +} + +class LLSpatialSetState : public LLSpatialGroup::OctreeTraveler +{ +public: + U32 mState; + LLSpatialSetState(U32 state) : mState(state) { } + virtual void visit(const LLSpatialGroup::OctreeState* branch) { ((LLSpatialGroup*) branch->getListener(0))->setState(mState); } +}; + +class LLSpatialSetStateDiff : public LLSpatialSetState +{ +public: + LLSpatialSetStateDiff(U32 state) : LLSpatialSetState(state) { } + + virtual void traverse(const LLSpatialGroup::TreeNode* n) + { + LLSpatialGroup* group = (LLSpatialGroup*) n->getListener(0); + + if (!group->isState(mState)) + { + LLSpatialGroup::OctreeTraveler::traverse(n); + } + } +}; + +void LLSpatialGroup::setState(U32 state, S32 mode) +{ + LLMemType mt(LLMemType::MTYPE_SPACE_PARTITION); + if (mode > STATE_MODE_SINGLE) + { + if (mode == STATE_MODE_DIFF) + { + LLSpatialSetStateDiff setter(state); + setter.traverse(mOctreeNode); + } + else + { + LLSpatialSetState setter(state); + setter.traverse(mOctreeNode); + } + } + else + { + mState |= state; + } +} + +class LLSpatialClearState : public LLSpatialGroup::OctreeTraveler +{ +public: + U32 mState; + LLSpatialClearState(U32 state) : mState(state) { } + virtual void visit(const LLSpatialGroup::OctreeState* branch) { ((LLSpatialGroup*) branch->getListener(0))->clearState(mState); } +}; + +class LLSpatialClearStateDiff : public LLSpatialClearState +{ +public: + LLSpatialClearStateDiff(U32 state) : LLSpatialClearState(state) { } + + virtual void traverse(const LLSpatialGroup::TreeNode* n) + { + LLSpatialGroup* group = (LLSpatialGroup*) n->getListener(0); + + if (!group->isState(mState)) + { + LLSpatialGroup::OctreeTraveler::traverse(n); + } + } +}; + + +void LLSpatialGroup::clearState(U32 state, S32 mode) +{ + LLMemType mt(LLMemType::MTYPE_SPACE_PARTITION); + if (mode > STATE_MODE_SINGLE) + { + if (mode == STATE_MODE_DIFF) + { + LLSpatialClearStateDiff clearer(state); + clearer.traverse(mOctreeNode); + } + else + { + LLSpatialClearState clearer(state); + clearer.traverse(mOctreeNode); + } + } + else + { + mState &= ~state; + } + +#if LL_OCTREE_PARANOIA_CHECK + if (state & LLSpatialGroup::ACTIVE_OCCLUSION) + { + LLSpatialPartition* part = mSpatialPartition; + for (U32 i = 0; i < part->mOccludedList.size(); i++) + { + if (part->mOccludedList[i] == this) + { + llerrs << "LLSpatialGroup state error: " << mState << llendl; + } + } + } +#endif +} + +//====================================== +// Octree Listener Implementation +//====================================== + +LLSpatialGroup::LLSpatialGroup(OctreeNode* node, LLSpatialPartition* part) +: mState(0), mOctreeNode(node), mSpatialPartition(part) +{ + LLMemType mt(LLMemType::MTYPE_SPACE_PARTITION); + sg_assert(mOctreeNode->getListenerCount() == 0); + mOctreeNode->addListener(this); + setState(DIRTY); + + mBounds[0] = LLVector3(node->getCenter()); + mBounds[1] = LLVector3(node->getSize()); + + sLODSeed = (sLODSeed+1)%SG_LOD_PERIOD; + mLODHash = sLODSeed; +} + +BOOL LLSpatialGroup::changeLOD() +{ + return LLDrawable::getCurrentFrame()%SG_LOD_PERIOD == mLODHash; +} + +void LLSpatialGroup::handleInsertion(const TreeNode* node, LLDrawable* drawable) +{ + LLMemType mt(LLMemType::MTYPE_SPACE_PARTITION); + addObject(drawable, FALSE, TRUE); + unbound(); + setState(OBJECT_DIRTY); +} + +void LLSpatialGroup::handleRemoval(const TreeNode* node, LLDrawable* drawable) +{ + LLMemType mt(LLMemType::MTYPE_SPACE_PARTITION); + removeObject(drawable, TRUE); + setState(OBJECT_DIRTY); +} + +void LLSpatialGroup::handleDestruction(const TreeNode* node) +{ + LLMemType mt(LLMemType::MTYPE_SPACE_PARTITION); + + if (mOctreeNode) + { + OctreeState* state = mOctreeNode->getOctState(); + for (OctreeState::element_iter i = state->getData().begin(); i != state->getData().end(); ++i) + { + LLDrawable* drawable = *i; + if (!drawable->isDead()) + { + drawable->setSpatialGroup(NULL, -1); + } + } + } + + if (safeToDelete()) + { + delete this; + } + else + { + setState(DEAD); + mOctreeNode = NULL; + } +} + +void LLSpatialGroup::handleStateChange(const TreeNode* node) +{ + //drop bounding box upon state change + if (mOctreeNode != node) + { + mOctreeNode = (OctreeNode*) node; + } + unbound(); +} + +void LLSpatialGroup::handleChildAddition(const OctreeNode* parent, OctreeNode* child) +{ + LLMemType mt(LLMemType::MTYPE_SPACE_PARTITION); + if (child->getListenerCount() == 0) + { + (new LLSpatialGroup(child, mSpatialPartition))->setState(mState & SG_STATE_INHERIT_MASK); + } + else + { + OCT_ERRS << "LLSpatialGroup redundancy detected." << llendl; + } + + unbound(); +} + +void LLSpatialGroup::handleChildRemoval(const OctreeNode* parent, const OctreeNode* child) +{ + unbound(); +} + +BOOL LLSpatialGroup::rebound() +{ + if (!isState(DIRTY)) + { //return TRUE if we're not empty + return TRUE; + } + + LLVector3 oldBounds[2]; + + if (isState(QUERY_OUT)) + { //a query has been issued, if our bounding box changes significantly + //we need to discard the issued query + oldBounds[0] = mBounds[0]; + oldBounds[1] = mBounds[1]; + } + + if (mOctreeNode->getChildCount() == 1 && mOctreeNode->getElementCount() == 0) + { + LLSpatialGroup* group = (LLSpatialGroup*) 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->hasLeafState()) + { //copy object bounding box if this is a leaf + boundObjects(TRUE, mExtents[0], mExtents[1]); + mBounds[0] = mObjectBounds[0]; + mBounds[1] = mObjectBounds[1]; + } + else + { + LLVector3& newMin = mExtents[0]; + LLVector3& newMax = mExtents[1]; + LLSpatialGroup* group = (LLSpatialGroup*) 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 = (LLSpatialGroup*) mOctreeNode->getChild(i)->getListener(0); + group->clearState(SKIP_FRUSTUM_CHECK); + group->rebound(); + const LLVector3& max = group->mExtents[1]; + const LLVector3& min = group->mExtents[0]; + + for (U32 j = 0; j < 3; j++) + { + if (max.mV[j] > newMax.mV[j]) + { + newMax.mV[j] = max.mV[j]; + } + if (min.mV[j] < newMin.mV[j]) + { + newMin.mV[j] = min.mV[j]; + } + } + } + + boundObjects(FALSE, newMin, newMax); + + mBounds[0] = (newMin + newMax)*0.5f; + mBounds[1] = (newMax - newMin)*0.5f; + } + + if (isState(QUERY_OUT)) + { + for (U32 i = 0; i < 3 && !isState(DISCARD_QUERY); i++) + { + if (fabsf(mBounds[0].mV[i]-oldBounds[0].mV[i]) > SG_DISCARD_TOLERANCE || + fabsf(mBounds[1].mV[i]-oldBounds[1].mV[i]) > SG_DISCARD_TOLERANCE) + { //bounding box changed significantly, discard last issued + //occlusion query + setState(DISCARD_QUERY); + } + } + } + + clearState(DIRTY); + + return TRUE; +} + +//============================================== + +LLSpatialPartition::LLSpatialPartition() +{ + LLMemType mt(LLMemType::MTYPE_SPACE_PARTITION); + mOctree = new LLSpatialGroup::OctreeNode(LLVector3d(0,0,0), + LLVector3d(1,1,1), + new LLSpatialGroup::OctreeRoot(), NULL); + new LLSpatialGroup(mOctree, this); +} + + +LLSpatialPartition::~LLSpatialPartition() +{ + LLMemType mt(LLMemType::MTYPE_SPACE_PARTITION); + delete mOctree; + mOctree = NULL; +} + + +LLSpatialGroup *LLSpatialPartition::put(LLDrawable *drawablep) +{ + LLMemType mt(LLMemType::MTYPE_SPACE_PARTITION); + const F32 MAX_MAG = 1000000.f*1000000.f; // 1 million + + if (drawablep->getPositionGroup().magVecSquared() > MAX_MAG) + { +#ifndef LL_RELEASE_FOR_DOWNLOAD + llwarns << "LLSpatialPartition::put Object out of range!" << llendl; + llinfos << drawablep->getPositionGroup() << llendl; + + if (drawablep->getVObj()) + { + llwarns << "Dumping debugging info: " << llendl; + drawablep->getVObj()->dump(); + } +#endif + return NULL; + } + + drawablep->updateSpatialExtents(); + validate_drawable(drawablep); + + //keep drawable from being garbage collected + LLPointer<LLDrawable> ptr = drawablep; + + assert_octree_valid(mOctree); + mOctree->insert(drawablep); + assert_octree_valid(mOctree); + + LLSpatialGroup::OctreeNode* node = mOctree->getNodeAt(drawablep); + + return (LLSpatialGroup*) node->getListener(0); +} + +BOOL LLSpatialPartition::remove(LLDrawable *drawablep, LLSpatialGroup *curp) +{ + LLMemType mt(LLMemType::MTYPE_SPACE_PARTITION); + + drawablep->setSpatialGroup(NULL, -1); + + if (!curp->removeObject(drawablep)) + { + OCT_ERRS << "Failed to remove drawable from octree!" << llendl; + } + + assert_octree_valid(mOctree); + + return TRUE; +} + +void LLSpatialPartition::move(LLDrawable *drawablep, LLSpatialGroup *curp, BOOL immediate) +{ + LLMemType mt(LLMemType::MTYPE_SPACE_PARTITION); + LLFastTimer t(LLFastTimer::FTM_UPDATE_MOVE); + + if (curp && curp->mSpatialPartition != this) + { + //keep drawable from being garbage collected + LLPointer<LLDrawable> ptr = drawablep; + if (curp->mSpatialPartition->remove(drawablep, curp)) + { + put(drawablep); + return; + } + else + { + OCT_ERRS << "Drawable lost between spatial partitions on outbound transition." << llendl; + } + } + + if (curp && curp->updateInGroup(drawablep, immediate)) + { + // Already updated, don't need to do anything + assert_octree_valid(mOctree); + return; + } + + //keep drawable from being garbage collected + LLPointer<LLDrawable> ptr = drawablep; + if (curp && !remove(drawablep, curp)) + { + OCT_ERRS << "Move couldn't find existing spatial group!" << llendl; + } + + put(drawablep); +} + +class LLSpatialShift : public LLSpatialGroup::OctreeTraveler +{ +public: + LLSpatialShift(LLVector3 offset) : mOffset(offset) { } + virtual void visit(const LLSpatialGroup::OctreeState* branch) + { + ((LLSpatialGroup*) branch->getListener(0))->shift(mOffset); + } + + LLVector3 mOffset; +}; + +void LLSpatialPartition::shift(const LLVector3 &offset) +{ + LLMemType mt(LLMemType::MTYPE_SPACE_PARTITION); + llinfos << "Shifting octree: " << offset << llendl; + LLSpatialShift shifter(offset); + shifter.traverse(mOctree); +} + +BOOL LLSpatialPartition::checkOcclusion(LLSpatialGroup* group, LLCamera* camera) +{ + if (sIgnoreOcclusion) + { + return FALSE; + } + + if (!group->isState(LLSpatialGroup::ACTIVE_OCCLUSION | LLSpatialGroup::OCCLUDED) && + !earlyFail(camera, group)) + { + group->setState(LLSpatialGroup::ACTIVE_OCCLUSION); + mQueryQueue.push(group); + return TRUE; + } + + return FALSE; +} + +class LLOctreeCull : public LLSpatialGroup::OctreeTraveler +{ +public: + LLOctreeCull(LLCamera* camera) + : mCamera(camera), mRes(0) { } + + virtual bool earlyFail(const LLSpatialGroup* group) + { + if (mRes && //never occlusion cull the root node + !sIgnoreOcclusion && //never occlusion cull selection + group->isState(LLSpatialGroup::OCCLUDED)) + { + return true; + } + + return false; + } + + virtual void traverse(const LLSpatialGroup::TreeNode* n) + { + LLSpatialGroup* group = (LLSpatialGroup*) n->getListener(0); + + if (earlyFail(group)) + { + return; + } + + if (mRes == 2 || + (mRes && group->isState(LLSpatialGroup::SKIP_FRUSTUM_CHECK))) + { //fully in, just add everything + LLSpatialGroup::OctreeTraveler::traverse(n); + } + else + { + mRes = mCamera->AABBInFrustum(group->mBounds[0], group->mBounds[1]); + + if (mRes) + { //at least partially in, run on down + LLSpatialGroup::OctreeTraveler::traverse(n); + } + else + { + lateFail(group); + } + mRes = 0; + } + } + + virtual void lateFail(LLSpatialGroup* group) + { + if (!group->isState(LLSpatialGroup::CULLED)) + { //totally culled, so are all its children + group->setState(LLSpatialGroup::CULLED, LLSpatialGroup::STATE_MODE_DIFF); + } + } + + virtual bool checkObjects(const LLSpatialGroup::OctreeState* branch, const LLSpatialGroup* 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 && !mCamera->AABBInFrustum(group->mObjectBounds[0], group->mObjectBounds[1])) //no objects in frustum + { + return false; + } + + return true; + } + + virtual void preprocess(LLSpatialGroup* group) + { + if (group->isState(LLSpatialGroup::CULLED)) + { //this is the first frame this node is visible + group->clearState(LLSpatialGroup::CULLED); + if (group->mOctreeNode->hasLeafState()) + { //if it's a leaf, force it onto the active occlusion list to prevent + //massive frame stutters + group->mSpatialPartition->checkOcclusion(group, mCamera); + } + } + } + + virtual void processDrawable(LLDrawable* drawable) + { + if (!drawable->isDead()) + { + const LLVector3* extents = drawable->getSpatialExtents(); + + F32 objRad = drawable->getRadius(); + objRad *= objRad; + F32 distSqr = ((extents[0]+extents[1])*0.5f - mCamera->getOrigin()).magVecSquared(); + if (objRad/distSqr > SG_MIN_DIST_RATIO) + { + gPipeline.markNotCulled(drawable, *mCamera); + } + } + } + + virtual void visit(const LLSpatialGroup::OctreeState* branch) + { + LLSpatialGroup* group = (LLSpatialGroup*) branch->getListener(0); + + preprocess(group); + + if (checkObjects(branch, group)) + { + for (LLSpatialGroup::OctreeState::const_element_iter i = branch->getData().begin(); i != branch->getData().end(); ++i) + { + processDrawable(*i); + } + } + } + + LLCamera *mCamera; + S32 mRes; +}; + + +class LLOctreeSelect : public LLOctreeCull +{ +public: + LLOctreeSelect(LLCamera* camera, std::vector<LLDrawable*>* results) + : LLOctreeCull(camera), mResults(results) { } + + virtual bool earlyFail(const LLSpatialGroup* group) { return false; } + virtual void lateFail(LLSpatialGroup* group) { } + virtual void preprocess(LLSpatialGroup* group) { } + + virtual void processDrawable(LLDrawable* drawable) + { + if (!drawable->isDead()) + { + if (drawable->isSpatialBridge()) + { + drawable->setVisible(*mCamera, mResults, TRUE); + } + else + { + mResults->push_back(drawable); + } + } + } + + std::vector<LLDrawable*>* mResults; +}; + + +void drawBox(const LLVector3& c, const LLVector3& r) +{ + glPushMatrix(); + glTranslatef(c.mV[0], c.mV[1], c.mV[2]); + glScalef(r.mV[0], r.mV[1], r.mV[2]); + glCallList(sBoxList); + glPopMatrix(); +} + +void genBoxList() +{ + if (sBoxList != 0) + { + return; + } + + sBoxList = glGenLists(1); + glNewList(sBoxList, GL_COMPILE); + + LLVector3 c,r; + c = LLVector3(0,0,0); + r = LLVector3(1,1,1); + + glBegin(GL_TRIANGLE_STRIP); + //left front + glVertex3fv((c+r.scaledVec(LLVector3(-1,1,-1))).mV); + glVertex3fv((c+r.scaledVec(LLVector3(-1,1,1))).mV); + //right front + glVertex3fv((c+r.scaledVec(LLVector3(1,1,-1))).mV); + glVertex3fv((c+r.scaledVec(LLVector3(1,1,1))).mV); + //right back + glVertex3fv((c+r.scaledVec(LLVector3(1,-1,-1))).mV); + glVertex3fv((c+r.scaledVec(LLVector3(1,-1,1))).mV); + //left back + glVertex3fv((c+r.scaledVec(LLVector3(-1,-1,-1))).mV); + glVertex3fv((c+r.scaledVec(LLVector3(-1,-1,1))).mV); + //left front + glVertex3fv((c+r.scaledVec(LLVector3(-1,1,-1))).mV); + glVertex3fv((c+r.scaledVec(LLVector3(-1,1,1))).mV); + glEnd(); + + //bottom + glBegin(GL_TRIANGLE_STRIP); + glVertex3fv((c+r.scaledVec(LLVector3(1,1,-1))).mV); + glVertex3fv((c+r.scaledVec(LLVector3(1,-1,-1))).mV); + glVertex3fv((c+r.scaledVec(LLVector3(-1,1,-1))).mV); + glVertex3fv((c+r.scaledVec(LLVector3(-1,-1,-1))).mV); + glEnd(); + + //top + glBegin(GL_TRIANGLE_STRIP); + glVertex3fv((c+r.scaledVec(LLVector3(1,1,1))).mV); + glVertex3fv((c+r.scaledVec(LLVector3(-1,1,1))).mV); + glVertex3fv((c+r.scaledVec(LLVector3(1,-1,1))).mV); + glVertex3fv((c+r.scaledVec(LLVector3(-1,-1,1))).mV); + glEnd(); + + glEndList(); +} + +void LLSpatialPartition::restoreGL() +{ + LLMemType mt(LLMemType::MTYPE_SPACE_PARTITION); + mOcclusionQueries.clear(); + sBoxList = 0; + + //generate query ids + while (mOcclusionQueries.size() < mOccludedList.size()) + { + GLuint id; + glGenQueriesARB(1, &id); + mOcclusionQueries.push_back(id); + } + + for (U32 i = 0; i < mOccludedList.size(); i++) + { //previously issued queries are now invalid + mOccludedList[i]->setState(LLSpatialGroup::DISCARD_QUERY); + } + + genBoxList(); +} + +S32 LLSpatialPartition::cull(LLCamera &camera, std::vector<LLDrawable *>* results, BOOL for_select) +{ + LLMemType mt(LLMemType::MTYPE_SPACE_PARTITION); + { + LLFastTimer ftm(LLFastTimer::FTM_CULL_REBOUND); + LLSpatialGroup* group = (LLSpatialGroup*) mOctree->getListener(0); + group->rebound(); + } + + if (for_select) + { + LLOctreeSelect selecter(&camera, results); + selecter.traverse(mOctree); + } + else + { + LLOctreeCull culler(&camera); + culler.traverse(mOctree); + } + + sIgnoreOcclusion = !(gSavedSettings.getBOOL("UseOcclusion") && gGLManager.mHasOcclusionQuery); + return 0; +} + +class LLOctreeClearOccludedNotActive : public LLSpatialGroup::OctreeTraveler +{ +public: + LLOctreeClearOccludedNotActive() { } + + virtual void traverse(const LLSpatialGroup::TreeNode* n) + { + LLSpatialGroup* group = (LLSpatialGroup*) n->getListener(0); + if ((!group->isState(LLSpatialGroup::ACTIVE_OCCLUSION)) //|| group->isState(LLSpatialGroup::QUERY_PENDING) + || group->isState(LLSpatialGroup::DEACTIVATE_OCCLUSION)) + { //the children are all occluded or culled as well + group->clearState(LLSpatialGroup::OCCLUDED); + for (U32 i = 0; i < group->mOctreeNode->getChildCount(); i++) + { + traverse(group->mOctreeNode->getChild(i)); + } + } + } + + virtual void visit(const LLSpatialGroup::OctreeState* branch) { } +}; + +class LLQueueNonCulled : public LLSpatialGroup::OctreeTraveler +{ +public: + std::queue<LLSpatialGroup*>* mQueue; + LLQueueNonCulled(std::queue<LLSpatialGroup*> *queue) : mQueue(queue) { } + + virtual void traverse(const LLSpatialGroup::TreeNode* n) + { + LLSpatialGroup* group = (LLSpatialGroup*) n->getListener(0); + if (group->isState(LLSpatialGroup::OCCLUDED | LLSpatialGroup::CULLED)) + { //the children are all occluded or culled as well + return; + } + + if (!group->isState(LLSpatialGroup::IN_QUEUE)) + { + group->setState(LLSpatialGroup::IN_QUEUE); + mQueue->push(group); + } + + LLSpatialGroup::OctreeTraveler::traverse(n); + } + + virtual void visit(const LLSpatialGroup::OctreeState* branch) { } +}; + +BOOL earlyFail(LLCamera* camera, LLSpatialGroup* group) +{ + LLVector3 c = group->mBounds[0]; + LLVector3 r = group->mBounds[1] * (SG_OCCLUSION_FUDGE*2.f) + LLVector3(0.01f,0.01f,0.01f); + + if (group->isState(LLSpatialGroup::CULLED) || !camera->AABBInFrustum(c, r)) + { + return TRUE; + } + + LLVector3 e = camera->getOrigin(); + + LLVector3 min = c - r; + LLVector3 max = c + r; + + for (U32 j = 0; j < 3; j++) + { + if (e.mV[j] < min.mV[j] || e.mV[j] > max.mV[j]) + { + return FALSE; + } + } + + return TRUE; +} + +void LLSpatialPartition::processOcclusion(LLCamera* camera) +{ + LLMemType mt(LLMemType::MTYPE_SPACE_PARTITION); + LLSpatialGroup* rootGroup = (LLSpatialGroup*) mOctree->getListener(0); + { + LLFastTimer ftm(LLFastTimer::FTM_CULL_REBOUND); + rootGroup->rebound(); + } + + //update potentials + if (!rootGroup->isState(LLSpatialGroup::IN_QUEUE)) + { + rootGroup->setState(LLSpatialGroup::IN_QUEUE); + mOcclusionQueue.push(rootGroup); + } + + const U32 MAX_PULLED = 32; + const U32 MAX_PUSHED = mOcclusionQueue.size(); + U32 count = 0; + U32 pcount = 0; + + while (pcount < MAX_PUSHED && count < MAX_PULLED && !mOcclusionQueue.empty()) + { + LLFastTimer t(LLFastTimer::FTM_OCCLUSION); + + LLSpatialGroup* group = mOcclusionQueue.front(); + if (!group->isState(LLSpatialGroup::IN_QUEUE)) + { + OCT_ERRS << "Spatial Group State Error. Group in queue not tagged as such." << llendl; + } + + mOcclusionQueue.pop(); + group->clearState(LLSpatialGroup::IN_QUEUE); + + if (group->isDead()) + { + if (group->safeToDelete()) + { + delete group; + } + continue; + } + + if (group->isState(LLSpatialGroup::CULLED | LLSpatialGroup::OCCLUDED)) + { //already culled, skip it + continue; + } + + //before we process, enqueue this group's children + for (U32 i = 0; i < group->mOctreeNode->getChildCount(); i++) + { + LLSpatialGroup* child = (LLSpatialGroup*) group->mOctreeNode->getChild(i)->getListener(0); + + if (!child->isState(LLSpatialGroup::OCCLUDED | LLSpatialGroup::CULLED) + && !child->isState(LLSpatialGroup::IN_QUEUE | LLSpatialGroup::ACTIVE_OCCLUSION)) + { + child->setState(LLSpatialGroup::IN_QUEUE); + mOcclusionQueue.push(child); + } + } + + /*if (group->isState(LLSpatialGroup::QUERY_PENDING)) + { //already on the pending group, put it back + group->setState(LLSpatialGroup::IN_QUEUE); + mOcclusionQueue.push(group); + pcount++; + continue; + }*/ + + if (earlyFail(camera, group)) + { + sg_assert(!group->isState(LLSpatialGroup::OCCLUDED)); + group->setState(LLSpatialGroup::IN_QUEUE); + mOcclusionQueue.push(group); + pcount++; + continue; + } + + //add to pending queue + if (!group->isState(LLSpatialGroup::ACTIVE_OCCLUSION)) + { +#if LL_OCTREE_PARANOIA_CHECK + for (U32 i = 0; i < mOccludedList.size(); ++i) + { + sg_assert(mOccludedList[i] != group); + } +#endif + //group->setState(LLSpatialGroup::QUERY_PENDING); + group->setState(LLSpatialGroup::ACTIVE_OCCLUSION); + mQueryQueue.push(group); + count++; + } + } + + //read back results from last frame + for (U32 i = 0; i < mOccludedList.size(); i++) + { + LLFastTimer t(LLFastTimer::FTM_OCCLUSION_READBACK); + + if (mOccludedList[i]->isDead() || !mOccludedList[i]->isState(LLSpatialGroup::ACTIVE_OCCLUSION)) + { + continue; + } + GLuint res = 0; + + if (mOccludedList[i]->isState(LLSpatialGroup::EARLY_FAIL | LLSpatialGroup::DISCARD_QUERY) || + !mOccludedList[i]->isState(LLSpatialGroup::QUERY_OUT)) + { + mOccludedList[i]->clearState(LLSpatialGroup::EARLY_FAIL); + mOccludedList[i]->clearState(LLSpatialGroup::DISCARD_QUERY); + res = 1; + } + else + { + glGetQueryObjectuivARB(mOcclusionQueries[i], GL_QUERY_RESULT_ARB, &res); + stop_glerror(); + } + + if (res) //NOT OCCLUDED + { + if (mOccludedList[i]->isState(LLSpatialGroup::OCCLUDED)) + { //this node was occluded last frame + LLSpatialGroup::OctreeNode* node = mOccludedList[i]->mOctreeNode; + //add any immediate children to the queue that are not already there + for (U32 j = 0; j < node->getChildCount(); j++) + { + LLSpatialGroup* group = (LLSpatialGroup*) node->getChild(j)->getListener(0); + checkOcclusion(group, camera); + } + } + + //clear occlusion status for everything not on the active list + LLOctreeClearOccludedNotActive clear_occluded; + mOccludedList[i]->setState(LLSpatialGroup::DEACTIVATE_OCCLUSION); + mOccludedList[i]->clearState(LLSpatialGroup::OCCLUDED); + mOccludedList[i]->clearState(LLSpatialGroup::OCCLUDING); + clear_occluded.traverse(mOccludedList[i]->mOctreeNode); + } + else + { //OCCLUDED + if (mOccludedList[i]->isState(LLSpatialGroup::OCCLUDING)) + { + if (!mOccludedList[i]->isState(LLSpatialGroup::OCCLUDED)) + { + LLSpatialGroup::OctreeNode* oct_parent = (LLSpatialGroup::OctreeNode*) mOccludedList[i]->mOctreeNode->getParent(); + if (oct_parent) + { + LLSpatialGroup* parent = (LLSpatialGroup*) oct_parent->getListener(0); + + if (checkOcclusion(parent, camera)) + { //force a guess on the parent and siblings + + for (U32 i = 0; i < parent->mOctreeNode->getChildCount(); i++) + { + LLSpatialGroup* child = (LLSpatialGroup*) parent->mOctreeNode->getChild(i)->getListener(0); + checkOcclusion(child, camera); + } + } + } + } + mOccludedList[i]->setState(LLSpatialGroup::OCCLUDED, LLSpatialGroup::STATE_MODE_DIFF); + } + else + { + //take children off the active list + mOccludedList[i]->setState(LLSpatialGroup::DEACTIVATE_OCCLUSION, LLSpatialGroup::STATE_MODE_DIFF); + + //keep this node on the active list + mOccludedList[i]->clearState(LLSpatialGroup::DEACTIVATE_OCCLUSION); + + //this node is a top level occluder + mOccludedList[i]->setState(LLSpatialGroup::OCCLUDING); + } + } + + mOccludedList[i]->clearState(LLSpatialGroup::QUERY_OUT); + } + + //remove non-occluded groups from occluded list + for (U32 i = 0; i < mOccludedList.size(); ) + { + if (mOccludedList[i]->isDead() || //needs to be deleted + !mOccludedList[i]->isState(LLSpatialGroup::OCCLUDING) || //is not occluding + mOccludedList[i]->isState(LLSpatialGroup::DEACTIVATE_OCCLUSION)) //parent is occluded + { + LLSpatialGroup* groupp = mOccludedList[i]; + mOccludedList.erase(mOccludedList.begin()+i); + groupp->clearState(LLSpatialGroup::ACTIVE_OCCLUSION); + groupp->clearState(LLSpatialGroup::DEACTIVATE_OCCLUSION); + groupp->clearState(LLSpatialGroup::OCCLUDING); + + if (groupp->isDead() && groupp->safeToDelete()) + { + delete groupp; + } + } + else + { + i++; + } + } + + //pump some non-culled items onto the occlusion list + //count = MAX_PULLED; + while (!mQueryQueue.empty()) + { + LLSpatialGroup* group = mQueryQueue.front(); + mQueryQueue.pop(); + //group->clearState(LLSpatialGroup::QUERY_PENDING); + mOccludedList.push_back(group); + } + + //generate query ids + while (mOcclusionQueries.size() < mOccludedList.size()) + { + GLuint id; + glGenQueriesARB(1, &id); + mOcclusionQueries.push_back(id); + } +} + +void LLSpatialPartition::doOcclusion(LLCamera* camera) +{ + LLMemType mt(LLMemType::MTYPE_SPACE_PARTITION); + + sIgnoreOcclusion = gUseWireframe; + LLFastTimer t(LLFastTimer::FTM_RENDER_OCCLUSION); + +#if LL_OCTREE_PARANOIA_CHECK + LLSpatialGroup* check = (LLSpatialGroup*) mOctree->getListener(0); + check->validate(); +#endif + + stop_glerror(); + + //actually perform the occlusion queries + LLGLDepthTest gls_depth(GL_TRUE, GL_FALSE); + glDisable(GL_TEXTURE_2D); + gPipeline.disableLights(); + LLGLEnable cull_face(GL_CULL_FACE); + LLGLDisable blend(GL_BLEND); + LLGLDisable alpha_test(GL_ALPHA_TEST); + LLGLDisable fog(GL_FOG); + glColorMask(GL_FALSE, GL_FALSE, GL_FALSE, GL_FALSE); + glColor4f(1,1,1,1); + + //sort occlusion queries front to back + /*for (U32 i = 0; i < mOccludedList.size(); i++) + { + LLSpatialGroup* group = mOccludedList[i]; + + LLVector3 v = group->mOctreeNode->getCenter()-camera->getOrigin(); + group->mDistance = v*v; + } + + std::sort(mOccludedList.begin(), mOccludedList.end(), dist_greater()); + + glClearStencil(0); + glClear(GL_STENCIL_BUFFER_BIT); + LLGLEnable stencil(GL_STENCIL_TEST); + glStencilFunc(GL_GREATER, 1, 0xFFFFFFFF); + glStencilOp(GL_KEEP, GL_SET, GL_KEEP);*/ + + genBoxList(); + + for (U32 i = 0; i < mOccludedList.size(); i++) + { +#if LL_OCTREE_PARANOIA_CHECK + for (U32 j = i+1; j < mOccludedList.size(); j++) + { + sg_assert(mOccludedList[i] != mOccludedList[j]); + } +#endif + LLSpatialGroup* group = mOccludedList[i]; + if (group->isDead()) + { + continue; + } + + if (earlyFail(camera, group)) + { + group->setState(LLSpatialGroup::EARLY_FAIL); + } + else + { //early rejection criteria passed, send some geometry to the query + LLVector3 c; + LLVector3 r; + + sg_assert(!group->isState(LLSpatialGroup::DIRTY)); + + c = group->mBounds[0]; + r = group->mBounds[1]*SG_OCCLUSION_FUDGE + LLVector3(0.01f,0.01f,0.01f); + for (U32 k = 0; k < 3; k++) + { + r.mV[k] = llmin(group->mBounds[1].mV[k]+0.25f, r.mV[k]); + } + +#if LL_OCTREE_PARANOIA_CHECK + LLVector3 e = camera->getOrigin(); + LLVector3 min = c - r; + LLVector3 max = c + r; + BOOL outside = FALSE; + for (U32 j = 0; j < 3; j++) + { + outside = outside || (e.mV[j] < min.mV[j] || e.mV[j] > max.mV[j]); + } + sg_assert(outside); +#endif + + glBeginQueryARB(GL_SAMPLES_PASSED_ARB, mOcclusionQueries[i]); + drawBox(c,r); + glEndQueryARB(GL_SAMPLES_PASSED_ARB); + + group->setState(LLSpatialGroup::QUERY_OUT); + group->clearState(LLSpatialGroup::DISCARD_QUERY); + } + } + stop_glerror(); + + glFlush(); + + glColorMask(GL_TRUE, GL_TRUE, GL_TRUE, GL_TRUE); + glEnable(GL_TEXTURE_2D); +} + +class LLOctreeGet : public LLSpatialGroup::OctreeTraveler +{ +public: + LLOctreeGet(LLVector3 pos, F32 rad, LLDrawable::drawable_set_t* results, BOOL lights) + : mPosition(pos), mRad(rad), mResults(results), mLights(lights), mRes(0) + { + + } + + virtual void traverse(const LLSpatialGroup::TreeNode* n) + { + LLSpatialGroup* group = (LLSpatialGroup*) n->getListener(0); + + if (mRes == 2) + { //fully in, just add everything + LLSpatialGroup::OctreeTraveler::traverse(n); + } + else + { + LLVector3 center, size; + + center = group->mBounds[0]; + size = group->mBounds[1]; + + mRes = LLSphereAABB(center, size, mPosition, mRad); + if (mRes > 0) + { + LLSpatialGroup::OctreeTraveler::traverse(n); + } + mRes = 0; + } + } + + static BOOL skip(LLDrawable* drawable, BOOL get_lights) + { + if (get_lights != drawable->isLight()) + { + return TRUE; + } + if (get_lights && drawable->getVObj()->isHUDAttachment()) + { + return TRUE; // no lighting from HUD objects + } + if (get_lights && drawable->isState(LLDrawable::ACTIVE)) + { + return TRUE; // ignore active lights + } + return FALSE; + } + + virtual void visit(const LLSpatialGroup::OctreeState* branch) + { + for (LLSpatialGroup::OctreeState::const_element_iter i = branch->getData().begin(); i != branch->getData().end(); ++i) + { + LLDrawable* drawable = *i; + if (!skip(drawable, mLights)) + { + if (mRes == 2) + { + mResults->insert(drawable); + } + else + { + LLVector3 v = LLVector3(drawable->getPositionGroup())-mPosition; + float dsq = v.magVecSquared(); + float maxd = mRad + drawable->getVisibilityRadius(); + if (dsq <= maxd*maxd) + { + mResults->insert(drawable); + } + } + } + } + } + + LLVector3 mPosition; + F32 mRad; + LLDrawable::drawable_set_t* mResults; + BOOL mLights; + U32 mRes; +}; + +S32 LLSpatialPartition::getDrawables(const LLVector3& pos, F32 rad, + LLDrawable::drawable_set_t &results, + BOOL get_lights) +{ + LLMemType mt(LLMemType::MTYPE_SPACE_PARTITION); + + LLOctreeGet getter(pos, rad, &results, get_lights); + getter.traverse(mOctree); + + return results.size(); +} + +S32 LLSpatialPartition::getObjects(const LLVector3& pos, F32 rad, LLDrawable::drawable_set_t &results) +{ + return getDrawables(pos, rad, results, FALSE); +} + +S32 LLSpatialPartition::getLights(const LLVector3& pos, F32 rad, LLDrawable::drawable_set_t &results) +{ + return getDrawables(pos, rad, results, TRUE); +} + +class LLOctreeRenderNonOccluded : public LLOctreeTraveler<LLDrawable> +{ +public: + LLOctreeRenderNonOccluded() {} + + virtual void traverse(const LLSpatialGroup::OctreeNode* node) + { + const LLSpatialGroup::OctreeState* state = node->getOctState(); + LLSpatialGroup* group = (LLSpatialGroup*) node->getListener(0); + + if (!group->isState(LLSpatialGroup::OCCLUDED | LLSpatialGroup::CULLED)) + { + state->accept(this); + + for (U32 i = 0; i < state->getChildCount(); i++) + { + traverse(state->getChild(i)); + } + + /*if (state->getElementCount() == 0) + { + return; + }*/ + + //draw tight fit bounding box for spatial group + if (gPipeline.hasRenderDebugMask(LLPipeline::RENDER_DEBUG_OCTREE)) + { + if (node->getElementCount() == 0) + { + return; + } + + if (node->hasLeafState()) + { + glColor4f(1,1,1,1); + } + else + { + glColor4f(0,1,1,1); + } + + + LLVector3 pos; + LLVector3 size; + + pos = group->mObjectBounds[0]; + size = group->mObjectBounds[1]; + + LLVector3 v1 = size.scaledVec(LLVector3( 1, 1,1)); + LLVector3 v2 = size.scaledVec(LLVector3(-1, 1,1)); + LLVector3 v3 = size.scaledVec(LLVector3(-1,-1,1)); + LLVector3 v4 = size.scaledVec(LLVector3( 1,-1,1)); + + glBegin(GL_LINE_LOOP); //top + glVertex3fv((pos+v1).mV); + glVertex3fv((pos+v2).mV); + glVertex3fv((pos+v3).mV); + glVertex3fv((pos+v4).mV); + glEnd(); + + glBegin(GL_LINE_LOOP); //bottom + glVertex3fv((pos-v1).mV); + glVertex3fv((pos-v2).mV); + glVertex3fv((pos-v3).mV); + glVertex3fv((pos-v4).mV); + glEnd(); + + + glBegin(GL_LINES); + + //right + glVertex3fv((pos+v1).mV); + glVertex3fv((pos-v3).mV); + + glVertex3fv((pos+v4).mV); + glVertex3fv((pos-v2).mV); + + //left + glVertex3fv((pos+v2).mV); + glVertex3fv((pos-v4).mV); + + glVertex3fv((pos+v3).mV); + glVertex3fv((pos-v1).mV); + + glEnd(); + + LLVector3 nc = LLVector3(node->getCenter()); + LLVector3 ns = LLVector3(node->getSize()); + + LLVector3 nv1 = ns.scaledVec(LLVector3( 1, 1,1)); + LLVector3 nv2 = ns.scaledVec(LLVector3(-1, 1,1)); + LLVector3 nv3 = ns.scaledVec(LLVector3(-1,-1,1)); + LLVector3 nv4 = ns.scaledVec(LLVector3( 1,-1,1)); + + + + /*if (node->getElementCount() > 0) + { + //spokes + glColor4f(1,1,0,1); + glVertex3fv(pos.mV); + glColor4f(1,1,0,0); + glVertex3fv(nc.mV); + + glColor4f(1,1,0,1); glVertex3fv((pos+v1).mV); glColor4f(1,1,0,0); glVertex3fv(pos.mV); + glColor4f(1,1,0,1); glVertex3fv((pos-v1).mV); glColor4f(1,1,0,0); glVertex3fv(pos.mV); + glColor4f(1,1,0,1); glVertex3fv((pos+v2).mV); glColor4f(1,1,0,0); glVertex3fv(pos.mV); + glColor4f(1,1,0,1); glVertex3fv((pos-v2).mV); glColor4f(1,1,0,0); glVertex3fv(pos.mV); + glColor4f(1,1,0,1); glVertex3fv((pos+v3).mV); glColor4f(1,1,0,0); glVertex3fv(pos.mV); + glColor4f(1,1,0,1); glVertex3fv((pos-v3).mV); glColor4f(1,1,0,0); glVertex3fv(pos.mV); + glColor4f(1,1,0,1); glVertex3fv((pos+v4).mV); glColor4f(1,1,0,0); glVertex3fv(pos.mV); + glColor4f(1,1,0,1); glVertex3fv((pos-v4).mV); glColor4f(1,1,0,0); glVertex3fv(pos.mV); + }*/ + + + + /*glColor4f(0,1,0,1); + glBegin(GL_LINE_LOOP); //top + glVertex3fv((nc+nv1).mV); + glVertex3fv((nc+nv2).mV); + glVertex3fv((nc+nv3).mV); + glVertex3fv((nc+nv4).mV); + glEnd(); + + glBegin(GL_LINE_LOOP); //bottom + glVertex3fv((nc-nv1).mV); + glVertex3fv((nc-nv2).mV); + glVertex3fv((nc-nv3).mV); + glVertex3fv((nc-nv4).mV); + glEnd(); + + + glBegin(GL_LINES); + + //right + glVertex3fv((nc+nv1).mV); + glVertex3fv((nc-nv3).mV); + + glVertex3fv((nc+nv4).mV); + glVertex3fv((nc-nv2).mV); + + //left + glVertex3fv((nc+nv2).mV); + glVertex3fv((nc-nv4).mV); + + glVertex3fv((nc+nv3).mV); + glVertex3fv((nc-nv1).mV); + glEnd();*/ + + glLineWidth(1); + + glDepthMask(GL_FALSE); + glBlendFunc(GL_SRC_ALPHA, GL_ONE); + glColor4f(0.1f,0.1f,1,0.1f); + drawBox(group->mObjectBounds[0], group->mObjectBounds[1]*1.01f+LLVector3(0.001f, 0.001f, 0.001f)); + glDepthMask(GL_TRUE); + glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA); + } + } + /*else + { + //occlusion paranoia check + const LLSpatialGroup::OctreeNode* parent = node; + while (parent != NULL) + { + LLSpatialGroup* grp = (LLSpatialGroup*) parent->getListener(0); + if (grp->isState(LLSpatialGroup::ACTIVE_OCCLUSION)) + { + return; + } + parent = (const LLSpatialGroup::OctreeNode*) parent->getParent(); + } + + glColor4f(1,0,1,1); + drawBox(group->mBounds[0], group->mBounds[1]); + }*/ + } + + virtual void visit(const LLSpatialGroup::OctreeState* branch) + { + LLSpatialGroup* group = (LLSpatialGroup*) branch->getListener(0); + + if (group->isState(LLSpatialGroup::CULLED | LLSpatialGroup::OCCLUDED)) + { + return; + } + + LLVector3 nodeCenter = group->mBounds[0]; + LLVector3 octCenter = LLVector3(group->mOctreeNode->getCenter()); + + if (gPipeline.hasRenderDebugMask(LLPipeline::RENDER_DEBUG_OCTREE)) + { + glBegin(GL_LINES); + glColor4f(1,0.5f,0,1); + glVertex3fv(nodeCenter.mV); + glColor4f(0,1,1,0); + glVertex3fv(octCenter.mV); + glEnd(); + } + + for (LLSpatialGroup::OctreeState::const_element_iter i = branch->getData().begin(); i != branch->getData().end(); ++i) + { + LLDrawable* drawable = *i; + + if (drawable->isSpatialBridge()) + { + LLSpatialBridge* bridge = (LLSpatialBridge*) drawable; + glPushMatrix(); + glMultMatrixf((F32*)bridge->mDrawable->getWorldMatrix().mMatrix); + traverse(bridge->mOctree); + glPopMatrix(); + } + + if (!drawable->isVisible()) + { + continue; + } + + if (gPipeline.hasRenderDebugMask(LLPipeline::RENDER_DEBUG_BBOXES)) + { + if (drawable->isSpatialBridge()) + { + glColor4f(1,0.5f,0,1); + } + else if (drawable->getVOVolume()) + { + if (drawable->isRoot()) + { + glColor4f(1,1,0,1); + } + else + { + glColor4f(0,1,0,1); + } + } + else if (drawable->getVObj()) + { + switch (drawable->getVObj()->getPCode()) + { + case LLViewerObject::LL_VO_SURFACE_PATCH: + glColor4f(0,1,1,1); + break; + case LLViewerObject::LL_VO_CLOUDS: + glColor4f(0.5f,0.5f,0.5f,1.0f); + break; + case LLViewerObject::LL_VO_PART_GROUP: + glColor4f(0,0,1,1); + break; + case LLViewerObject::LL_VO_WATER: + glColor4f(0,0.5f,1,1); + break; + case LL_PCODE_LEGACY_TREE: + glColor4f(0,0.5f,0,1); + default: + glColor4f(1,0,1,1); + break; + } + } + else + { + glColor4f(1,0,0,1); + } + + + const LLVector3* ext = drawable->getSpatialExtents(); + + LLVector3 pos = (ext[0] + ext[1]) * 0.5f; + LLVector3 size = (ext[1] - ext[0]) * 0.5f; + + LLVector3 v1 = size.scaledVec(LLVector3( 1, 1,1)); + LLVector3 v2 = size.scaledVec(LLVector3(-1, 1,1)); + LLVector3 v3 = size.scaledVec(LLVector3(-1,-1,1)); + LLVector3 v4 = size.scaledVec(LLVector3( 1,-1,1)); + + glBegin(GL_LINE_LOOP); //top + glVertex3fv((pos+v1).mV); + glVertex3fv((pos+v2).mV); + glVertex3fv((pos+v3).mV); + glVertex3fv((pos+v4).mV); + glEnd(); + + glBegin(GL_LINE_LOOP); //bottom + glVertex3fv((pos-v1).mV); + glVertex3fv((pos-v2).mV); + glVertex3fv((pos-v3).mV); + glVertex3fv((pos-v4).mV); + glEnd(); + + + glBegin(GL_LINES); + + //right + glVertex3fv((pos+v1).mV); + glVertex3fv((pos-v3).mV); + + glVertex3fv((pos+v4).mV); + glVertex3fv((pos-v2).mV); + + //left + glVertex3fv((pos+v2).mV); + glVertex3fv((pos-v4).mV); + + glVertex3fv((pos+v3).mV); + glVertex3fv((pos-v1).mV); + + glEnd(); + + //render space partition trace + glBegin(GL_LINE_STRIP); + glColor4f(1,0,0,1); + glVertex3fv(pos.mV); + glColor4f(0,1,0,1); + glVertex3dv(drawable->getPositionGroup().mdV); + glColor4f(0,0,1,1); + glVertex3fv(nodeCenter.mV); + glColor4f(1,1,0,1); + glVertex3fv(octCenter.mV); + glEnd(); + } + + if (drawable->getVOVolume() && gPipeline.hasRenderDebugMask(LLPipeline::RENDER_DEBUG_FACE_CHAINS | LLPipeline::RENDER_DEBUG_TEXTURE_PRIORITY)) + { + glLineWidth(3); + + for (int face=0; face<drawable->getNumFaces(); ++face) + { + LLFace *facep = drawable->getFace(face); + + if (gPipeline.hasRenderDebugMask(LLPipeline::RENDER_DEBUG_FACE_CHAINS)) + { + LLGLDepthTest depth(GL_FALSE); + if (facep->mNextFace) + { + glBegin(GL_LINE_STRIP); + + if (facep->isState(LLFace::GLOBAL)) + { + glColor4f(0,1,0,1); + } + else + { + glColor4f(1,0.5f,0.25f,1); + } + + if (drawable->isActive()) + { + glVertex3fv(facep->mCenterLocal.mV); + glVertex3fv(facep->mNextFace->mCenterLocal.mV); + } + else + { + glVertex3fv(facep->mCenterAgent.mV); + glVertex3fv(facep->mNextFace->mCenterAgent.mV); + } + + glEnd(); + } + else + { + glPointSize(5); + glBegin(GL_POINTS); + + if (!facep->isState(LLFace::GLOBAL)) + { + glColor4f(1,0.75f,0,1); + glVertex3fv(facep->mCenterLocal.mV); + } + else + { + glColor4f(0,0.75f,1,1); + glVertex3fv(facep->mCenterAgent.mV); + } + + glEnd(); + glPointSize(1); + } + } + + if (gPipeline.hasRenderDebugMask(LLPipeline::RENDER_DEBUG_TEXTURE_PRIORITY)) + { + LLVector4 cold(0,0,0.25f); + LLVector4 hot(1,0.25f,0.25f); + + LLVector4 boost_cold(0,0,0,0); + LLVector4 boost_hot(0,1,0,1); + + LLGLDisable blend(GL_BLEND); + + LLViewerImage* imagep = facep->getTexture(); + if (imagep) + { + + //F32 vsize = LLVOVolume::getTextureVirtualSize(facep); + F32 vsize = imagep->mMaxVirtualSize; + + if (vsize > sCurMaxTexPriority) + { + sCurMaxTexPriority = vsize; + } + + F32 t = vsize/sLastMaxTexPriority; + + LLVector4 col = lerp(cold, hot, t); + glColor4fv(col.mV); + } + else + { + glColor4f(1,0,1,1); + } + + LLVector3 center = (facep->mExtents[1]+facep->mExtents[0])*0.5f; + LLVector3 size = (facep->mExtents[1]-facep->mExtents[0])*0.5f + LLVector3(0.01f, 0.01f, 0.01f); + drawBox(center, size); + + S32 boost = imagep->getBoostLevel(); + if (boost) + { + F32 t = (F32) boost / (F32) (LLViewerImage::BOOST_MAX_LEVEL-1); + LLVector4 col = lerp(boost_cold, boost_hot, t); + LLGLEnable blend_on(GL_BLEND); + glBlendFunc(GL_SRC_ALPHA, GL_ONE); + glColor4fv(col.mV); + drawBox(center, size); + glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA); + } + + } + } + } + + if (gPipeline.hasRenderDebugMask(LLPipeline::RENDER_DEBUG_POINTS)) + { + glPointSize(4); + glColor4f(1,1,1,1); + glBegin(GL_POINTS); + S32 num_faces = drawable->getNumFaces(); + for (S32 i = 0; i < num_faces; i++) + { + LLStrider<LLVector3> vertices; + drawable->getFace(i)->getVertices(vertices); + + LLFace* face = drawable->getFace(i); + + for (S32 v = 0; v < (S32)drawable->getFace(i)->getGeomCount(); v++) + { + if (!face->getDrawable()->isActive()) + { + //glVertex3fv(vertices[v].mV); + } + else + { + glVertex3fv((vertices[v]*face->getRenderMatrix()).mV); + } + } + } + glEnd(); + glPointSize(1); + } + + glLineWidth(1); + } + } +}; + +void LLSpatialPartition::renderDebug() +{ + if (!gPipeline.hasRenderDebugMask(LLPipeline::RENDER_DEBUG_OCTREE | + LLPipeline::RENDER_DEBUG_OCCLUSION | + LLPipeline::RENDER_DEBUG_BBOXES | + LLPipeline::RENDER_DEBUG_POINTS | + LLPipeline::RENDER_DEBUG_FACE_CHAINS | + LLPipeline::RENDER_DEBUG_TEXTURE_PRIORITY)) + { + return; + } + + if (gPipeline.hasRenderDebugMask(LLPipeline::RENDER_DEBUG_TEXTURE_PRIORITY)) + { + //sLastMaxTexPriority = lerp(sLastMaxTexPriority, sCurMaxTexPriority, gFrameIntervalSeconds); + sLastMaxTexPriority = sCurMaxTexPriority; + sCurMaxTexPriority = 0.f; + } + + LLMemType mt(LLMemType::MTYPE_SPACE_PARTITION); + + LLGLDisable cullface(GL_CULL_FACE); + LLGLEnable blend(GL_BLEND); + glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA); + LLGLDisable tex(GL_TEXTURE_2D); + gPipeline.disableLights(); + + LLOctreeRenderNonOccluded render_debug; + render_debug.traverse(mOctree); + + LLGLDisable cull_face(GL_CULL_FACE); + + { + LLGLDepthTest gls_depth(GL_TRUE, GL_FALSE); + + //draw frustum + glColor4f(0,0,1,0.5f); + glBegin(GL_QUADS); + //glVertex3fv(gCamera->mAgentFrustum[0].mV); + //glVertex3fv(gCamera->mAgentFrustum[1].mV); + //glVertex3fv(gCamera->mAgentFrustum[2].mV); + //glVertex3fv(gCamera->mAgentFrustum[3].mV); + + //glVertex3fv(gCamera->mAgentFrustum[4].mV); + //glVertex3fv(gCamera->mAgentFrustum[5].mV); + //glVertex3fv(gCamera->mAgentFrustum[6].mV); + //glVertex3fv(gCamera->mAgentFrustum[7].mV); + + glVertex3fv(gCamera->mAgentFrustum[0].mV); + glVertex3fv(gCamera->mAgentFrustum[1].mV); + glVertex3fv(gCamera->mAgentFrustum[5].mV); + glVertex3fv(gCamera->mAgentFrustum[4].mV); + + glVertex3fv(gCamera->mAgentFrustum[1].mV); + glVertex3fv(gCamera->mAgentFrustum[2].mV); + glVertex3fv(gCamera->mAgentFrustum[6].mV); + glVertex3fv(gCamera->mAgentFrustum[5].mV); + + glVertex3fv(gCamera->mAgentFrustum[2].mV); + glVertex3fv(gCamera->mAgentFrustum[3].mV); + glVertex3fv(gCamera->mAgentFrustum[7].mV); + glVertex3fv(gCamera->mAgentFrustum[6].mV); + + glVertex3fv(gCamera->mAgentFrustum[3].mV); + glVertex3fv(gCamera->mAgentFrustum[0].mV); + glVertex3fv(gCamera->mAgentFrustum[4].mV); + glVertex3fv(gCamera->mAgentFrustum[7].mV); + + glEnd(); + } + + if (gPipeline.hasRenderDebugMask(LLPipeline::RENDER_DEBUG_OCCLUSION)) + { + LLGLDisable fog(GL_FOG); + LLGLDepthTest gls_depth(GL_FALSE); + glBlendFunc(GL_SRC_ALPHA, GL_ONE); + + for (std::vector<LLSpatialGroup*>::iterator i = mOccludedList.begin(); i != mOccludedList.end(); ++i) + { //draw occluded nodes + LLSpatialGroup* node = *i; + if (node->isDead()) + { + continue; + } + if (!node->isState(LLSpatialGroup::OCCLUDED)) + { + continue; + } + else + { + glColor4f(0.25f,0.125f,0.1f,0.125f); + } + LLVector3 c; + LLVector3 r; + + c = node->mBounds[0]; + r = node->mBounds[1]*SG_OCCLUSION_FUDGE + LLVector3(0.01f,0.01f,0.01f);; + + drawBox(c,r); + } + glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA); + } +} + + +BOOL LLSpatialPartition::isVisible(const LLVector3& v) +{ + if (!gCamera->sphereInFrustum(v, 4.0f)) + { + return FALSE; + } + + return TRUE; +} + +class LLOctreePick : public LLSpatialGroup::OctreeTraveler +{ +public: + LLVector3 mStart; + LLVector3 mEnd; + LLDrawable* mRet; + + LLOctreePick(LLVector3 start, LLVector3 end) + : mStart(start), mEnd(end) + { + mRet = NULL; + } + + virtual LLDrawable* check(const LLSpatialGroup::OctreeNode* node) + { + const LLSpatialGroup::OctreeState* state = node->getOctState(); + state->accept(this); + + for (U32 i = 0; i < node->getChildCount(); i++) + { + const LLSpatialGroup::OctreeNode* child = node->getChild(i); + LLVector3 res; + + LLSpatialGroup* group = (LLSpatialGroup*) child->getListener(0); + + LLVector3 size; + LLVector3 center; + + size = group->mBounds[1]; + center = group->mBounds[0]; + + if (LLLineSegmentAABB(mStart, mEnd, center, size)) + { + check(child); + } + } + + return mRet; + } + + virtual void visit(const LLSpatialGroup::OctreeState* branch) + { + for (LLSpatialGroup::OctreeState::const_element_iter i = branch->getData().begin(); i != branch->getData().end(); ++i) + { + check(*i); + } + } + + virtual bool check(LLDrawable* drawable) + { + LLViewerObject* vobj = drawable->getVObj(); + if (vobj->lineSegmentIntersect(mStart, mEnd)) + { + mRet = vobj->mDrawable; + } + + return false; + } +}; + +LLDrawable* LLSpatialPartition::pickDrawable(const LLVector3& start, const LLVector3& end, LLVector3& collision) +{ + LLOctreePick pick(start, end); + LLDrawable* ret = pick.check(mOctree); + collision.setVec(pick.mEnd); + return ret; +} |