muyyatin2

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

This is correct! My CPU implementation of this code can handle the overlapping polygons / meshes / textures. https://phetsims.github.io/alpenglow/#depthSort (takes forever to load, sorry!) is an example of using the analytic approach to render a phong-shaded teapot, where it splits things into adjacent but non-overlapping polygons (from a source of VERY overlapping polygons).

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.

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.

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

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!

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.

Do you have some links/references for someone wanting to learn more about this?

I saw an analysis for a four-word blind combination, but I believe it didn't fully determine the word by the 5th guess: http://www.garytay.net/4-words-to-win-wordle-in-less-than-a-...