Trienco style frustum system, general discussion

Started by
15 comments, last by Captian Goatse 20 years, 7 months ago
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]
Advertisement
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.)
f@dzhttp://festini.device-zero.de
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.
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.
my way is
-x
-y
-z
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.
Sorry if im incorrect, but is''nt a Cube check faster than a Sphere Check?...

i thought some if''s are faster than a Few x² + y² + z²... quares
J.A.N.K.E.Y.: Journeying Artificial Nocturnal Killing and Exploration Youth
1.
if (n==8 || f==8 || l==8 || r==8 || t==8 || b==8)


2.
if ((n==8) | (f==8) | (l==8) | (r==8) | (t==8) | (b==8))


is''nt the second one Faster?
J.A.N.K.E.Y.: Journeying Artificial Nocturnal Killing and Exploration Youth
ok i tried it out ....


if ((n==8) | (f==8) | (l==8) | (r==8) | (t==8) | (b==8))

is 0.5% faster ... *puh*
J.A.N.K.E.Y.: Journeying Artificial Nocturnal Killing and Exploration Youth
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]

This topic is closed to new replies.

Advertisement