# KD Tree rare weird results

2 replies to this topic

### #1Alienizer

Member

• Members
• 435 posts

Posted 02 July 2012 - 08:28 PM

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

### #2Vilem Otte

Valued Member

• Members
• 345 posts

Posted 02 July 2012 - 10:05 PM

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.
My blog about game development (and not just game development) - http://gameprogramme...y.blogspot.com/

If you don't know how to speed up application, go "roarrrrrr!", hit the compiler with the club and use -O3 :D

### #3Alienizer

Member

• Members
• 435 posts

Posted 03 July 2012 - 12:32 AM

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

#### 1 user(s) are reading this topic

0 members, 1 guests, 0 anonymous users