ікселів. Теоретично трудомісткість алгоритмів, що працюють в об'єктному просторі, менше трудомісткості алгоритмів, що працюють у просторі зображення, при n lt; N. Оскільки N зазвичай одно (512) 2, то теоретично більшість алгоритмів слід реалізовувати в об'єктному просторі. Однак на практиці це не так. Справа в тому, що алгоритми, працюють у просторі зображення, ефективніші бо них легше скористатися перевагою когерентності при растрової реалізації.
1. Опис алгоритму видалення невидимих ??ліній і поверхонь алгоритмом плаваючого горизонту
1.1 Загальний алгоритм (Опис алгоритму)
Алгоритм плаваючого горизонту найчастіше за все використовується для видалення невидимих ??ліній тривимірного представлення функцій, що описують поверхню у вигляді:
F (x, у, z)=0.
Подібні функції виникають у багатьох додатках у математиці, техніці, природних науках та інших дисциплінах.
Запропоновано багато алгоритмів, котрі цей підхід. Оскільки в додатках переважно цікавляться описом поверхні, цей алгоритм зазвичай працює у просторі зображення. Головна ідея даного методу полягає у зведенні тривимірної задачі до двовимірної шляхом перетину вихідної поверхні послідовністю паралельних січних площин, мають постійні значення координат х, у або z.
На рис.10.2 наведено приклад, де зазначені паралельні площині визначаються постійними значеннями z. Функція F (x, у, z)=0 зводиться до послідовності кривих, що в кожній з цих паралельних площин, наприклад до послідовності
у=f (x, z) або х=g (у, z)
де z постійно на кожній із заданих паралельних площин.
Отже, поверхня тепер складається з послідовності кривих, що у кожної з цих площин, як показано на рис. 10.3. Тут передбачається, що отримане криві є однозначними функціями незалежних змінних. Якщо спроектувати отримані криві на площину z=0, як показано на рис.10.4, то відразу стає зрозуміла ідея алгоритму видалення невидимих ??ділянок вихідної поверхні. Алгоритм спочатку впорядковує площині z=const за зростанням відстані до них від точки спостереження. Потім для кожної площині, починаючи з найближчої до точки спостереження, будується крива, що у ній, т. Е. Для кожного значення координати x у просторі зображення визначається відповідне значення y. Алгоритм видалення невидимою лінії полягає в наступному:
Якщо поточної площині попри деякий заданому значенні x відповідне значення у на кривою більше значення y всім попередніх кривих при цьому значенні x, то поточна крива видимою у цій точці; в іншому випадку вона невидима.
Невидимі ділянки показані пунктиром на рис. 10.4. Реалізація даного алгоритму досить проста. Для зберігання максимальних значень y при кожному значенні x використовується масив, довжина якого дорівнює числу помітних точок (вирішенню) по осі x у просторі зображення. Значення, які у цьому масиві, є поточні значення горизонту raquo ;. Тому в міру малювання кожної чергової кривою цей горизонт спливає raquo ;. Фактично цей алгоритм видалення невидимих ??ліній працює щоразу з однією лінією. Алгоритм працює дуже добре до тих пір, поки якась чергова крива бракуватиме нижче найпершою зі кривих, як показано на рис. 10.5а.
Такі криві, природно, видимі і є нижню сторону вихідної поверхні, однак алгоритм буде вважати їх невидимими. Нижня сторона поверхні робиться видимої, якщо модифікувати цей алгоритм, включивши до нього нижній обрій, який опускають вниз по ходу роботи алгоритму. Це реалізується з допомогою другого масиву, довжина якого дорівнює числу помітних точок по осі x у просторі зображення. Цей масив містить найменші значення y для кожного значення x. Алгоритм тепер стає таким:
Якщо поточної площині попри деякий заданому значенні x відповідне значення y на кривою більше максимуму менше мінімуму по y всім попередніх кривих при цьому x, то поточна крива видимою. В іншому випадку вона невидима.
Отриманий результат показаний на ріс.10.5b.
У викладеному алгоритмі передбачається, що значення функції, тобто y, відомо для кожного значення x у просторі зображення. Однак якщо для кожного значення х можна вказати (обчислити) відповідне йому значення y, то неможливо підтримувати масиви верхнього й нижнього плаваючих горизонтів. У такому випадку використовується лінійна інтерполяція значень y між відомими значеннями для того, щоб заповнити масиви верхнього й нижнього плаваючих горизонтів, як показано на рис. 10.6. Якщо видимість кривою змінюється, то метод з такою простий інтерполяцією дасть коректного результату. Цей ефект проілюстрований рис. 10...
