2009-11-23

# Scrollbars and Greyscale Algorithms

Scrollbars have been one of the major banes of Woopsi’s existence for years. No matter what I’ve done, they’ve always been slightly inaccurate. When scrolling through large amounts of data in particular, it is frequently impossible to scroll to the end of the list. If the list is scrolled by dragging the list itself, clicking on the grip causes the list to jump back to show a different portion of the data. Part of my ongoing testing frenzy involved writing a test for the ScrollingListBox gadget, which finally put me in the position to try and really fix these problems.

My first guess was a rounding issue. Scrollbars are basically a simple ratio problem. Suppose we have a list of items 100 pixels high displayed in a window with a scrollbar 10 pixels high. The total height of the scrollbar (10 pixels) must represent the entire list (100 pixels). Therefore, each pixel in the scrollbar is worth 10 pixels in the list.

The rounding problem can arise because Woopsi deals only with integers. Behind the scenes all of the ratio calculations are done with fixed-point math, but the scrollbar’s grip is displayed on the screen and therefore has to align to a pixel. If we adjust the height of the list to 105 pixels, each pixel in the scrollbar is worth 10.5 pixels. That will clearly result in a rounding error.

However, testing the algorithm demonstrated that although the rounding issue exists, it is not significant enough to account for the problems displayed by the scrollbar. In the first example (10 pixels vs 100), there isn’t a rounding error but the inaccuracies in the scrollbar still manifested themselves. Clearly the problem lay somewhere else.

I had a nagging suspicion that the problem had something to do with the height of the grip but couldn’t identify what the exact cause could be. After combing through the code for a while I hit on it. The scrollbar calculates the height of the grip based on the height of the visible portion of data it is scrolling through. In the first example, assuming the window was the same height as the scrollbar, the grip would be one pixel tall. The window and scrollbar are 10 pixels tall, whilst the list of items is 100 pixels tall. The height of the grip is therefore 10 * (10/100), or window * (scrollbar / list).

This gives us a final height of 1 pixel, which is clearly too small to be usable. Instead, the grip height is limited to a minimum of 5 pixels tall. However, if the grip is 5 pixels tall and not 1 pixel tall, this means the last 4 pixels cannot be scrolled through. This was the problem. The fix was to reduce the logical height of the scrollbar whenever the grip was artificially increased in size.

Once this was fixed, another problem became obvious. Clicking the up/down buttons in the scrollbar had strange effects. Sometimes the grip would move in the wrong direction; sometimes it would move and then get stuck; and on other occasions it wouldn’t move at all.

The reason for this was fairly simple. The scrollbars included a way to set the amount that each click would scroll through. By default, it was set to “1”. That would represent the number of pixels scrolled through in a textbox, for example, or the number of items in a list. If we return to the first example, however, attempting to scroll by 1 pixel would actually result in no movement at all. To the scrollbar, 1 pixel translates to 0.1 pixels, which is nothing more than a rounding error.

Instead of this, the scrollbars now calculate the minimum movement that the grip can make and move by that instead.

The scrollinglistbox test project highlighted some other bugs. The ScrollingListBox::getPreferredDimensions() method now returns reasonable values, and it greys out when disabled. Its draw() method performs some preclipping functions that have significantly improved its performance.

Other new test projects include tests for the Label, Button, BitmapButton and AnimButton gadgets. All of these return correct values for their getPreferredDimensions() methods. They all grey out when disabled. This last piece of functionality proved tricky for the BitmapButton and AnimButton classes. In order to allow bitmaps to be greyed out, I’ve added two new methods to the Graphics/GraphicsUnclipped/GraphicsPort classes:

• drawBitmapGreyScale(), which will draw a greyscale version of a bitmap;
• greyScale(), which will grey out a specified region.

The former works like the version of drawBitmap() with transparency - it plots pixel-by-pixel, so it is slower than a straightforward bitmap blit. The second works like dim() - it reads a pixel from the destination, applies a filter to the colour, and writes it back.

drawBitmapGreyScale() isn’t a fast method, and using it with the AnimButton probably isn’t the smartest idea. Every new frame drawn to the button needs to be greyed out. On the DS it isn’t noticably slow, but in a DS emulator the slowdown is pronounced. I’m considering stopping the animation when a button is disabled and restarting it when the button is enabled again. This will significantly reduce the amount of work done each frame.

The greyscale routine was fairly easy to write. The algorithm looks like this:

• Read pixel (in 555 RGB format)
• Halve brightness of pixel by right-shifting one place (giving 444 RGB format)
• Extract red pixel right-shifted one place (giving 344 RGB format)
• Extract green pixel (still 344 RGB format)
• Extract blue pixel right-shifted one place (giving 343 RGB format)
• Add red, green and blue components together (giving a single 5-bit component)
• Recreate a 555 format pixel by re-using the single component in the place of R, G and B
• Write pixel back at original co-ordinates.

This simplistic luminosity-based algorithm gives a 15-bit greyscale image weighted slightly more in the green component, reflecting the properties of the human eye. Other algorithms for this are listed on John D Cook’s blog.