Minimising Longest Edge for Closed Surface Construction from Unorganised 3D Point Sets

Abstract

Given an unorganised 3D point set with just coordinate data, we formulate the problem of closed surface construction as one requiring minimisation of longest edge in triangles, a criterion derivable from Gestalt laws for shape perception. Next we define the Minimum Boundary Complex (BCmin), which resembles the desired surface Bmin considerably, by slightly relaxing the topological constraint to make it at least two triangles per edge instead of exactly two required by Bmin. A close approximation of BCmin can be computed fast using a greedy algorithm. This provides a very good starting shape which can be transformed by a few steps into the desired shape, close to Bmin. Our method runs in O(nlogn) time, with Delaunay Graph construction as largest run-time factor. We show considerable improvement over previous methods, especially for sparse, non-uniform point spacing.