Computing Maximum-Area Sections of Convex Polyhedra

Applet

The interactive Java applet lets you explore the sectional area properties of arbitrary convex polyhedra. Please read the instructions carefully before using the applet, or you won't get as much out of it.

Instructions - Manipulating the model

Action	How to do it
Rotate the model around its x and y axes	Drag with the left mouse button.
Rotate the model around its z axis	Drag up/down with the right mouse button.
Translate the model in the x and y directions	Hold down CTRL and drag (some point other than a vertex) with the left mouse button.
Translate the model in the z direction	Hold down CTRL and drag (some point other than a vertex) up/down with the right mouse button.
Translate a vertex in the x and y directions	Hold down CTRL and drag the vertex with the left mouse button.^{0, 1}
Translate a vertex in the z direction	Hold down CTRL and drag the vertex up/down with the right mouse button.^{0, 1}
Add a vertex	Double click. This adds a vertex at the average z depth of the other vertices such that the new point's projection appears exactly under the mouse cursor.^{0, 2}
Remove a vertex	Hold down CTRL and double click on a vertex.^{0, 3}

⁰ These actions change the model. In each case, the new polyhedron is taken to be the convex hull of the set of points after the action is taken. This guarantees that our model is always a convex polyhedron.

¹ When translating a vertex, the hullifying operation is performed when the vertex being moved is released, so the intermediate object you see when translating a vertex may not be a legal polyhedron. Note that if you translate a vertex into the convex hull of the remaining vertices, it will disappear when you release the mouse button.

² Adding a vertex is equivalent to an insertion of a vertex into the convex hull. This is why double clicking on the interior of the polyhedron will probably not make a vertex appear, since it gets swallowed up immediately by the convex hull.

³ The applet will not let you remove a vertex if the convex hull of the remaining vertices is not a polyhedron (if, for instance, the remaining vertices are coplanar).

Instructions - Viewing options

Show information shows, in the bottom left hand corner of the viewport, the number of vertices, edges and faces of the polyhedron and in the top left hand corner, the equation of the plane orthgonal to the x axis that induces a maximum-area section on the polyhedron. The actual sectional area is also shown. This is computed in real time using a binary search approach, as discussed on the algorithms page. Whenever the polyhedron is transformed, the information is updated accordingly.

Show maximum area section shows, in dark blue, the polygonal intersection of the polyhedron with the plane that induces the maximum area section. This, too, is computed in real time.

Lock maximum area section is enabled only when the maximum area section is shown and 'locks' the current maximum area section polygon, in the sense that rotating or translating the model will maintain it. This is useful because it is difficult to clearly see maximum area sections if they are in the yz plane. This feature allows you to find the maximum area section of a polyhedron, lock it, then rotate the polyhedron to inspect the maximum area section from any angle. When you lock a maximum area section, the current (realtime) maximum area section is disabled to prevent confusion between the two sections, but it can be enabled by checking Show maximum area section again. This will result in two maximum-area polygonal sections being shown simultaneously. If the polyhedron is modified (that is, a vertex is added, removed or translated), the section is unlocked, as these operations might change the polyhedron. If Show information is checked, then the area of the locked maximum area section is shown in the top left hand corner of the viewport.

Show hovering section shows, in lighter blue, the polygonal section of the polyhedron obtained when a plane orthogonal to the x axis is sliced through it at the position under the mouse cursor. Also, if Show information is checked, then the equation of the plane yielding the hovering section and its sectional area are shown in the top left hand corner. This is a useful feature for finding sectional areas throughout the polyhedron and for convincing oneself that sectional area in convex polyhedra is indeed a unimodal function.

Show coordinates shows, hovering beside each vertex, its coordinates in xyz space. This is useful for carefully positioning vertices.

Show drums partitions the polyhedron into drums by slicing a plane through the x coordinate of each vertex. The resulting intersections are shown as blue-green polygons in the polyhedron. These are computed in real time.

Lock drums is equivalent to Lock maximum area section, but locks the drums, if they are shown.

Reset returns the applet to its initial state, showing the initial octahedron.

Applet

Remarks

I've tested the applet with polyhedra of up to 60 vertices and more than 100 faces. It performed reasonably well, slowing down only marginally. Conceivably, however, it might fail or crash on extremely complex polyhedra.

A note on numerical error: As with any tool involving floating point arithmetic, there may be some numerical error. However, it shouldn't be much of a problem, particularly in the sectional area computations. The only unusual effect is that occasionally, when four or more vertices are coplanar, certain rotations will make the applet think that they aren't, making one or more diagonals appear suddenly. Other rotations will make these diagonals disappear again. This is not a severe problem, since it occurs very sporadically and since these fluctuating diagonals are always degenerate. The robustness of the implementation of the 3D convex hull algorithm ensures good results.

A note on the projection model: The camera, by default, is positioned at (0, 0, -4) and the projection plane is z = 0. x, y and z point right, up and forwards, respectively (yes, it's a left handed coordinate system). The applet will not let you translate the model such that its minimum z extent is behind the camera. Trying to do so will have the effect of pushing the camera backwards. This doesn't accomplish anything interesting, but you can try it out if you like.

A note on rotations: When you rotate the model, the centre of rotation is the point of average x, y and z coordinates, averaging over the vertices of the model.

Acknowledgements

The applet contains a robust 3D QuickHull implementation by John E. Lloyd. It is distributed under this copyright license. The rest of the code is original.

Next: References.