neilobremski
Experienced Member
These wonderful digital processing units of ours are, at their heart, very fast binary adders. There may be a SUBtract instruction but this is the same as adding the two's complement of a number. [SUP][1][/SUP] Knowing this is important when I'm mixing signed and unsigned numbers; I must be discriminate.
In the current case, I'm storing texture coordinates as whole byte values which I will then interpret as fixed point. To clarify this a little, I'll explain the concepts with nibbles instead of bytes because we can express these in a single hex digit (and you can do the binary math with your two hands, using one thumb as the carry).
Assume that my texture is a tiny 4x4 grid which means the maximum coordinates are 0,0 in the top left and 3,3 in the bottom right. Further, I am using a nibble to represent these in a 2:2 fixed point. Rather than going from 0,0 to C,C though I want these to extend to F,F which is the maximum a nibble can hold. I can then chop off the lower 2 bits to see what the texture coordinate is.
Now if I am interpolating in a positive direction there doesn't seem to be any issue at all. I can simply divide the difference of two texture coordinates by the length of the span they're crossing. My texture coordinates are always absolutes, either 0 or F, so the difference will always be either 0 or F too.
But the length is variable: this is how much I'm shrinking or stretching the texture. In my example usage, I can only stretch to a length of 16 or weird shit will happen. Even though the length is 16, the divisor will only be 15 because I am counting steps not spots. This is an important distinction. It is entirely possible to use spots instead of steps but then you have a lot of add-one's. Anyway, I digress ...
So if I am interpolating from 0 to F over 15 then the delta is 1 which is very simple. This is a fractional value in my 2:2 fixed point which will cause the texture coordinate to move ahead once every 4 steps. That's perfect! But of course perfect divisions rarely happen. What happens if the division is not perfect.
If I interpolate 0 to F over ... 4. This can be confusing at first because it seems as though 4 will divide evenly due to using a nibble (16 possible values) but it actually means there are 5 pixels and dividing F (15) by 4 is not even. You can see this is true because shifting to the right twice to achieve a divide-by-four will drop set bits. The result is 3. So this would show:
This repeats the first texel twice in order to stretch slightly to fit.
What does this have to do with subtraction? Well, what if I am interpolating from F to 0 instead of 0 to F? Right away you're going to run into problems. Check it out:
To understand why, I have to go back to two's complement and the fact that the subtraction really just adds that version of the number. The two's complement of 1111 is its opposite (0000) plus 1 which is simply 0001. Adding anything to zero results in itself so I am left with 1. Doh!
Yet you can check that a subtraction flipped the bits around like this by checking the carry flag. So firstly, I can tell without issuing a CMP (compare) that the interpolation is going to be with a negative delta. Next I just need that negative delta. It may seem impossible but I can achieve negative deltas by using the same two's complement concepts on unsigned numbers which cause their bits to roll over. Let me explain with an example ...
Let's say you want to subtract 7 from F and you expect the result to be 8. The two's complement of 7 is 9 (1001) and adding this to F (1111) will indeed come out to 8 (1000). Obviously there is a carry and working in a whole byte you'll end up with 0x18 (remember in my theoretical examples, I am assuming the nibble is the whole integer). Adding that bigger number, the 9 which is the two's complement of 7, rolls over the bits like a score counter that has a fixed number of dials.
Back to the interpolation, the first step is to get the two's complement of the negative value, the result of the subtraction. The two's complement of 0001 (1) is 1111 (F) which is totally expected since I am only ever going to see 0 or F. Now the only extra step is to perform the divide as usual but then get the two's complement of the result using the NEG instruction.
The two's complement of 3 (0011) is (1101) or D (13). Let's see how this plays out ...
Well lookie there! The same stretching occurs but texels start at coordinate 3 and end up at 0 instead of the other way around. Success!
Footnotes:
[SUP][1][/SUP]. The two's complement of a number is its binary opposite plus 1. For example, the two's complement of the nibble 0111 (7) is 1001, because the opposite is 1000 and 1 is added to that.
In the current case, I'm storing texture coordinates as whole byte values which I will then interpret as fixed point. To clarify this a little, I'll explain the concepts with nibbles instead of bytes because we can express these in a single hex digit (and you can do the binary math with your two hands, using one thumb as the carry).
Assume that my texture is a tiny 4x4 grid which means the maximum coordinates are 0,0 in the top left and 3,3 in the bottom right. Further, I am using a nibble to represent these in a 2:2 fixed point. Rather than going from 0,0 to C,C though I want these to extend to F,F which is the maximum a nibble can hold. I can then chop off the lower 2 bits to see what the texture coordinate is.
Now if I am interpolating in a positive direction there doesn't seem to be any issue at all. I can simply divide the difference of two texture coordinates by the length of the span they're crossing. My texture coordinates are always absolutes, either 0 or F, so the difference will always be either 0 or F too.
But the length is variable: this is how much I'm shrinking or stretching the texture. In my example usage, I can only stretch to a length of 16 or weird shit will happen. Even though the length is 16, the divisor will only be 15 because I am counting steps not spots. This is an important distinction. It is entirely possible to use spots instead of steps but then you have a lot of add-one's. Anyway, I digress ...
So if I am interpolating from 0 to F over 15 then the delta is 1 which is very simple. This is a fractional value in my 2:2 fixed point which will cause the texture coordinate to move ahead once every 4 steps. That's perfect! But of course perfect divisions rarely happen. What happens if the division is not perfect.
If I interpolate 0 to F over ... 4. This can be confusing at first because it seems as though 4 will divide evenly due to using a nibble (16 possible values) but it actually means there are 5 pixels and dividing F (15) by 4 is not even. You can see this is true because shifting to the right twice to achieve a divide-by-four will drop set bits. The result is 3. So this would show:
- T=0 (0 + 3)
- T=0 (3 + 3)
- T=1 (6 + 3)
- T=2 (9 + 3)
- T=3 (C)
This repeats the first texel twice in order to stretch slightly to fit.
What does this have to do with subtraction? Well, what if I am interpolating from F to 0 instead of 0 to F? Right away you're going to run into problems. Check it out:
0 - F = 1
To understand why, I have to go back to two's complement and the fact that the subtraction really just adds that version of the number. The two's complement of 1111 is its opposite (0000) plus 1 which is simply 0001. Adding anything to zero results in itself so I am left with 1. Doh!
Yet you can check that a subtraction flipped the bits around like this by checking the carry flag. So firstly, I can tell without issuing a CMP (compare) that the interpolation is going to be with a negative delta. Next I just need that negative delta. It may seem impossible but I can achieve negative deltas by using the same two's complement concepts on unsigned numbers which cause their bits to roll over. Let me explain with an example ...
Let's say you want to subtract 7 from F and you expect the result to be 8. The two's complement of 7 is 9 (1001) and adding this to F (1111) will indeed come out to 8 (1000). Obviously there is a carry and working in a whole byte you'll end up with 0x18 (remember in my theoretical examples, I am assuming the nibble is the whole integer). Adding that bigger number, the 9 which is the two's complement of 7, rolls over the bits like a score counter that has a fixed number of dials.
Back to the interpolation, the first step is to get the two's complement of the negative value, the result of the subtraction. The two's complement of 0001 (1) is 1111 (F) which is totally expected since I am only ever going to see 0 or F. Now the only extra step is to perform the divide as usual but then get the two's complement of the result using the NEG instruction.
The two's complement of 3 (0011) is (1101) or D (13). Let's see how this plays out ...
- T=3 (F + D)
- T=3 (C + D)
- T=2 (9 + D)
- T=1 (6 + D)
- T=0 (3)
Well lookie there! The same stretching occurs but texels start at coordinate 3 and end up at 0 instead of the other way around. Success!
Footnotes:
[SUP][1][/SUP]. The two's complement of a number is its binary opposite plus 1. For example, the two's complement of the nibble 0111 (7) is 1001, because the opposite is 1000 and 1 is added to that.