z sort
(Warning! this will be technical mumbojumbo)

In real time computer graphics one thing has given headaches to artist for years: Z-sorting (iow. Z-buffering). Everything goes great until you need to sort objects on screen. It simply eats your CPU. In AS3 this is a huge bottle neck. Yeah the drawing is rather slow but sorting is even more slow. If the challenge is demanding you just need to be equally smart.

As you may have noticed in my works the z-sorting doesn’t seems to be very big issue. For example the GameOfLife3D rolls 13824 particles and does dozen other stuff as well. In worst case just the sort can take up to 40ms in every frame.

When creating an engine of 3D the handling and z-sorting of objects should not thought as separated blocks. To gain performance every piece need to work together. The perfect symbiosis has to be found to serve all step of the system.

I build a test that sort list of objects that have X,Y,Z -coordinates and parameter i. Task is to z-sort objects and set i to z. In every test coordinates are set to same to have fair results. I added all z-sort methods I could find.
Here are average results with 100000 objects (click on them to stop the process):

Vector native sort-method + for-loop: 327ms
Vector shellShort-method + for-loop: 207ms
Array native sort-method + for-loop: 328ms
Array native sortOn-method + for-loop: 54ms
Jedi+Voodoo sorting and handle method: 4ms

Cut the bullshit and tell us how!

Michael Baczynski introduced this code back in 2007 and I think it’s extremely weird that it hasn’t been noticed more widely. I was convinced about the power of linked lists after reading his post and been using them ever since. I build the evo3d and evoCunningParticleEngine based on doubly-LinkedLists. He also shows a very elegant method for sorting called InsertionSort and boy it’s fast when used right.

The beauty of it is that it doesn’t do anything unnecessary. Here’s the lines I use on test:

var f:Particle3D = first;
var n:Particle3D, j:Particle3D, p:Particle3D, c:Particle3D;
c = f.next;
while(c) {
        n = c.next;
        p = c.prev;
        if (c.z > p.z)
        {
                j = p;
                while(j.prev)
                {
                        if (c.z > j.prev.z)
                        {
                                j = j.prev;
                        }else{
                                break;
                        }
                }
                n ? (p.next = n, (n.prev = p)) : p.next = null;
                (j == f) ? (c.prev = null, (c.next = j), (j.prev = c), (f = c)) : (c.prev = j.prev, (j.prev.next = c), (c.next = j), (j.prev = c));
        }
        c = n;
}

As you can see if the objects are in order there’s only one comparison and everything happens inside linkedlist while loop that is the fastest way to loop in as3. Also the benefit of this is that it provides the first object in linkedlist and it can be used to loop again in linkedlist while loop.

while(first)
{
        first = first.next;
}

There is a but on this method. If objects are completely mixed this insertion sorting is by far the slowest. That’s why list has to semi ordered in the first run. This is not a problem in 3d when you are moving using camera and objects doesn’t swap too much. All the models should be preordered by other methods for the first time. After that insertion sort will take the rest and give maximum performance.

Yeah I know the test isn’t very good since all objects are in order all ready :) Anyway the linkedlist + insertion sorting is the fastest there is since it only swap those that need to be swapped and does it inside the fastest loop possible.
You can check out the sources here and try for your self.
If you find a faster way to do this I would really appreciate if you let me know how.

— UPDATE 06:32pm 8.12.2009 —
Rob Bateman responded on this topic by explaining his method on Z-sorting.
Radix Sort is something I didn’t even knew exist until now :) A must read post.