Divide And Conquer

There’s an old-school technique for rendering the classic fractal, the Mandelbrot set, called Divide and Conquer. This technique takes advantage of the fact that all of points in the Mandelbrot set are ‘connected’ – there are no islands of Mandelbrot set points which aren’t connected to the main set; and there are no islands of non-Mandelbrot set enclosed by points within Mandelbrot set. Think of it as a single blob of water. Given this, you can speed up rendering of any subset of the Mandelbrot set by:

  1. Divide the image into four rectangles.
  2. For each of the four rectangles:
  3. If the rectangle has a non-zero width and height:
  4. Calculate all the points along the edges.
  5. If all the points along the edges have the same calculated value, all points within the rectangle must be the same, too. No ‘islands’, remember. So, fill the rectangle with the value you calculated for the edges.
  6. If the points along the edge are not the same, divide that rectangle into four rectangles and, for each sub-rectangle, go to step 3. (Keep in mind that since you’ve already calculated the points on the edges, you can reduce the size of the rectangle by 1 on each edge).

So, it’s a recursive space-filling technique. It divides the work area into smaller and smaller rectangles until it finds something it can fill or it can no longer sub-divide. And in this way it gobbles-up large identically-valued sections of the Set very quickly, and so it spends most of its time working on details. In general, that’s a performance gain. And, even better, this technique is far more fun to watch than just seeing pixels calculated one at a time, one row after another. It’s kind of mezmerizing. Or, it was back in the day. These days, computers are fast enough that you can’t see it in action.

Anyway, I thought it would be fun to put a variation of this technique to use on non-fractal images. So, I used color differences in the source image to determine where the edges of the rectangles go, with a selectable threshold to control color matching. I added a way to limit the minimum rectangle size, and taught it to optionally draw tastefully-colored borders around each rectangle.

And away we go!

Start with this:

monalisa_sm

Set the minimum rectangle dimension to 25 pixels, set the threshold to “100” and…

ml_sz25_t100

Not amazing.

The rectangles are too big. So, reduce the min rect size to 10:

ml_sz10_t100

Now you can start to see what’s going on. Variety in rectangle sizes is what we’re after – otherwise it’s just pixelation. And this would be a most inefficient way to do pixelation…

Set min rect size to 4, and then to 2:

ml_sz4_t100

ml_sz2_t100

There we go.

Now, that’s fun.

But there’s one thing I don’t love about this: the rectangles follow a perfectly even grid, regardless of min rect size. Look at the four rectangles in the top-left of this one, then look at the previous images. They are the same in all of the images except for minsize=25 – and in that case, those four rects fit perfectly into its top-left rectangle. This is completely expected, since we’re just dividing the image into 1/2 then 1/4 then 1/8 then 1/16, etc., and so we’re going to keep hitting those same edges over and over.

What we need is to vary the sizes of the sub-rects, to get off of that power-of-two thing. To do that, I added something called ‘jitter’. Instead of dividing the rectangle evenly into four equal sub-rects, jitter divides the rectangle by 2, 3 or 4 vertically, then 2, 3 or 4 horizontally. The divisor is chosen at random.

That gives:

ml_sz2_t100_j

And because the jitter is random, the output image will be different every time.

Other variations:

No outlines:
ml_sz2_t100_no

Don’t fill the rectangles, just draw the outlines:

ml_sz2_t100_je

That shows another variation: instead of randomizing the sub-rect proportions, just nudge the edges of the sub-rects by a pixel or two. That maintains the even grid, but adds just enough noise to break the monotony if you look closely.

Or, render the same image twenty times with jitter on, and put the results into a GIF !

bart

Far out, man!

Don’t Run

Really, Mr Webb. Do not run for President – especially not as a Democrat. It won’t go well if you do.

This is an emotional time and we all need to think through these issues with a care that recognizes the need for change but also respects the complicated history of the Civil War. The Confederate Battle Flag has wrongly been used for racist and other purposes in recent decades. It should not be used in any way as a political symbol that divides us.

It’s far too late to stop the Confederate Battle Flag from being used to divide the country, since the goal of the Confederacy was to literally divide the country. They seceded, remember? Formed an army, waved that flag around? Hundreds of thousands died as a result?

And as for “racist purposes”? Again, too late! It’s been a symbol of racism from its inception. The Confederacy was created to preserve slavery. That’s no northerner’s revisionist history, either. To know the Confederacy’s intentions, we need only read the declarations of secession that the Confederate states issued.

Minced oath

A minced oath is a euphemistic expression formed by misspelling, mispronouncing, or replacing a part of a profane, blasphemous, or taboo term to reduce the original term’s objectionable characteristics. Some examples include gosh, darn, dang, and heck.

Wiki