# designing a robust and flexible bounding volume system

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

## Recommended Posts

I am developing the foundation for a FPS game. In order to speed up view frustum culling and perhaps collision detection, I am going to represent the scene as a tree of bounding volumes. Hence the root node will be a node with a BV that encloses the entire scene. After that the tree will be defined by the rule that a parent completely encloses all its children, and that no object in the scene can have more than one parent. Basically I am going to make a height adjusted quadtree...but thats not the point of this post. So I want my bounding volumes to derive from some ABC, so I can throw them around without caring if they are spheres, AABBs, OBs, lozenges...whatever. I want to be able to say something like if( BoundingVolume1.intersects( boundingVolume2 ) ) // etc... The problem is that the math is different depending on what type of BVs are being used. What I was going to do is use a simple RTTI system so that the intersects() method would do something like this: bool SomeDrivedBoundingVolume::intersects( BoundingVol b ) { if( b.isInstanceOf( BVSphere ) ) { /* sphere intersection test with whatever *this is */ } if( b.isInstanceOf( BVLozenge ) ) { /* lozenge test against this shape... */ } } etc. Is there a better way to do this. Dynamic typecasting like this is usually frowned upon by oop programmers. And I want my engine to be clean and academic :) Thanks guys, I hope you could understand that as I have a beer and programming related headache right now. ~Rob

##### Share on other sites
mictian,

As you've pointed out, the code to perform intersection testing between the different types of objects is unique. ie, collision between a box and a sphere is different than two boxes, etc...

For this reason, having a common base class and using a common interface doesnt gain you anything, because you'd still have to write the intersection code inside of the intersect function. example:

//assume the following
class shape;
class cube : public shape;
class sphere : public shape:

Now, I could write this:

class hull : public shape{public:    bool Intersects( shape* pShape );}bool hull::Intersects( shape* pShape ){    if( pShape->IsA( "cube" ) )    {        ...    }    else if( pShape->IsA("sphere") )    {        ...    }}

As you can see, the only thing you've accomplished is having a single, large function with potentially a dozen if/else statements. Better would just be to do this

class hull : public shape{public:    bool Intersects( const cube& cube );    bool Intersects( const sphere& cube );}

With the above, each intersection is well defined in its own function. This will make it easier to unit test. As well, you can provide default intersections inside the base class shape. For example, a simple point intersection test.

As well, you can make class shape an abstract class. Make each of its intersections pure virtual, which will force you to add intersection tests for all classes whenever you add a new type of "shape".

These are primarily opinions but I've found in general, for the purpose of testing, as well as debugging that its better to keep your functions small - especially when dealing with things such as intersection testing.

##### Share on other sites
This way though, I cant just pass shape pointers around, each node in my BV tree will have to know what kind of object it contains, and then cast that before passing it to the intersection fincrion...right?

~Rob

##### Share on other sites
Quote:
 Original post by mictianIs there a better way to do this. Dynamic typecasting like this is usually frowned upon by oop programmers. And I want my engine to be clean and academic :)

What your looking for is multi-methods, dynamic dispatch on more than one polymorphic type. In your case the dispatch is on two so its referred to as double dispatch.

The problem is languages such as C++ do not support multiple dynamic dispatch natively, they only support single dynamic dispatch.

You have two choices in the matter, using some form of the visitor design pattern or use a library which implements multi-methods in your language, i'm assuming your using C++ so i would suggest you look into the Loki library, it has generic visitors and also a generic multi-methods package.

I have to say how ever BVH or scene graphs augmented as BVH are typically not implementated with different types of BVs at the same time except maybe a different one use in model space but all internal nodes & leafs typically use the same bounding volume type. At the end of the day you want to cull out branches as quickly as possiable.

##### Share on other sites
Thanks.

Well my scene is going to be a tree of AABBs for the most part. But inside the leaf nodes (where the geometry is) I want to have as efficient containment as possible so that I can use it for collision detection .

##### Share on other sites
do like

class CollisionThing
{
virtual bool collides(CollisionThing ) = 0;
virtual bool collidesRect(Rect) = 0;
virtual bool collidesCircle(circle) = 0;
};

class CollisionCircle : public CollisionThing
{
collides(shape) { return shape.collidesCircle(this); }
collidesCircle() { do circle circle code here }
collidesRect() { do rect circle code here; }
};

class CollisionRect: public CollisionThing
{
collides(shape) { return shape.collidesRect(this); }
collidesCircle() { do circle Rect code here }
collidesRect() { do rect rect code here; }
};

class BigThing : public CollisionThing
{
bool collides(shape) {
if ( shape.collidesRect(legs) || shapes.collidesCircle(arms) )
blah.....
}
Rect legs;
Circle arms;
}

[code/]

1. 1
2. 2
JoeJ
20
3. 3
frob
20
4. 4
5. 5

• 10
• 11
• 12
• 13
• 9
• ### Forum Statistics

• Total Topics
632212
• Total Posts
3004819

×