2
\$\begingroup\$

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?

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
9
  • \$\begingroup\$ 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. \$\endgroup\$
    – at.
    Nov 21 '12 at 20:38
  • \$\begingroup\$ 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. \$\endgroup\$ Nov 21 '12 at 21:04
  • \$\begingroup\$ By every pixel, I mean every vertex, pixel values are generally interpolated. \$\endgroup\$ Nov 21 '12 at 21:13
  • \$\begingroup\$ @at. Are you going to support texture maps and lighting? If so, you will have to draw your pixels yourself anyway ... \$\endgroup\$ Nov 21 '12 at 21:19
  • \$\begingroup\$ 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) \$\endgroup\$
    – at.
    Nov 21 '12 at 21:25
0
\$\begingroup\$

1st question: Is this the proper way to render triangles? This will usually work, but not always (see below for details).

2nd question: If I'm sorting all the objects, this is n*log(n) now. Is this the most efficient way to do this? Probably, unless you know something special about the triangles before you start drawing them (e.g., if you are drawing a surface that doesn't fold over itself, you can do it quicker because any order will work).

Some details on the 1st question: I think I'm working on the same problem. I create a list of triangles using triples of (x,y,z) coordinates and then send them in order to a draw_triangle method. None of my triangles overlap (i.e., none puncture or slice through each other). However, the "back to front" approach using distance does not always work. It occasionally draws some triangles in front of others when they should be behind them.

Stephen's response that "you could probably just do sorting back to front" is fairly accurate, as this works almost all of the time for normal cases. However, I started noticing errors and eventually determined that the cause was the ordering algorithm that did back to front by distance.

A simple counter-example is two triangles arranged like a bowtie, where they overlap in the middle near their vertices. Assume the right triangle is slightly behind the left triangle. Now rotate the entire bowtie as a single unit so that the right side comes forward and the left goes back. Using "back to front" based on distance, the left triangle is drawn first because it is farther away. However, the correct order is to draw the right triangle first, because it is behind the left one where they overlap.

A solution to resolve this is based on a different method to compare the drawing order of any two triangles, instead of just distance. It looks at whether any vertex of one triangle is "inside of" the other triangle from the perspective of the viewer. If so, it determines whether that vertex is in front of or behind the other triangle and then orders the triangles the same way. If not, the order doesn't matter because neither triangle obstructs the other. This 2-triangle comparison is then used as the comparison operator for a sorting algorithm that sorts all triangles.

This works if there are no cycles in your triangle order. It is possible that part of triangle A is in front of part of triangle B, part of B is in front of part of C, and part of C is in front of A. For example, in the bowtie example, add a third triangle that overlaps part of the right side and part of the left, but does not overlap the center of the bowtie. In this case, the left triangle blocks the right, right blocks third, and third blocks left, so there is no ordering that will work. A more sophisticated method is required than just choosing an order to draw the triangles. Depth buffers would work if you switch to drawing pixels, or you could divide triangles into smaller ones that break the cycles in order to stay with the draw_triangle interface.

\$\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.