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.

Comments

Chase-san on 2009-11-30 at 22:29 said:

I recently had problems with scrollbars so I decided to do a short writeup on them. You can find my full explination here: http://www.csdgn.org/db/179

I had looked at your older code originally and I realized it just looked wrong, and it didn’t work for any scrollbars I was to construct from it. So I realized I would need to work out the problem for myself. Which I did. :)

Ant on 2009-11-30 at 23:24 said:

You have a few bugs in there. If you override the calculated size of the grip and set it to a minimum size (if the grip is too small), you need to adjust the ratio to compensate. This was the bug I fixed most recently. If you don’t, you’ll find that you can’t scroll to the bottom of the content.

You don’t need to work from the middle of the grip. Suppose you have a track 100px tall and a grip 10px tall. If you consider the top of the grip to be the “hotspot”, you can drag it from 0px to 90px, giving you a range of 90px. If you consider the middle of the grip to be the hotspot, you can drag it from 5px to 95px, giving you a range of… 90px. As long as your calculations are consistent in the way they work with the grip there is no advantage at all in trying to use the centre of the grip as the hotspot. In fact, it’s a definite disadvantage in some places. Consider a grip 7px tall - you’re screwed on platforms without floats, since 7/2 = 3.5. More importantly, you’re doing unnecessary calculations.

Good post, though! If only there was some way I could send a link to it back to myself in January last year it’d save me a lot of work…

Chase-san on 2009-12-01 at 21:06 said:

It doesn’t actually use the center of the grip, I optimized that away, and it uses the top of the grip, I was just explaining how myself see it, but in the end I use the top as seen in the code. As for the ratio… your right. I did forget about that. Hah. Well I am not perfect. I suppose I will add that and credit you for it.

Chase-san on 2009-12-01 at 21:07 said:

Actually now that I look at it, I never use the grip ratio again, just its size, so I do not need to recalculate the ratio. :P

Ant on 2009-12-01 at 21:34 said:

You need to adjust anywhere you use the height of the track. For example, suppose you have a track 100px tall and a grip 10px tall. You want to make sure that the grip is at least 30px tall, so you set its height to 30px. Now your track only represents a range of 70px, not the 90px that it should show, due to the fact that the grip has been made 20px larger.

You calculate scrollSize like this:

float scrollSize = trackSize - gripSize;

That will give you a scrollSize of 70px (the range I was discussing) instead of 90px. This is 20px off.

You calculate gripPosition like this:

float gripPosition = scrollSize * scrollRatio;

This is now 20 * scrollRatio off, because of the error in scrollSize.

Lastly, you calculate this:

float newScrollRatio = newGripPosition / scrollSize;
windowPosition = newScrollRatio * contentSize;

newScrollRatio is totally wrong because of the inaccuracy in scrollSize. windowPosition is wrong too, because newScrollRatio is off.

What you need to do is this:

float trackSize = 180;
float virtualTrackSize = 180;
float windowSize = 200;
float contentSize = 520;

float minGripSize = 24;
float maxGripSize = trackSize;

//0.4
float gripRatio = windowSize / contentSize;

//72
float gripSize = trackSize * gripRatio;

if(gripSize < minGripSize) {
    virtualTrackSize -= (minGripSize - gripSize);
    gripSize = minGripSize;
}
if(gripSize > maxGripSize) gripSize = maxGripSize;

Now if you use the new virtualTrackSize in the place of trackSize everywhere else in the code, you should find that you eliminate the problem. This is the same issue I was discussing in the blog post - if you increase the size of the grip artificially, you also need to decrease the logical size of the track that contains it.

Chase-san on 2009-12-02 at 23:42 said:

Ahh I think understand, I suppose this one of those ‘special cases when the grip is set to the minimum size, because it was smaller’, that I was trying to avoid having when writing the code, I take it the handful of bottom items are cut off?

If not I would need it to explained in a way so that I will understand the problem. :)

Ant on 2009-12-03 at 06:44 said:

Yep, that’s right.