Polygon on which side?
Author
I would like to know any efficient mathematical formula for determining which octree cube is inside, layon and outside the viewing frustum?
I am currently using this method:
Use the octree''s 8 points, test against the 6 planes of the viewing frustum to see it is inside or not. If so, then traverse into lower levels of the octree.
Any better method? Or any faster equation in the testing?
How about using a cheaper "early reject". An example might be to convert the frustum to a cone and each octree node cube to a sphere. That way at least you can reject the "definately not in the frustum" nodes extremely cheaply (i.e. a sphere in cone test).
--
Simon O''''Connor
Creative Asylum Ltd
www.creative-asylum.com
--
Simon O''''Connor
Creative Asylum Ltd
www.creative-asylum.com
Well M8 thank me I know the best exact formula of early rejection because I discovered it myself mixing an article of the Graphic gems and my impressive coding skill ! LOL
Instead of using less precise cones and spheres hear me then count the clock cycles spent.
In Quake they use the same kind of code ( discovered it recently ). But mine is much better. It''s based on plane/box rejection. Your view frustrum is convex. Compute the plane equations of the hull in world coordinates ... like your octree boxes I suppose.
A box can be rejected if at least one plane (half space) rejects it. If it passes the 6 tests then your box is visible or is near an edge or vertex of the frustrum. You could test a bit further but I dont think it''s worth doing it. And it''d be quite more complicated.
Thus the crucial routine that will be executed roughly 3 times per box is the box/half space culling. It uses the nearest vertex trick. Your box has 8 vertices : 000 001 ... 111. But only one needs to be checked the nearest to the plane. Its number is given by the signs of the components of the normal !
For instance if the normal is {1,1,1}/sqrt(3) then the nearest vertex is 000. If the ditance is positive reject the box.
It''s not pure ANSI but it just assumes 32 bit floats and ints. What a big issue !
Getting the sign is based on the IEEE standard for floating points.
// Each plane tested costs the equivalent of a dot product !!!
int BoxPlane( float Box[3][2], float Plane[4] )
{
//uint i=(Plane[0]>0)? 1:0; // far less efficiently pipelined.
uint i=(*(uint*)&Plane[0])>>31; // Get x sign bit
uint j=(*(uint*)&Plane[1])>>31; // Get y sign bit
uint k=(*(uint*)&Plane[2])>>31; // Get z sign bit
float d = Box[0]*Plane[0]+Box[1]*Plane[1]+Box[2]*Plane[2]-Plane[3];<br><br> return ( d > 0 ); // Else U can use the dirty cast trick to get the sign of d<br>}<br><br>Now some more ideas : you can reorder dynamically the "list" of rejecting planes. Thus you can exploit the spatial coherence of the octree walk and reject the boxes with usually only one plane/box test !<br><br>LOL it''s really if you want to save a few more clock cycles. <br><br>Charles B from Paris. </i>
Instead of using less precise cones and spheres hear me then count the clock cycles spent.
In Quake they use the same kind of code ( discovered it recently ). But mine is much better. It''s based on plane/box rejection. Your view frustrum is convex. Compute the plane equations of the hull in world coordinates ... like your octree boxes I suppose.
A box can be rejected if at least one plane (half space) rejects it. If it passes the 6 tests then your box is visible or is near an edge or vertex of the frustrum. You could test a bit further but I dont think it''s worth doing it. And it''d be quite more complicated.
Thus the crucial routine that will be executed roughly 3 times per box is the box/half space culling. It uses the nearest vertex trick. Your box has 8 vertices : 000 001 ... 111. But only one needs to be checked the nearest to the plane. Its number is given by the signs of the components of the normal !
For instance if the normal is {1,1,1}/sqrt(3) then the nearest vertex is 000. If the ditance is positive reject the box.
It''s not pure ANSI but it just assumes 32 bit floats and ints. What a big issue !
Getting the sign is based on the IEEE standard for floating points.// Each plane tested costs the equivalent of a dot product !!!
int BoxPlane( float Box[3][2], float Plane[4] )
{
//uint i=(Plane[0]>0)? 1:0; // far less efficiently pipelined.
uint i=(*(uint*)&Plane[0])>>31; // Get x sign bit
uint j=(*(uint*)&Plane[1])>>31; // Get y sign bit
uint k=(*(uint*)&Plane[2])>>31; // Get z sign bit
float d = Box[0]*Plane[0]+Box[1]*Plane[1]+Box[2]*Plane[2]-Plane[3];<br><br> return ( d > 0 ); // Else U can use the dirty cast trick to get the sign of d<br>}<br><br>Now some more ideas : you can reorder dynamically the "list" of rejecting planes. Thus you can exploit the spatial coherence of the octree walk and reject the boxes with usually only one plane/box test !<br><br>LOL it''s really if you want to save a few more clock cycles. <br><br>Charles B from Paris. </i>
Well I did not explain how to test for layon and inside but it''s not complicated with what I gave to you.
However if you are interested I have made a pure c style module that does exactly what you want. I even made an html doc of the interface ! I have an OpenGL/glut32 user side demo of the small C interface.
contact me at cbcht@wanadoo.fr
Charles B from Paris
However if you are interested I have made a pure c style module that does exactly what you want. I even made an html doc of the interface ! I have an OpenGL/glut32 user side demo of the small C interface.
contact me at cbcht@wanadoo.fr
Charles B from Paris
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
