Алгоритм Вейлера-Азертона

Вейлер і Азертон спробували оптимізувати алгоритм Варнока відносно числа виконуваних розбивок, перейшовши від прямокутних розбивок до розбивок уздовж границь багатокутників (1977). Для цього вони використовували ними ж розроблений алгоритм відсікання багатокутників. Алгоритм працює в об'єктному просторі, і результатом його роботи є багатокутники. У самому загальному виді він складається із чотирьох кроків.

1. Попереднє сортування по глибині.

2. Відсікання по границі найближчого до крапки спостереження багатокутника, називане сортуванням багатокутників на площині.

3. Видалення багатокутників, экранируемых більше близькими до крапки спостереження багатокутниками.

4. Якщо потрібно, то рекурсивна розбивка й нове сортування.

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

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

Цей алгоритм надалі був узагальнений Кэтмулом (1974) для зображення гладких бикубических поверхонь. Його підхід полягав у тім, що розбивці піддавалася поверхня. Коротко цей алгоритм можна описати так:

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

2. Визначити атрибути поверхні в цьому пикселе й зобразити його.

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

Дата добавления: 2014-01-07