Loading AI tools
З Вікіпедії, вільної енциклопедії
Алгоритм Ньюелла — це процедура комп'ютерної 3D-графіки для ліквідації циклу з многокутників при сортування по глибині, який використовується для видалення невидимих поверхонь[en]. Був запропонований в 1972 році Мартіном Ньюеллом, Діком Ньюеллом[en] і Т. Санча.
Основна ідея полягає у визначенні многокутників для сортування в залежності від відстані до глядача з тим, щоб потім, починаючи з найдальшого многокутника, намалювати їх усіх один за одним. При продовженні деталі будуть замінюватись на деталі більш близьких об'єктів, якщо вони повністю або частково перекривають попередньо оброблені. Якщо завдання буде виконано правильно, то ця процедура забезпечує правильний перегляд прихованої поверхні.
Починаємо з формування списку багатокутників, які впорядковуються по значенню zmin для кожного багатокутника. Першим у списку буде багатокутним з найменшим значенням zmin. Цей багатокутник найвіддаленіший по Z-напряму. Позначимо його через P, а наступний за ним через Q. Сортування багатокутників P і Q відбувається в кілька етапів, в яких з'ясовується їх взаємне розташування.
Многокутники повинні бути плоскі, тобто, всі вершини повинні лежати на одній площині. Перевірте, чи є які-небудь вершини на площині, підставляючи координати всіх точок у рівняння площини.
Порядок кроків обирається таким чином, щоб прості тести були першими, а більш складні тести виконувались в кінці з метою мінімізації часу на обчислення.
Алгоритм Ньюелла використовує набагато менше ресурсів пам'яті, ніж, скажімо, алгоритм Z-буфера, який частіше використовується для прихованої поверхні обчислень, але явно поступається у швидкості.