Archive for the ‘3d’ Category

booo adobe

Friday, August 20th, 2010

Just wanted to share a few of my frustrations with as3, in particular the apis added to aid 3d development.

My reason for voicing these is really to find out if its me miss understanding things or if other people share my opinions.

My main issue is the restrictions of the drawtriangles/projectVectors/transformVectors methods.

These methods work well and are pretty fast but the parameter format drives me nuts!

everything has to be in vectors of numbers i.e.

var verts:Vector.<Number> = new Vector.<Number>();

verts.push(0, 0, 0, 10, 0, 0, 0, 0, 10);

the vector verts now contains a representation of three 3d vertices (that make up a triangle) in the format the flash wants them in.

is this format easy to manage/maintain…no.

is it easy to debug…no.

is it faster for non-native methods…no.

is it the format flash demands…yes.

is it a pain in the arse…yes.

directly referencing a vertex like this is impossible and accessing it will require a minimum of 6 vector index operations, 3 to get the numbers out and 3 to put them back (slow slow slow).

🙁

I find things so inflexible that I run two systems in parallel, just to take advantage of the new methods resulting in wasted time and memory.

You often end up just having to repopulate these lists every frame, which although works its just plain craziness.

I am sure there are good reasons for this but what are they?

Why couldn’t they have given us a few interfaces instead i.e. IVector2D and IVector3D. Would it really be much slower?

Let us manage things our own way, give us freedom to implement things how we like!

Another thing that has been bugging me is drawTriangles, it isn’t currently flexible enough to be fully taken advantage of. Say for example you had a cube, and you decide to use 8 vertices to define it, one for each corner, drawTriangles is great because it lets you define which of the vertices makes up each individual triangle but it wont let you specify individual uv-coordinates per triangle-vertex. booo. Ideally a vertex shouldn’t need to be tied to one uv and one uv only because if that vertex is also part of another face it make have a different uv-coord.

Given that adobe are supposedly working on new 3d shiznit that are gonna blow our minds, I really really hope they consult the community and ask the people who are going to be using it most for input, ideas and suggestions!

Backface culling method

Friday, July 30th, 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)

z-sorting a vector of triangles

Thursday, July 29th, 2010

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)

3d matrix to position scale and rotation

Thursday, July 29th, 2010

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:

a b c d
e f g h
i j k l
m n o p

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

drawTriangles, z-sorting and culling in flash player 10

Tuesday, June 22nd, 2010

My first real post woop!

Ok here’s the scoop, if you have every played with 3d in flash and want your meshes to render correctly you will need to ensure its polygons are drawn in the right order (from back to front).

Simple, just sort them on the average z-value of their transformed vertices (or centroid).

Well you can stop right there, with the new flash player 10 extracting the z values can be a bit tricky, I have seen the uvt data generated used with some success to solve this issue but I don’t know if there is a better way lurking out there. Any ideas?

Following on from that is another issue… back-face-culling, this used be easy and only took a couple of ms to run through about 10,000 polygons to check their winding.

But what’s that you say?  “drawTriangles can do the culling for you if you only but tell it to!”

Well, although it can (using TriangleCulling.POSITIVE/NEGATIVE) that’s no use to me!!!!

I wan’t my triangles culled BEFORE I draw them, meaning I don’t waste time sorting polygons (the painful bit) that will never end up being rendered!

Now as yet, I’ve not come up with a method that can simply project all my vertices, cull all my triangles, then sort the badgers, then draw them. I am sure it’s got to be doable.. I just don’t have the brains.

I expect dozens of solutions and corrections…so hit me.