Get a convex polygon from a set of infinite planes

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

Recommended Posts

In the Doom 3 map format, their convex brushes are stored as 4 or more infinite planes, so it's somehow possible to get the polygon in the end.

I basically need this for my view frustum culling. I have the view frustum itself, but I might sometimes need to additionally clip it against some volume defined by its own planes. In the end I need a set of points and edges joining the points so I can rasterize it inside a uniform 3D grid with an algorithm I'm working on.

Share on other sites
Well, the algorithm you need is tricky. I read somewhere that you can compute the dual of your planes (ax+by+cz=1 maps to the point (a,b,c)), then compute the convex hull, and then compute the dual back (I imagine that step means map each face of the convex hull into a point in through the same mapping). My projective geometry is rusty to determine if that should work in general. I just did a little test by hand for the intersection of three half-planes in 2D and it seems to work, as long as you place the origin somewhere inside the intersection.

But if all you need is the rasterization, you could simply loop over the points in your grid and test each one of them agains the half-spaces, right?

Share on other sites
The previous post on duality is correct - IIRC, the planes do need to contain the origin for this to work (you can translate the planes by any point inside if it's not).

For a direct solution If you take any 4 non-parallel planes in your set, there are four ways to choose three planes. The intersection of these 3 planes will give you a vertex. This will give you four vertices - turn this into a tetrahedron (4 triangles, 4 vertices, 6 edges). Then iterate through the remaining planes clipping this volume at each iteration. At the end you have the resulting polyhedron. If you search my posts, I gave a lot more detail on one of my last posts about how to do the clipping (as part of a convex polyhedron intersection algorithm).

1. 1
2. 2
Rutin
23
3. 3
JoeJ
20
4. 4
5. 5

• 23
• 40
• 23
• 13
• 13
• Forum Statistics

• Total Topics
631733
• Total Posts
3001928
×