Click here to Skip to main content
15,867,686 members
Articles / Desktop Programming / WPF
Article

Fun with WPF 3D and Delaunay Triangulation

Rate me:
Please Sign up or sign in to vote.
4.96/5 (24 votes)
18 Mar 2011CPOL9 min read 87.1K   6.2K   43   31
Computing, rendering, and animating the Delaunay triangulation of a random set of 3D points.

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.

Image 1

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:

C#
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):

C#
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:

C#
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:

C#
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.

XML
<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:

C#
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:
  • C#
    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.

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

Image 2

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:

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

Image 3

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:

C#
AnimationTimeline CreateExpandAnimation(double to)
{
  return new DoubleAnimation 
  { 
    From = 0, 
    To = to, 
    Duration = TimeSpan.FromSeconds(1), 
    EasingFunction = expandEasing, 
      // = new CircleEasing { EasingMode = EasingMode.EaseOut } 
    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:

C#
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:

C#
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:

C#
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:

C#
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:

C#
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:

C#
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.

Image 4

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

C#
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.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Student
Czech Republic 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.

Comments and Discussions

 
QuestionPossible Bug??? Pin
Laurent Chougrani26-Dec-16 21:32
Laurent Chougrani26-Dec-16 21:32 
SuggestionShouldn't it be "tetrahedronization" :-) Pin
SMD1112-Mar-16 9:20
SMD1112-Mar-16 9:20 
QuestionGraident color to whole model Pin
bhupsiii27-Jan-16 1:16
bhupsiii27-Jan-16 1:16 
Questionquick question please Pin
Member 1160912428-Apr-15 23:54
Member 1160912428-Apr-15 23:54 
GeneralWish I had read this before writing my own version :) Pin
HoshiKata15-Nov-12 1:33
HoshiKata15-Nov-12 1:33 
GeneralRe: Wish I had read this before writing my own version :) Pin
David Sehnal15-Nov-12 4:34
David Sehnal15-Nov-12 4:34 
QuestionWell Done! Pin
araon12312-Oct-11 17:20
araon12312-Oct-11 17:20 
AnswerRe: Well Done! Pin
David Sehnal12-Oct-11 23:19
David Sehnal12-Oct-11 23:19 
QuestionI have a 2D sample on my blog Pin
Vasily Tserekh12-Oct-11 3:32
Vasily Tserekh12-Oct-11 3:32 
AnswerRe: I have a 2D sample on my blog Pin
David Sehnal12-Oct-11 23:18
David Sehnal12-Oct-11 23:18 
Questiongreat example for 100 nodes but.... Pin
Jaime Olivares16-Jul-11 18:47
Jaime Olivares16-Jul-11 18:47 
AnswerRe: great example for 100 nodes but.... Pin
David Sehnal16-Jul-11 23:12
David Sehnal16-Jul-11 23:12 
Generalthanks and regards - another useful article [modified] Pin
Member 363069217-Jun-11 2:41
Member 363069217-Jun-11 2:41 
GeneralHOW? Pin
Pritesh Aryan29-Apr-11 2:15
Pritesh Aryan29-Apr-11 2:15 
GeneralAnd one thing also........... [modified] Pin
Pritesh Aryan21-Apr-11 3:07
Pritesh Aryan21-Apr-11 3:07 
GeneralRe: And one thing also........... Pin
David Sehnal21-Apr-11 4:18
David Sehnal21-Apr-11 4:18 
Generalvery very very very.....^ N ^N ....... NICE ARTICAL................. Pin
Pritesh Aryan20-Apr-11 23:52
Pritesh Aryan20-Apr-11 23:52 
GeneralRe: very very very very.....^ N ^N ....... NICE ARTICAL................. Pin
David Sehnal21-Apr-11 0:53
David Sehnal21-Apr-11 0:53 
GeneralRe: very very very very.....^ N ^N ....... NICE ARTICAL................. Pin
Pritesh Aryan21-Apr-11 1:34
Pritesh Aryan21-Apr-11 1:34 
GeneralRe: very very very very.....^ N ^N ....... NICE ARTICAL................. Pin
David Sehnal21-Apr-11 1:42
David Sehnal21-Apr-11 1:42 
GeneralRe: very very very very.....^ N ^N ....... NICE ARTICAL................. Pin
Pritesh Aryan21-Apr-11 3:00
Pritesh Aryan21-Apr-11 3:00 
GeneralRe: very very very very.....^ N ^N ....... NICE ARTICAL................. Pin
David Sehnal21-Apr-11 4:21
David Sehnal21-Apr-11 4:21 
GeneralRe: very very very very.....^ N ^N ....... NICE ARTICAL................. Pin
Pritesh Aryan21-Apr-11 4:23
Pritesh Aryan21-Apr-11 4:23 
GeneralVery Neat Pin
AspDotNetDev6-Apr-11 12:37
protectorAspDotNetDev6-Apr-11 12:37 
GeneralRe: Very Neat Pin
David Sehnal6-Apr-11 13:46
David Sehnal6-Apr-11 13:46 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.