Friday, March 26, 2010

Obicham -- Color Algorithm

I discovered yesterday that the color selection algorithm I used for the nearest color algorithm didn't quite cover all the possible combination of foregrounds, backgrounds, and blends. The old algorithm code looked something like this:

Let c be the color that is the texel in an image at row y, column x:
Find the nearest two colors in the 16-color VGA palette (note: O(16) time)
Let output be the console character on the screen at row y, column x
Let output's background color be the closest color (most predominant visually)
Let output's foreground color be the next closest color (least predominant visually)
Let output's display character be a blend between 0%, and 50% fill, depending on how close the color is to its nearest color (blank) or to its second-nearest color (50% fill)


And with the new palette containing all available possible characters:

(We build the table before hand)
For fg in 16-color VGA palette:
 For bg in 16-color VGA palette:
  For bl in the available blend amounts:
   Let blend be the bl% mix of color fg onto bg
    If the fg, bg, and blend combination doesn't already exist in the palette then
    Add blend, along with the fg, bg, and blend used, to the palette

(Next, the color selection algorithm)
Let c be the color that is the texel in an image at row y, column x:
Let output be the console character on the screen at row y, column x
Set output to be the fg, bg, and blend combination for the closest color to c in the palette (note: O(310) time)


For small palettes, say the old 16 colors, this algorithm didn't need any optimization. However, now that we have all the possible 310 (!) colors, this algorithm now becomes quite heavy. For an image sized 80 by 60, the total time to convert an image will take O(80x60x310) time, or O(1,488,000) time! So a hunt begins for a data structure that will improve the speed.

I first thought a Voronoi diagram would help sort the data. However, implementing a 3D Voronoi tree builder took me more time than I was willing to spend on it. So I searched elsewhere.

Next, I hypothesized that a Voronoi diagram is the same as a BSP where its branches are a selection of planes, where each unique plane is equidistant to two unique points. Also, it would be faster for me to implement. In a half hour's time, I came up with a rough tree building algorithm:


If there is only one point in P left, then add it to the tree, and return
Find a plane, L, that is equidistant between two points that splits the points as close to half as possible
Repeat for points in P that are in front of the plane L
Repeat for points in P that are behind the plane L


Although there is a small delay building the tree (brute force implementation), the results of this tree are significantly faster, since it takes at most log(310)/log(2) ~8 checks per texel instead of 310! However, my assumption is incorrect:


On the right is the non-BSP color selection algorithm (most correct), and on the left is the BSP color selection algorithm. As you can see there are abnormalities in the BSP color selection algorithm. It became quite clear to me that making a planar cut anywhere in a Voronoi diagram chops off some of the cells! D'oh!

Well, from here I can do two things to spend my weekend:
  1. Build a proper Voronoi structure
    • Either using Fortune's algorithm
    • Or by creating convex meshes from the availble planes built by the original BSP algorithm
  2. Duplicate some of the data in the BSP tree
  3. Play DoTA/League of Legends
  4. Catch up on homework


Hmm ...

No comments:

Post a Comment