# Fun with WPF 3D and Delaunay Triangulation

By , 18 Mar 2011
Votes of 3 or less require a comment

## Introduction

Recently, I have been working with Delaunay triangulation/Voronoi meshes a lot, and one day, I got the idea I could also do something fun with it. So I thought, what if I take a random set of 3D points, triangulate it, and then animate the result. I think that what I got looked pretty cool, so I decided to share it.

• Calling a library to calculate the Delaunay triangulation (well, tetrahedralization, but that word is so much pain to write/read/pronounce) on a random set of 3D points.
• Representing the result as a WPF `Visual3D` object.
• Generating several types of animations - expand, random expand, collapse, and pulse/collapse.

• Using MVVM and other fancy stuff that has the word pattern associated with it.

## Background

Although the topic of 3D Delaunay triangulation is not trivial per se, for the purposes of this article, it is enough to know it is a set of tetrahedrons. Additionally, some basic knowledge of linear algebra and familiarity with WPF is always welcome.

In this article, I use the following code written by other people:

## First, the "hard work"...

Before we can start having fun, we need to do some heavy lifting. In this case, it is generating the data, computing the triangulation, and representing the result.

#### Generating the data

We will use the class `Vertex` to represent our random 3D points. Choosing a wrapper instead of a more straightforward `Point3D` is required because MIConvexHull encourages the input data to implement the `IVertexConvHull` interface, which is a little inconvenient, but we will have to live with that:

```class Vertex : IVertexConvHull
{
public double[] coordinates { get; set; }

// For convenience
public Point3D Position
{
get
{
return new Point3D(coordinates[0], coordinates[1], coordinates[2]);
}
}

// Constructor omitted
}```

Given the number of points to generate and the radius of the points, generating the random data is straightforward (`List` is used because MIConvexHull uses it):

```var rnd = new Random();
Func<double> nextRandom = () => 2 * radius * rnd.NextDouble() - radius;
var vertices = Enumerable.Range(0, count)
.Select(_ => new Vertex(nextRandom(), nextRandom(), nextRandom())
.ToList();```

#### Triangulation

Random data generated - check. MIConvexHull represents the tetrahedrons of the triangulation by a type that implements the `IFaceConvHull` interface:

```class Tetrahedron : IFaceConvHull
{
public IVertexConvHull[] vertices { get; set; }
public double[] normal { get; set; }

// For convenience
Point3D GetPosition(int i) { return ((Vertex)vertices[i]).Position; }
}```

As a side node, the interface is called "`FaceConvHull`" because the triangulation is computed by finding a convex hull of a 4D object (which sounds fancy, but the idea is remarkably simple). Later, we will expand the `Tetrahedron` type with the code to generate its WPF model and animations.

The triangulation itself is done by these two lines of code:

```var convexHull = new ConvexHull(vertices);
var tetrahedrons = convexHull.FindDelaunayTriangulation(
typeof(Tetrahedron)).Cast<Tetrahedron>().ToArray();```

The cast is present because `FindDelaunayTriangulation` returns a list of `IFaceConvHull`.

#### Representing the data

The type `Tetrahedron` contains a function called `CreateModel` which returns a `Model3D` object. The models of all the tetrahedrons are later grouped using `Model3DGroup` and finally wrapped in a `ModelVisual3D` which can be displayed in a `Viewport3D`.

So, the tetrahedron model is an instance of the `GeometryModel3D` (which is derived from `Model3D`) class. To successfully create an instance of `GeometryModel3D`, we need to specify its geometry (triangles representing the object) and the material.

There are two ways to specify the `MeshGeometry3D`:

• Add three points for each triangle. For triangles that share an edge, the points need to be duplicated. In this case, flat shading is used and the object gets a "faceted" look.
• Add `n` points and `3n` indices. Each consecutive triplet of indices then represents a triangle. In this case, smooth shading is used because the system can compute the adjacency of individual triangles and therefore interpolate the normal for each vertex.

Furthermore, the order in which the points in the first case and the indices in the second case are added determines whether the triangle is facing front or back. This determines the lighting and visibility of the triangle. I will not go into more detail about this and point the reader for an example here.

In this article, the second approach is used. The function that takes care of correctly ordering the indices of triangles is called `MakeFace` and I leave it as an exercise for the reader to figure how it works.

The material used has two components: the `DiffuseMaterial` component which is the randomly generated color of each tetrahedron and the `SpecularMaterial` that makes the tetrahedron "shine".

Additionally, a `TranslateTransform3D` is applied to each model which will later be animated.

The whole model is represented by the `RandomTriangulation` class which is derived from WPF's `ModelVisual3D`.

#### The User Interface (or the lack thereof)

The user interface of this application is rather simple. It only contains a `Viewport3D`, a bunch of buttons, a text box, and two labels. There are many articles about WPF layout and the sorts, so I will not focus on it here.

However, there are some points of interest. The first is setting up the camera and lighting and the other is rotating and zooming the scene.

```<ModelVisual3D>
<ModelVisual3D.Content>
<Model3DGroup>
<DirectionalLight x:Name="light" Color="#FF808080" Direction="0 -2 -1" />
<AmbientLight Color="LightYellow" />
</Model3DGroup>
</ModelVisual3D.Content>
</ModelVisual3D>

<Viewport3D.Camera>
<PerspectiveCamera Position="0 0 80" UpDirection="0 1 0"
LookDirection="0 0 -1" FieldOfView="45" />
</Viewport3D.Camera>```

The `DirectionalLight` is named because we will want to apply a transform to it depending on the position of the camera.

For rotation and zooming, the `Trackball` class is used, which is very well described here. The `Viewport3D` is wrapped in a `Grid` to capture the mouse event for the `Trackball`. Also, I have extended the trackball code and made the rotation component of the transform public to be used for rotating the light direction:

```var trackball = new Wpf3DTools.Trackball();
trackball.EventSource = background;
viewport.Camera.Transform = trackball.Transform;
light.Transform = trackball.RotateTransform;```

## ... and then some fun

The fun part is the animation. To animate a property of an object, the `BeginAnimation` method of the type `Animatable` is used (pretty much everything in WPF derives from this type). This method takes two arguments: a `DependencyProperty` to animate and an `AnimationTimeline` object:

• The `DependencyProperty` is, for example, the `OffsetXProperty` of the `TranslateTransform3D` type.
• The `AnimationTimeline` is an object that wraps how the value of the property changes over time. For example:
• ```AnimationTimeline timeline =
new DoubleAnimation { From = 2, To = 10, Duration = TimeSpan.FromSeconds(2) };```

represents the gradual change of the value from 2 to 10 over the course of 2 seconds. In general, WPF animations have several properties that can be changed. For example, not specifying the `From` field means the current value of the animated property is used as the start value when the animation starts. `IsAdditive` is another interesting property, which when set to `true` adds the animated value to the original value of the animated property - at the end of the animation, the value is `original + to`.

By default, the animated value is de facto a linear function of the time parameter (I say de facto because there is some interpolation going on, but I hope you get the idea). This is often pretty boring. One way around this "problem" is using the so called easing functions. By utilizing an easing function, the animated value is now a function of the time parameter. There are several predefined easing functions such as `CircleEase` and `ElasticEase`. These classes implement the `IEasingFunction` interface which contains only one function: `double Ease(double normalizedTime)`. The `normalizedTime` argument is a value from 0 to 1 and is interpolated from the actual duration of the animation.

The following example shows an implementation of the circle ease out function - in this case, the value changes much more rapidly at the start of the animation and then almost ceases to change towards the end. Additionally, the red line shows the "original" linear function.

```class MyCircleEaseOut : IEasingFunction
{
public double Ease(double normalizedTime)
{
double t = 1 - normalizedTime;
return Math.Sqrt(1 - t * t);
}
}```

As a side note, when implementing custom animations, a better idea would be to derive from the `EasingFunctionBase` class which has some basic functionality already built in (such as ease in/out support). Also, there is a nice gallery of easing functions at MSDN. Furthermore, other types of animations exist such as `Point3DAnimation` or `ColorAnimation`, but in the article, we will only use the `DoubleAnimation`.

#### Expand animation

The idea behind the expand animation (and almost all other animations presented here for that matter) is translating the tetrahedron towards the direction defined by the geometrical center of the tetrahedron and the origin (0 vector). The geometrical center is simply the arithmetic average of the tetrahedron vertices' positions, and can be computed for example by some simple LINQ:

```var center = points.Aggregate(new Vector3D(),
(a, c) => a + (Vector3D)c) / (double)points.Count;```

Furthermore, we would like to expand the object ad infinitum. This is where the `IsAdditive` property comes in. Now, each time the user starts the expand animation, the object will expand more and more.

The `TranslateTransform3D`, which will be used as the means for moving the tetrahedron, has three properties: `OffsetX`, `OffsetY`, and `OffsetZ`. Therefore, we will need to animate each property independently. Nevertheless, animation of each translation will be very similar, so we will write a function that creates the animation:

```AnimationTimeline CreateExpandAnimation(double to)
{
return new DoubleAnimation
{
From = 0,
To = to,
Duration = TimeSpan.FromSeconds(1),
EasingFunction = expandEasing,
// = new CircleEasing { EasingMode = EasingMode.EaseOut }
};
}```

Notice the use of `circleOutEasing`. This ensures that the expansion will start fast and then gradually slows down.

Now, nothing stands in our way of creating the animations:

```expandX = CreateExpandAnimation(2 * center.X);
expandY = CreateExpandAnimation(2 * center.Y);
expandZ = CreateExpandAnimation(2 * center.Z);```

It is also convenient to define another helper function to begin the desired animation and specify the handoff behavior, which specifies how the animation should behave if two animations overlap:

```void Animate(AnimationTimeline x, AnimationTimeline y, AnimationTimeline z)
{
translation.BeginAnimation(TranslateTransform3D.OffsetXProperty,
x, HandoffBehavior.SnapshotAndReplace);
translation.BeginAnimation(TranslateTransform3D.OffsetYProperty,
y, HandoffBehavior.SnapshotAndReplace);
translation.BeginAnimation(TranslateTransform3D.OffsetZProperty,
z, HandoffBehavior.SnapshotAndReplace);
}```

Finally, the function `Expand` does the job of moving the tetrahedron:

```void Expand()
{
Animate(expandX, expandY, expandZ);
}```

Alternatively, a `Storyboard` type could be used to apply the animation to the components of the translation, but I will not discuss that here.

To animate all the tetrahedrons, we simply call `Expand` on each of them:

`foreach (var t in tetrahedrons) t.Expand()`

#### Randomized expand

To make the expand animation a little more interesting, here's a randomized version. Each tetrahedron is randomly moved along the X, Y, or Z axis, either in positive or negative direction:

```public void ExpandRandom()
{
switch (rnd.Next(6))
{
case 0: translation.BeginAnimation(TranslateTransform3D.OffsetXProperty,
movePositive, HandoffBehavior.SnapshotAndReplace); break;
case 1: translation.BeginAnimation(TranslateTransform3D.OffsetXProperty,
moveNegative, HandoffBehavior.SnapshotAndReplace); break;
case 2: translation.BeginAnimation(TranslateTransform3D.OffsetYProperty,
movePositive, HandoffBehavior.SnapshotAndReplace); break;
case 3: translation.BeginAnimation(TranslateTransform3D.OffsetYProperty,
moveNegative, HandoffBehavior.SnapshotAndReplace); break;
case 4: translation.BeginAnimation(TranslateTransform3D.OffsetZProperty,
movePositive, HandoffBehavior.SnapshotAndReplace); break;
case 5: translation.BeginAnimation(TranslateTransform3D.OffsetZProperty,
moveNegative, HandoffBehavior.SnapshotAndReplace); break;
default: break;
}
}```

where the move animations are defined as `movePositive = CreateExpandAnimation(radius / 2)` and `moveNegative = CreateExpandAnimation(-radius / 2)` (`radius` is an input parameter for generating the random points).

#### Collapse animation

As opposed to the additive nature of expand, we would like to collapse the object to its original configuration from any state. Furthermore, we want the object to start collapsing slowly and then gradually speed up the process. This is achieved by not specifying the `From` value and using the `CircleEasing` with `EaseIn`:

```var collapse = new DoubleAnimation
{
To = 0,
Duration = TimeSpan.FromSeconds(1),
EasingFunction = collapseEasing
// = new CircleEasing { EasingMode = EasingMode.EaseIn }
};

void Collapse()
{
Animate(collapse, collapse, collapse);
}```

#### Pulse and collapse animation

Save the best for last. The idea here is to have the object pulse for a while and then suddenly collapse. Now, the pulse part can be done using the `ElasticEase` shown below on the left. The collapse part is the circle ease in function. The goal is to combine these two together, as shown bellow on the right.

To achieve this, we could define a custom easing function. However, WPF gives us another option - the keyframe animation:

```AnimationTimeline CreatePulseAnimation(double to)
{
DoubleAnimationUsingKeyFrames pulseAndCollapse = new DoubleAnimationUsingKeyFrames
{
Duration = new Duration(TimeSpan.FromSeconds(3.5)),
KeyFrames = new DoubleKeyFrameCollection
{
new EasingDoubleKeyFrame(to, KeyTime.FromTimeSpan(TimeSpan.FromSeconds(3)),
pulseEasing),
new EasingDoubleKeyFrame(0, KeyTime.FromTimeSpan(TimeSpan.FromSeconds(3.5)),
collapseEasing)
}
};
return pulseAndCollapse;
}```

where `pulseEasing = new ElasticEase { Springiness = 1, EasingMode = EasingMode.EaseOut, Oscillations = 8 }`.

## Conclusion

Well, that's it. I hope you will have some fun playing with/improving the code. I did not cover some aspects such as freezing the objects, defining the animations in XAML (and say, using storyboards), or calculating the triangulation asynchronously, because I did not consider it important for the purpose of this application/article.

## History

• March 18th 2010 - Initial version.

Student
Czech Republic
I have a master's degree in computer science and currently I am a PhD student. My main research interest is in computational chemistry (sort of), although I am more interested in the computational than the chemical aspects of the field.

 First PrevNext
 Well Done! araon123 12-Oct-11 17:20
 Good Effort! Grats.
 Re: Well Done! David Sehnal 12-Oct-11 23:19
 I have a 2D sample on my blog GL_Terminator 12-Oct-11 3:32
 Re: I have a 2D sample on my blog David Sehnal 12-Oct-11 23:18
 great example for 100 nodes but.... Jaime Olivares 16-Jul-11 18:47
 Re: great example for 100 nodes but.... David Sehnal 16-Jul-11 23:12
 HOW? Pritesh Aryan 29-Apr-11 2:15
 Last Visit: 31-Dec-99 18:00     Last Update: 6-Dec-13 8:05 Refresh 123 Next »