Skip to Main content Skip to Navigation
Journal articles

Robust polylines tracing for N-symmetry direction field on triangulated surfaces

Nicolas Ray 1 Dmitry Sokolov 2
1 ISA - Models, algorithms and geometry for computer graphics and vision
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
2 ALICE - Geometry and Lighting
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Abstract : We are proposing an algorithm for tracing polylines that are oriented bya direction field defined on a triangle mesh. The challenge is to ensure thattwo such polylines cannot cross or merge. This property is fundamental formesh segmentation and is impossible to enforce with existing algorithms.The core of our contribution is to determine how polylines cross eachtriangle. Our solution is inspired by EdgeMaps where each triangle boundaryis decomposed into inflow and outflow intervals such that each inflowinterval is mapped onto an outflow interval. To cross a triangle, we find theinflow interval that contains the entry point, and link it to the correspondingoutflow interval, with the same barycentric coordinate. To ensure that polylinescannot merge or cross, we introduce a new direction field representation,we resolve the inflow/outflow interval pairing with a guaranteed combinatorialalgorithm, and propagate the barycentric positions with arbitraryprecision number representation. Using these techniques, two streamlinescrossing the same triangle cannot merge or cross, but only locally overlapwhen all streamlines extremities are located on the same edge.Cross-free and merge-free polylines can be traced on the mesh by iterativelycrossing triangles. Vector field singularities and polyline/vertexcrossing are characterized and consistently handled.
Document type :
Journal articles
Complete list of metadatas
Contributor : Nicolas Ray <>
Submitted on : Tuesday, December 9, 2014 - 3:32:30 PM
Last modification on : Wednesday, September 18, 2019 - 4:36:03 PM


  • HAL Id : hal-01092823, version 1



Nicolas Ray, Dmitry Sokolov. Robust polylines tracing for N-symmetry direction field on triangulated surfaces. ACM Transactions on Graphics, Association for Computing Machinery, 2014, pp.11. ⟨hal-01092823⟩



Record views