쿼드트리

쿼드트리란?

2차원 공간을 재귀적으로 네 영역으로 분할하여 관리하는 계층적 자료구조

1 . 최대 깊이
2. 객체가 네 자식영역 중 하나에 완전히 포함되는지 확인
3. 포함되면 해당 영역을 또 분할하고 객체를 자식 노드로 내려보냄
4. 여러 자식 영역에 걸쳐있음녀 객체를 현재 노드에 저장
더이상 분할하지 못하면 멈춤

쿼드 트리의 주요 연산

• 삽입
• 삭제
• 범위 검색
  • 검색 영역하고 충돌할 노드들만 충돌판정 진행
  • 멀리 떨어져있는 애들은 검사할 필요없으니
  • 겹치는 노드들만 충돌 판정하거나 범위 검색
    검사를 줄이는데 사용한다
    영역을 다룰때 최적화를 하는것.
    필터링하려고

최적화에대해 알아두라, 많은 계산을 해야하는데 계산을 줄이거나 건너뛰는 방법이 최적화

쿼드트리 특징

• 각 노드는 하나의 사각형 영역을 담당
• 노드를 분할하면 네 개의 자식노드가 생성(균등 분할)
• 데이터가 필요한 영역만 더 깊게 분할 가능
• 최대 깊이, 최소 영역 크기, 노드당 객체 수 등으로 분할 제한함
• 여러 사분면에 걸친 객체를 어느 노드에 저장할지 규칙 필요
  • 사분면에 포함되어있는지 보고 걸처져있다면 많이 걸쳐져있는 노드에 저장하는게 일반적 (방법은 여러가지)
• 객체의 이동이 많으면 위치 변경에 따른 제거와 재삽입 비용이 발생
  • 충돌처리 쪽에서 최적화 목적으로 사용하는게 좋음

쿼드트리 장단점

장점

• 검색 영역과 무간한 공간 제외
• 가까운 객체나 특정 범위의 객체 찾을때 활용
• 모든 객체를 직접 비교하는 횟수 줄임
• 공간 밀도에 따라 필요한 영역 세분화

단점

• 객체가 특정 영역에 몰리면 한쪽 가지가 깊어짐 (순차탐색과 별반 다를게 없을 수 있음, 쿼드트리가 항상 최적화는 아님)
• 트리 노드가 객체 목록을 저장할 추가 메모리 필요
• 움직이는 객체가 많으면 제거와 재삽입 비용이 증가, 움직이는 물체, 움직이지 않는 물체 따로 구분
• 객체가 넓거나 여러 영역에 걸치면 공간 분할의 효과가 줄음

*오브젝트 풀링?

활용

• 충돌 검사 후보 검색
• 카메라 영역
• 주변 객체 검색
• 지형과 LOD 관리

다른 공간 분할 구조와 관계

• 쿼드트리 : 2차원 공간을 네 영역으로 분할
• 옥트리 : 3차원 공간을 여덞 영역으로 분할
• BSP 트리 : 하나의 선이나 평면을 기준으로 두 공간으로 분할

사용 전 확인할 점

1. 관리 공간이 2차원인지
2. 객체가 특정 영역에서 비교적 고르게 분포하는지
3. 영역 검색을 반복해서 수행하는지
4. 객체가 얼마나 자주 이동하는지
5. 여러 사분면에 걸치는 큰 객체가 얼마나 많은지
6. 트리 관리 비용보다 줄어드는 검사 비용이 더 큰지

구현 방법

쿼드트리 구성요소

• 노드가 담당하는 사각형 영역 (Bounds)
• 현재 노드에 저장된 객체 목록
• 네 개의 자식 노드
• 현재 깊이 (depth)
• 최대 깊이 (MaxDepth)

Bounds 클래스

사각형 영역의 시작 위치와 크기를 저장

• 점이 영역 안에 있는지 확인
• 객체의 전체 영역이 현재 영역 안에 포함되는지 확인
• 두 사각형 영역이 서로 겹치는지 확인

x <= pointX < x + width
y <= pointY < y + height

서로 최대값, 최소가 겹치는 구간이 있다. 겹치는 구간에 점이 들어갈 수도있음
그 위치처리하기위에 위처럼
보통 한쪽만 처리, 한쪽은 포함, 한쪽은 미포함

반개구간(구간의 양 끝 가운데 하나는 포함하고 다른 하나는 포함하지 않음)

지형과 LOD 관리 (unreal에서...)

https://dev.epicgames.com/documentation/unreal-engine/water-meshing-system-and-surface-rendering-in-unreal-engine

• 참고
  • 면이있므면, 다시 다눠주는게 테셀레이션, 면쪽에 주는 기법
  • 각 정점의 높이가 다를 때 차이가 남