1 /* 2 ----------------------------------------------------------------------------- 3 This source file is part of OGRE 4 (Object-oriented Graphics Rendering Engine) 5 For the latest info, see http://www.ogre3d.org/ 6 7 Copyright (c) 2000-2013 Torus Knot Software Ltd 8 9 Permission is hereby granted, free of charge, to any person obtaining a copy 10 of this software and associated documentation files (the "Software"), to deal 11 in the Software without restriction, including without limitation the rights 12 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 13 copies of the Software, and to permit persons to whom the Software is 14 furnished to do so, subject to the following conditions: 15 16 The above copyright notice and this permission notice shall be included in 17 all copies or substantial portions of the Software. 18 19 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 20 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 21 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 22 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 23 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 24 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 25 THE SOFTWARE. 26 ----------------------------------------------------------------------------- 27 */ 28 29 #ifndef __Ogre_TerrainQuadTreeNode_H__ 30 #define __Ogre_TerrainQuadTreeNode_H__ 31 32 #include "OgreTerrainPrerequisites.h" 33 #include "OgreCommon.h" 34 #include "OgreHardwareIndexBuffer.h" 35 #include "OgreMovableObject.h" 36 #include "OgreRenderable.h" 37 38 39 40 namespace Ogre 41 { 42 class HardwareVertexBufferSharedPtr; 43 44 /** \addtogroup Optional Components 45 * @{ 46 */ 47 /** \addtogroup Terrain 48 * Some details on the terrain component 49 * @{ 50 */ 51 52 53 /** A node in a quad tree used to store a patch of terrain. 54 @remarks 55 <b>Algorithm overview:</b> 56 @par 57 Our goal is to perform traditional chunked LOD with geomorphing. But, 58 instead of just dividing the terrain into tiles, we will divide them into 59 a hierarchy of tiles, a quadtree, where any level of the quadtree can 60 be a rendered tile (to the exclusion of its children). The idea is to 61 collect together children into a larger batch with their siblings as LOD 62 decreases, to improve performance. 63 @par 64 The minBatchSize and maxBatchSize parameters on Terrain a key to 65 defining this behaviour. Both values are expressed in vertices down one axis. 66 maxBatchSize determines the number of tiles on one side of the terrain, 67 which is numTiles = (terrainSize-1) / (maxBatchSize-1). This in turn determines the depth 68 of the quad tree, which is sqrt(numTiles). The minBatchSize determines 69 the 'floor' of how low the number of vertices can go in a tile before it 70 has to be grouped together with its siblings to drop any lower. We also do not group 71 a tile with its siblings unless all of them are at this minimum batch size, 72 rather than trying to group them when they all end up on the same 'middle' LOD; 73 this is for several reasons; firstly, tiles hitting the same 'middle' LOD is 74 less likely and more transient if they have different levels of 'roughness', 75 and secondly since we're sharing a vertex / index pool between all tiles, 76 only grouping at the min level means that the number of combinations of 77 buffer sizes for any one tile is greatly simplified, making it easier to 78 pool data. To be more specific, any tile / quadtree node can only have 79 log2(maxBatchSize-1) - log2(minBatchSize-1) + 1 LOD levels (and if you set them 80 to the same value, LOD can only change by going up/down the quadtree). 81 The numbers of vertices / indices in each of these levels is constant for 82 the same (relative) LOD index no matter where you are in the tree, therefore 83 buffers can potentially be reused more easily. 84 */ 85 class _OgreTerrainExport TerrainQuadTreeNode : public TerrainAlloc 86 { 87 public: 88 /** Constructor. 89 @param terrain The ultimate parent terrain 90 @param parent Optional parent node (in which case xoff, yoff are 0 and size must be entire terrain) 91 @param xoff, yoff Offsets from the start of the terrain data in 2D 92 @param size The size of the node in vertices at the highest LOD 93 @param lod The base LOD level 94 @param depth The depth that this node is at in the tree (or convenience) 95 @param quadrant The index of the quadrant (0, 1, 2, 3) 96 */ 97 TerrainQuadTreeNode(Terrain* terrain, TerrainQuadTreeNode* parent, 98 uint16 xoff, uint16 yoff, uint16 size, uint16 lod, uint16 depth, uint16 quadrant); 99 virtual ~TerrainQuadTreeNode(); 100 101 /// Get the horizontal offset into the main terrain data of this node getXOffset()102 uint16 getXOffset() const { return mOffsetX; } 103 /// Get the vertical offset into the main terrain data of this node getYOffset()104 uint16 getYOffset() const { return mOffsetY; } 105 /// Is this a leaf node (no children) 106 bool isLeaf() const; 107 /// Get the base LOD level this node starts at (the highest LOD it handles) getBaseLod()108 uint16 getBaseLod() const { return mBaseLod; } 109 /// Get the number of LOD levels this node can represent itself (only > 1 for leaf nodes) 110 uint16 getLodCount() const; 111 /// Get child node 112 TerrainQuadTreeNode* getChild(unsigned short child) const; 113 /// Get parent node 114 TerrainQuadTreeNode* getParent() const; 115 /// Get ultimate parent terrain 116 Terrain* getTerrain() const; 117 118 /// Prepare node and children (perform CPU tasks, may be background thread) 119 void prepare(); 120 /// Prepare node from a stream 121 void prepare(StreamSerialiser& stream); 122 /// Load node and children (perform GPU tasks, will be render thread) 123 void load(); 124 /// Load node and children in a depth range (perform GPU tasks, will be render thread) 125 void load(uint16 depthStart, uint16 depthEnd); 126 void loadSelf(); 127 /// Unload node and children (perform GPU tasks, will be render thread) 128 void unload(); 129 /// Unload node and children in a depth range (perform GPU tasks, will be render thread) 130 void unload(uint16 depthStart, uint16 depthEnd); 131 /// Unprepare node and children (perform CPU tasks, may be background thread) 132 void unprepare(); 133 /// Save node to a stream 134 void save(StreamSerialiser& stream); 135 136 struct _OgreTerrainExport LodLevel : public TerrainAlloc 137 { 138 /// Number of vertices rendered down one side (not including skirts) 139 uint16 batchSize; 140 /// Index data on the gpu 141 IndexData* gpuIndexData; 142 /// Maximum delta height between this and the next lower lod 143 Real maxHeightDelta; 144 /// Temp calc area for max height delta 145 Real calcMaxHeightDelta; 146 /// The most recently calculated transition distance 147 Real lastTransitionDist; 148 /// The cFactor value used to calculate transitionDist 149 Real lastCFactor; 150 LodLevelLodLevel151 LodLevel() : batchSize(0), gpuIndexData(0), maxHeightDelta(0), calcMaxHeightDelta(0), 152 lastTransitionDist(0), lastCFactor(0) {} 153 }; 154 typedef vector<LodLevel*>::type LodLevelList; 155 156 /** Get the LodLevel information for a given lod. 157 @param lod The lod level index relative to this classes own list; if you 158 want to use a global lod level, subtract getBaseLod() first. Higher 159 LOD levels are lower detail. 160 */ 161 const LodLevel* getLodLevel(uint16 lod); 162 163 /** Notify the node (and children) that deltas are going to be calculated for a given range. 164 @remarks 165 Based on this call, we can know whether or not to reset the max height. 166 */ 167 void preDeltaCalculation(const Rect& rect); 168 169 /** Notify the node (and children) of a height delta value. */ 170 void notifyDelta(uint16 x, uint16 y, uint16 lod, Real delta); 171 172 /** Notify the node (and children) that deltas have finished being calculated. 173 */ 174 void postDeltaCalculation(const Rect& rect); 175 176 /** Promote the delta values calculated to the runtime ones (this must 177 be called in the main thread). 178 */ 179 void finaliseDeltaValues(const Rect& rect); 180 181 /** Assign vertex data to the tree, from a depth and at a given resolution. 182 @param treeDepthStart The first depth of tree that should use this data, owns the data 183 @param treeDepthEnd The end of the depth that should use this data (exclusive) 184 @param resolution The resolution of the data to use (compared to full terrain) 185 @param sz The size of the data along one edge 186 */ 187 void assignVertexData(uint16 treeDepthStart, uint16 treeDepthEnd, uint16 resolution, uint sz); 188 189 /** Tell a node that it should use an anscestor's vertex data. 190 @param treeDepthEnd The end of the depth that should use this data (exclusive) 191 @param resolution The resolution of the data to use 192 */ 193 void useAncestorVertexData(TerrainQuadTreeNode* owner, uint16 treeDepthEnd, uint16 resolution); 194 195 /** Tell the node to update its vertex data for a given region. 196 */ 197 void updateVertexData(bool positions, bool deltas, const Rect& rect, bool cpuData); 198 199 200 201 /** Merge a point (relative to terrain node) into the local bounds, 202 and that of children if applicable. 203 @param x,y The point on the terrain to which this position corresponds 204 (affects which nodes update their bounds) 205 @param pos The position relative to the terrain centre 206 */ 207 void mergeIntoBounds(long x, long y, const Vector3& pos); 208 /** Reset the bounds of this node and all its children for the region given. 209 @param rect The region for which bounds should be reset, in top-level terrain coords 210 */ 211 void resetBounds(const Rect& rect); 212 213 /** Returns true if the given rectangle overlaps the terrain area that 214 this node references. 215 @param rect The region in top-level terrain coords 216 */ 217 bool rectIntersectsNode(const Rect& rect); 218 /** Returns true if the given rectangle completely contains the terrain area that 219 this node references. 220 @param rect The region in top-level terrain coords 221 */ 222 bool rectContainsNode(const Rect& rect); 223 /** Returns true if the given point is in the terrain area that 224 this node references. 225 @param x,y The point in top-level terrain coords 226 */ 227 bool pointIntersectsNode(long x, long y); 228 229 /// Get the AABB (local coords) of this node 230 const AxisAlignedBox& getAABB() const; 231 /// Get the bounding radius of this node 232 Real getBoundingRadius() const; 233 /// Get the local centre of this node, relative to parent terrain centre getLocalCentre()234 const Vector3& getLocalCentre() const { return mLocalCentre; } 235 /// Get the minimum height of the node 236 Real getMinHeight() const; 237 /// Get the maximum height of the node 238 Real getMaxHeight() const; 239 240 /** Calculate appropriate LOD for this node and children 241 @param cam The camera to be used (this should already be the LOD camera) 242 @param cFactor The cFactor which incorporates the viewport size, max pixel error and lod bias 243 @return true if this node or any of its children were selected for rendering 244 */ 245 bool calculateCurrentLod(const Camera* cam, Real cFactor); 246 247 /// Get the current LOD index (only valid after calculateCurrentLod) getCurrentLod()248 int getCurrentLod() const { return mCurrentLod; } 249 /// Returns whether this node is rendering itself at the current LOD level 250 bool isRenderedAtCurrentLod() const; 251 /// Returns whether this node or its children are being rendered at the current LOD level 252 bool isSelfOrChildRenderedAtCurrentLod() const; 253 /// Manually set the current LOD, intended for internal use only 254 void setCurrentLod(int lod); 255 /// Get the transition state between the current LOD and the next lower one (only valid after calculateCurrentLod) getLodTransition()256 float getLodTransition() const { return mLodTransition; } 257 /// Manually set the current LOD transition state, intended for internal use only 258 void setLodTransition(float t); 259 260 /// Buffer binding used for holding positions 261 static unsigned short POSITION_BUFFER; 262 /// Buffer binding used for holding delta values 263 static unsigned short DELTA_BUFFER; 264 265 /// Returns the internal renderable object for this node 266 Renderable *_getRenderable(); 267 protected: 268 Terrain* mTerrain; 269 TerrainQuadTreeNode* mParent; 270 TerrainQuadTreeNode* mChildren[4]; 271 LodLevelList mLodLevels; 272 273 uint16 mOffsetX, mOffsetY; 274 uint16 mBoundaryX, mBoundaryY; 275 /// The number of vertices at the original terrain resolution this node encompasses 276 uint16 mSize; 277 uint16 mBaseLod; 278 uint16 mDepth; 279 uint16 mQuadrant; 280 Vector3 mLocalCentre; /// Relative to terrain centre 281 AxisAlignedBox mAABB; /// Relative to mLocalCentre 282 Real mBoundingRadius; /// Relative to mLocalCentre 283 int mCurrentLod; /// -1 = none (do not render) 284 unsigned short mMaterialLodIndex; 285 float mLodTransition; /// 0-1 transition to lower LOD 286 /// The child with the largest height delta 287 TerrainQuadTreeNode* mChildWithMaxHeightDelta; 288 bool mSelfOrChildRendered; 289 290 struct VertexDataRecord : public TerrainAlloc 291 { 292 VertexData* cpuVertexData; 293 VertexData* gpuVertexData; 294 /// Resolution of the data compared to the base terrain data (NOT number of vertices!) 295 uint16 resolution; 296 /// Size of the data along one edge 297 uint16 size; 298 /// Number of quadtree levels (including this one) this data applies to 299 uint16 treeLevels; 300 /// Number of rows and columns of skirts 301 uint16 numSkirtRowsCols; 302 /// The number of rows / cols to skip in between skirts 303 uint16 skirtRowColSkip; 304 /// Is the GPU vertex data out of date? 305 bool gpuVertexDataDirty; 306 VertexDataRecordVertexDataRecord307 VertexDataRecord(uint16 res, uint16 sz, uint16 lvls) 308 : cpuVertexData(0), gpuVertexData(0), resolution(res), size(sz), 309 treeLevels(lvls), numSkirtRowsCols(0), 310 skirtRowColSkip(0), gpuVertexDataDirty(false) {} 311 }; 312 313 TerrainQuadTreeNode* mNodeWithVertexData; 314 VertexDataRecord* mVertexDataRecord; 315 316 /** MovableObject implementation to provide the hook to the scene. 317 @remarks 318 In one sense, it would be most convenient to have a single MovableObject 319 to represent the whole Terrain object, and then internally perform 320 some quadtree frustum culling to narrow down which specific tiles are rendered. 321 However, the one major flaw with that is that exposing the bounds to 322 the SceneManager at that level prevents it from doing anything smarter 323 in terms of culling - for example a portal or occlusion culling SceneManager 324 would have no opportunity to process the leaf nodes in those terms, and 325 a simple frustum cull may give significantly poorer results. 326 @par 327 Therefore, we in fact register a MovableObject at every node, and 328 use the LOD factor to determine which one is currently active. LODs 329 must be mutually exclusive and to deal with precision errors, we really 330 need to evaluate them all at once, rather than as part of the 331 _notifyCurrentCamera function. Therefore the root Terrain registers 332 a SceneManager::Listener to precalculate which nodes will be displayed 333 when it comes to purely a LOD basis. 334 */ 335 class _OgreTerrainExport Movable : public MovableObject 336 { 337 protected: 338 TerrainQuadTreeNode* mParent; 339 public: 340 Movable(TerrainQuadTreeNode* parent); 341 virtual ~Movable(); 342 343 // necessary overrides 344 const String& getMovableType(void) const; 345 const AxisAlignedBox& getBoundingBox(void) const; 346 Real getBoundingRadius(void) const; 347 void _updateRenderQueue(RenderQueue* queue); 348 void visitRenderables(Renderable::Visitor* visitor, bool debugRenderables = false); 349 bool isVisible(void) const; 350 uint32 getVisibilityFlags(void) const; 351 uint32 getQueryFlags(void) const; 352 bool getCastShadows(void) const; 353 354 }; 355 Movable* mMovable; 356 friend class Movable; 357 SceneNode* mLocalNode; 358 359 /// Hook to the render queue 360 class _OgreTerrainExport Rend : public Renderable, public TerrainAlloc 361 { 362 protected: 363 TerrainQuadTreeNode* mParent; 364 public: 365 Rend(TerrainQuadTreeNode* parent); 366 virtual ~Rend(); 367 368 const MaterialPtr& getMaterial(void) const; 369 Technique* getTechnique(void) const; 370 void getRenderOperation(RenderOperation& op); 371 void getWorldTransforms(Matrix4* xform) const; 372 Real getSquaredViewDepth(const Camera* cam) const; 373 const LightList& getLights(void) const; 374 bool getCastsShadows(void) const; 375 376 }; 377 Rend* mRend; 378 friend class Rend; 379 380 // actual implementation of MovableObject methods 381 void updateRenderQueue(RenderQueue* queue); 382 void visitRenderables(Renderable::Visitor* visitor, bool debugRenderables = false); 383 // actual implementations of Renderable methods 384 const MaterialPtr& getMaterial(void) const; 385 Technique* getTechnique(void) const; 386 void getRenderOperation(RenderOperation& op); 387 void getWorldTransforms(Matrix4* xform) const; 388 Real getSquaredViewDepth(const Camera* cam) const; 389 const LightList& getLights(void) const; 390 bool getCastsShadows(void) const; 391 392 393 const VertexDataRecord* getVertexDataRecord() const; 394 void createCpuVertexData(); 395 /* Update the vertex buffers - the rect in question is relative to the whole terrain, 396 not the local vertex data (which may use a subset) 397 */ 398 void updateVertexBuffer(HardwareVertexBufferSharedPtr& posbuf, HardwareVertexBufferSharedPtr& deltabuf, const Rect& rect); 399 void destroyCpuVertexData(); 400 401 void createGpuVertexData(); 402 void destroyGpuVertexData(); 403 void updateGpuVertexData(); 404 void createGpuIndexData(); 405 void destroyGpuIndexData(); 406 407 void populateIndexData(uint16 batchSize, IndexData* destData); 408 void writePosVertex(bool compress, uint16 x, uint16 y, float height, const Vector3& pos, float uvScale, float** ppPos); 409 void writeDeltaVertex(bool compress, uint16 x, uint16 y, float delta, float deltaThresh, float** ppDelta); 410 411 uint16 calcSkirtVertexIndex(uint16 mainIndex, bool isCol); 412 413 }; 414 415 /** @} */ 416 /** @} */ 417 } 418 419 #endif 420