טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentFarchi Nahum
SubjectInteger-Only Cross Field Computation
DepartmentDepartment of Computer Science
Supervisor Professor Mirela Ben-Chen


Abstract

Directional fields are important objects in geometry processing with applications

ranging from texture synthesis to non-photorealistic rendering, quadrangular

remeshing, and architectural design. In this thesis, we focus our attention on cross

fields - a direction field in which four unit vectors with π/2 symmetry are defined at

each point on the surface.


Computing smooth cross fields on triangle meshes is challenging, as the problem

formulation inherently depends on integer variables to encode the invariance of the

crosses to rotations by integer multiples of π/2. Furthermore, finding the optimal

placement for the cone singularities is essentially a hard combinatorial problem.


We propose a new iterative algorithm for computing smooth cross fields on triangle

meshes that is simple, easily parallelizable on the GPU, and finds solutions with lower

energy and fewer cone singularities than state-of-the-art methods. Furthermore, the

output cross fields are such that there is no relocation of a single ±π/2 singularity that

will reduce the energy.


Our approach is based on a formal equivalence, which we prove, between two

formulations of the optimization problem. This equivalence allows us to eliminate the

real variables and design an efficient grid search algorithm for the cone singularities.

We make use of a recent graph-theoretical approximation of the resistance distance

matrix of the triangle mesh to speed up the computation and enable a trade-off

between the computation time and the smoothness of the output.