Publications by year

2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  

Most documents on this website are protected by copyright. By clicking on a PDF icon, you confirm that you or your institution has the right to do so. Note that the definitive versions of all EG papers (Eurographics,...) can be downloaded from ACM papers (Siggraph, ...) can be downloaded from


“Robust Polylines Tracing for N-Symmetry Direction Field on Triangulated Surfaces”
Nicolas Ray and Dmitry Sokolov
ACM Transactions on Graphics, 2014

Abstract: We are proposing an algorithm for tracing polylines that are oriented by a direction field defined on a triangle mesh. The challenge is to ensure that two such polylines cannot cross or merge. This property is fundamental for mesh segmentation and is impossible to enforce with existing algorithms. The core of our contribution is to determine how polylines cross each tri- angle. Our solution is inspired by EdgeMaps where each triangle boundary is decomposed into inflow and outflow intervals such that each inflow inter- val is mapped onto an outflow interval. To cross a triangle, we find the inflow interval that contains the entry point, and link it to the corresponding out- flow interval, with the same barycentric coordinate. To ensure that polylines cannot merge or cross, we introduce a new direction field representation, we resolve the inflow/outflow interval pairing with a guaranteed combinatorial algorithm, and propagate the barycentric positions with arbitrary precision number representation. Using these techniques, two streamlines crossing the same triangle cannot merge or cross, but only locally overlap when all streamline extremities are located on the same edge. Cross-free and merge-free polylines can be traced on the mesh by it- eratively crossing triangles. Vector field singularities and polyline/vertex crossing are characterized and consistently handled.

BibTex reference

   TITLE      = "Robust Polylines Tracing for N-Symmetry Direction Field on Triangulat
                   ed Surfaces",
   AUTHOR     = "Nicolas Ray and Dmitry Sokolov",
   JOURNAL    = "ACM Transactions on Graphics",
   YEAR       = "2014",