Алгоритми порядкового сканування для криволінійних поверхонь

Ідея порядкового сканування, запропонована в 1967 р. Уайли, Ромни, Эвансом і Эрдалом, полягала в тім, що сцена обробляється в порядку проходження сканирующей прямій. В об'єктному просторі це відповідає проведенню січної площини, перпендикулярної простору зображення. Строго говорячи, алгоритм працює саме в просторі зображення, відшукуючи крапки перетинання сканирующей прямій з ребрами багатокутників, що становлять картину (для випадку зображення багатогранників). Але при перетинанні чергового елемента малюнка виконується аналіз глибини отриманої крапки й порівняння її із глибиною інших крапок на сканирующей площини. У деяких випадках можна побудувати список ребер, упорядкований по глибині, але найчастіше це неможливо виконати коректно. Тому сканування сполучать із іншими методами.

Один з таких методів ми вже розглядали - метод Z-Буфера, у якому буфер инициализируется заново для кожної сканирующей рядка. Інший метод називають интервальным алгоритмом порядкового сканування. У ньому сканирующая рядок розбивається проекціями крапок перетинання ребер багатокутників на інтервали, потім у кожному з інтервалів вибираються видимі відрізки. У цій ситуації їх уже можна відсортувати по глибині. Ми зупинимося ледве докладніше на методі порядкового сканування для криволінійних поверхонь.

В описі методу пріоритетів поверхня задавалася у вигляді функції двох змінних, тут ми будемо задавати поверхню параметричними рівняннями:

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

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

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