ISSN 0253-2778

CN 34-1054/N

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

Face sorting and stripe texture mapping of triangle mesh based on spectral decomposition

  • 1.

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

  • 2.

    College of Computer Science and Electronic Engineering, Hunan University, Changsha 410082, China

Cite this:
https://doi.org/10.3969/j.issn.0253-2778.2017.09.002
  • Received Date: 11 October 2016
  • Accepted Date: 22 May 2017
  • Rev Recd Date: 22 May 2017
  • Publish Date: 30 September 2017
    Abstract

  • Abstract

    The layout of the triangle face in the existing mesh file format is often out of order, which brings great difficulties in the subsequent processing of large meshes. A useful approach later proposed based on spectral decomposition of dual meshes, did lead to a good face order. However, the order was only partial. In view of the drawback of the algorithm, a unique traversal algorithm was presented here which can get a triangular mesh with a total ordered layout of the faces. Furthermore, a series of ordered triangle strips were obtained, and the geometric and topological properties of the original input mesh didn’t change in the process. Finally, the triangle strips were parameterized, and the stripe texture mapping was applied. Experimental results show that the method is superior to the spectral decomposition method and can generate a satisfactory triangular strip.

    Abstract

    The layout of the triangle face in the existing mesh file format is often out of order, which brings great difficulties in the subsequent processing of large meshes. A useful approach later proposed based on spectral decomposition of dual meshes, did lead to a good face order. However, the order was only partial. In view of the drawback of the algorithm, a unique traversal algorithm was presented here which can get a triangular mesh with a total ordered layout of the faces. Furthermore, a series of ordered triangle strips were obtained, and the geometric and topological properties of the original input mesh didn’t change in the process. Finally, the triangle strips were parameterized, and the stripe texture mapping was applied. Experimental results show that the method is superior to the spectral decomposition method and can generate a satisfactory triangular strip.
    • FullText(HTML)
  • loading
    • References(26)
  • [1]
    ISENBURG M, LINDSTROM P. Streaming meshes[C]//VIS 05. IEEE Visualization, 2005. IEEE, 2005: 231-238.
    [2]
    WU J, KOBBELT L. A stream algorithm for the decimation of massive meshes[C]// Proceedings of Graphics Interface 2003. Waterloo, Canada: Canadian Human-Computer Communications Society, 2003: 185-192.
    [3]
    ISENBURG M, GUMHOLD S. Out-of-core compression for gigantic polygon meshes[C]// ACM Transactions on Graphics (TOG). New York: ACM, 2003, 22(3): 935-942.
    [4]
    DEERING M. Geometry compression[C]//Proceedings of the 22nd Annual Conference on Computer Graphics and Interactive Techniques. New York: ACM, 1995: 13-20.
    [5]
    HOPPE H, MILLER J W. Optimization of mesh locality for transparent vertex caching: US, US 6426747 B1[P]. 2002: 269-276.
    [6]
    BOGOMJAKOV A, GOTSMAN C. Universal rendering sequences for transparent vertex caching of progressive meshes[J]. Computer Graphics Forum, 2002, 21(2):137-149.
    [7]
    TCHIBOUKDJIAN M, DANJEAN V, RAFFIN B. Binary mesh partitioning for cache-efficient visualization[J]. IEEE Transactions on Visualization & Computer Graphics, 2010, 16(5): 815-828.
    [8]
    GAREY M R, JOHNSON D S, TARJAN R E. The planar Hamiltonian circuit problem is NP-complete[J]. Siam Journal on Computing, 1976, 5(4):704-714.
    [9]
    AKELEY K, HAEBERLi P, BURNS D. Tomesh. c: C program on SGI developer’s toolbox CD[R]. Milpitas, CA: Silicon Graphics, 1990: T990.
    [10]
    EVANS F, SKIENA S, VARSHNEY A. Optimizing triangle strips for fast rendering[C]// Proceedings of the 7th Conference on Visualization '96. IEEE, 1996:319-326.
    [11]
    CHOW M M. Optimized geometry compression for real-time rendering[C]// Proceedings of the 8th Conference on Visualization '97. IEEE, 1997:347-ff.
    [12]
    SPECKMANN B, SNOEYINK J. Easy triangle strips for tin terrain models[J]. International Journal of Geographical Information Science, 2001, 15(4): 379-386.
    [13]
    XIANG X, HELD M, MITCHELL J S B. Fast and effective stripification of polygonal surface models[C]// Proceedings of the 1999 Symposium on Interactive 3D Graphics. New York: ACM, 1999: 71-78.
    [14]
    SHAFAE M, PAJAROLA R. Dstrips: Dynamic triangle strips for real-time mesh simplification and rendering[C]// Proceedings Pacific Conference on Computer Graphics and Applications, 2003. IEEE, 2003: 271-280.
    [15]
    DEMAINE E D, EPPSTEIN D, ERICKSON J, et al. Vertex-unfoldings of simplicial manifolds[C]// Proceedings of the Eighteenth Annual Symposium on Computational Geometry. New York: ACM, 2002: 237-243.
    [16]
    PORCU M B, SCATENI R. Partitioning meshes into strips using the enhanced tunnelling algorithm (ETA)[C]// VRIPHYS 2006. Geneve, Switzerland: Eurographics Association, 2006: 61-70.
    [17]
    秦爱红, 石教英. 基于混合模式缓存优化的三角形条带化[J]. 计算机辅助设计与图形学学报, 2011, 23(6):1006-1012.
    QIN Aihong, SHI Jiaoying. Cach-friendly triangle strip generation based on hybrid model[J]. Journal of Computer Aided Design & Computer Graphic, 2011, 23(6): 1006-1012.
    [18]
    张洁, 吴佳泽, 郑昌文,等. 应用哈密顿回路的三角网格拓扑压缩[J]. 计算机辅助设计与图形学学报, 2013, 25(5): 697-707.ZHANG Jie, WU Jiaze, ZHEN Changwen, et al. Connectivity compression of triangle meshes based on Hamiltonian cycle[J]. Journal of Computer Aided Design & Computer Graphic, 2013, 25(5): 697-707.
    [19]
    魏潇然, 耿国华, 张雨禾. 几何信息预测的三角网格模型拓扑压缩[J]. 西安电子科技大学学报(自然科学版), 2015, 42(5):194-199.
    WEI Xiaoran, GEN Guohua, ZHANG Yuhe. Connectivity compression of triangle meshes based on geometric parameter predict[J]. Journal of Xi’an Electronic and Science University (Natural Science Edition), 2015, 42(5): 194-199.
    [20]
    ARKIN E M, HELD M, MITCHELL J S B, et al. Hamiltonian triangulations for fast rendering[J]. Visual Computer, 1996, 12(9):429-444.
    [21]
    PAJAROLA R, ANTONIJUAN M, LARIO R. QuadTIN: Quadtree based triangulated irregular networks[C]// Proceedings of the Conference on Visualization 2002. IEEE, 2002: 395-402.
    [22]
    TAUBIN G. Constructing Hamiltonian triangle strips on quadrilateral meshes[M]// Visualization and Mathematics III. Berlin: Springer, 2003: 69-91.
    [23]
    GOPI M, EPPSTIEN D. Single-strip triangulation of manifolds with arbitrary topology[J]. Computer Graphics Forum, 2004, 23(3):371-379.
    [24]
    DIAZ-GUTIERREZ P, BHUSHAN A, GOPI M, et al. Single-strips for fast interactive rendering[J]. Visual Computer, 2006, 22(6):372-386.
    [25]
    GURUNG T, LUFFEL M, LINDSTROM P, et al. LR: compact connectivity representation for triangle meshes[J]. ACM Transactions on Graphics, 2011, 30(4):76-79.
    [26]
    FLOATER M S. Parametrization and smooth approximation of surface triangulations[J]. Computer Aided Geometric Design, 1997, 14(3): 231-250.
    • Supplements(0)
    • Related Articles
    • Track Citations
  • 加载中

Catalog

    |
    Get Citation
    PDF
    XML
    [1]
    ISENBURG M, LINDSTROM P. Streaming meshes[C]//VIS 05. IEEE Visualization, 2005. IEEE, 2005: 231-238.
    [2]
    WU J, KOBBELT L. A stream algorithm for the decimation of massive meshes[C]// Proceedings of Graphics Interface 2003. Waterloo, Canada: Canadian Human-Computer Communications Society, 2003: 185-192.
    [3]
    ISENBURG M, GUMHOLD S. Out-of-core compression for gigantic polygon meshes[C]// ACM Transactions on Graphics (TOG). New York: ACM, 2003, 22(3): 935-942.
    [4]
    DEERING M. Geometry compression[C]//Proceedings of the 22nd Annual Conference on Computer Graphics and Interactive Techniques. New York: ACM, 1995: 13-20.
    [5]
    HOPPE H, MILLER J W. Optimization of mesh locality for transparent vertex caching: US, US 6426747 B1[P]. 2002: 269-276.
    [6]
    BOGOMJAKOV A, GOTSMAN C. Universal rendering sequences for transparent vertex caching of progressive meshes[J]. Computer Graphics Forum, 2002, 21(2):137-149.
    [7]
    TCHIBOUKDJIAN M, DANJEAN V, RAFFIN B. Binary mesh partitioning for cache-efficient visualization[J]. IEEE Transactions on Visualization & Computer Graphics, 2010, 16(5): 815-828.
    [8]
    GAREY M R, JOHNSON D S, TARJAN R E. The planar Hamiltonian circuit problem is NP-complete[J]. Siam Journal on Computing, 1976, 5(4):704-714.
    [9]
    AKELEY K, HAEBERLi P, BURNS D. Tomesh. c: C program on SGI developer’s toolbox CD[R]. Milpitas, CA: Silicon Graphics, 1990: T990.
    [10]
    EVANS F, SKIENA S, VARSHNEY A. Optimizing triangle strips for fast rendering[C]// Proceedings of the 7th Conference on Visualization '96. IEEE, 1996:319-326.
    [11]
    CHOW M M. Optimized geometry compression for real-time rendering[C]// Proceedings of the 8th Conference on Visualization '97. IEEE, 1997:347-ff.
    [12]
    SPECKMANN B, SNOEYINK J. Easy triangle strips for tin terrain models[J]. International Journal of Geographical Information Science, 2001, 15(4): 379-386.
    [13]
    XIANG X, HELD M, MITCHELL J S B. Fast and effective stripification of polygonal surface models[C]// Proceedings of the 1999 Symposium on Interactive 3D Graphics. New York: ACM, 1999: 71-78.
    [14]
    SHAFAE M, PAJAROLA R. Dstrips: Dynamic triangle strips for real-time mesh simplification and rendering[C]// Proceedings Pacific Conference on Computer Graphics and Applications, 2003. IEEE, 2003: 271-280.
    [15]
    DEMAINE E D, EPPSTEIN D, ERICKSON J, et al. Vertex-unfoldings of simplicial manifolds[C]// Proceedings of the Eighteenth Annual Symposium on Computational Geometry. New York: ACM, 2002: 237-243.
    [16]
    PORCU M B, SCATENI R. Partitioning meshes into strips using the enhanced tunnelling algorithm (ETA)[C]// VRIPHYS 2006. Geneve, Switzerland: Eurographics Association, 2006: 61-70.
    [17]
    秦爱红, 石教英. 基于混合模式缓存优化的三角形条带化[J]. 计算机辅助设计与图形学学报, 2011, 23(6):1006-1012.
    QIN Aihong, SHI Jiaoying. Cach-friendly triangle strip generation based on hybrid model[J]. Journal of Computer Aided Design & Computer Graphic, 2011, 23(6): 1006-1012.
    [18]
    张洁, 吴佳泽, 郑昌文,等. 应用哈密顿回路的三角网格拓扑压缩[J]. 计算机辅助设计与图形学学报, 2013, 25(5): 697-707.ZHANG Jie, WU Jiaze, ZHEN Changwen, et al. Connectivity compression of triangle meshes based on Hamiltonian cycle[J]. Journal of Computer Aided Design & Computer Graphic, 2013, 25(5): 697-707.
    [19]
    魏潇然, 耿国华, 张雨禾. 几何信息预测的三角网格模型拓扑压缩[J]. 西安电子科技大学学报(自然科学版), 2015, 42(5):194-199.
    WEI Xiaoran, GEN Guohua, ZHANG Yuhe. Connectivity compression of triangle meshes based on geometric parameter predict[J]. Journal of Xi’an Electronic and Science University (Natural Science Edition), 2015, 42(5): 194-199.
    [20]
    ARKIN E M, HELD M, MITCHELL J S B, et al. Hamiltonian triangulations for fast rendering[J]. Visual Computer, 1996, 12(9):429-444.
    [21]
    PAJAROLA R, ANTONIJUAN M, LARIO R. QuadTIN: Quadtree based triangulated irregular networks[C]// Proceedings of the Conference on Visualization 2002. IEEE, 2002: 395-402.
    [22]
    TAUBIN G. Constructing Hamiltonian triangle strips on quadrilateral meshes[M]// Visualization and Mathematics III. Berlin: Springer, 2003: 69-91.
    [23]
    GOPI M, EPPSTIEN D. Single-strip triangulation of manifolds with arbitrary topology[J]. Computer Graphics Forum, 2004, 23(3):371-379.
    [24]
    DIAZ-GUTIERREZ P, BHUSHAN A, GOPI M, et al. Single-strips for fast interactive rendering[J]. Visual Computer, 2006, 22(6):372-386.
    [25]
    GURUNG T, LUFFEL M, LINDSTROM P, et al. LR: compact connectivity representation for triangle meshes[J]. ACM Transactions on Graphics, 2011, 30(4):76-79.
    [26]
    FLOATER M S. Parametrization and smooth approximation of surface triangulations[J]. Computer Aided Geometric Design, 1997, 14(3): 231-250.
    Recommended articles
    TrendMD
    Volume 47 Issue 9 page: 721-728
    Cover

    Article Metrics

    Article views (27) PDF downloads(91)
    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