Метод Z-Буфера

Це один з найпростіших алгоритмів видалення невидимих поверхонь. Уперше він був запропонований Кэтмулом в 1975 р. Працює цей алгоритм у просторі зображення. Ідея Z-Буфера є простим узагальненням ідеї про буфер кадру. Буфер кадру використовується для запам'ятовування атрибутів кожного пикселя в просторі зображення, а Z-Буфер призначений для запам'ятовування глибини (відстані від картинної площини) кожного видимого пикселя в просторі зображення. Оскільки досить розповсюдженим є використання координатної площини як картинна площина, то глибина дорівнює координаті крапки, звідси й назва буфера. У процесі роботи значення глибини кожного нового пикселя, якому потрібно занести в буфер кадру, рівняється із глибиною того пикселя, що вже занесений в Z-Буфер. Якщо це порівняння показує, що новий пиксель розташовано спереду пикселя, що перебуває в буфері кадру, те новий пиксель заноситься в цей буфер і, крім того, виробляється коректування Z-Буфера новим значенням глибини. Якщо ж порівняння дає протилежний результат, то ніяких дій не виробляється. По суті, алгоритм є пошуком по й найбільшого значення функції .

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

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

Наприклад, можна розбивати простір зображення на 4, 16 або більше прямокутників або смуг. У граничному варіанті можна використовувати буфер розміром в один рядок розгорнення. Для останнього випадку був розроблений алгоритм порядкового сканування. Оскільки кожний елемент сцени обробляється багато разів, то сегментування Z-Буфера, загалом кажучи, приводить до збільшення часу, необхідного для обробки сцени.

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

У цілому алгоритм виглядає так:

1. Заповнити буфер кадру фоновим значенням кольору.

2. Заповнити Z -буфер мінімальним значенням z (глибини) .

3. Перетворити зображувані об'єкти в растрову форму в довільному порядку.

4. Для кожного об'єкта:

4.1. Для кожного пикселя образа обчислити його глибину .

4.2. Зрівняти глибину зі значенням глибини, що зберігається в Z-Буфері в цій же позиції.

4.3. Якщо , те занести атрибути пикселя в буфер кадру й замінити . У противному випадку ніяких дій не робити.

Алгоритм, що використовує Z-Буфер, можна також застосовувати для побудови перетинів поверхонь. Зміниться тільки оператор порівняння:

де - глибина шуканого перетину.

Методи пріоритетів (художника, що плаває обрію)

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

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

Нехай поверхня задана рівнянням

Як картинна площина виберемо площину . В області завдання функції на осях координат побудуємо сітку вузлів:

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

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

Рис. 8.4. Просте каркасне зображення з поверхні

Рис. 8.5. Каркасне зображення діагональними ребрами

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

Насправді ми будемо малювати чотирикутник і одна діагональ. У процесі малювання нам знадобляться два целочисленных масиви: (нижній обрій) і (верхній обрій) розмірністю, що відповідає горизонтальному розміру екрана в пикселях. Вони потрібні для аналізу видимості ділянок зображуваних відрізків. Спочатку ми инициализируем верхній обрій нулем, а нижній - максимальним значенням вертикальної координати на екрані. Кожна виведена на екран крапка може закривати інші крапки, які "ховаються за обрієм". У міру малювання нижній обрій "опускається", а верхній "піднімається", поступово залишаючи усе менше незакритого простору. На відміну від методу художника, тут ми просуваємося від ближнього кута до далекого. Тепер опишемо алгоритм докладніше.

Функція в цьому фрагменті призначена для виводу на екран відрізка прямій, причому в момент ініціалізації чергового пикселя вона виконує наступні дії:

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

На мал. 8.5 наведений приклад зображення поверхні з використанням цього алгоритму.