I've been reading up Christer Ericson's Real-Time Collision Detection to implement GJK in my game (namely section 9.5.2), but I have some questions regarding how Ericson picks the correct face voronoi region that contains the origin.

In the book, he states that if the origin is not within any vertex or edge voronoi regions, then testing whether or not the origin is within any face voronoi regions simply becomes checking whether or not the origin and the last point from the tetrahedron are on the same side of the face plane. Let me elaborate:

Let's define the tetrahedron Q as a set of four points, Q = {Q1, Q2, Q3, Q4}. 

Say we are currently testing face Q1Q2Q3, and we define origin as point P. We can obtain the normal of face Q1Q2Q3 by cross producting two edges, I will denote the normal as N now. 

The plane that contains Q1Q2Q3 divides the 3D space into two halfspaces. Ericson's face region test is to check if Q4, the only other point from the tetrahedron, and P, the point we are checking against, reside in two different halfspaces. 

Since the plane is defined by its normal N, we can do dot(P - Q1, N) and dot(Q4 - Q1, N) and check if they have different signs (that means they are in two different halfspaces). Here's the face region check written out in code:

if (dot(P - Q1, N) * dot(Q4 - Q1, N) < 0) PIsInFaceRegionQ1Q2Q3(); 

However, I have an issue with this approach. Consider this tetrahedron:

It is obvious that the origin is contained by the face voronoi region made up by red vertex, yellow vertex, and green vertex. However, if I take a picture of it from the side, we can see that this tetrahedron is nearly coplanar:

'

If we do Ericson's test for face made up by red, yellow, and green vertex, then the test tells us that, yes, origin is inside RYG's voronoi region. However, if we do the same test on the face made up by green, yellow, and blue vertex, the test tells us that the origin is ALSO in GYB's region. The test result becomes ambiguous. The origin can be simultaneously in different halfspaces for two different triangle faces of the same tetrahedron while the origin is not in any vertex region or edge region.

Therefore, I think either this technique is wrong or I am not understanding it correctly. Am I correct on saying that this way of testing face voronoi regions is wrong? If so, what is the best way to do it then? Thanks a lot!

Here are two cents from me on the issue:

My temporary solution is to check all four faces and keep the possible candidates (accept the fact that there might be multiple triangle faces that pass the test). Recall that the test is consist of two dot products. Let's use the example above: one of the dot product, dot(P - Q1, N), can be used to calculate (P - Q1)'s projection onto N, the triangle normal. Then I take the absolute value of this projection value. This projected value tells us the absolute distance between the origin and the triangle face plane. Then we can choose the candidate with the highest projected length as the face whose voronoi region contains the origin.

I haven't proved this to be absolutely correct, although I do have some intuitions to why it should work. I added it to my game and it works reasonably well. 

But again, I doubt that this is the best solution. Putting the questionable correctness aside, this will cost an extra division and sqrt for each candidate triangle face. Quite expensive. 

1 hour ago, MonterMan said:

Therefore, I think either this technique is wrong or I am not understanding it correctly

I think you may have missed some of the rest of this section (assuming it is section 5.1.6). As I read it, you need to calculate whether the origin falls in each of the 4 half spaces, and then by combining those results can classify which voronoi region it falls in. At that point you can project it on the relevant vertex/edge/face to find the closest point.

Hi swiftcoder. Sorry I didn't mention the section that I am referring to. I am talking about what's written in section 9.5.2 in the book, page 404. The author explicitly states that, if the point is not in any vertex or edge regions, then

"P lies in the Voronoi region of Q1Q2Q3 if and only if the following inequality holds:

((P - Q) . n123)((Q4 - Q1) . n123) < 0,

where again

n123 = (Q2 - Q1) x (Q3 - Q1)"

 And that other face regions can be tested the same way. I don't see additional halfspace tests in this particular section. 

Hmm. 9.5.2 mentions that it uses the exact same method as in 5.1.6, and the very end of 5.1.6 mentions that with some tricks you can get the test down to as few as 10 dot products, so I'm pretty sure the author intends one to exhaustively test all the voronoi regions.

For what it's worth, Eberly just calculates the distances to each face, and then returns the closest one. 

Hi swiftcoder. If that's the case then it makes some sense now. I can see how these are intended to be just helpful facts for optimization.

Also Eberly's approach is simple and correct, I like it.

All in all, thank you for clearing it up for me! This was confusing me big time and now it finally makes some sense!

They way I do this is to order the vertices and named them A, B, C and D. There are 15 regions in total. The interior region, and 14 exterior regions. There are 6 edge regions, 4 face regions, and 4 vertex regions, to form all 14 exterior edges.

A simple way to figure out which region a given point is in, is to compute barycentric coordinates of the point against the tetrahedron. This will tell you which faces the point is in front of. Another approach would be to compute distance of point to plane for each face of the tetrahedron.

Assuming the point is above a face, it can potentially also be in front of other faces, up to three. So some test would need to be done to see if the point is nearest to one of the edges, one of the faces, or potentially a vertex.

In my own code I just up-front compute barycentric coordinates for the tetrahedron, along with coordinates for all the triangles, and directly enumerate the 15 different cases with 15 different checks (and 15 different return points).

This can mostly be seen in Erin's 2D version, which is fairly straightforward to extend to 3D: http://box2d.org/files/GDC2010/Distance2D.zip

I've never thought about taking the barycentric coordinates of the point against the tetrahedron, good point! That seems like an elegant way to do the voronoi regions check for a tetrahedron, thanks a lot!