BSP Tree Balancing
Scott Le Grand
on a series of non-convex spaceship models designed for a video
game. I am finding that I end up with 7 to 8 times as many faces
as I started with after processing them. It appears that what
happens is that the initial steps divide the faces up almost
evenly (as evenly as can reasonably be expected), but when a node
is down to 3-5 faces, all hell breaks loose with lots of face
splits. Since these BSP Trees will be used for collision detection,
it is vital for me to get them as balanced as possible so that
the whole process is as lose to log n as I can get it...
So, I am asking if anyone knows of any references on balancing
BSP Trees other than the cursory treatment of Thibbault and Naylor
in Computers Graphics 21:153-162 which is great but I cannot believe
this is the only work done on this problem since 1987...
At each step of tree construction, I currently find the median of all the
vertices in a half space and then pass a series of randomly oriented planes
through the median, and then select for the plane which most evenly divides
the remaining polygons (5000 random trials)...
This does not seem like a problem amenable to annealing or genetic algorithms,
but might be suitable for a heuristic tree search of some sort... So,
has anyone tried anything?
Scott
Juri Munkki
>Hi, I've just written my first BSP Tree creator. I am testing it
>on a series of non-convex spaceship models designed for a video
>game. I am finding that I end up with 7 to 8 times as many faces
>as I started with after processing them. It appears that what
>happens is that the initial steps divide the faces up almost
>evenly (as evenly as can reasonably be expected), but when a node
>is down to 3-5 faces, all hell breaks loose with lots of face
>splits. Since these BSP Trees will be used for collision detection,
>it is vital for me to get them as balanced as possible so that
>the whole process is as lose to log n as I can get it...
If you the models are indeed spaceships, I doubt that collision
detection at polygon level will be the limiting factor in your
game. In space most collision tests can be done with bounding
volumes (spheres and/or boxes) before you need to use polygons.
For rendering purposes, I always go for the minimum amount of
polygons and usually end up with around 30% more, although of
course convex shapes introduce 0 splits (and a totally unbalanced
tree).
>At each step of tree construction, I currently find the median of all the
>vertices in a half space and then pass a series of randomly oriented planes
>through the median, and then select for the plane which most evenly divides
>the remaining polygons (5000 random trials)...
I think you could improve on this, if you chose a random edge and a vertex
and use the three points to define the plane. Use the best balanced split
and try to minimize the amount of split polygons too (weigh these too
parameters with some formula). I think that even a 1:3 division with very
few split polygons would be far better than a close to 1:1 division that
creates a large number of new polys.
>This does not seem like a problem amenable to annealing or genetic algorithms,
>but might be suitable for a heuristic tree search of some sort... So,
>has anyone tried anything?
I think you are trying too hard to find the most balanced tree.
--
Juri Munkki jmu...@hut.fi There ain't no such thing as a shareware lunch.
http://www.hut.fi/~jmunkki Windsurfing: Faster than the wind.
Scott Le Grand
> In article <3tlko1$j...@saba.info.ucla.edu> leg...@localhostmbi.ucla.edu (Scott Le Grand) writes:
> >Hi, I've just written my first BSP Tree creator. I am testing it
> >on a series of non-convex spaceship models designed for a video
> >game. I am finding that I end up with 7 to 8 times as many faces
> >as I started with after processing them. It appears that what
> >happens is that the initial steps divide the faces up almost
> >evenly (as evenly as can reasonably be expected), but when a node
> >is down to 3-5 faces, all hell breaks loose with lots of face
> >splits. Since these BSP Trees will be used for collision detection,
> >it is vital for me to get them as balanced as possible so that
> >the whole process is as lose to log n as I can get it...
>
> If you the models are indeed spaceships, I doubt that collision
> detection at polygon level will be the limiting factor in your
> game. In space most collision tests can be done with bounding
> volumes (spheres and/or boxes) before you need to use polygons.
Alas it will be the limiting factor at the very worst time... I have capitol
ships you can literally fly through hunting for weak spots and they are very
non-convex... I cannot think of a way to use bounding volumes for
these irregularly shaped beasts... They're mini Doom levels at
some times... But lots of fun...
> For rendering purposes, I always go for the minimum amount of
> polygons and usually end up with around 30% more, although of
> course convex shapes introduce 0 splits (and a totally unbalanced
> tree).
Ok, it seems like the speed of BSP collision detection is dependent on the number
of sub-spaces one can encounter (each one spawning two tests), so it would
seem best to minimize this...
> >At each step of tree construction, I currently find the median of all the
> >vertices in a half space and then pass a series of randomly oriented planes
> >through the median, and then select for the plane which most evenly divides
> >the remaining polygons (5000 random trials)...
>
> I think you could improve on this, if you chose a random edge and a vertex
> and use the three points to define the plane. Use the best balanced split
> and try to minimize the amount of split polygons too (weigh these too
> parameters with some formula). I think that even a 1:3 division with very
> few split polygons would be far better than a close to 1:1 division that
> creates a large number of new polys.
Great idea! Will try it... My effort of the day was to go for maximum
balancing until a branch contained 8 or fewer polygons and then switch
to minimizing the number of splits, but I was not happy with the depth
of these beasts...
> >This does not seem like a problem amenable to annealing or genetic algorithms,
> >but might be suitable for a heuristic tree search of some sort... So,
> >has anyone tried anything?
>
> I think you are trying too hard to find the most balanced tree.
As usual :-)... I come from a background ion optimization... I see far
too many things as fitness functions...
Scott
Tim Sweeney
When picking a splitter polygon, rank all polygons based on a
function like this:
Score =
(
(FLOAT)Balance * (FLOAT)(OurAbs(Front-Back)) +
(FLOAT)(100-Balance) * (FLOAT)Splits
);
Where:
Balance = 0-100, tendency to balance tree rather than minimize cuts,
15-25 works well.
Front = polygons in front
Back = polygons in back
Splits = polygons split
For typical complex objects, the polygon count only increases
by 20-30% after BSP'ing.
-Tim Sweeney, Epic MegaGames, Inc.
Jon Beltran de Heredia
: When picking a splitter polygon, rank all polygons based on a
: function like this:
: Where:
--
-----------------------------------------------------
Jon Beltran de Heredia - Yann/Iguana
-----------------------------------------------------
Bretton Wade
you might need to balance your tree. I'll be working on it some more in
the next couple of months, after I finish my thesis =).
--
Bretton Wade (bw...@graphics.cornell.edu)
http://www.graphics.cornell.edu/~bwade/
Gerald Gutierrez
check any algorithms book on AVL trees. What's presented should be
adaptable to your particular applications.
--
`'`'`'`'`'`'`'`'`'`'`'`'`'`'`'`'`'`'`'`'`'`'`'`'`'`'`'`'`'`'`'`'`'`'`'`'`'
Gerald Gutierrez Computer Engineering
Faculty of Applied Science
gut...@unixg.ubc.ca University of British Columbia
Doug Nadel
>Regarding BSP tree balancing : For an algorithm to balance binary trees,
>check any algorithms book on AVL trees. What's presented should be
>adaptable to your particular applications.
I just bought Knuth vol3 for the AVL algorithms today, but he does not have
any examples of the algorithm for deleting a node. It's left as a exercise for
user, so to speak. Does any one know of an Internet source, or published
book that explicitly details the AVL deletion algorithm?
Thanks,
Doug Nadel
R. Ethan Rohrer
Doug Nadel <na...@ibm.net> wrote:
>In <3uoqcg$5...@nnrp.ucs.ubc.ca>, gut...@unixg.ubc.ca (Gerald Gutierrez) writes:
>>Regarding BSP tree balancing : For an algorithm to balance binary trees,
>>check any algorithms book on AVL trees. What's presented should be
>>adaptable to your particular applications.
Hello,
I was just wondering:
I had thought about applying a balancing algorithm to BSP trees, but
had given the idea up, because a BSP tree seems to depend on the order
in which you choose the splitting polygons. (forgive me, its been a while
since I have put much thought into this idea).
The algorithm I thought of applying was that of Balanced Binary Search
Trees (BBST's), which seem to be, in some way, related to AVL trees.
Anyway, the algorithm required a 'rotation' of nodes (or subtrees) in
some cases. After some inspection, I thought that the rotations destroyed
the relationships defined by the BSP tree. Not only does the left/right
relationship of the tree define front/back subspaces, but a subtree defines
a particular region of space. By rotating nodes, the shape of that subspace
changes, and (it seemed at the time), could contradict the previous
relationships. (the splitting polygons at lower levels in the tree
tend to be small portions of polygons used at higher levels)
I know that didn't seem too coherent, but can anyone confirm or
deny my fears that an adjusted BSP tree may not be the same as the
original? If the response is denial, can you define the algorithm
for balancing the BSP tree?
Thanks,
Ethan "finally-about-to-embark-on-implementing-a-true-3d-engine" Rohrer
r...@wlbr.iipo.gtegsc.com
Wilco Dijkstra
>Hello,
>
>I was just wondering:
>
>I had thought about applying a balancing algorithm to BSP trees, but
>had given the idea up, because a BSP tree seems to depend on the order
>in which you choose the splitting polygons. (forgive me, its been a while
>since I have put much thought into this idea).
>
>The algorithm I thought of applying was that of Balanced Binary Search
>Trees (BBST's), which seem to be, in some way, related to AVL trees.
>Anyway, the algorithm required a 'rotation' of nodes (or subtrees) in
>some cases. After some inspection, I thought that the rotations destroyed
>the relationships defined by the BSP tree. Not only does the left/right
>relationship of the tree define front/back subspaces, but a subtree defines
>a particular region of space. By rotating nodes, the shape of that subspace
>changes, and (it seemed at the time), could contradict the previous
>relationships. (the splitting polygons at lower levels in the tree
>tend to be small portions of polygons used at higher levels)
>
>I know that didn't seem too coherent, but can anyone confirm or
>deny my fears that an adjusted BSP tree may not be the same as the
>original? If the response is denial, can you define the algorithm
>for balancing the BSP tree?
>
>Thanks,
>Ethan "finally-about-to-embark-on-implementing-a-true-3d-engine" Rohrer
>r...@wlbr.iipo.gtegsc.com
Yes, your worst fears come out: AVL balancing is of no use for building BSP
trees...
There have been numerous postings about BSP balancing (some from me), but I'll
try to explain BSP tree balancing shortly - as I use it currently:
Do NOT try to balance by picking a polygon which divides the scene in two equal
parts. This will introduce lots of splits, so your tree will be bigger (and
deeper..). The trick is to see that you NEVER need a 50%-50% balance in every
node. A 10%-90% balance is GOOD enough, and still gives a tree depth of log (N).
The first concern is to pick a polygon which doesn't split too much polygons. Then
for polygons which split an equal number of polygons, choose the one that gives
the
best balanced tree. (So you reject 1%-99% splits) When you need really good
balancing, you might even reject some free cuts (because free cuts tend to be on
the outside of objects, and thus give bad splits - typically with zero polygons in
one leaf) How important balancing is, depends on your application. For
ray-tracing,
you might need a very balanced tree, but in most 3D applications, you draw the
whole BSP-tree, so balancing has no real use. Balancing might be handy when you
use it for culling a world database with BSP, or for collision detection (but this
can be done much faster by using a degenerate object describing only the shape
of the object you are testing).
--
====================================================================
Name : Wilco Dijkstra
Email : csg...@cs.rug.nl
Status : Student IT (about to graduate), ARMPowered
Expertise: Optimisation, 2D/3D graphics, compression, programming,
compiler writing, developing algorithms.
Interests: Operating systems, programming languages, computer
architecture, hardware design, software engineering.
====================================================================