ICS Theory Group

ICS 269, Fall 1999: Theory Seminar


10 December 1999:
"Surface Reconstruction Algorithms for Mesh Generation"
Speaker: Mac Casale, ICS, UC Irvine

Abstract: This talk explores the use of surface reconstruction algorithms as an aid to the mesh generation of less than ideal CAD models, ones that we call semi-valid. We begin with a brief description of the problem context, and define what we mean by semi-valid. The majority of the talk will focus on a paper by Bernardini, et. al, for the automatic reconstruction of CAD models from unordered point sets using alpha-shapes. We will define the alpha-shape and present some of its properties, such as how it is a generalization of the convex hull of a set of points. We will also present conditions on the sampling rate that, if achieved, guarantee that the reconstructed solid is homeomorphic to the original and is within a specified accuracy. This is followed by the reconstruction algorithm, which proceeds as follows: 1) Produce an initial triangulation of the points using alpha-shapes, 2) Simplify the mesh, making it suitable for p-element analysis, 3) Fit smooth surfaces to the mesh. We conclude by showing how additional information is available in the context of semi-valid CAD models and present several possible avenues for additional research.