[Q] 쿼드트리나 옥트리에서 leaf node에 들어가는 실제 폴리곤

2D, 3D, 다각형, 픽셀 등 게임의 그래픽 프로그래밍에 관한 포럼입니다.

Moderator: 류광

Locked
착실이
Posts: 77
Joined: 2002-11-29 11:12

[Q] 쿼드트리나 옥트리에서 leaf node에 들어가는 실제 폴리곤

Post by 착실이 »

대부분 인터넷이나 책에 나와있는 옥트리나 쿼드트리를 이용한 공간분할은

정방형 또는 격자형 폴리곤만을 데이터로 다루는데,

정방형 이나 격자형 이 아닌 비정형 폴리곤들로 이루어진 3D 데이터와 object들을 관리하는 방법에 대한

설명은 터무니 없이 부족하고, 몇줄의 문장으로 설명이 끝이 나버리더 군요...

노드가 중복되게 삼각형을 가지게 하고, 이 중복된 삼각형을 적절하게 처리해야 한다는게 대부분의 공통된 설명

인데 이에 대한 자세한 설명이 아쉽더군요...

그래서 이렇게 이런 고민을 겪으셨던 분이 계시면 약간의 조언을 부탁드리겠습니다.
ekflame
Posts: 93
Joined: 2003-11-27 22:26

Post by ekflame »

음.. 크게 두가지 방법이 있는듯 합니다.

1. 옥트리의 노드에 맞게 폴리곤을 재분배(분활)하는 방법.
2. 분리하지 않고 느슨한 옥트리 등으로 오브젝터를 나누지 않는 방법.

2번의 경우.. 장면상의 오브젝터라면 별 문제가 없겠지만 길다란 오브젝터
처럼 느슨한 옥트리로 처리하기 힘들거나 처리한다고 해도 그 효율이 지극
히 떨어지는 경우는 적합하지 않겠죠..

결국 맵의 경우 1번을 쓰야하는데 여기에도 크게 두가지 방법이 있는듯합니다.
1-1. 폴리곤(삼각형) 단위로 처리한다.
1-2. 오브젝터단위로 처리하되 리프노드의 경계선을 가로지르는 경우
삼각형을 분할해서 오브젝터를 둘 이상으로 나눈다.

1-1 의 방법의 경우 책에서는 플래그를 두어서 한번 그렸던건 건너뛴다
등으로 설명하고 있는데.. 그래픽가속을 중요시 하는 현재로 볼때 그리
좋은 방법은 아닐듯 합니다(지극히 개인적인 생각). 왠만해서는
drawprimitive 호출 횟수를 줄이는 것이 훨씬 효율이 좋더군요..

1-2. 의 방법은 말그대로 두개로 쪼개는겁니다.. 그럴려면 아무래도
삼각형 갯수는 늘어나겠고 인덱스처리도 조정해 줘야겠죠..

옥트리등에서 이 부분에 대한 논의가 적은것은.. 제 생각으로는 거의
대부분의 맵이 실내베이스 이거나 실외의 경우 지형을 베이스로 하고
건물등을 오브젝터로 올리기 때문인 듯 합니다. 통맵을 잘 사용하시지들
않아서 인듯..(물론 지극히 개인적인 생각입니당)
pacman
Posts: 188
Joined: 2004-04-13 12:48

이렇게 하는 방법도 있습니다. ^^

Post by pacman »

느슨한 옥트리가 아닌 일반적인 옥트리를 제가 아는 대로 설명드리겠습니다.
느슨한 옥트리는 제가 써보지 않아서 모릅니다. -_-;

1. 옥트리는 하나의 입방체를 가진 루트 노드로부터 시작합니다.

2. 이 노드를 다시 8개의 자식 노드로 구역을 나누어 폴리곤을 재분배합니다.
이때, 폴리곤이 하나도 포함되어 있지 않는 노드는 아예 생성하지 않습니다.

3. 일정 개수 이상의 폴리곤을 가진 자식 노드들에 대해 위의 과정을 반복합니다.

옥트리를 생성하는 부분은 책 또는 웹상의 자료를 통해 이미 아실 것이라 생각되므로 간단하게 알아보았습니다.
위의 '입방체'는 실제로 메쉬 오브젝트의 '바운딩 박스'를 말합니다.

즉, 어떠한 형태의 물체든 바운딩 박스, 정점 데이타, 폴리곤(평면) 데이타만 알면 옥트리로 구현할 수 있습니다.
엄청나게 큰 복잡한 지형이든 작은 곰인형이든 상관없이 모두 옥트리의 대상이 될 수 있습니다.
물론, 조그만 물체 자체가 옥트리가 될 필요는 없겠지요. 옥트리에 포함시켜 관리해야겠죠. ^^;

옥트리 구현시 문제는 폴리곤이 여러 자식 노드들의 구역에 속하는 경우에는 어떻게 할 것이냐죠.
방법은 크게 세가지로 나누어 볼 수 있겠습니다. (1,2번은 이미 윗분이 말씀하신 방법이고, 3번은 제가 사용하는 방법입니다.)

1. 폴리곤을 해당 노드들에 중복 저장
: 렌더링이나 충돌 처리시에 똑같은 폴리곤을 여러번 처리하는 것은 낭비이므로, 폴리곤마다 플래그를 따로 둡니다.

2. 폴리곤을 쪼개서 각각의 노드에 저장
: 플래그가 따로 필요없지만 폴리곤 수가 많이 늘어나게 돼죠.

3. 폴리곤을 현재 노드에 저장
: 하나의 자식 노드에만 속하지 않으므로 맘편하게 자식노드가 아닌 현재 노드(부모 노드)에 저장합니다.

여기서 고민되는 것이
1번처럼 폴리곤 마다 플래그를 두어 처리하자니 비효율적이고,
2번처럼 자식 노드 사이의 경계면에 걸리는 폴리곤을 모조리 쪼개서 저장하자니 폴리곤 수가 늘어나서 역시 비효율적입니다.

저는 고심끝에 3번의 방법으로 옥트리를 구현하였습니다.
이 방법으로 하면 플래그를 따로 둘 필요도, 폴리곤을 나눌 필요도 없어서 코드가 깔끔해집니다.
단점은 자식 노드보다 더 큰 부모 노드에 폴리곤을 저장하므로 공간 분할의 효율성이 떨어진다고 볼 수도 있겠습니다.

즉, 그렇게 하면 옥트리를 구현한 의미가 없지 않느냐고 반문할 수도 있겠습니다.
하지만, 이것은 경계면에 걸치는 폴리곤에만 해당되는 문제이므로 전체적으로 볼 때 그리 큰 문제는 되지 않는다고 생각합니다.
또한 1,2번의 단점을 가지고 있지 않으므로 오히려 더 효율적이라 생각됩니다.
아래에 보시다시피 옥트리 구현하는 코드는 길기만 하고 단순무식합니다.
렌더링하는 코드도 매우 단순합니다. 여기에 최적화는 얼마든지 가능합니다.

참고로 1,2번은 폴리곤 데이타가 리프노드에만 저장이 되는 반면, 3번은 리프노드가 아니더라도 폴리곤 데이타가 존재할 수 있습니다.
(1,2번과의 차이점일뿐 실행 성능상의 단점이 결코 아닙니다.)

다분히 저의 주관에 입각해 구현한 옥트리이므로 최선의 방법은 아닐거라 생각합니다.
단지 이런 방법도 있다는 걸 보여드리고 싶었을 뿐입니다.
그리고 객체를 관리하기 위해 옥트리를 사용하는 경우에도 마찬가지일거라 생각됩니다.

제 개인적인 바램입니다만,
옥트리는 자료구조의 단순함과 깔끔함(비교적 :D ),
구현의 용이함(쉽지는 않죠 :wink: ),
활용 영역의 다양함(쓰는 사람 나름 :roll: ),
그래픽 하드웨어의 발전(폴리곤 수에 구애받지 않는 :oops: )으로 인해 앞으로 더욱 주목 받기를 희망합니다.

<참고 자료>
- GPG 1권: 4.10 옥트리의 구축, 4.11 느슨한 옥트리
- 게임 프로그래밍 Trick of the Trade: Trick 14. 옥트리를 사용한 공간 분할
- http://www.gametutorials.com/Tutorials/ ... GL_Pg5.htm

Code: Select all

// 정점
struct cVert
{
	float	x, y, z;
};

// 평면
struct cFace
{
	uint	v0;				// 첫번째 정점 인덱스
	uint	v1;				// 두번째 정점 인덱스
	uint	v2;				// 세번째 정점 인덱스
};

// 옥트리 노드
class cOctreeNode
{
public:
	cOctreeNode(int iNumFaces, cVector& vMin, cVector& vMax);
	virtual ~cOctreeNode(){ Empty(); }

	void	Empty();
	void	Build();
	void	Draw();

private:
	BOOL	IsInFrustum();

private:
	static uint	_iMinFacesPerNode;		// 노드당 최소 평면 수
	static cVert*	_pVert;			// 정점 배열
	static cFrustum*	_pFrustum;		// 시야 절두체

	// 자식 옥트리 노드
	cOctreeNode*	_pChild[8];		// 자식 노드
	int		_iNumChildren;		// 자식 노드 수
	// 평면
	cFace*		_pFace;			// 평면 배열
	uint		_iNumFaces;		// 평면 수
	// 바운딩 박스
	cVector		_vMin;			// 최소점
	cVector		_vMax;			// 최대점
	cVector		_vCenter;		// 중심점
};

cOctreeNode::cOctreeNode(int iNumFaces, cVector& vMin, cVector& vMax)
: _vMin(vMin), _vMax(vMax), _vCenter((_vMin + _vMax)*0.5)
{
	// 자식 옥트리 노드
	_pChild[0] = _pChild[1] = _pChild[2] = _pChild[3] =
	_pChild[4] = _pChild[5] = _pChild[6] = _pChild[7] = NULL;
	_iNumChildren = 0;
	// 평면
	_pFace = new cFace[iNumFaces];
	_iNumFaces = iNumFaces;
}

void cOctreeNode::Empty()
{
	if(_pFace){ delete [] _pFace; _pFace = NULL; }

	for(int i = 0; i < 8; ++i)
	{
		if(_pChild[i]){ delete _pChild[i]; _pChild[i] = NULL; }
	}
}

void cOctreeNode::Build()
{
	// 리프 노드는 바로 리턴
	if(_iNumFaces <= _iMinFacesPerNode) return;

	// 각 자식에 속하는 평면의 개수 셈
	cVector p0, p1, p2;
	uint iFaceCount0 = 0, iFaceCount1 = 0, iFaceCount2 = 0, iFaceCount3 = 0;
	uint iFaceCount4 = 0, iFaceCount5 = 0, iFaceCount6 = 0, iFaceCount7 = 0, iFaceCount8 = 0;
	cFace* pTempFace = NULL;

	for(uint i = 0; i < _iNumFaces; ++i)
	{
		p0 = cVector(&_pVert[_pFace[i].v0].x);
		p1 = cVector(&_pVert[_pFace[i].v1].x);
		p2 = cVector(&_pVert[_pFace[i].v2].x);

		if(
			// 아래 왼쪽 뒤
			(p0.x <= _vCenter.x && p0.y <= _vCenter.y && p0.z <= _vCenter.z) &&
			(p1.x <= _vCenter.x && p1.y <= _vCenter.y && p1.z <= _vCenter.z) &&
			(p2.x <= _vCenter.x && p2.y <= _vCenter.y && p2.z <= _vCenter.z)
			) ++iFaceCount0;
		else if(
			// 아래 오른쪽 뒤
			(p0.x >= _vCenter.x && p0.y <= _vCenter.y && p0.z <= _vCenter.z) &&
			(p1.x >= _vCenter.x && p1.y <= _vCenter.y && p1.z <= _vCenter.z) &&
			(p2.x >= _vCenter.x && p2.y <= _vCenter.y && p2.z <= _vCenter.z)
			) ++iFaceCount1;
		else if(
			// 아래 왼쪽 앞
			(p0.x <= _vCenter.x && p0.y <= _vCenter.y && p0.z >= _vCenter.z) &&
			(p1.x <= _vCenter.x && p1.y <= _vCenter.y && p1.z >= _vCenter.z) &&
			(p2.x <= _vCenter.x && p2.y <= _vCenter.y && p2.z >= _vCenter.z)
			) ++iFaceCount2;
		else if(
			// 아래 오른쪽 앞
			(p0.x >= _vCenter.x && p0.y <= _vCenter.y && p0.z >= _vCenter.z) &&
			(p1.x >= _vCenter.x && p1.y <= _vCenter.y && p1.z >= _vCenter.z) &&
			(p2.x >= _vCenter.x && p2.y <= _vCenter.y && p2.z >= _vCenter.z)
			) ++iFaceCount3;
		else if(
			// 위 왼쪽 뒤
			(p0.x <= _vCenter.x && p0.y >= _vCenter.y && p0.z <= _vCenter.z) &&
			(p1.x <= _vCenter.x && p1.y >= _vCenter.y && p1.z <= _vCenter.z) &&
			(p2.x <= _vCenter.x && p2.y >= _vCenter.y && p2.z <= _vCenter.z)
			) ++iFaceCount4;
		else if(
			// 위 오른쪽 뒤
			(p0.x >= _vCenter.x && p0.y >= _vCenter.y && p0.z <= _vCenter.z) &&
			(p1.x >= _vCenter.x && p1.y >= _vCenter.y && p1.z <= _vCenter.z) &&
			(p2.x >= _vCenter.x && p2.y >= _vCenter.y && p2.z <= _vCenter.z)
			) ++iFaceCount5;
		else if(
			// 위 왼쪽 앞
			(p0.x <= _vCenter.x && p0.y >= _vCenter.y && p0.z >= _vCenter.z) &&
			(p1.x <= _vCenter.x && p1.y >= _vCenter.y && p1.z >= _vCenter.z) &&
			(p2.x <= _vCenter.x && p2.y >= _vCenter.y && p2.z >= _vCenter.z)
			) ++iFaceCount6;
		else if(
			// 위 오른쪽 앞
			(p0.x >= _vCenter.x && p0.y >= _vCenter.y && p0.z >= _vCenter.z) &&
			(p1.x >= _vCenter.x && p1.y >= _vCenter.y && p1.z >= _vCenter.z) &&
			(p2.x >= _vCenter.x && p2.y >= _vCenter.y && p2.z >= _vCenter.z)
			) ++iFaceCount7;
		else{
			// 여러 자식에 걸쳐있는 평면
			++iFaceCount8;
		}
	}

	// 평면을 가진 자식만 생성
	if(iFaceCount0 > 0)
	{
		++_iNumChildren;
		_pChild[0] = new cOctreeNode(iFaceCount0, _vMin, _vCenter);
	}
	if(iFaceCount1 > 0)
	{
		++_iNumChildren;
		_pChild[1] = new cOctreeNode(iFaceCount1, cVector(_vCenter.x, _vMin.y, _vMin.z), cVector(_vMax.x, _vCenter.y, _vCenter.z));
	}
	if(iFaceCount2 > 0)
	{
		++_iNumChildren;
		_pChild[2] = new cOctreeNode(iFaceCount2, cVector(_vMin.x, _vMin.y, _vCenter.z), cVector(_vCenter.x, _vCenter.y, _vMax.z));
	}
	if(iFaceCount3 > 0)
	{
		++_iNumChildren;
		_pChild[3] = new cOctreeNode(iFaceCount3, cVector(_vCenter.x, _vMin.y, _vCenter.z), cVector(_vMax.x, _vCenter.y, _vMax.z));
	}
	if(iFaceCount4 > 0)
	{
		++_iNumChildren;
		_pChild[4] = new cOctreeNode(iFaceCount4, cVector(_vMin.x, _vCenter.y, _vMin.z), cVector(_vCenter.x, _vMax.y, _vCenter.z));
	}
	if(iFaceCount5 > 0)
	{
		++_iNumChildren;
		_pChild[5] = new cOctreeNode(iFaceCount5, cVector(_vCenter.x, _vCenter.y, _vMin.z), cVector(_vMax.x, _vMax.y, _vCenter.z));
	}
	if(iFaceCount6 > 0)
	{
		++_iNumChildren;
		_pChild[6] = new cOctreeNode(iFaceCount6, cVector(_vMin.z, _vCenter.y, _vCenter.z), cVector(_vCenter.x, _vMax.y, _vMax.z));
	}
	if(iFaceCount7 > 0)
	{
		++_iNumChildren;
		_pChild[7] = new cOctreeNode(iFaceCount7, _vCenter, _vMax);
	}
	if(iFaceCount8 > 0)
	{
		pTempFace = new cFace[iFaceCount8];
		iFaceCount8 = 0;
	}

	// 자식에 속하는 평면을 모두 추가
	iFaceCount0 = 0, iFaceCount1 = 0, iFaceCount2 = 0, iFaceCount3 = 0;
	iFaceCount4 = 0, iFaceCount5 = 0, iFaceCount6 = 0, iFaceCount7 = 0, iFaceCount8 = 0;

	for(i = 0; i < _iNumFaces; ++i)
	{
		p0 = cVector(&_pVert[_pFace[i].v0].x);
		p1 = cVector(&_pVert[_pFace[i].v1].x);
		p2 = cVector(&_pVert[_pFace[i].v2].x);

		if(_pChild[0] &&
			(p0.x <= _vCenter.x && p0.y <= _vCenter.y && p0.z <= _vCenter.z) &&
			(p1.x <= _vCenter.x && p1.y <= _vCenter.y && p1.z <= _vCenter.z) &&
			(p2.x <= _vCenter.x && p2.y <= _vCenter.y && p2.z <= _vCenter.z)
			) _pChild[0]->_pFace[iFaceCount0++] = _pFace[i];
		else if(_pChild[1] &&
			(p0.x >= _vCenter.x && p0.y <= _vCenter.y && p0.z <= _vCenter.z) &&
			(p1.x >= _vCenter.x && p1.y <= _vCenter.y && p1.z <= _vCenter.z) &&
			(p2.x >= _vCenter.x && p2.y <= _vCenter.y && p2.z <= _vCenter.z)
			) _pChild[1]->_pFace[iFaceCount1++] = _pFace[i];
		else if(_pChild[2] &&
			(p0.x <= _vCenter.x && p0.y <= _vCenter.y && p0.z >= _vCenter.z) &&
			(p1.x <= _vCenter.x && p1.y <= _vCenter.y && p1.z >= _vCenter.z) &&
			(p2.x <= _vCenter.x && p2.y <= _vCenter.y && p2.z >= _vCenter.z)
			) _pChild[2]->_pFace[iFaceCount2++] = _pFace[i];
		else if(_pChild[3] &&
			(p0.x >= _vCenter.x && p0.y <= _vCenter.y && p0.z >= _vCenter.z) &&
			(p1.x >= _vCenter.x && p1.y <= _vCenter.y && p1.z >= _vCenter.z) &&
			(p2.x >= _vCenter.x && p2.y <= _vCenter.y && p2.z >= _vCenter.z)
			) _pChild[3]->_pFace[iFaceCount3++] = _pFace[i];
		else if(_pChild[4] &&
			(p0.x <= _vCenter.x && p0.y >= _vCenter.y && p0.z <= _vCenter.z) &&
			(p1.x <= _vCenter.x && p1.y >= _vCenter.y && p1.z <= _vCenter.z) &&
			(p2.x <= _vCenter.x && p2.y >= _vCenter.y && p2.z <= _vCenter.z)
			) _pChild[4]->_pFace[iFaceCount4++] = _pFace[i];
		else if(_pChild[5] &&
			(p0.x >= _vCenter.x && p0.y >= _vCenter.y && p0.z <= _vCenter.z) &&
			(p1.x >= _vCenter.x && p1.y >= _vCenter.y && p1.z <= _vCenter.z) &&
			(p2.x >= _vCenter.x && p2.y >= _vCenter.y && p2.z <= _vCenter.z)
			) _pChild[5]->_pFace[iFaceCount5++] = _pFace[i];
		else if(_pChild[6] &&
			(p0.x <= _vCenter.x && p0.y >= _vCenter.y && p0.z >= _vCenter.z) &&
			(p1.x <= _vCenter.x && p1.y >= _vCenter.y && p1.z >= _vCenter.z) &&
			(p2.x <= _vCenter.x && p2.y >= _vCenter.y && p2.z >= _vCenter.z)
			) _pChild[6]->_pFace[iFaceCount6++] = _pFace[i];
		else if(_pChild[7] &&
			(p0.x >= _vCenter.x && p0.y >= _vCenter.y && p0.z >= _vCenter.z) &&
			(p1.x >= _vCenter.x && p1.y >= _vCenter.y && p1.z >= _vCenter.z) &&
			(p2.x >= _vCenter.x && p2.y >= _vCenter.y && p2.z >= _vCenter.z)
			) _pChild[7]->_pFace[iFaceCount7++] = _pFace[i];
		else{
			pTempFace[iFaceCount8] = _pFace[i];
			++iFaceCount8;
		}
	}

	// 자식 노드 재귀 호출
	if(_pChild[0]) _pChild[0]->Build();
	if(_pChild[1]) _pChild[1]->Build();
	if(_pChild[2]) _pChild[2]->Build();
	if(_pChild[3]) _pChild[3]->Build();
	if(_pChild[4]) _pChild[4]->Build();
	if(_pChild[5]) _pChild[5]->Build();
	if(_pChild[6]) _pChild[6]->Build();
	if(_pChild[7]) _pChild[7]->Build();

	// 리프 노드가 아니므로 평면 제거
	if(_pFace)
	{
		delete [] _pFace;
		_pFace = NULL;
		_iNumFaces = 0;
	}
	if(pTempFace)
	{
		_pFace = pTempFace;
		_iNumFaces = iFaceCount8;
	}
}

void cOctreeNode::Draw()
{
	// 시야 절두체 안에 포함되지(교차되지) 않는 노드는 그냥 리턴
	if(!IsInFrustum()) return;

	// 현재 노드에 속한 폴리곤이 있으면 드로잉
	for(uint i = 0; i < _iNumFaces; ++i)
	{
		// 드로잉 코드
	}
	
	if(_iNumChildren > 0)
	{
		// 자식 드로잉
		if(_pChild[0]) _pChild[0]->Draw();
		if(_pChild[1]) _pChild[1]->Draw();
		if(_pChild[2]) _pChild[2]->Draw();
		if(_pChild[3]) _pChild[3]->Draw();
		if(_pChild[4]) _pChild[4]->Draw();
		if(_pChild[5]) _pChild[5]->Draw();
		if(_pChild[6]) _pChild[6]->Draw();
		if(_pChild[7]) _pChild[7]->Draw();
	}
}
착실이
Posts: 77
Joined: 2002-11-29 11:12

감사합니다. 큰 도움이 되겠습니다.

Post by 착실이 »

lsg0222님... 성실한 답변 감사 드립니다.

아. 처음에 답변해주신 ekflame님께도 감사드립니다.
Locked