Approximate implicitization of triangular Bézier surfaces

ABSTRACT

We discuss how Dokken's methods of approximate implicitization can be applied to triangular Bézier surfaces in both the original and weak forms. The matrices D and M that are fundamental to the respective forms of approximate implicitization are shown to be constructed essentially by repeated multiplication of polynomials and by matrix multiplication. A numerical approach to weak approximate implicitization is also considered and we show that symmetries within this algorithm can be exploited to reduce the computation time of M. Explicit examples are presented to compare the methods and to demonstrate properties of the approximations.

References

1. Bloomenthal, J., and Wyvill, B., Eds. 1997. Introduction to Implicit Surfaces. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA.
2. Dokken, T., and Thomassen, J. B. 2003. Overview of approximate implicitization. In Topics in algebraic geometry and geometric modeling, vol. 334. Amer. Math. Soc., Providence, RI, 169--184.
3. Dokken, T., and Thomassen, J. B. 2006. Weak approximate implicitization. In SMI '06: Proceedings of the IEEE International Conference on Shape Modeling and Applications 2006, IEEE Computer Society, Washington, DC, USA, 31.
4. Dokken, T. 1997. Aspects of intersection algorithms and approximations. PhD thesis, University of Oslo.
5. Dokken, T. 2001. Approximate implicitization. In Mathematical methods for curves and surfaces. Vanderbilt Univ. Press, Nashville, TN, 81--102.
6. Farin, G. 1986. Triangular Berstein-Bézier patches. Comput. Aided Geom. Des. 3, 2, 83--127.
7. Farin, G. 2002. Curves and surfaces for CAGD: a practical guide. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA.
8. Farouki, R. T., Goodman, T. N. T., and Sauer, T. 2003. Construction of orthogonal bases for polynomials in Bernstein form on triangular and simplex domains. Computer Aided Geometric Design 20, 4, 209--230.
9. Hoffman, C. M. 1993. Implicit curves and surfaces in CAGD. IEEE Comput. Graph. Appl. 13, 1, 79--88.
10. Jüttler, B., Chalmovianský, P., Shalaby, M., and Wurm, E. 2005. Approximate algebraic methods for curves and surfaces and their applications. In SCCG '05: Proceedings of the 21st spring conference on Computer graphics, ACM, New York, NY, USA, 13--18.
11. Pratt, V. 1987. Direct least-squares fitting of algebraic surfaces. SIGGRAPH Comput. Graph. 21, 4, 145--152.
12. Reimers, M., and Seland, J. 2008. Ray casting algebraic surfaces using the frustum form. Comput. Graph. Forum 27, 2, 361--370.
13. Sederberg, T. W., and Chen, F. 1995. Implicitization using moving curves and surfaces. In SIGGRAPH 95: Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, ACM, New York, NY, USA, 301--308.
14. Sederberg, T. W., Anderson, D. C., and Goldman, R. N. 1984. Implicit representation of parametric curves and surfaces. Computer Vision, Graphics, and Image Processing 28, 1, 72--84.
15. Sederberg, T. W., Zheng, J., Klimaszewski, K., and Dokken, T. 1999. Approximate implicitization using monoid curves and surfaces. Graphical Models and Image Processing 61, 4, 177--198.
16. Taubin, G. 1991. Estimation of planar curves, surfaces, and nonplanar space curves defined by implicit equations with applications to edge and range image segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 13, 11, 1115--1138.
17. Thomassen, J. B. 2005. Self-intersection problems and approximate implicitization. In Computational Methods for Algebraic Spline Surfaces, Springer Berlin Heidelberg, 155--170.
18. Wurm, E., and Jüttler, B. 2003. Approximate implicitization via curve fitting. In SGP '03: Proceedings of the 2003 Euro-graphics/ACM SIGGRAPH symposium on Geometry processing, Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, 240--247.

Index Terms

• Computing methodologies

  • Computer graphics

    • Shape modeling

• Mathematics of computing

  • Mathematical analysis

    • Functional analysis

      • Approximation

• Theory of computation

  • Design and analysis of algorithms

    • Approximation algorithms analysis

  • Randomness, geometry and discrete structures

    • Computational geometry