GameBoy Pixmap Demo (Part 7)

This is the 7th and likely last in the series on Framebuffer-based graphics on the Nintendo GameBoy. As before I'll start with a recap. Then we'll continue with more development, classic 8-bit display routines for pixel plotting and line drawing.

Recap

The incredibly successful 8-bit Nintendo GameBoy used tile-based graphics for performance reasons and memory constraints. The 160x144 pixel screen is divided into 20x18 (=360) TileMap locations and each one can point to one of 256, 8x8 2-bpp Tiles. However, a raster trick enables another 128 tiles to be selected part-way through each refresh and I want to use that feature to provide a full frame buffer.

In previous posts I described the tile system, then interesting aspects of the CPU, then the basic mechanism for generating a full frame buffer and displaying characters in all ink/paper combinations. The most recent posts added line drawing and dynamic text generation (waiting for VRAM to be free), resulting in a significant slow-down.

Plot

There are two main tasks, in plotting (in any colour), calculating the base address and performing the shift and mask from the bit position to both planes. The calculation is pretty easy, expressed in 'C':

addr=0x8000|( (((y>>3)*20)+(x>>3) ) <<4)|((y&7)<<1);

As it's in assembly, for the character address calculations, I'd combine the (y>>3)*20 into (((y&0xfe)>>1)*5), and I would combine the <<1 in ((y&7)<<1) into the <<4 shift because it saves on an 8-bit shift.

For pixel plotting we only need to consider the ink colour. I need to mask 2 bytes on a given tile row, one for each colour plane.

maskLo=(ink&1)?(128>>(x&7)):0; // it's 128>>, because pixel 0 is on the left.

maskHi=(ink&2)?(128>>(x&7)):0;

andMask=~(128>>(x&7));

*addr=(*addr&andMask)|maskLo;

addr++;

*addr=(*addr&andMask)|maskHi;

Of course, it's more efficient to calculate the (128>>(x&7)) once. However, we can see that this will still involve a reasonable amount of calculation and given the need to make the most of the limited HBlank time, I decided to recalculate all the shifts and masks for all bit positions and colours. This reduces the calculations to the following in SM83 assembly:

  ld b,2
PlotLp:
  waitScan 5
  ld a,[de] ;dst
  and [hl] ;src mask
  inc hl
  or [hl]
  inc hl
  ld [de],a 
  inc e ;only need to inc e, it's 16 byte aligned.
  dec b
  jr nz,PlotLp ;7*8+12=68 cycles

There's one loop for each plane. HL points to the table of masks, which is a whole 128b long!

PlotMsk:
  ; Lf7t. Right Lf7t. Right Lf7t. Right Lf7t. Right
  dw 0x007f,0x007f,0x00bf,0x00bf,0x00df,0x00df,0x00ef,0x00ef, ;ink 0, x=0..3
  dw 0x00f7,0x00f7,0x00fb,0x00fb,0x00fd,0x00fd,0x00fe,0x00fe, ;ink 0, x=4..7
  dw 0x807f,0x007f,0x40bf,0x00bf,0x20df,0x00df,0x10ef,0x00ef, ;ink 1, x=0..3
  dw 0x08f7,0x00f7,0x04fb,0x00fb,0x02fd,0x00fd,0x01fe,0x00fe, ;ink 1, x=4..7
  dw 0x007f,0x807f,0x00bf,0x40bf,0x00df,0x20df,0x00ef,0x10ef, ;ink 2, x=0..3
  dw 0x00f7,0x08f7,0x00fb,0x04fb,0x00fd,0x02fd,0x00fe,0x01fe, ;ink 2, x=4..7
  dw 0x807f,0x807f,0x40bf,0x40bf,0x20df,0x20df,0x10ef,0x10ef, ;ink 3, x=0..3
  dw 0x08f7,0x08f7,0x04fb,0x04fb,0x02fd,0x02fd,0x01fe,0x01fe, ;ink 3, x=4..7

Since a single plot loop is 68 cycles long already, the full table could easily make a crucial difference to performance.

Draw

Draw uses a standard Bresenham line drawing algorithm. This is actually a very versatile concept that can be applied to pulse-density modulation or dithering or waveforms at arbitrary frequencies and allows fractional calculations to be performed without divisions. I actually first came across it in an exercise in chapter 18 of the ZX81 Basic Manual, because the ZX81 lacks a draw routine. The description in the ZX81 manual is clearer than Wikipedia.

But basically (sic), the concept is this. If we start with a ≤ 45º line, ∆x pixels long and ∆y up, then it makes sense to loop ∆x pixels from x0 and increment y by ∆y/∆x each step s. So, y(s)=y0+int(∆y*s/∆x). Thus, this is equivalent to adding ∆y to a running sum at each step s as though it was:

∆y_sum+=∆y;

y'=y+int(∆y_sum/∆x);

And because ∆y_sum only causes y' to be incremented when it's ≥∆x, in fact all we need to do is calculate the fraction for ∆y_sum and as soon as it's bigger than ∆x, we increment y. So, the calculation never needs more bits than ∆x and in our case, because the coordinate space for the screen is 160x144, we never need more than 8 bits.

This deals with one octant (≤45º). The next octant (45º.. 90º) is the same, but with ∆y and ∆x reversed. The remaining quadrants are just the same except that either or both of ∆y and ∆x are negated. So, by taking the absolute values (and remembering the signs), then sorting ∆y and ∆x to see which is the major loop, we can handle all the cases.

In the GameBoy implementation, there's two further tricks we need to consider:

1. How to fit all of this data into the SM83's registers (and we need bc to be (y,x) since that's what Plot expects). This is non-trivial, because there's at least 8 different variables to consider including two signs, ∆y, ∆x, x, y, ∆y_sum and the loop count. Yet the SM83 only has 7 registers (and register a is usually needed as a temp). We solve this by putting the signs in individual bits in register h and push/popping af for the loop count.
2. We can't have ∆x and ∆y as signed values on input, because they're only +/- 7-bits in magnitude. And if we supply (x0,y0) and (x1,y1) as inputs, then the difference could also be a signed 8-bit value. We solve this by treating sign(∆x):∆x and sign(∆y):∆y as 9-bit values, so the signs go into the sign bits and ∆x and ∆y both become abs(∆x) and abs(∆y).

This makes the drawing loop reasonably compact at 37 lines:

Draw50:

  ;h={yIsMax:0000:majorAxisSign:minorAxisSign}, b=y, c=x

  ;d=minorAxisSum, e=minorAxisLength, l=majorAxisLength.
  push af
  ld a,h ;Delta=(h&2)-2
  and 2
  dec a ;resulting in +1 or -1.
  bit 7,h
  jr nz,DrawYLin
  add a,c ;x is linear
  ld c,a
  jr Draw55
DrawYLin:
  add a,b ;y is linear.
  ld b,a
Draw55:
  ld a,d ;val
  add a,e ;+=frac
  ld d,a
  cp l ;lim (val-lim)=>cy if val<lim.
  jr c,Draw60
  sub l
  ld d,a
  ld a,h ;Delta=((h&2)>>1)-2
  and 1
  add a,a
  dec a
  bit 7,h
  jr nz,DrawXDiag ;y is linear (y is max)
  add a,b;YisDiag, Y+=((h&2)>>1)-2
  ld b,a
  jr Draw60
DrawXDiag: ;XisDiag, X+=((h&2)>>1)-2
  add a,c
  ld c,a
Draw60:
  call Plot
  pop af
  dec a
  jr nz,Draw50

Performance

Using a simple test that fills the screen with pixels, the plot rate is 7.0s for 20*18*64=23,040 pixels, so that's about 3300 pixels per second, or about 55 pixels per frame, good enough for animation.

By comparison, a ZX Spectrum can draw pixels at least at the rate of 3.33s for 16002 pixels = 4805 pixels. With a similar GameBoy test I found the draw rate is: 1.8s for 80*80 pixel lines, about 3,555 pixels/s which is about the same speed as the basic plotting test.

Conclusion

Plotting and Drawing lines pretty much concludes this series, though I might add a few updates for better illustrations. I started out wondering how feasible it was to implement a full pixel-mapped frame buffer on a Nintendo GameBoy, given that this wasn't how graphics were designed to be used on it.

To prove the feasibility I figured it needed to support basic text and graphics functionality similar to early 8-bit computers:

• Displaying text: and I chose a 4x8 font, because that can't be done with tiles and many 8-bitters supported 40 columns of text.
• Clearing a screen and scrolling.
• Plotting and Drawing straight lines.

And all these had to support all 4 colours (really, shades).

I think I've managed to demonstrate reasonable feasibility and I've had fun programming in the slightly odd Z80-but-not-Z80-and-not-8080, SM83 architecture. It would be possible to implement a text editor that runs in a 40x18 text mode or some graphs or Mandelbrot or simple 3D.

If I were to take it further, the following springs to mind:

• Scrolling up or down by n lines, maybe all 4 directions are feasible.
• Drawing circles and filled-in triangles.
• Blitting would be cruelly slow, so I don't plan on that.
• Text input via the gamepad that's fairly fast (then an editor would work OK).

But for now, I think that's a wrap.

The complete source code is available here.

The ROM image is available here.

I've tested the demo on the macOS SameBoy emulator.