9

I'm building a small 3D engine for a game I'm working on. I've got my basics sorted: textured triangles with backface culling. However depth sorting is proving to be a difficult problem.

I'm calculating the face Z by averaging out the 3 points that make up the triangular face. The longer faces sometimes overlap the smaller faces since they have a larger Z value and therefore rise up in the depth sorted display list.

How do I fix this? I'm sure there are known depth sorting techniques if I can only get some practical help in programming them. I've build the render pipeline myself so I have access to all the required data - triangles, points, textures, UV coordinates, etc.

Cathedral rendered in a 3D program

alt text

Cathedral rendered in my 3D engine

alt text

Rob Hruska
  • 118,520
  • 32
  • 167
  • 192
Robin Rodricks
  • 110,798
  • 141
  • 398
  • 607

3 Answers3

7

You need to subdivide your triangles so that they are all roughly the same size - regardless of whether you do the sorting yourself or employ a z-buffer. Unless, of course, the z-buffer algorithm also splits the long thin triangles up for you.

The problem is that if you've got some small compact triangles and some long thin ones (for example) the algorithm will miss classify the long thin ones more often than not. If you use the mid point of the triangle there will be view points where it will be regarded as "in front" of a more compact one when in fact if really is behind. Take this top down view where + represents the mid point.

            o

-+-            1
-----+------   2
         -+-   3

*

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

If (2) was split into 3 or 4 smaller triangles then the z-buffering would work more of the time.

ChrisF
  • 134,786
  • 31
  • 255
  • 325
  • Is there any way I can bias the Z-sorting routine to take the triangle area into account, without having to split tris? – Robin Rodricks Sep 18 '10 at 17:58
  • 2
    Incorrect. This is exactly the problem that Z-buffering solves. Z-buffering is per pixel and is independent of polygon size (it happens to far down the pipeline to even know). The problem you describe is only applicable to polygon sorting, or if you're rendering non-opaque polygons. Precision issues are relevant to z-buffering and there's a good intro here: http://www.sjbaker.org/steve/omniv/love_your_z_buffer.html – Justicle Sep 18 '10 at 22:11
  • What Justicle said. Additionally, if you need z-sorting (for instance for transparency), a computationally efficient way to z-sort is to use a BSP tree. – Kos Nov 21 '11 at 18:08
  • @Kos - if you have a static scene then a BSP tree is the right way to go. This covers the general case of moving objects. – ChrisF Nov 21 '11 at 20:24
  • Z-buffering only works if all the triangles are a similar size. If any are long and thin you will get this problem. – ChrisF Nov 21 '11 at 20:39
5

You choices are either to:

  1. Subdivide your meshes so that you can sort each polygon reliably (but there are still horrible edge cases that you may or may not see).

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

Justicle
  • 14,761
  • 17
  • 70
  • 94
  • Lots of notable 3d hardware does not support z buffering. Next time you're writing some PS1 homebrew you had better check yourself... – fabspro Aug 11 '22 at 00:58
3

The corner case that complicates any triangle sorting algorithm is represented by the following diagram:

unsortable triangles

Each of the triangles is in front of one triangle and behind the other. I had to do some very simple tricks in inkscape just to create this diagram.

It is not hard to arrange polygons in 3D such that you have a cycle in the "in front of" graph. To solve this problem your algorithm would need the ability to subdivide the triangles to break the cycle.

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

Mutant Bob
  • 3,121
  • 2
  • 27
  • 52