Welcome to Fractal Forums

Fractal Software => Programming => Topic started by: asimes on August 27, 2013, 07:23:47 AM



Title: Buddhabrot optimizations
Post by: asimes on August 27, 2013, 07:23:47 AM
I made a gray scale Buddhabrot renderer in Processing a while ago and am trying it out in JavaScript / Canvas at the moment. I'm using more or less the same idea to try to pre-calculate initial points, trying to see what to do to speed it up. At the moment I am testing with 1,000 as the maximum iteration and am getting 1,000 random points plotted about every 4 seconds. Here's what I'm doing:

1.) Before anything else, run all pixels through the Mandelbrot Set equation to see if they bail or not (don't hit the maximum number of iterations). All pixels that bail are added to an array named nonMSet.

2.) In the function for picking a random point (x, y):
- Randomly pick a pixel (an element) from nonMSet. This is guaranteed to not be in the Mandelbrot Set.
- Convert the pixel to the complex plane as (x, y) = (pixel to real, pixel to imaginary).
- Add a random amount between -0.5 and 0.5 to both x and y (EDIT: I add this amount before converting to the complex plane, the range -0.5 to 0.5 is in pixel coordinates). Doing this means that (x, y) can take on a larger set of values than just the pixels in nonMSet. There is however, a slight risk in that a randomly chosen pixel was right on the boundary of the Mandelbrot Set and the random deviation pushed it in.

3.) Iterating the random point (x, y):
- A temporary buffer named orbitBuffer is made of length w*h where w and h are the width and height in pixels. All elements are initialized as 0.
- A for loop is used to count to the maximum iteration. Inside the for loop I do the typical Mandelbrot equation code and bail if z's magnitude is greater than 2.0. I also bail if z's real or imaginary component goes outside the window. As long as the bail does not happen, I keep track of where z jumped around in pixel coordinates with orbitBuffer.

4.) Storing where z jumped around:
- If the for loop did not reach the maximum iteration then I add orbitBuffer to my pixel buffer. Otherwise the calculation for iterating the random point was a waste (this only happens when the randomly selected pixel from nonMSet was on the boundary of the Mandelbrot Set and the random deviation pushed it in). Luckily it almost never hits the maximum iteration.

5.) Rendering:
- Every time steps 1 - 4 happen 1,000 times I render what is in my pixel buffer. At the moment I am using square root coloring, I am not too worried about speeding that up.

Here is the pre-calculation for finding points that do not belong in the Mandelbrot Set:
Code:
Bbrot.prototype.findMSet = function() {
	// Find all pixels that do not belong to the Mandelbrot Set
	var x = this.xmin;
	for (var i = 0; i < this.pixelLength; i++) {
		var y = this.ymin;
		for (var j = 0; j < this.pixelLength; j++) {
			var zr = x;
			var zi = y;
			
			// Iterate z to determine if it would go to infinity
			var n = 0;
			for (; n < this.maxIterations; n++) {
				var sqZr = zr*zr;
				var sqZi = zi*zi;
				var twoZri = 2.0*zr*zi;
				zr = sqZr-sqZi+x;
				zi = twoZri+y;
				
				// If (i, j) does not belong to the Mandelbrot Set
				if (sqZr+sqZi > 4.0) {
					this.nonMSet.push(i+j*this.pixelLength);
					break;
				}
			}
			y += this.delta;
		}
		x += this.delta;
	}
	
	oldDate = new Date(); // TEMPORARY, JUST FOR SEEING HOW LONG THINGS TAKE
	
	var self = this;
	var orbitCounter = 1;
	canvasInterval = setInterval(function() {
		self.addOrbitTrap(orbitCounter++);
	}, 0);
}

Here is my function that does steps 2 - 5:
Code:
Bbrot.prototype.addOrbitTrap = function(inCount) {
	// Select a random pixel that does not belong to the Mandelbrot Set
	var rIndex = (Math.random()*this.nonMSet.length)|0;
	
	// Add a random amount (-0.5, 0.5) to the pixel and translate to the complex plane
	var x = ((this.nonMSet[rIndex]%this.pixelLength)+Math.random()-0.5)*this.delta+this.xmin;
	var y = (((this.nonMSet[rIndex]/this.pixelLength)|0)+Math.random()-0.5)*this.delta+this.ymin;
	var zr = x;
	var zi = y;
	
	// This will store the orbit trap z produces
	var orbitBuffer = [];
	for (var i = 0; i < this.sqPL; i++) orbitBuffer[i] = 0;
	
	var n = 0;
	for (; n < this.maxIterations; n++) {
		// Determine if a pixel translated from z would be within the canvas
		if (zr > this.xmin && zr < this.xmax && zi > this.ymin && zi < this.ymax) {
			// Translate z to pixel coordinates
			var px = ((zr-this.xmin)*this.pDelta)|0;
			var py = ((zi-this.ymin)*this.pDelta)|0;
			
			// Increment the appropriate element as well as its symmetric element
			orbitBuffer[px+py*this.pixelLength]++;
			orbitBuffer[px+(this.pixelLength-1-py)*this.pixelLength]++;
			
			// Iterate z
			var sqZr = zr*zr;
			var sqZi = zi*zi;
			var twoZri = 2.0*zr*zi;
			zr = sqZr-sqZi+x;
			zi = twoZri+y;
			if (sqZr+sqZi > 4.0) break;
		}
		else break;
	}
	
	// If the randomly selected pixel did not belong to the Mandelbrot Set add all orbitBuffer[i] to this.pixelBuffer[i]
	if (n !== this.maxIterations) {
		for (var i = 0; i < this.sqPL; i++) {
			this.pixelBuffer[i] += orbitBuffer[i];
			if (this.pixelBuffer[i] > this.maxVal) this.maxVal = this.pixelBuffer[i];
		}
	}
	
	if (inCount%1000 === 0) {
		var sqrtMaxVal = Math.sqrt(this.maxVal);
		for (var i = 0; i < this.sqPL; i++) {
			var index = i<<2;
			var pVal = (255.0*Math.sqrt(this.pixelBuffer[i])/sqrtMaxVal)|0;
			this.imageData.data[index] = pVal;
			this.imageData.data[index+1] = pVal;
			this.imageData.data[index+2] = pVal;
		}
		this.canvas.getContext("2d").putImageData(this.imageData, 0, 0);
		
		// TEMPORARY, JUST FOR SEEING HOW LONG THINGS TAKE
		var newDate = new Date();
		debug.innerHTML = inCount+", "+(newDate.getTime()-oldDate.getTime());
		oldDate = new Date();
	}
}

Title: Re: Buddhabrot optimizations
Post by: asimes on August 27, 2013, 08:06:09 AM
After 100,000 loops of addOrbitTrap() I got this:

(http://i.imgur.com/v1Yw2gg.png)

I changed the coloring to:
- Red is linear color
- Green is square root color
- Blue is logarithmic color

At 400 x 400 pixels rendering after every 100 loops of addOrbitTrap() at about ~420 milliseconds (~7 minutes). Waaay too slow but starting to look promising at least.

Title: Re: Buddhabrot optimizations
Post by: asimes on August 27, 2013, 09:27:19 AM
I made a few discoveries, still not where I want to be speed-wise, but I found removing orbitBuffer significantly speeds up the process for larger w*h images (actually I almost not affected by image size now). Turns out that this is faster:

1.) Using the maximum iterations is overkill in many cases. It seems that for high maximum iterations (like 1,000,000) that 1,000 is plenty for a maximum iteration in finding the non-Mandelbrot Set, nonMSet. Upper bounding this step with 1,000 maximum iterations seems to work well. There is a slightly higher chance of a randomly selected pixel with a random deviation to be in the Mandelbrot Set but it still does not happen often.

2.) No Change

3 / 4.) Testing if the randomly selected point with a random deviation is not in the Mandelbrot Set first and then running almost the same code again to increment my pixel buffer directly (instead of using orbitBuffer) is much faster. This kind of makes sense because adding all the elements of orbitBuffer to my pixel buffer is asymptotically Theta(w*h) which is why larger images were so slow for me. The only Theta(w*h) calculation I have now is assigning the highestVal among my pixel buffer's elements which is not that significant. Even though both passes of iterating z are O(maximum iterations), on average this seems to be significantly less than Theta(w*h) for large images.

5.) Only change is that I am using linear, square root, and logarithmic coloring like in the last post.

New code for pre-calculating the non-Mandelbrot Set (almost the same):
Code:
Bbrot.prototype.findMSet = function() {
	// 1,000 is a reasonable non-Mandelbrot Set for higher maximum iterations
	var boundMaxIterations = Math.min(this.maxIterations, 1000);
	
	// Find all pixels that do not belong to the Mandelbrot Set
	var x = this.xmin;
	for (var i = 0; i < this.pixelLength; i++) {
		var y = this.ymin;
		for (var j = 0; j < this.pixelLength; j++) {
			var zr = x;
			var zi = y;
			
			// Iterate z to determine if it would go to infinity
			var n = 0;
			for (; n < boundMaxIterations; n++) {
				var sqZr = zr*zr;
				var sqZi = zi*zi;
				var twoZri = 2.0*zr*zi;
				zr = sqZr-sqZi+x;
				zi = twoZri+y;
				
				// If (i, j) does not belong to the Mandelbrot Set
				if (sqZr+sqZi > 4.0) {
					this.nonMSet.push(i+j*this.pixelLength);
					break;
				}
			}
			y += this.delta;
		}
		x += this.delta;
	}
	
	oldDate = new Date(); // TEMPORARY, JUST FOR SEEING HOW LONG THINGS TAKE
	
	var self = this;
	var orbitCounter = 1;
	canvasInterval = setInterval(function() {
		self.addOrbitTrap(orbitCounter++);
	}, 0);
}

New code for steps 2-5:
Code:
Bbrot.prototype.addOrbitTrap = function(inCount) {
	// Select a random pixel that does not belong to the Mandelbrot Set
	var rIndex = (Math.random()*this.nonMSet.length)|0;
	
	// Add a random amount (-0.5, 0.5) to the pixel and translate to the complex plane
	var x = ((this.nonMSet[rIndex]%this.pixelLength)+Math.random()-0.5)*this.delta+this.xmin;
	var y = (((this.nonMSet[rIndex]/this.pixelLength)|0)+Math.random()-0.5)*this.delta+this.ymin;
	
	// Make sure the random deviation did not push z into the Mandelbrot Set
	var zr = x;
	var zi = y;
	var n = 0;
	for (; n < this.maxIterations; n++) {
		var sqZr = zr*zr;
		var sqZi = zi*zi;
		var twoZri = 2.0*zr*zi;
		zr = sqZr-sqZi+x;
		zi = twoZri+y;
		if (sqZr+sqZi > 4.0) break;
	}
	
	// If z does not belong to the Mandelbrot Set
	if (n !== this.maxIterations) {
		zr = x;
		zi = y;
		n = 0;
		for (; n < this.maxIterations; n++) {
			// Determine if a pixel translated from z would be within the canvas
			if (zr > this.xmin && zr < this.xmax && zi > this.ymin && zi < this.ymax) {
				// Translate z to pixel coordinates
				var px = ((zr-this.xmin)*this.pDelta)|0;
				var py = ((zi-this.ymin)*this.pDelta)|0;
				
				// Increment the appropriate element as well as its symmetric element
				this.pixelBuffer[px+py*this.pixelLength]++;
				this.pixelBuffer[px+(this.pixelLength-1-py)*this.pixelLength]++;
				
				// Iterate z
				var sqZr = zr*zr;
				var sqZi = zi*zi;
				var twoZri = 2.0*zr*zi;
				zr = sqZr-sqZi+x;
				zi = twoZri+y;
				if (sqZr+sqZi > 4.0) break;
			}
			else break;
		}
	}
	
	if (inCount%100 === 0) {
		// Set this.maxVal as the highest valued element in this.pixelBuffer
		for (var i = 0; i < this.sqPL; i++) this.maxVal = (this.pixelBuffer[i] > this.maxVal) ? this.pixelBuffer[i] : this.maxVal;
		
		var sqrtMaxVal = Math.sqrt(this.maxVal);
		var logMaxVal = Math.log(this.maxVal);
		for (var i = 0; i < this.sqPL; i++) {			
			// Rotate the Buddhabrot
			var index = ((i%this.pixelLength)*this.pixelLength+((i/this.pixelLength)|0))<<2;
			this.imageData.data[index] = (255.0*this.pixelBuffer[i]/this.maxVal)|0;
			this.imageData.data[index+1] = (255.0*Math.log(this.pixelBuffer[i])/sqrtMaxVal)|0;
			this.imageData.data[index+2] = (255.0*Math.log(this.pixelBuffer[i])/logMaxVal)|0;
		}
		this.canvas.getContext("2d").putImageData(this.imageData, 0, 0);
		
		// TEMPORARY, JUST FOR SEEING HOW LONG THINGS TAKE
		var newDate = new Date();
		debug.innerHTML = inCount+", "+this.maxVal+", "+(newDate.getTime()-oldDate.getTime());
		oldDate = new Date();
	}
}

New image going at 1,000,000 maximum iterations for a 600 x 600 image with almost the same speed (but a larger image and 100x maximum iterations at ~425 milliseconds per 100 loops of addOrbitTrap()):

(http://i.imgur.com/W4JQfWR.png)

Title: Re: Buddhabrot optimizations
Post by: asimes on August 28, 2013, 08:36:07 AM
Got it down to about ~20-30 milliseconds per 1,000 added orbit traps. The solution was to just not call addOrbitTrap() using setInterval() so often and instead do some specified number of orbit traps in a for loop for steps 2-4 in addOrbitTrap(). Then at the end of the function the rendering happens (after the for loop). I guess that has more to do with JavaScript timing but it is a gigantic speed improvement.

Title: Re: Buddhabrot optimizations
Post by: asimes on August 29, 2013, 07:32:36 AM
I tried out histogram equalization for each r, g, b channel. The images produced look much better regardless of the number of orbit traps added, but it does take a little bit for them to mix channels nicely. I'll post a link to the Buddhabrot render as soon as I finish up the UI.

(http://i.imgur.com/Q3bsKNA.png)

Red channel max iterations: 1,000,000
Blue channel max iterations: 10,000
Green channel max iterations: 100

Title: Re: Buddhabrot optimizations
Post by: cKleinhuis on August 29, 2013, 07:53:27 AM
do i see this right ? you are using javascript for this?!
the rules of thumb for normal programming languages count here as well,i just read your statement with the function calls ... javascript is an interpreted language, so, every function call slows down your execution time, for managed languages one of the most time critical thing is the "new" operation, or the general work for the garbage collector, try re-using arrays instead of de-referencing them and then creating a blank one this is very expensive, in your inner for loop where you have the calculation of the temporary array, make sure you do not recreate this array for every n-iterations, the same goes for variables defined in the loop, to hardcore optimize the javascript code you should reuse all your inner loop variables as often as humanly possible - coming down to declare them globally without name clashing in the functions ;)
as long as you arent using threading there is always just one function active at the same time, and thus with carefully selecting the global names name clashes in the functions shall be easily to counter

as a starter you could just move the "var" variable definitions from your inner loops to the beginning of the function, and measure the difference in execution time, if that brought you something continue and make them globally, removing ANY "var" DEFINITION out of your functions/loops!!!

Title: Re: Buddhabrot optimizations
Post by: asimes on August 29, 2013, 08:41:22 AM
Yes, it is JavaScript :)

I could try declaring the temporary variables outside the loop, but all in all it is executing 10,000 loops (i) of Mandelbrot Set loops (n) at the moment and rendering within 33 milliseconds for arbitrary image sizes, so I'm fairly happy (not limited by 33 milliseconds, just timed to do it that often). I agree about the temporary array, that turned out to be slow, I removed it later (a version of the code is in a previous post). It was faster to just do the Mandelbrot Set code twice, once to make sure the random point did not belong to the Mandelbrot Set and then again to increment the pixel buffers (there are three now, for r, g, and b).

Here are some more:

(http://i.imgur.com/OTVcMF7.png)

(http://i.imgur.com/gHL9ScS.png)

(http://i.imgur.com/ImmbsFq.jpg)

Title: Re: Buddhabrot optimizations
Post by: cKleinhuis on August 29, 2013, 08:48:31 AM
and? have you compared the speed when moving the "var" variable definitions to outside the loop?
:D ???

Title: Re: Buddhabrot optimizations
Post by: hobold on August 29, 2013, 12:32:26 PM
asm.js might be of interest:

http://badassjs.com/post/43420901994/asm-js-a-low-level-highly-optimizable-subset-of

Title: Re: Buddhabrot optimizations
Post by: Alef on August 29, 2013, 06:32:00 PM
I would recomend auto equalisation.

1. find max colour value of all pixels.
2. Turn it so that max colour pixel would be only pixel white.

Exact code were somewhere, byt I would recomend something like sigmoid function z= (N+1)*z/(z+N). With N you can change amount.

http://www.fractalforums.com/images-showcase-%28rate-my-fractal%29/brahmabrot-%28halfway-tobuddhabrot%29-equalisated/?PHPSESSID=9bfba3e38ab1c41b8a51651254aeb0c7 (http://www.fractalforums.com/images-showcase-%28rate-my-fractal%29/brahmabrot-%28halfway-tobuddhabrot%29-equalisated/?PHPSESSID=9bfba3e38ab1c41b8a51651254aeb0c7)

Title: Re: Buddhabrot optimizations
Post by: asimes on August 30, 2013, 07:36:34 AM
cKleinhuls, I tried declaring all of my temporary variables outside the loops. The outer loop is for how many orbit traps to try to add in the function addOrbitTrap(inRGB) (set to 10,000). There are two inner loops, both do the Mandelbrot Set code and loop up to maxIterations (set to 1,000,000 for red, 10,000 for green, and 100 for blue) but the second one actual increments my buffer that gets used for the histogram equalization. The inner loops alternate among red, green, and blue every time addOrbitTraps(inRGB) is called (using inRGB%3). Then the histogram equalization code runs for the current color channel in the same function.

For both tests I set the interval for addOrbitTraps(inRGB) to 100 milliseconds (that is how often it is called). I added some code at the end of the function to give the time the function took and the averaged the times until I had a total of ~60,000,000 successful orbit traps added:

- For the code declaring temporary variables within the loops the average time was: 45.263978762236604
- For the code declaring the variables before the loops the average time was: 46.90922030681639

Admittedly, this is higher than I thought. I had done the average time for the function before by eyeballing just the milliseconds addOrbitTraps(inRGB) took and printed the values. The values printed so fast that I did not realize every once in a while it spikes to 70-110 which is what made the average higher than I thought. Most of the time it is around ~20 but those spike increase the average to ~45.

This is the current code (with temporary values declared in the loops, timing code removed):
Code:
Bbrot.prototype.addOrbitTrap = function(inRGB) {
	var bbrotRGB, rgbMod = inRGB%3;
	if (rgbMod === 0) bbrotRGB = document.getElementById("bbrotROrbits");
	else if (rgbMod == 1) bbrotRGB = document.getElementById("bbrotGOrbits");
	else bbrotRGB = document.getElementById("bbrotBOrbits");
	
	for (var i = 0; i < 10000; i++) {
		// Select a random pixel that does not belong to the Mandelbrot Set
		var rIndex = (Math.random()*this.nonMSet[rgbMod].length)|0;
		
		// Add a random amount (-0.5, 0.5) to the pixel and translate to the complex plane
		var x = ((this.nonMSet[rgbMod][rIndex]%this.pixelLength)+Math.random()-0.5)*this.delta+this.xmin;
		var y = (((this.nonMSet[rgbMod][rIndex]/this.pixelLength)|0)+Math.random()-0.5)*this.delta+this.ymin;
		
		// Make sure the random deviation did not push z into the Mandelbrot Set
		var zr = x;
		var zi = y;
		var n = 0;
		for (; n < this.maxIterations[rgbMod]; n++) {
			var sqZr = zr*zr;
			var sqZi = zi*zi;
			var twoZri = 2.0*zr*zi;
			zr = sqZr-sqZi+x;
			zi = twoZri+y;
			if (sqZr+sqZi > 4.0) break;
		}
		
		// If z does not belong to the Mandelbrot Set
		if (n !== this.maxIterations[rgbMod]) {
			zr = x;
			zi = y;
			n = 0;
			for (; n < this.maxIterations[rgbMod]; n++) {
				// Determine if a pixel translated from z would be within the canvas
				if (zr > this.xmin && zr < this.xmax && zi > this.ymin && zi < this.ymax) {
					// Translate z to pixel coordinates
					var px = ((zr-this.xmin)*this.pDelta)|0;
					var py = ((zi-this.ymin)*this.pDelta)|0;
					
					// Increment the appropriate element as well as its symmetric element
					this.rgbBuffers[rgbMod][px+py*this.pixelLength]++;
					this.rgbBuffers[rgbMod][px+(this.pixelLength-1-py)*this.pixelLength]++;
					
					// Iterate z
					var sqZr = zr*zr;
					var sqZi = zi*zi;
					var twoZri = 2.0*zr*zi;
					zr = sqZr-sqZi+x;
					zi = twoZri+y;
					if (sqZr+sqZi > 4.0) break;
				}
				else break;
			}
			this.orbitTraps[rgbMod]++;
		}
	}
	bbrotRGB.innerHTML = this.orbitTraps[rgbMod];
	
	// Set maxVal as the highest valued element in this.rgbBuffers[rgbMod]
	var maxVal = 0;
	for (var i = 0; i < this.sqPL; i++) maxVal = (this.rgbBuffers[rgbMod][i] > maxVal) ? this.rgbBuffers[rgbMod][i] : maxVal;
	maxVal++; // Needed for the last element in cdf[] and histogram[]
	
	// Make a histogram of the values
	var histogram = [];
	for (var i = 0; i < maxVal; i++) histogram[i] = 0;
	for (var i = 0; i < this.sqPL; i++) histogram[this.rgbBuffers[rgbMod][i]]++;
	
	// Make a cumulative distribution function of the histogram
	var minCdf = 0x7fffffff;
	var cdf = [];
	cdf[0] = histogram[0];
	for (var i = 1; i < maxVal; i++) {
		cdf[i] = histogram[i]+cdf[i-1];
		minCdf = (cdf[i] < minCdf) ? cdf[i] : minCdf;
	}
	
	// Apply histogram equalization to this.rgbBuffers[rgbMod][i]'s elements
	var hDivisor = this.sqPL-minCdf;
	for (var i = 0; i < this.sqPL; i++) {
		// Rotate the Buddhabrot
		var index = ((i%this.pixelLength)*this.pixelLength+((i/this.pixelLength)|0))<<2;
		this.imageData.data[index+rgbMod] = ((cdf[this.rgbBuffers[rgbMod][i]]-minCdf)/hDivisor*255)|0;
	}
	this.canvas.getContext("2d").putImageData(this.imageData, 0, 0);
}

Title: Re: Buddhabrot optimizations
Post by: asimes on August 30, 2013, 07:43:33 AM
hobold, that is pretty cool. Admittedly I don't think I have the time to learn it right now because classes have started again and I have a few jobs at the moment. I will definitely look into it in the future.

Alef, I don't think I understand your suggestion. What I am doing at the moment is treating red, green, and blue as completely separate histogram equalizations. Each one will have some number of value 0s (possibly one usually many) and some number of value 255s (usually only one or very few). My coloring does not use n, it uses a cumulative distribution function on my histograms for each color channel. Here is an explanation: http://en.wikipedia.org/wiki/Histogram_equalization#Small_image

Title: Re: Buddhabrot optimizations
Post by: asimes on August 30, 2013, 08:56:03 AM
I ended up making a separate topic to post the renderer and a summary of my monologue up there (too much text): http://www.fractalforums.com/programming/buddhabrot-renderer-javascript-canvas/

Title: Re: Buddhabrot optimizations
Post by: ker2x on September 01, 2013, 01:31:29 PM
Hello forum, long time no see ! Buddhabrot is my favorite fractal :)
So, optimizing the buddhabrot.

You can't now for sure that something isn't in the mandelbrot set.
What you can now for sure is that some points are in the Mandelbrot set.

You can do some check :
- is this point in the main cardioid ? (there really is a real cardioid included in the set.
- is the point inside one of the 2nd order bulb ?

Here is some openCL code (it's just C code) :

Code:
//Check if choosen point is in MSet
bool isInMSet(
    float cr,
    float ci,
    const uint maxIter,
    const float escapeOrbit)
{
    int iter = 0;
    float zr = 0.0;
    float zi = 0.0;
    float ci2 = ci*ci;
    float temp;

    //Quick rejection check if c is in 2nd order period bulb
    if( (cr+1.0) * (cr+1.0) + ci2 < 0.0625) return true;

    //Quick rejection check if c is in main cardioid
    float q = (cr-0.25)*(cr-0.25) + ci2;
    if( q*(q+(cr-0.25)) < 0.25*ci2) return true; 


    // test for the smaller bulb left of the period-2 bulb
    if (( ((cr+1.309)*(cr+1.309)) + ci*ci) < 0.00345) return true;

    // check for the smaller bulbs on top and bottom of the cardioid
    if ((((cr+0.125)*(cr+0.125)) + (ci-0.744)*(ci-0.744)) < 0.0088) return true;
    if ((((cr+0.125)*(cr+0.125)) + (ci+0.744)*(ci+0.744)) < 0.0088) return true;

    while( (iter < maxIter) && ((zr*zr+zi*zi) < escapeOrbit) )
    {
        temp = zr * zi;
        zr = zr*zr - zi*zi + cr;
        zi = temp + temp + ci;
        iter++;
    }

    if( iter < maxIter)
    {
        return false;
    } else {
        return true;
    }

}

The code is compact, openCL prefer bruteforce math instead of accessing some temporary variable that usually avoid to compute many times the same thing.


cr and ci are the coordinates of the point (real & imaginary), generated using :
Code:
    float cr = mix(realMin, realMax, rand.x);
    float ci = mix(imaginaryMin, imaginaryMax, rand.y);

mix is an openCL function :
Code:
gentype mix ( gentype x, 	gentype y, 	gentype a)
Returns the linear blend of x and y implemented as: x + (y - x) * a
(convert random 0..1 point to the fractal coordinates)


Another intersting thing is that you don't have to look for point on the whole screen.
Code:
REAL, PARAMETER :: xmin = -1.0, xmax = 2.0, ymin = -1.3, ymax =1.3
(now, that's some fortran code)

Also, the same code to check for main cardioid and biggest bulbs, but the code is very compact too. Fortran handle complex math natively
Code:
  IF(((ABS(c - CMPLX(-1,0) )) < 0.25) .OR. ((ABS( 1.0 - SQRT(1-(4*c)) ))  < 1.0 ) ) THEN
(c is a complex number which is the coordinate of the point being tested)



Title: Re: Buddhabrot optimizations
Post by: ker2x on September 01, 2013, 01:45:53 PM
Now you have another problem :

You test each pixel to now of it's in the mandelbroset or not.
Which is wrong.

each pixel can possibly hold an infinite numbers of point that are and are not in the mandelbrot set.
That's why your buddhabroth is noisy.

You probably already now that the intersting points for the buddhabrot are at the frontier of the mandelbrot set.
By doing what you do you dismiss an infinity of interesting points.

You test the infinitesimal point that is at the center of your pixel. But can you now for sure that the infinity of point/coordinates that are in this pixel are also in the mandelbrot set ?
You can't.

The best optimisation i know is the metropolis-hasting algorithm http://www.steckles.com/buddha/
I helped to write the buddhabrot generation software (C++) : https://github.com/emmmile/buddha

Take a look at this : http://www.fractalforums.com/images-showcase-(rate-my-fractal)/ker2x's-buddhabrot-gallery/
You need to run billions and billions of random numbers (much more than the number of pixel) to get something nice and smooth.

Title: Re: Buddhabrot optimizations
Post by: ker2x on September 01, 2013, 01:47:56 PM
Ho ...

And don't refresh your screen everytime you find an orbit.
Drawing (javascript or not) is SSSSSSLLLLLOOOOOOOOOWWWWWWWW !!

Title: Re: Buddhabrot optimizations
Post by: Ryan D on September 01, 2013, 03:39:55 PM
Have you considered simply ignoring whether they are in the M-set or not?  Points which escape quickly will not have much effect on your histogram.  They fall out of the iteration loop quickly and contribute very little to increasing the hit count of any individual pixel.  A very simple solution to that is to simply not plot the first few iterations - a classic escape-time view of the M-set looks almost the same after 20 iterations as it does after 2000 iterations, so just ignore the first 20 iterations before you start updating the hit count on the individual pixels.

Points which are very close to the border and require hundreds of iterations will follow a path very similar to the points just barely over the border, and only the last few iterations will vary significantly.  Again, that's only a few iterations and those will have very little effect on increasing the hit count of any individual pixel.

I play around a fair bit with orbit path Buddhabrot-style fractals, and I always ignore whether the point being tested escapes or not.  I'm old school, so I still have enough fun with Fractint that I'm not ambitious enough to bother updating to anything more current - probably I will some day, but I'll treat that as a retirement project!  In Fractint, you don't have the option of ignoring the first iterations, so you usually get a regular grid resulting from the first iteration or two, but if the colour scheme is set so that the lowest hit counts are the faintest colours, then you hardly notice that.  Here's one of my favourite orbit path animations, ignoring whether the points fall in or out of any set.

http://vimeo.com/moogaloop.swf?clip_id=49084660&amp;server=vimeo.com&amp;fullscreen=1

Ryan

Title: Re: Buddhabrot optimizations
Post by: ker2x on September 01, 2013, 04:13:53 PM
Yes yes, of course.

All my codes have a min & max iteration, for each color

So you can have a buddhabroth like this :
RED : 100->1000 iterations
GREEN : 500 -> 1500
BLUE = 1000->3000

and 0 to 100 aren't drawn. any orbit with low iteration count (here < 100) are not drawn.

Title: Re: Buddhabrot optimizations
Post by: cKleinhuis on September 01, 2013, 05:14:14 PM
What i dont like about the buddhas is the random distribution of starting positions
i think interestin patterns could be found by somehow generalized aproach to scan a grid at least to check out what very dense starting positions vary . . .

Title: Re: Buddhabrot optimizations
Post by: asimes on September 01, 2013, 06:32:06 PM
ker2x, I don't think I follow a few of your posts and I think you either did not follow my explanations or misunderstood my code.

Quote
"You can't now for sure that something isn't in the mandelbrot set.
What you can now for sure is that some points are in the Mandelbrot set"

I don't see why I can't. Before I run the orbit trap loop I determine if each pixel is in the Mandelbrot Set. If it is I ignore it otherwise I add it to my nonMSet array. Any pixel in nonMSet it is guaranteed not to be in the Mandelbrot Set.

Quote
You test the infinitesimal point that is at the center of your pixel. But can you now for sure that the infinity of point/coordinates that are in this pixel are also in the mandelbrot set ?
You can't.

I pick a random pixel in nonMSet and add a random deviation in the range (-0.5 to 0.5) to its x and y values. The reason I am using -0.5 and 0.5 is because that theoretically means every pixel inNonMSet is now an area of random points (an area of the length of a pixel by the length of a pixel). I say theoretically because of floating point inaccuracy.

This does mean that one of the pixels chosen from nonMSet + random deviation could now be in the Mandelbrot Set, so that is why I test for it in the orbit trap code. I could add the quick rejection tests there, but otherwise I am doing the exact same thing.

Quote
And don't refresh your screen everytime you find an orbit.
Drawing (javascript or not) is SSSSSSLLLLLOOOOOOOOOWWWWWWWW !!

I'm not? I'm drawing the screen after 10,000 orbit traps are attempted (not all of them pass the not-in-the-Mandebrot-Set test).

Title: Re: Buddhabrot optimizations
Post by: asimes on September 01, 2013, 06:35:23 PM
Ryan D, That sounds like a promising idea, I will try it out

Edit: Still using my code the way it was but only adding orbit traps if their iterations count is > 20:
- Low maximum iteration counts fail often (they don't pass the acceptable-orbit-trap test often)
- A lot less noise around the image, looks nicer when the glowing cloud around the Buddhabrot hugs tighter instead of being spread out in a circle. Also builds a nice looking Buddhabrot without noise much faster.
- The glowing cloud around the Buddhabrot is affected in the sense that it kind of looks like a Buddhabrot rendered at 20 maximum iterations. In the picture below there is some lightning-looking stuff (I actually like it) around the head that never appeared before without the > 20 test.

Normal result for red max iterations = 1,000,000; green max iterations = 10,000; blue max iterations = 100:
(http://i.imgur.com/Q3bsKNA.png)

Result of doing the n > 20 test for red max iterations = 1,000,000; green max iterations = 10,000; blue max iterations = 100 (I did not wait very long by comparison to the other images for this to be produced, it is faster):
(http://i.imgur.com/6udTYAf.jpg)

Normal result for all max iterations = 20 (for reference):
(http://i.imgur.com/xakW2r3.jpg)

Title: Re: Buddhabrot optimizations
Post by: ker2x on September 01, 2013, 07:12:45 PM
Because you'll add in your ignorelist a lot of point that are at the frontier of the MSet and they are the most interesting orbits.

Title: Re: Buddhabrot optimizations
Post by: asimes on September 01, 2013, 07:30:36 PM
ker2x, I tried making a diagram in Photoshop to explain and realized a random range of (-0.5 to 0.5) does miss some points. Here is the diagram anyway:

(http://i.imgur.com/Ma8A19H.jpg)

- The small red squares are pixels that do not belong to the Mandelbrot Set
- The small green squares are pixels that do belong to the Mandelbrot Set
- The pink areas are the random deviation every red pixel has (only shown at the boundary of the Mandelbrot Set)
- The light green areas might be part of the Mandelbrot Set and I am missing those

I will change the code to use a random range of (-1.0 to 1.0) and then that will completely cover the boundary

Title: Re: Buddhabrot optimizations
Post by: asimes on September 01, 2013, 07:50:18 PM
I'm not really sure why putting the minimum iteration limit (x) on n makes it look like a maximum iteration (x). The maximum iterations here are the same as above, the only difference is that the random point contributes to the value buffers if n > 10):

Code:
if (n > 10 && n < maxIterations[inRGB])

(http://i.imgur.com/bzmNmLz.png)

Title: Re: Buddhabrot optimizations
Post by: Roquen on September 01, 2013, 09:32:38 PM
I have no clue about the scheme involved, but about quasi-random (LDS) instead of pseudo?

Title: Re: Buddhabrot optimizations
Post by: matsoljare on September 01, 2013, 09:46:56 PM
How about making a video of the iteration count increasing?

Title: Re: Buddhabrot optimizations
Post by: asimes on September 01, 2013, 10:01:42 PM
matsoljare, that would be really cool but other than just taking a lot of screenshots I don't know of an easy way to use JavaScript to render a movie. It looks like some other people on this thread also have Buddhabrot renderers, maybe they would be more prepared.

By iteration count increasing did you mean:
- The maximum iteration count for one / all the color channels
- The minimum iteration count that was confusing me in the last few posts
- Something else?



Powered by SMF 1.1.21 | SMF © 2015, Simple Machines