×
Barrowclough, Oliver J. D.; Dokken, Tor

Approximate implicitization using linear algebra. (English) Zbl 1235.65018

J. Appl. Math. 2012, Article ID 293746, 25 p. (2012).
Summary: We consider a family of algorithms for approximate implicitization of rational parametric curves and surfaces. The main approximation tool in all of the approaches is the singular value decomposition, and they are therefore well suited to floating-point implementation in computer-aided geometric design (CAGD) systems. We unify the approaches under the names of commonly known polynomial basis functions and consider various theoretical and practical aspects of the algorithms. We offer new methods for a least squares approach to approximate implicitization using orthogonal polynomials, which tend to be faster and more numerically stable than some existing algorithms. We propose several simple propositions relating the properties of the polynomial bases to their implicit approximation properties.

Cited in 4 Documents

MSC:

65D17 Computer-aided design (modeling of curves and surfaces)
14Q05 Computational aspects of algebraic curves
14Q10 Computational aspects of algebraic surfaces
15-04 Software, source code, etc. for problems pertaining to linear algebra

Software:

Chebfun; PovRay
PDF BibTeX XML Cite
\textit{O. J. D. Barrowclough} and \textit{T. Dokken}, J. Appl. Math. 2012, Article ID 293746, 25 p. (2012; Zbl 1235.65018)
Full Text: DOI arXiv

References:

[1] T. W. Sederberg and F. Chen, “Implicitization using moving curves and surfaces,” in Proceedings of the 22nd Annual ACM SIGGRAPH Conference on Computer Graphics (SIGGRAPH ’95), pp. 301-308, ACM, New York, NY, USA, 1995.
[2] C. L. Bajaj, I. Ihm, and J. Warren, “Higher-order interpolation and least-squares approximation using implicit algebraic surfaces,” ACM Transactions on Graphics, vol. 12, no. 4, pp. 327-347, 1993. · Zbl 0805.65014
[3] J. H. Chuang and C. M. Hoffmann, “On local implicit approximation and its applications,” ACM Transactions on Graphics, vol. 8, no. 4, pp. 298-324, 1989. · Zbl 0746.68091
[4] R. M. Corless, M. W. Giesbrecht, I. S. Kotsireas, and S. M. Watt, “Numerical implicitization of parametric hypersurfaces with linear algebra,” in Revised Papers from the International Conference on Artificial Intelligence and Symbolic Computation (AISC ’00), vol. 1930, pp. 174-183, Springer, London, UK, 2001. · Zbl 1042.65020
[5] T. Dokken, Aspects of intersection algorithms and approximations, Ph.D. thesis, University of Oslo, 1997. · Zbl 0883.65127
[6] V. Pratt, “Direct least-squares fitting of algebraic surfaces,” SIGGRAPH Computer Graphics, vol. 21, no. 4, pp. 145-152, 1987.
[7] T. Dokken, “Approximate implicitization,” in Mathematical Methods for Curves and Surfaces, pp. 81-102, Vanderbilt University Press, Nashville, Tenn, USA, 2001. · Zbl 0989.65020
[8] T. Dokken and J. B. Thomassen, “Weak approximate implicitization,” in Proceedings of the IEEE International Conference on Shape Modeling and Applications (SMI ’06), p. 31, IEEE Computer Society, Washington, DC, USA, 2006. · Zbl 1039.65012
[9] D. Wang, “A simple method for implicitizing rational curves and surfaces,” Journal of Symbolic Computation, vol. 38, no. 1, pp. 899-914, 2004. · Zbl 1137.65322
[10] T. Dokken, H. K. Kellermann, and C. Tegnander, “An approach to weak approximate implicitization,” in Mathematical Methods for Curves and Surfaces, pp. 103-112, Vanderbilt University Press, Nashville, Tenn, USA, 2001. · Zbl 0989.65020
[11] I. Z. Emiris and I. S. Kotsireas, “Implicitization exploiting sparseness,” in Geometric and Algorithmic Aspects of Computer-Aided Design and Manufacturing, vol. 67 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp. 281-297, American Mathematical Society, Providence, RI, USA, 2005. · Zbl 1272.65018
[12] Z. Battles and L. N. Trefethen, “An extension of MATLAB to continuous functions and operators,” SIAM Journal on Scientific Computing, vol. 25, no. 5, pp. 1743-1770, 2004. · Zbl 1057.65003
[13] B. K. Alpert and V. Rokhlin, “A fast algorithm for the evaluation of Legendre expansions,” SIAM Journal on Scientific and Statistical Computing, vol. 12, pp. 158-179, 1991. · Zbl 0726.65018
[14] A. Gil, J. Segura, and N. M. Temme, Numerical Methods for Special Functions, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, Pa, USA, 1st edition, 2007. · Zbl 1144.65016
[15] O. J. D. Barrowclough and T. Dokken, “Approximate implicitization of triangular Bézier surfaces,” in Proceedings of the 26th Spring Conference on Computer Graphics (SCCG ’10), pp. 133-140, ACM, New York, NY, USA, 2010.
[16] T. D. DeRose, R. N. Goldman, H. Hagen, and S. Mann, “Functional composition algorithms via blossoming,” ACM Transactions on Graphics, vol. 12, no. 2, pp. 113-135, 1993. · Zbl 0771.68100
[17] M. S. Floater and T. Lyche, “Asymptotic convergence of degree-raising,” Advances in Computational Mathematics, vol. 12, no. 2-3, pp. 175-187, 2000. · Zbl 0953.41004
[18] J. Milnor, Singular Points of Complex Hypersurfaces, Annals of Mathematics Studies, Princeton University Press, Princeton, NJ, USA, 1968. · Zbl 0184.48405
[19] R. T. Farouki and T. N. T. Goodman, “On the optimal stability of the Bernstein basis,” Mathematics of Computation, vol. 65, no. 216, pp. 1553-1566, 1996. · Zbl 0853.65051
[20] J. Schicho and I. Szilágyi, “Numerical stability of surface implicitization,” Journal of Symbolic Computation, vol. 40, no. 6, pp. 1291-1301, 2005. · Zbl 1124.65017
[21] T. W. Sederberg, J. Zheng, K. Klimaszewski, and T. Dokken, “Approximate implicitization using monoid curves and surfaces,” Graphical Models and Image Processing, vol. 61, no. 4, pp. 177-198, 1999. · Zbl 05467293
[22] B. Jüttler and A. Felis, “Least-squares fitting of algebraic spline surfaces,” Advances in Computational Mathematics, vol. 17, no. 1-2, pp. 135-152, 2002. · Zbl 0997.65028
[23] J. N. Lyness and R. Cools, “A survey of numerical cubature over triangles,” in Proceedings of Symposia in Applied Mathematics, vol. 48, pp. 127-150, 1994. · Zbl 0820.41026
[24] R. T. Farouki, “Construction of orthogonal bases for polynomials in Bernstein form on triangular and simplex domains,” Computer Aided Geometric Design, vol. 20, no. 4, pp. 209-230, 2003. · Zbl 1069.65517
[25] Persistence of Vision Pty. Ltd. Persistence of vision raytracer (version 3.6), 2004, http://www.povray.org/download/.
[26] C. L. Bajaj and I. Ihm, “Algebraic surface design with Hermite interpolation,” ACM Transactions on Graphics, vol. 11, no. 1, pp. 61-91, 1992. · Zbl 0742.68077
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.