llvieweroctree.h 15 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525
  1. /**
  2. * @file llvieweroctree.h
  3. * @brief LLViewerObjectOctree header file including definitions for supporting functions
  4. *
  5. * $LicenseInfo:firstyear=2003&license=viewergpl$
  6. *
  7. * Copyright (c) 2003-2009, Linden Research, Inc.
  8. *
  9. * Second Life Viewer Source Code
  10. * The source code in this file ("Source Code") is provided by Linden Lab
  11. * to you under the terms of the GNU General Public License, version 2.0
  12. * ("GPL"), unless you have obtained a separate licensing agreement
  13. * ("Other License"), formally executed by you and Linden Lab. Terms of
  14. * the GPL can be found in doc/GPL-license.txt in this distribution, or
  15. * online at http://secondlifegrid.net/programs/open_source/licensing/gplv2
  16. *
  17. * There are special exceptions to the terms and conditions of the GPL as
  18. * it is applied to this Source Code. View the full text of the exception
  19. * in the file doc/FLOSS-exception.txt in this software distribution, or
  20. * online at
  21. * http://secondlifegrid.net/programs/open_source/licensing/flossexception
  22. *
  23. * By copying, modifying or distributing this software, you acknowledge
  24. * that you have read and understood your obligations described above,
  25. * and agree to abide by those obligations.
  26. *
  27. * ALL LINDEN LAB SOURCE CODE IS PROVIDED "AS IS." LINDEN LAB MAKES NO
  28. * WARRANTIES, EXPRESS, IMPLIED OR OTHERWISE, REGARDING ITS ACCURACY,
  29. * COMPLETENESS OR PERFORMANCE.
  30. * $/LicenseInfo$
  31. */
  32. #ifndef LL_VIEWEROCTREE_H
  33. #define LL_VIEWEROCTREE_H
  34. #include <map>
  35. #include <vector>
  36. #include "llvector2.h"
  37. #include "llvector4.h"
  38. #include "llmatrix4.h"
  39. #include "lloctree.h"
  40. #include "llrefcount.h"
  41. #include "llviewercamera.h"
  42. class LLVertexBuffer;
  43. class LLViewerRegion;
  44. class LLViewerOctreeEntry;
  45. class LLViewerOctreeEntryData;
  46. class LLViewerOctreeGroup;
  47. class LLViewerOctreePartition;
  48. typedef LLOctreeListener<LLViewerOctreeEntry> OctreeListener;
  49. typedef LLOctreeNode<LLViewerOctreeEntry> OctreeNode;
  50. typedef LLOctreeRoot<LLViewerOctreeEntry> OctreeRoot;
  51. typedef LLOctreeTraveler<LLViewerOctreeEntry> OctreeTraveler;
  52. typedef LLTreeNode<LLViewerOctreeEntry> TreeNode;
  53. // Gets index buffer for binary encoded axis vertex buffer given a box at
  54. // center being viewed by given camera
  55. U32 get_box_fan_indices(LLCamera* camera, const LLVector4a& center);
  56. U8* get_box_fan_indices_ptr(LLCamera* camera, const LLVector4a& center);
  57. S32 AABBSphereIntersect(const LLVector4a& min, const LLVector4a& max,
  58. const LLVector3& origin, const F32& rad);
  59. S32 AABBSphereIntersectR2(const LLVector4a& min, const LLVector4a& max,
  60. const LLVector3& origin, const F32& radius_squared);
  61. S32 AABBSphereIntersect(const LLVector3& min, const LLVector3& max,
  62. const LLVector3& origin, const F32& rad);
  63. S32 AABBSphereIntersectR2(const LLVector3& min, const LLVector3& max,
  64. const LLVector3& origin, const F32& radius_squared);
  65. // Defines data needed for octree of an entry
  66. class alignas(16) LLViewerOctreeEntry : public LLRefCount
  67. {
  68. friend class LLViewerOctreeEntryData;
  69. public:
  70. LL_VOLUME_AREANA_NEW_DELETE
  71. typedef enum
  72. {
  73. LLDRAWABLE = 0,
  74. LLVOCACHEENTRY,
  75. NUM_DATA_TYPE
  76. } eEntryDataType_t;
  77. LLViewerOctreeEntry();
  78. // Called by group handleDestruction() only
  79. LL_INLINE void nullGroup() { mGroup = NULL; }
  80. void setGroup(LLViewerOctreeGroup* group);
  81. void removeData(LLViewerOctreeEntryData* data);
  82. LL_INLINE LLViewerOctreeEntryData* getDrawable() const
  83. {
  84. return mData[LLDRAWABLE];
  85. }
  86. LL_INLINE bool hasDrawable() const { return mData[LLDRAWABLE] != NULL; }
  87. LL_INLINE LLViewerOctreeEntryData* getVOCacheEntry() const
  88. {
  89. return mData[LLVOCACHEENTRY];
  90. }
  91. LL_INLINE bool hasVOCacheEntry() const { return mData[LLVOCACHEENTRY] != NULL; }
  92. LL_INLINE const LLVector4a* getSpatialExtents() const
  93. {
  94. return mExtents;
  95. }
  96. LL_INLINE const LLVector4a& getPositionGroup() const
  97. {
  98. return mPositionGroup;
  99. }
  100. LL_INLINE LLViewerOctreeGroup* getGroup() const { return mGroup; }
  101. LL_INLINE F32 getBinRadius() const { return mBinRadius; }
  102. LL_INLINE S32 getBinIndex() const { return mBinIndex; }
  103. LL_INLINE void setBinIndex(S32 index) const { mBinIndex = index; }
  104. protected:
  105. ~LLViewerOctreeEntry() override;
  106. private:
  107. void addData(LLViewerOctreeEntryData* data);
  108. private:
  109. // Note: before these variables, we find the 32 bits counter from
  110. // LLRefCount... Since mExtents will be 16-bytes aligned, fill-up the gap
  111. // in the cache line with other member variables. HB
  112. F32 mBinRadius;
  113. mutable S32 mBinIndex;
  114. mutable U32 mVisible;
  115. // Aligned members
  116. alignas(16) LLVector4a mExtents[2];
  117. LLVector4a mPositionGroup;
  118. // Do not use LLPointer here:
  119. LLViewerOctreeEntryData* mData[NUM_DATA_TYPE];
  120. LLViewerOctreeGroup* mGroup;
  121. };
  122. // Defines an abstract class for entry data
  123. class LLViewerOctreeEntryData : public LLRefCount
  124. {
  125. protected:
  126. ~LLViewerOctreeEntryData() override;
  127. public:
  128. #if 0
  129. LL_VOLUME_AREANA_NEW_DELETE
  130. #endif
  131. LLViewerOctreeEntryData(const LLViewerOctreeEntryData& rhs)
  132. {
  133. *this = rhs;
  134. }
  135. LLViewerOctreeEntryData(LLViewerOctreeEntry::eEntryDataType_t data_type);
  136. LL_INLINE LLViewerOctreeEntry::eEntryDataType_t getDataType() const
  137. {
  138. return mDataType;
  139. }
  140. LL_INLINE LLViewerOctreeEntry* getEntry() { return mEntry; }
  141. virtual void setOctreeEntry(LLViewerOctreeEntry* entry);
  142. void removeOctreeEntry();
  143. LL_INLINE F32 getBinRadius() const { return mEntry->getBinRadius(); }
  144. const LLVector4a* getSpatialExtents() const;
  145. LLViewerOctreeGroup* getGroup()const;
  146. const LLVector4a& getPositionGroup() const;
  147. LL_INLINE void setBinRadius(F32 rad) { mEntry->mBinRadius = rad; }
  148. void setSpatialExtents(const LLVector3& min, const LLVector3& max);
  149. void setSpatialExtents(const LLVector4a& min, const LLVector4a& max);
  150. void setPositionGroup(const LLVector4a& pos);
  151. virtual void setGroup(LLViewerOctreeGroup* group);
  152. void shift(const LLVector4a& shift_vector);
  153. LL_INLINE U32 getVisible() const { return mEntry ? mEntry->mVisible : 0; }
  154. void setVisible() const;
  155. void resetVisible() const;
  156. virtual bool isVisible() const;
  157. virtual bool isRecentlyVisible() const;
  158. LL_INLINE static S32 getCurrentFrame() { return sCurVisible; }
  159. protected:
  160. LL_INLINE LLVector4a& getGroupPosition() { return mEntry->mPositionGroup; }
  161. LL_INLINE void initVisible(U32 visible) { mEntry->mVisible = visible; }
  162. LL_INLINE static void incrementVisible() { ++sCurVisible; }
  163. protected:
  164. // Note: the first member variable is 32 bits in order to align on 64 bits
  165. // for the next variable, counting the 32 bits counter from LLRefCount. HB
  166. LLViewerOctreeEntry::eEntryDataType_t mDataType;
  167. LLPointer<LLViewerOctreeEntry> mEntry;
  168. // Counter for what value of mVisible means currently visible
  169. static U32 sCurVisible;
  170. };
  171. // Defines an octree group for an octree node, which contains multiple entries.
  172. class alignas(16) LLViewerOctreeGroup : public LLOctreeListener<LLViewerOctreeEntry>
  173. {
  174. friend class LLViewerOctreeCull;
  175. protected:
  176. LOG_CLASS(LLViewerOctreeGroup);
  177. public:
  178. LL_VOLUME_AREANA_NEW_DELETE
  179. enum
  180. {
  181. CLEAN = 0x00000000,
  182. DIRTY = 0x00000001,
  183. OBJECT_DIRTY = 0x00000002,
  184. SKIP_FRUSTUM_CHECK = 0x00000004,
  185. DEAD = 0x00000008,
  186. INVALID_STATE = 0x00000010,
  187. };
  188. typedef LLOctreeNode<LLViewerOctreeEntry>::element_iter element_iter;
  189. typedef LLOctreeNode<LLViewerOctreeEntry>::element_list element_list;
  190. LLViewerOctreeGroup(OctreeNode* node);
  191. LLViewerOctreeGroup(const LLViewerOctreeGroup& rhs)
  192. {
  193. *this = rhs;
  194. }
  195. bool removeFromGroup(LLViewerOctreeEntryData* data);
  196. bool removeFromGroup(LLViewerOctreeEntry* entry);
  197. virtual void unbound();
  198. virtual void rebound();
  199. LL_INLINE bool isDead() { return hasState(DEAD); }
  200. void setVisible();
  201. bool isVisible() const;
  202. LL_INLINE virtual bool isRecentlyVisible() const
  203. {
  204. return false;
  205. }
  206. LL_INLINE S32 getVisible(S32 id) const { return mVisible[id]; }
  207. LL_INLINE S32 getAnyVisible() const { return mAnyVisible; }
  208. LL_INLINE bool isEmpty() const { return mOctreeNode->isEmpty(); }
  209. LL_INLINE U32 getState() { return mState; }
  210. LL_INLINE bool isDirty() const { return (mState & DIRTY) != 0; }
  211. LL_INLINE bool hasState(U32 state) const { return (mState & state) != 0; }
  212. LL_INLINE void setState(U32 state) { mState |= state; }
  213. LL_INLINE void clearState(U32 state) { mState &= ~state; }
  214. // Listener functions
  215. virtual void handleInsertion(const TreeNode* node,
  216. LLViewerOctreeEntry* obj);
  217. virtual void handleRemoval(const TreeNode* node,
  218. LLViewerOctreeEntry* obj);
  219. virtual void handleDestruction(const TreeNode* node);
  220. virtual void handleStateChange(const TreeNode* node);
  221. virtual void handleChildAddition(const OctreeNode* parent,
  222. OctreeNode* child);
  223. virtual void handleChildRemoval(const OctreeNode* parent,
  224. const OctreeNode* child);
  225. LL_INLINE OctreeNode* getOctreeNode() { return mOctreeNode; }
  226. LLViewerOctreeGroup* getParent();
  227. LL_INLINE const LLVector4a* getBounds() const { return mBounds; }
  228. LL_INLINE const LLVector4a* getExtents() const { return mExtents; }
  229. LL_INLINE const LLVector4a* getObjectBounds() const
  230. {
  231. return mObjectBounds;
  232. }
  233. LL_INLINE const LLVector4a* getObjectExtents() const
  234. {
  235. return mObjectExtents;
  236. }
  237. // Octree wrappers to make code more readable
  238. LL_INLINE const element_list& getData() const { return mOctreeNode->getData(); }
  239. LL_INLINE element_iter getDataBegin() { return mOctreeNode->getDataBegin(); }
  240. LL_INLINE element_iter getDataEnd() { return mOctreeNode->getDataEnd(); }
  241. LL_INLINE U32 getElementCount() const { return mOctreeNode->getElementCount(); }
  242. bool hasElement(LLViewerOctreeEntryData* data);
  243. private:
  244. virtual bool boundObjects(bool empty, LLVector4a& minOut,
  245. LLVector4a& maxOut);
  246. protected:
  247. // Bounding box (center, size) of this node and all its children (tight
  248. // fit to objects):
  249. alignas(16) LLVector4a mBounds[2];
  250. // Bounding box (center, size) of objects in this node:
  251. alignas(16) LLVector4a mObjectBounds[2];
  252. // Extents (min, max) of this node and all its children:
  253. alignas(16) LLVector4a mExtents[2];
  254. // Extents (min, max) of objects in this node:
  255. alignas(16) LLVector4a mObjectExtents[2];
  256. OctreeNode* mOctreeNode;
  257. S32 mVisible[LLViewerCamera::NUM_CAMERAS];
  258. U32 mState;
  259. S32 mAnyVisible; // Latest visible to any camera
  260. };
  261. // Octree group which has capability to support occlusion culling
  262. class LLOcclusionCullingGroup : public LLViewerOctreeGroup
  263. {
  264. public:
  265. typedef enum
  266. {
  267. OCCLUDED = 0x00010000,
  268. QUERY_PENDING = 0x00020000,
  269. ACTIVE_OCCLUSION = 0x00040000,
  270. DISCARD_QUERY = 0x00080000,
  271. EARLY_FAIL = 0x00100000,
  272. } eOcclusionState;
  273. typedef enum
  274. {
  275. STATE_MODE_SINGLE = 0, // Set one node
  276. STATE_MODE_BRANCH, // Set entire branch
  277. // Set entire branch as long as current state is different
  278. STATE_MODE_DIFF,
  279. // Used for occlusion state, set state for all cameras
  280. STATE_MODE_ALL_CAMERAS,
  281. } eSetStateMode;
  282. protected:
  283. ~LLOcclusionCullingGroup() override;
  284. public:
  285. LLOcclusionCullingGroup(OctreeNode* node, LLViewerOctreePartition* part);
  286. LLOcclusionCullingGroup(const LLOcclusionCullingGroup& rhs)
  287. : LLViewerOctreeGroup(rhs)
  288. {
  289. *this = rhs;
  290. }
  291. void setOcclusionState(U32 state, S32 mode = STATE_MODE_SINGLE);
  292. void clearOcclusionState(U32 state, S32 mode = STATE_MODE_SINGLE);
  293. void checkOcclusion(); // Reads back last occlusion query (if any)
  294. // Issues occlusion query:
  295. void doOcclusion(LLCamera* camera, const LLVector4a* shift = NULL);
  296. LL_INLINE bool isOcclusionState(U32 state) const
  297. {
  298. return (mOcclusionState[LLViewerCamera::sCurCameraID] & state) != 0;
  299. }
  300. LL_INLINE U32 getOcclusionState() const
  301. {
  302. return mOcclusionState[LLViewerCamera::sCurCameraID];
  303. }
  304. bool needsUpdate();
  305. U32 getLastOcclusionIssuedTime();
  306. void handleChildAddition(const OctreeNode* parent,
  307. OctreeNode* child) override;
  308. bool isRecentlyVisible() const override;
  309. bool isAnyRecentlyVisible() const;
  310. LL_INLINE LLViewerOctreePartition* getSpatialPartition() const
  311. {
  312. return mSpatialPartition;
  313. }
  314. static U32 getNewOcclusionQueryObjectName();
  315. static void releaseOcclusionQueryObjectName(U32 name);
  316. LL_INLINE static U32 getTimeouts() { return sOcclusionTimeouts; }
  317. protected:
  318. void releaseOcclusionQueryObjectNames();
  319. private:
  320. bool earlyFail(LLCamera* camera, const LLVector4a* bounds);
  321. protected:
  322. U32 mOcclusionState[LLViewerCamera::NUM_CAMERAS];
  323. U32 mOcclusionIssued[LLViewerCamera::NUM_CAMERAS];
  324. U32 mOcclusionChecks[LLViewerCamera::NUM_CAMERAS];
  325. U32 mOcclusionQuery[LLViewerCamera::NUM_CAMERAS];
  326. LLViewerOctreePartition* mSpatialPartition;
  327. S32 mLODHash;
  328. static U32 sOcclusionTimeouts;
  329. };
  330. class LLViewerOctreePartition
  331. {
  332. public:
  333. LLViewerOctreePartition();
  334. virtual ~LLViewerOctreePartition();
  335. // Cull on arbitrary frustum
  336. virtual S32 cull(LLCamera& camera, bool do_occlusion = false) = 0;
  337. bool isOcclusionEnabled();
  338. protected:
  339. // *Must* be called from destructors of any derived classes (SL-17276)
  340. void cleanup();
  341. public:
  342. OctreeNode* mOctree;
  343. // The region this partition belongs to:
  344. LLViewerRegion* mRegionp;
  345. U32 mPartitionType;
  346. U32 mDrawableType;
  347. U32 mLODSeed;
  348. // Number of frames between LOD updates for a given spatial group
  349. // (staggered by mLODSeed)
  350. U32 mLODPeriod;
  351. // If true, occlusion culling is performed:
  352. bool mOcclusionEnabled;
  353. };
  354. class LLViewerOctreeCull : public OctreeTraveler
  355. {
  356. protected:
  357. LOG_CLASS(LLViewerOctreeCull);
  358. public:
  359. LLViewerOctreeCull(LLCamera* camera)
  360. : mCamera(camera),
  361. mRes(0)
  362. {
  363. }
  364. void traverse(const OctreeNode* n) override;
  365. protected:
  366. virtual bool earlyFail(LLViewerOctreeGroup* group);
  367. // Agent space group cull
  368. S32 AABBInFrustumNoFarClipGroupBounds(const LLViewerOctreeGroup* group);
  369. S32 AABBSphereIntersectGroupExtents(const LLViewerOctreeGroup* group);
  370. S32 AABBInFrustumGroupBounds(const LLViewerOctreeGroup* group);
  371. // Agent space object set cull
  372. S32 AABBInFrustumNoFarClipObjectBounds(const LLViewerOctreeGroup* group);
  373. S32 AABBSphereIntersectObjectExtents(const LLViewerOctreeGroup* group);
  374. S32 AABBInFrustumObjectBounds(const LLViewerOctreeGroup* group);
  375. // Local region space group cull
  376. S32 AABBInRegionFrustumNoFarClipGroupBounds(const LLViewerOctreeGroup* group);
  377. S32 AABBInRegionFrustumGroupBounds(const LLViewerOctreeGroup* group);
  378. S32 AABBRegionSphereIntersectGroupExtents(const LLViewerOctreeGroup* group,
  379. const LLVector3& shift);
  380. // Local region space object set cull
  381. S32 AABBInRegionFrustumNoFarClipObjectBounds(const LLViewerOctreeGroup* group);
  382. S32 AABBInRegionFrustumObjectBounds(const LLViewerOctreeGroup* group);
  383. S32 AABBRegionSphereIntersectObjectExtents(const LLViewerOctreeGroup* group,
  384. const LLVector3& shift);
  385. virtual S32 frustumCheck(const LLViewerOctreeGroup* group) = 0;
  386. virtual S32 frustumCheckObjects(const LLViewerOctreeGroup* group) = 0;
  387. bool checkProjectionArea(const LLVector4a& center, const LLVector4a& size,
  388. const LLVector3& shift, F32 pixel_threshold,
  389. F32 near_radius);
  390. virtual bool checkObjects(const OctreeNode* branch,
  391. const LLViewerOctreeGroup* group);
  392. virtual void preprocess(LLViewerOctreeGroup* group);
  393. virtual void processGroup(LLViewerOctreeGroup* group);
  394. void visit(const OctreeNode* branch) override;
  395. protected:
  396. LLCamera* mCamera;
  397. S32 mRes;
  398. };
  399. // Scan the octree, output the info of each node for debug use.
  400. class LLViewerOctreeDebug : public OctreeTraveler
  401. {
  402. public:
  403. virtual void processGroup(LLViewerOctreeGroup* group);
  404. void visit(const OctreeNode* branch) override;
  405. public:
  406. static bool sInDebug;
  407. };
  408. // Called from LLPipeline
  409. bool ll_setup_cube_vb(LLVertexBuffer* vb);
  410. #endif