What are the basics of 3D triangle/quad sorting?

I am really curious how any 3D engine or even the GPU sorts triangles and quads. Are they basically taking a "center" point of a particular triangle/quad/poly and then calculate a distance from a camera point?

How is the depth of a polygon calculated if not using a point distance algorithm? Keep in mind I am a complete noob regarding 3D.

-

For the most part, depth sorting does not occur at the triangle level. For opaque geometry - which is the majority of geometry drawn in a typical 3D application - depth sorting is usually done per pixel, using a depth buffer, also called a Z-buffer. It's a block of video memory that keeps track of the depth (distance into the screen) of each drawn pixel. When a new triangle is drawn, the GPU calculates the depth of each pixel in the triangle and compares it to the depth already stored in the depth buffer for that pixel. Only if the new pixel is closer does it get drawn (and the depth buffer updated). Thus, geometry that's behind other geometry gets culled away.

This image-space approach allows for interpenetrating geometry to be rendered correctly, and is a lot easier to parallelize (i.e. to make it fast) than an approach based on depth sorting at the triangle level.

Now, for transparent geometry it's another story. For transparent stuff the depth buffer doesn't help you, because you can't just cull away a transparent pixel that's behind another transparent pixel. In this case, the usual approach is to sort objects or individual triangles from back to front on the CPU, then the GPU will draw them in the correct order. The GPU doesn't have any built-in sorting capabilities that help with this case. Sorting by the depth of each triangle's centroid is a common and generally reasonable approximation, although it does not work in all cases.

Lastly, there are advanced techniques known collectively as "order-independent transparency" that allow you to do per-pixel depth sorting on the GPU for transparent geometry. These techniques can generate a visually correct image in cases where triangle sorting fails, but are very expensive in performance and memory.

-
For nVidia / AMD the above is certainly true. But there are other cards out there, notably the PowerVR, which can do z-order correct per-pixel alpha blending (i.e. polys with alpha are correctly drawn just like opaque polys). This was used in the Sega Dreamcast machine and, more recently, in mobile platforms as it lends itself to low-power systems quite well. – Skizz Feb 29 '12 at 9:14
@Skizz Interesting; I didn't know that. I read a little bit about it and it sounds like it buffers up all the triangles in the scene into VRAM, then does some tile-based sorting and rasterization. It's an interesting approach but would be extremely memory intensive for detailed scenes with millions of visible triangles. – Nathan Reed Feb 29 '12 at 17:09
It does require a bit more memory but there will be optimisations in there. It is also a very easy system to parallelise - in the extreme case each tile can be rendered with its own GPU. Plus you can do some really cool effects easily that would be quite tricky on an nVidia/AMD style renderer. – Skizz Mar 1 '12 at 9:15
I think the centroid sort logic is what I was trying to figure out... I am trying to learn the basics of the new stage3D APIs for the Flash Player, basically trying to approximate and project 2D isometric content by a) assuming that the projected content will have either a flat spacial area or a cubic volume, then b) creating the faces of that geometry and projecting into Flash via a blitting engine I have created. – as3isolib Mar 1 '12 at 14:31