1. 기술 분석
공간 분할은 지형을 일정크기로 나누어놓은 것을 말한다. 이 공간분할을 하는 이유는 카메라 시야 범위 내에 들어오지 않는 오브젝트나 지형을 제외시키기 위해서 사용한다. 지형 자체의 페이스가 많을 뿐더러 캐릭터 같은 경우도 시야 범위에 들어 오지 않을 경우 애니메이션을 처리할 필요가 없다.
카메라 프로스텀으로 제외 처리를 하고 있지만, 모든 오브젝트와 비교하는 것은 엄청난 연산 부하가 일어나기 때문에 공간을 분할하여 어느 공간이 카메라 프로스텀에 들어오는지 확인하는 것이 필수적으로 있어야 한다.
이러한 공간 분할 알고리즘을 사용하는데 주로 QuadTree, Octree, BSP(Binary Space Partitioning) 이 세 가지를 사용하며, 셋 다 트리 구조를 하고 있다.
1) Node
공간 분할에 사용되는 알고리즘들은 트리 구조이기 때문에 당연히 노드가 존재한다. 공간분할에서 사용하는 경우에는 노드가 공간을 가지고 있다.
RootNode는 분할할 공간의 전체 공간을 가지고 있다. 이 공간을 알고리즘에 따라서 자식 노드들은 부모의 공간을 나누어 가진다. 이는 재귀호출을 통해서 반복된다. 즉, 나누어진 노드의 자식 노드가 부모의 공간을 나누어 가지는 상황을 반복한다는 뜻이다. 다음 그림을 보면 쉽게 이해할 수 있을 것이다. 다음 그림은 QuadTree 기준으로 만들어졌다.
공간 분할이기 때문에 해당 노드에는 오브젝트들의 리스트와 해당 노드에 포함되는 지형의 버텍스들과 인덱스들을 가지고 있다.
2) QuadTree
Quad Tree는 높낮이의 차이가 크지 않으면서 맵이 넓은 지형에 적합한 알고리즘이다. 지형을 나누는 것도 2차원을 기준으로 나누어진다. 나누는 방식은 4개로 나누기 때문에 좌상, 우상, 좌하, 우하로 나눈다.
3) Mouse Picking
마우스 피킹은 스크린 공간의 마우스 좌표를 사용하여 클라이언트 공간에 렌더링되어 있는 3D오브젝트를 선택하거나 교점을 찾는 방법들을 말한다.
마우스 좌표를 월드 공간의 반직선으로 변환하여 오브젝트를 구성하는 충돌체나 삼각형과의 충돌 검사 및 교점을 찾는 방법을 사용한다.
- 화면 좌표계 -> 투영 좌표계
투영 좌표계로 옮기기 위해서는 먼저 화면 크기부터 얻어야 한다. 이 화면 크기로 해당 좌표를 0 ~ 1 사이의 좌표로 로 변환한 다음 -1 ~ +1 사이의 좌표로 바꿀 것이다. 투영 좌표계에서 스크린 좌표계로 변환하는 과정의 역순이라고 생각하면 된다.
S = 마우스로 선택한 스크린 좌표
Width = 화면 길이
Height = 화면 높이
위의 수식을 이용하면 투영 좌표로 변환할 수 있게 된다.
- 투영 좌표계 –> 뷰 좌표계
투영 좌표계에서 뷰 좌표계로 변환하는 제일 간단한 방법은 해당 좌표에 투영 행렬의 역행렬을 곱해주는 것이다. 하지만 여기서는 역행렬을 곱해주는 대신 다른 방법을 사용할 것이다.
p = 투영 행렬
우리가 가지고 있는 값은 x, y좌표 값 밖에 없으므로 투영행렬을 곱해줘도 x, y 값에만 영향을 받는다. 투영행렬에서 x,y 값에 영향을 주는 행렬의 요소는 P00, P11 밖에 없기 때문에 위의 식을 사용하면 연산량을 줄이면서 같은 결과를 얻을 수 있다.
- 뷰 좌표계 -> 월드 좌표계
월드 좌표계로 변환하는 것은 뷰 행렬의 역행렬을 곱해주면 된다. 만약 비교를 월드 좌표계가 아닌 로컬 좌표계로 하고 싶다면 해당 오브젝트의 월드 역행렬을 곱해주면 된다. 주의해야할 점은 월드 좌표로 옮기는 것이기 때문에 z 값이 1인 상태로 역행렬을 곱해주어야 한다. 그렇지 않으면 z값이 0으로 고정되어 버린다.
- 반직선과 삼각형 교점
한 삼각형의 교점을 찾기 위해서는 두 가지 과정이 필요하게 된다. 먼저 그 삼각형을 포함하는 평면과 교점을 찾은 다음에 면이 교점을 포함하는지 테스트를 해야한다. 평면 교점은 평면의 방정식을 통해 구할 수 있고, 교점 포함 테스트는 두 가지 방법이 존재한다.
첫번째로 외적을 사용하는 방법이다. 이는 삼각형 정점과 노말 벡터가 주어졌을 경우에 사용되는 방법이다. 이는 삼각형의 세 정점과 해당 교점을 외적한 후에 노말과 내적하여 교점 포함 여부를 확인한다. 전부다 양수로 나온다면 삼각형에 포함된 것이다.
두번째는 UV 매개변수를 사용하는 것이다. UV는 평면의 x, y값이라고 생각하면 된다. 이 u, v값으로 삼각형 내에 존재하는지 확인하는 것이다.
이렇게 구한 u,v 값이 삼각형에 포함되어 있다면, 각각 0보다 크거나 같아야하고 둘의 합은 1이 같거나 작아야한다.
평면의 교점과 교점 포함 테스트를 한번에 하는 방법이 있지만, 문서가 길어지기 때문에 생략하도록 하겠다.
4) Collision Dectection
Mouse Picking으로 만든 반직선으로 오브젝트들의 모든 삼각형과 비교하는 방법은 비용이 너무 비싸다. 그렇기 때문에 삼각형 대신에 물체와의 충돌로 처리하는 방법을 주로 사용하게 된다.
여기서 모든 물체와의 비교를 설명하는 것은 너무 많기 때문에 주로 쓴 기술인 OBB와 Ray와 충돌 처리를 설명하도록 하겠다.
- OBB, Ray 충돌 처리
평면과 OBB의 충돌 여부를 판단하는 방법을 그대로 사용되며, 여기에 분리축을 사용하는 것이 추가된다. 분리 축이란 충돌 대상 객체를 투영하는 축이다. 이 축을 이용해 반직선과 OBB사이에 분리 평면이 만들어지면 충돌하지 않게 된다.
2. 클래스 구조
1) Map
맵을 생성하고 관리하는 클래스.
(1) 변수
| 자료형 | 변수명 | 설명 |
| int | m_iSellNum | 셀 갯수 |
| int | m_iNumCols | 가로 타일 개수 |
| int | m_iNumRows | 세로 타일 개수 |
| int | m_iNumSellCols | 가로 셀 개수 |
| int | m_iNumSellRows | 세로 셀 개수 |
| float | m_fSellDistance | 셀 간의 길이 |
(2) 함수
- bool CreateVertexData()
버텍스데이터를 만드는 함수. 정점 개수(셀 개수)를 이용해 버텍스 데이터를 생성한다.
- bool CreateIndexData()
인덱스 데이터를 생성하는 함수.
2) QuadTree
QuadTree를 구현한 클래스이다.
(1) 변수
| 자료형 | 변수명 | 설명 |
| float | m_fWidth | 나눌 공간의 길이 |
| float | m_fHeight | 나눌 공간의 높이 |
| float | m_fMinDivideSize | 나눈 공간의 최소 길이(높이) |
| int | m_iNumDepth | 깊이 |
| int | m_iRenderDepth | 렌더를 깊이 단위로 제한하기위한 변수 |
| int | m_iMaxDepthLimit | 최대 깊이 |
| SNode* | m_pRootNode | 부모 노드 |
(2) 함수
- bool BuildTree(SNode* pNode)
트리를 생성하기 위한 재귀 함수. 간단한 코드이므로 코드를 첨부했다.
- bool SubDivide(SNode* pNode)
공간을 분할한 후에 자식 노드를 생성하는 함수. 최대 깊이나, 노드가 가지고 있는 반지름 길이에 따라서 리프노드인지 판단한다. 리프노드가 아니면 자식 노드들을 생성한다.
3) SSelect
마우스 피킹을 담당하는 클래스이다. 반직선과 삼각형의 교점을 찾는 것 외에도 반직선과 물체의 충돌도 담당하고 있다.
(1) 변수
| 자료형 | 변수명 | 설명 |
| D3DXVECTOR3 | vIntersection | 해당 교점 |
| D3DXMATRIX | m_matWorld | 교점을 찾기 위한 월드 행렬 |
| D3DXMATRIX | m_matView | 뷰 행렬 |
| D3DXMATRIX | m_matProj | 투영행렬 |
| DWORD | m_dwClientWidth | 클라이언트 길이 |
| DWORD | m_dwClientHeight | 클라이언트 높이 |
(2) 함수
- void Update()
매 프레임마다 호출되는 함수. 이전 뷰 행렬과 투영행렬을 통해 마우스가 있던 위치를 월드 좌표계로 변환시킨다. 그 과정은 위에 설명했으므로 과정 설명은 생략한다.
- bool ChkOBBToRay(S_BOX* pBox, S_RAY* pRay)
반직선과 OBB 충돌 체크하는 함수. 두번째 인자가 NULL일 경우 Update()호출되어 만들어진 vIntersection를 사용한다.
3. 추가 / 변경 사항
1) 디버깅
충돌처리가 제대로 되어있는지 확인하기 위한 기능이 필요하다. 그러기 위해서 다음과 같은 함수를 만들었다.
- void FindNodeTile()
FindNodeTile은 마우스 피킹이 되는 타일을 보여주는 함수이다. 원리는 마우스 피킹에 사용되는 반직선과 타일마다 가지고 있는 OBB 박스와 충돌체크를 한 후 해당 노드에 표시를 하는 것이다.
'DirectX11' 카테고리의 다른 글
| 스키닝 애니메이션 (0) | 2021.11.02 |
|---|---|
| 3ds Max SDK Export(Object Animation) -2- (0) | 2019.10.31 |
| 3ds Max SDK Export(Object Animation) -1- (0) | 2019.10.31 |
| DirectX11의 객체들이 제대로 Release 했는지 확인하는 방법(DirectX11의 Debugging) (0) | 2019.10.31 |
| 2DLibrary 정리 1차 (0) | 2019.10.31 |
