0001
`
`Volkswagen 1011 - Part 1 of 6
`
`

`
`
`
`Computer
`Graphics
`
`0002
`
`0002
`
`

`
`I3'n:_-.;-r |':~'u:_:u1'r_
`I-,':: :_|_ii
`'.;'I,i |-: an
`
`We work with leading authors to develop the strongest educational materials in
`computer science. bringing cutting-edge thinking and best learning practice In a global
`market.
`
`Under a range of weI1—i:n-awn Imprints, including Addison-Wesley, we crafi high quality
`print and electronic publications which help readers to understand and apply their content,
`whether studying or at work.
`
`Tb find out about the complete range of our publishing please visit us on the
`world Wide Web at;
`
`hltp:.r'Iwww_pea:sonedu1:.Dom
`
`0003
`
`

`
`Computer
`Graphics
`
`THIRD EDITION
`
`ALAN WATT
`
`ifi, ADDISON-‘WESLEY
`
`An imprfnl uni’ PEARSON EDUCATION
`Hanan England - |.ondnn - New ‘tori: - Reading. Mnuchumts - San Francisco - Tomrwn 1 Dan Mina... Unuflo - Sydney
`Tolqrq - Singapore - Hang Kong - Suuul - Taipei - Cape Twrrl r Madrid — Mu:-:|ou City - Nmtenda-II1 r Munich - Fan-1:
`- Milan
`
`0004
`
`

`
`husnnlducluouummni.
`E:I|n'I:.uu1I3m
`I-llflnrur
`Emerita-[Z113]!
`|'-M-ill
`
`Ind-1-nochcltdiacnw-uIJcm1roIuIInI.flIi=nvmd::I
`l"NtIastIu-fln:'||'i:r;Id'|II'li-1\'EIi-al:-
`ww
`
`Hlltjnblilshad I939
`-hI1mdIdlIion1993
`Thhadhinnhupdalhhedaflm
`o19sa,199aMaam-uucynahuuun;1u.Mdmn-uuqrauunm; Colnpnqrlnc.
`flPHfl$DI'lE|hIfl'BInI.iIn'Htd2l}llJ
`
`T|1iI:ig1rInI.fl.l.|n1||.|2IltInbeIb.Il.flaclI5luIiIurvnl
`ilnswukhnsbaautmudhyhlmlinmrdutmnllh
`1heCngyri5|1I,Dui¢I'u.IndPlb¢nu.u:t19Il».
`
`.hfl:'|ghbruIrud;nnplnnlflflipflic||hnm|ybIIfindaaI6,IIcnd
`matmuflwumwummuudmuyhmwbymrmumuemuk.
`mxhldnl.
`lanutIHn.g.urnlhn-nlnelflthnndliznrthzprilr
`1I'mhenpuuIu1m1 mchflbhmualhmmpwnmumukmmfim
`lnlhaflnllndllxfiqnluuicdhyflpefinpytqillllzennsgaigncjrlad,
`flI1bmnhm0nu1lnul.hnmonwIT4L?.
`
`lhapnsrnmmlhhhnnkhnubnmindududtmtbehimuuuamtllnhu.
`Illaptlnlldlu-mnsI'nIvfleI'uI3.IwInI:Ith:.ar
`ufimhlupendmflr
`&nre:nIlatupu1s.u.|1|tpup-nrsnmtdoeuthepu
`uncgplmyhlhllqrlatmgr
`hflotdlmlgztuflauthlnlotwxmnalhljwrwdwthlirflllgfiumfllehwc.
`LHny:[Iluflafl5:.|€heI5uldbyn.uuflrm:u:u|dan1|uI1ed.hflI1ylihfl|dr
`pmdiltnzmdlmdnmu-unaIla.remuIIEducIunnummdtuII'nnduuI3r
`nuunpmmpplyuademulh-Lfurmuumubunmnnul-crurasudunurprodtacls
`Inuumundmuuuuukauuofutdtmutdcuunllommdiheummeu
`ififlI'i¢I'|fll.flEI.L
`I§INl]fl|!I-H559
`
`Mmwm um
`Auuhgumufllulhuboolanhoulmdnmmcwmhuhuy.
`
`LHflWWwm kH
`Aflflfllifinmllltpuflhlna.
`
`T!'MII|||3'43
`P:|1'nIn|!I|:.IlI:u:u1'niIn‘.I.'I:aUr|1I:acl$IIIu|;n'lu1uflu
`1|?-*9!-T
`|.'I3‘D6Cl.§0|I03
`
`0005
`
`

`
`Para Dionéa
`
`a gamta de Copacabana
`
`0006
`
`

`
`Contents
`
`Colo-urplates nppeartretweenpages 5116 audit)?
`Prefiaoe
`
`Ad
`
`Hllllllultlul funtllmenllls of computer graphics
`1.1
`
`Manipulatlng three-dlmensional structures
`1.1.1
`11-mee-¢:IImensIona1 geometry In eornputer graphics —
`affine transfonnations
`
`1.1.2 Transfonnatjonsfnr changing coordinate systems
`
`Structure-cIefo=n'nlng transformations
`
`Vectors and oornputer graphics
`I .11 Addition of vectors
`
`1.3.2 Length 01 vectors
`1.3.3 Normal vectors and cross products
`1.3.4 Nonnal vectors and dot products
`1.3.5 Vectorsassodatedwiththenotmalvectorrefleclion
`
`Rays and computer grnphiu
`1.4.1
`Ray geometry — intersections
`1.4.2
`Intersections — raybsphere
`1.4.3
`intersections - ray-convex polygon
`1.4.4
`Intersections — rny—box
`1.4.5 mterseaztions — ray-quadric
`1.4.6 Ray tracing geornetry - reflection and refraction
`
`1.5
`
`Interpol:-ting properties In the Image plane
`
` n and modelling of Illree-dllnenslonll objects {1}
`Introduction
`
`2.1
`
`Folygonal representation oi three-dlmertslonal ohlects
`2.1.1 Creating polygonal objects
`
`0007
`
`

`
`2.1.2 Manual modelling of polygonal obiects
`2.1.3 Autornetlc generation oi polygonal objects
`2.1.4 Mathematical generation of polygonal objects
`2.1.5
`Procedural polygon mesh objects - fractal obiecls
`
`Constructive solid geometry {C545} representation of objects
`
`Space sub-disrlslpn techniques for object representation
`2.3.! Oclnees and polygons
`2.3.2
`ESP trees
`
`2.3.3 Creating vowel obi-ecls
`
`2.4 Represenrlzlng obiects with implicit functions
`
`2.5 Some management and object reperesentatlon
`2.5.1
`Polygon mesh optimization
`
`2.16 Summary
`
`Illprlel-llltlltlon Ind modeling -of III-no-drnenslnnll ob|IcI3{1}
`Introduction
`
`3.1 Bezier curves
`
`3.1.1
`3.1.2
`
`joining Bézier curve segments
`Summary ol ll-ézler curve properties
`
`B-spline representation
`3.2.1
`I-spline cunres
`3.2.2 Uniform B-splines
`3.2.3 Non—unilorrn B-splines
`3.2.4 Summary ol‘ B-spline curve properties
`llatlonal curves
`3.3.1 Rational Beaver curves
`3.3.2 NUILBS
`
`From curves to surfaces
`
`3.4.1 Continuity and Bézier palrhes
`3.4.2 A B-ézler patdr object — the Utah teapot
`
`B-spline surface patches
`
`Modelling or creating patell surfaees
`3.6.1 Cross-sectional or linear axis design example
`3.5.2 Control polyhedron design - basic technique
`3.6.3 Creating patnh objects by surface fiming
`
`3.: From patches to objects
`
`4
`
`lepnesentotlnn In-cl nrldlrlng
`lntroduclion
`
`4.1 Rendering polygon meshes - a brief overview
`
`0008
`
`

`
`4.2 Itendering parametric surfaces
`4.2.1
`itendeiing directly from the patch descriptions
`4.2.2
`Patch to polygon corwersion
`4.2.3 Object space subdivision
`4.2.4
`Image space subdivision
`
`4.3 Rendering a C56 description
`
`-I-.4
`
`Iilenclering a vowel description
`
`-its Rendering implicit fratctions
`
`The graphics pipeline {I}: gcolnltric operations
`Introduction
`
`5.1 Coordinate spaces In the graphics pipeline
`5.1.1
`Local or modelling coordinate systems
`5.1.2 World coordinate systerns
`5.1.3 Camera or eye orview coordinate system
`
`Dperltlons carried out in view space
`5.2.1
`Culling or back-face eiirniriatiori
`5.2.2 The View volume
`
`5.2.3 Three-dimensional screen space
`5.2.4 View volume and depth
`
`5.3 Advenoed viewing systers-is {PHIGS and arts)
`5.3.1 Direnriew oi the PHIGS viewing system
`5.3.2 The view orientation parameters
`5.3.3 The View mapping parameters
`5.3.4 The view piane in rnore detail
`5.3.5
`Implementing an PHIGS-type viewing system
`
`11re graphics pipeline (1'): rand-arlng or algorfthrnlc processes
`introduction
`
`6.1 Clipping polygons against the view Irolurne
`6.2 Slladlrrg pixels
`6.2.1
`Local reiiection models
`
`Local reiiecticin rnodeis — practical points
`6.2.2
`6.2.3 Local reflection models — light source considerations
`
`interpolative shading techniques
`6.3.1
`Inter-poiathre shading techniques - Gouraud shading
`6.3.2
`intaerpoiathre shading techniques - Phong shading
`6.3.3
`iiendener shading options
`5.3.4 Comparison of Gouraud and Phong shading
`itasterization
`
`6.4.1
`6.4.2
`
`itasterizing edge
`Ilasterizing polygons
`
`0009
`
`

`
`6.6 Hlvdden slsrfece removal
`6.6.1
`The Z-buffer algtrrithm
`6.6.2 Z-buffer and CS5 representatlnn
`6.6.3
`I-buffer and compasiting
`6.6.4 Z-buffer and rendering
`6.6.6
`Scan line Z-bttffer
`
`6.6.6 Spanning hidden surface remcwal
`6.6.? A spanning scan line algorithm
`6.6.8
`I-buffer and cumplett scenes
`6.6.9
`I-buffer surrunary
`6.6.10 BSP trees and hidden surface removal
`
`6.?
`
`Iufulti-pass rendering and ecctunulatlnn buffer:
`
`7 Slrrltletlnglglrt-olaiectftslaerectlonr Intel nllectlun rneclels
`Introduction
`
`11 ltefiectlen from a perfect surfece
`
`12 Iteflectlon here an imperfect surfece
`13 The bl-directional rellectance clstrflsutlnn function
`
`14 Diffuse and specular cerhprments
`
`15 Perfect dffuse - empirically spread specular reflection
`
`7.6 Physicelly based specular reflectfon
`16.1 Modelling the mlap-geometry of the surface
`16.2
`Shactnwing and masking effects
`16.3 ‘viewing geometry
`1.6.4 The Fnesnel terrrl
`
`1? Pre-computing Illtflfs
`
`16 Pltyslcllly baaed diffuse component
`
`Illpplng techniques
`Intmduction
`
`6.1 1im:-dlmenslunal texture maps to palygen mesh objects
`3.1.1
`Inverse mapping ly bilinear Interpolation
`8.1.2
`Inverse mapping by using an intennediate surface
`‘Mo-dinserulonal tenure dumaln to bl-cubic parametric patch
`ohfects
`Billboards
`
`B‘-ump mapping
`8.4.1
`A multi-pass technique for hump mapping
`8.4.2
`.6 pm-calculations technique for bump mapping
`
`0010
`
`

`
`8.5 Light rnlps
`
`3.6 Environment or reflection mapping
`B.fi.1
`Cubic mapping
`3.6.2
`Sphere mapping
`t1-.63 Environment mapping: comp-arathre points
`5.6.4
`Surface propa.-rtIes and environment mapping
`
`Three-dirnen.s|ona| texture domain tedtnlques.
`3.11
`Three-dimensional noise
`
`$.12
`8.47.3
`
`Sirnulatingturtnulence
`T1'tree~d1rnensionaIteJ-tture and anirrtation
`
`8.3’.-4 Three-dimensional Ilght maps
`
`8.3 Antl-allaslng and texture mapping
`
`8.9 Interactive techniques In texture mapping
`
`9 Geonutrlc alt-ado-us
`Introductlon
`
`9.1 Properties of shadows used In computer graphics
`
`9.! Simple shadows on a ground plane
`
`9.3 Shadow algorithms
`
`9.3.1
`9.3.2
`9.3.3
`
`Shadow algorithms: projecting polygorssfscan line
`Shadow algorithrns: shadow volurnes
`Shadow algorithrns: deritration of shadow potygorts from
`light source transformations
`9.3.4 Shadow algorithms: shadow I-hufier
`
`‘It! Global Ilnunlnartlon
`Introduction
`
`ln.1 Gfohal Illumination models
`
`19.1.1 The rendering equation
`19.1.2 Radiance, irradiance and the radiance equation
`10.1.3 Path notation
`
`11.1.2 The evolution of global Illumination algorithms
`
`111.3 Established adgorttl1ms— ray traclng and radloslty
`10.3.1 'II'II'|1itteo| ray tracing
`11.1.3.2 Iladiosity
`
`1tI.-I Monte Carlo tecltniques In global Illumination
`
`10.5 Path traclng
`
`19.6 Dlstrlbutod ray tracing
`
`1l1.? Two-pass ray tracing
`
`10.8 View dependencefindepcntlonce and rnulti-pass methods
`
`0011
`
`

`
`10.9 (Inching Illumination
`
`1iJ.1i:| Light Volume:
`
`10.11 Particle tretlng and density estimation
`
`11
`
`Thu rfllolltf I‘I'II|‘I'|oII
`introduction
`
`11.1 itadiosity theory
`11.2 Form factor determination
`
`11.3 The Gauss-—5eide| method
`
`11.4 Seeing an partial solution — progressive refinement
`
`11.5 Problems with the radiosity method
`
`11.6 ilurtefatts in radlosity hnoges
`11.6.1 Hernitube artefacts
`11.6.2 |1ecI:r'lstIu:tion artefascts
`
`11.6.3 Meshing artlefacis
`
`11.? iuieshing strategies
`11.2.1 Adapfiveotoposrerfoflmeshlng
`11.2.2 .-tpriorimeshlng
`
`II!‘ tracing all-Iloglu
`Introduction - Whltted ray training
`
`12.1 The basis: algorithm
`12.1.1 Tracing rays — initial considerations
`12.1.2 Lighting model corr-ponents
`12.1.3 Shadows
`12.1.4 Hidden sutface renttwal
`
`12.2 Using recursion to irrlpivetltent ray tracing
`
`12.3 Theadventtwesofsevenrays-aroytradngmrdgr
`
`12.4 Ray tracing polygon objects — Interpolation of a normal at an
`lnmaoctlon point In on polygon
`
`12.5 Efflclenqr measures in ray trodng
`12.5.1 Adaptive depth control
`12.5.2 First hit speed up
`'|2.5.3 Bounding objects with sirnpie shapes
`12.5.-1 Secondary data S1.l'l.ICt‘i.II'E5
`12.5.5 flay space wbdivision
`
`12.6 1111: use of ray oohervenoe
`
`12.? A historical digression - the optics of the rainbow
`
`0012
`
`

`
`Volume rendering
`Introduction
`
`13.1 'W.l-Il.lrI'|!& I'¢l‘Id'El'Il'lsg and the vlsuaflzatlon oi volume data
`
`13.2 ‘semi-transparent gel‘ option
`1 3.2.1 Vowel classification
`
`13.2.2 Transfon-ning into the viewing direction
`13.2.3 Caumpofiling pixels along a ray
`
`13.3 5«emI-transparent gel plus surfaces
`13.3.1 Explicit extraction ol lsosurfaces
`
`13.4 Stu-uctural considerations In volume rendering alga.-III-urns
`13.1.1 Ray casting [untransforrned data)
`13.4.2 llay casting [transformed data]-
`13.-L3 "l|'t:ote| project]-an mel;l'Io-d
`
`13.5 Perspective projection in volume rendering
`
`‘I3-.6 Threewdlnrensionnl texture and volume rendering
`
`‘II Altlivlllulng llnoly and prlctlu
`Introduction
`
`14.1 Aliases and samplng
`
`14-2 I399!‘ $595
`
`14.3 Sampling in computer graphics compared with sampling ruily
`14.4 Sampling and reconstruction
`
`14.5 A simple oomparison
`
`14.5 Pre-filtering methods
`
`14.? Supersampllng or post-filtering
`
`14.5 Non-unlforrn sampling - some theoretical concepts
`
`14.9 111.e Fourier transform of Images
`
`15 Colour and computer gnphlea
`lntmducllion
`
`15.1 Colour sets in computer Imagery
`
`15.2 Colour and tltnee-cllm-ensional space
`15.2.1 RG11 space
`15.2.2 The HSV single heat-lrone model
`15.2.3 ‘(IQ space
`
`15.3 Colour. lnfon11atIort and perceptual spaces
`15.3.1 C1E DWI space
`15.3.2 CIE xyrspace
`
`15.4 Itendering and colour spaoes
`
`0013
`
`

`
`15.5 Monitor considerations
`
`15.5.1 RGB......n.. space and other monitor considerations
`15.5.2 Monitor considerations — difiereni. monitors and the
`same colour
`
`15.5.3 Monitor considerations - colour gamut mapping
`15.5.4 Monitor considerations — gamma correction
`
`16
`
`hung:-Insarl rendering and photo-rnodelllng
`Introduction
`
`16.1 Reuse oi previously rendered imagery - two-dimensional
`techniques
`16.1.1 Planar impostors or sprites
`16.1.2 Calculating the validity of planar impostflfi
`
`16.2 ‘iiarjrlng rendering resources
`16.2.1 Priority rendering
`16.2.2 Image layering
`
`16.3 Using depth lninnnation
`16.3.1 Three-dimensional warping
`16.3.2 Layered depth images (LDls}
`
`16.4 View interpolation
`16.4.1 ‘iriew morphing
`
`16.5 Four-dimensional techniques - the Lurnigraph or light field
`rendering approach
`
`16.6 Photo-modelling and IBR
`16.6.1 Image-baaed rendering using photographic panoramas
`16.6.2 Ccrmpocsiting panoramas
`16.6.3 Photo-modelling for image-hosed rendering
`
`1?
`
`computer animation
`Introduction
`
`11.1 A categorization and description of computer animation
`techniques
`
`‘I12 Rigid hotly animation
`1}'.2.'I
`Interpolation or lteyfrarning
`13.2.2 Explicit scripting
`112.3 Interpolation of mutation
`112.4 Using quatemions to represent rotation
`112.5 Inte-rpoiating quaternions
`112.6 The camera as an anirnated object
`ljnlrecl structures and hierarchical motion
`
`113.1 Solving the imrerse kinematics problem
`
`0014
`
`

`
`114 Dynamics In computer anlmation
`114.1 Easlc theory for a rigid hody— particles
`114.2 The nature of forces
`
`114.3 Rigid bodies - exhended masses
`114.4 Using dynamics in computer animation
`114.5 Simulating the dynamics of a lumped mass
`114.6 Space-tlme constraint.-r
`115 Colllsion detection
`
`1 15.1 Broad phosaejnarrow phase algorithms
`115.2 Broad phase collision detection with DEB:
`11.5.3 Narrow phase: pairs of convex polyhedra - exact collision
`detection
`
`115.4 Single phase algorithms — obiect hieran-_hIes
`
`1115 Collision response
`11? Particle animation
`
`118 Bellatrloural anlmatioll
`
`119 Summary
`
`Colltplrllltrt Image shady
`introduction
`
`181 Local reflectlorl models
`
`18.2 Texture and shadow mapping
`
`18.3 1l'll‘I1ltted ray tracing
`
`18.4 llldlosity
`18.5 HADIANCE
`
`18.6 Summary
`
`Illenncea
`
`Index
`
`0015
`
`

`
`This is the third edition oi a book that deals with the prooenes involved in
`converting a mathematical or geometric description of an object — a computer
`graphics mode] - into a visualization - a two-dimensional projection - that
`simulates the appearance of a real oh|ect. The analogy of a synthetic camera is
`oftenusedandthisisagoodaliustortprovldedwebearinmindcertainimportant
`limitations that are not usually available in a computer graphics camera (depth of
`field and motion blur are two examples} and certain computer graphics facilities
`that do not appear in a camera {near and far clipping planes).
`Algorithms in computer graphit: mostly function in a threedlmenslonal
`domain and the creations in this space are then mapped into a two-dimensional
`display or image plane at a late stage in the overall process. Traditionally oom-
`puter graphics has created pictures by starting with a very detailed geometric
`description, suhlecting this to a scrim of transformations that orient a viewer
`and objects in three-dlrnensional space. then imitating reality by making the
`objects lo-olt solid and real — a process ltriown as rendering. In the early 1950:
`there was a oomlng together of research — carried out in the 1970: into reflection
`models, hidden surface removal and the like - that resulted in the emergence of
`a de jircto approach to image synthesis of solid oblects. But now this is proving
`Insufficient for the new demands oi moving computer imagery and virtual re-
`ality and much research is being carried out into how to model complex objects,
`where the nature and shape of the object changes dynarnicaiiy and into captur-
`ing the richness of the world without having to explicitly mode] every detail.
`Such efforts are resulting in diverse synthesis methods and modelling rnethods
`but at the Il'lD‘I|1EI'lt there has been no emergence of new image generation tech-
`niques that rival the pseudo-standard way of modelling and rendering solid
`objects - a method that has been established since the ttiid-I9‘?t]s.
`So where did it all begin? Most of the deveioprnerit in computer graphics as
`we lmotv it today was motivated by hardware evolution and the availability of
`new devices. Software rapidly developed to use the image psodudng hardware.
`In this respect the most important developmecnt is the so-called raster display. a
`device that proliferated in the mass market shortly after the development of the
`PC. In this device the complete image is stored in a memory variously called a
`
`0016
`
`

`
`Iigirlfii
`The main elements of:
`9.-spmssystern.
`
`frame store. a screen buffer or a refresh I:r’ierr1or'_tr. This information - the dis»
`cretioed oomputer image — is oontinually converted by a video controller into a
`set of horizontal scan lines {a raster) which is then fed to a Ti-'-type monitor. The
`image is generated by an application program which usually accesses a model or
`geometric description of an oblect or ohiects. The main elements in such a sys-
`tem are shown in Figure R1. The display hardware to the right of the dotted line
`can be separate to the processor. but nowadays is usually integrated as in the case
`of an enhanced PC or a graphics workstation. The raster graphics device over-
`shad-ot-vs all other hardware developments in the sense that it made possible the
`display of shaded three-dimensional ol'J|ects — the single most important tl1eo-
`reticai development. The inte:raction of three-dimensional oblects with a light
`source oould be calculated and the effect projected into ttvo-dimensional space
`and displayed by the device. Such shaded imagery is the foundation of modern
`computer graphics.
`"lite two early landmark achievements that made shaded imagery possible are
`the algorithms developed by Gouraud in i9?i and Phong in Il9?5 enabling easy
`and fast calculation oi the intensifies of pixels when shading an object. The
`Phong technique is still in mainstream use and is undoubtedly responsible for
`most of the shaded images in computer graphics.
`
`A brief history of shaded imagery
`
`When we tool: at oomputer graphics from the viewpoint of its practitioners, we
`see that since the mid-i.9?ils the developmental motivation has been photo-
`reaiism or the pursuit oi‘ techniques that matte a graphics image of an oblect or
`scene irtdistingilishable from a TV image or photograph. A more recent strartd of
`the application of l'l1-ese techniques is to display information in. for example.
`medicine. science and engineetirig.
`The foundation of photo-realism is the calculation oi‘ lighI:—ob|ecr interaction
`and this splits neatly into two fields - the development of local reiiection
`
`0017
`
`

`
`models and the development of global models. Local or direct relleetion models
`only consider the interaction or’ an object with a light source as If the ob|ect and
`light were floating in dark space. That is, only the first reflection of light from
`the object is considered. Global retiection models consider how light reflects
`from one object and travels onto another. In other words the light impinging on
`a point on the surface can ccrne either from a light source [direct light} or iridi-
`rect light that has first hit another object. Global interaction is for the most part
`an unsolved problem, although two partial sohitions, ray tracing and radlositv.
`are now widely implemented.
`Computer graphics research has gone the way of much modern scientific
`researdt — early major advances are created and consolidaced into a practical
`technology. Later significant advances seem to be more diflicult to achieve. We
`can say that most images are produced using the Phorig local reflection model
`[first reported in 19?5]. fewer using ray tracing {first popularized in 19%] and
`fewer still using radlosity (first reported in 198.4]. Aldtough there is still much
`research being carried out in Light-scene interaction methodologies much oi‘ the
`current research in computer graphics is concerned more with applications, for
`eirample.t~1th such general applications as animation, visualization and virtual
`reality. in the most important computer graphics publication mu: annual SIG»
`GRAPH conference proceedings) there was in I935 a total of 22 papers con-
`cerned with the production techniques of images (rendering. modelling and
`hardware) compared with 13 on what could loosely be called applications. A
`decade later in 1995 there were 33' papers on appilmiions and I? on image pro-
`duction techniques.
`
`(3
`
`Modelling surface reflection with local interaction
`
`Two early advances which went hand-in-hand were the development of hidden
`surface removal algorithms and shaded imagery —- simulating the interaction of
`an ob|et:t with a light source. Most of the hidden surface removal research was
`carried out in the l9?Ds and nowadays. tor general-purpose use, the most com-
`mon algorithm is the zeiurter .— an approach that is very easy to implement and
`combine with shading or rendering algorithms
`In shaded imagery the major prop is the Phone reflection model. This Is an
`elegant but completely empirical model that usually ends up with an obiect
`reflecting more light than it receives. its parameters are based on the grossest
`aspects of reduction of light from a surface. Despite this, it is the most widely
`used model in computer graphics - responsible for the vast ma|crit}r or created
`images. Why is this so? Probably because users find it adequate and it is easy to
`implement.
`llieoretically based reflection models attempt to model reliection more accu-
`rately and their parameters have physical meaning — that is they can be mea-
`sured for a real surlace. For example, light rellects dlflerenthr from an isotropic
`surface, such as plastic. compared no its behaviour with a non-isotropic surface
`
`0018
`
`

`
`PREFACE @
`
`such as brushed aluminium and such an effect can be imitated by explicitly
`modelling the surface cha.racterIstl. such models attempt to imitate the behav-
`iour of light at a "mlllisr:ale' level (where the roughness or surface geometry is
`still much greater titan the wavelength of light}. Their purpose is to imitate the
`material signature — why different materials in reality look different.
`Altemathlely. parameters of a model can be measured on a real surface and used
`in a simulation. The work into more elaborate or theoretical local reilection
`
`models does not seem to have gained any widespread acceptance as far as its
`implementation in rendering systems is concerned. This may be due to the fact
`that users do not perceive that the extra processing costs are worth the some-
`what marginal improvement in the appearance of the shaded object.
`all these models, while attending to the accurate modelling of light from a
`surface, are local models which means that they only consider the interaction of
`light with the obiect as if the obiect was floating In free space. No ob]ect—ob|ect
`interaction is considered and one of the main problems that immediately arises
`is that shadows — a phenomenon due to global interaction - are not incorporated
`into the model and have to be calculated by a separate ‘add-on’ algorithm.
`The development of the Phong reilectlon model spawned research into add-
`on shadow algorithms and texture mapping, both of which e11l'tan-ced the
`appearance of the shaded ob|ect. and tempered the otherwise ‘floating irl free
`space’ plastic look of the basic Pholng mode].
`
`(D
`
`Modelling global Interaction
`
`The 1950s saw the development of two significant global models - light reflec-
`tion modeis that attempt to evaluate the interaction between obiects. Global
`interaction gives rise to such phenomena as the determination of the Intensity
`of light within a shadow area, the reflection of objects In each other {specular
`interaction) and a subtle effect known as colour bleeding where the colour from
`a diffuse surface is transported to another nearby surface {diffuse Interaction}.
`The light intensity within a shadow area can only be determined from global
`interaction. An area in shadow, by definition. cannot receive light directly from
`a light source but only indirectly from light reflecting front another object.
`inihenyouseeshinyobiectsiriasceneytruexpecttoseein tlie-tit refieciionsof
`other obiects. A very shiny surface. such as chromium plate, behaves almost as
`a mirror taking all its surface detail from its surroundings and distorting this geo-
`metrically accordlng to stirlace curvature.
`The successful global models are ray tracing and raclioslty. However, in their
`basic implementation both models only cater for one aspect of global illumina-
`tion.
`ltay tracing attends to perfect specular reflection - very shiny oblects
`reflectirig in each other, and radlosity models diffuse interaction which is light
`reilecting off matte surfaces to illuminate other surfaces. Diffuse interaction is
`
`common in man-made interiors which tend to have carpets on the floor and
`matte finishes on the walls. Areas in a room that cannot see the light source are
`
`0019
`
`

`
`iilumirtatecl by ciiifuse interaction. Munuaiiy exclusive in the phenomena they
`model, images creatned by both methods tend to have identifying "signatures".
`Ra}!-traced Images are notable for perfect rectirsive reflectitlris and super sharp
`refraction. Raidioslty images are usirally of softly-lit interiors and do not oontaln
`specular or shiny objects.
`Computer graphics is not an exact science. Much research in light-surface
`interaction in computer graphics proceeds by taking existing physical models
`and simulating then with a computer graphics algorithm. This may involve
`muen simplification in the original mathematical model so that it can he imple-
`mented as a computer graphics algorithm. Ray I1-acin; and ratiioslty are classic
`examples of this tendency. Simplifications, which may appear gross to a mathe-
`matician, are made by computer graphlcists for practical reasons. The reason this
`process ‘works’ is that when we look at a sjritthlzed scene we do not generally
`perceive the sirnpli.ficatioos in the mathematics unless they result in visible
`degerierarzies known as aliases. However, most people can easily distinguish a
`computer graphics image from a photograph. Thus computer gmplucs. have a
`‘realism’ of their own that is a function of the model. and the neamess of the
`computer graphics image to a photograph of a real scene varies widely accord-
`ing to the method. Photo-realism in computer graphics means the image looks
`real not that it approaches. on a pixel by pixel basis, a photograph. This subjec-
`tive |ud.ge:rne:nt of oomputergraphics images somewhat devslues the widely used
`ad|ectiire *photo-realistic’, but there you are. with one or two exceptions very lit-
`tle worit has been done on comparing a human's perception of a computer
`graphics image with_. say, a TV iiriage of the equivalent real scene.
`
`0020
`
`

`
`- Acknowledgements
`
`The author would like to than]: the following:
`
`I Ligiitworlr Design Ltd (Sheffield. UK) and Dave Cauldron for providing the
`facilities to produce the front newer Image {model of the Tate Gallery, St Ives.
`UK} and the renderer, iiadloltay.
`
`Daniel Tieece for the images on the back cover which he produced as part of
`his PhD thesis and which comprise three-dimensional palm strokes
`interactively applied to a standard polygon model.
`
`Lee Cooper for prodiicing Figures -5.12, ?.E, 8.23, 3.10, 10.4, 15.1. 18.3. 18.5,
`13.5, 13.1, 13.11, 1:19, 13.10, 13.11, 111.12, 111.13, 111.14, 13.16. 111.11 and
`18.19 together with the majority of Images on the CD-ROM. These were
`produced using Llghrworlrs Application Development System kindly
`supplied by Llghtworit Design Ltd.
`Mari: Puller for Figtue13.1.
`
`Steve Haddock for Figures 1.5, 4.9, 3.8, 5.215.
`
`Agata Opaiach for Figure 2.20.
`Klaus de Geuss for Figures 13.10 an-113.11.
`
`Guy Brown for Figure 16.19.
`Fat‘.-io Policarpo for Figure 8.14.
`
`O ll~.{Dh-1' Uiiiirersity, l-iarni:-u:rg.. for Figure 13.3.
`
`in addition the author would like to thank Keith Mansfield, the production staff at
`Addison-Wesley, Robert Chaundry of Boolrstylc for his care with the manuscript
`and Dinnea Watt for the cover design.
`
`The ptlh-lishers are grateful to the following for permission to reproduce copyright
`material:
`
`Figure 2.1 reproduced with the permission of Viewpoint Digital, Inc; Figure 2.4
`from mi:-nut: Computer Graphics, Ze [Beatty and ll-c-oth, 19821, O 1932 lF.i:'.E, The
`Institute of Electrical and Electronics Engineners, Inc, New Yorlr; Flgtues 2.? and 2.8
`from Gem-11:11-e Modeiiingfar Carnpuarr Gmpiifcr and CAD (Snyder, 19921, Academic
`
`0021
`
`

`
`(ED Acxuumsncmsms
`
`Pam, Inndan:Figure2.20reprodumdwid1mepumisslm1ofAgau0paJach:Flgu12
`13.3 from VUXEL-WIN, Part 1': Drab: andslurll, CD-ROM for UNIX workstauons and
`Lmux pcg, version 1.1 n Karl-I-rem: HG-l1neand5PTlIl£Ef-Verlag GmbH :5: Co. KG
`1996. reproduced I-V111: kind pennlrslm; Figure 16.14 mpmdrrczd with the permlsr
`sionoistmen Seitz; Fig-use 11.23 ErnmACM11urIsnc1iar1sarIGmpIrJ:s.15:3,]uIyl996
`(Hubbard. 1996], ACM Ptlbllcartiorrs, New ‘fork.
`
`fifl1fl5tEVuj'EEfmtha5beeJ1madetotacefl|emmeIsofDnpyrlgh1mateflal.ma
`Eewcasesrhbhupwvedlmposslbleandwetaherhisappamuriqrtuofiermn
`apaluglu to any copy-1-Iglrt holders whose rights we may have unwltdragly
`infringed.
`
`Trademark nutlte
`
`Apple" and Qmckhme“ are trade-rnarks of Apple Computer, Inc.
`LuxnT' is a trademark ufjac Jacobson Industries.
`Kodak“ is a trademark of Eastman Kodak Company.
`I1enderM;an“' is a uachrnrark at Pixar Curpmatlon.
`VAX?" ls a trademark of Digital Equipment Curpnratlon.
`3D Data.-rein‘ is 1 tradtmaxk ml‘ Vtewpolnt Digltal. Inc.
`
`0022
`
`

`
`GD
`
`Mathematical fundamentals of
`computer graphics
`
`1.1 Menipularttng three-dimensional stnrctures
`
`1.2 Structure-defonnlng transionnations
`
`1.3 Vectors and computer graphics
`
`1.4
`
`Iiays and computer graphics
`
`1.5
`
`interpolating properties in the image plane
`
`03
`
`Manipulating three-cllrnortslortal structures
`
`Transfonnations are important tools in generating three-dimensional scenes.
`They are used to move ohleciri around in an emrironment, and also to construct
`a two-dimensional view of the environment for a display surface. This chapter
`deals with basic three-dimensional transfonnations, and introduces some useful
`sltape-changing transformations and basic three-dimensional geometry that we
`will be using later in the text.
`in oompuiner graphics the most popular method for representing an object
`is die polygon mesh model. This representation is fully described in Chapter 2.
`We do this by representing the surface of an ol:I|ect as a set of connected planar
`polygons and each polygon is a list of [connected] points. This form of
`representation is either enact or an approximation depending on the nature of
`the obiect. A cube. for example. can be represented exactly by sir. squares. A
`cylinder, on the other hand can only be approximated by polygons; say six rec-
`tangles for the curved surface and two hexagons for the end faces. The number
`of polygons used tn the approxlrnatlon determines how accurately the ohiect
`lsrepresentedandthtshasrepercusstonsinmodeujn,geost,storageand
`rendering cost and quality. The popularity of the polygon mesh modelling tech-
`nique in oontputer graphics is undoubtediy due to its inherent simplicity
`and the development or‘ inexpensive shading algorithms that work with such
`models.
`
`0023
`
`

`
`(3 MATHEMATICAL sun DAMENTALS or computes oiimiics
`
`A polygon mesh model consists of a structure of vertices. each vertex beinga
`three-dimensional point in so-called world coordinate space. Later we will be
`concerned with how yertioes are connected to form polygons and how polygons
`are structusecl Into complete objects. But to start with we shall consider obiects
`just as a set of three-dimensional verttces and look at how these are transiormed
`in three-dimensional space using linear transforrriations.
`
`Three-dimensional geometry in computer graphics - affine
`transformations
`
`in this section we look at threevdimensiona] affine transformations. These are
`the transforinations that effect rotation, scaling. shear and translation. Affine
`transformations can be represented by a matrix. and a set of affine transtonna-
`tions can be combined into a single overall affine transformation. Technically we
`say that an affine transformation is made up of any combination of linear trans-
`formations (rotation, scaling and shear} followed by translation.
`Clbiecis are defined in a world coordinate system which is conventionally a
`right-handed system. A right-handed and left-handed three-dimensional coordi-
`nate system is shown in Figure 1.1. Right-handed systems are the standard math-
`ematical convention, although left-handed systetris have, and still are. used in
`the speci