Hlavní navigace

Vytváříme křivky v PostScriptu

Pavel Tišnovský 17. 5. 2007

V dnešní části seriálu o grafických formátech a metaformátech si řekneme, jak je možné vykreslovat v PostScriptu křivky. Vysvětlíme si význam Bézierových kvadratických a kubických křivek, které jsou použity mimo jiné i v definicích znaků PostScriptových a TrueType fontů.

Obsah

1. Bézierovy křivky
2. Význam kotvicích a řídicích bodů Bézierovy křivky
3. Bézierovy kubické křivky
4. Bézierovy kvadratické křivky
5. PostScript a Bézierovy křivky
6. První demonstrační příklad – Bézierova křivka v PostScriptu
7. Druhý demonstrační příklad – vliv polohy řídicích bodů na tvar křivky
8. Odkazy na další informační zdroje
9. Obsah dalšího pokračování tohoto seriálu

1. Bézierovy křivky

Bézierovy křivky patří v počítačové grafice mezi jedny z nejpoužívanějších typů parametrických (aproximačních) křivek. Jsou totiž velmi jednoduché jak na vytváření a editaci (tj. nepřináší žádné větší komplikace pro uživatele), tak i velmi rychlé při vykreslování, což je výhoda pro programátora nebo pro hardwarovou implementaci vykreslování (to se projeví například i v rychlejším RIPování PostScriptových souborů). Bézierovy křivky stupně dvě a tři, tj. kvadriky a kubiky, jsou použity v mnoha aplikacích a technologiích, včetně PostScriptu a PostScriptových fontů (kubické křivky), TrueType fontů (kvadratické křivky), formátech aplikace Inkscape, CorelDraw!, Adobe Illustrator a „vektorového“ XML formátu SVG – Scalable Vector Graphics.

Bézierova křivka n-tého stupně je určena n+1 body P0, P1, … Pn (jedná se o dva kotvicí a n-2 řídicí body) a vztahem:

401

Kde index i probíhá přes interval i=0, …, n a Bni(t) představuje takzvaný Bernsteinův polynom n-tého řádu. Vyčíslení obecného Bernsteinova polynomu je poměrně složité a zdlouhavé, protože se ve vzorci používají faktoriály (resp. kombinační čísla) a mocniny. Bernsteinovy polynomy nízkých řádů, zejména druhého a třetího řádu, jsou však výpočetně jednoduché, protože použité mocniny a faktoriály jsou nízkého stupně (faktoriál se samozřejmě nemusí počítat, jeho výsledná hodnota se nahradí konstantou).

2. Význam kotvicích a řídicích bodů Bézierovy křivky

Bézierova křivka obecně prochází pouze svým prvním a posledním bodem (kotvicí body), ostatní body pouze ovlivňují výsledný tvar křivky – jde tedy o aproximační křivky, i když je lze po programových výpočtech použít i pro interpolaci. Ve speciálních případech však křivka může procházet i dalšími (řídicími) body, například tehdy, když všechny body leží na jedné přímce. Pomocí prvního bodu (kotvicího) a druhého bodu (řídicího) P0 a P1 se určuje tečný vektor na začátku křivky. Předposlední bod (řídicí) a poslední bod (kotvicí) Pn-1 a Pn zase určují tečný vektor na konci křivky. Této vlastnosti se velmi často využívá při hladkém navazování Bézierových křivek, typicky i v PostScriptu při tvorbě cest či obrysů fontů. Samozřejmě je také možné hladce navázat Bézierovu křivku na úsečku či kruhový oblouk.

Pokud na sebe mají Bézierovy křivky hladce navazovat, tj. mají mít parametrickou spojitost alespoň C1, musí být poslední kotvicí bod první křivky totožný s prvním kotvicím bodem křivky druhé: Pn=P'0 – tím je zajištěno napojení obou křivek, tj. spojitost C0. Také tečný vektor na konci první křivky musí být stejný jako tečný vektor na začátku druhé (navazující) křivky. Na druhém obrázku jsou zobrazeny dvě Bézierovy kvadratické křivky, které jsou hladce navázány se spojitostí C1. Vzhledem k tomu, že se jedná o kvadratické křivky, je každá křivka specifikována počátečním kotvicím bodem, jedním řídicím bodem a koncovým kotvicím bodem. Podobným způsobem jsou konstruovány obrysy písmen v TrueType fontech.

402
Obrázek 2: Dvě Bézierovy kvadratické křivky, které jsou navázány se spojitostí C1

Jednodušší je dosažení geometrické spojitosti G1, kde je nutné, mimo totožnosti posledního řídicího bodu první křivky a prvního bodu druhé křivky, dodržet alespoň kolinearitu tečného vektoru na konci první křivky a na začátku křivky druhé (vektory tedy musí mít stejný směr, ale mohou mít různou velikost, jinými slovy, tyto vektory jsou na sobě lineárně závislé). Geometrickou spojitost je snažší dodržet z toho důvodu, že volnost uživatele při zadávání řídicích bodů je větší než v případě parametrické spojitosti, zejména při použití Bézierových kvadratických a kubických křivek – viz následující kapitoly.

3. Bézierovy kubické křivky

V počítačové grafice patří mezi nejpoužívanější typ parametrických křivek Bézierovy kubické křivky, jejichž podporu nabízí téměř jakýkoli vyspělejší program pracující s vektorovou grafikou – jedná se opět o již zmiňovaný Inkscape, CorelDraw!, Adobe Illustrator či OpenOffice Draw. U systémů CAD a CAM je situace složitější, tam si své místo našly B-splajny a NURBS. Avšak i v těchto programech se Bézierovy kubické křivky často používají, minimálně při práci s PostScripto­vými fonty.

Bézierovy kubické křivky jsou zadány pomocí čtyř bodů v ploše či prostoru. Křivka přitom prochází prvním a posledním (kotvicím) bodem, druhý a třetí bod (řídicí) určuje tečné vektory na začátku a konci křivky. Křivka tedy druhým a třetím řídicím bodem obecně neprochází, což je patrné i ze třetího ilustračního obrázku.

403
Obrázek 3: Bézierova kubická křivka zadaná dvojicí kotvicích bodů a dvojicí bodů řídicích

Vykreslení Bézierovy kubické křivky lze provést postupným dosazováním hodnot do výše uvedeného vztahu a zobrazením či propojením bodů R(t) lomenou křivkou (urychlení výpočtu přináší Hornerovo schéma či metoda konečných diferencí). Další možností, jak vykreslit Bézierovu křivku, je využití de Casteljauova algoritmu pro postupné dělení křivky – právě tento algoritmus je použit ve většině softwarových i hardwarových PostScriptových RIPů, protože je možné snadno detekovat, kdy lze rekurzivní dělení křivky zastavit.

Mezi hlavní výhody Bézierových kubických křivek patří jejich intuitivní zadávání a snadné hladké navazování křivek na sebe. Také výpočet bodů, které leží na křivce, je velmi jednoduchý a rychlý. Pomocí Bézierových kubických křivek však nelze přesně modelovat kuželosečky, zejména kruh a elipsu, což omezuje použití těchto křivek v CAD systémech. Také nelze k obecné Bézierově kubice vytvořit offsetovou křivku, tj. křivku, která se od zadané křivky nachází v určité vzdálenosti – toto omezení se teoreticky může projevit i v komerční grafice (doména programů typu „Illustrator“), ale je nutno říci, že chyba vzniklá použitím Bézierových křivek bývá velmi malá, mnohdy pod rozlišovací schopností lidského oka. Většinou postačí (automatické) rozdělení Bézierovy křivky, která má tvořit offsetovou cestu, na více částí, čímž se získá i větší množství řídicích bodů, se kterými je možné manipulovat.

4. Bézierovy kvadratické křivky

V některých aplikacích, kde se pracuje s parametrickými křivkami (například tvorba fontů TrueType), jsou využity i jednodušší Bézierovy kvadratické křivky, které jsou určeny pouze jedním řídicím bodem a dvojicí bodů kotvicích. Křivka prochází prvním a třetím bodem (kotvicí body), druhý bod (řídicí) určuje současně oba tečné vektory. Ukázka Bézierovy kvadratické křivky spolu s jejími určujícími body je zobrazena na čtvrtém obrázku.

404
Obrázek 4: Bézierova kvadratická křivka zadaná dvojicí kotvicích bodů a jedním bodem řídicím

Základní grafický rozdíl mezi Bézierovými kubickými křivkami (zadanými čtyřmi body) a kvadratickými křivkami (zadanými třemi body) je zobrazen na pátém obrázku.

405
Obrázek 5: Rozdíl mezi kvadratickými a kubickými Bézierovými křivkami

Hladké napojení Bézierových kvadratických křivek lze zajistit zadáním identického koncového bodu první křivky a počátečního bodu křivky druhé. Současně musí být shodné tečné vektory v těchto bodech, tj. prostřední (řídicí) body musí být středově symetrické okolo společného bodu obou křivek. Způsob hladkého napojení je patrný již ze druhého obrázku.

Mnoho vektorových souborových formátů, zejména SVG, podporuje jak kvadratické Bézierovy křivky, tak i křivky kubické, protože každý typ křivek má jiný způsob použití. Při zadávání kvadratických křivek je možné povolit pouze specifikaci „prostředních“ řídicích bodů s tím, že se krajní body dopočtou automaticky – musí ležet vždy v polovině vzdálenosti mezi dvěma prostředními řídicími body. Tento způsob práce s Bézierovými křivkami je použit například v TrueType fontech.

V PostScriptu se přímo s kvadratickými křivkami nesetkáme, používají se však při převodu písem z formátu TrueType do formátu Type 1 či přímo do PostScriptových maker (potřebný převodní program je dostupný například v instalaci TeXLive). Není však problematické si v PostScriptu napsat vlastní vykreslovací rutinu, která po zadání trojice bodů Bézierovy kvadratické křivky vygeneruje cestu složenou z úseček – opět de Casteljauovým algoritmem.

5. PostScript a Bézierovy křivky

V PostScriptu se při tvorbě cest (path) používají výhradně Bézierovy kubické křivky, zejména kvůli jejich jednoduchému a rychlému vykreslování a také relativně velkým možnostem při modifikaci jejich tvaru. Bézierovy kvadratické křivky, tj. křivky nižšího stupně, nemají tak dobré schopnosti aproximovat skutečný tvar modelovaného objektu a křivky vyšších řádů se naopak složitěji (a především pomaleji) vykreslují. V případě kubických křivek je jejich tvar specifikován čtyřmi body. Dva body jsou koncové (také nazývané kotvicí body) a další dva body jsou řídicí. Bézierova kubická křivka začíná a končí v koncových bodech, řídicími body obecně neprochází; jejich poloha však ovlivňuje celkový tvar křivky (z předchozích kapitol již víme, že řídicí body udávají směr a délku tečných vektorů v koncových bodech).

Bézierovy křivky jsou v PostScriptu součástí cest; to mimo jiného znamená, že se při jejich specifikaci zadávají pouze tři body: dva body řídicí a jeden koncový bod. Zbývající koncový bod je tvořen bodem, kterým cesta doposud končila. Je to podobné, jako při přidávání úseček do cest – také jsme specifikovali pouze druhý koncový bod úsečky, první koncový bod nebylo zapotřebí zadávat. Křivka je do aktuálně vytvářené cesty přidána příkazem curveto. Tento příkaz si při svém spuštění (zavolání) vyzvedne ze zásobníku souřadnice tří bodů, vytvoří křivku (většinou ji ihned převede na sadu úseček) a přidá takto rozloženou křivku do cesty. Při převodu Bézierovy křivky na úsečky se křivka rekurzivně dělí až do okamžiku, kdy je rozdíl mezi skutečným průběhem křivky a její aproximací menší než hodnota plochosti (flatness).

Tato hodnota je při zobrazování PostScriptového souboru na zařízeních s relativně nízkým rozlišením (obrazovka, inkoustová tiskárna, laserová tiskárna s 300 DPI) většinou nastavena na hodnotu jednoho obrazového bodu (pixelu). U osvitových jednotek je však nastavena hodnota vyšší (4, 8, 16 pixelů), protože tam se jejich mnohem vyšší rozlišení používá při reprodukci celé barevné škály (většinou pomocí takzvaného autotypického rastru). To znamená, že nemá smysl u osvitové jednotky s 2540 DPI či dokonce 4000 DPI používat jako hodnotu plochosti 1 pixel, ale můžeme se spokojit s hodnotou například čtyř pixelů bez viditelné ztráty kvality – ta je dostatečná již při 600 DPI a hodnotě plochosti 1 pixel. Výsledkem této „optimalizace“ je samozřejmě vyšší rychlost rastrování a tím i ušetřené peníze v případě, že se na osvitové jednotce platí za čas strávený osvitem.

6. První demonstrační příklad – jedna Bézierova křivka v PostScriptu

V dnešním prvním demonstračním příkladu je ukázán způsob vykreslení jedné Bézierovy křivky pomocí základních příkazů pro tvorbu cest. Jedná se o příkazy newpath, moveto, curveto, stroke a showpage. Kromě příkazu showpage jsme si význam všech ostatních příkazů vysvětlili v předchozí části tohoto seriálu. Také již z předešlé kapitoly víme, že příkaz curveto vybírá ze zásobníku trojici bodů (tj. šest reálných hodnot), které považuje za dva řídicí body a koncový (kotvicí) bod. Tento bod se současně stane výchozím bodem při pokračování definice cesty či ořezové křivky.

% Demonstracni priklad na vykresleni jedne Bezierovy krivky.

newpath
100 100
moveto
100 400
400 400
400 100
curveto
% rasterizace cesty
stroke
% vykresleni cele stranky
showpage 

406
Obrázek 6: Snímek prvního demonstračního příkladu po zobrazení programovým RIPem

7. Druhý demonstrační příklad – vliv polohy řídicích bodů na tvar křivky

Ve druhém demonstračním příkladu je ukázán vliv poloh řídicích bodů na tvar Bézierovy křivky. Ta sice těmito body obecně neprochází, ale body významně ovlivňují její tvar. První křivky na sebe nenavazují, ale v pravé části obrázku je ukázáno, jakým způsobem lze na sebe navázat Bézierovy kubické křivky tak, aby byla zachována spojitost typu C1, tj. matematická hladkost a G1, tj. geometrická spojitost. Všimněte si, že příkaz curveto je poměrně dlouhý (7 znaků plus mezera), proto mnoho programů do PostScriptových souborů vkládá na jejich začátek makra a místo volání curveto použije například pouze c. Tímto způsobem vytváří PostScriptové soubory například známý AutoCAD, který definuje makra typu c (curveto), m (moveto) a l (lineto). Při tisku předpokládám formát papíru A4.

% Demonstracni priklad na vykresleni sady Bezierovych krivek.

% prvni krivka (tvar odpovida prvnimu prikladu)
newpath
 50 700
moveto
 50 800
150 800
150 700
curveto
% rasterizace cesty
stroke

% druha krivka
newpath
 50 550
moveto
100 650
100 650
150 550
curveto
% rasterizace cesty
stroke

% treti krivka
newpath
 50 400
moveto
125 500
 75 500
150 400
curveto
% rasterizace cesty
stroke

% ctvrta krivka
newpath
 50 250
moveto
150 350
 50 350
150 250
curveto
% rasterizace cesty
stroke

% pata krivka (se smyckou)
newpath
 75 100
moveto
150 200
 50 200
125 100
curveto
% rasterizace cesty
stroke

% cesta v prave casti papiru
newpath
200 800
moveto
% zacneme useckou
400 800
lineto
% a hladce navazeme krivkou
600 800
600 700
400 700
curveto
200 700
200 600
400 550
curveto
600 500
600 450
400 400
curveto
200 350
200 450
400 450
curveto
% hladce navazeme useckou
500 450
lineto
% oblouk - ridici body jsou shodne!
550 450
550 450
550 400
curveto
% opet hladce navazeme useckou
550 200
lineto
% rasterizace cesty
stroke

% vykresleni cele stranky
showpage 

407
Obrázek 6: Snímek druhého demonstračního příkladu po zobrazení programovým RIPem

8. Odkazy na další informační zdroje

  1. Pierre Bézier,
    http://en.wiki­pedia.org/wiki/Pi­erre_B%C3%A9z­ier
  2. Dmitry Kirsanov's monthly column: Nonlinear Design,
    http://www.we­breference.com/dlab/99­02/index.html
  3. Wikipedia: PostScript,
    http://en.wiki­pedia.org/wiki/Pos­tScript
  4. Paul Bourke: PostScript Tutorial,
    http://local.was­p.uwa.edu.au/~pbou­rke/dataformat­s/postscript/
  5. A First Guide to PostScript,
    http://www.ta­ilrecursive.or­g/postscript/pos­tscript.html
  6. Thomas Merz:
    PostScript & Acrobat/PDF : Applications, Troubleshooting, and Cross-Platform Publishing,
     1996
  7. Jean Callan King, Tony Esposito:
    The Designer's Guide to PostScript Text Type,
     1997
  8. Ross Smith:
    Learning PostScript : A Visual Approach,
    Published 1990
  9. Henry McGilton, Mary Campione:
    PostScript by Example,
     1992
  10. Adobe Systems Incorporated, Glenn C. Reid:
    PostScript Language Program Design,
     1988
  11. Adobe Systems Incorporated:
    PostScript Language Reference Manual,
     1990
  12. Adobe Systems Incorporated:
    PostScript Language Tutorial and Cookbook,
     1985
  13. Adobe Systems Incorporated:
    Programming the Display PostScript System With X,
     1993

9. Obsah dalšího pokračování tohoto seriálu

V následující části tohoto seriálu si řekneme, jakým způsobem je v PostScriptu možné pracovat s fonty a znaky. Uvidíme, že v této oblasti je PostScript velmi výkonný a umožňuje s fonty provádět mnoho operací, včetně použití obrysů písem jako cest (dokonce s možností barevné výplně) či ořezových křivek.

Našli jste v článku chybu?

18. 5. 2007 14:08

MetafontBook mam (tak trosku nelegalne :-(, asi jako vetsina ), tak se do nej mrknu sam.

18. 5. 2007 12:07

tomas z (neregistrovaný)
Rozsáhlá diskuse Bezierových křivek s dvěma body "mezi" (včetně interpretace coby limity konstrukce s trojúhelníky) je určitě v MetafontBooku - ale musil bych se podívat, zda tam je i něco o historii.
Lupa.cz: Seznam mění vedení. Pavel Zima v čele končí

Seznam mění vedení. Pavel Zima v čele končí

Podnikatel.cz: Přehledná titulka, průvodci, responzivita

Přehledná titulka, průvodci, responzivita

Vitalia.cz: Tesco: Chudá rodina si koupí levné polské kuře

Tesco: Chudá rodina si koupí levné polské kuře

DigiZone.cz: Recenze Prostřeno: cirkus postižených

Recenze Prostřeno: cirkus postižených

Podnikatel.cz: Babiše přesvědčila 89letá podnikatelka?!

Babiše přesvědčila 89letá podnikatelka?!

Podnikatel.cz: Hledáte investora? Neunáhlete se

Hledáte investora? Neunáhlete se

DigiZone.cz: Rádio Šlágr má licenci pro digi vysílání

Rádio Šlágr má licenci pro digi vysílání

Lupa.cz: Insolvenční řízení kvůli cookies? Vítejte v ČR

Insolvenční řízení kvůli cookies? Vítejte v ČR

Vitalia.cz: Drahé i levné. Tyhle potraviny nosili na charitu

Drahé i levné. Tyhle potraviny nosili na charitu

120na80.cz: Na ucho teplý, nebo studený obklad?

Na ucho teplý, nebo studený obklad?

Lupa.cz: Avast po spojení s AVG propustí 700 lidí

Avast po spojení s AVG propustí 700 lidí

Vitalia.cz: Baletky propagují zdravotní superpostel

Baletky propagují zdravotní superpostel

Vitalia.cz: Chtějí si léčit kvasinky. Lék je jen v Německu

Chtějí si léčit kvasinky. Lék je jen v Německu

Root.cz: Certifikáty zadarmo jsou horší než za peníze?

Certifikáty zadarmo jsou horší než za peníze?

Podnikatel.cz: Babiš: E-shopy z EET možná vyjmeme

Babiš: E-shopy z EET možná vyjmeme

Měšec.cz: U levneELEKTRO.cz už reklamaci nevyřídíte

U levneELEKTRO.cz už reklamaci nevyřídíte

Vitalia.cz: Dáte si jahody s plísní?

Dáte si jahody s plísní?

Lupa.cz: Co se dá měřit přes Internet věcí

Co se dá měřit přes Internet věcí

DigiZone.cz: Sat novinky: slovenská TV8 HD i ruský NTV Mir

Sat novinky: slovenská TV8 HD i ruský NTV Mir

Podnikatel.cz: Víme první výsledky doby odezvy #EET

Víme první výsledky doby odezvy #EET