6 ms·

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

• eru 2y ago
  A note for other readers: this is a lot more impressive with 'WebGPU' available.
  • deleted 2y ago
    [deleted]
  • rty32 2y ago
    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)
    • fjkdlsjflkds 2y ago
      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.
      • eru 2y ago
        On my MacBook, Firefox (my usual browser) didn't have WebGPU, so rendering was mostly disabled; and on Chrome WebGPU was available. Viewing the page in either browser was fine for the rest of my machine. But I can imagine that it's a heavy load on some computers.
    • eru 2y ago
      You could say it's a denial-of-service attack on your phone. But I guess it's not exactly a secret that misbehaving websites that you visit can slow down your phone. (However it seems wrong that Android doesn't set up things via eg cgroups or whatever to make sure that the browser can't hog all the resources. You'd want to reserve say 5% of memory and RAM for use by system tasks perhaps? (Reserve in the sense that these system tasks can pre-empt anyone else using these, not that no one else can use these.))
      • rty32 2y ago
        I do think such mechanisms exist in various places. CPU intensive browser pages (e.g. running an infinite loop in JavaScript) would leave the page unresponsive, but the browser and the OS in general is still fine. You can easily close the page causing trouble. Well, at least in desktop Chrome and Firefox. I definitely haven't seen one page slowing the entire browser since the IE days. On the other hand, if a (general) Android app is not responsive, there is also a dialog inviting you to kill it ("[app name] isn't responding - Close app"). But this one is different. I don't know the underlying mechanisms for the browser and the OS, but it almost feels like a bug.
• pixelpoet 2y ago
  Fantastic article, exactly my kinda thing :) One significant limitation here is that the polygon needs to have constant colour, unfortunately.
  • Etherlord87 2y ago
    But the blurring example has a gradient on the star?
  • muyyatin2 2y ago
    Ahh yes, for exact filtering it does need to be constant colour. I'm looking into seeing whether it can be done for gradients. However in practice, it works quite well visually to compute the "average color of the polygon" for each piecewise section, and blend those together.
    • pixelpoet 2y ago
      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/ArvoThesis.pdf 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_Antialiasing_with_Prism_Splines https://www.researchgate.net/publication/2524514_Analytic_An...
      • dahart 2y ago
        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 certainly going to result in an expression that is not analytically integrable.
        • 2y ago
• mfabbri77 2y ago
  I 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.
  • muyyatin2 2y ago
    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.
    • mfabbri77 2y ago
      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.
      • muyyatin2 2y ago
        I ran across https://dl.acm.org/doi/pdf/10.1145/72935.72950 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!
      • dvdkon 2y ago
        I believe Vello does this for AA (though I can't find the source now), and it's very fast, running on the GPU via compute shaders.
• rsp1984 2y ago
  > 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?
  • muyyatin2 2y ago
    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).
    • blauditore 2y ago
      This kind of makes sense from a mathematical point of view, but how would this look implementation-wise, in a scenario where you need to render a polygon scene? The article states that box filters are "the simplest form of filtering", but it sounds quite non-trivial for that use case.
    • Klaus23 2y ago
      If it essentially calculates the area of the polygon inside the pixel box and then assigns a colour to the pixel based on the area portion, how would any spatial aliasing artifacts appear? Shouldn't it be equivalent to super-sampling with infinite sample points?
  • Sharlin 2y ago
    It literally means that you take a box-shaped piece of the polygon, ie. the intersection of the polygon and a box (a square, in this case the size of one pixel). And do this for each pixel as they’re processed by the rasterizer. If you think of a polygon as a function from R^2 to {0, 1}, where every point inside the polygon maps to 1, then it’s just a signal that you can apply filters to.
• codeflo 2y ago
  The opening statement makes it out that this exact calculation is supposed to be superior to multisampling, but the opposite is the case. Computing the exact mathematical coverage of a single polygon against a background is useless for animations if you can't seamlessly stitch multiple polygons together. And that's why GPUs use multisampling: Each sample is an exact mathematical point that's covered by either polygon at the seam, without the background bleeding through.
  • blauditore 2y ago
    If you can't stitch polygons together seamlessly, how can you be sure the background doesn't bleed through with sampling? Isn't computing the exact coverage the same as having infinitely many point samples? The bleed-through of the background would then also be proportional to the gap between polygons, so if that one's small, the bleeding would be minor as well.
    • codeflo 2y ago
      No, in animated models, there is no gap between polygons. And if you only compute single-polygon coverage, you can’t determine whether for two polygons that each cover 50% of a pixel, they both cover the same 50%, or complementary 50%, or anything in between. In practice, systems like that tend to show something like 25% background, 25% polygon A and 50% polygon B for the seam pixels, depending on draw order. That is, you get 25% background bleed.
  • CodeVenturer 2y ago
    [dead]
  • deleted 2y ago
    [deleted]
  • deleted 2y ago
    [deleted]
  • dahart 2y ago
    You might be making some incorrect assumptions about what this article is describing. It’s not limited to a single polygon against a background. Analytic integration is always superior to multisampling, assuming the same choice of filter, and as long as the analytic integration is correct. Your comment is making an assumption that the analytic integration is incorrect in the presence of multiple polygons. This isn’t true though, the article is using multiple polygons, though the demo is limited in multiple ways for simplicity, it doesn’t appear to handle any arbitrary situation. The limitations of the demo (whether it handles overlapping polygons, stitched meshes, textures, etc.) does not have any bearing on the conceptual point that computing the pixel analytically is better than taking multiple point samples. GPUs use multisampling because it’s easy and finite to compute, not because it’s higher quality. Multisampling is lower quality than analytic, but it’s far, far easier to productize, and it’s good enough for most things (especially games).
• AKSZ 2y ago
  [flagged]
• raphlinus 2y ago
  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 free compositing[1] which should closely approximate the quality of the samples here. That in turn depends on sparse strips[2], though a degraded performance experiment could be done to validate the quality outcomes. Sparse strips in turn depend on high performance segmented sort[3]. The analytic approach to path overlaps is intriguing, but I think it will be very challenging to implement efficiently on GPU. I'm looking forward to seeing what results. [1]: https://xi.zulipchat.com/#narrow/stream/197075-gpu/topic/Conflation.20artifact.20free.20compositing https://xi.zulipchat.com/#narrow/stream/197075-gpu/topic/Con... [2]: https://docs.google.com/document/d/16dlcHvvLMumRa5MAyk2Du_MsjF32w0G-n7L9NOJUbRI/edit?usp=drive_link https://docs.google.com/document/d/16dlcHvvLMumRa5MAyk2Du_Ms... [3]: https://xi.zulipchat.com/#narrow/stream/197075-gpu/topic/A.20Better.20Sort.20for.20Sparse.20Strip.20Rendering https://xi.zulipchat.com/#narrow/stream/197075-gpu/topic/A.2...
  • muyyatin2 2y ago
    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.
    • raphlinus 2y ago
      Ah, you watched my "good parallel computer" talk[﹡] :) If I were going to take it on, I'd start with BVH construction - the H-PLOC paper at the latest HPG [1] looks promising - then traverse down the hierarchy until you get very small number of path segments so you can pairwise compare them. Obviously any time there is an intersection you need at least the two segments. This seems hard to me, humbling even. I mean, overlap removal is hard enough on the CPU, especially because it's so sensitive to numerical robustness, and doubly so for curves. But I think you'll learn something for trying! [﹡] https://news.ycombinator.com/item?id=41105102 https://news.ycombinator.com/item?id=41105102 but it didn't make the front page; I'm holding back promoting it further pending writing a companion blog post. [1]: https://gpuopen.com/download/publications/HPLOC.pdf https://gpuopen.com/download/publications/HPLOC.pdf
• david-gpu 2y ago
  The problem with these sorts of analytical approaches is how to handle backgrounds, depth and intersections. There are good reasons why GPUs rely on variations of multisampling. Even CPU-based 3D render engines use similar methods rather than analytic filters, as far as I know. A more interesting approach to antialiasing, in my opinion, is the use of neural nets to generate aesthetically pleasing outputs from limited sample data, as seen for example in NVidia's DLAA [0]. These methods go beyond trying to optimize over-simplistic signal processing reconstruction metrics. [0] https://en.wikipedia.org/wiki/Deep_learning_anti-aliasing https://en.wikipedia.org/wiki/Deep_learning_anti-aliasing
  • adastra22 2y ago
    You order your operations by depth.
    • david-gpu 2y ago
      If only it was so simple. You typically don't have the memory capacity and computational budget to sort and render the whole scene back to front. You can use bucketing and other tricks to try and do a better job, but at the end of they day it is just impractical. This method has been studied for decades and it is still not in common use.
      • adastra22 2y ago
        Are we still talking about 2D raster libraries (TFA)?
        • david-gpu 2y ago
          It makes no difference.
• agumonkey 2y ago
  Anybody has a link to a non interactive paper or article about this. It turns my smartphone into paperweight. I assume memory pressure or webgpu failing.
  • deleted 2y ago
    [deleted]
• kens 2y ago
  I'm surprised that the article doesn't mention Fourier transforms and neither do any of the comments. All the talk about aliasing and different filters makes a whole lot more sense if you take a look at the frequency domain. (Unfortunately I don't have time to elaborate here. But Fourier transforms are so useful in many ways that I encourage people to learn more.)
  • raphlinus 2y ago
    If you want to go hardcore into the frequency domain, may I suggest "A Fresh Look at Generalized Sampling" by Nehab and Hoppe[1]. That said, while a frequency-centric approach works super well for audio, for images you need to keep good track of what happens in the spatial domain, and in particular the support of sampling filters needs to be small. [1]: https://hhoppe.com/filtering.pdf https://hhoppe.com/filtering.pdf
• SCLeo 2y ago
  Is this website freezing for anyone else? EDIT: yes it is.
• 3n_scanline 2y ago
  For comparison, Tom Duff has just made available a copy of his 1989 paper "Polygon scan conversion by exact convolution" which uses more or less the same mathematical trick. It involves a scanline algorithm and avoids polygon clipping. http://tomduff.com/conscan.pdf http://tomduff.com/conscan.pdf