surface normals of cube symmetrical ??

[shipstern]

Hi,
Given the symmetrical nature of a cube (3D).
Why calculate a surface normal for all six of the faces making up a cube ... when it would seem that reversing the direction of the surface normal of one face would give the suface normal of the opposite face??
Does this make sense??
Any reasons why this would not work??
In relation to both backface culling and also lighting.
Shipstern

[ferdymania]

yes that makes perfect sense to me...
you are quite right..
but only if you want to have cubes as models..
you are limiting yourself a bit maybe :-)

but you may be onto something there...
give it a try..
you would only have to calculate half the normals your way..
but you would have to keep track of your faces ...

good luck
steve

[shipstern]

Hi ferdymania,
Yes using just cubes would be a bit boring to say the least.
I have been playing with some c/c++ 3D engine code (full first person camera control) and adapting it to a Flash MX environment. Needless to say optimization is a BIG issue and anything that can be squeezed out of Flash is a bonus. I have been working on the bottlenecks. And though an objects surface normals are precalculated in object space they still need to be transformed into camera space. So I was thinking of ways to reduce these calculations. The cube face idea was one. Another was sorting all the precalculated normals in all the objects and finding those faces which have equal surface normals. Having an array of only the unique surface normals and giving each face an index number into this array rather than storing a surface normal for each face. Same method as a face having a list of indexes into the objects vertex list. So far it would seem that a large scene of objects can at times have over 50% of surface normals which are equal!!! This is particularly relavent to the static objects which make up the worlds buildings etc.
Thanks for your thoughts.
Shipstern.

[ferdymania]

Another was sorting all the precalculated normals in all the objects and finding those faces which have equal surface normals.

yeah i have thought of that but do not understand how you precalculate
normals when the points are moving around all the time..
and if you sort the normals, will you lose the index number of the face normal ..?
i guess you need some sort of linked list ... or

faceNumber[i] .. 0 1 2 3 4 5 6
normalNum[i] .. 0 1 2 3 2 3 4

Having an array of only the unique surface normals and giving each face an index number into this array rather than storing a surface normal for each face. Same method as a face having a list of indexes into the objects vertex list. So far it would seem that a large scene of objects can at times have over 50% of surface normals which are equal!!! This is particularly relavent to the static objects which make up the worlds buildings etc.

i guess you are right about the worlds buildings, terrain etc..
i was thinking of rendering them in the onLoad function but if
you have a camera , you need to render them on an enterFrame.. because the viewpoint is constantly changing....
hmm... you have made some very good points...
i should go and have a look at some algorithms and see what the standard approach is...

i could send you my classes if you like...
i am doing a 3d engine in AS2.0 ...
i am just sorting out the lighting.. i have the lighting sorted..
i just have to work out how to convert hex to rgb... or vice versa
so that i can change the colours of the faces according to the normal angle...
let me know how you go with your normals array and sorting ..
sounds like a good idea....

good luck
steve

[shipstern]

Hi ferdymania,
Yes my idea (would) work best for static world objects.
Of course all your surface normals should have been calculated in Object space. Then you transform them with the same transform you are using on your vertex list. Otherwise you would have to recalculate your surface normals every frame.

If your face had a normalIndex property then you could just set it to be the index into a normals array.ie:

normalArray=new Array();
function Face(){
this.normalIndex;
}
face1=new Face();
//do the calculation for the surface normal
//test this new surface normal against other exisiting surface normals

if(the new surface normal == normalArray[i]){
face1.normalIndex=i;
}

But this could be a REALLY DUMB IDEA I have not tried to implement it yet.

Hey I am also working on lighting!!!
Here is my method of using the RGB values.

If "intensity" is the final light intensity of your surface normal light vector angle calculations (for me + AmbientLight).
Face.col is my object face base color. ie: 0x00FF00 (or something)
Face.compCol will be my final object face color

//placed somewhere in your light calculations script
var r,g,b;
r=(Face.col>>16)&intensity;
g=(Face.col>>8)&intensity;
b=(Face.col)&intensity;
Face.compCol=((r) << 16 | (g) << 8 | (b));

So then when I use the Drawing API
this.beginFill(compCol,100); This will result in a shade of the base color in line with your calculated intensity. I am sure it can be extended to surface light absorption and also r,g,b components of the light source itself. But I am far off that.

Have you implemented frustum culling of objects?? This is something I am struggling with. Still yet to find some code I can apply. I have looked into using a frustum cone within a bounding sphere, this seems to be very fast (as opposed to testing against six frustum planes) but have not found a complete enough explanation to implement it.

Shipstern

[ferdymania]

hi shippy
here is my rgb - hex ...
yours is much neater and faster... can i try yours ?...
my brightness is a value from 0.0 to 1.0 for right angle to
light..
i could optimise my code heaps... it is way too heavy i reckon..

// ------ HEX to RGB 
	// adapted from pixelwit
function hexToRGB(hex){
		var red = hex>>16;
		var grnBlu = hex - (red<<16);
		var grn = grnBlu>>8;
		var blu = grnBlu - (grn<<8);
		r = red;
		g = grn ;
		b = blu;
	}
//	----	RGB to HEX
	// adapted from figleaf 
function rgbToHex(pr,pg,pb){
		r = pr<<16;
		r = r.toString(16).substr(0,2);
		g = pg<<8;
		g= g.toString(16).substr(0,1);
		b = pb;
		b = b.toString(16).substr(0,1);
// this is a kludge, but it works..
		clr = "0x"+r+g+ g+ b+ b;
	}

and here is my code for the lighting...

// in draw face method
hexToRGB(_clr);
r = Math.round(r * brightness);
g = Math.round(g * brightness);
b = Math.round(b * brightness);
rgbToHex(r,g,b);
//
_root.createEmptyMovieClip(name, dep);
_root[name].lineStyle();
_root[name].beginFill(clr);

i will have to give yours a try..
steve

[ferdymania]

Have you implemented frustum culling of objects?? This is something I am struggling with. Still yet to find some code I can apply. I have looked into using a frustum cone within a bounding sphere, this seems to be very fast (as opposed to testing against six frustum planes) but have not found a complete enough explanation to implement it.

No i havent done it yet.. i should have done it first..
one idea i have heard about is remarkably simple..
i dont know how slow it is but...
all you do is..
make a square mc the size of the stage and do a hitTest on it of
all mcs ... and if the hitTest is true then
test for backface culling .. then draw it.,
if hitest is false , break, dont draw it...

i havent tried it yet but...
you would probably need an array of faces...
you should have one anyway.. i havent.. doh!

see ya
steve

[shipstern]

Hi Steve,
Wow your lighting script is really straight forward.
Here is my complete script for lighting. I have also attached a screen shot of it on a standard checkered plane surface. It works really well. I calculate it based on the angle between the polygon surface normal and the vector from the light source to a vertex on the polygon. It also takes into account the distance from the light source to the polygon face. The script is not optimized in any way shape or form ... will get around to that soon enough.

As for the frustum culling. I have also heard of the screen hit test method. But the problem that I can see with that is that the objects would need to be on the stage already. Which means you have still had to send them all the way down the rendering pipeline. I am hoping to cull objects before they get that far down the rendering pipeline. Otherwise I don't see how Flash could have any chance of coping with anything more than a few objects.
Anyway here is the code for my lighting ... its not very pretty at this point. And I am open to all forms of advice.

My polyogons (object faces) have a variable col which has three components.
Each component represents the amount of red green and blue that the face will reflect.
col[0] //is the red   component
col[1] //is the green component
col[2] //is the blue  component
This would set the polygon to reflect only the red component at full strength.
col[0]=0;
col[1]=1;
col[2]=0;
This would set the polygon to reflect only the blue component at .9 strength.
col[0]=0;
col[1]=0;
col[2]=.9;



my light structure.

function Light(x,y,z,intensity){
	this.location=new Vector3D(x,y,z); //location of light
	this.intensity=intensity;          //intensity of light
};

//create a light
LightSource = new Light(0,300,200,1000);

//My ambient light level 
var AmbientLight=10;

//script for calculating the light that will hit the polygon
Where:
P            //is a point/vertex on the polygon face
FN           //is the surface normal of the polygon (normalized)
             //ie a (unit vector).
LightSource  //is an instance of the Light object.
col[]        //is the Face/polygon r g b reflective values
compCol      //is the final calculated color of the polygon

//get the vector from the light source to a polygon vertex.
//by subtracting the light position from the polygon vertex.
Var lVect=P.return_subtraction(LightSource.location);
//get the length (magnitude) of the lightVector
var length=Math.sqrt ((lVect.x * lVect.x) + (lVect.y * lVect.y) + (lVect.z * lVect.z)));

//Get the dot product of the polygon surface normal and the light vector 
//the light vector must be normalized (unit_vector) 
var product=FN.dot_product(lVect.unit_vector());

if(product<=0){
    //take into account the distance from light source to polygon
    //and the intensity of the light source multiply it by the
    //dot product
    product*=LightSource.intensity/length;
    //get intensity of the maximum r g b component (255) and add 
    //in the ambient light
    product=-(product*255)+AmbientLight;
    //make sure we don't exceed the maximum r g b components
    if(product>255){product=255;}
	r=Face.col[0]*product; //multiply by the polygon red 
                               //reflective value
	g=Face.col[1]*product; //multiply by the polygon green
                               //reflective value
 	b=Face.col[2]*product; //multiply by the polygon blue
                               //reflective value
    }
    else{
	r=Face.col[0]*AmbientLight; //if polygon not facing light 
	g=Face.col[1]*AmbientLight; //if polygon not facing light 
	b=Face.col[2]*AmbientLight; //if polygon not facing light 
   }
//push  r g b into final polygon color variable.
compCol=(r << 16 | g << 8 | b);

As you can see at the moment I have little regard about what Flash can handle without getting bogged down. I figure I am going all the way and see what happens in the end. I have seen some really interesting methods to do texture mapping with actionscript so I am even game for that!!!!!!!!! So far full camera movement and lighting, back face culled in world space I can handle 150 polygons.

Hope you can keep this communication up I find it great! Unfortunately I am still using MX (2003). How do you find the new AS2 it looks a lot more like C++ to me.

Milosav

[ferdymania]

hi milosav
here is my lighting code calcs....
i did it with the backface culling..
seeing i am calcing the normals ,

// backface culling
function backface(p1,p2,p3){
//
//	----------	calculate lights
	var omni = new Light(0,0,-200);
	var  lv:v3d = new v3d(0,0,0);
	// p1 of face minus light coords..
	lv.x = p1.x - omni.x;
	lv.y = p1.y - omni.y;
	lv.z = p1.z - omni.z;
	
	// get length of lightVector lv
	lv.normalize();
	// - normals
	var v1:v3d = new v3d(0,0,-200);
	// get vecs p1-p2, and p2-p3
	var v2 = p1.minVecNew(p2);
	var v3 = p2.minVecNew(p3);
	// normalise
	v2.normalize();
	v3.normalize();
	// v4 is our normal...
	var v4 = v2.cross(v3);
	//  p1 minus lightSource 
	var camVector = p1.minVecNew(v1);
	var result = v4.dot(camVector);
	// lights again 
        // normal dot lightVector lv
	var  lichtresult = v4.dot(lv)
	//
	if(lichtresult > 0){
		brightness = 0;
	}else{
		brightness = -lichtresult;
	}
	if(result > 0){
		return false;
	}else {
		return true;
	}

its a bit of a mess as well.. all my code is a mess at the moment..
i really should do a refactor now it is working and i know how ...

As for the frustum culling. I have also heard of the screen hit test method. But the problem that I can see with that is that the objects would need to be on the stage already. Which means you have still had to send them all the way down the rendering pipeline.

yeah i had a suspicion there was something too easy about it..
i havent thought it out at all... i have totally avoided frustrum
culling.. i will have to do it very soon... LMAO..

yeah i think about 150 polygons would be the limit...
that means the models will have to be clunky..
and not triangulated..
i have to reintegrate my camera... it works but i have left it out for yonks to get all the other stuff working so i dont have to worry about it.. but it has to go back in soon..

As2 is very good .. i reckon the flash player 7 is heaps faster than flash6 player..
but i think that as1 is the same if you use prototypes ...
you can convert as2 to as1 by just changing class to function(prototype) etc..

yes we should keep up this communication .. it is good to talk and share experiences and techniques...
when i get the chance i will post all my examples url's..
if you have a look at my site you will find some things...
see ya mate
steve

[shipstern]

Hi steve,
You code is a lot cleaner than mine thats for sure.
Like your incorporation of the backface culling with the lighting.
I have two sets of lighting calcs the first for the static objects they are precalculated when they are translated into world space. And they don't need to be calculated again. And then lighting calculations for the mobile objects that takes place within the animation/game loop. That gets really expensive as far as load on the Flash player goes. So I figure I may do a lot more detail with the static world as so much of it can be precalculated.
What are you using for your vertex transforms. Are you using Matixes?
Have you looked into using quaternions instead of straight vectors? I had a look at this but am still trying to get my head around it. Seems to hold some possibilities for optimization.

I find the biggest drag is the constant switching of targeting when transforming points of an object. If all the points off all the final objects where in one array then the speed gains are really substantial. The standard system of Faces having indexes into the objects vertex list is so slow ... it may not be a problem in c/c++ but it pushes Flash to the hilt. I am sure there must be some other method.

Anyway take it easy. Catch you again soon.
By the way I am in Queensland ... for now. Will be moving to Coffs Harbour in about ten days.

Milosav

[ferdymania]

hiya milos
i am using a matrix 3x3 for my transforms...
and i have a vector multiply with mAtrix method..
i tried a 4x4 matrix class but could not get the matrices
to concatenate...
i have had a quick look at quaternions but am not sure if they
are faster or not..

i do all my vertex transforms in one signle array..
wait till i have a look...

for example here is my rotate local z

// rotate around local z axis of the object
	function rotateLocalZ(sin, cos) {
		M1.loadIdentityMatrix();
		M1.rotationZ(sin, cos);
		var temp = pointList[0].minVecNew(pointList[1]);
		temp.scaleVec(.5);
		temp.addVec(pointList[1]);
		for (var i = 0; i<pointList.length; i++) {
			// minus p0
			pointList[i].x -= temp.x ;
			pointList[i].y -= temp.y;
			pointList[i].z -= temp.z;
			// multiply by rotation x matrix
			pointList[i] = M1.vectorMultiplication(pointList[i]);
			// add back p0	
			pointList[i].x += temp.x;
			pointList[i].y += temp.y;
			pointList[i].z += temp.z;
		}
	}

this may not be the best because i have to transfrom all the points
but it is triggered by a key event so it is ....
hmmm thinks... still calcs going on... not so smart...

maybe this way...

for(var i=0; i<vertexArray.length;i++){
// check if point is in frustrum, cull
// check backface cull, (hmm not sure here, faceList ??)
// lighting
// transform point
// perspective calc..
// render
}

much optimising to do..
and thinking..

coffs harbour is nice.. the beaches are very good...
see ya
steve

[shipstern]

Hi Steve,
I am also using 3x3 matrices.
I think though there are times when they chew up too much time.ie:
with a straight z rotation (no Matrix)

cosA is already calculated cos angle
sinA is already calculated sin Angle
vertexList[] is the vertex list.
transList[]  is the transformed vertex list
for(var j=0;j<numVetices;j++){
    transList[j] = vertexList[j].x*cosA - vertexList[j]*sinA;
    transList[j] = vertexList[j].x*sinA + vertexList[j]*cosA;
    transList[j].z=vertexList[j].z;
}

Here there are only 4 multiplications
Where as a Matrix Vector_Multiply has 9?? (I think).

I am working for something like.
for(j=0;j<numObj;j++){
//inverse matrix transform of camera to world space
//cull objects to frustrum
//cull non visible faces of object
//push those vertices left into an finalPtsArray
}
Then..only transform those points faces left.
for(var i=0; i<finalPtsArray.length;i++){
// lighting
// transform point
// perspective calc..
// render
}
What do you think???
Also have been thinking about some other method of storing data, objects, vertices etc. Arrays are so inflexible. So I thought why not use a Linked List. And do away with the array indexing. So here is a basic setup for that it seems to work well. The code below is and example that does a Linked list Vs an array for storing what ever object you wanted (here I just used a basic Vector with x,y,z components).
On my machine the Linked List clocks in just under 50% faster than the array accessing!!! Try it out and let me know you results and any ideas. You can also delete and add objects into a Linked List with the advantage that the Linked list shrinks unlike an array where you would have to re_sort the whole array. I think it MAY have some possible use to optimize things.

Anyway here it is (some comments).

//just to have some data structure to test with
function Vector3D(x,y,z){
	this.x=x;
	this.y=y;
	this.z=z;
};
//The Linked List stuff
//A node of the linked list containing an object and pointer to next node.
//parameter aObject could be any object
function Node(aObject){
	this.obj=aObject;
	this.next=null;
}
//The Linked List constructor
function LinkedList(){
	this.head=null;
	this.tail=null;
}
//Add object to list
LinkedList.prototype.AddNode=function(aObject){
	if(this.head){
		this.tail.next=new Node(aObject);
		this.tail=this.tail.next;
	}else{
		this.head=new Node(aObject);
		this.tail=this.head;
	}
}
//Display all node data;
LinkedList.prototype.ShowAllNodes=function(){
	var temp=this.head.next;
	while(temp){
		trace("Vector3D("+ temp.obj.x+ ","+temp.obj.y+","+temp.obj.z+")");
		temp=temp.next;
	}
}
// Using the Linked List 
var faceList=new LinkedList();
//just fill it with some data
for(var i=0; i<500; i++){
  faceList.AddNode(new Vector3D(0,i*10,0));
}
t=getTimer();
faceList.ShowAllNodes();
trace(getTimer()-t);

// Now using an Array 
vectorArray=new Array();
for(var t=0;t<500;t++){
	vectorArray[t]=new Vector3D(0,t*10,0);
}
t=getTimer();
for(var g=0;g<500;g++){
	trace("Vector3D("+ vectorArray[g].x+ ","+vectorArray[g].y+","+vectorArray[g].z+")");
}
trace(getTimer()-t);

Milo

[ferdymania]

hi milo
hmm i will have to look into the matrix situation..
9 calcs versus 3 .. sounds right to me..
i cant remember if i use all the matrix multiplications.. hmm yes i do..
i must investigate

for(j=0;j<numObj;j++){
//inverse matrix transform of camera to world space
//cull objects to frustrum
//cull non visible faces of object
//push those vertices left into an finalPtsArray
}
Then..only transform those points faces left.
for(var i=0; i<finalPtsArray.length;i++){
// lighting
// transform point
// perspective calc..
// render
}

i am not too keen on this algorithm(IMHO :-) , because you are doing the calculations twice.. and having two loops when you might be able to have one
i think it might be better to have one loop and just have nested ifs
and organise it so that the most probable if is thrown out (break)
first so that only the necessary calcs are done...
just thinking out loud, without much thought..

// loop thru all points
// if (backface) else break
//      if ( frustrum) else break
//        lighting
//        transforms 
//        perspective
//      end if
// end if
// end loop

the linked list idea sounds very good..
i will copy it and play with it..
i think you are on to something here...

check you later,
steve

[ferdymania]

hi milo,
i tested your linked list code and you are right .
it is twice as fast..
i tested this on both systems..
5 for linked list and 15 for array..

var testx = temp.obj.x / Math.sin(.1);
var testy = temp.obj.y / Math.sin(.1);
var testz = temp.obj.z / Math.sin(.1);

I tried to test it against my rotateLocalY method..
but i am not sure if it will work..
here is what i wrote:

function testList(sin, cos,list) {
		M1.loadIdentityMatrix();
		M1.rotationY(sin, cos);
		var centre = list.head;
		var temp = list.head.next;
		while(temp){
		{
			// minus p0
			temp.obj.x -= centre.obj.x ;
			temp.obj.y -= centre.obj.y;
			temp.obj.z -= centre.obj.z;
			// multiply by rotation x matrix
			temp.obj = M1.vectorMultiplication(temp.obj);
			// add back p0	
			temp.obj.x += centre.obj.x;
			temp.obj.y += centre.obj.y;
			temp.obj.z += centre.obj.z;
			// make it move in that direction
			// 
			temp = temp.next;
		}
		
	}

i couldnt work out any more.. i got lost..
not sure about above...
can you have a go at it ??
my brain hurts...
but i had a thought ... i have a list of points of each face that
are the indices of my pointList array..
how can i link the vertices of the face to the points as they are rotated, translated etc..??
i cant get my head around it...
but linked lists are definitely faster and it is worth exploring further.. just needs a lot of thinking..
oh well it is getting late and my head is full of it...
see ya later
steve

[shipstern]

Hi Steve,
Could not get back to you yesterday as we were hit by a big storm ...
80 foot trees being torn out of the ground and flying through the air.
The power was out till this morning.
First the matrices ... yes i think there are times when they are better not used ... but WHEN would be the big question. For me part of it is keeping in mind that Flash will only be able to handle a limited number of polygons and points. Most conventional 3D methods are designed around a huge number of polygons and points, memory managment is a real issue and a very small gain in speed per point can make up for initial setup of such systems as matrices. But at the moment I am using matrices and only thinking and looking at other possibilties.

Next yep I think your pipeline method is a way more efficient idea (ie in the one loop).

The linked list. There are limitations with linked lists. Especialy using actionscript. Mainly that is you can't index into the list!! This is a big drawback. If you need some data half way through the list then you would have to walk the list to that point. I don't know how you could get around this in actionscript as it has no method of referencing a variables memory address (like pointers in C/C++).

Your local rotation method looks like it should work to me. I have been wondering how you have your Objects setup? How do you store their vertice and face info? In you example code: It looks like you are subtracting the objects current x,y,z location to translate it into object space so you can perform the rotation ... then translating it back into world space after the rotation. Is that right??

As for how can you link the Face indices to the list of points ... with a Linked List ... using actionscript ... I am still wondering that myself. As I mentioned the linked list may be of no use if you have to index into it ... as walking the list to find a point would be way too slow.

I have been playing around with some stuff but have yet to try and implement it. It seems that arrays are the only thing that has some possibility for referencing (in a pseudo pointers fashion).

Say in C++:
var fl=3.14;
var Ptraddr = &fl;
Ptraddr is the memory address of fl, and can be then used to alter the value of fl. With this you can build a linked list and give your faces indices which are the address of the values in the list.

In actionscript:
pointArray=new Array(10,20,30,40);
k=pointArray;
pointArray[2]=600;
trace(k[2]); //ok now it is 600.

I am wondering ... what if the Linked list nodes are made up of arrays. ie
node1=new Array(data goes here,next node goes here);

Then you could give your Faces the address of the node in the list and you have access to it updated transforms. It also means you could add and delete or build new lists using these nodes and your Face reference to them would remain intact. ie:

node1=new Array(10,30);
FaceIndice0=node1;
node1[1]=600;
trace(FaceIndice0[1]); //now 600
p=node1;
p[1]=900;
trace(FaceIndice0[1]); //now 900

I know there are somethings about this that may just make it a crazy idea.
1: This may be taking up a lot of memory. However we can only deal with a small number of polygons anyway so maybe memory is not an issue.
2: The use of arrays as nodes may slow things down again. Even if it ended up only 5% faster it could be a way more powerfull method of passing and storing data.

Anyway I have gone on way too long ... give me your opinion on this. Also have been working on the Linked List will be adding more functionality. I have just added in a previous to complement the next so now it is a double linked list. Here it is will send you new versions as I develop them.

Milo

[ferdymania]

hi milo
i saw the storm on the news.. looked vicious..
we have been having storms every night now.. but not too wild..

re my algorithm..
i think it may be wrong..
becuase you have to rotate and translate before youdo frustrum culling i think..
so quick think..

//transform points

// frustrum ()- else break
// not sure of sequence here..
// separate faces with no points available ???
// backface -( else break
// render

not sure about that.. but it can be refined and thought about..
we will get it.. i am sure..

LinkeList
---------
Great idea.. i have played with it and i am sure that it will be helpful.. maybe push a list of renderable points or something to a linked list for heavy calculations...
but i think structure is the first step in optimising..
so that the minimum amount of calcs get done,,,
i need to sit down and start drawing boxes and lines...
But i think that developing the linkedLIst class is a good idea..
it can be very useful in a lot of sitiuatoins...
Also , it probably needs a ListIterator class as well..
i have been looking... and researching.. have to read it all yet..

you are really onto something there buddy..

you are right about the pointers and memory address...
that would be so fast.. but ... i guess we are stuck wit flash LMAO..

For my objects, i have a pointsList and i have a faceList for every face that contains the index each point has in the pointsList..
oh i will send you the lot...
is your email address on this board ?
no, send me an email- webmaster at video-animation dot com

i had a look at your idea of mixing arrays and linkedLists but couldnt get my head around it... sorry.. :-)

And the trouble with LinkedLists is you have to go thru the list to get to a certain place.. is that correct.?
but an array you can go directly to an index...
maybe we could write our own array class.. lol..
something like the STL Vector class.. but totally stripped down
to only allow pop and push and direct index access..
dream on !!!!
anyway...
brekky awaits..
steve

[shipstern]

Hi again Steve,
Just implemented the Linked List using three element arrays as the nodes. First elements holds data.Second element will hold reference to next node. I removed the previous component as initializing it slowed things down.
I can't believe it though but it is still 30-40% faster than array access!!!!!
However ... there always is one. In my test the arrays are an average of 40-50% faster to fill than the lists.
So I guess if using the list outweighs building it.

This now means you could use a linked list to hold vertice info and give your Face indices a reference to the nodes in the array. And the indices will always point to the updated/transformed info, even if you build a new list out of the nodes the Face indices will still point to the correct info!

In the end actual implementation will be the only way to find out. But it seems like a good thing. Or I am just going tropo up here.

Anyway here is the LinkedlistV2 using arrays as nodes. Bang me on the head if you think I am losing the plot!!
Milo

[shipstern]

Hi,
Here is the linkedlistv2.
and here is my email mpelic@ozwide.net.au

[ferdymania]

hi milo
ha ha ha .. it is the wet up there..LOL
i will have a look at your new linked list ..
i cant get my head around it yet. but will have to
write the code out to get it..
i am a bit slow you know :-)

i sent you my files...

steve

btw i have found a java optimisation tips page.. it may be useful

http://www.javaperformancetuning.com/tips/rawtips.shtml

[shipstern]

Hi Steve,
Hmmm I think this link list thing may be getting too weird.
Here is a function anyway that pulls a node out of the list.
By walking the list. ind is the index number you want out of the list.

LinkedList.prototype.ReturnNode=function(ind){
	var temp=this.head;
	var c=0;
	while(temp){
		if(c==ind){break;}
		temp=temp[1];
	    c++;
	}
	return temp;
};

here is also a test I am working on using it with a 3D object ie adding to a points list and getting the face indices out of the list.

function Object3D(){
	this.FaceList=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]); //0,1,2,3 being the indices into the list

Its really rough but works ... I think I will throw this into my current engine and see how it works. I am not really hoping for much ... who knows ... something different until it stops raining!!
Milo