I have a data structure for convex polyhedrons containing a set of planes, a set of points and a set of polygons with indices to the points for representing level geometry. When the points are no longer planar enough from 64-bit rounding errors, I regenerate the polygons from the plane equation by creating a convex polyhedron from the bounding box and cutting it with each surface plane.

But now I want to save the shapes into a file without redundancy for maximum version compatibility so that there will be only by a set of planes for each convex polyhedron.

Is there an efficient algorithm to get a bounding box from only a set of surface planes defining the convex polyhedron?

It may include more volume than actually used but not so much that it loses significant precision for the polygons.

Plan B is to generate the shape twice starting with an insanely large box and then redo using the given points but that is a waste of computations.

Plan C is to just save the whole level's bounding box in the file but that is not a clean format.

Efficient? Probably not. But I do know you can do this:

• Transform planes to dual space, this form points
• Compute convex hull of points
• Transform planes, yet again, with dual transform
• You now have the points of intersection for the original planes
• Compute bounding box of these points

More info.

What Randy suggests *only* works if the origin is inside the convex polyhedron. I guess you can use the original points to shift the polyhedron before constructing the dual.

From the QHull link:

"Assume the origin is inside the cone and let the first cone's facets define a set of halfspaces"

Thanks for your replies. If there is no performance improvement in doing it then I will probably just stick to plan B or C that are safe. I might be able to represent infinite shapes for outdoor spaces if the bound is set manually or to a reasonable constant.

I think the standard approach is to have a really large "world cube" as the initial shape and clip it against the planes. This is the approach in most papers I've read and the one I'm using. I am however using a plane based representation for all the actual operations, and only compute points for rendering since this allows me to have 100% robust CSG operations.

I have managed to implement it using the very large box method and fraction representation of the planes. The point on the plane is a fraction for each dimension and the normal is an integer vector using its own length as the denominator. Then I won't have problems with rounding errors nor alternative decimal signs in the file format.

I am now thinking about using direct carving on additive volumes like in Hammer World Editor or have both additive and carving volumes like in Unreal Editor.

The former would allow splitting up geometry into pieces and perform heavier operations. Adding occlusion planes will be trivial if no subtracting volume touches a certain area. I will probably have to make the world in multiple sets anyway for culling and dynamic rigid bodies.

The latter would reduce the need for merging of fragments after filling a hole but I will probably implement the optimization anyway.