Help us understand the problem. What is going on with this article?

空間分割をしてみる

More than 1 year has passed since last update.

はじめに

可視判定や衝突判定のブロードフェーズ等でBSPを試したいので簡単なサンプルを作りました。
このサンプルでは空間分割の簡単なテストだけで、大量のオブジェクトを管理していません。分割も単純なものです。

今回のコードを下記に置きました。
https://github.com/jnhtt/EasySpatialPartioningSample

bsp01.gif

超平面で空間を分割

平面で空間を2つに分割します。
ある点が平面の表と裏のどちらにあるかを知りたい場合、点と平面の符号付き距離を求めることで表と裏のどちらにあるか分かります。

平面の裏表 符号付き距離
正(+)
負(-)
平面上 零(0)
Plane.cs
using UnityEngine;

namespace Utils
{
    public class Plane
    {
        public Vector3 Normal { get; private set; }
        public float Distance { get; private set; }

        public Plane(Vector3 n, float d)
        {
            Normal = n;
            Distance = d;
        }

        // 符号付き距離が正になる半空間に、点があるかどうか
        public bool IsPositive(Vector3 pos, bool includeZeroFlag = true)
        {
            float distance = Vector3.Dot(pos, Normal) - Distance;

            return includeZeroFlag ? 0f <= distance : 0f < distance;
        }
    }
}

バイナリ空間分割

ノードの親子で空間を分割します。子ノードほど小さな空間になります。

メンバ 説明
positive BSPNode plane平面で分割した時の正の空間がぶら下がるノード
negative BSPNode plane平面で分割した時の負の空間がぶら下がるノード
plane Plane 空間を分割する平面
exec Action 葉ノードに到達したら実行する処理
Node.cs
using System;
using System.Collections;
using System.Collections.Generic;
using UnityEngine;

namespace Utils
{
    public interface INode
    {
        void Execute();
        INode GetNext(Vector3 pos);
        bool IsLeaf();
    }

    public class BSPNode : INode
    {
        protected BSPNode positive;
        protected BSPNode negative;
        protected Plane plane;
        protected Action exec;

        public static BSPNode CreateLeaf(Action exec)
        {
            return new BSPNode(null, null, null, exec);
        }

        public BSPNode(Plane plane, BSPNode posi, BSPNode nega, Action exec)
        {
            this.plane = plane;
            this.positive = posi;
            this.negative = nega;
            this.exec = exec;
        }

        public INode GetNext(Vector3 pos)
        {
            if (plane.IsPositive(pos)) {
                return positive;
            } else {
                return negative;
            }
        }

        public void Execute()
        {
            if (exec != null) {
                exec();
            }
        }

        public bool IsLeaf()
        {
            return positive == null && negative == null;
        }
    }
}

手動で簡単に空間を分割します。
全空間AをYZ平面(x=0)で分割して、半空間BとCに分けます。
 半空間BとCをそれぞれ、XZ平面(y=0)で分割して半空間Bから半空間DとEが、半空間Cを分割して半空間FとGができます。
これらの空間をBSPNodeでBSP-Treeを構築します。

bsp.png

Main.cs
private void BuildTree()
{
    root = new Utils.BSPNode(
        new Utils.Plane(Vector3.right, 0f),
        new Utils.BSPNode(
            new Utils.Plane(Vector3.up, 0f),
            Utils.BSPNode.CreateLeaf(ChangeColorRed),
            Utils.BSPNode.CreateLeaf(ChangeColorBlue),
            null
            ),
        new Utils.BSPNode(
            new Utils.Plane(Vector3.up, 0f),
            Utils.BSPNode.CreateLeaf(ChangeColorGreen),
            Utils.BSPNode.CreateLeaf(ChangeColorYellow),
            null
            ),
        null
    );
}

さいごに

なんとなく空間分割ができたのでは。。。と思います。
木構造の構築は、プログラムで行いたかったですが、今回は手動で行いました。
ゲームだと均一な格子を配列で管理した方が分かりやすいような気がしました。その方が、近傍格子へのアクセスも楽だと思います。

木構造を使いたい場合は、kd-treeの方が構築が楽そう。
設計された静的な空間の場合は、分割を事前計算してファイルに保存するのが良いかもしれません。

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした