MacPaint is a monochromatic raster image painting program that introduced many people to mouse-driven controls, tool palettes, and copy and paste integration with other applications. One of two launch applications for the Apple Macintosh in 1984, MacPaint is emblematic of the Macintosh’s early quirky revolutionary branding, focus on ease of use, and appeal to artistic customers. Using the source code, we examine the design and implementation of the application. We find that the buffer management and bucket filling algorithms demonstrate mechanical empathy with the 68k platform and leverage the limitations of the domain as a means to improve performance. We also find positive and negative aspects in the code style and architecture and its pliability for change. Finally, we dispute some claimed novel aspects of the program while also arguing for its significance and impact on the development of digital graphic systems. MacPaint 1.5 (1985) Correction 04-06: Corrected details on the origin of PCPaint. Table of Contents Background Timeline Developer: Bill Atkinson Development and Testing Design and Source Code Interesting Algorithms and Designs Alternative Paths and Competitors Post Release Conclusion Special Recognition References Background At the Boston Computer Society’s general meeting on January 30th 1984, Steve Jobs laid out his rationale for why Apple’s newest product, the Macintosh computer, was the third milestone product of the computer industry after Apple’s own Apple II and the IBM PC. The Macintosh would be the “computer for the rest of us.” The Macintosh used the same software as the Lisa bringing the same ease of use from a point-and-click interface and pull down menus as well as sharing the same fast Motorola 68000 processor. After highlighting hardware features such as portability, the 3.5" diskette drive, and the AppleBus support, Jobs let the computer do a demo on its own. Booting the Mac from a diskette, the Mac displayed its name and the “Insanely Great” logo, and then showed the first real, application image: a MacPaint screenshot showing a woodcut of a Japanese lady. MacPaint screenshot with Japanese Lady (1984) Apple used the screenshot heavily within their advertisements and most of the audience would have seen static screenshots of MacPaint and MacWrite in the months beforehand, but the audience was still delighted. Twenty-nine minutes in, Jobs introduces a panel of the Macintosh development team and Bill Atkinson starts the first demo, a demo of MacPaint that he developed. Over the next seven minutes, Atkinson demonstrates how to make art with the program. The audience’s first applause comes when he uses an eraser to erase little chunks of previously drawn lines and rectangles. The applause is due to both how easy and quick the tool is to use but also that it demonstrates the program is working with actual pixels; he isn’t creating new clipping regions or restricted to deleting entire shapes. The audience also applauded when Bill draw lines filled with patterns and then again when, by holding down the spray can, the paint grows denser. Heralding the feature’s value, the fourth applause comes when Bill zooms in and manipulates individual pixels using the Fat Bits mode. The audience similarly loves the many ways areas of the image can be selected, moved and copied. Atkinson finishes the demo by copying an image of a fish that will soon be pasted into a MacWrite document. In an unspoken nod to the limits of the Macintosh’s hardware, Atkinson closes MacPaint so the memory can be used by MacWrite. Randy Wigginton, who is about to demo MacWrite, pauses to praise Bill’s work on QuickDraw, the foundational graphical library for the Lisa and the Macintosh. “Without Bill, none of us would be up here on stage.” Bill Atkinson’s contributions at Apple, including foundational user interface contributions for the Lisa and Macintosh computers, and one of the two application programs that shipped with the “Insanely Great” Macintosh as the advertisements claimed, have been well-recorded. With the release of the QuickDraw and MacPaint source code in 2010, we have an opportunity to examine the technical design and implementation of his work. This article examines the MacPaint application, how it was built, what are some of the interesting algorithms and engineering trade offs, and how we might measure its impact against the larger industry trends around image painting and rastering technology. Timeline The development of MacPaint is intertwined with the development of the mouse and the graphical user interface, the Lisa and Macintosh computers, and QuickDraw, the foundational graphics library used by both the Lisa and the Macintosh. This timeline focuses on MacPaint and contemporary competitor painting programs, not on the overall history of raster drawing programs. See (Smith 2001) for a history of early raster drawing programs and their commercial applications and development. 1982 Over a period of six weeks, Atkinson develops a prototype painting program that “sort-of worked” (Young 1985, pg 315). The source code file MyTools.text, later renamed to MyTools.a, states it was created October 31st. 1983 In January, Apple announces the Lisa Computer, although no units are shipped until June. The Lisa includes Atkinson’s QuickDraw library. Microsoft broadens the development of mouse-based applications by releasing their first Microsoft Mouse. The package includes a color raster drawing program program called ‘Doodle.’ Doug Wolfgram releases perhaps the first third-party drawing program with ‘Mouse Draw,’ which uses the Microsoft Mouse. Atkinson resumes work on MacPaint, at this point called MacSketch. The set of palettes and tools is already very close to the eventual MacPaint UI. The image in the screenshot (below) is celebrating ROM 2.0; based on MyTools.a, this would date the image between February 13th and March 16th, when the file was regenerated for ROM 2.0 but before ROM 2.4. MacSketch (MacPaint c. 1983; Source folklore.org) MacSketch is renamed MacPaint in April. Between then and October, Atkinson iterates on the program adding features and improving performance. The last entry in MyTools.a is dated September 1983. In December, Apple advertises the Macintosh with a full-color brochure. MacPaint is featured prominently and is used to educate the public on how tool palettes, menus, and copy-paste work. The ad also mentions that the content area can be scrolled for more work space. 1984 With great fanfare, the Apple Macintosh is shown at the Boston Computer Society January 30th General Meeting. Bill Atkinson demos MacPaint (and implicitly, QuickDraw) to the crowd. The original Macintosh 128k comes with two applications: MacWrite and MacPaint. In May, MacPaint 1.3 is released as part of a free software update to customers. This version adds the ability to lasso an object and repeatedly fill it (via the Fill item in the Edit menu) with a pattern. In September, MacPaint 1.4 is released along with the Macintosh 512k. Competitors quickly adopt the MacPaint interface. In June, Mouse Systems ships PCPaint 1.0 bundled with a mouse in competition with Microsoft. PCPaint, co-developed by John Bridges and Doug Wolfgram, is based on Apple’s MousePaint program (demoed in November 1983 at Comdex), which itself is based on an early, unreleased version of MacPaint. (MacPaint originally featured a menubar “Aids” but changed it to “Goodies” before it was released.) Similarly, ZSoft Corporation ships their PC Paintbrush, also DOS-based but with an interface derived from MacPaint. 1985 Microsoft releases a new version of their mouse. They drop their ‘Doodle’ program and replace it with a rebranded version of PC Paintbrush, licensed from ZSoft Corporation. In April, Apple releases System Software 2.0 which includes MacPaint 1.5 (https://archive.org/details/mac_Paint_2). This is the last version until 1988, when MacPaint 2.0 is released by a new developer. There are no more official releases of MacPaint. Developer: Bill Atkinson When you start MacPaint, the name Bill Atkinson briefly flashes in the credits. You can also find Atkinson’s name and a small portrait in the About menu. MacPaint 1.5 About Window (1985) Ironically for someone who would rise to be an Apple Fellow, Bill Atkinson did not receive classical training in computing. His undergraduate education was in chemistry and biochemistry with graduate training in neuroscience. However, he was not disconnected from the computing scene. He built both an IMSAI and an Altair computer (Atkinson 2004, pg 4). Further, his college work emphasized using computers and he made contacts that would prove highly influential to his career. While at UC San Diego, Atkinson met Jef Raskin and was introduced to Raskin’s unconventional computer lab which emphasized direct and real-time connections with computers. He also met Guy Bud Tribble at UCSD, who would later live with Atkinson and help develop the Macintosh. Atkinson’s mentor at the University of Washington, Kent Wilson, introduced him to computer graphics and innovations in the field, such as Ivan Sutherland’s work on Sketchpad. Lured to Apple in 1978 by Jef Raskin, Atkinson became the company’s first application software developer. His first project was a stock portfolio evaluator because, while Apple featured one in an advertisement, they did not have any in the catalog (Atkinson 2004, pg 7). His second major project was helping port the UCSD Pascal system to the Apple II. With no other structured programming options, Lisa development adopted this version of Pascal (Atkinson 2004, pg 9). In 1979, Steve Jobs made visits to Xerox Parc along with a small group of Apple employees, including Atkinson. At Parc they were shown the Alto computer, Smalltalk programming language, and (likely) the Bravo text editor (Atkinson 2004, pg 18). Transferred to the Lisa project, Atkinson was responsible for LisaGraf, the foundational graphics library (later named QuickDraw), as well as the original window manager, menu manager, and event manager (Atkinson 2004, pg 20). Since the Macintosh re-used software from the Lisa, in particular Atkinson’s user interface and graphics code, he moved onto the Macintosh team where he started to work on MacPaint in earnest in 1983. Unlike the founders of Adobe, Atkinson did not come from the computer graphics research world, but was familiar with research advances through his academic mentors and had met luminaries such as Douglas Engelbart. Similar to the Adobe founders who worked on the same problems multiple times, he had time to iterate, with several years of experiments as Lisa developed from a research effort into a product. Intentionally straddling both foundational and application development, Atkinson had the viewpoint of a “vertical integrator,” able to control where functionality should go and how the interfaces should work. Development and Testing Finding life in the Apple office too “busy” (Atkinson 2004, pg 20), he worked out of a home laboratory using a prototype Apple Lisa. The Lisa had a “Workshop” mode which featured a graphical editor and a command-line environment for compiling and other development activities. Atkinson took Polaroids of the user interface as it evolved and drove into work to share them with the team. Fortunately for posterity, Atkinson saved the Polaroids and we have a detailed visual history of the evolution of the Lisa interface and QuickDraw capabilities as shown in the 2022 CHM interview below. (SketchPad is briefly shown and discussed, starting at 9:45.) The Macintosh team used the ‘Monkey’ as a durability and robustness test mechanism. Developed by Steve Capps, the Monkey would randomly type keys, move objects, and interact with menus (Atkinson 2010, pg 14-15). The team used a computer running in Monkey mode to effectively stress-test an application. MacPaint was able to survive two weeks without crashing. Monkey mode can be seen in the source code: 1 2 3 4 5 6 7 8 9 .FUNC Monkey ;--------------------------------------------------------------------- ; ; FUNCTION Monkey: BOOLEAN; ; TST MonkeyLives ;IS THE MONKEY ACTIVE ? SGE 4(SP) ;YES IF >= ZERO NEG.B 4(SP) ;CONVERT TO PASCAL BOOLEAN RTS To prevent Monkey mode from quitting the program and thus ending the test prematurely, the Pascal code calls this function to selectively disable the Apple menu, File menu, and the Quit Program command. Susan Kare, who served as the graphics designer for the Macintosh, was the main customer of MacPaint. Atkinson watched her use MacPaint and “see what she stumbled on or wished she had” (Atkinson 2004, pg 47). As the only true artist on the team, and someone who used MacPaint as a tool for their job, Kare’s feedback was invaluable. Andy Hertzfeld characterized her impact as “I think a lot of the refinement of MacPaint came from watching an actual user, an actual artist use the program on a day-to-day basis.” (Atkinson 2010, pg 9). Similarly, Atkinson states “I would credit Susan Kare as a co-designer of MacPaint because she used it as I was trying to write it.” (ibid). Design and Source Code Physical Description The MacPaint 1.3 distribution consists of five files: MacPaint.p, 4,688 lines of Pascal (Lisa Pascal variant) MacPaint.rsrc, resource description for the program containing icons, strings, and other localizable attributes. The version string identifies itself as version 1.3. MyHeapAsm.a, 67 lines of assembly for calls into system memory management routines MyTools.a, 300 lines of assembly defining traps or external calls into QuickDraw. A comment states this file was mostly generated via MakeTTraps. This is the only file with a change log and content attributed to someone other than Bill Atkinson. PaintAsm.a, 1,809 lines of assembly containing application code called from the Pascal code We counted physical lines of code using the pascal_count and asm_count programs, both part of David A. Wheeler’s SLOCCount suite. Data Types and Structures MacPaint defines very few datatypes for its own use, leveraging instead types from QuickDraw such as Point, Rect (Rectangle), Pattern, and BitMap. The Pascal code heavily uses global variables; the list extends from lines 212 through 370, with white-space used to group them by commonality. Most of the global variables are used to store various flags or interface state, such as the current font specification. This list is distinct from global constants (lines 27 through 190). Most of the constants are used to specify menu items, buttons, or other interface elements. The application is a set of tools that, ultimately, modify the document which is a fixed size 1-bit bitmap stored as an array of integers. The document lacks dynamic metadata. As pixels are pretty simple, few abstractions or data types are required. Pascal vs. Assembly Roughly one-third of MacPaint’s lines of code are in Motorola 68000 assembly, while two-thirds are in Pascal. In (Young 1985, pg 316), Atkinson explains the rationale and benefit of both languages: By frequency of working on it, I would bring up the Pascal file 20 or 30 times for every one time I brought up the assembly language file. Basically, the information in assembly language doesn’t really need a lot of maintenance. The assembly-language portion contains things that are there for speed, or that were small and I knew wouldn’t need a lot of maintenance. I put them in assembly language just to reduce the code size. By keeping the main control, flow, and logic in Pascal, the program was more pliable. Atkinson’s rationale is supported by the list of procedures in each language. Performance-critical code, such as that which manipulates the buffers directly, is in assembly. User interface control logic is in Pascal, as well as code that handles initial setup or rare operations. Operating system calls, such as checking the amount of spare space in the disk drive or invoking the system beep, are in assembly. Since MacPaint was developed concurrently with the operating system, some functionality may have existed in the ROM but had not yet been exposed by Pascal system libraries. As an example of Atkinson’s assembly style and quality, we present the NearPt function: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 .FUNC NearPt ;----------------------------------------------------------- ; ; FUNCTION NearPt(pt1,pt2: Point; tol: INTEGER): BOOLEAN; ; ; NearPt:=((ABS(pt1.h-pt2.h) < tol) AND (ABS(pt1.v-pt2.v) < tol)); ; MOVE.L (SP)+,A0 ;pop return addr MOVE (SP)+,D0 ;pop tolerance MOVE.L (SP)+,D1 ;pop pt2 MOVE.L (SP)+,D2 ;pop pt1 CLR.B (SP) ;assume result FALSE SUB.W D1,D2 ;calc delta horiz BGE.S DHPOS ;continue if dh positive NEG.W D2 ;else negate for abs value DHPOS CMP.W D0,D2 ;is ABS(dh) < tol ? BGE.S FALSE ;no, return false SWAP D1 ;get pt2.v SWAP D2 ;get pt1.v SUB.W D1,D2 ;calc delta vert BGE.S DVPOS ;continue if dv positive NEG.W D2 ;else negate for abs value DVPOS CMP.W D0,D2 ;is ABS(dv) < tol ? BGE.S FALSE ;no, return FALSE MOVE.B #1,(SP) ;result := TRUE FALSE JMP (A0) ;and return NearPt returns true if two points are “close enough,” even if they are not truly equal. Since points use integral values, this code is not for handling floating point error, but for human imprecision. For instance, if a user was trying to close a polygon by clicking on a previous point, the code allows the polygon to be closed if the user clicks within a few pixels of an earlier point. Similarly, the mouse may slip a small distance during a double click. While this is not particularly performance critical code as it is called a relatively small number of times, it is code that is unlikely to need to change. As is typical for his assembly code, the function is documented with the Pascal calling convention. This function is further documented with a mathematical definition; few functions or procedures warranted descriptive comments. Each line is commented semantically. Almost every assembly line in PaintAsm.a is similarly commented. In contrast, HVConstain is a Pascal procedure. We chose it as an example because it is relatively short and self-enclosed. This procedure is used to constrain or trap an anchor while drawing to a particular direction or a 45 degree angle. For example, the user can hold down shift while drawing a rectangle to force the drawing of a square. Or, while drawing a line, force it to be parallel with the edges of the screen. PROCEDURE HVConstrain(VAR newPt: Point); VAR dh,dv: INTEGER; BEGIN IF shiftFlag THEN { constrain to horiz or vert } BEGIN IF hConstrain AND vConstrain THEN { still chosing direction } BEGIN dh := ABS(newPt.h-ptConstrain.h); dv := ABS(newPt.v-ptConstrain.v); IF (dh > dv) AND (dh > 1) THEN vConstrain := FALSE; IF (dv > dh) AND (dv > 1) THEN hConstrain := FALSE; END; IF hConstrain THEN newPt.v := ptConstrain.v; { horiz } IF vConstrain THEN newPt.h := ptConstrain.h; { vert } END; END; Atkinson has a very consistent naming style for his variables and the code is usually highly readable. In contrast to his assembly code, comments are rare and terse in the Pascal code, although still focused on explaining the semantic purpose of the line. HVConstrain uses one global variable, shiftFlag, to track the user mode, and three global variables to store state: hConstrain, vConstrain, and ptConstrain. Although global variables, there is only one other procedure that accesses the latter three variables directly: InitConstrain. The three variables are commented as belonging to HVConstrain. The design allows a developer to use the variables without proper initialization or accidentally modifying them. Although this is a violation of the design principle of encapsulation, we believe this was an effective trade-off of code complexity and memory resources. Message Loop MacPaint is an early event-driven program. The core of the program is: REPEAT [...] IF GetNextEvent(everyEvent,theEvent) THEN ProcessTheEvent; [...] UNTIL quitFlag; GetNextEvent is a Toolbox Event Manager function that fetches the next event, if it exists, from the event queue. ProcessTheEvent is an application procedure that is a long CASE statement that maps event locations to buttons or, more accurately rectangular areas of the screen. ProcessTheEvent calls other application procedures that control tool-specific modes. ProcessTheEvent is sufficiently low-level it has to measure the time since the last click to differentiate between single and double clicks. Since the user interface is fixed (windows cannot be moved), the code is tedious but easy to follow. Example: Straight Line Tool The Straight Line tool is an exemplar of the software design and the intermix of Pascal, assembly, and QuickDraw functionality. For the StraightLine procedure to be invoked, the user will have previously selected the straight line tool from the tool palette and then clicked (and held) the mouse within the content area. While in this procedure (the straight line “mode”), one end of the line will be anchored at the initial point (startPt) while the other end will follow the cursor until the user releases the mouse button. The mode-driven interface gives the user continuous feedback on what the eventual line will look like within the painting. {$S } PROCEDURE StraightLine; VAR newPt,oldPt,startPt: Point; lineTop,lineBot: INTEGER; BEGIN JamLine; PinGridMouse(startPt); oldPt.h := 1000; { force first time } REPEAT PinGridMouse(newPt); IF shiftFlag THEN Constrain(startPt,newPt,TRUE); IF NOT EqualPt(newPt,oldPt) THEN BEGIN MainToAlt; { erase old } AltBufLine(startPt,newPt,oldPt); oldPt := newPt; END; UNTIL NOT StillDown; END; The first line {$S } is a compiler directive stating that this procedure should live in the default main segment (for more about segments, see the section below Allocation Failure and Segment Anti-Fragmentation) JamLine resets some QuickDraw state using PenNormal and then sets the pen’s size, pattern, and mode (depending on keys being depressed) to the current palette settings. PinGridMouse sets the passed in variable to the current position of the mouse as modified by various modes (e.g. snap to grid, fat bits). Similarly, Constrain sets newPt to a 45-degree constrained point value if the user is holding down the shift key. The REPEAT block tests the StillDown condition. StillDown is a Toolbox Event Manager function that will return false even if the user released and then quickly pressed the mouse button again between invocations. If a line exists (IF NOT EqualPt), the main buffer will be copied into the alt(ernate) buffer. (QuickDraw uses integral values for a Point’s coordinates, so EqualPt does not need a tolerance parameter.) MainToAlt calls BufToBuf, which is an assembly routine that includes the same MOVEM optimization as BufToScrn (see section Fast Buffer to Screen Copy). AltBufLine writes, to the alt buffer, the line from startPt to newPt using the MoveTo and LineTo QuickDraw routines. The contents from the alt buffer are then sent to the screen buffer using a boundary box that includes the oldPt, thus eliminating (by redrawing) any previous line sent to the screen, but also reducing the amount of written data. (BandToScrn also takes care to hide and show the cursor.) The lineTop and lineBot variables are declared but unused. Our assumption is that part of the functionality of AltBufLine originally was part of the StraightLine as it is the only other block to use variables with the same names. The program also uses the constant lineTop to describe the top of the line size palette window, so the compiler must not have considered duplicate lineTop declarations as an error. Interesting Algorithms and Designs Fast Buffer to Screen Copy In an interview with the Macintosh team (Lemmon 1984), the team explains their process for optimizing code size and processing time. After arguing that code must be first made correct before being made fast, Atkinson brings up register allocation. He states: This little baby, the 68000, has sixteen 32-bit registers sitting there, and the way you get performance out of that is to keep them full. Keep the registers full of important stuff all the time. That’s the way you make this processor sing. The buffer copying code, which is performance critical, illustrates this technique. MacPaint uses two off-screen buffers for rendering which are then copied to the screen buffer for display. Within the pascal code, the two buffer’s storage are declared as: mainBuf: ARRAY[0..239,0..12] OF LongInt; altBuf: ARRAY[0..239,0..12] OF LongInt; In Pascal, range definitions are inclusive, so each buffer contains 240 rows of 13 LongInts each. The content area is fixed at 416 pixels by 240 pixels. Since a LongInt contains 32 bits, each row stores 416 single-bit pixels. While MacPaint’s user interface looks well-proportioned to the Macintosh’s display, Atkinson could have designed the content area to be larger or adjusted the design for a portrait arrangement. However, the need to keep registers full suggests the technical reason for the given layout. If we look at the BufToScrn assembly code: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 .PROC BufToScrn,2 ;-------------------------------------------------------- ; ; PROCEDURE BufToScrn(bufPtr,scrnPtr: Ptr; top,bottom: INTEGER); ; ; top and bottom coords are relative to start of buffer ; ; cursor has already been hidden. ; MOVE.L (SP)+,D0 ;POP RETURN ADDR MOVE (SP)+,D1 ;POP BOTTOM MOVE (SP)+,D2 ;POP TOP MOVE.L (SP)+,A1 ;POP SCRNPTR MOVE.L (SP)+,A0 ;POP BUFPTR MOVE.L D0,-(SP) ;PUSH RETURN ADDR MOVEM.L D3-D7/A2-A6,-(SP) ;SAVE REGS SUB D2,D1 ;CALC HEIGHT BLE.S GOHOME ;QUIT IF COUNT <= 0 MOVE D1,-(SP) ;INIT ROW COUNT MOVE D2,D1 ;COPY TOP COORD MULU #52,D1 ;CALC SRC OFFSET ADD.L D1,A0 ;OFFSET SRCPTR MULU screenRow,D2 ;CALC SCRN OFFSET ADD.L D2,A1 ;OFFSET SCRNPTR NXTROW MOVEM.L (A0),D0-D7/A2-A6 ;SUCK UP 13 LONGS FROM BUF MOVEM.L D0-D7/A2-A6,(A1) ;SPIT THEM OUT TO SCREEN ADD #52,A0 ;BUMP SRCPTR ADD screenRow,A1 ;BUMP SCREENPTR SUB #1,(SP) ;DECREMENT ROWCOUNT BNE NXTROW ;LOOP 240 ROWS TST (SP)+ ;POP ROW COUNT GOHOME MOVEM.L (SP)+,D3-D7/A2-A6 ;RESTORE REGS RTS ;AND RETURN The NXTROW loop is executed 240 times with each execution copying 13 LongInts from the buffer. The Motorola 68k supports a “move multiple” (MOVEM) instruction that accepts up to 13 registers as the source or destination. (The .L informs the assembler we are copying long values.) According to (Motorola 1993), a MOVEM instruction requires \(12 + 4n\) clock periods to move memory from an address stored in an A register to registers and \(8 + 8n\) clock periods to move values stored in registers to a memory location (Table 9-16). Thus, memory transfers require \(20 + 12n\) (where \(n\) is the number of registers) or 176 clock periods. In contrast, if the transfers were performed via MOVE instructions, each transfer requires 12 clock periods or 312 clock periods total (Table 9-18). By maximizing the throughput possible with MOVEM by populating all (relevant) registers, each buffer to screen transfer saves 136 clock periods. Bucket Fill (Seed Fill) Bucket Fill is an algorithm that, starting from a given pixel, travels along all adjacent pixels sharing a base color and transforms those pixels to a target color. MacPaint implements a variant of this function by filling the space with a pattern, rather than just a single color. As the boundaries can be arbitrarily complex, this can be an expensive computation. In the worst-case, filling an empty screen, this requires 416 by 240 pixel checks or 99,840 checks in total. Through various tricks, Atkinson’s implementation reduces the amount of work and makes the operation feel fast. (This algorithm is not used when the boundaries are known, such as painting a filled in rectangle. QuickDraw supported drawing filled in polygons directly.) By 1983, several researchers had investigated and published algorithms for bucket filling. SuperPaint, in the mid 1970s, was likely the first implementation of the idea (Glassner 2001); (Lieberman 1978) and (Smith 1979) represent early research papers. The MacPaint algorithm is similar to Lieberman’s algorithm as the algorithm travels along vertical and horizontal pixel paths and supports filling in with patterns as well as colors. MacPaint’s code has been optimized for the restrictions in the domain, i.e. one-bit bitmaps. Within the source code, the Bucket Fill tool is called SeedFill. The SeedFill procedure contains the top-level business logic for the tool: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 PROCEDURE SeedFill(startPt: Point); VAR firstBlack: BOOLEAN; BEGIN firstBlack := PixelTrue(startPt.h,startPt.v,mainBits); CalcMask(mainBits,altBits,altBits.bounds,startPt,firstBlack,FALSE); SetPortBits(altBits); PenPat(thePat); IF firstBlack THEN BEGIN PenMode(patBic); PaintRect(altBits.bounds); InvertBuf(@altBuf); BufAndBuf(@mainBuf,@altBuf); END ELSE BEGIN PenMode(notPatBic); PaintRect(altBits.bounds); BufOrBuf(@mainBuf,@altBuf); END; PenNormal; AltToScrn; clickTime := TickCount; GetMouse(clickLoc); LocalToGlobal(clickLoc); killDouble := TRUE; END; Based on the position of the mouse click (startPt) and the current state of the image (mainBits), the procedure determines if the clicked pixel is black (firstBlack is true) or white. The assembly CalcMask procedure travels the image in mainBits, from the startPt, and computes a mask for the eventual pattern, storing this in altBits. After the boundaries for the fill are determined by CalcMask, the graphics port is set to the alternate buffer and the pattern is set to the currently selected pattern. The pattern transfer mode (patBic or notPatBic) is set to effectively erase the destinations content. The pattern is then filled within the bounding box, inverting the color depending on if the object’s boundary is a black or white pixel. Afterwards, the alternate buffer is sent to the screen and the procedures performs some cleanup. If the result is not what the user wishes, they can undo the action, whereupon the screen switches to the other buffer which contains the content prior to the fill. CalcMask contains the complicated parts of the program. CalcMask is also shared with the Lasso tool, which similarly needs to match arbitrary shapes. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33