Why Triangles

I love a good theoretical discussion, so when Peter Sikachev asked “…will triangles live forever…”, I decided to put aside the post I was working on and jump in.  It’s interesting and instructive to question the conventional wisdom, and go through exactly why we do the things we do. So, why do we use triangles when there are so many other choices?

Triangles Are Good

When I taught an introductory graphics course a while back, I listed some points in favor of triangles

  1. We can exactly represent any polyhedral shape using triangles
  2. We can approximate any non-polyhedral surface to an arbitrary degree of accuracy with a sufficiently large number of triangles.
  3. Triangles are guaranteed to be both planar and convex, which makes them very simple to rasterize

So, triangles are a nice universal rendering primitive. This is the reason why we have been able to build an entire industry around dedicated triangle rasterization accelerators.  If you have a robust, efficient triangle renderer, you can render pretty much any surface model by breaking it down into a large enough soup of triangles.  You can either do this in advance, or you can do it on the fly so that you don’t need to store the full triangle mesh.

Even in the offline rendering world, where you can do whatever you like, it’s common to see renderers that decompose everything into triangles or quads for simplicity’s sake.  Reyes is built around the idea of turning every primitive into a quad mesh.  The Kilauea raytracer used triangles exclusively. The PantaRay raytracer turns everything into triangles or quads.

Triangles Are Not Good

The drawbacks of triangles, and the reasons I made my students learn about Bezier Patches, NURBs, Implicits, and all that other crap:

  1. Accuracy. You cannot exactly represent a non-polyhedron with any number of polygons. Information is lost when tessellating.
  2. Compactness. Even if you could, it’s hardly the most efficient representation.  A Bezier patch or subdiv surface with a displacement map is considerably less data than its tessellated form.
  3. Ease of Modelling/Animation. Directly manipulating a triangle mesh is a pain in the neck, and the other stuff enables us to build much more intuitive tools.

Note that there’s a distinction between a rendering primitive, which triangles are, and a modelling primitive, which triangles could be, but generally aren’t.

Now, to addressing the specific points Peter raised:

Lost PS performance, I’ve written about this elsewhere. There are ways around it if we’re willing to think outside the box about how we shade. Shading per vertex is one option, deferred shading is another. We can have even more options if we’re willing to wait for hardware changes.  I predict that tessellation is going to force IHVs to fix this sooner or later.

Clipping/Culling, a good raster engine can and should use bounding volumes for view-frustum culling anyway, such that the culling load is roughly proportional to the number of visible primitives and not scene size.   Culling can be done on the triangle bounding box and is thus pretty cheap.  Clipping is definitely awkward, but it happens relatively rarely in non-pathological scenes.  Most triangles are either in or out.  It is also possible to build a rasterizer without any clipping.  The fact that this is not very widely known outside the hardware community is rather unfortunate, because it’s pretty cool.

Voxels are very memory intensive, and more importantly, are extremely difficult to animate without considerable pain. Even if we could build a whole renderer around voxels we’re likely to want deforming meshes for animation, which we’d then voxelize on the fly. If we’re going to go to all that trouble then I can’t see any reason not to just rasterize the animated stuff, and if we’re going to do that, may as well do the static stuff that way too.  The exception would be if we wanted lower resolution voxels for some sort of GI tricks, but that’s more about augmenting triangles than replacing them.

Splats  (I assume you mean something like EWA Splatting or QSplat).

Most of the point based rendering research, from what I can tell, is focused on looking at point clouds as an alternative model representation. If you have a massive point cloud from say a laser scanner, you’d just render it directly instead of trying to build a mesh out of it first. I don’t find the size argument to be very compelling for authored content, because all you really save is an index buffer, and by the time an authored asset got big enough for this to matter, we’d most likely have switched to a displacement map.

It seems to me that point splatting isn’t fundamentally very different from rasterizing a dense mesh. To do a splat, you have to transform the point, figure out what pixels it covers, and shade them. Occlusion is kindof icky. I’m not sure if there’s any way to do the equivalent of early Z culling with a point based renderer, but let’s ignore that whole question for the sake of argument.

For a mesh, you have to transform vertices, do clipping (or not), figure out what pixels are covered, and shade them. In the best case (a closed manifold and perfect vertex caching), you will transform about 0.5 vertices per face. In my experience, on real meshes and with caching tossed in, this will fluctuate between around 0.7ish and 1.5ish vertices per face.  The point is that the aggregate per-element cost probably isn’t all that different between one triangle per pixel and one splat per pixel, especially if we’re talking about a hardware implementation.

The Human Factor

Finally, the last reason (least important in theory, but most important in practice): We’ve been doing it this way for two decades now, and human beings hate change.  We have an entire ecosystem built around triangles, and even if it’s not an optimal one, it’s a stable and familiar one. It seems unlikely that they’ll ever disappear given how heavily we’re invested in them. We’ll be stuck with those little three-sided vermin for a long time to come.