読者です 読者をやめる 読者になる 読者になる

自習室

こもります

Unity で ドロネー Delaunay 分割 (平面編)

はじめに

f:id:AMANE:20140819221233p:plain

とあるネタのために、頂点群をメッシュ化、っぽい表現をしたくなったので調べてみたところ、ドロネー分割というのが良さそうという知見を得ました。

上記資料中にドロネー分割というワードがあったので、そこに焦点を絞って調査しました

やりたいこと

時間と共に位置が変わり新しく生まれたり死んだりする点群を、ドロネー分割してワイヤフレームを引きます。 有機的/生命的 な印象になるのを狙っています。

今回はドロネー三角形分割がちゃんと出来るか検証したいだけなので、シンプルな物にとどめます。できあがりはこんな感じ

達成したいネタが2次元で十分なので、今回は2次元で行います。また、ドロネー分割のアルゴリズムには踏み込みません。利用させていただくのにとどめます。

実装

主な構成要素は以下の様になっています。

  • パーティクルシステムと空メッシュの用意
  • 上記パーティクルの点群を元にドロネー分割でメッシュ化
  • メッシュのワイヤフレームレンダリング
  • カメラを構える

順に見ていきます

パーティクルシステムと空メッシュの用意

分割元の頂点を動的に生成するために、標準のパーティクルシステムをおきます。

また、空のメッシュフィルタとメッシュレンダラを持つオブジェクトを、パーティクルシステムオブジェクトの子として持たせておきます。この空メッシュオブジェクトに、ドロネー分割で得られるメッシュを上書きして描画します。

構成はこんな感じ

f:id:AMANE:20140821092218j:plain

パーティクルの点群を元にドロネー分割でメッシュ化

肝心のドロネー分割の部分は、下記コードを参考にさせていただきました。

上記コードでは、Triangulator.CreateInfluencePolygon() 関数に点群を渡すと、レンダラとメッシュフィルタを持った「できあがった」オブジェクトを返してくれますが、私のプログラムでは、Editorからレンダラを指定したかったので、Triangulator.CreateInfluencePolygon() 関数が Mesh だけを返すよう書き換えています。

// Trinagulator.cs
public Mesh CreateInfluencePolygon(Vector2[] XZofVertices) {
//  GameObject CreateInfluencePolygon(Vector2[] XZofVertices) {
  Vector3[] Vertices = new Vector3[XZofVertices.Length];
  for (int ii1 = 0; ii1 < XZofVertices.Length; ii1++) {
    Vertices[ii1] = new Vector3(XZofVertices[ii1].x, 0, XZofVertices[ii1].y);
  }
//    GameObject OurNewMesh = new GameObject("OurNewMesh1");
  Mesh mesh = new Mesh();
  mesh.vertices = Vertices;
  mesh.uv = XZofVertices;
  mesh.triangles = TriangulatePolygon(XZofVertices);
  mesh.RecalculateNormals();
//    MeshFilter mf = OurNewMesh.AddComponent < MeshFilter > ();
//    OurNewMesh.AddComponent < MeshRenderer > ();

//    mf.mesh = mesh;
//    return OurNewMesh;
  return mesh;
}

下記のスクリプトをパーティクルシステムにアタッチします。
ここでは

  • パーティクルシステムの現在の頂点座標を取得
  • 三角形分割クラスに食わせてメッシュを作って
  • 子の空オブジェクトのメッシュとして利用

という作業を行います。

// Delaunay.cs

using UnityEngine;
using System.Collections;

public class Delaunay : MonoBehaviour {

  MeshFilter meshFilter;  // 子に持たせたオブジェクトのメッシュを指す
  Triangulator tr;        // ドロネー分割を行うクラス(上記)

  void Start () {
    meshFilter = GetComponentInChildren<MeshFilter>() as MeshFilter;
    tr = new Triangulator();
  }

  void Update () {
    ParticleSystem.Particle[] particles = new ParticleSystem.Particle[particleSystem.particleCount];
    particleSystem.GetParticles(particles);  // 最新のパーティクル座標を取得
    Vector2[] particlePoss = new Vector2[particles.Length]; // 三角形分割クラスに渡す平面点群情報
    for( int i = 0; i < particles.Length; i++) {

      particlePoss[i].x = particles[i].position.x;
      particlePoss[i].y = particles[i].position.z;
    }
    if( particles.Length > 3 ){
      meshFilter.mesh = tr.CreateInfluencePolygon(particlePoss);  // 平面点群を元にメッシュを作成し、レンダリング対象となるよう子のオブジェクトに渡す
    }
  }
}

メッシュのワイヤフレームレンダリング

ワイヤフレームレンダリングについては、本ブログの過去記事で一度扱いましたので、これを元にします。

この記事の MakeLineFromMesh.cs スクリプトは、起動時にメッシュが存在し、そのメッシュの頂点や面の情報が変化しないことを前提に書かれていますが、今回はパーティクルシステムを元にするため刻々と頂点・面の情報が変化します。そのため、Update() ごとに頂点情報を張り直す作業を行います。

詳細は、本記事末リンク先のコードを参考にされてください。

カメラを構える

3次元に広がるパーティクル座標を2次元に並行投影してドロネー分割しているので、並行投影して見ないと、各三角形の頂点とパーティクルの位置が合いません。そのため、今回は平行投影で世界をとらえます。

Main Camera > Camera > Projection を Orthographic に。

f:id:AMANE:20140819221504j:plain

最後に

本記事であつかったコードとサンプルシーンを含むプロジェクトを Github にあげました。

スピード

凸包の算出やドロネー三角形分割には様々なアルゴリズムがあるようで、それぞれスピードや正確性に差があるようなのですが、今回はとくにそのあたり気にしていません。参考にしたアルゴリズムは、 C# 1ファイル取り込むだけで出来て楽だったので採用しました。

自分が想定する頂点数・使い方の範囲内だと、毎フレーム分割を計算し直しても今のところ 70fps をキープできているので十分ですが、頂点数しだいではアルゴリズムのより良い物を検討する必要もあるかもしれません。

3次元

平行投影で見るのは用途が限られるので、3次元のバージョンもトライしてみたいです。