Archived

This topic is now archived and is closed to further replies.

ogracian

Axis-Aligned BSP-Tree, Help me please....

Recommended Posts

ogracian    180
Hello I am trying to write an axis-aligned BSP-Tree compiler (Kd-tree). I understand the theory behaind kd-trees where I must split my world polys with an axis aligned plane swithching form x to y and z each subdivision, and so on until some criteria is reached. But my main trouble with this is how can I compute the best position for the spliting plane? For example: My world extents from MIN to MAX (my world bounding box). and I need split the world with a plane aligned to Y-Axis so here is the trouble (for me ) this plane(y-aligned) could be in any place from the range of MIN.x to MAX.x , but how can i know which is the best position to place this splitting plane? Thanks in advance Oscar

Share this post


Link to post
Share on other sites
Pragma    395
The best way is to find the median of the data points. You can do this with an algorithm such as quickselect. This will ensure that you have a perfectly balanced kd-tree.

"Math is hard" -Barbie

Share this post


Link to post
Share on other sites