Clipping

References:

  1. Andy Johnson's CS 488 Course Notes, Lecture 3 and 4
  2. Foley, Van Dam, Feiner, and Hughes, "Computer Graphics - Principles and Practice", Section 3.11 to 3.14

Clipping

Since we have a separation between the models and the image created from those models, there can be parts of the model that do not appear in the current view when they are rendered.
pixels outside the clip rectangle are clipped, and are not displayed.

can clip analytically - knowing where the clip rectangle is clipping can be done before scan-line converting a graphics primitive (point, line, polygon) by altering the graphics primitive so the new version lies entirely within the clip rectangle

can clip by brute force (scissoring) - scan convert the entire primitive but only display those pixels within the clip rectangle by checking each pixel to see if it is visible.

as with scan conversion, this must be done as quickly as possible as it is a very common operation.


Point Clipping

point (X,Y)
clipping rectangle with corners (Xmin,Ymin) (Xmax,Ymax)

point is within the clip rectangle if:


Cohen-Sutherland Line Clipping ( Foley 3.12.3 )

given a line segment, repeatedly:

  1. check for trivial acceptance
  2. check for trivial rejection
  3. divide segment in two where one part can be trivially rejected

Clip rectangle extended into a plane divided into 9 regions
each region is defined by a unique 4-bit string

(the sign bit being the most significant bit in the binary representation of the value. This bit is '1' if the number is negative, and '0' if the number is positive.)

The frame buffer itself, in the center, has code 0000.

1001 | 1000 | 1010
-----+------+-----
0001 | 0000 | 0010
-----+------+-----
0101 | 0100 | 0110

For each line segment:

  1. each end point is given the 4-bit code of its region
  2. repeat until acceptance or rejection
    1. if both codes are 0000 -> trivial acceptance
    2. if bitwise logical AND of codes is not 0000 -> trivial rejection
    3. divide line into 2 segments using edge of clip rectangle
      1. find an endpoint with code not equal to 0000
      2. move left to right across the code to find a 1 bit -> the crossed edge
      3. break the line segment into 2 line segments at the crossed edge
      4. forget about the new line segment lying completely outside the clip rectangle

The full algorithm ( was? ) given (in C) in the red book ( ??? Edition ) as program 3.7 on p.105.
The full algorithm is given (in C) in the white book as figure 3.41 on p.116.

Sutherland-Hodgman Polygon Clipping ( Foley 3.14.1 )

Unlike line-clipping where we selectively clipped against each edge, here we sucessively clip a polygon against all four edges of the clip rectangle

given a polygon with vertices V1, V2, ... Vn
and edges between vertices Vi and Vi+1, and from Vn to V1

for each of the four clipping edges

This algorithm can break a single polygon into multiple polygons connected by edges on the boundary of the clipping rectangle for display.

The full algorithm ( was? ) given (in C) in the red book ( ??? Ediiton ) as program 3.9 on p.114.
The full algorithm is given (in Pascal) in the white book as program 3.49 on p.128.


Example of Polygon Clipping


Clipping on Ymax edge:

the new vertex sequence is then checked against the Ymin edge and so on through the Xmax edge and the Xmin edge


2 More Examples