[CG] Linear-Speed Vertex Cache Optimisation - 4

7. Results

 

이 알고리즘을 개발하는 동안 다양한 테스트 mesh가 사용됐다. 그 중 4개에 대한 결과가 여기에 나와있다. 이 중 3개는 일반적인 인터랙태브(예: 게임) mesh를 대표하며, 1개는 알고리즘의 건전성 검사에 사용된 보다 이상화된 mesh다. 이상화된 mesh의 결과는 지형 높이 필드(terrain height-fields)나 세밀하게 tesellated 모델과 같이 매우 규칙적인 표면과 관려히 있지만, 알고리즘의 방향에 큰 영향을 미치지는 않았으며, 보다 현실적인 mesh를 훨씬 더 중요하게 고려했다.

 

mesh의 종류는 다음과 같다:

• GrannyRocks: 흔들 의자에 앉은 할머니 mesh다. Grann Viewer(http://www.radgametools.com/gradown.htm) 의 일부로 제공된다. 이 버전의 mesh에는 많은 PC 및 콘솔 게임에서 일반적으로 사용된 30개의 뼈대 덩어리(30-bone chuncks)로 분할됐다. 각 덩어리의 크기는 1000개 미만의 삼각형이었으며, 각 덩어리는 개별적으로 최적화되어 각각 별도의 렌더링 호출로 제출됐다. ACMR은 모든 덩어리에 대해 총합으로 제공된다. 
• RaybackSplit: 이족 보행 공룡형 creature(Granny SDK의 일부로 제공). 이 역시 30개의 뼈대 덩어리로 분할되었다. 뼈 덩어리의 크기는 500~1500개의 삼각형이다.
• RaybackWhole: 동일한 공룡 mesh지만 이번에는 덩어리로 분할되지 않고 texture의 이음새가 거의 없는 단일 550개의 삼각 mesh(5500-tri mesh)다.
• Sphere: 각 면이 1024개의 삼각형(각 면에 32개)으로 tesellatd된 icosahedron이다. 총 20480개의 삼각형ㅇ고 이음새가 없다(no seams.

이 알고리즘은 32개의 항목으로 구성된 modeled cache를 사용해 각 mesh에서 수행됐다. 64개의 항목도 시도했지만 출력에 거의 차이가 없는 것으로 나타났으며 알고리즘이 더 느리게 실행됐다. 그런 다음 단일 출력을 다양한 크기의 이상적인 FIFO cache에 공급했으며, 그 결과 ACMR이 아래 표에 나와있었다. 1024개 항목의 FIFO cache는 "완벽한 cache"의 상항으로 의도됐으며, 실제로 1024개보다 적은 덩어리가 있는 mesh의 경우 렌더링 순서에 관계없이 실제로 완벽한 값을 나타낸다. 실제 하드웨어에는 일반적으로 12~24개의 엔트리가 있으며, 추가 엔트리로 인해 추가 하드웨어 영역에 대한 이점(returns)이 감소하기 전에는 32개를 유용한 cache의 상한으로 간주하는 경우가 많다.

 

4개의 엔트리 cache는 기존의 삼각형 및 사각형 strip을 염두에 두고 설계된 구형 하드웨어를 모방하기 위한 것이다. ACMR 1.0은 기존의 비 인덱싱 strip이 생성할 수 있는 최고 점수를 나타내며, 여기서는 그보다 훨씬 나쁜 결과를 볼 수 있다. 그러나 이러한 종류의 하드웨어의 효율성을 높이려는 시도는 다른 모든 cache 크기의 효율성을 크게 떨어뜨리는 것으로 나타났다. 이와 같은 하드웨어는 이제 다른 측면에서 볼 때 너무 오래되고 느리기 때문에 관련성이 없는 것으로 간주되므로 여기서는 설명으로만 수치를 남겨두었다. 이 하드웨어가 어떤 이유로 여전히 특정 대상인 경우(예: 일부 구형 및 휴대용 콘솔은 여전히 비색은 렌더링을 사용함), 알고리즘 중 하나를 싱해나는 것이 좋다.

 

Hardware cache size	4	8	12	16	20	24	28	32	1024
GrannyRocks	1.556	0.908	0.820	0.797	0.781	0.776	0.771	0.765	0.732
RaybackSplit	1.559	0.893	0.791	0.769	0.755	0.747	0.738	0.730	0.695
RaybackWhole	1.596	0.874	0.756	0.727	0.713	0.703	0.691	0.682	0.647
Sphere	1.785	0.888	0.740	0.715	0.702	0.691	0.681	0.672	0.529

 

cache에 더 많은 항목이 추가될 수록 ACMR은 지속적으로 감소한다는 점에 유의하자. 모든 cache 효율성 측정에 동일한 렌더링 순서가 사용되었다는 점 역시 중요하다. 알고리즘은 각 cache마다 다시 실행되지 않았으며 실제로 어떤 크기의 hardware cache에서 실행될지 전혀 알 수 없다. 보시다시피, 특정 cache 크기에 대한 선호도가 병적인 사례 없이 ACMR이 일관되고 원활하게 감소한다. 이는 목표 cache 크기를 알아야 하는 다른 알고리즘과 대조적이다. 추측(guess)이 너무 크면 알고리즘이 더 작은 cache를 과도하게 사용해 성능이 저하될 수 있고, 추측(guess)가 너무 작으면 알고리즘이 더 큰 cache 크기로 인한 이점을 거의 보이지 않는다.

 

흥미로운 점은 Hoppe가 에측한 대로 32개 엔트리 cache가 (비현실적으로 큰) 1024개 엔트리 cache의 성능에 매우 근접하다는 점이다. 대부분의 경우 16개 엔트리에서 32개 엔트리로의 개선은 32개 엔트리에서 1024개 엔트리로의 개선만큼이나 크다. 이 알고리즘이 완벽에 가까운 ACMR에 매우 근접한 순서를 생성하는 것을 보면 안심할 수 있다(reassure).

 

예외는 매우 규칙적인 sphere tesellation으로, 32개 엔트리와 1024개 엔트리 사이에 상당한 차이가 있다. 이는 다른 테스트 mesh의 정점 수가 충분하지 않아 추가 cache 크기의 이점을 충분히 활용하지 못하기 때문일 수 있다.(RaybackWhole의 정점수는 5500개이지만 texturing 제약 조건으로 인해 이음새가 상당히 많음), mesh의 극도로 규칙적인 특성으로 인해 더 큰 cache가 더 잘 작동하기 때문일 수 있다. 경험상 대부분의 실제 게임 mesh는 이러한 특성을 공유하지 않는 것으로 알려져 있다. 삼각형의 무한히 큰 plane과 완벽한 cache를 위한 완벽한 ACMR은 삼각형당 0.5개의 정점이지만, 실제 mesh는 이러한 규칙성을 갖지 않으며 많은 이음새와 가장자리, 기타 불연속성을 포함하고 있어 cache의 성능을 제한할 수 있다. 그럼에도 불구하고 이러한 가정을 확인하기 위해 더 큰 실제 mesh에서 결과를 얻는 것이 유용할 것이다.

 

아직 다른 vertex-cache 방법과 비교는 이루어지지 않았다. 향후 이 작업이 숭해될 수 있기를 발한다. 그러나 32개 엔트리 cache 크기와 후자의 두 mesh를 사용한 [Bogomjakov]의 결과를 눈으로 비교해보면 두 알고리즘 모두 약 0.68의 ACMR을 생성하는 것으로 나타났다. 여기에 표시된 처음 두 개의 mesh는 참조된 다른 논문에서 표시된 것보다 훨씬 작은 mesh 덩어리를 가지고 있다. 덩어리가 작을수록 더 많은 가장자리를 가지므로 최상의 경우 경우에 나타나는 성능이 떨어진다.(실제로 GrannyRocks의 경우 1024개 엔트리 cache가 각 mesh 덩어리 전체에 들어갈 수 있으므로 렌더링 순서는 0.732의 ACMR보다 더 나은 성능을 낼 수 없다.)

 

 

여기까지가 해당 페이퍼의 결과까지의 번역이고, 이후에도 Future Work와 Additional Notes가 있지만, 필요시 추후에 진행하도록 하겠다. 아직 직접 구현과 테스트를 해보진 않았지만, 단순히 indexing을 사용해 정점을 재활용하는 것이 아닌 점수 계산을 통한 LRU cache 사용으로 인해 최적화의 이점이 나타난다는 것으로 보인다.

 

참고

- http://eelpi.gotdns.org/papers/fast_vert_cache_opt.html