[CG] Linear-Speed Vertex Cache Optimisation - 3

5. The Constants

 

위 코드에 사용된 4개의 상수는 추측과 판단, 며칠 동안의 무차별(brute-force) 대입을 통해 아주 전형적인 데이터 세트와 아주 전형적인 hardware cache 구조의 시뮬레이션을 통해 전송된 결과를 종합해 가장 좋은 점수를 얻은 것으로 결정되었다. 아직 발견되지 않은 더 나은 설정과 값이 존재할 가능성도 있다. 또한 점수에 거듭제곱 함수를 사용하는 것이 적절한 함수인지 여부와 다른 함수나 사용자가 커스터마이징한 look-up-table을 사용하는 것이 더 나을 결과를 낳을 수도 있다. 그러나 도출된 결과는 최적이라고 간주되는 값에 상당히 근접하며, 나머지 개성 사항은 거의 없을 것으로 보인다. 요약하자면, 이러한 값은 대부분의 목적에 "충분히 좋은" 것으로 보인다.

 

참고로, 4개의 상수가 모두 "정상" 수치에 가깝다는점이 흥미롭다. 1.5, 0.75, 2.0, 0.5 값들은 거의 지루할 정도로 평범해 보인다. 그러나 담금질 과정에서 이들 모든 값에 대해 최소 +/- 0.5의 범위에서 0.05씩 증가시켜가며 다양한 가능성을 고려했다. 이 값들이 담글질 과정 시작시 사람의 판단으로 선택된 것도 아니다(예를 들어, valence boost 스케일은 2.0보다 훨씬 낮은 곳에서 시작했는데, 이것이 그토록 중요해질 줄은 다소 놀라운 일이다). 그럼에도 불구하고, 이 값들은 다양한 cache 크기와 mesh 유형에 걸쳐 일관되게 최상의 전체 점수를 도출했다.

 

6. Runtime Efficiency

삼각형의 그리기 순서는 위의 알고리즘에 나와있다. 그러나 이 알고리즘을 느리게 실행하는 여러 가지가 있으며, 이 알고리즘의 주요 특징 중 하나는 속도다.

 

기존의 많은 mesh topology algorithm과 달리 데이터가 보관되지 않으며 필요하지도 않다. 따라서 edge data를 찾는 데 드는 비용(일반적으로 다소 번거로운 작업)과 하나의 가장자리를 여러 개의 삼각형(일반적인 알고리즘에서는 두 개 이상을 의미!)이 공유하는 병리적 mesh의 고유한 문제를 피할 수 있다.

 

대신, 각 정점은 다음과 같은 데이터를 지닌다:

• modeled cache에서의 위치(cache에 없는 경우 -1)
• 현재 점수
• 이를 사용하는 삼각형의 총 개수
• 아직 추가되지 않은 삼각형 중 이를 사용하는 삼각형의 수
• 이를 상요하는 삼각형의 index 목록

정점을 사용하는 삼각형의 총 개수는 알고리즘을 실행하는 데 반드시 필요한 것은 아니지만 디버깅에 유용하다는 점에 유의하자. 삼각형의 index 목록은 항상 이 길이지만, 아직 추가되지 않은 삼각형 index가 먼저 나열되고 그 다음에 이미 그리기 목록에 추가된 삼각형 index가 나열되도록 순서가 정해져 있다.

 

mesh의 각 삼각형은 다음 데이터도 저장한다.:

• 그리기 목록에 추가되었는지 여부
• 삼각형의 점수(해당 정점의 점수 합계)
• 세 정점에 대한 index

다른 데이터 구조는 가장 최근에 사용된 것부터 가장 적게 사용된 것까지 순서대로 나열된 정점 index의 목록인 FIFO cache 자체다. 개념적으로 이 cache는 32개의 항목으로 구성되어 있지만, 구현의 편의를 위해 실제로는 3개의 항목으로 늘어난다.

 

데이터 초기화는 매우 간단하며, 삼각형 데이터에 대해 두 번의 전달을 수행한다. 첫 번째는 단순히 각 정점을 사용하는 삼각형 수의 카운터를 증가시키고, 두 번째는 각 정점에 대해 삼각형 목록을 할당하고 이를 채운다. 그 후 위의 코드를 사용해 각 정점의 점수를 구한 다음, 삼각형이 사용하는 각 정점의 점수를 합산해 각 삼각형의 점수를 구한다. 이 점수는 단순히 계산된 점수의 cache된 값이며, 알고리즘이 실행되면서 필요할 때 업데이트된다.

 

그런 다음 더 이상 그릴 삼각형이 남아 있지 않을 때까지 그려진 삼각형 목록에 추가할 삼각형을 한 번에 하나씩 선택하는 알고리즘의 본체가 등장한다. 일반적으로 알고리즘은 이전 반복을 통해 어떤 삼각형이 가장 높은 점수를 받았는지 파악하고 해당 삼각형을 선택하기만 하면 된다. 알고리즘이 처음 실행될 때 가장 좋은 삼각형을 아직 알지 못하거나, 가장 좋은 것으로 추정되는 삼각형의 점수가 비정상적으로 낮을 경우(mesh에 더 좋은 다른 삼각형이 있을 수 있음), 알고리즘이 해당 삼각형을 선택하지 않을 수도 있다. 이러한 드문 상황에서는 mesh의 나머지 삼각형을 모두 실행해 가장 좋은 점수를 찾는다.

 

[힌트: 실제로 "비정상적으로 낮은 점수" 조항은 결과에 거의 영향을 미치지 않는 것으로 밝혀졌다. 알고리즘을 개발한 동안에는 유용했지만, 여기서 제시된 최종 알고리즘의 경우 전체 테스트 데이터 세트에서 단 3개의 삼각형에 대해서만 발생하므로 실제로는 효율성에 큰 영향을 미치지 않는 것으로 나타났다.]

 

그런 다음 가장 좋은 삼각형을 그리기 목록에 추가한다. 삼각형이 사용된 각 정점에 대해 해당 정점의 valence가(해당 정점을 사용하는 아직 그려지지 않은 삼각형의 수)가 하나씩 감소하고 정점의 삼각형 index 목록이 적절하게 업데이트 된다.

 

삼각형이 사용하는 세 개의 정점은 LRU로 모델링된 cache의 head로 이동하거나, 아직 cache에 없는 경우 head에 추가 된다. cache는 이전에 cache에 있던 모든 정점과 이 삼각형의 새로운 정점 3개까지 포함하도록 일시적으로 정점 3개만큼 크기가 커진다. 그런 다음 cache에서 정점의 새로운 위치가 업데이트 되고, 위에 제공된 코드를 사용해 해당 점수를 찾고, 아직 추가되지 않은 모든 삼각형의 점수도 업데이트 된다.

 

이 작업이 완료되면 지금까지 가장 높은 점수를 받은 삼각형의 점수와 index가 기록된다. 현재 cache에 있는 정점을 사용하는 삼각형만 점수를 스캔하지만, 이는 전체 mesh에서 가장 높은 점수를 받은 삼각형의 합리적인 추정치다. 이 추정치가 참인지 여부를 철저하게 확인하는 코드를 디버깅한 결과, 모든 테스트에서 몇 번만민 거짓으로 확인됐으며, 그마저도 정답과 근사치 간의 점수 차이는 매우 작았다. 실제로 이 차이는 cache 성능에 큰 영향을 미치지 않으며 알고리즘의 런타임 비용을 크게 줄여준다.

 

마지막으로 cache가 다시 정상 크기로 축소돼 최대 3개의 정점이 빠지게 된다. 해당 정점의 cache 위치는 이미 적절하게 업데이트된 상태다. 알고리즘은 더 이상 추가할 삼각형이 남이 않을 때까지 반복된다.

 

위의 내용을 자세히 살펴보면, 각 정점이 약 6개의 삼각형에 의해 사용되는 "일반" mesh의 경우 이 알고리즘의 런타임 속도와 메모리 사용량은 mesh의 정점 수에 선형적으로 비례한다는 것을 알 수 있다. 이는 다양한 look-ahead 또는 계층적 세분화 방법이나 복잡한 topological information(위상수학 정보)를 사용하는 방법보다 훨씬 낫다.

 

 

참고

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