Computer Graphics

The Cohen-Sutherland algorithm clips a line against a rectangular window quickly by using region codes.

Region codes. The plane is divided into 9 regions by the window edges. Each endpoint gets a 4-bit outcode (bits: top, bottom, right, left), where a bit is 1 if the point is: above $y_{max}$, below $y_{min}$, right of $x_{max}$, left of $x_{min}$. A point inside the window has code 0000.

Algorithm

1. Compute outcodes for both endpoints $P_1$ and $P_2$.
2. If both codes are 0000, the line is completely inside: accept it.
3. If the bitwise AND of the two codes is not 0000, both endpoints lie on the outside of the same edge: reject the line.
4. Otherwise the line is partially inside. Pick an endpoint with a nonzero code, find the intersection with the window edge indicated by a 1 bit, and replace the endpoint by the intersection:
   • left/right: $x = x_{min}$ or $x_{max}$, $y = y_1 + m(x - x_1)$
   • top/bottom: $y = y_{max}$ or $y_{min}$, $x = x_1 + (y - y_1)/m$ where $m = (y_2 - y_1)/(x_2 - x_1)$.
5. Compute the new outcode and repeat from step 2 until the line is accepted or rejected.

It is efficient when most lines are clearly inside or outside, but a line may need up to four intersection calculations.

Cohen-Sutherland line clipping quickly accepts or rejects lines against a rectangular window ($x_{min},x_{max},y_{min},y_{max}$) using 4-bit region codes.

Region code (bit = 1 if true): bit 1 = above ($y>y_{max}$), bit 2 = below ($y<y_{min}$), bit 3 = right ($x>x_{max}$), bit 4 = left ($x<x_{min}$). The window itself is 0000.

Algorithm

1. Compute the codes of both end points.
2. If both are 0000: trivially accept (line inside).
3. If the bitwise AND of the codes is non-zero: trivially reject (both on the outside of the same edge).
4. Otherwise, pick an end point outside the window, find the intersection with a window edge it crosses, replace that end point by the intersection, recompute its code and repeat.

Intersection: with slope $m=(y_2-y_1)/(x_2-x_1)$: left/right edge $y = y_1 + m(x_{edge}-x_1)$; top/bottom edge $x = x_1 + (y_{edge}-y_1)/m$.

Example: Window $x:10..20$, $y:10..20$. Line $P_1(5,15)$ to $P_2(15,25)$. Code of $P_1$ = 0001 (left); $P_2$ = 1000 (above). AND = 0000, so not rejected; $m = 1$. Clip $P_1$ at $x=10$: $y=15+1(10-5)=20$, so $P_1'=(10,20)$, code 0000. Clip $P_2$ at $y=20$: $x = 15 + (20-25)/1 = 10$, giving $(10,20)$. Both ends are the same point, so the line only touches the corner of the window; in general the clipped segment is drawn between the two new inside points.

Ambient light: light of uniform intensity that reaches an object after repeated reflections from the surroundings; it has no direction. Every surface receives it equally, giving the basic brightness of shadowed areas: $I_{amb} = k_a I_a$ where $k_a$ is the ambient reflection coefficient and $I_a$ the ambient intensity. Example: the faint illumination inside a room away from the lamp.

Diffuse reflection: light from a point source is scattered equally in all directions by a dull, rough surface (e.g. chalk, matte paint). Brightness depends on the angle $\theta$ between the surface normal $N$ and the light direction $L$ (Lambert's cosine law) but not on the viewer: $I_{diff} = k_d I_l \cos\theta = k_d I_l (N\cdot L)$ Example: a matte wall looks equally bright from any viewpoint but darker as it turns away from the lamp.

Specular reflection: mirror-like reflection from shiny surfaces that produces a bright highlight whose position depends on the viewer. Phong model: $I_{spec} = k_s I_l (V\cdot R)^{n_s}$ where $R$ is the reflection vector, $V$ the viewing direction and $n_s$ the shininess (large for metals, small for rough surfaces). Example: the bright spot on a polished apple or metal ball.

Total intensity: $I = I_{amb}+I_{diff}+I_{spec}$.

(a) Ambient light

Ambient light is non-directional light of uniform intensity resulting from multiple reflections of light from walls, floor and other objects of the environment. It lights all surfaces equally from all directions, independent of position and viewer, so surfaces facing away from every light source are not completely black. $I_{amb}=k_aI_a$ $k_a$ ($0\le k_a\le1$) is the surface's ambient reflection coefficient. Example: a room corner not directly lit by a bulb is still dimly visible.

(b) Diffuse reflection

Diffuse reflection is the scattering of incident light equally in all directions by a rough, matte surface (e.g. paper, chalk). The brightness depends only on the angle $\theta$ between the unit surface normal $N$ and the unit direction to the light $L$, according to Lambert's cosine law: $I_{diff}=k_dI_l\cos\theta=k_dI_l\,(N\cdot L)\quad(N\cdot L\ge0)$ It is independent of the viewing position: the surface looks equally bright from any direction and is brightest when the light is perpendicular ($\theta=0$). Example: a matte-painted wall.

Differences between DDA and Bresenham's algorithm

Bresenham's algorithm for $(10, 6)$ to $(12, 1)$

$\Delta x = 2$, $\Delta y = 5$ (in magnitude). Since $|\Delta y| > |\Delta x|$ the slope is steep, so $y$ is the driving axis. $x$ stays the same or increases by 1 and $y$ decreases by 1 at each step.

Initial decision parameter: $p_0 = 2\Delta x - \Delta y = 4 - 5 = -1$

Rule: if $p_k < 0$, $x$ does not change and $p_{k+1} = p_k + 2\Delta x = p_k + 4$; otherwise $x$ increases by 1 and $p_{k+1} = p_k + 2(\Delta x - \Delta y) = p_k - 6$.

The pixels plotted are (10,6), (10,5), (11,4), (11,3), (12,2), (12,1).

Decision parameter in circle drawing (midpoint circle algorithm)

A circle centred at the origin is symmetric in 8 octants, so only the octant from $(0, r)$ to $x = y$ is calculated. At each step $x$ increases by 1 and we decide whether $y$ stays or decreases by 1. The decision uses the circle function $f(x, y) = x^2 + y^2 - r^2$, evaluated at the midpoint between the two candidate pixels:

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

If $p_k < 0$, the midpoint is inside the circle, so the pixel $(x_k+1, y_k)$ is chosen; otherwise $(x_k + 1, y_k - 1)$ is chosen. The parameter is updated incrementally:

• $p_k < 0$: $p_{k+1} = p_k + 2x_{k+1} + 1$
• $p_k \ge 0$: $p_{k+1} = p_k + 2x_{k+1} + 1 - 2y_{k+1}$

with the initial value $p_0 = 1 - r$ (starting at $(0, r)$).

Circle with $r = 5$, centre $(10, 5)$

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

At $(3,4)$, the next point has $x > y$ so we stop. Octant points: (0,5), (1,5), (2,5), (3,4).

Shifting by the centre $(10, 5)$ and using 8-way symmetry $(x_c \pm x, y_c \pm y)$ and $(x_c \pm y, y_c \pm x)$:

• from (0,5): (10,10), (10,0), (15,5), (5,5)
• from (1,5): (11,10), (9,10), (11,0), (9,0), (15,6), (5,6), (15,4), (5,4)
• from (2,5): (12,10), (8,10), (12,0), (8,0), (15,7), (5,7), (15,3), (5,3)
• from (3,4): (13,9), (7,9), (13,1), (7,1), (14,8), (6,8), (14,2), (6,2)

Vector (random-scan) display architecture

Block diagram: Host CPU and application program -> Display Processor Unit (display program in a display list/refresh buffer) -> Display controller with vector generator and DAC -> CRT.

• The picture is stored as a set of line-drawing commands (display list) in the refresh buffer.
• The display processor reads the commands and the electron beam is moved directly from endpoint to endpoint, drawing only the lines needed. The picture is refreshed (30-60 times per second) by repeating the list.

Advantages: high resolution and smooth lines, little memory needed, easy to modify parts of a picture, fast for line drawings. Disadvantages: poor for filled areas and shaded realistic images, flicker when the picture is complex, expensive, limited colours.

Raster-scan display architecture

Block diagram: CPU -> system memory -> video controller (display processor) -> frame buffer (pixel values) -> DAC / colour lookup table -> CRT (or LCD).

• The screen is a matrix of pixels. The frame buffer stores the intensity or colour of every pixel; the video controller reads it line by line, row by row, and the beam sweeps the whole screen (scanning left to right, top to bottom) at the refresh rate.

Advantages: can fill areas and show shaded, realistic, multi-colour images, low cost, no flicker for complex scenes, easy to combine with TV technology. Disadvantages: needs large memory for the frame buffer, lines show aliasing (jaggies) because of discrete pixels, lower resolution of lines, and redrawing needs scan conversion.

Computer graphics is used in many areas.

• Computer-aided design (CAD): design of buildings, machines, vehicles, circuits and chips with 2D/3D models and simulation.
• Entertainment: movies, special effects, animation, video games and virtual reality.
• Education and training: simulators for pilots, drivers and surgeons, and interactive learning.
• Presentation graphics and data visualisation: charts, graphs, histograms and dashboards.
• Medicine: CT, MRI and ultrasound imaging, 3D reconstruction and surgical planning.
• Scientific visualisation and simulation: weather, molecular structures, fluid flow and astronomy.
• GIS and cartography: maps, satellite images and terrain modelling.
• Graphical user interfaces: windows, icons, menus in operating systems and apps.
• Art and advertising: digital painting, image editing, logos and web design.
• Image processing and virtual/augmented reality.

A polygon is a closed plane figure made of straight line segments (edges) that join vertices. In a computer, a polygon surface is stored using tables.

• Vertex table: a list of all the vertices, with the coordinates $(x, y, z)$ of each, for example V1: (x1,y1,z1).
• Edge table: a list of the edges; each edge entry holds the two vertices it joins, for example E1: V1, V2.
• Polygon (surface) table: a list of the polygons; each entry holds the edges that make up the polygon, for example S1: E1, E2, E3.

Example (triangle): V1(0,0), V2(4,0), V3(2,3); E1 = V1V2, E2 = V2V3, E3 = V3V1; S1 = E1, E2, E3.

The three-table scheme avoids storing coordinates repeatedly, gives fast access to shared edges and vertices, and supports consistency checks (every edge belongs to at least one polygon, every vertex to at least two edges). Extra attributes, such as surface normal, can be added to the polygon table.

Boundary representation (B-rep) describes a 3D solid by its surface boundary, which separates the interior of the object from the exterior. The object is defined as a collection of connected surface elements: faces, edges and vertices.

• Geometry gives the shape of each element: vertex coordinates, edge curves and surface equations.
• Topology records the connections: which faces share edges, which edges meet at vertices, and which side is outside (face orientation).

Typically, it is stored as polygon meshes (vertex, edge and face tables) or as curved patches (NURBS), and the Euler formula $V - E + F = 2$ holds for a valid simple solid.

Advantages: the surface is directly available for rendering and display, suitable for complex shapes, and allows local editing. Disadvantages: stores a large amount of data, does not directly record the volume, and Boolean operations are complex. It contrasts with constructive solid geometry (CSG) and spatial partitioning.

The Phong model calculates the specular reflection, the bright highlight on shiny surfaces, which is seen when the viewer is near the direction of mirror reflection of the light.

Let $\mathbf{N}$ be the unit surface normal, $\mathbf{L}$ the direction to the light, $\mathbf{R}$ the direction of reflected light and $\mathbf{V}$ the direction to the viewer. Then

$\mathbf{R} = 2(\mathbf{N}\cdot\mathbf{L})\mathbf{N} - \mathbf{L}$

The specular intensity is

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

where $k_s$ is the specular reflection coefficient, $I_l$ the light intensity, $\phi$ the angle between $\mathbf{V}$ and $\mathbf{R}$, and $n_s$ the specular exponent (shininess).

• A large $n_s$ (100 or more) gives a small sharp highlight for shiny surfaces such as metal; a small $n_s$ gives a broad highlight for dull surfaces.
• The intensity is maximum when $\phi = 0$ and falls off as $\phi$ increases. It is zero when $\mathbf{V}\cdot\mathbf{R} < 0$.
• The highlight colour is that of the light.

The total intensity is the sum of ambient, diffuse and specular terms. A common faster variant uses the halfway vector $\mathbf{H} = (\mathbf{L}+\mathbf{V})/|\mathbf{L}+\mathbf{V}|$ and $(\mathbf{N}\cdot\mathbf{H})^{n_s}$ (Blinn-Phong).

(a) Shearing and scaling

Scaling changes the size of an object. For scale factors $s_x$ and $s_y$ about the origin:

$x' = x \cdot s_x,\quad y' = y \cdot s_y,\qquad \begin{bmatrix}x'\\y'\end{bmatrix} = \begin{bmatrix}s_x & 0\\0 & s_y\end{bmatrix}\begin{bmatrix}x\\y\end{bmatrix}$

If $s > 1$ the object enlarges, if $s < 1$ it shrinks, and $s_x = s_y$ is uniform scaling (the shape is preserved).

Shearing distorts the shape by shifting the coordinates proportionally to the other coordinate, as if layers slide over one another.

• x-shear: $x' = x + sh_x \cdot y,\; y' = y$
• y-shear: $x' = x,\; y' = y + sh_y \cdot x$

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

(b) Line clipping

Line clipping removes the parts of a line that lie outside a clipping window (usually rectangular) and keeps the part inside. A line is classed as completely inside (accepted), completely outside (rejected) or partially inside (clipped by finding intersections with the window boundaries). Algorithms: Cohen-Sutherland (region outcodes), Liang-Barsky (parametric) and Nicholl-Lee-Nicholl. It saves processing and display of invisible parts.

The "line method" here refers to the scan-line method of visible-surface detection, an image-space method that processes the picture one scan line at a time.

Procedure

1. For each scan line, find the intersections of the line with the projections of all polygon edges.
2. Sort the intersection points on the line by $x$ and divide the line into spans.
3. For each span, find which polygons overlap it (using flags in/out and the polygon table).
4. Calculate the depth $z$ of each overlapping polygon from its plane equation $Ax + By + Cz + D = 0$: $z = \frac{-Ax - By - D}{C}$
5. The polygon with the smallest depth (nearest to the viewer) is visible in that span, and its colour is placed in the frame buffer for the span.
6. Depth is recalculated only where polygons intersect or overlap; it is updated incrementally across the span by $z' = z - A/C$.

Example. Two overlapping polygons S1 and S2 are given. On a scan line, the spans where only S1 or only S2 is present take its colour. In the span where both overlap, their depths are compared: if S1 has the smaller $z$, S1's colour is shown there. Where they do not intersect, the order cannot change across the span, so no extra depth calculation is needed.

Both are more realistic than flat shading and first compute vertex normals by averaging the normals of the polygons that share the vertex.

A Bezier curve is a parametric curve defined by a set of control points $P_0, \dots, P_n$. It is shaped by the control polygon and is widely used in graphics, CAD and font design. The curve is

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

where the Bernstein blending functions are

$B_{i,n}(u) = \binom{n}{i} u^i (1-u)^{n-i}$

For $n = 3$ (cubic) there are four control points, and $P(u) = (1-u)^3P_0 + 3u(1-u)^2P_1 + 3u^2(1-u)P_2 + u^3P_3$.

Properties

• It passes through the first and last control points: $P(0) = P_0$, $P(1) = P_n$.
• The tangent at the ends is along the first and last segments of the control polygon.
• The degree of the curve is one less than the number of control points.
• The curve lies within the convex hull of its control points (convex hull property).
• The blending functions are non-negative and sum to 1 (partition of unity).
• It is invariant under affine transformations, so only the control points need to be transformed.
• It is smooth and has no local control: changing one control point changes the whole curve.
• It is symmetric: reversing the order of the control points gives the same curve.

Polygon clipping

Polygons are clipped so that only the parts inside the clipping window remain, and the result must still be a closed polygon (new edges along the window boundary are added). Clipping the edges as separate lines is not enough.

Sutherland-Hodgman algorithm. The polygon is clipped against each window boundary in turn (left, right, bottom, top); the output list of vertices of one stage is the input of the next. For each edge from vertex $S$ to vertex $E$ of the polygon, four cases are handled:

1. Both $S$ and $E$ inside: output $E$.
2. $S$ inside, $E$ outside: output the intersection point.
3. Both outside: output nothing.
4. $S$ outside, $E$ inside: output the intersection point and $E$.

Other methods are Weiler-Atherton (handles concave polygons and holes) and Liang-Barsky.

Gouraud shading model

Gouraud shading (intensity interpolation) renders a smooth surface from a polygon mesh.

1. Vertex normals: at each vertex, average the unit normals of the polygons sharing it: $\mathbf{N}_v = \frac{\sum_{k=1}^{n}\mathbf{N}_k}{\left|\sum_{k=1}^{n}\mathbf{N}_k\right|}$
2. Vertex intensities: apply the illumination model (ambient + diffuse + specular) at each vertex using $\mathbf{N}_v$.
3. Interpolate along edges: for a scan line $y_s$ between vertices 1 and 2 of an edge, $I_a = \frac{y_s - y_2}{y_1 - y_2} I_1 + \frac{y_1 - y_s}{y_1 - y_2} I_2$ and similarly $I_b$ on the other edge, giving the end intensities $I_a$ and $I_b$ of the scan-line span at $x_a$ and $x_b$.
4. Interpolate along the scan line: $I_p = \frac{x_b - x_p}{x_b - x_a} I_a + \frac{x_p - x_a}{x_b - x_a} I_b$ Incrementally, $I(x+1) = I(x) + \Delta I$ with $\Delta I = (I_b - I_a)/(x_b - x_a)$.

It removes the intensity discontinuities between faces and is fast, but it can miss highlights and show Mach bands.

Bresenham's line algorithm (for slope $0 < m < 1$, $x_0 < x_1$)

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

For other slopes the roles of $x$ and $y$ are swapped, and $y$ decreases when the line goes downward.

Line $A(6, 9)$ to $B(10, 5)$

$\Delta x = 4$, $\Delta y = 4$ (slope $= -1$, so $y$ decreases by 1 with every step of $x$).

$p_0 = 2\Delta y - \Delta x = 8 - 4 = 4$.

Since $p_k \ge 0$ at every step, $y$ decreases by 1 each time, and $p_{k+1} = p_k + 2\Delta y - 2\Delta x = p_k + 0 = 4$.

The pixels plotted are (6,9), (7,8), (8,7), (9,6), (10,5).

Parallel versus perspective projection

Rotation by $30^\circ$ counterclockwise about the pivot $(5, 3)$

Rotation about a pivot $(x_r, y_r)$:

$x' = x_r + (x - x_r)\cos\theta - (y - y_r)\sin\theta$ $y' = y_r + (x - x_r)\sin\theta + (y - y_r)\cos\theta$

with $\cos 30^\circ = 0.866$, $\sin 30^\circ = 0.5$.

• A(5, 7): $(x - x_r, y - y_r) = (0, 4)$. $x' = 5 + 0 - 4(0.5) = 3$; $y' = 3 + 0 + 4(0.866) = 6.464$. So $A' = (3, 6.46)$.
• B(12, 85): $(7, 82)$. $x' = 5 + 7(0.866) - 82(0.5) = 5 + 6.062 - 41 = -29.94$; $y' = 3 + 7(0.5) + 82(0.866) = 3 + 3.5 + 71.01 = 77.51$. So $B' = (-29.94, 77.51)$.
• C(5, 3): this is the pivot, so it does not move: $C' = (5, 3)$.

The new triangle is $A'(3, 6.46)$, $B'(-29.94, 77.51)$, $C'(5, 3)$.

Motion capture (mocap) is the process of recording the movement of real people or objects and transferring it to a digital 3D model so that the model moves in the same natural way.

How it works

1. Markers (reflective balls or sensors) are placed on key joints of an actor (head, shoulders, elbows, wrists, hips, knees, ankles).
2. Several cameras (optical systems) or inertial/magnetic sensors track the 3D position of each marker many times per second.
3. The software triangulates marker positions into 3D coordinates for every frame.
4. These positions are mapped onto the skeleton (rig) of a digital character, which drives the mesh through skinning.
5. The animator cleans the data (removes noise, fills gaps) and edits it.

Types: optical (marker-based or markerless), inertial (gyroscope/accelerometer suits), magnetic and mechanical.

Example: In a film or game, an actor wearing a marker suit walks, fights and jumps in a studio. The captured motion is applied to a 3D monster or game character, so its walk cycle looks realistic without an animator posing every frame. Gollum in The Lord of the Rings and sports-game players are well-known examples.

Advantages: realistic motion, fast production, subtle detail. Disadvantages: expensive equipment, data clean-up, limited to motions that humans/real objects can perform.

Parametric curve

A parametric curve represents the coordinates of each point as a function of a parameter $u$ (or $t$) instead of one variable in terms of another:

$x = x(u),\quad y = y(u),\quad z = z(u),\qquad 0 \le u \le 1$

Thus $P(u) = (x(u), y(u), z(u))$. It can represent multi-valued curves, closed curves and curves with vertical tangents, which $y=f(x)$ cannot. A circle is $x = r\cos\theta,\ y = r\sin\theta$. Common graphics forms are Bezier, B-spline and Hermite curves.

Bezier curve

A Bezier curve of degree $n$ is defined by $n+1$ control points $P_0,\dots,P_n$:

$P(u) = \sum_{i=0}^{n} P_i\, B_{i,n}(u),\qquad B_{i,n}(u) = \binom{n}{i}u^i(1-u)^{n-i}$

Properties

1. It passes through the first and last control points: $P(0)=P_0$, $P(1)=P_n$.
2. The tangent at the start is along $P_1-P_0$ and at the end along $P_n-P_{n-1}$.
3. The curve lies inside the convex hull of its control points (convex hull property).
4. The blending functions are non-negative and sum to 1: $\sum B_{i,n}(u)=1$.
5. The curve has degree $n$, i.e. one less than the number of control points, and is smooth (infinitely differentiable).
6. It is invariant under affine transformations: transforming the control points transforms the curve.
7. It has global control: moving one control point changes the whole curve, and it is symmetric (reversing the point order gives the same curve).

Wireframe representation shows a 3D object only by its edges (the skeleton), like a frame made of wire; faces are not filled.

Data stored

• A vertex table with the $(x, y, z)$ coordinates of each vertex.
• An edge table where each edge is a pair of vertex indices.
• Optionally, a surface/face table listing edges per face.

For a cube: 8 vertices, 12 edges, 6 faces. The edge $E_1$ may be stored as $(V_1, V_2)$.

Display: the vertices are transformed and projected to 2D, and then each edge is drawn as a line between the projected end points. Curved surfaces are drawn by a mesh of lines (e.g. latitude/longitude lines on a sphere).

Advantages: very fast to draw, little memory, ideal for quick previews, modelling and editing in CAD.

Disadvantages: no surface or shading information; hidden lines are not removed, so the picture is ambiguous (the Necker cube effect) and looks unrealistic. Hidden-line removal can be added to reduce this.

In OpenGL a polygon is created by listing its vertices between glBegin() and glEnd(). The mode argument decides the primitive: GL_POLYGON (a single convex polygon), GL_TRIANGLES, GL_QUADS, GL_TRIANGLE_STRIP, GL_TRIANGLE_FAN, etc. The polygon must be convex and planar. Colour is set by glColor3f() and vertices by glVertex2f()/glVertex3f().

Example (draw a coloured pentagon, using GLUT)

#include <GL/glut.h>

void display(void) {
    glClear(GL_COLOR_BUFFER_BIT);
    glColor3f(1.0, 0.0, 0.0);          // red
    glBegin(GL_POLYGON);
        glVertex2f(-0.3, -0.5);
        glVertex2f( 0.3, -0.5);
        glVertex2f( 0.5,  0.1);
        glVertex2f( 0.0,  0.6);
        glVertex2f(-0.5,  0.1);
    glEnd();
    glFlush();
}

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

The vertices are joined in order and the last is joined to the first. glPolygonMode(GL_FRONT_AND_BACK, GL_LINE) can draw only the outline instead of a filled polygon.

(a) Z-Buffer

The Z-buffer (depth buffer) is an image-space method of visible surface detection. Two buffers of the same size as the screen are used: a frame (refresh) buffer storing colour of each pixel and a depth buffer storing the depth $z$ of the nearest surface seen so far at each pixel.

Algorithm: initialise depth to the maximum (far) value and the frame buffer to the background colour. For each polygon and each pixel $(x,y)$ it covers, compute $z$; if $z$ is nearer than depth[x][y], set depth[x][y] = z and frame[x][y] = the surface colour. Depth along a scan line is computed incrementally from the plane equation $z = (-Ax - By - D)/C$, giving $z' = z - A/C$. It is simple and handles any order of polygons, but needs extra memory and cannot handle transparency easily.

(b) Polygon Table

A polygon table stores the geometric and attribute data of a polygon-mesh object in tables:

• Vertex table: coordinates of each vertex.
• Edge table: each edge as a pair of vertex pointers.
• Surface (polygon) table: each polygon as a list of edges, plus attributes such as colour and transparency.

Example: $V_1(x_1,y_1,z_1)$ ...; $E_1: V_1, V_2$; $S_1: E_1, E_2, E_3$. The tables allow quick consistency checks (every edge belongs to two polygons) and each polygon's plane equation $Ax+By+Cz+D=0$ can also be stored for visibility tests and shading.

Random scan (vector) display draws a picture as a set of line segments directly, with the electron beam moving from one end point to the next in any order, rather than sweeping the whole screen.

Architecture

 Application program --> Graphics package --> Display file (refresh buffer)
                                                      |
                                           Display controller (DPU)
                                                      |
                                  Vector generator / DACs --> Deflection amps
                                                      |
                                             CRT (beam deflection)

Components

1. Display file memory: stores the picture definition as display commands (line, point, character with coordinates) produced by the graphics package.
2. Display controller (processor): repeatedly reads the commands and sends them to the vector generator.
3. Vector generator: converts coordinates into analog deflection voltages (via DACs) to move the beam.
4. CRT: phosphor lights where the beam passes; because phosphor fades, the picture is refreshed 30 to 60 times a second.

Features: high resolution and smooth lines; refresh time depends on the number of lines; less memory; poor at shaded/filled areas; used in plotters and CAD.

Reflection about the vertical line $x = 7$: translate the line to the y-axis, reflect about the y-axis, translate back.

$M = T(7,0)\cdot R_{y}\cdot T(-7,0)$

The result simplifies to $x' = 14 - x,\ y' = y$.

Matrix form (homogeneous): $\begin{bmatrix}x'\\y'\\1\end{bmatrix}=\begin{bmatrix}-1&0&14\\0&1&0\\0&0&1\end{bmatrix}\begin{bmatrix}x\\y\\1\end{bmatrix}$

• $A(9,3)$: $x' = 14-9 = 5$, so $A'(5,3)$.
• $B(12,10)$: $x' = 14-12 = 2$, so $B'(2,10)$.

Result: the reflected segment has end points $(5,3)$ and $(2,10)$.

Graph (description): Draw the vertical mirror line $x=7$. The original segment from $(9,3)$ to $(12,10)$ lies to the right of it, sloping up and to the right. The image segment from $(5,3)$ to $(2,10)$ lies to the left, sloping up and to the left. Each point and its image are at equal distance from $x=7$ (2 units for $A$, 5 units for $B$), and the joining lines are horizontal (perpendicular to the mirror).

Z-buffer (depth-buffer) method

An image-space visible-surface method that compares surface depths pixel by pixel. It uses two arrays of screen size: a depth buffer depth(x,y) and a refresh (frame) buffer frame(x,y).

Algorithm

1. Initialise depth(x,y) = 1.0 (far plane) (or $\infty$) and frame(x,y) = background colour for all pixels.
2. For every polygon in the scene, for every pixel $(x,y)$ in its projection:
   • Calculate the depth $z$ from the plane equation $Ax+By+Cz+D=0$, i.e. $z = \dfrac{-Ax-By-D}{C}$.
   • If $z <$ depth(x,y) (nearer): set depth(x,y) = z and frame(x,y) = surface colour at $(x,y)$.
3. After all polygons are processed, the frame buffer holds the visible surfaces.

Along a scan line the depth is obtained incrementally: $z(x+1,y) = z(x,y) - \dfrac{A}{C}$, and for the next scan line $z(x,y-1)= z(x,y)+\dfrac{B}{C}$ (or $z - A/C$ along an edge), reducing computation.

Advantages: simple, objects can be drawn in any order, no sorting, easy hardware implementation, works with any surface for which depth can be computed.

Limitations and remedies

1. Memory: needs an extra buffer of full screen size. Remedy: process the screen in strips or sub-regions (area subdivision), or use smaller depth precision.
2. Only one visible surface per pixel: cannot handle transparency or translucency. Remedy: the A-buffer method keeps a linked list of surfaces per pixel and blends them.
3. Aliasing: discrete pixel decisions give jagged edges. Remedy: A-buffer/supersampling for anti-aliasing.
4. Depth precision and z-fighting: limited bits cause errors for nearly coplanar surfaces. Remedy: tighter near/far planes, higher bit depth (24/32-bit), non-linear (1/z) depth.
5. Wasted work: hidden polygons are still rasterised (overdraw). Remedy: early-z test, front-to-back ordering or hierarchical z-buffers.

Role of clipping

Clipping removes the parts of a picture that lie outside a chosen clipping window (or view volume) so that only the visible portion is processed and displayed. Its roles are:

• It prevents drawing outside the display area or viewport and the wrong display (wrap-around) of objects.
• It saves computation, since scan conversion, shading and transformation work are done only for visible parts.
• It is used in viewing transformations, in selecting parts of a picture to enlarge, in hidden-surface and anti-aliasing procedures, and in copy/move/delete editing operations.
• Algorithms: Cohen-Sutherland and Liang-Barsky (lines), Sutherland-Hodgman and Weiler-Atherton (polygons).

DDA for $(20,10)$ to $(30,18)$

$\Delta x = 10,\ \Delta y = 8$. Steps $= \max(|\Delta x|,|\Delta y|) = 10$. $x_{inc} = 10/10 = 1,\quad y_{inc} = 8/10 = 0.8$.

Clockwise rotation matrices (angle $\theta$, homogeneous 3D, right-handed system, clockwise when looking from the positive axis towards the origin):

$$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},\quad 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}$$

$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 axis $y=4$

The axis $y=4$ (with $z=0$) is a line parallel to the x-axis. The angle is not given, so take $\theta = 90^\circ$ clockwise. Steps: translate the axis to the x-axis, rotate about x, translate back:

$M = T(0,4,0)\cdot R_x(-90^\circ)\cdot T(0,-4,0)$

With $\cos90^\circ=0,\ \sin90^\circ=1$, a point $(x,y,z)$ becomes $y_1 = y-4$; then $y_2 = y_1\cos\theta + z\sin\theta = z$, $z_2 = -y_1\sin\theta + z\cos\theta = -y_1$; finally $y' = y_2+4$.

• $(0,0,0)$: $y_1=-4$, so $y_2 = 0,\ z_2 = 4$, giving $(0,4,4)$.
• $(2,3,0)$: $y_1=-1$, so $y_2=0,\ z_2=1$, giving $(2,4,1)$.
• $(5,4,0)$: $y_1=0$, so $y_2=0,\ z_2=0$, giving $(5,4,0)$.

New object: $(0,4,4),\ (2,4,1),\ (5,4,0)$. The x-coordinates are unchanged, as expected for rotation about an axis parallel to x, and the point on the axis stays fixed.

Phong shading (normal-vector interpolation) gives more accurate highlights than Gouraud shading because it interpolates surface normals, not intensities, and applies the illumination model at every pixel.

Procedure

1. Find vertex normals: for each vertex, average the normals of the polygons sharing it: $N_v = \frac{\sum_k N_k}{\left|\sum_k N_k\right|}$
2. Interpolate normals along polygon edges: for an edge between vertices 1 and 2, the normal at scan-line intersection $y_s$ is $N = \frac{y_s - y_2}{y_1 - y_2}N_1 + \frac{y_1 - y_s}{y_1 - y_2}N_2$ (incrementally, $N' = N + \Delta N$).
3. Interpolate along each scan line between the left and right edge normals to get the normal at every pixel, then normalise it.
4. Apply the illumination model at each pixel with the interpolated normal: $I = k_a I_a + k_d I_l (N\cdot L) + k_s I_l (N\cdot H)^{n_s}$
5. Set the pixel to the computed intensity and repeat for all scan lines and polygons.

Features: realistic specular highlights and reduced Mach bands, but it is much more costly than Gouraud shading since lighting is computed per pixel.

Parametric cubic curve

A parametric cubic curve is a curve whose $x$, $y$, $z$ coordinates are cubic polynomials in the parameter $u$ ($0\le u\le1$):

$x(u)=a_xu^3+b_xu^2+c_xu+d_x$ and similarly for $y(u)$ and $z(u)$. In vector form $P(u) = a u^3 + b u^2 + c u + d = U\cdot M\cdot G$ with $U=[u^3\ u^2\ u\ 1]$, $M$ the basis matrix and $G$ the geometry vector (control points or end points and tangents). The 12 coefficients are fixed by 12 conditions, such as end points and tangent vectors (Hermite), or four control points (Bezier, B-spline).

Properties

1. Cubic is the lowest degree that can represent a non-planar space curve and gives enough flexibility (end points plus end tangents) with low computation.
2. It gives smooth curves; two segments joined with matching tangents have $C^1$ (or $C^2$) continuity at the joint (parametric continuity $C^0,C^1,C^2$, or geometric $G^0,G^1$).
3. It is independent of the coordinate system and can represent multi-valued curves and vertical tangents.
4. It can be easily transformed, as only the control geometry needs transforming.
5. Types: Hermite (end points and tangents), Bezier (control points), B-spline and Catmull-Rom splines.
6. A long curve is built by joining many cubic segments (piecewise cubic) rather than using a high-degree polynomial, which oscillates.

Use the midpoint circle algorithm with centre $(0,0)$ and $r=6$. Start at $(x_0,y_0)=(0,6)$ with decision parameter $p_0 = 1 - r = -5$.

Rule: if $p_k<0$, next point $(x_k+1,\,y_k)$ and $p_{k+1}=p_k+2x_{k+1}+1$; else next point $(x_k+1,\,y_k-1)$ and $p_{k+1}=p_k+2x_{k+1}+1-2y_{k+1}$. Stop when $x\ge y$.

Starting point $(0,6)$; the points in the first octant are $(0,6),(1,6),(2,6),(3,5),(4,4)$.

Using 8-way symmetry, each $(x,y)$ gives $(\pm x,\pm y)$ and $(\pm y,\pm x)$:

• $(0,6),(0,-6),(6,0),(-6,0)$
• $(1,6),(-1,6),(1,-6),(-1,-6),(6,1),(-6,1),(6,-1),(-6,-1)$
• $(2,6),(-2,6),(2,-6),(-2,-6),(6,2),(-6,2),(6,-2),(-6,-2)$
• $(3,5),(-3,5),(3,-5),(-3,-5),(5,3),(-5,3),(5,-3),(-5,-3)$
• $(4,4),(-4,4),(4,-4),(-4,-4)$

In boundary representation (B-rep), a 3D object is described by its bounding surfaces, usually polygons forming a polygon mesh. Polygon tables store this information in organised tables for processing and display. They have two groups of data: geometric (vertex coordinates and spatial orientation) and attribute (colour, transparency, reflectivity, texture).

Tables used

1. Vertex table: $V_i: (x_i, y_i, z_i)$.
2. Edge table: each edge $E_j$ with its two end vertices, e.g. $E_1: V_1, V_2$.
3. Surface-facet (polygon) table: each polygon with the edges forming it, e.g. $S_1: E_1, E_2, E_3$, plus attributes.

Example (triangle mesh): $S_1: E_1,E_2,E_3$; $S_2: E_3,E_4,E_5$ share edge $E_3$.

Uses

• Fast access to the data when drawing and transforming objects.
• Error checking: every edge should be in at least two polygons and every vertex in at least two edges, with closed polygons.
• Each polygon's plane equation $Ax+By+Cz+D=0$ is stored (computed from three vertices); the normal $(A,B,C)$ is used in visibility tests (back-face: $V\cdot N>0$) and shading.
• Sharing of vertices and edges avoids repeated data and drawing common edges twice.

Intensity attenuation

Light intensity from a point source decreases as it travels away from the source. For distance $d$, the physical rule is inverse-square: $I\propto 1/d^2$. Since this gives too sharp variation for nearby sources, graphics uses an attenuation factor $f(d)=\min\left(1,\ \frac{1}{a_0+a_1 d+a_2 d^2}\right)$ with constants $a_0,a_1,a_2$. The diffuse and specular terms are multiplied by $f(d)$ so that farther surfaces appear darker, which gives depth realism.

Types of projection

Projection maps 3D coordinates to a 2D plane.

1. Parallel projection: projectors are parallel; size is preserved, with no perspective foreshortening.
   • Orthographic: projectors are perpendicular to the plane (front, top, side views; axonometric views such as isometric).
   • Oblique: projectors are at an angle to the plane (cavalier: scale 1; cabinet: scale 1/2 on receding lines).
2. Perspective projection: projectors converge to the centre of projection; distant objects appear smaller (foreshortening), which looks realistic. Depending on the number of vanishing points: one-point, two-point and three-point perspective. Matches the human eye and camera but does not preserve shape or parallel lines.

OpenGL (Open Graphics Library) is a cross-platform, cross-language API for rendering 2D and 3D vector graphics. It is hardware independent, provides about 250 commands for drawing primitives, transformations, lighting, texture mapping, shading and hidden-surface removal (z-buffer), and works as a state machine and a rendering pipeline. Related libraries: GLU (utilities such as gluPerspective), GLUT (windowing and input, platform independent), and GLFW/GLEW.

Syntax: functions are prefixed gl (e.g. glVertex3f), constants GL_ and types GL.

Callback functions

GLUT is event driven: the program registers functions that the library calls when an event occurs, and then enters glutMainLoop().

• glutDisplayFunc(display) called when the window needs redrawing.
• glutReshapeFunc(reshape) called when the window is resized (set viewport and projection).
• glutKeyboardFunc(keyboard) called for a key press.
• glutMouseFunc(mouse) and glutMotionFunc(motion) for mouse buttons and movement.
• glutIdleFunc(idle) called when nothing else is happening (animation).
• glutTimerFunc(ms, func, value) called after a delay.

void display(){ glClear(GL_COLOR_BUFFER_BIT); /* draw */ glFlush(); }
void keyboard(unsigned char k,int x,int y){ if(k==27) exit(0); }
int main(int c,char**v){
  glutInit(&c,v); glutCreateWindow("Demo");
  glutDisplayFunc(display); glutKeyboardFunc(keyboard);
  glutMainLoop();
}

A 3D object is commonly represented by boundary representation as a polygon mesh, and its data is split into geometric and attribute information and stored in tables.

Geometric information: where the object is and how it is shaped. It consists of the vertex coordinates, the edges (vertex pairs), the surfaces (edge lists) and each plane's equation $Ax+By+Cz+D=0$, with the normal $(A,B,C)$ giving the orientation.

Attribute information: how it appears, such as colour, transparency, reflectivity, texture and shading parameters.

Storage in three tables

• Vertex table: $V_1:(0,0,0),\ V_2:(1,0,0),\ V_3:(0,1,0),\ V_4:(0,0,1)$
• Edge table: $E_1:V_1V_2,\ E_2:V_2V_3,\ E_3:V_3V_1,\ E_4:V_1V_4,\ E_5:V_2V_4,\ E_6:V_3V_4$
• Surface table (with attributes): $S_1: E_1,E_2,E_3$ (red); $S_2: E_1,E_5,E_4$ (green); $S_3: E_3,E_6,E_4$ (blue); $S_4: E_2,E_6,E_5$ (yellow)

This example is a tetrahedron (4 vertices, 6 edges, 4 faces). The tables avoid duplication (shared vertices stored once), allow consistency checks and give the data needed for transformation, hidden-surface removal and shading. A compact alternative is a single list of polygons with direct vertex coordinates, or a plane equation table with a vertex list.

Bresenham's circle drawing algorithm

For a circle of radius $r$ centred at the origin, compute only one octant (from $(0,r)$ until $x\ge y$) and use 8-way symmetry. The decision parameter chooses between the pixel $(x+1, y)$ and $(x+1, y-1)$ using integer arithmetic only.

1. Input $r$; set $x=0,\ y=r$ and decision parameter $d=3-2r$.
2. Plot the 8 symmetric points $(\pm x,\pm y),(\pm y,\pm x)$ (added to the centre $(x_c,y_c)$).
3. While $x<y$ (using the current, old $x$ and $y$):
   • if $d<0$: $d = d+4x+6$ (y unchanged)
   • else: $d = d+4(x-y)+10$ and $y=y-1$
   • $x = x+1$
   • plot the 8 symmetric points.
4. Stop when $x\ge y$.

The method uses only additions, subtractions and shifts, so it is fast.

DDA from $(2,2)$ to $(6,6)$

$\Delta x=4,\ \Delta y=4$; steps $=4$; $x_{inc}=1,\ y_{inc}=1$.

The line is the 45 degree diagonal, with all pixels exactly on the line.