“ℓ1-Based Construction of Polycube Maps from Complex Shapes” by Huang, Jiang, Shi, Tong, Bao, et al. …

  • ©Jin Huang, Tengfei Jiang, Zeyun Shi, Yiying Tong, Hujun Bao, and Mathieu Desbrun

Conference:


Type(s):


Title:

    ℓ1-Based Construction of Polycube Maps from Complex Shapes

Session/Category Title:   Surfaces, Shapes, and Maps

Presenter(s)/Author(s):


Moderator(s):


Abstract:


    Polycube maps of triangle meshes have proved useful in a wide range of applications, including texture mapping and hexahedral mesh generation. However, constructing either fully automatically or with limited user control a low-distortion polycube from a detailed surface remains challenging in practice. We propose a variational method for deforming an input triangle mesh into a polycube shape through minimization of the ℓ1-norm of the mesh normals, regularized via an as-rigid-as-possible volumetric distortion energy. Unlike previous work, our approach makes no assumption on the orientation, or on the presence of features in the input model. User-guided control over the resulting polycube map is also offered to increase design flexibility. We demonstrate the robustness, efficiency, and controllability of our method on a variety of examples, and explore applications in hexahedral remeshing and quadrangulation.

References:


    1. M. Alexa, D. Cohen-Or, and D. Levin. 2000. As-rigid-as-possible shape interpolation. In Proceedings of the Annual ACM SIGGRAPH Conference on Computer Graphics and Interactive Techniques. 157–164.
    2. K. D. Andersen. 1996. An efficient newton barrier method for minimizing a sum of euclidean norms. SIAM J. Optim. 6, 1, 74–95.
    3. N. Aspert, D. Santa-Cruz, and T. Ebrahimi. 2002. Mesh: Measuring errors between surfaces using the hausdorff distance. In Proceedings of the IEEE International Conference and Multimedia Expo (ICME’02). Vol. 1. 705–708.
    4. H. Avron, A. Sharf, C. Greif, and D. Cohen-Or. 2010. ℓ1-sparse reconstruction of sharp point set surfaces. ACM Trans. Graph. 29, 5, 135.
    5. M. Benzi, G. Golub, and J. Liesen. 2005. Numerical solution of saddle point problems. Acta Numerica 14, 1, 1–137.
    6. M. Botsch, M. Pauly, M. Gross, and I. Kobbelt. 2006. Primo: Coupled prisms for intuitive surface modeling. In Proceedings of the Symposium on Geometry Processing. Vol. 256. 11–20.
    7. M. Campen, D. Bommes, and I. Kobbelt. 2012. Dual loops meshing: Quality quad layouts on manifolds. ACM Trans. Graph. 31, 4, 110.
    8. Y. Chen, T. A. Davis, W. W. Hager, and S. Rajamanickam. 2008. Algorithm 887: Cholmod, supernodal sqare cholesky factorization and update/downdate. ACM Trans. Math. Softw. 35, 3, 22:1–22:14.
    9. R. El-Attar, M. Vidyasagar, and S. Dutta. 1979. An algorithm for ℓ1-norm minimization with application to nonlinear ℓ1-approximation. SIAM J. Numer. Anal. 16, 1, 70–86.
    10. I. Garcia, J. Xia, Y. He, S.-Q. Xin, and G. Patow. 2013. Interactive applications for sketch-based editable polycube map. IEEE Trans. Vis. Comput. Graph. 19, 7, 1158–1171.
    11. N. I. M. Gould, D. Orban, and P. L. Toint. 2003. An interior-point ℓ1-penalty method for nonlinear optimization. Tech. rep. RAL-TR-2003-022, Rutherford Appleton Laboratory.
    12. J. Gregson, A. Sheffer, and E. Zhang. 2011. All-hex mesh generation via volumetric polycube deformation. Comput. Graph. Forum 30, 5, 1407–1416.
    13. Y. He, H. Wang, C.-W. Fu, and H. Qin. 2009. A divide-and-conquer approach for automatic polycube map construction. Comput. Graph. 53, 369–380.
    14. J. Huang, Y. Tong, H. Wei, and H. Bao. 2011. Boundary aligned smooth 3d cross-frame field. ACM Trans. Graph. 30, 6, 143.
    15. P. J. Huber. 1981. Robust Statistics. John Wiley & Sons.
    16. G. Irving, J. Teran, and R. Fedkiw. 2004. Invertible finite elements for robust simulation of large deformation. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation. 131–140.
    17. F. Knoppel, K. Crane, U. Pinkall, and P. Schroder. 2013. Globally optimal direction fields. ACM Trans. Graph. 32, 4, 59:1–59:10.
    18. Y. Li, Y. Liu, W. Xu, W. Wang, and B. Guo. 2012. All-hex meshing using singularity-restricted field. ACM Trans. Graph. 31, 6, 177:1–177:11.
    19. J. Lin, X. Jin, Z. Fan, and C. C. L. Wang. 2008. Automatic polycube-maps. In Proceedings of the 5th International Conference on Advances in Geometric Modeling and Processing (GMP’08). Springer, 3–16.
    20. L. Luksan, C. Matonoha, and J. Vlcek. 2007. Trust region interior-point method for large sparse ℓ1 optimization. Optim. Methods Softw. 22, 5, 737–753.
    21. A. Myles, N. Pietroni, D. Kovacs, and D. Zorin. 2010. Feature-aligned t-meshes. ACM Trans. Graph. 29, 4, 117.
    22. M. C. Pinar and W. M. Hartmann. 2006. Huber approximation for the non-linear ℓ1 problem. Euro. J. Oper. Res. 169, 3, 1096–1107.
    23. SANDIA NATIONAL LABORATORY. 2010. Mesh verification with verdict. https://cubit.sandia.gov/public/verdict.html.
    24. K. Schittkowski. 2008. NLPL1: A fortran implementation of an sqp algorithm for minimizing sums of absolute function values, user’s guide. www.ai7.uni-bayreuth.de/NLPL1.pdf.
    25. J. Schoberl. 1997. Netgen: An advancing front 2d/3d-mesh generator based on abstract rules. Comput. Vis. Sci. 1, 1, 41–52.
    26. M. Tarini, K. Hormann, P. Cignoni, and C. Montani. 2004. Polycube-maps. ACM Trans. Graph. 23, 3, 853–860.
    27. M. Tarini, E. Puppo, D. Panozzo, N. Pietroni, and P. Cignoni. 2011. Simple quad domains for field aligned mesh parameterization. ACM Trans. Graph. 30, 6, 142.
    28. H. Wang, M. Jin, Y. He, X. Gu, and H. Qin. 2008. User-controllable polycube map for manifold spline construction. In Proceedings of the ACM Symposium on Solid and Physical Modeling. 397–404.
    29. C. Yao and T. Lee. 2008. Adaptive geometry image. IEEE Trans. Vis. Comput. Graph. 14, 4, 948–960.

ACM Digital Library Publication:


Overview Page: