1 | #include "generic_hierarchy.hpp" |
2 | #include "ostream_utility.hpp" |
3 | |
4 | namespace |
5 | { |
6 | enum |
7 | { |
8 | splitting_size = 20, |
9 | }; |
10 | |
11 | class Element |
12 | { |
13 | public: |
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 | |
23 | class TreeBase:fastuidraw::noncopyable |
24 | { |
25 | public: |
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 | |
78 | private: |
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 | |
97 | class Node:public TreeBase |
98 | { |
99 | public: |
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 | |
108 | private: |
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 | |
128 | class Leaf:public TreeBase |
129 | { |
130 | public: |
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 | |
139 | private: |
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 |
162 | Node:: |
163 | Node(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 | |
174 | Node:: |
175 | ~Node() |
176 | { |
177 | FASTUIDRAWdelete(m_children[0]); |
178 | FASTUIDRAWdelete(m_children[1]); |
179 | } |
180 | |
181 | TreeBase* |
182 | Node:: |
183 | add_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 | |
214 | void |
215 | Node:: |
216 | query_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 | |
230 | unsigned int |
231 | Node:: |
232 | query_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 |
261 | Leaf:: |
262 | Leaf(const BoundingBox<float> &bbox, const std::vector<Element> &elements): |
263 | TreeBase(bbox), |
264 | m_elements(elements) |
265 | {} |
266 | |
267 | Leaf:: |
268 | Leaf(const BoundingBox<float> &bbox): |
269 | TreeBase(bbox) |
270 | {} |
271 | |
272 | Leaf:: |
273 | ~Leaf() |
274 | {} |
275 | |
276 | void |
277 | Leaf:: |
278 | query_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 | |
290 | unsigned int |
291 | Leaf:: |
292 | query_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 | |
306 | TreeBase* |
307 | Leaf:: |
308 | add_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 |
365 | GenericHierarchy:: |
366 | GenericHierarchy(const BoundingBox<float> &bbox) |
367 | { |
368 | m_root = FASTUIDRAWnew Leaf(bbox); |
369 | } |
370 | |
371 | GenericHierarchy:: |
372 | ~GenericHierarchy() |
373 | { |
374 | TreeBase *d; |
375 | |
376 | d = static_cast<TreeBase*>(m_root); |
377 | FASTUIDRAWdelete(d); |
378 | } |
379 | |
380 | void |
381 | GenericHierarchy:: |
382 | add(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 | |
395 | void |
396 | GenericHierarchy:: |
397 | query(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 | |
405 | unsigned int |
406 | GenericHierarchy:: |
407 | query(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 | |