Смешение цветов, быстрее можно ли?

← →
DVM © (2008-01-14 12:20) [0]

Обратите внимание, что степень смешения должна быть типа Single - так продиктовано задачей где используется смешение.

function MixerColors(FromColor, ToColor: TColor; Rate: Single): TColor; var r1, g1, b1: byte; r2, g2, b2: byte; r3, g3, b3: byte; r: Single; ra, rb: byte; begin RA := round(Rate * 255); RB := 255 - RA; //r1 := lo(FromColor); g1 := lo(FromColor shr 8); b1 := lo(FromColor shr 16); //r2 := lo(ToColor); g2 := lo(ToColor shr 8); b2 := lo(ToColor shr 16); r3 := (Lo(FromColor) * RA + Lo(ToColor) * RB) shr 8; g3 := (g1 * RA + g2 * RB) shr 8; b3 := (b1 * RA + b2 * RB) shr 8; Result := (r3 or (g3 shl 8) or (b3 shl 16)); end;

← →
Сергей М. © (2008-01-14 12:24) [1]

А в чем, собссно, тормоза ?

← →
DVM © (2008-01-14 12:27) [2]

> Сергей М. © (14.01.08 12:24) [1]

не, тормозов нет, просто спортивный интерес, можно ли еще быстрее даже на ASM?

← →
Rouse_ © (2008-01-14 12:29) [3]

Сколько вызовов данной функции планируется в секунду?

← →
oxffff © (2008-01-14 12:31) [4]

> Rouse_ © (14.01.08 12:29) [3]

Inline?

← →
DVM © (2008-01-14 12:32) [5]

> Rouse_ © (14.01.08 12:29) [3]

Сложно сказать. Но предполагается ее использовать для антиалиазинга линий и фигур и эффектов полупрозрачности.

← →
homm © (2008-01-14 12:33) [6]

А чего g1, b1 не подставил в выражение?

← →
homm © (2008-01-14 12:35) [7]

> [0] DVM © (14.01.08 12:20)
> RA := round(Rate * 255);

Вернет 255 для значений от 254,5 до 255, а 254 вернет для значений от 253,5 до 254,5. Не складно.

← →
DVM © (2008-01-14 12:36) [8]

> А чего g1, b1 не подставил в выражение?

опс, забыл. Подставил. Скорость немноговозросла.

← →
Сергей М. © (2008-01-14 12:37) [9]

> DVM © (14.01.08 12:32) [5]

> предполагается ее использовать для антиалиазинга линий и
> фигур и эффектов полупрозрачности

Значит, вероятно, предполагается, что один и тот же Rate будет использован при вызове ф-ции для всех точек смешиваемых изображений ?

Тогда зачем всякий раз при вызове ф-ции вычислять RA и RB ? Вполне достаточно сделать это всего один раз.

← →
Rouse_ © (2008-01-14 12:37) [10]

Вот так убрать можно лишние действия:

function MixerColors1(FromColor, ToColor: TColor; Rate: Single): TColor; var g1, b1: byte; g2, b2: byte; r3, g3, b3: byte; ra, rb: byte; begin RA := round(Rate * 255); RB := 255 - RA; g1 := FromColor shr 8; b1 := FromColor shr 16; g2 := ToColor shr 8; b2 := ToColor shr 16; r3 := (Byte(FromColor) * RA + Byte(ToColor) * RB) shr 8; g3 := (g1 * RA + g2 * RB) shr 8; b3 := (b1 * RA + b2 * RB) shr 8; Result := (r3 or (g3 shl 8) or (b3 shl 16)); end;

← →
DVM © (2008-01-14 12:38) [11]

> Значит, вероятно, предполагается, что один и тот же Rate
> будет использован при вызове ф-ции для всех точек смешиваемых
> изображений ?

Для полупрозрачности - верно, но для краевого антиалиазинга нет - там все точки разные.

← →
homm © (2008-01-14 12:38) [12]

> [0] DVM © (14.01.08 12:20)

А теперь рассмотри вариант, когда Rate = 1.0
RA := round(Rate * 255); RB := 255 - RA;
RA = 255;
RB = 0;

g3 := (g1 * RA + g2 * RB) shr 8;
g3 := (g1 * 255 + 0) / 256;
g3<>g1, хотя Rate = 1.0

← →
DVM © (2008-01-14 12:43) [13]

> homm © (14.01.08 12:35) [7]

Да, я знаю. На это можно закрыть глаза. Все равно визуально неотличимо.

> Rouse_ © (14.01.08 12:37) [10]
> Вот так убрать можно лишние действия:

На скорость не повлияло

← →
Сергей М. © (2008-01-14 12:43) [14]

> DVM © (14.01.08 12:38) [11]

Значит нужны разные алгоритмы для тех или иных задач.
Стремление к универсальности алгоритма никогда еще не приводило к приросту его производительности.

← →
homm © (2008-01-14 12:44) [15]

> [13] DVM © (14.01.08 12:43)
> На это можно закрыть глаза. Все равно визуально неотличимо.

После ста наложений станет вполне отличимо.

← →
DVM © (2008-01-14 12:44) [16]

> А теперь рассмотри вариант, когда Rate = 1.0

для Rate = 1 будет отдельная добавка, там считать вообще не надо.

← →
homm © (2008-01-14 12:45) [17]

> [16] DVM © (14.01.08 12:44)
> для Rate = 1 будет отдельная добавка, там считать вообще
> не надо.

Блин, ну возьми Rate = 0,999. Результат будет не верен для любого значения, т.к. ты умнеожаешь на 255, а делишь на 256 всегда

← →
DVM © (2008-01-14 12:46) [18]

> После ста наложений станет вполне отличимо.

Другого ничего в голову не приходит мне что-то.

← →
homm © (2008-01-14 12:51) [19]

> [18] DVM © (14.01.08 12:46)
> Другого ничего в голову не приходит мне что-то.

RA := trunc(Rate * 257);

← →
homm © (2008-01-14 12:53) [20]

ra, rb: byte;

DWORD

← →
oxffff © (2008-01-14 12:56) [21]

> homm © (14.01.08 12:51) [19]
> > [18] DVM © (14.01.08 12:46)
> > Другого ничего в голову не приходит мне что-то.
>
> RA := trunc(Rate * 257);

А если rate=1 ?

← →
homm © (2008-01-14 12:59) [22]

> [21] oxffff © (14.01.08 12:56)
> А если rate=1 ?

Очевидно поправка,
либо через if, либо умножать на 256,999

← →
DVM © (2008-01-14 13:03) [23]

> homm © (14.01.08 12:51) [19]

> homm © (14.01.08 12:59) [22]

потеряем в скорости

← →
oxffff © (2008-01-14 13:05) [24]

> DVM © (14.01.08 13:03) [23]

Чего ты хочешь добиться?
Если тебе нужна скорость.
IMHO не изобретай велосипед. См. готовые реализации.
Если тебе нужна скорость, см. в сторону использования GPU,
в том числе и для расчетов.

← →
DVM © (2008-01-14 13:06) [25]

Пока что самый быстрый вариант таков (если не принимать в расчет недостаток, замеченный homm):

function MixerColors(FromColor, ToColor: TColor; Rate: Single): TColor; var ra, rb: byte; begin RA := round(Rate * 255); RB := 255 - RA; result := (((Lo(FromColor) * RA + Lo(ToColor) * RB) shr 8) or (((Lo(FromColor shr 8) * RA + Lo(ToColor shr 8) * RB) shr 8) shl 8) or (((Lo(FromColor shr 16) * RA + Lo(ToColor shr 16) * RB) shr 8) shl 16)); end;

224 микросекунды на 10000 повторов

← →
DVM © (2008-01-14 13:09) [26]

> oxffff © (14.01.08 13:05) [24]

> Чего ты хочешь добиться?
> Если тебе нужна скорость.
> IMHO не изобретай велосипед. См. готовые реализации.

Да я уже добился собственно чего хотел :) Что значит готовые реализации? Аппаратное ускорение? Все реализации, даже на ASM которые мне попались я уже обогнал.

> Если тебе нужна скорость, см. в сторону использования GPU,
>
> в том числе и для расчетов.

Я бы рад. Дело в том, что не у всех есть подходящий GPU

← →
homm © (2008-01-14 13:14) [27]

> Все реализации, даже на ASM которые мне попались я уже обогнал.

Сомневаюсь что есть много реализаций такого кривого подхода, в котором для каждого пикселя считается коэффициент, да еще и в виде процедуры.

> 224 микросекунды на 10000 повторов

Это около 58 смешиваний 1024х768. Кажется это число у меня было близко к тысячи.

← →
homm © (2008-01-14 13:15) [28]

> [27] homm © (14.01.08 13:14)
> Это около 58 смешиваний 1024х768.

в секунду

← →
oxffff © (2008-01-14 13:17) [29]

> Да я уже добился собственно чего хотел :) Что значит готовые
> реализации? Аппаратное ускорение? Все реализации, даже на
> ASM которые мне попались я уже обогнал.

Не скромно. :)

← →
Сергей М. © (2008-01-14 13:18) [30]

> DVM © (14.01.08 13:09) [26]

> не у всех есть подходящий GPU

Зато с весьма большой долей вероятности у этих всех есть CPU, поддерживающий MMX/XMM/SSE/SSE2

← →
DVM © (2008-01-14 13:22) [31]

> Сомневаюсь что есть много реализаций такого кривого подхода,
> в котором для каждого пикселя считается коэффициент, да
> еще и в виде процедуры.

Не много, но есть. Подход нет лучший - спору нет.

> Это около 58 смешиваний 1024х768. Кажется это число у меня
> было близко к тысячи.

Да, 57 с чем то. Ты смешивал что с чем? Битмапы в памяти? И как?

← →
DVM © (2008-01-14 13:24) [32]

> Сергей М. © (14.01.08 13:18) [30]

> Зато с весьма большой долей вероятности у этих всех есть
> CPU, поддерживающий MMX/XMM/SSE/SSE2

Я, к сожалению моему, не владею ASM в достаточной степени.

← →
Сергей М. © (2008-01-14 13:26) [33]

> DVM © (14.01.08 13:24) [32]

> не владею ASM в достаточной степени

Беда, конечно, но не так уж и велика.
Ничто не мешает воспользоваться чьей-либо готовой библиотечной реализацией, использующий тот или иной набор инструкций для достижения сабжа.

← →
homm © (2008-01-14 13:27) [34]

> [31] DVM © (14.01.08 13:22)

Слушай, а это не ты мне советовал глянуть в сторону Graphics32 (или что то похожее)? Вот теперь я советую глянуть на нее :)

← →
DVM © (2008-01-14 13:30) [35]

> Слушай, а это не ты мне советовал глянуть в сторону Graphics32

Не не я. Мы с тобой дискутировали как то по поводу FastDIB. :)

← →
homm © (2008-01-14 13:33) [36]

> [35] DVM © (14.01.08 13:30)
> Мы с тобой дискутировали как то по поводу FastDIB

Ну возможно я ее и имею ввиду (название не помню). Хоть обогнать мне ее ненамного удалось, но она более универсальна.

← →
Ketmar © (2008-01-14 14:26) [37]

таки присоединюсь: есть отличная Graphics32, где велосипеды уже написаны и отлажены.

← →
Dib@zol © (2008-01-14 15:37) [38]

function MCA(FromColor, ToColor: COLORREF; Rate: Byte): COLORREF;
asm
PUSH EBX;
PUSH ESI;
PUSH EDI;

MOV CH, CL;
SUB CH, 255;
NEG CH;

MOV ESI, EAX;
MOV EDI, EDX;
MUL CL;
XCHG EAX, EDX;
MUL CH;
ADD AX, DX;
SHR AX, 8;
MOV BL, AL;
ROR EBX, 8;

MOV EAX, ESI;
MOV EDX, EDI;
MOV AL, AH;
MUL CL;
XCHG EAX, EDX;
MOV AL, AH;
MUL CH;
ADD AX, DX;
SHR AX, 8;
MOV BL, AL;

MOV EAX, ESI;
SHR EAX, 16;
SHR EDI, 16;
MUL CL;
XCHG EAX, EDI;
MUL CH;
ADD EAX, EDI;
SHR AX, 8;
MOV BH, AL;

ROL EBX, 8;
MOV EAX, EBX;

POP EDI;
POP ESI;
POP EBX;
end;

Вот. Работает капельку быстрее. 350 мс за 10 миллионов проходов, тогда как сабжевая выдаёт 550 мс. Однако я оч сильно подозреваю, что тут можно обойтись только XOR-ом и битовыми масками. Пока что "масковый" метод даёт довольно приблизительные результаты, однако работает быстрее в 5 раз. Будем работать.

← →
Ketmar © (2008-01-14 15:41) [39]

всё-таки: а зачем? может, смотреть в сторону аппаратного ускорения, если уж так скорость важна? а то вот на 286 твой код тоже нерабочий…

← →
Dib@zol © (2008-01-14 16:01) [40]

Нет... увы :( Чем больше отличия Rate от половины, тем больше прут искажения :(

> всё-таки: а зачем? может, смотреть в сторону аппаратного
> ускорения, если уж так скорость важна? а то вот на 286 твой
> код тоже нерабочий…
Дыкъ! Спрошенож было: а можно ли быстрее? Я ответил: "В лоб" - можно, но ненамного. "В обход" - нельзя, ибо глюкаво. Хотя...
ЗЫ На 286-м вряд ли кто-то в здравом уме будет ставить и запускать хотя бы Win 3.11, а тем более уж 9х и далее.
ЗЗЫ Пойду Висту на х286 поставлю :D

← →
DVM © (2008-01-14 17:35) [41]

> всё-таки: а зачем? может, смотреть в сторону аппаратного
> ускорения, если уж так скорость важна?

Если кто-то возьмется написать с использованием MMX/SSE я не против :)

Немного о том, зачем мене все это понадобилось. Занялся изучением антиалиазинга (который бы не помешал мне в некотором подобии векторного редактора надо которым работаю). Поэтому возникла идея создать модуль с основными функциями рисования графических примитивов, но с антиалиазингом. Вот, собственно.

← →
homm © (2008-01-14 17:39) [42]

> [41] DVM © (14.01.08 17:35)
> Поэтому возникла идея создать модуль с основными функциями
> рисования графических примитивов, но с антиалиазингом.

Как доберешся до элипса с произвольной толщиной заливки границы, дай мне знать :)

← →
J_f_S (2008-01-14 17:48) [43]

Баян конечно, но курите алгоритмы, примененные в антигрейне. Антигрейн на сегодня - лучшая, самая качественная и быстрая графическая библиотека. Это факт.
http://antigrain.com/
Стиль чисто плюсовый, все на шаблонах, но алгоритмы ситаются очень хорошо.

← →
J_f_S (2008-01-14 17:49) [44]

ситаются = читаются. :(

← →
homm © (2008-01-14 17:59) [45]

> [43] J_f_S (14.01.08 17:48)

Это что-то! Спасибо за ссылку.

> Если кто-то возьмется написать с использованием MMX/SSE
> я не против :)

Объясни алгоритм смешивания на пальцах.. А то мне сейчас думать влом над кодом в [0].
SSE владею, если пойму, напишу с использованием SSE.

> [46] @!!ex © (14.01.08 18:06)
> Объясни алгоритм смешивания на пальцах.. А то мне сейчас
> думать влом над кодом в [0].

Он проще чем то можно представить :)

> @!!ex © (14.01.08 18:06) [46]

примерно так:
function BlendColors(const Color1, Color2: TColor; Amount: Extended): TColor; Var R,R2,G,G2,B,B2: Integer; win1, win2: Integer; begin win1 := ColorToRGB(color1); win2 := ColorToRGB(color2); R := GetRValue(win1); G := GetGValue(win1); B := GetBValue(win1); R2 := GetRValue(win2); G2 := GetGValue(win2); B2 := GetBValue(win2); b2:=round((1-amount)*b+amount*b2); g2:=round((1-amount)*g+amount*g2); r2:=round((1-amount)*r+amount*r2); if R2 < 0 then R2 := 0; if G2 < 0 then G2 := 0; if B2 < 0 then B2 := 0; if R2 > 255 then R2 := r; if G2 > 255 then G2 := r; if B2 > 255 then B2 := r; Result := TColor(RGB(R2, G2, B2)); end;

> [48] antonn © (14.01.08 22:01)

мда... здесь SSE Не поможет... нужен SSE3 помойму, вроде в нем есть умножение вектора на число.
Хотя ничто не мешает сделать вектор заполненный amount...
Но в любом случае первый SSE не умет работать с целыми, либо MMX(который я не знаю), либо SSE2>, который я не помню...
Завтра посмотрю на свежую голову, заодно ассемблер потренирую. ;)

у меня через ммх не получается :)
есть "обычное" смешение, без указания степени:
function AverageColor(const c1, c2: Tcolor): TColor; asm mov ecx, $7F7F7F shr eax, 1 shr edx, 1 and eax, ecx and edx, ecx add eax, edx end;

> Dib@zol © (14.01.08 15:37) [38]

Rate должна быть типа Single. С byte я и сам ьыстрее написать могу ибо Round - главный тормоз становится не нужен. Но обычно при вычислениях на вход будет подаваться именно Single. От этого никуда не денешься ибо это результат деления. Кстати, Real48 или Double тоже чуть медленнее.

> @!!ex © (14.01.08 18:06) [46]

да, конечно код из [25] воспринимается с трудом :) Но сам алгоритм прост.

> J_f_S (14.01.08 17:48) [43]

Да, мимо этой библиотеки я не мог пройти при поиске инфы об антиалиазинге. Библиотека хорошая, но навороченная и придется много кода перелопатить, чтобы выявить сами алгоритмы.

> antonn © (14.01.08 22:01) [48]

Да, это примерно тот код, который я оптимизировал. Кстати, его скорость примерно 640 против 240 из [25]

> homm © (14.01.08 17:39) [42]

Обязательно. :) От хороших советов не откажусь.

>
> Да, это примерно тот код, который я оптимизировал. Кстати,
> его скорость примерно 640 против 240 из [25]

у меня мой грубо говоря 50, а твой 17. Там перед ними еще куча нулей :)

кстати, на моем к2д round работает в 4-5 раз быстрее трунка. Был удивлен очень...

> [51] DVM © (14.01.08 22:32)
> Но обычно при вычислениях на вход будет подаваться именно
> Single. От этого никуда не денешься ибо это результат деления.

Денешся. Еще как. Я сомневаюсь, что там есть функции, которые нельзя перевести к целочисленной арифметике. Я делал градиентную заливку под произвольным угром. После того, как перешел на целочисленуб арифметику, ускорение было в 2 раза, точность не пострадала, кажется у меня 24 бита отводилось на промежуток от 0 до 1.

> homm © (15.01.08 10:49) [54]

Целочисленная арифметика в случае с инталиазингом неприменима по его сути. Дело в том, что яркость краевого пиксела - это по сути площадь трапеции (она <=1) которая образуется идеальной линией (у которой концы заданы вещественными координатами) и координатной сеткой (сеткой из пикселей растра). Соответственно округлять эту площадь все равно придется - либо до вызова функции смешения цветов, либо в ней самой.

Под яркостью я подразумеваю степень смешения с фоном

> [55] DVM © (15.01.08 11:10)
> у которой концы заданы вещественными координатами

Я говорю о полном переходе на целочисленую арифметику. Это не так сложно. Те же координаты пересчитаывем с целые числа (integer, верхнее слово — целая часть, нижнее — количество долей целой единицы.). Для линии синус и косинус нужно посчитать один раз, после вычисления они точно так же преобразуются. До умножения 2-х таких сисел они сдвигаются на 8 бит вправо, после умножения еще раз вправо (кажжется так). При сложении, складываются как есть. Коорджинаты все целые.

Вот в помошь:
http://delphimaster.net/view/8-1189622890/

> Те же координаты пересчитаывем с целые числа (integer, верхнее
> слово — целая часть, нижнее — количество долей целой единицы.
> ).

А ты вон о чем. Т.е предлагаешь изобрести свой новый тип данных с целой и дробной частью, заданными целыми числами?

> Ну ты же хочешь утвердительный ответ на сабж :)

Мороки много больно.

У меня вот щас в векторном редакторе все координаты вершин - целые числа. Вначале это было некритично, но теперь я понял, какую ошибку я совершил, не став использовать вещественные. В том же твоем примере про градиент - угол только целочисленный, но для серьезного применения этого недостаточно. Будет большая погрешность при больших размерах фигур.

Вот пример. Есть ломаная в виде горизонтальной пилы шириной 100 точек. Пользователь выставляет горизонтальный размер в 1 точку для этой фигуры.
Она превращается визуально в вертикальный отрезок. Далее он возвращает ее ширину к прежней. Если координаты вершин будут целочисленные, то обратно ее не вернуть к прежнему виду ибо х координата всех вершин станет одинаковой.

> [60] DVM © (15.01.08 11:39)
> В том же твоем примере про градиент - угол только целочисленный

Это вообще не принципиально, угол нужен для синуса и косинуса, которые в любом случае вещественные, поэто му целый угол — искуственное ограничени, меняешь описание функции, получаешь вещественный угол.

> Вот пример.

Я разве говорю о формате в котором хранятся данные? Да пусть хоть в текстовом, главное при расчете цвета исходные данные легко переводятся в любое представление.

> homm © (15.01.08 11:46) [61]

А вообще с градиентом у тебя хорошо получилось. Быстро. :)

Вот кстати так как то можно расширить возможности функции по заливке градиентом, чтобы заливать регион любой формы:

procedure GradientFillRgn(Canvas: TCanvas; ARect: TRect; ARgn: HRGN; StartColor, EndColor: TColor; AAngle: Integer); var rgn: HRGN; i: integer; FWasClippingRgn: Boolean; begin rgn := CreateRectRgn(0, 0, 0, 0); i := GetClipRgn(Canvas.Handle, rgn); // Old clipping region FWasClippingRgn := (i = 1); SelectClipRgn(Canvas.Handle, ARgn); DrawAngleGradient(Canvas, ARect, StartColor, EndColor, AAngle); if FWasClippingRgn then SelectClipRgn(Canvas.Handle, rgn) else SelectClipRgn(Canvas.Handle, 0); DeleteObject(rgn); end;

> [62] DVM © (15.01.08 11:51)
> Вот кстати так как то можно расширить возможности функции
> по заливке градиентом, чтобы заливать регион любой формы:

А разве рект из региона не проще и логичнее узнавать?

> А разве рект из региона не проще и логичнее узнавать?

ну мало ли , вдруг надо залить надо часть региона.

← →
Sapersky (2008-01-15 13:54) [65]

Я говорю о полном переходе на целочисленую арифметику. Это не так сложно.

Подтверждаю. В FastLIB масса примеров, хотя бы то же масштабирование картинки.
Если так уж пугает "новый тип", можно считать, что просто переходим на другие единицы измерения, вместо 1 пикселя - 1/65536-я пикселя.
Вот мой пример получения значения пикселя с "дробной" координатой X (с линейной интерполяцией между двумя соседними), имеется FP и целочисленный вариант, так что можно сравнить:

Var x, w2, i2, i3, t, t2, z, iz : Integer;
i, k : Single;

w2 := w div 2;
t := Round(theta * 65536); // theta = 0..1
t2 := w2 * (65536 - t);

If Smooth then
For x:=0 to w-1 do begin
// get average from neighbour pixels
If UseRealFP then begin // note: floating point calculations here
i := (x - w2) * theta + w2; // are slower 6-7 times
k := Frac(i); i2 := Trunc(i);
i3 := Round(SLine[i2] * (1-k) + SLine[i2+1] * (k));
end else begin
i2 := (x * t + t2); // really i * 65536
z := i2 and $FFFF; // float part (k)
iz := $FFFF - z; // 1 - k
i2 := i2 shr 16; // integer part
i3 := (SLine[i2] * iz + SLine[i2 + 1] * z) shr 16;
end;
<...>

Смешение цветов, быстрее можно ли? Найти похожие ветки