1#include "generic_hierarchy.hpp"
2#include "ostream_utility.hpp"
3
4namespace
5{
6enum
7 {
8 splitting_size = 20,
9 };
10
11class Element
12{
13public:
14 Element(const BoundingBox<float> &b, unsigned int r):
15 m_box(b),
16 m_reference(r)
17 {}
18
19 BoundingBox<float> m_box;
20 unsigned int m_reference;
21};
22
23class TreeBase:fastuidraw::noncopyable
24{
25public:
26 explicit
27 TreeBase(const BoundingBox<float> &bbox):
28 m_bbox(bbox)
29 {}
30
31 virtual
32 ~TreeBase()
33 {}
34
35 TreeBase*
36 add(const BoundingBox<float> &bbox, unsigned int reference)
37 {
38 if (bbox.intersects(m_bbox))
39 {
40 return add_implement(bbox, reference);
41 }
42 else
43 {
44 return this;
45 }
46 }
47
48 void
49 query(const BoundingBox<float> &bbox,
50 std::vector<unsigned int> *output)
51 {
52 if(bbox.intersects(m_bbox))
53 {
54 query_implement(bbox, output);
55 }
56 }
57
58 unsigned int
59 query(const fastuidraw::vec2 &p,
60 BoundingBox<float> *out_bb)
61 {
62 if (m_bbox.intersects(p))
63 {
64 return query_implement(p, out_bb);
65 }
66 else
67 {
68 return GenericHierarchy::not_found;
69 }
70 }
71
72 const BoundingBox<float>&
73 bounding_box(void)
74 {
75 return m_bbox;
76 }
77
78private:
79 virtual
80 TreeBase*
81 add_implement(const BoundingBox<float> &bbox,
82 unsigned int reference) = 0;
83
84 virtual
85 void
86 query_implement(const BoundingBox<float> &bbox,
87 std::vector<unsigned int> *output) = 0;
88
89 virtual
90 unsigned int
91 query_implement(const fastuidraw::vec2 &p,
92 BoundingBox<float> *out_bb) = 0;
93
94 BoundingBox<float> m_bbox;
95};
96
97class Node:public TreeBase
98{
99public:
100 Node(const BoundingBox<float> &bbox,
101 const BoundingBox<float> &bbox0,
102 const std::vector<Element> &elements0,
103 const BoundingBox<float> &bbox1,
104 const std::vector<Element> &elements1);
105
106 ~Node();
107
108private:
109 virtual
110 TreeBase*
111 add_implement(const BoundingBox<float> &bbox,
112 unsigned int reference);
113
114 virtual
115 void
116 query_implement(const BoundingBox<float> &bbox,
117 std::vector<unsigned int> *output);
118
119 virtual
120 unsigned int
121 query_implement(const fastuidraw::vec2 &p,
122 BoundingBox<float> *out_bb);
123
124 fastuidraw::vecN<TreeBase*, 2> m_children;
125 std::vector<Element> m_elements;
126};
127
128class Leaf:public TreeBase
129{
130public:
131 explicit
132 Leaf(const BoundingBox<float> &bbox);
133
134 Leaf(const BoundingBox<float> &bbox,
135 const std::vector<Element> &elements);
136
137 ~Leaf();
138
139private:
140 virtual
141 TreeBase*
142 add_implement(const BoundingBox<float> &bbox,
143 unsigned int reference);
144
145 virtual
146 void
147 query_implement(const BoundingBox<float> &bbox,
148 std::vector<unsigned int> *output);
149
150 virtual
151 unsigned int
152 query_implement(const fastuidraw::vec2 &p,
153 BoundingBox<float> *out_bb);
154
155 std::vector<Element> m_elements;
156};
157
158}
159
160///////////////////////////////////
161// Node methods
162Node::
163Node(const BoundingBox<float> &bbox,
164 const BoundingBox<float> &bbox0,
165 const std::vector<Element> &elements0,
166 const BoundingBox<float> &bbox1,
167 const std::vector<Element> &elements1):
168 TreeBase(bbox)
169{
170 m_children[0] = FASTUIDRAWnew Leaf(bbox0, elements0);
171 m_children[1] = FASTUIDRAWnew Leaf(bbox1, elements1);
172}
173
174Node::
175~Node()
176{
177 FASTUIDRAWdelete(m_children[0]);
178 FASTUIDRAWdelete(m_children[1]);
179}
180
181TreeBase*
182Node::
183add_implement(const BoundingBox<float> &bbox, unsigned int reference)
184{
185 fastuidraw::vecN<bool, 2> child_takes;
186
187 for (unsigned int i = 0; i < 2; ++i)
188 {
189 child_takes[i] = m_children[i]->bounding_box().intersects(bbox);
190 }
191
192 if (child_takes[0] && child_takes[1])
193 {
194 Element E(bbox, reference);
195 m_elements.push_back(E);
196 }
197 else
198 {
199 unsigned int IDX;
200 TreeBase *p;
201
202 IDX = child_takes[0] ? 0u : 1u;
203 p = m_children[IDX]->add(bbox, reference);
204 if (p != m_children[IDX])
205 {
206 FASTUIDRAWdelete(m_children[IDX]);
207 m_children[IDX] = p;
208 }
209 }
210
211 return this;
212}
213
214void
215Node::
216query_implement(const BoundingBox<float> &bbox,
217 std::vector<unsigned int> *output)
218{
219 m_children[0]->query(bbox, output);
220 m_children[1]->query(bbox, output);
221 for (const auto &E : m_elements)
222 {
223 if (E.m_box.intersects(bbox))
224 {
225 output->push_back(E.m_reference);
226 }
227 }
228}
229
230unsigned int
231Node::
232query_implement(const fastuidraw::vec2 &p,
233 BoundingBox<float> *out_bb)
234{
235 int R;
236
237 R = m_children[0]->query(p, out_bb);
238 if (R != GenericHierarchy::not_found)
239 {
240 return R;
241 }
242 R = m_children[1]->query(p, out_bb);
243 if (R != GenericHierarchy::not_found)
244 {
245 return R;
246 }
247
248 for (const auto &E : m_elements)
249 {
250 if (E.m_box.intersects(p))
251 {
252 *out_bb = E.m_box;
253 return E.m_reference;
254 }
255 }
256 return GenericHierarchy::not_found;
257}
258
259///////////////////////////////////////////
260// Leaf methods
261Leaf::
262Leaf(const BoundingBox<float> &bbox, const std::vector<Element> &elements):
263 TreeBase(bbox),
264 m_elements(elements)
265{}
266
267Leaf::
268Leaf(const BoundingBox<float> &bbox):
269 TreeBase(bbox)
270{}
271
272Leaf::
273~Leaf()
274{}
275
276void
277Leaf::
278query_implement(const BoundingBox<float> &bbox,
279 std::vector<unsigned int> *output)
280{
281 for (const auto &E : m_elements)
282 {
283 if (E.m_box.intersects(bbox))
284 {
285 output->push_back(E.m_reference);
286 }
287 }
288}
289
290unsigned int
291Leaf::
292query_implement(const fastuidraw::vec2 &p,
293 BoundingBox<float> *out_bb)
294{
295 for (const auto &E : m_elements)
296 {
297 if (E.m_box.intersects(p))
298 {
299 *out_bb = E.m_box;
300 return E.m_reference;
301 }
302 }
303 return GenericHierarchy::not_found;
304}
305
306TreeBase*
307Leaf::
308add_implement(const BoundingBox<float> &bbox, unsigned int reference)
309{
310 m_elements.push_back(Element(bbox, reference));
311 if (m_elements.size() > splitting_size)
312 {
313 fastuidraw::vecN<std::vector<Element>, 2> split_x, split_y;
314 fastuidraw::vecN<BoundingBox<float>, 2> split_x_bb, split_y_bb;
315 unsigned int split_x_size(0), split_y_size(0);
316
317 split_x_bb = bounding_box().split(0);
318 split_y_bb = bounding_box().split(1);
319
320 for (const Element &E : m_elements)
321 {
322 for (unsigned int i = 0; i < 2; ++i)
323 {
324 if (split_x_bb[i].intersects(E.m_box))
325 {
326 split_x[i].push_back(E);
327 ++split_x_size;
328 }
329 if (split_y_bb[i].intersects(E.m_box))
330 {
331 split_y[i].push_back(E);
332 ++split_y_size;
333 }
334 }
335
336 FASTUIDRAWassert(split_x_bb[0].intersects(E.m_box) || split_x_bb[1].intersects(E.m_box));
337 FASTUIDRAWassert(split_y_bb[0].intersects(E.m_box) || split_y_bb[1].intersects(E.m_box));
338 }
339
340 unsigned int allow_split;
341 const float max_overlap(1.5f);
342 allow_split = static_cast<unsigned int>(max_overlap * static_cast<float>(m_elements.size()));
343
344 if (fastuidraw::t_min(split_x_size, split_y_size) <= allow_split)
345 {
346 if (split_x_size < split_y_size)
347 {
348 return FASTUIDRAWnew Node(bounding_box(),
349 split_x_bb[0], split_x[0],
350 split_x_bb[1], split_x[1]);
351 }
352 else
353 {
354 return FASTUIDRAWnew Node(bounding_box(),
355 split_y_bb[0], split_y[0],
356 split_y_bb[1], split_y[1]);
357 }
358 }
359 }
360 return this;
361}
362
363///////////////////////////////////
364// GenericHierarchy methods
365GenericHierarchy::
366GenericHierarchy(const BoundingBox<float> &bbox)
367{
368 m_root = FASTUIDRAWnew Leaf(bbox);
369}
370
371GenericHierarchy::
372~GenericHierarchy()
373{
374 TreeBase *d;
375
376 d = static_cast<TreeBase*>(m_root);
377 FASTUIDRAWdelete(d);
378}
379
380void
381GenericHierarchy::
382add(const BoundingBox<float> &bbox, unsigned int reference)
383{
384 TreeBase *d, *p;
385
386 d = static_cast<TreeBase*>(m_root);
387 p = d->add(bbox, reference);
388 if (p != d)
389 {
390 FASTUIDRAWdelete(d);
391 m_root = p;
392 }
393}
394
395void
396GenericHierarchy::
397query(const BoundingBox<float> &bbox, std::vector<unsigned int> *output)
398{
399 TreeBase *d;
400
401 d = static_cast<TreeBase*>(m_root);
402 d->query(bbox, output);
403}
404
405unsigned int
406GenericHierarchy::
407query(const fastuidraw::vec2 &p, BoundingBox<float> *out_bb)
408{
409 TreeBase *d;
410
411 d = static_cast<TreeBase*>(m_root);
412 return d->query(p, out_bb);
413}
414