Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!wuarchive!usc!apple!sun-barr!newstop!sun!coherent!dplatt
From: dplatt@coherent.com (Dave Platt)
Newsgroups: comp.graphics
Subject: Re: Excluding Mandelbrot set -- Summary
Message-ID: <40444@improper.coherent.com>
Date: 27 Nov 89 18:27:22 GMT
References: <3544@quanta.eng.ohio-state.edu> <3586@quanta.eng.ohio-state.edu> <1989Nov25.174444.8953@isy.liu.se>
Reply-To: dplatt@improper.UUCP (Dave Platt)
Organization: Coherent Thought Inc., Palo Alto CA
Lines: 45

In article <1989Nov25.174444.8953@isy.liu.se> pell@isy.liu.se (P{r Emanuelsson) writes:
>This is of course not mathematically correct, but it's a useful assumption.
>Especially if you take, say, every fifth point on the rectangle borders.
>Sure, the images will start to look a bit strange but it's useful if you
>want to have a quick peek at what things look like.

It's true that the rectangle-approximation system is not mathematically
justifiable.  However, it actually works out in practice _extremely_
well... there are very few cases in which it miscolors an image, as long
as it's implemented correctly.

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.

This algorithm may "miss" occasionally, if a tiny tendril of one color
"sneaks through" the border of a rectangle which is otherwise
monochromatic.  In practice, this seems to be a very rare occurrance...
I've calculated images using a normal raster-scan sweep and via the
Mariani/Silver algorithm, and have been unable to see _any_ differences
between the two.  It's entirely possible that my eyes have missed a
single-pixel difference here and there... but no gross differences have
ever appeared in the tests I've run.

At high magnifications, and at high dwell limits, the Mariani/Silver
algorithm doesn't buy you much... the dwell bands are so close together,
and so greatly convoluted, that there aren't many sizeable monochromatic
areas to be found.  In this situation, the Mariani/Silver algorithm's
performance degenerates, and it becomes slightly slower than the
raster-scan iteration (same number of calculations, with higher
overhead).

In practice, I've never seen Mariani/Silver run slower than raster-scan.

-- 
Dave Platt                                             VOICE: (415) 493-8805
  UUCP: ...!{ames,apple,uunet}!coherent!dplatt   DOMAIN: dplatt@coherent.com
  INTERNET:       coherent!dplatt@ames.arpa,  ...@uunet.uu.net 
  USNAIL: Coherent Thought Inc.  3350 West Bayshore #205  Palo Alto CA 94303


Brought to you by Super Global Mega Corp .com