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’)
...
monibach