Внешний вид сайта:

CryENGINE: Coverage Buffer в деталях

Некоторое время назад я наткнулся в замечательной презентации Secrets of CryEGNINE 3 Graphics Technology от не менее замечательных Nickolay Kasyan, Nicolas Schulz и Tiago Sousa на описание любопытной технологии, названной авторами
Coverage Buffer. Технология представлена как основной метод окклюжен куллинга, активно используемый начиная с Crysis 2. Так как никакого внятного пейпера по данной технологии Crytek не предоставили, а разобраться было интересно, то пришлось плясать с тем, что имеем.

Что?

Итак, идея, по словам авторов презентации, заключается в следующем.

  • Получить depth-buffer предыдущего кадра
  • Сделать репроекцию в текущий кадр
  • Софтварно растеризуя BBox'ы объектов, проверять, видны ли они камере - и рисовать/не рисовать

Метод в принципе не содержит никаких революционных идей, отличие от основного конкурента - Software Occlusion Culling - заключается в том в том методе
нам необходимо строго поделить объекты на категории Occluder/Occludee, что не всегда возможно сделать.

пикч | Coverage Buffer из CryENGINE в деталях

Итак, еще раз кратко резюмируя, каковы плюсы этого метода?

  • + не нужно разделять объекты на occluder/occludee
  • + использование уже готового depth buffer

ну и очевидные минусы:

  • - ошибка связанная с отставанием на 1 кадр (репроекция полностью не решает данную проблему)
  • - оверхед при полной видимости объектов, связанный с манипуляциями с depth buffer (downscale, lock и т.д.)

 

Где?

Так уж получилось, что я гуглил в сторону Occlusion Culling не просто так, на проекте необходимо было решить довольно важную задачу, связанную с тормозами, возникающими
из-за огромного лесного массива. Речь идёт, конечно же, о горячо любимом мною Life is Feudal. (Все скрины ниже будут оттуда)

Итак, вкратце суть изначальной проблемы.

  • Есть остров, густо засаженный деревьями. Рисуется всё это действо на движке Torque3D.

Из оптимизаций, изначально встроенных в движок, есть неплохая система батчинга/биллбордов для дальних деревьев и инстансинга для тех, которые поближе. Однако, решение "рисовать/не рисовать" принимается по дефолту исключительно в результате frustum culling'а (т.е. мы смотрим, попадает ли данное дерево/батч в пирамиду, и, если попадает, то рисовать).

Однако, такой подход не вполне оправдывает себя в случае действительно больших лесных массивов с десятками тысяч деревьев. В этом случае попадают во фрустум (и как следствие, рисуются) те деревья, которые находятся за стеной, горой и другими деревьями. Из-за этого бюджет кадра терпит катастрофические потери:  даже смотря сквозь стену в направлении центра острова, рисование невидимых батчей и деревьев занимало порядко 20-30мс, что, в общем-то, вплотную приближается к рассчетному бюджету кадра (33мс).

Как результат, игроки получали драматическое падение ФПС просто глядя в направлении центра острова.

gbr | Coverage Buffer из CryENGINE в деталях

 Для решения данной задачи было решено воспользоваться технологией Coverage Buffer. Если бы я писал, например, диплом, то тут бы стоило сделать обзор всех остальных методов OC, обозначить плюсы и минусы,
и обосновать, почему был выбран именно этот.

mapsmall | Coverage Buffer из CryENGINE в деталях

К счастью, это не диплом, потому ограничусь одним предложением:
После чтения многочисленных пейперов и статей, переписки и бесед с более мудрыми и опытными коллегами было решено опробовать этот метод, тем более, что в бою он уже себя показал.

Осталось лишь посмотреть, как он покажет себя в нашей ситуации.

Когда? Как?

Теперь перейдём к техническим деталям и, собственно, коду.

Первая задача, которая встала - это получить depth buffer. Torque3D, который на момент написания статьи поддерживал DirectX только 9й версии, накладывал в этом
свете определённые ограничения.

Как получить Depth Buffer в DirectX 9?

Ответ нашёлся на сайте Араса Пранцкевичуса (я не уверен, что правильно транслитерировал его фамилию), это главный render-guy известного движка Unity. Оказалось, что depth buffer получить в directX 9 все таки можно, но для этого нужно использовать специальный формат INTZ. Согласно официальной документации от AMD и NVidia, все видеокарты, выпущенные начиная с 2008го года, поддерживают данный формат (для более ранних есть RAWZ), так что можно без особых опасений пользоваться данным хаком. Ссылки на документацию: AMD и NVidia

Код использования тривиален, взят из одного из пейперов вверху, приведу его тут чтобы, так сказать, все яйца были в одной корзине.

#define FOURCC_INTZ ((D3DFORMAT)(MAKEFOURCC(‘I’,’N’,’T’,’Z’)))

// Determine if INTZ is supported
HRESULT hr;
hr = pd3d->CheckDeviceFormat(AdapterOrdinal, DeviceType, AdapterFormat,
 D3DUSAGE_DEPTHSTENCIL, D3DRTYPE_TEXTURE,
FOURCC_INTZ);
BOOL bINTZDepthStencilTexturesSupported = (hr == D3D_OK);

// Create an INTZ depth stencil texture
IDirect3DTexture9 *pINTZDST;
pd3dDevice->CreateTexture(dwWidth, dwHeight, 1,
 D3DUSAGE_DEPTHSTENCIL, FOURCC_INTZ,
 D3DPOOL_DEFAULT, &pINTZDST,
 NULL);

// Retrieve depth buffer surface from texture interface
IDirect3DSurface9 *pINTZDSTSurface;
pINTZDST->GetSurfaceLevel(0, &pINTZDSTSurface);

// Bind depth buffer
pd3dDevice->SetDepthStencilSurface(pINTZDSTSurface);

// Bind depth buffer texture
pd3dDevice->SetTexture(0, pINTZDST);

Дальнейшая подготовка Depth buffer'а

  • downscale до низкого разрешения (было выбрано 256х128)
  • lock + memcpy
  • reprojection

Всё тут достаточно тривиально, downscale делается с маской max (берется максимальное расстояние, ближе к камере, дабы
не закрыть чего лишнего), репроекция делается путём применения обратной матрицы от предыдущего кадра и новой - от текущего.
Возникшие пробелы "замазываются" maxValue, дабы не закрыть чего лишнего.

Итак, теперь есть depth buffer. Теперь дело за малым - софтварная растеризация ббоксов

Софтварная растеризация

Данную тему никак нельзя назвать нехоженной тропой, уже довольно много мусолили на разные лады. Однако внятной инструкции к
реализации найти не так-то просто. Самый полезный материал, который я нашёл по сабжу, был тут: https://software.intel.com/en-us/blogs/2013/09/06/software-occlus… ling-update-2. Это крайне полезная интеловская демка по conventional occlusion culling, которую всем рекомендую - внутри много полезного.

Первая версия функции для софтварной растеризации была реализована в, так сказать, plain c++. Она работала, но довольно медленно. Спасибо комраду bazhenovc, подсказал переписать на SSE. Я по молодости с SSE еще не работал, но с божьей и интеловской помощью переписал на SSE, стало работать в 2-2.5 раза быстрее. Вот она, магия SIMD. Делюсь кодом безвозмездно, юзайте на здоровье =)
Если вдруг кто заметит какие недочёты или возможности для оптимизации, очень прошу сообщить!

static const int sBBIndexList[36] =
{
  // index for top 
  4, 8, 7,
  4, 7, 3,

  // index for bottom
  5, 1, 2,
  5, 2, 6,

  // index for left
  5, 8, 4,
  5, 4, 1,

  // index for right
  2, 3, 7,
  2, 7, 6,

  // index for back
  6, 7, 8,
  6, 8, 5,

  // index for front
  1, 4, 3,
  1, 3, 2,
};

__m128 SSETransformCoords(__m128 *v, __m128 *m)
{
  __m128 vResult = _mm_shuffle_ps(*v, *v, _MM_SHUFFLE(0,0,0,0));
  vResult = _mm_mul_ps(vResult, m[0]);

  __m128 vTemp = _mm_shuffle_ps(*v, *v, _MM_SHUFFLE(1,1,1,1));
  vTemp = _mm_mul_ps(vTemp, m[1]);

  vResult = _mm_add_ps(vResult, vTemp);
  vTemp = _mm_shuffle_ps(*v, *v, _MM_SHUFFLE(2,2,2,2));

  vTemp = _mm_mul_ps(vTemp, m[2]);
  vResult = _mm_add_ps(vResult, vTemp);

  vResult = _mm_add_ps(vResult, m[3]);
  return vResult;
}

__forceinline __m128i Min(const __m128i &v0, const __m128i &v1)
{
  __m128i tmp;
  tmp = _mm_min_epi32(v0, v1);
  return tmp;
}
__forceinline __m128i Max(const __m128i &v0, const __m128i &v1)
{
  __m128i tmp;
  tmp = _mm_max_epi32(v0, v1);
  return tmp;
}


struct SSEVFloat4
{
  __m128 X;
  __m128 Y;
  __m128 Z;
  __m128 W;
};

// get 4 triangles from vertices
void SSEGather(SSEVFloat4 pOut[3], int triId, const __m128 xformedPos[])
{
  for(int i = 0; i < 3; i++)
  {
    int ind0 = sBBIndexList[triId*3 + i + 0]-1;
    int ind1 = sBBIndexList[triId*3 + i + 3]-1;
    int ind2 = sBBIndexList[triId*3 + i + 6]-1;
    int ind3 = sBBIndexList[triId*3 + i + 9]-1;

    __m128 v0 = xformedPos[ind0];
    __m128 v1 = xformedPos[ind1];
    __m128 v2 = xformedPos[ind2];
    __m128 v3 = xformedPos[ind3];
    _MM_TRANSPOSE4_PS(v0, v1, v2, v3);
    pOut[i].X = v0;
    pOut[i].Y = v1;
    pOut[i].Z = v2;
    pOut[i].W = v3;

    //now X contains X0 x1 x2 x3, Y - Y0 Y1 Y2 Y3 and so on...
  }
}


bool RasterizeTestBBoxSSE(Box3F box, __m128* matrix, float* buffer, Point4I res)
{
  //verts and flags
  __m128 verticesSSE[8];
  int flags[8];
  static Point4F vertices[8];
  static Point4F xformedPos[3];
  static int flagsLoc[3];

  // Set DAZ and FZ MXCSR bits to flush denormals to zero (i.e., make it faster)
  // Denormal are zero (DAZ) is bit 6 and Flush to zero (FZ) is bit 15. 
  // so to enable the two to have to set bits 6 and 15 which 1000 0000 0100 0000 = 0x8040
  _mm_setcsr( _mm_getcsr() | 0x8040 );


  // init vertices
  Point3F center = box.getCenter();
  Point3F extent = box.getExtents();
  Point4F vCenter = Point4F(center.x, center.y, center.z, 1.0);
  Point4F vHalf   = Point4F(extent.x*0.5, extent.y*0.5, extent.z*0.5, 1.0);

  Point4F vMin    = vCenter - vHalf;
  Point4F vMax    = vCenter + vHalf;

  // fill vertices
  vertices[0] = Point4F(vMin.x, vMin.y, vMin.z, 1);
  vertices[1] = Point4F(vMax.x, vMin.y, vMin.z, 1);
  vertices[2] = Point4F(vMax.x, vMax.y, vMin.z, 1);
  vertices[3] = Point4F(vMin.x, vMax.y, vMin.z, 1);
  vertices[4] = Point4F(vMin.x, vMin.y, vMax.z, 1);
  vertices[5] = Point4F(vMax.x, vMin.y, vMax.z, 1);
  vertices[6] = Point4F(vMax.x, vMax.y, vMax.z, 1);
  vertices[7] = Point4F(vMin.x, vMax.y, vMax.z, 1);

  // transforms
  for(int i = 0; i < 8; i++)
  {
    verticesSSE[i] = _mm_loadu_ps(vertices[i]);

    verticesSSE[i] = SSETransformCoords(&verticesSSE[i], matrix);

    __m128 vertX = _mm_shuffle_ps(verticesSSE[i], verticesSSE[i], _MM_SHUFFLE(0,0,0,0)); // xxxx
    __m128 vertY = _mm_shuffle_ps(verticesSSE[i], verticesSSE[i], _MM_SHUFFLE(1,1,1,1)); // yyyy
    __m128 vertZ = _mm_shuffle_ps(verticesSSE[i], verticesSSE[i], _MM_SHUFFLE(2,2,2,2)); // zzzz
    __m128 vertW = _mm_shuffle_ps(verticesSSE[i], verticesSSE[i], _MM_SHUFFLE(3,3,3,3)); // wwww
    static const __m128 sign_mask = _mm_set1_ps(-0.f); // -0.f = 1 << 31
    vertW = _mm_andnot_ps(sign_mask, vertW); // abs
    vertW = _mm_shuffle_ps(vertW, _mm_set1_ps(1.0f), _MM_SHUFFLE(0,0,0,0)); //w,w,1,1
    vertW = _mm_shuffle_ps(vertW, vertW, _MM_SHUFFLE(3,0,0,0)); //w,w,w,1
  
    // project
    verticesSSE[i] = _mm_div_ps(verticesSSE[i], vertW);

    // now vertices are between -1 and 1
    const __m128 sadd = _mm_setr_ps(res.x*0.5, res.y*0.5, 0, 0);
    const __m128 smult = _mm_setr_ps(res.x*0.5, res.y*(-0.5), 1, 1);

    verticesSSE[i] = _mm_add_ps( sadd, _mm_mul_ps(verticesSSE[i],smult) );
  }

  // Rasterize the AABB triangles 4 at a time
  for(int i = 0; i < 12; i += 4)
  {
    SSEVFloat4 xformedPos[3];
    SSEGather(xformedPos, i, verticesSSE);

    // by 3 vertices
    // fxPtX[0] = X0 X1 X2 X3 of 1st vert in 4 triangles
    // fxPtX[1] = X0 X1 X2 X3 of 2nd vert in 4 triangles
    // and so on
    __m128i fxPtX[3], fxPtY[3];
    for(int m = 0; m < 3; m++)
    {
      fxPtX[m] = _mm_cvtps_epi32(xformedPos[m].X);
      fxPtY[m] = _mm_cvtps_epi32(xformedPos[m].Y);
    }

    // Fab(x, y) =     Ax       +       By     +      C              = 0
    // Fab(x, y) = (ya - yb)x   +   (xb - xa)y + (xa * yb - xb * ya) = 0
    // Compute A = (ya - yb) for the 3 line segments that make up each triangle
    __m128i A0 = _mm_sub_epi32(fxPtY[1], fxPtY[2]);
    __m128i A1 = _mm_sub_epi32(fxPtY[2], fxPtY[0]);
    __m128i A2 = _mm_sub_epi32(fxPtY[0], fxPtY[1]);

    // Compute B = (xb - xa) for the 3 line segments that make up each triangle
    __m128i B0 = _mm_sub_epi32(fxPtX[2], fxPtX[1]);
    __m128i B1 = _mm_sub_epi32(fxPtX[0], fxPtX[2]);
    __m128i B2 = _mm_sub_epi32(fxPtX[1], fxPtX[0]);

    // Compute C = (xa * yb - xb * ya) for the 3 line segments that make up each triangle
    __m128i C0 = _mm_sub_epi32(_mm_mullo_epi32(fxPtX[1], fxPtY[2]), _mm_mullo_epi32(fxPtX[2], fxPtY[1]));
    __m128i C1 = _mm_sub_epi32(_mm_mullo_epi32(fxPtX[2], fxPtY[0]), _mm_mullo_epi32(fxPtX[0], fxPtY[2]));
    __m128i C2 = _mm_sub_epi32(_mm_mullo_epi32(fxPtX[0], fxPtY[1]), _mm_mullo_epi32(fxPtX[1], fxPtY[0]));

    // Compute triangle area
    __m128i triArea = _mm_mullo_epi32(B2, A1);
    triArea = _mm_sub_epi32(triArea, _mm_mullo_epi32(B1, A2));
    __m128 oneOverTriArea = _mm_div_ps(_mm_set1_ps(1.0f), _mm_cvtepi32_ps(triArea));

    __m128 Z[3];
    Z[0] = xformedPos[0].W;
    Z[1] = _mm_mul_ps(_mm_sub_ps(xformedPos[1].W, Z[0]), oneOverTriArea);
    Z[2] = _mm_mul_ps(_mm_sub_ps(xformedPos[2].W, Z[0]), oneOverTriArea);

    // Use bounding box traversal strategy to determine which pixels to rasterize 
    __m128i startX =  _mm_and_si128(Max(Min(Min(fxPtX[0], fxPtX[1]), fxPtX[2]),  _mm_set1_epi32(0)), _mm_set1_epi32(~1));
    __m128i endX   = Min(Max(Max(fxPtX[0], fxPtX[1]), fxPtX[2]), _mm_set1_epi32(res.x - 1));

    __m128i startY = _mm_and_si128(Max(Min(Min(fxPtY[0], fxPtY[1]), fxPtY[2]), _mm_set1_epi32(0)), _mm_set1_epi32(~1));
    __m128i endY   = Min(Max(Max(fxPtY[0], fxPtY[1]), fxPtY[2]), _mm_set1_epi32(res.y - 1));

    // Now we have 4 triangles set up.  Rasterize them each individually.
    for(int lane=0; lane < 4; lane++)
    {
      // Skip triangle if area is zero 
      if(triArea.m128i_i32[lane] <= 0)
      {
        continue;
      }

      // Extract this triangle's properties from the SIMD versions
      __m128 zz[3];
      for(int vv = 0; vv < 3; vv++)
      {
        zz[vv] = _mm_set1_ps(Z[vv].m128_f32[lane]);
      }

      //drop culled triangle

      int startXx = startX.m128i_i32[lane];
      int endXx  = endX.m128i_i32[lane];
      int startYy = startY.m128i_i32[lane];
      int endYy  = endY.m128i_i32[lane];

      __m128i aa0 = _mm_set1_epi32(A0.m128i_i32[lane]);
      __m128i aa1 = _mm_set1_epi32(A1.m128i_i32[lane]);
      __m128i aa2 = _mm_set1_epi32(A2.m128i_i32[lane]);

      __m128i bb0 = _mm_set1_epi32(B0.m128i_i32[lane]);
      __m128i bb1 = _mm_set1_epi32(B1.m128i_i32[lane]);
      __m128i bb2 = _mm_set1_epi32(B2.m128i_i32[lane]);

      __m128i cc0 = _mm_set1_epi32(C0.m128i_i32[lane]);
      __m128i cc1 = _mm_set1_epi32(C1.m128i_i32[lane]);
      __m128i cc2 = _mm_set1_epi32(C2.m128i_i32[lane]);

      __m128i aa0Inc = _mm_mul_epi32(aa0, _mm_setr_epi32(1,2,3,4));
      __m128i aa1Inc = _mm_mul_epi32(aa1, _mm_setr_epi32(1,2,3,4));
      __m128i aa2Inc = _mm_mul_epi32(aa2, _mm_setr_epi32(1,2,3,4));

      __m128i alpha0 = _mm_add_epi32(_mm_mul_epi32(aa0, _mm_set1_epi32(startXx)), _mm_mul_epi32(bb0, _mm_set1_epi32(startYy)));
      alpha0 = _mm_add_epi32(cc0, alpha0);
      __m128i beta0 = _mm_add_epi32(_mm_mul_epi32(aa1, _mm_set1_epi32(startXx)), _mm_mul_epi32(bb1, _mm_set1_epi32(startYy)));
      beta0 = _mm_add_epi32(cc1, beta0);
      __m128i gama0 = _mm_add_epi32(_mm_mul_epi32(aa2, _mm_set1_epi32(startXx)), _mm_mul_epi32(bb2, _mm_set1_epi32(startYy)));
      gama0 = _mm_add_epi32(cc2, gama0);

      int  rowIdx = (startYy * res.x + startXx);

      __m128 zx = _mm_mul_ps(_mm_cvtepi32_ps(aa1), zz[1]);
      zx = _mm_add_ps(zx, _mm_mul_ps(_mm_cvtepi32_ps(aa2), zz[2]));
      zx = _mm_mul_ps(zx, _mm_setr_ps(1.f, 2.f, 3.f, 4.f));

      // Texels traverse
      for(int r = startYy; r < endYy; r++,
        rowIdx += res.x,
        alpha0 = _mm_add_epi32(alpha0, bb0),
        beta0 = _mm_add_epi32(beta0, bb1),
        gama0 = _mm_add_epi32(gama0, bb2))
      {
        // Compute barycentric coordinates
        // Z0 as an origin
        int index = rowIdx;
        __m128i alpha = alpha0;
        __m128i beta = beta0;
        __m128i gama = gama0;

        //Compute barycentric-interpolated depth
        __m128 depth = zz[0];
        depth = _mm_add_ps(depth, _mm_mul_ps(_mm_cvtepi32_ps(beta), zz[1]));
        depth = _mm_add_ps(depth, _mm_mul_ps(_mm_cvtepi32_ps(gama), zz[2]));
        __m128i anyOut = _mm_setzero_si128();

        __m128i mask;
        __m128 previousDepth;
        __m128 depthMask;
        __m128i finalMask;
        for(int c = startXx; c < endXx;
          c+=4,
          index+=4,
          alpha = _mm_add_epi32(alpha, aa0Inc),
          beta  = _mm_add_epi32(beta, aa1Inc),
          gama  = _mm_add_epi32(gama, aa2Inc),
          depth = _mm_add_ps(depth, zx))
        {
          mask = _mm_or_si128(_mm_or_si128(alpha, beta), gama);
          previousDepth = _mm_loadu_ps(&(buffer[index]));

          //calculate current depth
          //(log(depth) - -6.907755375) * 0.048254941;
          __m128 curdepth = _mm_mul_ps(_mm_sub_ps(log_ps(depth),_mm_set1_ps(-6.907755375)),_mm_set1_ps(0.048254941));
          curdepth = _mm_sub_ps(curdepth, _mm_set1_ps(0.05));      

          depthMask = _mm_cmplt_ps(curdepth, previousDepth);    
          finalMask = _mm_andnot_si128(mask, _mm_castps_si128(depthMask));
          anyOut = _mm_or_si128(anyOut, finalMask);

        }//for each column  

        if(!_mm_testz_si128(anyOut, _mm_set1_epi32(0x80000000)))
        {
          // stop timer
          QueryPerformanceCounter(&t2);

          // compute and print the elapsed time in millisec
          elapsedTime = (t2.QuadPart - t1.QuadPart) * 1000.0 / frequency.QuadPart;

          RasterizationStats::RasterizeSSETimeSpent += elapsedTime;

          return true; //early exit
        }

      }// for each row

    }// for each triangle
  }// for each set of SIMD# triangles

  return false;
}
Собственно, всё, технология Coverage Buffer в общих чертах готова.
В процессе имплементации, правда, вскрылся еще ряд других сложностей и багов, связанных с рендером леса, на борьбу с которыми ушло в 20 раз больше времени, чем на сам C-Buffer, но борьба с ними не входит в тему данного поста =)

Результаты

Использование технологии C-Buffer для интеллектуального OC для рендеринга леса позволило уменьшить время рендера кадра на открытых пространствах от 5 до 20мс, а в закрытых - до 30мс (в случаях, когда отсекается вся растительность). Однако дало оверхед в 1.5-2мс при неэффективном отсечении (т.е. технология использована, но ничего не отсеклось).

pic3 | Coverage Buffer из CryENGINE в деталях

Комментарии

Нет комментариев. Ваш будет первым!