Logo by tomot - Contribute your own Logo!

END OF AN ERA, FRACTALFORUMS.COM IS CONTINUED ON FRACTALFORUMS.ORG

it was a great time but no longer maintainable by c.Kleinhuis contact him for any data retrieval,
thanks and see you perhaps in 10 years again

this forum will stay online for reference
News: Did you know ? you can use LaTex inside Postings on fractalforums.com!
 
*
Welcome, Guest. Please login or register. March 28, 2024, 06:09:40 PM


Login with username, password and session length


The All New FractalForums is now in Public Beta Testing! Visit FractalForums.org and check it out!


Pages: [1]   Go Down
  Print  
Share this topic on DiggShare this topic on FacebookShare this topic on GoogleShare this topic on RedditShare this topic on StumbleUponShare this topic on Twitter
Author Topic: Lilac Exponent  (Read 1977 times)
0 Members and 1 Guest are viewing this topic.
Pauldelbrot
Fractal Senior
******
Posts: 2592



pderbyshire2
« on: September 15, 2011, 12:43:21 AM »

Lilac Exponent



http://www.fractalforums.com/index.php?action=gallery;sa=view;id=8514

This is an unusual visualization of a Mandelbrot zoom, for which I cannot take full credit. I chose the zoom location and color scheme (one of my multifrequency ones) but someone named David Madore came up with the technique used here.

That technique is as follows: invert the complex plane about the zoom target (here the center of a minibrot shallowly into high-precision arithmetic -- 22 decimals) and then use polar coordinates as screen coordinates, and moreover the y axis is the logarithm of the modulus, rather than the modulus.

This is analogous to a Mercator projection of the Riemann sphere, with infinity at the north pole and the target point at the south. Horizontal lines in the image represent circles of constant radius (hence the repetition along the x axis) about the target point. Higher precision math is needed farther south.

The math to convert screen coordinates to Mandelbrot coordinates is exceptionally simple. First map screen coordinates into the complex plane. Then multiply by i and take the complex exponential -- z -> eiz. Now invert at zero (take the reciprocal and complex conjugate, in either order) and add the target point (with normal complex number addition).

Since this mapping is conformal, spirals don't get squished or skewed.

The result is what you see here: infinity is infinitely far up, the target point is infinitely far down, and everything else is in between, with higher magnifications toward the bottom.  In principle, everything you'd see in a zoom movie from the full set down to the target minibrot is in this single still image. The black blob at the top is the bulk of the M-set; the large black blob a short way south of it is a shallow minibrot in a weed-tendril. The small minibrot farther down with an enlarged "nose" pointing south is in that one's seahorse valley. The fat minibrot just below that one is the previous one's main spike minibrot. And the black area at the bottom is the target minibrot, which is a smaller spike minibrot and is down in the elephant valley area of the larger spike minibrot.

Now, here's the really freaky thing. In theory, the most efficient way to compute a zoom movie is to compute an image like this (but higher resolution!) and then create the movie frames from it by mapping vertical "windows" of one horizontally-repeating strip into the image space through the inverse mapping. The desired input resolution is: horizontal resolution equal to the circumference, in pixels, of a circle about the frame center and passing through the frame corners; vertical resolution equal to the radius in pixels of that same circle, times a factor for oversampling, times the number of zooms from one pixel radius to that circle's radius needed to get from whole-set view to target view.

In fact, any movie frame centered on the target point and within a certain magnification range can be computed, in principle, using the data in an image like this of sufficient resolution; with any given magnification and (via a plain old translation along the x axis of the input data applied before anything else) rotation.
Logged

Pauldelbrot
Fractal Senior
******
Posts: 2592



pderbyshire2
« Reply #1 on: September 22, 2011, 07:03:03 AM »

Finally got around to doing the math on the zoom-movie computation idea.



Heavy Math Ahead -- Proceed With Caution


The previous best known method for computing a zoom movie computes keyframes at zooms that are successive factors of some quantity μ. Supposing we want a final frame resolution of 1024x768 and don't mind if the outer part of each frame is not antialiased, but require it not be undersampled, the keyframe resolution will have to be larger than 1024x768, as a final frame will be composited using the last keyframe bigger than the target frame and (conceptually) all the ones smaller than the target frame, so the center part of a given final frame is densely oversampled and the outer part is undersampled if the keyframe resolution is not larger than 1024x768 by a factor of μ.

Supposing the final zoom magnification is ω and the initial zoom magnification is 1. The number of keyframes is then the base-μ logarithm of ω, or ln ω/ln μ. The number of square pixels per keyframe is 1024∙768∙μ2, and the total number of pixels to compute is 1024∙768∙μ2ln ω/ln μ. The first derivative of this in μ is 1024∙768∙ln ω∙(μ2/ln μ)' and has zeros where (μ2/ln μ)' has zeros. This latter expression is, by a combination of the product rule and the chain rule, 2μ/ln μ - μ/(ln μ)2 = (μ/ln μ)(2 - 1/ln μ). The latter is the one component in the product that can be zero for nonpathological values of μ and attains that value when ln μ = 1/2, or μ = √e. The second derivative of the total pixel count in μ is 1024∙768∙ln ω∙(μ2/ln μ)'' and has the same sign as (μ2/ln μ)'' = (μ/ln μ)(2 - 1/ln μ)' = (1/(ln μ)3) + (2 - 1/ln μ)(1/ln μ - 1/(ln μ)2). Substituting ln μ = 1/2 in this gives 8, since the first term in the sum is 8 and the second is zero due to the factor of (2 - 1/ln μ). So, the second derivative is positive at μ = √e and this is therefore a minimum, rather than a maximum, an inflection point, or a singularity.

It follows that a zoom factor μ of √e is optimum for computing the minimum number of pixels to generate via keyframe interpolation a movie whose frames are not undersampled anywhere.

For a final zoom factor of ω = 10143 and a target resolution of 1024x768, the keyframe resolution needs to be 1689x1267 and the number of keyframes is 673 (using a corrected ω = 10146 to multiply in the roughly thousand-fold range of magnifications contained in the initial frame at that resolution), for a pixel count of 1,440,195,099 -- nearly one and one-half billion.

Using the Mercator strip trick gives a different result. To avoid undersampling the final frames, the horizontal resolution of the strip needs to be the circumference, in pixels, of a circle through the frame corners. For a 1024x768 frame, the diameter of this circle is the diagonal length of the image, which is 1280 pixels, and the circumference is π times this, or 4022 pixels. The height is more complex to calculate. Each row of pixels corresponds to a circle of some radius about the zoom's target. To avoid undersampling, the one through a particular frame's corners and the next smaller one must not have gaps, so the next smaller one should be only two pixels less in radius; the zoom factor to shrink the larger circle to the smaller will therefore be 1280/1278. This gives us a μ value that can be used to compute the total number of circles needed to reach our target zoom.

So, the number of vertical rows is the logarithm of ω = 10146 divided by the logarithm of μ; it comes out as 214986 rows. Multiplying by the 4022-pixel width gives 863,467,092 -- fewer than two-thirds the pixels to calculate as in the optimal keyframe-interpolation case!

It's not hard to see where most of the improved efficiency comes from. Each keyframe in the keyframe case contains samples close to samples from earlier keyframes -- 1/e or nearly forty percent of a keyframe's pixels contain a sample from the immediately preceding keyframe, which could be recycled as a sample in that keyframe. Presuming that samples in still earlier keyframes landing in the current keyframe land in a subset of the same pixels, using the samples from previous keyframes in subsequent keyframes allows all keyframes except the first (which is very low iteration and low precision, so super-fast) to be reduced to 60% new-to-calculate pixels. For a 1689x1267 keyframe, computing only 1 - 1/e of the pixels (rounded up, as with all pixel counts in the foregoing) gives 1352633 pixels to compute per keyframe and 910,322,009 pixels total. This is still larger than the Mercator method's 863,467,092 for the same zoom sequence.

There is also one more advantage to the Mercator method and one more disadvantage to the keyframe method with recycled pixels. The latter has the problem that the samples "jitter" relative to the pixel centers, and indeed with the linear dimensions expanding by a factor of only about 1.6 per keyframe, new pixels are inserted between only some rows and columns of existing pixels to generate each new keyframe (for new pixels to be between every row and every column of existing pixels they'd have to comprise at least 75% of the whole, not just 63 or so) and distortions may get magnified as successive keyframes are generated.

The Mercator method, meanwhile, enjoys a smooth, rather than a step-function, increase in oversampling level towards the center of a given final frame from its outer edges. Noticeable rectangular boundaries between regions with little and with more antialiasing can result from the layering of keyframes into the final frame with the keyframe method, which the Mercator method avoids.

The Mercator method, however, may be a bit more math-intensive. Each frame of our 1024x768 video spans roughly three orders of magnitude of size, and turns out to involve 4576 of the concentric circles that become rows in the Mercator mapping. So, instead of being made from a few 1689x1267 keyframes via affine transformations, it's made from a 4022x4576 block of raw data via a more complex, nonlinear transformation that maps that raw data into the image to drop samples into the frame's pixels. (All of the remaining circles either ring the frame without intersecting it, or lie entirely in the frame's central group of four pixels.)

Another complication is the question of whether png or other image formats permit dimensions as large as 214986 pixels in width or height, and whether that much data would fit in memory happily -- 8-bit-per-channel RGB data for this hypothetical zoom would fill more than 2.5GB of RAM. These numbers get worse the deeper the zoom goes, as the height depends on ω as well as frame resolution, though the width depends only on frame resolution.

Most likely, the data would have to be generated as a sequence of smaller images, say 4022x4576 blocks, which when stacked vertically amount to the equivalent of a single, much taller image. Choosing the block height to equal the height corresponding to the scale range spanned in a single frame means the movie maker software would have to read exactly two of these blocks to generate one output frame in the general case. The blocks' number, rather than their height, now depends on ω, and their resolution depends only on frame resolution; the blocks take roughly 60 megabytes in this case for 8-bit-per-channel RGB. More generally, they will take roughly 24 times as much space as the frames themselves will, more or less independently of resolution. (The height, if made equal to a frame's magnification span, grows a bit faster than linearly due to an added logarithmic factor.) 120 megabytes suffices to hold the raw data to compute a frame. The amount of I/O is not appreciably increased either from discarding and reloading of blocks, as adjacent frames will usually use the same two blocks; for a zoom movie that never goes into reverse at any point, the movie maker can load and discard blocks once each, sequentially, holding only two in memory at a time and reading each byte of block data exactly once, in principle performing identically to one loading a monolithic image file holding all of the data. (In practice, if the data is stored in a common format like png, there will be a bit of overhead from each one having separate headers.)

Of course, using fixed-size blocks runs into a potential problem if the zoom target is reached partway down the bottom block, instead of exactly at its bottom. But the extra rows needn't be computed; the bottom block could be padded with black instead, which would work particularly well if the zoom is centered on a point contained in a minibrot, as the smallest computed circle can then just be the smallest about that point that contains escaping points, and in principle the zoom then goes on infinitely. smiley More generally, the bottom block can be padded with the color of the leftmost pixel on the bottom actually-computed row, and if this smallest circle about the zoom center is contained in a minibrot colored a solid color or is away from dendrites and small enough in comparison to nearby dwell bands that the color of the disk it bounds is pretty much uniform, this will give good results.

As with the advanced keyframe interpolation mechanism, a movie maker based on the Mercator algorithm can synthesize any frame, with any orientation, whose magnification lies within the range spanned by the computed circles. Indeed, rotation of a frame is actually simpler in this scheme, as it can be accomplished simply by cyclically permuting the columns of the input data! Whereas in the keyframe interpolator it requires complex, extra coordinated affine transforms of keyframes and it requires one extra keyframe, zoomed out from the first keyframe needed without rotation, as the image corners will in general not lie in the first keyframe of larger width but will lie in the second (for image proportions not ridiculously far from square -- the Mercator method, by contrast, doesn't have any problems with long, thin frames or tall, narrow frames, but loses efficiency there as larger and larger portions of the outer circles are not used in non-heavily-oversampled regions of the frames -- unless, of course, the movie is also spinning quite fast! In which case no version of the keyframe method would avoid horrid undersampling of the regions far from the image center, so, advantage Mercator again).
Logged

bib
Global Moderator
Fractal Senior
******
Posts: 2070


At the borders...


100008697663777 @bib993
WWW
« Reply #2 on: September 22, 2011, 02:02:07 PM »

Fascinating picture and explanations, very smart! I hope you'll manage to create a zoom using that method, but to me, the pictures that could be done with that method are more interesting than just a speed up to compute deep zooms.

Just a quick question. In the picture, if the fat minibrot is in the spike of the above minibrot, how come it is upside down?
Logged

Between order and disorder reigns a delicious moment. (Paul Valéry)
Pauldelbrot
Fractal Senior
******
Posts: 2592



pderbyshire2
« Reply #3 on: September 22, 2011, 03:13:43 PM »

The spike goes right through the target point, so, all the way down to negative infinity, and then back up 180 degrees around that point, so back up from negative infinity one-half of a cycle to the side, and up into the elephant valley of the minibrot that's "upside down".

Alternatively, just note that the target point is in that minibrot's elephant valley a ways, so the rest of its elephant valley, and the minibrot itself, are to one side of the target point with elephant valley closest, and the minibrot whose spike it is is on the other side with the spike end pointed at the target point. So, spike-bearing minibrot down (and with nose enlarged); other minibrot up (and with tail enlarged).
Logged

subblue
Conqueror
*******
Posts: 116



WWW
« Reply #4 on: September 22, 2011, 04:10:05 PM »

Looks very nice. I've bookmarked this to read through it properly later. There's some further info about these types of mapping with source code over here: http://mrob.com/pub/muency/exponentialmap.html
Logged

www.subblue.com - a blog exploring mathematical and generative graphics
Pauldelbrot
Fractal Senior
******
Posts: 2592



pderbyshire2
« Reply #5 on: September 23, 2011, 02:47:05 AM »

Thanks. I'll check it out. Though I already have another innovation in this area in the works that'll knock your socks off.
Logged

cKleinhuis
Administrator
Fractal Senior
*******
Posts: 7044


formerly known as 'Trifox'


WWW
« Reply #6 on: September 23, 2011, 07:14:47 PM »

i never undestood how this method works, and never implemented it, i wonder if that method could have been used to make "realtime" zooms on oldschool computers, like AMIGA....
in the days they used snapshots of the sequence, and blended the zoomed images together to create a straight zoom experience, but you could always see the stepping, and this method somehow seems to produce smooth animations .... but i still dont get it, and when i see that 2 pages long algorithm, i dont feel like it could be hacked in a few minutes, and second is, how are those maps produced ?!?!? does there exist a maping for ultrafractal ?! or are they "hand" produced !?
Logged

---

divide and conquer - iterate and rule - chaos is No random!
Pauldelbrot
Fractal Senior
******
Posts: 2592



pderbyshire2
« Reply #7 on: September 24, 2011, 06:40:49 AM »

My Forks video uses keyframe interpolation, but the stepping isn't obvious because of the advanced bicubic interpolation used to blend the keyframes to create the output frames. It's far from real-time, though.

As for producing the exponential maps, that much is fairly simple: take image coordinates, rescale them so x ranges from 0 to 2π and y ranges from 1 to -ln ω, and take z = ey + ix.

That means z = ey(cos x + i sin x).

If ω is 1050, for example, the largest modulus for z will end up being e and the smallest will end up being 10-50 and the argument will complete a full circle as x varies.

Just add the target center coordinates to z afterward and you get it centered there.

This transforms from image space to coordinates for Mandelbrot calculations. To generate Lilac Exponent, this suffices. Other things get trickier. For starters, a distance estimator requires an extra step in the derivative calculations, as otherwise the filaments will be either too thin near the top or too fat near the bottom.

Movie-making requires performing the inverse transformation on the images generated, which is also possibly complicated.

UF cannot make movies in this manner, I'm fairly sure. And the last time I used it it didn't care much for transformations that made the effective magnification vary much across the image -- periodicity checking in particular went haywire, and turning it off made everything excruciatingly slow. And it would use too low a precision in places. This could be fixed, I expect, by using a uxf that also downscaled the whole thing so the pixels were the same size in pre-transformation space as in the deepest zoom obtained. So, the whole thing would be scaled by 1/ω and you'd have to set the magnification to ω to fix everything up. And then it applies the highest precision math even to the low-magnification areas at the top of the image, so still less than ideal efficiency.

Using it to generate blocks for conversion into movies would work better, as the magnification, and thus the precision, would only need to be sufficient for the bottom of the block being generated. So the precision would be higher for successive blocks, but low for the initial ones, similarly to with successive keyframes.
Logged

bib
Global Moderator
Fractal Senior
******
Posts: 2070


At the borders...


100008697663777 @bib993
WWW
« Reply #8 on: September 24, 2011, 08:26:11 AM »

More interesting than a zoom would be an animation of the exponential map by moving the target point coordinates.
Logged

Between order and disorder reigns a delicious moment. (Paul Valéry)
Pauldelbrot
Fractal Senior
******
Posts: 2592



pderbyshire2
« Reply #9 on: September 24, 2011, 02:44:33 PM »

I thought of that, but the problem is that if the target point moves relatively slowly as seen at the maximum zoom depth, only the bottom end of the image will change noticeably, and if the target point moves quickly enough for much change to be visible higher up in the image, the bottom part will be flickering madly and will basically just be noise.
Logged

bib
Global Moderator
Fractal Senior
******
Posts: 2070


At the borders...


100008697663777 @bib993
WWW
« Reply #10 on: September 24, 2011, 03:48:28 PM »

I understand. You would have to find a reasonable depth to make it move fast enough in the upper/middle part and avoid noise at the bottom, and unite effort with this thread: http://www.fractalforums.com/general-discussion-b77/how-would-you-define-a-path-along-mandelbrot-border/msg36540/#msg36540
Logged

Between order and disorder reigns a delicious moment. (Paul Valéry)
cKleinhuis
Administrator
Fractal Senior
*******
Posts: 7044


formerly known as 'Trifox'


WWW
« Reply #11 on: September 24, 2011, 06:51:19 PM »

People arent you talking the log mapping into a normal map reversing the log effects?

How long takes calculation of such a map?
Logged

---

divide and conquer - iterate and rule - chaos is No random!
Pauldelbrot
Fractal Senior
******
Posts: 2592



pderbyshire2
« Reply #12 on: September 24, 2011, 08:35:27 PM »

Applying the map itself doesn't take much time at all, since the math for it only has to be done once per pixel instead of once per iteration.
Logged

Pages: [1]   Go Down
  Print  
 
Jump to:  

Related Topics
Subject Started by Replies Views Last post
Exponent increment Images Showcase (Rate My Fractal) HPDZ 0 916 Last post March 21, 2009, 10:02:51 PM
by HPDZ
Splitting up the exponent into a triplex Theory cbuchner1 10 2597 Last post December 13, 2009, 09:43:44 PM
by Paolo Bonzini
Direct colouring exponent smoothing? 2D (new) Theories & Research Alef 4 687 Last post February 20, 2012, 04:35:29 PM
by Alef
Working on more advanced exponent smoothing UltraFractal Alef 2 5585 Last post July 18, 2012, 04:27:46 PM
by Alef
6 digit exponent Kalles Fraktaler Gallery Kalles Fraktaler 9 3291 Last post April 12, 2017, 11:09:22 PM
by Kalles Fraktaler

Powered by MySQL Powered by PHP Powered by SMF 1.1.21 | SMF © 2015, Simple Machines

Valid XHTML 1.0! Valid CSS! Dilber MC Theme by HarzeM
Page created in 0.627 seconds with 24 queries. (Pretty URLs adds 0.025s, 2q)