[PATCH 3/3] winex11: Use TINN algorithm to speed up
colour lookups.
Jacek Caban
jacek at codeweavers.com
Sat May 5 13:24:45 CDT 2007
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
More information about the wine-devel
mailing list