3 ms·

Bézier Curves and Surfaces: The Utah Teapot

95 points by jacobedawson 8y ago

royjacobs 8y ago
If you're ever in Palo Alto I can recommend a visit to the Computer History Museum. I was there a few years ago and got a selfie with the original Utah teapot.
jacobolus 8y ago
> Contrary to intuition maybe, the De Casteljau method is actually more expensive than evaluating the Bernstein polynomials directly Both of these proposed methods are O(n^2). Polynomial evaluation can be done in O(n) in many other choices of basis. Starting from Bernstein basis one faster evaluation method with apparently decent numerical stability is to take an inverse discrete Fourier transform using O(n log n), then evaluate from the resulting basis in linear time, https://doi.org/10.1016/j.amc.2013.05.079 https://doi.org/10.1016/j.amc.2013.05.079 But it’s also pretty reasonable to convert to some other basis [e.g. Chebyshev basis] in O(n^2) and then evaluate from there in O(n). [For n = 4 this might not matter so much.] I’m skeptical that finding the derivatives and then using the proposed forward difference method https://www.scratchapixel.com/lessons/advanced-rendering/bezier-curve-rendering-utah-teapot/fast-forward-differencing https://www.scratchapixel.com/lessons/advanced-rendering/bez... is a practical way to evaluate a polynomial in Bernstein basis at a large number of equispaced points in 2019. It might have made sense a few decades ago when multiplication was substantially more expensive than multiplication. Nowadays floating point multiplication is very fast.
- aidenn0 8y ago
  Of course rendering curves is expensive. It's the law of spline demand.
  - kayamon 8y ago
    ಠ_ಠ
peter_d_sherman 8y ago
Before reading this article, I thought I knew everything about Bezier curves... After reading this article, I now know that I really didn't know anything about Bezier curves! Great article!
peterkelly 8y ago
Another great resource on Bézier curves: https://pomax.github.io/bezierinfo/ https://pomax.github.io/bezierinfo/
Const-me 8y ago
I once used single bicubic Bezier patch to software compensate for optical distortion. Worked quite well, better than my previous attempts. Before that I made user mark optical center (in my hardware usually quite far from picture center) and edit radial distortion function. That’s when I learned these details about Bezier patches. I needed to calculate them a lot, in pixel shader that distorts some images, in vertex shaders for calibration grid, and in a few other places, that’s a complex product with my software running both on PC and embedded.

95 points by jacobedawson 8y ago

If you're ever in Palo Alto I can recommend a visit to the Computer History Museum. I was there a few years ago and got a selfie with the original Utah teapot.

jacobolus 8y ago

> Contrary to intuition maybe, the De Casteljau method is actually more expensive than evaluating the Bernstein polynomials directly Both of these proposed methods are O(n^2). Polynomial evaluation can be done in O(n) in many other choices of basis. Starting from Bernstein basis one faster evaluation method with apparently decent numerical stability is to take an inverse discrete Fourier transform using O(n log n), then evaluate from the resulting basis in linear time, https://doi.org/10.1016/j.amc.2013.05.079 https://doi.org/10.1016/j.amc.2013.05.079 But it’s also pretty reasonable to convert to some other basis [e.g. Chebyshev basis] in O(n^2) and then evaluate from there in O(n). [For n = 4 this might not matter so much.] I’m skeptical that finding the derivatives and then using the proposed forward difference method https://www.scratchapixel.com/lessons/advanced-rendering/bezier-curve-rendering-utah-teapot/fast-forward-differencing https://www.scratchapixel.com/lessons/advanced-rendering/bez... is a practical way to evaluate a polynomial in Bernstein basis at a large number of equispaced points in 2019. It might have made sense a few decades ago when multiplication was substantially more expensive than multiplication. Nowadays floating point multiplication is very fast.

aidenn0 8y ago
Of course rendering curves is expensive. It's the law of spline demand.
- kayamon 8y ago
  ಠ_ಠ

peter_d_sherman 8y ago

Before reading this article, I thought I knew everything about Bezier curves... After reading this article, I now know that I really didn't know anything about Bezier curves! Great article!

peterkelly 8y ago

Another great resource on Bézier curves: https://pomax.github.io/bezierinfo/ https://pomax.github.io/bezierinfo/

Const-me 8y ago

I once used single bicubic Bezier patch to software compensate for optical distortion. Worked quite well, better than my previous attempts. Before that I made user mark optical center (in my hardware usually quite far from picture center) and edit radial distortion function. That’s when I learned these details about Bezier patches. I needed to calculate them a lot, in pixel shader that distorts some images, in vertex shaders for calibration grid, and in a few other places, that’s a complex product with my software running both on PC and embedded.