Jump to content
  • Advertisement

Archived

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

Chuck3d

binary tree and number of leafs.

This topic is 5181 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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)

Share this post


Link to post
Share on other sites
Advertisement
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]

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!