CODEWITHSUNDEEP
binary-search-treebsp-tree
Saba
Saba

Reputation: 9

Convert unbalanced to balanced bsp tree?

How I can change an unbalanced bsp to a balanced bsp tree?

Upvotes: 0

Views: 220

Answers (1)

jdolan
jdolan

Reputation: 587

In Quake, this is really left up to the mapper. The Quake BSP compiler starts bisecting volumes from the origin (0, 0, 0). So, in order to produce a more balanced and BSP-friendly map, the mapper should center their geometry, on all three axis, around the origin.

I think a similar strategy could apply to your problem. Find the absolute bounds (mins and maxs) of your BSP nodes, and calculate the point in the center. That is where you should begin partitioning your tree. Now, unless your map is perfectly symmetrical, you will never achieve a perfectly balanced tree. But, for practical purposes, this gets you relatively close.

Upvotes: 0

Related Questions