Computer Graphics

Projection is the transformation of a 3D object onto a 2D view plane. Each point is mapped along projectors (lines of projection) to its intersection with the plane. The two main kinds are parallel projection (projectors parallel) and perspective projection (projectors meet at a centre of projection).

Perspective projection

All projectors converge at the centre of projection (eye point). Objects farther away look smaller (perspective foreshortening), which gives a realistic view, but parallel lines (not parallel to the view plane) converge and sizes/angles are not preserved.

Take the centre of projection at the origin and the view plane at $z = d$. A point $P(x,y,z)$ projects to $P'(x_p, y_p, d)$. By similar triangles:

$\frac{x_p}{d} = \frac{x}{z},\qquad \frac{y_p}{d} = \frac{y}{z}$

$x_p = \frac{x\,d}{z} = \frac{x}{z/d},\qquad y_p = \frac{y\,d}{z} = \frac{y}{z/d},\qquad z_p = d$

Matrix form (homogeneous coordinates):

$\begin{bmatrix}x_h\\y_h\\z_h\\h\end{bmatrix} = \begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&1/d&0\end{bmatrix}\begin{bmatrix}x\\y\\z\\1\end{bmatrix} = \begin{bmatrix}x\\y\\z\\z/d\end{bmatrix}$

Dividing by $h = z/d$ gives $x_p = x/h = xd/z$, $y_p = y/h = yd/z$, $z_p = z/h = d$.

RGB colour model

RGB uses Red, Green and Blue as primary colours of light. Colours are produced by mixing these lights in different intensities (0-255 each, giving about 16.7 million colours). It is used in monitors, TVs, cameras and scanners. R + G = yellow, G + B = cyan, R + B = magenta, R + G + B = white, and no light = black. It is an additive model.

CMYK colour model

CMYK uses Cyan, Magenta, Yellow and Key (Black) inks. It is the model for printing. $C=1-R,\ M=1-G,\ Y=1-B$. Black ink is added because overlaying C, M, Y gives only a dull dark brown and black text would otherwise need three inks.

Why CMYK is subtractive

Printing starts with white paper, which reflects all wavelengths. Each ink acts as a filter that absorbs (subtracts) some part of the white light: cyan absorbs red, magenta absorbs green and yellow absorbs blue. Adding more ink subtracts more light, and all inks together absorb almost all light, giving black; with no ink the paper stays white. Since colours are obtained by subtracting wavelengths from white light, the model is called subtractive.

RGB colour model

RGB uses Red, Green and Blue as primary colours. Every colour is made by mixing these three lights in different intensities; each is typically 8 bits (0-255), giving $2^{24}\approx16.7$ million colours. It is used by light-emitting devices such as monitors, TVs, cameras and scanners.

• R + G = Yellow, G + B = Cyan, R + B = Magenta
• R + G + B = White, none = Black

CMYK colour model

CMYK uses Cyan, Magenta, Yellow and Black (K). It is used in printing. Cyan, magenta and yellow are the complements of R, G and B ($C=1-R$, $M=1-G$, $Y=1-B$). Black ink is added because mixing C, M and Y gives a muddy dark brown rather than true black, and black ink is cheaper and sharper for text.

Why RGB is additive

Colours are produced by adding light to a black (dark) screen. Starting with no light (black), adding red, green and blue light together gives white. More light means a brighter colour.

Why CMYK is subtractive

Printing starts with white paper that reflects all colours. Each ink absorbs (subtracts) part of the white light: cyan absorbs red, magenta absorbs green, yellow absorbs blue. Adding more ink removes more light, and all inks together absorb nearly everything, giving black. Hence it is a subtractive model.

Parallel projection

Projectors are parallel to each other, so the centre of projection is at infinity. Sizes and parallel lines are preserved but there is no depth effect. Types: orthographic (projectors perpendicular to the plane) and oblique (cavalier, cabinet). Used in engineering drawing.

Perspective projection

Projectors converge at a centre of projection (the eye). Objects farther away look smaller (perspective foreshortening) and parallel lines meet at vanishing points, giving realistic views, but true sizes are not preserved.

Derivation of perspective projection

Take the centre of projection at the origin and the view plane at $z=d$. A point $P(x,y,z)$ projects to $P'(x_p,y_p,d)$. By similar triangles:

$\frac{x_p}{d}=\frac{x}{z}\Rightarrow x_p=\frac{x\,d}{z}=\frac{x}{z/d},\qquad \frac{y_p}{d}=\frac{y}{z}\Rightarrow y_p=\frac{y\,d}{z}=\frac{y}{z/d},\qquad z_p=d$

Matrix representation

Using homogeneous coordinates:

$\begin{bmatrix}x_h\\y_h\\z_h\\w\end{bmatrix}=\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&1/d&0\end{bmatrix}\begin{bmatrix}x\\y\\z\\1\end{bmatrix}=\begin{bmatrix}x\\y\\z\\z/d\end{bmatrix}$

Dividing by $w=z/d$: $x_p=x_h/w=xd/z$, $y_p=y_h/w=yd/z$, $z_p=z_h/w=d$.

Need for clipping

Clipping removes the part of a picture lying outside a clipping window (or volume). It is needed because:

• only the portion inside the window is to be displayed, so objects partly outside must be cut;
• it avoids wasted processing/drawing of invisible parts and saves time and memory;
• it prevents writing outside the frame buffer/viewport (which would corrupt other regions);
• it is used in viewing transformation, windowing, 3D hidden-part removal and multi-window displays.

Cohen-Sutherland line clipping

The plane is divided into 9 regions by the window edges. Each end point gets a 4-bit region code (outcode) $b_4b_3b_2b_1$ = Top, Bottom, Right, Left:

• bit 1 (Left) = 1 if $x<x_{min}$
• bit 2 (Right) = 1 if $x>x_{max}$
• bit 3 (Bottom) = 1 if $y<y_{min}$
• bit 4 (Top) = 1 if $y>y_{max}$

The window itself has code 0000.

Algorithm:

1. Compute codes of both end points.
2. If both codes are 0000 (OR = 0): line is completely inside, accept (trivial accept).
3. If the logical AND of codes is not 0000: line is completely outside one edge, reject (trivial reject).
4. Otherwise pick an end point outside the window, find the intersection with a window edge it violates, replace the end point with the intersection, recompute its code, and go back to step 2.

Intersection formulas, with $m=(y_2-y_1)/(x_2-x_1)$:

• vertical edge $x=X$: $y=y_1+m(X-x_1)$
• horizontal edge $y=Y$: $x=x_1+(Y-y_1)/m$

Example

Window: $x_{min}=2,\ x_{max}=8,\ y_{min}=2,\ y_{max}=6$. Line $P_1(1,3)$ to $P_2(9,5)$.

• $P_1$: $x<2$ so code $0001$. $P_2$: $x>8$ so code $0010$.
• OR is $0011\ne0$, AND is $0000$, so clipping is required.
• $m=(5-3)/(9-1)=0.25$.
• Clip $P_1$ with $x=2$: $y=3+0.25(2-1)=3.25$ gives $(2,3.25)$, code 0000.
• Clip $P_2$ with $x=8$: $y=3+0.25(8-1)=4.75$ gives $(8,4.75)$, code 0000.

Both codes are now 0000, so the visible part is the line from $(2,3.25)$ to $(8,4.75)$.

Graphics and image processing

Computer graphics is the creation and manipulation of pictures from descriptions or models (points, lines, polygons, equations) using a computer. Input is a description of objects, output is an image. Examples: games, CAD, animation, GUIs.

Image processing is the analysis and modification of existing images (photos, scans, satellite images) to improve them or extract information. Input is an image, output is an improved image or data. Operations include enhancement, noise removal, restoration, compression, segmentation and recognition. Examples: medical imaging, remote sensing, face recognition, OCR.

The two fields overlap: e.g. texture mapping and augmented reality use both.

Why clipping is needed: only the part of a picture lying inside the viewing window (clip window) is to be displayed. Clipping removes the portions outside the window, so that processing and display time is not wasted on invisible parts, and the drawing does not overflow into other screen areas or memory.

Cohen-Sutherland line clipping

The plane is divided into 9 regions by the window edges. Every endpoint gets a 4-bit region code (outcode) $b_4 b_3 b_2 b_1$:

• bit 1 = 1 if $x < x_{min}$ (left)
• bit 2 = 1 if $x > x_{max}$ (right)
• bit 3 = 1 if $y < y_{min}$ (below)
• bit 4 = 1 if $y > y_{max}$ (above)

The window itself has code 0000.

Steps

1. Find the codes of both endpoints $P_1, P_2$.
2. Trivially accept if both codes are 0000 (OR of codes = 0000): draw the whole line.
3. Trivially reject if the logical AND of the codes is non-zero (both endpoints on the outer side of the same edge): discard the line.
4. Otherwise (partially inside): choose an endpoint outside the window (non-zero code), and find the intersection with a window edge for the first set bit, using the slope $m = (y_2-y_1)/(x_2-x_1)$:
   • left/right edge: $y = y_1 + m(x_{edge} - x_1)$
   • bottom/top edge: $x = x_1 + (y_{edge} - y_1)/m$
5. Replace the outside endpoint by the intersection point, recompute its code, and repeat from step 2 until the line is accepted or rejected.

Example: a line with codes 0001 and 1000 has AND = 0000, so it cannot be rejected immediately; it is clipped against the left edge, then the top edge, until the remaining segment is accepted or rejected.

Advantage: quickly accepts or rejects most lines without computing intersections. Disadvantage: may need several intersection computations for lines that are outside but not trivially rejected.

Projection

Projection is the transformation of 3D object coordinates onto a 2D view plane. In parallel projection the projectors are parallel; in oblique parallel projection they are parallel to each other but not perpendicular to the view plane.

Derivation

Let the view plane be $z=0$. A point $P(x,y,z)$ projects to $P_p(x_p,y_p)$ on the plane. The projector makes angle $\alpha$ with the view plane; the projection of the projector onto the plane makes angle $\phi$ with the $x$-axis. Let $(x,y)$ be the point $(x,y,0)$ lying directly below $P$ on the plane, and $L$ the length of the line from $(x,y)$ to $(x_p,y_p)$.

Then $\tan\alpha = z/L$, so $L=z/\tan\alpha = zL_1$ where $L_1=\cot\alpha$. From the geometry:

$x_p = x + L\cos\phi = x+ zL_1\cos\phi$

$y_p = y + L\sin\phi = y+ zL_1\sin\phi$

$z_p=0$

Matrix form

$\begin{bmatrix}x_p\\y_p\\z_p\\1\end{bmatrix}=\begin{bmatrix}1&0&L_1\cos\phi&0\\0&1&L_1\sin\phi&0\\0&0&0&0\\0&0&0&1\end{bmatrix}\begin{bmatrix}x\\y\\z\\1\end{bmatrix}$

Special cases:

• Cavalier projection: $\alpha=45^\circ$, so $L_1=1$ and lengths perpendicular to the plane are preserved.
• Cabinet projection: $\tan\alpha=2$ ($\alpha\approx63.4^\circ$), so $L_1=1/2$ and perpendicular lengths are halved.
• For orthographic projection $L_1=0$ and the matrix reduces to dropping $z$.

Computer graphics vs image processing

Applications of computer graphics

• User interfaces: windows, icons, menus (GUI).
• Computer-aided design (CAD): design of buildings, machines, circuits, cars.
• Presentation graphics: charts, graphs, bar and pie diagrams for reports.
• Computer art: painting and drawing packages, commercial art, advertising.
• Entertainment: movies, animation, video games, special effects.
• Education and training: simulators for pilots, drivers, surgeons.
• Visualization: scientific and business data (weather maps, molecular structures).
• Medical imaging: CT, MRI visualization.
• Cartography and GIS: maps and terrain.
• Virtual reality and simulation.

Beam penetration technique (random-scan colour CRT): the screen is coated with two phosphor layers, red (outer) and green (inner). The colour depends on how deeply the electron beam penetrates, which is controlled by the beam's accelerating voltage.

Merits

• Simple and inexpensive compared with shadow-mask.
• Good for random-scan (line drawing) displays.
• Gives high resolution, because there is no mask and only one gun.

Demerits

• Only four colours: red, green, orange and yellow.
• Poor colour quality and picture quality compared with the shadow-mask method.
• Slow and hard to control; voltage changes are needed for colour change.

Colour generation in a CRT (shadow-mask method)

• The screen is coated with a large number of triads of phosphor dots: red, green and blue.
• There are three electron guns (R, G, B), one for each colour, and a shadow mask, a metal plate with small holes behind the screen, positioned so that each gun's beam can reach only its own colour dots.
• The beams are converged on a hole of the mask, and each excites only its own phosphor dot. The intensity of each gun is varied.
• Because the dots are very close, the eye blends them into one colour. Different intensities of R, G, B give a wide range of colours (e.g. equal R+G+B gives white, R+G gives yellow). With 8 bits per gun, about 16 million colours are possible.
• A convergence system keeps the three beams aligned.

R gun \
G gun --> [shadow mask] --> R G B triads on screen
B gun /

Given: $(x_1,y_1) = (20,10)$, $(x_2,y_2) = (26,15)$.

$\Delta x = 6,\ \Delta y = 5$. Slope $m = 5/6 < 1$, so $x$ is incremented by 1 at every step.

Initial decision parameter:

$p_0 = 2\Delta y - \Delta x = 10 - 6 = 4$

Rules:

• If $p_k < 0$: next point $(x_k+1,\ y_k)$ and $p_{k+1} = p_k + 2\Delta y = p_k + 10$.
• If $p_k \ge 0$: next point $(x_k+1,\ y_k+1)$ and $p_{k+1} = p_k + 2\Delta y - 2\Delta x = p_k - 2$.

Pixels plotted: (20,10), (21,11), (22,12), (23,13), (24,13), (25,14), (26,15).

Scan conversion is the process of converting a geometric primitive (point, line, circle, polygon) described by coordinates and equations into the set of pixels on the raster display that best represents it. It is also called rasterization.

Midpoint circle algorithm

Circle centred at origin, radius $r$: $f(x,y) = x^2 + y^2 - r^2$, which is

• $< 0$ for points inside the circle,
• $= 0$ for points on it,
• $> 0$ for points outside it.

By eight-way symmetry, only the octant from $(0,r)$ to $x=y$ is computed (clockwise), where $x$ increases by 1 each step and $y$ either stays or decreases by 1.

Given the current pixel $(x_k, y_k)$, the next candidates are $(x_k+1, y_k)$ and $(x_k+1, y_k-1)$. Their midpoint is $(x_k+1,\ y_k-\tfrac12)$. Define the decision parameter

$p_k = f\left(x_k+1,\ y_k-\tfrac12\right) = (x_k+1)^2 + \left(y_k-\tfrac12\right)^2 - r^2$

• If $p_k < 0$, the midpoint is inside the circle, so the pixel $(x_k+1, y_k)$ is closer: choose it.
• If $p_k \ge 0$, the midpoint is outside, so choose $(x_k+1, y_k-1)$.

Incremental form. At step $k+1$:

$p_{k+1} = (x_{k+1}+1)^2 + \left(y_{k+1}-\tfrac12\right)^2 - r^2$

Subtracting:

$p_{k+1} - p_k = 2(x_k+1) + 1 + (y_{k+1}^2 - y_k^2) - (y_{k+1} - y_k)$

• If $p_k<0$, $y_{k+1}=y_k$: $p_{k+1} = p_k + 2x_{k+1} + 1$.
• If $p_k\ge0$, $y_{k+1}=y_k-1$: $y_{k+1}^2-y_k^2 - (y_{k+1}-y_k) = -2y_k+1+1 = -2y_{k+1}$ (using $y_k = y_{k+1}+1$), so $p_{k+1} = p_k + 2x_{k+1} + 1 - 2y_{k+1}$.

Initial value at $(0, r)$:

$p_0 = f\left(1, r-\tfrac12\right) = 1 + r^2 - r + \tfrac14 - r^2 = \tfrac54 - r \approx 1 - r$

(rounding is allowed since $r$ is an integer).

Algorithm

1. Input $r$ and centre $(x_c, y_c)$; set $x=0,\ y=r,\ p=1-r$.
2. Plot the eight symmetric points $(x_c\pm x, y_c\pm y)$, $(x_c\pm y, y_c\pm x)$.
3. While $x < y$: $x = x+1$; if $p<0$, $p = p + 2x + 1$; else $y = y-1$, $p = p + 2x + 1 - 2y$; plot the symmetric points.

Rectangle: A(0,0), B(0,4), C(8,4), D(8,0); width 8, height 4, centre $(4,2)$.

(a) Reduce to half size keeping the centre fixed

Scale by $s = 0.5$ about the point $(4,2)$: translate the centre to the origin, scale, translate back.

$M = T(4,2)\cdot S(0.5,0.5)\cdot T(-4,-2)$

$M = \begin{bmatrix}1&0&4\\0&1&2\\0&0&1\end{bmatrix}\begin{bmatrix}0.5&0&0\\0&0.5&0\\0&0&1\end{bmatrix}\begin{bmatrix}1&0&-4\\0&1&-2\\0&0&1\end{bmatrix} = \begin{bmatrix}0.5&0&2\\0&0.5&1\\0&0&1\end{bmatrix}$

So $x' = 0.5x + 2,\ y' = 0.5y + 1$.

New coordinates: $A'(2,1),\ B'(2,3),\ C'(6,3),\ D'(6,1)$ (a 4 by 2 rectangle, centre still $(4,2)$).

(b) Converting the rectangle to a square

The rectangle is 8 wide and 4 high, so the scale factors must differ: choose $s_x = 0.5$, $s_y = 1$ (width becomes 4). Scaling about the centre $(4,2)$:

$M_{sq} = T(4,2)\,S(0.5,1)\,T(-4,-2) = \begin{bmatrix}0.5&0&2\\0&1&0\\0&0&1\end{bmatrix}$

Generally $x' = s_x x + (1-s_x)\,4$, $y' = s_y y + (1-s_y)\,2$.

New square: $A(0,0)\to(2,0)$, $B(0,4)\to(2,4)$, $C(8,4)\to(6,4)$, $D(8,0)\to(6,0)$. It is a $4\times4$ square with centre $(4,2)$.

(Equivalently, applying $s_x=1,\ s_y=2$ about $(4,2)$ to the half-size rectangle of part (a) gives the same square.)

(i) Two successive rotations are additive

Using 2D homogeneous matrices:

$R(\theta_1) = \begin{bmatrix}\cos\theta_1 & -\sin\theta_1 & 0\\ \sin\theta_1 & \cos\theta_1 & 0\\0&0&1\end{bmatrix},\quad R(\theta_2) = \begin{bmatrix}\cos\theta_2 & -\sin\theta_2 & 0\\ \sin\theta_2 & \cos\theta_2 & 0\\0&0&1\end{bmatrix}$

$R(\theta_2)R(\theta_1) = \begin{bmatrix}\cos\theta_2\cos\theta_1 - \sin\theta_2\sin\theta_1 & -(\cos\theta_2\sin\theta_1 + \sin\theta_2\cos\theta_1) & 0\\ \sin\theta_2\cos\theta_1 + \cos\theta_2\sin\theta_1 & \cos\theta_2\cos\theta_1 - \sin\theta_2\sin\theta_1 & 0\\0&0&1\end{bmatrix}$

By the sum formulas for sine and cosine:

$R(\theta_2)R(\theta_1) = \begin{bmatrix}\cos(\theta_1+\theta_2) & -\sin(\theta_1+\theta_2) & 0\\ \sin(\theta_1+\theta_2) & \cos(\theta_1+\theta_2) & 0\\0&0&1\end{bmatrix} = R(\theta_1+\theta_2)$

Hence two successive rotations about the origin equal a single rotation through the sum of the angles. Since the sum is commutative, the order does not matter.

(ii) Two successive translations are additive

$T(t_{x1},t_{y1}) = \begin{bmatrix}1&0&t_{x1}\\0&1&t_{y1}\\0&0&1\end{bmatrix},\quad T(t_{x2},t_{y2}) = \begin{bmatrix}1&0&t_{x2}\\0&1&t_{y2}\\0&0&1\end{bmatrix}$

$T(t_{x2},t_{y2})\,T(t_{x1},t_{y1}) = \begin{bmatrix}1&0&t_{x1}+t_{x2}\\0&1&t_{y1}+t_{y2}\\0&0&1\end{bmatrix} = T(t_{x1}+t_{x2},\ t_{y1}+t_{y2})$

So two successive translations equal one translation whose distances are the sums of the individual distances.

Geometric (polygon) tables are used to store the data of a 3D object represented by polygon surfaces (a polygon mesh). They have two groups of data: geometric data (vertices, edges, surfaces) and attribute data (colour, transparency, texture, reflectivity). Three tables are used:

1. Vertex table: coordinates $(x,y,z)$ of each vertex.
2. Edge table: each edge as a pair of vertices.
3. Surface (polygon) table: each polygon as a list of its edges.

Example: a triangular pyramid-like shape with vertices $V_1(0,0,0), V_2(1,0,0), V_3(0,1,0), V_4(0,0,1)$.

Storing edges separately avoids repeating shared vertices, and lets each edge be drawn once.

Conditions for an error-free table

• Every vertex is listed at least once, and every vertex is part of at least one edge.
• Every edge is part of at least one polygon, and every polygon is closed.
• Every edge appears in at least two polygons for a closed solid (and the edge's two ends are different vertices).
• Each polygon has at least one shared edge with another polygon.
• No vertex coordinate is duplicated or missing, and a surface's edges form a closed loop.

Why hidden-surface removal is necessary: when a 3D scene is projected onto the screen, surfaces nearer the viewer may block those behind them. If all surfaces were drawn, far surfaces would wrongly show through near ones and the picture would be confusing or unrealistic. Removing the hidden surfaces (or lines) gives the correct visible image, and also saves processing time.

Z-buffer (depth-buffer) method

An image-space method. Two arrays of the screen size are maintained:

• Depth buffer $Z(x,y)$: stores the depth (z) of the nearest surface found so far at each pixel.
• Refresh (frame) buffer $F(x,y)$: stores the colour/intensity of that surface.

Algorithm

1. Initialise $Z(x,y) = z_{max}$ (far limit, depth of the back clipping plane) and $F(x,y) =$ background colour for all pixels.
2. For each polygon, and for each pixel $(x,y)$ its projection covers, calculate the depth $z$.
3. If $z < Z(x,y)$ (nearer than the stored depth): set $Z(x,y) = z$ and $F(x,y) =$ colour of the polygon at $(x,y)$. Otherwise leave it unchanged.
4. After all polygons are processed, $F$ contains the visible surfaces.

Depth calculation: from the plane equation $Ax+By+Cz+D=0$, $z = (-Ax-By-D)/C$. Moving along a scan line to $x+1$: $z' = z - A/C$, and moving to the next scan line: $z' = z + B/C$, so depth is computed incrementally.

Advantages: simple, handles any polygon order, no sorting needed, easy to implement in hardware. Disadvantages: needs extra memory for the depth buffer; handles transparency poorly; each pixel may be computed several times (overdraw); precision/aliasing problems.

Rendering is the process of generating the final 2D image from a 3D scene model by applying hidden-surface removal, illumination (lighting), shading, texture and colour, so that the objects appear realistic on screen.

Gouraud shading (intensity interpolation)

1. Find the average unit normal at each polygon vertex (average of the normals of polygons sharing it).
2. Apply the illumination model at each vertex to get its intensity.
3. Linearly interpolate the vertex intensities along edges and then across scan lines.

Phong shading (normal-vector interpolation)

1. Find the vertex normals as above.
2. Linearly interpolate the normal vectors along edges and across scan lines.
3. Apply the illumination model at every pixel using its interpolated normal.

Why Phong is better

• Specular highlights are rendered accurately; Gouraud interpolates only intensities, so a highlight inside a polygon (not at a vertex) is missed or smeared, and the shape of the highlight is wrong.
• It removes the Mach-band effect much better, giving a smoother and more realistic surface.
• Intensity at each pixel is calculated from the proper normal, so the result is more accurate for curved surfaces.

Cost: Phong needs far more computation (illumination for every pixel), while Gouraud is faster because it uses only the vertex calculation and linear interpolation. So Phong gives higher quality at higher cost.

Multimedia authoring is the process of combining multimedia elements (text, graphics, images, audio, video, animation) into a single interactive application or presentation, adding structure, navigation and user interaction, and packaging it for delivery. An authoring tool is the software used for this, usually without needing deep programming.

Common authoring tools

• Adobe Animate (Flash)
• Adobe Director
• Macromedia/Adobe Authorware
• Adobe Captivate
• Microsoft PowerPoint
• ToolBook
• HyperCard / HyperStudio
• Articulate Storyline
• Unity (for interactive content)

Two explained

(1) Adobe Director: a timeline-and-score based tool. A stage shows the content, a cast stores the media, and a score arranges them over time in frames and channels. It uses the Lingo scripting language for interactivity and is used to build CD-ROMs, games and kiosk applications with sophisticated animation and interaction.

(2) Authorware (flowchart-based): the author drags icons (display, interaction, calculation, navigation, decision) onto a flowline; the sequence of icons defines the program flow. It is well suited to e-learning and training applications, with strong tracking of user responses and little coding.

Other paradigms: card/page based (ToolBook, HyperCard) where content is arranged as pages linked by buttons, and presentation based (PowerPoint) with slides.

MIDI (Musical Instrument Digital Interface) is a standard protocol and hardware interface that lets electronic musical instruments, computers and other devices communicate. It transmits instructions about music (which note, how long, how loud, which instrument), not the sound itself, so files are very small.

MIDI hardware

• Controllers/keyboards/synthesizers: produce MIDI messages when played and generate sound.
• Sequencers: record, edit and play back MIDI data.
• Sound modules (sound generators): receive messages and produce the sound.
• Interface and cables: 5-pin DIN connectors with ports MIDI IN, MIDI OUT and MIDI THRU, running at 31.25 kbaud, serial.
• Computer interface (sound card or USB MIDI adapter).

MIDI software

• Sequencing software (e.g. Cubase) records and edits tracks.
• Notation software prints sheet music.
• Patch editors/librarians and soft synthesizers that produce sound on the computer.
• Standard MIDI files (.mid) and General MIDI to ensure instrument numbers are the same on all devices.

Communication MIDI messages are sent as bytes: a status byte (message type and channel number, 16 channels) followed by data bytes. Examples: Note On (key, velocity), Note Off, Program Change, Pitch Bend, Control Change. The OUT port of a controller is connected to the IN port of the sound module; THRU passes the incoming data to a third device (daisy chain). Each device listens on its own channel.

Keyboard (OUT) ---> (IN) Sound module (THRU) ---> (IN) Another module

How video works

Video is a sequence of still images (frames) displayed fast enough, 24-30 frames per second (fps), that the eye (persistence of vision) perceives continuous motion. In analog video (NTSC 30 fps, PAL 25 fps) a CRT's electron beam scans each frame line by line; in many systems with interlacing, odd and even lines are drawn in two fields to reduce flicker. Digital video is obtained by sampling and quantizing each frame as pixels (e.g. RGB or YUV colour space), forming a very large amount of data: for example, $640\times480$ pixels at 24 bits and 30 fps is about $640\times480\times3\times30 \approx 27.6$ MB/s. So compression is essential.

Video compression techniques

Lossless vs lossy: lossless gives exact reconstruction (low ratio); lossy discards information that is not noticeable (high ratio).

1. Spatial (intra-frame) compression: compresses each frame independently, as an image, removing redundancy within the frame, e.g. JPEG/DCT-based coding, quantization and entropy coding (Motion JPEG).
2. Temporal (inter-frame) compression: consecutive frames are very similar, so only the differences are stored. Uses motion estimation and compensation: a frame is divided into macroblocks, a motion vector is found to a similar block in a reference frame, and only the vector and the small residual are stored.
3. MPEG frame types:
   • I-frame (intra): coded independently, the reference points.
   • P-frame (predicted): predicted from the earlier I or P frame.
   • B-frame (bidirectional): predicted from both past and future frames; gives the highest compression.
4. Other techniques: run-length encoding, Huffman/arithmetic (entropy) coding, chroma sub-sampling (4:2:0), and standards such as H.261, MPEG-1/2/4, H.264/AVC and H.265/HEVC.

Illumination model (lighting model) is a formula to calculate the intensity of light at a point on a surface, based on the light sources, the surface properties and the viewer's position. It is used by shading methods to give realism.

Components of the basic (Phong) model

• Ambient light: uniform background light from the surroundings: $I_a = k_a I_{amb}$.
• Diffuse reflection: light scattered equally in all directions from a rough surface, following Lambert's cosine law: $I_d = k_d I_l \cos\theta = k_d I_l (\mathbf{N}\cdot\mathbf{L})$.
• Specular reflection: bright highlight on shiny surfaces, seen near the mirror direction: $I_s = k_s I_l (\mathbf{R}\cdot\mathbf{V})^{n}$, where $n$ is the specular exponent (larger for shinier surfaces).

Total intensity:

$I = k_a I_a + k_d I_l(\mathbf{N}\cdot\mathbf{L}) + k_s I_l(\mathbf{R}\cdot\mathbf{V})^n$

with intensity falling with distance by an attenuation factor for point sources.

Kinds of light source: point source, directional (distant) source, spotlight, and area/ambient light.

Other models include Lambertian, Blinn-Phong (using the halfway vector $\mathbf{H}$) and global models like ray tracing and radiosity.

Animation is the process of creating the illusion of motion by displaying a sequence of still images (frames) quickly one after another.

Types of animation

• Traditional (cel) animation: each frame is hand-drawn on transparent cels, layered over a background and photographed. Very labour intensive.
• Stop-motion animation: physical objects (clay, puppets, models) are moved slightly and photographed frame by frame.
• 2D computer animation: drawings are created or interpolated on a computer, using key frames and in-betweening (tweening), as in Flash.
• 3D computer animation: objects are modelled in 3D, rigged with skeletons, and moved with keyframes, motion capture or physics, then rendered. Used in modern films and games.
• Motion graphics: animated text and graphic design elements (titles, logos).
• Path / morphing animation: an object moves along a path, or one shape smoothly changes into another (morphing).
• Procedural/physics-based animation: motion produced by rules or simulation (particles, cloth, fluids).

Methods: key-frame animation, motion capture, and procedural animation.

Image formats are the file formats used to store digital images. They differ in compression, colour depth and features.

Formats are broadly raster (bitmap), made of pixels, and vector, made of mathematical shapes. Choice depends on quality, file size, transparency and the intended use.

Computer graphics is the field of computer science concerned with creating, storing, manipulating and displaying pictures and images (2D and 3D) by computer, using hardware and software.

Impact of its evolution on gaming

Early stage: games such as Pong used simple monochrome shapes and text (1970s). 8-bit and 16-bit consoles introduced sprites and tile-based 2D with limited colours.

Realism

• 3D polygons and texture mapping (1990s) replaced flat sprites, giving real 3D worlds.
• Hardware GPUs allow millions of polygons per second, with high resolution and frame rate.
• Shading and lighting: Gouraud/Phong shading, per-pixel shaders, shadows, bump/normal mapping and HDR lighting make surfaces look real.
• Real-time ray tracing and global illumination give physically accurate reflections and light.
• Realistic characters through motion capture, facial animation and physics simulation (water, cloth, destruction).

Player immersion

• Large open worlds with seamless detail.
• Virtual reality and augmented reality headsets place the player inside the game.
• Realistic motion and sound, high frame rates, and responsive controls increase the feeling of presence.
• Better visual storytelling makes emotional connection with characters stronger.
• Cinematic quality of cutscenes and in-game graphics are now close.

Overall: progress in graphics hardware and algorithms moved games from simple abstract shapes to near-photorealistic, immersive interactive worlds, and made the gaming industry a major driver of graphics research and GPU development.

(a) Frame buffer

A frame buffer (refresh buffer) is a dedicated block of memory that stores the intensity/colour value of every pixel of the screen. The display controller reads it repeatedly (about 60 times per second) and sends the values to the monitor, so whatever is written into the frame buffer appears on the screen. Its size is $\text{width} \times \text{height} \times \text{bits per pixel}$; for example a $1024 \times 768$ screen with 24 bits per pixel needs $1024 \times 768 \times 3 = 2.25$ MB.

(b) Raster scan vs random scan

DDA (Digital Differential Analyzer) algorithm

DDA is a scan-conversion method that uses the differential equation of a line. For a line from $(x_1,y_1)$ to $(x_2,y_2)$:

$\Delta x = x_2 - x_1,\quad \Delta y = y_2-y_1,\quad m=\frac{\Delta y}{\Delta x}$

Sampling at unit intervals gives the increments:

• If $|m|\le 1$ (sample in $x$): $\Delta x=1$, so $x_{k+1}=x_k+1$ and $y_{k+1}=y_k+m$.
• If $|m|> 1$ (sample in $y$): $\Delta y=1$, so $y_{k+1}=y_k+1$ and $x_{k+1}=x_k+\dfrac{1}{m}$.

(For lines drawn right-to-left use $-1$ and $-m$ instead.)

Steps:

1. Read the end points and find $dx$, $dy$.
2. $steps=\max(|dx|,|dy|)$.
3. $x_{inc}=dx/steps$, $y_{inc}=dy/steps$.
4. Plot $(x_1,y_1)$ rounded; then repeat $steps$ times: $x=x+x_{inc}$, $y=y+y_{inc}$, plot $(\text{round}(x),\text{round}(y))$.

Comparison with Bresenham's line algorithm

Decision parameter in circle drawing

In the midpoint circle algorithm the circle is $f(x,y)=x^2+y^2-r^2=0$. Inside the circle $f<0$, outside $f>0$, on it $f=0$. Starting at $(0,r)$ and moving in unit steps of $x$, the next pixel is either $(x_k+1,y_k)$ or $(x_k+1,y_k-1)$. The decision parameter is the value of $f$ at the midpoint of these two candidates:

$p_k=f\left(x_k+1,\;y_k-\tfrac12\right)=(x_k+1)^2+\left(y_k-\tfrac12\right)^2-r^2$

• If $p_k<0$: midpoint is inside, so choose $(x_k+1,y_k)$ and $p_{k+1}=p_k+2x_{k+1}+1$.
• Else: choose $(x_k+1,y_k-1)$ and $p_{k+1}=p_k+2x_{k+1}+1-2y_{k+1}$.

Initial value: $p_0=\tfrac54-r\approx 1-r$. Only the first octant ($x\le y$) is calculated; the other octants come from symmetry.

Numerical: $r=5$, centre $(10,5)$

$p_0=1-5=-4$, start $(x_0,y_0)=(0,5)$.

The loop stops when $x\ge y$ (the next point $(4,4)$ would have $x\ge y$, so the octant is complete). First-octant points (relative to centre): $(0,5),(1,5),(2,5),(3,4)$. Reflecting by $(x,y)\to(y,x)$ gives $(4,3),(5,2),(5,1),(5,0)$.

First-quadrant pixels (relative): $(0,5),(1,5),(2,5),(3,4),(4,3),(5,2),(5,1),(5,0)$.

Translate by adding the centre $(10,5)$:

$(10,10),\ (11,10),\ (12,10),\ (13,9),\ (14,8),\ (15,7),\ (15,6),\ (15,5)$

Homogeneous coordinates

In homogeneous coordinates a 2D point $(x,y)$ is represented by three numbers $(x_h,y_h,h)$ with $x=x_h/h,\ y=y_h/h$ (usually $h=1$, so the point is $(x,y,1)$). This allows translation, rotation and scaling to be expressed all as $3\times3$ matrix multiplications, so a sequence of transformations can be combined into a single composite matrix.

Composite matrix for rotation by $\theta=45^\circ$ about $(2,3)$

Steps: translate $(2,3)$ to origin, rotate, translate back.

$M=T(2,3)\cdot R(45^\circ)\cdot T(-2,-3)$

$M=\begin{bmatrix}1&0&2\\0&1&3\\0&0&1\end{bmatrix}\begin{bmatrix}\cos45&-\sin45&0\\\sin45&\cos45&0\\0&0&1\end{bmatrix}\begin{bmatrix}1&0&-2\\0&1&-3\\0&0&1\end{bmatrix}$

With $\cos45=\sin45=0.7071$:

$M=\begin{bmatrix}0.7071&-0.7071&2-2(0.7071)+3(0.7071)\\0.7071&0.7071&3-2(0.7071)-3(0.7071)\\0&0&1\end{bmatrix}=\begin{bmatrix}0.7071&-0.7071&2.7071\\0.7071&0.7071&-0.5355\\0&0&1\end{bmatrix}$

Rotating triangle A(0,0), B(6,2), C(3,4)

$x'=0.7071x-0.7071y+2.7071,\quad y'=0.7071x+0.7071y-0.5355$

• A: $x'=2.7071,\ y'=-0.5355$ gives $A'(2.71,-0.54)$
• B: $x'=4.2426-1.4142+2.7071=5.5355,\ y'=4.2426+1.4142-0.5355=5.1213$ gives $B'(5.54,5.12)$
• C: $x'=2.1213-2.8284+2.7071=2.0,\ y'=2.1213+2.8284-0.5355=4.4142$ gives $C'(2.00,4.41)$

2D vs 3D graphics

Which is more applicable?

3D graphics is more widely applicable today, because the real world is three-dimensional. It gives realistic visualisation with depth, lighting, shadows and perspective, and lets the viewer rotate and inspect objects from any angle. It is used in games, movies and animation, architecture, CAD/CAM, medical imaging, virtual reality and scientific simulation. Modern GPUs make its cost manageable. 2D remains best for simple interfaces, charts and text, but for realistic applications 3D is preferred.

Importance of shading

A polygon mesh model approximates a curved surface with flat polygons. Without shading each polygon is displayed with one flat colour and the facets and edges are clearly visible. Shading calculates intensity across the surface using a lighting model, which:

• gives the object a smooth, realistic appearance with the illusion of depth and curvature;
• shows the effect of light sources, highlights and shadows;
• hides the polygon facets without increasing the number of polygons;
• helps the viewer understand the shape of 3D objects.

Gouraud vs Phong shading

Multimedia technology

Multimedia is the integrated use of several media elements (text, graphics, images, audio, video and animation) in a computer-controlled, usually interactive, system. Multimedia technology covers the hardware, software, storage (CD/DVD), compression, authoring and delivery methods used to create and present such content. It is used in education, entertainment, advertising, games, training, web and kiosks.

Multimedia team

A multimedia project needs people with different skills:

• Project manager: plans, schedules, budgets, coordinates the team and communicates with the client.
• Multimedia designer / instructional designer: designs the content structure, navigation and interface, and the learning objectives.
• Content specialist / subject expert: supplies and checks the information.
• Scriptwriter: writes text, narration and scripts.
• Graphic artist / illustrator: creates images, icons and layouts.
• Animator: creates animation and 2D/3D models.
• Audio specialist: records, edits and mixes sound, music and narration.
• Video specialist (producer, camera, editor): shoots and edits video.
• Programmer / author: integrates the elements using authoring tools or code and adds interactivity.
• Quality tester: tests the product for errors and usability.
• Marketing and support staff: release, distribute and support the product.

One person may play several roles in small projects.

Animation

Animation is the process of creating the illusion of motion by displaying a rapid sequence of still images (frames), each slightly different from the previous one. Because of persistence of vision, the viewer sees continuous movement when frames are shown at about 12-30 or more frames per second (24 fps for film, 25/30 fps for video).

Principles of animation (from the Disney animators, still used in 2D, 3D and game animation today)

1. Squash and stretch: deforming an object during motion to show weight and flexibility.
2. Anticipation: a preparatory action before the main action (e.g. crouching before a jump).
3. Staging: presenting the idea clearly so the viewer's attention is on the important thing.
4. Straight-ahead action and pose-to-pose: two drawing approaches, frame by frame or via key poses with in-betweens.
5. Follow-through and overlapping action: parts of a body continue moving after the main body stops (hair, tail, clothes).
6. Slow in and slow out: more frames at the start and end of a movement, fewer in the middle, for natural acceleration.
7. Arcs: natural motion follows curved paths.
8. Secondary action: supporting actions that enrich the main action.
9. Timing: number of frames for an action controls speed and mood.
10. Exaggeration: emphasising actions for impact.
11. Solid drawing: keeping volume, weight and perspective in the 3D form.
12. Appeal: characters should be interesting and believable.

Today these principles guide game character design, films, web/UI animation, advertisements and e-learning, making motion look natural and engaging.

LCD vs LED

An LCD (Liquid Crystal Display) controls light passing through liquid-crystal cells placed between polarisers, lit from behind by a light source. The term "LED display" usually means an LCD that uses LEDs as its backlight (LED-backlit LCD); older LCDs used CCFL (fluorescent) tubes.

In both, the liquid crystals form the image; only the light source differs. (OLED, in contrast, has self-emitting pixels and needs no backlight.)