Hierarchical Gradient Domain Vector Field Processing

Abstract

Vector fields are a fundamental mathematical construct for describing flow-field-related problems in science and engineering. To solve these types of problems effectively on a discrete surface, various vector field representations are proposed using finite dimensional bases, a discrete connection, and an operator approach. Furthermore, for computational efficiency, quadratic Dirichlet energy is preferred to measure the smoothness of the vector field in the gradient domain. However, while quadratic energy gives a simple linear system, it does not support real-time vector field processing on a high-resolution mesh without extensive GPU parallelization. To this end, this dissertation describes an efficient hierarchical solver for vector field processing. Our method extends the successful multigrid design for interactive signal processing on meshes using an induced vector field prolongation combing it with novel speedup techniques. We formulate a general way for extending scalar field prolongation to vector fields. Focusing on triangle meshes, our convergence study finds that a standard multigrid does not achieve fast convergence due to the poorly-conditioned system matrix. We observe a similar performance in standard single-level iterative methods such as the Jacobi, Gauss-Seidel, and conjugate gradient methods. Therefore, we compare three speedup techniques -- successive over-relaxation, smoothed prolongation, and Krylov subspace update, and incorporate them into our solver. Finally, we demonstrate our solver on useful applications such as logarithmic map computation and discuss the applications to other hierarchies such as texture grids, followed by the conclusion and future work.