Mondrian Shows Off Dissolve Effect

By Mike Morton, Cambridge, MA

DissBits: A subroutine to do "dissolve" shots

One of the first sample Mac programs was Cary Clark's "File". The "About File" menu item did a nifty piece of animation with text which grew and seemed to "zoom out" toward the viewer. Clark calls this a "bit of fluff". I disagree: effects like this are part of the allure of the Mac. Here's a description of another visual effect which "File" inspired: a "dissolve" routine called DissBits, which fades from one image to another on the screen.

The routine is patterned after Quickdraw's CopyBits, which copies a rectangle in one bitmap to any other rectangle in any other bitmap. Along the way, it can clip to any region, stretch the image if the rectangles aren't the same size, and use any transfer mode. DissBits performs only some of these functions: it will work with any two bitmaps, but the rectangles must be of the same size, no clipping is done, and the bits are always copied directly, as the "srcCopy" mode does.

How does DissBits work? The idea is simple: pixels are copied from one rect to another in a random sequence which copies each pixel once. There are two tricky parts to this: finding a way to copy each bit only once and coding it to be fast. This article covers both issues.

The random sequence which hits all the bits is simple to implement. Let's reduce it to a smaller problem first: Suppose we want to copy all bits in a rect H bits wide and V bits high. Then we want a sequence which produces all (v, h) combinations in the rect. Suppose instead we have a random sequence of numbers n, 0 through V*H. If we take each number n and compute h=(n / V) and v=(n mod V), that gives us all (v, h) pairs in the rect. So we've changed the problem of hitting every point to the problem of generating the first V*H integers in a random sequence. If we can find a "1-dimensional" sequence, that gives us the "2-dimensional" sequence.

A way to generate the linear sequence without huge arrays is this: start with any number between 1 and N. To get the next sequence element, shift the number right by one bit. If a bit fell off in the shift, exclusive-or in a magic value (more on this value later). Repeat this to get more sequence elements. The resulting sequence will be all the numbers from 1 through 2k-1, where "k" depends on the magic value (don't worry, I really will explain about the magic values). To get numbers between 0 and N, choose a magic value such that 2k-1 is greater than or equal to N, and throw away elements which are too big. This may seem like a waste, but generating the extra elements is very fast. (Note: the sequence doesn't produce the value zero; this has to be done with special-case code.)

An example: if you want to cover an 80-by-100 bit rect, you must produce the numbers 0 through 7999 and map those to the points in the rect. To do this, use a magic value of $1D00, which will produce a sequence from 1 through 213-1; discard all the ones above 7999. Add special-case code to throw in the value 0.

How does one know which magic value to use? If you're into abstract algebra, you'll know that the magic values are related to prime polynomials. If you'd rather take the empirical approach, you can write a program to find the values. This took two weeks of CPU time on a Lisa. You'll probably want to use the table in the DissBits source. It gives the magic values to use for all "k"s from 2 to 32. (Be careful: the table is compressed; see the code which expands it.)

To sum up the sequence problem: to copy the pixels of one rect to another requires these steps: Find the total number of pixels in the rect. Find "k" which will produce a sequence including that number of elements (and a few more, which will be discarded). Cycle once through the sequence, taking each element and checking if it's in range. If so, map the integer to coordinates inside the rect and copy that point. When the sequence returns to the first element ( it always will), copy the point (0, 0), which the sequence doesn't produce.

The actual implementation has one difference: instead of using "modulo" and division to map a sequence element to two coordinates, the number is broken bit-wise, extracting the low bits to get one coordinate, and the high bits to get the other. This means that the sequence is slightly longer, and that both coordinates must be checked to see if they're in range, but the time saved by avoiding a 68000 DIV instruction is worth it.

Now for the graphics part. To copy a pixel from one rect to another, we want to know the state of the source pixel. We could use Quickdraw's "GetPixel", and then plot a black or white pixel depending on the source pixel. This would be too slow. Instead, DissBits works directly with the graphical data.

All graphics work is done using bitmaps: arrays of pixels in memory. A bitmap has a "base address", which points to the data. It has a "bounds" rect, which describes the coordinate system of the bitmap: the range of v and h coordinates. And it has a field called "rowbytes", which describes how many bytes are used to store each row of graphical data. The "rowbytes" field is important: to move "down" one pixel in the bitmap, you skip "ahead" by one row of bytes in memory -- "rowbytes" tells you how much to skip.

The link between a coordinate pair (v,h) and a bit in memory is through a bitmap. The point is (v-bounds.top) rows down into the bitmap and (h-bounds.left) columns across into it. Call these offsets "dv" and "dh". The base address of the bitmap is where you start. Then to skip "dv" rows, each of "rowbytes" bytes, skip (dv*rowbytes) bytes. The address of the start of the row is:

baseaddr + dv*rowbytes

To index by "dh" bits into the row, remember that each byte is eight bits. To get to the correct byte, the above address needs (dh/8) more bytes, so the final byte address is:

pixaddr = baseaddr + dv*rowbytes + (dh/8)

To select the correct bit number within this byte, use the remainder from computing (dh/8) -- this is (dh mod 8). Unfortunately, the 68000's method of bit numbering is backwards from the way Quickdraw numbers bits, so the 68000 bit number in the byte is:

pixbit = 7 - (dh mod 8)

These formulas let us take a point (v, h) in a bitmap and find the bit in memory, so we can quickly test the point with the instruction

BTST pixbit,pixaddr

If we also find bit and byte addresses for the pixel we want to copy to, we can branch after the BTST and do either a BSET or BCLR to set the destination pixel to match the source.

Putting all this together, we can take two rectangles of equal size, each in a bitmap, and produce a sequence of integers which (discarding some elements) takes us through all coordinate pairs in the rect. For each point, we use the bitmaps to find the actual bits in memory, test the source bit and set the destination bit appropriately.

Most of the algorithm is described in the code. The code has become obscure as successive optimizations have been added. One very important optimization should be explained in detail: a lot of the time spent in the loop is calculating (dv*rowbytes). If "rowbytes" is a power of two (as it is for the Mac screen), DissBits notices this and shifts into "middle gear" using a different loop and using shifts to avoid the multiply. If the rects being copied are the full width of the bitmaps, some more tricks can be done, and a third loop is used. At top speed, DissBits can copy an image onto the full screen in under 3.5 seconds.

Low Level Tricks

Most of the high-level optimizations are too detailed to cover here; the comments describe them in detail. Some low-level tricks worth mentioning are:

• When changing Quickdraw's numbering of bits to the 68000 conventions, it's actually not necessary to map x to (7-x). Since only the low 3 bits of the bit index are used in bit instructions, a NOT will convert the bit offset. (See the code after LOOPROW.)

• The first part of getting a new sequence element is shifting it to the right. If no magic value needs to be XOR-ed in, then the row number (in the high bits of the sequence element) is in range. (See the code after NEXT.)

• If the first sequence element is the magic value, the next to last element before the cycle loops is one (this is easy to prove). When 1 is shifted right, it becomes 0, so the end of the sequence is easy to detect. (See the code after NEXT.)

• Since the code to find the next sequence element wants to detect the case where no carry has occurred, and the result of the shift isn't zero, it combines these two conditions with a BHI instruction.

• When the high bits of the sequence element are shifted down to get the row number, they're soon multiplied by the "rowbytes" value. If "rowbytes" is even, it can be halved and the shift-down can be reduced by one. The code in HALFLOOP does this repeatedly, until "rowbytes" is odd.

• In the fastest case (copying the whole screen), it doesn't matter if the bit-numbering is reversed or not, since every bit will be copied anyway. This step is skipped in the "high-gear" loop.

The Mondrian Demo

"Mondrian", a short demo program for the dissolve effect is given here. Be sure to pull out "About Mondrian" from the apple menu to see the high-speed, full-screen dissolve.

DissBits is a good example of how the Mac's processing power can animate an effect which few other microcomputers can do in real time. Even machines with faster 68000 processors, such as the Amiga, can't get the speed the Macintosh can in copying the full screen, because of Apple's decision to make the screen's width a power of two pixels, allowing shifts instead of multiplies.

DissBits is a favorite effect of mine. I use it in nearly everything I write. I hope you'll use it in your applications, and perhaps be inspired to exploit the Mac's visual technology in new ways, just as Cary Clark's "bit of fluff" brought about DissBits.

program Mondrian;
  
{ Mondrian -- a demo of the "dissBits" procedure.  The user clicks 
  and drags; the selected rectangle is inverted by copying the rect 
  from the screen to an offscreen bitmap using the "srcXor" mode 
  of copyBits, then dissolving that to the screen, giving the 
  impression of slowly inverting in place. }

{ Written by Mike Morton for MacTutor }
{ Converted to TML Pascal by David E. Smith }
  
    {$I Memtypes.IPas }          { TML Mac libraries}
    {$I QuickDraw.IPas } 
    {$I OSIntf.IPas }
    {$I ToolIntf.IPAS }
    
  const
      appleMenu    = 1;
        aboutItem= 1;{ menu item: About Mondrian... }
      fileMenu     = 2;
        quitItem = 1;{ menu item: Quit }
      lastMenu     = 2; { number of menus }
      mBarHeight   = 22;  { height of the menu bar, in pixels }
 applesymbol= 20;{apple symbol character }
 
  var
    myPort: grafPort;{ our graphics environment }
    bits: bitmap;         { the offscreen bitmap }
    done: boolean;          { flag for the main loop }
    myMenus: array[1..lastMenu] of menuHandle;     { for the menu manager 
}
    ev: eventrecord; { for main loop, or awaiting click }

  procedure dissbits (sb, db: bitmap; sr, dr: rect); external; { dissolver 
}

  { Frame a rectangle, even it "topLeft" and "botRight" are oriented 
wrong. }

  procedure frameNeatRect (VAR r: rect);     { draw rect; flip corners 
if needed }
  var
    rc: rect;    { copy of rect (don't change caller's) }
  begin;
    pt2rect (r.topLeft, r.botRight, rc);           { sort out the rectangle's 
corners }
    frameRect (rc);{ now draw it }
  end;  { procedure frameNeatRect }

  { Get the mouse location, but don't let them drag into the menu bar. 
}
  
  procedure getScrMouse (VAR p: point); { get mouse loc, avoiding the 
menu bar }
  begin;
    getMouse (p);         { get mouse location in global coords }
    if p.v < mBarHeight   { in the menu bar? }
    then p.v := mBarHeight; { yes: force it to below the bar }
  end;  { procedure getScrMouse }

  { Called for a click on the "desk".  Track the mouse, sampling slowly 
to
    avoid shimmer.  When they release, dissolve and invert the selected 
area. }
  
  procedure doinvert;{ track mouse; invert the rect }
  var
    alarm: longint;         { time at which we should sample mouse }
    r: rect;{ rectangle the user selected }
    mloc: point;          { mouse location }
  begin;
    penMode (patXor);{ so we can easily undraw the rect }
    getScrMouse (r.topLeft);{ remember where we started }
    r.botRight := r.topLeft;{ initially, the rectangle is null }

    while button do{ wait for the button to be up }
    begin;
       alarm := tickcount + 3;{ what time should we wake up? }
       repeat until tickcount >= alarm;      { delay a bit (avoid flicker) 
}

       getScrMouse (mloc);  { where's the mouse now? }
       if not equalPt (mloc, r.botRight)     { did it move from where 
it was last? }
       then begin;          { yes!  they've done some dragging }
          frameNeatRect (r);{ erase rect (we're XORing, remember?) }
          r.botRight := mloc; { remember the new location }
          frameNeatRect (r);{ and draw the new rectangle }
       end; { of changing rectangles }
    end;         { of looping while the button is down }

    frameNeatRect (r);    { button's up: erase last rectangle }
    pt2Rect (r.topLeft, r.botRight, r);      { straighten things out 
for our caller }
    copyBits (screenbits, bits, r, r ,notsrcCopy,nil);   { copy & flip 
}
    dissbits (bits ,screenbits, r, r);       { "fade to black" (or whatever) 
}
  end;

  procedure about; { blather about the program }
  const
    textHeight = 22; { pixel height for a row of text }
  var
    oldbits: bitmap; { for saving the screen's bitmap }
    aboutr: rect;         { general purpose rect }
  procedure say (s: str255);{ print a string; move text rect down }
    begin;
      textbox(ptr (longint(@s)+1), length (s), aboutr, { print the text... 
}
        teJustCenter);    { ...centered }
      offsetRect (aboutr, 0, textHeight); { slide down one line }
    end;
  begin;{ main code for "about" }
    oldbits := screenBits;         { remember old bitmap (the screen) 
}
    setPortBits (bits);   { draw offscreen }
    aboutr := screenBits.bounds;             { start with the whole screen 
}
    eraseRect (aboutr);   { clean the whole (off)screen }

    penNormal;   { no funny stuff with the pen here }
    insetRect (aboutr, 30, 30);  { move in a bit }
    frameRect (aboutr);   { outline the rectangle }
    insetRect (aboutr, 2, 2);          { move in a teeny bit more }
    frameRect (aboutr);   { outline another rect }
    insetRect (aboutr, 2, 2);          { move in another teeny bit more 
}
    frameRect (aboutr);   { outline the last rectangle }
    insetRect (aboutr, 1, 1);          { keep "textBox" rects small }

    aboutr.top := aboutr.top + 48;           { start text a ways down 
the screen }
    aboutr.bottom := aboutr.top + textHeight;      { make the rect one 
line high }

    textFont (0);         { write in the system font }
    textSize (12);          { and keep it legible }
    say ('A simple demonstration of the "dissBits" dissolve effect.');
    say ('To invert a rectangle, click anywhere outside the menu bar.');
    say ('Drag until you have the rectangle you want, then release.');
    say ('');            { skip a line }
    say ('The dissolve subroutine is public domain "freeware".');
    say ('');            { skip a line }
    say ('Mike Morton');
    say ('Version 2.0, September 1985');
    say ('        (click to continue)');     { don't hide the mode }

    aboutr := screenBits.bounds;   { again, specify the whole screen 
}
    dissBits (bits, oldbits, aboutr, aboutr);      { dissolve in offscreen 
text }
    repeat until getnextevent(mdownmask+keyDownMask, ev);      { await 
click }

    setPortBits (oldbits);         { go back to drawing on the screen 
}
    eraseRect (screenbits.bounds);                 { clean everything 
up }
    drawMenuBar;          { and bring back the menu bar }
  end;           { procedure about }

  procedure docommand (cmd: longint);        { do a menu command }
  var
    menu, item: integer;           { menu number, item number for menu 
}
  begin;
    menu := hiword (cmd); { extract menu number... }
    item := loword (cmd);          { ...and item number }
    case menu of          { branch on the selected menu }
      appleMenu: about;   { this is our only apple-menu item }
      fileMenu:   done := true;  { assume they hit "Quit"; flag it }
    end;         { of case on meny }
    hilitemenu (0);         { un-highlight the menu }
  end;

  procedure click (ev: eventrecord);    { handle a mouseclick }
  var
    code:   integer;          { type of click }
    win:    windowPtr;    { dummy for findwindow call }
  begin;
    code := findwindow (ev.where, win); { look up the window }
    case code of          { branch on what happened: }
      inmenubar: docommand (menuselect (ev.where));      { menu: do a 
menu command }
      indesk:   doinvert;          { desk: track the mouse; dissolve 
}
    end;         { of branching on code }
  end;  { procedure click }

  procedure eventhandle;  { main loop's routine }
  begin;
     if getnextevent (everyevent, ev)        { was there an event? }
     then begin;          { yes: handle it }
       case ev.what of    { branch on the type }
         mousedown: click (ev);    { handle a click }
         keydown, autokey: sysbeep (2); { we ignore keydowns }
       end;  { case of events }
     end;   { of handling an event }
  end;    { procedure eventhandle }

  procedure init;{ initialize everything }
  var
    i: integer;  { menu counter }
  begin;
      initGraf(@thePort);          { fire up quickdraw }
      openPort(@myPort);           { get a drawing environment }
      initFonts;          { we use the font manager for "about" }
      initWindows;          { and this for locating mouseclicks }
      initMenus;          { and the menu manager }
      eraseRect (myPort.portRect);           { clean the screen }

      for i := 1 to lastMenu do    { loop through all the menus... }
         myMenus[i] := getMenu (i);          { ...and read in each one 
}
      myMenus[appleMenu]^^.menudata[1] := chr(applesymbol);    { "@" 
-> apple }
      for i := 1 to lastMenu do              { again, loop through menus... 
}
        insertMenu (myMenus [i], 0);         { ...and now install each 
one }
      drawMenuBar; { show the completed menu bar }

      done := false;          { tell main loop program's not done }
      initCursor;         { set the arrow cursor -- we're ready }
  end;  { procedure init }

  procedure initoffs (VAR bits: bitmap);     { set up the offscreen bitmap 
}
  var
    rows: integer; { number of rows in the bitmap }
    cols: integer; { number of columns }
    totbytes: integer;  { number of bytes needed for bitmap }
  begin;
    with bits do  { lots of operations on the bitmap: }
    begin;
      bounds := screenbits.bounds;                 { copy the screen's 
coordinates }
      rows := bounds.bottom - bounds.top;    { compute # of rows in the 
screen... }
      cols := bounds.right-bounds.left;            { ...and the number 
of columns }
      { Note that a bitmap's "rowbytes" must be even; hence this odd 
formula: }
      rowbytes := (((cols)+15) div 16) * 2;  { compute number of bytes 
per row }
      totbytes := rowbytes * rows;           { rows*(bytes/row) = bytes 
for bitmap }
      baseaddr := qdptr (newptr (totbytes));       { allocate space for 
the bitmap }
    end;

    if longint (bits.baseaddr) = 0                 { allocation failed? 
}
    then begin;           { yes: bag it before we crash }
      moveTo (40, 40);
      DrawString ('Sorry!  Not enough memory for Mondrian to run...  
click to exit');
      flushEvents (everyevent, 0);                 { don't allow "clickahead" 
}
      repeat until getnextevent(mdownmask,ev);     { wait for them to 
click }
      done := true;{ call it a day }
    end;{ of handling failed memory allocation }
  end;  { procedure initoffs }

       { main program }
       
  begin;
    init;          { initialize Mac-application things }
    initoffs (bits);          { create an offscreen bitmap }
    flushEvents (everyevent, 0);                   { ignore old clicks, 
keys, etc. }

    repeat eventhandle    { do the user's bidding...}
      until done;{ ...'til they get bored and ask us to stop }
  end.  { program Mondrian }

Putting It All Together

by David E. Smith

Now comes the problem of putting all the pieces together. The Pascal source code for Mondrian was written first in Lisa Pascal and has been converted here to TML Pascal on the Macintosh. Actually, very little was required to make this conversion; only the TML libraries were substituted for the Lisa compiler versions. Nearly all the source code compiled without change. The TML product has been covered extensively by Alan Wootton in the Pascal column and is highly recommended as an inexpensive full-blown Pascal compiler that is MDS ".REL" file compatible. This source code is compiled to MDS assembly source as shown graphically in figure 3. That assembly code is then run through the MDS assembler to produce the ".REL" file for the MDS linker. In this respect, the product works much like the Absoft Fortran package, only better because there is no "run time" package to fool around with and no incompatibility problems with MDS as we have noted in our Fortran columns. [MICROSOFT please take note!!] Only one problem was encountered. It seems TML does not handle the Writeln statement yet. That was replaced with DrawString, which worked fine.

Even though the TML Pascal produces an MDS link file for you, it is best to either edit that file or use your own. In this case, I used my own, shown below. The DissBits subroutine [see next article] is assembled and linked with the Mondrian source and the resource file. As is my custom, I chose to do the resources in assembly so they could be assembled with MDS and linked directly to the two ".REL" files, thus avoiding the RMaker loop. One thing to note in the link file produced by the TML compiler is the names of the Pascal support routines that must be linked to your source code also. The result is a stand-alone, fully machine code program!

!PAS$Xfer
]
)
/OUTPUT Mondrian Game

mondrian
dissbits
PAS$Sys
OSTraps
ToolTraps

/TYPE 'APPL' 'MDRN'
/BUNDLE
/RESOURCES
MONDRIAN_RSCS

$ 

; Mondrian_rscs.asm
; resource file for the Mondrian game
; created using the assembler
; signiture is creator tag 
;
RESOURCE 'MDRN' 0 'IDENTIFICATION'

 DC.B 42, 'Mondrian  version 2.0 -- 21 September 1985'
 
.ALIGN 2
RESOURCE 'BNDL' 128 'BUNDLE'

 DC.L 'MDRN'     
 DC.W 0,1 
 DC.L 'ICN#'
    DC.W0 ;# Maps-1
    DC.W 0,128      ;MAP 0 TO 128
    
 DC.L 'FREF';FREF 
    DC.W0 ;# of maps-1
    DC.W 0,128      ;MAP 0 TO  128

RESOURCE 'FREF' 128 'FREF 1'
 
 DC.B 'APPL', 0, 0, 0
 
.ALIGN 2
RESOURCE 'ICN#' 128 'MY ICON'

; FIRST APPLICATION ICON BIT MAP

DC.L $00010000, $00028000, $00044000, $00082000 
DC.L $00101000, $002FF800, $004FF400, $008FF200 
DC.L $010FF100, $020FF080, $040E0F40, $080E0F20 
DC.L $13EE0F10, $2221FF08, $4221FF04, $8221C082 
DC.L $42218041, $22213022, $13E1C814, $081E7F0F 
DC.L $04023007, $02010007, $01018007, $0081E007 
DC.L $005E3FE7, $003E3E1F, $001E3C07, $0009F800 
DC.L $0005F000, $00022000, $00014000, $00008000

;  mask data: 32 rows of 32 bits

DC.L $00010000, $00038000, $0007C000, $000FE000 
DC.L $001FF000, $003FF800, $007FFC00, $00FFFE00 
DC.L $01FFFF00, $03FFFF80, $07FFFFC0, $0FFFFFE0 
DC.L $1FFFFFF0, $3FFFFFF8, $7FFFFFFC, $FFFFFFFE 
DC.L $7FFFFFFF, $3FFFFFFE, $1FFFFFFC, $0FFFFFFF 
DC.L $07FFFFFF, $03FFFFFF, $01FFFFFF, $00FFFFFF 
DC.L $007FFFFF, $003FFE1F, $001FFC07, $000FF800 
DC.L $0007F000, $0003E000, $0001C000, $00008000

; MENU BAR RESOURCES

.ALIGN 2
RESOURCE 'MENU' 1 'apple menu'

 DC.W 1 ;MENU  ID
 DC.W 0 ;WIDTH HOLDER
 DC.W 0 ;HEIGHT HOLD
 DC.L 0 ;RESOURCE ID 
 DC.L $1FF  ;ENABLE ALL 
 DC.B 1 ; TITLE LENGTH
 DC.B 20; APPLE title
 
 DC.B 18; ITEM  LENGTH
 DC.B  'About Mondrian... '
 DC.B 0 ; NO ICON
 DC.B 0 ; NO KEYBOARD 
 DC.B 0 ; MARKING 
 DC.B 0 ; STYLE OF TEXT
 
 DC.B 0 ; END OF MENU 
 
.ALIGN 2
RESOURCE 'MENU' 2 'file menu'

 DC.W 2 ;MENU  ID
 DC.W 0 ;WIDTH HOLDER
 DC.W 0 ;HEIGHT 
 DC.L 0 ;RESOURCE ID 
 DC.L $1FF  ;ENABLE ALL 
 DC.B 4 ; TITLE LENGTH
 DC.B 'File'; file menu 
 
 DC.B 4 ; ITEM LENGTH
 DC.B  'Quit'
 DC.B 0 ; NO ICON
 DC.B 0 ; NO KEYBOARD 
 DC.B 0 ; NO MARKING 
 DC.B 0 ; STYLE OF TEXT
 
 DC.B 0 ; END OF MENU