🔒 Locked

Frustum Culling problems

Started by maya18222 Apr 6, 2009 at 7:35 AM 5 replies 1.1k views

Original Post

Apr 6, 2009 at 7:35 AM

I have my terrain split up into chunks, depending on size and other paramters, at the moment its 8x8, giving me 64 tiles. Each tile has a bounding box, which obviously has 8 points. I then use these 8 points to test if a tile is in the camera frustum and needs to be drawn. I do this, by testing each of the 8 points against the 6 frustum planes in a loop. If any of the 8 points has a location within the frustum, i dont test the rest, i drop out of the loop and draw the tile, as i conclude there is an intersection BUt ive noticed when walking around the terrain, this method presents the following problems, where look down of positioning the camera in such a way, fails tests, that really need to be drawn, shown in 2d from a side view. The blue box, is a bounding box for some terrain tile The red points mark the failed test points, and green vice versa The green plane marks the terrain

As you can see, example 2 and 3 fail, but need to be drawn. How can i resolve this issue? I can see the same thing happening for other objects with bounding boxes. Lets say i had a very large tree, at some point, when i get too close to it, its going to happen where although the tree is inside the frustum, all the bounding box points may not be, as in example 3.

Zakwayda

Apr 6, 2009 at 10:11 AM

The 'corners' test doesn't actually work, as you've discovered. What you want is the SAT (separating axis test).

For an axis-aligned box and a plane, there are two common ways of expressing the SAT: as a simple projection and comparison, and in terms of the points that project maximally and minimally onto the plane normal (the 'p-vertex' and the 'n-vertex').

I'm not sure why, but the latter form seems to be more commonly used, and is a little easier to find info about online. Check out this article, for example; you'll find a description of the algorithm in section 2.4, 'Basic intersection test'.

terra0nova

Apr 6, 2009 at 12:05 PM

If you want a simple way that is quite effective - try transforming the object into screen space using the projection matrix, and then intersect that object with the normalized cube (-1, -1, -1) -> (1, 1, 1). The projection matrix transforms your scene to this normalized cube, which it uses to calculate screen coord and depth. So if you do the same trick, instead of intersecting with a frustum, you can now intersect with an axis aligned bounding box.

NVM, jyk already explained the above lol.

MJP

Apr 6, 2009 at 3:25 PM

Also remember that if a SAT test is expensive for you, you can test with a bounding sphere first before you do the full test.

maya18222

Apr 6, 2009 at 3:45 PM

Thanks Guys.

Quote:
If you want a simple way that is quite effective - try transforming the object into screen space using the projection matrix, and then intersect that object with the normalized cube (-1, -1, -1) -> (1, 1, 1). The projection matrix transforms your scene to this normalized cube, which it uses to calculate screen coord and depth. So if you do the same trick, instead of intersecting with a frustum, you can now intersect with an axis aligned bounding box.

NVM, jyk already explained the above lol.

When you say object, do you mean the bounding box? if so, wouldnt i still get the same problems?

Krypt0n

Apr 7, 2009 at 3:53 AM

frustum vs box culling is usually done by testing if the box is located completely behind one of the six planes of a frustum. in the most simple way you test

for every plane of frustum {  Count=0;  for every vertex of box     if vertex behind plane       Count++;  if Count is 8    return invisible;}return visible.

this leads of course to the opposide of your problem, not all invisible boxes are culled, but most ppl accept this, lot of ppl who copy&paste some frustum culling code don't even realize this.

harveypekar

Apr 7, 2009 at 4:15 AM

Instead of brute forcing the vertices, I test the distance of the midpoint of the AABB to the plane. If it's bigger than the distance from midpoint to any vertex, the box does not intersect the plane ( but if it smaller, it may not be intersecting. It's conservative, but not accurate). The side of the plane of the midpoint is used to determine (in)visibilty.

So more or less

foreach plane in frustrum   distance = plane.distance(aabb.get_mid_point())   abs_distance = abs_dot_product(plane.normal, aabb.get_half_size())   if distance < - distance      return invisiblereturn visible

if the positive side of the plane is the inside of the frustrum.

This brings the average plane side tests to about 3.5 instead of 6*8

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.