NDEVR
API Documentation
KDTree.hpp
1/*--------------------------------------------------------------------------------------------
2Copyright (c) 2019, NDEVR LLC
3tyler.parke@ndevr.org
4 __ __ ____ _____ __ __ _______
5 | \ | | | __ \ | ___|\ \ / / | __ \
6 | \ | | | | \ \ | |___ \ \ / / | |__) |
7 | . \| | | |__/ / | |___ \ V / | _ /
8 | |\ |_|_____/__|_____|___\_/____| | \ \
9 |__| \__________________________________| \__\
10
11Subject to the terms of the Enterprise+ Agreement, NDEVR hereby grants
12Licensee a limited, non-exclusive, non-transferable, royalty-free license
13(without the right to sublicense) to use the API solely for the purpose of
14Licensee's internal development efforts to develop applications for which
15the API was provided.
16
17The above copyright notice and this permission notice shall be included in all
18copies or substantial portions of the Software.
19
20THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
21INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
22PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE
23FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
24OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
25DEALINGS IN THE SOFTWARE.
26
27Library: Tree
28File: KDTree
29Included in API: False
30Author(s): Tyler Parke
31\internal
32 *-----------------------------------------------------------------------------------------**/
33#pragma once
34#include <NDEVR/TreeIterator.h>
35#include <NDEVR/Node.h>
36#include <NDEVR/Tree.h>
37#include <NDEVR/BaseValues.h>
38#include <NDEVR/Buffer.h>
39#include <NDEVR/Bounds.h>
40#include <NDEVR/Median.h>
41#include <NDEVR/InfoPipe.h>
42#include <NDEVR/Vector.h>
43#include <NDEVR/VectorFunctions.h>
44#include <NDEVR/Intersection.h>
45#include <NDEVR/BinaryHeap.h>
46
47
48namespace NDEVR
49{
50 template<uint01 t_dims, class t_type>
51 class KDNode : public TreeNode
52 {
53 public:
54 KDNode(const KDNode& node)
55 : TreeNode(node)
56 , m_split(0)
57 , m_split_dim(0)
58 {}
59 explicit KDNode(uint04 index_start)
60 : TreeNode(index_start)
61 , m_split(0)
62 , m_split_dim(0)
63 {}
64
65 void clear(uint04 index_start, const Bounds<t_dims, t_type>& bounds)
66 {
67 setBegin(index_start);
68 //TreeNode::template m_cache_bounds = bounds;
69 m_element_size = 0;
70 }
71
72 uint04 left() const
73 {
74 return uint04(m_child_start);
75 }
76 uint04 right() const
77 {
78 return uint04(m_child_start) + 1;
79 }
80
81 const t_type& split() const
82 {
83 return m_split;
84 }
85 const uint01& splitDim() const
86 {
87 return m_split_dim;
88 }
89 void setSplit(uint01 split_dim, t_type split)
90 {
91 m_split = split;
92 m_split_dim = split_dim;
93 }
94 protected:
95 t_type m_split;
96 uint01 m_split_dim;
97 };
98
99
100
101 template<uint01 t_dims, class t_type>
102 class KDTreeBase : public TreeBase<KDNode<t_dims, t_type>, t_type, 2>
103 {
104 public:
105 explicit KDTreeBase<t_dims, t_type>(uint04 bucket_size)
106 : TreeBase(bucket_size)
107 {}
108 KDTreeBase<t_dims, t_type>(const KDTreeBase<t_dims, t_type>& tree)
109 : TreeBase(tree)
110 {}
111 KDTreeBase<t_dims, t_type>(KDTreeBase<t_dims, t_type>&& tree)
112 : TreeBase(std::move(tree))
113 {}
114 protected:
115 KDTreeBase<t_dims, t_type>(const Buffer<KDNode<t_dims, t_type>>& nodes, const Buffer<uint04>& indices, bool is_read_only)
116 : TreeBase(nodes, indices, is_read_only)
117 {}
118 public:
119 template<class t_node_type>
120 bool validate(const Buffer<t_node_type>& elements)
121 {
122 TreeIterator iterator(root_node);
123
124 Buffer<bool> values;
125 values.setSize(elements.size());
126
127 while (iterator.valid())
128 {
129
130 uint04 node_index = iterator.get();
131 KDNode<t_dims, t_type>& node = m_nodes[node_index];
132 iterator.pop();
133
134 values.setAllToValue(false);
135 _getAllT(node_index, values);
136 if (node.size() != values.numSet())
137 return false;
138 }
139 return true;
140 }
141
142 protected:
143 template<class t_node_type, class t_buffer_type>
144 uint04 _calculateAndSplit(uint04 node_index, Bounds<t_dims, t_type> node_bounds, const t_buffer_type& elements, Buffer<uint04>& indices, uint04 start, uint04 end, bool is_precise)
145 {
146 Vector<t_dims, uint04> location;
147 Vector<t_dims, t_type> d_size;//The difference between the right and left size if a given node is chosen
148 for (uint01 dim = 0; dim < t_dims; ++dim)
149 {
150 if (is_precise)
151 location[dim] = median(elements, indices, start, end, dim);
152 else
153 location[dim] = ApxMedian(elements, indices, start, end, dim);
154 Bounds<t_dims, t_type> bounds(elements[indices[location[dim]]]);
155 d_size[dim] = getMin(
156 abs(bounds.center()[dim] - node_bounds[MIN][dim])
157 , abs(node_bounds[MAX][dim] - bounds.center()[dim]));
158 }
159 const uint01 split_dim = d_size.getDimension<MAX>();//maximize our smallest split dimension
160 if (is_precise)
161 location[split_dim] = median(elements, indices, start, end, split_dim);
162
163 const uint04 new_left = SortAboutValue<t_type>(location[split_dim], elements, indices, start, end, split_dim);
164
165 splitLeafNode(node_index);
166 m_nodes[node_index].setSplit(split_dim, elements[indices[new_left]][split_dim]);
167
168 return new_left;
169 }
170
171
172 template<class t_node_type, class t_buffer_type>
173 bool _balanceLeafNode(uint04 top_index, const t_buffer_type& elements, Buffer<uint04>& indices, uint04 top_start, uint04 top_end, bool is_precise, ProgressInfo& progress)
174 {
175 uint04 start_stack[256];
176 uint04 end_stack[256];
177 Bounds<t_dims, t_type> node_bounds[256];
178 start_stack[0] = top_start;
179 end_stack[0] = top_end;
180 node_bounds[0] = _getBounds<t_dims>(indices, elements, top_start, top_end);
181 TreeIterator iterator(top_index);
182 uint04 size = 0;
183 const uint04 update_size = getMax(uint04(1000), (top_end - top_start) / 10000);
184
185 while (iterator.valid())
186 {
187 uint01 level = iterator.depth();
188 uint04 start = start_stack[level];
189 uint04 end = end_stack[level];
190 uint04 node_index = iterator.get();
191 Bounds<t_dims, t_type> bounds = node_bounds[level];
192
193 iterator.pop();
194 m_nodes[node_index].setSize(end - start);
195
196 if ((end - start) > m_bucket_size)
197 {
198 const uint04 new_left = _calculateAndSplit(node_index, bounds, elements, indices, start, end, is_precise);
199
200 iterator.addAndGoToIndex(m_nodes[node_index].right());
201 start_stack[iterator.depth()] = new_left;
202 end_stack[iterator.depth()] = end;
203 node_bounds[iterator.depth()] = bounds;
204 node_bounds[iterator.depth()][MIN][m_nodes[node_index].splitDim()] = m_nodes[node_index].split();
205
206 iterator.addAndGoToIndex(m_nodes[node_index].left());
207 start_stack[iterator.depth()] = start;
208 end_stack[iterator.depth()] = new_left;
209 node_bounds[iterator.depth()] = bounds;
210 node_bounds[iterator.depth()][MAX][m_nodes[node_index].splitDim()] = m_nodes[node_index].split();
211 }
212 else
213 {
214 m_indices.setAll(indices.begin(start), m_nodes[node_index].begin(), (end - start));
215 size += (end - start);
216
217 if (progress.isValid() && node_index % update_size == 0)
218 progress.setProgress(cast<fltp04>(size) / elements.size());
219 }
220 }
221 if (progress.isValid())
222 progress.setProgress(1.0f);
223 return true;
224 }
225
226
227 template<class t_node_type, class t_buffer_type>
228 bool _getClosestElement(uint04 top_index, const Vector<t_dims, t_type>& point, const t_buffer_type& elements, t_type& min_distance, const t_type epsilon, uint04& min_index) const
229 {
230 TreeIterator iterator(top_index);
231 t_type split_values[256];
232 while (iterator.valid())
233 {
234 const uint04 index = iterator.get();
235 if (split_values[iterator.depth()] >= min_distance)
236 {
237 iterator.pop();
238 continue;
239 }
240 iterator.pop();
241
242 const KDNode<t_dims, t_type>& node = m_nodes[index];
243
244 if (node.isLeaf())
245 {
246 const uint04 end = node.end();
247 for (uint04 i = node.begin(); i < end; i++)
248 {
249 const uint04 check_index = m_indices[i];
250 t_type distance = distanceSquared(point, elements[check_index]);
251 if (distance < min_distance)
252 {
253 min_distance = distance;
254 min_index = check_index;
255 if (distance <= epsilon)
256 return true;
257 }
258 }
259 }
260 else
261 {
262 const t_type distance = point[node.splitDim()] - node.split();
263 if (distance > 0)
264 {
265 iterator.addAndGoToIndex(node.left());
266 split_values[iterator.depth()] = distance * distance;
267
268 iterator.addAndGoToIndex(node.right());
269 split_values[iterator.depth()] = 0;
270 }
271 else
272 {
273 iterator.addAndGoToIndex(node.right());
274 split_values[iterator.depth()] = distance * distance;
275
276 iterator.addAndGoToIndex(node.left());
277 split_values[iterator.depth()] = 0;
278 }
279 }
280 }
281 return false;
282 }
283
284 template<class t_node_type, class t_buffer_type>
285 void _getClosestElements(uint04 top_index, const Vector<t_dims, t_type>& point, const t_buffer_type& elements, t_type& min_distance, const t_type& epsilon, MinHeap<t_type, uint04>& heap, uint04 size) const
286 {
287 TreeIterator iterator(top_index);
288 t_type split_values[255];
289 while (iterator.valid())
290 {
291 const uint04 index = iterator.get();
292 if (split_values[iterator.depth()] >= min_distance)
293 {
294 iterator.pop();
295 continue;
296 }
297 iterator.pop();
298
299 const KDNode<m_bucket_size, t_dims, t_type>& node = m_nodes[index];
300 if (node.isLeaf())
301 {
302 const uint04 end = node.end();
303 for (uint04 i = node.begin(); i < end; i++)
304 {
305 uint04 check_index = m_indices[i];
306 t_type distance = distanceSquared(point, elements[check_index]);
307 if (distance < min_distance)
308 {
309 heap.insert(distance, check_index);
310 if (heap.size() == size + 1)
311 {
312 heap.deleteMax();
313 min_distance = heap.max();
314 }
315 }
316 }
317 if (min_distance <= epsilon)
318 return;
319 }
320 else
321 {
322 const t_type distance = point[node.splitDim()] - node.split();
323 if (distance > 0)
324 {
325 iterator.addAndGoToIndex(node.left());
326 split_values[iterator.depth()] = distance * distance;
327
328
329 iterator.addAndGoToIndex(node.right());
330 split_values[iterator.depth()] = 0;
331 }
332 else
333 {
334 iterator.addAndGoToIndex(node.right());
335 split_values[iterator.depth()] = distance * distance;
336
337
338 iterator.addAndGoToIndex(node.left());
339 split_values[iterator.depth()] = 0;
340 }
341 }
342 }
343 }
344
345 template<class t_node_type, class t_buffer_type>
346 bool _getClosestElement(uint04 top_index, const LineSegment<t_dims, t_type>& top_line, const t_buffer_type& elements, t_type& min_distance, t_type epsilon, uint04& min_index) const
347 {
348 TreeIterator iterator(top_index);
349 t_type split_values[256];
350
351 Vector<3, uint01> dim_min;
352 Vector<3, uint01> dim_max;
353 for (uint01 i = 0; i < t_dims; i++)
354 {
355 dim_min[i] = top_line[0][i] < top_line[1][i] ? MIN : MAX;
356 dim_max[i] = dim_min[i] != MIN ? MIN : MAX;
357 }
358
359 split_values[0] = 0;
360 t_type sqrt_min_dist = sqrt(min_index);
361 CachedLineSegment<t_dims, t_type> cached_line(top_line);
362
363 while (iterator.valid())
364 {
365 const uint04 index = iterator.get();
366 if (abs(split_values[iterator.depth()]) >= min_distance)
367 {
368 iterator.pop();
369 continue;
370 }
371 //const LineSegment<t_dims, t_type> line = lines[iterator.depth()];
372
373 iterator.pop();
374 const KDNode<t_dims, t_type>& node = m_nodes[index];
375
376 if (node.isLeaf())
377 {
378 const uint04 end = node.end();
379 for (uint04 i = node.begin(); i < end; i++)
380 {
381 uint04 check_index = m_indices[i];
382 t_type distance = distanceSquared(cached_line, elements[check_index]);
383 if (distance < min_distance)
384 {
385 min_distance = distance;
386 min_index = check_index;
387 sqrt_min_dist = sqrt(min_index);
388 }
389 }
390 if (distance <= epsilon)
391 return true;
392 }
393 else
394 {
395 const uint01 split_dim = m_nodes[index].splitDim();
396 const uint01 min = dim_min[split_dim];
397 const uint01 max = dim_max[split_dim];
398 if (cached_line[max][split_dim] >= m_nodes[index].split())
399 {
400 if (cached_line[min][split_dim] <= m_nodes[index].split())
401 {
402 iterator.addAndGoToIndex(node.right());
403 split_values[iterator.depth()] = 0;
404
405 iterator.addAndGoToIndex(node.left());
406 split_values[iterator.depth()] = 0;
407 }
408 else
409 {
410 iterator.addAndGoToIndex(node.left());
411 split_values[iterator.depth()] = cached_line[min][split_dim] - m_nodes[index].split();
412 split_values[iterator.depth()] *= split_values[iterator.depth()];
413
414 iterator.addAndGoToIndex(node.right());
415 split_values[iterator.depth()] = 0;
416 }
417 }
418 else if (cached_line[min][split_dim] <= m_nodes[index].split())
419 {
420 iterator.addAndGoToIndex(node.right());
421 split_values[iterator.depth()] = m_nodes[index].split() - cached_line[max][split_dim];
422 split_values[iterator.depth()] *= -split_values[iterator.depth()];
423
424 iterator.addAndGoToIndex(node.left());
425 split_values[iterator.depth()] = 0;
426 }
427 }
428 }
429 return false;
430 }
431
432 template<class t_node_type, class t_buffer_type>
433 bool _getClosestElement(uint04 top_index, const Triangle<t_dims, t_type>& triangle, const t_buffer_type& elements, t_type& min_distance, t_type epsilon, uint04& min_index) const
434 {
435 TreeIterator iterator(top_index);
436
437 CachedTriangle<t_dims, t_type> cached_tri(triangle);
438
439 while (iterator.valid())
440 {
441 const uint04 index = iterator.get();
442 iterator.pop();
443 const KDNode<m_bucket_size, t_dims, t_type>& node = m_nodes[index];
444 if (!node.bounds().expand(sqrt(min_distance)).doBoundsIntersect<t_dims>(cached_tri))
445 continue;
446 if (node.isLeaf())
447 {
448 const uint04 end = node.end();
449 for (uint04 i = node.begin(); i < end; i++)
450 {
451 const uint04 check_index = m_indices[i];
452 const t_type distance = distanceSquared(cached_tri, elements[check_index]);
453 if (distance < min_distance)
454 {
455 min_distance = distance;
456 min_index = check_index;
457 }
458 }
459 if (distance <= epsilon)
460 return true;
461 }
462 else
463 {
464 if (m_nodes[node.left()].bounds().contains(cached_tri.centroid()))
465 iterator.addAndGoToIndex(node.right(), node.left());
466 else
467 iterator.addAndGoToIndex(node.left(), node.right());
468 }
469 }
470 return false;
471 }
472
473 template<class t_node_type, class t_area_type, class t_buffer_type>
474 void _getEnclosedElements(uint04 top_node, t_area_type area, Buffer<bool>& indices, const t_buffer_type& elements) const
475 {
476 Bounds<t_dims, t_type> bounds[256];
477 bounds[0] = Constant<Bounds<t_dims, t_type>>::Max;
478 TreeIterator iterator(top_node);
479 while (iterator.valid())
480 {
481 uint04 index = iterator.get();
482 const KDNode<t_dims, t_type>& node = m_nodes[index];
483 const Bounds<t_dims, t_type> box = bounds[iterator.depth()];
484 iterator.pop();
485 switch (classify(area, box))
486 {
487 case IntersectionTypes::e_inside:
488 _getAll<false>(index, indices);
489 break;
490 case IntersectionTypes::e_outside:
491 break;
492 case IntersectionTypes::e_mixed:
493 if (node.isLeaf())
494 {
495 const uint04 end = node.begin() + node.size();
496 for (uint04 i = node.begin(); i < end; i++)
497 {
498 if (classify(area, elements[m_indices[i]]) != IntersectionTypes::e_outside)
499 {
500 indices.set(m_indices[i], true);
501 }
502 }
503 }
504 else
505 {
506 Bounds<t_dims, t_type> left = box;
507 left[MAX][node.splitDim()] = node.split();
508 Bounds<t_dims, t_type> right = box;
509
510 Bounds<t_dims, t_type> left = box;
511 right[MIN][node.splitDim()] = node.split();
512
513 iterator.addAndGoToIndex(node.left());
514 bounds[iterator.depth()] = left;
515
516 iterator.addAndGoToIndex(node.right());
517 bounds[iterator.depth()] = right;
518 }
519 break;
520 }
521 }
522 }
523
524 template<class t_area_type, class t_node_type, class t_buffer_type>
525 uint04 _getNumberOfEnclosedElements(uint04 top_node, const t_area_type& area, const t_buffer_type& elements) const
526 {
527 TreeIterator iterator(top_node);
528 uint04 size = 0;
529 while (iterator.valid())
530 {
531 uint04 index = iterator.get();
532 const KDNode<t_dims, t_type>& node = m_nodes[index];
533 iterator.pop();
534 switch (classify(area, node.bounds()))
535 {
536 case IntersectionTypes::e_inside:
537 size += node.size();
538 break;
539 case IntersectionTypes::e_outside:
540 break;
541 case IntersectionTypes::e_mixed:
542 if (node.isLeaf())
543 {
544 const uint04 end = node.begin() + node.size();
545 for (uint04 i = node.begin(); i < end; i++)
546 {
547 if (classify(area, elements[m_indices[i]]) != IntersectionTypes::e_outside)
548 {
549 ++size;
550 }
551 }
552 }
553 else
554 {
555 iterator.addAndGoToIndex(node.left(), node.right());
556 }
557 break;
558 }
559 }
560 return size;
561 }
562
563
564 template<class t_node_type, class t_buffer_type>
565 void _removeValue(uint04 top_node, uint04 index, const t_buffer_type& elements)
566 {
567 bool recalculate_bounds = false;
568 TreeIterator iterator(top_node);
569 while (iterator.valid())
570 {
571 const uint04 node_index = iterator.get();
572 KDNode<t_dims, t_type>& node = m_nodes[node_index];
573 if (node.isLeaf())
574 {
575 uint04 end = node.end();
576 Bounds<t_dims, t_type> bounds(Constant<Bounds<t_dims, t_type>>::Min);
577 uint04 index_location = Constant<uint04>::Invalid;
578 for (uint04 i = node.begin(); i < end; i++)
579 {
580 uint04 check_index = m_indices[i];
581 if (index != check_index)
582 bounds.addToBounds(elements[check_index]);
583 else
584 index_location = i;
585 }
586 node.setSize(node.size() - 1);
587 if (node.size() != 0)
588 m_indices.swapIndices(index_location, node.end());
589 if (classify(node.bounds(), bounds) == IntersectionTypes::e_inside)
590 recalculate_bounds = true;
591 node.setBounds(bounds);
592 iterator.pop();
593 break;
594 }
595 else
596 {
597
598 bool needs_rebalance = false;
599 if (classify(m_nodes[node.left()].bounds(), elements[index]) == IntersectionTypes::e_inside)
600 {
601 if (needsRebalance(m_nodes[node.left()].size() - 1, m_nodes[node.right()].size()))
602 needs_rebalance = true;
603 else
604 iterator.addAndGoToIndex(node.left());
605 }
606 else
607 {
608 if (needsRebalance(m_nodes[node.left()].size(), m_nodes[node.right()].size() - 1))
609 needs_rebalance = true;
610 else
611 iterator.addAndGoToIndex(node.right());
612 }
613 if (needs_rebalance || node.size() - 1 == m_bucket_size)
614 {
615 Buffer<uint04> indices(node.size());
616 _getAll(node_index, indices);
617 node.setSize(node.size() - 1);
618 indices.removeElement(index);
619 reclaimChildren(node_index);
620 _balanceLeafNode(node_index, elements, indices, 0, indices.size(), false);
621 recalculate_bounds = true;
622 break;
623 }
624 else
625 {
626 node.setSize(node.size() - 1);
627 }
628 }
629 }
630 if (recalculate_bounds)
631 {
632 while (iterator.valid())
633 {
634 if (!recalculateBounds(iterator.get(), elements))
635 return;
636 iterator.pop();
637 }
638 }
639 }
640
641
642 template<class t_node_type, class t_buffer_type>
643 void _moveValue(uint04 top_node, uint04 index, const t_node_type& new_location, const t_buffer_type& elements)
644 {
645 TreeIterator iterator(top_node);
646 bool recalculate_bounds = false;
647 while (iterator.valid())
648 {
649 const uint04 node_index = iterator.get();
650 KDNode<t_dims, t_type>& node = m_nodes[node_index];
651 if (node.isLeaf())
652 {
653 if (classify(m_nodes[node.left()].bounds(), new_location) == IntersectionTypes::e_inside)
654 return;
655 uint04 end = node.end();
656 Bounds<t_dims, t_type> bounds(Constant<Bounds<t_dims, t_type>>::Min);
657 uint04 index_location = Constant<uint04>::Invalid;
658 for (uint04 i = node.begin(); i < end; i++)
659 {
660 uint04 check_index = m_indices[i];
661 if (index != check_index)
662 bounds.addToBounds(elements[check_index]);
663 else
664 index_location = i;
665 }
666 node.setSize(node.size() - 1);
667 if (node.size() != 0)
668 m_indices.swapIndices(index_location, node.end());
669 recalculate_bounds = (classify(node.bounds(), bounds) != IntersectionTypes::e_inside);
670 node.setBounds(bounds);
671 iterator.pop();
672 break;
673 }
674 else
675 {
676
677 bool needs_rebalance = false;
678 if (classify(m_nodes[node.left()].bounds(), elements[index]) == IntersectionTypes::e_inside)
679 {
680 if (needsRebalance(m_nodes[node.left()].size() - 1, m_nodes[node.right()].size()))
681 needs_rebalance = true;
682 else
683 iterator.addAndGoToIndex(node.left());
684 }
685 else
686 {
687 if (needsRebalance(m_nodes[node.left()].size(), m_nodes[node.right()].size() - 1))
688 needs_rebalance = true;
689 else
690 iterator.addAndGoToIndex(node.right());
691 }
692 if (needs_rebalance || node.size() - 1 == m_bucket_size)
693 {
694 Buffer<uint04> indices(node.size());
695 _getAll(node_index, indices);
696 node.setSize(node.size() - 1);
697 indices.removeElement(index);
698 reclaimChildren(node_index);
699 _balanceLeafNode(node_index, elements, indices, 0, indices.size());
700 recalculate_bounds = true;
701 break;
702 }
703 else
704 {
705 node.setSize(node.size() - 1);
706 }
707 }
708 }
709 if (recalculate_bounds)
710 {
711 while (iterator.valid())
712 {
713 if (!recalculateBounds(iterator.get(), elements))
714 return;
715 iterator.pop();
716 }
717 }
718 }
719
720 bool needsRebalance(uint04 left_size, uint04 right_size)
721 {
722 const uint04 total_size = left_size + right_size;
723 return (left_size < total_size / 4 || right_size < total_size / 4);
724 }
725
726 bool useBulkResize(uint04 change_size)
727 {
728 return (change_size > size() / 4);
729 }
730 template<class t_node_type, class t_buffer_type>
731 bool recalculateBounds(uint04 node_index, const t_buffer_type& elements)
732 {
733 Bounds<t_dims, t_type> bounds(Constant<Bounds<t_dims, t_type>>::Min);
734 KDNode<t_dims, t_type>& node = m_nodes[node_index];
735 if (node.isLeaf())
736 {
737 uint04 end = node.end();
738 for (uint04 i = node.begin(); i < end; i++)
739 {
740 bounds.addToBounds(elements[m_indices[i]]);
741 }
742 }
743 else
744 {
745 bounds = Bounds<t_dims, t_type>(m_nodes[node.left()].bounds(), m_nodes[node.right()].bounds());
746 }
747 if (classify(node.bounds(), bounds) == IntersectionTypes::e_inside)
748 return false;
749 node.setBounds(bounds);
750 return true;
751 }
752 protected:
753 template<class t_node_type, class t_buffer_type>
754 void _addValues(uint04 top_node, Buffer<uint04> indices, const t_buffer_type& elements, bool is_precise, ProgressInfo& progress)
755 {
756 _getAll(top_node, indices);
757 reclaimChildren(top_node);
758
759 uint04 max_size = 3 * indices.size();
760 m_indices.ensureCapacity(max_size + (m_indices.size() - getNumberOfFreeIndices()));
761 m_nodes.ensureCapacity(2 * max_size / m_bucket_size + (m_nodes.size() - getNumberOfNodes()));
762
763 //m_nodes[top_node].setBounds(_getBounds(indices, elements, 0, indices.size()));
764 bool did_balance = _balanceLeafNode(top_node, elements, indices, 0, indices.size(), is_precise, progress);
765 }
766
767
768 template<class t_node_type, class t_buffer_type>
769 void _addValue(uint04 node_index, uint04 index, const t_buffer_type& elements)
770 {
771 /*Bounds<t_dims, t_type> bounds(elements[index]);
772 for (;;)
773 {
774
775 KDNode<t_dims, t_type>& node = m_nodes[node_index];
776 node.bounds().addToBoundingBox(bounds);
777 if (node.isLeaf())
778 {
779 if (node.size() == m_bucket_size)
780 {
781 Buffer<uint04> indices(m_bucket_size + 1);
782 _getAll(node_index, indices);
783 indices.add(index);
784 _balanceLeafNode(node_index, elements, indices, 0, m_bucket_size + 1, false);
785 }
786 else
787 {
788 m_indices[node.begin() + node.size()] = index;
789 node.setSize(node.size() + 1);
790 }
791 return;
792 }
793 else
794 {
795 Bounds<t_dims, t_type> left = m_nodes[node.left()].bounds();
796 Bounds<t_dims, t_type> right = m_nodes[node.right()].bounds();
797
798 left.addToBoundingBox(bounds);
799 right.addToBoundingBox(bounds);
800 bool needs_rebalance = false;
801 if (left.volume() - m_nodes[node.left()].bounds().volume() < right.volume() - m_nodes[node.right()].bounds().volume())
802 {
803 if (needsRebalance(m_nodes[node.left()].size() + 1, m_nodes[node.right()].size()))
804 needs_rebalance = true;
805 else
806 node_index = node.left();
807 }
808 else
809 {
810 if (needsRebalance(m_nodes[node.left()].size(), m_nodes[node.right()].size() + 1))
811 needs_rebalance = true;
812 else
813 node_index = node.right();
814 }
815 if (needs_rebalance)
816 {
817 Buffer<uint04> indices(node.size() + 1);
818 _getAll(node_index, indices);
819 indices.add(index);
820 reclaimChildren(node_index);
821 _balanceLeafNode(node_index, elements, indices, 0, indices.size(), false);
822 return;
823 }
824 else
825 {
826 node.setSize(node.size() + 1);
827 }
828 }
829 }*/
830 }
831
832 void _makeWriteable()
833 {
834 if (!m_is_read_only)
835 return;
836 Buffer<uint04> indices(size());
837
838 TreeIterator iterator(root_node);
839 while (iterator.valid())
840 {
841 KDNode<m_bucket_size, t_dims, t_type>& node = m_nodes[iterator.get()];
842 iterator.pop();
843 if (node.isLeaf())
844 {
845 node.setBegin(iterator.size());
846 indices.addAll(m_indices.begin(node.begin()), node.size());
847 }
848 else
849 iterator.addAndGoToIndex(node.left(), node.right());
850 }
851 m_indices = indices;
852 }
853 };
854
855
856 template<uint01 t_dims, class t_type>
857 class KDTree : public Tree<t_dims, t_type, KDTreeBase<t_dims, t_type>>
858 {
859 public:
860 explicit KDTree<t_dims, t_type>(uint04 bucket_size)
861 : Tree(bucket_size)
862 {}
863 KDTree<t_dims, t_type>(const KDTreeBase<t_dims, t_type>& tree)
864 : Tree(tree)
865 {}
866 KDTree<t_dims, t_type>(KDTreeBase<t_dims, t_type>&& tree)
867 : Tree(std::move(tree))
868 {}
869 protected:
870 KDTree<t_dims, t_type>(const Buffer<KDNode<t_dims, t_type>>& nodes, const Buffer<uint04>& indices, bool is_read_only)
871 : TreeBase(nodes, indices, is_read_only)
872 {}
873 public:
874 inline KDTree& operator=(const KDTree& value)
875 {
876 m_indices = value.m_indices;//setting equal to ourselves
877 m_nodes = value.m_nodes;
878 m_available_node_positions = value.m_available_node_positions;
879 m_available_indexed_positions = value.m_available_indexed_positions;
880 return (*this);
881 }
882 inline KDTree& operator=(KDTree&& value)
883 {
884 std::swap(m_indices, value.m_indices);//setting equal to ourselves
885 std::swap(m_nodes, value.m_nodes);
886 std::swap(m_available_node_positions, value.m_available_node_positions);
887 std::swap(m_available_indexed_positions, value.m_available_indexed_positions);
888 return (*this);
889 }
890
891 virtual const char* getTreeType() const override
892 {
893 return "KD Tree";
894 }
895 };
896}
897/*--------------------------------------------------------------------------------------------
898\endinternal
899 *-----------------------------------------------------------------------------------------**/
NDEVR
The primary namespace for the NDEVR SDK.
Definition ArialTileFetcherModule.h:35
getMin
constexpr t_type getMin(const t_type &left, const t_type &right)
Finds the minimum of the given arguments based on the < operator Author: Tyler Parke Date: 2017-11-05...
Definition BaseFunctions.hpp:56
getMax
constexpr t_type getMax(const t_type &left, const t_type &right)
Finds the max of the given arguments using the > operator The only requirement is that t_type have > ...
Definition BaseFunctions.hpp:94
abs
constexpr Angle< t_angle_type > abs(const Angle< t_angle_type > &value)
Changes an input with a negative sign, to a positive sign.
Definition AngleFunctions.h:753
uint04
uint32_t uint04
-Defines an alias representing a 4 byte, unsigned integer -Can represent exact integer values 0 throu...
Definition BaseValues.hpp:97
SortAboutValue
uint04 SortAboutValue(uint04 value_index, const Buffer< t_node_type > &points, Buffer< uint04 > &indices, uint04 start, uint04 end, uint01 dimension)
Sorts all incoming indices within the given range such that the resulting index matrix will have valu...
Definition Median.hpp:349
Max
constexpr HSLColor Constant< HSLColor >::Max
The maximum HSLColor constant with all components at their maximum values.
Definition HSLColor.h:265
ApxMedian
uint04 ApxMedian(const t_buffer_type &elements, const Buffer< uint04 > &indices, uint04 start, uint04 end, uint01 dimension)
Returns the aproximate median, or value that is close to the median, significantly faster than it wou...
Definition Median.hpp:307
uint01
uint8_t uint01
-Defines an alias representing a 1 byte, unsigned integer -Can represent exact integer values 0 throu...
Definition BaseValues.hpp:81
sqrt
t_type sqrt(const t_type &value)
Definition VectorFunctions.hpp:1181
Min
constexpr HSLColor Constant< HSLColor >::Min
The minimum HSLColor constant with saturation, brightness, and alpha at zero.
Definition HSLColor.h:266
cast
constexpr t_to cast(const Angle< t_from > &value)
Casts an Angle from one backing type to another.
Definition Angle.h:408