Vertex clipping and primitive types

[Sam Spilsbury]

Hey all,

I've started playing around with trying to get weston surfaces (or
views as they will later be called) to use arbitrary vertex meshes.
This would allow for more complex geometry and effects with the demo
compositor.

Currently, the vertex clipping implementation supports up to eight
vertices and assumes that they are arranged in a fan (eg
GL_TRIANGLE_FAN)[1]. I'm pretty sure that most geometry can be covered
as long as we support GL_TRIANGLES (disjunct triangles),
GL_TRIANGLE_STRIP (quadrilaterals or other sequential meshes) and
GL_TRIANGLE_FAN (circles).

The latter two of these essentially work by "inferring" a path between
previous vertices and the next vertex in a sequence after n > 2. For
instance:

GL_TRIANGLE: Line explicit between n and n - 1.
GL_TRIANGLE_STRIP: Line explicit between n and n - 1 and inferred
between n and n - 2.
GL_TRIANGLE_FAN: Line explicit between n and n - 1 and inferred between n and 1.

Currently, our clipping code doesn't take these inferred paths into
account (it only clips the explicit between n and n - 1). Which means
that geometry arranged as a strip of sequential rectangles gets
clipped along the diagonal between the concentric triangles.

The more or less obvious solution is to do this:

GL_TRIANGLE_STRIP: Clip explicit path and clip implicit path from n to n - 2.
GL_TRIANGLE_FAN: Clip explicit path and clip implicit path from n to 1.

However, it gets a little more complicated than this, because a
quadrilateral can have its vertices arranged in such a way that it
would pass as both a GL_TRIANGLE_STRIP and GL_TRIANGLE_FAN. That is,
if the vertices are arranged such that they wind in a particular
direction, eg:

x1,y1 -> x2,y1 -> x2,y2 -> x1,y2 (counterclockwise) or
x1,y1 -> x1,y2 -> x2,y2 -> x2,y1 (clockwise)

In that case, even though the mesh would still be a valid
GL_TRIANGLE_STRIP, we can't clip the n - 2 path because for the fourth
vertex, a path is inferred between 4 and 1 and not 4 and 2.

I've been trying to think of ways to solve this problem:

In both solutions we will need the vertex mesh to specify its
primitive type (for obvious reasons).

The first solution is to detect such winding and infer the path as
though the mesh was a fan. I think this this problem is only going to
be relevant to GL_TRIANGLE_STRIP arrangements that could also be
expressed as a GL_TRIANGLE_FAN without any ordering adjustments.

The second solution would be to require that a GL_TRIANGLE_STRIP is
arranged in such a way that it cannot also be a GL_TRIANGLE_FAN
without any ordering change. That way, we can assume that clipping the
n - 2 path for a STRIP will always be correct.

Thoughts?

Sam.



[1] For those who are curious about the various primitive types, have
a look at http://www.opengl.org/wiki/Primitive

-- 
Sam Spilsbury