65.9K
CodeProject 正在变化。 阅读更多。
Home

WPF 3D 和 Delaunay 三角剖分的乐趣

David Sehnal
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.96/5 (24投票s)

2011年3月18日

CPOL

9分钟阅读

viewsIcon

91852

downloadIcon

6219

计算、渲染和动画化一组随机 3D 点的 Delaunay 三角剖分。

引言

最近，我一直在大量研究 Delaunay 三角剖分/Voronoi 网格，有一天，我萌生了可以用它来做一些有趣事情的想法。所以我想，如果我取一组随机的 3D 点，对它进行三角剖分，然后对结果进行动画化会怎么样。我认为我得到的结果看起来很酷，所以我决定分享它。

本文涵盖

  • 调用一个库来计算一组随机 3D 点的 Delaunay 三角剖分（嗯，是四面体剖分，但这个词写起来/读起来/发音起来都太痛苦了）。
  • 将结果表示为 WPF Visual3D 对象。
  • 生成几种类型的动画 - 展开、随机展开、收缩和脉冲/收缩。

本文不涵盖

  • 使用 MVVM 以及其他带有“pattern”一词的 fancy 东西。

背景

尽管 3D Delaunay 三角剖分本身并非易事，但对于本文而言，知道它是一组四面体就足够了。此外，一些基本的线性代数知识和熟悉 WPF 总是受欢迎的。

在本文中，我使用了以下其他人编写的代码

首先，“艰难的工作”...

在我们开始玩乐之前，我们需要做一些繁重的工作。在这种情况下，就是生成数据、计算三角剖分并表示结果。

生成数据

我们将使用 Vertex 类来表示我们的随机 3D 点。选择一个包装器而不是更直接的 Point3D 是必需的，因为 MIConvexHull 鼓励输入数据实现 IVertexConvHull 接口，这有点不方便，但我们必须接受。

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
}

考虑到要生成的点的数量和点的半径，生成随机数据很简单（使用 List 是因为 MIConvexHull 使用它）

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();

三角剖分

随机数据已生成 - 勾选。MIConvexHull 通过实现 IFaceConvHull 接口的类型来表示三角剖分的四面体。

class Tetrahedron : IFaceConvHull
{
  public IVertexConvHull[] vertices { get; set; }
  public double[] normal { get; set; }
  
  // For convenience
  Point3D GetPosition(int i) { return ((Vertex)vertices[i]).Position; }
}

顺便说一句，该接口称为“FaceConvHull”，因为三角剖分是通过查找 4D 对象的凸包来计算的（这听起来很花哨，但想法非常简单）。稍后，我们将扩展 Tetrahedron 类型，并附带代码来生成其 WPF 模型和动画。

三角剖分本身是通过这两行代码完成的

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

进行强制转换是因为 FindDelaunayTriangulation 返回一个 IFaceConvHull 列表。

表示数据

Tetrahedron 类型包含一个名为 CreateModel 的函数，该函数返回一个 Model3D 对象。所有四面体的模型稍后会使用 Model3DGroup 进行分组，最后包装在 ModelVisual3D 中，然后可以在 Viewport3D 中显示。

因此，四面体模型是 GeometryModel3D（它派生自 Model3D）类的实例。要成功创建 GeometryModel3D 的实例，我们需要指定其几何图形（表示对象的三角形）和材质。

有两种方法可以指定 MeshGeometry3D

  • 为每个三角形添加三个点。对于共享边的三角形，需要复制点。在这种情况下，使用平面着色，对象会获得“多面体”外观。
  • 添加 n 个点和 3n 个索引。然后，每三个连续的索引代表一个三角形。在这种情况下，使用平滑着色，因为系统可以计算单个三角形的邻接关系，从而插值每个顶点的法线。

此外，在第一种情况下添加点的顺序或在第二种情况下添加索引的顺序决定了三角形是正面还是背面。这决定了三角形的照明和可见性。我将不再详细介绍这一点，而是将读者引导至此处的示例 。

在本文中，使用了第二种方法。负责正确排序三角形索引的函数称为 MakeFace，我将其留作练习，供读者自己研究其工作原理。

使用的材质有两个组成部分：DiffuseMaterial 组件是每个四面体随机生成的颜色，SpecularMaterial 使四面体“闪耀”。

此外，还对每个模型应用了 TranslateTransform3D，稍后将对其进行动画化。

整个模型由 RandomTriangulation 类表示，该类派生自 WPF 的 ModelVisual3D。

用户界面（或缺乏用户界面）

此应用程序的用户界面相当简单。它只包含一个 Viewport3D、一堆按钮、一个文本框和两个标签。有许多关于 WPF 布局等的文章，所以我不会在这里重点介绍。

但是，有一些值得注意的地方。第一是设置摄像机和灯光，第二是旋转和缩放场景。

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

DirectionalLight 被命名是因为我们将需要根据摄像机的位置对其应用变换。

对于旋转和缩放，使用了 Trackball 类，该类在 此处有很好的描述。Viewport3D 被包装在一个 Grid 中，以便捕获 Trackball 的鼠标事件。此外，我还扩展了 trackball 代码，并将变换的旋转分量设为 public，以便用于旋转光照方向。

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

...然后是一些乐趣

有趣的部分是动画。要动画化对象的属性，可以使用 Animatable 类型的 BeginAnimation 方法（几乎 WPF 中的所有内容都派生自此类型）。此方法接受两个参数：要动画化的 DependencyProperty 和一个 AnimationTimeline 对象。

  • 例如，DependencyProperty 是 TranslateTransform3D 类型的 OffsetXProperty。
  • AnimationTimeline 是一个包装属性值如何随时间变化的对象的。例如：
    • AnimationTimeline timeline = 
  new DoubleAnimation { From = 2, To = 10, Duration = TimeSpan.FromSeconds(2) };

    表示值在 2 秒内从 2 逐渐变为 10。通常，WPF 动画有几个可以更改的属性。例如，不指定 From 字段意味着在动画开始时，动画化属性的当前值用作起始值。IsAdditive 是另一个有趣的属性，当设置为 true 时，它会将动画值添加到动画化属性的原始值 - 在动画结束时，该值为 original + to。

默认情况下，动画值实际上是时间参数的线性函数（我说“实际上”是因为存在一些插值，但我希望你能理解）。这通常非常无聊。解决这个“问题”的一种方法是使用所谓的缓动函数。通过利用缓动函数，动画值现在是时间参数的函数。有几种预定义的缓动函数，例如 CircleEase 和 ElasticEase。这些类实现了 IEasingFunction 接口，该接口只包含一个函数：double Ease(double normalizedTime)。normalizedTime 参数是一个从 0 到 1 的值，并从动画的实际持续时间进行插值。

以下示例显示了圆 out 缓动函数的实现 - 在这种情况下，值在动画开始时变化得更快，然后在接近结束时几乎停止变化。此外，红线显示了“原始”线性函数。

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

顺便说一句，在实现自定义动画时，更好的做法是从 EasingFunctionBase 类派生，该类已经内置了一些基本功能（例如缓入/缓出支持）。此外，MSDN 上还有一个很棒的缓动函数库 。此外，还存在其他类型的动画，例如 Point3DAnimation 或 ColorAnimation，但在本文中，我们将只使用 DoubleAnimation。

展开动画

展开动画（以及此处几乎所有其他动画）背后的想法是将四面体沿着由四面体几何中心和原点（0 向量）定义的方向进行平移。几何中心是四面体顶点位置的算术平均值，可以通过一些简单的 LINQ 来计算。

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

此外，我们希望对象无限展开。这就是 IsAdditive 属性的用武之地。现在，每次用户启动展开动画时，对象都会越来越多地展开。

将用作移动四面体的 TranslateTransform3D 有三个属性：OffsetX、OffsetY 和 OffsetZ。因此，我们需要独立动画化每个属性。尽管如此，每个平移的动画将非常相似，所以我们将编写一个创建动画的函数。

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

注意使用了 circleOutEasing。这确保了展开会快速开始，然后逐渐减慢。

现在，没有什么可以阻碍我们创建动画了。

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

定义另一个辅助函数来开始所需的动画并指定交接行为（handoff behavior）也很方便，该行为指定了如果两个动画重叠，动画应该如何表现。

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);
}

最后，Expand 函数完成了移动四面体的任务。

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

或者，可以使用 Storyboard 类型将动画应用于平移的分量，但我在这里不讨论。

要动画化所有四面体，我们只需对每个四面体调用 Expand。

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

随机展开

为了使展开动画更有趣一点，这里有一个随机版本。每个四面体沿 X、Y 或 Z 轴随机移动，方向为正或负。

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;
  }
}

其中移动动画定义为 movePositive = CreateExpandAnimation(radius / 2) 和 moveNegative = CreateExpandAnimation(-radius / 2)（radius 是用于生成随机点的输入参数）。

收缩动画

与展开的加性性质相反，我们希望将对象从任何状态收缩回其原始配置。此外，我们希望对象开始缓慢收缩，然后逐渐加快该过程。这是通过不指定 From 值并使用带有 EaseIn 的 CircleEasing 来实现的。

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

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

脉冲和收缩动画

把最好的留到最后。这里的想法是让对象脉冲一段时间，然后突然收缩。现在，脉冲部分可以使用下面的左侧显示的 ElasticEase 来完成。收缩部分是圆 out 缓动函数。目标是将这两者结合起来，如右侧所示。

为了实现这一点，我们可以定义一个自定义缓动函数。但是，WPF 为我们提供了另一种选择 - 关键帧动画。

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;
}

其中 pulseEasing = new ElasticEase { Springiness = 1, EasingMode = EasingMode.EaseOut, Oscillations = 8 }。

结论

好了，就是这样。希望您能玩得开心，并改进代码。我没有涵盖一些方面，例如冻结对象、在 XAML 中定义动画（例如使用 storyboards）或异步计算三角剖分，因为我认为它们对于此应用程序/文章的目的并不重要。

参考文献

历史

  • 2010 年 3 月 18 日 - 初始版本。
© . All rights reserved.