I read that for minimize the number of leafs of a BSP tree, the best way is to take the polygons that cut the least possible of other polygons. What is the same as to maximize the tree height (generally the chosen polygon put the remaining polygons in one side). I don''t agree with that. For a binary tree which have a height equal to n where n is the number of nodes, the number of leafs is n+1. For a balanced tree, the height is equal to E( ln n/ln 2) where E is the whole part. Then the number of leafs is equal to 2^E( ln n/ln 2). However E( ln n/ln 2) <= ln n/ln 2 then 2^E(ln n/ln 2) <= 2^(ln n/ln 2) then 2^E(ln n/ln 2) <= n (or n+1). Then I think the best way is to have a balanced tree (the best way between the two I consider). What do you think ? Do I make a mistake ? !o)

There is n+1 leafs in a binary tree where n is the number of nodes. Sorry for the absurdity question...

!o)

EDIT: In fact, in a BSP tree, we must to minimize the number of polygons of the leafs.


[edited by - Chuck3d on April 16, 2004 5:51:05 AM]

You are wrong in saying that choosing a polygon so that all other polygons are on one side only will minimize the number of cuts : cutting occurs when a polygon is on both sides of the separation plane, it has nothing to do with the side of the plane non-cut polygons are on.

Your best bet would be to set two goals in your sparation plane choice method : have a heuristic that chooses the plane depending on both the tree unbalance it causes and the number of cuts it causes.

Victor Nicollet, INT13 game programmer