This is very cool, a clever technique to get cubic Bezier evaluation using a single 2D 2x2 bilinear texture sample. (Hi Alan!) I’m not sure I realized that the trilinear diagonal of a cube is a cubic Bezier (but when you say it that way it seems more obvious :P plus it makes sense with control points a,b,c,d you have 1 a, 3 bs and cs, and 1 d - the coefficients of the cubic equation)
The Seiler representation feels in a way similar to Hermite; it’s still a Bezier with the 2 endpoints, and the interior 2 control points use a convenient differential form.
Kind of amazing the perf is as good as using shader code, FMA instructions or whatever. I would make the argument that this is useful even if slower (and it might be on, say, mobile hardware), since you are offloading work to the texture hardware. It’s like adding extra FMA units to the machine.
This makes me wonder if there’s some way to evaluate a quadratic B-spline using a 2D 2x(N+1) texture, sharing a texture edge with the neighbor segment, so the amortized cost of a segment is ~2 texels instead of 4…
Oh also the paper mentions Boehm’s algorithm for converting Bezier to B-spline. Note that if you lookup Boehm’s algorithm it will look crazy complicated, but you can convert the control points of a cubic Bezier to a cubic uniform B-spline with a single matrix-matrix multiply. This is true for converting to/from Catmull-Rom as well, plus I think any type that’s cubic polynomial. You lose the vertex sharing, but that’s already gone with texture sampling - so this paper will automatically work on any polynomial curves, not just Bezier.
I never heard of the Seiler interpolation algorithm mentioned in the paper before, but the way it uses extra additions and subtractions up-front to turn six interpolations into only three reminds me a bit of the Karatsuba algorithm for multiplication[0]. I wonder if that was an inspiration for it?
Also makes me wonder if this will have uses outside of graphics? Bézier curves are used in other contexts too, aren't they?
> Yuksel [2024] explained how Seiler interpolation can be used to evaluate polynomial curves, including B´ezier curves, and noted that GPU linear interpolation could be used for the initial linear interpolation steps, with the remaining interpolations done in shader code.
> In this paper, we present the details of evaluating Bézier curves using hardware-accelerated linear texture interpolation and show how to perform all interpolations on the hardware, using both the de Casteljau algorithm and Seiler interpolation. We also compare performance and accuracy against curves evaluated as polynomials in shader code.
This is very cool, a clever technique to get cubic Bezier evaluation using a single 2D 2x2 bilinear texture sample. (Hi Alan!) I’m not sure I realized that the trilinear diagonal of a cube is a cubic Bezier (but when you say it that way it seems more obvious :P plus it makes sense with control points a,b,c,d you have 1 a, 3 bs and cs, and 1 d - the coefficients of the cubic equation)
The Seiler representation feels in a way similar to Hermite; it’s still a Bezier with the 2 endpoints, and the interior 2 control points use a convenient differential form.
Kind of amazing the perf is as good as using shader code, FMA instructions or whatever. I would make the argument that this is useful even if slower (and it might be on, say, mobile hardware), since you are offloading work to the texture hardware. It’s like adding extra FMA units to the machine.
This makes me wonder if there’s some way to evaluate a quadratic B-spline using a 2D 2x(N+1) texture, sharing a texture edge with the neighbor segment, so the amortized cost of a segment is ~2 texels instead of 4…
Oh also the paper mentions Boehm’s algorithm for converting Bezier to B-spline. Note that if you lookup Boehm’s algorithm it will look crazy complicated, but you can convert the control points of a cubic Bezier to a cubic uniform B-spline with a single matrix-matrix multiply. This is true for converting to/from Catmull-Rom as well, plus I think any type that’s cubic polynomial. You lose the vertex sharing, but that’s already gone with texture sampling - so this paper will automatically work on any polynomial curves, not just Bezier.
Looks like the theoretical heavy-lifting was done by Lin et al. https://onlinelibrary.wiley.com/doi/10.1111/cgf.14377
Preprint of that:
https://dqlin.xyz/pubs/2021-hpg-HOI/
I never heard of the Seiler interpolation algorithm mentioned in the paper before, but the way it uses extra additions and subtractions up-front to turn six interpolations into only three reminds me a bit of the Karatsuba algorithm for multiplication[0]. I wonder if that was an inspiration for it?
Also makes me wonder if this will have uses outside of graphics? Bézier curves are used in other contexts too, aren't they?
[0] https://en.wikipedia.org/wiki/Karatsuba_algorithm
Nice work, using fixed-function units for unexpected applications feels properly old-school!
Done 3 years earlier at https://www.cemyuksel.com/research/seilers_interpolation/ ?
This builds on that paper, apparently:
> Yuksel [2024] explained how Seiler interpolation can be used to evaluate polynomial curves, including B´ezier curves, and noted that GPU linear interpolation could be used for the initial linear interpolation steps, with the remaining interpolations done in shader code.
> In this paper, we present the details of evaluating Bézier curves using hardware-accelerated linear texture interpolation and show how to perform all interpolations on the hardware, using both the de Casteljau algorithm and Seiler interpolation. We also compare performance and accuracy against curves evaluated as polynomials in shader code.
Ah yes. That covered some Bezier interpolations; this covers all. Thanks for the correction.
Yeah bro, that's just awesome.