четверг, 22 октября 2009 г.

Woop's unit triangle intersection test

После курения пейпров и вникания в кудовские кернелы реализовал и этот алгоритм. Математика - это вещь! Диву даёшься, как только получается реализовать полную проверку такого пересечения в несколько инструкций.

Кстати я не знаю точно, кто именно автор алгоритма. S. Woop указан в качестве соавтора пейпра, в котором рассматривается математика алгоритма, это правда. Но там же идут отсылки к более ранней работе J. Arenberg 1988 года, и говорится что это просто его расширенная версия. Но везде (презентации, на форумах) упоминается именно Woop.

Моя идея с матрицей преобразования хороша, но не пригодна. Впрочем, преобразование из одной системы координат в другую матрицей афинного преобразования - задача не новая, алгоритм Woop-a использует эту же идею. Проблема в том, что кроме самих текстурных координат мне нужны ещё как минимум интерполированные позиция и нормаль (растеризатор-то теперь мне ничего интерполировать не будет), и искать её удобно через те же барицентрические координаты. И алгоритм Мюллера, и алгоритм Вупа делают проверку через поиск барицентрических координат, а раз они уже есть, то использовать их для интерполяции вершинных значений - наиболее разумное решение.

Пока я фигачил тестовые реализации для этого тормоза CPU, в голове крутились мысли, как это должно быть реализовано на GPU класса DX10/11. Во-первых, зачем таскать текстурные координаты (а в перспективе - и нормали) вместе c precomputed данными? Ведь для поиска самого пересечения они не нужны, а требуются лишь тогда, когда найдено пересечение с треугольником и его индекс известен. Нужно отделить данные для интерполяции от precomputed данных для поиска пересечения, разнести их по двум буферам. Тогда буфер precomputed данных ужмётся до минимума, а значит, и фетчинг данных при линейном поиске по массиву пойдёт быстрее. А когда треугольник найден, то по индексу делаем выборку атрибутов вершин из второго буфера. Хотя тут и есть скачок по памяти, но он всего один на пиксель.

Тогда структура для алгоритма Мюллера должна быть такой:
struct prec_tri
{
float3 v0;
float3 e0;
float3 e1;
};

Тут к сожалению, в cbuffer пропадает впустую 3 вещественных, а это 12 байт из 48. Один из вариантов - использовать Buffer < float3 > и Load(). Для алгоритма Вупа достаточно матрицы 4x3 (четыре столбца по 3 элемента - поворот и перенос). Это те же 48 байт. А вот если мне нужна позиция в точке пересечения (для L, V), то не обязательно тащить вершины - можно попробовать найти по O + t * D, хотя неясно что будет с точностью и визуальным качеством. Но это так, мысли наперёд.

А вот вопрос, как именно фетчить: через cbuffer, tbuffer или Load() - очень интересен. Судя по описаниям в SDK, tbuffer оптимизирован для случайного доступа, cbuffer - для последовательного. Может оказаться, что это "шило на мыло". Можно упереться не в память, а в расчёты, kd-tree то не планирую, цикл соответственно будет только расти с ростом кол-ва треугольников. Да и моя HD 2400 очень тормозная железяка, грех на ней рэйтресингом баловаться, а может заниматься оптимизациями - в самый раз? :). Думаю, не купить ли на последние деньги HD 4770 или 4850, в районе 100$ сейчас...

Кстати, привет от компайлера шейдеров! Что-то вроде такого он пережёвывает секунд 10:

#define MAX_TRIANGLES 200

[loop]
for (int i = 0; i less than MAX_TRIANGLES; ++i)
{
prec_tri t = g_buf[ i ];
// Дальше куча расчётов.
}

Если взять, скажем, 500 - думает секунд 40. Ассемблерный листинг показывает, что цикл не разворачивается. Может компайлер проверяет валидность i для всех итераций цикла? Пробовал разные флаги подсовывать, убирать оптимизацию - бесполезно. Единственное, что помогло - замена compile-time MAX_TRIANGLES на значение из буфера констант. Тормоза пропадают. Какой из этого вывод? Незнание - это блаженство (с) The Matrix.

Комментариев нет:

Отправить комментарий