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.
This article covers:
- 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.
This article does not cover:
- 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; }
public Point3D Position
{
get
{
return new Point3D(coordinates[0], coordinates[1], coordinates[2]);
}
}
}
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; }
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,
IsAdditive = true
};
}
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
};
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.
References
History
- March 18th 2010 - Initial version.
