Проследяване на лъчи (компютърна графика)

Рекурсивно проследяване на лъчите за сфера, демонстриращо ефекти като малка дълбочина на рязкост, площни светлинни източници и дифузно отражение.

В компютърната графика проследяването на лъчи е техника за рендиране, при която за да се генерира изображение, се проследява пътят на светлината през пикселите от равнината на изображението и се симулират последствията от взаимодействията ѝ с виртуални обекти. С тази техника може да се постигне много висока степен на визуален реализъм, обикновено по-висока от тази на типичните методи със сканираща линия, но с по-високи изчислителни разходи. Затова проследяването на лъчи е най-подходящо за приложения, в които относително бавното рендиране на всеки кадър е приемливо – например за неподвижни изображения и за визуални ефекти в киното и телевизията, – и по-неподходящо за приложения в реално време като видео игрите, където скоростта е от решаващо значение. Проследяването на лъчите е в състояние да симулира голямо разнообразие от оптични ефекти, като отражение и пречупване, разсейване и дисперсионни явления (например хроматична аберация).

Общо описание на алгоритъма

Алгоритъмът изгражда изображението, като изпраща лъчи към сцената.

Лъч през конкретен пиксел, проследен до първото отражение.

Оптичното проследяване на лъчи е метод за получаване на изображения в триизмерната компютърна графика, който осигурява по-висок фотореализъм от техники като ray casting или сканираща линия. То работи чрез проследяване пътя на светлината от въображаемо око през всеки пиксел от виртуален екран и изчисляване на цвета на обекта, който се вижда през него.

Проследяването на лъчи изисква математическо описание на сцената, което се подготвя от програмист или художник (обикновено чрез специализиран софтуер). Сцените могат да включват и данни от изображения и модели, заснети с помощта на цифрова фотография и подобни средства.

Обикновено всеки лъч се проверява за пресичане с някакво подмножество от обектите в сцената. След като бъде открит най-близкият обект, алгоритъмът оценява падащата светлина в точката на пресичане, взема предвид свойствата на материала на обекта и въз основа на тази информация изчислява окончателния цвят на пиксела. Някои алгоритми за осветяване и отразяващи или полупрозрачни материали изискват проследяване на допълнителни лъчи в сцената.

На пръв поглед може да изглежда нелогично да се изпращат лъчи „назад“, т.е. навън от камерата, а не към нея (както се движи светлината в действителност), но това е с много порядъци по-ефективно. Тъй като огромното мнозинство от светлинните лъчи от даден източник не достигат пряко до очите на наблюдателя, симулацията в посока „напред“ може да доведе до огромно количество излишни изчисления за лъчи, които никога няма да бъдат регистрирани от окото.

Затова, за да се спестят изчисления, при проследяването на лъчи поначало се предполага, че даденият лъч пресича видимия кадър. След като лъчът претърпи максимален брой отражения или измине определено разстояние без пресичане, проследяването му приключва и се актуализира стойността на пиксела.

Изчисляване на лъчи за правоъгълен прозорец на изгледа

На входа имаме (в изчислението използваме нормализация на вектори и векторно произведение):

• ${\displaystyle E\in \mathbb {R^{3}} }$ позиция на окото
• ${\displaystyle T\in \mathbb {R^{3}} }$ позиция на целта
• ${\displaystyle \theta \in [0,\pi )}$ зрително поле – за човек можем да приемем ${\displaystyle \approx \pi /2{\text{ rad}}=90^{\circ }}$
• ${\displaystyle m,k\in \mathbb {N} }$ брой квадратни пиксели в прозореца на изгледа във вертикална и хоризонтална посока
• ${\displaystyle i,j\in \mathbb {N} ,1\leq i\leq k\land 1\leq j\leq m}$ индекси на конкретен пиксел
• ${\displaystyle {\vec {w}}\in \mathbb {R^{3}} }$ вертикален вектор, определящ посоките нагоре и надолу, обикновено ${\displaystyle {\vec {w}}=[0,1,0]}$ (не е показан на илюстрацията)

Идеята е да се намери позицията на центъра на всеки пиксел от прозореца на изгледа, ${\displaystyle P_{ij}}$, което лесно ще ни позволи да намерим права от окото ${\displaystyle E}$ през този пиксел и съответно лъч, описан от точката ${\displaystyle E}$ и вектора ${\displaystyle {\vec {R}}_{ij}=P_{ij}-E}$ (или нормализирания му вариант ${\displaystyle {\vec {r}}_{ij}}$). Първо трябва да намерим координатите на долния ляв пиксел на прозореца на изгледа, ${\displaystyle P_{1m}}$, а след това намираме следващия пиксел, транслирайки в посоки, успоредни на прозореца на изгледа (вектори ${\displaystyle {\vec {b}}_{n}}$ и ${\displaystyle {\vec {v}}_{n}}$) със стъпка размера на пиксела. Долните формули използват разстоянието ${\displaystyle d}$ между окото и прозореца на изгледа, но тази стойност се съкращава при нормализирането на лъча ${\displaystyle {\vec {r}}_{ij}}$ (поради това можем просто да приемем, че ${\displaystyle d=1}$ и да го премахнем от изчисленията).

Предварителни изчисления: намираме и нормализираме вектора ${\displaystyle {\vec {t}}}$ и векторите ${\displaystyle {\vec {b}},{\vec {v}}}$, които са успоредни на изгледа (и трите са показани на горната илюстрация).

${\displaystyle {\vec {t}}=T-E,\qquad {\vec {b}}={\vec {w}}\times {\vec {t}}}$

${\displaystyle {\vec {t}}_{n}={\frac {\vec {t}}{||{\vec {t}}||}},\qquad {\vec {b}}_{n}={\frac {\vec {b}}{||{\vec {b}}||}},\qquad {\vec {v}}_{n}={\vec {t}}_{n}\times {\vec {b}}_{n}}$

Отбелязваме, че центърът на изгледа е ${\displaystyle C=E+{\vec {t}}_{n}d}$, после изчисляваме размерите му ${\displaystyle h_{x},h_{y}}$, разделени на 2, вземайки предвид пропорцията ${\displaystyle {\frac {m}{k}}}$

${\displaystyle g_{x}={\frac {h_{x}}{2}}=d\tan {\frac {\theta }{2}},\qquad g_{y}={\frac {h_{y}}{2}}=g_{x}{\frac {m}{k}}}$

и след това намираме векторите за отместване на следващия пиксел ${\displaystyle q_{x},q_{y}}$ в посоки (${\displaystyle {\vec {b}},{\vec {v}}}$), успоредни на прозореца на изгледа, и центъра на левия долен пиксел ${\displaystyle p_{1m}}$

${\displaystyle {\vec {q}}_{x}={\frac {2g_{x}}{k-1}}{\vec {b}}_{n},\qquad {\vec {q}}_{y}={\frac {2g_{y}}{m-1}}{\vec {v}}_{n},\qquad {\vec {p}}_{1m}={\vec {t}}_{n}d-g_{x}{\vec {b}}_{n}-g_{y}{\vec {v}}_{n}}$

Изчисления: отбелязваме, че ${\displaystyle P_{ij}=E+{\vec {p}}_{ij}}$ и лъчът ${\displaystyle {\vec {R}}_{ij}=P_{ij}-E={\vec {p}}_{ij}}$, следователно

${\displaystyle {\vec {p}}_{ij}={\vec {p}}_{1m}+{\vec {q}}_{x}(i-1)+{\vec {q}}_{y}(j-1)}$

${\displaystyle {\vec {r}}_{ij}={\frac {{\vec {R}}_{ij}}{||{\vec {R}}_{ij}||}}={\frac {{\vec {p}}_{ij}}{||{\vec {p}}_{ij}||}}}$

Горната формула е изпробвана в този проект на JavaScript (работи в браузъра).

Подробно описание на компютърния алгоритъм за проследяване на лъчи и неговия произход

Какво се случва в природата (опростено)

В природата даден светлинен източник изпуска лъч светлина, който рано или късно стига до повърхност, която прекъсва движението му. Можем да си представяме този „лъч“ като поток от фотони, които се движат по един и същ път. В съвършен вакуум лъчът ще бъде права линия (ако пренебрегнем релативистичните ефекти). С него може да се случи произволна комбинация от следните четири явления: поглъщане, отражение, пречупване и флуоресценция. Повърхността може да абсорбира част от светлинния лъч, намалявайки интензивността на отразената и/или пречупената светлина. Тя може също така да отрази целия лъч или част от него в една или повече посоки. Ако повърхността е прозрачна или полупрозрачна, тя пречупва през себе си част от светлинния лъч в различна посока, като същевременно поглъща в част от спектъра или целия спектър (и евентуално променя цвета). Понякога повърхността може да погълне част от светлината и да я излъчи отново чрез флуоресценция, с по-голяма дължина на вълната и в произволна посока, макар че това е достатъчно рядко, че може да се пренебрегне в повечето приложения за рендиране. Сумата от погълнатата, отразената, пречупената и излъчената чрез флуоресценция светлина трябва да отговаря на цялата първоначална падаща светлина и не повече. Една повърхност не може, например, да отразява 66% от входящия светлинен лъч и да пречупва 50%, тъй като сумата от двете би била 116%. Впоследствие, отразените и/или пречупените лъчи могат да срещнат други повърхности, чиито абсорбционни, рефракционни, отразяващи и флуоресцентни свойства отново повлияват върху движението им. Някои от тези лъчи се движат по такъв начин, че стигат до очите ни, позволявайки ни да видим сцената, като по този начин допринасят за окончателното изображение.

Алгоритъм с хвърляне на лъчи (ray casting)

Първият алгоритъм за проследяване на лъчите, използван за рендиране, е представен от Артър Апел през 1968 г.^[1] Впоследствие този алгоритъм получава името ray casting („хвърляне на лъчи“). Основната му идея е да се изпрати по един лъч от окото към всеки пиксел и да се намери най-близкият обект на пътя на лъча. Нека си представим, че гледаме изображението през фина мрежа, като всяко квадратче от нея е пиксел. Тогава намереният обект е точно този, който окото вижда през този пиксел. Вземайки предвид свойствата на материала и влиянието на светлинните източници в сцената, алгоритъмът може да определи светлосянката в съответната точка от обекта. За простота се предполага, че ако повърхността е обърната към светлинен източник, светлината ще я достигне и няма да бъде закрита или засенчена. Светлосянката се изчислява чрез традиционните модели за осветяване в триизмерната компютърна графика. Важно предимство на хвърлянето на лъчи в сравнение с по-старите алгоритми със сканираща линия е фактът, че се справя лесно с не-равнинни повърхнини и тела като конуси и сфери. Ако една математическа повърхнина може да бъде пресечена с лъч, тя може да се рендира чрез хвърляне на лъчи. Лесно могат да се рендират и по-сложни обекти, като бъдат пресъздадени с помощта на техники за параметрично моделиране.

Рекурсивен алгоритъм за проследяване на лъчи

С проследяване на лъчи могат да се създават реалистични изображения.

Освен високата степен на реализъм, проследяването на лъчи може да симулира особеностите на фотографските снимки, които се дължат на дълбочината на рязкост и формата на блендата на фотоапарата (в този случай шестоъгълник).

Броят на разрешените отражения за всеки „лъч“ и начинът, по който му влияят срещнатите повърхности, се контролират чрез софтуерни настройки. Тук за всеки лъч е било разрешено да се отрази до 16 пъти. Така могат да се видят множество „отражения на отраженията“. Създадено с cobalt

Броят на разрешените пречупвания за всеки „лъч“ и начинът, по който му влияят срещнатите повърхности, се контролират чрез софтуерни настройки. Тук за всеки лъч е било разрешено да се пречупва и отразява до 9 пъти. Използвани са отражения на Френел. Също така обърнете внимание на каустиката. Създадено с Vray

Следващият важен изследователски пробив идва от Търнър Уитид през 1979 г.^[2] Предишните алгоритми проследяват лъчи от окото към сцената, докато те не срещнат обект, но определят цвета на лъча, без да проследяват рекурсивно повече лъчи. Уитид продължава процеса. Когато един лъч срещне повърхност, той може да генерира до три нови типа лъчи, за моделиране съответно на отражение, пречупване и сянка.^[3] Лъчът за отражение се проследява в огледално отразена посока. Най-близкият обект, който пресече, е това, което ще се види в отражението. Лъчите за пречупване, които преминават през прозрачен материал, работят по подобен начин, но се добавя пречупен лъч, който може да влиза или излиза от материала. Към всеки светлинен източник се проследява лъч за засенчване. Ако между повърхността и източника има непрозрачен обект, повърхността е в сянка и източникът не я осветява. Това рекурсивно проследяване на лъчите подобрява реалистичността на изображенията.

Предимства пред други методи на рендериране

Популярността на проследяването на лъчи се дължи на факта, че то се базира на реалистична симулация на осветление, за разлика от други методи на рендериране (като сканираща линия и ray casting). Ефекти като отражения и сенки, които са трудни за симулиране с други алгоритми, се получават естествено при алгоритъма с проследяване на лъчи. Изчислителната независимост на всеки лъч прави проследяването на лъчи податливо на паралелизация.^[4][5]

Недостатъци

Сериозен недостатък на проследяването на лъчи е ниското бързодействие (макар че на теория може да бъде по-бързо от традиционната сканираща линия в зависимост от сложността на сцената спрямо броя на пикселите на екрана). Алгоритмите със сканираща линия и други алгоритми използват кохерентността на данните, за да споделят изчисленията между пикселите, докато проследяването на лъчи обикновено започва процеса наново, обработвайки всеки лъч от окото поотделно. Това разделяне обаче предлага други предимства, например възможността да се изпращат повече лъчи при нужда, за да се извърши пространствено изглаждане на назъбванията и да се подобри качеството на изображението, където е необходимо.

Въпреки че моделира точно взаимни отражения и оптични ефекти като пречупване, традиционното проследяване на лъчи не е задължително фотореалистично. Истински фотореализъм се получава, когато е налице уравнението на рендирането е много добре апроксимирано или реализирано напълно. Пълната реализация на уравнението на рендирането дава истински фотореализъм, тъй като уравнението описва всички физични явления, свързани със светлинния поток. Това обаче обикновено е невъзможно, като се имат предвид необходимите изчислителни ресурси.

Реализмът на всеки метод за рендиране може да бъде оценен като приближение към уравнението. Проследяването на лъчите, ако е ограничено до алгоритъма на Уитид, не е непременно най-реалистичното. Методите, които проследяват лъчи, но включват и допълнителни техники (фотонни карти, проследяване на пътища), дават далеч по-точна симулация на реалното осветление.

Обърната посока на обхождане на сцената от лъчите

Създаването на изображение чрез изпращане на лъчи от окото към светлинния източник понякога се нарича обратно проследяване на лъчи, тъй като фотоните в действителност се движат в обратна посока. Тази терминология обаче е свързана с обърквания. Отначало проследяването на лъчи винаги се е извършвало от окото, а ранните изследователи като Джеймс Арво разбират под термина „обратно проследяване на лъчи“ изпращане на лъчи откъм светлинните източници и събиране на резултатите. Затова е по-ясно проследяването на лъчи да се дели на проследяване откъм окото или откъм светлинния източник.

Докато прякото осветление обикновено се моделира най-добре чрез проследяване на лъчи от окото, за някои непреки ефекти могат да са от полза лъчите, изпратени от светлинните източници. Каустиките са светли шарки, образувани при фокусиране на светлината от обширна огледална област върху тясна част от (почти) дифузно отразяваща повърхност. Това явление би било отразено по-добре от алгоритъм, който хвърля лъчи директно от светлинните източници към отразяващите обекти и проследява техните пътища към окото. Това съчетаване на лъчи, изпращани откъм окото и откъм светлинните източници, често се реализира като двупосочно проследяване на пътища, при което пътищата се проследяват както от окото, така и откъм светлинните източници, и впоследствие се съединяват чрез свързващ лъч след определено разстояние.^[6][7]

Фотонните карти са друг метод, който съчетава проследяването на лъчи откъм окото и откъм светлинните източници; при първоначалния етап енергийните фотони се проследяват по лъчи от източника на светлина, за да се изчисли оценката на лъчистия поток като функция на триизмерното пространство (точно това е въпросната фотонна карта). В следващия етап се проследяват лъчи от окото към сцената, за да се определят видимите повърхности, и фотонната карта се използва за оценка на осветяването на видимите точки на повърхността.^[8][9] Предимството на фотонните карти спрямо двупосочното проследяване на пътища е възможността да се постигне значително повторно използване на фотони, като изчисленията се намаляват на цената на известно статистическо отклонение.

Допълнителен проблем възниква, когато светлината, осветяваща сцената, преминава през много тесен отвор (например в затъмнена стая с леко открехната врата към съседна ярко осветена стая), или при сцена, в която повечето точки нямат пряка видимост към никой светлинен източник (например при насочени към тавана осветителни тела). В такива случаи само много малко подмножество от пътищата ще пренася енергия; методът Metropolis light transport започва със случайно претърсване на пространството от пътища и когато се открият наситени с енергия пътища, тази информация се използва повторно при изследване на близките области от пространството на лъчите.^[10]

Изображението вдясно показва прост пример за път от лъчи от камерата (или окото) към светлинния източник, генериран рекурсивно с горния алгоритъм. Дифузната повърхност отразява светлината във всички посоки.

Първият лъч тръгва от окото, минава през даден пиксел и продължава към сцената, където среща дифузно отразяваща повърхност. От тази повърхност алгоритъмът рекурсивно генерира отразен лъч, който се проследява през сцената, където среща друга дифузна повърхност. Накрая се генерира и проследява трети отразен лъч през сцената, който стига до светлинния източник и се абсорбира. Цветът на пиксела сега зависи от цветовете на първата и втората дифузно отразяваща повърхност и цвета на светлината, излъчвана от източника. Например, ако източникът излъчва бяла светлина, а двете дифузни повърхности са сини, тогава полученият цвят на пиксела е син.

Пример

Като демонстрация на принципите, използвани при проследяване на лъчи, да разгледаме как можем да намерим пресечната точка между лъч и сфера. Това включва само изчисленията за пресичане на права със сфера и последващото определяне на цвета на изчислявания пиксел. Разбира се, общият процес на проследяване на лъчи е много по-сложен, но това е пример за използваните алгоритми.

Във векторен запис уравнението на сфера с център ${\displaystyle \mathbf {c} }$ и радиус ${\displaystyle r}$ е

${\displaystyle \left\Vert \mathbf {x} -\mathbf {c} \right\Vert ^{2}=r^{2}.}$

Всяка точка на лъча с начало ${\displaystyle \mathbf {s} }$ и посока ${\displaystyle \mathbf {d} }$ (където ${\displaystyle \mathbf {d} }$ е единичен вектор) може да се представи като

${\displaystyle \mathbf {x} =\mathbf {s} +t\mathbf {d} ,}$

където ${\displaystyle t}$ е разстоянието между ${\displaystyle \mathbf {x} }$ и ${\displaystyle \mathbf {s} }$. В нашата задача са известни ${\displaystyle \mathbf {c} }$, ${\displaystyle r}$, ${\displaystyle \mathbf {s} }$ (например позицията на светлинен източник) и ${\displaystyle \mathbf {d} }$ и трябва да намерим ${\displaystyle t}$. Затова заместваме ${\displaystyle \mathbf {x} }$:

${\displaystyle \left\Vert \mathbf {s} +t\mathbf {d} -\mathbf {c} \right\Vert ^{2}=r^{2}.}$

Нека за простота ${\displaystyle \mathbf {v} \ {\stackrel {\mathrm {def} }{=}}\ \mathbf {s} -\mathbf {c} }$; тогава

${\displaystyle \left\Vert \mathbf {v} +t\mathbf {d} \right\Vert ^{2}=r^{2}}$

${\displaystyle \mathbf {v} ^{2}+t^{2}\mathbf {d} ^{2}+2\mathbf {v} \cdot t\mathbf {d} =r^{2}}$

${\displaystyle (\mathbf {d} ^{2})t^{2}+(2\mathbf {v} \cdot \mathbf {d} )t+(\mathbf {v} ^{2}-r^{2})=0.}$

Фактът, че d е единичен вектор, ни позволява следното малко опростяване:

${\displaystyle t^{2}+(2\mathbf {v} \cdot \mathbf {d} )t+(\mathbf {v} ^{2}-r^{2})=0.}$

Това квадратно уравнение има решения

${\displaystyle t={\frac {-(2\mathbf {v} \cdot \mathbf {d} )\pm {\sqrt {(2\mathbf {v} \cdot \mathbf {d} )^{2}-4(\mathbf {v} ^{2}-r^{2})}}}{2}}=-(\mathbf {v} \cdot \mathbf {d} )\pm {\sqrt {(\mathbf {v} \cdot \mathbf {d} )^{2}-(\mathbf {v} ^{2}-r^{2})}}.}$

Двете стойности на ${\displaystyle t}$, намерени чрез решаване на уравнението, съответстват на точките ${\displaystyle \mathbf {s} +t\mathbf {d} }$, в които лъчът пресича сферата.

Точките, съответстващи на отрицателни стойности, не лежат на лъча, а в обратната полуправа (т.е. тази, която започва от ${\displaystyle \mathbf {s} }$ в противоположна посока).

Ако числото под квадратния корен (дискриминантата) е отрицателно, то лъчът не пресича сферата.

Да предположим, че има поне едно положително решение и нека ${\displaystyle t}$ е минималното решение. Освен това, нека предположим, че сферата е най-близкият обект от сцената, пресичащ нашия лъч, и че тя е от огледално отразяващ материал. Трябва да намерим в каква посока се отразява светлинният лъч. Според законите на отражението ъгълът на отражение е равен и противоположен на ъгъла на падане между падащия лъч и нормалата към сферата.

Нормалата към сферата е просто

${\displaystyle \mathbf {n} ={\frac {\mathbf {y} -\mathbf {c} }{\left\Vert \mathbf {y} -\mathbf {c} \right\Vert }},}$

където ${\displaystyle \mathbf {y} =\mathbf {s} +t\mathbf {d} }$ е намерената по-горе пресечна точка. Посоката на отразяване може да се намери чрез отражение спрямо ${\displaystyle \mathbf {n} }$, тоест

${\displaystyle \mathbf {r} =\mathbf {d} -2(\mathbf {n} \cdot \mathbf {d} )\mathbf {n} .}$

Следователно уравнението на отразения лъч е

${\displaystyle \mathbf {x} =\mathbf {y} +u\mathbf {r} .\,}$

Сега остава само да изчислим пресечната точка на последния лъч с нашето зрително поле, за да получим пиксела, през който минава отразеният светлинен лъч. Накрая, на този пиксел се присвоява подходящ цвят, като се има предвид как отражението комбинира цвета на оригиналния светлинен източник с цвета на сферата.

Адаптивно управление на дълбочината

Това означава, че спираме да генерираме отразени и пречупени лъчи, когато изчисленият интензитет стане по-малък от определен праг. Винаги трябва да се задава конкретна максимална дълбочина, иначе програмата ще генерира безкраен брой лъчи. Но ако повърхностите не са силно отразяващи, не винаги е необходимо тази максимална дълбочина да бъде достигната. За да проверява за това, при проследяване на лъчите програмата трябва да изчислява и съхранява произведението на глобалните коефициенти и коефициентите на отражение.

Пример: нека за съвкупност от повърхности имаме K_r = 0,5. Тогава максималният принос на първата повърхност е 0,5; за отражението от втората имаме: 0,5 . 0,5 = 0,25, за третата: 0,25 . 0,5 = 0,125, за четвъртата: 0,125 . 0,5 = 0,0625, за петата: 0,0625 . 0,5 = 0,03125 и т.н. Освен това можем да приложим коефициент на затихване с разстоянието, например 1/d², който също би намалил приноса към интензитета.

За пречупен лъч бихме могли да направим нещо подобно, но в такъв случай разстоянието, изминато през обекта, би причинило още по-бързо намаляване на интензивността. Като пример за това, Hall & Greenberg установяват, че дори за силно отразяваща сцена използването на тази техника с максимална дълбочина 15 води до средна дълбочина само 1,7 на дървото от лъчи.^[11]

Обхващащи обеми

Обектите се ограждат със съвкупности от йерархични обхващащи обеми и първо се проверява за пресичане с обхващащия обем и само ако има такова – с оградените от него обекти.

Обхващащите обеми трябва да позволяват лесна проверка за пресичане; такива са например сферата и правоъгълният паралелепипед. Видът на най-подходящия обем зависи от формата на съдържащия се в него обект или обекти. Например, ако обектите са дълги и тънки, сферата би обхванала предимно празно пространство и паралелепипедът е много по-подходящ. С паралелепипеди също така е по-лесно да се съставят йерархични обхващащи обеми.

Трябва да отбележим, че използването на такава йерархична система (ако е реализирана внимателно) променя времето за изчисляване на пресичанията от линейно спрямо броя на обектите към нещо между линейно и логаритмично. Това е така, защото в идеалния случай всяка проверка за пресичане би разделяла възможностите на две и бихме имали структура от типа двоично дърво. Това е и целта на разглежданите по-долу методи за подразделяне на пространството.

Kay & Kajiya дават списък с желани свойства за йерархични обхващащи обеми:

• Поддърветата трябва да съдържат обекти, които са близо един до друг, и колкото повече наближаваме листата, толкова по-близки трябва да са обектите.
• Обемът на всеки възел трябва да бъде минимален.
• Сумата от обемите на всички обхващащи обеми трябва да бъде минимална.
• По-голямо внимание трябва да се обръща на възлите близо до корена, тъй като изключването на клон близо до корена ще отстрани повече потенциални обекти, отколкото на такъв, който е по-близо до листата.
• Времето, необходимо за изграждането на йерархията, трябва да бъде много по-малко от времето, спестено от него.

В реално време

Първата реализация на проследяване на лъчи „в реално време“ е компютърната графична система LINKS-1, построена през 1982 г. в инженерната школа към университета в Осака, от професорите Омура Куичи, Ширакава Исао и Кавата Тору заедно с 50 студенти. Това е масово паралелно обработваща компютърна система с 514 микропроцесора (257 Zilog Z8001 и 257 iAPX 86), използвана за рендиране на реалистична триизмерна компютърна графика с високоскоростно проследяване на лъчи. Според Японската асоциация за обработка на информация: „В основата на рендирането на триизмерното изображение стои изчисляването на яркостта на всеки пиксел, представящ рендираната повърхност от дадената гледна точка, източника на светлина и позицията на обекта. Системата LINKS-1 е разработена, за да реализира методология за рендиране на изображения, при която всеки пиксел може да бъде обработен паралелно и независимо чрез проследяване на лъчи. Чрез разработването на нова софтуерна методология специално за високоскоростно рендиране, LINKS-1 бе в състояние да рендира бързо много реалистични изображения.“ Тя е „използвана за създаване на първото в света триизмерно, подобно на планетариум видео на цялото небе, реализирано изцяло с компютърна графика. Видеото е представено в павилиона на Fujitsu на Международната изложба през 1985 г. в Цукуба.“^[12] LINKS-1 е най-мощният компютър в света през 1984 г.^[13]

Като най-ранен документиран случай на проследяване на лъчи „в реално време“ с интерактивно рендиране (т.е. кадрова честота, по-голяма от един кадър в секунда) на конференцията за компютърна графика на SIGGRAPH през 2005 г. са цитирани инструментите REMRT/RT, разработени през 1986 г. от Mike Muuss за системата за параметрично моделиране BRL-CAD. Първоначално публикуван през 1987 г. в USENIX, рейтрейсърът на BRL-CAD е ранна реализация на паралелно разпределена мрежова система за проследяване на лъчи, която постига рендиране с няколко кадъра в секунда.^[14] Тази производителност е постигната с помощта на силно оптимизирания, но независим от платформата модул за проследяване на лъчи LIBRT в BRL-CAD и чрез използване на параметрични геометрични модели на няколко паралелни машини със споделена памет през стандартна компютърна мрежа. Рейтрейсърът на BRL-CAD, включително инструментите REMRT/RT, продължава да бъде достъпен и разработван днес като софтуер с отворен код.^[15]

Оттогава насам са вложени значителни усилия и изследвания за реализиране на проследяване на лъчи в реално време за различни цели в самостоятелни настолни компютърни конфигурации. Тези цели включват интерактивни триизмерни графични приложения като графични демонстрации, компютърни и видео игри и рендиране на изображения. Някои софтуерни 3D двигатели в реално време, базирани на трасиране на лъчи, са разработени от демо програмистите от края на 90-те години.^[16]

Проектът OpenRT включва силно оптимизирано софтуерно ядро за проследяване на лъчи, заедно с интерфейс за приложно програмиране, подобен на OpenGL, за да предложи алтернатива на сегашния, базиран на растеризация подход за интерактивна триизмерна графика. Създаден е специализиран хардуер, като експерименталния Ray Processing Unit, разработен в университета на Саарланд, който ускорява някои от интензивните изчислителни операции при проследяване на лъчи. На 16 март 2007 г. Университетът на Саарланд представя реализация на високопроизводителна машина за проследяване на лъчи, която позволява рендиране на компютърни игри чрез проследяване на лъчи без интензивно използване на ресурси.^[17]

На 12 юни 2008 г. Intel демонстрира специална версия на Enemy Territory: Quake Wars, озаглавена Quake Wars: Ray Traced, която използва проследяване на лъчи за рендиране и работи в разделителна способност HD (720p). ETQW работи с 14 – 29 кадъра в секунда. Демонстрацията е проведена на 16-ядрена (4 гнезда, 4 ядра) система Xeon Tigerton, работеща на 2,93 GHz.^[18]

На конференцията SIGGRAPH 2009 Nvidia обявява OptiX – безплатен приложно-програмен интерфейс за проследяване на лъчи в реално време чрез графичните процесори на Nvidia. Той предоставя седем програмируеми входни точки към конвейера за проследяване на лъчи, позволявайки персонализирани камери, пресичания на лъчи с примитиви, шейдъри, сенки и др. Тази гъвкавост дава възможност за двупосочно проследяване на пътища, Metropolis light transport и много други алгоритми за рендиране, които не могат да бъдат реализирани с опашкова рекурсия.^[19] От април 2013 г. Nvidia е доставила над 350 000 000 графични процесора с поддръжка на OptiX. Базирани на OptiX модули за рендиране се използват в Adobe AfterEffects, Bunkspeed Shot, Autodesk Maya, 3ds max и много други.

AMD предлага реалновремево проследяване на лъчи в графичните карти Vega чрез GPUOpen Radeon ProRender.^[20] Nvidia предоставя същата възможност чрез графичните карти Quadro RTX. Серията видеокарти Nvidia GeForce 20 поддържа проследяване на лъчи в реално време.

Imagination Technologies предлага безплатен приложно-програмен интерфейс, наречен OpenRL, който ускорява алгоритмите за рендиране, базирани на опашкова рекурсия и заедно със специализиран фирмен хардуер работи с Autodesk Maya, предоставяйки възможност, която списание 3D World определя като „реалновремево проследяване на лъчи за редовите художници“.^[21]

През 2014 г. демонстрация на видеоиграта за PlayStation 4 The Tommorow Children, разработена от Q-Games и SIE Japan Studio, демонстрира нови техники за осветление, разработени от Q-Games, в частност каскадно вокселно проследяване на конуси, което симулира осветление в реално време и използва по-реалистични отражения, а не такива в екранното пространство.^[22]

За предстоящата игра MechWarrior 5: Mercenaries е обявено, че използва проследяване на лъчи. За съответната възможност се признава, че затруднява дори най-мощните графични карти през 2018 г.^[23]

Изчислителна сложност

За определени формулировки на задачата за проследяване на лъчи са получени различни резултати по отношение на изчислителната сложност. В частност, ако формулираме задачата като проверка^[24] дали при дадено начало и посока на светлинния лъч и някаква фиксирана точка лъчът в крайна сметка достига тази точка, цитираната статия доказва следните резултати:

• Проследяването на лъчи в триизмерни оптични системи с крайно множество от отразяващи или пречупващи обекти, представени чрез система на рационални квадратични неравенства, е неразрешимо.
• Проследяването на лъчи в триизмерни оптични системи с крайно множество от пречупващи обекти, представени чрез система на рационални линейни неравенства, е неразрешимо.
• Проследяването на лъчи в триизмерни оптични системи с крайно множество от правоъгълни отразяващи или пречупващи обекти е неразрешимо.
• Проследяването на лъчи в триизмерни оптични системи с крайно множество от отразяващи или частично отразяващи обекти, представени чрез система от линейни неравенства, някои от които могат да бъдат ирационални, е неразрешимо.
• Проследяването на лъчи в триизмерни оптични системи с крайно множество от отразяващи или частично отразяващи обекти, представени чрез система от рационални линейни неравенства, е PSPACE-трудно.
• За всяко измерение, равно на или по-голямо от 2, проследяването на лъчи с крайно множество от успоредни и перпендикулярни отразяващи повърхности, представени с рационални линейни неравенства, е в класа PSPACE.

Източници

1. Appel A. (1968) Some techniques for shading machine renderings of solids. AFIPS Conference Proc. 32 pp.37 – 45
2. Whitted T. (1979) An improved illumination model for shaded display. Proceedings of the 6th annual conference on Computer graphics and interactive techniques
3. Tomas Nikodym. Ray Tracing Algorithm For Interactive Applications // Czech Technical University, FEE. юни 2010. Архивиран от оригинала на 2011-07-18. Посетен на 2019-02-10.
4. J.-C. Nebel. A New Parallel Algorithm Provided by a Computation Time Model, Eurographics Workshop on Parallel Graphics and Visualisation, 24 – 25 септември 1998, Rennes, France.
5. A. Chalmers, T. Davis, and E. Reinhard. Practical parallel rendering, ISBN 1-56881-179-9. AK Peters, Ltd., 2002.
6. Eric P. Lafortune and Yves D. Willems. Bi-Directional Path Tracing // Proceedings of Compugraphics '93. декември 1993. с. 145 – 153.
7. Péter Dornbach. Implementation of bidirectional ray tracing algorithm // Посетен на 11 юни 2008.
8. Global Illumination using Photon Maps Архив на оригинала от 2008-08-08 в Wayback Machine.
9. Photon Mapping – Zack Waters
10. graphics.stanford.edu
11. Hall, Roy A. и др. A Testbed for Realistic Image Synthesis // IEEE Computer Graphics and Applications 3 (8). ноември 1983. DOI:10.1109/MCG.1983.263292. с. 10 – 20.
12. 【Osaka University 】 LINKS-1 Computer Graphics System // IPSJ Computer Museum. Information Processing Society of Japan. Посетен на 15 ноември 2018.
13. Defanti, Thomas A. Advances in computers. Volume 23. Academic Press. ISBN 0-12-012123-9. с. 121.
14. Виж Proceedings of 4th Computer Graphics Workshop, Cambridge, MA, USA, October 1987. Usenix Association, 1987. pp. 86 – 98.
15. About BRL-CAD // Архивиран от оригинала на 2009-09-01. Посетен на 18 януари 2019.
16. Piero Foscari. The Realtime Raytracing Realm // ACM Transactions on Graphics. Посетен на 17 септември 2007.
17. Mark Ward. Rays light up life-like graphics // BBC News, 16 март 2007. Посетен на 17 септември 2007.
18. Theo Valich. Intel converts ET: Quake Wars to ray tracing // TG Daily, 12 юни 2008. Архивиран от оригинала на 2009-12-12. Посетен на 16 юни 2008.
19. Nvidia. Nvidia OptiX // Nvidia, 18 октомври 2009. Посетен на 6 ноември 2009.
20. GPUOpen Real-time Ray-tracing
21. 3DWorld: Hardware review: Caustic Series2 R2500 ray-tracing accelerator card // Посетен на 23 април 2013.3D World, април 2013
22. Cuthbert, Dylan. Creating the beautiful, ground-breaking visuals of The Tomorrow Children on PS4 // PlayStation Blog. 24 октомври 2015. Посетен на 7 декември 2015.
23. MechWarrior 5: Mercenaries Developer on NVIDIA RTX and NVIDIA DLSS: We’ll Get the Greatest Benefit from Doing Both
24. Computability and Complexity of Ray Tracing.

Външни препратки

• Interactive Ray Tracing: The replacement of rasterization? Архив на оригинала от 2011-06-09 в Wayback Machine.
• The Compleat Angler (1978)
• Writing a Simple Ray Tracer (scratchapixel) Архив на оригинала от 2015-02-28 в Wayback Machine.
• Ray tracing a torus

Тази страница частично или изцяло представлява превод на страницата Ray tracing (graphics) в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс – Признание – Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година – от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите. ​ ВАЖНО: Този шаблон се отнася единствено до авторските права върху съдържанието на статията. Добавянето му не отменя изискването да се посочват конкретни източници на твърденията, които да бъдат благонадеждни.​