Хм, а это мысль!
Попробую реализовать: после первого прохода цикла рендеринга — запускать второй, который будет искать границы, и запускать уточняющие лучи.
Кстати, у меня была идея написать механизм, который позволял бы распределять на разные компьютеры рендеринг разных кадров (или частей изображения). Хотел написать для этого прослойку на Эрланге. Но, пока что это так и осталось в планах)
Я пробовал увеличить количество лучей (несколько лучей на пиксель) — но это приводило к замедлению рендеринга.
Наверное, целесообразно увеличивать количество лучей только в тех участках изображения, где наблюдаются границы объектов.
Но в данном случае нужно каким-нибудь эффективным образом детектить границы объектов.
В общем, так это и осталось в мыслях )
Честно говоря, особо не интересовался.
Видео красивое, подозреваю что там используется какой-нибудь алгоритм глобального освещения.
Я бы с удовольствием занялся реализацией данной фичи :-) но, чувствую что в одиночку это будет довольно долго…
Спасибо за идею. Тоже думал над этим — должно получится довольно красиво.
При аккуратной реализации можно будет даже смоделировать опыт Ньютона по разложению белого света, при прохождении сквозь призму :-)
Я тоже думал об ускорении построения дерева. У меня сейчас используется довольно прямолинейный алгоритм:
1) Допустим, что мы рассекаем сцену плоскостью XY
2) Значит, нужно найти соответствующую координату разбиения по оси Z
3) У нас есть крайние точки сцены: Zmin и Zmax
4) Zdist = Zmax — Zmin
5) dZ = Zdist / MAX_SPLITS_OF_VOXEL
6)
for(z = Zmin; z < Zmax; z += dZ) {
Внутри цикла - разбиваем сцену на 2 части
считаем количество полигонов попавших в разные части сцены
считаем площадь каждой части
считаем SAH
}
Шаг 6 можно оптимизировать — для каждой новой итерации не нужно пересчитывать заново какие полигоны куда попали. Но, к сожалению, руки ещё до этого не дошли
1. Относительно того, когда прекращать построение дерева:
Допустим, мы пытаемся разбить сцену на две части.
Начальная площадь поверхности сцены = S_0 и содержит она N_0 полигонов
Допустим — площадь левой части S_L, и содержит она N_L полигонов
Площадь правой части S_R, и содержит она N_R полигонов
если (delta_SAH < 0) — значит разбиение проводит целесообразно
5) ещё, «на всякий случай», я контролирую максимальную глубину дерева (у меня есть константа MAX_TREE_DEPTH)
2. «Дробление» примитива
Если примитив попадает и в «левую» и в «правую» половину — значит считаем его и там и там увеличиваем значение N_L и N_R)
3. Я читал про различные структуры данных для ускорения рендеринга, но kd-дерево для меня показалось наиболее понятным и гибким (хотя, возможно я ошибаюсь)
Bump mapping можно добавить в текущую архитектуру без особых проблем — по сути это просто отдельная текстура, которая используется для отклонения вектора нормали (а текстуры уже реализованы).
В плане глобального освещения — мне нравится photon mapping. Для реализации данной технологии можно переиспользовать уже написанное kd-дерево (используется для быстрого поиска фотонов). Хотя, в последнее время всё больше обращаю внимание на path tracing.
Много чего хочется реализовать, но т.к. это pet project — иногда просто не хватает времени…
Спасибо.
Планирую перенести на CUDA (пока что нахожусь на этапе изучения данной технологии).
Насколько я понял, придётся отказаться от указателей на функции (а ведь на этом сейчас базируется архитектура рендера).
...Internally, node.js relies on libev to provide the event loop, which is supplemented by libeio which uses pooled threads to provide asynchronous I/O...
Внутренний механизм ноды полагается на пул POSIX потоков, для того чтобы эмулировать асинхронный I/O. Соответственно не совсем корректно утверждать что
1 thread может обрабатывать сотни запросов
Конечно, для node.js программиста высокоуровневая абстракция выглядит имеено таким образом. Но есть ли у вас возможность конфигурировать подлежащий пул потоков (например изменять количество потоков)? (если вопрос выглядит слишком по дилетантски — заранее прошу извинения, т.к. с node.js на практике не работал).
В этом плане решения на основе Java выглядят привлекательней, т.к. во всех серверных технологиях (будь то jetty, tomcat или даже комплексные application сервера, типа jboss) — есть возможность конфигурировать пул потоков, запускать потоки-демоны для фоновых задач и т.п. Относительно механизма реализации потоков в Java — можно сказать что он зависит от виртуальной машины, и в случае *nix — это могут быть те же pthreads.
Если разбивать пространство на ячейки одинакового размера, это значит, что в случае, если большинство объектов сцены попадут в одну ячейку — то, соответственно, будут иметь одинаковый хэш, что опять возвращает нас к квадратической сложности поиска ближайших соседей.
Если же выбрать ячейки очень маленького размера (для того чтобы уменьшить количество попаданий объектов в одну ячейку) — то столкнёмся с тем, что объекты большого размера, будут занимают много ячеек — в данном случае вычислительные ресурсы будут тратится на вычисление большого количества хэшей для одного объекта (а если больших объектов будет много?).
Таким образом, можно сделать вывод, что данная техника наиболее эффективна в тех случаях, когда все объекты сцены примерно одинакового размера, и распределены равномерно в пространстве.
В качестве дополнения, приведу ещё ссылку на K-d дерево, которое, также, можно использовать для поиска ближайших соседей.
Но при использовании деревьев, возникает несколько проблем:
как построить оптимальное дерево для данного расположения объектов в пространстве? (как вариант, в случае ray-tracing рендеринга, можно использовать Surface area heuristic)
и, соответственно — ресурсоёмкость процедуры построения и модификации (в случае очень динамичных сцен — речь идёт о полной перестройке дерева)
Таким образом, использование техники хэширования (и удачно подобранной хэш функции) позволяет обойти вышеперечисленные ограничения деревьев.
Интересная статья :-)
В качестве дополнения, могу предложить собственную статью на данную тему: habrahabr.ru/post/163195/
Относительно параллелизма, идея хорошая. Хотя, иногда, для быстрого нахождения оптимального решения достаточно просто удачно подобрать параметры мутации и скрещивания (в случае генетического алгоритма). Однажды я реализовывал генетический алгоритм с обратной связью — в котором отслеживалась динамика схождения, и когда схождение замедлялось, то алгоритм либо останавливался, либо некоторым образом подстраивал свои параметры.
Спасибо за интересную статью.
Возможно дополнением к теме, будет этот пост: habrahabr.ru/post/171759/ где я рассказывал о применении энтропии в машинном обучении. А также, ещё один вариант вывода формулы энтропии Шеннона :-)
Если честно, немного удивительно, что Вы используете модель мешка слов, ведь она не учитывает порядок слов.
На самом деле, реализация алгоритма шинглов использует тот же коэффициент Жаккара. Только в данном случае, вместо слов, оперируют шинглами (на практике — хэшами шинглов, но это уже детали...).
Попросту говоря, шинглы — это кортежи из нескольких слов, построенные следующим образом (рисунок схематический): Чисто иллюстративный пример:
слон ест красное яблоко
яблоко ест красного слона
(у некоторых слов разные окончания, но будем считать, что в качестве предварительной обработки мы используем лемматизатор).
Если использовать модель мешка слов, то получится, что эти два предложения дубликаты, поскольку содержат идентичные наборы слов.
Что на это скажет алгоритм шинглов:
Если использовать в качестве шинглов — кортежы слов, взятых через одно, получим:
слон ест красное яблоко -> A = {слон, красный} и {ест, яблоко}
яблоко ест красного слона -> B = {яблоко, красный} и {ест, слон}
Множества А и В не содержат одинаковых кортежей. Поэтому, пересечение A и B, даст пустое множество. Таким образом, можно заключить что данные тексты не дубликаты.
Ещё раз обращаю внимание — пример чисто иллюстративный, но, надеюсь, что общую концепцию мне удалось проиллюстрировать :-)
P.S. На самом деле, именно характер данных, их объём и другие особенности предметной области диктуют алгоритм обработки. Так что, если в Вашем случае описанный алгоритм работает хорошо, то, действительно, не стоит усложнять систему.
В данном комментарии, я просто хотел показать, что в общем случае Алгоритм шинглов более эффективный для идентификации дубликатов.
Попробую реализовать: после первого прохода цикла рендеринга — запускать второй, который будет искать границы, и запускать уточняющие лучи.
Для текстур, кстати, неплохие результаты даёт билинейная фильтрация.
Наверное, целесообразно увеличивать количество лучей только в тех участках изображения, где наблюдаются границы объектов.
Но в данном случае нужно каким-нибудь эффективным образом детектить границы объектов.
В общем, так это и осталось в мыслях )
Видео красивое, подозреваю что там используется какой-нибудь алгоритм глобального освещения.
Я бы с удовольствием занялся реализацией данной фичи :-) но, чувствую что в одиночку это будет довольно долго…
При аккуратной реализации можно будет даже смоделировать опыт Ньютона по разложению белого света, при прохождении сквозь призму :-)
Я тоже думал об ускорении построения дерева. У меня сейчас используется довольно прямолинейный алгоритм:
1) Допустим, что мы рассекаем сцену плоскостью XY
2) Значит, нужно найти соответствующую координату разбиения по оси Z
3) У нас есть крайние точки сцены: Zmin и Zmax
4) Zdist = Zmax — Zmin
5) dZ = Zdist / MAX_SPLITS_OF_VOXEL
6)
Шаг 6 можно оптимизировать — для каждой новой итерации не нужно пересчитывать заново какие полигоны куда попали. Но, к сожалению, руки ещё до этого не дошли
Я ещё черпал полезную информацию из этой книги: Max K. Agoston, Computer Graphics and Geometric Modeling (вдруг кому пригодится)
Здесь, начиная со строки 267, функция для поиска наилучшего разбиения. Там реализация того что я описал (немножко оптимизированная).
Допустим, мы пытаемся разбить сцену на две части.
Начальная площадь поверхности сцены = S_0 и содержит она N_0 полигонов
Допустим — площадь левой части S_L, и содержит она N_L полигонов
Площадь правой части S_R, и содержит она N_R полигонов
Тогда делаем следующее:
1) нормируем площади:
S_0_norm = S_0 / S_0 = 1
S_L_norm = S_L / S_0
S_R_norm = S_R / S_0
2) рассчитываем SAH
SAH_0 = S_0_norm * N_0
SAH_L = S_L_norm * N_L
SAH_R = S_R_norm * N_R
3) введём «штраф» за разбиение (просто константа, которую я подобрал эмпирически) — SPLIT_PENALTY
4) рассчитаем целесообразность разбиения:
delta_SAH = (SAH_L + SAH_R + SPLIT_PENALTY) — SAH_0
если (delta_SAH < 0) — значит разбиение проводит целесообразно
5) ещё, «на всякий случай», я контролирую максимальную глубину дерева (у меня есть константа MAX_TREE_DEPTH)
2. «Дробление» примитива
Если примитив попадает и в «левую» и в «правую» половину — значит считаем его и там и там увеличиваем значение N_L и N_R)
3. Я читал про различные структуры данных для ускорения рендеринга, но kd-дерево для меня показалось наиболее понятным и гибким (хотя, возможно я ошибаюсь)
В плане глобального освещения — мне нравится photon mapping. Для реализации данной технологии можно переиспользовать уже написанное kd-дерево (используется для быстрого поиска фотонов). Хотя, в последнее время всё больше обращаю внимание на path tracing.
Много чего хочется реализовать, но т.к. это pet project — иногда просто не хватает времени…
Планирую перенести на CUDA (пока что нахожусь на этапе изучения данной технологии).
Насколько я понял, придётся отказаться от указателей на функции (а ведь на этом сейчас базируется архитектура рендера).
Хочу обратить внимание на один нюанс из сабжа:
Внутренний механизм ноды полагается на пул POSIX потоков, для того чтобы эмулировать асинхронный I/O. Соответственно не совсем корректно утверждать что
Конечно, для node.js программиста высокоуровневая абстракция выглядит имеено таким образом. Но есть ли у вас возможность конфигурировать подлежащий пул потоков (например изменять количество потоков)? (если вопрос выглядит слишком по дилетантски — заранее прошу извинения, т.к. с node.js на практике не работал).
В этом плане решения на основе Java выглядят привлекательней, т.к. во всех серверных технологиях (будь то jetty, tomcat или даже комплексные application сервера, типа jboss) — есть возможность конфигурировать пул потоков, запускать потоки-демоны для фоновых задач и т.п. Относительно механизма реализации потоков в Java — можно сказать что он зависит от виртуальной машины, и в случае *nix — это могут быть те же pthreads.
Хочу уточнить несколько нюансов.
Если разбивать пространство на ячейки одинакового размера, это значит, что в случае, если большинство объектов сцены попадут в одну ячейку — то, соответственно, будут иметь одинаковый хэш, что опять возвращает нас к квадратической сложности поиска ближайших соседей.
Если же выбрать ячейки очень маленького размера (для того чтобы уменьшить количество попаданий объектов в одну ячейку) — то столкнёмся с тем, что объекты большого размера, будут занимают много ячеек — в данном случае вычислительные ресурсы будут тратится на вычисление большого количества хэшей для одного объекта (а если больших объектов будет много?).
Таким образом, можно сделать вывод, что данная техника наиболее эффективна в тех случаях, когда все объекты сцены примерно одинакового размера, и распределены равномерно в пространстве.
Но при использовании деревьев, возникает несколько проблем:
Таким образом, использование техники хэширования (и удачно подобранной хэш функции) позволяет обойти вышеперечисленные ограничения деревьев.
В качестве дополнения, могу предложить собственную статью на данную тему: habrahabr.ru/post/163195/
Относительно параллелизма, идея хорошая. Хотя, иногда, для быстрого нахождения оптимального решения достаточно просто удачно подобрать параметры мутации и скрещивания (в случае генетического алгоритма). Однажды я реализовывал генетический алгоритм с обратной связью — в котором отслеживалась динамика схождения, и когда схождение замедлялось, то алгоритм либо останавливался, либо некоторым образом подстраивал свои параметры.
Возможно дополнением к теме, будет этот пост: habrahabr.ru/post/171759/ где я рассказывал о применении энтропии в машинном обучении. А также, ещё один вариант вывода формулы энтропии Шеннона :-)
На самом деле, реализация алгоритма шинглов использует тот же коэффициент Жаккара. Только в данном случае, вместо слов, оперируют шинглами (на практике — хэшами шинглов, но это уже детали...).
Попросту говоря, шинглы — это кортежи из нескольких слов, построенные следующим образом (рисунок схематический):
Чисто иллюстративный пример:
(у некоторых слов разные окончания, но будем считать, что в качестве предварительной обработки мы используем лемматизатор).
Если использовать модель мешка слов, то получится, что эти два предложения дубликаты, поскольку содержат идентичные наборы слов.
Что на это скажет алгоритм шинглов:
Если использовать в качестве шинглов — кортежы слов, взятых через одно, получим:
Множества А и В не содержат одинаковых кортежей. Поэтому, пересечение A и B, даст пустое множество. Таким образом, можно заключить что данные тексты не дубликаты.
Ещё раз обращаю внимание — пример чисто иллюстративный, но, надеюсь, что общую концепцию мне удалось проиллюстрировать :-)
P.S. На самом деле, именно характер данных, их объём и другие особенности предметной области диктуют алгоритм обработки. Так что, если в Вашем случае описанный алгоритм работает хорошо, то, действительно, не стоит усложнять систему.
В данном комментарии, я просто хотел показать, что в общем случае Алгоритм шинглов более эффективный для идентификации дубликатов.