# 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.