Computer Graphics

Reflection about the horizontal line $y = 7$ is done by a composite transformation:

1. Translate so the line coincides with the x-axis: $T(0,-7)$.
2. Reflect about the x-axis: $F_x$.
3. Translate back: $T(0,7)$.

$M = T(0,7)\cdot F_x \cdot T(0,-7) = \begin{bmatrix}1&0&0\\0&1&7\\0&0&1\end{bmatrix}\begin{bmatrix}1&0&0\\0&-1&0\\0&0&1\end{bmatrix}\begin{bmatrix}1&0&0\\0&1&-7\\0&0&1\end{bmatrix} = \begin{bmatrix}1&0&0\\0&-1&14\\0&0&1\end{bmatrix}$

So $x' = x$, $y' = 14 - y$.

For $A(9,3)$:

$\begin{bmatrix}1&0&0\\0&-1&14\\0&0&1\end{bmatrix}\begin{bmatrix}9\\3\\1\end{bmatrix} = \begin{bmatrix}9\\11\\1\end{bmatrix}$

so $A' = (9, 11)$.

For $B(12,10)$:

$\begin{bmatrix}1&0&0\\0&-1&14\\0&0&1\end{bmatrix}\begin{bmatrix}12\\10\\1\end{bmatrix} = \begin{bmatrix}12\\4\\1\end{bmatrix}$

so $B' = (12, 4)$.

Graph (each point is the same distance from $y = 7$ on the opposite side: $A$ is 4 below, $A'$ is 4 above; $B$ is 3 above, $B'$ is 3 below):

 y
11 |  A'(9,11)
10 |                B(12,10)
 7 |------------------------------  mirror line y = 7
 4 |                B'(12,4)
 3 |  A(9,3)
   +--------------------------- x
      9            12

The initial line joins $A(9,3)$ to $B(12,10)$ (rising); the final line joins $A'(9,11)$ to $B'(12,4)$ (falling). The two lines cross at $y = 7$, where $x = 9 + 3\cdot\frac{4}{7} \approx 10.71$, on the mirror line, and the length of the segment is unchanged.

SVGA resolution is taken as $800 \times 600$ pixels. True colour with 24 bits needs $24/8 = 3$ bytes per pixel.

Memory per frame

$800 \times 600 \times 3 = 1{,}440{,}000 \text{ bytes}$

Number of frames. Duration is $8 \times 60 = 480$ s, at 25 frames per second:

$480 \times 25 = 12{,}000 \text{ frames}$

Total memory

$1{,}440{,}000 \times 12{,}000 = 17{,}280{,}000{,}000 \text{ bytes}$

In binary units:

$\frac{17{,}280{,}000{,}000}{1024^2} \approx 16{,}479.5 \text{ MB} \approx 16.09 \text{ GB}$

So about 17.28 x 10^9 bytes (about 16.1 GB) is needed for the uncompressed video.

Reflection about the vertical line $x = 7$ is a composite transformation:

1. Translate the line to the y-axis: $T(-7, 0)$.
2. Reflect about the y-axis: $F_y$.
3. Translate back: $T(7, 0)$.

$M = T(7,0)\cdot F_y\cdot T(-7,0) = \begin{bmatrix}1&0&7\\0&1&0\\0&0&1\end{bmatrix}\begin{bmatrix}-1&0&0\\0&1&0\\0&0&1\end{bmatrix}\begin{bmatrix}1&0&-7\\0&1&0\\0&0&1\end{bmatrix} = \begin{bmatrix}-1&0&14\\0&1&0\\0&0&1\end{bmatrix}$

So $x' = 14 - x$, $y' = y$.

For $A(9,3)$:

$\begin{bmatrix}-1&0&14\\0&1&0\\0&0&1\end{bmatrix}\begin{bmatrix}9\\3\\1\end{bmatrix} = \begin{bmatrix}5\\3\\1\end{bmatrix}$

so $A' = (5,3)$.

For $B(12,10)$:

$\begin{bmatrix}-1&0&14\\0&1&0\\0&0&1\end{bmatrix}\begin{bmatrix}12\\10\\1\end{bmatrix} = \begin{bmatrix}2\\10\\1\end{bmatrix}$

so $B' = (2,10)$.

Graph

 y
10 |  B'(2,10)         |            B(12,10)
   |                   |
   |                   |
 3 |  A'(5,3)          |   A(9,3)
   +-------------------+-------------------- x
                      x = 7  (mirror line)

The original segment joins $A(9,3)$ and $B(12,10)$ to the right of the mirror line $x = 7$; the reflected segment joins $A'(5,3)$ and $B'(2,10)$ to the left. Each point and its image are at equal distances from the line ($A$: 2 units right, $A'$: 2 units left; $B$: 5 units right, $B'$: 5 units left), and the length of the segment is unchanged.

SVGA resolution is taken as $800 \times 600$ pixels. 24-bit true colour needs $24/8 = 3$ bytes per pixel.

Memory per frame

$800 \times 600 \times 3 = 1{,}440{,}000 \text{ bytes}$

Number of frames. Duration is $5 \times 60 = 300$ s, at 30 frames per second:

$300 \times 30 = 9{,}000 \text{ frames}$

Total memory

$1{,}440{,}000 \times 9{,}000 = 12{,}960{,}000{,}000 \text{ bytes}$

In binary units:

$\frac{12{,}960{,}000{,}000}{1024^2} \approx 12{,}359.6 \text{ MB} \approx 12.07 \text{ GB}$

So about 12.96 x 10^9 bytes (about 12.07 GB) is needed for the uncompressed video.

Window. A window is a rectangular area of the world-coordinate scene that is selected for display. Only what lies inside the window is shown.

Viewport. A viewport is the rectangular area of the display device (screen) in device/normalised coordinates into which the contents of the window are mapped.

Viewing transformation (window-to-viewport transformation). It is the mapping of world-coordinate points of the window to the viewport, keeping the relative position of every point. For a point $(x_w, y_w)$ in a window $[xw_{min}, xw_{max}] \times [yw_{min}, yw_{max}]$ and viewport $[xv_{min}, xv_{max}] \times [yv_{min}, yv_{max}]$:

$x_v = xv_{min} + (x_w - xw_{min})\,s_x,\quad y_v = yv_{min} + (y_w - yw_{min})\,s_y$

$s_x = \frac{xv_{max} - xv_{min}}{xw_{max} - xw_{min}},\quad s_y = \frac{yv_{max} - yv_{min}}{yw_{max} - yw_{min}}$

It is carried out by translating the window to the origin, scaling to the viewport size, and translating to the viewport position.

Cohen-Sutherland clipping. The window has $x_{min} = 20$, $x_{max} = 90$, $y_{min} = 20$, $y_{max} = 70$ (from A(20,20), B(90,20), C(90,70), D(20,70)).

The 4-bit region code is $b_4b_3b_2b_1$ = Top, Bottom, Right, Left: bit 1 = 1 if $x < x_{min}$, bit 2 = 1 if $x > x_{max}$, bit 3 = 1 if $y < y_{min}$, bit 4 = 1 if $y > y_{max}$.

Region codes.

• $P(10, 30)$: $x = 10 < 20$ so Left = 1; $y = 30$ is between 20 and 70. Code $= 0001$.
• $Q(80, 90)$: $x = 80$ is inside; $y = 90 > 70$ so Top = 1. Code $= 1000$.

Logical AND of the codes $= 0001 \,\&\, 1000 = 0000$, and the codes are not both 0000, so the line is neither trivially accepted nor rejected. It must be clipped.

Slope: $m = \dfrac{90 - 30}{80 - 10} = \dfrac{60}{70} = \dfrac{6}{7}$.

Clip P (left boundary, $x = 20$):

$y = y_P + m(20 - x_P) = 30 + \frac{6}{7}(10) = 38.57$

New point $P'(20, 38.57)$. Its code is $0000$ (inside).

Clip Q (top boundary, $y = 70$):

$x = x_Q + \frac{1}{m}(70 - y_Q) = 80 + \frac{7}{6}(70 - 90) = 80 - 23.33 = 56.67$

New point $Q'(56.67, 70)$. Its code is $0000$.

Both end points now have code 0000, so the clipped line segment to be displayed is from $P'(20, 38.57)$ to $Q'(56.67, 70)$.

Two disadvantages of the BSP tree method.

1. Constructing the BSP tree is expensive (preprocessing), and it needs to be rebuilt when objects move, so it is not suited to dynamic scenes.
2. Splitting polygons that cross a partitioning plane increases the number of polygons (and the size of the tree), and the tree can become unbalanced; the number of fragments is hard to predict.

(Also: the tree depends on the choice of splitting planes, and the memory use is high.)

Painter's algorithm vs A-buffer algorithm.

Both are hidden surface methods. The painter's algorithm is simple and uses little memory, while the A-buffer gives more accurate results, with transparency and anti-aliasing, at a higher memory cost.

Architecture of a raster scan display. In a raster scan system the screen is a matrix of pixels. The picture is stored in a frame buffer (refresh buffer) as intensity values for each pixel, and the beam sweeps the screen row by row (scan line by scan line) from top to bottom, refreshing the display about 60 times a second.

Components:

• CPU and system memory: run the application program and the graphics package, and place the picture definition in system memory.
• Video controller (display controller): reads the frame buffer, computing the x and y addresses using registers, and controls the horizontal and vertical deflection of the electron beam through the x register (for the column) and y register (for the scan line).
• Frame buffer: a memory area (often a dedicated video RAM) which stores colour/intensity values for every pixel; for $n$ bits per pixel it can display $2^n$ colours, with memory size $= \text{width} \times \text{height} \times n$ bits.
• Display processor (graphics controller): an optional processor that does scan conversion of graphics primitives, fill and other operations, relieving the CPU.
• Look-up table (colour LUT) and digital-to-analog converters: convert pixel values to analog voltages for the guns of the monitor.
• Monitor (CRT/LCD) shows the image, with the beam sweeping each line left to right with horizontal retrace after each line and vertical retrace after each frame.

 CPU <--> System memory <--> Frame buffer <--> Video controller --> Monitor
                  |                                ^
                  +---- Display processor ---------+

Solid-modeling representations.

1. Sweep representation. A solid is built by moving a 2D shape (profile) along a path.

• Translational sweep: a 2D shape swept along a straight line gives a prism or cylinder (extrusion).
• Rotational sweep: a 2D shape rotated about an axis gives a solid of revolution (sphere, cone, vase).
• General sweeps follow a curved path with a changing cross-section. It is simple and easy for symmetric shapes but cannot describe all objects.

2. Octree representation. A cube enclosing the object is recursively subdivided into eight octants. Each octant is marked full (inside the object), empty (outside), or partially filled, and the partial ones are subdivided further until a resolution limit. The data is stored as a tree where each node has eight children. It is a space-partitioning method suited for volume data, medical imaging, and set operations (union, intersection) are easy, but it needs much memory for high resolution and it is approximate.

3. Boundary representation (B-rep). A solid is described by its bounding surfaces: faces, edges and vertices, with the topology (which faces share which edges and vertices) and geometry (equations of surfaces and curves). Polygon meshes are an example. It supports rendering directly and gives exact surface information, and obeys Euler's formula $V - E + F = 2$ for simple polyhedra. It uses more storage, and checking validity is complex.

Basic colour models.

1. RGB (additive model): colours are produced by mixing Red, Green and Blue light; (0,0,0) is black and (1,1,1) is white. Used by monitors, TVs and cameras.
2. CMY / CMYK (subtractive model): Cyan, Magenta, Yellow (plus Black K) pigments subtract light from white; $C = 1 - R$, $M = 1 - G$, $Y = 1 - B$. Used in printing.
3. HSV (HSB): Hue, Saturation, Value (brightness); intuitive for the user choosing colours.
4. HLS (HSL): Hue, Lightness, Saturation.
5. YIQ: luminance (Y) and chrominance (I, Q) used in NTSC colour TV broadcasting, which keeps compatibility with black and white sets.
6. CIE XYZ: device-independent standard model based on human vision.

OpenGL commands.

Drawing a pixel (point):

glColor3f(1.0, 0.0, 0.0);     // set colour red
glPointSize(4.0);             // size of the point
glBegin(GL_POINTS);
    glVertex2i(100, 50);      // pixel at (100, 50)
glEnd();

(A raw pixel block can also be drawn with glDrawPixels(width, height, GL_RGB, GL_UNSIGNED_BYTE, data).)

Drawing a polygon:

glColor3f(0.0, 1.0, 0.0);
glBegin(GL_POLYGON);
    glVertex2f(50.0, 50.0);
    glVertex2f(150.0, 50.0);
    glVertex2f(100.0, 120.0);
glEnd();

glBegin(mode) starts a primitive (GL_POINTS, GL_LINES, GL_LINE_LOOP, GL_POLYGON, GL_TRIANGLES, GL_QUADS), glVertex*() gives its vertices, and glEnd() ends it; glFlush() forces the drawing to be shown.

Bresenham's line algorithm for the end points $(x_1, y_1) = (1, 1)$ and $(x_2, y_2) = (8, 5)$.

$\Delta x = 8 - 1 = 7$, $\Delta y = 5 - 1 = 4$. Slope $m = 4/7 < 1$, so $x$ is incremented by 1 at each step.

Initial decision parameter:

$p_0 = 2\Delta y - \Delta x = 8 - 7 = 1$

Rules:

• If $p_k < 0$: next point $(x_k + 1, y_k)$ and $p_{k+1} = p_k + 2\Delta y = p_k + 8$.
• 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 - 6$.

Starting point $(1, 1)$.

Pixels plotted: $(1,1), (2,2), (3,2), (4,3), (5,3), (6,4), (7,4), (8,5)$. The last point matches the end point $(8, 5)$, which confirms the trace.

Use homogeneous coordinates, so a point $P = (x, y, z)$ is written $(x, y, z, 1)$ and each transformation is a $4 \times 4$ matrix.

3D translation. Translating a point by $(t_x, t_y, t_z)$ along the axes gives

$x' = x + t_x,\quad y' = y + t_y,\quad z' = z + t_z$

In matrix form $P' = T\cdot P$:

$\begin{bmatrix} x' \\ y' \\ z' \\ 1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 & t_x \\ 0 & 1 & 0 & t_y \\ 0 & 0 & 1 & t_z \\ 0 & 0 & 0 & 1 \end{bmatrix}\begin{bmatrix} x \\ y \\ z \\ 1 \end{bmatrix}$

The inverse translation uses $-t_x, -t_y, -t_z$.

3D rotation. The rotation is by angle $\theta$ about a coordinate axis (positive angle is counter-clockwise looking from the positive axis towards the origin).

Rotation about the z-axis. The $z$ coordinate is unchanged, and $x, y$ rotate as in 2D. A point at radius $r$ and angle $\phi$: $x = r\cos\phi$, $y = r\sin\phi$. After rotating by $\theta$:

$x' = r\cos(\phi + \theta) = r\cos\phi\cos\theta - r\sin\phi\sin\theta = x\cos\theta - y\sin\theta$

$y' = r\sin(\phi + \theta) = r\cos\phi\sin\theta + r\sin\phi\cos\theta = x\sin\theta + y\cos\theta$

$z' = z$

$R_z(\theta) = \begin{bmatrix} \cos\theta & -\sin\theta & 0 & 0 \\ \sin\theta & \cos\theta & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}$

Rotation about the x-axis. By cyclic permutation $x \to y \to z \to x$ of the z-axis result:

$y' = y\cos\theta - z\sin\theta,\quad z' = y\sin\theta + z\cos\theta,\quad x' = x$

$R_x(\theta) = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & \cos\theta & -\sin\theta & 0 \\ 0 & \sin\theta & \cos\theta & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}$

Rotation about the y-axis. Cyclic permutation again ($z' = z\cos\theta - x\sin\theta$, $x' = z\sin\theta + x\cos\theta$, $y' = y$):

$R_y(\theta) = \begin{bmatrix} \cos\theta & 0 & \sin\theta & 0 \\ 0 & 1 & 0 & 0 \\ -\sin\theta & 0 & \cos\theta & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}$

The inverse of a rotation is its transpose, $R^{-1}(\theta) = R(-\theta) = R^T(\theta)$. For rotation about an axis parallel to a coordinate axis, translate the object so the axis passes through the origin, rotate, then translate back: $T(p)\,R(\theta)\,T(-p)$.

Wireframe representation. In a wireframe model an object is represented only by its edges (lines and curves) and vertices, with no surface information. Purpose:

• It is the simplest and fastest representation, with small storage, for quick display and previewing.
• It lets the designer see the overall shape and the internal structure, since all edges (even hidden ones) are visible, so it is used in CAD for design interaction.
• It is used for interactive manipulation such as rotation and checking positions, because it needs little computing.
• It is a starting point for generating surface and solid models.

Its weakness is ambiguity (the same wireframe can be read as different solids), no hidden-line removal, and no volume or surface properties.

Boundary representation. The solid is described by its surface boundary, a set of surface elements (faces, edges and vertices) with their connectivity. The polygon mesh, with vertex, edge and face tables, is typical. The inside is implied by the surface. The representation is exact for polyhedra and renders quickly, but needs a lot of storage for curved objects, and the geometry and topology must be consistent (Euler's formula $V - E + F = 2$).

Space partitioning representation. The 3D space containing the object is divided into non-overlapping solid cells, usually cubes, and the object is described by the cells it occupies. Methods:

• Octree: the cube is recursively divided into 8 octants until each is full, empty, or at the resolution limit.
• BSP tree: space is recursively split by planes into two half-spaces.
• Voxel (uniform grid) / cell decomposition.

It makes volume-related operations, such as union, intersection and mass properties, easy and suits medical imaging, but it is approximate, and needs much memory for fine detail.

Midpoint ellipse algorithm with centre $(0, 0)$, $r_x = 8$, $r_y = 6$. $r_x^2 = 64$, $r_y^2 = 36$, $2r_y^2 = 72$, $2r_x^2 = 128$. Only the first quadrant is computed; the other quadrants follow by symmetry.

Region 1 (slope magnitude < 1). Start at $(x_0, y_0) = (0, r_y) = (0, 6)$.

$p1_0 = r_y^2 - r_x^2 r_y + \tfrac{1}{4}r_x^2 = 36 - 384 + 16 = -332$

Steps: if $p1_k < 0$, next point $(x_k + 1, y_k)$ and $p1_{k+1} = p1_k + 2r_y^2 x_{k+1} + r_y^2$. Otherwise next point $(x_k + 1, y_k - 1)$ and $p1_{k+1} = p1_k + 2r_y^2 x_{k+1} - 2r_x^2 y_{k+1} + r_y^2$. Continue while $2r_y^2 x < 2r_x^2 y$.

At $(7, 3)$: $504 \ge 384$, so move to region 2.

Region 2. Start from the last point $(7, 3)$:

$p2_0 = r_y^2\left(x_0 + \tfrac12\right)^2 + r_x^2(y_0 - 1)^2 - r_x^2r_y^2 = 36(56.25) + 64(4) - 2304 = 2025 + 256 - 2304 = -23$

Steps: if $p2_k > 0$, next point $(x_k, y_k - 1)$ and $p2_{k+1} = p2_k - 2r_x^2 y_{k+1} + r_x^2$. Otherwise next point $(x_k + 1, y_k - 1)$ and $p2_{k+1} = p2_k + 2r_y^2 x_{k+1} - 2r_x^2 y_{k+1} + r_x^2$. Continue until $y = 0$.

Points in the first quadrant: $(0,6), (1,6), (2,6), (3,6), (4,5), (5,5), (6,4), (7,3), (8,2), (8,1), (8,0)$.

The points in the other quadrants are $(\pm x, \pm y)$. The plot is a smooth ellipse passing through $(0, \pm 6)$ and $(\pm 8, 0)$.

Clipping is the process of identifying the portions of a picture that lie inside (or outside) a specified region, called the clip window, and discarding the rest before display. It is applied to points, lines, polygons, curves and text, and saves the time of scan-converting objects that will never be seen.

Cubic spline interpolation

A spline is a piecewise polynomial curve. A cubic spline passes through a given set of control points (it interpolates them) and is built from cubic segments

$P_k(u) = a_k u^3 + b_k u^2 + c_k u + d_k, \quad 0 \le u \le 1$

For $n+1$ control points there are $n$ segments, so $4n$ unknown coefficients are needed. The conditions are:

• Each segment passes through its two end points ($2n$ conditions).
• First-derivative (tangent) continuity at the $n-1$ interior joints, $P_k'(1)=P_{k+1}'(0)$ ($n-1$ conditions).
• Second-derivative (curvature) continuity at the interior joints, $P_k''(1)=P_{k+1}''(0)$ ($n-1$ conditions).

This gives $4n-2$ equations. The two remaining conditions are supplied by boundary conditions, for example:

• Natural spline: the second derivative is zero at both end points.
• Clamped spline: the end tangents are specified.

Properties:

• The curve is $C^2$ continuous, so it looks very smooth.
• It passes exactly through all control points.
• It has global control: changing one control point changes the whole curve, since the equations form one linear system.
• Used in animation paths, curve fitting and font design. Related forms are the Hermite, cardinal and Kochanek-Bartels splines, which give local control.

Shadow detection in computer graphics

A point is in shadow if it cannot "see" the light source, so shadow detection is a visibility problem solved from the light's point of view. Common methods are:

1. Shadow rays (ray tracing): from each visible surface point, cast a ray toward every light source. If the ray hits any opaque object before reaching the light, the point is in shadow and that light's diffuse and specular contribution is omitted. This is simple and accurate but costly.
2. Shadow mapping (z-buffer method): render the scene from the light's position and store the depth in a shadow map. While rendering from the camera, transform each point into light space and compare its depth with the stored value. If the point is farther than the stored depth, it is in shadow.
3. Shadow volumes: each occluder and light define a volume of space that lies in shadow. Counting entries and exits of these volumes (stencil buffer) along the view ray tells whether a point is inside a shadow.
4. Projected (planar) shadows: polygons are projected onto a ground plane from the light position and drawn in a dark colour.

Challenges in computing a light model

• Real light interaction (inter-reflection, refraction, scattering) is very complex, so models use approximations.
• Global illumination is computationally expensive; the cost grows with the number of lights and objects.
• Accurate material properties (reflectance, transparency, roughness) are hard to measure and represent.
• Soft shadows (penumbra) from area lights are hard to compute, whereas point lights give only hard shadows.
• Aliasing artefacts appear in shadow maps because of limited resolution.
• Real-time rendering demands a trade-off between realism and speed.
• Colour and intensity representation is limited by the display's range of intensities.

Applications of virtual reality (VR)

• Games and entertainment (immersive games, virtual theatre)
• Education and training (flight simulators, surgery simulation, military training)
• Medicine (therapy, rehabilitation, tele-surgery)
• Architecture and engineering (virtual walk-through of a building, product design)
• Scientific visualisation (molecules, astronomy)
• Virtual tourism, museums and heritage sites
• Marketing and virtual shopping

Navigation techniques

Navigation is how the user moves through the virtual world.

• Physical movement (tracking): the user's real walking or head movement, tracked by sensors, is mapped to movement in the virtual world. It is the most natural, but limited by the size of the tracked space.
• Steering (gaze or hand directed): the user points or looks in a direction and moves that way using a controller or joystick. It is simple and covers large spaces.
• Teleportation: the user selects a target point and is instantly moved there. It reduces motion sickness.
• Walking in place, treadmills: simulate walking while the user stays in one location.
• Map or world-in-miniature: the user picks a location on a small map and is transported there.

Manipulation interfaces

Manipulation means selecting, grabbing, moving and rotating virtual objects.

• Data gloves and hand tracking: direct, natural grasping with the fingers, which gives intuitive control.
• 3D mouse, wand or controllers: a ray is cast from the controller to select an object, which is then moved with a button. Useful for distant objects.
• Haptic devices: provide force feedback so the user feels the object.
• Voice and gesture commands: hands-free interaction.

Justification: the best technique depends on the task. Natural techniques give a greater sense of presence but suffer from limited tracking space and hardware cost, while indirect techniques (teleport, ray-casting) cover large environments with less fatigue and reduce motion sickness. Most systems therefore combine them.

Two colour commands in OpenGL

1. glColor3f(r, g, b) sets the current drawing colour, with each component in the range 0.0 to 1.0. Example: glColor3f(1.0, 0.0, 0.0); selects red. The variant glColor4f also takes an alpha value.
2. glClearColor(r, g, b, a) sets the colour used to clear the colour buffer (the background), used with glClear(GL_COLOR_BUFFER_BIT). Example: glClearColor(0.0, 0.0, 0.0, 1.0);.

Hermite curve

A Hermite curve is a cubic polynomial curve defined by its two end points and the tangent vectors at those end points. Given $P_0$, $P_1$ (end points) and $R_0$, $R_1$ (tangents at $P_0$ and $P_1$), the curve is

$P(u) = a u^3 + b u^2 + c u + d, \quad 0 \le u \le 1$

with the conditions $P(0)=P_0$, $P(1)=P_1$, $P'(0)=R_0$, $P'(1)=R_1$. Solving for the coefficients gives

$P(u) = (2u^3-3u^2+1)P_0 + (-2u^3+3u^2)P_1 + (u^3-2u^2+u)R_0 + (u^3-u^2)R_1$

In matrix form,

$P(u) = \begin{bmatrix}u^3 & u^2 & u & 1\end{bmatrix}\begin{bmatrix}2 & -2 & 1 & 1\\ -3 & 3 & -2 & -1\\ 0 & 0 & 1 & 0\\ 1 & 0 & 0 & 0\end{bmatrix}\begin{bmatrix}P_0\\P_1\\R_0\\R_1\end{bmatrix}$

The four polynomials are the Hermite blending functions. Properties:

• The curve passes through $P_0$ and $P_1$.
• The direction and length of the tangent vectors control the shape: a longer tangent makes the curve follow its direction for longer.
• Adjacent segments are $C^1$ continuous if the end tangent of one equals the start tangent of the next.
• It gives local control, and is used in animation and font design.

Differences between DDA and Bresenham's line algorithm

DDA algorithm for end points (2, 2) and (9, 2)

Algorithm:

1. $dx = x_2-x_1$, $dy = y_2-y_1$.
2. $steps = \max(|dx|,|dy|)$.
3. $x_{inc} = dx/steps$, $y_{inc} = dy/steps$.
4. Starting at $(x_1,y_1)$, repeat $steps$ times: $x \leftarrow x + x_{inc}$, $y \leftarrow y + y_{inc}$, and plot $(\text{round}(x),\text{round}(y))$.

Here $dx = 9-2 = 7$, $dy = 2-2 = 0$, so $steps = 7$, $x_{inc} = 1$, $y_{inc} = 0$ (a horizontal line).

The line is drawn through the pixels (2,2), (3,2), (4,2), (5,2), (6,2), (7,2), (8,2), (9,2).

Polygon tables

A 3D object is described by a set of polygon surfaces (a polygon mesh). The data are organised in polygon tables, in two groups:

• Geometric tables store the geometry:
  • Vertex table: coordinates of every vertex.
  • Edge table: for each edge, pointers to its two end vertices.
  • Surface (polygon) table: for each polygon, pointers to the edges forming it.
• Attribute tables store properties such as colour, transparency, reflectivity and texture.

Example: the vertex table holds $V_1(x_1,y_1,z_1),\dots$; the edge table holds $E_1: V_1,V_2$; $E_2: V_2,V_3$; and the surface table holds $S_1: E_1,E_2,E_3$. This avoids duplicating shared vertices, makes consistency checks easy (every edge belongs to at least one polygon), and gives quick access for rendering. The plane equation $Ax+By+Cz+D=0$ of each polygon is also stored; the normal $(A,B,C)$ is used for shading and visibility tests.

Representations of curves

1. Bezier curve: defined by $n+1$ control points $P_i$:

$P(u)=\sum_{i=0}^{n} P_i \binom{n}{i} u^i (1-u)^{n-i}, \quad 0\le u\le1$

It interpolates the first and last control points only, lies inside the convex hull of the control polygon, and has global control. A cubic Bezier ($n=3$) is widely used.

2. B-spline curve: a piecewise polynomial of degree $d$:

$P(u)=\sum_{i=0}^{n} P_i B_{i,d}(u)$

The blending functions $B_{i,d}$ are non-zero only over a limited range, giving local control, and the degree is independent of the number of control points.

3. Hermite curve: a cubic defined by two end points and the tangents at them; it gives $C^1$ continuity between segments.

4. Cubic spline (interpolating): a piecewise cubic through all the given points with $C^2$ continuity.

Realism in human perception

Realism is the degree to which a computer-generated image appears to the viewer as a real scene. It depends on how well the image reproduces the cues the human visual system uses to perceive the world: perspective (size shrinking with distance), hidden surface removal, shading and light-surface interaction, shadows, texture, colour, transparency and reflection, motion parallax and stereo depth. The more of these cues that are modelled, the more realistic the image feels.

Rendering and image synthesis

• Image synthesis is the overall process of creating a 2D image from a description of a 3D scene (models, materials, lights, camera). It includes modelling, viewing transformation, hidden surface removal, lighting and final display.
• Rendering is the specific stage of that process that computes the colour of each pixel: visibility determination, illumination and shading, texturing, and so on.

So image synthesis is the broader pipeline from scene description to picture, and rendering is its computational core that produces the final shaded pixels.

Polygon rendering methods

1. Constant (flat) shading: one intensity is computed for the entire polygon using its normal and a single illumination calculation, and the whole polygon is filled with that intensity. It is fast, but the individual facets are visible and the surface looks faceted. It is acceptable only for small polygons or distant light sources.

2. Gouraud shading (intensity interpolation):

   • Compute the unit normal at each vertex by averaging the normals of the polygons sharing it.
   • Apply the illumination model at each vertex to get vertex intensities.
   • Linearly interpolate the intensities along the edges, then along each scan line across the polygon.

   It removes the intensity discontinuities between facets and gives a smooth look, but can miss specular highlights and produce Mach bands.

3. Phong shading (normal interpolation): interpolate the vertex normals across the polygon and evaluate the illumination model at every pixel. It gives accurate highlights and smoother shading than Gouraud, at a higher computational cost.

Vector and raster graphics

Translation moves every point by $(t_x, t_y)$:

$x' = x + t_x, \quad y' = y + t_y$

Here $t_x = 2$, $t_y = 3$. In homogeneous coordinates,

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

• $A(0,0) \to A'(0+2,\,0+3) = A'(2,3)$
• $B(5,0) \to B'(5+2,\,0+3) = B'(7,3)$
• $C(5,5) \to C'(5+2,\,5+3) = C'(7,8)$

The translated triangle has vertices $A'(2,3)$, $B'(7,3)$, $C'(7,8)$. Its shape and size are unchanged; only its position has moved.

Projection maps 3D points onto a 2D view plane. There are two main classes: parallel and perspective. Orthographic projection is a special case of parallel projection.

Parallel projection

Projectors (projection lines) are parallel to each other. Object size is preserved regardless of distance, and parallel lines stay parallel. It has two types:

• Orthographic: the projectors are perpendicular to the view plane (front, top and side views). It gives true dimensions and is used in engineering drawing, but shows only one face at a time.
• Oblique: the projectors are parallel but not perpendicular to the plane (cavalier, cabinet), showing the front face true-shaped along with some depth.

Perspective projection

Projectors converge at a single point, the centre of projection. Distant objects appear smaller (perspective foreshortening) and parallel lines not parallel to the view plane converge at vanishing points. It looks realistic, like a camera or the eye, but does not preserve sizes or angles.

BSP (Binary Space Partitioning) tree

A BSP tree represents a scene by recursively dividing space with planes (lines in 2D). Each polygon's supporting plane splits the remaining polygons into two sets: those in front of the plane and those behind it. Polygons crossing the plane are split into two pieces.

Construction:

1. Pick a polygon and use its plane as the root partition.
2. Classify every other polygon as in front, behind, or spanning (split the spanning ones along the plane).
3. Recursively build the front subtree from the front set and the back subtree from the back set.
4. Stop when a set holds one polygon or none.

Each node therefore holds a polygon (and its plane), with a front child and a back child.

Example (2D): let line segments $A$, $B$, $C$ be given with $B$ and $C$ in front of $A$'s line and $D$ behind it. Choose $A$ as the root. Its front set is $\{B, C\}$ and its back set is $\{D\}$. Within the front set, choose $B$ as the node; if $C$ is in front of $B$, then $C$ is the front child of $B$.

        A
      /   \
     B     D
      \
       C

Use in display: to draw back to front for a viewpoint $E$, traverse recursively. At each node, if $E$ is in front of the node's plane, draw the back subtree, then the node's polygon, then the front subtree; if $E$ is behind, reverse this. Once built, the tree can be traversed for any viewpoint, so it is useful in walk-throughs and games, and it supports hidden surface removal and visibility ordering without a z-buffer.

Role of ray tracing in visible surface detection

In ray tracing, a ray is cast from the viewpoint through each pixel of the view plane into the scene. The ray is intersected with all objects, and the intersection point nearest to the viewer (smallest positive $t$) gives the visible surface for that pixel. This resolves visibility directly, and it works for curved surfaces too, not just polygons. The same method also traces secondary rays: reflection, refraction and shadow rays, so it gives realistic reflections, transparency and shadows along with hidden surface removal. Its drawbacks are the cost of testing every ray against every object and the need for acceleration structures.

Scan line algorithm and back-face detection

Back-face detection and the scan-line method are two different steps that work together:

1. Back-face detection: a polygon with plane equation $Ax+By+Cz+D=0$ and outward normal $N=(A,B,C)$ is a back face if $N\cdot V > 0$, where $V$ is the viewing direction (from the viewer toward the object); with the viewer looking along $-z$, this is the test $C<0$. Back faces are removed, which eliminates roughly half the polygons.
2. Scan-line processing of the remaining (front-facing) polygons: for each scan line,
   • Maintain an edge table (all edges, sorted by $y$) and an active edge list for the current scan line.
   • Find the spans where the scan line crosses polygons.
   • Where only one polygon covers a span, fill it with that polygon's colour.
   • Where several overlap, compare depths $z=(-Ax-By-D)/C$ at the span and display the nearest.
   • Move to the next scan line, updating $x$ and $z$ incrementally.

Thus removing back faces first reduces the polygons the scan-line algorithm must handle.

How virtual reality differs from the real world

• VR is a computer-generated, simulated environment; the real world is physical.
• In VR, the laws of physics, time and space can be changed or ignored (flying, scaling, teleporting). The real world follows fixed natural laws.
• VR is experienced through devices such as headsets, gloves and trackers, whereas the real world is perceived directly with the senses.
• VR is limited by the resolution, latency and field of view of the hardware, and sensory feedback (touch, smell) is incomplete.
• VR is safe and repeatable (training for dangerous situations) and can be reset, but the real world is not.
• VR requires hardware and software cost; reality is free.

Components of a VR system

1. Input devices: trackers (head, hand, body), data gloves, controllers, 3D mouse, microphones. They capture the user's position and actions.
2. Output / display devices: head-mounted display (HMD), CAVE projection systems, stereo displays for visuals; speakers/3D audio; haptic devices for touch and force feedback.
3. Computer / graphics engine: the processing unit (CPU, GPU) which renders the scene in real time at a high frame rate, to avoid lag and motion sickness.
4. VR software and database: the world model (3D objects, textures, physics, behaviour) and the software (VR engine, APIs) managing simulation, interaction and collision detection.
5. User interaction interface: navigation and manipulation techniques linking the user to the virtual world.

Procedure to draw a line in OpenGL

#include <GL/glut.h>

void display(void)
{
    glClear(GL_COLOR_BUFFER_BIT);     // clear the window
    glColor3f(1.0, 0.0, 0.0);         // red colour
    glLineWidth(2.0);                 // line width
    glBegin(GL_LINES);
        glVertex2f(-0.5, -0.5);       // start point
        glVertex2f( 0.5,  0.5);       // end point
    glEnd();
    glFlush();
}

int main(int argc, char **argv)
{
    glutInit(&argc, argv);
    glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);
    glutInitWindowSize(400, 400);
    glutCreateWindow("Line");
    glClearColor(1.0, 1.0, 1.0, 1.0); // white background
    glutDisplayFunc(display);
    glutMainLoop();
    return 0;
}

glBegin(GL_LINES) treats each pair of glVertex calls as the end points of one line; GL_LINE_STRIP and GL_LINE_LOOP draw connected lines.

Painter's algorithm

This is a depth-sorting (object-space) hidden surface method that imitates a painter who paints the distant parts of a scene first and the nearer parts over them.

Steps:

1. Sort all polygons in decreasing order of depth (greatest $z$ distance from the viewer first), usually by their farthest vertex or centroid.
2. Resolve any ambiguities where depth ranges overlap (test whether polygons can be reordered, or split a polygon).
3. Scan-convert (paint) the polygons in that order, so nearer polygons overwrite farther ones.

Advantages: simple, and no depth buffer is needed. Disadvantages: sorting takes time; it fails or needs polygon splitting for cyclically overlapping or intersecting polygons; and every polygon is painted even if hidden, which wastes work.

Liang-Barsky line clipping

The line is written parametrically as $x = x_1 + u\,\Delta x$, $y = y_1 + u\,\Delta y$, $0\le u\le1$, and the inside conditions $x_{min}\le x\le x_{max}$, $y_{min}\le y\le y_{max}$ become $p_k u \le q_k$ with

$p_1=-\Delta x,\ q_1=x_1-x_{min};\quad p_2=\Delta x,\ q_2=x_{max}-x_1;\quad p_3=-\Delta y,\ q_3=y_1-y_{min};\quad p_4=\Delta y,\ q_4=y_{max}-y_1$

For $p_k<0$ the line enters the window at $u=q_k/p_k$; for $p_k>0$ it leaves at $u=q_k/p_k$. Then $u_1=\max(0,\text{entering values})$ and $u_2=\min(1,\text{leaving values})$.

Given: window $x_{min}=0$, $x_{max}=10$, $y_{min}=0$, $y_{max}=10$; $X(5,3)$, $Y(15,9)$.

$\Delta x = 15-5 = 10$, $\Delta y = 9-3 = 6$.

$u_1=\max(0,-0.5,-0.5)=0$

$u_2=\min(1,0.5,1.167)=0.5$

Since $u_1<u_2$, part of the line is visible.

New end points:

• $u_1=0$: $(5,3)$
• $u_2=0.5$: $x=5+0.5\times10=10$, $y=3+0.5\times6=6$, giving $(10,6)$

The clipped line runs from $(5,3)$ to $(10,6)$.

Blobby objects

Blobby objects (metaballs, soft objects) are shapes that do not have a fixed, rigid surface but show a smooth, fluid distortion when they come near each other, like water droplets merging, molecular structures or muscle shapes. Each object is defined by a density (field) function that falls off with distance from its centre, for example the Gaussian

$f(r)=b\,e^{-a r^2}$

and the total field is the sum over all the blobs. The surface is the set of points where the total field equals a threshold:

$\sum_k b_k e^{-a_k r_k^2} - T = 0$

When two blobs come close, their fields add and the surfaces blend smoothly into a single shape. Parameters $a$, $b$ and $T$ control the size and smoothness.

Basic illumination models

An illumination model computes the intensity of light reflected from a surface point. The components are:

1. Ambient light: constant background illumination from the environment, $I = k_a I_a$.
2. Diffuse reflection (Lambert's cosine law): light scattered equally in all directions from a dull surface; it depends on the angle $\theta$ between the surface normal $N$ and the light direction $L$:

$I_{diff}=k_d I_l \cos\theta = k_d I_l (N\cdot L)$

3. Specular reflection: the bright highlight on shiny surfaces, depending on the angle $\alpha$ between the reflected direction $R$ and the viewing direction $V$ (Phong model):

$I_{spec}=k_s I_l (V\cdot R)^{n_s}$

where $n_s$ is the shininess exponent.

The Phong illumination model adds them:

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

Other models include the Blinn-Phong model (uses the halfway vector $H$) and the global models (ray tracing, radiosity).