Gregory's Server@raph You might want to take a look over how forma currently does it: it reduces the problem to finding the ith term in the sorted union between two arithmatic progressions ax + c and bx + d, which can be solved in O(1) for some given level of accuracy.
|
5 comments
@raph Numerical robustness is the tricky part for sure. The guess requires the use of double-precision for when the difference between two points is very small but non-zero. Another way to solve this would be force lower precision for all points (e.g. f16) and then compute the guess in single-precision.  @dtiselice I'm *hoping* to make it robust by having correct rendering for either of the two cases when the decision is near the critical point. But we'll see how practical that is. @raph Robustness is a tricky but very satisfying problem to solve. For conflation, I was considering marking pixels/tiles and saving coverage information, and then running another round of painting on those pixels only, recursively. In any case, enjoy your time and good luck! :) @dtiselice I have ideas along those lines as well, and think it's the winning strategy for solving conflation in compositing. But for just path rendering, the current plan is to do the MSAA resolve every pixel. With bit-magic I expect it to be fast (faster than overhead from two passes/sparseness), and I'm also thinking of special casing winding numbers fitting in 4 bits. A bit more detail on the line algorithm in https://github.com/linebender/vello/issues/270#issuecomment-1416256458 |
@dtiselice Nice solution, and I did look at it, but of course had to put my own spin on it.
What I have is "Binary search to find segment and pixel" in https://github.com/linebender/vello/issues/270. It seems to work magically, but I haven't yet done the numerical robustness work. As you know, that's often just as hard as solving the happy path.