Texel and image processing

# Texel and image processing

here i will try to explain how to process drawing characters and turn 2D pixel maps into text format in great detail along with a technical deepdive into the methods used

If you read this whole article you should have very in depth and advanced level of understanding of how 2D rendering in computercraft works and you should for example be able to render png images with ease with incredible speeds

This article will cover a whole range of topics from basics to expert, someone who is even slightly competent in Lua and CC should be able to understand  the stuff discussed here as i try to explain it from basics up

Each topic will be labeled with one of 3 difficulties,
|marking|   name   	|Short description                                                                              |
|---	|--------	|---------------------------------------------------------------------------------------------	|
| B 	| Basic  	| Should be able to be understood by a decently competent programmer                          	|
| M 	| Medium 	| If you fully understood basics and know some basic graphics you should understand this fine 	|
| E 	| Expert 	| Decently complex. Not as detailed explanations cause too many details                       	|

## List of contents:
- **Rendering pixels**
    - [**Pixel rendering basics**](#rendering-pixels) **<sub>B</sub>**
    - [**Basics of binary**](#understanding-base2) **<sub>B</sub>**
    - Understanding drawing character (texel) structure
        - [**Binary encoding of texels**](#connection-of-binary-and-texels) [*ex. code*](#example-implementation) **<sub>B</sub>**
        - [**String bitstream reversing** (endian correcting)](#why-reverse-the-bitstream-this-is-because-if-you-look-at-the-actual-charset-we-start-at-values-in-the-top-left-which-have-the-lowest-value-index-in-the-actual-charset-however-if-we-just-map-it-into-a-binary-number-like-010110-the-top-left-pixel-will-be-the-left-most-bit-in-the-string-and-since-binary-values-are-represented-with-big-endian-meaning-leftmost-digit-has-the-highest-valuecontribution-to-the-number-this-woulnt-match-up-because-as-mentioned-the-top-left-pixel-actually-has-the-lowest-value-so-we-just-flip-the-bitstream-to-correct-for-this-this-wont-actually-matter-for-real-scenarios-and-purely-matters-for-this-explanation-as-when-we-actually-process-these-characters-we-wont-be-doing-it-like-this-this-is-purely-to-explain-the-theory-and-reasons-behind-it)
        - [**Handling sixth texel bit**](#the-6th-bit) [*ex. code*](#example-implementation-1) **<sub>B</sub>**
        - [**Table implemention**](#table-implementation) [*ex. code*](#example-implementation-2) **<sub>M-</sub>**

- **Color handling**
    - [**Issues with texels and colors**](#issues-with-color-handling-in-texels) **<sub>B</sub>**
    - [**Making a bitstream out of colors with mapping**](#making-a-bitstream-out-of-colors) [*ex. code*](#example-implementation-3) **<sub>B</sub>**
    - [**Simple color processing**](#simple-color-processing) **<sub>B</sub>**
    - [**Simple quantization**](#quantization-and-mapping) [*ex. code*](#example-implementation-4) **<sub>M</sub>**
    - [**Complex quantization**](#complex-quantization) [*ex. code*](#example-implementation-5) **<sub>M+</sub>**

- **Optimization**
    - Basic optimization ideas **<sub>M</sub>**
    - 16^6 problematic **<sub>M</sub>**
    - Using color "patterns" to make lookup possible **<sub>E</sub>**
    - Lookup ID generation **<sub>E</sub>**
    - Using lookups for character picking **<sub>E</sub>**
    - Using lookups for color quantization **<sub>E</sub>**
    - Bruteforcing IDs for best memory efficiency **<sub>E+</sub>**

- **Extra**
    - Screen edge artifacts **<sub>B</sub>**
    - Turning CC colors from and to blit codes **<sub>B</sub>**
    - Monitor character and pixel size calculation **<sub>B</sub>**
    - Simple RGB color quantization **<sub>B+</sub>**
    - Fast color quantization **<sub>M</sub>**
    - Png image loading with [**PngLua**](https://github.com/9551-Dev/pngLua) **<sub>B</sub>**

- **Credits**
    - [**People and project contributors**](#credit)
    - [**CCGR Project**](#part-of-computercraft-graphics-research)

### rendering pixels:
In computercraft we use specialized drawing characters to display "pixels", to these we will refer to texels from now on because well, its pixels made out of text, heres the computercraft charset, what we are interested in here are the characters 128 to 159

![computercraft charset](resources/cc_charset.png)

For you to understand how to process these you will have to understand base2, also known as binary.
#### understanding base2
in base10 we have 10 digits (0,1,2,3,4,5,6,7,8,9) and each digit has 10x higher value than the one before it, for example to see this you can split a base10 number into its individual digits. Lets split 5189, that would be `5*1000 + 1*100 + 8*10 + 9*1` Notice the "coefficients" here, starting from left to right we have 1000,100,10,1, each one is 10x more significant than the one more to the right you could also easily note this as `5*10^3 + 1*10^2 + 8*10^1 + 9*10^0`, while this doesnt seem to be very useful you can use this to understand and convert any base to base10!, notice how we have `digit*base^(digit_index-1) + ...`, this means that if i told you to convert 101011 to base10 you would be able to do it just like this!
```lua
1*2^5 + 0*2^4 + 1*2^3 + 0*2^2 + 1*2^1 + 1*2^0
```
Counting in base2 is bit more difficult but doesnt take too long to master, here i will do an example with 3 bits (binary digits)
```lua
0: 000
1: 001
3: 010
4: 011
5: 100
6: 101
7: 110
8: 111
```
this also shows an interesting fact that you can calculate the maximum number you can archive in a given base with a given digit count with a simple formula, `base^(digit_count) - 1`. Here we use - 1 because `base^digit_count` calculates the amount of values we can represent **INCLUDING ZERO** with a given digit count, however we dont want that. We want the maximum value, so we subtract 1 to exclude 0 digit from the values.
ex.
```lua
-- base^(digit_count) - 1
2^3 - 1 = ?
2^3 = 2*2*2 = 8
8 - 1 = 7
-- the maxmimum amount of digits we can represent with 3 bits in base2 is 7
-- which checks out, tonumber("111",2) -> 7 ("111" being the maximum number representable with 3 bits)
```
#### Connection of binary and texels
Okay lets look at it like this, lets take our desired texel and turn it into a 2D color map, lets use 153 as an example
our map will be 2x3 because all texels represent pixels in a 2 by 3 grid (note that colors are here taken from the chart above)
```yml
blue  white
white blue
blue  white
```
now lets turn it into a so called "stream" basically just put it into a 1 dimensional data structure instead of 2D
```yml
blue white white balue blue white
```
This was done by essentially just removing the newlines between the individual layers of the character.

Now lets just turn it into a "binary stream" by converting the "lit up" areas of the character to 1 and the "emtpy" (background color ones) to 0
```yml
100110
```
this gets us the binary code for the character, now lets do this for all the characters in the charset, also first we can calculate how many entries we will even have, notice how no character has the sixth bit enabled, this means there is just 5 bits to calculate with which is 2^5, `2^5 = 2*2*2*2*2 = 32`, So there will be 32 entries in our table
```
000000
100000
010000
110000
001000
101000
011000
111000
000100 ...
```
Im not gonna actually write out all of these, but if you look closely or flip the binary strings you will notice that its essentially binary counting, this means the order of the character in the list directly coresponds to what it is
so if you wanna know how the sixth character looks like you can just encode 5 in binary (Why 5? because 5 is the 6th digit in base10, 0,1,2,3,4,5. Never forget about 0!), which is `101` then pad it to get all 6 bits you need to get your texel code, `101000`, lastly you can just split it into 2D map by adding a newline every two bits
```
10
10
00
```

Knowing this you can easily also lookup any character in the charset,
first take your 2D character map
```
01
01
10
```
Then turn it into a bitstream `010110`, reverse the bitstream, so that we have `011010` which is 26 in decimal (base10)

###### *why reverse the bitstream?*, this is because if you look at the actual charset we start at values in the top left which have the lowest value (index in the actual charset), however if we just map it into a binary number like `010110` the top left pixel will be the left most bit in the string, and since binary values are represented with big endian (meaning leftmost digit has the highest value/contribution to the number) this woulnt match up, because as mentioned the top left pixel actually has the lowest value, so we just flip the bitstream to correct for this. This wont actually matter for real scenarios and purely matters for this explanation as when we actually process these characters we wont be doing it like this, this is purely to explain the theory and reasons behind it

Knowing this also tells you that the character with this specific pixel config is the 26th character in the computercraft texel charset,
but of course the entire CC charset doesnt start off with the texel characters, to get to that range you need to add 128 to the values.
This shifts the character into the telext character range

###### example implementation
```lua
-- defines character data
local char = [[
01
01
10
]]

-- removes all newlines by replacing them with an empty string
local binary_stream = char:gsub("\n","")

-- reverses to correct for order, reasoning explained above
binary_stream = binary_stream:reverse()

-- turn the binary stream into base10 from base2 using tonumber
local char_num = tonumber(binary_stream,2)

-- calculate the position in the actual charset using an offset
local char_index = char_num + 128

-- get the character string from the number and display it
print(string.char(char_index))
```

**TLDR**: Characters in the charset are essentially encoded as binary, if you put them into a 1D list of bits you notice they are essentially counting in binary

#### The 6th bit
The sharper ones among you might have noticed that none of the the characters have the bottom right pixel enabled, this is the sixth bit and it has a bit of special handling to save up on charset size, ommiting this bit in the charset isnt actually big deal as you can still get your desired characters every time!

All you really need to do is flip flip the bits and your colors- lemme explain. Lets say you want to render
```
red red
red black
red red
```
And your algorithm encodes a red as 1 and black as a 0, which will give you
```
11
10
11
```
but if you happen to try and encode this into a texel the normal method without any special handling the data will oveflow outside of the texel charset range.

We need a way to somehow convert this into a format where the sixth bit can never be 1 while muting all the data the same way to not actually alter the saved data

The solution is quite simple, simple invert the entire texels bitstream like this
```
00
01
00
```
Okay now you have a viable character that you can process, the only issue is that your colors have been broken, oh no!
```
black black
black red
black black
```
Lucky for you the solution is super easy, as instead of red and black and 1 and 0 you can just think it of these as the text color (foreground/fg) and background color (bg)
```
bg bg
bg fg
bg bh
```
Which means that all you really need to fix your colors is to flip the background and foreground color of the rendered character and bam!
```
red red
red black
red red
```
you have corrected the colors back to your original character by flipping the background and using an inverted symbol, in this case you would specifically want a symbol like mentioned above (binary string being `000100`)

###### example implementation
```lua
-- applies the colors given in the explanation above
term.setTextColor(colors.red)

local char = [[
11
10
11
]]

-- removes all newlines by replacing them with an empty string
local binary_stream = char:gsub("\n","")

-- read the last bit in the stream and check if it happens to be enabled
local bit6 = binary_stream:match(".$") == "1"

-- reverses to correct for order, reasoning explained above
binary_stream = binary_stream:reverse()

-- if bit6 is enabled inverts all bits to get an alternate existing character
-- this makes use of gsub to match all ones and zeroes and invert them
-- accordingly using a lookup table, little known feature of gsub.
-- also flips the colors of foreground and background to correct for
-- the inversion of the character
if bit6 then
    binary_stream = binary_stream:gsub("[10]",{["1"]=0,["0"]=1})

    local fg = term.getTextColor()
    local bg = term.getBackgroundColor()

    term.setTextColor(bg)
    term.setBackgroundColor(fg)
end

-- turn the binary stream into base10 from base2 using tonumber
local char_num = tonumber(binary_stream,2)

-- calculate the position in the actual charset using an offset
local char_index = char_num + 128

-- moves cursor pos to not have character touch edges of the screen
term.setCursorPos(2,2)

-- get the character string from the number and display it
print(string.char(char_index))
```
**TLDR**: Invert bits within binary stream and flip background and foreground color

#### Table implementation
So far all of the examples shown have used strings to store bitstreams and string function like reverse and gsub to handle them, however this is now how we will work going forward as manipulating strings in any more complex ways than this is a major hassle, instead we will use tables for pretty much everything. Lets think about what we need to change.
###### character stream data structure
While before we could just use a multline string, now we will use tables. There are 2 ways to do this, either we can do it using a **2D array** or the **stream method** we used with string

2D array method
```lua
local char = {
    {1,1},
    {1,0},
    {1,1}
}
```
While this may seem convenient (and at first it actually is) because we can look up value of any bit in the pixel with x,y coordinates like this: `char[y][x]` its actually more of a hassle going forward. Thats why there is the second bitstream method.
There is essentially 2 ways to write this, one way more readable than the other but data wise essentially same.
```lua
local char = {1,1,1,0,1,1}
```
```lua
local char = {
    1,1,
    1,0,
    1,1
}
```
Not only is this faster and more memory efficient, it also allows us to still index it as a 2D array with just a little index calculation equation!
The general equation/rule for calculating indices in arrays like this is
```
index = (y-1)*width + x
```
so lets say we wanted the bit at position `x=1,y=3`, we know that the width of texel is 2 pixels
```lua
index = (3-1)*2 + 1
index = 2    *2 + 1
index = 4       + 1
index = 5
```
the index 2 does indeed correspond to the value at `x=1,y=3` in the pixel
###### reading the last bit for 6th bit correction
Well, this is super simple.
Given by how we format the table we can decide that the 6th bit will always be on the sixth index in the table (duh), so we simply just do something like this
```lua
-- comparing the last (sixth bit) to check if its enabled
local bit6 = char[6] == 1
```
###### Reversing the bit stream
Considering that we wont be able to use `tonumber` like we did with the string (`tonumber` uses big endian which requires as to invert our bitstream) we dont really have to invert the bitstream, this is because we will have full control over the function that turns the binary data into decimal and can make it work with small endian so we directly convert it backwards instead of inverting before conversion
###### Iverting the bit stream
Reversing the bit stream can be handled the same way as reversing the bit stream, just do it in the `binary->decimal` conversion step
###### translating into base10
There is 2 ways to do it, you can either use a for loop or you can use a bunch of if statements.

With a for loop we will essentially just do the same stuff we did in the [binary basics part](#understanding-base2) with this equation `digit*base^(digit_index-1) + ...`
```lua
-- init number as 0 so we can add to it the different parts of the binary number
local char_num = 0

-- defines the fact that we want to decode base2 numbers
local base = 2

-- loop over all 6 bits of the binary number
-- technically we can loop over just 5 as the last one will always be zero
for i=1,6 do
    -- grab binary number from the char data array (this is why making it a 2D array would make it a pain)
    local binary_value = char[i]

    -- inverts the bit if the sixth bit is enabled
    -- this is equivalent to our bitstream inversion from before
    if bit6 then
        binary_value = 1-binary_value
    end

    -- calculates the value coefficient for the given digit.
    -- this essentially indicates how much value the current digit
    -- contributes to the whole thing
    local coefficient = base^(i-1)

    -- turn a piece of the binary digit into the decimal part using the equation from before
    -- notice how we dont have to reverse the binary stream like we had to with tonumber
    -- this is because tonumber uses big endian and takes the first value as the largest one
    -- but if you look here the first value has the lowest i, which results in the first value
    -- actually having the lowest coefficient and thus small endian, no need for reversing!
    char_num = char_num + binary_value*coefficient
end
```
The same goes for the if statement implementation except we will hard code it for all the 6 values
```lua
local char_num = 0
char_num = char_num + char[1] * 2^(1-1)
char_num = char_num + char[2] * 2^(2-1)
char_num = char_num + char[3] * 2^(3-1)
char_num = char_num + char[4] * 2^(4-1)
char_num = char_num + char[5] * 2^(5-1)
char_num = char_num + char[6] * 2^(6-1)
```
This can be further simplified by precalculating the coefficients
```lua
local char_num = 0
char_num = char_num + char[1] * 1
char_num = char_num + char[2] * 2
char_num = char_num + char[3] * 4
char_num = char_num + char[4] * 8
char_num = char_num + char[5] * 16
char_num = char_num + char[6] * 32
```
We can also easily get rid of the multiplication by 1 by directly asigning char[2] to char_num
```lua
local char_num = char[1]
char_num = char_num + char[2] * 2
char_num = char_num + char[3] * 4
char_num = char_num + char[4] * 8
char_num = char_num + char[5] * 16
char_num = char_num + char[6] * 32
```

The rest of the code will be essentially the same as right now we got to our char number, all we need is to offset it by 128 and look it up into the charset

###### example implementation
```lua
-- character data
local char = {
    1,1,
    1,0,
    1,1
}

local bit6 = char[6] == 1

-- flips the colors of foreground and background to correct for
-- the inversion of the character
if bit6 then
    local fg = term.getTextColor()
    local bg = term.getBackgroundColor()

    term.setTextColor(bg)
    term.setBackgroundColor(fg)
end

local char_num = 0
local base = 2
for i=1,6 do
    -- grab binary number from the char data array (this is why making it a 2D array would make it a pain)
    local binary_value = char[i]

    -- inverts the bit if the sixth bit is enabled
    -- this is equivalent to our bitstream inversion from before
    if bit6 then
        binary_value = 1-binary_value
    end

    -- calculates the value coefficient for the given digit.
    -- this essentially indicates how much value the current digit
    -- contributes to the whole thing
    local coefficient = base^(i-1)

    -- turn a piece of the binary digit into the decimal part using the equation from before
    -- notice how we dont have to reverse the binary stream like we had to with tonumber
    -- this is because tonumber uses big endian and takes the first value as the largest one
    -- but if you look here the first value has the lowest i, which results in the first value
    -- actually having the lowest coefficient and thus small endian, no need for reversing!
    char_num = char_num + binary_value*coefficient
end

-- calculate the position in the actual charset using an offset
local char_index = char_num + 128

-- moves cursor pos to not have character touch edges of the screen
term.setCursorPos(2,2)

-- get the character string from the number and display it
print(string.char(char_index))
```
And of course, version with the if statement binary conversion, since thats what we are going to be using from now on for the sake of efficiency
```lua
-- character data
local char = {
    1,1,
    1,0,
    1,1
}

local bit6 = char[6] == 1

if bit6 then
    local fg = term.getTextColor()
    local bg = term.getBackgroundColor()

    term.setTextColor(bg)
    term.setBackgroundColor(fg)
end

-- The binary conversion and flipping bit when bit6 is present is gonna be handled a bit differently
-- instead of inverting the values when bit6 is present like this
--[[
local char_num = (bit6 and 1-char[1] or char[1])
char_num = char_num + (bit6 and 1-char[2] or char[2]) * 2
char_num = char_num + (bit6 and 1-char[3] or char[3]) * 4
char_num = char_num + (bit6 and 1-char[4] or char[4]) * 8
char_num = char_num + (bit6 and 1-char[5] or char[5]) * 16
char_num = char_num + (bit6 and 1-char[6] or char[6]) * 32
]]
-- lets rather take a look at a truth table for how these values change
-- this truth table will have 2 values, bit and the sixth bith of the texel (int) and one output.
-- so our table will have 4 (2^2) possible states,
-- sixth;bit;result ((sixth == 1) and 1-bit or bit)
-- 0     0   (false and 1-0 or 0) = 0
-- 0     1   (false and 1-1 or 1) = 1
-- 1     0   (true  and 1-0 or 0) = 1
-- 1     1   (true  and 1-1 or 1) = 0
-- you may notice that this is essentially an xnor
-- but thats not the most important thing, the most important fact for us is that
-- the value is only !0 when the values are different, this along with the fact
-- that i add a value multiplied by this number to char_num means that
-- i dont have to add anything at all when the values are same, as when they are the same
-- it guarantees addition of a 0.
-- Its also important to note that before we multiplied the coefficient by the bit value
-- which automatically caused a 0 addition, instead i will just use some if statements
-- i also dont have to add the sixth bit at all as its always equal to itself and thus will
-- always result in a 0 addition. I will also replace the charset shift of 128 by
-- just inicializing char_num at that value and thus have it be shifted since the start
-- Here is a simple implementation
local char_num = 128
if char[1] ~= char[6] then char_num = char_num + 1  end
if char[2] ~= char[6] then char_num = char_num + 2  end
if char[3] ~= char[6] then char_num = char_num + 4  end
if char[4] ~= char[6] then char_num = char_num + 8  end
if char[5] ~= char[6] then char_num = char_num + 16 end

-- no actual addition needed cause offset is added at char_num's definition
local char_index = char_num + 0

term.setCursorPos(2,2)

print(string.char(char_index))
```

#### Color handling
The entirety of texel color handling lies in a few techniques.
It mostly boils down to quantization,mapping and throwing data out!

##### Issues with color handling in texels
The main issue you will encounter when trying to process texel in color is the fact that each character (2x3 pixels) can only technically have 2 colors as you can only control the background and foreground color, while each character can have up to 6 different colors to it. How do you then pick the the bg and fg color along with the symbol? Turns out the only way to handle this is to discart some colors but that doesnt mean you cant get smart about how you deal with the positions of the discarted colors and picking the two colors to keep.

##### Making a bitstream out of colors
As you already know you need some sort of a [bitstream](#connection-of-binary-and-texels) or a list of ones and zeroes to calculate which drawing character you will want to use, previously every time ive used colors in any examples i just converted them to the bitstream by hand but we need to program something to do that for us as we wont be sitting there calculating this stuff by hand obviously

Here we will have an ideal scenario where we will only have 2 colors and thus we dont have to throw any data out and we can just process as is.
All of this can be just handled using value mapping.

Specific example:
```yml
white blue
blue white
white blue
```

Now to map it we will need a mapping list which we will explain how to create in later section which talks about quantization.
For now lets just take this list

|key    |   value   |
|---	|--------	|
| white | 0       	|
| blue 	| 1     	|

**note that with this system 1 will always refer to the fg and 0 to the bg**, this is very important to know if you want to actually do colored rendering as we will be using term.blit later on!

###### example implementation
This can just be a lookup table, to show this i will make a simple implemention based on [code from before](#table-implementation)
```lua
local char = {
    "white","blue",
    "blue" ,"white",
    "white","blue"
}

-- define the list that will allow me to map the color codes onto the fg (1) and bg (0)
local mapping_lookup = {
    ["white"] = 1,
    ["blue"]  = 0
}

-- apply the mapping iteratively to the list
for i=1,#char do
    char[i] = mapping_lookup[char[i]]
end

term.setTextColor(colors.white)
term.setBackgroundColor(colors.blue)

local bit6 = char[6] == 1

if bit6 then
    local fg = term.getTextColor()
    local bg = term.getBackgroundColor()

    term.setTextColor(bg)
    term.setBackgroundColor(fg)
end

local char_num = 0
local base = 2
for i=1,6 do
    local binary_value = char[i]

    if bit6 then binary_value = 1-binary_value end

    char_num = char_num + binary_value*2^(i-1)
end

local char_index = char_num + 128
term.setCursorPos(2,2)

print(string.char(char_index))
```
feel free to play around with the char list to see that this really does work!

[[
First we need to make some sort of a list to be used for the value mapping, this simply consist of us making a list which defines which color maps to 1 or a 0.
Here we can easily do it by iterating the list until we find 2 colors and every time we find a new color we can asign a 0 or a 1 to it depending on which one comes first.
Like this we iterate

`index1 -> white` and we asign a 0 for example (the order doesnt actually matter)

`index2 -> blue` and now we got our second unique color so we can stop
]]

##### Simple color processing
Slightly more advanced color processint techniques, this function will be able to handle up up to 6 different color on its input and do some simple estimation for which character it should choose

It will mostly rely on a few things
- finding the two most common colors
- changing rest of the colors to one of the two common colors (quantization)
- mapping into a bitstream and drawing (mapping)
- terminal color settings and drawing

I will also put the code into an actual function as we will be referring to it later on.

###### Finding the most common colors
Lets start off by defining our character as a 1D list of colors
```lua
local char = {
    colors.blue,colors.red,
    colors.green,colors.blue,
    colors.blue,colors.red
}
```
Now lets create a lookup with all of the colors present in the list
```lua
local color_lookup = {}
for i=1,#char do
    local color = char[i]
    color_lookup[color] = true
end
```
Since we want the color count and not just if its present or not (since we will later want to sort by the count) we will store a number instead of just a boolean for each color
```lua
local color_lookup = {}
for i=1,#char do
    local color = char[i]

    -- check for colors existence to prevent arithmetic on nil
    if color_lookup[color] then
        color_lookup[color] = color_lookup[color] + 1
    else
        color_lookup[color] = 1
    end
end
```
To sort the table i will use table.sort, the only issue with that is that the list needs to be ordered from 1-n with no holes, the list ive made here obviously isnt that since its indexed by the color which is in the `2^n -1 < n < 16` range, so there will always be holes and its definitely not gonna be in order. To fix that we can just convert convert the color_lookup to into such a list.
```lua
local sortable_colors = {}
for k,v in pairs(color_lookup) do
    local color_data = {
        color = k,
        count = v
    }

    sortable_colors[#sortable_colors+1] = color_data
end
```
Now to just sort it using table.sort and simple function which will make the values with the highest count be at the lowest index
```lua
table.sort(sortable_colors,function(a,b)
    return a.count > b.count
end)
```
The final code for this will be
```lua
local char = {
    colors.blue,colors.red,
    colors.green,colors.blue,
    colors.blue,colors.red
}

local color_lookup = {}

for i=1,#char do
    local color = char[i]

    if color_lookup[color] then
        color_lookup[color] = color_lookup[color] + 1
    else
        color_lookup[color] = 1
    end
end

local sortable_colors = {}
for k,v in pairs(color_lookup) do
    local color_data = {
        color = k,
        count = v
    }

    sortable_colors[#sortable_colors+1] = color_data
end

table.sort(sortable_colors,function(a,b)
    return a.count > b.count
end)
```

###### Quantization and mapping
The next two steps can actually be handled in one step.
As we can both turn the colors into a bitstream and map other colors to 2 most common ones at the same time

Lets start off by iterating all of the colors in the character like so, im going to be going off from the code above
```lua
for i=1,6 do
    local subpixel_color = char[i]
end
```
Now to form the stream we can check if the color is either one of the most common colors
and then asign it either a 1 or a 0 to the bitstream.

I am gonna take the sortable_colors list from the previous section
```lua
local stream = {}
for i=1,6 do
    local subpixel_color = char[i]

    if subpixel_color == sortable_colors[1].color then
        stream[i] = 1
    elseif subpixel_color == sortable_colors[2].color then
        stream[i] = 0
    end
end
```
The last part left to handle is when find a color which is not among the 2 most common ones.
There is really no right or wrong way to do this as its all just estimation after all

Here i will just use super simple method which will result in a dither-like effect. I will just make a table which will
tell me which one of the 2 most common colors to sample depending on the texel sub-pixel index

Since i want a pattern effect like this
```lua
10
01
10
```
The lookup will look something like this
```lua
local sample_lookup = {
    1,2,
    2,1,
    1,2
}
```
Considering we translate the sortable colors to 1s and 0s anyway we can just turn this into a 1 and 0 list
(essentially preprocessing the mapping)
```lua
local sample_lookup = {
    1,0,
    0,1,
    1,0
}
```
Now lastly i will integrate this into the existing code, using `i` for the chracter index
```lua
local stream = {}
for i=1,6 do
    local subpixel_color = char[i]

    if subpixel_color == sortable_colors[1].color then
        stream[i] = 1
    elseif subpixel_color == sortable_colors[2].color then
        stream[i] = 0
    else
        stream[i] = sample_lookup[i]
    end
end
```
###### terminal configuration
To have this character properly render we will have to set the foreground and background color accordingly depending on the
2 most common colors.

In our bitstream configuration `1` reffers to a foreground color reference and `0` to a background color reference.
Given our current code `sortable_colors[1]` has to be the fg and `sortable_colors[2]` has to be the background color.

Also dont forget that you need to swap these two to correct for the bitstream flip if the sixth bit is enabled.
This could be done with something like this
```lua
if stream[6] == 0 then
    term.setTextColor      (sortable_colors[1].color)
    term.setBackgroundColor(sortable_colors[2].color)
elseif stream[6] == 1 then
    term.setTextColor      (sortable_colors[2].color)
    term.setBackgroundColor(sortable_colors[1].color)
end
```

###### example implementation
Here ive made a culmination of all the code above plus ive put it into a function so it can be used more easily

This should already be able to process a list of colors into a somewhat acceptable texel
```lua
local sample_lookup = {
    1,0,
    0,1,
    1,0
}

local function process_texel(colors)
    -- figuring out the 2 most common colors
    local color_lookup = {}

    for i=1,6 do
        local color = colors[i]

        if color_lookup[color] then
            color_lookup[color] = color_lookup[color] + 1
        else
            color_lookup[color] = 1
        end
    end

    local sortable_colors = {}
    for k,v in pairs(color_lookup) do
        local color_data = {
            color = k,
            count = v
        }

        sortable_colors[#sortable_colors+1] = color_data
    end

    table.sort(sortable_colors,function(a,b)
        return a.count > b.count
    end)

    -- bitstream generation from colors
    local stream = {}
    for i=1,6 do
        local subpixel_color = colors[i]

        if subpixel_color == sortable_colors[1].color then
            stream[i] = 1
        elseif subpixel_color == sortable_colors[2].color then
            stream[i] = 0
        else
            stream[i] = sample_lookup[i]
        end
    end

    -- terminal color setting
    if stream[6] == 0 then
        term.setTextColor      (sortable_colors[1].color)
        term.setBackgroundColor(sortable_colors[2].color)
    elseif stream[6] == 1 then
        term.setTextColor      (sortable_colors[2].color)
        term.setBackgroundColor(sortable_colors[1].color)
    end
W
    -- character generation from bitstream
    local char_num = 128
    if stream[1] ~= stream[6] then char_num = char_num + 1  end
    if stream[2] ~= stream[6] then char_num = char_num + 2  end
    if stream[3] ~= stream[6] then char_num = char_num + 4  end
    if stream[4] ~= stream[6] then char_num = char_num + 8  end
    if stream[5] ~= stream[6] then char_num = char_num + 16 end

    -- rendering to term
    term.setCursorPos(2,2)
    print(string.char(char_num))
end

local char = {
    colors.blue,colors.red,
    colors.green,colors.blue,
    colors.blue,colors.red
}

process_texel(char)
```
Well lets give this function a try on an actual image shall we.
Lets try to render the original computercraft charset with it
![CC charset rendered with texels](resources/charser_texel.png)
Or some oreos!
![oreos rendered with texels](resources/oreos.png)

###### Complex quantization
Not much is actually gonna change here. The main difference is how we will sample colors for pixels which are not among the 2 most common colors

Before i just used a simple pattern which made a dithering like effect
```lua
local sample_lookup = {
    1,0,
    0,1,
    1,0
}

local stream = {}
for i=1,6 do
    local subpixel_color = colors[i]

    if subpixel_color == sortable_colors[1].color then
        stream[i] = 1
    elseif subpixel_color == sortable_colors[2].color then
        stream[i] = 0
    else
        stream[i] = sample_lookup[i]
    end
end
```
Instead of doing it like this i will try to handle it on a distance based approach. When i find a color which
Is nowhere to be found in the 2 most colors and thus must be remapped to a different one i will check that colors
neighbors in a specific order.

I will mostly follow 2 rules for this.
- closest pixels, finding the closest pixels to the current one, if no suitable color is found then repeating that for those neighboring pixels aswell
- clockwise iteration: when we get the 3 (or less) pixel neighbors of the current one we will iterate them in a clockwise order

Here you can see these rules being applied to two texels, one with the `i1` sampled and other with `i4` being sampled

![Color sampling visual](resources/sampling_visual.png)

We could technically generate this for all positions using euclidean distance and some recursive algorithm but thats painful, and considering there
is just 6 options (possible sample points) each with 5 values (5 alternate sample points) its probably gonna be the best idea to hardcode this

If you look at the example image where is started at `C1` you can see that it essentially just spreads to its neighbors.
So your original sample point is always gonna be surrounded by `A1` and all `A1` sample points are gonna be surrounded by `A2` sample points.
This slowly expands over the entirety of the texel (max of 3 search levels, aka A3).

We are gonna be looking for one of the 2 most commons in the texel and specifically prefer ones with the lowest search level (closest to the original sample points)
And also if there are for example 2 of the most common colors right in the same search level we will search it in a clockwise manner
To always have a predictable outcome, this clockwise type of search would be pretty hard to implement so as mentioned before we will just hardcode all of this

Lets start off by making the sampling lookup for our first texel pixel (C1), you can refer to the first texel in the visual above. What im gonna be mostly interested in is
the B (iteration index) component of the subpixel, as thats what will set its weight/priority in the sampling process (the lower the more preferred it will be)

Note that i will go through the subpixels in order (given by the iter index component) and write down its subpixel index, the actual iter index is not
written down anywhere and purely used for figuring out the subpixel indices.

```lua
local sampling_lookup = {
    -- [subpixel index] = {sample subpixel index from lowest iter index to highest}
    [1] = {2,3,4,5,6}
}
```

Okay now lets do it for the second texel in the visual (the one where `C4` is being sampled)
```lua
local sampling_lookup = {
    -- [subpixel index] = {sample subpixel index from lowest iter index to highest}
    [4] = {2,6,3,5,1}
}
```
Oh well all thats left is to do it for all the subpixels
```lua
local sampling_lookup = {
    [1] = {2,3,4,5,6},
    [2] = {4,1,6,3,5},
    [3] = {1,4,5,2,6},
    [4] = {2,6,3,5,1},
    [5] = {3,6,1,4,2},
    [6] = {4,5,2,3,1}
}
```
That was rather straight forward.
Now all thats left is to upgrade our original sampler
```lua
else
    stream[i] = old_sample_lookup[i]
end
```
Instead of doing this we will look up the current subpixel in the sampling_lookup
```lua
else
    local sample_points = sampling_lookup[i]
end
```
Then we iterate over all the sampling points until we find a color which is one of the 2 most common character colors (meaning we can actually use it during rendering).
To do this you will have to up the actual color at that position in the character
```lua
else
    local sample_points = sampling_lookup[i]
    for sample_index=1,5 do
        local sample_subpixel_index = sample_points[sample_index]
        local sample_color          = colors[sample_subpixel_index]

        local common_1 = sample_color == sortable_colors[1].color
        local common_2 = sample_color == sortable_colors[2].color

        if common_1 or common_2 then
            print("Found suitable color!")

            -- stop looking for colors once one has been alreay found
            break
        end
    end
end
```
The last thing that needs to be done is actually writing either a 1 or a zero into the bitstream depending on which one
of the two common colors it actually is.

Since the original code considers the most **number 1** most common color to be a 1 in the bitstream and the **second most common** one
to be a 0 zero in the bitstream (because of this piece of code)
```lua
if subpixel_color == sortable_colors[1].color then
    stream[i] = 1
elseif subpixel_color == sortable_colors[2].color then
    stream[i] = 0
else
```
We can easily go off of that and say that if the `sample_color` is equal to the most common color (`sortable_colors[1].color`) also called `common_1` then
we should write a 1 into the bitstream, else we write a 0.
Heres how that would be done
```lua
else
    local sample_points = sampling_lookup[i]
    for sample_index=1,5 do
        local sample_subpixel_index = sample_points[sample_index]
        local sample_color          = colors[sample_subpixel_index]

        local common_1 = sample_color == sortable_colors[1].color
        local common_2 = sample_color == sortable_colors[2].color

        if common_1 or common_2 then
            -- this can also be implemented with an if statement but i prefer the ternary version
            -- here is the if statement version for those who are not familiar with ternary anyway
            -- if common_1 then
            --     stream[i] = 1
            -- else
            --     stream[i] = 0
            -- end

            stream[i] = common_1 and 1 or 0

            break
        end
    end
end
```

Now we just have to put it all together!
###### example implementation
```lua
-- sampling lookup definition
local sampling_lookup = {
    [1] = {2,3,4,5,6},
    [2] = {4,1,6,3,5},
    [3] = {1,4,5,2,6},
    [4] = {2,6,3,5,1},
    [5] = {3,6,1,4,2},
    [6] = {4,5,2,3,1}
}

local function process_texel(colors)
    -- figuring out the 2 most common colors
    local color_lookup = {}

    for i=1,6 do
        local color = colors[i]

        if color_lookup[color] then
            color_lookup[color] = color_lookup[color] + 1
        else
            color_lookup[color] = 1
        end
    end

    local sortable_colors = {}
    for k,v in pairs(color_lookup) do
        local color_data = {
            color = k,
            count = v
        }

        sortable_colors[#sortable_colors+1] = color_data
    end

    table.sort(sortable_colors,function(a,b)
        return a.count > b.count
    end)

    -- bitstream generation from colors
    local stream = {}
    for i=1,6 do
        local subpixel_color = colors[i]

        if subpixel_color == sortable_colors[1].color then
            stream[i] = 1
        elseif subpixel_color == sortable_colors[2].color then
            stream[i] = 0
        else
            -- more advanced missing color sampling
            local sample_points = sampling_lookup[i]
            for sample_index=1,5 do
                local sample_subpixel_index = sample_points[sample_index]
                local sample_color          = colors[sample_subpixel_index]

                local common_1 = sample_color == sortable_colors[1].color
                local common_2 = sample_color == sortable_colors[2].color

                if common_1 or common_2 then
                    stream[i] = common_1 and 1 or 0

                    break
                end
            end
        end
    end

    -- terminal color setting
    if stream[6] == 0 then
        term.setTextColor      (sortable_colors[1].color)
        term.setBackgroundColor(sortable_colors[2].color)
    elseif stream[6] == 1 then
        term.setTextColor      (sortable_colors[2].color)
        term.setBackgroundColor(sortable_colors[1].color)
    end

    -- character generation from bitstream
    local char_num = 128
    if stream[1] ~= stream[6] then char_num = char_num + 1  end
    if stream[2] ~= stream[6] then char_num = char_num + 2  end
    if stream[3] ~= stream[6] then char_num = char_num + 4  end
    if stream[4] ~= stream[6] then char_num = char_num + 8  end
    if stream[5] ~= stream[6] then char_num = char_num + 16 end

    -- rendering to term
    term.setCursorPos(2,2)
    print(string.char(char_num))
end

local char = {
    colors.blue,colors.red,
    colors.green,colors.blue,
    colors.blue,colors.red
}

process_texel(char)
```
Now lets again give this function a try with some images

![Texel rendered cat (advanced)](resources/cat_texel_advanced.png)

Now lets try it on a larger screen

![Texel rendered cat (advanced & large)](resources/cat_texel_advanced_large.png)

And of course some obligatory oreos

![Texel rendered oreo (advanced)](resources/oreo_texel_advanced.png)

Now it can be kind hard to spot the differences from the sampler from before but close up there is actually a lot less noise!

![Difference of noiser leves from the 2 samplers](resources/sampler_difference.png)

If you gotten this far congrats! you are now fully familiar with how to work with drawing characters!
The function we've built here is decently fast and should scale well aswell as being really readable.

However there is still a ton to improve! In the next sections i will show some methods which will allow you to
make this up to 6x faster! and even more extreme in some cases.



# credit
- [**ShadyDuck**](https://github.com/exerro/) - helping with understanding of graphics concepts and certain optimizations
- [**HaruCoded**](https://github.com/Kariaro) - idea and implementation of using color patterns for handling texel color quantization

###### written by [**9551Dev**](https://github.com/9551-dev)
###### part of the [**ComputerCraft Graphics Research**](https://github.com/ComputercraftGraphics) project
###### licensed under the [**MIT LICENSE**](https://mit-license.org/)