“Implicitizing Rational Tensor Product Surfaces Using the Resultant of Three Moving Planes” by Shen and Goldman – ACM SIGGRAPH HISTORY ARCHIVES

“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:


Submit a story:

If you would like to submit a story about this presentation, please contact us: historyarchives@siggraph.org