“Dyadic T-mesh subdivision” by Kovacs, Bisceglio and Zorin

  • ©Denis Kovacs, Justin Bisceglio, and Denis Zorin




    Dyadic T-mesh subdivision



    Meshes with T-joints (T-meshes) and related high-order surfaces have many advantages in situations where flexible local refinement is needed. At the same time, designing subdivision rules and bases for T-meshes is much more difficult, and fewer options are available. For common geometric modeling tasks it is desirable to retain the simplicity and flexibility of commonly used subdivision surfaces, and extend them to handle T-meshes.We propose a subdivision scheme extending Catmull-Clark and NURSS to a special class of quad T-meshes, dyadic T-meshes, which have no more than one T-joint per edge. Our scheme is based on a factorization with the same structure as Catmull-Clark subdivision. On regular T-meshes it is a refinement scheme for a subset of standard T-splines. While we use more variations of subdivision masks compared to Catmull-Clark and NURSS, the minimal size of the stencil is maintained, and all variations in formulas are due to simple changes in coefficients.


    1. Andersson, L.-E., and Stewart, N. F. 2010. Introduction to the mathematics of subdivision surfaces. SIAM. Google ScholarDigital Library
    2. Bazilevs, Y., Calo, V., Cottrell, J., Evans, J., Hughes, T., Lipton, S., Scott, M., and Sederberg, T. 2010. Isogeometric analysis using T-splines. Computer Methods in Applied Mechanics and Engineering 199, 5–8, 229–263.Google ScholarCross Ref
    3. Bertram, M., Duchaineau, M., Hamann, B., and Joy, K. 2004. Generalized B-spline subdivision-surface wavelets for geometry compression. Visualization and Computer Graphics, IEEE Transactions on 10, 3, 326–338. Google ScholarDigital Library
    4. Bitmapworld, 2006. Little girl head 3d model (http://www.turbosquid.com/3d-models/polygonal-head-little-girl-3d-model/302581).Google Scholar
    5. Buffa, A., Cho, D., and Sangalli, G. 2010. Linear independence of the T-spline blending functions associated with some particular T-meshes. Computer Methods in Applied Mechanics and Engineering 199, 23–24, 1437–1445.Google ScholarCross Ref
    6. Cashman, T., Augsdörfer, U., Dodgson, N., and Sabin, M. 2009. NURBS with extraordinary points: high-degree, non-uniform, rational subdivision schemes. ACM Transactions on Graphics (TOG) 28, 3, 46. Google ScholarDigital Library
    7. Cashman, T., Dodgson, N., and Sabin, M. 2009. A symmetric, non-uniform, refine and smooth subdivision algorithm for general degree B-splines. Computer Aided Geometric Design 26, 1, 94–104. Google ScholarDigital Library
    8. Cashman, T. 2012. Beyond Catmull-Clark? a survey of advances in subdivision surface methods. In Computer Graphics Forum, vol. 31, 42–61. Google ScholarDigital Library
    9. Catmull, E., and Clark, J. 1978. Recursively generated B-spline surfaces on arbitrary topological meshes. Computer-Aided Design 10, 6, 350–355.Google ScholarCross Ref
    10. Cottrell, J., Hughes, T., and Bazilevs, Y. 2009. Isogeometric analysis: toward integration of CAD and FEA. John Wiley & Sons Inc. Google ScholarDigital Library
    11. Deng, J., Chen, F., and Feng, Y. 2006. Dimensions of spline spaces over T-meshes. Journal of Computational and Applied Mathematics 194, 2, 267–283. Google ScholarDigital Library
    12. Deng, J., Chen, F., Li, X., Hu, C., Tong, W., Yang, Z., and Feng, Y. 2008. Polynomial splines over hierarchical T-meshes. Graphical Models 70, 4, 76–86. Google ScholarDigital Library
    13. Dörfel, M., Jüttler, B., and Simeon, B. 2010. Adaptive isogeometric analysis by local h-refinement with T-splines. Computer methods in applied mechanics and engineering 199, 5–8, 264–275.Google Scholar
    14. Eck, M., DeRose, T., Duchamp, T., Hoppe, H., Lounsbery, M., and Stuetzle, W. 1995. Multiresolution analysis of arbitrary meshes. In Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, ACM, 173–182. Google ScholarDigital Library
    15. Evans, E., Scott, M., Li, X., and Thomas, D. 2014. Hierarchical t-splines: Analysis-suitability, bézier extraction, and application as an adaptive basis for isogeometric analysis. Computer Methods in Applied Mechanics and Engineering.Google Scholar
    16. Khodakovsky, A., Schröder, P., and Sweldens, W. 2000. Progressive geometry compression. In Proceedings of the 27th annual conference on Computer graphics and interactive techniques, ACM Press/Addison-Wesley Publishing Co., 271–278. Google ScholarDigital Library
    17. Li, M., and Scott, M. 2011. On the nesting behavior of t-splines. Tech. Rep. 11–13, ICES.Google Scholar
    18. Li, X., Deng, J., and Chen, F. 2010. Polynomial splines over general T-meshes. The Visual Computer 26, 4, 277–286. Google ScholarDigital Library
    19. Li, X., Zheng, J., Sederberg, T., Hughes, T., and Scott, M. 2012. On linear independence of T-spline blending functions. Computer Aided Geometric Design 29, 1, 63–76. Google ScholarDigital Library
    20. Liu, L., Zhang, Y., Liu, Y., and Wang, W. 2015. Feature-preserving t-mesh construction using skeleton-based polycubes. Computer-Aided Design 58, 162–172.Google ScholarDigital Library
    21. Lounsbery, M., DeRose, T., and Warren, J. 1997. Multiresolution analysis for surfaces of arbitrary topological type. ACM Transactions on Graphics (TOG) 16, 1, 34–73. Google ScholarDigital Library
    22. Morgenstern, P., and Peterseim, D. 2014. Analysis-suitable adaptive t-mesh refinement with linear complexity. Arxiv preprint arXiv:1407.6175.Google Scholar
    23. Mourrain, B. 2010. On the dimension of spline spaces on planar t-subdivisions. Arxiv preprint arXiv:1011.1752.Google Scholar
    24. Müller, K., Reusche, L., and Fellner, D. 2006. Extended subdivision surfaces: Building a bridge between NURBS and Catmull-Clark surfaces. ACM Transactions on Graphics (TOG) 25, 2, 268–292. Google ScholarDigital Library
    25. Müller, K., Fünfzig, C., Reusche, L., Hansford, D., Farin, G., and Hagen, H. 2010. Dinus: Double insertion, nonuniform, stationary subdivision surfaces. ACM Transactions on Graphics (TOG) 29, 3, 25. Google ScholarDigital Library
    26. Myles, A., Pietroni, N., Kovacs, D., and Zorin, D. 2010. Feature-aligned T-meshes. ACM Transactions on Graphics (TOG) 29, 4, 117. Google ScholarDigital Library
    27. Prautzsch, H., and Chen, Q. 2011. Analyzing midpoint subdivision. Computer Aided Geometric Design. Google ScholarDigital Library
    28. Scott, M., Li, X., Sederberg, T., and Hughes, T. 2012. Local refinement of analysis-suitable t-splines. Computer Methods in Applied Mechanics and Engineering 213–216, 206–222.Google Scholar
    29. Sederberg, T., Zheng, J., Sewell, D., and Sabin, M. 1998. Non-uniform recursive subdivision surfaces. In Proceedings of the 25th annual conference on Computer graphics and interactive techniques, ACM, 387–394. Google ScholarDigital Library
    30. Sederberg, T., Zheng, J., Bakenov, A., and Nasri, A. 2003. T-splines and T-NURCCs. In ACM Transactions on Graphics (TOG), vol. 22, ACM, 477–484. Google ScholarDigital Library
    31. Sederberg, T., Cardon, D., Finnigan, G., North, N., Zheng, J., and Lyche, T. 2004. T-spline simplification and local refinement. In ACM Transactions on Graphics (TOG), vol. 23, ACM, 276–283. Google ScholarDigital Library
    32. Stam, J. 2001. On subdivision schemes generalizing uniform B-spline surfaces of arbitrary degree. Computer Aided Geometric Design 18, 5, 383–396. Google ScholarDigital Library
    33. Wang, W., Zhang, Y., Scott, M., and Hughes, T. 2011. Converting an unstructured quadrilateral mesh to a standard T-spline surface. Computational Mechanics, 1–22. Google ScholarDigital Library
    34. Zorin, D., and Schröder, P. 2001. A unified framework for primal/dual quadrilateral subdivision schemes. Computer Aided Geometric Design 18, 5, 429–454. Google ScholarDigital Library
    35. Zorin, D., Schröder, P., and Sweldens, W. 1997. Interactive multiresolution mesh editing. In Proceedings of the 24th annual conference on Computer graphics and interactive techniques, ACM Press/Addison-Wesley Publishing Co., 259–268. Google ScholarDigital Library

ACM Digital Library Publication:

Overview Page: