Fractals
Fractal
naming: fractional dimension
Definition:
self-similar $$\to$ when zoomed in, look the same
Types:
- Exactly self-similar
- Statistically self-similar
Exactly Self-similar
If zoomed in, there is no way to tell that we have zoomed in.
Sierpinski Carpet
- A square divided into 9 squares
- The center square is empty
- Each other square is divided again
Koch Snowflake
- Chop the lines into 3 Segments
- replace the middle one with equal lateral triangle
- Chop and replace each segment
The important property is that when we zoom in on an edge, it is arbitrarily “bumpy” - non-smooth. This is similar to things like shorelines. There is a self-similarity in natural shorelines.
However, shorelines are not as bumpy as Koch Snowflakes. They are smoother. Hence, we need a concept to describe the bumpiness.
Length of Koch Snowflake
Each Step increases the length to $$\dfrac{4}{3} \times$ original. Hence, Koch Snowflake is infinitely long.
$$l_k = \dfrac{4}{3} l_{k-1}$
Question: How quickly does Koch Snowflake’s length converge to infinity?
Measuring Length of Fractal Line
Different measuring scales lead to different length.
From the starting point, jump a fixed distance, $$d_u$, and measure how many $d_u$ are there in the line.
Each different $$d_u$ results in a unique length, and as $d_u$ approaches 0, the length measured approaches $\infty$
The scale is related to length and this function describes the bumpiness of a fractal line. This is called Fractal Dimension.
- Higher Fractal Dimension means more bumpiness
- Lower Fractal Dimension means less bumpiness
Shoreline/Mountain Topology
Use fractal dimension to model a bumpy line, and computationally derive the line, rather than describing more details.
Statistically Self-similar
Recursive Tree: Tree := Stick + Tree + Tree
Moreover, we need to take care of the angles, length and returning position.
It becomes:
- Stick
- Turn
- Tree -> this will expand to the same routine
- Turn
- Tree -> this will expand to the same routine
- Turn
- Backwards
L-System
The above process can be described by CFG:
$$T:S\leftarrow T \rightarrow \rightarrow T \leftarrow \overline{S}$
This use of CFG is called L-System.
Improvement to L-System Tree
- Randomness : This introduces Statistically similar fractal image.
The sub-parts are statistically similar to the original image, but not exactly the same.
To create a nice tree, it is important to examine each tree. There is a grammar to each type of tree, describing its patterns.
However, sadly trees don’t grow by the fractal model.
Incorporating Randomness Into Fractals
Example Algorithm (Subdivide and Offset)
repeat
foreach segment
offset midpoint for random distance
hence create two segments
- deeper repetition: bumpier
More sophisticated examples:
Height Map
A raster vector of height
- Can represent any terrain with no overlapping height (not bumpy topology, water, etc.)
- Cannot represent extremely rocky terrain
Diamond Square
- Level 0: Four corners set to $$h = 0$
- Level 1: Mid-point $$m_1$ set to $h_1 += random$
- Level 2: Point on Edges aligned with $$m_1$, offset randomly
- Level 3: Mid-point of each sub-square, offset randomly
- …
The result could look something like:
The problem is the grid pattern is visible. There are ‘+’ in the graph, so rotating the graph will be noticed (not entirely natural)
Solution: Use
Applications:
-
NOT good for terrain. Natural terrain has very few local minima. The minima will drain, and become global minima. This is not reflected by diamond square subdivision.
-
Clouds. Clouds density is similar to the patterns generated from diamond square subdivision.
-
Dirt. This could create “dirty” texture to human-created objects.
Perlin Fractal
A perlin fractal is created by taking in a height map, downsize it, and fill itself with the small height map.