SDF rendering for large world

Question

There are lots of cool things you can do with SDFs to render implicit surfaces. Most of the examples I've seen have been “all in the shader”, where the entire distance function is encoded in the shader source code.

Examples:

• https://www.iquilezles.org/www/articles/distfunctions2d/distfunctions2d.htm
• https://www.shadertoy.com/view/3lsSzf

The problem is that all of those examples assume the shader has total knowledge of the entire world. It evaluates a single distance function, which is complex, but complete.

I want to make a large world (too large to fit in a shader, certainly), and am looking for approaches to render it with the SDF approach.

Does anyone have experience with this? It is 2D-only, if it helps.

The stumbling block seems to be: Since the rendering happens in the fragment shader, I somehow have to transfer “game world” information into that shader. But there do not seem to be good ways to send bulk data to the fragment shader.

Some ideas I have had:

• Write one generic shader that can draw, say, a combination of 500 SDFs.
  • The input to the shader (maybe a UBO?) would contain an encoded version of a piece of the world, with commands like “put a circle at (x,y,radius), do a union with the next object, …” to build the total SDF for that piece of the world.
  • On the CPU side, I'd have to split the world into chunks that could be rendered by that shader, and populate the input data appropriately for each draw call.
  • So for 2D, I might do a tile-based render of the screen, where each tile has “small” amount of data, enough to be handled in the shader.
• Generate shaders on-the-fly, depending on the part of the world I want to render.
  • Here, the shader code would look a lot like the “everything baked in” shaders, but I'd just be generating the code on the CPU.
  • This approach seems bad though, since compiling shaders is a pretty heavy process, in my experience. I did a test with an SDF that was the union of a few thousand circles, and it took 30sec+ to compile.

Any other ideas?

Answer 1

You tile idea seems to be a good one to cut down on local complexity. You can't reasonably evaluate every primitive everywhere. Not if you want good performance anyway. So you need a simplified version for each tile, where you remove elements which have insignificant contribution. This is an interesting problem of its own. A simple version of this would be to:

• Assign each primitive "usefulness bounds" beyond which it is considered 0. What exactly those are will depend on the curves you're using to map distance to world height. To make your life easier, pick something which actually goes to 0 over a finite distance. Or alter your favorite curve so it does.
• For each tile, trim out primitives for which the bounds don't intersect the tile. You can do this with a simple loop to begin with.
• Further simplify the operation tree. This is a little vague because you did not provide details on the kind of operations which will be in your function. But essentially, you want to do the like of replacing $x \times 0$ by $0$ and $x + 0$ by $x$, until you can't anymore. The zeroes come from the previous step where you removed some primitives.

You may need spatial hierarchies if you want this to scale to a world with millions of primitives. This can quickly become a complex topic so I'll leave it at that for now. Ask again when you get there :-)

For your more immediate problem, I suggest using the CPU to rewrite your SDF using reverse polish notation. This will allow you to write your shader as a simple interpreter, with two large buffers as inputs:

• An integer buffer with commands (union, add, multiply, point primitive, segment primitive, etc).
• A float buffer with operands and transforms for the primitives.

The shader is then just a loop over commands which consumes operands as needed. You'll need different command/operand buffers for every tile, obviously. Depending on the typical nature of your SDF, you may find it more efficient to have your primitives always perform union and have an explicit push command for the rare exceptions. There are a lot of ways to go about this really.

You should take care to make sure the resulting SDF can be evaluated with a reasonably small stack as this will be fixed in your shader. This is another problem by itself, perhaps well suited for the computer science SE, but probably not too difficult to solve on your own either.

I'm sorry if I have not provided enough OpenGL specific details but GPUs are not my specialty.