International scientific e-journal

ΛΌГOΣ. ONLINE

16 (December, 2020)

e-ISSN: 2663-4139
КВ №20521-13361Р

ENGINEERING AND IT

UDC 519.6

EOI 10.11232/2663-4139.16.41

МЕТОДИ ТА АЛГОРИТМИ РЕНДЕРИНГУ ЗОБРАЖЕННЯ ДЛЯ СИСТЕМ ТРИВИМІРНОЇ КОМП'ЮТЕРНОЇ ГРАФІКИ

ЧЕРНИШОВ Олег Дмитрович

здобувач вищої освіти факультету інформаційних технологій

Державний вищий навчальний заклад «Приазовський державний технічний університет»

 

НАУКОВИЙ КЕРІВНИК:

 

ОСТАПЕНКО Артем Олексійович

ORCID ID: 0000-0003-3368-8203

канд. техн. наук, ст. викладач кафедри вищої та прикладної математики,

Державний вищий навчальний заклад «Приазовський державний технічний університет»

 

УКРАЇНА


Анотація. В роботі описані алгоритми комп’ютерної графіки: трасування та марширування променів. Розглянуті особливості їх реалізації. Розроблена комп'ютерна програма, що реалізує ці алгоритм, за допомогою якої проведено їх дослідження, зокрема порівняння продуктивності.

Ключові слова: комп’ютерна графіка; рендеринг зображень; трасування променів; марширування променів; ефективність алгоритму.

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

Аналіз досліджень і публікацій. Підвищення продуктивності являється однією із головних задач фотореалістичного відображення тривимірних об'єктів [1]. Увесь час іде удосконалення методів підвищення продуктивності формування зображень [2-3] і пошук альтернативних алгоритмів отримання реалістичної графіки [4-5].

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

Виклад основного матеріалу. 

На сьогодні, в більшості систем комп'ютерної графіки широко використовують методи променів. Головним принципом будь-якого такого алгоритму є випускання променів з очей спостерігача в бік віртуальної тривимірної сцени, і знаходження точок перетину з об'єктами всередині сцени.

До методів променів відносяться:

  • Трасування променів (анг. Ray tracing). Відправляється промінь, який шукає перетин з кожним об'єктом сцени окремо аналітичним методом.

  • Марширування променів (анг. Ray marching). Промінь летить з певним кроком, а перетин з об'єктом вважається, коли відстань від променя до об'єкта менше мінімального кроку. Це дискретний метод.

Одним з найпопулярніших є алгоритм трасування променів. В його основі лежить аналітичний принцип роботи.

Для того щоб візуалізувати сферу на поверхні екрану, нам потрібно записати рівняння променя (прямої) в параметричному вигляді (1) і рівняння самого об'єкта, в нашому випадку сфери (2):

                                                       (1)

                             (2)

де   – радіус-вектор точки центру камери,

– вектор променя спрямованого в сцену,

t– параметр,

– радіус-вектор центру сфери,

R – радіус сфери.

 

Далі підставляємо рівняння прямої (1) в рівняння сфери (2):

         (3)

Тепер, для того щоб знайти точку перетину потрібно розв'язати це рівняння

Щоб спростити обчислення ми можемо нормувати вектор , так як для нас не важлива довжина променя, і замінити різницю векторів  на вектор для скорочення запису. Тоді отримаємо:

                     (4)

В рівнянні (4) позначимо   та . Отримаємо квадратне рівняння відносно параметра t. Розв’яжемо його, враховуючи, що .

,

Якщо , то промінь не перетинає сферу.

Якщо , то промінь має одну точку перетину.

Якщо , то промінь потрапив в сферу і має дві точки перетину і найближча відповідає параметру t = min(t1,t2).

Оскільки наша мета максимальна ефективність алгоритму, то можна врахувати наступне:

b – скалярний добуток між векторами напрямку променя та різницею радіус-векторів початку променя і центру кулі . Тоді за властивостями скалярного множення його негативна величина вказує нам на те, що кут між векторами більше  та менш . Отже, даний промінь не може перетнутися зі сферою. Ця інформація дозволяє нам не виробляти обчислення дискримінанту зайвий раз.

c – різниця квадрата модуля вектора між камерою і центом кулі і квадратом радіуса сфери. Від’ємне значення якого свідчить про те, що камера розташована всередині сфери.

Так само слід встановити деякі граничні умови:  і , так як ми можемо бачити тільки ті об'єкти, які знаходяться перед камерою. І якщо , то  і вигідніше спочатку перевірити . В разі успіху ми можемо ігнорувати одну логічну перевірку.

В якості альтернативи методу трасування променів, використовується алгоритм марширування променя. Замість того, щоб розв’язувати задачу аналітично, вона розв’язується дискретно. Пускається відрізок вздовж напрямку променя, який рухається із заданим кроком (довжини). Одним з недоліків такого підходу є можливість пропустити справжню точку перетину, і допустити деяку неточність. Тому спільно з даним алгоритмом застосовується метод знаходження полів відстаней. Поле відстаней це функція, що отримує на вході точку і повертає мінімальну відстань від неї до кожного об’єкту сцени.  Таким чином, для знаходження точки перетину променя зі сферою, нам потрібно вивести рівняння поля відстаней до поверхні сфери. Вважаємо, що сфера знаходиться в центрі своїх локальних координат, тобто її центр перебуває в точці (0,0,0), тоді щодо її центру, скаляр відстані до поверхні можна записати так:

  (5)

де f = f(x,y,z) – мінімальна відстань до поверхні сфери від точки P(x,y,z),

R – радіус сфери,

length – функція знаходження відстані в евклідовому просторі від точки до центру сфери.

 

Тепер необхідно змістити поточну точку P на знайдену відстань f вздовж променя , що напрямлений у сторону спостереження:

             (6)

де – радіус-вектор точки P,

– радіус-вектор точки центру камери.

 

І повторюємо крок (4) і (5) n разів () або поки , де N – максимальна кількість кроків, а деяка мала величина, зазвичай її беруть 0,001, але все залежить від допустимої нами похибки.

 

Таблиця 1. Результат роботи програми

Алгоритм трасування виявляється швидше. Однак через те, що алгоритм марширування променя використовує знаходження поля відстаней ми можемо відображати більш складні об'єкти, такі як фрактали (рис. 1), для яких аналітичний розв’язок знаходження точки перетину з променем є нетривіальною задачею.

Рис. 1. Тривимірний фрактал – губка Менгера

 

Висновки. У процесі порівняння двох алгоритмів можна прийти до висновку, що хоч алгоритм марширування променів незначно програє навіть при використанні полів відстаней алгоритму трасування, який за рахунок свого аналітичного принципу роботи виграє в продуктивності. Але алгоритм марширування є більш зручним у використанні інструментом для візуалізації складної тривимірної графіки, що абсолютно нівелює його недоліки.


СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ:

 

  • Vasiou, E., Shkurko, K., Mallett, I., Brunvand, E. & Yuksel, C. (2019) A Detailed Study of Ray Tracing Performance: Render Time and Energy Cost. Visual Computer, 34(4), 1-10. https://doi.org/10.1007/s00371-018-1532-8

  • Мохаммад Ю.Я. (2016) Разработка программно-аппаратных решений повышения производительности компьютерных систем формирования трехмерных изображений. (диссертация канд. техн. наук). Донецкий Национальный Технический Университет, Красноармейск, Украина.

  • Мальцев А.В. (2011) Методы  и алгоритмы эффективного вычисления освещенности  трехмерных виртуальных сцен в реальном режиме времени. (диссертация канд. физ.-матем. наук). Научно-исследовательский институт  системных  исследований  РАН, Москва, Россия.


IMAGE RENDERING METHODS AND ALGORITHMS FOR THREE-DIMENSIONAL COMPUTER GRAPHICS SYSTEMS

CHERNYSHOV O.,
Student of the Faculty of Information Technologies
Pryazovskyi State Technical University

SCIENTIFIC ADVISER:

OSTAPENKO A.,
PhD (Technical Sciences), Senior Teacher of the Department of High and Applied Mathematics
Pryazovskyi State Technical University
UKRAINE

Abstract.
The paper describes the algorithms of computer graphics: ray tracing and ray marching. The peculiarities of their implementation are considered. A computer program that implements these algorithms has been developed, which used in methods research, in particular, comparison of productivity, has been carried out.


Keywords: computer graphics; image rendering; ray tracing; ray marching; algorithm efficiency.

© Чернишов О.Д., 2020

© Chernyshov O., 2020

 

This work is licensed under a Creative Commons Attribution 4.0 International License.

PUBLISHED : 11.12.2020