前回の記事では指定された点が多角形の内部に存在するか否かを、平面を用いて判定を行う方法を紹介しました。

本記事では、Ray Casting Algorithmを用い多角形の内外判定を行う方法を紹介します。

中身は複雑に見えますが参考URLや本文中のWikipediaからもわかるように広く知られたアルゴリズムです。

Unityで標準搭載されているPlaneやRayの仕組みを用いた記事がなかったため勉強として作成してみました。

本記事に関して

多角形の内外判定を行う方法のシリーズの4本目です。

UIや必要な事前準備は同じであるため、最初の記事からご覧いただけると理解しやすいと考えております。

この記事では1回目の記事でも用いたIsPolygonInsideメソッドで多角形の内外判定を行っている箇所のみを紹介します。

シリーズ目次

【Unity】多角形の内外判定を行う方法 #1 (外積を用いる) tech.kentem.jp

【Unity】多角形の内外判定を行う方法 #2 (角度を用いる) tech.kentem.jp

【Unity】多角形の内外判定を行う方法 #3 (平面を用いる) tech.kentem.jp

【Unity】多角形の内外判定を行う方法 #4 (Ray Casting Algorithmを用いる) ←本記事 tech.kentem.jp

Ray Casting Algorithmとは？
Ray Casting Algorithmを用いた判定
参考URL
おわりに

Ray Casting Algorithmとは？

Ray Casting Algorithm は本シリーズを通して説明してきた多角形の内側か外側かを判定する仕組みの一種です。

en.wikipedia.org

判定対象の点から特定の方向にRayを飛ばし、多角形の平面に衝突した回数を数えます。


1回平面に衝突	2回平面に衝突

その回数が偶数回であれば多角形の外部、奇数回であれば多角形の内部に存在しているという判定となります。

詳細はWikipediaの記事をご覧いただけると理解しやすいと考えています。

Ray Casting Algorithmを用いた判定

下記ではこのアルゴリズムの解説を行います。

平面の設定

前記事で紹介した方法と同じ方法で平面を作成します。

光線の設定

判定対象の点から飛ばす光線(Ray)を定義します。

光線の方向は任意の方向で設定できますが下記に示すソースコードでは多角形の頂点リストの1番目を始点とし0番目を終点とする方向とします。

衝突判定

公式の説明によると、Planeは「A plane is an infinitely large, flat surface 」すなわち「無限に広く平らな面」となっています。

docs.unity3d.com

そのため、単に衝突しただけであれば下のように多角形の外側の場所で衝突している可能性も考えられます。

このような可能性を防ぐために、多角形の辺上で衝突した場合だけ衝突回数として加算するようにします。

辺上で衝突したかどうかを判定するため、①、②の判定を行います。

① 平面と光線が衝突した点(交差点)を取得します。

② ①の点が多角形の辺上に存在しているかを計算により求めます。

そのために、(1) 多角形の端点を始点とし交差点を終点とするベクトルの長さが多角形の辺の何倍かを計算し、 (2) 0倍から1倍の間であれば多角形の辺上に存在していると判定します。

該当するソースコードは下記を確認いただけると理解できると考えています。

ソースコード

private bool IsPolygonInside(Vector3 mousePosition)
{
    var count = _polygon.Vertices.Count;

    var hitCount = 0;
    var rayDirection = _polygon.Vertices[0] - _polygon.Vertices[1];
    for (int i = 0; i < count; i++)
    {
        var currentIndex = i;
        var nextIndex = (i + 1) % count;
        var sideVector = _polygon.Vertices[nextIndex] - _polygon.Vertices[currentIndex];
        var verticalVector = Vector3.Cross(_camera.transform.forward, sideVector);

        // 平面を生成
        var plane = new Plane(verticalVector, _polygon.Vertices[currentIndex]);

        // 光線を生成
        var ray = new Ray(mousePosition, rayDirection);

        // 光線と平面に交差していればenterに距離が入る
        if (plane.Raycast(ray, out var enter))
        {
            // 交差点を計算
            var intersection = ray.GetPoint(enter);

            // 多角形の一端を始点とし交差点を終点とするベクトルを定義
            var currentToIntersectionVector = intersection - _polygon.Vertices[currentIndex];

            // (1)currentToIntersectionVectorが多角形の辺の何倍かを計算する。
            var scale = Vector3.Dot(currentToIntersectionVector, sideVector) / Vector3.Dot(sideVector, sideVector);

            // (2)この値が0以上1以下であれば、多角形の辺上に交差点があることになる。
            if (scale >= 0 && scale <= 1)
            {
                hitCount++;
            }
        }
    }
    return hitCount % 2 == 1;
}