Ray casting

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

Не слід плутати з Трасування променів (анг. ray tracing).

Проста ілюстрація Кидання променів

Ray casting, рейкастинг або Кидання променів  —  використання методу перетину променів з поверхнею для вирішення різних завдань в комп'ютерній графіці та обчислювальній геометрії. Цей термін вперше був використаний в комп'ютерній графіці в роботі Скотта Рота 1982 року, щоб описати спосіб перетворення моделей конструктивної блокової геометрії. [1] Кидання променів може стосуватися різних завдань та методів:

  • Загальне завдання визначення першого об’єкта, який перетинається променем [2]

Незважаючи на те, що "кидання променів" та "трасування променів" в ранній комп'ютерній графічній літературі часто використовувалися як тотожні [4] — останнім часом намагаються їх відрізняти. [5] Різниця полягає в тому, що кидання променів — це алгоритм рендеринга, при якому рекурсивно ніколи не відстежуються вторинні промені, тоді як інші алгоритми візуалізації на основі трасування променів можуть це зробити.

Концепція[ред. | ред. код]

Кидання променів є найбільш простим з багатьох алгоритмів рендеринга комп'ютерної графіки, які засновані на геометричному алгоритмі трасування променів. Алгоритми рендеринга на базі трасування променів працюють в image order[en] для відтворення тривимірних сцен на двовимірний екран. Геометричні промені надходять з ока спостерігача для зразка світла (сяйва), що рухається до спостерігача від напрямку променю. Швидкість і простота кидання променів забезпечується обчисленням кольору світла без рекурсивного відстеження додаткових променів, які відбивають сяйва, що падають на ту точку, в яку потрапляє промінь. Це виключає можливість точного рендерингу відбиття, заломлення або природного падіння тіней; Однак усі ці елементи можуть бути певною мірою підроблені, шляхом творчого використання текстурних карт або інших методів. Висока швидкість обчислення зробила кидання променів зручним методом рендеринга в ранніх 3D-відеоіграх реального часу.

У природі джерело світла випромінює промінь світла, який, врешті-решт, рухається до поверхні, яка й перериває його прогрес. Можна уявити цей "промінь" як потік фотонів, що рухаються уздовж тієї самої траєкторії. На цьому шляху може бути будь-яке поєднання трьох речей з цим світловим променем: поглинання, відбиття та рефракція. Поверхня може відбити весь або частину світлового променя в одному або декількох напрямках. Вона також може поглинути частину світлового променя, що призводить до втрати інтенсивності відбитого та / або заломленого світла. Якщо поверхня має будь-які прозорі або напівпрозорі властивості, вона заломлює частину світлового променя в собі, в іншому напрямку — поглинаючи деякий (або весь) спектр (і, можливо, змінюючи колір). Між поглинанням, відбиттям та заломленням, все вхідне світло повинно враховуватися, і не більше. Поверхня, наприклад, не може відбити 66% вхідного світлового проміння, і рефрактувати 50%, оскільки ці два значення складають 116%. Звідси, відбиті та / або заломлені промені можуть "вражати" інші поверхні, де їх поглинаючі, рефракційні та відбиваючі властивості знову підраховуються на основі вхідних променів. Деякі з цих променів рухаються таким чином, що відповідно потрапляють в очі, змушуючи нас бачити дійсність і тим самим сприяють появі зображення. Спроба симулювати цей реальний процес трасуванням світлових променів за допомогою комп'ютера може вважатися надзвичайно марною, оскільки лише мізерна частка фізичних променів світла дійсно потрапляє у видимість або вюпорт.

Вперше алгоритм кидання променів, що використовується для рендеринга, був представлений Артуром Аппелем (Arthur Appel) у 1968 році.[6] Ідея кидання променів полягає в основі відстеження променю від ока, один на піксель, і знаходити найближчий об'єкт, який блокує шлях цього променю. Наче зображення екранованих дверей, причому кожен квадрат на екрані є піксельним. Це є тим об'єктом, який око бачить через цей піксель. Використовуючи властивості матеріалу та вплив світла на сцену, цей алгоритм може визначити затінення цього об'єкта. Спрощене припущення говорить, що якщо поверхня повернута до світла, світло досягне цієї поверхні і не буде заблоковано або знаходитись в тіні. Затінення поверхні обчислюється за допомогою алгоритмів затінення традиційної 3D комп'ютерної графіки. Однією з найважливіших переваг кидання променів (над старшими алгоритмами сканування), була його здатність легко мати справу з непласкими поверхнями та твердими тілами, такими як конуси та сфери. Якщо математична поверхня може перетинатися променем, вона може зазнати рендеринг ​​за допомогою кидання променів. Складні об'єкти можуть бути створені за допомогою методу моделювання твердих тіл та легко відтворенні через рендеринг.

Раннє використання алгоритму рендеринга кидання променів був здійснений компанією Mathematical Applications Group, Inc. (MAGI) міста Ельмсфорд (штат Нью-Йорк).[7]

Кидання променів в комп’ютерних іграх[ред. | ред. код]

Wolfenstein 3D[ред. | ред. код]

Сцена з Wolfenstein 3D (iD Software). Зверніть увагу на блоковий вигляд. Об'єкти (зброя) і вороги (собака) - це просто прозорі растрові зображення, які масштабуються та стираються (наприклад, вставляються) на тлі.

Світ у Wolfenstein 3D побудований з квадратної сітки стін рівномірної висоти, які стикаються з суцільними підлогами і стелями. Для того, щоб промалювати світ, відстежується один промінь для кожного стовпця пікселів на екрані, де вертикальний фрагмент текстури стінки вибирається та масштабується відповідно до того, як промінь натикається на стіну світу і наскільки далеко він рухався перед цим зіткненням. [8]

Створення рівнів побудованих на сітці виконує два завдання: зіткнення променю зі стіною можна визначити швидше, оскільки потенційні зіткнення є більш передбачуваними та це потребує значно менше ресурсів для роботи. Проте кодування широких відкритих областей займає додатковий простір

Значення рівнів, побудована на сітці є двояке: зіткнення променю зі стіною можна визначити швидше, оскільки потенційні зіткнення є більш передбачуваними та це потребує значно менше ресурсів для роботи. Проте кодування широких відкритих областей займає додатковий простір.

Серія Comanche[ред. | ред. код]

Рушій Voxel Space, розроблений компанією NovaLogic для ігор Comanche, простежує промінь через кожен стовпець пікселів екрану і перевіряє кожен промінь у напрямку до точок на карті висот. Потім він перетворює кожен елемент карти висот в стовпчик пікселів, визначає, які з них видимі (тобто не були заблоковані пікселями, які були зроблені попереду), і малює їх відповідним кольором з текстурної карти. [9]

Обчислювальна геометрія[ред. | ред. код]

В обчислювальній геометрії проблема кидання променів також відома як проблема ray shooting і може бути зазначена як наступна задача запиту. Враховуючи набір об'єктів у d-вимірюваному просторі, попередня обробка їх структури даних є така, щоб для кожного запиту променю можна було швидко знайти початковий об'єкт, на якій потрапляє промінь. Проблема була досліджена для різних параметрів: просторовий вимір, види об'єктів, обмеження на запит променю тощо. [10] Одним з методів є використання Sparse Voxel Octree.

Дивись також[ред. | ред. код]

Примітки[ред. | ред. код]

  1. Scott D, Roth (February 1982). "Ray Casting for Modeling Solids", Computer Graphics and Image Processing (en). с. 18 (2): 109–144. doi:10.1016/0146-664X(82)90169-1. 
  2. Woop, Sven; Schmittler, Jörg; Slusallek, Philipp (2005). "RPU: A Programmable Ray Processing Unit for Realtime Ray Tracing" (en). Siggraph 2005. с. 24 (3): 434. doi:10.1145/1073204.1073211. 
  3. Weiskopf, Daniel (2006). GPU-Based Interactive Visualization Techniques (en). Springer Science & Business Media. с. p. 21. ISBN 978-3-540-33263-3. 
  4. Foley, James D; van Dam, Andries; Feiner, Steven K; Hughes, Steven K; Hughes, John F (1995). Computer Graphics: Principles and Practice (en). Addison-Wesley. с. p. 701. ISBN 0-201-84840-6. 
  5. Boulos, Solomon (2005). Proceeding SIGGRAPH '05 ACM SIGGRAPH 2005 Courses Article No. 10 (en). New York, NY, USA: ACM. doi:10.1145/1198555.1198749. 
  6. Macey, Jon. "Ray-tracing and other Rendering Approaches" lecture notes, MSc Computer Animation and Visual Effects (PDF) (en). University of Bournemouth. 
  7. Goldstein, R.А; Nagel, R (1971). Simulation 16(1). 3-D visual simulation (en). с. 25–31. 
  8. Ray-Casting Tutorial For Game Development And Other Purposes. http://permadi.com (en). May 6, 1996. Процитовано 13.08.2017. 
  9. LaMothe, Andre (1995). Black Art of 3D Game Programming (en). с. 14, 398, 935–936, 941–943. ISBN ISBN 1-57169-004-2. 
  10. de Berg, Mark (1993). Ray shooting, depth orders and hidden surface removal (en). Springer-Verlag. с. 201. ISBN 3-540-57020-9. 

Зовнішні посилання[ред. | ред. код]