[GPU] Occlusion Culling (Early-Z vs. Occlusion Queries)

by

What is Occlusion Culling? (출처 1)

간단히 설명하면 필요 없는 Geometry(지형, 물체 등)를 그리지 않도록 불필요한 연산을 제거하는 기술이다. 보통 모니터에 보이는 화면에 벗어난 물체 또는 다른 물체에 의해서 가려지는 물체(Occlusion) 등에 대한 연산을 수행하지 않게 하여서 Rendering 성능을 향상하는 방법을 의미한다. Occlusion Culling은 크게 “Occlusion Query”와 “Early-Z” 방법을 사용하여서 필요 없는 Rendering 연산을 제거한다.

 

What is Early-Z Rejection? (출처 1)

요즘(?) 생산되는 대부분의 GPU는 Early-Z를 지원한다. Early-Z Rejection은 Rasterization Stage에서 수행한다. 출처 5에 따르면 Rasterization 연산을 완료 후 Frame-Buffer (FB)에 저장된 Depth Value (Z 값)과 비교하여서 연산이 필요 없으면 Fragement 연산을 수행하지 않는 것이다. 예를 들어 Rasterization연산 후 FB에 저장된 Z 값보다 뒤에 있어서 그릴 필요가 없으면 해당 연산을 수행하지 않는다. Fragement 연산을 제거하면 Fragement 연산 + Texture 로딩(Memory 로딩) 연산을 줄일 수 있다. Early-Z Rejection을 효과적으로 사용하기 위해서는 프로그래머가 Object를 Front-to-Back 순서로 정렬을 해야 한다. 앞에 그려진 Object 먼저 FB의 값을 업데이트하면 뒤에 그려지는 Object는 Early-Z Rejection을 통해서 연산을 제거할 수 있다.

 

What is Occlusion Queries? (출처 1, 2)

Occlusion Queries는 Early-Z와 비슷하게 필요 없는 연산을 제거하는 것이다. Early-Z와 달리 Occlusion Queries는 Geometry Level에서 연산을 제거한다. Occlusion Queries는 Rendering 연산을 수행하기 전에 해당 Rendering 연산의 결과가 FB에 쓰일지 여부를 먼저 확인하다. 만약 Rendering 연산의 결과가 FB에 쓰여지지 않는다고 판단되면(불필요한 연산) 해당 Rendering 연산을 수행하지 않음으로 불필요한 연산을 제거한다.

  • MK: 아마 Drawcall을 완전히 수행하지 않음으로 Geometry Level에서 연산을 제거한다는 의미인 것 같다.

Occlusion Queries의 핵심은 해당 Object (Rendering 결과)가 불필요한 연산인지를 판단하는  부분이다. 최근(?) 기술은 이전 프레임의 정보를 활용하는 방법을 사용한다. 카메라가 급격히 변하지 않는 경우 현재 그려질 Frame은 이전에 그려진 Frame과 큰 차이가 없다. 이 경우 이전 프레임에서 불필요하다고 판단된 연산은 이번 Frame에서도 역시 불필요할 확률이 높다.

  • MK: 간단히 설명했는데 상세한 알고리즘은 출처 1, 2, 3에서 확인 할 수 있다. 최선을 다해서 설명을 번역해 볼 계획이지만 충분한 설명이 가능할지 모르겠다.

Occlusion Queries의 경우 이득을 보는 장면과 이득을 전혀 얻지 못하는 장면(오히려 Occlusion Queries를 사용하는 경우 성능 하락이 발생)이 나뉘어 있다. 예를 들어서 엄청난 큰 도시의 중간에 메인 캐릭터가 있는 장면을 그린다고 가정해보자. 메인 캐릭터가 도시를 걸어가고 있다고 가정하자. 메인 캐릭터 시각에서는 제일 앞에 있는 물체/빌딩만을 육안으로 불 수 있지만 그 물체/빌딩 뒤에 물체/빌딩은 보이지 않기 때문에 Rendering 연산을 수행할 필요가 없다. 이런 장면의 경우 Occlusion Queries를 사용하여 Rendering 성능에 이득을 볼 수 있다.

반면 반대로 성능적으로 손해를 볼 수 있는 장면은 도시를 하늘에서 내려다보는 경우이다. 도시를 위에서 내려다보는 경우 모든 도시의 물체/빌딩을 Rendering 해야 한다. 이런 경우 Occlusion Queries를 사용해서 물체/빌딩의 연산이 필요한지 판단하는 연산이 오히려 전체 Rendering 성능을 떨어뜨리게 된다.

Occlusion Queries 역시 프로그래머가 물체를 먼저 Front-to-Back 순서로 정렬해야 한다. 이와 더불어 훨씬 많은 작업이 필요하다. 아래 출처 1, 2에서 정리된 Occlusion Queries에 Algorithm에 대해서 아래 정리해보았다. Algorithm을 보면 프로그래머가 해야 하는 추가적인 작업을 확인 할 수 있다.

 

Naive Occlusion Culling Algorithm (출처 1, 2)

Naive Algorithm은 아래와 같은 순서로 실행한다.

  1. 먼저 모든 Object를 Front-to-Back 순서로 정렬한다.
  2. 각 Object에 대해서 아래의 절차를 수행한다.
    1. Occlusion Query를 시작
    2. Framebuffer/Depth Buffer에 값을 업데이트하지 못하도록 변경 (추가로 불필요한 부분을 Disable 함)
    3. Object를 간단한 모양으로 변경하여서 해당 Object가 Rendering 되는지 확인함
    4. Occlusion Query를 종료하고 결과를 Return 함
    5. 만약 Occlusion Query 결과가 True (앞에 테스트 결과에서 해당 Object를 그려야 한다는 결과를 얻은 경우를 의미함. 보통 그려야 하는 Pixel의 수를 Return 한다고 함)이면 해당 Object의 Rendering 연산을 수행함

지금 설명한 방법을 사용하면 그냥 Rendering 하는 거보다 느릴 확률(?)이 매우 높다. 모든 Object의 Occlusion Query 연산을 수행해야 하므로 바로 Rendering 하는 방법이 더 효율적이다. 이러한 단점을 해결하기 위해서 Hierarchical 구조를 활용한다.

 

Hierarchical Stop-and-Wait Method Algorithm (출처 2)

  • MK: 출처 2의 설명으로 완전히 이해하지 못해서 추측을 조금 추가하였다.

그림 1: Tree (Hierarchical) 구조를 사용하여 Area를 나눈 예제 그림 

Hierarchical Stop-and-Wait Method는 공간 분할 (KD tree, BSP tree) 기법을 사용하여 모든 Object에 대한 Occlusion Query 연산을 수행하지 않는 것이다. 공간 분할 기법은 보통 Tree 구조를 가짐으로 Hierarchical 구조라고 한다. 그림 1은 Tree를 사용해서 공간을 분할한 예제 이미지이다. 예를 들어 그림 1에서 영역 3, 4 에 위치한 물체만 Rendering을 한다고 가정하면 Node를 4번만을 거치면 필요한 Object를 알 수 있게 된다. 그림 1은 작은 예제이므로 4번이 많아 보이지만 Object의 수가 많거나 공간이 넓으면 효율성이 증가한다.

Hierarchical 구조를 사용한 Occlusion Query Algorithm은 아래와 같다.

  1. Occlusion Query 연산을 시작 (Stop & Wait)
  2. 현재 Pointing하고 이는 Node의 Visible 여부를 테스트하여 Visible 한 경우 아래 절차를 반복한다.
    1. 만약 해당 Node가 Leaf Node인 경우, Node에 있는 모든 Object에 대한 Rendering 연산을 수행한다.
    2. 만약 해당 노드가 Interior Node (Leaf Node가 아닌 경우), Child 노드에 대해서 상위 2번  Step을 반복한다.

위 알고리즘은 기존 Naive 한 버전보다 훨씬 빠를 수도 있다. 하지만, 크게 2가지 문제가 있다.

그림 2: CPU/GPU Stall이 발생 (출처 2)

  1. Stalls: 위 그림 2는 Query의 동작 순서이다. Query의 결과를 기다림으로 Rendering 연산을 수행할 수 없어서 CPU/GPU Stall이 발생한다.
  2. Query Overhead: Visible한 Object가 많은 경우 Query에 따른 Overhead가 커지는 경향이 있다.

 

Coherent Hierarchical Culling Algorithm (출처 2)

Hierarchical Stop-and-Wait Method에서 문제가 되는 Stalls와 Query Overhead를 제거하기 위해서 크게 2가지 아이디어를 제안한다.

  • 아이디어 1: Being Smart and Guessing

그림 3: Guessing을 통한 Query 연산 제거 (출처 2)

Query를 기다리기보다 추측을 통하여서 Query 연산을 제거하는 방법이다. 보통 Graphic 연산에서 카메라 위치가 급격히 달라지지 않는 경우 앞 Frame의 결과와 이번에 그려질 Frame의 결과 차이는 많이 발생하지 않는다. 이렇게 이전 Frame과 다음 Frame의 결과 차이가 적은 것을 Temporal Coherence라고 한다. 그림 3은 Guessing을 통한 Query 연산을 제거하는 예제를 보여준다 (출처 2). 그림 3의 초록색 부분은 앞 Frame에서 Rendering 된 결과이므로 Query 연산을 하지 않고 바로 Render 연산을  시작한다. 파란색의 경우 앞 Frame에서 보이지 않았던 결과였으나 이번 Frame에서는 보일 수도 있기 때문에 Query 연산을 수행한다. 위와 같은 Guessing 방식으로 Query 연산을 제거하여서 Query 결과를 기다리기 위한 Stall을 제거한다.

  • 아이디어 2: Pull Up

그림 4: Interior Node 연산 제거 (출처 2)

중간노드 (Interior Node)의 연산을 제거하기 위해서 필요 없는 중간 노드에 대한 Query 연산을 수행하지 않는다. 아이디어 1과 동일하게 이전 Frame의 결과를 기준으로 불필요한 중간노드 연산을 제거한다. 그림 4는 불필요한 Query 연산을 제거하는 그림이다. 초록색 부분은 앞 Frame에서 그려진 결과로 해당 노드에 대한 Query 연산을 수행하지 않아도 된다. 파란색의 경우 Query 연산을 수행해야 하는 부분이다.

MK: 솔직히 정확한 동작 원리를 완전히 이해하지 못했다. 개인적으로 아이디어 1과 아이디어 2는 동일한 효과인 것으로 추측된다. 이전 Frame의 결과를 기준으로 그려졌던 Object를 포함하는 노드 (부모 포함) 모두 Query 연산을 수행하지 않고 바로 Rendering 연산을 수행한다는 의미인 것 같다. 새로 그려지는 프레임에서 결과가 달라질 수도 있기 때문에 (이전 Frame에 없었던 새로운 Object가 보여야 하는 경우) 앞 Frame에서 보이지 않았던 Node는 Query 연산을 수행하여서 Rendering 여부를 판단한다는 의미인 것 같다.

아래 Pseudocode는 Coherent Hierarchical Culling Algorithm 이다 (출처 2).

TraversalStack.Push(hierarchy.Root);

while ( not TraversalStack.Empty() or not QueryQueue.Empty() ){

//--PART 1: process finished occlusion queries
while ( not QueryQueue.Empty() and (ResultAvailable(QueryQueue.Front()) or TraversalStack.Empty()) ) {
	node = QueryQueue.Dequeue();

	// wait if result not available
	visiblePixels = GetOcclusionQueryResult(node);
	if ( visiblePixels > VisibilityThreshold ) {
		PullUpVisibility(node);
		TraverseNode(node);
	}
}

//--PART 2: hierarchical traversal
if ( not TraversalStack.Empty() )
{
	node = TraversalStack.Pop();
	if ( InsideViewFrustum(node) ) {

		// identify previously visible nodes
		wasVisible = node.visible and (node.lastVisited == frameID - 1);

		// identify nodes that we cannot skip queries for
		leafOrWasInvisible = not wasVisible or IsLeaf(node);

		// reset node's visibility classification
		node.visible = false;

		// update node's visited flag
		node.lastVisited = frameID;

		// skip testing previously visible interior nodes
		if ( leafOrWasInvisible ) {
			IssueOcclusionQuery(node);
			QueryQueue.Enqueue(node);
		}

		// always traverse a node if it was visible
		if ( wasVisible ) {
			TraverseNode(node);
		}
	}
}

TraverseNode(node){
	if ( IsLeaf(node) )
		Render(node);
	else
		TraversalStack.PushChildren(node);
}

PullUpVisibility(node){
	while (not node.visible){
		node.visible = true;
		node = node.parent;
	}
}

 

A Little Reminder (출처 1)

  • Geometry 수가 적은 경우: 성능 향상이 제한적일 수 있다. 특히 CPU가 느리고 GPU가 빠른 경우 Occlusion Query 기술은 딱히 도움이 되지 않는다.
  • Geometry 수가 많은 경우: 대부분의 상황에서 성능 향상이 있다. 모든 Object에 대한 Occlusion Query 테스트를 진행하여도 크게 성능이 떨어지지 않는다.

출처

  1. http://developer.download.nvidia.com/books/HTML/gpugems/gpugems_ch29.html
  2. https://developer.nvidia.com/gpugems/GPUGems2/gpugems2_chapter06.html
  3. https://slideplayer.com/slide/8972133/
  4. http://blog.naver.com/PostView.nhn?blogId=gomdev&logNo=220112312081&parentCategoryNo=&categoryNo=14&viewDate=&isShowPopularPosts=true&from=search
  5. (Unite Seoul 2019) https://www.youtube.com/watch?v=hQSiDQidyGk

Leave a Comment