Mycetozoa 開発記録 #5

C# Unity

ナビゲーションメッシュの生成 その➂

前回はユニークな辺を生成したので、今回は辺上に分割するための点を挿入していきます。

辺上に点を挿入する

挿入する方法は単純に始点から終点に向かい一定間隔で挿入していきます。

/// <summary>
/// ユニークな辺上に点を挿入する
/// Edgeをキー、挿入した点のリストをValueとしたマップを作成する
/// </summary>
private bool CreateBoundaryPointsMap(float interval)
{
    EditorCommonUtility.ProcessDelegate p = (ref int i) =>
    {
        var boundaryPoints = new List<Vertex>();
        var edge = sourceEdgeSet.ElementAt(i++);
        var pos = edge.Start.Position;
        while (true)
        {
            pos = Vector3.MoveTowards(pos, edge.End.Position, interval);
            // Vector3.MoveTowardsでは誤差でdestと一致しないことがあるのでLooseEqualsを使う
            if (pos.LooseEquals(edge.End.Position))
                break;

            var boundaryPoint = new Vertex(pos);
            boundaryPoint.Id = vertexId++;
            boundaryPoints.Add(boundaryPoint);
        }
        // メンバに格納
        generatedBoundaryPoints.Add(edge, boundaryPoints);
    };

    return EditorCommonUtility.ExecuteProcess(p, sourceEdgeSet.Count, "Creating boundary points...", 10);
}

三角形の内部に点を挿入する

  1. 三角形の辺の中から基準となる辺と移動する方向となる辺を決める
  2. 基準辺上に挿入された点を移動する方向へずらしながら点を挿入していく
  3. 挿入した点が三角形内部にあるか判定

イメージにするとこんな感じです。

f:id:skanmera:20170817231953p:plain

/// <summary>
/// 三角形の内部に等間隔で点群を生成する
/// 1) 与えられた三角形から任意の辺を基本辺とする
/// 2) 基本辺上に生成された点群を取得する
/// 3) 基本辺の開始点から基本辺と向かい合う点へのベクトルを生成する方向とする
/// </summary>
private bool CreateInteriorPointMap(float maxInterval)
{
    EditorCommonUtility.ProcessDelegate p = (ref int i) =>
    {
        var triangle = sourceTriangles[i++];

        //　1番辺上の点が多いものを基準辺とする
        var baseEdge = triangle.Edges.FindMin(e => generatedBoundaryPoints[e].Count);
        var boundaryPoints = generatedBoundaryPoints[baseEdge];
        var startType = triangle.GetVertexType(baseEdge.Start);
        var endType = triangle.GetVertexType(baseEdge.End);
        // 角度が90度に近いものを採用する
        var startAngle = triangle.CalculateAngle(startType);
        var endAnge = triangle.CalculateAngle(endType);
        var diffAngleStart = Math.Abs(90.0f - startAngle);
        var diffAngleEnd = Math.Abs(90.0f - endAnge);
        var baseVertex = diffAngleStart < diffAngleEnd ? baseEdge.Start : baseEdge.End;
        var oppositeVertex = triangle.GetOppositeVertexOrElse(baseEdge, null);
        var direction = (oppositeVertex.Position - baseVertex.Position);

        var interiorPoints = GenerateInteriorPoints(triangle, boundaryPoints, direction, maxInterval);

        generatedInteriorPoints.Add(triangle.Id, interiorPoints);
    };

    return EditorCommonUtility.ExecuteProcess(p, sourceTriangles.Count, "Creating interior points ...", 10);
}

/// <summary>
/// 三角形の内部に等間隔で点群を生成する
/// 1) 与えられた境界点群(辺上の点群)をキューに変換
/// 2) キューから逐次点を取り出し生成方向に新しい点を生成する
/// 3) 生成した点が三角形に包含されている場合はキューと内部点群に追加
/// 4) 4,5をキューが空になるまで繰り返す
/// </summary>
/// <param name="triangle">対象となる三角形</param>
/// <param name="boundaryPoints">辺上に生成された点群</param>
/// <param name="direction">点群を生成する方向</param>
/// <returns>三角形の内部に生成された点群</returns>
private List<Vertex> GenerateInteriorPoints(
    Triangle triangle, IEnumerable<Vertex> boundaryPoints, Vector3 direction, float maxInterval)
{
    var interiorPoints = new List<Vertex>();
    var pointQueue = new Queue<Vertex>(boundaryPoints);
    while (pointQueue.Any())
    {
        var currentPoint = pointQueue.Dequeue();
        var pos = Vector3.MoveTowards(currentPoint.Position, currentPoint.Position + direction, maxInterval);
        if (!triangle.IsEncompass(pos))
            continue;

        var interiorPoint = new Vertex(pos);
        interiorPoint.Id = vertexId; vertexId++;
        interiorPoints.Add(interiorPoint);
        pointQueue.Enqueue(interiorPoint);
    }

    return interiorPoints;
}

次は挿入した点をもとの三角形分割を行います。

Mycetozoa 開発記録 #4

C# Unity

ナビゲーションメッシュの生成 その②

前回メッシュからTriangleのリストを生成したので、今回はさらにユニークなEdgeのハッシュセットを生成します。

ユニークな辺のハッシュセットを生成する

NavigationMeshGenerator.cs

/// <summary>
/// 生成したTriangleのリストからユニークなEdgeのハッシュセットを生成する
/// </summary>
/// <returns>キャンセルしたか</returns>
private bool CreateEdgeSet()
{
    EditorCommonUtility.ProcessDelegate p = (ref int i) =>
     {
　　　　 // sourceEdgeSet は　HashSet<Edge>型のメンバ
         foreach (var edge in sourceTriangles[i++].Edges)
             sourceEdgeSet.Add(edge);
     };

    return EditorCommonUtility.ExecuteProcess(p, sourceTriangles.Count, "Creating edge set...", 10);
}

ここで生成したEdgeを格納しているsourceEdgeSetは始点、終点を区別しない比較方法で生成しています。

NavigationMeshGenerator.cs

・・・

/// <summary>
/// 辺の等価性を比較する比較演算子
/// </summary>
private static PositionsEqualityCompare<Edge> edgeLooseCompare = new PositionsEqualityCompare<Edge>(3);

・・・

private HashSet<Edge> sourceEdgeSet;

・・・


/// <summary>
/// コンストラクタ
/// </summary>
public NavigationMeshGenerator()
{

・・・

    sourceEdgeSet = new HashSet<Edge>(edgeLooseCompare);


・・・


}

ここでLooseがついているのはMeshによっては頂点が微妙にずれていることがあるため、ある精度を落として比較しています。

で、PositionsEqualityCompareの実装です。


PositionsEqualityCompare.cs

/// <summary>
/// 点群の位置が等しいかで比較する比較演算子
/// IPositionsEquatable<T>のPositionsEqualsメソッドで比較を行う
/// </summary>
/// <typeparam name="T"></typeparam>
public class PositionsEqualityCompare<T> : IEqualityComparer<T> where T : IPositionsEquatable<T>
{
    /// <summary>
    /// 有効数字
    /// </summary>
    public int SignificantFigures { get; private set; }

    /// <summary>
    /// コンストラクタ
    /// </summary>
    /// <param name="significantFigures"></param>
    public PositionsEqualityCompare(int significantFigures = 0)
    {
        SignificantFigures = significantFigures;
    }

    /// <summary>
    /// 点群の位置が等しいか
    /// </summary>
    /// <param name="x"></param>
    /// <param name="y"></param>
    /// <returns></returns>
    public bool Equals(T x, T y)
    {
        return x.PositionsEquals(y, SignificantFigures);
    }

    /// <summary>
    /// IPositionEquatableのGetPositionsHashCodeメソッドが呼ばれる
    /// </summary>
    /// <param name="obj"></param>
    /// <returns></returns>
    public int GetHashCode(T obj)
    {
        return obj.GetPositionsHashCode(SignificantFigures);
    }
}

ついでにPositionsEqualityCompareの制約となっているIPositionsEquatableの実装です。
これは複数の点群をその性質を問わず座標だけを見て比較する方法を実装します。


IPositionsEquatable.cs

/// <summary>
/// 点群の位置を比較する方法を実装するインターフェース
/// 辺や三角形の方向を考慮せず、全ての座標が一致するかで判定する
/// 有効桁数を指定することが可能
/// </summary>
public interface IPositionsEquatable<in T>
{
    /// <summary>
    /// 点群の位置を比較する
    /// </summary>
    /// <param name="other">比較対象</param>
    /// <param name="significantFigures">有効桁数 デフォルトで0(指定なし)</param>
    /// <returns>等価かどうか</returns>
    bool PositionsEquals(T other, int significantFigures = 0);
    /// <summary>
    /// 点群の位置からハッシュ値を生成する
    /// </summary>
    /// <param name="significantFigures">有効数字</param>
    /// <returns>ハッシュ値</returns>
    int GetPositionsHashCode(int significantFigures = 0);
}


次回は生成したユニークな辺上に分割する点を挿入する処理を書きます。

RubyとRailsのメモ

会員制のサイトを作ってくれと頼まれたので会社の同僚の助けを借りてRailsで作成することになりました。(というかほぼ作ってくれてる)。
で、Rails(Ruby)を勉強することになったのでメモ。

  • rake makeのruby版
  • db:migrate db/migrate に基づいてテーブルを作成、更新する
  • generate いろいろファイルを作成する


maeharin.hatenablog.com

  • module インスタンス化されない、メソッドを持てる
  • mixin Scalaのtraitみたいな感じ、moduleのメソッドをクラスのインスタンスメソッドとして使う、オーバーライドもできる
  • ActiveRecord::Base ActiveRecordはモジュール Baseはクラス
  • メソッド呼び出しは . :: どちらでもできる .で統一したほうがよさげ
  • @hoge @はメンバ変数
  • インスタンス化 Hoge.new()
  • 初期化 initializeでする
  • scaffold アプリケーションの雛形作成、generateの強化版？、使ったほうがいいのかまだ分からない

Mycetozoa 開発記録 #3

C# Unity

ナビゲーションメッシュの生成 その①

先に自前実装のクラスとインターフェースを簡単に説明。

Vertexクラス
  • 座標、IDなどを保持
Edgeクラス
  • 辺を表すクラス
  • 開始頂点と終了頂点をVertex型で保持
  • IVertexCollectionを継承
Triangleクラス
  • 三角形を表すクラス
  • 3つの頂点をVertex型で保持
  • 3辺をEdge型で保持
  • IEdgeCollectionを継承
IVertexCollectionインターフェース
  • Vertexの配列をメンバに持つ
  • 拡張メソッドとしてインターフェースを提供

主要インターフェース

public static bool HasVertex(this IVertexCollection self, Vertex vertex);
public static bool HasVertex(this IVertexCollection self, Vertex vertex, IEqualityComparer<Vertex> comparer)
public static bool HasAnyVertex(this IVertexCollection self, IEnumerable<Vertex> vertices);
public static bool HasAnyVertex(this IVertexCollection self, IEnumerable<Vertex> vertices, IEqualityComparer<Vertex> comparer;
public static bool HasVertices(this IVertexCollection self, IEnumerable<Vertex> vertices);
public static bool HasVertices(this IVertexCollection self, IEnumerable<Vertex> vertices, IEqualityComparer<Vertex> comparer);
public static bool HasCommonVertex(this IVertexCollection self, IVertexCollection other);
public static bool HasCommonVertex(this IVertexCollection self, IVertexCollection other, IEqualityComparer<Vertex> comparer);
public static IEnumerable<Vertex> GetCommonVertices(this IVertexCollection self, IVertexCollection other);
public static IEnumerable<Vertex> GetCommonVertices(this IVertexCollection self, IVertexCollection other, IEqualityComparer<Vertex> comparer);
public static IEnumerable<Vertex> GetOtherVertices(this IVertexCollection self, Vertex vertex);
public static IEnumerable<Vertex> GetOtherVertices(this IVertexCollection self, Vertex vertex, IEqualityComparer<Vertex> comparer);
IEdgeCollectionインターフェース
  • IVertexCollectionを継承
  • Edgeの配列をメンバに持つ
  • 拡張メソッドとしてインターフェースを提供

主要インターフェース

public static bool HasEdge(this IEdgeCollection self, Edge edge);
public static bool HasEdge(this IEdgeCollection self, Edge edge, IEqualityComparer<Edge> comparer);
public static bool HasAnyEdge(this IEdgeCollection self, IEnumerable<Edge> edges);
public static bool HasAnyEdge(this IEdgeCollection self, IEnumerable<Edge> edges, IEqualityComparer<Edge> comparer);
public static bool HasEdges(this IEdgeCollection self, IEnumerable<Edge> edges);
public static bool HasEdges(this IEdgeCollection self, IEnumerable<Edge> edges, IEqualityComparer<Edge> comparer);
public static bool HasCommonEdge<TEdge, TVertex>(this IEdgeCollection self, IEdgeCollection other);
public static bool HasCommonEdge(this IEdgeCollection self, IEdgeCollection other, IEqualityComparer<Edge> comparer);
public static IEnumerable<Edge> GetCommonEdges(this IEdgeCollection self, IEdgeCollection other);
public static IEnumerable<Edge> GetCommonEdges(this IEdgeCollection self, IEdgeCollection other, IEqualityComparer<Edge> comparer);
public static IEnumerable<Edge> GetOtherEdges(this IEdgeCollection self, Edge edge);
public static IEnumerable<Edge> GetOtherEdges(this IEdgeCollection self, Edge edge, IEqualityComparer<Edge> comparer);


各クラス、インターフェースの実装はそのうち載せる予定です。

プログレスバーの表示

ナビゲーションメッシュを生成する各工程は時間がかかるのでプログレスバーを表示します。
使いまわせるようにプログレスバーの更新処理を一か所にまとめました。

EditorCommonUtility.cs (Editor拡張で共通で使用するユーティリティメソッドを集約したクラス)

/// <summary>
/// ループで処理するプロセスのデリゲート
/// </summary>
/// <param name="count">現在のループカウント</param>
public delegate void ProcessDelegate(ref int count);

/// <summary>
/// プログレスバーを更新しながらプロセスを実行する
/// </summary>
/// <param name="process">実行するプロセス</param>
/// <param name="count">カウント</param>
/// <param name="title">プログレスバーに表示するタイトル</param>
/// <param name="interval">プログレスバーを更新する頻度</param>
/// <returns></returns>
public static bool ExecuteProcess(ProcessDelegate process, int count, string title, int interval)
{
    int i = 0;
    while (i < count)
    {
	if (i % interval == 0)
	{
	    float progress = (float)i / count;
	    if (!UpdateProgessBar(progress, title))
		return false;
	}

	process(ref i);
    }

    EditorUtility.ClearProgressBar();

    return true;
}

/// <summary>
/// プログレスバーを更新する
/// </summary>
/// <param name="progress">現在の進展</param>
/// <param name="title">タイトル</param>
/// <returns>キャンセルしたか</returns>
private static bool UpdateProgessBar(float progress, string title)
{
    if (EditorUtility.DisplayCancelableProgressBar(title, string.Format("{0}%", (progress * 100).ToString("F2")), progress))
    {
	EditorUtility.ClearProgressBar();
	return false;
    }

    return true;
}

Triangleリストの生成

まずはUnityのメッシュからTriangleのリストを生成します。
メッシュの情報をそのまま使用しても問題ないのですが、一度三角形の構造にしたほうが分かりやすいのでそうしています。

NavigationMeshGenerator.cs

/// <summary>
/// MeshからTriangleのリストを生成する
/// </summary>
/// <returns>キャンセルしたか</returns>
private bool CreateTriangles(Mesh mesh)
{
    EditorCommonUtility.ProcessDelegate p = (ref int i) =>
     {
	 var posA = mesh.vertices[mesh.triangles[i++]];
	 var posB = mesh.vertices[mesh.triangles[i++]];
	 var posC = mesh.vertices[mesh.triangles[i++]];

	 // 各頂点をVertexに変換する
	 var vertexA = posA.ToVertex(vertexId++);
	 var vertexB = posB.ToVertex(vertexId++);
	 var vertexC = posC.ToVertex(vertexId++);

	 var triangle = new Triangle(vertexA, vertexB, vertexC);
	 triangle.Id = triangleId++;

	 // メンバ変数として定義しているsourceTrianglesに格納する
	 sourceTriangles.Add(triangle);
     };

    return EditorCommonUtility.ExecuteProcess(p, mesh.triangles.Length, "Creating triangles...", 10);
}

これでTriangleのリスト生成は完了です。
次回はここからユニークな辺のリストを生成していきます。

おわりに

現状のナビゲーションメッシュを生成するデモを載せときます。

generate navmesh

Mycetozoa 開発記録 #2

C# Unity

今日は訳あって Windows + Docker + Rails の環境構築をしてたのですが、ハマってしまい書くことがなくなったのでMycetozoaで採用している最短経路を求める手法を大まかに書きます。

 3Dモデルの表面上の最短経路を求める手法  ～概要～

  1. 3Dモデルのメッシュを基にナビゲーション用のメッシュを生成
  2. ポリゴンをノードとしてダイクストラ法を適用
  3. Funnelアルゴリズムを適用してパスを最適化

 

次回からナビゲーションメッシュの生成方法について書きます。

 

 

差分抽出アルゴリズムのC#実装

個人で開発しているプロジェクトでDiffのアルゴリズムが必要だったので実装してみました。

今回実装したのはMyersのアルゴリズムというものです。

こちらのサイトを参考にしました。

www.atmarkit.co.jp

論文はこちら

http://www.xmailserver.org/diff2.pdf

 

C#実装のものはいくつかあったのですが、プロジェクトの都合上カスタマイズがかなり必要そうだったので自前実装しました。

 

まだテスト段階中なので実装の詳細は後ほど書きます。

 

一応ソースです。

github.com

 

Mycetozoa 開発記録 #1

Unity C#

f:id:skanmera:20170806001857p:plain

はじめに

人に見られずとも完璧に物事をこなす人間になりたいと常日頃思っていますが、なかなかそうはいきません。

得に個人で開発しているプロジェクトのソースコードを見返すと痛感します。

 コードを公開することで品質が高まることもあるのではと思い、以前からやらねばと思いつつ手を出さなかった技術ブログを始めることにしました。

とりあえず今回は趣味で開発しているUnityのプラグインを紹介します。

プロジェクト紹介

概要

3Dモデルの表面上の最短経路を計算するプラグインです。

プロジェクト名は最短経路を解決することができる「粘菌」の学術名からとりました。迷路を解く様がA*のシュミレーションのように見えます。


Slime mold solving maze

目的

プレイヤーやエネミーを簡単な設定だけで複雑な形状のモデル上で経路探索させるAIを目指します。

現状

ポリゴン数が数千程度かつ形状がそこまで複雑でないモデルであれば実用できるぐらいにはなってます。

 ・デモ


Unity pathfinding on 3D model surface.

 

また、ナビゲーション用に生成しているメッシュのポリゴンを編集するEditor拡張も実装中です。

こちらは通行可・不可の設定ができるレベルしか実装できていません。

f:id:skanmera:20170806004257p:plain

課題

・数万ポリゴンでも動かせるようにパフォーマンス改善(無理ならLowPoly専用にするつもり)

・複数モデルを組み合わせて使えるようにする

・まだAPIを使用するためにスクリプトをがっつり書く必要がある

 

最後に

今後は実際の実装なども紹介していく予定です。

飽きっぽい性格なのでいつまで続くか分かりませんが、何か成果が得られるまでは続けるつもりですw