Algoritmy počítačové grafiky I (Algorithms for Computer Graphics I) Prof.Ing.Václav Skala, CSc. http://www.VaclavSkala.eu
Abstrakt Algoritmy počítačové grafiky a jejich implementace je nedílnou součástí jak grafických systémů, tak i CAD/CAM systémů. V této práci jsou uvedeny základní algoritmy, metody a postupy, které se používají v různých modifikacích i v dnešních systémech
Abstract Algorithms for computer graphics and their implementation is a part of graphical systems and CAD/CAM systems. Fundamental algorithms, methods and approaches used in today’s systems are explained.
Algoritmy počítačové grafiky I Algorithms for Computer Graphics I Published & printed by: Vaclav Skala – UNION Agency Na Mazinach 9 CZ 322 00 Plzen Czech Republic Year 2011 ISBN 978-80-86943-19-0 Electronic version
http://www.VaclavSkala.eu http://Graphics.zcu.cz
Profil autora Prof. Ing. Václav Skala, CSc. se zabývá počítačovou grafikou od r.1975, kdy na Vysoké škole strojní a elektrotechnické v Plzni zavedl a následně vyučoval předmět Počítačová grafika a umělá inteligence. V roce 1981 obhájil disertační práci na témate relačních databází se specializací na reprezentaci relací a optimalizaci dotazů uživatele. V současné době se odborně věnuje především algoritmům počítačové grafiky a vizualizaci dat a algoritmům včetně matematických aspektů. Je vedoucím Centra počítačové grafiky a vizualizací (http://Graphics.zcu.cz) při Katedře informatiky a výpočetní techniky na Fakultě aplikovaných věd Západočeské univerzity v Plzni. V letech 1984-1989 působil na Brunel University v Londýně a později přednášel na NATO Advanced Study Institute v zahraničí. V roce 1996 se stal profesorem na Západočeské univerzitě, odborně působil na Bath University v U.K., Gavle University ve Švédsku a na dalších zahraničních odborných pracovištích. Prof.Skala je řešitelem zahraničních i národních odborných výzkumných projektů, členem několika redakčních rad prestižních zahraničních odborných časopisů, členem programových výborů mezinárodních odborných konferencí. Od r.1992 je organizátorem mezinárodních odborných konferencí WSCG zaměřených na počítačovou grafiku, vizualizaci dat a počítačové vidění (http://www.WSCG.eu). V současné době je prof. Skala profesorem na Západočeské univerzitě v Plzni a VŠB-Technické univerzitě v Ostravě. V roce2010 odborně působil též na Přírodovědné fakultě Ostravské univerzity v Ostravě (http://AlgVis.osu.cz). V roce 2010 získal významné ocenění mezinárodní asociace pro počítačovou grafiku „Fellow of the Eurographics Association“ za dlouhodobé odborné výsledky a organizační aktivity v oblasti počítačové grafiky.
Poznámky pro laskavého čtenáře Toto je rekonstrukce učebního textu Algoritmy počítačové grafiky I – III, který vznikl pro studenty Západočeské univerzity v Plzni v roce 1991. Tato publikace vznikla rozšířením publikace Počítačová grafika I - II, která vznikala v roce 1989 pro potřeby studentů Vysoké školy strojní a elektrotechnické a která byla vydána v roce 1990. Jde tedy o text zohledňující algoritmy, metody a stav technologie před více než před 20 lety. Je nutné si uvědomit, že obor počítačové grafiky je poměrně velmi mladý, bouřlivě se rozvíjející a poměrně hodně závislý na dostupných technologiích. Nicméně většina metod, postupů a algoritmů je používána dodnes. Pochopitelně je oblast počítačové grafiky dnes podstatně širší a zahrnující mnohé jiné oblasti, které jsou odborně rozvíjeny kolegy v Centru počítačové grafiky a vizualizací při Katedře informatiky a výpočetní techniky Fakulty aplikovaných věd, viz http://Graphics.zcu.cz Rád bych proto požádal čtenáře, aby uvedený text a kvalitu tisku posoudil v kontextu té doby, kdy: nebyl prakticky přístup k zahraniční literatuře a publikace se velmi obtížně získávaly přes mezinárodní výpůjčky, resp. přes osobní kontakty nebyl k dispozici Internet, e-mail, WEB a digitální knihovny byly k dispozici první 8mi bitové PC systémy s „fantastickou“ kapacitou paměti 512 KB byly k dispozici první jehličkové tiskárny (9 tiskových bodů na textovou řádku) a „unikátní“ textové procesory T602 a výborný graficko-textový procesor Chi-Writer (http://en.wikipedia.org/wiki/ChiWriter), ve kterém byl text napsán. Je nutné si uvědomit, že před rokem 1989 bylo velmi obtížné získávat odborné publikace a publikovat odborné výsledky v mezinárodně uznávaných časopisech a na mezinárodních konferencích. Již v roce 1975 na Vysoké škole strojní a elektrotechnické, Fakultě elektrotechnické vzniká předmět Počítačová grafika a umělá inteligence Nové odborné výsledky, algoritmy a metody laskavý zájemce nalezne na URL: http://www.VaclavSkala.eu. Také bych rád zájemce o počítačovou grafiku odkázal na publikace z mezinárodních konferencí WSCG, na časopis Journal of WSCG a GraVisMa workshopy: WSCG – International Conferences on Computer Graphics, Visualization and Computer Vision http://www.WSCG.eu GraVisMa – Computer Graphics, Vision and Mathematics http://www.GraVisMa.eu
Tento text, který vznikl rekonstrukcí z archivu autora, byl doplněn o seznam publikací tak, aby tvořil ucelenou publikaci. Předpokládá se, že další části původní publikace budou rekonstruovány následně. Je mi milou povinností poděkovat všem, kteří mi stimulovali moje odborné aktivity a které jsem měl tu čest nejen potkat na Brunel University a na NATO Advanced Study Institutes, ale i s mnohými odborně spolupracovat. Patří k nim zejména: Prof. M.L.V. Pitteway Brunel University, U.K.
Prof. Jack E. Bresenham IBM Corp., USA a Winthrop University, USA Prof. David F.Rogers U.S. Naval Academy, USA
Prof. F.R.A.Hopgood Rutherford Appleton Laboratory, U.K. a Oxford Brookes University, U.K.
V Plzni dne: 2011‐07‐25
prof.Ing.Václav Skala, CSc.
Předmluva
V
publ ikac i
pokus i l
Al gor i tmy
z achy t i t
p o č í tačové
s oučasný
s tav
v
grafiky I - I I I
oblas t i
algo r i tmů p o č í t a čové grafiky a CAD sys témů .
pr inc ipů
j s em
se
vybr aných
Vzhl e dem k prudkému
r ozvo j i použ i t í te chni ckých a programových p r o s t ř e dků p o č í t a čové grafiky j e tato publ ika ce do ur čité míry p o j ata j ako p ř ehledov á , p ř i čemž podrobnos t i lze nal é z t v l i teratuř e .
Někte r é p a s á ž e byl o
nutno z r e dukovat na téměř informat ivní úroveň z důvodů p ř í l išné teor e t i cké s l ožitos t i , nedos tupn o s t ,
s lo ž i t o s t i algo r i tmů ,
p ř í p adně p r o j e j i ch
n e bo ť firmy skute čně použ i té me tody nepubl ikuj í .
Pro dal š í s tudium v obl a s t i p o č í t a čové grafiky j e n e z bytné s le dovat odbornou l i t e r a turu, na kterou by ch rád upozorni l ,
a to
ze j ména na : a ) časopisy Computer Gr aphi cs Forum , Nor th Ho l l and Comp . * ACM Tran s a c t ion on Gr aphi cs , ACM + The Visua l Compute r , Springer Verlag
*
+ Computer Aided Geome t r i e Des ign , Nor th Ho l l and Comp . Computational
Geome try ,
Theory
and ,App l i cat ions ,
E l s ev i e r
S cience PUbl : Computer Aided Des ign , Butte rworth & Co ( Publ i s he r s ) L t d . Compu t e r s & Gr aphi cs ,
+
pe rgamon Pr e s s
b ) s borníky konfe rencí * EUROGRAPH I C S ( EUROGRAPHICS As s o ciat ion ) , + S I GGRAPH ( USA ) , + Comput e r Gr aphi c s Internat ional Publ ika c e
označené
Západo če ské
*,
+
univ e r z i ty
je
možné
( publ ikace
vypůj č i t označené
přes +
knihovnu
n e tvoř í
celý
kompl e t ) . Za
zákl adní
považovat [ 9 7 ],
[ 5],
[ 1 0 4],
publ ika ce
[ 1 1 ],
[ 1 0 8],
[ 44], [ 1 0 9],
v
[ 5 5], [ 1 1 2],
uve dené v s e znamu l i t e ratury , p ř e de v š ím k
d a l š ímu
s ouvi s e j í cí ch
s
s tudiu
p o č í t a čovou
l i t e r atury j e uveden v 3 .
obl a s t i [ 5 6], [ 1 1 4],
p o č í t a čové [ 6 6],
[ 6 9],
[ 1 2 3],
grafiky [ 7 2 ],
probl emat iky ,
grafikou .
Ce lkový
díle t é to publ ika ce .
[ 9 4],
p ř i č em ž o s t atní ,
lze ozna č i t za doplňkové , dané
lze
s l oužící
př ípadně s e znam
p ar t i í použ i t é
Je
mou
milou povinnos t í
vzniku t é t o publ ika ce , k vlas tn í p r á c i . za
j ej í
zamě ř ením
podně tné
s tudentům
gr afika
pomo cníky
demon s t r a čn í ch
a
laskavě
z apůj čen
neocenite lným pomo c í
prl
výukových
k dispo z i c i . pomo c í
kr i t i cké
textového firmou
a
CAD
ke
byl a
do
Vě t š ina který
j s ou
formátu
p r o c e s oru
obr ázků
byl a
ukázal
být
byl i
p ř í padným
ChiWr i te r , ( USA )
se
a tvor bě
" came r a
Software se
kte ř í
a l go r i tmů
které
bývalým
v P l zn i
sys témy ,
ově ř ování
Hor s tmann
COREL DRAW ,
př ipomínky ,
univ e r z i ty
programů ,
Skr ipta
pomo cníkem .
programu
a
Z ápadoče ské
P o č í t ačová
p ř ip r avena
přispěli
a ť už vytvořením podmínek n e bo s t imul a c í
neocenite lnými záj emcům
kteří
Cht ě l by ch z e j ména poděkovat ing . I . Kol ing e r ové
konkr é tní ,
i s oučasným
poděkovat vš em ,
r eady "
který
byl
a který
byl
r e a l i zována ve lmi
dobrým
Budu z avázán v š em č tenářům za j akéko l iv p ř ipomínky ,
návrhy
nás t r o j em p r o daný úče l . či
doplnění
předkládaného
textu .
Uví tám
informace o ap l ikaci předkl ádaných algor i tmů , či z c e l a nových algor itme ch počítačové grafiky .
r ovně ž
p ř ípadné
j e j i ch mod i f ika c í
Obsah
1.
2.
3.
Úvod
1
1 . 1 Vyme zení obs ahu p o č í ta čové graf iky
2
1 . 2 Apl ikace p o č í t a čové grafiky
4
Gr afi cká z a ř ízení
12
2 . 1 Vs tupní zaří zení
12
2 . 2 Výs tupní z a ř ízení
24
2 . 3 Ne t r a d i ční v s tupní a výs tupní zař ízení
45
2 . 4 P ř íkl ady
47
Z ákl adn í algor i tmy počítačové grafiky
54
3 . 1 Algor i tmus p r o kr e s lení čáry
54
3 . 2 Digitáln í diferen c iální analyzátor
55
3 . 3 B r e s enhamův algoritmus
59
3 . 4 Gene rátor kružni c e
66
3 . 5 Gene r átor kuže l o s e ček
76
3 . 6 Kódování grafi cké informace
77
3 . 7 Rep r e zentace n-úhe lníků a oblas t í
85
3 . 8 P lnění a š r afování
90
3 . 9 Ant ia l i as ing
99
3 . 1 0 Rep r e zentace tř írozměrných obj ektů
102
1.
Úvod
P o č í t a č ová grafika 'j e oblas tí výpo č e tní zabývá
znázorňováním
dat
rychlou komunikaci me z i rychl o s t i
v l a s tního
pře dávané
v
grafické
podobě .
Člověk
ale
i
pomocí
z
která
Umožňuj e
č lověkem a p o č ítačem ne j en
zobrazován í ,
informace .
t e chniky , po
h l e diska
z r akového
se
ve lmi s t r án ce
mno ž s tv í
v j emu
může
abs orbovat grafickou informaci o něko l ik ř ádů rychl e j i n e ž p ř i pře dáván í
informace
p o č í t a čové
grafiky narůs tá s neus tále k l e s a j í cí
j ak
pomocí
j e dno t l ivých
mikr opo č í ta čů ,
tabulek
grafických
j e j ichž
čísel
apo d .
p e r ife r i í ,
dne šní
cenou har dwaru
t ak
parame try
Důl e ž i t o s t
j iž
i
o s o bn í ch
b ě žně
dos ahuj í
parame trů minip o č í tačů . S r ozvo j em technologií v oblas ti výpo č e tní t e chniky n a s tává odklon od tr adičních grafických perife r i í , na kr e s lení čar , j e dno t l ivých vývo j em
které
j s ou z a l o ž eny
k r a s t r ovým zař í zením zalo ženým na zobrazování
bodů
s
využ it ím
vyv s tává
š ir oké
nutno s t
bar evné
vytvář ení
s p e ci a l i zovaných na ras trové p r o s t ř e d í .
p a l e ty .
nových
S
t ímto
a l go r i tmů
Mnohé a l go r i tmy uve dené
v této publ ikaci j s ou t é ž použi t e lné p r o bě žná z ař í zení ,
která
s e v prax i používaj í . ,
Ro zvoj
p o č íta čové
vzrůs t a j í cím Kdys i
k
nim
p o č tu
grafiky
systémů
patř ily
ř adě
minipo č ítačů
sys témy
PC AT ,
p r ak t i cky
na
resp .
ADT 4 5 0 0 ,
PC 3 8 6 ,
v š e ch
ČSFR
vhodných
z e j ména
minipo č í t a čů SM 5 2 / 1 1 ,
v
pro
systémy
resp .
p o č í t a č ovou IGS
ADT 4 7 0 0 . j s ou
Tyto
s y s témy
na
ř adě
z a l o žené na
Velmi
dne s
na
grafiku .
zalo žené
systémy
PS/2
pracov i š t í ch .
dokumentovat
I SAP
SM 5 2 / 1 2 , resp .
l ze
k
r o z š í ř ené d i s p o z i ci
j s ou
v
mnoha
př ípade ch doplňovány různými grafickými zobr azovacími j e dno tkami s velkou r o z l i š ovací s chopnos t í a akce l erátory .
V s ou č a s né době
se r o z š iřuj í z e j ména systémy PC 3 8 6 / 3 8 7 ,
resp .
PC 4 8 6 ,
s p o j ení
ART I ST
apod .
s vide okar tou
Super VGA ,
výkon ,
a l e i p o s t a čuj í cí výkonno s t v oblas t i grafických oper a cí . budoucnos ti
s a r chit ekturou pr ováděných
R I SC
velkým
firmy
o čekávat
SUN,
pamě t i
výkonem,
oper ací . APOLLO,
INTERGRAPH ,
Patří
a
výp o č e tní
používání
grafických pracovních
pracovn ím
grafických
s t an i ce typů I R I S , i s y s t émy
a
lze
kapacitu
pro
apl ikace
vyzna čuj í
pos tačuj ící
maj í
b ě žné
V kr átké
nej en
resp .
k t e r é ve
s t anic,
z e j ména k
n im
p ak
ne j en
p o č í t a čů které
p o č tem p r a covní
VRX firmy Hewl e t t Packar d , kter é
- 1 -
j s ou
využ ívány
se
ale
z e j ména
v oblas t i
GIS
( ge ogr afických
informačních
a
sys t émů )
pro
apl ikace v o b l a s t i kar t ogr afie a geodé z i e . Se
s y s t émy
je
dodáváno
ne j en
p r o p o č í t a č ovou grafiku ( např . s y s témy o r ientované ( CADD )
firmy
ULT I MATE
např .
sys tém Micr o S tat ion PC,
firmy
a
pro
návrh
sys tém
I NTERGRAPH,
CADD ,
se
PHI G S ) ,
AutoCAD ,
plošných je
Micr o S t a t ion PC
r e sp .
ur č en
ur čen
chovaj í vůči uživat e l i
a
U l t iCap
Or CAD .
pro
pro
vybavení
ale i uce lené
U l t iBoard
s po j ů ,
který j e
který
programové
Jsou to např .
Eagl e ,
firmy
a M S DOS ,
normy GKS ,
uživate l sky .
INTERGRAPH ,
zákl adní
Naví c
p r o s t ř e dí
pr acovní s t e j ně ,
PC
s tan ice
i když
se
pr ovozuj í n a t e chnice z ce l a rozdílné .
1 . 1 Vymez ení obsahu pačí tačové graf iky
Vym e z i t o b s ah p o č í t a čové gr afiky j e dne s
z a s ahuj e
t e chniky ,
do mnoha oblas tí
kte r é
ne j s ou
i apl ikací ,
j e j ichž
t e chno logií .
Ap l ikace
j en
těžiště
spoj ených s př ímého
je
složité ,
apl ikací
apl ika čního
předev š ím
p o č í ta čové
n e t r a d i čn í ch oblastech , např .
poměrně
grafiky
ve
lze
neboť
výp o č e tn í r áz u ,
výzkumu
nal é z t
i
ale
nových v
mnoha
animace filmů apo d .
Z p r acování grafické informace s e z e j ména vyzna čuj e : - extr émním obj emem zpracovávaných dat , - nume r i ckou náročno s t í j edno tlivých výp o čtů, - vys okými nár oky na všechny har dwar ové parametry výp o č e tního sys tému ,
ze j ména pak na kapacitu pamě t i .
Někte r é
typy
kdy
použ ití
ani
úloh ,
z e j ména
s imul ační ,
vyžaduj í
systému CRAY není pos t a čuj í cí ,
rychlo s t i ode zvy sys tému .
s up e r po č í t a č e , např .
z
důvodů
Pro e fekt ivní použ i t í a tvo r bu nových
grafických sys témů j e v š ak ne zbytné pochop it j edn o t l ivé z ákladní pr incipy
metod
a
algor itmů ,
i
když
bude
neus t á l e
narůs tat
použi t í s p e ciali zovaných grafických proce s orů a akce l e r átorů . Vymezení
oblasti
p o č í t a čové
grafiky
je
cha r ak t e r izováno
tabulkou 1 . 1 . 1 , kde j e p o č í t a čová gr afika chápána úzce j ako tzv . gene r a t ivní gr afika , vytvoř í
obrazový
s chemat i cké ,
tj .
j ako proce s ,
výs tup .
vys t ihuj e
Toto
hlavní
který ze
vymezen í ,
probl émy
zadaného popisu i
když
p o č í t a čové
grafiky .
V s oučasné době j e j e dním z hl avních směrů výzkumu např . - 2 -
dos ti ř e š ení
problému věrno s t i
zobrazení ,
kde vedle výp o č e tn í ch p r o b l émů
je
t é ž nutné ř e š it probl emat iku použi t í bar e v a bar evných sys t émů .
výs tup j e dán j ako :
v s tup j e dán j ako : popis
manipul ace
výs tup
grafika zpr acování
r o zpoznávání obrazů
zvuk
hlas ový
p o č í t ačová
symbol i cká
obrázek
zvuk
obrázek
popis
obrazů zpracován í
rozpoznávání
zvuku
zvuku
Tabulka 1 . 1 . 1
t r an s formace
I�
..
_
formální popis
r o zpoznávání
gener ace
takt i ln í č i dl o
manipu l á t o r
Lr
Č I D L A
reprezentace vj emu pomocí datových -
s truktur
-
obrazové č id l o zvukové č i d l o
��
zpracování vjemu
Obr . 1 . 1 . 1
- 3 -
I--
-
A K Č N
Č L E N
1 y
-
r-
obrazový výs tup h l a s ový výs tup
Funkční Při
z a č l enění
symbol ické
vzorců atd . ,
p o č í tačové
manipulaci ,
grafiky
např .
symbo l i cké
docház í vlas tně k trans formaci
V př ípadě rozpoznávání obrazu j de daného obrazu , p o č í ta čové z obl a s t i
j de
p o č í t ač ové
o
j ako na probl émy duá lní . gr afiky
pos tup
grafiky Z
a
der ivaci ,
úpr avě
formálního p op i s u . tj .
opačný .
šířej i
a
použ i t í apar á tu
Na
zpracování
toho to důvodu
chápána
obr . 1 . 1 . 1 .
o nalezení formálního p o p i s u
zat ímco při gener aci obrazu ,
grafiky ,
p o č í t a čové
naznačuj e
mnohé
obr azu je
p r o bl émy
lze
pohl í ž e t
t aké n ěkdy o b l a s t
zahrnuj e
p ak
i oblas t i
zpr acován í a r o zpoznávání obr azu . Z a obrazové č i d l o l ze považovat např . kame r u , ( s canner ) ,
atd .
takt ilním snímač
Zvukovým č idlem může být např .
č idlem může
t l aku .
být např .
Hlas ový
r eproduktor e m ,
výs tup
ř ádkový s n ímač
mikrofon ,
s p ínač vyme zuj í cí může
obrazový výs tup např .
být
z a t ímco
p o l ohu
r e p r e zentov án
nebo např .
monitorem .
1. 2 Ap l ikace a použ i t í počí tačové graf iky
P o č í t a čová gr afika se dne s používá v nej různě j š í ch odvě tvích l i dské
č inno s t i .
oblast
Je
r o zvinuta
ap l ikací ,
je
poněkud
par adoxn í ,
př edevš ím
z
že
\
hledi ska
a čko l iv
mo žných
a tou j e animace fi lmů .
exis tuj í
s p o l e čnos t i ,
s p e ci a l izované
s p e ciální programové vybavení , j s ou
že
tato
t e chni ckých
j e dnou z ne j více finančně výhodných o b la s t í p r ávě
obl a s t ryze n e t e chnická ,
z ř e j mé ,
byla
tato
t e chni cké
oblast
vytvoř eny
za
pomoci
z oblasti
p o č í t a čové
zce l a
Mezi
animace , animace
n e j enže
vytvář e j í
ale též i p ř í s lušné s y s t é my .
vyžaduj e
apl ikace .
které
V dne š n í době
odlišné
prvními je
známý
j s ou
na
p r o s t ř e dky
filmy ,
které
f i lm
než byly
Ukázky
TRON .
obr . 1 . 2 . 1
Je
a o br . 1 . 2 . 2 .
Kromě v l as tní gene race obr ázků j e nutné t é ž napodob i t p lynul o s t pohybů apod . známá . [ 129 ] ,
Problematika p o č í ta čové
není
u nás
V l i te r atuř e l z e v š ak nal é z t mnoho informací , [ 17 1 ] .
Animační
s imul a čn í ch programů , Je
animace
pochopite lné ,
as pekty
např . že
l ze
nal é z t
i
1 024 x 1024
pro účely p o č í t ačové
není
v i z např . u
různých
z obl as t i kosmického výzkumu . animace
k d i s p o z i ci s p e ciální výs tupní zařízen í , nebo ť např . s chopno s t
zce l a
pos tačuj ící
ve l iko s t p r omítací plochy v kině .
- 4 -
při
mus í
být
r o z l i š ovací
zvě t š en í
např .
na
Obr . 1 . 2 . 2
Obr . 1 . 2 . 1 J inou
obl a s t í
apl ikace
počíta čové
s imul átorů p i l o táže le tade l ,
lodí ,
grafiky
aut apod .
Tyto
je
použ i t í
sys témy byly
v první fázi motivovány pře dev š ím možno s tmi využ i t í p ř i výzkumu vesmíru, l e tade l ,
ve voj ens tví apod . o b s ahuj í
též
Skute čné s imul átory ,
s l oži té
kte r é z a j i š ťuj í náklon kabiny , Me z i Mil e s
š p i čkové (U. K. )
sys témy a
patří
Mar coni
prvky
např .
mechanického
p ilotáže
cha r akt e r u ,
vytvář ení poci tu p ř e tížení apod . např .
Radar
systémy
Sys t ems
firmy
L td . ,
viz
S INGER
obr . 1 . 2 . 3 .
a obr . 1 . 2 . 4 .
Obr . 1 . 2 . 4
Obr . 1 . 2 . 3 - 5 -
L ink
Naví c
uve dené
sys témy
umožňuj í
aerodynamických
parametrů
a
apod .
r e álno s t i
poskytuj í
Z
prostoru.
důvodů
též
s imul aci
chování
s imul aci tyto
p ř e sn ě
n e j různě j š í ch s y s t émy
v j em
Dne šní s imul a ční systémy navíc umo žňuj í např .
l e tu nad r o z s áhlým ter énem , umožňuj e
vytvář e t na
obrovské
č tve r e ční
poruch h l o ubky
s imul a ci
neboť rozvoj pamě ťových t e chno l o g i í databáze
( sy s tém
CT 6
repre zentovat 1 0 0 0 0 č tvere čních mil při hus t o t ě až n-úhelníků
podle
míli ) .
Na
obr . 1 . 2 . 5
a
Obr . 1 . 2 . 6 - 6 -
1 . 5 mil iónů
obr . 1 . 2 . 6
ukázky grafického výs tupu u automobilového tr enažéru .
Obr . 1 . 2 . 5
umožňuj e j s ou
Ve d l e
gene r a t ivní
p o č í tačové
grafiky
je
zpr a c ování obrazu ve lmi důl e ž i tou ap l ikac í .
též
5 0 0 0 mIm .
Spacel ab- l ,
Tento
k t e r é j e ve výš ce
snímek byl poř ízen v průběhu
v i z obr .
při
J ako p ř ík l a d s i l z e
uvé s t snímek č ás t i Tibe tu s j e zerem Har a Nuur , asi
výs tup
l e tu s t ani c e
1. 2. 7.
Obr . ! . 2 . 7 Dal š í ukázkou j e snímek s t ř ední čás t i Švýcarska ( as i 6 0 x 8 0 km oko l í
Luc e rnu) ,
obr . l . 2 . 8 ,
pohled
š ipkou
obs ahuj e
byl
poří zen
sys témem
Land s a t - TM ,
a k t e r ý byl nás l edně zpracován tak ,
per spekt ivní obrázku
který z
v levo
2 500 x 3 000
kte r é
mís t a ,
po
p ixelů,
ž e b y l vytvořen
označeno
obr . l . 2 . 9 .
viz
dol e ,
je
p e r s p ekt ivní
viz
na
O r i g in á l
původním obr azu
t r an s forma c i
pak
1 0 0 0 x 7 1 0 p ixelů . Je
z ř e j mé ,
že
te chniky
dálkového
i monitor ování ur č i t é oblas ti .
průzkumu
Na obr . l . 2 . l 0
Če rnobylu p ř e d havárií j ade rné e l ektr árny .
je
Země
umo žňuj í
s nímek o b l a s t i
Snímek na obr . l . 2 . l l
ukazuj e s i tua c i 1 2 dní po havár ii .
Zvýšená t e p l o t a v o dy v nádr ž i
je
resp .
identifikována
změnou
barvy ,
vyš š ím
j as em .
mon i t o r ov a c í t e chniky l z e použí t v mnoha oblas t e ch , - 7 -
Takové
z e j ména pak
prl
použ i t í
kamer
např .
pr a cuj í c í ch
v
infr a č e rvené
části
s pektr a .
Obr . ! . 2 . 1 1
Obr . ! . 2 . 1 0 Jedno
z
n e j známě j š í ch
RAE Farnbor ough ( U . K . ) . grafiky
lze
po čas í ,
viz
vidět
center
Téměř
na
Dal š í
nal é z t v o b l a s t i ar chi tektur y , j s ou
ukázány
výs tupy
každodenní
obr azovce
obr . 1 . 2 . 1 2 .
z kamery
dálkového TV
průzkumu
ap l ika c i
p ř i j ímač e
apl ikace
prl
p o č í t a čové
s tavebn i c tv í apod . Polar o id ,
kte r é
Z emě
je
p o č í ta čové p ř e dpovědi grafiky
lze
Na obr . 1 . 2 . 1 3 j s ou
v l a s tně
podkladem p r o účas t v konkursu na vybavení mí s tno s t í nábytkem . Sys t émy tohoto druhu s e daj í využít např . pro
s tave bní
např .
ú č e ly
a
i pro
p ř i r ekon s truk c i u l i c
č i s t ě ur ban i s t i cké
s tudie ,
budova " zas adí " d o skute čně exis tuj í c í kraj iny . - 8 -
kdy
se
Obr . I . 2 . 1 2 Kromě výš e uvedených ap l ikací j e ne zbytné t é ž upozornit na ty ,
kte r é
Jednou
z
s č l ověkem výr obě
n e j s ou n i ch v
vůb e c .
o " ne zaj ímavý " a j ednodu ché , e l ektr i ckého
s i ce
je
tak
použití
sys téme ch Z
ř ízení
s amotné
neboť
j de
s chéma
v p e t r o chemi ckém pr ovo zu apod .
s t e j ně
důl e ž i t é .
pro
komun ikaci
grafiky
te chnol ogických
zobrazuj í např .
p r oudu ,
ni cméně
počí tačové
hledi ska
problém, které
" e fektní " ,
p r o c e sů
p o č í t a čové o
výs tupy
grafiky
téměř
a
ve j de
s ta t i cké
s chéma zapo j ení v r o zvodně potrubního
hos p odář s tví
Do tě chto zákl adn í ch " s ta t i ckých " - 9 -
výs tupů
se
v r o zvodně
pak s
promítaj í
bar evným
změny ,
vyj ádřením
např . t ě ch
p ř e pnut í
čás t í ,
r o zvaděčů
které
j s ou
pod
nap ě t ím apod .
Obr . 1 . 2 . 1 3 Kromě
uve dených
apl ikací
je
a
bude
těžiště
ap l ikací
p o č í t a čové grafiky př edevš ím v te chni ckých aplika c í ch , kdy půj de ze j ména o p o dporu kons truk čních pra cí .
Takové s y s témy ( ně kdy též
nazývané CAD sys témy ) v š ak neobs ahuj í j en p r o s t ř e dky p o č í t a čové gr afiky ,
kte r é mus e j í být z te chni ckého hl e di s ka ve lmi výkonné ,
a l e mus e j í t é ž o b s ahovat čás t i pro práci s r o z s áhlými dat abázemi a vazbu
na
p ř ipravuj í
v l as tní " na
míru "
p ř ípravu
výr oby .
ur či té
apl ikace ,
použ i t í v automobilovém ,
Tyto
s y s t é my ,
doznaly
asi
které
se
ne j vě t š ího
l e t e ckém a loďař ském průmy s lu .
Dal š í oblas t í aplikace počít ačové grafiky j e obl a s t s y s t émů usnadňuj í c í ch publ ikační činno s t . Jednoduš š í s y s t émy s e nazývaj í textovými p r o c e s ory ,
resp .
WP systémy ( Word Pro c e s s or Sys t ems ) ,
me z i které l z e zařadit WordPerfe c t ,
Chi-Wr iter apod .
Tato tř ída
sys témů j e ur čena pro p s aní r o z s ahem malých pub l ika c í . typu
DTP
s y s t émy
k usnadnění
( Desk
č inno s t í
Top
nutných
Publ i shing
Systems )
k
r o z s áhlých
vydávání
kte r é maj í být t i š těny v kvalitě kni žního t i sku . lze
z ahrnout
sys tém VENTURA ,
resp .
TEX .
Obě
Sys témy
j s ou
u r čeny
pub l ika c í ,
Do t é t o tř í dy
t ř í dy
dne s
ve lmi
us poko j ivě ř e š í probl emat iku práce pouze s če rnobí l ými obrázky . Jistě
nepo s l e dní
oblas t í
ap l ikace
nads t avby p r o oper ační systémy , umo žňuj í
uživate l i
sys témy umo žňuj í ,
" př í j emnou "
p o č í ta čové
grafiky
či j iné programové c e lky , komunikac i
se
sys t émem .
aby i bě žný uživate l výp o č e tní - 10 -
j s ou které Tyto
t e chniky mohl
tuto
te chn iku
př íklad
využívat
uve ďme
p o č í t a čů Ve použi t o
a l e s poň
ř ady
v š e ch
ve lmi
ATAR I , výš e
barev
k
pravděpodobně
prostředí
resp .
získání
dimenzí ,
své
J ako
p ř e devš ím
ze
sys t émů
p o č í t a čové
žádaného
která
p r o fe s i .
známé
známý
ap l ika c í ch
výs l e dného
ve
GEM ,
O S - She l l
uve dených
novou
efektivně
typu
grafiky
je
Barva
je
v j emu .
vs tupuj e
od
do
oblasti
v i zua l i z a c e dat . U
v š e ch
pos tup
s tá l e
sys témů
a
zcela
j asný
s chopno s t a poskytovaná p a l e t a barev j e s tále v ě t š í .
U některých
u
l a s e r ových
v š ak vždy ome zen p o č e t t zv . proto
nutné
barev
v
ne j en
p o č í t a čové
nebo
v j em
skute čný
boha t é
po chopit
některé
grafi ce ,
počet
p a l e ty
barev
inkous tových
t i skáren
bude
základních bar ev na ur č i tý p o če t . ale
mí chání a s p e c iálním te chnikám , z í skal
bar e v ,
je
r o z l i š ov a c í
např .
využívání
zař ízení
p ř i čemž
zař í zení ,
č a s tě j š ího
per iferních
i
zákl adní
pr inc ipy
porozumě t
barev n a výs l e dném
poskytovaný
- 11 -
zař í zením
použ i t í
p r in c ipům
které umožňuj í , je
Je
j e j i ch
aby p o z o r ovate l obrázku , velmi
i
když
ome z ený .
2.
Graf i cká z a ř ízení
Grafi cká p r in cipů .
zař ízení
Pro
lze
výklad
rozdě l i t
algor itmů
je
podle
mnoha
vhodné
h l e d i s ek
r o zdě l i t
či
g r afi cká
zař í zení t akto : vektorová ( pamě ťové obrazovky )
{
g r af i cká zař ízení
Vektorová zatímco
r as t r ová
interpo l a c i . zobr azovaná
{
ras t r ová
grafi cká Z
s př ímým p ř í s tupem k bodu ( monitory apod . )
zař í zení
využívaj í
grafi cká
zařízení
toho
čára
s e s ekven čním p ř í s tupem k b o du ( zapi s ovače apod . )
vyplývá ,
p r o cházet
že
i
u
mimo
hus tota j e ur čena c i t l ivos t í např .
analogové
inte r po l a c e ,
využ ívaj í
vektorových
č í s l i c ovou
zař í ze n í
uzlové. body
mř í žky ,
může j e j íž
DIA převodníků .
2 . 1 V stupní z a ř í zení
Zař í zení pro podle
různých
snímání grafi cké
hledisek,
magn e to s t r ik čního , me chani ckého
např .
informace mohou být
atd . ) ,
přesno s t i ,
p r in c ipu
( kapa c i tního ,
magn e t i ckého ,
odpor ového ,
podle
indukčního ,
č l eněna
v e l iko s t i
snímané
p l o chy
apod .
U z a ř ízení s ve lkou pře snos t í nebo v e l iko s t í p r a covní p l o chy s e použ ívá posuv
které
i sys témů ,
dílů,
me chani ckých
ur č oval
rychl o s t ,
směr
a
j s ou
vybaveny
které
umožňuj í ,
smys l
pohybu
s e rvome chani s my a
aby
operátor
nemus e l
pro
p ouze
p ř e konávat
tření a momenty s e t rvačno s t i . Zvukové pero
Zvukové p ř e s no s t i
pero
je
poměrně
( až 0 , 1 mm )
pře sné
zař í z ení ,
a pra covní ploše
snímání s ouř adni c j ak v rovině ,
kte r é
při
1 x l , 5m )
( až
tak i v pro s to r u ,
viz
dobré
umožňuj e [ 44 ] .
Je
založeno na m ě ř e n í času, k t e r ý up lyne , než vygener ovaný zvukový impul s
(z
důvodů
s trmé
náběhové
dos áhne
membrány
Vzhl e dem
k
p ř e s no s t
i v nekl ima t izovaných
např .
tomu ,
l ineárního že
hr any
se
použ ívá
mikrofonu ,
v některých
apl ikac í ch
pros torách ,
viz je je
o br . 2 . 1 . 1 . a . nutné nutné
r e dundantní mikr ofony k automat i cké kalibr a c i . - 12 -
u l t r azvuk ) dodr ž e t používat
300 V
o -l---t '�
Y SlOl>
VZ;!/2Zd7ZZ77/lZZZZZ7VZ7/1
I
E /ll"
J •
c. s
X STOP
T
SIA'll.1 'I.,Y
'+--11- ---__
pp
-
MF
-
E
pracovní plu,ch" mylarovft fúlie
pokovená
-
druhá
elektruda
mikrofonu ZX, ZY z
-
-
zdroj
zl!silovačr. SOOO V
Princip zvukového pera Obr . 2 . 1 . 1 . a
:.-'-".J,;:; 1:
, c.t'.J
..
,
. . ,. " i I, " ,; ';�' I",
�" " '/
-;:-::4i!:�;:;::�
Zvukové p e r o firmy S c ience Ac c e s s o r i e s Corp . Obr . 2 . 1 . 1 . b
- 1, 3 -
------- -------
--
I
když
n e j j e dnoduš š í
s ouřadn i c
v
zvukové
p r o s toru
or togonálních
os ,
sníma če
uspoř ádání
je
z
mnoha
--------"-- ----
používaly
l ineárn í ch
důvodů
k
o dmě ř ování
mikrofonů
výhodně j š í
do
použ i t í
tří č tyř
l ineárních mikr ofonů uspořádaných v r ovině na kr a j í ch s n íma c í p l o chy , v i z obr . 2 . 1 . 2 . a . z pozice zvukového pera
( x o,Yo, zO )
A x
y
B
Obr . 2 . 1 . 1 . a Z obr . 2 . 1 . 2 . a vyplývá ,
že
z
2 + ( a a
z
2 + ( a - x )2 a a
+
xa ) 2
=
d
2 1
d
2 2
p ř i čemž ( X ' Y , z ) j s ou s ouřadnice mě ř ené p o z i c e . a a a Vyj ádř íme - l i d
i
- d
�
,
pak - z
=
a t e dy
- 14 -
2 2 - ( a - x ) a a
=
3SPACE- DIGITIZER
3D ultr azvukové pero Obr . 2 . 1 . 2 . b Analogi cky l z e p r o s ouřadn i c i y p s á t
Nyní
je
n e z bytné
ur č i t
souř adnici
neboť p l a t í Z
2 o
+
( a
+
X
Z
2 o
+
( b
+
y
P ak Z
2 o
=
Uve dené
2 ( d1
[
v z t ahy
+
d
2 2
o
)
o ) +
d
2
=
2
2 3
nej enže
+
Z
o
z
j e dno t l ivých
d
2 1
Z
2 2 + ( a - X ) o o
d
2 3
Z
2 2 + ( b - Y ) o O
d
2 2 ) - 2 ( X 4 o
poskytuj í
+
y
2 o
možnos t i
+
a
2
+
b
p ř e s ného
2
rovn i c ,
=
d
2 2
d
2 4
) ] / 4 výp o č tu
polohy bodu ( x , y , z ) , ale nav í c umožňuj í kon t r o lu namě ř e ný ch o o O hodnot a p ř ípadnou kal ibraci zař ízení . Vzhl edem k t omu , ž e s e v s ouč asných zař í zeních použ ívaj í mikrop r o c e s ory ,
není výp o č e t
uve dených
p ř ípadě ,
vztahů n i j ak problemat i cký , - 15 -
a
to
i
v
kdy
l ineární
mikrofony
j s ou
umí s t ěny
p ak
j s ou v
nahr azeny
r o z í ch
byl o vyvinuto v Lincoln Lab . obrazovky
d i s p l aye .
Na
sníma c í
bodovými
mikrof ony ,
oblas t i .
Takové
které
z a ř í zení
a mikrofony byly umí s t ěny v r o z í ch
obr . 2 . 1 . 1 . b
je
pak
a p l ika c e
zvukového
p e r a p r o 3D apl ikace . Rand-tab l e t
Tato z a ř í zení , obvykle
která s e t é ž někdy nazývaj í digi t i z é ry ,
zalo žena
na
kapacitním,
magn e t o s t r ikčním
a e l ektr omagne t i cko- indukčním prin c ipu . Někte r á z a ř í z en í , MAX
firmy
volno s t i ,
Terminal
D i s p l ay
Sys tems
Ltd . ,
j s ou
nabí z e j í
i
např .
6 s tupňů
neboť umo žňuj í ode č í tat ne j en s ouřadn i c e x a y ,
ale
i náklon ve s m ě r u osy x , y a též poo točení ukazovátka a t l ak , kte rým n a n ě j operátor působí . Z a ř ízení
zalo žené
na
kapac i tním
pr inc ipu
obr . 2 . 1 . 3 .
kapacitní p r in c ip Obr . 2 . 1 . 3 - 16 -
je
zobrazeno
na
Pracovní
pl o cha
je
zho tovena
z
tenké
nan e s eny e l ektr i cky vodivé obraz ce .
fólie ,
na
k t e r ou
j s ou
Na j e dné s tr aně j e s ous t ava
vodičů r ovnobě žných s o s ou x, na s t r aně druhé j e pak s ous t ava vodičů r ovno bě žných s o s ou y . Nad těmito s ou s t avami s e pohybuj e č id l o ,
kte r é
vod i č ů ,
které
kapa c i tně j s ou
impu l s ů z č í t a čů .
př ij ímá
př i po j eny
př e s
impulsy
od
s ouřadn i cových
kódovací
zařízení
na
zdroj
K e kódování s e používá v ě t š inou Gr ayův kód .
Na plo š e 30x30 cm l z e dos áhnout r o z l i š ení a s i 1 0 2 4xl0 2 4 bodů . Pr inc ip magnetostr ikce , který j e pou�íván u s níma č ů , je ukázán na obr . 2 . 1 . 4 a byl používán př edevš ím u ul t r azvukových magne tos t r ikčn í ch
l inek .
Princip
je
založen
me chani cké deforma c i magne t i ckého mat e r iálu, magne t i ckým po lem .
Je-li do l evé cívky vys l án pr oudový impu l s ,
pod é l drátu rychl o s t í a s i 5 km/ s a v mís t e ch , průchodu změna
která
se
deformační
pr o cháze j í c ího
vlny drátu
sníma cí
impul s .
okol ím změnu
c ívkou ,
Hodnota
pe rmanentního indukce č ímž
př í s lušné
je
magn e tu
magne t i ckého na
c ív c e
s ouřadn i c e
dobou m e z i vys l áním impulsu a j eho detekc í .
šíří
j im i ž pr o cház í ,
př e chodnou změnu okamžité hodno ty pe rmeabi l i ty .
perme abi l i ty
napě ť ový
pružné
kte r á j e vyv o l ána
v zn iká me chani cká deformace magneti ckého drátu , z půs o buj e
na
je
Při
vyvo l á toku
indukován pak
ur čena
U t ě chto z a ř í zení
lze dos áhnout př i pr acovní pl oše 1x1 ,S m př e snos t i a s i 0,1 mm.
P r in c i p magne tos t r ikce Obr . 2 . 1 . 4
- 17 -
Odčítání
s
větší
přesností
( až
0, 0 2 mm ) je umožněno e lektr omagnet icko- indukčním pr inc ipem . Ve snímacím zařízení je umístěna kruhová cívka a v pracovní ploše jsou pak umístěna čtyři meandrová vedení s konstantní roztečí. Pro každou souřadnici jsou dvě meandrová vedení a ta jsou navzájem posunuta o čtvrtinu rozteče, viz obr. 2 .1.5. Cívka ve snímači je obvykle buzena střídavým proudem se sinusovým průběhem a měří se indukovaná napětí v soustavě meandrových vinutí. Měření změny souřadnice v rámci jedné rozteče se "1>rovádí analogově, počet roztečí, o něž se snímací zařízení posune, je registrován obousměrnými čítači .
r--, I I
r-'"
- --
__
I I
I 1
0'''
I I
I I 1
I
.1.
-I-
I I I I L _...J
I
r-'" I I I
r- ' I I I I I 1
I I I -Il- -r I I I I 1 I I I L_.J L_.J
-l-
1
I -, 1 I
1
- -,
I L_...J
I
-1I
I 1 I L_.J
Ur1
el.mag- indukční princip Obr. 2 .1. 5 - 18 -
I I 1
�9f
koule fototranzistor disk válec
Myš mechanická Obr. 2 . 1 . 6. a
tlačítka
zrcadlo fotodetektor čočky
LED
Myš optoelektronická Obr . 2 . 1 . 6. b - 19 -
Myš
Toto zařízení, které je založeno buď na mechani ckém , nebo optoe l ektr ickém principu, se používá zejmé na ve spojení s osobními počítači a umožňuje rychlou komunikaci operátora s výpočetním systé mem. Pohyb myši je přenášen na obrazovku a slouží především k ovládání polohy kurzoru na obrazovce . U mechanické ho principu se pohyb myši převádí na odvalování mechanické kuličky, jejíž otáčení se pomocí mechanického převodu rozkládá do dvou kolmých směrů. Tento pohyb se pak registruje pomocí čítačů, viz obr . 2 .1 . 6. U optoelektrického principu se používá pro každou souřadnou osu zdroj světla a optické čidlo, které registruje, zda byl či nebyl paprsek, který se odráží od speciální podložky, přerušen. Přerušení je způsobeno barevnou mřížkou, pro jeden směr je použita vždy jedna barva. Zdroje světla vyzařují nebo čidla registrují jen určitou vlnovou délku, která je opět jiná pro každý směr, viz obr. 2 . 1 . 6 . a. Kulový ovladač
Na podobné m mechanické m principu j�ko mechanická myš je řešen i kulový ovladač . Jde vlastně o obrácenou myš vzhůru dnem, viz obb. 2 .1.7 . Operátor pak ovládá přímo pohyb koule, zatímco zařízení polohu nemění. U některých systé mů bývají místo kulové ho ovladače použity dva potenciometry s osami na sebe kolmými.
- 20 -
Pákový ovla dač
Pákový ovladač je velmi rozšířeným zařízením zejména u domácích počítačů. Jde o zařízení, které převádí výchylku do jednotlivých směrů buď na analogový signál, který je úměrný výchylce v daném směru, nebo na impuls, pokud vychýlení je takové, že dojde k sepnutí koncových spínačů. Některé typy umoznu]1 pootočením osy páčky ovladače zadávání třetí souřadnice. Pákové ho ovladače se s výhodou používá k nastavení počáteční polohy u některých zapisovačů a grafických displayů. K masovému rozšíření pak došlo zejména ve spojení s domácími počítači a herními automaty . Světelné pero
Kromě výše uvedených zařízení se k určení pozice na obrazovce používá té ž světelné pero, které pracuje na optické m principu. Optický detektor, který je buď přímo v ukazovátku, nebo mimo něj s přívodem optické informace pomocí optického vlákna, převádí optický záblesk, který vzniká při opětovné aktivaci světelného bodu na obrazovce, na signál, z něhož se odvodí pozice snímané ho bodu. Kromě vlastního optické ho snímače má světelné pero spínač oznamující platnost výběru. Spínač může být řešen mechanickým nebo kapacitním způsobem. Nevýhodou světelného pera je menší přesnost, zakrytí žádané pozice vlastním perem a v neposlední řadě i únava ruky operátora při delší práci. Zař í zení pro vs tup obrazové informace
Zařízení pro vstup obrazové informace .je většinou tvořeno kamerou, resp. videopřehrávačem, a převodníkem, který převádí analogový video signál na číslicovou formu vhodnou k dalšímu zpracování na počítači, viz obr. 2 .1.8. Rozvoj prvků CCD podstatně zjednodušil tento typ zařízení, při zvětšení rozlišovací schopnosti ( 6 60 x 480 bodů s 2 4 bity pro odlišení
barvy na jeden bod ) . Tato zařízení slouží především v oblasti zpracování obrazových dat v aplikacích, kdy musí docházet k složitému zpracování obrazové informace, např. v oblasti nasazení robotů, dálkové ho průzkumu Země, optického čtení písma a jeho následné ho rozpoznávání apod.
- 21 -
Kamera připojená k PC-38 6 firmy Digithurst Ltd. Obr. 2 . 1 . 8 Podobného principu využívají i tzv. scannery , viz obr. 2 . 1 . 9 . V tomto případě se dosahuje vyšší hustoty snímaných bodů ( až 8 00 dpi, resp. 7 . 7 bodů/mm ) i při velkých formátech snímaných dokumentů, a to až formátu AD. Nejčastěji se používají formáty A4 / A3, kdy při hustotě 400 dpi může být nasnímáno teoreticky až 1 6 miliónů barev, např. scanner FS1 - S firmy RICOH. Pro reprezentaci barev se používá RGB systé m s tím, že signál odvozený od každé základní barvy může mít až 2 5 6 úrovní. Pro každou základní barvu jsou pak ve scanneru použity oddělené snímací prvky CCD. Nezbytnou částí systémů používající scannery je pak programové vybavení zajišťující převod nasnímaných informací z rastrové ho do vektorového tvaru�
- 22 -
S canner formátu AO firmy INTERGRAPH Obr . 2 . 1 . 9
S c anner formátu A4 firmy Panason i c Obr . 2 . 1 . 10
- 23 -
2 . 2 Výstupní z a ř í zení
Výs tupní gr afi cká zařízení p r in c ipu ,
p ř e s no s t i
p l o chy ,
rychl o s t i
opakovatelno s t i
výs tupní ch typu ,
a
i
grafi ckých
kdy ž
vektor ov á ,
se
např .
z
lze opě t d ě l i t d o s kupin p o d l e kr e s l ení ,
kr e s by
zaří zení
vně j š ího
ve l iko s t i
apod .
je
ve
hlediska
kr e s l i c í
Př evážná
své
podstatě
uži va t e l e
vě t š ina r a s t r ového
chova j í
j ako
kr e s l i c í s toly, neboť v e l iko s t fyz i ckého kr oku
j e uživate l em nepo zorovate lná . Ti skárny
Ne j č a s t ě j i a s tá l e
je
používaným
t i skárna .
V
zař í zením
počát c í ch
pro
grafi cký
rozvo j e
výs tup
p o č í ta čové
by l a
g r a f iky
byly k d i s po z i c i pouze tiskárny alfanume r i cké , které umo žňovaly tisk j en j e dnoduchých gr afů a tabulek . výs tupní ch
zař ízení
způsobi l a ,
že
I když p o t ř e b a r y chlých byly
tiskárny ,
výs tup grafi ckých informa c í byl
Teprve
velkým
umo žn i l r o zv o j
s
výr o bu t iskáren
v mas ovém
pokrokem ve lkých s
v
měří tku
začaly
l a s e r ové
s t á l e ve lmi
ome zen .
polovodičové
pamě tí
mo žno s t í
vyvinuty
za
t e chno l o gi i ,
p ř i j a t e lnou
grafi ckého výs tupu . používat
t zv�
c enu ,
který nas tal
J ako první
mozaikové
se
t i skárny ,
které umo žňovaly tisk alfanumer i ckých znaků v r a s tru 8 x 8 nebo 2 4 x 2 4 bodů a výs tup grafi ckých informací . Elekt r o s t a t i cké t i skárny
E l ektro s ta t i cké
tiskárny j s ou ti skárny ,
j e j i chž r o zv o j
s p j at p ř e devš ím s r ozvo j em integrace pamě t í .
je
Tyt o t i s kárny l z e
v zásadě r o z d ě l i t takto :
e l ektr os t a t i cké t i s kárny
{
suchý proces mokrý proces
{ {
l a s e rové - typ XEROX termografi cké inkous tové t is kárny typ CO STAR
J i s tou nevýhodou vš e ch e l ektr os tati ckých výstupní ch zař í zení j e nutno s t
vytvoření
výs tup
na
pamě ť
vlas tního
fyz i cké
binárního médium , zař í zení
obr azu
což nebo
v
klade
pamě t i ve lké
systému .
- 24 -
a
j eho
nároky V
nás l e dný
z e j ména
př ípadě ,
že
na je
využívána
p amě ť
s y s t ému ,
kl adou
se
též
přenos ovou c e s tu ze sys tému do zařízení . má r ozměr
8 19 2 x 8 19 2
bodů ,
dos áhnout
p ř i j ate lné
kvality
což není
ve lké
Uvážíme - l i ,
příliš
výs tupu ,
nár oky
pak
že obraz chceme - l i
mnoho , je
na
nutná
pam ě ť
o kap a c i t ě 8 MB . Někdy s e pod poj mem e l ektros tatické tiskárny o značuj í pouze e l ekt r o s t a t i cké procesu ) ,
tiskárny
které
maJ l
( ať
už založené
záznamovou
hlavu
na
suchém
( vě t š inou
či
mokr ém
uspoř ádanou
j ako ř adu e l ektrod ) , kte rá nabí j í dané médium . Laserové t i skárny
J s ou založeny na obdobném pr inc ipu j ako r o zmn o žov a c í s tr o j e typu
X e r ox ,
osvě t luj e .
kdy
se
s e l énový
Osvě t l ené
čás ti
vále c se
pomo c í
s t anou
l a s e r ového
e l ektr i cky
papr sku
v o divými
a
j e j i ch nábo j s e odvede p ř e s kovové čás t i .
Na tyto č á s t i s e pak
př i chyt í
kl adně
kte r é
se
záporně
nabitý
poté
mus í
s tabil izovat .
nabité
barvivo
papír .
Současné
( toner ) ,
Barvivo
l a s e r ové
se
t iskárny
6 0 0 bOdů / p a l e c ( dpi-dot per inch ) .
dos ahuj í
p ř ená š í
tepelně
hus toty
vyrcvnávac/ P()n»t
oIeIcode'r
nab/jec(
e/l. IttrodQ
barvícl'
+
P r in c ip las er ové tiskárny Obr . 2 . 2 . 1 - 25 -
až
P r in c ip l a s e r ové t i s kárny j e
znázorněn na o br . 2 . 2 . 1.
p'osék
na
Ti skárny se z áznamovou h lavou
Tyt o
t is kárny
nabí j ení
média v
p r in c i p
pro
maj í
záznamovou
j e dno t l ivých bode ch .
v í ce barevný
tisk
s
hlavu, Na
se
n e z ap éká ,
ale
použitá
vývoj ka
obr . 2 . 2 . 2
použi t ím
T iskárny mohou používat buď mokrý p r o c e s s
kte r á
umo žňuj e je
suchého
ukáz án
procesu .
( typ CO STAR - barvivo
barvivem
se
mus í
odsát
a papír o s u š i t ) , nebo suchý . U tohoto typu t i skáren se v ě t š inou používá
role
papíru .
Typ i ckým
p r o c e s e m j e firma VERSATEC,
výrobcem
t i skárny
se
suchým
zatímco tiskárnu s mokr ým p r o c e s e m
vyrábí ARI TMA p o d označením E C 7 1 40 .
role s papírem
M
B
y
toner el.stat. nabíjení
P r in c ip v í c e bar evné tiskárny používaný firmou VERSATEC Obr . 2 . 2 . 2
- 26 -
Termografické t i skárny
Jde o p ě t o e lekt r o s t a t i ckou ti skárnou s e záznamovou hl avou s
t ím
r o z d í l em ,
spe ciální
že
l átky ,
papír
která
vzniká p f i nabíj ení , teplem
p f en á š í
p f e t i sku . hus toty
na
Napf . 300
dither ingu
buď
bílý
a
mění
papír , 7
do c í l i t
nebo
barvu
pokryt
účinkem
bar evného
p r l cemž
firmy
používaj í
j e mo žné
napuš těn
nebo v p f ípadě
t i s kárny
dpi
je
Shinko
t ep l a ,
t is ku
Pfi barev .
barva
bar evného
Co .
použi t í
které
se
využívá
Electric
barev .
až 4 0 9 6
se
v r s tvou
dos ahuj í
vzorů
Ry chl o s t
nebo
t i s ku
je
as i 9 0 s e c p r o formát A4 . Kapacita použité vnitfní p amě t i j e až 6 MB . Inkous tové t i skárny
Inkous tové
t i s kárny l z e rozdě l i t na
dvě
základní
s kup iny ,
a to : - s e s tá l ým papr skem - proud malých kap i ček ( typi cky 5 0 O DD/ s ) buď
dopadne
na
papír ,
nebo
je
odkloněn
pomo c í
e l ekro s ta t i ckéko náboj e , -
kapi čky
j s ou
vys tf ikovány
na
základě
požadavku
ve
vhodný
č a s ový okamžik . Princip
inkous t ové
poznamena t ,
že
tfí
je
na
t i skárny obvykl e maj í
ekonomi č tě j š ího s lo žením
tiskárny
provozu ,
barev .
i kdy ž j e
Tímto
obr . 2 . 2 . 3 . i
černou barvu
možné
způs obem
Je
se
černé
vhodné z
barvy
nav í c
důvodů do c í l i t
do c í l í
lepší
sytos t i č e rné barvy . Kre s l i c í stoly
Kr e s l i c í větš í ,
s toly
maj í
větš inou
tvar
de sky
formátu
AD n e bo
p f i čemž vzhledem k požadované p f e s no s t i kr e s by
0 , 0 1 mm
j e nutná poměrně r o bus tní me chani cká kons truk c e ,
c o ž způs o buj e
pomal e j š í
kr e s bu
s e trvačnos t i .
Typ i ckým
p f e d s tavi t e l em
zaf í z ení
se
z
důvodu
používaj í
s
zvě tš ených
je
napf .
různými
momentů
D I G IGRAF 1 2 0 8 - 4G .
te chno logi ckými
Tato
hl avami
vytváf ení různých p f e dl oh , napf . mas ek integrovaných obvodů .
- 27 -
pro
�
WASTE INK RESERVOIR
INK RECEPTOR INK N
LI.
(I) P. � O P. �
�( I (1),
O t1 I"i N 00
N N w Pl
DURAPULSE
INK SENSOR PCS
INK-JET HEAD
PERISTALTIC INK PUMPS
tll n ::T (1), a Pl
�. ."
SECONDARY RESERVOIR
l '-'IJ. 1>c:=:ot
f-'. � � O � tll rt O < (1),
SUS RESERVOIR
ASTE INK RETURN
rt f-'. tll � Pl'
�I
y.'(
L--W IPER MOTOR
JET DRIVER PCS
CPU PCS
PURGE SWITCH
Inkous tová tiskárna pro tisk ve lkých formátů
=== � -�
=== X 'f f\OIIE/t
_
DX Y- 980 A
\
Osmibar evný zap i s ovač pro Obr . 2 . 2 . 4 - 29 -
Ctrná c t ibar evný zap i s ovač formátu A l firmy Hous on I n s t ruments Obr . 2 . 2 . 5
Zap i sovače
Z ap i s ovače vyzna čuj e
tvo ř í
p ř e devš ím
o zař ízení
se
třídu
výs tupních
ve lkou
s ekvenčním
rychl o s t í
přís tupem
k
kr e s l eného mot ivu a dobré p ř e snos ti .
kr e s l ení bodu )
původně
pos tupně
interpolátor ,
vybavovány n e j en
avš ak
ve lké
s
První zapisovače
r o zvo j em
interpolátory ,
ale
int e g r a c e
nebo
podobu ,
" zmenš ených "
kr e s l í c í ch
obr . 2 . 2 . 4 ( ROLAND ,
dne s
maj í
s tolů
na
dvo j í formát
byly
i mikrop r o c e s ory
např .
Z a p i s ovače
ploše
Tato zař í z e n í j s ou vhodná
zaj i š ťuj í c ími komunika c i na vyš š í drovn i , HPGL .
se ( j de
vektorů
při
pro v ě t š inu výs tupů v te chni ckých apl ika c í ch . nemě ly
která
zař í z en í ,
A3
v
j azy c e
BGL
a
to
buď
A4,
viz
nebo
COLORGRAF-ARI TMA ) , n e bo vál cových z ap i s ovačů
s pap í r ovou r o l í s e š ířkou až 2 m , viz obr . 2 . 2 . 5 ( Ca l Comp ) .
- 30 -
D i splaye s paměťovou obrazovkou
s
D i s p l ay vektorového vytvářena v ě t š inou
pamě ťovou
typu ,
t ak ,
že
ros toucí
na
obrazovka ,
vlas tně
před
neus tále
mě la
to ,
obraz
že
v
d i s p l ayů
byl a
s t ínítku
pak
a
po
j e ž byl a na ní zobrazena . která umo žňuj e ,
luminoforem o bnovován .
př ípadě
s mazán
Pap r s ek
s chopno s t
se na
Tento
př ivádí s t ín í tku
opr avy
znovu
firma
dobu
z aznamenaný
nábo j e m ,
obrazovek
překr e s l en . V
mot ivu
Typ i ckým s oučasné
mus e l
být
výr o b ce m době
se
p am ě ť ové
Interface to host computer
��
t
(Interaction data)
.. "
I
Display processor
1
Keyboard
S chemat i cké uspořádání displaye s pamě ť ovou obrazovkou Obr . 2 . 2 . 6 - 31 -
celý
t ě chto
pam ě t í a j e j í kapac i ty .
I
byl
umo žňoval
obr azovky nepoužívaj í vzhle dem k prudce k l e s a j í c í poměru
(Display commands)
byl a
kte r é měly j e dinou nevýhodu ,
kres leného
TEKTRONIX .
dl ouhou
aby obr a z ,
typ
je
Využívala k t omu
e l ektr o s t a t i ckým
vyr ábě t l a c iné grafi cké displaye , a
na
s oustavu p ap r sku
napě tí .
která
s e kundární emis i , mř í žc e
zobrazovaná
z a ř í zením
k
patří
V době , kdy cena pamě t í byl a ve lmi vys oká ,
zachovat informa c i , t zv .
ús e čka
na vy chylovací
l ine árně
zobr a z í ú s e čku . vyvinuta
kdy
obrazovkou
ceny
D i splaye s obnovovaným obr azem
Rozv o j p o žadavky vývoj
a
e lektroniky kl adenými
nás l e dnou
obrazem .
Tato
neus t á l ého d i s p l ay
a
na
výrobu
zař í zení
s ouboru,
pamě t í ,
výs tupní
grafi ckých
vlas tně obr azu
který
též
ceny
grafi cká
o bnovování
a umo žňoval
pokl e s
zákl adní
z a l o žena
základě
repre zentoval operace
s
zaří zení ,
d i s p l ayů
byl a
na
s p o lu s
novými
způ s o b i ly o bnovovaným
na
p r inc ipu
inte r p r e t a c e
zobr azovanou vkl ádání ,
t zv .
informac i
rušení
apo d .
Zař ízení založená na tomto pr inc ipu byl a použi t a i v grafi ckém s y s t é mu možné
SM 5 2 / 11- I SAP .
čás t
označením
obr azu
Výhodou
vymazat
p ř í s lušných
dat
tě chto
pouhým a
d i s p l ayů
zrušením
př íkazů
v
je
nebo
tzv .
to ,
že
s p e c i álním
d i s p l ay
s ouboru,
který j e uložen v lokální pamě ti displaye .
Interface to host computer
I
(Display commands)
t
( Interaction data)
+
I
Display
MOVE
prdcessor
10
15
L INE
100 25
CRT
CHAR LU CY L INE
Refresh buffer memory Alphanumeric keyboard
Data tablet
S chema t i cké uspoř ádání displaye s obnovovaným obrazem Obr . 2 . 2 . 7 - 32 -
je
Ra s tr ové di splaye
J e dn ím grafi cký
z
nej častěj i
d i s p l ay
používaných
ras tr ového
typu .
grafi ckých
Tato
založena na zobrazování čás ti pamě t i ,
zař í zení
zař ízení
j s ou
je
vesměs
která se nazývá v ě t š inou
vide o-pamě ť nebo frame-buffer . • • •
• • •
•
•
•
•
•
•
•
•
Obr . 2 . 2 . B Na
obr . 2 . 2 . B
je
znázorněn
vektor ovém zař ízení , r a s t r ovém
ř adou
nazývaj í p ixe ly .
s j ed inou zobrazování Roz l i šovací
bodů
je
ús e čkou
kte r é
r as tr ového
j ednot l ivých
kr e s l enou
zobr a zuj e obr azu ,
a na
ús e čka
je
zař í zení
e l ementů
čáry ,
na
kte r é
se
Ne j čas tě j i používanou r e a l i z a c í p r o grafi cké
ras tr ového
frame-buffer .
me z i
zařízení ,
li
zař í zení .
aproximována d i s p l aye
tj .
rozdíl
Na
( dále
obr . 2 . 2 . 9
b itovou bodu
typu rovinou
s
j edinou pak
schopno s t í
v
d i s p l aye )
zobrazen
p r in c ip
frame-buffe r u . barvou ,
ro zumíme
zobrazite lných
adre sovate lnos t j e údaj
je
j en
ose x
resp .
Toto
je
d i s p l ay e umo žňuj e
úr ovn í
š edi .
údaj , ' který uvád í , a
v
ose y ,
tzv .
ko l ik
z a t ím c o
o rozměru bitové r oviny ( ne bo b i tových
frame-buffer
1 lI<-+--I---,
registr
1 bitová rovina
převodník
1 bit
stínítko obrazovky
F r ame buffer s j ednou bitovou r ov inou Obr . 2 . 2 . 9 - 33 -
------- --- -
-
a
Roz l i š i telnost
které by nemě ly být zaměňovány .
údaj e ,
j e dnodu cho s t p ř i dr žíme toho , j ako
j s ou
adresovate lnost
zobrazení
r o z s ah
obe cně
dva
rozdí lné
V dal š ím výkladu s e p r o
že r o z s ah frame-bufferu j e s t e j ný
na
obrazovce ,
tj .
r o z l i š i t e lno s t
a adr e s ovatelno s t j s ou s te j né . Pro
adr e s ovatelnost
kons trukté r s kou
1024 x 1024,
prax i ,
která
je
kap a c i tu
do s t áváme
n e z by tná pamě t i
pro 1 Mb .
V ur č itých a p l ikac í ch j e nezbytně nutné mít někol ik úr ovní š e di N , tj . a obvyk l e j e p o č e t úrovní š edi vyj ádřen č í s lem 2 N v r o z s ahu O až 2 - 1 , kde N j e p o č e t bi tových r ov in . P r in c i p takového d i s p l aye j e zobrazen na obr . 2 . 2 . 1 0 .
V daném p ř ípadě s e
b o d na obrazovce zobr azí s úrovní š edi odpovídaj í c í hodno t ě 3 , p ř i čemž
je
mo žné
v
daném
př ípadě
mít
osm
různých
inten z i t
s oučasně na výs tupu .
frame-buffer
1 1
O
W O
1
I I 1
\
DIA 2N 3 bitová rovina
,----
�
----�
�---�----� � � � � --------� � l.---
�
____L---
L---
převodník
( N=3 )
,---'------
\
stínítko obrazovky
2N úrovní
Frame buffer se tř emi bitovými rovinami Obr . 2 . 2 . 1 0 Pro
někt e r é
apl ikace
je
vhodné
mít
více
š e di , ne ž j e aktuální kapacita frame -buffe ru . s e používá j e š tě tabulka ,
možných
úr ovní
V t akovém p ř ípadě
která umo žňuj e překódování a nazývá
se př ekódovac í tabulka ( l ook-up table ) , - 34 -
viz obr . 2 . 2 . 1 1 .
frame-buffer
� 'tl
�
9
9
I
I
registry N bitů
f-
-
O 1 f-
I
I
f-
f-
l---
1
l I-1 1-- t--
1
1
l-
f-
l-
O l-
I--
O
I--
B
I-
f--
I---
-
--::=
�
O
�
G
1
l-
L;;..
R
-
--
O
\I
------
trysky -�
O
DIA
�
DIA
�
zelená
DIA
�
červená
----------�
t:=?�----V -----
modrá
p řevodníky
----
--------L--L--L-L--
/r----
stínítko obrazovky
Frame buffer s př ekódova c í tabulkou Obr .
2. 2. 11
- 35 -
1
Uvedený p r in c i p umo žňuj e snadnou změnu dané úr ovně p ixe lů
na
novou
úroveň
přepisem
o b s ahu
š e di v š e ch
p ř í s lušné
ř ádky
př ekódova c í tabulky m í s to př ekódování v š e ch p ř í s lušných p i x e lů na
novou
hodno tu .
Tabulka
po chopi t e lně
př ípadě r e a l i zována pamě t í typu ROM , J e z ř e j mé ,
nesmí
být
v
tomto
ale pamě t í typu RAM .
že pro ar chitekturu z obr . 2 . 2 . 1 1 bude p l at i t , �
w
že
N
kde W j e p o č e t bitů řádky př ekódova cí tabulky N
je
po č e t
bi tových rovin ,
tj .
poče t
bitů
r e p r e z en tuj í c í
tj .
po č e t ř ádek , mus í p l a t i t
č í s l o zvolené úr ovně š e di Pro dé lku L př ekódovací tabulky ,
Ce lková pamě ť frame - bufferu p r o N
=
8
( tj .
2 5 6 úr ovní
š e di )
p ř i adr e s ovatelno s t i 1 0 2 4 x 1 0 2 4 bodů j e r ovna 1 MB . Zkusme
nyní
výš e
zobrazování barev . každou
barvu .
( če rvená ) ,
uve dené
ar chi tektury
p ouží t
v
př ípadě
Ne j j e dnoduš š í je použít I -b i t ovou r ov inu p r o
Budeme
pracovat
G - green
v
systému
( ze l ená ) ,
RGB ,
B - blue
kde
je
( modrá ) .
R - red Pak
pro
j e dno t l ivé kombinace dos táváme : barva
R
G
B
če rná
O
O
O
modrá
O
O
1
z e l ená
O
1
O
modr o-zel ená
O
1
1
če rvená
1
O
O
purpurová
1
O
1
žlutá
1
1
O
bílá
1
1
1
J e známo ,
že bar evné obrazovky maj í t ř i t rysky ,
základn í
barvu
j ednu .
Ne j j e dnoduš š í
p ř ípad
a t o p r o každou je
zobrazen
na
obr . 2 . 2 . 1 2 . Nyní bi t ových
j e mo žné každé
barvě
r ovin
tak různé
a
získat
přiřadit ne
p ř ípad znázorněný na obr . 2 . 2 . 1 3 .
- 36 -
barevné
j e dnu ,
ale
ods t íny .
něko l ik
Dos t áváme
frame-buffer trysky
registry
R
modrá I---+---+----l l +-+----, o +--f-\---,
zelená červená
převodníky
stínítko obrazovky
F r ame buffer s j e dnou bi tovou r ovinou p r o každou barvu Obr . 2 . 2 . l 2
- 37 -
frame-buffer
�
9
I
I
registry N bittl
I--
ce,
�
9
-
O
I
1 1-
I l-
1
I
t--
I-
t-- .
- r---
I-
I-
O l-
I--
B
,...--
�
O I-
I--
-
I--
s.-
I--
-
-
G
-
�-L
-
I-
�+
R
.------. \ .----------.---�
trysky
DIA DIA
,
f.-
t--
t--
I
. .�
I--
1 1-
I
-J
O
?7* � ------? --- :...V
modrá
�
DIA
----
---
zelená
�L---� --L---L---L----L---
/r---
červená
převodníky
stínítko obrazovky
F r ame buffer s osmi bi tovými rovinami p r o každou barvu O br.2.2.13
- 38 -
l
�
Ch
registry N bitů
frame-b uffer
O
9
1
U O
1\
-
�
Ch
I I
1-
9
�
r--
1
�
1 f-
r--
f-
-
-
O fO f- ff-
'1\
�
B
f-
f-
1
1
-
\11
O
O
O
fR
<E::
�
W
překódovací tabulky
7
,-----
,
t--
�
�
f--
trysky -
-
f--
DIA
červená
DIA
�
zelená
DIA
�
modrá
r-------
------
l------;:r l.-----
�V� � __
�
----
�---VL.---
/�
L,..----
L.--převodníky Obr . 2 . 2 . 1 4
- 39 -
stínítko obrazovky
1024 x
Uváž íme - l i nyní opět adr e s ovatelno s t 8-mi b i tových r ov inách p r o každou barvu ,
1 0 2 4 bodů p ř i
pak do s t áváme kap a c i tu
pamě t i r ovnu *
3 Pro
*
8
zvýš ení
p o č tu
1 0 2 4 = 2 4 Mb = 3 MB
*
1024
dos tupných
př ekódovávací tabulku ,
barev
je
možné
zařadit
opět
č ímž do s t aneme ar chitekturu znázorněnou
na o br . 2 . 2 . 1 4 . Nyní
je
nutné
a r o z l i š i t e lno s t ,
opět
které
poukázat
s e ve lmi
na
poj my
čas to
ztotožňuj í
z e j ména v obla s t i popisu systémů ze zahr ani č í . d i s p l aye
o bvykle
maj í
adr e s ov a t e lno s t a
Dne š n í g r a f i cké
4096 x 40 9 6
adr e s ovatelno s t
z aměňuj í , bodů
při
p a l e ty bodů , p ř i čemž např . z r oz l i š i t e lnos t i 1024 x 1024 24 16 777 216 ( 2 ) barev j e zobrazitelných na obrazovce pouze 512
barev . x
x
To
znamená ,
adre sovate lno s t
se
opravdu zobrazí pokud j e k dispozici odpovídaj í c í moni t o r ,
je
4096
pouze 10 2 4
x
16 7 7 7 2 16 ,
10 2 4
x
roz l i š i telno s t ,
tj .
to ,
je
co
4096
zatímco
že
5 12 .
Z obr . 2 . 2 . 1 4 vyp lývá ,
že paleta barev ,
j e r ovna ( 2
3
)
W
= ( 2
W
)
z kte r é můžeme vyb í r a t ,
3
z a t ím c o p o č e t zobrazite lných barev v daném č a s e na obrazovce j e ( 2
3
)
N
= ( 2
N
)
3
a t e dy p r o př ípad s 2 5 6 barvami dos táváme : p o č e t bitových r ovin pro barvu :
N = 3
p o č e t bitů pro př ekódovac í tabulku :
W
=
8
kap a c i t a pamě t i frame-bufferu P : 4 0 9 6 x 4 0 9 6 x 3 x 3 = 1 44 Mb = 1 8 MB kapac ita př ekódovacích tabul ek T : 2 5 6 x 8 x 3 = 6 1 44 b = 7 6 8 B J e zř e j mé , důvodů ,
ž e j e dno t l ivé bity n e l ze vybírat pos tupně z č a s ových
ale vybírá se vždy skupina bodů
j e okol o 1 0 0 ns ) .
- 40 -
( doba p ř í s tupu pamě t í
D i splaye s tekutými krystaly
D i s p l aye s tekutými krys taly ( L iquid Crys tal D i s p l ay - LCD ) patř í
me z i
dopada j í c í
d i s p l aye , s vě t l o .
měnit
neemi tuj í
Tekuté
or gani ckých mol ekul , možné
které
krys taly
svě t l o , tvo ř í
vlas tně
kte r é maj í tvar tyč inek .
e lekt r i ckým
polem .
Bez
ale
moduluj í v r s tvu
Pol ohu tyč inek j e
e l ekt r i ckého
pole
d o chází
k o t o č ení polarizace světla o 90· , kte ré j e druhým p o l a r i z a čn ím fil trem pole ,
pr opuš těno
p ak ke
a
odr aženo
změně polarizace
zpě t .
Pokud
svě tla nedo cház í
druhým p o l a r i z a čním fil trem pr opuš těno , odraženo zpě t . vytvo ř i t
prvek ,
půs obí a
e l ektr i cké svě t l o není
a tedy nemůže
být ani
Ve spoj ení s polari začním f i l t r em j e p ak možné který
buď
propouš t í
svě t l o ,
či
obr . 2 . 2 . 1 5 . WITHOUT CURRENT I N E RT lIOU I O C RYSTALS
TWIST LlGHT BY 90·
ACTIVATEO lIOUIO CRYSTALS PREVENT
l I G HT RAYS
LlGHT FROM PASSING THROUGH SECONO POLAR IZER S E G M E N T
P r in c ip LCD displaye Obr . 2 . 2 . 1 5 - 41 -
LEWELL
niko l i v ,
viz
LCD
d i s p l aye
se
i p r opus tných hodine k ,
se
pane lů .
ve
Odr azný
použ ívá
Forma
LAPTOP .
vyráběj í ve
formě
typ ,
spoj ení
pr opus tných
j ak
známý s
panelů
odrazných ,
např .
os obními se
pak
t ak
z digi tální ch po č í t a č i
použ ívá
tř ídy
např .
ve
spoj ení se zpě tnými proj ektory a ty se pak používaj í k výukovým a demons tr a čním ú č e lům . 1 1 00 x 800 firmy
bodů
SONY .
při
Dos ahovaná r o z l i š ovací s chopnos t j e a s i
16
Ne j vě t š ím
úrovn í ch
šedi ,
probl émem
je
např .
viz
r e a l iz a c e
l ap t op
NEWS
bar evných
LCD
d i s p l ayů . Pla smové di splaye
P l asmové malých
d i s p l aye
ne ónových
vypnout dos áhnout
či
zdr o j ů
z apnout 16
j s ou reali zovány
úr ovní
svě t l a .
asi j asu
za
Každý
20 �s .
při
j ako
dvouro změrná p o l e
zdroj
U
svě t l a
tě chto
r o z l i š ení
je
možné
d i s p l ayů
1024 x 7 68
lze
pixe lů .
Princip p l asmových d i s p l ayů j e znázorněn na obr . 2 . 2 . 1 6 .
GLASS
HORIZONTAL ELECTRODES
DIELECTRIC MATERIAL
VERTICAL ELECTRODES
Princip p l asmového disp laye Obr . 2 . 2 . 1 6
- 42 -
LEWELL
Jak p l asmové ,
tak i LCD displaye tvo ř í a l t e rnat ivu k d i s p l ayům
obrazovkovým .
Je
d i s p l aye
budou
se
vš ak
nutné
j eště
p o č ítat dl ouhou
s
t ím ,
dobu
že
o b r az ovkové
používat
z e j ména
v průmy s lu .
'"
High resolution monochrome CRT
Neutral polanzer
Ti
-cell
Color polarizers
LCS switched on: Green fleld I S transmitted
LCS sWltched oft: Red fleld IS transmitted
Princip s ter oskopi ckého d i s p l aye
D i s p l ay SGS / 6 2 5 firmy TEKTRONIX I n c . Obr . 2 . 2 . 1 8 - 43 -
3D di splaye
Až dosud p ř e dkl ádané pr inc ipy zař í zení umo žňovaly zobrazení t ř í r o změrných obj ektů po proj ekci na p r omí t a c í p l o chu , méně zobrazení dvour o změrných útvarů . tř írozměrný ch aplika c í . apod . ,
obj ektů
pouzlva J l
s par abol i ckými bar evnými
vyvinul a zař í zení tuto
fil try s
vj em
vy chází
p ř e dmětem
před
změnu .
Tyto
obrazovek
systémy
apod .
F irma
vibruj í cím
z
j ev
obraz
na
mnoho
myš l �nky ,
je
a
vzad ,
pak
obrazovce )
stoj í
v j em
p o l ar i z a čními
Compute r s
Ten
p ak
Corp .
p o s kytuj e
pros toru .
a
to :
pak
využ it
s p o j ení
z ískat
s
Genis co
třírozměrného
vpř e d
ve
umožňuj í
zr cadlem .
j ednoduché
zr cadlem
pro
z e j ména s imul átory p i lotáže l e tadel
skute čného
Tento
skute čno s t i
nezbytné
Jiné systémy používaj í brýl í
d i s p l ay
oper átorovi
je
proj ekčních
z r cadly .
t ř e t ího r o změru . či
např .
více
Z í s kání s kute čného v j emu
operátorem
Některé systémy ,
tj .
P r i n c ip
p ohybuj eme - l i
pozorov a t e l
tak,
že
vnímá
p ř e dm ě t
a pohybuj e
( ve
se
zr cadlo .
Místo p evného zr cadla s e pak používá pružná membr ána ,
k t e r á má
zr cadlově odráže j í c í povr ch a j e j í pr ohnutí či vydu t í j e ř íz eno p o č ít a č em synchr onně s e zobrazováním obj ektu na obrazov c e . vlas tně
o
zobr azování
pozor ova t e l e v š e chny
v
j e dno t l ivých
j e dnotl ivých
" ř e zy "
časových
zobrazovány
rychl e j i
,
� ř e zů "
smě r em
ús e c í ch .
než
Pokud
za
dos táváme nebl ikaj í c í obr az s e vj emem hloubky .
Jde od j s ou
1 /30 s ,
p ak
Podr obno s t i l z e
nalézt v [ 5 7 ] . J i s tou
náhr adou
s bar evnými nebo SGS ,
d i s p l aye .
Využívá
s p e c iální
filtr
j s ou se
touto z
fil try .
bar evného
obrazovkou . tekutých
p ř i čemž
je
fil try možné
z e l enou v če tně
je
pak
zobr azovat
je
když
Před
pomo c í
ř e š ení
b í l ého
vys okou
je
světla umí s těn
r o z l i š ov a c í
Tento f i l t r umožňuj e ,
vše chny Je
je
mono chr omního
s t ínítkem s
výs ledkem
brýl í
p ř i š l a n a trh s ř adou
anebo z e l ená .
bar evných ods t ínů .
použi tí toto
rozkladu
krys talů
buď propouš t ě l a barva červená, bar evnými
I
r e a l izovány
s chopno s t í a přepínací rychl o s t í . s
systému
firma TEKTRONIX Inc .
které
p r odukovaného
uvedeného
polarizačními
známé dl ouhou dobu, d i s p l ayů
výše
aby s e
P ř i použi t í brýlí
s te r e o s kopi cký
barvy
od
z ř e j mé ,
č e rvené
že
tento
v j em , až
po
sys tém
mus í zobr azovat dvo j i c i s te r e oskopi ckých snímků a l e s poň 30 krát za
sec .
Na obr . 2 . 2 . 18
je
pak ukázán
skute čná podoba . - 44 -
p r in c ip
d i s p l aye
a
j eho
2 . 3 Netradiční vstupní a výstupní z a ř í zení
D ř íve bě žně
uve dená
vyr áběna
vs tupní
a
a
dodáván a ,
výs tupní j s ou
nákl adná nebo j inak nedos tupná . s canne r p r o vě t š í formáty .
v
mnoha
čas to pr ováděna ,
která
př ípade ch
j s ou
f inančně
Typ i ckou ukázkou může být např .
V mnoha apl ika c í ch může být ne zbytné
nasnímat p ř e dl ohy vě t š í než formát A4 . není
zař í z en í ,
Pokud v š ak úl oha s nímání
pak zakoupení s canne ru např .
formátu A l
nebude pr avděpodobně finančně únosné . V tomto př ípadě p ak l z e : - r o z s t ř íhat
snímanou předlohu na
s okr a j i ) vybavení , - zadat
a
zakoup it
nebo
vytvoř i t
A4
(s
p r o b l émy
s p e c i ální
co
p r o g r amové
které tyto čás t i " s l oží " opět do j e dnoho c e lku
tuto
úlohu
firmě ,
kte r á
p ř e dlohy bez j e j ího zni čení . problém
formáty
p ř enosu
nerea l i z ovatelný .
zaj i s t í
nasnímán í
dané
V tomto př ípadě j e nutné ř e š i t
dat ,
neboť
přenos
Pokud
nepouži j eme
pomo c í
te chnik
disket
komp r e s e
je dat ,
pak p r o formát A4 p ř i hus totě 4 0 0 dpi a př i osmi b i t e ch na s l o žky
RGB
je
dat a s i 44 MB ,
nutná kapacita
pamě t i k uložení
n a s n ímaných
p ř i nasnímání formátu AO j e pak j i ž z ap o t ř e b í
a s i 7 0 4 MB . Z uvedeného j e z ř e j mé ,
že úloha vlas tního s e j mutí p ř e d l ohy
formátu A O /A1 nebude tak čas t á , obj emu dat bude
neboť zpra cování odpovídaj í c ího
časově velmi náro čné .
Z toho to důvodu l z e p r o
méně náro čné apl ika ce použít zař ízení , předl ohy
s
tím,
že
např .
se
k t e r é zaj i s t í nasnímání
použij e
p l o t t er ,
na
kterém
v dr žáku pro p e r o upevněna s p e c iální s onda pro snímán í . způsobem l z e nasnímat předlohy s r o z l i š ením šedi .
Ve l iko s t
nasnímaného
formátu
je
1 2 nebo
pak
dána
p ř e dlohy a ve l ikos tí kre s l í c í plo chy plotteru . finančně
nenáro čné
z e j ména
v š ak
a
tam ,
je
plně
kde
je
postačuj í c í nutné
Takovým
1 6 úr ovní v e l ikos t í
Takové ř e š en í j e
pro
občas
je
mnoho
a p l ika c í ,
nasnímat
i
tzv .
prodloužené formáty . Podobným
způs obem
i
možné
je
z p ř e d l oh různého formátu ,
tj .
řešit
problém
s nímání
náhradu snímačů s ouřadn i c ,
pomo c í kláv e s ovládaj í c í ch polohu kur zoru , n i tkový
ENTER
se
kř í ž pak
kryl
p r ovede
se
snímaným
ode č tení - 45 -
kdy
myš i nebo s p e c i ální
kláve s n i c e ur čuj eme po suvy na p l o tteru v obou smě r e ch t ak , se
bodů
bodem . ' S t i s knut ím souřadnic
aby
k l ávesy
nasn ímaného
bodu
( vě t š ina
p l o t terů
je
s chopna
ur čit
s oučasnou
pozici
pera ) .
Kláv e s a ESC pak může ruš it platno s t nasnímaných dat . Dal š ím kte r é
zvláš tním
zař í zením
j e podobné myš i ,
výs tupn í ,
ale
s
je
zař í zení
tím r ozdílem ,
nazývané že
PENMAN ,
o
z a ř í zení
j s ou
umí s t ěny
j de
v i z obr . 2 . 3 . 1 .
r
,
If
' ,-
(
" II ..... II .
'/
,
-
1 1 1 '/ ,
·
I
II
; I
I
1
"
l
:� '"
-, -,
1-
li .: , iI'1
\
, I
1 "
';-.
I
I
,
I d l
I
I
'I
I�
\ 1\'\
, ,
I I
\
I I "
Robo t i c Plotter firmy Z e r i con Obr . 2 . 3 . 1 Zařízení
obsahuj e
dva
v tě žkém kovovém kvádr u , pe r a .
kr okové
mo torky ,
které
na kte rém j s ou umís těna t é ž kr e s l í c í
Z a ř ízení polo žené n a kr e s l í c í p l o š e s e pak p ohybuj e vpřed
nebo v z ad ,
p ř i čemž
j e možné měnit směr pohybu .
Toto
z a ř í zení
vyniká s vo j í j e dnoducho s t í a minimem po žadovaných me chani ckých s oučás tí pro výr o bu p ř i za chování do s t a t e čné p ř e s no s t i kr e s by . - 46 -
Me z i
n e t r ad i ční
techno logické
výs tupní
graf ické
v ě t š iny
zobrazovaných
něko l ik
nume r i ckých
zař ízení které
di splaye ,
prvků ,
úda j ů
symbo lů ( odpo j en o / p ř ipoj eno ,
se
p r l cemž
( napě t í , resp .
lze
počítat
i
vyzna čuj í
s e · v ě t š inou
resp .
průtok )
uzavřen%
tzv .
s tá l o s t í mění
nebo
tevř eno ) .
j en barva
Vzh l e dem
k mal ému p o č tu měn í c í ch s e dat je možné použí t p r o komun ika c i i s é r iové
r ozhr aní ,
neboť
př enos
dat
definuj í c í ch
" po z ad í "
výs l e dného obr azu s e přenáš í j en při ini c ial i za c i . PC video výs tupy
Vzh l e dem zákl adní
k
r ozvo j i
typy
os obních
videoadaptérů
sys témů
( kar e t )
je
a
vhodné
j e j i ch
uvé s t
r o z l i š ov a c í
s chopno s t i : Color
Gr aphi c s
Adapter
640 x 200
CGA
s oučasně zobrazite lných barvá ch ;
bodů
při
dvou
modifika c e umo žňuj í až
1 6 bar ev s oučasně . He r cu l e s
Card - HGC
Gr aphi cs
barvách
pouze
720 x 348
textový
r e žim ;
bodů
při
dvou
modifikace
HGC
P lus
umo žňuj e i grafi cký r e ž im s př ípaqnou vo l bou barev . Enhan c e d Graph i c s Adapter - EGA zobrazite lných
barev
ze
640 x 3 5 0 až
64
možných
(v
16
s oučasně
z áv i s l o s t i
na
konfigur a c i pamě t i kar ty ) . Video
Ar r ay - VGA :
Graph i c s
možných , He r cu l e s
640 x 480
až
16
barev
z
256
nebo 3 2 0 x 4 8 0 při 2 5 6 barvách .
GSC
( Gr aphi cs
Stat ion
Car d )
:
používá
p r o c e s or
3 40 1 0 a umožňuj e p ř i r o z l i š ení 1 0 2 4 x 7 6 8 až 2 5 6 barev . Futur e
Velká 8 5 1 4 /A ,
Adapter - FGA
z p a l e ty
1 6 . 7M;
moni tory ,
nebo
1280 x 1024
adap tér př ekrýt
umožňuj e
výs tupy
až
256
pomo c í
oken
p ř i čemž př ekrytí j e ř e š eno hardwa r ově .
v ě t š ina
dne s
dodávaných
k t e r ý umožňuj e 1 024 x 7 68 j ako
PWGA 1
a
zobr azit který
videokaret
používá
56
2 5 6K
je
barev
též
z
barev
obs luhovat
monitor ,
r o z l i š ení D i g i t al
Graph i c s
vyr áběn
na
dva j e den
procesor
mořných
firmou
při
W e s tern
( Pe r s onal Works tat ion Graphi c s Ar r ay I ) ,
nebo využ ívá novou ar chitekturu T I GA ( Texas Ins t rument Gr aphi c s - 47 -
Ar chite c tur e ) , který j e založen na použ i t í p r o c e s orů ř ady 3 4 0 x O a
který
umo žňuj e
zobrazit
5 6 6M
až
bar ev
při
r o z l i š ení
1 2 8 0 x 1 0 2 4 bodů . Kr omě n e j en
výš e
j e j i ch
uve dených
modifika c í
základních ( Super
VGA
typů
exis tuj e
1024 x 1024
celá
až
256
apod . ) ,
a l e též i kar e t s vyš š ími užitkovými parame try ,
uve deme
j en někt e r é
s chopno s t ,
( údaj e
j s ou uve deny ve
tvaru
1 024 x 7 68
ART I ST 1 PLU S
1024 x 7 68
/
ART I ST 1 0
1 024 x 7 68
/ 2 5 6 / 2 6 2K
ART I ST TI
1 280 x 1024 / 256 / 1 6 M
TVGA
1280 x 1024 / 256 / 1 6 M
SOTA 3 40 i
1280 x 1024 / 256
Q2000
2048 x 2048 / 2 5 6 / 1 6 M
TVGA 8 9 0 0
2048 x 2048 / 2 5 6 / 1 6 M
Spectrum / 2 4
1024 x 7 68
ColorBOARD / 2 4
1024 x 7 6 8
Dire ctColor / 2 4
1 1 52 x 882
nás tupem
neposkytuj í rychl os t i ,
barev
z n i chž
r o z l i š ov a c í
p o č e t zobrazovaných barev , p o č e t možných barev ) .
ART I ST 1 MONO
S
ř ada
pracovní ch
dos tatečnou
4 / 4096
}
s tani c
výkonnos t
\
až 2 4 bitů na 1 p ixe l
v š ak
uve dené
vzhle dem
k
v i d e okar ty p o žadované
r o z l i š ovací s chopnos t i a po čtu zobr az i t e lných barev .
Ukázkou j e pak např . p r a cuj e na fr ekven c i
procesor IMS G 1 8 0 [ 1 7 6 ] f irmy INMO S , 200 MHz a který poskytuj e
až
32
který
b i tů na
p ix e l . Grafi cký
akc e l e r átor
PUMA
[ 177 ]
nej en s vými výkonnos tními parame try ,
firmy
Chips
je
z a j ímavý
ale i použi t ím grafi ckého
r o zhraní na vys oké úrovni . Na obr . 2 . 3 . 2 j e ukázán p ř e dpokládaný způs ob použ i t í .
- 48 -
P U M A 001 GUI
Ap l ikační � p r og r am
grafi cký interface
�
dr ivery pro � VGA /VGA- 8 5 1 4 /A
moni tor
dr ivery pro l a s e r ovou t iskárnu
l a s e r ová t iskárna
r--
�
t r ans form ace , o ř e záván í , p lnění , kružn i c e , e l ip s a , s p l inové aprox ima ce
�
zobrazování vektorů , v z o r ů , b l t ove o p e r a c e ,
GUI ( Gr aphi c s U s e r Interface ) - uživatelský grafi cký inte r fa c e DDI ( Devi ce Dependent Interface ) - interface závi s lý na zař ízení Obr . 2 . 3 . 2
Vedle
v i de oadaptérů
j s ou
j e š tě
vyr áběny
umožňuj í c í
kar ty
zpracování vide o s i gnálů j ak v normě PAL , ' tak i NTS C .
Color Capture
NuVis t a
r o z l i š ení
s i gnál
640 x 480
NTSC
T I FF
512 x 575
PAL
I MAGE
7 5 6 x 48 5
NTSC
TGA
7 68 x 575
PAL
P I CT
formát dat
}
1 6 b i tů
}
3 2 b i tů
Někt e r é n e j nově j š í sys témy nabíze j í vyš š í r o z l i š ov a c í s chopno s t při
24
b i t e ch
formátů Targa ,
pro
pro
r o z l i š ení
ukl ádání
barev
obrazových
dat ,
a
podporuj í j ako :
c e l ou
ř adu
TGA ,
I FF ,
T I FF ,
G I F atd .
Kr omě
uve dených
z a č ína j í
pros azovat
využ ívá
parale lního
základn í ch
principů
s p e cializované zpracování
r e a l izovaných operac í .
- 49 -
z a ř ízení
p r o c e s ory , k
se v
pod s tatnému
j iž n i chž
dne s se
urychlení
2 . 4 P ř í kl ady Př íklad
l
Odvoďte
z ákladní
pros toru p ř i použi ty
vztahy
pro
použ i t í
zvukového
bodové
mikrofony ,
č tyř i
odmě ř ování
pe r a .
v
P ř e dpokláde j te ,
kte r é
j s ou umí s t ěny
mě ř í c í oblas t i .
z pozice zvukovéh o pera
( x o,Yo, zO )
x
B
Odmě ř ování s použ it ím čtyř mikrofonů Obr . 2 . 4 . 1 Z obr . 2 . 4 . 1 vyplývá ,
Pro ( , ( TJ
2 2
=
=
že platí 2
d
2 1
=
z
2 2 ( a +
d
2 2
=
z
2 a
d
2 3
=
z
2 �2 a +
d
2 4
=
z
2 2 � a +
� ,
TI
,
+
� platí nás leduj í c í vztahy
2 2 + ( b - Ya ) ( a - xO ) 2 2 + ) b - y ( a + xo ) O - 50 -
t ř í r o změ rném
TI
že v
j s ou
r o z í ch
� �
2
( a
2
+
Xo )
( a - xO )
=
2 2
+
+
( b
+
( b
+
y y
)
o
o )
2 2
Pak po úpr avách do s táváme d
2 3
_
d
2 4
=
4ax
O
Z výš e uvedených vztahů vyp lýv á , I
kde
C
d
�
- d
�
- d
� di +
I
$
že C
j e hrani c í možných nepřesno s t í p ř i o dmě ř ování apod .
Analogi cky p r o y
o
dos táváme
resp .
Na Xo '
z ákl adě y
o
výš e
uvedených
vztahů
je
možné
ur č i t
s ouřadn i c e
t akto : - d
2 ) / ( 8 a ) 1
- d
) / ( 8 ,b )
�
Nyní j e ne zbytné ur č i t s ouřadn i c i z o O
- 51 -
Lze ukázat ,
že platí :
Př íklad
Z
Odvoďte pros toru použi ty
zákl adní
při tři
použ i t í bodové
vztahy
pro
zvukového mikr ofony ,
odměřování
v
t ř í r o změ rném
per a .
P ř e dpoklá d e j t e ,
které
j s ou
umí s těny
že ve
r o z í ch mě ř í c í o b l as t i .
z pozice zvukového pera
A B
Odmě ř ování s použ itím t ř í mikr ofonů Obr . 2 . 4 . 2
Z obr . 2 . 4 . 2 vyp lývá , d Pro
2 1 �
� Tj
2
Z ,
=
2
ť}- 2
=
Tf
2
+ �
o
,
2
ť}-
d
2 2
=
Z
2
o
+ Tj
platí
( a - xO )
2
( a
2
+
že
x
o )
( a - xO )
2
+
( b - YO )
+ ( b +
( b
y +
y
o o
) )
2 2 2
- 52 -
2
d
2 3
=
Z
2
o
2 + ť}-
j s ou t ř e ch
Na základě uve dených vztahů pak úpr avami d o s t áváme X
=
o
2 ( d2
2 YO = ( d3
d
2 / ( 4 a ) 1 )
d
2 / ( 4 b ) 1 )
d
2 / 2 1 )
_
_
Označ íme - l i ° a
=
1
ex =
2 ( d2 2a
2
+
pak z r ovni c p r o d
Z Z Z
2
o
2
o
2
o
1 2 3
_
X
2
l
= d
2 - ex 1
= d
2 - ex 2
= d
2 - ex 3
d
,
2
=
2 ( d3
d _
2 1 )
/ 2
2 YO
+
o
°
+
°
-
°
+
°
d
,
2
1 1
+
°
+
° °
-
1
dos táváme
3
2 2 2
Pak Z
2
o
=
2 2· ( Zo + Zo 1 2
+
Z
2
o
3
) / 3
Uve dený pos tup výp o č tu s ouřadnic poskytuj e i možno s t i z j i š tění někte r ý ch chyb zař ízení , např .
pokud někte r y mikr ofon n e p r a cuj e
s po l ehl ivě .
- 53 -
3.
Základní a lgor i tmy r a strové grafiky
Ras t r ová obrazů,
ke
kre s l eni
n-úhe lniků kap i t o l e
tak , a
v
r a s trových
př imek
aby chom [ 49 ] ,
a
mě l i
V
kř ivek , do j em
[ 109 ]
z a ř izení .
j e dn o t l ivými ras t r ová
zař i zeni vyžaduj i spe ciálni
zákl adnimi
kap i to l e
tj .
se
vyplňováni V
p ř e d cho z i
zákl adni
p r in c ipy
se
které
j ak
k
oblas t i .
uvedeny
algor itmy ,
z a ř izeni obou typů ,
př ipadně
plné
j s ou
této
a l gor i tmy k vytvářeni
budeme j s ou
z abývat
vhodné
s ekvenčnim
pro
p ř i s tupem,
tak i s př imým p ř i s tupem k bodu . 3 . 1 Algo r i tmus pro kres lení čáry
V př ipadě ras trového zaři zeni j e zobrazov a c i p l o cha v l a s tně rozdělena do mat i c e j e dnotl ivých. p o l i ček, j e dnot l ivě
adr e s ovat ,
a de finovat označováno v př ipadě
též j ako
i
j e j i ch p ixe l .
r a s t r ových
když
j as Na
ne
či
zař izeni
vždy
barvu .
rozdil
od
obrazem
svis lých
j e dnotl ivých
ane bo p ixelů
čar v
zabývat 45
ras tru
sklonem v c e l ku
aktivace pixelů v ras tru
- 54 -
p o l i čko
je
z a ř i zeni
se
o tá zkou ,
kř ivky .
obr . 3 . 1 . 1 .
Obr . 3 . 1 . 1
mod i f ikovat ,
vektorových
resp . s
pr lmo
Jedno t l ivé
mus ime
způsobem s e vlas tně zobraz i ús e čky , vodor ovných,
z n i chž každé j e možné
j akým
V p ř ipadě čar je
gene r a ce
j e dnoduchá ,
viz
V
os tatních
př ípade ch
vlas tně
z ákladním
zaj i s té
p ožadovat , a
v š ak
požadavkem aby
maximální p ř e s nos t i . ry chlo s t í ,
se
pro
př ímka
dos táváme hle daný
zůs tala
do
potí ž í .
Co
a l g o r i tmus ?
př ímkou
prl
je
Budeme
z a chování
Kr e s lení čáry by mělo probíhat s maximální
t e dy
vlastní
r e ž imu
budeme
al gor i tmus
mus í
být
p omě rně
j ednodu chý . V
bě žném
kons tantní j as .
též
požadovat ,
aby
čára
měla
J e zř e j mé , vzhl edem k ras t r ovému p r in c i pu ,
ž e ne
v š e chna o bvykl á kr i t é r ia lze splnit beze zbytku , j e dána j emno s t í ras tru . provádě t vede
ke
modul a c i
j asu
požaduj e ,
Pro zlepšení vizuálního v j e mu j e možné z e j ména
s l o ž i tě j š ím a
neboť p ř e s nos t
tedy
" pos trann í ch "
p ix e lů ,
což
i pomale j š ím algo r i tmům .
v š ak
Obe cně
se
aby a l gor i tmy pokud možno používaly pouze c e l o č í s e lnou
r e p r e ze n t a c i č í s e l a byly r e a l izovány hardwar ově . V ě t š ina metod že
z
dané
je
pozice
zalo žena na přírůs tkovém p r in c ip u - t zn . ,
chceme
nakr e s l i t
čáru
do
pozice
v zdál ené
o ( llx , lly ) . 3 . 2 Digi tá lní diferenc i á lní ana lyzátor
J e dnou
z
pros t ř e d í ,
je
možno s t í , použi t í
j ak
gene r ovat\
digitálního
ú s e čku
diferenc iálního
v
r a s trovém analyzátoru
( DDA ) k ř e š ení diferenc iální rovnice : dy
kons t .
dx
lly
nebo
llx
=
kde ( x ' Y ) j e počáte ční bod , ( x ' Y ) j e koncový bod ús e čky . a a b b ř e š ením j e ( llx = 1 , neboť x - x = 1): i+1 i
P ak
Y i+ 1 = y 1. + lly
tj .
+
Yb
-
Ya
Y i+ 1
= y.
kde :
( x , y ) j e bod ( x ' Y ) ' o O a b
Je
1
zř e j mé ,
oktan t y ,
X
- x
b
že
kde p l a t í
X
a
tento algoritmus
1
llx
1
zaměnit s ouř adn i c e x a y . tak ,
aby
i+1
p r acoval
pro
�
1
lly
I.
=
je
x.
1
použi t e lný pouze
podprogramem :
- 55 -
-- ---- ------
pro
ty
Pro os tatní oktanty s e mus í
Algoritmus DDA , vše chny
+ 1
který j e mo d i f ikován
oktanty ,
lze
r e a l i zovat
ya , x b , yb :
procedur e DDA ( x a ,
dy ,
i,
er ,
srn :
r ea l ;
- xb - x a ;
begin dx
x
iy , x , y :
ix ,
va r dx ,
- xa; y
integer ) ;
integer ;
- yb - ya ;
dy
- ya;
- 0. 5;
er
PLOT ( x , y ) ; if dx > O then ix : = 1 e l se ix : = - 1 ; if dy > O then iy : = 1 e l se iy : = - 1 ; if abs ( dx )
> = abs ( dy ) then
begin srn : = abs ( dy ) / abs ( dx ) ; for i : = 1 to abs ( dx ) do
- e r + s rn ; if er > = 1 then
begin er
x
-
+
x
er . - er - 1 end ;
- y + iy ;
begin y
ix ;
PLOT ( x , y ) end end e l se
- abs ( dx ) / ( dy ) ;
begin srn
for i : = 1 to abs ( dy ) do
- e r + s rn ; if er > = 1 then
begin er
begin x
Y
- Y
-
+
e r - 1 end ;
er
x + ix ;
iy ;
PLOT ( x , y ) end end end ;
{ PLOT ( x , y ) zaj i s t í akt iva ci bodu o s ouřadn i c í ch ( x , y )
}
Algori tmus 3 . 2 . 1 Uváž íme - l i
úse čku
z
bodu
( 0, 0)
bodu
do
algor i tmus bude mít nás l e duj í c í s t avy : xa = O
ya = O
x = O
xb = 5
yb = 5
dx = 5
Y = O dy = 5
ix = 1
iy = 1
srn = 1
er
- 56 -
0. 5
( 5, 5 ) ,
pak
DDA
i
er
x
y
1
0. 5
1
1
2
0. 5
2
2
3
0. 5
3
3
4
0. 5
4
4
5
0. 5
5
5
Y
x
Výs l e dek DDA algor i tmu v 1 . Z
uve deného
a l go r i tmu
o br . 3 . 2 . 1
kvadrantu
je
zř e j mé ,
že
v
př ípadě
na
s e be
navazuj í c í ch ú s e ček bude kon cový a počáte ční bod z ap s án dvakrát . Toto
může
v
některých př ípade ch vé s t
barvy tě chto bodů ,
k
zvýr aznění
nebo
změně
z e j ména u zař ízení provádě j í c í ch záp i s př ímo
na film . Uvažme nyní ús e čku z bodu
( 0, 0 )
do bodu
( -8 , -4 )
ve
t ř e t ím
kvadran tu . Algor i tmus DDA pak bude mít nás l e duj í c í s t avy :
xa x
O
=
O
=
ya Y
O
=
O
=
x
y
O
-1
-1
2
0. 5
-2
-1
3
O
-3
-2
i
er
1
xb
=
-8
yb
=
-4
4
0. 5
-4
-2
dx
=
-8
dy
=
-4
5
O
-5
-3
ix
=
-1
iy
=
-1
6
0. 5
-6
-3
s rn
=
0. 5
er
=
0. 5
7
O
-7
-4
8
0. 5
-8
-4
Výs l e dek j e uve den n a obr . 3 . 2 . 2 . a . Budeme - l i v š ak mít ús e čku z bodu ( - 8 , - 4 ) d o bodu ( 0 , 0 ) , DDA bude mít s t avy : -4
xa
=
-8
ya
=
-4
x
xb
=
O
yb
=
O
dx
=
8
dy
=
4
ix
=
1
iy
=
1
srn
=
0. 5
er
=
0. 5
-8
=
- 57 -
Y
=
pak
i
er
1
O
2
x
y
O
-3
-1
6
0. 5
-2
-1
-2
7
O
-1
O
-2
8
0. 5
O
O
x
y
i
er
7
-3
5
0. 5
-6
-3
3
O
-5
4
0. 5
-4
-
y
y
x
x
Obr . 3 . 2 . 2 Výs l e dek j e uve den na obr . 3 . 2 . 2 . b . obou
Por ovnáním gener ovaná
výs l e dků
čára není syme t r i cká .
lze
nah l é dnout ,
snadno ,
Navíc DDA a l gor i tmus
že
vyžaduj e
použ i t í p r o c e s oru s pohybl ivou ř ádovou čárkou . y
y
( 0 .1)
w
(0,0)
H
( 1 ,0)
x
b)
a) Obr . 3 . 3 . 1 - 58 -
3 . 3 B r e senhamův a lgor i tmus
B r e s enhamův
algoritmus ,
př írůs tkové z ap i s ovače , zař ízeních . pouze
Výhodou
c e l o č í s e lné
ome zíme
pouze
př ípad
na
na
který
byl
původně
navr žen
pro
j e t é ž vhodný pro použ i t í v r as t r ových
Bres enhamova
algor itmu
r e p r e zentace
dat .
D
tj .
první
oktant ,
obr . 3 . 3 . 1 . a ,
kde
Při
je
výlučné
o dvo zení
použi t í
a l go r i tmu
se
O
:5 . 1 !J.y I :5 l !J.x I . Uvažme diagonální krok , H zna č í
zna č í
hor izontální ( vodorovnou ) krok . Je
z ř e j mé ,
hor i zontální ,
že či
diagonální
Jestl iže
podobnou
obdr ž íme
s chéma
diagonální s chéma
lze
D,
me zní hodnotou pro úvahu
pro
či
kr ok ,
krok
je
provedeme
pos tupné
i
tak ,
hodno t a v
že
H,
není
zda
p r ov é s t
!J. y / !J.x
0. 5.
nás l e duj í c ím
rozhodován í ,
hor i zontální
modifikovat
r o zhodování ,
viz nutné
z da l i
kr oku ,
zvol i t
krok
obr . 3 . 3 . 3 .
Uvedené
používat
operací
v pohyblivé ř ádové č ár ce .
(6,2)
(0,0)
a)
(0,0)
(0,0)
b)
c)
Obr . 3 . 3 . 2 .
�D � � �D !J.y / !J.x :5 1 / 2
H
�
2 !J.y j !J.x :5 3 / 2
:5 1 / 2
n!J.y / !J.x :5 1 / 2
?�
3/2
n!J.y / !J.x :5 3 / 2
Obr . 3 . 3 . 3 - 59 -
D
3 !J.y / !J.x :5 5 / 2
�\
n!J.y / !J.x :5 ( 2n - 1 ) / 2
Vynás obením výr a zů hodno tou 2�x dos táváme ( �x > O ) :
�
::s
O
H
D
4�y- 3 �x
�
H
::s
O
Obr . 3 . 3 . 4 Algor i tmus gen e r a c e čáry lze pak popsat takto : procedure BRE SENHAM ( x l ,
a,
y,
x,
va r i , begin x
b,
d:
y 1 , x 2 , y2 :
integer
);
integer ;
xl;
y : = y1; x2 - xl;
dx
dy : = y 2 - y 1 ; d
-
2
*
dy - dx ;
a
- 2
*
dy ;
b
-
2
*
( dy - dx ) ;
for i
- O to dx do
if d < = O then begin d
-
d + a;
+
x
x
x
x + 1;
1;
KROK ( " H " ) end e l se begin d : = d
KROK (
+
b;
"D"
Y
y
+
1;
)
end end ;
Algor i tmus 3 . 3 . 1
- 60 -
--- ----
-- -
-
-- -
Uvažme př ípad z obr . 3 . 3 . 2 . c . �y / �x
Pak pro dané hodnoty x
=
6 a y
=
2 je
1 / 3 a podle algoritmu na obr . 3 . 3 . 3 dos táváme p o s l oupno s t :
=
�y �x 3�y ---rx
!:O
3 3
=
5 �y ---rx Počet
1 3
=
!:O
5 3
=
!:O
1 � H "2
2 �y ---rx
3 � H "2
4�y ---rx
3 "2
6 �y ---rx
je
kr oků
e l ementárních
----7
r oven
kr oků
D
v tomto algor i tmu hodnotou 2 �x , obr . 3 . 3 . 4 .
Ozna č íme - l i
"H"
v př ípadě
kr oku
v př ípadě
kr oku
výr az
mus íme
"D"
je
4 3
=
6 3
!:O
!:O
!:O
1 "2
-----7
3 "2
-T H
5 "2
-T H
Vynás obíme - l i
D
p o s l oupno s t
Z í s kaná
�x .
hodnotě
" HDHHDH " .
je
2 3
=
z l omky
vš e chny
dos taneme algori tmus uve dený na 2�y-�x
identifiká t o r em
připo č í s t
nutné
hodnotu
p ř ipo č í s t
a
d,
pak
r ovnou
2�y ,
hodnotu
b
r ovnou
2 �y - 2�x . Vzhl e dem k r e p r e zenta c i ,
tomu , je
že
algoritmus
možné
j ej
používá
snadno
c e l o č í s e lnou
pouze
int e gr ovaným
r e a l i zovat
obvodem . Odvození B r e s enhamova algor itmu pro ,kr e s l ení byl o
uve deno výš e ,
po chopení
a
i po chopení
byl o
př ípadné
ú s e čky ,
zal oženo na intuit ivním
odvození
matemati ckého
dal š í ch
p ř í s tupu
k
p ř í s tupu .
algor i tmů
odvoz ení .
které
je
Pro
ne zbytné
P ř e dpokláde j me
ur čuj í skute čnou vzdáleno s t kde d ' d l 2 o d nej bližš ích bodů ras tru a kde vzdáleno s t
s i tua c i na obr . 3 . 3 . 1 . b , př ímky w p r o x me z i
body
=
x
ras tru
l je
v
obou
smě r e ch
rovna
ús e čka l e ž í na p ř ímce w a má kon cové body x
r
j e dné .
Z o b r azovaná
a x . s
Pro p ř ímku l z e p s á t y = m x + b p ř i čemž smě r n i c e m j e dána výr azem m
�y / �x
=
Hodnotu b lze ur č i t dosazením např . položíme X o Y
O
=
=
x
r '
pak
�y �x
x
O
+ b
a b
( �x y
O
- �y X o ) / �x - 61 -
bodu x
r
do r ovn i c e ,
p ř i čemž
Pro krok i ,
a t e dy i pro prvý , !J.y � uX
y = m x. + b = 1
Vzhl e dem k tomu , je
nutné
pro
lze p s á t
x. + b 1
že bod ( x . , y ) není obe cně bodem daného r a s tru, 1
prvý krok
vybrat
j eden
bod
( x , y ) nebo O 1 kr i t é r ium , pomo c í
z
bodů
( x ' y + 1 ) . Pro volbu bodu j e nutné zvo l i t l 0 kter ého r o zhodneme , který bod vybr at . P ř i r oz eným
kr i t é r i em
je
výběr
( Xt ' y ) ,
to
t oho
bodu
ras tru,
vzhle dem k o s e y ,
který
např .
d
dos táváme y - y. = m x 1
d
je
- d . 2
l
i+1
ne j bl íže Pak p r o
bodu
i-tý
(
i
=
O
a )
krok
+ b - Y = m ( X. + 1 ) + b - y. 1 1 i
- Y = Y + 1 - m x - b = Y i+ 1 i+1 i
2
1
+ 1 - m ( X 1. + 1 ) - b
i
+ 1) - 2 Y + 2 b - 1 i
= y.
Ode č tením dos táváme d
- d
l
2
=
2 m ( x
dos azením za m = !J.y / !J.x pak !J. X ( d
l
- d
2
) = 2 !J.y x
i
- 2 !J.x
�i
+ 2 !J.y + 2 b !J.x - !J.x
Označ íme - l i P i = !J. x ( d l - d 2 ) pak l ze p s á t p.
= 2 !J.y x .
1
1
- 2 !J.x y . + c 1
p ř i č emž Je
c = 2 !J.y + !J.x ( 2 b - 1 )
z ř e j mé ,
ž e kon s t antu c by bylo možné ur č i t např .
počáte čního bodu ús e čky .
dos a z en ím
Dos azením za b do výr azu p r o kon s t antu
c dos táváme c = 2 !J.y + !J.x [
- 2 !J.y Xo ) O - 2 !J.y X o - !J.x
( 2 !J.x y
2 !J.y + 2 !J.x y O Dos adíme - l i nyní za c do =
rovnice
ur čuj í c í
/ !J.x - 1 ] hodnotu
p.
1
,
pak
dos táváme : P i = 2 !J.y x i - 2 !J.x Y + 2 !J.y + 2 !J.x Y - 2 !J.y Xo - !J.x i O Úpr avou p r o i = O dos táváme
P
o = 2 !J.y - !J.x - 62 -
v záv i s l o s t i na hodno t ě P ' Nyní j e ne zbytné ur č i t hodno tu P i+1 i Obe cně j e možné p s á t , ž e :
- 2 �y x . + 2 � X y . - C 1
Úpr avou a dosazením za X
1
kde x
i+1
i+1
= x. + 1 , 1
dos t áváme
P i+ 1 - P i = 2 �y - 2 �x ( Y i + 1 - Y i ) a t e dy l z e p s á t ,
Ze
že :
zvo l eného kr i t é r i a vyp lývá ,
bude vybrán krok hor izontáln í ,
že pokud bude tj .
d - d !S O , p ak 1 2 zvolen bod ( x . + 1 , y . ) .
bude
1
Pak
1
P l = P o + 2 �y Pokud
bude
d - d > O , pak bude 1 2 bude zvo len bod ( x . + 1 , y . + 1 ) . Pak 1
vybrán
krok
d iagonální ,
tj .
1
P l = P o + 2 �y - 2 �x
Poznámka
Z
uvedeného
je
zř e j mé ,
že
hodnotě
1
ident ifikátor d v algoritme ch 3 . 3 . 1 a 3 . 3 . 2 .
Br e s enhamův
algor i tmus
pro
modifikován pro v š e chny oktanty , obe cné
polohy
nevýhodu ,
že
ú s e čky . n e j s ou
z obr . 3 . 3 . 2 . a,
obe cně
snadno
v př ípadě kr e s l ení
z bodu
dosud
( 4, 2 )
známé
syme t r i cké .
z j i s tíme , ( 0, 0)
čáry
mus í
být
nyní
aby mohl být použ i t p r o př ípad
Vš e chny
pak
p ř i kr e s l ení z bodu
gene r a c i
odpovídá
p.
do
d o bodu
že bodu
a l go r i tmy
Uvážíme - l i
p o s l oupno s t (4, 2 )
než
( 0 , 0 ) - naznačeno
maj í p ř ípad
bude
j iná
pos l oupno s t č árkovaně .
Tuto nevýhodu n e l z e v zás adě e l iminovat , neboť j ak j e ukáz áno na obr . 3 . 3 . 2 . b , a ( 2, 1 ) ,
a "to
j s ou možné pouze dva způs oby propo j ení bodů " horem "
nebo
" do l em " .
záv i s l é na operátoru v podmínce ,
tj .
nebo ( = p ř i por ovnávání chyby d .
- 63 -
( 0, 0)
Který způs o b použ i j eme ,
je
zda l i použi j eme ope r át or (
procedure BRE SENHAM ( x l , var ix ,
iy,
j,
d,
a,
begin xp
-
ix
-
dx
- abs ( x 2
xl i
yp
b,
y l , x 2 , y2 :
dx ,
dy ,
xp , yp :
intege r i
- yli
S I GN ( x 2 - x l ) i -
xl ) i
iy
S I GN ( y 2 - y l
-
abs ( y 2 - y l
dy
i f dx > = dy then { l o , 4 . , S . , 8 . begin a : = 2 * d Y i * DRAW STEP i for j
integer ) i
)i
)i
oktant } b : = a - 2 * dX i
d : = a - dX i
1 to dx do
begin i f d < = O then d : = d + a e l se begin yp : = yp + i Y i Ci
:= d + b
end i
xp : =XP +i X i DRAW STEP end end
{
e l se
2. , 3. , 6. , 7.
2 * dX i * DRAW STEP i
begin a
for j
oktant } b
d : = a - dY i
a - 2 * dY i
1 to dy do
begin i f d < = O then d
d + a
e l se begin xp : = xp + i X i
d . - d + b end
yp : = yp + i Y i DRAW STEP end end end i
{ př íkazy označené * j en v př ípadě zař í zení s p ř ímým } { p ř í s tupem - j s ou nutné k akt ivaci počáte čního bodu } Algor itmus 3 . 3 . 2
Z a j ímavý a l gor i tmus pro gene raci čáry ,
viz
[ 22 ] ,
p r o p ř ípad
O < �y < �x j e uve den na obr . 3 . 3 . S .
- 64 -
----- -
--- -----
: =
b
J,
�Y i
a
Ml = H r------7
1- M l
M2
o M2- 1
1
1 ?
a
1
�x - � Y
M2 = D �------,
a < b
b
a = b 1 generuj M 2 o M 1 -
- a - b
a
kde M-
a > b
: =
b
a-kr át
1
ozna čuj e inv e r z i ř e t ě z ce M
1
Ml
M2 o M 1 - 1 b - a
ozna čuj e z ř e tě zení
a
Obr . 3 . 3 . s Činno s t
a l go r i tmu
l ze
demons trovat
na
p ř íkladě
kr e s l en í
č áry
z bodu ( 0 , 0 ) do bodu ( 5 1 , 1 1 ) nás leduj í c í tabulkou hodno t :
Ml
M2
H
HD
H
HDH
H
HHDH
HHDHH
HHDH
a
b
40
7
11 11 11 11
7
4
HHDHH
3
4
3
1 1
29 18
2
HHDHHHDHH HHDHHHDHH
HHDHHHDHHHHDHH
HHDHHHDHHHHDHHHHDHHHDHH
HHDHHHDHHHHDHH HHDHHHDHHHHDHH
HHDHHHDHHHHDHHHHDHHHDHHHHDHHHHDHHHDHH
1
1
gene ruj e výs l e dnou pos loupno s t kr oků
HHDHHHDHHHHDHHHHDHHHDHHHHDHHHHDHHHDHHHHDHHHHDHHHDHH
kte r ou l z e zap s at
J e vhodné zde po znamenat , pouze
s
t e s továním
že c e l á pos l oupno s t byla vygener ována
devíti
podmínek,
a inv e r z e j e poměrně časově nár o čná .
- 65 -
avš ak
oper a c e
z ř e t ě zení
3 . 4 Gene r á t o r kružnice
některých
V
ap l ikacích,
me chani ckých
čás t í ,
její
V
č ás t .
je
prax i
aproximovaly
ze j ména
zapotř ebí byl o
kružni ce
z
oblasti
vykr e s l ovat
použ ito
pomo c í
pak
mnoho
kr e s l ení
kružni c i ,
resp .
a l go r i tmů ,
př ímkových
ús eků .
které Je dním
z ne j pr imi t ivně j š í ch algor i tmů j e př ímá apl ikac e p a r ame t r i ckých r ovn i c kružni ce : y = R * s in .( t )
x = R * cos ( t ) t E < O , krokem
2n ) ,
kde s ouřadnice bodu ( x , y ) j s ou po č ít ány s malým
parametru
t
pro
t=O ,
spoj ovány př ímkovými ús eky . neoby če j ně
náro čný pro
t=A t ,
a
j edno t l ivé
body
j s ou
Tento způsob gene r ování kružn i c e j e
opě tovné výp o č ty hodnot
goniome t r i ckých
funkc í co s ( t ) a s in ( t ) . Kruhový
oblouk
l ze
též
snadno
aprox imovat
J e - l i R p ol oměr kružni c e a d povo lená od chylka ,
l omenou
č á r ou .
pak l z e s p o č ítat
s ouř adn i c e l omené čáry aproximuj í c í kružn i c i x.
cos
a
x.
s in
a
l
l
y . s in
a
y.
a
l
+
l
cos
i=O , I , . . .
nebo v mati covém tvaru
kde
x. , y. l
l
cos
a
- s in
a
s in
a
cos
a
j s ou
počáte ční
i= O , I , . . . .
s ouř adnice
l omené
č áry
a
poo t o č en í . (xO , y O)
(xO, y O )
(xI, y1)
R
R+d
b)
a)
Obr . 3 . 4 . 1 - 66 -
a
úhe l
Pro vni třní nahr azení kružni c e l omenou č árou ,
o br . 3 . 4 . 1 . a ,
platí : ex
cos V
př ípadě
2""
R - d R
-
_
nahr azení
obr . 3 . 4 . 1 . b , cos
kružnice
lomenou
čárou
s
je
ex
2""
d,
R - d R + d
-
se p o č í t á pouze j ednou .
s tá l e
±
platí
p ř i čemž bod ( x ' y ) není bodem kružnice . o o Výhodou uve deného p ř í s tupu j e , že hodnota funkc í
od chy lkou
příliš
s ložitý .
Pro
Nicméně výše uve dený a l go r i tmus ras trové
prostředí
generovat
pomo c í B r e s enhamova algor itmu .
generován
pouze
1.
oktant
a
goniome t r i ckých
os tatní
l ze
kružn i c e
Poznamene j me ,
oktanty
se
že
z í skaj í
bude např .
p omo c í s yme t r i e , v i z obr . 3 . 4 . 2 .
y (y, x )
( -y, x )
(y,-x )
x x
(0, 0) b)
( x ,-y)
( - x ,-y)
( O ,R)
a)
Obr . 3 . 4 . 2 K
odvození
1.
kvadrant
č inno s t i a
budeme
v p o čátku s ouřadn i c . x =
O,
Y = R,
Bres enhamova
pak
předpokládat ,
Poznamene j me , s ouřadnice
pr oměnné x v
1.
kvadr antu,
ver t ikální m
'
d iagonální m
V
generátoru
y
že
kružn i c e
s tř e d
kružn i c e
je
že začne - l i a l go r i tmus v bodě je
monotónně
kle s a j í c í
a j s ou tedy možné pouze D
uváž íme
tři
funkc í směry :
a hor i zontální m , v i z o br . 3 . 4 . 3 . H
- 67 -
Algori tmus by mě l vybrat takový nás le duj í c í p ixe l , nej blíže
ke
s kute čnému
průběhu
kre s l ené
kružn i c e .
který j e
Ozna č ím e - l i
j e dn o t l ivé směry výrazy m
=
( x.
+
1
)2
+
n
=
( x.
+
1
)2
+ ( y. - 1
V
=
H
m m
1
1
2 y . - R2 1
)2
1
)2 2 x. + ( y. - 1 1
I
1
R
_
2
R
_
2
I
I
pak bude vybrán ten směr , pro který výr az z uve dených t ř í výr azů nabývá minimální hodno ty . Vzhl e dem k ras trovému prostředí exi s tuj e
pouze p ě t možných
s i tua c í průběhu kružni ce v ras tru . (xi+l,y i+l)
mv
1 ( x i +1, Y i -l) 5
( x . -l, y 1. - l ) 1
4
3
b)
a)
Obr . 3 . 4 . 3 Ozna čme
�.
1
rozdíl kvadrátu vzdáleno s t i bodu
(x.
1
počátku kružn i c e a kvadr átu poloměru kružn i c e R , �.
1
=
( x. + 1 ) 1
2 + ( y. 2 2 1 ) - R 1
- 68 -
----
------- --
---
-
+
1,y.
pak :
1
- 1)
od
Podobně i v
j ako
př ípadě
u B r e s enhamova algor itmu pro . kr e s l en í gene r átoru
kr e s lení .
J e s t l iže
kružni ce ,
tj .
j de
kružnice
lJ. .
< O 1 o př ípad
je
pak 1.
pods tatné
p ř ímé
znaménko
č áry chyby
bod
( x . + 1 , y . - 1 ) j e uvni t ř 1 1 2 . Je zř e j mé , ž e mus í být
nebo
vybrán buď bod ( x . + 1 , y . - 1 ) , t j . směr m ' nebo bod ( x . + 1 , y . ) , n 1 1 1 1 t j . směr m . K r o zhodnut í , j aká možnos t s e má vybr a t , j e nutné H z j i s t i t , který z výrazů m a m j e v abso lutní hodno t ě menš í , n H r e s p . ur č i t znaménko výr azu :
Je-li
ó
<
O
tj .
cx
I
1
I
<
I,
cx
pak
2 Opačně ,
mus í
být
vybrán
bod
(x . + 1,y. ) , tj . krok m . j e-li ó > O tj . 1 1 H pak mus í být vybr án bod ( x + l ' Y - 1 ) , t j . I cx 1 I > I cx 2 I i i krok m . Když vzdáleno s t i cx a cx j s ou s i rovné , vybe r eme n 1 2 hor i zontální krok . Tedy j e - l i : Ó
!:
O
ó > O ,
vyber krok m ' H
tj .
bod ( x . + l , y . ) 1 1
vyber krok m
tj .
bod ( x . + 1 , y . - 1 ) 1 1
'
n
Uve dené výrazy j s ou poměrně komp l ikované .
Je tedy vhodné p ř evé s t
výr azy p r o ó n a takový tvar , kdy není zapo tř e b í o p e r a c í nás obení a dělení . Pro p ř í pa d 1 .
platí,
( x. + 1 ) 1 ( X. + 1 ) 1
že
2 2 + y. - R 1
2 2
�
+ ( y. - 1 ) 1
O 2
R
2
< O
_
neboť p l a t í ,
ž e bod ( x . + 1 , y . ) j e vždy vně kružn i c e , z a t ím c o bod 1 1 ( x . + 1 , y . - 1 ) j e uvnitř kružni ce . Pak výr az p r o ó může být 1 1 p ř e p s án na ó
=
( x.+ 1 ) 1
2
2 + y. 1
R _
2
2 2 2 + ( x. + 1 ) + ( y. - 1 ) R 1 1
po úpr avě dos t aneme : ó
=
2 [
( x. + 1 ) 1
2
+ ( y. - 1 ) 1
2
- R
Použ i j eme - l i nyn í výr az pro výpo čet lJ. . , 1 2 ( lJ. . + y . ) - 1 ó 1 1
2
+
y. ] - 1 1
dos táváme
=
což j e pods tatně j e dnoduš š í výr az ( nás obení dvěma s e r e a l izuj e j ako posuv vlevo ) . Uvá ž íme - l i př ípad průběhu funkce ,
2. ,
pak vzhle dem k monotónně k l e s a j í c ímu
mus í být vybrán bod ( x . + 1 , y . ) . 1 1 - 69 -
Pak t e dy p l a t í
( x . + 1 ) 2 + y 2. - R 2 < O 1 1 ( x. + 1 )2 + ( y. 1 1
-
1 ) 2 - R2 <
O
( x . + 1 , y . ) a ( x . + 1 , y . - 1 ) l e ž í uvn i t ř kružn i c e . 1 1 1 1 Tudí ž o < O a bod ( x . + 1 , y . ) j e vybr án podle s te j ného k r i t é r i a 1 1 j ako p r o př ípad 1 .
nebo ť
body
fl . > O , pak bod ( x . + l , y . - 1 ) j e vně s kute čné 1 1 1 t j . mohou nas tat pouze případy 3 . , r e s p . 4 . J e z ř e j mé ,
J e s t l i že kružn i c e , že
mus í
být
vybrán
buď
bod
o
souřadn i c í ch
' nebo bod ( x + l ' Y - 1 ) , tj . směr m V D i i p ř e de š l ém textu se budeme snažit vybrat bod ,
směr m v
( x . , y . - I), tj . 1 1 . Anal o g i cky j ako který
způs obí
ne j menš í chybu při zobrazení . Pak podle obr . 3 . 4 . 4
a t e dy : o'
( x. + 1 )2 + ( y. - 1 )2 1 1
=
- I
x � + ( y . - 1 ) 2 - R2 1 1
_
R2
I
Obr . 3 . 4 . 4 Jestl iže o ' V př ípadě , krok m . V
< že
O o'
,
pak >
O
Pro př ípad o '
l a 1 1 ' a tedy bude vyb r án krok m D . I a 1 1 a mus í být vybr án pak I a 1 < 2
l a2 1
>
= O bude vybrán krok m - 70 -
D
.
Tedy j e - l i : o'
S
O , vyber krok m , D
tj .
bod ( x . + l , y . - 1 ) 1 1
o'
) O , vyber krok m ' y
tj .
bod ( x . , y . - 1 ) 1 1
Uve dené podmínky pro o ' P r o př ípad 3 p l at í ,
j e opě t nutné z j e dnoduš i t . že
( x . + 1 ) 2 + ( y . - 1 ) 2 - R2 1 1
�
O
x � + ( y . - 1 ) 2 - R2 < O 1 1 nebo ť bod pro o '
( x . + l , y . - 1 ) j e vždy vně skute čné kružn i c e . 1 1 může být upr aven na tvar
0 ' = ( x . + 1 ) 2 + ( y . - 1 ) 2 - R2 + x � + ( y . - 1 1 1 1 1
Pak výr az
)2
_
R2
Po úpr avě dos taneme o'
( x . + 1 ) 2 + ( y . - 1 ) 2 - R2 1 1
= 2 [
Použ i j eme - l i nyní výr az pro výp o č e t � . , 1 0'= 2 ( �. - x. ) - 1 1 1 Uvá žíme - l i nyní př ípad 4, funkce j e monotónně k l e s aj í c í , tj .
směr m ' y
Je z ř e j mé ,
pak
- x. ] - 1 1
platí :
vzhl e dem
k
mus í být vybrán bod
tomu ,
že
(x. ,y.- 1) 1
že :
1
,
( x . + 1 ) 2 + ( y . - 1 ) 2 - R2 ) O 1 1
x� + ( y . - 1 ) 2 - R2 ) O 1 1 neboť
body
(x. ,y.- 1) a (x.+ 1,y.- 1) j s ou vně s kute čné 1 1 1 1 kružn i c e , tedy o ' ) O , a j e vybr án bod ( x . , y . - 1 ) , t j . směr m ' y 1 1 Nyní z bývá pouze r ozhodnout př ípad 5 , který nas t ává pouze tehdy , p r o cház í - l i skute čná kružni ce bodem ( x . + 1 , y . - 1 ) , 1 1 výp o č e t j ednotl ivých komponent o platí
tj .
� . =O . 1
Pro
tj .
směr
m . D
( x . + 1 ) 2 + y � - R2 ) O 1 1
( x . + 1 ) 2 + ( y . - 1 ) 2 - R2 = O 1 1 a tedy o
)
O
a byl
(x.+ 1,y.- 1), 1 1 dos t áváme
by vybr án bod
Anal o g i cky p r o komponenty o '
( x . + 1 ) 2 + ( y . - 1 ) 2 - R2 = O 1 1
x � + ( y . - 1 ) 2 - R2 < O 1 1
( x . + 1 , y . - 1 ) , tj . 1 1 směr m . Tudí ž p r o p ř ípad � = O platí s t e j ná kr i t é r ia j ako p r o D i př ípad � ) O nebo � i < O . i a
o' <
O
,
což
je
podmínka
pro
výběr
- 71 -
bodu
Shrneme - l i p ř e d chozí výs l e dky , pak dostáváme : tJ. . < O 1
o :5 O
vyber bod ( x . + l , y . ) , 1 1
tJ. . < O 1
o > O
vybe r bod ( x . + l , y . - 1 ) , 1 1
tj .
směr m
vyber bod ( x . + 1 , y . - 1 ) , 1 1
tj .
směr m
vyber bod ( x . + 1 , y . - 1 ) , 1 1
tj .
směr m
tJ. . 1
=
O
tJ. . > O 1
0 ' :5
tJ. . > O 1
o' > O
Nyní
lze
O
poměrně
vyber bod ( x . , y . _o 1 ) , 1 1 snadno
odvodit
celý
tj .
tj .
směr m
H
směr m
algor i tmus .
D D D
H
Aby chom
nemus e l i p r o každý krok s tále poč ítat výr az tJ. . , o , r e s p . o ' , 1 pokusme s e vyj ád ř i t výr azy j e dnoduš e j i . Předpokláde j me n e j dř íve , že s e má pokr a čovat hor izontálním kr okem m . H bod p l at í : x
tJ.
i+1
( i + l ) -vý
x. + 1 1
i+ 1
Yi + 1
Pak p r o
=
y. 1
2 2 - 1 ) + ( Y - R i+1 2 '2 2 - R + 1 ) + ( y. - 1 ) ( x i+ 1 1 2 2 2 + 1 - R + 2x + ( y. - 1 ) = ( x. + 1 ) i+ 1 1 1
=
+ 1 ) ( X i+ 1
2
=
Podobně p r o d iagonální krok m : D =
=
x. + 1 1 y. - 1 1
= �
i
+ 2x
i+1
- 2Y
i+l
+ 2
Pro v e r t ikální krok m dos táváme : y x
i+ 1
Yi + 1 tJ.
i+1
=
=
=
x. 1 y.- 1 1
+ 1 tJ. . - 2 Y i+1 1
j e záv i s l é pouze na tJ. , i i+ 1 v p ř e d cháze j í c ím kr oku , l z e indexy e l iminovat .
Yzhledem k tomu ,
že tJ.
- 72 -
tj .
na hodno tě
Výs l e dný algor itmus l z e znázornit vývoj ovým diagramem , �
=
(1)
2
+ ( R - 1 ) 2 - R2
=
1 + R
2
+
- 2R
1 - R
kde :
2
1 - R )
= 2 (
1
x : = Oi Y : = R : =
�
*
2
1 - R )
(
l imit
�------�l
O
-
y < l imit
1
--� )
� +
--
kone c
------
PLOT ( x , y ) <5 '
:
= 2� - 2x - 1 (
{m } D
1 r
<5 ' �
Y �
-
O
1
� > O
{m } D
Y -1
1
.r
+
- � - 2y
1
�
2 � + 2y - 1
=
1 r
O
1
O
x : = x + 1
Y - 1
-
�
<5
{m } H
� + 2x - 2y
-
) <5 :
x := x + 1 Y
+
� < O
� ? O
+
�
2
-
� + 2x
I
+
1
Obr . 3 . 4 . 5
V p ř ípadě ,
že chceme generovat kružn i c i j en p r o oktant ,
nas tav i t L IMIT na hodnotu trunc ( R / Dal š í z j e dnoduš ení j e možné , kružn i c e v j ednom oktantu . algor i tmu ,
viz
obr . 3 . 4 . 3 ,
s y s tému obl ouk
a z
vzdáleno s t r a s tru d
l
její bodu
že
poloměr ( O, r )
skute čného
ome z íme - l i s e pouze na gene r a c i
který bral
je
v úvahu mo žno s t i
1 - 5 ,
2 a 5.
kružnice do
�) .
Na rozdíl o d původního B r e s e nhamova
mohou nas t at pouze př ípady 1 , P ř e dpokláde j me ,
j e nutné
r oven bodu ,
bodu
má
s tř e d
r. kdy
kružnice
a d , v i z obr . 3 . 4 . 6 . 2
- 73 -
v
po č átku
Cht ě j me je od
s ouř adného
gener ovat =
Ozna čme
opět
odpovídaj í c í ch
bodů
x
y.
kruhový
y
Obr . 3 . 4 . 6 Obe cně p r o kružnici s e s tře dem v p o čátku p l at í , x a
t e dy
2
j e-li
+ y x
2 _ 2 r
že
O
=
proměnná ,
j e j íž
hodno ty
vol íme ,
p ak
pro
krok
i lze p s á t
Pro d
l
a d d
2
l
2
2 - x. 1 p ak p l a t í
Y
=
= r
2
2 2 2 2 2 y. - y = y. - r + ( x. + I ) 1 1 1 ( Y i- l )
2
=
r
2 _ ( x. + I )2 _ ( y. _ I 1 1
)
2
Označ íme - l i Pi
=
d
- d
l
2
p ak dos táváme p. = 2 ( x. + I ) 1 1
2
2 2 + y� + ( y . - I ) _ 2 r 1 1
Dos adíme - l i do výrazu pro p . s ouř adni ce počáte čního bodu ( O , r ) , 1 pak dos táváme p
O
=
3 - 2 r
j ako funkc i P ' Pro r ekur entní výp o č e t j e nutné ur čit P i i+ l p ak s ouřadn i c v p ř e d chozím kr oku . Vyj ádříme - l i P ' i+ l =
resp .
2
= 2 [
( x + I ) + I ] i
2
- 74 -
+ y
2 - I + ( y i+ l i+ l
)
2
- 2r
Po p ronás obení a úpravě dos táváme
�
P i+ 1 = P i + 4 x i + 6 + 2 ( y + l - y Z
uve deného
vyp lývá ,
- Y ) ) - 2 ( Y i i+ 1
p. < O , je vybr án 1 a t e dy po dos azení bodu ( x . + l , y . ) d o s t áváme 1 1
horizontáln í ,
že
�
pokud
krok
P i+ 1 = P i + 4 x i + 6 zatímco
j e-li
p . !:! O j e vybr án krok 1 dosazení bodu ( x . + l , y . - 1 ) do s t áváme 1 1
diagonální ,
a
t e dy
po
x . - y . ) + 10 1 1 Z j e dnodušený algoritmus ,
který byl navr žen Mi chn e r em ,
může
být
pop s án takt o : procedure M I CHNER ( R : integer ) ; va r x ,
y,
d:
intege r ;
procedure PLOT8 ( x , begin PLOT ( x ,
y:
integer ) ;
PLOT ( -x , -y ) ;
Y );
PLOT ( x , -y ) ;
PLOT ( -x , Y ) ;
PLOT ( y , x ) ;
PLOT ( -y , -x ) ;
PLOT ( y , -x ) ;
PLOT ( -y , x ) ;
{ PLOT ( x , Y ) akt ivuj e bod o s ouřadn i c í ch ( x , y )
}
end ; begin x : = O ;
: =
y
3 - 2
d
R;
*
R;
whi l e x < y do begin PLOT 8 ( x , y ) ; i f d < O then d
: =
d + 4
e l se begin d
Y
*
x + 6
- d + 4 - Y - 1
*
( x - y ) + 10;
end ;
x
- x + 1
end ;
PLOT 8 ( x , y ) end ;
Algor itmus 3 . 4 . 1 Poznamene j me ,
ž e uve dená procedur a generuj e
pouze
j e den oktant
a využívá syme t r ie k zobrazení c e l ého kruhového o b l ouku . Poznámka
Z
uve deného
je
z ř e j mé ,
že
hodno tě
v algor itmu 3 . 4 . 1 . - 75 -
p. 1
odpovídá
p r oměnná d
3 . 5 Generace kuž e l o seček V
l i te r atuře
algor itmů ,
l ze
j ak
Kuž e l o s e čky
nal é z t
generovat
mohou
být
mnoho
v í ce
kuže l o s e čky
pop s ány
v
v
či
méně
důmy s lných
r a s t r ovém
kar té zském
pros tředí .
s ouř adném
sys t ému
imp l i citní r ovn i c í d ( x , y ) = O , kde : d ( x , y ) = 2vx - 2uy + c - �x
2
- ay
2
- 2 0 xy
Pak : dy dx Kuže l o s e čka
v - �x - oy u + o X + ay
=
může
být
gener ována
např .
pomo c í
P i t tewayova
algor i tmu [ 3 9 ] : s tart
1
K 1 : = 2� ; K2 : = 2 o ; K 3 : = 2 a b : = 2v-o ;
hor izontální změna
f(---
oktantu
+
( záměna x , y )
-
a : = 2u+o ;
d : =v-u+ c- ( a+� + 2 o ) / 4
1
d < O
1
j
-
a < O
b < O
1
1
diagonální .,.--� )
+
-
změna oktantu
diagonální
hori zontální
krok
krok
1
b
b - Kl
b
a
a + K2
a
d
d - b
1
a + K3
� �; �: � � d
b - K2 d - a
d 1
P
+ 1 konec Obr . 3 . 5 . 1 Použití
algor itmu
z
obr . 3 . 5 . 1
j e dn o t l ivé koe f i c ienty tak ,
ome zuj e
ř e š en í úlohy ,
j ak ur č i t
aby chom obdr že l i ne j l e p š í aproxima ci
kuže l o s e čky dané s n e c e l o č í s e lnými koe fic ienty . - 76 -
3 . 6 Kódování g r a f i cké informace
S
r o zvo j em
principu
grafi ckých
p o s tupného
systémů
vykr e s l ování
vektorů,
zobrazování po sobě j douc í ch řádek p ř i j íma če ) . zobrazení
založených
grafické
zákl adní te chniky ,
informace .
V
ale
( podobně
Vyvinuly se nové te chniky ,
niko l iv na
na
p r in c ipu
j ako u t e l evi zního
které umo žňuj í e fektivní
zás adě
byly
vyvinuty
čtyři
a to :
- kódování dé lky běhu ( run l ength encoding ) - kódování buněk - frame buffer - ř ádková konv e r z e ( s can l ine conver s ion )
Kódování dé lky běhu
Te chnika kódování dé lky běhu tu
skute čno s t ,
že
ve lké
intenz itu či barvu . ur čuj e
j en
oblas ti
tato
intenzitu a
barva ,
te chnika
např .
obrázku
počet
po
často
s te j nou
rozš ířena
sobě
tak ,
že
se
\
mís to
Je zř e j mé ,
obrázků do chází
i ke komp r e s i dat .
své
které
p ix e lů
s
touto
Tato
důs ledkem
intenzity
udává
že v p ř ípadě vě t š í ch t e chnika má ni cméně
i
s ekven čního
uspoř ádání
s ložito s t í ros tou i nár oky na pamě ť ,
k t e r á může
výs l e dné s ekven ce ,
j s ou
j douc í ch
Pro případ bar evných výs tupů může
pomo c í s ložek RGB .
nevýhody ,
maJ l
využ ívá
V ne j j ednoduš š ím tvaru kódování d é l ky běhu
intenzitou v r ámci dané řádky . být
( run l ength encoding )
a to :
- o b t í žné vkl ádání a ruš ení , -
s
r o s toucí
být v ě t š í než vlas tní frame-buffe r . Kódování obsahu buněk
Te chnikou
kódování
buněk
( ce l l
en coding )
se
r e p r e z en tuj e
ur čitá čás t obrázku j ako ce l ek . Na rozdíl o d p ř e d choz í t e chniky , která
v
podstatě
te chnika
kódování
zvažovala obs ahu
buněk
bere
dis p l ayů ,
k t e r é umo žňovaly zobrazovat znaky
např . ,
že
mohly obr a z
ve l iko s t i 8x8 ,
být
definovány
6 4 0x4 8 0
může
být
u
v
j ednom
smě r u ,
i
oko l í .
Tato
úvahu
byl a
v š ak
zej ména
v
pouze
te chnika které
použ ívána
informac e
t zv .
p s eudografi ckých ( vě t š inou max . 2 5 6 ) ,
uživat e l em . rozdě l en
P ř e dpokl ádá do
4800
p o l í ček
p ř i čemž obsah p o l í ček j e možné de finov a t . - 77 -
se
Obsah
p o l í čka
v e l iko s t i
n x n j e možné repre zentovat pomo c í v z o r ů , 2 19 n kterých j e v š ak 2 , t j . pro n=8 dostáváme p ř i b l i žně 1 . 8 * 1 0 Tento p o č e t j e možné snížit pomo cí posuvu ,
zr cadlení a maskování
na 1 0 8 vzorů při r o změru p o l í čka 8x8 ,
[9].
viz
použ ite lná i p r o př ípad bar evného výs tupu , je
j iž
menš í .
Jis tým
probl émem
je
Tato t e chnika j e
avš ak komp r e sní poměr
pak·
int e r ak c e
s
t akto
definovaným obrázkem .
[1 , 2 ],[0,4 ],[ 1 , 2 ] [0, 1 ],[ 1 , 5 ],[0, 2 ] [0,8] [0, 3 ],[ 1 , 1 ],[0, 4 ] [0, 2 ],[ 2 , 3 ],[0,3 ] [0, 1 ],[2 , 5 ],[0, 2 ] [0,8] [0,8]
kde [ x , y ] = [ intenzi t a , p o č e t po sobě j douc í ch p ix e lů ] Obr . 3 . 6 . 1 Frame buf f e r
Te chnika pros tor , p ixe lu .
frame-bufferu
který
s l ouží
Vzhle dem
k
k
využívá
uložení
rychle
ve lký
grafické
kl e s a j í c í
ceně
a
s p o j itý
pamě ť ový
informa c e
p ix e l
po
pamě ťových
p rvků
se
používá tato te chnika nej čas tě j i v e spoj ení s o s obními p o č í t a č i a grafi ckými s tanicemi . pomo c í
s p e ciální
pods tatně počítače ,
zvý š i t
S amotný fr ame buffer můž e být r e a l i zován
pamě ti
gr afi ckého
výkonno s t
sys tému ,
procesoru, ane bo
j ako
což
umo žňuj e
s ou č á s t
pamě ti
viz [ 4 5 ] , [ 1 0 9 ] .
Frame-buffer
je
obvykle
real izován
pomo c í
s p o j itého
ús eku
pamě t i ,
který si l z e předs tavit j ako vektor .. J e - l i r , r e s p . r , y x r o z l iš ovací s chopno s t ve směru osy x , r e s p . o s y y , a j e - l i adr e s a vektoru B O ' ) s pozi c í ( x , y ) j e dána výr azem :
p o č áte ční
pak
- 78 -
adr e s a
záp i s u
pro
p ixe l
B ( x , y ) = BQ p ř i čemž x E { Q , . . . , Vzhl e dem k t omu , oblouků
atd .
r
y
x
r -1 } x
+
X E { Q , . . . ,
a
obvykl e
akt ivovat
+
r .y x
B ( x , y± l ) = B Q
+
r . (y ± 1 ) x
l ze
r -1 } y
s ou s e dn í
ur č i t
i
+
je
x ± 1 = B(x, y) ± 1
adr e s u
+
x = B (x, y) ± r
bodu
B ( x± l , y ± l )
x
r e p r e z en tuj í c í
bod ( x± l , y± l ) v závi s l o s t i n a znal o s t i adr e sy p ix e lu e fekt ivní
p ix e ly ,
že :
B ( x± l , y ) = B Q
Analogi cky
x
že zákl adní algo r i tmy p r o k r e s lení ús e če k ,
potř e buj í
vhodné poznamenat ,
+
imp l ementaci
Bres enhamova
algo r i tmu
je
(x, y) .
nutné
Pro
vyu ž í t
v ý š e uve dené vztahy .
y
o
B(x ,y)
Obr . 3 . 6 . 2
Řádková konver z e
Řádková konv e r ze umožňuj e
poměrně
( s c an l ine conve r s ion )
e fekt ivní
reprezentaci
j ednoduš e ur č í průs e číky ús e če k , ř ádkou ,
tj .
efekt ivně
i
s
př ímkou
dal š í
resp .
y = kons t .
ope r a c e
nad
obr azu
s
t ím ,
hran n-úhe lníka s
Nav í c
danou
j e t e chnikou ,
je
datovou
možné
že
se
každou
r e a l i zovat
s t ruktur ou .
názorno s t uvažme j e dnoduchý př ípad n-úhe lníka z obr . 3 . 6 . 3 .
- 79 -
která
Pro
y 10 8 6 4 2
o
4
2
6
10
8
12
14
x
16
Obr . 3 . 6 . 3 Vyj ádř íme-li
r ovni c i
př ímky ,
na
kter é
leží
daná
ús e čka ,
pak
( �y= 1 ) : 1 m Pro n-úhe lník
z
+ x. 1
obr . 3 . 6 . 3
+ x. 1
=
dos táváme
nás l e duj í c í
n-tice
ve zmeme ten kon cový bod , který má minimální s ouřadn i c i y ) . yo
hrana e e e e e e
1 2 3 4 S 6
J e zř e j mé , datová kte r é
xo
'
Yl
,
[
1
7
3
[
3 ,
2 ,
9 ,
[
7 ,
9 ,
9 ,
[
7 ,
9 ,
[
5 ,
14 ,
[
1
7 ,
�x , -5
�y ] 2 ]
O , -7
Xo
6 ]
,
2 ]
9 ,
5 ,
2 ]
9 ,
O ,
4 ]
5
7 ,
4 ]
ž e z důvodů rychl o s t i mus í být j e š tě zvo l ena vhodná
s truktu r a , daná
'
( za
ř ádka
která umožňuj e p r o t íná .
rychlé vyhledávání
Jedním
z
možných
s truktur a , kte r á j e zobr azena na obr . 3 . 6 . 4 .
- 80 -
ř e š en í
t ě ch hran , je
datová
TAB Xo
9
�X
Yl
směrník na další
�Y
:;:.o
e4
e3
8 7
eS
6
:;:.ol
S
14
9
X
4
O e2
4 3
e
2
e6
l
7
S
1 O
Obr . 3 . 6 . 4 Uvedená datová s truktura j e výhodná z někol ika důvodů , v š ak
proto ,
z a č ínaj í hran ,
že
na
umožňuj e
daném
které
r e p r e zentace
ř ádku ,
vy tvoř i t
používá
z e j ména
se
uve denou
r e p r e zent aci
vodor ovné
resp . řádku
l e t ade l .
v
modifikovat k
aktivní ch hr any
a
hodnotám hran .
Je
př ípady ,
nalé z t
ty
různých že a
nutné
kdy
s imulátor e ch ,
pro
nap ř .
j e nutné
z ř e t ě zený vhodně
ř ádka
datová
Uvedená
to
které
aktivn í ch
š r afování apod .
tak,
xo '
hr any ,
s e znam
t zv .
protínaj í .
Pro operace plnění ,
v zhl e dem
i v s e znamu
rychle
aktuální
p i l o t áž e
us pořádaný
ve lmi
z e j ména
s e znam
každou
je
ř ádku
r e p r e zentovat
vr cho l em
n-úhe lníka
p r o chází nebo se j e j do týká . Ra s t rová řádková konverze
Te chnika
ř ádkové
obj ektů
využ ívá
ur č i tou
nevýhodou,
procesor
konverze
ope r a c í neboť
podporuj í c í
v ne
umožňuj í cí
pohyblivé pro
pohybl ivou
ř ádové
v š e chny řádovou
- 81 -
dobrou
č ár ce .
ap l ikace čárku .
r ep r e z en t a c i je
Proto
Toto
je
použ íván je
možné
použi t
t zv .
r as trové
výhoda s p o č ivá v tom ,
fádkové
Yiz
o br . 3 . 6 . S .
Jej i
že poskytuj e ne j en r a s t r ovou r e p r e zentaci
zobrazovaného obj ektu , s reprezentaci
konve r z e ,
ale j e s ni možné nav i c i p r a covat j ako
hr anovou .
Pro
obj ekt
na
obr . 3 . 6 . S
d o s t áváme
datovou s trukturu uve denou na obr . 3 . 6 . 6 .
( 5 ,11) (17 ,10)
(8, 7)
(0,1) (15,0)
Obr . 3 . 6 . S y. 1
N
(X ' Y ) l r
11
2
( 5, 5 ) - ( 5, 10)
10
2
( 5 , 5 ) - ( 1 1 , 17 )
9
2
( 4, 4 ) - ( 17 , 17 )
8
2
( 4, 4 ) - ( 17 , 17 )
7
4
( 3, 3 ) - ( 8, 8)
6
4
( 3, 3) - ( 6, 7)
( 1 0 , 1 1 .) - ( 1 7 , 1 7 )
5
4
( 2, 2 ) - ( 4, 5 )
( 12, 1 3 ) - ( 17 , 17 )
4
4
( 2, 2) - ( 6, 7)
( 14, 1 5 ) - ( 17 , 17 )
3
4
( 1, 1 ) - ( 8, 9)
( 1 6 , 17 ) - ( 17 , 17 )
2
2
( 1 , 1 ) - ( 10, 1 1 )
1
2
( 0, 7 ) - ( 12, 13)
O
2
( 8, 14) - ( 14, 1 5 )
(8, 9)
kde N j e p o č e t průs e č iků hran s danou f ádkou y . 1 Obr . 3 . 6 . 6 - 82 -
( 17, 17 )
Uve dená
datová
s truktura
B r e s enhamovým a lgor itmem .
může
být
vygene r ována
upr aveným
Pro každý ř ádek pak dos t áváme dvo j i c i
hodno t < x ' x > ur čuj í c í začátek a konec aktivovaných bodů r a s tru l r pro danou s ouřadn i c i y . . V př ípadě , že zobr azovaný útvar j e 1
uzavř ený ,
p ak
pro
každou
řádku
do s t áváme
dvě
dvo j i c e
hodnot
,x > . Hodno ty < x ,x > p ak ur čuj í vně j š í ,x > a <x r l r r l i+ 1 i i i i+ l i+ 1 hran i c e zobrazovaného útvaru . Datovou s trukturu je možné <x
l
modifikovat i pro př ípad použ ití kruhových obl ouků , Uve dená
datová
zap i s ova č e , být
je
vhodná
i
pro
e l ektros tat i cké
pokud se nedos áhne ur č i té s lo ž i t o s t i ,
výhodn ě j š í
obraz .
s truktura
použí t
záznam
př ímo
do
viz kap . 3 . 7 . od k t e r é může
pamě t i
r e p r e z entuj í c í
Datovou s trukturu l z e t é ž modifikovat p r o př ípad použ i t í
barev č i r ep r e zentace p l o ch v pros toru . S t r omová struktura QUADTREE
Použ i t í
hierar chi ckých
v p o č í t a čové použita
grafice
ve lmi
a prudký
datových
pokles
čas té .
pamě t í
umo žni l
V
Ni cméně při
v š ak
je
v
podstatě
tzv .
ve lmi
vlas tně z Warno ckova algor itmu , viz kap . Na
obr . 3 . 6 . 7 . a
je
naznačen
s odpovídaj í c ím o č í s l ováním . n-úhe lník
r e p r e zentuj e
skutečný tva r v r as tru,
pos tup
V př ípadě
datovou
byla
e l ektroniky integr a c e
quadtr e e s
a
octrees
a l e na úrovni
j e dnoduchá
a
vy chází
7. 6. d ě l ení quadt r e e s
s trukturou
viz obr . 3 . 6 . 7 . b .
r ep r e zentaci
hus t o ty
I
Myš lenka
p ř ípadě
vývoj
k reprezentaci obj ektů na úr ovni niko l iv defini c , ras tru .
je
k
vzr�s tu
použ i t í
s t r uktur
p ř e d chozím
s truktur a
obj ektů .
ceny
polovodi čových prvků
s t r omových
datová
hierar chi cká
j e dnotl ivých
či
oblas t i , se
t ak ,
spolu
např . že
daný
odráží
Datová s truktur a daného
n-úhe lníka má pak tvar , který j e uve den na obr . 3 . 6 . 8 . Výhodou s tr omové datové s truktury quadtr e e s j e , i ur čení
takových ve l i čin,
j ako
je
obsah ,
těžiště
ž e umo žňuj e apo d .
Počet
úr ovní s tr omu j e pak dán veliko s t í ne j menš í. zobr az i t e lné p l o š ky , což bývá v ě t š inou p ixe l .
- 83 -
I I
U6 I
1
3
2
Obr . 3 . 6 . 7
o
1
2
3
o
1
2
3
o
1
2
Obr . 3 . 6 . 8
- 84 -
3
o
1
2
3
o
1
2
3
3 . 7 Repr ezentace n-úhelníků a oblastí
Až
dosud
uve dené
r e p r e zentace
úse ček
algor itmy nebo
a
metody
n-úhe lníků .
ř e š ily
V
p r o b l e mat iku
te chni cké
p r ax i
v š ak
nas távaj í s l ož i t ě j š í p ř ípady , kdy j e nezby tné de finovat o b l as t i , j e j i chž hr an i c e j s ou tvořeny j ak ús e čkami , čás tmi kdy
kuž e l o s e čky .
oblasti
Naví c
o b s ahuj í
analogi ckým způs obem . l omenou
čárou ,
j e ne zbytné
" díry " ,
tak i oblouky ,
zvl ádnout
j e j i chž
i
hran i ce
ty
resp .
s i tua c e ,
j s ou
tvoř eny
Je p o chop ite lně možné apr oximova t o b l ouky
avš ak
to
má
za
nás l e dek
neúměrné
zvě t š ení
ve l iko s t i datových s truktur i rychl o s t výp o č tů a vykr e s l ován í . Reprezentace n-úhe lníků
V mnoha s t rukturu
ap l ika c í ch
použí t
že
n-úhe lníka .
j doucí vr cho ly Vlas tní
způsob
Ne j j e dnoduš š ím
datovou
použ i t í s e znamu s ouřadn i c vr cholů, kte r é j s ou uspoř ádány t ak , s obě
n-úhe lníka .
j e dnodu chou
je
po
defin i c i
ne zbytné
p ř ípadem
dva
pro
je
de finuj í
odpov ídaj í cí
r e al i zace
datové
hr anu
s truktury
daného se
liší
případ od př ípadu , např .
GKS předpokládá dvě j e dnorozměrná p o l e ,
a
a
to
pro
Součás t í
s ouřadn i c e dat
V někt e rý ch
p ak
x
bývá
př ípade ch
s ouřadn i c e prvého bodu ,
souřadnice y
údaj , je
který nutné
zvláš ť ,
počet
přidat
kon e c
na
vr cho lů . s e znamu
aby se zaj i s t i l o " uz avření " n-úhe lníka .
6 5 4 3 2 1 o 1
obr . 3 . 7 . 1 .
spe c;: ifikuj e
y
o
viz
2
3
4
Obr . 3 . 7 . 1 - 85 -
5
6
x
Souřadn i c e vr cho lů
Počet vr cholů N = 4
x
2
6
4. 5
4
Y
1
2
5
2
Vykr e s lení
daného
n-uhe lníka
je
pak
algo r i tmem 3 . 7 . 1 . MOVE TO ( X [ N ]
,
Y[N]
)i
for i : = l to N do begin L I NE TO ( X [ i ]
, Y[i]
)i
end
Algor itmus 3 . 7 . 1
s
01
Obr . 3 . 7 . 2 - 86 -
možné
r e a l i zovat
např .
Uve dená datová s truktura v š ak není p ř í l i š vhodná p r o s lo ž i tě j š í manipulace , p l o cha
neboť
podílí
na
neposkytuj e defin i c i
informa ce
o
zobr azovaného
tom ,
j ak
obj ektu .
se
daná
Nav í c
j s ou
problémy s r e p r e zentací n-úhe lníků , které obsahuj í díry . Zobrazovanou hie rar chi cké
s cénu
je
obe cně
s t ruktury ,
viz
možné
obr . 3 . 7 . 2 ,
p okud
popsat
pomo c í
j s ou
o b j ekty
tvoř eny n-úhe lníky , které j s ou definovány s ouřadni c emi vr cholů . Uve denou datovou s trukturu lze modifikovat nebo r e a l izovat mnoha způs oby ,
např .
definována polí
s
lze
vyne chat
vr choly ) ,
ome zením
nebo max .
de fini c i
realizaci po č tu
uve dená
v kar tografi i . např .
hr an i c e
datová
pr ové s t
podř ízených
dynami ckých s e znamových s truktur . něž
hran
( p l o cha pomo c í uzlů
je
p ak
s ta t i ckých či
pomo c í
Ni cméně exis tuj í apl ika c e ,
s truktura
není
pos t a čuj í c í ,
pro
např .
Hran i c e kar tografi ckých obl as t í n e j s ou p ř ímkové , s tátů ,
ale
j de
obe cně
o
l omenou
obr . 3 . 7 . 3 .
-------
Obr . 3 . 7 . 3 - 87 -
čáru,
viz
V
tomto
de finována n e j en vr choly l V ' V , V , V , ale i vr cho ly l omených č ar S ' S ' S ' S · l l 4 3 2 4 3 2 Nav í c může být požadováno i dal š í hierar chi cké d ě l en í , neboť např .
př ípadě
kon t inent
je
např .
je
P
rozdělen na republ iky ,
pak j s ou r o z dě l eny na č leněna .
p l o cha
Z uve deného
s táty je
či hrabs tví ,
zře j mé ,
že
kr á l ov s tví
apod .
kte r á mohou být
návr h
da tových
Ty
dále
s t r uktur
podsta tně ovl ivní r ea l i zaci algor itmů .
Uvažme
oblas t ,
j e j íž hranice
je
tvoř ena
j ak ú s e čkami ,
t ak
i obl ouky a která obs ahuj e t é ž " díry " , viz obr . 3 . 7 . 4 .
Obr . 3 . 7 . 4 Pokud nemaj í být kruhové obl ouky aproximovany l ineárními ús eky , je
nezbytné
kuže l os e čky , obl ouku
o dvodit
j e dnotl ivé
v i z kap . 4 .
definovat
vhodné p odo tknout ,
ge ome t r i cké
t r an s forma c e
i
pro
Navíc j e též nutné kromě kon cových bodů
orientaci
oblouku
z
bodu x
bodu x . J e 2 že p ř i změně mě ř í tka obe cně do chází ke změně l
do
kružn i c e v e l ip s u . Kuž e l o s e čky j e možné repre zentovat pomo c í kvad r a t i cké formy p ř i použ i t í homogenních s ouřadnic : x
=
o
- 88 -
Lze
pak
pro
v i z kap . 4 .
ně
definovat
j edno t l ivé
geome t r i cké
Datová s truktur a repre zentuj í c í . o b l a s t
obsahovat n e j en kon cové body ,
t r an s forma c e , b e z děr mus í
ale t é ž i orientaci a koe f i c i enty
repre zentuj í c í kuž e l o s e čku . Kuž e l o s e čka j e dána r ovnicí ax
2
+ 2 bxy + cy
2
+
2dx + 2 ey + f = O
a tedy p ř i použ i t í kvadrat i cké formy k záp i s u dos táváme :
x
� [ x ,
y ,
1 ]
-
[
a
b
d
b
c
e
d
e
f
Pro r ovni c i př ímky a x + b Y
+
c = O
] [� ]
j ako s p e c iální př ípad kuž e l o s e čky pak dostáváme :
x
Je vhodné
= [ X , y ,
po znamenat ,
l l
o
[
�
�
O
a/2
O
b 2
b/2
a/2
že mat i ce A j e
x
syme t r i cká ,
obe cně 6 koe f i cientů k repre zentaci j ak �ř ímky ,
a
=
stačí
O
tedy
tak i l ibovolné
kuž e l os e čky . Ni cméně j e v ě t š inou zapotřebí úse čka , e l ip t i cký obl ouk apod .
To znamená ,
informa ce
bode ch ús e čky ,
o
koncových
resp .
že j e nutné uchovávat t é ž i resp .
oblouku též informa c i ur čuj í c í or ientaci .
- 89 -
kru.hový oblouk , oblouku .
V př ípadě
3 . 8 P l nění a š r a fování
V mnoha aplika c í ch I když
je
možné
operace
nee fekt ivní
ze j ména
tato
j iných
používá ope r a c í
r ea l i zovat
apl ikováním Pro
se
zař í zení
š r afování ,
oře závání , pro je
p r in c ipe ch ,
viz
ras trová
možné
které
resp .
a
š r afování .
p lnění
n-úhe lníka
kap . 6 . ,
zař í zení
r e a l i zovat j s ou
plnění je
s
tento
př ímým
algor i tmy
vhodně j š í
z
způsob
p ř í s tupem .
zal ožené
h l e di s ka
na
př ímé
r e a l i z a c e pomo c í hardwaru . Semínkové p lnění
Algor i tmus j e dním
z
s emínkového plnění
n e j j e dnoduš š í ch
algo r i tmů ,
aktiva c i - č tyř s ous e dních bodů , body
v
dal š ím
( s e e d fil l )
kr oku .
je
který
je
p r avděpodobně zalo žený
na
které pak s l ouž í j ako s tar t ov a c í S emínkové
p lnění
l ze
p op s at
algo r itmem 3 . 8 . 1 . procedure SEED F ILL ( x , y ,
var i :
{ s tar tova c í bod }
bc,
{ barva hran i c e }
fc :
integer { barva p lnění }
)i
integer i
begin i : = Ge t P ix e l Color ( x , y ) i
{ vrací barvu p ixelu ( x , y )
}
i f ( i < > b c ) and ( i < > fc ) then begin S e t P ixe l Color ( x ,
y ,
fc ) i
{ nas t aví barvu p ixelu ( x , y )
}
S EED F ILL ( x+ l , y ,
bc ,
fc ) i
S EED FILL ( x - I , Y ,
bc
fc ) i
S EED F I LL ( x , y+ l ,
bc
fc ) i
SEED F I LL ( x , y- l ,
bc ,
fc ) i
end end { SEED F I LL } i
Algoritmus 3 . 8 . 1 Uve dený
a l gor i tmus
neefektivní , které
byly
je
zalo žený
na
pro
a l t e rnativ
je
velmi
neboť po skytuj e pro dal š í úroveň r ekur z e i ty body , j iž
v
daném
nebo
předchozím
kroku
Tyto nevýhody s e ř e š í ner ekur z ivní modifika c í , z e j ména
a
rekur z i
imp l ementa c i je
např .
ve
VL S I
pos tupné
obvode ch .
plnění
- 90 -
svi s l e
ini c ial i zovány . k t e r á j e vhodná
J e dnou či
z
mo žných
vodor ovně
od
s emínka ,
p ř i č emž
se
pokr a čovac í ch bodů . p ř íp ade ch ,
viz
obr . 3 . 8 . l . a ,
využívá
zás obník
k
ukl ádání
t zv .
Uvedený algor i tmus v š ak s e lhává v někter ých
obr . 3 . 8 . l .
V
př ípadě ,
se vyplní j en spodní
který
je
čás t n-úhe lníka ,
uve den j e-li
na
z adán
s tar tovac í bod ( x , y ) , neboť semínko s e nemůže " přené s t " do horní čás t i
n-úhe lníka .
Analogi cký
př ípad
charakte r i s t i cký
pro
úzké
obdélníky j e uve den na obr . 3 . 8 . l . b .
x a)
b)
Obr . 3 . 8 . l Ne r eku r z ivní v e r z i
algor itmu s emínkového p lnění
lze
popsat
algo r i tmem 3 . 8 . 2 . procedure SCAN SEED F ILL ( x , y ,
{ s tartova c í bod }
bc,
{ barva hran i c e }
fc :
integer { barva p lnění }
proce dure Che ck and S e t ( xl , xr ,
y: var x , x O :
intege r ;
{ r o z s ah ř ádku }
integer { kontrol ovaná ř ádka }
flag : boolean ;
begin
x : =xl ; whi l e x < xr do begin
f l ag : = f a l se ; whi le ( Ge t P ixe l Color ( x , y )
<>
bc )
and ( Ge t P ix e l Color ( x , y ) and ( x < xr begin flag :
<>
) do
= true ;
x
);
x + 1 end ; - 91 -
fc )
);
{ ulož do zás obníku pixe l ,
který j e ne j v í ce vpravo }
i f f l ag then begin if ( x = xr ) and ( Get Pixe l Color ( x , y ) and ( Get Pixel Color ( x , y )
< > bc )
< > fc )
then PUSH ( x , y , s ) e l se PUSH ( x- 1 , y , S ) i
f l ag : = f a l se end i
xO : = Xi whi le «
Ge t P ix e l Co l or ( x , y ) = bc
)
o r ( Ge t P ix e l Color ( x , y ) = f c » and ( x < xr ) do
x : = x + li i f x = x O then x : = x + 1 end { whi l e } end { Che ck and S e t } i begin { ulož s ouřadnice bodu do zás obníku s
PUSH ( X , y , S ) i
}
{ pokud není zás obník p r á z dný }
whi le not EMPTY ( s ) do begin
POP ( s , x , y ) ;
{ vyber ze zás obníku s ouřadn i c e bodu }
S e t Pixe l Color ( x , y , f c ) ; { vyp lň řádku nalevo } xO : = x ; x : = x + 1 ; whi l e Ge t Pixel Color ( x , y )
< > b c do
begin S e t P ixe l Color ( x , y , f c ) i
xr : = x - l i x : = X O i
x : = x + 1 end i
{ obnovení původní s ouřadn i c e x }
x : = x - li whi l e Ge t P ix e l COlor ( x , y ) < > b c do begin S e t Pixe l Color ( x , y , f c ) i
xl : = x + l i
{ < xl , xr > j e nyní interval p lnění }
{ Nyní j e ne zbytné ur č i t , {
{
x : = x - I end i
zda v š e chny p ixe ly nad nebo p o d }
z p r a c ovávanou řádkou j s ou body hran i c e nebo j i ž byly akt ivovány .
Pokud tomu tak nen í ,
{ p okr a čovat v p lnění } Che ck and S e t ( xI , xr , y+ 1 ) i Che ck and S e t ( xI , xr , y- 1 ) i end { whi l e } end { S CAN S EED F I LL } i
Algor itmus 3 . 8 . 2 - 92 -
pak j e ne zbytné
} }
Pro
demon s t r a c i
která
je
uloženy
na
funkce
algo r i tmu
obr . 3 . 8 . 2 . a .
s ouřadn i c e
bodů ,
Po
uvažme
vyp lnění
viz
j e dnodu chou
řádku
obr . 3 . 8 . 2 . b ,
j s ou
kte r é
do
oblas t ,
zás obníku
j s ou
o zna č eny
č í s ly vyj adřuj í c ími poř adí ukládání souřadn i c bodů do z á s o bníku . Tyto body j s ou pak pos tupně vzaty j ako s tar tova c í .
a)
b)
c)
d)
Obr . 3 . 8 . 2 Kromě uvedených algor i tmů exis tuj e či
a l go r i tmů ,
např .
které
[ 2 ] , [ 34 ] , [ 6 6 ] ,
zř e j mé , vzorem,
že
p ř i čemž
metoda
založeny
na
j iných
p r in c i p e c h ,
viz
využívaj í c í ch vlastno s t í fr ame - bufferu .
uve dený
S e t Pixel Color . není
j s ou
c e l á ř ada j e j i ch modifika c í
algoritmus je
Pro
s emínka
lze
nutné
pouze
zaří zení vhodná
modifikovat
a
pozměnit
s ekven čním
se
větš inou
nás l e duj í c í . - 93 -
i
se
pro
Je
p lnění
p r o c e duru
p ř í s tup em používá
k
bodu
me toda
Plnění řádkovou konver z í
Metoda f i l l ing ) neboť
p lnění
ř ádkovou
konv e r z í
( s c an
l ine
j e vhodná pro zař ízení se s ekven čním p ř í s tupem k bodu,
požadavky
minimal i zovány . barvu ,
n-úhe lníků
na tato
kr e s l eného
konve r z i ,
p ř i čemž
a ukládaná
metoda
hlediska
měnit
řádku .
pro
data
p ř e dpokládat ,
z
obj emu
dat
mohou
Nav í c u zař ízení umožňuj í c í ch měni t
umo žňuj e
v r ám c i
výs tup
pos tupně
Metoda
účely plnění
je
modifikovat .
že
je
p lnění
se
bude
j as ,
Pro
barvu ,
na
ř ádkové
datovou
s trukturu
j e dnoducho s t
provádět ve
resp .
r e sp .
zalo žena možné
j as ,
směru
budeme
vodor ovném .
Algor i tmus p lnění řádkovou konverzí j e založen na p r in c ipu , př ímka nutné přímka
může
mít
řešit
pouze
s p e c iální
vr cholem
imp l emen t a c í
tyto
sudý
počet
př ípady ,
průs e č íků
kdy
hr ana
s
n-úhe lníkem .
leží
pro cház í ,
nebo
se
j ej
spe ciální
př ípady
v
zás adě
být
na
p ř ím c e ,
Je či
Vě t š ina
dotýká . řeší
kdy
t akto
( vi z
obr . 3 . 8 . 3 ) : leží-li p ak
se
hrana
na
p ř ímce
tato
hrana
repre zentuj í c í tj .
vynechá ,
zpr a covávaný
nepouž i j e
se
v
ř ádek , dal š ím
z p r a c ování - dotýká - l i s e př ímka zpracovávaného ř �dku vr cho l u ,
pak s e obě
hr any zpr acuj í normálním způsobem - p r o chá z í - l i př ímka zpracovávaného řádku vr cho l em , zkr á t í
j e dna
hrana
tak ,
aby
začínala
až
na
14
16
dal š ím
anebo j e nutné s ní takto zacháze t .
y 10 8 6 4 2
o
2
4
6
8
10
Obr . 3 . 8 . 3 - 94 -
12
p ak se buď
x
ř á dku ,
Pro
r e p r e zentaci
konv e r z e obs ahuj e
prvků
použ i j eme místo
z obr . 3 . 8 . 3
Ax
lze
s e znamu
v
modifikovanou a
Ay
př ímo
repre zentovat
datové datovou
hodnotu
s t ruktuře s t rukturu ,
Ax j Ay .
pomo c í
ř ádkové
datové
P ak
která
n-úhe lník
s truktury ,
viz
obr . 3 . 8 . 4 .
Tabulka hran
směrník na další
Il. X /1l. Y
;::..
8 7 e4
6 -
5
6
-
4 3
7
e5 -
-1
11
8
3/4
X
e6
3
3
1/2
X
e3
6
8
-
1
2
2/3
X
e7 =
1/2
3
X
,
e1
2
2/3
9
4
e2
o
Obr . 3 . 8 . 4 Plnění zal ožené na řádkové konverzi l z e p o p s a t a l go r i tmem 3 . 8 . 3 . 1.
Vytvoř
p r á z dný
char akte r i zovat
s e znam ty
akt ivní ch
hr any ,
hran
kte r é
AE tab ,
j s ou
který
p r o t ínány
bude p r ávě
zpracovávanou řádkou . 2.
Nas tav
index
zpracovávané
řádky
na
nej nižší
hodno t u ,
tj .
Y = O 3.
Pokud Y
s
Y max '
děl e j :
a ) z a t ř i ď prvky ze s e znamu E tab [ y ] AE tab a s e tř i ď j e podle hodnot x - 95 -
do s e znamu akt ivn í ch hran
b ) plň n-úhe lník v r ámci zpracovávané řádky tak, ty p ixe ly ,
ž e s e akt ivuj í
j e j i chž s ouřadnice x j e ur čena s ou s e dn ími prvky
v s e znamu v AE tab c ) o d s t r aň z AE tab s e znamu ty prvky ,
j e j i chž horní s ouřadn i c e
y j e r ovna zpracovávanému ř ádku d ) p r o každý zbylý prvek v s e znamu aktivní ch hr an AE tab nahr aď hodnotu x + 1 / m,
průs e č íku tj .
x
pro
nás l e duj í c í
hodno tou
řádku
př ip o č t i hodnotu inverzní smě r n i c e
e ) zvyš index zpracovávané řádky o I ,
tj Y : = Y + 1
Algo r i tmus 3 . 8 . 3 Na obr .
3 . 8 . 5 j e uve den obsah s e znamu aktivn í ch hran AE tab p r o
různé řádky v okamž iku j e j i ch zpracování .
řád e k
řád e k .
řád e k .
řád e k •
1 >1 2 3 1 l/2 1 (
e
2 >1 2 l/� 3 1 1/2 1
e
2 >1 9 4 1 2/3 1 2 >19 2/31 4 1 2/31
3 >1 3 I 3 1 1/2 1 I >�o l/� 4 >13 1/41 1 1/4 1 3 >1 11
řád e k 5
e2
.
e
7
•
3
e
Obr . 3 . 8 . 5 - 96 -
X
X
4 1 2/3 1
X
4 1 2/3 1
X
e7
e7
e7
e7
Uvedeným algo r i tmem j e možné též plnit n-úhe lník d e finovaným vzor em . ve
V tomto př ípadě j e nutné
shodě
s
defin i c í
o r ozmě ru n x m ,
obj ektu .
vzor
j e j í ž prvek definuj e j as
S e t Pixel Color ( x , zvol eným
Je - l i
vzoru .
se daný p ix e l má akt ivovat ,
Vhodně
aktivovat odpovídaj í c í p ix e ly
vzorem
Uvedený
či barvu ,
t abulkou
s e kterými
pak lze pixel aktivovat p ř íkazem : TAB [ x mod n + . 1 ,
y , l ze
pos tup
definován
pak
do c í l i t
lze
použí t
i
Y mod m + 1 ]
vyš r afování
daného
ods tr aňování
k
i
)
nevidi t e lných hran č i povr chů , viz kap . 7 .
Plnění a š r a f ování rastrovou řádkovou konver z í
V
kap . 3 . 6
Vzhl e dem
k
byl
tomu ,
uve den že
pro
prin c ip každou
r as t r ové
ř ádku
je
v
ř ádkové
konve r ze .
datové
s truktuře
obs ažena informa ce o tom , který p ixel dané oblas t i p ř in ál e ž í , zř e j mé ,
ž e a l gor i tmy plnění a š r afování j s ou ve lmi
a tedy
i
rychl é .
Algor itmus
plnění
může
být
alg . 3 . 8 . 4 . procedure F I LL AREA i var i , j , k :
{ plnění }
intege r i
begin do for y : = y . to Y mln max begin j : = l i whi l e j < p o č e t průs e č íků pro dané y do begin for k : = x [ y , j ] + 1 to x [ y , j + l ] - 1 do r l S e t Pixe l ( k , y ) i
j : =j + 2 i end end end
Algoritmus 3 . 8 . 4
- 97 -
je
j ednoduché ,
p op s án
např .
procedure HATCH AREA ;
{ š r afování } const N = 4 ; type pattern = a r ray [ 1 . . N , l . . N ] o f byte ; cons t pat :
pat tern = ( ( 1 , O , O , O ) , ( O , 1 , O , O ) , ( O , O , 1 , O ) , ( O , O , O , 1 ) ) ;
{ odpovídaj í c í vzor viz obr . var i , j , k :
3. 8. 6 }
intege r ;
begin for y .. - y begin j
:
min = 1;
do to Y max
whi l e j < p o č e t průs e číků pro dané y do
x [ y , j ] + l to x [ y , j + 1 ] - 1 do r l i f pat [ y mod n + 1 , k mod N + 1 ] = 1
begin for k
: =
then S e t Pixel ( k , y ) ;
j : =j + 2 ; end end end
Algo r i tmus 3 . 8 . 5 Š r afován í j e operace ve lmi podobná plněnl s t ím r o z d í l em , plní
vzorem,
který
Algo r i tmus 3 . 8 . 5 .
je
v
naš em
p ř ípadě
uložen
v
poli
že s e PAT .
pak ukazuj e pos tup p ř i š r afování .
Obr . 3 . 8 . 6 Uve dený vzor
na
obr . 3 . 8 . 6 vyp lní daný n-úhe lník t ak , ž e š r afy ° budou mít sklon 4 5 . Obe cně j e možné nadefinovat téměř l ibovolný
vzor vhodnou v o l bou N a nas tavením pole PAT . Vzhl e dem
k
j ednoducho s t i
mohou
r e al izovány hardwar ově . - 98 -
být
uve dené
a l go r i tmy
3 . 9 Ant i a l i a s ing
Při
zobr azování
v r a s t r ovém
úse ček
př ímek ,
pros tředí
proj evuj e
se
barva
mus í
být
vyj ádř eny
pomo c í
neboť p r o s t o r ,
diskr é tn í ch
vzorkování s e pak p r o j evuj e v zás adě tím,
ome zené
k
vzhle dem
r o z l i š ovací s chopno s t i problém vzorkování ,
e l ementů
j iných
či
v e l i č in .
j as č i P r o b l ém
že :
- ú s e čky s e zobr azuj í s typi ckým s chodovi tým p růběhem - mal é
o b j ekty ,
které
j s ou menš í než
( vl ivem
j as u ,
p ix e l ,
pods tatně
větší
se
akt ivuj e ) ,
nebo s e ne zobrazuj í vůbe c
se
kterým
do chá z í ke ztrátě informace u detailů,
buď se
zobrazuj í
daný
p ix e l
které j s ou r o změ r ově
b l í zké r o změ ru pixelu - při anima c i pohybu " obj evováním " a " mi zením " malých o b j ektů Te chniky , nazývaj í [ 64 ] ,
se
ant i a l ia s ing .
[ 109 ] .
při čem �
které Problém
v š e chny
v
snaží
Lze
je
řešit
nal é z t např .
vzorkování zásadě
tuto
l ze
řešit
používaj í
p r o b l emat iku , v
[ 39 ] - [ 41 ] ,
něko l ika
modu l a c i
se
[ 44 ] ,
p ř í s tupy ,
j as u
pixelu
k vytvoř en í doj mu " hl adkos t i " . Je dnou
ze
zákl adních
te chnik
je
r o z š í ř ený
algor i tmus p r o kre s lení ús e čky , viz algor i tmus 3 . 9 . 1 . např .
viz
[ 103 ] ,
že hodnota proměnné d ,
- 99 -
L z e ukázat ,
p ř i čemž d E < O ,
j e úmě rná v e l ikos t i obsazené plo chy p ixe lu ,
Obr . 3 . 9 . 1
B r e s enhamův
viz obr . 3 . 9 . 1 .
[I
poloviční jas
•
plný jas
1 >,
procedure DRAW ANT IAL IAS ( x 1 , y 1 ,
x2 , y2 : var x , y , d , m :
{ počáte ční bod } integer { kon c ový bod }
)i
r ea l i
begin
x : =x i y : =y i 1 1 m : = ( Y -Y ) / ( x -X ) i 1 2 1 2 a : = l -m i
d: =0. 5i
S e t P ixe l ( x , y ,
d )i
repeat if d < a then { hor izontální krok } +
d := d
m
e l se { diagonální kr ok } begin d . - d - a i
x := x
+
y + 1 end i
Y
li
S e t P ixe l ( x , y , . unt i l x = x 2 '
d )
Algor itmus 3 . 9 . 1
•
O
střed zobrazovaného pixelu
1
2
1
1
ev
"1
1
2
1
Obr . 3 . 9 . 2 Druhou možno s t í fr ekven c í , možné
tj .
realizace vytvoření
zobr a zi t .
ar itme t i ckým
P ix e l
nebo
obrazových e l ementů ,
váhovým
ant ialias ingu obrazu se
s
vě t š ím
zobrazuj e
průmě r em
viz obr . 3 . 9 . 2 . - 100 -
je
z
s
vzorkování r o z l i š ením , intenzi tou
vyp o č tených
s
vyš š í
než
je
danou
" oko lních "
Tato
te chnika
se
vzrůs taj í cím
redukčním
i zvě t š en í v e l ikos t i potřebné pamě t i . úrovn í ch j as u j s ou lepší než při
dvou barvy
512 x 512
že
bodů p ř i
r o z l i š ení
1 024 x 1 0 2 4 při
v
j is tých
me z í ch
je
kap a c i tu pamě t i n a reprezent a c i v í c e
úr ovní
j as u
úrovní ch
" věnova t "
vyžaduj e
Z exper imentů vypl ývá ,
výs l e dky z ís kané p ř i r o z l i š ovací s chopno s t i 16
faktorem
m í s to
j asu .
To
zvýš ení
znamená ,
že
r o z l i š ovací
při
s chopno s t i
l ép e či
s t e j ných
p amě ť ových nár o c í ch . Dal š í mo žnou te chnikou j e filt rování .
Vy cház í s e z t oho ,
intenz i t a p ixelu j e ovl ivňována svým oko l ím .
Obe cně l z e ř í c i ,
že že
p l at í : 00
f f
c (x, y ) = kde
H( �, � )
v bodě
je
(x, y )
00
H ( � , � ) . I ( x+ � , y + � ) d � d �
-00 -00
f i l t r a ční a
funkce ,
c ( �, �)
p r ovedení f i l t r ace .
c(x, y) =
je
I (x, y)
intenzita
je
aktivovaného
H( i, j )
=
16
[
00
00
.I
.I
po
H ( i , j ) . I ( x+i , y+ j )
4
1
2
�]
2
pro
z a l o žené
na
používaj í
t aké
zpracování
nabývaj í
na
f i l t r ování
důl e ž itos ti viz [ 4 1 ] ,
i
E
nap ř .
{ -1, 0, 1 } & j E { -1 , 0, 1 }
j inak H ( i , j ) = °
Te chniky
" r ay t r a c ing " ,
f i l tru
1 = -00 J = -oo
� při
z ís kaná
Pro diskr é tní hodnoty l z e p s á t :
p ř i čemž f i l t r a ční funkce j e dána mat i c í H , 1
inten z i t a
j iž
obrazu ,
z e j ména
[ 64 ] .
- 101 -
s
p r o o s t atní i , j
vytvořeného viz
[ 52 ] .
použi t ím
obrazu
Tyt o
se
t e chniky
te chnik
typu
3 . 10 Repr e z entace t ř írozměrných obj ektů
dosud
Až
dvourozmě rných
j sme
se tj .
obj ektů ,
S malými modifikacemi
lI;:teré
obj ektů ,
j s ou některé
datové
l e že t
obe cně
na
l ibovolné
způs o bu r e p r e zentace
r ovině
l ze j e dnot l ivé
hran i č n í ch r epre zenta c í ,
v
j s ou
r ovinné .
s truktury použ i t e lné
i pro r ep r e zentaci rovinných obj ektů v pros toru, může
r e p r e zentace
možno s t í
zabýval i
nap ř .
pros toru .
n-úhe lník Z hledi ska
způs oby r oz d ě l i t
do
skup in
nebo obj emových repre zenta c í .
Hraniční reprezentace
Hran i ční hran ,
p l o ch ,
r ep r e zentace nebo t zv .
l ze
dělit
na
r ep r e z entace
pomo c í
okř ídlených hran .
z
o
7
plocha č.2
6 8
11 2
12
8
8 15
10
(0 Y
5 x
1
Obr . 3 . 1 0 . 1 Hranová reprez entace
Tato
r ep r e z entace
j e vhodná pouze
pro
Uváž íme - l i j e dnoduché t ě l e s o z obr . 3 . 1 0 . 1 ,
j e dnoduché pak toto
apl ika c e . těleso lze
hranově r e p r e zentovat pomo c í tabulek : - t abulky s ouřadn i c vr cholů V , - tabulky
hran
H,
která
tj .
ur čuj e
vr cho ly j s ou kon cové . - 1 02 -
s ouřadn i c x , y , z , pro
p ř í s lušnou
hranu ,
j aké
Tabulka
V,
o b s ahuj í c í
s ouřadnice
j e dn o t l ivých
vr cho lů
tělesa
z o br . 3 . 1 0 . 1 , m á p ak tvar : vr cho l
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
4
O
O
4
1
O
O
4
4
4
3
3
O
O
3
3
O
O
2·
3
O
O
O
O
4
4
4
4
4
2
Tabulka H ,
definuj í c í hr any ,
obs ahuj e č í s l a vr cholů ,
kon c ovými body p ř í s lušné hr any .
hrana 1 .
2.
3.
4.
2
6
5
6
5
10
k t e r é j s ou
Pro t ě l e s o z o br . 3 . 1 0 . 1 má tvar :
6.
7.
8.
9.
10.
ll.
12 .
13.
14.
10
6
7
3
7
8
9
8
4
9
1
7
3
2
8
9
5
4
1
10
5.
15.
tabulka souřadnic vrcholů
tabulka hran
H
]
v
obsazená část
obsazená část
pV
� I-------t
pH
I-----I
�
neobsazená
neobsazená
část
část � �-----�
� '-----""
pVmax
pHmax
Obr . 3 . 1 0 . 2 Je z ř e j mé , např .
ž e uve dená datová s t ruktura není vhodná ,
o d s t r anit
j e dnoznačně např .
nevidite lné
ur č i t ,
obr . 3 . 7 . 1 .
drátěným
Proto
mode lem .
pos t a čuj í c í
pro
které
hr any je
Ni cméně
mnoho
hr any .
Z
� opisu
ohran i čuj í
někdy
také
uve dená
te chni ckých - 103 -
obe cně
danou
t ento datová
ap l ika c í .
pokud chceme nelze
p l o chu ,
mod e l
viz
nazýván
s t ruktura Pokud
by
je
s cénu
tvo ř i l o
více
těles ,
s trukturovaná
nepoužívá
or ganizace
dat .
buď
se
v
Tabulky
j ako
pole
tomto V
fyz i cky
r e al izovány
př íp ady ,
nebo p omo c í s e znamových s truktur .
a
p ř ípadě
H
( ma t i c e )
žádná
pak
mohou
být
pro
j e dnoduš š í
Př i b ě žných p o t ř e bá ch
pravděpodobně použij eme realizaci da tových s truktur ,
k t e r á j e na
obr . 3 . 1 0 . 2 . Pro
s ložitěj š í
apl ikace ,
kdy
hran a j iným grafi ckým editacím , s e znamových s truktur , nár o čně j š í , co
do
dochází
k
rušení
a
vkl ádání
j e nutné zvá ž i t mo žno s t použi t í
které j s ou pružně j š í ;
avš ak imp l ementačně
neboť někt eré pros tř edky maj í různá ome zení ,
p o č tu
prvků
tj .
Collection,
s e znamů ,
znovu
neposkytuj í
využití
uvolněné
možno s t
p amě t i .
např .
Garbage
Ten t o
způsob
r e a l i zace j e pak výhodný např . v kar tografi ckých a p l ika c í ch ,
viz
kap . 3 . 6 . Hranová
repre zentace
o zobrazovaném bod ,
je
tělese .
v l as tně
poskytuj e
Určení ,
problémem
ke
j en
zákl adní
kterým hr anám
s ekvenčního
informa c e
p ř í s luš í
prohledávání
daný
t abulky
V,
což j e p ř i r o z s áhl e j š í ch úlohách neúnosné . Reprezentace pomocí ploch
Př i
ř e š ení
nevidite lných
problému
p l o ch ,
je
o j e dnotl ivých p l o chách ,
viditelnos t i ,
ne zbytné
mít
dispozici
které dané t ě l e s o . tvoř í .
hr anový model o tuto informa ci r o z š í ř i t . P a V
k
k pře dcháze j í c ím tabulkám
H a V
e l imina ce
tj .
informa ce
J e nutné tedy
Dop lněním tabu lky p l o ch dos táváme
j i ž datovou
s trukturu , která obsahuj e informa ce o p l o chách a j e j i ch vazbě na hr any a vr choly .
Pro t ě l e s o z obr . 3 . 1 0 . 1 má t abulka P tvar
číslo
počet
č í s l o hr any
p l o chy
hr an
ohrani čuj í c í plo chu
1
5
1 ,
2 ,
3 ,
4
2
4
2
6
7
8
3
4
7 ,
9 ,
4
5
12 ,
13 ,
5
5
6 ,
9
10
6
3
4 ,
11 ,
14
7
4
1 ,
8 ,
15
,
12
5 tabulka P
15
5 ,
14 , 11
,
10 3
13
Tabulka 3 . 1 0 . 1 - 104 -
Někdy
se
j e š tě
n-úhelníky
tabulka
H
rozš iřuj e
o
informa c i ,
Tabulka H '
obsahuj í danou hr anu .
které
dva
má p ak p r o
těleso
z obr . 3 . 1 0 . 1 tvar :
hrana
H/ =
Prvé
6.
7.
8.
9.
10.
ll.
12.
13.
14.
15.
10
6
7
3
7
8
9
8
4
9
9
10
1
7
3
2
8
9
5
4
1
10
5
1
1
1
2
2
2
3
4
5
3
4
4
3
5
6
4
5
3
7
5
5
6
4
7
6
7
1.
2.
3.
4.
1
2
6
5
2
6
5
1
1
7
2
5.
tabulky H '
dva ř ádky
obsahuj í
dva ř ádky obs ahuj í indexy ploch, Je o bvyk l é ,
indexy vr cho lů hr an ,
druhé
j imiž j e hrana de finována .
že s e znam hran v tabul ce P j e uspoř ádán o bvyk l e
v j ednom smě r u ,
a pak j e možné i tabulku hran H vyne chat
modifikované tabulky P '
uvé s t p ř ímo vr choly dané p l o chy .
P ak p r o
tvar
t ě l e s o z o br . 3 . 1 0 . 1 m á tabulka P ' číslo
počet
č í s l a vr cho lů
p l o chy
vr cho lů
p l o chy
1
5
1
2
3 ,
4 ,
2
4
2 ,
8 ,
7 ,
6
3
4
15
12 ,
9 ,
7
4
5
13
5
5
5
11 ,
6
3
7
4
,
a do
5 tabulka P '
14 ,
10 ,
12
3 ,
6
9
10
4 ,
11 ,
14
1 ,
13 ,
15 ,
,
8
Tabulka 3 . 1 0 . 2 Pro vnitřní r epre zentaci j e v š ak vhodné i z tabulky P ' tabulky P a H s tím, i
informa ce
využ i j e např . Uve dené
o
odvodit
že u odkazu na hr anu v tabul c e P j e ulo žena
or ientaci
hr any .
Ta to
informace
se
s
výhodou
k urychlení procesu e l imina ce nev i d i t e lných hran .
datové
s truktury
l ze
opět
s e znamů .
- 105 -
r e a l i zovat
pomo c í
polí
nebo
Reprezentace " okřídlenými hranami "
D ř íve uve dené dal š í ch
datové
p o t ř e bných
s truktury neposkytuj í možno s t uložení
informací .
informa ce
mnoho
s ous edn í ch
apl ika c í
je
j i s té
vr cho l e c h .
Z tohoto důvodu byl a navr žena datová s t ruktura známá ( okř ídlená hr ana ) ,
viz
p l o chá c h ,
vhodné
uchovávat
j ako winged edge
o
Pro
[ 168 ] ,
hranách
[ 44 ] ,
či
která
je
znázorněna na o br . 3 . l 0 . 3 .
A další hrana I
AV
ll
AH 4 2
AV
AP 2
AP I AH
AH
21
2
AH
13
H
III III
Pi - i-tá plocha H ij
-
\
\
I
seznani hran seznam vrcholů seznam p loch
'--�
j-tá hrana od vrcholu i-tého
Obr . 3 . l 0 . 3 J e j í výhodou j e ,
že umožňuj e uložení informací o hran á c h ,
které
tvo ř í ur č i tou p l o chu ,
a l e t é ž informa ce o s ous e dn í ch p l o chách č i
hr anách .
uchovat
Nav í c
lze
urychl i t ř e š ení různých úloh . téměř
výhr adně
s e znamových
i Při
" or ientac i "
p l o ch ,
fyz i cké r e a l i z a c i
s truktur .
V tomto
se
př ípadě
doplnit j e š t ě dané s truktury o nás l e duj í c í odkazy : - 106 -
což
může
používá je
nutné
- odkaz na dal š í hr anu v s e znamu v š e ch hr an , - odkaz n a dal š í p l o chu v s e znamu vš e ch p l o c h , - odkaz na dal š í vr cho l v s e znamu vš e ch vr cho lů Uve dené s e znamy p ak bývá vhodné real izovat j ako obousmě rné . Pro hr anu h j e tedy obe cně možné ukl ádat tyto informa c e : - odkazy na vr choly v
l
a v
2 - odkazy na p l o chy P l a P 2 o dkazy na hr any h a h , kte r é j s ou čás t í hr an i c e p l o chy P l ll 24 a in c i duj í s vr cho lem v nebo v l 2 odkazy na hr any h a h , které j s ou čás t í hran i c e p l o chy P 2 21 13 a in c i duj í s vr cholem v nebo v l 2 a př ípadně o dal š í dodate čné informace , hrana
je
v i d i t e lná ,
či
zdali
neviditelná
hrana j e pomo cná
Tyto informace s e pouzlvaJ l např .
p ř i aproximaci v á l c e v í c e bokým
hranolem nebo v př ípadě p l o ch s
" dě r ami " .
Informace v z t ahuj í c í
s e k p l o chám P ' . . . , P se při zpra covávání hr any h neuvažuj í . l 7 Informa ce o p l o š e j s ou uloženy v oatové s truktuř e , kte r á kromě j iného obs ahuj e : - uka z a t e l na l i bovolnou hranu , která tvoř í j e j í hran i c i koe f i c ienty A ,
B,
C,
D rovnice r oviny , n a n í ž p l o cha l e ž í ,
tj .
Ax + By + Cz + D = O Reprezentace s amotného t ě l e s a j e pak kromě j iných úda j ů tvoř ena třemi cyk l i ckými s e znamy ,
a to :
- s e znamem p l o ch - s e znamem hran - s e znamem vr cho lů viz obr .
3 . 10. 3. b.
Původní adr e s
na
imp l ementace počítači
byla
PDP- I O
a
zakládání a manipulaci s uzly , nad
daty ,
odkazů ,
p ř i č emž
viz [ 1 6 8 ] ,
datové
provedena
v
obsahovala
j azy ce 16
s ymbo l i ckých
podp r o g r amů
pro
9 podprogramů p r o v l a s tní p r á c i
s truktury
obs ahovaly
22
různých
typů
[ 169 ] .
Pro př ípad t ě l e s a z obr . 3 . 1 0 . 4 má pak datová s truktur a tvar uve dený na obr . 3 . 1 0 . 5 a 3 . 1 0 . 6 . - 107 -
4
6
CD 3
2
5
l:: :.
I
Obr . 3 . 1 0 . 4
e zn rn všech ploch P
l
////
,, �\ H i--
(,
seznam všech vrcholů
am všech hran
- - - - - - - - - - - - - -- -
Obr . 3 . 1 0 . 5 - 108 -
->
Odk az na prvn í hranu dané plochy
2
h rana H l je společná plochám I a 4 a inciduje s hranami H 2 ' H 3 ' H 4 ' H 5
Obr . 3 . l 0 . 6 V př ípadě ,
že daná p l o cha obsahuj e
poměrně j e dnoduš e tak , z j iného
obrysu ) ,
které
" díru " ,
l z e s itua c i vyř e š i t
ž e s e vyberou dva vhodné vr cho ly se
spoj í dvěma hranami ,
j ež
se
( každý o zna č í
j ako pomo cné a nevidite lné , v i z obr . 3 . l 0 . 7 .
Obr . 3 . 1 0 . 7 - 109 -
------
Kr omě r ov inných p l o ch l ze použí t i p l o chy analyt i cké , exp l i c itní či parame t r i cké . koul e ,
anul o i d
apod .
se
Při použ i t í analyti ckých p l o ch typu
ve
ve lké
vě t š ině
aproximuj í pomo c í l ineárních p l o š e k ,
s y s témů
tyto
p ak
nemus í
být
popis
p l o chy
použít obe cných parame tri ckých p l o ch . n a l é z t např .
p l o chy
neboť v opa čném p ř ípadě by
byl o nutné ř e š i t obe cně ne l ine ární s ous tavy r ovn i c . ap l ika c í ch
a ť už
znám
a
V někter ých
pak
je
možné
Je j i ch popis a použi t í l z e
v [ 163 ] .
Je z ř e j mé ,
ž e datová s t ruktur a okř ídl ených hr an není vhodná
pro zadáván í dat ,
ale pouze pro vnitřní r e p r e ze n t a c i t ě l e s .
Obj emová reprezentace těles
Obj emové
r ep r e zentace
pomo c í o c t r e e a tzv .
těles
lze
rozdě l it
na
r e p r e zentace
CSG s tromů .
D
Obr . 3 . 1 0 . 8 Reprezentace pomocí CSG stromů
Až dosud uve dené te chniky repre zentace t ě l e s umo žňovaly j en velmi tě žko výp o č e t me chani ckých veli čin , t ě l e s a apod . těle s ,
j ako j e t ě ž i š t ě ,
Tyto možno s t i poskytuj e t zv .
j e j íž
j e dna
r epre zentace
je
geome trie
těles "
Ge ome try - CSG ) .
Základem
repre zent.ace
tělesa, kvádry ,
kterými
mohou
být
koul e ,
ale také polopros tory .
obj emová r e p r e zentace
též
" kons t rukt ivní
obj em
známa
pod
( Cons tr u c t ive j s ou
vál ce ,
t zv .
kuže l e ,
názvem Solid z ákl adní
anu l o i dy ,
S těmito t ě l e s y l z e p ak p r ovádě t
- 110 -
zákl adní
g e ome t r i cké
zmenš en í oper a c e
či
trans formace ,
zvě t š ení .
s j e dno cení ,
Naví c
je
průniku ,
j ako
pak možné
t zv .
CSG
p omo c í
s tr omů ,
mno ž inové
binární ch
j e j i chž
operace ,
nebo
i mno ž inové
S l ožená t ě l e s a j s ou pak
obs ahuj í
použité
rotace ,
K p o p i s u zákl adní ch
hierar chi ckých
uzly
o
posuv ,
p r ovádě t
rozdílu apod .
t ě l e s s e použ ívá analyti ckého vyj ádření . r e p r e z entována
je:
s truktur
informace
geome t r i cké
o
nebo typu
t r an s forma c i
a j e j í ch parame t r e ch . Z obr . 3 . 1 0 . 8 j e zř e j mé ,
že výs ledné t ě l e s o l z e s l o ž i t j ako
A u B ) u C ) - D
«
neuvažuj eme - l i
geome t r i cké
t r ans formace ,
tj .
ope r a c e
posuvu
apod .
rotace
rotace
/ � x . tt / 2
A
x
y . 1t / 2
y
Obr . 3 . 1 0 . 9 Výhodou
CSG
s tr omů
je
úsporno s t
popisu
a
mode l ován í ,
avš ak p ř i zobrazování vznikaj í p r o b l émy ,
řešit
vytvořením
buď
t e chnik , t r a c ing ,
které
hran i ční
hraniční
viz kap . l . 7 ,
r e p r e zentace ,
reprezentaci
a které s e s tále - 111 -
anebo
nepo t ř e buj í ,
s nadno s t které
lze
použ i t ím nap ř .
r ay
čas tě j i používa j í .
Jako
j e dnoduchý p ř íklad na CSG s tr omy uvažme průnik t ř í o r t o gonál n í ch válců .
Pak
CSG
s t r om má
tvar
uvedený
na
obr . 3 . 1 0 . 9 .
Výs l e dné
t ě l e s o má p ak v š e chny o r togonální průmě ty s t e j né a j eho tvar j e ukázán na o br . 3 . 1 0 . 1 0 .
těleso vzniklé průnikem tří ortogonálních válců o stejném průměru
nárys
bokorys pohled zleva
půdorys pohled ze spodu
Obr . 3 . 1 0 . 1 0
spodní zadní roh
směr pohled u
Obr . 3 . 1 0 . 1 1 - 112 -
S t r omová s t r uktura OCTREE
S t r omová
datová
s truktur a ,
nazývaná
k r ep r e z en t a c i pros torových obj ektů .
octre e ,
se
používá
Vznikla p r o s tým r o z š íř ením
datové s truktury quadtree o dal š í rozměr a v l as tně j de o výčet p r o s tor ových e lementární ch prvků , Je
zř e j mé ,
V datové
že
j de
v
s truktuře
zás adě
o
odpovídá
které
způsob
j s ou
t ě l e s em obs a zeny .
defin i c e
každému
uzlu
daného
o b j ektu .
p r o s torová
oblas t ,
kt e r á j e r ep r e z entována kry chl í . Cí s l ování s ? naznačením
obla s t í pos tupu
je
ukázáno
dalš ího
na
mo žného
obr . 3 . 1 0 . 1 1
dě lení .
Toto
s p o lu
dělení
je
možné až do t akové úrovně , kdy pros torový e l ement j i ž n e l z e dále dělit .
Tento e l ement s e nazývá voxe l ,
p ř e d s t avy
p ixe lu
r e p r e ze n t a c e
je
o dal š í
to ,
že
třetí
umožňuj e
což j e v l a s tně r o z š íř ením
rozmě r . snadné
Výhodou ur čení
této
obj emu ,
datové těžiš tě
apod . Pro zobr azení v š ak j iž nelze př ímo použí t
t e chniky uve dené
v kap . 5 .
Ne j j e dnodu š š í způs ob zobrazení datové s t ruktury o c t r e e
je
p ř evod
j ej í
do
datové
s truktury
zobr a z i t e l emen t árním způsobem . rekur z ivním pos tupem [ 8 ] , type oct_node_ptr oc t_entry
=
quad t r e e ,
k t e r ou
l ze
j iž
Vlas tní př evod l z e pop s at např .
viz alg . 3 . 1 0 . 1 .
\
A o c t_node i
record
=
case homogeneous boo lean of
{ předs t avuj e uzel s tr omu c e l ou oblas t ? true :
( co l or : ( chi l d :
f a l se :
integer ) i
{ barva pros torové oblas t i }
oct node_ptr )
end i
{ r e cord }
end i
oct_node = a r r ay [ O . . 7 ] of oct_entr Y i quad_node_pt r = A quad_node i quad_entry
=
record
ca se homogene ous : t r ue : f a l se :
( color : ( chil d :
boolean o f integer ) i quad_node_ptr )
end i end i
}
{ r e cord }
quad_node = a r ray [ O . 3 ] of quad_ent r Y i var newquad t r e e : quad_node_ptr i backcolor : .
- 113 -
intege r i
procedure conv e r t o c t to_quad ( o c tree : oct_node i _ _ var quadtree : quad node ) i va r k :
integer i
begin for k : = O to 3 do
qua d t r e e [ k ] . homogene ous
begin
true i
if o c tr e e [ k ] . homogene ous then if
( o c t r e e [ k ] . color > - 1 )
then { př ední oktant j e plný }
quadtree [ k ] . color : =octree [ k ] . color { p ř e dní oktant j e prázdný }
e l se
i f o c t r e e [ k+ 4 ] . homogeneous then i f ( o c t r e e [ k+ 4 ] . color > - 1 ) then { př e dní oktant j e pr ázdný ,
zadní p lný }
quadtree [ k ] . color : =o c t r e e [ k+ 4 ] . c o l o r e l se { přední a zadní oktant j � p r á z dný }
quadtree [ k ] . color : =backcolor e l se begin { p ř e dní prázdný,
zadní smíš ený }
quadt r e e [ k ] . homogeneous : =f a l se i new ( newquadtr ee ) i quadtree [ k ] . chi l d : = newquadtr e e i c onve r t_o c t_ to_quad ( o ctree [ k+ 4 ] . chil d A , newquad t r e e A ) i end e l se begin { p ř e dní smíšený ,
zadní není ne znám }
qua d t r e e [ k ] . homogene ous : = f a l se i
new ( newquadtr e e ) i
quadtree [ k ] . chi l d : = newquadtre e i conver t _o c t to quad ( o c t r e e [ k+ 4 ] . chil d A , newquadtr e e A ) i _ _ conver t _o c t_ to_quad ( o c tree [ k ] . chi l d A , newquadtre e A ) i end end
{ cyklus for }
end i
Algor itmus 3 . 1 0 . 1 Podrobně j š í informace o použ ití s t romových datových s t ruktur l z e n a l é z t v dos tupné l i t e r atuř e , viz např . - 114 -
[ 16 5 ] - [ 1 67 ] .
5.
Literatura
[ 1 ] Akimot o , T . ,
Mas e , K . ,
S e l e c ted Ray Tracing , [ 2 ] Acland, B . , We s t , N. : Display 1980,
System,
in [ 6 4 ] ,
Re al
Computer
Anima tion
Graphics
on
a
Frame
( S I GGRAPH ' 8 0 ) ,
S tore
Vol . 1 4 ,
The Edge F lag AIgor ithm - A Me thod for
Ras ter S can Displays ,
IEEE Tr ans .
on Computers ,
Vol .
C30,
pp . 4 1 - 4 8 .
[ 4 ] ACM Computer Phi lade lphia , [ 5 ] Angel l , I . O . : Gr aphi c s ,
1 984,
ACM 1 9 8 4 . A
Practical
Cas ciol a , G . :
Pract ice ,
Proceedings o f the
S c ience Conference ,
MacMil l an Pres s ,
[ 6 ] Alvis i , L . , in
pp . 2 9 - s 0 .
pp . 1 8 2 - 1 8 8 .
[ 3 ] Ackl and , B . , We s t , N . : 1981,
Time
1989,
Pixel
Suenaga , Y . :
Hashimoto , A . ,
TR
Intr oduct ion
to
Computer
198 5 .
Two and Four Ar ray Mask AIgor i thms
Dep t .
of
Mathematics ,
Univ .
of
Bologna ,
1 988 . [ 7 ] Alvi s i , L . ,
Cas ciol a , G . :
TAM
r ivisi tato :
un
me t odo
rapido
ed a s t to per la rappr e s entazione prospe t t i c a di supe r fi c e , P IXEL No . 1 0 ,
1988,
pp . 1 5 - 2 4 .
[ 8 ] Baker , M . P . , Hearn , D . :
Computer
Internat ional Edit ion,
[ 1 0 ] Bar t s ch , H . J . : [ 1 1 ] Berge r , M . :
CACM ,
Computer
Vol . 1 7 ,
[ 1 4 ] Birren, F . : York,
Vo l . 1 6 ,
with
Menlo Park,
No . 3 ,
pp . 7 0-7 7 .
SNTL ,
1 97 1 . Benj amin
Pas cal , 1986 .
Confe rence
S I GGRAPH ' 8 2
Creative Color ,
P r o c e edings ,
July 1 9 8 2 . Van Nos trand Re inho l d Co . ,
New
1961 .
[ 1 5 ] B l inn , J . F . : Synthe s ized Vol . 1 1 ,
1977 ,
[ 1 6 ] B l inn , J . F . : The s is ,
Univ .
Models
Coor dinates ,
Light
Reflec tion
Computer
Graphics
of
Pictur e s ,
for
Comput er
( S I GGRAPH ' 7 7 ) ,
pp . 1 9 1 - 1 9 8 . Computer of Utah ,
[ 1 7 ] Blinn , J . F . , Newe l l , M . E . : 1 978,
1 974,
Graphi cs
Cummi ngs Publishing Comp . , ACM S I GGRAPH ,
Hall ,
A Cell Organized Ras t e r Display
Matemati cké vzor ce ,
[ 1 2 ] Bergeron , R . D . ( Ed . ) :
Pren t i ce
1986.
[ 9 ] Bar r e t t , R . C . , Jordan , B . W . : for L ine Drawings ,
Graphi cs ,
Computer
Display
of
Curved
Sur face s ,
PhD
197 8 . Cl ipping Graphics
pp . 2 4 5 - 2 5 1 . - 117 -
Us ing
Homogene ous
( S IGGRAPH ' 7 8 ) ,
Vol . 1 2 ,
[ 1 8 ] Bono , P . R . , He rman , I . ( Ed . ) : EUROGRAPHI CS ,
A
Dimens ional
Procedure
Hal f- toned
CACM , Vol . 1 3 , [ 2 0 ] But l and , J . :
for
Gen e r a tion
Computer
Graph i c s
of
Thre e
P r e s entation ,
1 9 7 0 , pp . 5 2 7 - 5 6 3 . Surface
1979,
[ 2 1 ] Cas c i o l a , G . :
Drawing
Made
S imp l e ,
CAD
J ournal ,
pp . 1 9- 2 2 . B a s i c Concepts to A c c e l er a t e Line Algo r i thms ,
Compute r & Graphi c s , Vol . 1 2 ,
1 988,
[ 2 2 ] Cas t l e , C . M . A . , P i t t eway , M . L . V . : Algo r i thm
Practice ,
and
The ory
1 987 .
[ 1 9 ] Bouknight , J . :
Vol . 1 1 ,
GKS
to
Drawing
pp . 4 8 9 - 5 0 2 .
An App l i cat ion o f Euk l i d ' s
S t raight
Line s ,
in [ 3 9 ] "
1985,
pp . 1 3 5 - 1 3 9 . [ 2 3 ] Catmull , E . E . :
A Subdivis ion Algorithm for Compute r D i s p l ay
o f Curved Sur fa c e s , [ 2 4 ] Catmul l , E . :
A
S IGGRAPH ' 7 9 ,
PhD The s is , Univ . Tutor ial
on
Computer Graphi c s ,
o f Utah ,
1974.
Compensation Vol . 1 4 ,
No . 3 ,
Tabl e s , July
1 980,
pp . 2 7 9 - 2 8 5 . [ 2 5 ] Cheng , F . , Yen , Y . :
A
Paral l e l
Line
I t s Imp lementation,
in [ 4 1 ] ,
1 98 9 .
[ 2 6 ] Cl ark , J . H . : for 1 98 2 ,
The
Graphics ,
Geome try
Cl ipping
Engine :
A VL S I
Algo r i thm
Geome try
Graphi c s ' ( S IGGRAPH ' 8 2 ) ,
Computer
and
Sys tem Vol . 1 6 ,
pp . 1 2 7 - 1 3 3 .
[ 2 7 ] Claus s en , U . : in [ 64 ] ,
On
1 98 9 ,
[ 2 8 ] Computational
Synthe s is ,
Geome t r y ,
Phong
Shading
M e tho d ,
A
Proceedings
Refle ction
PhD .
of
the
Fifth
Annual
Real i s t i c
Image
1 989 . The s i s ,
[ 3 0 ] Cyrus , M . , Be ck , J . : Cl ipping ,
the
pp . 3 3 3 - 3 8 0 .
Confer en c e , ACM , [ 2 9 ] Cook , R . L . :
Reducing
Mode l
Corne l l Univ . ,
Generalized &
Compute r s
for
Two
Graphi c s ,
1 982 .
and
Thre e
Dimens ional No . I ,
Vol . 3 ,
1979,
pp . 2 3 - 2 8 . [ 3 1 ] Devi l l e r s , O . : Subdivis ion
The
Macro
S tructure
for
Regions : Ray
An
Tr acing
Effi cient
Space
in [ 6 4 ] ,
1 98 9 ,
pp . 2 7 - 3 8 . [ 3 2 ] Dr s , L . , Vš e t e čka , J . :
Obj ektivem počítače ,
[ 3 3 ] Duc e , D . A . , Jan cene , P . ( Ed . ) :
EUROGRAPHI C S ' 8 9 ,
P r o c e edings , Nor th Hol land Publ .
- 118 -
---
- - --- �--
------
SNTL ,
----�- - - -----
Comp . ,
1 98 9 .
1 98 1 . Confe rence
[ 3 4 ] Dun l avey , M . R . : Ras t e r
Efficient
Polygon on
Trans .
Display s ,
F i l l ing
Alg o r i thms
Graphi c s ,
Vol . 2 . ,
for
1983,
pp . 2 6 4- 2 7 3 . [ 3 5 ] E l l is , T . M . R . , Semenkov , O . I . ( Ed . ) : Nor th Hol l and Pub l .
Comp . ,
IFIP ,
1 98 3 .
[ 3 6 ] En c arnacao , J . , S chle chtendahl , E . G . : Fundamentals
and
Sys tem
CAD / CAM ,
in
Advan c e s
Computer Aided D e s ign -
Ar chi te c tur e s ,
Spr ing e r
Ver l ag ,
1983. Programmin g ,
Graphi c s
Compu t e r
[ 3 7 ] End e r le , G . , Kans y , K . , Pfaf f , G . : Springer Ver l a g ,
1 984.
[ 3 8 ] End e r le , G . , Gr av e , M . , Lillenhagen , F . ( Ed . ) : Compute r Gr aph i c s I , [ 3 9 ] Earnshaw, R . A . ( Ed . ) : Graphi c s , Ver l a g ,
NATO
Springer Ver l a g , Fundamental
ASI
S e r ie s ,
Gr aphics
and
The o r e tical
CAD ,
S p r inger Ver l ag ,
NATO
AS I
Graphi c s ,
P r o c e e d ings
Springer Ver lag,
F,
Computer
Vol . 1 7 . ,
S p r inger
Foundat ions
S e r ie s ,
Graphi c s
for
of
Series
New
Advanc e s
o f Compute r
Graph i c s
Computer Vol . 4 0 ,
F, in
Compute r
International
1989 .
[ 4 2 ] F i t zgeral d , W . , Gr a ce r , F . , Wo l fe , R . : Mode l ing
Solids ,
GRI N : Re s . &
IBM
Inte r a c tive Deve l . ,
Vol . 2 5 ,
July 1 9 8 1 , pp . 2 8 1 - 2 9 4 .
[ 4 3 ] F l oy d , R . , S t e inber g , L . : Gr ay
for
1 987 .
[ 4 1 ] Earnshaw, R . A . , Wyvill , B . ( Ed . ) :
No . 4 . ,
1986.
Algo r i thms
S e r ie s
in
1 985 .
[ 40 ] Earnshaw, R . A . ( Ed . ) :
89,
Advan c e s
S ca l e ,
S ID
An Adaptive
1975,
Int .
Algorithm
Symp .
Dig .
for
Spatial
Te chn . ,
1 97 5 ,
pp . 3 6- 3 7 . [ 44 ] F o l ey , J . D . , van
Dam , A . :
Fundamenta l s
Compute r Graphi c s , Addis on-We s le y , [ 4 5 ] F o l ey , J . D . : Too l s ,
Nex t
in [ 6 4 ] ,
Generation
Data
Ope r at e s
in
by
Prism
An L inear
Pr o c e s s ing , Vol . 1 5 , [ 4 8 ] Fuchs , H . ( Ed . ) :
1984.
User
Inter fa c e
Deve l opment
3-D Gr aphi c Displ ay o f D i s c r e t e Maps ,
S IGGRAPH ' 7 8 ) , Vol . 1 2 , No . 3 , [ 47 ] F r ankl in , W . R . :
Inte r a ct iv e
1 9 8 9 , pp . 5 3 7 - 5 3 8 .
[ 4 6 ] F r ankl i n , W . R . , Lewis , H . R . : Spatial
of
Exac t 1 98 1 ,
Gr aphi c s
( ACM
Algo r i thm
That
Augus t 1 9 7 8 . Hidden
Time ,
Compute r Spher e
Compute r
Graphi c s
and
Image
pp . 3 6 4- 3 7 9 .
S I GGRAPH ' 8 1
Conference
S IGGRAPH , Vol . 1 5 , No . 3 , Augus t 1 9 8 1 . - 119 -
P r o c e e dings ,
ACM ,
[ 4 9 ] Gervantz , M . , Pur gathofer , W . : Quantization : Graphi c s
Octree
A
S impl e
Quantization ,
International ' 8 8 ,
Me thod
for
P r o c ee dings
Springer
Color
Compute r
Ver lag ,
1 988,
pp . 2 1 9 - 2 3 1 . [ 5 0 ] Ge tto , P . :
Fast
Ray
Tracing
S o l id Geome try Mode l s ,
of
in [ 4 1 ] ,
[ 5 1 ] Ghazanfarpour , D . , Peroche , B . : S teps with a Z -Buffer , We s ley ,
1989,
Cons tructive
pp . 5 6 3- 5 7 8 .
Anti - alias ing by suc c e s s ive
in [ 6 4 ] ,
[ 5 2 ] Gonzale s , R . G . , Wint z , P . :
Unevaluated
1989,
pp . 2 3 5 - 2 44 .
Digital Image
P r o ce s s in g ,
Addi s on
1 97 7 .
[ 5 3 ] Got t l ie b , M :
Hidden Line Subroutine s for Thre e D imens ional
Plo ttin g , Byte , Vol . 3 , No . 5 , [ 5 4 ] Gor e l ik , A . G . :
Logi cal
Geome t r i ca l Obj e ct s ,
Fun ctions
in [ 3 5 ] ,
[ 5 5 ] Gr an át , L . , S e chovský , H . : [ 5 6 ] Graphi cal
Kernel
1 9 7 8 , pp . 4 9 - 5 8 . as
a
Means
for
Mode l l ing
pp . 1 3 5- 1 5 1 .
Počítačová gr afika ,
Sys tem
of
Thr e e
SNTL ,
Dimens ions
1980.
( GK S - 3 D )
-
Fun c tional D e s c r iption , Norma I SO /TC9 7 / SC 2 1 I S 7 9 4 2 . EUROGRAPH I CS ' 8 2
[ 5 7 ] Gre enaway , D . S . , Warman , E . A . ( Ed . ) :
Confer en c e P r o c e edings , Nor th Hol l and Publ . Comp . , [ 5 8 ] Greenber g , D . P . , Meyer , G . W . : Compute r
-Graphi c s ,
P e r ceptual
Computer
Color
Gr a.phi c s ,
1982.
Spa c e s
Vol . 1 4 ,
for 1980,
pp . 2 5 4- 2 6 1 . The
[ 5 9 ] Gr e enber g , D . P . , Mar cus , A . , S chmidt , A . , Go r t er , V . : Computer Image -Appl i cations of Compute r Graphi c s , We s l e y ,
Addi s on
1982.
[ 6 O ] Gre enbe r g , D . P . , Meye r , G . W . : Synthe s i s
in
App l i cat ion ,
Compute r
Vol . 1 1 ,
Color
Educa t ion
Graphi c s ,
Color
John Wiley & S ons ,
and
Color
Re s e ar ch
Supp l ement
and 1 98 6 ,
pp . S 3 9 - 4 4 . [ 6 1 ] Greenbe r g , D . P . : Algo r i thms , [ 6 2 ] ten
Advances
in [ 6 4 ] ,
in
Global
1 9 8 9 , pp . 40 1 - 4 0 2 .
Hagen , P . J . W . , Tomiyama , T . ( Ed . ) :
Sys tems I , [ 6 3 ] Haml in , G . ,
Spr inger Ver l a g ,
1987 .
Gear , C . :
S c an Hidden
Te chnique s ,
I l lumination
Ras ter
Inte l l igent
CAD
Sur fa c e Algo r i thm
Computer Graphics ( S IGGRAPH ' 7 7 ) ,
Vo l . 1 1 ,
1977,
pp . 2 0 6 - 2 1 3 . [ 6 4 ] Hansmann , W . , Hopgood , F . R . A . , S tr a s s e r , W . ( Ed . ) : EUROGRAPHI C S ' 8 9 Pub l .
Comp . ,
Conference
1 989 . - 120 -
Proceedings ,
Nor th
Hol l and
[ 6 5 ] Hara l i ck , R . M . :
P i c tor ial
S e r i e s F , Vol . 4 . , [ 6 6 ] Har r ington , S . : M cGr aw Hi l l ,
Springer Ver lag,
ASI ,
NATO
Analy s i s , 1983.
Computer Graphic s - A Programming App r oa ch ,
1 987 .
[ 6 7 ] He ckbe r t , P . : D i s p l ay ,
Data
Color
Image
Computer
Quantization
Gr aphi cs ,
for
Vol . 1 6 ,
Fr ame
No . 3 ,
Buffer
July
1 98 2 ,
pp . 2 9 7 - 3 0 5 . [ 6 8 ] Hilbe r t , R . : Cons truction P o lygon His tograms ,
and
Display
of
Thr e e
Computer Graphi c s ,
Dimens ional
Vol . 1 5 ,
No . 2 ,
July
1 98 1 . [ 6 9 ] Hopgood , F . R . A . , Duce , D . A . , Gallop , J . R . , Sut c l iffe , D . C . : Intro duction
to
Academi c P r e s s ,
the
Graphical
Kernel
Sys tem
1983 . Advanc e s
[ 7 0 ] Hopgood , F . R . A . , Hubbol t , R . J . , Duce , D . A . ( Ed . ) : Compute r Graphi c s I I ,
Springer Ver l ag ,
EUROGRAPHI C S As s os . ,
Geneva ,
[ 7 3 ] I ns e lberg , A . :
Note s ,
Not e s ,
Univ .
of
Inte r a c t ive Compute r Manche s t e r ,
Compute r
1 984. The
Plane
Visual Compute r , Vol . 1 ,
wi th
Para l l e l
Coordinates ,
Coor dina t e s ,
The
1 9 8 5 , pp . 6 9- 9 1 .
[ 7 4 ] Ins e l berg , A . , Comut , T . , Re i f , M . : P ar a l l e l
Tuto r i a l
1 982 .
[ 7 2 ] Hubbol t , R . J . , Arno l d , A . C . , Hewitt , W . T . : Gr aphi c s - Cour s e
in
1986 .
EUROGRAPHICS ' 8 2 ,
[ 7 1 ] HUbbo l t , R . J . ( Ed . ) :
Gr aphi c s Unit ,
( GK S ) ,
JACM ,
Convex i ty
Vol . 3 4 ,
No . 4 ,
Algo r i thms
in
October
1 987 ,
Coo r d in a t e s
for
pp . 7 6 5- 8 0 1 . [ 7 5 ] I n s e l b e rg , A . , Dims dale , B . : Visua l i z ing
Par a l l e l
Mul t i-Dimens ional
Geome try ,
in [ 8 4 ] ,
1987,
pp . 2 5-44 . [ 7 6 ] Jarvis , J . F . , Judice , C . N . , Ninke , W . H . : A Survey o f Te chniques for
the
Display
D i s p l ays ,
of
Continue s
Computer Graphi cs
and
Tone
P i c ture s
Image
on
B i l ev e l
P r o ce s s ing ,
Vol . 5 ,
1 9 7 6 , pp . 1 3- 4 0 . [ 7 7 ] Jevans , D . A . J . : in [ 4 1 ] ,
Optimi s t i c
Mul t ip r o c e s s o r
Ray
Tra c ing ,
1 9 8 9 , pp . 5 0 7 - 5 2 2 .
[ 7 8 ] Jos eph, H . :
Computer Graphi cs Har dware - Intro du c t ion
S tate of the Ar t ,
EUROGRAPHICS ' 8 7 Tutor ia l ,
1 987 .
- 121 -
and
EUROGRAPHI C S ,
[ 7 9 ] Kay , D . S . :
Tran s p ar en cy ,
Computer
Synthe s ized
Refra c t ion
Image s ,
PhD
and
Ray
The s is ,
T r a c ing
Corn e l l
for
Univ . ,
1979. [ 8 0 ] Kilgour , A . C . : S can
Unifying
Conv e r s ion
and
Ve ctor
and
Cl ipping ,
Polygon
TR
Algor i thm
C S C / 8 7 /R 7 ,
for
Univ .
of
Glas gow, May 1 9 8 7 . [ 8 1 ] Knuth , D . E . :
Digital Halftones by Dot Diffus ion ,
on Gr aphi c s , Vol . 6 , No . 4 , O c tober 1 9 8 7 , [ 8 2 ] Kubo , S . :
Continuous
I nk J e t P r inte r s , [ 8 3 ] Kunii , T . L . ( Ed . ) : Ver l ag ,
pp . 2 4 5 - 2 7 3 .
P r e s entat ion
Us ing
a
L ow
Co s t
in [ 8 4 ] , 1 9 8 7 , pp . 3 48 . Frontiers in Computer Gr aphi c s ,
S p r inger
1985.
[ 8 4 ] Kunii , T . L . ( Ed . ) : the
Color
ACM Tran s .
5 th
Computer
International
S p r inger Ver la g ,
Confer ence
1987 , on
P r o c e edings
Comput e r
of
Gr aphi c s ,
1 987 .
[ 8 5 ] Liang , Y . D . , Barsky , B . A . : P o lygon Cl ipping ,
An
Analys is
and
CACM , Vol . 2 6 , No . 1 1 ,
[ 8 6 ] Liang , Y . D . , Barsky , B . A . : Cl ipping ,
Gr aphi c s
Algor i thms
1 984,
for
pp . 8 6 8-87 6 .
A New Concept and Me thod for L ine
ACM Tran s a ction on Graphi c s ,
Vol . 3 ,
No . 1 ,
1 984,
pp . 1 - 2 2 . [ 8 7 ] Lewe l l , J . :
Computer
Te chnique s
and
Gr aphi c s
Appl i cations ,
- \A
Survey
Orbis
of
Curr en t
Pub l .
Ltd . ,
L ondon ,
and
Hidden
1985. [ 8 8 ] Mach, K . D . , Pe tty , J . S . :
Contouring
Algo r i thms for Ve c tor Graphi c Display ,
Rep .
Line
AFAPL-TR- 7 7 - 3 ,
1 97 7 . [ 8 9 ] Měření bar ev , [ 9 0 ] Meye r , G . W . : Gene r ation ,
C SN 0 1 1 7 1 8 . Wavelength
[ 9 1 ] Meyer , G . W . :
Tektronix , [ 9 3 ] Mur ch, G . : 1989,
on
Color
Springer Ver l a g ,
Human Oregon ,
for
Synthe t i c
Image
Graphi c s
and
Image
S c ience ,
The
Visual
1 9 8 8 , pp . 5 7 - 7 9 .
Tutor ial
Compute r , Vo l . 2 , [ 9 2 ] Mur ch, G. M . :
Vis ion ,
Computer
P r o ce s s ing , Vol . 4 1 ,
S e l e ction
Factors
of
pp . 2 7 8- 2 9 0 . Color
D i s p l ay s ,
TR ,
1 989 .
Color Mat ching of Di s p l ay and P r in t e r ,
in [ 6 4 ] ,
pp . 3 1 3- 3 1 4 .
[ 9 4 ] Newmann , W . M . , Sproul l , R . F . : Computer Gr aphics ,
Prin c ip le s
2nd e d . , McGr aw Hil l ,
- 122 -
of 1 98 1 .
I n t e r a ct ive
[ 9 5 ] Ni chol l , T . M . , Le e , D . T . , Ni chol l , R . A . : Algor i thm
for
Analys i s ,
2D
Line
An
Cl ipping :
ACM Compute r Graphic s ,
Its
Vol . 2 1 ,
Effic ient
New
Deve l opment
and
No . 4 ,
July
1987,
pp . 2 5 3- 2 6 2 . [ 9 6 ] O ' B ar a , R . M . , Abi-Ezzi , S . : i n [ 64 ] ,
1989,
[ 9 7 ] P av l idis , T . : Ver l a g ,
An
Analys i s
of
Mod e l ing
C l ip ,
pp . 3 6 7 - 3 8 0 . Graphi c s
and
Image
P r o c e s s ing ,
S p r inger
1 982 .
[ 9 8 ] P e i tgen , H . O . : Graphi c s ,
The Impact of Fractal Geome try for Compute r
in [ 64 ] ,
[ 9 9 ] P e r due , L . :
1 9 8 9 , pp . 3 1 5- 3 1 6 .
Super charging Your P C , McGraw Hil l ,
[ 1 0 0 ] Phil l ips , R . L . ( Ed . ) :
S I GGRAPH ' 7 8 ,
Confer e n c e
1 987 . P r o c e e dings ,
ACM S IGGRAPH , Vol . 1 2 , No . 3 , Augus t 1 9 7 8 . [ 1 0 1 ] Pins , M . , Hi l d , H . : 1989,
Var iation
on Dither
in [ 6 4 ] ,
pp . 3 8 1 - 3 9 2 .
[ 1 0 2 ] Pit t eway , M . L . V . :
The Algebra of Algor i thms - A New Toy for
the The o r e t i cian ? ,
IUCC Bul l e t in , Vol . 1 ,
[ 1 0 3 ] Pit t eway , L . M . V . , Watkinson , D . J . : Gr ay S ca l e ,
CACM , Vol . 2 3 ,
[ 1 04 ] P l a s to ck , R . A . , Kaley , G . : [ 1 0 5 ] P o l l a c k , B . W . ( Ed . ) :
1979,
pp . 1 3 9 - 1 4 4 .
B r e s enham ' s Algo r i thm wi th
1980,
pp . 6 2 5- 6 2 6 .
Theory
and
Gr aphi c s , McGraw Hil l , New Yor k , ACM ,
Algor i thm ,
P r o b l ems
of
Comput e r
1 98 6 .
S I GGRAPH ' 7 9
Conf e r e n c e
P r o c e e dings ,
S I GGRAPH , Vol . 1 3 . , No . 2 . , Augu s t 1 9 7 9 .
[ 1 0 6 ] Pop s e l , J . , Hornung , C . : Shading
in
a
Highl ighting Shading - L ighting and
PHIGS + / PEX
Environment ,
in [ 6 4 ] ,
1989,
pp . 3 1 7 - 3 3 2 . [ 1 0 7 ] Preparata , F . P . , Shamos , M . I . : Introdu c t ion ,
Computational
Spr inger Ver lag ,
geome try
An
1 98 5 .
[ 1 0 8 ] Roger s , D . F . , Adams , J . A . : Mathematical El ements for Computer Gr aphi c s , McGraw Hil l , New York, [ 1 0 9 ] Roger s , D . F . : McGraw Hil l ,
Procedural
Elements
[ 1 1 1 ] de
Spr inger Ver l a g ,
Rui t e r , M . M . ( Ed . ) :
Springer Ve r la g , [ 1 1 2 ] S an to , H . P . : Dinal ivro ,
for
2.
vydání 1 9 9 0 .
Compu t e r
Graphi c s ,
1 985 .
[ 1 1 0 ] Roger s , D . F . , Earnshaw , R . A . ( Ed . ) : Gr aphi c s ,
1976,
Te chnique s
for
Computer
1 987 .
Advan c e s
in
Compute r
Gr aphi c s
III,
1 988 .
Mé todos Lis boa ,
Gráficos
1985 .
- 123 -
e
Geome t r i a
Computa c ionais ,
[ 1 1 3 ] Sheppard , J . :
Human Color P e r c eption - A C r i t i c a l S tudy o f
the Exp e r imental Foundation , E l s evier , New York , [ 1 1 4 ] Shi r ai , Y . : Ve r l a g ,
Thre e
Dimens ional
Compute r
1 9 68 .
Vis ion ,
S p r inger
1 987 .
[ 1 1 5 ] Skala , V . :
An
Interes ting
Modification
to
Algor i thm for Hidden-Line Problem S o lution ,
the
B r e s enham
in [ 3 9 ] ,
1 985,
pp . 5 9 3- 6 0 2 . [ 1 1 6 ] S ka l a , V . :
An
Al gorithm ,
Inter s e c ting
Computer
Modification
Graphi c s
Forum ,
to
the
Vo l . 6 ,
B r e s e nham
No . 4 ,
1 987 ,
pp . 3 4 3 - 3 4 7 . [ 1 1 7 ] Ska l a , V . :
Algor ithms for 2D Line Cl ipping ,
in [ 4 1 ] ,
1989,
in [ 6 4 ] ,
1 989,
pp . 1 2 1 - 1 2 8 . [ 1 1 8 ] Ska l a , V . :
Algor i thms for 2D Line Cl ipping ,
pp . 3 5 5- 3 6 7 . [ 1 1 9 ] S l avkovský , P . :
Problém vidite lnos t i v p o č í t ačové grafi c e ,
kandidátská dis e r tačn í práce , MFF UK , [ 1 2 0 ] Smith , A . R . :
Color
Gamut
Trans form
Conference P r o c e e dings , ACM , [ 1 2 1 ] Smith , A . R . : Vol . 1 3 ,
Tint
1979,
Fil l ,
Compute r
The
S e cond
and App l i cation s ,
Graphics
S I GGRAPH ' 7 8 pp . 1 2 .
( S I GGRAPH ' 7 9 ) ,
CSN ' 3 6 0 0 0 0 .
International
Advanc e s
Spr inger Ver l ag ,
Gr aphi c s
Compute r
Beij ing , China ,
[ 1 2 4 ] S tr a s s e r , W . ( Ed . ) :
Conf .
on
Comput e r s
1987 .
in
Gr aphics
Compute r
1 987 .
[ 1 2 5 ] Suther l and , I . E . , Hodgman , G . W . : CACM , Vol .
1978,
1 987 .
pp . 2 7 6 - 2 8 3 .
[ 1 2 3 ] S taudhammer , J . , Livadas , P . E . :
Har dwar e I ,
Pair s ,
S IGGRAPH ,
[ 1 2 2 ] Svě t e lně-te chn i cké názvos loví , A Tuto r ial ,
Bratis l av a ,
Reentrant
1 7 . , No . 1 , January 1 9 7 4 ,
P o lygon C l ipping ,
pp . 3 2- 4 2 .
[ 1 2 6 ] Suthe r l an d , I . E . , Sproul , R . F . , S chumacker , R . A . : A Cha r a c t e r ization
of
Ten
Computing Surveys , Vo l . 6 , [ 1 2 7 ] Tanner , P . ( Ed . ) :
Hidden- Sur face
1 974,
S I GGRAPH ' 8 3 ,
Algo r i thms ,
pp . 1 - 5 5 .
Confer en c e
P r o c e e dings ,
ACM ,
S I GGRAPH, Vol . 1 7 , No . 3 , July 1 9 8 3 . [ 1 2 8 ] Teunis s en , W . J . M . : HlRASP - A Hierar chical Mode l l in g Sys tem for Ras te r Graphi c s ,
PhD The s i s ,
[ 1 2 9 ] Tha lmann , N . M . , Thalmann , D . ( Ed . ) : P r o c e edings
of
Gr aphi c s
1 988 . Computer Gen e r a t e d Image s ,
Interface ' 8 5 ,
1 98 5 .
- 124 -
S p r inger
V e r l ag ,
[ 1 3 0 ] Thomas , J . J . ( Ed . ) : ACM ,
S IGGRAPH ' 8 0 , Vol . 1 4 "
[ 1 3 1 ] Toifl , J . : informa c í , [ 1 3 2 ] Toifl , J . :
vs tupní
č. 2,
1 97 3 .
SNTL ,
č. 4,
[ 1 3 3 ] UNlRAS
Firemní
Con t r a c tor s ,
zařízení
počítače ,
Výb ě r
zař ízení
p o č í ta č e ,
Výběr
výs tupní
SNTL ,
1 97 3 . mater iály
firmy
[ 1 3 5 ] Vandoni , C . E . ( Ed . ) :
S oftwar e
Tel evizní te chnika ,
[ 1 3 7 ] Warnock, J . E . :
Fir emní mater iály , Comp . ,
SNTL ,
1 98 5 .
Confer en c e
EUROGRAPHI CS ' 8 5 ,
P r o c e e dings , Nor th Hol l and Pub l .
1985.
P r aha ,
1 97 9 .
A Hidden Line AIgorithm for Halftone P i c tur e
Repr e s entat ion , TR 4- 5 ,
Eur opean
1985 .
[ 1 3 4 ] UNlRAS - Univer s al Ras ter Repo r t ,
[ 1 3 6 ] Vít a kol . :
P r o c e e dings ,
No . 3 , July 1 9 8 0 .
Gr afi cké Grafi cké
informa c í ,
Confer e n c e
S I GGRAPH ' 8 0 ,
Univ .
of
Utah ,
Comp . S c i . Dep t . ,
Repor t
May 1 9 6 8 .
[ 1 3 8 ] Warnock , J . E . : Gener a t e d
A
Hidden
Surface
Halftone
AIgo r i thm
P i c tur e s ,
for
Univ .
Compute r
of
Utah,
Comp . S ci . Dept . , TR 4- 1 5 , June 1 9 6 9 . [ 1 3 9 ] Watkins , G . S . : of
Utah ,
A Real Time Vis ible
Comp . S ci . Dept . ,
Surface
Report
Program ,
Univ .
UTEC-CSC- 7 0- 1 0 1 ,
June
1970. [ 1 40 ] Wa tkins , S . L . :
Masked Thre e Dimens ional
Rotat ion , AIgor i thm 48 3 , CACM , Vol . 1 7 , [ 1 4 1 ] Watte r s , G . , Wi l l is , P . : Ultra
High
S c an
Definition ,
No . 2 , May 1 9 8 7 , Ar e a
Vol . 1 1 ,
1 97 7 ,
[ 1 4 3 ] Whi tted , T . : Display , CACM ,
Vol . 1 5 ,
[ 1 4 5 ] Wr ight , T . J . : P r o b l em Tr ans .
for
Sorting ,
Hidden
Extruded
Graphi c s Sur fac e
Compute r
An
Improved
Lines
Forum ,
at
Vol . 6 ,
Removal
Graphi c s
Vol .
I l lumination
2 3 , 1 980,
U s ing
( S I GGRAPH ' 7 7 ) ,
Mod e l
Hidden-Line Plotting P rogr am , 1972, A
Shaded
AIgo r ithm 4 2 0 ,
pp . 1 0 0- 1 0 3 .
Two-Space
Plotting
Image s , in [ 4 1 ] ,
for
pp . 3 4 3 - 3 4 9 .
Solution
Func tions
on Compute r s , Vol . C- 2 2 , Fas t
of
1973,
to Two
1 9 8 9 , pp . 5 7 9- 5 9 0 .
the
Hidden
L ine
Var iable s ,
I EEE
pp . 2 8 - 3 3 .
Antialiasing
- 125 -
-- ---
pp . 5 2 0- 5 2 3 .
pp . 2 1 4- 2 2 2 .
[ 1 4 6 ] Wyvil l , G . , Shar p , P . :
-
P r o g r am wi th
pp . 1 3 3- 1 40 .
CACM,
[ 1 44 ] Wil l iams , H . :
1 974,
Conver ting
Computer
[ 1 42 ] We i l er , K . , Athe rton , P . : Polygon
Plot
of
Ray
Traced
[ 1 47 ] Xu , H . , Peng , Q . S . , Liang , Y . D . : for Compute r Environment , [ 1 48 ] Zhang , J . : 1898,
Accelerated
in [ 6 4 ] ,
Radios i ty
1989,
pp . 5 1 - 6 2 .
A Fas t Hidden-Line Removal Algo r i thm ,
in [ 4 1 ] ,
pp . 5 9 1 - 6 0 2 .
[ 1 4 9 ] B l inn , J . F . , Carpenter , L . C . , Lane , J . M . , Whi t t ed , T . : Me thods CACM ,
Me thod
for
Displaying
Vo l . 2 3 , pp . 2 3 - 3 4 ,
[ 1 5 0 ] Phong , B . T . :
Par ame tr i c al ly for
of Utah ,
for
the
Defined Surfa ce s , Vo l . 1 1 ,
Computer
Gene r al ized
A
Compute r
Image s ,
Display
of
Line
S c an
P a r ame t r i ca l ly
Compute r Graphics and Image P r o c e s s ing,
Computer
The s is , Univ . [ 1 5 3 ] Kay , Douglas T r a c ing
S co t t :
for
of
Curved
Transparency ,
Refr a c tion
Synthes ized
PhD
Image s ,
and
MSc
Ray
The s i s ,
1 97 9 . S co t t ,
Gre enberg , D . :
Synthe s ized
Image s ,
T r an s p a r e n cy Compu t e r
( S I GGRAPH ' 7 9 P r o c e edings ) , Vol . 1 3 , 'pp . [ 1 5 5 ] B e ckmann , P . , Spizzichiono , A . : from
Surfa ce s ,
1 97 1 .
Computer
Douglas
Computer
Display
of Utah ,
Corne l l Univ . ,
Wav e s
Gen e r a t e d
pp . 2 9 0 - 2 9 7 , 1 9 7 9 .
[ 1 5 2 ] Gour aud , H . :
[ 1 5 4 ] Kay ,
Sur f a c e s ,
1973.
[ 1 5 1 ] Carpenter , L . C . , Lane , J . M . : Algorithm
Defined
Line
1 980 .
I l luminat ion
PhD The s is , Univ .
S can
Rough
for
Gr aphi c s
1 58- 1 64 ,
1 97 9 .
S ca t t e r ing of E l e c t r omagn e t i c
Sur fa c e s ,
MacMi l l an
P re s s ,
New
Yor k ,
1 9 6 3 , pp . 1 - 3 3 , 7 0- 9 8 . [ 1 5 6 ] Cook , R . L . , Tor r an ce , K . E . :
A Refle c tan c e Mod e l for Compute r
Gr aphi c s , ACM o n Gr aphi c s , Vol . 1 . , [ 1 5 7 ] Tor r an ce , K . E . , d i s tr ibution ,
Spar r ow , E . M . : and
pp . 7 - 2 4 ,
1 982 .
Polarization,
off- spe cular
peak
r e f l e c t e d from r oughened surface s ,
d ir e c t ional
phenomena
in
l i ght
Journal of the Op t i c al
S o c i e ty of Ame r i c a , Vol . 5 7 , 7 ( July 1 9 6 6 ) , 9 1 6 - 9 2 5 . [ 1 5 8 ] Tor r an ce , K . E . ,
Sparrow , E . M . :
Theory
off-s p e cular
for
r e f l e c t iom from roughened surface s ,
Journal of the Opt i c al
S o c i e ty of Ame r i c a , Vol . 5 7 , 9 ( S ept .
1 9 6 7 ) , 1 1 0 5- 1 1 1 4 .
[ 1 5 9 ] Trowbr idge , T . S . , r e pr e s entat ion
Re i t z , K . P . : of
r oughened
i r r e gular i ty
Ave r age
sur face
for
Journal of the Op t i cal S o c i e ty of Ame r i c a ,
r ay
r e f l e c t ion ,
Vo l . 6 5 ,
5
( May
1975 ) , 531-536. [ 1 6 0 ] Ago s ton , G . A . : D e s ign ,
Color Theory and I t s App l i c a ton in Ar t and
Springe r Ver l ag 1 9 8 7 - 126 -
[ 1 6 1 ] B a l dwin , L . :
Color
Consideration ,
BYTE
S e p tember
1 984,
pp . 2 2 7 - 2 4 6 [ 1 6 2 ] Cahi l l , B . :
on
Dr awing
the
BYTE
8 5 1 4 /A ,
1 990,
Mar ch
pp . 2 7 9 - 2 8 9 [ 1 6 3 ] Dr s , L . : SNTL ,
P l o chy v e výp o č e tní t e chni c e ,
Matema t i cký s eminář
SNTL 1 9 8 4
[ 1 6 4 ] Ska l a , V . : Are a s
F i l l ing and Hat ching Ope r ation s
with
Con i c
ACM- S IGGRAPH
Workshop
Por tugal ,
1 988
[ 1 6 5 ] S ame t , H . :
The
S t ructur e s ,
Edg e s
for L i s boa
Quadtree
Computing
the
and
Ras t e r
Re lated Vol . 1 6 ,
Environment , L i s bo a ,
Gr oup ,
Local
Surveys ,
for Non- Convex
Hie r a r chical No . 2 ,
Data
June
1 984,
pp . 1 8 7 - 2 6 0 [ 1 6 6 ] S ame t , H . ,
Webbe r , R . E . :
U s in g Quad t re e s , July 1 9 8 5 ,
pp .
ACM Trans .
Ras ter
Po lygons
4,
No .
3,
Polyhedron for
Rep r e s entat ion Mode l l ing
C r anfie l d
1986 for
Compute r
and
D i s p l ay ing
of
3D
1 98 6
Te chnical Repor t ,
Ins t .
of
pp . 5 8 9 - 5 9 6
of Glas gow,
Type s of Mode l l e r ,
Data
pr o c e edings
Springe r Ve r lag ,
Te chnical Repor t , Univ .
Mathemat i c s , U. K. ,
A
Te chnique s
[ 1 7 0 ] P r at t , M . J . :
Vol .
Graphi c s ,
P ro c . Nat . Comp . Conf . , AF I P S 1 9 7 5 ,
[ 1 6 9 ] Kilgour , A . :
of
P e t e r s , F . J . , van Lierop , M . L . P . ( Ed . ) :
for
[ 1 6 8 ] B aumgar t , B . G . :
S ce ne s ,
Col l e c t ion
on Graphi c s ,
a Workshop he l d at S te ens e l , Vi s ion ,
a
1 8 2-222
[ 1 6 7 ] Ke s s ener , L . R . A . , S tructur e s
S to r ing
Te chno l o gy ,
Dep t .
of
C r an fi e l d
S e ptember 1 9 8 2
[ 1 7 1 ] Thalmann , N . M . , Thalmann , D . ( Ed . ) : and P r a c t i ce ,
Springer Ver l ag ,
[ 1 7 2 ] Greenbe r g , D . P . :
Computer Anima tion , 1 98 5 .
Ray Tracing and Radio s ity ,
Image Synthe s is ,
cour s e not e s ,
S ta t e o f Ar t in
S IGGRAPH ' 8 6 , ACM ,
for
Computing
Global
1986 Rad io s i ty :
[ 1 7 3 ] Gre enbe r g , D . P . , Cohe n , M . F . , Torran ce , K . E . : A Me thods
Theory
I l l iminat ion ,
The
Visual
Comput e r , Vol . 2 . , No . 5 . , S e pt ember 1 9 8 6 . [ 1 7 3 ] Bur goon , D . A . : Radios ity,
Global Hewl e t t
I l luminat ion
Packard
Mode l ing
Journa l ,
D e c ember
U s ing 1989,
pp . 7 8 - 8 8 . [ 1 7 4 ] Goral , C . M . , Torrance , K . E . , Gr e enbe r g , D . P . , B a t t a il e , B : Mod e l l ing Sur fa ce s ,
the
Interac tion
S IGGRAPH ' 8 4 , ACM ,
of
Light
b e twe en
D iffus e
1 984.
- 127 -
-----�-.- ---- - - - - - - -,--- ------� -- �
�----- -------- --------
[ 1 7 5 ] Cohen , M . F . , Greenberg, D . P . :
The
Hemi-Cube :
So lut ion for Complex Envir onmen ts , [ 1 7 6 ] Gr aphi es
Dat abook,
fir emní
Radi o s i ty
S I GGRAPH ' 8 5 ,
mate riály
INMO S
ACM ,
1985 .
SGS-Thomp s on ,
1990. [ 177 ]
Sys tems Solut ions ,
[ 1 7 8 ] Jarvi s , J . F . ,
fir emní mate r iály IChips Eur ope ,
Robe r t s , C . S . :
Continuous
Tone
Images
Communi e . ,
Vol . 2 4 ,
A New Te ehnique for D i s p l aying
on a Bilivel
pp . 8 9 1- 8 9 8 ,
Display ,
I EEE Trans .
1976. Improper
[ 1 7 9 ] Abhyankar , S . S . , Chandras ekar , S . , Chandru, V . : Inte r s e e t ion of Algebraie Curves , vo l . 9 ,
No . 2 ,
1990,
[ 1 8 0 ] Andreev , R . D . :
Computer Gr aphies Forum , [ 1 8 1 ] Brune t , P . , Navazo , I . : Extended
No . 2 ,
19 90,
[ 1 8 2 ] Day , A . M . : Convex Trans .
ACM Trans .
on Gr aphi es ,
pp . 1 4 7- 1 5 9 .
Al gorithm
Us ing
for
Cl ipping Arbi trary
Vo l . 7 ,
Solid
Oetrees ,
No . 3 ,
1988,
pp . 1 8 3 - 1 9 2 .
Repres entat ion
ACM
Tra:ns .
on
Po lygons ,
and
Ope r a t ion
Graphi e s ,
vol . 9 ,
pp . 1 7 0- 1 9 7 .
The
Hul I
Implementat ion of an Algo r i thm
of
a
Set
of
on Gr aphies , vo l . 9 ,
Thr ee No . 1 ,
to
Dimens ional
find
Poin ts ,
1990,
pp . 1 0 5 - 1 3 2 .
[ 1 8 3 ] Dobkin , D . P . , Levy , S . L . F . , Thurs ton , W . P . ,
Wilks , A . R . :
Traeing by Pie eewise Linear Appr oximations , Gr aphi es ,
1 9 90 .
vo l . 9 ,
No . 4 ,
1990,
to
Algori thms ,
ACM
Cope
with
Trans .
S imul at ion
Cont our
ACM Trans .
of
Degenerate
Cas e s
Graphi es ,
vol . 9 ,
on
ACM
on
pp . 38 9-42 3 .
[ 1 84 ] Ede l s brunner , H . , Mueke , E . P . : A Te ehnique
the
S imp l ie i ty : in
Geome t r i e
No . 1 ,
1990,
pp . 6 6 - 1 0 4 . [ 1 8 5 ] Fal eidieno , B . , Floriani , L . : for
S o l id Obj e e t
vo l . 7 ,
No . 1 ,
Hierar ehi eal
Representation ,
1988,
Boundary
ACM Trans .
On
on Graphies ,
the
Power
of
the
Gr aphi es , [ 1 8 8 ] Heal , B . :
vo l . 7 ,
No . 2 ,
1988,
Vo l . 7 ,
for
High
Speed
vo l . 7 ,
No . 3 ,
1 98 8 ,
Hidden
No . 3 ,
Oetree
1988,
Comput er
Ray
Tr aeing
Buffe r ,
pp . 1 0 3 - 1 2 8 . Mul tip r o e e s s or ACM
Trans .
on
pp . 1 5 1 - 1 7 9 .
Removal ,
Computer
Graph i e s
Forum ,
pp . 1 9 9- 2 0 6 .
[ 1 8 9 ] Herman , I . , Reviezky , J . : Problem,
Gr aphies ,
Frame
[ 1 8 7 ] Gaude , S . , Hobs on , R . , Chilka , P . , Calver t , T . : Exper iments
on
Mode l
pp . 42- 6 0 .
[ 1 8 6 ] Fournie r , A . , Fus s e l , D . : ACM Tr ans .
A
Some Remarks
Graphies
pp . 2 6 5 - 2 7 2 . - 128 -
Forum,
on the Mode l l ing Clip Vo l . 7 ,
No . 4 ,
1 988,
[ 1 9 0 ] Herman , I . : Computer 1990,
On
The
Proj e c t ive
Graphi c s ,
Computer
Invar iant
Graphi cs
of
Forum ,
Coni c s
Vol . 8 ,
in
No . 4 ,
pp . 3 0 1 - 3 1 4 .
[ 1 9 1 ] Hobby , J . D . : Trans .
Ras terizat ion
of
on Gr aphi cs , vo l . 9 ,
[ 1 9 2 ] Kui j k , A . A . M . , B lake , E . H . : Interpola ti on ,
Nonparame tr i c
No . 3 ,
1990,
Fas ter
Curve s ,
ACM
pp . 3 2 6 2 - 2 7 7 .
Phong
Shading via Angular
Comput er Graphics. Forum ,
Vol . 8 ,
No . 4 ,
1990,
pp . 3 1 5 - 3 2 5 . [ 1 9 3 ] Lamming , L . , Rhode s , W . L . :
A S imple Me thod for Improved Color
Pr inting of Monitor Image s , No . 4 ,
19 90,
[ 1 9 4 ] Levoy , M . : Trans .
Efficient
[ 1 9 5 ] Nichol l , R . A . ,
Ray
Tracing
vo l . 9 ,
No . 3 ,
by
vo l . 9 ,
of
1 9 90,
Ni chol l , T . M . :
Trans formations
of
Axial
View
Trans .
on Graphics ,
Vo l . 9 ,
1 9 90,
a
Set
No . 3 ,
1 9 90,
Un ifi cation? ,
1990,
vo l . 9 ,
Interference Det e c tion ,
No . 4 ,
1990,
Active
vol . 8 , No . 1 ,
Include ACM
of
Par a l le lopides ,
on the ACM
pp . 2 7 8 - 3 00 . Gr aphi c s
Forum ,
1989,
Spe cularly
Trans .
on
ACM
pp . 3 7 6 - 3 8 8 . Zones
in
CSG
for
Redundan cy E l imination ,
and Shading Algo r i thms ,
[ 2 00 ] Rushmeier , H . E . , Torrance , K . E . : Mater i al s ,
T r ans .
Computation
Computer
Ac c e l e r a t ing Boundary Evaluat ion ,
to
ACM
Fas t Line S can Conve r s ion,
[ 1 9 9 ] Ro s s igna c , J . , Voe l cker , H . B . :
Me thod
Geome t r i e
pp . 1 4 9- 1 6 4 .
on Graphi cs ,
on Graph i c s ,
ACM
pp . 2 8 -40 . I s othe t i c
vo l . 9 ,
Data"
Relat ionships Between Image Synthe s i s and
Towar ds
No . 2 ,
of
[ 1 9 8 ] Rokne , J , G . , Wyvil l , B . , Wu , X . : Trans .
vol . 9 ,
pp . 2 4 5 - 2 6 1 .
Program Tr ans formation,
No . 1 ,
[ 1 9 7 ] Pun , T . , B l ake , E . :
Volume
Performing
[ 1 9 6 ] Preparata , F . P . , Vitter , J . S . , Yvine c , M . :
Analys is :
on Gr aphic s ,
pp . 3 4 5 - 3 7 5 .
on Gr aphi cs ,
Gr aphi cs ,
ACM Trans .
ACM Trans .
pp . 5 1 - 8 7 . Extended
the
Radios i ty
Refl e c t ing
and
Trans luent
Graphics ,
vo l . 9 ,
No . 1 ,
1990,
pp . 1 - 1 7 . [ 2 0 1 ] S t one , M . C . , Cowan , W . B . , Beatty , J . C . : the
Pr inting
Gr aphics ,
of
vo l . 7 ,
Digital No . 4 ,
Color
1988,
1990,
Image s ,
ACM
Trans .
on
pp . 2 4 9 - 2 9 3 .
[ 2 0 2 ] Thomas , D . , Netraval i , A . N . , Fox , D . S . : Tr a c ing wi th Covers ,
Color Gamut Mapping and
Ant i-al ias e d
Computer Graph i c s Forum ,
pp . 3 1 5 - 3 2 4 .
- 129 -
Vo l . 8 ,
Ray No . 4 ,
[ 2 0 3 ] Veens t r a . J . , Ahuj a , N . : Obj e c t s ,
ACM
Line
Drawing
on
Gr aphi c s ,
Trans .
of
Octree
vol . 7 ,
Repre s en t e d No . 1 ,
1988,
pp . 6 1 - 7 5 . [ 2 0 4 ] Ware , C . , Cowan , W . :
The RGYB Color Geome t r y ,
Graphi c s , vol . 9 , No . 2 , [ 2 0 5 ] Zyd a , M . J . :
A
1 98 8 ,
on
1 9 9 0 , pp . 2 2 6 - 2 3 2 .
de compos able
D i s p l ay Gener at ion ,
ACM T r an s .
Algori thm
ACM Trans .
for
Con t our
o n Graph i c s ,
Sur fa c e
v ol . 7 ,
No . 2 ,
pp . 1 2 9 - 1 4 8 .
[ 2 06 ] JeŽek, F . :
AutoCAD - učební text , VŠ SE P l zeň ,
[ 2 0 8 ] Rank l in , J . R . :
1991.
Compute r
Graphics
Softwar e
Advan c e s in Compute r S cience S e r ie s , [ 2 0 9 ] Rushme ier , H . E . , To r r an ce , K . E . : Cal cul ating
a P ar t i c ipating Medium ,
Z onal
1989.
Method
the
in
Compute r
Con s t r u c t ion ,
P r e n t i c e Hal l ,
The
Intens ities
Light
g rafika ,
P o č í ta čová
[ 2 0 7 ] P O l á Č e k , J . , Je Že k , F . , Kopincová , E . : skr ipta CVUT-FS Pr aha ,
199 1 .
for
P r e s en c e
Graphi c s ,
Vol . 2 1 ,
of
No . 4 ,
July 1 9 8 7 . [ 2 1 0 ] P o č í t a č ová grafika - Názvos l oví ,
CSN 3 6 9 0 0 1 č á s t 1 3 .
[ 2 1 1 ] Sys t émy zpr a c ování informa c í ( GKS ) ,
CSN 3 6 9 1 8 0 .
[ 2 1 2 ] F i remní materiály firmy INTERGRAPH ,
June 1 9 9 1 .
[ 2 1 3 ] Skal a , V . :
P o č í ta čová grafika I ,
univer zita ) , [ 2 1 4 ] Skala , V . :
Plzeň,
2.
vydán í ,
Skripta V Š SE 1991 .
P o č í t a čová gr afika I I ,
univer z it a ) ,
P l zeň ,
[ 2 1 5 ] D r z ai c , P . S . :
2 . vydání ,
Nematic
Drop l e t
Skr ipta V Š S E ( Západ o č e s ká
199 1 . Pqlymer
Con t r as t colour ed Re f l e c t ive Displays , and No . 1 ,
Appl i cations ,
Fi lms
for
High
D i s p l ay s Te chn o l o gy
Butterwor th-He inemann
Ltd . ,
Vol . 1 2 ,
January 1 9 9 1 , pp . 2 - 1 3 .
Comp a r i s on Mode l s ,
of
RGB ,
YIQ,
LAB ,
Expe r imental
An
[ 2 1 6 ] S chwar z , M . W . , Cowan , W . B . , Be a t ty . J . C . : HSV,
and
Opponent
ACM Tr ans a c t ion on Compute r Graphi c s ,
Apr il 1 9 8 7 ,
Color
Vol . 6 , No . 2 ,
pp . 1 2 3- 1 5 8 .
[ 2 1 7 ] Col our Addendum to I SO 8 6 1 3 - Working Draft , WG 5 ,
( Západ o č e s ká
I S O TC 9 7 S C 1 8
X3H3 / 8 8-47 .
[ 2 1 8 ] Pret t , V . :
Cifrovaj a
obrobo tka
izobražen i j ,
Mir ,
Mos kva ,
1982. [ 2 1 9 ] Serba, I . : p r o s torové
Termodynami cký s cény
v
p ř í s tup
p o č í t ač ové
1991. - 130 -
k
výp o č tu
grafice ,
o s v ě t l en í
s eminář
MOP 9 1 ,
[ 2 2 0 ] S o chor , J o :
S l e dování paprsku ve
3D s céně ,
s eminář MOP 9 1 ,
1991. [ 2 2 1 ] Hal l , R o : Imaginary ,
I l lumination
and
Springer Ver lag ,
Color
in
Compute r
Gener ated
1989 0
- 131 -
---
- - --�--------- -�--------- -
- - -------�-- --- -------_. _-�--
---�
