Archived

This topic is now archived and is closed to further replies.

Captian Goatse

Trienco style frustum system, general discussion

Recommended Posts

As we all now premature optimisation is the root of all good I started looking possible ways to optimise one's view system and all I could come up with was the way Trienco does it. Trienco's system is usually finished before Morley style is done with the plane normalisation, which in my opinion is really good. I managed to optimize the AABB check on paper (12 dot products max, right now in trienco's implementation 8*3 max 24), however I have problems with implementing Trienco's version of the AABB check. Questions: which one of the vectors is min and max? I assume the first one is min and latter one is max.

bool Frustum::boxTest(Vector3f& max, Vector3f& min){
	int l=0, r=0, f=0, n=0, t=0, b=0;
	float tmpcorners[2][3];
	
	tmpcorners[0][0]=min[0]-transform[12];
	tmpcorners[0][1]=min[1]-transform[13];
	tmpcorners[0][2]=min[2]-transform[14];
	
	tmpcorners[1][0]=max[0]-transform[12];
	tmpcorners[1][1]=max[1]-transform[13];
	tmpcorners[1][2]=max[2]-transform[14];

	for (int i=0; i<8; ++i) {
		int in=0;
		float d[3]={tmpcorners[i&1][0], tmpcorners[(i>>2)&1][1], tmpcorners[(i>>1)&1][2]};
		
		float camZ=-transform[8]*d[0] + -transform[9]*d[1] + -transform[10]*d[2];
		if (camZ < nearPlane) ++n;
		else if (camZ > farPlane) ++f;
		else ++in;
		
		float camY=transform[4]*d[0] + transform[5]*d[1] + transform[6]*d[2];
		if (camY < -yFac*camZ) b++;
		else if (camY > yFac*camZ) t++;
		else ++in;
		
		float camX=transform[0]*d[0] + transform[1]*d[1] + transform[2]*d[2];
		if (camX < -xFac*camZ) ++l;
		else if (camX > xFac*camZ) ++r;
		else if (in==2) return true;
	}
	
	if (n==8 || f==8 || l==8 || r==8 || t==8 || b==8) return false;
	return true;
}


What am I doing wrong here? On paper it looks fine, however I'm not doing inverted X axis as trienco and I have all of my positions "inverted" like this:

   

	float view[16] ={     transform[0], transform[4], transform[8], 0,
						  transform[1], transform[5], transform[9], 0,
						  transform[2], transform[6], transform[10], 0,

						  -(transform[0]*transform[12] +
						  transform[1]*transform[13] +
						  transform[2]*transform[14]),

						  -(transform[4]*transform[12] +
						  transform[5]*transform[13] +
						  transform[6]*transform[14]),

						  -(transform[8]*transform[12] +
						  transform[9]*transform[13] +
						  transform[10]*transform[14]), 1};
The problem is that the some boxes are culled away on although they shouldn't. Those boxes are on the edge. Now on paper I have seen couple of ways to optimise the AABB routine. First is to test only the most extreme vertex, similiarly to how carmack handles it in Q2 source, which would reduce the AABB test to only 4 loops and max 12 dot products. Anyway, trienco thanks for pointing me to the right direction. This is just so much better 8) [edited by - Captian Goatse on September 2, 2003 1:29:12 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by Captian Goatse
Trienco''s system is usually finished before Morley style is done with the plane normalisation, which in my opinion is really good.



which planes? assuming youre talking about the frustum planes there is no need to normalize them, as you only care about the sign anyway. and as extracting the planes is only needed after rotating the cam it shouldnt cause any overhead worth mentioning.

quote:
I managed to optimize the AABB check on paper (12 dot products max, right now in trienco''s implementation 8*3 max 24), however I have problems with implementing Trienco''s version of the AABB check.


how? i wouldnt mind adding this if i may ,-)

yes, the first three are min and the last three are max, but with your references there shouldnt be a possibility for mixing it up anyway.

quote:

What am I doing wrong here? On paper it looks fine, however I''m not doing inverted X axis as trienco and I have all of my positions "inverted" like this:



z axis.. have you tried not inverting it in the frustum test or tested it with the inverted axis? i think i might have left quite a mess with changing the sign but i still think that z going into the screen is more natural *g*

quote:

The problem is that the some boxes are culled away on although they shouldn''t. Those boxes are on the edge.



hm, usually i just get disappearing objects along the edge when messing up the sphere culling again (modifying z and limit by radius allows more combinations of sign errors ,-) )

quote:

Now on paper I have seen couple of ways to optimise the AABB routine. First is to test only the most extreme vertex, similiarly to how carmack handles it in Q2 source, which would reduce the AABB test to only 4 loops and max 12 dot products.



sounds good, if you can determine the most extreme vertex fast enough. i could think of doing it with a camera that cant roll simply by checking the quadrant the camera is in or somehow just looking the three local axes to find the most significant, but i havent thought about that yet. guess i''ll just go and try it (even though most of the objects never get to the box test as the sphere test is usually enough for everything thats not along the edges).

quote:

Anyway, trienco thanks for pointing me to the right direction. This is just so much better 8)



just different. its less precise for spheres (as you test the box around the sphere rather then the sphere). i simply prefer not to care about any frustum normals and x/yFac are used for a lot of things anyway (drawing the frustum, transforming screen/world space etc.)

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Replying from school bear the anonymous:

Yes, the inverted Z axis and indeed it is messing me up. I think the problem is with the finding of effective radius, since your ways is:

-x
-y
z

and mine is is

-x
-y
z


When I get your AABB test to work I''ll post my "extended" version here. It is based on the fact that you can decide where to point is just by testing it against all the plane normals and then deciding on which side it lies on.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Oh no, I don''t think it is that... It is strange, when I remove the - signs the view is upside down, which is more like inverting the y axis. I think I might have mixxed up myself since I like to have Z axis pointing up, y into the screen and x right.

Share this post


Link to post
Share on other sites
I just found the main reason, since I set up perspective projection myself I was using different values for the actual frustum than for the xFac/yFac. I start on the extreme vertex implementation right away. If it works out alright as it did on paper the box check is going to be almost as fast as the sphere check.

Share this post


Link to post
Share on other sites
What the hell, how do you turn this thing into non-reversed? I thought I had it, but I still have visible boxes although I face away from them. I have removed the - signs, but it doesn't seem to help. There is something with the culling itself that is not totally clear to me.

And can anyone explain why does my backface culling get all mixed up and the view tilted upside down when I change the zaxis. should is set the culling from back to front? This really is a strange one.

I think I will start on tomorrow with the inverted z-axis one and work from that, since right now the z-axis thing looks overwhelming.

edit:

Yes there is something that is not coherent here. I tried the camera itself(non-modified) and I still have these problem... Can you please clarify what exactly is changed by the axis change. I mean changing z axis to point forward does not require to tilt the screen upside down.

[edited by - Captian Goatse on September 3, 2003 2:35:47 PM]

Share this post


Link to post
Share on other sites
lets see... sign changes are:
-in the constructor (Transform[10] = 1.0f)
-in setView
float viewmatrix[16]={ Transform[0], Transform[4], Transform[8], 0,
Transform[1], Transform[5], Transform[9], 0,
Transform[2], Transform[6], -Transform[10], 0,
...
-(Transform[8]*Transform[12] + Transform[9]*Transform[13] + Transform[10]*Transform[14]), 1};

that should be all.


also i couldnt find a good way to determine to most extreme vertices in all directions without having any limitations (like strict fps style camera). at least none that wouldnt take just as long as doing the additional tests.

jankey: there are no squares

float d[3]={pos[0]-Position[0], pos[1]-Position[1], pos[2]-Position[2]};

float camZ=Forward[0]*d[0] + Forward[1]*d[1] + Forward[2]*d[2];
if (camZ+radius < NearP || camZ-radius > FarP) return 0;

float camX=Right[0]*d[0] + Right[1]*d[1] + Right[2]*d[2];
float xLimit=(camZ+radius)*xFac + radius;
if (camX<-xLimit || camX>xLimit) return 0;

float camY=Up[0]*d[0] + Up[1]*d[1] + Up[2]*d[2];
float yLimit=(camZ+radius)*yFac + radius;
if (camY<-yLimit || camY>yLimit) return 0;

xLimit=(camZ-radius)*xFac - radius;
yLimit=(camZ-radius)*yFac - radius;
if (camZ-radius>NearP && camZ+radius<FarP && camX>-xLimit &&
camX<xLimit && camY>-yLimit && camY<yLimit) return 1;

else return -1;


i dont see any reason to mix bitwise and logical operators. with only .5% difference (which seems less than the difference i expect when running the same program twice) i wouldnt deliberately write "bad" code that just happens to have the same result.






Share this post


Link to post
Share on other sites
I''m afraid that is not it. I''m not sure whether you ran the code or not, but it results in perverted view orientation, which is visible when the scene is rotated(the scene rotates around a point.

I will investigate this more on the afternoon.

Share this post


Link to post
Share on other sites
hm.. youre right.. im not too surprised that everything is inverted, but it affects a lot more than i thought. i guess the setView shouldnt even be changed (as its opengl that has a "wrong" sign), but inverting the z axis still inverts everything else. its making sense, as you would have to change right to left. the constructor will make the cam look into the screen, if you want to look out of it you have to rotate the whole thing, making "right" go the other way (so in the end you would just move the - )

Share this post


Link to post
Share on other sites
Yes, however I think this is the right non-inverted z axis:

float view[16] ={transform[0], transform[4], transform[8], 0, transform[1], transform[5], transform[9], 0, transform[2], transform[6], transform[10], 0,
-(transform[0]*transform[12] + transform[1]*transform[13] + transform[2]*transform[14]),

-(transform[4]*transform[12] + transform[5]*transform[13] + transform[6]*transform[14]),

-(transform[8]*transform[12] +
transform[9]*transform[13] + transform[10]*transform[14]), 1};

But the problem still lies how to convert the culling code so that it "adapts" to this, which is quite "hard". As I said I will keep investigating this, because it is quite good alternative to morley style bruteforcing.


And I'd appreciate if someone looks that code and sees whether there are big flaws or not.

[edited by - Captian Goatse on September 4, 2003 8:28:18 AM]

Share this post


Link to post
Share on other sites
What exactly do you store in bbox? Is it not the max/min values of the aabb OR is it the effective radius?? I know I have my box dimensions right, because I can draw the AABBs on the screen right, however I can''t use even your original code properly. There is something thats not entirely clear in your code.

Share this post


Link to post
Share on other sites
good point.. its storing min/max as x0,y0,z0,x1,y1,z1. whats going wrong with culling?

i checked the directx lookat functions and they do the same (more or less). for left handed they do at-eye and for right handed eye-at, so inverting the z-axis seems to be necessary for opengl''s right handed system.

problem is: right/up/forward just doesnt work in opengl without either right or forward being inverted.
just had a look at mesa and their glulookat and its also inverting the "forward" axis (eye-center)

Share this post


Link to post
Share on other sites
I''m afraid that should not be so. I think you should reverse the view system in projection matrix instead of the view matrix. That way your view system stays the same, however the "idea" changes.

I think I will go mid-way morley and trigonometric system. I just noticed that if I had stored the clip plane dummies in my engine I would have recieved the frustum planes for free. I will still keep your sphere check, because I use the sphere for rough estimation and it is so fast ~__^.

Share this post


Link to post
Share on other sites