opengl z-buffer alpha sorting

[3hM2Nwbp]

I have a quick question if anyone's worked with this before...

First off, I'm taking a side-trip from my 'norm' and writing a game! The game is (hopefully) going to be something a bit like DOOM95. Here's a pic of an outside map section. ( http://imageshack.us/scaled/landing/402/gameui.png )

Other than artistic ineptness, I'm wondering if I'm on the right track with sorting my polygons. As of now, I'm using the distance between the poly's center and the view position. It seems to work fine with the ground / walls / ceilings, but I'm a bit worried about what will happen when I start placing some more intricate models.

Has anyone tried center-to-camera sorting on their alpha polygons in a more intense scene than the one above?

Perhaps if I use care to keep my models far enough apart so that their calculated centers don't fall victim to inaccuracies?

[tition]

Diclaimer: I have never done anything with 3D graphics.

Nevertheless, you should sort your polygons according to whether they cover one another. How many vertices do your polygons have ? Are they all triangles? Quadrilaterals?

[Edit:]
Triangles can be compared (operator >) relative to which should be drawn first on the screen. However, the comparison is not good: it might so happen that triangle A > triangle B> triangle C > triangle A (think of three intertwined triangles).

However, if your entire scene has only two triangles, you can always draw one first and then the other, without fear your picture will be inaccurate.

[helios]

A better distance function is the distance to the view plane, aka the absolute value of the z component in the view coordinate system.

EDIT:

Triangles can be compared (operator >) relative to which should be drawn first on the screen. However, the comparison is not good: it might so happen that triangle A > triangle B> triangle C > triangle A (think of three intertwined triangles).

However, if your entire scene has only two triangles, you can always draw one first and then the other, without fear your picture will be inaccurate.

Actually, this isn't necessarily true. Imagine two triangles, one red and one green, in front of the camera with their vertices at the exact same positions. Now imagine one of them is rotated slightly along the vertical axis, and the other is rotated by the same amount in the opposite direction. Now in some pixels the red triangle should be in front of the green triangle, but in others the green one is in front. If you simply draw one and then the other, you'll end up with a mostly red or mostly green shape, rather than something half green and half red.

[3hM2Nwbp]

think of three intertwined triangles

I'd rather not. I'm very scared of hairy spots, especially if they're in 3 dimensions. What I'm doing now is approximating the center of each object that I'm rendering (floors, walls, roofs, etc) and sorting them by approximation, not by individual polygons. This is the first 3D game that I've made, so I'm pretty much asking: "Am I doing this right?" It seems to be working now, but I really don't want to go much farther until I'm reasonably sure that it will keep working as I add a reasonable number of objects to the mix.

My reasoning here is that if the bulk of an object is behind another, then I should be able to assume that the object is really behind it so long as I don't go crazy with overlapping models.

[helios]

If you want to keep things simple, just don't use alpha blending. You don't need to draw your polygons in any particular order (unless they use alpha blending), as the hardware can handle the details of rendering.

[3hM2Nwbp]

helios wrote:

If you want to keep things simple, just don't use alpha blending.

I could just make sure no overlapping happens though, correct? Would approximating centers work then?

IE. I have a model that is (x, y, z) units in volume (meaning the center is at (x/2, y/2, z/2)), I just need to keep it that many units away from any other model in the scene, comparing the approximated centers for each thing that I'm rendering against the viewing position. I'm planning on only having static models in a scene and rendering sprites for the various movable enemies.

[tition]

Actually, this isn't necessarily true. Imagine two triangles, one red and one green, in front of the camera with their vertices at the exact same positions. Now imagine one of them is rotated slightly along the vertical axis, and the other is rotated by the same amount in the opposite direction. Now in some pixels the red triangle should be in front of the green triangle, but in others the green one is in front. If you simply draw one and then the other, you'll end up with a mostly red or mostly green shape, rather than something half green and half red.

Of course, but these triangles are then intersecting one another, ("they are not solid"). I presume OP wants to draw triangles that cannot intersect (think of them made of some solid material).

What I was pointing out is that even if the triangles are solid and do not intersect, you still cannot order them.

If your scenery has only two triangles that do not intersect pairwise, we could cook up formulas for determining which of two triangles must be drawn first quite easily.

Would approximating centers work then?

Nope, you can cook up very simple examples (two rectangles perpendicular to the ground) in which this will fail.

[Edit:]
How I would go about determining which of two solid shapes comes first? I would take all of the sides of the solid shapes and compare those. If all sides of a solid convex body are in front of all sides of another convex body then the first convex body is in front of the second. A parallelepiped has 6 walls, so that is an easy function.

How I would go about determining which of two solid pairwise non-intersecting polygons comes first? I triangulate each polygon, and boil down the problem to one for triangles. A rectangle can be triangulated in two triangles.

Now, to solve the problem for two triangles. I would go about like this. 1) Project each edge of each triangle on the viewing surface ("the eye of the beholder").
[Edit:] Thanks to helios for the correction:
If the edges do not intersect pairwise you are done (neither of the objects lies in front of the other).

1.5) Find whether a vertex of one triangle is contained in the other triangle. There is a ready formula for that.

2) Find the first intersection (in a non-corner point!) You need to check 9 cases here (each of the 3 edges of the first triangle with each of the 3 edges of the second triangle).
3) Find the two corresponding point on the original (non-projected triangles). Those will lie on the same ray that projects them onto the same point on the surface of the "eye of the beholder".
4) Determine which of the two points is closer to the point of projection.


Note that the surface projection onto the "eye of the beholder" is usually done like this. You select a point "the center of your eye". Then you put a canvas ("the surface of your eye") in front of the "center of your eye". This canvas is usually rectangular and represented by the monitor of your computer.
Then a point in the scenery is projected by drawing a segment between the point and the center of your eye, and determining at which point does that segment intersect "the surface of your eye".

[3hM2Nwbp]

Nope, you can cook up very simple examples (two rectangles perpendicular to the ground) in which this will fail.

I'm having a tough time picturing such a case in my head...suppose this is why I normally don't do games.

[helios]

Of course, but these triangles are then intersecting one another, ("they are not solid"). I presume OP wants to draw triangles that cannot intersect (think of them made of some solid material).

Oh, okay, now I get what you mean. I interpreted your example as overlapping polygons, rather than as non-overlapping polygons with overlapping projections.

two rectangles perpendicular to the ground

I don't see this one.

1) Project each edge of each triangle on the viewing surface ("the eye of the beholder"). If the edges do not intersect pairwise you are done (neither of the objects lies in front of the other).

A triangle could completely occlude another triangle, such that there are no intersecting edges.

[tition]

Think of this shape:

_______________________________________
        |          .

The dot represents your viewpoint. The two lines (one very long horizontal and one short vertical) are two walls. From your viewpoint, you need to draw the short wall first second, i.e., on top of the long wall, but the center of the long wall is closer.

A triangle could completely occlude another triangle, such that there are no intersecting edges.

Oh shoot... my bad!!! Editing back !

[3hM2Nwbp]

Oh, I see what you're saying. It's my fault for forgetting to state that I'm using a tile-based approach where each tile is 1 unit x 1 unit, so at most I'm dealing with walls of 1 unit long. I have a terrain format that I read from and generate the coordinates for the entire scene, but only feed opengl tiles that are within X units of the camera (those inside of zFar). On each frame that's drawn, I resample which tiles should be in view, sort their polygons based on their centers, and feed them to opengl. The part that I was worried about was introducing other models. It seems to me that as long as I make sure nothing geometrically overlaps, then the center approximation should work. I'd sure like to be told otherwise now than when I find out later though!

[NGen]

You're looking for the painter's algorithm: http://en.wikipedia.org/wiki/Painter's_algorithm

There are a LOT of different articles on it due to the complications that have been discussed here. This one seems promising, though:
http://www.sea-of-memes.com/LetsCode4/LetsCode4.html
Not because I've read through it much, but because he tends to be pretty reliable on his blog entries and it also comes with source code.


EDIT: Only just noticed the picture, so this doesn't necessarily apply to your game. For anyone else that's curious, you're free to look here anyway.

If you want to be cheap, then you can try this:
There's a very simple (but inefficient) workaround ONLY for polygons that either have fully-opaque textures or no texture (single color). Polygons with varying levels of translucency are allowed, but no vertices can be fully opaque if that's the case. What I mean is, no gradients from opaque to transparent/translucent.

If you meet those requirements, cool. You can get lazy.

The way that the algorithm works is:

disableColorWrite ();
enableDepthWrite ();
drawAllOpaquePolygons ();

enableColorWrite ();
disableDepthWrite ();
drawAllPolygons ();

Write in the depth values of the polygons that matter for depth clipping (only the opaque ones, since we don't clip against translucent ones), without writing into the color buffer, and then render everything since the depth buffer for the scene has already been generated. Polygons will be clipped as appropriate regardless of order. Note that this requires your depth comparison function to be LEQUAL for OpenGL, or GEQUAL for Direct3D.

This is the code from a rendering function I wrote for some 3D modeling software (never finished) a while back, which used this algorithm. Second parameter of RenderViewContents() states whether or not to draw translucent objects as well.

ApplyMatrixConfigurations ();

glDepthMask (GL_TRUE);
glColorMask (GL_FALSE, GL_FALSE, GL_FALSE, GL_FALSE);
g_SourceView.RenderViewContents (this, false);

glDepthMask (GL_FALSE);
glColorMask (GL_TRUE, GL_TRUE, GL_TRUE, GL_TRUE);
g_SourceView.RenderViewContents (this, true);

While writing this, I also realized a more efficient algorithm:

enableDepthWrite ();
enableColorWrite ();
renderAllOpaquePolygons ();

disableDepthWrite ();
renderAllTranslucentPolygons ();

Meets the requirement that translucent objects blend for both opaque and translucent objects, since they rasterize for all points that do not clip against opaque and aren't clipped by other translucent polygons. Opaque polygons are not clipped by translucent ones either. This still has the limitation of polygons that are either fully translucent or fully opaque. Not suitable for translucent textures.