인프런 커뮤니티 질문&답변
작성한 질문수
쿼드트리 구현 강의자료에 포함된 LQNode의 GetQuads함수에 궁금한 점이 있습니다.
작성
·
240
·
수정됨
0
LooseQuadTree의 Query함수 호출 시 겹칠 가능성이 있는 모든 LQNode를 수집할 때 일부 결과가 누락된 것으로 판단되어서 문의합니다.
강의 자료의 Query함수의 기능이 틀린 내용인지, 아래 내용이 옳은지 그리고 더 최적화된 로직이 있는지 궁금합니다.
public LQNode(LQuadtree tree, LQNode parent, Bounds bounds, int depth)
{
_tree = tree;
_parent = parent;
_bounds = bounds;
_looseBounds = new Bounds(bounds.center, bounds.size * tree._constantK);
_depth = depth;
}
private List<LQNodeIndex> GetQuads(Bounds bounds)
{
List<LQNodeIndex> quads = new List<LQNodeIndex>();
if (_children[(int)LQNodeIndex.UPPERLEFT]._looseBounds.Intersects(bounds))
{
quads.Add(LQNodeIndex.UPPERLEFT);
}
if (_children[(int)LQNodeIndex.UPPERRIGHT]._looseBounds.Intersects(bounds))
{
quads.Add(LQNodeIndex.UPPERRIGHT);
}
if (_children[(int)LQNodeIndex.LOWERRIGHT]._looseBounds.Intersects(bounds))
{
quads.Add(LQNodeIndex.LOWERRIGHT);
}
if (_children[(int)LQNodeIndex.LOWERLEFT]._looseBounds.Intersects(bounds))
{
quads.Add(LQNodeIndex.LOWERLEFT);
}
return quads;
}
답변 2
0
안녕하세요 답신이 늦었습니다.
강의를 제작할 때 느슨한 쿼드트리의 depth를 잘못 계산했습니다. 최종 코드에서 이를 반영해 정정했는데, 영상에서는 이를 반영할 수 없어 노트로만 수정사항을 정리했습니다.
( 관련 링크 : https://www.inflearn.com/questions/1114256 )
이 수정사항을 반영해도 문제가 발생하는지요?
안녕하세요.
말씀주신 부분에 대한 예외를 처리하지 못했네요. 이 부분을 수정한 코드를 다시 올렸습니다.
보완한 코드는 다음과 같습니다.
1. 생성자에서 바운드볼륨의 사이즈를 늘려줍니다.
public LQNode(LQuadtree tree, LQNode parent, Bounds bounds, int depth)
{
_tree = tree;
_parent = parent;
_bounds = bounds;
_depth = depth;
_bounds.size *= _tree._constantK;
}검사할 때 영역을 검사하지 않고 실제 자식 노드의 바운딩 볼륨과 검사해야 합니다. 그래서 구조를 조금 변경했습니다.
public void Query(BoxCollider item, List<LQNode> possibleNodes) { possibleNodes.Add(this); if (IsSplitted) { List<LQNode> quads = GetQuads(item.bounds); foreach (var quad in quads) { quad.Query(item, possibleNodes); } } } private List<LQNode> GetQuads(Bounds bounds) { List<LQNode> quads = new List<LQNode>(); foreach (var child in _children) { if(child._bounds.Intersects(bounds)) { quads.Add(child); } } return quads; }
트리에 속한 아이템의 분포가 크기에 따라 골고루 되지만 검색량이 늘어나므로, 항상 LQ가 좋은 것은 아니지만, 그래도 최적화를 위한 다양한 옵션 중 하나로 생각하시면 될 것 같습니다.
public LQNode(LQuadtree tree, LQNode parent, Bounds bounds, int depth)
{
_tree = tree;
_parent = parent;
_bounds = bounds;
_depth = depth;
_bounds.size *= _tree._constantK;
}이걸 쓰면 Root node도 범위가 커져서 64*64 가 아니고 128*128이 되지 않나요???
안녕하세요. 답신이 늦었습니다.
기존 노드 영역을 표시할 때 사용하는 bounds에 물체 영역과의 충돌을 검색하기 위해 루즈 영역을 관리하는 _qbounds 멤버 변수를 추가해 구현했습니다.
다음과 같이 간신히 걸치는 물체도 탐지합니다. 
5강 자료 파일에 올렸으니 참고해주시면 되겠습니다.
0
안녕하세요, 인프런 AI 인턴입니다.
gewdox님, 문의 주신 내용을 바탕으로 쿼드트리 구현과 관련하여 GETQuads 함수에 대해 설명드리겠습니다.
코드에서 GetQuads 함수는 주어진 bounds와 자식 노드들의 _looseBounds가 교차하는지를 검사하여, 교차하는 모든 자식 노드들의 인덱스를 수집합니다. 이러한 방식은 LooseQuadTree가 원하는 범위 내의 객체를 찾기 위해 각 노드가 관심 영역과 겹치는지를 판단하는 과정에 사용됩니다.
제공하신 코드는 이미 최적화된 로직의 좋은 예로 보입니다. 여러 자식 노드들과 주어진 bounds가 겹치는지 각각 확인하여 겹치는 노드의 인덱스를 리스트에 추가하는 것은, 관련 객체들을 효율적으로 찾기 위한 과정에서 매우 중요합니다.
문의하신 내용을 바탕으로 최적화에 대해 더 궁금하시면, 구체적인 성능 요구 사항이나 문제 상황에 맞춰 추가적인 설명을 드릴 수 있습니다. 영역 검사 과정에서 최적화할 수 있는 부분이 있다면, 그것은 특정 상황에서의 공간 복잡도나 시간 복잡도를 고려하여 결정됩니다.
겹칠 가능성이 있는 모든 LQNode를 수집할 때 누락되는 결과가 있다면, 확인해봐야 할 부분은 _looseBounds.Intersects(bounds) 메서드의 정확성입니다. 또한, 실제 겹치는 객체들이 올바르게 인식되지 않는 경우, _looseBounds의 정의 및 생성 방식에서부터 검토하는 것이 좋습니다.
각 노드의 영역(_looseBounds)을 계산하고 이러한 영역들이 주어진 bounds와 올바르게 교차하는지를 확인하는 로직은 쿼드트리의 성능과 직결되므로, 구현하신 내용이 이미 적절한 접근 방식을 따르고 있다고 생각합니다.
위 코드 수정으로는 사분면 경계에 걸쳐진 일부 영역에서는 여전히 검출 누락이 발생합니다.
LooseQuadtreeQuery씬에서
InsertObjects/Insert24 오브젝트에 대해 QueryObjects/Query1의 위치를 옮기면서 실행해본 결과입니다.
순회할 자식 노드를 검사할 때
일반적인 쿼드트리라면, 해당 노드의 Center위치에 자식 노드의 중심에 가까운 꼭지점들이 합쳐져서 하나만으로 검출이 가능하지만,
K값을 곱해서 영역이 늘어나면 자식 노드의 각 꼭지점은 모두 달라지게 되는데,
해당 예제에서는 QNode와 LQNode의 GetQuads함수 내용이 같아 로직의 오류가 의심됩니다.