M.Sc Thesis

M.Sc StudentReani Yair
SubjectFunctional Tracing of Discrete Vector Fields
DepartmentDepartment of Computer Science
Supervisor ASSOCIATE PROF. Mirela Ben-Chen
Full Thesis textFull thesis text - English Version


We propose a method for approximating the flowlines of a discrete tangent vector field on a triangle mesh. Our method makes use of the recently proposed discrete representation of a vector field as a derivation operator. This representation allows us to state the problem of flowlines computation as the advection of the Euclidean coordinate functions by the vector field. By representing the vector field as a linear derivation operator, and discretizing both the vector field operator and the coordinate functions using Lagrange linear elements (or "hat functions"), the spatial discretization of the flowline equations leads to three linear systems of ordinary differential equations (ODEs), one system for each Euclidean coordinate function. These linear ODEs have a closed form solution as a function of time, thus the system can be solved without explicit time discretization, using an exponential integrator.

Our approach requires only the construction of the derivative operator that represents the vector field and multiplying the exponential of a sparse matrix by a vector, which can both be efficiently computed. For a given equally spaced time vector, we compute the flowlines from all the vertices of the mesh simultaneously. With this global definition of the problem, our method is characterized by making use of mostly global solutions, as opposed to algorithms that analyse local geometric details through the explicit generation of curves and intersecting line segments. We compare our approach to analytical solutions in cases where these are known, and to an iterative simple tracing algorithm. In addition, we examine our solution from other aspects, such as invariance to global transformations, the distance of the flowlines from the mesh, and other local characteristics. Finally, we use our method for the simple, robust and efficient visualization of discrete tangent vector fields on triangle meshes.