6. Podstawy systemów operacyjnych i systemów grafiki komputerowej.

1. SYSTEM OPERACYJNY (SO). PRZEZNACZENIE, BUDOWA I PODSTAWOWE FUNKCJE. PODZIAŁ ZADAŃ SO POMIĘDZY SPRZĘT I OPROGRAMOWANIE.

System operacyjny jest programem, który działa jako pośrednik między użyt­kownikiem komputera a sprzętem komputerowym. Zadaniem systemu opera­cyjnego jest tworzenie środowiska, w którym użytkownik może wykonywać programy w wygodny i wydajny sposób.

Budowa systemu operacyjnego:

Przyjęto podział na trzy główne elementy budowy systemu operacyjnego:

• jądro systemu wykonywujące w/w zadania

• powłoka - specjalny program komunikujący użytkownika z systemem operacyjnym

• system plików - sposób zapisu struktury danych na nośniku.

Jądro systemu operacyjnego (ang. kernel) - to jego podstawowa część, która jest odpowiedzialna za wszystkie jego zadania.

Powłoka systemowa - (ang. shell) to program komputerowy pełniący rolę pośrednika pomiędzy systemem operacyjnym lub aplikacjami a użytkownikiem, przyjmując jego polecenia i "wyprowadzając" wyniki działania programów. Owo pośrednictwo nie jest obowiązkowe (programy mogą chcieć być bardziej "samodzielne"). Wyróżniamy powłoki tekstowe np.:

• bash - Bourne Again Shell (znów powłoka Bourne'a)

• ksh - Korn Shell

• zsh

• sh

• csh

• command.com - procesor poleceń systemu DOS

oraz graficzne, takie jak np.:

• GNOME, a dokładniej Nautilus lub GMC

• KDE, a dokładniej Konqueror

• finder - powłoka systemu Mac OS

• explorer - powłoka systemu Microsoft Windows.

Powłoka często sama zawiera podstawowe polecenia, gdy jednak wydane przez użytkownika polecenie nie jest wbudowane, uruchamiany jest program zewnętrzny. Po zalogowaniu użytkownik znajduje się w linii poleceń i może wydawać polecenia systemowi. Zachęca go do tego tzw, znak zachęty (shell prompt). Zwykle znak '>', '$' lub '#'.

System plików - metoda przedstawienia logicznej struktury danych (pliki, katalogi/foldery) na fizycznym medium, zwanym też nośnikiem danych (w postaci ciągu zer i jedynek).

STRUKTURY SYSTEMÓW OPERACYJNYCH

1. Struktura monolityczna - system operacyjny traktowany jako zbiór procedur, przy czym każda z nich może wywoływać drugą; poszczególne procedury muszą mieć bardzo dobre złącza (ang. interface). W celu stworzenia konkretnej wersji systemu operacyjnego należy skompilować odpowiedni zbiór procedur.

2. Struktura warstwowa - system zbudowany jest z kilku poziomów, co zapewnia jego modularność. Każdy poziom składa się ze zbioru procedur i danych, które mogą być wywoływane z poziomu wyższego. Poziom najniższy - sprzęt, najwyższy - interface z użytkownikiem. W każdym systemie operacyjnym poziomy mogą być różne.

W systemach operacyjnych o strukturze warstwowej wyodrębniona jest część realizująca najbardziej podstawowe funkcje systemu operacyjnego, tzw. jądro systemu lub warstwa wewnętrzna. Pozostała część systemu to warstwa zewnętrzna. Podział taki nie jest jednoznacznie określony dla wszystkich systemów.

W jądrze systemu implementuje się wszystkie funkcje, które muszą być traktowane w sposób uprzywilejowany. Jądro odpowiada m.in. za: obsługę przerwań, przydział procesora, operacje wej/wyj. Ponadto w jądrze systemu są implementowane mechanizmy, które tworzą wspomnianą już maszynę wirtualną.

Warstwa zewnętrzna obejmuje procesy użytkowników (można przyjąć, że są to po prostu programy) i moduły systemu operacyjnego nienależące do jądra systemu. Jednym z procesów warstwy zewnętrznej jest POWŁOKA (ang. shell). Powłoka jest jedyną widoczną częścią maszyny wirtualnej.

Funkcje systemowe (ang. system calls) stanowią maszynę wirtualną, ich wywołania są poleceniami dla jądra systemu, np. zainicjowanie nowego procesu, otwarcie pliku. Funkcje systemowe dzielą się na: funkcje systemowe dotyczące procesów i funkcje systemowe dotyczące sytemu plików. Zwykłe polecenia użytkowników są poleceniami dla programu powłoki.

3. Struktura klient - serwer - model związany z rozproszonymi systemami operacyjnymi. Rozróżniamy sieciowe i rozproszone systemy operacyjne - w systemach sieciowych klient/użytkownik musi znać adres pliku, z którym chce pracować, który chce wywoływać, w systemach rozproszonych użytkownik pracuje jak na własnym pececie. Podstawową zasadą działania w tej strukturze jest przesyłanie maksymalnej ilości kodu na wyższe poziomy, pozostawiając minimalne jądro.

Zadania systemu operacyjnego:

• zarządzanie zasobami komputera, m.in.: procesorem (a dokładniej czasem procesora), pamięcią, urządzeniami peryferyjnymi oraz przydzielanie zasobów procesom,

• koordynacja pracy w/w urządzeń poprzez obsługę przerwań oraz odpowiednie na nie reagowanie,

• ochrona danych i pamięci - tak aby jeden proces, w wyniku błędu lub zamierzonego działania nie mógł zniszczyć lub pozyskać danych innego procesu,

• automatyzacja najczęściej wykonywanych funkcji

• ukrywanie skomplikowania sprzętu komputerowego przez tworzenie abstrakcji, np.

• zbiory zapisanych klastrów na dysku widziane są jako pliki o symbolicznych nazwach

• abstrakcja równoległości wykonywania programów

• jednolity sposób dostępu do urządzeń

System operacyjny jest ładowany do pamięci na początku pracy komputera. Program ten ma bardzo specyficzny charakter: w przeciwieństwie do programów użytkowych (aplikacji) nie korzysta z żadnych gotowych funkcji, tylko sam je udostępnia, a więc od niego zależą rzeczywiste możliwości wykorzystania sprzętu komputerowego.

1. PROCESY W SYSTEMIE KOMPUTEROWYM: POJĘCIE PROCESU, PROCES A PROGRAM, PODOBIEŃSTWA I RÓŻNICE PROCESÓW I WĄTKÓW. WYŻSZY I NIŻSZY POZIOM PLANOWANIA PROCESÓW W SO (PLANOWANIE DŁUGO- I KRÓTKOTERMINOWE) - POJĘCIE I ZASADY OGÓLNE. ROLA I PRZYKŁADY KOLEJEK W SYSTEMIE OPERACYJNYM. BLOKADA PROCESÓW; SYTUACJE SPRZYJAJĄCE BLOKADOM I SPOSOBY ZAPOBIEGANIA; PRZYKŁADY BLOKADY.

Pojęcie procesu, proces a program:

Proces: mówiąc nieformalnie, proces jest wykonywanym programem. Wykonanie procesu musi przebiegać w sposób sekwencyjny. Oznacza to, że w dowolnej chwili na zamówienie danego procesu może być wykonywany, co najwyżej jeden rozkaz kodu programu. Podkreślamy, że sam program nie jest procesem.

Program jest obiektem pasywnym, tak jak zawartość pliku na dysku. Proces zaś jest obiektem aktywnym, z licznikiem rozkazów określających następny rozkaz do wykonania i ze zbiorem przydzielonych mu zasobów. Procesy możemy wyświetlić za pomocą polecenia ps. Każdy proces otrzymuje unikatowy numer, tzw. PID (ID Procesu). Dzięki temu proces jest odróżnialny od innych.

Chociaż dwa procesy mogą być związane z jednym programem, będą one zawsze traktowane jako dwie oddzielne sekwencje wykonania. Na przykład wielu użytkowników może korzystać z działania kopii programu pocztowego lub jeden użytkownik może zapoczątkować pracę wielu kopii edytora. W każdym z tych przypadków mamy do czynienia z osobnymi procesami, które - niezależnie od równoważności sekcji tekstu - będą się różniły sekcja­mi danych.

Proces składa się z:

• kodu programu (sekcji tekstu)

• odpowiedniego ustawienia licznika rozkazów

• zawartości rejestrów procesora

• stosu procesu z danymi tymczasowymi (parametrami procedur, adresami powrotnymi)

• sekcji danych ze zmiennymi globalnymi

Podobieństwa i różnice procesów i wątków.

Wątek (ang. thread), nazywany niekiedy procesem lekkim (ang. lightweight process - LWP), jest podstawową jednostką wykorzystania procesora

Wątek:

• Jednostka, dla której system przydziela czas procesora,

• Kontekst wątku składa się z: licznika rozkazów, stanu rejestrów, stosu (ale nie sterty!),

• Każdy proces ma co najmniej jeden wątek

Podobieństwa wątków i procesów:

• mogą znajdować się w jednym z kilku stanów: gotowości, zablo­kowania, aktywności lub kończenia.

• użytkują wspólnie jednostkę centralną i w danej chwili tylko jeden wątek/proces jest aktywny (wykonywany).

• Wykonanie wątku w procesie przebiega sekwencyjnie, a każ­dy wątek ma własny stos i licznik rozkazów.

• mogą tworzyć wątki/procesy po­tomne i mogą blokować się do czasu zakończenia wywołań systemowych.

• Jeśli jeden wątek.proces jest zablokowany, to może działać inny wątek/proces.

Związek pomiędzy procesami a wątkami:

• Proces nie wykonuje kodu, proces jest obiektem dostarczającym wątkowi przestrzeni adresowej,

• Kod zawarty w przestrzeni adresowej procesu jest wykonywany przez wątek,

• Pierwszy wątek procesu tworzony jest implicite przez system operacyjny, każdy następny musi być utworzony explicite,

• Wszystkie wątki tego samego procesu dzielą wirtualną przestrzeń adresową i mają dostęp do tych samych zmiennych globalnych i zasobów systemowych.

Wyższy i niższy poziom planowania procesów w SO (planowanie długo- i krótkoterminowe) - pojęcie i zasady ogólne:

Proces wędruje między różnymi kolejkami przez cały czas swego istnienia. W celu planowania działań system operacyjny musi w jakiś sposób wybierać procesy z tych kolejek. Selekcji dokonuje odpowiedni proces systemowy zwany planistą (programem szeregującym; ang. scheduler).

W systemie wsadowym często występuje więcej procesów niż można by ich natychmiast wykonać. Procesy te są przechowywane w urządzeniach pa­mięci masowej (zazwyczaj na dyskach), gdzie oczekują na późniejsze wykona­nie.

Planista długoterminowy (ang. long-term scheduler), nazywany też plani-stązadań (ang.job scheduler), wybiera procesy z tej puli i ładuje je do pamięci w celu wykonania.

Planista krótkoterminowy (ang. short-term scheduler), czyli planista przydziału procesora (ang. CPU scheduler), wybiera jeden proces spośród procesów gotowych do wykonania i przydziela mu procesor.

Podstawową różnicą między obydwoma planistami jest częstość ich uaktywnień.

Planista krótkoterminowy musi bardzo często wybierać nowy proces dla procesora. Proces może działać zaledwie kilka milisekund, a potem przejść w stan oczekiwania, wydawszy zamówienie na operację wejścia--wyjścia. Często planista krótkoterminowy podejmuje działanie co najmniej raz na każde 100 ms. Ze względu na krótkie odcinki czasu między kolejnymi wykonaniami planista krótkoterminowy musi być bardzo szybki. Jeśli decyzja o wykonaniu procesu przez 100 ms zabiera 10 ms, to 10/(100 + 10) = 9% pracy procesora jest zużywane (marnowane) na samo zaplanowanie działania.

Natomiast planista długoterminowy działa o wiele rzadziej. Między utworzeniem nowych procesów w systemie mogą upływać minuty. Planista długoterminowy nadzoruje stopień wieloprogramowości, tj. liczbę procesów w pamięci. Jeśli stopień wieloprogramowości jest stabilny, to średnia liczba utworzonych procesów musi się równać średniej liczbie procesów usuwanych z systemu. Toteż planista długoterminowy może być wywoływany tylko wte­dy, gdy jakiś proces opuszcza system. Wskutek dłuższych przerw między wykonaniami planista długoterminowy może mieć więcej czasu na rozstrzy­ganie, który proces należy wybrać do wykonania.

Planowanie długoterminowe polega na wyborze procesów do wykonania i załadowaniu ich do pamięci. Stosowane jest przede wszystkim w systemach wsadowych do nadzorowania stopnia wieloprogramowości. W systemach wielozadaniowych (z podziałem czasu) w zasadzie nie jest stosowane.

Planowanie krótkoterminowe polega na wyborze jednego procesu z kolejki procesów gotowych do wykonania i przydzieleniu mu dostępu do procesora. Ten typ planowania dominuje w systemach z podziałem czasu, takich jak Unix, Linux, Windows NT.

Blokada procesów; sytuacje sprzyjające blokadom i sposoby zapobiegania; przykład blokady:

W środowisku wieloprogramowym kilka procesów może rywalizować o skończoną liczbę zasobów. Proces zamawia zasoby i jeśli nie są one dostępne w danym czasie, wchodzi w stan oczekiwania. Może się zdarzyć, że ocze­kujące procesy nigdy już nie zmienią swego stanu, ponieważ zamawiane przez nie zasoby są przetrzymywane przez inne procesy. Sytuację taką nazy­wa się blokadą (zakleszczeniem) (ang. deadlock).

O zjawisku blokady (zakleszczeniu) mówimy, gdy w zbiorze procesów każdy proces oczekuje na zdarzenie, które może być spowodowane tylko przez inny proces z tego zbioru (zdarzenia, z którymi mamy najczęściej do czynienia to przydział i zwalnianie zasobów).

Do blokady (zakleszczeń) może dochodzić wtedy, kiedy w systemie zachodzą jednocze­śnie cztery warunki:

1. Wzajemne wykluczanie: Przynajmniej jeden zasób musi być niepo­dzielny; to znaczy, że zasobu tego może używać w danym czasie tylko jeden proces. Jeśli inny proces zamawia dany zasób, to musi być opóź­niany do czasu, aż zasób zostanie zwolniony.

2. Przetrzymywanie i oczekiwanie: Musi istnieć proces, któremu przydzielono co najmniej jeden zasób i który oczekuje na przydział dodatko­wego zasobu, przetrzymywanego właśnie przez inny proces.

3. Brak wywłaszczeń: Zasoby nie podlegają wywłaszczaniu, co oznacza, że zasób może zostać zwolniony tylko z inicjatywy przetrzymującego go procesu, po zakończeniu pracy tego procesu.

4. Czekanie cykliczne: Musi istnieć zbiór {P_o, P₁,..., P_n} czekających procesów, takich że P₀ czeka, na zasób przetrzymywany przez proces P₁,P₁ czeka na zasób przetrzymywany przez proces P₂..., P_n - i czeka na za­sób przetrzymywany przez proces P_n a P_n czeka na zasób przetrzymywa­ny przez proces P_0..

Metody postępowania z zakleszczeniami.

1. można stosować protokół gwarantujący że system nigdy nie wejdzie w stan zakleszczenia-aby zapewnić że zakleszczenie nigdy się nie pojawi system może stosować metody zapobiegawcze lub schemat unikania zakleszczeń przez zapobieganie zakleszczenia rozumie się zbiór metod zapewniających że co najmniej jeden z warunków koniecznych do wystąpienia zakleszczenia nie będzie spełniony. Metody te zapobiegają zakleszczeniu przez nakładanie ograniczeń na sposób zamawiania zasobów.

2. Pozwala się systemowi na zakleszczenia a potem podejmuje się działania zmierzające do ich usunięcia.- jeżeli system nie korzysta z algorytmu zapobiegania zakleszczeniu ani z algorytmu ich unikania to zakleszczenie może się pojawić. W takich warunkach system powinien umożliwiać wykonanie algorytmu, który sprawdzi czy doszło do zakleszczenia, oraz algorytmu likwidowania zakleszczenia.

3. Można też zlekceważyć ten problem zupełnie uważając, że zakleszczenia nigdy się nie pojawiają w systemie. Takie rozwiązania stosuje się w większości systemów m.in. w systemie UNIX. Unikanie zakleszczeń wymaga, aby system operacyjny dysponował dodatkowymi informacjami o zasobach, które proces będzie zamawiał i używał podczas swojego działania. Proces może wtedy rozstrzygać dla każdego zamówienia, czy proces powinien zaczekać, czy nie. Każde zamówienie wymaga, aby system podejmując decyzję o tym czy można je realizować czy też należy je odłożyć wziął pod uwagę dostępne zasoby, zasoby w danej chwili przydzielane do procesów i oraz przyszłe zamówienia i zwolnienia zasobów w odniesieniu do każdego procesu.

1. PAMIĘĆ WIRTUALNA. CEL ZASTOSOWANIA, NIEZBĘDNE WYPOSAŻENIE SPRZĘTOWE I OGÓLNY ALGORYTM DZIAŁANIA.

Pamięć wirtualna, wirtualna przestrzeń adresowa (angielskie virtual memory, virtual address space), zbiór jednolicie adresowanych elementów pamięci oddawany do użytku w programach przez systemy pamięci wirtualnej. Pamięć wirtualna może przekraczać rozmiary fizycznej pamięci operacyjnej, gdyż jest implementowana z użyciem pamięci zewnętrznej (dyskowej), z zastosowaniem sprzętowego stronicowania i algorytmów stronicowania na żądanie, zastępowania stron i stronicowania wstępnego.

Czas działania programów wykonywanych w systemach pamięci wirtualnej może zależeć od programowego sposobu organizacji danych oraz zmieniać się od wykonania do wykonania, toteż pamięci wirtualnej nie stosuje się w systemach czasu rzeczywistego.

Poza tymi wyjątkami pamięć wirtualna jest wielkim udogodnieniem programowania, gdyż zdejmuje z osób programujących ostre ograniczenia na ilość dostępnej pamięci i uwalnia je od niejednolitego zarządzania pamięciami fizycznymi w aplikacjach.

Pamięć wirtualna jest najczęściej implementowana w formie stronico­wania na żądanie (ang. demand paging). Można ją także zrealizować w systemie segmentacji.

2. METODY RZUTOWANIA W PRZESTRZENI 3D, PODSTAWOWE OPERACJE.

Do opisu punktu w przestrzeni należy użyć trzech współrzędnych P(x,y,z). Oznaczenie osi w modelu 3D jest sprawą umowną, jednak zapominając na chwilę o trzecim wymiarze, od razu widać, iż najbardziej naturalne będzie opisanie ekranu monitora osiami X i Y. Gdy uzmysłowimy sobie ten fakt oczywistym staje się zastosowanie osi Z do określenia odległości między obserwatorem (powierzchnią ekranu) a obiektem w przestrzeni 3D. Dodatkowo nale­ży zwrócić uwagę, że można zastosować dwa typy układu współrzędnych, w jednym współ­rzędne z będą rosły w głąb monitora, natomiast w innym podejściu będą przybierały coraz to mniejsze wartości. Pierwszy typ układu nazywany jest często lewoskrętnym i jego będziemy używać. Poniżej podane są postaci macierzy opisujących odpowied­nie operacje w przestrzenie 3D.

Macierzowe równania opisujące operacje obrotów.

Macierz rotacji wokół osi X:

Macierz rotacji wokół osi Y:

Macierz rotacji wokół osi Z:

METODY RZUTOWANIA W PRZESTRZENI 3D, PODSTAWOWE OPERACJE.

Rzutowanie jest podstawowym przekształceniem w grafice trójwymiarowej, gdyż każdy obiekt przestrzenny wymaga odwzorowania go na płaski ekran monitora. Rzutowania możną podzielić na dwie zasadnicze klasy:

- rzuty równoległe

- rzuty perspektywiczne zwane także rzutami środkowymi.

Rzuty równoległe

Rzut równoległy zachowuje równoległość prostych, stosunek długości odcinków równoległych i związki miarowe figury płaskiej równoległe do płaszczyzny rzutowania (na rysunku płaszczyzna P). Z powyższych powodów rzuty równoległe stosuje sie głównie w rysunku technicznym.

Rzuty ortogonalne lub prostokątne lub pionowe

W rzucie równoległym wszystkie proste rzutowania maja taki sam ustalony kierunek. Jeżeli jest on prostopadły do rzutni, to rzut nazywamy ortogonalnym lub prostokątnym Inna stosowana nazwa to rzut pionowy.

Typowymi rzutami ortogonalnymi są:

- rzut przedni

- rzut górny

- boczny

- aksonometryczne

- izometryczne

Są one najczęściej wykorzystywane w rysunku technicznym do przedstawiania obiektów z trzech stron.

Natomiast w aksonometrycznym rzucie prostokątnym rzutnia nie jest prostopadła do głównej osi co powoduje jednoczesna widoczność kilku stron obiektu.

Często stosowanym rzutem aksonometrycznym jest rzut izometryczny. W rzucie tym kierunek rzutowania tworzy równe kąty z głównymi osiami. Rzut ten ma dość użyteczną właściwość polegającą na jednakowym skróceniu trzech podstawowych osi, co umożliwia wykonywanie pomiarów wzdłuż tych osi.

Rzuty ukośne

W ogólnym przypadku kierunek rzutu równoległego tworzy z płaszczyzna rzutowania kat α .Rzuty takie nazywamy rzutami ukośnymi. Aby jednoznacznie zorientować prostą rzutowania względem rzutni, obok kata α, potrzebny jest dodatkowy parametr np. odległość L lub kat φ.

Rzuty perspektywiczne

W rzucie perspektywicznym, zwanym także rzutem środkowym, punkty zostają przeniesione na rzutnie wzdłuż prostych przecinających się w jednym punkcie zwanym środkiem projekcji. Obrazem rzutowanych punktów są przecięcia prostych rzutowania z rzutnia. Jeżeli określony jest jeden środek projekcji to mówimy o rzucie jednopunktowym. Można także określić dwa lub trzy środki projekcji, które dają w efekcie rzuty dwupunktowe i trzypunktowe.

Rzut jednopunktowy

Jednopunktowy rzut perspektywiczny jest bardzo często stosowany w grafice trójwymiarowej z uwagi na proste obliczenia oraz dobre efekty wizualne. Jedna z możliwych realizacji rzutu jednopunktowego polega na tym, że środek projekcji umieścimy na ujemnej stronie osi OZ, a rzutnie będzie stanowić płaszczyzna X-Y.

Rzut dwupunktowy

W rzucie perspektywicznym dwupunktowym mamy dwa środki projekcji. Typowo przyjmuje się, że środki projekcji położone są na parach osi OX-OZ i OY-OZ. Rysunek przedstawia obraz sześcianu w dwupunktowych rzutach perspektywicznych. Lewy rysunek - środek projekcji znajduje się na osiach OX-OZ, prawy rysunek - środek projekcji znajduje się na osiach OY-OZ.

Rzut trzypunktowy

W rzucie perspektywicznym dwupunktowym mamy trzy środki projekcji.

PODSUMOWANIE

Planarne rzuty geometryczne:

• rzut perspektywiczny
  środek rzutowania w skończonej odległości od płaszczyzny rzutowania

• rzut równoległy
  środek rzutowania w nieskończoności, promienie rzutujące są równoległe

Rzut perspektywiczny odwzorowuje sposób widzenia człowieka (skrót perspektywiczny).

Wielkość rzutu zmniejsza się przy wzroście odległości między środkiem rzutowania a obiektem.

Zniekształcane są kształty i wymiary obiektów.

Rodzaje:

• jednopunktowy

• dwupunktowy

• trzypunktowy

Rzut równoległy nie zachowuje perspektywy, zachowuje kształt i rozmiar obiektów.

Rodzaje rzutu równoległego (i przykłady):

• prostokątny

• ortogonalne: przedni, górny, boczny

• aksonometryczne: izometryczny

• ukośny

• wojskowy

• kawaleryjski

Rzut izometryczny - kierunek rzutowania tworzy jednakowe kąty ze wszystkimi osiami

Rzut prostokątny: void GlOrtho()

Rzut perspektywiczny: void GlFrustum()

1. Metody reprezentacji krzywych, powierzchni i reprezentacji brył.

Obiekty 3D

Każdy obiekt 3D jest aproksymowany zbiorem ścian, które tworzą siatkę. Każda ściana jest zdefiniowana przez uporządkowany zbiór wierzchołków. Każdy wierzchołek jest zdefiniowany przez współrzędne (x, y, z) i wektor normalny N. Z reguły obiekt umieszczany jest na scenie w lokalnym układzie współrzędnych.

Typy obiektów:

1. Obiekty parametryczne- Opisane są przez podstawowe wymiary (np. szerokość, wysokość, promień). Można je zamienić na siatkę wielokątów lub siatkę łat.

2. Obiekty siatkowe- Możliwa modyfikacja wierzchołków, krawędzi, ścianek.

3. Krzywe- Używane są przy modyfikacjach wytłaczania ścinania, tworzeniu brył obrotowych i obiektów o powierzchniach krzywoliniowych. Można edytować wierzchołki
i segmenty krzywej.

Możliwych jest kilka metod zbudowania modelu bryły:

Kopiowanie prymitywów- metoda ta polega na kopiowaniu gotowych już prymitywów, przy czym ich cechy mogą być parametryzowane.

Reprezentacje z przesuwaniem- przesuwanie obiektu płaskiego wzdłuż trajektorii w przestrzeni definiuje nowy obiekt 3D.

Reprezentacje brzegowe- opisują one obiekt za pomocą powierzchni ograniczających, wierzchołków, krawędzi i ścian.

Reprezentacje z podziałem przestrzennym- w tej reprezentacji bryła jest dekomponowana na zbiór sąsiadujących nie przecinających się brył, które są prostszymi prymitywami od oryginalnej bryły.

Konstruktywna geometria brył (CSG)- w tym opisie łączy się proste prymitywy za pomocą regularyzowanych operatorów boolowskich, które stają się nieodłączną częścią modelu.

PODSUMOWANIE

Obiekty graficzne trójwymiarowe - istniejące w świecie rzeczywistym lub sztucznie tworzone- mogą być w obrazie komputerowym reprezentowane (opisywane) przy pomocy:

• modelowania powierzchni

• siatki wielokątów

• powierzchnie parametryczne

• powierzchnie drugiego stopnia

• modelowania brył

MODELOWANIA POWIERZCHNI

Siatka wielokątowa - zbiór krawędzi, wierzchołków i wielokątów taki, że

• każda krawędź jest wspólna przynajmniej dla dwóch wielokątów

• krawędź łączy dwa wierzchołki

• wielokąt jest zamkniętą sekwencją krawędzi

• wierzchołek jest wspólny dla przynajmniej dwóch krawędzi

• każda krawędź jest częścią jakiegoś wielokąta

Siatki wielokątowe mogą być reprezentowane na kilka sposobów.

• Reprezentacja bezpośrednia - wykaz wierzchołków każdego wielokąta, reprezentacja ta jest nadmiarowa

• Metoda wskaźników na listę wierzchołków
  - każdy wierzchołek jest zapamiętywany raz, wielokąty zapisywane jako wskaźniki do wierzchołków

• Metoda wskaźników na listę krawędzi - lista krawędzi wskazuje na dwa wierzchołki oraz wielokąty, do których należy krawędź.

Krzywe Hermite'a

Krzywe Béziera

Krzywe B-sklejane

Rodzaje krzywych B-sklejanych:

• jednorodne

• niejednorodne

Parametryczne powierzchnie bikubiczne

Powierzchnie bikubiczne to takie które są modelowane w oparciu o krzywe zwane kubkami, które w bardzo małych przedziałach tworzą powierzchnie - inaczej gęsto upakowane krzywe.

W zależności od algorytmu aproksymacji krzywych można rozpatrzyć:

• powierzchnie Hermite'a

• powierzchnie Béziera

• powierzchnie B-sklejane

MODELOWANIE BRYŁ

Problem reprezentacji (opisu parametrycznego) brył - obiektów trójwymiarowych.

Najczęstsze reprezentacje:

• z przesuwaniem lub obrotem

• brzegowa

• z podziałem przestrzennym

• dekompozycja na komórki

• wokselowa

• drzewa ósemkowe

Reprezentacja z przesuwaniem lub obrotem

Obiekt 3D powstaje poprzez przesunięcie obrysu 2D wzdłuż pewnej trajektorii lub poprzez obrót wokół jakiejś osi.

Reprezentacja z podziałem przestrzennym:

Dekompozycja na komórki:

Każdy obiekt można podzielić na prostsze obiekty: duże obiekty tworzymy poprzez sklejenie pewnych prostych obiektów. Sklejane - komórki nie mogą się przecinać i dodatkowo dwie komórki muszą mieć wspólny punkt, krawędź lub ścianę.

Wokselowa:

Dokonujemy dekompozycji obiektu 3D na identyczne komórki uporządkowane wg, regularnej siatki. Komórki te nazywamy wokselami.

Drzewa ósemkowe:

Hierarchiczny wariant metody wokselowej. (podział przestrzeni, oszczędność miejsca w pamięci.

Np. z prostokąta można uzyskać:

• bryłę przesuwaną - prostopadłościan

• bryłę obrotową - walec

1. METODY PRZETWARZANIA OBRAZÓW: FILTRY LINIOWE I NIELINIOWE, FILTRACJA KONTEKSTOWA I PUNKTOWA. RODZAJE FILTRÓW. PRZEKSZTAŁCENIA MORFOLOGICZNE PROSTE I ZŁOŻONE.

2. SEGMENTACJA OBRAZÓW. TECHNIKI SEGMENTACJI.

3. ALGORYTMY WYZNACZANIA POWIERZCHNI WIDOCZNYCH, MODELE OŚWIETLENIA I CIENIOWANIA.

Dla danego zbioru obiektów, specyfikację parametrów widzenia należy określić, które linie albo które powierzchnie obiektów są widoczne, tak żeby było możliwe wyświetlenie tylko linii albo powierzchni widocznych.

Założenie: każdy obiekt jest zbiorem powierzchni, np. wielokątów. Mamy p pikseli i n obiektów.

• algorytm z precyzją obrazową: dla każdego piksela obrazu wyznaczyć obiekt najbliższy obserwatora, który jest napotkany przez promień rzutowania przechodzący przez piksel; złożoność: np

• algorytm z precyzją obiektową: dla każdego obiektu wyznaczyć i narysować te części obiektu, których rzut nie jest zasłonięty przez inne części tego lub innych obiektów; złożoność: n2, zwykle większa niż 1. metody

Określanie widoczności obiektów przeprowadza się przed rzutowaniem na płaszczyznę, zwykle po przekształceniu normalizującym.

Przykład: punkty P1=(x1,y1,z1) , P2=(x2,y2,z2).

Zasłanianie jednego punktu przez drugi zachodzi wtedy, gdy punkty P1 i P2 leżą na tym samym promieniu rzutującym. Warunek:

• w rzucie równoległym x1=x2 , y1=y2

• w rzucie perspektywicznym x1/z1 =x2/z2 , y1/z1 =y2/z2

Modele oświetlenia:

*lokalne modele oświetlenia:

- model Phonga

- model Cooka - Torrance'a

*globalne modele oświetlenia:

- metody śledzenia promieni

- metody energetyczne

- połączona metoda energetyczna i śledzenia promieni

Lokalne modele oświetlenia biorą pod uwagę jeden punkt powierzchni i oświetlające go bezpośrednio źródła światła; światło bezpośrednie.

Globalne modele oświetlenia biorą pod uwagę odbicia światła między powierzchniami sceny; światło pośrednie.

Lokalny model oświetlenia Phonga:

Postrzegana przez obserwatora barwa dowolnego punktu powierzchni obiektu jest sumą:

- rozpraszania światła otaczającego

- odbicia rozproszonego

- odbicia zwierciadlanego

- samoświecenia

1. MODELE BARW.

Model RGB

Jest modelem opartym na kolorach światła. Światło widzialne składa się z trzech podstawowych barw składowych - światła czerwonego, zielonego i niebieskiego. Każdy z kolorów składowych ma 256 poziomów intensywności (24-bitowy zapis kolorów). Im większa jest liczba reprezentująca dany kolor tym kolor jest jaśniejszy. Model RGB jest również nazywany podstawowym modelem addytywnym, ponieważ kolor staj się jaśniejszy w miarę jak dodaje się więcej czerwonego , zielonego lub niebieskiego światła.

Wszystkie monitory, urządzenia projekcyjne i inne, które transmitują lub filtrują światło - włączając w to TV, projektory kinowe, kolorowe projektory światła działają w oparciu o model addytywny.

Model ten można przedstawić w postaci sześcianu rozpostartego na osiach R, G, B. Środek układu współrzędnych odpowiada barwie czarnej, natomiast wektor [1,1,1] reprezentuje barwę białą.

MODEL CMY

Model CMY podobnie jak RGB, tworzy przestrzeń barw w kształcie sześcianu. Barwami podstawowymi w tym modelu są: Cyan (morskim), Magneta (turkusowy) oraz Yellow (Żółty). W modelu tym w przeciwieństwie do modelu RGB, mieszanie barw odbywa się substraktywnie (mieszanie barw poprzez odejmowanie promieniowań widzialnych różnych długości (najczęściej poprzez pochłanianie niektórych długości fal przez powierzchnię, od której odbija się światło białe, lub szeregowo ustawionych filtrów światła przechodzącego przez nie).

W praktyce, w procesie druku często stosuje się 4 składowe: trzy barwy podstawowe uzupełnia się kolorem czarnym. Dzieje się tak dlatego, że złożenie trzech podstawowych barw CMY często nie daje koloru czarnego, tylko ciemny brąz lub ciemnoszary.

Dodanie czarnego koloru podnosi kontrast obrazu. Model CMY + czarny oznacza się CMYK.

MODEL HSV

Aby określić barwę w tym modelu, należy w pierwszej kolejności zdefiniować barwę spektralną (Barwy spektralne powstają, gdy światło słoneczne zostaje rozszczepione przez pryzmat na kolorową wstęgę (tęcza). Powstają wtedy pary kolorów, które nałożone na siebie, w oku ludzkim łączą się w kolor biały), a następnie podać ilość czerni i bieli, która musi zostać dodana do barwy spektralnej, aby otrzymać końcową barwę.

Parametry barwy w modelu HSV oznaczają Hue (spektrum), Saturation (nasycenie) oraz Value (wartość).

Reprezentacja trójwymiarowa modelu HSV przedstawiona jest za pomocą ostrosłupa foremnego o podstawie sześciokąta.

Wierzchołki podstawy symbolizują barwy spektralne. Środek podstawy oznacza barwę białą. Poruszając się zatem po podstawie, od krawędzi do środka sześciokąta otrzymuje się tonalne przejście od czystej barwy spektralnej do bieli, wysokość ostrosłupa określa ilość czerni dodanej do barwy, tak aby otrzymać ostateczną barwę wynikową.

MODEL HLS

Trójwymiarową interpretację tego modelu przedstawić można za pomocą dwóch stożków złączonych podstawami. Trzy parametry oznaczają odpowiednio Hue (spektrum), L (Lightness) , Saturation (nasycenie).

Parametr H oznacza to samo co w modelu HSV, to znaczy wartość koloru spektralnego. Parametr S oznacza względne nasycenie barwy. Ostatnim parametrem jest L - jasność barwy. Wierzchołki stożków odpowiadają brawie czarnej oraz białej.

11

Krzywe Beziera

łamana Beziera B-sklejana Cardinal NURBS

dla 0 ≤ t ≤ 1, gdzie parametr t zmienia się wzdłuż krzywej.

P_i - punkt kontrolny, B_i - funkcja bazowa, inaczej wielomian Bernsteina

Wielokąty rozpięte opisane na czterech punktach kontrolnych

P₁, P₂, P₃, P₄ segmentu Q(t)

krzywej Beziera.

segment Q(t)

Wektory styczne R₁, R₂ w końcowych punktach kontrolnych są równe:

R₁

R₂

R₁

R₂

Dwa segmenty krzywej Beziera

Krzywe sklejane (splajny)

Jednorodna nieułamkowa krzywa
B-sklejana (uniform nonrational
B-spline):

P - punkty kontrolne,

Q - segmenty krzywej,

t - węzły; t_i+1 - t_i =1

Każdy segment Q_i krzywej (zawarty między dwoma węzłami i, i+1) jest określony przez cztery punkty kontrolne.

Dlatego zmiana położenia punktu kontrolnego wpływa lokalnie na kształt krzywej sklejanej.

Niejednorodna nieułamkowa krzywa
B-sklejana (nonuniform nonrational
B-spline):

P - punkty kontrolne,

Q - segmenty krzywej,

t - węzły; węzły mogą być wielokrotne, tzn. t_i+1 = t_{i .}

Krzywe NURBS

(ang. Nonuniform Rational B-Splines)

Niejednorodne ułamkowe krzywe B -sklejane

gdzie: X(t), Y(t), Z(t), W(t) są wielomianami 1, 2, lub 3-go stopnia, których punkty kontrolne są określone we współrzędnych jednorodnych. Możemy przekształcić każdą nieułamkową krzywą w krzywą ułamkową dodając W(t) = 1 jako czwarty element.

Wielomianami krzywej ułamkowej mogą być np. wielomiany Beziera.

Jeżeli są to krzywe B-sklejane to mamy krzywe NURBS.

---