Formát X3D a záhadná zkratka NURBS

Obsah

1. Formát X3D a záhadná zkratka NURBS
2. Všeobecně uznávaný standard pro popis těles v počítačové grafice
3. Parametrické křivky a plochy
4. Vlastnosti NURB křivek a ploch
5. Uzly určené pro popis NURB křivek a ploch
6. Literatura a odkazy na internetu
7. Obsah další části tohoto seriálu

1. Formát X3D a záhadná zkratka NURBS

Zkratkou NURBS jsou v počítačové grafice označovány jedny z nejpoužívanějších typů parametrických křivek a ploch. Tato zkratka má dva významy, což může být při čtení některých textů poněkud matoucí:

1. Non-Uniform Rational B-Splines – racionální neuniformní B-splajny. Jedná se o zobecnění neracionálních B-splajnů o racionalitu (váhy řídicích bodů) a uzlový vektor (knot vector).
2. Non-Uniform Rational B-Surfaces – racionální neuniformní B-plochy. Jedná se o zobecnění B-ploch (plátů).

NURB křivky a především plochy se staly populární zejména díky podpoře matematicky přesného modelování kvadrik (koule, kužel, válec) a takzvaných offsetových ploch (jedná se o obecné plochy, které jsou od sebe vzdálené o zadanou minimální hodnotu), které nebylo možné s pomocí klasických B-ploch a Bézierových ploch přesně vytvořit. Důležitá je také značná flexibilita při tvorbě NURBS, protože kromě poloh samotných řídicích bodů je možné měnit i jejich váhu (racionalita) a globální uzlový vektor – knot-vector (neuniformita), jímž se určuje vzdálenost řídicích bodů v parametrickém prostoru.

Postupem času se NURBS pro svoji nespornou kvalitu staly standardem pro systémy CAD i CAM (například se jedná o systém SurfCAM), stejně jako pro pokročilé modelovací programy (Alias Wavefront atd.). Význam samotné existence takového standardu pro počítačovou grafiku je nastíněn v další kapitole.

NURB plocha, která vzdáleně připomíná, jak trefně poznamenal jeden ze čtenářů tohoto seriálu, nejmenovanou budovu.

2. Všeobecně uznávaný standard pro popis těles v počítačové grafice

Při postupném rozšiřování programových prostředků pro tvorbu počítačové grafiky se už před více než dvěma desetiletími začalo ukazovat, že je zapotřebí určitým způsobem sjednotit, popř. navrhnout vhodný matematický a programový aparát, který by se používal při modelování plošných i prostorových objektů. V minulosti se totiž používalo mnoho parametrických křivek a ploch, které mezi sebou nebyly navzájem plně převoditelné nebo měly některé nešikovné vlastnosti.

Výhody sjednocení a následné standardizace takového aparátu byly zřejmé – umožnil by se poměrně nekomplikovaný převod modelů těles mezi různými programovými systémy (zde se přibližujeme k tématu tohoto seriálu, konkrétně k formátu X3D), byl by možný vývoj dokonalejších, rychlejších či paměťově efektivnějších algoritmů i celých výpočetních systémů a v neposlední řadě by zde existovala možnost vytvoření veřejně dostupných knihoven pečlivě navržených modelů těles.

NURB plocha vykreslená pomocí grafické knihovny OpenGL

Úplné a dokonalé sjednocení všech možných reprezentací těles však samozřejmě není možné provést pro všechny myslitelné aplikace, protože každým způsobem reprezentace se snažíme popsat pouze určité (pro nás v tuto chvíli důležité) atributy těles, přičemž ostatní (pro nás nezajímavé) atributy jsou většinou zanedbány. Obecně je však možné říci, že je možné popisovat buď povrch těles (tj. množinu tzv. hraničních bodů) nebo objem těles (tj. množinu vnit­řních bodů).

První typ reprezentace se nazývá povrchová (hraniční) reprezentace, anglicky boundary representation, zkráceně B-rep. Druhý typ je nazván objemová reprezentace, anglicky volume representation. V dalším textu se budu zabývat výhradně reprezentací hraniční, i když povídání o objemové reprezentaci by bylo taktéž zajímavé (viz například knihovna OpenGL Volumizer od firmy SGI). Formát X3D totiž slouží především pro ukládání modelů těles popsaných svou hranicí. Jedinou výjimkou jsou základní geometrická tělesa: kvádr, koule, kužel a válec.

Hraniční reprezentace povrchů těles stále patří k nejpoužívanějším způsobům popisu těles v počítačové grafice. Mezi hlavní důvody vedoucí k častému použití tohoto typu reprezentace patří poměrně jednoduché datové struktury využívané pro popis plochy tělesa (typicky se jedná o „okřídlenou hranu“), přímočaré a rychlé zobrazení s případným využitím grafických akcelerátorů a grafických knihoven (OpenGL, Direct3D, GKS, postarší Phigs) a dobrá podpora ze strany CAD a CAM systémů.

V dnešní době jsou také k dispozici programové knihovny, které umožňují práci s hierarchicky uspořádanou trojrozměrnou scénou, kde jsou využity různé metody pro rozdělení a zpracování této scény. Jedná se o popis topologie a geometrie scény pomocí KD-stromů, BSP-stromů, portálů nebo hierarchických mřížek. Tyto datové struktury tvoří i nezanedbatelnou část herních enginů (Quake engine, Crystal Space apod.).

Mezi další přednosti tohoto způsobu reprezentace těles patří skutečnost, že dnes již existují a jsou poměrně dobře přístupná zařízení umožňující získávání trojrozměrných dat o reálných tělesech. Mezi tato zařízení patří i optické 3D skenery, které mohou po základním zpracování získaného obrazu vygenerovat pravidelnou či nepravidelnou trojúhelníkovou síť (TIN) představující povrch snímaného tělesa.

Dobré výsledky však dává i použití digitálních fotoaparátů spolu s osvětlením scény speciálním vzorkem a následným postprocessingem získaných snímků (po osobních zkušenostech však musím říct, že skutečně dobrých výsledků lze dosáhnout pouze za absolutně dokonalých světelných podmínek a k tomu je ještě nutné předměty zbavit všech odlesků).

Pokud se prostorová tělesa ve vytvářených scénách popisují svojí hranicí, je nutné zvolit vhodný způsob popisu povrchu těles, tj. hranice mezi tělesem a volným prostorem či jiným tělesem. Povrch lze popsat buď jako celek, nebo jako množinu částí povrchu. Popis povrchu jako celku se většinou používá pouze pro jednoduchá tělesa, jež lze popsat jednou implicitní či explicitní rovnicí (koule, válec, kužel, toroid apod.) – to je právě případ základních geometrických objektů, pro které ve formátu X3D existují samostatné uzly.

Mnohem častěji se však povrch tělesa před dalším zpracováním rozděluje na menší části, z nichž každá je popsána samostatně. Zbývá pouze výběr vhodných tvarů (nazývaných také poněkud nepřesně grafická primitiva), pomocí nichž bude celý povrch tělesa popsán. Nejčastěji se setkáme s rozdělením povrchu na trojúhelníkové plošky, kdy jednotlivé sousední trojúhelníky sdílí společné hrany a vrcholy. Podle způsobu rozdělení povrchu tělesa je možné vytvářet pravidelné sítě trojúhelníků či naopak nepravidelné trojúhelníkové sítě (Triangular Irregular Network – TIN).

Tímto typem reprezentace těles jsem se podrobněji zabýval v seriálu o grafické knihovně OpenGL, neboť v OpenGL se mezi grafická primitiva (stavební prvky vykreslované scény) zařadil i trojúhelník, pruh trojúhelníků a trs trojúhelníků, pomocí nichž lze TIN sítě jednoduše a efektivně tvořit. Podobnou strukturu je samozřejmě možné vytvořit, jak již víme z předchozí části tohoto seriálu, i v X3D pomocí uzlu typu IndexedFaceSet i v dříve popisovaném formátu VRML.

Nepravidelná trojúhelníková síť – TIN

Pokud není z nějakého důvodu vhodné reprezentovat povrch těles TIN sítí, je možné podle požadavků aplikace zvolit buď jednodušší reprezentaci nebo naopak reprezentaci na vyšší úrovni. Jednodušší reprezentaci lze zvolit v případě požadavku na co nejvyšší rychlost vykreslování, který se kloubí s požadavkem na malé datové toky mezi pamětí a grafickým akcelerátorem. Reprezentace na vyšší úrovni je zase potřebná (dalo by se říci dokonce nezbytná) při modelování a tvorbě animací.

Jediným plošným útvarem, který je jednodušší než trojúhelník, je elementární rovinná ploška, nazývaná také surfel (surface element). Tato ploška je popsaná pozicí svého středu v prostoru, velikostí a normálovým vektorem. To při vhodném návrhu představuje méně dat, než je tomu u trojúhelníku, u kterého je zapotřebí popsat pozice všech jeho vrcholů – ve skutečnosti se totiž u trojúhelníkových sítí zbytečně ukládají i topologické informace, které nejsou pro některé operace (včetně vykreslování) nezbytně nutné.

3. Parametrické křivky a plochy

Mnohem častěji je však zapotřebí zvolit hraniční reprezentaci povrchu těles na vyšší úrovni, než kterou nabízí pouhá trojúhelníková síť. Důvodů může být víc, nejpatrnější je však potřeba zachování topologie těles, snazší tvorba animací, práce s hierarchickým modelem scény, zachování hladkého povrchu i při velkém přiblížení k tělesu aj. V počítačové grafice se povrch tělesa rozděluje na elementární části povrchu nazývané pláty či záplaty. Výsledná plocha tělesa se získá hladkým navázáním těchto plátů na sebe.

Plát popsaný bodovou rovnicí

Tvar každého z těchto plátů může být vyjádřen takzvanou bodovou rovnicí, což je explicitní vyjádření polohy bodu v závislosti na jednom (křivka) či více (plocha) parametrech. V počítačové grafice se nejčastěji používají bodové rovnice, které jako své bázové funkce obsahují polynomy nízkých stupňů. Předností polynomů je snadný výpočet jejich hodnot pomocí Hornerova schématu (to je důležité při tesselaci, neboli rozdělení plochy na trojúhelníky před jejich vykreslením) a v neposlední řadě také to, že polynomy jsou snadno diferencovatelné, čehož se využívá při hladkém navazování křivek a ploch.

Detail modelu vytvořeného z parametrických ploch (konkrétně NURBS)

Bodová rovnice parametrické plochy Q(u,v) dvou parametrů u a v může být vyjádřena následovně:

Q(u,v)=[x(u,v), y(u,v), z(u,v)]

kde x(u,v), y(u,v) a z(u,v) jsou funkce dvou parametrů, jejichž hodnoty leží v rozsahu <0, 1>. Jak uvidíme dále, není u NURBS potřebné, aby parametry (resp. jejich hodnoty) rostly rovnoměrně, protože díky knot-vectoru (uzlovému vektoru) je možné pro každé rozmezí dvou řídicích bodů zvolit jiný rozsah hodnot a tím i míru růstu hodnot parametrů. Míra může být dokonce nulová, čehož se někdy používá při tvorbě ostrých zlomů na NURB křivce či ploše.

Z bodové rovnice parametrické plochy lze jednoduše vyjádřit i rovnice tečných vektorů ve směrech růstu (či poklesu) parametrů u a v. Tečné vektory se používají ve dvou případech: pro výpočet normálového vektoru (pomocí normálového součinu dvou tečných vektorů, jednoho ve směru růstu parametru u a druhého ve směru růstu parametru v) a pro hladké napojení jednotlivých plátů.

4. Vlastnosti NURB křivek a ploch

NURB křivky a plochy se v počítačové grafice, resp. na ni navazujících oborech, staly velmi populární zejména díky některým svým výhodným vlastnostem, které si krátce popíšeme v následujících odstavcích:

1. Pomocí NURB křivek lze jednoduše a přesně vytvářet kuželosečky, tj. kružnici, elipsu, parabolu nebo jejich části (oblouky). Zejména možnost přesného vytváření kružnic a elips (a samozřejmě i jejich částí – oblouků) je v CAD/CAM aplikacích velmi důležitá a právě z tohoto důvodu se v CAD/CAM nepoužívají jinak oblíbené Bézierovy křivky.
2. NURB plochy mohou přesně vytvářet povrch (nebo část povrchu) kvadrik, jež jsou obdobou kuželoseček v prostoru. Je tedy možné naprosto přesně vymodelovat kouli, válec, kužel apod.
3. Vhodnou volbou uzlového vektoru a vah řídicích bodů je možné vytvářet povrchy se zlomy a hranami, například kvádry. Tato vlastnost se opět použije při práci v CAD/CAM systémech, ve kterých se běžně vytváří tělesa, jež mají střídavě spojité a nespojité povrchy. Lehce se tak může stát, že celá scéna je tvořena pouze NURB plochami, i když se v ní budou vyskytovat kvadriky, kostky atd.
4. NURB křivky a plochy si přitom zachovávají veškeré vlastnosti parametrických křivek a ploch, například invarianci k transformacím, existenci komplexní obálky (pro nezáporné váhy řídicích bodů) atd. To je důležité zejména pro rychlé vykreslování – transformace je možné aplikovat pouze na řídicí body a ne na výsledné trojúhelníky (dnes se ovšem situace v souvislosti s moderními grafickými akcelerátory poněkud změnila, protože transformace prováděná přímo na grafické kartě je většinou provedena rychleji, než při její programové implementaci). Existence konvexní obálky zajišťuje zrychlený výpočet kolizí a také – což je mnohdy důležitější – viditelnosti.
5. Editace NURB je z uživatelského hlediska poměrně jednoduchá – mění se polohy řídicích bodů, jejich váhy a případně i uzlový vektor. Při interaktivním modelování se však téměř vždy mění pouze polohy řídicích bodů, jejichž cílenou změnou lze dosáhnout téměř jakéhokoli tvaru. Změna vah řídicích bodů a uzlového vektoru je aplikována automaticky při vytváření kvadrik a offsetových ploch – viz předchozí odstavce.

Přesný kruhový oblouk vytvořený jedinou NURB křivkou

Přesná kružnice vytvořená jedinou NURB křivkou

5. Uzly určené pro popis NURB křivek a ploch

V grafickém formátu X3D se NURB křivky a plochy používají v několika variantách. Z tohoto důvodu se můžeme setkat i s různými typy uzlů, pomocí kterých se tyto grafické prvky do vytvářených scén vkládají. Jedná se především o následující typy uzlů:

Kvadriky i další tvary popsané NURB plochami

6. Literatura a odkazy na internetu

1. Foley J., Dam van A., Feiner S., Hughes J.: Computer Graphics – Principles and Practice (Second Edition)
   Addison-Wesley, Reading, Massachusetts, 1990, ISBN 0–201–12110–7
2. W.T.Hewitt a další: NURBS: A Tool or an Ornament for Graphics?
   Manchester Computing Centre, University of Manchester, Manchester M13 9PL
   (pravděpodobně nejlepší shrnující článek o NURBS)
3. Žára J., Beneš B., Felkel P.: Moderní počítačová grafika
   Computer Press, Praha, 1998, ISBN 80–7226–049–9
4. Žára J., Limpouch A., Beneš B., Werner T.: Počítačová grafika – principy a algoritmy
   Grada, Praha, 1992, ISBN 80–85623–00–5
5. Krátké a výstižné vysvětlení pojmu NURBS na stránkách Wikipedie:
   http://en.wiki­pedia.org/wiki/Nur­bs
6. Model stegosaura byl získán na stránce:
   http://www.tur­bosquid.com/HTMLCli­ent/FullPrevi­ew/Index.cfm/ID/1710­71/Action/FullPre­view
7. Obrázek nohy dinosaura byl získán na adrese:
   http://perso.wa­nadoo.fr/rimas­son/3d/leg.htm

Model vytvořený pomocí NURBS, který

7. Obsah další části tohoto seriálu

V následující části článku o grafickém formátu X3D si ukážeme tvorbu NURB křivek i NURB ploch podrobněji. Zejména si popíšeme uzly typu NurbsCurve2D, NurbsCurve, NurbsSet a NurbsPatchSur­face, které tvoří nejpodstatnější a pravděpodobně také nejpoužívanější část celého standardu.