
hi there, u guys have been busy talking!
i tried to implement frustum culling but im not that great with some of the 3d theory,even though i did specialist maths :(
here's my idea: get the pov vector from the camera and then get the angle between the direction ur looking and the center of the object/and or face. if the angle is >45 then cull it... u could even be more accurate and do it for each point on a face. of course u only cull in a conic shape in front and behind u but that's ok if u cull the objects behind u and widen the angle to say 5055 degrees so u dont cull objects on screen.
sorry i couldn't read all the posts u've made, but what is this linked list thing? what i plan to do is generate a list of points (like u guys?) for each object and in my array of faces i will have a number like 1 or 0 or 5 indicating the array position (array[5]) of the point. this way i can work 8 points only per cube and not the 24 for each square face (and definately not 36 for the triangles!).

Hi 03ricr,
I am also no 3D math expert.
Your idea sounds very simple and fast I will have to give it a try.
The linked list stuff is.
A linked list is a data storage structure used a lot in other programming languages. I have not seen it used much in actionscript. But it seems it can be done.
Basicly you have a data structure Node which holds two components the first is your data (what ever you want ie a object vertex) and the other "next" points down the list to the next Node.To traverse the data you move from one Node to the next Node. It is faster by aprox 40% than indexing through an array. But the drawback is you cannot index directly into a Linked List. So if you want to pull data out of the List you have to "walk" the list until you reach the correct Node.
The method of your Faces having indices into the pointList of the object is a standard method and works well. I am trying to work out something that can take into consideration that:
Say you have an object with 50 faces.
Each Face has indices into the points list.
You cull the faces in world space.
Now maybe 30% of your points are not needed!!
So why waste time transforming the entire array to camera then screen cords.
The problem is that if you pushed the points of your object still
needed into a new 30% smaller array of points, your Face indices would
now point to nothing. Or you would need to reset them all to the new array ... which I think would be a difficult procedure.
In other programing languages you can use pointers which point to the memory address of a variable. So it is easy to maintain a reference to a variable no matter where you shove it. Actionscript however does not have such a method. So here is my idea. Pseudo pointers for actionscript.
Code:
//data structure for a vertex
function V3D(x,y,z){
this.x=x;
this.y=y;
this.z=z;
};
//array to hold vertex list
pointsList=new Array();
//place a new vertex in an array and push it into the points list.
pointsList[0]=new Array(new V3D(10,20,30));
//give your Face indice a reference to the vertex
FaceIndice0=pointsList[0];
//push a vertex from the pointsList into a new array
camPoints=new Array(pointsList[0],0,0,0);
//lets say we transform it.
camPoints[0][0].x=500;
//now trace the FaceIndice0
trace(FaceIndice0[0].x);
the output shows that we have maintained our link to the vertex even though it has been pushed onto a new array!!!!! So we can shift
our vertices around into different arrays and our Face indices will
still maintain their connection.
The drawback is that it requires more memory but as Flash cannot handle a huge amount of polygons anyway I don't see this as a problem.
I have tested it with 1000 points. Which would be a lot for Flash.
The other thing is that in order to ensure (if you need to) that your original points array does not get corrupted you would have to have a copy of it and you can't do this with the usual
newList[j]=pointsList[j] method. You would have to build a completely new array ... something like this.
Code:
var i=10001;
do{
newArray[i]=new Array(new V3D(oldArrayO[i][0].x,oldArray[i][0].y,oldArray[i][0].z));
}while(i);
You could use a for loop but do while with an iterator is faster. To
copy this sort of array is slower than copying a standard array but I think it may be worth it. Depending how much advantage you will gain by transforming less points.
Anyway thats what I have done with my day!!!!
Milo

hi milo,
here are the results from your linkedlist v2
Code:
Start linked list setup = 27
Finish linked list set up = 66
Start array setup = 66
Finish array setup = 91
Time divide math.sin  array = 13
Time divide sin linked list = 5
i had the x y z 's divide by Math.sin(.1)..
seems like the linked list setup is costly but reading is
really fast.. that is ok.. because once you set it up in an onload
then its done..
i think its a winner.. especially if you have acces to index numbers..
but i still dont totally understand mixing the array and list..
doh !! .. i will get it...
yeah do a test on your engine and compare it with the old way...
i tried but couldnt get there.. my head was gonna explode...
< Guy Sebastian

well i went ahead and did it anyway, for each object i had a point list of 8 points and a refrence list for 6 faces (objects being 4 point cubes). the thing was that even though i calc 8 instead of 24 points... it was actually slower. the array lookup had a nice big fat overhead. and i have p42.6c
Last edited by 03ricr; 01272004 at 08:19 AM.

Good Morning ... for me anyway.
Wow Steve ... I am using Flash MX (2003) a pretty fast system and my result were same sort of % but twice as slow as yours. Is that the difference with MX (2004) AS2!!!!
I have been plugging a small 3D engine together to do some tests ... don't want to mess too much with my larger project until there is a real proven advantage. Here is the Linked List as I have it now (set up with an example Face indice situation). Tested and working. I have placed trace statements so the output gives you a real idea of what is going on (just remove them later).
I would have liked to optimize the ReturnNode()function more but I can't even decrement n as the list needs to be walked head to tail. If I changed the Linked List to a double linked list then it could be traversed from tail to head. But then the overhead for setup time increases. Maybe you can optimize it better than me. Just paste this code and run it. (The output will give you an idea of what I am getting at).
Code:
function Vector3D(x,y,z){
this.x=x;
this.y=y;
this.z=z;
this.count=0;
};
function LinkedList(){
this.h=null;
this.t=null;
}
LinkedList.prototype.AddNode=function(aObject){
if(this.h){
this.t[1]=aObject;
this.t=this.t[1];
}else{
this.h=aObject;
this.t=this.h;
}
this.c++;
}
LinkedList.prototype.ReturnNode=function(i){
var te=this.h;
var n=0;
do{
if(n==i){return te;}
te=te[1];
n++;
}while(te);
return null;
};
function Object3D(){
this.FaceList=new Array(new Array());
this.numFaces=0;
this.pointsList=new LinkedList();
};
Object3D.prototype.AddPoint=function(x,y,z){
this.pointsList.AddNode([new Vector3D(x,y,z),0]);
};
Object3D.prototype.AddFace=function(indices){
this.FaceList[this.numFaces]=new Array();
for(var j=0;j<indices.length;j++){
this.FaceList[this.numFaces][j]=this.pointsList.ReturnNode(indices[j]);
}
this.numFaces++;
};
plane=new Object3D();
plane.AddPoint(20,50,10);
plane.AddPoint(20,50,10);
plane.AddPoint(20,50,10);
plane.AddPoint(20,50,10);
plane.AddFace([0,1,2,3]);
t=plane.FaceList[0][3];
trace("Show vertex data using the FaceList indices");
for(j=0;j<4;j++){
temp=plane.FaceList[0][j][0];
trace("Indice "+j+" ("+temp.x+","+temp.y+","+temp.z+")");
}
trace("Now ........");
trace("Create a shorter Linked List using points 0 and 3. Alter their values");
newList=new LinkedList();
temp=plane.FaceList[0][0][0];
temp.x+=200;temp.y+=400;temp.z+=600;
newList.AddNode(temp);
temp=plane.FaceList[0][3][0];
temp.x+=200;temp.y+=400;temp.z+=600;
newList.AddNode(temp);
trace("Now use the FaceList indices and read their values");
temp=plane.FaceList[0][0][0];
trace("Indice "+0+" ("+temp.x+","+temp.y+","+temp.z+")");
temp=plane.FaceList[0][3][0];
trace("Indice "+3+" ("+temp.x+","+temp.y+","+temp.z+")");
trace("FaceList indices now point to the altered values");
Anyway what do you REALLY think of this?
Is it even a usable idea ... it maybe the same situation with the standard array version that 03ricr tested ... ie the overheads may cancel out any benifits. I am just thinking that if you have say 1000 plus vertices the gains will start to exceed to overheads.
Milo

Hi again,
Steve I did not answer your question about the mixing of arrays with the points list.
First it is not a must and the whole thing would be faster with a straight Node structure.The last example I sent should in some way explain my idea.
But here it is anyway.
//We have a straight Linked List (no array mixing).
poinstList = new LinkedList();
//and an indice into that list
indice0=1;
So now to get the data from the list we will have to walk the list.
using ReturnNode()(which is not that fast).
If however we use an array as a Node. Then we can set our indices to point to the array (which is our Node). This means we no longer have to walk the list as far as our faces getting the vertex data. it also means that if the data in the list is updated or moved to some other location our indices still point to it.
But there are lots of disadvantages too.
1:
More memory use as we are not storing a memory address to the Node but rather the whole Node in our indices!
This can be tested easily by.
myArray=new Array(10,20,30);
temp=myArray;
delete myArray;
trace(temp[0]);
2:
Lets say we have a Linked List of vetices called pointsList.We place a Node from that list into a new list.
newList.AddNode(poinstList.ReturnNode(1));
then we pull the Node out of the newList and alter its value
temp=newList.ReturnNode(0);
temp[0].x=7000;
We have now altered not only the data in newList but also the data in
pointsList!!
3: You can see what a pain it is to pull a node off the list. And if you had to do that all the time everything would grind to a halt. This would be the case if you used a straight list (no array mix) and wanted to get vertex info say to draw a face;
So ... I don't know ... great speed for iterating through the List.
Even faster if you used a straight list.
Maybe you/we could use a Linked List for doing transforms. And that function could push the results into an array for easy access. That may be the perfect combination. You could do away with the array mix which would make the Linked List even faster.
ie
//camPts being a straight array.
LinkedList.prototype.WrldToCam=function(camPts){
var te=this.h;
var n=0;
do{
//do transform stuff.
camPts[n++]=te.data;
te=te[1];
}while(te);
};
That would be REALLY FAST!!!
Milo

Hi again,
Well this is it for me as far as the linked list idea goes for now.
This is stripped down (no Array mixing).
The added function pushes the results into an array. So they can be accesed ... if they need to be. Which they most likely do.
I am leaving this alone until I can implement it in a real situation.
It beats an array version hands down as far as the transform goes. But again who knows ... filling an array no matter what method is slow. On my machine I am clocking 1000 point (250 4 point polygons) transform pushed into an array at about 300 milliseconds.
Code:
//what ever data you used in the linked list has to have a next
//variable set to null by the constructor.
function Vector(x,y,z){
this.x=x;
this.y=y;
this.z=z;
this.next=null;
};
function LinkedList(){
this.h=null;
this.t=null;
}
LinkedList.prototype.AddNode=function(N){
if(this.h){
this.t.next=N;
this.t=this.t.next;
}else{
this.h=N;
this.t=this.h;
}
}
LinkedList.prototype.RotateXYZ=function(out,ax,ay,az){
var te=this.h;
var cosx=Math.cos(ax),sinx=Math.sin(ax);
var cosy=Math.cos(ay),siny=Math.sin(ay);
var cosz=Math.cos(az),sinz=Math.sin(az);
var n=0,rx,ry,rz;
do{
out[n]=new Vector();
//x rotation
ry = te.y * cosx  te.z * sinx;
rz = te.y * sinx + te.z * cosx;
//y rotation
rx = te.x * cosy + rz * siny;
out[n].z = te.x * sinx + rz * cosx;
//z rotation
out[n].x = rx * cosz  ry * sinz;
out[n++].y = rx * sinc + ry * cosz;
te=te.next;
}while(te);
};
Milo

u could make tha faster by not caclulating the cos and sin every time. instead u could precalc with an angle of 15. if u need to change the angle, recalc the var from what ever changes the angle increments(button, mouse..etc).

hi milo, ross,
i had a brainwave.. why not store the index in with the vertex...
so the vertex class contains, x, y , z, index..
some systems also have a normal stored with the vertex..
and lighting info..
but that might solve the faceList problem...
hmmm maybe... anyway... needs thinking about...
i have copied all your link examples and will try them out...
i havent done any coding ..
i have been researching the graphics pipeline..
and i have realised that my engine is way inefficient...
so i am working on a rendering pipeline that is the most efficient..
so when i finish my research i should have the most efficient
graphics pipeline that i can work out..
then if we have the most efficient list traversal system...
we are laughing and can pump out some sick,, graphics...
oh.. milo btw ,, mx2004 is way faster than flash 6 ..it is pretty much a fact.. dont know why because as2 compiles down to as1 bytecode...
and that is another thing when we have optimised all we can up top then we could write the most cpu intensive function in bytecode using Flasm ... do you know it.. ??? it disassembles the swf and you can write stuff in bytecode direct.. heaps fast..
i dont know how to do it but... lol..
i will have a test of your linked list code and give you some figures... i like your idea of using the linkedList to do the transfroms .. that is a great idea...
hey oracle...
how is it doing.. i rendered your object you sent me and i will email it to you lateer... it looks spooky... ..
my lighting is still crap... i have to fix it up yet...
what was the name of the
free 3d modeller you were using... ???
well that is all
byeee
steve

it was anim8or, i found it in the 3d links sticky right in this 3D forum. (the post was at the bottom). i also found another nice little modeler called wings... i think that's also in the links. anyway im off to research too.. no coding for a bit.. or is it byte.. hmm... that's why.
something like www.anim8or.com and www.wings3D.com
Last edited by 03ricr; 01282004 at 10:31 AM.

Hi Steve,
Yes I have had a at Flasm and flash bytecode. There is a possibility for optimization there and the whole register stack setup does not seem too hard to get my head around certainly easier than assembly.
Did not really get the index in the vertex idea?
Checked out you files, looks sweet ... my files look like some crazy guy from a tin shed in the tropics put them together!!! You lighting files are amazing. I could not look at your .fla files (damn!!!!) as 2004 format.
I have a question as you are talking about efficient pipelines. I noticed that you have all the vertex transform functions in the objects themselves. I too have used this idea. But have been trying to move away from it. I don't know but I think it may be faster to have them in the engine itself. I have done quick and dirty implementation of it and there is a real speed gain. If you imagine that all the Vertex info for all the objects is in a single array or Linked List. Then the engine can speed through it for transforms etc. It is faster than looping through the objects and doing the necessary set up each time for the transform. But the data storage and control becomes more complex. And without a actionscript version of pointers it is a nightmare. I quess thats why I am so interested in a fast data structure with some sort of flexible indexing system.
I will be really interested in what you find in your reaserch. I know there are heaps of great methods out there but so many of them are not useable with actionscript ... or if you do implement it in actionscript its either slower or somehow a crippled version of the original concept.
see ya
Milo

hi milo
i sent you my fla but i realised it is totally not optimised..
doh!
oh well you live and learn .. fall down and get back up again..
cliche cliche etc..
see ya
steve

can we make a 2nd thread?.. then it wont take so long to load on my 56k..(damn 56k).

hi oss
ok..
i have 56k too..
see ya
steve
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
