Алгоритми розв'язання позиційних задач

Перетин кривих поперхонь площиною.

Якщо поверхня задана у прямокутних декартових координатах явною чи неявною формою, а січна площина — будь-яким визначни­ком, то взявши координати трьох неколінійних точок, що належать січній площині, обчислимо коефіцієнти А, В, С, D за фор­мулами (1.85) і дістанемо рівняння січної площини в неявній формі (1.83).

Визначимо тип системи, в якій січна площина є площиною рівня, а також обчислимо параметр відповідної системи спеціальних координат. У результаті матимемо рівняння січ­ної площини в параметричній формі. Підставивши здобуті вирази у рівняння поверхні зведемо його до рівняння з двома змінними u та v. Якщо це рівняння можна розв'язати відносно однієї із змінних, тобто знати функцію v = v(u), то, надаючи u значення і деяким кроком маємо відповідні значення. Оскільки uOv є прямокутною декартовою системою на січній площині, то лінія перетину, віднесена до цієї системи, визначається в натуральному вигляді. Що6 скласти її рівнян­ня у просторі, треба підставити відповідні значення u та v в параметричні рівняння січної площини. Приклад.

Нехай треба знайти рівняння лінії пере­тину центральної поверхні обертання дру­гого порядку (1.93) і площини, заданої трьома точками M₀(x₀, y₀, z₀), M₁ (x₁, y₀, z₁), M₂ (x₂, y₂, z₂). Застосування формулу (1.85) дістанемо: А¹0, В¹0, С¹0, D¹0), знаходимо

                  (1.124)

Підставивши ці вирази дістанемо пара­метричні рівняння січної площини:

                            (1.125)

Тепер підставимо вирази (1.125) у рів­няння поверхні (1.93). У результаті мати­мемо

(1.126)

Це рівняння другого ступеня відносно  u та v, тобто його можна розв'язати відносно будь-якої з цих змінних.

Натуральний вигляд лінії перетину знай­демо побудовою графіка функції (1.126) за її рівнянням у системі uОv. Масиви коор­динат u_і, v_і, що визначаються в процесі по­будови, підставимо в параметричні рівнян­ня січної площини (1.125). Дістанемо про­сторові координати х_і у_і z_і, точок, які ви­значають лінію перетину. Наведемо при­клади програмної реалізації цього алгорит­му для двох поверхонь, що перетинаються площиною.

На рис. 23.1 наведено в ізометричній проекції поверхню еліпсоїда обертання за функцією (1,93) при а = 3, с = 5, р = 1, q = 1, що перетинаються площиною [див. рівняння (1.85)] при А = 1, В = 3, С = 16, D = -16.

На рис. 23.2 зображено в ізометричній проекції поверхню однопорожнинного гіперболоїда, що перетинається тією самою січною площиною. Порівняно з поперед­німи вхідні дані відрізняються тільки зна­ченням р, яке в цьому випадку набуває зна­чення -1.

Застосуємо наведений алгоритм для по­будови лінії перетину прямої призми та

 

площини. Нехай січна площина має такі коефіцієнти A, B, C, D при яких викону­ються рівності (1.124) і (1.125). Позначимо  і підстави­мо вирази (1.124) у рівняння (1.85), що при значеннях t згідно з рівнянням (1.119) є рівнянням граней призми, В результаті ма­тимемо

.                      (1.126а)

Це є рівнянням лінії перетину і рані призми із січною площиною у системі uОv на січні із площині. Підставляючи замість u його значення з рівняння (1.120), знайдемо коорди­нати u_і та v_і, точок перетину ребер призми із січною площиною. Нагадаємо, що за­мість t треба підставляти у рівняння (1.126а) послідовно значення з формули (1.119).

Масиви просторових координати x_і, y_і, z_і , вершин шуканої лінії перетину знайдемо підстановкою u_і та v_і, у рівняння (1.125).

Приклади програмної реалізації наведе­ного алгоритму показано на рис.1.14-1.16. В ізометричній проекції подано правильну дванадцятигранну призму, висота якої 12 см, ра­діус описаного циліндра 5см, а кутовий параметр однієї з вершин нижньої основи становить 0,13 рад. ІІризму перетинає про­щина

Використовуючи замість (1.85) рівняння сім’ї площин (1,86), матимемо алгоритм по­будови лінії перетину правильної піраміди та площини. На рис.1.117 подано ізометричну проекцію правильної дванадцятигранної піраміди, висота якої 12 см, кут між бічною гранню і ви­сотою 0,35 рад, а кутовий параметр основи вершин основи становить 0.26 рад. Пірамі­ду перетинає площина

.

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

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

Площинний алгоритм. Позначимо фун­кціональний параметр рівняння лінії через s. Нехай розв'язок лежить в інтервалі s1<s<s2. Визначимо координати x, y, z точ­ки М, що відповідає значенню

.                                                (1.127)

Об­числимо значення спеціальних координат u, v, t у системі, до якої віднесено поверхню. Підставляючи значення t у внутрішнє рівняння поверхні, дістанемо ріння лінії рівня t=const цієї поверхні. Скористав­шись формулами та враховуючи, що роль x і у відігра­ють u і v відповідно, визначимо належність точки М до внутрішності чи зовнішності лінії рівня t = соnst заданої поверхні.

Якщо точка М належить до зовнішності лінії рівня, то функціональний параметр наступної довільної точки М визначаємо за формулою (1.127). надаючи s1 значення s_M. Якщо точка M належить до внутрішності, то значення s_M надаємо s2. Ітераційний процес продовжуємо доти, доки виконується умова , де e визначає наперед задану точність.

Значення функціонального параметра довільної точки, при якому виконується ця умова, треба підставити в рівняння лінії, щоб дістати просторові координаті x, y, z шуканої точки перетину.

Рис.1.117

Зазначимо, що одна й та сама лінія може перетинати поверхню більше, ніж в одній точці. При цьому треба позначити той функ­ціональний параметр s_M довільної точки М, при якому вона вперше опинилася всере­дині поверхні, а після знаходження розв'яз­ку для однієї точки перетину за наведеним алгоритмом слід повернутися до цього зна­чення та направити ітераційній процес у протилежний бік.

Просторовий алгоритм. Для поверхонь другого порядку (1.119). (1.122) при роз­гляді питання про належність довільної точки до внутрішності чи зовнішності поверхні не обов'язково переходити до рів­няння лінії ріння цієї поверхні. Досить під­ставити координати x, y, z довільної точки в рівняння (1.119) або (1.122). Якщо знак "=" - змінюється на знак  “>”, то довільна точка належить до зовнішності, якщо на знак " < ", то до внутрішності поверхні.

Просторовий алгоритм більше нічим не відрізняється від площинного.

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

Геометричну модель відображення лінії чи поверхні засобами комп'ютерної графі­ки дістають методом проекцювання та спо­лучення точок, які лежать на лінії, впоряд­кованих відповідно із зростанням або спа­данням значення функціонального пара­метра. Вхідні дані у вигляді рівняння лінії та інтервалу значень функціонального параметра дають змогу обчислити координа­ти x, y, z послідовності точок.

Щодо візуалізації поверхні, то проекції відтворюють деякі характерні для поверхні лінії: ребра багатогранників, лінії, об­відну проекції кривої поверхні, межі відсіку поверхні. Ефективний спосіб візуалізації кривої поверхні полягає в попередньому визначенні на поверхні сім'ї або сітки координатних ліній та відображенні на проекції видимих відрізків (рис.1.17 …рис.1.22) та відповідно для прямокутних ізо­метрії, диметрії та косокутної диметрії.

Точкове відображення простору на фрон­тальну площину проекцій визначено формулами    

,                                      (1.128)

а на горизонтальну площину проекцій — формулами

.                                   (1.129)

Визначення лінії, обвідної проекції по­верхні. Нехай поверхня задана в парамет­ричній формі:

                         (1.130)

 

                                                                    

                              

               

                                                                         

 

Як було показано, явна форма задання поверхні є окремим випадком задання у формі (1.130). До форми (1.130) приводить також задання поверхні внутрішнім рівнян­ням у спеціальних координатах.

Застосовуючи формули відповідного точкового перетворення простору при проекціюванні, можна записати

.                                    (1.131)

де х, у -- прямокутні декартові координа­ти проекцій точок; f,j — функції, що реалізують ланцюжок —одну з функцій -- (1.128), (1.129).

Проаналізувавши вирази (1.131), дійде­мо висновку, що ці рівняння відповідають

рінянням двох сімей ліній u=const, t=const Кожна сім'я залежить від одного параметра. Як відомо, такі сім'ї мають об­відну, рівняння якої

.                                 (1.132)    

Обвідна (1.132) поділяє точки на по­верхні (1.130) на два класи, що визначають­ся знаком нерівності, в яку перетворюєть­ся ліва частина (1.132) після підстановки внутрішніх координат u, t довільної точки на поверхні. Отже, в результаті підстановки внутрішніх координат u, t точки на поверхні ліву частину (1.132) дістанемо один з трьох випадків:

І=0,                                                    (1.133)

коли точка належить обвідній. За цієї умо­ви можна скласти рівняння обвідної і по­будувати її:

І>0,                                                   (1.134)

коли точка є видимою на проекції;

І<0,                                                  (1.135)

коли точка невидима на проекції.

Випадок (1.134) або (1.135) завжди мож­на дістати множенням лівої частини (1.132) на -1.

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

У табл. 1.1 наведено приклади застосу­вання форм задання та алгоритму визна­чення видимості найпоширеніших поверхонь.

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

Табл.1.2 Поверхні в ортогональних проекціях та в ізометрії ізометрії

Поверхня	№ Рис.	Внунтрішнє рівняння	Вираз І в рівнянні (1.32)
Циліндр		U=0
Конус		u=0
Елыпсоїд
Гелікоїдальний циліндр
Циклічна G-поверхня

Щодо побудови проекції обвидної, то в багатьох випадках це можна зробити, роз­в'язуючи рівняння (1.123) відносно однієї з дих змінних. Так для циліндра та конуса

(див. табл. 1.1) обидва розв'язки не залежать від другої змінної, для центральних поверхонь другого порядку рівняння (1.123) є квадратним відносно лінійної змінної. Розв'язки цього рівняння використано також для каналової поверхні, різьбленої поверхні Монжа, катеноїда, псевдосфери.

Для гранних поверхонь алгоритм визна­чення видимості полягає в порівнянні знаків лівої частини (1.123) для суміжних граней.

Якщо

І_і>0, І_і+1 > 0,                                              (1.136)

то ребро, по якому перегинаються ці грані, видиме;

якщо

 І_і І_і+1 < 0,                                                 (1.137)

то ребро контурне;

якщо

І_і<0, І_і+1 < 0,                                             (1.138)

то ребро невидиме.

Моделювання розгорток

До розгортних належать такі поверхні:

багатогранники, циліндри, конуси та тор­си. Задача розгортування полягає в знахо­дженні функцій

,                               (1.139)

або з урахуванням залежності прямокутних декартових координат точки на циліндрі чи конусі від відповідних спеціальних координат, в яких ці поверхні мають рівняння u=0,

                                    (1.140)

У формулах (1.139) та (1.140) x_p, y_p -- декартові прямокутні координати на пло­щині розгортки, x, y, z — декартові прямокутні координати точки, що належать розгортній поверхні.

Циліндр. Для циліндра, радіус основи якого r формули (1.140) мають вигляд

                                       (1,141)

Правильна призма. Нехай правильна n-гранна призма описана навколо циліндра радіуса r і має висоту h. Кутовий параметр однієї з вершин відносно площини визначимо через t_H. Апофеми бічних гра­ней призми мають узагальнену циліндрічну координату

.                       (1.142)

Знайдемо  а з умови

                                        (1.143)

дістанемо таке значення j = 1, при якому ця умова виконується.

     Позначимо

                                           (1.144)

Тоді координата u точки на поверхні призми в узагальненій ціліндричній системі виражається рівністю

                                   (1.145)

                           

Рис.1.24

 

 

                         

	Рис.1.23		Рис.1.25

    

 

Рис.1.26

                     

 

                       

Рис.1.27

Рис.1.28

            

 

 

Формули (1.141) мають вигляд

,                                           (1.146)

де v = z.

Нагадаємо, що координати точки x, y, z на поверхні призми вважаємо заданими.

Конус. У гіперболічних координатах рівнянням конуса є u = 0. Формули (1.140) набувають вигляду

                   (1.147)

де a — кут між віссю та твірною конуса.

Правильна піраміда. Правильну піраміду віднесемо до вписаного в неї конуса. Кут a між його твірною та віссю входить до визначника піраміди. Як і для призми, t_H — кутовий параметр однієї з вер­шин основи піраміди відносно площини х0z. Обчислимо t_i за формулою (1.142), та р — за формулою (1.144), b та j — за форму­лою (1.143). Потім знаходимо:

Функції (1.140) мають вигляд

.                   (1.148)

Па рис.1.23,1.28, наведено приклади про­грамної реалізації алгоритму визначення лінії взаємного перетину поверхонь та ал­горитмів моделювання розгорток, На рис. 1.23 зображено конус і циліндр, які пере­тинаються. На рис.1.24 і рис. 1.26 пода­но розгортки конуса й циліндра відповід­но з визначенням на розгортці лінії взаєм­ного перетину.

На рис. 1.27 показано два циліндри, які перетинаються, а на рис. 1.25 і рис. 1.28 — розгортки поверхонь циліндра з горизон­тальною та вертикальною осями відповідно з визначенням на розгортці лінії перетину.