GJK Ray cast

[kevlar]

I believe that Bullet implements the algorithm in "Ray Casting against General Convex Objects with Application to Continuous Collision Detection" by Gino Van Den Bergen.

I'm now in the process of implementing it as I need to be able to find out the collision point and normal. One thing that I'm slightly confused about though is what the values of s(point) and r(direction) should be. Lets say I have 2 objects A and B, each of which have an acceleration, velocity and position vector associated with them. What do I set the values of s and r to? I've had a quick look at Bullet implementation but it hasn't helped me unfortunately

Thanks.

[Erwin Coumans]

I believe that Bullet implements the algorithm in "Ray Casting against General Convex Objects with Application to Continuous Collision Detection" by Gino Van Den Bergen.

I'm now in the process of implementing it as I need to be able to find out the collision point and normal. One thing that I'm slightly confused about though is what the values of s(point) and r(direction) should be. Lets say I have 2 objects A and B, each of which have an acceleration, velocity and position vector associated with them. What do I set the values of s and r to? I've had a quick look at Bullet implementation but it hasn't helped me unfortunately

Thanks.

Bullet contains 3 implementations for Ray/convex casting, all variations on Brian Mirtichs Conservative Advancement, see
http://www.continuousphysics.com/Bullet ... xCast.html

btGjkConvexCast is the original version by Mirtich, btSubsimplexConvexCast is Gino's contribution mixing the Conservative Advancement loop with GJK loop (just having 1 loop), limited to pure linear motion (good for ray cast and generic convex object sweeps)
btContinuousConvexCollision is my contribution, which includes rotation.
They all operate in different spaces.

Which version are you using?
Erwin

[kevlar]

Then I guess btSubsimplexConvexCast is the one described in this paper?
jgt04raycast.pdf

This is what Bullet does in that class. But what does it all mean?

Code: Select all

SimdVector3 s = -rayFromLocalA.getOrigin();
SimdVector3 r = -(rayToLocalA.getOrigin()-rayFromLocalA.getOrigin());

[dog]

Bullet really is an amazing resource. I wish it had been around when I was first doing this stuff.

But, looking at the referenced code, your version seems a little odd to me. Probably it hasn't been tested much. For instance, I think you need to check for when the simplex is full and flush it, otherwise your GJK class will corrupt (unless I'm reading the code wrong) in some circumstances. Also, you probably only need a time out of 32 not 1000. At least if this code performs the way mine does. And it looks fairly similar.

[Erwin Coumans]

But, looking at the referenced code, your version seems a little odd to me. Probably it hasn't been tested much. For instance, I think you need to check for when the simplex is full and flush it, otherwise your GJK class will corrupt (unless I'm reading the code wrong) in some circumstances. Also, you probably only need a time out of 32 not 1000. At least if this code performs the way mine does. And it looks fairly similar.

There is no overflow: you add points to the voronoi simplex solver, and the 'closest' vector to the origin performs reduction. This implementation is very well tested, in several games and in Blender, for raycasting. Also the mouse picking in the Bullet demos use this code path. In release mode on a modern computer you should be able to do at least 100.000 tests per second (See the Raytracer demo to visualize the Minkowski sum and other GJK shapes).

The safety 'maximum' of 1000 should never be reached. I haven't had the time to analyze typical number of iterations, but usual GJK, who shares the same voronoi simplex solver, has an average in the range 3 to 4.

This is what Bullet does in that class. But what does it all mean?

Code: Select all

SimdVector3 s = -rayFromLocalA.getOrigin();
SimdVector3 r = -(rayToLocalA.getOrigin()-rayFromLocalA.getOrigin());

The 's' is starting point of the ray, in Minkowski space, 'r' is the ray direction. The minus symbols are there, because of the space (Minkowski difference). Basically the raycast is literally casting a point, but the implementation also allows to cast any other convex shape. See the GjkConvexCast demo.

Hope this helps?
Erwin

[dog]

Ah, should have looked at your closest implementation.

3-4 cycles average is typical, but some nasty edge cases can have an oscillation (especially with single precision floats) which is why the time out. I see nothing special in your code that would stop this.

Edit: To be clearer, VERY occasionally it may actually do the 1000 loops. And it may show as a bizarre spike in performance. At least doing something similar did for me. Took me ages to find too.

[kevlar]

The 's' is starting point of the ray, in Minkowski space, 'r' is the ray direction. The minus symbols are there, because of the space (Minkowski difference). Basically the raycast is literally casting a point, but the implementation also allows to cast any other convex shape. See the GjkConvexCast demo.

Hope this helps?
Erwin

So if I had two shapes A and B. I would set the ray starting position to A.position() - B.position() and the ray direction r to ... ?

In that demo it looks like you are setting the positions of A and B to (0,0,0) and (0,10,0) respectively. I don't quite understand the purpose of the fromA and toA variables. Are those purely for camera transformation? They seem to be passed to the GJK also.

Thanks for the responses so far.

[Erwin Coumans]

The 's' is starting point of the ray, in Minkowski space, 'r' is the ray direction. The minus symbols are there, because of the space (Minkowski difference). Basically the raycast is literally casting a point, but the implementation also allows to cast any other convex shape. See the GjkConvexCast demo.

Hope this helps?
Erwin

So if I had two shapes A and B. I would set the ray starting position to A.position() - B.position() and the ray direction r to ... ?

In that demo it looks like you are setting the positions of A and B to (0,0,0) and (0,10,0) respectively. I don't quite understand the purpose of the fromA and toA variables. Are those purely for camera transformation? They seem to be passed to the GJK also.

Thanks for the responses so far.

If it is not clear, I should make the demo more obvious.

The convex cast (==sweep) demo performs time of impact between two linear moving objects, objectA and objectB. Each objects has a starting position (fromA/fromB) and an ending position (toA/toB), both in worldspace. Then internally, the SubsimplexCast algorithm converts this into minkowski space. That's where the intuition usually starts failing. However, this calculation can also be performed in world space. See the ContinuousConvexCollision ( http://www.continuousphysics.com/Bullet ... tml#l00040 ). If you ignore the rotation, you can see the concept and how 'fromA and fromB' are processed. The other version just transforms things into 'relative' MinkowskiSpace.

In the case of raycasting against a convex object, the ray is represented as a moving sphere. Both this sphere and the convex are passed into the routine to find the hitpoint/fraction/normal.

Erwin

[kevlar]

If it is not clear, I should make the demo more obvious.

The convex cast (==sweep) demo performs time of impact between two linear moving objects, objectA and objectB. Each objects has a starting position (fromA/fromB) and an ending position (toA/toB), both in worldspace. Then internally, the SubsimplexCast algorithm converts this into minkowski space. That's where the intuition usually starts failing. However, this calculation can also be performed in world space. See the ContinuousConvexCollision ( http://www.continuousphysics.com/Bullet ... tml#l00040 ). If you ignore the rotation, you can see the concept and how 'fromA and fromB' are processed. The other version just transforms things into 'relative' MinkowskiSpace.

In the case of raycasting against a convex object, the ray is represented as a moving sphere. Both this sphere and the convex are passed into the routine to find the hitpoint/fraction/normal.

Erwin

Okay, I think I see what fromA and toA are. fromA is the current object position (A.getPosition()) and toA is the final position at the next point in time (A.getPosition() + A.getVelocity()). Then your calculateVelocity function takes toA - fromA = (A.getPosition() + A.getVelocity()) - A.getPosition() = A.getVelocity().

Aside from the conversion from world to minkowski space that you mentioned, Gino's algorithm seems a little bit easier to implement. Before setting the values of s and r, you seem to do some sort of transformations with fromA/toA and fromB/toB

Code: Select all

rayFromLocalA = fromA.inverse()* fromB;
rayToLocalA = toA.inverse()* toB;

It seems like your postitions are specified as matrices then you take the inverse of one and multiply it by the other? I guess what I would like to know is, can the vectors s and r be specified somehow using position/velocity vectors of the two objects A and B(as offsets from world origin [0,0,0]) together with simple operations such as addition, subtraction, cross and dot products?

As an example:
Update accel/vel/pos until contact.

A is a sphere radius 10.

A.getPosition() = [0, 50, 0]
A.getVelocity() = [0, 0, 0]
A.getAcceleration() = [0, -9.8, 0]


B is a sphere radius 10.

B.getPosition() = [0, 0, 0]
B.getVelocity() = [0, 0, 0]
B.getAcceleration() = [0, 0, 0]

Resulting contact point should be approx [0, 10, 0] with normal [0, 1, 0].
Does lambda in this algortihm have to lie between 0..1 ?

Thats is basically all of the information I have to work with currently.
Maybe I'm expecting a simple solution to this that just doesn't exist...

Thanks for your patience with me

[Erwin Coumans]

Aside from the conversion from world to minkowski space that you mentioned, Gino's algorithm seems a little bit easier to implement. Before setting the values of s and r, you seem to do some sort of transformations with fromA/toA and fromB/toB

The SubsimplexConvexCast is exactly Gino's formulation, there is no difference. Gino's paper doesn't provide the details how to build the transforms for the minkowski sum, and that is what you are referring to. As I mentioned before, you can ignore the Minkowski sum part or take the ContinuousConvexCollision as a start, which operates in world space.

We are not dealing with acceleration or ballistic motion.We use piece-wise constant linear and angular velocity during each timestep. You can read Brian Mirtich's PhD, he describes the steps to add gravity/acceleration to the equation.

At the moment, Bullet's time of impact calculations take two moving objects, and return the fraction between 0 and 1 for time of impact, as well as the normal at impact and contactpoint.
Just take the ConvexCastDemo as a starting point, and integrate the acceleration each step to get new velocities.

Hope this helps,
Erwin

[rjobling]

Hi Erwin
Sorry for dragging up this old topic. However I'm trying to understand Gino's method and have been looking at your Bullet implementation.

The current Bullet code for btSubsimplexConvexCast::calcTimeOfImpact would seem to differ from Gino's writing in a number of way:

1. You are interpolating the matrices for the bodies rather than shifting the start point of the ray segment as Gino does.
2. You are not clearing the simplex when a new time is acquired.
3. Your conditions for the VdotR failure would seem to be opposite to those of Gino's.
4. You are incrementing the time value each improvement rather than calculating a new one.

It does indeed seem to be working great, however I was wondering if you could elaborate on why these differences work?
Surely when you interpolate the matrices your old simplex vertices are all invalid?
The other stuff is even more puzzling to me, at least right now.

Update:
Okay I figured out the answer to question 3.
Your condition is opposite because your "r" is "linVelA-linVelB" in contrast to "linVelB-linVelA".