Thursday, December 17, 2009

Fractal Koch Snowflakes in Silverlight

So late last night I decided that since I spend most of the day writing software for other companies, it was time to build something for my daughter. I knew right away it would be snowflakes. I'm not much of a "graphic design" guy, but I do know math, so when I can lean on math to make pretty things, I'm all for it.

What I decided to do was create some fanciful "snowflakes" that would drift around the screen. The result is the snowflake scene you can view by clicking here:

Fractal Koch Snowflakes in Silverlight.

The Koch curve made the most sense for a starting point because, well, it's fairly easy! You simply start with a line segment, break it into thirds, then extend the middle into a new triangle. The sequence looks like this:

Koch Curve

Imagine that happening with the three sides of a triangle, and you start to understand how a snowflake will come out of the process. The still picture doesn't give full justice to how it looks in motion with your CPU maxing out:

Koch Snowflake Snapshot

Download the Source

So let's get down to business. The first step was to build a factory to generate the snowflakes for me. Understanding the math is pointless (pardon the pun) unless I can turn it into a shape.

The following method will take a list of points and turn it into a path. There is no optimization or determining how wildly the points jump around ... just takes it and turns it straight into the path object:


private static Path _CreatePath(List<Point> points)
{            
    PathSegmentCollection segments = new PathSegmentCollection();

    bool first = true;

    foreach (Point point in points)
    {
        if (first)
        {
            first = false;
        }
        else
        {
            segments.Add(
                new LineSegment
                {
                    Point = point
                });
        }
    }

    PathGeometry pathGeometry = new PathGeometry();

    pathGeometry.Figures.Add(
        new PathFigure
    {
        IsClosed = true,
        StartPoint = points[0],
        Segments = segments
    });

    return new Path { Data = pathGeometry };            
}

It should be fairly straightforward ... we combine the lines into a set of segments, collapse the segments into a figure that is closed, then add the figure to the path.

Next, we need to be able to take a line segment and divide it. The math is fairly straightforward (you can Bing Koch Curve to find it). I created this little method to return the points in the way I think: one step at a time.


private static IEnumerable<Point> _RefactorPoints(Point a, Point b)
{
    yield return a; 

    double dX = b.X - a.X; 
    double dY = b.Y - a.Y;

    yield return new Point(a.X + dX / 3.0, a.Y + dY / 3.0);

    double factor = _random.NextDouble() - 0.5;

    double vX = (a.X + b.X) / (2.0 + factor) + Math.Sqrt(3.0+factor) * (b.Y - a.Y) / (6.0 + factor*2.0);
    double vY = (a.Y + b.Y) / (2.0 + factor) + Math.Sqrt(3.0+factor) * (a.X - b.X) / (6.0 + factor*2.0);

    yield return new Point(vX, vY);

    yield return new Point(b.X - dX / 3.0, b.Y - dY / 3.0);

    yield return b;
}

The segment will end up being 4 segments, or 5 points. First, we return the first point. Next, we find a point 1/3 of the way from point a to point b. Next we have some fun. The equation approximates finding the point for the apex of a unilateral triangle, but we jiggle it a bit with some randomness to make for unique snowflakes and then return that point. Next, it's 1/3 of the way to point a from point b, and finally it's point b itself.

Easy enough? Now that we can split a side into pieces, we can now write our recursive method to continuously break down segments. It will take in a level (how many iterations to do) and then start hacking away. Keep in mind the levels can't get too high because of the exponential growth (3 points becomes 15, becomes 75, etc). Here is that routine, which ultimately takes in a segment and gives me back a fully iterated collectoin of points that represent the Koch curve:


private static List<Point> _RecurseSide(Point a, Point b, int level)
{
    if (level == 0)
    {
        return new List<Point> { a, b };
    }
    else
    {
        List<Point> newPoints = new List<Point>();

        foreach (Point point in _RefactorPoints(a, b))
        {
            newPoints.Add(point);
        }

        List<Point> aggregatePoints = new List<Point>();

        for (int x = 0; x < newPoints.Count; x++)
        {
            int y = x + 1 == newPoints.Count ? 0 : x + 1;
            aggregatePoints.AddRange(_RecurseSide(newPoints[x], newPoints[y], level-1));                    
        }

        return aggregatePoints; 
    }
}

As you can see, if we hit the iteration target, we return the segment back. Otherwise, we split the segment, then recursively call the method on each new segment and decrement the level.

Now we can spin it all off with three staring points (the vertices of our triangle ... and I know that this isn't a unilateral triangle, but it works):


public static Path Create()
{
    Point a = new Point(0, 0);
    Point b = new Point(_random.NextDouble()*70.0+15.0, 0);
    Point c = new Point(0, b.X); 

    int levels = _random.Next(MIN, MAX);

    List<Point> points = new List<Point>();
    points.AddRange(_RecurseSide(a,b,levels));
    points.AddRange(_RecurseSide(b,c,levels));
    points.AddRange(_RecurseSide(c,a,levels));

    // walk the sides and iterate them
    Path retVal = _CreatePath(points);           
   
    return retVal;  
}

That gets us a snowflake. If you are a stickler for optimizing the code, a good side project would be to kill the second and third calls to recurse the side. Once we have one segment, we can simply reflect/rotate it to complete the triangle without necessarily having to compute the points all over again. I'll leave that up to some math wizard to work out with matrix transformations.

Of course, a snowflake like that is pretty boring. I added a method to colorize it using a random gradient (and random alpha so they are semi-transparent) and also set the path up with a rotate transform and plane projection, so it can be spun and twisted on the screen. Nothing special there; you can inspect those methods in the source code.

My next step was to encapsulate the snowflake in a class that would handle animating and moving it on the screen. The idea is that each snowflake has a unique behavior, and appears, falls gently, then disappears and notifies the world that's gone so we can make a new one.

The class I built, SnowFlakeEntity, is here in it's entirety:


public class SnowFlakeEntity
{
    const double LEFT = 800.0;
    const double TOP = 600.0;
    const double GONE = 700.0;

    private double _affinity; // affects behaviors

    DispatcherTimer _snowflakeFrame; 

    private Guid _identifier = Guid.NewGuid();       

    private static Random _random = new Random();

    private Canvas _surface; 

    public Canvas Surface
    {
        get { return _surface; }
    }

    private double x, y, velocity;

    private Path _snowflake;

    public Guid Identifier
    {
        get { return _identifier; }
    }
   
    public SnowFlakeEntity(Action<Path> insert) : this(insert, false)
    {
    }

    public SnowFlakeEntity(Action<Path> insert, bool fromTop)
    {
        _snowflake = SnowFlakeFactory.Create();

        _affinity = _random.NextDouble();

        velocity = _random.NextDouble() * 10.0;
        x = _random.NextDouble() * LEFT;
        y = fromTop ? -100.0 : _random.NextDouble() * TOP;

        _snowflake.SetValue(Canvas.LeftProperty, x);
        _snowflake.SetValue(Canvas.TopProperty, y); 

        insert(_snowflake);

        _surface = _snowflake.Parent as Canvas;

        _snowflakeFrame = new DispatcherTimer();
        
        _snowflakeFrame.Interval = TimeSpan.FromMilliseconds(_random.NextDouble()*25 + 25.0);
        _snowflakeFrame.Tick += (o, e) => _Frame();
        _snowflakeFrame.Start(); 
    }

    private void _Frame()
    {
        y = y + velocity + 3.0 * _random.NextDouble() - 1.0;

        if (y > GONE)
        {
            _snowflakeFrame.Stop();
            _snowflakeFrame = null;

            _surface.Children.Remove(_snowflake);                

            EventHandler handler = SnowflakeDied;
            if (handler != null)
            {
                handler(this, EventArgs.Empty); 
            }
        }
        else
        {
            double xFactor = 10.0 * _affinity;
            if (_affinity < 0.45) xFactor *= -1.0;
            x = x + _random.NextDouble() * xFactor;
            
            if (x < 0)
            {
                x = 0;
                _affinity = 1.0 - _affinity;
            }

            if (x > LEFT)
            {
                x = LEFT;
                _affinity = 1.0 - _affinity;
            }

            _snowflake.SetValue(Canvas.LeftProperty, x);
            _snowflake.SetValue(Canvas.TopProperty, y);
        }

        RotateTransform rotate = (RotateTransform)_snowflake.GetValue(Path.RenderTransformProperty);
        rotate.Angle += _random.NextDouble() * 4.0 * _affinity;

        PlaneProjection plane = (PlaneProjection)_snowflake.GetValue(Path.ProjectionProperty);
        double rotateFactor = 6.0 * _affinity;
        plane.RotationX += _random.NextDouble() * rotateFactor;
        plane.RotationY += _random.NextDouble() * rotateFactor;
        plane.RotationZ += _random.NextDouble() * rotateFactor;
    }

    public event EventHandler SnowflakeDied;

    #region Overrides 

    public override int GetHashCode()
    {
        return Identifier.GetHashCode();
    }

    public override bool Equals(object obj)
    {
        return obj is SnowFlakeEntity && ((SnowFlakeEntity)obj).Identifier.Equals(Identifier); 
    }

    #endregion 
}

Since every snowflake is unique, I give it a unique identifier that I use in the hash code and comparison methods. This makes it easy to remove from a list because it has a unique tag to identify itself. Most of the internal parameters are straightforward: the class itself has a singleton random number generator, we track a velocity (so they fall at different rates) and some coordinates.

When the snowflake is constructed, it can either appear on a random portion of the screen (when the application is first fired up) or get created offscreen at the top so it can drift in (this is when a replacement snowflake is generated for one that fell offscreen). The snowflake sets up a dispatcher timer with frames to update itself. This is a little expensive (with 75 snowflakes, that's 75 timers to keep track of) ... I could probably hook into the composition render event and iterate the list instead for more efficiency. Something to look into!

The _affinity variable gives the snowflake its own unique twist. It controls the direction of drift (left or right, you can see I set it up so slightly more will start out drifting right) and also factors into the rate of spinning and twisting. You can see in each frame that the snowflake updates itself using this, and if it goes off an edge, it flips the affinity to start drifting the opposite direction. This has interesting side effects due to the multipliers in rotation: you'll notice, for example, that a slow snowflake that drifts off the left edge will suddenly move very quickly to the right.

The snowflake delegates getting inserted onto the Canvas to whatever is hosting it, but once it is on the surface, it knows it has a parent and exposes that property. When the snowflake goes off the screen, it shuts down the dispatcher, removes itself from the canvas, then raises an event so the "outside world" knows that its time to create a new snowflake.

Now that we have a snowflake, its time to create the environment for the snowflakes to live in. I decided to implement it as an attachable behavior to a canvas. This snippet defines the behavior as well as a list of snowflakes to manage. Because this is not optimized, I settled on 75 but for your machine you may be able to handle more or less.


public static class SnowFlakeBehavior
{
    const int CAPACITY = 75; 

    private static List<SnowFlakeEntity> _snowflakes = new List<SnowFlakeEntity>(CAPACITY);

    public static DependencyProperty AttachSnowFlakeProperty = DependencyProperty.RegisterAttached(
        "AttachSnowFlake",
        typeof(bool),
        typeof(SnowFlakeBehavior),
        new PropertyMetadata(false, new PropertyChangedCallback(_Attach)));

    public static bool GetAttachSnowFlake(DependencyObject obj)
    {
        return (bool)obj.GetValue(AttachSnowFlakeProperty);
    }

    public static void SetAttachSnowFlake(DependencyObject obj, bool value)
    {
        obj.SetValue(AttachSnowFlakeProperty, value);
    }
}

When we are attached, we check to make sure the flag passed is "true" and then wait for the canvas to get fully loaded:


public static void _Attach(object sender, DependencyPropertyChangedEventArgs args)
{
    Canvas canvas = sender as Canvas; 

    if (canvas != null && args.NewValue != null && args.NewValue.GetType().Equals(typeof(bool)) && (bool)args.NewValue)
    {
        canvas.Loaded += new RoutedEventHandler(Canvas_Loaded);
    }
}

When the canvas is loaded, we can start making snowflakes!


static void Canvas_Loaded(object sender, RoutedEventArgs e)
{
    Canvas canvas = sender as Canvas;
    for (int x = 0; x < _snowflakes.Capacity; x++)
    {
        SnowFlakeEntity snowflake = new SnowFlakeEntity((o) => canvas.Children.Add(o));
        snowflake.SnowflakeDied +=new EventHandler(Snowflake_SnowflakeDied);
        _snowflakes.Add(snowflake);
    }
}

The last piece to wire in is to make a new snowflake when an existing one dies:


static void Snowflake_SnowflakeDied(object sender, EventArgs e)
{
    SnowFlakeEntity snowflake = sender as SnowFlakeEntity;
    
    Canvas canvas = snowflake.Surface; 

    _snowflakes.Remove(snowflake);

    SnowFlakeEntity newFlake = new SnowFlakeEntity((o) => canvas.Children.Add(o), true);
    newFlake.SnowflakeDied += Snowflake_SnowflakeDied;
    _snowflakes.Add(newFlake);
}

If you have a keen eye, you'll probably gripe about the way I cheated a bit using the Surface property. Instead of worrying about state and storing the canvas, I take the old, dead snowflake and simply attach the new one to the same surface. It probably works out fine in the end, but a purist would argue that the snowflake really shouldn't even know or care about its parent. Anyway, we simply register for the new death and send the new snowflake on its way.

Here's a rhetorical question for you: do I need to unregister the event from the old snowflake? We're removing any reference to it by pulling it from the list. Events can be a source of memory leaks when mismanaged. Who "holds" the event reference, my behavior or the SnowFlakeEntity class?

Now we can build a canvas to host the snowflakes. Our main requirement is to attach the snowflake behavior. We also want to clip the canvas so the snowflakes don't go offscreen as they are being added and recycled. The basic layout looks like this:


<Canvas snow:SnowFlakeBehavior.AttachSnowFlake="true"
   x:Name="LayoutRoot"  
   Width="800" 
   Height="600" 
   Margin="5">
   <Canvas.Clip>
      <RectangleGeometry Rect="0,0,800,600"/>
   </Canvas.Clip>
</Canvas>

I embellished with a gradient and a "Merry Christmas" message, all of that is in the source.

There you have it ... a nice little window that displays "drifting" fractal snowflakes. Of course, I wrote it for my daughter, so ... Merry Christmas, Lizzie!

Fractal Koch Snowflakes in Silverlight.

Download the Source

Jeremy Likness

1 comment:

  1. CPU max out is right! Hits 70% on my quad core. Still pretty cool!

    ReplyDelete