×

Enhancing Levin’s method for computing quadric-surface intersections. (English) Zbl 1069.65570

Summary: Levin’s method produces a parameterization of the intersection curve of two quadrics in the form
\[ p(u)=a(u)\pm d(u)\sqrt{s/(u)} \]
where \(a(u)\) and \(d(u)\) are vector valued polynomials, and \(s(u)\) is a quartic polynomial. This method, however, is incapable of classifying the morphology of the intersection curve, in terms of reducibility, singularity, and the number of connected components, which is a critical structural information required by solid modeling applications. We study the theoretical foundation of Levin’s method, as well as the parameterization \(p(u)\) it produces. The following contributions are presented in this paper: (1) It is shown how the roots of \(s(u)\) can be used to classify the morphology of an irreducible intersection curve of two quadric surfaces. (2) An enhanced version of Levin’s method is proposed that, besides classifying the morphology of the intersection curve of two quadrics, produces a rational parameterization of the curve if the curve is singular. (3) A simple geometric proof is given for the existence of a real ruled quadric in any quadric pencil, which is the key result on which Levin’s method is based. These results enhance the capability of Levin’s method in processing the intersection curve of two general quadrics within its own self-contained framework.

MSC:

65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
14Q05 Computational aspects of algebraic curves
65D17 Computer-aided design (modeling of curves and surfaces)
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68U07 Computer science aspects of computer-aided design
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abhyankar, S. S.; Bajaj, C., Automatic parameterization of rational curves and surfaces III: Algebraic space curves, ACM Trans. Graph., 8, 4, 325-334 (1989) · Zbl 0746.68104
[2] Baker, H. F., Principle of Geometry, Vol. III (1923), Cambridge Press
[3] Bix, R., Conics and Cubics—A Concrete Introduction to Algebraic Curves (1998), Springer: Springer New York · Zbl 0906.51001
[4] Bromwich, T. J., Quadratic forms and their classification by means of invariant-factors, Cambridge Tracts in Mathematics and Mathematical Physics, 3, 1906 (1906) · JFM 37.0134.01
[5] Dickson, L. E., Elementary Theory of Equations (1914), Wiley: Wiley New York · Zbl 0027.29502
[6] Farouki, R. T.; Neff, C. A.; O’Connor, M. A., Automatic parsing of degenerate quadric-surface intersections, ACM Trans. Graph., 8, 3, 174-203 (1989) · Zbl 0746.68093
[7] Garrity, T.; Warren, J., On computing the intersection of a pair of algebraic surfaces, Computer Aided Geometric Design, 6, 2, 132-153 (1989) · Zbl 0699.65012
[8] Levin, J. Z., A parametric algorithm for drawing pictures of solid objects composed of quadrics, Comm. ACM, 19, 10, 555-563 (1976) · Zbl 0334.68050
[9] Levin, J. Z., Mathematical models for determining the intersections of quadric surfaces, Comput. Graph. Image Process., 1, 73-87 (1978)
[10] Miller, J. R., Geometric approaches to nonplanar quadric surface intersection curves, ACM Trans. Graph., 6, 274-307 (1987)
[11] Miller, J. R.; Goldman, R. N., Geometric algorithms for detecting and calculating all conics sections in the intersection of any two natural quadric surfaces, Graphical Models and Image Processing, 57, 1, 55-66 (1995)
[12] Ocken, S.; Schwartz, J. T.; Sharir, M., Precise implementation of CAD primitives using rational parameterizations of standard surfaces, (Schwartz; Hopcroft; Sharir, Planning, Geometry, and Complexity of Robot Motion (1987), Ablex), 245-266
[13] Piegl, L., Geometric method of intersecting natural quadrics represented in trimmed surface form, Computer-Aided Design, 21, 4, 201-212 (1989) · Zbl 0673.65007
[14] Pottmann, H.; Wallner, J., Computational Line Geometry (2001), Springer: Springer Berlin · Zbl 1006.51015
[15] Salmon, G., Higher Plane Curves (1934), Stechert: Stechert New York
[16] Sarraga, R. F., Algebraic methods for intersections of quadric surfaces in GMSOLID, Computer Vision, Graphics and Image Processing, 22, 2, 222-238 (1983)
[17] Semple, G. J.; Kneebone, G. K., Algebraic Projective Geometry (1952), Oxford University Press: Oxford University Press London · Zbl 0046.38103
[18] Shene, C. H.; Johnstone, J. K., On the lower degree intersections of two natural quadrics, ACM Trans. Graph., 13, 4, 400-424 (1994)
[19] Sommerville, D. M.Y., Analytical Geometry of Three Dimensions (1947), Cambridge University Press · Zbl 0008.40203
[20] Tu, C. H.; Wang, W.; Wang, J. Y., Classifying the morphology of the nonsingular intersection curves of two quadric surfaces, (Proceedings of Geometric Modeling and Processing 2002 (2002)), 23-32
[21] Uspensky, J. V., Theory of Equations (1948), McGraw-Hill: McGraw-Hill New York · Zbl 0005.11104
[22] Wang, W.; Joe, B.; Goldman, R. N., Rational quadratic parameterizations of quadrics, Internat. J. Comput. Geom. Appl., 7, 6, 599-619 (1997) · Zbl 0887.68109
[23] Wang, W.; Joe, B.; Goldman, R., Computing quadric surface intersections based on an analysis of plane cubic curves, Graphical Models, 64, 6, 335-367 (2002) · Zbl 1055.68133
[24] Wilf, I.; Manor, Y., Quadric surface intersection: shape and structure, Computer-Aided Design, 25, 10, 633-643 (1993) · Zbl 0794.65102
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.