Алгоритм Ньюелла

Два багатокутники, які не можуть бути впорядковані по глибині. Тому слід один з них розбити на два багатокутники.

Алгоритм Ньюелла — це процедура комп'ютерної 3D-графіки для ліквідації циклу з многокутників при сортування по глибині, який використовується для видалення невидимих ​​поверхонь. Був запропонований в 1972 році Мартіном Ньюеллом, Діком Ньюеллом і Т. Санча.

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

Сортування багатокутників

Циклічні багатокутники повинні бути усунені, щоб правильно сортувати їх по глибині

Починаємо з формування списку багатокутників, які впорядковуються по значенню z_min для кожного багатокутника. Першим у списку буде багатокутним з найменшим значенням z_min. Цей багатокутник найвіддаленіший по Z-напряму. Позначимо його через P, а наступний за ним через Q. Сортування багатокутників P і Q відбувається в кілька етапів, в яких з'ясовується їх взаємне розташування.

1. Якщо крайні значення Z-координат усіх вершин P лежать далі, ніж Q, сортування тривіальне. P сортується пізніше.
2. Якщо многокутники, що порівнюються, не перекриваються крайніми значеннями в площині X, У, їх не потрібно сортувати, оскільки вони не перетинаються.
3. Якщо всі вершини P більш віддалені від глядача, ніж рівень в Q, то P упорядкований.
4. Якщо всі вершини Q до глядача ближче, ніж на рівні P, то P упорядкований.
5. Якщо X, Y значення P і Q перетинаються, то їх не потрібно сортувати.
6. Якщо досі немає сортування і не вдалося циклічно перекрити многокутники, то у цьому випадку, вони повинні бути виділені і сортування буде продовжене з нециклічних частин. Поділ відбувається на одному з многокутників на розрізаній кромці з іншого многокутника.

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

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

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

Джерела

• Д. Роджерс. Алгоритмические основы машинной графики. — Москва : Мир, 1989. — С. 331. — ISBN 5-03-000476-9.(рос.)
• Sutherland, Ivan E.; Sproull, Robert F.; Schumacker, Robert A. (1974), A characterization of ten hidden-surface algorithms, Computing Surveys, 6 (1): 1—55, doi:10.1145/356625.356626(англ.)
• Newell, M. E.; Newell, R. G.; Sancha, T. L. (1972), A new approach to the shaded picture problem, Proc. ACM National Conference, с. 443—450(англ.)