Sign in to follow this  
mictian

designing a robust and flexible bounding volume system

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by mictian
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 :)


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 this post


Link to post
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 this post


Link to post
Share on other sites
do like
[/code]
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/]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this