Archived

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

Frustum culling possible optimization?

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

Recommended Posts

Recently I have been looking at some frustum culling code, to optimize the rendering of a 3d scene (if you can''t see it, don''t draw it). I have a basic knowledge of how this is done - by calculating if it is within the viewing frustum (using crossproduct). Now if I am correct, you need to do a minimum of 5 cross-products for each object to determine if an object is within the viewing frustum (one for the left plane, the right plane, the top plane, the bottom plane and the far plane of the view frustum). Now assuming that we have a 3d world that is equally spaced with objects, wouldn''t that mean that approximately half of the objects are behind an imaginary plane that is perpendicular to the view point of the camera. Let me try to explain with some cheap ascii art:
  \ / <-view frustum \ / _____0_____ <-plane perpendicular to viewpoint of camera (lets call it the "camera plane") <-space behind camera (in theory half of the objects should be here) 
Now wouldn''t it be faster to do one cross product to determine if the object is behind the ''camera plane''? In theory half of the objects should be behind this plane, and you would only have to do one cross-product instead of 5. Now I realize that that will only take care of half of the objects. The other objects will need to be checked against the 5 planes of the frustum. Wouldn''t this make more sense, and shouldn''t it run faster? Moe''s site

Share on other sites
Faster is to avoid any unnecessary checking until you really need to. A test to see if the bounding sphere of an object is inside a cone representing the frustum should be enough to give you a rough idea of what''s visible and what''s not.
Anything which passes the test is "probably" on screen, if it doesn''t take much processing to draw, just draw it, if it does, go down to plane based methods to further cull.

--
Simon O''''Connor
Creative Asylum Ltd
www.creative-asylum.com

Share on other sites
um... Moe... something I should point out is that you absolutely must include the "plane of the camera" (aka the front clipping plane) in your frustum culling tests. As you pointed out, it can eliminate a lot of geometry by testing this, but this could be said for any of the planes (depending on the position of the camera in the scene). The important thing to realise is that a frustum is made of 6 planes... if you only use the 5 that you named, you will actually be determining a crapload of geometry that is behind the viewer as being visible

Crap ascii art to the rescue:

  _________\ / \ / \ / \ / X camera/viewpoint / / \ "phantom frustum" behind viewer

see how the planes extend back past the viewpoint, and include an infinitely large volume which is not really visible... this is because you are not testing using the front clipping plane ("the plane of the camera" that you described).

In roundabout answer to your question, the minimum tests for frustum culling an object is 1, and the maximum is 6... how many are actually performed can't really be optimised if your camera can move about freely, as objects may be anywhere in relation to it.

PS: for what its worth, i test in the order: front, back, left, right, top, bottom... it really doesn't make a difference, but it just seems like a nice natural order to me

EDIT - AAAAARGGGHHH!!
Can't get the infernal picture to work, so imagine the frustum reflected through the viewpoint, only the "frustum" behind the viewpoint has no rear plane (just top, bottom, left, right)

Edited by - Bad Monkey on December 28, 2001 4:01:20 AM

Share on other sites
I think I see what you are saying about having a 6th plane. I guess I didn't think about that before. What I am saying is do a general test first. Let me try to explain with some more cheap ascii art:
  ------------- <- far frustum plane \ 5 / \ / \ 7 / <- viewing frustum \ / 6 \ / 4 \ / ------ 0 ------ <- camera and near frustum plane 3 2 1the numbers are objects

Okay, so normally we would just check each object agains all 6 planes to see if it is the pyramid shaped viewing frustum, right? What I am saying is check all the objects agains the near frustum plane first. If the object is not in front of the near frustum plane than there is no need to do further checks on it (unlike testing it against all 6 planes). If an object is in front of the near frustum plane, then check it against the other 5 planes to see if it is in the viewing frustum.

Lets take a look at object number 1. Now what I am saying is check object 1 against the near frustum plane. Since its behind that plane, there is no further need to check it, and we save doing 5 cross-products. The same can be said for numbers 2 and 3, so we save a total of 15 cross-products, Right? Now numbers 4, 5, 6, and 7 need to be checked against all the planes, so there are going to be 4*6 checks - or 24 checks. Now that comes to a total of 27 checks (3 for the objects behind the camera, 24 for infront of the camera).

Now lets do it the way that I thought it was traditionally done. Objects 1,2, and 3 would be checked against all 6 planes, coming to a total of 3*6, or 18 checks. Objects 4, 5, 6, and 7 would also be checked against all 6 planes, so that adds another 4*6 (24) checks. The grand total for this method is 42 checks.

I guess my point is that its important to check the near frustum plane first, and see if you need to check the objects further. If its behind the camera, there should be no reason to do any further checking, and that would save quite a few checks in the long run.

Moe's site

Edited by - Moe on December 28, 2001 3:27:25 PM

Share on other sites
Sorry... I should have elaborated a bit further... the order you test the planes is not that relevant, but it is important that you do indeed provide an early exit (avoiding any further testing) as soon as an object is found to be outside any of the planes.

I think this is what you were getting at, but don''t limit yourself to only stopping early if they outside the front frustum plane.

BTW, to take the idea of frustum culling further, you should look into organising your geometry using a scene-graph (a number of which Magmai mentioned). This will bring a great boost in performance compared to checking every object in a scene (in most cases reducing visibility test times to (O)logN rather than (O)N )

Share on other sites
Could anybody care to explain how you can use crossproducts to do frustrum culling?

Crossproducts give you the normal between two vectors, dont they?

I''ve been trying to do frustrum culling, but with dotproducts (with mixed results).

~ I''''m a wannabe programmer ~

Share on other sites
As far as I know, a cross-product of 2 vectors will give you a normal that is perpendicular to the plane formed by the 2 vectors. If you do a little searching, there is a lot of info out there.

I will hopefully eventually add in an oct/quad tree as well. I would consider using a BSP tree but I am using DirectX 8 with vertex buffers, and in the end it might be faster to just shove the vertex buffer through instead of reading the vertex buffer, sorting it, refilling the vertex buffer, and then rendering in a different order with a bunch of SetTexture() calls.

Moe's site

Edited by - Moe on December 31, 2001 12:58:52 PM

Share on other sites
Moe, I think your "idea" is exactly what the frustum culling of 6 planes does. So, no, you dont have an optimization for that culling method.

However, I really like the idea of cone/sphere testing. Is testing if a sphere intersects a cone a fast test??? Im sure you can add a front/back plane to this test as well.

But how do you get a cone of size >= frustum view??

Share on other sites
This is more a side note.
After playing around with different frustum culling techniques I found that the initial guess of knowing what is "probably" in view is the most important thing, as S1CA said. Quad/Octree or BSP didnt satisfy me as they need traversal time, I choosed a brute force method of statically saving which world cell/node/cubelet is visible from each other. This approach performs also hidden surface removal for free as hidden cells/nodes/cubelets are not added to the list.

The remaining visibility tests belong then to moveable objects. Those are anyway distant-sorted from the camera in each frame, so I have to test the close ones for visibility. Here I would not recommend to test by planes, a simple vector product with the camera view vector is enough. The vector product result for xz plane must be corrected by the screen width:screen height relation as the FOV angle relates to the screen height only. So this unique vector product solves the culling.

- thomas

1. 1
2. 2
3. 3
Rutin
15
4. 4
khawk
14
5. 5
frob
12

• 9
• 11
• 11
• 23
• 12
• Forum Statistics

• Total Topics
633662
• Total Posts
3013228
×