НОУ ІНТУІТ, Лекція, Видалення невидимих поверхонь та ліній
Завдання видалення невидимих ліній і поверхонь є однією з найцікавіших і найскладніших у комп'ютерній графіці. Алгоритми видалення полягають у визначенні ліній ребер, поверхонь або обсягів, які є видимими або невидимими для спостерігача, що знаходиться в заданій точці простору.
Необхідність видалення невидимих ліній, ребер, поверхонь чи обсягів проілюстровано на рис. 6.1. Малюнок наочно демонструє, що зображення без видалення невидимих ліній сприймається неоднозначно.
Складність завдання видалення невидимих ліній та поверхонь призвела до появи великої кількості різних способів її вирішення. Багато з них орієнтовані на спеціалізовані програми. Єдиного (загального) вирішення цього завдання, придатного для різних випадків, природно, не існує: для кожного випадку вибирається найбільш вдалий метод. Наприклад, для моделювання процесів у реальному часі потрібні швидкі алгоритми, у той час як для формування складного реалістичного зображення, в якому представлені тіні, прозорість і фактура, що враховують ефекти відображення та заломлення кольору в найдрібніших відтінках, фактор часу виконання вже не такий істотний. Подібні алгоритми працюють повільно, і часто на обчислення потрібно кілька хвилин або годин. Існує тісний взаємозв'язок між швидкістю роботи алгоритму та детальністю його результату. Жоден з алгоритмів неспроможна досягти хороших оцінок цих двох показників одночасно. У міру створення дедалі швидших алгоритмів можна будувати дедалі детальніші зображення. Реальні завдання, однак, завжди вимагатимуть урахування ще більшої кількості деталей.
Всі алгоритми такого роду так чи інакше включаютьсортування, причому головне сортування ведеться по геометричній відстані від тіла, поверхні, ребра або точки до точки спостереження чи картинної площини. Основна ідея, покладена в основу сортування на відстані, полягає в тому, що далі розташований об'єкт від точки спостереження, тим більша ймовірність, що він буде повністю або частково заслонений одним з об'єктів, ближчих до точки спостереження. Після визначення відстаней абопріоритетівпо глибині залишається провести сортування по горизонталі і по вертикалі, щоб з'ясувати, чи буде об'єкт, що розглядається, дійсно заслонений об'єктом, розташованим ближче до точки спостереження. Ефективність будь-якого алгоритму видалення значною мірою залежить ефективності процесу сортування.
Алгоритми видалення невидимих ліній чи поверхонь можна класифікувати за способом вибору системи координат чи простору, де вони працюють. Алгоритми, що працюють в об'єктному просторі, мають справу зі світовою системою координат, де описані ці об'єкти. У цьому виходять дуже точні результати, обмежені, власне кажучи, лише похибкою обчислень . Отримані зображення можна вільно масштабувати. Алгоритми, що працюють в об'єктному просторі, особливо корисні в додатках, де необхідна висока точність . Алгоритми, що працюють у просторі зображення, мають справу з системою координат того екрана, на якому об'єкти візуалізуються. При цьому точність обчислень обмежена роздільною здатністю екрана.
Ми наведемо деякі з алгоритмів, що працюють як в об'єктному просторі, так і в просторі зображення, кожен з яких ілюструє одну або кілька основних ідей теорії алгоритмів видалення невидимих ліній і поверхонь.
Видалення нелицьових граней багатогранника
Алгоритм Робертса
Цей алгоритм, запропонований у 1963 р., є першою розробкою такого роду і призначений для видалення невидимих ліній при штриховому зображенні об'єктів, які складаються з опуклих багатогранників. Він відноситься до алгоритмів, що працюють в об'єктному просторі, і дуже елегантний з математичної точки зору. У ньому дуже вдало поєднуються геометричні методи та методи лінійного програмування.
Випуклий багатогранник однозначно визначається набором площин, що утворюють його грані, тому вихідними даними алгоритму є багатогранники, задані списком своїх граней. Грані задаються у вигляді площин, заданих у канонічній формі (див. "Геометричні перетворення") в об'єктній системі координат: .
Таким чином, кожна площина визначається чотиривимірним вектором , а кожна точка , задана в однорідних координатах, також є чотиривимірним вектором:
Приналежність точки площини можна з допомогою скалярного твори, тобто. якщо , то точка належить площині, а якщо ні, то знак твору показує, з якого боку від площині ця точка перебуває. У алгоритмі Робертса площини будуються в такий спосіб, що внутрішні точки багатогранника лежать у позитивної полуплоскости. Це означає, що вектор єзовнішньою нормаллюдо багатогранника (рис. 6.2). З векторів площин будується прямокутна матриця порядку, яка називаєтьсяузагальненою матрицею опису багатогранника:
Помножуючи стовпці матриці на вектор, отримаємоn-мірний вектор, і якщо всі його компоненти невід'ємні, то точка належить багатограннику. Цю умову будемо записувати у вигляді (мається на увазі множеннявектор-рядки на матрицю).
У своєму алгоритмі Робертс розглядає лише відрізки, що є перетином граней багатогранника.
З узагальненої матриці можна отримати інформацію про те, які межі багатогранника перетинаються у вершинах. Справді, якщо вершина належить граням , вона задовольняє рівнянням
Алгоритм насамперед видаляє з кожного багатогранника ті ребра чи грані, які екрануються самим тілом. Робертс використав для цього простий тест: якщо одна чи обидві суміжні грані звернені своєю зовнішньою поверхнею до спостерігача, то ребро є видимим. Цей тест виконується обчисленням скалярного твору координат спостерігача на вектор зовнішньої нормалі грані: якщо результат негативний, то грань видима.
Потім кожне з видимих ребер кожного багатогранника порівнюється з кожним з багатогранників, що залишилися для визначення того, яка його частина або частини, якщо такі є, екрануються цими тілами. Для цього в кожну точку ребра проводиться відрізок променя, що виходить із точки розташування спостерігача. Якщо відрізок не перетинає жодного багатогранників, то точка видима. Для вирішення цієї задачі використовуються параметричні рівняння прямої, що містить ребро, та променя.
Якщо задані кінці відрізка і , а спостерігач розташований у точці, то відрізок задається рівнянням
Для визначення тієї частини відрізка, яка закривається будь-яким тілом, достатньо знайти значення і при яких добуток вектора на узагальнену матрицю позитивно. Для кожної площини записується нерівність
Вважаючи, отримуємо систему рівнянь, рішення якої дають нам точки "зміни видимості" відрізка. Результат можна отримати шляхом спільного вирішення різних пар рівнянь із цієї системи. Числовсіляких рішень при площинах дорівнює.
Оскільки обсяг обчислень зростає зі збільшенням числа багатокутників, бажано в міру можливості скорочувати їх число, тобто. якщо ми апроксимуємо деяку поверхню багатогранником, то як грані можна використовувати не трикутники, а складніші багатокутники. При цьому, зрозуміло, постає проблема, як збудувати такий багатокутник, щоб він мало відхилявся від плоскої фігури.