Helper for Bézier Curves, Triangles, and Higher Order Objects

Summary

bezier is a Python helper for Bézier curves and surfaces (T. W. Sederberg 2016, Farin (2001)). Bézier curves (and surfaces) are parametric curves with polynomial components, but they are expressed in terms of the Bernstein basis rather than the traditional power basis. In addition to being more numerically stable (R. Farouki and Rajan 1987, R. Farouki (1991), R. T. Farouki and Goodman (1996)), this basis allows "intuitive" manipulation of geometric shapes by controlling a set of points rather than via algebraic techniques.

Bézier curves and surfaces have been widely used for decades (Rida T. Farouki 2012) in industrial design (e.g. shape), computer fonts and graphics, mathematics (e.g. isoparametric elements in finite elements), and many other fields.

This library provides support for

  • 2D plotting
  • 2D intersection (via both geometric (T. Sederberg 1989, T. Sederberg and Nishita (1990), Kim, Lee, and Shin (1998), T. W. Sederberg and Parry (1986)) and algebraic (Jónsson and Vavasis 2005, Manocha and Demmel (1992)) algorithms)
  • Curve and surface subdivision (R. T. Farouki and Neff 1990)
  • Degree-elevation and reduction
  • Evaluation of points on curves / surfaces
  • Determining parameters corresponding to a point on a on a curve or on a surface (i.e. the inverse of evaluation)
  • Specialization / reparameterization
  • Self-intersection / singularity check for 2D surfaces

Surface-surface intersection example

References

Farin, Gerald. 2001. Curves and Surfaces for Cagd, Fifth Edition: A Practical Guide (the Morgan Kaufmann Series in Computer Graphics). Morgan Kaufmann. https://www.amazon.com/Curves-Surfaces-CAGD-Fifth-Practical/dp/1558607374.

Farouki, R. T., and T. N. T. Goodman. 1996. “On the Optimal Stability of the Bernstein Basis.” Mathematics of Computation 65 (216). American Mathematical Society (AMS): 1553–67. doi:10.1090/s0025-5718-96-00759-4.

Farouki, R. T., and C. A. Neff. 1990. “On the Numerical Condition of Bernstein-Bézier Subdivision Processes.” Mathematics of Computation 55 (192). JSTOR: 637. doi:10.2307/2008438.

Farouki, R.T. 1991. “On the Stability of Transformations Between Power and Bernstein Polynomial Forms.” Computer Aided Geometric Design 8 (1). Elsevier BV: 29–36. doi:10.1016/0167-8396(91)90047-f.

Farouki, R.T., and V.T. Rajan. 1987. “On the Numerical Condition of Polynomials in Bernstein Form.” Computer Aided Geometric Design 4 (3). Elsevier BV: 191–216. doi:10.1016/0167-8396(87)90012-4.

Farouki, Rida T. 2012. “The Bernstein Polynomial Basis: A Centennial Retrospective.” Computer Aided Geometric Design 29 (6). Elsevier BV: 379–419. doi:10.1016/j.cagd.2012.03.001.

Jónsson, GuđbjörnF., and Stephen A. Vavasis. 2005. “Accurate Solution of Polynomial Equations Using Macaulay Resultant Matrices.” Mathematics of Computation 74 (249). American Mathematical Society: 221–62. https://www.jstor.org/stable/4100244.

Kim, Deok-Soo, Soon-Woong Lee, and Hayong Shin. 1998. “A Cocktail Algorithm for Planar Bézier Curve Intersections.” Computer-Aided Design 30 (13). Elsevier BV: 1047–51. doi:10.1016/s0010-4485(98)00052-9.

Manocha, Dinesh, and James W. Demmel. 1992. “Algorithms for Intersecting Parametric and Algebraic Curves.” UCB/CSD-92-698. EECS Department, University of California, Berkeley. https://www2.eecs.berkeley.edu/Pubs/TechRpts/1992/6266.html.

Sederberg, T.W. 1989. “Algorithm for Algebraic Curve Intersection.” Computer-Aided Design 21 (9). Elsevier BV: 547–54. doi:10.1016/0010-4485(89)90015-8.

Sederberg, T.W., and T. Nishita. 1990. “Curve Intersection Using Bézier Clipping.” Computer-Aided Design 22 (9). Elsevier BV: 538–49. doi:10.1016/0010-4485(90)90039-f.

Sederberg, Thomas W. 2016. “Lecture Notes: Computer Aided Geometric Design.” Department of Computer Science, Brigham Young University. http://tom.cs.byu.edu/~557/text/cagd.pdf.

Sederberg, Thomas W, and Scott R Parry. 1986. “Comparison of Three Curve Intersection Algorithms.” Computer-Aided Design 18 (1). Elsevier BV: 58–63. doi:10.1016/s0010-4485(86)80013-6.