Wow, I'm glad I revisited this since I think I can save some rendering
time by saving the vertex normals from the bowtie checks for the
OpenGl lighting phase in LdGLite.

Here is the algorithm I came up with before I decided to use the L3
code as is.  I had kinda given up on it since I only had it figured
out for 2D screen coords.  The trick of using the dot product to
determine if the cross product vectors pointed in the opposite
direction eluded me until I saw Lars' code.  (You don't need it in 2D
since the normals have only a z component and it's sign determines the
direction of the turn).

I think this is pretty similar to the method in L3.

Calculate the normal vector for each vertex in the quad using the
cross product.  (We can use these again later for lighting)

Eliminate colinear points (i = j = k = 0 in the normal).  Make a
triangle if only one.  Discard the quad if more than one.  Either way
you're done if you found any colinear points.

For each vertex calculate the dot product of its normal with the
normal of the first vertex.  The sign determines whether the 
turn at that vertex is clockwise or counterclockwise.

If you get 3 similar turns and 1 opposite turn then you have a concave
point at the oddball turn.  Split the quad into 2 triangles at that
point and you're done.

If you have 2 clockwise and 2 counterclockwise turns then you have
a bowtie.  Find the first two adjacent vertices with the same turn,
swap them, and you're done.

Otherwise you must have 4 similar turns and an nice simple convex
quad.

Pretty neat, eh?  And it's not all that complicated after all...

Don





