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.
GJK Ray cast
-
- Site Admin
- Posts: 4221
- Joined: Sun Jun 26, 2005 6:43 pm
- Location: California, USA
Re: GJK Ray cast
Bullet contains 3 implementations for Ray/convex casting, all variations on Brian Mirtichs Conservative Advancement, seekevlar wrote: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.
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
Last edited by Erwin Coumans on Sat Sep 30, 2006 6:29 am, edited 1 time in total.
-
- Posts: 4
- Joined: Fri Sep 29, 2006 9:41 am
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?
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());
-
- Posts: 40
- Joined: Fri Jul 22, 2005 8:00 pm
- Location: Santa Monica
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.
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.
-
- Site Admin
- Posts: 4221
- Joined: Sun Jun 26, 2005 6:43 pm
- Location: California, USA
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).dog wrote: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.
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.
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.kevlar wrote:
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());
Hope this helps?
Erwin
-
- Posts: 40
- Joined: Fri Jul 22, 2005 8:00 pm
- Location: Santa Monica
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.
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.
Last edited by dog on Sat Sep 30, 2006 3:16 pm, edited 1 time in total.
-
- Posts: 4
- Joined: Fri Sep 29, 2006 9:41 am
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 ... ?Erwin Coumans wrote: 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
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.
-
- Site Admin
- Posts: 4221
- Joined: Sun Jun 26, 2005 6:43 pm
- Location: California, USA
If it is not clear, I should make the demo more obvious.kevlar wrote: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 ... ?Erwin Coumans wrote: 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
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.
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
-
- Posts: 4
- Joined: Fri Sep 29, 2006 9:41 am
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().Erwin Coumans wrote: 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
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;
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
-
- Site Admin
- Posts: 4221
- Joined: Sun Jun 26, 2005 6:43 pm
- Location: California, USA
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.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
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
-
- Posts: 1
- Joined: Wed Mar 05, 2014 8:19 pm
Re: GJK Ray cast
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".
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".
Last edited by rjobling on Wed Mar 05, 2014 8:38 pm, edited 2 times in total.