[PATCH 3/3] winex11: Use TINN algorithm to speed up colour lookups.

[Jacek Caban]

Vitaly Budovski wrote:
> Vitaliy Margolen wrote:
>> Vitaly Budovski wrote:
>>  
>>> Vitaliy Margolen wrote:
>>>     Thanks for the tip. Unfortunately in this instance it will not
>>> work as I
>>> do in fact query more than a < b. See the nearest function in patch 2.
>>>     
>> And what is so special about subtracting one from the other?
>>
>>   
>
> A lot actually. As an example with squared distances: a^2 - b^2 <= c^2.
> If a^2 = 27, b^2 = 16, c^2 = 9, then 27 - 16 <= 9 is false. However,
> if we use the square root in distance calculations, sqrt(27) - 4 <= 3
> is true. As you can see, we get entirely different results.
>

I didn't really read your code, but answering on above, it's still
possible in this case to avoid sqrt. A bit of math:
You want to check if a-b <= c. Assuming a>=b (otherwise it's always
true), it's equal to:
(a-b)^2 <= c^2    is equal to
a^2 + b^2 - 2ab <= c^2    is equal to
a^2 + b^2 - c^2 <= 2ab    is equal to  (assuming a^2 + b^2 - c^2 >= 0)
(a^2 + b^2 - c^2)^2 <= (2ab)^2   is equal to
(a^2 + b^2 - c^2)^2 <= 4 a^2 b^2
so if you store a^2, b^2 and c^2 instead of a, b, c you may compare it
using a few integer operations. In C it would look like:

BOOL abccmp(int a2, int b2, int c2) {
    int tmp = a2+b2-c2;
    return a2 <= b2 || tmp <= 0 || tmp*tmp <= 4*a2*b2;
}

It may be not so easy in a real code, but in most cases it should be
possible to use such tricks.


Jacek