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