[CG] Linear-Speed Vertex Cache Optimisation - 2

계속해서 살펴보자.

 

4. Vertex Scores in Detail

 

주어진 정점의 점수는 해당 정점을 사용하는 삼각형이 다음에 렌더링 목록에 추가될 가능성을 나타낸다. 점수가 높을수록 가능성이 높아지고 점수가 낮을수록 가능성이 낮아진다. 점수는 여러 가지 요소에 따라 달라진다.

 

 첫 번째는 정점이 최근에 사용되었을 수록 점수가 높다는 것이다. 점수는 LRU cache에서 정점의 위치를 0에서 1 사이의 실수로 계산하는데, 마지막(LRU) 위치는 0이고 첫 번째(MRU) 위치는 1이다. 그런 다음 이 스케일링된 위치는 1보다 큰 거듭제곱으로 올라간다. 거듭된 시뮬레이션을 통해 거듭제곱의 값을 선택했는데, 1.5가 좋은 결과를 가져다주는 것으로 보인다. 단순한 선형 점수가 아닌 거듭제곱을 사용하면 규모에 더 독립적인 동작을 제공하는 것으로 보이며, 이는 cache의 크기를 알 수 없는 hardware cache 크기에 맞게 최적화를 위한 알고리즘에 바람직한 특성이다.

 

  이 규칙의 예외는 가장 최근에 추가된 삼각형에서 사용된 정점, 즉 가장 최근의 정점 세 개는 고정된 점수를 갖는다는 것이다. 이 세 개의 정점이 독립적인 이유는 사용된 순서가 전적으로 가장 최근 삼각형에 지정된 순서에 따라 달라지며, 이는 export pipelines(내보내느 파이프라인)과 기타 예측할 수 없는 요소의 영향을 받기 때문이다. cache에 있는 나머지 정점에 대한 점수는 처음 세 개의 정점이 없는 것처럼, 즉 cache의 네 번째 정점이 "최고" 점수인 1.0을 받는 것처럼 수행된다는 점에 유의해야한다. 놀라운 점은 처음 세 개의 점의 점수는 실험 결과 0.75로 설정하는 것이 가장 좋다는 것이다. 이는 cache에서 그 뒤에 있는 정점의 점수보다 낮다.

 

 그 이유는 가장 최근에 추가된 정점 3개가 가장 높은 점수를 받으면 다음에 추가될 삼각형은 가장 최근에 추가된 삼각형의 가장자리(정점 중 2개)를 공유하는 삼각형이 될 것이 거의 확실하기 때문이다. 언뜻 보기에 이것을 우리가 원하는 것과 정확히 일치하는 것처럼 들린다. 문제는 이 알고리즘에는 앞을 내다보는 기능(lookahead) 기능이 없기 때문에 먼저 mesh를 통해 길고 얇은 strip을 형성한 다음 strip이 먼 거리까지 다시 돌아가고 또 다시 strip이 형성된다는 것이다. 이 방식은 꽤 괜찮은 것처럼 보이지만, 삼각형당 하나의 정점이 약 1.0의 ACMR을 얻을 뿐이며, 이는 성능이 좋은 알고리즘이 얻을 수 있는 결과보다 훨씬 나쁘다. 가장자리의 즉각적인 재사용을 약간 억제함으로써 알고리즘은 좀 더 멀리 내다보는 효과를 얻게 되고, 이는 이론적으로 이상적인 모양인 Hilbert curve와 다르지 않은 보다 일반적으로 수용 가능한 패턴을 생성하는 것으로 보인다. 아래는 32개 항목으로 구성된 LRU cache의 전반부 위치가 점수에 어떻게 대응하는지 보여주는 표다:

 

LRU pos	Score
0	0.75
1	0.75
2	0.75
3	1.00
4	0.99
5	0.98
6	0.97
7	0.95
8	0.93
9	0.91
10	0.88
11	0.86
12	0.83
13	0.80
14	0.77
15	0.73

 

EMERGENCY EDIT(긴급 수정): 사실 위 표의 숫자가 잘못됐다! 모양은 맞지만 엑셀 수식을 잘못 입력해 실제 숫자가 정확하지 않는다. 하지만 아래는 정확하니 사용 가능하다.

 

정점의 valence가 낮으면 정점 점수에 더해진다. 정점의 남은 valence는 해당 정점을 삼각형 중 아직 그려지지 않은 삼각형의 수다. 그려야 할 삼각형이 하나만 남은 정점은 가장 높은 부스트(boost)를 받고, 아직 그려야 할 삼각형이 많은 정점은 훨씬 낮은 부스트를 받는다. 점수의 증가는 아직 남은 삼각형의 수에 비례해 음의 소수 거듭제곱(실험 결과 -0.5가 가장 효과적)으로 올린 다음 FIFO 점수에 비례해 스케일링된다. 실험 결과 2.0이 가장 효과적인 것으로 나타났다. 다음은 적절한 값을 가진 정점과 그 점수 표다.

Valence	Score
1	2.00
2	1.41
3	1.15
4	1.00
5	0.89
6	0.82
7	0.76
8	0.71
9	0.67
10	0.63

 

낮은 valence를 보상하는 이유는 valence가 없어도 알고리즘이 여전히 mesh를 통과하는 최적의 경로를 선택해 낮은 정점/삼각형 비율을 유지하기 때문이다. 문제는 동떨어졌거나 작은 삼각형 클러스터(덩어리)의 삼각형을 추가하는 것이 다른 삼각형을 추가하는 것보다 약간 덜 최적화된다는 것이다. mesh의 90%가 완성될 때쯤에는 여전히 그려야 하는 고립된 조각인 "파편"만 남게 된다. 이 시점에서 ACMR은 여전히 만족스러울 정도로 낮지만, 이러한 나머지 조각을 추가하는 것은 서로 가깝지 않기 때문에 삼각형당 거의 3개의 모든 정점이 발생하므로 비용이 매우 많이 든다. 이는 mesh 전체의 ACMR에 끔찍한 영향을 미치고 효율성을다시 떨어드릴 수 있다. 훨씬 더 나은 방법은 알고리즘이 진행됨에 따라 렌더링 순서에 이러한 파편들을 추가하는 것이다. 파편들을 한 번에 추가하는 것은 최적이 아니지만 나중에 추가하면 비용이 매우 많이 든다. 남은 삼각형이 거의 없는 정점의 점수를 높이면 적절한 시점에 남은 파편(detritus)를 추가하도록 유도할 수 있다.

 

또한 알고리즘이 더 이상 추가할 삼각형이 없는 mesh의 "막다른 골목(dead end)" 부분(예를 들어 손에서도 손가락의 끝 부분)에 도달한 경우, 알고리즘이 패치 중간에서 시작해 인위적인 dead end가 생기지 않고 mesh의 가장자리와 같은 다른 "dead end" 근처에 있는 삼각형에서 다시 시작하도록 유도한다.

 

두 개의 점수(FIFO 위치에 따른 점수와 나머지 valence에 따른 점수)를 합산해 총 정점 점수를 구한다. 각 삼각형의 점수를 구하려면 세 꼭지점 각각에 대한 점수를 합산한다. 그리고 각 단계에서 가장 높은 점수를 받은 삼각형이 추첨 목록에 추가되고 정점의 점수가 다시 계산 된다.

 

정점의 점수를 계산하는 전체 코드는 아래와 같다:

const float FindVertexScore_CacheDecayPower = 1.5f;
const float FindVertexScore_LastTriScore = 0.75f;
const float FindVertexScore_ValenceBoostScale = 2.0f;
const float FindVertexScore_ValenceBoostPower = 0.5f;
float FindVertexScore ( vcache_vertex_data *VertexData )
{
    if ( VertexData->NumActiveTris == 0 )
    {
        // No tri needs this vertex!
        return -1.0f;
    }
 
    float Score = 0.0f;
    int CachePosition = VertexData->CacheTag;
    if ( CachePosition < 0 )
    {
        // Vertex is not in FIFO cache - no score.
    }
    else
    {
        if ( CachePosition < 3 )
        {
            // This vertex was used in the last triangle,
            // so it has a fixed score, whichever of the three
            // it's in. Otherwise, you can get very different
            // answers depending on whether you add
            // the triangle 1,2,3 or 3,1,2 - which is silly.
            Score = FindVertexScore_LastTriScore;
        }
        else
        {
            assert ( CachePosition < MaxSizeVertexCache );
            // Points for being high in the cache.
            const float Scaler = 1.0f / ( MaxSizeVertexCache - 3 );
            Score = 1.0f - ( CachePosition - 3 ) * Scaler;
            Score = powf ( Score, FindVertexScore_CacheDecayPower );
        }
    }
 
    // Bonus points for having a low number of tris still to
    // use the vert, so we get rid of lone verts quickly.
    float ValenceBoost = powf ( VertexData->NumActiveTris,
                                -FindVertexScore_ValenceBoostPower );
    Score += FindVertexScore_ValenceBoostScale * ValenceBoost;
 
    return Score;
}

 

참고

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