Ray Marching Soft Shadows in 2D

This reminded me of a shadow casting engine for the Pico-8 (https://medium.com/hackernoon/pico-8-lighting-part-1-thin-da...).

Despite the limitations of the "console" the result is quite impressive: https://miro.medium.com/max/384/1*xgIPZgLgcJGBnRhFeJIJLQ.gif

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

[1] https://raphlinus.github.io/graphics/2020/04/21/blurred-roun...

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.

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?

That’s pretty nice. And impressive how this just runs on my iPad Air 2.

For anyone getting interested in distance functions and ray marching, whether it is in 2D or 3D, Inigo Quilez [1] is the authority in this field.

[1]: https://www.iquilezles.org/

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

[1] http://graphics.stanford.edu/~boulos/papers/prefilter_rt08.p...

This shows how broken webgl is on mobile...

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

firefox, ubuntu 20.04

Failed to get uniform location

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.

reminded me of this other tutorial:

https://www.redblobgames.com/articles/visibility/

it's been around for a while now, 2012 I guess

Error: Failed to get uniform location for name O, Firefox on Linux

Uncaught ReferenceError: TouchEvent is not defined