Updating Niklaus Wirth with a LineDrawing graphics module in (what else?) Modula-2.

April 01, 1988
URL:http://www.drdobbs.com/database/structured-programming/184407934

STRUCTURED PROGRAMMING

Implementing Wirth's LineDrawing Module

In his seminal work Programming A in Modula-2 , the venerable Nicklaus Wirth, lord of structured programming, proposes a graphics module that he calls LineDrawing. It's defined on pages 114-115 of my copy, which is the Springer-Verlag 1982 edition. Although LineDrawing lacks the razzle-dazzle of more recent graphics packages, it's serviceable for many applications. Yet Modula-2 vendors seem to have by-passed it even though they leap at everything else Wirth even vaguely suggests. Consequently, this month's column makes a Valuable Contribution by implementing LineDrawing and showing some ways to use it.

For this project I tried out a new Modula-2 development system from Stony Brook Software up in Wilton, New Hampshire. I used Version 1.00, a level number certain to make any serious programmers break out in a sweat as cold as the New Hampshire winter. It's a command-line compiler, which isn't much fun after getting used to Turbo Pascal 4.0's glitzy integrated environment. Also, I didn't use the included program editor, M2EDIT, because I'm spoiled by BRIEF. (If you haven't tried BRIEF, it's like coming to the One True Religion.) Still and all, Stony Brook's Modula-2 is a terrific compiler. I found only one real bug using it for this and some other projects: remarkable for any new product. It's dazzlingly fast as well, compiling the 201-line LINEDWG.MOD in five seconds from Enter to system prompt on my 8-MHz AT clone with a 40-ms hard disk.

Lest the previous paragraph leave you with the impression that I'm just overflowing with praise for all and sundry, let me take a whack at The Master Himself. Professor Wirth might be the progenitor of structured programming languages, but he writes stylistically sloppy code. If this guy were a student in one of my programming classes, I'd drop his grade for the lack of comments and a tendency to put unrelated statements on the same line. Wirth gets away with it because he's Who He Is, but that's no excuse, particularly in a work that is to Modula-2 what K & R is to C. And while I'm at it, Springer-Verlag gets a hiss for consistently producing the worst-indexed books in the computer publishing industry.

So much for congratulations and contumely. Let's get on with it.

The Line-Drawing Module

The definition module for LineDrawing is LINEDWG.DEF in Listing One, page 88. With minor stylistic changes, it adheres faithfully to Wirth's definition. The only alteration of substance is the name itself; LineDrawing doesn't fit into the eight characters DOS allows, so I shortened it to LineDwg.

There's one other change as well. In the prototype, Wirth defines a procedure called area, which fills a rectangular region with a color. But elsewhere, in connection with the Queens program on pages 5859 (which actually calls the procedure), he refers to an apparently identical process called paint. The latter makes more sense, so that's its name in LINEDWG.DEF.

I chose to implement LineDwg using EGA (the IBM Enhanced Graphics Adapter) mode 10h, which furnishes 640 x 350-pixel color graphics. This is somewhat at odds with the Wirth model, which proposes four gray scales from white (0) to black (3), but it makes sense in that the EGA is widely available and it has decent resolution. Mapping Wirth's color indicators to EGA color numbers is easy to do via a CASE statement.

The problem with EGA 640 X 350 is that the pixels aren't square. To achieve orthogonal integrity on an IBM PC display, the y dimension should be 75 percent of the x. The EGA resolution yields 53.8 percent of x, so everything is taller than it should be. Because Wirth's line-drawing procedure works in increments of 45 degrees, he obviously had square pixels in mind.

The solution is to use a virtual-coordinate space to represent the display. In virtual space, the screen can be 800 x 600 pixels, and following the Cartesian convention, the origin (coordinates [0,0]) can be at the lower-left corner with y ascending upward. Because the virtual range is larger than the device range, rounding off tends to jam pixels together, thus producing visual objects without gaps. The opposite effect-- gapping--occurs when the virtual range is smaller than the physical, as in 400 x 300 pixels mapped to a 640 X 350-pixel display. in both cases you get jaggies, but jaggies are an inevitable feature of the computer graphics landscape. Fortunately, they're not glaringly apparent with the EGA.

Mapping virtual coordinates into physical space is relatively simple. The program works entirely within the virtual range, and only the output functions "know" that the coordinate system is a myth. The functional procedures devX and devY in Listing Two (the LineDwg implementation), page 88, perform virtual-to-physical translations based on factors computed during the module's initialization phase. These functions are called when writing pixels to the device. The only procedure exempt from virtual addressing is writePixel, which works entirely in device space.

Perhaps one reason why LineDrawing has not been implemented elsewhere is that Wirth's thoughts on the subject seem to be incomplete. For example, he formulates the Paint Mode enumeration as a control for the paint and copy routines, yet none of the calls ever touches it. Consequently, it's set here to replace and never changed, and the routines don't refer to it. Likewise the matter of color inheritance is unresolved. The paint and dot procedures accept a color parameter, but what color applies to line? I opted for a "last color used prevails" strategy. The color variable, global to the implementation module but not externally visible, forces the next line to inherit the color of the most recently written pixel.

Wirth's approach emulates turtle graphics by employing the concept of a graphics pen that draws a line as it moves, and any activity causes the pen to come to rest at the last pixel written. You can see this idea at work by examining the line procedure. Px and Py are externally visible virtual coordinates giving the pen's position. Line advances them before writing each pixel so that, when the line is completed, they reflect the location of the most recent pixel. A pen-up motion is effected by changing the values of Px and Py; the turtle instantly moves without drawing. The same end results from writing a black pixel (color 3) to a nonsequential location via a call to dot.

The line routine in LineDraw is quite limited. It draws in direction d for n units from the current pen location. The direction indicator d is a digit 0. .7 expressing a multiple of 45 degrees such that 0 draws to the right, 1 to the northeast, 2 straight up, and so on. To draw lines at unpredictable angles, it's necessary to develop your own routine outside LineDwg; it should call the dot procedure for output because dot maps virtual coordinates into the physical space.

The clear procedure does more than simply clear the screen, but it's consistent with Wirth's ideas. On the IBM PC, any mode change clears the display, even if you switch to the same mode that's currently active. Wirth's demonstration programs inevitably begin with clear in lieu of initiating a graphics mode, so the implemented clear procedure puts the display into graphics. In the absence of indications otherwise, clear also establishes white as the default color. Wirth never calls clear again after the start of the run, but your programs can call it any number of times to reset the display without leaving the graphics mode.

Using the Module

From the standpoint of the PC Wirth's programs are inconsiderate because they leave the machine in graphics mode on exit. Obviously he doesn't program on a PC, or he'd have included the switch back to text that precedes the termination of Listing Three , page 90.

This program, called SIERPIN.MOD, is included here as a test to make sure the graphics functions work as expected. Wirth's book shows the output of the program, which is based on a mutually recursive graphics algorithm developed by the Polish mathematician Sierpinski. The only changes from the Wirth model are the addition of the switch back to 80 x 25-pixel color text at the end and removal of superfluous Read statement from the REPEAT...UNTIL loop. The output of the program (to my astonishment, it ran correctly the first time) appears in Figure 1, page 118.

Figure 1: Output from SIERPIN.MOD, drawn with LineDwg routines.

The paint procedure fills a rectangular area with the specified gray scale. The origin of the area is at (x, y), extending right for w units and up for h units, expressed in virtual coordinates. This routine is internally optimized to prevent rewriting pixels that physically coincide as a result of mapping round-offs. Even so, because it's based on ROM BIOS interrupt 10h, it's agonizingly slow. Much greater efficiency could be achieved by manipulating the EGA registers directly. I chose not to in the interest of limiting the scope of this project; the EGA is a whole big subject of its own.

The copyArea procedure also uses the ROM BIOS and is similarly poky in performance, even though-like paint-it's internally optimized to operate at the physical pixel level. This routine copies part of the screen to another location. The source is at (sx, sy) and the destination at (dx, dy), the copied area being ow virtual units wide by dh units high. You'll see it in operation a little later.

The two text routines in LineDwg are Write and WriteString, which parallel similarly named procedures in Modula-2's standard InOut module. The difference is that they start writing at the current pen position well, near it, anyway. This implementation uses the default EGA character set rather than a stroked font, so it places the text cursor--hence the first character--in the 8 X 14 physical cell occupied by the pen. That's as close as you can get with the built-in characters, and it should be good enough for most applications. The foundation routine is Write, which outputs a single character and advances the pen. WriteString merely calls Write for each character in the string.

This is where the bug in Stony Brook Modula-2 popped up. It's unclear what's wrong, but literals passed as parameters to WriteString sometimes show up with a garbage character appended to the end. Either the compiler isn't placing a null terminator in literals, or else the Length procedure has a glitch. Through trial and error, I discovered that an extra space at the end of the literal makes the problem go away sometimes, and other times taking that padding space out has the same effect. This is a bug in the category of an annoyance and hardly a major flaw.

The SPIRAL.MOD program in Listing Four, page 92, exercises all directions of line, plus copyArea and the text-writing routines. Though a small program, it runs for quite a while because of the inefficiency of ROM BIOS calls, two of which are made for each pixel copied to the outlined window at the right side of the screen. The figure copied is a portion of the spiral pattern; Figure 2, page 122, shows the final screen.

Figure 2: Output from SPIRAL.MOD ( Listing Four)

These two demonstration programs are nice to look at, especially the interesting Sierpinski curve, but they have no practical value. For that reason, I've thrown in MATHPLOT.MOD (Listing Five, page 93) to illustrate a more useful application of Wirth's LineDrawing module. This program plots the function y = cos x + sin 2x, which is representative of any number of mathematical graphing applications in both business and scientific programming.

MathPlot draws three curves in different gray scales using the dot routine. Dark gray follows sin 2x, light gray plots cos x, and white is the curve deriving from their sum, where 0< x <10. Thus the curves go slightly beyond x = 3, tracing the function through a bit more than 1.5 circles. The vertical grid lines delineate intervals of 2, and the horizontal grids indicate unity on either side of the x axis, giving visual reference points for the curves. The photo in Figure 3, page 122, doesn't do it justice. This is a handsome display that you have to see on an EGA screen to appreciate the usefulness and elegance of the gray-scale plots produced by Wirth's LineDrawing module.

Figure 3: Photo of MathPlot's output

Stony Brook's Modula-2

[LISTING ONE]

DEFINITION MODULE LineDwg;
  EXPORT QUALIFIED
    width, height, CharWidth, CharHeight, PaintMode, Px, Py,
    mode, dot, line, paint, copyArea, clear, Write, WriteString;

  TYPE PaintMode = (replace, add, invert, erase);

  VAR Px, Py     : INTEGER; (* Current coordinates of drawing pen *)
      mode       : PaintMode;  (* Current mode for paint and copy *)
      width      : INTEGER;   (* Width of picture area, read-only *)
      height     : INTEGER;  (* Height of picture area, read-only *)
      CharWidth  : INTEGER;               (* Width of a character *)
      CharHeight : INTEGER;              (* Height of a character *)

  PROCEDURE dot (c : CARDINAL; x, y : INTEGER);
        (* Place a dot at coordinate x, y in color c *)

  PROCEDURE line (d, n : CARDINAL);
        (* Draw a line of length n in direction d
           (angle = 45 * d degrees) *)

  PROCEDURE paint (c : CARDINAL; x, y, w, h : INTEGER);
        (* Paint the rectangular area at x, y of width w and
           height h in color c, where 0 = white, 1 = light gray,
           2 = dark gray, 3 = black *)
        (* Note: This proc is also called 'area' by Wirth *)

  PROCEDURE copyArea (sx, sy, dx, dy, dw, dh : INTEGER);
        (* Copy rectangular area at sx, sy into rectangle at dx, dy
           of width dw and height dh *)

  PROCEDURE clear;        (* Clear the screen *)
        (* Note: Also places display in EGA 640 x 350 color mode *)

  PROCEDURE Write (ch : CHAR);   (* Write ch at pen's position *)

  PROCEDURE WriteString (s : ARRAY OF CHAR);

END LineDwg.

IMPLEMENTATION MODULE LineDwg;

(* Implements LineDrawing module defined by N. Wirth in *)
(*   "Programming in Modula-2." This module assumes EGA *)
(*   monitor in 640 x 350 color graphics mode.          *)
(* Uses virtual coordinates, where origin is at lower   *)
(*   left corner of screen area, size is 800 x 600.     *)
(* Adapted by K. Porter for DDJ, April 1988 issue       *)
(* ---------------------------------------------------- *)

  FROM SYSTEM IMPORT REGISTERS, INT;
  FROM Strings IMPORT Length;

  CONST  VW  = 800.0;        (* virtual width of screen *)
         VH  = 600.0;                 (* virtual height *)
         RW  = 640.0;  (* real device width, EGA screen *)
         RH  = 350.0;                  (* device height *)
         EGA = 16;          (* EGA 640 x 350 color mode *)

  (* Variables local to this module *)
  VAR   reg    : REGISTERS;
        xf, yf : REAL;
        color  : INTEGER;

  (* --------------LOCAL PROCEDURES ------------------------- *)

  PROCEDURE writePixel (c, x, y : INTEGER);
                     (* write pixel of color c at device x, y *)

  BEGIN
    reg.AH := 12;
    CASE c OF           (* map color indicator to EGA palette *)
      0 : reg.AL := 15|                              (* white *)
      1 : reg.AL :=  7|                         (* light gray *)
      2 : reg.AL :=  8|                          (* dark gray *)
      3 : reg.AL :=  0                               (* black *)
    END;  (* of CASE *)
    reg.BX := 0;
    reg.CX := x;
    reg.DX := y;
    INT (16, reg);
    color := c;                       (* set prevailing color *)
  END writePixel;
  (* ------------------------ *)

  PROCEDURE devX (x : INTEGER) : INTEGER;
                                   (* translate x to device x *)

  BEGIN
    RETURN TRUNC (xf * FLOAT (x));
  END devX;
  (* ------------------------ *)

  PROCEDURE devY (y : INTEGER) : INTEGER;
                                   (* translate y to device y *)

  BEGIN
    RETURN TRUNC (RH - (yf * FLOAT (y)));
  END devY;


(* ------------------ VISIBLE PROCEDURES -------------------- *)

  PROCEDURE dot (c : CARDINAL; x, y : INTEGER);

        (* Place a dot of color c at coordinate x, y *)

  BEGIN
    writePixel (c, devX (x), devY (y));
  END dot;
  (* ------------------------ *)

  PROCEDURE line (d, n : CARDINAL);

        (* Draw a line of length n in direction d
          (angle = 45 * d degrees) *)

  VAR  xdir, ydir : INTEGER;    (* x and y directions given d *)
       distance   : CARDINAL;

  BEGIN
    CASE d OF
      0 : xdir :=  1; ydir :=  0|                    (* right *)
      1 : xdir :=  1; ydir :=  1|
      2 : xdir :=  0; ydir :=  1|                       (* up *)
      3 : xdir := -1; ydir :=  1|
      4 : xdir := -1; ydir :=  0|                     (* left *)
      5 : xdir := -1; ydir := -1|
      6 : xdir :=  0; ydir := -1|                     (* down *)
      7 : xdir :=  1; ydir := -1
    END;    (* of CASE *)
    FOR distance := 1 TO n DO
      Px := Px + xdir;                     (* advance the pen *)
      Py := Py + ydir;
      dot (color, Px, Py);        (* draw in prevailing color *)
    END;
  END line;
  (* ------------------------ *)
  PROCEDURE paint (c : CARDINAL; x, y, w, h : INTEGER);

  (* Paint the rectangular area at x, y of width w and
            height h in color c, where 0 = white,
            1 = light gray, 2 = dark gray, 3 = black *)

  VAR  cy, prevY, dy : INTEGER;

  BEGIN
    prevY := 0;
    color := c;                   (* set new prevailing color *)
    FOR cy := y TO y+h DO
      dy := devY (cy);                (* get current device y *)
      IF dy <> prevY THEN           (* if new scan line, draw *)
        Px := x; Py := cy;
        line (0, w);
        prevY := dy;        (* remember where last line drawn *)
      END
    END
  END paint;
  (* ------------------------ *)

  PROCEDURE copyArea (sx, sy, dx, dy, dw, dh : INTEGER);

        (* Copy rectangular area at sx, sy into rectangle
            at dx, dy of width dw and height dh *)

  VAR  c, x, y, ix, iy, nx, ny, tx, ty : INTEGER;

  BEGIN
    ix := devX (sx);    iy := devY (sy); (* source dev coords *)
    nx := devX (sx+dw); ny := devY (sy+dh);  (* ending coords *)
    tx := devX (dx);    ty := devY (dy);     (* target coords *)
    FOR y := ny TO iy DO                  (* go top to bottom *)
      FOR x := ix TO nx DO
        reg.AH := 13;                           (* read pixel *)
        reg.BX := 0;
        reg.CX := x;
        reg.DX := y;
        INT (16, reg);             (* get pixel color into al *)
        reg.AH := 12;                  (* write pixel to dest *)
        reg.CX := tx + x - ix;
        reg.DX := ty + y - iy;
        INT (16, reg);
      END
    END
  END copyArea;
  (* ------------------------ *)

  PROCEDURE clear;                        (* Clear the screen *)
                (* Also places display into EGA graphics mode *)

  BEGIN
    reg.AH := 0;
    reg.AL := EGA;                           (* EGA 640 x 350 *)
    INT (16, reg);
    color := 0;               (* reset default color to white *)
  END clear;
  (* ------------------------ *)

  PROCEDURE Write (ch : CHAR);  (* Write ch at pen's position *)

  VAR  cc, cr : INTEGER;                  (* Char col and row *)

  BEGIN
    cc := devX (Px) DIV  8;       (* Derive char pos from pen *)
    cr := devY (Py) DIV 14;
    reg.AH := 2;                  (* Set text cursor position *)
    reg.BX := 0;
    reg.DX := (cr * 256) + cc;
    INT (16, reg);
    reg.AX := 2560 + ORD (ch);     (* Write char via ROM BIOS *)
    reg.BX := 7;                      (* Light gray text only *)
    reg.CX := 1;
    INT (16, reg);
    Px := Px + CharWidth;    (* advance by char virtual width *)
  END Write;
  (* ------------------------ *)

  PROCEDURE WriteString (s : ARRAY OF CHAR);

  VAR  i : CARDINAL;

  BEGIN
    FOR i := 0 TO Length (s) DO
      Write (s[i]);
    END
  END WriteString;

  (* ---------------- INITIALIZATION ------------------------ *)

BEGIN
  Px         := TRUNC (VW / 2.0);    (* Virtual screen center *)
  Py         := TRUNC (VH / 2.0);
  mode       := replace;
  width      := TRUNC (VW);            (* Virtual screen size *)
  height     := TRUNC (VH);
  CharWidth  := 10;            (* Char sizes in virtual units *)
  CharHeight := 24;
  xf         := RW / VW;              (* x translation factor *)
  yf         := RH / VH;              (* y translation factor *)
  color      := 0;                  (* white is default color *)
END LineDwg.

MODULE Sierpin;

(* Based on the Sierpinski recursive model in N. Wirth's book *)
(*   "Programming in Modula-2."                               *)
(* Wirth's program has been modified slightly to accommodate  *)
(*   EGA graphics mode on the IBM PC.                         *)
(* Written by K. Porter for DDJ, April 1988 issue.            *)

(* ---------------------------------------------------------- *)

FROM InOut   IMPORT Read;
FROM LineDwg IMPORT width, height, Px, Py, clear, line;
FROM SYSTEM  IMPORT REGISTERS, INT;

CONST SquareSize = 512;

VAR  i, h, x0, y0 : CARDINAL;
     ch           : CHAR;
     reg          : REGISTERS;

PROCEDURE A (k : CARDINAL);
BEGIN
  IF k > 0 THEN
    A (k-1);   line (7, h);   B (k-1);   line (0, 2*h);
    D (k-1);   line (1, h);   A (k-1)
  END
END A;
(* -------------------------- *)

PROCEDURE B (k : CARDINAL);
BEGIN
  IF k > 0 THEN
    B (k-1);   line (5, h);   C (k-1);   line (6, 2*h);
    A (k-1);   line (7, h);   B (k-1)
  END
END B;
(* -------------------------- *)

PROCEDURE C (k : CARDINAL);
BEGIN
  IF k > 0 THEN
    C (k-1);   line (3, h);   D (k-1);   line (4, 2*h);
    B (k-1);   line (5, h);   C (k-1)
  END
END C;
(* -------------------------- *)

PROCEDURE D (k : CARDINAL);
BEGIN
  IF k > 0 THEN
    D (k-1);   line (1, h);   A (k-1);   line (2, 2*h);
    C (k-1);   line (3, h);   D (k-1)
  END
END D;
(* -------------------------- *)

BEGIN
  clear;
  i := 0;
  h := SquareSize DIV 4;
  x0 := CARDINAL (width) DIV 2;
  y0 := CARDINAL (height) DIV 2 + h;
  REPEAT
    i  := i + 1;
    x0 := x0 - h;
    h  := h DIV 2;
    y0 := y0 + h;
    Px := x0;
    Py := y0;
    A (i);   line (7, h);   B (i);   line (5, h);
    C (i);   line (3, h);   D (i);   line (1, h);
  UNTIL (i = 4);
  Read (ch);                             (* hold for keypress *)
  reg.AH := 0;
  reg.AL := 3;             (* restore 80 x 25 color text mode *)
  INT (16, reg);
END Sierpin.

MODULE MathPlot;

(* Graphs the function y = cos x + sin 2x using LineDwg *)
(* K. Porter, DDJ, April 88                             *)

FROM MathLib0 IMPORT sin, cos, real, entier;
FROM LineDwg IMPORT line, dot, clear, WriteString, Px, Py;
FROM InOut IMPORT Read;
FROM SYSTEM IMPORT REGISTERS, INT;

VAR  x, sx, cx, y : REAL;
     xc           : INTEGER;
     ch           : CHAR;
     reg          : REGISTERS;

PROCEDURE yc (y : REAL) : INTEGER;
BEGIN
  RETURN entier (y * 100.0) + 300;
END yc;

BEGIN
  clear;
  Px :=   0; Py := 300; line (0, 800);        (* x axis *)
  Px :=   0; Py := yc (1.0);                   (* grids *)
  WriteString ("  1");
  dot (2, Px, Py);                     (* set dark gray *)
  line (0, 750);
  Px := 0; Py := yc (-1.0);
  WriteString (" -1"); line (0, 750);
  FOR xc := 125 TO 799 BY 126 DO      (* vertical grids *)
    Px := xc; Py := yc (2.0); line (6, 400);
  END;
  Px := 310; Py := 599;
  WriteString ("y = cos x + sin 2x ");

  FOR xc := 1 TO 799 DO
    x  := real (xc) / 80.0;             (* x to radians *)
    sx := sin (2.0 * x);
    dot (2, xc, yc (sx));     (* plot sine in dark gray *)
    cx := cos (x);
    dot (1, xc, yc (cx));          (* cos in light gray *)
    y  := sx + cx;
    dot (0, xc, yc (y));      (* plot function in white *)
  END;
  Read (ch);
  reg.AH := 0; reg.AL := 3; INT (16, reg)  (* text mode *)
END MathPlot.

MODULE Spiral;

(* Draws a spiral, then copies part of it to a window *)

FROM SYSTEM IMPORT REGISTERS, INT;
FROM LineDwg IMPORT Px, Py, line, copyArea, WriteString, clear;
FROM InOut IMPORT Read;

VAR  reg  : REGISTERS;
     ch   : CHAR;
     n, d : INTEGER;

BEGIN
  clear;
  Px := 250;
  FOR n := 0 TO 24 DO                      (* Draw the spiral *)
    d := n MOD 8;
    line (d, n * 5);
  END;
  Px := 548; Py := 198;            (* Outline the copy window *)
  line (0, 204);
  line (2, 204);
  line (4, 204);
  line (6, 204);
  Px := 630; Py := 440;
  WriteString ("Copy ");
  copyArea (200, 200, 550, 200, 200, 200);    (* Copy portion *)
  Read (ch);                             (* Wait for keypress *)
  reg.AH := 0; reg.AL := 3; INT (16, reg);
END Spiral.

Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.