erich@eye.com ( Eric Haines) (12/07/90)
I've recently been looking at the following problem: Given an orthogonal (axis-aligned) box and a set of planes defining a space (e.g. a polyhedron, a view frustum, etc), find if the box is entirely inside, entirely outside, or overlapping the plane-set space. Note that the space defined by the planes is convex. A practical example of this would be finding if an object was inside, outside, or overlapping a view frustum. The trick is I want a general answer (it has to work for more that view frustums, i.e. for any set of planes defining a space). Such an algorithm would have a lot of potential uses, e.g. it would certainly be handy for Arvo & Kirk's formation of candidate lists for their 5D ray tracing efficiency scheme. I know of the techniques mentioned in A & K's article - has anyone found anything faster for this particular sub-problem? I thought I'd ask before trying to refine and write up an idea I had, so that I don't get "you silly fool, this problem was solved long ago by Euclid" notices. Interested to hear from you all, Eric Haines