Algorithms

Hubička algorithm

XaoS was originally just a "poorly written" Mandelbrot viewer^[1] until Jan Hubička added efficient zooming (= real time zoom^[2])^[3], using a technique sometimes called the XaoS algorithm or Hubička algorithm.

At the time fractal zoom movies were produced by completely recalculating each frame, even though they naturally had much of their area in common with each other. This made interactive zooming impossible without very powerful computers.^[4] Furthermore, unless even more processing is used in order to do antialiasing, recalculating every frame produces a 'twinkle' effect as small bright areas hit and then disappear between pixels.^[5]

Yet allowing the user to zoom, rather than jump as in Fractint, seemed like the most natural way to interact with fractals. In order to create an interactive zoom, Hubička needed to find a way to save the calculations which were already made. It would take up too much memory to save every pixel ever calculated, so the Hubička algorithm only saves the previous frame, and rather than remembering the location of each pixel it can keep them aligned in rows and columns and remember those instead.

The most difficult part of the XaoS algorithm was choosing which saved rows and columns to draw where. Doing this wrong results in distorted images, yet it must be done quickly to be useful. After several different heuristics were tried, eventually the problem was treated as an optimization problem.

The remaining rows and columns are colored in the same as the closest row/column, and are freshly calculated as the CPU gets time to do so. This is a careful balance between keeping the zoom going and increasing the level of detail. Calculating areas where the image is being zoomed to is put at a higher priority since these will be on the screen the longest and this is likely where the user is looking anyway. Zooming out, the reverse occurs and the priority is on the edges.^[5]

The Hubička algorithm can also be applied to zooming in on other images where the pixels are calculated, and has been used in other software such as the rtzme complex function graphing program,^[6] and other fractal zoomers.

Images

commons : Category:Fractals created with Xaos

Command line options

To find it use :

xaos -help

Output is :

 XaoS3.5 help text
 (This help is genereated automagically. I am sorry for all inconvencies)

option string   param   description

 -delay          number
                  Delay screen updates (milliseconds)
 -driver         string
                  Select driver
 -list            List available drivers. Then exit
 -config          Print configuration. Then exit
 -speedtest       Test speed of calculation loop. Then exit
 -threads        number
                  Set number of threads (CPUs) to use
 -pipe           string
                  Accept commands from pipe (use "-" for stdin)
 -maxframerate   number
                  Maximal framerate (0 for unlimited - default)

Screen size options:

  Knowledge of exact screen size makes random dot stereogram look better. 
  Also is used for choosing correct view area

 -screenwidth    f.point
                  exact size of screen in centimeters
 -screenheight   f.point
                  exact size of screen in centimeters

  Use this option in case you use some kind of virtual screen
  or something similar that confuses previous options

 -pixelwidth     f.point
                  exact size of one pixel in centimeters
 -pixelheight    f.point
                  exact size of one pixel in centimeters
 -formula        string
                  user formula
 -forminit       string
                  z0 for user formula

Animation rendering:

 -render         string
                  Render animation into seqence of .png files
 -basename       string
                  Name for .png files (XaoS will add 4 digit number and extension
 -size           string
                  widthxheight
 -renderimage    string
                  256 or truecolor
 -renderframerate  f.point
                  framerate
 -antialiasing    Perform antialiasing (slow, requires quite lot of memory)
 -alwaysrecalc    Always recalculate whole image (slowes down rendering, increases quality)
 -rendervectors   Render motion vectors (should be used for MPEG encoding)
 -iframedist     number
                  Recommended distance between I frames in pat file (should be used for MPEG encoding)

X11 driver options:

 -display        string
                  Select display
 -size           string
                  Select size of window (WIDTHxHEIGHT).
 -sync            Generate sync signals before looking for events. This
			helps on old and buggy HP-UX X servers.
 -shared          Use shared colormap on pseudocolor display.
 -usedefault      Use default visual if autodetection causes troubles.
 -nomitshm        Disable MITSHM extension.
 -fullscreen      Enable fullscreen mode.
 -windowid       number
                  Use selected window.
 -window-id      number
                  Use selected window.
 -root            Use root window.

AA driver options:

 -aadriver       string
                  Select display driver used by aa-lib
 -kbddriver      string
                  Select keyboard driver used by aa-lib
 -mousedriver    string
                  Select keyboard driver used by aa-lib
 -font           string
                  Select font
 -width          number
                  Set width
 -height         number
                  Set height
 -minwidth       number
                  Set minimal allowed width
 -minheight      number
                  Set minimal allowed height
 -maxwidth       number
                  Set maximal allowed width
 -maxheight      number
                  Set maximal allowed height
 -recwidth       number
                  Set recommended width
 -recheight      number
                  Set recommended height
 -normal          enable usage of narmal characters
 -nonormal        disable usage of narmal characters
 -dim             enable usage of dim(half bright) characters
 -nodim           disable usage of dim(half bright) characters
 -bold            enable usage of bold(double bright) characters
 -nobold          disable usage of bold(double bright) characters
 -boldfont        enable usage of boldfont characters
 -noboldfont      disable usage of boldfont characters
 -reverse         enable usage of reversed characters
 -noreverse       disable usage of reversed characters
 -all             enable usage of reserved characters
 -eight           enable usage of non ansi characters
 -extended        enable usage of extended character set
 -inverse         enable inverse
 -bright         number
                  set bright (0-255)
 -contrast       number
                  set contrast (0-255)
 -gamma          f.point
                  set famma (0-1)
 -nodither        Disable dithering
 -floyd_steinberg   Enable floyd steinberg dithering
 -error_distribution   Enable error distribution dithering
 -random         number
                  Set random dithering value
 -dimmul         f.point
                  Multiply factor for dim color (5.3)
 -boldmul        f.point
                  Multiply factor for bold color (5.3)
 -nomouse         Disable mouse

Command line options only

 -print_menus     print menus specifications of all menus
 -print_menu     string 
                  print menu specification
 -xshl_print_menustring 
                  print menu specification in xshl format
 -xshl_print_menus print all menu specifications in xshl format
 -print_dialog   string 
                  print dialog specification

File

 -loadpos        input_file 
                  Load
 -savepos        output_file 
                  Save
 -record         output_file 
                  Record
 -play           input_file 
                  Replay
 -saveimg        output_file 
                  Save image
 -loadexample     Load random example
 -savecfg         Save configuration

Fractal

 -usrform        string 
                  User formula
 -usrformInit    string 
                  User initialization
 -perturbation   real_number  real_number 
                  Perturbation
 -initstate       Reset to defaults
 -julia          on|off 
                  Julia mode
 -view           real_number real_number real_number real_number 
                  View
 -angle          real_number 
                  Set angle
 -plane          integer 
                  Set plane
 -incoloring     integer 
                  Inside coloring mode
 -outcoloring    integer 
                  Outside coloring mode
 -intcoloring    integer 
                  Inside truecolor coloring mode
 -outtcoloring   integer 
                  Outside truecolor coloring mode
 -juliaseed      real_number  real_number 
                  Julia seed

Calculation

 -periodicity     Periodicity checking
 -maxiter        integer 
                  Iterations
 -bailout        real_number 
                  Bailout
 -fastjulia       Fast julia mode
 -range          integer 
                  Solid guessing range

Filters

 -edge            Edge detection
 -edge2           Edge detection2
 -threed          Pseudo 3d
 -starfield       Starfield
 -stereogram      Random dot stereogram
 -interlace       Interlace filter
 -blur            Motionblur
 -emboss          Emboss
 -palettef        Palette emulator
 -anti            Antialiasing
 -truecolor       Truecolor emulator

UI

 -letterspersec  integer 
                  Letters per second
 -autopilot       Autopilot
 -inhibittextoutput VJ mode
 -recalculate     Recalculate
 -interrupt       Interrupt
 -speed          real_number 
                  Zooming speed
 -fixedstep       Fixed step
 -nogui           Disable XaoS's builtin GUI
 -status          Status
 -ministatus      Ministatus

Misc

 -playstr        string 
                  Play string
 -text           string 
                  Display text
 -color          white|black|red 
                  Color
 -textposition   left|center|right top|middle|bottom 
                  Text position
 -message        string 
                  Message

Help

 -help            Help

Formulae

 -mandel          Mandelbrot
 -mandel3         Mandelbrot^3
 -mandel4         Mandelbrot^4
 -mandel5         Mandelbrot^5
 -mandel6         Mandelbrot^6
 -newton          Newton
 -newton4         Newton^4
 -barnsley        Barnsley1
 -barnsley2       Barnsley2
 -barnsley3       Barnsley3
 -octal           Octal
 -phoenix         Phoenix
 -magnet          Magnet
 -magnet2         Magnet2

More formulae

 -trice           Triceratops
 -catseye         Catseye
 -mbar            Mandelbar
 -mlambda         Lambda
 -manowar         Manowar
 -spider          Spider
 -sier            Sierpinski
 -carpet          S.Carpet
 -koch            Koch Snowflake
 -hornflake       Spidron hornflake
 -user            User defined

Palette

 -defpalette      Default palette
 -randompalette   Random palette
 -palette        integer integer integer 
                  Custom palette
 -cycling         Color cycling
 -cyclingspeed   integer 
                  Color cycling speed
 -shiftpalette   integer 
                  Shift palette

Dynamic resolution

 -fastmode       zero|never|animation|new|allways 
                  Dynamic resolution mode

Rotation

 -rotationspeed  real_number 
                  Rotation speed
 -autorotate     on|off 
                  Automatic rotation
 -fastrotate     on|off 
                  Fast rotation mode

Quit

 -quit            Exit now

Files

xaf

Xaos Animnation File (*.xaf ) is a file with functions for generating sequence of images

For example :

xaos-3.5/tutorial/julia.xaf

To make xaf file use record function, syntax :

(record bool [ file ])

example :

 (record #t)

or :

(record #f)

How to render image sequence from xaf file :

xaos -render [xpf_filename] -size 352x240 -antialiasing -renderframerate 24 -basename [basename]

xpf

xpf stands for Xaos Position File. This file is human-readable, and can easily be improved by hand after saving, or used as a base for animations.^[7]

See for example :

standard view (Mandelbrot set without zoom = image) :

;Position file automatically generated by XaoS 3.5
;  - a real-time interactive fractal zoomer
;Use xaos -load <filename> to display it
(initstate)
(defaultpalette 0)
(formula 'mandel)
(view -0.75 0 2.5 2.5)

when we switch to Julia mode (disabled Mandelbrot mode) :

(initstate)
(defaultpalette 0)
(formula 'mandel)
(julia #t)
(view -0.75 0 2.5 2.5)

or change c value ( = julia seed)from c=0 to c= -1

(initstate)
(defaultpalette 0)
(formula 'mandel)
(juliaseed -1 0)
(julia #t)
(view -0.8434 0.07535 2.744 2.744)

or show plane value ( default = 0 is not shown ) :

(initstate)
(defaultpalette 0)
(formula 'mandel)
(juliaseed -1 0)
(julia #t)
(plane 0)
(view -0.9127 -0.09268 2.285 2.285)

minibrot.xpf :

(initstate)
(palette 1 860134713 0)
(formula 'mandel)
(outcoloring 1)
(view -1.9854567 -1.351727E-05 0.00029196024 0.00029196024)

where view^[8] is describing viewport ( rectangle part of the plane ):

 view float float float float
 view centerRe centerIm radius angle

List of xpf files :

list by by Chris Gray Some Fractals Computed by XaoS with xpf files by Chris Gray

view

to describe plane ( view ) Xaos uses:

4 numbers in scripts
3 numbers in menu

Xaos uses to call it "radius" but it is defind as : the greater of (x2-x1= width) and y2-y1=height." This is the reason why in Xaos one can set the radius to 2/zoom.

To set the same viewpoint in XaoS using menu set 3 numbers to define circle

the real portion of the center to (x1+x2)/2
the imaginary part of center to (y1+y2)/2
"the radius" = the greater of x2-x1 and y2-y1.

where the coordinates of the upper-left and lower-right visible points, specifying the coordinates as four numbers x1, y1, x2, y2.

In xpf file plane can be described by 4 floating point numbers :^[9]

real part of the center
imaginary part of the center
width in world coordinate = x2-x1 called "a real radius"
height in world coordinte = y2-y1 called "an imaginary radius"

Syntax :

(view float float float float)

Example :

(view -0.75 0 2.5 2.5)

"People specify fractal coordinates in many ways. Some people use the coordinates of the upper-left and lower-right visible points, specifying the coordinates as four numbers x1, y1, x2, y2. 
To set the same viewpoint in XaoS, set the real portion of the center to (x1+x2)/2, the imaginary   part of center to (y1+y2)/2, and the radius to the greater of x2-x1 and y2-y1.
Other programs use a zoom factor instead of a radius. For these, you can set the radius to 2/zoom."^[10]

" ... lets you specify an ellipse instead of a circle. You can specify both a real and an imaginary radius "

usrform

(initstate)
(defaultpalette 0)
(formula 'user)
(usrform "Z^2+C")
(usrformInit "")
(view -0.4641 0.01977 2.444 2.444)

bailout

(bailout 6)

Bailout value or escape radius. Xaos uses here square of escape radius so if you want bailout value 2 put here 2*2 = 4.

formula

Syntax:^[11]

 (formula keyword)

example

 (formula mandel)

Name	description	tutorial	User formula
mandel	Standard Mandelbrot or Julia sets.	mset.xaf	Z^2+C
mandel3	Example	power.xaf	Z^3+C
mandel4	Example	power.xaf	Z^4+C
mandel5	Example	power.xaf	Z^5+C
mandel6	Example	power.xaf	Z^6+C
newton	This is Newton’s approximation method for finding the roots of a polynomial. It uses the polynomial x^3=1	newton.xaf
barnsley	Example	Example	Example
octo	Example	Example	Example
phenix	Example	Example	Example
magnet
trice

Changing named formule ( Menu/Fractal/Formule ) does not change user formule !!!

plane

Syntax :

(plane integer)

Allowed values :^[12]

value	name	description
0	mu	Normal complex plane (default)
1	1/mu	Inversion : old infinity is at 0 now and old 0 is at infinity now.
2	1/(mu+0.25)	Similar to inversion, but also moves the center outside the Mandelbrot set, so it looks parabolic.
3	lambda	lambda plane
4	1/lambda	Inversion of lambda plane
5	1/(lambda-1)	Inversion with moved center
6	1/(mu-1.40115)	Inversion with moved center

// from xaos-3.5\src\engine\plane.c 
/* 
 *     XaoS, a fast portable realtime fractal zoomer 
 *                  Copyright (C) 1996,1997 by
 *
 *      Jan Hubicka          (hubicka@paru.cas.cz)
 *      Thomas Marsh         (tmarsh@austin.ibm.com)
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */
CONST char *CONST planename[] = {
    "mu",
    "1/mu",
    "1/(mu+0.25)",
    "lambda",
    "1/lambda",
    "1/(lambda-1)",
    "1/(mu-1.40115)",
    NULL
};

// include/complex.h:57:
// #define myabs(x) ((x)>0?(x):-(x))

REGISTERS(3)
void recalculate(int plane, number_t * x1, number_t * y1)
{
    number_t x = *x1, y = *y1;
    switch (plane) {
    case 1:
	{			/* 1/mu */
	    number_t t;
	    if (myabs(x) + myabs(y) < 0.000001)
		t = INT_MAX, y = INT_MAX;
	    else {

		c_div(1, 0, x, y, t, y);
	    }
	    x = t;
	}
	break;
    case 2:
	{			/* 1/(mu + 0.25) */
	    number_t t;
	    if (myabs(x) + myabs(y) < 0.000001)
		t = INT_MAX, y = INT_MAX;
	    else {

		c_div(1, 0, x, y, t, y);
	    }
	    x = t;
	    x += 0.25;
	}
	break;
    case 3:			/* lambda */
	{
	    number_t tr, ti, mr, mi;

	    mr = x, mi = y;
	    c_pow2(x, y, tr, ti);
	    c_div(tr, ti, 4, 0, x, y);
	    c_div(mr, mi, 2, 0, tr, ti);
	    c_sub(tr, ti, x, y, mr, mi);
	    x = mr, y = mi;
	}
	break;
    case 4:			/* 1/lambda */
	{
	    number_t tr, ti, mr, mi;

	    c_div(1, 0, x, y, tr, y);
	    x = tr;
	    mr = x, mi = y;
	    c_pow2(x, y, tr, ti);
	    c_div(tr, ti, 4, 0, x, y);
	    c_div(mr, mi, 2, 0, tr, ti);
	    c_sub(tr, ti, x, y, mr, mi);
	    x = mr, y = mi;
	}
	break;
    case 5:			/* 1/(lambda-1) */
	{
	    number_t tr, ti, mr, mi;

	    c_div(1, 0, x, y, tr, y);
	    x = tr + 1;
	    mr = x, mi = y;
	    c_pow2(x, y, tr, ti);
	    c_div(tr, ti, 4, 0, x, y);
	    c_div(mr, mi, 2, 0, tr, ti);
	    c_sub(tr, ti, x, y, mr, mi);
	    x = mr, y = mi;
	}
	break;
    case 6:
	{			/* 1/(mu + 0.25) */
	    number_t t;
	    if (myabs(x) + myabs(y) < 0.000001)
		t = INT_MAX, y = INT_MAX;
	    else {

		c_div(1, 0, x, y, t, y);
	    }
	    x = t;
	    x -= 1.40115;
	}
	break;
    default:
	break;
    }
    *x1 = x;
    *y1 = y;
}

perturbation

It changes the point at which orbits start. Traditionally zero is used.^[13]

(perturbation complex)

doc

 info xaosdev.info

How to render big images ?

It is not simple.^[14] One can do it using :

using animation thru menu ( "saving your fractal to a .xpf file (File->Save), then rendering it using the Misc->Render Animation function. "^[15]
using command line options^[16]

XaoS -render fractal.xpf -size 18000x12000

How to change the resolution

"XaoS usually starts in low resolution (320x200 or so) to make calculations faster. In case you have fast computer or you need to save bigger .gif images you may change resolution. This should be done by pressing '=' in full screen drivers or simply by resizing XaoS window." ^[17]

Formula

use xpf file
use Main Menu/ Fractal/user formula
Adding Built-in Formulas^[18]
edit the source code in src/engine/formulas.c

formulas.c

#define VARIABLES register number_t n,sqrr,sqri,zre1,zim1;
#define INIT sqri=zim*zim,n=zre,zre=pre,pre=n,n=zim,zim=pim,pim=n,n=(number_t)1;
#define BTEST greater_then_1Em6(n)
#define FORMULA \
    zre1 = zre; \
    zim1 = zim; \
    n = zim * zim; \
    sqri = zre * zre; \
    sqrr = sqri - n; \
    sqri = n + sqri; \
    n = 0.3333333333 / ((sqri * sqri)); \
    zim = (0.66666666) * zim - (zre + zre) * zim * n + pim; \
    zre = (0.66666666) * zre + (sqrr) * n + pre; \
    zre1 -= zre; \
    zim1 -= zim; \
    n = zre1 * zre1 + zim1 * zim1;
#define CALC newton_calc
#include "docalc.c"

After modifying the code you must recompile XaoS to take any effect.^[19]

References

This article is issued from Wikibooks. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] XaoS man page, http://www.ibiblio.org/pub/X11/contrib/graphics/XaoS.README

[2] Real-Time Zooming Math Engine by Zoltán Kovács

[3] xaosdev.info : algorithm

[4] CS and Dance, archived from the original on 2005-12-20, https://web.archive.org/web/20051220172055/http://www.cs.wfu.edu/~burg/papers/CSAndDance.pdf

[algorithms-5] 1 2 Hubička, Jan (1997), XaoS Algorithms, archived from the original on 2014-03-28, https://web.archive.org/web/20140328130719/http://web.mit.edu/kolya/sipb/afs/root.afs/athena/activity/p/peckers/OldFiles/Programs/XaoS-2.2/doc/algorithm.txt .

[6] Visualizations on the Complex Plane, archived from the original on 2006-10-17, https://web.archive.org/web/20061017071047/http://www.math.u-szeged.hu/~kovzol/VotCP-submitted-edited-1column-final.doc

[7] Xaos- format description

[8] Xaos - view

[9] Xaos - plane description

[10] Xaos - view

[11] Xaos doc - formula

[12] GNU XaoS » Documentation » XaoS » Plane

[13] Xaos doc - perturbation

[14] Can't (easily) render high-resolution static images #53

[15] xaos-users group : resolution

[16] xaos-users group : Higher resolution on Mac OSX

[17] Xaos tutorial

[18] Xaos doc : Adding Built-in Formulas by Arpad Fekete

[19] xaos-users group : Newton fractals