00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020 #ifndef _STELSPHERICALINDEXMULTIRES_HPP_
00021 #define _STELSPHERICALINDEXMULTIRES_HPP_
00022
00023 #define MAX_INDEX_LEVEL 8
00024
00025 #include "StelRegionObject.hpp"
00026
00029 class StelSphericalIndexMultiRes : public StelSphericalIndex
00030 {
00031 public:
00032 StelSphericalIndexMultiRes(int maxObjectsPerNode = 100);
00033 virtual ~StelSphericalIndexMultiRes();
00034
00036 void insert(StelRegionObjectP obj);
00037
00039 template<class FuncObject> void processIntersectingRegions(const SphericalRegionP& region, FuncObject& func) const
00040 {
00041 for (int i=1;i<MAX_INDEX_LEVEL;++i)
00042 {
00043 const RootNode* node = treeForRadius[i-1];
00044 if (node!=NULL)
00045 node->processIntersectingRegions(region, func);
00046 }
00047 }
00048
00050 template<class FuncObject> void processAll(FuncObject& func) const
00051 {
00052 for (int i=1;i<MAX_INDEX_LEVEL;++i)
00053 {
00054 const RootNode* node = treeForRadius[i-1];
00055 if (node!=NULL)
00056 node->processAll(func);
00057 }
00058 }
00059
00060 private:
00061
00063 struct NodeElem
00064 {
00065 NodeElem() {;}
00066 NodeElem(StelRegionObjectP aobj) : obj(aobj), cap(obj->getRegion()->getBoundingCap()) {;}
00067 StelRegionObjectP obj;
00068 SphericalCap cap;
00069 };
00070
00074 struct Node
00075 {
00076 QVector<NodeElem> elements;
00077 QVector<Node> children;
00078 SphericalConvexPolygon triangle;
00080 virtual void split()
00081 {
00082
00083 Q_ASSERT(children.empty());
00084 Q_ASSERT(triangle.getConvexContour().size() == 3);
00085
00086 const Vec3d& c0 = triangle.getConvexContour().at(0);
00087 const Vec3d& c1 = triangle.getConvexContour().at(1);
00088 const Vec3d& c2 = triangle.getConvexContour().at(2);
00089
00090 Q_ASSERT((c1^c0)*c2 >= 0.0);
00091 Vec3d e0(c1[0]+c2[0], c1[1]+c2[1], c1[2]+c2[2]);
00092 e0.normalize();
00093 Vec3d e1(c2[0]+c0[0], c2[1]+c0[1], c2[2]+c0[2]);
00094 e1.normalize();
00095 Vec3d e2(c0[0]+c1[0], c0[1]+c1[1], c0[2]+c1[2]);
00096 e2.normalize();
00097
00098 children.resize(4);
00099 children[0].triangle = SphericalConvexPolygon(e1,c0,e2);
00100 Q_ASSERT(children[0].triangle.checkValid());
00101 children[1].triangle = SphericalConvexPolygon(e0,e2,c1);
00102 Q_ASSERT(children[1].triangle.checkValid());
00103 children[2].triangle = SphericalConvexPolygon(c2,e1,e0);
00104 Q_ASSERT(children[2].triangle.checkValid());
00105 children[3].triangle = SphericalConvexPolygon(e2,e0,e1);
00106 Q_ASSERT(children[3].triangle.checkValid());
00107 }
00108 };
00109
00112 class RootNode : public Node
00113 {
00114 public:
00115 RootNode(double amargin, int amaxObjectsPerNode, int amaxLevel) : maxObjectsPerNode(), maxLevel(amaxLevel), margin(amargin)
00116 {
00117 }
00118
00120 virtual void split()
00121 {
00122 static const Vec3d vertice[6] =
00123 {
00124 Vec3d(0,0,1), Vec3d(1,0,0), Vec3d(0,1,0), Vec3d(-1,0,0), Vec3d(0,-1,0), Vec3d(0,0,-1)
00125 };
00126
00127 static const int verticeIndice[8][3] =
00128 {
00129 {0,2,1}, {0,1,4}, {0,4,3}, {0,3,2}, {5,1,2}, {5,4,1}, {5,3,4}, {5,2,3}
00130 };
00131
00132
00133 Node node;
00134 for (int i=0;i<8;++i)
00135 {
00136 node.triangle = SphericalConvexPolygon(vertice[verticeIndice[i][0]], vertice[verticeIndice[i][1]], vertice[verticeIndice[i][2]]);
00137 Q_ASSERT(node.triangle.checkValid());
00138 children.append(node);
00139 }
00140 }
00141
00143 void insert(const NodeElem& el, int level)
00144 {
00145 insert(*this, el, level);
00146 }
00147
00149 template<class FuncObject> void processIntersectingRegions(const SphericalRegionP& region, FuncObject& func) const
00150 {
00151 processIntersectingRegions(*this, region->getEnlarged(margin), func);
00152 }
00153
00155 template<class FuncObject> void processAll(FuncObject& func) const
00156 {
00157 processAll(*this, func);
00158 }
00159
00160 private:
00162 void insert(Node& node, const NodeElem& el, int level)
00163 {
00164 if (node.children.isEmpty())
00165 {
00166 node.elements.append(el);
00167
00168 if (level>=maxLevel && node.elements.size() >= maxObjectsPerNode)
00169 {
00170 node.split();
00171 const QVector<NodeElem> nodeElems = node.elements;
00172 for (QVector<NodeElem>::ConstIterator iter = nodeElems.begin();iter != nodeElems.end(); ++iter)
00173 {
00174 insert(node, *iter, level+1);
00175 }
00176 node.elements.clear();
00177 }
00178 }
00179 else
00180 {
00181
00182 for (QVector<Node>::iterator iter = node.children.begin(); iter!=node.children.end(); ++iter)
00183 {
00184 if (iter->triangle.contains(el.cap.n))
00185 {
00186 insert(*iter, el, level+1);
00187 return;
00188 }
00189 }
00190 }
00191 }
00192
00194 template<class FuncObject> void processIntersectingRegions(const Node& node, const SphericalRegionP& region, FuncObject& func) const
00195 {
00196 foreach (const NodeElem& el, node.elements)
00197 {
00198 if (region->intersects(el.obj->getRegion()))
00199 func(el.obj);
00200 }
00201 foreach (const Node& child, node.children)
00202 {
00203 if (region->contains(node.triangle))
00204 processAll(child, func);
00205 else if (region->intersects(node.triangle))
00206 processIntersectingRegions(child, region, func);
00207 }
00208 }
00209
00211 template<class FuncObject> void processAll(const Node& node, FuncObject& func) const
00212 {
00213 foreach (const NodeElem& el, node.elements)
00214 func(el.obj);
00215 foreach (const Node& child, node.children)
00216 processAll(child, func);
00217 }
00218
00220 int maxObjectsPerNode;
00222 int maxLevel;
00224 double margin;
00225 };
00226
00228 int maxObjectsPerNode;
00229
00231 RootNode* treeForRadius[MAX_INDEX_LEVEL];
00232
00233 double cosRadius[MAX_INDEX_LEVEL];
00234 };
00235
00236 #endif // _STELSPHERICALINDEXMULTIRES_HPP_
00237
00238