1/* -*-c++-*- */ 2/* osgEarth - Geospatial SDK for OpenSceneGraph 3* Copyright 2019 Pelican Mapping 4* http://osgearth.org 5* 6* osgEarth is free software; you can redistribute it and/or modify 7* it under the terms of the GNU Lesser General Public License as published by 8* the Free Software Foundation; either version 2 of the License, or 9* (at your option) any later version. 10* 11* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 12* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 13* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 14* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 15* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 16* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS 17* IN THE SOFTWARE. 18* 19* You should have received a copy of the GNU Lesser General Public License 20* along with this program. If not, see <http://www.gnu.org/licenses/> 21*/ 22 23#ifndef OSGEARTH_UTIL_HTM_H 24#define OSGEARTH_UTIL_HTM_H 1 25 26#include <osgEarthUtil/Common> 27#include <osg/Geode> 28#include <osg/Group> 29#include <osg/Polytope> 30#include <vector> 31#include <osgEarth/optional> 32 33namespace osgEarth { namespace Util 34{ 35 using namespace osgEarth; 36 37 struct HTMSettings 38 { 39 unsigned _maxObjectsPerCell; 40 optional<float> _rangeFactor; 41 optional<float> _maxRange; 42 float _minCellSize; 43 float _maxCellSize; 44 bool _storeObjectsInLeavesOnly; 45 int _debugCount; 46 int _debugFrame; 47 bool _debugGeom; 48 }; 49 50 /** 51 * Hierarchical Triangular Mesh group - for geocentric maps only 52 * http://www.geog.ucsb.edu/~hu/papers/spatialIndex.pdf 53 * 54 * An osg::Group that automatically organizes its contents spatially 55 * in order to improve culling performance. 56 */ 57 class OSGEARTHUTIL_EXPORT HTMGroup : public osg::Group 58 { 59 public: 60 HTMGroup(); 61 62 //! Sets the maximum number of objects that can live in a single cell. 63 void setMaximumObjectsPerCell(unsigned value) { _settings._maxObjectsPerCell = value; } 64 float getMaximumObjectsPerCell() const { return _settings._maxObjectsPerCell; } 65 66 //! Minimum size (bounding radius*2) of an HTM cell. 67 void setMinimumCellSize(double value) { _settings._minCellSize = value; } 68 double getMinimumCellSize() const { return _settings._minCellSize; } 69 70 //! Maximum size (bounding radius*2) of an HTM cell that can contain objects. 71 void setMaximumCellSize(double value) { _settings._maxCellSize = value; } 72 double getMaximumCellSize() const { return _settings._maxCellSize; } 73 74 //! Cells become visible at (cell bounding radius * range factor). 75 //! If this is set, the value in setRange is ignored. 76 void setRangeFactor(float value) { _settings._rangeFactor = value; } 77 78 //! Range at which objects become visible. This overrides range factor if set. 79 void setMaxRange(float value) { _settings._maxRange = value; } 80 81 //! If true, only store objects in the leaf nodes (defaults to false) 82 void setStoreObjectsInLeavesOnly(bool value) { _settings._storeObjectsInLeavesOnly = value; } 83 84 //! Enable debugging geometry 85 void setDebug(bool value) { _settings._debugGeom = value; } 86 bool getDebug() const { return _settings._debugGeom; } 87 88 public: // osg::Group 89 90 /** Add a node to the group. */ 91 virtual bool addChild(osg::Node* child); 92 93 /** Add a node to the group. Ignores the "index". */ 94 virtual bool insertChild(unsigned index, osg::Node* child); 95 96 97 public: // osg::Group (internal) 98 99 /** These methods are derived from Group but are NOOPs for the HTMGroup. */ 100 virtual bool removeChildren(unsigned pos, unsigned numChildrenToRemove); 101 virtual bool replaceChild(osg::Node* origChild, osg::Node* newChild); 102 virtual bool setChild(unsigned index, osg::Node* node); 103 104 protected: 105 virtual ~HTMGroup() { } 106 107 bool insert(osg::Node* node); 108 109 void reinitialize(); 110 111 HTMSettings _settings; 112 }; 113 114 115 /** 116 * Internal index cell for the HTMGroup (do not use directly). 117 */ 118 class HTMNode : public osg::Group 119 { 120 public: 121 HTMNode(HTMSettings& settings, 122 const osg::Vec3d& v0, const osg::Vec3d& v1, const osg::Vec3d& v2, 123 const std::string& id = ""); 124 125 bool contains(const osg::Vec3d& p) const { 126 return _tri.contains(p); 127 } 128 129 void insert(osg::Node* node); 130 131 public: 132 void traverse(osg::NodeVisitor& nv); 133 134 protected: 135 virtual ~HTMNode() { } 136 137 void split(); 138 139 // test whether the node's triangle lies entirely within a frustum 140 bool entirelyWithin(const osg::Polytope& tope) const; 141 142 // test whether the node's triangle intersects a frustum 143 bool intersects(const osg::Polytope& tope) const; 144 145 private: 146 147 struct PolytopeDP : public osg::Polytope 148 { 149 bool contains(const osg::Vec3d& p) const; 150 bool containsAnyOf(const std::vector<osg::Vec3d>& p) const; 151 }; 152 153 struct Triangle 154 { 155 std::vector<osg::Vec3d> _v; 156 PolytopeDP _tope; 157 158 void set(const osg::Vec3d& v0, const osg::Vec3d& v1, const osg::Vec3d& v2); 159 160 void getMidpoints(osg::Vec3d* w) const; 161 162 bool contains(const osg::Vec3d& p) const { 163 return _tope.contains(p); 164 } 165 }; 166 167 168 Triangle _tri; 169 bool _isLeaf; 170 HTMSettings& _settings; 171 osg::ref_ptr<osg::Node> _debug; 172 }; 173 174} } // namesapce osgEarth::Util 175 176 177#endif // OSGEARTH_UTIL_HTM_H 178