2 replies to this topic

[Alienizer]

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 ???

[Vilem Otte]

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.

[Alienizer]

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