Программирование игр, создание игрового движка, OpenGL, DirectX, физика, форум
GameDev.ru / Программирование / Форум / Screenspace Raymarching

Screenspace Raymarching

Страницы: 1 2 Следующая »
SuslikМодераторwww14 июля 20184:38#0
Хочу обсудить интересные алгоритмы трассировки лучей в скринспейсе. Обычно такие алгоритмы можно применять для самых разных техник от скринспейс теней до скринспейс отражений, поэтому в первую очередь интересует именно центральная часть любого из этих алгоритмов — быстрый и точный поиск пересечения луча с depth buffer'ом.

Самый базовый алгоритм с трассировкой с постоянным шагом в мировых или view-координатах не рассматриваем за очевидностью. Также логичным улучшением алгоритма является трассировка в экранных координатах для сохранения плотности выборок: http://jcgt.org/published/0003/04/04/paper-lowres.pdf . Теоретически этот алгоритм позволяет шагать с шагом 1 пиксель, гарантированно не пропуская тонкие фичи, однако, выпускать много длинных лучей, шагая с таким маленьким шагом — очень дорого.

Существуют более продвинутые acceleration data structures, которые испольуют мипмапы для хранения минимальной и максимальной глубины в группе пикселей и с дальнейшей трассировкой всего этого дела по типу октри: http://jankautz.com/publications/AcceleratedSSRT_HPG15.pdf http://www.highperformancegraphics.org/wp-content/uploads/2017/Pa… ayTracing.pdf Мне нравится идея построения отдельной структуры для ускорения и нравится, что эти техники позволяют гарантированно находить пересечение, не пропуская тонких фич, однако, трассировка по октри — не бесплатное удовольствие и реализуется не слишком красиво.

Однако, в практических применениях вовсе не всегда необходимо искать именно все пересечения с тонкими фичами, потому что потом их всё равно часто придётся выбрасывать, если исходить из предположения о конечной толщине объектов. Поэтому я думал в следующем направлении:
Для трассировки луча из точку [cht]p_0[/cht] в [cht]p_1[/cht], нам нужно найти такой минимальный скаляр [cht]t \in [0..1][/cht], для которого выполняется: [cht]f(t) = \text{depth}(\text{project}(p_0 + t(p_1 - p_0)) < 0[/cht] то есть задача сводится к поиску первого нуля функции [cht]f(t)[/cht].

Очевидно, в общем случае [cht]f(t)[/cht] может быть какой угодно плохой и эффективных методов поиска её корней существовать не может, однако, мы можем сами на неё накладывать такие ограничения, какие захотим, чтобы решить задачу эффективнее. Например, можно сказать, что по ходу луча производная функции не превосходит некоторой фиксированной величины: [cht]\left|\frac{df}{dt}\right| < \alpha[/cht] и далее при трассировке использовать не реальные значения функции, а построенные рекуррентно: [cht]\hat f(x+\Delta x) = \max(\hat f(x) - \alpha \Delta x, f(x + \Delta x))[/cht]
в результате если функция не удовлетворяет условию Липшица:
Изображение
мы фактически проецируем её значения на эти ограничивающие прямые, позволяя эффективно искать нули модифицированной функции. Однако, у метода есть проблема, что результирующая функция получается разной в зависимости от того, в каком порядке и с каким шагом строятся точки для неё, поэтому методы с адаптивным шагом (да даже просто [cht]\Delta x = \frac{f(x)}{\alpha}[/cht]) дают шумный результат, так как небольшое изменение входных данных может сильно повлиять на выходные.

Может быть, кто-то встречал интересные алгоритмы для эффективного raymarching'а буфера глубины? Или есть свои соображения, что можно попробовать?

Правка: 14 июля 2018 4:39

MrShoorУчастникwww14 июля 20185:16#1
Suslik
> и реализуется не слишком красиво.
Да вроде просто реализуется. Трейсишь две точки уменьшая mip на каждом хите, и перезапуская трасировку с новой парой точек, и так пока не дойдешь до нулевого мипа.
MrShoorУчастникwww14 июля 20185:49#2
Короче как бы я решал задачу:

Мы в глубине храним min/max, а значит каждый пиксель такой глубины однозначно описывает маленький фрустум. Каждый mip уровень большего разрешения - разбивает этот фрустум на 4 фрустума.
Поэтому в первой реализации можно написать такую пару функций:

Frustum GetDepthFrustum(float2 UV, int mip) {
}

bool Intersect(float3 ray_origin, float3 ray_dir, Frustum f, out float t) {
}

и дальше так:

const float STEP_DIR[4] = {{-1,-1}, {-1,1}, {1,-1}, {1,1}};

//сначала проверяем возможны ли вообще пересечения на самом последнем мипе 1*1, чтобы быть уверенным, что пересечение будет
float dummy;
if Intersect( ro, rd, GetDepthFrusum(0.5, num_mips - 1), dummy ) {
  //и запускаем цикл по всем мипам лежащим выше:
  float2 UV = 0.5;
  float2 UVStep = 0.25;  
  for (int mip = num_mips-2; mip >= 0; mip--) { 
    float min_t = 10000.0;
    float min_UV;
    //и проверяем 4 фрустума этого mip-а, чтобы определить, какой из фрустумов оставить
    for (int i = 0; i < 4; i++) {
      float2 UVi = UV + UVStep * STEP_DIR[i];
      float t;
      if (Intersect( ro, rd, GetDepthFrusum(UVi, mip), t)) 
        if (t < min_t) { //оставляем понятное дело ближайший
          min_UV = UVi;
          min_t = t;
        }
    }
    UV = min_UV;
    UVStep /= 2.0;
  }
  //ну и как бы тут все, теперь у нас в UV хранятся координаты текстуры глубины из нулевого мипа
}

Ну а дальше можно уже оптимизацией заняться, т.к. уверен, что пересечение фрустума с лучом можно сильно ускорить.

Правка: 14 июля 2018 5:52

SuslikМодераторwww14 июля 20186:03#3
MrShoor
ты не учёл, что если луч пересекает большой фрастум, то это не значит, что он пересекает хоть один из его под-фрастумов. короче, это обозначает, что проверять нужно все под-фрастумы, с которыми есть пересечение, а не только самый ближний. а это значит, что без рекурсии не обойтись. а так как рекурсий в sm 3.0 нет, это значает, что её придётся вручную разворачивать в стек. боль. и алгоритм внезапно становится гораздо менее привлекательным.

на самом деле весь стек можно не хранить, достаточно уметь обходить все субпиксели текущего пикселя и переходить от текущего к следующему, но я не знаю, как это красиво и эффективно реализовать.

ещё, кстати, интересный момент. мне по сути даже не нужна точка пересечения, мне важен сам факт — пересекает луч буфер глубины или нет.

Правка: 14 июля 2018 6:20

SuslikМодераторwww14 июля 20186:31#4
нашёл ништяк: http://www.tevs.eu/project_i3d08.html
MrShoorУчастникwww14 июля 20187:48#5
Suslik
> ты не учёл, что если луч пересекает большой фрастум, то это не значит, что он
> пересекает хоть один из его под-фрастумов
Да, так и есть, мой пример не рабочий. :)

> вручную разворачивать в стек. боль. и алгоритм внезапно становится гораздо
> менее привлекательным.
Но вручную разворачивать в стек там один фиг не надо, потому что тебе не надо впринципе "помнить" предыдущее значение, его можно вычислять. Я кажется уже придумал как это красиво можно записать в коде. В общем если интересно - могу попробовать набросать реализацию, но смогу это либо завтра, либо в понедельник.

> нашёл ништяк: http://www.tevs.eu/project_i3d08.html
Ништяк не читал особо. Лишь глянул, какой-то код есть, выглядит норм. Если ништяк заработает - дай знать.

SuslikМодераторwww14 июля 20188:51#6
MrShoor
> Ништяк не читал особо. Лишь глянул, какой-то код есть, выглядит норм. Если
> ништяк заработает - дай знать.
там то и есть. пассы руками про "стек можно не хранить, значения можно вычислять", но в таких задачах 90% итоговой производительности определяется чисто реализацией. у них реализация в пейпере жуткая. свою я напишу, но на 100% уверен, что что-то можно будет улучшить. поэтому если ты напишешь свою реализацию, я смогу слепить из двух одну нормальную, всем профит :D

на самом деле, я считаю, задача интересная и полезная в жизни для самых разных штук, поэтому твоя реализация в любом случае не пропадёт.

у меня *быстренько* накатать реализацию не получилось, потому что в домашнем opengl wrapper'е нету возможности байндить мипы к фреймбуфферу. пока переписываю эту часть, потом можно сравнить, у кого лучше получится.

Правка: 14 июля 2018 8:53

/A\Постоялецwww14 июля 20189:39#7
Suslik
> нашёл ништяк:
maximum mipmap, я делал такую штуку для ландшафта, самое сложное это в конце найти точное пересечение с учетом интерполяции карты высот, но для скринспейс техник это не нужно
g-contПостоялецwww14 июля 201811:15#8
А что такое тонкие фичи?
SuslikМодераторwww14 июля 201811:17#9
g-cont
например, линия толщиной 1 пиксель очень близко к камере. или просто ветки у дерева.
Panzerschrek[CN]Участникwww14 июля 201814:31#10
Suslik
> гарантированно не пропуская тонкие фичи
Да, можно забить, т. к. ещё на этапе растеризации легко пропустить мелкие фичи.
SuslikМодераторwww14 июля 201818:17#11
в общем, написал я свою реализацию трассировщика по октри:
Изображение

к сожалению, результат оказался примерно такой, какой я ожидал: примерно та же скорость, что и у аккуратно реализованного обычного трассировщика по шагам. да, точность 100%, это радует. да, в принципе алгоритм позволяет трассировать абсолютно любые карты высот. но, мипмапы строить — тоже не совсем бесплатное удовольствие. ещё я ищу хоть какое-то пересечение, а если искать только самое близкое, то производительность алгоритма ещё радостно падает раза в 2. но идейно алгоритм очень крутой — надеюсь, его ещё можно оптимизировать.

вот моя реализация. не знаю, насколько она оптимальна:

float GetRaytraceTransparency(vec3 startViewPoint, vec3 endViewPoint)
{
  vec3 startScreenspacePoint = Project(startViewPoint, camProjection);
  vec3 endScreenspacePoint = Project(endViewPoint, camProjection);

  ivec2 startPixel = ivec2(startScreenspacePoint.xy * viewportSize + vec2(0.5f));
  ivec2 endPixel = ivec2(endScreenspacePoint.xy * viewportSize + vec2(0.5f));

  float transparency = 1.0f;

  vec3 screenRayStart = startScreenspacePoint;
  vec3 screenRayEnd = endScreenspacePoint;

  vec3 invRayDir = vec3(1.0f) / (screenRayEnd - screenRayStart);

  int skipCount = 0;

  //reference
  /*for(float ratio = 0.0f; ratio < 1.0f; ratio += 1e-2f)
  {
    vec3 screenPoint = mix(screenRayStart, screenRayEnd, ratio);
    if(texelFetch(depthTex, ivec2(screenPoint.xy * viewportSize), 0).r + 1e-4f < screenPoint.z)
      transparency = 0.0f;
  }*/
  ivec3 cellIndex = ivec3(0, 0, 9); //start at 9th mip
  float bestRatio = 1.0f;
  for(int i = 0; i < 1000; i++)
  {
    float currDepth = texelFetch(depthTex, cellIndex.xy, cellIndex.z).r;

    vec2 minPoint2, maxPoint2;
    GetPixelAABB(cellIndex, minPoint2, maxPoint2);
    vec3 minPoint = vec3(minPoint2, 10.0f);
    vec3 maxPoint = vec3(maxPoint2, (currDepth + 1e-4f));

    float tmin, tmax;
    if(skipCount > 0)
    {
      skipCount -= SkipCell(cellIndex) ? 1 : 0;
    }else
    if(BoxRayCast3(screenRayStart, invRayDir, minPoint, maxPoint, tmin, tmax) && tmin < bestRatio && tmax > 0.01f)
    {
      if(cellIndex.z == 0)
      {
        transparency *= exp(-100.1f);
        bestRatio = tmin;
        break; //comment this break to find closest intersection
        skipCount++;
      }else
      {
        DescendCell(cellIndex);
      }
    }else
    {
      if(cellIndex.z < 10) //10 mips total
        skipCount++;
      else
        break;
    }
  }
  return transparency;
}
посчитал, за сколько итераций оно сходится. получается что-то около 100-500. не больно ли это дофига? с таким количеством можно просто с шагом в 1 пиксель по диагонали весь фреймбуффер проползти. ну, почти.

Panzerschrek[CN]
> Да, можно забить, т. к. ещё на этапе растеризации легко пропустить мелкие фичи.
не надо мне, пожалуйста, объяснять, что я должен хотеть.

Правка: 14 июля 2018 18:36

Panzerschrek[CN]Участникwww14 июля 201819:17#12
Suslik
> в общем, написал я свою реализацию трассировщика по октри:
Какой-то велосипед. Даже два.

А если серьёзно, то для чего тебе нужна трассировка в экранном пространстве? От неё ведь ужасные артефакты, чтобы делать хоть какие-нибудь адекватные тени.

SuslikМодераторwww14 июля 201819:18#13
Panzerschrek[CN]
скоро узнаем.
MrShoorУчастникwww14 июля 201819:19#14
Panzerschrek[CN]
> А если серьёзно, то для чего тебе нужна трассировка в экранном пространстве?
SSGI поди какой нибудь
Страницы: 1 2 Следующая »

/ Форум / Программирование игр / Графика

2001—2018 © GameDev.ru — Разработка игр