質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.33%

Unity2D:オブジェクトを二つに自由切断する方法

解決済

回答 5

投稿

  • 評価
  • クリップ 0
  • VIEW 204

hobby-polite

score 15

こんにちは。

Unity2dにおいて、一つのオブジェクトAを任意の方向に切断(例:指orカーソルでなぞる等)し、オブジェクトBとオブジェクトCに分割するやり方が見つかりません。
イメージ説明
具体的に説明します。上の図のように、始点から徐々に指やカーソルやプレイヤーを任意の方向へ移動させ始めます。この時点ではオブジェクトAは切断されていません。やがてカーソルが終点にたどり着いたとき、上の図では結果的に点線のような軌跡を描きます。終点にたどり着いた瞬間にオブジェクトAは破壊され、オブジェクトBとオブジェクトCが生成されます。(注:BとCの間の隙間は実際には存在しません。)

ここまでの手順をどのように実行するのか?というのが具体的な質問内容です。
スプライトを直線的に切断する方法はいくつか見つけることができたのですが、それらをこのように曲線的に切断する応用の仕方もうまく思いつきません。

付け加えさせていただくと、切断後にオブジェクトBとオブジェクトCにそれぞれ異なった操作を加えたいため、これら二つのオブジェクトをfindする大まかな手順も教えていただければとても助かります。

よろしくお願いいたします。

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 5

checkベストアンサー

+2

結論から言うと曲線できることは出来ません
曲線を直線の集合体として切ることになると思います

ABCDという矩形をEFを通る直線できったとき、
一例として、ABEFとEFCDという図形に区切られる場合、
曲線っぽい直線の集合体として、ABExxxxFとExxxxFCDという図形にする感じだと思います

あとは、自己交差をした場合(曲線が輪を持っている場合)の挙動が面倒ですね
自己交差は禁止したほうが楽だと思います

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/08/09 17:35

    ご回答ありがとうございます!
    実はUnityの公式コミュニティでも同様の質問をしたのですが、ありがたいことに一名の方からアドバイスをいただきましたのでご興味がございましたらどうぞ。https://answers.unity.com/questions/1654857/how-to-cut-an-object-in-any-direction.html?childToView=1655248#answer-1655248

    Unityでの完全オリジナルのゲーム製作は初めての経験ですので、かなり手探りの状態ではありますが、皆さんのアドバイスからぼんやりと筋書きが固まってきました。なんとか頑張ってみます。
    ありがとうございました!

    キャンセル

+2

1.線を書き始めた時点で線が書かれたSpriteと同じ大きさのテクスチャを生成します。
2.線が引き終わった時点で片側のみを塗りつぶします。
3.この塗りつぶされたテクスチャをマスクテクスチャとして利用し、塗りつぶされた部分だけを描写するシェーダー、塗りつぶされていない部分だけを描写するシェーダーのマテリアルを貼り付けたGameObjectをそれぞれ作成する。

この手順で2つ生成されたGameObjectがそれぞれ切断されたオブジェクトを表現することができ、この方法であれば自己交差等にも対応することができます。

テクスチャに線を書く方法についてはこちらのサイトが参考になると思います。

また、引き終わった時点の判定、塗りつぶし処理などに関しては「塗りつぶし アルゴリズム」などで検索すれば割と一般的な処理であることもありたくさん資料が出てきます。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/08/09 17:35

    ご回答ありがとうございます!
    実はUnityの公式コミュニティでも同様の質問をしたのですが、ありがたいことに一名の方からアドバイスをいただきましたのでご興味がございましたらどうぞ。https://answers.unity.com/questions/1654857/how-to-cut-an-object-in-any-direction.html?childToView=1655248#answer-1655248

    Unityでの完全オリジナルのゲーム製作は初めての経験ですので、かなり手探りの状態ではありますが、皆さんのアドバイスからぼんやりと筋書きが固まってきました。なんとか頑張ってみます。
    ありがとうございました!

    キャンセル

+2

私も先のお二人の方針が妥当かと思います。izmktrさんの案はドローソフトのような、Ram.Type-0さんの案はペイントソフトのようなイメージが連想されますね。

興味深いご質問でしたので、試しにizmktrさん方式で実現の見込みがあるか検討してみました。ご参考になれば幸いです。
下記のようなプランはいかがでしょうか?

  • まず、スプライトのメッシュを構成する三角形を有向グラフのようなものと見なす。普通のメッシュなら内部の辺は行きと帰りがペアになっているはずなので、それらを削除するとメッシュの外周を時計回りに一周する経路が得られる(ちなみに穴の開いたメッシュの場合は穴の縁が反時計回りの経路として得られるはずですが、さしあたりそれは考えないことにしました)。

図1

  • 切断パスとメッシュ外周の交点を調べ、頂点を割り込ませてメッシュ外周をちょん切る。

図2

  • 切断パスに沿って、メッシュ内部に辺を張る。辺は行きと帰りをペアにした二重線にしておく。頂点を時計回りにたどると切断後のメッシュ外周が得られる。それぞれの多角形を三角形の集まりに分割すれば新しいメッシュができあがる。

図3

コードは少々長くなってしまったので省略しますが、下図のような感じになりました。

図4

ご意見のあった通り、切断パスに自己交差があるとややこしくなりそうですね。自己交差部分があるパスは一旦交差点で切って繋ぎ直し、自己交差のないパスに分割して複数回に分けて切断した方が楽かもしれません。

切断後の各パーツをどうやって取得するかについては、まずは切断処理を作ってから検討してもいいんじゃないでしょうか。おそらくさほど難しいことはないだろうと思います。切断時にパーツをリストかなにかに放り込んで管理してもいいでしょうし、規則的な名前を付けておいてFindで探すという手もあるでしょう(たとえば今回の実験では、切断後のパーツには元のオブジェクトの名前の後ろにハイフンと連番を入れた名前を付けてみました)。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/08/09 17:34

    ご回答ありがとうございます!
    実はUnityの公式コミュニティでも同様の質問をしたのですが、ありがたいことに一名の方からアドバイスをいただきましたのでご興味がございましたらどうぞ。https://answers.unity.com/questions/1654857/how-to-cut-an-object-in-any-direction.html?childToView=1655248#answer-1655248

    Unityでの完全オリジナルのゲーム製作は初めての経験ですので、かなり手探りの状態ではありますが、皆さんのアドバイスからぼんやりと筋書きが固まってきました。なんとか頑張ってみます。
    ありがとうございました!

    キャンセル

  • 2019/08/14 01:15

    こんにちは。
    先日は詳細なご回答ありがとうございました。

    日をまたいでの質問で申し訳ないのですが、切断パスとメッシュ外周の交点座標はどのように取得すれば良いのでしょうか。また、どのようにしてその取得した交点座標を適切に頂点リストに割り込ませるのでしょうか。
    初歩的な質問になってしまい申し訳ございません。

    キャンセル

  • 2019/08/14 06:10

    図中のPictureオブジェクトにアタッチしたスクリプトを別回答に追記しました(なんとか2回答分におさまりました...)。実験目的で思いつくままに書いた状態ですので、十分に整理されていなかったり非効率的な面もあるかと思います。動作テストも十分に行ったわけではありませんので、あくまでもご参考として...ということでお願いします。

    切断パスと外周パスの交点は、パスを構成する各線分について直線同士の交差をとることによって求めました。http://marupeke296.com/COL_2D_No10_SegmentAndSegment.html に図入りで理屈が紹介されており、ご参考になりそうです。
    交点を割り込ませる段階(CreateCutOutlinesメソッド)では、まず切断パス・外周パスはVertexオブジェクトを双方向連結リスト状に繋いだ形に直し、追加した新しいVertexオブジェクトに対して前後の頂点を接続し直す方式でやってみました。ご覧の通りごちゃごちゃしたコードですみません...

    キャンセル

  • 2019/08/14 15:00

    あああありがとうございます!!!
    参考になるサイトまで何から何まで本当にありがとうございます!
    プログラミング初心者なのでこのスクリプトはかなりチャレンジングに見えますが、自分なりに理解できるよう頑張ります!

    キャンセル

+1

前半

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

namespace SpriteJigsaw
{
    public class SpriteJigsaw : MonoBehaviour
    {
        private static readonly int MainTexProperty = Shader.PropertyToID("_MainTex");

        [SerializeField] private bool attachRigidbody2D = true;

        private Sprite sourceSprite;
        private Material spriteMaterial;
        private Mesh shapeMesh;
        private Vector2[] shapeOutlinePathPositions;
        private PolygonCollider2D shapeCollider;

        // このオブジェクトをワールド座標系のパスで切断し、新しいオブジェクトを返す
        // 切断に成功した場合、このオブジェクトは破壊される
        public List<SpriteJigsaw> Cut(IList<Vector2> cuttingPathPositions)
        {
            Debug.Log($"Cut {this.name}...");
            Debug.Assert(cuttingPathPositions != null);
            Debug.Assert(this.shapeCollider != null);

            // 始点・終点の点検
            var cuttingPathSigns = GetPathCornerSigns(cuttingPathPositions, this.shapeCollider);
            if (cuttingPathSigns.First())
            {
                Debug.LogError("First point is inside collider!");
                return null;
            }
            if (cuttingPathSigns.Last())
            {
                Debug.LogError("Last point is inside collider!");
                return null;
            }

            // 自己交差の点検
            var cuttingPathCornerCount = cuttingPathPositions.Count;
            var cuttingPath = Enumerable.Range(0, cuttingPathCornerCount).ToList();
            var cuttingPathEdges = CreateEdgeListFromPath(cuttingPath, false);
            if (CheckWhetherPathHasSelfIntersection(cuttingPathEdges, cuttingPathPositions))
            {
                Debug.LogError("Path has self intersections!");
                return null;
            }

            // 切断パスをローカル空間に移す
            var worldToLocal = this.transform.worldToLocalMatrix;
            var cuttingPathLocalPositions = cuttingPathPositions.Select(p => (Vector2)worldToLocal.MultiplyPoint3x4(p)).ToList();

            // 切断後のアウトラインを求める
            var cutOutlines = CreateCutOutlines(
                this.shapeOutlinePathPositions,
                cuttingPathLocalPositions,
                cuttingPathSigns);

            // 新しいオブジェクトを作り...
            var result = cutOutlines.Select(
                (loop, i) =>
                {
                    var newName = $"{this.name}-{i}";
                    var loopArray = loop.ToArray();
                    var indices = new Triangulator(loopArray).Triangulate().Select(j => (ushort)j).ToArray();
                    var newSprite = Instantiate(this.sourceSprite);
                    var spriteSize = newSprite.rect.size;
                    var spritePivot = newSprite.pivot;
                    var spritePixelsPerUnit = new Vector2(newSprite.pixelsPerUnit, newSprite.pixelsPerUnit);
                    var spriteSpaceLoopArray = loopArray.Select(
                        p => Vector2.Min(
                            Vector2.Max((p * spritePixelsPerUnit) + spritePivot, Vector2.zero),
                            spriteSize)).ToArray();
                    newSprite.OverrideGeometry(spriteSpaceLoopArray, indices);
                    var newMesh = new Mesh
                    {
                        name = newName,
                        vertices = newSprite.vertices.Select(v => (Vector3)v).ToArray(),
                        uv = newSprite.uv,
                        triangles = newSprite.triangles.Select(j => (int)j).ToArray()
                    };
                    var newObject = Instantiate(this);
                    newObject.name = newName;
                    newObject.sourceSprite = newSprite;
                    newObject.shapeMesh = newMesh;
                    var newMeshFilter = newObject.GetComponent<MeshFilter>();
                    newMeshFilter.sharedMesh = newMesh;
                    var newRenderer = newObject.GetComponent<MeshRenderer>();
                    var materialProperties = new MaterialPropertyBlock();
                    newRenderer.GetPropertyBlock(materialProperties);
                    materialProperties.SetTexture(MainTexProperty, newSprite.texture);
                    newRenderer.SetPropertyBlock(materialProperties);
                    var newCollider = newObject.GetComponent<PolygonCollider2D>();
                    newCollider.points = loopArray;
                    newObject.shapeCollider = newCollider;
                    newObject.shapeOutlinePathPositions = loopArray;
                    return newObject;
                }).ToList();

            // 自分自身は破壊する
            Destroy(this.gameObject);
            return result;
        }

        // 切断後のアウトラインを表す頂点座標ループ群を作る
        private static List<List<Vector2>> CreateCutOutlines(
            IList<Vector2> shapeOutlinePathPositions,
            IList<Vector2> cuttingPathLocalPositions,
            IList<bool> cuttingPathSigns)
        {
            // アウトラインパス、切断パスをともにVertexチェーンに変換する
            var shapeOutlineFirstVertex = CreateVerticesFromPath(shapeOutlinePathPositions, true);
            var cuttingPathFirstVertex = CreateVerticesFromPath(cuttingPathLocalPositions, false, cuttingPathSigns);

            // 後で頂点を総ざらいするときのため、パス作成に関与している頂点をこれに覚えておく
            var vertexBag = new HashSet<Vertex>();
            {
                var intersectionsForVertex = new Dictionary<Vertex, List<Intersection>>();

                // 切断パスをたどっていき...
                var cuttingVertex = cuttingPathFirstVertex;
                while (cuttingVertex.To != null)
                {
                    vertexBag.Add(cuttingVertex);
                    var intersections = new List<Intersection>();
                    intersectionsForVertex.Add(cuttingVertex, intersections);

                    // アウトラインパスをたどっていき...
                    var outlineVertex = shapeOutlineFirstVertex;
                    do
                    {
                        vertexBag.Add(outlineVertex);
                        if (Intersection.CreateIntersection(cuttingVertex, outlineVertex, out var intersection))
                        {
                            // 交点が見つかれば、生成された交点情報を覚えておく
                            // このとき同時にアウトラインパスに切れ目が挿入されている
                            intersections.Add(intersection);
                            vertexBag.Add(intersection.OutlineIn);
                            vertexBag.Add(intersection.OutlineOut);
                            outlineVertex = intersection.OutlineOut;
                        }

                        outlineVertex = outlineVertex.To;
                    } while (outlineVertex != shapeOutlineFirstVertex);

                    cuttingVertex = cuttingVertex.To;
                }

                // アウトラインパスに一通り切れ目を入れた後で、もう一度切断パスをたどっていき...
                cuttingVertex = cuttingPathFirstVertex;
                while (cuttingVertex.To != null)
                {
                    var segmentTerminalVertex = cuttingVertex.To;
                    var intersections = intersectionsForVertex[cuttingVertex];
                    var intersectionCount = intersections.Count;
                    var currentVertexSign = cuttingVertex.Sign == Vertex.VertexSign.Inside;
                    var nextVertexSign = cuttingVertex.To.Sign == Vertex.VertexSign.Inside;

                    // この頂点と同じ位置に頂点を追加してペアを作り...
                    var otherCuttingVertex = new Vertex(cuttingVertex.Position);
                    vertexBag.Add(otherCuttingVertex);
                    cuttingVertex.Other = otherCuttingVertex;
                    otherCuttingVertex.Other = cuttingVertex;

                    // 頂点が形状の内側かを調べ...
                    if (currentVertexSign)
                    {
                        // 内側なら、起点が形状内であることを許さないルールにより
                        // 必ず一つ前の頂点が存在するはず
                        Debug.Assert(cuttingVertex.From != null);

                        // 内側なら自身の双子頂点と一つ前の双子頂点の間に逆向きの接続を作る
                        cuttingVertex.From.Other.From = otherCuttingVertex;
                        otherCuttingVertex.To = cuttingVertex.From.Other;
                    }
                    else
                    {
                        // 外側なら、ここまでの処理の過程でこの頂点よりも前の頂点との接続は切ってあるはず
                        Debug.Assert(cuttingVertex.From == null);

                        // 次の頂点への接続は不要なので切断、この頂点ペアは廃棄する
                        cuttingVertex.To.From = null;
                        cuttingVertex.To = null;
                        vertexBag.Remove(cuttingVertex);
                        vertexBag.Remove(otherCuttingVertex);
                    }

                    if (intersectionCount <= 0)
                    {
                        // この頂点から次の頂点まで交点がないなら、両頂点の内外符号は同じはず
                        Debug.Assert(currentVertexSign == nextVertexSign);
                    }
                    else
                    {
                        // この頂点から次の頂点までの交点が偶数なら両頂点の内外符号は同じ、奇数なら異なるはず
                        Debug.Assert((intersectionCount % 2) == 0 == currentVertexSign == nextVertexSign);

                        // 起点に近い順に交点情報を並べて...
                        intersections = intersections.OrderBy(i => i.T).ToList();

                        // 頂点をつなぎ変えていく
                        var intersectionPointerVertex = cuttingVertex;
                        var sign = currentVertexSign;
                        for (var i = 0; i < intersectionCount; i++)
                        {
                            var intersection = intersections[i];
                            if (sign)
                            {
                                // 交差部分の双子頂点に対して、出る側と入る側を接続する
                                intersectionPointerVertex.To = intersection.OutlineOut;
                                intersection.OutlineOut.From = intersectionPointerVertex;
                                intersectionPointerVertex.Other.From = intersection.OutlineIn;
                                intersection.OutlineIn.To = intersectionPointerVertex.Other;
                            }

                            // 次の交差点へ
                            intersectionPointerVertex = intersection.OutlineIn;
                            intersectionPointerVertex.Other = intersection.OutlineOut;
                            sign = !sign;
                        }

                        // 最後の交差点とセグメント末端を接続する
                        Debug.Assert(sign == nextVertexSign);
                        if (sign)
                        {
                            intersectionPointerVertex.To = segmentTerminalVertex;
                            segmentTerminalVertex.From = intersectionPointerVertex;
                        }
                        else
                        {
                            segmentTerminalVertex.From = null;
                        }
                    }

                    cuttingVertex = segmentTerminalVertex;
                }
            }

            // 出来上がった頂点群から新しいアウトラインを作る
            var result = new List<List<Vector2>>();
            while (vertexBag.Count > 0)
            {
                // 頂点を一つ取り出し...
                var firstVertex = vertexBag.First();
                vertexBag.Remove(firstVertex);
                if (firstVertex.To == firstVertex)
                {
                    continue;
                }

                var loop = new List<Vector2>();
                var vertex = firstVertex;
                var nextVertex = vertex.To;
                do
                {
                    // 頂点をたどって輪を作る
                    Debug.Assert(vertex.From != null);
                    Debug.Assert(vertex.To != null);
                    loop.Add(vertex.Position);
                    Debug.Assert((vertex == firstVertex) || vertexBag.Contains(vertex));
                    vertexBag.Remove(vertex);
                    vertex = nextVertex;
                    nextVertex = vertex.To;
                } while (vertex != firstVertex);

                result.Add(loop);
            }

            return result;
        }

        private void Start()
        {
            if (this.shapeMesh != null)
            {
                return;
            }

            var spriteRenderer = this.GetComponent<SpriteRenderer>();
            if (spriteRenderer == null)
            {
                return;
            }

            this.sourceSprite = spriteRenderer.sprite;
            if (this.sourceSprite == null)
            {
                return;
            }

            // SpriteRendererをMeshRendererに差し替える
            this.shapeMesh = new Mesh
            {
                name = this.name,
                vertices = this.sourceSprite.vertices.Select(v => (Vector3)v).ToArray(),
                uv = this.sourceSprite.uv,
                triangles = this.sourceSprite.triangles.Select(i => (int)i).ToArray()
            };
            this.spriteMaterial = spriteRenderer.sharedMaterial;
            DestroyImmediate(spriteRenderer);
            var meshFilter = this.gameObject.AddComponent<MeshFilter>();
            meshFilter.mesh = this.shapeMesh;
            var meshRenderer = this.gameObject.AddComponent<MeshRenderer>();
            meshRenderer.sharedMaterial = this.spriteMaterial;

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

+1

後半

            var materialProperties = new MaterialPropertyBlock();
            meshRenderer.GetPropertyBlock(materialProperties);
            materialProperties.SetTexture(MainTexProperty, this.sourceSprite.texture);
            meshRenderer.SetPropertyBlock(materialProperties);

            // メッシュの外周を求め、その形のPolygonCollider2Dを付ける
            this.shapeCollider = this.gameObject.AddComponent<PolygonCollider2D>();
            var meshOutlines = GetOutlines(this.shapeMesh);
            Debug.Assert(meshOutlines.Length == 1);
            var meshOutline = meshOutlines[0];
            var meshVertices = this.shapeMesh.vertices;
            this.shapeOutlinePathPositions = meshOutline.Select(i => (Vector2)meshVertices[i]).ToArray();
            this.shapeCollider.points = this.shapeOutlinePathPositions;

            // 必要に応じてRigidbody2Dも付ける
            if (this.attachRigidbody2D)
            {
                this.gameObject.AddComponent<Rigidbody2D>();
            }
        }

        // パスに自己交差部分があるかを検査し、交差が見つかればtrueを返す
        private static bool CheckWhetherPathHasSelfIntersection(IList<Edge> pathEdges, IList<Vector2> pathPositions)
        {
            Debug.Assert(pathEdges != null);
            return pathEdges.Where((e0, i) => pathEdges.Skip(i + 2).Any(e1 => GetIntersection(e0, e1, pathPositions, out _, out _))).Any();
        }

        // パス座標を基に、連結リスト状につながったVertex群を作る
        // 入力される座標リストは連結順に並んでいることが前提
        private static Vertex CreateVerticesFromPath(
            IList<Vector2> sortedPathPositions,
            bool closed,
            IList<bool> signs = null)
        {
            Debug.Assert(sortedPathPositions != null);
            var firstV = new Vertex(sortedPathPositions.First());
            var vertexList = new List<Vertex>();
            var v = firstV;
            vertexList.Add(v);
            foreach (var p in sortedPathPositions.Skip(1))
            {
                var nextV = new Vertex(p);
                v.To = nextV;
                nextV.From = v;
                v = nextV;
                vertexList.Add(v);
            }

            if (closed)
            {
                firstV.From = v;
                v.To = firstV;
            }

            if (signs != null)
            {
                Debug.Assert(signs.Count == vertexList.Count);
                var count = signs.Count;
                for (var i = 0; i < count; i++)
                {
                    vertexList[i].Sign = signs[i] ? Vertex.VertexSign.Inside : Vertex.VertexSign.Outside;
                }
            }

            return firstV;
        }

        // Edgeを引数とするGetIntersection
        private static bool GetIntersection(Edge e0, Edge e1, IList<Vector2> pathPositions, out float t0, out float t1)
        {
            Debug.Assert(pathPositions != null);
            return GetIntersection(pathPositions[e0.From], pathPositions[e0.To], pathPositions[e1.From], pathPositions[e1.To], out t0, out t1);
        }

        // 二つの線分の交点の、線分上の内分点を得る
        // t0、t1がいずれも0以上1以下ならtrueを返す
        // 線分が平行な場合は交差なしと見なしfalseを返す
        private static bool GetIntersection(
            Vector2 p00,
            Vector2 p01,
            Vector2 p10,
            Vector2 p11,
            out float t0,
            out float t1)
        {
            var vc = p10 - p00;
            var v0 = p01 - p00;
            var v1 = p11 - p10;
            var cc = CrossZ(v0, v1);
            if (Mathf.Approximately(cc, 0.0f))
            {
                t0 = 0.0f;
                t1 = 0.0f;
                return false;
            }

            var c0 = CrossZ(vc, v0);
            var c1 = CrossZ(vc, v1);
            t0 = c1 / cc;
            t1 = c0 / cc;
            return (t0 >= 0.0f) && (t0 <= 1.0f) && (t1 >= 0.0f) && (t1 <= 1.0f);
        }

        // a、bを3次元ベクトルと見なし、外積のZ成分を返す
        private static float CrossZ(Vector2 a, Vector2 b)
        {
            return (a.x * b.y) - (a.y * b.x);
        }

        // パス上の各点が形状の内側にあるかを調べて返す
        private static List<bool> GetPathCornerSigns(IList<Vector2> pathPositions, Collider2D collider)
        {
            Debug.Assert(pathPositions != null);
            Debug.Assert(collider != null);
            return pathPositions.Select(collider.OverlapPoint).ToList();
        }

        // パスのインデックスリストから辺のリストを得る
        private static List<Edge> CreateEdgeListFromPath(IList<int> path, bool closed)
        {
            Debug.Assert(path != null);
            var pointCount = path.Count;
            var points = closed ? path : path.Take(pointCount - 1);
            return points.Select((index, i) => new Edge(index, path[(i + 1) % pointCount])).ToList();
        }

        // メッシュ境界をたどる頂点のインデックスを得る経路の配列を得る
        // 外周は時計回り、内周は反時計回り
        private static int[][] GetOutlines(Mesh mesh)
        {
            Debug.Assert(mesh != null);
            var indices = mesh.triangles;
            var triangleCount = indices.Length / 3;
            var edges = Enumerable.Range(0, triangleCount).SelectMany(
                i =>
                {
                    var o = i * 3;
                    return Enumerable.Range(0, 3).Select(j => new Edge(indices[o + j], indices[o + ((j + 1) % 3)]));
                }).ToList();
            var outlineEdges = edges.Where(e => !edges.Contains(e.Inverse())).ToList();
            var result = new List<int[]>();
            while (outlineEdges.Any())
            {
                var outlineIndices = new List<int>();
                var e0 = outlineEdges.First();
                var firstIndex = e0.From;
                var e1 = outlineEdges.First(e => e.From == e0.To);
                while (true)
                {
                    outlineIndices.Add(e0.From);
                    outlineEdges.Remove(e0);
                    e0 = e1;
                    if (e0.To == firstIndex)
                    {
                        outlineIndices.Add(e0.From);
                        outlineEdges.Remove(e0);
                        break;
                    }

                    e1 = outlineEdges.First(e => e.From == e0.To);
                }

                result.Add(outlineIndices.ToArray());
            }

            return result.ToArray();
        }

        private struct Edge
        {
            public readonly int From;
            public readonly int To;

            public Edge(int from, int to)
            {
                this.From = from;
                this.To = to;
            }

            public Edge Inverse()
            {
                return new Edge(this.To, this.From);
            }
        }

        private class Vertex
        {
            public enum VertexSign
            {
                None,
                Inside,
                Outside
            }

            public readonly Vector2 Position;
            public VertexSign Sign;
            public Vertex From;
            public Vertex To;
            public Vertex Other;

            public Vertex(Vector2 position)
            {
                this.Position = position;
                this.Sign = VertexSign.None;
            }

            /// <inheritdoc />
            public override string ToString()
            {
                return $"{(this.From == null ? "null" : this.From.Position.ToString())}->[{(this.Sign == VertexSign.Inside ? "+" : this.Sign == VertexSign.Outside ? "-" : "0")}]{this.Position.ToString()}->{(this.To == null ? "null" : this.To.Position.ToString())}";
            }
        }

        private struct Intersection
        {
            public readonly Vertex OutlineIn;
            public readonly Vertex OutlineOut;
            public readonly float T;

            private Intersection(Vertex outlineIn, Vertex outlineOut, float t)
            {
                this.OutlineIn = outlineIn;
                this.OutlineOut = outlineOut;
                this.T = t;
            }

            public static bool CreateIntersection(Vertex pathFrom, Vertex outlineFrom, out Intersection intersection)
            {
                var p00 = pathFrom.Position;
                var p01 = pathFrom.To.Position;
                var p10 = outlineFrom.Position;
                var p11 = outlineFrom.To.Position;
                if (GetIntersection(p00, p01, p10, p11, out var t0, out _))
                {
                    var position = Vector2.Lerp(p00, p01, t0);
                    var outlineIn = new Vertex(position);
                    var outlineOut = new Vertex(position);
                    outlineIn.From = outlineFrom;
                    outlineIn.To = outlineOut;
                    outlineOut.From = outlineIn;
                    outlineOut.To = outlineFrom.To;
                    outlineFrom.To.From = outlineOut;
                    outlineFrom.To = outlineIn;
                    intersection = new Intersection(outlineIn, outlineOut, t0);
                    return true;
                }
                intersection = new Intersection();
                return false;
            }
        }
    }

    // runevisionさんによるTriangulator(http://wiki.unity3d.com/index.php/Triangulator)
    public class Triangulator
    {
        private readonly List<Vector2> m_points = new List<Vector2>();

        public Triangulator(Vector2[] points)
        {
            this.m_points = new List<Vector2>(points);
        }

        public int[] Triangulate()
        {
            var indices = new List<int>();
            var n = this.m_points.Count;
            if (n < 3)
            {
                return indices.ToArray();
            }
            var V = new int[n];
            if (this.Area() > 0)
            {
                for (var v = 0; v < n; v++)
                {
                    V[v] = v;
                }
            }
            else
            {
                for (var v = 0; v < n; v++)
                {
                    V[v] = n - 1 - v;
                }
            }
            var nv = n;
            var count = 2 * nv;
            for (var v = nv - 1; nv > 2;)
            {
                if (count-- <= 0)
                {
                    return indices.ToArray();
                }
                var u = v;
                if (nv <= u)
                {
                    u = 0;
                }
                v = u + 1;
                if (nv <= v)
                {
                    v = 0;
                }
                var w = v + 1;
                if (nv <= w)
                {
                    w = 0;
                }
                if (this.Snip(u, v, w, nv, V))
                {
                    int a, b, c, s, t;
                    a = V[u];
                    b = V[v];
                    c = V[w];
                    indices.Add(a);
                    indices.Add(b);
                    indices.Add(c);
                    for (s = v, t = v + 1; t < nv; s++, t++)
                    {
                        V[s] = V[t];
                    }
                    nv--;
                    count = 2 * nv;
                }
            }
            indices.Reverse();
            return indices.ToArray();
        }

        private float Area()
        {
            var n = this.m_points.Count;
            var A = 0.0f;
            for (int p = n - 1, q = 0; q < n; p = q++)
            {
                var pval = this.m_points[p];
                var qval = this.m_points[q];
                A += (pval.x * qval.y) - (qval.x * pval.y);
            }
            return A * 0.5f;
        }

        private bool Snip(int u, int v, int w, int n, int[] V)
        {
            int p;
            var A = this.m_points[V[u]];
            var B = this.m_points[V[v]];
            var C = this.m_points[V[w]];
            if (Mathf.Epsilon > (((B.x - A.x) * (C.y - A.y)) - ((B.y - A.y) * (C.x - A.x))))
            {
                return false;
            }
            for (p = 0; p < n; p++)
            {
                if ((p == u) || (p == v) || (p == w))
                {
                    continue;
                }
                var P = this.m_points[V[p]];
                if (this.InsideTriangle(A, B, C, P))
                {
                    return false;
                }
            }
            return true;
        }

        private bool InsideTriangle(Vector2 A, Vector2 B, Vector2 C, Vector2 P)
        {
            float ax, ay, bx, by, cx, cy, apx, apy, bpx, bpy, cpx, cpy;
            float cCROSSap, bCROSScp, aCROSSbp;
            ax = C.x - B.x;
            ay = C.y - B.y;
            bx = A.x - C.x;
            by = A.y - C.y;
            cx = B.x - A.x;
            cy = B.y - A.y;
            apx = P.x - A.x;
            apy = P.y - A.y;
            bpx = P.x - B.x;
            bpy = P.y - B.y;
            cpx = P.x - C.x;
            cpy = P.y - C.y;
            aCROSSbp = (ax * bpy) - (ay * bpx);
            cCROSSap = (cx * apy) - (cy * apx);
            bCROSScp = (bx * cpy) - (by * cpx);
            return (aCROSSbp >= 0.0f) && (bCROSScp >= 0.0f) && (cCROSSap >= 0.0f);
        }
    }
}

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.33%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

同じタグがついた質問を見る