Apologies if this is a dumb question... but given four arbitrary (non-coplanar) points in 3D space, there are obviously two different ways to triangulate the quad that they form. One triangulation may produce much more natural results than the other- but how can I determine which one to pick?
Context: I’m doing Dual Contouring, and the quad forms part of an isosurface. I have access to the hermite/gradient data at that point.
A simple heuristic that many 3D content creation apps use is to split along the shorter of the two diagonals of the quad. This generally seems to work pretty well. It minimizes the appearance of long, skinny triangles, which are generally undesirable both for visual and performance reasons.
See this article: Deformation and Triangulation in Maya for some further discussion. In particular if you have a dynamically deforming mesh, you ideally want to retriangulate the quads based on the deformed geometry each frame, or you can get some pretty wonky artifacts if you stick with a fixed triangulation:
(image from the above linked blog post)
One other, albeit more expensive approach, is to subdivide your quad into 4 triangles by putting a point at the centre of each quad. There are some advantages to this in that:
It will be more temporally stable. If your quad vertices are moving and you were otherwise using the "shortest diagonal" approach Nathan has suggested, the tessellation will change pattern every now and then. Maybe this won't matter too much geometrically, but remember that the UV texture coordinates are also linearly interpolated in world space (obviously hyperbolically in screen space) and so the texturing can jump.
If the quad is quite distorted (e.g non-planar or non-convex), I think the 4xtri approach will look much better than either of the two 2xtri options
If you instead are just chopping into triangles based on the order of the vertices of your quad, i.e. ABCD always becomes ABC and CDA, then if by chance the modelling package spits out another "identical" quad but ordered as BCDA, then the rendered versions won't match.
Of course, the downside is that you have 2x the number of vertices and triangles, but it may be worth considering.
This isn't a dumb question. This is a much more important question than most people realize.
Here's the worst case scenario for triangulating a quad:
No sane artist will ever make this for static geometry, but no sane animator will check every frame of every animation to make sure that we never get this. We have a degenerate quad, with three collinear vertices, and it's being triangulated such that we have a zero area face. Note that this is shortest diagonal triangulation; shortest diagonal is no proof against this, and neither is longest diagonal.
If we put some normals on there, and treat this as smooth shaded, we'll see that the central vert's normal contributes reasonably to the quads on the left, but not at all to the quad on the right. This will cause a discontinuity in normals:
This is not some magical thing that only happens at perfect degeneracy. As our quad is divided into triangles of increasingly different areas, our vertex data will be divided increasingly unevenly across the quad. That may mean pinched normals, it may mean unsmooth vertex color-- in either case, the triangulation will be increasingly apparent visually.
The best way to prevent this bad situation is to triangulate to minimize the difference in area between triangles. Triangulation in this way will also give us symmetrical triangulation on symmetrical portions of our mesh, which is also a desirable trait.
For animated meshes, one might be tempted to do this dynamically, but that would be a mistake. Flipping triangulation will change the interpolation of vertex data across the quad:
All I'm doing here is flipping triangulation. This is shown with mildly distorted UV, which is an optimistic expectation, but we'll see the same swimming with normals and vertex color, and with data derived from interpolated vertex data, like UV tangents. Instantaneous change like this-- pop-- is one of the most noticeable kinds of artifacts in animation.
So we don't want to determine triangulation from a deformed state. To have stably interpolated vertex data, we need to have a consistent triangulation of the mesh. If our framework allows, we can mark vertices appropriate for triangulation in the pre-deformed state. If it doesn't, it's better to use something like vertex order, which is stable through deformations, than it is to risk swimming from dynamic triangulation.
Assuming we are using a separate array for indices into the vertex array, the following pattern for the indices array is the most efficient for splitting a quad. Must be in this specific order:
0 3
1 2
using this exact sequence of triangulation:
(0,1,2) (0,2,3) for splitting the two tris in one diagonal
OR
(0,1,3) (1,2,3) for the other diagonal
Why? because you just have to add one unit to the two adjacent indices to switch from one diagonal to the other:
const offset = 0 or 1 (*)
(0,1,2+offset) (0+offset,2,3)
(*) 0 or 1 depending on the shortest distance between the two diagonals: abs( length( vertex2 - vertex0 )) and abs( length( vertex1 - vertex3 ))
Obs. all sequences of three numbers (a triangle) above are CCW (counter clockwise) for Front Facing triangles
Obs.2 this array of groups of 4 indices into the vertices array could be treated as a vec4 in glsl ;)
