4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I should say that they’re not totally arbitrary- they lie on the form corners of a square and it’s only the z coordinate that changes $\endgroup$ – andygeers Sep 1 at 20:27
4
$\begingroup$

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:

dynamic retriangulation based on shortest diagonal vs fixed triangulation
(image from the above linked blog post)

| improve this answer | |
$\endgroup$
  • $\begingroup$ Interesting suggestion- thank you! $\endgroup$ – andygeers Sep 1 at 20:28
3
$\begingroup$

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:

  1. It will be more temporarily 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.

  2. 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

  3. 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.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.