Software rendering 3d triangles in the proper order

I'm implementing a basic 3d rendering engine in software (for education purposes, please don't mention to use an API). When I project a triangle from 3d to 2d coordinates, I draw the triangle. However, it's in a random order and so whatever gets drawn last draws on top of all other triangles (which might be in front of triangles it shouldn't be in front of)...

Intuitively, seems I need to draw the triangles in the correct order. So I can calculate all their distances to the camera and sort by that. The objects furthest away get drawn last. Is this the proper way to render triangles? If I'm sorting all the objects, this is n*log(n) now. Is this the most efficient way to do this?

-

This is a valid approach normally known as the Painter's Algorithm. Sorting your triangles will not support overlapping triangles. By that I mean two triangles that overlap in a way such that half of one triangle is infront of the other, while the other is behind. If you don't need to support this, you could probably just do sorting back to front. That is, the furthest geometry gets drawn first.

The more general technique typcally used is a depth buffer. When you paint a pixel, you also record its depth. Then, when you go to paint the pixel again, you can compare depths to see if you need to keep the new pixel or the old pixel. Please see the linked wikipedia article for more info.

-
I meant to mention that there will be no overlapping triangles. I had thought of that and figured it wouldn't be too hard to split triangles if the need arose. The depth buffer technique sounds so inefficient. Calculating distance for every single pixel.. I do use an API's triangle drawing method to draw the triangles.. so I guess I'm cheating at pure software rendering. To use depth buffering, I'd need to fill those triangles pixel by pixel. So it seems sorting back to front is the way to go in my situation. – at. Nov 21 '12 at 20:38
It is not actually inefficient. In 3D graphics you basically have a point in world space that you transform/project into 2D space. This must be done for every pixel. That is how you get what x/y co-ordinate to paint on the screen. But you also get a depth value after doing a projection simply by multiplying your point by a projection matrix. You simply store this value into the buffer, a value that gets computed anyway. – Stephan van den Heuvel Nov 21 '12 at 21:04
By every pixel, I mean every vertex, pixel values are generally interpolated. – Stephan van den Heuvel Nov 21 '12 at 21:13
@at. Are you going to support texture maps and lighting? If so, you will have to draw your pixels yourself anyway ... – Stephan van den Heuvel Nov 21 '12 at 21:19
I just compute 3 points when projecting a 3d triangle onto 2d space. Then I use an API's `draw_triangle` method. I think the filled 2d triangle is drawn using OpenGL, so it's very fast. You're right though, if I have to draw every pixel anyway, making an additional depth calculation isn't too bad I guess.. `sqrt((x-camx)**2 + (y-camy)**2 + (z-camz)**2)` – at. Nov 21 '12 at 21:25