Surface Reconstruction between Simple Polygons via Angle Criteria

Emo Welzl, Barbara Wolfers Institut für Informatik Freie Universität Berlin email: Report B 94-11 April 94

Get the report here or by anonymous ftp: 
File:   pub/reports/
We consider the problem of connecting two simple polygons $P$ and $Q$ in parallel planes by a polyhedral surface. The goal is to find an optimality criterion which naturally satisfies the following conditions: (i) if $P$ and $Q$ are convex, then the optimal surface is the convex hull of $P$ and $Q$ (without facets $P$ and $Q$), and (ii) if $P$ can be obtained from $Q$ by scaling with a center $c$, then the optimal surface is the portion of the cone defined by $P$ and apex $c$ between the two planes. We provide a criterion (based on the sequences of angles of the edges of $P$ and $Q$), which satisfies these conditions, and for which the optimal surface can be efficiently computed. Moreover, we supply a condition, so-called {\em angle consistency}, which proved very helpful in preventing self intersections (for our and other criteria). The methods have been implemented and gave improved results in a number of examples.