Rendered at 03:10:05 GMT+0000 (Coordinated Universal Time) with Cloudflare Workers.
dahart 3 days ago [-]
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.
You know, I see that Cem Yuksel is one of the authors, and he is one of those names that keeps popping up in the weirdest places whenever I look up something random that involves graphics and the maths behind it (especially when splines are involved). Is he like one of those "experts know he's a big deal in his niche but non-experts never heard about him" kind of guys?
EDIT: I remember now that the first time I came across his work was over 15 years ago when I was trying to interpolate between two vector shapes, and always had to deal with twists between them. I ended up reading a paper by him showing the fix for Catmull-Rom splines[0]. Ever since I've sounded like mad-man for complaining that 3b1b should have used "centripetal parameterization" for manim, haha, because it also often has these twists when interpolating.
> Is he like one of those “experts know he’s a big deal in his niche but non-experts never heard about him” kind of guys?
Depends on what you mean. Is Bezier famous enough, or are we talking Stephen Hawking or Billie Eilish famous? Only time will tell, and it’s too early to say. All the experts that non-experts have heard of started out being unknown.
Cem’s already very well known in the computer graphics community, at Siggraph for example. He’s doing active research and advising and graduating many students. He’s published quite a few papers on curve/hair rendering and simulation physics, with a tendency toward real-time & game applications. So most active graphics students and profs know of him, and outside academic graphics, a lot of game programmers have heard of him.
Maybe in 50 years, you’ll hear Yuksel curves as often as Bézier curves.
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.
chrisjj 2 days ago [-]
Ah yes. That covered some Bezier interpolations; this covers all. Thanks for the correction.
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.
EDIT: I remember now that the first time I came across his work was over 15 years ago when I was trying to interpolate between two vector shapes, and always had to deal with twists between them. I ended up reading a paper by him showing the fix for Catmull-Rom splines[0]. Ever since I've sounded like mad-man for complaining that 3b1b should have used "centripetal parameterization" for manim, haha, because it also often has these twists when interpolating.
[0] https://www.cemyuksel.com/research/catmullrom_param/
Depends on what you mean. Is Bezier famous enough, or are we talking Stephen Hawking or Billie Eilish famous? Only time will tell, and it’s too early to say. All the experts that non-experts have heard of started out being unknown.
Cem’s already very well known in the computer graphics community, at Siggraph for example. He’s doing active research and advising and graduating many students. He’s published quite a few papers on curve/hair rendering and simulation physics, with a tendency toward real-time & game applications. So most active graphics students and profs know of him, and outside academic graphics, a lot of game programmers have heard of him.
Maybe in 50 years, you’ll hear Yuksel curves as often as Bézier curves.
https://dqlin.xyz/pubs/2021-hpg-HOI/
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
> 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.