Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Алгоритм Сазерленда-Коена відсікання прямокутною областю

ВІДСІКАННЯ (КЛіпування) ГЕОМЕТРИЧНИХ ПРИМІТИВІВ

ЛЕКЦІЯ 7

Алгоритм розподілу відрізка навпіл. Коди Сазерланда - Коэна. Кліпування багатокутників. Штрихование багатокутної області. Перехід до тривимірного кліпування пірамідою видимості

 

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

Розглянемо плоску сцену, що складається з відрізків різної довжини й напрямків, у якій треба виділити частину, що перебуває усередині прямокутника. Прямокутник заданий списком ребер: t<op>, b<ottom>, l<eft>, r<ight>, відрізки також задаються координатами кінцевих крапок. Область, що відтинається вікном (з урахуванням його границі), складається із крапок , що задовольняють співвідношенням

(7.1)

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

 

Рис. 7.1. Коди Сазерленда-Коена для областей

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

1. праворуч від ребра ;

2. ліворуч від ребра ;

3. знизу від ребра ;

4. зверху від ребра .

У всіх інших випадках відрізок може (але не зобов'язаний) перетинати прямокутне вікно.

Для виконання аналізу повної видимості або невидимості відрізка А.Сазерленд і Д.Коен запропонували наступний алгоритм. Прямі, яким належать ребра прямокутника, розбивають площина на дев'ять областей, кожної з яких привласнюється чотирьохразрядний код. Кожний біт цього коду "відповідає" за одну із прямих: 1-й (старший) біт - за пряму , 2-й - за пряму , 3-й - за , 4-й - за . Якщо в коді області який-небудь біт установлений в 1, то це означає, що вона відділена від вікна відповідної прямої. Схема ідентифікації областей наведена на мал. 7.1.

Кінцевим крапкам відрізків сцени тепер можна привласнити коди залежно від розташування крапок. Ясно, що якщо коди обох кінців відрізка дорівнюють нулю, то відрізок повністю лежить усередині вікна. Для подальшого аналізу скористаємося операцією логічного множення кодів (поразрядне логічне "И"). Тоді таблиця істинності для кодів, відповідно до схеми на мал. 7.1, буде виглядати в такий спосіб:

Таблиця 7.1. Значення істинності для логічного множення кодів областей
 
T F F F T T F F
F T F F F F T T
F F T F T F T F
F F F T F T F T
T F T F T T T F
T F F T T T F T
F T T F T F T T
F T F T F T T T

Із зіставлення таблиці з малюнком видно, що якщо добуток кодів кінців відрізка приймає значення T<rue>, те відрізок цілком лежить по одну сторону якоїсь із прямих, причому зовнішню сторону стосовно вікна, отже, він повністю невидимий. У всіх інших випадках відрізок може частково лежати усередині вікна, тому для визначення їхньої видимої частини треба вирішувати завдання про перетинання відрізків з ребрами вікна. При цьому бажано по можливості скоротити число пар, що перебираються, " відрізок-ребро".

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

 

Рис. 7.2. Блок-схема алгоритму Сазерленда-Коэна

У блок-схемі використовуються наступні угоди й позначення:

- вхідними даними є крапки , масив координат вікна ;

- на виході одержуємо нові кінцеві крапки , а також значення змінної IsVisible (0 - відрізок видимий);

- використовуються наступні допоміжні функції:

GetCode(r) - визначення коду крапки;

Intersec0(r1,l) - пошук перетинання відрізка зі сторонами вікна за умови, що обидві крапки лежать поза вікном; якщо перетинання ні, установлює змінну IsVisible в 0;

Intersec(r1,l) - пошук перетинання відрізка зі сторонами вікна за умови, що крапка r1 лежить у вікні;

C1, C2 - коди крапок r1, r2.

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

або в координатному виді

Спробуємо визначити крапку перетинання відрізка з верхньою границею вікна. Оскільки ця границя описується співвідношеннями

та умова перетинання з нею кліпованого відрізка виглядає в такий спосіб:

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

Цей алгоритм реалізований у вигляді функції Intersec, блок-схема якої наведена на мал. 7.3.

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

Потім послідовно розглядаються чотири випадки розташування крапки відносно прямих, що обмежують вікно. Якщо в якімсь із варіантів буде знайдена крапка перетинання, то аналіз припиняється, крапка заміняється новою крапкою й викликається функція Intersec. У випадку ж, коли всі чотири варіанти не дали позитивного результату, змінної IsVisible привласнюється значення 0. Алгоритм реалізується функцією Intersec0 (блок-схема на мал. 7.5).

Запропонована реалізація алгоритму відсікання не є єдиною у своєму роді. Існують і інші підходи, зокрема використання методу розподілу відрізка навпіл для пошуку крапок перетинання й виявлення видимої частини відрізка. Такий варіант алгоритму був запропонований Сазерлендом і Спрулом для апаратної реалізації, але він може бути реалізований і на програмному рівні, хоча при цьому ефективність його буде нижче, ніж у попередні. У ньому немає прямого обчислення координат нової крапки по явних алгебраїчних співвідношеннях. Пошук здійснюється ітераційним методом, у якому на кожному кроці для відрізка, "підозрюваного" у частковій видимості, перебуває його середня крапка, визначається її код, потім із двох відрізків залишаються або обоє (якщо вони обоє не виявляться повністю невидимими), або тільки один, після чого операції тривають із новими відрізками. Ситуація, коли подальшому дробленню піддаються відразу два знову отриманих відрізки, може виникнути тільки на першому ітераційному кроці в тих випадках, коли вихідний відрізок має дві крапки перетинання із границями вікна. На наступних ітераційних кроках кількість аналізованих відрізків уже не буде збільшуватися. Процес триває доти, поки довжина чергового відрізка не стане менше наперед заданій точності. Після цього знайдена крапка перевіряється на предмет перетинання зі стороною вікна. На мал. 7.6 наведені три варіанти відрізків, попередній аналіз яких не класифікує їх як повністю невидимі, і показаний перший ітераційний крок. Відрізок a після першого розподілу дає два частково видимих відрізки, після чого шукаються дві крапки перетинання. В інших випадках залишається лише один із двох відрізків, причому у випадку відрізка c крапка перетинання зі стороною вікна відсутній, тобто виявляється повна невидимість відрізка. По суті справи загальний алгоритм, показана на мал. 7.3, зберігається, змінюється лише метод пошуку крапки перетинання.

 

Рис. 7.3. Блок-схема функції Intersec

 

Рис. 7.4. Відрізки паралельні сторонам вікна

 

Рис. 7.5. Блок-схема функції Intrsec0

 

Рис. 7.6. Довільне розташування відрізків

<== предыдущая лекция | следующая лекция ==>
Побудова шляхом стиску окружності | Відсікання опуклим багатокутником
Поделиться с друзьями:


Дата добавления: 2014-01-07; Просмотров: 720; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.033 сек.