Line Drawing & Clipping — CSE Graphics Notes

Overview

Core concept & historical context

Eight‑Way Symmetry

Line drawing

A geometric shortcut that lets a line‑drawing routine written for a single octant (Zone 0) be reused for lines pointing in any of the eight directions around the origin, by reflecting/rotating coordinates into Zone 0, drawing there, then mapping the result back.

It grew out of the same "exploit symmetry to avoid recomputation" idea used in Bresenham's circle algorithm, where one computed octant is mirrored eight times.

Cohen‑Sutherland Algorithm

Line clipping

One of the earliest (1967‑68) and most widely taught line‑clipping algorithms, developed by Danny Cohen and Ivan Sutherland. It encodes the position of a point relative to a rectangular clip window using a 4‑bit outcode, enabling fast trivial accept/reject decisions before doing any expensive intersection math.

Cyrus‑Beck Algorithm

Line clipping

A more general, parametric line‑clipping algorithm (Cyrus & Beck, 1978) that represents the line with a parametric equation and uses vector dot products with boundary normals to find the exact parametric range that lies inside the clip region. Because it relies only on edges and normals, it extends naturally to convex polygons and 3‑D polyhedra.

Why study both clipping algorithms together? Cohen‑Sutherland is fast and intuitive for simple rectangular windows; Cyrus‑Beck is more mathematically general and works for any convex clipping region. Comparing them highlights the classic trade‑off between specialized speed and general applicability in graphics algorithm design.

Eight‑Way Symmetry

Zones · FindZone · Conversion · Example

Core Idea

The midpoint line‑drawing algorithm is normally derived only for lines in the first octant (slope between 0 and 1, moving right and up). Instead of re‑deriving the algorithm for every possible direction, the plane around a line's starting point is divided into 8 zones (octants). Any line segment is first classified into a zone, then its endpoints are mathematically transformed into the equivalent line in Zone 0, drawn with the standard midpoint algorithm, and finally the computed pixels are transformed back into the original zone.

Mid‑Point Line Drawing Algorithm with Eight‑Way Symmetry

Input: 2 endpoints — (x₀, y₀) and (x₁, y₁)

Step 1:
  • Find the Zone

Step 2:
  • If (zone == 0) {
      Apply Mid‑Point Line Drawing Algorithm
  }
  Else {
      • Convert the zone to → Zone 0 (find dy, dx from start         and end points and check the conditions)
      • Apply Mid‑Point Line Drawing Algorithm
      • Convert to the Original zone
  }

Fig. The 8 zones around a line's start point. Pink = zone number, dark = dx/dy classification, amber italic = the coordinate swap used by ConvertToZone0 / OriginalZone for that zone.

Step 1 — FindZone(): classifying dx, dy

Given endpoints (x₁,y₁) and (x₂,y₂), compute dx = x₂ − x₁ and dy = y₂ − y₁. The zone is decided first by which axis dominates (|dx| > |dy| vs |dy| ≥ |dx|), then by the signs of dx and dy.

Zone	Condition	Zone	Condition
0	dx>0, dy≥0, \|dx\|>\|dy\|	4	dx<0, dy≤0, \|dx\|>\|dy\|
1	dx>0, dy>0, \|dy\|>\|dx\|	5	dx<0, dy<0, \|dy\|>\|dx\|
2	dx<0, dy>0, \|dy\|>\|dx\|	6	dx>0, dy<0, \|dy\|>\|dx\|
3	dx<0, dy>0, \|dx\|>\|dy\|	7	dx>0, dy<0, \|dx\|>\|dy\|

Worked check: for endpoints (−50,−15) → (100,35): dx = 150 > 0, dy = 50 > 0, and |dx| > |dy| ⇒ Zone = 0 — the line is already in the "home" octant, so no transformation is needed before drawing.

Step 2 — Convert Zone M → Zone 0

Each zone has a simple coordinate swap/negation that maps it onto Zone 0 (first octant, |dx| ≥ dy ≥ 0):

Zone	(X,Y) → Zone 0
1	(Y, X)
2	(Y, −X)
3	(−X, Y)
4, 5, 6, 7	Mirror of 3, 2, 1, 0 (left as exercise / DIY in source slides)

Step 3 — Convert Zone 0 → back to Zone M

After the midpoint algorithm produces pixels (x, y) in Zone 0, the inverse mapping restores the original zone:

Zone	(X,Y) → Original Zone
1	(Y, X)
2	(−Y, X)
3	(−X, Y)
4, 5, 6, 7	Symmetric inverses (DIY in source slides)

Full Pipeline

FindZone — classify the input line's zone M from its dx, dy.
ConvertToZone0 — remap both endpoints into Zone 0 coordinates.
Midpoint Line Algorithm — run the standard decision‑variable (D, ΔNE, ΔE) midpoint algorithm on the Zone‑0 line, generating pixels while x ≤ x₂ using the classic increment/decision rule.
OriginalZone — map every generated pixel back to zone M using the inverse transform, so it is plotted in the correct location on screen.

Worked Example

Find the first pixels of the line from (−10,−20) to (−20,70).

Step 1 (zone): dx = −10, dy = 90, |dy| > |dx| and dx<0, dy>0 ⇒ Zone 2.

Step 2 (to Zone 0): using (x=Y, y=−X): start (−10,−20)→(−20,10); end (−20,70)→(70,20).

Step 3 (midpoint on Zone 0): dx′=90, dy′=10, D=2(10)−90=−70, ΔNE=2(10−90)=−160, ΔE=2(10)=20 — the standard decision loop is then run to generate pixels such as (−20,10), (−19,10), (−18,10) …

Step 4 (back to Zone 2, x=−Y′, y=X′): pixels (−20,10)→(−10,−20), (−19,10)→(−10,−19), (−18,10)→(−10,−18), … reproducing the true pixels of the original line.

Cohen‑Sutherland Line Clipping

Region codes · Trivial accept/reject · Boundary intersection

What is Clipping?

Clipping removes (or trims) the parts of a picture that fall outside a rectangular clip window so that only the portion inside the visible viewport is drawn — the same idea as a physical picture frame cutting off everything outside its edges. In raster graphics, clipping can be done analytically (before scan conversion, for lines & polygons), during scan conversion (scissoring — used for curves, where only checking extrema suffices), or while writing individual pixels (when only a few pixels of an otherwise‑fitting shape stick out).

Fig. 9‑region outcode map. Bit order: above(3) below(2) right(1) left(0).

Fig. calculate_outcode() bit‑assignment rule.

Fig. Point clipping — only points strictly within [x_min,x_max] × [y_min,y_max] survive; the rest are clipped. This is the same inequality the outcode bits are built from.

Region Code / Outcode

World space is divided into 9 regions by extending the window's 4 edges. Each region gets a unique 4‑bit code:

Bit 3	Bit 2	Bit 1	Bit 0
Above	Below	Right	Left

if (x < x_min) bit0 = 1 (left)
if (x > x_max) bit1 = 1 (right)
if (y < y_min) bit2 = 1 (below)
if (y > y_max) bit3 = 1 (above)

The window itself always has outcode 0000.

Extension to 3‑D

The same idea extends to a 6‑bit outcode for 3‑D clipping against a box, adding near and far planes along z:

5	4	3	2	1	0
Near	Far	Above	Below	Right	Left

Bits 4–5 are set by comparing z against z_min and z_max the same way x and y are compared in 2‑D.

Trivial Acceptance & Trivial Rejection

Trivial Acceptance

A line is completely inside the window (and can be drawn as‑is) when both endpoint outcodes are zero:

OC1 == OC2 == 0000

Trivial Rejection

A line is completely outside the window (and can be discarded entirely) when both endpoints share at least one "outside" bit — i.e. they are both above, both below, both left, or both right of the window:

(OC1 AND OC2) != 0000

If neither condition holds, the line is only partially inside/outside and must actually be clipped against one boundary at a time.

Algorithm (theory outline)

Compute outcodes OC1, OC2 for both endpoints.
If both are 0000 → accept the whole segment.
If OC1 AND OC2 ≠ 0000 → reject the whole segment.
Otherwise pick whichever endpoint has a non‑zero outcode, find where the line crosses the boundary corresponding to that non‑zero bit, replace that endpoint with the intersection point, and recompute its outcode.
Repeat from step 2 until the line is trivially accepted or rejected.

Boundary Intersection Formulas

Using the line's slope m = (y₂ − y₁) / (x₂ − x₁), the exact crossing point on each boundary is found analytically:

Boundary	Fixed coordinate	Solve for the other coordinate
Left	x = x_min	y = y₁ + m·(x_min − x₁)
Right	x = x_max	y = y₁ + m·(x_max − x₁)
Bottom	y = y_min	x = x₁ + (1/m)·(y_min − y₁)
Top	y = y_max	x = x₁ + (1/m)·(y_max − y₁)

Worked Example

Clip region (0,0)–(300,200). Line: (50,−125) to (−100,225).

OC1 (50,−125): y < 0 → below ⇒ 0100. OC2 (−100,225): x < 0 → left, y > 200 → above ⇒ 1001.

OC1 AND OC2 = 0000 (not trivially rejected) and neither is 0000 (not trivially accepted) → clipping is required. Clipping P1 against the bottom boundary (slope m = −7/3) moves P1 to (−3.57, 0), whose new outcode is 0001 (left). Now OC1 AND OC2 = 0001 → trivially rejected: both points share the "left" bit, so the visible line lies entirely to the left of the window and the whole segment is discarded.

Visual Walkthrough — General Case

The same iterative logic shown visually for a line whose endpoints start in opposite corner regions, [0101] (left+below) and [1010] (right+above):

Step A — both endpoints outside, opposite corners. OC1 AND OC2 = 0000 → not trivially rejected.

Step B — clip P1 against the LEFT boundary → P1' still outside (top bit set).

Step C — clip against the TOP boundary → P1'' is [0000]. Now clip P2 next.

Step D — both outcodes now 0000 → trivially accepted. Bold segment is the clipped line.

When it Works Best — and its Limitations

Best for

Very large clip regions — most lines are trivially accepted.
Very small clip regions — most lines are trivially rejected.

Weaknesses

Only works for rectangular clip windows.
Can perform unnecessary clipping iterations for lines that snake in and out near the window.
The order in which boundaries are tested can change the number of iterations needed to finish.

Cyrus‑Beck Line Clipping

Parametric line · Normals · PE / PL classification

Parametric Equation of a Line

Any point on the segment from P₀(x₀,y₀) to P₁(x₁,y₁) can be written as a function of a single parameter t:

P(t) = P₀ + t·(P₁ − P₀) = (x₀ + t(x₁−x₀), y₀ + t(y₁−y₀))

At t = 0, P(t) = P₀; at t = 1, P(t) = P₁. All points with 0 ≤ t ≤ 1 lie strictly inside the segment; t‑values outside that range lie on the infinite extension of the line, beyond its endpoints.

Example: for P₀(1,1), P₁(5,9): P(t) = (1+4t, 1+8t). P(0)=(1,1), P(1)=(5,9), P(0.5)=(3,5), P(0.25)=(2,3) — all inside the segment, while P(−0.3) and P(1.3) fall outside it.

Fig. P(t) sweeps the segment as t goes from 0 to 1.

Fig. An intersection only counts if its t falls within [0,1].

Direction Vector & Boundary Normals

The direction vector of the line is D = P₁ − P₀. Each of the 4 clip‑window boundaries has an outward‑pointing unit normal:

Boundary	Normal N
Left	(−1, 0)
Right	(1, 0)
Top	(0, 1)
Bottom	(0, −1)

Fig. Outward unit normals for a rectangular window.

Potentially Entering (PE) vs Leaving (PL)

At each boundary intersection, the sign of the dot product between the normal N and the direction D classifies the crossing:

N·D < 0 → Potentially Entering (PE)
N·D > 0 → Potentially Leaving (PL)

Geometrically: if the angle between N and D is more than 90°, the line is heading into the clip region at that boundary (PE); if less than 90°, it's heading out (PL).

Fig. The line crosses the left boundary while entering (PE) and the top boundary while leaving (PL) the clip window.

Deriving the Intersection Parameter t

A boundary edge Eᵢ passes through point P_Eᵢ with outward normal Nᵢ. The intersection of the line with that edge's infinite extension satisfies Nᵢ · [P(t) − P_Eᵢ] = 0. Substituting the parametric line equation and solving for t gives the general formula:

t = ( Nᵢ · [P₀ − P_Eᵢ] ) / ( −Nᵢ · D ), where D = P₁ − P₀

Applying this formula to each of the 4 axis‑aligned boundaries simplifies to:

Boundary	t formula
Left	t = −(x₀ − x_min) / (x₁ − x₀)
Right	t = −(x₀ − x_max) / (x₁ − x₀)
Top	t = −(y₀ − y_max) / (y₁ − y₀)
Bottom	t = −(y₀ − y_min) / (y₁ − y₀)

Algorithm (theory outline)

Pre‑compute the normal Nᵢ and a boundary point P_Eᵢ for each of the 4 (or more, for a polygon) clip edges.
If P₁ = P₀ the segment is degenerate — clip it as a single point.
Initialize t_E = 0 and t_L = 1.
For each boundary where Nᵢ·D ≠ 0 (i.e. not parallel to that edge), compute t and classify it as PE or PL from the sign of Nᵢ·D.
Keep the largest PE value as t_E, and the smallest PL value as t_L.
If t_E > t_L, the whole line is outside the clip region → discard it. Otherwise the visible segment runs from P(t_E) to P(t_L).

Worked Example

Clip window (0,0)–(300,200). Line: (−250,200) to (150,100), so D = (400,−100).

Boundary	Nᵢ	Nᵢ·D	t	PE / PL
Left	(−1,0)	−400	0.625	PE
Right	(1,0)	400	1.375	PL
Bottom	(0,−1)	100	2.0	PL
Top	(0,1)	−100	0.0	PE

t_E = max(0.625, 0.0) = 0.625; t_L = min(1.375, 2.0, 1) = 1. Since t_E ≤ t_L, the visible segment runs from P(0.625) = (0, 137.5) to P(1) = (150, 100).

Strength & Key Limitation

Advantages

Works for any convex polygon clip region, not just rectangles.
Generalizes directly to 3‑D clipping against convex polyhedra by adding more boundary planes/normals.

Limitation

It fails for concave clip polygons: a line can cross a concave boundary multiple times, producing a PE t‑value that is numerically larger than a PL t‑value (t_E > t_L) even though part of the line really is visible. The whole segment then gets incorrectly discarded.

Fig. Concave clip region: t_E = t3, t_L = t2, and t_E > t_L, so the whole line is incorrectly discarded even though the segments near t1–t2 and t3–t4 should be visible.

Side‑by‑Side Comparison

Cohen‑Sutherland vs Cyrus‑Beck

Cohen‑Sutherland

Representation: 4‑bit region outcodes.
Core test: bitwise AND / equality on outcodes.
Clip region: rectangular window only.
Best case: very large or very small windows (many trivial accepts/rejects).
Worst case: lines that repeatedly cross window edges, needing several intersection recomputations.
Extends to 3‑D: yes, with a 6‑bit outcode.
Conceptually: simpler to teach and implement first.

Cyrus‑Beck

Representation: parametric line + boundary normal vectors.
Core test: dot product sign (Nᵢ·D) and t_E vs t_L comparison.
Clip region: any convex polygon (or polyhedron in 3‑D).
Best case: non‑rectangular / arbitrary convex clip shapes.
Worst case: concave clip regions — algorithm gives incorrect results.
Extends to 3‑D: yes, naturally, via more clip planes.
Conceptually: more general, more linear‑algebra‑heavy.

Summary Table

Aspect	Cohen‑Sutherland	Cyrus‑Beck
Year / Authors	Danny Cohen & Ivan Sutherland	Cyrus & Beck (1978)
Underlying math	Boolean logic on region codes	Parametric equations & vector dot products
Rectangular window only?	Yes	No — works for any convex shape
Handles concave clip regions	N/A (rectangle is always convex)	No — fails on concave polygons
Typical use case	Screen/viewport clipping in 2‑D raster systems	General polygon & 3‑D polyhedron clipping
Performance sweet spot	Extreme window sizes (very large / very small)	Any convex region, uniform cost per boundary

Additional Details & Practical Notes

Edge cases · related concepts

Point Clipping (Foundational Rule)

Before line clipping, the simplest case is point clipping: a point (x,y) is not clipped (i.e. it is kept) only if it satisfies both range checks:

x_min ≤ x ≤ x_max AND y_min ≤ y ≤ y_max

Otherwise the point is discarded. This same inequality underlies the outcode bits used in Cohen‑Sutherland.

Aliasing & Antialiasing (context for line drawing)

Because rasterized lines approximate a continuous entity with discrete pixel samples, an all‑or‑nothing "each pixel is either colored or left unchanged" approach produces a visible jagged / staircase effect known as aliasing. Antialiasing techniques such as unweighted area sampling reduce this by shading each pixel with an intensity proportional to the percentage of that pixel's tile the ideal line actually covers (e.g. 95%, 75%, 25% coverage in the classic example figure).

Practical / Implementation Considerations

Zone symmetry: only Zones 0–3 need explicit transformation formulas to be derived by hand; Zones 4–7 are mirror images (negate both x and y of the corresponding 0–3 transform), so they are often left as an exercise once the pattern is understood.
Cohen‑Sutherland order matters: which boundary is tested first when an outcode has multiple non‑zero bits can change how many iterations the while‑loop takes to converge — different implementations pick a fixed bit‑test order (e.g. top, bottom, right, left).
Degenerate lines: in Cyrus‑Beck, if P₀ = P₁ the "line" is really a single point and must be handled as a point‑clipping test instead of dividing by a zero‑length direction vector.
Parallel edges: in Cyrus‑Beck, boundaries where Nᵢ·D = 0 are parallel to the line and contribute no intersection — they must be skipped rather than producing a divide‑by‑zero.
Numerical example habit: for both algorithms, always verify trivial accept/reject first — it is far cheaper than computing any intersection, and in the common case (very large or very small clip windows) it resolves most lines instantly.

Zone	Condition	Zone	Condition
0	dx>0, dy≥0, \|dx\|>\|dy\|	4	dx<0, dy≤0, \|dx\|>\|dy\|
1	dx>0, dy>0, \|dy\|>\|dx\|	5	dx<0, dy<0, \|dy\|>\|dx\|
2	dx<0, dy>0, \|dy\|>\|dx\|	6	dx>0, dy<0, \|dy\|>\|dx\|
3	dx<0, dy>0, \|dx\|>\|dy\|	7	dx>0, dy<0, \|dx\|>\|dy\|