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

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

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

Розглянемо алгоритм видалення невидимих граней з використанням z-буфера, який часто використовується в сучасних додатках комп’ютерної графіки. Він працює в просторі зображення та застосовується в таких популярних графічних бібліотеках як OpenGL та Direct3D.

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

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

Розглянемо спосіб прискореного обчислення z-координат при розкладанні багатокутників в растр. Запишемо рівняння площини, яка утворюється багатокутником в просторі: .

Виразимо z-координату точки: . Нехай . Знайдемо z-координату для сусідньої точки . Для сусіднього піксела на екрані , тоді , звідси слід, що . Отже, обчислення z-координати сусіднього піксела зводиться до однієї операції обчислення.

Розглянемо далі алгоритм видалення невидимих граней методом сортування по глибині (автори: Ньюелл, Ньюелл, Санча). Частина цього метода працює в просторі об’єкта, а частина в просторі зображення. Він також працює для паралельної проекції, тобто із врахуванням того що проведено перспективне перетворення. Введемо визначення просторової оболонки.

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

Метод полягає у трьох основних кроках:

1. Впорядкування всіх багатокутників у відповідності з їх найбільшими z-координатами.

2. Розширення всіх невизначеностей, які виникають при перекритті z-оболонок багатокутників.

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

Найближчі багатокутники перетворюються в растрову форму останніми та закривають більш віддалені багатокутники, так як зображаються поверх попередніх. Реалізація пунктів 1 і 3 достатньо очевидна. Розглянемо детальніше пункт 2.

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

П’ять тестів:

1. x-Оболонки багатокутників не перекриваються, тому самі багатокутники також не перекриваються.

2. y-Оболонки багатокутників не перекриваються, тому самі багатокутники також не перекриваються.

3. P повністю розташований з тієї сторони від площини Q, яка далі від точки зору (цей тест дає позитивну відповідь як показано на рис. 36 а).

4. Q повністю розташований з тієї ж самої сторони від площини P, яка ближче до точки зору. Цей тест дає позитивну відповідь як показано на рис. 36 b).

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

Рис. 35. -оболонки трикутників P і Q – перетинаються.

а) b)

Рис. 36. Взаємне розташування трикутників в просторі.

Якщо в усіх п’яти тестах отримана негативна відповідь, то P – дійсно закриває Q. Тоді міняючи P і Q в списку місцями, у випадку, як показано на рис. 37, алгоритм зациклюється.

Рис. 37.

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