Infinite Cheese Fractal using WPF 3D and F#

I always liked fractals, because they look like objects from another world, but on the other side if you look at some things in our world you can see many similarities with fractals (but not quite as ideal with the infinite level of precision). One of my favorite fractals is 3D version of Sierpinski carpet [1], which itself is based on very famous Cantor set. Quite long time ago I thought that it would be nice to implement animation of flying through this fractal, but I was never good in 3D graphics and it looked like a lot of work, so I never get to doing it. Luckily, now with F#, which makes it very easy to write the code to generate the fractal and with WPF 3D, which can be easily used to animate the fractal, I finally had everything I needed to do it, so here it is!

How does it work?

Before looking at the source code, I'd like to explain how the animation works, because it uses one very simple trick. Even though it looks, that the precision of the model is increased every time the camera turns up or down when flying through the fractal, the shape isn't actually changing. The effect is achieved by the fact that the position of camera changes when turning up or down and the view starts again from a location before the whole cube. This means that the model is not changing and we only need to do a loop of camera animation to get the feeling of infinite movement through the fractal. The code that generates the fractal is written in F# (and I will shortly describe the key parts below) and the code to do the animation is declaratively specified in XAML.

Generating the Fractal in F#

The first problem that we will look at is how to generate the fractal. As usually in 3D graphics we'll need to generate a collection of triangles, but the code will first compose a fractal from small cubes and then turn them into triangles. There is also one optimization, which occurs when placing two cubes side-by-side. Obviously we don't want to include the sides that would be hidden, so this is handled in the code that composes the fractal and the code generates reasonable number of triangles.

First, we'll define triangles from which the cube is composed. This needs to be done by hand and it is just a bunch of numbers, so you can look at the attached source code for the complete declaration. The type of this value is however interesting, so let's look at the type:

// 3D point represented using integers
type pointi3d = int * int * int
// Triangle using integral points
type trianglei = pointi3d * pointi3d * pointi3d
// A value that represents a cube
val cube : ((int * int * int) * trianglei list) list

As we can see the cube is represented as a list of sides (so the length of the list will be 6) and for each side we have a tuple that represents the side (for example left side will have (-1, 0, 0), bottom side will have (0, -1, 0) etc.) and the side is represented as collection of triangles (we need two triangles for every rectangular side). The cube represented by a cube value has size 1*1*1. Now that we have a cube, we also need a function that will return only the sides that we need:

// Returns a cube with filtered sides
let GetCube incl_sides = 
  [ for (side,trigs) in cube 
      when Set.mem side incl_sides
      ->> trigs ]

The natural representation of needed sides is a set which contains tuples that represent the needed sides (which I mentioned earlier), so the type of incl_sides value is Set<int*int*int>. The function takes sides from the cube, filters those that should be included (because the side identifier is included in the set) and then returns all triangles from the side, so the result of the function will be simply a collection of triangles.

The next function is a function that we will call during every recursive step and that will call recursively our function for generating cubes and collect the generated triangles. Before looking at the function we need to define the 'pattern' of the fractal. In the actual code, this is represented using 3D array (created using Array3 module), but the values look like this:

The pattern representing the fractal:
  [ [1; 1; 1]; [1; 0; 1]; [1; 1; 1] ];
  [ [1; 0; 1]; [0; 0; 0]; [1; 0; 1] ];
  [ [1; 1; 1]; [1; 0; 1]; [1; 1; 1] ];

By the way, if you want to experiment a bit you can try changing the function that generates the pattern to return the opposite values, this means that it would return 1 instead of 0 and respectively - this generates another interesting fractal, but you would also have to change the animation as the existing one would 'fly' through the model.

Now, let's look at the PatternMap function, which uses the pattern and calls a function given as an argument for every smaller cube generated using the pattern. When you look at the function signature, you can see that the function takes a set of sides as an argument (this represents the sides of the whole cube that should be included) and a function that will be called recursively to generate the triangles. This function takes coordinates (x, y, z) of the smaller cube to generate and a set of sides that should be included for this smaller cube (this set depends on the pattern, but also on the argument specifying which sides should of the large cube should be included):

  
// Takes set representing included sides (around the cube) and calls 'f'
// for every sub-cube in the cube where pattern has '1', giving it  
// coordinates and set with sides to include in the cube.
//
// Type signature:
//   type side = int*int*int
//   Set<side> -> (int*int*int -> Set<side> -> #seq<'b>) -> list<'b>
let PatternMap incl_sides f =

  // Calculates set of sides to be included for specific location in the 
  // pattern. Uses 'incl_sides' for lookup when testing border sides and
  // uses the pattern for sides inside the pattern.
  let get_included_sides x y z = 
    Set.of_seq
      (seq 
        { // loop over all possible 'directions',
          // test if out of range and use either pattern or 'incl_sides'
          for idx, neq, (dx, dy, dz) in 
              [ (x, 0, (-1,0,0)); (y, 0, (0,-1,0)); (z, 0, (0,0,-1));
                (x, 2, ( 1,0,0)); (y, 2, (0, 1,0)); (z, 2, (0,0, 1)); ] do
            if ((idx <> neq && pattern.[x+dx, y+dy, z+dz] = 0) ||
                (idx = neq  && Set.mem (dx, dy, dz) incl_sides)) then yield (dx, dy, dz) })    
  
  // Recursively collect triangles from all the smaller 
  // cubes that should be included (as specifyied by the pattern).
  [ for x in [0 .. 2] do
      for y in [0 .. 2] do
        for z in [0 .. 2] do
          if (pattern.[x,y,z] = 1) then
            yield! f (x, y, z) (get_included_sides x y z) ]

The function contains one inner function (get_included_sides), which generates a set with sides to be included for a smaller cube and the return value is generated by sequence comprehension, which loops over all the elements (small cubes) in the pattern and calls the function given as an argument (f). The sequence comprehension returns using yield!, which means that it collects all the recursively generated triangles and returns a list containing all of them.

As a last step we need to implement the recursive function that takes depth as an arguments and returns triangles using GetCube when the depth reaches some specified level, or calls PatternMap giving it a function that calls Generate recursively for every generated cube. Note that the function also needs to move the recursively generated cubes accordingly to the depth of the recursion:

let rec Generate k incl_sides = 
  if k = 1 then 
    (GetCube incl_sides) 
  else
    let d = k/3
    PatternMap incl_sides ( fun (x, y, z) incl_sides -> 
      (Generate d incl_sides) |> translate (x*d, y*d, -z*d)  )

And that's all - the rest of the code that I didn't comment here mostly deals with conversion of the generated triangles (which contained coordinates in the edges) to the format required by WPF (triangles contain just indices to some array with edges), but that's not very interesting. The second part that I didn't mention is calling the WPF functionality, but as F# is .NET language this is very straightforward, so this is commented only in the complete source code, which you can find below. You can also look at a good introduction to this topic in an article that discusses using WPF 3D from F# written by Robert Pickering [2].

Animating the Camera in WPF

Now let's look at the second part of the application, in which we'll use XAML (which is a declarative language based on XML, which is used for defining user interface and some basic interactions including animations in WPF). We'll need to declare a Storyboard, which is an object that describes an animation. Our storyboard will first perform an animation that moves the camera from the initial position (which is far from the fractal) closer to the object and then we'll use ParallelTimeline object, which can contain an animation that is executed forever. In this repeated animation we start moving the camera from a position right before the fractal and move it into the fractal and we'll also change the LookDirection property of the camera when turning up or down (there are two distinct parts of the animation, first which moves the camera up and second which moves the camera down, but the following code sample includes only the first part, because the second is similar):

<Storyboard>
  <!-- First, move to the fractal -->
  <Point3DAnimation Storyboard.TargetName="cam" 
    Storyboard.TargetProperty="Position" Duration="0:0:4" 
    From="0,0,100" To="0,0,27" RepeatBehavior="1x"/>
    
  <!-- Repeat fractal animation forever -->
  <ParallelTimeline RepeatBehavior="Forever" BeginTime="0:0:4">
    <!-- Move forward -->
    <Point3DAnimation Storyboard.TargetName="cam" 
      Storyboard.TargetProperty="Position" BeginTime="0:0:0"
      From="0,0,27" To="0,0,-9" Duration="0:0:4" RepeatBehavior="1x" />
    <!-- Rotate camera up -->
    <Vector3DAnimation Storyboard.TargetName="cam" 
      Storyboard.TargetProperty="LookDirection" BeginTime="0:0:3"
      From="0, 0, -1" To="0, 1, 0" Duration="0:0:1" RepeatBehavior="1x" />
      
    <!-- Move forward & rotate camera down -->
    <!-- ... -->
  </ParallelTimeline>
</Storyboard>

Animation of Position property is described using Point3DAnimation, which animates a property specified by TargetProperty from an initial value (From) to a target value (To) interpolating the coordinates of the 3D point linearly. The second animation primitive which I used in this example is Vector3DAnimation, which similarly animates a 3D vector, which specifies a direction in WPF.

Downloads and References

• Download the 3D fractal source code (7.68 kB)
• For a latest version of the source code visit the F# Samples project at CodePlex

• [1] Sierpinski carpet - Wikipedia
• [2] Bending the Cat: F# meets WPF 3D - Robert Pickering's Strange Blog