Processing What Are Computer Graphics & Computer

2y ago
38 Views
4 Downloads
1.39 MB
50 Pages
Last View : 1d ago
Last Download : 1d ago
Upload by : Madison Stoltz
Transcription

Computer Graphics & ImageProcessing1Computer Graphics & Image Processing2What are Computer Graphics &Image Processing? Sixteen lecturesPart IBPart II(General) Diploma Scenedescription Computergraphics Normally lectured by Dr Neil Dodgson Three exam questionsImage analysis &computer visionDigitalimageImage processingWhat are Computer Graphics &Image Processing?3 All visual computer output depends onComputer GraphicsScenedescriptionComputergraphicsprinted outputmonitor (CRT/LCD/whatever) all visual computer output consists of real imagesgenerated by the computer from some internaldigital image Image analysis &computer visionDigitalimageImagecapture4Why bother with CG & IP?ImagedisplayImage processing56What are CG & IP used for? 2D computer graphics Image processing graphical user interfaces: Mac, Windows, X, graphic design: posters, cereal packets, typesetting: book publishing, report writing, photograph retouching: publishing, posters, photocollaging: satellite imagery, art: new forms of artwork based on digitised imagesCourse Structure Background [3L] visualisation: scientific, medical, architectural, Computer Aided Design (CAD)entertainment: special effect, games, movies, 2003 Neil A. Dodgson3D CGlines, curves, clipping, polygon filling,transformations 3D computer graphics [6L]3D computer graphics images, human vision, displays 2D computer graphics [4L]projection (3D 2D), surfaces,clipping, transformations, lighting,filling, ray tracing, texture mapping2D CGIPBackground Image processing [3L] filtering, compositing, half-toning,dithering, encoding, compression1

Computer Graphics & ImageProcessing78Past exam questionsCourse books Computer Graphics: Principles & Practice Slater, Steed, & Chrysanthou, Addison-Wesley, 2002 Digital Image Processing what is a digital image? 10What is an image?IP two dimensional function value at any point is an intensity or colour not digital!Backgroundwhat are the constraints on digital images? how does human vision work? the course was so different back then that they are not helpful93D CG2D CGthe course changed considerably between 1996 and 1997all questions from 1997 onwards are good examples of hisquestion setting styledo not worry about the last 5 marks of 97/5/2z this is now part of Advanced Graphics syllabusdo not attempt exam questions from 1994 or earlier Gonzalez & Woods, Addison-Wesley, 1992z Alternatives: Digital Image Processing, Gonzalez & Wintz Digital Picture Processing, Rosenfeld & KakBackground Dr Dodgson has been lecturing the course since 1996 Computer Graphics & Virtual Environments Foley, van Dam, Feiner & Hughes,Addison-Wesley, 1990z Older version: Fundamentals of Interactive Computer Graphics Foley & van Dam, Addison-Wesley, 1982what are the limits of human vision?what can we get away with given these constraints& limits? how do displays & printers work? how do we fool the human eye into seeing whatwe want it to see?1112What is a digital image? a contradiction in termsif you can see it, it’s not digital if it’s digital, it’s just a collection of numbers a sampled and quantised version of a realimage a rectangular array of intensity or colourvalues 2003 Neil A. DodgsonImage capture a variety of devices can be used scanners line CCD in a flatbed scannerspot detector in a drum scannercameras area CCD2

Computer Graphics & ImageProcessing1314Image capture exampleImage display a digital image is an array of integers, how doyou display it? reconstruct a real image on some sort ofdisplay device103 59 12 80 56 12 34 30 1 78 79 21 145 156 52 136 143 65 115 129 41 128 143 50 85106 11 74 96 14 85 97 23 66 74 23 73 82 29 67 76 21 40 48 7 33 39 9 94 54 1942 27 6 19 10 3 59 60 28 102 107 41 208 88 63 204 75 54 197 82 63 179 63 46 158 6246 146 49 40 52 65 21 60 68 11 40 51 17 35 37 0 28 29 0 83 50 15 2 0 1 13 148 243 173 161 231 140 69 239 142 89 230 143 90 210 126 79 184 88 48 152 69 35 123 5127 104 41 23 55 45 9 36 27 0 28 28 2 29 28 7 40 28 16 13 13 1 224 167 112 240174 80 227 174 78 227 176 87 233 177 94 213 149 78 196 123 57 141 72 31 108 53 22 12162 22 126 50 24 101 49 35 16 21 1 12 5 0 14 16 11 3 0 0 237 176 83 244 206 123241 236 144 238 222 147 221 190 108 215 170 77 190 135 52 136 93 38 76 35 7 113 56 26156 83 38 107 52 21 31 14 7 9 6 0 20 14 12 255 214 112 242 215 108 246 227 133 239232 152 229 209 123 232 193 98 208 162 64 179 133 47 142 90 32 29 19 27 89 53 21 171116 49 114 64 29 75 49 24 10 9 5 11 16 9 237 190 82 249 221 122 241 225 129 240 219126 240 199 93 218 173 69 188 135 33 219 186 79 189 184 93 136 104 65 112 69 37 191 15380 122 74 28 80 51 19 19 37 47 16 37 32 223 177 83 235 208 105 243 218 125 238 206103 221 188 83 228 204 98 224 220 123 210 194 109 192 159 62 150 98 40 116 73 28 146 10446 109 59 24 75 48 18 27 33 33 47 100 118 216 177 98 223 189 91 239 209 111 236 213117 217 200 108 218 200 100 218 206 104 207 175 76 177 131 54 142 88 41 108 65 22 10359 22 93 53 18 76 50 17 9 10 2 54 76 74 108 111 102 218 194 108 228 203 102 228 200100 212 180 79 220 182 85 198 158 62 180 138 54 155 106 37 132 82 33 95 51 14 87 4815 81 46 14 16 15 0 11 6 0 64 90 91 54 80 93 220 186 97 212 190 105 214 177 86 208165 71 196 150 64 175 127 42 170 117 49 139 89 30 102 53 12 84 43 13 79 46 15 72 4214 10 13 4 12 8 0 69 104 110 58 96 109 130 128 115 196 154 82 196 148 66 183 138 70174 125 56 169 120 54 146 97 41 118 67 24 90 52 16 75 46 16 58 42 19 13 7 9 10 50 18 11 3 66 111 116 70 100 102 78 103 99 57 71 82 162 111 66 141 96 37 152 102 51130 80 31 110 63 21 83 44 11 69 42 12 28 8 0 7 5 10 18 4 0 17 10 2 30 20 1058 88 96 53 88 94 59 91 102 69 99 110 54 80 79 23 69 85 31 34 25 53 41 25 21 20 8 0 0 17 10 4 11 0 0 34 21 13 47 35 23 38 26 14 47 35 23A real imageCRT - computer monitor, TV setLCD - portable computer printer - dot matrix, laser printer, dye sublimation A digital image15Image display example103 59 12 80 56 12 34 30 1 78 79 21 145 156 52 136 143 65 115 129 41 128 143 50 85106 11 74 96 14 85 97 23 66 74 23 73 82 29 67 76 21 40 48 7 33 39 9 94 54 1942 27 6 19 10 3 59 60 28 102 107 41 208 88 63 204 75 54 197 82 63 179 63 46 158 6246 146 49 40 52 65 21 60 68 11 40 51 17 35 37 0 28 29 0 83 50 15 2 0 1 13 148 243 173 161 231 140 69 239 142 89 230 143 90 210 126 79 184 88 48 152 69 35 123 5127 104 41 23 55 45 9 36 27 0 28 28 2 29 28 7 40 28 16 13 13 1 224 167 112 240174 80 227 174 78 227 176 87 233 177 94 213 149 78 196 123 57 141 72 31 108 53 22 12162 22 126 50 24 101 49 35 16 21 1 12 5 0 14 16 11 3 0 0 237 176 83 244 206 123241 236 144 238 222 147 221 190 108 215 170 77 190 135 52 136 93 38 76 35 7 113 56 26156 83 38 107 52 21 31 14 7 9 6 0 20 14 12 255 214 112 242 215 108 246 227 133 239232 152 229 209 123 232 193 98 208 162 64 179 133 47 142 90 32 29 19 27 89 53 21 171116 49 114 64 29 75 49 24 10 9 5 11 16 9 237 190 82 249 221 122 241 225 129 240 219126 240 199 93 218 173 69 188 135 33 219 186 79 189 184 93 136 104 65 112 69 37 191 15380 122 74 28 80 51 19 19 37 47 16 37 32 223 177 83 235 208 105 243 218 125 238 206103 221 188 83 228 204 98 224 220 123 210 194 109 192 159 62 150 98 40 116 73 28 146 10446 109 59 24 75 48 18 27 33 33 47 100 118 216 177 98 223 189 91 239 209 111 236 213117 217 200 108 218 200 100 218 206 104 207 175 76 177 131 54 142 88 41 108 65 22 10359 22 93 53 18 76 50 17 9 10 2 54 76 74 108 111 102 218 194 108 228 203 102 228 200100 212 180 79 220 182 85 198 158 62 180 138 54 155 106 37 132 82 33 95 51 14 87 4815 81 46 14 16 15 0 11 6 0 64 90 91 54 80 93 220 186 97 212 190 105 214 177 86 208165 71 196 150 64 175 127 42 170 117 49 139 89 30 102 53 12 84 43 13 79 46 15 72 4214 10 13 4 12 8 0 69 104 110 58 96 109 130 128 115 196 154 82 196 148 66 183 138 70174 125 56 169 120 54 146 97 41 118 67 24 90 52 16 75 46 16 58 42 19 13 7 9 10 50 18 11 3 66 111 116 70 100 102 78 103 99 57 71 82 162 111 66 141 96 37 152 102 51130 80 31 110 63 21 83 44 11 69 42 12 28 8 0 7 5 10 18 4 0 17 10 2 30 20 1058 88 96 53 88 94 59 91 102 69 99 110 54 80 79 23 69 85 31 34 25 53 41 25 21 20 8 0 0 17 10 4 11 0 0 34 21 13 47 35 23 38 26 14 47 35 23Displayed on a CRTDifferent ways of displaying the samedigital imageNearest-neighboure.g. LCDGaussiane.g. CRT16Half-toninge.g. laser printerThe image data1718Sampling a digital image is a rectangular array ofintensity values each value is called a pixel Sampling resolution256 256128 12864 6432 322 24 48 816 16“picture element” sampling resolution is normally measured inpixels per inch (ppi) or dots per inch (dpi) computer monitors have a resolution around 100 ppilaser printers have resolutions between 300 and 1200 ppi 2003 Neil A. Dodgson3

Computer Graphics & ImageProcessing1920QuantisationQuantisation levels each intensity value is a number for digital storage the intensity values mustbe quantised 8 bits(256 levels)7 bits(128 levels)6 bits(64 levels)5 bits(32 levels)1 bit(2 levels)2 bits(4 levels)3 bits(8 levels)4 bits(16 levels)limits the number of different intensities that can bestoredlimits the brightest intensity that can be stored how many intensity levels are needed forhuman consumption 8 bits usually sufficientsome applications use 10 or 12 bits2122The workings of the human visual systemThe retina to understand the requirements of displays(resolution, quantisation and colour) we needto know how the human eye works. consists of 150 million light receptors retina outputs information to the brain alongthe optic nervethere are 1 million nerve fibres in the optic nervethe retina performs significant pre-processing toreduce the number of signals from 150M to 1M pre-processing includes:The lens of the eye forms animage of the world on theretina: the back surface ofthe eye GW Fig 2.1, 2.2; Sec 2.1.1FLS Fig 35-2averaging multiple inputs togethercolour signal processingedge detection23Some of the processing in the eye discrimination discriminates between different intensities and colours adaptation adapts to changes in illumination level and colourcan see about 1:100 contrast at any given timebut can adapt to see light over a range of 101024Simultaneous contrast as well as responding to changes in overalllight, the eye responds to local changesGLA Fig 1.17GW Fig 2.4 persistence integrates light over a period of about 1/30 second edge detection and edge enhancement visible in e.g. Mach banding effects 2003 Neil A. DodgsonThe centre square is the same intensity in all four cases4

Computer Graphics & ImageProcessing2526Mach bandsGhost squares show the effect of edge enhancement in theretina’s pre-processing another effect caused by retinal pre-processingEach of the nine rectangles is a constant colour2728Light detectors in the retinaFoveal vision two classes 150,000 cones per square millimetre in thefovearods cones cones come in three types high resolutioncolour outside fovea: mostly rodssensitive to short, medium and long wavelengths the fovea is a densely packed region in thecentre of the retina lower resolutionprincipally monochromaticprovides peripheral visioncontains the highest density of cones provides the highest resolution visionz allows you to keep the high resolution region in context z allows you to avoid being hit by passing branchesGW Fig 2.1, 2.229Summary of what human eyes do. sample the image that is projected onto theretina adapt to changing conditions perform non-linear processing makes it very hard to model and predict behaviour pass information to the visual cortex 30What is required for vision? illumination some source of light objects which reflect (or transmit) the light eyes to capture the light as an imagewhich performs extremely complex processingdiscussed in the Computer Vision coursedirect viewing 2003 Neil A. Dodgsontransmissionreflection5

Computer Graphics & ImageProcessing3132Light: wavelengths & spectraClassifying colours light is electromagnetic radiation we want some way of classifying colours and,preferably, quantifying them we will discuss:visible light is a tiny part of the electromagnetic spectrumvisible light ranges in wavelength from 700nm (red end ofspectrum) to 400nm (violet end) every light has a spectrum of wavelengths thatit emitsMIN Fig 22a every object has a spectrum of wavelengthsthat it reflects (or transmits) the combination of the two gives the spectrumof wavelengths that arrive at the eye MIN Examples 1 & 2 Munsell’s artists’ scheme the mechanism of colour vision various colour spaces which classifies colours on a perceptual basishow colour perception workswhich quantify colour based on either physical orperceptual models of colour3334Munsell’s colour classification systemColour vision three axes three types of conehue ¾ the dominant colourlightness ¾ bright colours/dark colourssaturation ¾ vivid colours/dull colours worked out by testing it on peopleeach responds to a different spectrum can represent this as a 3D graph any two adjacent colours are a standard“perceptual” distance apart different numbers of the different types MIN Fig 4Colour plate 1 but how does the eye actually see colour?far fewer of the short wavelength receptorsso cannot see fine detail in blueoverall intensity response of the eye can becalculated invented by A. H. Munsell, an American artist, in 1905 in an attempt to systematically classify coloursJMF Fig 20bvery roughly long, medium, and short wavelengthseach has a response function l(λ), m(λ), s(λ)y(λ) l(λ) m(λ) s(λ)y k P(λ) y(λ) dλ is the perceived luminance3536Colour signals sent to the brain the signal that is sent to the brain is preprocessed by the retinalong mediumlong-mediumlong medium -shortshort luminance red-green yellow-bluethis theory explains: colour-blindness effectswhy red, yellow, green and blue are perceptually importantwhy you can see e.g. a yellowish red but not a greenish red 2003 Neil A. DodgsonChromatic metamerism many different spectra will induce the same responsein our cones the values of the three perceived values can be calculated as:z l k P(λ) l(λ) dλz m k P(λ) m(λ) dλz s k P(λ) s(λ) dλk is some constant, P(λ) is the spectrum of the light incident onthe retinatwo different spectra (e.g. P1(λ) and P2(λ)) can give the samevalues of l, m, swe can thus fool the eye into seeing (almost) any colour bymixing correct proportions of some small number of lights6

Computer Graphics & ImageProcessing3738Mixing coloured lightsXYZ colour space by mixing different amounts of red, green,and blue lights we can generate a wide rangeof responses in the human eye not every wavelength can be represented as amix of red, green, and blue but matching & defining coloured light with amixture of three fixed primaries is desirable CIE define three standard primaries: X, Y, Zgreengreen bluelightoffredlightfully onredFvDFH Sec 13.2.2Figs 13.20, 13.22, 13.23 blueY matches the human eye’s response to light of a constantintensity at each wavelength (luminous-efficiency function of theeye)X, Y, and Z are not themselves colours, they are used fordefining colours – you cannot make a light that emits one ofthese primariesXYZ colour space was defined in 1931 by the Commission Internationale de l’ Éclairage (CIE)3940CIE chromaticity diagramRGB in XYZ space chromaticity values are defined in terms of x, y, zXx ,X Y Z Yy ,X Y ZZz x y z 1X Y Zignores luminancecan be plotted as a 2D functionFvDFH Fig 13.24Colour plate 2pure colours (single wavelength) lie along the outercurve all other colours are a mix of pure colours and hencelie inside the curve points outside the curve do not exist as colours CRTs and LCDs mix red, green, and blue tomake all other colours the red, green, and blue primaries each map toa point in XYZ space any colour within the resulting triangle can bedisplayed any colour outside the triangle cannot be displayedfor example: CRTs cannot display very saturated purples,blues, or greensFvDFH Figs 13.26, 13.274142Colour spacesCIE XYZ, Yxy Pragmatic Munsell-like used because they relate directly to the way that the hardwareworksFvDFH Fig 13.28RGB, CMY, CMYKSummary of colour spacesthe eye has three types of colour receptor therefore we can validly use a three-dimensionalco-ordinate system to represent colour XYZ is one such co-ordinate system Uniform considered by many to be easier for people to use than thepragmatic colour spacesFvDFH Figs 13.30, 13,35HSV, HLSequal steps in any direction make equal perceptual differencesL*a*b*, L*u*v*GLA Figs 2.1, 2.2; Colour plates 3 & 4 2003 Neil A. Dodgson Y is the eye’s response to intensity (luminance)X and Z are, therefore, the colour co-ordinatesz same Y, change X or Z same intensity, different colourz same X and Z, change Y same colour, different intensitysome other systems use three colour co-ordinates luminance can then be derived as some function of the threez e.g. in RGB: Y 0.299 R 0.587 G 0.114 B7

Computer Graphics & ImageProcessing4344Implications of vision on resolutionImplications of vision on quantisation humans can distinguish, at best, about a 2%change in intensityin theory you can see about 600dpi, 30cm fromyour eye in practice, opticians say that the acuity of the eyeis measured as the ability to see a white gap,1 minute wide, between two black lines about 300dpi at 30cm 8 bits is usually sufficient for movie film 14 bits of intensity informationz why use only 8 bits? why is it usually acceptable?resolution decreases as contrast decreases colour resolution is much worse than intensityresolution not so good at distinguishing colour differences for TV 10 bits of intensity informationfor TV the brightest white is about 25x as bright asthe darkest blackthis is exploited in TV broadcastmovie film has about 10x the contrast ratio of TV4546Storing images in memoryColour images 8 bits has become a de facto standard forgreyscale images memory is 1D, images are 2Dbase 1 5 2 43210tend to be 24 bits per pixel can be stored as a contiguous block of memory more common to store each colour in a separate “plane” the idea of planes can be extended to other attributesassociated with each pixel 8 bits 1 byte an image of size W H can therefore be stored ina block of W H bytes one way to do this is to store pixel[x][y] atmemory location base x W y5 base 53 bytes: one red, one green, one blueof size W H 3each plane contains just W H valuesalpha plane (transparency), z-buffer (depth value), A-buffer (pointerto a data structure containing depth and coverage information),overlay planes (e.g. for displaying pop-up menus)0 1 2 3 44748The frame bufferDouble buffering most computers have a special piece ofmemory reserved for storage of the currentimage being displayedBUSframebufferoutputstage(e.g. DAC) sometimes referred to as Video RAM (VRAM) 2003 Neil A. Dodgson display the frame buffer normally consists of dualported Dynamic RAM (DRAM)if we allow the currently displayed image to be updatedthen we may see bits of the image being displayedhalfway through the updatedouble buffering solves this problem: we draw into oneframe buffer and display from the other BUSthis can be visually disturbing, especially if we want the illusionof smooth animationwhen drawing is complete we flip buffersBuffer ABuffer Boutputstage(e.g. DAC)display8

Computer Graphics & ImageProcessing4950Image displayLiquid crystal display a handful of technologies cover over 99% of alldisplay devices active displays cathode ray tubeliquid crystal displayplasma displaysspecial displays most common, declining userapidly increasing usestill rare, but increasing usee.g. LEDs for special applications either on or off: transparent or opaquegreyscale can be achieved in some liquid crystalsby varying the voltage colour is achieved with colour filters low power consumption but image quality not asgood as cathode ray tubes printers (passive displays) liquid crystal can twist the polarisation of lightcontrol is by the voltage that is applied across theliquid crystallaser printersink jet printersseveral other technologiesJMF Figs 90, 915152Cathode ray tubes How fast do CRTs need to be?focus an electron gun on a phosphor screen speed at which entire screen is updatedis called the “refresh rate” 50Hz (PAL TV, used in most of Europe) produces a bright spotscan the spot back and forth, up and down tocover the whole screen vary the intensity of the electron beam to changethe intensity of the spot repeat this fast enough and humans see acontinuous picture betterPAL 50Hz768x576NTSC 60Hz640x48080-90Hz displaying pictures sequentially at 20Hz gives illusionof continuous motionbut humans are sensitive to flicker atCRT slides in handoutfrequencies higher than this.many people can see a slight flicker60Hz (NTSC TV, used in USA and Japan)Flicker/resolutiontrade-off99% of viewers see no flicker, even on verybright displays100HZ (newer “flicker-free” PAL TV sets) practically no-one can see the image flickering5354Colour CRTs: shadow masksuse three electron guns & colour phosphors electrons have no colourPrinters many types of printer use shadow mask to direct electrons from each gunonto the appropriate phosphorthe electron beams’ spots are bigger than theshadow mask pitch can get spot size down to 7/4 of the pitchpitch can get down to 0.25mm with delta arrangementof phosphor dotswith a flat tension shadow mask can reduce this to0.15mmFvDFH Fig 4.14 ink jet dot matrix laser printer pushes pins against an ink ribbon and onto the paperuses a laser to lay down a pattern of charge on a drum;this picks up charged toner which is then pressed ontothe paper all make marks on paper 2003 Neil A. Dodgsonsprays ink onto paperessentially binary devices: mark/no mark9

Computer Graphics & ImageProcessing5556Printer resolutionWhat about greyscale? laser printer up to 1200dpi, generally 600dpi ink jet used to be lower resolution & quality than laserprinters but now have comparable resolution phototypesetter achieved by halftoning up to about 3000dpi bi-level devices: each pixel is either black orwhitedivide image into cells, in each cell draw a spot of theappropriate size for the intensity of that cellon a printer each cell is m m pixels, allowing m2 1 differentintensity levelse.g. 300dpi with 4 4 cells 75 cells per inch, 17 intensitylevelsphototypesetters can make 256 intensity levels in cells sosmall you can only just see theman alternative method is dithering dithering photocopies badly, halftoning photocopies wellwill discuss halftoning and dithering in Image Processing section of course5758Dye sublimation printers: true greyscale What about colour? generally use cyan, magenta, yellow, and blackinks (CMYK) inks aborb colourdye sublimation gives true greyscalepixel sized heaterdye sheetspecial paper direction of travel c.f. lights which emit colourCMY is the inverse of RGB why is black (K) necessary?dye sublimes off dye sheet and onto paper inproportion to the heat levelJMF Fig 9binks are not perfect aborbersmixing C M Y gives a muddy grey, not black lots of text is printed in black: trying to align C, Mand Y perfectly for black text would be a nightmare colour is achieved by using four different coloureddye sheets in sequence — the heat mixes them59How do you produce halftoned colour?Colour plate 5print four halftone screens, one in each colour carefully angle the screens to prevent interference (moiré)patterns Standard anglesMagenta 45 Cyan15 Yellow90 Black75 150 lpi 16 dots per cell 2400 dpi phototypesetter(16 16 dots per cell 256intensity levels) 2003 Neil A. DodgsonStandard rulings (in lines per inch)65 lpi85 lpinewsprint100 lpi120 lpiuncoated offset paper133 lpiuncoated offset paper150 lpimatt coated offset paper or art paperpublication: books, advertising leavlets200 lpivery smooth, expensive papervery high quality publication603D CG2D Computer Graphics lines 2D CGIPBackgroundhow do I draw a straight line? curves how do I specify curved lines? clipping what about lines that go off the edge of the screen? filled areas transformations scaling, rotation, translation, shearing applications10

Computer Graphics & ImageProcessing6162Drawing a straight line Which pixels do we use?ya straight line can be defined by: y mx cthere are two reasonably sensible alternatives:mthe slope ofthe linec1xa mathematical line is “length withoutbreadth” a computer graphics line is a set ofpixels which pixels do we need to turn on todraw a given line? every pixel through whichthe line passesthe “closest” pixel to theline in each column(can have either one or twopixels in each column)(always have just one pixelin every column)89 in general, use this63A line drawing algorithm - preparation 164A line drawing algorithm - preparation 2 pixel (x,y) has its centre at real co-ordinate (x,y) the line goes from (x0,y0) to (x1,y1) the line lies in the first octant (0 m 1) x0 x1(x1,y1)it thus stretches from (x-½, y-½) to (x ½, y ½)y 1½pixel (x,y)y 1y ½yy-½x-½x-1½x-1x ½xx 1½(x0,y0)x 165Bresenham’s line drawing algorithm 1InitialisationIterationassumesinteger endpointsd (y1 - y0) / (x1 - x0)x x0yi y0y y0DRAW(x,y)WHILE x x1 DOx x 1yi yi dy ROUND(yi)DRAW(x,y)END WHILEBresenham’s line drawing algorithm 2naïve algorithm involvesfloating point arithmetic &rounding inside the loop slow Speed up A: dyiy(x0,y0)xx 1 yi’dy & y’yixx’ separate integer and fractionalparts of yi (into y and yf)replace rounding by an IFz removes need to do rounding66d (y1 - y0) / (x1 - x0)x x0yf 0y y0DRAW(x,y)WHILE x x1 DOx x 1yf yf dIF ( yf ½ ) THENy y 1yf yf - 1END IFDRAW(x,y)END WHILEJ. E. Bresenham, “Algorithm for Computer Control of a Digital Plotter”, IBM Systems Journal, 4(1), 1965 2003 Neil A. Dodgson11

Computer Graphics & ImageProcessingBresenham’s line drawing algorithm 3 Speed up B: multiply all operations involving yfby 2(x1 - x0)z yf yf dy/dx yf yf 2dyz yf ½ yf dxz yf yf - 1 yf yf - 2dxremoves need to do floating pointarithmetic if end-points haveinteger co-ordinates67dy (y1 - y0)dx (x1 - x0)x x0yf 0y y0DRAW(x,y)WHILE x x1 DOx x 1yf yf 2dyIF ( yf dx ) THENy y 1yf yf - 2dxEND IFDRAW(x,y)END WHILEBresenham’s algorithm for floating pointend pointsd (y1 - y0) / (x1 - x0)x ROUND(x0)yi y0 d * (x-x0)y ROUND(yi)yf yi - yDRAW(x,y)WHILE x (x1 - ½) DOx x 1yf yf dIF ( yf ½ ) THENy y 1yf yf - 1END IFDRAW(x,y)END WHILEdy(x0,y0)xyi y yfx 1y’ yf’y & y’dxy yfx’6970Bresenham’s algorithm — more detailsA second line drawing algorithm we assumed that the line is in the first octant a line can be specified using an equation ofthe form: can do fifth octant by swapping end points68k ax by c therefore need four versions of the algorithm this divides the plane into three regions:3rd2ndabove the line k 0below the line k 0 on the line k 0 1stExercise: work out whatchanges need to be madeto the algorithm for it towork in each of the otherthree octants4th5th6th 7thk 0k 0k 08th7172Midpoint line drawing algorithm 1Midpoint line drawing algorithm 2 given that a particular pixel is on the line,the next pixel must be either immediately tothe right (E) or to the right and up one (NE) decision variable needs to make a decision atpoint (x 1, y ½) use a decision variable(based on k) to determinewhich way to go if go E then the new decision variable is at(x 2, y ½)d ' a ( x 2 ) b( y 12 ) cEvaluate thedecision variableat this pointif 0 then go NEThis is the current pixel 2003 Neil A. Dodgsond a( x 1) b( y 12 ) cif 0 then go E d a if go NE then the new decision variable is at(x 2, y 1½)d ' a ( x 2 ) b( y 1 12 ) c d a b12

Computer Graphics & ImageProcessing7374Midpoint line drawing algorithm 3InitialisationWHILE x (x1 - ½) DOx x 1IF d 0 THENd d aELSEd d a by y 1END IFDRAW(x,y)END WHILEyxx 1 this version only works for lines in the firstoctantIterationa (y1 - y0)b -(x1 - x0)c x1 y0 - x0 y1x ROUND(x0)y ROUND(y0-(x- x0)(a / b))d a * (x 1) b * (y ½) cDRAW(x,y)(x0,y0)Midpoint - commentsFirst decisionpointE casejust increment x extend to other octants as for Bresenham Sproull has proven that Bresenham andMidpoint give identical results Midpoint algorithm can be generalised todraw arbitary circles & ellipsesNE caseincrement x & y If end-points have integer co-ordinates thenall operations can be in integer arithmeticBresenham can only be generalised to drawcircles with integer radii7576CurvesMidpoint circle algorithm 1222 equation of a circle is x y r circles & ellipses Bezier cubics Pierre Bézier, worked in CAD for Renaultwidely used in Graphic Design222 decision variable can be d x y r Overhauser cubics Overhauser, worked in CAD for Ford d 0 on the circle, d 0 outside, d 0 inside divide circle into eight octants NURBS centred at the originNon-Uniform Rational B-Splinesmore powerful than Bezier & now more widely usedconsider these in Part II on the next slide we consider onlythe second octant, the others aresimilar7778Midpoint circle algorithm 2 decision variable needs to make adecision at point (x 1, y-½)d ( x 1) 2 ( y 12 ) 2 r 2 if go E then the new decision variable is atd ' ( x 2) 2 ( y 12 )2 r 2(x 2, y-½)Taking circles further the algorithm can be easily extended tocircles not centred at the origin a similar method can be derived for ovals d 2x 3 if go SE then the new decision variable is222at (x 2, y-1½) d ' ( x 2 ) ( y 1 12 ) r d 2x 2 y 5 2003 Neil A. Dodgsonbut: cannot naively use octants use points of 45 slope to divideoval into eight sectionsand: ovals must be axis-aligned there is a more complex algorithm whichcan be used for non-axis aligned ovalsExercise: complete the circlealgorithm for the second octant13

Computer Graphics & ImageProcessing7980Are circles & ellipses e

Computer Graphics & Image Processing 2003 Neil A. Dodgson 2 7 Course books Computer Graphics: Principles & Practice Foley, van Dam, Feiner & Hughes,Addison-Wesley, 1990 zOlder version: Fundamentals of Interactive Computer Graphics Foley & van Dam, Addison-Wesley, 1982 Computer Graphics &

Related Documents:

L’ARÉ est également le point d’entrée en as de demande simultanée onsommation et prodution. Les coordonnées des ARÉ sont présentées dans le tableau ci-dessous : DR Clients Téléphone Adresse mail Île de France Est particuliers 09 69 32 18 33 are-essonne@enedis.fr professionnels 09 69 32 18 34 Île de France Ouest

Graphics Courses Key course Image processing and computer graphics (modeling, rendering, simulation) Specialization courses Advanced computer graphics (global illumination) Simulation in computer graphics (deformable and rigid solids, fluids) Master project, lab course, Master thesis Simulation track, rendering track

Introduction to Computer Graphics COMPSCI 464 Image credits: Pixar, Dreamworks, Ravi Ramamoorthi, . –Game design and development It is about –Learning the fundamentals of computer graphics –Implementing algorithms that are at the core of computer graphics . Fundamentals of Computer Graphics

Graphics API and Graphics Pipeline Efficient Rendering and Data transfer Event Driven Programming Graphics Hardware: Goal Very fast frame rate on scenes with lots of interesting visual complexity Pioneered by Silicon Graphics, picked up by graphics chips companies (Nvidia, 3dfx, S3, ATI,.). OpenGL library was designed for this .

Interactive graphics is useful in a. Training pilots b. Computer aided design c. Process control d. All of these 57. The origin of computer graphics was developed in a. 1950 b. 1960 c. 1970 d. 1990 58. The term business graphics came into use in late a. 1950 b. 1960 c. 1970 d. 1990 59. Computer graphics is used in many DTP software as a .

D. Salomon: Computer Graphics Geometric Modeling, Springer, 1999 A. Watt: 3D Computer Graphics. Addison-Wesley Publishing Company, Inc., 2000 Journals Computer Graphics Forum IEEE CG & Applications ACM Transactions on Graphics ACM Transaction

COMPUTER GRAPHICS & VISUALIZATION - 15CS62 Module -1 1. a. Enlist the applications of computer graphics and explain. (6 marks). i. Graphs and charts Display of simple data graphs was the early application of computer graphics plotted on a character printer. Data plotting one of the most common graphics applications

Annual Book of ASTM Standards now available at the desktop! ASTM updates nearly 3,000 standards annually! Annual Book of Volume 01.05: Steel--Bars, Forgings, Bearing, Chain, Tool ASTM Standards now available at the desktop! Section 1: Iron and Steel Products Volume 01.01: Steel--Piping, Tubing, Fittings Volume 01.02: Ferrous Castings; Ferroalloys Volume 01.03: Steel--Plate, Sheet, Strip, Wire .