Computer Graphics and Animation

Computer graphics: Computer graphics is the field of computer science concerned with creating, storing, manipulating and displaying pictures and images using a computer. A picture is built from basic primitives (points, lines, polygons, curves) and shown on an output device such as a monitor or printer. It may be interactive (the user controls the image in real time) or passive, and 2D or 3D.

Application areas:

1. Computer-Aided Design (CAD): design of buildings, machines, cars, aircraft, circuits and VLSI chips, with drawings that can be viewed from any angle.
2. Entertainment and animation: cartoons, films, special effects and video games.
3. Education and training: simulators for pilots, drivers and ship captains; virtual laboratories.
4. Presentation graphics: bar charts, pie charts, line graphs and slides for business and statistics.
5. Medical imaging and visualisation: CT, MRI and ultrasound images, 3D organ models, surgical planning.
6. Scientific visualisation: weather maps, molecular structures, simulations of fluid flow.
7. Graphical user interfaces (GUI): windows, icons, menus used by operating systems and software.
8. Virtual reality: immersive 3D environments for games, design and training.
9. Cartography and GIS: digital maps, terrain models, satellite image processing.
10. Image processing: enhancement, restoration and analysis of photographs.

Mid-point circle algorithm: It draws a circle of radius $r$ centred at the origin by using the symmetry of the circle and an integer decision parameter. Only one octant (from $x=0$ to $x=y$) is computed, starting at $(0, r)$; the other seven octants come from symmetry: $(\pm x,\pm y)$ and $(\pm y,\pm x)$. Shifting the centre to $(x_c, y_c)$ is done by adding $x_c$ and $y_c$ to every point.

Idea: The circle function is $f(x,y) = x^2 + y^2 - r^2$ which is $<0$ inside the circle, $=0$ on it and $>0$ outside. Having plotted $(x_k, y_k)$, the next pixel is either $(x_k+1, y_k)$ or $(x_k+1, y_k-1)$. The decision parameter is the function value at their midpoint: $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; then $p_{k+1} = p_k + 2x_{k+1} + 1$.
• If $p_k \ge 0$, choose $(x_k+1, y_k-1)$; then $p_{k+1} = p_k + 2x_{k+1} + 1 - 2y_{k+1}$.

The initial value at $(0,r)$ is $p_0 = f\left(1, r-\tfrac12\right) = \tfrac54 - r \approx 1 - r$

Algorithm:

1. Input radius $r$ and centre $(x_c, y_c)$; set $x=0$, $y=r$.
2. Compute $p = 1 - r$.
3. Plot the point and its seven symmetric points.
4. While $x < y$:
   • $x = x + 1$
   • if $p < 0$: $p = p + 2x + 1$
   • else: $y = y - 1$, $p = p + 2x + 1 - 2y$
   • plot the eight symmetric points (shifted by the centre).
5. Stop when $x \ge y$.

It uses only integer addition and subtraction, so it is fast.

In 3D, a point $P(x,y,z)$ is written in homogeneous coordinates as $(x, y, z, 1)$ and each transformation is a $4\times4$ matrix, so that transformations can be combined by matrix multiplication: $P' = M \cdot P$.

1. Translation by $(t_x, t_y, t_z)$: $T = \begin{bmatrix}1&0&0&t_x\\0&1&0&t_y\\0&0&1&t_z\\0&0&0&1\end{bmatrix}$ i.e. $x'=x+t_x,\; y'=y+t_y,\; z'=z+t_z$.

2. Scaling by $(s_x, s_y, s_z)$ about the origin: $S = \begin{bmatrix}s_x&0&0&0\\0&s_y&0&0\\0&0&s_z&0\\0&0&0&1\end{bmatrix}$

3. Rotation by angle $\theta$:

• About the z-axis: $x' = x\cos\theta - y\sin\theta,\; y' = x\sin\theta + y\cos\theta,\; z'=z$ $R_z = \begin{bmatrix}\cos\theta&-\sin\theta&0&0\\\sin\theta&\cos\theta&0&0\\0&0&1&0\\0&0&0&1\end{bmatrix}$
• About the x-axis: $y' = y\cos\theta - z\sin\theta,\; z' = y\sin\theta + z\cos\theta,\; x'=x$
• About the y-axis: $z' = z\cos\theta - x\sin\theta,\; x' = z\sin\theta + x\cos\theta,\; y'=y$

(Other basic transformations are reflection and shearing.)

Example: Let $P = (2,3,4)$.

• Translation by $(1,2,3)$ gives $P' = (3,5,7)$.
• Scaling by $(2,2,2)$ gives $P' = (4,6,8)$.
• Rotation by $90^\circ$ about the z-axis: $x' = 2(0) - 3(1) = -3$, $y' = 2(1) + 3(0) = 2$, $z'=4$, so $P' = (-3, 2, 4)$.

Polygon clipping: Clipping is the process of removing the parts of a picture that lie outside a clipping window/region. Polygon clipping clips a polygon against the window so that the result is again a polygon (or polygons) that can be filled, with new edges added along the window boundary where required. Applying a line clipping algorithm to each edge separately does not give a closed polygon, so special algorithms are used.

Sutherland-Hodgman algorithm: The polygon is clipped against one window boundary at a time (left, right, bottom, top). The output vertex list of one stage becomes the input of the next stage. The polygon is processed edge by edge, taking each pair of consecutive vertices $(S, P)$ (from vertex $S$ to vertex $P$), and four cases arise with respect to the current clip boundary:

Steps:

1. Take the vertex list of the polygon.
2. For each clip boundary in turn:
   • Start with $S$ = last vertex of the list.
   • For each vertex $P$ in the list, apply the four cases above (computing the intersection of segment $SP$ with the boundary where needed), then set $S = P$.
   • The collected output vertices form the new list.
3. After the four boundaries, the final list is the clipped polygon.

For a vertical boundary $x = x_{min}$, the intersection of $SP$ is $y = y_S + m(x_{min} - x_S)$ with slope $m = \frac{y_P-y_S}{x_P-x_S}$.

Limitation: For concave polygons it may produce extra connecting edges along the window boundary, which is removed by post-processing or by the Weiler-Atherton algorithm.

Triangle: $A(2,3),\; B(5,5),\; C(4,3)$. The transformation is a rotation by $90^\circ$ (anticlockwise) about the origin followed by translation by $(2,2)$.

Rotation matrix ($\theta=90^\circ$, $\cos\theta=0$, $\sin\theta=1$): $R = \begin{bmatrix}0&-1&0\\1&0&0\\0&0&1\end{bmatrix},\qquad T = \begin{bmatrix}1&0&2\\0&1&2\\0&0&1\end{bmatrix}$

Composite matrix (rotation first, then translation, so $M = T\cdot R$): $M = \begin{bmatrix}1&0&2\\0&1&2\\0&0&1\end{bmatrix}\begin{bmatrix}0&-1&0\\1&0&0\\0&0&1\end{bmatrix} = \begin{bmatrix}0&-1&2\\1&0&2\\0&0&1\end{bmatrix}$

Apply to the vertices (as columns of homogeneous coordinates): $\begin{bmatrix}0&-1&2\\1&0&2\\0&0&1\end{bmatrix}\begin{bmatrix}2&5&4\\3&5&3\\1&1&1\end{bmatrix} = \begin{bmatrix}-1&-3&-1\\4&7&6\\1&1&1\end{bmatrix}$

Check: $A$: $x' = 0(2) - 1(3) + 2 = -1$, $y' = 2 + 0 + 2 = 4$. $B$: $x' = -5+2 = -3$, $y' = 5+2 = 7$. $C$: $x' = -3+2 = -1$, $y' = 4+2 = 6$.

New vertices: $A'(-1,4)$, $B'(-3,7)$, $C'(-1,6)$.

Scan-line algorithm: It is an image-space method for visible surface detection that works scan line by scan line, from top to bottom of the screen. For each scan line it finds which polygon surface is nearest to the viewer at each pixel and writes that surface's colour into the frame buffer. It is an extension of the scan-line polygon filling algorithm to several surfaces.

Data structures:

• Edge table: the edges of all polygons with end coordinates, slope and the polygons they belong to.
• Polygon table: for each polygon, its plane coefficients, colour and an in/out flag.
• Active edge list: edges that cross the current scan line, sorted by $x$.

Procedure:

1. For each scan line, update the active edge list with edges intersecting that line.
2. Go along the line from left to right. Each time an edge is crossed, the flag of its polygon is switched on (entering) or off (leaving).
3. Pixels (spans) between edges where only one polygon flag is on take the colour of that polygon.
4. Where the flags of two or more polygons are on (overlap), the depth of each plane at the span is calculated from the plane equation $Ax+By+Cz+D=0$, i.e. $z = -(Ax+By+D)/C$. The polygon with the smallest depth (closest to viewer) is visible and its colour is used.
5. Where no flag is on, the background colour is used.
6. Move to the next scan line, using coherence (edge $x$ values and depths change by constant amounts from one line to the next) to update values quickly.

If polygons do not intersect in depth, depth calculation is needed only when a new edge is crossed. Intersecting surfaces may need to be split.

Virtual Reality (VR) system: A VR system creates a computer-generated 3D environment that the user can enter and interact with in real time, using devices that track the user and give sensory feedback so that the user feels present in the virtual world.

Architecture and components:

1. Input devices: let the user and the system interact with the virtual world.
   • Position/motion trackers (magnetic, optical, inertial) that follow the head, hands and body.
   • Data gloves, 3D mice, joysticks, wands, treadmills, voice input.
2. Output devices: give sensory feedback.
   • Visual: head-mounted display (HMD), CAVE projection rooms, stereoscopic glasses.
   • Audio: 3D spatial sound through headphones or speakers.
   • Haptic: force and touch feedback gloves and suits.
3. VR engine / computer system: a powerful computer with a fast CPU and GPU that processes input, runs the simulation and renders images at a high frame rate (at least 30-60 frames per second) to avoid lag and motion sickness.
4. Software and databases:
   • A virtual world database holding 3D models, textures, sounds and physical properties of objects.
   • Modelling tools (CAD/3D modelling) to build the objects.
   • Real-time rendering, collision detection and physics simulation routines.
   • VR toolkits/APIs (e.g. OpenGL, Unity) to integrate everything.
5. Application: the specific content such as a flight simulator, game, training or medical system.

Working loop: Trackers send the user's position and orientation to the VR engine, which updates the virtual world and renders the new view, then sends it to the display, audio and haptic devices. This loop repeats continuously with minimal delay.

DDA (Digital Differential Analyzer) line algorithm: DDA draws a line between $(x_1,y_1)$ and $(x_2,y_2)$ by sampling at unit intervals along the axis in which the line changes most, and computing the other coordinate from the slope.

Working:

1. Compute $dx = x_2 - x_1$ and $dy = y_2 - y_1$.
2. Number of steps: $steps = \max(|dx|, |dy|)$.
3. Increments: $x_{inc} = dx / steps$, $y_{inc} = dy / steps$ (one of them is 1 or $-1$).
4. Start at $(x_1, y_1)$. Repeat $steps$ times: $x = x + x_{inc}$, $y = y + y_{inc}$ and plot $(\text{round}(x), \text{round}(y))$.

It is simple and faster than using the line equation directly, but it uses floating-point addition and rounding, so error accumulates on long lines.

Bresenham's algorithm for (2,2) to (10,5):

$dx = 8,\; dy = 3$, slope $m = 3/8 < 1$, so $x$ is incremented each step.

Initial decision parameter: $p_0 = 2dy - dx = 6 - 8 = -2$.

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

Pixels plotted: (2,2), (3,2), (4,3), (5,3), (6,4), (7,4), (8,4), (9,5), (10,5).

Object-space vs image-space methods of visible surface detection:

Z-buffer (depth-buffer) algorithm: An image-space method that uses two buffers of the same size as the screen: a frame buffer holding the colour of each pixel, and a depth buffer holding the depth ($z$) of the surface currently visible at each pixel. Surfaces can be processed in any order.

Algorithm:

1. Initialise the depth buffer to the maximum depth (far plane, e.g. 1.0 or $\infty$) and the frame buffer to the background colour:
   • depth$(x,y) =$ max depth, frame$(x,y) =$ background, for all pixels.
2. For each polygon, for each pixel $(x,y)$ it covers, compute its depth $z(x,y)$ from the plane equation: $z = \frac{-Ax - By - D}{C}$
   • If $z <$ depth$(x,y)$ (closer to viewer): set depth$(x,y) = z$ and frame$(x,y) =$ the polygon's colour at $(x,y)$.
   • Otherwise leave the pixel unchanged.
3. After all polygons are processed, the frame buffer holds the visible image.

Depth along a scan line is computed incrementally: moving from $x$ to $x+1$ gives $z' = z - A/C$, and to the next scan line $z' = z + (B/C)$ (using the edge $x$ change).

Merits: simple, easy to implement in hardware, handles any surface that can give a depth, no sorting needed. Demerits: needs extra memory for the depth buffer, cannot easily handle transparency, and has aliasing and depth precision problems.

Window-to-viewport transformation: A window is the region of the world coordinate system selected for display and a viewport is the region of the screen where it is displayed. The mapping keeps the relative position of every point the same.

Derivation: Let the window be $(xw_{min}, yw_{min})$ to $(xw_{max}, yw_{max})$ and the viewport $(xv_{min}, yv_{min})$ to $(xv_{max}, yv_{max})$. A window point $(x_w, y_w)$ maps to $(x_v, y_v)$ with the same relative position: $\frac{x_v - xv_{min}}{xv_{max} - xv_{min}} = \frac{x_w - xw_{min}}{xw_{max} - xw_{min}},\qquad \frac{y_v - yv_{min}}{yv_{max} - yv_{min}} = \frac{y_w - yw_{min}}{yw_{max} - yw_{min}}$ Solving, $x_v = xv_{min} + (x_w - xw_{min})\,s_x,\qquad y_v = yv_{min} + (y_w - yw_{min})\,s_y$ where the scale factors are $s_x = \frac{xv_{max}-xv_{min}}{xw_{max}-xw_{min}},\qquad s_y = \frac{yv_{max}-yv_{min}}{yw_{max}-yw_{min}}$ This is equivalent to: translate the window to the origin, scale by $(s_x, s_y)$, and translate to the viewport position.

Numerical: Window: $(0,0)$ to $(4,4)$; viewport: $(0,0)$ to $(2,2)$. $s_x = \frac{2-0}{4-0} = 0.5,\qquad s_y = \frac{2-0}{4-0} = 0.5$ For the point $(x_w, y_w) = (2, 4)$: $x_v = 0 + (2-0)(0.5) = 1,\qquad y_v = 0 + (4-0)(0.5) = 2$

The point is mapped to (1, 2) in the viewport. It lies halfway along $x$ and on the top edge in both the window and the viewport, so the relative placement is preserved.

Area filling: Area filling is the process of colouring all the pixels inside a closed region (polygon or any bounded area) with a specified colour or pattern. Two approaches are used: the scan-line method (for regions defined by their edges) and the seed fill methods (boundary fill and flood fill) for regions defined by their pixel colours.

Boundary fill algorithm: Starting from an interior point (the seed), it paints neighbouring pixels until a boundary of a given colour is met. It works for regions whose boundary is a single colour.

Algorithm (4-connected):

boundaryFill(x, y, fillColor, boundaryColor):
    current = getPixel(x, y)
    if current != boundaryColor and current != fillColor:
        setPixel(x, y, fillColor)
        boundaryFill(x + 1, y, fillColor, boundaryColor)
        boundaryFill(x - 1, y, fillColor, boundaryColor)
        boundaryFill(x, y + 1, fillColor, boundaryColor)
        boundaryFill(x, y - 1, fillColor, boundaryColor)

Steps:

1. Choose a seed pixel inside the region.
2. If the pixel colour is neither the boundary colour nor the fill colour, set it to the fill colour.
3. Recursively repeat for its neighbours.
4. Stop when all neighbours are boundary or already filled.

4-connected vs 8-connected: The 4-connected version visits left, right, up and down neighbours; the 8-connected version also visits the four diagonals, and so can fill regions with diagonal-only connections and avoid leaving gaps, but it may leak through diagonal boundary gaps.

Drawback: The recursion uses a lot of stack and is slow for large areas, so a stack-based or scan-line variant is used in practice.

Scaling transformation: Scaling changes the size of an object. A point $(x,y)$ is multiplied by scale factors $s_x$ and $s_y$ about the origin: $x' = x\cdot s_x,\qquad y' = y\cdot s_y$ In homogeneous form: $S(s_x,s_y) = \begin{bmatrix}s_x&0&0\\0&s_y&0\\0&0&1\end{bmatrix}$ If $s_x=s_y>1$ the object is enlarged, and if $<1$ it is reduced.

Proof that successive scalings are multiplicative: Apply $S(s_{x1},s_{y1})$ and then $S(s_{x2},s_{y2})$ to a point $P$: $P' = S_1\cdot P,\qquad P'' = S_2\cdot P' = S_2\cdot S_1\cdot P$ The composite matrix is $S_2\cdot S_1 = \begin{bmatrix}s_{x2}&0&0\\0&s_{y2}&0\\0&0&1\end{bmatrix}\begin{bmatrix}s_{x1}&0&0\\0&s_{y1}&0\\0&0&1\end{bmatrix} = \begin{bmatrix}s_{x1}s_{x2}&0&0\\0&s_{y1}s_{y2}&0\\0&0&1\end{bmatrix}$ which equals $S(s_{x1}s_{x2},\; s_{y1}s_{y2})$.

Hence two successive scalings are equivalent to one scaling whose factors are the products of the individual factors. Since multiplication of numbers is commutative, the order does not matter either.

Example: Scaling by $(2,3)$ then by $(4,2)$ equals a single scaling by $(8,6)$.

Symmetry property of a circle: A circle centred at the origin is symmetric about both axes and both diagonals $y=\pm x$. So if $(x,y)$ lies on the circle, then so do the seven points $(x,y),\ (y,x),\ (-x,y),\ (-y,x),\ (x,-y),\ (y,-x),\ (-x,-y),\ (-y,-x)$ Therefore only one octant (the $45^\circ$ arc from $x=0$ to $x=y$) needs to be computed, and the rest is obtained by reflection. This is called eight-way symmetry.

Digitising the circle with centre $(0,0)$ and $r=9$ (mid-point algorithm):

Start at $(0,9)$, initial parameter $p_0 = 1 - r = -8$.

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

The next point would be $(7,6)$ with $x>y$, so we stop.

Points of the first octant: (0,9), (1,9), (2,9), (3,8), (4,8), (5,7), (6,7).

Other octants by symmetry (swap coordinates and change signs):

• Swapped: (9,0), (9,1), (9,2), (8,3), (8,4), (7,5), (7,6)
• Every point is also plotted with signs $(\pm x, \pm y)$, e.g. (-1,9), (1,-9), (-9,-1) etc.

Window: A window is the rectangular area in the world coordinate system that selects what part of the scene is to be displayed.

Viewport: A viewport is the rectangular area on the display device (screen coordinates) that specifies where the selected part is displayed.

2D viewing transformation pipeline: The pipeline is the sequence of steps that maps a scene described in world coordinates to device coordinates:

1. Modelling coordinates to world coordinates: each object, defined in its own local (modelling) coordinates, is placed in the common world coordinate system by modelling transformations (translation, rotation, scaling).
2. World coordinates to viewing coordinates: a window is defined (it may be rotated or placed at any position), and the world is transformed so that the window lies in a viewing coordinate system aligned with the axes: translate the window origin to the origin and rotate it.
3. Viewing coordinates to normalised viewing coordinates: the window is mapped to a normalised square (0 to 1 or -1 to 1) so the process is independent of any device. Clipping against the window is usually done here.
4. Normalised coordinates to device coordinates: the normalised picture is mapped to the viewport on the screen (the window-to-viewport transformation): $x_v = xv_{min} + (x_w - xw_{min})\frac{xv_{max}-xv_{min}}{xw_{max}-xw_{min}}$ and similarly for $y_v$.

Summary: Modelling coordinates $\rightarrow$ world coordinates $\rightarrow$ viewing coordinates $\rightarrow$ normalised coordinates (clipping) $\rightarrow$ device coordinates.

The prism has vertices $A(0,0,0)$, $B(1,1,0)$, $C(1,2,2)$, $D(0,2,0)$. It is first rotated by $+90^\circ$ about the y-axis and then reflected about the yz-plane.

Rotation about the y-axis by $\theta=90^\circ$ ($\cos\theta=0$, $\sin\theta=1$): $x' = x\cos\theta + z\sin\theta = z,\qquad y'=y,\qquad z' = -x\sin\theta + z\cos\theta = -x$ $R_y = \begin{bmatrix}0&0&1&0\\0&1&0&0\\-1&0&0&0\\0&0&0&1\end{bmatrix}$

Reflection about the yz-plane (the $x$ coordinate changes sign): $M = \begin{bmatrix}-1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\end{bmatrix}$

Composite matrix: $M\cdot R_y = \begin{bmatrix}0&0&-1&0\\0&1&0&0\\-1&0&0&0\\0&0&0&1\end{bmatrix}$ so $x'' = -z,\; y''=y,\; z''=-x$.

Applying to each vertex:

• $A(0,0,0)$: rotation gives $(0,0,0)$, reflection gives $(0,0,0)$.
• $B(1,1,0)$: rotation gives $(0,1,-1)$, reflection gives $(0,1,-1)$.
• $C(1,2,2)$: rotation gives $(2,2,-1)$, reflection gives $(-2,2,-1)$.
• $D(0,2,0)$: rotation gives $(0,2,0)$, reflection gives $(0,2,0)$.

New vertices: $A'(0,0,0)$, $B'(0,1,-1)$, $C'(-2,2,-1)$, $D'(0,2,0)$.

Visible surface detection: When a 3D scene is projected onto a 2D screen, some surfaces are hidden behind others. Visible surface detection (hidden surface removal) is the process of identifying which parts of the surfaces are visible from a given viewing position so that only they are displayed, giving a realistic picture. The methods are of two kinds: object-space methods (back-face detection, depth sorting) and image-space methods (Z-buffer, scan-line).

Z-buffer (depth-buffer) algorithm: An image-space method that uses a frame buffer (colour of each pixel) and a depth buffer (depth $z$ of the nearest surface found so far at each pixel). Polygons can be processed in any order.

Algorithm:

1. Initialise: for all pixels $(x,y)$, depth$(x,y) =$ maximum depth (far plane) and frame$(x,y) =$ background colour.
2. For each polygon in the scene, for each pixel $(x,y)$ covered by its projection:
   • Calculate the depth $z$ using the plane equation $Ax+By+Cz+D=0$: $z = \frac{-Ax - By - D}{C}$
   • If $z <$ depth$(x,y)$: set depth$(x,y)=z$ and frame$(x,y)=$ surface colour at $(x,y)$.
3. After all polygons are processed, the frame buffer contains the visible image.

Along a scan line the depth is found incrementally: $z(x+1,y) = z(x,y) - A/C$.

Advantages: simple, no sorting, works for any surface that gives depth, easily done in hardware. Disadvantages: extra memory for the depth buffer, no direct support for transparency, and precision limits.

Animation is the process of generating a series of still images (frames) and displaying them quickly, usually 24-30 frames per second or more, so that the viewer perceives motion or change over time. In computer graphics, the frames are produced by changing object positions, shapes, colours, lighting or camera view from one frame to the next.

Steps to create an animation sequence

1. Storyboard layout: an outline of the action is prepared as a set of sketches showing the main events, the timing and the order of scenes.
2. Object definitions: each object taking part is defined, with its shape, size, colour, texture and the allowed motions (for example as polygon meshes or splines).
3. Key-frame specification: a key frame is a detailed drawing of the scene at a chosen instant. Key frames are placed at points where the motion changes significantly.
4. Generation of in-betweens: the frames between two key frames are produced by interpolating positions, sizes and colours (linear or spline interpolation). The number of in-betweens depends on the frame rate and on the speed of the action; for example, a 2-second shot at 24 fps needs 48 frames.
5. Rendering and output: the frames are rendered (with lighting, shading and hidden-surface removal), then played back in sequence, or stored as a video, and checked and refined if the motion is not smooth.

Other tasks such as sound synchronisation and any needed motion-path or morphing specifications are done along these steps.

Refresh rate: a CRT screen must be redrawn repeatedly because the phosphor glow fades. The number of times per second the picture is redrawn is the refresh rate (for example 60 Hz means 60 redraws per second). A rate below about 50-60 Hz causes visible flicker.

Persistence: the time a phosphor continues to emit light after the electron beam has been removed, usually measured as the time for the emitted light to fall to 10% of its original intensity. Low-persistence phosphors need a higher refresh rate, whereas high-persistence phosphors suit static displays.

Architecture of a random scan (vector) display system

In a random scan system the electron beam is directed only to those parts of the screen where the picture is to be drawn, one line at a time, in any order. Because it draws line segments, it is also called a vector or calligraphic display.

Block diagram (components in order):

 Application program --> Graphics package --> Display file (refresh buffer)
                                                       |
                                                       v
 CPU <--> System memory                      Display processor (display controller)
                                                       |
                                                       v
                                  Vector generator / DAC --> Deflection amplifiers --> CRT

• Application program and graphics package: the application describes the picture, and the graphics package converts the picture description into line-drawing commands.
• Display file (refresh display file): stores the line-drawing commands (endpoints, colour, intensity) for the whole picture, in system memory.
• Display processor (display controller): cycles through the display file once in every refresh cycle, reads each command and sends it to the vector generator.
• Vector generator: converts the digital coordinates to analog voltages that control the horizontal and vertical deflection of the beam, so that the beam draws each line directly.
• CRT: the beam is turned on only while drawing a line, then moved to the start of the next line.

Refresh rate depends on the number of lines in the picture: more lines means a lower refresh rate. Random scan gives high resolution and smooth lines and suits line drawings, but it cannot fill areas or display realistic shaded scenes well.

Bresenham's line drawing algorithm is an incremental algorithm that uses only integer addition, subtraction and multiplication by 2, and a decision parameter to choose the pixel closest to the true line.

Algorithm (for slope $0 < m < 1$)

1. Input endpoints $(x_0,y_0)$ and $(x_1,y_1)$. Compute $\Delta x = x_1-x_0$ and $\Delta y = y_1-y_0$.
2. Plot the first point $(x_0,y_0)$. Compute the initial decision parameter $p_0 = 2\Delta y - \Delta x$.
3. For each $x_k$ along the line:
   • if $p_k < 0$: next point is $(x_k+1,\,y_k)$ and $p_{k+1}=p_k+2\Delta y$;
   • otherwise: next point is $(x_k+1,\,y_k+1)$ and $p_{k+1}=p_k+2\Delta y-2\Delta x$.
4. Repeat step 3 $\Delta x$ times.

Trace for P(1, 4) and Q(7, 8)

$\Delta x = 6$, $\Delta y = 4$, slope $= 4/6 < 1$. $2\Delta y = 8$, $2\Delta y-2\Delta x = 8-12=-4$.

$p_0 = 2\Delta y-\Delta x = 8-6 = 2$

Pixels rasterized: (1, 4), (2, 5), (3, 5), (4, 6), (5, 7), (6, 7), (7, 8). The last point equals Q, which confirms the trace.

Cohen-Sutherland line clipping divides the plane into 9 regions by extending the window edges, and gives each end point a 4-bit region code TBRL (Top, Bottom, Right, Left). A bit is 1 if the point is: above the window ($y>y_{max}$), below ($y<y_{min}$), right ($x>x_{max}$), left ($x<x_{min}$).

Algorithm

1. Find the region codes of both end points.
2. If both codes are 0000, the line is completely inside: accept.
3. If the bitwise AND of the codes is non-zero, the line lies wholly outside one edge: reject.
4. Otherwise, pick an end point that is outside, find the intersection of the line with the window edge indicated by a 1 bit (in order T, B, R, L), and replace that end point by the intersection. Using slope $m=(y_2-y_1)/(x_2-x_1)$: for a vertical edge $y=y_1+m(x-x_1)$, for a horizontal edge $x=x_1+(y-y_1)/m$.
5. Recompute the code and repeat from step 2.

Numerical. Window: $x_{min}=20$, $x_{max}=90$, $y_{min}=20$, $y_{max}=70$.

• P(10, 30): $x<20$, so left bit set. Code = 0001.
• Q(80, 80): $y>70$, so top bit set. Code = 1000.

Neither code is 0000, and AND $= 0000$, so the line is neither trivially accepted nor rejected and must be clipped.

Slope: $m = \dfrac{80-30}{80-10} = \dfrac{50}{70} = \dfrac{5}{7}$.

Clip P against the left edge $x=20$: $y = 30 + \tfrac{5}{7}(20-10) = 30+7.14 = 37.14$ P becomes P'(20, 37.14), whose code is 0000.

Clip Q against the top edge $y=70$: $x = 80 + \frac{70-80}{5/7} = 80-14 = 66$ Q becomes Q'(66, 70), whose code is 0000.

Both new end points are inside, so the visible part of the line is from (20, 37.14) to (66, 70).

Horizontal retrace: in a raster CRT, after the electron beam finishes a scan line it is switched off and moved quickly from the right end of that line back to the left end of the next line. This return is the horizontal retrace.

Vertical retrace: after the last line at the bottom of the screen has been scanned, the beam is turned off and moved from the bottom right back to the top left corner to begin the next frame. This return is the vertical retrace.

Architecture of a random scan display system

A random scan (vector) system draws the picture as straight line segments, with the beam directed only to the parts of the screen that contain the picture.

• Application program / graphics package: creates the picture definition and converts it into line-drawing commands.
• Display file (refresh buffer): stores these commands in system memory.
• Display processor (display controller): reads the display file every refresh cycle and sends each command to the vector generator.
• Vector generator and deflection circuits: convert the coordinates to analog voltages that deflect the beam along each line.
• CRT: displays the line segments; the picture is refreshed 30-60 times per second by redrawing all lines.

Because it draws lines directly, it gives smooth, high-resolution lines, but the refresh rate falls as the number of lines grows, and it is poor for filled or shaded pictures.

Decision parameter in the mid-point circle algorithm. The circle is $f(x,y)=x^2+y^2-r^2=0$. For a point inside the circle $f<0$, on it $f=0$, outside it $f>0$. Starting from $(0,r)$ and stepping in $x$ over the octant from $x=0$ to $x=y$, at each step we must choose between pixel $(x_k+1,y_k)$ and $(x_k+1,y_k-1)$. The decision parameter is the value of $f$ at their mid-point:

$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 mid-point is inside the circle, so $y_k$ is closer: next point $(x_k+1,y_k)$ and $p_{k+1}=p_k+2x_{k+1}+1$.
• Otherwise next point is $(x_k+1,y_k-1)$ and $p_{k+1}=p_k+2x_{k+1}+1-2y_{k+1}$.

Initial value at $(0,r)$: $p_0 = 1-r$ (the integer form of $5/4-r$).

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

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

Now $x=3<y=4$ is the last point of the octant; the next step gives $x>y$, so we stop.

Octant points relative to origin: (0, 5), (1, 5), (2, 5), (3, 4). By eight-way symmetry, the other points are (4, 3), (5, 2), (5, 1), (5, 0) and their mirror images in the other quadrants.

Shift by the centre $(10,5)$, i.e. add $(10,5)$ to $(\pm x,\pm y)$ and $(\pm y,\pm x)$:

Window to viewport transformation. A window is the rectangular region of the world-coordinate scene that we want to display. A viewport is the rectangular area of the display device (normalized or device coordinates) in which the window contents are shown. The window-to-viewport transformation maps each point $(x_w,y_w)$ in the window to the corresponding point $(x_v,y_v)$ in the viewport, keeping the relative position:

$\frac{x_v-x_{vmin}}{x_{vmax}-x_{vmin}}=\frac{x_w-x_{wmin}}{x_{wmax}-x_{wmin}},\qquad \frac{y_v-y_{vmin}}{y_{vmax}-y_{vmin}}=\frac{y_w-y_{wmin}}{y_{wmax}-y_{wmin}}$

$x_v = x_{vmin}+(x_w-x_{wmin})s_x,\quad y_v=y_{vmin}+(y_w-y_{wmin})s_y$

with $s_x=\dfrac{x_{vmax}-x_{vmin}}{x_{wmax}-x_{wmin}}$, $s_y=\dfrac{y_{vmax}-y_{vmin}}{y_{wmax}-y_{wmin}}$. If $s_x\ne s_y$ the picture is distorted. It is done as translation of the window to the origin, scaling by $(s_x,s_y)$, and translation to the viewport position.

2D viewing pipeline. The steps from the scene description to the display are:

1. Modelling coordinates: objects are defined in their own local coordinates.
2. Modelling transformation: objects are placed into the common world coordinate scene.
3. Viewing transformation: world coordinates are converted to viewing coordinates relative to the window (translation and rotation if the window is rotated).
4. Normalization transformation: viewing coordinates are mapped to normalized viewing coordinates (0 to 1), making the system device independent.
5. Workstation transformation (window to viewport): normalized coordinates are mapped to device coordinates of the viewport on the output device.
6. Clipping is done against the window (or the normalized viewport) so only the visible part is displayed.

Thus: Modelling coordinates -> World coordinates -> Viewing coordinates -> Normalized coordinates -> Device coordinates.

DDA (Digital Differential Analyzer) algorithm for the line from $(2,2)$ to $(9,6)$.

$\Delta x = 9-2 = 7$, $\Delta y = 6-2 = 4$. Steps $=\max(|\Delta x|,|\Delta y|)=7$.

Increments: $x_{inc}=\Delta x/\text{steps}=1$, $y_{inc}=\Delta y/\text{steps}=4/7\approx 0.571$.

Starting at $(2,2)$, add the increments at each step and round to the nearest pixel:

Points generated: (2, 2), (3, 3), (4, 3), (5, 4), (6, 4), (7, 5), (8, 5), (9, 6).

Visible surface detection (hidden surface removal) is the process of identifying which surfaces or parts of surfaces of 3D objects are visible from a given viewing position, so that hidden parts are not displayed. It is needed to produce realistic pictures.

Z-buffer (depth-buffer) algorithm. This is an image-space method. It uses two buffers of the screen's size: a frame buffer (colours) and a depth buffer (the $z$ value of the nearest surface at each pixel).

1. Initialise depth buffer to the maximum depth (farthest), $depth(x,y)=\infty$ (or 1), and frame buffer to the background colour.
2. For each polygon, for each pixel $(x,y)$ that it covers, calculate the depth $z$ (by the plane equation $z=\dfrac{-Ax-By-D}{C}$, incrementally along scan lines: $z' = z - A/C$).
3. If $z <$ depth$(x,y)$ (nearer to the viewer), set depth$(x,y)=z$ and frame$(x,y)$ = the polygon's colour at that point.
4. After all polygons are processed, the frame buffer holds the visible picture.

Advantages

• Simple and easy to implement, in hardware as well.
• Polygons can be processed in any order, with no sorting.
• Works for any surface that can give depth at each pixel, and handles intersecting surfaces correctly.

Disadvantages

• Needs extra memory for the depth buffer.
• Only one visible surface per pixel is stored, so transparency and anti-aliasing are difficult.
• Time is wasted calculating depth for surfaces that later get overwritten.
• Limited depth precision can cause errors (z-fighting) for surfaces very close in depth.

Virtual Reality (VR) is a computer-generated, interactive, three-dimensional environment that gives the user the feeling of being present in it (immersion). The user wears or uses devices such as a head-mounted display (HMD), data gloves, motion trackers and 3D sound, and the system updates the scene in real time according to the user's head and body movements.

Types of virtual reality

1. Non-immersive VR: the virtual world is viewed on an ordinary computer monitor and interacted with by keyboard, mouse or joystick. The user remains aware of the real world. Examples: 3D video games, CAD walkthroughs, simulators on a desktop.
2. Semi-immersive VR: gives a partial feeling of presence using large screens, projection systems or a high-resolution display with a physical cockpit or control set-up. Example: flight simulators for pilot training.
3. Fully immersive VR: the user wears an HMD with head tracking and often gloves and body sensors, so that the real world is blocked out and the user feels inside the virtual world. Examples: VR games, surgical training, virtual tours.
4. Augmented reality (AR) / mixed reality (often listed as a related type): virtual objects are overlaid on the view of the real world (for example on a phone or smart glasses).
5. Collaborative VR: several users in different places share the same virtual environment at the same time, over a network.

Reflection is a transformation that produces a mirror image of an object. The image is formed by rotating the object by $180^\circ$ about the reflection axis, which can be a line in the plane (such as the $x$-axis or $y$-axis).

Reflection about the x-axis. A point $(x,y)$ goes to $(x,-y)$: the $x$ coordinate is unchanged, the $y$ coordinate changes sign.

$x' = x\cdot 1 + y\cdot 0,\qquad y' = x\cdot 0 + y\cdot(-1)$

In homogeneous coordinates:

$\begin{bmatrix}x'\\y'\\1\end{bmatrix}=\begin{bmatrix}1&0&0\\0&-1&0\\0&0&1\end{bmatrix}\begin{bmatrix}x\\y\\1\end{bmatrix}$

Reflection about the y-axis. A point $(x,y)$ goes to $(-x,y)$:

$x'=-x,\qquad y'=y$

$\begin{bmatrix}x'\\y'\\1\end{bmatrix}=\begin{bmatrix}-1&0&0\\0&1&0\\0&0&1\end{bmatrix}\begin{bmatrix}x\\y\\1\end{bmatrix}$

For example, the point $(3,2)$ reflects to $(3,-2)$ about the x-axis and to $(-3,2)$ about the y-axis.