Войти
ПрограммированиеТерминыГрафика

Вершинный кеш (VCache: Vertex Cache)

На современных видеоускорителях одной из первых стадий является [[TnL]] (Transformations and Lightning), обрабатывающий вершины. Для эффективной его работы предусмотрены pre-[[TnL]] и post-[[TnL]] кеши. При подаче геометрии необходимо учитывать их особенности, иначе теряется значительная часть производительности.

pre-[[TnL]] кеш устроен по принципу LRU (аналогичен кешу процессора) и измеряется килобайтами. В нем кешируются выбранные из памяти вершины и для его эффективного использования достаточно соблюдать локальность данных в вершинном буфере (см. пример 2). Существование этого кеша означает, что (для массивов вертексов, размещённых в видеопамяти) interleaved меши эффективнее раздельных массивов для координат, нормалей и т. д. Рекомендуется хранить вертексный атрибут в отдельном массиве только в том случае, когда он будет динамически изменяться отдельно от остальных данных.

post-[[TnL]] кеш устроен по принципу FIFO (т.е. при поступлении новой вершины самая старая удаляется и все вершины сдвигаются на 1) и кеширует вершины после прохождения трансформаций, измеряется несколькими вершинами. Для эффективного использования необходимо подавать индексы дублирующихся вершины в пределах размера кеша. Тут заключена интересная особенность. В видеокартах NVidia post-[[TnL]] кеш может работать только для индексированных мешей; именно в этом смысл использования индексированных мешей вообще. В видеокартах ATI кеш может работать и для неиндексированных мешей (то есть, механизм post-[[TnL]] кеша способен сам обнаруживать дублирующиеся вертексы).

Эффективно использовать post-[[TnL]] кеш гораздо сложнее (вообще, задача является NP-полной), и, как правило, для этого необходимо учитывать особенности геометрии конкретных алгоритмов и другие эвристические (Heuristics) методы. Например, квадратную регулярную сетку имеет смысл рисовать длинными полосками шириной в половину кеша (см. пример 1).

На практике для рендеринга используют либо отдельные треугольники либо стрипы. И те и другие эффективно оптимизируются под кеш, при этом отдельные стрипы могут объединятся вырожденными треугольниками. Однако таких треугольников не должно быть более 20% (это число может быть больше и зависит от железа), иначе эффект от оптимизации будет обратный. Если размер индексного буфера не критичен, триангл-листы дают близкий результат, т.к. "лишние" вершины в любом случае окажутся в кеше.
Тонкости работы post-[[TnL]] кеша сильно зависят от конкретной карты и драйвера. Рассчитывать, как правило, стоит только на минимально гарантированные характеристики. Использование преувеличенного размера кеша приведет к сильному падению производительности. Достоверно известно что размер кеша NV10 - 16, NV20 - 24, для Radeon-ов есть непроверенная информация, что он составляет 16 вершин. Кроме того карты NVidia могут использовать только индексированную геометрию, а Radeon-ы будут кешировать даже неиндексированные примитивы. Более того, на кеширование может повлиять драйвер. На некоторых картах эффект такой оптимизации может быть слабо заметен.

Во время ручной оптимизации под кеш нужно использовать не реальный размер кеша, а т.н. эффективный. Несколько элементов кеша (обычно 4) не смогут быть использованы, поэтому размер эффективнго кеша всегда меньше.

Суммируя сказанное: нужно рассчитывать на эффективный размер кеша в 12 вершин и использовать индексированные стрипы соединенные дегенератами (или отдельные треугольники). При оптимизациях желательно учитывать разброс вершинного буфера и перераспрелделять его для повышения локальности данных. Естественно, эти оптимизации тем более эффективны, чем больше дублирутся вершин в меше. В любом случае количество кеш-промахов будет не меньше чем общее количество выводимых вершин.
Для облегчения ручной работы по оптимизации существуют утилиты, создающие оптимизированный индекс и вертекс буфферы. Например, NVTriStrip от NVidia (http://www.nvidia.com/object/nvtristrip_library.html) или еше более эффективная реализация - Stripe (http://www.cs.sunysb.edu/~stripe/), еще есть TriStripper (http://users.pandora.be/tfautre/softdev/tristripper/). Кроме того, в библиотеке D3DX реализованы методы оптимизации под кеш (ID3DXMesh::Optimize, см.  Оптимизация мешей в DX9).
Все выше сказанное справедливо только в том случае, если конвеер ограничен трансформациями (блоком [[TnL]]). Тогда, возможно, удастся достичь заявленной максимальной пропускной способности блока для видеокарты.

Пример 1.

//функция генерирует оптимизированный индекс-буфер 
//для регулярной сетки заданной длинны и ширины
  template< typename index_t >
  void OptimizeRegularGrid( 
    std::vector< index_t > & indices, 
    int width, int height, int eff_cache_size )
  {
    int x_pos = 0, strip_start = 0;
    int cache_half = eff_cache_size / 2;

    indices.reserve( indices.size( ) + height * width * 2 );

    for( ; strip_start < height - 1;  strip_start += cache_half - 1 )
    {
      if( strip_start >= height - cache_half )
        cache_half = height - strip_start;

      //add degenerate
      indices.push_back( strip_start * width );

      for( x_pos = 0; x_pos < width - 1; ++x_pos )
      {
        int strip_len, incr;
        if( (x_pos % 2) == 0 ) {
          strip_len = 0;
          incr = 1;
        }
        else {
          strip_len = cache_half - 1;
          incr = -1;
        }

        for( ; (strip_len < cache_half) && (strip_len >= 0); strip_len += incr )
        {
          indices.push_back( x_pos + (strip_len + strip_start) * width );
          indices.push_back( x_pos + (strip_len + strip_start) * width + 1 );
        }
      }
      //add degenerate
      indices.push_back( *(indices.rbegin( )) );

    }
  }

Пример 2.

//функция перераспределяет индекс- и вертекс-буферы
//для увеличения локальности данных
  template< typename vertex_t, typename index_t >
  void IndexRemap( std::vector< vertex_t > &vb, std::vector< index_t > &ib )
  {
    std::vector< index_t > index_cache( vb.size( ), vb.size( ) );
    typename std::vector< index_t >::iterator i;

    std::vector< vertex_t > new_vb;
    std::vector< index_t > new_ib;

    new_vb.reserve( vb.size( ) );
    new_ib.reserve( ib.size( ) );

    for( i = ib.begin( ); i < ib.end( ); ++i )
    {
      if( index_cache[ *i ] == vb.size( ) )
      {
        index_cache[ *i ] = new_vb.size( );
        new_ib.push_back( new_vb.size( ) );
        new_vb.push_back( vb[ *i ] );
      }
      else
        new_ib.push_back( index_cache[ *i ] );
    }

    vb.swap( new_vb );
    ib.swap( new_ib );
  }
}

Лекция: http://www.gamedev.ru/community/gamedev_lecture/articles/?id=24

Что такое Вершинный кеш (VCache: Vertex Cache)?

#cash, #вершины, #оптимизация

14 сентября 2005 (Обновление: 7 фев. 2007)

купить мяч адидас киев