“Implicitizing Rational Tensor Product Surfaces Using the Resultant of Three Moving Planes” by Shen and Goldman

  • ©

Conference:


Type(s):


Title:

    Implicitizing Rational Tensor Product Surfaces Using the Resultant of Three Moving Planes

Session/Category Title:   An Immersion in Computational Geometry

Presenter(s)/Author(s):


Abstract:


    Implicitizing rational surfaces is a fundamental computational task in Computer Graphics and Computer Aided Design. Ray tracing, collision detection, and solid modeling all benefit from implicitization procedures for rational surfaces. The univariate resultant of two moving lines generated by a μ-basis for a rational curve represents the implicit equation of the rational curve. But although the multivariate resultant of three moving planes corresponding to a μ-basis for a rational surface is guaranteed to contain the implicit equation of the surface as a factor, μ-bases for rational surfaces are difficult to compute. Moreover, μ-bases for a rational surface often have high degrees, so these resultants generally contain many extraneous factors. Here we develop fast algorithms to implicitize rational tensor product surfaces by computing the resultant of three moving planes corresponding to three syzygies with low degrees. These syzygies are easy to compute, and the resultants of the corresponding moving planes generally contain fewer extraneous factors than the resultants of the moving planes corresponding to μ-bases. We predict and compute all the possible extraneous factors that may appear in these resultants. Examples are provided to clarify and illuminate the theory.

References:


    1. William A. Adkins, J. William Hoffman, and Hao Hao Wang. 2005. Equations of parametric surfaces with base points via syzygies. Journal of Symbolic Computation 39, 1 (2005), 73–101. DOI:http://dx.doi.org/10.1016/j.jsc.2004.09.007 Google ScholarDigital Library
    2. B. Buchberger. 1985. Groebner-bases: An algorithmic method in polynomial ideal theory. In Multidimensional Systems Theory—Progress, Directions and Open Problems in Multidimensional Systems, N. K. Bose (Ed.). Reidel Publishing Company, Dordrecht, Chapter 6, 184–232. (Second edition: N. K. Bose (Ed.), Multidimensional Systems Theory and Application, Kluwer Academic Publisher, 2003, pp. 89–128).Google Scholar
    3. Laurent Busé. 2014. Implicit matrix representations of rational Bézier curves and surfaces. Computer-Aided Design 46 (2014), 14–24. DOI:http://dx.doi.org/10.1016/j.cad.2013.08.014. Google ScholarDigital Library
    4. Laurent Busé, Marc Chardin, and Jean-Pierre Jouanolou. 2009. Torsion of the symmetric algebra and implicitization. Proceedings of the American Mathematical Society 137, 6 (2009), 1855–1865. Google ScholarCross Ref
    5. Laurent Busé, David A. Cox, and Carlos D’andrea. 2003. Implicitization of surfaces in P3 in the presence of base points. Journal of Algebra and Its Applications 2, 2 (2003), 189–214. Google ScholarCross Ref
    6. Falai Chen, David A. Cox, and Yang Liu. 2005. The μ-basis and implicitization of a rational parametric surface. Journal of Symbolic Computation 39, 6 (2005), 689–706. DOI:http://dx.doi.org/10.1016/j.jsc.2005.01.003 Google ScholarDigital Library
    7. Falai Chen and Wenping Wang. 2002. The μ-basis of a planar rational curve-Properties and computation. Graphical Models 64, 6 (2002), 368–381. DOI:http://dx.doi.org/10.1016/S1077-3169(02)00017-5 Google ScholarDigital Library
    8. Falai Chen, Jianmin Zheng, and Thomas W. Sederberg. 2001. The μ-basis of a rational ruled surface. Computer Aided Geometric Design 18, 1 (2001), 61–72. DOI:http://dx.doi.org/10.1016/S0167-8396(01)00012-7 Google ScholarDigital Library
    9. Eng-Wee Chionh, Ming Zhang, and Ron Goldman. 2002. Fast computation of the Bezout and Dixon resultant matrices. Journal of Symbolic Computation 33, 1 (2002), 13–29. DOI:http://dx.doi.org/10.1006/jsco.2001.0462 Google ScholarDigital Library
    10. David A. Cox. 2001. Equations of parametric curves and surfaces via syzygies. In Symbolic Computation: Solving Equations in Algebra, Geometry, and Engineering, Vol. 286. AMS, Providence, RI, Contemporary Mathematics, 1–20. DOI:http://dx.doi.org/10.1090/conm/286/0475Google Scholar
    11. David A. Cox. 2004. Curves, surfaces and syzygies. In Algebraic Geometry and Geometric Modeling, Vol. 334. AMS, Providence, RI, Contemporary Mathematics, 131–150. DOI:http://dx.doi.org/10.1090/conm/334Google Scholar
    12. David A. Cox, John B. Little, and Donal O’Shea. 1998. Using Algebraic Geometry. Springer, New York. http://opac.inria.fr/record=b1094391 Google ScholarCross Ref
    13. David A. Cox, John B. Little, and Donal O’Shea. 2015. Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra (4th ed.). Springer. Google ScholarCross Ref
    14. Carlos D’Andrea. 2002. Macaulay style formulas for sparse resultants. Transactions of the American Mathematical Society 354, 7 (2002), 2595–2629. DOI:https://doi.org/10.1090/S0002-9947-02-02910-0Google ScholarCross Ref
    15. Carlos D’Andrea and Ioannis Z. Emiris. 2003. Sparse resultant perturbations. In Algebra, Geometry and Software Systems, Michael Joswig and Nobuki Takayama (Eds.). Springer, Berlin, 93–107. DOI:http://dx.doi.org/10.1007/978-3-662-05148-1_5 Google ScholarCross Ref
    16. Jiansong Deng, Falai Chen, and Liyong Shen. 2005. Computing μ-bases of rational curves and surfaces using polynomial matrix factorization. In Proceedings of the 2005 International Symposium on Symbolic and Algebraic Computation (ISSAC’05). ACM, New York, 132–139. DOI:http://dx.doi.org/10.1145/1073884.1073904 Google ScholarDigital Library
    17. Alicia Dickenstein and Ioannis Z. Emiris. 2003. Multihomogeneous resultant formulae by means of complexes. Journal of Symbolic Computation 36, 3–4 (2003), 317–342. DOI:http://dx.doi.org/10.1016/S0747-7171(03)00086-5 ISSAC 2002. Google ScholarDigital Library
    18. Ioannis Z. Emiris and Ilias Kotsireas. 2005. Implicitization exploiting sparseness. In Geometric and Algorithmic Aspects of Computer-Aided Design and Manufacturing, R. Janardan D. Dutta, and M. Smid (Eds.). American Mathematical Society, Providence, RI, 281–298. Google ScholarCross Ref
    19. Ioannis Z. Emiris and Angelos Mantzaflaris. 2012. Multihomogeneous resultant formulae for systems with scaled support. Journal of Symbolic Computation 47, 7 (2012), 820–842. DOI:http://dx.doi.org/10.1016/j.jsc.2011.12.010 Google ScholarDigital Library
    20. Izrail Moiseevitch Gelfand, Mikhail M. Kapranov, and Andrei V. Zelevinsky. 1994. Discriminants, Resultants, and Multidimensional Determinants. Birkhäuser, Boston. Google ScholarCross Ref
    21. Dinesh Manocha and John Canny. 1991. Efficient techniques for multipolynomial resultant algorithms. In Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation (ISSAC’91). ACM, New York, 86–95. DOI:http://dx.doi.org/10.1145/120694.120706 Google ScholarDigital Library
    22. Dinesh Manocha and John F. Canny. 1992. Algorithm for implicitizing rational parametric surfaces. Computer Aided Geometric Design 9, 1 (1992), 25–50. DOI:http://dx.doi.org/10.1016/0167-8396(92)90051-P Google ScholarDigital Library
    23. Thomas W. Sederberg and Falai Chen. 1995. Implicitization using moving curves and surfaces. In Proceedings of the 22nd Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH’95). ACM, New York, 301–308. DOI:http://dx.doi.org/10.1145/218380.218460 Google ScholarDigital Library
    24. Li-Yong Shen. 2016. Computing μ-bases from algebraic ruled surfaces. Computer Aided Geometric Design 46 (2016), 125–130. DOI:http://dx.doi.org/10.1016/j.cagd.2016.07.001 Google ScholarDigital Library
    25. Li-Yong Shen and Ron Goldman. 2017a. Algorithms for computing strong μ-bases for rational tensor product surfaces. Computer Aided Geometric Design 52–53 (2017), 48–62. DOI:http://dx.doi.org/https://doi.org/10.1016/j.cagd.2017.03.001. Geometric Modeling and Processing 2017.Google Scholar
    26. Li-Yong Shen and Ron Goldman. 2017b. Strong μ-bases for rational tensor product surfaces and extraneous factors associated to bad base points and anomalies at infinity. SIAM Journal on Applied Algebra and Geometry 1, 1 (2017), 328–351. DOI:https://doi.org/10.1137/16M1091952.Google ScholarCross Ref
    27. Li-Yong Shen and Chun-Ming Yuan. 2010. Implicitization using univariate resultants. Journal of Systems Science and Complexity 23, 4 (2010), 804–814. DOI:http://dx.doi.org/10.1007/s11424-010-7218-6 Google ScholarCross Ref
    28. Xiaoran Shi, Xiaohong Jia, and Ron Goldman. 2013. Using a bihomogeneous resultant to find the singularities of rational space curves. Journal of Symbolic Computation 53 (2013), 1–25. DOI:http://dx.doi.org/10.1016/j.jsc.2012.09.005 Google ScholarDigital Library
    29. Xiaoran Shi, Xuhui Wang, and Ron Goldman. 2012. Using μ-bases to implicitize rational surfaces with a pair of orthogonal directrices. Computer Aided Geometric Design 29, 7 (2012), 541–554. DOI:http://dx.doi.org/10.1016/j.cagd.2012.03.026. Google ScholarDigital Library
    30. Jianmin Zheng, Thomas W. Sederberg, Eng-Wee Chionh, and David A Cox. 2003. Implicitizing rational surfaces with base points using the method of moving surfaces. In Topics in Algebraic Geometry and Geometric Modeling (Workshop on Algebraic Geometry and Geometric Modeling 2002). American Mathematical Society, Providence, RI, 151–168. DOI:http://dx.doi.org/10.1090/conm/334 

ACM Digital Library Publication:


Overview Page: