1. Znaczenie i wzajemne związki między terminami: przestrzeń urządzenia, przestrzeń operacyjna urządzenia, powierzchnia obrazowania, macierz adresowalna, jednostka rastru, krok kreślaka.

Przestrzeń urządzenia (obrazującego) to obszar zdefiniowany przez układ współrzędnych ograniczony pojemnością rejestrów pozycji x i y w urządzeniu graficznym - określony przez skończony zbiór punktów adresowalnych urządzenia wizualizującego.
Przestrzeń operacyjna to obszar w przestrzeni urządzenia, którego zawartość została odwzorowana na powierzchni obrazowania.
Powierzchnia obrazowania to nośnik w urządzeniu wizualizacyjnym na którym element kreślący obraz (rozjaśniający lub zaciemniający albo kolorujący piksel) tworzy obraz fizyczny (np. papier, film, ekran lampy elektronopromieniowej).
Macierz adresowalna - to macierz utworzona punktów adresowalnych, określająca wielkość obrazu, który można przesłać do generatora obrazu.
Wielkość przyrostu to odległość między dwoma sąsiednimi punktami adresowalnymi na powierzchni obrazowania (mierzona w [mm]), w wypadku monitora i drukarki graficznej używany jest termin jednostka rastru, a w wypadku kreślaka - krok kreślaka. Jednostka rastru – piksel w przypadku monitorów.

2. Znaczenie i związki między terminami: kadr obrazu, obcinanie, okrawanie, monitor rastrowy graficzny, częstotliwość odświeżania.

Kadr obrazu - wyróżniony obraz wystawiany z ciągu obrazów jakie mogą być przesłane do generatora obrazów w celu ich wygenerowani; jest to obraz powstający analogicznie do klatki w technice filmowej.
Obcinanie - polega na wyznaczaniu punktów i fragmentów odcinków leżących w prostokątnym obszarze o bokach równoległych do osi układu. „Wyznaczanie elementów rysunku leżących wewnątrz okna”
Okrawanie - może wystąpić w monitorze, który dopuszcza rysowanie obrazów większych od rozmiarów ekranu, a dotyczy reakcji na przekroczenie obszaru ekranu przez strumień elektronowy i oznacza automatyczne wygaszanie strumienia, gdy wychodzi poza ramy ekranu; przy braku wygaszania strumienia występują odbicia obrazu. „ograniczanie sceny renderowania do prostokąta, zdefiniowanego we współrzędnych ekranowych”
Monitor rastrowy graficzny - to monitor rastrowy wyposażony w bloki funkcjonalne do przetwarzania listy obrazowej.
Częstotliwość odświeżania to liczba cykli na sekundę, z jaką należy odświeżać obraz na monitorze, aby uzyskać wrażenie jego stabilności.

3. Znaczenie i wzajemne związki między terminami: język graficzny, bufor obrazu, generator obrazu, lista obrazowa, konturowe rozwinięcie obrazu, rastrowe rozwinięcie obrazu.

Język graficzny to język do programowania urządzeń graficznych; produktem wykonania programu graficznego jest (zapełniony) bufor obrazu.
Bufor obrazu to obszar w pamięci (zwykle pamięci komputera lub specjalnej pamięci sterownika danego urządzenia graficznego), w którym są przechowywane rozkazy graficzne lub dane obrazowe potrzebne do wygenerowania obrazu fizycznego (wystawionego na powierzchni obrazowania).
Generator obrazu to urządzenie elektroniczne przetwarzające zawartość bufora obrazu na obraz fizyczny.
Lista obrazowa - rozkazy graficzne i dane zawarte w buforze obrazu opisujące obraz fizyczny (program tworzenia obrazu fizycznego wyrażony w rozkazach urządzenia obrazującego).
Konturowe rozwinięcie obrazu - sposób kreślenia elementów obrazu zadanych przez program, gdzie ruch elementu kreślącego obraz jest analogiczny do przesunięć pióra kreślaka stołowego.
Rastrowe rozwinięcie obrazu - technika punkowego generowania lub zapisywania obrazu punkt po punkcie wzdłuż poziomych linii równoległych, radialnych lub spiralnych; jest wykorzystywana do generowania obrazu np. w odbiornikach telewizyjnych, monitorach komputerowych, urządzeniach radarowych itp.

4. Znaczenie i związki między terminami: konsola graficzna, generator wektorów, generator znaków, generator krzywych, drążek sterujący, manipulator kulowy, pióro świetlne, rysownica.

Konsola graficzna to zestaw sprzętowy składający się co najmniej z jednego graficznego urządzenia wyjściowego i zazwyczaj jednego lub większej liczby urządzeń wejściowych, takich jak klawiatura alfanumeryczna, klawisze funkcyjne lub graficzne urządzenia wejściowe wraz z odpowiednim oprogramowaniem.

Generator wektorów to układ elektroniczny (lub program), który generuje odcinki prostych na podstawie zadanych punktów skrajnych lub przyrostów wzdłuż osi układu współrzędnych; wyróżnia się generator o proporcjonalnym czasie, generator o stałym czasie, generator przyrostowy (który składa wektor z elementarnych odcinków linii siatki dyskretnej); sprzętowe generatory wektorów są stosowane zwykle w komputerowych urządzeniach wizualizacyjnych.
Generator znaków to układ elektroniczny (lub program), który na podstawie podanego kodu znaku generuje postać graficzną znaku; wyróżnia się różne rodzaje generatorów znaków, m.in.: generator mozaikowy i generator segmentowy.
Generator krzywych to pogram lub układ elektroniczny, który generuje krzywą na podstawie definiujących ją danych; generowanie to polega na wyznaczeniu węzłów siatki punktów (którą jest (zwykle powierzchnia obrazowania), leżących wzdłuż wejściowej krzywej, przy spełnieniu dodatkowego kryterium, np. zadany typ siatki, czy dopuszczalny błąd przybliżenia.
Manipulator kulowy - mechanoelektryczny przekształtnik z kulą, która ma co najmniej dwa stopnie swobody ruchu, służący do plasowania elementu obrazu na ekranie monitora ('trackball').
Manipulator ramieniowy - mechanoelektryczny przekształtnik z drążkiem mającym co najmniej dwa stopnie swobody ruchu służący do plasowania elementów obrazu na ekranie monitora ('joystick').
Pióro świetlne -urządzenie wskazujące kształtem przypominające zwykłe pióro podłączone do jednostki wizualizującej. Wskazująca końcówka pióra posiada światłoczuły element, który umieszczony przy ekranie wykrywa światło pozwalając komputerowi zlokalizować położenie kursora. Lokalizacja odbywa się na podstawie rejestrowania częstotliwości pracy monitora.
Rysownica - (zakładając, że chodzi tu o tablet) - urządzenie wskazujące służące przede wszystkim do rysowania elementów graficznych na komputerze. Składa się ze specjalnej podkładki oraz wskaźnika zwanego piórkiem (rysikiem), zwykle w kształcie długopisu. Ruch rysika po podkładce jest przenoszony do komputera jako informacja o bieżącym położeniu oraz o sile nacisku wskaźnika na tablet.

5. Definicja siatki generacyjnej, modułu siatki i jej rzędu spójności.

Siatka generacyjna - siatka składająca się ze skończonej liczby węzłów ułożonych prostopadle względem siebie w l wierszach i k kolumnach.

Rząd spójności siatki – liczba odcinków wychodzących z każdego węzła siatki do węzłów sąsiadujących z nim bezpośrednio.

Moduł siatki – wielkość l*k określająca rozmiar siatki generacyjnej oraz jej rozdzielczość.

6. Podaj idee generowania linii (prostych, krzywych) na siatkach generacyjnych. Z czego wynika konieczność generowania linii na siatkach generacyjnych?

Polega na znalezieniu węzłów siatki lezących na trasie pomiędzy punktem początkowym i końcowym. Możemy wybierać je stosując cztero- lub ośmiokierunkowy wybór (zależny od stopnia spójności siatki). Wybieramy ten piksel, którego środek leży najbliżej linii odcinka. Konieczność generowania linii na siatkach generacyjnych wynika z faktu, iż takie generowanie nie powoduje tworzenia się błędów systematycznych oraz kumulowania się błędów.

7. Zapis we współrzędnych jednorodnych operacji na punkcie: przesunięcia, skalowania, obrotu wokół punktu P(0; 0) oraz P(xo; yo).

x y - współrzędne bazowe punktu
x' y' - współrzędne punktu po przekształceniu,
tx, ty - wartości przesunięcia wg osi x i y
sx, sy - współczynniki skalowania odpowiednio współrzędnej x i y
φ - kąt obrotu

8. Zdefiniuj okno i widok oraz oknowanie i obcinanie; podaj co to są współrzędne znormalizowane i do czego one służą.

Okno - prostokątny obszar w przestrzeni danych.
Widok - prostokątny obszar na urządzeniu graficznym.
Oknowanie - powoduje odwzorowanie obszaru określonego we współrzędnych zadania (danych) na obszar określony we współrzędnych urządzenia wizualizacyjnego.
Obcinanie - polega na wyznaczeniu elementów rysunku leżących wewnątrz okna.
Współrzędne znormalizowane Często przejście od współrzędnych rzeczywistych do współrzędnych danego urządzenia graficznego jest wykonywane dwustopniowo. Najpierw przechodzi do współrzędnych znormalizowanych, to znaczy do kwadratu [0,1]x[0,1], a stąd do współrzędnych urządzenia.

9. Zdefiniuj operacje jednokładności i powinowactwa prostokątnego oraz omów ich podobieństwa, różnice i ich szczególne przypadki.

Jednokładnością o środku S =(x0,y0) i skali k≠0 nazywamy przekształcenie płaszczyzny, w którym obrazem punktu P=(x,y) jest taki punkt P’=(x’,y’), ze SP’ = kSP. Dla k = -1 przekształcenie takie jest symetrią o środku S.
Powinowactwo prostokątne: Niech osia powinowactwa będzie prosta o równaniu ax+by+c=0 i stosunek powinowactwa niech wynosi k≠0. Punkt P=(x,y) odwzorowujemy więc w taki punkt P’=(x’,y’), ze QP’ = kQP, gdzie Q jest rzutem prostokątnym punktu P na oś powinowactwa ax +by +c=0. Dla k=-1 powinowactwo prostokątne staje się symetrią osiową.

10. Podaj ideę algorytmu Cohena-Sutherlanda obcinania odcinka do prostokątnego okna i jego trzy pierwsze kroki; podaj w jakich współrzędnych działa ten algorytm i dlaczego?

Algorytm opiera się na przypisaniu każdemu końcowi odcinka czterobitowego kodu określającego położenie tego punktu względem prostokątnego okna. Kod(P)=b4 b3 b2 b1
b1=1, gdy P leży na lewo od okna,
b2=1, gdy P leży na prawo od okna,
b3=1, gdy P leży na poniżej okna,
b4=1, gdy P leży na powyżej okna,
a w przeciwnym razie bity kodu mają wartość 0. Jeżeli odcinek leży w wewnątrz okna to krańcowe punkty odcinka mają kod 0000. Proces obcinania odcinka przebiega następująco:
- koniec odcinka z prostą o kodzie niezerowym jest zastępowany punktem przecięcia badanego odcinka z prostą zawierającą jeden z boków okna. W ten sposób odrzuca się fragment odcinka leżący na zewnątrz okna.

- następnie pozostała część odcinka jest obcinana prostymi zawierającymi inne boki.
- postępowanie kontynuuje się do momentu, gdy cały odcinek może być pominięty lub gdy znajdziemy jego fragment leżący wewnątrz okna.

11. Podaj definicje wielokątów: dowolnego, zwykłego, monotonicznego, wklęsłego i wypukłego; podaj nazwy i koncepcje działania znanych ci algorytmów określania położenia punktu względem wielokąta.

Wielokąt:
dowolny - taki, w którym boki przecinają się wzajemnie.
zwykły - taki, który nie zawiera przecinających się boków.
monotoniczny - taki, w którym występuje szczególny rodzaj uporządkowania (uporz. monotoniczne) wierzchołków.
wypukły - taki, w którym wewnętrzne kąty są mniejsze niż 180°
wklęsły – taki, w którym istnieje co najmniej jeden kąt większy niż 180°.
Test parzystości - przeprowadzamy przez punkt P(x0,y0) dowolną półprostą l, np. równoległą do osi x;
- szukamy liczby lp przecięć półprostej l z bokami wielokąta W;
- jeśli liczba lp jest parzysta, to P(x0,y0) leży na zewnątrz wielokąta W, jeśli nieparzysta - wewnątrz.
Test nie obejmuje przypadków szczególnych:

1. Przechodzenie prostej l przez wierzchołek wielokąta.
2. Zawieranie przez półprostą l boku wielokąta.
Test kątowy W tej metodzie sprawdzamy położenie punktu P względem wielokąta W poprzez obliczenie sumy kątów między półprostymi poprowadzonymi z punktu P przez wierzchołki Pi wielokąta.
Załóżmy uporządkowanie numeracji wierzchołków odwrotnie do ruchu wskazówek zegara i niech αi oznacza kąt między wierzchołkami PPi a PPi+1(Pn+1=P1). Wówczas:
- punkt P leży wewnątrz wielokąta wtedy i tylko wtedy, gdy suma wszystkich kątów αi wynosi 360°.
- dla punktów na zewnątrz wielokąta suma wszystkich kątów αi wynosi 0°.

12. Sformułuj zadanie i ogólne warunki trójkątowania wielokąta, warunki trójkątowania naturalnego oraz podaj ideę trójkątowania wielokąta monotonicznego.

Triangulacja wielokątów jest przeprowadzana w celu uproszczenia kształtów powierzchni, przez co ułatwia się rozwiązywanie zadań typu: wypełnianie obszarów, określenie zasłaniania, oświetlenia i przecinania się obiektów 3W.
Zadanie triangulacji formułuje się jako podział wielokąta zwykłego na sumę nie nakładających się na siebie trójkątów, których wierzchołkami mogą być tylko wierzchołki danego wielokąta.
Ogólne warunki:
1. Liczba trójkątów powinna być jak najmniejsza (tj. równa n-2 dla n-kąta)
2. trójkąty nie mogą się nakładać
3. ich wierzchołkami mogą być tylko wierzchołki wielokąta

W praktyce polega to na przeglądaniu odpowiednio uporządkowanych wierzchołków i tam, gdzie będzie to możliwe poprowadzenie przez kolejny wierzchołek przekątnej. Przekątna odetnie trójkąt pozostawiając prostszy wielokąt do dalszej triangulacji.

13. Podaj definicje: zbioru wypukłego punktów i powłoki wypukłej oraz wymień (3) główne kroki algorytmu Grahama wyznaczania powłoki wypukłej.

Zbiór Z nazywamy wypukłym, jeśli zawiera wszystkie odcinki, których końcami są dowolne punkty ze zbioru Z. Powłoka wypukła zbioru punktów to najmniejszy zbiór wypukły (w sensie zawierania), do którego należą te punkty.
Z tych definicji wynika, że powłoka wypukła zbioru jest wielokątem.
Algorytm Grahama wyznaczania powłoki wypukłej n punktów:
1. Spośród wszystkich danych Pi=(xi,yi), i=1,2,…,n wyszukujemy punkt Pi1=(xi1,yi1) o najmniejszej współrzędnej x.
2. Porządkujemy punkty zgodnie z malejącymi wartościami kątów αi, obliczając: tg αi = (xi–xi1)/(yi-yi1) Niech i1,i2,…in będzie nowym uporządkowaniem.
3.Tworzymy listę Pl1,Pl2,…,Plk wierzchołków wielokąta będącego powłoką wypukłą zbioru danych punktów następująco:
We wstępnym kroku przyjmujemy l1 = i1, l2 = i2, l3 = i3 i podstawiamy k=3,
Dalej dla j = 4,5,…,n:
- (*) jeśli para wektorów Plk-1Plk, PlkPlj jest ujemnie zorientowana, to usuwamy z listy wierzchołek Plk, zmniejszamy k o 1 i wracamy do (*)
- (**) w przeciwnym wypadku dopisujemy Plj do listy, czyli zwiększamy k o 1 i podstawiamy lk = ij,

14. Podaj ideę algorytmu Sutherlanda-Hodgmana obcinania wielokąta do prostokątnego okna.

Oznaczmy wielokąt W ciągiem wierzchołków Pi(i=1,2,...,n) uporządkowanych dodatnio (przeciwnie do ruchu wsk. zeg.). Zatem, jego krawędziami są odcinki PiPi+1 (Pi+1=Pi).
Teraz porównujemy wierzchołki z bokami okna i tworzymy z nich nowy ciąg określający wielokąt obcięty danym bokiem.
Te wierzchołki, które leżą po wewnętrznej stronie krawędzi okna niech będą elementami nowego ciągu, a wierzchołki z zewnątrz są odrzucane. Nowy ciąg wierzchołków porównujemy z następnymi bokami okna w ten sam sposób jak z pierwszym bokiem okna.

15. Podaj ideę algorytmu Shamosa-Hoeya wyznaczenia części wspólnej wielokątów wypukłych.

Dane wielokąty dzielimy po przez pionowe linie, które przechodzą prze wierzchołki wielokątów. Gdzie jest tworzone O(n+m) pasków, a zawarte w nich części wielokątów to trapezy lub trójkąty. Zadanie sprowadza się do uzyskania części wspólnej, gdzie kosztem tej operacji jest rzędu n+m działań.

16. Podaj definicję iloczynu skalarnego wektorów w1 = [x1; y1; z1] i w2 = [x2; y2; z2]

17. Podaj definicję iloczynu wektorowego wektorów w1 i w2 oraz wzór na długość wektora w =[x,y,z].

Iloczyn wektorowy wektorów
w1 = [x1,y1,z1] i w2 = [x2,y2,z2]
jest wektorem, jego składowe wyznacza się następująco

18. Wyprowadź równanie płaszczyzny przechodzącej przez 3 punkty: P1, P2, P3.

19. Wyprowadź równanie na punkt przecięcia prostej z płaszczyzną.

20. Wyprowadź równanie płaszczyzny w oparciu o jej wektor normalny n = [xn,yn,zn] i punkt P0 = (x0,y0,z0), przez który ona przechodzi.

21. Wyprowadź macierzowe równanie płaszczyzny przechodzącej przez 3 punkty P1, P2, P3.

Niech P1 = [x1,y1,z1], P2 = [x2,y2,z2], P3 = [x3,y3,z3].
Wtedy macierzowe równanie płaszczyzny przechodzącej przez P1,P2 i P3 ma postać:

22. Wyprowadź równanie krawędzi przecinania się dwóch płaszczyzn.

23. Podaj macierze przesunięcia, skalowania i obrotu o kąt fi wokół osi Z punktu w przestrzeni R3.

tx, ty, tz - wartości przesunięcia wg osi x, y i z
sx, sy, sz - współczynniki skalowania odpowiednio współrzędnej x, y i z
φ - kąt obrotu

24. Zdefiniuj przekształcenie 3-punktowe. Do czego ono służy?

Dane są dwie trojki punktów P1, P2, P3 i Q1, Q2, Q3.
Szukamy takiej izometrii która:
- odwzorowuje punkt P1 w Q1
- kierunek P=P2-P1 przekształca w kierunek Q=Q2-Q1,
- transformuje płaszczyznę przechodzącą przez P1, P2, P3 na płaszczyznę wyznaczona punktami Q1, Q2, Q3.
Zakłada się ze P1,P2,P3 nie są współliniowe i podobne Q1,Q2,Q3.
Zastosowanie - szczególnie przydatne przy budowaniu scen trójwymiarowych, gdy jeden obiekt chcemy ’dokleić’ do drugiego

25. Zdefiniuj i podaj własności rzutowania środkowego

Przy rzutowaniu na płaszczyznę Π obrazem punktu P jest punkt P’ przecięcia z Π prostej przechodzącej przez P.
W rzucie środkowym wszystkie proste (promienie rzutowania) mają punkt wspólny, nazywany środkiem rzutowania. Odległość tego punktu decyduje o deformacji rysunku, gdyż przy rzutowaniu środkowym zmienione zostają relacje odległości. Rzut środkowy pozwala na bardziej realistyczną wizualizację obiektów trójwymiarowych i daje wrażenie głębi – modeluje metodę rzutowania ludzkiego systemu wzrokowego.

26. Podaj wzajemne położenie układów współrzędnych: danych i obserwatora.

Układ obserwatora nie jest określony jednoznacznie. Możemy przyjąć, że jego początek pokrywa się z początkiem układu danych 0. Przekształcenie układu danych do układu obserwatora będzie polegało na wykonaniu takich obrotów wokół osi układu, by wektor n=[xn,yn,zn] miał kierunek osi nowego układu i przeciwny do niej zwrot.

27. Podaj zależności na współrzędne x’, y’ rzutu P’ punktu P w rzutowaniu środkowym w układzie obserwatora.

Przyjmujemy, że P = [x,y,z], P’=[x’,y’,z’], a obserwator utożsamiany ze środkiem rzutowania E znajduje się na ujemnej części osi z układu w punkcie (0,0,-d). Wtedy zależności współrzędnych x’ i y’ to:

28. Wymień we właściwej kolejności operacje, jakie należy wykonać, aby obrócić punkt P o kąt φ dookoła prostej zadanej przez dwa punkty P1 i P2.

1. Przesunięcie punktów P1 i P2 o wektor -P1 (tak, aby P1 znalazł się w początku układu współrzędnych).
Niech β oznacza kąt, jaki prosta P1’P2’ tworzy z płaszczyzną xz, a kąt między jej rzutem P1’P2’’ na tę płaszczyznę i osią x niech będzie równy α.
2. Obrót wokół osi y o kąt α,
Obrót wokół osi z o kąt β,
3. Obrót wokół osi z o kąt φ,
4. Wykonanie punktów 1. i 2. w odwrotnej kolejności i z przeciwnymi wartościami kątów (-α,-β) i przesunięcia, czyli:
Obrót wokół osi z o kąt -β,
Obrót wokół osi y o kąt -α,
Przesunięcie na współrzędne pierwotne – o wektor +P1

29. Zdefiniuj i podaj własności rzutowania równoległego. Podaj definicję rzutu ortogonalnego.

Rzut równoległy – to rodzaj rzutu, w którym wszystkie proste rzutowania (proste przechodzące przez punkt P i jego obraz P’ na płaszczyźnie rzutowania Π) mają ten sam ustalony kierunek k.
Rzut równoległy zachowuje równoległość prostych, stosunek długości odcinków równoległych i związki miarowe figury płaskiej równoległej do płaszczyzny rzutowania.
Rzut ortogonalny – to rodzaj rzutu równoległego, w którym proste rzutowania są prostopadłe do rzutni.

30. Co to jest aksonometria kawalerska, a co wojskowa?

Aksonometria wojskowa – rodzaj rzutu równoległego, w którym kąt pomiędzy kierunkiem rzutu k a rzutnią Π wynosi 45°.
Aksonometria kawalerska – rodzaj rzutu równoległego, w którym kąt pomiędzy kierunkiem rzutu k a rzutnią Π wynosi 63°.

31. Co należy zadać, by zdefiniować ostrosłup widzenia?

- Wierzchołek ostrosłupa widzenia E, który może być jakimkolwiek punktem R3,
- Ograniczony obszar o wybranym kształcie wielokąta, np. prostokąta o wymiarach a x b, który stanowić będzie rzutnię,
Krawędzie ostrosłupa będą półprostymi wychodzącymi z wierzchołka E i przechodzące przez wierzchołki prostokąta rzutni.

32. Podaj zależności dla algorytmu Cohena-Sutherlanda obcinania odcinka do prostopadłościanu.

Algorytm opiera się na przypisaniu każdemu końcowi odcinka sześciobitowego kodu określającego położenie tego punktu względem prostopadłościanu.
Kod(P)=b6 b5 b4 b3 b2 b1
b1=1, gdy P leży na lewo od prostopadłościanu,
b2=1, gdy P leży na prawo od prostopadłościanu,
b3=1, gdy P leży poniżej prostopadłościanu,
b4=1, gdy P leży powyżej prostopadłościanu,
b5=1, gdy P leży przed prostopadłościanem,
b6=1, gdy P leży za prostopadłościanem,

33. Jakie parametry 3W obiektów - oprócz czysto geometrycznych, umożliwiają ich realistyczną wizualizację?

Stopień realizmu wizualizacji można osiągnąć poprzez:
- Zastosowanie odpowiedniego modelowania kolorów powierzchni,
- Zastosowanie ścian przybliżających powierzchnię za pomocą wielokątów,
- Zastosowanie odpowiedniego modelowania oświetlenia,

34. Jakie znasz sposoby reprezentacji krzywych? Podaj przykład.

Krzywe mogą być opisywane:
- analitycznie funkcją jednej zmiennej
y = f (x) dla x z [t1,t2]
- lub parametrycznie
x = x(t), y = y(t), t z [t1,t2]
- gdy czasami dysponujemy tylko dyskretną informacją o krzywej w postaci zbioru punktów P1,P2,…,Pn, przez które krzywa przechodzi. Jednym z możliwych postępowań jest wtedy przybliżanie krzywej funkcją ustalonej klasy. Może nią być wielomian, funkcja sklejania itp. Prowadzi to do rozwiązania zadania interpolacyjnego lub aproksymacyjnego.
Wyznaczone współczynniki kombinacji liniowej wybranych funkcji bazowych dają reprezentację krzywej.
Przykład:
y = tg(x) dla x z [0,Pi/2]

35. Co to jest drzewo czwórkowe i do czego jest używane?

Drzewo czwórkowe to struktura danych będąca drzewem w którym każdy węzeł nie będący liściem, ma 4 następniki (synów). Używane jest do podziału dwuwymiarowej przestrzeni na mniejsze części, dzieląc ją na cztery równe ćwiartki, a następnie każdą z tych ćwiartek na cztery itd.. Struktura ta wykorzystywana jest np. przy wykrywaniu kolizji przestrzeni 2W, tworzeniu sum i iloczynów dwóch obszarów, czy też kompresji obrazów dwukolorowych, przechowywaniu reprezentacji powierzchni 2W.

36. Podaj reguły na sumę i przecięcie (iloczyn) dwóch obszarów płaskich opisanych za pomocą drzew czwórkowych.

Suma: Konstrukcja drzewa U będącego sumą U = S U T dwóch drzew opisujących obszary płaskie wymaga równoległego przeglądania obu drzew (S i T) od korzeni w dół i sprawdzania
odpowiadających sobie węzłów w kolejnych pokoleniach:
- jeśli jeden z węzłów jest liściem czarnym, to w drzewie U umieszczamy liść czarny,
- gdy węzeł jednego drzewa jest liściem białym, to w U umieszczamy w tym miejscu kolor z drzewa drugiego,
- jeśli odpowiadające sobie dwa węzły będą szare, to wynikowy węzeł w U również będzie szary.
Algorytm stosuje się do wszystkich potomków w obu drzewach. Jeśli przy sumowaniu dwóch szarych węzłów otrzymano cztery czarne liście, należy je połączyć, zastępując w drzewie-sumie ich szarego ojca czarnym liściem i sprawdzić, czy sytuacja nie ma miejsca u wcześniejszych przodków. Iloczyn (przecięcie, część wspólna) U = S (AND) T : algorytm analogiczny jak w sumie, z tym iż zamieniamy rolami kolory biały i czarny, a w przypadku sumy dwóch szarych węzłów, łączenie potomków dotyczy białych synów.

37. Podaj reprezentację szkieletową wielościanu.

Szkieletowa reprezentacja wielościanu – sposób opisu bryły w postaci szkieletu utworzonego przez krawędzie ścian bryły. Ma hierarchiczną strukturę
– powierzchnia bryły jest opisana płaskimi, wielokątnymi ścianami, które przecinają się wzdłuż krawędzi, a te łączą się między sobą w wierzchołkach bryły. Każda ściana jest określona zbiorem krawędzi, krawędzie natomiast – parami wierzchołków. Metodą zapamiętywania tej reprezentacji są listy:
- tablica wierzchołków (TW) – zawiera współrzędne x,y,z wierzchołków w przestrzeni 3W,
- tablica krawędzi (TK) – zawiera pary numerów wierzchołków,
- lista ścian (LŚ) – ciągi numerów krawędzi będących bokami ścian bryły.
- lista krawędzi (LK) – lista liczby krawędzi kolejnych ścian,
Pamiętane są również liczby ścian s, wierzchołków w i krawędzi k.

38. Podaj ideę reprezentacji bryły przez zakreślenie przestrzeni.

Reprezentację bryły przez zakreślenie przestrzeni rozumiemy jako budowanie bryły poprzez przemieszczenie jej przekroju (płaskiej figury) wzdłuż pewnej trajektorii w przestrzeni. Najprostszymi przykładami są: przesunięcie równoległe i obrót wokół prostej.

39. Podaj definicję „klocka”, „brzegu klocka” oraz jego dopełnienia (zewnętrza) stosowane w konstruktywnej geometrii brył (ang. CSG).

Klocek – dowolna podprzestrzeń, czyli zbiór punktów (x,y,z) spełniających nierówność f(x,y,z) < 0, gdzie f jest dowolnym funkcjonałem ciągłym. Brzeg klocka – tworzą go punkty, dla których f(x,y,z) = 0,Dopełnienie (zewnętrze) – tworzą je punkty spełniające nierówność f(x,y,z) > 0.

40. Co to jest drzewo ósemkowe i do czego jest wykorzystywane?

Drzewo ósemkowe jest strukturą danych analogiczną do drzewa czwórkowego. O ile jednak drzewo czwórkowe wykorzystywane do opisywania obszarów na płaszczyźnie, o tyle drzewo ósemkowe opisuje bryły. Drzewo ósemkowe charakteryzuje się tym, że każdy węzeł nie będący liściem, posiada ośmiu synów. Drzewo ósemkowe jest wykorzystywane do przechowywania reprezentacji bryły 3W.

41. Od czego zależy liczba poziomów reprezentacji obiektu w drzewie (czwórkowym lub ósemkowym)?

Liczba poziomów reprezentacji w drzewie zależy od kryterium zakończenia. Wyróżnia się dwa podstawowe kryteria zakończenia
podziału węzłów:
- do momentu, gdy wszyscy potomkowie będą jednorodni („czarne” lub „białe”),
- do momentu, gdy rozmiary podzielonych kwadratów (sześcianów) są odpowiednio małe, np. mniejsze od wielkości piksela na ekranie.

42. Opisz zwięźle operację kodowania figury płaskiej za pomocą drzewa czwórkowego.

Dzielenie kwadratów, które są w drzewie oznaczone jako węzły szare (czyli częściowo w figurze, częściowo poza nią) na kolejne czwórki węzłów, do momentu gdy wszystkie liście drzewa będą białe lub czarne albo będą reprezentować wystarczająco małe kwadraty.

43. Czym się różni drzewo czwórkowe do opisu obszaru od drzewa do opisu konturu?

Do opisu obszaru używamy koloru: białego – poza obszarem, szarego – częściowo wewnątrz (niejednolity), czarny – wewnątrz obszaru.
W przypadku gdy opisujemy kontur zaznaczamy kolorem te kwadraty przez które przechodzi krawędź, a kwadraty które są całkowicie wewnątrz lub na zewnątrz maja kolor biały. W przypadku krawędzi wyróżnia się dodatkowy typ liścia – krawędź, oznaczający, że przez obszar liścia przechodzi dokładnie jedna krawędź figury.

44. Objaśnij termin "konstruktywna geometria brył"(ang. CSG).

Termin „konstruktywna geometria brył” oznacza metodę budowania brył w wyniku składania ustalonych, elementarnych „klocków”. Operacje składania to dodawanie, odejmowanie i iloczyn zbiorów. Możliwe są też transformacje tych klocków – przesunięcie, skalowanie i obrót.

45. Jaką postać ma opis konstruowania sceny w CSG?

Opis konstruowania sceny w CSG ma postać drzewa konstrukcji, którego liśćmi są elementy podstawowe (klocki) lub parametry określające transformacje. Natomiast węzły wewnętrzne odpowiadają działaniom na tych elementach (dodawaniu, odejmowaniu, iloczynowi) albo transformacjom (skalowaniu, obrotowi, przesunięciu).

46. Podaj schemat tworzenia reprezentacji 3W bryły za pomocą drzewa ósemkowego.

Obiekt przestrzenny (bryłę) wpisujemy w sześcian, któremu odpowiada korzeń drzewa ósemkowego. Ten wyjściowy sześcian dzielimy na osiem mniejszych sześcianów. Jeśli mniejszy sześcian leży całkowicie wewnątrz bryły to reprezentującemu go synowi korzenia przypisujemy kolor czarny. Gdy cały leży na zewnątrz bryły to kolor biały, sześciany niejednorodnym, tylko częściowo zawarte w bryle dzielimy na mniejsze aż do uzyskania wszystkich potomków jednorodnych lub mniejszych od ustalonej minimalnej wielkości.

47. Jakie znasz grupy metod i algorytmów wyznaczania linii i powierzchni zasłoniętych i jaka jest podstawa tego podziału?

Podział 1.
Podstawą podziału są różne techniki wizualizowania powierzchni.
Metoda pikselowa – wykorzystuje algorytm Bresenhama rysowania odcinków i wyznacza zbiory pikseli odpowiadające widocznym fragmentom linii.
Metoda analityczna – niezasłonięte obszary są określane analitycznie, co wymaga rozwiązywania układów równań nieliniowych.
Podział 2.
Podstawą podziału jest wymiarowość przestrzeni, w której odbywają się obliczenia i rozstrzyganie o zasłanianiu.
Metody przestrzeni danych – potrzebne obliczenia i porównania między elementami geometrycznymi rysowanej sceny są wykonywane w trójwymiarowej przestrzeni obiektów.
Metody przestrzeni obrazu – odnoszą się do przestrzeni obrazu i w niej zachodzi rozstrzyganie, czy należy badać przestrzenne położenie obiektów by ustalić zasłanianie.

48. Podaj przykład algorytmu obliczania zasłonięć z przestrzeni danych oraz idei jego działania.

Przykładem algorytmu obliczania zasłonięć z przestrzeni danych jest algorytm Ricciego. Jego idea sprowadza się do porównywania rzutu każdej krawędzi i każdego odcinka z rzutami wszystkich ścian i wyznaczania widocznych fragmentów badanej krawędzi (odcinka). Założenie, że ściany są wielokątami wypukłymi umożliwia istotne zmniejszenie kosztu obliczenia części wspólnej odcinka i ściany. Nie stanowi to jednak istotnego ograniczenia.

49. Podaj przykład działania algorytmu obliczania zasłonięć z przestrzeni obrazu i podaj ideę jego działania.

Przykładem algorytmu obliczania zasłonięć z przestrzeni obrazu jest algorytm z buforem głębokości. W tym algorytmie wypełnia się bufor ekranu znajdując dla każdego piksela ścianę leżącą najbliżej przed nim w kierunku patrzenia i przypisując mu kolor/jasność odpowiedniego fragmentu tej ściany. Ściany obiektu mogą być dowolnymi wielokątami, mogą też się wzajemnie przenikać i mieć dziury.