Как устроен растеризатор на GPU?

Question

При разработке ray-tracer на основе структуры ускорения дерева kd я столкнулся с проблемой. Иногда во время теста пересечения луч / треугольник (с использованием алгоритма Мёллера – Трумбора) для двух соседних треугольников луч пропускает оба из них. Это приводит к мерцанию ярких точек между темными треугольниками (или наоборот для любой контрастной пары) при медленном движении по оси обзора. Особенно для высокополигональных моделей.

Предположим, что алгоритм пересечения лучей и треугольников является самой горячей точкой всей трассировки лучей (это утверждение является результатом тщательного комплексного полномасштабного бенчмаркинга). Möller–Trumbore - самый быстрый алгоритм для GPU (кстати, я использую GPU, а не CPU). Из-за SAH (эвристика площади поверхности) около половины всего времени кадра расходуется на тесты пересечения луча и треугольника.

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

Для правильного расширения треугольников я делаю следующее: каждый рассчитывается u, v или же w умножается на длину соответствующей высоты треугольника и сравнивается с -EPSILON или же 1.0 + EPSILON измеряется в физических единицах (скажем, 0,0001 метра, если высота измеряется в метрах).

Чтобы вычислить все три высоты треугольника, мне нужно вычислить его квадрат, т.е. длину перекрестного произведения: для ABC треугольник равен AB = B - A, AC = C - A, length(cross(AB, AC))и длины каждой его стороны: length(AB), length(AC), BC = AC - AB, length(BC), куда length(vec) является sqrt(dot(vec, vec)) под капотом (упоминается для оценки его сложности для расчета). Конечно, вычисление sqrtS можно легко избежать. Но все же этот шаг расширения занимает около 10% всего времени кадра. Таким образом, существует компромисс между корректностью и скоростью выполнения.

Напомню, что у растеризатора нет такого параметра как EPSILON совсем. Его корректность не зависит от ошибок округления.

Как устроен аппаратный растеризатор? Почему это всегда дает правильные результаты?

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

Пример кода (HLSL), где правильность жертвуется в пользу скорости выполнения:

bool KdTriIntersectCheck(TKdTree kdTree,
                         in TRay ray, in float tMin, in float tMax,
                         inout THit hit, in uint face)
{ // Möller–Trumbore
  float3 A = KdGetVertex(kdTree, hit.triangleIndex, 0);
  float3 AB = KdGetVertex(kdTree, hit.triangleIndex, 1) - A;
  float3 AC = KdGetVertex(kdTree, hit.triangleIndex, 2) - A;
  float3 P = cross(ray.direction, AC);
  float denominator = dot(AB, P);
  if (denominator <= 0.0) {
    return false;
  }
  float3 Q = ray.source - A;
  hit.uv.x = dot(Q, P);
  if ((hit.uv.x < 0.0) || (hit.uv.x > denominator)) {
    return false;
  }
  float3 R = cross(Q, AB);
  hit.uv.y = dot(ray.direction, R);
  if ((hit.uv.y < 0.0) || (hit.uv.x + hit.uv.y > denominator)) {
    return false;
  }
  hit.uv /= denominator;
  hit.distance = dot(AC, R) / denominator;
  hit.isFront = true;
  return (hit.distance >= tMin - EPSILON) && (hit.distance <= tMax + EPSILON);
}