Jump to content

  • Log In with Google      Sign In   
  • Create Account

Get a convex polygon from a set of infinite planes


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
2 replies to this topic

#1 ill   Members   -  Reputation: 320

Like
0Likes
Like

Posted 05 August 2012 - 01:35 PM

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.

Sponsor:

#2 Álvaro   Crossbones+   -  Reputation: 13934

Like
0Likes
Like

Posted 05 August 2012 - 03:39 PM

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?

#3 Crowley99   Members   -  Reputation: 178

Like
0Likes
Like

Posted 06 August 2012 - 07:34 AM

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).




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS