|
@raphlinus | |||||
|
Recursive subdivision is not the best way to flatten quadratic Béziers to polylines. Here's a better way: raphlinus.github.io/graphics/curve… . Hopefully catnip for my followers who are really into 2D graphics and math.
|
||||||
|
||||||
|
Raph Levien
@raphlinus
|
28. pro |
|
I've generalized this to cubic Béziers, test page is up at levien.com/tmp/flatten.ht…. Question for 2d graphics Twitter: what's a good journal or conference to submit to? It feels like it's met the threshold for an academic paper.
|
||
|
|
||
|
Ali Rahimi
@alirahimi0
|
24. pro |
|
my instinct is to do this by dynamic programming instead, since you know the number of segments. locate endpoint of first segment assuming subsequent ones are chosen optimally. then work backwards by DP.
|
||
|
|
||
|
Raph Levien
@raphlinus
|
24. pro |
|
Yeah, that's what was going through my head a week or so ago. But this way, you have a closed form expression that just spits out all the t values in parallel for all the segments, which is *way* better if your evaluation environment is a GPU.
|
||
|
|
||
|
Allan MacKinnon
@pixelio
|
25. pro |
|
Wang’s Formula bounds how many levels of subdivision you need to achieve a specified degree of flatness.
“Pyramid Algorithms” by Ron Goldman covers Wang’s formula (chap. 5.6.3).
Wang’s formula is also discussed in: DEC Paris Research Laboratory report #1, May 1989.
Good luck!
|
||
|
|
||
|
Raph Levien
@raphlinus
|
25. pro |
|
Thanks for the reference, it looks excellent. How did I not know about that before now?
|
||
|
|
||
|
Andreas Urbán
@1amjau
|
24. pro |
|
Any thoughts on doing recursive subdivision on GPU using the tessellation stage and transform feedback? Breadth first makes it quite parallel, and error can be decreased over several frames.
|
||
|
|
||
|
Raph Levien
@raphlinus
|
24. pro |
|
It can probably be done, but for my own GPU work I'm basically using compute exclusively. It's also the case that my algorithm produces more efficient results than recursive subdivision, which takes away most of the motivation to do that.
|
||
|
|
||
|
Nicolas Silva
@nicalsilva
|
24. pro |
|
Interesting! One thing to note with these adaptative flattening techniques is that if you don't consistently flatten in the same direction (say, top to bottom) you can get unexpected cracks between adjacent paths. Easy to address in most cases but worth keeping in mind!
|
||
|
|
||
|
DaveFile
@davefile
|
24. pro |
|
Let's all understand this: Bézier curves are evil...
5th order curve is pure!
|
||
|
|
||