UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Optimal mapping with topology change for animation and geometry problems Zhu, Yufeng


This thesis investigates several aspects of the optimal mapping problem, finding a bijective function between two shapes which minimizes some metric, and its many applications in computer graphics such as finding planar embeddings of curved surface meshes, image warping, mesh deformation, elastoplastic simulation, and more. We highlight in particular problems where differences in topology between the shapes—which necessitate discontinuities in the mapping—play a crucial role, e.g. due to animation decisions or physical fracture. Our first project presents an approach to extend discrete variational shape interpolation to create keyframe animation involving extreme deformation, topology change and dynamics. To construct correspondence between keyframe shapes as well as satisfying feature matching constraints, we introduce a consistent multimesh structure that is able to resolve topological in-equivalence between shapes and a Comesh Optimization algorithm that optimizes our multimesh for both intra and inter-mesh quality. To further speed up the total solving time, we then develop three new improvements to the state of the art nonlinear optimization techniques that are frequently used in this field, including a barrier-aware line-search filter that cures blocked descent steps due to element barrier terms; an energy proxy model that adaptively blends the Sobolev gradient and L-BFGS descent to gain the advantages of both; and a characteristic gradient norm providing a robust and largely mesh- and energy independent convergence criterion. Finally, we demonstrate another related interesting graphics application, brittle fracture simulation. In particular, we investigate whether we can sidestep the volumetric optimal mapping problem for solving elastic deformation and instead use a boundary element discretization which only requires a surface mesh. We will show how the computational cost of such problems can be alleviated using a boundary integral formulation and kernel-independent Fast Multipole Method. By combining with an explicit surface tracking framework, we further avoid the expensive volumetric mesh construction and maintenance during fracture propagation and shape topology change.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International