Оптимизация Ray Tracer

Question

Мне поручено оптимизировать следующий трассировщик лучей:

void Scene::RayTrace() 
{

    for (int v = 0; v < fb->h; v++)  // all vertical pixels in framebuffer
    {
        calculateFPS(); // calculates the current fps and prints it

        for (int u = 0; u < fb->w; u++) // all horizontal pixels in framebuffer
        {

            fb->Set(u, v, 0xFFAAAAAA); // background color
            fb->SetZ(u, v, FLT_MAX);  // sets the Z values to all be maximum at beginning
            V3 ray = (ppc->c + ppc->a*((float)u + .5f) + ppc->b*((float)v + .5f)).UnitVector(); // gets the camera ray

            for (int tmi = 0; tmi < tmeshesN; tmi++)  // iterates over all triangle meshes
            {
                if (!tmeshes[tmi]->enabled) // doesn't render a tmesh if it's not set to be enabled
                    continue;
                for (int tri = 0; tri < tmeshes[tmi]->trisN; tri++) // iterates over all triangles in the mesh
                {
                    V3 Vs[3]; // triangle vertices
                    Vs[0] = tmeshes[tmi]->verts[tmeshes[tmi]->tris[3 * tri + 0]];
                    Vs[1] = tmeshes[tmi]->verts[tmeshes[tmi]->tris[3 * tri + 1]];
                    Vs[2] = tmeshes[tmi]->verts[tmeshes[tmi]->tris[3 * tri + 2]];
                    V3 bgt = ppc->C.IntersectRayWithTriangleWithThisOrigin(ray, Vs); // I don't entirely understand what this does

                    if (bgt[2] < 0.0f || bgt[0] < 0.0f || bgt[1] < 0.0f || bgt[0] + bgt[1] > 1.0f) 
                        continue;
                    if (fb->zb[(fb->h - 1 - v)*fb->w + u] < bgt[2])
                        continue;

                    fb->SetZ(u, v, bgt[2]);
                    float alpha = 1.0f - bgt[0] - bgt[1];
                    float beta = bgt[0];
                    float gamma = bgt[1];
                    V3 Cs[3]; // triangle vertex colors
                    Cs[0] = tmeshes[tmi]->cols[tmeshes[tmi]->tris[3 * tri + 0]];
                    Cs[1] = tmeshes[tmi]->cols[tmeshes[tmi]->tris[3 * tri + 1]];
                    Cs[2] = tmeshes[tmi]->cols[tmeshes[tmi]->tris[3 * tri + 2]];
                    V3 color = Cs[0] * alpha + Cs[1] * beta + Cs[2] * gamma;
                    fb->Set(u, v, color.GetColor()); // sets this pixel accordingly

                }

            }


        }
        fb->redraw();
        Fl::check();
    }

}

Две вещи:

1. Я не совсем понимаю, что ppc->C.IntersectRayWithTriangleWithThisOrigin(ray, Vs); делает. Может ли кто-нибудь объяснить мне это с точки зрения трассировки лучей? Вот функция внутри моего класса "Плоская камера-обскура" (эта функция была мне дана):

   V3 V3::IntersectRayWithTriangleWithThisOrigin(V3 r, V3 Vs[3]) 
   {
   
       M33 m; // 3X3 matrix class
       m.SetColumn(0, Vs[1] - Vs[0]);
       m.SetColumn(1, Vs[2] - Vs[0]);
       m.SetColumn(2, r*-1.0f);
       V3 ret; // Vector3 class
       V3 &C = *this;
       ret = m.Inverse() * (C - Vs[0]);
       return ret;
   
   }
   

Основные шаги этого очевидны, я просто не вижу, что он на самом деле делает.

2. Как мне оптимизировать этот трассировщик лучей отсюда? Я нашел в Интернете кое-что о "деревьях кд", но я не уверен, насколько они сложны. У кого-нибудь есть хорошие ресурсы по простым решениям для оптимизации этого? У меня были некоторые трудности с расшифровкой того, что там.

Спасибо!

Answer 1

Вероятно, самая большая оптимизация на данный момент заключалась бы в использовании некоторой ограничивающей иерархии томов. Прямо сейчас код пересекает все лучи со всеми треугольниками всех объектов. С помощью BVH мы вместо этого спрашиваем: "учитывая этот луч, какие треугольники пересекаются?" Это означает, что для каждого луча вам, как правило, нужно только проверять пересечение с несколькими примитивами и треугольниками, а не с каждым треугольником в сцене.

Answer 2

1. IntersectRayWithTriangleWithThisOrigin

   • судя по всему
   • он создает матрицу обратного преобразования из ребер треугольника (базисными векторами треугольника являются X,Y)
   • не получить ось Z. Я ожидал бы направление луча там, а не положение пикселя (начало луча)
   • но может быть неправильно истолковывать что-то
   • в любом случае вычисление обратной матрицы является самой большой проблемой
   • Вы рассчитываете это для каждого треугольника на пиксель, что много
   • быстрее будет вычисление матрицы обратного преобразования каждого треугольника до трассировки лучей (один раз)
   • где X, Y - основание, а Z - перпендикулярно кабине, из которой они всегда обращены в одну сторону к камере.
   • а затем просто превратить ваш луч в него и проверить границы пересечения
   • это просто matrix*vector и мало ifs вместо вычисления обратной матрицы
   • другим способом было бы алгебраически решить пересечение луча с плоскостью
   • это должно привести к гораздо более простому уравнению, чем обращение матрицы
   • после того, что это просто вопрос проверки базисного вектора