   Is there "flawless" frustum culling?
  Hi;At the moment I desperately need a frustum culling method, which exactly rules out a node( a node is a quadtree node in my terrain;these nodes are axis aligned bounding boxes)if it is completely outside of the frustum. If it partially intersects the frustum or is completely inside of it, it will be accepted. Currently, my code tests 8 corners of a node against every 6 planes of the viewing frustum. If all 8 corners are in the back of any plane, then it will be rejected. The flaw of this algorithm is, if a node is not completely in the back of any frustum plane, but is outside of the frustum also, it will be accepted. I tried to illustrate the situation in the following picture:http://img530.imageshack.us/img530/8956/frustum.jpgI need to avoid such nodes getting accepted by the frustum test, so I need a "flawless" frustum culling algorithm as possible. I exhaustively searched the internet, tried to devise new approaches, but I somehow failed every time. Thanks in advance[Edited by - 67rtyus on May 13, 2009 3:56:19 AM]
  I might be totally off here but can't you check the points of the box if they are inside the frustum and accept them instead of checking them if they are outside? Even if only one point of the box is inside the frustum you accept that.Something like :points v[8]; //points of boxplanes frustumBox[6]; //planes of frustumif(pointInsideBox(v[0],frustumBox) || // check if v[0] is inside the frustum planes   pointInsideBox(v[1],frustumBox) ||   pointInsideBox(v[2],frustumBox) ||   pointInsideBox(v[3],frustumBox) ||   pointInsideBox(v[4],frustumBox) ||   pointInsideBox(v[5],frustumBox) ||   pointInsideBox(v[6],frustumBox) ||   pointInsideBox(v[7],frustumBox))    v is visibleelsev outside frustumMaybe I'm just dreaming [lol]   ;  @BlackKnightThere can be situations where no point of the bounding shape is inside the frustum but parts of the shape's area are (e.g. an edge of the shape intersects the frustum).@OPThere are no algorithm which are as fast as the normal culling. ou may want to explain why you desperatly need a more precise culling? Maybe your nodes are too big? It should not hurt too much because you should only encountered one or two nodes that are falsely marked as being visible by this frustum test. And sending them to the render should not influence performance too much.   ;Quote:Original post by Black KnightI might be totally off here but can't you check the points of the box if they are inside the frustum and accept them instead of checking them if they are outside? Even if only one point of the box is inside the frustum you accept that.Something like :*** Source Snippet Removed ***Maybe I'm just dreaming [lol]No, that won't work. There are cases possible where all points are outside the frustum, while another part is still inside it. Think for example of the case where a corner of the frustum is sticking through one of the faces of the box.I think the best way for doing what you want is to use the separating axis theorem. Just do a google search for that, there should be more then enough available about it.Another possible way of doing it is to just project all the faces of the box using your projection matrix, and then perform the standard frustum clipping on it. If after this clipping there is anything left of your box, you should consider it visible. (Note that you need to have a special case here when you are inside the box, or so close to it that it could be clipped by the near plane)   ;  Won't that cause a problem if the box is bigger than the frustum?i.e no points are inside all six planes but one point is outside the left frusum plane one point is outside the right frustum plane. The box should be visible but if you are excluding all objects that have no points inside the frustum you won't be able to see it.   ;  Ok ok I know I was missing something [lol]   ;  Intersect every edge of the node to the frustum volume, as well as every frustum edge to the node box. To check if a line intersects a convex volume, simply clip the line to the front of each plane, and if there is something left when you have clipped to all planes, then that part is inside.   ;  The reason I want this is a bit complex. I want to implement shadow mapping for my terrain engine. Normally, in shadow mapping you draw the scene from the view point of the light source. In my case, the light source is the sun and the lighting is directional. So, instead of a single point light source, there is a "plane" light source. This plane represents the sun, the light rays, which are all orthogonal to this plane, are thought to be sourced from it. I orthogonally project and draw the whole scene on this "sun" plane as the shadow map.The biggest trouble of the shadow mapping is the resolution of the shadow map and the sharp edge artifacts stemming from it. If I simply let whole terrain to be drawn on this shadow plane, it will both increase shadowmap resolution artifacts dramatically and too much geometry will be rendered every time, hurting the frame rate heavily. So, I am using the fact that most of the time only a part of the whole terrain is visible, and I only project the parts, which are visible by our camera, to the shadow (or the sun) plane. With that I aim to both increase the shadow quality and increase the frame rate. I want a culling algorithm with high precision, because every unseen node drawn on the shadow map quadratically reduce the resolution.   ;Quote:Original post by Black KnightI might be totally off here but can't you check the points of the box if they are inside the frustum and accept them instead of checking them if they are outside? Even if only one point of the box is inside the frustum you accept that.Something like :*** Source Snippet Removed ***Maybe I'm just dreaming [lol]There would still be problems (also with the method of 67rtyus) when the bounding box intersects the frustum, but all corners of the box are outside the frustum. Look for instance to the example image given by 67rtyus (this one) and consider what would happen if the box would be moved further to the lower right corner in such a way that part of the box is inside the frustum but the corners of the bounding box are still outside. In that case the box should be drawn.I don't know what the best method would be, perhaps you can look into intersections of the faces of the bounding box with the frustum (although I don't know how hard this actually is).[edit]And while I was typing and thinking about the problem, many others spotted the same problem ;)[/edit];Quote:Original post by quasar3dI think the best way for doing what you want is to use the separating axis theorem. Just do a google search for that, there should be more then enough available about it.Just wanted to emphasise this as it seems to have been ignored slightly - a test based on the SAT will do what you want. A description of how to do this for an oriented box is here; the axis-aligned version will be simpler but the principle is the same.   