오늘은 쿼드 트리 & 옥 트리 에 대해 공부하도록 하겠습니다.
1. 트리란?
나무를 거꾸로 놓아듯한 자료구조이다.
대표적인 비선형 자료구조의 하나로 이진 트리 즉 트리의 데이터가 완전이진트리가 되면 탐색 시간이 매우 감소한다.
트리의 대표적인 특성으로는
- 최소 1개 이하의 부모노드를 가지고 있다.(루트 노드는 부모가 없다)
- 1개의 노드가 여러개의 자식을 가질수 있다.(리프 노드는 자식이 없다) (리프 노드란 : 맨 끝에 있는 노드)
- 대표적인 비선형 자료구조
- 선형 : 리스트, 배열, 원형 큐 등
- 비선형 : 트리, 그래프
트리에는 이진 트리, 비 이진 트리가있다.
이진 트리에는 이진 탐색 트리, 레드 블랙 트리가 있으며 비 이진 트리에는 쿼드트리, 옥트리 등이 있다.
2 쿼드 트리란?
사진 분할 트리라 하며 노드가 자식을 4개씩 가질수있는 트리 이다.
탐색을 이진 트리와 비교를 하면
| 이진 트리 | 쿼드 트리 |
| 레벨에 자식들 두개 중 하나의 노드를 선택 | 레벨에 자식들 네개 중 하나의 노드를 선택한다. |
| 쿼드트리는 이진트리의 비해 개체가 2배가 많다. |
쿼드트리는 평면의 적당하다.
3 옥 트리란?
팔진 분할 트리라고 하며 8개의 자식을 가질수 있습니다.
옥트리는 공간에서 많이 활용합니다.
3 활용
지형의 렌더링을 하기 위해 보통 전체 렌더링 정보를 단일 버퍼 안에 넣습니다.
이것은 분명 매우 비효율적인 성능을 보이게 될것입니다.
그러므로 쿼드트리를 이용하여 지형을 쪼개고 쪼개서 더이상 쪼개지 못하는 곳으로 쪼개서 버퍼에 담아서 보냅니다.
그러면 GPU는 작은 이 지형정보를 더욱 빠르게 계산할수 있으며 특정 지형의 정보를 빠르게 얻을 수 있습니다.
옥트리도 마찬가지로 쪼개고 쪼개서 얻는 정보를 빠르게 얻을수 있습니다.
단지 차이점이라면 쿼드트리는 평면에 매우 효과적이며 옥트리는 3D환경에서 많이 사용된다고 합니다.
이런 식으로 프리스텀 컬링에서도 많이 표현이 된다고 합니다.
대부분 컬링때문에 사용하는 경우가 많은거 같습니다.
'개발자 면접 공부 > 그래픽스' 카테고리의 다른 글
| 벡터의 내적으로 라디안 및 디그리 구하기 (0) | 2023.09.29 |
|---|---|
| IK 와 FK의 차이점 (0) | 2023.05.11 |
| 퐁 모델 (2) | 2022.09.13 |
| 쉐이더란? (사용 이유) (0) | 2022.09.04 |
| 벡터 외적을 통한 적이 오른쪽 왼쪽 판별 (0) | 2022.08.03 |