Первый контакт с c ++. Первый контакт с компьютерной графикой (CG).
Забавно, но у каждого проекта есть свои сложности, но он никогда не преподносится так, как должен. Даже потому, что основное внимание в презентации уделяется конечным результатам (конечно).
Итак, цель этого поста - не показать техники и коды [вы можете проверить здесь], а вместо этого передать некоторый контекст проекта, процесс разработки, последние секунды страданий и счастья (я хочу сохранить этот текст форматный подход).
Для любителей кода ~ https://github.com/arthurflor23/ray-tracing.
В 2015 году я был на выпускном и знал только языки программирования Pascal и C. Я даже не знал о Github.
Ну, в классе компьютерной графики был новый учитель с другим подходом. Ничего из проектов, использующих Blender. Да, в том году пришло время разработать нашу собственную трассировку лучей.
Но ... какого хрена трассировка лучей !?
Формально Википедия [здесь] говорит:
Трассировка лучей - это метод рендеринга для создания изображения путем отслеживания пути света в виде пикселей в плоскости изображения и моделирования эффектов его встреч с виртуальными объектами. .
Я бы сказал, что это что-то сложное, требующее много математики, обработки ЦП, больше математики, структуры данных и большого терпения, чтобы завершить простой проект, в котором синий шар будет помещен в центр изображения.
Первым вызовом, на самом деле, было изучение объектно-ориентированного программирования и C ++ (вау!). Итак, наше приключение начинается. Первой задачей, которую мы выполнили, было прочитать файл конфигурации с координатами объектов в трехмерном пространстве (начиная с простого круга) и поместить его в центр изображения (a) размером 800x600.
Следующие задачи, которые усложнялись, заключались в добавлении источников света (b), теней (c) и треугольников (d). Позади этого добавлена дополнительная математика и для каждой точки света, пиксель за пикселем:
- Проверить, не попадает ли свет в круг (математика);
- Проверить, не попадает ли свет в треугольник (математика);
- Проверить, распространяется ли тень на другие объекты (больше математики);
- Огни не погасли? повторить петлю с другим светом.
Обработка ЦП также значительно увеличилась. Если сценарий изначально занимал менее 5 секунд (a), в конце этого времени это заняло около 1 минуты (d). Помните, что в коде еще нет структуры данных, и в сцене всего 5 объектов с 2 точками света.
Теперь мы можем продолжать и грустить, когда скрипт загружает объектный файл коровы с 8708 объектами в сцене (300x150) и занимает около 45 минут, чтобы вставить изображение.
Становится печальнее, когда сценарий загружает объектный файл дракона с 30 181 объектом в сцене (1100x300) и занимает около 7 часов, чтобы вставить изображение.
И становится еще печальнее, когда скрипт загружает объектный файл Бэтмена с 41792 объектами в сцене (600x800) и занимает около 12 часов, чтобы вставить изображение.
Было действительно неприятно запускать скрипт ночью и только на следующий день, чтобы проверить, правильное ли изображение на выходе или нет.
Структура данных KD-Tree
Итак, последней задачей в проекте было структурировать весь код с помощью KD-Tree. И человеку было действительно сложно понять концепцию и поставить все объекты в соответствии с логикой.
По сути, объекты были распределены в двоичном дереве, в котором каждый узел представляет собой разделение положения на оси времени (чередование осей x, y и z) до тех пор, пока не достигнет листьев (с условием остановки) .
Упомянутый выше попиксельный процесс был значительно сокращен, потому что вместо проверки столкновения света на всех объектах код теперь будет проходить KD-Tree (руководствуясь положением проверяемого пикселя) и возвращать 10 объектов. с листа (я не могу вспомнить, было ли условие остановки на самом деле с 10 объектами, но все равно).
Затем мы перешли от теста тысяч объектов на пиксель к 10.
Процесс, который занял 12 часов, теперь занимает максимум 10 минут. Остальное вы уже знаете.
В итоге, конечно, какие-то результаты
Наконец, спасибо, кто начал читать этот пост, и особенно, кто попал сюда ~ ха-ха.
Эти проекты представляют собой личное обучение, которое я разработал в последние годы и считаю их интересными. К сожалению, в конце цикла разработки о них забывают в Github.
Так что я намерен создать привычку размещать их здесь нетехническим и непринужденным образом. Увидимся в следующем посте.
использованная литература
- Эми Уильямс, Стив Баррус, Р. Кейт Морли и Питер Ширли (2005) Эффективный и надежный алгоритм пересечения лучевых боксов, Journal of Graphics Tools, 10: 1,49–54, DOI: 10.1080 / 2151237X.2005.10129188
- И. Вальд и В. Хавран, «О создании быстрых KD-деревьев для трассировки лучей и о выполнении этого за O (N log N)», Симпозиум IEEE 2006 г. по интерактивной трассировке лучей, Солт-Лейк-Сити. , UT, 2006, стр. 61–69.
doi: 10.1109 / RT.2006.280216 - Хапала М. и Хавран В. (2011), Обзор: Алгоритмы обхода Kd-дерева для трассировки лучей. Форум компьютерной графики, 30: 199–213. DOI: 10.1111 / j.1467–8659.2010.01844.x
- Уолд И., Перселл Т.Дж., Шмитлер Дж., Бентин К. и Слусаллек П. (2004). Трассировка лучей в реальном времени и ее использование для интерактивного глобального освещения.
