절두체 컬링(frustum culling)

[만진씨.]

출처 : http://blog.naver.com/treewild?Redirect=Log&logNo=20005011311

절두체 컬링(frustum culling)



평면의 정의:

네이버 백과사전의 입을 빌면 평면의 정의는 다음과 같다.

//========================================================================================
하나의 직선을 다른 직선으로 나란히 이동시키면 평평한 면이 이루어진다. 이것을 평면이라 한다. 거울과 같이 조용한 수면을 예상할 수 있다. 그러나 수학적으로 이것을 정의하기는 어렵고 점이나 직선과 더불어 무정의용어(無定義用語)로서 다음 공리를 설정하여 간접적으로 그 성질을 규정하고 있다.

① 하나의 직선 위에 없는 3개의 점이 정하는 평면은 하나 존재하고 유일하다. ② 두 개의 서로 다른 점이 하나의 평면에 포함되어 있으면 이들의 점을 잇는 직선 위의 점은 모두 포함된다. ③ 두 개의 평면이 한 점을 공유하면 두 개의 평면은 그 점을 포함하는 직선을 공유한다. 공간에 직교축을 정하면 그 공간 내의 평면은 3개의 좌표 x,y,z에 관한 1차방정식 ax＋by＋cz＋d=0으로 표시된다. 평면은 가로 ·세로의 방향으로 한없이 연장되어 있으나 그림을 그릴 때는 습관상 평행사변형 등으로 나타낸다. 또한 직선의 일부를 선분이라고 하듯이 평면의 일부도 면분이라고 하는 경우가 있다.
//========================================================================================



평면의 방정식:

윗 글을 보면 평면은 방정식 ax＋by＋cz＋d=0 로 표현할 수 있다고 나와있다.
계수 a,b,c는 이 평면의 방향을 나타내는 법선 벡터이고 d는 평면이 원점으로부터 떨어진 거리를 나타낸다. 또 이 식을 만족하는 x,y,z들은 평면을 이루는 점들이라 할 수 있다.



평면의 성질:

계수 a,b,c가 평면의 방향을 나타내는 법선 벡터라고 했다. 평면에 방향이 있다는 것은 어떤 임의의 한 점이 평면의 앞에 있는지 뒤에 있는지 또는 평면 위에 있는지 알수 있다는 말이다.
방법은 간단한데 평면의 방정식에다가 임의의 한점을 대입하여 그 결과값을 보는 것이다.
일반적으로 다음과 같다.

ax+by+cz+d의 결과값 = 0 : 점이 평면 위에 있다.
ax+by+cz+d의 결과값 > 0 : 점이 평면 앞에 있다.
ax+by+cz+d의 결과값 < 0 : 점이 평면 뒤에 있다.



절두체의 정의:

'3D게임 프로그래밍, 컴퓨터 그래픽을 위한 수학'에 보면 절두체(frustum culling)란 다음과 같이 정의되어 있다.

시야 절두체(view frustum)는 하나의 3차원 장면 안에서 보이는 모든 것들을 담는 공간적 입체이다.



절두체의 구성 요소:

실제적으로 절두체를 구성하는 것은 6개의 평면이다. 이 6개의 평면은 다음과 같다.

근평면(near plane): 카메라와 수직하며 제일 가까운 곳의 시야 범위를 나타내는 평면
원평면(far plane): 카메라와 수지하며 제일 먼 곳의 시야 범위를 나타내는 평면
좌평면(left plane): 카메라의 좌측 시야 범위를 나타내는 평면
우평면(right plane): 카메라의 우측 시야 범위를 나타내는 평면
상평면(top plane): 카메라의 상단 시야 범위를 나타내는 평면
하평면(bottom plane): 카메라의 하단 시야 범위를 나타내는 평면



평면을 코드로 나타내면?

Direct3D에는 세개의 점으로부터 평면의 방정식을 구해주는 함수가 준비되어 있다.

D3DXPLANE *D3DXPlaneFromPoints(D3DXPLANE *pOut,
CONST D3DXVECTOR3 *pV1,
CONST D3DXVECTOR3 *pV2,
CONST D3DXVECTOR3 *pV3,
);



절두체 클래스 소스 분석:

절두체를 나타내는 클래스의 예는 다음과 같다. 김용준님이 쓰신 '3D 게임 프로그래밍' 책에 나오는 소스들이다.

//=========================================================================
// 프러스텀 컬링을 관리하기 위한 클래스
//
//=========================================================================
class ZFrustum
{
  D3DXVECTOR3 m_vtx[8]; /// 프러스텀을 구성할 정점 8개
  D3DXVECTOR3 m_vPos; /// 현재 카메라의 월드좌표
  D3DXPLANE m_plane[6]; /// 프러스텀을 구성하는 6개의 평면

public:
  /// 생성자
  ZFrustum();

  /// 카메라(view) * 프로젝션(projection)행렬을 입력받아 6개의 평면을 만든다.
  BOOL Make( D3DXMATRIXA16* pmatViewProj );



  /// 한점 v가 프러스텀안에 있으면 TRUE를 반환, 아니면 FALSE를 반환한다.
  BOOL IsIn( D3DXVECTOR3* pv );
  /** 중심(v)와 반지름(radius)를 갖는 경계구(bounding sphere)가 프러스텀안에 있으면
  * TRUE를 반환, 아니면 FALSE를 반환한다.*/
  BOOL IsInSphere( D3DXVECTOR3* pv, float radius );



  /// 현재 카메라의 월드좌표를 얻어준다.
  D3DXVECTOR3* GetPos() { return &m_vPos; }



  /// 프러스텀을 화면에 그려준다.
  BOOL Draw( LPDIRECT3DDEVICE9 pDev );
};

내가 보기에 중요한 메소드를 골라본다면 Make, IsIn, IsInSphere 등이라 생각된다. 각각 절두체를 생성하고 절두체안에 점, 구가 포함되는지 판단하는 메소드이다.
멤버 데이터는 절두체의 정의에 걸맞게 여섯개의 평면을 이루는 데이터로 되어있다.

그 외의 기능으로 카메라에 관한 기능과 절두체의 출력 기능이 구현되어 있는데 절두체 출력 기능은 테스트를 위한 것이므로 중요한 건 아니고 카메라의 기능은 당연히 구현되어야 하는 것이다. 왜냐하면 카메라의 시야에서 보이는 공간을 담는 것이 절두체이기 때문이다.


다음은 절두체를 구성하는 여섯개의 평면을 만드는 메소드의 구현이다. 구현의 대략적인 알고리즘은 다음과 같다.

1. 프로젝션 행렬까지 거친 월드좌표계의 경계들을 이루는 정점들을 알아온다. 이 정점들의 값은 (-1,-1,0) ~ (1,1,1)사이의 값이다.
2. 뷰, 프로젝션이 모두 연산된 행렬의 역행렬을 구한다
3. 뷰, 프로젝션이 모두 연산된 행렬의 역행렬을 아까 구한 정점들과 연산하여 실제 월드에서의 좌표들을 구한다.
이 좌표들이 실제 절두체의 각 꼭지점이다.

//==============================================================================
// 카메라(view) * 프로젝션(projection)행렬을 입력받아 6개의 평면을 만든다.
//==============================================================================
BOOL ZFrustum::Make( D3DXMATRIXA16* pmatViewProj )
{
  int i;
  D3DXMATRIXA16 matInv;

  // 투영행렬까지 거치면 모든 3차원 월드좌표의 점은 (-1,-1,0) ~ (1,1,1)사이의 값으로 바뀐다.
  // m_vtx에 이 동차공간의 경계값을 넣어둔다.
  m_vtx[0].x = -1.0f; m_vtx[0].y = -1.0f; m_vtx[0].z = 0.0f;
  m_vtx[1].x = 1.0f; m_vtx[1].y = -1.0f; m_vtx[1].z = 0.0f;
  m_vtx[2].x = 1.0f; m_vtx[2].y = -1.0f; m_vtx[2].z = 1.0f;
  m_vtx[3].x = -1.0f; m_vtx[3].y = -1.0f; m_vtx[3].z = 1.0f;
  m_vtx[4].x = -1.0f; m_vtx[4].y = 1.0f; m_vtx[4].z = 0.0f;
  m_vtx[5].x = 1.0f; m_vtx[5].y = 1.0f; m_vtx[5].z = 0.0f;
  m_vtx[6].x = 1.0f; m_vtx[6].y = 1.0f; m_vtx[6].z = 1.0f;
  m_vtx[7].x = -1.0f; m_vtx[7].y = 1.0f; m_vtx[7].z = 1.0f;

  // view * proj의 역행렬을 구한다.
  D3DXMatrixInverse(&matInv, NULL, pmatViewProj );

  // Vertex_최종 = Vertex_local * Matrix_world * Matrix_view * Matrix_Proj 인데,
  // Vertex_world = Vertex_local * Matrix_world이므로,
  // Vertex_최종 = Vertex_world * Matrix_view * Matrix_Proj 이다.
  // Vertex_최종 = Vertex_world * ( Matrix_view * Matrix_Proj ) 에서
  // 역행렬( Matrix_view * Matrix_Proj )^-1를 양변에 곱하면
  // Vertex_최종 * 역행렬( Matrix_view * Matrix_Proj )^-1 = Vertex_World 가 된다.
  // 그러므로, m_vtx * matInv = Vertex_world가 되어, 월드좌표계의 프러스텀 좌표를 얻을 수 있다.
  for( i = 0; i < 8; i++ )
   D3DXVec3TransformCoord( &m_vtx[i], &m_vtx[i], &matInv );

  // 0번과 5번은 프러스텀중 near평면의 좌측상단과 우측하단이므로, 둘의 좌표를 더해서 2로 나누면
  // 카메라의 좌표를 얻을 수 있다.(정확히 일치하는 것은 아니다.)
  m_vPos = ( m_vtx[0] + m_vtx[5] ) / 2.0f;

  // 얻어진 월드좌표로 프러스텀 평면을 만든다
  // 벡터가 프러스텀 안쪽에서 바깥쪽으로 나가는 평면들이다.
 // D3DXPlaneFromPoints(&m_plane[0], m_vtx+4, m_vtx+7, m_vtx+6); // 상 평면(top)
 // D3DXPlaneFromPoints(&m_plane[1], m_vtx , m_vtx+1, m_vtx+2); // 하 평면(bottom)
 // D3DXPlaneFromPoints(&m_plane[2], m_vtx , m_vtx+4, m_vtx+5); // 근 평면(near)
  D3DXPlaneFromPoints(&m_plane[3], m_vtx+2, m_vtx+6, m_vtx+7); // 원 평면(far)
  D3DXPlaneFromPoints(&m_plane[4], m_vtx , m_vtx+3, m_vtx+7); // 좌 평면(left)
  D3DXPlaneFromPoints(&m_plane[5], m_vtx+1, m_vtx+5, m_vtx+6); // 우 평면(right)

  return TRUE;
}


다음은 각각 점, 구가 절두체 안에 포함되는지를 테스트하는 메소드이다. 구현은 간단하므로 설명하지 않는다.

//==============================================================================
/// 한점 v가 프러스텀안에 있으면 TRUE를 반환, 아니면 FALSE를 반환한다.
//==============================================================================
BOOL ZFrustum::IsIn( D3DXVECTOR3* pv )
{
float fDist;
// int i;

// 현재는 left, right, far plane만 적용한다.
// for( i = 0 ; i < 6 ; i++ )
{
fDist = D3DXPlaneDotCoord( &m_plane[3], pv );
if( fDist > PLANE_EPSILON ) return FALSE; // plane의 normal벡터가 far로 향하고 있으므로 양수이면 프러스텀의 바깥쪽
fDist = D3DXPlaneDotCoord( &m_plane[4], pv );
if( fDist > PLANE_EPSILON ) return FALSE; // plane의 normal벡터가 left로 향하고 있으므로 양수이면 프러스텀의 왼쪽
fDist = D3DXPlaneDotCoord( &m_plane[5], pv );
if( fDist > PLANE_EPSILON ) return FALSE; // plane의 normal벡터가 right로 향하고 있으므로 양수이면 프러스텀의 오른쪽
}

return TRUE;
}
//==============================================================================
// 중심(v)와 반지름(radius)를 갖는 경계구(bounding sphere)가 프러스텀안에 있으면
// TRUE를 반환, 아니면 FALSE를 반환한다.
//==============================================================================
BOOL ZFrustum::IsInSphere( D3DXVECTOR3* pv, float radius )
{
float fDist;

fDist = D3DXPlaneDotCoord( &m_plane[3], pv );
if( fDist > (radius+PLANE_EPSILON) ) return FALSE; // 평면과 중심점의 거리가 반지름보다 크면 프러스텀에 없음
fDist = D3DXPlaneDotCoord( &m_plane[4], pv );
if( fDist > (radius+PLANE_EPSILON) ) return FALSE; // 평면과 중심점의 거리가 반지름보다 크면 프러스텀에 없음
fDist = D3DXPlaneDotCoord( &m_plane[5], pv );
if( fDist > (radius+PLANE_EPSILON) ) return FALSE; // 평면과 중심점의 거리가 반지름보다 크면 프러스텀에 없음

return TRUE;
}



2003. 1222. Edited