Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Exact Polygonal Filtering: Using Green's Theorem and Clipping for Anti-Aliasing

jonathanolson.net

Post reply on HN
Print view View original

51–60 of 86 posts

Re: Exact Polygonal Filtering: Using Green's Theorem and Clipping for Anti-Aliasing

#51

Post by mfabbri77 »

raphlinus wrote: post #48
dahart wrote: post #35

Earlier quoted context omitted.

Why are you convinced of this, and can I help unconvince you? ;) What you describe is what’s called “Box Filtering” in the article. Box filtering is well studied, and it is known to not be the best possible output quality. The reason this is not the best approach is because a pixel is not a little square, a pixel is a sample of a signal, and it has to be approached with signal processing and human perception in mind.…

I think the story is a lot more complicated. Talking about "the best possible output quality" is a big claim, and I have no reason to believe it can be achieved by mathematically simple techniques (ie linear convolution with a kernel). Quality is ultimately a function of human perception, which is complex and poorly understood, and optimizing for that is similarly not going to be easy. The Mitchell-Netravali paper[1]…

In my opinion, if you break down all the polygons in your scene into non-overlapping polygons, then clip them into pixels, calculate the color of each piece of polygon (applying all paints, blend modes, etc) and sum it up, ...in the end that's the best visual quality you can get. And that's the idea i'm working on, but it involves the decomposition/clip step on the CPU, while sum of paint/blend is done by the GPU.

Re: Exact Polygonal Filtering: Using Green's Theorem and Clipping for Anti-Aliasing

#52

Post by dahart »

mfabbri77 wrote: post #51
raphlinus wrote: post #48

Earlier quoted context omitted.

I think the story is a lot more complicated. Talking about "the best possible output quality" is a big claim, and I have no reason to believe it can be achieved by mathematically simple techniques (ie linear convolution with a kernel). Quality is ultimately a function of human perception, which is complex and poorly understood, and optimizing for that is similarly not going to be easy. The Mitchell-Netravali paper[1]…

In my opinion, if you break down all the polygons in your scene into non-overlapping polygons, then clip them into pixels, calculate the color of each piece of polygon (applying all paints, blend modes, etc) and sum it up, ...in the end that's the best visual quality you can get. And that's the idea i'm working on, but it involves the decomposition/clip step on the CPU, while sum of paint/blend is done by the GPU.

That isn’t true. Again, please look more closely at the first example in the article, and take the time to understand it. It demonstrates there’s a better method than what you’re suggesting, proving that clipping to pixels and summing the area is not the best visual quality you can get.

Re: Exact Polygonal Filtering: Using Green's Theorem and Clipping for Anti-Aliasing

#53

Post by pixelpoet »

dahart wrote: post #50
pixelpoet wrote: post #32

Earlier quoted context omitted.

If you look at old papers by James Arvo, he has done analytic illumination from linearly varying lights, maybe this is helpful. Here for example his thesis: https://www.cs.cornell.edu/courses/cs667/2005sp/readings/Arv... There's also this work on analytic antialiasing by Michael Mccool: https://www.researchgate.net/publication/2524514_Analytic_An...

Arvo’s work is also using Green’s theorem, in much the same way this article is. Integrating the phong-exponent light reflections is a little bit insane though (and btw I’ve seen Arvo’s code for it.) The problem you run into with non-constant polygon colors is that you’d have to integrate the product of two different functions here - the polygon color and the filter function. For anything real-world, this is almost c…

Yup, I've tried many years ago to follow this work (special cases for even and odd exponents!), with a mix of analytic and numerical integration. IMO linear/tent filter is sufficient. Also more recently there's the Linearly Transformed Cosine stuff, which is most of what people usually want in realtime graphics.

Ideally you also want motion blur and probably some other effects, so IMO it just makes sense to use a 2D BVH and high efficiency Monte Carlo importance sampling methods.

Re: Exact Polygonal Filtering: Using Green's Theorem and Clipping for Anti-Aliasing

#54

Post by mfabbri77 »

dahart wrote: post #52
mfabbri77 wrote: post #51

Earlier quoted context omitted.

In my opinion, if you break down all the polygons in your scene into non-overlapping polygons, then clip them into pixels, calculate the color of each piece of polygon (applying all paints, blend modes, etc) and sum it up, ...in the end that's the best visual quality you can get. And that's the idea i'm working on, but it involves the decomposition/clip step on the CPU, while sum of paint/blend is done by the GPU.

That isn’t true. Again, please look more closely at the first example in the article, and take the time to understand it. It demonstrates there’s a better method than what you’re suggesting, proving that clipping to pixels and summing the area is not the best visual quality you can get.

As pointed out by Raphlinus, the moire pattern in the Siemens star isn't such a significant quality indicator for the type of content usually encountered in 2D vector graphics. With the analytical coverage calculation you can have perfect font/text rendering, perfect thin lines/shapes and, by solving all the areas at once, no conflating artifacts.

Re: Exact Polygonal Filtering: Using Green's Theorem and Clipping for Anti-Aliasing

#55

Post by dahart »

mfabbri77 wrote: post #54
dahart wrote: post #52

Earlier quoted context omitted.

That isn’t true. Again, please look more closely at the first example in the article, and take the time to understand it. It demonstrates there’s a better method than what you’re suggesting, proving that clipping to pixels and summing the area is not the best visual quality you can get.

As pointed out by Raphlinus, the moire pattern in the Siemens star isn't such a significant quality indicator for the type of content usually encountered in 2D vector graphics. With the analytical coverage calculation you can have perfect font/text rendering, perfect thin lines/shapes and, by solving all the areas at once, no conflating artifacts.

Raph made an argument that Box is good enough for lots of things, which is subjective and depends entirely on what things you’re doing, and how much you actually care about quality.

You are claiming it’s the best possible. Box filter is simply not the best possible, and this fact is well understood and documented.

You can relax your claim to say it’s good enough for what you need, and I won’t disagree with you anymore. Personally, I’m sensitive to visible pixelation, and the Box Filter will always result in some visible pixelation with all 2D vector graphics, so if you really care about high quality rendering, I’m very skeptical that you really want Box filtering as the ideal target. Box filter is a compromise, it’s easier & faster to compute. But it’s not the highest quality. It would be good to understand why that’s the case.

* Edit to further clarify and respond to this:

> With the analytical coverage calculation you can have perfect font/text rendering, perfect thin lines/shapes and, by solving all the areas at once, no conflating artifacts.

You cannot get perfect font or text rendering with a Box filter, and you will get some conflating artifacts. They might be very slight, and not bothersome to most people, but they do exist with a Box filter, always. This is a mathematical property of Box filtering, not a subjective claim.

Re: Exact Polygonal Filtering: Using Green's Theorem and Clipping for Anti-Aliasing

#56

Post by fjkdlsjflkds »

rty32 wrote: post #31
eru wrote: post #2

A note for other readers: this is a lot more impressive with 'WebGPU' available.

The web page is able to slow down my Android phone to the point that it stops responding to power button click. If you told me this page exploits a 0-day vulnerability in Android I would have believed it. Impressive. (Android 14, Android WebView/Chrome 127)

This. Unfortunately, I couldn't read beyond the first page, since it keeps crashing my (desktop) browser. Would be nice to have a button to stop/remove all animations in the page, so I could actually read the rest.

Re: Exact Polygonal Filtering: Using Green's Theorem and Clipping for Anti-Aliasing

#57

Post by phkahler »

dahart wrote: post #52
mfabbri77 wrote: post #51

Earlier quoted context omitted.

In my opinion, if you break down all the polygons in your scene into non-overlapping polygons, then clip them into pixels, calculate the color of each piece of polygon (applying all paints, blend modes, etc) and sum it up, ...in the end that's the best visual quality you can get. And that's the idea i'm working on, but it involves the decomposition/clip step on the CPU, while sum of paint/blend is done by the GPU.

That isn’t true. Again, please look more closely at the first example in the article, and take the time to understand it. It demonstrates there’s a better method than what you’re suggesting, proving that clipping to pixels and summing the area is not the best visual quality you can get.

Backing up to your earlier comment. Pixels on some displays are in fact little squares of uniform color. The question then is how to color a pixel given geometry with detail within that square.

All of this "filtering" is variations on adding blur. In fact the article extends the technique to deliberately blur images on a larger scale. When we integrate a function (which could be a color gradient over a fully filled polygon) and then paint the little square with a solid "average" color that's also a form of blurring (more like distorting in this case) the detail.

It is notable that the examples given are moving, which means moire patterns and other artifacts will have frame-to-frame effects that may be annoying visually. Simply blurring the image takes care of that at the expense of eliminating what looks like detail but may not actually be meaningful. Some of the less blurry images seem to have radial lines that bend and go back out in another location for example, so I'd call that false detail. It may actually be better to blur such detail instead of leaving it look sharper with false contours.

Re: Exact Polygonal Filtering: Using Green's Theorem and Clipping for Anti-Aliasing

#58

Post by dahart »

phkahler wrote: post #57
dahart wrote: post #52

Earlier quoted context omitted.

That isn’t true. Again, please look more closely at the first example in the article, and take the time to understand it. It demonstrates there’s a better method than what you’re suggesting, proving that clipping to pixels and summing the area is not the best visual quality you can get.

Backing up to your earlier comment. Pixels on some displays are in fact little squares of uniform color . The question then is how to color a pixel given geometry with detail within that square. All of this "filtering" is variations on adding blur. In fact the article extends the technique to deliberately blur images on a larger scale. When we integrate a function (which could be a color gradient over a fully filled…

Yes it’s a good point that LCD pixels are more square than the CRTs that were ubiquitous when Alvy Ray wrote his paper. I think I even made that point before on HN somewhere. I did mention in response to Raph that yes the ideal target depends on what the display is, and the filter choice does depend on whether it’s LCD, CRT, film, print, or something else. That said, LCD pixels are not perfect little squares, and they’re almost never uniform color. The ideal filter for LCDs might be kinda complicated, and you’d probably need three RGB-separated filters.

Conceptually, what we’re doing is low-pass filtering, rather than blurring, so I wouldn’t necessarily call filtering just “adding blur”, but in some sense those two ideas are very close to each other, so I wouldn’t call it wrong either. :P The render filtering is a convolution integral, and is slightly different than adding blur to an image without taking the pixel shape into account. Here the filter’s quality depends on taking the pixel shape into account.

You’re right about making note of the animated examples - this is because it’s easier to demonstrate aliasing when animated. The ‘false detail’ is also aliasing, and does arise because the filtering didn’t adequately filter out high frequencies, so they’ve been sampled incorrectly and lead to incorrect image reconstruction. I totally agree that if you get such aliasing false detail, it’s preferable to err (slightly) on the side of blurry, rather than sharp and wrong.

Re: Exact Polygonal Filtering: Using Green's Theorem and Clipping for Anti-Aliasing

#59

Post by yorwba »

dahart wrote: post #55
mfabbri77 wrote: post #54

Earlier quoted context omitted.

As pointed out by Raphlinus, the moire pattern in the Siemens star isn't such a significant quality indicator for the type of content usually encountered in 2D vector graphics. With the analytical coverage calculation you can have perfect font/text rendering, perfect thin lines/shapes and, by solving all the areas at once, no conflating artifacts.

Raph made an argument that Box is good enough for lots of things, which is subjective and depends entirely on what things you’re doing, and how much you actually care about quality. You are claiming it’s the best possible. Box filter is simply not the best possible, and this fact is well understood and documented. You can relax your claim to say it’s good enough for what you need, and I won’t disagree with you anymor…

Why do conflation artifacts always exist with a box filter? AFAIK conflation artifacts are a product of the compositing process, not the filtering process.

If you have two non-overlapping shapes of the same color covering the plane and use a box filter on the first shape to sample a pixel on the boundary, and then use the same box filter on the second shape, and then composit them with alpha blending, you get a conflation artifact along the boundary where the background bleeds through.

But if you use the fact that the shapes are non-overlapping and sum their contributions instead, the artifact disappears, while still using the same box filter.

Re: Exact Polygonal Filtering: Using Green's Theorem and Clipping for Anti-Aliasing

#60

Post by muyyatin2 »

raphlinus wrote: post #37

I love to see more work in this space. It's clear that GPU compute is the future of 2D rendering, and we need to explore a bunch of different approaches to find the best one. I especially appreciate the focus on rendering quality; the author is absolutely correct that the current state of Vello has conflation artifacts and does not do antialiasing in the correct (linear) colorspace. We do have a plan for conflation f…

The analytic approach to occlusion definitely does seem like a "humbling parallelism" type of problem on the GPU. My curiosity is leading me to explore it, and it may be reasonable if I find alternatives to large GPU sorts (although I understand you've done some work on that recently). I think the Vello approach is very likely the superior option for the best general quality/performance tradeoff.
Post reply on HN