Wersja z 16:29, 23 lis 2007

Wykład

Komputerowe wspomaganie projektowania jest dziedziną stosunkowo nową, ale szeroko wykorzystywaną przez różnych specjalistów. Różnorakie zastosowania wymagają definicji – opisu reprezentacji różnych obiektów. Z jednej strony typowe obiekty mechaniczne czy architektoniczne, z drugiej efekty specjalne filmów science fiction, gdzie jedynym ograniczeniem jest wyobraźnia twórców. Z drugiej strony systemy wspomagania projektowania dają dodatkowe możliwości wykonywania wielu obliczeń związanych bezpośrednio z dziedziną zastosowania – obliczeń konstrukcyjnych czy wytrzymałościowych. Oczywiście grafika komputerowa daje możliwość zobaczenia projektu – możliwość wizualizacji wyobrażeń projektanta. Niezbędne staje się narzędzie do modelowania kształtu – obiektu, powierzchni. Warto zwrócić uwagę na fakt, że użytkownicy takich systemów reprezentują różne poziomy przygotowania informatycznego. System modelowania powinien być więc prosty i efektywny, powinien dawać możliwość definicji kształtu za pomocą minimalnej liczby parametrów, a modyfikacja kształtu powinna dotyczyć wybranego fragmentu, a nie całości krzywej czy powierzchni.

W latach sześćdziesiątych XX wieku w fabryce Renault rozpoczął pracę pierwszy system modelowania geometrycznego na użytek komputerowego wspomagania projektowania. Twórcą tego systemu był P. Bézier – będący jedną z najważniejszych postaci w tej dziedzinie. Dzisiaj każda fabryka samochodów projektuje kształty karoserii wykorzystując modelowanie geometryczne.

Istnieje wiele metod modelowania krzywych i powierzchni. Mają one różne właściwości i wymagają osobnego omówienia.

Wydawać by się mogło, że najprostszą forma modelowania krzywej jest wskazanie zbioru punktów na niej leżących a następnie połączenie ich krzywą interpolującą – najprościej wielomianową. Jeżeli dany jest ciąg parami różnych liczb Parser nie mógł rozpoznać (błąd składni): {\displaystyle t_0, t_1, t_2, …t_n } – węzłów interpolacyjnych i odpowiadających im punktom Parser nie mógł rozpoznać (błąd składni): {\displaystyle P_0, P_1, P_2,…P_n.} To poszukujemy krzywej wielomianowej $P (t)$ takiej, że jest ona stopnia co najwyżej $n$ oraz $P (t_{i}) = P_{i}$ dla każdego $i$ . Tak sformułowane zadanie jest zadaniem interpolacyjnym Lagrange’a i ma dokładnie jedno rozwiązanie w postaci:

$P (t) = Σ_{i = 0}^{n} P_{i} (\prod_{j = 0 j \neq i}^{n} \frac{t - t_{j}}{t_{i} - t_{j}})$

Dla małej liczby punktów (kilku) uzyskana krzywa zachowuje się zgodnie z oczekiwaniem. Niestety dla większej liczby punktów – krzywa wykazuje bardzo dużą wrażliwość na zaburzenia węzłów i skłonność do oscylacji – co pokazuje rysunek a). Dodatkowo każdy fragment krzywej zależy od wszystkich węzłów – brak jest lokalnej reprezentacji. Problem oscylacji można rozwiązać korzystając z interpolacji krzywą sklejaną – przedziałami wielomianową niskiego stopnia, rysunek b). Jednak w obu przypadkach kontrola nad kształtem krzywej pomiędzy węzłami jest trudna. Wady te powodują, że takie rozwiązanie jest praktycznie nieprzydatne.

Wiele krzywych jest opisanych równaniem uwikłanym. Taka reprezentacja nie daje możliwości kontroli konkretnego fragmentu krzywej.

Wygodnym sposobem opisu krzywych i powierzchni jest opis parametryczny. W tym przypadku za pomocą doboru wartości parametru można zdefiniować dowolny fragment krzywej, a kierunek wzrostu parametru jednoznacznie określa np. kierunki stycznych połączonych fragmentów. Przykładowa czterolistna koniczynka jest narysowana na rysunku a) w postaci rozety czterolistnej :

$x (t) = a \cdot s i n (2 \cdot t) \cdot c o s (t)$

$y (t) = a \cdot s i n (2 \cdot t) \cdot s i n (t)$

dla

$a > 0, 0 \leq t < 2 π$

Na rysunku b) w postaci hipotrochoidy:

$x (t) = (R + r) c o s (t) - λ r c o s (\frac{R + r}{r} t)$

$y (t) = (R + r) s i n (t) - λ r s i n (\frac{R + r}{r} t)$

dla

$R > 0, r < 0, λ > 1, 0 \leq t < 2 π$

Często wykorzystywanymi powierzchniami są powierzchnie drugiego stopnia. Ich równanie uwikłane ma postać:

$f (x, y, z) = P^{T} Q P = 0$

gdzie Q jest macierzą współczynników postaci

$Q = [\begin{matrix} A & D & F & G \\ D & B & E & H \\ F & E & C & J \\ G & H & J & K \end{matrix}]$

oraz

$P = [\begin{matrix} x & y & z & 1 \end{matrix}]$

Przy czym dla każdej powierzchni drugiego stopnia jest znana reprezentacja parametryczna. Dla przykładowej hiperboloidy jednopowłokowej z prezentowanego rysunku:

Zalety stosowania powierzchni drugiego stopnia: Możliwość łatwego wyznaczenia wektora normalnego

Parser nie mógł rozpoznać (nieznana funkcja „\cec”): {\displaystyle \cec N= [\frac{\delta f}{\delta x} \frac{\delta f}{\delta y} \frac{\delta f}{\delta z}]}

Możliwość szybkiego wyznaczenia przecięcia powierzchni z prostą – efektywność stosowania w algorytmach związanych z metodą śledzenia promieni. Możliwość szybkiego wyznaczenia $z$ na podstawie $x$ i $y$ – przydatne w algorytmach eliminacji elementów zasłoniętych.

Wielomiany Bernsteina są funkcjami bazowymi dla krzywych Béziera. Ich właściwości mają decydujący wpływ na właściwości krzywych.

Rysunek przedstawia wykresy wielomianów Bernsteina 2, 3, 4 i 5 stopnia. Najczęściej mamy do czynienia z wielomianami stopnia 3. W tym przypadku:

$B_{0, 3} (t) = (1 - t)^{3}, B_{1, 3} (t) = 3 t (1 - t)^{2}, B_{2, 3} (t) = 3 t^{2} (1 - t), B_{3, 3} (t) = t^{3}$

Ostatnia właściwość (zależność rekurencyjna) prowadzi do algorytmu wyznaczania punktów na krzywej bazującej na wielomianach Bernsteina.

Krzywa Béziera zawdzięcza swą nazwę Pierre’owi Bézierowi, warto jednak pamiętać,

że rozwiązanie to miało dwóch niezależnych twórców. Drugim był P. de Casteljau. Jego nazwiskiem został opatrzony podstawowy algorytm wyznaczania punktu krzywej. Krzywa Béziera stopnia $n$ jest definiowana przez $n + 1$ punktów Parser nie mógł rozpoznać (błąd składni): {\displaystyle P_0, P_1, P_2,…P_n} w bazie wielomianów Bernsteina. Jest to krzywa gładka, której kształt zależy od położenia punktów kontrolnych. Najczęściej stosowane są krzywe stopnia 3. Użytkownicy komputerów spotykają się z nią na co dzień w postaci fontów, których kształt jest projektowany właśnie z jej wykorzystaniem

Krzywa Béziera interpoluje dwa końcowe punkty kontrolne i aproksymuje pozostałe. Oznacza to, że dla krzywej stopnia 3 , jeśli ustalone są punkty końcowe (a tak jest najczęściej), to dwa pozostałe punkty decydują o kształcie.

Wady:

- Brak możliwości reprezentacji krzywych stożkowych.

- Zmiana reprezentacji krzywej po rzutowaniu perspektywicznym.

Korzystając z właściwości rekurencyjnej wielomianów Bernsteina można wyznaczyć punkty krzywej Béziera.

Algorytm de Casteljau wyznaczania punktu leżącego na krzywej Béziera na podstawie ciągu punktów kontrolnych Parser nie mógł rozpoznać (błąd składni): {\displaystyle P_0, P_1, P_2,…P_n}

for i:= 0 to n do  $P_{i},_{0} = P_{i}$ ;
for j:=1 to n do 
      for i:=j to n do
             $P_{i},_{j}$  :=  $(1 - t) * P_{i}_{-}_{1},_{j}_{-}_{1} + t * P_{i},_{j}_{-}_{1}$ ;

Jeśli zadaniem jest wyznaczenie dużej liczby punktów leżących na krzywej Béziera to tańszym obliczeniowo rozwiązaniem będzie przejście w wielomianach Bernsteina do postaci naturalnej wielomianu i obliczanie jego wartości algorytmem Hornera.

W praktyce rzadko kiedy używa się krzywych Béziera wysokiego stopnia. Ponieważ każdy punkt krzywej Béziera zależy od wszystkich punktów kontrolnych, więc w takiej sytuacji trudno byłoby kontrolować kształt krzywej. O wiele prościej jest złożyć całą krzywą z fragmentów, każdy niskiego stopnia.

Rozpatrzmy dwa segmenty krzywych $P_{0}, P_{1}, P_{2}, P_{3}$ i $R_{0}, R_{1}, R_{2}, R_{3}$ , połączone w punkcie $P_{3} = R_{0}$ . Jeżeli punkty $P_{2}, P_{3} = R_{0}, R_{1}$ są współliniowe mówimy o ciągłości geometrycznej G1 krzywej (rysunek a). Jeżeli punkty $P_{2}, P_{3} = R_{0}, R_{1}$ są współliniowe i sąsiednie odcinki łamanej są równej długości $(P_{2} - P_{3}) = (R_{0} - R_{1})$ to mówimy o ciągłości parametrycznej C1 krzywej (rysunek b).

Krzywe wymierne Béziera opisane są w przestrzeni jednorodnej. Oznacza to, że analogicznie do przekształceń geometrycznych opisanych macierzowo w przestrzeni jednorodnej, krzywe płaskie będą opisane w

R^{3}

, natomiast krzywe trójwymiarowe będą opisane w przestrzeni

R^{4}

.

Krzywa taka ma następujące cechy: Dana krzywa może mieć nieskończenie wiele reprezentacji we współrzędnych jednorodnych. Pomnożenie wszystkich wag przez tę samą stałą różną od zera nie zmienia krzywej. Krzywa wymierna jest uogólnieniem krzywej wielomianowej. Dla równej wartości wszystkich wag otrzymujemy krzywą wielomianową Béziera. Konstrukcja krzywej wymiernej jest niezmiennicza afinicznie. Krzywa wyznaczona na podstawie ciągu punktów kontrolnych jest taka sama jak krzywa wyznaczona na podstawie ciągu punktów kontrolnych poddanych przekształceniom afinicznym. Zmieniając odpowiednio wagi można uzyskać wszystkie krzywe stożkowe. Ta cecha była nieosiągalna w przypadku krzywych wielomianowych Béziera.

Krzywa B-sklejana jest definiowana jako kombinacja liniowa funkcji sklejanych

N_{i}^{m} (t)

o współczynnikach odpowiadających punktom kontrolnym (punktom de Boora). Funkcje sklejane są przedziałami stopnia

m

, co nie jest związane z liczbą punktów tak jak w przypadku krzywych Béziera. Oznacza to rzeczywiście uniezależnienie stopnia wielomianu opisującego krzywą (oczywiście przedziałami w tym przypadku) od liczby punktów kontrolnych.

Zakłada się, że węzły $t_{i}$ są uporządkowane niemalejąco tzn. $t_{i} \leq t_{i + 1}$ co oznacza, że mogą istnieć równe węzły (wielokrotne). Przyjmuje się wtedy, że 0/0=0. Takie założenia generalnie definiują krzywą dla węzłów które nie musza być równoodległe. Jednocześnie możliwość dodania (wstawienie) węzła pomiędzy dwa już istniejące, lub zwielokrotnienia węzła daje dodatkowe możliwości wpływania na kształt krzywej. Czasami jednak rozpatruje się krzywe o węzłach równoodległych. Istnieje algorytm de Boora i Coxa wyznaczania punktów krzywej B-sklejanej (analogiczny do algorytmu de Casteljau krzywej Béziera). Jeśli wyznaczanych jest wiele punktów krzywej to tańszym rozwiązaniem będzie obliczenie współczynników postaci naturalnej wielomianu w kolejnych podprzedziałach i skorzystanie z algorytmu Hornera.

Pierwsza właściwość – zerowanie funkcji sklejanej poza przedziałem

< t_{i}, t_{i + m + 1} >

jest bardzo istotna dla modelowania kształtu. Oznacza bowiem lokalność wpływu parametrów. Rozpatrzmy podprzedział

< t_{i}, t_{i + m + 1} >

dla

t \in (t_{i}, t_{i + m + 1})

niezerowe są tylko funkcje

N_{i}^{m} (t)

o indeksach

i = j - m, j - m + 1, j - m + 2, j

. W takim przedziale wartość

Q (t)

, a tym samym kształt krzywej, zależy tylko od punktów kontrolnych Parser nie mógł rozpoznać (błąd składni): {\displaystyle P_{j-m}, P_{j-m+1}, P_{j-m+2},…P_j} . Z drugiej strony punkt kontrolny

P_{i}

wpływa jedynie na fragment krzywej odpowiadający

t \in < t_{i}, t_{i + m + 1} >

.

Indeks $j$ zmienia się od 0 do $m$ , natomiast $i$ od 0 do $n$ . Cały zakres takiej krzywej definiują więc węzły: $t_{0} \leq t_{1} \leq t_{2} \leq . . . \leq t_{n}_{+}_{m}_{+}_{1}$ . Ale danych jest $n + 1$ punktów kontrolnych (de Boora). Punkty Parser nie mógł rozpoznać (błąd składni): {\displaystyle P_0, P_1, P_2,…P_m} definiują krzywą dla $t \in < t_{m}, t_{m + 1} >$ , natomiast punkty Parser nie mógł rozpoznać (błąd składni): {\displaystyle P_{n-m}, P_{n-m+1}, P_{n-m+2},…P_n} definiują krzywą dla $t \in < t_{n}, t_{n + 1} >$ . Węzły $t_{0}, t_{1}, t_{2}, . . ., t_{n}$ oraz $t_{n + 1}, t_{n + 2}, . . ., t_{n + m + 1}$ nazywane są węzłami brzegowymi. Jeśli krzywa jest otwarta, to znaczy $Q (t_{m}) \neq Q (t_{n + 1})$ , i $t_{0} = t_{1} = t_{2} = . . . = t_{m}$ oraz $t_{n + 1} = t_{n + 2} = . . . = t_{n + m + 1}$ to krzywa przechodzi przez końcowe punkty kontrolne, czyli $Q (t_{m}) = P_{0}$ oraz $Q (t_{n + 1}) = P_{n}$ . Podobnie jak było w przypadku krzywych Béziera, styczne do krzywej w punktach końcowych mają kierunek końcowych odcinków łamanej kontrolnej. Dla krzywej zamkniętej przyjmuje się, że punkty de Boora i węzły kontrolne są cykliczne $(P_{n} = P_{0})$ .

Wymierne krzywe B-sklejane (ang. Non-Uniform Rational B-Splines) to rozwiązanie, które łączy zalety krzywych Béziera i krzywych B-sklajenych.

Krzywe wymierne dają możliwość wykreślenia dowolnej krzywej stożkowej. .Konstrukcja wykorzystująca funkcje sklejane pozwala opisywać krzywą wielomianami, których stopień jest niezależny od liczby punktów kontrolnych. Wpływ punktu kontrolnego na kształt krzywej istnieje tylko w zakresie lokalnym. Dodatkowo wagi każdego punktu kontrolnego pozwalają na precyzyjne zmiany kształtu krzywej (też lokalnie). Krzywe wymierne są niezmiennicze względem przekształceń obrotu, skalowania i przesunięcia oraz przekształcenia perspektywicznego punktów kontrolnych.

Właściwości powierzchni są analogiczne do właściwości krzywych konstruowanych z wykorzystaniem tych samych funkcji bazowych. Z drugiej strony przyjmując stałość jednego parametru (u lub v) otrzymujemy krzywą (rodzinę krzywych dla różnych wartości parametru.

Przedstawione tutaj sposoby modelowania kształtu krzywej i powierzchni należą do najbardziej uniwersalnych i najczęściej stosowanych.. Istnieje jednak wiele innych reprezentacji.

Wykorzystując bazę wielomianów Hermite’a otrzymamy krzywe i powierzchnie Hermite’a. Płaty Coonsa są definiowane za pomocą czterech krzywych brzegowych mających wspólne punkty narożne oraz interpolacji między nimi. Powierzchnie Gordona są uogólnieniem płatów Coonsa,. definiują powierzchnię za pomocą dwóch wzajemnie przecinających się rodzin krzywych. Stosowane jest również modelowanie kształtu powierzchni w oparciu o fragmenty trójkątne. Zarówno w postaci powierzchni Béziera jak i B-sklejanej.

Zastosowania CAD/CAM, zastosowania symulacyjne często wymagają definicji obiektów trójwymiarowych, które odzwierciedlałyby pewne wybrane cechy fizyczne. We wspomaganiu projektowania ważne staje się na przykład rozgraniczenie na powierzchnie wewnętrzne i zewnętrzne, położenie środka ciężkości czy objętość obiektu. Oprogramowanie wykorzystywane w tego typu zastosowaniach powinno dawać możliwość edycji (wprowadzenia i późniejszego poprawiania) kształtu obiektu i możliwość efektywnego przechowywania opisu obiektu. Zwykle wymagane jest także współdziałanie modułu edycji z programami specjalistycznymi w zakresie wyznaczania parametrów fizycznych. Oczywiście modelowanie i edycja powinno być efektywne to znaczy dawać możliwość łatwego definiowania opisu skomplikowanych elementów. Potrzeba opisu spełniającego takie warunki – reprezentacji obiektu – doprowadziła do powstania kilku różnych metod reprezentacji wymagających niezależnego omówienia.

W zasadzie można byłoby stwierdzić, że oczekiwane właściwości końcowe projektu i wyobraźnia projektantów powinna być jedynymi ograniczeniami narzuconymi na proces wspomagania projektowania. W takim razie przez obiekt graficzny należałoby rozumieć cokolwiek, co da się narysować przy pomocy komputera. Wydaje się jednak, że celem nie jest swoboda projektowania ale efekt końcowy jakim jest realizacja fizyczna danego obiektu. I z tego powodu bardzo często wprowadza się pewne ograniczenia reprezentacji.

Zaproponowany zestaw właściwości bryły jest pewnym kompromisem między swobodą projektowania a zastosowaniami praktycznymi, kompromisem, który daje przy tym możliwość efektywnego wspomagania projektowania. Przykładem jak należy rozumieć ten kompromis jest jednorodność topologiczna. Z jednej strony nie ma w zasadzie żadnych przeciwwskazań w grafice komputerowej aby tworzyć obiekty niejednorodne (np. krzesło w postaci trójwymiarowego sześciennego siedziska połączonego z dwuwymiarowym prostokątnym oparciem). Ale jednocześnie ujednolicenie opisu może uprościć podejście do różnie definiowanych elementów. Natomiast jeśli popatrzymy na problem od strony praktycznej ; technologicznie realizacyjnej, to okaże się, że problem w zasadzie nie istnieje ponieważ żyjemy wśród obiektów trójwymiarowych jednorodnych topologicznie i praktyczne wykonanie prostokątnego oparcie dla rozpatrywanego krzesła i tak będzie wymagało określenia trzeciego wymiaru – jego grubości. Jeśli już nawet dla spełnienia wizji projektanta jest niezbędne istnienie niejednorodności topologicznej to prościej jest założyć, że w ramach jednej bryły zachowujemy jednorodność i w ostateczności dopuszczamy zestawienie różnych brył w ramach jednego procesu. Chociaż i tak w efekcie końcowym na etapie technologii zostanie to ujednolicone. Drugim elementem opisu właściwości bryły na który warto zwrócić uwagę jest domknięcie bryły. To co widzimy obserwując dowolny przedmiot jest efektem odbicia światła od powierzchni tego przedmiotu. Jeśli zostanie on przekrojony to zobaczymy powierzchnię przekroju – to znaczy będzie to nowy brzeg powstały przecięcia. Powierzchnia brzegu obiektu jest więc bardzo istotna w procesie rysowania – wizualizacji obiektu.

Proces rozwiązania problemu domknięcia bryły nazywany jest regularyzacją zbioru. Jeśli rozpatrzymy dowolny obiekt jako pewien zbiór punktów to można wyróżnić punkty wewnętrzne tworzące zbiór otwarty, punkty brzegowe (punkty których odległość zarówno od obiektu jak i jego uzupełnienia jest równa zeru) oraz zbiór domknięty zawierający wszystkie jego punkty wewnętrzne i wszystkie brzegowe. Rysunek pokazuje regularyzację zbioru. Kolejne etapy to: domknięcie poprzez przejęcie do wnętrza ewentualnych punktów zdefiniowanych jako brzeg (np. w wyniku jakiejś operacji na zbiorach), a które w rzeczywistości znajdują się we wnętrzu. Otwarcie zbioru pozwalające wyeliminować punkty brzegowe niepołączone z wnętrzem. Ponowne domknięcie dające regularyzację zbioru.

Konstruktywna geometria brył (ang. constructive solid geometry – CSG) jest metodą reprezentacji obiektów polegająca na definicji obiektu jako wyniku regularyzowanych operacji boolowskich. Obiekt jest zapisywany (pamiętany) jako drzewo o odpowiedniej budowie ( z określonymi operacjami w węzłach i prymitywami w liściach). To znaczy metoda ta nie podaje opisu gotowego obiektu, podaje natomiast "przepis" jak go stworzyć.

Aby zdefiniować obiekt trzeba podać z jakich elementów go zbudować (z jakich prymitywów jest on skonstruowany) oraz podać w jaki sposób prymitywy te konstruują obiekt (podać drzewo operacji koniecznych do uzyskania obiektu).

Zestaw prymitywów należy rozumieć bardzo szeroko. Z jednej strony jest to zestaw „klocków” potrzebny do definicji danego zestawu elementów na scenie. Z drugiej strony zestaw ten powinien być na tyle szeroki aby nie stwarzać problemów przy definicji dowolnych elementów sceny w ramach pewnej klasy. Można na przykład założyć że scena będzie zawierała tylko elementy wielościenne. Wtedy naturalnym byłoby zestawienie zbioru prymitywów w postaci wzorców każdego rozpatrywanego typu wielościanu. Można się zastanowić, czy wygodniejszym nie byłoby użycie tylko jednego prymitywu – półprzestrzeni. W takiej sytuacji za pomocą różnych ustawień półprzestrzeni i operacji boolowskich (regularyzowanych) można byłoby skonstruować dowolny wielościan bez żadnych ograniczeń i co ważne, zawsze w taki sam sposób. Jednak w takiej sytuacji należałoby pamiętać o tym, że w przeciwieństwie do operacji na klockach będących bryłami, operacje przeprowadzane na półprzestrzeniach mogą w ogóle nie dawać bryły. I regularyzacja operacji w takiej sytuacji nie pomoże. Wybór prymitywów jest sprawą bardzo ważną . Powinien być dokonany w zależności od typu obiektów jakie pojawiają się na scenie oraz możliwości systemu modelowania i celów dla jakich został on zbudowany..

Konstruktywna geometria brył jest techniką, w której poważnym problemem jest definicja brzegu i wyznaczenie go po wykonaniu operacji boolowskich. Konieczność stosowania operacji regularyzowanych pokazuje rysunek. Jeśli wykonamy iloczyn lub różnicę brył A i B, to mogą pojawić się obszary dla których nie będzie zdefiniowany brzeg, ale również obszary dla których brzeg będzie określony niejednoznacznie. Zastosowanie regularyzacji zbioru (regularyzowanych operatorów boolowskich) zapewnia poprawność konstrukcji.

Reprezentacja brzegowa (ang. b-rep – boundary representation) opisuje obiekt za pośrednictwem opisu jego brzegu – powierzchni ograniczającej obiekt. Możemy tu mieć do czynienia z modelem wielościennym (ang. polygonal representation) lub powierzchniowym, w którym kształt brzegu obiektu jest opisany parametrycznie.

Dla modelu wielościennego istotnym problemem jest organizacja struktury danych zapamiętującej obiekt. Realizowane jest to w postaci list lub tablic ścian, krawędzi i wierzchołków. Pamiętanie powiązań między elementami obiektów prowadzi do struktur redundantnych. Wiąże się to oczywiście ze wzrostem kosztu pamięciowego. Czasami celowo wprowadzane są struktury redundantne w celu przyspieszenia wyszukania elementów. Takimi strukturami są na przykład DCEL (double connected edg list) i struktura krawędziowa Baumgarta. Są to struktury, w których deskryptory krawędzi zawierają wskazania na sąsiednie krawędzie, węzły i ściany.

Model wielościenny może być reprezentowany dowolną siatką wielokątów. Rodzaj siatki zależy od budowy obiektu i sposobu jego definiowania. Przypisanie położenia poszczególnym punktom i powiązań tworzących siatkę może być realizowane ręcznie przez konstruktora. Może wynikać z matematycznego opisu obiektu – można wykorzystać charakterystyczne przekroje obiektu, albo linie stałego parametru. Może to być zrealizowane automatycznie na podstawie pomiarów położenia i kształtu obiektu rzeczywistego lub jego modelu. Często wykorzystywane są siatki trójkątów, gdyż przy dowolnym rozmieszczeniu węzłów siatka taka gwarantuje, że każde jej oczko zawsze będzie figurą płaską – wielokątem.

Dla każdego wielościanu zwykłego spełniona jest reguła Eulera. Rozszerzoną klasę obiektów - rozmaitości dwuwymiarowych obowiązuje uogólniona (rozszerzona) reguła Eulera. Należy jednak pamiętać że spełnienie tych warunków jest warunkiem koniecznym ale niewystarczającym przynależności do odpowiedniej klasy. Na przykład sześcian, do którego krawędzi doczepiono jeszcze jeden prostokąt nie jest już wielościanem zwykłym ale regułę Eulera (podstawową) spełnia.

Reprezentacja brzegowa jest czasem łączona w systemach modelowania z konstrukcyjną geometrią brył.

Reprezentacja z przesunięciem (ang. sweet) nazywane czasem zagarnianiem lub zakreślaniem przestrzeni buduje obiekt przez przemieszczenie przekroju wzdłuż pewnej trajektorii. Obiekt tworzą wszystkie punkty znajdujące się na drodze przekroju. Najprostsze do takiej definicji są obiekty podobne do przedstawionego na rysunku. Ale również kula torus czy spirale są proste do takiego definiowania. Dla bardziej skomplikowanych kształtów można zaproponować możliwość zmiany kształtu w funkcji trajektorii.

Reprezentacja z przesunięciem nie stanowi samodzielnego sposobu opisu. Najczęściej jest łączona z reprezentacją powierzchniową i służy do definicji położenia węzłów siatki wielokątów. Ewentualnie (rzadziej) jest łączona z konstrukcyjną geometrią brył.

Podział przestrzeni jest sposobem opisu polegającym na rozkładzie obiektu na elementy składowe, prostsze.

Woksel jest najmniejszym elementem przestrzeni analogicznym do piksela na płaszczyźnie. Można zdefiniować obiekt wskazując, które woksele on zajmuje. Taka reprezentacja jest dekompozycją na komórki, które tworzą regularną siatkę w przestrzeni. Podstawową cechą reprezentacji tego typu jest aproksymacja kształtu z zadana rozdzielczością. Struktura danych opisująca tak dekomponowaną bryłę będzie listą zajętych komórek. Podobny efekt można uzyskać strukturą hierarchiczną – drzewem ósemkowym wskazując w przestrzeni kolejne prostopadłościenne elementy będąca wielokrotnością woksela. W tym przypadku jednak struktura danych (drzewo ósemkowe) da efektywniejszy sposób zapisu (mniejszy koszt pamięciowy). Natomiast aproksymacja kształty z zadana rozdzielczością wokselową będzie identyczna. Alternatywą dla drzewa ósemkowego mogłoby być drzewo podziału binarnego (ang. BSP tree – binary space partitioning tree), w którym na każdym etapie podziału można wskazać którą półprzestrzeń reprezentuje dany fragment obiektu. Drzewa tego typu nie są jednak stosowane jako samodzielne systemy modelowania. SA natomiast wykorzystywane w algorytmach eliminacji elementów zasłoniętych

Podsumowując zaprezentowane sposoby reprezentacji obiektów można porównać ich podstawowe właściwości.

Dokładność. Jeśli na scenie znajdują się obiekty wielościenne to reprezentacje wielościenne mogą dać dokładny opis obiektu. W pozostałych przypadkach tylko reprezentacja powierzchniowa z opisem kształtu za pomocą powierzchni Béziera, B-sklejanych, lub funkcji wymiernych może dać dokładny opis. Z reguły mamy do czynienia z pewną aproksymacją zależną np. od rozdzielczości siatki wokseli.

Dziedzina (zakres stosowania). Podział przestrzeni może być stosowany do dowolnych obiektów, przy czym zawsze będzie istniał problem aproksymacji zależny od siatki wokselowej. Pozostałe metody reprezentacji mogą być stosowane do określonej klasy obiektów. Na przykład w konstrukcyjnej geometrii brył klasa reprezentowanych obiektów bardzo silnie zależy od zastosowanego zestawu prymitywów.

Jednoznaczność/unikatowość. W zasadzie tylko podział przestrzeni za pomocą drzewa ósemkowego i reprezentacja wokselowa zapewniają unikatowośc reprezentacji w tym sensie, że istnieje tylko jeden zestaw wokseli reprezentujący dany obiekt. W pozostałych systemach modelowania istnieje wiele możliwości opisu tego samego obiektu. Szczególnym przypadkiem jest konstruktywna geometria brył gdzie dany obiekt można uzyskać nie tylko korzystając z różnych drzew, ale także z różnych zestawów prymitywów.

Poprawność. Podział przestrzeni jest zawsze poprawny – zawsze uzyskamy poprawny fragment przestrzeni. Pytanie oczywiście czy jest to ten fragment o który chodziło konstruktorowi. W pozostałych przypadkach wymagane jest sprawdzenie czy wynik definiowania/operacji jest poprawnym obiektem w danej klasie. Najtrudniejsze do sprawdzenia są opisy reprezentacji powierzchniowej.

Efektywność. Najprostsze w reprezentacji są metody wokselowe, gdyż pozwalają na szybkie manipulowanie takimi obiektami. Również konstruktywna geometria brył daje prosty nieprzetworzony (wymagający przetworzenia w trakcie np. rysowania) mechanizm, pozwalający dodatkowo na szybką modyfikacje obiektów.

Wiele obiektów naturalnych (rośliny, formy skalne, linia brzegowa, zbocza gór itp.) a także sztucznych (np. polimery) ma cechę samopodobieństwa. Obrazy tych obiektów są podobne bez względu na skalę w jakiej, są oglądane.

Często klasyfikuje się to pojęcie Samopodobieństwo dokładne – mówimy o nim wtedy, kiedy występuje wierna kopia powiększonego lub pomniejszonego fragmentu. Taką cechę mają fraktale IFS. Quasi- samopodobieństwo – gdy występuje przybliżona kopia powiększonego lub pomniejszonego fragmentu. Charakterystyczne dla wielu fraktali definiowanych pewną zależnością rekurencyjną definiującą położenie punktów w przestrzeni. Samopodobieństwo statystyczne – tę cechę mają fraktale losowe.

Rysunek z lewej strony pokazuje jeden z najbardziej znanych fraktali - tak zwany zbiór Mandelbrota. Zbiór ten powstaje przez interpretację barwami właściwości ciągu liczb zespolonych postaci $z_{i + 1} = z_{i}^{2} + c$ .

Twórcą geometrii fraktalnej i samego pojęcia fraktal jest B.Mandelbrot - francuski matematyk polskiego pochodzenia. Przykładem najprostszym iteracyjnie generowanego fraktala jest tal zwana śnieżynka Kocha zaproponowana przez H. von Kocha w 1904 roku. W każdym kroku iteracji każdy odcinek jest dzielony na trzy części (segmenty) po czym w miejsce jednego segmentu środkowego są wstawiane dwa segmenty tworząc z podstawą trójkąt równoboczny. Przy liczbie iteracji dążącej do nieskończoności otrzymuje się figurę, której każdy fragment jest zbudowany dokładnie na tej samej zasadzie (samopodobieństwo) i jednocześnie tak uzyskana krzywa ma nieskończoną długość oraz nie ma stycznej w żadnym punkcie.

Problemem pozostaje wymiar takiej krzywej. Dla fraktali określa się wymiar Hausdorffa. F.Hausdorf – matematyk niemiecki zaproponował pojęcie wymiaru jako miarę wzrostu liczby kul (lub kół na płaszczyźnie) o promieniu  potrzebnych do pokrycia danego zbioru przy  dążącym do zera. Wymiar Hausdorffa nigdy nie jest mniejszy niż wymiar topologiczny danego zbioru. Dla fraktali jest liczbą ułamkową. Sniezynka Kocha ma wymiar d=log4/log3=1,2618…

Fraktale stosuje się w grafice komputerowej do modelowania kształtu obiektów naturalnych wykazujących samopodobieństwo. Przykładem może być modelowanie krajobrazu. Fourier, Fussel i Carpenter zaproponowali zastosowanie iteracyjnego podziału do generowania fraktalnej góry. Jeśli podstawę góry będziemy dzielić systematycznie na pół, to po odpowiedniej liczbie iteracji uzyskamy punkty o zadanej dokładności. Wysokość dla każdego punktu podziału określa się na podstawie wysokości punktów poprzedniego kroku iteracji oraz pewnej funkcji zaburzenia. W zależności od przyjętej funkcji zaburzenia można w ten sposób otrzymać odpowiedni charakter zmian wysokości (łagodne pagórki lub ostre szczyty).

Innym zastosowaniem fraktali w grafice i przetwarzaniu obrazów jest kompresja fraktalna.

Przekształcenie afiniczne nazywamy zwężającym jeśli długość każdego odcinka po przekształceniu jest mniejsza niż przed przekształceniem.

Metryka Hausdorffa określa odległości między zbiorami. Jeśli rozpatrzymy dwa zbiory A i B, to odległością d(a,B) punktu a ze zbioru A od zbioru B jest najmniejsza odległość spośród odległości tego punktu od wszystkich punktów zbioru B. Odległością d(A,B) zbioru A od zbioru B jest to największa odległośc spośród odległości punktu zbioru A od zbioru B. Metryka Hausdorfa h(A,B) jest określona wyrażeniem: h(A,B)=max(d(A,B), d(B,A))

Atraktory rozpatrywane są w przestrzeni metrycznej zupełnej, w której obowiązuje metryka Hausdorffa.

L-systemy zwane także L-układami służą, przede wszystkim, do opisu wzrostu roślin. Bardzo trudno byłoby klasycznymi metodami modelowania (np. CSG lub reprezentacja powierzchniowa) wygenerować obrazy roślin – gałęzi, liści itp. Elementy roślin zachowują samopodobieństwo i podlegaja pewnym regułom związanym z rozwojem - wzrostem rośliny. A.Lindenmayer zaproponował w 1969 roku sposób opisu wzrostu oparty na prostych regułach gramatycznych. System ten był później rozwijany, między innymi przez A.R.Smitha i P.Prusinkiewicza.

Na tej samej zasadzie można opisać grafikę żółwia rozkładając ruch pióra na proste reguły sterowania. Warto zwrócić uwagą na fakt, że również fraktale takie jak śnieżynka Kocha czy dywan Sierpińskiego można wygenerować za pomoca L-systemu.

Na przykład dla śnieżynki Kocha (dla pojedynczego boku startowego trójkąta !) aksjomat: F reguła produkcji: F -> F-F++F-F

gdzie F oznacza ruch do przodu z rysowaniem, - oznacza obrót w lewo o zadany kąt $α$ , + oznacza obrót w prawo o zadany kąt $α$ . Dla śnieżynki Kocha $α$ wynosi 60 stopni.

Paprotka Barnsleya jest chyba najbardziej znanym przykładem wykorzystania gramatyk do modelowania roślin.

Pierwotne języki równoległych gramatyk grafowych zostały przez Lindenmayera rozszerzone o dodanie nawiasów (różnych, co daje możliwość rozróżnienia operacji) pozwalających na zagnieżdżanie operacji z wykorzystaniem stosu.

W opisie reguł produkcji wykorzystuje się takie symbole atrybutów jak długość i szerokość odcinka czy barwę. Pozwala to dość swobodnie definiować reguły wzrostu.

L-system można niezależnie uzupełnić o dodatkowe zasady „obowiązujące” roślinę w trakcie wzrostu. Pozwala to symulować naturalne zjawiska takie jak tropizm (naturalne kierowanie się rośliny w kierunku słońca) i geotropizm (reakcja wzrostowa roślin na siłę ciężkości).

Modelowanie wolumetryczne jest próbą rozwiązania problemu modelowania i wizualizacji zjawisk, które nie dają się opisać w prosty sposób klasycznymi metodami, a które to zjawiska związane są z objętościowym rozproszeniem światła. Efekt taki powstaje zazwyczaj na skutek istnienia pewnego dodatkowego czynnika zmieniającego warunki rozchodzenia się światła. Przykładem może być mgła, chmury, wydobywający się gaz lub para wodna.

Podobne efekty mogą powstawać przy przechodzeniu światła przez niejednorodne ośrodki półprzezroczyste np. powierzchnię morza. Analogicznie modeluje się przekroje na potrzeby prześwietleń w medycynie. W przypadku takich badań jak tomografia komputerowa (CT) czy rezonans magnetyczny (MRI) jest to związane z wizualizacją trójwymiarowej funkcji pochłaniania promieniowania. Funkcja ta określona jest dla każdego punktu przestrzeni pokazując właściwości badanej tkanki.

Stosuje się następujące metody:

• Metody uproszczone. Wizualizacja za pomocą tekstur (dwuwymiarowych rzadziej trójwymiarowych). Wizualizacja za pomocą półprzepuszczalnych płaszczyzn (jednej lub kilku) z nałożonymi obrazami zjawiska. Metody te dają dobre efekty i są efektywnie obliczeniowo, ale związane są tylko z określonym kierunkiem patrzenia. Metody takie stosuje się do uproszczonego modelowania mgły i chmur oraz podobnych zjawisk (np. w grach komputerowych).

Metoda próbek w przestrzeni (particle tracing) polegająca na umieszczeniu (zazwyczaj półprzezroczystych) elementów (kul, walców, sześcianów) w przestrzeni, mających rozpraszać światło – lub generalnie zmieniać warunki jego rozchodzenia się. Metodami takimi wizualizuje się chmury, mgłę i podobne zjawiska.

Metoda analizy objętościowej. (volume rendering) polegająca na przypisaniu właściwości rozpraszających określonym punktom w przestrzeni. Jest to realizowane najczęściej w postaci wokselowej – każdy weksel ma określone parametry związane z przechodzeniem światła. Podczas śledzenia promieni wyznaczane są woksele na drodze promienia i ich parametry wpływają na barwę promienia. Analogicznie jest analizowane tak zwane światło wolumetryczne (volume light). Metody te stosuje się przede wszystkim w medycynie. Czasami stosuje się je do modelowania mgły lub chmur. Światło wolumetryczne pozwala symulować reflektory świecące we mgle, kurz unoszący się w powietrzu i rozpraszający światło w delikatny sposób, zadymione pomieszczenia.

Metody uproszczonego opisu fizycznego zjawiska. Opis szumu trójwymiarowego i turbulencji, wykorzystanie szumu Perlina. Takie metody najczęściej stosuje się do wizualizacji płomienia, dymu, chmur, tworzenia efektu ognia i wybuchu. Metody te są często realizowane w postaci złożonej tekstury trójwymiarowej..

Warto zwrócić uwagę na funkcję szumu opracowaną przez K.Perlina w 1985 roku (uzupełniona w 2002). Funkcja ta jest gładką interpolacją wektora gradientu między węzłami siatki. Jest ona prosta w implementacji i daje zaskakująco dobre efekty. Z tego powodu szum Perlina jest często dodawany do tekstur różnych powierzchni aby podkreślić drobne niejednorodności rzeczywistych obiektów i nadać naturalny wygląd.

Literatura

@@ Linia 302: / Linia 302: @@
 |valign="top"|Podsumowując zaprezentowane sposoby reprezentacji obiektów można porównać ich podstawowe właściwości.
-Dokładność.
+'''Dokładność'''.
 Jeśli na scenie znajdują się obiekty wielościenne to reprezentacje wielościenne mogą dać dokładny opis obiektu. W pozostałych przypadkach tylko reprezentacja powierzchniowa z opisem kształtu za pomocą powierzchni Béziera, B-sklejanych, lub funkcji wymiernych może dać dokładny opis. Z reguły mamy do czynienia z pewną aproksymacją zależną np. od rozdzielczości siatki wokseli.
-Dziedzina (zakres stosowania).
+'''Dziedzina (zakres stosowania)'''.
 Podział przestrzeni może być stosowany do dowolnych obiektów, przy czym zawsze będzie istniał problem aproksymacji zależny od siatki wokselowej. Pozostałe metody reprezentacji mogą być stosowane do określonej klasy obiektów. Na przykład w konstrukcyjnej geometrii brył klasa reprezentowanych obiektów bardzo silnie zależy od zastosowanego zestawu prymitywów.
-Jednoznaczność/unikatowość.
+'''Jednoznaczność/unikatowość'''.
 W zasadzie tylko podział przestrzeni za pomocą drzewa ósemkowego i reprezentacja wokselowa zapewniają unikatowośc reprezentacji w tym sensie, że istnieje tylko jeden zestaw wokseli reprezentujący dany obiekt. W pozostałych systemach modelowania istnieje wiele możliwości opisu tego samego obiektu. Szczególnym przypadkiem jest konstruktywna geometria brył gdzie dany obiekt można uzyskać nie tylko korzystając z różnych drzew, ale także z różnych zestawów prymitywów.
-Poprawność.
+'''Poprawność'''.
 Podział przestrzeni jest zawsze poprawny – zawsze uzyskamy poprawny fragment przestrzeni. Pytanie oczywiście czy jest to ten fragment o który chodziło konstruktorowi. W pozostałych przypadkach wymagane jest sprawdzenie czy wynik definiowania/operacji jest poprawnym obiektem w danej klasie. Najtrudniejsze do sprawdzenia są opisy reprezentacji powierzchniowej.
-Efektywność.
+'''Efektywność'''.
 Najprostsze w reprezentacji są metody wokselowe, gdyż pozwalają na szybkie manipulowanie takimi obiektami. Również konstruktywna geometria brył daje prosty nieprzetworzony (wymagający przetworzenia w trakcie np. rysowania) mechanizm, pozwalający dodatkowo na szybką modyfikacje obiektów.

GKIW Moduł 6 - Modelowanie obiektów: Różnice pomiędzy wersjami

Wersja z 16:29, 23 lis 2007

Spis treści

Wykład

Literatura

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia