×

Computing intersection and self-intersection loci of parametrized surfaces using regular systems and Gröbner bases. (English) Zbl 1247.65022

The authors present two general and efficient methods for determining intersection and self-intersection loci of rationally parametrized surfaces.
One of the methods, based on regular systems, is capable to compute the exact parametric loci of intersection and self-intersection. The other, based on Gröbner bases, can compute the minimal varieties passing through the exact parametric loci.
The relation between the results computed by the two methods is established and algorithms for computing parametric loci of intersection and self-intersection are described. Experimental results and comparisons with some existing methods show that our algorithms have a good performance.

MSC:

65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
13P10 Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)

Software:

CASA; Epsilon
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abdel-Malek, K.; Yeh, H. J., On the determination of starting points for parametric surface intersection, Computer-Aided Design, 29, 21-35 (1997)
[2] 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
[3] Buchberger, B., Gröbner bases: an algorithmic method in polynomial ideal theory, (Bose, N. K., Multidimensional Systems Theory (1985), Reidel: Reidel Dordrecht), 184-232 · Zbl 0587.13009
[4] Busé, L.; Elkadi, M.; Galligo, A., Intersection and self-intersection of surfaces by means of Bezoutian matrices, Computer Aided Geometric Design, 25, 53-68 (2008) · Zbl 1172.14346
[5] Chen, F.; Cox, D.; Liu, Y., The \(μ\)-basis and implicitization of a rational parametric surface, Journal of Symbolic Computation, 39, 689-706 (2005) · Zbl 1120.14054
[6] Coffman, A.; Schwartz, A. J.; Stanton, C., The algebra and geometry of Steiner and other quadratically parametrizable surfaces, Computer-Aided Design, 13, 257-286 (1996) · Zbl 0875.68860
[7] Cox, D.; Little, J.; OʼShea, D., Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra (1997), Springer: Springer New York
[8] Elber, G.; Grandine, T. A.; Kim, M. S., Surface self-intersection computation via algebraic decomposition, Computer-Aided Design, 41, 1060-1066 (2009)
[9] Elkadi, M.; Galligo, A.; Lê, T. H., Parametrized surfaces in \(P^3\) of bidegree \((1, 2)\), (Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSACʼ04. Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSACʼ04, Santander, Spain, July 4-7, 2004 (2004), ACM Press: ACM Press New York), 141-148 · Zbl 1134.14316
[10] Farin, G., Curves and Surfaces for Computer Aided Geometric Design: A Practical Guide (1992), Academic Press Inc.: Academic Press Inc. Boston, MA
[11] Fioravanti, M.; Gonzalez-Vega, L.; Necula, I., Computing the intersection of two ruled surfaces by using a new algebraic approach, Journal of Symbolic Computation, 41, 1187-1205 (2006) · Zbl 1124.65022
[12] Fulton, W., Algebraic Curves: An Introduction to Algebraic Geometry (1989), Addison-Wesley: Addison-Wesley Redwood City, CA · Zbl 0681.14011
[13] Galligo, A.; Pavone, J. P., Selfintersections of a Bézier bicubic surface, (Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSACʼ05. Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSACʼ05, Beijing, China, July 24-27, 2005 (2005), ACM Press: ACM Press New York), 148-155 · Zbl 1360.65064
[14] Galligo, A.; Pavone, J. P., A sampling algorithm computing self-intersection of parametric surface, (Algebraic Geometry and Geometric Modeling (2006), Springer: Springer Berlin Heidelberg), 185-204 · Zbl 1107.65310
[15] Galligo, A.; Stillman, M., On the geometry of parametrized bicubic surfaces, Journal of Symbolic Computation, 42, 136-158 (2007) · Zbl 1141.65014
[16] Gonzalez-Vega, L., Implicitization of parametric curves and surfaces by using multidimensional Newton formulae, Journal of Symbolic Computation, 23, 137-151 (1997) · Zbl 0872.68192
[17] Grandine, T. A.; Klein, F. W., A new approach to the surface intersection problem, Computer Aided Geometric Design, 14, 111-134 (1997) · Zbl 0906.68151
[18] Hartshorne, R., Algebraic Geometry (1977), Springer: Springer New York · Zbl 0367.14001
[19] Heo, H. S.; Kim, M. S.; Elber, G., The intersection of two ruled surfaces, Computer-Aided Design, 31, 33-50 (1999) · Zbl 1054.68747
[20] Hoffmann, C. M., Geometric and Solid Modeling (1989), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA
[21] Huang, Y.; Wang, D., Computing self-intersection loci of parametrized surfaces using regular systems and Gröbner bases, (Proceedings of the 11th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC. Proceedings of the 11th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC, Timişoara, Romania, September 26-29, 2009 (2009), IEEE Computer Society: IEEE Computer Society Los Alamitos, CA), 28-36
[22] Hur, S.; Oh, M. J.; Kim, T. W., Approximation of surface-to-surface intersection curves within a prescribed error bound satisfying \(G^2\) continuity, Computer-Aided Design, 41, 37-46 (2009)
[23] Jia, X.; Chen, F.; Deng, J., Computing self-intersection curves of rational ruled surfaces, Computer Aided Geometric Design, 26, 287-299 (2009) · Zbl 1205.65119
[24] Krishnan, S.; Manocha, D., An efficient surface intersection algorithm based on lower-dimensional formulation, ACM Transactions on Graphics, 16, 74-106 (1997)
[25] Lasser, D., 1988. Self-intersections of parametric surfaces. In: Proceedings of the Third International Conference on Engineering Graphics and Descriptive Geometry, Vol. 1, Vienna, Austria, July 11-16, 1988, pp. 312-321.; Lasser, D., 1988. Self-intersections of parametric surfaces. In: Proceedings of the Third International Conference on Engineering Graphics and Descriptive Geometry, Vol. 1, Vienna, Austria, July 11-16, 1988, pp. 312-321.
[26] Li, X.; Jiang, H.; Chen, S.; Wang, X., An efficient surface-surface intersection algorithm based on geometry characteristics, Computers and Graphics, 28, 527-537 (2004)
[27] Mullenheim, G., On determining start points for a surface/surface intersection algorithm, Computer Aided Geometric Design, 8, 401-408 (1991) · Zbl 0742.65106
[28] Patrikalakis, N. M., Surface-to-surface intersections, IEEE Computer Graphics and Applications, 13, 89-95 (1993)
[29] Patrikalakis, N. M.; Maekawa, T., Intersection problems, (Farin, G.; Hoschek, J.; Kim, M. S., Handbook of Computer Aided Geometric Design (2002), North-Holland: North-Holland Amsterdam), 623-649
[30] Pekerman, D.; Elber, G.; Kim, M. S., Self-intersection detection and elimination in freeform curves and surfaces, Computer-Aided Design, 40, 150-159 (2008) · Zbl 1206.65104
[31] Sendra, J. R.; Winkler, F.; Pérez-Díaz, S., Rational Algebraic Curves: A Computer Algebra Approach (2008), Springer: Springer Berlin · Zbl 1129.14083
[32] Thomassen, J. B., Self-intersection problems and approximate implicitization, (Computational Methods for Algebraic Spline Surfaces (2005), Springer: Springer Berlin), 155-170 · Zbl 1065.65041
[33] Wang, D., Computing triangular systems and regular systems, Journal of Symbolic Computation, 30, 221-236 (2000) · Zbl 1007.65039
[34] Wang, D., Elimination Methods (2001), Springer: Springer Wien, New York · Zbl 0964.13014
[35] Wang, D., Elimination Practice: Software Tools and Applications (2004), Imperial College Press: Imperial College Press London · Zbl 1099.13047
[36] Wang, D., Implicitization and offsetting via regular systems, (Chen, F.; Wang, D., Geometric Computation (2004), World Scientific Publ. Co.: World Scientific Publ. Co. Singapore), 156-176 · Zbl 1082.65514
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.