Archived

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

Polygon on which side?

This topic is 5814 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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?

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
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][i]*Plane[1]+Box[2][i]*Plane[2]-Plane[3];

return ( d > 0 ); // Else U can use the dirty cast trick to get the sign of d
}

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 !

LOL it''s really if you want to save a few more clock cycles.

Charles B from Paris.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
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

Share this post


Link to post
Share on other sites