Z-sorting Indices For drawTriangles()

While constantly improving 3DDM (drawTriangles() version soon to be released), I was looking for the fastest possible solution to render simple 3D object. It soon appeared to be drawTriangles() – the native ActionScript 3 method, that let you make illusion of 3D object based on deforming your texture. In fact native ActionScript contains a lot of useful and fast classes to work with 3D like: Utils3D, Vector3D, Matrix3D, PerspectiveProjection… so you do not need to create your own basic 3D engine tools. One thing that it does not contain is z-sorting. Z-sorting is very tricky job, that is why modern 3D engines let you decide which sorting method to use with your scenes (faster vs. precise). For my needs it is enough to use simpliest z-sort possible, based on projected max z coordinate of face (3 vertices).

Before continue reading, make sure you understand the basics of Using triangles for 3D effects, Transforming bitmaps, UV mapping and Culling. Everything is very good described by Adobe.

Defining

In order to apply texture with drawTriangles() we have to define vertices, indices (used for z-sort) and uvtData.

var vertices:Vector.<Number>;
var indices:Vector.<Number>;
var uvtData:Vector.<Number>;

While indices is Vector it is not easy nor fast to order it by its corresponding vertice’s-es z-coordinates. Lets help it a bit with linked lists (double linked lists). I have used merge and insertion sort methods, both are very fast (merge is faster for unsorted lists, insertion for nearly sorted lists). Both sorting methods were depricated and replaced by radix sort (by Rob Bateman), the speed is enormous, the disadvantage of radix sorting is that it only sorts using integers, but that is not a problem in our case. I have created Triangle class, that handles all the necessary for you, from creating linked list up to z-sort indices.

Z-sort

Before z-sorting starts we have to transform the scene – recalculate coordinates based on viewer position/rotation etc.

var projection:PerspectiveProjection = new PerspectiveProjection();
projection.fieldOfView = 60;
var projected:Vector.<Number> = new Vector.<Number>();
var matrix3D:Matrix3D = new Matrix3D();
matrix3D.appendRotation(-rotX, Vector3D.X_AXIS);
matrix3D.appendRotation(rotY, Vector3D.Y_AXIS);
matrix3D.appendTranslation(0, 0, 550);
matrix3D.append(projection.toMatrix3D());
matrix3D.transformVectors(vertices, projected);

…now we can sort indices using Triangle built in method (zSortMerge or zSortInsertion)

if(!firstTriangle) // create linked list if does not exist
    firstTriangle = Triangle.create(indices, projected);
else // or update coordinates if it exists
    firstTriangle.vertices = projected;
var indices:Vector.<int> = firstTriangle.zSort;

Render

Final step before rendering is projection. To project means to transform 3D object into 2D representation based on the same viewer position/rotation. Once we have vertices and uvtData defined and indices sorted we can render:

var projected:Vector.<Number>;
Utils3D.projectVectors(matrix3D, vertices, projected, uvtData);
graphics.clear();
graphics.beginBitmapFill(image, null, false, true);
graphics.drawTriangles(projected, indices, uvtData);

Other sorting methods

I have made merge and insertion sort methods depricated, while radix sort method works much faster for our needs. Anaway I am including those methods below:

Merge sorting by Polygonal

public function get zSortMerge():Triangle
{
    var h:Triangle = this;
    var p:Triangle, q:Triangle, e:Triangle, tail:Triangle;
    var insize:int = 1, nmerges:int, psize:int, qsize:int, i:int;
    while(true)
    {
        p = h;
        h = tail = null;
        nmerges = 0;
        
        while(p)
        {
            nmerges++;
            
            for (i = 0, psize = 0, q = p; i < insize; i++)
            {
                psize++;
                q = q.next;
                if(!q)
                    break;
            }
            
            qsize = insize;
            
            while(psize > 0 || (qsize > 0 && q))
            {
                if (psize == 0)
                {
                    e = q; q = q.next; qsize--;
                }
                else if (qsize == 0 || !q)
                {
                    e = p; p = p.next; psize--;
                }
                else if (p.z - q.z >= 0)
                {
                    e = p; p = p.next; psize--;
                } 
                else
                {
                    e = q; q = q.next; qsize--;
                }
                
                if (tail)
                    tail.next = e;
                else
                    h = e;
                
                e.prev = tail;
                tail = e;
            }
            p = q;
        }
        
        tail.next = null;
        if (nmerges <= 1)
            return h;
        insize <<= 1;
    }
    return null;
}

Insertion sort method by Simppa

public function get zSortInsertion():Triangle
{
    var f:Triangle = this;
    var c:Triangle = f.next;
    var n:Triangle, j:Triangle, p:Triangle;
    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;
    }
    return f;
}

You may find more sorting methods in as3ds project (no longer developed).

In the next post I am going to post some benchmark results and example.

4 comments so far

  1. stanar007 October 11, 2010 03:21

    Great work Josef! Can’t wait to see examples

  2. [...] on my previous post about z-sorting indices, I have created a superfast 3DDM version using drawTriangles(). The following example renders [...]

  3. Jozef Chúťka October 11, 2010 11:17

    @stanar007, thankx, the example is ready on http://blog.yoz.sk/2010/10/superfast-3d-scene-without-3d-engine/

  4. tamt October 28, 2010 11:08

    great work. awsome

Leave a comment

Please be polite and on topic. Your e-mail will never be published.