낭만코더

벡터의 내적 정의는 [프로그래밍/3D Programming] - [3D수학] 벡터의 내적 참고 해주세요.

벡터의 내적에 값을 이제 좀 더 편하게 할 수 있는 방법을 찾아 보도록 하겠습니다.

백터 내적의 공식은 다음과 같습니다.

그러나 프로그래밍에서 삼각함수를 사용하는건 프로그램의 성능을 저하 시킬 수 있기 때문에

좀 더 편한 방식을 알아보도록 하겠습니다.

벡터의 내적은 좌표값의 각 성분을 곱해서 더하면 됩니다. 과연 위에 공식이랑 똑같은 값이 나오는지 한번 확인 해보겠습니다.

벡터A와 벡터B의 내적은 각 성분을 곱해서 더하면 된다고 했는데요 

계산해보면 ( 4 X 6 ) + ( 3 X 0 ) = 24가 나오는 것을 알 수 있습니다.

그럼 위의 값이 우리가 만든 공식에 부합되는지도 알아볼려면

cos값을 알아야 되는데요 일단 위에 나온 값을 대입해서 증명 해보도록 하겠습니다.

벡터a의 절대값 곱하기 벡터b의 절대값에 cos값을 곱한 결과가 24입니다.

따라서 cos값은 

cos값은 대충 이런식으로 처리 됩니다.

원하는 값이 없네요.... 계산기로 두들겨 보니 가장 근사치의 값이.... cos36이네요

근데 이런 방식으로 구할려니 그냥 대충 때려 넣는 느낌이라 다른 방법으로 한번 찾아보겠습니다.

두점을 가진 벡터가 있고 그 사잇각( 사이각? ) 을 구하는 공식은 다음과 같습니다. 굳이 외울 필요는 없습니다

엄청 복잡해 보이지만 간단합니다.

벡터 v1 즉 a벡터의 크기는 5이고 v2 벡터 즉 b벡터의 크기는 6입니다 그리고 각 좌표의 값을 계산하면 저렇게 되구요

즉 사이의 각도는 입니다. 또 계산기를 두들겨 보면 다음과 같이 나옵니다.

애매하긴 합니다만 밑에 소수점은 버리기로 하였기 때문에 36도라고 하겠습니다.

그럼 위에 저희가 가정했던 각도가 일치 하는것을 볼수 있습니다.

그러므로 벡터의 내적은 각 성분을 곱해서 더하면 된다는 것을 알 수 있습니다.

프로그래밍에서는 각 성분을 곱해서 더하는 것으로 내적을 쉽게 구하는것이 성능에도 좋고 계산하기도 편합니다.

게임에서는 거의 대부분은 좌표값을 가지고 있기 때문에 내적은 저런식으로 표현해준다고 생각하시면 될 것 같습니다.

내적을 다른 방법으로 구하는 방법은 이제 보셨습니다 이제 게임에서 어떻게 활용하는지 알아 보도록 하겠습니다.

현재 주인공 케릭터의 위치에서 적이 있는 위치가 내 앞에 있는지 혹은 뒤에 있는지 계산하는 방법을 알아보도록 하겠습니다.

다음 그림에서 

주인공의 위치를 편의상 원점이라고 했을 경우에 적A와 적B의 위치는 주인공 앞인지 뒤인지 보면 그림으로 봤을 경우에는

적A는 주인공의 앞쪽 적B는 주인공케릭터의 뒷쪽인걸 알 수 있습니다. 

이걸 내적을 사용해서 알아보도록 하겠습니다.

내적은 각 성분의 곱이라고 말씀 드렸기 때문에

계산 과정은 생략하고 

적A와 주인공의 내적에 코사인값은 0.6 이고 적B와 주인공의 내적에 코사인값은 -0.6이 됩니다.

일반적으로 방향벡터는 단위벡터로 만들어줘서 계산을 좀 더 빠르게 할 수 있도록 합니다.

따라서 내적시에 값이 0보다 크면 앞쪽에, 0보다 작으면 뒷쪽에 있는것으로 판별 합니다.

간단하게 벡터의 내적의 활용의 예를 알아봤습니다.

이외에도 내적은 적이 주인공의 시야각안에 들어와 있는지 아닌지 확인하고, 선이 평면과 접하는 접점을 구할때도 사용되고

게임에 사용되는 곳이 많으므로 개념을 이해하고 있으시면 프로그래밍하는데 많은 도움이 됩니다.

벡터의 덧셈과 뺄셈을 정리 했으니 이제 슬슬 곱셈에 대한 개념이 나올때가 된것 같습니다.

벡터의 곱셈의 개념으로 벡터의 내적과 외적이 있습니다.

일단 이번 포스팅에는 내적을 다루겠지만 두가지 개념의 차이점만 짚고 넘어 가자면,

입니다.

내적( dot product, inner product )에 대한 정의는 다음과 같습니다.

위에 그림에서 

로 정의하고   로 정의를 하겠습니다.  세타의 값은 일 때  내적의 정의는 다음과 같습니다.

벡터의 내적의 특징은 다음과 같습니다.

1번식은 딱히 설명 드릴께 없을 것 같습니다.

2번식은 동일 한 벡터가 있을 경우에는 두 벡터가 이루는 각은 0도이므로 cos0 = 1 입니다. ( 이부분은 나중에 삼각함수때 또 정리를 하도록 하겠습니다. ) 그러므로 벡터a의 절대값 ( 길이 )의 제곱이 되는것을 알 수 있습니다.

다음으로 두 벡터의 내적이 가지는 기하학적인 의미 를 얘기해보겠습니다. 머 기하학이라고 해서 어려운 얘기는 아닙니다.

다음과 같은 교환이 성립되는 이유는 a벡터의 크기는 실수, b벡터의 크기도 실수, cos 값도 실수기 때문에 교환 법칙이 성립됩니다.

a벡터의 크기 즉 벡터의 길이 X cos 값은 점A에서 수선의 발을 내린점이 H라고 했을때 즉 선분 OH의 길이가 됩니다.

그리고 벡터b의 값은 그림에서 보시는 바와 같이 선분 OB의 길이가 됩니다. 

따라서 선분 OB의 길이와 선분 OH의 곱은 a벡터와 b벡터의 내적과 같다라는 도출이 됩니다.

노란색의 빛이 비추었을 경우에 벡터a의 그림자 OH와 벡터의 길이의 곱이 됩니다.

정리하자면 두 벡터의 내적이 가지는 기하학적 의미는 한 벡터를 다른 벡터위로 정사영 시킨 길이와 그 다른 벡터의 길이의 곱셈이다.

위의 그림에서는 선분 OH와 선분 OB의 길이의 곱이 됩니다.

개념적인 부분은 이쯤에서 마무리 하고 다음 포스팅에서 벡터의 내적을 어떻게 게임에 활용하여 사용하는지 

확인 해보도록 하겠습니다.

3D 게임 프로그래밍을 하다보면 3D 관련 수학에 대한 갈증이 생겨나기 마련입니다.

3D 수학을 알고 있느냐 모르고 있느냐에 따라서 관련 작업의 소스파악도 훨씬 쉬워지기 때문에

관련 내용을 한번 정리 해보도록 하겠습니다.

3D 수학의 가장 기초라고 할 수 있는 벡터에 대해서 알아보고 가장 기본이 되는 연산 덧셈과 뺄셈에 대해서 알아보도록 합시다.

• 벡터란 무엇인가?

 -> 크기와 방향을 동시에 나타내는 물리량을 말한다. 

     크기와 방향을 표시하는 좋은 방법이 화살표입니다. 그래서 보통 수학에서 벡터를 화살표로 표시 해줍니다.

위 그림에서 길이는 크기를 나타내고 화살표의 방향이 그래도 방향을 나타내서 보통 저런식으로 표현해줍니다.

 벡터의 표현은 이런식으로 해줍니다.

 이렇게 표현하면 벡터의 크기를 나타내주는 기호입니다. ( 절대값 표현 )

  일때 이 벡터를 "단위 벡터" 라고 합니다. 단위벡터는 보통 방향을 표현할때 많이 쓰고 3D 프로그래밍에서도 많이 사용합니다.

• 두 벡터가 서로 같을 조건

• 역벡터

• 벡터의 덧셈

두벡터 a와 b의 덧셈은 어떻게 표현하는지 알아보겠습니다. 보통 시작점이 같은 경우에는 쉽게 하는 방법이 있지만 일단은 그림을 보시면 벡터 b를 이동해줍니다. 왜냐하면 벡터는 크기와 방향이 동일하면 같은 벡터이기 때문에 밑에 그림처럼 이동해도 벡터의 합은 동일하게 됩니다.

따라서 해당 벡터 a와 벡터b의 덧셈은 최종적으로 다음과 같이 됩니다.

매번 이런식으로 덧셈을 하기 어렵기 때문에 시작점이 같은 경우에는 평형사변형 점섬을 그어줘서 이런식으로 덧셈을 처리하는게 조금 편합니다.

• 벡터의 뺄셈

벡터의 뺄셈은 벡터a와 벡터b가 다음과 같이 있다고 가정했을 경우에

벡터a와 벡터b의 뺄셈은 

다음과 같이 벡터b의 역벡터를 더해주는것과 동일합니다. 

따라서 벡터의 덧셈을 진행하게 되면다음 그림과 같이 됩니다.

벡터는 크기와 방향이 동일하면 같은 벡터이기 때문에 다음 그림과 같이 벡터의 뺄셈이 나옵니다.

같은 방법으로 벡터b - 벡터a 를 진행하게 되면 다음과 같이 진행됩니다.

이처럼 벡터의 뺄셈은 

특정 위치에서 다른 위치를 향하는 벡터를 구할 때 벡터의 뺄셈을 사용한다면 

 http://cafe.naver.com/graphicsprogramming/6

근데 사이트가 없어짐....

0. 들어가며

Shader X2 를 살펴 보기 이전에 쉐이더가 무엇인지에 대해서 살펴 보고 가야 할 것 같습니다.

물론 책을 보는 것이 더 빠를 수도 있겠지만 저같은 허접이 한 번 정리해 보는 것도 쉽게 접근할 수 있는 방법이 되지 않을까 생각합니다.

1. Fixed Pipeline

보통 게임 프로그래밍을 한다고 하면 C/C++ 에 대해서 공부하고, Win32 나 MFC 응용프로그램을 작성하고, 그리고 나서 OpenGL 이나 Direct3D 같은 라이브러리를 응용프로그램에 통합하여 사용하게 됩니다.

Direct3D 튜토리얼이나 입문 서적들을 보면서 장치, 정점 버퍼, 인덱스 버퍼, 텍스처, 변환, 광원, 재질 등에 대해서 공부하게 됩니다. 제일 간단한 형태가 아래와 같은 구현이겠죠.

    장치 생성

    정점 버퍼 생성

    인덱스 버퍼 생성

    텍스처 생성

    Clear()

    BeginScene()

        각종 렌더 스테이트 설정

        정점 스트림 설정

        인덱스 스트림 설정

        광원 설정

        재질 설정

        텍스처 설정

        각종 텍스처 스테이지 스테이트 설정

        각종 샘플러 스테이트 설정

        텍스처 설정

        뷰행렬 설정

        투영행렬 설정

        월드 행렬 설정

        DrawXXX()

    EndScene()

    Present()

    텍스처 언로드

    인덱스 버퍼 언로드

    정점 버퍼 언로드

    장치 언로드

뭐 빠진 부분도 있겠지만 BeginScene() 과 EndScene() 사이에 여러 가지 상태를 설정하고 Draw() 한 다음에 장치에 제출(Present)하게 됩니다. 이러한 일련의 과정들을 수행하기 위해서 Direct3D9 는 여러 가지 함수들을 제공합니다.

하지만 자세히 살펴 보면 이러한 여러 가지 작업들은 자료(Data) 와 연산(Operation) 으로 구분할 수 있다는 것을 알 수 있습니다.

SetXXX() 를 통해 설정하는 광원, 재질, 텍스처, 정점, 인덱스, 행렬 등은 응용프로그램에서 준비한 자료라 할 수 있고, 각종 SetXXXState() 메서드는 실제 그래픽 카드 내에서의 연산 방식을 설정하는 것이라 할 수 있습니다. 물론 이 연산에는 조건이라는 부분도 포함이 됩니다.

예를 들어 하나의 메시(Mesh) 를 렌더링한다고 합시다. 메시는 Max 등의 모델링 툴을 통해서 생성되거나 프로그래머가 직접 정점 위치를 설정하여 만들어 낼 수 있습니다. 보통 메시 자체의 공간인 오브젝트 공간을 가지고 있으며, 이를 3D 월드 내에서 표현하기 위해서는 월드 변환을 수행해 주어야 합니다. 그 다음으로는 보이지 않는 데이터들에 대한 처리 비용을 줄이기 위해서 뷰 공간으로 이동하고, 최종적으로 화면에 투영하기 위해서 절단 공간으로 이동하게 됩니다.

이러한 과정들을 처리하기 위해서 우리는 아래와 같이 간단하게 행렬들을 설정합니다.

    m_pD3DDevice->SetTransform( D3DTS_WORLD, &mWorld );      // 월드 행렬

    m_pD3DDevice->SetTransform( D3DTS_VIEW, &mView );          // 뷰 행렬

    m_pD3DDevice->SetTransform( D3DTS_PROJECTION, &mProj); // 투영 행렬

내부적으로는 어떤 식으로 처리되든지 우리는 개념적으로 파악하고 있기만 하면 되고 모든 계산은 라이브러리 및 GPU 가 알아서 해 줍니다.

안개를 설정할 때도 마찬가지로 자료와 연산의 종류만 설정해 주면 됩니다. 안개 이론이 어쩌고 저쩌고 알지 못해도 간단하게 몇 줄 호출함으로써 이를 구현하는 것이 가능합니다.

    float Start = 0.5f,
          End   = 0.8f;
 
    g_pDevice->SetRenderState(D3DRS_FOGENABLE, TRUE);
 
    g_pDevice->SetRenderState(D3DRS_FOGCOLOR, Color);
    
    g_pDevice->SetRenderState(D3DRS_FOGVERTEXMODE, D3DFOG_LINEAR);
    g_pDevice->SetRenderState(D3DRS_FOGSTART, *(DWORD *)(&Start));
    g_pDevice->SetRenderState(D3DRS_FOGEND,   *(DWORD *)(&End));

D3DRS_FOGENABLE 에서 안개를 렌더링하라고 조건을 설정한 것이며,

D3DRS_FOGCOLOR 는 안개 색상을 설정하고,

D3DRS_FOGVERTEXMODE 는 안개 연산을 위한 알고리즘을 설정하고,

D3DRS_FOGSTART 와 D3DRS_FOGEND 는 안개의 시작 및 종료를 설정합니다.

매우 간단하지 않습니까. 안개를 렌더링하는 알고리즘은 D3DFOG_EXP, D3DFOG_EXP2 등으로 간단히 대체될 수도 있습니다.

우리는 단순하게 FOG 를 사용할 것임을 설정하고 관련 자료 및 연산을 "미리 정해진 형식"으로 설정하기만 하면 됩니다.

이렇게 "미리" 정해진 연산을 수행할 수 있도록 제공되는 기능이 바로 고정함수 파이프라인(Fixed Pipeline)입니다.

2. Shader, Programmable Pipeline

고정함수 파이프라인을 이용해서 왠만한 것들을 표현하는 것이 가능합니다. 하지만 시간이 지날 수록 사람들은 고정함수 파이프라인이 제공하지 않는 다른 특별한 표현을 하고자 하는 욕망을 품게 되었으며, 고정 함수 파이프라인의 성능에 대한 의구심을 품게 되었습니다.

예를 들면 "D3DFOG_LINEAR, D3DFOG_EXP, D3DFOG_EXP2 가 아니라 Volume Fog 를 사용하고 싶어요" 같은 요구가 생겨나게 된 것입니다. D3D 가 고정적으로 지원하는 기능이 아니기 때문에 사용자가 직접 구현해야 할 필요가 생긴 것입니다.

이러한 요구를 받아 들여 하드웨어 제조 업체와 마이크로 소프트는 Vertex Shader 와 Pixel Shader 라는 것을 발표하게 됩니다. 이 쉐이더를 사용하는 일련의 작업들은 하드웨어 상에서 처리되는 작업들에 대한 코드를 프로그래머가 직접 조작할 수 있다는 의미에서 프로그래밍 가능한 파이프라인(programmable pipeline) 이라고 불립니다.

Vertex Shader 는 정점 처리에 대한 부분이고 Pixel 쉐이더는 픽셀 처리에 대한 부분입니다. Pixel 쉐이더는 fragment 쉐이더라고 불리기도 하는데, 개인적으로는 프래그먼트 쉐이더가 더 정확한 의미를 전달한다고 생각합니다. 일반적으로 픽셀이라는 것은 화면에 찍히는 점 하나를 의미합니다. 하지만 프래그먼트는 그 점이 계산하기 위해서 필요로 하는 여러 가지 정보들을 모두 포함하는 개념입니다.

여기에서 우리가 눈치챌 수 있는 사실은 어떤 자료를 가지고 작업을 하느냐에 따라서 XXX Shader 라는 이름이 붙는다는 것입니다. 물론 자료에 따라서 수행할 수 있는 연산들은 다르겠죠. 이 시점에서 우리는 Direct3D 아키텍처를 살펴볼 필요가 있습니다.

출처는 http://www.lameproof.com/ 요기에서 뽑아왔습니다.

컬링의 종류는 조사한 바에 의하면 3가지가 있는거 같다.

1. Backface culling 
2. View frustum culling 
3. Occlusion Culling

2번, 3번은 질의로 나온 문제였는데... 보기 좋게 제대로 못 적었다. 컄컄컄

Backface Culling은  object 가 closed polygon 으로 구성되어있다고 가정할때, 각 face 의 방향이 시점의 반대쪽을 바라보고 있을때에는 찍을 필요가 없다는 것을 의미한다.

 Frustum 은 절단체라는 것인데, 이것은 피라미드 모양에서 위의 뾰족한 부분을 잘라낸 모양을 생각하면 된다. frustum 이란 개념이 왜 나오냐 하면, 월드상에서 인간의 눈에 보이는 부분을 골라내면 바로 frustum 의 모양을 하기 때문이다. 눈에 가까운 쪽은 작은 사각형쪽에 해당하고 멀리 있는 쪽은 큰 사각형쪽에 해당한다. 물론 인간의 시야는 무한히 먼 곳을 바라볼 수 있게 되어있지만, 보통 3d 엔진에서는 시야에 어느정도 한계를 두도록 되어있다. 예를 들면 눈으로 볼 수 있는 가장 가까운 거리는 10 이고 가장 먼 거리는 5000 으로 정하는 식이다. 폴리곤이 카메라에 너무 가까와져서 모델의 내부가 보인다던가 하는 일은 거리가 최소거리보다 작은 폴리곤을 출력할때 나오는 현상인 것이다

  frustum 을 활용하기 위해서는 frustum 의 자료구조를 디자인하고, 실제적인 데이타 (최소거리, 최대거리, fov) 등으로부터 frustum 데이타를 만들어내는 법을 알아야 한다. frustum 은 보통 6 개의 평면이 이루는 것으로 구현하게 되어있다. 즉 near plane, far plane, left plane, right plane, top plane, bottom plane 의 6 개가 그것이다. 

  그렇다면 실질적으로 월드를 구성하는 폴리곤이 화면상에 들어오는가 안 들어오는가를 판단하기 위해서는 어떻게 하는 것일까? 그것은 각각의 폴리곤이 6 개의 plane 의 안쪽에 속하는지를 검사하는 것이다. 

  plane 은 보통 카메라좌표계에서 정의되고, 월드상의 폴리곤은 월드좌표계상에서 정의되기때문에 서로 비교를 하려면 같은 좌표계상에 오도록 변환을 해야 한다. 카메라좌표계를 기준으로 하는 것이 좋을까 월드 좌표계를 기준으로 하는 것이 좋을까? 당연히 월드좌표계를 기준으로 하는 것이 좋다. 만약 카메라 좌표계를 기준으로 한다면 폴리곤이 1 만개일 경우, 월드->>카메라 변환을 1 만번 해야 하지만, 월드좌표계를 기준으로 하면 카메라->>월드 역변환을 평면의 갯수만큼, 즉 6 번만 해주면 되기 때문이다. 평면을 변환, 역변환하는 방법에 대해선 역시나 수학책을 참고하길 바란다. 

  이제 frustum 을 구성하기도 했고, 각각의 폴리곤이 frustum 에 속하는지 비교하는 방법도 알긴 했지만 이것만으로는 부족하다. 왜냐하면 수만개의 폴리곤이 화면에 찍히는지 안찍히는지 일일이 frustum 에 대해 검사를 해야하기 때문에 실질적으로 큰 소득을 얻지 못했기 때문이다. 어떻게 해야지 간단한 방법으로 (적은 수의 계산으로) frustum 안에 들어오는 polygon 만을 골라낼 수 있을까? 

  그 해답은 polygon 을 그룹을 지워놓고 나서, 그룹단위로 frustum 에 들어오는지를 판별하는 것에 있다. 예를 들어서 월드상의 인접한 폴리곤들을 100 개정도의 그룹으로 분리(partition 을 구성)를 해 놓은 다음에 그 그룹을 최대한으로 감싸는 bounding box 를 계산해놓고, bounding box 와 frustum 간의 포함관계여부를 검사를 하면 어떻게 될까? 물론 훨씬 계산량이 줄어들 수 있게 된다. 왜냐하면 그룹의 bounding box 가 frustum 과 전혀 충돌하지 않는다는 것을 알게 되면 (적은 수의 계산으로 알 수 있다) 그 그룹안에 포함된 수백개의 폴리곤들또한 전혀 frustum 에 속하지 않는 다는 결론을 내릴 수 있기 때문이다. 

  이 방법만 쓰더라도 폴리곤 한개씩을 frustum 에 대해 비교하던 방법보다는 훨씬 나은 효과를 얻을 수 있다. 참고로 폴리곤을 일정한 단위로 그룹을 짓는다는 것은, 각각의 폴리곤이 전혀 움직이지 않는다는 가정을 했기 때문에 가능한 것이다. 만약 폴리곤이 일부라도 움직이게 되면 그룹을 다시 짜거나, 또는 그룹의 bounding box 를 재계산 해야만 할 것이다. 

  이 방법은 좋긴 하지만 더 좋게 할 수 있는 방법이 더 많이 있는데, 그중 하나는 그룹을 계층적으로 구성하는 것이다. 말하자면 월드 전체를 커다란 한개의 그룹으로 일단 구성하고, 그 그룹을 어떤 기준에 의해서 2 개나 4 개, 혹은 8 개의 소그룹으로 나누고, 그 소그룹을 다시 또 기준에 의해서 소그룹으로 분할하는 방법을 말한다. 이런식으로 일정단계까지 (예를 들면 5 단계까지) 나누고 나면 월드 전체는 그룹들로 구성된 트리구조로 표현할 수 있게 된다. 하나의 그룹을 임의의 기울기의 평면을 사용해서 2 개의 소그룹으로 나누는 방법을 Binary Space Partitioning 이라고 부르고, x 축과 z 축의 직교된 평면을 이용해 4 개의 소그룹으로 나누는 방법을 Quad-Tree Partitioning 이라고 하고, x,y,z 축의 평면을 이용해 8 개의 소그룹으로 나누는 방법을 Oct-tree partitioning 이라고 한다. bsp 와 quad-tree, oct-tree 는 각각 구조에 따라 장단점이 있는데, 실질적으로 가장 기본이 되는 것은 bsp 라고 할 수가 있고, quad-tree 나 oct-tree 는 bsp 의 단계를 묶어서 간략화한 형태라고 할 수 있다. 그리고 quad-tree 는 높낮이의 변화가 심하지 않은 2.5 차원 배경을 표현할때 효과적이고, oct-tree 는 높낮이의 변화가 심한 3 차원 배경을 표현할때 효과적이다. 

 이렇게 월드를 그룹으로 나눌때에는 몇가지 주의할 사항이 있다. bsp 건 quad-tree 건 oct-tree 건 평면을 이용해서 폴리곤들을 나누게 되어있는데, 어떤 경우건 폴리곤이 두개의 그룹간에 걸치게 되는 경우가 있다. 이런 때에는 어떻게 해야 할까? 

  첫번째 방법은 폴리곤을 2 개로 쪼개서 각각의 그룹에 하나씩 보내주는 경우이다. 이 경우에는 각각의 그룹은 폴리곤을 완벽하게 포함시키게 되지만, 폴리곤의 갯수가 늘어나게 된다는 단점이 있다. bsp 를 이용해서 은면제거까지 해야한다면 반드시 이 방법을 써야만 한다. 

  두번째 방법은 하나의 폴리곤을 양쪽에 모두 포함시키는 것이다. 이 경우에는 그룹이 폴리곤을 완전히 포함시키지 못하므로 후에 추가적인 테스트가 필요하거나 정확성이 약간 떨어지게 되고, 은면제거의 방법으로 활용할 수 없게 되지만 폴리곤의 갯수는 유지된다는 장점이 있다. 그리고 한 폴리곤이 두번 표시되지 않도록, 폴리곤을 표시했는지 여부를 각 폴리곤마다 기록해줘야 할 필요가 있다. 근래에는 보통 두번째 방법을 많이 쓰는 것으로 알고 있다. 내가 만들었던 엔진에서는 quad-tree 에 두번째 방법을 주로 이용했다. 

  실질적으로 VFC 를 이용해서 화면상에 복잡한 배경을 찍는다는 것은 3 개의 단계로 나뉘어진다 

  첫번째는 월드상의 모든 폴리곤들을 적절한 구분방법에 의해 그룹의 트리구조를 만드는 것이다. 이 구조를 보통 SceneGraph 라고 부른다. 배경(Scene) 이 어떤 구조로 나타나있는지를 표현하는 그래프라는 의미이다. bsp, quad-tree, oct-tree 는 scenegraph 의 종류를 일컫는 말이다. 이 작업은 배경이 변하지 않는 한에는 처음에 1 번만 해두면 된다. 고정된 배경이기 때문에 미리 계산을 해놓을 수 있는 것이고, 미리 계산을 해 놓기 때문에 속도를 빠르게 할 수 있는 것이다. SceneGraph 의 각 요소를 node 라고 하고, node 가 가지는 내용은, node 가 월드상에서 담당하는 범위 (bounding box), node 가 가진 폴리곤들의 리스트, node 에 딸린 자식 node 의 리스트를 나타낸다. 

  두번째는 현재 카메라의 시점을 계산해서 frustum 을 새롭게 만들어 놓는 것이다. (물론 월드 좌표계로) 이것은 시점이 바뀔때마다 매번 해야 하는 일이다. 

  세번째는 SceneGraph 의 각 노드에 대해 frustum 과의 충돌체크를 수행하고 (노드의 bounding box 와 frustum 간의 충돌체크) 만약 frustum 과 조금이라도 충돌하였으면 해당 scenegraph 의 자식 노드들에 대해 다시 각각 충돌체크를 수행하는 것이다. 만약 node 가 자식 노드가 없다면 (즉 최 말단 노드라면) 노드가 갖고 있는 폴리곤들을 화면에 그대로 찍으면 된다. 

  여기서 중요한 점은 각각의 노드들은 자식노드들을 완전히 포함하고 있기 때문에, 하나의 노드가 frustum 과 완전히 충돌하지 않는다는 것을 알게 되면, 그 자식노드들은 전혀 계산할 필요가 없다는 점이다. 이 원리에 의해서 수만개의 폴리곤들이 몇백번 이내의 계산에 의해서 훨씬 적은 수의 화면상에 들어오는 폴리곤들로 컬링되는 것이다 

Occlusion culling 을 사용할지 여부는 내가 표현하고자 하는 배경이 어떤 형태를 지니는가에 따라 달라진다. 즉, 배경이 실외중심으로 되어있느냐, 실내 중심으로 되어있느냐에 따라서 달라진다. Occlusion 이라는 것은 가리기라는 뜻인데, 완전히 불투명힌 벽같은 것 뒤에 완전히 가려진 물체는 View Frustum 상에 들어온다고 하더라도 표시할 필요가 없다는 점에 착안한 것이다. 

 그런데 실외의 경우에는 occlusion 의 발생여부를 따지기가 힘들고, 대부분 frustum 상에 들어온 물체를 모두 표현해야 하기 때문에 실외 표현 전용엔진에서는 occlusion culling 은 도입하지 않는다. 

  하지만 실내의 경우, 커다란 경우가 여러개의 방과 복도로 나뉘어져 있고, 시점이 그 내부에서 이동한다고 할때에는 상당히 많은 부분이 벽에 의해서 가려지게 된다. 이것을 활용하기 위한 방법이 occlusion culling 이다. 

  occlusion 의 체크또한 상당히 많은 량의 계산을 필요로 하게 된다. 따라서 배경이 고정되어있다는 것을 감안하여 최대한 많은 정보를 미리 계산해놓을 필요가 있는데, occlusion 정보를 미리 계산해놓은 것을 PVS (Potential Visible Set) 라고 한다. PVS 는 말 그대로 "보일 가능성이 있는 것들의 집합" 이라는 의미이다.

 예를 들어서 건물이 있는데, 건물을 10 개의 방과 복도로 나눌 수 있다고 생각하자. 각 방과 복도 사이에는 문(portal) 과 창이 존재하기 때문에 한 지역 안에서 다른 지역도 볼 수가 있지만, 모든 지역을 다 볼 수는 없다고 가정할 수 있다. 예를 들어서 방 1 에서는 복도를 볼 수 있고, 복도 너머의 방 2 와 방 3 을 볼 수 있다는 점을 미리 계산을 많이 해서 알아낼 수가 있다고 하면, 시점이 방 1 에 있을 때에는 먼저 pvs 정보에 입각하여 방1 (자신) 과 방2, 방3, 복도에 해당하는 폴리곤만을 VFC 할 수 있다는 의미이다. 또한 여기에 3 차원적 clipping 을 더 추가하여 portal 단위로 보이는 부분을 더욱 압축하는 방법도 생각해볼 수 있다. 이것은 portal rendering 이라고 불린다.