Sign in to follow this  

Get a convex polygon from a set of infinite planes

This topic is 1956 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

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 this post


Link to post
Share on other sites
Well, the algorithm you need is tricky. I read [url="http://cgal-discuss.949826.n4.nabble.com/Intersection-of-two-CONVEX-3D-polyhedrons-td4564202.html"]somewhere [/url]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 this post


Link to post
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).

Share this post


Link to post
Share on other sites

This topic is 1956 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this