Computer graphics basics

In short

Computer graphics is the study of creating, storing, transforming and displaying pictures with a computer - from drawing a single line of pixels to rendering a shaded 3D scene. It rests on three pillars: scan-conversion algorithms (line, circle, fill), geometric transformations in homogeneous coordinates, and the viewing pipeline (clipping, projection, hidden-surface removal, shading). It is a full university paper in most CSE curricula, a regular GATE/UGC-NET source of 2-3 mark numericals on Bresenham and transformation matrices, and it is tested directly in interviews at gaming and visual-computing employers (Ubisoft Pune, Rockstar India, Zynga, Nvidia Bengaluru, Qualcomm, AMD, Samsung R&D, Adobe, Autodesk, ISRO visualisation groups) and indirectly in any front-end, CAD or embedded-display role.

Explained

Display hardware, raster fundamentals and colour

• Raster display: the screen is a rectangular grid of pixels; the picture is held as an intensity array in the frame buffer (refresh buffer) and swept out line by line by the video controller.
• Random-scan (vector) display: the beam traces only the line endpoints stored in a display list - smooth lines, no jaggies, but no area fill; obsolete except in plotters and oscilloscopes.
• Resolution: pixels across × down (e.g. 1920 × 1080). Aspect ratio = width : height of the display area (16:9, 4:3).
• Bit planes / colour depth: bits per pixel. 1 bpp = monochrome, 8 bpp = 256 colours, 24 bpp = "true colour" (8 bits each R, G, B), 32 bpp adds an 8-bit alpha (opacity) channel.
• Frame buffer size = resolution × bpp / 8 bytes. Refresh rate 60-144 Hz; below about 24-30 Hz the eye sees flicker. Interlacing draws odd then even scan lines to halve bandwidth.
• Colour look-up table (CLUT / palette): each pixel stores an index into a table of wide colour values - saves memory at the cost of simultaneous colours.
• Colour models: RGB additive (displays), CMY/CMYK subtractive (printing), HSV/HSL (hue, saturation, value - intuitive for artists), YIQ/YCbCr separates luminance from chrominance for broadcast and JPEG/MPEG compression.
• Devices: CRT (electron gun, phosphor, shadow mask) is historical; LCD/TFT, LED-backlit LCD and OLED dominate; input via mouse, tablet, touch, scanner; output via inkjet/laser printers and plotters.

Scan conversion - lines, circles and ellipses

• Scan conversion (rasterisation): choosing the pixel set that best approximates a mathematical primitive.
• DDA (digital differential analyser) line algorithm: compute m = Δy/Δx; if |m| ≤ 1 step x by 1 and y by m, else step y by 1 and x by 1/m; round each coordinate. Simple but uses floating-point addition and accumulates round-off error.
• Bresenham's line algorithm: integer-only. For |m| ≤ 1 with the line going up-right, start p₀ = 2Δy − Δx; at each step, if pₖ < 0 choose (xₖ+1, yₖ) and pₖ₊₁ = pₖ + 2Δy; else choose (xₖ+1, yₖ+1) and pₖ₊₁ = pₖ + 2Δy − 2Δx. The decision variable is the sign of the difference of the two candidate pixels' distances from the true line.
• Advantages of Bresenham: no floating point, no rounding, no multiplication inside the loop - hence used in hardware and in print/plotter firmware.
• Midpoint circle algorithm: exploits 8-way symmetry; plot only the 45° octant and mirror. Start at (0, r) with p₀ = 1 − r; if pₖ < 0 the midpoint is inside, pick (xₖ+1, yₖ) and pₖ₊₁ = pₖ + 2xₖ₊₁ + 1; else pick (xₖ+1, yₖ−1) and pₖ₊₁ = pₖ + 2xₖ₊₁ + 1 − 2yₖ₊₁.
• Midpoint ellipse algorithm: 4-way symmetry, two regions - region 1 while the slope magnitude is less than 1 (step x), region 2 after (step y); the region changes when 2ry²x ≥ 2rx²y.
• Antialiasing: jagged edges (aliasing) arise from sampling a continuous line on a discrete grid. Remedies: supersampling (sample sub-pixels and average), area sampling (intensity proportional to the pixel area covered - Gupta-Sproull), pixel-phasing on hardware that shifts beam position, MSAA/FXAA in GPUs.

Filling, polygons and clipping

• Scan-line polygon fill: for each scan line find intersections with all edges, sort x values, fill between pairs (odd-even parity rule). An edge table / active edge list with coherence (incremental x += 1/m) makes it fast. Vertex rule: count a vertex twice if both its edges lie on the same side of the scan line (a local maximum or minimum), once if they lie on opposite sides; horizontal edges are ignored.
• Inside tests: odd-even (even-odd) rule - a point is inside if a ray from it crosses an odd number of edges; non-zero winding number rule - count signed crossings; the two differ for self-intersecting polygons.
• Boundary fill: start from a seed pixel, recursively set neighbours until the boundary colour is reached. Flood fill: replace all connected pixels of a given interior colour. Both come in 4-connected and 8-connected forms; 4-connected fill leaks nothing through diagonal gaps but fails to fill through them.
• Point clipping: keep (x, y) if xwmin ≤ x ≤ xwmax and ywmin ≤ y ≤ ywmax.
• Cohen-Sutherland line clipping: assign each endpoint a 4-bit region code (bits: top, bottom, right, left). Both codes 0 → trivially accept; bitwise AND non-zero → trivially reject; otherwise clip against one boundary at a time using the line equation and repeat.
• Liang-Barsky line clipping: parametric form, solves for t ranges (t = q/p tests); more efficient as it computes only the final intersections.
• Midpoint subdivision clipping: repeatedly bisect the line - suited to hardware with fast shifters.
• Sutherland-Hodgman polygon clipping: clip the vertex list successively against each window edge; four output cases per edge pair (in-in: output second; in-out: output intersection; out-in: output intersection then second; out-out: output nothing). Can leave spurious connecting edges for concave polygons.
• Weiler-Atherton polygon clipping: follows polygon and window boundaries alternately - handles concave polygons and arbitrary clip regions correctly.
• Window-to-viewport transformation: map a world-coordinate window to a device viewport by translate-scale-translate; normalised device coordinates (NDC) in 0-1 make the pipeline device-independent.

Two-dimensional transformations and homogeneous coordinates

• Basic transformations: translation (add tx, ty), scaling (multiply by sx, sy about the origin), rotation (about the origin by θ, anticlockwise positive), reflection (about x axis, y axis, origin, y = x, y = −x) and shear (x-shear: x' = x + shx·y).
• Why homogeneous coordinates: translation is additive while scaling and rotation are multiplicative, so they cannot be combined by plain 2×2 matrices. Representing (x, y) as (x, y, 1) makes all three 3×3 matrix multiplications, so any sequence composes into one matrix.
• Composite transformation: multiply matrices in the order applied - with column vectors P' = Mn···M2·M1·P, the rightmost matrix acts first. Matrix multiplication is associative but not commutative (rotate-then-translate ≠ translate-then-rotate); two rotations about the same point, or two scalings, do commute.
• Rotation about an arbitrary pivot (xp, yp): T(xp, yp) · R(θ) · T(−xp, −yp). Scaling about a fixed point and reflection about an arbitrary line follow the same translate-to-origin, act, translate-back pattern.
• Rigid-body (Euclidean) transformation preserves lengths and angles (rotation + translation); affine transformation preserves parallelism and straight lines but not lengths or angles; projective transformation preserves only straight lines.

Three dimensions - transformations, projection and curves

• 3D transformations use 4×4 homogeneous matrices. Rotation about the z axis keeps z; about x keeps x; about y keeps y (note the sign pattern of sin θ reverses for the y-axis matrix). Rotation about an arbitrary axis = align the axis with a coordinate axis, rotate, undo the alignment.
• Projections: parallel (projectors parallel; preserves relative proportions - used in engineering drawing) and perspective (projectors meet at the centre of projection; gives foreshortening and vanishing points - looks realistic).
• Parallel sub-types: orthographic (projectors ⊥ plane) - multiview (top, front, side) and axonometric (isometric: all three axes equally foreshortened, scale ≈ 0.816; dimetric; trimetric); oblique - cavalier (no foreshortening, 45°) and cabinet (half-scale depth, 63.4°).
• Perspective sub-types by the number of vanishing points - one-point, two-point, three-point, depending on how many axes cut the view plane.
• Viewing pipeline (3D): modelling transformation → world coordinates → viewing (camera) transformation → view/eye coordinates → projection → clipping against the view volume (frustum for perspective, box for parallel) → normalisation → viewport/device coordinates.
• Curves: a Bezier curve of degree n is defined by n+1 control points with Bernstein basis blending functions; it passes through the first and last control points only, lies inside the convex hull, and is tangent to the first and last control polygon segments. Changing one control point changes the whole curve (global control).
• B-splines use piecewise basis functions with local control (moving a control point affects only a few spans), allow degree independent of the number of control points, and need a knot vector; NURBS (non-uniform rational B-splines) add weights and represent conics exactly - the CAD standard.
• Continuity: C⁰ (meeting), C¹ (equal tangent vectors), C² (equal second derivatives); geometric continuity G¹ needs only the same tangent direction.

Hidden surfaces, illumination and shading

• Visible-surface detection: object-space methods compare objects with each other (depth sorting, BSP); image-space methods decide per pixel (z-buffer, scan-line, ray casting).
• Z-buffer (depth buffer) algorithm: keep a depth value per pixel initialised to the far plane; for each polygon, compute depth at each covered pixel and overwrite colour and depth if nearer. Advantages: trivial to implement, no sorting, handles any geometry; drawbacks: extra memory, handles transparency poorly, suffers z-fighting when precision is low.
• Painter's / depth-sort algorithm: draw polygons from farthest to nearest; fails for cyclically overlapping or interpenetrating polygons, which must be split.
• Back-face culling: a polygon faces away if the dot product of its outward normal with the view vector is ≥ 0 - discards roughly half the polygons of a closed convex solid cheaply, but cannot resolve occlusion between different objects.
• Area subdivision (Warnock) recursively splits the screen until each region is trivially simple; scan-line and BSP-tree methods suit static scenes; ray casting handles any surface and gives shadows and reflections naturally.
• Illumination model (Phong): ambient + diffuse + specular. Diffuse (Lambertian) intensity ∝ cos θ between the surface normal and the light direction - independent of the viewer. Specular highlight ∝ cosⁿˢ φ between the reflected-light vector and the view vector; large specular exponent nₛ gives a small, sharp highlight.
• Shading methods: flat (constant) shading - one colour per polygon, fastest, shows Mach-band edges; Gouraud (intensity-interpolation) - compute intensity at vertices and interpolate across the polygon; smooth but can miss a highlight inside a polygon; Phong (normal-vector interpolation) - interpolate normals and shade per pixel; best highlights, highest cost. Modern GPUs do Phong-style per-fragment shading in the pixel shader.
• Texture mapping pastes an image onto a surface (needs perspective-correct interpolation and mip-maps to avoid aliasing); bump/normal mapping perturbs normals to fake relief; shadow maps and ray tracing add global effects.
• Software and standards: OpenGL (cross-platform; the state machine and fixed pipeline are examined), Vulkan, DirectX, WebGL/WebGPU, GKS and PHIGS (older ISO standards, still in syllabi); SRGP/SPHIGS in textbooks. File formats: BMP, PNG, JPEG (raster), SVG (vector), OBJ, STL, glTF (3D).
• Animation: keyframing with in-betweening, double buffering to avoid tearing, morphing, kinematics and inverse kinematics, particle systems.

Key points

• Frame buffer - memory holding one intensity value per pixel; its size = resolution × bits per pixel.
• Aspect ratio - width-to-height ratio of the display or image; distorting it stretches circles into ellipses.
• DDA - incremental line algorithm using floating-point addition; simpler than Bresenham but slower and less accurate.
• Bresenham - integer decision-parameter line algorithm; p₀ = 2Δy − Δx for a gentle up-right line.
• Midpoint circle - uses 8-way symmetry with p₀ = 1 − r; only one octant is actually computed.
• Aliasing - staircase artefact from sampling; cured by supersampling or area-based antialiasing, not by higher brightness.
• Homogeneous coordinates - adding a third (2D) or fourth (3D) coordinate turns translation into matrix multiplication so transformations compose.
• Non-commutativity - the order of composite transformations matters; the rightmost matrix acts first on a column vector.
• Rotation about a pivot - translate the pivot to the origin, rotate, translate back.
• Window-to-viewport - scale factors sx = (xvmax − xvmin)/(xwmax − xwmin) and sy similarly; unequal factors distort shapes.
• Cohen-Sutherland - 4-bit region codes; AND ≠ 0 rejects, both codes 0 accepts.
• Sutherland-Hodgman - clips a polygon edge-list against each window boundary in turn; Weiler-Atherton is needed for concave cases.
• Parallel vs perspective - parallel preserves size and parallelism; perspective foreshortens and creates vanishing points.
• Bezier - passes through only the end control points, lies in the convex hull, has global control; B-spline gives local control.
• Z-buffer - per-pixel depth comparison; no sorting needed, memory-heavy, polygons processed in any order.
• Back-face culling - normal·view ≥ 0 means hidden; removes about half the faces of a closed solid.
• Shading order of cost - flat < Gouraud < Phong; Phong interpolates normals, Gouraud interpolates intensities.
• Illumination terms - ambient (constant), diffuse (cos θ, view-independent), specular (cosⁿˢ φ, view-dependent).

Formulas and examples

Example 1 - Frame buffer and bandwidth. A 1920 × 1080 display at 24 bits per pixel, refreshed at 60 Hz.

• Pixels per frame = 1920 × 1080 = 2,073,600.
• Bits per frame = 2,073,600 × 24 = 49,766,400 bits; bytes = 49,766,400 / 8 = 6,220,800 bytes ≈ 5.93 MiB (≈ 6.22 MB in decimal units).
• Refresh bandwidth = 6,220,800 × 60 = 373,248,000 bytes/s ≈ 373 MB/s.
• With a 32 bpp buffer (alpha added), size = 2,073,600 × 4 = 8,294,400 bytes ≈ 7.91 MiB, bandwidth ≈ 498 MB/s.
• Double buffering doubles the storage, not the refresh bandwidth.

Example 2 - Bresenham line from (20, 10) to (30, 18). Δx = 10, Δy = 8, m = 0.8 ≤ 1, so step x. p₀ = 2Δy − Δx = 16 − 10 = 6. Increments: 2Δy = 16, 2Δy − 2Δx = 16 − 20 = −4.

Pixels: (20,10), (21,11), (22,12), (23,12), (24,13), (25,14), (26,15), (27,16), (28,16), (29,17), (30,18) - 11 pixels, y rising by 8 over 10 x-steps, as the slope requires.

Example 3 - Midpoint circle, r = 10, first octant. p₀ = 1 − 10 = −9, start (0, 10).

Octant pixels: (0,10), (1,10), (2,10), (3,10), (4,9), (5,9), (6,8), (7,7); the other 48 points follow by reflecting x and y.

Example 4 - Rotating a triangle 90° anticlockwise about the point (2, 2). Vertices A(4, 2), B(6, 2), C(4, 5). With θ = 90°, cos θ = 0, sin θ = 1, so the composite gives x' = 2 − (y − 2) = 4 − y and y' = 2 + (x − 2) = x.

• A(4, 2) → x' = 4 − 2 = 2, y' = 4 → A'(2, 4).
• B(6, 2) → x' = 4 − 2 = 2, y' = 6 → B'(2, 6).
• C(4, 5) → x' = 4 − 5 = −1, y' = 4 → C'(−1, 4).
• Check: AB had length 2 and was horizontal; A'B' has length 2 and is vertical - a rigid-body rotation preserves length and turns the direction by 90°. Note the pivot (2, 2) itself maps to (2, 2).

Example 5 - Window-to-viewport mapping. Window (xwmin, ywmin) = (0, 0) to (10, 10); viewport (0, 0) to (400, 300) device pixels. Map the world point (6, 4).

• sx = (400 − 0)/(10 − 0) = 40, sy = (300 − 0)/(10 − 0) = 30.
• xv = 0 + (6 − 0) × 40 = 240, yv = 0 + (4 − 0) × 30 = 120.
• Because sx ≠ sy, a circle in the window becomes an ellipse on screen; keeping the viewport at 400 × 400 (sx = sy = 40) preserves shape.

Example 6 - Perspective projection. Centre of projection at z = −d with d = 50, projection plane z = 0. A point P(30, 20, 100).

• Divisor = 1 + z/d = 1 + 100/50 = 3. xp = 30/3 = 10, yp = 20/3 ≈ 6.67.
• A nearer point Q(30, 20, 25): divisor = 1.5, xp = 20, yp ≈ 13.33 - halving the distance from the centre of projection (150 → 75) doubles the projected size, which is foreshortening.

/* Bresenham line, |m| <= 1, x1 < x2, integer only */
void bres_line(int x1,int y1,int x2,int y2){
    int dx = x2-x1, dy = y2-y1;
    int sy = (dy >= 0) ? 1 : -1;          /* handle downward lines */
    dy = (dy >= 0) ? dy : -dy;
    int p = 2*dy - dx, x = x1, y = y1;
    setpixel(x,y);
    while (x < x2) {
        x++;
        if (p < 0) p += 2*dy;
        else { y += sy; p += 2*dy - 2*dx; }
        setpixel(x,y);
    }
}

Where it is used

• Gaming and real-time 3D: engines (Unity, Unreal) at Ubisoft Pune/Mumbai, Rockstar India (Bengaluru), Zynga, Dream11 and Nazara - roles such as graphics programmer, technical artist, rendering engineer; transformation matrices and shading models are asked directly in these interviews.
• GPU and silicon: Nvidia (Pune, Bengaluru, Hyderabad), AMD, Qualcomm (Adreno GPU), Arm (Mali), Intel and Samsung R&D Bengaluru/Noida hire for rasteriser, driver and shader-compiler work built on exactly these pipeline stages.
• CAD, CAM and engineering visualisation: Autodesk, Dassault Systèmes, Siemens, Ansys and Indian product-design firms use NURBS surfaces, projections and hidden-surface removal; STL and glTF outputs drive 3D printing.
• Media, VFX and animation: DNEG India, Technicolor, MPC and Prime Focus (Mumbai, Chennai, Bengaluru, Hyderabad) and ad/animation studios - rendering, compositing, texture and shading pipelines.
• GIS, remote sensing and simulation: ISRO/NRSC visualisation, flight and driving simulators, HAL and DRDO display systems, Survey of India mapping - clipping, window-to-viewport and projection work at scale.
• Everyday software: web and app UI rendering (WebGL, Canvas, SVG, Flutter/Skia), medical imaging (CT/MRI volume rendering), data visualisation dashboards, AR/VR headsets and digital twins.

Interview questions

• Q: Why is Bresenham's algorithm preferred over DDA? A: It uses only integer additions, subtractions and comparisons with no rounding, so it is faster, free of accumulated round-off and easy to implement in hardware.
• Q: Why are homogeneous coordinates needed at all? A: Translation is an addition while scaling and rotation are multiplications; adding an extra coordinate makes translation a matrix multiplication too, so a whole sequence of transformations collapses into one matrix.
• Q: Does the order of transformations matter? A: Yes - matrix multiplication is not commutative, so rotate-then-translate differs from translate-then-rotate; only special cases such as two rotations about the same point, or two scalings, commute.
• Q: How do you rotate an object about a point other than the origin? A: Translate that point to the origin, apply the rotation, then translate back: T(xp,yp)·R(θ)·T(−xp,−yp).
• Q: How does Cohen-Sutherland decide quickly whether to keep or discard a line? A: Each endpoint gets a 4-bit region code; if both codes are 0000 the line is wholly inside and accepted, and if the bitwise AND of the codes is non-zero both endpoints lie outside the same boundary so the line is rejected.
• Q: What is the difference between the odd-even rule and the winding-number rule? A: Odd-even counts ray crossings and calls a point inside if the count is odd; the winding rule sums signed crossings - they classify holes in self-intersecting polygons differently.
• Q: Explain the z-buffer algorithm and one drawback. A: It stores a depth per pixel and keeps the colour of the nearest surface found so far, needing no sorting; drawbacks are the extra depth memory, poor handling of transparency, and z-fighting when depth precision is insufficient.
• Q: When does the painter's algorithm fail? A: When polygons overlap cyclically or interpenetrate, no back-to-front ordering exists and the polygons must be split.
• Q: Gouraud or Phong shading - what exactly differs? A: Gouraud interpolates intensities computed at the vertices, which can miss a specular highlight inside a polygon; Phong interpolates the normal vectors and evaluates the illumination model per pixel, giving correct highlights at higher cost.
• Q: Does a Bezier curve pass through all its control points? A: No - only through the first and last; the rest pull the curve, which always stays within the convex hull of the control polygon.
• Q: Why would you choose a B-spline over a Bezier curve? A: B-splines give local control (moving one control point affects only nearby spans) and let the degree be chosen independently of the number of control points.
• Q: What causes aliasing and how is it reduced? A: Sampling a continuous primitive on a discrete pixel grid below the needed rate; it is reduced by supersampling, area sampling with intensity weighting, or hardware MSAA - not by changing colour or brightness.
• Q: What does back-face culling achieve, and what does it not? A: It cheaply discards faces whose normal points away from the viewer, roughly halving the polygons of a closed solid, but it cannot resolve one object occluding another.

Common mistakes

• Writing Bresenham's initial parameter as 2Δx − Δy, or using the |m| ≤ 1 version for steep lines instead of swapping the roles of x and y.
• Multiplying composite transformation matrices in the wrong order and forgetting that with column vectors the rightmost matrix acts first.
• Rotating about an arbitrary point by applying R(θ) directly, without the translate-rotate-translate-back sandwich.
• Using degrees in a program where the library's sin and cos expect radians.
• Treating Bezier curves as interpolating all control points, or claiming they have local control.
• Confusing Gouraud with Phong shading, and confusing the Phong illumination model with Phong shading (the model computes intensity; the shading method interpolates normals).
• Choosing unequal x and y scale factors in the window-to-viewport mapping and then wondering why circles appear as ellipses.
• Forgetting the 8-way symmetry in the circle algorithm and computing all 360° of points, or testing the stopping condition as x > r instead of x ≥ y.

Related topics

Parallel computing and GPUs · Computer organisation and architecture · Linear algebra and matrices · Image processing and computer vision · Numerical methods and interpolation · Data structures (trees for BSP and spatial indexing)