Sorting primitives - according to which value???

Hi there!

I have been away from these forums for quite a while but I have a new problem with one of my 3D engines and need some help from experienced users.

My problem is a “classic”: I have implemented transparency in my engine and I can’t seem to get sorting to work properly. In order to keep things simple, I am only working with triangles.

I have read many topics on the subject in these forums but couldn’t find the answer to my question: how should I sort my primitives to get the “correct” result? I have tried the following:

1. Calculate centre of triangles in World Space Coordinates, sort according to Z (distance from vertex to view plane).
2. Calculate centre of triangles in World Space Coordinates, sort according to X^2+Y^2+Z^2 (square of distance from vertex to viewer).
3. Project triangle vertices (Projection Matrix * Modelview Matrix * vertex), sum up Z values of projected vertices, divide by 3, sort according to this value.
4. Project triangle vertices (gluProject), sum up Z values of projected vertices, divide by 3, sort according to this value.

I have also tried other methods but they were so dumb that I won’t even mention them.

The problem is that whichever technique I use, I always get artefacts. My “test case” is a box made of 6 faces (12 triangles). Whatever I try, I always find a “viewpoint” (position/orientation) that has some kind of problem.

Is it possible for one of you who has implemented such a thing is one of his own engine to tell me how to do this properly? I have done many searches on the web or here but couldn’t find a definitive answer…

Thanks a lot.

Regards,

Eric

[This message has been edited by Eric (edited 10-08-2003).]

Hi,
Sorry, I have not implemented this myself, but I thought you wanted to sort based on the furthest z value (the z value of the furthest vertex from the viewing plane).

Well, I have read many things and here is what I found:

1. Sort according to the distance between the closest vertex and the viewing plane.
2. Sort according to the distance between the farthest vertex and the viewing plane.
3. Sort according to the distance between the triangle center and the viewing plane.
4. Sort according to the distance between the closest vertex and the viewer.
5. Sort according to the distance between the farthest vertex and the viewer.
6. Sort according to the distance between the triangle center and the viewer.

I have tried all of this and there is always a problem on my “simple” box example (when you think about it, it is actually easy to understand why the closest/farthest vertex approach can’t work in this case).

I am really wondering if there is a “general” solution to this problem.

[This message has been edited by Eric (edited 10-08-2003).]

Two approaches that works :

1/ BSP
2/ Depth peeling

SeskaPeel.

Last time I had a look at it, Depth Peeling was interesting but much too slow even for my GF4. I doubt it will be of more use to my clients.

As far as BSPs are concerned it is true that I could probably use them but as the software I am working on is some kind of “modeller”, I need to be able to recalculate these in real time as the geometry is modified by the user. I am not sure if this is very practical when you get hundreds of thousand of triangles in the scene.

That being said, I’d be happy to hear from other contributors if they think this is my only solution.

Regards,

Eric

How about the distance between the viewer and the triangle as a whole? http://www.magic-software.com/Documentation/DistancePoint3Triangle3.pdf

– Tom

Tom,

That may be a really good idea indeed. I’ll try to implement it as soon as I understand the paper.

While I am doing that, I am still interested in knowing how other people actually do that kind of thing. I thought it would be easy (silly me!) but it looks like it can get much more complicated than I initially thought.

I forgot to mention that my triangles will never intersect, just in case it matters!

Regards,

Eric

There is no general solution because in general, polygons are not ‘well ordered’ objects.

BSP trees are created by splitting polygons into ‘nearer’ and ‘farther’ groups using planes until the question ‘is this polygon closer or farther than that polygon’ can be answered uniquely from any perspective.

Nearer and farther do not refer to distance in this case, ‘how far away is that polygon’ is actually an undefined question since distance can only refer to the length of a line between two points. Polygons are not points.

Near and far in the case of polygons refers to whether a polygon is on the far side or near side of a plane. A polygon on the far side of a plane should be drawn before a polygon on the far side even if the ‘distance’ to the viewer is ‘closer’ (which ever points on the polygon you choose to use to define ‘distance’, none of which can ever be perfect).

A BSP tree is built to make sure that all polygons are only on one side of a plan, so any polygons crossing a plane are split.

I am probably being confusing. Just remember that there is actually no well defined thing as distance between polygons or between polygons and a point. And, one way to tell which order to draw polygons is to put a plane between each polygon and define ‘far’ as being on the far side of the plane from a given perspective. One way to put planes between polygons is to build a BSP tree.

Nakoruru,

Thanks a lot for this detailed explanation. I suppose then that all software (games or professional applications) use some kind of BSP in order to render transparent objects properly.

I am just wondering whether this will be very practical in my case. I can have thousands of objects each of them with thousands of triangles (well, the user decides what he is modelling! ). Maintaning a BSP tree in this case may be a lot of overhead. Or am I completely wrong?

Regards,

Eric

[This message has been edited by Eric (edited 10-08-2003).]

Even if the distance between the viewer (a point) and the triangle was something that could be defined in a meaningful way, does it really answer the question ‘what order should I draw these triangles?’

‘distance’, even if we can imagine it was defined perfectly, does not definitivly answer that question because even for a polygon on which every point was closer than some other polygon (unambiguously closer) to the viewer, could still be drawn after the farther one in some cases and result in a correct image.

One correct answer (perhaps the only?) is to find a plane that fits between the two polygons and consider the one on the far side of the plane to be farther away, and thus needing to be drawn first.

This is the theory behind BSP trees, and I am presenting the theory because maybe it can help original poster think about this problem in a more correct way, so he can find a solution that works.

Drawing arbitruary transparent objects from back to front correctly will definitely require the splitting of some polygons, like any space partitioning algorithm does.

I bet that building a BSP will be faster than doing an imperfect distance formula for every polygon, especially considering that it only has to be done each time you change the model as opposed to every time you change perspective.

I also assume that the transparent view is just one mode of the modeler, so it would only have to be done when the user switches.

Just some ideas.

[This message has been edited by Nakoruru (edited 10-08-2003).]

Originally posted by Eric:
The problem is that whichever technique I use, I always get artefacts. My “test case” is a box made of 6 faces (12 triangles). Whatever I try, I always find a “viewpoint” (position/orientation) that has some kind of problem.

I’ll suggest something for the cube case and propose that it’s applicable to any object, but you’ll have to prove it to yourself. It may not be immediately intuitive, but you’ll figure it out.

For the cube, there are exactly eight unique correctly-sorted polygon orders, depending on its current orientation w.r.t the viewer. Each of those describes the correct rendering order (assuming no intersecting triangles) from a particular set of viewing angles, subtending a 90 degree arc. The order doesn’t change until you rotate more than 90 degrees.

You can code these eight orders easily by hand (for the cube), or you can build a small BSP tree per object to determine them automatically. Evaluate the BSP tree from the eight major directions and store those rendering orders as your eight lists.

Once you have the eight order-lists, store those as eight triangle index lists and select one based on the object’s current orientation w.r.t. the viewer. Render with that order.

Trick: the correct list can be selected by transforming the “at” vector from the viewer to object into local object coords or any equivalent that determines the true orientation on screen. Look at the signs of X,Y,Z results. There are eight sign-bit combinations for +/- xyz. Convert the eight signs-bits to a number (0-7) to pick from your table of index lists. Obviously, it’s easiest to organize the table so the right list comes out in the right slot based on the +/- signs, not the other way around.

BTW, I’ve used this to optimize rendering of many cubes, where I can construct cubes on the fly with only 6 triangles (12 for transparent ones). Since it can be as simple as a cross product and a table lookup, it’s very fast.

For full-scene transparency, you would then sort by object centers. Assuming objects don’t interpenetrate, this generally works and is very fast, but not perfect. Interpenetration is a potential problem, as is the occasional confusion about which object is in front of which, which comes up more often with widely distributed object sizes (imagine small cube next to big flat plate. small cube can be in front of the plane of, but behind the center of the plate).

For perfect results, use BSP (OIT is too expensive generally) but keep in mind for “perfect” results in a dynamic and potentially overlapping scene, it may require splitting triangles on the fly.

For hybrid results, sort by object centers first, but put any objects which might overlap each other (at least in terms of their bounding sphere|box) into a separate bin for finer-grain testing, such as with a dynamic BSP. If the number of polys is small per tree, it can be very fast.

P.S. there’s also a poor man’s OIT, which involves not sorting by transparency at all, but rendering transparent objects twice, once with z-pass and once with z-fail. The results are very crude, but perhaps reasonable for some cases.

Avi

[This message has been edited by Cyranose (edited 10-08-2003).]

I was thinking his problem was not multiple objects, but rendering a single object without artifacts.

In anycase, for multiple objects, ‘near’ and ‘far’ are also determined by a putting a plane between the objects (this is also used in collision detection to rule out collisions). Everything I said about distance being a bad determiner of drawing order applies to full 3D objects as well.

Originally posted by Nakoruru:
[b]I was thinking his problem was not multiple objects, but rendering a single object without artifacts.

In anycase, for multiple objects, ‘near’ and ‘far’ are also determined by a putting a plane between the objects (this is also used in collision detection to rule out collisions). Everything I said about distance being a bad determiner of drawing order applies to full 3D objects as well.

[/b]

Yes, the first half of my post was related to just the single object case. My main point is that as long as interpenetration is not an issue, pre-computing the intra-object rendering orders is preferable from a performance standpoint. I don’t recommend throwing a large number of dynamic polys into a BSP soup on the fly unless it’s absolutely necessary.

You’re right about distance testing being crude. However, it’s debatable whether it’s faster to use splitting planes for everything vs. using crude distance tests first for the easy cases and special-casing the potential problem cases for more expensive tests.

Avi

If triangles can never intersect, then for any two triangles, one of the triangles will (almost) always be completely to one side of the other (or coplanar at a vertex / along an edge). Say triangle A is “behind” triangle B’s plane. If the camera is also “behind” triangle B’s plane, draw A first; otherwise, draw B first. This is 4 to 7 plane distances per pair of triangles, and can easily be put into a qsort routine.

This test can fail for some triangle pairs, but any such case that I can think of should easily be sorted with the average vertex distance to the viewer. The test fails when the line formed by the intersection of the two triangles’ planes cuts through both triangles. For example, this could happen on a “string mobile”, where two triangles are hung from a string one below the other and each has some twist with respect to the other. Some amount of “tilt” can be added to the twist and the line of intersection still cuts through both triangles.

I’ll admit that some sort of distance test will work most of the time. It is just that Eric seems to be looking for a perfect result. ‘Crude’ and ‘almost’ do not fit my idea of perfect.

I wonder, how fast can a BSP tree be built for a 100,000 polygon model on a modern >2Ghz computer?

Maybe if Eric explained more about how his program works we could get a better idea of what is optimal. I seem to be assuming that building a BSP is no big deal, while everyone else is objecting. But we really don’t know how often it would need to be done or when.

I was assuming that the user would edit in a wireframe mode, and view in flat, smooth, and transparent modes.

A BSP would only have to be built after an edit and only if a window contained a transparent view. If the BSP builder had its own thread and took, say, half a second, then the transparent view would update 2 times a second while the user was editing, but at full speed while the user was just rotating/zooming it. Of course, it wouldn’t be fast enough to edit in a window showing a transparent model.

I am making all sorts of assumptions here.

Originally posted by Nakoruru:
[b]I’ll admit that some sort of distance test will work most of the time. It is just that Eric seems to be looking for a perfect result. ‘Crude’ and ‘almost’ do not fit my idea of perfect.

…

I am making all sorts of assumptions here.

[/b]

Yes. If he wants a perfect result, he should probably use depth peeling. It’s pixel accurate without splitting polygons or requiring pre-computation.

In my mind (and in my code), the distance test, while crude, is only a first step. Once objects are distance sorted, it becomes easier to find overlapping bounding boxes and do more expensive tests on just those special cases.

If two objects potentially overlap, throwing just those triangles into a BSP can be much better than evaluating a BSP for the entire scene (assuming it’s somewhat dynamic, and if it’s not, you can pre-evaluate the BSPs as I mentioned). Personally, I don’t even bother with that since I can guarantee no interpenetration.

Some methods may waste time figuring out precise in-front/behind releationships for objects or polygons that don’t even overlap in image-space. Real-time algorithms often take this sort of approach: do a cheap/crude first pass and handle exceptions specially.

Anyway, we’re offering a range of suggestions. Eric or anyone reading this can pick and choose given the various caveats and performance expectations.

Avi

P.S. I’m pretty sure that whether you use “separating planes” or use one triangle as the plane to test another against, it’s called BSP – splitting the universe into two spaces with one or more dividing planes. There are many variations on this theme, including b-rep, axial planes, and so on. It mostly comes down to how you pick the planes.

[This message has been edited by Cyranose (edited 10-09-2003).]