facebook
twitter
vk
instagram
linkedin
google+
tumblr
akademia
youtube
skype
mendeley
Wiki
Global international scientific
analytical project
GISAP
GISAP logotip

КОМБІНОВАНИЙ МЕТОД ПРИСКОРЕНОГО ВИЗНАЧЕННЯ ОДИНИЧНИХ ВЕКТОРІВ

Автор Доклада: 
Романюк О.В.
Награда: 
КОМБІНОВАНИЙ МЕТОД ПРИСКОРЕНОГО ВИЗНАЧЕННЯ ОДИНИЧНИХ ВЕКТОРІВ

УДК 004.921

КОМБІНОВАНИЙ МЕТОД ПРИСКОРЕНОГО ВИЗНАЧЕННЯ ОДИНИЧНИХ ВЕКТОРІВ

Романюк Оксана Володимирівна, аспірант
Вінницький національний технічний університет


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

There has been proposed combined method of accelerated unit vector calculation, which allows to eliminate trigonometric functions from calculation process and reduce the quantity of division and square root operations.
Key words: unit vector, interpolation.

У задачах формування реалістичних зображень невід’ємною складовою є розрахунок векторів до внутрішніх точок рядків растеризації [1, 2]. При розрахунку векторів у точках поверхні вздовж рядка растеризації використовують лінійне інтерполювання для визначення ортогональних складових вектора з подальшою нормалізацією знайдених векторів. Оскільки нормалізація виконується для кожної точки поверхні, то важливою задачею є зменшення обчислювальної складності визначення нормалізованих векторів.

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

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

Нехай рядок растеризації містить m точок. Позначимо позиції непарних точок рядка растеризації через , а парних – через .
Ортогональні складові векторів у непарних точках рядка растеризації можна визначити за формулою


Рис. 1. Розрахунок векторів шляхом лінійного інтерполювання в непарних точках та за принципом дихотомії в парних точках рядка растеризації

У формулі (3) складним з апаратної точки зору є розрахунок виразу . Для зменшення кількості розрахунків виразу   було зроблено припущення, що значення кута   для усіх пар векторів, розташованих у сусідніх непарних точках рядка растеризації, є сталим числом. Позначимо цей кут через . Тоді кут , утворений початковим і кінцевим   векторами рядка растеризації, буде дорівнювати

Таким чином, замість операції  необхідно виконати лише 1 операцію множення та 2 операції типу інкрементування/декрементування.

На рис. 2 зображено поверхню, яка відображає залежність абсолютної похибки ^ апроксимації виразу від   кута  та кількості точок m у рядку растеризації.

Рис. 2. Залежність абсолютної похибки від кута і кількості точок

Як видно з графіка, максимальна абсолютна похибка апроксимації має місце для значень кута , які близькі до 900, і при m<10. Для більшої частини поверхні абсолютна похибка апроксимації приймає значення близькі до нуля. 

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

Література:

  • 1.Порев В.Н. Компьютерная графика / В.Н.Порев. – Спб.: БХВ-Петербург, 2002. – 432 с.
  • 2.Ламот А. Программирование трехмерных игр для Windows. Советы профессионала по трехмерной графике и растеризации. – М.: ИД «Вильямс», 2004. – 1424 с.
  • 3.Романюк О. Н. Комбіноване використання бінарної та кодової лінійної інтерполяції для нормалізації векторів нормалей при зафарбовуванні тривимірних об’єктів / О. Н. Романюк // Вестник Херсонского национального технического университета. — 2006. — № 25. — С. 408—411.
6.75
Ваша оценка: Нет Средняя: 6.8 (4 голоса)

"шило на мило" ?

Важко оцінити рівень ефективності запропонованого методу, в якому водночас зі зменшенням складності обчислень збільшується похибка апроксимації на певній ділянці графіка (рис.2) та припускається, що кут у формулі (3) є сталим. Для сучасних процесорів швидкодія обчислення будь-яких (у т.ч. й тригонометричних функцій) - не проблема, тоді як значно важливішим є роздільна здатність зображень. Загальна оцінка - "посередньо".

Відповідь

Шановний Володимир Васильович, дякую Вам за увагу до моєї роботи. Стосовно питань роздільної здатності зображень, то ними займаються розробники моніторів. Я працюю у галузі компьютерної графіки, основною задачею якої є підвищення продуктивності формування реалістичних зображень, особливо у динамічному режимі. Сучасні процеси дійсно є потужними, але вимоги до реалістичності зображень постійно зростають, випереджаючи темпи розвитку процесорів. В сучасних комп'ютерних іграх в сцені в середньому використовується 300000–500000 полігонів, які графічна відеокарта повинна відображати зі швидкістю більшою 25 кадрів у секунду. У найближчі роки очікуються ігри, що використовуватимуть до 1000000–3000000 полігонів у сцені. Для кожної точки полігона потрібно виконати велику кількість розрахунків, повязаних з визначенням векторів, їх нормалізацією, розрахунком текстурних координат з урахуванням перспективи, розрахунком освітленності та багатьох інших процедур, що дозволяють формувати реалістичні зображеня. Очевидно, що формування реалістичних зображень є надзвичайно трудомістким процесом, тому актуальним є питання зменшувати обчислювальну складність, зокрема шляхом вилучення таких трудомістких операцій, як ділення, квадратний корінь, тригонометричні операції, які все ще "повільно" виконуються. Щодо похибки на рис.2, то вона має місце для випадків (кількість точок у рядку растеризації менше 8 при куті між векторами у кінцевих точках рядка растеризації близьких до 90 град.), ймовірність появи яких дуже мала. В межах робочої зони похибка майже дорівнює нулю, що не призводить до візуальних змін у зображенні. Якщо ж трапився випадок, коли похибка приймає велике значення, то рядок растеризації можна розбити на два підінтервали та для кожного з них виконати описані дії.

Похвала и вопрос по прикладному использования метода.

Оксана, Ваша работа мне понравилась. Чувствуется хорошая математическая и научно- методическая школа подготовки. К сожалению, продвинутых математически коллег женского пола нас зачастую в некоторых организациях (далеко не всех) окружает очень мало. К сожалению, я не знаю украинского языка. Но из аннатации на английском и математической формализации материала, я склоняюсь к мысли , что практической прикладной значимостью Ваших научных изысков может явиться уход от необходимости решения транциндентных уравнений в неявном виде численным методом, например, методом касательных? Хотелось бы получить ответ на этот вопрос.

О методе касательных

Уважаемый Вячеслав Викторович, я очень благодарна Вам за внимание к моей статье. Одной из задач в области компьютерной графики, в которой я работаю, есть упрощение процеса формирования реалистичных изображений, поэтому необходимо уменьшать количество "длинных" операций, таких как деление, квадратный корень, тригонометрические функции. В данной статье я пыталась уйти от необходимости находить угол "пси", поскольку это требует выполнения операции аркосинуса. Поэтому стояла задача найти cos(2*'psi'/(m-1)) через cos(psi), который легко находится как скалярное произведение двух нормализированных векторов. Для этой цели было выбрано разложение в ряд Тейлора. Метод касательных можно было бы использовать для нахождения угла "пси", но это итерационный метод, кроме того, он предполагает нахождение производной (это приведет к появлению синуса), выполнение операции деления, что в нашем случае использовать невыгодно.

Отклик на ответ

Уважаемая Оксана, теперь после Вашего пояснения всё стало ясно. Ещё раз подтверждаю очень хорошее впечатление от Вашей работы. Желаю Вам больших успехов на научном поприще!

)

Мои пожелания Вам, Оксана, успешно завершить работу над диссертацией! Дело сложное, но выполнимое, тем более, с таким подходом.

)

Уважаемая Татьяна Львовна, мне очень приятно, что моя статья произвела на Вас приятное впечатление. Большое Вам спасибо за пожелания.
Партнеры
 
 
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
image
Would you like to know all the news about GISAP project and be up to date of all news from GISAP? Register for free news right now and you will be receiving them on your e-mail right away as soon as they are published on GISAP portal.