Unit 3: Clipping and filling
Computer Graphics notes · PTU syllabus (PGCA1919)
On this page
Unit summary
Clipping removes what lies outside the view, and filling colours what lies inside a shape. This unit covers point clipping, Cohen–Sutherland and Liang–Barsky line clipping, polygon and text clipping, and boundary fill and flood fill algorithms.
After this unit you can
- Clip points and lines
- Clip polygons and text
- Fill regions with boundary and flood fill
- Compare clipping and filling algorithms
PTU syllabus topics
- Point clipping
- line clipping (Cohen-Sutherland, Liang-Barsky)
- polygon and text clipping
- boundary fill and flood fill algorithms
Both endpoints 0000
Fully inside
Accept the line
Logical AND of codes ≠ 0000
Fully outside on one side
Reject the line
Otherwise
Partly inside
Clip at a boundary and repeat
Topic 1
Point clipping
- A point (x, y) is displayed only if xwmin ≤ x ≤ xwmax and ywmin ≤ y ≤ ywmax; otherwise it is clipped. Point clipping is used for particles, text characters and scatter plots.
Topic 2
Line clipping: Cohen–Sutherland
- Each endpoint gets a 4-bit region code — bit 1 left, bit 2 right, bit 3 below, bit 4 above the window.
- 1Assign region codes to both endpoints
- 2Both codes 0000
Line fully inside — accept
- 3Logical AND of codes non-zero
Fully outside — reject
- 4Otherwise
Find the intersection with a window edge for an outside endpoint
- 5Replace that endpoint and repeat
With a vertical edge x = xb
y = y1 + m (xb − x1)
With a horizontal edge y = yb
x = x1 + (yb − y1) ÷ m
Example
Window (0,0)–(10,10); line (−5, 5) to (5, 5): codes 0001 and 0000; intersect x = 0 → (0, 5); clipped line (0,5)–(5,5).
Topic 3
Line clipping: Liang–Barsky
- Uses the parametric line x = x1 + t·Δx, y = y1 + t·Δy, 0 ≤ t ≤ 1, and computes entry and exit values of t directly — fewer intersection calculations than Cohen–Sutherland.
p and q values
p1 = −Δx, q1 = x1 − xwmin; p2 = Δx, q2 = xwmax − x1; p3 = −Δy, q3 = y1 − ywmin; p4 = Δy, q4 = ywmax − y1
Rule
If pk = 0 and qk < 0 the line is outside; for pk < 0, t1 = max(0, qk ÷ pk); for pk > 0, t2 = min(1, qk ÷ pk)
Result
If t1 > t2 reject; else clipped endpoints at t1 and t2
Example
Window (0,0)–(10,10), line (−5, 3) to (15, 9): Δx = 20, Δy = 6. p1 = −20, q1 = −5 → t = 0.25; p2 = 20, q2 = 15 → t = 0.75; y conditions give no tighter limits. Clipped endpoints at t = 0.25 and 0.75: (0, 4.5) and (10, 7.5).
Topic 4
Polygon clipping: Sutherland–Hodgman
- 1Clip the polygon against one window edge at a time — left, right, bottom, top
- 2For each edge from vertex S to vertex P apply four cases
- 3Output of one stage is input to the next
- Both inside
- Output P
- Inside to outside
- Output the intersection I
- Outside to outside
- Output nothing
- Outside to inside
- Output I and P
- Limitation: concave polygons may produce extra connecting edges; the Weiler–Atherton algorithm handles them correctly.
Topic 5
Text clipping
All-or-none string
Keep the whole string only if completely inside
Fastest, least accurate
All-or-none character
Keep only characters completely inside
Moderate
Individual character components
Clip parts of characters like lines (stroke fonts) or pixels (bitmap fonts)
Most accurate, slowest
Topic 6
Boundary fill and flood fill
Scan-line polygon fill
For each scan line, find intersections with edges, sort them, fill between pairs
Polygons defined by vertices
Boundary fill
From a seed, colour neighbours until the boundary colour is reached
Regions with one boundary colour
Flood fill
From a seed, replace all connected pixels of the old interior colour
Regions with multi-coloured boundaries; paint bucket tool
cvoid floodFill(int x, int y, int oldColor, int newColor) {
if (getpixel(x, y) == oldColor) {
putpixel(x, y, newColor);
floodFill(x + 1, y, oldColor, newColor); /* 4-connected */
floodFill(x - 1, y, oldColor, newColor);
floodFill(x, y + 1, oldColor, newColor);
floodFill(x, y - 1, oldColor, newColor);
}
}- 4-connected fill checks four neighbours; 8-connected also checks diagonals. Recursion can overflow the stack for large areas, so scan-line seed fill with an explicit stack is used in practice.
cvoid boundaryFill(int x, int y, int fill, int boundary) {
int c = getpixel(x, y);
if (c != boundary && c != fill) {
putpixel(x, y, fill);
boundaryFill(x + 1, y, fill, boundary);
boundaryFill(x - 1, y, fill, boundary);
boundaryFill(x, y + 1, fill, boundary);
boundaryFill(x, y - 1, fill, boundary);
}
}Key terms
- Clipping window
- Rectangle defining the visible region
- Region code
- Four bits locating an endpoint relative to the window
- Parametric line
- x = x1 + tΔx, y = y1 + tΔy
- Boundary fill
- Filling until a boundary colour is met
- Flood fill
- Replacing a connected interior colour
Quick revision
- Point clipping inequalities.
- Cohen–Sutherland: codes, trivial accept and reject, intersections.
- Liang–Barsky: p and q values; t1 and t2.
- Sutherland–Hodgman four cases; Weiler–Atherton for concave polygons; text clipping strategies.
- Boundary vs flood fill; 4- and 8-connected; scan-line fill.
Important exam questions
Practice questions written to the PTU exam pattern for this unit's syllabus: short answers (Section A style) and long answers (Sections B and C style).
Short-answer questions
- Q1.State the condition for a point to be visible.
- Q2.What does a region code of 0101 mean?
- Q3.Why is Liang–Barsky more efficient than Cohen–Sutherland?
- Q4.What are the four cases of Sutherland–Hodgman clipping?
- Q5.Distinguish boundary fill and flood fill.
- Q6.What is 8-connected filling?
Long-answer questions
- Q1.Explain the Cohen–Sutherland line clipping algorithm with an example.
- Q2.Explain the Liang–Barsky algorithm with an example.
- Q3.Explain polygon and text clipping.
- Q4.Explain boundary fill and flood fill algorithms.
Stuck on this unit?
Message SBS on WhatsApp for help with Computer Graphics, or to ask about studying M.Sc IT at Synetic.