Surface Reconstruction and Deformation

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering


PhD Thesis Defence


Title: "Surface Reconstruction and Deformation"

By

Mr. Jiongxin Jin


Abstract

This thesis studies the problems of reconstructing surfaces and 
maintaining a deforming surface mesh. We first present a practical 
algorithm for surface reconstruction from a point cloud, which runs in O(n 
log n) time, where n is the number of sample points. This is optimal in 
the pointer machine model.  The only existing O(n log n)-time algorithm 
due to Funke and Ramos is far from practical as it involves several 
sophisticated data structures, including the well-separated pair 
decomposition, approximate directional nearest neighbor searching, and 
approximate range searching. Our algorithm is based on a variant of the 
standard octree, and is much simpler.

We investigate the complexity of edge flips in a surface mesh. Given a 
surface mesh whose vertices are dense with respect to the local feature 
size and whose triangles have angles at least a constant, we prove that 
one can flip edges in linear time such that all triangles have almost 
empty diametric balls. As a corollary, a planar triangulation with a 
constant angle lower bound can be converted to the Delaunay triangulation 
in linear time. It is known that a general planar triangulation needs 
Ω(n2) edge flips to become Delaunay.

Using the edge flip results, we design an efficient algorithm to update a 
deforming surface mesh, which is specified only by a dense sample of n 
points that move with the surface. Although edge flips alone cannot 
improve the angles in the mesh substantially after they worsen, they can 
be used in conjunction with vertex insertions and deletions to restore the 
mesh quality. Under a reasonable motion model, we can enforce bounded 
aspect ratios and a small approximation error throughout the entire 
deformation.  The update takes O(n) time at each time step.

The reconstruction and maintenance algorithms have been implemented and 
they give good performance in our experiments.


Date:			Wednesday, 6 June 2012

Time:			2:00pm – 4:00pm

Venue:			Room 3501
 			Lifts 25/26

Chairman:		Prof. Xijun Hu (CBME)

Committee Members:	Prof. Siu-Wing Cheng (Supervisor)
 			Prof. Sunil Arya
 			Prof. Mordecai Golin
 			Prof. Ajay Joneja (IELM)
                         Prof. Jian Sun (Tsinghua Univ.)


**** ALL are Welcome ****