Feature Extraction From Point Clouds

Proceedings, 10th International Meshing Roundtable, Sandia National Laboratories, pp.293-305, October 7-10 2001

MESHING
RESEARCH
CORNER

10th International Meshing Roundtable
Newport Beach, California, U.S.A.
October 7-10, 2001

Stefan Gumhold
WSI/GRIS
University of Tubingen
Email: stefan@gumhold.com

Xinlong Wang and Rob Macleod
Scientific Computing and Imaging Institute
University of Utah, Utah
Email: wangxl@cs.utah.edu, macleod@cvrti.utah.edu

Abstract
This paper describes a new method to extract feature lines directly from a surface point cloud. No surface recon- struction is needed in advance, only the inexpensive computation of a neighbor graph connecting nearby points. The feature extraction is performed in two stages. The first stage consists of assigning a penalty weight to each point that indicates the unlikelihood that the point is part of a feature and assigning these penalty weights to the edges of a neighbor graph. Extracting a sub-graph of the neighbor graph that minimizes the edge penalty weights then produces a set of feature patterns. The second stage is especially useful for noisy data. It recovers feature lines and junctions by fitting wedges to the crease lines and corners to the junctions. As the method works on the local neighbor graph only, it is fast and automatically adapts to the sampling resolution. This makes the approach ideal as a preprocessing step in mesh generation.

Download Full Paper (Postscript Format)