Enhanced mode 1 pictures

[paulb]

I just use a Floyd someone dither where the difference between the current pixel colour channels and what I will display is spread over the pixel to the right and the three pixels below on the next row.

The parrot taught me to spread the error from one row to the next, which is obvious in hindsight, but this makes all the difference. I also added spreading the error to the right, which was actually what I tried some time ago, and together with propagation to the next row this seems to make a more pleasing dithering pattern:

To pick which colours to use, I pick the combination with the least sum of differences squared for each channel (rgb).

I calculate the sum of each colour's contributions, identifying the most significant colours. However, if there are pixels for which the given selection of colours cannot usefully contribute, the next most significant colours are tried. Here, I'm picking four colours freely to work with davidb's code.

As I can only change two colours, I do a lookahead to make sure I don't back myself into a corner with the colours, but I have at least one bug when I look more than two rows ahead. What it also needs is a way to ignore day nearly black and not put a white pixel every twenty to get the correct overall brightness, but as I guess Francis has already tried these things, i'm hoping that he will add support for this type of encoding to his excellent image converter.

I haven't looked at his converter, but I imagine that it shouldn't be too difficult for him. My own code is available in a repository.

[davidb]

I've updated the code to try and figure out how long to wait before starting to write to the palette registers instead of hard-coding a value and checking for that. There may be situations where it doesn't figure it out, and you'll get a jittery display.

I've attached a new picture disk as well, containing images that have been processed using paulb's script.

As usual, here are some screenshots from Elkulator:

[paulb]

It's amusing to see how our expectations have increased, from hoping that we might manage to make use of more than four colours in an image...



...to being able to represent that image quite accurately:



Here's the original (courtesy of some unknown street artist):

[paulb]

Can't wait to see a MODE 0 picture in colour.

As tricky pointed out, that's a tricky one! But with reasonable expectations, it might be possible to get some usable output:



The above image would be equivalent to a MODE 4 version (which we aren't doing for various reasons, in fact), and the MODE 0 version would provide twice the horizontal resolution, of course. Unfortunately, 3 colours seems to be about as low as you can generally go with decent-enough results. Here's the 4-colour version for comparison:



Even with such favourable examples, the loss of colour information is greater than any resolution gain. But specially-prepared images would, of course, do much better.

[davidb]

I've been playing with mode 0 a bit (too much) and have found some ways to exploit palette changes, even with only 2 colours to play with. I don't think I have a promising career ahead of me designing heavy metal album covers, but you never know.

[tricky]

Very colourful; on the beeb, there would only be time for one colour change per line. One day, I will code up a partial palette programming encoder, but it is quite a way down the todo list.
EDIT: but one colour pure line is enough for your image except the line immediately below the word THIS!

[davidb]

Very colourful; on the beeb, there would only be time for one colour change per line. One day, I will code up a partial palette programming encoder, but it is quite a way down the todo list.
EDIT: but one colour pure line is enough for your image except the line immediately below the word THIS!

I would have thought it would have been easier to do full palette changes in mode 0 than in mode 1 given that there are only two colours to change, or is there more to it than that? Could you recover more time per scanline by switching to a 256x256 mode 1 or 512x256 mode 0?

In any case, I kind of feel like my palette experiments have been distracting you from your Frogger port.

[sbadger]

I'd seen the mode change on scanline (a la Elite) but never come across this colour trick.
Did any games every make use of it?

[davidb]

I'd seen the mode change on scanline (a la Elite) but never come across this colour trick.
Did any games every make use of it?

A few used one or two palette changes per frame to hide data in screen memory or to use different colours in different regions of the screen. See the Electron Games that use Palette or Mode switching thread for details of some of these.

[davidb]

OK, I think I've done enough on mode 0 for now. I'll finish for the time being with this image, courtesy of Elkulator.

[hexwab]

Changing both colours takes 46 cycles, but a bit less from first register write to last.
There are 128 cycles per scanline, with 80 of them visible, leaving 48 cycles to change the palette and allow for which of the 7 cycles in the BEQ+BIT the vsync starts. As I haven't seen any flicker, I either have my maths wrong, or don't use the changed colour in the first/last byte!

This can be easily reduced to 44 cycles by calculating one of the EORs ahead of time and storing the result in X. This gives a first-write-to-last-write time of 41 cycles, which allows 7 cycles of jitter. More than enough!

But stepping back a bit: I have reason to believe cycle-exact synchronization is possible. I'm not aware of it having been done on the Beeb, but it's been done on other 6502-based systems, notably the C64 (magic phrase: "stable raster"). While I have no code (yet?), let's see what it would buy us if it could be achieved.

With precise timing palette writes could happen anywhere, not just between lines. We have 256 lines * 128 cycles = 32768 cycles for the displayed part of the frame, plus the vblank interval. Assume that during vblank we can rewrite the entire palette plus A,X,Y. Assume also that memory is no object. Then code like

Code: Select all

LDA #xx
STA FE21

writes an arbitrary palette value in 6 cycles[1]. We can shave off 2*3=6 cycles due to not needing to load the 3 values already set up in A,X,Y. So this gets us roughly (32768+6)/6~=5462 palette writes per frame, or about 21.3 per line. This is much better than the 8 required to change two colours per line!

There's also the flash bit, which for the same price as a palette write can invert the RGB values of an arbitrarily-chosen subset of the entire palette. We want to write D8 or D9 to the control register (FE20). But since we don't really care about the top 3 bits, which adjust the cursor, there are 8 possibilities for each choice of the flash bit: {1,3,5,7,9,B,D,F}{8,9}. When writing to the palette register these correspond to setting any logical colour to either phyical colour 14 or 15. Conveniently these are flashing colours themselves, so black, white, red and cyan are potentially cheaper to use than other colours due to the possibility of storing the same value into both the control and the palette register, saving two cycles.

How much space would this take? "LDA #xx: STA FE21" is 5 bytes. 5462 copies is about 27K. Obviously this wouldn't fit on a model B with 20K also used for screen memory. Conceivably it might fit on a B with sideways RAM, but the non-contiguous nature of the code (we have 0000-3000 free, then 8000-C000) would complicate matters. With shadow screen the code would easily fit in RAM. On a Master we'd also have use of STZ for additional cycle savings.

Even targeting a memory-limited model B, clearly two colour changes per line is barely scratching the surface of what's possible. There's a lot of potential for optimization here!

Tom.

[1] I'm reasonably sure there's no cycle stretching and writes to the video ULA run at 2MHz.

[tricky]

That all sounds good, I has thought about the mid line changes, but was waiting for an encoder which would handle partial palette programming as changing mid line would mean s supporting partially programmed palettes for 40+pixel stretches. I had also thought of the flash bit, but thought that it would be so rarely useful that I hadn't bothered, but might give you something near the end of a line where you could tidy up off screen.
I thing you can lock to the v sync by counting cycles between vsyncs in a loop that is one cycle took too long/shot and stopping when the count changes.
You could also move the screen lower down to give contiguous memory into SWRAM.
Keep the ideas coming.

[sbadger]

Can't wait to see a MODE 0 picture in colour.

As tricky pointed out, that's a tricky one! But with reasonable expectations, it might be possible to get some usable output:



The above image would be equivalent to a MODE 4 version (which we aren't doing for various reasons, in fact), and the MODE 0 version would provide twice the horizontal resolution, of course. Unfortunately, 3 colours seems to be about as low as you can generally go with decent-enough results. Here's the 4-colour version for comparison:



Even with such favourable examples, the loss of colour information is greater than any resolution gain. But specially-prepared images would, of course, do much better.

is it a coincidence that youre trying the elixir image?, i think elixir is a game that could have really benefited from this technique.

[paulb]

is it a coincidence that youre trying the elixir image?, i think elixir is a game that could have really benefited from this technique.

It is a coincidence, but it does appear that some of the cover artwork may have been done in such a way that lends itself to "recolouring", maybe because it could have been drawn that way to begin with. For instance:





With a bit of tidying up, you could get quite "clean" images that might convert even better. I just used the cover images from STH, and they are fairly low resolution and are, of course, subject to the usual colour and noise issues you get when scanning things.

[paulb]

Out of interest, I wrote something up recently that touches upon the image optimisation work I did for this effort, even though the motivation for writing the article was to document the use of a particular piece of software and its role in optimising the performance of the tool I made. I hope someone finds it vaguely interesting, at least.

[puppeh]

I've read the whole thread and I still can't figure out if you guys are using the same technique I used in "Some Nasty Effects" .

FWIW my technique (partial palette programming + a theorem prover to figure out which byte values/palette entries to use) allows more than four colours per MODE 1 line, but I could only change (IIRC) 9 palette entries in the hblank period, and only every two rows (from a timer1 interrupt).

My conversion code's at https://github.com/crtc-demos/some-nast ... /palsearch btw. (You need OCaml & Z3.) It's kinda slow: probably better maths could make it faster...

[davidb]

I only did the palette programming, not the image conversion, so I can only write about that.

We use the property of the Electron's CPU/ULA memory contention to block when the ULA is transferring memory for a scanline, effectively synchronising the execution of the palette programming code to the start of each scanline. We're running from ROM, so we execute a few instructions to wait until we're fairly sure that the ULA is accessing the memory then we try to access memory, causing the CPU to block. When the CPU continues we want to be sure to have enough time to change the palette, but not too much that we try to block again before the ULA has priority.

Because the MODE 1 palette can be reprogrammed with two writes on the Electron, we have enough time to allow four unique colours per scanline. In theory, if we loaded a couple of values into A and X, say, and a counter value into Y, we could also change the palette part way across the screen, but that would involve careful timing and I'm not too good at that.

[puppeh]

I hadn't realised the Electron palette was handled so differently to the BBCs, to be honest! Interesting.

[puppeh]

Here's a testcard (not quite the same one) from my converter for comparison:



The 2x2 ordered dither is chosen quite deliberately: that leads to input that's fairly well-conditioned for input to the search algorithm. Then one of two strategies is used to search for an optimum palette to represent that set of bytes, for each group of two rows in turn. Firstly:

• Each byte in the double row is sorted by frequency, with the most frequent first. A binary search is then used to find a palette that allows the greatest number of bytes to be displayed exactly, from the start to some cut-off point. Slightly counterintuitively, since we're programming the palette partially and specialising it to display some byte values only, this means we can display >4 colours per row.
• Often the trailing end of this list won't match perfectly, so a "best effort" is made to match a byte with the closest colours possible in the palette that has been found (e.g. white pixels might be substituted for yellow, or vice versa).

If the overall error from this process is greater than some threshold, then a secondary algorithm is used to try to improve the result:

• Many particular shades (e.g. mid-grey) can be made by dithering different colour pixels in a 2x2 block together (e.g. white/black/black/white or green/magenta/magenta/green). This offers an opportunity to relax the constraints around the palette that we find, since each dither pattern can be made in more than one way, and all will look reasonably similar.
• We try to match all these variations of all the bytes in the list at once with a gradually-increasing "nastiness" factor, corresponding to the difference in intensity between the pixels making up the dither pattern (i.e. "softer" dithers are preferred, because those arguably look better and are the ones used by the first phase).
• If this succeeds (which is not guaranteed!), we use the pattern it finds, else we fall back to the result from the first phase again.

An additional wrinkle is the inability to change more than 9 palette entries per double row: this is just fed into the theorem solver as an additional set of constraints. That means the conversion must be done serially (aw!), which is a shame because it takes several hours to process each image!

[kieranhj]

I've read the whole thread and I still can't figure out if you guys are using the same technique I used in "Some Nasty Effects" .

FWIW my technique (partial palette programming + a theorem prover to figure out which byte values/palette entries to use) allows more than four colours per MODE 1 line, but I could only change (IIRC) 9 palette entries in the hblank period, and only every two rows (from a timer1 interrupt).

My conversion code's at https://github.com/crtc-demos/some-nast ... /palsearch btw. (You need OCaml & Z3.) It's kinda slow: probably better maths could make it faster...

Hey Jules. Funny you should bring this topic up again. I just tried this week to get your palette search built and running in Cygwin64 + OCAML + Z3 but sadly failed. I eventually got it built but get a runtime error at initialisation.

The theorem prover is way over my head but very cool that you have applied this to the Beeb palette problem. None of the solutions presented here use partial palette AFAIK, just calculating best 4x colours per scanline in MODE 1 and then changing max 2x full colours (so 4x palette entries) during H-blank.

I wanted to use your algorithm to generate colour pictures in MODE 0, what do you reckon?

PS. Every good idea I have for Beeb demos I find you've already done it years ago.

[puppeh]

Here's Yoda:



Not so great around his mouth I think, but generally OK!

[puppeh]

You could maybe do MODE 0, "Mode Infinity" did, sort of. That exact way gets you lots of colours in a kind of "1x128" mode with partial palette programming and a well-chosen dither pattern on the screen (worked out manually, that time). But 1x128 isn't much use for images.

The problem (I think) is about degrees of freedom for each of the colours within a byte: the way the bytes are shifted out whilst being rendered (the taps at bits 7, 5, 3, 1) in MODE 1 mean that (I'll try to get this right, it's been a while) the first two pixels shifted out can use any of 16 palette entries, and the next two can use any of 8 palette entries, then we stop there. In MODE 0, we keep going for another four pixels, meaning the last two can only select their colour from two different palette entries.

Right, I definitely messed up that explanation. But I think it means you'll get "stripes" on the screen (because of those last two bits shifted out) unless you're spectacularly careful!

[puppeh]

The four stanzas at the top of https://github.com/crtc-demos/mode-infi ... tterns.txt are, I think, the four byte patterns used (four horizontal rows, repeating down the whole screen) in Mode Infinity -- I'd have to stare a bit more to figure out how they worked again!

[paulb]

None of the solutions presented here use partial palette AFAIK, just calculating best 4x colours per scanline in MODE 1 and then changing max 2x full colours (so 4x palette entries) during H-blank.

For the record, the Electron palette switching changes all 4 colours per scanline (if necessary).

As for the palette computations, the algorithm I use is fairly straightforward. From memory and looking at it recently:

Code: Select all

for each row:

    # Compute the colour distribution.

    for each pixel:
        obtain the contributions of the standard eight colours
    sum the contributions for the row
    
    # Determine the best choice of colours for the row.

    for each combination of four colours (in order of decreasing suitability):
        for each pixel:
            allocate one of the four colours for the pixel
            determine the error (the difference between the allocated colour and the original colour)
        sum the errors for the row

    choose the combination with the least error sum
    (or, for speed, choose the first combination that could allocate colours for every pixel)

    # Update the image and distribute errors to adjacent pixels.

    for each pixel:
        allocate one of the four colours and update the image
        distribute some of the error to the next horizontal and vertical pixels

Looking at it again, I see the potential for more optimisation and documentation.

[kieranhj]

For the record, the Electron palette switching changes all 4 colours per scanline (if necessary).

Oops, sorry. This thread does have Beeb & Electron stuff liberally & confusingly intermingled!

[tricky]

For the beeb, I don't partially program the palette, so only need to write 8 entries allowing two colours to be replaced per scan line.
I didn't go with T1 for this, but just cycle count with interrupts disabled.
If a faster encoding method could be worked out, partial palette programming could be done throughout the whole frame with cycle counting and still have time at the end for some sound.
I have found that some beebs have twinkling colours when there palette is partially programmed, this actually benefits the stars in my phoenix WiP.

[pixelblip]

Do you think it's feasible to paint with all these extra colours in a paint package.....I doubt it as I am sure it is mustering all it has.........it would be amazing if you could .....

They look so good .......people really pushing the Beeb and Elk.......

[tricky]

I think the closest you could come would be something like a split mode 2/mode 1 screen where the mode 2 bit was zoomed in to 2x and the output was displayed in the top or bottom half, as changing any pixel could change the colours on the rest of the row (or even several rows on the beeb).

EDIT, actually the encoding would not be feasible on a beeb, even using a 100+ KHz co-pro; even encoding on a desktop is not a real time thing.

You could display the possible patterns for a given byte and pick from them, but it wouldn't really be an art package.
You could also pick the palette for each row and then draw with a colour that only drew on lines with that colour in their palette.

[davidb]

I wrote a desktop (not 6502) tool to play around with MODE 0 images, giving each character line (8 scanlines) its own two colours. The idea was to see if anything interesting and colourful could be created for a game in that mode. Something similar could be done for MODE 1.

[SteveF]

BITD I used to have a green screen monitor on my BBC, and one of the few advantages thereof was that you could use mode 2 to display images in 8 different levels of greyscale; I seem to remember a few PD discs or similar which had suitable digitised images on.

I wondered if the techniques used here to give 8 colours in mode 1 would be helpful in giving a high-res greyscale display, such as you'd see if you had your Electron plugged into a monochrome monitor or turned the colour down on the TV. Here's my attempt at the parrot; I took the original image, dithered it down to 8 greyscales in gimp (I suspect this might be improved slightly if it was told to use a custom palette) and then used a hacked version of make_picture.py which picks the Electron RGB colour closest to the desired greyscale. I've attached my make_picture.py in case anyone wants to take a look at it.

Here's the version you'd see if you were rich enough to have a colour monitor:

And here's what you'd see with a monochrome monitor:

(I couldn't see a "simulate monochrome monitor" option in Elkulator, so I took the screenshot and turned it into greyscale using gimp.)

I have a suspicion it's not really taking full advantage of the 8 colours; telling gimp exactly which 8 shades of grey are available via a custom palette might help.