[Первая и вторая части.]


Сегодня мы совершим большой скачок. Мы отойдём от исключительно сферических конструкций и бесконечной плоскости, которые трассировали ранее, и добавим треугольники — всю суть современной компьютерной графики, элемент, из которого состоят все виртуальные миры. Если вы хотите продолжить с того, чем мы закончили в прошлый раз, то воспользуйтесь кодом из части 2. Готовый код того, что мы будем делать сегодня, выложен здесь. Давайте приступим!

Треугольники


Треугольник — это всего лишь список трёх соединённых вершин, каждая из которых хранит свою позицию, а иногда и нормаль. Порядок обхода вершин с вашей точки обзора определяет, на что мы смотрим — на переднюю или заднюю грань треугольника. Традиционно «передом» считается порядок обхода против часовой стрелки.

Во-первых, нам нужно иметь возможность определять, пересекает ли луч треугольник, и если да, то в какой точке. Очень популярный (но совершенно точно не единственный) алгоритм для определения пересечений луча с треугольником был предложен в 1997 году джентльменами Томасом Акенин-Меллером и Беном Трембором. Подробно о нём можно прочитать в их статье «Fast, Minimum Storage Ray-Triangle Intersection» здесь.

Код из статьи легко можно портировать в код шейдера на HLSL:

static const float EPSILON = 1e-8;

bool IntersectTriangle_MT97(Ray ray, float3 vert0, float3 vert1, float3 vert2,
    inout float t, inout float u, inout float v)
{
    // find vectors for two edges sharing vert0
    float3 edge1 = vert1 - vert0;
    float3 edge2 = vert2 - vert0;

    // begin calculating determinant - also used to calculate U parameter
    float3 pvec = cross(ray.direction, edge2);

    // if determinant is near zero, ray lies in plane of triangle
    float det = dot(edge1, pvec);

    // use backface culling
    if (det < EPSILON)
        return false;
    float inv_det = 1.0f / det;

    // calculate distance from vert0 to ray origin
    float3 tvec = ray.origin - vert0;

    // calculate U parameter and test bounds
    u = dot(tvec, pvec) * inv_det;
    if (u < 0.0 || u > 1.0f)
        return false;

    // prepare to test V parameter
    float3 qvec = cross(tvec, edge1);

    // calculate V parameter and test bounds
    v = dot(ray.direction, qvec) * inv_det;
    if (v < 0.0 || u + v > 1.0f)
        return false;

    // calculate t, ray intersects triangle
    t = dot(edge2, qvec) * inv_det;

    return true;
}

Чтобы воспользоваться этой функцией, нам нужен луч и три вершины треугольника. Возвращаемое значение сообщает нам, произошло ли пересечение треугольника. В случае пересечения вычисляются три дополнительных значения: t описывает расстояние вдоль луча до точки пересечения, а u / v — это две из трёх барицентрических координат, определяющих местоположение точки пересечения на треугольнике (последнюю координату можно вычислить как w = 1 - u - v). Если вы пока не знакомы с барицентрическими координатами, то прочитайте их превосходное объяснение на Scratchapixel.

Без лишних промедлений давайте оттрассируем один треугольник с указанными в коде вершинами! Найдите в шейдере функцию Trace и добавьте в неё следующий фрагмент кода:

// Trace single triangle
float3 v0 = float3(-150, 0, -150);
float3 v1 = float3(150, 0, -150);
float3 v2 = float3(0, 150 * sqrt(2), -150);
float t, u, v;
if (IntersectTriangle_MT97(ray, v0, v1, v2, t, u, v))
{
    if (t > 0 && t < bestHit.distance)
    {
        bestHit.distance = t;
        bestHit.position = ray.origin + t * ray.direction;
        bestHit.normal = normalize(cross(v1 - v0, v2 - v0));
        bestHit.albedo = 0.00f;
        bestHit.specular = 0.65f * float3(1, 0.4f, 0.2f);
        bestHit.smoothness = 0.9f;
        bestHit.emission = 0.0f;
    }
}

Как я и говорил, t хранит расстояние вдоль луча, и мы можем напрямую использовать это значение для вычисления точки пересечения. Нормаль, которая важна для вычисления правильного отражения, может быть вычислена с помощью векторного произведения любых двух рёбер треугольника. Запустите режим игры и полюбуйтесь своим первым оттрассированным треугольником:


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

Меши из треугольников


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

В компьютерной графике меш задаётся несколькими буферами, самыми важными из которых являются буферы вершин и индексов. Буфер вершин — это список 3D-векторов, описывающий позицию каждой вершины в пространстве объекта (это значит, что такие значения не нужно изменять при переносе, повороте или масштабировании объекта — они преобразуются из пространства объекта в мировое пространство на лету, с помощью матричного умножения). Буфер индексов — это список целочисленных значений, являющихся индексами, указывающими на буфер вершин. Каждые три индекса составляют треугольник. Например, если буфер индексов имеет вид [0, 1, 2, 0, 2, 3], то в нём есть два треугольника: первый треугольник состоит из первой, второй и третьей вершин в буфере вершин, а второй треугольник состоит из первой, третьей и четвёртой вершин. Следовательно, буфер индексов также определяет вышеупомянутый порядок обхода. Кроме буферов вершин и индексов могут существовать дополнительные буферы, добавляющие к каждой вершине другую информацию. Самые часто встречающиеся дополнительные буферы хранят нормали, координаты текстур (которые называются texcoords или просто UV), а также цвета вершин.

Использование GameObjects


В первую очередь нам нужно узнать, какие GameObjects должны стать частью процесса трассировки лучей. Наивным решением было бы просто воспользоваться FindObjectOfType<MeshRenderer>(), но сделаем нечто более гибкое и быстрое. Давайте добавим новый компонент RayTracingObject:

using UnityEngine;

[RequireComponent(typeof(MeshRenderer))]
[RequireComponent(typeof(MeshFilter))]
public class RayTracingObject : MonoBehaviour
{
    private void OnEnable()
    {
        RayTracingMaster.RegisterObject(this);
    }

    private void OnDisable()
    {
        RayTracingMaster.UnregisterObject(this);
    }
}

Этот компонент добавляется к каждому объекту, который мы хотим использовать для трассировки лучей и занимается их регистрацией с помощью RayTracingMaster. Добавим в мастер следующие функции:

private static bool _meshObjectsNeedRebuilding = false;
private static List<RayTracingObject> _rayTracingObjects = new List<RayTracingObject>();

public static void RegisterObject(RayTracingObject obj)
{
    _rayTracingObjects.Add(obj);
    _meshObjectsNeedRebuilding = true;
}

public static void UnregisterObject(RayTracingObject obj)
{
    _rayTracingObjects.Remove(obj);
    _meshObjectsNeedRebuilding = true;
}

Всё идёт хорошо — теперь мы знаем, какие объекты нужно трассировать. Но далее идёт сложная часть: мы собираемся собрать все данные от мешей Unity (матрица, буферы вершин и индексы — помните о них?), записать их в собственные структуры данных и загрузить их в GPU, чтобы ими мог воспользоваться шейдер. Давайте начнём с задания структур данных и буферов на стороне C#, в мастере:

struct MeshObject
{
    public Matrix4x4 localToWorldMatrix;
    public int indices_offset;
    public int indices_count;
}

private static List<MeshObject> _meshObjects = new List<MeshObject>();
private static List<Vector3> _vertices = new List<Vector3>();
private static List<int> _indices = new List<int>();
private ComputeBuffer _meshObjectBuffer;
private ComputeBuffer _vertexBuffer;
private ComputeBuffer _indexBuffer;

… а теперь давайте сделаем то же самое в шейдере. Вы ведь к этому уже привыкли?

struct MeshObject
{
    float4x4 localToWorldMatrix;
    int indices_offset;
    int indices_count;
};

StructuredBuffer<MeshObject> _MeshObjects;
StructuredBuffer<float3> _Vertices;
StructuredBuffer<int> _Indices;

Структуры данных готовы, и мы можем заполнить их настоящими данными. Мы собираем все вершины всех мешей в один большой List<Vector3>, а все индексы в большой List<int>. С вершинами никаких проблем не возникает, но индексы нужно изменить так, чтобы они продолжали указывать на верную вершину в нашем большом буфере. Представьте, что мы уже добавили объекты с 1000 вершин, а теперь добавляем простой меш-куб. Первый треугольник может состоять из индексов [0, 1, 2], но так как у нас в буфере уже было 1000 вершин, то перед добавлением вершин куба нужно сместить индексы. То есть они превратятся в [1000, 1001, 1002]. Вот как это выглядит в коде:

private void RebuildMeshObjectBuffers()
{
    if (!_meshObjectsNeedRebuilding)
    {
        return;
    }

    _meshObjectsNeedRebuilding = false;
    _currentSample = 0;

    // Clear all lists
    _meshObjects.Clear();
    _vertices.Clear();
    _indices.Clear();

    // Loop over all objects and gather their data
    foreach (RayTracingObject obj in _rayTracingObjects)
    {
        Mesh mesh = obj.GetComponent<MeshFilter>().sharedMesh;

        // Add vertex data
        int firstVertex = _vertices.Count;
        _vertices.AddRange(mesh.vertices);

        // Add index data - if the vertex buffer wasn't empty before, the
        // indices need to be offset
        int firstIndex = _indices.Count;
        var indices = mesh.GetIndices(0);
        _indices.AddRange(indices.Select(index => index + firstVertex));

        // Add the object itself
        _meshObjects.Add(new MeshObject()
        {
            localToWorldMatrix = obj.transform.localToWorldMatrix,
            indices_offset = firstIndex,
            indices_count = indices.Length
        });
    }

    CreateComputeBuffer(ref _meshObjectBuffer, _meshObjects, 72);
    CreateComputeBuffer(ref _vertexBuffer, _vertices, 12);
    CreateComputeBuffer(ref _indexBuffer, _indices, 4);
}

Вызовем RebuildMeshObjectBuffers в функции OnRenderImage, и не забудем освободить новые буферы в OnDisable. Вот две вспомогательные функции, которые я использовал в показанном выше коде, чтобы немного упростить обработку буферов:

private static void CreateComputeBuffer<T>(ref ComputeBuffer buffer, List<T> data, int stride)
    where T : struct
{
    // Do we already have a compute buffer?
    if (buffer != null)
    {
        // If no data or buffer doesn't match the given criteria, release it
        if (data.Count == 0 || buffer.count != data.Count || buffer.stride != stride)
        {
            buffer.Release();
            buffer = null;
        }
    }

    if (data.Count != 0)
    {
        // If the buffer has been released or wasn't there to
        // begin with, create it
        if (buffer == null)
        {
            buffer = new ComputeBuffer(data.Count, stride);
        }

        // Set data on the buffer
        buffer.SetData(data);
    }
}

private void SetComputeBuffer(string name, ComputeBuffer buffer)
{
    if (buffer != null)
    {
        RayTracingShader.SetBuffer(0, name, buffer);
    }
}

Отлично, мы создали буферы и они заполнены нужными данными! Теперь нам просто нужно сообщить об этом шейдеру. Добавим в SetShaderParameters следующий код (и благодаря новым вспомогательным функциям мы можем сократить код буфера сфер):

SetComputeBuffer("_Spheres", _sphereBuffer);
SetComputeBuffer("_MeshObjects", _meshObjectBuffer);
SetComputeBuffer("_Vertices", _vertexBuffer);
SetComputeBuffer("_Indices", _indexBuffer);

Итак, работа скучноватая, но давайте посмотрим, что мы только что сделали: мы собрали все внутренние данные мешей (матрицу, вершины и индексы), поместили их в удобную и простую структуру, а затем отправили в GPU, который теперь с нетерпением ждёт, когда их можно будет использовать.

Трассировка мешей


Давайте не будем заставлять его ждать. В шейдере у нас уже есть код трассировки отдельного треугольника, а меш — это, по сути, просто множество треугольников. Единственный новый аспект здесь заключается в том, что мы используем матрицу для преобразования вершин из пространства объекта в мировое пространство с помощью встроенной функции mul (сокращение от multiply). Матрица содержит перенос, поворот и масштаб объекта. Она имеет размер 4?4, поэтому для умножения нам понадобится 4d-вектор. Первые три компонента (x, y, z) берутся из буфера вершин. Четвёртому компоненту (w) мы задаём значение 1, потому что имеем дело с точкой. Если бы это было направление, то мы бы записали в него 0, чтобы игнорировать все переносы и масштаб в матрице. Вас это сбивает с толку? Тогда прочитайте не меньше восьми раз этот туториал. Вот код шейдера:

void IntersectMeshObject(Ray ray, inout RayHit bestHit, MeshObject meshObject)
{
    uint offset = meshObject.indices_offset;
    uint count = offset + meshObject.indices_count;
    for (uint i = offset; i < count; i += 3)
    {
        float3 v0 = (mul(meshObject.localToWorldMatrix, float4(_Vertices[_Indices[i]], 1))).xyz;
        float3 v1 = (mul(meshObject.localToWorldMatrix, float4(_Vertices[_Indices[i + 1]], 1))).xyz;
        float3 v2 = (mul(meshObject.localToWorldMatrix, float4(_Vertices[_Indices[i + 2]], 1))).xyz;

        float t, u, v;
        if (IntersectTriangle_MT97(ray, v0, v1, v2, t, u, v))
        {
            if (t > 0 && t < bestHit.distance)
            {
                bestHit.distance = t;
                bestHit.position = ray.origin + t * ray.direction;
                bestHit.normal = normalize(cross(v1 - v0, v2 - v0));
                bestHit.albedo = 0.0f;
                bestHit.specular = 0.65f;
                bestHit.smoothness = 0.99f;
                bestHit.emission = 0.0f;
            }
        }
    }
}

Мы всего в одном шаге от того, чтобы увидеть всё это в действии. Давайте немного реструктурируем функцию Trace и добавим трассировку объектов-мешей:

RayHit Trace(Ray ray)
{
    RayHit bestHit = CreateRayHit();
    uint count, stride, i;

    // Trace ground plane
    IntersectGroundPlane(ray, bestHit);

    // Trace spheres
    _Spheres.GetDimensions(count, stride);
    for (i = 0; i < count; i++)
    {
    	IntersectSphere(ray, bestHit, _Spheres[i]);
    }

    // Trace mesh objects
    _MeshObjects.GetDimensions(count, stride);
    for (i = 0; i < count; i++)
    {
    	IntersectMeshObject(ray, bestHit, _MeshObjects[i]);
    }

    return bestHit;
}

Результаты


Вот и всё! Давайте добавим несколько простых мешей (вполне подойдут примитивы Unity), дадим им компонент RayTracingObject и понаблюдаем за магией. Не используйте пока детализированных мешей (больше нескольких сотен треугольников)! Нашему шейдеру не хватает оптимизации, и если перестараться, то для трассировки хотя бы одного сэмпла на пиксель могут уйти секунды или даже минуты. В результате система остановит драйвер GPU, движок Unity может вылететь, а компьютеру потребуется перезагрузка.


Заметьте, что наши меши имеют не плавное, а плоское затенение. Так как мы пока не загрузили в буфер нормали вершин, для получения нормали вершины каждого треугольника нужно выполнять векторное произведение. Кроме того, мы не можем интерполировать по площади треугольника. Мы займёмся этой проблемой в следующей части туториала.

Ради интереса я скачал стэнфордского кролика (Stanford Bunny) из архива Моргана Макгвайра и с помощью модификатора decimate пакета Blender снизил количество вершин до 431. Вы можете поэспериментировать с параметрами освещения и жёстко прописанным материалом в функции шейдера IntersectMeshObject. Вот диэлектрический кролик с красивыми мягкими тенями и небольшим рассеянным глобальным освещением в Grafitti Shelter:


… а вот металлический кролик под сильным направленным освещением Cape Hill, отбрасывающий на плоскость пола дискотечные блики:


… а вот два маленьких кролика, прячущихся под большой каменной Сюзанной под голубым небом Kiara 9 Dusk (я прописал альтернативный материал для второго объекта, проверяя, равно ли смещение индексов нулю):


Что дальше?


Очень здорово впервые видеть реальный меш в собственном трейсере, правда? Сегодня мы обработали кое-какие данные, узнали о пересечении по алгоритму Меллера-Трэмбора и собрали всё так, чтобы сразу же можно было использовать GameObjects движка Unity. Кроме того, мы увидели одно из преимуществ трассировки лучей: как только ты добавляешь в код новое пересечение, все красивые эффекты (мягкие тени, отражённое и рассеянное глобальное освещение, и так далее) сразу начинают работать.

Рендеринг блестящего кролика занял кучу времени, и мне всё равно пришлось использовать немного фильтрации, чтобы избавиться от самого очевидного шума. Для решения этой проблемы сцена обычно записывается в пространственную структуру, например, в сетку, K-мерное дерево или иерархию ограничивающих объёмов, что значительно повышает скорость рендеринга крупных сцен.

Но нужно двигаться по порядку: дальше мы устраним проблему с нормалями, чтобы наши меши (даже низкополигональные) выглядели более гладкими, чем сейчас. Также неплохо было бы автоматически обновлять матрицы при перемещении объектов и напрямую ссылаться на материалы Unity, а не просто прописывать их в коде. Этим мы и займёмся в следующей части серии туториалов. Спасибо за чтение, и до встречи в части 4!

Комментарии (3)


  1. click0
    02.05.2019 14:45

    Непонятна постановка задачи.
    1) Определение пересечения прямой и треугольника на плоскости?
    2) Определение пересечения прямой и треугольника в (трехмерном) пространстве?

    Если пункт 1), то достаточно такого алгоритма.

    Если пункт 2) то тогда еще добавится еще один.


    1. beeruser
      03.05.2019 04:45

      В статье есть и постановка и решение. Что тут может быть непонятно?
      Второй алгоритм лучше не использовать вообще.
      Он использует acos(), что куда медленнее, чем предложенный чисто векторный алгоритм.
      И что более важно

      a kitten is sacrificed somewhere every time there's trigonometry involved down there

      www.iquilezles.org/www/articles/noacos/noacos.htm

      Ну и давали бы лучше ссылку на оригинал:
      Determining whether a line segment intersects a 3 vertex facet
      paulbourke.net/geometry/polygonmesh


  1. Bookvarenko
    02.05.2019 15:37

    Отличный материал, спасибо!