Hacker News Reader

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

oh yes, I was soo amazed (and still I am!) when I've first learned about this! Really clever work!

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.

You can use Jump Flood Assignment to compute the distance field in parallel. See: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.101...

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.

That is really awesome, thank you.

Author here. That's a neat trick!

> I mention this because the mystery of the getDistance() function is often one of the tricky parts of demos like these.

I agree! In the demos I use a library I wrote to generate 2D distance fields: https://github.com/ryankaplan/gpu-distance-field

It's also pretty fast :)

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.

I don't get it how would this help you to write a function to get distance to a shape from any point on a canvas.

Edit: oh wait, you measure the pixel color :) nice

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.

I'd love to be proven wrong on this :)

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.

The advantage of this approach is that it achieves an approximate result in a single sample.

You might require dozens of samples to get a similar result using a multisampling technique like you describe.

If you want to run this in real time on a phone, ray tracing is expensive.

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/

Thanks! I've learned a ton from iq's writing. He's such an inspiration!

I find that his articles are best for folks who already know a thing or two about computer graphics. Here's a post that I think is pretty good for beginners: http://jamie-wong.com/2016/07/15/ray-marching-signed-distanc...

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

graphics.ts:822:14

firefox, ubuntu 20.04

Thanks! I just pushed a fix. Does it work now?

no its still broken, different errors now. you should look into adding metrics so you dont have users doing this for you

Uncaught Exception { name: "NS_ERROR_FAILURE", message: "", result: 2147500037, filename: "https://ray-marching-talk.netlify.app/src.c9ac1cf4.js", lineNumber: 20, columnNumber: 0, data: null, stack: "k@https://ray-marching-talk.netlify.app/src.c9ac1cf4.js:20:425... } canvas-scene.ts:1

Uncaught Exception { name: "NS_ERROR_FAILURE", message: "", result: 2147500037, filename: "https://ray-marching-talk.netlify.app/src.c9ac1cf4.js", lineNumber: 28, columnNumber: 0, data: null, stack: "t@https://ray-marching-talk.netlify.app/src.c9ac1cf4.js:28:748... } app.ts:269

Failed to get uniform location

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.

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

Thanks! I just pushed a fix. Does it work now?

Uncaught ReferenceError: TouchEvent is not defined

You're on Safari, aren't you?

Firefox

Whoops, just pushed a fix! Does it work now?

Yes, thanks a lot! The demos are fun and interesting.

Ray Marching Soft Shadows in 2D