“T-spline simplification and local refinement” by Sederberg, Cardon, Finnigan, North, Zheng, et al. …

  • ©Thomas (Tom) W. Sederberg, David L. Cardon, G Thomas Finnigan, Nicholas S. North, Jianmin Zheng, and Tom Lyche




    T-spline simplification and local refinement



    A typical NURBS surface model has a large percentage of superfluous control points that significantly interfere with the design process. This paper presents an algorithm for eliminating such superfluous control points, producing a T-spline. The algorithm can remove substantially more control points than competing methods such as B-spline wavelet decomposition. The paper also presents a new T-spline local refinement algorithm and answers two fundamental open questions on T-spline theory.


    1. BOEHM, W. 1980. Inserting new knots into B-spline curves. Computer-Aided Design 12 (July), 199–201.Google ScholarCross Ref
    2. BOEHM, W. 1981. Generating the Bezier points of B-spline curves and surfaces. Computer-Aided Design 13 (Nov.), 365–366.Google ScholarCross Ref
    3. COHEN, E., LYCHE, T., AND RIESENFELD, R. F. 1980. Discrete B-spline subdivision techniques in computer-aided geometric design and computer graphics. Computer Graphics and Image Processing 14 (Oct.), 87–111.Google ScholarCross Ref
    4. DAEHLEN, M., AND LYCHE, T. 1992. Decomposition of splines. In Mathematical Methods in Computer Aided Geometric Design II, Academic Press, New York, T. Lyche and L. L. Schumaker, Eds., 135–160. Google ScholarDigital Library
    5. FARIN, G., REIN, G., SAPIDIS, N., AND WORSEY, A. J. 1987. Fairing cubic B-spline curves. Computer Aided Geometric Design 4, 1–2 (July), 91–103. Google ScholarDigital Library
    6. FORSEY, D. R., AND BARTELS, R. H. 1988. Hierarchical B-spline refinement. In Computer Graphics (SIGGRAPH ’88 Proceedings), J. Dill, Ed., vol. 22, 205–212. Google ScholarDigital Library
    7. FORSEY, D., AND WONG, D. 1998. Multiresolution surface reconstruction for hierarchical b-splines. In Graphics Interface, 57–64.Google Scholar
    8. GOLDMAN, R. N., AND LYCHE, T. 1993. Knot Insertion and Deletion Algorithms for B-Spline Curves and Surfaces. Philadelphia: SIAM.Google Scholar
    9. GONZALEZ-OCHOA, C., AND PETERS, J. 1999. Localized-hierarchy surface splines (less). In Proceedings of the 1999 symposium on Interactive 3D graphics, ACM Press, 7–15. Google ScholarDigital Library
    10. GRINSPUN, E., KRYSL, P., AND SCHRÖDER, P. 2002. CHARMS: a simple framework for adaptive simulation. In Proceedings of SIGGRAPH02, ACM Press, 281–290. Google ScholarDigital Library
    11. HANDSCOMB, D. 1987. Knot elimination: reversal of the Oslo algorithm. International Series of Numerical Mathematics 81, 103–111.Google ScholarCross Ref
    12. KRAFT, R. 1997. Adaptive and linearly independent multilevel B-splines. In Surface Fitting and Multiresolution Methods, Vanderbilt University Press, A. L. Mhaut, C. Rabut, and L. L. Schumaker, Eds., vol. 2, 209–218.Google Scholar
    13. LANE, J. M., AND RIESENFELD, R. F. 1980. A theoretical development for the computer generation of piecewise polynomial surfaces. IEEE Transactions on Pattern Analysis and Machine Intelligence PAMI-2, 1 (Jan.), 35–46.Google ScholarDigital Library
    14. LYCHE, T., AND MÖRKEN, K. 1987. Knot removal for parametric B-spline curves and surfaces. Computer Aided Geometric Design 4, 3 (Nov.), 217–230. Google ScholarDigital Library
    15. LYCHE, T., AND SCHUMAKER, L. L. 2000. A multiresolution tensor spline method for fitting functions on the sphere. SIAM Journal of Scientific Computing 22, 724–746. Google ScholarDigital Library
    16. LYCHE, T., COHEN, E., AND MORKEN, K. 1985. Knot line refinement algorithms for tensor product B-spline surfaces. Computer Aided Geometric Design 2, 1–3, 133–139.Google ScholarDigital Library
    17. LYCHE, T., MORKEN, K., AND QUAK, E. 2001. Theory and algorithms for non-uniform spline wavelets. In Multivariate Approximation and Applications, N. Dyn, D. Leviatan, D. Levin, and A. Pinkus, Eds. Cambridge University Press, 152–187.Google Scholar
    18. LYCHE, T. 1993. Knot removal for spline curves and surfaces. In Approximation Theory VII, Academic Press, E. W. Cheney, C. K. Chui, and L. L. Schumaker, Eds., 207–227.Google Scholar
    19. SCHRÖDER, P., AND SWELDENS, W. 1995. Spherical wavelets: Efficiently representing functions on the sphere. In Proceedings of SIGGRAPH 95, 161–172. Google ScholarDigital Library
    20. SEDERBERG, T. W., ZHENG, J., BAKENOV, A., AND NASRI, A. 2003. T-splines and T-nurccs. ACM Transactions on Graphics 22, 3 (July), 477–484. Google ScholarDigital Library
    21. SEIDEL, H.-P. 1988. Knot insertion from a blossoming point of view. Computer Aided Geometric Design 5, 1 (June), 81–86. Google ScholarDigital Library
    22. WELLER, F., AND HAGEN, H. 1995. Tensor product spline spaces with knot segments. In Mathematical Methods for Curves and Surfaces, M. Daehlen, T. Lyche, and L. L. Schumaker, Eds. Vanderbilt University Press, Nashville, 563–572.Google Scholar

ACM Digital Library Publication: