Оптимизация рекурсии трассировки лучей

Question

Играюсь с примером софтварной реализации трассировки лучей от майкрософта. На самом деле пример про многопоточность, но меня в нём привлек именно алгоритм 3D рендера.

Вот метод. Если бы это была хвостовая рекурсия, я бы легко справился, но здесь пока не могу.

using System.Numerics;

private const int maxDepth = 6;

private Vector3 TraceRay(Ray ray, Scene scene, int depth)
{
    (SceneObject obj, float distance) = ClosestIntersection(ray, scene);
    if (obj is null)
        return Vector3.Zero;

    Vector3 pos = distance * ray.Direction + ray.Start;
    Vector3 normal = obj.Normal(pos);
    Vector3 reflectDir = Vector3.Reflect(ray.Direction, normal);
    Vector3 color = GetNaturalColor(obj, pos, normal, reflectDir, scene);

    if (depth >= maxDepth)
        return color;

    // типы =              float                     Vector3
    return color + obj.Surface.Reflect(pos) * obj.Surface.Diffuse(pos) * TraceRay(new Ray(pos, reflectDir), scene, depth + 1);
}

Изначальный вызов:

Vector3 color = TraceRay(new Ray(camera.Pos, GetPoint(x, y, camera)), scene, 0);

Возможна ли линейная оптимизация без выделения дополнительной памяти? Или с выделением, но чтобы оно хотя-бы чуть-чуть быстрее заработало.

Я не буду показывать вызываемые отсюда методы и свои структуры данных, они на суть вопроса не влияют. Но если надо - пишите, добавлю в вопрос.

Вот луч.

readonly ref struct Ray
{
    public readonly Vector3 Start;
    public readonly Vector3 Direction;

    public Ray(Vector3 start, Vector3 direction)
    {
        Start = start;
        Direction = direction;
    }
}

Кстати, формулу цвета пикселя я вывел такую

c0 + r0 * (c1 + r1 * (c2 + r2 * (c3 + r3 * (c4 + r4 * (c5 + r5 * (c6))))))

cN - цвет объекта с учетом освещения
rN - коэффициенты отражения
N - итерация

Answer 1

В целом, магии, как и ожидалось, не найдено.

От рекурсии удалось избавиться, но с выделением памяти...в стеке. :)

private const int maxDepth = 6;
private const int stackDepth = maxDepth * 2 + 1;

private Vector3 TraceRay(Vector3 start, Vector3 direction, Scene scene)
{
    Span<Vector3> stack = stackalloc Vector3[stackDepth];
    int s = 0;
    while (true)
    {
        (SceneObject obj, float distance) = ClosestIntersection(start, direction, scene);
        if (obj is null)
            break;
        start += distance * direction;
        Vector3 normal = obj.Normal(start);
        direction = Vector3.Reflect(direction, normal);
        stack[s++] = GetNaturalColor(obj, start, normal, direction, scene);

        if (s == stackDepth)
            break;
        stack[s++] = obj.Surface.Reflect(start) * obj.Surface.Diffuse(start);
    }
    Vector3 color = (s & 1) == 1 ? stack[--s] : Vector3.Zero;
    while (s > 0)
    {
        color = color * stack[--s] + stack[--s];
    }
    return color;
}

Есть совсем незначительный прирост производительности, почти в рамках погрешности измерений. Но лучшего я ничего пока не придумал.

БЛОГ НА HUSL

Оптимизация рекурсии трассировки лучей

Ответы (1 шт):