e.blog

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

iOSのARKitを使ってVRのポジトラをやってみた

概要

ずっと気になっていたARKit。やっと触ることができたので、ひとまず、空間認識して色々触ったあと、VRのポジトラに流用するのをやってみたのでまとめておきます。
AR自体がポジトラしてモデルなんかを表示できるので、これをVRモードのカメラの位置に転化してあげる、という流れです。

実際に動かしてみた動画です↓

ひとまず、単純に空間を認識して平面などを配置、カメラを移動する、いわゆる「AR」の実装方法を解説したあと、VRモードへの転用を説明します。
(まぁといっても、ほぼAR空間での処理が実装できれば、あとはカメラの位置同期を別のものに置き換えるだけなので大した問題ではありませんが)

単純にARコンテンツをさっと作るだけなら、そもそもUnityが専用のコンポーネントをすでに用意してくれているので、それを組み合わせるだけですぐにでも空間にモデルなんかを配置することができます。
今回の解説は、VRに転用するにあたって、動作の仕組みなんかを把握したかったので、基本クラスを使いつつ、自前で実装するにはどうするか、という視点でのまとめです。
(とはいえ、ネイティブのARKitとの通信はほとんどUnity側でやってくれてしまうので、あまりむずかしいことはやりませんが)

準備

アセットのインポート

UnityのアセットストアですでにUnity ARKit Pluginが公式に配布されているのでそれをダウンロード、インポートします。

Bitbucketから最新のものが取得できるようなので、新しい機能なりを試したい場合は見てみるといいかも。

インポートが終わったら準備完了です。
ネイティブのARKitとの通信はすべてUnityのコンポーネントが行ってくれるので、それを使って構築していきます。

既存のコンポーネントを利用する

今回は、ネイティブからのデータを使って処理を行うように実装していますが、ARの機能をさっと試したいだけであれば、既存のコンポーネントを組み合わせるだけですぐにARの機能を使うことができるようになっています。

使うコンポーネント

使うコンポーネントUnityEngine.XR.iOS名前空間に定義されています。
余談ですが、Android向けビルドでVR SDKをDaydreamにすると、Unity2017以降だとXRという名前になっていて、ARCoreのチェックボックなんかも出てくるので、今後はVR x ARのポジトラは標準になりそうな予感がしますね。

使うコンポーネントは以下になります。

  • UnityARVideo
  • UnityARCameraNearFar
  • UnityARCameraManager
  • UnityARHitTestExample
  • UnityARSessionNativeInterface

UnityARVideo

iOSバイスのカメラの映像を、CommandBuffer経由で描画するようです。
カメラ自体にAddComponentして使います。
また、インスペクタにはマテリアルを設定するようになっていますが、ARKitアセットに含まれているYUVMaterialを設定してあげればOKです。

なお、カメラの映像を出力しないVRモードであっても、このコンポーネントがないとARカメラの位置トラッキングがおかしくなっていたので、もしかしたらARとしての画像解析がこのクラス経由で行われているのかもしれません。

UnityARCameraNearFar

ARカメラのNearとFarを適切に設定するコンポーネント・・・のようですが、これがないとなにがダメなのかはちょっとまだ分かっていません( ;´Д`)
このコンポーネントも、メインのカメラにAddComponentして使います。

UnityARCameraManager

カメラの動きを制御するコンポーネント。マネージャという名前の通り、これは、カメラにAddComponentするのではなく、空オブジェクトなどに設定して、インスペクタからカメラオブジェクトを登録する形で使います。

内部的な処理としては、後述するUnityARSessionNativeInterfaceクラスから、ARKitの解析データを受け取り、適切にカメラの位置をARで認識した空間に基いて移動する仕組みを提供します。

UnityARHitTestExample

画面をタッチした際に、タッチ先に平面が認識されていたらそこに3Dモデルなどを移動してくれるサンプル用コンポーネント
Hit testのやり方などが記述されているので、タッチに反応するアプリを作る場合などは参考にするとよさそうです。

UnityARSessionNativeInterface

ネイティブのARKitからの情報を受け取る最重要クラス。
基本的に、上記のような機能を自前で実装する場合はこのクラスからの値を適切に使う必要があります。

以上のコンポーネントを連携させるだけで、ARKitの機能を使った簡単なモデル配置などはすぐに行うことができます。

このコンポーネント群については、以下の記事を参考にさせていただきました。

qiita.com

ARKitの機能を使う

さて、上記のコンポーネントを使うことで簡単なモックならすぐ作れてしまうでしょう。
ここからは、それらのコンポーネントが行ってくれている部分を少し紐解きながら、ARを使ったコンテンツを作る上で必要になりそうな部分を個別に解説していきたいと思います。

ARKitで認識した位置をUnityのカメラと同期する

ARコンテンツをAR足らしめているのが、この「カメラの移動」でしょう。
空間を認識し、それに基いてカメラが適切に動いてくれることで、3Dオブジェクトなどが本当にそこにあるかのように見せることができるわけです。

UnityARCameraManagerを参考に、必要な部分だけ抜き出す

さて、先ほども紹介したUnityARCameraManagerには、このカメラの位置を同期する処理が書かれています。
といっても、内部的な処理はほぼUnityARSessionNativeInterfaceがやってくれるので、毎フレーム、現在の姿勢をカメラに適用するだけでOKです。

private void Start()
{
    _session = UnityARSessionNativeInterface.GetARSessionNativeInterface();

    ARKitWorldTrackingSessionConfiguration config = new ARKitWorldTrackingSessionConfiguration();
    config.planeDetection = UnityARPlaneDetection.Horizontal; // 現状は`None`か`Horizontal`しか選べない
    config.alignment = UnityARAlignment.UnityARAlignmentGravity;
    config.getPointCloudData = true;
    config.enableLightEstimation = true;
    _session.RunWithConfig(config);
}

private void Update()
{
    Matrix4x4 matrix = _session.GetCameraPose();
    _arCamera.transform.localPosition = UnityARMatrixOps.GetPosition(matrix);
    _arCamera.transform.localRotation = UnityARMatrixOps.GetRotation(matrix);
    _arCamera.projectionMatrix = _session.GetCameraProjection();
}

大雑把に説明すると、ARKitの動作のConfigを作成し、それを元にセッションを開始、以後はそのセッションから得られるカメラの位置や回転を、そのままカメラのlocalPositionlocalRotationに適用してやるだけです。
こうすることで、ARのカメラとして適切に移動、回転が行われます。

UnityARAnchorManagerを元に、平面の位置のトラッキングを行う部分を抜き出す

オブジェクトを配置して、カメラの移動が行われれば、基本的にはARらしい見た目を表現することは可能です。
次は、ARKitのシステムが認識した平面の情報を使って、実際に空間に平面情報を表示する方法を見てみます。

private Dictionary<string, ARPlaneAnchorGameObject> planeAnchorMap;


private void Start()
{
    planeAnchorMap = new Dictionary<string,ARPlaneAnchorGameObject> ();

    UnityARSessionNativeInterface.ARAnchorAddedEvent += AddAnchor;
    UnityARSessionNativeInterface.ARAnchorUpdatedEvent += UpdateAnchor;
    UnityARSessionNativeInterface.ARAnchorRemovedEvent += RemoveAnchor;
}

上記の3つのイベントが、ARKitのシステムから発行されます。
それぞれ、アンカー(平面)が認識された、更新された、破棄されたタイミングで呼ばれます。

そのイベント内でどんな処理が書かれているのか見てみましょう。

ARAnchorAddedEvent

まずは、平面が認識された際のハンドラ内での処理です。

public void AddAnchor(ARPlaneAnchor arPlaneAnchor)
{
    GameObject go = UnityARUtility.CreatePlaneInScene (arPlaneAnchor);
    go.AddComponent<DontDestroyOnLoad> ();  //this is so these GOs persist across scene loads
    ARPlaneAnchorGameObject arpag = new ARPlaneAnchorGameObject ();
    arpag.planeAnchor = arPlaneAnchor;
    arpag.gameObject = go;
    planeAnchorMap.Add (arPlaneAnchor.identifier, arpag);
}

平面が認識された際の処理は、まず、UnityARUtilityクラスのユーティリティを使って平面オブジェクトを生成します。
そして、ARPlaneAnchorGameObjectクラスのインスタンスを生成し、それぞれ、GameObjectARPlaneAnchorへの参照をセットにして保持します。

あとはそれを、マネージャクラス自身が持っているDictionaryに登録しておきます。
これを登録する理由は、平面の情報は、認識後に連続した状態を持つため(※)更新時に、identifierを元に処理を行う必要があるためです。

※ 連続した情報というのは、どうやらARKitが認識した平面は一意なIDが振られ、その平面の状態がどうなったか、という連続的な計算になるようです。
そのため、検知時のIDをキーにして登録し、更新があった場合に、それを元に平面の位置などを変更してやる必要があるのです。

ARAnchorUpdatedEvent

次に更新処理。
上記でも書きましたが、更新処理は、「平面の連続性」故に、検知時のIDを利用して更新処理を行います。

public void UpdateAnchor(ARPlaneAnchor arPlaneAnchor)
{
    if (planeAnchorMap.ContainsKey (arPlaneAnchor.identifier)) {
        ARPlaneAnchorGameObject arpag = planeAnchorMap [arPlaneAnchor.identifier];
        UnityARUtility.UpdatePlaneWithAnchorTransform (arpag.gameObject, arPlaneAnchor);
        arpag.planeAnchor = arPlaneAnchor;
        planeAnchorMap [arPlaneAnchor.identifier] = arpag;
    }
}

Dictionaryに登録のある平面だった場合に、その状態を更新する処理となります。

ARAnchorRemovedEvent

最後に、平面が破棄されたときの処理。
こちらはたんに、Dictionary内にあったらその情報を削除しているだけですね。

public void RemoveAnchor(ARPlaneAnchor arPlaneAnchor)
{
    if (planeAnchorMap.ContainsKey (arPlaneAnchor.identifier)) {
        ARPlaneAnchorGameObject arpag = planeAnchorMap [arPlaneAnchor.identifier];
        GameObject.Destroy (arpag.gameObject);
        planeAnchorMap.Remove (arPlaneAnchor.identifier);
    }
}

平面に対する処理は以上です。
あとは、ARKit側で検知、更新、破棄が起こるタイミングで平面情報が更新されていきます。

画面をタップした際に、その位置の平面にオブジェクトを移動させる

ARでモデルを表示するだけでもだいぶ楽しい体験ができますが、やはりタップしたりしてインタラクティブなことができるとより楽しくなります。

private void Update()
{
    // 中略。Touchの確認処理
    
    var screenPosition = Camera.main.ScreenToViewportPoint(touch.position);
    ARPoint point = new ARPoint {
        x = screenPosition.x,
        y = screenPosition.y
    };

    // prioritize reults types
    ARHitTestResultType[] resultTypes = {
        ARHitTestResultType.ARHitTestResultTypeExistingPlaneUsingExtent, 
        // if you want to use infinite planes use this:
        //ARHitTestResultType.ARHitTestResultTypeExistingPlane,
        ARHitTestResultType.ARHitTestResultTypeHorizontalPlane, 
        ARHitTestResultType.ARHitTestResultTypeFeaturePoint
    }; 

    foreach (ARHitTestResultType resultType in resultTypes)
    {
        if (HitTestWithResultType (point, resultType))
        {
            return;
        }
    }
}

まずは、Updateメソッド内での処理です。
基本的なタッチ判定処理後だけを抜き出しています。

画面のタッチされた位置をViewport座標に変換したのち、ARpointクラスに値を設定します。
そして、検知したいResultTypeの配列を作り、順次、そのタイプに応じてタッチ位置との判定を行います。
判定は同クラスに設定されたHitTestWithResultTypeで行います。

bool HitTestWithResultType (ARPoint point, ARHitTestResultType resultTypes)
{
    List<ARHitTestResult> hitResults = UnityARSessionNativeInterface.GetARSessionNativeInterface ().HitTest (point, resultTypes);
    if (hitResults.Count > 0) {
        foreach (var hitResult in hitResults) {
            Debug.Log ("Got hit!");
            m_HitTransform.position = UnityARMatrixOps.GetPosition (hitResult.worldTransform);
            m_HitTransform.rotation = UnityARMatrixOps.GetRotation (hitResult.worldTransform);
            Debug.Log (string.Format ("x:{0:0.######} y:{1:0.######} z:{2:0.######}", m_HitTransform.position.x, m_HitTransform.position.y, m_HitTransform.position.z));
            return true;
        }
    }
    return false;
}

UnityARSessionNativeInterfaceHitTestメソッドが定義されているので、それを用いてヒットテストを行っています。
もしヒットした平面があった場合はヒット結果が1以上にあるため、それを元に分岐処理を行い、ヒットしたらその情報を出力しています。

なお、このクラスではタッチ位置にオブジェクトを移動する処理が含まれているので、同時に、設定されたオブジェクトの位置を変更する記述が見られます。

ARカメラを使ってポジトラする

さて最後に。
今回のAR関連の機能を使って、VRでのポジトラをする方法を説明します。
といっても、今までの処理を少し変えるだけなので、実装自体は大したことはしません。

まずはざっとコードを見てもらったほうが早いでしょう。

using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using UnityEngine.XR.iOS;

public class ARAnchorUpdater : MonoBehaviour
{
    [SerializeField]
    private Transform _target;

    [SerializeField]
    private Camera _arCamera;

    [Header("---- AR Config Options ----")]
    [SerializeField]
    private UnityARAlignment _startAlignment = UnityARAlignment.UnityARAlignmentGravity;

    [SerializeField]
    private UnityARPlaneDetection _planeDetection = UnityARPlaneDetection.Horizontal;

    [SerializeField]
    private bool _getPointCloud = true;

    [SerializeField]
    private bool _enableLightEstimation = true;

    private Dictionary<string, ARPlaneAnchorGameObject> _planeAnchorMap = new Dictionary<string, ARPlaneAnchorGameObject>();

    private UnityARSessionNativeInterface _session;

    private void Start()
    {
        _session = UnityARSessionNativeInterface.GetARSessionNativeInterface();

        Application.targetFrameRate = 60;
        ARKitWorldTrackingSessionConfiguration config = new ARKitWorldTrackingSessionConfiguration();
        config.planeDetection = _planeDetection;
        config.alignment = _startAlignment;
        config.getPointCloudData = _getPointCloud;
        config.enableLightEstimation = _enableLightEstimation;
        _session.RunWithConfig(config);
    }

    private void Update()
    {
        // セッションからカメラの情報をもらう
        Matrix4x4 matrix = _session.GetCameraPose();

        _target.transform.localPosition = UnityARMatrixOps.GetPosition(matrix);

        // VRカメラでジャイロを使って回転するため、ここでは回転を適用しない
        //_target.transform.localRotation = UnityARMatrixOps.GetRotation(matrix);

        // ARカメラのプロジェクションマトリクスを更新
        // TODO: もしかしたらいらないかも?
        _arCamera.projectionMatrix = _session.GetCameraProjection();
    }
}

さて、見てもらうと分かりますが、上で書いたUnityARCameraManagerの中身を少しカスタマイズしただけですね。

違う点は、_targetに、ARカメラの移動を適用するためのオブエジェクトを、インスペクタから設定しているだけです。
Updateメソッド内を見てもらうと、カメラの位置同期の処理が_targetに対して行われているのが分かりますね。

そしてもうひとつ注意点として、「回転は適用しない」ということ。
なぜかというと、_targetに指定しているオブジェクトの子要素に、VRカメラが存在しているためです。
そしてVRカメラはCardboard SDKが、ジャイロを使って自動的に回転処理をしてくれます。

つまり、ARカメラの回転も伝えてしまうと、回転が二重にかかってしまうわけなんですね。
(最初それに気づかず、なんで180°回転しただけなのに一周しちゃうんだろうとプチハマりしてました・・)

なので位置だけを同期してあげればいいわけです。
まさに「ポジトラだけ」ARカメラからもらっている感じですね。

以上で、モバイルVRでもポジトラができるようになります。

その他、参考にした記事

lilea.net

recruit.gmo.jp

視錐台とAABBとの交差判定

概要

とあるオブジェクトが「カメラに映る対象か」というのを知りたいケースはあると思います。
また、通常のカメラだけでなく、「視界」を表した視錐台を定義してその中にオブジェクトが含まれるか、というのもあるとありがたい機能でしょう。
(例えば敵AIの視界表現とか)

実際に動かした感じはこんなふうになります↓

ただ、ツイートにも書いてますが視錐台を視覚化するGizmosメソッドがありますが、微妙にカメラのそれと違うのが気になりました・・。
気づいた点として、OnDrawGizmosのときのカメラのAspectが、プレイ時のカメラのAspectと違う、というのはありました。

今回の記事、実装は以下の記事を参考にさせてもらいました。

実装したサンプルはGithubにアップしてあります。

考え方

平面には「表面」と「裏面」が存在します。
平面は、平面の位置から表と裏のふたつの空間に分離している、と見ることもできますね。

ここで、「表側」を平面の法線が向いている方向、「裏側」を平面の法線の反対側とし、AABB(Axis-Aligned Bounding Box:軸並行境界ボックス)の8つある頂点のうち、表側の方向にある点の中で一番端の点を「Positive Point(正の頂点)」、裏側の方向にある点の中で一番端にある点を「Negative Point(負の頂点)」とします。

そしてそれら2頂点の平面との距離を測り、その結果によって平面のどちら側にAABBが存在しているか(あるいは交差しているか)を判定します。

と、言葉だけでは分かりづらいと思うので、図にすると以下のようになります。

図解すると以下のようになります。

AABBの位置の判定方法

AABBの位置の判定方法ですが、意外にシンプルです。

まず、定義した正の頂点と平面との垂線の距離を測ります。
仮にその距離(内積結果)がマイナスだった場合、これは正の頂点が裏側にあることになります。

上記の図を見てもらうと一目瞭然ですが、正の頂点がそもそも裏側にある場合、AABBは必ず裏側にあることになります。

さて、正の頂点がプラス側にある場合、AABBは平面の表側に存在することが確定します。
しかし、状況として以下の2点が考えられます。

  • AABBが完全に表側にある
  • AABBが平面と交差している

もし交差を無視していいのであれば、この時点で判定は終わりになりますが、交差も求めたい場合はさらに計算を続けます。
といっても計算は正の頂点に行ったものと同じことを、負の頂点にも行うだけです。

もし、負の頂点と平面との垂線の距離がプラスだった場合は、AABBは完全に平面の表側にあります。
逆に、距離がマイナスだった場合は、負の頂点が平面の裏側にあることになるので、AABBは平面と交差していることになります。

AABBと平面との判定がこんなに簡単にできるのは驚きですね。

視錐台の内外を判定する

以上で、平面とAABBの交差判定が行えることが分かりました。
今回は、カメラの視錐台にオブジェクトが入っているかどうか、の判断を行いたいため、これだけでは終わりません。

といってもほぼ答えは出ている状態です。

つまり、視錐台は6つの平面で出来ている、と考えることができるので、この6平面との交差判定を行い、そのすべての平面と交差、あるいは表側にある、と判定されれば、それは視錐台の中にオブジェクトが含まれている、と考えることができるのです。

考え方は以上で終わりです。理論としてはとてもシンプルですね。
以下からは、それらの計算方法について詳しく見ていきたいと思います。

正・負の頂点を求める

AABBが持つ8頂点のうち、どの点が平面に対して正の頂点・負の頂点となるのか。
その取得には面の法線のみで決定することができます。

実際に実装した内容は以下のようになります。

/// 
/// 法線から一番近い点を算出する
/// 
/// ターゲットとなるAABB
/// 算出する法線
/// 
static private Vector3 GetPositivePoint(Collider target, Vector3 normal)
{
    Bounds bounds = target.bounds;
    Vector3 result = bounds.min;

    if (normal.x > 0)
    {
        result.x += bounds.size.x;
    }
    if (normal.y > 0)
    {
        result.y += bounds.size.y;
    }
    if (normal.z > 0)
    {
        result.z += bounds.size.z;
    }

    return result;
}

/// 
/// 法線から一番遠い点を算出する
/// 
/// ターゲットとなるAABB
/// 算出する法線
/// 
static private Vector3 GetNegativePoint(Collider target, Vector3 normal)
{
    Bounds bounds = target.bounds;
    Vector3 result = bounds.min;

    if (normal.x < 0)
    {
        result.x += bounds.size.x;
    }
    if (normal.y < 0)
    {
        result.y += bounds.size.y;
    }
    if (normal.z < 0)
    {
        result.z += bounds.size.z;
    }

    return result;
}

処理はとてもシンプルです。

渡された面の法線ベクトルの各成分のプラス・マイナスを見て、プラス(マイナス)側に属する点を算出しているだけです。
なので、法線ベクトルの各成分の0未満、0より上かの判定だけで点の位置を求めています。

なぜ法線だけで求まる?

なぜこれだけで点が求まるのか。
理由は、AABBは「座標に対してすべての辺が垂直・平行である」ということを考えれば分かります。

例えば、平面の法線の方向が上に向いている(Y軸の値がプラス)の場合、AABBの正の側の頂点は必ず上部にある点に限定されます。
あとはこれを、XZ軸に対してもそれぞれ行ってやれば、めでたく正・負の頂点が求まる、というわけです。

さぁ、ふたつの点が算出できたので、次は平面との距離の計算に進みましょう。

平面との距離を計算する

平面との交差判定のために、平面に対する垂線の距離が必要となります。
平面と頂点の垂線の距離は、平面の法線との内積を取ることで簡単に計算することができます。
具体的には、距離を測りたい点Aと、平面の位置を表す点Bとのベクトル「 \vec{AP}」と平面の法線「 \vec{N}」との内積の絶対値が垂線の長さとなります。

図にすると以下のようになります。

ただし、今回は「表」をプラス、「裏」をマイナスとするため絶対値ではなくそのまま結果を利用することで、表裏の判定も含めて距離を算出することができます。

視錐台の6平面の法線を求める

さて最後は、問題となる視錐台を構成する6平面の、各平面の法線の求め方です。
求め方は以下の記事がとても分かりやすく書かれています。

http://miffysora.wikidot.com/frustum-extract-plane

まず考え方として、判定したい点 vにProjectionMatrix(射影行列)を掛ます。

ProjectionMatrixを Pとし、判定したい頂点を vとすると、


Pv = v'

と書けます。

行列とベクトルの掛け算は行とベクトルとの内積を計算するのと同じことなので、以下のように書くことができます。


\begin{vmatrix}
x \cdot P\_{11} + y \cdot P\_{12} + z \cdot P\_{13} + w \cdot P\_{14} \\\
x \cdot P\_{21} + y \cdot P\_{22} + z \cdot P\_{23} + w \cdot P\_{24} \\\
x \cdot P\_{31} + y \cdot P\_{32} + z \cdot P\_{33} + w \cdot P\_{34} \\\
x \cdot P\_{41} + y \cdot P\_{42} + z \cdot P\_{43} + w \cdot P\_{44}
\end{vmatrix} =
\begin{vmatrix}
v \cdot row_1 \\\
v \cdot row_2 \\\
v \cdot row_3 \\\
v \cdot row_4
\end{vmatrix} =
\begin{vmatrix}
x' \\\
y' \\\
z' \\\
w'
\end{vmatrix}

このとき、変換された v'は「同次座標」と呼ばれ、これは「クリッピング座標系」となります。
 wで全要素( x, y, zを割ることで、クリッピング座標系は立方体となります)

参考: http://miffysora.wikidot.com/clip-coordinates

さてここで、以下の式を満たすとき、 xは視錐台の中に収まります。


-w' < x' < w'

つまり、すべての要素に対して不等式が成り立てば、頂点 vは視錐台内にある、と判定されます。


-w' < x' < w' \\\
-w' < y' < w' \\\
-w' < z' < w'

そしてそれぞれの不等式の意味は以下のようになります。


-w' < x' ... (1) \\\
x' < w' ... (2) \\\
-w' < y' ... (3) \\\
y' < w' ... (4) \\\
-w' < z' ... (5) \\\
z' < w' ... (6)
  • (1) ... x'は視錐台の左平面の内側
  • (2)... x'は視錐台の右平面の内側
  • (3) ... y'は視錐台の下平面の内側
  • (4)... y'は視錐台の上平面の内側
  • (5) ... z'は視錐台の近平面の内側
  • (6)... z'は視錐台の遠平面の内側

ここで、左平面に着目してみると、


-w' < x'

を満たすとき、点 xは左平面の「表側」にいることになります。

この式は以下から得られます。


\begin{vmatrix}
v \cdot row_1 \\\
v \cdot row_2 \\\
v \cdot row_3 \\\
v \cdot row_4
\end{vmatrix} =
\begin{vmatrix}
x' \\\
y' \\\
z' \\\
w'
\end{vmatrix}

-w' = -(v \cdot row_4)
x' = (v \cdot row_1)

として得られます。展開すると、


-(v \cdot row_4) < (v \cdot row_1)

となります。

さらに整理して、


0 < (v \cdot row_4) + (v \cdot row_1) \\\
0 < v \cdot (row_4 + row_1) 

となります。

 v (x, y, z, w)です。上記は、ベクトルのそれぞれの成分と、行列の成分( row_4 + row_1)を足したものの内積を取る、ということになります。

つまり、


x(m\_{41} + m\_{11}) + y(m\_{42} + m\_{12}) + z(m\_{43} + m\_{13}) + w(m\_{44} + m\_{14}) = 0

 wの値は常に1で消せるので、


x(m\_{41} + m\_{11}) + y(m\_{42} + m\_{12}) + z(m\_{43} + m\_{13}) + (m\_{44} + m\_{14}) = 0

となります。

 x成分に着目すると、 x * (m_{41} + m_{11})ということです)

さてここで、「平面の方程式」を思い出してみます。

mathtrain.jp

平面の方程式は


ax + by + cz + d = 0

です。
先程展開した式を見てみるとまさにこの形になっているのが分かるかと思います。

展開した式を平面の方程式に当てはめてみると、


a = (m\_{41} + m\_{11}) \\\
b = (m\_{42} + m\_{12}) \\\
c = (m\_{43} + m\_{13}) \\\
d = (m\_{44} + m\_{14})

と整理することが出来ます。

そして平面の方程式から、各 a, b, cは平面の法線になります。
(ただし正規化していないので使う際に正規化する必要あり)

あとは、それぞれの平面に対して上記を求めてやれば視錐台の6平面の法線が求まります。

平面 係数a 係数b 係数c 係数d
m41 + m11 m42 + m12 m43 + m13 m44 + m14
m41 - m11 m42 - m12 m43 - m13 m44 - m14
m41 + m21 m42 + m22 m43 + m23 m44 + m24
m41 - m21 m42 - m22 m43 - m23 m44 - m24
m41 + m31 m42 + m32 m43 + m33 m44 + m34
m41 - m31 m42 - m32 m43 - m33 m44 - m34

※ ただ、Unityの場合は上記の計算ではうまく行かなかったので、サンプルコードでは若干調整してあります。

いったん整理

ここまでで、以下の道具が揃いました。

  • 射影行列から視錐台の平面の法線の求め方
  • 点と平面の垂線の長さの計算
  • AABBの正・負の頂点位置の計算

これを元に計算を行えば、カメラのFov、Near、Far、そしてワールド座標位置から射影行列を計算し、さらにその行列から6平面を計算、それぞれの平面に対してAABBが内外どちらにあるかの判定、が行えるようになります。

ちなみに、射影行列の成分の意味についてはマルペケさんのこちらの記事(その70 完全ホワイトボックスなパースペクティブ射影変換行列)が非常に分かりやすいです。

これをゲームに組み込む場合は、毎フレームごとにこれを繰り返してやれば、冒頭の動画のように「視界に入っているか否か」を判定することができるようになります。

注意点として、これはあくまで「射影行列の視錐台の中に入っているか」という判定を行っているにすぎないので、もし視点と対象の間に遮蔽物があったとしても「内外判定」は「true」を返します。
実際のAIに組み込むなどする場合は、さらに視線と対象の間に遮蔽物がないか、の判定が必要になるでしょう。
(ただ、それは今回の解説の範疇外なので割愛します)

サンプルコード

最後に、今回実装したコードを載せておきます。

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

static public class CheckFrustum
{
    public enum State
    {
        Outside, Inside, Intersect,
    }

    /// 
    /// 対象AABBとProjection Matrixから視錐台内に入っているかの検知を行う
    /// 
    /// AABB対象
    /// Projection Matrix
    /// カメラ位置
    /// カメラのNear
    /// カメラのFar
    /// 
    static public State Detect(Collider target, Matrix4x4 pmat, Transform eyeTrans, float near, float far)
    {
        Plane[] planes = CalculateFrustumPlanes(pmat, eyeTrans, near, far);

        State result = State.Inside;

        for (int i = 0; i < planes.Length; i++)
        {
            Vector3 normal = planes[i].normal;
            Vector3 vp = GetPositivePoint(target, normal);
            Vector3 vn = GetNegativePoint(target, normal);

            // (vp - plane.pos)・normal
            float dp = planes[i].GetDistanceToPoint(vp);
            if (dp < 0)
            {
                return State.Outside;
            }

            float dn = planes[i].GetDistanceToPoint(vn);
            if (dn < 0)
            {
                result = State.Intersect;
            }
        }

        return result;
    }

    /// 
    /// 法線から一番近い点を算出する
    /// 
    /// ターゲットとなるAABB
    /// 算出する法線
    /// 
    static private Vector3 GetPositivePoint(Collider target, Vector3 normal)
    {
        Bounds bounds = target.bounds;
        Vector3 result = bounds.min;

        if (normal.x > 0)
        {
            result.x += bounds.size.x;
        }
        if (normal.y > 0)
        {
            result.y += bounds.size.y;
        }
        if (normal.z > 0)
        {
            result.z += bounds.size.z;
        }

        return result;
    }

    /// 
    /// 法線から一番遠い点を算出する
    /// 
    /// ターゲットとなるAABB
    /// 算出する法線
    /// 
    static private Vector3 GetNegativePoint(Collider target, Vector3 normal)
    {
        Bounds bounds = target.bounds;
        Vector3 result = bounds.min;

        if (normal.x < 0)
        {
            result.x += bounds.size.x;
        }
        if (normal.y < 0)
        {
            result.y += bounds.size.y;
        }
        if (normal.z < 0)
        {
            result.z += bounds.size.z;
        }

        return result;
    }

    /// 
    /// 指定されたProjection Matricsから視錐台の6面の平面を求める
    /// 
    /// Projection Matrix
    /// カメラ位置
    /// カメラのNear
    /// カメラのFar
    /// 
    static public Plane[] CalculateFrustumPlanes(Matrix4x4 pmat, Transform eyeTrans, float near, float far)
    {
        Plane[] result = new Plane[6];

        // 0: Left, 1: Right, 2: Bottm, 3: Top
        for (int i = 0; i < 4; i++)
        {
            float a, b, c, d;
            int r = i / 2;
            if (i % 2 == 0)
            {
                // 平面の方程式
                // ax + by + cz + d = 0
                a = pmat[3, 0] - pmat[r, 0];
                b = pmat[3, 1] - pmat[r, 1];
                c = pmat[3, 2] - pmat[r, 2];
                d = pmat[3, 3] - pmat[r, 3];
            }
            else
            {
                a = pmat[3, 0] + pmat[r, 0];
                b = pmat[3, 1] + pmat[r, 1];
                c = pmat[3, 2] + pmat[r, 2];
                d = pmat[3, 3] + pmat[r, 3];
            }

            Vector3 normal = -new Vector3(a, b, c).normalized;
            normal = eyeTrans.rotation * normal;

            result[i] = new Plane(normal, eyeTrans.position);
        }

        // for the near plane
        {
            float a = pmat[3, 0] + pmat[2, 0];
            float b = pmat[3, 1] + pmat[2, 1];
            float c = pmat[3, 2] + pmat[2, 2];
            float d = pmat[3, 3] + pmat[2, 3];

            Vector3 normal = -new Vector3(a, b, c).normalized;
            normal = eyeTrans.rotation * normal;

            Vector3 pos = eyeTrans.position + (eyeTrans.forward * near);
            result[4] = new Plane(normal, pos);
        }

        // for the far plane
        {
            float a = pmat[3, 0] - pmat[2, 0];
            float b = pmat[3, 1] - pmat[2, 1];
            float c = pmat[3, 2] - pmat[2, 2];
            float d = pmat[3, 3] - pmat[2, 3];

            Vector3 normal = -new Vector3(a, b, c).normalized;
            normal = eyeTrans.rotation * normal;

            Vector3 pos = eyeTrans.position + (eyeTrans.forward * near) + (eyeTrans.forward * far);
            result[5] = new Plane(normal, pos);
        }

        return result;
    }
}

UnityのAPIを使う

ちなみに、カメラ自体を使う場合はUnityに標準で同等の処理をしてくれるユーティリティがあるので、そちらを使うほうが手っ取り早いでしょう。

// 視錐台の6平面を取得
Plane[] planes = GeometryUtility.CalculateFrustumPlanes(Camera.main);
 
// 内外判定
if (GeometryUtility.TestPlanesAABB(planes, bounds))
{
    // 含まれていたときの処理
}
else
{
    // 含まれていなかったときの処理
}

参考にさせてもらった記事: 【Unity】【数学】視錐台(Frustum)について(第2回) – 株式会社ロジカルビート

docs.unity3d.com

ComputeShaderを触ってみる その2 ~バッファ・テクスチャ編~

概要

前回の記事(ComputeShaderを触ってみる その1 ~スレッド編~)で、Compute Shaderのスレッドの概念について書きました。

edom18.hateblo.jp

今回は、Compute Shaderを実際に使って、少し意味のある計算をしてみたいと思います。
意味のある計算をさせるためには当然、CPU側との連携が必要になるので、そのあたりを中心に書いていきたいと思います。

ちなみに今回実装したのは、とある案件で実際に使うことにしたのでそれを元にしたメモです。
具体的には、ひとつのテクスチャを渡すと、決められたブロック単位に切り分け、そのブロック内の透明度を判断、不透明と判断されたところを有効、それ以外を無効としてマークする、というものです。

実際に実行したイメージ図は以下のような感じです。

f:id:edo_m18:20171004110055p:plain

左の画像が渡したテクスチャで、黒い部分が透明なところです。
右の絵がそれを元に計算した、ざっくりと「不透明な部分」を青く色づけしたものです。

なんとなく、不透明な部分と青い部分が一致しているのが分かるかと思います。

まぁぶっちゃけ、CPUでやってもまぁ問題にならないレベルの処理だと思いますが、Compute Shaderを使ういい練習にはなるかなとw

ComputeShaderに値を渡す

さて、コンピュートシェーダで大事なスレッドの概念を説明したあとは、シェーダに対してCPU側から値を送る方法を見てみましょう。

設定についてはSetXXXX系メソッドを使います。

例えば、特定のfloat値を渡したい場合は以下のように記述します。

シェーダ側

float myFloat;

スクリプト

shader.SetFloat("myFloat", 1.0f);

intを渡したい場合は、

shader.SetInt("myInt", 5);

などのようにしてやれば大丈夫です。

CPUとGPUでは基本的にはメモリ空間が異なるため(物理的にも離れているケースがだいたい。のはず)、CPUで使っているデータを、GPUで使えるメモリにコピーする(転送する)必要があります。
そのため、上記のように、GPU側に「これからこのデータをこういう変数名で送りますよ」という宣言をしているわけですね。

ちなみに、GPU周りのことについて詳しく知りたい方は、以下の書籍がオススメです。
最近のグラフィック事情から、GPUのハード・ソフト的な面の説明に、CPUとどうやって連携しているか、など細かい内容が詳細に書かれています。

GPUを支える技術 ――超並列ハードウェアの快進撃[技術基礎] (WEB+DB PRESS plus)

GPUを支える技術 ――超並列ハードウェアの快進撃[技術基礎] (WEB+DB PRESS plus)

閑話休題

基本的には、シェーダ側で使用したい変数を宣言しておき、SetXXXX系メソッドでCPUからデータを転送してやればOKなわけですね。

データを受け取るバッファ

さて、送るだけなら上記のように記述してやればOKですが、GPGPUということは、なにかしら計算した結果をCPU側で利用したいはずです。
そのため、GPUで計算した結果を受け取る方法が必要になります。

そのために利用されるのがComputeBufferクラスです。

まずは簡単に、使い方のコード断片を。

RWStructuredBuffer<float> Result;

シェーダ側ではRWStructuredBuffer<T>型のバッファを宣言しておきます。
ジェネリックで指定する型は、実際に利用したいデータの型です。

続いてCPU側。

ComputeBuffer buffer = new ComputeBuffer(num, sizeof(float));
int kernelID = _shader.FindKernel("CSMain");
_shader.SetBuffer(kernelID, "Result", buffer);

CPU側ではComputeBufferクラスのインスタンスを、これまたSetBufferでセットします。
ComputeBufferのコンストラクタに渡している第一引数はバッファの個数です。第二引数で1要素のサイズを指定します。

このあたりはC言語などを触ったことがある人であればイメージしやすいかと思います。

実際にデータを受け取る

さて、バッファをセットしただけでは当然、データは取得できません。
実際にデータを取得するには以下のようにします。

float[] data = new float[num];
buffer.GetData(data);

GPUに設定していたバッファのGetDataメソッドを利用して、GPUの計算結果をCPUに転送します。
受け取るために、バッファと同じサイズのデータをCPU側で確保して、その確保した領域にデータを転送してもらう感じですね。

あとは、dataをいつものようにfor文などでループさせて、目的の処理を行います。

バッファの後処理

普段、C#を触っているとGCでメモリを開放してくれるのであまり気にすることはないかもしれませんが、今回利用したバッファは自身で適切に解放してやらないとなりません。

buffer.Release();

Releaseメソッドを呼ぶことで適切にメモリが開放されます。

このあたりは、C言語C++を触っている人ならそこまで気にならないかもしれませんね。

テクスチャのread / write

次はテクスチャへのアクセスについてです。
本来、GPUはグラフィクス周りを担当するハードウェアなので、当然ながらテクスチャへのアクセスも行えます。

GPU側では以下のように宣言します。

RWTexture2D<float4> texCopy;
Texture2D<float4> tex;

さて、RWと付いたものと付いていないものがあります。
これは、(多分)Read / Writeの略だと思いますが、つまり、読み込み専用か、書き込みも行えるか、の違いです。
そして上記のtexCopy変数のほうは読み書きが行なえます。

前回の記事のコードを再掲すると、

#pragma kernel CSMain

RWTexture2D<float4> texCopy;
Texture2D<float4> tex;

[numthreads(8,8,1)]
void CSMain(uint2 id : SV_DispatchThreadID)
{
    float4 t = tex[id];
    texCopy[id] = t;
}

これはただ、渡されたテクスチャの値をコピーするだけの簡単なサンプルです。
ここで重要な点は、テクスチャの各要素へのアクセスが非常に簡単だ、という点です。

上記の例では分かりやすさのために、一度テクセルを変数に入れたのちに、コピー対象のテクスチャに入れていますが、それを省略すれば一行で記述できてしまうほどの簡単さです。
テクスチャは2次元の配列になっていて、添字にはuint2型の値を使うことができます。
上記の例ではiduint2型なので、そのままアクセスできている、というわけですね。

そしてなぜそれが適切に各テクセルにアクセスできるのか、については前回の記事を参照してください。

テクスチャの内容を、畳込み処理で透明・不透明を判断する

以上で、バッファ、変数周りの記述とその意味についての解説が終わりました。
最後は、これらをまとめて、少し意味のある計算を行う例を解説したいと思います。

冒頭でも書いたように、今回は、テクスチャに対して指定したブロック単位に区切り、そのブロックの中のテクセルの平均が、「透明」に属するのか「不透明」に属するのかの計算をしてみたいと思います。

まずは今回書いたシェーダコードを載せます。

#pragma kernel CSMain

RWStructuredBuffer<float> Result;
Texture2D<float4> Texture;

int Length;
int Width;
int Height;

[numthreads(1, 1, 1)]
void CSMain (uint2 id : SV_DispatchThreadID)
{
    float result = 0;
    int halfWidth = Width * 0.5;
    int halfHeight = Height * 0.5;

    // 指定された分の、縦横の透明度を合計する
    for (int i = -halfHeight; i <= halfHeight; i++)
    {
        for (int j = -halfWidth; j <= halfWidth; j++)
        {
            int u = (id.x * Width) + halfWidth + j;
            int v = (id.y * Height) + halfHeight + i;
            float4 tex = Texture[uint2(u, v)];
            result += tex.a;
        }
    }

    float denom = 1.0 / (Width * Height);
    int index = id.y * Length + id.x;
    Result[index] = result * denom;
}

とても短いコードですね。

まず、なにをしているかを図解します。

今回、CPU側では以下のようにComputeShaderを起動しています。

_shader.Dispatch(kernelID, divCount, divCount, 1);

つまり、縦横に同じ数だけ分割したスレッドグループを起動しています。
なので図にすると以下のようなブロック分、スレッドグループが起動されるわけですね。

f:id:edo_m18:20171007165123p:plain

今回は10 x 10分割したので、全部で100個のブロックがあることになります。
そして、各ブロックに含まれるピクセルすべての透明度を足しこみ、最後に全体のピクセル数で割ることで、そのブロックの平均透明度を求めている、というわけです。

利用する際は、その平均値を元に、しきい値以上あれば不透明扱い、それ以下なら透明扱いと判断することで、冒頭の画像のように、透明・不透明の判定を行っている、というわけですね。

CPU側は以下のように起動しています。

_shader = ComputeShader.Instantiate(Resources.Load<ComputeShader>("Shaders/HitAreaDetector"));

// 分割数で算出された一区画に対するピクセル数をさらに奇数に補正する
int pixelPerDivW = texture.width / divCount;
pixelPerDivW = pixelPerDivW - (1 - pixelPerDivW % 2);

int pixelPerDivH = texture.height / divCount;
pixelPerDivH = pixelPerDivH - (1 - pixelPerDivH % 2);

int num = divCount * divCount;
ComputeBuffer buffer = new ComputeBuffer(num, sizeof(float));

int kernelID = _shader.FindKernel("CSMain");

_shader.SetBuffer(kernelID, "Result", buffer);
_shader.SetTexture(kernelID, "Texture", texture);
_shader.SetInt("Length", divCount);
_shader.SetInt("Width", pixelPerDivW);
_shader.SetInt("Height", pixelPerDivH);

float[] rawData = new float[num];

_shader.Dispatch(kernelID, divCount, divCount, 1);
buffer.GetData(rawData);

buffer.Release();

やっていることはシンプルに、ひとブロック分のピクセル数を計算し、GPUへは、計算対象となるテクスチャと、結果を受け取るバッファ、そしてピクセル数などのパラメータを送っているのみです。
あとは、計算結果を取得して必要なデータとして処理を行う、という流れです。

ハマった点

最後に、いくつかハマった点を。

今回、テクスチャをブロックに分割してあたりを付ける、という処理を書きましたが、ComputeShaderの仕様なのか、ひとつのシェーダを複数個同時起動すると、バッファへ値が正常に格納されず、意図した動作にならない、という挙動になりました。
シェーダ自体を複製すると問題が解決するので、ロードしたシェーダを複製したところ、以下のエラーが・・・。

!(transfer.IsRemapPPtrTransfer() && transfer.IsReadingPPtr())
UnityEngine.Object:Instantiate(ComputeShader)

どうやらUnityのバグ?らしく、以下の投稿を見つけました。

https://forum.unity.com/threads/error-when-instantiating-compute-shader.408533/

ただ、エラーは出るものの、意図した挙動になっているので、いったんはこのエラーに目をつぶって実装を進めました・・。

このあたりについて、なにか情報をお持ちの方は連絡いただけるとうれしいです( ;´Д`)

シンプルなBehavior Treeを実装してみる

概要

今回は、AIの中でも比較的スタンダードな、「Behavior Tree」について書きたいと思います。
(内容は、いろいろな記事を拾い読みしながら、自分の解釈で実装したものになるので、多少の誤解や間違いがあるかもしれません)

実装したサンプルはGithubで公開しています。

GitHub - edom18/SimpleBehaviorTree

スクエニの以下の記事にも、

現在のゲームのキャラクターの人工知能の約7割程度がビヘイビア・ツリーで作られていると推測されます。

と記載があるので、それなりに大きな比率を占めているものだと思います。

thinkit.co.jp

ちなみに、Unityのアセットストアにも、GUIで簡単に実装が行えるアセットが売られています。


Behavior Designer

Behavior Treeとは

Behavior Treeとは、ビヘイビア、つまり振る舞いをツリー構造状に定義し、それを逐一実行してく形のものです。
AIに対して、なにかしらの判断と、一連の流れを記述した行動をとらせたい場合に重宝する手法です。

Behavior Treeを構成するのは「ノード」です。
いくつかの基本ノードを様々に組み合わせながら、AIとしての処理を作っていきます。

ノードの種類

  • ActionNode
  • Decorator
  • ConditionNode
  • Sequencer
  • Selector
  • Repeater

などがあります。

特に、ActionNodeConditionalNodeについてはリーフノードになっていて、分岐処理や、実際のアクションを実行するノードとなります。
それ以外のSequencerSelectorは、いわゆるコンポジットパターンによる、子ノードを持てるノードになっています。

名前からなんとなく分かるかと思いますが、Sequencerは一連の流れを処理し、Selectorは、子ノードのうちのどれかを選択します。

以下で少し細かく見ていきます。

ActionNode

アクションノード。一番末端にあるノードで、ゲームオブジェクトの実際の振る舞い(アニメータを起動してアクションさせたり、1フレーム分移動させたり、など具体的な行動)を記述します。

Decorator

デコレータ。アクションノードなどの結果をデコレート、つまり装飾して返します。
例えば、アクション自体は成功しているけど、強制的に失敗にする、など用途は様々です。

ConditionNode

条件分岐用のノード。
プレイヤーが近くにいあるか、HPは足りているか、など様々な分岐を行うのに利用されるノードです。
以下で説明するシーケンサの中のひとつのノードに指定することで、例えば「プレイヤーが近くにいたら攻撃する」などの分岐が可能になります。

また、条件分岐ノードは「条件が更新された」場合に、それまで実行していた処理を中断して分岐がtrueになったあとの処理を再度実行するかを評価することができます。(詳細は後述します)

Sequencer

シーケンサ。つまり一連の流れを処理するノードです。
Selectorとの大きな違いは、登録された子ノードすべてを実行し、もし途中のノードで「失敗」が返された場合は、その時点でシーケンサの処理自体を「失敗」として親に戻します。
いわゆる「AND」的な振る舞いをするのがシーケンサの役割です。

主な利用シーンとしては、プレイヤーの位置を特定し(1)、その場所まで移動(2)、そして一定距離まで近づいたら攻撃(3)というような一連の流れを実行します。
もし仮に、途中の「プレイヤーの位置まで移動」が困難になった場合、(高台に逃げられた、とか)この処理は「失敗」扱いとなり、結果として「近づいて攻撃する」という一連の流れ自体が失敗になるわけです。

Selector

セレクタ。どれかひとつを選択します。イメージ的には「OR」ですね。
そしてこれは、「どんな行動をすべきか」を選択する場合に一番用いられるノードでしょう。

前述のシーケンサと組み合わせることで、「一定の体力がある場合は、近づいて攻撃」のパターンと、「体力が少なくなったから離れて攻撃」の選択肢があった場合に、ふたつのパターン自体はシーケンサにより一連の流れとして実装し、その「どちらかを選択する」ことを、セレクタが行う、という感じになります。

Repeater

設定されたノードを「リピート」するノードです。
ルートノードの下において処理をループすることで、常に思考を繰り返すAIが作れたりします。

ノードの状態

ノードにはいくつかの状態があります。

  • 非アクティブ(Inactive)
  • 成功(Success)
  • 失敗(failure)
  • 実行中(Running)
  • 完了(Completed)

該当の処理が成功した場合は「成功」、失敗した場合は「失敗」、そして移動処理中など、まだ処理結果が分からず、処理中を表す状態が「実行中」となります。
また、まだタスクの実行が開始されていない状態を「非アクティブ」とし、非アクティブ状態で活性化された場合にOnStartなどの処理を実行します。

そして最終的に、全タスクが完了状態になった場合に、Behavior Tree全体が完了状態となるようになっています。

ノードのサイクル

各ノードはサイクルを持っていて、OnAwakeOnStartOnUpdateOnEndなどがあります。
今回実装したのはこの4つの状態です。

これを見てピンと来る方もいるかもしれませんが、いわゆるステートパターンにある状態遷移に近いイメージですね。
各ノードが活性化され、アクティブなノードが常にOnUpdateが呼ばれる形で実装しています。

冒頭のスクエニの記事でも触れられていますが、ステートパターンとは相性がよく、スクエニFF15の各キャラクターは全体の大きな状態はステートパターンで実装され、各状態ごとの細かい処理はBehavior Treeで実装されているようです。

Conditionalノードの場合は、必要に応じて再評価する

Conditionalノードについてはやや特殊で、条件分岐を行う関係上、「再評価する必要がある場合」があります。
例えば、敵が近くにきた場合は攻撃する、というAIを作るとしましょう。

当然、最初は敵は近くにいません。
そしてその分岐は「失敗」に終わります。敵が近くにいないからですね。

その後、時間が経過して、敵が近づいてきたとしましょう。
しかし、再評価する仕組みがない場合、すでにその分岐は評価が終わってしまっているため、敵が近くにいる、という分岐処理は二度と実行されません。
つまり、敵が近づいてきたにもかかわらず、「敵が近づいてきたら攻撃する」という項目が一切実行されなくなってしまいます。

AIとしてこれでは困りますね。
そのため、再評価が必要な分岐の場合は、親ノード側でそれを知る必要があるわけです。

UnityのアセットであるBehavior Designerを見てみたところ、どうやら再評価がある分岐ノードについては常にOnUpdateを呼び続け、仮に状態が変化した場合にそれを検知するような仕組みになっていました。
実装方法は様々でしょうが、(オブザーバパターンなど)とにかく、分岐ノードの再評価が必要な場合は、常にチェックするように実装する必要がある、というわけです。
(じゃないと状態変化に気づけませんからね)

直感的にも再評価してくれるほうがいいと思うので、今回自分で自作してみた実装には再評価の仕組みを入れてあります。

実装方針

今回の実装は、比較的シンプルな形で、「ちょっとした分岐と再評価、そして行動」ができるAIが作れるレベルのものを目指しました。
(あくまでビヘイビアツリーの内容把握が目的なので)

まず、全体を管理するためのクラスとしてSimpleBehaviorTreeクラスを用意します。
このクラスがマネージャとして振る舞い、全体のタスクの更新と現在の状況の把握を行います。

ノードはNodeクラスがベースクラス

各ノードに関しては、Nodeクラスをベースクラスとして、前述したノードを実装しました。
これをそれぞれツリー構造になるように親子構造を構築し、それのルートノードをSimpleBehaviorTreeの実行する最初のノードとして設定します。

using UnityEngine;

namespace BehaviorTreeSample
{
    /// <summary>
    /// Simple Behavior Treeのノードベースクラス
    /// </summary>
    public abstract class Node
    {
        protected GameObject _owner;
        public GameObject Owner
        {
            get { return _owner; }
            set { _owner = value; }
        }

        private int _index = -1;
        public int Index
        {
            get { return _index; }
            set { _index = value; }
        }

        protected Node _parentNode;
        public Node ParentNode
        {
            get { return _parentNode; }
            set { _parentNode = value; }
        }

        protected string _name;
        public string Name
        {
            get { return _name; }
            set { _name = value; }
        }

        // 現在のステータス
        protected BehaviorStatus _status = BehaviorStatus.Inactive;
        public BehaviorStatus Status
        {
            get { return _status; }
        }

        public Node()
        {
            _name = GetType().ToString();
        }

        /// <summary>
        /// Behavior Tree起動時に一度だけ呼ばれる
        /// </summary>
        public virtual void OnAwake()
        {
            // do nothing.
        }

        /// <summary>
        /// ノードが実行されたら呼ばれる
        /// </summary>
        public virtual void OnStart()
        {
            Debug.Log("[OnStart] " + Name);
            _status = BehaviorStatus.Running;
        }

        /// <summary>
        /// ノード実行中(Running)に毎フレーム呼ばれる
        /// </summary>
        public virtual BehaviorStatus OnUpdate()
        {
            if (_status == BehaviorStatus.Completed)
            {
                Debug.Log("This task already has been completed.");
                return _status;
            }

            if (_status == BehaviorStatus.Inactive)
            {
                OnStart();
            }

            return _status;
        }

        /// <summary>
        /// ノードの実行が終了したら呼ばれる
        /// </summary>
        public virtual void OnEnd()
        {
            if (_status == BehaviorStatus.Completed)
            {
                return;
            }

            _status = BehaviorStatus.Inactive;
        }

        /// <summary>
        /// ノードが中断された際に呼び出される
        /// </summary>
        public virtual void OnAbort()
        {
            OnEnd();
        }

        /// <summary>
        /// 子ノードを追加する
        /// </summary>
        /// <param name="child">追加する子ノード</param>
        public virtual void AddNode(Node child)
        {
            // do nothing.
        }

        /// <summary>
        /// 子ノードを複数追加する
        /// </summary>
        /// <param name="nodes">追加する子ノード郡</param>
        public virtual void AddNodes(params Node[] nodes)
        {
            // do nothing.
        }
    }
}

見てもらうと分かるように、OnStartOnUpdateOnEndメソッドをvirtualで定義し、派生クラス側でそれをoverrideして利用する想定です。
OnAwakeだけは少し特殊で、SimpleBehaviorTreeクラスが起動された際に、ツリー全体を走査して、すべてのノードを「起こし」ます。そのときに実行されるのがOnAwakeです。
なので、このメソッドは実行後一度だけ呼ばれるメソッドとなります。初期化処理などをここで記述する想定です。

SimpleBehaviorTreeクラスは全体を管理

前述したように、SimpleBehaviorTreeクラスが全体を管理するマネージャクラスとなります。
そして管理方法としてはシンプルに、ツリー構造を持ったタスクすべてにユニークなインデックスを割り振り、インデックス番号からすぐに該当タスクを取り出せるようにします。

インデックス割り振りは、起動時に全タスクを起こすOnAwakeを呼び出すタイミングで行います。その際に、順にツリーを辿ってインデックスを割り振ります。

処理としては以下のようになります。

/// <summary>
/// 対象ノードを起動(Awake)する
/// </summary>
/// <param name="node">起動するノード</param>
private void CallOnAwake(Node node)
{
    // ノードに全体のグラフの通し番号を設定する
    node.Index = _nodeList.Count;

    _nodeList.Add(node);

    // 対象ノードにオーナーを設定する
    node.Owner = _owner;

    // ノード起動
    node.OnAwake();

    // CompositeNodeの場合は再帰的に起動させる
    CompositeNode cnode = node as CompositeNode;
    if (cnode != null)
    {
        foreach (var child in cnode.Children)
        {
            CallOnAwake(child);
        }
    }
}

そして、全体が管理できるようになったら、ルートノードから処理を開始します。
実行はツリー構造を辿り、シーケンサセレクターなどから構成された部分ごとに実行を繰り返します。

最終的には必ずどれかのリーフノードにたどり着くので、それを実行し、それが「成功」か「失敗」か、あるいは「実行中」かを判断し、「実行中」だった場合は処理をいったんそこで停止します。

※ 今回の実装では、全タスクの走査は1フレーム内で行います。そのため、どこかに無限ループがあったり、実行内容が多すぎる場合はゲームが停止します。

Conditionalノードの監視

前述したように、条件分岐を行うノードに関しては必要に応じて「再評価」する仕組みを導入します。
具体的には、再評価するべきとフラグが立てられたノードに関しては再評価リストにノードを登録し、他のタスク実行中も常に条件分岐処理(OnUpdate内でそれを行う)を実行し、もし条件分岐の状態が変化した場合にそれを通知します。

再評価対象などの情報を保持する専用クラスを設ける

今回の設計方針では、全タスクに対してインデックスが割り振られているので、そのインデックスを保持して、どのタスクが再評価必要かを把握するにはインデックスだけがあれば十分です。
ただ、それに紐づく親のタスクインデックスや、前回のタスクの終了状態などを一緒に保持しておくことで、評価が切り替わったことを検知することができるようになっています。

/// <summary>
/// 再評価する際の諸々の情報を格納する
/// </summary>
public class ConditionalReevaluate
{
    public int Index { get; set; }
    public BehaviorStatus Status { get; set; }
    public int CompositeIndex { get; set; }
    public int StackIndex { get; set; }
    public void Initialize(int i, BehaviorStatus status, int stack, int composite)
    {
        Index = i;
        Status = status;
        StackIndex = stack;
        CompositeIndex = composite;
    }
}

Indexはタスクのインデックス、Statusは判断されたときの状態、StackIndexはスタック中どこにあるかのインデックス、CompositeIndexは親のインデックスを参照しています。

この「再評価情報」をリスト化し、再評価が必要なタスクを毎フレームチェックし、変化があった場合にそれを検知します。
そのために、毎フレームのUpdateごとに再評価リストをすべて評価します。

/// <summary>
/// 再評価が必要なノードを再評価する
/// </summary>
/// <returns>再評価して変化のあったノードのIndex</returns>
private int ReevaluateConditionalTasks()
{
    for (int i = 0; i < _reevaluateList.Count; i++)
    {
        ConditionalReevaluate cr = _reevaluateList[i];
        BehaviorStatus status = _nodeList[cr.Index].OnUpdate();

        // 前回の状態と変化していたら、祖先まで遡って処理を停止する
        if (cr.Status != status)
        {
            CompositeNode cnode = _nodeList[cr.CompositeIndex] as CompositeNode;
            if (cnode != null)
            {
                cnode.OnConditionalAbort(cr.Index);
            }
            _reevaluateList.Remove(cr);
            return cr.Index;
        }
    }

    return -1;
}

再評価に変化があったら、同じ祖先ノードまで遡って停止を伝える

もし仮に、どこかの再評価が変化した場合は、それまで実行していたタスクを終了させ、変化した分岐からやり直します。
例えば、シーケンサの最初のタスクに「敵が近くにいたら」というタスクがあった場合、大体の場合においては敵が近くにいないため「失敗」に終わります。
失敗した場合は「パトロール」などの別のタスクが実行されることになります。

そしてしばらくして敵が近づいてきた場合は分岐の結果が変わります。
このタイミングで、先に進んでいたタスクの「パトロール」を停止し、分岐結果が変わったところまでやり直し、以後の処理を継続します。

つまり、敵が近づいてきたら攻撃、などの「分岐が成功したあと」のタスクが実行される、というわけです。

↑最初の分岐が失敗になり、次のシーケンスが実行されている状態

↑最初の分岐状態が変更されたため、それまで実行されていたタスクを終了し、変化した分岐先の処理が開始される

以上のように、タスクを順次実行しながら、分岐が変化した際にそこまで戻って処理を行うことで、状況を把握し、適切に行動を起こすAIの仕組みを構築することができます。

実装してみて

SequencerSelectorが重要な要素になります。
これらが連携しながらAIとしてキャラクターを操作していきます。

なので、アクションノードなどは実際の実行処理を記述するのみです。

今回は簡単のため、インスタンス生成時にラムダ式を渡してそれを実行するようにしています。
よく使われるようなアクションは個別に新規で作成してもいいと思います。(例えば一定時間待つアクションとか)

今回実装したアクションノードクラス↓

/// <summary>
/// 実際のアクションを行うノード
/// </summary>
public class ActionNode : Node
{
    private Func<GameObject, BehaviorStatus> _action;

    public ActionNode(Func<GameObject, BehaviorStatus> action)
    {
        _action = action;
    }

    public override BehaviorStatus OnUpdate()
    {
        base.OnUpdate();
        _status = _action.Invoke(Owner);
        return _status;
    }
}

実装してみて思ったのは、こうしたグラフを持つものはやはり、GUIベースのツールがないと実装するのは困難だな、ということ。
仕組み自体はできたものの、これを、高度に入り組んだAIを実際に組むとなるとコードが膨大になり、かつ管理も困難になるので、実際のところは、上で紹介したようなアセットを使うなどしたほうがよさそうです。

が、仕組みや動作原理などを把握したかったので今回のサンプルを作成しました。
冒頭でも書きましたが、いろんな記事を拾い読みして想像で実装したので、若干勘違いや他で使われているものと異なっている部分があるかもしれません。
また、「Behavior Designer」を実際に使ってその使用感や、カスタムタスクを実際に作成して動作確認したりしながら内部を想像して実装したので、だいぶ「Behavior Designer」よりの実装になっていると思います。

ちなみに、(タイトル同じですが)GREEのEngineerブログで、PHPによる実装例が記載されていました。
こちらもだいぶシンプルな例になっているので、合わせて見てみるとより分かりやすいかもしれません。

シンプルなBehaviour Treeを実装してみる - GREE Engineers' Blog

その他のAI実装パターン

ちなみに、以前にこれとは別のAI作成パターンとして、「ゴール駆動型エージェント」の記事も書いているので、AI関連に興味がある方は読んでみてください。

edom18.hateblo.jp

edom18.hateblo.jp

Daydream開発はじめたのでメモ

概要

Daydream開発を始めてみたので、色々とメモしていきます。
基本的に気づきベースなので、随時更新していきます。

開発環境の整備

開発環境が整わないと色々と大変なので、Tips的な部分をメモ。

adbをWi-Fi経由で実行する

Daydream開発をしていると、実機インストール→Daydreamデバイスで見る、を繰り返すため、USB接続でやっているととてもめんどくさいです。
しかし、adbにはWi-Fi経由でコマンドを実行する方法が用意されています。

まず、USBで一度Android端末とPCを接続します。
コマンドプロンプトから以下のコマンドを実行することで、以後はWi-Fi経由でコマンドを実行し、ケーブルレスでapkのインストールなども可能になります。

$ adb tcpip 5555
$ adb connect xxx.xxx.xxx.xxx

xxx.xxx.xxx.xxxAndroid端末のIPアドレスです。

接続を解除するには以下のようにします。

$ adb disconnect

コントローラを使う

Daydream Viewには標準でコントローラが付属しています。
そしてDaydreamアプリはコントローラを認識しないと起動しないので、必然的にコントローラが必須となります。

アプリ内でコントローラを利用するにはGvrControllerクラスが提供するプロパティを利用します。
ドキュメントはこちら(Controller API Basics

コントローラの状態を知る

ドキュメントから引用すると、以下の状態を知ることができます。

Buttons

The controller reports the following button properties:

  • ClickButton: True if the Click button (a touchpad click) is currently being pressed.
  • ClickButtonDown: True for 1 frame after user starts pressing the Click button.
  • ClickButtonUp: True for 1 frame after user stops pressing the Click button.
  • AppButton: True if the App button is currently being pressed.
  • AppButtonDown: True for 1 frame after user starts pressing the App button.
  • AppButtonUp: True for 1 frame after user stops pressing the App button.

GvrEventSystemを使う

Google VR SDKから、イベントシステムを利用した、各種イベントの制御の方法が提供されています。
といっても、独自のものはIGvrPointerHoverHandlerのみで、それ以外は通常のuGUIで提供されているインターフェースを実装することでイベントをトラッキングすることができるようになっています。
(例: IPointerClickHandlerなど)

ハマったこと

いくつかハマったことをメモとして残しておきます。

Single Passレンダリングを利用すると色味がおかしくなる

色々な最適化方法を参考に設定を行っていたところ、Single Passレンダリングを有効化して実機確認したところ、色が反転するような現象が現れました。
結論から言うと、Use 32bit Display Bufferをオフにしていると起こるようです。

Daydreamコントローラの感度が悪い

開発をしていて、しばらくしたらどうも「Daydreamコントローラの感度が悪いな・・」と思うことが何度かありました。
いろいろ調べてみると以下の投稿を発見。どうやら、充電がなくなると精度が悪くなるようです。
なので、充電に気をつけて、できるだけフル充電状態で開発ができるようにしておくとよさそうです。

www.reddit.com

Playerにコライダを設定したらイベントが動作しない

GvrEventSystemに則ってイベントを処理していて、とあるタイミングでPlayerにコライダを設定したところ、コントローラのRayが自身にヒットしてしまって一向にオブジェクトに反応しない、ということがありました。

冷静に考えればRayCastなので当たり前ですが、仕組みがそもそもどうやっているのかを把握していなかったので若干ハマりました。
GvrPointerPhysicsRaycasterクラスに、eventMaskというプロパティがあるので、それにマスクを設定しておけば大丈夫です。

例:

GvrPointerPhysicsRaycaster raycaster = GetComponentInChildren<GvrPointerPhysicsRaycaster>();
int playerLayer = (1 << 8);
raycaster.eventMask = ~playerLayer;

ポイントした先にワープするとポインタが正常に動かなくなる

これも理由は上記と同じなのですが、ワープポイントみたいなオブジェクトを作り、それにコントローラで選択させて、決定時にその場所までワープする、みたいなことは比較的やる処理かなと思います。

ただ気をつけないとならないのは、ワープポイントの場所に移動させると、(実装の仕方によっては)コライダの中に入ってしまい、結果そのオブジェクトにコントローラのポインタが取られ続けてしまう、という問題があります。

自分の実装では、プレイヤーがワープポイントにいる間はRaycast向こうなレイヤーに変更し、別の場所に移動したら戻す、ということで対処しました。

AndroidアプリのDaydreamコントローラエミュレータで実機アプリを動かす

Daydreamは、専用コントローラを関連付けないと起動ができません。
(コントローラを認識してね画面から先に進まない)

とはいえ、現状は日本での発売がなく、せっかくDaydream対応端末を買ってもDaydreamコンテンツを楽しむことができません。
そこで、Android上で実行できる、コントローラのエミュレータを使います。

エミュレータはこちらからダウンロードすることができます。
基本的にはPC(開発機)に接続して開発用途として使うものになります。

が、やはり実機での確認は必須。
ということで、これを実機でも利用できるように設定します。

手順としては、

  1. Daydreamアプリを実行するAndroid(実機)と、コントローラ用AndroidBluetoothでペアリングしておく(これはDaydream関係なく普通に設定から行う)
  2. Daydreamアプリ側で、GoogleVR設定画面から「ビルド」を複数回タップして開発者メニューを表示する
  3. 開発者メニューから、コントローラのエミュレータを有効化する
  4. (3)のタイミングで、どのAndroid端末のエミュレータを利用するかリストが表示されるので、(1)で同期した端末を選択する

という流れで行います。

無事に接続が完了すると、エミュレータ画面で「Connected」表示になるので、あとは普通にDaydreamアプリを操作することが可能になります。

フレームレートが出ない

開発をしていて、Physicsを利用してすばやく動かしたオブジェクトがやたらブレて見える現象がありました。 野生の漢さんの記事で書かれている、FixedUpdate周りかなと思って色々やってみたものの変化なし。

そして色々調べていたところ、以下の記事を発見。

https://forum.unity3d.com/threads/best-practice-project-settings-for-daydream.438598/

ここで書かれている以下の項目にしたところだいぶ軽くなりました。

  • Enable 2x Anti Aliasing. (Unity will issue a warning about performance when you build, but it performs fine and looks bad without it.)
  • Disable real time shadows. (They look bad and kill performance.)
  • Disable "Use 32-bit Display Buffer"
  • Stick with Forward or Vertex rendering
  • Enable Multithreaded Rendering
  • Enable Static and Dynamic batching

HDRが有効にならない

Post Processing Stackを使っていて、Bloomが有効にならないなーと思ったら、そもそもHDRが有効になってなかったというオチ。
Graphics Settingsを見てみると、Androidの場合はuse HDRがデフォルトではオフになっているのが原因。それをオンにしたら普通に動きました。

このへんで言及されてるやつ。

github.com

プロファイリング

プロファイリングするにはいくつかのツールがあります。
一番シンプルなのは、ビルトインの内部プロファイラを利用することだと思います。(が、なぜかAndroidでこれが出力できなかった( ;´Д`))
ただ、色々試したのでメモしておきます。

adb logcatでログを出力

AndroidをPCに接続して、以下のようにコマンドプロンプトから実行すると、ログがだーっと出力されます。

$ adb logcat

ただ、これだとAnroid上で実行されているすべてのアプリやシステムのログがすべて出力されてしまうので、Unityだけに絞ります。
具体的には、

$ adb logcat Unity:V *:S

Unity部分がタグで、VVerboseの略、*:Sは、Unityとタグが付いたもの以外のログをすべてSilentにする、という指定です。
これで無事、Unityタグがついたログだけがフィルタリングして出力されるようになります。

ファイル保存

セーブデータなど、ファイルを保存するには保存先パスを指定する必要があります。
保存先パスとしてはApplicationクラスから取得できる以下のパスを利用します。

Application.dataPath

アプリケーションが保存されているパス。

環境 取得パス
Android(本体) /data/app/<アプリのID>.apk
Android(SDカード) /mnt/asec/<アプリのID>/pkg.apk
iOS /var/mobile/Applications/****/myappname.app/Data

Application.persistentDataPath

永続的なデータを保存するパス。 ユーザーデータなど、アプリが再生成できないファイルを配置する。

環境 取得パス
Android(本体) /data/data/<アプリのID>/files/
Android(SDカード) /mnt/sdcard/Android/data/<アプリのID>/files/
iOS /var/mobile/Applications/****/Documents

apkに含まれているManifestの内容を確認する

Daydream向けアプリでは、いくつかの機能の有効化などをManifestに記載する必要があります。
その際、実際にビルドしたapkに該当の項目がしっかり含まれているか、というのを確認したいケースがあります。

それを行うには、aaptというツールがあるので、それを利用します。
aaptは、apktoolsに含まれています)

ibotpeaches.github.io

コマンドは以下のように実行します。

$ aapt l -a hoge.apk

すると、ダーっと色々な情報が出力され、その中にマニフェストの内容も含まれているので、それで内容を確認することが出来ます。

詳細はこちら

stackoverflow.com

参考

logcat コマンドライン ツール  |  Android Developers

docs.unity3d.com

maimai-jp.hatenablog.com

有用リンク

八分木(モートンオーダー)を使ってエリアを分割して処理負荷を軽減する

概要

今回の記事に関しては以下の記事をほぼそのまま参考にさせてもらっています。
実装自体はUnityで行い、コードもC#で作りましたがベースとなる理論は記事をそのまま参考にさせていただきました。
マルペケさんの記事には毎度本当にお世話になっています。

ここでは、そこで得た知識を「自分なりに」理解した内容をまとめて解説したいと思います。

ちなみに今回の記事を書くのに、Unityで実装したサンプルがあります。(サンプルプロジェクトはGithubに上げてあります

実行イメージは以下のようになります。


赤いラインがセルを表現していて、どの空間に所属しているかによって衝突可能性のあるオブジェクト同士をラインで結ぶというデモです。

参考にさせていただいた記事

そしてこれを使って実際にUnity上で動くサンプルも作ってみたので、興味がある方は見てみてください。
https://github.com/edom18/MortonOrder

ちなみにどんな内容かと言うと、八分木(Octree(オクトツリー))という概念を使って、3D空間を格子状に分割し、衝突判定などを効率的に行うための理論です。

Wikipeidaから引用させてもらうと以下のようなイメージです。

八分木(オクトツリー)とは

八分木(英: Octree)とは、木構造の一種で、各ノードに最大8個の子ノードがある。3次元空間を8つのオクタント(八分空間)に再帰的に分割する場合によく使われる。四分木を3次元に拡張したものと見ることができる。英語の名称は oct + tree に由来するが "octtree" とは書かず "octree" と書く。

Wikipediaから引用

図を見てもらうと分かりますが、ひとつのBoxが8つに分割され、さらにその分割されたうちのひとつのBoxがまた8つに分割されていく、という構図になっています。
そしてこれを理解する上で重要なポイントは、2進数で考えること。

8つなので3bit単位で分割されていくわけですね。
以下からの解説に関してはこのbitを意識して読んでもらうと分かりやすいかと思います。

※ ただし、今回の記事のほぼすべての解説は2D平面による解説(4分木)となっています。(なので2bit単位)
が、基本的にX,Y軸に加えてZ軸を追加するだけで、基本的な考え方はあまり違いはありません。

モートンオーダー(モートン順序)

これ、最初に知ったときは驚きました。
空間に登録するための判定処理が、まさかオーダーO(1)にまで縮小できるなんてと。
世の中にはほんとに頭のいい人がいるんだなーと思わされました。

2進数(2bit)で空間を分解していく

まずは以下の図を見てください。
4つごとにどんどん分割されていく状況を示しています。

じーっと図を見ていると、徐々になにかが見えてきます。
冒頭で話した通り、それは「2進数」です。

ひとつの空間を4つに分割する。つまり2進数で言うと2桁ですね。コンピュータなら2bit単位です。
そしてそれをひとつの単位として、さらにそれを分割する場合は、また2bitで分解します。

つまり、ひとつ下のレベルに分解するに従って末尾に2bitずつ追加されていく、と見ることもできます。

上の図をベースに説明すると、ルート空間は当然ながら「0」ですね。これは分割してないので当然です。
これをひとまず2bitを使って00と表現しておきます。

さてでは次に。これを4分割します。すると2bitなので2桁の2進数を末尾に追加します。
すると合計4桁になるので00 00となりますね。

そして下位2bitは当然、0〜3の値を持つことができます。まさに分割された空間のindexですね。
ではさらに続けて、それを分解してみましょう。すると、00 00 00と6桁になります。
末尾2桁は前述と同じく0〜3となります。

つまり、親空間を示すのが(上記の例で言えば)中央の2bitに当たります。
以後は、親→子→孫→ひ孫と分解レベルが上っていくにつれて末尾にたされる2bitもそれに応じて増えていくことになります。
しかし今見たように、基本的なルールはなにも変わりません。

試しに45番を例にしていましょう。

まず、孫での45番は一番右の図の位置になります。
そして左にいくに連れて親空間での位置になります。

45という数字を2bit単位に分解して考えると、確かにそれぞれの空間のindexが隠れていることが分かるかと思います。
(ルート空間は0なので省略)

前述の説明を借りるなら、親空間の2、つまり10を分解して2bitを末尾に足し、さらにそのindexである3、つまり11を追加。
さらにそれを分割して1(01)を末尾に追加し、これを10進数に戻せば45が出て来る、というわけですね。
こう考えるとなんとなく数値と分割の関連が見えてこないでしょうか。

裏を返せば、示された番号を2進数に分解して、かつ2bit単位で分けていくと各空間のindexが顔出す、というわけです。
別の言い方をするなら、2進数の概念を整理してうまく視覚化したもの、と見ることができるかもしれません。
最初にこれを見たときはまさにこの感覚を持ちました。

つまり、空間の通しindex番号をひとつ与えられただけで、そのオブジェクトがどの空間のどの位置にいるか、ただのビットシフトのみで計算できるというわけなのです。
計算量として表せばO(1)のオーダーとなります。なんとすばらしい! 真面目にどの位置にいるか線形検索していては到底たどり着けない高速さです。

座標位置から、所属する空間番号を割り出す

空間分割をモートンオーダーで行うと、すばらしく簡単に空間番号を割り出すことができることが分かりました。

では実際に利用するシーンを仮定して見てみましょう。
以下の図を見てください。

空間分割している意味は、そもそも動くオブジェクトとのあたり判定など「総当り」で調べることをせず、簡単に「近くの」オブジェクトを探すことが目的です。
なので「このオブジェクトはどこに属しているのか?」を知ったり、「この点の近くにあるオブジェクトは?」といったことにも答えられなければなりません。

しかしそれもとても簡単に達成することができます。
上記の図は、孫空間まで分割された状態(8x8=64分割)を示しています。

仮にルート空間の一辺の長さを100とした場合、孫空間での単位距離は8({=2^3})で割ることで求められます。
そして(例えばユーザがクリックした位置などとして)35, 58という座標が与えられたとしましょう。
これを、求めた単位距離で割ると2.8, 4.64となります。そしてこれをさらに端数切り捨てて2, 4にします。

これは、64分割された空間の左から2番目、上から4番目の位置であることを示しています。(indexなので0番始まりな点に注意)
つまり「36」の位置になります。

さて、今までずっと2進数で話をしてきたので、こちらも同じく2進数で見比べてみましょう。
すると、最初の2, 4010, 100となります。 そして「36」を2進数で表すと100100となります。

ちなみに上では3bit単位で表現していますが、これは空間の分割回数(空間レベル)からです。(冒頭で書いた2D = 2bit、3D = 3bitの意味ではありません)
今回の例では3回分割を行っているため3bit表現になっています。空間分割が2進数の視覚化と考えれば、分割数がそのままbitとして出現するのはイメージができるかと思います。

実はこれ、2bit単位で見たときにxの値(=2)を右のbit、yの値(=4)を左のbitとして合成すると、100100となるのです。

|_0|_1|_0| // xの値は2bit単位で区切った際の右bit
|1_|0_|0_| // yの値は2bit単位で区切った際の左bit
----------
 10 01 00

なんということでしょう。
xの値は右のbit、yの値は左のbitとして機能しているわけですね。
そしてこれは、これに限らずすべての空間について成り立ちます。

前述のように、この数値から孫空間だけでなく、子空間、親空間のどの位置か、までが一発で決まってしまいます。やってみましょう。
まず、100100を2bit単位に分解します。すると、10 01 00と分けることができます。

左から順に、「親空間」「子空間」「孫空間」の位置を表していたのでしたね。
親空間は10です。つまり、2番の位置にあることがわかります。図にすると以下ですね。

孫空間の36番は確かに「親空間」の2番の位置にあるのが確認できます。
では「子空間」ではどうでしょうか。

子空間の番号は01、つまり1ですね。1は右上です。図で言うと、

こちらも確かに1番の位置にありました。

最後は孫空間です。
孫空間は00ですね。つまり0、左上です。

こちらも確かに左上にありました。

以上のように、bit演算だけで、座標からびしっと空間を特定する方法、それが「モートンオーダー」です。
これを考えた人、ほんと天才だと思います。

以上を踏まえた上で、x,yの値から孫空間の位置を割り出す関数(bitシフト)は以下のようになります。

int BitSeparate(n)
{
    n = (n | n << 8) & 0x00ff00ff;
    n = (n | n << 4) & 0x0f0f0f0f;
    n = (n | n << 2) & 0x33333333;
    return (n | n << 1) & 0x55555555;
}

「オブジェクト」の所属空間を求める

さて、前述のように「点」がどの位置にあるかを求める方法が分かりました。
しかし、ほとんどの場合、オブジェクトは点ではなく、ある程度の大きさを持った「ボリューム」となります。

そしてそのサイズによっては孫空間には収まらず、「どの空間分割数が適切か」を判断しないとなりません。
2Dの場合、大きさを考慮するには左上と右下の値を採用し、いわゆるAABB(軸並行バウンディングボックス)で考えることで解決できます。

つまり、左上の点と右下の点ふたつの所属空間をまず求め、その後にそのサイズに応じてどの空間に属するかを判断します。
とはいえこれは簡単ではありません。― 普通に考えては。
これまたすごい発想(というかどうしたらそんな発想が出るのかと思ってしまいますが)を利用します。

参考にさせていただいた記事から引用させてもらうと、

上の例だと左上は19番、右下は31番に含まれています。ここからが面白いところで、色々と試行錯誤し、またJagoon様からのご指摘によって修正されたうれしい法則です。右下の空間番号31と左上空間番号19の排他的論理和を取ると12となります。この12を2進数で表現するとこうなります:

実は、境界図形の所属する分割レベルはこの排他的論理和の結果ビットが0じゃない最上位の区切りに表現されます。上の例だと青色で示した区切りが[11]となっています。所属空間は、上の例のように一番下の区切りを一つ上のレベル(ここでは子になります)、そこから親、ルートと空間レベルを上げていきます。[11]のビットはこの法則に従うと「親空間に所属」と判断されます。

とのこと。ほんとbit演算さまさまです。
サイズに応じてどの空間に属するか、ほぼO(1)で処理が済んでしまいます。

XORでなぜ所属空間が求まる?

このXORで出てくる理由。自分の理解を添えておくと、以下のようなイメージです。

各番号には所属親空間の情報が残っている。つまり、同じ親空間の情報はXORで取り除かれる。
結果として、違う親空間にいる場合はそれが「フラグ」として抽出される。

という感じです。
ここで「フラグ」と書いたのは、抽出した値自体に意味はなく、「どの位置のbitが立っているか」という、まさにフラグ的な利用をするからです。
その利用については後述します。

試しにひとつ例題をやってみましょう。

以下の図を見てください。

左上を32、右下を47とします。まず、図を見て答えを見つけてしまうと「親空間」の2に所属することが分かりますね。これを計算で求めてみましょう。
32^46 = 15となります。2進数にすると1111ですね。4分割なので00 11 11と3つ分で表します。(子空間から始めるので4-1 = 3
そして「ルート 親 子」のどこに属しているかは、bitが立っている位置を参考にします。

具体的には「どの位置のbitが立っているか」です。
上記の例で言うと、3つに分解した範囲で考えると、左から2つめ、および3つめにbitが立っていますね。
そしてbitが立っている部分の、一番左側を採用します。

「ルート/親/子」の3つとして考えると「親」の部分のbitが一番左側のbitとなります。
つまり所属空間は「親」ということになりますね。

こうして手作業で探すのは簡単ですが、プログラムでもそれほどむずかしくはありません。
2bit単位で見ているだけなので、最初の2bitをチェックして値が1以上かをチェックし、そうであった場合に空間レベルを上げていく、というふうに実装すればよいのです。

実際に今回これを実装した箇所は以下のようになります。
(ちなみに下のコードでは3Dに拡張しているため、3bitごとチェックしている点に注意してください)

int xor = ltd ^ rbd; // 2点の位置のXOR
int i = 0;
int shift = 0;
int spaceIndex = 0;

while (xor != 0)
{
    // 下位3bitずつマスクして値をチェックする
    if ((xor & 0x7) != 0)
    {
        // 空間シフト数を採用
        spaceIndex = (i + 1);
        shift = spaceIndex * 3;
    }

    // 3bitシフトさせて再チェック
    xor >>= 3;
    i++;
}

計算結果の下位3bitの値をチェックし、0以外=bitが立っているので、その場合はいったんその空間レベルを記憶しておきます。
そして計算結果を3bitシフトして再チェック。以後、値が0になるまでこれを繰り返し、最終的に得られた結果が空間レベルと、空間レベルを得るために必要なシフト数が得られる、というわけです。

さて、実際にこれを前述のルールの沿って見てみると、親空間のindexを得るには右4シフトすればいいことが分かります。
なぜか?

そもそも求めた番号には常に、その親に当たる空間のindexは含まれているのでしたね。
なので、「どの親に所属するか」さえわかれば、あとは数値をその親空間までシフトしてやれば自然とそのindexが姿を表す、というわけです。

実際にやってみましょう。
右下の数字47を右に4シフトすると(47 >> 4)答えは2です。
(ちなみに、どちらも同じ親に属しているので、32のほうを4bit分シフトしても同じ値が算出できます)

つまりまとめると「親空間の2に属する」となりました。

図で見ていた通りの結果になりましたね。すごい!

線形4分木でアクセスを高速化

前述の話は、すべてツリー状(木構造)での話でした。
しかしそれでは再帰的に調べていなかければならず、せっかく空間への登録・確認がO(1)にできたのに意味がなくなってしまいます。
これもO(1)で取れるようにしてみましょう。

今まで出てきたものを線形、つまりひとつの配列に収めてしまいます。

上図のように、線形配列に直したものを線形4分木(Liner Quaternary Tree)と呼びます。
線形の配列(リスト)にすることで、これまた各空間へのアクセスをO(1)にします。

ただ当然ですが、各分割レベルの最初のindexは0です。
そのまま分割空間レベルごとのindexを使うわけにはいきません。
以下のように通し番号として表現する必要があります。

図を見てもらうと分かりますが、各分割空間レベルの最初のindexはその前の空間レベルの分割数の合計を足した数になっているのが分かるかと思います。
例えばレベル2なら、その前にはルート空間で1、その下の空間で4、合計5個の要素があります。
なのでレベル2は5から始まっているわけですね。

そしてこれを計算するには「等比級数の和」を利用し、以下のように式で表すことができます。

\( 足す数 = \frac{4^L - 1}{4 - 1} = \frac{4^L - 1}{3} \)

今回の例では以下のように実装しました。

int ToLinearSpace(int mortonNumber, int level)
{
    int denom = _divisionNumber - 1;
    int additveNum = (int)((Mathf.Pow(_divisionNumber, level) - 1) / denom);
    return mortonNumber + additveNum;
}

さぁ、これで各オブジェクトの所属空間の検索、更新、登録、操作すべてがO(1)で行えるようになりました。

衝突判定について

衝突判定についても最適化の方法があります。
ただ、今回の記事はあくまで8分木の解説なので、その後のリスト生成などはしません。
参考にしたマルペケさんの記事ではそのあたりについても解説しているので、そちらを参考にしてみてください。
いちおうサンプルとして上げたほうはそれを元に、衝突判定のリストを生成するところまでも実装済みです。

ちなみに衝突判定以外にも、近傍のオブジェクトを取得する、など他にも色々と使いみちはありそうです。
その場合でも、空間へのアクセスがO(1)で行えるので、「近傍」を定義してその空間へアクセスすればすぐにその空間に所属しているオブジェクトのリストを得ることができると思います。

SkinnedMeshとBoneWeightについてメモ

概要

とある実装をしていて、アニメーション周りをわりと触ったのでそのメモです。
具体的には、メッシュカットを利用してメッシュを分断したあと、分断したメッシュもボーンアニメーションさせたくて実装したメモです。

実際に切断してアニメーションさせた動画↓

見てもらうと分かりますが、カットされて分断されても同じようにアニメーションしているのが分かるかと思います。

ちなみに、ボーンアニメーション(スキニング)については、前にWebGLで実装した際に解説した記事があるので、興味がある人は読んでみてください。

qiita.com

また、いつもお世話になっているマルペケさんのところの記事を参考にしたので、こちらのほうがもっと詳細です。

その61 完全ホワイトボックスなスキンメッシュアニメーションの解説

原理

スキニング自体の実装や概念については、上記の記事を参考にしてみてください。
ここでは、あくまでメッシュカットをしたときに実装した内容を元に、Unity上でどうしたらいいか、という視点から書いていきます。

とはいえ、簡単なボーンアニメーションの仕組みについて触れておきます。

ボーンアニメーションとは、ボーンと呼ばれる頂点群を定義し、そのボーンの動きに応じてポリゴンの各頂点が動かされる、という仕組みです。
では、どのボーンが動いたらどの頂点が動くのか。それを定義するのがBoneWeightです。

名前の通り、ボーンのウェイト、つまり「影響度」の値を保持します。
なので、メッシュは頂点数と同じだけのBoneWeight配列を保持しています。

BoneWeightは最大で4本までのボーンが設定できます。
ここで勘違いしないでもらいたいのは、モデル全体で4本だけ、ではなく、あくまで「1頂点に影響を与えることができるボーンは最大で4本」ということです。
これはマルペケさんの記事を見てもらうといいと思いますが、とにかくボーンの数を増やしてしまうとGPUで扱えるメモリの領域(レジスタ)がすぐに枯渇してしまうためです。

また、頂点に着目すれば、そもそも4本以上のボーンから影響を受けるケースというのは稀でしょう。
つまり、逆を言えば4本で十分とも言えます。

なのでBoneWeight構造体の定義を見てもらうと分かりますが、boneIndex0boneIndex3weight0weight3まで、配列ではなくそのままの名称で定義が書かれています。

ここで、boneIndexは、各ボーンに振られたインデックス番号、wegithは、そのボーンからどれくらいの影響を受けるかを示したものになっています。
なお、4本のボーンの影響度の合計は必ず1になるように正規化されます。

ボーンの簡単な説明は以上です。

今回はこのボーンの影響度を、メッシュカット後の各メッシュに適用し、それをアニメーションさせる、という実装を行いました。

ちなみに、メッシュカットについては以前、公開されていたコードを読んで解説した記事を書いたので、興味がある方はそちらも合わせてご覧ください。

qiita.com

登場人物

今回の実装にあたって、必要なクラスやプロパティなどがいくつか絡み合っているのでそれらを明確にします。

  • Mesh
  • SkinnedMeshRenderer
  • Animator
  • BoneWeight

Meshクラス

まずはMeshクラス。

Mesh mesh = new Mesh();
mesh.name = "Split Mesh";

// _cuttedMeshesは独自で定義したメッシュ情報を持つクラスの配列
mesh.vertices = _cuttedMeshes[i].Vertices;
mesh.triangles = _cuttedMeshes[i].Triangles;
mesh.normals = _cuttedMeshes[i].Normals;
mesh.uv = _cuttedMeshes[i].UVs;
mesh.subMeshCount = _cuttedMeshes[i].SubMeshCount;
for (int j = 0; j < _cuttedMeshes[i].SubMeshCount; j++)
{
    mesh.SetIndices(_cuttedMeshes[i].GetIndices(j), MeshTopology.Triangles, j);
}

mesh.bindposes = oriRenderer.sharedMesh.bindposes;
mesh.boneWeights = _cuttedMeshes[i].BoneWeights;

Meshはポリゴンを形成するために必要な情報をまとめて持っているクラスです。
verticestrianglesnormalsuvsubMeshCountsubMeshIndicesなどがそれに当たります。

今回はメッシュを平面で切って分割するため、新しく計算した頂点群などを再設定しています。

そしてさらに、メッシュは(前述のように)ボーンの影響度についても知らなければなりません。(アニメーションさせたい場合)
そこで設定しているのがboneWeightbindposeです。

boneWeightは上で書いた通り、各頂点が影響を受けるボーンの情報です。
そしてbindposeは、「モデルのデフォルト位置としてのボーンの姿勢」です。

人型のモデルであれば、Tポーズ時の位置、と考えるといいと思います。
つまり、「動いていない状態のボーンの位置」ということですね。

なぜこれを定義しているかというと、ボーンというのは「動いた差分分だけ、頂点に影響を与える」ようになっているからです。
つまり、ボーンがまったく動かされないならTポーズのまま、ということですね。

そしてそこから、ボーンが曲がったり移動したりすることで、モデルは様々な形に変形されます。
さらにそれを連続して行うことでアニメーションが成立している、というわけです。

SkinnedMeshRenderer

アニメーションするために必要なSkinnedMeshRenderer
ボーンに対応した頂点を、ボーンの動きに追従して動かすことでアニメーションを行います。

そしてSkinnedMeshRendererはその名の通り、スキニングされるメッシュを表示するためのクラスになります。
そのため、いくつかのボーンなどの情報を持たせる必要があります。

// objは新規生成されたGameObject
SkinnedMeshRenderer renderer = obj.GetComponent<SkinnedMeshRenderer>();
renderer.sharedMesh = mesh;
renderer.materials = mats;
renderer.bones = newBones;
renderer.rootBone = newRootBone;

メッシュは頂点群や、それらのボーンの影響度を持つ「データ構造」と言っていいでしょう。
そしてSkinnedMeshRendererは、このデータ構造を用いて適切にボーンの影響を頂点に与えます。まさにレンダラですね。

ボーンアニメーションに必要な情報はここではふたつ。
ひとつはbones、そしてもうひとつがrootBoneです。

rootBoneは、どのボーンがルートになっているのかを示す、Trasnformへの参照です。
そしてbonesは、定義されているボーンへの参照の配列になっています。

ちなみに、なにかしらのモデルデータを開いてみると分かると思いますが、ボーンとして利用されるオブジェクトのツリー構造は、必ずしもボーンだけとは限りません。
例えばなにかをグルーピングするための目的で配置されているオブジェクトなどもあるでしょう。

つまり、ルートボーン以下にはボーンとして機能していないオブジェクトも当然ながら存在します。
そのため、ボーンとしてアサインされたもののみをbones配列が持っている、というわけですね。

Animator

メッシュやレンダラの設定を適切にしても、アニメーション自体を再生しないことには動きません。
ということで、Animatorクラスが必要になります。

今回の実装では、メッシュカット対象オブジェクトが持っていたアニメーションのデータをそのままコピーして使っています。

Animator anim = newObj.AddComponent<Animator>();
anim.runtimeAnimatorController = _target.transform.root.GetComponent<Animator>().runtimeAnimatorController;
anim.avatar = _target.transform.root.GetComponent<Animator>().avatar;

AnimatorAddComponentして、適切にアニメーションに必要なデータを設定(コピー)します。

AnimatorAnimatorControllerについては、Unityでアニメーションさせたことがある人には特に説明の必要はないでしょう。
今回はコピーしていますが、切断後のアニメーションを変える場合は単なるコピーではなく、新しいコントローラを設定してもいいと思います。

そして最後にAvatarをコピーして終了です。

まとめ

今回はあくまでボーンをどうアサインしていったらいいかのメモなので以上となります。
まとめると、

  • メッシュに頂点情報およびボーンウェイト情報とボーンのデフォルト位置を紐付ける
  • SkinnedMeshRendererに、ルートボーンと、アニメーションに使われるボーンの配列を登録する
  • Animatorを通じてアニメーションを行い、AnimatorControllerのステートマシンを用いて各アニメーションを制御する

という流れになります。
データ構造的にはとてもシンプルですね。

次回の記事では、メッシュカットにボーンアニメーションを設定したあたりを書こうと思います。