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

[[Файл:Recursive_raytrace_of_a_sphere.png|дясно|мини|250x250пкс| Рекурсивно проследяване на лъчите за сфера, демонстриращо ефекти като малка [[дълбочина на рязкост]], площни светлинни източници и [[Отражение|дифузно отражение]].]]

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

== Общо описание на алгоритъма ==
[[Файл:Ray_trace_diagram.svg|дясно|мини|300п| Алгоритъмът изгражда изображението, като изпраща лъчи към сцената.]]
[[Файл:Ray_Tracing_Illustration_First_Bounce.png|дясно|мини|300п| Лъч през конкретен пиксел, проследен до първото отражение.]]

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

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

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

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

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

=== Изчисляване на лъчи за правоъгълен прозорец на изгледа ===
На входа имаме (в изчислението използваме [[Вектор|нормализация]] на вектори и [[векторно произведение]]):

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

[[Файл:RaysViewportSchema.png|708x708пкс|Схема на прозореца на изгледа с пиксели, око E, цел T и център на прозореца C]]

Идеята е да се намери позицията на центъра на всеки пиксел от прозореца на изгледа, <math>P_{ij}</math>, което лесно ще ни позволи да намерим права от окото <math>E</math> през този пиксел и съответно лъч, описан от точката <math>E</math> и вектора <math>\vec R_{ij} = P_{ij} -E</math> (или нормализирания му вариант <math>\vec r_{ij}</math>). Първо трябва да намерим координатите на долния ляв пиксел на прозореца на изгледа, <math>P_{1m}</math>, а след това намираме следващия пиксел, транслирайки в посоки, успоредни на прозореца на изгледа (вектори <math>\vec b_n</math> и <math>\vec v_n</math>) със стъпка размера на пиксела. Долните формули използват разстоянието <math>d</math> между окото и прозореца на изгледа, но тази стойност се съкращава при нормализирането на лъча <math>\vec r_{ij}</math> (поради това можем просто да приемем, че <math>d=1</math> и да го премахнем от изчисленията).

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

: <math>
\vec t = T-E, \qquad \vec b = \vec w\times \vec t
</math>

: <math>
\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
</math>

Отбелязваме, че центърът на изгледа е <math>C=E+\vec t_nd</math>, после изчисляваме размерите му <math>h_x, h_y</math>, разделени на 2, вземайки предвид [[Пропорционалност|пропорцията]] <math>\frac{m}{k}</math>

: <math>
g_x=\frac{h_x}{2} =d \tan \frac{\theta}{2}, \qquad g_y =\frac{h_y}{2} = g_x \frac{m}{k}
</math>

и след това намираме векторите за отместване на следващия пиксел <math>q_x, q_y</math> в посоки (<math>\vec b,\vec v</math>), успоредни на прозореца на изгледа, и центъра на левия долен пиксел <math>p_{1m}</math>

: <math>
\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
</math>

Изчисления: отбелязваме, че <math>P_{ij} = E + \vec p_{ij}</math> и лъчът <math>\vec R_{ij} = P_{ij} -E = \vec p_{ij}</math>, следователно

: <math>
\vec p_{ij} = \vec p_{1m} + \vec q_x(i-1) + \vec q_y(j-1)
</math>
: <math>
\vec r_{ij} = \frac{\vec R_{ij}}{||\vec R_{ij}||} = \frac{\vec p_{ij}}{||\vec p_{ij}||}
</math>

Горната формула е изпробвана в този [https://kamil-kielczewski.github.io/fractals/mandelbulb.html проект на JavaScript] (работи в браузъра).

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

=== Алгоритъм с хвърляне на лъчи (''ray casting'') ===
Първият алгоритъм за проследяване на лъчите, използван за рендиране, е представен от Артър Апел през 1968 г.<ref>Appel A. (1968) ''[http://graphics.stanford.edu/courses/Appel.pdf Some techniques for shading machine renderings of solids]''. AFIPS Conference Proc. 32 pp.37 – 45</ref> Впоследствие този алгоритъм получава името ''ray casting'' („хвърляне на лъчи“). Основната му идея е да се изпрати по един лъч от окото към всеки пиксел и да се намери най-близкият обект на пътя на лъча. Нека си представим, че гледаме изображението през фина мрежа, като всяко квадратче от нея е пиксел. Тогава намереният обект е точно този, който окото вижда през този пиксел. Вземайки предвид свойствата на материала и влиянието на светлинните източници в сцената, алгоритъмът може да определи [[светлосянка]]та в съответната точка от обекта. За простота се предполага, че ако повърхността е обърната към светлинен източник, светлината ще я достигне и няма да бъде закрита или засенчена. Светлосянката се изчислява чрез традиционните модели за осветяване в триизмерната компютърна графика. Важно предимство на хвърлянето на лъчи в сравнение с по-старите алгоритми със сканираща линия е фактът, че се справя лесно с не-равнинни повърхнини и тела като [[конус]]и и [[Сфера|сфери]]. Ако една математическа повърхнина може да бъде пресечена с лъч, тя може да се рендира чрез хвърляне на лъчи. Лесно могат да се рендират и по-сложни обекти, като бъдат пресъздадени с помощта на техники за [[параметрично моделиране]].

=== Рекурсивен алгоритъм за проследяване на лъчи ===
[[Файл:Glasses_800_edit.png|дясно|мини|300x300пкс| С проследяване на лъчи могат да се създават реалистични изображения.]]
[[Файл:BallsRender.png|дясно|мини|300x300пкс| Освен високата степен на реализъм, проследяването на лъчи може да симулира особеностите на фотографските снимки, които се дължат на [[Дълбочина на рязкост|дълбочината на рязкост]] и формата на [[бленда]]та на фотоапарата (в този случай [[шестоъгълник]]).]]
[[Файл:Ray-traced_steel_balls.jpg|дясно|мини|300x300пкс| Броят на разрешените отражения за всеки „лъч“ и начинът, по който му влияят срещнатите повърхности, се контролират чрез софтуерни настройки. Тук за всеки лъч е било разрешено да се отрази до 16 пъти. Така могат да се видят множество „отражения на отраженията“. ''Създадено с [[Cobalt (CAD програма)|cobalt]]'']]
[[Файл:Glass_ochem.png|дясно|мини|300x300пкс| Броят на разрешените [[Пречупване|пречупвания]] за всеки „лъч“ и начинът, по който му влияят срещнатите повърхности, се контролират чрез софтуерни настройки. Тук за всеки лъч е било разрешено да се пречупва и отразява до 9 пъти. Използвани са [[Отражение на Френел|отражения на Френел]]. Също така обърнете внимание на [[каустика]]та. ''Създадено с [[V-Ray|Vray]]'']]

Следващият важен изследователски пробив идва от [[Търнър Уитид]] през 1979 г.<ref>Whitted T. (1979) ''[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.156.1534 An improved illumination model for shaded display]''. Proceedings of the 6th annual conference on Computer graphics and interactive techniques</ref> Предишните алгоритми проследяват лъчи от окото към сцената, докато те не срещнат обект, но определят цвета на лъча, без да проследяват рекурсивно повече лъчи. Уитид продължава процеса. Когато един лъч срещне повърхност, той може да генерира до три нови типа лъчи, за моделиране съответно на отражение, пречупване и сянка.<ref>{{cite journal | url = https://dip.felk.cvut.cz/browse/pdfcache/nikodtom_2010bach.pdf | title = Ray Tracing Algorithm For Interactive Applications | author = Tomas Nikodym | journal = Czech Technical University, FEE | date = юни 2010 | accessdate = 2019-02-10 |archivedate = 2011-07-18 | archive-url = https://web.archive.org/web/20110718171000/https://dip.felk.cvut.cz/browse/pdfcache/nikodtom_2010bach.pdf }}</ref> Лъчът за отражение се проследява в огледално отразена посока. Най-близкият обект, който пресече, е това, което ще се види в отражението. Лъчите за пречупване, които преминават през прозрачен материал, работят по подобен начин, но се добавя пречупен лъч, който може да влиза или излиза от материала. Към всеки светлинен източник се проследява лъч за засенчване. Ако между повърхността и източника има непрозрачен обект, повърхността е в сянка и източникът не я осветява. Това рекурсивно проследяване на лъчите подобрява реалистичността на изображенията.

=== Предимства пред други методи на рендериране ===
Популярността на проследяването на лъчи се дължи на факта, че то се базира на реалистична симулация на [[Осветление в тримерното моделиране|осветление]], за разлика от други методи на рендериране (като сканираща линия и ''ray casting''). Ефекти като отражения и [[Сянка|сенки]], които са трудни за симулиране с други алгоритми, се получават естествено при алгоритъма с проследяване на лъчи. Изчислителната независимост на всеки лъч прави проследяването на лъчи податливо на [[Паралелни изчисления|паралелизация]].<ref>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.</ref><ref>A. Chalmers, T. Davis, and E. Reinhard. Practical parallel rendering, {{ISBN|1-56881-179-9}}. AK Peters, Ltd., 2002.</ref>

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

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

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

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

Докато прякото осветление обикновено се моделира най-добре чрез проследяване на лъчи от окото, за някои непреки ефекти могат да са от полза лъчите, изпратени от светлинните източници. [[Каустика|Каустиките]] са светли шарки, образувани при фокусиране на светлината от обширна огледална област върху тясна част от (почти) дифузно отразяваща повърхност. Това явление би било отразено по-добре от алгоритъм, който хвърля лъчи директно от светлинните източници към отразяващите обекти и проследява техните пътища към окото. Това съчетаване на лъчи, изпращани откъм окото и откъм светлинните източници, често се реализира като двупосочно проследяване на пътища, при което пътищата се проследяват както от окото, така и откъм светлинните източници, и впоследствие се съединяват чрез свързващ лъч след определено разстояние.<ref>{{cite journal | url = http://www.graphics.cornell.edu/~eric/Portugal.html | title = Bi-Directional Path Tracing | author = Eric P. Lafortune and Yves D. Willems | journal = Proceedings of Compugraphics '93 | date = декември 1993 | pages = 145 – 153}}</ref><ref>{{cite web | url = http://www.cescg.org/CESCG98/PDornbach/index.html | title = Implementation of bidirectional ray tracing algorithm | author = Péter Dornbach | accessdate = 11 юни 2008}}</ref>

[[Фотонни карти|Фотонните карти]] са друг метод, който съчетава проследяването на лъчи откъм окото и откъм светлинните източници; при първоначалния етап енергийните фотони се проследяват по лъчи от източника на светлина, за да се изчисли оценката на лъчистия поток като функция на триизмерното пространство (точно това е въпросната фотонна карта). В следващия етап се проследяват лъчи от окото към сцената, за да се определят видимите повърхности, и фотонната карта се използва за оценка на осветяването на видимите точки на повърхността.<ref>[http://graphics.ucsd.edu/~henrik/papers/photon_map/global_illumination_using_photon_maps_egwr96.pdf Global Illumination using Photon Maps] {{webarchive|url=https://web.archive.org/web/20080808140048/http://graphics.ucsd.edu/~henrik/papers/photon_map/global_illumination_using_photon_maps_egwr96.pdf |date=8 август 2008 }}</ref><ref>[http://web.cs.wpi.edu/~emmanuel/courses/cs563/write_ups/zackw/photon_mapping/PhotonMapping.html Photon Mapping – Zack Waters]</ref> Предимството на фотонните карти спрямо двупосочното проследяване на пътища е възможността да се постигне значително повторно използване на фотони, като изчисленията се намаляват на цената на известно статистическо отклонение.

Допълнителен проблем възниква, когато светлината, осветяваща сцената, преминава през много тесен отвор (например в затъмнена стая с леко открехната врата към съседна ярко осветена стая), или при сцена, в която повечето точки нямат пряка видимост към никой светлинен източник (например при насочени към тавана осветителни тела). В такива случаи само много малко подмножество от пътищата ще пренася енергия; методът [[Metropolis light transport]] започва със случайно претърсване на пространството от пътища и когато се открият наситени с енергия пътища, тази информация се използва повторно при изследване на близките области от пространството на лъчите.<ref>[http://graphics.stanford.edu/papers/metro/metro.pdf graphics.stanford.edu]</ref>
[[Файл:PathOfRays.svg|мини]]
Изображението вдясно показва прост пример за път от лъчи от камерата (или окото) към светлинния източник, генериран рекурсивно с горния алгоритъм. Дифузната повърхност отразява светлината във всички посоки.

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

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

Във [[Вектор|векторен запис]] уравнението на сфера с център <math>\mathbf c</math> и радиус <math>r</math> е

: <math>\left\Vert \mathbf x - \mathbf c \right\Vert^2=r^2.</math>

Всяка точка на лъча с начало <math>\mathbf s</math> и посока <math>\mathbf d</math> (където <math>\mathbf d</math> е [[единичен вектор]]) може да се представи като

: <math>\mathbf x=\mathbf s+t\mathbf d,</math>

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

: <math>\left\Vert\mathbf{s}+t\mathbf{d}-\mathbf{c}\right\Vert^{2}=r^2.</math>

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

: <math>\left\Vert\mathbf{v}+t\mathbf{d}\right\Vert^{2}=r^{2}</math>

: <math>\mathbf{v}^2+t^2\mathbf{d}^2+2\mathbf{v}\cdot t\mathbf{d}=r^2</math>

:<math>(\mathbf{d}^2)t^2+(2\mathbf{v}\cdot\mathbf{d})t+(\mathbf{v}^2-r^2)=0.</math>

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

: <math>t^2+(2\mathbf{v}\cdot\mathbf{d})t+(\mathbf{v}^2-r^2)=0.</math>

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

: <math>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)}.</math>

Двете стойности на <math>t</math>, намерени чрез решаване на уравнението, съответстват на точките <math>\mathbf s+t\mathbf d</math>, в които лъчът пресича сферата.

Точките, съответстващи на отрицателни стойности, не лежат на лъча, а в обратната [[Права (геометрия)|полуправа]] (т.е. тази, която започва от <math>\mathbf s</math> в противоположна посока).

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

Да предположим, че има поне едно положително решение и нека <math>t</math> е минималното решение. Освен това, нека предположим, че сферата е най-близкият обект от сцената, пресичащ нашия лъч, и че тя е от огледално отразяващ материал. Трябва да намерим в каква посока се отразява светлинният лъч. Според законите на [[отражение]]то ъгълът на отражение е равен и противоположен на ъгъла на падане между падащия лъч и [[нормала]]та към сферата.

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

: <math>\mathbf n=\frac{\mathbf y- \mathbf c}{\left\Vert\mathbf y- \mathbf c\right\Vert},</math>

където <math>\mathbf y=\mathbf s+t\mathbf d</math> е намерената по-горе пресечна точка. Посоката на отразяване може да се намери чрез [[Отражение (математика)|отражение]] спрямо <math>\mathbf n</math>, тоест

: <math>\mathbf r = \mathbf d - 2(\mathbf n \cdot \mathbf d) \mathbf n.</math>

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

: <math>\mathbf x = \mathbf y + u \mathbf r. \, </math>

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

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

Пример: нека за съвкупност от повърхности имаме ''K<sub>r</sub>'' = 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''<sup>2</sup>, който също би намалил приноса към интензитета.

За пречупен лъч бихме могли да направим нещо подобно, но в такъв случай разстоянието, изминато през обекта, би причинило още по-бързо намаляване на интензивността. Като пример за това, ''Hall & Greenberg'' установяват, че дори за силно отразяваща сцена използването на тази техника с максимална дълбочина 15 води до средна дълбочина само 1,7 на дървото от лъчи.<ref>{{Cite journal|last=Hall|first=Roy A.|last2=Greenberg|first2=Donald P.|date=ноември 1983|title=A Testbed for Realistic Image Synthesis|url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.131.1958|journal=IEEE Computer Graphics and Applications|volume=3|issue=8|pages=10 – 20|doi=10.1109/MCG.1983.263292|via=}}</ref>

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

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

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

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

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

== В реално време ==
Първата реализация на проследяване на лъчи „в реално време“ е [[Суперкомпютър|компютърната графична система LINKS-1]], построена през 1982 г. в инженерната школа към университета в Осака, от професорите Омура Куичи, Ширакава Исао и Кавата Тору заедно с 50 студенти. Това е [[Масово паралелна архитектура|масово паралелно]] обработваща [[компютър]]на система с 514 [[микропроцесор]]а (257 Zilog Z8001 и 257 [[Intel 8086|iAPX 86]]), използвана за рендиране на реалистична [[3D компютърна графика|триизмерна]] [[компютърна графика]] с високоскоростно проследяване на лъчи. Според [[Японска асоциация за обработка на информация|Японската асоциация за обработка на информация]]: „В основата на рендирането на триизмерното изображение стои изчисляването на яркостта на всеки пиксел, представящ рендираната повърхност от дадената гледна точка, [[Осветление в тримерното моделиране|източника на светлина]] и позицията на обекта. Системата LINKS-1 е разработена, за да реализира методология за рендиране на изображения, при която всеки пиксел може да бъде обработен паралелно и независимо чрез проследяване на лъчи. Чрез разработването на нова софтуерна методология специално за високоскоростно рендиране, LINKS-1 бе в състояние да рендира бързо много реалистични изображения.“ Тя е „използвана за създаване на първото в света триизмерно, подобно на [[планетариум]] видео на цялото [[Вселена|небе]], реализирано изцяло с компютърна графика. Видеото е представено в павилиона на [[Фуджицу|Fujitsu]] на Международната изложба през 1985 г. в [[Цукуба]].“<ref>{{cite web |title=【Osaka University 】 LINKS-1 Computer Graphics System |url=http://museum.ipsj.or.jp/en/computer/other/0013.html |work=IPSJ Computer Museum |publisher=[[Information Processing Society of Japan]] |accessdate=15 ноември 2018}}</ref> LINKS-1 е най-мощният компютър в света през 1984 г.<ref>{{cite book |last1=Defanti |first1=Thomas A. |title=Advances in computers. Volume 23 |publisher=[[Academic Press]] |isbn=0-12-012123-9 |page=121 |url=http://www.vasulka.org/archive/Writings/VideogameImpact.pdf#page=29}}</ref>

Като най-ранен документиран случай на проследяване на лъчи „в реално време“ с интерактивно рендиране (т.е. кадрова честота, по-голяма от един кадър в секунда) на конференцията за компютърна графика на SIGGRAPH през 2005 г. са цитирани инструментите REMRT/RT, разработени през 1986 г. от Mike Muuss за системата за параметрично моделиране BRL-CAD. Първоначално публикуван през 1987 г. в USENIX, рейтрейсърът на BRL-CAD е ранна реализация на паралелно разпределена мрежова система за проследяване на лъчи, която постига рендиране с няколко кадъра в секунда.<ref>Виж Proceedings of 4th Computer Graphics Workshop, Cambridge, MA, USA, October 1987. Usenix Association, 1987. pp. 86 – 98.</ref> Тази производителност е постигната с помощта на силно оптимизирания, но независим от платформата модул за проследяване на лъчи LIBRT в BRL-CAD и чрез използване на параметрични геометрични модели на няколко паралелни машини със споделена памет през стандартна компютърна мрежа. Рейтрейсърът на BRL-CAD, включително инструментите REMRT/RT, продължава да бъде достъпен и разработван днес като софтуер с [[Софтуер с отворен код|отворен код]].<ref>{{Цитат уеб|url=http://brlcad.org/d/about|title=About BRL-CAD|accessdate=18 януари 2019|архив_дата=2009-09-01|архив_уеб_адрес=https://web.archive.org/web/20090901222818/http://brlcad.org/d/about}}</ref>

Оттогава насам са вложени значителни усилия и изследвания за реализиране на проследяване на лъчи в реално време за различни цели в самостоятелни настолни компютърни конфигурации. Тези цели включват интерактивни триизмерни графични приложения като [[Демо (програмиране)|графични демонстрации]], [[Видеоигра|компютърни и видео игри]] и рендиране на изображения. Някои софтуерни 3D двигатели в реално време, базирани на трасиране на лъчи, са разработени от [[Демосцена|демо програмистите]] от края на 90-те години.<ref>{{Цитат уеб|url=http://www.acm.org/tog/resources/RTNews/demos/overview.htm|title=The Realtime Raytracing Realm|author=Piero Foscari|work=ACM Transactions on Graphics|accessdate=17 септември 2007}}</ref>

Проектът OpenRT включва силно оптимизирано софтуерно ядро за проследяване на лъчи, заедно с интерфейс за приложно програмиране, подобен на [[OpenGL]], за да предложи алтернатива на сегашния, базиран на [[растеризация]] подход за интерактивна триизмерна графика. Създаден е специализиран хардуер, като експерименталния Ray Processing Unit, разработен в [[Университет на Саарланд|университета на Саарланд]], който ускорява някои от интензивните изчислителни операции при проследяване на лъчи. На 16 март 2007 г. Университетът на Саарланд представя реализация на високопроизводителна машина за проследяване на лъчи, която позволява рендиране на компютърни игри чрез проследяване на лъчи без интензивно използване на ресурси.<ref>{{Cite news|url=http://news.bbc.co.uk/1/hi/technology/6457951.stm|title=Rays light up life-like graphics|author=Mark Ward|publisher=BBC News|date=16 март 2007|accessdate=17 септември 2007}}</ref>

На 12 юни 2008 г. Intel демонстрира специална версия на ''Enemy Territory: Quake Wars'', озаглавена ''Quake Wars: Ray Traced'', която използва проследяване на лъчи за рендиране и работи в разделителна способност HD (720p). ETQW работи с 14 – 29 кадъра в секунда. Демонстрацията е проведена на 16-ядрена (4 гнезда, 4 ядра) система Xeon Tigerton, работеща на 2,93 GHz.<ref>{{Цитат уеб|url=http://www.tgdaily.com/html_tmp/content-view-37925-113.html|title=Intel converts ET: Quake Wars to ray tracing|author=Theo Valich|publisher=TG Daily|date=12 юни 2008|accessdate=16 юни 2008|архив_дата=2009-12-12|архив_уеб_адрес=https://web.archive.org/web/20091212050521/http://www.tgdaily.com/html_tmp/content-view-37925-113.html}}</ref>

На конференцията SIGGRAPH 2009 Nvidia обявява OptiX – безплатен приложно-програмен интерфейс за проследяване на лъчи в реално време чрез графичните процесори на Nvidia. Той предоставя седем програмируеми входни точки към конвейера за проследяване на лъчи, позволявайки персонализирани камери, пресичания на лъчи с примитиви, шейдъри, сенки и др. Тази гъвкавост дава възможност за двупосочно проследяване на пътища, ''Metropolis light transport'' и много други алгоритми за рендиране, които не могат да бъдат реализирани с [[Рекурсия|опашкова рекурсия]].<ref>{{Цитат уеб|url=http://www.nvidia.com/object/optix.html|title=Nvidia OptiX|author=Nvidia|publisher=Nvidia|date=18 октомври 2009|accessdate=6 ноември 2009}}</ref> От април 2013 г. Nvidia е доставила над 350 000 000 графични процесора с поддръжка на OptiX. Базирани на OptiX модули за рендиране се използват в [[Adobe Systems|Adobe]] [[Adobe After Effects|AfterEffects]], Bunkspeed Shot, [[Autodesk Maya]], [[Autodesk 3ds Max|3ds max]] и много други.

AMD предлага реалновремево проследяване на лъчи в графичните карти Vega чрез GPUOpen Radeon ProRender.<ref>[https://gpuopen.com/announcing-real-time-ray-tracing/ GPUOpen Real-time Ray-tracing]</ref> Nvidia предоставя същата възможност чрез графичните карти Quadro RTX. Серията видеокарти Nvidia [[GeForce 20]] поддържа проследяване на лъчи в реално време.

Imagination Technologies предлага безплатен [[приложно-програмен интерфейс]], наречен OpenRL, който ускорява алгоритмите за рендиране, базирани на [[Рекурсия|опашкова рекурсия]] и заедно със специализиран фирмен хардуер работи с [[Autodesk Maya]], предоставяйки възможност, която списание 3D World определя като „реалновремево проследяване на лъчи за редовите художници“.<ref>{{Цитат уеб|url=http://www.3dworldmag.com/2013/04/16/hardware-review-caustic-series2-r2500-ray-tracing-accelerator-card/|title=3DWorld: Hardware review: Caustic Series2 R2500 ray-tracing accelerator card|accessdate=23 април 2013}}3D World, април 2013</ref>

През 2014 г. демонстрация на видеоиграта за [[PlayStation 4]] ''The Tommorow Children'', разработена от Q-Games и SIE Japan Studio, демонстрира нови техники за [[Компютърна графика|осветление]], разработени от Q-Games, в частност каскадно [[воксел]]но проследяване на конуси, което симулира осветление в реално време и използва по-реалистични отражения, а не такива в екранното пространство.<ref name="ps10">{{Цитат уеб|url=http://blog.eu.playstation.com/2014/10/24/creating-striking-unusual-visuals-tomorrow-children-ps4-2/|title=Creating the beautiful, ground-breaking visuals of The Tomorrow Children on PS4|first=Dylan|last=Cuthbert|work=[[PlayStation Blog]]|date=24 октомври 2015|accessdate=7 декември 2015}}</ref>

За предстоящата игра ''MechWarrior 5: Mercenaries'' е обявено, че използва проследяване на лъчи. За съответната възможност се признава, че затруднява дори най-мощните графични карти през 2018 г.<ref>[https://wccftech.com/mechwarrior-5-mercenaries-dev-nvidia-rtx-dlss/ MechWarrior 5: Mercenaries Developer on NVIDIA RTX and NVIDIA DLSS: We’ll Get the Greatest Benefit from Doing Both]</ref>

== Изчислителна сложност ==
За определени формулировки на задачата за проследяване на лъчи са получени различни резултати по отношение на изчислителната сложност. В частност, ако формулираме задачата като проверка<ref>''[https://www.cs.duke.edu/~reif/paper/tygar/raytracing.pdf Computability and Complexity of Ray Tracing]''.</ref> дали при дадено начало и посока на светлинния лъч и някаква фиксирана точка лъчът в крайна сметка достига тази точка, цитираната статия доказва следните резултати:

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

== Източници ==
<references />

== Външни препратки ==
* [http://www.few.vu.nl/~kielmann/theses/avdploeg.pdf Interactive Ray Tracing: The replacement of rasterization?] {{Webarchive|url=https://web.archive.org/web/20110609192149/http://www.few.vu.nl/~kielmann/theses/avdploeg.pdf |date=2011-06-09 }}
* [https://www.youtube.com/watch?v=WV4qXzM641o The Compleat Angler (1978)]
* [http://www.scratchapixel.com/lessons/3d-basic-rendering/introduction-to-ray-tracing Writing a Simple Ray Tracer (scratchapixel)] {{Webarchive|url=https://web.archive.org/web/20150228122303/http://scratchapixel.com/lessons/3d-basic-rendering/introduction-to-ray-tracing |date=2015-02-28 }}
* [https://marcin-chwedczuk.github.io/ray-tracing-torus Ray tracing a torus]

{{Превод от|en|Ray tracing (graphics)|882464778}}

[[Категория:3D компютърна графика]]
[[Категория:Компютърна графика]]
[[Категория:Виртуална реалност]]
[[Категория:Геометрична оптика]]