Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

OBB Trees.

43 views
Skip to first unread message

A.K

unread,
Jun 5, 1998, 3:00:00 AM6/5/98
to

Hi there, I am trying to do collisions and the like for a game I am writing
at the moment. I was talking to someone and they
mentioned OBB trees might be the thing to use for the cars. I tried looking
on the net but couldn't find anything on them.
Does anyone have an references I can look up, source, description of the
structure of them etc.
Are they actually any good for car-car collisions?. I'd obviously need
plane information (normals) our of the algorithm etc.

Cheers.
Aaron


Roland B. Hougs

unread,
Jun 6, 1998, 3:00:00 AM6/6/98
to

I found a paper on OBB Trees ("OBB-Tree: A hierarchical structure for
rapid interference detection" by Gottschalk/Lin/Manocha) on UNC's
"Walkthru Project" pages:

http://www.cs.unc.edu:80/~walk/papers/index.html


Hope this helps...

Roland
(To reply replace ALL underscores by dots in the address)
Any views expressed are strictly my own.

Dave Eberly

unread,
Jun 7, 1998, 3:00:00 AM6/7/98
to

A.K wrote in message <01bd9055$0ebf9b60$27f0d4cf@aza166>...


>Hi there, I am trying to do collisions and the like for a game I am writing
>at the moment. I was talking to someone and they
>mentioned OBB trees might be the thing to use for the cars. I tried looking
>on the net but couldn't find anything on them.
>Does anyone have an references I can look up, source, description of the
>structure of them etc.
>Are they actually any good for car-car collisions?. I'd obviously need
>plane information (normals) our of the algorithm etc.


Proceedings of SIGGRAPH 96, paper by Gottschalk et al. on OBB trees.
Code for computing if two OBBs intersect (and each OBB can have a
velocity, so you get dynamic collision testing with this) is
http://www.cs.unc.edu/~eberly/gr_intr.htm, collide.* files. A simple OBB
construction from a set of points is the page gr_cont.htm (obb.*). This
is not as sophisticated as Gottschalk's algorithm whereby he uses triangle
areas and centroids to get a better fit. Minimum volume OBBs is minbox3.*.

I am planning on putting code at the site in a link "collision detection".
This
will include the hierarchy construction. The abstract algorithm is to take
a
collection of points ordered as a triangle mesh and compute an OBB. Split
the triangles into two submeshes. For each submesh, build an OBB.
Recursively you get a binary tree of OBBs. At each leaf nodes you should
have
a single triangle. In the Gottschalk paper, the OBBs are built by
constructing a
covariance matrix. The eigenvectors of that matrix are used as box axes.

Given two OBB trees, you compare top level boxes. If they do not intersect,
the objects do not intersect. If they do intersect, recurse down one tree
and
compare to the top level OBB of the other. If you get to a leaf node of the
first tree, you can start recursing on the other tree.

Dave Eberly
ebe...@cs.unc.edu


Adrian J. Chung

unread,
Jun 7, 1998, 3:00:00 AM6/7/98
to

Dave Eberly <ebe...@cs.unc.edu> wrote:
> Given two OBB trees, you compare top level boxes. If they do not
> intersect, the objects do not intersect. If they do intersect,
> recurse down one tree and compare to the top level OBB of the other.
> If you get to a leaf node of the first tree, you can start recursing
> on the other tree.

Is this traversal the most efficent algorithm?

Let's say I build one OBB-tree for a pigeon model, call it treeA.

I construct another OBB-tree for an oil refinery (and we're talking
lot's of pigeon-sized pipes here) which spans over a kilometer. Call
this treeB.

I want to do collision detection for a pigeon flying through a
refinery.

1) The naive way

Descend down treeA all the way to the leaves before descending treeB.
Unfortunately the pigeon may be sitting on a pipe located somewhat
central to the refinery, so all leaves of treeA overlap the root box
of treeB. For each of these leaves we now recurse over treeB. This
negates all the advantages of having OBB treeA.

2) Slightly smarter way (but still naive)

Descend treeB before descending treeA. Note that some components of
the oil refinery (nuts, bolts & screws) are smaller than the pigeon.
It so happens our pigeon is flying by a bunch of screws in the middle
of the oil refinery. So we have a similar situation occuring as
before but at a smaller scale and with roles reversed. We end up
testing lots of leaves of treeB against the whole of treeA.

3) Compare box sizes

Test for intersection with children of the larger parent. At some
point in the recursion we have just determined that boxA from treeA
overlaps boxB from treeB. If boxA is larger than boxB we do recursive
intersection tests between boxB and each child of boxA. (And vice
versa.) The size metric used to compare boxes could be volume or
something as simple as miximum length over the three dimensions.

This definitely avoids the degenerate behaviour but I haven't seen
this algorithm described formally in any publication. I'm using this
in my work and need a reference, so could anyone volunteer the info
(in bibtex, please) ?

4) Descend both at same rate (synchronised descent)

If sizes of bounding volumes at each level are fixed in advance we can
avoid size comparisons altogether and just descend both trees in
lock-step or alternating between them. The root nodes over all trees
are all the same size, their children are of like size, and their
children are all the same size, etc. This is used in some sphere-tree
collision detection code.

For the pigeon/refinery example this introduces a lot of loose
bounding nodes on top of the pigeon's tree. This can be dispensed
with and the algorithm coded to descend the largeer tree an appropriate
number of times before commencing the synchronised descent.

5) Overlap-region-dependent size testing

Deciding which tree to descend next depends not only on the relative
sizes of the current potentially intersecting nodes, but also on their
positions relative to each other. For most collision detection
applications this optimisation finds no use as bounding volumes are
typically isotrophic (that is, extend equally in all directions) as is
the placement of the descendant nodes.

Suppose the bounding scheme allows for long thin OBB's (like the
obelisk in 2001), tapered volumes (cones, pyramids) and perhaps even
non-convex shapes (hour-glasses, donuts, etc). Additionally the
placement of the child nodes is known to be restricted (e.g. lies in a
plane, or along one line) with this infomation being assumed or
annotated in the parent. Things start to get really complicated and I
have yet to find much research in this area. It does have potential
application in bounding hierarchies for nearly-parallel rays for use
in visibility algorithms.

One related scheme in which the overlap region influences the next
recursion is the S-box mechanism. Descendant nodes are culled against
the overlap region and any that survive are tested against their
counterparts from the second hierarchy. S-boxing is easier to do with
axis-aligned boxes though.


--
Adrian

Dave Eberly

unread,
Jun 7, 1998, 3:00:00 AM6/7/98
to

Adrian J. Chung wrote in message <6le9nu$ef9$1...@magpie.doc.ic.ac.uk>...


>Dave Eberly <ebe...@cs.unc.edu> wrote:
>> Given two OBB trees, you compare top level boxes. If they do not
>> intersect, the objects do not intersect. If they do intersect,
>> recurse down one tree and compare to the top level OBB of the other.
>> If you get to a leaf node of the first tree, you can start recursing
>> on the other tree.
>
>Is this traversal the most efficent algorithm?

<snip - lots of good variations on traversal>

How to traverse the trees most effectively will depend on the data sets, as
you noticed. My post was just to get the basic idea across. In the game
engine I work on, the traversal is a lot smarter. For very large data sets,
a good idea is not to treat the data set as a single object. For something
like your example of an oil refinery, you can break the data set up with an
octree decomposition (or "cells" or whatever). For animated characters
moving through a scene, this type of decomposition makes sense in that you
can localize which objects the character can interact with. For each cell,
you can build an OBB tree. The size of the trees is therefore kept to a
reasonable size. I also have some tuneable parameters. One is to specify
how many triangles per OBB leaf. While the Gottschalk algorithm assumes 1,
there is usually not a need for that accuracy in a game (you don't need to
do triangle-triangle tests). Another parameter is how many levels to
descend in the OBB tree.

At any rate, your nicely written post indicates that a "production-level"
collision detection system is not simply an implementation of building OBBs
and a tree and doing a simple comparison. It takes a lot of work to get it
right for your application(s).

Dave Eberly
ebe...@cs.unc.edu


A.K

unread,
Jun 8, 1998, 3:00:00 AM6/8/98
to

> Proceedings of SIGGRAPH 96, paper by Gottschalk et al. on OBB trees.
> Code for computing if two OBBs intersect (and each OBB can have a
> velocity, so you get dynamic collision testing with this) is
> http://www.cs.unc.edu/~eberly/gr_intr.htm, collide.* files. A simple OBB

Thanks Dave. I looked at the stuff and I think I need to learn some more
mathematics! :-)
Should be able to do soemthing with it though!

Cheers.
Aaron


0 new messages