Collision of Spheres

[Vijay Patil]

Hi

I am trying to implement simple collision detection using OSG. Just
few balls/spheres enclosed in a closed box colliding with each other
and deflecting.
Since the objects are spheres, I used BoundingSphere objects to detect
collision.

I expect the bounding sphere to coincide with actual spherical object,
so collision should be accurate, That's where I face the problem. The
the collision is being detected (intersects true) some distance
*before* balls actually touch with each other. I want it to detect the
collision (intersects true) when they touch with each other. Is there
anything I might be missing ? Following is relevant segment of the
code.

/* Check for intersection of one object with every other. */
for(int i = 0; i < (int)carlist.size(); i++) {
for(int j = i+1; j < (int)carlist.size(); j++) {

/* Use pointer to MatrixTransform to obtain bound
objects. */
const osg::BoundingSphere& bs1 = carlist[i]->mt->getBound();
const osg::BoundingSphere& bs2 = carlist[j]->mt->getBound();

if(bs1.intersects(bs2)) {
/* Collision detection. Simply reverse direction. */
carlist[i]->dx = -carlist[i]->dx;
carlist[i]->dz = -carlist[i]->dz;
carlist[j]->dx = -carlist[j]->dx;
carlist[j]->dz = -carlist[j]->dz;
}
}
}

Attached is complete code listing.

[Jean-Sébastien Guay]

Hello Vijay,

Post by Vijay Patil
I expect the bounding sphere to coincide with actual spherical object,

I haven't looked at the code specifically, but I think this is the
assumption which turns out to be false. The Drawables have bounding
boxes, and then the Geodes containing them have bounding spheres which
are built to encompass the Drawables' bounding boxes. Hence, the Geode's
bounding sphere will be larger than the original sphere because it has
to encompass the sphere's bounding box, which has to encompass the
sphere itself.

I hope this makes sense. If not, draw it on a piece of paper: draw a
circle (which is your graphical object), then draw the smallest box that
encompasses this circle, and then draw the smallest circle that
encompasses that box. The second circle will inevitably be larger than
the first one.

It's also pretty easy to make a visitor that will add a graphical
representation of all bounding volumes of a scene.

Hope this helps,

J-S

[Paul Martz]

Post by Jean-Sébastien Guay
I haven't looked at the code specifically, but I think this
is the assumption which turns out to be false. The Drawables
have bounding boxes, and then the Geodes containing them have
bounding spheres which are built to encompass the Drawables'
bounding boxes. Hence, the Geode's bounding sphere will be
larger than the original sphere because it has to encompass
the sphere's bounding box, which has to encompass the sphere itself.

J-S is right here. But, there is a ShapeVisitor class and a
ConstShapeVisitor class that you can use to create a more accurate bounding
sphere, as in the code below... (Coding this off the top of my head, so
forgive typos, thanks.)
-Paul

class SphereBoundVisitor : public osg::ConstShapeVisitor
{
public:
SphereBoundVisitor() {}
virtual ~SphereBoundVisitor() {}

virtual void apply( const osg::Shape& s )
{
osg::notify( osg::WARN ) << "Unknown shape." << std::endl;
}
virtual void apply( const osg::Sphere& s )
{
osg::notify( osg::INFO ) << "Found Sphere." << std::endl;

osg::Vec3 c = s.getCenter();
float radius = s.getRadius();
_bs = osg::BoundingSphere( c, r );
}

osg::BoundingSphere _bs;
};

[Vijay Patil]

Thank you Paul for your inputs.

Post by Paul Martz

Post by Jean-Sébastien Guay
I haven't looked at the code specifically, but I think this
is the assumption which turns out to be false. The Drawables
have bounding boxes, and then the Geodes containing them have
bounding spheres which are built to encompass the Drawables'
bounding boxes. Hence, the Geode's bounding sphere will be
larger than the original sphere because it has to encompass
the sphere's bounding box, which has to encompass the sphere itself.

J-S is right here. But, there is a ShapeVisitor class and a
ConstShapeVisitor class that you can use to create a more accurate bounding
sphere, as in the code below... (Coding this off the top of my head, so
forgive typos, thanks.)
-Paul
class SphereBoundVisitor : public osg::ConstShapeVisitor
{
SphereBoundVisitor() {}
virtual ~SphereBoundVisitor() {}
virtual void apply( const osg::Shape& s )
{
osg::notify( osg::WARN ) << "Unknown shape." << std::endl;
}
virtual void apply( const osg::Sphere& s )
{
osg::notify( osg::INFO ) << "Found Sphere." << std::endl;
osg::Vec3 c = s.getCenter();
float radius = s.getRadius();
_bs = osg::BoundingSphere( c, r );
}
osg::BoundingSphere _bs;
};
_______________________________________________
osg-users mailing list
http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org

This gives me a simpler idea. Since I am storing x, y, z co-ordinates
of the sphere is external ( to SG) objects (Car objects). I could just
use/access that information to create BoundingSphere objects of
desired center and radius, as following code demonstrates:

/* Check for intersection of one object with every other. */
for(int i = 0; i < (int)carlist.size(); i++) {
for(int j = i+1; j < (int)carlist.size(); j++) {

/* Use pointer to MatrixTransform to *create*
bound objects. */
osg::Vec3d c1(carlist[i]->x, 0.0, carlist[i]->z);
osg::BoundingSphere bs1(c1, RAD);

osg::Vec3d c2(carlist[j]->x, 0.0, carlist[j]->z);
osg::BoundingSphere bs2(c2, RAD);

if(bs1.intersects(bs2)) {
/* Collision detection. Simply reverse direction. */
carlist[i]->dx = -carlist[i]->dx;
carlist[i]->dz = -carlist[i]->dz;
carlist[j]->dx = -carlist[j]->dx;
carlist[j]->dz = -carlist[j]->dz;
break;
}
}
}


I tried this and it's working fine. Attached is complete code listing.
Next step for me would to study physics behind "elastic collision" and
implement correct deflection.

[Vijay Patil]

Hi J-S

Thanks for you reply.

On Wed, Sep 3, 2008 at 6:26 PM, Jean-Sébastien Guay

Post by Jean-Sébastien Guay
Hello Vijay,

Post by Vijay Patil
I expect the bounding sphere to coincide with actual spherical object,

I haven't looked at the code specifically, but I think this is the
assumption which turns out to be false. The Drawables have bounding boxes,
and then the Geodes containing them have bounding spheres which are built to
encompass the Drawables' bounding boxes. Hence, the Geode's bounding sphere
will be larger than the original sphere because it has to encompass the
sphere's bounding box, which has to encompass the sphere itself.

You are right, my assumption was wrong. I briefly looked at the
relevant OSG source code. Since 'class MatrixTransform' is derived
from 'class Group', I studied Group::computeBound(). Indeed, we are
iterating over all children and calling 'getBound' on them. If a
Drawable object is a child then of course call to getBound will return
a BoundingBox object, which is expanded further (i.e enclosed in a

Following is relevant code:

Group.cpp, BoundingSphere Group::computeBound()

for(itr=_children.begin();itr!=_children.end(); ++itr)
{
const osg::Transform* transform = (*itr)->asTransform();
if (!transform ||
transform->getReferenceFrame()==osg::Transform::RELATIVE_RF)
{
bsphere.expandRadiusBy((*itr)->getBound());
}
}

So when I call getBound on MatrixTransform object, spherical shape
will be enclosed in a bounding box, which in turn will be enclosed in
final bounding sphere. This is what caused the problem.

Also after calling getBound, Drawable objects returning a BoundingBox
(instead of BoundingSphere) object is just a design decision, right?
Is there anything that prevents us in having a BoundingSphere for
Drawable objects?

Post by Jean-Sébastien Guay
I hope this makes sense. If not, draw it on a piece of paper: draw a circle
(which is your graphical object), then draw the smallest box that
encompasses this circle, and then draw the smallest circle that encompasses
that box. The second circle will inevitably be larger than the first one.
It's also pretty easy to make a visitor that will add a graphical
representation of all bounding volumes of a scene.

Yes I think so. IIRC there was a thread with lots of attachment about
this. Will look into it.

Thanks again.

[Jean-Sébastien Guay]

Hello Vijay,

Post by Vijay Patil
Also after calling getBound, Drawable objects returning a BoundingBox
(instead of BoundingSphere) object is just a design decision, right?
Is there anything that prevents us in having a BoundingSphere for
Drawable objects?

The bounding volumes OSG maintains in every Node and Drawable are there
to facilitate view frustum culling. A bounding box will generally fit
closer to an object than a bounding sphere (one exception being if the
object itself is a sphere :-) ) but also costs more to test for
inclusion within the view frustum.

So the idea is that any Group's bounding sphere includes the bounding
volumes of all its children, and any Geode's bounding sphere includes
the bounding boxes of all its Drawables. While traversing the graph in
the cull traversal, the Nodes (Groups and Geodes in this example) will
be tested for inclusion in the view frustum. Since it's a sphere/frustum
test, it's pretty quick. When the test passes, the children are examined.

Once we get to a Geode and the test still passes, we want to have a
better test to make sure we aren't drawing Drawables for nothing. Since
the drawing cost is relatively high in general, it makes sense to use a
slightly more costly test and potentially avoid the high cost of drawing
the Drawable. So this is where the Drawable's bounding box is tested
against the frustum. If this final test passes, the Drawable will be put
in the render graph to be rendered in the draw traversal.

I hope this explains the general rationale for the presence of bounding
spheres on Nodes and bounding boxes on Drawables. Note that I took some
shortcuts in explaining it, but it should make it clearer.

Please see Paul's followup to my message which gives you a way of
creating a bounding sphere from your Sphere which will be identical to
the original object.

Hope this helps,

J-S