Continuous GJK for spherically extended objects

Please don't post Bullet support questions here, use the above forums instead.
Post Reply
Adrian Lopez
Posts: 10
Joined: Thu Jan 21, 2010 7:07 pm

Continuous GJK for spherically extended objects

Post by Adrian Lopez »

Is there a way to perform a ray cast as described in Gino Van Den Bergen's Ray Casting against General Convex Objects, against spherically extended objects without having to calculate support points for the enlarged objects? With GJK you can adjust the termination condition to account for the slightly expanded objects, but what about Gino's ray cast algorithm?

Specifically, would adjusting this (from page 11):

Code: Select all

while (v.squaredMagnitude() > epsilon*epsilon) {...}
To read like this:

Code: Select all

while (v.squaredMagnitude() > epsilon*epsilon + margin) {...}
... be enough to produce results equivalent to a ray cast against the CSO of a pair of spherically extended objects?

The goal is to use Gino's ray cast algorithm to determine collision time, and regular GJK (without EPA) to determine witness points and collision normals for the [near] collision. I'd rather avoid computing support points for the expanded objects if possible.
gino
Physics Researcher
Posts: 22
Joined: Mon Jun 27, 2005 9:28 am
Location: Helmond, Netherlands
Contact:

Re: Continuous GJK for spherically extended objects

Post by gino »

Adrian Lopez wrote:Is there a way to perform a ray cast as described in Gino Van Den Bergen's Ray Casting against General Convex Objects, against spherically extended objects without having to calculate support points for the enlarged objects? With GJK you can adjust the termination condition to account for the slightly expanded objects, but what about Gino's ray cast algorithm?

Specifically, would adjusting this (from page 11):

Code: Select all

while (v.squaredMagnitude() > epsilon*epsilon) {...}
To read like this:

Code: Select all

while (v.squaredMagnitude() > epsilon*epsilon + margin) {...}
... be enough to produce results equivalent to a ray cast against the CSO of a pair of spherically extended objects?

The goal is to use Gino's ray cast algorithm to determine collision time, and regular GJK (without EPA) to determine witness points and collision normals for the [near] collision. I'd rather avoid computing support points for the expanded objects if possible.
Hi Adrian,

It would be enough if you only need to know whether the ray hits the convex or not. However, most of the time you need to have the earliest time the ray hits the object as well as the normal at the hit point. By performing GJK on the "bone" objects (without dilation) you will step into the dilated object before you trigger termination, which means that both your time of impact and your contact normal are wrong. In order to advance conservatively, the best thing I can think of right now is to generate support points on the dilated object. This means that you'll need to compute the reciprocal of a square root in each iteration, which is a pity. I recall having given this issue some thought a while back and this was the best I could come up with.

If you find something better, I'd be happy to discuss it with you.

Regards,

Gino
Post Reply