Rozsah látky
Seznam oficiálních státnicových otázek:
:: Projektivní rozšíření afinního prostoru, homogenní souřadnice, afinní a projektivní transformace v rovině a v prostoru, kvaterniony v reprezentaci 3D orientace, diferenciální geometrie křivek a ploch, základní spline funkce, kubické spliny C2 a jejich vlastnosti, interpolace kubickými spliny, Bézierovy křivky, Catmull-Rom spliny, B-spline, de Casteljaův a de Boorův algoritmus, aproximační plochy, plochy zadané okrajem, Bezierovy plochy, plátování, B-spline plochy, NURBS plochy, základní věty o konvexitě, kombinatorická složitost konvexních mnohostěnů, návrh geometrických algoritmů a jejich složitost, Voroného diagram a Delaunayova triangulace, konvexní obal, lokalizace, datové struktury a algoritmy pro efektivní prostorové vyhledávání.
Projektivní rozšíření afinního prostoru, homogenní souřadnice, afinní a projektivní transformace v rovině a v prostoru
Projektivne rozsireny euklidovsky_prostor.pdf
Afinní prostor:
neprázdná množina bodů
- vektorový prostor (zaměření)
je bijektivní
Běžně .
Ekv. definice: Buď neprázdná mnžožina nazývaná body, buď vektorový prostor nad tělesem reálných čísel a dále mějme zobrazení spl%nující
pro každý bod a libovolný vektor existuje právě jedno , pro které platí
pro každé tři body platí, že
Potom se nazývá affiní prostor.
Soustava souřadnic
Repér: pevný bod + báze zaměření
Transformace souřadnic
Lineárně nezávislé body
jsou LN jsou LN
Afinní prostor dimenze n je jednoznačně určen n+1 body:
::
Afinní kombinace bodů (barycentrické souřadnice)
, Konvexní kombinace bodů - navíc požadavek
Homogenní souřadnice. Pelikán - Algebraická motivace - dokáží reprezentovat body v nekonečnu, průnik dvou přímek má vždy řešení.
Homogení na kartézské - unikátní, kartézské na homogení neunikátní.
Proč? Transformace lze vyjádřit pomocí jedné matice
afinní a projektivní transformace v rovině a v prostoru
Geometric transformation, Pelikán - transformace
Euklidovské transformace:
otáčení - pozor, někde se může změnit znaménka u sinus, kvůli soustavě
posunutí
Afinní transformace: Mohou se měnit délky a úhly (např. kružnice do elipsy).
scale - změna měřítka
shear - kosení ()
obecná afinní transformace - matice s různými koeficienty, poslední řádek [0,0,0,1], obecně apod pro ostatní. Matice může být singulární, ale pak neexistuje inverzní transformace.
Kombinace transformací. Transformace aplikovány na jednotlivé body. Transformace nejsou komutativní.
projektivní zobrazení =
Nejobecnější, vyžaduje homogení souřadnice, transformační matice nemá v posledním řádku [0,0,0,1]. Matice musí být nesingulární (=má inverzní zobrazení). Projekce může dávat vlastní body do nevlastních (=nekonečno) když w'=0. Nejsou lineární (dělení novým w'),
Kvaterniony v reprezentaci 3D orientace
Operace s kvaterniony
- komutativní pokud shodné vektorové části, jinak pouze asociativní a distributivní
:: :: ::
Věta: :: Dk:
Jednotkové kvaterniony
tvoří multiplikativní podgrupu
Jednotkový kvaternion je tvaru:
Rotace
Mějme jednotkový kvaternion , je jednotkový vektor. Potom je rotace kolem osy o úhel proti směru hodinových ručiček.
Pokud není kvaternion jednotkový, lze jednoduše upravit na jednotkový.
Proč je to rotace: Rodrigezova formule dává stejný výsledek jako operace na kvaternionech
Složení dvou rotací je opět rotace:
Interpolace rotace
Lineární Eulerova interpolace
Kvaterniony - LERP
SLERP - sférická lineární interpolace
Diferenciální geometrie křivek a ploch
Šír - diferenciální geometrie křivek, Šír křivky, fjfi, Skripta
Křivky
Parametrizovaná křivka v R^3: interval je hladké zobrazení (=na I má spojité derivace všech řádů)
Vektor se nazývá tečný vektor ke křivce c v bodě t.
Křivka je regulární, pokud její derivace
ParseError: KaTeX parse error: Undefined control sequence: \[ at position 12: c'(t) \neq \̲[̲0,0,0]
.Křivka je parametrizovaná obloukem, pokud
Každou regulární křivku lze parametrizovat obloukem
Délka křivky:
Příklady křivek: přímka, úsečka, kružnice, šroubovice,
Buď křivka parametrizovaná obloukem:
pak křivost definujeme jako .*
bod, kde nazýváme inflexní
Mimo inflexní body definuji Frenetův repér jako tři vektory tečný (), normálový () a binormálový vektor ().
Existuje jediná hladká fce nazývaná torze, tak, že
, ,
Definujeme několik rovin:
oskulační rovina
normálová rovina
rektifikační rovina
Reparametrizace křivky: křivka se nazývá reparametrizací parametrizované křivky .
Nejdříve vyjádříme fci , která pro zadaný parametr t spočítá délku křivky až k bodu t: . K ní uděláme inverzní fci , která pro zadanou délku nám dá parametr, reparametrizovaná křivka parametrizovaná obloukem.
Plochy
Šír - Diferenciální geometrie ploch
Plocha: hladké zobrazení z otevřené množiny R2 do R3.
Parametrická regulární plocha je hladké (jsou derivace všech supňů) regulární (první derivace nikde 0) zobrazení p z otevřené množiny O R2 do R3 takové, že vektory parciálních derivací jsou v každém bodě lineárně nezávislé. Množinu nazveme obrazem mapy. Pokud je p wcs:homeomorfismus, tak se nazývá mapa.
Řekneme, že vektor je tečný vektor k ploše v bodě , pokud existuje křivka , (c leží na S) taková, že .
Je li p mapa na S, tak definuji normálový vektor jako (, jsou parciální derivace)
Základní spline funkce
wen:Spline%20%28mathematics%29, wcs:Spline
Spline křivka stupně je po částech polynomiální křivka, kde každý polynom má stupeň nejvýše . Jméno pocházi od pružného pravítka - křivítka. Požadujeme, aby polynomy sousedících částí měly stejné derivace až do .
Spline je uniformní, pokud jsou všechny intervaly stejně veliké.
wen:Spline%20interpolation
Přirozený spline je spline, který interpoluje své body, např. přirozený kubický spline je křivka, která je složená z polynomiálních oblouků stupně 3, patří do třídy C^2 (v řídících bodech ).
Máme n+1 bodů (0..n), n intervalů, použijeme přirozené kubiky spline. 4*n neznámých (kubka má 4 neznámé, n intervalů). Máme n+1 bodů x,y. Máme celkem 4n - 2 požadavků (každá kubika musí na začátku a na konci protínat bod + první a druhé derivace se musí v bodech rovnat), zbývají dva, které zvolíme jak chceme, např. druhé derivace koncových bodů = 0.
Kubické spliny C2 a jejich vlastnosti, interpolace kubickými spliny
Bézierovy křivky
wen:Bézier%20curve, wcs:Bézierova%20křivka
Křivka zadaná svým kontrolním polynomem, obvykle se používají kvadratiky (2 kontrolní body) nebo kubiky (3 kontrolní body)
, kde Bernsteinovy polynomy . T je 0..1
Široce používané, SVG, fonty.
Výpočet hodnoty buď pomocí rovnice nebo de Casteljau algoritmem.
Kreslení: obvykle adaptivní změna kroku, pokud přiliš malý/velký.
Vlastnosti:
tečny v koncových bodech křivy jsou dané poslenímy body kontrolního polynomu
invariantní vůči lineárním transformacím
křivka uvnitř konvexní obálky kontrolního polynomu (součet všech Bersteinových polynomů = 1)
prochází přesně koncovými body
vliv bodu globální, změna neovlivňuje jenom malé okolí.
hodograf (křivku derivace) lze spočítat jednoduše z bodů
derivace v počátečním a koncovém bodu stejná, jako směr dvou prvních a posledních bodů
Rozdělení na 2 křivky
Subdividing a Bézier Curve. Používají se vnitřní body získané de Casteljau.
Racionální bézier: dáme každému bodu váhu, nemusíme měnit kontrolní polygon pro změnu.
$ \mathbf{B}(t) =
\frac{ \sum_{i=0}^n B_{i,n}(t) \mathbf{P}_{i}w_i
} {
\sum_{i=0}^n B_{i,n}(t) w_i }
$
V normální Bézierovce je všude váha 1 a proto je suma jmenovatele 1.
Catmull-Rom spliny
Kubické spliny zadané posloupností bodů . Křivka neprochází všemi body, vynechává první () a poslední (). Pokud uživatel chce, aby jimi procházela, je potřeba zadat první a poslední dvojnásobně. Používají se pro interpolaci animaci mezi klíčovými snímky.
Vlasnost tečny:
tečna v bodě je rovnoběžná s přimkou .
nejsou v konvexním obalu kontrolních bodů.
Výpočet na každém intervalu je snadný (známe lokace počátečního a koncového bodu a víme derivace [viz podmínka]) -> lze velmi snadno spočítat Catmul-Rom pro interval [P_i, P_{i+1}] pomocí bodů [P_{i-1}, P_{i}, P_{i+1}, P_{i+2}] (dají hodnoty i derivace).
B-spline
Základní fce jsou definovány podle p.
Pro platí
Pro platí .
B spline křivka stupně p je definovaná jako . Máme n+1 bodů, m+1 uzlů a stupeň základních fcí p. Musí platit m = n + p + 1
Křivky nezačínají v počátečních souřadnicích. Pokud chceme, musíme dát počátečnímu/koncovému uzlu násobnost p+1.
Lokální, bod je nenulové pouze na
Uzavřená v konvexním obalu bodů (základní fce dávají dohromady 1)
Lokální modifikace: změna pozice bodu ovlivní pouze úseky
ParseError: KaTeX parse error: Undefined control sequence: \[ at position 1: \̲[̲u_i, u_{i+p+1})
uvnitř segmentů uzlového vektoru hladká, v uzlech je spojitá, kde je násobnost uzlu
béziér je speciálním případem B spline.
invariantní k afinním transformacím
Výhody - narozdíl od Béziera jsme oddělili stupeň křivky od počtu kontrolních bodů. Díky tomu můžeme mít velké množství kontrolních bodů a přesto mít jednoduchý výpočet.
Modifikace uzlu - změní se mapování úseku a fce => změna tvaru. Změna není moc predikovatelná.
De Casteljaův a de Boorův algoritmus
De Casteljaův algoritmus
wen:De%20Casteljau's%20algorithm
Algoritmus pro nalezení bodu na bézierově křivce.
Více numericky stabilní než přímé vyhodnocení Béziera. Založeno na Bernštejnově polynomu:
,
Proč je alg. korektní - spočítá se, jaký je celkový příspěvek každého přes všechny cesty, je to rovné bersteionovu polynomu.
de Boorův algoritmus
wen:De%20Boor's%20algorithm
Chceme, aby v uzlovém vektoru měl hledaný bod násobnost p. Pak bude jen jedna nenulová základí fce () a díky pyramidálnímu výpočtu bude křivka v daném bodě rovna kontrolnímu bodu.
Podíváme se, jakou má hledan= násobnost a podle toho musím vložit do uzlového vektoru.
najdi interval v uzlovém vektoru, kam patří ( - ).
Je potřeba přidat nový bod (aby m=n+p+1 stále platilo i po přidání )
Najdi všechny body, které ovlivňuje (je vidět z pyramidy), jsou to .
Vytvoř nové body Q, ,
Nahraď vnitřní body (= ne body a ) body . Přidej do uzlového vektoru
Aproximační plochy
Aproximační plochy = plochy zadané body. Plochy modelujeme pomocí zadávání sítě řídících bodů v 3D. Obvykle se paroximuje po částech.
Pozor na rozdíl:
interpolační - plocha prochází body
aproximační - ploha používá body k určení svého tvaru
Zajímá nás napojení, bázové funkce jsou polynomy, protože snadno diferencovatelné. Reprezetn
plochy zadané okrajem
wen:Coons%20surface - Bilineární a bikubická Coonsova plocha, Coons patch & Bicubic patch
Coonsova plocha
Coonsova plocha používá křivky, nikoliv body k interpolaci povrchu. Máme zadané křivky okrajů, (levý okraj) (pravý okraj), (dolní okraj) a (horní okraj), stýkají se v rozích a hranice od 0-1.
Horizontální lineární interpolace mezi P nekopíruje hranice Q. Obdobně vertikální lineární interpolace mezi Q nekopíruje hranice P.
Co zkusit lineálně interpolovat obě najednou: ? Problém - na hranicích to přirozeně nefunguje, protože v podstatě interpolujeme 2 body a pak je sečteme. Co se stane na okrajích:
, ale má být
, ale má být
, ale má být
, ale má být
Od odečteme přebytečné členy (ty podtržené). To už hranice následuje.
Výhody
Jednoduché na implementaci
následují okrajové křivky
Nevýhody: nemůžeme kontrolovat vnitřní tvar plochy
Bezierovy plochy
Zobecnění křivek: ;
Výpočet: vnitřní suma je bézierovka-> de casteljau a pak vnější suma, znovu de Casteljau. Případně přímo.
Vlastnosti:
Lineární transformace nezmění plát.
Plocha zahrnuje rohové body (P_{0,0}, P_{n,0}, P_{0,m} a P_{n,m})(dosadut do rovnice)
hranice jsou Bézierovy křivky (dosadit).
Plocha je uvnitř konvexního obalu
Obvykle se používají bikubiky (n=m=3)
plátování
Žára, Moderní Poč. Grafika, str. 160
Převedení Bézierovy plochy (zejména bikubit) na trojúhelníkovou síť.
Algoritmus: Pokud síť dost rovná, skonči. Jinak vezmeme síť, rozdělíme všechny křivky řídících polynomů pomocí de Casteljau na 2 v t=1/2. Pak totéž ve vertikálním směru pro každou polovinu.
Adaptivní - pokud bychom automaticky dělili všechny 4 plochy, není o nic lepší, než spočítat přímo. Plochyu před rozdělením ohodnotíme, zda není dost rovná (např. kvadrát vzdálenosti od roviny 3 okrajů).
Cracking problém - 2 sousedící pláty, 1 se rozdělí, druhý ne. Hranice rozděleného již není přímka (=je to více přímek) a máme prasklinu.
B-spline plochy
Máme uzlový vektor v horizontální u, pro vertikální v.
.
Pozor, stále musí platit, že počet prvků v uzlovém vektoru musí být stupeň křivky v tom směru + počet bodů v tom směru + 1. Taktéž pokud se má dotýkat okrajových bodů, násobnost musí být stupeň + 1 (i.e. nebo )
Vykreslení: dvojitý de Boorův algoritmus, . Není potřeba transformovat všechny body (lokálnost).
NURBS plochy
Invariantní vůči perspektivní projekci, ta je náročná na prostředky, ale u NURBS mi stačí perspektivně transformovat body a pak ji zobrazit.
Umí zobrazovat komplikované plochy, kuželosešky, válec atd. Díky tomu ve všech alg. stačí implementovat NURBS a máme všechno ostatní (např. sledování paprsku - místo X různých objektů se pracuje s jedním typem).
Vzorec .
NURBS používají homogení souřadnice - vložení nového uzlu je přes vynásobení váhovou funkcí, takže máme o dimenzi víc, tam provedeme vložení a vrátíme do 3D. Dtto de Boor.
Základní věty o konvexitě, kombinatorická složitost konvexních mnohostěnů
http://www.fi.muni.cz/%7Ehlineny/Teaching/OU/OU-text07.pdf
Konvexní kombinace dvou vektorů rozumíme každý vektor ve tvaru
Množina je konvexní, pokud pro každé dva prvky jsou i všechny jejich konvexní kombinace prvky X.
Věta: Průnik je konvexní množina.
Dk: Pro každé x,y z průniku platí, že všechny jejich kombinace patří do X i Y, což je definice.
Definice: Nechť je konvexní množina. Bod je krajním bodem , pokud neexistují body takové, že v by bylo konvexní kombinací a .
Věta o oddělující nadrovině: Máme uzavřenou konvexní množinu. Dále máme . Pak existuje nadrovina oddělující od .
Návrh geometrických algoritmů a jejich složitost
Voroného diagram a Delaunayova triangulace
Voronoi diagramy,wen:Voronoi%20diagram
Máme množinu bodů a VD rozděluje rovinu na oblasti, kde každý bod je součátí oblasti nejbližšího bodu. VD je hranice mezi oblastmi (=body, které jsou stejně vzdálené k více bodům).
Vlastnosti:
konvexní
v každé oblasti 1 bod
některé oblasti neuzavřené
pokud žádné 4 body neleží na kružnici, uzly mají stupeň 3
je-li p_i nejbližší soused p_j, tak jejich oblasti sdílí hranu
Konstrukce:
wen:Fortune's%20algorithm - má sweep line, která jde zleva doprava a beachline (sjednocení parabol - parabola = stejná vzdálenost od přímky a bodu). beachline mapuje VD, když SL přijde nový bod tak nová parabola v beachline, pokud se ruší křivka (pokud se tři body, které tvoří tři sousední paraboly na beachline jsou v kruhu, který se dotýká sweep line = bod má stejnou vzdálen ost ke všem třem bodům)
Delaunayova triangulace
Rovinne triangulace a jejich aplikace,wen:Delaunay%20triangulation
Triangulace N bodů množiny P - rozdělení ConvexHull(N) do simplexů (simplex v dimenzi k má k+1 bodů=ve 2D trojúhelník). Počet hran v E2 (euklid2D) max 3N-6, přesně 3N-3-N_convex_hull
Kritéria - lze vybrat mnoho triangulačních sítí, kterou?:
Co nejrovnostranější trojúhelníky - úhlová kritéria: maximalizace min. úhlů, mainimalizace max. úhlů. Hranová kritéria: Co nejkratší součet délek hran.
občas např. chceme zachovat nekonvexnost oblasti (např. písmena)
začlenění některých povinných hran
kružnice opsaná libovolnému trojúhelníku DT(P) v sobě neobsahuje žádné další body z P. Ze všech triangulací má trojúhelníky nejblíže k rovnostranným. Duální k voroniho diagramu
pokud nejsou tři na čáře apod, tak je triangulace unikátní.
Flipping: pokud máme dva trojúhelníky, které sousedí hranou a které nejsou DT (=opsané kružnice obsahují další vrchol nebo úhly > 180), přehození hrany to změní. Začne se s libovolnou triangulací a poté se přehazují hrany, které nejsou DT.
Konvexní obal, lokalizace, datové struktury a algoritmy pro efektivní prostorové vyhledávání
Pozor na degenerované případy, např. více bodů na přímce
2D
Grahamův algoritmus - najdi bod s nejmenším y (pokud víc, nejpravější), seřaď body podle úhlu s bodem p a osou x, potom v pořadí testuj, jestli je to stále konvexní, pokud se otáčí opačným směrem, odstraň předcházející body, dokud není zase konvexní. Nejde zobecnit do vyšších dimenzí. O(N log N)
Balení dárku - vybere se nejlevější bod (zaručeně v obalu). Opakuj: najdi další bod obalu tak, že se podívá na všechny body a vybere ten s nejmenším úhelm od současného úhlu. Složitost (počet_bodu_obalu * N). Pomalý (až N^2), nepoužívá se.
Rozděl a panuj - pokud málo bodů, zkonstruuj obal, jinak rozděl na 2 poloviny, pro každou rekurzivně vlastní obal a výsledné obaly spoj. Pokud spojení O(N), tak O(N log N)
3D
Balení dárku - máme stěnu F a hledáme přes její hranu e polorovinu, která má největší úhel < 180. O(počet_stěn*N)
Rozděl a panuj. Pokud spojení O(N), tak O(N log N)
Lokalizace
Lokalizace - hledání bodu. Geometricke vyhledavani
Konvexní polygon
Ray crossing, vodorovná přímka procházející bodem, pokud lichý počet průsečíků, uvnitř, jinak venku
Test vůči každé hraně - každá hrana definuje polorovinu, pokud ve všech, tak uvnitř
Půlení intervalu
Nekonvexní polygon
Ray crossing
Ovíjení - jdu postupně po všech bodech a sčítám úhly P_i - bod - P_i+1. Pokud je uvitř, tak obejde celý polygon a vysledek je 360, pokud venku, tak se vrátí a výsledek 0.
Hledání v síti
Planární dělení - Každý separátor dělí rovinu na 2 částí=lze použít binární vyledávání. Něco jako BSP
Metoda pásů - vezmemem všechny body a seřadíme do pásů podle x (lze vyhledávat binárně), v každém pásu všechny přimky, seřazené posle y. Hledání O(log N)
datové struktury a algoritmy pro efektivní prostorové vyhledávání
Geometricke vyhledavani 2 Datové struktury pro prostorové vyhledávání
octree
k-D tree
range tree - strom podle x a v každé node strom podle y prvků, které spadají pad danou node
BSP tree
R-tree - v listech obálky, vnitřní uzly obálky podstromů
Materiály
…
{{Stub}} Category:%20Státnice%20Informatika%20Mgr.