Computing the Width of a Three Dimensional Point Set

Introduction and Motivation

Before giving the exact definition of the width of a point set, let us consider the following problem, where knowledge of the width of a point set might be useful.
In the late 80's the application of computer aided design (better known as CAD) was developed. This entirely new technique helps the engineers to rapidly generate virtual objects without getting "physical". For this prototyping process the object of desire must be visualized, verified in some matter and optimized. Since one does not want to build physical versions of prototypes for these tests, simulations and virtual experiments are necessary.

Once the virtual object passed all the tests and is well designed, it has to be manufactured. For this purpose Stereo-Lithography was developed. Stereo-Lithography (or three-dimensional printing) was the first commercially available layer-additive process to enable the rapid generation of physical objects directly from the CAD database. The Stereo-Lithography process begins with the generation of a CAD model of the desired object, as you can see in the figure.
The next step then is to tessellate the boundary surfaces of the CAD description, that is the description is formed as a connected array of triangles (triangulation). The triangles may be as large or as small as desired; with the obvious advantage of finer resolution in the case of small triangles and of less storage capacity with large triangles.
After the surface of the object has been triangulated, all useful information is now stored in the STL-file - the STereoLithography file. This file basically consists of the x-, y- and z-coordinates of the three vertices of each surface triangle and of an index that describes the orientation of the surface normal. This index is necessary to ensure that a clear distinction between inner and outer surfaces is made.
Once the STL-file has been generated from the original CAD description of an object, the following procedure involves slicing that file: Here a series of closely spaced horizontal planes are mathematically passed through the tessellated object file. The result (the SLI-file or SLIce file) represents a series of closely spaced two dimensional cross-sections of the three dimensional object, each of these cross-section at a slightly different z-coordinate.
Earlier the most common layer-thickness was about half a millimeter. As Stereo-Lithography achieved finer precision and improved accuracy, the slice thickness values have decreased to 0.1 mm and the laboratories are still working on minimization of this thickness. This is important, because finite layer-thickness causes stair-stepping errors in the z-axis. These errors are inevitable but have to be minimized of course.

Among other criteria the build direction, i.e. the direction in which these layers are manufactured, plays an important role, because the number of layers needed to get a physical model increases with the thickness of the object in this build direction. And the more layers we build the more time we need; or vice versa the less layers we have to build the more time we can save. We have the problem to find the optimal build direction. Once this direction is given, then the layers are orthogonal to this direction and the number of layers needed can be computed in terms of the distance between the first and the last layer.
Thus choosing an optimal orientation of the model is an important - but not the only - factor to save time in the manufacturing process. And the optimal build direction can be computed by solving the width problem.

Problem

The problem of finding the direction of minimal extension of the object can mathematically described as follows: Given a set of points S={p1, ..., pn} in 3 dimensions. The width of S is defined as the minimum distance between parallel hyperplanes of support of the convex hull of S.

To compute the width of the point set S we can first use a convex hull algorithm to reduce the problem space. Points p_i inside the convex hull are of no importance to find parallel hyperplanes of support of S. As the width of S and the width of the convex hull P=conv(S) is the same, we therefore assume that every given point in S is also a vertex of the convex hull of S.

There are two similar problems about computing the width:

1. Compute the minimum distance between parallel hyperplanes of support that enclose S.
2. Compute one (or all) direction(s) d, so that the distance between two parallel hyperplanes of support is minimal and so that these hyperplanes enclose S and are orthogonal to d.

Note these two problems are only similar, not equivalent. Perhaps there exists an "oracle" that gives us the minimum distance, but we have no idea where the corresponding width-determining hyperplanes are situated in space.

One might expect that these hyperplanes will always be determined by a vertex on one side and a facet on the other side of P to be lying on the two hyperplanes respectively. But this isn't true in general. The width is determined by (at least) 4 vertices of S. For example in three dimensions the width can also be determined by two edges (two dimensional faces) of conv(S).

Implementation Notes

We present an exact and robust algorithm to solve the three dimensional width problem, that is to determine the two parallel planes of support of conv(S) with minimal distance. The algorithm uses neither the heavy machinery of a point location data structure nor a sweep through an arrangement of lines - instead, it uses only some simple optimization techniques and Linear Algebra. The sole involved geometric algorithm is the computation of a convex hull that determines the combinatorial structures needed in the further algorithm.
The two libraries LEDA and CGAL are used to implement the algorithm that is written in C++.
The algorithm is also part of CGAL. I refer to the CGAL-Homepage for further informations.