frustrum culling by hand

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

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;

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 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.

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 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 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 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 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.

• Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 16
• 11
• 9
• 24
• 51