Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!cornell!uw-beaver!Teknowledge.COM!polya!rokicki
From: rokicki@polya.Stanford.EDU (Tomas G. Rokicki)
Newsgroups: comp.graphics
Subject: Re: Excluding Mandelbrot set -- Summary
Message-ID: <12892@polya.Stanford.EDU>
Date: 27 Nov 89 23:55:25 GMT
References: <3544@quanta.eng.ohio-state.edu> <3586@quanta.eng.ohio-state.edu> <40444@improper.coherent.com>
Organization: Computer Science Department, Stanford University
Lines: 50

dplatt@coherent.com (Dave Platt) writes:
> The implementation I use (Mariani/Silver) was described in the Amygdaya
> newsletter a couple of years ago.  Briefly:  pick a rectangular region
> which does not include the full M-set.  Scan the border of this region,
> checking to see whether it's monochromatic.  If so, color the entire
> region with this color and exit.  Otherwise, divide the region in half
> along its longer axis, and run this algorithm recursively on each half.
> Stop recursing if the size of a rectangle drops below a chosen minimum
> (shorter side < 5 seems to work well) and color points in the rectangles
> by the usual point-at-a-time iteration.

I've found a different algorithm to be faster, combining parts of the
raster scan and parts of the rectanglularly-enclosed algorithms.

You calculate the entire top and the entire bottom raster row of a region
using the standard scan approach.  Then, you search these rows for a region
of a single color, where the color is the same in both rows.  For each of
these regions, you scan down to complete the rectangle---if you can (and
you will, most of the time) then you fill the entire rectangle.

Then, you recurse, filling in a row in the middle, and iterating as before.

The reason this works is that most regions of the same color are
approximately parallelograms:


---------------|---------------|-------------------  one raster row
              /|               |    /
             / |               |   /
            /  |               |  /
           /   |               | /
          /    |               |/
---------------|---------------|-------------------  another raster row

The parallelogram is the `actual' same-color region.  The rectangle is
the same-color region you find because the top and bottom colors are
the same.

This helps maximize the size of the rectangles you find each time, and
there is very, very little overhead . . .

Of course, when you scan vertically trying to complete a rectangle, you
save away the colors you calculate into an array so you don't have to
recalculate them . . .

I've always wanted to refine this into a `boundary seeking' algorithm
(ie, trace out the actual parallelogram rather than using a bunch of
progressively smaller rectangles) but haven't had the time or patience.

-tom


Brought to you by Super Global Mega Corp .com