From Distance Functions to Shadows

Goal

Define a shape with only a distance function, find the surface with sphere tracing, find normals from the gradient, and even add shading and shadows. The last picture of this path comes out here.

Why it matters

Rasterization presupposes triangles. To change a shape you have to rebuild the vertices, and merging or subtracting two shapes is a geometric operation and therefore tricky. A distance function expresses a shape as a formula — a sphere is one line, and a union is one line of min.

And the single property that the value is a safe distance to advance makes the whole algorithm work. If the nearest surface is d away, nothing exists for d in any direction, so even if you jump the ray ahead by that much in one go, you cannot pass the surface. The normal is found from the gradient, and a shadow takes just one more ray. Things that needed separate data structures and several stages in rasterization are solved here with the same single function.

Steps

Put the toolbox in /root/raymarch.
/root/raymarch/sdf.py — distance functions and combination operations.
/root/raymarch/march.py — sphere tracing.
/root/raymarch/out/sphere.png — the silhouette.
/root/raymarch/out/shaded.png — gradient normals and Lambert.
/root/raymarch/out/csg.png — a shape carved and joined.
/root/raymarch/out/shadow.png and out/07-shadow.txt — shadow rays.

Notes

Start a server with nohup python3 -m http.server 8080 -d /root/raymarch/out & and open http://localhost:8080/ in the Web preview.
At 160x160 there are 25,600 rays. Even in Python it takes under 1 second per picture — because the distance function jumps far through empty space.
Common mistake 1: starting the shadow ray right on the surface. It hits itself at the first step and every pixel ends up in shade.
Common mistake 2: the distance function returning a value larger than the real distance. The ray jumps over the surface and holes appear.

Put the drawing toolbox in place

Save /root/raymarch/gfxlib.py exactly as in the example, and use /root/raymarch/check.py to draw a test pattern and make /root/raymarch/out/00-check.png. The pattern is a 64x64 black background with a white (255,255,255) diagonal line from (0,0) to (63,63), and over it a red (255,0,0) horizontal line from (0,32) to (63,32).

From this lab on, you do not rebuild the PNG encoder. We hand you the same code you built by hand in the first lab as a tool — because file formats are not what you learn here.

The lab Pod has no volume, so the files you made in the previous lab are not kept. That is why each lab starts by putting the toolbox in place again.

Create Canvas(w, h, bg), draw the two lines with line(x0, y0, x1, y1, rgb), and then save with write_png(path). Draw the horizontal line later, so that the intersection (32,32) becomes red.

In this lab you use it to export the result of shooting a ray per pixel as pictures.

Distance functions and combining

In /root/raymarch/sdf.py, make sphere(p, r), box(p, b), plane_y(p, h), op_union(a,b), op_intersect(a,b), op_subtract(a,b) and smooth_union(a,b,k). For the box, let q = abs(p) - b and use length(max(q,0)) + min(max(qx,qy,qz), 0), the subtraction is max(a, -b), and the smooth union is b*(1-h) + a*h - k*h*(1-h) for h = clamp(0.5 + 0.5*(b-a)/k, 0, 1).

A signed distance function is negative inside, positive outside, and 0 on the surface. A sphere satisfies that property with the single line length(p) - r.

The reason the box's expression has two terms is that it treats outside and inside separately. Outside, it takes each axis's excess as a vector and measures its length, and inside, it uses the distance (negative) to the nearest face.

What the -b in the subtraction means is flipping the inside and outside of b. The intersection of the flipped b and a is "a with b carved out".

The last term -k*h*(1-h) of smooth_union swells the joined part to make it smooth. Without this term it is just linear interpolation, and the seam stays angular.

Sphere tracing

In /root/raymarch/march.py, make march(ro, rd, scene, max_steps=64, max_dist=20.0, eps=0.001). Starting from t=0, find d = scene(ro + rd*t), and if d < eps, return (True, t, 걸음수) (the placeholder is the step count), and if t > max_dist, return (False, t, max_steps). Otherwise advance with t += d.

The value the distance function gives you is a distance that is safe in any direction. So even if you jump ahead by that much in one go, you cannot pass the surface. This is the whole reason this algorithm works.

In empty space it jumps far, and near a surface it approaches a little at a time. That is why a ray that grazes the surface is the most expensive — the steps are cut fine.

If you shoot from (0,0,-5) in the direction (0,0,1) toward the sphere of radius 1 at the origin, t stops near 4. It is not exactly 4 because there is an error of eps.

Return the step count too. In the next step you can use it to see the cost with your own eyes.

The silhouette first

Use /root/raymarch/render.py to make the 160x160 picture /root/raymarch/out/sphere.png. The camera is at (0,0,-4) and the ray direction for pixel (x,y) is normalize((px, py, 1.5)), with px = (x+0.5)/160*2 - 1 and py = -((y+0.5)/160*2 - 1). The scene is only a sphere of radius 1 at the origin, and a hit is white (255,255,255) and otherwise black.

The minus on py is because y in an image grows downward. It is the same problem that has kept coming up in this path.

1.5 corresponds to the focal length. If it is larger, the view narrows (telephoto), and if smaller, it widens (wide angle). It is the same thing as the field of view in the previous course, written a different way.

At 160x160 there are 25,600 rays. Even in Python it finishes in under 1 second — because the distance function jumps far through empty space.

The circle's diameter should be about half of the screen. If it is much smaller or larger, check the camera distance or the focal length.

Find the normal from the gradient

Use /root/raymarch/shade.py to add shading to the same sphere and make /root/raymarch/out/shaded.png. The normal is found from the distance differences along each axis with e=0.001 and normalized, the light is normalize((-0.6, 0.7, -0.5)), ambient is 0.15, the base color is (230,180,120), and the brightness is ambient + (1-ambient)*max(0, dot(n, l)).

The gradient of the distance function is the normal. This is because the direction in which distance grows most steeply is the outward direction of the surface. Not needing to store the normal separately is one of the advantages of this method.

For each axis, compute scene(p + e) - scene(p - e). It is a central difference, so you call the distance function twice per axis, six times in all.

If you make e too small, floating-point error grows, and if you make it too large, the normal gets smeared. 0.001 suits a scene of this size.

The hit point is ro + rd*t. The light comes from the upper left, so the upper left of the sphere should be bright.

Carve and join shapes

Use /root/raymarch/csg.py to draw the following scene to /root/raymarch/out/csg.png. Make a cube with rounded edges with base = op_intersect(box(p,(0.85,0.85,0.85)), sphere(p,1.1)), carve out the front face with base = op_subtract(base, sphere(p-(0,0,-1.0), 0.6)), and then join a small sphere smoothly with smooth_union(base, sphere(p-(1.0,0.9,0.0), 0.45), 0.35). The shading is the same as in step 5.

Look at what each of the three operations does. The intersection keeps only the part where the two shapes overlap, rounding the edges, the subtraction digs a hole, and the smooth union melts the seam.

Changing the shape is simply changing the formula. You do not need to rebuild a vertex buffer or an index buffer. To do the same thing with triangles, you would need a geometry-operations library.

For a sphere moved to another position, write sphere(p - 중심, 반지름) (the placeholders are the center and the radius). Measuring with the point moved is the same as moving the shape.

Use the render(scene, path) you made in step 5 as it is, changing only the scene function.

Shadow rays

Set the scene to op_union(sphere(p,1.0), plane_y(p,-1.0)), and from a spot lifted 0.02 along the normal from the hit point, march again toward the light with max_dist=10.0, and if it hits something, apply only ambient. Write the result to /root/raymarch/out/shadow.png and write three lines to /root/raymarch/out/07-shadow.txt: hits=, shadowed= and fraction=. fraction is shadowed / hits.

A shadow takes just one ray. From the hit point you march again toward the light, and if it hits something, it is in shade. All the problems you run into with rasterization, baking a shadow map and transforming coordinates, are absent here.

Lifting slightly along the normal is important. If you start right on the surface, it hits itself at the first step and every pixel ends up in shade. This problem is called shadow acne, and it appears under the same name in rasterization shadow maps.

A floor plane has been added, so the bottom of the screen is the floor. You should see the ball casting a shadow on the floor.

The shaded fraction is around 6 percent. If it is much larger, the lift is insufficient, and if it is 0, the shadow ray always misses.