“Robust Polylines Tracing for N-symmetry Direction Field on Triangulated Surfaces” by Ray and Sokolov

  • ©Nicolas Ray and Dmitry Sokolov

Conference:


Type:


Title:

    Robust Polylines Tracing for N-symmetry Direction Field on Triangulated Surfaces

Session/Category Title: Fields on Surfaces

Presenter(s)/Author(s):


Moderator(s):


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 triangle. Our solution is inspired by EdgeMaps where each triangle boundary is decomposed into inflow and outflow intervals such that each inflow interval 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 outflow 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 iteratively crossing triangles. Vector field singularities and polyline/vertex crossing are characterized and consistently handled.

References:


    1. P. Alliez, D. Cohen-Steiner, O. Devillers, B. Levy, and M. Desbrun. 2003. Anisotropic polygonal remeshing. ACM Trans. Graph. 22, 3, 485–493.
    2. H. Bhatia, S. Jadhav, P.-T. Bremer, G. Chen, J. A. Levine, L. G. Nonato, and V. Pascucci. 2011. Edge maps: Representing flow with bounded error. In Proceedings of the IEEE Pacific Visualization Symposium (PacificVis’11). 75–82.
    3. D. Bommes, H. Zimmer, and L. Kobbelt. 2009. Mixed-integer quadrangulation. ACM Trans. Graph. 28, 3, 77:1–77:10.
    4. E. Colin de Verdiere and F. Lazarus. 2005. Optimal system of loops on an orientable surface. Discr. Comput. Geom. 33, 3, 507–534.
    5. S. Dong, P.-T. Bremer, M. Garland, V. Pascucci, and J. C. Hart. 2006. Spectral surface quadrangulation. ACM Trans. Graph. 25, 3, 1057–1066.
    6. D. Eberly. 1998. Triangulation by ear clipping. http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf.
    7. M. Fisher, P. Schroder, M. Desbrun, and H. Hoppe. 2007. Design of tangent vector fields. ACM Trans. Graph. 26, 56.
    8. F. Kalberer, M. Nieser, and K. Polthier. 2007. Quadcover — Surface parameterization using branched coverings. http://www.polthier.info/articles/quadCover/KNP07-QuadCover.pdf.
    9. N. Kowalski, F. Ledoux, and P. Frey. 2013. A pde based approach to multidomain partitioning and quadrilateral meshing. In Proceedings of the 21st International Meshing Roundtable. Springer, 137–154.
    10. W. C. Li, B. Levy, and J.-C. Paul. 2005. Mesh editing with an embedded network of curves. In Proceedings of the IEEE International Conference on Shape Modeling and Applications. 62–71.
    11. D. Martinez, L. Velho, and P. C. Carvalho. 2005. Computing geodesics on triangular meshes. Comput. Graph. 29, 5, 667–675.
    12. M. Mrozek. 1995. Conley index theory. In Handbook of Dynamical Systems II, Elsevier/North-Holland, 393–460.
    13. A. Myles, N. Pietroni, D. Kovacs, and D. Zorin. 2010. Feature-aligned t-meshes. In Proceedings of the 37th International Conference and Exhibition on Computer Graphics and Interactive Techniques (SIGGRAPH’10). 117:1–117:11.
    14. J. Palacios and E. Zhang. 2007. Rotational symmetry field design on surfaces. ACM Trans. Graph. 26, 3, 55.
    15. K. Polthier and M. Schmies. 2006. Straightest geodesics on polyhedral surfaces. In Proceedings of the 33rd International Conference and Exhibition on Computer Graphics and Interactive Techniques (SIGGRAPHCourses’10). ACM Press, New York, 30–38.
    16. N. Ray, W. C. Li, B. Levy, A. Sheffer, and P. Alliez. 2006. Periodic global parameterization. ACM Trans. Graph. 25, 4, 1460–1485.
    17. N. Ray, B. Vallet, L. Alonso, and B. Levy. 2009. Geometry aware direction field processing. ACM Trans. Graph. 29, 1, 1:1–1:11.
    18. N. Ray, B. Vallet, W. C. Li, and B. Levy. 2008. N-symmetry direction field design. ACM Trans. Graph. 27, 2, 10:1–10:13.
    19. C. Rossl and H. Theisel. 2012. Streamline embedding for 3d vector field exploration. IEEE Trans. Vis. Comput. Graph. 18, 3, 407–420.
    20. B. Spencer, R. S. Laramee, G. Chen, and E. Zhang. 2009. Evenly spaced streamlines for surfaces: An image-based approach. Comput. Graph. Forum 28, 6, 1618–1631.
    21. V. Surazhsky, T. Surazhsky, D. Kirsanov, S. J. Gortler, and H. Hoppe. 2005. Fast exact and approximate geodesics on meshes. ACM Trans. Graph. 24, 3, 553–560.
    22. A. Szymczak and E. Zhang. 2012. Robust morse decompositions of piecewise constant vector fields. IEEE Trans. Vis. Comput. Graph. 18, 938–951.
    23. K. Wang, Weiwei, Y. Tong, M. Desbrun, and P. Schroder. 2006. Edge subdivision schemes and the construction of smooth vector fields. ACM Trans. Graph. 25, 3, 1041–1048.
    24. E. Zhang, K. Mischaikow, and G. Turk. 2006. Vector field design on surfaces. ACM Trans. Graph. 25, 4, 1294–1326.

ACM Digital Library Publication:


Overview Page: