Трассировка лучей в пространстве вокселей

Опубликовано от

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

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

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

Алгоритм состоит из следующих этапов:

  1. Этап предварительной подготовки
    • вычисляем расстояние, которое пролетает луч при его перемещении на один воксель по каждой координате
    • вычисляем шаг по каждой оси (+1 или -1, в зависимости от направления луча)
    • вычисляем расстояние до ближайшего столкновения по каждой оси, необходимо учитывать, что если луч направлен вдоль отрицательного направления текущей оси, расстояние вычитается из единицы.
    • вычисляем текущее положение в координатной сетке (целочисленное положение луча)
  2. Находим ось, вдоль которой случится ближайшее пересечение координатной сетки
  3. Перемещаемся на один воксель по данной оси
  4. Если в новой координате не пусто, произошло столкновение
  5. Пересчитываем расстояние до ближайшего столкновения по данной оси
  6. Итеративно повторяем алгоритм, начиная с этапа 2

    В рамках алгоритма удобно считать, что к координатам точки и вектора можно обращаться по индексу(v[0] - x координата, v[1] - y координата и т.д.), это позволяет не только обобщить алгоритм на пространство произвольной размерности, но и избежать дублирования кода.

    Предположим, что мир представляет из себя трёхмерный массив world, к которому можно обращаться по индексу-точке world[p], а результат этой операции (воксель) можно проверить на пустоту функцией empty, если для текущего вокселя операция empty возвращает false, считается что произошло столкновение, после чего производится его обработка (обработка столкновения не отличается от таковой для обычной трассировки лучей).

// поиск оси с минимальным значением
function argmin(p: intPoint): int {
    return
        p[0] < p[1] ?
        p[0] < p[2] ? 0 : 2:
        p[1] < p[2] ? 1 : 2;
}

function Trace(p: Point, v: Point): Color {
    var len: Point;         // перемещении по каждой координате
    var step: intPoint;     // шаг по каждой оси
    var next: Point;        // расстояние до ближайшего столкновения по каждой оси
    var pixel: intPoint;    // текущее положение в координатной сетке

    for (int i = 0; i < 3; ++i) {
        len[i] = std::abs(1 / v[i]);
        step[i] = signum(v[i]);
        pixel[i] = floor(p[i]);
        next[i] = len[i] * (v[i] > 0 ? 1 - (p[i] - pixel[i]) : p[i] - pixel[i]);
    }

    while (true) {
        // поиск оси, вдоль которой произойдёт ближайшее столкновение
        var axis = argmin(next);

        // перемещение текущей координаты по соответствующей оси
        pixel[axis] += step[axis];

        // проверка столкновения
        if (!empty(world[pixel]))
            return intersection(pixel, p + v * next[axis], v); // обработка столкновения

        // увеличение расстояния до ближайшего пересечения данной оси
        next[axis] += len[axis];
    }
}

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