Алгоритм Варнока

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

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

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

Конкретна реалізація алгоритму Варнока залежить від методу розбивки вікна й від деталей критерію, використовуваного для того, щоб вирішити, чи є вміст вікна досить простим. В оригінальній версії алгоритму кожне вікно розбивалося на чотири однакових подокна. Багатокутник, що входить у зображувану сцену, стосовно вікна будемо називати (мал. 8.3)

- зовнішнім, якщо він цілком перебуває поза вікном;

- внутрішнім, якщо він цілком розташований усередині вікна;

- що перетинає, якщо він перетинає границю вікна;

- що охоплює, якщо вікно цілком розташоване всередині нього.

Рис. 8.3. Варіанти розташування багатокутника стосовно вікна

Тепер можна в самому загальному виді описати алгоритм.

Для кожного вікна:

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

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

3. Якщо тільки один багатокутник сцени має загальні крапки з вікном і є стосовно нього що перетинає, то вікно заповнюється фоновим кольором, а частина багатокутника, що належить вікну, заповнюється кольором багатокутника.

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

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

6. У противному випадку виробляється нова розбивка вікна.

Кроки 1-4 розглядають ситуацію перетинання вікна тільки з одним багатокутником. Вони використовуються для скорочення числа подразбиений. Крок 5 вирішує завдання видалення невидимих поверхонь. Багатокутник, що перебуває ближче всіх до крапки спостереження, екранує всі інші.

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

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