ВИДАЛЕННЯ НЕВИДИМИХ ПОВЕРХОНЬ І ЛІНІЙ

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

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

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

Рис. 8.1. Неоднозначність сприйняття зображення куба

Складність завдання видалення невидимих ліній і поверхонь привела до появи великої кількості різних способів її рішення. Багато хто з них орієнтовані на спеціалізовані додатки. Єдиного (загального) рішення цього завдання, придатного для різних випадків, природно, не існує: для кожного випадку вибирається найбільш підходящий метод. Наприклад, для моделювання процесів у реальному часі потрібні швидкі алгоритми, у той час як для формування складного реалістичного зображення, у якому представлені тіні, прозорість і фактура, що враховують ефекти відбиття й переломлення кольору в дрібних відтінках, фактор часу виконання вже не так существенен. Подібні алгоритми працюють повільно, і найчастіше на обчислення потрібно кілька мінут або навіть годин. Існує тісний взаємозв'язок між швидкістю роботи алгоритму й детальністю його результату. Жоден з алгоритмів не може досягти гарних оцінок для цих двох показників одночасно. У міру створення усе більше швидких алгоритмів можна будувати усе більше детальні зображення. Реальні завдання, однак, завжди будуть вимагати обліку ще більшої кількості деталей.

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

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

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