Archived

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

Ruudje

Frustum Culling

Recommended Posts

Hey all, another question: Is it possible to do this culling technique (skip rendering of what can't be seen by the camera) per object? I've never even done normal culling before, so maybe this is a stupid question, but I'm planning of having a "large" world-object in 3ds, and don't want to loose my entire fps-count [edited by - Ruudje on September 3, 2003 5:31:08 PM]

Share this post


Link to post
Share on other sites
Thats what i am doing. Also im not using Octrees, since my scenes are not really that huge and frustum culling is more than enough since i have below 100 objects in a scene.

Frustum culling by per object is great because a large number of polygons can be excluded if they are not in the frustum. The method is exactly the same as culling by triangles. Only difference is the bounding sphere/circle/box contains a whole object instead of a triangle.

It should be quite easy to calculate the bounding sphere or box for you objects by using the min/max x/y/z values.

Share this post


Link to post
Share on other sites
It''s not just possible, it''s (more or less, depending on numbers) required. Some form of culling will be needed or you''ll kill your card by throwing geometry at it that can''t be seen. Large worlds often use hierarchical structures (e.g. BSP, octrees, quadtrees etc.) to speed up culling even more. For a large world in 3DS which will essentially be a polygon soup, you might consider an octree, or some sort of AABB tree.

Share this post


Link to post
Share on other sites
As mentioned before, frustum culling is done per-object. Use a bounding-sphere/box to check if the object lies within your view frustum. If you have a large object, like a terrain or the world/level (BSP, etc.) you can use Qaud- or Octree. With this technique you divide your vertex data into small groups and only render those groups (they are defined by a bounding-box) that lie within your view.

BTW: Is anyone familiar with the problem, that objects that lie within the view are culled though they shouldn be? If I fake the position of the object (for example give a y - 10 value to my CheckCubeInFrustum() function) it''s not culled anymore.

Share this post


Link to post
Share on other sites
Check out www.gametutorials.com - OpenGL Tutorials - Page 5
They have a good tutorial about Octrees, there is a .html file with the Download that describes the technique. Quadtree is actually the same with the only difference that 4 Boxes instead of 8 are used (you will know what I mean when you read that tutorial). Quadtree is more often used in connection with terrains and Octree with in-house worlds.

EDIT: Sorry, Page 5 not 4

[edited by - ZMaster on September 3, 2003 1:30:51 PM]

Share this post


Link to post
Share on other sites
funny... i just read that stuff :D

anyways, the html did explain the theory, but not how to do it. I havent looked at the code yet (guess the same code would work for cbuilder right? since its .net)

Before posting here I had a different idea, and wonder what you all think of it:

The world-file would be read in and all vertices would be stored. Next up I would check (somehow) whether or not the vertex I am about to draw is in front or behind the camera. If its in front of it, draw it using the glVertex3f(...), else just skip it. That would basically be tutorial # 10, but everything behind the camera would get cut off... I''m not sure this is gonna work though, since I havent tried it yet, nor know how I''m gonna load 3ds-models and store their data...

Share this post


Link to post
Share on other sites
check out the octree tutorials at gametutorials.com that is where I learned how to make octrees (using the octree class). Once again, I repeat, group vertices (preferably polygons) in an octree and check the octree section (i.e. node) to see if it is in the frustum.

Share this post


Link to post
Share on other sites
Ruudje, I know what you mean and I already tried that. The Problem is, that if a one vertex of a triangle is behind the camera and the others lie within the view, the triangle wouldn''t draw because it would need 3 to draw correctly (sometimes it draws but gives a wiered shape since the triangle takes a vertex that doesn''t actually belong to it).
Maybe you should do it per triangle, like this:

Check_if_one_of_those_vertices_is_in_frustum();
//draw the triangle
glVertex3f();
glVertex3f();
glVertex3f();

But if you do it like this you can''t get the performance advantage of for example GL_TRIANGLE_STRIP if you don''t use some intelligent re-ordering system of your vertices. You see, it''s pretty complicated and If I were you, I would do it with Octrees/Quadtrees.

PS.: The tutorial source code has a detailed explanation in form of comments. Just go through it - it sets the theory of the .html tutorial into code.

Share this post


Link to post
Share on other sites
Yeah I was looking for that triagle_list stuff, but NeHe doesnt cover it does he? I remember that somewhat from my d3d7 time... but never really did much with it. (I was 2D all the way man! :D )

tnx for all the advise

Share this post


Link to post
Share on other sites
quote:
Original post by ZMaster
BTW: Is anyone familiar with the problem, that objects that lie within the view are culled though they shouldn be? If I fake the position of the object (for example give a y - 10 value to my CheckCubeInFrustum() function) it''s not culled anymore.


Using bouding boxes, sometimes the corners of your box are outside the frustum (each side of the frustum for example)so it''s culled but it shouldn''t.

\ /
+-\--/---+
| \/ |
| |
| |
| |
+--------+

The tutorial mentions this problem but dont solve it. I solved it, but I use my own function for culling.

Share this post


Link to post
Share on other sites
I used some functions I wrote to get the point coordinates in the camera space. From this I can know if a point is to the left or to the right of the camera. My computation was something like "if some corners of the bounding box are to the left and some others are to the rigth AND are in front of the camera, then display it".

I dont remember exactly how the tutorial works, but I think it''s something like using planes equation ax+by+cz+d with the 6 frustum planes. With this equation < 0 or > 0 (depends of the plane''s definition) you can know if a point is from one side or the other of the plane.
Depending of each plane, you can know if a point is to the left or to the rigth of the plane. Then for your bounding box you should save the number of point being to the left and to the rigth. If all the points are not to the left or to the right, that means that the bounding box crosses the frustum.

You should do the same for up and down planes

Share this post


Link to post
Share on other sites
Ok, I see.

But what I actually thought about is, that it can''t be this kind of problem since bouding spheres have the same strange behaviour. I double-checked my frustum culling class and came to the result that it can''t be some mistake in there, because I also tried an exact copy of the gametutorials.com class and had the same problems. Could it be something in conjunction with the matrices? Is there something important to take care about when dealing with gluLookAt, in this case?

Share this post


Link to post
Share on other sites
It''s done like this:


bool ViewFrustum::SphereInFrustum(float x, float y, float z, float radius)
{
for(int i=0; i < 6; i++)
{
if(myFrustum[i][A] * x + myFrustum[i][B] * y + myFrustum[i][C] * z + myFrustum[i][D] <= -radius) { return false; }
}

return true;
}


I check for every of the 6 planes of the frustum if point + radius lies behind one of them (using the plane equation)

Share this post


Link to post
Share on other sites
Yes, it''s a lot easier with bounding spheres But I think the same trouble can occur at the beginnig of the frustum when it is thin.
Have you noticed it occurs at specific locations ? Being near the camera for example ?
And are you sur of your bounding spheres ? Try to draw them, and check if it is radius instead of -radius

Share this post


Link to post
Share on other sites
ZMaster: I have exactly the same problem. The weird thing is that it's view dependent. If the camera an the object is positioned along the z-axis then there's no problem. If both the camera an the object is positioned along the x-axis then there's to cases.

1: If the camera looks along the x-axis then the objects disappear on the left side of the frustum.

2: If the camera looks along the negative x-axis then the objects disappear on the right side of the frustum. I use spheres as bounding volumes.

[edited by - __fold on September 5, 2003 7:02:07 PM]

Share this post


Link to post
Share on other sites
This is kindof in the other direction than the last posts, but: what would be faster, Frustum Culling, suing an octree, or putting the entire worldmesh into a display list. Or what if I manually divide the mesh up in say 4 parts (or 16 or whatever) using a 3D editor, and place em in display lists, and come up with a formula to check whether or not they are in the camera''s view?

By the way... how on earth am I supposed to do that (the checking if the camera sees it)? (I''m still a opengl newbie, and need all my time figuring out how to do the online part for now...)

Share this post


Link to post
Share on other sites
Bruno: A simple rectangle/frustum check is this.

For all planes in the frustum.
{
  For all vertices i (Xi,Yi,Zi) in the rectangle
  {
    Calculate the distance by inserting the vertex in the plane
    (distance = A*Xi + B*Yi + C*Zi + D).
  }   
if all distances are positive
return outside
}
return inside.



[edited by - __fold on September 6, 2003 4:05:00 AM]

Share this post


Link to post
Share on other sites