1. Podaj znaczenie terminów: przestrzeń urządzenia, przestrzeń operacyjna urządzenia, powierzchnia

obrazowania, macierz adresowania, jednostka rastru.

Przestrzeń urządzenia (obrazującego) - 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 wizualnego).

Przestrzeń operacyjna - obszar w przestrzeni urządzenia, którego zawartość została odwzorowana na powierzchni

obrazowania

Powierzchnia obrazowania – nośnik w urządzeniu wizualizacyjnym na którym tworzony jest obraz fizyczny

Macierz adresowalna - utworzona z 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

Jednostka rastru - jednostką rastru jest piksel

2. Podaj znaczenie kadr obrazu, obcinanie, okrawanie, ekranowanie, monitor rastrowy graficzny,

częstotliwość odświeżania.

Kadr obrazu – pewien obraz wystawiony z ciągu obrazów jakie mogą być przesłane do generatora obrazów w celu

ich wygenerowania i wystawienia.

Częstotliwość odświeżania – liczba cykli na sekundę z jaką trzeba odświeżać obraz na monitorze, aby uzyskać

wrażenie jego stabilności.

Monitor rastrowy - w monitorach rastrowych obraz wyświetlany jest poprzez wiązkę elektronów przebiegającą przez

cały ekran w pionie w postaci pionowych linii wzbudzając świecenie niewielkich fragmentów ("punktów") ekranu z

których składa się każda linia; wyposażony w bloki funkcjonalne do przetwarzania listy obrazowej.

Obcinanie – wyliczanie części elementów leżących w oknie.

Okrawanie – przy przekroczeniu rozmiaru ekranu automatycznie wygasza strumień elektronowy

3. Podaj znaczenie i omów wzajemne związki miedzy terminami: język graficzny, bufor obrazu, generator

obrazu, lista obrazowa, konturowe rozwiniecie obrazu, rastrowe rozwiniecie obrazu.

Język graficzny – służy do programowania urządzeń graficznych; produktem wykonania programu graficznego jest

(zapełniony) bufor obrazu

Bufor obrazu - obszar w pamięci, w którym przechowywane są rozkazy graficzne lub dane obrazowe potrzebne do

wygenerowania obrazu fizycznego.

Generator obrazu - 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

Konturowe rozwinięcie obrazu – sposób kreślenia elementów obrazu zadany przez program, gdzie ruch

elementu kreślącego obraz jest analogiczny do przesunięć pióra kreślaka stołowego.

Rastrowe rozwinięcie obrazu – technika punktowego generowania lub zapis obrazu punkt po punkcie wzdłuż

poziomych linii równoległych, radialnych lub spiralnych. Wykorzystywane do generowania obrazu np. w monitorach.

4. Podaj znaczenie i związki miedzy terminami: konsola graficzna, generator wektorów, generator znaków,

generator krzywych, drążek sterujący, manipulator kulowy, pióro świetlne, rysownica.

Generator wektorów - (vector generator) - urządzenie lub układ elektroniczny, 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ę kilka

rodzajów generatorów, min.: generator o proporcjonalnym czasie (proportional time vector generator) w, którym czas

kreślenia wektora jest w przybliżeniu proporcjonalny do długości tego wektora; generator o stałym czasie, w którym

czas kreślenia wektora nie zależy od jego długości; generator przyrostowy, który składa wektor z elementarnych

odcinków linii siatki dyskretnej tak , że wektory nachylone mają postać zębatej piły zamiast linii prostej Generator znaków - (character generator) - urządzenie lub układ elektroniczny, który na podstawie danego kodu

generuje postać graficzną znaku. Wyróżnia się różne rodzaje generatorów znaków, min.: generator mozaikowy, który

tworzy znaki z kropek i generator segmentowy, który składa je z odcinków linii.

Generator krzywych - (curve generator) - urządzenie lub układ elektroniczny, który generuje krzywą na podstawie

definiujących ją danych.

Pióro świetlne – obecnie rzadko spotykane (głównie w pracowniach projektowych) urządzenie peryferyjne w

kształcie długopisu służące do sterowania komputerem (np. zamiast myszy).

Drążek sterujący – manipulator, zmienia ustawienie 2 potencjometrów, które określają współrzędne x ,y znacznika

na ekranie.

Konsola graficzna – zestaw sprzętowy, składający się z min 1 graf. urządzenia wyjściowego i 1 lub więcej urządzeń

wejściowych

Manipulator kulowy – ma dwa stopnie swobody ruchu, służy do umiejscowienia elementu na ekranie

Rysownica – chyba chodzi o tablet ;) – wskazują cale linie (pióra świetlne tylko punkt). Powierzchnia takiego

urządzenia jest najczęściej odwzorowana na monitorze a wyświetlany znacznik wskazuje położenie sondy która

użytkownik przesuwa po urządzeniu.

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

Rząd spójności siatki – liczba półprostych siatkowych wychodzących z każdego węzła siatki.

Siatka Generacyjna – jest to zbiór współrzędnych całkowitych danego urządzenia graficznego (Układ

współrzędnych pikselowych) /+/ na nich rysujemy proste i krzywe – patrz pytanie 6

Moduł siatki – Chuj wie :D może chodzi o sposób wybierania sąsiednich pikseli – wybór czterokierunkowy i

Ośmiokierunkowy

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

Końcami rysowanego odcinka (krzywej) są punkty o współrzędnych pikselowych (x0,y0) i (xk, yk)

W zależności od wyboru pikseli czterokierunkowych lub ośmiokierunkowych wybieramy kolejny piksel ten którego

środek leży najbliżej odcinka(krzywej).

Konieczność – chodzi chyba o to ze współrzędne pikselowe różnią się od współrzędnych rzeczywistych i jak

aspekt jest np. różny od 1 to by zniekształcało rysunek ?

7. Podaj we współrzędnych jednorodnych zapis operacji na punkcie: przesunięcia, obrót wokół P=(0,0) i

P=(x0,y0) // (normalny obrót i wokół dowolnego punktu)

Przesuniecie:

[x’,y’,1]=[x,y,1][1,0,0; 0,1,0;tx,ty,1]

Obrot:

[x’y’1] = [x,y,1][cos (fi), sin(fi), 0; -sin(fi),cos(fi),0; 0,0,1]

Obrot wokół dowolnego punktu:

[x’,y’,1]= [x,y,1][1,0,0; 0,1,0;-tx,-ty,1][cos (fi), sin(fi), 0; -sin(fi),cos(fi),0; 0,0,1] [1,0,0; 0,1,0;tx,ty,1]

Skalowanie

[x’,y’,1]=[x,y,1] [ sx,0,0; 0, sy,0; 0,0,1]

8. Zdefiniuj okno i widok oraz okienkowanie i obcinanie; podaj co to są współrzędne znormalizowane i do

czego one służą.

Okienkowanie – wyizolowanie dowolnej części wyświetlonego obrazu .

Obcinanie – wyznaczanie elementów wewnątrz okna.

Okno – ograniczony obszar w obrębie przestrzeni obrazowania, który jest odwzorowany na wziernik; może być

rozszerzone do całej przestrzeni obrazowania; Prostokątny obszar w przestrzeni danych

Widok – ograniczony obszar w obrębie przestrzeni operacyjnej urządzenia, który prezentuje zawartość okna; może

być rozszerzony do całej przestrzeni operacyjnej; Obszar (prostokątny) na urządzeniu graficznym

a) Okno we współrzędnych rzeczywistych; b) Widok we współrzędnych urządzenia graficznego.

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 stad 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ść

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.

(x’,y’)=(x0,y0)+k(x-x0, y-y0)

Macierzowo:

[x’,y’,1]=[x,y,1][k,0,0; 0,k,0; (1-k)x0, (1-k)y0, 1]

Dla k = -1 przekształcenie takie jest symetria 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 wiec w taki punkt P’=(x’,y’), ze QP’ = kQP, gdzie Q jest rzutem prostokątnym punktu P na oś

powinowactwa ax +by +c=0.

Wektor [a,b] jest prostopadły do prostej ax+by+c=0. Punkt Q jest zatem równy P+t[a,b] dla pewnej wartości

parametru t. Wartość t wyznaczamy z warunku, ze Q leży na osi powinowactwa, a więc a(x+ta)+b(y+tb)+c=0. Stąd:

t=ax+by+ca2+b2 i Q=x,y-ax+by+ca2+b2(a,b)

W omawianym przekształceniu obrazem punktu P ma być punkt P’ spełniający zależność QP’=kQP, a wiec

P’=Q+k(P-Q). Ze wzorów wynika zatem, ze

P=(x,y)+(k-1) -ax+by+ca2+b2(a,b)

Zapis macierzowy:

[x’,y’,1]=[x,y,1][1+wa2, wab, 0; wab, 1+wb2, 0; wac, wbc, 1]

w=(k-1)/(a2+b2)

W szczególnym przypadki k=-1 powinowactwo prostokątne jest symetria osiowa.

10. Podaj idee 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?

Nie jest istotne, czy obcinanie wykonujemy w przestrzeni danych rzeczywistych, czy w przestrzeni obrazu. Niech prostokąt (okno), do którego obcinamy punkty i odcinki będzie definiowany nierównościami

ymin =< x =< xmax, ymin=<y=<ymax

Jeśli współrzędne (x,y) danego punktu P spełniają te nierówności to leży on wewnątrz zadanego prostokąta. W przypadku odcinka proces obcinania nie jest aż tak trywialny.

Algorytm Cohena-Sutherlanda

Każdemu końcowi przypisujemy kod czterobitowy określający

położenie tego punktu względem prostokątnego okna

Kod(P)=b4b3b2b1

b1 = 1 gdy P leży na lewo od okna b2 = 1 gdy P leży ma prawo od okna

b3 = 1 gdy P leży poniżej okna, b4 = 1 gdy P leży powyżej okna

b1 jest bitem znaku x-xmin, b2 i b3 odpowiednio xmax-x i y-ymin, a b4 jest bitem znaku ymax-y.

Punkt P=(x,y) leży wewnątrz okna jeśli spełnione sa nierówności

(ymin =< x =< xmax → ymin=<y=<ymax)

a wtedy kod(P)=0000. Odcinek P1P2 leży całkowicie wewnątrz okna, gdy kod (P1) = kod(P2) = 0000.

Proces obcinania odcinka od prostokątnego okna przebiega w algorytmie Cohena-Sutherlanda w ten sposób, ze koniec odcinka o kodzie nie zerowym jest zastępowany punktem przecięcia badanego odcinka z prosta zawierająca

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. Wybór kolejnych boków okna

względem których obcinamy odcinek jest obojętny.

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ąty zwykle – takie których krawędzie nie maja punktów wspólnych różnych od wierzchołków.

Monotoniczny – jeżeli przy odpowiedniej numeracji wierzchołków, możemy podzielić brzeg wielokąta na 2 łańcuchy

P1->P2->…->Pk i Pk -> Pk+1 -> … -> P1 i rzut prostopadłe na pewna prosta l wierzchołków są uporządkowane tak

samo jak tworzące je wierzchołki.

Wypukły – jeżeli dla każdych 2 punktów będących wewnątrz wielokąta i cały odcinek łączący te 2 punkty leży

wewnątrz tego wielokąta.

Wklęsły – jeżeli istnieje taka para punktów znajdujących się wewnątrz wielokąta dla których odcinek łączący je nie

leży całkowicie wewnątrz tego wielokąta Algorytmy sprawdzania czy punkt P leży wewnątrz wielokąta W.

I.Algorytm parzystości.

Z punktu P prowadzimy dowolna półprosta l, dla prostoty np. na prawo równolegle do osi x;

Znajdujemy liczbę ‘np.’ przeciec tej półprostej z bokami wielokąta;

Jeśli liczba ‘np.’ jest parzysta to P leży na zewnątrz wielokąta W, a gry nieparzysta to wewnątrz.

-algorytm nie obejmuje przypadków szczególnych. Jednym z nich jest przechodzenie półprostej przez wierzchołek.

Innym to półprosta zawiera bok wielokąta II. Obliczanie sumy kątów miedzy półprostymi prowadzonymi z punktu P przez wierzchołki Pi wielokąta.

Zakładamy ze wierzchołki sa uporządkowane odwrotnie do ruchu wskazówek zegara. Niech αi oznacza kat miedzy

PPi PPi+1. Jeżeli uporządkowanie ramion jest zgodne z ruchem wskazówek zegara to kat ma znak +, w przeciwnym

przypadku - .

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

podaj idee trójkątowania wielokąta monotonicznego.

Triangulacja wielokątów

Jest to podział wielokąta na trójkąty, ułatwia rozwiązywanie wielu zadań. Należą do nich wypełnianie obszarów,

określanie zasłaniania i oświetlania obiektów twojwymiarowych, a także wyznaczanie linii i ich przecięcia. Dla efektywności tych zastosowań ważne jest by liczba składowych trójkątów była jak najmniejsza i by nie było trzeba

definiować nowych danych.

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 moglu być tylko wierzchołki danego wielokąta.

Interesuje wiec nas podział n-kata (np. piecio-kata) na n-2 liczbę trójkątów.

Dla niektórych wielokątów triangulacja jest bardzo łatwa, np. kiedy wielokąt jest wypukły, wówczas wystarczy

połączyć wierzchołek z pozostałymi.

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.

Wyznaczanie powłoki wypukłej zbioru punktów.

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 nazywamy najmniejszy(w sensie zawierania) zbiór wypukły do którego należą

dane punkty. Powłoka wypukła n punktów jest wielokątem.

Algorytmy związane z wyznaczaniem powłoki wypukłej.

-Algorytm Grahama wyznaczania powłoki wypukłej n punktów

-Algorytm Greena i Silvermana wyznaczania powłoki wypukłej zbioru punktów

Algorytm Grahama wyznaczania powłoki wypukłej n punktów

Dane: punkty Pi=(xi,yi),, i=1,2,...,n;

1) wyszukujemy punkt o najmniejszej współrzędnej y, oznaczamy go jako Pi1,

2) porządkujemy punkty zgodnie z rosnącymi wartościami kątów Pαi, obliczając:

ctg(Pαi) = (xi-xi1)/(yi-yi1). Otrzymujemy nowe uporządkowanie, oznaczamy je jako i1, i2, ..., in.

3) tworzymy listę Pl1, Pl2, ... , Plk wierzchołków wielokąta będącego powłoką wypukła następująco:

- na początku przyjmujemy: l1=i1, l2=i2, l3=i3 i podstawiamy k=3,

- dla j=4,5,...,n; lj=ij

(*) jeśli para wektorów Plk-1Plk, PlkPlj jest ujemnie zorientowana, to usuwamy z listy wierzchołek Plk, podstawiamy

k=k-1 i wracamy do (*),

w przeciwnym razie dopisujemy Pij do listy, czyli podstawiamy k=k+1, lk=ij.

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

Wierzchołki są uporządkowane odwrotnie do kierunku wskazówek zegara, porównuje się wierzchołki kolejno z bokiem okna i tworzy z nich nowy ciąg określający wielokąt obcięty danym bokiem. Wierzchołki leżące wewnątrz okna staja się elementami ciągu, a te na zewnątrz są odrzucane. Na koniec łączymy wg kolejności niepołączone ze

sobą wierzchołki bokami okna.

15. Podaj idee algorytmu Shamosa-Hoeya wyznaczania czesci wspólnej wielokątów wypukłych.

Niech będą wielokąty P i Q o wierzchołkach uporządkowanych odwrotnie do kierunku wskazówek zegara. Przez

wierzchołki prowadzimy pionowe linie dzielące ten wielokąt na trapezy i trójkąty. Następnie wyznaczamy części

wspólne dla co najwyżej n+m trapezów (trójkątów).

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

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

w – wektor

|w| - długość wektora (długość euklidesowa) |w|=(x2+y2+z2)1/2

Znakiem ‘o’ oznaczamy iloczyn skalarny, a znakiem ‘x’ iloczyn wektorowy.

w1=[x1,y1,z1] i w2=[x2,y2,z2]

a) Iloczyn Skalarny: w1o w2 = |w|1 |w|2 cos L(w1,w2)= w1w2

T = x1x2 + y1y2 +z1z2

b) Iloczyn wektorowy: w=w1 x w2

(1) Wektor jest prostopadły do obu wektorów w1 i w2

(2) Trójka uporządkowana wektorów w1, w2 i w jest dodatnio zorientowana

Det(w1, w2, w) = det[ x1,y1,z1; x2,y2,z2; x, y, z ] > 0

(3) |w| = |w|1 |w|2 sin L(w1,w2)

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

+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.

Płaszczyznę można określić np. podając wektor normalny n =[xn,yn,Zn], czyli wektor prostopadły do płaszczyzny, i

punkt P0 = (x0,y0,z0), przez który ona przechodzi. Wtedy dla dowolnego punktu P płaszczyzny wektor P-P0 jest

prostopadły do n.

n o (P-P0) = 0

- Równanie płaszczyzny: xnx+yny+znz = c

c= n o P0 = xnx0+yny0+znz0

Równanie płaszczyzny wyznaczonej przez trzy nie współliniowe punkty P1, P2 i P3.

Wektory P3-P1 i P2-P1 rozpinają te płaszczyznę, a ich iloczyn wektorowy jest wektorem normalnym do niej.

((P2-P1)x(P3-P1)) o (P-P1) = 0

19. Wyprowadź zależność na punkt przecięcia prostej z płaszczyzna.

Jeżeli istnieje punkt przecięcia prostej z płaszczyzna to jest określony wartoscią parametru t spełniająca równanie:

n o (P0 + tk) = c

Ta zależność nie ma sensu dla n o k = 0, tzn. kiedy prosta i płaszczyzna są równoległe.

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

((P2-P1)x(P3-P1)) o ( P-1) =0

- macierzowo:

det[ x,y,z,1; x1,y1,z1,1; x2,y2,z2,1; x3,y3,z3,1] = 0

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

Niech:

n1 o P = c1 i n2 o P = c2

będą danymi równaniami płaszczyzn. Zakładamy ze nie sa rownolegle. Szukamy prostej wspolnej dla dwoch

płaszczyzn. Taka prosta jest prostopadla do n1 i n2. Jej wektorem kierunkowym jest n1 x n2. Do wyznaczenia przedstawienia parametrycznego

P(t) = P0 + t n1 x n2

Szukanej prostej brakuje dowolnego punktu P0, przez która ta prosta przechodzi. Możemy wyznaczyc P0 jako punkt

przecięcia tych dwoch płaszczyzn z trzecia do nich nie rownolegla. Taka plaszczyzna jest np. plaszczyzna o

wektorze n1 x n2 przechodzaca przez poczatek układu współrzędnych, a zatem spelniajaca rownanie (n1 x n2)oP=0

23. Podaj macierze przesuniecia, skalowania i obrotu o kat φ wokół osi z w przestrzeni R3 (3W).

Obrazem punktu P po obrocie o kat φ wokół osi z jest punkt P’=(x’,y’,z’)

x’=x; y’=y cosφ – z sinφ; z’=y sinφ + z cosφ;

[x’,y’,z’,1]=[x,y,z,1]=[1,0,0,0; 0, cosφ , – z sinφ ,0; 0, cosφ, sinφ,0; 0,0,0,1]

Obrazem punktu P po obrocie o kat φ wokół osi y jest punkt P’=(x’,y’,z’)

x’=x cosφ + z sinφ ; y’=y; z’= -x sinφ + z cosφ;

[x’,y’,z’,1]=[x,y,z,1]=[ cosφ,0, –sinφ,0; 0,1,0,0; sinφ,0, cosφ,0; 0,0,0,1]

Obrazem punktu P po obrocie o kat φ wokół osi z jest punkt P’=(x’,y’,z’)

x’= x cosφ - y sinφ; y’= x sinφ + y cosφ; z’=z;

[x’,y’,z’,1]=[x,y,z,1]=[ cosφ, sinφ,0,0; -sinφ, cosφ,0,0; 0,0,1,0; 0,0,0,1]

Przesuniecie skalowanie jest analogiczne do R2 – Jednorodnosc – zadanie 7

25. Zdefiniuj i podaj własnosci rzutowania srodkowego.

Rzut srodkowy pozwala na bardziej realistyczna wizualizacje obiektow trójwymiarowych i daje wrazenie glebi.

W rzucie srodkowym wszystkie proste (promienie rzutowania) maja punkt wspolny, nazywany srodkiem rzutowania.

Odleglosc tego punktu decyduje o deformacji rysunku.

26. Podaj wzajemne połozenie układów współrzednych: danych i obserwatora.

Rzutnia w układzie obserwatora pokrywa się z plaszyzna z=0. Rzutem punktu P= (x,y,z) jest wtedy P’=(x,y,0)

27. Podaj zaleznosci na współrzedne x’, y’ rzutu P’ punktu P w rzutowaniu srodkowym w układzie

obserwatora.

W przypadku rzutu srodkowego będziemy utożsamiali polozenie obserwatora ze srodkiem rzutowania E o

współrzędnych (xE,yE,zE) w wyjsciowym układzie danych 0xyz. Przyjmujemy, ze plaszczyzna rzutowania jest

prostopadla do 0E.

28. Wymien we własciwej kolejnosci operacje, jakie nalezy wykonac, aby obrócic punkt P o kat φ dookoła prostej zadanej przez dwa punkty P1 i P2.

Obrot wokół takiej prostej można otrzymać jako złożenie odpowiednich translacji i obrotow wokół osi układu

współrzędnych.

1) Wykonujemy translacje (od siebie dodam ze chodzi o translacje P1 i P2, a nie tylko P1) o wektor

–P1=[-x1,-x2,-x3]. Punkt P1 będzie przesuniety do początku układu współrzędnych. Nich β oznacza kat, jaki prosta

P1’P2’ tworzy z plaszczyzna xz, a kat miedzy jej rzutem P1’P2” na te płaszczyznę i osia x niech będzie rowny α .

2) Obroty najpierw o kat –α wokół osi y, a nastepnie o kat β wokół osi z przekształcają prosta p1’P2’ na os x.

Wybor osi układu współrzędnych na która przekształcamy os P1P2 jest dowolny.

3) wykonujemy obrot o kat φ wokół osi x.

4) dokonujemy przekształceń odwrotnych do wstepnych transformacji (2) i (1) w odpowiedniej kolejnosci:

obrot o kat β ,obrot o kat α i przesuniecie o wektor +P1

29. Zdefiniuj i podaj własnosci rzutowania równoległego. Podaj definicje rzutu ortogonalnego.

Rzut rownolelgy zachowuje równoległość prostych, stosunek długości odcinkow i związki miarowe figury równoległej

do płaszczyzny rzutowania. Stosuje się go glownie w rysunku technicznym.

Przy rzutowaniu równoległym wszystkie proste rzutowania maja ten sam ustalony kierunek k. Jeśli jest on prostopoadly do rzutni to rzut nazywamy ortogonalnym.

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

Aksonometria - rodzaj rzutu równoległego, odwzorowanie przestrzeni na płaszczyznę z wykorzystaniem

prostokątnego układu osi.

Aksonometria kawaleryjska - kąt wynosi około 63°

Aksonometria wojskowa - kąt wynosi 45°

31. Co nalezy zadac, by zdefiniowac ostrosłup widzenia?

Definiowanie ostrosłupa widzenia polega na rzutowaniu tylko tych obiektow (ich fragmentow) które się mieściły w ow ostroslupie. Wierzcholek ostrosłupa widzenia E może być jakimkolwiek punktem R3 a krawdzie sa półprostymi wychodzącymi z E i majace kierunki: v+u+w, v+u-w, v-u+w, v-u-w. Im mniejsze w u v tym wiekszy jest ostroslup widzenia.

32. Podaj zaleznosci dla algorytmu Cohena-Sutherlanda obcinania odcinka do prostopadłoscianu.

dochodzi 5 i 6 bit

b5 – przed prostopadłościanem

b6 - za prostopadłościanem

33. Jakie parametry 3W obiektów - oprócz czysto geometrycznych, umozliwiaja ich realistyczna

wizualizacje?

Zludzenie przestrzenności można osiągnąć stosując wyrafinowane metody wizualizacji np. uwzględniając

oświetlenie. Powierzchnie figury przybliżamy wielokatami. Dla każdej plaskiej sciany wyznaczamy jej oświetlenie

(jasność) zaleznie od wielkosci kata miedzy kierunkiem padania swiatla a wektorem prostopadłym do sciany.

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

Krzywe mogą być opisywane analitycznie funkcją jednej zmiennej y=f(x) dla x?(x1,x2).

Ogólniejsze jest przedstawienie parametryczne. Dla krzywych płaskich postaci: x=x(t), y=y(t), t?(t1,t2) a dla

przestrzennych dodatkowo z=z(t).

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 funcji bazowych dają reprezentację krzywej.

W grafice komputerowej często ustala się funkcje bazowe i tak dobiera współczynniki, by otrzymana kombinacja

liniowa była krzywą o potrzebnych własnościach, np. kształcie.

35. Co to jest drzewo czwórkowe i do czego jest uzywane?

Drzewo czwórkowe - (ang. quadtree) struktura danych będąca drzewem, używana do podziału dwuwymiarowej

przestrzeni na mniejsze części, dzieląc ją na ćwiartki, a następnie każdą z tych ćwiartek na cztery itd.

Skończone drzewo D z korzeniem definiuje się jako niepusty, skończony zbiór etykietowanych węzłów taki, że

istnieje jeden wyróżniony węzeł nazywany korzeniem drzewa, a pozostałe węzły są podzielone na n>=0 różnych

poddrzew D1, D2, ..., Dn z korzeniami.

Podział jest kontynuowany do momentu, gdy wszyscy potomkowie są jednorodni (każdy z mniejszych kwadratów

leży całkowicie wewnątrz lub cały na zewnątrz obszaru) albo gdy rozmiary podzielonych kwadratów są odpowiednio

małe, na przykład mniejsze od wielkości piksela na ekranie. Drzewo czwórkowe reprezentujące obraz dla monitora

2n x 2n będzie miało nie więcej niż n+1 poziomów.

36. Podaj reguły na sume i przeciecie (iloczyn) dwóch obszarów plaskich opisanych za pomoca drzew

Czwórkowych

Suma:

U = S u T

Jeżeli jeden z węzłów jest lisciem czarnym to to w drzewie wynikowym U także umieszczamy czarny lisc

Jeżeli jeden z węzłów jest wezlem białym, to wezlem wynikowym będzie wezel drugiego drzewa.

Jeżeli 2 wezly sa szare to wezel wynikowy tez jest szary.

Przeciecie:

S ∩ T

Szare tak samo

Czarny to wynikowy z 2 drzewa

Jeżeli jeden bialy to wynikowy bialy

37. Podaj reprezentacje szkieletowa wieloscianu.

Jest to często stosowany sposób opisu bryly – polega na okresleniu jej drucianego szkieletu. W przypadku

wielościanu szkielet tworza krawędzie scian. Powierzchnia takiego wielościanu jest suma plaskich wielokątnych

scian. Zakladamy ze sciany przecinaja się jedynie we wspolnych krawędziach i wierzcholkach

Opisuje się je tablicami:

TW – tablica wierzchołków; zawierająca współrzędne x, y, z tych punktów; (x1,y1,z1),(x2,y2,z2)…(xn,yn,zn)

TK – Krawedzi; pary numerów wierzchołków - krawędzi; (1,2)(2,5)…(m,n)

LS – lista ścian; elementami są listy numerów krawędzi stanowiących boki ścian; (1,2,5)(5,2,7,8)…(m,n,o)

LK – lista krawędzi kolejnych ścian 3,4,3,3….X

38. Podaj idee reprezentacji bryły przez zakreslenie przestrzeni.

Przez pojecie zakreslania przestrzeni rozumiemy budowanie bryly przez przemieszczanie jej przekroju (figury

plaskiej) wzdłuż pewnej trajektorii w przestrzeni. Najprostsze to przesuniecie rownolegle lub obrot wokół prostej.

39. Podaj definicje „klocka”, „brzegu klocka” oraz jego dopełnienia (zewnetrza) stosowane w

konstruktywnej geometrii brył (ang. CSG).

Klockiem nazywamy dowolna półprzestrzeń, czyli zbior punktow (x,y,z) spełniających nierówność F(x,y,z)<0

Brzeg klocka tworza punkty dla których f(x,y,z)=0, a dopełnienie (zewnętrze) to punkty spełniające nierówność

f(x,y,z)>0

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

Jest to drzewo uporządkowane, gdzie każdy rodzic posiada 8 potomkow. Sluzy do reprezentacji objętościowej

wnętrza bryly. Obiekt przestrzenny (bryle) wpisujemy w sześcian, któremu odpowiada korzen drzewa ósemkowego.

Ten wyjściowy sześcian dzielimy na osiem mniejszych sześcianów. Jeśli mniejszy sześcian lezy całkowicie wewnątrz

bryly to reprezentującemu go synowi korzenia przypisujemy kolor czarny. Gdy caly lezy na zewnatrz bryly to kolor

bialy, sześciany niejednorodnym, tylko czesciowo zawarte w bryle dzielimi na mniejsze az do uzyskania wszystkich

potomkow jednorodnych lub mniejszych od minimalnej wielkości.

Dzialania sa analogiczne do drzew czworkowych.

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

Od tego czy wszystkie kwadraty sześciany sa jednorodne, czy jeszcze nie i można je dzielic dalej, lub od ustalonej wielkości minimalnej.

42. Opisz zwiezle operacje kodowania figury płaskiej za pomoca drzewa czwórkowego

dzielenie dzielenie dzielenie, im wiecej dzielimy tym wicej poziomow reprezentacji kolorowanie, a na koncu

numeracja zaczynając od lewego gornego rogu, pozniej prawy gorny, prawy dolny i na koncu lewy dolny, jeżeli nie sa

podzielone. Jeżeli jakis kwadrat jest podzielony na mniejsze to patrzymy numerujemy po kolei kwadraciki wewnątrz,

jeżeli nie sa podzielone na jeszcze mniejsze kwadraciki itd.

43. Czym sie rózni drzewo czwórkowe do opisu obszaru od drzewa do opisu konturu?

Do opisu obszaru uzywamy koloru:

białego – poza obszarem,

szary – czesciowo 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 sa całkowicie wewnątrz lub na zewnatrz maja kolor bialy.

44. Objasnij termin "konstruktywna geometria brył"(ang. CSG).

Oznacza metode budowania bryl w wyniku skladania ustalonych elementarnych klockow. Operace skladania to dodawanie, odejmowanie i iloczyn (czesc wspolna) zbiorow.

45. Jaka postać ma opis konstruowania sceny w CSG?

Sposób konstrukcji opisuje się drzewem, którego liśćmi są elementy podstawowe lub wielkości określające

transformacje, a węzły wewnętrzne odpowiadają działaniom na tych elementach albo transformacjom.

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

Obiekt przestrzenny (bryle) wpisujemy w sześcian, któremu odpowiada korzen drzewa ósemkowego. Ten wyjściowy

sześcian dzielimy na osiem mniejszych sześcianów. Jeśli mniejszy sześcian lezy całkowicie wewnątrz bryly to

reprezentującemu go synowi korzenia przypisujemy kolor czarny. Gdy caly lezy na zewnatrz bryly to kolor bialy,

sześciany niejednorodnym, tylko czesciowo zawarte w bryle dzielimi na mniejsze az do uzyskania wszystkich

potomkow jednorodnych lub mniejszych od minimalnej wielkości.

47. Czy możliwa jest drzewiasta reprezentacja obiektu, w której wszystkie węzły maja ten sam kolor? Ew. jaki to może być kolor? Uzasadnij.

Drzewiasta reprezentacja obiektu w ktorej wszystkie węzły maja ten sam kolor jest możliwe, ponieważ gdy wszyscy synowie maja jeden kolor, to się lacza zastępując ich ojca lisciem tego koloru. Tak wiec, gdy wszyscy potomkowie maja ten sam kolor to zostaje sam korzeń, który jest jednocześnie liściem, w

przypadku kiedy kolor tego wezla jest czarny tzn ze Obiekt pokrywa się z calym obszarem. W przypadku gdy mialby być ten kolor bialy tzn ze nie ma zadnego obiektu, wiec nie można go reprezentowac. Nie może to być tez kolor szary, ponieważ oznacza on, ze kwadat/sześcian lezy czesciowo wewnątrz obiektu, wiec jak podzielimy go na mniejsze czesci to liscie miałyby rozne kolory.

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

Metody wyznaczania zasłoniętych linii i powierzchni w istotny sposób zaleza od urządzeń graficznych na których tworzymy obraz. W przypadku monitorow ekranowych można malowac jedno na drugim, wymazywac wczesniej narysowane elementy itp. sprowadza się to wprowadzania zmian w buforze.

Metody dziela się na dyskretne (pikselowe) i analityczne. Metoda pikselowa wykorzystuje algorytm Bresenhama rysowania odcinkow i wyznacza zbiory pikseli odpowiadające widocznym fragmentom lini. Metoda analityczna niezasłonięte obszary sa okreslane analitycznie, co wymaga rozwiązywania układów rownan liniowych.

Inna klasyfikacja algorytmow jest zwiazana z przestrzenia w ktorej działają. W R3 – metody przestrzeni danych Odroznia się je od algorytmow przestrzeni obrazow, w których badane sa dwuwymiarowe rzuty elementow obiektu na płaszczyznę rysunku i dopiero gdy rzuty maja czesci wspolne rozstrzyga się zasłanianie w trójwymiarowej przestrzeni danych. Algorytmy przestrzeni danych najczęściej daja dokładne wyniki analityczne i sa na ogol kosztowne. Metody przestrzeni danych stosuje się glownie na monitorach rastrowych – niektóre z tych metod np. algorytm Watkinsa – przegladania obrazu liniami poziomymi naśladują prace takiego urzadzenia a większość uwzglednia jego rozdzielczość (algorytm z buforem głębokości) Rozne sa charakterystyki kosztu obu grup metod. Liczba działań wykonywanych w algorytmach przestrzeni danych zalezy glownie od złożoności sciany np. liczby

krawędzi obiektow wielościennych, a w metodach przestrzeni obrazu jest raczej funkcja liczby pikseli monitora.

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

Wybrane algorytmy przestrzeni danych: Algorytm Appela

-znajdujemy ściany odwrócone tyłem, pozostałe traktujemy jako potencjalnie widoczne;

-pomijamy krawędzie ograniczające tylko ściany odwrócone tyłem, resztę nazywamy istotnymi i wyróżniamy wśród

nich krawędzie konturowe - ograniczające równocześnie ściany potencjalnie widocznie i odwrócone tyłem;

-dla rzutów wszystkich istotnych krawędzi obliczamy początkową wartość ;

Wyznaczmy punkty przecięcia odcinka , t(0,1) ze wszystkimi krawędziami konturowymi i porządkujemy je tak by dla

k=1,2,…,l

niech będą punktami odpowiednio krawędzi konturowej i odcinka , których wspólnym rzutem jest ;

wartość ulega zmianie w punkcie jeśli leży bliżej obserwatora (bliżej w kierunku patrzenia). Dokładniej, dla leżących

za jest jeśli krawędź „wchodzi za ścianę”, a w przeciwnym przypadku, tzn. kiedy „wychodzi z za ściany”, jest. Chyba

się parę rzeczy zgubiło, bo ni chuja nie ma sensu

Dla obliczenia początkowej wartości można wyznaczyć punkty przecięcia wszystkich płaszczyzn zawierających

ściany potencjalnie widoczne z odcinkiem , w przypadku rzutu perspektywicznego o środku E, lub z półprostą

wychodzącą z punktu o wektorze kierunkowym równym kierunkowi rzutowania (patrzenia) i zwrocie przeciwnym, gdy

rozważamy rzut równoległy . Wielkość jest równa liczbie punktów leżących wewnątrz wielokątów .

Przy założeniu, że krawędzie ścian są uporządkowane można łatwo rozstrzygnąć, czy krawędź

„wchodzi a ścianę” czy „wychodzi zza niej”.

50. Podaj przykład działania algorytmu z przestrzeni obrazu i podaj idee jego działania.

Wybrane algorytmy przestrzeni obrazu: algorytm z buforem głębokości

Algorytm z buforem głębokości jest jednym z algorytmów najłatwiejszych do implementacji, a przy tym można go

stosować do szerokiej klasy obiektów. Służy do wyznaczania widocznych fragmentów ścian i ich wizualizacji na

urządzeniu rastrowym. Urządzenie może być np. kolorowa drukarka, jednak najczęściej korzysta się z omawianego

algorytmu przy wyświetlaniu obrazu na ekranie.

W algorytmie tym będziemy wypełniali bufor ekranu znajdując dla każdego piksela ścianę leżącą najbliżej przed nim

w kierunku patrzenia i przypisując pikselowi kolor/jasność odpowiednio fragmentu tej ściany.

Ściany rysowanego obiektu mogą być dowolnymi wielokątami, mogą mieć tez dziury i wzajemnie się przenikać.

Zakładamy, że dana jest funkcja kolor(S,x,y,z) przypisująca każdemu punktowi o współrzędnych (x,y,z) leżącemu na

ścianie S kolor/jasność.

Trzeba pamiętać że współrzędne pikselowe urządzenia graficznego są na ogół inne niż współrzędne rzeczywiste

rysowanych punktów. Odwzorowanie prostokątnego obszaru przestrzeni rzeczywistej w prostokątny obszar obrazu

na urządzeniu graficznym często określa się wzorami. Tu zakładamy, że umiemy wykonać przekształcenie odwrotne

– obliczyć współrzędne rzeczywiste punktu mając dane współrzędne pikselowe.

Przyjmujemy dalej, że rzutowanie odbywa się w przestrzeni obserwatora, a zatem współrzędne z przeciw obrazów

punktów z płaszczyzny rysunku można obliczać odpowiednio ze wzorów.

Algorytm z buforem głębokości

*inicjujemy bufor buf ekranu i tablice tab głębokości podstawiając dla wszystkich pikseli (i , j) ekranu

buf(i , j) = tło;

tab(i , j)=rmax;

wartość tło określa kolor tła obrazu, a rmax jest największa liczba rzeczywista w stosowanej arytmetyce;

*dla wszystkich ścian rysowanej sceny dla wszystkich pikseli (i , j) zawartych w rzucie obliczamy współrzędne

rzeczywiste (x,y) odpowiadające pikselowi (i , j);

obliczamy współrzędną z przeciw przeciwobrazu (x,y) leżącego na ścianie ;

jeśli z<tab(i , j), to {tab(i , j) =z; buf(i , j) = kolor(,x,y,z)}

Koszt tego algorytmu jest w przybliżeniu stały, niezależny od złożoności rysowanej sceny. Przy wzroście liczby ścian

na ogół zmniejsza się liczba pikseli zawartych w rzutach poszczególnych ścian. Statystycznie liczba wykonywanych

działań jest proporcjonalna do liczby pikseli ekranu.

Pytania spoza listy

51. Co to są współrzędne jednorodne? Zapisz w nich punkt (5,7)

Współrzędne jednorodne to sposób reprezentacji punktów n-wymiarowych za pomocą n + 1 współrzędnych.

(5,7) = (5,7,W) , gdzie W!=0

52. Zdefiniuj jednokładność o środku S =(x0, y0) i skali k≠0

Jednokładność o środku S=(x0,y0) i skali k!=0 jest takim przekształceniem płaszczyzny, w którym obrazem punktu

P=(x,y) jest taki punkt P’=(x’,y’), gdzie SP’=kSP. Stąd np. dla x mamy: x0-x’=k(x0-x). Zatem

(x’,y’)=(x0,y0)+k(x-x0,y-y0) = (kx,ky)+(x0-kx0,y0-ky0)

53. Zdefiniuj ostrosłup widzenia i podaj jego zastosowanie

Jest to ostrosłup zdefiniowany przez wirtualną kamerę, w obrębie którego znajdują się obiekty widoczne w danym

rzucie. Dzięki temu możemy „postawić” obserwatora w każdym punkcie obrazu uzyskując różne widoki np. z lotu

ptaka.

54. Podaj koncepcje działania algorytmów określania położenia punktu P względem wielokąta W

Z punktu P prowadzimy dowolną półprostą l, znajdujemy liczbę przecięć tej półprostej z bokami wielokąta W, gdy

liczba jest nieparzysta to punkt leży wewnątrz niego, gdy parzysta - na zewnątrz. Jeżeli prosta przechodzi przez

wierzchołek B wielokąta będący wspólnym końcem boków AB i BC i jeśli A i C leżą po różnych stronach l, to liczymy

takie przecięcie jako jednokrotne, a gdy A i C leżą po tej samej stronie to liczymy je podwójnie, tak samo jest gdy

prosta przylega do jednej z krawędzi wielokąta.

55. Podaj ideę obrotu punktu P(x, y, z) o kąt φ dookoła prostej w

przestrzeni 3W

Niech P(x,y,z) będzie macierzą przesunięcia o wektor [x,y,z], a R (β,u) macierzą obrotu o kąt α wokół osi u. Przy

takich oznaczeniach macierz obrotu wokół danej osi jest iloczynem:

P(-x1,y1,-z1)R(-α,y)R(β,z)R(α,x)R(-β,z)R(α,y)P(x1,y1,z1)

56. Co to jest drzewo konstrukcji?

Drzewem konstrukcji nazywamy drzewo, którego liśćmi są elementy podstawowe lub wielkości określające

transformacje, a węzły wewnętrzne odpowiadają działaniom na tych elementach (dodawaniu, odejmowaniu,

przecięciu) albo transformacjom (obrotowi, przesunięciu, skalowaniu).

57. Podaj wzory na prostą i płaszczyznę 3W, współrzędne punkty wspólnego płaszczyzny i prostej oraz

krawędzi dwóch płaszczyzn.

Równanie prostej przechodzącej przez dwa punkty P1 = (x1,y1,z1) i P2 = (x2,y2,z2) możemy zapisać w postaci

układu zależności, które spełniają współrzędne każdego punktu P = (x,y,z) należącego do tej prostej

P(t)= P1 +tk , t ε (-∞,+∞), k= P2-P1

Równanie płaszczyzny: xnx+yny+znz=c

58. Zdefiniuj symetrię względem płaszczyzny oraz przekształcenie 3-punktowe.

Przekształcenie trzypunktowe:

Dane są dwie trójki 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ę wyznaczoną punktami Q1, Q2, Q3

Symetria względem płaszczyzny - Dla danego punktu P = (x,y,z) szukamy punktu P'=(x',y',z') symetrycznego

względem płaszczyzny ax+by+cz=d. Wektor [a,b,c]jest prostopadły do tej płaszczyzny, a więc rzut prostopadły Q

punktu P na nią jest postaci Q=P+t[a,b,c].