“Exploring Quadrangulations” by Peng, Barton, Jiang and Wonka

  • ©Chi-Han Peng, Michael Barton, Caigui Jiang, and Peter Wonka

Conference:


Type:


Title:

    Exploring Quadrangulations

Session/Category Title: Fields on Surfaces

Presenter(s)/Author(s):


Moderator(s):


Abstract:


    We present a framework for exploring topologically unique quadrangulations of an input shape. First, the input shape is segmented into surface patches. Second, different topologies are enumerated and explored in each patch. This is realized by an efficient subdivision-based quadrangulation algorithm that can exhaustively enumerate all mesh topologies within a patch. To help users navigate the potentially huge collection of variations, we propose tools to preview and arrange the results. Furthermore, the requirement that all patches need to be jointly quadrangulatable is formulated as a linear integer program. Finally, we apply the framework to shape-space exploration, remeshing, and design to underline the importance of topology exploration.

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. M. Berkelaar, K. Eikland, and P. Notebaert. 2004. Ipsolve: Open source (mixed-integer) linear programming system. http://lpsolve.sourceforge.net/5.5/
    3. M. Bessmeltsev, C. Wang, A. Sheffer, and K. Singh. 2012. Design-driven quadrangulation of closed 3d curves. ACM Trans. Graph. 31, 5.
    4. T. D. Blacker And M. B. Stephenson. 1991. Paving: A new approach to automated quadrilateral mesh generation. Int. J. Numer. Methods Engin. 32, 4, 811–847.
    5. D. Bommes, B. Levy, N. Pietroni, E. Puppo, M. Tarini, and D. Zorin. 2012. State of the art in quad meshing. In EuroGraphics STARS.
    6. D. Bommes, H. Zimmer, and L. Kobbelt. 2009. Mixed-integer quadrangulation. ACM Trans. Graph. 28, 3, 77.
    7. M. Botsch, L. Kobbelt, M. Pauly, P. Alliez, and B. Levy. 2010. Polygon Mesh Processing. A. K. Peters, Natick, MA.
    8. D. Cohen-Steiner, P. Alliez, and M. Desbrun. 2004. Variational shape approximation. In Proceedings of the Conference on Computer Graphics and Interactive Techniques (SIGGRAPH’04). ACM Press, New York, 905–914.
    9. J. Daniels, C. T. Silva, J. Shepherd, and E. Cohen. 2008. Quadrilateral mesh simplification. ACM Trans. Graph. 27, 5, 148:1–148:9.
    10. S. Dong, P.-T. Bremer, M. Garland, V. Pascucci, and J. C. Hart. 2006. Spectral surface quadrangulation. ACM Trans. Graph. 25, 3, 1057–1066. 
    11. S. Dong, S. Kircher, and M. Garland. 2005. Harmonic functions for quadrilateral remeshing of arbitrary manifolds. Comput.-Aid. Geom. Des. 22, 392–423.
    12. F. Kalberer, M. Nieser, and K. Polthier. 2007. Quadcover — Surface parameterization using branched coverings. Comput. Graph. Forum 26, 3, 375–384.
    13. B. Levy, S. Petitjean, N. Ray, and J. Maillot. 2002. Least squares conformal maps for automatic texture atlas generation. ACM Trans. Graph. 21, 3, 362–371.
    14. Y. Liu, H. Pottmann, J. Wallner, Y.-L. Yang, and W. Wang. 2006. Geometric modeling with conical meshes and developable surfaces. ACM Trans. Graph. 25, 3, 681–689.
    15. M. Marinov and L. Kobbelt. 2004. Direct anisotropic quad-dominant remeshing. In Proceedings of the 12th Pacific Conference on Computer Graphics and Applications (PG’04). 207–216.
    16. M. Marinov and L. Kobbelt. 2006. A robust two-step procedure for quad-dominant remeshing. Comput. Graph. Forum 25, 3, 537–546.
    17. S. Maza, F. Noel, and J. Leon. 1999. Generation of quadrilateral meshes on free-form surfaces. Comput. Struct. 71.
    18. A. S. M. Nasri and Z. Yasseen. 2009. Filling n-sided regions by quad meshes for subdivision surfaces. Comput. Graph. Forum 28, 1644–1658.
    19. J. Palacios and E. Zhang. 2007. Rotational symmetry field design on surfaces. ACM Trans. Graph. 26, 3, 55.
    20. C. Park, J.-S. Noh, I.-S. Jang, and J. M. Kang. 2007. A new automated scheme of quadrilateral mesh generation for randomly distributed line constraints. Comput.-Aid. Des. 39, 4, 258–267.
    21. C.-H. Peng, E. Zhang, Y. Kobayashi, and P. Wonka. 2011. Connectivity editing for quadrilateral meshes. ACM Trans. Graph. 30, 6, 141.
    22. N. Ray, W. C. Li, B. Levy, A. Sheffer, and P. Alliez. 2006. Periodic global parameterization. ACM Trans. Graph. 25, 4, 1460–1485.
    23. N. Ray, B. Vallet, L. Alsonso, and B. Levy. 2009. Geometry aware direction field design. ACM Trans. Graph. 29, 1, 1:1–1:11.
    24. 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.
    25. S. Schaefer, J. Warren, and D. Zorin. 2004. Lofting curve networks using subdivision surfaces. In Proceedings of the 2nd EuroGraphics Symposium on Geometry Processing (SGP’04). 103–114.
    26. Y. Tong, P. Alliez, D. Cohen-Steiner, and M. Desbrun. 2006. Designing quadrangulations with discrete harmonic forms. In Proceedings of the 4th EuroGraphics Symposium on Geometry Processing (SGP’06). 201–210.
    27. D. White and P. Kinney. 1997. Redesign of the paving algorithm: Robustness enhancements through element by element meshing. In Proceedings of the 6th International Meshing Round Table. 323–335.
    28. Y.-L. Yang, Y.-J. Yang, H. Pottmann, and N. J. Mitra. 2011. Shape space exploration of constrained meshes. ACM Trans. Graph. 30, 6, 124:1–124:12.
    29. E. Zhang, K. Mischaikow, and G. Turk. 2006. Vector field design on surfaces. ACM Trans. Graph. 25, 1294–1326.
    30. M. Zhang, J. Huang, X. Liu, And H. Bao. 2010. A wave-based anisotropic quadrangulation method. ACM Trans. Graph. 29, 4, 118:1–118:8.

ACM Digital Library Publication:


Overview Page: