PDA

View Full Version : Intersecting a 3D segment with perspective frustum



devdept
12-23-2009, 10:49 PM
Hi All,

We are trying to do object selection looking for intersection of left/top/right/bottom frustum planes and a 3D segment but suddenly realized that in many cases you find intersections even if the segment is completely outside the frustum because of infinite planes.

http://www.devdept.com/frustum.jpg

How do we overcome this issue?

Thanks,

Alberto

Ilian Dinev
12-23-2009, 11:04 PM
A quick idea: on each of the 6 segment-plane tests, modify the segment (clip it). It's done by simply replacing the value of the vertex that falls outside the plane with the line-plane intersection point.



Plane g_frustum[6];

bool IsSegmentInside(vec3 A,vec3 B){
Line line = Line(A,B); // a cache in a nice format
for(int i=0;i<6;i++){
float distA = g_frustum[i].distanceTo(A); // signed. Negative value means outside
float distB = g_frustum[i].distanceTo(B);
if(distA<0 &amp;&amp; distB<0)return false; // completely outside
if(distA * distB >0)continue; // both points are inside, no clip

// now, clipping
vec3 pointC = g_frustum[i].intersectLine(line);
if(distA<0){
A = pointC;
}else{
B = pointC;
}
}
return true;
}

devdept
12-23-2009, 11:24 PM
Ilian,

Premise:

1) We have already succesfully implemented the PointInFrustum() algorithm
2) Now we need to check if the segment intersect one of the *finite* frustum planes (polygons), not the infinite ones.

It easy for us to clip the segment with planes and check if the points are laying on the right side of the planes but this means we need to find intersection for almost all the entities (infinite planes cut something everywhere) and it's pretty slow.

I am sure there is a more straightforward way to do it.

Thanks,

Alberto

Ilian Dinev
12-23-2009, 11:54 PM
Polygon-line tests have all above operations as the second, fastest step in the algo. The first step is the construction of an infinite plane from the polygon. After that, the intersection-point (pointC above) is checked whether it's inside the poly.
So, I doubt the operation can be made faster than the above code. Or I simply don't understand the problem you've met. (how many planes, how many segments? Any other primitives/objects being involved in the hittests?)

devdept
12-24-2009, 12:13 AM
Ilian,

More details on our approach follows:

Suppose you have a wire rect on screen and you want to select it by dragging a box. Two cases are possible:

1) One of the rect vertices is inside the frustum (easy to check, positive distance from all six frustum planes)
2) The user drags a selection box crossing the rect edges but not enclosing any rect corner (what we are trying to accomplish)

In case 2) we are trying to find intersections with the 4 lateral frustum planes but as mentioned about is not enough to determine if the rect is to be selected or not.

The only possibility we see is to clip the segment but if you think about triangles edges for a 1,000,000 triangles mesh the speed would be unaceptable.


Thanks,

Alberto

Dark Photon
12-24-2009, 08:24 AM
Suppose you have a wire rect on screen and you want to select it by dragging a box.
If this is your use case, then I really don't understand why you're even considering clipping against the side frustum planes.

The way I might implement it: You've got a tiny little selection box on the screen. When they click the mouse, you've got to go figure out the closest thing that it "hit". I'd immediately then build a vector starting at the near clip plane centered inside the selection box and pointing parallel to the -Z axis in eye space. Then I'd intersect this against your scene.

If you've still got the saved "draw list" from your previous cull, you could look through that, though it could be huge. Instead, I'm assuming you have a spatial acceleration data structure for your scene (bounding volume heirarchy [BVH] or spatial subdivision structure) of some sort which you use for cull. If so, I'd just "intersect" your ray against your scene using it. That should be fairly efficient. You just keep the closest intersection point/object.

With this, you don't even care about clipping against your side (or near) frustum planes at all. The only frustum plane you possibly might care about is your far clip, because if the nearest hit is beyond the far clip then obviously the ray didn't hit anything in the frustum.

A variation on this is to due full quad-frustum clipping on the sides of your selection box, keeping the closest hit anywhere inside the box. More expensive.

devdept
12-26-2009, 12:14 AM
Hi DarkPhoton,

Thanks for your post but we can have very large selection boxes and can't try to use a single ray in the middle of them.

Of course we can skip object outside the frustum using bounding boxes or sphere intersection tests but again, what is a huge mesh is inside the frustum? Intersecting all those triangles edges is too slow.

Thanks,

Alberto