fractal.md

   1 # Fractal
   2
   3 Informally speaking fractal is a shape that's geometrically "infinitely complex" while being described in an extremely simple way, e.g. with a very simple formula or [algorithm](algorithm.md). Shapes found in the nature, such as trees, mountains or clouds, are often fractals. Fractals show self-similarity, i.e. when "zooming" into an ideal fractal we keep seeing it is composed, down to an infinitely small scale, of shapes that are similar to the shape of the whole fractal; e.g. the branches of a tree look like smaller versions of the whole tree etc.
   4
   5 TODO: brief history
   6
   7 Fractals are the [beauty](beauty.md) of mathematics that can easily be seen even by non-mathematicians, so are probably good as a motivational example in [math](math.md) education.
   8
   9 Fractal geometry is a kind of [geometry](geometry.md) that examines these intricate shapes -- it turns out that unlike "normal" shapes such as circles and cubes, whose attributes (such as circumference, volume, ...) are mostly quite straightforward, perfect fractals (i.e. the mathematically ideal ones whose structure is infinitely complex) show some greatly unintuitive properties -- basically just as anything involving [infinity](infinity.md) they can get very tricky. For example a 2D fractal may have **finite area but infinite circumference** -- this is because the border is infinitely complex and swirls more and more as we zoom in, increasing the length of the border more and more the closer we look.
  10 This was famously notice e.g. when people tried to measure lengths of rivers or coastlines (which are sort of fractal shapes) -- the length they measured always depended on the length of the ruler they used; the shorter ruler you use, the greater length you get because the meanders of the details increase it. For this reason it is impossible to exactly and objectively give an exact length of such a shape.
  11
  12 Fractal is formed by [iteratively](iteration.md) or [recursively](recursion.md) (repeatedly) applying its defining rule -- once we repeat the rule infinitely many times, we've got a perfect fractal. [In the real world](irl.md), of course, both in nature and in computing, the rule is just repeat many times as we can't repeat literally infinitely. The following is an example of how iteration of a rule creates a simple tree fractal; the rule being: *from each branch grow two smaller branches*.
  13
  14 ```
  15                                                     V   V V   V
  16                                 \ /   \ /         V  \ /   \ /  V
  17                |     |      _|   |     |   |_   >_|   |     |   |_<
  18             '-.|     |.-'     '-.|     |.-'        '-.|     |.-'
  19    \   /        \   /             \   /                \   /
  20     \ /          \ /               \ /                  \ /
  21      |            |                 |                    |
  22      |            |                 |                    |
  23      |            |                 |                    |
  24
  25 iteration 0  iteration 1       iteration 2          iteration 3
  26 ```
  27
  28 Mathematically fractal is a shape whose [Hausdorff dimension](hausdorff_dimension.md) (the "scaling factor of the shape's mass") may be non-integer and is bigger than its [topological dimension](topological_dimension.md) (the "normal" dimension suh as 0 for a point, 1 for a line, 2 for a plane etc.). For example the [Sierpinski triangle](sierpinski_triangle.md) has a topological dimension 1 but Hausdorff dimension approx. 1.585 because if we scale it down twice, it decreases its "weight" three times (it becomes one of the three parts it is composed of); Hausdorff dimension is then calculated as log(3)/log(2) ~= 1.585.
  29
  30 [L-systems](l_system.md) are one possible way of creating fractals. They describe rules in form of a [formal grammar](grammar.md) which is used to generate a string of symbols that are subsequently interpreted as drawing commands (e.g. with [turtle graphics](turtle_graphics.md)) that render the fractal. The above shown tree can be described by an L-system. Among similar famous fractals are the [Koch snowflake](koch_snowflake.md) and [Sierpinski Triangle](sierpinski_triangle.md).
  31
  32
  33 ```
  34               /\
  35              /\/\
  36             /\  /\
  37            /\/\/\/\
  38           /\      /\
  39          /\/\    /\/\
  40         /\  /\  /\  /\
  41        /\/\/\/\/\/\/\/\
  42
  43      Sierpinski Triangle
  44 ```
  45
  46 Fractals don't have to be [deterministic](determinism.md), sometimes there can be [randomness](random.md) in the rules which will make the shape be not perfectly self-similar (e.g. in the above shown tree fractal we might modify the rule to *from each branch grow 2 or 3 new branches*).
  47
  48 Another way of describing fractals is by iterative mathematical formulas that work with points in [space](space.md). One of the most famous fractals formed this way is the **[Mandelbrot set](mandelbrot_set.md)**. It is the set of [complex numbers](complex_number.md) *c* such that the series *z\_next = (z\_previous)^2 + c*, *z0 = 0* does not [diverge](divergence.md) to [infinity](infinity.md). Mendelbrot set can nicely be rendered by assigning each iteration's result a different color; this produces a nice colorful fractal. [Julia sets](julia_set.md) are very similar and there is infinitely many of them (each Julia set is formed like the Mandelbrot set but *c* is fixed for the specific set and *z0* is the tested point in the complex plain).
  49
  50 Fractals can of course also exist in 3 and more dimensions so we can have also have animated 3D fractals etc.
  51
  52 ## Fractals In Tech
  53
  54 [Computers](computer.md) are good for exploring and rendering fractals as they can repeat given rule millions of times in a very short time. Programming fractals is quite easy thanks to their simple rules, yet this can highly impress noobs.
  55
  56 However, as shown by Code Parade (https://yewtu.be/watch?v=Pv26QAOcb6Q), complex fractals could be rendered even before the computer era using just a projector and camera that feeds back the picture to the camera. This is pretty neat, though it seems no one actually did it back then.
  57
  58 A nice [FOSS](foss.md) program to interactively zoom into 2D fractals is e.g. [xaos](xaos.md).
  59
  60 3D fractals can be rendered with [ray marching](ray_marching.md) and so called *distance estimation*. This works similarly to classic [ray tracing](ray_tracing.md) but the rays are traced iteratively: we step along the ray and at each step use an estimate of the current point to the surface of the fractal; once we are "close enough" (below some specified threshold), we declare a hit and proceed as in normal ray tracing (we can render shadows, apply materials etc.). The distance estimate is done by some clever math.
  61
  62 [Mandelbulber](mandelbulber.md) is a [free](free_software.md), advanced software for exploring and rendering 3D fractals using the mentioned method.
  63
  64 [Marble Racer](marble_racer.md) is a [FOSS](foss.md) [game](game.md) in which the player races a glass ball through levels that are animated 3D fractals. It also uses the distance estimation method implemented as a [GPU](gpu.md) [shader](shader.md) and runs in real-time.
  65
  66 Fractals are also immensely useful in [procedural generation](procgen.md), they can help generate complex art much faster than human artists, and such art can only take a very small amount of storage.
  67
  68 There exist also [compression](compression.md) techniques based on fractals, see [fractal compression](fractal_compression.md).
  69
  70 There also exist such things as fractal antennas and fractal transistors.
  71
  72 ## Example
  73
  74 Here is [C](c.md) code that draws one of the super simple fractals: Sierpinski triangle:
  75
  76 ```
  77 #include <stdio.h>
  78
  79 char sierpinski(int x, int y, int w, int h)
  80 {
  81   if (x >= w/2 && y < h/2)
  82     return ' ';
  83
  84   if (w <= 1 || h <= 1)
  85     return 'H';
  86
  87   return sierpinski(x % (w/2),y % (h/2),w/2,h/2);
  88 }
  89
  90 int main(void)
  91 {
  92   #define W 32
  93   #define H 32
  94
  95   for (int y = 0; y < W; ++y)
  96   {
  97     for (int x = 0; x < H; ++x)
  98     {
  99       char c = sierpinski(x,y,W,H);
 100       putchar(c); putchar(c);
 101     }
 102
 103     putchar('\n');
 104   }
 105
 106   return 0;
 107 }
 108 ```
 109
 110 which outputs:
 111
 112 ```
 113 HH
 114 HHHH
 115 HH  HH
 116 HHHHHHHH
 117 HH      HH
 118 HHHH    HHHH
 119 HH  HH  HH  HH
 120 HHHHHHHHHHHHHHHH
 121 HH              HH
 122 HHHH            HHHH
 123 HH  HH          HH  HH
 124 HHHHHHHH        HHHHHHHH
 125 HH      HH      HH      HH
 126 HHHH    HHHH    HHHH    HHHH
 127 HH  HH  HH  HH  HH  HH  HH  HH
 128 HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH
 129 HH                              HH
 130 HHHH                            HHHH
 131 HH  HH                          HH  HH
 132 HHHHHHHH                        HHHHHHHH
 133 HH      HH                      HH      HH
 134 HHHH    HHHH                    HHHH    HHHH
 135 HH  HH  HH  HH                  HH  HH  HH  HH
 136 HHHHHHHHHHHHHHHH                HHHHHHHHHHHHHHHH
 137 HH              HH              HH              HH
 138 HHHH            HHHH            HHHH            HHHH
 139 HH  HH          HH  HH          HH  HH          HH  HH
 140 HHHHHHHH        HHHHHHHH        HHHHHHHH        HHHHHHHH
 141 HH      HH      HH      HH      HH      HH      HH      HH
 142 HHHH    HHHH    HHHH    HHHH    HHHH    HHHH    HHHH    HHHH
 143 HH  HH  HH  HH  HH  HH  HH  HH  HH  HH  HH  HH  HH  HH  HH  HH
 144 HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH
 145 ```
 146
 147 ## See Also
 148
 149 - [Lissajous curve](lissajous_curve.md)
 150 - [rose curves](rose_curve.md)
 151 - [cardioid](cardioid.md)
 152 - [spirograph](spirograph.md)
 153 - [procedural generation](procgen.md)
 154 - [turtle graphics](turtle_graphics.md)