END OF AN ERA, FRACTALFORUMS.COM IS CONTINUED ON FRACTALFORUMS.ORG

Here's a simple optimization that should make mandelbulb rendering a whole lot faster.  A picture is worth a thousand words:



The idea is to use the distance estimation from one step to update multiple rays.  This doesn't help much far from the fractal, but as you get closer and iteration counts go up, it can be a big win.  This makes this method perfect for supersampling and deep zooming.

Another thing to do is trace a cone, rather than a single ray.  You would then spawn new cones at each raymaching step as you got close to the fractal and the cone ends shrink (the base of the cone would be the distance estimation radius).  The idea is to only traverse a single ray for a group of pixels until the fractal is close enough for the distance estimation to not cover all the pixels.

This method, properly implemented, should cause no artifacts, since we're never advancing rays beyond a "proven" empty space through the distance estimation.

The biggest downside to this method is that it doesn't map to GPUs all that well.  You'd have to use a compute shader, and break the image into chunks that are evaluated independently - a simple pixel shader would not be able to extract the full potential of this method.  This isn't to say it cant be done, mind!

Does anyone want to try to implement this and see how well it performs?

has anyone attempted this optimization in his renderer yet? Was there a notable speed benefit?

I am thinking about a slightly refined approach. I would be shooting probe rays from the camera towards the fractal. For every coordinate reached in a DE iteration I would fill an octree data structure with voxel data representing the space that is definitely not part of the fractal (i.e. the volume of the sphere). Of course it will be impossible to exactly represent the "DE sphere" using cubes, but it could be approximated using 3 or 4 levels in the octree (imagine a sphere approximated with Lego bricks)

All further rays can then traverse this volume by using a lookup in the octree instead of interating with the fractal formula. My hope is that this will be significantly faster than applying the iteration formula itself. Only for volumes for which the octree currently holds no data the DE based on the iterative fractal formula must be used (further completing the octree in memory).

Ah, one more interesting detail: Slight changes in camera perspective can re-use the previous frame's octree structure, greatly speeding up the rendering. Only where new details become visible, the octree has to be amended with new data.

I have no idea how much memory this will take, but let's find out! Also I have no idea if the tradeoff of the CPU's arithmetic throughput vs. available memory throughput will pay off.

I'm resurrecting this post because I'd like to tie two similar ideas together, here's someone who ray-marches into increasing resolutions, therefore grouping the rays for the majority of the tracing.

<a href="http://www.youtube.com/v/AtsGeuO_ed8&rel=1&fs=1&hd=1" target="_blank">http://www.youtube.com/v/AtsGeuO_ed8&rel=1&fs=1&hd=1</a>
Note the comments and my questions at the time.

So he's rendering at progressive resolutions, using the depth data from the previous resolution to start the ray at the current one.
Quite neat and very fast.

Laters,
Dave H.

On the note of gradually increasing resolutions, perhaps a good approach would be adjusting epsilon based on the 'size' of a pixel at the current resolution and the potential function at the current location.  It's hard to explain it the way it looks in my head but if you use the derivative with respect to c, and you know that the distance between this ray and it's neighboring ray, than you can guestimate how much deviation there is between the two rays at a certain distance from the camera.  Then, when the expected deviation starts to become large compared to the distance between the neighboring rays, you increase the resolution (and adjust epsilon accordingly). 

This would work best if you could adjust the resolutions of various areas on the screen separately from the others, because then a single ray would only split into more rays once it has encountered a region of high detail.  Unfortunately, it doesn't seem like this would be very practical given current GPU infrastructure.

On a slightly different note, an idea that I've been mulling over for a while is increasing epsilon as distance from the camera increases (I apologize if this has already been done, but on the chance that it hasn't I will elaborate).  It doesn't really makes sense to have an epsilon smaller than the separation between your rays, since any details seen at that scale are inherently an effect of aliasing.  And since the rays become linearly more separated as they get further from the camera, adjusting epsilon linearly with distance would work nicely.  And if the normal vectors are sampled at a distance that is dependent on epsilon, I think this would reduce aliasing as the ray got farther too--making detail fade smoothly away as objects get further.

Much older, actually. In Hart's 1989 sphere tracing paper he talks a bit about constant, linear, and quadratic epsilon (section 4.2):
https://www.cs.drexel.edu/~david/Classes/Papers/rtqjs.pdf

In fact, he also talks about anti-aliasing using DE:
http://mathinfo.univ-reims.fr/IMG/pdf/hart94sphere.pdf