개요

전에 살펴본 KD트리의 이해를 바탕으로 Unity 엔진을 통해 KD 트리를 구현한다.

전체 구조

KdtreeManager.cs

KNode.cs

using System.Collections.Generic;
using System.Linq;
using UnityEditor;
using UnityEditor.Experimental.GraphView;
using UnityEditor.UIElements;
using UnityEngine;

public class KNode
{
		//생성자 - KD 트리 노드를 생성할 떄 필요한 정보 할당
    public KNode(int dimension, KNode parent, Transform transform, int depth)
    {
        _dimension = dimension; //차원
        _depth = depth;//현재 노드 깊이
        _transform = transform; // Unity 오브젝트 위치 정보
        _parent = parent; // 상위 노드
    }

    private Transform _transform; //오브젝트 위치 좌표
    private int _depth = 0; // 노드의 깊이
    private int _dimension = 2; //전체 차원 수(기본 2D)
    private KNode _parent; // 상위 노드
    private KNode _left = null; //왼쪽 자식
    private KNode _right = null; //오른쪽 자식
	
		//분할 훅을 기준으로 KD 트리 시각화 영역을 그리는 함수
    public void DrawSplitPlane(Bounds drawArea)
    {
        Bounds[] splittedBounds = new Bounds[2];

        Vector3 planeCenter = drawArea.center;
        planeCenter[_depth % _dimension] = KdValue;
        Vector3 planeSize = drawArea.size;
        planeSize[_depth % _dimension] = 0.0f;

        // 왼쪽 노드의 AABB 영역
        Vector3 leftMin = drawArea.min;
        Vector3 leftMax = drawArea.max;
        leftMax[_depth % _dimension] = KdValue;
        splittedBounds[0].min = leftMin;
        splittedBounds[0].max = leftMax;

        // 오른쪽 노드의 AABB 영역
        Vector3 rightMin = drawArea.min;
        rightMin[_depth % _dimension] = KdValue;
        Vector3 rightMax = drawArea.max;
        splittedBounds[1].min = rightMin;
        splittedBounds[1].max = rightMax;

        Gizmos.color = Color.gray;
        Gizmos.DrawWireCube(planeCenter, planeSize);
        Gizmos.color = Color.white;
        Gizmos.DrawCube(Transform.position, Vector3.one);

        if (!IsLeftOpen)
        {
            _left.DrawSplitPlane(splittedBounds[0]);
        }

        if (!IsRightOpen)
        {
            _right.DrawSplitPlane(splittedBounds[1]);
        }
    }
		
		//KD 트리에서 최근접 이웃 탐색의 핵심 메소드
		//testTransform : 기준이 되는 타겟 위치
		//nearestNode : 지금까지 찾은 노드
		//searchedNode : 방문한 노드 리스트
    public KNode CheckNearestNode(Transform testTransform, KNode nearestNode, List<KNode> searchedNode)
    {
        searchedNode.Add(this); // 방문한 노드 정보
				
				
				//현재까지의 최단 거리와 현재 노드와의 거리 계산
        KNode nearestNodeSoFar = nearestNode;
        
        //현재까지 찾은 노드와 타겟 간 제곱 거리
        float nearestSqrDistance = nearestNodeSoFar.SquaredDistanceTo(testTransform.position);
        
        //현재 노드와 타겟 간 거리
        float sqrDistanceToNode = SquaredDistanceTo(testTransform.position);
        
        //현재 노드가 더 가까운 경우에
        if (sqrDistanceToNode < nearestSqrDistance)
        {
            nearestSqrDistance = sqrDistanceToNode; //최근접 후보 업데이트

            if (IsLeaf) // 만일 현재 노드가 리프노드라면
            {
                return this; // 즉시 반환
            }
            else
            {
                nearestNodeSoFar = this; //리프 노드가 아니면 후보만 갱신하고 하위 탐색 진행
            }
        }
				
				//분할축과의 거리 계산
				//KdValue :  현재 노드의 분할축 기준 값
				//testtransform.GetKdValue() 타겟의 동일 축 좌표
				//distanceToSplitAxis : 현재 노드의 분할선과 타겟 점 거리 
        float distanceToSplitAxis = KdValue - testTransform.GetKdValue(_dimension, _depth);
        float sqrDistanceToSplitAxis = distanceToSplitAxis * distanceToSplitAxis;
				
				//타겟이 분할축 기준보다 작으면
        if (testTransform.GetKdValue(_dimension, _depth) < KdValue)
        {
		        //왼쪽 서브트리부터 검색하되, 왼쫏 서브트리가 존재할 경우 탐색
            if(!IsLeftOpen)
            {
		            //재귀 호출 ChecjNearestNode()로 왼쪽 서브트리 탐색
                nearestNodeSoFar = _left.CheckNearestNode(testTransform, nearestNodeSoFar, searchedNode);
                //탐색 결과가 더 가까울 수 있으므로 최근접 거리 갱신
                nearestSqrDistance = nearestNodeSoFar.SquaredDistanceTo(testTransform.position);
            }
						//가지치기 판단 -> 오른쪽 노드가 존재하고 분할선과 타겟의 거리가 현재 최단 거리인 경우에만
            if (!IsRightOpen && (sqrDistanceToSplitAxis < nearestSqrDistance))
            {
                nearestNodeSoFar = _right.CheckNearestNode(testTransform, nearestNodeSoFar, searchedNode);
            }
        }
        else //타겟이 분할축 기준보다 크거나 같다면
        {
		        //오른쪽 서브트리부터 검색하되, 존재한다면.
            if (!IsRightOpen)
            {
                nearestNodeSoFar = _right.CheckNearestNode(testTransform, nearestNodeSoFar, searchedNode);
                nearestSqrDistance = nearestNodeSoFar.SquaredDistanceTo(testTransform.position);
            }
            
						//가지치기 판단
            if (!IsLeftOpen && (sqrDistanceToSplitAxis < nearestSqrDistance))
            {
                nearestNodeSoFar = _left.CheckNearestNode(testTransform, nearestNodeSoFar, searchedNode);
            }
        }
				
				//현재 탐색 범위 내에서 최종 최근접 노드 반환
        return nearestNodeSoFar;
    }

    public bool IsLeaf
    {
        get { return (_left == null && _right == null) ? true : false; }
    }
    
    public KNode Left
    {
        get { return _left; }
        set { _left = value; }
    }

    public KNode Right
    {
        get { return _right; }
        set { _right = value; }
    }

    public bool IsLeftOpen
    {
        get { return _left == null; }
    }

    public bool IsRightOpen
    {
        get { return _right == null; }
    }

    public Transform Transform
    {
        get { return _transform; }
    }

    public float KdValue
    {
        get { return _transform.GetKdValue(_dimension, _depth); }
    }

    // 계산 성능을 위해 제곱근을 씌우지 않음
    public float SquaredDistanceTo(Vector3 targetPosition)
    {        
        return (targetPosition - Transform.position).sqrMagnitude;
    }

    public float DistanceTo(Vector3 targetPosition)
    {
        return Vector3.Distance(targetPosition, Transform.position);
    }

}

float distanceToSplitAxis = KdValue - testTransform.GetKdValue(_dimension, _depth);
float sqrDistanceToSplitAxis = distanceToSplitAxis * distanceToSplitAxis;

최근접 이웃을 탐색하는 메소드 CheckNearestNode() 내부에 위 코드에서

distanceToSplitAxis 에 현재 노드의 분할 축 기준 위치와 타겟 점의 동일 축 값의 차이를 계산하여

분할선과 타겟 점 사이의 거리를 구한다.

이 거리는 탐색된 최근전 거리보다 가까운지 판단하는 기준이 되며,

만일 이 거리보다 이미 찾은 노드가 더 가깝다면?

반대편 서브트리는 볼 필요가 없어진다. → 가지치기

여기서 가지치기의 조건이 필요하다