Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!wuarchive!zaphod.mps.ohio-state.edu!usc!apple!motcsd!xdos!doug
From: doug@xdos.UUCP (Doug Merritt)
Newsgroups: comp.graphics
Subject: Re: Mandelbrot/Julia optimizations (was Re: Excluding Mandelbrot set)
Message-ID: <558@xdos.UUCP>
Date: 1 Dec 89 17:33:02 GMT
References: <7106@ficc.uu.net> <3544@quanta.eng.ohio-state.edu> <234@xochitl.UUCP> <601@otto.bf.rmit.oz.au>
Reply-To: doug@xdos.UUCP (Doug Merritt)
Organization: Hunter Systems, Mountain View CA (Silicon Valley)
Lines: 65

In article <601@otto.bf.rmit.oz.au> athos@otto.bf.rmit.oz.au (David Burren [Athos]) writes:
>In article <234@xochitl.UUCP>, cheeks@edsr.eds.com (Mark Costlow) writes:
>>In article <7106@ficc.uu.net>, peter@ficc.uu.net (Peter da Silva) writes:
>>> After you have determined that a point is in the set, you know
>>>that all the other points visited in determining that are in the set as well,
>>  But, isn't the path different for each different C?
>If you get to point X from any
>previous point then you WILL proceed to the same next point. Of course, this
>is subject, like everything else, to rounding errors. [...]
>However the search time to determine if you have found a point previously
>makes Peter's scheme sound rather daunting.

About four years ago, when I was doing lots and lots of Mandelbrot graphics,
I tried this optimization, but with the definition of "point" being "pixel".
This failed rather miserably, because it effectively drastically reduced
precision, and many, many distinct paths passed through the same pixel,
even at a zoom of 1X.

I never followed up with a comparison with the actual floating point
coordinate of the pixel, but it still seems to me that Peter's scheme
might be a win. All you need is a 2 dimensional array corresponding to
the screen, with each cell containing two floats and a state marker
(not-visited, visited-and-in-set, visited-and-not-in-set). Call it
17 bytes per cell (2 double precision plus 1 byte state). The resulting
array for a 1Kx1K screen is a mere 17 megabytes, which will easily fit
into memory on *someone's* computer out there, and hence won't incur swapping.

My current Sun only has 12 Meg so I can't make this work. Well, ok,
I could use single precision and cram the array into 9 Meg, yeah, that
would work, at the expense of a smaller workable maximum zoom.

Anyway, if you've got the memory, this'll cost only 4 floating point
comparisons (assuming +/- check for equality to avoid mismatch in the
least significant digit(s)) on each step of the trajectory. Ok, on average
how many recurrences of the trajectory need to be calculated before finding
a previously-hit point? Well, let's say the whole screen is in the
interior of the set. Let's also say we're real near one of the strange
attractors in the interior, so that the trajectory tends to follow a
tight loop, usually staying on screen throughout. In the best case, with
a dwell of 256, a mere 4K pixels need be calculated before every pixel
on the screen has been visited. Thereafter, every single step of the
calculation will hit a visited pixel on the first iteration.

Hmm, but the floating point values will probably differ pretty often,
and meanwhile we've ensured that the data cache misses on every instance
of the inner loop. Maybe we can keep the instruction cache filled, though.

And of course, if the screen is mostly outside the Mandelbrot set, there's
no win at all, because we need to calculate the whole trajectory in order
to color the pixel by the dwell.

Ok, I give up, I can't see any way for it to win after all. The only
way to ensure more hits on the floating point comparisons would be to
keep more than one trajectory result per pixel, but that quickly
increases memory demands. A supercomputer with 512Meg of RAM could
store about 64 trajectory cells per pixel. Calculate the +/- delta
on the fly rather than storing it, and cut the storage requirements in
half, yielding 128 trajectory cells per pixel.

Maybe that's enough for a win. Anyone know, on average, how many different
trajectories pass through a given pixel?
	Doug
-- 
Doug Merritt		{pyramid,apple}!xdos!doug
Member, Crusaders for a Better Tomorrow		Professional Wildeyed Visionary


Brought to you by Super Global Mega Corp .com