Алгоритми видалення невидимих ребер та граней

 

При побудові непрозорих об’єктів варто враховувати, що деякі ділянки їхньої поверхні не видні спостерігачеві, тому що закриваються іншими частинами об’єкта.

Є різні алгоритми видалення невидимих частин. Деякі із них засновані на сортуванні граней по відстані від спостерігача. Нехай є дві грані, що перебувають на різній відстані від точки спостереження (Рис. 1.5).

 

Рис. 1.5. Розташування закритих граней об’єкта щодо спостерігача

 

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

Алгоритми видалення невидимих граней можуть бути умовно поділені на два класи залежно від принципів, закладених для їхньої реалізації. Перший клас – це алгоритми що працюють в просторі об’єкта. Це означає, що для визначення видимості даної грані рівняється її взаємне розташування з усіма іншими гранями в тривимірній сцені. Нехай N – кількість граней у тривимірній сцені. Для побудови тривимірної сцени в цьому випадку необхідно зрівняти положення кожної грані із тими, що залишилися, це вимагає порядку  операцій. Наприклад, нехай кількість граней у тривимірній сцені , тоді час роботи алгоритмів цього класу порядку 1 000 000 операцій [11].

Другий клас алгоритмів - працюючих у просторі зображення, заснований на знаходженні точки найближчої грані яку перетинає промінь зору, що проходить через задану точку на екрані. Оскільки число точок на растровому екрані фіксоване, то алгоритми цього класу менш чутливі до збільшення кількості об’єктів у тривимірній сцені. Нехай n - число точок на растровому екрані. Тоді кількість операцій, необхідних для побудови тривимірної сцени буде порядку . Наприклад, для екранного розширення 320  200 точок, 64000, тоді кількість операцій для 1000 граней буде порядку 64 000 000. Вибір класу алгоритму може залежати від особливостей конкретної задачі, а також від способів реалізації алгоритму.

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

 

, (1.35)

, (1.36)

, (1.37)

 

де п - кількість вершин кожної грані. При виконанні геометричних перетворенні об’єкта, наприклад при його поворотах, перетворюються й координати середніх точок граней. Будемо вважати, що напрямок спостереження — уздовж осі х.

Перед побудовою об’єкта проводимо сортування середніх точок його граней по х -координаті й малювання граней починається з найбільш віддаленої. Цей метод називається алгоритмом художника.

Розглянутий алгоритм не дуже ефективний, оскільки припускає вивід навіть тих частин об’єкта, які спостерігачеві не видні. Є й інші алгоритми видалення невидимих частин об’єкта. Серед них алгоритм z -буфера й деякі інші.

Z -буфер являє собою "поточкову" копію екрана, яку можна зберігати, наприклад, у виді масиву цілих значень. Спочатку всім елементам цього масиву привласнюються початкові значення, рівні максимально припустимим цілим. Кожній точці зображення поверхні зіставляється значення відстані від цієї точки до площини спостереження. При виводі зображення чергової точки поверхні це значення параметра рівняється зі значенням, записаним для неї в z -буфері. Якщо при цьому виявляється, що значення з z -буфера більше, графічна крапка виводиться на екран, тому що вона перебуває ближче до спостерігача. Відстань до точки заноситься в z -буфер. У протилежному випадку графічна точка не виводиться, оскільки вона "затуляється" уже намальованою точкою. Описаний алгоритм виявляється більш ефективним при побудові складних поверхонь, хоча і вимагає додатковий затрат пам’яті.

Ще один метод визначення невидимих поверхонь заснований на використанні нормалі – перпендикуляра до поверхні грані. Якщо вважати, що нормаль спрямована з об’єкта назовні, то у видовій системі координат проекція нормалі па вісь z, яку ми вважаємо що вона іде до площини екрану і спостерігача, буде позитивною, у тому випадку, коли грань видна спостерігачеві, і негативної, коли не видна. Як побудувати нормаль? Якщо вважати, що дві сторони багатокутника, що виходять із загальної вершини, є векторами, то їхній векторний добуток можна прийняти за нормаль до поверхні цього багатокутника. Напрямок нормалі буде однозначно визначено, якщо задано порядок векторних співмножників. Спрощений варіант даного алгоритму укладається в те, що вершини грані нумеруються по годинниковій стрілці. Якщо подивитися на цю грань із "тильної" сторони, нумерація вершин буде йти проти годинникової стрілки. Порядок нумерації, таким чином, можна використати для визначення того, чи видна дана грань із обраної точки спостереження [12].

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

 

Рис. 1.6. Перетинання прямої AB із площинами граней призми

 

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