×
Schumaker, Larry L.; Speleers, Hendrik

Convexity preserving splines over triangulations. (English) Zbl 1229.65043

Comput. Aided Geom. Des. 28, No. 4, 270-284 (2011).
Visualization of 3D data in the form of a surface view is one of the important topics in Computer Graphics. The problem gets critically important when the data possesses some inherent shape feature. This paper is concerned with the solution of this problem when the data has a convex shape and its visualization is required to have similar inherent features to that of the data, and its purpose is twofold. First, to describe a general method for constructing sets of sufficient linear conditions in terms of the control points of a triangular Bézier surface that ensure convexity. The method, which is based on blossoming, can be used to create nested sequences of weaker and weaker conditions, including all of the known sets of linear conditions. Second, to develop explicit convexity preserving interpolation and approximation methods using the linear convexity conditions together with certain macro-element spline spaces defined on triangulations.
Reviewer: Juan Monterde (Burjasot)

Cited in 6 Documents

MSC:

65D17 Computer-aided design (modeling of curves and surfaces)
65D07 Numerical computation using splines
41A15 Spline approximation
65D18 Numerical aspects of computer graphics, image analysis, and computational geometry

Keywords:

spline interpolation; shape preservation; convex surfaces; visualization of 3D data; computer graphics; triangular Bézier surface; blossoming; triangulations
Cite Review PDF
Full Text: DOI Link

References:

[1] Bangert, C.; Prautzsch, H., A geometric criterion for the convexity of Powell-Sabin interpolants and its multivariate generalization, Comput. Aided Geom. Design, 16, 529-538 (1999) · Zbl 0997.65008
[2] Cao, Y.; Hua, X. J., The convexity of quadratic parametric triangular Bernstein-Bézier surfaces, Comput. Aided Geom. Design, 8, 1-6 (1991) · Zbl 0724.65010
[3] Carnicer, J. M., Multivariate convexity preserving interpolation by smooth functions, Adv. Comp. Math., 3, 395-404 (1995) · Zbl 0831.65007
[4] Carnicer, J. M.; Dahmen, W., Convexity preserving interpolation and Powell-Sabin elements, Comput. Aided Geom. Design, 9, 279-289 (1992) · Zbl 0760.65005
[5] Carnicer, J. M.; Floater, M. S., Piecewise linear interpolants to Lagrange and Hermite convex scattered data, Numer. Algorithms, 13, 345-364 (1996) · Zbl 0870.65004
[6] Carnicer, J. M.; Floater, M. S.; Peña, J. M., Linear convexity conditions for rectangular and triangular Bernstein-Bézier surfaces, Comput. Aided Geom. Design, 15, 27-38 (1997) · Zbl 0894.68151
[7] Carnicer, J. M.; Goodman, T. N.T.; Peña, J. M., Convexity preserving scattered data interpolation using Powell-Sabin elements, Comput. Aided Geom. Design, 26, 779-796 (2009) · Zbl 1205.65057
[8] Chang, G.; Davis, P. J., The convexity of Bernstein polynomials over triangles, J. Approx. Theory, 40, 11-28 (1984) · Zbl 0528.41005
[9] Chang, G.; Feng, Y. Y., An improved condition for the convexity of Bernstein-Bézier surfaces over triangles, Comput. Aided Geom. Design, 1, 279-283 (1984) · Zbl 0563.41009
[10] Cheng, Z.; Chui, C. K., Convexity of parametric Bézier surfaces in terms of Gaussian curvature signatures, Advances in Comp. Math., 2, 437-459 (1994) · Zbl 0826.41014
[11] Dahmen, W., Convexity and Bernstein-Bézier polynomials, (Laurent, P.-J.; Le Méhauté, A.; Schumaker, L. L., Curves and Surfaces (1991), Academic Press: Academic Press New York), 107-134 · Zbl 0735.41005
[12] Dahmen, W.; Micchelli, C. A., Convexity of multivariate Bernstein polynomials and box spline surfaces, Stud. Sci. Math. Hung., 23, 265-287 (1988) · Zbl 0689.41013
[13] Dierckx, P., On calculating normalized Powell-Sabin B-splines, Comput. Aided Geom. Design, 15, 61-78 (1997) · Zbl 0894.68152
[14] Dierckx, P.; Van Leemput, S.; Vermeire, T., Algorithms for surface fitting using Powell-Sabin splines, IMA J. Numer. Anal., 12, 271-299 (1992) · Zbl 0774.65007
[15] Feng, Y. Y.; Chen, F. L.; Zhou, H. L., The invariance of weak convexity conditions of B-nets with respect to subdivision, Comput. Aided Geom. Design, 11, 97-107 (1994) · Zbl 0809.65006
[16] Floater, M. S., A weak condition for the convexity of tensor-product Bézier and B-spline surfaces, Adv. Comp. Math., 2, 67-80 (1994) · Zbl 0828.65011
[17] Floater, M. S., A counterexample to a theorem about the convexity of Powell-Sabin elements, Comput. Aided Geom. Design, 14, 383-385 (1997) · Zbl 0925.68429
[18] Goodman, T. N.T., Convexity of Bézier nets on triangulations, Comput. Aided Geom. Design, 8, 175-180 (1991) · Zbl 0731.41009
[19] Goodman, T. N.T.; Peters, J., Bézier nets, convexity and subdivision on higher-dimensional simplices, Comput. Aided Geom. Design, 12, 53-65 (1995) · Zbl 0875.68829
[20] Grandine, T. A., On convexity of piecewise polynomial functions on triangulations, Comput. Aided Geom. Design, 6, 181-187 (1989) · Zbl 0675.41029
[21] Gregory, J. A.; Zhou, J. W., Convexity of Bézier nets on sub-triangles, Comput. Aided Geom. Design, 8, 207-211 (1991) · Zbl 0756.41026
[22] He, T. X., Shape criteria of Bernstein-Bézier polynomials over simplexes, Comput. Math. Appl., 30, 317-333 (1995) · Zbl 0837.68123
[23] Jüttler, B., Surface fitting using convex tensor-product splines, J. Comput. Appl. Math., 84, 23-44 (1997) · Zbl 0883.65007
[24] Jüttler, B., Convex surface fitting with parametric Bézier surfaces, (Dæhlen, M.; Lyche, T.; Schumaker, L. L., Mathematical Methods for Curves and Surfaces II (1998), Vanderbilt University Press: Vanderbilt University Press Nashville), 263-270 · Zbl 0905.65011
[25] Jüttler, B., Arbitrarily weak linear convexity conditions for multivariate polynomials, Stud. Sci. Math. Hung., 36, 165-183 (2000) · Zbl 0974.41022
[26] Koras, G. D.; Kaklis, P. D., Convexity conditions for parametric tensor-product B-spline surfaces, Adv. Comp. Math., 10, 291-309 (1999) · Zbl 1131.41304
[27] Lai, M. J., Some sufficient conditions for convexity of multivariate Bernstein-Bézier polynomials and box spline surfaces, Stud. Sci. Math. Hung., 28, 363-374 (1993) · Zbl 0803.41012
[28] Lai, M. J., Convex preserving scattered data interpolation using bivariate \(C^1\) cubic splines, J. Comput. Appl. Math., 119, 249-258 (2000) · Zbl 0966.65016
[29] Lai, M. J.; Schumaker, L. L., Spline Functions on Triangulations (2007), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1185.41001
[30] Leung, N. K.; Renka, R. J., \(C^1\) convexity-preserving interpolation of scattered data, SIAM J. Sci. Comput., 20, 1732-1752 (1999) · Zbl 0942.65016
[31] Li, A., Convexity preserving interpolation, Comput. Aided Geom. Design, 16, 127-147 (1999) · Zbl 0909.68183
[32] Liu, Z.; Tan, J.; Chen, X.; Zhang, L., The conditions of convexity for Bernstein-Bézier surfaces over triangles, Comput. Aided Geom. Design, 27, 421-427 (2010) · Zbl 1210.65043
[33] Lorente-Pardo, J.; Sablonnière, P.; Serrano-Pérez, M. C., On the convexity of Powell-Sabin finite elements, (Chen, Z.; Li, Y.; Micchelli, C.; Xu, Y., Advances in Computational Mathematics (1998), Marcel Dekker: Marcel Dekker New York), 395-404 · Zbl 0931.65009
[34] Lorente-Pardo, J.; Sablonnière, P.; Serrano-Pérez, M. C., On the convexity of \(C^1\) surfaces associated with some quadrilateral finite elements, Adv. Comp. Math., 13, 271-292 (2000) · Zbl 0956.65010
[35] Lorente-Pardo, J.; Sablonnière, P.; Serrano-Pérez, M. C., On the convexity of Bézier nets of quadratic Powell-Sabin splines on 12-fold refined triangulations, J. Comput. Appl. Math., 115, 383-396 (2000) · Zbl 0947.65018
[36] Sauer, T., Multivariate Bernstein polynomials and convexity, Comput. Aided Geom. Design, 8, 465-478 (1991) · Zbl 0756.41029
[37] Schumaker, L. L., Computing bivariate splines in scattered data fitting and the finite-element method, Numer. Algorithms, 48, 237-260 (2008) · Zbl 1146.65019
[38] Seidel, H. P., An introduction to polar forms, IEEE Comp. Graph. Appl., 13, 38-46 (1993)
[39] Wang, Z. B.; Liu, Q. M., An improved condition for the convexity and positivity of Bernstein-Bézier surfaces over triangles, Comput. Aided Geom. Design, 5, 269-275 (1988) · Zbl 0714.41010
[40] Willemans, K.; Dierckx, P., Surface fitting using convex Powell-Sabin splines, J. Comput. Appl. Math., 56, 263-282 (1994) · Zbl 0827.65017
[41] Zheng, J. J., The convexity of parametric Bézier triangular patches of degree 2, Comput. Aided Geom. Design, 10, 521-530 (1993) · Zbl 0794.65011
[42] Zhou, C. Z., On the convexity of parametric Bézier triangular surfaces, Comput. Aided Geom. Design, 7, 459-463 (1990) · Zbl 0717.41022
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.