About the 4-point DE

[JosLeys]

In my attempts to do a better raymarching algorithm in Ultrafractal, I came across the following:

I'm trying to do hybrid fractals without a known analytical DE, so the only option is to use the "four point DE".

It is normally implemented as iterating four points : <x,y,z> (the point on the ray, <x+eps,y,z>, <x,y+eps,z> and <x,y,z+eps>  where eps is a very small number, for instance 10^(-9).
At bailout we have four values for the distance of the iterated point to the origin : R, Rx, Ry, Rz.
The gradient at the point in question is then G=<(R-Rx)/eps, (R-Ry)/eps, (R-Rz)/eps> ( and if normalized, this can be used as the surface normal)

The distance estimate (DE) is then normally calculated from R*log(R)/dR/2, where dR is the length of G.

Two things :

- I find that taking DE=R/dR/2 works just as well and avoids calculating the log function. This is probably cheap in most programs, but every little bit counts!
  ( I find that R*log(R)/dR/8 and R/dR/2 are about equivalent in most cases) 

- Maybe more importantly, the dR vector also gives us an approximate direction towards the closest point on the fractal.
  If this direction is not straight ahead along the ray, we can get away with a bigger fudge factor on the DE!
  Normally one calculates DE and then advances on the ray with a distance DE*ff (ff=fudge factor <1) .
 The cosine of the angle between the ray being marched (along a normalized vector V) and the direction of the closest point is a=dot (V. normalize(G))

We can then take the step on the ray, for instance as step=DE*newff, with newff=ff+(1-ff)*(1-(a+1)/2). (other variations are possible)
This would mean that the fudge factor is indeed the original ff if a=1 (the angle between the ray and the closest point vector is zero : the 'wall' is straight ahead)
If a=0 (the angle is 90°, we are passing parallel to a wall) the ff becomes 0.5*(1+ff). ( if the ff was 0.5 originally, it will then be 0.75)
If a=-1, meaning the 'wall' is directly behind us (which will not happen in practice), ff becomes 1.

Now all this is only useful if ff<1. (if ff=1, newff=ff=1) The smaller ff, the more we gain.
I find in my UF implementation that with ff=0.5, rendering time is 35% shorter. With ff=0.25, the gain is 60% !

I would be very happy if somebody could confirm these results in other programs besides UF ( M3D, Fragmentarium, Mandelbulber...)

[Syntopia]

That's a nice idea.

It reminds me of something we discussed some time ago her on the forum: instead of dividing by the length of the gradient, why don't take the derivate in the direction of the ray, and divide by the length of that? (essentially Newtonian root finding). It seems strange that DE's must be non-directional.

[JosLeys]

The directional derivative would imply taking two nearby points in the ray being marched on instead of the four points. This goes back to Dave Makin's original 'delta DE' idea.
The drawback of this is that we now have no gradient that gives us the surface normal, and we need to shoot  at least two adjacent rays to get the normal from a vector cross product.
On the other hand, if the directional derivative would give a more accurate DE, then there are less steps on the ray, and the overall result could be beneficial.

I have not tried it yet..

[David Makin]

The idea of modifying the DE based on the directional density should work - in fact the same idea applied to analytical DE may also be optimal even with the extra calcs. involved

Personally I'm more interested in a foolproof general (non-analytical) method that will correctly handle discontinuous changes in the potential density - e.g. where there's a hard break that cannot be smoothed - such as in many fractals involving conditionals and in escape-time IFS.
One alternative is to use Ron's "exp" smoothing as a 4-point method but that *is* expensive due to the per-iteration overhead and maybe won't work with escape-time IFS (not sure).

[Alef]

I don't know nothing about DE, but there are some simple recriprocal colour algorithms simmilar to exp smoothing, one were in kaliset thread. If Exp smoothing can be used for DE, so maybe alsou some other  sum=sum 1/function(z) type with  computation less expensive function.

[Jesse]

Just did some tests, but i have not disabled the small corrections for the DE that are integrated in m3d, so this is not absolute objective 

Used an older kind of testimage proposed by David that gives nice overstepping results for thin planes in various directions.

The attached image shows in the top left corner the default renderer with a fudge factor of 0.3 and the internal DE corrections, that are:
if DE > LastDE + LastStepWidth then DE = LastDE + LastStepWidth
and a fudgefactor decreasement for the opposit case (maximum halve the FF), got the exact formula not in my mind yet but it doesnt got much effect here.

On the right side you see the modifications with a multiplier of 0.5 for the (1- FF) term, so the overall FF can reach up to 0.65.
I just verified the maximal gradient of the 3 directions and calculated the dotproduct for this direction and the actual ray.
In the lower right image i inverted the modification just to see what what happens (instead of (0.5 - 0.5 * dotp) i used 0.5 * dotp).
It shows clearly the advantage in speed over quality that you should do it as proposed 

Of course, in all images i used the internal m3d corrections over this modified fudge factors.

But what i would say while done also some attempts for speed improvements is, that if you got bad DE's, you also can't rely on specific gradients or so that are part of the bad DE, so you better rely on well known issues, like if the DE is bigger than the Last DE plus the raystep, you really know that something is wrong 

[JosLeys]

Your last comment is important Jesse.
I also found in the meantime that for certain hybrid combinations the speedup scheme fails : too many overshoots, supposedly because the DE in those cases is too inaccurate.
For others it works quite well...