Not to keep flogging my own work, but something kinda similar is my blurred rounded rectangle shader[1]. That is super-fast and produces very nice smooth shadows, but is limited in the shapes it can blur because it uses tricks that make a lot of assumptions about them. I also prototyped light sources other than gaussian, specifically disk, and I think that generalizes pretty well.
Given that the original article is blurring glyphs, one thing that might be worth exploring is decomposing the glyph into primitive shapes. For example "b" can be a rect for the stem, an ellipsoid for the main bowl, and another ellipsoid (with negative sign) for the inner countour of the bowl. It doesn't have to be perfect because you're only rendering the blurred shapes. And no doubt you could have some kind of automated process that refines the decomposition when it can use more primitive shapes.
Though our techniques are different, it's interesting (and not terribly surprising) that they both use some of the same techniques under the hood, specifically distance fields, and that we cite some of the same people.
I should mention that of course shadows and blurs are not the same thing, but sometimes you can use one for the other in a pinch :)
The algorithm discussed here reminds me very much of the "Line of Sight" problem.
Line of Sight is calculated on a 2-d topographical map, where each 2d point is a height-map. The question is: does location "X" have a line-of-sight to location "Y" ?? You solve this question by marching rays from X towards Y, and seeing if any intermediate 2d point has a height that would block the sight.
I bring this up because line-of-sight has been SIMD-optimized and is highly efficient to calculate now. Line-of-sight is similar enough that the large body of research behind that problem can probably serve as inspiration to algorithms in this 'ray marching shadows' algorithm.
Its quite possible that your calculation here is "just" a 2-value line of sight: where 0 means "sight is not blocked" and 1 means "sight is blocked".
------
Ray Marching itself seems innately "sequential", because you need to calculate the closest "solid object" to know how far to march.
In contrast, the naive "try every pixel" approach is easily parallelized if you understand prefix-sum style computations (see: https://en.wikipedia.org/wiki/Prefix_sum). If you could easily group pixels into 1-bit objects (see PEXT or PDEP: https://www.felixcloutier.com/x86/pdep), I'm sure that a SIMD-parallel version would be outstandingly fast to compute for "small" 256-pixel (aka: AVX2) bit-vectors.
-------
EDIT: Now that I think of it: the computation of the distance field is likely sequential. But the use of the distance-field is probably read-only / parallel. A SIMD-line of sight style algorithm using the distance field could be "scheduled" using a sequential algorithm, but then computed with SIMD techniques.
There’s a simple trick you can use if you want to generate the distance field for text or simple shapes in the browser. The way you do it is by repeatedly drawing the text with strokeText, varying the stroke width and the stroke color.
For example, you fill the background with 100% white, and then draw a 10px stroke at 90% gray, 9px at 80%, 8px at 70%, etc. This is, most importantly, an extremely fast way to generate a distance field for text from JavaScript in the browser.
I mention this because the mystery of the getDistance() function is often one of the tricky parts of demos like these.
Computing distance fields with a jump flooding approach in O(n log n) is neat, but there is a O(n) algorithm, which might be faster https://prideout.net/blog/distance_fields/
Neat! In my experience jump flooding on the GPU is faster than any CPU side approach for images bigger than a few hundred pixels. It's O(n ^ 2 log n) which sounds really expensive, but it requires just O(log n) draw calls.
The link you provided also describes a GPU amenable approach, but it says that jump flooding on the GPU is faster.
> For a more efficient GPU-amenable method, see also jump flooding by Rong and Tan. Their method generates a closest point coordinate field from which a distance field can be derived.
nice! but why don't you just calculate soft shadows the way they occur physically by sampling an area light source instead of a point light source? You can basically run the same algorithm again and again with light source points in a circle from the center of the light source, then alpha-fuse them together? Am I missing something?
There are definitely more physically accurate ways to render soft shadows, but AFAIK they all involve some kind of bounce lighting where light bounces off of objects in the scene and indirectly lights other parts of it.
This looks great when combined with area light sources, like you suggest, but in my experience it's too slow for interactive demos.
The parent is saying that you can simply do the hard shadow algorithm but n times, starting from n random points uniformly sampled from a disk around the original point light source, then averaging the result. The bigger the disk the softer the shadow. This is how soft shadows are often achieved in ray tracing.
Ah, thanks for clarifying! I think someone already called this out above, but the benefit of the approach I describe is that you only need one sample per pixel. Four samples per pixel starts to feel pretty slow on my machine, and I suspect you'd need more than that to make the averaging approach look good.
One option might be to render, say, two samples per frame, and keep the previous samples when the light source doesn’t move. The shadows would be noisy while the light is moving, but quickly look smoother when it stops.
I can’t seem to find the PDF of Brent’s siggraph sketch in 2006 (Shadow map bias cones), but our follow up work [1] hopefully makes the connection between distance and r^2 clear: these techniques are all computing some sort of solid angle and filter width from that.
As Raph is mentioning in a side thread, there are lots of assumptions! (Some of them similar to the randomized assumptions behind alpha, generally).
On my Mediatek device, each demo worked great... Until I scrolled up the screen and then suddenly I saw a "Chrome error icon" in the demo... I refreshed the page and the demos were replaced with white boxes. I killed and restarted chrome and now the demos appeared to work till you interacted with them and they became black boxes.
Had to restart the phone to regain full functionality.
Uncaught Error: Failed to get uniform location for name O
get graphics.ts:822
value graphics.ts:950
value graphics.ts:1234
value graphics.ts:493
value renderer.ts:355
value renderer.ts:471
onFrame app.ts:631
t app.ts:501
QCba index.ts:4
QCba index.ts:3
f src.515687e2.js:1
parcelRequire src.515687e2.js:1
<anonymous> src.515687e2.js:1
I just pushed something that will print more info when that error happens. If you or anyone else runs into it again, please post the error here so I can fix it :)
Very cool! I've been working on a little text graphics engine in Common Lisp, using SDF for rendering the text and doing some effects with it. This will be great to add and play with.
Despite the limitations of the "console" the result is quite impressive: https://miro.medium.com/max/384/1*xgIPZgLgcJGBnRhFeJIJLQ.gif