Point Clipping

Assuming a rectangular clip window, point clipping is easy:

we save the point if

xwmin <= x <=xwmax

ywmin <= y <= ywmax

Line Clipping

Trivial Accept - save a line with both endpoints inside all clipping boundaries.

Trivial Reject - discard a line with both endpoints outside the clipping boundaries.

For all other lines - compute intersections of line with clipping boundaries.

Parametric representation of a line:

x = x1 + u (x2 - x1)

y = y1 + u (y2 - y1), and 0 <= u <= 1.

If the value of u for an intersection with a clipping edge is outside the range 0 to 1, then the line does not enter the interior of the window at that boundary. If the value of u is within this range, then the line does enter the interior of the window at that boundary.

Cohen-Sutherland

Idea - every line endpoint is assigned a four-digit binary code:

bit 1: left

bit 2: right

bit 3: below

bit 4: above

Look at Fig. 6-8 on p. 227 in Hearn & Baker.

Trivial Accept - if a is the region code for one endpoint and b is the region code for the other endpoint then

Trivial Accept is obtained by the bitwise operation !(a|b), and

Trivial Reject is obtained by the operation (a&b), and

a point is inside if its region code is a=0000, or equivalently (!a) is true.

For intersection calculations look in text.

Liang-Barsky

Idea - make use of the parametric representation of the line to speed up the intersections computations. More specifically, can represent the four inequalities (mentioned above) in a uniform way:

u*pk <= qk, for k=1,2,3,4

and compute an intersection with a particular boundary edge by inverting the above equation:

u = qk / pk.

The details of the algorithm are described in the text. Read it through, and answer

Question 1: How is Trivial Reject carried out in Liang-Barsky.

Question 2: How is Trivial Accept obtained ?

Question 3: Why is the Liang-Barsky algorithm more efficient than the Cohen-Sutherland algorithm ?

Question 4: How would you extend both algorithms to three-dimensional line clipping ? (Hint: How many more bits would you need in Cohen-Sutherland ? How many inequalities would you have in Liang-Barsky ?)

Your Task

Create a directory lab3:

Download the following files to the lab3 directory:

Makefile
main.c
callbacks.c
clip.c
const.h
types.h
funcs.h

First, take a look at clip.c - this is an implementation of the Liang-Barsky clipping algorithm.

Then, compile the files and run the executable.

When you execute the code and enter many lines, you will find that the program seg faults. Find the bug, and fix it !

If you have enough time, try to implement the Cohen-Sutherland algorithm. For comparison, count the number of arithmetic operations, and the number of conditional evaluations in both algorithms.