×

A new method of evaluating compact geometric bounds for use in subdivision algorithms. (English) Zbl 0742.65011

A major problem in computer graphics methods depending on search or bisection is the construction of a box containing a curve or surface. The authors describe a new method giving smaller boxes than most other methods, based on the following estimate for an \(n\)-th degree polynomial \(f(u)\) on \([0,1]\) evaluated at points \(u_ i\): \[ (n+1)^{-1/2}[\sum^ n_{i=0}f^ 2(u_ i)]^{1/2}\leq \max_{0\leq u\leq 1}| f(u)| \leq C[\sum^ n_{i=0}f^ 2(u_ i)]^{1/2} \] where \(C\) is a function of the \(u_ i\) alone, evaluated on the coefficients of the Lagrange interpolation formula. A proper choice of the \(u_ i\) will give a minimum of \(C\) (determined in the paper for \(n\leq 9\)). The estimate can then be extended to multivariate polynomials and splines and applied to the maximal distance from lines and planes and therefore to the construction of boxes and subdivision algorithms.

MSC:

65D17 Computer-aided design (modeling of curves and surfaces)
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Barnhill, R. E.; Kersey, S. N., A marching method for parametric surface/surface intersection, Computer Aided Geometric Design, 7, 257-280 (1990) · Zbl 0716.65013
[2] Bartels, R.; Beatty, J.; Barsky, B., An Introduction to Splines for use in Computer Graphics and Geometric Modelling (1987), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA
[3] Boehm, W.; Farin, G.; Kahmann, J., A survey of curve and surface methods in CAGD, Computer Aided Geometric Design, 1, 1, 1-60 (1984) · Zbl 0604.65005
[4] Cargo, G. T.; Shisha, O., The Bernstein form of a polynomial, J. Res. Nat. Bur. Stand. 70B, 79-81 (1966) · Zbl 0139.10003
[5] Chuang, J. H.; Hoffmann, C. M., On local implicit approximation and its applications, ACM Trans. Graphics, 8, 4, 298-324 (1989) · Zbl 0746.68091
[6] Cohen, E.; Lyche, T.; Riesenfeld, R., Discrete B-Splines and subdivision techniques in computer-aided geometric design and computer graphics, Computer Graphics and Image Processing, 14, 2, 87-111 (1980)
[7] de Boor, C., A Practical Guide to Splines (1978), Springer: Springer New York · Zbl 0406.41003
[8] Farin, G., Curves and Surfaces for Computer Aided Geometric Design - A Practical Guide (1988), Academic Press: Academic Press New York · Zbl 0694.68004
[9] Faux, I. D.; Pratt, M. J., Computational Geometry for Design and Manufacture (1979), Ellis Horwood: Ellis Horwood Chichester, UK · Zbl 0395.51001
[10] Filip, D.; Magedson, R.; Markot, R., Surface algorithms using bounds on derivatives, Computer Aided Geometric Design, 3, 4, 295-311 (1986) · Zbl 0632.65013
[11] Houghton, E. G.; Emnett, R. F.; Factor, J. D.; Sabharwal, C. L., Implementation of a divide-and-conquer method for intersection of parametric surfaces, Computer Aided Geometric Design, 2, 173-183 (1985) · Zbl 0613.65143
[12] IEEE CG & A., IEEE Computer Graphics & Appl., Special Issue on Graphics Super Workstations, 9, 4 (1989)
[13] Lane, J. M.; Riesenfeld, R. F., Bounds on a polynomial, BIT 21, 112-117 (1981)
[14] Moore, R. E., Interval Analysis (1966), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0176.13301
[15] Mudur, S. P.; Koparkar, P. A., Interval methods for processing geometric objects, IEEE Computer Graphics & Appl., 4, 2, 7-17 (1984) · Zbl 0601.65094
[16] Pratt, M. J.; Geisow, A. D., Surface/surface intersection problems, (Gregory, J. A., The Mathematics of Surfaces (1986), Oxford University Press: Oxford University Press Oxford)
[17] Ratschek, H.; Rokne, J., Computer Methods for the Range of Functions (1984), Ellis Horwood: Ellis Horwood Chichester, UK · Zbl 0584.65019
[18] Rivlin, T. J., Bounds on a polynomial, J. Res. Nat. Bur. Stand., 74B, 47-54 (1970) · Zbl 0197.34704
[19] Sederberg, T. W.; Parry, S. R., Comparison of three curve intersection algorithms, Computer Aided Design, 18, 1, 58-63 (1986)
[20] Sederberg, T. W.; White, S. C.; Zundel, A. K., Fat arcs: a bounding region with cubic convergence, Computer Aided Geometric Design, 6, 3, 205-218 (1989) · Zbl 0676.65010
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.