Fractals and L-SystemsBrian Cavalier15-462November 25, 1997Overview The notion of a fractal Self similarity and Iteration Fractal Dimension Fractal Uses L-SystemsWhats With Euclid Anyway? (Motivation) Arent spheres, cubes, and polygons good enough? Well, it depends on your intent, but . Not many interesting real-world objects are really traditional geometric objects. Coastlines, trees, lightning These could be modeled with cylinders, polygons, etc, but . Their true level of complexity can only be crudely approximated with traditional geometric shapesFirst, a Question How long is the coast line of Britain? How would you measure it?A Solution? Start by looking at it from a satellite Pick equally spaced points and draw lines between them. Then measure the lines Now you know the length, right? Well, sort of . What if you move closer and decrease the distance between the points? Suddenly what looked like a straight stretch of coast becomes bays and peninsulasThe Notion of a Fractal “. a geometrically complex object, the complexity of which arises through the repetition of form over some range of scales.” - Ken Musgrave, Texturing and Modeling Say what?Self-Similarity and Iteration Simple Shapes repeat themselves exactly at different scales Koch curves and snowflakes Statistical Statistics of a random geometry are similar at different scales Trees, rivers, mountains, lightningPhysical Dimension A point, line, plane, and cube all have physical dimension that we accept as being 0, 1, 2, and 3 respectively. Mandelbrots view Dimension is a scale-dependent term Consider zooming in on a ball of threadFractal Dimension In the Euclidian plane we usually speak of topological dimension, which is always an integer. Fractal dimensions can have non-integer values. What does a dimension of, say, 2.3 mean? 2 is the underlying Euclidian dimension of the fractal The fractional value “slides” from 0 to 0.9999. as the fractal goes from occupying its Euclidian dimension, e.g. plane, to densely filling some part of the next higher dimension.Simple Fractals Using Iteration Use mathematical iteration and simple logic to produce amazing images One kind, you have already seen in the Koch and Sierpinski fractals Another kind is more numerical Mandelbrot Julia fractional Brownian motionMandelbrot Set - How? Simple algorithm using points on the complex plane Pick a point on the complex plane The corresponding complex number has the form: x + i*y, where i = sqrt( - 1 ) Iterate on the function Zn = Zn-1 2 + C Where Z0 = 0, and Z1 = C2 + C What does Z do? It either Remains near the origin, or Eventually goes toward infinityMandelbrot Set - How? (2) To produce pretty pictures, do this for every point C on the complex plane where -2.5 x 1.5, and -1.5 y 2, the iteration will go to infinity. Color the point C based on the number of iterationsJulia Sets Just a variant on Mandelbrot Sets There is an entire Julia Set corresponding to each point in the complex plane. An infinite number of Julia Sets Most interesting sets tend to be those found by using points just outside the Mandlebrot set. Similar Iteration formula, but vary Z not C Zn = Zn-12 + CFractional Brownian Motiondouble fBm( Vector point, double H, double lacunarity, double octaves ) if ( firstTimeCalled ) initialize exponent table for octavesfor( i=0 to octaves-1 ) value = BasisFuction( point )*exponentForOctave( i );point.x *= lacunarity;point.y *= lacunarity;point.z *= lacunarity;if( octaves not and integer ) value += fractionalPartOf( octaves ) * BasisFunction( point )*exponentForOctave( i );return value;Cool, But What are They Good For? Not just neat pictures in 2D Procedural Textures Terrain Generation Other Realism Music?!?L-Systems Remember the Koch Curve & Snowflake? Think of it as a grammar:Just Add Water . L-Systems “grow” based on their production rules Plants Cells Can control the iteration of production rules and actually animate the growth Grammars of fine enough granularity could simulate growth at the cell level . talk about eating CPU cycles .