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
00055 void clear()
00056 {
00057 rootNode->clear();
00058 }
00059
00061 unsigned int count()
00062 {
00063 CountFunc func;
00064 processAll<CountFunc>(func);
00065 return func.nb;
00066 }
00067
00068 private:
00069 struct CountFunc
00070 {
00071 CountFunc() : nb(0) {;}
00072 void operator()(const StelRegionObjectP&)
00073 {
00074 ++nb;
00075 }
00076 unsigned int nb;
00077 };
00078
00080 struct NodeElem
00081 {
00082 NodeElem() {;}
00083 NodeElem(StelRegionObjectP aobj) : obj(aobj), cap(obj->getRegion()->getBoundingCap()) {;}
00084 StelRegionObjectP obj;
00085 SphericalCap cap;
00086 };
00087
00091 struct Node
00092 {
00093 virtual ~Node() {;}
00094 QVector<NodeElem> elements;
00095 QVector<Node> children;
00096 SphericalConvexPolygon triangle;
00098 virtual void split()
00099 {
00100
00101 Q_ASSERT(children.empty());
00102 Q_ASSERT(triangle.getConvexContour().size() == 3);
00103
00104 const Vec3d& c0 = triangle.getConvexContour().at(0);
00105 const Vec3d& c1 = triangle.getConvexContour().at(1);
00106 const Vec3d& c2 = triangle.getConvexContour().at(2);
00107
00108 Q_ASSERT((c1^c0)*c2 >= 0.0);
00109 Vec3d e0(c1[0]+c2[0], c1[1]+c2[1], c1[2]+c2[2]);
00110 e0.normalize();
00111 Vec3d e1(c2[0]+c0[0], c2[1]+c0[1], c2[2]+c0[2]);
00112 e1.normalize();
00113 Vec3d e2(c0[0]+c1[0], c0[1]+c1[1], c0[2]+c1[2]);
00114 e2.normalize();
00115
00116 children.resize(4);
00117 children[0].triangle = SphericalConvexPolygon(e1,c0,e2);
00118 Q_ASSERT(children[0].triangle.checkValid());
00119 children[1].triangle = SphericalConvexPolygon(e0,e2,c1);
00120 Q_ASSERT(children[1].triangle.checkValid());
00121 children[2].triangle = SphericalConvexPolygon(c2,e1,e0);
00122 Q_ASSERT(children[2].triangle.checkValid());
00123 children[3].triangle = SphericalConvexPolygon(e2,e0,e1);
00124 Q_ASSERT(children[3].triangle.checkValid());
00125 }
00126
00128 void clear()
00129 {
00130 elements.clear();
00131 children.clear();
00132 }
00133 };
00134
00137 class RootNode : public Node
00138 {
00139 public:
00140 RootNode(int amaxObjectsPerNode, int amaxLevel) : maxObjectsPerNode(amaxObjectsPerNode), maxLevel(amaxLevel)
00141 {
00142 }
00143
00145 virtual void split()
00146 {
00147 static const Vec3d vertice[6] =
00148 {
00149 Vec3d(0,0,1), Vec3d(1,0,0), Vec3d(0,1,0), Vec3d(-1,0,0), Vec3d(0,-1,0), Vec3d(0,0,-1)
00150 };
00151
00152 static const int verticeIndice[8][3] =
00153 {
00154 {0,2,1}, {0,1,4}, {0,4,3}, {0,3,2}, {5,1,2}, {5,4,1}, {5,3,4}, {5,2,3}
00155 };
00156
00157
00158 Node node;
00159 for (int i=0;i<8;++i)
00160 {
00161 node.triangle = SphericalConvexPolygon(vertice[verticeIndice[i][0]], vertice[verticeIndice[i][1]], vertice[verticeIndice[i][2]]);
00162 Q_ASSERT(node.triangle.checkValid());
00163 children.append(node);
00164 }
00165 }
00166
00168 void insert(const NodeElem& el, int level)
00169 {
00170 insert(*this, el, level);
00171 }
00172
00174 template<class FuncObject> void processIntersectingRegions(const SphericalRegionP& region, FuncObject& func) const
00175 {
00176 processIntersectingRegions(*this, region, func);
00177 }
00178
00180 template<class FuncObject> void processContainedRegions(const SphericalRegionP& region, FuncObject& func) const
00181 {
00182 processContainedRegions(*this, region, func);
00183 }
00184
00186 template<class FuncObject> void processAll(FuncObject& func) const
00187 {
00188 processAll(*this, func);
00189 }
00190
00191 private:
00193 void insert(Node& node, const NodeElem& el, int level)
00194 {
00195 if (node.children.isEmpty())
00196 {
00197 node.elements.append(el);
00198
00199 if (level<maxLevel && node.elements.size() > maxObjectsPerNode)
00200 {
00201 node.split();
00202 const QVector<NodeElem> nodeElems = node.elements;
00203 node.elements.clear();
00204
00205 for (QVector<NodeElem>::ConstIterator iter = nodeElems.constBegin();iter != nodeElems.constEnd(); ++iter)
00206 {
00207 insert(node, *iter, level);
00208 }
00209 }
00210 return;
00211 }
00212
00213
00214 for (QVector<Node>::iterator iter = node.children.begin(); iter!=node.children.end(); ++iter)
00215 {
00216 if (((SphericalRegion*)&(iter->triangle))->contains(el.obj->getRegion().data()))
00217 {
00218 insert(*iter, el, level+1);
00219 return;
00220 }
00221 }
00222
00223 node.elements.append(el);
00224 }
00225
00227 template<class FuncObject> void processIntersectingRegions(const Node& node, const SphericalRegionP& region, FuncObject& func) const
00228 {
00229 foreach (const NodeElem& el, node.elements)
00230 {
00231 if (region->intersects(el.obj->getRegion().data()))
00232 func(el.obj);
00233 }
00234 foreach (const Node& child, node.children)
00235 {
00236 if (region->contains(child.triangle))
00237 processAll(child, func);
00238 else if (region->intersects(child.triangle))
00239 processIntersectingRegions(child, region, func);
00240 }
00241 }
00242
00244 template<class FuncObject> void processContainedRegions(const Node& node, const SphericalRegionP& region, FuncObject& func) const
00245 {
00246 foreach (const NodeElem& el, node.elements)
00247 {
00248 if (region->contains(el.obj->getRegion().data()))
00249 func(el.obj);
00250 }
00251 foreach (const Node& child, node.children)
00252 {
00253 if (region->contains(child.triangle))
00254 processAll(child, func);
00255 else if (region->intersects(child.triangle))
00256 processContainedRegions(child, region, func);
00257 }
00258 }
00259
00261 template<class FuncObject> void processAll(const Node& node, FuncObject& func) const
00262 {
00263 foreach (const NodeElem& el, node.elements)
00264 func(el.obj);
00265 foreach (const Node& child, node.children)
00266 processAll(child, func);
00267 }
00268
00270 int maxObjectsPerNode;
00272 int maxLevel;
00273 };
00274
00276 int maxObjectsPerNode;
00277
00278 RootNode* rootNode;
00279 };
00280
00281 #endif // _STELSPHERICALINDEX_HPP_
00282
00283