Polyhedra of Minimal Area as 3D Object Models

1. INTRODUCTION

Ullman's "Structure fran Motion TheOfem" [16) am similar schemes [1) [8) [9) erw.ble the three dimensional (3D) cOOfdirw.tes of CXlrresporded points on the surface of a rigid object to be exuacted from a aequence of imqes. After the 3D cocxdirw.tes of a set of points has been fOWKI, a natural next step Is to form a 3D object model for the set of points [9) [3). The object model rould then be used for prediction and verification in later frames of the imiJ8C scqucm:c, or for recognition purposes, or for shape analysis.

Let us Ignore the other information that might be extncted from the imap, am ask the following qUestion: What is the most reasonable 3D obj!Jct model for a set of 3D points? Posed in this swk form, there is surely no best answer for all applications. First, there are a large variety of reprcsenwions for solid objects [ 14), am serord. there are a variety of definitions of "most reasonable" for each reprcseruation.

This paper explores one possible object model: polyhedra. It is proposed that a polyhedron of minimal surface area is the most "natural" polyhedral model for a given set of points. This roncept is explored theoretically, and an algorithm for axnputing an approximation to this polyhedron is described. Preliminary results of an implementation of the algorithm are presented.

l. POLYHEDRA OF MINIMAL SURF ACE AREA

We will say that a simple polyhedron · P is a minimal :sutjilce area polyh«Jron for a set of 3D points S iff (a) the set of vertices of P is identical to S, am (b) no other simple polyhedron whose ver­ tex set is predsely S has a smaller surface area.

One rould also define polyhedra of maximal volume, but these seem to be tellS "natural" than polyhedra of minimal surface area. A well-known fact fran elemenwy physics may partially explain the naturalness of minimal area surfaces: the tension in in certain surfaces (e.g., -P bubble films) is proportional to their area, so that they tend to form the surface of minimal area wher­ ever they have free movement.

The idea that maximizing the volume or minimizing the sur­ face area may result in natural polyhedral shapes is not new. Kep­ pel [7) interpolated triangular faces between parallel slices by max­ imizing the samwiched volume, and Puchs et a/ [4) attacked the

Tho nolion or a "simple P011Mdron· may be made p~so by a combina· IOriaiiOPOioiY deftnllion, e.a~ 16). We imend lhe dollnition 10 require lha1 the sn1ke h&-. lOftlS 0. i.e., 1llere are no holes.

Polyhedra of Minimal Area as 3D Object Models

Joseph O'Rourke

Electrical Engineering Deparunent Johns Hopkins University Raltimore, MD 21218

arne problem by minlmlzina an arbitrary function of the tiles, for example, the surface area. The fact that only a single cylindrical band of faces have to be axnputed makes the interpolation problem far more uactable than the general case under consideration here.

A few basic properties of minimal area polyhedra are claimed here without proof:

• ( 1) A minimal area polyhedron exbtl for every set of 4 or more 3D points that are not all coplanar.
• {2) For a given set of 3D points, a minimal area polyhedron is not necessarily unique.
• The comex J.l/1 is a minimal surface area polyhedron for the set of hull vertices, since the a>nvex hull is the oflly simple polyhedron for its vertices.
• The romputation of the 2D analog of the minimal area polyhedron, the minimal perimeter polygon for a set of 2D points, is NP-hard; I rorUcc:turc that the 3D problem is NP­ hard as well.

The reason that the 2D problem is NP-hard is that the minimal per­ imeter polygon is identical to the Euclidean Travelina Salesperson Path, am the computation of this has been shown to be NP-hard [S) [12).

If the computation of the minimal area polyhedron is in fact a fundamentally inuactable problem, heuristics am sub-optimal algo­ rithms arc inevitable. A number of Traveling Salesperson Problem {TSP) heuristics are known [2) llSl but it is not clear how these may be directly applied to the 3D problem. However, their sense may be mimicked, am in the next section, an algorithm is pro­ pcl8Cd fa computing an approximation to the polyhedron of minimal surface area via a type a "greedy" algorithm.

3. ALGORITHM: SHRINKING FROM THE HULL

That the a>nvex hull is a minimal area polyhedron for its ver­ tices {{3) above) suggests that it be used as the starting point of an algorithm that systematically modifies a given polyhedron to include new points. The assumption is that most obj!Jcts encountered in the real world have tarse convex sections that coincide with the hull, am so an algorithm which starts wilh the convex hull will be fast am accurate on these objects.

The two dimensiorllll convex hull is sometimes explained as the shape that a rubber bam would take were it to encompass a set of pegs placed at the point locations. The physical analogy can be extemed to non-convex three dimensional shapes: there is a type of electronic plastic shieldina that shrinks to ronform to whatever shape it encloses when heated. t This is roughly the behavior intemed for the algorithm below:

t ThlsanaloaY Ms suaes&ed 10 me by Bernd Neumann.

Ccmpute the convex hull;

while (there are internal points) do

bqlD

• ( 1 ) Choose a point internal to the hull;
• Modify the current polyhedron to include it;
• Make local adjlsunents to the polyhedron in the vicinity of the modified region.

eDd

The internal point chosen in step (1) is the one that is the "best" in the following sense. Each internal point is associated with the closest face that it onhogoii81Jy projects into, or j.lst the closest face if it projects into none. An area stretch factor is ccmputed for each point as the ratio of the area that would result if the closest face were modified as in step (2) to the area of the closest face. The "best" interll81 point is the one with the smallest stretch factor. The modification in step (2) consists of removing the face of the polyhedron closest to the chosen point, and replacing it with a number of faces that reach in towards the point and include it as a -w:rtex (see Figure 1).

This modification essentially puts a dent into the polyhedron, and it is quite possible that i· will disturb the minimality of the surface area in the neighborhood of the dent. Step (3) of the algorithm is intended to improve the polyhedron in the vicinity of the alteration via a simple local transformation, called here a flip traMformation (see Figure 2).

The Oip transformation should only be performed if it "improves" the surface. Currently the improvement is measured by a heuristic mix of three terms: (a) the area reduction, (b) the perimeter reduc­ tion, and (c) the reduction in the sharpness of the face angles. If it i3 performed, then the neighboring faces should be considered for the flip operation also, and so on, recursi"Vely. The cascading is guaranteed to halt eventually, since only inward flips are permitted.

Note that the algorithm is essentially a "best-first" or "nearest neighbOr" algorithm, but with local impro"Vements after each greedy A preliminary version of the algorithm has been imple­ mented, and three samples of its performance are shown in Figures 3, 4, and S. In each of the examples, the conve" hull of the input point set is a 26 point cylinder dctermiood by two 12 point ring.~ plus a point in the center of each cap. The examples differ in the number and placement of the points internal to the hull . In Figure 3, 27 internal points form a spherical dent in the side of the cylinder. The 32 internal points in Figure 4 are distributed in 3 rin&'! about the cylinder uis, the middle one having a smaller radius than its symmetrically placed neighbors. FigureS's SO inter­ nal points lie on the surfaces of two intersecting hemispheres. In all three examples, the algorithm has produced a surface close to the "natural" one, although some minor quirks are evident in the surface shown in Figure 5.

4. DISCUSSION

Relative to naiw ean:h, which mquires exponential time, the shrinldng aJaorithm is quite fast. The three dimensional oonvex huU of a set of 11 points can be computed in time 0(11 log 11) by the divide-and-conquer method of Preparata and Hong [13). · The remainder of the algorithm has a c05t of 0(1./'11) in the current implementation, where I is the number of the 11 points internal to the hull and f is the averqe number of flip uansformations per step. t This is &:ertainly no worse than 0 (II 3 ), and may be 0 (II 2 ).

The main theoreti~ drawback of the algorithm is that, in contrast to some of the TSP heuristics [2) [lSI. it is not guaranteed to achieve a surface area within a fixed percemqe of the minimal area. The algorithm can be led asuay by &:ertain inputs; this is typi­ cal behavior of algorithms that seek a global optimum via heuristic-guided local search.

Fi.rally, it is rarely the case that a 3D object model must be consuucted solely from a set of 3D points: usually, other informa­ tion is available. For example, the location of certain sharp edges may be known, or a silhouette may be available. The point of this note is to sugest that surface area minimization might be used as an aid in the fonnation of JD object models when the other avail­ able consuaints are insuftlcient for completely determining the 3D shape.

ACKNOWLEDGEMENTS

The work reported in this communication was begun at H.-H. Nqel's laboratory at the University of Hamburg. I thank Professor Nqel and his colleques for their hospitality and for providing a stimulating research envirorment.

· This has been lmplernenled In Pass!, and Is remalkably ,_Sl. requlrlna only 17 IOQOndS of CPU lime (on a DEC-Kl.lO) 10 compule lhe huU of 256 110in1s. See Ill I for deWis.

t For lhe examples shown In Fi&ures 3-S, /-.3.