Diagram 1 |

So the beginning of the line

t0 = 0 t1 = 1

We need to find out some values before we proceed. These two (Xdelta and Ydelta) are the most frequently used throughout the whole algorithm, so get them stuck into your brain:

Xdelta = P1x-P0x = 280-30 = 250 // Horizontal diff between P0 and P1. Ydelta = P1y-P0y = 160-20 = 140 // Vertical diff between P0 and P1.

Diagram 1b |

P = -XDelta = -(280-30) = -250 Q = -(leftEdge-P0x) = -(70-30) = -40 R = Q/P = 0.16

It isn't in our case, but if P = 0 AND Q < 0, then we already quit. In this case, the line would parallel to the left edge ( P=0 : remember, P represents the Xdelta), and outside the edge (Q<0), so we don't need to worry about anything else, and no line is drawn. 'Thankfully', although Q is less than zero, P is not equal to zero, so we can continue....

If P is less than zero (which it is in our case, since -250 < 0 ), that means, the line from P0 to P1 is travelling in the opposite direction of our edge name (which in our case is 'left', so the line is going rightwards). Anyway, if this is the case (which it is for us), we do this check:

Otherwise, if R > t0 (is 0.16 > 0 ?), then set t0 to R !!! (clip the beginning of the line to something higher than zero). So for us, t0 = 0.16 ! Now go to next edge. Otherwise, skip to next edge. |

If P is more than zero however (which it isn't in this example btw - we've already had the above executed, so the below boxout is only for future edge checks!), that means the line is travelling in the SAME direction as our edge name (which in our case is 'left', so the line would be going leftwards), we would instead have done another (similar) check:

Now this time, if R < t0 (is 0.16 < 0 ?), that must mean the (other end of the) line is too short to meet the left edge, so it must be outside. Thus scrap *everything*.P = -XDelta = -(280-30) = -250 Q = -(leftEdge-P0x) = -(70-30) = -40 R = Q/P = 0.16 Otherwise if R < t1 (is 0.16 < 1 ?), then set t1 = R ! Now go to next edge. Otherwise, skip to next edge. |

Start with: t0 = 0 t1 = 1 P = -XDelta = -(280-30) = -250 Q = -(leftEdge-P0x) = -(70-30) = -40 R = Q/P = 0.16 // Results so far using algorithm above: t0 = 0.16 t1 = 1 P = XDelta = (280-30) = 250 Q = rightEdge-P0x = (230-30) = 200 R = Q/P = 0.8 // Results so far using algorithm above: t0 = 0.16 t1 = 0.8 P = -YDelta = -(160-20) = -140 Q = -(bottomEdge-P0y) = -(60-20) = -40 R = Q/P = 0.2857 // Results so far using algorithm above: t0 = 0.2857 t1 = 0.8 P = YDelta = 160-20 = 140 Q = topEdge-P0y = 150-20 = 130 R = Q/P = 0.9286 // Results so far using algorithm above: t0 = 0.2857 t1 = 0.8 |

Final values for t0 and t1 !! : t0 = 0.2857 t1 = 0.8

Diagram 3 |

newP0x = P0x + t0*Xdelta = 30 + 0.2857*250 = 101.425 newP0y = P0y + t0*Ydelta = 20 + 0.2857*140 = 60 newP1x = P0x + t1*Xdelta = 30 + 0.8*250 = 230 newP1y = P0y + t1*Ydelta = 20 + 0.8*140 = 132 drawline newP0x,newP0y to newP1x,newP1y

We can 'optimize' the above five lines of code by using this instead. It basically avoids any unnecessary calculations if the line was already completely inside the edges to start with:

If t0=0 // Stick with original values newP0x = P0x; newP0y = P0y; Else // Values need clipping newP0x = P0x + t0*Xdelta; newP0y = P0y + t0*Ydelta; End if If t1=1 { // Stick with original values newP1x = P1x; newP1y = P1y; Else // Values need clipping newP1x = x0src + t1*Xdelta; newP1y = y0src + t1*Ydelta; End If drawline P0x,P0y to P1x,P1yFinisimo!

// Liang-Barsky function by Daniel White @ http://www.skytopia.com/project/articles/compsci/clipping.html // This function inputs 8 numbers, and outputs 4 new numbers (plus a boolean value to say whether the clipped line is drawn at all). // bool LiangBarsky (double edgeLeft, double edgeRight, double edgeBottom, double edgeTop, // Define the x/y clipping values for the border. double x0src, double y0src, double x1src, double y1src, // Define the start and end points of the line. double &x0clip, double &y0clip, double &x1clip, double &y1clip) // The output values, so declare these outside. { double t0 = 0.0; double t1 = 1.0; double xdelta = x1src-x0src; double ydelta = y1src-y0src; double p,q,r; for(int edge=0; edge<4; edge++) { // Traverse through left, right, bottom, top edges. if (edge==0) { p = -xdelta; q = -(edgeLeft-x0src); } if (edge==1) { p = xdelta; q = (edgeRight-x0src); } if (edge==2) { p = -ydelta; q = -(edgeBottom-y0src);} if (edge==3) { p = ydelta; q = (edgeTop-y0src); } r = q/p; if(p==0 && q<0) return false; // Don't draw line at all. (parallel line outside) if(p<0) { if(r>t1) return false; // Don't draw line at all. else if(r>t0) t0=r; // Line is clipped! } else if(p>0) { if(r<t0) return false; // Don't draw line at all. else if(r<t1) t1=r; // Line is clipped! } } x0clip = x0src + t0*xdelta; y0clip = y0src + t0*ydelta; x1clip = x0src + t1*xdelta; y1clip = y0src + t1*ydelta; return true; // (clipped) line is drawn }

All material on this page is copyright D. White 2006 onwards (other than the code which you can freely use).