Author Topic: School of Grayscale  (Read 4886 times)

0 Members and 1 Guest are viewing this topic.

Offline Runer112

  • Moderator
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2289
  • Rating: +639/-31
    • View Profile
School of Grayscale
« on: August 24, 2015, 04:59:21 pm »
Reserved for future use.

Offline Runer112

  • Moderator
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2289
  • Rating: +639/-31
    • View Profile
Re: School of Grayscale
« Reply #1 on: August 24, 2015, 04:59:30 pm »
History of Grayscale

Since the dawn of a long time ago, man has tried to use technology to make cool stuff. In the TI graphing calculator programming community, that often means making games to play in math class (note: not actually recommended to do this!). For instance, let's briefly look at the top 83+/84+ programs from 2004, as rated by ticalc.org's 2004 POTY (program of the year).

First place went to Acelgoyobis, the first (and as far as I know, the only good) pinball game created for the platform. The reviews rave about the crispness and fluidity of the graphics and spectacular physics, making it feel very nearly like a real pinball table, minus the quarters.


Acelgoyobis

Looking at the graphics, they do indeed look quite crisp. But it's clear that sacrifices had to be made to work with the very limited graphical hardware of the calculator: a monochrome 96x64 screen. The lack of any shades other than black or white and the tiny resolution are quite restrictive. But what if these restrictions could be lifted, at least partially?

The resolution restriction is pretty hard and fast. But the fourth place program from the previous year's POTY push backs against the color restriction. The highest-placing non-game, the Grayscale Programming Package provides code to simulate four-level grayscale with the monochrome screen by rapidly flashing pixels between black and white to simulate a shade of gray. ticalc.org's news article states that "the demos cast aside any flickers of doubt regarding the viability of grayscale on the 83+." But do they, really?

Returning back to the 2004 POTY, second place went to Desolate, an adventure RPG with a great story and, largely thanks in part to the Grayscale Programming Package, revolutionary graphics for the platform.


Desolate

Looks quite flickerless!... But this was recorded using an emulator, and while an emulator can easily accurately emulate a digital process, it's much harder to accurately emulate a physical process like LCD updates, which rely on the action of the liquid crystal molecules that liquid crystal displays depend on. And in this case, the emulator is pretty far off from the real result. Here's a sample of what the game looks like when run on a much newer and more accurate (but still not perfect) emulator.


A more accurate emulation of Desolate

The next novel development to show up in a popular game showed up in Chip's Challenge, a recreation of a classic puzzle game and the second place winner of the 2009 POTY. The Grayscale Programming Package and all the games that used it dobuled the amount of available shades, from 2 to 4. So... let's double it again, to 8!


A reasonably accurate emulation of Chip's Challenge

Once again, a rolling flickering effect is visible. It turns out there are a number of obstacles in the way of fighting this flickering effect and achieving flickerless grayscale, and it has taken many years since the appearance of the first popular grayscale package/games to finally start ironing them out. I would like to take all of the currently available knowledge, and some of my own developments, to fully establish the extent to which these obstacles can be overcome.

Offline Runer112

  • Moderator
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2289
  • Rating: +639/-31
    • View Profile
Re: School of Grayscale
« Reply #2 on: August 24, 2015, 04:59:36 pm »
Grayscale 101

Disclaimer: The update artifacts depicted on my emulator may be fairly different from those on a real calculator, but the concepts of what causes them and how to correct them are roughly the same.

As previously mentioned, grayscale can be simulated on a monochrome screen by rapidly flashing pixels between black and white to simulate a shade of gray. But that's a terribly vague description, and not at all one that you could devise any reasonable grayscale display algorithm from. So let's go into more detail about what makes up an average grayscale display algorithm. For simplicity's sake, we'll consider the simplest depth of grayscale: 3-level grayscale. That means there are only 3 shades available: white, gray (50%), and black.

Obviously, to display a white or black pixel, you simply... display a white or black pixel. So let's focus on the interesting part: gray. As the "gray (50%)" name may suggest, this shade should be 50% black and 50% white. But since you can't actually make a pixel 50% black and 50% white at the same time, let's make it 50% black and 50% white over a period of time. The simplest way to do this is to make a pixel black for one unit of time, then white for one unit of time, and repeat.

But what's a good unit of time? Let's see what happens if we alternate the whole screen between black and white for different units of time.

Spoiler For Strobing gray:
2Hz
4Hz
8Hz
16Hz
32Hz
64Hz

So it started off pretty blatantly altering between black and white, but eventually got up to looking like a somewhat flickery gray that's got strange artifacts in it. For now, let's see what we can do to improve the gray quality across any frequency. And it turns out there's a pretty good method: combining flashing pixels on and off, which one could call dithering in time, with the much more traditional dithering in space. That way, each individual frame should look a lot more like gray and should hopefully help to fool our eyes/the LCD. So let's see what these look like using a checkerboard pixel pattern, alternating which pixels are black and white each frame.

Spoiler For Strobing gray (dithered):
2Hz
4Hz
8Hz
16Hz
32Hz
64Hz

That's definitely a lot better, isn't it! It seems like anything in the range of 32-64Hz would probably be acceptable, and that's about as far as widely used grayscale methods got. But if you look really closely at the 32Hz and 64Hz images and compare them to their non dithered counterparts, you can see that the artifacts scroll across the screen in approximately the same shape. These artifacts are the result of the pixels in the range being black and white for an uneven amount of time. If you want a really good explanation of what's going on here, which is where I learned it, check out thepenguin77's perfect grayscale tutorial. But the gist of it is that the LCD has a constant update frequency, roughly 60Hz, and if you send frames at any frequency that doesn't evenly divide this, the pixels in each frame you send won't appear on the LCD for the same amount of time. And which pixels experience this effect and to what degree depends on where they are in the frame and the order in which the LCD updates its pixels.

So the solution to these artifacts is to match your update frequency to the LCD's update frequency. Which it turns out is impossible to do perfectly, unfortunately, because the LCD update frequency isn't exposed as a signal anywhere that can be synchronized with. But the next best thing is to start with a frequency of around 60Hz and let the user slightly adjust the frequency up or down manually, where getting closer to the LCD's update frequency should noticeably reduce the level of artifacting. When that's all said and done, you'll hopefully get (nearly) perfect grayscale!


I promise it's not just a still image.

Offline Runer112

  • Moderator
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2289
  • Rating: +639/-31
    • View Profile
Re: School of Grayscale
« Reply #3 on: August 24, 2015, 04:59:42 pm »
Grayscale 201

Prerequisites: Grayscale 101, z80 Assembly 101

Before we move on to implementation specifics, there's one more global grayscale quality improvement that you should be aware of. It turns out that the LCD's update direction is left-to-right followed by top-to-bottom, and artifacts appear when your LCD update routine's write position intersects with the LCD's update position. So, to minimize artifacts, your LCD update routine should also go left-to-right followed by top-to-bottom. This unfortunately means more LCD port writes to move the write position around, but unless you're desparate to squeeze out more speed, it's still recommended.

Now that that's out of the way, let's talk more about how to actually implement grayscale in a program. I have identified three important pieces:
  • Image representation/drawing
  • Update routine
  • Update timing

Image representation/drawing

To actually represent grayscale imagery, you're going to need more than 1bpp (bit per pixel). To be precise, you'll need ?log2(shades)?bpp. That comes out to 2bpp for 3- to 4-level grayscale, 3bpp for 5- to 8-level grayscale, 4bpp for 9- to 16-level grayscale, etc. There are two common approaches to storing grayscale image buffers: as separate 1bpp buffers or as one byte-interleaved buffer. The former has the advantages that monochrome drawing routines can be simply be used on each buffer instead of needing dedicated grayscale drawing routines and that the buffers don't need to occupy a contiguous section of memory. The latter has the advantage that routines designed for it, whether drawing or LCD update, are generally faster. But since the way in which you represent grayscale imagery isn't actually integral to how it's displayed on the LCD, we'll end this piece here.

Update routine

The update routine is almost certainly the hardest piece to create, especially at higher levels of grayscale. Specifically, dithering is what makes it hard. A good dithering pattern of course needs to be good at temporal dithering, so each pixel is black/white for the correct percentage of updates. But perhaps harder, especially in combination with the former, is that it should also be good at spatial dithering, so each individual update most accurately approximates the grayscale image.

For 3- and 4-level grayscale, the optimal dithering patterns are rather trivially obvious. Assuming an interleaved buffer pointer in hl with MSB bytes coming immediately after LSB bytes, the inner loop to display dithered 3-level grayscale should look something like the following:

Code: [Select]
loop:
loop:
        rrc     c               ; rotate mask with pattern %10101010
        ld      a,(hl)          ; read a byte of LSB's
        inc     hl
        and     c               ; select half of them
        or      (hl)            ; read a byte of MSB's; set bit -> black
        inc     hl
        out     ($11),a         ; output the dithered byte
        djnz    loop

And, for 4-level grayscale should look something like the following:

Code: [Select]
loop:
        rr      c               ; rotate mask with pattern %100100100
        push    af
        ld      a,(hl)          ; read a byte of LSB's
        inc     hl
        xor     (hl)            ; mux byte of LSB's with byte of MSB's
        and     c
        xor     (hl)
        inc     hl
        out     ($11),a         ; output the dithered byte
        pop     af
        djnz    loop

But past that, the visually best dithering patterns aren't so obvious, and neither are the ways to generate them efficiently in code. Perhaps the best attempt to go further beyond is by the same man who helped out in Grayscale 101. thepenguin77's allGray is an open source demo program that showcases all levels of grayscale from the ultra trivial of 1 up to the far less trivial 8. There are also some somewhat hidden works by tr1p1ea, which simulate 7-, 8-, and [url=http://tr1p1ea.net/files/downloads/ANLVL.8XP]9-level grayscale, but they're unfortunately compiled code only. I defer to both of these individual's work on this matter because they have put in more work into actual implementation, while I've worked more on theory. Speaking of which, I theorycrafted up this chart of what seemed to me to be the best dithering patterns for all levels of grayscale from 1 to 8.


I could certainly believe that there are better patterns. For a number of levels, I provided multiple options becuase I'm not sure which is better visually and/or implementation-wise. In particular, the asterisk in the black color for 7-level grayscale indicates that I don't even think the masking logic for the previous shades works out to produce black. I would wholeheartedly welcome feedback on these!

As an interesting side note, when putting in the actual grays next to the dithered grays for comparison, I noticed that a dither pattern in which x percent of pixels are black does not actually produce x% gray. Upon researching this and other topics, I stumbled across this dithering article, in which appendix 1 is espeically of interest. It corroborates this finding and, furthermore, suggests a formula for how to calculate between the two figures. Combined with some individual's past perceptions that grayscale on a physical calculator does not evenly distribute the shades of gray, this is a topic that I believe requires more research. If one wanted more shade-accurate 4-level grayscale, for instance, perhaps that could be better achieved by selectively using 2 shades of gray from a higher level of grayscale.

Update timing

This topic was pretty well covered in thepenguin77's perfect grayscale tutorial, but I'll repeat the important results. You'll want the grayscale update frequency to be tunable by the user, but it should be roughly around 60Hz. A good way to achieve a roughly 60Hz timer is with the crystal timers on the 83+SE/84+(SE). Write 03h to a timer's loop control port, write 40h to a timer's on/off port for the best base frequency of 10922.667Hz, and write the counter value (start with a value of around 182) to the timer's counter port. Each interrupt, make sure to rewrite 03h to a timer's loop control port! For a sample interrupt handler installer, consider checking out this WikiTI page, although make sure to use the crystal timer as an interrupt source instead of the hardware timer!

Offline Runer112

  • Moderator
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2289
  • Rating: +639/-31
    • View Profile
Re: School of Grayscale
« Reply #4 on: August 24, 2015, 04:59:49 pm »
Reserved for future use.

Offline Runer112

  • Moderator
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2289
  • Rating: +639/-31
    • View Profile
Re: School of Grayscale
« Reply #5 on: August 24, 2015, 04:59:55 pm »
Reserved for future use.