Maintaining Deforming Surface Meshes

PhD Thesis Proposal Defence


Title: "Maintaining Deforming Surface Meshes"

by

Mr. Jiongxin Jin


Abstract:

We study edge flips in a surface mesh and the maintenance of a deforming 
surface mesh. In the first part of the proposal, we show that if the vertices 
are dense with respect to the local feature size and the triangles have angles 
at least a constant, we can flip edges in linear time such that all triangles 
have almost empty diametric balls.  For a planar triangulation with a constant 
angle lower bound, we can flip it to the Delaunay triangulation in linear time. 
It is known that a general planar triangulation needs Omega(n2) edge flips to 
become Delaunay.

In the second part of the proposal, we design an efficient algorithm using the 
edge flip results 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.  In comparison, 
reconstructing the surface from scratch without a bounded aspect ratio 
guarantee already takes O(n log n) time currently.  Our surface mesh 
maintenance algorithm also gives a good performance in experiments.

In some applications, a surface may undergo complicated structure changes. In 
the future, we plan to accommodate topological changes by extending our work, 
that is, to maintain a surface which is topologically correct before and after 
the topological changes.


Date:  			Monday, 31 January 2011

Time:           	2:00pm - 4:00pm

Venue:          	Room 3501
 			lifts 25/26

Committee Members:      Prof. Siu-Wing Cheng (Supervisor)
 			Prof. Mordecai Golin (Chairperson)
 			Dr. Sunil Arya
 			Dr. Ke Yi


**** ALL are Welcome ****