Алгоритм Кіруса — Бека

Алгоритм Кіруса — Бека (англ. Cyrus — Beck) — алгоритм відсікання відрізків довільним опуклим багатокутником. Був запропонований як ефективніша заміна алгоритму Коена — Сазерленда, який виконує відсікання за кілька ітерацій.[1]

Опис алгоритму

Відрізки, що відсікаються представляються в параметричному вигляді:

де

p0, p1 — координати початку і кінця відрізка відповідно,
t — параметр.

Кожен відрізок, що відсікається, містить координати початку і кінця, а також два параметра tA та tB, що відповідають початку і кінцю відрізка. Для кожного відрізка, що відсікається P виконуються наступні дії:

  • Ребра багатокутника, що відсікає, обходяться проти годинникової стрілки. Для кожного ребра E обчислюється параметр tE, що описує перетин E з прямою, на якій лежить відрізок P. Обчислюється скалярний добуток вектора E та зовнішньої нормалі N, в залежності від знака якого виникає одна з наступних ситуацій:
    • E · N < 0 — відрізок P спрямований з внутрішньої на зовнішню сторону ребра E. У цьому випадку параметр tA замінюється на tE, якщо tE > tA.
    • E · N > 0 — відрізок P спрямований із зовнішньої на внутрішню сторону ребра E. У цьому випадку параметр tB замінюється на tE, якщо tE < tB.
    • E · N = 0 — відрізок P паралельний ребру E. Відрізок P відкидається як невидимий, якщо знаходиться праворуч від E.
  • Якщо tA tB, то задана параметрами tA та tB частина відрізка P видима. В іншому випадку відрізок P повністю невидимий.

Див. також

Примітки

Література

  • Mike Cyrus, Jay Beck. «Generalized two- and three-dimensional clipping». Computers & Graphics, 1978: 23-28.
  • James D. Foley. Computer graphics: principles and practice. Addison-Wesley Professional, 1996. p. 117.

Посилання


This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.