How to Z-sort triangles for a 3D engine?

Question

I am creating a small 3D engine for the game I'm working on. I have sorted my basics: textured triangles with a drop of the back surface. However, sorting depths is a difficult problem.

I calculate the face of Z by averaging the 3 points that make up the triangular face. Longer faces sometimes overlap smaller faces, since they have a larger Z value and therefore rise in the list sorted by depth of display.

How to fix it? I am sure that there are known methods for sorting depth, if I can get some practical help in programming them. I built the rendering pipeline myself, so I have access to all the required data: triangles, points, textures, UV coordinates, etc.

Cathedral made in 3D program

Cathedral made in my 3D engine

Answer 1

You need to split your triangles so that they are approximately the same size - regardless of whether you are sorting yourself or using the z-buffer. Unless, of course, the z-buffer algorithm also breaks long thin triangles into you.

The problem is that if you have small compact triangles and some long thin ones (for example), the algorithm will skip classifying long thin ones most often. If you use the midpoint of the triangle, there will be points of view where it will be considered “in front” of the more compact, if in fact, if it really stands. Take this top view down, where + represents the midpoint.

  o -+- 1 -----+------ 2 -+- 3 * 

Looking from * to o , the large triangle (2) can be interpreted as being in front of the small triangle (3) and, therefore, be drawn on top of it.

If (2) was broken into 3 or 4 smaller triangles, then z-buffering will work longer.

Answer 2

You can choose:

• Separate your grids so that you can sort each polygon reliably (but there are still terrible edge cases that you may or may not see).

• Use Z-Buffer , which is supported by all graphics hardware and is essentially free.

Answer 3

The angular case, which complicates any triangle sorting algorithm, is represented by the following diagram:

Each of the triangles is in front of one triangle and after another. I needed to do very simple tricks in inkscape to create this diagram.

It’s easy to organize polygons in 3D, so you have a loop in the “before” column. To solve this problem, your algorithm would need the ability to divide the triangles by breaking the loop.

This is one of the reasons why Z-buffers are so popular (that they are easily accelerated in hardware).