diff options
Diffstat (limited to 'indra/newview/llvieweroctree.h')
| -rw-r--r-- | indra/newview/llvieweroctree.h | 420 |
1 files changed, 420 insertions, 0 deletions
diff --git a/indra/newview/llvieweroctree.h b/indra/newview/llvieweroctree.h new file mode 100644 index 0000000000..219ec7e8da --- /dev/null +++ b/indra/newview/llvieweroctree.h @@ -0,0 +1,420 @@ +/** + * @file llvieweroctree.h + * @brief LLViewerObjectOctree.cpp header file, defining all supporting classes. + * + * $LicenseInfo:firstyear=2002&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$ + */ + +#ifndef LL_VIEWEROCTREE_H +#define LL_VIEWEROCTREE_H + +#include <vector> +#include <map> + +#include "v2math.h" +#include "v3math.h" +#include "v4math.h" +#include "m4math.h" +#include "llvector4a.h" +#include "llquaternion.h" +#include "lloctree.h" +#include "llviewercamera.h" + +class LLViewerRegion; +class LLViewerOctreeEntryData; +class LLViewerOctreeGroup; +class LLViewerOctreeEntry; +class LLViewerOctreePartition; + +typedef LLOctreeListener<LLViewerOctreeEntry> OctreeListener; +typedef LLTreeNode<LLViewerOctreeEntry> TreeNode; +typedef LLOctreeNode<LLViewerOctreeEntry> OctreeNode; +typedef LLOctreeRoot<LLViewerOctreeEntry> OctreeRoot; +typedef LLOctreeTraveler<LLViewerOctreeEntry> OctreeTraveler; + +#if LL_OCTREE_PARANOIA_CHECK +#define assert_octree_valid(x) x->validate() +#define assert_states_valid(x) ((LLViewerOctreeGroup*) x->mSpatialPartition->mOctree->getListener(0))->checkStates() +#else +#define assert_octree_valid(x) +#define assert_states_valid(x) +#endif + +// get index buffer for binary encoded axis vertex buffer given a box at center being viewed by given camera +U32 get_box_fan_indices(LLCamera* camera, const LLVector4a& center); +U8* get_box_fan_indices_ptr(LLCamera* camera, const LLVector4a& center); + +S32 AABBSphereIntersect(const LLVector4a& min, const LLVector4a& max, const LLVector3 &origin, const F32 &rad); +S32 AABBSphereIntersectR2(const LLVector4a& min, const LLVector4a& max, const LLVector3 &origin, const F32 &radius_squared); + +S32 AABBSphereIntersect(const LLVector3& min, const LLVector3& max, const LLVector3 &origin, const F32 &rad); +S32 AABBSphereIntersectR2(const LLVector3& min, const LLVector3& max, const LLVector3 &origin, const F32 &radius_squared); + +//defines data needed for octree of an entry +//LL_ALIGN_PREFIX(16) +class LLViewerOctreeEntry : public LLRefCount, public LLTrace::MemTrackable<LLViewerOctreeEntry, 16> +{ + friend class LLViewerOctreeEntryData; + +public: + typedef enum + { + LLDRAWABLE = 0, + LLVOCACHEENTRY, + NUM_DATA_TYPE + }eEntryDataType_t; + +protected: + virtual ~LLViewerOctreeEntry(); + +public: + LLViewerOctreeEntry(); + + void nullGroup(); //called by group handleDestruction() only + void setGroup(LLViewerOctreeGroup* group); + void removeData(LLViewerOctreeEntryData* data); + + LLViewerOctreeEntryData* getDrawable() const {return mData[LLDRAWABLE];} + bool hasDrawable() const {return mData[LLDRAWABLE] != NULL;} + LLViewerOctreeEntryData* getVOCacheEntry() const {return mData[LLVOCACHEENTRY];} + bool hasVOCacheEntry() const {return mData[LLVOCACHEENTRY] != NULL;} + + const LLVector4a* getSpatialExtents() const {return mExtents;} + const LLVector4a& getPositionGroup() const {return mPositionGroup;} + LLViewerOctreeGroup* getGroup()const {return mGroup;} + + F32 getBinRadius() const {return mBinRadius;} + S32 getBinIndex() const {return mBinIndex; } + void setBinIndex(S32 index) const {mBinIndex = index; } + +private: + void addData(LLViewerOctreeEntryData* data); + +private: + LLViewerOctreeEntryData* mData[NUM_DATA_TYPE]; //do not use LLPointer here. + LLViewerOctreeGroup* mGroup; + + //aligned members + LL_ALIGN_16(LLVector4a mExtents[2]); + LL_ALIGN_16(LLVector4a mPositionGroup); + F32 mBinRadius; + mutable S32 mBinIndex; + mutable U32 mVisible; + +} ;//LL_ALIGN_POSTFIX(16); + +//defines an abstract class for entry data +//LL_ALIGN_PREFIX(16) +class LLViewerOctreeEntryData : public LLRefCount +{ +protected: + virtual ~LLViewerOctreeEntryData(); + +public: + LLViewerOctreeEntryData(const LLViewerOctreeEntryData& rhs) + { + *this = rhs; + } + LLViewerOctreeEntryData(LLViewerOctreeEntry::eEntryDataType_t data_type); + + LLViewerOctreeEntry::eEntryDataType_t getDataType() const {return mDataType;} + LLViewerOctreeEntry* getEntry() {return mEntry;} + + virtual void setOctreeEntry(LLViewerOctreeEntry* entry); + void removeOctreeEntry(); + + F32 getBinRadius() const {return mEntry->getBinRadius();} + const LLVector4a* getSpatialExtents() const; + LLViewerOctreeGroup* getGroup()const; + const LLVector4a& getPositionGroup() const; + + void setBinRadius(F32 rad) {mEntry->mBinRadius = rad;} + void setSpatialExtents(const LLVector3& min, const LLVector3& max); + void setSpatialExtents(const LLVector4a& min, const LLVector4a& max); + void setPositionGroup(const LLVector4a& pos); + + virtual void setGroup(LLViewerOctreeGroup* group); + void shift(const LLVector4a &shift_vector); + + U32 getVisible() const {return mEntry ? mEntry->mVisible : 0;} + void setVisible() const; + void resetVisible() const; + virtual bool isVisible() const; + virtual bool isRecentlyVisible() const; + + static S32 getCurrentFrame() { return sCurVisible; } + +protected: + LLVector4a& getGroupPosition() {return mEntry->mPositionGroup;} + void initVisible(U32 visible) {mEntry->mVisible = visible;} + + static void incrementVisible() {sCurVisible++;} +protected: + LLPointer<LLViewerOctreeEntry> mEntry; + LLViewerOctreeEntry::eEntryDataType_t mDataType; + static U32 sCurVisible; // Counter for what value of mVisible means currently visible +};//LL_ALIGN_POSTFIX(16); + + +//defines an octree group for an octree node, which contains multiple entries. +//LL_ALIGN_PREFIX(16) +class LLViewerOctreeGroup +: public LLOctreeListener<LLViewerOctreeEntry>, public LLTrace::MemTrackable<LLViewerOctreeGroup, 16> +{ + friend class LLViewerOctreeCull; +protected: + virtual ~LLViewerOctreeGroup(); + +public: + enum + { + CLEAN = 0x00000000, + DIRTY = 0x00000001, + OBJECT_DIRTY = 0x00000002, + SKIP_FRUSTUM_CHECK = 0x00000004, + DEAD = 0x00000008, + INVALID_STATE = 0x00000010, + }; + +public: + typedef LLOctreeNode<LLViewerOctreeEntry>::element_iter element_iter; + typedef LLOctreeNode<LLViewerOctreeEntry>::element_list element_list; + + LLViewerOctreeGroup(OctreeNode* node); + LLViewerOctreeGroup(const LLViewerOctreeGroup& rhs) + : LLTrace::MemTrackable<LLViewerOctreeGroup, 16>("LLViewerOctreeGroup") + { + *this = rhs; + } + + bool removeFromGroup(LLViewerOctreeEntryData* data); + bool removeFromGroup(LLViewerOctreeEntry* entry); + + virtual void unbound(); + virtual void rebound(); + + BOOL isDead() { return hasState(DEAD); } + + void setVisible(); + BOOL isVisible() const; + virtual BOOL isRecentlyVisible() const; + S32 getVisible(LLViewerCamera::eCameraID id) const {return mVisible[id];} + S32 getAnyVisible() const {return mAnyVisible;} + bool isEmpty() const { return mOctreeNode->isEmpty(); } + + U32 getState() {return mState; } + bool isDirty() const {return mState & DIRTY;} + bool hasState(U32 state) const {return mState & state;} + void setState(U32 state) {mState |= state;} + void clearState(U32 state) {mState &= ~state;} + + //LISTENER FUNCTIONS + virtual void handleInsertion(const TreeNode* node, LLViewerOctreeEntry* obj); + virtual void handleRemoval(const TreeNode* node, LLViewerOctreeEntry* obj); + virtual void handleDestruction(const TreeNode* node); + virtual void handleStateChange(const TreeNode* node); + virtual void handleChildAddition(const OctreeNode* parent, OctreeNode* child); + virtual void handleChildRemoval(const OctreeNode* parent, const OctreeNode* child); + + OctreeNode* getOctreeNode() {return mOctreeNode;} + LLViewerOctreeGroup* getParent(); + + const LLVector4a* getBounds() const {return mBounds;} + const LLVector4a* getExtents() const {return mExtents;} + const LLVector4a* getObjectBounds() const {return mObjectBounds;} + const LLVector4a* getObjectExtents() const {return mObjectExtents;} + + //octree wrappers to make code more readable + element_list& getData() { return mOctreeNode->getData(); } + element_iter getDataBegin() { return mOctreeNode->getDataBegin(); } + element_iter getDataEnd() { return mOctreeNode->getDataEnd(); } + U32 getElementCount() const { return mOctreeNode->getElementCount(); } + bool hasElement(LLViewerOctreeEntryData* data); + +protected: + void checkStates(); +private: + virtual bool boundObjects(BOOL empty, LLVector4a& minOut, LLVector4a& maxOut); + +protected: + U32 mState; + OctreeNode* mOctreeNode; + + LL_ALIGN_16(LLVector4a mBounds[2]); // bounding box (center, size) of this node and all its children (tight fit to objects) + LL_ALIGN_16(LLVector4a mObjectBounds[2]); // bounding box (center, size) of objects in this node + LL_ALIGN_16(LLVector4a mExtents[2]); // extents (min, max) of this node and all its children + LL_ALIGN_16(LLVector4a mObjectExtents[2]); // extents (min, max) of objects in this node + + S32 mAnyVisible; //latest visible to any camera + S32 mVisible[LLViewerCamera::NUM_CAMERAS]; + +};//LL_ALIGN_POSTFIX(16); + +//octree group which has capability to support occlusion culling +//LL_ALIGN_PREFIX(16) +class LLOcclusionCullingGroup : public LLViewerOctreeGroup +{ +public: + typedef enum + { + OCCLUDED = 0x00010000, + QUERY_PENDING = 0x00020000, + ACTIVE_OCCLUSION = 0x00040000, + DISCARD_QUERY = 0x00080000, + EARLY_FAIL = 0x00100000, + } eOcclusionState; + + typedef enum + { + STATE_MODE_SINGLE = 0, //set one node + STATE_MODE_BRANCH, //set entire branch + STATE_MODE_DIFF, //set entire branch as long as current state is different + STATE_MODE_ALL_CAMERAS, //used for occlusion state, set state for all cameras + } eSetStateMode; + +protected: + virtual ~LLOcclusionCullingGroup(); + +public: + LLOcclusionCullingGroup(OctreeNode* node, LLViewerOctreePartition* part); + LLOcclusionCullingGroup(const LLOcclusionCullingGroup& rhs) : LLViewerOctreeGroup(rhs) + { + *this = rhs; + } + + void setOcclusionState(U32 state, S32 mode = STATE_MODE_SINGLE); + void clearOcclusionState(U32 state, S32 mode = STATE_MODE_SINGLE); + void checkOcclusion(); //read back last occlusion query (if any) + void doOcclusion(LLCamera* camera, const LLVector4a* shift = NULL); //issue occlusion query + BOOL isOcclusionState(U32 state) const { return mOcclusionState[LLViewerCamera::sCurCameraID] & state ? TRUE : FALSE; } + U32 getOcclusionState() const { return mOcclusionState[LLViewerCamera::sCurCameraID];} + + BOOL needsUpdate(); + U32 getLastOcclusionIssuedTime(); + + //virtual + void handleChildAddition(const OctreeNode* parent, OctreeNode* child); + + //virtual + BOOL isRecentlyVisible() const; + LLViewerOctreePartition* getSpatialPartition()const {return mSpatialPartition;} + BOOL isAnyRecentlyVisible() const; + + static U32 getNewOcclusionQueryObjectName(); + static void releaseOcclusionQueryObjectName(U32 name); + +protected: + void releaseOcclusionQueryObjectNames(); + +private: + BOOL earlyFail(LLCamera* camera, const LLVector4a* bounds); + +protected: + U32 mOcclusionState[LLViewerCamera::NUM_CAMERAS]; + U32 mOcclusionIssued[LLViewerCamera::NUM_CAMERAS]; + + S32 mLODHash; + + LLViewerOctreePartition* mSpatialPartition; + U32 mOcclusionQuery[LLViewerCamera::NUM_CAMERAS]; + +public: + static std::set<U32> sPendingQueries; +};//LL_ALIGN_POSTFIX(16); + +class LLViewerOctreePartition +{ +public: + LLViewerOctreePartition(); + virtual ~LLViewerOctreePartition(); + + // Cull on arbitrary frustum + virtual S32 cull(LLCamera &camera, bool do_occlusion) = 0; + BOOL isOcclusionEnabled(); + +public: + U32 mPartitionType; + U32 mDrawableType; + OctreeNode* mOctree; + LLViewerRegion* mRegionp; // the region this partition belongs to. + BOOL mOcclusionEnabled; // if TRUE, occlusion culling is performed + U32 mLODSeed; + U32 mLODPeriod; //number of frames between LOD updates for a given spatial group (staggered by mLODSeed) +}; + +class LLViewerOctreeCull : public OctreeTraveler +{ +public: + LLViewerOctreeCull(LLCamera* camera) + : mCamera(camera), mRes(0) { } + + virtual void traverse(const OctreeNode* n); + +protected: + virtual bool earlyFail(LLViewerOctreeGroup* group); + + //agent space group cull + S32 AABBInFrustumNoFarClipGroupBounds(const LLViewerOctreeGroup* group); + S32 AABBSphereIntersectGroupExtents(const LLViewerOctreeGroup* group); + S32 AABBInFrustumGroupBounds(const LLViewerOctreeGroup* group); + + //agent space object set cull + S32 AABBInFrustumNoFarClipObjectBounds(const LLViewerOctreeGroup* group); + S32 AABBSphereIntersectObjectExtents(const LLViewerOctreeGroup* group); + S32 AABBInFrustumObjectBounds(const LLViewerOctreeGroup* group); + + //local region space group cull + S32 AABBInRegionFrustumNoFarClipGroupBounds(const LLViewerOctreeGroup* group); + S32 AABBInRegionFrustumGroupBounds(const LLViewerOctreeGroup* group); + S32 AABBRegionSphereIntersectGroupExtents(const LLViewerOctreeGroup* group, const LLVector3& shift); + + //local region space object set cull + S32 AABBInRegionFrustumNoFarClipObjectBounds(const LLViewerOctreeGroup* group); + S32 AABBInRegionFrustumObjectBounds(const LLViewerOctreeGroup* group); + S32 AABBRegionSphereIntersectObjectExtents(const LLViewerOctreeGroup* group, const LLVector3& shift); + + virtual S32 frustumCheck(const LLViewerOctreeGroup* group) = 0; + virtual S32 frustumCheckObjects(const LLViewerOctreeGroup* group) = 0; + + bool checkProjectionArea(const LLVector4a& center, const LLVector4a& size, const LLVector3& shift, F32 pixel_threshold, F32 near_radius); + virtual bool checkObjects(const OctreeNode* branch, const LLViewerOctreeGroup* group); + virtual void preprocess(LLViewerOctreeGroup* group); + virtual void processGroup(LLViewerOctreeGroup* group); + virtual void visit(const OctreeNode* branch); + +protected: + LLCamera *mCamera; + S32 mRes; +}; + +//scan the octree, output the info of each node for debug use. +class LLViewerOctreeDebug : public OctreeTraveler +{ +public: + virtual void processGroup(LLViewerOctreeGroup* group); + virtual void visit(const OctreeNode* branch); + +public: + static BOOL sInDebug; +}; + +#endif |