# How can I make a graphics demo without a frame buffer?

I am programming a microcontroller - a tiny 8 bit computer that has about 100Mhz - 300Mhz CPU clock speed and 64K application RAM (actually ROM), but only a tiny amount of RAM (6K) - nowhere near enough for a graphics frame buffer.

So, I want to display an animated graphics demo on this machine. It seems to have enough computing power to calculate animated graphics of some sort.

To get animated graphics to display, I will somehow need to have a computer program that each time it is called, returns a single line of pixels of one image frame, which is then displayed. The display controller program continues to do this, calling line after line until it has displayed a whole frame, then it starts at the top again for the next frame.

Just to be clear, I'm not asking about the program that controls the display. I'm asking about the demo program. I need a demo program that yields its graphics one line at a time, which my display controller will then throw onto the screen.

I'm trying to imagine what sort of graphics program could work this way? Presumably the display of some sort of mathematical formula.

Can anyone suggest techniques for graphics programming that work in this way, in which a function can be called, which calculates and returns a line of the frame, only when requested to do so? Are there existing programs that work like this that I could examine?

I hope the question makes sense. Any pointers in the right direction or hints would be appreciated.

• github.com/ssloy/tinyrenderer/wiki/Lesson-0-getting-started - I guess that you're looking for something like this i.e. creating your own rasterizer. I wasn't working much with microcontrollers, so I limited my code to simple shapes and touch input. But based on that, I assume, that there is already library which allows you to send data pixel by pixel (or line by line as you said). – DirectX_Programmer Aug 18 at 15:10
• @DirectX_Programmer: Triangle rasterizers, by their nature, require a framebuffer. This question is specifically about drawing stuff without a framebuffer. – Nicol Bolas Aug 18 at 15:13
• @NicolBolas You're probably right, I have never researched that subject. But how should we define framebuffer? If he's storing data in 64K application ROM and load only part of data to compute in RAM, store result, unload RAM, load next part of data and so on - can we call it framebuffer then? In a sense, it meet contraints that OP asked for. Or do I have a wrong idea? – DirectX_Programmer Aug 18 at 15:29
• @DirectX_Programmer: I think the OP makes it clear what they mean by "framebuffer". Namely, the entire screen stored in memory as pixel data. – Nicol Bolas Aug 18 at 15:31

This is a case where looking at the workings of more retro hardware would be reasonable. Older hardware had strong limitations in both memory and processing power. Your 100+Mhz chip is far faster than most consumer-grade chips of the 80s and before. So while those CPUs needed dedicated graphics chips to be able to render, your much faster CPU can probably handle the task adequately.

I would suggest starting with something like the NES's tilemap-and-sprite architecture. These architectures are designed to be both memory efficient (getting a lot out of limited storage space) and computationally efficient in a line-by-line output, as they generated pixel data and sent it directly to the display device at the expected speed of a CRT.

The broad idea is this. A tilemap consists of two parts: a series of tiles and a 2D array of indices into the tile map that represents the image being created. The tiles are typically 8x8, and on the NES were 2-bits-per-pixel and the tiles used palettes. Or more specifically, the index into the tile map includes not just the index of a tile but also the index of the palette to use with that tile. So a tile is not inherently associated with a palette; the association is made at the point of use (technically, on the NES, the tile map and palette map were separate, as each 2x2 block of tiles all had to use the same palette).

To allow for scrolling, the tile map is bigger than the visible screen, and there is an offset that represents where the top-left corner of the visible screen is within the tilemap. Let this offset be at position Xoff and Yoff.

You can see how this makes row-by-row processing trivial. To generate a horizontal row for the horizontal position Ypos (in screen-space), you need to get the starting pixel within the tilemap. That requires transforming the XY position (0, Ypos) from screen-space to tilemap space. So you add to it the vector (Xoff, Yoff), hielding the vector Xoff, Yoff + Ypos).

Note that when doing any mapping from screen-space to tilemap space, that the tilemap space should wrap around in both the X and Y axes. So whenever you compute a new pixel in tilemap space, you have to wrap it around the size of the tilemap space.

Now, we need to break down this tilemap pixel into two 2D components: the tile index within the tilemap that gives us this this pixel, and the pixel within that tile that we need to fetch for this pixel. The tile index is just the tilemap-space pixel integer-divided by the tile size. The pixel coordinate is the tilemap-space pixel integer-modded by the tile size. Given an 8x8 tile size, you're doing this:

ivec2 tilemap_pixel = ...; //Compute the tilemap starting pixel as above.
ivec2 tilemap_tile = ivec2(tilemap_pixel.x & ~0x7, tilemap_pixel.y & ~0x7); //Mask off the lower 3 bits.
ivec2 pixel_in_tile = ivec2(tilemap_pixel.x & 0x7, tilemap_pixel.y & 0x7); //Mask off all but the lower 3 bits.


So given tilemap_tile, we now have the index of the tile we are currently working within. And pixel_in_tile gives us the pixel we're working in. So we can fetch that pixel, whose value can be mapped into a palette to produce the final color for that pixel. Or we can use it directly.

To get the next pixel is pretty trivial. We just increment pixel_in_tile.x by 1, modulo the tile size. If the increment exceeded the tile size, then we also increment tilemap_tile.x` by 1, modulo the tilemap size. And you keep going until you've filled out the row of pixels.

There are many opportunities for performance optimization of such an algorithm.

The tiles probably represent the largest data. A 128 element tile set of 8x8 tiles, even at 2bpp, is 2K. But the thing is, those can be stored in ROM, since you're probably not changing the tiles themselves. The size of the tile map (assuming it must be in RAM) depends on the desired output resolution and the tile size. A tile map for 8x8 tiles that can cover a 320x240 screen is 1,200 bytes. Not exactly tiny. You'll need to take up more memory if you want room for smooth scrolling (and thus a larger tile map).

That being said, it's also important to note that the "output size" doesn't have to be the actual size of the display device. For example, if you intend to draw to a 1080p display device, you could still render to an internal resolution that's, for example, 8 times smaller, 240x135. It's easy to modify this algorithm to essentially generate the same pixel value 8 times in a row, as well as reusing the same line 8 times per 1080p line. Indeed, it wouldn't be too difficult to have this algorithm allow for subpixel scrolling (scrolling in 1080p space, not 135p space) and even adding some filtering between pixel values. A 240x135 "output size" tilemap would only require 510 bytes for the visible region, so you would have more room for a larger scrolling area.

• This hits the mark thanks, very interesting information. – Duke Dougal Aug 18 at 22:55