“Construction of Manifolds via Compatible Sparse Representations” by Wang, Liu, Yang, Wang, Shan, et al. …

  • ©Ruimin Wang, Ligang Liu, Zhouwang Yang, Kang Wang, Wen Shan, Jiansong Deng, and Falai Chen




    Construction of Manifolds via Compatible Sparse Representations





    Manifold is an important technique to model geometric objects with arbitrary topology. In this article, we propose a novel approach for constructing manifolds from discrete meshes based on sparse optimization. The local geometry for each chart is sparsely represented by a set of redundant atom functions, which have the flexibility to represent various geometries with varying smoothness. A global optimization is then proposed to guarantee compatible sparse representations in the overlapping regions of different charts. Our method can construct manifolds of varying smoothness including sharp features (creases, darts, or cusps). As an application, we can easily construct a skinning manifold surface from a given curve network. Examples show that our approach has much flexibility to generate manifold surfaces with good quality.


    1. Fatemeh Abbasinejad, Pushkar Joshi, and Nina Amenta. 2011. Surface patches from unorganized space curves. Computer Graphics Forum 30, 5, 1379–1387.
    2. Seok-Hyung Bae, Ravin Balakrishnan, and Karan Singh. 2008. ILove-Sketch: As-natural-as-possible sketching system for creating 3D curve models. In Proceedings of the 21st Annual ACM Symposium on User Interface Software and Technology. ACM, New York, NY, 151–160. 
    3. Seok-Hyung Bae, Ravin Balakrishnan, and Karan Singh. 2009. EverybodyLovesSketch: 3D sketching for a broader audience. In Proceedings of the 22nd Annual ACM Symposium on User Interface Software and Technology. ACM, New York, NY, 59–68. 
    4. Mikhail Bessmeltsev, Caoyu Wang, Alla Sheffer, and Karan Singh. 2012. Design-driven quadrangulation of closed 3D curves. ACM Transactions on Graphics 31, 6, 178. 
    5. Alfred M. Bruckstein, David L. Donoho, and Michael Elad. 2009. From sparse solutions of systems of equations to sparse modeling of signals and images. SIAM Review 51, 1, 34–81. 
    6. Steven A. Coons. 1967. Surfaces for Computer-Aided Design of Space Forms. Technical Report. DTIC Document. 
    7. Giovanni Della Vecchia and Bert Jüttler. 2009. Piecewise rational manifold surfaces with sharp features. In Mathematics of Surfaces XIII. Springer, 90–105. 
    8. Giovanni Della Vecchia, Bert Jüttler, and Myung-Soo Kim. 2008. A construction of rational manifold surfaces of arbitrary topology and smoothness from triangular meshes. Computer Aided Geometric Design 25, 9, 801–815. 
    9. Tony DeRose, Michael Kass, and Tien Truong. 1998. Subdivision surfaces in character animation. In Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH’98). ACM, New York, NY, 85–94. 
    10. David L. Donoho. 1995. De-noising by soft-thresholding. IEEE Transactions on Information Theory 41, 3, 613–627. 
    11. Michael Elad. 2010. Sparse and Redundant Representations. Springer. 
    12. Michael Elad and Michal Aharon. 2006. Image denoising via sparse and redundant representations over learned dictionaries. IEEE Transactions on Image Processing 15, 12, 3736–3745. 
    13. Jean Gallier, Dianna Xu, and Marcelo Siqueira. 2012. Parametric pseudo-manifolds. Differential Geometry and Its Applications 30, 6, 702–736.
    14. Cindy Grimm, Tao Ju, Ly Phan, and John Hughes. 2009. Adaptive smooth surface fitting with manifolds. Visual Computer 25, 5–7, 589–597. 
    15. Cindy Grimm and Denis Zorin. 2006. Surface modeling and parameterization with manifolds. In ACM SIGGRAPH 2006 Courses. ACM, New York, NY, 1–81. 
    16. Cindy M. Grimm and John F. Hughes. 1995. Modeling surfaces of arbitrary topology using manifolds. In Proceedings of the 22nd Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH’95). ACM, New York, NY, 359–368. 
    17. Xianfeng Gu, Ying He, and Hong Qin. 2006. Manifold splines. Graphical Models 68, 3, 237–254. 
    18. Ying He, Kexiang Wang, Hongyu Wang, Xianfeng Gu, and Hong Qin. 2006. Manifold t-spline. In Geometric Modeling and Processing—GMP 2006. Lecture Notes in Computer Science, Vol. 4077. Springer, 409–422. 
    19. Wan Chiu Li, Nicolas Ray, and Bruno Lévy. 2006. Automatic and interactive mesh to t-spline conversion. In Proceedings of the 4th Eurographics Symposium on Geometry Processing (SGP’06). 
    20. P. Malraison. 2000. N-sided Surfaces: A Survey. Technical Report. Defense Technical Information Center.
    21. A. Nasri, M. Sabin, and Z. Yasseen. 2009. Filling n-sided regions by quad meshes for subdivision surfaces. Computer Graphics Forum 28, 6, 1644–1658.
    22. J. Cotrina Navau and N. Pla Garcia. 2000. Modeling surfaces from meshes of arbitrary topology. Computer Aided Geometric Design 17, 7, 643–671. 
    23. Andrew Nealen, Takeo Igarashi, Olga Sorkine, and Marc Alexa. 2007. FiberMesh: Designing freeform surfaces with 3D curves. ACM Transactions on Graphics 26, 3, 41. 
    24. Hao Pan, Yang Liu, Alla Sheffer, Nicholas Vining, Chang-Jian Li, and Wenping Wang. 2015. Flow aligned surfacing of curve networks. ACM Transactions on Graphics 34, 4, 127. 
    25. Yagyensh Chandra Pati, Ramin Rezaiifar, and P. S. Krishnaprasad. 1993. Orthogonal matching pursuit: Recursive function approximation with applications to wavelet decomposition. In Conference Record of the 1993 27th Asilomar Conference on Signals, Systems, and Computers. IEEE, Los Alamitos, CA, 40–44.
    26. Scott Schaefer, Joe Warren, and Denis Zorin. 2004. Lofting curve networks using subdivision surfaces. In Proceedings of the Eurographics/ACM SIGGRAPH Symposium on Geometry Processing. ACM, New York, NY, 103–114. 
    27. Elif Tosun and Denis Zorin. 2011. Manifold-based surfaces with boundaries. Computer Aided Geometric Design 28, 1, 1–22. 
    28. Hongyu Wang, Ying He, Xin Li, Xianfeng Gu, and Hong Qin. 2008. Polycube splines. Computer-Aided Design 40, 6, 721–733. 
    29. John Wright, Allen Y. Yang, Arvind Ganesh, Shankar S. Sastry, and Yi Ma. 2009. Robust face recognition via sparse representation. IEEE Transactions on Pattern Analysis and Machine Intelligence 31, 2, 210–227. 
    30. Shiyao Xiong, Juyong Zhangy, Jianmin Zheng, Jianfei Cai, and Ligang Liu. 2014. Robust surface reconstruction via dictionary learning. ACM Transactions on Graphics 33, 6, 201. 
    31. Linlin Xu, Ruimin Wang, Juyong Zhang, Zhouwang Yang, Jiansong Deng, Falai Chen, and Ligang Liu. 2015. Survey on sparsity in geometric modeling and processing. Graphical Models 82, 160–180. 
    32. Jianchao Yang, John Wright, Thomas S. Huang, and Yi Ma. 2010. Image super-resolution via sparse representation. IEEE Transactions on Image Processing 19, 11, 2861–2873. 
    33. Lexing Ying and Denis Zorin. 2004. A simple manifold-based construction of surface of arbitrary smoothness. ACM Transactions on Graphics 23, 3, 271–275. 
    34. Yixin Zhuang, Ming Zou, Nathan Carr, and Tao Ju. 2013. A general and efficient method for finding cycles in 3D curve networks. ACM Transactions on Graphics 32, 6, 180. 
    35. Olgierd Cecil Zienkiewicz and Robert Leroy Taylor. 1977. The Finite Element Method. Vol. 3. McGraw-Hill London.

ACM Digital Library Publication: