Clipping/Test for quad visibility

I would like to test for the (partial) visibility of a rectangle in model space, when rendered into viewport space. I’m currently using Gl’s GL_SELECT mode, but there are speed issues with this.

Problem reduces to: an algorithm to test for overlap between a convex quadrilateral Q (the projection into viewport space) and a rectangle R (the viewport itself).

If any vertex of Q is inside R, there’s overlap (trivial).
If any edge of Q crosses an edge of R, there’s overlap (Cohen-Sutherland, perhaps?)
Finally, if Q encloses R, there’s overlap (can’t see any easy way to do this).

Can anyone help?

If you want a boolean answer then this is a point in frustum problem.

If you want the amount of rectangle that is visible, you will have to clip the rectangle to the frustum and then calculate the area of the resultant polygon.

Do a google search, you’ll come up with tons of hits. Crack open your copy of Foley et al. Or head over to wild-magic.com. There should be source code and an explanation there.

Originally posted by PK:
[b]If you want a boolean answer then this is a point in frustum problem.

If you want the amount of rectangle that is visible, you will have to clip the rectangle to the frustum and then calculate the area of the resultant polygon.

Do a google search, you’ll come up with tons of hits. Crack open your copy of Foley et al. Or head over to wild-magic.com. There should be source code and an explanation there.[/b]

Thanks. While you are correct that I ought really to be clipping against the frustum, it would be sufficient to clip against the viewport rectangle in this case.
I want a boolean answer that corresponds to ‘is any part of the projected rectangle visible?’. This becomes: 'Is any part of the projection of the rectangle - which is a convex quadrilateral - visible within the viewport rectangle? It’s not sufficient to test just the vertices.
I’ll have a look at the references you mention. I’m not a ‘graphics person’, so I don’t have a copy of Foley et al - don’t even know the title of the book!

I would do it this way:

  1. First determine the geometric center of each polygon and its bounding sphere radius (better do this before runtime).

Then at runtime, for each frame:

  1. Define the six planes of the view frustum (use glGetFloatv).

  2. Measure the distance from the center of each polygon to each of these planes. If in all six cases the distance is smaller than minus radius, then your poly is outside the frustum.

This sounds like a lot of calculation but it isn’t actually and you do get a nice framerate increase.

Originally posted by Keermalec:
[b]I would do it this way:

  1. First determine the geometric center of each polygon and its bounding sphere radius (better do this before runtime).

Then at runtime, for each frame:

  1. Define the six planes of the view frustum (use glGetFloatv).
  1. Measure the distance from the center of each polygon to each of these planes. If in all six cases the distance is smaller than minus radius, then your poly is outside the frustum.

This sounds like a lot of calculation but it isn’t actually and you do get a nice framerate increase.

[/b]

That sounds really promising, but your point 3 seems to be garbled slightly (“smaller than minus radius”?) and my intuition isn’t quite up to filling in the gaps… Could you clarify, please?

If I am not mistaken, the planes returned by glGetFloatv face the inside of the frustum. That means anything outside the frustum will be underneath the planes.

Therefore the condition for a sphere to be outside the frustum is

bool isOutsideFrustum()
{
if(( distance(center, plane0) < -radius ) &&
( distance(center, plane1) < -radius ) &&
( distance(center, plane2) < -radius ) &&
( distance(center, plane3) < -radius ) &&
( distance(center, plane4) < -radius ) &&
( distance(center, plane5) < -radius ))
return TRUE;
else return FALSE;
}

[This message has been edited by Keermalec (edited 12-17-2003).]

Ah - signed distance. This would work, but since my polygons are long, thin rectangles the bounding sphere will be much larger than the rectangle itself, and the clipping achieved will be very conservative. I’m currently looking at ‘correct’ determination of intersection, by using the ‘projection interval’ techniques described at wild-magic; it’s looking promising.

Thanks again for your help.

PixelPhile, there is actually a faster way than using spheres, and that is to use bounding boxes. The only thing is it is more complicated.

You would first have to determine the corner nearest to the plane, and then test that point to be below the plane. A bounding box will probably work better than a bounding sphere in your case, though if you polys are not all axis aligned you would have to use oriented bounding boxes which makes the code even more complex.

Originally posted by Keermalec:
[b] use bounding boxes. The only thing is it is more complicated.
B]

Thanks. As I’ve mentioned, I am only concerned about the 2D (x/y) aspects, so I am trying to determine whether an arbitrary quad overlaps an axis-aligned rectangle (the viewport). I found some excellent papers and almost-what-I-needed sample code at wild-magic.com, and got it working. It’s cleaner than before, and much faster.