Choosing a frustum to guarantee point visibility

In my application, I have a base point, which can be thought of as being close to the middle of a rectangle, and a normal direction. I want to travel from this base point along the normal, and then look back down on the surface… but I want to travel up far enough to guarantee that I can see 4 distinct points (ie, the corners of this “rectangle”). While it’s common that the 4 points will “mostly” be in the 4 cardinal directions, some variation can occur, and the 4 points are definitely not planar.

How can I choose a distance to travel up this normal so that I can create a viewing frustum which contains all 4 of these points? I don’t want to go up too far, either, because I need to do some color/depth picking and I don’t want to lose too much accuracy, so the “minimum” distance (or something close to it) is needed here. Is there a way I can pick an arbitrary distance, test if all 4 points are viewable, and if not, move up a bit more (or calculate exactly how much more I need to move up to make a missing point visible)? Or is there a faster method? Thanks for any help!

It is possible to compute the exact position you want with some math.
Here’s a hint. Let B be your base point and C the camera position, and n the normal vector giving the direction a the camera translation. Then you seek a scalar lambda such that C = B + lambda * n.
Now you take as many points as you want and want to see all of them. You compute the max of the distances between the base point B and each of these points. This gives you a distance d. You now imagine the sphere of center B and radius d. This sphere projects to a circle knowing the modelview (with unknown lambda) and the projection matrices. You can even say that you want to add a few percents to the radius so that you get some margin. You now need to solve for lambda so that the circle fits the viewport using the formulas you get from the OpenGL spec. Since we use a circle, the up vector of the camera isn’t even needed.

Thanks for your reply, sharp_pixel. Isn’t that even a bit overcomplicated, actually? Why can’t d just be the distance along the vector (plus some epsilon for margin)? We’d be guaranteed to see the “worst case” point (ie, if the point furthest away is actually on the plane defined by B and n, and therefore is on the boundary of the projected circle), and all other points will be within the projected circle.

If you use perspective, the field of view angles will modify the visibility of your points.
If you think it is complicated, you can try to get the point that is farthest from the base point, move the camera along the direction vector and stop when this point is visible but the method I gave you is really simple (draw it on a paper viewed from the side). And the resulting formula isn’t that complicated either.