Katedra informatiky, Univerzita Palackého v Olomouci. 27. listopadu 2013

Poˇ c´ıtaˇ cov´ a grafika

Poˇc´ıtaˇcová grafika Markéta Krmelová Katedra informatiky, Univerzita Palack´ eho v Olomouci

27. listopadu 2013

Mark´ eta Krmelov´ a



Rekonstrukce 3D tˇeles Reprezentace trojrozmˇerných dat. Hledán´ı povrchu tˇelesa v tˇechto datech. Pˇredstaven´ı nˇekolika algoritm˚ u.




Reprezentace a modelován´ı tˇeles tˇeleso = mnoˇzina bod˚ u v trojrozmˇerném prostoru tˇeleso = sjednocen´ı dvou disjunktn´ıch mnoˇzin - vnitˇrn´ı body a hraniˇcn´ı body tˇeleso je spojitý u ´tvar, tvoˇrený jedn´ım celkem tato definice tˇelesa vyluˇcuje pˇr´ımky, kˇrivky v prostoru...




Trjúheln´ıky a s´ıtˇe trojúheln´ık˚ u troj´ uheln´ık - je vˇzdy konvexn´ı, vˇsechny vrcholy leˇz´ı v rovinˇe, rychlé algoritmy na jejich vyplˇ nován´ı, zobrazován´ı podporováno grafickým procesorem s´ıt’ troj´ uheln´ık˚ u (triangle mesh) = troj´ uheln´ıky, které spolu sd´ılej´ı hrany popis s´ıtˇe 2 logické ˇcásti: geometrická - souˇradnice vrchol˚ u topologická - u ´daje o tom, které vrcholy tvoˇr´ı troj´ uheln´ık




u S´ıt’ trojúheln´ık˚ rozdˇelen´ı na topologickou a geometrickou ˇcást - praktické pro operace se s´ıt´ı napˇr. pˇri geometrických transformac´ıch se poze pˇrepoˇc´ıtávaj´ı souˇradnice vrchol˚ u kriteria pro tvorbu troj´ uheln´ıkových s´ıt´ı Pˇresné a u ´sporné vyjádˇren´ı tvaru, který s´ıt’ vyjadˇruje uspoˇrádán´ı vhodné pro dalˇs´ı zpracován´ı




u S´ıt’ trojúheln´ık˚ troj´ uheln´ıková s´ıt’ nen´ı vhodná pro modelován´ı tvaru je tˇreba optimalizovat tak, aby pro co nejmenˇs´ı poˇcet troj´ uheln´ık˚ u byl vymodelován co nejpˇresnˇejˇs´ı tvar

Obrázek : Vlevo pravidelná troj´ uheln´ıková s´ıt’, vpravo jemnˇejˇs´ı v m´ıstech s vˇetˇs´ı kˇrivost´ı Mark´ eta Krmelov´ a



u S´ıt’ trojúheln´ık˚ pro nˇekteré u ´lohy je nevhodné rozdˇelen´ı do dvou struktur (geometrická a topologická) napˇr. zpracován´ı grafickým procesorem chceme, aby bylo co nejménˇe operac´ı s vrcholy - vhodný výber troj˚ uheln´ıkové s´ıtˇe pruh troj´ uheln´ık˚ u vˇej´ıˇr troj´ uheln´ık˚ u




Hraniˇcn´ı reprezentace tˇeles popis hranice (boundary representation) - tj. popis hraniˇcn´ıch bod˚ u informace o vnitˇrn´ıch bodech tˇelesa se neuchovávaj´ı (lze je odvodit z popisu hranice) tato reprezentace je pˇrirozená




Konstruktivn´ı geometrie tˇeles tˇeleso reprezentováno stromovou strukturou (CSG) uchovávaj´ıc´ı historii d´ılˇc´ıch konstrukˇcn´ıch krok˚ u CSG primitiva - jednoduché geometrické objekty (kvádr, koule, válec, kuˇzel, toroid, jehlan,...) výsledný objekt je sloˇzen z CSG primitiv a a prostorových transformac´ı

Obrázek : Popis tˇelesa CSG stromem Mark´ eta Krmelov´ a



Objemová reprezentace tˇeles nemáme k dispozici geometrický popis tˇelesa sada vzork˚ u v urˇcitém m´ıstˇe povrchu, nebo objemu rozprýlená data - kromˇe hodnotˇe o jasu, má i souˇradnice pravidelné mˇr´ıˇzky




Mˇr´ıˇzky d˚ uleˇzitý je tvar mˇr´ıˇzky

Obrázek : Zleva - kartézská, pravidelná, pravo´ uhlá, strukturovaná, nestrukturovaná, blokovˇe strukturovaná, hybridn´ı Mark´ eta Krmelov´ a



Trojrozmˇerné objekty a data v diskrétn´ı mˇz´ıˇzce problém - velké mnoˇzstv´ı dat m´ısto spojité informace pouze diskrétn´ı - sloˇzité natáˇcen´ı o u ´hly jiné neˇz pravé, zvˇetˇsován´ı a pod. výhody - snadná práce s namˇeˇrenými daty, snadné zpracován´ı objemu dat jako celku (nezávislé na poˇctu objekt˚ u ve scénˇe)




Voxel voxel = analogie dvourozmˇerného pixelu nejmenˇs´ı element ve trojrozmˇerném diskrétn´ım prostoru kvádr, nebo krychle v pravo´ uhlé mˇr´ıˇzce




Skalárn´ı objemové algoritmy dˇel´ıme na: algoritmy zobrazuj´ıc´ı povrchy (surface rendering) pˇr´ımé objemové algoritmy (volume rendering)




Surface rendering (surface-fitting rendering) vytváˇr´ı geometrickou reprezentaci povrchu (nejˇcastˇeji s´ıt´ı troj´ uheln´ık˚ u) následnˇe zobrazuj´ı výhody : sn´ıˇzen´ı mnoˇzstv´ı dat




Volume rendering (direct volume rendering) zobrazen´ı dat bez pˇreveden´ı do povrchové reprezentace nen´ı potˇreba znát, zda prvek (voxel) patˇr´ı do zobrazovaného tˇelesa, nebo ne zobrazuj´ı jak vnitˇrek tˇelesa, tak rozhran´ı mezi materiály




Algoritmy zobrazuj´ıc´ı povrchy propojován´ı kontur (opláˇstˇen´ı kontur) povrchové kostky (opaque cubes) pochoduj´ıc´ı kostky dˇelené kostky




Algoritmy zobrazuj´ıc´ı objem Jednou z nejznámˇejˇs´ıch metod je tzv. Ray casting neboli metoda vrhán´ı paprsku. Zobrazován´ı dat touto metodou lze dále ˇclenit na: metody pracuj´ıc´ı s daty bez hledán´ı povrchu, metody hledaj´ıc´ı povrch, které nezjiˇst’uj´ı normály, metody hledaj´ıc´ı povrch a jeho normály.




Algoritmy zobrazuj´ıc´ı objem Budeme brát v u ´vahu data v trojrozmˇerné mˇr´ıˇzce. P´ısmenem Ii si oznaˇc´ıme hodnotu intenzity i-tého vzorku podél paprsku. P´ısmenem J oznaˇc´ıme mnoˇzinu zapoˇc´ıtaných vzork˚ u (vzork˚ u zasaˇzených paprskem, pˇr´ıpadnˇe vyhovuj´ı nˇejakému dalˇs´ımu kritériu) viz. 4

Obrázek : Oznaˇcen´ı. Mark´ eta Krmelov´ a



Metody nehledaj´ıc´ı povrch Tyto metody t´ım, ˇze nehledaj´ı povrch a nevyˇzaduj´ı ˇzádné pˇredzpracován´ı, jsou rychlé a proto se hod´ı zejména pro vytváˇren´ı náhledu. Patˇr´ı sem metody: Maximum intensity projection Summed intensity projection Average intensity projection




Maximum intensity projection Tato metoda zobrazuje pouze nejjasnˇejˇs´ı struktury podél paprsku. Pro kaˇzdý bod se vypoˇc´ıtává hodnota I pomoc´ı vzorce: I = maxi∈J Ii .

Obrázek : Výstup z programu Volume - maximum intensity projection. Mark´ eta Krmelov´ a



Summed intensity projection Tato metoda poˇc´ıtá∑ jas jako souˇcet jas˚ u podél paprsku pomoc´ı vzorce: I = i∈J Ii

Obrázek : Výstup z programu Volume - summed intensity projection.




Average intensity projection ∑

jas pr˚ umˇeruje dle vzorce: I =

i∈J Ii

|J|

Obrázek : Výstup z programu Volume - average intensity projection.




Metody s jednoduchým zobrazen´ım povrchu Tyto metody vyˇzaduj´ı znalost hraniˇcn´ı hustoty tˇelesa, které chceme zobrazit. Prvn´ımu pixelu na dráze paprsku, který patˇr´ı do tˇelesa, pˇriˇrad´ıme hodnotu jasu podle hloubky (vzdálenosti od plochy procházej´ıc´ı okrajem sn´ımk˚ u). Takto zobrazený povrch ale nevypadá pˇr´ıliˇs objemovˇe. Potlaˇcuje ˇsum vzorkován´ı a s n´ım i hrany a nespojitosti. Jeˇstˇe jednoduˇsˇs´ı metodou je zobrazit prvn´ı pixel na dráze paprsku s jeho hodnotou. Tato metoda nezobrazuje tvar, ale pouze barvu povrchu objektu.




Metody s jednoduchým zobrazen´ım povrchu

Obrázek : Výstup z programu Volume - zobrazn´ı povrchu bez výpoˇctu normál.




Obrázek : Výstup z programu Volume - zobrazn´ı povrchu bez výpoˇctu normál II.




Metody zobrazuj´ıc´ı povrch s normálou Tˇemito metodami z´ıskáme kvalitnˇejˇs´ı zobrazen´ı objektu, d´ıky tomu, ˇze se snaˇz´ıme odhadnout orientaci povrchu v m´ıstˇe dopadu paprsku. Zm´ın´ıme tˇri nejznámˇejˇs´ı metody pro odhad normál. Patˇr´ı sem metody: Z-buffer gradient shadding Voxel gradient shading Gray-level gradient shading




Z-buffer gradient shadding Normálu aproximuje vektorem, jehoˇz kolmým pr˚ umˇetem do plochy obrazovky je vektor gradientu v pamˇeti hloubky. Sloˇzky normály vypoˇc´ıtáme: n0 = Z (px + 1, py ) − Z (px − 1, py ), n1 = Z (px , py + 1) − Z (px , py − 1), n2 = 1, kde [px , py ] jsou souˇradnice pixelu, pro který poˇc´ıtáme normálu. Na konci je potˇreba takto vypoˇc´ıtaný vektor normovat. Tato metoda zachycuje tvar tˇelesa, ale na zaoblených povrˇs´ıch jsou vidˇet vrstevnice.




Z-buffer gradient shadding




Voxel gradient shading odhaduje oproti pˇredeˇslé metodˇe normálu podle gradientu v binárn´ım objemu vzork˚ u. Sloˇzky gradientu nabývaj´ı hodnot {−1, 0, 1} a sloˇzky výsledné normály nabývaj´ı jednu z 27 hodnot. Sloˇzky gradientu spoˇc´ıtáme dle následuj´ıc´ıch vzorc˚ u: n0 = b(px + 1, py , pz ) − b(px − 1, py , pz ), n1 = b(px , py + 1, pz ) − b(px , py − 1, pz ), n2 = b(px , py , pz + 1) − b(px , py , pz − 1), kde [px , py , pz ] jsou souˇradnice pixelu a hodnota b(px , py , pz ) nabývaj´ıc´ı 1 nebo 0 pˇredstavuje funkci pˇr´ısluˇsnosti pixelu k povrchu. Stejnˇe jako v pˇredeˇslé metodˇe se i zde objevuj´ı vrstevnice.




Voxel gradient shading

eta Krmelov´ a Volume Poˇ c´ıtaˇ cov´ a grafika gradient shading. Obrázek : Výstup Mark´ z programu Voxel


Gray-level gradient shading pˇredpokládá, ˇze na povrchu docház´ı k nejvˇetˇs´ı zmˇenˇe hodnot vzork˚ u, tj. opˇet poˇc´ıtáme s t´ım, ˇze normála bude ve smˇeru gradientu, ale budeme zde narozd´ıl od pˇredchoz´ı metody poˇc´ıtat s p˚ uvodn´ımi hodnotami. Sloˇzky normály tedy vypoˇc´ıtáme: n0 = f (px + 1, py , pz ) − f (px − 1, py , pz ), n1 = f (px , py + 1, pz ) − f (px , py − 1, pz ), n2 = f (px , py , pz + 1) − f (px , py , pz − 1).




Gray-level gradient shading

eta Krmelov´ a Poˇ c´ıtaˇ ov´ a grafika Obrázek : Výstup z Mark´ programu Volume - cGray-level gradient shading.


Surface rendering (surface-fitting rendering) hledáme povrch reprezentuj´ıc´ı konstantn´ı hodnotu vzork˚ u vytváˇr´ı geometrickou reprezentaci povrchu (nejˇcastˇeji s´ıt´ı troj´ uheln´ık˚ u) následnˇe zobrazuj´ı výhody : sn´ıˇzen´ı mnoˇzstv´ı dat




Rekonstrukce povrchu opláˇstˇen´ım kontur hledán´ı hranic tˇelesa v jednotlivých vzorc´ıch (kontura) pˇriˇrazen´ı kontur opláˇstˇen´ı




Obrázek : Vstupn´ı objekt.




Obrázek : Sada ˇrez˚ u.




a)

b)

c)

d)

e)

Obrázek : Ukázka odhadu skuteˇcného povrchu pokud nemáme dalˇs´ı informaci o tvaru tˇelesa mezi ˇrezy.




Kontura kontura = orientovaný jednoduchý uzavˇrený polygon ci = p 1 , p 2 , . . . , p n kontury se v rámci ˇrezu neprot´ınaj´ı 2 druhy kontur - vnˇejˇs´ı kontura, d´ıra hledán´ı kontur napˇr´ıklad metodou Marching Squares

Obrázek : Kontura a kontura s d´ırou. Mark´ eta Krmelov´ a



Rekonstrukce povrchu opláˇstˇen´ım kontur máme kontury a hledáme odhad p˚ uvodn´ıho tvaru povrchu ve formˇe troj´ uheln´ıkové s´ıtˇe chyb´ı nám data mezi jednotlivými vzorky - hrubý odhad kl´ıˇcový problém - vzájemné pˇriˇrazen´ı kontur je potˇreba dalˇs´ı znalost o struktuˇre vzorkovaného objektu (jiný postup u kulovitých u ´tvar˚ u a pˇri rekonstrukci objektu stromové struktury)




Heuristiky pro pˇriˇrazen´ı kontur Plocha pˇrekryt´ı kontur = velikost kolmé projekce sousedn´ıch kontur

Obrázek : Kritérium pˇrekryt´ı kontur.




Heuristiky pro pˇriˇrazen´ı kontur Zobecnˇené válce = kontury maj´ı tvar kruhu nebo elipsy stˇredy lez´ı pˇribliˇznˇe na jedné pˇr´ımce

Obrázek : Zobecnˇené válce.




Heuristiky pro pˇriˇrazen´ı kontur Strom minimáln´ıho pokryt´ı v grafu kontur - sestavuje se graf, jednotlivé kontury jsou uzly a hrany tvoˇr´ı propojen´ı kontur. Hrany se ohodnocuj´ı podle vzdálenosti. Hledáme zde strom minimáln´ıho pokryt´ı.

Obrázek : Správné a chybné propojen´ı kontur.




Propojen´ı kontur propojen´ı jednotlivých kontur s´ıt´ı troj´ uheln´ık˚ u problém vˇetven´ı a spojován´ı kontur r˚ uzné metody si r˚ uznˇe porad´ı s vˇetven´ım heuristiky, které nezkoumaj´ı celý obvod kontury, ale pouze definuj´ı kritéria, která mus´ı splˇ novat novˇe pˇridaný troj´ uheln´ık lokáln´ı a globáln´ı metriky




Propojen´ı kontur Minimáln´ı povrch - objem troj´ uheln´ıku - nehod´ı se pokud jsou kontury posunuty

Obrázek : Chybné spojen´ı kontur.




Propojen´ı kontur Smˇer pˇriˇrazen´ı - preferuje spojnice, které se moc neliˇs´ı od spojnice tˇeˇziˇst’ Maximáln´ı objem - objem kl´ınu, který tvoˇr´ı troj´ uheln´ıková záplata a spojnice tˇeˇziˇst’ kontur

Obrázek : Maximáln´ı objem.




Závˇer vhodné pro aproximaci dat s vˇetˇs´ıme rozestupy mezi vzorky mnoho r˚ uzných pˇr´ıstup˚ u k propojen´ı kontur, je potˇreba znát dodateˇcné informace




Pochoduj´ıc´ı kostky (Marching Cubes) publikována 1987 W. Lorensenen and H. Clinem v knize Computer Grapgics Vstup: objemová data v pravidelné mˇr´ıˇzce a konstanta prahu Výstup - mnoˇzstv´ı troj˚ uheln´ık˚ u aproximuj´ıc´ı povrch data chápe jako krychle a ty postupnˇe procház´ı a poˇc´ıtá jednotlivé troj´ uheln´ıky pro danou krychli velké mnoˇzstv´ı troj´ uheln´ık˚ u - pro kaˇzdou krychli mohou vzniknout aˇz 4 troj´ uheln´ıky nezohledˇ nuje globáln´ı pohled




Marching Squeres Pracuje stejnˇe jako Marching Cubes, ale v 2D hledá hranici dat dvourozmˇernou mˇr´ıˇzku s indexy i a j Mˇr´ıˇzka je o rozmˇeru m × n (hodnoty i = 0, ..., m − 1 a j = 0, ..., n − 1) fij = f (x0 + ih, y0 + jh) hodnoty funkce v jednotlivých bodech mˇr´ıˇzky f0 hodnota, pro kterou hledáme kˇrivku.




Algoritmus Marching Squeres Kaˇzdému bodu mˇr´ıˇzky pˇriˇrad´ıme hodnotu fij = f (x0 + ih, y0 + jh) Pro kaˇzdý ˇctverec: vypoˇc´ıtáme index ˇctverce Interpolujeme vrcholy na aktivn´ıch hranách Pro kaˇzdou hranu: vykresl´ıme hranu




Algoritmus Marching Squeres Zjist´ıme zda je vrchol uvnitˇr tˇelesa, nebo vnˇe Pokud pro sousedn´ı vrcholy plat´ı, ˇze jeden je vnˇe a jeden uvnitˇr - kˇrivka procház´ı mˇezi nimi

D´ıky n´ım m˚ uˇzeme kaˇzdému ˇctverci jednoznaˇcnˇe pˇriˇradit index




Algoritmus Marching Squeres Index ˇctverce - index = 20 A + 21 B + 22 C + 23 D A, B, C , D jsou hodnoty 0 nebo 1, podle toho, zda body A, B, C , D jsou vnitˇrn´ımi nebo vnˇejˇs´ımi body index nabývá hodnot 0 . . . 15




Algoritmus Marching Squeres Máme index ˇctverce, do pomocné tabulky se pod´ıváme, na kterých hranách leˇz´ı vrcholy u ´seˇcek (aproximuj´ıc´ı hranici) interpolujeme tyto vrcholy (moˇzné pouˇz´ıt stˇred hrany, ale lepˇs´ı lineárn´ı interpolace)




Algoritmus Marching Squeres D=2

x3

4

A=3

C=6 y2

1

B=3

f0 = 4 index = 20 A + 21 B + 22 C + 23 D, dostaneme index = 0 + 0 + 4 + 0 = 4 krajn´ı body u ´seˇcky leˇz´ı na hranách 2 a 3 a hodnota ve výchoz´ım bodˇe a b v koncovém I (u) = mu + n, I (a) = 0, I (b) = h h je délka hrany ˇctverce Mark´ eta Krmelov´ a



Algoritmus Marching Squeres 0 −a I (u) = fb−a . V naˇsem pˇr´ıpadˇe tedy:

x=

f0 − f (D) 4−2 h h= h= , f (C ) − f (D) 6−2 2

y=

4−3 h f0 − f (B) h= h= . f (C ) − f (B) 6−3 3




Algoritmus Marching Squeres - Závˇer vznikaj´ı nejednoznaˇcnosti

nen´ı moˇzné rozhodnout zda pouˇz´ıt sp´ıˇse u ´seˇcky v prvn´ım ˇrádku, nebo ve druhém. V rámci algoritmu jde o vˇec konvence - pokud prvn´ı a druhý ˇrádek nekombinujeme bude výsledná kˇrivka vˇsude plynule navazovat prvn´ıho ˇrádek - kˇrivka tvoˇr´ı nesouvislé struktury, druhý ˇrádek souvislejˇs´ı celky.




Algoritmus Marching cubes Kaˇzdému bodu mˇr´ıˇzky pˇriˇrad´ıme hodnotu fijk = f (x0 + ih, y0 + jh, z0 + kh) Pro kaˇzdou krychli: vypoˇc´ıtáme index krychle Interpolujeme vrcholy na aktivn´ıch hranách Pro kaˇzdý troj´ uheln´ık: vykresl´ıme troj´ uheln´ık




Algoritmus 4

4

5

7

5 6

7

6

9

8 10 11

0

1

0

3 3

1 2

2

Obrázek : Oznaˇcen´ı hran a vrchol˚ u krychle




Algoritmus

Obrázek : Vˇsechny moˇzné kombinace um´ıstˇen´ı troj´ uheln´ık˚ u v krychli




Nejednoznaˇcnosti algoritmu vede ke d´ırám jak je vidˇet na obr.

Vyˇreˇsen´ım této nejednoznaˇcnosti se vyhneme d´ırám, ale nezaruˇc´ı nám to správnou topologii viz.




Pochoduj´ıc´ı ˇctyˇrstˇeny - Marching Tetrahedra Tato metoda byla poprvé uvedena B.A. Paynem a A.W. Togou v knize Surface Mapping Brain Function on 3D Models pokusem o odstranˇen´ı nejednoznaˇcnost´ı v metodˇe Marching Cubes krychle se rozdˇel´ı na 5 ˇctyˇrstˇen˚ u a troj´ uheln´ıky se um´ıst’uj´ı do nich




Pochoduj´ıc´ı ˇctyˇrstˇeny - Marching Tetrahedra Problém dˇer byl v tomto algoritmu zcela vyˇreˇsen, ale na u ´kor nárustu poˇctu troj´ uheln´ık˚ u a nutnosti stˇr´ıdán´ı zp˚ usobu dˇelen´ı krychle (To je nutné pro zachován´ı spojitosti povrchu).

Zlepˇsen´ı návaznosti lze vylepˇsit dˇelen´ım na 6 ˇci 24 ˇctyˇrstˇen˚ u tento algoritmus nen´ı v praxi pˇr´ıliˇs pouˇz´ıván




Marching cubes 33 zaruˇcuje topologii a ˇreˇs´ı nejednoznaˇcnosti t´ım, ˇze: má rozˇs´ıˇrenou look-up tabulku provád´ı dodateˇcné zkoumán´ı krychle




Rozˇs´ıˇrená look-up tabulka




Algoritmus Marching cubes 33 look-up tabulka tabulka pˇr´ıpad˚ u oznaˇcen´ı stˇen (faces)

Obrázek : oznaˇcen´ı stˇen (faces)




Tabulka pˇr´ıpad˚ u




ˇ sen´ı nejednoznaˇcnost´ı Reˇ ˇ sen´ı face nejednoznaˇcnost´ı Reˇ dva protilehlé vrcholy A a C jedné stˇeny jsou pozitivn´ı (leˇz´ı v tˇelese) a dalˇs´ı dva B a D jsou negativn´ı Testujeme, zda jsou vrcholy A a C propojeny uvnitˇr stˇeny, nebo ne sign(facelabel ∗ F (A) ∗ (F (A) ∗ F (C ) − F (B) ∗ F (D)))




ˇ sen´ı nejednoznaˇcnost´ı Reˇ ˇ sen´ı vnitˇrn´ıch nejednoznaˇcnost´ı Reˇ dva diagonálnˇe protilehlé vrcholy krychle mohou být propojené skrz krychli pokud je zde ˇretˇezec pozitivn´ıch vrchol˚ u spojuj´ıc´ı tyto vrcholy pˇrez hrany, nebo v pˇr´ıpadˇe pˇrez face (nen´ı vnitˇrn´ı nejednoznaˇcnost) pokud existuje rovina P, kde jsou oba protilehlé vrcholy (At a Ct ) pozitivn´ı ⇒ ˇreˇs´ıme jako face nejednoznaˇcnost




Závˇer ˇreˇs´ı nejednoznaˇcnosti metody Marching Cubes

generuje v´ıce troj´ uheln´ık˚ u m˚ uˇze vzniknout aˇz 12 troj´ uheln´ık˚ u, coˇz je 3x v´ıce neˇz je tomu v jednoduché metodˇe Marching Cubes




Dividing Cubes - Dˇelené kostky v roce 1988 v publikaci Two Algorithms for the Three-Dimensional Reconstruction of Tomograms H.E. Cline, W.E Lorensen, S.Ludke, C.R. Crawford a B.C. Teeter ˇreˇs´ı pˇreváˇznˇe problém pomalého vykreslován´ı tˇelesa, který vzniká pˇri rasterizaci obrovského mnoˇzstv´ı malých ploˇsek vykresl´ı pouze povrchové body s normálou nevýhodou této metody je ztráta informace o tom, ke které ploˇse bod náleˇz´ı nemoˇznost pˇribl´ıˇzen´ı tˇelesa




Dividing Cubes - Algoritmus Naˇcteme objemová data a prahovou konstantu, pro kterou hledáme povrch. Do pamˇeti naˇcteme ˇctyˇri soused´ıc´ı ˇrezy. Vytvoˇr´ıme krychli, kterou definujeme 8 body dvou soused´ıc´ıch ˇrez˚ u. Ve vˇsech osmi vrcholech vypoˇc´ıtáme vektor gradientu jednotlivé sloˇzky vypoˇc´ıtáme jako rozd´ıl mezi pˇredchoz´ım a následuj´ıc´ım sousedem ve smˇeru kaˇzdé osy. Ohodnot´ıme kaˇzdou krychli. Krychle je: Vnitˇrn´ı - pokud intenzita vˇsech vrchol˚ u je menˇs´ı neˇz prahová konstanta Vnˇejˇs´ı - pokud intenzita vˇsech vrchol˚ u je vˇetˇs´ı neˇz prahová konstanta jinak prot´ınaj´ı povrch hledaného obrazu Mark´ eta Krmelov´ a



Dividing Cubes - Algoritmus Rozdˇel´ıme vˇsechny krychle na a × b × c subkrychl´ı, které jsou velké jako zobrazované body. Denzitu kaˇzdého vrcholu vypoˇc´ıtáme lineárn´ı interpolac´ı. Procház´ıme jednotlivé subkrychle a hledáme ty, které leˇz´ı na hranici tˇelesa (nˇekteré vrcholy leˇz´ı uvnitˇr a nˇekteré vnˇe). Interpolujeme vektor gradientu tˇechto krychl´ı. Vypoˇc´ıtáme intenzitu svˇetla kaˇzdého povrchového bodu, projekc´ı normálového vektoru podél smˇeru pohledu .



Katedra informatiky, Univerzita Palackého v Olomouci. 27. listopadu 2013

Recommend Documents