Трёхмерная графика с нуля. Часть 1: трассировка лучей

[samodum]

Спасибо, отличная статья!
Я почти всегда при изучении нового языка пробую писать трассировщик лучей, т.к. здесь можно обкатать почти все элементы, конструкции языка, в т.ч. и многопоточность.
У меня такой вопрос по CSG (constructive solid geometry). Пусть на приведённой выше картинке шар А у нас синий, а шар B — красный. Если мы вычитаем из шара B шар A, то какой цвет ставить в место этой разницы — синий вычтенного шара A или красный от шара B?
Как будет правильно?

[bask]

Здесь нет однозначно правильного решения. Разработчик сам решает какой цвет указывать.
Вообще, здесь возможны 8 вариантов цветов и для их определения можно ввести флаги, управляющие рендерингом в условиях текущей операции CSG:
Флаги цветов внешней оболочки полученного CSG-объекта (псевдоконстанты):
— RT_EXTERNAL_OBJ_A
— RT_INNER_OBJ_A
— RT_EXTERNAL_OBJ_B
— RT_INNER_OBJ_A
Флаги для внутренней оболочки полученного CSG-объекта (дублируем, то же самое):
— RT_EXTERNAL_OBJ_A
— RT_INNER_OBJ_A
— RT_EXTERNAL_OBJ_B
— RT_INNER_OBJ_A

То есть, мы можем выбрать любой нужный нам в данных условиях цвет.

[neochapay]

Старый добрый хабр! Годнота прям годнетская!

[sshmakov]

В свое время хорошо зашла книга Роджерса "Алгоритмические основы машинной графики". Там же есть переиздание.

[samodum]

Мне по RT больше помогла книга
m.books.ru/books/trekhmernaya-kompyuternaya-grafika-115173

[xGromMx]

Было дело) в универе увлекался всяким таким) в те времена была еще XNA и DirectX

[zabbius]

Спасибо, вспомнил детство, нам такое в школе преподавали, правда писали тогда под дос на чистом С =)

[moooV]

Фигасе у вас детство. У меня были класса с 6 по 11й проводник, пеинт, ворд и эксель, а на программировании надо было тупо набрать с бумажки код в окно турбопаскаля, без пояснений. Школа, правда, гуманитарная была.

Настоящее программирование (Asm, C/C++) было только в универе на первых двух курсах, и это было прикольно.

[shaman4d]

Очень отлично — спасибо! Продолжайте пожалуйста.

[Tarik02]

Заметил, что всё чаще и чаще статьи об графике с использованием трассировки лучей. Будет ли трассировка лучей перспективной в будущем для Realtime графики? Ведь раньше, когда экраны были меньше, сложность отрисовки была меньше: O(wh).

[MTonly]

Быстродействие компьютеров непрерывно повышается и продолжит повышаться, а разрешение в конце концов зафиксируется на предельном разумном уровне, после которого дальнейшее повышение разрешения будет уже нецелесообразно: таким уровнем, скорее всего, станет 8K, хотя и 4K на 24-дюймовом экране уже вполне достаточно. И тогда выбор алгоритма рендеринга будет определяться лишь сложностью сцены.

[JTG]

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

Про диагонали смартфонов тоже так говорили :(

[MTonly]

У смартфонов появилось новое применение — виртуальная реальность, где, в свою очередь, разумный предел — тоже 4K-8K. А ещё есть PenTile, где эффективное разрешение ниже формального.

[samodum]

Как минимум сложность надо умножить на количество объектов и число отражений + преломление.
Есть, правда, хитрости по их уменьшению, но всё же

[haqreu]

Смотря что вы называете трассировкой лучей. Например, в финальной статье моего курса графики, что я публиковал на хабре, я рассказывал, как отрисовывать сферы при помощи шейдеров. По факту, это трассировщик, который даёт заметный прирост в производительности.

[samodum]

У метода трассировки лучей есть давно устоявшееся определение.
Нечего сюда лезть со своими грязными шейдерами!

[haqreu]

Трассировка лучей — технология построения изображения трёхмерных моделей в компьютерных программах, при которых отслеживается обратная траектория распространения луча (от экрана к источнику)

Чем вам не угодили шейдеры?

[samodum]

Определение трассировки лучей вы дали. Теперь дайте определение шейдерам.

[haqreu]

Попробуйте общаться чуть вежливее.

In the field of computer graphics, a shader is a special type of computer program that was originally used to do shading (the production of appropriate levels of light, darkness, and color within an image) but which now perform a variety of specialized functions in various fields of computer graphics special effects or do video post-processing unrelated to shading, and even functions unrelated to graphics at all.

[samodum]

А это вежливо писать по-английски? Какой там перевод? Определения шейдерам я там не увидел.

[samodum]

А вот карму минусовать не стоило. Мог бы по-человечески объяснить, что не так.

[MrShoor]

Программа, исполняема на графическом процессоре. Такое определение подойдет?

[shuhray]

А если так рисовать большие сферы, да ещё полупрозрачные, будет ли это очень долго?

[MrShoor]

Если как в анекдоте «проверить японскую бензопилу», то да, даже такими сферами можно заставить железку тормозить. Если же речь все же идет о реальных задачах, то почти всегда можно найти подход (например битоническая сортировка и front to back блендинг).

[shuhray]

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

[MrShoor]

Рисовать можно любые, хоть большие, хоть маленькие. Но если у вас большие пересекающиеся сферы и они все прозрачные, то появляются другие проблемы (хоть с этим методом, хоть с полигональным). Нужна правильная сортировка + возможно front-to-back блендинг.

[khim]

Зависит от того, как «зайдёт» HBM.

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

Нарастить доступ в память до ширины шины в сотни тысяч бит теоретически возможно, но будет ли это реализовано на практике? Сомнительно…

[DrZlodberg]

Тмотря что понимать под трассировкой. RayMarching по своей сути тоже трассировка. Но в комплекте с SDF там как раз памяти нужно мало, зато дофига вычислений.
Собственно с помощью этой связки делают весьма впечатляющие демки на голых шейдерах.
Примеры почти в реалтайме (на моём не самом свежем железе)

[Torvald3d]

В гпу трассировка лучей работает плохо не потому, что память медленная. В гпу она как раз таки довольно быстрая. Там проблема в том, что в трассировки очень много ветвлений, а т.к. гпу — это SIMD, то с ветвлениями там все очень плохо.

[khim]

Трассировка может быть сделана «поверх» условно-выполняемых инструкций, с ними SIMD довольно неплохо работает. Но в этом случае нужно много обращений в память.

Если же делать «честные» ветвление — то да, это гроб с музыкой, GPU на этом умрёт немедленно.

[Torvald3d]

Трассировка может быть сделана «поверх» условно-выполняемых инструкций

Можно подробнее, это как?

[DrZlodberg]

Сейчас есть демо движки, использующие Path Tracing (вики пишет, что этот метод медленнее RT, но быстрые движки используют именно его). Вроде даже действующий игровой двиг показывали довольно давно и игру обещали(на ютубе видео можно найти, вполне впечатляет).
Квейк 4 в своё время запускали в RT режиме, но там ему требовалось несколько топовых (на тот момент) видях для работы в реальном времени.

[Torvald3d]

Будет ли трассировка лучей перспективной в будущем для Realtime графики?

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

[GigaCore]

Разбиение пространства давно уже производится за считанные миллисекунды прямо на гпу, начиная с lbvh, как крайне высокопараллелизируемого варианта bvh. Чистая трассировка очень хорошо подходит для гпу, проблемы идут в основном на сложных материалах.

[eagleivg]

КМК, учитывая что бюджет кадра для 60 FPS это около 17 милисекунд, несколько милисекунд только на разбиение не так уж и мало.

[GigaCore]

Речь шла про перспективы в будущем, а про миллисекнуды на перестройку всей сцены это репорты из ресерчей ~2011 года hlbvh2 2011

[AgentSmith]

Хабр — торт!

[haqreu]

Спасибо за большую работу, и в частности за перевод формул в латех. Обратите, пожалуйста, внимание, что формулы типа sin в математических текстах набираются прямым шрифтом; размер скобок тоже важен. Сравните:

\alpha2 = arcsin({sin(60) \over 1.33}) = 40.628^\circ


\alpha_2 = \arcsin\left(\frac{\sin(60^\circ)}{1.33}\right) = 40.628^\circ

[PatientZero]

Перевод формул делал не я, а автор статьи. Постараюсь в свободное время исправить.

[alwer]

А как же старый добрый blending
https://www.khronos.org/registry/OpenGL-Refpages/gl4/html/glBlendFunc.xhtml который, по сути, делает все то, что вы описали. Назвать это трассировкой лучей можно с крайне большой оговоркой, так как не учитывается отражение луча и дальнейшее его использование для освещения.

[eagleivg]

У меня такой вопрос, который мучает уже давно: почему не используется комбинированный подход (ray trace + raster) в описании сцены — те же сферы компактнее описывать точкой и радиусом, чем мешем, и наоборот, угловатые объекты проще описать полигонами? Почему нельзя описывать объект комбинацией элементов сфер и полигонов?

Также очень интересует вопрос про NURBS — для решения каких проблем в графике он используется?

[alwer]

NURBS Non-uniform rational B-spline. Нужен для сглаживания моделей и уменьшения количества полигонов для модели без ухудшения качества отображения модели.
На момент OpenGL 3.0 аппаратной реализации не было, все считал CPU. Как сейчас для OpenGL 4.x не нашел информации.

[khim]

Почему нельзя описывать объект комбинацией элементов сфер и полигонов?

Потому что SIMD очень прохо относится к ветвлениям.

[Bookvarenko]

Давным-давно была такая игрушка Extatica. Там из эллипсов всё.

[gt8one]

А может кто-нибудь объяснить чем отличаются:
— Бросания лучей, Рейкастинг (Ray Casting)
— Трассировка лучей (Ray Tracing)
— Трассировка пути (Path Tracing)

[Bookvarenko]

Как раз думал над тем как протащить в 2d движок хотя бы статическое 3d. Спасибо!

[Nesles]

После таких статей, руки тянутся свой движок делать )

[SphinxKingStone]

Отличная статья, хотелось бы ещё почитать про примитивы программирования графики

[MooNDeaR]

Просто божественная статья. Спасибо вам!!!

[shaman4d]

После того как начал следовать статье нашел здесь же habrahabr.ru/post/248153 — еще одно отличное про компьютерную графику на коленке.

[SCINER]

Подскажите пожалуйста, как реализовать вращение камеры курсором в данном примере?
Что за что тут отвечает?
camera_rotation = [
[0.7071, 0, -0.7071],
[ 0, 1, 0],
[0.7071, 0, 0.7071]
];

[haqreu]

.7071 это явно 1/sqrt(2), таким образом, это наверняка матрица вращения вокруг оси Y на 45°.

https://en.wikipedia.org/wiki/Rotation_matrix#In_three_dimensions

[SCINER]

Спасибо! Не ожидал получить ответ так быстро!
Если еще кому интересно, то получается, чтобы реализовать поворот камеры вокруг оси, то вот что надо сделать:

var xd = 45; // угол вращения 0-360
var xr = deg2rad(xd); // переводим угол в радианы

// Вращение по оси Y
camera_rotation = [
    [Math.cos(xr), 0, Math.sin(xr)],
    [     0, 1,       0],
    [-Math.sin(xr), 0,  Math.cos(xr)]
];