You will also need to test the edges of the polygons, not just vertices. Simply check to see if the line that makes up the edge of the polygon intersects with a plane in your frustum (line to plane intersection test).

And no, there is no better way than to test all of the points of the polygon. It is expensive, which is why you only do it unless you absolutely have to. :) However, for your purposes, testing is only going to be done once, not every frame.

That being said, though, if you can somehow cut down on your test set (using smaller sets of bounding boxes around the model), then you can definitely increase performance.

You could use OpenGL selection mode, which would return anything that was partially or entirely drawn within the selection frustum. However, that might be slower (and less flexible) than the general solution. I think maybe what you want is a simplified separating axis test between the triangles and the frustum, perhaps with a bounding volume hierarchy to accelerate the test. This approach would handle the problem case that you mentioned, and would be relatively inexpensive.

A "line in frustum test" basically is a line to plane intersection test for all planes in the frustum. :)

To expand a bit on jyk's reply, OpenGL's selection mode basically works by drawing each polygon in a unique color (an ID), and then tested within a 2D region. It requires you to rerender your scene, but that's probably not too big of a problem. However, since it does bind you to OpenGL, you should consider first if you need to support other graphics APIs or not.

As for the bounding volumes, if you could separate different sections of the model (say, the hat and the face), then you could check which bounding volumes intersect the frustum first, then test all of the polygons within that volume. For example, that particular selection would only need to test the hat, since the face portion does not intersect the frustum at all.

Quote:Original post by bpoint
...OpenGL's selection mode basically works by drawing each polygon in a unique color (an ID), and then tested within a 2D region. ..."

Just to clear up a common misunderstanding. The OpenGL selection mode doesn't work this way. To quote the blue book

"In selection mode, no pixel fragments are produced from rasterization. Instead, if a primitive intersects the clipping volume defined by the viewing frustum and the user-defined clipping planes, this primitive causes a selection hit. (With polygons, no hit occurs if the polygon is culled.)"

However, to the original question:

[Edit - I just read jyk's reply]

Jyk is spot on, implement the separating axis method for your frustum and your pimitives, and you'll be laughing.

For your selection process:

* First test the object's bounding volume against the frustum.
* Now for any object whose bounding volume intersects the frustum, test the primtives (triangles, points whatever) to see which of those intersect your frustum.

There are several techniques you can use for dividing up your mesh to get fast spatial testing, such as KD trees or Octrees (and of course many others)

There is a swathe of information out there for how to do intersection between a number of primitves. One very handy page is this one:"

For some excellent code on the intersection of various primitives, have a look at : http://www.geometrictools.com/Intersection.html

- Phil