Dual-Playfield Nightmare

Okay, people, buckle in and put on your mirrorshades.  This is my final Retrochallenge 2015 07 entry, and it’s a doozy:  A tragedy of blunders and a triumph of late-night hacking.  Or something.

In our last exciting episode, I had filled-polygon cubes and icosahedrons spinning around in front of a static background.  Static backgrounds are boring.  So I set out to make the background scroll.  I figured it would be easy.

Mistake #1: Dual-Playfield Mode using ScrollVPort()

The tricky thing is that I wanted to scroll the background (the moon, the stars, and the pyramids) without moving the foreground (the polyhedrals).  Conveniently, the Amiga has a graphics mode specifically for this kind of thing called “Dual-Playfield Mode”.  The idea is that you split your bitplanes between two “Playfields” each of which can be independently scrolled in the X or Y direction.

This was pretty easy to set up.  I had to shift my bitplanes around a little, so that the 3D shapes were drawn in bitplanes 0 and 1, and the background in bitplane 0 of a separate RasInfo structure.  Since I was scrolling horizontally, I also doubled the width of the bitmaps from 320 to 640 pixels.  I pasted the same background image into this expanded space.  I figured that if I scrolled the background 320 pixels to the left, it would look just like the original image.  Then I could set the scroll back to 0 and start over again, for a fake infinite scroll.

It was easy, but the effect was kind of goofy.  The closer pyramids moved at the same speed as the pyramids on the horizon, and the moon, and the stars.  It definitely wasn’t the effect I was looking for.

Also, ScrollVPort() was kind of slow, and I couldn’t spare the speed.

Mistake #2: Copper Interrupts

It’s a good thing I had these on hand.

Lots of Amiga games feature “parallax scrolling” where objects closer to the viewer scroll at a different speed than objects in the background.  If those objects are separated vertically, they can be represented by the same bitplane.  The idea is that as the graphics chip outputs the final image, one scanline at a time, you can go in and change the register values in the middle to change how things are drawn.  It’s very much like “racing the beam” on an Atari 2600 or C64.

The Copper ought to make that sort of thing really easy, but I had a quandary.  The Copper can set a value in a register at a precise time, but in my case the value I’d need to write would change every frame.  I didn’t have a way to change the copper list easily because I was using the graphics.library functions to create the list dynamically and hand it off to the operating system using the (also pretty expensive) MrgCop() function.

They didn’t want it anymore. I promise.

In my reading, I had discovered that one of the things the Copper could do was trigger an interrupt by writing to the interrupt request register.  I figured I could have the Copper do that, and then my interrupt handler could set the registers with the correct, dynamically changing values to create a smooth scrolling effect.  It sounded like a good idea, and I spent most of Saturday night implementing it.

This was tricky for several reasons.  First of all, my interrupt handler needed to be written in 68000 assembly language, which I haven’t used since about 1991.  Luckily I still have some old books on the subject, and my code didn’t have to do anything too sophisticated.  The important bit where I changed the registers was just a few instructions:

    ; Set the address of the next byte to be read for bitplane 1
    move.l (_bytepos),($00DFF0e4)
    
    move.w (_bitpos),d0      ; load the number of bits to scroll
;   move.w d0,($00DFF180)    ; test setting background color
    move.w d0,($00DFF102)    ; set scroll position

At the hardware register level, scrolling is split into two operations.  You can shift the position where pixels are drawn by up to 16 pixels, which gives you the fine control.  To scroll further than that, you change the register that tells the video hardware which byte of data to read next.

It was the timing that made this approach a pain.  So far I’ve left most of the operating system running in the background, and because of that there was quite a bit of delay between when I asked for the interrupt and when my interrupt handler was called – almost an entire scanline worth of time, and it wasn’t consistent from frame to frame.  That was a problem because my timing requirements were pretty tight – I had to set the new bitplane address during the horizontal blanking time between one scanline and the next.

After messing around with different Copper lists and delay loops, I had a solution that seemed to work okay.  I’d divided the background image into three zones.  The top, with the moon and stars, was stationary.  The middle, with the pyramids on the horizon, scrolled at a rate of one pixel per frame.  The bottom, with the foreground pyramids, scrolled faster – two pixels per frame.

It was okay, but it wasn’t perfect.  Occasionally, maybe one frame in 60, the timing would be a little off and there would be a glitch – one of the sets of pyramids would be drawn in the wrong location.  But it was 4 AM, and all in all it looked pretty good.

As long as I was running in WinUAE…

Mistake #3: Wait until the last minute to test on real hardware

I haven’t had a lot of free time this Retrochallenge, and because of that I’ve been doing a lot of development, and all my video capture, in the WinUAE emulator.  WinUAE is very good, so I figured if my code worked there, it should work on the real thing.  Famous last words.

The saddest moment in retrocomputing is when a beloved piece of hardware starts to show its age.

The only problem is that my Amiga is no longer stock.  Back when I was working on the previous iteration of this project, I picked up an ACA500 accelerator, which provides a 14 MHz 68000 CPU.  I’ve been doing my testing on an emulated stock 7.14 MHz Amiga 500 configuration.  I figured for the real hardware test, I could pull out the ACA500 and replace it with my GVP A500 HD+, which provides a hard disk and RAM upgrade.

That was last night, when the first in a series of catastrophes struck.  The GVP has performed admirably for many years, but last night it wouldn’t boot.  It sometimes started to run the startup-sequence script, but would stop after a few seconds.  Worse, the steady drone of the motor started to sound… wobbly.  Not a good wobbly.  A bad wobbly.

Definitely not how this was supposed to look.

Eventually, I found an old Workbench 2.0 boot floppy, and I figured that would solve my problem – but I just traded one problem for something else.  I was able to run my test program on an Amiga running at the right clock speed, but that brittle timing structure I’d put together for the scroll routine just completely fell apart.  It was a mess.

Adding insult to injury, the Toshiba TV I was using as a monitor completely screwed up the colors, turning my twilight desert backdrop into a garish green-brown miasma.  I tried out a couple other monitors, as you can see in the video, but only that one had a problem.  I still don’t know why.

Solution: Going back to the beginning

So it was Monday evening, and I was just about out of time, and nothing was working.  So I drank some Coke, ate some chocolate, put on Hawkwind’s Live Chronicles album, and got to work.

I figured the chances of fixing my interrupt-driven timing were slim to none, so I went back to the start and considered the Copper list.  If you had a pointer to the actual memory location that the Copper was reading from, I figured you could poke new values into the instruction list.  Besides, self-modifying code was one of the few tricks I haven’t tried during this project.

The only problem is that I didn’t have that list.  I was still mostly using the Amiga’s graphics.library to handle my Views and Viewports.  In that paradigm, I created a fragment of a Copper list for the changes I wanted to run, and then called MrgCop().  MrgCop() would take all the Copper lists for all the visible Viewports and merge-sort them into a master list which it attached to the View structure and told the Copper to run every frame.

So I started by printing out that final Copper list and seeing what it looked like.  Here’s how it starts:

0x2b01,  0xfffe, // Wait for Y=42
0x0180,  0x031c, // start of color table
0x0182,  0x0c00,
0x0184,  0x00c0,
0x0186,  0x033c,
0x0188,  0x00c0,
0x018a,  0x033c,
0x018c,  0x0272,
0x018e,  0x0333, // end of color table
0x008e,  0x2c81, // diwstrt
0x0100,  0x3200, // bplcon0h
0x0104,  0x0024, // bplcon2h
0x0090,  0xf4c1, // diwstop
0x0092,  0x0038, // ddfstrt
0x0094,  0x00d8, // ddfstop
0x0102,  0x0000, // bplcon0l
0x0108,  0x0026, // bpl1mod
0x010a,  0x0026, // bpl2mod
0x00e0,  0x0000, // bitplane 0 address high word
0x00e2,  0x9810, // bitplane 0 address low word
0x00e4,  0x0000, // bitplane 1 address high word
0x00e6,  0xd690, // bitplane 1 address low word
0x00e8,  0x0002, // bitplane 2 address high word
0x00ea,  0x8340, // bitplane 2 address low word
0x01e4,  0x2000, // diwhigh
0x2c01,  0xfffe, /* start of my custom list */
0x0180,  0x042c,
...

Well, that doesn’t look too bad.  Most of those lines are just setting a video register (left column) to a particular value (right column).  I don’t know what half of those register names mean, but the ones I was most interested in were the bitplane address registers.  If I were to create my own Copper list, I’d need to fill in those values with whatever the actual pointers would be for a particular run of the program.

Once I had my list, I just jammed it into the View structure in place of the one that graphics.library had created for it.  This is a pretty graceless way to go about it, and I’m sure I’m leaking memory again, but the clock was ticking.

For my scrolling routine, I’d need to reset those registers during the hblank intervals between particular scanlines.  So I added in a few lines to do that:

...
// horizon transition
0x8ae3, 0xfffe, // wait for the end of line 138
0x00e4, 0x0000, // bitplane address high word [78]
0x00e6, 0x0000, // bitplane address low word
0x0102, 0x0000, // bplcon0 (scroll up to 16 pixels)
...
// foreground pyramids transition
0xb1e3, 0xfffe, // wait for the end of line 177
0x00e4, 0x0000, // bitplane address high word [146]
0x00e6, 0x0000, // bitplane address low word
0x0102, 0x0000, // bplcon0
...

Then I could just write a quick routine that my main program loop could call every frame to fill in new values for those lines of the Copper list:

void UpdateCopperList (struct MyScreen* s, UWORD* ptr1, UWORD scroll1, UWORD* ptr2, UWORD scroll2)
{
s->View->LOFCprList->start[79] = (UWORD)((ULONG)ptr1 >> 16);
s->View->LOFCprList->start[81] = (UWORD)((ULONG)ptr1 & 0x0000ffff);
s->View->LOFCprList->start[83] = scroll1;

s->View->LOFCprList->start[147] = (UWORD)((ULONG)ptr2 >> 16);
s->View->LOFCprList->start[149] = (UWORD)((ULONG)ptr2 & 0x0000ffff);
s->View->LOFCprList->start[151] = scroll2;
}

Did it work?  Yes!  And I’ve got to say, it’s way better than that ridiculous interrupt-driven approach I wasted my time on.  This scroll routine is rock-steady.

I tried it out on the real hardware and the results looked just like in the emulator.  That was an incredibly satisfying moment.

Success at last!

Finally, I crossed my fingers and tried the code out on the real Amiga with the ACA500 attached.  The scroll routine still worked!  The only difference was the frame rate, which was considerably improved by the 14 MHz 68000.

And that’s where I’m going to leave things for this summer’s Retrochallenge.  It sure looks a lot more impressive than the version I started with.  The performance is a lot better than it was, but still not up to snuff with what you’d see in the demoscene after, say, 1987.  I think next time I come back to this project we’ll be looking at a lot more assembly language and bare metal programming.  Which should be fun.

From Wireframe to Filled Polygons

I’d been putting off moving from wireframe rendering to filled polygons because I was worried about what was going to happen to my framerate, but now that I’ve finally bit the bullet it’s not nearly as big a deal as I thought it would be.  That’s another advantage of the Amiga’s Blitter: it does all the work, and I take all the credit.

As I understand it, here’s what happens when you use the graphics.library’s filled polygon routines:

1. The program calls AreaMove() to begin the polygon and give the location of the first vertex in screen coordinates.  It then calls AreaDraw() for each remaining vertex, and then AreaEnd() when it’s done.
2. The vertex coordinates are stored in a temporary buffer called AreaInfo attached to the screen’s RastPort.
3. The blitter is used to draw the outline of the polygon into a temporary buffer called TmpRas, also attached to the screen’s RastPort.
4. The rectangle containing the polygon is copied into one or more bitplanes of the screen buffer using a special fill mode.  For each row, the Blitter scans until it hits the outline, and then writes fill bits until it hits the outline on the other side of the polygon.  (The fill bits can be turned on and off multiple time per row, so that this can be used to fill in concave polygons).

The Blitter is very flexible and can perform a variety of logical operations on its inputs, apply mask inputs, and so on.  I’ve really only scratched the surface.  In this case, it’s figuring out how to fill in an arbitrary polygon for the price of copying a rectangle between two bitplanes, which is a pretty good deal.

Once I’d replaced my wireframe cube with a solid version, I started playing with the graphics again.  I used some tricks with the palette to make the cube look partially transparent.  I’m using three bitplanes now, with the different-colored sides of the cube drawn in bitplanes 0 and 2, and the background elements drawn in plane 1.  The palette looks like this:

Color #      Description
0            Background land and sky
1            Red surfaces of cube
2            Background details (pyramids, moon, stars)
3            Background details behind red side
4            Green surface of cube
5            Blue surface of cube
6            Background details behind green side
7            Background details behind blue side

If I want the cube to appear solid, I just need to make color 1 the same as 3, 4 the same as 6, and 5 the same as 7.  Make any pair different shades, and the background will “show through”.

I also used the copper to change the actual color values at various positions, so that the cube colors are pale when it’s in front of the moon and darker when it’s in front of the pyramid, and so that the ground color seen through the cube fades the same way it does without the cube in the way.  It’s a fake, and doesn’t entirely make sense because the rear faces of the cube aren’t drawn, but it’s still pretty convincing looking.

I also decided that I was tired of seeing that cube spinning in one place, so I played with its animation a bit.  I’ve now got it orbiting around the origin, coming closer to and then farther away from the camera.

Finally, I decided to add another shape back in.  I’ve got to wrap this project up in a couple days because I’m leaving for Gen Con on Wednesday, so in honor of that I added an icosahedron – the iconic shape of a twenty-sided die.

The icosahedron puts a lot more load on the CPU than the cube does: 20 faces versus 6, 12 vertices versus 8.  It cuts my framerate in half, as you can tell from the video.  I’m getting 20+ fps from the cube, and just over 10 fps when the icosahedron is onscreen.

Drawing the Line

Implementing a line-drawing algorithm isn’t that hard, but no nontrivial piece of code works right on the first try. Or the second.

Over the last few days I’ve let my progress on this project run ahead of my documentation, so let’s try to catch up.  Tonight, I’d like to briefly discuss how to draw lines – and why you might not have to care.

So far, my approach has been to not care – I’m using the AmigaOS graphics.library functions Move() and Draw() to render the actual lines of my shapes.  There’s a good reason for that: I’m lazy.  Besides, graphics.library is probably well-optimized, and it can take advantage of some of that snazzy Amiga custom hardware.

The Blitter, like the Copper I talked about last time, is one of the Amiga’s graphics coprocessors, and it’s part of the Fat Agnus chip.  Basically, a blitter just moves data from one part of memory to another.  It’s good for copying stuff into a bitmap, or moving an image around.  The Amiga’s Blitter also has some special functions – it can draw lines into bitmap memory directly, and even draw filled polygons (we’ll get to that in another entry).

On the stock Amiga, the Blitter can do all this much more quickly than the CPU can.  For one thing, it doesn’t have to keep fetching instructions to run – you just set up its registers and let it go, and it’ll move data around as quickly as possible.

Additionally, blits can take place asynchronously while the CPU is doing something else.  It’s not exactly multiprocessing, but it’s definitely an advantage.  The graphics.library functions don’t give me complete control over when to wait for the Blitter and when not to, but for example I can use the Blitter to clear the framebuffer while the CPU is computing the transformation matrices to use while drawing the next frame.

The take-home here is that the graphics.library functions for drawing lines are easy to use, fast, and actually work.  You might do better if you’re writing your own assembly routines that set up the Blitter directly, but I’m not getting into that at this stage.

However, I was kind of interested in writing my own line-drawing routine, just to see how a software solution compared speed-wise.  The best known algorithm for drawing lines (at least, for drawing lines without antialiasing) is Bresenham’s algorithm.  In this algorithm, you iterate from the start of the line to the end of the line in the positive-x direction, drawing a pixel at each x coordinate and using a magic “error” value to figure out when to increment the y coordinate.  For “steep” lines, you can do the same basic thing, but swap the roles of x and y.  An important part of the algorithm’s performance is that its main loop only uses integer addition and subtraction.

(Okay, the error value isn’t actually magic – it increments by Δx and decrements by Δy to basically count out the slope of the line – but it is pretty clever.  You can read the details over at Wikipedia.)

My first attempt at implementing a line-drawing algorithm was so slow that I didn’t even want to measure it, and for good reason.  Calculating the x and y coordinates was fast enough, but figuring out which bit of memory to change to plot those values took way too much time – and it required an expensive integer division.  The solution was to figure out the memory location for the first point in the line – which byte of the bitplane, and which bit of that byte – and then incrementally change those values as I drew the line.  So if the first pixel was at bit 1 of byte 0x0000ccc5, the pixel to its right was bit 0, and one to the right of that was bit 7 of byte 0x0000ccc6.  Going down or up meant adding or subtracting the number of bytes in one row of the bitmap.

Once I did that, I was back to using integer addition and subtraction for all the operations.  There were, of course, a few glitches along the way – you can see a couple of them at the top of this post.  One thing that messes with my head is that bytes are arranged from left to right in each row of the bitmap, but the bits of each byte run from right to left.  That right-hand picture shows me getting things backwards.

So how fast did my heavily-optimized software line drawing routine go?  I am pleased to report that it took about 2.75 times as long as the Blitter to do the same amount of work.  It was a fun exercise, but I’ve reverted back to using the graphics.library routines for real work – and we’ll get into more of that tomorrow.

RetroChallenge Winter Warmup Video

After having a few technical problems (aka running out of space on my iPhone) I was finally able to create a video of my RetroChallenge code running on my actual Amiga 500.  Just for fun, I added a couple more shapes than just the cube, and switch between them during the program.  The most CPU-intensive is the octagonal solid, which requires transforming 16 points and drawing 24 edges each frame.