Monday, November 26, 2012

Koch Snowflakes on Windows 8 with XAML

A few years back I wrote a little program that would generate Koch snowflakes in Silverlight. After brisk walk in the cold weather today, I decided it was time to port it over to Windows 8, more just to see how easy it would be. It turns out it only took about 5 minutes to have the program up and running. I made a few tweaks, and it works. I spent some more time just changing how the snowflakes are updated. It is definitely far from perfect (there is an occasional unhandled exception I haven’t debugged and it pegs the CPU) but it’s still a fun little project to run and see.

The Koch curve is simple. You start with a line segment, break it into thirds, and extend the middle third into a triangle. You then repeat the process with the outer line segments recursively. This image depicts the process:

Working backwards, the implementation for the Windows Store app starts with a helper method that takes a set of points and turns them into a path so we can render the snowflake on the XAML surface:

private static Path CreatePath(IReadOnlyList<Point> points)
{
   
var segments = new PathSegmentCollection
();

   
foreach (var point in
points.Skip(1))
    {
        segments.Add(
           
new LineSegment
                {
                    Point = point
                });
    }

   
var pathGeometry = new PathGeometry
();

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

   
return new Path { Data = pathGeometry };
}

The points turn into segments then are collapsed into a closed path. Next, two points need to be split into thirds with a triangle in the middle. The following method does that. It turns 2 points into 5, so the first and last are returned “as is” while the middle triangle is produced using some trigonometry and randomness:

private static IEnumerable<Point> RefactorPoints(Point a, Point b)
{
   
// first point
    yield return
a;

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

   
// 1/3 of the way from first point to second point
    yield return new
Point(a.X + (dX / 3.0), a.Y + (dY / 3.0));

   
var
factor = Random.NextDouble() - 0.5;

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

   
// apex of the middle triangle
    yield return new
Point(vX, vY);

   
// 1/3 of the way from the second point to the first point
    yield return new
Point(b.X - (dX / 3.0), b.Y - (dY / 3.0));

   
// second point
    yield return b;
}

Now we know how to break down a side. This is done recursively for several levels and the points are aggregated back:

private static IEnumerable<Point> RecurseSide(Point a, Point b, int level)
{
   
// iterations are done, so return this line segment
    if
(level == 0)
    {
       
return new List
<Point> { a, b };
    }

   
// first we need to build a list of points that make the refactoring of the side
    var
newPoints = RefactorPoints(a, b).ToList();

   
// this breaks down the segment into 5 points
    var aggregatePoints = new List
<Point>();

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

   
return aggregatePoints;
}

Now the whole process is kicked off by a triangle – not a perfect triangle and the midpoint is randomized a bit, but enough to get the process started to generate a snowflake. As I noted in my post a few years back, you could probably eliminate the second and third calls for recursion and simply reflect a single side:

public static Path Create()
{
   
// something to start with
    var a = new
Point(0, 0);
   
var b = new
Point((Random.NextDouble() * 70.0) + 15.0, 0);
   
var c = new
Point(0, b.X);

   
// now we refactor as many times as needed
    var
levels = Random.Next(Min, Max);

   
// first set of points (first triangle)
    var 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
    var retVal = CreatePath(points);
}

The original example had colorful snowflakes. This time I’m going for a more black and white effect, so I generate a random gradient based on some shades of gray with a random transparency value.

kochsnowflakes

I then wrap the snowflake entity in a class that knows how to insert itself into a canvas (a delegate is passed in so it doesn’t have to take a hard reference on the canvas):

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

   
this
.affinity = Random.NextDouble();

   
// set velocity, initial x and y
    this
.velocity = (Random.NextDouble() * 10.0) + 1.0;
   
this
.x = Random.NextDouble() * Left;
   
this
.y = fromTop ? -100.0 : Random.NextDouble() * Top;

   
// set it
    this.snowflake.SetValue(Canvas.LeftProperty, this
.x);
   
this.snowflake.SetValue(Canvas.TopProperty, this
.y);

   
// place onto surface
    insert(this
.snowflake);

   
// remember parent
    this.surface = this.snowflake.Parent as Canvas
;

   
this.NextTick = DateTime.Now.Add(Interval);
}

It is set up with an initial position and velocity, as well as an interval to update it. If I wasn’t randomizing the motion, I could get away with a storyboard (and potentially have much better performance and less CPU utilization) but the motions are randomized to appear more “organic” as you can see in the following method. The affinity affects the drift direction and the rate of spinning/twisting. The snowflake falls and drifts, and when it is “out of bounds” is removed from the canvas so a new flake can be born:

public void Frame()
{
   
// fall
    this.y = this.y + this
.velocity + (3.0 * Random.NextDouble()) - 1.0;

   
// is it offscreen?
    if (this
.y > Gone)
    {
       
this.surface.Children.Remove(this
.snowflake);

       
// notify the outside world that things changed
        var handler = this
.SnowflakeDied;
       
if (handler != null
)
        {
            handler(
this, EventArgs
.Empty);
        }
    }
   
else
    {
       
// nudge it
        var factor = 10.0 * this
.affinity;
               
       
if (this
.affinity < 0.45)
        {
            factor *= -1.0;
        }
               
       
this.x = this
.x + (Random.NextDouble() * factor);

       
// left edge
        if (this
.x < 0)
        {
           
this
.x = 0;
           
this.affinity = 1.0 - this
.affinity;
        }

       
// right edge
        if (this
.x > Left)
        {
           
this
.x = Left;
           
this.affinity = 1.0 - this
.affinity;
        }

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

   
// spin
    var rotate = (RotateTransform)this.snowflake.GetValue(UIElement
.RenderTransformProperty);
    rotate.Angle += Random.NextDouble() * 4.0 *
this
.affinity;

   
// rotate
    var plane = (PlaneProjection)this.snowflake.GetValue(UIElement
.ProjectionProperty);
   
var rotateFactor = 6.0 * this
.affinity;
    plane.RotationX += Random.NextDouble() * rotateFactor;
    plane.RotationY += Random.NextDouble() * rotateFactor;
    plane.RotationZ += Random.NextDouble() * rotateFactor;

   
this.NextTick = DateTime.Now.Add(Interval);
}

This is all managed by a behavior that attaches to the canvas. The behavior can update the size when the canvas changes, so the snowflakes fall within the confines of the surface regardless of the orientation or if the app is snapped (when you snap it, you just get a greater density of snowflakes). You can see the adjustment happening when you unsnap as snowflakes fall off the bottom and begin to appear in the additional space provided by the unsnapped view.

The older implementation used a set of dispatcher timers unique to each snowflake to update them. This felt a little unwieldy for a store app so I centralized it to a single task. If the application is suspended the task simply freezes and resumes when restarted, and if the app is terminated, so is the task and the entire thing can simply start over again when the user returns. I don’t like infinite loops so I could probably set a variable that is updated on suspension, but this gets the job done for now:

private static async void ThinkLoop(CoreDispatcher dispatcher)
{
   
while (true
)
    {
       
var
now = DateTime.Now;
       
var
snowFlake = Snowflakes.FirstOrDefault(s => s.NextTick <= now);
       
while (snowFlake != null
)
        {
           
var
flake = snowFlake;
           
await dispatcher.RunAsync(CoreDispatcherPriority
.Normal, flake.Frame);
            now = DateTime.Now;
            snowFlake = Snowflakes.FirstOrDefault(s => s.NextTick <= now);
        }
       
await Task
.Delay(1);
    }

}

Notice the task simply loops and finds the next flake that is eligible to update, then dispatches the update to the UI thread. The await is important to avoid clogging the thread (if I were to simply spam the dispatcher with tons of requests, the dispatcher would hit its quote and the app would get terminated). The delay is also fairly arbitrary but keeps the loop from spinning non-stop and instead adds a little bit of a break.

The behavior attaches to the canvas loaded event (and the resized to notify the snowflakes where they are allowed to drift) and kicks off the task, like this (notice the delegate being passed to attach the snowflake to the canvas):

private static void CanvasLoaded(object sender, RoutedEventArgs e)
{
   
var canvas = sender as Canvas
;

   
if (canvas == null
)
    {
       
return
;
    }

   
SnowFlakeEntity
.Left = canvas.ActualWidth;
   
SnowFlakeEntity
.Top = canvas.ActualHeight + 50.0;
   
SnowFlakeEntity
.Gone = canvas.ActualHeight;

   
for (var
index = 0; index < Snowflakes.Capacity; index++)
    {
       
var snowflake = new SnowFlakeEntity
(o => canvas.Children.Add(o));
        snowflake.SnowflakeDied += SnowflakeSnowflakeDied;
        Snowflakes.Add(snowflake);
    }

   
Task.Run(() => ThinkLoop(canvas.Dispatcher));
}

When a snowflake “dies” it is removed from the collection that the behavior is tracking as well as the canvas surface:

private static void SnowflakeSnowflakeDied(object sender, EventArgs e)
{
   
var snowflake = sender as SnowFlakeEntity
;

   
// get the surface so we can add the next snowflake to the same surface
    if (snowflake == null
)
    {
       
return
;
    }

   
var
canvas = snowflake.Surface;
    Snowflakes.Remove(snowflake);
   
var newFlake = new SnowFlakeEntity(o => canvas.Children.Add(o), true);
    newFlake.SnowflakeDied += SnowflakeSnowflakeDied;
    Snowflakes.Add(newFlake);
}

The XAML uses the behavior to kick everything off. A light gradient helps the flakes show up with more contrast. There is also an event that fires when the size of the canvas changes to update the bounds of the clip. The clip ensures snowflakes don’t appear outside of the row designated for snowflake activity.

<Grid Background="{StaticResource ApplicationPageBackgroundThemeBrush}">
    <Grid.RowDefinitions>
        <RowDefinition Height="Auto"></RowDefinition>
        <RowDefinition Height="*"></RowDefinition>
    </Grid.RowDefinitions>
    <TextBlock Text="Koch Snowflakes" Style="{StaticResource HeaderTextStyle}" Margin="12"></TextBlock>
    <Canvas Grid.Row="1"
 
          
HorizontalAlignment="Stretch" VerticalAlignment="Stretch"
           SizeChanged="FrameworkElement_OnSizeChanged"
           local:SnowFlakeBehavior.AttachSnowFlake="True">
 
       
<Canvas.Background>
            <LinearGradientBrush>
                <GradientStopCollection>
                    <GradientStop Color="Black" Offset="0"></GradientStop>
                    <GradientStop Color="#888888" Offset="1.0"></GradientStop>
                </GradientStopCollection>
            </LinearGradientBrush>
        </Canvas.Background>
        <Canvas.Clip>
            <RectangleGeometry x:Name="CanvasClipper" Rect="0,0,9999,9999"/>
        </Canvas.Clip>
    </Canvas
>
</
Grid
>

That’s it. You can download the full source here. Don’t have Visual Studio or don’t care to compile it? You can side load it with the app package here. I’m sure I could create a much better experience using Direct2D but this was literally an attempt to port an existing app. I was very pleasantly surprised to find so little had to be changed from my Silverlight implementation. Enjoy the snowflakes!