Shortcut geometric series when ray-marching towards a surface

[henryseg]

We might be able to save some ray-marching steps when we are approaching a surface.

If we come into the surface at right angles, the SDF tells us precisely how far to go to hit the surface, so we get there in one step. When we come in at an angle though, we have to go through a geometric series, getting closer and closer, until we get within epsilon and have reached the surface.

The idea is to recognize when we are in this kind of situation, and jump straight to the end of the geometric series, where we are either at the surface or have got past the point where we are almost tangent to the surface.

To do this, we need to record three results from the SDF in a row. Let's call them d0, d1 and d2. We have moved along the ray by d0 and d1, and we are about to move by d2 unless we decide to jump to the end. Whether or not to jump depends on a number of checks, which depend on some small values (delta, delta' below), which we will have to tune.

So, we need a bunch of things to be true to jump, in a big if statement:

(d2 < delta) // we are pretty close to the surface
(d0 > d1 > d2) // and we are getting closer
abs(d1d1 - d0d2) < d1d1delta' // the three distances are forming a geometric sequence

If so, then instead of stepping forward by d2, we "jump" forward by

d2/(1 - lambda),

where lambda = (d1d1+d0d2)/(2d0d1) // the average of the two geometric factors we have.

Multiplying out the above, we get that we jump forward by:

2d0d1d2 / ( d0(2d1-d2) - d1d1 )

We should probably limit this so that there is a max possible value for the jump. So jump by the min of the above value and, say, K*d0? (K is another magic number... maybe 10 or 20 is reasonable.)

[henryseg]

Thinking again, it's better to use

lambda = d2/d1

I think it should be a better estimate of the future behaviour of lambda than something involving d0, unless we want to look at order 2 behaviour as well - I'll think about this.

With this value of lambda, we jump forward by:

d1 * d2 / (d1 - d2)

[henryseg]

We tried this, it turned out to go from 60fps to around 64fps when the choices of delta were small enough to make no difference to the visuals on the simplex cuts mode. So not worth the added complexity in the code.