A solution to the "next best view" (NBV) problem for automated surface acquisition is presented. The NBV problem is to determine which areas of a scanner's viewing volume need to be scanned to sample all of the visible surfaces of an a priori unknown object and where to position/control the scanner to sample them. A method for determining the unscanned areas of the viewing volume is presented. In addition, a novel representation, positional space, is presented which facilitates a solution to the NBV problem by representing what must be and what can be scanned in a single data structure. The number of costly computations needed to determine if an area of the viewing volume would be occluded from some scanning position is decoupled from the number of positions considered for the NBV, thus reducing the computational cost of choosing one. An automated surface acquisition systems designed to scan all visible surfaces of an a priori unknown object is demonstrated on real objects.

An algorithm for the integration of meshes derived from range data is presented. All of the triangles from either mesh which have sampled the same surface patch of the object are identified as co-measurements and only the most confidently acquired one is kept. Co-measurement identification is based on the position and orientation of the range scanner when each triangle was sampled. Once the redundant triangles have been removed what remains is a patchwork of unconnected non-intersecting meshes which cover the sampled areas of the object. Neighborhood relationships established between the edge points of each patch are used to seam them together. The final mesh is guaranteed to be plausible in the sense that each triangle represents a surface which could have been scanned given the positions and orientations of the range scanner and 2-manifold with the exception that a vertex may be incident to two triangles that are connected only through that vertex. The algorithm performs equally well in areas of low and high curvature.

Acquiring the complete surface geometry of an object using a range scanner invariably requires that multiple range images be taken of it from different viewpoints. An algorithm is presented which solves the "next best view" (NBV) problem: determine the next position for the range scanner given its previous scans of the object. As part of a complete surface acquisition system the scanner's next position should cause it not only to sample more of the object's surface but to resample part of the object already scanned to allow for the registration and integration of the new data with the previous scans. A novel representation, positional space, is presented which facilitates a solution to the NBV problem by representing what must be and what can be scanned in a unified data structure. The expensive operation of determining the visibility of part of the viewing volume is computed only once, not for each potential position of the scanner thus breaking the computational burden of choosing the NBV from a large number of positions. No assumptions are made about the geometry or topology of the object. The algorithm is self-terminating will scan all visible surfaces of an object and can be directed to resample surfaces which were scanned with low confidence. In addition, the algorithm will work with nearly any range camera and scanning setup. A completely automated surface acquisition system featuring the proposed NBV algorithm is demonstrated on a real object.