ISSN 0253-2778

CN 34-1054/N

open
Free to Publish. Free to Read.
Open AccessOpen Access JUSTC Original Paper

Shape approximation via sparse optimization

  • School of Mathematical Sciences, University of Science and Technology of China, Hefei 230026, China

Cite this:
https://doi.org/10.3969/j.issn.0253-2778.2017.09.001
  • Received Date: 14 January 2017
  • Accepted Date: 05 June 2017
  • Rev Recd Date: 05 June 2017
  • Publish Date: 30 September 2017
    Abstract

  • Abstract

    A novel sparse optimization based shape approximation method to represent a 3D model using planar pieces was introduced, which enables a designer specified reasonable and fixed number of planes to be obtained. The method first gives a L0 minimization algorithm to optimize the face normal of the input model and then updates the vertex position based on filtered normal information. Next, a simple clustering method was proposed to obtain a clustering model. To this end, a boundary vertex gradient minimization algorithm was developed for solving a global energy function to represent the input model. A large number of experiments show the validity of the model and algorithm as well as the stability of the algorithm when solving mesh simplification problems in dynamic environments.

    Abstract

    A novel sparse optimization based shape approximation method to represent a 3D model using planar pieces was introduced, which enables a designer specified reasonable and fixed number of planes to be obtained. The method first gives a L0 minimization algorithm to optimize the face normal of the input model and then updates the vertex position based on filtered normal information. Next, a simple clustering method was proposed to obtain a clustering model. To this end, a boundary vertex gradient minimization algorithm was developed for solving a global energy function to represent the input model. A large number of experiments show the validity of the model and algorithm as well as the stability of the algorithm when solving mesh simplification problems in dynamic environments.
    • FullText(HTML)
  • loading
    • References(24)
  • [1]
    COHEN-STEINER D, ALLIEZ P, DESBRUN M. Variational shape approximation[J] ACM Transactions on Graphics (TOG), 2004, 23(3): 905-914.
    [2]
    CHEN D, SITTHI-AMORN P, LAN J T, et al. Computing and fabricating multiplanar models[J]. Computer Graphics Forum, 2013, 32(2pt3): 305-315.
    [3]
    CUTLER B, WHITING E. Constrained planar remeshing for architecture[C]// Proceedings of Graphics Interface 2007. New York: ACM, 2007: 11-18.
    [4]
    COHEN J, MANOCHA D, OLANO M. Simplifying polygonal models using successive mappings[C]//Proceedings of the 8th Conference on Visualization ′97. Los Alamitos, CA: IEEE Computer Society Press, 1997: 395-ff.
    [5]
    GARLAND M, HECKBERT P S. Surface simplification using quadric error metrics[C]// Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques. New York: ACM Press/ Addison-Wesley Publishing Co, 1997: 209-216.
    [6]
    HOPPE H. Progressive meshes[C]// Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques. New York: ACM, 1996: 99-108.
    [7]
    HOPPE H, DEROSE T, DUCHAMP T, et al. Mesh optimization[C]// Proceedings of the 20th Annual Conference on Computer Graphics and Interactive Techniques. New York: ACM, 1993: 19-26.
    [8]
    SCHROEDER W J, ZARGE J A, LORENSEN W E. Decimation of triangle meshes[C]// Proceedings of the 19th Annual Conference on Computer Graphics and Interactive Techniques. New York: ACM, 1992, 26(2): 65-70.
    [9]
    LI L, HE M, WANG P. Mesh simplification algorithm based on absolute curvature-weighted quadric error metrics[C]// 2010 5th IEEE Conference on Industrial Electronics and Applications. IEEE, 2010: 399-403.
    [10]
    YAO L, HUANG S, XU H, et al. Quadratic error metric mesh simplification algorithm based on discrete curvature[J]. Mathematical Problems in Engineering, 2015, 2015: Article ID 428917.
    [11]
    PAPAGEORGIOU A, PLATIS N. Triangular mesh simplification on the GPU[J]. The Visual Computer, 2015, 31(2): 235-244.
    [12]
    WANG J, WANG L, LI J, et al. A feature preserved mesh simplification algorithm[J]. Journal of Engineering and Computer Innovations, 2011, 2(6): 98-105.
    [13]
    周昆, 潘志庚, 石教英. 基于三角形折叠的网格简化算法[J]. 计算机学报, 1998, 21(6):506-513.
    ZHOU Kun, PAN Zhigeng, SHI Jiaoying. Mesh simplification algorithm based on triangle collapse[J]. Chinese J Computers, 1998, 21(6): 506-513.
    [14]
    潘志庚, 马小虎, 石教英. 虚拟环境中多细节层次模型自动生成算法[J]. 软件学报, 1996, 7(9): 526-531.
    PAN Zhigeng, MA Xiaohu, SHI Jiaoying. The automatic generation algorithm for models at multiple levels of detail in virtual environment[J]. Journal of Software, 1996, 7(9): 526-531.
    [15]
    周晓云, 刘慎权. 基于特征角准则的多面体简化方法[J]. 计算机学报, 1996(增刊): 212-223.
    ZHOU Xiaoyun, LIU Shenquan. Polyhedral simplification method based on characteristic angle criterion[J]. Chinese J Computers, 1996(suppl): 212-223.
    [16]
    GLOWINSKI R, LE TALLEC P. Augmented Lagrangian and operator-splitting methods in nonlinear mechanics[M]. Philadelphia, PA: SIAM, 1989.
    [17]
    WU C, TAI X C. Augmented Lagrangian method, dual methods, and split Bregman iteration for ROF, vectorial TV, and high order models[J]. SIAM Journal on Imaging Sciences, 2010, 3(3): 300-339.
    [18]
    WU C, ZHANG J, TAI X C. Augmented Lagrangian method for total variation restoration with non-quadratic fidelity[J]. Inverse Problems and Imaging, 2011, 5(1): 237-261.
    [19]
    ZHANG H, WU C, ZHANG J, et al. Variational mesh denoising using total variation and piecewise constant function space[J]. IEEE Transactions on Visualization and Computer Graphics, 2015, 21(7): 873-886.
    [20]
    WANG P S, FU X M, LIU Y, et al. Rolling guidance normal filter for geometric processing[J]. ACM Transactions on Graphics (TOG), 2015, 34(6): 173.
    [21]
    YU Y, ZHOU K, XU D, et al. Mesh editing with poisson-based gradient field manipulation[C]//ACM Transactions on Graphics (TOG). ACM, 2004, 23(3): 644-651.
    [22]
    ARTHUR D, VASSILVITSKII S. k-means++: The advantages of careful seeding[C]//Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2007: 1027-1035.
    [23]
    KANUNGO T, MOUNT D M, NETANYAHU N S, et al. An efficient k-means clustering algorithm: Analysis and implementation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 24(7): 881-892.
    [24]
    LOW K L, TAN T S. Model simplification using vertex-clustering[C]//Proceedings of the 1997 Symposium on Interactive 3D Graphics. New York: ACM, 1997: 75-ff.)
    • Supplements(0)
    • Related Articles
    • Track Citations
  • 加载中

Catalog

    Get Citation
    PDF
    XML
    [1]
    COHEN-STEINER D, ALLIEZ P, DESBRUN M. Variational shape approximation[J] ACM Transactions on Graphics (TOG), 2004, 23(3): 905-914.
    [2]
    CHEN D, SITTHI-AMORN P, LAN J T, et al. Computing and fabricating multiplanar models[J]. Computer Graphics Forum, 2013, 32(2pt3): 305-315.
    [3]
    CUTLER B, WHITING E. Constrained planar remeshing for architecture[C]// Proceedings of Graphics Interface 2007. New York: ACM, 2007: 11-18.
    [4]
    COHEN J, MANOCHA D, OLANO M. Simplifying polygonal models using successive mappings[C]//Proceedings of the 8th Conference on Visualization ′97. Los Alamitos, CA: IEEE Computer Society Press, 1997: 395-ff.
    [5]
    GARLAND M, HECKBERT P S. Surface simplification using quadric error metrics[C]// Proceedings of the 24th Annual Conference on Computer Graphics and Interactive Techniques. New York: ACM Press/ Addison-Wesley Publishing Co, 1997: 209-216.
    [6]
    HOPPE H. Progressive meshes[C]// Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques. New York: ACM, 1996: 99-108.
    [7]
    HOPPE H, DEROSE T, DUCHAMP T, et al. Mesh optimization[C]// Proceedings of the 20th Annual Conference on Computer Graphics and Interactive Techniques. New York: ACM, 1993: 19-26.
    [8]
    SCHROEDER W J, ZARGE J A, LORENSEN W E. Decimation of triangle meshes[C]// Proceedings of the 19th Annual Conference on Computer Graphics and Interactive Techniques. New York: ACM, 1992, 26(2): 65-70.
    [9]
    LI L, HE M, WANG P. Mesh simplification algorithm based on absolute curvature-weighted quadric error metrics[C]// 2010 5th IEEE Conference on Industrial Electronics and Applications. IEEE, 2010: 399-403.
    [10]
    YAO L, HUANG S, XU H, et al. Quadratic error metric mesh simplification algorithm based on discrete curvature[J]. Mathematical Problems in Engineering, 2015, 2015: Article ID 428917.
    [11]
    PAPAGEORGIOU A, PLATIS N. Triangular mesh simplification on the GPU[J]. The Visual Computer, 2015, 31(2): 235-244.
    [12]
    WANG J, WANG L, LI J, et al. A feature preserved mesh simplification algorithm[J]. Journal of Engineering and Computer Innovations, 2011, 2(6): 98-105.
    [13]
    周昆, 潘志庚, 石教英. 基于三角形折叠的网格简化算法[J]. 计算机学报, 1998, 21(6):506-513.
    ZHOU Kun, PAN Zhigeng, SHI Jiaoying. Mesh simplification algorithm based on triangle collapse[J]. Chinese J Computers, 1998, 21(6): 506-513.
    [14]
    潘志庚, 马小虎, 石教英. 虚拟环境中多细节层次模型自动生成算法[J]. 软件学报, 1996, 7(9): 526-531.
    PAN Zhigeng, MA Xiaohu, SHI Jiaoying. The automatic generation algorithm for models at multiple levels of detail in virtual environment[J]. Journal of Software, 1996, 7(9): 526-531.
    [15]
    周晓云, 刘慎权. 基于特征角准则的多面体简化方法[J]. 计算机学报, 1996(增刊): 212-223.
    ZHOU Xiaoyun, LIU Shenquan. Polyhedral simplification method based on characteristic angle criterion[J]. Chinese J Computers, 1996(suppl): 212-223.
    [16]
    GLOWINSKI R, LE TALLEC P. Augmented Lagrangian and operator-splitting methods in nonlinear mechanics[M]. Philadelphia, PA: SIAM, 1989.
    [17]
    WU C, TAI X C. Augmented Lagrangian method, dual methods, and split Bregman iteration for ROF, vectorial TV, and high order models[J]. SIAM Journal on Imaging Sciences, 2010, 3(3): 300-339.
    [18]
    WU C, ZHANG J, TAI X C. Augmented Lagrangian method for total variation restoration with non-quadratic fidelity[J]. Inverse Problems and Imaging, 2011, 5(1): 237-261.
    [19]
    ZHANG H, WU C, ZHANG J, et al. Variational mesh denoising using total variation and piecewise constant function space[J]. IEEE Transactions on Visualization and Computer Graphics, 2015, 21(7): 873-886.
    [20]
    WANG P S, FU X M, LIU Y, et al. Rolling guidance normal filter for geometric processing[J]. ACM Transactions on Graphics (TOG), 2015, 34(6): 173.
    [21]
    YU Y, ZHOU K, XU D, et al. Mesh editing with poisson-based gradient field manipulation[C]//ACM Transactions on Graphics (TOG). ACM, 2004, 23(3): 644-651.
    [22]
    ARTHUR D, VASSILVITSKII S. k-means++: The advantages of careful seeding[C]//Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2007: 1027-1035.
    [23]
    KANUNGO T, MOUNT D M, NETANYAHU N S, et al. An efficient k-means clustering algorithm: Analysis and implementation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 24(7): 881-892.
    [24]
    LOW K L, TAN T S. Model simplification using vertex-clustering[C]//Proceedings of the 1997 Symposium on Interactive 3D Graphics. New York: ACM, 1997: 75-ff.)
    Recommended articles
    TrendMD
    Volume 47 Issue 9 page: 713-720
    Cover

    Article Metrics

    Article views (29) PDF downloads(87)
    Proportional views

    Copyright © Editorial Office of JUSTC, All Rights Reserved. 皖ICP备05002528号

    Supported by: Beijing Renhe Information Technology Co. Ltd    

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return