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.
Type de document :
Article dans une revue
ACM Transactions on Graphics, Association for Computing Machinery, 2014, pp.11
Liste complète des métadonnées

https://hal.inria.fr/hal-01092823
Contributeur : Nicolas Ray <>
Soumis le : mardi 9 décembre 2014 - 15:32:30
Dernière modification le : jeudi 11 janvier 2018 - 06:25:23

Identifiants

  • HAL Id : hal-01092823, version 1

Collections

Citation

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〉

Partager

Métriques

Consultations de la notice

143