Bullet Ray Cast

[Dirk Gregorius]

I looked into Bullet's ray cast implementation, specifally in the btSubSimplexConvexCast. The Result structure doesn't return the hit point.

Q1) Why isn't the hit point returned? And how is hit point actually defined here, when e.g. two polytopes are swept against each other and have a face vs. face contact. E.g. does the function return one vertex on each face?

Q2) Isn't the point x computed during the iteration the global hit point? Do I actually get a hit point for a convex cast (e.g. two boxes) or do I need to perform another GJK to find such a point?


Bullet also has some minor differences w.r.t. the original paper. You seem to transform the problem in local coordinates and perform the ray cast vs the sum A + B. In the paper the the algorithm seems to work in world coordinates with a ray R: x = s + lambda * ( t - s ) where s and t are the linear movements (displacements) of the objects and the ray is actually casted against A - B (CSO). Are the special reasons for this?


Thanks,
-Dirk

[Erwin Coumans]

I looked into Bullet's ray cast implementation, specifally in the btSubSimplexConvexCast. The Result structure doesn't return the hit point.

Q1) Why isn't the hit point returned? And how is hit point actually defined here, when e.g. two polytopes are swept against each other and have a face vs. face contact. E.g. does the function return one vertex on each face?
Q2) Isn't the point x computed during the iteration the global hit point? Do I actually get a hit point for a convex cast (e.g. two boxes) or do I need to perform another GJK to find such a point?

The SubSimplexConvexCast merges the Conservative Advancement loop with the GJK loop that searches for the closest points. This means, it is not using regular GJK anymore, but directly operates on the Minkowski sum/difference using the CSO. This is described in more detail in chapter 4 of Gino van den Bergen's paper raycasting against convex objects. The convex sub simplex cast is meant for ray casting, so it just returns the hit normal and fraction.

The worldspace hitpoint for the raycast is calculated from the fraction and the begin/end point of the ray (a ray is a swept point). If you need contact points for 2 swept convex objects, use the world space implementation in btGjkConvexCast, or use a reversed raycast outwards starting at the origin of the minkowski sum that includes the linear swept motion (like Jay Stelly mentioned). If you want to include rotation (generic continuous collision detection), use btContinuousConvexCollision. There are seperate demos for each of them provided in Bullet, please check them out: Demos/Raycasting, Demos/GjkConvexCastDemo and ContinuousConvexCollision.

For both GjkConvexCast and ContinuousConvexCollision the hitpoint is already calculated by the last GJK closest point calculation, so it can be provided.

Bullet also has some minor differences w.r.t. the original paper. You seem to transform the problem in local coordinates and perform the ray cast vs the sum A + B. In the paper the the algorithm seems to work in world coordinates with a ray R: x = s + lambda * ( t - s ) where s and t are the linear movements (displacements) of the objects and the ray is actually casted against A - B (CSO). Are the special reasons for this?

Minkowski sum and difference (A + B or A - B) is the same, they both represent the CSO. There are several papers on Conservative Advancement. Brian Mirtich's PhD, pages 31 onwards, introduced this idea in the field. Then several refinements have been proposed mixing Conservative Advancement with GJK for pure linear motion, my draft paper on extending Gino's mixed loop for including rotation (either in worldspace, or on a deforming minkowski sum/CSO) and Kim Young's SIGGRAPH 2007 paper including rotation with hierarchies, concave objects and getting more tight bounds. Bullet implements several variations on the same theme, some in configuration space (against the CSO), and some in worldspace. This week at SIGGRAPH, I discussed the application of Conservative Advancement with Kim Young, and we both agreed that the idea can be applied on deforming triangles and deforming tetrahedra in a straightforward way (either in worldspace or in CSO). This would allow to calculate the time of impact for cloth and deformable objects.

Hope this helps,
Erwin

ps: moved to Bullet section, it is Bullet specific.

[Dirk Gregorius]

Yes, that clears up a lot. Thanks a lot!

I just implemented this today myself and swept two boxes against each other. So as a result (as "hit points") if found the world coordinates of the center of mass of the shapes, but not the points on the surface. In the case of a sphere with radius zero this would be of course the hit point of the ray with the other object. So this is indeed the expected result or am I missing something?

So for linear swept collision detection you recommend "btGjkConvexCast ". I will look into the code on Monday. Is this also based on some paper - is there a reference? Regarding Jay's method we could maybe compare them later. I have implemented it, but found it relatively hard to get it numerical stable. This is because when you cast rays against the tetrahdron you can have the ray either start/end exactly in a face or a ray is parallel and in the plane of the face. To make this numerical robust you need an additional point in triangle test for the first problem and a projected 2D test for the later. This makes this quite expensive then.


Looking forward you application for deformable objects! Great work!



Cheers,
-Dirk

[slithEToves]

This is good info. I have been running a GJKPairDetector test at the TOI location specified by the subsimplex cast to get the contact point. It returns the correct point, but it seems non-optimal to do this.

[Dirk Gregorius]

I wonder if the contact point isn't simply an extremal point (support) in the direction of the motion vector. Anybody thought about this?

[slithEToves]

The support in the motion direction would not be the correct point in general. Imagine a triangle moving in the direction of one of its vertices, with a glancing collision just at another vertex. The support would pick the wrong vertex in this case.

A support that is along the returned collision normal should work, but only if you knew which object the normal came from, which isn't entirely clear when operating just on the Minkowski sum of the shapes.

[Dirk Gregorius]

So the only way to compute the "correct" hit point is an additional GJK?

[slithEToves]

Intuitively it seemed like the correct point should have been available during the last step of the subsimplex cast, but I couldn't convince myself whether the correct point was there or not when stepping through the algorithm. I will probably switch to using the GJK cast instead as Erwin suggests, at least in cases when the cast shape isn't a point.

[dog]

I've only just seen this. You have almost all the information you need, but a couple of modifications are required.

When calculating the Minkowski sum:

i.e.
p <- Support Point on object at origin
q <- Support Point on located object
return p + q

Also store the q in the simplex, not just (p + q). I call it m_qlocal.

So you would have something like this (I'm following Gino's conventions here, my actual code is a bit different):

Code: Select all

	void AddVertex(const Pos3 w, const Pos3 p, const  Pos3 q, const Pos3 qlocal) {
		AddVertex(w);
		m_p[m_last] = p;
		m_q[m_last] = q;
		m_qlocal[m_last] = qlocal;
	}

Then you can add a function to compute the actual hit point. Gino style it would be something like:

Code: Select all

	Pos3 ComputeLocal(void) {
		float sum = 0;
		Pos3 p1(0,0,0);
		for (unsigned int i=0, bit=1; i<4; i++, bit <<= 1) {
			if (contains(m_bits, bit)) {
				sum += m_det[m_bits][i];
				p1 += m_qlocal[i] * (float)m_det[m_bits][i];
			}
		}
		if (sum > 0.0) {
			float invSum = 1.0f / sum;
			p1 = p1 * invSum;
		}
		return p1;
	}

This is your world space hit point AT THE TIME of collision. To be useful if you are doing a fixed timestep update you will probably need to get the transform of both objects at that time, rotate that world space hit point into the local object spaces and then calculate the world locations at the actual end of the time step for both objects.

Hope that helps.

[Dirk Gregorius]

Thanks for pointing this out. I will look at this more sorrowly on Monday, since I am not so familar with Gino's notation. Anyway do you suggest to additionally store the local support points and barycentric coordinates and then compute the global hit point as convex combintation as do you basically in normal GJK or is there a small variation I am overlooking?

[dog]

The code is just a barycentric combination the same way you extract points in standard GJK from the simplex. It is the equivalent of doing a ComputePoints() at the end of normal GJK to get the witness points. We are using the contribution of the world space located object to the Minkowski sum.