Bounding Volume Trees in C++

This isn’t exactly an OpenGL question, but I know a lot of the people here have poked around with game engines, so I thought maybe someone had run into this before.

As indicated, I’m working on a physics engine in C++. I want to be able to build a tree of bounding volumes for my objects and test intersections between these bounding volumes. I would also like to be able to use different types of volumes in the same tree (i.e. bounding spheres and bounding boxes in the same tree). I’m an experienced C++ programmer, so this is a rather embarrassing question, but I can’t figure out a good way to do this!

My initial thought was to have Sphere and Box classes. Of course, to stick them in the same tree, they’ll both have to have a common base class. When I test for pairwise overlaps through the base class is where the problems come up. For instance, suppose I have two tree nodes, node1 and node2. What I would like to have is a boolean function that returns whether they overlap. Like node1.testOverlap(node2). It doesn’t have to be a member function, though, I would be happy with testOverlap(node1, node2).

Here’s my question: If the testOverlap function is a member of the derived classes, it must be present in the base class as a virtual function. Unfortunately, this requires me to put references to Box and Sphere in the base class…I think it’s bad programming practice to have a base class have to “know” about all classes derived from it.

If the testOverlap(a,b) function is not a member (the solution I’d prefer), then I don’t think I can call it from a base class pointer, can I? For instance, I couldn’t call testOverlap(node1, node2) and have it realize node1 is a sphere and node2 is a sphere so it should really call testOverlap(sphere, sphere).

It seems like some of you may have run into a problem like this in the past. If so, or if you have an idea for an elegant solution, I’d really like to hear it. I’m really hoping I don’t have to have a type identifier in each class or do something kludgy like that.

Thanks,

–Zeno

Being an experienced C++ programmer you do what you should do every time you have a problem. Open up your copy of More Effective C++ by Scott Meyers, and go to Item 31 which tells you exactly what you need to know.

If you don’t have a copy, you slap yourself on the wrists for touching a C++ compiler without having read it, and then go to http://cseng.aw.com/book/0,3828,020163371X,00.html to order a copy.

Basically there’s no GOOD way to do it, but he explains about 4/5 ways to do it BAD. Too long to explain anyway about 25 pages.

There’s a CD version of both his books if you’ve got a really nice friend to give you just item 31, but you really should buy it. You won’t regret it.

Hope this helps.

When the problem domain is small, and the
need for efficiency is high, virtual
functions is not necessarily the way to go.
You could store each volume in a union, with
a switch variable at the front for what kind
of volume it is; then use if() to dispatch
to the right testing function.

struct volume {
enum volume_kind kind;
union {
sphere_volume sphere;
box_volume box;
};
};

bool intersects(const volume & a, const volume & b) {
if (a.kind == svSPHERE) {
if (b.kind == svSPHERE) {
return intersects_sphere_sphere(a,b);
}
return intersects_sphere_box(a,b);
}
if (b.kind == svSPHERE) {
return intersects_sphere_box(b,a); // NOTE ORDERING!
}
return intersects_box_box(a,b);
}

See, it doesn’t look so bad, as long as the
problem domain is small, and you can optimize
each of the intersects_ cases well.

Well I’ll be damned Fullon. I went to take a look at the book you mentioned. Not only does it talk about this issue, but it is described in EXACTLY the same context…of pairwise collision checking between objects with the same base class.

After I saw this I immediately purchased the book.

After I read it, I’ll decide between a solution in there and bgl’s.

Thanks guys!

– Zeno

[This message has been edited by Zeno (edited 02-26-2001).]