Month: July 2010

In 3d one needs to cull back-facing triangles before the render process so as not to render triangles that will never be seen by the observer.

There a couple of ways you can do this and at various stages in the pipeline.

Dotting:
One way is to take the dot product of the triangle’s normal with the vector from the camera’s position (transformed into object space) to the polygon.
(this can be sped up a little by using the vector of the camera’s position to the mesh, then you don’t have to recalculate it for each triangle).

Winding:
this can only be done once all points in a triangle have been projected into screen space (x and y coordinates) and works by determining if the points are in a clockwise or counter-clockwise order.

Pros:
dotting can be done at an earlier stage thus potentially reducing the number of points that need to be projected in the projection stage.
winding is easy to implement and involves very few mathematical operations.

Cons
dotting is slower, well it seems to be in actionscript anyway.
winding, done at a later stage in the pipeline so it potentially misses an opportunity to cull early and save some operations at other stages.

Conclusion:
I have always opted for the winding method because of its ease and speed. Even though have to project EVERY point in your scene before hand, this has never proven to be an issue as projection of many thousands of points seems to be a very quick and easy task. (and I have tried using my own matrix classes, the inbuilt ones and even a pixel bender implementation….all of which laugh at such a task).

Sub-conclusion:
I still think there is room for improvement so time to invent some methods to help speed it up even more.

Result of sub-conclusion:
I was thinking about different ways to speed this up and had a thought while looking at the bounding box around my meshes. With any given mesh you can only ever see at most 3 of its 6 sides and a minimum of 1! So I figured if I could find a simple way to assign each triangle to one of those sides then maybe I could cull whole groups of triangles.

What resulted was a method run after a mesh is created to loop through each of the triangles and assign them an integer id (1, 2, 4, 8, 16, or 32 for bitwise usage later) based on which bounding box side they are most facing.

Then when it came to culling all I had to do was project the bounding box of the mesh, loop through its faces to check their visibility and build a bit mask. Once this is done I could loop through the triangles and before doing a winding check I could use a simple bitwise AND operation: if(triangle.id & mask) == 0), and if it passes that skip the winding check.

Now this worked but the speed up gained was sooooo small it was almost not worth my time 🙁
This is because the current technique will only give the triangle the id of the BB side it is MOST facing, this does not guarantee it is not also facing another side, so it cannot be used to disregard triangles but only skip the winding check. (and only for on average 1/6th of the triangles).

I have tried dotting the face normals with the BB side normals to produce a broader cull but didn’t get it working 🙁

Anyone else got any amazing ideas to help speed up a process that probably doesn’t actually need it?

edit:
here are some images of the culling produced by this method alone (without additional winding culling)

Speed always being an issue with flash based 3d (fingers crossed this will change), sorting triangles is something one wants to be able to do as fast as possible.

If your working with vectors you might have noticed that they are slower to sort objects on a property than an array is.

There a numerous articles on the web about different methods to squeeze more speed out but here is what I do (specific to 3d shizznit).

var visibleTriangles:Array = [];
/*
...fill array with visible triangles...
*/
visibleTriangles.sortOn("distanceFromCamera", Array.NUMERIC);
return Vector.<Triangle3D>(visibleTriangles);

and that’s it 🙂
Pretty sure this won’t work for everybody but it’s much faster in my tests that using a vector during the sort process. (couldn’t detect any real overhead for the conversion)

When parsing .3ds files I noticed that the points coming in are all already transformed into their final positions.

This was kind of annoying as it messes things up when it comes to performing additional transformations on a mesh or trying to reset it back to its origin. Fortunately the .3ds file also contains a section for each mesh holding its matrix.

http://faydoc.tripod.com/formats/3ds.htm <– a little way down the page you can see the details (its a 3×4 matrix essentially).

Okay, so now we have the matrix the fun can begin 🙂

The idea is to reverse engineer the matrix to obtain all the transformations individually, then use that to build an inverse matrix (yes you could just invert the original but that’s less fun) then multiply all the points by that inverse to reset them back to where they should be. Then all that’s left is to set the positions, scales and rotations of the mesh according to what was extracted.

My matrix notation is as follows:

d, h, l, p are not in the .3ds 3×4 matrix but that’s not a problem as we know them to be 0, 0, 0, and 1 respectively.

as m, n and o represent the translation these are the easiest to extract, its a simple copy over from the 3×4 from the .3ds file.

translation.x = m;
translation.y = n;
translation.z = o;

scale is a little trickier

scale.x = sqrt(a*a + b*b + c*c);
scale.y = sqrt(e*e + f*f + g*g);
scale.z = sqrt(i*i + j*j + k*k);

now all we need is rotation

rotation.x = atan2(j/scale.z,k/scale.z)
rotation.y = -arcsin(i/scale.z)
rotation.z =  atan2(e/scale.y, a/scale.x)

of course there are reasons for why this works, but this isn’t the time or place to get into that.

so with all that info we can simply

• create a new matrix
• translate it by -translation
• rotate it by -rotation
• scale it by 1/scale
• use it to reset all the points
• then set the x, y, z, scaleX, scaleY, scaleZ, rotationX, rotationY and rotationZ on the mesh and POW…job’s a goodun’

So there you have it