3.1. Drawline

Version II.0, February 1979

The DRAWLINE intrinsic uses an incremental technique to plot line segments on a point-addressable matrix. The algorithm guarantees a best (least squares) approximation to the desired line. In general this approximation is not unique. DRAWLINE may pick different representations for a line depending on the starting point. (This could be corrected by always starting at the same end of the line.) No range checking is performed on parameters passed to this intrinsic.

The algorithm is essentially the one described in Newman and Sproul, Principles of Interactive Computer Graphics as the Digital Differential Analyzer. It has been modified to perform only integer arithmetic. Pascal source code is included below. The procedure first determined whether the line will be more horizontal or vertical. In the discussion below, we assume the horizontal case; vertical is similar.

There will be DELTAX points plotted with horizontal increment of 1 each. The vertical increment will be ABS(DELTAY / DELTAX) <= 1. The Y coordinate arithmetic is scaled by DELTAX to eliminate fractions. An additional savings in execution time has been gained by maintaining the address of the previous point, and doing only addition and subtraction to reach the next point to be plotted.

The RADAR function is complicated as two intersecting lines may have no plotted points in common. The detection condition is either (1) the computed point is TRUE, or (2) both the next horizontal and the next vertical points are TRUE. Condition (2) could be weakened: when the line is more horizontal, only the next vertical point need be checked.

Refer to Section 2.1.4 for a description of the parameter calling sequence.

A PASCAL implementation follows:

PROCEDURE DRAWLINE(VAR RANGE: INTEGER; VAR SCREEN: SCREENTYPE;
    ROWWIDTH, XSTART, YSTART, DELTAX, DELTAY, INK: INTEGER);

VAR X, Y, XINC, YINC, COUNT: INTEGER;

PROCEDURE DRAWDOT;

  PROCEDURE RADAR;
  VAR GOTIT: BOOLEAN;
  BEGIN
    GOTIT := FALSE;
    COUNT := COUNT + 1;
    IF SCREEN[Y, X] THEN GOTIT := TRUE (* landed on the point *)
    ELSE (* we might go through a line *)
      IF SCREEN[Y, X] THEN
        GOTIT := SCREEN[Y, X + 1];
    IF GOTIT THEN
    BEGIN
      RANGE := COUNT;
      EXIT(DRAWLINE)
    END;
  END (* radar *);

BEGIN (* drawdot *)
  CASE INK OF
    0 (* none *): EXIT (DRAWLINE);
    1 (* white *): SCREEN[Y, X] := TRUE;
    2 (* black *): SCREEN[Y, X] := FALSE;
    3 (* reverse *): SCREEN[Y, X] := NOT SCREEN[Y, X];
    4 (* radar *): RADAR
  END (* case *)
END (* drawdot *);

PROCEDURE DOFORX; (* more horizontal *)
VAR ERROR, I: INTEGER;
BEGIN
  IF DELTAX = 0 THEN EXIT(DRAWLINE); (* they're going nowhere *)
  ERROR := DELTAX DIV 2;
  I := DELTAX;
  REPEAT
    ERROR := ERROR + DELTAY;
    IF ERROR >= DELTAX
    THEN BEGIN ERROR := ERROR - DELTAX; Y := Y + YINC END;
    X := X + XINC;
    DRAWDOT;
    I := I - 1;
  UNTIL I = 0;
END (* doforx *);

PROCEDURE DOFORY; (* more vertical *)
VAR ERROR, I: INTEGER;
BEGIN
  ERROR := DELTAY DIV 2;
  I := DELTAY;
  REPEAT
    ERROR := ERROR + DELTAX;
    IF ERROR >= DELTAY;
      THEN BEGIN ERROR := ERROR = DELTAY; X := X + XINC END;
    Y := Y + YINC;

    DRAWDOT;
    I := I - 1;
  UNTIL I = 0;
END (* dofory *);

BEGIN (* drawline *)
  X := XSTART;
  IF DELTAX < 0
    THEN BEGIN XINC := -1; DELTAX := -DELTAX END
    ELSE XINC := 1;
  Y := YSTART;
  IF DELTAY < 0
    THEN BEGIN YINC := -1; DELTAY := -DELTAY END
    ELSE YINC := 1;
  COUNT := 0;
  IF DELTAX >= DELTAY THEN DOFORX ELSE DOFORY;
  IF INK = 4 (* radar *) THEN RANGE := COUNT; (* hit the limit given *)
END (* drawline *);