1 // 2 // Copyright (c) 2008-2017 the Urho3D project. 3 // 4 // Permission is hereby granted, free of charge, to any person obtaining a copy 5 // of this software and associated documentation files (the "Software"), to deal 6 // in the Software without restriction, including without limitation the rights 7 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 8 // copies of the Software, and to permit persons to whom the Software is 9 // furnished to do so, subject to the following conditions: 10 // 11 // The above copyright notice and this permission notice shall be included in 12 // all copies or substantial portions of the Software. 13 // 14 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 15 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 16 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 17 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 18 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 19 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 20 // THE SOFTWARE. 21 // 22 23 #pragma once 24 25 #include "../Container/List.h" 26 #include "../Core/Mutex.h" 27 #include "../Graphics/Drawable.h" 28 #include "../Graphics/OctreeQuery.h" 29 30 namespace Urho3D 31 { 32 33 class Octree; 34 35 static const int NUM_OCTANTS = 8; 36 static const unsigned ROOT_INDEX = M_MAX_UNSIGNED; 37 38 /// %Octree octant 39 class URHO3D_API Octant 40 { 41 public: 42 /// Construct. 43 Octant(const BoundingBox& box, unsigned level, Octant* parent, Octree* root, unsigned index = ROOT_INDEX); 44 /// Destruct. Move drawables to root if available (detach if not) and free child octants. 45 virtual ~Octant(); 46 47 /// Return or create a child octant. 48 Octant* GetOrCreateChild(unsigned index); 49 /// Delete child octant. 50 void DeleteChild(unsigned index); 51 /// Insert a drawable object by checking for fit recursively. 52 void InsertDrawable(Drawable* drawable); 53 /// Check if a drawable object fits. 54 bool CheckDrawableFit(const BoundingBox& box) const; 55 56 /// Add a drawable object to this octant. AddDrawable(Drawable * drawable)57 void AddDrawable(Drawable* drawable) 58 { 59 drawable->SetOctant(this); 60 drawables_.Push(drawable); 61 IncDrawableCount(); 62 } 63 64 /// Remove a drawable object from this octant. 65 void RemoveDrawable(Drawable* drawable, bool resetOctant = true) 66 { 67 if (drawables_.Remove(drawable)) 68 { 69 if (resetOctant) 70 drawable->SetOctant(0); 71 DecDrawableCount(); 72 } 73 } 74 75 /// Return world-space bounding box. GetWorldBoundingBox()76 const BoundingBox& GetWorldBoundingBox() const { return worldBoundingBox_; } 77 78 /// Return bounding box used for fitting drawable objects. GetCullingBox()79 const BoundingBox& GetCullingBox() const { return cullingBox_; } 80 81 /// Return subdivision level. GetLevel()82 unsigned GetLevel() const { return level_; } 83 84 /// Return parent octant. GetParent()85 Octant* GetParent() const { return parent_; } 86 87 /// Return octree root. GetRoot()88 Octree* GetRoot() const { return root_; } 89 90 /// Return number of drawables. GetNumDrawables()91 unsigned GetNumDrawables() const { return numDrawables_; } 92 93 /// Return true if there are no drawable objects in this octant and child octants. IsEmpty()94 bool IsEmpty() { return numDrawables_ == 0; } 95 96 /// Reset root pointer recursively. Called when the whole octree is being destroyed. 97 void ResetRoot(); 98 /// Draw bounds to the debug graphics recursively. 99 void DrawDebugGeometry(DebugRenderer* debug, bool depthTest); 100 101 protected: 102 /// Initialize bounding box. 103 void Initialize(const BoundingBox& box); 104 /// Return drawable objects by a query, called internally. 105 void GetDrawablesInternal(OctreeQuery& query, bool inside) const; 106 /// Return drawable objects by a ray query, called internally. 107 void GetDrawablesInternal(RayOctreeQuery& query) const; 108 /// Return drawable objects only for a threaded ray query, called internally. 109 void GetDrawablesOnlyInternal(RayOctreeQuery& query, PODVector<Drawable*>& drawables) const; 110 111 /// Increase drawable object count recursively. IncDrawableCount()112 void IncDrawableCount() 113 { 114 ++numDrawables_; 115 if (parent_) 116 parent_->IncDrawableCount(); 117 } 118 119 /// Decrease drawable object count recursively and remove octant if it becomes empty. DecDrawableCount()120 void DecDrawableCount() 121 { 122 Octant* parent = parent_; 123 124 --numDrawables_; 125 if (!numDrawables_) 126 { 127 if (parent) 128 parent->DeleteChild(index_); 129 } 130 131 if (parent) 132 parent->DecDrawableCount(); 133 } 134 135 /// World bounding box. 136 BoundingBox worldBoundingBox_; 137 /// Bounding box used for drawable object fitting. 138 BoundingBox cullingBox_; 139 /// Drawable objects. 140 PODVector<Drawable*> drawables_; 141 /// Child octants. 142 Octant* children_[NUM_OCTANTS]; 143 /// World bounding box center. 144 Vector3 center_; 145 /// World bounding box half size. 146 Vector3 halfSize_; 147 /// Subdivision level. 148 unsigned level_; 149 /// Number of drawable objects in this octant and child octants. 150 unsigned numDrawables_; 151 /// Parent octant. 152 Octant* parent_; 153 /// Octree root. 154 Octree* root_; 155 /// Octant index relative to its siblings or ROOT_INDEX for root octant 156 unsigned index_; 157 }; 158 159 /// %Octree component. Should be added only to the root scene node 160 class URHO3D_API Octree : public Component, public Octant 161 { 162 friend void RaycastDrawablesWork(const WorkItem* item, unsigned threadIndex); 163 164 URHO3D_OBJECT(Octree, Component); 165 166 public: 167 /// Construct. 168 Octree(Context* context); 169 /// Destruct. 170 ~Octree(); 171 /// Register object factory. 172 static void RegisterObject(Context* context); 173 174 /// Handle attribute change. 175 virtual void OnSetAttribute(const AttributeInfo& attr, const Variant& src); 176 /// Visualize the component as debug geometry. 177 virtual void DrawDebugGeometry(DebugRenderer* debug, bool depthTest); 178 179 /// Set size and maximum subdivision levels. If octree is not empty, drawable objects will be temporarily moved to the root. 180 void SetSize(const BoundingBox& box, unsigned numLevels); 181 /// Update and reinsert drawable objects. 182 void Update(const FrameInfo& frame); 183 /// Add a drawable manually. 184 void AddManualDrawable(Drawable* drawable); 185 /// Remove a manually added drawable. 186 void RemoveManualDrawable(Drawable* drawable); 187 188 /// Return drawable objects by a query. 189 void GetDrawables(OctreeQuery& query) const; 190 /// Return drawable objects by a ray query. 191 void Raycast(RayOctreeQuery& query) const; 192 /// Return the closest drawable object by a ray query. 193 void RaycastSingle(RayOctreeQuery& query) const; 194 195 /// Return subdivision levels. GetNumLevels()196 unsigned GetNumLevels() const { return numLevels_; } 197 198 /// Mark drawable object as requiring an update and a reinsertion. 199 void QueueUpdate(Drawable* drawable); 200 /// Cancel drawable object's update. 201 void CancelUpdate(Drawable* drawable); 202 /// Visualize the component as debug geometry. 203 void DrawDebugGeometry(bool depthTest); 204 205 private: 206 /// Handle render update in case of headless execution. 207 void HandleRenderUpdate(StringHash eventType, VariantMap& eventData); 208 209 /// Drawable objects that require update. 210 PODVector<Drawable*> drawableUpdates_; 211 /// Drawable objects that were inserted during threaded update phase. 212 PODVector<Drawable*> threadedDrawableUpdates_; 213 /// Mutex for octree reinsertions. 214 Mutex octreeMutex_; 215 /// Ray query temporary list of drawables. 216 mutable PODVector<Drawable*> rayQueryDrawables_; 217 /// Subdivision level. 218 unsigned numLevels_; 219 }; 220 221 } 222