komputerowa.pdf

GraﬁkakomputerowaI

PrzemyslawKiciak

przemek@mimuw.edu.pl

http://www.mimuw.edu.pl/~przemek

5października2011

Streszczenie. Treściąwykładusąpodstawyteoretycznegraﬁkikomputerowej

orazwykorzystywanewniej algorytmyistrukturydanych.Kolejnymitemata

mi są algorytmy rasteryzacji odcinków, krzywych i wielokątów, obcinanie od

cinków i wielokątów, elementy geometrii aﬁnicznej, rzutowanie, elementy mo

delowaniageometrycznego(wtymkrzyweipowierzchnieB´ezieraiBsklejane),

algorytmywidoczności,podstawowemodeleoświetleniaicieniowaniaimetoda

śledzenia promieni. Wykład uzupełniają kursy języka PostScript i programo

wania w OpenGL.

Wersja internetowa, zob. http://mst.mimuw.edu.pl ,

może zawierać dodatkowe materiały.

Niniejsze materiały są dostępne na licencji Creative Commons 3.0 Polska :

Uznanie autorstwa — Użycie niekomercyjne — Bez utworów zależnych .

plik został utworzony 5 października 2011.

SkładwsystemieL A T E X,zwykorzystaniemm.in.pakietów beamer oraz listings .Szablonypodręcznikaiprezentacji:

Piotr Krzyżanowski, projekt: Robert Dąbrowski.

Spis treści

1 Wiadomości wstępne 9

1.1 Przegląd zastosowań graﬁki komputerowej . . . . . . . . . . . . . . . . . . . . . . 9

1.2 Komputerowa wizualizacja przestrzeni . . . . . . . . . . . . . . . . . . . . . . . . 11

1.2.1 Wprowadzenie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.2.2 Perspektywa geometryczna . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.2.3 Widoczność . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.2.4 Perspektywa powietrzna . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.2.5 Głębia ostrości . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.2.6 Oświetlenie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.2.7 Cienie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.2.8 Stereoskopia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1.2.9 Ruch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1.2.10 Współdziałanie innych zmysłów . . . . . . . . . . . . . . . . . . . . . . . . 16

1.3 Graﬁka interakcyjna . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

1.3.1 Działanie programu interakcyjnego . . . . . . . . . . . . . . . . . . . . . . 17

2 Podstawowe algorytmy graﬁki rastrowej 22

2.1 Rysowanie odcinka . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.2 Rysowanie okręgu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.3 Rysowanie elips . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

2.4 Wypełnianie wielokątów . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.5 Wypełnianie obszaru przez zalewanie . . . . . . . . . . . . . . . . . . . . . . . . . 29

2.6 Algorytm z pływającym horyzontem . . . . . . . . . . . . . . . . . . . . . . . . . 30

3 Obcinanie linii i wielokątów 34

3.1 Obcinanie odcinków i prostych . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

3.1.1 Wyznaczanie punktu przecięcia odcinka i prostej . . . . . . . . . . . . . . 34

3.1.2 Algorytm SutherlandaCohena . . . . . . . . . . . . . . . . . . . . . . . . 35

3.1.3 Algorytm LiangaBarsky’ego . . . . . . . . . . . . . . . . . . . . . . . . . 36

3.1.4 Obcinanie prostych . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

3.2 Obcinanie wielokątów . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

SPIS TREŚCI

3.2.1 Algorytm SutherlandaHodgmana . . . . . . . . . . . . . . . . . . . . . . 37

3.2.2 Algorytm WeileraAthertona . . . . . . . . . . . . . . . . . . . . . . . . . 39

4 Elementy geometrii aﬁnicznej 41

4.1 Przestrzenie aﬁniczne i euklidesowe . . . . . . . . . . . . . . . . . . . . . . . . . . 41

4.1.1 Określenie przestrzeni aﬁnicznej . . . . . . . . . . . . . . . . . . . . . . . 41

4.1.2 Iloczyn skalarny . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

4.2 Układy współrzędnych . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

4.2.1 Współrzędne kartezjańskie . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

4.2.2 Współrzędne barycentryczne . . . . . . . . . . . . . . . . . . . . . . . . . 44

4.2.3 Współrzędne jednorodne . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

4.3 Przekształcenia aﬁniczne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

4.3.1 Deﬁnicja i własności . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

4.3.2 Jednorodna reprezentacja przekształceń aﬁnicznych . . . . . . . . . . . . 48

4.3.3 Przekształcanie wektora normalnego . . . . . . . . . . . . . . . . . . . . . 49

4.3.4 Zmiana układu współrzędnych . . . . . . . . . . . . . . . . . . . . . . . . 49

4.3.5 Szczególne przypadki przekształceń aﬁnicznych . . . . . . . . . . . . . . . 51

4.3.6 Składanie przekształceń w zastosowaniach graﬁcznych . . . . . . . . . . . 55

4.3.7 Rozkładanie przekształceń . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

4.3.8 Obroty, liczby zespolone i kwaterniony . . . . . . . . . . . . . . . . . . . . 57

5 Rzutowanie równoległe, perspektywiczne i inne 63

5.1 Rzutowanie równoległe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

5.2 Rzutowanie perspektywiczne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

5.3 Algorytm rzutowania . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

5.4 Stereoskopia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

5.5 Panorama i inne rzuty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

6 Elementy modelowania geometrycznego 71

6.1 Krzywe B´eziera . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

6.1.1 Określenie krzywych B´eziera . . . . . . . . . . . . . . . . . . . . . . . . . 71

6.1.2 Algorytm de Casteljau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

6.1.3 Własności krzywych B´eziera . . . . . . . . . . . . . . . . . . . . . . . . . . 73

6.2 Krzywe Bsklejane . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

6.2.1 Określenie krzywych Bsklejanych . . . . . . . . . . . . . . . . . . . . . . 75

6.2.2 Algorytm de Boora . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

6.2.3 Podstawowe własności krzywych Bsklejanych . . . . . . . . . . . . . . . . 77

6.2.4 Wstawianie węzła . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

6.2.5 Krzywe Bsklejane z węzłami równoodległymi . . . . . . . . . . . . . . . . 81

6.3 Powierzchnie B´eziera i Bsklejane . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

6.3.1 Płaty tensorowe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

c P.Kiciak, Uniwersytet Warszawski, 2011.

6.3.2 Płaty trójkątne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

6.3.3 Metody siatek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

6.4 Krzywe i powierzchnie wymierne . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

6.5 Modelowanie powierzchni i brył . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

6.5.1 Zakreślanie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

6.5.2 Powierzchnie rozpinane . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

6.5.3 Powierzchnie zadane w postaci niejawnej . . . . . . . . . . . . . . . . . . . 90

7 Reprezentacje scen trójwymiarowych 93

7.1 Prymitywy i obiekty złożone . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

7.2 Reprezentowanie brył wielościennych . . . . . . . . . . . . . . . . . . . . . . . . . 94

7.3 Konstrukcyjna geometria brył . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

7.3.1 Wyznaczanie przecięcia wielościanów . . . . . . . . . . . . . . . . . . . . . 97

7.4 Drzewa i grafy scen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

8 Drzewa binarne, czwórkowe i ósemkowe 101

8.1 Drzewa czwórkowe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

8.1.1 Konstrukcyjna geometria ﬁgur płaskich . . . . . . . . . . . . . . . . . . . 102

8.1.2 Algorytm widoczności . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

8.1.3 Transmisja obrazów i MIPmapping . . . . . . . . . . . . . . . . . . . . . 104

8.2 Drzewa ósemkowe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

8.3 Drzewa binarne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

8.4 Binarny podział przestrzeni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

9 Algorytmy widoczności 108

9.1 Rodzaje algorytmów widoczności . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

9.2 Algorytmy przestrzeni danych . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

9.2.1 Odrzucanie ścian „tylnych” . . . . . . . . . . . . . . . . . . . . . . . . . . 109

9.2.2 Obliczanie punktów przecięcia odcinków w przestrzeni . . . . . . . . . . . 110

9.2.3 Algorytm Ricciego . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

9.2.4 Algorytm WeileraAthertona . . . . . . . . . . . . . . . . . . . . . . . . . 113

9.2.5 Algorytm Appela . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

9.2.6 Algorytm Hornunga . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

9.3 Algorytmy przestrzeni obrazu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

9.3.1 Algorytm malarza . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

9.3.2 Algorytm binarnego podziału przestrzeni . . . . . . . . . . . . . . . . . . 116

9.3.3 Algorytm BSP wyznaczania cieni . . . . . . . . . . . . . . . . . . . . . . . 116

9.3.4 Algorytm z buforem głębokości . . . . . . . . . . . . . . . . . . . . . . . . 117

9.3.5 Algorytm przeglądania liniami poziomymi . . . . . . . . . . . . . . . . . . 118

9.3.6 Algorytm cieni z buforem głębokości . . . . . . . . . . . . . . . . . . . . . 120

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: