Advertisement Jump to content
Sign in to follow this  
fir

frustrum culling by hand

This topic is 1863 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 got an array of many triangles.. ( this is software rasterizer so i transform every triangle co camera space than cast to 2d then 

draw it fits to the screen )

 

i would like to do frustrum culling i read about - thay say that frustrum is 

build from six planes sphere can be tested for each plane in such way

 

//for six planes

 

dist = plane_a*sphere_x + plane_b*sphere_y + plane_c*sphere_z + plane_d;

 

if(dist>-sphere_radius) sphere_in_frustrum 

 

but i am thinking about details, how to obtain plane coeficients 

for six planes... is plane_a _b _c just normal to plane (it is plane_nx _ny _nz)    ?

 

I use such sipmle way for perspective casting

 

screen_x = 500.0*x/z

screen_x = 500.0*y/z

 

(and near plane cut I get for z < 1.0)

 

I got know recently that it is poor perspective and better is to do it 

by some perspective matrix but now i can still stay with that above

 

How to calculate sic planes for this?

 

also should I do this test in camera space of before the triangles transformation - better to transform the frustrum planes to object

space (this maybe shopuld be faster?)

 

other thing how to write this test efficiently? I could test each 3 vertices

of each triangle or maybe some precomputation for triangle size (bounding sphere - center opf the triangle and radius)  and do

just one test then?

 

 

Share this post


Link to post
Share on other sites
Advertisement

you should not tranform camera frustum to object space, as you should avoid matrix transformations just to test an object. you should create the frustum in the space that is common for examined objects, what object space usualy isnt. Compute the frustum in world space, and have aabs of objects defined in world space too. this way you can imidiately examine aabs position distance towards the planes of frustum.

 

A plane is defined by a point and a normal . Since I suspect you build the view matrix by eye position, which is in world space, you have the point for the 4 side planes, all left is near plane and far plane world space point. Near and far perspective value are world space sclaras as well. just take the direction vector of camera : At-Eye, normalize it, and multiply it with near scalar and far scalar, add result to eye position, to get the points of near and far plane. You are now left to compute normals for the six planes in world space, the at-eye vector is just very suitable to compute 2 normals of near and far plane  in world space.

 

For the 4 side planes to get world space normal, you should find the near plane 4 corner points and far plane 4 corner points, subtract them to get edges of plane and compute cross product of those two edges to get normal.

 

for near plane (the same for far plane) get the near value as a vector (0,0,n) and use FOV value and tan() goniometric function to compute the vector to add it with (4 variation ,x +/-,y +/-),

so you get

(t,0,n)

(-t,0,n)

(0,t,n)

(0,-t,n)

and add those four to eye postionm this way wou have four near plane croners in world space.

Share this post


Link to post
Share on other sites

you should not tranform camera frustum to object space, as you should avoid matrix transformations just to test an object. you should create the frustum in the space that is common for examined objects, what object space usualy isnt. Compute the frustum in world space, and have aabs of objects defined in world space too. this way you can imidiately examine aabs position distance towards the planes of frustum.

 

 

 

I got heavy object (100 thousands traingles - it is in his own space)

Normally all this would be transformed to camera space (300k vertices) then clip (cull) I think if i transform frustrum

to object space (this is just 6 planes) then I do not need to transform 300k of vertices, no?

 

But i never dit that yet so i am curious.

Share this post


Link to post
Share on other sites

the confusion here is that culling is usually done per objects, with an object bounding box, not per triangle, as you submit the whole drawcall to the gpu.

 

but as you are writing a software rasterizer, it's more efficient to test per triangle, of course.

 

BUT testing 6 planes against a vertex means ~ 6 dot products, it's simpler to do 4 dot products to transform a vertex to post projective space and test it here. it's 4:6 transforms, so it's faster and in case you _see_ the vertex, you don't have to transform it additionaly, so:

-invisible 40% faster

-visible 60% faster

 

to make it efficient, you should do it in passes

1. transform all vertices, while transforming generate an "outcode", an out code is one bit per visibility test, something like

    out = vert.x<screen.minx?1<<0:0;
    out |= vert.y<screen.miny?1<<1:0;
    out |= vert.x>screen.maxx?1<<2:0;
...

2. for every triangle, get the 3 outcodes, "AND" them and if even one bit is left, the triangle is out of frustum

bool Invisibile(triangle T)
{
return Outcode[T.Index0]&Outcode[T.Index1]^Outcode[T&Index2];
}

that way you 1. are very cache friendly during the transform, as you linearly process all vertices and write the transforms

2. you are very cache friendly during the 2nd pass, as you just index randomly into a byte array.

 

and for rasterization, cache/memory access is usually the biggest performance problem.

Share this post


Link to post
Share on other sites

I do not understand this with outcode (but im tired)

my software rasterizer is weak one and i do not have

much ambitions to do it effective right now, maybe next

years, but i would like to treat it at ease and as a self

education 

 

as to 4 dots indeed transformation is really three dots

(by vertex so it is 12 dots it seams)

 but after that what is the cost of frustrum cullin? i do not know but you seem say that it is none here (so it is

+ unknown)

 

also when transform frustrum to object space the cost

is not 6 but at most six statistically may be lover, if

i would precompute radius for each triangle, if no 18 dots?

 

you are right that if it is not culled then need then be transfered.. i did not realized that transformation is 

cheaper than ful six dots frustrum test 

 

so after that i am not sure which way would be cheaper

---------------------------------

 

in camera space now i do not do side frustrum culling

I cast it to 2d and then check if x and y is in the screen but it involves division by z - how to awoid this division by side culling test in camera space? something like DZ<Const*DX probably.. wel this can be some improvement... maybe also this bounding spheres for triangles

Edited by fir

Share this post


Link to post
Share on other sites

You could break your object up into a uniform grid say 10x10, any triangles in side a box gets tagged for that. Check visibility for all boxes and only draw triangles in those boxes. If a triangle is in more than one of the grid's boxes, then just tag it for all boxes that the triangle is part of. It takes some work to do the math for a triangle contained/intersecting a box though.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!