The one important thing I forgot to mention is that my script, this page, and an example .blend are avaliable at http://www.oocities.org/z3r0_d/files/sortFaces.zip

Making translucent faces render correctly

Theory

Translucent faces in blender are rendered in the order they appear in an object.  (The order different objects are rendered currently cannot be controlled. ) Ideally they would be rendered furthest to nearest, so that if they were all opaque only the nearest faces would be visible, and if they were not they would appear to overlap correctly.  

The problem

Example of incorrect ordering in game engine	Example of correct ordering	Explanation
		In both images the mesh is the same, but the ordering of the faces is different.  To emphasize this the faces at the bottom are less green than the faces nearing the top.   In the left image the faces are ordered from the top to bottom.  Notice how the faces at the bottom are rendered on top of (after) the faces of a lighter green.  This is not happening in the image on the right because the faces are being drawn from the bottom to the top, and therefore the faces that are higher up seem on top of the faces lower down.   More problems if the faces in this example were made to exist only once, and all set to twoside (double sided) problems would be encountered from some points of view, and not others.   The tree on the left would appear correct from the bottom, and the tree on the right incorrect from the bottom, so in the end neither would be completely correct.

The Solution

My solution is to find an order that will work from all points of view, by considering that faces are only visible from one side, and sorting the faces in a manner that would always have the translucent faces overlapping correctly.  

The abstract of my algorithm is that it finds the faces that needs to be drawn before a particular face (they are behind, and that face is in front of), and puts the faces back into the mesh in an order that allows all required faces to be drawn before a particular face. 

More problems that are encountered

Consider this example:

The aqua lines are the face normals, and each face is only visible from the side in which the normal points.  I will be referencing the faces by the blue letters.  They are extruded along the axis perpendicular to the screen.  

Ponder this:  

• Face B can be seen through Face A.  
• Face C can be seen through Face B.  
• Face D can be seen through Face C.  
• Face A can be seen through Face D.  

or to my script:

• Draw face A Before D Before C before B before A

There is a problem with this which there is no (reasonable) solution for.  

Another Example

My script creates a list of faces that need to be drawn before each face which may make this problem easier to understand.  The top row is the face, the second is the face that needs to be drawn before for this mesh to render correctly.  

... or not.  This table simply shows the face that needs to be drawn before another face because it MIGHT be visible through it.  For example Face C can be visible through Face A.  From some points of view it isn't, but from some it is.  

So what is the problem here?  It ends up happening that face A must be drawn before C which must be drawn before B which must be drawn before D which must be drawn before A, which is not possible. This stuff can get complex quick.  

A simpler example

This one is pretty simple.  Part of face B is visible through face A, and part of face A is visible through face B.   Yet again this will not work, but this one is easier to spot, and easier to avoid.  

Things that work

The simplest solvable case is one only a little more complex than the tree shown above.  

A table of faces that must be drawn before looks like so:

or in other words:

• Faces B, C, and D are visible through A
• Faces C, and D are visible through B
• Face D is visible through C
• There are no faces visible though D

So the order the faces should be drawn is D, C, B, A.  

I would like to continue rambling on my script again, as this is a good transition.  Notice how face D requires no faces to be drawn before it.  This is how my script puts the faces back into the object in the correct order (when possible).  If face D were added back into the object, and each reference to it as being needed to be drawn before were removed the result would be this:

Face	A	B	C
Draw Before	B	C
	C

Notice how face C now has no faces required to be drawn before it, so I repeat for face C, which yields face B, for which I do the same, yielding face A, and my proper order.  D, C, B, A.  

A more complex case

This one can be more easily explained in an abstract manner.  If the camera were inside the innermost triangle of faces (A, B, C) it would not be able to see faces X, Y, Z because they are oriented away from that area.  If the camera were outside of X, Y, Z it would be able to see some of A, B, C, but it would always be behind [the visible faces of] triangle X, Y, Z.  This creates the solution that faces A, B, C must be drawn, then X, Y, Z.  The table for these faces would look like:

Running through the same algorithm mentioned above for adding faces would do what I desire.  

Notes

the situations I have shown to not work, and to work on a plane also apply in three dimensions.  For example the inside/outside situation applies in spheres, one with normals pointing inwards, the other outwards.  

Also, the spaces I have put in are there merely to aide in making my point visible.  The previous example would work just as well if the inside triangle appeared to share edges with the outer triangle.  

Using my script

It is all pretty simple.  First your object must be prepared.  This involves a few steps

1. Try to expect how your object should be properly sorted, and what problems may arise.  My script doesn't really aide in finding problems, it just complains that they are there
2. Convert everything to triangles (my algorithm requires planar faces, this will guarantee them, but quads may work as well)
3. If you want double sided faces, select your geometry you want double sided (in edit mode), duplicate it, and flip it's normals. 
4. Select your object
5. Press [alt] + [P] in the script window to run the script. 
6. Wait (check console for updates).  More than 1000 faces may take some time, more than 10 000 may take hours. 
7. If the text window turns red it has failed, and I don't really have a solution for you (yet).  If the console prints of finishing the script, doesn't complain (except about quads), and the text window is not red, success has probably been reached. 

If it works, good, if it doesn't try to think about why.  There are many more reasons it could fail that I have mentioned here, but I believe these are the most likely. 

The one important thing I forgot to mention is that my script, this page, and an example .blend are avaliable at http://www.oocities.org/z3r0_d/files/sortFaces.zip