Jump to content
  • Advertisement
Sign in to follow this  
ill

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.

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
Advertisement
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 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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!