Rendering 3D fractals without distance estimators

[Syntopia]

It is not always easy to come with a distance estimator for a 3D fractal. I've seen quite a few requests for drawing fractals, where the defining function only tells you whether you are inside or not for a given point, e.g. functions defined by:

bool inside(vec3 point);

I decided to try out some simple brute-force methods to see how they would compare to the DE methods. Contrary to my expectations, it turned out that you can actually get reasonable results without a DE.

The method I used was to just simply sample random points along the camera ray for each pixel. Whenever a hit is found on the camera ray, the sampling wil proceed on only the interval between the camera and the hit point (since we are only interested in finding the closest pixels). This way you end up with a depth map, like:



In order to improve the quality, I then calculated surface normals from the depth buffer and pixel positions, and used this to do a standard Phong shading. I also applied a simple screen space ambient occlusion (and glow) pass to improve depth queuing. This results in:



You can do this at interactive frame rates in Fragmentarium, and I further improved responsiveness by using progressive rendering: do a number of samples, then storing the best found solution (closest pixel) in a depth buffer (I use the alpha channel), render the frame and repeat.

I'll add the brute-force tracer to the Fragmentarium repository, as soon as the script is cleaned up a bit.

[eiffie]

Thanks for all your work! This will be great for trying new functions. I remember my first renderer was brute force but not nearly with these results. Glad you gave it another look.

[hobold]

Wow, this works much better than I would have expected. Great find! Hmm ... I wonder if some statistical techniques could be used here? I.e. controlling the randomness a bit, to speed up convergence towards the "exact" solution ...?

[Kali]

Great!

Currently I'm using accumulative fixed-step raymarching for trying out weird 3D formulas without using a DE, like in this "3D-rotated Julia" :



But I always wanted a solid shader for formulas without DE, and I was thinking of modifying your fragmentarium default raytracer to do this (or at least trying to).

I'm glad you already did it, and that it works so good! Can't wait to try it.

[M Benesi]

The method I used was to just simply sample random points along the camera ray for each pixel. Whenever a hit is found on the camera ray, the sampling wil proceed on only the interval between the camera and the hit point (since we are only interested in finding the closest pixels).

  This sounds similar to what ChaosPro does.  There are a couple cool ideas here in the documentation  (click for documentation).  Read the "Resolution", "Start Scan", and "Precision" parts.  

  It makes ChaosPro an excellent piece of software to quickly whip up a new 3d formula, without having to do the extra math to whip up a DE, especially with some of these crazy formulas....

[Syntopia]

Wow, this works much better than I would have expected. Great find! Hmm ... I wonder if some statistical techniques could be used here? I.e. controlling the randomness a bit, to speed up convergence towards the "exact" solution ...?

I think it could.  I already found that a stratified approach, where the camera ray segment is divided into equal pieces and a sample is choosen from each part reduces noise. You could also probably gain speed by sampling closer to the found solution. Since I use  double buffered progressive rendering approach, at the start of each frame, I could actually read the adjacent pixel depth and sample closer to these. On the other hand, if you bias the search you are probably more like to miss subtle details closer to the camera.

Also the function I use for random numbers:

Code:

float rand(vec2 co){
	// implementation found at: lumina.sourceforge.net/Tutorials/Noise.html
	return fract(sin(dot(co.xy ,vec2(12.9898,78.233))) * 43758.5453);
}

is quite primitive, and will show visible artifacts. There is no easy solution in GLSL here: I probably should use a precalculated texture with random values (I do have a floating point texture loader), but I'm too lazy.

Currently I'm using accumulative fixed-step raymarching for trying out weird 3D formulas without using a DE, like in this "3D-rotated Julia" :

I know :-) Actually I decided to try this, because I saw that you were able to succesfully use brute-force fixed step rendering on your great volumetric renders. The worst part about these brute-force solids, is that you need to rely on screen space lighting - this introduces artifacts: e.g. when you do tile rendering you get visually transitions near the border of the tiles.

  This sounds similar to what ChaosPro does.

Yes, it seems to the same approach - I just don't choose a fixed step size, so there no bounds to the resolution: the image will converge towards the true set.

Just to make it clear: brute force ray tracing is not a novel idea - it was indeed the simplest method I could think of. What is perhaps surprising, is that it is fast enough to achieve interactive frame rates on a GPU.

[subblue]

Very interesting. I'm curious how the number of steps for the brute force approach differs from the DE method?

[KRAFTWERK]

Wow! I've always wanted to test brute force renders of the mandelbulb "to see what it REALLY looks like".
The mandelbulb you rendered have such beautiful details Syntopia.
Got to try out fragmentarium again!

[Syntopia]

Very interesting. I'm curious how the number of steps for the brute force approach differs from the DE method?

There are no steps as such - you just choose a number of samples on the ray for each camera ray. A fractal such as the Mandelbulb becomes recognizable/navigatable at about 50 samples, and has a good resolution at ~500-1000 samples.

Wow! I've always wanted to test brute force renders of the mandelbulb "to see what it REALLY looks like".
The mandelbulb you rendered have such beautiful details Syntopia.
Got to try out fragmentarium again!

Thanks Kraftwerk. There is still no guarantee that you won't miss detail, though - subtle and thin structures may be overlooked in the sampling process. So it is still just an approximation.

Btw, here is another test with Aexions MandelDodecahedron:

[hobold]

And shouldn't this randomized brute force method be effective for robust computation of inside views? It wouldn't be as fast, of course, since most samples iterate to the limit, but perhaps still fast enough.

[Syntopia]

I've written a blog post with some more information and links to code:
http://blog.hvidtfeldts.net/index.php/2012/09/rendering-3d-fractals-without-a-distance-estimator/

And shouldn't this randomized brute force method be effective for robust computation of inside views? It wouldn't be as fast, of course, since most samples iterate to the limit, but perhaps still fast enough.

Yes, just tried it, and it works nicely. Just invert the 'inside' function. As you say, it is a lot slower (~3-4x), since all pixels tested are inside.

[cKleinhuis]

nice, i like it very much, this way it is far more easier to try out hillarious new functions, thx for keeping the program in steady development!

[hobold]

About quick and dirty random number generation ... can't we use a chaotic iterated function for that? Like Feigenbaum's logistic map at parameter value 4, or something like that. Quick to compute, and guaranteed to be chaotic. That might be good enough.

[Kali]

About quick and dirty random number generation ... can't we use a chaotic iterated function for that? Like Feigenbaum's logistic map at parameter value 4, or something like that. Quick to compute, and guaranteed to be chaotic. That might be good enough.

Back in my early programming experiences, I developed a random number generator based on irrational numbers... I'll try to remember how it worked, but I think the single precision limitation could be a problem.

[Kali]

Ok, I just tested the raytracer with my "rotjulia" formula, and I'm very excited with the result:




This is the "inside" function for using with the tracer:   (requires complex.frag and mathutils.frag)

Code:

bool inside(vec3 z) {
	mat3 rot=rotationMatrix3(normalize(RotVector),RotAngle);	
	int i=0;
	float r;
	while (i<Iterations) {
		z.xy=cMul(z.xy,z.xy);
		z*=rot;
		z+=JuliaC;
		r=length(z);
		i++;
             if ( r>Bailout) {
			return false;
		}
	}
	return true;
}

This algorithm takes x and y coordinates as a complex number, squares it, does a 3D rotation and adds julia constants.



Too bad the lighting doesn't work well with tiled large renders, but it's an awesome tool for exploring new formulas and ideas...

Thanks Mikael, good job!!