00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020 #ifndef _STELSPHERICALINDEX_HPP_
00021 #define _STELSPHERICALINDEX_HPP_
00022
00023 #include "StelRegionObject.hpp"
00024
00027 class StelSphericalIndex
00028 {
00029 public:
00030 StelSphericalIndex(int maxObjectsPerNode = 100, int maxLevel=7);
00031 virtual ~StelSphericalIndex();
00032
00034 void insert(StelRegionObjectP obj);
00035
00037 template<class FuncObject> void processIntersectingRegions(const SphericalRegionP& region, FuncObject& func) const
00038 {
00039 rootNode->processIntersectingRegions(region, func);
00040 }
00041
00043 template<class FuncObject> void processContainedRegions(const SphericalRegionP& region, FuncObject& func) const
00044 {
00045 rootNode->processContainedRegions(region, func);
00046 }
00047
00049 template<class FuncObject> void processAll(FuncObject& func) const
00050 {
00051 rootNode->processAll(func);
00052 }
00053
00054 void clear()
00055 {
00056 rootNode->clear();
00057 }
00058
00059 private:
00060
00062 struct NodeElem
00063 {
00064 NodeElem() {;}
00065 NodeElem(StelRegionObjectP aobj) : obj(aobj), cap(obj->getRegion()->getBoundingCap()) {;}
00066 StelRegionObjectP obj;
00067 SphericalCap cap;
00068 };
00069
00073 struct Node
00074 {
00075 virtual ~Node() {;}
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
00110 void clear()
00111 {
00112 elements.clear();
00113 children.clear();
00114 }
00115 };
00116
00119 class RootNode : public Node
00120 {
00121 public:
00122 RootNode(int amaxObjectsPerNode, int amaxLevel) : maxObjectsPerNode(amaxObjectsPerNode), maxLevel(amaxLevel)
00123 {
00124 }
00125
00127 virtual void split()
00128 {
00129 static const Vec3d vertice[6] =
00130 {
00131 Vec3d(0,0,1), Vec3d(1,0,0), Vec3d(0,1,0), Vec3d(-1,0,0), Vec3d(0,-1,0), Vec3d(0,0,-1)
00132 };
00133
00134 static const int verticeIndice[8][3] =
00135 {
00136 {0,2,1}, {0,1,4}, {0,4,3}, {0,3,2}, {5,1,2}, {5,4,1}, {5,3,4}, {5,2,3}
00137 };
00138
00139
00140 Node node;
00141 for (int i=0;i<8;++i)
00142 {
00143 node.triangle = SphericalConvexPolygon(vertice[verticeIndice[i][0]], vertice[verticeIndice[i][1]], vertice[verticeIndice[i][2]]);
00144 Q_ASSERT(node.triangle.checkValid());
00145 children.append(node);
00146 }
00147 }
00148
00150 void insert(const NodeElem& el, int level)
00151 {
00152 insert(*this, el, level);
00153 }
00154
00156 template<class FuncObject> void processIntersectingRegions(const SphericalRegionP& region, FuncObject& func) const
00157 {
00158 processIntersectingRegions(*this, region, func);
00159 }
00160
00162 template<class FuncObject> void processContainedRegions(const SphericalRegionP& region, FuncObject& func) const
00163 {
00164 processContainedRegions(*this, region, func);
00165 }
00166
00168 template<class FuncObject> void processAll(FuncObject& func) const
00169 {
00170 processAll(*this, func);
00171 }
00172
00173 private:
00175 void insert(Node& node, const NodeElem& el, int level)
00176 {
00177 if (node.children.isEmpty())
00178 {
00179 node.elements.append(el);
00180
00181 if (level<maxLevel && node.elements.size() > maxObjectsPerNode)
00182 {
00183 node.split();
00184 const QVector<NodeElem> nodeElems = node.elements;
00185 node.elements.clear();
00186
00187 for (QVector<NodeElem>::ConstIterator iter = nodeElems.begin();iter != nodeElems.end(); ++iter)
00188 {
00189 insert(node, *iter, level);
00190 }
00191 }
00192 return;
00193 }
00194
00195
00196 for (QVector<Node>::iterator iter = node.children.begin(); iter!=node.children.end(); ++iter)
00197 {
00198 if (((SphericalRegion*)&(iter->triangle))->contains(el.obj->getRegion().data()))
00199 {
00200 insert(*iter, el, level+1);
00201 return;
00202 }
00203 }
00204
00205 node.elements.append(el);
00206 }
00207
00209 template<class FuncObject> void processIntersectingRegions(const Node& node, const SphericalRegionP& region, FuncObject& func) const
00210 {
00211 foreach (const NodeElem& el, node.elements)
00212 {
00213 if (region->intersects(el.obj->getRegion().data()))
00214 func(el.obj);
00215 }
00216 foreach (const Node& child, node.children)
00217 {
00218 if (region->contains(child.triangle))
00219 processAll(child, func);
00220 else if (region->intersects(child.triangle))
00221 processIntersectingRegions(child, region, func);
00222 }
00223 }
00224
00226 template<class FuncObject> void processContainedRegions(const Node& node, const SphericalRegionP& region, FuncObject& func) const
00227 {
00228 foreach (const NodeElem& el, node.elements)
00229 {
00230 if (region->contains(el.obj->getRegion().data()))
00231 func(el.obj);
00232 }
00233 foreach (const Node& child, node.children)
00234 {
00235 if (region->contains(child.triangle))
00236 processAll(child, func);
00237 else if (region->intersects(child.triangle))
00238 processContainedRegions(child, region, func);
00239 }
00240 }
00241
00243 template<class FuncObject> void processAll(const Node& node, FuncObject& func) const
00244 {
00245 foreach (const NodeElem& el, node.elements)
00246 func(el.obj);
00247 foreach (const Node& child, node.children)
00248 processAll(child, func);
00249 }
00250
00252 int maxObjectsPerNode;
00254 int maxLevel;
00255 };
00256
00258 int maxObjectsPerNode;
00259
00260 RootNode* rootNode;
00261 };
00262
00263 #endif // _STELSPHERICALINDEX_HPP_
00264
00265