Mycetozoa 開発記録 #5

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

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

辺上に点を挿入する

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

/// <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. 挿入した点が三角形内部にあるか判定

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

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

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