Intersecting quadrics: an efficient and exact implementation
- 作者：Sylvain Lazard ; Luis Mariano Peñ ; aranda and Sylvain Petitjean
- 关键词：Intersection of surfaces ; Quadrics ; Pencils ; Curve parameterization ; Implementation
- 刊名：Computational Geometry
- 出版年：2006
- 期刊代码：18_09257721
- 类别：cp
- 出版时间：August 2006
- 卷：35
- 期：1-2
- 页码：74-99
- 文件大小：440 K
摘要
We present the first complete, exact, and efficient C++ implementation for parameterizing the intersection of two implicit quadrics with integer coefficients of arbitrary size. It is based on the near-optimal algorithm recently introduced by Dupont et al. [L. Dupont, D. Lazard, S. Lazard, S. Petitjean, Near-optimal parameterization of the intersection of quadrics, in: Proc. of SoCG, ACM Symposium on Computational Geometry, San Diego, 2003, pp. 246–255] and builds upon Levin's seminal work [J. Levin, A parametric algorithm for drawing pictures of solid objects composed of quadric surfaces, Comm. ACM 19 (10) (1976) 555–563].
Unlike existing implementations, it correctly identifies and parameterizes all the connected components of the intersection in all cases, returning parameterizations with rational functions whenever such parameterizations exist. In addition, the field of the coefficients of the parameterizations is either of minimal degree or involves one possibly unneeded square root.
We prove upper bounds on the size of the coefficients of the output parameterizations and compare these bounds to observed values. We give other experimental results and present some examples.