Technical Report MSC-2018-15

Title: Integer-Only Cross Field Computation
Authors: Nahum Farchi
Supervisors: Mirela Ben-Chen
PDFCurrently accessibly only within the Technion network
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 $\pi / 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 \emph{integer} variables to encode the invariance of the crosses to rotations by integer multiples of $\pi / 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 $\pm \pi / 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 leverage a recent graph-theoretical approximation of the \emph{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.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2018
To the main CS technical reports page

Computer science department, Technion