Skip to main content
GameDev.net gamedev.net
🔒 Locked

Frustum-Frustum intersection

Started by JonnyQuest Jan 13, 2005 at 12:13 PM 9 replies 15.9k views
Original Post
JonnyQuest
JonnyQuest
Hi, I apologise if this has been covered before. No amount of searching yielded anything useful. The basic problem is to determine whether two frusta intersect. I need this to find out whether the objects illuminated by a spotlight are visible, for example so that I only update the depth shadow/light map when I have to. I figured the quickest way to do this is to determine whether the viewing volume intersects with the light's volume. The rest of the post assumes this technique - if you know a better one, I'd like to hear it, of course. :) Note that I only need to know if the frusta intersect, no details. I'd also like to avoid false positives, that is, using an algorithm that may claim that two frusta intersect, even though they don't. This is because the frustum tests are for avoiding render target switches, which are almost definitely more expensive than the intersection test. I've been thinking about this for weeks, but I'm kind of stuck. I'm already doing bounding-box/frustum intersection tests using an extension to the projection method described in [1], but its main shortcoming is that it may turn up false positives. I also can't find a simple (well, fast) way of applying this method to two frusta. My ideas so far have been: 1) Test whether any vertices of one frustum lie within the other frustum, and vice versa, by checking which side of each frustum plane a given vertex lies. If a vertex lies on the 'inside' of each plane, the frusta intersect. This won't work because two frusta can intersect although all vertices are 'free'. 2) Extend the frusta to pyramids in your mind. Take each of the 4 vectors from pyramid 1's apex (e.g. the camera or light position) to the vertices of pyramid 1's far plane and intersect them with pyramid 2's triangle faces. Calculate the point of intersection, and determine whether it lies between far and near plane of pyramid 2. If no intersections are found, do the same test against the near and far plane of pyramid 2, and check whether the intersections are within the quadrilateral. This will miss the case where one frustum completely contains the other, so one vertex of each frustum must be tested for being contained by the other frustum. The only reason I've included (1) is because I have a feeling it might be extensible to actually work. Method (2) seems awfully complicated and slow, as you have to check wether the vectors are parallel to the tested planes, etc. I'm also not 100% sure it'll work, either. Any ideas? Thanks ~phil [1] David Eberly, 3D Game Engine Design
~phil
Zakwayda
Zakwayda
Frusta are convex polyhedra, so you should be able to use any of the various algorithms for determining whether two convex objects intersect. I would recommend:

1. The separating axis algorithm, which could be implemented fairly efficiently for frusta. Specifically, you could exploit the fact that the front and back planes (usually) share normals (they are negatives of each other, but they are equivalent as far as the SAT test is concerned). For details on the SAT, check out Eberly's '3D Game Engine Design' and 'Game Physics' books, Christer Ericson's new book, perhaps van den Bergen's book (haven't read it yet), the archives here (if search is working), google, etc.

2. It's possible that the GJK algorithm could be specialized for an efficient frusta-frusta test, but I'd have to think about it. In any case, it would be harder to implement than SAT.

So I recommend the separating axis algorithm.

[Edit: Since you're dealing with arbitrary frusta (not necessarily the view volume), the front/back plane optimization may not apply - sorry. Still recommend looking into SAT though.]
Zakwayda
Zakwayda
I was thinking about this problem a little more since I last posted, and my initial answer may not have been as well thought-out as it could have been.

When you say frusta, do you specifically mean 6 planes? Or could the light volume have an arbitrary number of planes? Also, are the light volumes infinite or finite?

In any case, the SAT might not be the best choice. SAT is good for most 2D objects, 3D AABBs, OBBs, lines, triangles, and determining quickly that two convex objects do *not* intersect. However, for two arbitrary cuboids, 156 axes must be tested to determine conclusively that they *do* intersect. Not so good.

Another question is what sort of coherency can be exploited. I would assume that, as in most 3D simulations, your view frustum moves relatively little from frame to frame, except perhaps for the occasional sudden rotation. I would assume the same for your light volumes. There are algorithms which can take advantage of this coherency.

In short, the issue is boolean intersection between convex polyhedra. The good news is this is a solved problem in computer simulations. The bad news is that most of the algorithms (or at least any that are efficient enough to consider) are non-trivial to implement.

So here are some suggested references/algorithms:

1. Christer Ericson's new book on collision detection is excellent and discusses several approaches to convex intersection.

2. I haven't read the van den Bergen book, but I've heard it is also good, and covers the GJK algorithm in great detail, as well as including source code to the SOLID collision detection library.

3. For boolean algorithms that can exploit coherency and are likely more efficient than SAT, I'd look into Lin-Canny, V-Clip, and GJK. None is trivial to implement, but they could make your volume-volume intersection tests very fast.

4. You could also just use an already available coldet library (such as SOLID), although if you write it yourself you may be able to optimize it for your particular case.

Anyway, I do hope some of that was helpful to you.
bit64
bit64
It seems to me that this method would be inefficient for what you are trying to accomplish. You are wanting to find a volume that defines an intersection between two frustum and then see what objects are in that volume, correct?

Since you already need to do frustum testing for the view frustum against all objects somehow, then why not just take the subset of objects returned by your first test and test them against the spotlight frustum?

Though, perhaps I misunderstood your intentions.
Don't be afraid to be yourself. Nobody else ever will be.
Zakwayda
Zakwayda
Quote:
Since you already need to do frustum testing for the view frustum against all objects somehow, then why not just take the subset of objects returned by your first test and test them against the spotlight frustum?


That's a good point, but consider...

The method you mention most likely involves a number of additional tests to determine whether the objects found to be visible also intersect the light volume. Compare that to a single test (between the light volume and the frustum) that can potentially exclude the light volume from consideration completely.

Your method would certainly be easier to implement though. And maybe given his specific circumstances it could be as or more efficient. It's hard to say without knowing more about the application.
bit64
bit64
Quote:
It's hard to say without knowing more about the application.


True :)
Don't be afraid to be yourself. Nobody else ever will be.
JonnyQuest
JonnyQuest
Hi,

Thanks for the interesting replies. I haven't had time to go through, look up, and fully understand all the suggestions yet, but I'll answer a bunch of questions. Expect another reply later.

Quote:
Original post by jyk
When you say frusta, do you specifically mean 6 planes? Or could the light volume have an arbitrary number of planes? Also, are the light volumes infinite or finite?

Sorry, to clarify: we're dealing with two pyriamidal frusta with rectangular bases. Far and near planes are therefore parallel rectangles, and the other planes converge at a point, the apex of the cut-off pyramid.

Quote:
Original post by jyk
Another question is what sort of coherency can be exploited. I would assume that, as in most 3D simulations, your view frustum moves relatively little from frame to frame, except perhaps for the occasional sudden rotation. I would assume the same for your light volumes. There are algorithms which can take advantage of this coherency.

Good point. There won't be too much of a change from frame to frame.

Quote:
In short, the issue is boolean intersection between convex polyhedra. The good news is this is a solved problem in computer simulations. The bad news is that most of the algorithms (or at least any that are efficient enough to consider) are non-trivial to implement.

I'm not too worried about implementation difficulties, as long as I understand the algorithm and it does exactly what I want.

Quote:
Original post by bit64
It seems to me that this method would be inefficient for what you are trying to accomplish. You are wanting to find a volume that defines an intersection between two frustum and then see what objects are in that volume, correct?

No, at least for now I'd be happy to know if they intersect or not.

Quote:
Original post by bit64
Since you already need to do frustum testing for the view frustum against all objects somehow, then why not just take the subset of objects returned by your first test and test them against the spotlight frustum?

Well, the point of this is to avoid that. If the range of a spotlight doesn't intersect the visible area, I can completely drop the object or scene graph node vs. light frustum comparisons. I'd estimate that only about 5-10% of all lights are going to be visible at any given time.
Usually, I'd implement your method first and then slowly move to something better, but I'm hoping the "something better" is going to be nicer to implement in addition to being more efficient, so I'd prefer not to pollute the code with a slow and ugly algorithm... Besides, I'm somewhat time-constrained.

Thanks with your help so far!

~phil
~phil
JonnyQuest
JonnyQuest
OK, I've been following up various suggestions. I agree on the Separating Axes method being a pain in this case, I don't think it's going to be worth the effort.

I can't find any of the books you suggested in our university library, and buying them just for a few checks per frame is hardly going to be cost-effective.

From the googling I've done on the various keywords you've provided, the V-Clip algorithm sounds good, at least judging by the abstract of Brian Mirtich's Paper. I'm now in the process of reading said paper. I'm especially liking the ability to cache the results from frame to frame, that should really speed things up.

Thanks for the input so far, I'll probably post again when I've understood V-Clip.

~phil
~phil
bit64
bit64
Quote:
Well, the point of this is to avoid that. If the range of a spotlight doesn't intersect the visible area, I can completely drop the object or scene graph node vs. light frustum comparisons. I'd estimate that only about 5-10% of all lights are going to be visible at any given time.


Ya I sat down and thought about this more after I posted and your approach is making more sense to me.

Good luck,
Don't be afraid to be yourself. Nobody else ever will be.
GameCat
GameCat
The separating axis test isn't that hard to implement. It is also very easy to make temporally coherent. You just cache the last separating plane you found and try that first during the next test. That way, you typically only test one plane until the two objects start to intersect. A symmetrical frustum has 5 unique normals and 6 unique edges as far as SAT is concerned so the number of separating axis tests required certainly aren't enormous. A total of 46 tests, and that's just if the frustra are actually intersecting since you can early out when you find a separating plane. If you ignore the near plane each frustra also has just 6 triangles so you could probably just do a brute force mesh-mesh intersection test, although that will probably be slower.

Another idea is to approximate the light frustum with some bounding volume like a cone or a sphere and ignore the false positives you'll get. What's right to do really depends on your CPU budget for this.
Zakwayda
Zakwayda
As GameCat said, if your frusta are uniform and symmetrical, the SAT may once again be a contender. Also, it will be quite a bit easier to implement than GJK or VClip (watch out for numerical problems with nearly parallel edges, though).

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.