I've generalized this to cubic Béziers, test page is up at https://levien.com/tmp/flatten.html …. 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.
-
-
Show this threadThanks. Twitter will use this to make your timeline better. UndoUndo
-
-
-
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.
-
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.
- 1 more reply
New conversation -
-
-
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!
-
Shorter: you can use Wang’s (and successors) for computing the necessary number of line segments for quads, cubics, and even rationals.

- 4 more replies
New conversation -
-
-
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.
-
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.
End of conversation
New conversation -
-
-
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!
Thanks. Twitter will use this to make your timeline better. UndoUndo
-
-
-
Let's all understand this: Bézier curves are evil... 5th order curve is pure!
Thanks. Twitter will use this to make your timeline better. UndoUndo
-
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.