Once the SVG elements have been transformed and moved in a 3 dimensional spaces, next step is to sort them in order to manage their superposition.

Each time the SVG elements have been modified, an algorithm is applied on them to change their order. The element which is closer to the observer is placed at the end.

SVG sorting

In order to sort the SVG elements, several algorithms are available :

  • averageZ, the simplest, will just calculate the average z coordinate of the points of the face during the transformation. The faces are then sorted depending on that value.
  • oneToAll, default algorithm. At transformation step, the director vector and the center (average coordinates actually) of the face is calculated. When sorting, an iteration on faces compares each one to the already sorted faces. As soon as a closer face is found, the current face is put behind.
  • allToAll : for the ball_3d example, an augmented algorithm is necessary. Indeed, when comparing faces which intersect, you may find that the center of the first face is behind the second face AND the center of the second face is also behind the first face. So, depending on which face is analysed first, the result may be different. In order to avoid that, a double comparison is done.
If no sorting is needed, you can specify "none" as the sorting algorithm.

More technical explanations can be found below.

It is possible to choose the sorting algorithm to use, filling the attribute "z:sortAlgo" of the <g> element, see svg3d for the complete specification of the SVG declaration.

Benefits

The sorting algorithms used here are light, and they do not impact too much the CPU time which is highly used on parsing the coordinates of the SVG elements.

I tried to stay close to usual mathematics methods in order to stay understandable.

Explanation

Each time the coordinates of a point have been retrieved, they are passed to the function transformAndStore() which applies the transformations, and store the 3D resulting point into a variable "points", associated to the SVG element. At the end of the transformation of the whole element, the method setDirectorVector() will calculate the average Z or the director vector of the face, depending on the sorting algorithm selected.

averageZ algorithm

If the algorithm selected is "averageZ", then the method setDirectorVector() only sets a variable z in the Shape object associated to the SVG element.

Then the sort triggered is the method sortFacesAverageZ() which uses the following algorithm :

var i = pathArray.length;
while (i--) {
    var current = pathArray[i];
    var j = indexArray.length;
    while (j && pathArray[indexArray[j-1]].z > current.z) {
        //translates to the right
        indexArray[j] = indexArray[j-1];
        j--;
    }
    //only dumps the indice of the path
    indexArray[j] = i;
}
The backward loop is better for performance, as demontrated there. "indexArray" is the result of that sort, which only contains index of the faces in "pathArray", from the closest to the last. Until a closer face is found, the compared face (pathArray[indexArray[j-1]]) is moved one case to the end of the list.

That average Z algorithm is fast and would work for the cube if no text was put on the faces. But the average z coordinate of the text faces does not correspond to the middle of the face, as the points which compose the text are not equally distributed on that surface. So a text face which should be in front of its cube face can be composed of points which are "in average" behind it, and the order will be wrong.

However that algorithm works for the ball_3d example, whereas the following algorithm, more complex and more "exact", does not work.

oneToAll comparison algorithm

A more scientific algorithm is to calculate the director vector of the face, and the average coordinates of the points which compose it. That way, we determine a rough position and the exact direction of that face.

At sorting, a function isBehind() is called which returns true if "face" is behind "reference" :

function isBehind(face, reference) {
    var u = reference.directorVector;
    var p = reference.center;
    var b = face.center;
    var bpu = (p[0] - b[0]) * u[0] + (p[1] - b[1]) * u[1] + (p[2] - b[2]) * u[2];
    if (bpu * u[2] < 0) {
        return true;
    }
    return false;
}
The variable "bpu" is the scalar product of the vector "bp" and the vector "u".

The idea is to determine if the center of "face" and the observer are on the same side of the plan defined by the "reference". Let us take :

  • A : the position of the observer, whose coordinates are ( 0, 0, -infinite ).
  • B : the center of the "face".
  • P : the center of the "reference".
  • u : the director vector of the "reference".

if AP . u and BP . u have opposite signs, then they are not on the same side of the "reference", and "face" is behind "reference". Let us calculate AP . u, scalar product of the vectors AP and u :

AP . u = APx * ux + APy * uy + APz * uz
Replacing A by its coordinates ( 0, 0, -infinite ) :
AP . u = Px * ux + Py * uy + (Pz  + infinite) * uz
Px, ux, Py, uy and Pz are finite so if uz < 0 then AP . u is -infinite otherwise it is infinite : AP . u has the sign of uz (u[2] in the code). Last step is to calculate BP . u and compare their signs.

The sorting algorithm is the same than for average Z, except that the comparison is done with that isBehind() function.

That algorithm works for the cube and the pyramides but it does not work for ball_3d, as the SVG faces are a lot intersected and built on a circular way. For it, the average Z algorithm works but that is not very satisfying.

allToAll comparison algorithm

When comparing current face to the already sorted ones, it actually determines if the center of the current face is in front of the other one. With ball_3d example, when comparing a face on the right and a face on the left, there are great chances to find two faces that it is not possible to determine if one is behind the other. For example if it compares the two closest faces from the observer, it will find that the center of the face on the left is in front of the face on the right, but it will also find that the center of the face on the right is in front of the face on the left.

Let us take a situation where current face is the closest face on the right and some of the left faces and right faces have already been sorted. That face is very close to the observer, so it should be placed at the beginning of the list. But if last face already sorted is on the left and far from the observer, it may happen that the center of current face is behind that one. So current face will stay at the end of the list, behind other right faces, and the order will be wrong.

The solution implemented here is to compare both faces in both ways (this is why I called the algorithm "allToAll"). If it is not possible to determine if one face is behind the other because the two comparisons return the same result :

continueBrowsing = (comparedIsBehindCurrent ===  currentIsBehindCompared) || comparedIsBehindCurrent;
then it continues browsing, current face is declared in front of compared one, like a default behaviour.

Participation

All those developments are released under Cecill licence.

The project Forms Generator is available on a svn, contact me for more information. In the future, a project might be created on sourceforge.

Projects svg 3d, XSD to RelaxNG converter, javascript SAX parser, javascript RelaxNG validator, javascript datatype library are published on Google code. Project javascript SAX parser is also published on Github.

Requirements

In order to have javascript working as expected, please use last version of firefox.

For the applets, you will need to have java installed on your computer.