Видалення невидимих ліній і поверхонь

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

Розглянемо загальну постановку завдання видалення невидимих частин поверхні, що підлягає візуалізації.

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

Формалізація приводить до такої постановки задачі. Виділимо у просторі R³ деяку площину R² . Простір R³ будемо надалі називати об'єктним простором, а площину R² – картинною площиною. Нехай в об'єктному просторі знаходиться деяка поверхня S, розташована по один бік від картинної площини. Будемо вважати, що спостерігач розташований по інший бік від картинної площини в центрі проектування (у випадку ортогональної проекції центр проектування нескінченно віддалений).

Будемо казати, що крапка р₁ поверхні S загороджує крапку р₂ цієї поверхні, якщо проекції цих крапок на картинну площину збігаються і при цьому крапка р₁ виявляється розташованою між р₂ і їхньою загальною проекцією на картинну площину. Крапка р поверхні називається видимою, якщо ця крапка не загороджена ніякою іншою крапкою поверхні.

Задача видалення невидимих частин поверхні складається у виявленні всіх її видимих ділянок і зображенні їх на картинній площині.

Відомі методи вирішення задачі загороджування розрізняються між собою по чотирьох основних характеристиках:

• вибору структури даних для представлення поверхні;

• просторові, у якому відбувається аналіз видимості;

• способу візуалізації поверхні;

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

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

Представлення поверхні може бути:

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

• поліедральним – поверхня подана сукупністю багатокутних граней;

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

Під вирішенням поліедральної поверхні розуміється кількість її граней.

Під вирішенням картинної площини розуміється кількість крапок растра на екрані монітора.

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

По типу простору, у якому відбувається аналіз видимості, алгоритми діляться на три групи:

• об'єктні – що аналізують взаємне розташування частин поверхні в об'єктному просторі (характеристики часу праці таких алгоритмів мають квадратичну залежність від кількості об'єктів сцени і їхнього вирішення);

• картинні – що визначають видимість кожного елемента картинної площини (піксела) у площини зображення (тимчасові характеристики таких алгоритмів оцінюються як лінійні функції від добутку числа об'єктів на число крапок растра);

• змішані – що використовують для аналізу як перший, так і другий підхід.

По способу візуалізації алгоритми загороджування розділяються на дві групи:

• алгоритми, орієнтовані на одержання каркасного зображення;

• алгоритми, орієнтовані на одержання напівтонового зображення.