Jack Bresenham's Line Drawing Algorithm

Recently, it has came to my attention that IBM's own, Dr. Jack Bresenham used a IBM 1401, a 1407 typewriter inquiry console (which the museum lacks, and no one seems to have seen) and a Calcomp plotter, and when he created his line famous algorithm, which is still in use today.**

Though, I am not an official liaison of the museum and perhaps I have forgotten my place, yet I do wonder if IBM has any particulars about the backstory of how Bresenham's line algorithm was created? Was it indeed done on a 1401? Are there any photos of the first plots, or the equipment?

...

And if a punch-card copy of Bresenham's algorithm exists, like art, it should hang proudly on a wall.

...

Sincerely,
Brenda Ellen Make

**Ref: https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm

I just tried it from the only form I could find.

I resent it. The first email address you had went through, the other: Archive1@us.ibm.com bounced. The second attempt returned and out-of-office.
At least one went through. : )

Thank you for your understanding,
Brenda

Great — glad you forwarded your wonderful email about Bresenham to Jamie and Max (re: his algorithm for drawing lines, first done on a Calcomp connected to a 1401) !

Cheers,

— Robert

p.s. This may be Jack Elton Bresenham (from TruePeopleSearch. I’ll try calling tmrw).

Jamie and Max are thoughtful and engaging folks!! Jamie was actually new to computers when she took over the IBM archive directorship in 2014.

Here’s a 2016 photo of the Jamie, Max (and/Dave Bennet, of the CHM RAMAC demo team) visiting the RAMAC disk stack unit (350) on display at IBM Almaden Research, where I worked 2001 - 2018.)

I found a copy of Bresenham's original paper (but not the original source code,) following the breadcrumbs....

There's a page dedicated to the line drawing algorithm.
https://www.markwrobel.dk/post/amiga-machine-code-letter12-linedraw/

Which has an interview with Bresenham :
https://www.youtube.com/watch?v=fR6npND-0rw

Which was likely the likely the front source connecting it to the 1401, the National Institute of Standards and Technology, and mentions that
https://xlinux.nist.gov/dads/HTML/bresenham.html

It also leads me here, to a PDF that's pay-walled, that might contain details :
https://ieeexplore.ieee.org/document/5388473

Which leads me around it to find Bresenham's original paper but not the code, but it does mention 1401!
https://www.cse.iitb.ac.in/~paragc/files/bresenham_line.pdf

"The algorithm can be programmed without the use of multi- plication or division. It was found that 333 core locations were sufficient for an IBM 1401 program (used to control an IBM 1627). The average computation time between successive incrementations was approximately 1.5 milliseconds."

Which seems to change the branding of the Calcomp plotter to the identical one with the IBM logo, which perhaps was just done to keep it all IBM, back then, but apparently IBM also sold the plotters with their name, the IBM 1627
https://en.wikipedia.org/wiki/IBM_1627

Which also leads us back to the NIST page, which states "Calcomp (Jim Newland and Calvin Hefte) had copies"

Which will lead me here:
https://www.calcompgs.com/

Take Care,
Brenda

Awesome research (!) into Bresenham’s algorithm and its reported deployment on an IBM 1627 (aka Calcomp drum plotter) attached to a 1401.

It’s interesting that IBM OEM’ed the Calcomp drum plotters (models 565 and 563) as IBM 1620 peripherals:

• IBM 1627 Model 1 — Calcomp 565 — Plotting area: 11 inches by 120 feet, 1/100 inch incremental-step size, up to 18,000 steps/minute.

• IBM 1627 Model 2 — Calcomp 563 — Plotting area: 29-½ inches by 120 feet, 1/100 inch incremental-step size, up to 12,000 steps/minute.

Bob,

> I have some Calcomp drum plotters. ...
> Just picked up a Calcomp 563. It's pretty clean but with a badly dented drum. I have to figure out a way to fix that.

Is one of those the smaller Calcomp model 565? :)

Interesting & fun history,

— Robert

Ken

Some of the original code is found!!!!
I don't know if it's all there, it seem a small even for something that is only supposed to use 33 word locations. There is indeed an END statement, but I don't know if there were other routines.
(I tried a google search on some of the code, but nothing else, yet.)

"Jack Bresenham sent me code to drive a CalComp plotter attached via an RPQ to a 1407 console typewriter. It shows the four directional commands. I don't know what the "pen up" and "pen down" commands were. Do you?"

http://www.bitsavers.org/1401/progs/bresenham/bresenham.s

For some reason, the web maintainer also had a variation too.
Ref: http://www.bitsavers.org/1401/1401-progs.html

Take Care,
Brenda

     000       JOB  ENTER PLOT POINTS FROM 1407
               CTL  4411
               ORG  501
     *
     *                          TRAVEL SUBROUTINE
     *
     TRAVEL    SBR  LEAVE&3
               ZA   ZEROA,ALPHA
               ZA   XTRGT,DELX
               ZA                  YTRGT,DELY
               S    XPR,DELX
               S                   YPR,DELY
               MCW  XTRGT,XPR
               MCW                 YTRGT,YPR
               ZA   DELX,DELA
               ZA                  DELY,DELB
               MZ   *&8,DELA                 NEED MAGNITUDE SO  A B BITS
               MZ   *&1,DELB
     *                          DETERMINE OCTANT
               C    DELA,DELB
               BM   DELXN,DELX
               BM   DELYN,DELY
               MN   PXPY,D45
               BH   D00PY
     D00PX     MN   PX,D00
     SETDEL    ZS   DELA,DEL
               A    DELA           DELA NOW DOUBLED-SEE DRIVING LOOP
               A                   DELB NOW DOUBLED-SEE DRIVING LOOP
               B    TALPHA
     DELXN     BM   DELXYN,DELY
               MN   NXPY,D45
               BH   D00PY
     D00NX     MN   NX,D00
               B    SETDEL
     DELYN     MN   PXNY,D45
               BL   D00PX
     D00NY     MN   NY,D00
               B    DELAY
     D00PY     MN   PY,D00
     DELAY     MN   DELY,DELA                DELA S/B DELY  SAVE PLUS
               MCW
               MN   DELX,DELB                DELB S/B DELX
               MCW
               B    SETDEL
     DELXYN    MN   NXNY,D45
               BL   D00NX
               B    D00NY
     *                          PLOTTER DRIVING LOOP
     D00GO     MCW  %T0,D00,S                MOVE RELATIVE ZERO DEGREES
     TALPHA    C    ALPHA,DELA
     LEAVE     BE   0                        0 DUMMY
               A    TWOA,ALPHA        NOTE   DELA HAS BEEN DOUBLED
               A    DELB,DEL          NOTE   DELB PREVIOUSLY DOUBLED
               BM   D00GO,DEL
               MCW  %T0,D45,S
               S    DELA,DEL          NOTE   DELA PREVIOUSLY DOUBLED
               B    TALPHA
     *                          CONSTANTS
     ALPHA     DCW  #6
     YTRGT     DCW  #6                  DESIRED Y COORDINATE
     XTRGT     DCW  #6                  DESIRED X COORDINATE
     DELY      DCW  #6                  Y2 MINUS Y1
     DELX      DCW  #6                  X2 MINUS X1
     YPR       DCW  #6                  PRESENT Y COORDINATE
     XPR       DCW  #6                  PRESENT X COORDINATE
     DELB      DCW  #6                  DEPENDENT VARIABLE DIFF
     DELA      DCW  #6                  INDEPENDENT VARIABLE DIFF
     DEL       DCW  #6                  DECISION DIFFERENCE
     D00       DA   1X1,G               RELATIVE 0 DEGREE MOVE
     D45       DA   1X1,G               RELATIVE 45 DEGREE MOVE
     PX        DCW  @3@                   0  DEGREE CODE
     PXPY      DCW  @2@                  45  DEGREE CODE
     PY        DCW  @1@                  90  DEGREE CODE
     NXPY      DCW  @8@                 135  DEGREE CODE
     NX        DCW  @7@                 180  DEGREE CODE
     NXNY      DCW  @6@                 225  DEGREE CODE
     NY        DCW  @5@                 270  DEGREE CODE
     PXNY      DCW  @4@                 315  DEGREE CODE
     ZEROA     DCW  &0
     TWOA      DCW  &2
     *      
     *                          END OF TRAVEL SUBROUTINE
     *      
     *                                  --CALLING SEQUENCE--
     *                               1.   ZA   DESIRED X COORDINATE, XTRGT
     *                               2.   ZA   DESIRED Y COORDINATE, YTRGT
     *                               3.   B    TRAVEL
     *      
     *                          XPR,YPR ARE UPDATED
     *                          TRAVEL EXECUTED
     *                          CONTROL RETURNED TO INSTR AFTER *B TRAVEL*
     BEGINX    LCA  MXGX,47
               SW   27,MSGX-1
               MCE  XPR,33
               MCW  &XTRGT,PLACE&6
     TYPE      LCA  @}@,48
               MCW  %T0,21,W
               CS   8
               LCA  @}@,8
               BIN  VIN,Q
               B    *-8
     VIN       MCW  %T0,1,R
               SBR  PLACE&3
               BIN  TYPE,*
               BCE  PLACE&7,1,}
               MA   @I9H@,PLACE&3
               BM   VMINUS,1
               MCW  @?@,PLACE
               BWZ  VPLUS,1,B
               SW   1
     PLACE     ZA   0,0
               BW   BEGINY,MSGX-1
               B    TRAVEL
               B    BEGINX
     VMINUS    MCW  @!@,PLACE
     VPLUS     SW   2
               B    PLACE
     BEGINY    LCA  MSGY,47
               SW   27
               CW   MXGX-1
               MCE  YPR,33
               MCW  &YTRGT,PLACE&6
               B    TYPE
     MSGX      DCW  @X NOW     0 -, ENTER NEXT X@
     MSGY      DCW  @Y NOW     0 -, ENTER NEXT Y@
               END  BEGINX

Enjoyed chatting with you this morning. Brought back many good memories of my time working in Dr. Eugene Lindstrom’s comp lab at IBM San Jose from 1962-1967.

Attached are several scanned images you may find of interest.
1, 1a, 2, 3, 4, 5, 6, 7

Having enjoyed celebrating my 85_th birthday last month, I do need to start thinking about what to do with mementos from my past. Among other items, I have examples of drawings and the 1403 printout of the full plotting program I wrote for use in Dr. Lindstrom’s lab. The 1401 program would use tape output from 7094 output tape with columns of numbers to plot curves from various engineering calculations. … and, somewhere, I have a box of punched cards with related, but now unknown content.

Ciao, Jack
j.bresenham@computer.org
1.505.896.7893
303 Palo Alto Dr. NE Rio Rancho, New Mexico 87124