[CG] Linear-Speed Vertex Cache Optimisation - 1

Tom Forsyth 라는 Graphics Coder 가 소개한 Optimization 테크닉을 번역한 내용이다. (28th September 2006 발표)
 Linkedin과 본인 블로그에 따르면 Intel을 비롯한 graphics 관련 회사들에서 경력을 쌓은 이 분야의 전문가로 보인다. 내가 수강한 Computer Graphics 교수님이 제공한 자료를 통해 알게 됐다.

 

1. Introduction
   : 이 페이퍼는 크기가 알려지지 않은 다양한 Hardware Vertex Cache에 적합하도록 색인된(indexed) 삼각형 목록을 최적화하는 알고리즘을 소개한다. 이 방법은 다양한 cache 크기와 교체 정책에 보편적으로 적합하며 mesh의 삼각형 수에 비례하는 선형적인 시간(Linear time)과 공간에서 빠르게 실행된다는 장점이 있다. 또한 가장 잘 알려진 대체 알고리즘의 성능과 몇 퍼센트 이내이며 필요한 경우 쉽게 이해하고 조정이 가능하다.
   
   
2. Backgroud
   : indexed primitives는 오늘날 그래픽 하드웨어에서 가장 일반적인 rendering primitives로서 strip과 fan을 대체했다.각 삼각형을 렌더링할 때 사용하는 정점을 렌더링하기 전에 처리(예: 화면 공간(screen space)으로 변환 및 다양한 방식으로 조명)해야 한다. indexed rendering hardware는 일반적으로 작은 크기의 vertex cache를 사용해 최근에 렌더링된 삼각형 간에 공유되는 정점을 다시 처리하지 않는다. 적당한 크기의 cache(일반적으로 12~24개의 정점)를 사용하면 기존의 비색인(unindexed) strip 및 fan 모델보다 vertex processing pipeline의 부하가 훨씬 줄어들어 삼각형당 필요한 작업량이 줄어드는 경우가 많다.
   
   그러나 vertex cache는 삼각형의 순서에 따라 그 특성에 맞게 최적화된다. 삼각형이 임의의 순서로 전송되면 정점은 거의 항상 cache를 놓치게 되어(miss) 아무런 이득도 얻지 못한다. 삼각형이 클러스터(덩어리)로 전송되 각 삼각형이 이전에 렌더링된 삼각형에 가까워지면 더 많은 정점이 cache에 남아있을 가능성이 높아진다.
   
   따라서 삼각형을 렌더링할 올바른 순서를 찾는 것이 vertex processing pipeline의 작업을 줄이는 데 중요하다. 근본적인 문제는 mesh는 일반적으로 2차원 surface이며 cache는 1차원 데이터를 스트리밍할 때 가장 효율적이라는 점입니다. 따라서 이상적인 순서는 명확하지 않다.
   
   [Hoppe: 또 다른 computer graphics 연구자 Hoppe에 따르면]
   특정 크기의 주어진 캐시에 대해 삼각형의 순서와 교체 정책을 최적화하는 알고리즘에 대해 논의했다. 이 알고리즘은 게임 콘솔과 같이 고정되어 알려진 하드웨어 대상에 유용하다. 그러나 하드웨커 cache의 크기나 유형이 다른 경우에는 새로운 구성에 맞게 알고리즘을 다시 실행해야 한다.
   
   PC나 매킨토시 등 여러 플랫폼에서 동일한 art를 여러 콘솔에 출시할 때 vertex cache의 정확한 크기와 유형을 제작 시점에 알 수 없으며, 정확한 구조가 독점 정보인 경우가 많기 때문에 런타임에도 알 수 없는 경우가 많다. 이러한 이유로 [Bogomjakov]는 다양한 cache 크기와 유형에 적합하고 특정 약점이 없는 단일 시퀀스인 "universal rendering sequence(범용 렌더링 시퀀스)"에 대해 논의한다.
   
   Vertex cache의 효율성을 나타내는 일반적인 방법은 vertex cache의 miss 횟수를 mesh의 삼각형 수로 나누는 것이다. 이렇게 하면 삼각형당 처리해야 하는 평균 점정 수인 Average Cache Miss Ration(ACMR, 평균 캐시 미스 비율)이 나온다.
   
   
3. Outline
   : 제시된 알고리즘은 LRU(Least Recently Used)를 사용하는 vertex cache를 기반으로 한다. 각 정점은 LRU cache 내의 위치 (즉, 얼마나 최근에 사용되었는가)에 따라 "score(점수)"가 할당되는데, 이는 삼각형이 사용하는 정점의 점수를 합산한 값이다. mesh의 어떤 삼각형을 다음에 sequence에 추가할지 고려할 때 점수가 가장 큰 삼각형을 추가한다. 그런 다음 해당 삼각형의 정점 3개를 cache의 맨 위로 이동하거나 추가하고 다른 정점은 뒤로 밀어낸다(shuffle down). 이 알고리즘은 greedy로 선택한 삼각형을 역추적하거나 더 앞을 참고하지 않는다.
   
   대부분의 하드웨어는 단순성과 속도를 위해 FIFO-replacement cache를 사용하지만, 여기서는 LRU-replacement cache를 사용한다. 이 cache는 실제 그래픽 카드에 있는 실제 "hardware cache"와는 달리 "modelled cache(모델링 된)"라고 한다. modeled cache가 FIFO가 아닌 LRU인 이유는 이 알고리즘이 생성하는 단일 삼각형 시퀀스가 다양한(일반적으로 미리 알 수 없는) hardware cache와 교체 정책에서 사용할 수 있도록 고안되었으며, 잘못된 크기의 FIFO cache로 모델링하면 실제 hardware cache가 부정적이고 병적인(pathodological) "thrashing"되거나 활용도가 낮아지기 때문이다. 실제로 LRU modelled cache는 일반적인 하드웨어와 일치하지 않더라도 보다 일관된 sequence를 생성한다.
   
   modeled cache 크기는 모든 hardware cache를 포함할 수 있을만큼 '충분히 커야' 한다. [Hoppe]에 따르면 32개 항목보다 큰 cache에서 어떤 하드웨어도 큰 이점을 얻을 가능성이 거의 없으므로 여기서는 32개를 modeled cache의 크기로 선택했다. 64개로 modeled cache를 실험했지만 최종 cache 성능에는 큰 차이가 발경되지 않았으며 알고리즘이 그저 느리게 실행되었다.
   
   앞서 설명한 바와 같이, 이 알고리즘은 앞을 내다보거나(lookahead) 역추적(backtracking)하지 않는 greedy 알고리즘이다. rendering sequence에 삼각형을 추가하기로 선택하면 그 결정을 유지한다. 삼각형의 선택은 정점과 삼각형 점수를 통해 추후 선택에 영향을 미치지만, 추후의 선택에 영향을 주기 위해 삼각형이 선택되지는 않는다. 이러한 방식으로 알고리즘은 mesh의 삼각형 수에 비례하는 linear time으로 실행될 뿐만 아니라 매우 빠르게 유지된다. 이 속도는 artist가 모델을 빠르고 정확하게 미리 볼 수 있어야 하는 piepeline 제작에 매우 유용하다.
   
   또한 몸체와 얼굴의 일부를 결합해 합성 캐릭터를 만드는 등 동적으로 생성되는 콘텐츠가 있는 게임에서 결과 mesh를 hardware vertex cache에 맞게 전체적으로 최적화해야 효율성을 극대화할 수 있지만, 모든 부분이 하나의 mesh로 결합될 때까지는 이 작업을 수행할 수 없다. RPG나 MMO와 같이 수많은 잠재적 신체 모양이 동적으로 지정되는 게임에서는 매초마다 새로운 mesh가 나타날 수 있으며, mesh를 최적화하는 데 상당한 처리 시간이 걸리는 알고리즘은 비생산적이다.

 

 

 

참고

- https://tomforsyth1000.github.io/papers/fast_vert_cache_opt.html