2011-01-16
2011-01-15
2011-01-15 - More Dithering
Moving on from the success of Parrot dithering, I decided to run a few more tests on the quantising/dithering engine to see what kind of effects I could get out of it. I modified the drawing routine to allow a half-dithered option where the error value is divided by two so that only half the error is applied to the following pixel. Also adjusted the calling code to then draw three parrots with the three forms of dithering, none, half and full. The half-dithered approach did work to soften some of the artefacts from the crude dithering in some cases, but also ruined the effect in others.
The next thing I wanted to do was to see what effect changing the palette would have on the quantiser/ditherer. First thing I tried was a grey scale of 0x000000, 0x111111 up to 0xFFFFFF. This worked well and gave a very striking result, except for the anticipated fact that the greens looked dark and the blues looked bright. Also of note was that the non-dithered version looked considerably better than the dithered version as the dithering artefacts destroyed the image. It's possible that a Floyd-Steinberg dithering will improve this as each row will influence the following one.
Following on from this, I used a commercial paint package to calculate a 16-colour palette from the source image so that I could set the VGA palette to this. With the optimised palette in hand, I couldn't resist setting only the red colour into the palette ... the result was impressive. Most of the parrot was highlighted in red, with the entire background in shades of grey, very satisfying.
I implemented the full optimised palette, but the result didn't seem much better than my original palette, probably because the original palette was chosen to give a wide spread of colours in the available depth.
I then tried some different images, the OS logo (not released yet :P ), and two random images from the internet. All the images worked really well, especially the colourful logo.
The next thing I wanted to do was to see what effect changing the palette would have on the quantiser/ditherer. First thing I tried was a grey scale of 0x000000, 0x111111 up to 0xFFFFFF. This worked well and gave a very striking result, except for the anticipated fact that the greens looked dark and the blues looked bright. Also of note was that the non-dithered version looked considerably better than the dithered version as the dithering artefacts destroyed the image. It's possible that a Floyd-Steinberg dithering will improve this as each row will influence the following one.
Following on from this, I used a commercial paint package to calculate a 16-colour palette from the source image so that I could set the VGA palette to this. With the optimised palette in hand, I couldn't resist setting only the red colour into the palette ... the result was impressive. Most of the parrot was highlighted in red, with the entire background in shades of grey, very satisfying.
I implemented the full optimised palette, but the result didn't seem much better than my original palette, probably because the original palette was chosen to give a wide spread of colours in the available depth.
I then tried some different images, the OS logo (not released yet :P ), and two random images from the internet. All the images worked really well, especially the colourful logo.
2011-01-07
2011-01-07 - VGA Graphics over Christmas
Lots to catch up on here over the last two weeks, so here goes ...
Over the Christmas break, I began reading some more of the "Programmers guide to the EGA, VGA and Super VGA" book. Taking a few ideas and information from here, I decided to revisit some of the graphics VGA elements I have in place.
First things first, I took a copy of my base OS, stripped out various bits and pieces, and ended up with a kernel that booted, and set up Mode 12h. I also rewired the keyboard handler to reboot the machine so I didn't need to keep power cycling it. (Idea: Use the interrupt handler to reboot the machine on the escape key always, which should prevent infinite loops blocking the soft reset.)
With that in place, my OS boots to a black, 640 by 480 by 16 colour screen, and does nothing other than reboot when I press any key.
First thing I did was got something drawn to the screen. This was mainly so that I could see that it worked and this blank screen was, in fact, "A Good Thing"(TM). This was done using the the same method as before by setting the Plane Write and then writing to the memory.
This worked, so I quickly moved on to reimplementing the Plot routine to draw pixels to the screen. Instead of the previous method of looping each plane in turn, reading the byte, masking the old byte with the new one, then writing the new byte back, the new method uses VGA Write Mode 2, sets the Bit Mask register, and writes to the memory once. This should be significantly faster than before.
I then rewrote the DrawHorizontal() routine. This routine draws a horizontal line on the screen in one colour, and is optimised to take advantage of the screen's memory configuration. With this routine, I created a set of function calls to this routine so that I could verify that all the combinations of starting and ending pixels worked correctly as the calculation for this involves lots of bit shifting and boolean logic.
I knew I would also need control of the palette, so I pulled up a copy of some old code which set the palette and set about updating it. I added a global array of sixteen 24-bit colours to the file and made a routine to read this array, and set the equivalent 18-bit colour to the palette using the old routine. Curiously, the 16 EGA palette registers actually refer to colours in the 256 colour VGA palette, but they don't map to 0 to 15 as you might expect, so I remapped these into the 0 to 15 range for convenience. This was all tested to ensure that I could influence the palette as required.
With all of these things working, I had a fairly boring screen with some test elements on it. Time to throw in some Win!
When I was first toying with the Mode 12h screen, one of the things I did was to take a 640x480 picture on the PC, convert it down into 16 colours (which used a palette not far from the VGA standard) and then append the bitmap file onto the end of a kernel. I then wrote a function to read the bitmap header, find the palette and map it to the nearest displayable colour, and then draw the bitmap to the screen. It wasn't pretty code, and it certainly wasn't fast, but it worked and displayed the full-screen image. One of the things I always regretted about this implementation was that I have to convert the image to 16 colours using the PC.
This time around (and using the information on Colour Quantisation and Dithering that I had been subconsciously processing since) I decided that I would not only improve the nearest colour system, but also throw in some dithering as well. To start this off, I went to the OS Dev wiki and searched around for articles on either ... nothing, so I set about to write them.
A short while later, I had an article on Colour Quantisation that detailed how to extend or contract colours, talked about the Euclidean distance algorithm, and I have also come up with what should be a very fast method of pre-calculating Euclidean distances to greatly improve the speed of the GetNearestColour(). I had also finished an article on Dithering which covered some very basic Error Diffusion algorithms.
The main outcome from writing these articles was not the dissemination of information to help others (which is a side-benefit), but to help focus my thoughts and to allow me to write my own plan in the form of a guide to others.
I found a colourful picture from the web, specifically a 24-bit bitmap of a parrot, saved it to a file, and extracted 24-bit bitmap data from the file and placed it into a byte array inside my OS. This would be the image data that I would use to test the routines as I wrote them.
The first step for this part was to create a routine that was able to plot 8 neighbouring pixels at the same time because this is how the Mode 12h memory is organised. I threw this together fairly quickly, so that it accepted X and Y coordinates, a bitmask, and an array of eight palette indices to draw, and then draw them.
I then wrote the colour quantiser. I already had the Euclidean-based nearest colour algorithm from before, and from writing the article I had worked out that a pre-calculated table of 512 entries would enough for what I needed, so I created the table, and wrote a routine to populate it based on the colours in the global palette array.
Following on from this, I wrote the routine to read the bitmap data of the parrot, use the quantiser to map each pixel in turn, and write eight pixels at a time to the screen using the Plot8() function. Booting this up, it looked nothing like a parrot. Onoes!
Onto the familiar task of debugging. The first problem was easy to track down. Bitmap (.bmp) files align each row to a 4-byte boundary, and as my image was 150 pixels wide, I needed to advance the pointer by 2 bytes at the end of each row. The result of this problem was that the 3-byte pixels were falling out of alignment, so RGB on the first row was becoming BRG on the second, and GBR on the third, resulting in bands of colour. This was easily corrected, and things looked a little better.
The second issue was that the GetNearestColour() wasn't correctly contracting the 24-bit colour into the 9-bit colour required to access the precalculated table of colours. This just needed some bitmask corrections.
The display now definitely looked like a parrot, but a parrot behind a bathroom window, where each vertical stripe of the parrot looked backwards. Was this the Plot8() routine being wrong, or the data being passed to the Plot8() routine. Adding in a quick call to Plot8() to display a pattern of white pixels followed by purple pixels quickly revealed that the Plot8() routine was at fault and backwards. This was quickly fixed.
Recompiling and rebooting the test machine and, tada.wav, it works. One nearest colour parrot displayed from 24-bit bitmap data.
The quantiser was working perfectly, and the image display was fast. Well, I think it was fast, it displayed the image before the monitor had adjusted to the Mode 12h screen, so I'm happy to consider that fast for now. Unfortunately, nearest colour just wasn't good enough.
Turns out that to implemented my simple dithering algorithm was amazingly easy. Create a unioned structure so that I could access the red, green and blue components of the colour easily, and create a second one that used signed integers for the three components. This is needed of course because the error could be either positive or negative. I added the code to calculate the error, and the code to add the error into the bitmap colour before it was quantised. Recompiled and rebooted.
Sufficed to say, the first test was not successful, nor was the second, third or fourth. The problem with each attempt was that I got overflow errors every time, so a high red value plus a positive red error wrapped around to a low red value and vice-versa. For the fifth attempt, I wrote a separate function to add the colour error to the colour in a very careful manner.
Once more, tada.wav, and not just any tada.wav, but a really big tada.wav! The dithering, whilst being simple, was amazing and worked perfectly. One very well dithered parrot, even if it was only in 16 colours.
One more minor modification was to make the dithering enable an option to the drawing routine, along with an X coordinate start, so that I could draw two parrots side-by-side, one with nearest colour and the other dithered to see the difference. Took photos to show people. Big win!
Over the Christmas break, I began reading some more of the "Programmers guide to the EGA, VGA and Super VGA" book. Taking a few ideas and information from here, I decided to revisit some of the graphics VGA elements I have in place.
First things first, I took a copy of my base OS, stripped out various bits and pieces, and ended up with a kernel that booted, and set up Mode 12h. I also rewired the keyboard handler to reboot the machine so I didn't need to keep power cycling it. (Idea: Use the interrupt handler to reboot the machine on the escape key always, which should prevent infinite loops blocking the soft reset.)
With that in place, my OS boots to a black, 640 by 480 by 16 colour screen, and does nothing other than reboot when I press any key.
First thing I did was got something drawn to the screen. This was mainly so that I could see that it worked and this blank screen was, in fact, "A Good Thing"(TM). This was done using the the same method as before by setting the Plane Write and then writing to the memory.
This worked, so I quickly moved on to reimplementing the Plot routine to draw pixels to the screen. Instead of the previous method of looping each plane in turn, reading the byte, masking the old byte with the new one, then writing the new byte back, the new method uses VGA Write Mode 2, sets the Bit Mask register, and writes to the memory once. This should be significantly faster than before.
I then rewrote the DrawHorizontal() routine. This routine draws a horizontal line on the screen in one colour, and is optimised to take advantage of the screen's memory configuration. With this routine, I created a set of function calls to this routine so that I could verify that all the combinations of starting and ending pixels worked correctly as the calculation for this involves lots of bit shifting and boolean logic.
I knew I would also need control of the palette, so I pulled up a copy of some old code which set the palette and set about updating it. I added a global array of sixteen 24-bit colours to the file and made a routine to read this array, and set the equivalent 18-bit colour to the palette using the old routine. Curiously, the 16 EGA palette registers actually refer to colours in the 256 colour VGA palette, but they don't map to 0 to 15 as you might expect, so I remapped these into the 0 to 15 range for convenience. This was all tested to ensure that I could influence the palette as required.
With all of these things working, I had a fairly boring screen with some test elements on it. Time to throw in some Win!
When I was first toying with the Mode 12h screen, one of the things I did was to take a 640x480 picture on the PC, convert it down into 16 colours (which used a palette not far from the VGA standard) and then append the bitmap file onto the end of a kernel. I then wrote a function to read the bitmap header, find the palette and map it to the nearest displayable colour, and then draw the bitmap to the screen. It wasn't pretty code, and it certainly wasn't fast, but it worked and displayed the full-screen image. One of the things I always regretted about this implementation was that I have to convert the image to 16 colours using the PC.
This time around (and using the information on Colour Quantisation and Dithering that I had been subconsciously processing since) I decided that I would not only improve the nearest colour system, but also throw in some dithering as well. To start this off, I went to the OS Dev wiki and searched around for articles on either ... nothing, so I set about to write them.
A short while later, I had an article on Colour Quantisation that detailed how to extend or contract colours, talked about the Euclidean distance algorithm, and I have also come up with what should be a very fast method of pre-calculating Euclidean distances to greatly improve the speed of the GetNearestColour(). I had also finished an article on Dithering which covered some very basic Error Diffusion algorithms.
The main outcome from writing these articles was not the dissemination of information to help others (which is a side-benefit), but to help focus my thoughts and to allow me to write my own plan in the form of a guide to others.
I found a colourful picture from the web, specifically a 24-bit bitmap of a parrot, saved it to a file, and extracted 24-bit bitmap data from the file and placed it into a byte array inside my OS. This would be the image data that I would use to test the routines as I wrote them.
The first step for this part was to create a routine that was able to plot 8 neighbouring pixels at the same time because this is how the Mode 12h memory is organised. I threw this together fairly quickly, so that it accepted X and Y coordinates, a bitmask, and an array of eight palette indices to draw, and then draw them.
I then wrote the colour quantiser. I already had the Euclidean-based nearest colour algorithm from before, and from writing the article I had worked out that a pre-calculated table of 512 entries would enough for what I needed, so I created the table, and wrote a routine to populate it based on the colours in the global palette array.
Following on from this, I wrote the routine to read the bitmap data of the parrot, use the quantiser to map each pixel in turn, and write eight pixels at a time to the screen using the Plot8() function. Booting this up, it looked nothing like a parrot. Onoes!
Onto the familiar task of debugging. The first problem was easy to track down. Bitmap (.bmp) files align each row to a 4-byte boundary, and as my image was 150 pixels wide, I needed to advance the pointer by 2 bytes at the end of each row. The result of this problem was that the 3-byte pixels were falling out of alignment, so RGB on the first row was becoming BRG on the second, and GBR on the third, resulting in bands of colour. This was easily corrected, and things looked a little better.
The second issue was that the GetNearestColour() wasn't correctly contracting the 24-bit colour into the 9-bit colour required to access the precalculated table of colours. This just needed some bitmask corrections.
The display now definitely looked like a parrot, but a parrot behind a bathroom window, where each vertical stripe of the parrot looked backwards. Was this the Plot8() routine being wrong, or the data being passed to the Plot8() routine. Adding in a quick call to Plot8() to display a pattern of white pixels followed by purple pixels quickly revealed that the Plot8() routine was at fault and backwards. This was quickly fixed.
Recompiling and rebooting the test machine and, tada.wav, it works. One nearest colour parrot displayed from 24-bit bitmap data.
The quantiser was working perfectly, and the image display was fast. Well, I think it was fast, it displayed the image before the monitor had adjusted to the Mode 12h screen, so I'm happy to consider that fast for now. Unfortunately, nearest colour just wasn't good enough.
Turns out that to implemented my simple dithering algorithm was amazingly easy. Create a unioned structure so that I could access the red, green and blue components of the colour easily, and create a second one that used signed integers for the three components. This is needed of course because the error could be either positive or negative. I added the code to calculate the error, and the code to add the error into the bitmap colour before it was quantised. Recompiled and rebooted.
Sufficed to say, the first test was not successful, nor was the second, third or fourth. The problem with each attempt was that I got overflow errors every time, so a high red value plus a positive red error wrapped around to a low red value and vice-versa. For the fifth attempt, I wrote a separate function to add the colour error to the colour in a very careful manner.
Once more, tada.wav, and not just any tada.wav, but a really big tada.wav! The dithering, whilst being simple, was amazing and worked perfectly. One very well dithered parrot, even if it was only in 16 colours.
One more minor modification was to make the dithering enable an option to the drawing routine, along with an X coordinate start, so that I could draw two parrots side-by-side, one with nearest colour and the other dithered to see the difference. Took photos to show people. Big win!
Subscribe to:
Posts (Atom)