Skip to Main content Skip to Navigation
New interface
Journal articles

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

Nicolas Ray 1 Dmitry Sokolov 1 
1 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 metadata
Contributor : Nicolas Ray Connect in order to contact the contributor
Submitted on : Tuesday, December 9, 2014 - 3:32:30 PM
Last modification on : Thursday, February 10, 2022 - 12:28:12 PM

Links full text




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



Record views