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.

**0**

# Get a convex polygon from a set of infinite planes

Started by ill, Aug 05 2012 01:35 PM

2 replies to this topic

Sponsor:

###
#2
Crossbones+ - Reputation: **13934**

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?

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
Members - Reputation: **178**

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

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