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

71–80 of 86 posts

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

#71

Post by muyyatin2 »

raphlinus wrote: post #70
muyyatin2 wrote: post #60

Earlier quoted context omitted.

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.

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, o…

I'm curious what your thoughts are on my approach for robustness.

I've written similar operations[1] that include elliptical arcs AND Bézier curves, and robustness has been an issue. An assortment of polygon clipping approaches use ONLY line segments and fixed precision numbers to work around this.

If I discretize the line segments to 20bits (fixed), potentially in tiles (to reduce inaccuracies), then I can represent exact rational intersections (and parametric t values) with 64-bit numerators and 64-bit denominators[2].

This significantly concerns me about computation cost (and memory if I need to store them), but using this scheme to ensure absolute correctness (and ordering) of intersections does seem to work in CPU proof-of-concepts. Perhaps it is possible to only use this expensive method to disambiguate if it cannot be done from floating-point numbers.

My initial GPU concept imagined a sorting of intersected segments, however a radix sort over a 128-bit object seems like a non-starter, and if I try that, a merge sort may still be viable?

Thank you for the links and recommendations!

[1]: https://github.com/phetsims/kite

[2]: https://github.com/phetsims/alpenglow/blob/main/js/webgpu/wg...

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

#73

Post by david-gpu »

adastra22 wrote: post #61
david-gpu wrote: post #41

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…

You order your operations by depth.

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.

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

#74

Post by eru »

fjkdlsjflkds wrote: post #56
rty32 wrote: post #31

Earlier quoted context omitted.

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.

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.

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

#75

Post by eru »

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)

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.))

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

#76

Post by Klaus23 »

muyyatin2 wrote: post #10
rsp1984 wrote: post #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?

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).

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?

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

#77

Post by adastra22 »

david-gpu wrote: post #73
adastra22 wrote: post #61

Earlier quoted context omitted.

You order your operations by depth.

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.

Are we still talking about 2D raster libraries (TFA)?

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

#78

Post by rty32 »

eru wrote: post #75
rty32 wrote: post #31

Earlier quoted context omitted.

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)

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 th…

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.

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

#79

Post by rsp1984 »

dahart wrote: post #47
rsp1984 wrote: post #44

Earlier quoted context omitted.

OK, so reading a bit further this boils down to clipping the polygon to the pixel and then using the shoelace formula for finding the area? Why call it "box filter" then?

It’s very useful to point out that it’s a Box Filter because the article moves on to using other filters, and larger clipping regions than a single pixel. This is framing the operation in known signal processing terminology, because that’s what you need to do in order to fully understand very high quality rendering. Dig a little further into the “bilinear filter” and “bicubic filter” that follow the box filter discus…

OK, I get it now. Thanks for the explanation. I would just never in a lifetime call it a "filter". That's extremely poor naming.

If they called it a choice of basis or influence function, it would've been so much clearer.

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

#80

Post by taylorius »

bee_rider wrote: post #36
taylorius wrote: post #21

Earlier quoted context omitted.

Anything is constant colour if you dice it up into small enough pieces! :-)

Is that necessarily the case for vector graphics? I actually don’t know how they define their colors. It seems intuitive enough to define a gradient using a function rather than discrete series, but I have no idea if anyone actually does that.

They absolutely do define gradients via functions - but the point it, the screen only has a finite number of pixels. As I understood it, pixels is what this technique uses as it's dicing primitive. Pixel sized rectangles cut out of the polygon.

Pixar's Renderman used to use a (slightly) related technique. This was along time ago, and I have no idea if they still do things this way - but they would subdivide patches until each primitive was smaller than a pixel.

Post reply on HN