Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Path intersection (aka SVG clipPath) #30

Closed
eliasnaur opened this issue Aug 29, 2020 · 1 comment
Closed

Path intersection (aka SVG clipPath) #30

eliasnaur opened this issue Aug 29, 2020 · 1 comment

Comments

@eliasnaur
Copy link
Collaborator

I'd like to generalize path+fill to stack-of-paths+fills such that fills only cover the intersection of the paths in a stack. Would that be feasible with the current architecture? Would you be interested in having that work in piet-gpu?

An efficient algorithm that converts intersecting paths into a single path would be a nice alternative, in which case clipPath would be a pre-process step.

@raphlinus
Copy link
Contributor

Yes, I'd very much like to have this functionality; it's in the Piet imaging model and I would consider it fundamental to 2D graphics.

There are a few ways to do this. Doing it the second way using path ops is appealing, but has two major challenges. First is that robust, performant path ops are very difficult, largely because of numerical robustness issues. (They make #23 look like child's play). I'd estimate that standing up a new path op library from scratch is about a one year project (take a look at the commit history of Skia path ops if you're having trouble believing me). The second is that the preprocessing might have to be redone. For example, take a filled path inside a rounded rect, but the inner path is translating (for example because of a scrolling gesture). The path computation would need to be redone. If those paths are text, that's a serious performance killer. I'm also not sure if it's practical do to path ops GPU-side at all.

So I prefer doing it with blending. Another major reason to prefer blending is that the same infrastructure can be applied to do a bunch of other blending effects, such as group alpha and the non Porter-Duff blending modes.

Within blending, there are a few other choices. Pathfinder relatively recently solved this problem, and I think did it a little differently than what I have in mind (I discussed it with Patrick a bit but didn't review it carefully and don't remember all details). I strongly recommend reviewing that solution, so that there's a conscious choice which way to go.

Here's a rough outline of how I was envisioning doing it.

Instead of working on a single pixel, the fine rasterizer maintains a stack of pixels, and an alpha mask value. Having a clip in the scene translates into a push, rasterization of the clip path into the alpha mask channel, then the contents of the clip, and finally a pop. The pop operation does Porter-Duff compositing. A challenge here is storage space for the stack. Also what happens the stack depth is exceeded?

To be consistent with the existing scene representation (a sequence of fixed-size elements), I'm imagining extending that alphabet with similar operations: push, render path to alpha, pop. If it weren't for the pesky problem of bounding boxes, the coarse raster pipeline could just pass those right through.

Here's the pesky problem of bbox: if you push, draw a clip path, say the top half of the viewport, draw a circle in the bottom half, then pop, then the binned element streams don't tell the whole story. Specifically, if the bbox assigned to the push and pop operations is the bbox of the clip path, then in the bottom half you'd just see "draw circle," so the clip wouldn't be effective.

I think the solution is for the bbox on the push/pop elements to include the bounding box of its contents. Ultimately I'd like to compute that GPU-side, but that's a bit of a hard problem. I think to get forward progress, it's best to compute it CPU-side as part of the encoding process, then, once that's working, investigate moving it. I have some ideas, but best probably best not to complicate the discussion too much for now.

With this in place, there's a bit of additional logic that can go in the coarse rasterizer to optimize for mask tiles that are all 0 (children of the clip can just be suppressed) or all 1 (the alpha mask computation and push/pop operations can be elided). Those optimizations are actually quite compelling, as it means that the fine raster cost of clipping is limited to just the tiles that touch the clip path. But it's also possible to get something working without those.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants