Clipping an abscissa

    Clipping a point is relatively simple. However, for more complex objects we always need more operations, and therefore we try to minimize their number. This is also true in the case of an abscissa in a general shape. First of all, we test its end points, and if they belong to the display box so also the whole abscissa lies inside the display box. If the abscissa lies outside, we test the abscissa's penetration through its display box. If the abscissa crosses the display box, we clip it, and for this it is necessary to find the conjunction points (meaning where the abscissa crosses the display box's limits).

    An essential factor in clipping is the speed of the algorithm for searching for conjunction points (in displaying a scene we can have thousands of objects, which it is necessary to clip in the shortest possible time interval). Therefore there are several clipping algorithms designed. But, first of all we carry out tests of whether it is necessary to look for conjunction points. The abscissas, lying inside the display box, do not need clipping, and thus those can be directly displayed. If both the end points of an abscissa lie above the display box, meaning that their coordinate y < ymin of the display box, so we do not display them. Similarly, if they lie under the display box, right or left from the display box.

Cohen-Sutherland clipping algorithm

    The first part of this algorithm serves simply for excluding abscissas at which it isn't necessary to calculate the conjunction with the display box. Firstly, we split a plane into 9 sections, while the middle section represents a display box. For every section is allocated a 4-bit code, and such code is allocated also to the point of abscissa which belongs into this section. Individual bits for a point [x, y] are set as follows:

1.    bit - a point lying left of the display box ( xmin > x )
2.    bit - a point lying right of the display box ( xmax < x )
3.    bit - a point lying lower than the display box ( ymin > y )
4.    bit - a point lying higher than the display box ( ymax < y )

$$$APPLET

Applet Codes of areas determined by the display box

    A point located inside the display box has the code 0000. The abscissa is lying wholly inside in the display box. We can exclude this abscissa if both its points are left, right, above or down from the display box. We can easily identify this just by the codes of the end points. We take both codes of the end points of an abscissa, and we make their logical conjunction ((1 and 1) = 1, otherwise 0). If it is different from 0000, then the abscissa doesn't intersect the display box, and we can exclude it. In the opposite case, we cannot exclude this abscissa, and we must test it for a conjunction in respect of the display box limits, 4 times in a worst case. 

$$$APPLET

Applet Clipping the given abscissa in respect of the display box, and the determination of conjunction points.

Cyrus-Beck parametric line clipping algorithm

    With Cohen-Sutherland clipping algorithm it can happen that we clip even an abscissa 4 times. In 1978 Cyrus and Beck [CYRU78] reduced clipping to maximally twice; once on the abscissa's entry into the display box, and once on leaving the display box. We describe here the basic idea:  

    Let D be the direction vector of the abscissa AB; then we can write the abscissa AB in parametric form: P(t)=A+t.D, where the parameter t <0,1>.

$$$APPLET

Applet Clipping a set abscissa in respect of the display box, and determination of conjunction points.

For more informations see

Consecutive division algorithm

    With Cohen-Sutherland algorithm we use multiplication and division. The consecutive division algorithm tries to avoid these operations. Its basic principle lies in the transformation of the abscissa from user-coordinates into integral number coordinates, and then by consecutively dividing the abscissa to half [1]. The number of iterations of dividing an abscissa can be relative high, however, the calculations as such, due to absence of multiplication and division, are essentially faster. Firstly, for an abscissa with the points A[x1,y1] and B[x2,y2], we set the mid point S. Its coordinates are: (x1 + x2)/2, and (y1 + y2)/2. In this way we split the abscissa in two, and then, we test in the same way as in the case of the Cohen-Sutherland algorithm. The strategy of this method lies in dividing the abscissa into halves. At each step, usually one half of the divided abscissa is excluded (while its both end points fall in the same area), and we continue in dividing the other part.

$$$APPLET

Applet Clipping a given abscissa through division to half.

    The algorithm, in the worst case, finishes for log(n) steps, where n is the length of maximum side of the display box in pixels.

Liang-Barsky line clipping algorithm

Applet displays result of Liang-Barsky's Line Clipping Algorithm solution. There is initial line and clipping rectangle projected. The clipped part of initial line is highlighted by bolder and more contrast color. Interactivity affords to change parameters (positions of outer points and cornes) of initial line and clipping rectangle comfortably using mouse functionality:
- finding and marking closest flexible point
- drag & drop idea of relocation outer points of initial line and clipping rectangle corners

$$$APPLET

Applet Drawing point, in corner right bottom are co-ordinates current point. Authors: Branislav Malinovsky

Specificaton of algorithm

In fact, line clipping means finding two outer points of intersection between rectangle(clipping) and line(clipped). Line segment acquired by junction of these two points is then called clipped line. Liang-Barsky's Line Clipping Algorithm uses the parametric equations for a line and solves four inequalities to find the range of the parameter for which the line is in the intersection with rectangle.

In steps:

  • 1. Let P(x1,y1) and Q(x2,y2) be the outer points of initial line
  • 2. Set Tmin = 0 and Tmax = 1 (Tmin represents the starting position and Tmax represents ending position of actual phase of clipping the line relatively to initial line; at beginning positions of initial line)
  • 3. Use coordinates of clipping edges to find values of individual inequalities (generally t or individualy tL,tR,tT,tB)
    From parametric equation x = x1 + (x2-x1)*t, y = y1 + (y2-y1)*t (0<=t<=1):
    - let R (R = x1 + t*(x2 - x1)) is x coordinate of right edge - tL = (L-x1)/(x2-x1)
    - let L (L = x1 + t*(x2 - x1))is x coordinate of left edge - tR = (R-x1)/(x2-x1)
    - let T is y coordinate of top edge - tT = (T-y1)/(y2-y1)
    - let B is y coordinate of bottom edge - tB = (B-y1)/(y2-y1)
    If ttmax ignore it and go to the next edge otherwise classify the value of t as entering or exiting value (using inner product to classify). If t is entering value set tmin = t. If t is exiting value set tmax =t.
  • 4. If tmin < tmax then draw a line from (x1 + dx*tmin, y1 + dy*tmin) to (x1 + dx*tmax, y1 + dy*tmax).
  • 5. If the line crosses over the rectangle, you will see
    (x1 + dx*tmin, y1 + dy*tmin) and (x1 + dx*tmax, y1 + dy*tmax)
    are intersection between line and edge.