Stellarium 0.12.3
StelSphericalIndexMultiRes.hpp
1 /*
2  * Stellarium
3  * Copyright (C) 2009 Fabien Chereau
4  *
5  * This program is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU General Public License
7  * as published by the Free Software Foundation; either version 2
8  * of the License, or (at your option) any later version.
9  *
10  * This program is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13  * GNU General Public License for more details.
14  *
15  * You should have received a copy of the GNU General Public License
16  * along with this program; if not, write to the Free Software
17  * Foundation, Inc., 51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA.
18  */
19 
20 #ifndef _STELSPHERICALINDEXMULTIRES_HPP_
21 #define _STELSPHERICALINDEXMULTIRES_HPP_
22 
23 #define MAX_INDEX_LEVEL 8
24 
25 #include "StelRegionObject.hpp"
26 #include "StelSphericalIndex.hpp"
27 
31 {
32 public:
33  StelSphericalIndexMultiRes(int maxObjectsPerNode = 100);
34  virtual ~StelSphericalIndexMultiRes();
35 
37  void insert(StelRegionObjectP obj);
38 
40  template<class FuncObject> void processIntersectingRegions(const SphericalRegionP& region, FuncObject& func) const
41  {
42  for (int i=1;i<MAX_INDEX_LEVEL;++i)
43  {
44  const RootNode* node = treeForRadius[i-1];
45  if (node!=NULL)
46  node->processIntersectingRegions(region, func);
47  }
48  }
49 
51  template<class FuncObject> void processAll(FuncObject& func) const
52  {
53  for (int i=1;i<MAX_INDEX_LEVEL;++i)
54  {
55  const RootNode* node = treeForRadius[i-1];
56  if (node!=NULL)
57  node->processAll(func);
58  }
59  }
60 
61 private:
62 
64  struct NodeElem
65  {
66  NodeElem() {;}
67  NodeElem(StelRegionObjectP aobj) : obj(aobj), cap(obj->getRegion()->getBoundingCap()) {;}
68  StelRegionObjectP obj;
69  SphericalCap cap;
70  };
71 
75  struct Node
76  {
77  QVector<NodeElem> elements;
78  QVector<Node> children;
79  SphericalConvexPolygon triangle;
81  virtual void split()
82  {
83  // Default implementation for HTM triangle more than level 0
84  Q_ASSERT(children.empty());
85  Q_ASSERT(triangle.getConvexContour().size() == 3);
86 
87  const Vec3d& c0 = triangle.getConvexContour().at(0);
88  const Vec3d& c1 = triangle.getConvexContour().at(1);
89  const Vec3d& c2 = triangle.getConvexContour().at(2);
90 
91  Q_ASSERT((c1^c0)*c2 >= 0.0);
92  Vec3d e0(c1[0]+c2[0], c1[1]+c2[1], c1[2]+c2[2]);
93  e0.normalize();
94  Vec3d e1(c2[0]+c0[0], c2[1]+c0[1], c2[2]+c0[2]);
95  e1.normalize();
96  Vec3d e2(c0[0]+c1[0], c0[1]+c1[1], c0[2]+c1[2]);
97  e2.normalize();
98 
99  children.resize(4);
100  children[0].triangle = SphericalConvexPolygon(e1,c0,e2);
101  Q_ASSERT(children[0].triangle.checkValid());
102  children[1].triangle = SphericalConvexPolygon(e0,e2,c1);
103  Q_ASSERT(children[1].triangle.checkValid());
104  children[2].triangle = SphericalConvexPolygon(c2,e1,e0);
105  Q_ASSERT(children[2].triangle.checkValid());
106  children[3].triangle = SphericalConvexPolygon(e2,e0,e1);
107  Q_ASSERT(children[3].triangle.checkValid());
108  }
109  };
110 
113  class RootNode : public Node
114  {
115  public:
116  RootNode(double amargin, int amaxObjectsPerNode, int amaxLevel) : maxObjectsPerNode(amaxObjectsPerNode), maxLevel(amaxLevel), margin(amargin)
117  {
118  }
119 
121  virtual void split()
122  {
123  static const Vec3d vertice[6] =
124  {
125  Vec3d(0,0,1), Vec3d(1,0,0), Vec3d(0,1,0), Vec3d(-1,0,0), Vec3d(0,-1,0), Vec3d(0,0,-1)
126  };
127 
128  static const int verticeIndice[8][3] =
129  {
130  {0,2,1}, {0,1,4}, {0,4,3}, {0,3,2}, {5,1,2}, {5,4,1}, {5,3,4}, {5,2,3}
131  };
132 
133  // Create the 8 base triangles
134  Node node;
135  for (int i=0;i<8;++i)
136  {
137  node.triangle = SphericalConvexPolygon(vertice[verticeIndice[i][0]], vertice[verticeIndice[i][1]], vertice[verticeIndice[i][2]]);
138  Q_ASSERT(node.triangle.checkValid());
139  children.append(node);
140  }
141  }
142 
144  void insert(const NodeElem& el, int level)
145  {
146  insert(*this, el, level);
147  }
148 
150  template<class FuncObject> void processIntersectingRegions(const SphericalRegionP& region, FuncObject& func) const
151  {
152  processIntersectingRegions(*this, region->getEnlarged(margin), func);
153  }
154 
156  template<class FuncObject> void processAll(FuncObject& func) const
157  {
158  processAll(*this, func);
159  }
160 
161  private:
163  void insert(Node& node, const NodeElem& el, int level)
164  {
165  if (node.children.isEmpty())
166  {
167  node.elements.append(el);
168  // If we have too many objects in the node, we split it
169  if (level>=maxLevel && node.elements.size() >= maxObjectsPerNode)
170  {
171  node.split();
172  const QVector<NodeElem> nodeElems = node.elements;
173  for (QVector<NodeElem>::ConstIterator iter = nodeElems.begin();iter != nodeElems.end(); ++iter)
174  {
175  insert(node, *iter, level+1);
176  }
177  node.elements.clear();
178  }
179  }
180  else
181  {
182  // If we have children, store it in a sub-level
183  for (QVector<Node>::iterator iter = node.children.begin(); iter!=node.children.end(); ++iter)
184  {
185  if (iter->triangle.contains(el.cap.n))
186  {
187  insert(*iter, el, level+1);
188  return;
189  }
190  }
191  }
192  }
193 
195  template<class FuncObject> void processIntersectingRegions(const Node& node, const SphericalRegionP& region, FuncObject& func) const
196  {
197  foreach (const NodeElem& el, node.elements)
198  {
199  if (region->intersects(el.obj->getRegion()))
200  func(el.obj);
201  }
202  foreach (const Node& child, node.children)
203  {
204  if (region->contains(node.triangle))
205  processAll(child, func);
206  else if (region->intersects(node.triangle))
207  processIntersectingRegions(child, region, func);
208  }
209  }
210 
212  template<class FuncObject> void processAll(const Node& node, FuncObject& func) const
213  {
214  foreach (const NodeElem& el, node.elements)
215  func(el.obj);
216  foreach (const Node& child, node.children)
217  processAll(child, func);
218  }
219 
221  int maxObjectsPerNode;
223  int maxLevel;
225  double margin;
226  };
227 
229  int maxObjectsPerNode;
230 
232  RootNode* treeForRadius[MAX_INDEX_LEVEL];
233 
234  double cosRadius[MAX_INDEX_LEVEL];
235 };
236 
237 #endif // _STELSPHERICALINDEXMULTIRES_HPP_
238 
239