Computer Graphics

Computer graphics is a field of computer science that deals with generating images with the aid of computers. It involves the use of mathematical algorithms and data structures to represent and manipulate visual information. This field has applications ranging from video games and animated movies to scientific visualization and user interface design. Understanding the fundamental concepts of computer graphics is crucial for anyone working in areas that involve visual computation.

Display Devices

Display devices are the hardware components that present visual output from a computer to the user. The most common display devices are based on raster scan technology, where the screen is divided into a grid of pixels.

Raster Scan Displays

In a raster scan display, an electron beam sweeps across the screen horizontally, row by row, from top to bottom. This process is called a scan line. The intensity of the electron beam is varied to create different colors and brightness levels for each pixel. The screen is refreshed continuously, typically 60 times per second, to maintain a stable image.

Key components of a raster scan system include:

• Video Controller: This is a specialized processor that manages the display of images. It retrieves the pixel information from a frame buffer and sends it to the display.
• Frame Buffer: This is a memory area that stores the intensity values for each pixel on the screen. The size of the frame buffer determines the resolution and color depth of the display. For example, a monochrome display with a resolution of 1024x768 would require a frame buffer of 1024 * 768 bits. A color display with 24 bits per pixel (8 bits each for red, green, and blue) would require a frame buffer of 1024 * 768 * 24 bits.
• Monitor: The Cathode Ray Tube (CRT) is the traditional display technology for raster scan systems, though Liquid Crystal Displays (LCDs) and Light Emitting Diodes (LEDs) are now more common. In a CRT, the electron beam excites phosphors on the screen's inner surface, causing them to glow.

Random Scan Displays

Random scan displays, also known as vector displays, draw images by directly addressing the points on the screen. The electron beam moves only to the points that need to be illuminated. This method is efficient for line-drawing applications, such as CAD systems or architectural drawings, where images consist of straight lines. However, they are not suitable for displaying complex, shaded areas or solid objects.

Line Drawing Algorithms

Drawing a straight line between two points on a raster display involves determining which pixels should be illuminated to approximate the line. The goal is to produce a line that appears smooth and continuous, minimizing the "staircase" effect.

Bresenham's Line Algorithm

Bresenham's algorithm is an efficient and widely used method for drawing lines. It uses only integer arithmetic, making it very fast. The algorithm incrementally decides at each step which of two possible pixels is closer to the true line.

The basic idea is to start at one endpoint and, at each step, decide whether to move horizontally, vertically, or diagonally to the next pixel. This decision is based on an error term that tracks how far the chosen pixel is from the ideal line.

Let the line be defined by endpoints (x₁, y₁) and (x₂, y₂).

Consider a line segment in the first octant (0 ≤ slope ≤ 1).

1. Initialize pixel coordinates (x, y) to (x₁, y₁).
2. Calculate the initial decision parameter: P₀ = 2 * Δy - Δx, where Δx = x₂ - x₁ and Δy = y₂ - y₁.
3. For k = 0 to Δx:
• Plot the pixel at (x, y).
• If P_k < 0, then the next pixel is (x+1, y). Set P_k+1 = P_k + 2 * Δy.
• If P_k ≥ 0, then the next pixel is (x+1, y+1). Set P_k+1 = P_k + 2 * Δy - 2 * Δx.
• Increment x. If P_k ≥ 0, increment y.

Bresenham's algorithm can be adapted for lines with slopes greater than 1, negative slopes, and lines in other octants by swapping x and y coordinates or adjusting the increments.

DDA (Digital Differential Analyzer) Algorithm

The DDA algorithm is another method for line drawing. It uses floating-point arithmetic and calculates the positions of pixels based on the slope of the line.

The algorithm works by incrementing x by 1 and calculating the corresponding y value using the slope (m = Δy / Δx). If |m| ≤ 1, we increment x by 1 and y by m. If |m| > 1, we increment y by 1 and x by 1/m. The calculated coordinates are then rounded to the nearest integer to determine the pixel to be illuminated.

While conceptually simpler, DDA is generally slower than Bresenham's algorithm due to the use of floating-point calculations and rounding.

Circle Drawing Algorithms

Drawing a circle on a raster display involves selecting pixels that best approximate a circular path. Similar to line drawing, efficiency and accuracy are key.

Midpoint Circle Algorithm

The Midpoint Circle algorithm is an efficient, integer-only algorithm for drawing circles. It is similar in principle to Bresenham's algorithm. It generates the circle point by point, starting from a point on the circle and moving outwards, choosing the next pixel that is closest to the true circle.

The algorithm works by considering the circle equation (x - h)² + (y - k)² = r², where (h, k) is the center and r is the radius. It typically generates points in one octant (e.g., from (0, r) to the point where x = y) and then uses symmetry to plot the remaining 7 octants.

At each step, the algorithm decides whether to move horizontally (to the next x position) or diagonally (to the next x and y position). This decision is based on a decision parameter that determines whether the midpoint between the two possible next pixels lies inside or outside the circle.

The initial decision parameter for the first octant (starting at (0, r)) is calculated as P₀ = 1 - r.

For subsequent steps, if the decision parameter is negative, the midpoint is inside the circle, and the next point is chosen horizontally. If it's positive or zero, the midpoint is outside or on the circle, and the next point is chosen diagonally. The decision parameter is updated accordingly at each step using only addition and subtraction.

Polygon Filling

Polygon filling is the process of coloring the interior of a polygon. Polygons can be represented in various ways, such as by a list of vertices.

Scan-Line Polygon Fill Algorithm

This algorithm works by processing the polygon scan line by scan line. For each scan line that intersects the polygon, it determines the segments of the scan line that lie inside the polygon and fills those pixels.

The algorithm typically involves:

1. Edge Table: Store information about the edges of the polygon, sorted by their y-intercept. Each entry might include the edge's starting y-coordinate, ending y-coordinate, x-intercept at the lowest y, and the slope (1/m).
2. Active Edge List: Maintain a list of edges that intersect the current scan line. This list is updated as the scan line moves up the polygon.
3. Scan Line Processing: For each scan line:
   • Add edges whose starting y-coordinate matches the current scan line to the active edge list.
   • Remove edges whose ending y-coordinate matches the current scan line from the active edge list.
   • Sort the active edges by their x-coordinates.
   • Fill the pixels between pairs of intersecting edges.
   • Update the x-coordinates of the active edges for the next scan line by adding their slopes.

Boundary Fill Algorithm

The Boundary Fill algorithm is a recursive algorithm used to fill a connected region of a polygon. It starts from a seed point within the region and colors pixels until it encounters the boundary color.

The algorithm can be described as follows:

1. Define a function `BoundaryFill(x, y, fill_color, boundary_color)`:
2. Get the color of the current pixel at (x, y).
3. If the current pixel's color is not equal to `boundary_color` and not equal to `fill_color`:
   • Set the pixel at (x, y) to `fill_color`.
   • Recursively call `BoundaryFill` for the neighboring pixels (e.g., up, down, left, right, or diagonally).

This algorithm can lead to stack overflow issues for large regions due to deep recursion. An iterative version using a stack or queue can be implemented to avoid this.

Flood Fill Algorithm

The Flood Fill algorithm is similar to Boundary Fill but fills based on a target color rather than a boundary color. It starts from a seed point and colors all connected pixels that have a specific target color with a new fill color.

The algorithm can be described as:

1. Define a function `FloodFill(x, y, target_color, fill_color)`:
2. Get the color of the current pixel at (x, y).
3. If the current pixel's color is equal to `target_color`:
   • Set the pixel at (x, y) to `fill_color`.
   • Recursively call `FloodFill` for the neighboring pixels.

Like Boundary Fill, recursive Flood Fill can cause stack overflow. An iterative approach using a stack or queue is preferred.

2-D Transformations

2-D transformations are operations that manipulate objects in a 2-dimensional plane. These include translation, rotation, scaling, and reflection. They are fundamental for moving, resizing, and orienting objects within a scene.

Translation

Translation moves an object from one position to another. In 2-D, it involves adding a fixed displacement vector (tx, ty) to each point (x, y) of the object.

The transformation equations are: x' = x + tx y' = y + ty

Rotation

Rotation turns an object around a fixed point (the pivot point). If the pivot is the origin (0,0), the transformation equations for rotating a point (x, y) by an angle θ are:

x' = x * cos(θ) - y * sin(θ) y' = x * sin(θ) + y * cos(θ)

To rotate around an arbitrary pivot point (xp, yp), we first translate the object so that the pivot point is at the origin, perform the rotation, and then translate back.

Scaling

Scaling changes the size of an object. It involves multiplying the coordinates of each point by scaling factors (sx, sy) along the x and y axes, respectively. If sx and sy are greater than 1, the object is enlarged; if they are between 0 and 1, it is reduced.

The transformation equations with respect to the origin are: x' = x * sx y' = y * sy

Scaling is typically performed with respect to the origin. To scale an object around an arbitrary pivot point (xp, yp), translate the object so the pivot is at the origin, scale, and then translate back.

Reflection

Reflection is a transformation that creates a mirror image of an object. Reflections can be performed across the x-axis, y-axis, or an arbitrary line.

• Reflection across the x-axis: (x, y) → (x, -y)
• Reflection across the y-axis: (x, y) → (-x, y)
• Reflection across the origin: (x, y) → (-x, -y)

3-D Transformations

3-D transformations extend 2-D transformations to three dimensions. They involve operations like translation, rotation, and scaling in 3D space. In 3D, we also deal with rotations around the x, y, and z axes.

3-D Translation

Translation in 3D moves a point (x, y, z) by a displacement vector (tx, ty, tz): x' = x + tx y' = y + ty z' = z + tz

3-D Rotation

Rotation in 3D is more complex as it can be performed around any arbitrary axis. However, standard rotations are defined around the principal axes (x, y, z).

• Rotation around the x-axis by angle θ: x' = x y' = y * cos(θ) - z * sin(θ) z' = y * sin(θ) + z * cos(θ)
• Rotation around the y-axis by angle θ: x' = x * cos(θ) + z * sin(θ) y' = y z' = -x * sin(θ) + z * cos(θ)
• Rotation around the z-axis by angle θ: x' = x * cos(θ) - y * sin(θ) y' = x * sin(θ) + y * cos(θ) z' = z

3-D Scaling

Scaling in 3D multiplies coordinates by scaling factors (sx, sy, sz): x' = x * sx y' = y * sy z' = z * sz

Homogeneous Coordinates

To represent all 2D and 3D transformations (translation, rotation, scaling) using matrix multiplication, we use homogeneous coordinates. In 2D, a point (x, y) is represented as (x, y, 1). In 3D, a point (x, y, z) is represented as (x, y, z, 1).

This allows translation, which is an additive operation, to be represented as a matrix multiplication.

2D Example (Translation):
Matrix T = $$ \begin{pmatrix} 1 & 0 & tx \\ 0 & 1 & ty \\ 0 & 0 & 1 \end{pmatrix} $$
Point P = $$ \begin{pmatrix} x \\ y \\ 1 \end{pmatrix} $$
P' = T * P = $$ \begin{pmatrix} 1 & 0 & tx \\ 0 & 1 & ty \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} x \\ y \\ 1 \end{pmatrix} = \begin{pmatrix} x + tx \\ y + ty \\ 1 \end{pmatrix} $$

Combining transformations (e.g., translate, then rotate, then scale) becomes a matter of multiplying their corresponding matrices in the correct order.

Viewing Transformations

Viewing transformations define how a 3D scene is projected onto a 2D view plane, allowing us to see the scene from a particular perspective. This involves defining a camera, its position, orientation, and the properties of the view volume.

The Viewing Pipeline

The process of transforming a 3D world coordinate into a 2D screen coordinate typically involves several steps:

1. World Coordinates to Viewing Coordinates: Transform objects from their world positions into a coordinate system defined by the camera's position and orientation. This is often done using a view matrix.
2. Projection Transformation: Project the 3D scene onto a 2D projection plane. This can be either orthographic or perspective projection.
3. Clipping: Remove parts of the scene that lie outside the view volume.
4. Viewport Transformation: Map the projected 2D coordinates to the coordinates of the display window (the viewport).

Orthographic Projection

In orthographic projection, parallel lines in the 3D scene remain parallel after projection, and objects do not appear smaller as they move further away. This is useful for technical drawings and diagrams where true dimensions are important.

The projection is typically done by dropping the z-coordinate (or a scaled version of it) and mapping the x and y coordinates within the view volume to the viewport.

Perspective Projection

Perspective projection simulates how the human eye sees the world. Objects closer to the viewer appear larger, and objects further away appear smaller. Parallel lines may converge at vanishing points.

This is achieved by dividing the x and y coordinates by the z-coordinate (or a related value). The view volume for perspective projection is a pyramid or frustum.

Clipping

Clipping is the process of removing parts of a scene that are outside the defined viewing area or window. This is essential for efficiency, as rendering objects that are not visible is a waste of computational resources.

Point Clipping

A point (x, y) is inside the clipping window if: x_min ≤ x ≤ x_max y_min ≤ y ≤ y_max

Line Clipping (Cohen-Sutherland Algorithm)

The Cohen-Sutherland algorithm is a common algorithm for clipping lines against a rectangular window. It divides the 2D plane into 9 regions, assigning a 4-bit region code to each point based on its position relative to the window boundaries.

The region codes are:

• Top-Left (TL): 1010 (binary)
• Top-Right (TR): 1001
• Bottom-Left (BL): 0010
• Bottom-Right (BR): 0001
• Inside (I): 0000
• Top (T): 1000
• Bottom (B): 0000
• Left (L): 0010
• Right (R): 0100

(Note: The order and exact bit assignments can vary, but the principle is to identify regions outside the window.)

The algorithm proceeds as follows for a line segment with endpoints P1 and P2:

1. Compute the region codes for P1 and P2.
2. Trivial Accept: If both codes are 0000 (both points inside), the entire line is visible.
3. Trivial Reject: If the bitwise AND of the two codes is non-zero (meaning both points are in the same "outside" region, e.g., both above the window), the entire line is outside and can be rejected.
4. Clipping: If neither trivial accept nor reject applies, clip the line. Choose one endpoint that is outside the window. Calculate the intersection of the line with one of the window boundaries. Replace the outside endpoint with the intersection point and recompute its region code. Repeat the process until the line is trivially accepted or rejected.

Polygon Clipping (Sutherland-Hodgman Algorithm)

The Sutherland-Hodgman algorithm clips a polygon against a convex clipping window. It processes the polygon against each edge of the clipping window sequentially.

For each edge of the clipping window, the algorithm takes the vertices of the polygon (or the clipped polygon from the previous edge) and outputs a new list of vertices. For each edge of the subject polygon, it considers four cases:

• Inside to Inside: Output the second vertex (inside).
• Inside to Outside: Output the intersection point.
• Outside to Outside: Output nothing.
• Outside to Inside: Output the intersection point, then the second vertex (inside).

By repeating this process for all edges of the clipping window, the final clipped polygon is obtained.

Spline and Bezier Representations

Splines are curves defined by a set of control points. They are widely used in computer graphics for modeling smooth shapes, such as those found in fonts, character animation, and industrial design. Bezier curves are a popular type of spline.

Spline Curves

Splines are piecewise polynomial curves. They offer more control over shape than simple polynomial curves and are easier to manage.

Key properties of splines include:

• Continuity: Ensures that adjacent curve segments join smoothly. C⁰ continuity means the curves meet, C¹ means they have the same tangent, and C² means they have the same curvature.
• Control Points: Points that influence the shape of the curve.
• Degree: The degree of the polynomial used to define the curve segment.

Bezier Curves

Bezier curves are defined by a set of control points. The curve is always contained within the convex hull of its control points. The first and last control points are typically the endpoints of the curve.

A Bezier curve of degree n is defined by n+1 control points P₀, P₁, ..., P_n. The curve B(t) for t in [0, 1] is given by:

B(t) = Σⁿ_i=0 B_i,n(t) * P_i

where B_i,n(t) are the Bernstein polynomials:

B_i,n(t) = C(n, i) * tⁱ * (1-t)^n-i

and C(n, i) is the binomial coefficient "n choose i".

Quadratic Bezier (n=2): Defined by 3 control points P₀, P₁, P₂. B(t) = P₀(1-t)² + P₁(2t(1-t)) + P₂t²

Cubic Bezier (n=3): Defined by 4 control points P₀, P₁, P₂, P₃. This is very common in graphics. B(t) = P₀(1-t)³ + P₁(3t(1-t)²) + P₂(3t²(1-t)) + P₃t³

Bezier curves offer intuitive control: moving a control point affects the shape of the entire curve. They are also guaranteed to be smooth if the control points are arranged smoothly.

Illumination and Rendering

Illumination and rendering are the processes of determining how light interacts with surfaces in a 3D scene and generating the final 2D image. This involves simulating physical phenomena like light reflection, absorption, and scattering.

Light Sources

Different types of light sources are used in computer graphics:

• Ambient Light: Uniform light that illuminates all surfaces equally, providing a base level of brightness and preventing completely black areas.
• Directional Light: Light that comes from a single direction, like sunlight from a distant star. All parallel rays have the same direction.
• Point Light: Light emitted from a single point source, radiating in all directions. Its intensity decreases with distance.
• Spotlight: A cone of light emitted from a point source in a specific direction.

Surface Reflectance Models

These models describe how light reflects off a surface.

• Ambient Reflection: The portion of light that is scattered equally in all directions, regardless of the surface orientation.
• Diffuse Reflection: Light that is reflected equally in all directions from a rough surface. The intensity of diffuse reflection from a surface point depends on the angle between the surface normal and the light direction (Lambert's Cosine Law).
• Specular Reflection: Light that is reflected in a mirror-like fashion from a smooth surface. The angle of incidence equals the angle of reflection. This creates highlights on shiny surfaces.

Phong Reflection Model

The Phong reflection model is an empirical model that approximates the appearance of a surface under illumination by combining ambient, diffuse, and specular components.

The intensity of reflected light at a point P is given by: I = I_a * k_a + I_d * k_d * (N · L) + I_s * k_s * (R · V)ⁿ

Where:

• I_a: Ambient light intensity
• k_a: Ambient reflection coefficient
• I_d: Diffuse light intensity
• k_d: Diffuse reflection coefficient
• N: Surface normal vector
• L: Light direction vector
• (N · L): Dot product, representing the cosine of the angle between N and L. This term is zero if the surface faces away from the light.
• I_s: Specular light intensity
• k_s: Specular reflection coefficient
• R: Reflection vector (direction of perfect specular reflection)
• V: View vector (direction from the surface point to the viewer)
• (R · V)ⁿ: Controls the shininess of the surface. 'n' is the specular exponent; a higher 'n' means a smaller, sharper highlight.

Rendering Techniques

Rendering involves creating the final image. Common techniques include:

• Flat Shading: Calculates a single color for each polygon based on the surface normal and light direction. This results in a faceted appearance.
• Gouraud Shading: Calculates lighting at the vertices of a polygon and interpolates the colors across the polygon. This produces smoother results than flat shading.
• Phong Shading: Interpolates the surface normal across the polygon and calculates lighting at each pixel. This yields the smoothest results, with realistic highlights, but is computationally more expensive.
• Ray Tracing: A more physically accurate rendering technique that simulates the path of light rays from the camera into the scene. It can naturally handle reflections, refractions, and shadows.
• Radiosity: A technique that simulates the diffuse interreflection of light between surfaces. It is view-independent and good for scenes with complex indirect lighting, but is computationally intensive.