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

自習室

こもります

Unity で ドロネー Delaunay 分割 (3D編)

はじめに

f:id:AMANE:20140821093547p:plain

以前の記事で平面のドロネー分割をやりましたが、今回は3次元でやってみます。

Unity で ドロネー Delaunay 分割 (平面編) - 自習室

実用上困らなければアルゴリズムは問わない、姿勢で今回も使いやすそうな手法を探してみました。

参考と言うかぱくらせていただいた元ネタ

前記事の冒頭で取り上げさせていただいた、ドロネー分割の素敵な解説記事を書かれた たーせるさん(id:tercel_s)が、Processing で3Dのドロネー分割を行ったプログラムをまるっと公開してくださっていました。コードを読んでみたところ Unity-C# への書き換えが出来そうでしたので、こちらをもとにトライしてみました。

Kyle McDonald さんにコメントもらっててすごいです。

実装

主な構成要素は以下の様になっています。今回も、パーティクルシステムを使ってドロネー分割対象の点群を動的に生成・移動させています。

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

パーティクルシステム + 空メッシュを使うことや、ワイヤフレームレンダリングの手法などは、前記事とほぼ同じです。変わったのはドロネー分割のアルゴリズムのみです。

できあがりはこんな感じでございます。

たーせるさんドロネー分割の C#への書き換え

ドロネー分割のアルゴリズムは、上記たーせるさんのProcessingコードをそのまま Unityで使える C# のコードに書き換えた物です。具体的には、下記の項目らを書き換えています

  • PVector → Vector3
  • ArrayList<> → List<>
  • doubleのMath系計算 → UnityにはMathfしかないので、System.Math. 系を利用

というかぶっちゃけそれしかしてません(^_^;) 1時間ほどで出来ました。JavaC#はよく似ていますね。

ソースコードは記事末のリンクからご覧下さい。

パーティクルシステムとの接続とメッシュ化

パーティクルシステムからパーティクルの頂点座標を抜いて、Delaunay クラスに処理してもらって三角形群にします。

たーせるさんのコードでは Delaunay オブジェクトが 頂点・辺・表面の辺・三角形・分割された四面体 をそれぞれ別個に持っていて互いに頂点の順番などを別に管理しているので、私はそのうち三角形の情報を利用しました。

「重複の無い頂点群 + 頂点インデックス配列」 のようなUnityのメッシュ定義では無く、すべての三角形面に対して別個に頂点を定義されています。すべての頂点が重複して存在するのでメモリ上は不利ですが、頂点インデックスを管理しなくて良いので、Unityのメッシュ化は簡単です。

その部分のコードを掲載します。このコードはパーティクルシステムにアタッチして利用します。

// DelaunayMeshUpdater.cs

using UnityEngine;
using System.Collections;
using System.Collections.Generic;

public class DelaunayMeshUpdater : MonoBehaviour {
  
  MeshFilter meshFilter;
  Delaunay d;

  // Use this for initialization
  void Start () {
    meshFilter = GetComponentInChildren<MeshFilter>();
    d = new Delaunay();
  }
  
  // Update is called once per frame
  void Update () {
    ParticleSystem.Particle[] particles = new ParticleSystem.Particle[particleSystem.particleCount];
    particleSystem.GetParticles(particles); // パーティクルシステムからパーティクル情報を引っこ抜く

    List<Vector3> particlePoss = new List<Vector3>();
    for( int i = 0; i < particles.Length; i++) {
      particlePoss.Add (particles[i].position); // パーティクルの座標情報だけ利用する
    }
    if( particles.Length > 5 ){
      d.SetData(particlePoss); // たーせるさんのドロネー分割処理

      Mesh mesh = new Mesh(); // メッシュを用意
      Vector3[] vertices = new Vector3[d.triangles.Count * 3]; // 頂点を用意
      int[] indices = new int[d.triangles.Count * 3];
      for( int i = 0; i < d.triangles.Count; i++) {
        vertices[3 * i + 0] = d.triangles[i].v1; // 頂点座標は順に突っ込んでいくだけ
        vertices[3 * i + 1] = d.triangles[i].v2;
        vertices[3 * i + 2] = d.triangles[i].v3;
        for( int j = 0; j <3; j++) {
          indices[3 * i + j] = 3 * i + j; // 頂点インデックスは、0~頂点数-1 まで順番の数字になる
        }
      }
      mesh.vertices = vertices; // 頂点の更新
      // TODO mesh.uv // uvの定義はスルーしてますので、実行時warningが出ます、スミマセンスミマセン…
      mesh.triangles = indices; // 頂点インデックスの更新
      mesh.RecalculateNormals(); // 面の法線の再計算
      meshFilter.mesh = mesh;  // できあがったメッシュを利用
    }
  }
}

さいごに

今回もシーンごとGithub にあげました。

起動時に固定のメッシュを作るバージョン

f:id:AMANE:20140830101831j:plain

ちなみに、本文で紹介したようなパーティクルをどんどん動かしていくものとは別に、起動時にメッシュを生成して(上の図だと200点)その後はドロネー分割を更新しないサンプルも入っています。以下のあたりのコードを参考になさってください

- Assets/Scene/DelaunayFixPoints.unity //サンプルシーン
- Assets/Prefabs/DelaunayMesh          // パーティクルシステムを使わないでメッシュを生成するプレファブ
- Assets/Scripts/DelaunayMeshMaker     // 上記プレファブで利用しているスクリプト

スピード

毎フレームドロネー分割をし直しているので、結構重いです。パーティクルシステムの設定(寿命や発生速度)を変えて頂点数を増やしていくと、割と直ぐに60fpsを下回ってしまいます。 この辺は用途に応じてという感じですね。

また、起動時に固定のメッシュを作るサンプルの方でも超点数200点とか試してみたのですが、やはり少々時間がかかります。改善の余地はかなりありそうです。

他の手法

stackoverflow でいくつか挙げられています。

その中では下記がとても良くまとまってそうな印象ですが、触れていません。

作例で 26328頂点の凸包を0.023秒で算出、とかやってるのでかなりすごそうです。VisualStudioでビルドしてdll化して~という感じなので、Unityでの利用は敷居が高そうな雰囲気ですが、だれかやってくれないかな…(^_^;)