Module - 4: Computer Graphics Algorithms
Computer Science Engineering
1 Cohen-Sutherland Line-Clipping Algorithm
The Cohen-Sutherland algorithm is a popular and efficient line-clipping algorithm designed to
speed up processing by rapidly identifying lines that are completely inside or completely outside
the viewing window.
1.1 Region Codes (Outcodes)
The viewing area is defined by four boundaries: Top (ymax ), Bottom (ymin ), Right (xmax ), and Left
(xmin ). The 2D space is divided into 9 regions. Every endpoint of a line is assigned a 4-bit binary
code (TBRL - Top, Bottom, Right, Left).
• Bit 1 (Left): Set if x < xmin
• Bit 2 (Right): Set if x > xmax
• Bit 3 (Bottom): Set if y < ymin
• Bit 4 (Top): Set if y > ymax
1.2 Algorithm Logic
Step 1: Calculate region codes for both endpoints P1 and P2 .
Step 2 (Trivial Acceptance): If both codes are 0000, the line is completely inside. Draw it.
Step 3 (Trivial Rejection): If code(P1 ) & code(P2 ) 6= 0 (bitwise AND), both points share an outside
region. Discard the line.
Step 4 (Clipping): If neither, select an endpoint that is outside (code 6= 0000).
Step 5 (Intersection Calculation): Find the intersection with the boundary using m = (y2 −
y1 )/(x2 − x1 ).
• Left/Right Edge (x = xw ): y = y1 + m(xw − x1 )
• Top/Bottom Edge (y = yw ): x = x1 + (yw − y1 )/m
Step 6: Replace the outside point with the intersection point and repeat.
1
1.3 Step-by-Step Example
Window: xmin = 0, xmax = 10, ymin = 0, ymax = 10.
Line: P1 (−5, 3) to P2 (15, 12).
1. Codes: P1 (−5, 3) → 0001 (Left). P2 (15, 12) → 1010 (Top-Right).
2. Check: 0001 & 1010 = 0000. Not trivially rejected.
3. Clip P1 (Left Edge x = 0): m = 9/20 = 0.45. y = 3 + 0.45(0 − (−5)) = 5.25. New P10 = (0, 5.25).
4. Clip P2 (Right Edge x = 10): y = 5.25 + 0.45(10 − 0) = 9.75. New P20 = (10, 9.75).
5. Final Result: Line from (0, 5.25) to (10, 9.75).
2 Bresenham’s Line-Drawing Algorithm
Bresenham’s algorithm is an incremental scan-conversion algorithm that determines which pix-
els to plot to approximate a straight line using integer arithmetic.
2.1 Logic (Slope 0 < m < 1)
At step xk , we have (xk , yk ). The next pixel is either E(xk + 1, yk ) or N E(xk + 1, yk + 1). We use a
decision parameter pk :
• Initial: p0 = 2∆y − ∆x
• If pk < 0: Next pixel is (xk + 1, yk ). pk+1 = pk + 2∆y.
• If pk ≥ 0: Next pixel is (xk + 1, yk + 1). pk+1 = pk + 2∆y − 2∆x.
2.2 Advantages over DDA
• Integer Arithmetic: Uses only addition, subtraction, and bit-shifting.
• Precision: No cumulative floating-point round-off error (drift).
• Hardware Implementation: Efficiently implemented in simple hardware or firmware.
3 Midpoint Circle Algorithm
This algorithm determines the closest integer pixel to the circle boundary x2 + y 2 = r2 by ana-
lyzing the first octant.
3.1 Algorithm Steps
1. Start: Set (x0 , y0 ) = (0, r). Initial p0 = 1 − r.
2. Loop (While x ≤ y):
• If pk < 0: Next (x + 1, y), pk+1 = pk + 2x + 3.
• If pk ≥ 0: Next (x + 1, y − 1), pk+1 = pk + 2x − 2y + 5.
3. Symmetry: Plot 8 points for every (x, y) using octant symmetry.
2
4 Liang-Barsky vs. Cohen-Sutherland
Feature Cohen-Sutherland Liang-Barsky
Basis Region codes / outcodes. Parametric equations of a line.
Operations Repeated clipping per edge. Computes all intersections at once.
Efficiency Fast for trivial cases. Faster for lines crossing boundaries.
3D Extension Very straightforward. More complex logic.
5 Vertex to Fragment Conversion Tasks
1. Vertex Processing: Geometric transformations (Model, View, Projection).
2. Primitive Assembly: Connecting vertices into triangles/lines and clipping.
3. Rasterization: Converting continuous shapes into discrete fragments.
4. Fragment Processing: Texturing, Lighting, and Depth/Scissor tests.
6 Frame-Buffer Implementation
The frame buffer stores the image in high-speed memory.
• Structure: 2D array (screen pixels) stored linearly.
• Address Calculation: Address = Base + y × Stride + x × BytesP erP ixel.
• Double Buffering: Uses a Front Buffer (display) and Back Buffer (render) to prevent flick-
ering.
7 Parallel Processing in Graphics
• Data Partitioning: Screen is divided into regions; each processor handles one.
• Functional Partitioning: Different pipeline stages run on different cores.
• Pixel-Level Parallelism: Modern GPUs evaluate line equations for thousands of pixels
simultaneously.
8 Rendering Strategies
Object-Order (Object-Oriented): Iterate over objects, project them, and fill pixels (e.g., OpenGL).
Image-Order (Image-Oriented): Iterate over pixels and cast rays to find objects (e.g., Ray Trac-
ing).
3
9 OpenGL Implementation: Midpoint Circle Algorithm
1 # include <GL/glut.h>
2 # include <iostream >
3
4 void setPixel (int x, int y) {
5 glBegin ( GL_POINTS );
6 glVertex2i (x, y);
7 glEnd ();
8 }
9
10 void plotSymmetricPoints (int xc , int yc , int x, int y) {
11 setPixel (xc + x, yc + y); setPixel (xc - x, yc + y);
12 setPixel (xc + x, yc - y); setPixel (xc - x, yc - y);
13 setPixel (xc + y, yc + x); setPixel (xc - y, yc + x);
14 setPixel (xc + y, yc - x); setPixel (xc - y, yc - x);
15 }
16
17 void midpointCircle (int xc , int yc , int r) {
18 int x = 0, y = r;
19 int p = 1 - r;
20 plotSymmetricPoints (xc , yc , x, y);
21 while (x < y) {
22 x++;
23 if (p < 0) p += 2 * x + 1;
24 else { y--; p += 2 * (x - y) + 1; }
25 plotSymmetricPoints (xc , yc , x, y);
26 }
27 }
28
29 void display () {
30 glClear ( GL_COLOR_BUFFER_BIT );
31 glColor3f (1.0 , 0.0, 0.0);
32 midpointCircle (320 , 240, 100);
33 glFlush ();
34 }