Vizualizace

Závěrečná zpráva

29. 12. 2002


Téma: Průsečík paprsku s děravou NURBS plochou

Řešitel: Pavel Halabala

Konzultant: Jaroslav Křivánek

1 Zadání

Podle dodaného kódu naimplementujte do raytraceru GOLEM metody pro výpočet průsečíku paprsku a děravé (trimmed) NURBS plochy.
Pro úspěšnou realizaci zadání je nutné

není nutné Odkazy:

1.1 Podrobnosti zadání

Úkolem bylo implementovat metodu sledování paprsku děravých nurbs ploch do školního raytraceru GOLEM. Vstupním formátem byl VRML, bylo tedy nejprve nutné rozšířit VRML parser o nový objekt - obecnou nurbs plochu - dle standardu VRML. Hlavním bodem mé práce měl být přenos dodaného kódu do GOLEMu a jeho odladění. K dispozici jsem měl rovněž dokumentaci výpočetních metod použitých v kódu. Pro test funkčnosti programu jsem měl vytvořit několik scén s obecnou nurbs plochou (plochami), které budou demonstrovat různé základní vlastnosti materiálu jako je zrdcadlový odraz, lom, atd.

2 Teorie

Tento oddíl popisuje algoritmy používané při sledování paprsku u NURBS ploch.

2.1 Obecný postup při raytracingu NURBS ploch


Popis obr. 1: Základní metoda užívaná pro nalezení průsečíku paprsku s parametrickým objektem ukázaná na 2D příkladě. Vlevo: paprsek je testován na průsečík s množinou osově zarovnaných ohraničujících oblastí. Vpravo: Pro každý zásah ohraničující oblasti se generuje počáteční odhad v parametrickém intervalu, který tato oblast ohraničuje. Hledání průsečíku se počítá iterativně, dokud není splněno divergentní či konvergentní kritérium.

2.2 Konkrétní implementace raytracingu NURBS ploch (dle dodané dokumentace)


Obr. 2: Implementace raytraceru podle dodané documentace

2.3 Hledání průsečíku

Jde v podstatě o řešení dvou rovnic o dvou neznámých (u,v). Byla použita zmíněná Newtonova metoda, která iterativně počítá nový odhad místa průsečíku z předchozího odhadu. Zahrnuje 4 základní kritéria pro zastavení iterace:
  1. Kritérium úspěchu: odchylka od správného řešení je menší než námi definované epsilon
  2. Kritérium selhání: odchylka následnující iterace je větší než odchylka iterace předchozí, tedy nedovolíme, aby se řešení "vzdalovalo"
  3. Kritérium selhání: parametr u nebo parametr v vyběhne ze svého definičního oboru
  4. Kritérium selhání: počet iterací překročí maximální dovolenou mez



Obr 4: Hledání průsečíku

2.4 Ořezávací křivky (Trimming curves)

2.5 Tvorba hierarchie ořezávacích křivek

Protože se ořezávací křivky mohou do sebe vnořovat, je pro určení výsledných ořezaných a neořezaných částí plochy nutné si zapamatovat jejich topologii. K tomu se používá hierarchie ořezávacích křivek. Je dána množina ořezávacích křivek na obecné B-spline ploše. Vzhledem k tomu, že se křivky nesmí křížit, existují pouze 3 možné vztahy meze dvěma křivkami c1 a c2. c1 může obsahovat c2, být obsažena v c2 nebo nesdílet s c2 žádnou oblast. Každý uzel v naší hierarchii je seznam ořezávacích křivek a každá křivka může odkazovat na další seznam do ní spadajících křivek.

Obr. 5: Množina ořezávacích křivek a výsledná hierarchie.

Dále pro každou křivku a pro každý seznam křivek uložíme ohraničující oblast, kterou použijeme pro urychlení výběru potenciálně vhodných paprsků (procházejících touto oblastí).

2.6 Ray Tracing děravých NURBS

Nejdříve nalezneme průsečík paprsku s neořezanou NURBS plochou. Pokud byl nalezen průsečík (u,v), podíváme se do hierarchie ořezávacích křivek, abychom zjistili zda má být bod ořezán nebo zda má být vrácen zásah.


Obr. 5: Raytracing děravých NURBS ploch

3 Implementace

3.1 Rozšíření VRML parseru

Parser byl rozšířen o obecnou NURBS plochu dle standardu VRML následovně:

NurbsSurface { 
       field        SFInt32  uDimension        0     # [0,)  
       field        SFInt32  vDimension        0     # [0,)
       field        MFFloat  uKnot             []    # (-,) 
       field        MFFloat  vKnot             []    # (-,)
       field        SFInt32  uOrder            3     # [2,)  
       field        SFInt32  vOrder            3     # [2,)
       exposedField MFVec3f  controlPoint      []    # (-,)
       exposedField MFFloat  weight            []    # (0,)
       exposedField SFInt32  uTessellation     0     # (-,)  
       exposedField SFInt32  vTessellation     0     # (-,)  
       exposedField SFNode   texCoord          []
       field        SFBool   ccw               TRUE
       field        SFBool   solid             TRUE
     }
Pole, která GOLEM ignoruje jsou: Ostatní pole se ukládají do pamětí a jsou interpretována dle standartu VRML (+vypořádání se s vynechanými nebo špatně zadanými hodnotami - viz dále). Pro každou logicky rozdílnou část popisu NURBS plochy existuje samostatná třída. Byly tedy vytvořeny následující třídy: Rozšíření parseru proběhlo celkem bez problémů. Parser se umí vypořádat i s drobnými chybami v popisu NURBS plochy jako jsou vynechání nebo chybný zápis uzlového vektoru. V případě vynechání některého uzlového vektoru se automaticky vytvoří vektor s uniformním dělením uzlů. Zpřeházené hodnoty uzlů se vzestupně setřídí a nakonec se vektor znormuje do intervalu <0,1>. Chybějící hodnoty vah se nahradí jedničkami.

3.2 Analýza a přenos dodaného kódu do GOLEMu

Jak již bylo uvedeno, měl jsem k dispozici kód pro výpočet průsečíku paprsku s nurbs plochou, který bylo nutno nejprve přenést do GOLEMu a posléze odladit. Kód bohužel neobsahoval úplnou implementaci raytraceru. Úplně chyběl výpočet hierarchie ořezávacích oblastí popsanou metodou zjemňování plochy. Tato hierarchie je nezbytně nutná pro stanovení počátečního odhadu parametrů (u,v) možného průsečíku. Bez její aplikace je Newtonova metoda prakticky nepoužitelná. Při náhodné volbě počátečního odhadu dochází ke dvěma problémům: Jelikož by dodatečné zabudování hierarchie ořezávacích oblastí do programu bylo časově velmi náročné ( hlavně díky tomu, že nevím na jaké problémy bych mohl ještě narazit), vepsal jsem na patřičná místa v kódu podrobné komentáře, jaký algoritmus či strukturu by bylo vhodné použít pro vyřešení tohoto problému. Podle dodané dokumentace jsem také napsal metodu, která obsahuje heuristiku určující jemnost dělení plochy podle jejího zakřivení v daném místě. Jediné co je třeba dopsat a vymyslet, je algoritmus, který rozdělí nurbs plochu na části a z těchto částí vypočítá osově zarovnané kvádry. Pro dovedení programu do fungujícího stavu jsem použil jediný osově zarovnaný kvádr, který ohraničuje celou nurbs plochu. Počáteční odhad se obecně bere vždy v polovině intervalu parametrů, které vymezuje daný kvádr, a protože v mém případě existuje jen jeden, počáteční odhad bude vždy v polovině nurbs plochy. I tímto způsobem se dá dosáhnout rozumných výsledků, ale pouze v případě použití konvexních objektů, u kterých Newtonova metoda konverguje téměř vždy. Realizovaná implementace raytraceru vypadá tedy následovně:

Obr. 3: Realizovaná implementace raytraceru

3.3 Hierarchie ohraničujících oblastí

Dodaný kód neobsahoval implementaci hierarchie ohraničujících oblastí, proto zde alespoň popíšu možný postup. Tento postup jsem rovněž popsal formou komentářů na patřičných místech v kódu.

3.4 Ořezávací křivky (Trimming curves)

V GOLEMu jsou implementovány rovněž děravé NURBS plochy, ale kód byl přenesen tak jak je a není tudíž záruka, že bude správně fungovat!!! Zbývá doplnit parser o definici ořezávacích křivek a vše odladit. Třída CNurbsSurface obsahuje 2 konstruktory: jeden pro děravou a druhý pro neděravou nurbs plochu. Metoda pro výpočet průsečíku je implementována i pro děravou plochu, ale pro děravé plochy nebyla testována!!!

Třídy pro ořezávací křivky jsou následující:

Algoritmus, který testuje zda se bod nachází uvnitř nebo vně ořezávací křivky pracuje nyní s lineární složitostí vzhledem k počtu bodů, kterými je křivka definována. GOLEM obsahuje podobný algoritmus s logaritmickou složitostí, který lze v budoucnosti implementovat i zde.


3.5 Ostatní problémy během implementace

Při přenášení kódu a ladění jsem narazil na spoustu problémů, které byly většinou způsobeny nepochopením rozsáhlého matematického aparátu použitých metod. Bylo pro mě opravdu obtížné odhalit některé chyby nejen v mém kódu, ale i v tom originálním. Ten obsahoval dvě nebo tři chyby, které mi dalo práci odhalit. Nemůžu zde popisovat všechny problémy, protože bych musel vysvětlit také některé matematické principy z uvedené literatury [1].

Měl jsem například problémy s vahami řídících bodů. Domníval jsem se, že mají stejný význam jako váhy v homogenním souřadném systému. To je sice pravda, ale zapoměl jsem na jednu důležitou věc. Řídící bod s velmi velkou hodnotou váhy by měl ležet téměř na ploše, ale v homogenním souřadném systému by tento bod po korekci jeho velkou váhou ležel skoro v počátku. Pro vyřešení tohoto problému je třeba souřadnice bodu (x,y,z) nejprve vynásobit hodnotou váhy a poté je vše v pořádku.

Dále mi občas dělalo problémy porozumět GOLEMu. Měl jsem například problémy s barvami. Nevěděl jsem přesně pro jakou hodnotou parametru paprsku má být vrácen zásah, aby byl objekt vidět. Nakonec jsem úspěšně všechny tyto problémy vyřešil, protože chyba nebyla v GOLEMu, ale ve mně.

4 Výsledky

Kvůli výše zmíněným problémům s hierarchií ohraničujících oblastí jsem měl omezenou volbu objektů pro testovací scény. Hlavní testovací objekt byl proto válec vytvořený pomocí nurbs plochy. Výsledky jsem porovnával s obyčejným válcem (cylinder) a rozdíly jsou neznatelné.

Zkoušel jsem i složitější objekty skládající se z 10 a více nurbs ploch. Výsledný tvar odpovídá, ale na scéně se objevují černé fleky v místech, kde Newtonova metoda nezkonvergovala, což je v souladu s přechozím vysvětlením. (viz poslední obrázek - Stůl)

Pod obrázky scén jsou znázorněny doby výpočtu na počítači s procesorem Intel Celeron 500 MHz v operačním systému Linux RedHat 7.2. Delší časy u NURBS ploch by měly být zkráceny po implementaci hierarchie ohraničujících oblastí.


Průnik (2 Válce)

Čas: 5.9 s
Průnik (2 Nurbs)

Čas: 36.2 s
Zrdcadlení (Válec)

Čas: 18.5 s
Zrdcadlení (Nurbs)

Čas: 69.4 s



Lom (Válec)

Čas: 18.8 s
Lom (Nurbs)

Čas: 76.2 s
Pokřivená Nurbs

Čas: 66.7 s



Stůl (Golem)

Čas: 535.7 s
Stůl (Cortona)



5 Souhrn

Implementované části: Části, které je třeba implementovat v budoucnosti: Veškerá kód operující s NURBS plochami se nachází v souboru nurbs.cpp(+nurbs.h), který obsahuje implementaci následujících tříd: * Tento způsob řešení hierarchie ohraničujících oblastí byl převzat z dodané literatury, je třeba pouze dovést implementaci do konce. Potřebné instrukce jsou obsaženy též v komentářích.

6 Závěr

NURBS plochy jsou v počítačové grafice velmi důležité objekty. Mohou být použity k aproximaci objektů s lepší přesností než trojůhelníky a výsledná velikost dat je většinou menší. NURBS plochy se dají také jednoduše a intuitivně tvarovat. Bohužel, za tím vším stojí rozsáhlé matematické pozadí a není už tak jednoduché efektivně spočítat jejich tvar. Pro dosažení slušného výkonu je třeba použít rafinovaných metod, ale naneštěstí neexistuje absolutně nejlepší metoda. Jedna z nich byla implementována v dodaném kódu, ale má práce nespočívala pouze v okopírování už existujícího kódu. Musel jsem podrobně nastudovat použité metody, abych mohl vyřešit všechny problémy, které nastaly během přenosu kódu do GOLEMu a hlavní dosažený cíl je, že rutina pro výpočet průsečíku s paprskem funguje v GOLEMu správně.