1. W jakim celu wprowadzono zunifikowane jednostki cieniowania w najnowszej wersji biblioteki DirectX 10?

Pod zunifikowaną architekturą jednostki shadera nie pracowalyby niezależnie, a zmiast tego współpracowałyby nad zadaniem. Takie podejście nie tylko zwiększa efektywność ale również poprawia osiągi. Inżynierowie ATI którzy stworzyli Xbox-owe GPU Xenos, opracowali architekturę GPU która łączy vertex i pixel shadery w zunifikowane banki shaderów, obsługujące rendering. Znacząco poprawia to efektywność, przez co relatywnie poprawiając wydajność. Jak można sobie wyobrazić kluczem do zunifikowanej architektury jest kontroler, który może efektywnie alokować zadania dla jednostek shaderów.

Pomysł jest bardzo prosty: stworzyć jednostki, które będą w stanie wykonywać zadania zarezerwowane dotychczas dla Pixel Shaderów jak i Vertex Shaderów. I tak oto powstały zunifikowane shadery, które zajmują się przede wszystkim wykonywaniem kodu, za który dotychczas odpowiedzialne były osobne jednostki: PS oraz VS.

Takie rozwiązanie niesie za sobą niemalże same korzyści: programista ma do dyspozycji kilkadziesiąt wielozadaniowych jednostek i w zasadzie może za ich pomocą zrobić niemalże wszystko, gdyż jednostki te potrafią wykonywać nie tylko typowe obliczenia matematyczne charakterystyczne dla programów cieniujących, a również obliczać fizykę, czyli to czym dotychczas zajmował się procesor, a od niedawna akcelerator fizyki AGEIA PhysX.

2. Wymień i krótko opisz tryby pracy SLI i CrossFire.
SLI (Scan Line Interleave - Przeplot Skanowania Linii bądź Scalable Link Interface - Interfejs Skalowalnego Łącza) - technologia pozwalająca na skorelowanie pracy dwóch (lub trzech) kart graficznych celem szybszego renderowania obrazu.

SLI wykorzystuje dwie metody renderingu - pierwsza z nich polega na asymetrycznym podziale obrazu na dwie części, równe pod względem złożoności generowanego obrazu. Według specyfikacji NVIDII algorytm zajmujący się tym podziałem analizuje liczbę wielokątów, geometrię oraz kod jednostek Pixel i Vertex Shader w każdej z części podzielonego obrazu. Sprawia to, że każda z kart generuje pewną część klatki w tym samym czasie - każda z nich ma do wykonania teoretycznie tą samą ilość obliczeń, co z założenia wyeliminować ma taką sytuację, że jedna z kart jest w trakcie generowania obrazu, podczas gdy druga już tego dokonała. Drugą metodą jaką zastosowała NVIDIA jest rendering naprzemiennych klatek (AFR), gdzie jedna karta zajmuje się renderowaniem klatek parzystych a druga nieparzystych. Dobór metody renderowania obrazu jest uzależniony od tytułu i zawarty jest w sterownikach.

CrossFire, CrossFireX (dla platformy Spider) - marketingowa nazwa technologii graficznej opracowanej przez firmę ATI. W podwójnej konfiguracji, dzieli ona obraz idący do pierwszej karty graficznej (master) tak, że mniej więcej połowa (w zależności od konfiguracji) trafia do karty wspomagającej (slave). Umożliwia to znaczne przyśpieszenia aplikacji 3D.

3. Czym różni się rzutowanie ortograficzne od perspektywicznego?
Rzut ortograficzny - promienie rzutujące są oddalone w nieskończoność od obiektu.
Rzut perspektywiczny - środek rzutowania w skończonej odległości od płaszczyzny rzutowania

Podczas rzutowania ortogonalnego tworzonej sceny na płaszczyznę ekranu definiujemy bryłę obcięcia, którą w tym przypadku jest prostopadłościan. Wszstkie obiekty, które znajdą się w jego wnętrzu zostaną zrzutowane na ekran z zachowaniem ich rozmiarów - niezależnie od ich odległości od obserwatora, natomiast podczas rzutowania perspektywicznego tworzonej sceny na płaszczyznę ekranu również definiujemy bryłę obcięcia, którą tym razem jest ostrosłup ścięty. Wszstkie obiekty, które znajdą się w jego wnętrzu zostaną zrzutowane na ekran z zachowaniem zasad perspektywy.

A - rzut perspektywiczny, b - rzut równoległy

4. Jakie rodzaje światła wyróżniamy w OpenGL? Jakie są rodzaje źródeł światła?

OpenGL wykorzystuje lambertowski model światła, co oznacza, że źródła światła określane są za pomocą trzech składowych R (od angielskiego red), G (green) i B (blue), definiujących barwę promieni.
Ponadto każde źródło światła możemy opisać za pomocą trzech odmiennych rodzajów oświetlenia:
GL_AMBIENT - światło otaczające - nie pochodzi z żadnego kierunku, choć ma źródło. Wszystkie obiekty na scenie są nim równomiernie oświetlone ze wszystkich stron i na wszystkich powierzchniach.
GL_DIFFUSE - światło rozproszone - ma zdefiniowane źródło i z tego kierunku pochodzi. Jasność powierzchni zależy od kąta, pod jakim pada na nią światło. Światło rozproszone padające jest traktowane jako kierunkowe, w przypadku światła odbitego już jako bezkierunkowe.
GL_SPECULAR - światło odbłysków - ma kierunek i jest odbijane od powierzchni w jedną stronę.

• Kierunkowe - działające na całej scenie bez względu na pozycję,

• Stożkowe - tworzące snop światła o podanym kierunku i kącie stożka,

• Punktowe - działające w podanej pozycji równomiernie w każdym kierunku.

5. Proszę opisać listy wyświetlania i tablice wierzchołków. Do czego służą? Jakie są przewagi list, a jakie tablic? Jakie inne metody optymalizacyjne udostępnia OpenGL?

• Listy wyświetlania są dobrym sposobem optymalizacji, ale nie są rozwiązaniem uniwersalnym.

• Listy wyświetlania najlepiej stosować do zmian stanu renderowania, np. zmiany ustawień świateł.

• List wyświetlania nie da się stosować do dynamicznych obiektów, tzn. obiektów zmieniających kształt.

• Nawet dla obiektów o niezmiennym kształcie bardziej atrakcyjne mogą okazać się tablice wierzchołków.

• Lista wyświetlania to bardzo ważna i efektywna metoda optymalizacji czasowej w OpenGL.

• Lista wyświetlania to w istocie makro zawierające polecenia OpenGL, jednak są to polecenia w formie skompilowanej. Mamy tu więc do czynienia z załadowaniem do bufora wielu poleceń naraz bez potrzeby zamiany ich na formę zrozumiałą dla sterownika graficznego (skompilowaną).

• Zastosowanie list wyświetlania jest bardzo proste.

• Stosowanie list wyświetlania powinno stać się nawykiem każdego programisty OpenGL, chociaż nie we wszystkich przypadkach są one najlepszym wyjściem.

• Listy wyświetlania są dobrym sposobem optymalizacji, ale nie są rozwiązaniem uniwersalnym.

• Listy wyświetlania najlepiej stosować do zmian stanu renderowania, np. zmiany ustawień świateł.

• List wyświetlania nie da się stosować do dynamicznych obiektów, tzn. obiektów zmieniających kształt.

• Nawet dla obiektów o niezmiennym kształcie bardziej atrakcyjne mogą okazać się tablice wierzchołków.

• Kolejną metodą optymalizacji dostępną w OpenGL są tablice wierzchołków.

• Ich podstawowe przeznaczenie jest podobne do list wyświetlania:

• podawanie danych geometrii w dużych paczkach,

• ograniczenie do współrzędnych wierzchołków i ich własności.

• Użycie tablic wierzchołków pozwala zastąpić specyfikację pojedynczych wierzchołków funkcję glVertex odwołaniami do wcześniej przygotowanych tablic.

• Dodatkową zaletą stosowania tablic wierzchołków jest skrócenie kodu programu.

• Stosowanie tablic wierzchołków nie wyklucza stosowania funkcji glVertex.

• Stosowanie tablic wierzchołków sprowadza się do wykonania następujących kroków:

• włączenie obsługi określonego typu tablicy wierzchołków (jednej lub kilku),

• przygotowanie (utworzenie i wypełnienie danymi) wskazanych tablic,

• specyfikowanie wierzchołków jako pozycji w tablicach,

• usunięcie tablic.

• Włączenie i wyłączenie obsługi tablic wierzchołków z zastosowaniem funkcji:

• glEnableClientState, glDisableClientState

• GL_VERTEX_ARRAY - tablica współrzędnych wierzchołków.

• GL_COLOR_ARRAY - tablica kolorów wierzchołków,

• GL_SECONDARY_COLOR_ARRAY - tablica drugich kolorów wierzchołków,

• GL_EDGE_FLAG_ARRAY - tablica znaczników krawędzi wierzchołków,

• GL_FOG_COORDINATE_ARRAY - tablica współrzędnych wierzchołków mgły,

• GL_NORMAL_ARRAY - tablica normalnych wierzchołków,

• GL_TEXTURE_COORD_ARRAY - tablica współrzędnych tekstury wierzchołków,

Wskazanie tablic współrzędnych, kolorów i tekstur wierzchołków:

• glVertexPointer(size, type, stride, array),

• glColorPointer(size, type, stride, array),

• glTexCoordPointer(size, type, stride, array).

Wskazanie innych typów tablic:

• glNormalPointer(type, stride, array).

• glEdgeFlagPointer(stride, array).

• glFogCoordPointer(type, stride, array).

glInterleavedArrays - tablica łącząca różne dane wierzchołków (!!!)

Do rysowania tablic wierzchołków w trybie nieindeksowanym służą dwie funkcje:

• glArrayElement(index)

• funkcji używa się w połączeniu z glBegin i glEnd,

• rysuje jeden element z tablic(y)

• glDrawArrays(mode, first, count)

• funkcja rysuje dane z całej tablicy lub jej fragmentu,

• poza glBegin i glEnd,

• parametr mode określa rodzaj rysowanych prymitywów,

• rysowane jest count elementów licząc od first.

---- Inne metody optymalizacyjne

• Tablice indeksowane

• Użycie indeksów wierzchołków

• Bufory

• Tablice mapowane na pamięć karty graficznej - brak przesyłu danych między pamięcią CPU a GPU

• Metody algorytmiczne, np. wycinanie niewidocznych powierzchni
  

6. Na jakie trzy grupy dzielą się systemy cząsteczkowe? Do jakiej grupy należą systemy mas i sprężynek?
Do jakiej grupy należą efekty cząsteczkowe?

• Systemy cząsteczkowe można podzielić na 3 grupy:

• Systemy strukturalne (Structured Systems) - cząsteczki w takich systemach są statyczne (np. drzewa, chmury, itp.)

• Systemy stochastyczne (Stochastic Systems) - cząsteczki ruchome z elementami losowymi (np. ogień, śnieg, itp.) - tu cząsteczkowe efekty

• Systemy zorientowane (Oriented Systems) - cząsteczki tworzą grupy, w których „pracują” połączone ze sobą w pewien sposób (np. ciała plastyczne, tkaniny, itp.) - tu SA masy i sprężynki

7. Wymień, jakie dwie grupy sił są stosowane w dynamice efektów cząsteczkowych. Podaj po dwa przykłady każdej z nich.

• Stałe w całym środowisku - przyspieszenie uzyskiwane przez cząsteczkę pod wpływem takiej siły zależy od wartości jakiegoś specyficznego parametru np. masy w przypadku pola grawitacyjnego

• O określonej domenie działania - takie siły posiadają źródło i zasięg. Jeżeli cząsteczka znajduje się poza zasięgiem siły, nie ma ona na nią żadnego wpływu, natomiast jeżeli cząsteczka dostanie się w pole oddziaływania, jej ruch zmienia się w zależności od rodzaju siły, np. przyciąganie/odpychanie (Attract, Attract Line)

8. Podaj przynajmniej dwa z podstawowych sposobów reprezentacji cząsteczek w komputerowej grafice trójwymiarowej. Podaj ich zalety oraz wady.
Point sprite - punkt
+ brak konieczności transformowania
+ mały rozmiar
- zawsze „kwadratowe”
- ograniczony rozmiar
- brak możliwości określenia rotacji
Billboard - dwa trójkąty
+ dowolność transformowania
+ dowolność kształtu
- rozmiar cząsteczki
Konieczność liczenia transformacji
Mesh - siatka 3D
+ oświetlanie obiektów rozmytych
+ cienie
+ lepsze wrażenie objętości
+ tzw. „megaparticles”
- szybkość działania
- wielkość danych

9. Wyjaśnij pojęcia „szkielet” i „kość”.

Szkielet animacyjny: łańcuch kości połączonych węzłami (stawami). Ten składający się zwykle najwyżej z kilkunastu wektorów szkielet łączy się z powłoką w procesie zwanym powlekaniem

Łączenia hierarchicznego używa się do powiązania ze sobą poszczególnych segmentów postaci lub kości szkieletu

Hierarchia pozwala określić zależności pomiędzy obiektem będącym „rodzicem” i obiektem będącym „dzieckiem”

• W tej technice istnieją dwa sposoby animowania:

• animowanie sekwencyjne (forward kinematics) - występuje, gdy poruszając obiektem rodzicem, porusza się również jego dziećmi;

odwrotna kinematyka (inverse kinematics) - występuje, gdy przemieszczające się obiekty dzieci pociągają za sobą obiekty będące ich rodzicami.

Kości (bones) to modyfikatory pozwalające łączyć się w hierarchię i umożliwiające animowanie obiektów do nich “podłączonych”. Są to tzw. pomocniki, które nie są renderowane, natomiast umożliwiają nam pełną kontrolę nad obiektem.

Szkielet składa się z kości.

10. Opisz krótko budowę modelu trójwymiarowego.

Pod pojęciem modelu trójwymiarowego należy rozumieć każdy obiekt, który może zostać umieszczony na scenie trójwymiarowej. Dokładny opis modelu wymaga zdefiniowania następujących elementów:

- wierzchołek - punkt w przestrzeni trójwymiarowej; poza trzema współrzędnymi związane z nim są dodatkowe informacje, takie jak współrzędne wektora normalnego

do powierzchni, w skład której wchodzi dany wierzchołek,

- siatka - zbiór wierzchołków pogrupowanych w trójkąty. Jest podstawowym elementem opisującym kształt i wygląd modelu. Na jej podstawie określane są

interakcje modelu z otoczeniem. Z siatką związane są dodatkowe informacje określające wygląd modelu oraz sposób wyświetlenia siatki na scenie.

Sam model może się składać z więcej niż jednej siatki.

11. Opisać różnicę pomiędzy kinematyką prostą a odwrotną.

Kinematyka prosta: jest to najprostsza metoda zrealizowania animacji w czasie rzeczywistym. Może posłużyć do wyłącznie do realizacji najbardziej podstawowych animacji jak obracanie się lub nachylanie głowy. Polega na obróceniu zadanej kości o określoną rotację w sprecyzowanym przedziale czasu. Jest to rotacja podana względem rodzica i modelu.

Kinematyka odwrotna: Zadanie przesunięcia określonej kości w pobliże zadanego punktu realizowane jest przez kwaternionową wersję Cyclic Coordinate Descent. Jego analityczne rozwiązanie nie jest możliwe ze względu na istnienie wielu rozwiązań dla identycznych danych wejściowych. Jest to wydajny algorytm iteracyjny i heurystyczny znajdujący rozwiązanie z określonym błędem.

12. Podać algorytm modyfikacji wierzchołków modelu w animacji szkieletowej.

• Dla każdego wierzchołka określamy:

• n (>= 1) kości, które wpływają na wierzchołek

• n wag wpływów sumujących się do 1

• W każdej klatce animacji

• aktualizujemy stan szkieletu

• dla każdego wierzchołka

• obliczamy transformację i-tą kością aż do n

• sumujemy wyniki mnożąc je przez wagi wpływów

• Wynik - transformacja wierzchołka w układzie odniesienia modelu

13. Wymień znane Ci metody reprezentacji w trój wymiarze. Podaj zalety i wady reprezentacji kwaternionowej.

Rodzaje reprezentacji w trój wymiarze:
- Rotacja jako macierz 3x3
- Rotacja jako kąty Eulera
- Rotacja jako para oś-kąt
- Kwaterniony

Kwaterniony zalety / wady:
+ Brak osobliwości matematycznych,
+ Łatwa interpolacja (SLERP),
+ Wydajna kompozycja (mnożenie) kwaternionów
+ Łatwa normalizacja (zapobiega błędom obliczeń)
- Mało intuicyjna reprezentacja,
- Dualizm reprezentacji: Q i -Q to ta sama rotacja

14. Co to jest DirectX?

DirectX to zestaw funkcji API wspomagających generowanie grafiki (dwu- i trójwymiarowej), dźwięku oraz innych zadań związanych zwykle z grami i innymi aplikacjami multimedialnymi.

Finalna czysto 32-bitowa wersja DirectX 9.0c pochodzi z 13 grudnia 2004 roku i ma rozmiar tylko 33.6 MB. Bezpośrednio następujące po niej kolejne uaktualnienie DirectX 9.0c z 9 lutego 2005 już zawiera niewielkie zaczątki technologii 64-bitowej. Obecnie dostępna 64-bitowa wersja DirectX 9.0c ma już około 60 MB i jest zbędna dla użytkowników 32-bitowych Windows.

Najczęściej wykorzystywane do obsługi grafiki w grach komputerowych. Używane również do pisania programów do specyficznych zadań z wykorzystaniem np. grafiki trójwymiarowej (np. symulacja komputerowa itp.). DirectX jest produktem firmy Microsoft, dostępny tylko na platformę Windows oraz konsolę Xbox. Obecnie dostępna jest wersja DirectX 10, która została udostępniona wraz z premierą systemu operacyjnego Microsoft Windows Vista. Działa tylko na Windows Vista. Jest także wersja DirectX 10.1 wspomagana jednak tylko przez Windows Vista i karty graficzne z chipsetem ATI. Na tegorocznym Gamefast zapowiedziana została wersja jedenasta, która ma być w pełni kompatybilna z DirectX 10. DirectX 11 będzie dostępny z Windows 7, oraz z Windows Vistą. DirectX 11 będzie dostarczany do Visty przez dodatek SP2.

15. Wymień najważniejsze wady i zalety DirectX.

+ możliwość przeniesienia na XBOX'a
+ łatwość w pisaniu jednocześnie pod wiele typów kart graficznych
+ obiektowe API poprawia czytelność i zrozumiałość kodu
+ proste i zrozumiałe API, po pokonaniu pierwszych trudności
+ wygodny dostęp do wielu funkcji kart
- mniejsza liczba gotowych przykładów w sieci
- zabawa z odświeżaniem zasobów

16. [*] Przedstaw następujące barwy w modelu RGB podając wartości składowych R, G, B przy założeniu, że każda ze składowych przyjmuje wartości 0 - 255:

Wartości składowych w nawiasach oznaczają kolejno wartości dla modelu R,G,B
(R,G,B)

• Czarny (0,0,0)

• Biały (255,255,255)

• Zielony (jaskrawy o pełnym nasyceniu) (0,255,0)

• Żółty (jaskrawy o pełnym nasyceniu) (255,255,0)

Czy model barw RGB umożliwia oddanie pełnego spektrum barw widocznych dla człowieka?

Nie, model barw umożliwia tylko oddanie fragmentu spektrum barw widocznych dla człowieka.

17. [**] Omów czym są oraz do czego służą: BSDF, BRDF, BTDF.

BSDF: BRDF + BTDF

Generalnie chodzi o rozproszenie światła na płaszczyźnie - przenikanie (transmittance), odbicie (reflect),

BSDF - (Bidirectional scattering distribution function) Most often it is used to name the general mathematical function which describes the way in which the light is scattered by a surface.

BRDF (Bidirectional reflectance distribution function) is a simplified BSSRDF, assuming that light enters and leaves at the same point - odbicie swiatła od powierzchni.

BTDF (Bidirectional transmittance distribution function) is similar to BRDF but for the opposite side of the surface. - przenikanie swiatla przez powierzchnie.

18. [***] Omów pokrótce algorytm raytracingu. Odpowiedź zilustruj.

Algorytm ray tracingu przebiega następująco:

1. Z punktu w którym znajduje się obserwator wyprowadzany jest promień pierwotny; promień przecina rzutnię.

2. Wyszukiwany jest najbliższy punkt przecięcia z obiektami znajdującymi się na scenie.

3. 
   Następnie dla każdego światła zdefiniowanego na scenie wyznaczana jest jasność w tym punkcie, zgodnie z określonym modelem oświetlenia (np. Lamberta czy Phonga).
   Najczęściej także określa się cienie - w tym celu jest testowana widoczność źródła światła z danego punktu, tj. czy światło nie jest przesłaniane przez jakiś obiekt i jeśli nie - dopiero wówczas wyliczana jest jasność punktu dla tego źródła.

W algorytmie rekurencyjnym dochodzi jeszcze jeden warunek:

1. Jeśli punkt przecięcia należy do obiektu odbijającego światło lub przezroczystego, wysyłane są z tego punktu promienie wtórne - odpowiednio, promień odbity lub promień załamany - i algorytm rekursywnie powtarza się od drugiego kroku (w większości programów można ograniczyć liczbę zejść rekurencyjnych). Kolor punktu wyznaczany jest dopiero, gdy znane są wyniki przetwarzania promieni wtórnych; zwykle projektant podaje procentowo wpływ kolorów z promieni wtórnych, tj. określa jak bardzo obiekt odbija/załamuje światło.

Algorytm ray tracingu stosuje się dla wszystkich pikseli obrazu; aby uniknąć aliasingu przez jeden piksel przeprowadza się więcej niż jeden promień.

Bardzo dużą zaletą tej metody jest łatwość zrównoleglania programów - każdy promień pierwotny może być przetwarzany niezależnie od innych; podobnie promienie wtórne są od siebie niezależne.

19. [**] Opisz, jaka jest różnica między modelem oświetlenia globalnego a modelem oświetlenia lokalnego? Dodatkowo opisz, jaka będzie wizualna różnica sceny renderowanej z wykorzystaniem każdego z tych modeli oświetlenia w przypadku, gdy w scenie będziemy mieli biała kulę leżącą na czerwonej płaszczyźnie, całość oświetlona białym światłem od góry.

Global Illumination (oświetlenie globalne) to w grafice 3D model oświetlenia, w którym każdy obiekt na scenie oświetlany jest zarówno przez światło emitowane bezpośrednio ze źródła światła, jak również przez światło odbite od innych obiektów na scenie (w przeciwieństwie do oświetlenia lokalnego, gdzie obiekty oświetlane są wyłącznie bezpośrednio przez źródło światła). Taki model oświetlenia wymaga zastosowania algorytmów, które są znacznie wolniejsze niż algorytmy oświetlenia lokalnego, jednak pozwala uzyskać znacznie większy stopień realizmu. Przykładowe algorytmy (techniki renderingu) realizujące oświetlenie globalne to mapowanie fotonowe, path tracing, radiosity, Metropolis Light Transport.

20. [**] Dane jest analityczne równanie prostej promienia:

x = x₀ + x_dt

y = y₀ + y_dt

z = z₀ + z_dt

(gdzie O - współrzędne punktu początkowego, D - wsp. wektora kierunkowego, t - skalarna wartość czasu).

Dane jest analityczne równanie kuli:

(x - x_c)² + (y - y_c)² + (z - z_c)² = S_r²

(x_c, y_c, z_c - współrzędne punktu środka kuli, S_r - promień kuli).

Znaleźć równanie opisujące punkt przecięcia promienia i kuli oraz przedstawić je w postaci

At² + Bt + C = 0

i podać wartości współczynników A, B, C.

Należy znaleźć t dla których promień znajduje się na kuli. Wstawiamy równanie promienia do wzoru kuli.

(x₀ + x_d t - x_C)² + (y₀ + y_d t - y_C)² + (z₀ + z_d t - z_C)² = S_r²

(x₀ - x_C)² + 2 x_d (x₀ - x_C) t + x_d² t² + (y₀ - y_C)² + 2 y_d (y₀ - y_C) t + y_d² t² + (z₀ - z_C)² + 2 z_d (z₀ - z_C) t + z_d² t² + - S_r² = 0

(x_d² + y_d² + z_d²) t² + (2 (x_d (x₀ - x_C) + y_d (y₀ -y_C) + z_d (z₀ - z_C)) t + ((x₀ - x_C)² + (y₀ - y_C)² + (z₀ - z_C)²) - S_r² = 0

Zatem:

A = x_d² + y_d² + z_d²

B = 2 (x_d (x₀ - x_C) + y_d (y₀ -y_C) + z_d (z₀ - z_C))

C = (x₀ - x_C)² + (y₀ - y_C)² + (z₀ - z_C)² - S_r²

21. (**) Stosując algorytm de Casteljau należy znaleźć punkt dla wartości parametru t=0.5 na krzywej Beziera określonej następującymi punktami kontrolnymi P₀=[0,0], P₁=[1,5], P₂=[4,5], P₃=[5, 0].

Podać właściwości algorytmu de Casteljau.

Rozwiązanie graficzne przedstawione jest na slajdzie 27 prezentacji z pierwszego wykładu (zgk_pjwstk_2008cb.pdf):

Algorytm:

for i:= 0 to n do
;

for j:=1 to n do

for i:=j to n do

 :=
;

t = 0.5

0 krok algorytmu:

P_0,0 = (0,0), P_1,0 = (3,3), P_2,0 = (6,3), P_3,0 = (9,0)

1 krok algorytmu:

P_1,1 = 1-0.5 * P_0,0 + 0.5 * P_1,0 = (1.5, 1.5)

P_2,1 = 1-0.5 * P_1,0 + 0.5 * P_2,0 = (4.5, 3)

P_3,1 = 1-0.5 * P_2,1 + 0.5 * P_3,0 = (7.5, 1.5)

2 krok algorytmu:

P_2,2 = 1-0.5 * P_1,1 + 0.5 * P_2,1 = (3, 2.25)

P_3,2 = 1-0.5 * P_2,1 + 0.5 * P_3,1 = (6, 2.25)

3 krok algorytmu

P_3,3 = 1-0.5 * P_2,2 + 0.5 * P_3,2 = (4.5, 2.25)

22. (**) W jaki sposób można podzielić krzywą Beziera określoną przez podane punkty kontrolne P₀=[0,0], P₁=[3,3], P₂=[6,3], P₃=[9, 0] na dwie krzywe będące również krzywymi Beziera w punkcie dla wartości parametru t=0.25. Zaznaczyć na rysunku punkty kontrolne wyznaczonych dwóch krzywych Beziera.

23. (*) Wykaż, że krzywa Beziera podana wzorem

interpoluje końcowy (P₀) i początkowy (P₃) punkt kontrolny.

Krzywą Béziera trzeciego stopnia określa następujące równanie:

P(t) = A(1 − t)³ + 3Bt(1 − t)² + 3Ct²(1 − t) + Dt³     dla
.

Czyli:

P_x(t) = A_x(1 − t)³ + 3B_xt(1 − t)² + 3C_xt²(1 − t) + D_xt³

P_y(t) = A_y(1 − t)³ + 3B_yt(1 − t)² + 3C_yt²(1 − t) + D_yt³

Alternatywny zapis macierzowy:

Podstawiając pod t = 0 dla punktu początkowego otrzymujemy z mnożenia macierzy punkt A co dowodzi, że krzywa beziera jest styczna w punkcie A.
Podstawiając pod t = 1 dla punktu początkowego otrzymujemy z mnożenia macierzy punkt D co dowodzi, że krzywa beziera jest styczna w punkcie D.

24. (**) Zaznacz, która z poniższych stwierdzeń są prawdziwe dla płata powierzchni parametrycznej Beziera stopnia trzeciego:

1. interpoluje cztery narożne punkty kontrolne,

2. jest zawarty w wielokącie rozpiętym na punktach kontrolnym,

3. macierz geometrii składa się z 8 punktów,

4. można uzyskać ciągłość G¹ na granicach dwóch płatów powierzchni,

5. do obliczenia punktu na powierzchni może służyć algorytm de Boora.

25. (*) Zaznacz, które powierzchnie reprezentowane za pomocą siatki trójkątów spełniają warunki 2-wymiarowej rozmaitości topologicznej:

TYLKO 3!!!!! Nie może być żadnych dziur - w sensie każdy wierzchołek musi mieć na około trójkąty tak żeby tworzyły jakby cześć dysku.

26. (**) Krótko scharakteryzuj reprezentację siatki trójkątów za pomocą wskaźników na listę wierzchołków.
Zapisz podstawowe klasy umożliwiające implementację takiej reprezentacji.

- każdy wierzchołek siatki zapamiętany jest na liście wierzchołków, - wielokąt zdefiniowany jest jako lista wskaźników na wierzchołki, - dodatkowo* - wielokąt zawiera wskaźniki na sąsiadów, - brak bezpośredniej reprezentacji krawędzi, - każda krawędź wyświetlana jest 2 razy, - FV

class Face { public: Face *nbr[3]; Vertex *vert[3]; }; class Vertex { public: float x, y, z; };

27. (***) Podaj 2 sposoby konstrukcji modelu wielorozdzielczego siatki powierzchni. Dla każdego sposobu wymień po 2 przykłady algorytmów.

Dyskretny wielorozdzielczy model - przykład:

- VRML/X3D

Ciągły wielorozdzielczy model -

reprezentacja:

_ inkrementacyjna - M0 i sekwencja ulepszeń

_ hierarchiczna - hierarchia wierzchołków,

spanning tree,

DAG operacji…

28. (**) Podaj 3 przykładowe operatory topologiczne używane w algorytmach upraszczania siatki.

operatory topologiczne:

- złączenie krawędzi (edge collapse)

- połówkowe złączenie krawędzi (half-edge collapse)

- usuniecie wierzchołka (vertex removal)

- złączenie trójkąta (triangle collapse)

---