• Advertisement
Sign in to follow this  

Intersection of two frusta

This topic is 3325 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello! I want to optimize my light rendering by creating a snug-fit (axis aligned) bounding box around the visible part of a light's frustum, then just shade pixels inside the box. My first attempt was to simply calculate the corners of the light's frustum in world space, then transform them into normalized device coordinates using the camera's modelview and projection matrices. I then simply created the bounding box using those coordinates. The result was bad, there were false negatives, and the bounding box wasn't a perfect fit. My second attempt was to turn the light frustum corners into a list of edges which were intersected with the planes of the camera's frustum. If an edge is outside the camera's frustum, it would be discarded. The problem here was the discarding of edges; it caused false negatives. But what else than to discard them can I do? Hope I made myself clear!

Share this post


Link to post
Share on other sites
Advertisement
are false positive a problem? Else you can use the standard way frustum culling works. Use the largest frustum directly, and use the bounding box around the smallest, and cull the bounding box against the frustum.

If you want a perfect test, the SAT will sort you out, but it will be relatively expensive. You would need to test...

6 faces per frustum (with near and far plane considered).
6 edge sets per frustum.
-> 6 + 6 + 6 x 6 = 48 SAT test in the worst case.

using a bounding box and a frustum.
-> 6 faces for frustum (with near and far plane considered).
6 edge sets for frustum.
3 faces, 3 edge sets for the bounding box.
-> 6 + 3 + 6 x 3 = 27 SAT tests in the worst case. Almost half.

if you have false negatives, then it could simply be a code bug.

Share this post


Link to post
Share on other sites
Thanks for your reply!
So you're saying that I should compute a bounding box for the smallest frustum in world space, then clip it to the bigger frustum? How do I do that, really? And how do I calculate the size of a frustum? Why does it even matter, seems pretty arbitrary to me.

I'm willing to accept some false positives for now, but I will eventually have to optimize it further in the future.

Just to make myself a little more clear; both of my attempts failed because of the light frustum corners being outside view. 1. projecting corners outside the view using the camera matrices sometimes result in weird things, like where the Z wraps to the other side of the camera.
2. if the edge between two corners in the light frustum is completely outside the view frustum, two whole faces of the frustum will disappear. those faces might actually be visible.

Share this post


Link to post
Share on other sites
the frustum culling of an AABB is a pretty common problem in rendering, which has has been solved many times. I can't give you a method myself though!

Bounding the smallest with an AABB, and testing against the large frustum will reduce the number of false positives, as the space wasted by building an aabb will be less.

I can give you an algorithm to do exact frustum culling (or in fact, any convex shape, like box, pyramids, triangles and so on).

It's basically the SAT (seprating axis theorem). What the sat does is work on convex geometry to find a plane that will separate two convex objects.



struct Vector
{
float x, y, z;
float dotProduct(const Vector& v) const
{
return x*v.x + y*v.y + z*v.z;
}
Vector crossProduct(const Vector& v) const
{
Vector result;
result.x = y*v.z-z*v.y;
result.y = z*v.x-x*v.z;
result.z = x*v.y-y*v.x;
return result;
}
};

struct Convex
{
enum { MAX_VERTICES = 16, MAX_EDGES = 16, MAX_FACES = 16 };

Vector m_vertices[MAX_VERTICES];
int m_numVertices;

Vector m_edges[MAX_EDGES];
int m_numEdges;

Vector m_faces[MAX_FACES];
int m_numFaces;
};

void computeBounds(const Vector& dir, const Convex& convex, float& min, float& max)
{
min = max = convex.m_vertices[0].dotProduct(dir);

for(int i = 1; i < convex.m_numVertices; i ++)
{
float d = convex.m_vertices.dotProduct(dir);
if(d < min) min = d;
else if (d > max) max = d;
}
}

bool separated(const Vector& dir, const Convex& a, const Convex& b)
{
float mina, maxa;
float minb, maxb;

computeBounds(dir, a, mina, maxa);
computeBounds(dir, b, minb, maxb);

return (maxa + 0.000001f < minb || mina > maxb + 0.000001f);
}

bool intersect(const Convex& a, const Convex& b)
{
for(int i = 0; i < a.m_numFaces; i++)
{
if(separated(a.m_faces, a, b))
return false;
}

for(int i = 0; i < b.m_numFaces; i++)
{
if(separated(b.m_faces, a, b))
return false;
}

for(int i = 0; i < a.m_numEdges; i++)
{
for(int j = 0; j < b.m_numEdges; j++)
{
if(separated(a.m_edges.crossProduct(b.m_edges[j]), a, b))
return false;
}
}
return true;
}


If you take a box, a box is made of 8 vertices, 6 faces, and 12 edges.

However, from those 6 faces are really 3 pairs of faces that are back-facing each others. Similarly, from the 12 edges, you have 4 edges all sharing the same unique direction.

so in reality, you only need to consider 3 faces, 3 edges, and 8 vertices to convert a box into a Convex fit for the separation axis theorem above.

Similarly for the frustum (with near and far planes), you have 8 vertices, 6 faces, and 12 edges. However, you only need to consider 5 faces, and 6 edges (the rest of them are parallel to those major features, thus redundant).

setup two convex, one for each frustum, and call the intersect routine.

if you want to test against a single triangle, then you will need to fill in one of the convex with one face normal, three edges, and three vertices.

Share this post


Link to post
Share on other sites
Thanks a lot! I will try the SAT and see what kind of results I get.

Edit:
looking at your code, how do you store edges and faces? Not like a set of coordinates it would seem.
Is m_faces a collection of normals? and m_edges are tangents?

And I hope I can use the SAT to determine the maximum and minimum coordinates that are in both frusta. The intersecting points, that is.

[Edited by - patrrr on January 17, 2009 12:06:23 PM]

Share this post


Link to post
Share on other sites
m_edges[] are just what's between connected vertices. planes are just plane normals.

if you have two point A and B forming an edge, the edge vector would be (B - A). Don't need to normalised, nor the face normals. In fact, you can just take cross products between two edges that belong to a face. It wont matter if the normal is pointing the wrong way either.

What do you mean by intersection points? The SAT will not give you intersections per-se, but can give you how much the frustum intersects (by calculating the mtd vector).

if you want intersection points (meaning, intersecting edges with faces), I'm afraid you'll have to do it the hard way.

Now I wonder if the SAT code could be imlpemented efficiently using vertex shaders... hmmm that would be lovely.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement