Techniques for dynamic (algorithmic) graphics

Question

I'm programming an application for a 32 bit processor with limited memory (512k flash, 32k RAM).

The display on this device is 128x160 with 16 bit color, which would normally consume 40k ram if I were to buffer it on my processor. I don't have that much RAM, so I'm looking for techniques, tips, tricks, ideas for generating screen data on the fly.

Things that might help:

• Perhaps you know of a resource for this sort of limitation
• Maybe you've generated attractive graphics on the fly
• Is there a generic algorithm I might use to combine elements in program memory (including alpha blending) on the fly while I scan the display
• Simple vector rendering techniques (or free (bsd/mit/apache) source)
• ???

I do have a multiplier, but no floating point processor. The display itself has a very simple controller and memory for the display - but reads and writes are expensive so I don't want to use that as my workspace if I can avoid it.

Answer 1

In a way, you are in pretty much the same situation game developers where at the time of the Tandys, Spectrums and early PCs. So, here's my recommendation:

You should read Michael Abrash writings on computer graphics. They were written in a time where a floating point co-processor was an optional piece of hardware, and they describe a lot of the basic techniques (Bresenham lines, etc.) used in the old (supposedly 'bad') software-rendered days.

You can read most of his "Black Book" here.

Additionaly, you can probably find a lot of the old BBS files that most people used back in the day to learn graphics programming here. Just search for Graphics, Lines, and what not.

Hope that helps!

Update: I also recall using this in my first attempts at drawing things on the screen. Can't tell how much time I spent trying to understand the maths behind it (well, to be fair I was like 15 at the time). Very good (and simple) introduction to 3D, and a very nice premier on transformations, polygon-fillers and interpolation.

Answer 2

What kind of data will you show on the screen?

If it is not photographic images, you could consider using a palette. For instance: A 256 color palette using 8 bits per pixel would require 20kb, (plus 256 x 2bytes for the lookup table) which at least is better than 40kb.

Answer 3

I believe the basic technique for dealing with this kind of situation is to divide the screen into narrow horizontal stripes, and only buffer two such stripes in RAM. One stripe will be displayed, while you render the next one down. When the scanning 'beam' hits the next stripe (and fires off an interrupt for you to catch), you swap the two and start drawing the next stripe down.

A nasty side-effect of this is that that you have hard timing limits on how long you can spend on rendering each stripe. So I guess it would be tempting to stick with something boring but with predictable performance, like sprites.

Slightly offtopic but this is how the Nintendo DS 3D hardware works. You can see it if you try to render too many polygons around the same y-coordinate - polys will randomly flicker and drop out as the screen-refresh overtakes the rendering hardware.

Also, I'd second the other poster's suggestion that you use palettised rendering. It's very hard to do fast maths on 16bit pixels, but faster in 8bit if you're clever about how you lay out your palette.

Answer 4

Some ideas that would combine nice graphics and low memory:

• Store backgrounds and sprites in flash.
• Store dynamically generated graphics in RAM using a palette to half the bytes.
• Use the windowing feature of the LCD driver to only update the part of the screen you need to.