Stellarium 0.12.3
StelSphericalIndex.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 _STELSPHERICALINDEX_HPP_
21 #define _STELSPHERICALINDEX_HPP_
22 
23 #include "StelRegionObject.hpp"
24 
28 {
29 public:
30  StelSphericalIndex(int maxObjectsPerNode = 100, int maxLevel=7);
31  virtual ~StelSphericalIndex();
32 
34  void insert(StelRegionObjectP obj);
35 
37  template<class FuncObject> void processIntersectingRegions(const SphericalRegionP& region, FuncObject& func) const
38  {
39  rootNode->processIntersectingRegions(region, func);
40  }
41 
43  template<class FuncObject> void processBoundingCapIntersectingRegions(const SphericalCap& cap, FuncObject& func) const
44  {
45  rootNode->processBoundingCapIntersectingRegions(cap, func);
46  }
47 
49  template<class FuncObject> void processContainedRegions(const SphericalRegionP& region, FuncObject& func) const
50  {
51  rootNode->processContainedRegions(region, func);
52  }
53 
55  template<class FuncObject> void processAll(FuncObject& func) const
56  {
57  rootNode->processAll(func);
58  }
59 
61  void clear()
62  {
63  rootNode->clear();
64  }
65 
67  unsigned int count()
68  {
69  CountFunc func;
70  processAll<CountFunc>(func);
71  return func.nb;
72  }
73 
74 private:
75  struct CountFunc
76  {
77  CountFunc() : nb(0) {;}
78  void operator()(const StelRegionObject*)
79  {
80  ++nb;
81  }
82  unsigned int nb;
83  };
84 
86  struct NodeElem
87  {
88  NodeElem() {;}
89  NodeElem(StelRegionObjectP aobj) : obj(aobj), cap(obj->getRegion()->getBoundingCap()) {;}
90  StelRegionObjectP obj;
91  SphericalCap cap;
92  };
93 
97  struct Node
98  {
99  virtual ~Node() {;}
100  QVector<NodeElem> elements;
101  QVector<Node> children;
102  SphericalConvexPolygon triangle;
104  virtual void split()
105  {
106  // Default implementation for HTM triangle more than level 0
107  Q_ASSERT(children.empty());
108  Q_ASSERT(triangle.getConvexContour().size() == 3);
109 
110  const Vec3d& c0 = triangle.getConvexContour().at(0);
111  const Vec3d& c1 = triangle.getConvexContour().at(1);
112  const Vec3d& c2 = triangle.getConvexContour().at(2);
113 
114  Q_ASSERT((c1^c0)*c2 >= 0.0);
115  Vec3d e0(c1[0]+c2[0], c1[1]+c2[1], c1[2]+c2[2]);
116  e0.normalize();
117  Vec3d e1(c2[0]+c0[0], c2[1]+c0[1], c2[2]+c0[2]);
118  e1.normalize();
119  Vec3d e2(c0[0]+c1[0], c0[1]+c1[1], c0[2]+c1[2]);
120  e2.normalize();
121 
122  children.resize(4);
123  children[0].triangle = SphericalConvexPolygon(e1,c0,e2);
124  Q_ASSERT(children[0].triangle.checkValid());
125  children[1].triangle = SphericalConvexPolygon(e0,e2,c1);
126  Q_ASSERT(children[1].triangle.checkValid());
127  children[2].triangle = SphericalConvexPolygon(c2,e1,e0);
128  Q_ASSERT(children[2].triangle.checkValid());
129  children[3].triangle = SphericalConvexPolygon(e2,e0,e1);
130  Q_ASSERT(children[3].triangle.checkValid());
131  }
132 
134  void clear()
135  {
136  elements.clear();
137  children.clear();
138  }
139  };
140 
143  class RootNode : public Node
144  {
145  public:
146  RootNode(int amaxObjectsPerNode, int amaxLevel) : maxObjectsPerNode(amaxObjectsPerNode), maxLevel(amaxLevel)
147  {
148  }
149 
151  virtual void split()
152  {
153  static const Vec3d vertice[6] =
154  {
155  Vec3d(0,0,1), Vec3d(1,0,0), Vec3d(0,1,0), Vec3d(-1,0,0), Vec3d(0,-1,0), Vec3d(0,0,-1)
156  };
157 
158  static const int verticeIndice[8][3] =
159  {
160  {0,2,1}, {0,1,4}, {0,4,3}, {0,3,2}, {5,1,2}, {5,4,1}, {5,3,4}, {5,2,3}
161  };
162 
163  // Create the 8 base triangles
164  Node node;
165  for (int i=0;i<8;++i)
166  {
167  node.triangle = SphericalConvexPolygon(vertice[verticeIndice[i][0]], vertice[verticeIndice[i][1]], vertice[verticeIndice[i][2]]);
168  Q_ASSERT(node.triangle.checkValid());
169  children.append(node);
170  }
171  }
172 
174  void insert(const NodeElem& el, int level)
175  {
176  insert(*this, el, level);
177  }
178 
180  template<class FuncObject> void processIntersectingRegions(const SphericalRegionP& region, FuncObject& func) const
181  {
182  processIntersectingRegions(*this, region, func);
183  }
184 
185  template<class FuncObject> void processBoundingCapIntersectingRegions(const SphericalCap& cap, FuncObject& func) const
186  {
187  processBoundingCapIntersectingRegions(*this, cap, func);
188  }
189 
191  template<class FuncObject> void processContainedRegions(const SphericalRegionP& region, FuncObject& func) const
192  {
193  processContainedRegions(*this, region, func);
194  }
195 
197  template<class FuncObject> void processAll(FuncObject& func) const
198  {
199  processAll(*this, func);
200  }
201 
202  private:
204  void insert(Node& node, const NodeElem& el, int level)
205  {
206  if (node.children.isEmpty())
207  {
208  node.elements.append(el);
209  // If we have too many objects in the node, we split it.
210  if (level<maxLevel && node.elements.size() > maxObjectsPerNode)
211  {
212  node.split();
213  const QVector<NodeElem> nodeElems = node.elements;
214  node.elements.clear();
215  // Re-insert the elements
216  for (QVector<NodeElem>::ConstIterator iter = nodeElems.constBegin();iter != nodeElems.constEnd(); ++iter)
217  {
218  insert(node, *iter, level);
219  }
220  }
221  return;
222  }
223 
224  // If we have children and one of them contains the element, store it in a sub-level
225  for (QVector<Node>::iterator iter = node.children.begin(); iter!=node.children.end(); ++iter)
226  {
227  if (((SphericalRegion*)&(iter->triangle))->contains(el.obj->getRegion().data()))
228  {
229  insert(*iter, el, level+1);
230  return;
231  }
232  }
233  // Else store it here
234  node.elements.append(el);
235  }
236 
238  template<class FuncObject> void processIntersectingRegions(const Node& node, const SphericalRegionP& region, FuncObject& func) const
239  {
240  foreach (const NodeElem& el, node.elements)
241  {
242  // Optimization: We pass a plain pointer here, not smart pointer.
243  // As long as the FuncObject does not need to store the pointer,
244  // this isn't a problem.
245  if (region->intersects(el.obj->getRegion().data()))
246  func(&(*el.obj));
247  }
248  foreach (const Node& child, node.children)
249  {
250  if (region->contains(child.triangle))
251  processAll(child, func);
252  else if (region->intersects(child.triangle))
253  processIntersectingRegions(child, region, func);
254  }
255  }
256 
257  template<class FuncObject> void processBoundingCapIntersectingRegions(const Node& node, const SphericalCap& cap, FuncObject& func) const
258  {
259  foreach (const NodeElem& el, node.elements)
260  {
261  // Optimization: We pass a plain pointer here, not smart pointer.
262  // As long as the FuncObject does not need to store the pointer,
263  // this isn't a problem.
264  if (cap.intersects(el.cap))
265  func(&(*el.obj));
266  }
267  foreach (const Node& child, node.children)
268  {
269  if (cap.contains(child.triangle))
270  processAll(child, func);
271  else if (cap.intersects(child.triangle))
272  processBoundingCapIntersectingRegions(child, cap, func);
273  }
274  }
275 
277  template<class FuncObject> void processContainedRegions(const Node& node, const SphericalRegionP& region, FuncObject& func) const
278  {
279  foreach (const NodeElem& el, node.elements)
280  {
281  // Optimization: We pass a plain pointer here, not smart pointer.
282  // As long as the FuncObject does not need to store the pointer,
283  // this isn't a problem.
284  if (region->contains(el.obj->getRegion().data()))
285  func(&(*el.obj));
286  }
287  foreach (const Node& child, node.children)
288  {
289  if (region->contains(child.triangle))
290  processAll(child, func);
291  else if (region->intersects(child.triangle))
292  processContainedRegions(child, region, func);
293  }
294  }
295 
297  template<class FuncObject> void processAll(const Node& node, FuncObject& func) const
298  {
299  // Optimization: We pass a plain pointer here, not smart pointer.
300  // As long as the FuncObject does not need to store the pointer,
301  // this isn't a problem.
302  foreach (const NodeElem& el, node.elements)
303  func(&(*el.obj));
304  foreach (const Node& child, node.children)
305  processAll(child, func);
306  }
307 
309  int maxObjectsPerNode;
311  int maxLevel;
312  };
313 
315  int maxObjectsPerNode;
316 
317  RootNode* rootNode;
318 };
319 
320 #endif // _STELSPHERICALINDEX_HPP_
321 
322