e.blog

主にUnity/UE周りのことについてまとめていきます

フリーハンドで描いた図形をポリゴン分割する

C# Unity

概要

フリーハンドで平面に描いた形に図形を形成するのをやりたかったので、頂点群からポリゴンを形成する処理について書きたいと思います。

こんな感じで、適当に打った点からポリゴンを形成します↓

点群からポリゴンを形成する

まず必要になるのが、点群からポリゴンを形成する処理です。

実装についてはこちらの記事（Javaゲーム制作記 任意多角形の三角形分割）を参考にさせていただきました。

ちなみに、記事中に、さらに元となった記事へのリンクが書いてありましたがリンク切れしてました。
おそらく元となった記事はこちらだと思います↓

sonson.jp

任意の点群からポリゴンを形成する

点群からポリゴンを形成するには、当然ですが点群が囲む任意多角形をポリゴンとして三角形に分割していく作業が必要になります。

大まかに流れを書くと以下のようになります。

  1. 点群を得る
  2. 点群の中で、任意の点（※1）から一番遠い点を見つける
  3. (2)で見つかった点とその両隣の点で三角形を作る
  4. このとき、(2)の点と両隣の点から成る線が作る角度が180度を超えていないことを確認する（※2）
  5. (3)で形成した三角形の中に、点郡の他の点が含まれていないことを確認する
  6. (5)で内包している点がなかったら、それを分割された三角形として採用し、(2)で見つかった点を点群リストから除外する
  7. もし(5)の工程で内包する点が見つかった場合は三角形が構成できないので、ひとつ隣の点を採用点に変更し、もう一度(5)の処理を行う。その際、確認した三角形の向きを保持しておく（※3）
  8. (5)の処理を行い、見つかった三角形と、(7)で保持していた三角形の向きをチェックし、異なった方向だった場合はまた隣の点に移動して(5)の処理を繰り返す
  9. 以後、点群が残り3点（三角形が構成できる最後の点群）になるまで繰り返す

※1 ... 任意の点なのでどこでも構いません。原点などが採用しやすいでしょう。
※2 ... もし超えている場合、見つけた点よりも遠い点が存在するため判定がおかしい。
※3 ... 向きをチェックする理由は、多角形の点の構成によっては外側の三角形が見つかる可能性があるため（図解で後述します）

以上の手順を繰り返すことで、点群を複数の三角形に分割し、冒頭の画像のように任意の多角形をポリゴンに分解することができるようになります。

・・・と、文章だとなんのこっちゃ、だと思うのでまずは図解してみます。

f:id:edo_m18:20180324231129p:plain f:id:edo_m18:20180324231123p:plain f:id:edo_m18:20180324231218p:plain f:id:edo_m18:20180324231222p:plain f:id:edo_m18:20180324231321p:plain f:id:edo_m18:20180324231324p:plain f:id:edo_m18:20180324231327p:plain f:id:edo_m18:20180324231330p:plain f:id:edo_m18:20180324231337p:plain f:id:edo_m18:20180324231340p:plain f:id:edo_m18:20180324231346p:plain f:id:edo_m18:20180324231349p:plain
作った三角形の中に別の点が含まれてしまっている f:id:edo_m18:20180324231353p:plain
三角形の向きは採用点から次の点を辺1、前の点を辺2として、その外積を使って求める f:id:edo_m18:20180324231356p:plain f:id:edo_m18:20180324231402p:plain f:id:edo_m18:20180324231405p:plain f:id:edo_m18:20180324231408p:plain

以上のような感じで、順々に三角形に分解していき、最後の3頂点になるまでそれを繰り返す、という方法です。
仕組み自体はとてもシンプルですね。

コードで見てみる

今回実装したコードも合わせて載せておきます。
（図解したことをコードにしているだけなので、詳細は割愛します）

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

/// <summary>
/// Draw mesh by clicked points.
/// </summary>
public class DrawMesh : MonoBehaviour
{
    private List<Vector3> _leftVertices = new List<Vector3>();
    private List<Vector3> _triangles = new List<Vector3>();

    private Vector3 _prevDirection = Vector3.zero;

    private bool _isIncluding = false;
    private int _curIndex;
    private int _nextIndex;
    private int _prevIndex;

    private Vector3 CurrentPoint
    {
        get { return _leftVertices[_curIndex]; }
    }
    private Vector3 PreviousPoiont
    {
        get { return _leftVertices[_prevIndex]; }
    }
    private Vector3 NextPoint
    {
        get { return _leftVertices[_nextIndex]; }
    }

    /// <summary>
    /// Clear vertices and triangles.
    /// </summary>
    private void ClearMesh()
    {
        _leftVertices.Clear();
        _triangles.Clear();
    }

    /// <summary>
    /// Create mesh by vertices.
    /// </summary>
    public GameObject CreateMesh(List<Vector3> vertices)
    {
        ClearMesh();

        _leftVertices.AddRange(vertices);

        while (_leftVertices.Count > 3)
        {
            DetecteTriangle();
        }

        _triangles.AddRange(_leftVertices);

        Debug.Log("Done chekcing.");

        Mesh mesh = new Mesh();
        mesh.vertices = _triangles.ToArray();

        int[] indices = new int[_triangles.Count];
        for (int i = 0; i < indices.Length; i ++)
        {
            indices[i] = i;
        }

        mesh.triangles = indices;
        mesh.RecalculateNormals();

        GameObject go = new GameObject("MeshObject", typeof(MeshFilter), typeof(MeshRenderer));

        MeshFilter filter = go.GetComponent<MeshFilter>();
        filter.mesh = mesh;

        return go;
    }

    /// <summary>
    /// Detect triangle from far point.
    /// </summary>
    private void DetecteTriangle()
    {
        if (!_isIncluding)
        {
            FindFarPoint();
        }

        Vector3 a = CurrentPoint;
        Vector3 b = NextPoint;
        Vector3 c = PreviousPoiont;

        Vector3 edge1 = b - a;
        Vector3 edge2 = c - a;

        float angle = Vector3.Angle(edge1, edge2);
        if (angle >= 180)
        {
            Debug.LogError("Something was wrong.");
            return;
        }

        if (IsIncludePoint())
        {
            Debug.Log("Point is including.");

            // try to find other point.
            _isIncluding = true;

            // Store current triangle direction.
            _prevDirection = GetCurrentDirection();

            MoveToNext();

            return;
        }

        _isIncluding = false;

        _triangles.Add(a);
        _triangles.Add(b);
        _triangles.Add(c);

        _leftVertices.RemoveAt(_curIndex);
    }

    /// <summary>
    /// Check to include point in the triangle.
    /// </summary>
    /// <returns></returns>
    private bool IsIncludePoint()
    {
        for (int i = 0; i < _leftVertices.Count; i++)
        {
            // skip if index in detected three points.
            if (i == _curIndex || i == _nextIndex || i == _prevIndex)
            {
                continue;
            }

            if (CheckInPoint(_leftVertices[i]))
            {
                return true;
            }
        }

        return false;
    }

    /// <summary>
    /// Get current triangle direction.
    /// </summary>
    /// <returns>Triagnel direction normal.</returns>
    private Vector3 GetCurrentDirection()
    {
        Vector3 edge1 = (NextPoint - CurrentPoint);
        Vector3 edge2 = (PreviousPoiont - CurrentPoint);

        return Vector3.Cross(edge1, edge2).normalized;
    }

    /// <summary>
    /// Check including point.
    /// </summary>
    /// <param name="target">Target point.</param>
    /// <returns>return true if point is including.</returns>
    private bool CheckInPoint(Vector3 target)
    {
        // Triangle points.
        Vector3[] tp =
        {
            CurrentPoint,
            NextPoint,
            PreviousPoiont,
        };

        Vector3 prevNormal = default(Vector3);
        for (int i = 0; i < tp.Length; i++)
        {
            Vector3 edge1 = (target - tp[i]);
            Vector3 edge2 = (target - tp[(i + 1) % tp.Length]);

            Vector3 normal = Vector3.Cross(edge1, edge2).normalized;

            if (prevNormal == default(Vector3))
            {
                prevNormal = normal;
                continue;
            }

            // If not same direction, the point out of a triangle.
            if (Vector3.Dot(prevNormal, normal) <= 0.99f)
            {
                return false;
            }
        }

        return true;
    }

    /// <summary>
    /// Poition reference move to next.
    /// </summary>
    private void MoveToNext()
    {
        _curIndex = (_curIndex + 1) % _leftVertices.Count;
        _nextIndex = (_curIndex + 1) % _leftVertices.Count;
        _prevIndex = _curIndex - 1 >= 0 ? _curIndex - 1 : _leftVertices.Count - 1;
    }

    /// <summary>
    /// Find far point from origin.
    /// </summary>
    private void FindFarPoint()
    {
        int farIndex = -1;
        float maxDist = float.MinValue;
        for (int i = 0; i < _leftVertices.Count; i++)
        {
            float dist = Vector3.Distance(Vector3.zero, _leftVertices[i]);
            if (dist > maxDist)
            {
                maxDist = dist;
                farIndex = i;
            }
        }

        _curIndex = farIndex;
        _nextIndex = (_curIndex + 1) % _leftVertices.Count;
        _prevIndex = (_curIndex - 1) >= 0 ? _curIndex - 1 : _leftVertices.Count - 1;
    }
}

[2018.05.02追記]

上記コードではポリゴン用の頂点を複製してポリゴン数（x3）と同じだけの頂点を生成していましたが、インデックスを割り当てるように修正したのでそちらのコードも載せておきます。

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

/// <summary>
/// Draw mesh by clicked points.
/// </summary>
public class DrawMesh : MonoBehaviour
{
    private List<int> _triangles = new List<int>();
    private List<Vector3> _vertices = new List<Vector3>();
    private Dictionary<int, bool> _verticesBuffer = new Dictionary<int, bool>();

    private Vector3 _prevDirection = Vector3.zero;

    private bool _isIncluding = false;
    private int _curIndex;
    private int _nextIndex;
    private int _prevIndex;

    private Vector3 CurrentPoint
    {
        get { return _vertices[_curIndex]; }
    }
    private Vector3 PreviousPoiont
    {
        get { return _vertices[_prevIndex]; }
    }
    private Vector3 NextPoint
    {
        get { return _vertices[_nextIndex]; }
    }

    /// <summary>
    /// Clear buffers.
    /// </summary>
    private void Clear()
    {
        _vertices.Clear();
        _verticesBuffer.Clear();
        _triangles.Clear();
    }

    private void Initialize(List<Vector3> vertices)
    {
        Clear();

        // 設定された頂点を保持しておく
        _vertices.AddRange(vertices);

        // 全頂点のインデックスを保持、使用済みフラグをfalseで初期化
        for (int i = 0; i < vertices.Count; i++)
        {
            _verticesBuffer.Add(i, false);
        }
    }

    /// <summary>
    /// Create mesh by vertices.
    /// </summary>
    public GameObject CreateMesh(List<Vector3> vertices)
    {
        Initialize(vertices);

        while (true)
        {
            KeyValuePair<int, bool>[] left = _verticesBuffer.Where(buf => !buf.Value).ToArray();
            if (left.Length <= 3)
            {
                break;
            }
            DetecteTriangle();
        }

        int[] keys = _verticesBuffer.Keys.ToArray();
        foreach (int key in keys)
        {
            if (!_verticesBuffer[key])
            {
                _verticesBuffer[key] = true;
                _triangles.Add(key);
            }
        }

        Debug.Log("Done chekcing.");

        Mesh mesh = new Mesh();
        mesh.vertices = _vertices.ToArray();

        mesh.triangles = _triangles.ToArray();
        mesh.RecalculateNormals();

        GameObject go = new GameObject("MeshObject", typeof(MeshFilter), typeof(MeshRenderer));

        MeshFilter filter = go.GetComponent<MeshFilter>();
        filter.mesh = mesh;

        return go;
    }

    /// <summary>
    /// Detect triangle from far point.
    /// </summary>
    private void DetecteTriangle()
    {
        if (!_isIncluding)
        {
            FindFarPoint();
        }

        Vector3 a = CurrentPoint;
        Vector3 b = NextPoint;
        Vector3 c = PreviousPoiont;

        Vector3 edge1 = b - a;
        Vector3 edge2 = c - a;

        float angle = Vector3.Angle(edge1, edge2);
        if (angle >= 180)
        {
            Debug.LogError("Something was wrong.");
            return;
        }

        if (IsIncludePoint())
        {
            Debug.Log("Point is including.");

            // try to find other point.
            _isIncluding = true;

            // Store current triangle dicretion.
            _prevDirection = GetCurrentDirection();

            MoveToNext();

            return;
        }

        _isIncluding = false;

        _triangles.Add(_curIndex);
        _triangles.Add(_nextIndex);
        _triangles.Add(_prevIndex);

        bool isDtected = true;
        _verticesBuffer[_curIndex] = isDtected; 
    }

    /// <summary>
    /// Check to include point in the triangle.
    /// </summary>
    /// <returns></returns>
    private bool IsIncludePoint()
    {
        foreach (var key in _verticesBuffer.Keys)
        {
            int index = key;

            if (_verticesBuffer[key])
            {
                continue;
            }

            // skip if index in detected three points.
            if (index == _curIndex || index == _nextIndex || index == _prevIndex)
            {
                continue;
            }

            if (CheckInPoint(_vertices[index]))
            {
                return true;
            }
        }

        return false;
    }

    /// <summary>
    /// Get current triangle direction.
    /// </summary>
    /// <returns>Triagnel direction normal.</returns>
    private Vector3 GetCurrentDirection()
    {
        Vector3 edge1 = (NextPoint - CurrentPoint).normalized;
        Vector3 edge2 = (PreviousPoiont - CurrentPoint).normalized;

        return Vector3.Cross(edge1, edge2);
    }

    /// <summary>
    /// Check including point.
    /// </summary>
    /// <param name="target">Target point.</param>
    /// <returns>return true if point is including.</returns>
    private bool CheckInPoint(Vector3 target)
    {
        // Triangle points.
        Vector3[] tp =
        {
            CurrentPoint,
            NextPoint,
            PreviousPoiont,
        };

        Vector3 prevNormal = default(Vector3);
        for (int i = 0; i < tp.Length; i++)
        {
            Vector3 edge1 = (target - tp[i]);
            Vector3 edge2 = (target - tp[(i + 1) % tp.Length]);

            Vector3 normal = Vector3.Cross(edge1, edge2).normalized;

            if (prevNormal == default(Vector3))
            {
                prevNormal = normal;
                continue;
            }

            // If not same direction, the point out of a triangle.
            if (Vector3.Dot(prevNormal, normal) <= 0.99f)
            {
                return false;
            }
        }

        return true;
    }

    /// <summary>
    /// Poition reference move to next.
    /// </summary>
    private void MoveToNext()
    {
        _curIndex = FindNextIndex(_curIndex);
        _nextIndex = FindNextIndex(_curIndex);
        _prevIndex = FindPrevIndex(_curIndex);
    }

    /// <summary>
    /// 原点から最も遠い点を探す
    /// </summary>
    private void FindFarPoint()
    {
        int farIndex = -1;
        float maxDist = float.MinValue;

        foreach (var key in _verticesBuffer.Keys)
        {
            if (_verticesBuffer[key])
            {
                continue;
            }

            float dist = Vector3.Distance(Vector3.zero, _vertices[key]);
            if (dist > maxDist)
            {
                maxDist = dist;
                farIndex = key;
            }
        }

        _curIndex = farIndex;
        _nextIndex = FindNextIndex(_curIndex);
        _prevIndex = FindPrevIndex(_curIndex);
    }

    /// <summary>
    /// 指定インデックスから調べて次の有効頂点インデックスを探す
    /// </summary>
    private int FindNextIndex(int start)
    {
        int i = start;
        while (true)
        {
            i = (i + 1) % _vertices.Count;
            if (!_verticesBuffer[i])
            {
                return i;
            }
        }
    }

    /// <summary>
    /// 指定インデックスから調べて前の有効頂点インデックスを探す
    /// </summary>
    private int FindPrevIndex(int start)
    {
        int i = start;
        while (true)
        {
            i = (i - 1) >= 0 ? i - 1 : _vertices.Count - 1;
            if (!_verticesBuffer[i])
            {
                return i;
            }
        }
    }
}

クリック位置を点群として採用する

さて、任意の多角形（点群）から三角形（ポリゴン）に分割する処理ができました。
あとはドラッグした位置の点を取り、それを点群としてリスト化することで目的のことが達成できます。

今回はシンプルに以下のように点群を得る処理を書きました。

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

public class PointDrawer : MonoBehaviour
{
    [SerializeField]
    private DrawMesh _drawMesh;

    [SerializeField]
    private Material _dotMat;

    [SerializeField]
    private float _dotSize = 0.05f;

    [SerializeField]
    private Material _material;

    [SerializeField]
    private float _threshold = 0.1f;

    private float _sqrThreshold = 0;

    private List<Vector3> _samplingVertices = new List<Vector3>();

    private List<GameObject> _dotList = new List<GameObject>();
    private List<Vector3> _vertices = new List<Vector3>();
    private List<GameObject> _meshList = new List<GameObject>();

    /// <summary>
    /// Get average point.
    /// </summary>
    private Vector3 AveragePoint
    {
        get
        {
            Vector3 avg = Vector3.zero;
            for (int i = 0; i < _samplingVertices.Count; i++)
            {
                avg += _samplingVertices[i];
            }
            avg /= _samplingVertices.Count;

            return avg;
        }
    }

    private void Awake()
    {
        _sqrThreshold = _threshold * _threshold;
    }

    private void Update()
    {
        if (Input.GetMouseButton(0))
        {
            TryRaycast();
        }

        if (Input.GetMouseButtonUp(0))
        {
            GameObject go = _drawMesh.CreateMesh(_vertices);
            go.GetComponent<MeshRenderer>().material = _material;
            go.transform.position += go.transform.forward * -0.001f;
            _meshList.Add(go);
        }

        if (Input.GetKeyDown(KeyCode.Q))
        {
            Clear();
        }
    }

    /// <summary>
    /// Try raycast to the plane.
    /// </summary>
    private void TryRaycast()
    {
        Ray ray = Camera.main.ScreenPointToRay(Input.mousePosition);
        RaycastHit hit;
        if (Physics.Raycast(ray, out hit, float.MaxValue))
        {
            if (_vertices.Count == 0)
            {
                AddVertex(hit.point);
                return;
            }

            if (_samplingVertices.Count == 0)
            {
                _samplingVertices.Add(hit.point);
                return;
            }

            float dist = (AveragePoint - hit.point).sqrMagnitude;
            if (dist >= _sqrThreshold)
            {
                AddVertex(hit.point);
            }
            else
            {
                _samplingVertices.Add(hit.point);
            }
        }
    }

    private void AddVertex(Vector3 point)
    {
        CreateDot(point);
        _vertices.Add(point);
        _samplingVertices.Clear();
    }

    /// <summary>
    /// Create dot for clicked poisition.
    /// </summary>
    /// <returns>Dot GameObject.</returns>
    private GameObject CreateDot(Vector3 position)
    {
        Debug.Log("Create dot.");

        GameObject dot = GameObject.CreatePrimitive(PrimitiveType.Sphere);
        dot.transform.localScale = Vector3.one * _dotSize;
        dot.transform.position = position;
        dot.GetComponent<MeshRenderer>().material = _dotMat;
        Destroy(dot.GetComponent<Collider>());

        _dotList.Add(dot);

        return dot;
    }

    public void Clear()
    {
        for (int i = 0; i < _dotList.Count; i++)
        {
            Destroy(_dotList[i]);
        }
        _dotList.Clear();

        for (int i = 0; i < _meshList.Count; i++)
        {
            Destroy(_meshList[i]);
        }
        _meshList.Clear();
    }
}

実装は大したことしてないですが、ドラッグ中（マウスダウン中）にRaycastを行って点の位置を特定、さらにそれを即座に採用せず、閾値以上動いたらそれを点として採用する、という感じです。

閾値以上移動したかどうかは、現在のマウス位置を毎フレーム取り、それの平均位置から現在のマウス位置との距離で判定しています。

このあたりは、要は点群が得られればいいだけなので如何用にでも実装できるかと思います。

まとめ

点群が用意できれば、それをポリゴンに分解できるので、あとはそれに対してやりたいことを実装すれば完了です。
今回はマスクとして使いたかったので、作ったメッシュにマスク用シェーダ（マテリアル）を割り当てて実際は利用しました。

ちなみに、（たまたまかもしれませんが）多少立体的になってもちゃんとポリゴンが形成されたのでもしかしたら3Dでも応用できるかもしれません。