3D Coding TAT - Line Clipping & Polygon Edge Clipping
Every book that I have ever seen that deals with the subject of line clipping and polygon scan-converting describes the same old, identical copy of the "Cohen-Sutherland" method.
I will try and describe this method, but I have written this off the top of my head without access to the algorithm so it might have some mistakes. There is another algorithm called "Sutherland & Hodgman" but I think that's 3d clipping using 6 planes rather than 2d (screen) clipping.
The basic idea behind the "Cohen-Sutherland" clipper is to assign a 4 bit "outcode" for each 2d vertex (or 6 bit outcode for 3d vertices) and then to accept, reject or clip every line between two of these vertices. These bits in the outcode describes which one of the 9 zones a vertex is in. The area around the "view-port" (clipping window/screen) is divided into 9 zones using the minimum & maximum clipping limits to define their coordinates.
Take a single vertex at position (x,y), then create a 4-bit outcode using these xmin, ymin, ymax and ymax values.
e.g.
outcode = 0
if y < ymin then outcode + 0001 binary
if y > ymax then outcode + 0010 binary
if x < xmin then outcode + 0100 binary
if x > xmax then outcode + 1000 binary
-Å------------> X x min x max
³
³ | |
³ | above |
³ | |
³ 0101 | 0001 | 1001
v | |
Y | |
y min ------------------------Ú-------------¿---------------------
³ ³
³ ³
0100 ³ 0000 ³ 1000
³ view port ³
left ³ ³ right
³ ³
y max ------------------------À------------------------------------
| |
| |
0110 | 0010 | 1010
| |
| |
| below |
| |
Now if this outcode is 0000 binary then the vertex is entirely within the view-port so it can be drawn. Otherwise it lies outside the clipping view-port region.
Okay, now let's look at a line which requires 2 vertices (one for each end). We create a 4-bit outcode for each end of the line then we can either ACCEPT, REJECT or CLIP the line.
e.g.
outcode1 = 1st vertex(x1,y1) zone code
outcode2 = 2nd vertex(x2,y2) zone code
THE GOOD: if outcode1 AND outCODE <> 0000 binary then REJECT
(Both end points are outside the view-port, and
share 1 or 2 outcode bits. This means the line
is entirely above, below, left or right of the
view-port and does NOT cross into the
view-port. The entire line can be rejected &
not drawn.)
THE BAD: if outcode1 OR outcode2 = 0000 binary then ACCEPT
(Both end points are within the view-port, so
the entire line can be drawn without clipping.)
THE UGLY: otherwise CLIP
(This is the worst case as clipping MUST be
performed on the line as it may OR may not
cross the view-port. Even after this clipping
it is possible that the line is completely
outside the view-port. In the worst case a
maximum of 4 clips needs to be done, one for
x1, one for y1, one for x2 and one for y2. ALL
the algorithms that I have read about create a
new outcode for every x or y coordinate clipped
so in the worst case we are clipping 4 times
and creating outcodes 5 times!)
I will not describe the "Cohen-Sutherland" clipper because as I have already said I haven't got any reference to it and also because I want to describe my method which I think is more efficent then re-creating outcodes after each boundary clip. The Cohen-Sutherland clipper must examine end of the two end vertices to discover which zone a line starts in and which zone the line ends in. So in effect they are doing this:
1. determine the zone where each vertex is
2. create an outcode for each vertex
3. determine if it needs clipping
4. now determine the zone from the outcodes
5. find the intersection of the X or Y axis
6. create a new outcode for the clipped axis
7. if we can't ACCEPT or REJECT the line then goto 4
As you can see we it seems to ping-pong back and forwards between zones and outcodes. I think that the original algorithm was recursive (maybe), which makes it worse!
My clipper
1: Border clipping
Sadly, no-one else to my knowledge has ever presented a different method to the Cohen-Sutherland algorithm, I hope to address this with the following code. I can see some advantages in the Cohen-Sutherland method, namely the ACCEPT or REJECT cases for entire polygons, but for me the CLIP part has been neglected in every book I've seen.
In my line-drawing routine I support clipping WITHOUT the need to create outcodes for each end-point. I also use the line's slope to both speed up clipping and drawing and in many respects this removes the need for outcodes. My belief is that once some calculation or classification has been performed then why do it again? Just the previous knowledge and some tricks should be enough. Some programmers hate the very idea of using special-case routines and prefer to use a much slower, more general routine, but for things like graphics and especially video-games I think they are wrong.
Don't follow the generals, be special !!
First of all let's define a line using two vertices (x1,y1) and (x2,y2), then if we use vertex 1 (x1,y1) as our starting point and take vertex 2 (x2,y2) as our ending point, then the line can point in any one of the 360+ degree directions.
The end vertex (x2,y2) can be in any one of the below regions (it can also be exactly ON the X or Y axis, in these cases a custom vertical or horizontal routine is normally used). Knowing what region a line points in can greatly speed up the line drawing and clipping.
Remember (x1,y1) is the centre origin (our start point).
Å-------> X AXIS 0, -Y
³ ^
³ ³
³ ³
v ³
³
Y AXIS -X, -Y ³ +X, -Y
³
-X,0 <--------Å-------> +X, 0
³
³
-X, +Y ³ +X, +Y
³
³
³
v
0, +Y
We can sift out the horizontal and vertical cases by comparing the x and y coordinates. In these cases clipping and drawing can be done without any slopes calculation.
e.g.
if x1 = x2 then goto Line_is_Vertical
if y2 = y2 then goto Line_is_Horizontal
We can force an upwards pointing line into downwards pointing one simply by swapping the start (x1,y1) and the end (x2,y2) points over. This way we always start at the top-most point and only need to draw in one direction (downwards). You could use the X-axis in the same way and force lines to only go from left-to-right or right-to-left. But I'll stick to a top-2-bottom direction.
e.g.
if y2 < y1 then swap x1,x2
swap y1,y2
This means we are starting at the topmost vertex, this removes the whole 180 degree of upwards pointing cases. The end vertex (x2,y2) is in one of the below regions. (Remember we have already sifted out the horizontal & vertical cases so the line can NOT lie ON the X or Y axis lines.)
<--------Å-------> X AXIS
³
³
-X, +Y ³ +X, +Y
³
right-to-left ³ left-to-right
³
v
Y AXIS
At this stage we can reject some totally clipped cases. Because we know the top (Y1) and the bottom (Y2) coordinates.
e.g.
if y1 > ymax then goto REJECT (totally below)
if y2 < ymin then goto REJECT (totally above)
We can determine which region the end vertex (x2,y2) is in simply by comparing the X coordinates. From here we break into two seperate cases for left and right pointing slopes this does repeating the clipping code but it can be custom made and also removes some slope drawing direction tests which a general clipper would use.
e.g.
if x1 > y2 then goto Right_facing
else goto Left_facing
Below is the WORST possible case of a line, it needs to be clipped against 4 boundaries.
T = top clip make y1 = ymin &emp; x1 = X intercept
L = left clip make x1 = xmin &emp; y1 = Y intercept
B = bottom clip make y2 = ymax &emp; x2 = X intercept
R = right clip make x2 = xmax &emp; y2 = Y intercept
(x1,y1) LEFT RIGHT
*** ³ ³
*** ³ ³
TOP ------------T**-Å--------------Å-----------------------
*L* ³
³ *** ³
³ *** ³
³ *** ³
³ *** ³
³ *R*
³ ³ ***
³ ³ ***
BOTTOM ----------------Å--------------Å-------B**-------------
³ ³ ***
³ ³ ***
³ ³ (x2,y2)
Now that we have found the direction that the line ends in we can actually begin to test & clip it. Firstly we can reject two totally clipped cases.
e.g.
Right_facing:
if x1 > xmax then goto REJECT (totally right)
if x2 < xmin then goto REJECT (totally left)
The above 2 checks reject lines which are totally left or totally right of the clipping region. At this point we can work out the X and Y lengths of the line, these will be used for the clipping operations later on.
XL = 1 + x2 - x1
YL = 1 + y2 - y1
Now we can check and clip each vertex and each axis in turn. After each axis clip a simple test is performed to determine if the intercept value makes the entire line miss the clipping region completely. This happens when two vertices aren't in neighbouring, orthogonal zones (e.g. 1000 & 0001, 0100 and 0010), where the REJECT fails. It is possible for different lines in these zones to be completely clipped or partially clipped. In these cases the X or Y axis intercept can be used to determine if the line cuts through the viewing window or is outside.
e.g.
xmin xmax
³ ³
³ 0001 aa ³ 1001
³ aa ³
³ aa³
³ bb aa ³
³ bb ³ aa v
----Å--------------bb--Å---aa----------- ymin
³ ^ bb³ aa
³ 0000 ³ bb aa
³ ³ bb aa
³ viewing ³ bb
³ window ³ 1000
³ ³
----Å--------------bb--Å---aa----------- ymin
³ ³
xmin xmax
In the above diagram the two lines a and b both have the same slope and are both in the same clipping zones (0001 and 1000) but one cuts through the viewing-window and one does not. If we were clipping the top most Y coordinate to the ymin boundary then you should be able to see the the 3rd 'bb' line section is inside <= xmax where the 6th 'aa' section is outside > xmax.
The following code will check and clip a line against the clipping rectangle.
topclip = ymin - y1
if topclip > 0 then y1 = ymin
x1 = x1 + (topclip * XL / YL)
if x1 > xmax then goto REJECT
botclip = y2 - ymax
if botclip > 0 then y2 = ymax
x2 = x2 - (botclip * XL / YL)
if x2 < xmin then goto REJECT
leftclip = xmin - x1
if leftclip > 0 then x1 = xmin
y1 = y1 + (leftclip * YL / XL)
if y1 > ymax then goto REJECT
rightclip = x2 - xmax
if rightclip > 0 then x2 = xmax
y2 = y2 - (rightclip * YL / XL)
if y2 < ymin then goto REJECT
.... the line has been successfully clipped ...
.... and so now you can draw the line !!!! ....
We already know that the line begins on the left and ends on the right and also (y1) is the topmost point and (y2) is the bottom most point.
And this is the other region clipping algorithm, this time it deals with left facing lines. This means some of the clipping lengths and coordinates are reversed but the idea is the same. We know that the line faces downwards and ends to the left of the starting point.
e.g.
Left_facing:
if x1 < xmin then goto REJECT
if x2 > xmax then goto REJECT
XL = 1 + x1 - x2 <--- NOTE: reversed x2,x1
topclip = ymin - y1
if topclip > 0 then y1 = ymin
x1 = x1 - (topclip * XL / YL)
if x1 < xmin then goto REJECT
botclip = y2 - ymax
if botclip > 0 then y2 = ymax
x2 = x2 + (botclip * XL / YL)
if x2 > xmax then goto REJECT
rightclip = x1 - xmax
if rightclip > 0 then x1 = xmax
y1 = y1 + (rightclip * YL / XL)
if y1 > ymax then goto REJECT
leftclip = ymin - x2
if leftclip > 0 then x2 = xmin
y2 = y2 - (leftclip * YL / XL)
if y2 < ymin then goto REJECT
... draw the line ! ....
And that's my clipping method, no need to generate the outcodes or regenerate them with each clip, just use the region and the line's slope. This type of clipper is reasonably good for polygons and if they are drawn in a top-to-bottom manner than you can avoid having to perform the bottom edge clipping and instead clip the polygon height (the number of scan lines).
2: Creating the outcode bits
If you do use the outcode method then the following tip might be handy. Instead of using the standard compare, jump and OR instructions:
e.g.
AX = X coordinate
BX = Y coordinate
1 MOV DL, 0 <-- outcode = 0
1 CMP AX, xmax
1 JLE @@1
1 OR DL, 1000b ; outside right
@@1
1 CMP AX, xmin
1 JGE @@2
1 OR DL, 0100b ; outside left
@@2:
1 CMP AX, ymax
1 JLE @@3
1 OR DL, 0010b ; outside bottom
@@3:
1 CMP AX, ymin
1 JGE @@4
1 OR DL, 0001b ; outside top
@@4:
====
9 .. 13 CLKs (Pentium)
13 .. 17 CLKs (486)
Use the CF (carry flag), RCL and the SETC instructions:
e.g.
1 CMP AX, xmax 1
1 SETC DL 4/3
1 CMP AX, ymin 1
1 RCL DL, 1 3
1 CMP BX, ymax 1
1 RCL DL, 1 3
1 CMP BX, ymin 1
1 RCL DL, 1 3
1 XOR DL, 1010b ; invert bottom + right bits
====
10 CLKs (Pentium)
17 .. 18 CLKs (486) ** worse **
This removes all those nasty conditional jump instructions which can seriously damage your speed.
There is also a way to remove the final XOR instruction, but I'll leave that to the reader (heh heh, king neg).
3: Clipping Similar Triangles
In the previous example of clipping I have used the old properites of similar-triangles to find the intersection point of a triangle along a straight line but I failed to describe how it works so I better do this now.
xmin (x2,y2)
Ã- xclip -´³ oX Â
³ oo . ³
e.g. (xi,yi) ³oo . ³
oX . ³
oo ³ . y length
oo ³ . ³
oo ³ . ³
oo ³ . ³
Xo................ Á
³
(x1,y1)
Ã--- x length ---´
In the above diagram we have a line (x1,y1) to (x2,y2) and the X-axis boundary (xmin) to which the line needs to have it's left side clipped to. We need to find the coordinates (xi,yi) which is the point at which the line intercepts the vertical xmin boundary.
The xi coordinate is simply the xmin value and the yi can be found using the following formula:
(y2 - y1) * xclip
yi = ------------------------ + y1
(x2 - x1)
where:
xclip = xmin - x1
This just demonstrates clipping against the left boundary edge of the clipping region but the same technique can be applied to each of the other 3 sides (right, top and bottom edges).
4: Slope Based Edge Intersection
The normal approach to clipping is to test and clip one boundary edge at a time so the entire clipping process is performed in 4 individual steps. The order I usually do these steps is top, bottom, left then right. Even a number of the very well known algorithms work in this 4 stage way. But there is a problem for 50% of line cases, it is to do with the order of these clipping steps.
Consider just 2 of the normal 4 clipping boundary edges (top and right) and the order of clipping is top then right.
³ A
³ oo
above ³ oo
³ oo
------------------Å----oo--------
³ oo
³oo
inside oo right
oo ³
oo ³
D
In the above diagram the line A..D needs to be clipped inside the top and right boundary edges. But in the top first then right clipping order the line would first be clipped against the top (ymin) limit at point B like this:
stage 1) xmax
³ A
³ ..
above ³ ..
³ ..
------------------Å----oo-------- ymin
³ oo B
³oo
inside oo right
oo ³
oo ³
D
And then against the right boundary limit at point C.
stage 2) xmax
³ A
³ ..
above ³ ..
³ ..
------------------Å----..-------- ymin
³ .. B
³..
inside oo right
oo ³ C
oo ³
D
Now we have the line section C..D after two operations. Okay, that was the worst case. Let's have a look at another line with an identical slope but a different origin.
xmax
³ A
³ oo
above oo
oo³
--------------oo--Å--------------
oo ³
inside oo ³
oo ³ right
oo ³
oo ³
D
The same top then right clipping order is performed on this new line, which gives:
stage 1) xmax
³ A
³ ..
above ..
B ..³
--------------oo--Å--------------
oo ³
inside oo ³
oo ³ right
oo ³
oo ³
D
Please notice that the first example needed TWO operations whereas this example only requires ONE.
SO WHAT ?
Well, if you perform the right edge clipping operation before the top edge then the situation is reversed. The first example now needs only ONE operation and the second example needs TWO. The inefficency comes about from not selecting the correct boundary edge to clip against. So if we can identify the correct edge to use we can avoid performing any unneccasary clipping operations. This is quite easy once you realise that the point at which two region edges meet is the decision point for the top or right edge. Simply examine the line's slope from A..D against the slope of an imaginary line from K..A.
NOTE: The point K has coordinates (xmax,ymax) where the top and right boundary lines meet.
xmax
³ A
³ ... oo
above ³ ... oo
³... oo
------------------K---oo-------- ymax
³ oo
³oo
inside oo right
oo ³
oo ³
D
It could look something like this:
(Ay-Ky) (Ay-Dy)
IF ---------- > --------- THEN clip against right
(Ax-Kx) (Ax-Dy)
(Ay-Ky) (Ay-Dy)
IF ---------- = --------- THEN clip 45' degree line
(Ax-Kx) (Ax-Dy)
(Ay-Ky) (Ay-Dy)
IF ---------- < --------- THEN clip against top
(Ax-Kx) (Ax-Dy)
Of course the test only really needs to be done once and the result used to select the appropriate action.
BUT .....
The major draw back on this method is that it requires 2 divisions to perform the test whereas the 2-stage method would only use an extra 1 multiply + 1 division in the worst case (incorrect edge order) or NONE in the best case.
At the moment it seems of little interest except for experimentation purposes but I'm sure it will find a useful application somewhere....
5: Divide And Conquer (the Clk's)
There is an obvious speed-up to the clipping and general polygon drawing technique especially if you use an incremental approach (to step the X-axis for each line) rather than use a Bresenham method. First of all you calculate the slope of the line (the increment) BEFORE you do any clipping. Now when you want to clip you can simply use a multiply instruction for two of the clipping boundaries this saves a costly division.
XMIN XMAX
³ ABOVE ³
³ ³
y axis ---------Å-------------------------------Å----------- YMAX
^ ³ ³
³ ³ ³
³ LEFT ³ CLIPPING REGION ³ RIGHT
³ ³ ³
³ ³ ³
³ ---------Å-------------------------------Å----------- YMIN
³ ³ ³
³ ³ BELOW ³
³
-Å------------------> x axis
NOTE: The following pseudo-code assumes x2 > x1 and y2 > y1.
e.g.
xl = (x2-x1)
yl = (y2-y1)
xstep = xl / yl <---- slope reciprocal
topclip = y2 - ymax
if topclip > 0 then x2=x2 - (topclip*xstep)
y2=ymax
botclip = ymin - y1
if botclip > 0 then x1=x1 + (botclip*xstep)
y1=ymin
You can also take the proper slope (yl/xl) and perform the left and right boundary clips using that.
NOTE: The following pseudo-code assumes x2 > x1 and y2 > y1. e.g.
xl = (x2-x1)
yl = (y2-y1)
ystep = (yl/xl) <---- slope
leftclip = xmin - x1
if leftclip > 0 then x1=xmin
y1=y1 + (leftclip*ystep)
rightclip = x2 - xmax
if rightclip > 0 then x2=xmax
y2=y2 - (rightclip*ystep)
In the worst clipping case this method would take 2 divides and 4 multiplies where the normal similar triangles method would take 4 divides and 4 multiplies. And remember this method automattically calculates the axis step (the X or Y increment) so scan converting the line, especially for polygons can be done much faster than a Bresenham based one which requires a conditional jump instruction within the main loop.
6: Bresenham vs. Incremental
When 'scan-converting' a line or polygon edge (finding the X axis coordinate for each scan line) you need to interpolate between the two end vertices along a straight line to discover what pixels you should draw. Many, many moons ago a clever little chappie called Jack Bresenham described one of the most useful algorithms of all time (back in 1965-ish I think). It has been so widely used and studied that most programmers can code it in their sleep. What makes it a very attractive little algorithm is that fact that it can trace out a straight line WITHOUT the need for a single division or multiplication. Instead a quick test is performed and the nearest axis to the correct line is stepped along a pixel at a time. The test is based on the old repeated subtraction method to perform division just the opposite of repeating addition to perform multiplication. There is a hidden trick up its sleeve, it actually does TWO divisions. One for the integer part and one for the fraction part. I will not go into detail as this doc is already far too big, but see for yourself how the minor step occurs one iteration earlier due to the fact of ADDING to the quotient counter rather than reloading it (see line marked by ***). This earlier step is actually the fractional carry.
e.g.
MAJOR = 100
MINOR = 10
X = 10
Y = 10
D = MAJOR - minor
again:
PLOT (X,Y)
D = D - minor
*** IF D <= 0 THEN D=D+MAJOR : Y=Y+1
X=X+1
IF X < 200 THEN GOTO again
The problem with the Bresenham style of scan converting is it isn't very good for polygons where slopes are smaller than 45 degrees. For very steep (larger than 45 degree slope) it is good because there is only one loop iteration per scan line. But for the other slopes many iterations are needed before the algorithm advances onto the next scan line. We could be tracing many pixels along a horizontal scan line before we reached the point where the Y axis changed.
I believe most people use the incremental method for polygon drawing as it requires a constant amount of CPU time within the scan-converting loop, usually just 1 ADD instruction, whereas the Bresenham way would require about 3 or 5 instructions per loop. The Bresenham doesn't need a division but the incremental method does to calculate the axis stepping value. There is a way to perform Bresenham using NO conditional jumps but that requires memory accessing (using either the CARRY FLAG or the SIGN of the decision variable to act as an index). Also you can perform Bressy in 2 or 3 instructions if you stick to a 64kb screen mode (like mode 13h) and use 32-bit registers (bits 31..16 as the decision and bits 15..0 as the screen offset). Together with a 16-bit addressing mode, this can be done something like this:
a 4 instruction Bresenham:
MOV [DI],AL <--- plot pixel
ADD EDI,ESI <--- d+minor, DI+minorstep
JG SHORT notyet
ADD EDI,EBX <--- d+major, DI+majorstep
notyet:
I haven't described what the variables are and how it works because I'm far too lazy.
It is possible to write a Bressy in just 3 instructions (well 2 plus 1 to plot the pixel) that doesn't perform the conditional jump instruction, but you don't wanna know, do ya? Well, I not gonna tell you. But here are some hints. The Bressy has only TWO states (either a major axis step OR a minor axis step). The decision SIGN bit can be used to indicate which state (and so which axis) should be taken. Okay, enough hints. Here is the darn thing:
MOV [ES:DI],AL ; plot the pixel
SBB BH,BH ; n = index = CF
SUB EDI,[BX] ; d+axis[n], DI+step[n]
NOTE: This could only work for a 64kb linear VGA screen mode and will probably won't handle the 64kb wrap correctly (which happens if the screen is scrolled).
I'll leave you to figure it out, you need 4 bytes at address [DS:00xx] and 4 bytes at [DS:FFxx] which are the update variables for the top 16-bits of EDI and the low 16-bits (DI) is the screen pixel address.
In light of the recent discussion about clipping (using the slope to clip) I would imagine that the incremental method is still the king especially on a dual-pipe Pentium super CPU where other instructions can be performed while waiting for the division to finish. And with floating-point instructions being faster than most integer ones the days of the Bresenham looks sadly numbered. But King Bressy has another trick up its old sleeve. It doesn't NOT suffer from the accumulation errors which the incremental method does. So, there's still life in this old dog yet eh?
7: Binary Sub-Division Clipper
Unfortunately I cannot remember whose algorithm this is but I remember reading about somewhere (perhaps I need to actually buy a damn graphics book!). It is a way to avoid having to perform multiplications and divisions to find the intersection point(s) of a line using nothing more than shift, add and subtract instructions. It might be part of the Sutherland-Cohen or Hodgman outcode algorithm.
Say we have a line with a single end vertex outside the clipping region. We need to find the point on the line at which it meets the boundary limits.
(x1,y1) ³
o- ³
--³
--
³ --
outside ³ -- inside
³ --
³ --
³ --
³ -o (x2,y2)
Given the two end vertices (x1,y1) and (x2,y2) we can quickly find the middle point of the line by doing this:
(x1+x2) (y1+y2)
xc = --------- yc = ---------
2 2
Now we have the coordinates (xc,yc) which are middle point which breaks the line into two seperate sections (x1,y1) to (xc,yc) and (xc,yc) to (x2,y2).
(x1,y1) ³
o- ³
--³
--
³ --
outside ³ *- inside
(xc,yc) --
³ --
³ --
³ -o (x2,y2)
In effect we have subdivided the line into 2 halves.
In the above diagram we have found a point inside the clipping region so we know that the point of intersection is in the first half of the line from (x1,y1) to (xc,yc) so we can take this as our line and subdivide this too until we finish up ON the boundary line. At this point we have found the intersection coordinate of the other axis.
8: Combined Incremental Clipper
After a little bit of thought and taking a broader outlook on the problem of line clipping and drawing, it is possible to combine the two tasks and reduce the number of divisions and multiplications. Using the incremental method of drawing a line together with the slope based edge selection method it is possible to perform the clipping tests and all the intersection calculations using 4 divides and 2 multiplies and this includes calculating the increment value to draw the actual line.
This 4 divide, 2 multiply example is the WORST case where BOTH end points need to be clipped to the window region. For the normal edge-by-edge approach (top, bottom, left, right) it would take 5 divides and 4 multiplies (remember this includes a divide to find the slope increment value) in the worst case or 3 divides and 2 multiplies in the best case.
The advantage of this method is that the correct region's clipping edge is selected from the start, unlike the 4-stage method which can find the intersection point which is still beyond the clipping window region (see below T and B).
Å---->X (x1,y1) xmin xmax
³ *** ³ ³
³ *** ³ above ³
v ymin ------------T**-Å--------------Å-----------------------
Y *L* ³
³ *** ³
³ *** ³
left ³ *** ³ right
³ *** ³
³ *R*
³ ³ ***
³ ³ ***
ymax ----------------Å--------------Å-------B**-------------
³ below ³ ***
³ ³ ***
³ ³ (x2,y2)
e.g.
xslope = (y2 - y1) / (x2 - x1)
yslope = (x2 - x1) / (y2 - y1) ;; our incremental step for drawing
;** Compare the top-left slope against the line slope, the difference **
;** selects the correct clipping edge (either top or left) **
IF (xmin - x1) > 0 THEN tslope = (ymin - y1) / (xmin - x1)
ELSE tslope = 0
IF xslope >= tslope THEN y1 = y1 + (xmin - x1) * xslope ;; left
x1 = xmin ;; edge
ELSE x1 = x1 + (ymin - y1) * yslope ;; top
y1 = ymin ;; edge
;** A similar thing is done for the bottom-right slope. The difference **
;** selects the correct clipping edge (either bottom or right) **
IF (x2 - xmax) > 0 THEN bslope = (y2 - ymax) / (x2 - xmax)
ELSE bslope = 0
IF xslope >= bslope THEN y2 = y2 - (x2 - xmax) * xslope ;; right
x2 = xmax ;; edge
ELSE x2 = x2 - (y2 - ymax) * yslope ;; bottom
y2 = ymax ;; edge
NOTE: The above code is not a general case algorithm and may contain bugs so please use it as reference only to develop your own clipper. The above pseudo-code is possibly only worth doing for diagonal clipping where a line goes from above-left to below-right OR from above-right to below-left outside the clipping region. Of course this code can be further optimized to only do some calculations (like the 'xslope' value) if it actually needs to be used.
THE BAD NEWS
This method works out slower than the previous DAC method (Divide And Conquer) with two more divide instructions. It may still be useful for locating the correct edge of the clipping region perhaps for polygon clipping.
9: Custom Outcode Clipping
The problem with writing any general code is that it usually operates at a far slower pace than some custom, special case code. As line and polygon clipping is already slow enough any short cut to boost performance is welcome. If you stick to the standard outcode method of labelling vertices then you can handle difficult (worst case) problems in a custom routine which will hopefully run faster. The ACCEPT and REJECT cases using the outcode algorithm is fine, but the CLIP stage can be improved. I have already described some ideas on how to minimize multiplications and divisions. The outcodes can be used to select the correct clipper sub-case. One obvious solution would be to create an 8-bit code from two 4-bit codes, this could then be used to index into a jump table to reach the correct routine. You could even use this to remove the ACCEPT (logical OR) and the REJECT (logical AND) stages. Both of these could be built into the jump table.
This 8-bit jump table could look like this:
index outcode1 outcode 2 Action
------- ------------------ ----------
00 hex 0000 0000 accept entire line
01 0000 0001 clip vertex 2 against top
02 0000 0010 clip vertex 2 against bottom
03 0000 0011 -- invalid outcode --
04 0000 0100 clip vertex 2 against left
.. .... ....
11 0001 0001 reject entire line (above window)
12 0001 0010 clip vertex 1 top, vertex 2 bottom
13 0001 0011 -- invalid outcode --
.. .... ....
FF hex 1111 1111 -- invalid outcode --
This way it is possible to quickly choose the best custom clipping routine for a particular line without having to perform lots of tests and conditional jumps.
It may be worthwhile seeing if this method could be extended to polygon clipping.