I'm talking about case when frustum is inside the box or i see the side of a box but every point of box is outside of frustum, i can't find any solution for that.
Determine whenever box is visible in frustum
I am not certain if I understand the question correctly, but here is a short tutorial on frustum culling: View Frustum Culling. You can check the second section about Testing Boxes, which gives an efficient method to determine if the box is inside, outside or intersects the frustum. If the above does not help, could you please elaborate (perhaps with pictures) what is the specific case you need to determine?
Author
as shown there are two cases:
one box is visible (covers whole screen) and points are all outside of frustum thats the easy one (you can make another exaple when 50% of box is outside of far plane) anyway
theres second case when only part of the box is bisible thus its vertices are outside of frustum but still testing against each frustum plane will return that its not visible
or
or you coudl imagine that frustum intersect right line of box
You should only reject a box if all vertices are "outside" the same frustum plane.
OP doesn't mention whether he's trying to implement frustum culling so I believe it's worth to mention that such approach isn't error free. Sometimes it gives false-positives, as in flags box as visible even though it is not.
its vertices are outside of frustum but still testing against each frustum plane will return that its not visible
Perhaps I am missing something obvious, but I can't imagine a case when this happens. If we pick the most distant point of the box for each of the view frustum's planes in respect to the plane's normal, we'll see the points are always on the positive half-space, even though none of them is inside the frustum itself. See the image below:
[attachment=30787:FrustumCulling.png]
OP doesn't mention whether he's trying to implement frustum culling
Perhaps we need more details what he needs this for, before we can help.
I struggled with this recently myself. The recommendation to only reject when all vertices are in the negative of the same plane bothered me because it would allow some false positives. But it's also a lot more efficient than more complex solutions, depending on how costly false positives are. Here's an example of a false positive that was tripping me up:
It gets even worse in 3D where none of the box's corners are within the frustum, none of the frustum's corners are within the box, at least some corners are on the positive side of every plane, and it's still unclear whether or not the volumes intersect. If you want perfect clarity, no false positives or false negatives, you'll need something more.
My solution was the following:
- Check all eight corners of the box against the six planes of the frustum.
- If any corner is in the positive region of all six planes, immediately accept the box and skip the rest of the algorithm.
- If all eight corners are in the negative region of any single plane, immediately reject the box and skip the rest of the algorithm.
- (Optionally do the inverse, checking the eight corners of the frustum against the six planes of the box.)
- Find the equations for the twelve line segments that make up the frustum's edges. I found it convenient to use a ray structure (starting point and non-normalized direction vector).
- For each line segment, geometrically subtract all six planes of the box from the line segment, noting if it gets subtracted away completely. (Each ray starts as parameterized from t = 0 to 1, and I just increase the minimum t or decrease the maximum t depending on how and where the ray intersects the plane. When min >= max, the line is zero length.)
- If even a single line out of the twelve still has a positive length, then the box is accepted; otherwise the box is rejected.
I'm pretty certain that the above is "perfect" in that there are no false positives or false negatives; it's an exact intersection test that handles all edge cases. (And conveniently should work for any combination of convex polyhedrons, not just rectangular box and frustum.) But no clue if it's optimal or close to optimal for that generic problem set.
And after having written the above, I'm now reassessing whether it's really worth it to do all those computations in order to eliminate false positives. I guess the only way to be sure is profiling, eh?
And after having written the above, I'm now reassessing whether it's really worth it to do all those computations in order to eliminate false positives
My idea to speed things up is to bound the frustum with a cone and test against that, the remaining false positives might be acceptable.
What i do in practice is to clip the box polygons inside frustum, because i need this for software hidden surface removal anyways.
There are always only 1-3 polys visible, i guess this could be used to speed up any approach a lot.
This page shares your idea of testing frustum outside box:
http://iquilezles.org/www/articles/frustumcorrect/frustumcorrect.htm
Usually GJK is used to quickly figure out if two pieces of 3D geometry are intersecting, or not. This is great for visibility testing. Assuming some kind of spatial partition is used the frustum can be treated as an AABB (or some other primitive) and tested against the spatial partition's primitives to rule out most potential collision pairs. Then, when an object is close enough to the frustum to get through the spatial partition GJK can be used to quickly figure out if an actual volume intersection occurs.
3D GJK isn't too hard to implement and I'm sure there are some 3D sources online to refer to. My suggestion to anyone that would like to implement GJK is to take Erin Catto's 2D example and port it to 3D -- he has slides to explain the algorithm. Just a note for any future readers: the tetrahedron case has 14 Voronoi regions, and 15 cases counting the interior.
The reason GJK is preferred is that it crawls through the volumes of two 3D objects very effciently, despite how complex they may be. It also doesn't do any extra work involving gathering information about *how* shapes are penetrating one another, making it focused solely on the closest features (to be exact, closest points) in the non-intersecting case. Explained another way: GJK treats the problem of closest points on two objects as closest point on *a single* object to the origin; this allows for an efficient intersection testing algorithm.
If GJK isn't an attractive solution I did like Andy's idea for approximation 
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
