Exact Polygonal Filtering: Using Green's Theorem and Clipping for Anti-Aliasing
1–10 of 86 posts
Re: Exact Polygonal Filtering: Using Green's Theorem and Clipping for Anti-Aliasing
#2A note for other readers: this is a lot more impressive with 'WebGPU' available.
Re: Exact Polygonal Filtering: Using Green's Theorem and Clipping for Anti-Aliasing
#3Fantastic article, exactly my kinda thing :)
One significant limitation here is that the polygon needs to have constant colour, unfortunately.
Re: Exact Polygonal Filtering: Using Green's Theorem and Clipping for Anti-Aliasing
#4A note for other readers: this is a lot more impressive with 'WebGPU' available.
[deleted]
Re: Exact Polygonal Filtering: Using Green's Theorem and Clipping for Anti-Aliasing
#5I am quite convinced that if the goal is the best possible output quality, then the best approach is to analytically compute the non-overlapping areas of each polygon within each pixel. Resolving all contributions (areas) together in the same single pass for each pixel.
Re: Exact Polygonal Filtering: Using Green's Theorem and Clipping for Anti-Aliasing
#6I am quite convinced that if the goal is the best possible output quality, then the best approach is to analytically compute the non-overlapping areas of each polygon within each pixel. Resolving all contributions (areas) together in the same single pass for each pixel.
I've been looking into how viable this is as a performant strategy. If you have non-overlapping areas, then contributions to a single pixel can be made independently (since it is just the sum of contributions). The usual approach (computing coverage and blending into the color) is more constrained, where the operations need to be done in back-to-front order.
Re: Exact Polygonal Filtering: Using Green's Theorem and Clipping for Anti-Aliasing
#7I am quite convinced that if the goal is the best possible output quality, then the best approach is to analytically compute the non-overlapping areas of each polygon within each pixel. Resolving all contributions (areas) together in the same single pass for each pixel.
I've been looking into how viable this is as a performant strategy. If you have non-overlapping areas, then contributions to a single pixel can be made independently (since it is just the sum of contributions). The usual approach (computing coverage and blending into the color) is more constrained, where the operations need to be done in back-to-front order.
I've been researching this field for 20 years (I'm one of the developers of AmanithVG). Unfortunately, no matter how fast they are made, all the algorithms to analytically decompose areas involve a step to find intersections and therefore sweepline approaches that are difficult to parallelize and therefore must be done in CPU. However, we are working on it for the next AmanithVG rasterizer, so I'm keeping my eyes open for all possible alternatives.
Re: Exact Polygonal Filtering: Using Green's Theorem and Clipping for Anti-Aliasing
#8> This is equivalent to applying a box filter to the polygon, which is the simplest form of filtering.
Am I the only one who has trouble understanding what is meant by this? What is the exact operation that's referred to here?
I know box filters in the context of 2D image filtering and they're straightforward but the concept of applying them to shapes just doesn't make any sense to me.
Can someone clarify?
Re: Exact Polygonal Filtering: Using Green's Theorem and Clipping for Anti-Aliasing
#9Earlier quoted context omitted.
I've been looking into how viable this is as a performant strategy. If you have non-overlapping areas, then contributions to a single pixel can be made independently (since it is just the sum of contributions). The usual approach (computing coverage and blending into the color) is more constrained, where the operations need to be done in back-to-front order.
I've been researching this field for 20 years (I'm one of the developers of AmanithVG). Unfortunately, no matter how fast they are made, all the algorithms to analytically decompose areas involve a step to find intersections and therefore sweepline approaches that are difficult to parallelize and therefore must be done in CPU. However, we are working on it for the next AmanithVG rasterizer, so I'm keeping my eyes ope…
I ran across https://dl.acm.org/doi/pdf/10.1145/72935.72950 a few weeks ago, it seems like a potential non-sweepline highly-parallel method. I've had some promising results for first doing a higher-dimensional Hilbert-sort (giving spatial locality), and then being able to prune a very large percentage of the quadratic search space. It might still be too slow on the GPU. I'm curious if you have any write-ups on things that have been explored, or if I'd be able to pick your brain some time!
Re: Exact Polygonal Filtering: Using Green's Theorem and Clipping for Anti-Aliasing
#10> This is equivalent to applying a box filter to the polygon, which is the simplest form of filtering. Am I the only one who has trouble understanding what is meant by this? What is the exact operation that's referred to here? I know box filters in the context of 2D image filtering and they're straightforward but the concept of applying them to shapes just doesn't make any sense to me. Can someone clarify?
It is more similar to the convolution of the shape with the filter (you can take the product of the filter, at various offsets, with the polygon)
Essentially if you have a polygon function p(x,y) => { 1 if inside the polygon, otherwise 0 }, and a filter function f(x,y) centered at the origin, then you can evaluate the filter at any point x_0,y_0 with the double-integral / total sum of f(x-x_0,y-y_0)*p(x,y).