Sign in to follow this  
Dirk Gregorius

Identify diagonals in convex quadrilateral

Recommended Posts

TheAdmiral    1122
I don't know about fastest, but here's a method. At worst, it takes 12 24 additions, 8 16 multiplications and up to four signed comparisons (this can be improved upon slightly at the cost of readability):

Arbitrarily label the vertices A, B, C, D (assumed to be in the x-y plane).
Calculate the edge vectors AB, BC, CD, DA.
Calculate the cross-products

c1 = AB × BC
c2 = BC × CD
c3 = CD × DA
c4 = DA × AB

If all of {c1.z, c2.z, c3.z, c4.z} have the same sign, then you 'guessed' the edges right and the diagonals are AC, BD.

Edit: If not, then they are either AB, CD; or AD, BC. In this case, you'll need to switch two vertices (say, A and B) and repeat the calculation.

My intuition tells me that it's impossible to work this out without performing four calculations, but its altogether possible that they could be made simpler than this.

Admiral

[Edited by - TheAdmiral on May 5, 2007 7:54:59 PM]

Share this post


Link to post
Share on other sites
jyk    2094
I'm sure this is wrong and that I've missed some case or another (don't have time to double-check at the moment), but I'll go ahead and post it just to contribute something to the discussion:
vector3 c1 = ABxBC
vector3 c2 = BCxCD
vector3 c3 = CDxDA

int s1 = sign(dot(c1,c2))
int s2 = sign(dot(c1,c3))
int s3 = sign(dot(c2,c3))

if (s1 == s2) {
if (s1 == s3) {
...diagonals are AC and BD...
} else {
...diagonals are AD and BC...
}
} else {
...diagonals are AB and CD...
}

Share this post


Link to post
Share on other sites
TheAdmiral    1122
Quote:
Original post by Christer Ericson
Quote:
Original post by TheAdmiral
If [...] the diagonals are AC, BD. If not, then they are AB, CD.
Except, of course, when they are AD and BC.

I must admit I'm a little confuddled right now (read: drunk), but if the diagonals were AD and BC, wouldn't the test still come out negative, only with the values having the opposite sign? Or is that your point?
As far as I can tell, there's only one way to get the order wrong under isomorphism.

Quote:
Actually my points exist is R3, but I know the plane normal. Do need to project or can this also be solved in 3D?
It works just fine in 3D, but you'd need to project the cross-products to the normal's vector before comparing. In this case, I suspect there's a more efficient method.

Admiral

Share this post


Link to post
Share on other sites
Quote:
Original post by TheAdmiral
[...] Or is that your point?
Fix one vertex of the convex quad and call it A. Arbitrarily labeling the remaining three vertices then gives six different labelings, with three unique pairs of diagonals: AB+CD, AC+BD, and AD+BC.

My point was that your code only distinguished two of these cases, not three. Therefore what you suggested cannot have been a complete solution.

Share this post


Link to post
Share on other sites
TheAdmiral    1122
Quote:
Original post by Christer Ericson
My point was that your code only distinguished two of these cases, not three. Therefore what you suggested cannot have been a complete solution.
Good call. I think it's fixed now.

Admiral

Share this post


Link to post
Share on other sites
Dirk Gregorius    2757
What about this:

Label vertices arbitrary as A,B,C and D. Additionaly to the vertices I have the plane normal n. Now I simply test three edges AB, AC and AD and test the if the other two vertices are on opposite sides where I use the plane through A with the normal direction n_i = n x AX (X = B,C,D) to define the test plane.

Anything that could go wrong with this? It is similar to jyk's test though I need the normal while he gets along with the edges...? Aren't in his example

vector3 c1 = ABxBC
vector3 c2 = BCxCD
vector3 c3 = CDxDA

c1, c2 and c3 parallel since all edges lie in the same plane?

Share this post


Link to post
Share on other sites
While I didn't verify the details of what jyk posted, his basic approach is correct. Here's a full description (albeit using different vector cross products).

In the plane of ABCD, fix A. That leaves six different configurations:
A---B  A---B  A---C  A---C  A---D  A---D
| 1 | | 2 | | 3 | | 4 | | 5 | | 6 |
C---D D---C B---D D---B B---C C---B
(1 and 3, 2 and 5, and 4 and 6 have the same diagonals, so we really only have three different cases, as I pointed out earlier.) Now pick three different edge pairs and perform cross products between them. I picked ABxAC, ABxAD, and ACxAD.

Assuming a vantage point looking into the screen you're reading this on, these cross products result in vectors that point in or out of the screen, like so:
         1     2     3     4     5     6
ABxAC | in | in | out | out | out | in |
ABxAD | in | in | out | in | out | out |
ACxAD | out | in | in | in | out | out |
Of course, we don't actually know from which side we will be looking at the quad, so "in" and "out" could be swapped. Neatly though, if you look at the pairs that have the same diagonals (1 and 3, 2 and 5, and 4 and 6) you see they are each others opposites.

Thus, in order to distinguish between the 3 unique cases of different diagonals, we perform the following tests:
// Cases 1 and 3:
if SameDirection(ABxAC, ABxAD) && !SameDirection(ABxAC, ACxAD)
then diagonals are AD and BC
// Cases 2 and 5:
if SameDirection(ABxAC, ABxAD) && SameDirection(ABxAC, ACxAD)
then diagonals are AC and BD
// Cases 4 and 6:
if !SameDirection(ABxAC, ABxAD) && !SameDirection(ABxAC, ACxAD)
then diagonals are AB and CD
The SameDirection() tests are done with signs of dot products which results in code similar to what jyk posted:

Vector u = Cross(ab, ac), v = Cross(ab, ad), w = Cross(ac, ad);
float s = Dot(u, v), t = Dot(u, w);
if (s > 0.0f && t < 0.0f) return DIAGONALS_ARE_AD_AND_BC;
if (s > 0.0f && t > 0.0f) return DIAGONALS_ARE_AC_AND_BD;
if (s < 0.0f && t < 0.0f) return DIAGONALS_ARE_AB_AND_CD;
return QUAD_IS_DEGENERATE;

If you know the quad cannot be degenerate, you can optimize this to:

Vector u = Cross(ab, ac), v = Cross(ab, ad), w = Cross(ac, ad);
float s = Dot(u, v), t = Dot(u, w);
if (s * t < 0.0f) return DIAGONALS_ARE_AD_AND_BC;
if (s > 0.0f) return DIAGONALS_ARE_AC_AND_BD;
return DIAGONALS_ARE_AB_AND_CD;

If cross products are more expensive than dot products (which isn't necessarily true on all platform) this can be rewritten through two applications of Lagrange's identity into:

float e = Dot(ab, ab), f = Dot(ab, ac), g = Dot(ab, ad), h = Dot(ac, ac), i = Dot(ac, ad);
float s = e * i - f * g, t = f * i - h * g;
if (s * t < 0.0f) return DIAGONALS_ARE_AD_AND_BC;
if (s > 0.0f) return DIAGONALS_ARE_AC_AND_BD;
return DIAGONALS_ARE_AB_AND_CD;

The last two versions are about as efficient as this test will ever get.

Share this post


Link to post
Share on other sites
Dirk Gregorius    2757
When you use GJK (instead of SAT and clipping) you find only one contact point per frame. So you have to build and maintain you contact manifold over several frames. Once you have four points in your manifold (which is anabitrary upper bound) you need some heuristic how to add points into your manifold. One such heuristic is to choose those four points that span the largest area (and sometimes you also keep the point with the maximum penetration). So assume we have four points A,B,C,D and a new point E. I test all possible quadrilaterals and keep the four points that span th biggest area. The formula for the area of a (convex) quadrilateral is Area = 0.5 * | p x q | where p and q are the diagonals. For an arbitrary convex quadilateral I don't know the diagonals, so I need to identify them. That is what the code is for.

So nothing special. Unfortunately we will not get rich and famous with this :-)


Cheers,
-Dirk

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this