KD Tree rare weird results

88dc730f0f71e55be39de0ad103bd9ff
0
Alienizer 109 Jul 02, 2012 at 20:28

I’ve implemented a stack, non-recursive KD-Tree for my triangles, but I get some weird effect sometimes. The problem is at this code…

if Split_Pos.x >= Split_Axis.x {

} else {

}

If I change it to

if Split_Pos.x > Split_Axis.x {

then it works, but the problem is elsewhere! What should I do when Split_Pos.x = Split_Axis.x ???

2 Replies

Please log in or register to post a reply.

B20d81438814b6ba7da7ff8eb502d039
0
Vilem_Otte 117 Jul 02, 2012 at 22:05

All items in KD-tree are assigned to either left, right or both sides. If your item is exactly at boundary, then you can assign it to left or right (means left, right … actually we could also to left and right - but that would duplicate items on edge -> leading to small unused overhead). If it crosses boundary you must assign it to both sides (e.g. left and right).

Imagine this case:

**|**
**A**
**A**
**A**
**|**

Where | is splitting plane in KD-tree and A is your item. In this case you can assign item A to either left or right sub-node.

**|**
**|A*
**A**
*A|**
**|**

On the other hand in this case you have to assign item A to both, left and right sub-nodes.

Anyway there might be also a bug in your traversal code if you assign boundary items to left/right, remember, that your traversal must also consider things on boundary (e.g. not using just < or > operators, but also <= or >= operators - otherwise item at boundary can be ignored - which leads to incorrect result.

88dc730f0f71e55be39de0ad103bd9ff
0
Alienizer 109 Jul 03, 2012 at 00:32

Thanks! That clarified it for me, and I had > as oppose to >= in the kd_Build and it works fine now. Thanks again :)