Odpowiedzi do 55.pdf

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 zwiazki miedzy terminami: jezyk 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 zwiazki miedzy terminami: konsola graficzna, generator wektorów, generator znaków,

generator krzywych, drazek sterujacy, manipulator kulowy, pióro swietlne, 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).

Drazek sterujacy – manipulator, zmienia ustawienie 2 potencjometrow, które okreslaja wspolrzedne 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łuzy do umiejscowienia elementu na ekranie

Rysownica – chyba chodzi o tablet ;) – wskazuja cale linie (piora świetlne tylko punkt). Powierzchnia takiego

urzadzenia jest najczęściej odwzorowana na monitorze a wyswietlany znacznik wskazuje polazenie sondy która

użytkownik przesuwa po urzadzeniu.

5. Podaj definicje siatki generacyjnej, modułu siatki i jej rzedu spójnosci.

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

Siatka Generacyjna – jest to zbior wspolrzednych całkowitych danego urzadzenia graficznego (Uklad

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

Modul siatki – Chuj wie :D może chodzi o sposób wybierania sąsiednich pikseli – wybor czterokierunkowy i

ośmiokierunkowy

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

koniecznosc generowania linii na siatkach generacyjnych?

Koncami rysowanego odcinka (krzywej) sa punkty o współrzędnych pikselowych (x0,y0) i (xk, yk)

W zależności od wyborupiskeli czterokierunkowych lub osmiokierunkowych wybieramy kolejny piksel ten którego

srodek lezy najbliżej odcinka(krzywej).

Koniecznosc – chodzi chyba o to ze współrzędne pikselowe roznia się się od wspolrzendych rzeczywistych i jak

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

7. Podaj we współrzednych jednorodnych zapis operacji na punkcie: przesuniecia, obrot wokół P=(0,0) i

P=(x0,y0) // (normalny obrot 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 wokol 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 oknowanie i obcinanie; podaj co to sa współrzedne znormalizowane i do

czego one słuza .

Okienkowanie – wyizolowanie dowolnej części wyswietlonego 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 wspolrzednych urzadzenia graficznego.

Wspolrzedne znormalizowane –

Często przejscie od współrzędnych rzeczywistych do współrzędnych danego urzadzenia 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 urzadzenia.

9. Zdefiniuj operacje jednokładnosci i powinowactwa prostokatnego oraz omów ich podobienstwa, róznice

i ich szczególne przypadki.

- Jednokladność

Jednokladnoscia o srodku 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 przeksztalcenie takie jest symetria o srodku 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 prostopadly do prostej ax+by+c=0. Punkt Q jest zatem rowny P+t[a,b] dla pewnej wartości

parametru t. Wartosc t wyznaczamy z warunku, ze Q lezy 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 przeksztalceniu obrazem punktu P ma być punkt P’ spełniający zależność QP’=kQP, a wiec

P’=Q+k(P-Q). Ze wzorow 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 prostokatnego okna i jego trzy

pierwsze kroki; podaj w jakich współrzednych działa ten algorytm i dlaczego?

Nie jest istotne, czy obcinanie wykonujemy w przestrzeni danych rzeczywistych, czy w przestrzeni obrazu. Niech

prostokat (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 lezy on wewnątrz zadanego prostokata. W

przypadku odcinka proces obcinania nie jest az tak trywialny.

Algorytm Cohena-Sutherlanda

Kazdemu koncowi przypisujemy kod czterobitowy określający polozenie tego punktu wzglegem prostokątnego okna

Kod(P)= b 4 b 3 b 2 b 1

b 1 = 1 gdy P lezy na lewo od okna

b 2 = 1 gdy P lezy ma prawo od okna

b 3 = 1 gdy P lezy poniżej okna

b 4 = 1 gdy P lezy powyżej okna

b 1 jest bitem znaku x- x min , b 2 i b 3 odpowiednio xmax-x i y- y min , a b 4 jest bitem znaku y max -y.

Punkt P=(x,y) lezy wewnątrz okna jeśli spełnione sa nierownosci

( y min =< x =< x max → y min =<y=< y max )

a wtedy kod(P)=0000. Odcinek P 1 P 2 lezy całkowicie wewnątrz okna, gdy kod ( P 1 ) = kod( P 2 ) = 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 zastepowany punktem przecięcia badanego odcinka z prosta zawierajaca

jeden z bokow okna. W ten sposób odrzuca się fragment odcinka lezacy na zewnatrz okna. Nastepnie pozostala

czesc odcinka jedt obcinana prostymi zawierającymi inne boki. Postepowanie kontynuuje się do momentu gdy caly

odcinek może być pominiety lub gdy znajdziemy jego fragment lezacy wewnątrz okna. Wybor kolejnych bokow okna

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

11. Podaj definicje wielokatów: dowolnego, zwykłego, monotonicznego, wklesłego i wypukłego; podaj

nazwy i koncepcje działania znanych ci algorytmów okreslania połozenia punktu wzgledem wielokata.

Wielokaty zwykle – takie których krawędzie nie maja punktow wspolnych roznych od wierzcholkow.

Monotoniczny – jeżeli przy odpowiedniej numeracji wierzcholkow, możemy podzielic brzeg wielokata na 2 lancuchy

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

samo jak tworzące je wierzcholki.

Wypukly – jeżeli dla każdych 2 punktow bedacych wewnątrz wielokata i caly odcinek łączący te 2 punkty lezy

wewnątrz tego wielokata.

Wklesly – jeżeli istnieje taka para punktow znajdujących się wewnątrz wielokata dla ktorych odcinek łączący je nie

leży całkowicie wewnątrz tego wielokata

Algorytmy sprawdzania czy punkt P lezy wewnątrz wielokata W.

I.Algorytm parzystości.

Z punktu P prowadzimy dowolna polprosta l, dla prostoty np. na prawo rownolegle do osi x;

Znajdujemy liczbe ‘np’ przeciec tej półprostej z bokami wielokata;

Jeśli liczba ‘np’ jest parzysta to P lezy na zewnatrz wielokata W, a gry nieparzysta to wewnątrz.

-algorytm nie obejmuje przypadkow szczególnych. Jednym z nich jest przechodzenie półprostej przez wierzcholek.

Innym to polprosta zawiera bok wielokata

II. obliczanie sumy katow miedzy półprostymi prowadzonymi z punktu P przez wierzcholki P i wielokata.

Zakladamy ze wierzcholki sa uporządkowane odwrotnie do ruchu wskazowek zegara. Niech α i oznacza kat miedzy

PP i PP i+1. Jeżeli uporządkowanie ramion jest zgodne z ruchem wskazowek zegara to kat ma znak +, w przeciwnym

przypadku - .

12. Sformułuj zadanie i ogólne warunki trójkatowania wielokata, warunki trójkatowania naturalnego oraz

podaj idee trójkatowania wielokata monotonicznego.

Triangulacja wielokątów

Jest to podzial wielokata na trojkaty, ulatwia rozwiązywanie wielu zadan. Naleza do nich wypelnianie obszarow,

okreslanie zasłaniania i oświetlania obiektow twojwymiarowych, a także wyznaczanie linii i ich przecięcia. Dla

efektywności tych zastosowan wazne jest by liczba składowych trójkątów była jak najmniejsza i by nie było trzeba

definiowac nowych danych.

Zadanie triangulacji formuluje się jako podzial wielokata zwykłego na sume nie nakładających się na siebie trójkątów

których wierzcholkami moglu być tylko wierzcholki danego wielokata.

Interesuje wiec nas podzial n-kata (np. piecio-kata) na n-2 liczbe trójkątów.

Dla niektórych wielokątów triangulacja jest bardzo latwa, np. kiedy wielokat jest wypukly, wówczas wystarczy

polaczyc wierzcholek z pozostałymi.

13. Podaj definicje: zbioru wypukłego punktów i powłoki wypukłej oraz wymien (3) główne kroki

algorytmu Grahama wyznaczania powłoki wypukłej

Wyznaczanie powloki wypuklej zbioru punktow.

Zbior Z nazywamy wypukłym jeśli zawiera wszystki odcinki, których koncami sa dowolne punkty ze zbioru Z.

Powloka wypukla zbioru punktow nazywamy najmniejszy(w sensie zawierania) zbior wypukly do którego naleza

dane punkty. Powloka wypukla n punktow jest wielokątem.

Algorytmy związane z wyznaczaniem powloki wypuklej.

-Algorytm Grahama wyznaczania powloki wypuklej n punktow

-Algorytm Greena i Silvermana wyznacznia powloki wypuklej zbioru punktow

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

Dane: punkty P i =(x i ,y i ), , i=1,2,...,n;

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

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

ctg(Pα i ) = (x i -x i1 )/(y i -y i1 ) . Otrzymujemy nowe uporządkowanie, oznaczamy je jako i 1 , i 2 , ..., i n .

3) tworzymy listę P l1 , P l2 , ... , P lk wierzchołków wielokąta będącego powłoką wypukła następująco:

- na początku przyjmujemy: l 1 =i 1 , l 2 =i 2 , l 3 =i 3 i podstawiamy k=3,

- dla j=4,5,...,n; l j =i j

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

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

w przeciwnym razie dopisujemy P ij do listy, czyli podstawiamy k=k+1, l k =i j .

14. Podaj idee algorytmu Sutherlanda-Hodgmana obcinania wielokata do prostokatnego okna.

Wierzcholki sa uporządkowane odwrotnie do kierunku wskazowek zegara, porownuje się wierzcholki kolejno z

bokiem okna i tworzy z nich nowy ciag określający wielokat obcięty danym bokiem. Wierzcholki leżące wewnątrz

okna staja się elementami ciagu, a te na zewnatrz sa odrzucane. Na koniec laczymy wg kolejnosci niepolaczone ze

soba wierzcholki bokami okna.

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

Niech będą wielokaty P i Q o wierzcholkach uporządkowanych odwrotnie do kierunku wskazowek zegara. Przez

wierzcholki prowadzimy pionowe linie dzielace ten wielokat na trapezy i trojkaty. Nastepnie wyznaczamy czesci

wspolne dla conajwyzej n+m trapezow (trójkątów).

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: