Математика матриц,векторов и кватернионов в макросах Си препроцессора

Когда-то написал набор макросов для работы с матрицами, векторами и прочими сущностями используемыми в 3D графике. Выкладываю теперь в паблик домен.

http://dumpz.org/16627/

Макросы хорошо оптимизируются компилятором, так что не стоит обращать внимание на некоторую неоптимальность (мол синус считается от одного угла несколько раз и т.д. :)), это сделано намеренно. Есть однако оптимизированные варианты для пары макросов, например, matrix44_rotate_from_axis_sincos для matrix44_rotate_from_axis.

Эти макросы использовались в некоторых программах, как моих собственных, так и по работе. Известных багов нет. Тесты даже были, да потерял.

Слабые ссылки в GObject (Weak Refs)

В С++ есть различного рода умные указатели и прочие приблуды для упрощения управления динамической памятью, и вот система типов GObject написанная на чистом Си также использует подсчёт ссылок для объектов унаследованных от GObject.

Делается это функциями g_object_ref и g_object_unref, с которыми всё ясно, ref увеличивает счётчик на 1 а unref уменьшает на 1, объект создаётся с счётчиком равным единице. Как только счётчик достигает 0, объект удаляется.

Однако совсем не всегда нужно, чтобы объекты висели в памяти пока кто-нибудь не удосужится их удалить отовсюду. Для этого в GObject есть удобный механизм слабых ссылок. Работает всё очень просто, к объекту можно присоеденить обратные вызовы, которые будут вызваны при удалении объекта. Функция g_object_weak_ref добавляет такой обратный вызов :

void g_object_weak_ref(GObject *object,
GWeakNotify notify,
gpointer data);

Функция g_object_weak_unref удаляет заданный обратный вызов.

void g_object_weak_unref(GObject *object,
GWeakNotify notify,
                         gpointer data);

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

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

void g_object_add_weak_pointer(GObject *object, gpointer weak_pointer_location);
void g_object_remove_weak_pointer(GObject *object, gpointer weak_pointer_location);

Эти функции соответсвенно добавляют и удаляют специальные вызовы для обнуления укателей по переданному в качестве аргумента адресу.

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

P.S. Система типов GObject имеет кучу разной вкуснатищи, о которой я буду тут переодически писать.

Быстрый алгоритим заполнения half-edge структуры (WIP)

Общее описание

Алгоритм расчитан на применение с полигональными сетками с индексной адресацией, т.е. не с указателями.

Индексация в описании ниже начинается с 0. Под ссылкой обычно понимается индекс, если не сказано иного.

Основные этапы:

1. Создание геометрии меша. Установка вершин для всех граней. Рёбра, полурёбра и все ссылки на них заполняются заведомо не правильным индексом, чтобы потом можно было проверить заполнена ссылка или нет.
2. Проход по всем граням заполняя данные рёбер и полурёбер, вычисляя индексы (подробный алгоритм показан ниже).

Вычисление индексов рёбер и полурёбер

Пусть индексы полурёбер ребра будут ei*2 и ei*2+1, где ei индекс ребра. Тогда зная индекс ребра мы можем узнать индексы его полурёбер, и наоборот, зная один из индексов полурёбер можно узнать индекс ребра и парного полуребра.

Нахождение индексов полурёбер по индексу ребра:

hei1 = ei*2
hei2 = ei*2+1

Найти индекс ребра для обоих полурёбер можно просто разделив их индексы на 2:

ei = hei1 / 2
ei = hei2 / 2

Нахождение парного полуребра:

pair = (hei&1) ? hei-1 : hei+1

Таким образом ссылку на пару в полуребе можно не хранить, т.к. она быстро вычисляется. А также ссылку на ребро из полуребра, и ссылку на полуребро из ребра.

Заполнение граней

Структура полигональной сетки с данными half-edge ограничена возможностью иметь максимум две грани вокруг ребра, таким образом проходя по рёбрам мы можем иметь дело с рёбрами трёх видов: которые ещё не были использованы, которые были использованы один раз, и с рёбрами, которые были использованы два раза. Дважды использованные рёбра можно исключать из расмотрения, т.к. известно, что вокруг них больше не будет граней, требующих обработки. Т.е. нужно хранить только те рёбра, которые были использованы один раз. Если ребра нет в этом списке, то либо оно ещё не создано, либо для него уже создано всё что можно и про него можно забыть. Для экономии памяти для хранения единожды использованных рёбер эффективно использовать двусвязный список, т.к. массив будет потреблять гораздо больше памяти (нужно будет хранить элемент для каждого ребра) и что более страшно, для поиска ребра по вершинам нужно будет просматривать весь массив, а в случае со списком только единожды использованные рёбра храняться в списке, а это число по крайней мере на порядок меньше общего числа рёбер.

Таким образом проходя по вершинам грани мы знаем только индексы текущей и следующей вершин.

vi = i
nvi = ((v_num-1) == i) ? 0 : i + 1

Всё остальное мы можем либо вычислить либо создать.

Проверяем использовалась ли вершина nvi в других гранях. Для этого получаем ссылку на полуребро вершины v_data[nvi].half_edge.

Если индекс корректный, то вершина использовалась и какое-нибудь ребро с этой вершиной уже лежит в списке (или уже удалено) и нам нужно его найти пройдя список и сравнив индексы vi и nvi с индексами начала и конца каждого ребра в списке. Если ничего не найдено создаём новое ребро, заполняем данные для нового ребра и его полурёбер и создаём элемент в списке для нового ребра. Если найдено, то заполняем оставшиеся данные и удаляем ребро из списка.

А если индекс полуребра вершины nvi не корректный, то это значит, что вокруг вершины ещё не было заполнено ни одной грани, и нужно просто создать ребро и элемент списка.

В структуре half-edge грани не хранят прямых ссылок на рёбра, доступ к ним возможен только через полурёбра. Грань должна иметь одну ссылку на любое своё полуребро.

Для каждой грани мы проходим по всем её вершинами заполняя данные ребёр между ними.

Реализация

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

Посмотреть можно тут: moto-mesh.c

Это реализовано в функции moto_mesh_update_he_data, заполнение меша недействительными индексами происходит в функции moto_mesh_new.

Код только что написан и ещё не причёсан. =)

Ограничения

Те же, что и для классической half-edge структуры, в смысле возможных для представления сеток, за исключением висячих рёбер, которые не имеют ни одной прилежашей грани.

P.S.

У меня есть ещё некоторые идеи как можно ускорить этот алгоритм, но они требуют проверки. О прогрессе в этом направлении я напишу.

Для хранения уже задействованных вершин я пробовал использовать матрицу смежности, это конечно на небольших мешах позволяет быстро находить ребро, однако требует памяти как минимум v_num*(v_num+1)/2*sizeof(index_type), что делает новозможным использование этого способа на больших мешах.

Sler AOV

Вот, для тех кто в курсе, что такое Sler. Если это не про вас, смотрите это.

Релизовал я таки в Sler AOV, хотя и не до конца. Получилось хоть и Output Variables, но точно уж не Arbitrary.

Посмотреть чего я натворил и как это использовать можно тут.

Суть такова, что все входы всех блоков не будут использоваться для аргументов генерируемых шейдеров (как это было раньше), если это явно не указать. Что вроде бы логично, т.е. обычно нужно изменять только некоторые атрибуты шейдера. В будущем нужно будет реализовать высокоуровневые команды, типа "Установить все инпуты всех блоков ниже по иерархии для использования в качестве аргументов шейдера". Ну и так далее.

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

И ещё, для инпутов теперь можно задать storage class (см. инфу по RenderMan, например, спеку) и вот как это работает.

Если инпут используется как аргумент, и ни с чем не соеденён, то storage class просто указывается в аргументах шейдера. По умолчанию storage class для всех будет uniform.

Если инпут используется как аргумент и соеденён с чем либо (имеет смысл только если он также объявлен как output), то storage class игнорируется, и в шейдере записывается storage class источника.

Если инпут не используется в качестве аргумента, то и storage class не используется никак, т.к. при генерации подставляется значение инпута, а не имя его переменной. Мало того, переменная не создаётся вообще.

Ну вот и всё вроде.

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

Запечённое освещение

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

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

Сколько времени требуется на рендеринг? Если длительность ролика 3 мин, и кадров в секунду 24, то получается 1440 кадров в минуте или всего 4320 кадра. Допустим время рендеринга одного кадра 3 минуты, тогда на рендеринг всей анимации понадобится 12960 минут, 216 часов или 9 суток.

В принципе это не так уж и много, но этих 3-х минут на кадр нужно ещё достич. Особенно если речь идёт о фотореалистичности.

Эффекты Motion Blur и DoF очень полезны в достижении реализма, кроме того, можно было бы использовать глобальное освещение, но на его расчёт требуется не приемлемое в моём случае количество времени.

К счастью Motion Blur и DoF имеют очень эффективные реализации. Например, RenderMan-совместимый рендерер 3Delight расчитывает эти эффекты очень быстро. Свободные RenderMan-совместимые рендереры Pixie и Aqsis тоже вполне для этого пригоды. Но это только в случае scanline рендеринга, для трассировки лучей эти эффекты довольно медленны.

Поэтому я буду обходить это ограничение. Например, можно в одном кадре запечь освещение в 2D или 3D текстуры и использовать их во всей анимации. Это конечно имеет смысл только для неподвижных объектов, которых однако очень часто большинство в сцене. В моём случае это действительно так.

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

В Blender есть хорошая возможность для запекания результата рендеринга в текстуры. Вот тут:


Как видно можно запечь следующее: все вычисления рендеринга (Full Render), только Ambient Occlusion, нормали или текстуры. При нажатой кнопки Clear запечённые текстуры будут отчищаться перед очередным тестовым рендерингом. Margin влияет на кол-во пикселей, на которые будет расширен результат запекания, это делается для избежания чёрных полос на краях полигонов из-за интерполяции при получении значения из текстуры.

Однако перед запеканием объект должен быть развёрнут. Blender даже имеет специальный режим развёртки для LightMap (U в FaceSelect режиме -> LightMap UVPack), который делает развёртку полностью автоматически, однако далеко не всегда подходящую.

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

Итак, вот тестовая сцена.

Включаю AO (F8->Amb Occ), устанавливаю кол-во сэмплов в 16, т.к. тут больше нужно заботися о разрешении тектсуры для запекания. Для UV кубика делаю картинку с разрешением 256x256, этого пока хватит. Устанавливаю Ambient Occlusion во вкладке Bake и жму соотвествующую кнопку. Повторяю для плоскости.

Перевожу Blender в режим отображения текстур. И вот что имею.


А вот и мой бульдозер с AO в реальном времени (правда ещё не все карты доделаны). Это то, что нужно, т.к. сам бульдозер не будет трансформироваться или деформироваться в процессе анимации. С такого расстояния как показано на картинке, для качественного результата вполне достаточно текстур с разрешением не большим 1024x1024. Максимально 1024 используется для корпуса и кабины. На некоторых мелких деталях можно использовать128 и даже 64.


Теперь я могу без пробем использовать Motion Blur и DoF, не боясь тормозов с трассировкой лучей. Motion Blur имеет смысл разве что для камеры, т.к. объект неподвижный.

Теперь вот нужно придумать чем ещё заполнить сцену, чтобы рендеринг занимал 3 минуты как задумано, а не доли секунды =). Думаю за этим дело не станет.