 I just booked a cottage on a lake for a week-long research retreat Feb 13-18. I've done this kind of thing a couple times before and am hoping to make it a regular practice. The idea is to fully immerse into one deep topic, without the usual distractions and gear-switching. This time it'll *probably* be path rendering without conflation artifacts, but there are a couple other deep topics I'd love to address. Attached is an image from that inquiry: how to parallelize line coverage on a grid. 8 comments
@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. @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. @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 |
Gregory's Server
@raph Hi Raph, I watched your great talk about Xilem, very interesting stuff,
looking forward to see where it will go.
I am currently building a 2D sprite editor in Rust, so this problem you
posted is something I had to deal with recently (but without the parallelism).
If you calculate the size of the line, you can find the intermediate points
and give each pair to a thread/task, would that work?