В поисках пикселя

← →
Mihey © (2004-03-25 17:28) [0]

Ради интереса производил тестирование скорости доступа к пикселям различными средствами: TCanvas.Pixels, Scanline, QPix (TQuickPixels, статья на сайте, а одним из авторов скромно выступил MBo, если не ошибаюсь) и Graphic32 (http://www.g32.org, делал тоже наш - Alex Denisov). Для замерения времени был выбран компонент THPCounter - высокоточный таймер, точность до 0,000001 секунды.

Было создано 4 проекта, в которых реализовывалась одна и та же задача: просканировать изображение 800x600 с глубиной цвета 24bit и присвоить значение переменной. Измерялась скорость только от начала сканирования до его завершения.

Значение в обычном случае присваивалось переменной типа TColor. Для Scanline была использована функция RGBToColor следующего вида:

function RGBToColor(R,G,B:Byte): TColor;
begin
Result:=B Shl 16 Or
G Shl 8 Or
R;
end;

Проблема вышла с Graphic32. Дело в том, что этот графический пакет определяет свой класс TBitmap32 для работы с битмапами, используя при этом свой класс TColor32 для хранения цвета - обычный TColor с альфа-каналом. С одной стороны, TColor32 используется в Graphic32 везде и в пределах работы с Graphic32 конвертации не требуется. С другой стороны, хотел соблюсти строгость теста, поэтому в одном из результатов использовалась функция WinColor, возвращающая TColor из TColor32.

Результаты были замерены несколько раз, на глаз выбрано что-то среднее, что (!) не меняет картину результатов.

Тест выполнялся на компьютере PII 400 MHz с 64 Mb RAM, Win 98.

=====

TCanvas.Pixels
Этот способ показал самый медленный результат - 1.91 секунды.

=====

Scanline
Использовать этот метод довольно неудобно, но тем не менее он дал вполне приемлемый результат - 0.04 секунды.

=====

QPix
Мне он показался очень удобным. создаёшь переменную класса TQuickPixels, присоединяешься к битмапа и всё. Он показал очень хорошую скорость: 0.026 секунды! Пожалуй, если вы хотите работать в переделах класса TBitmap, то используйте этот способ.

=====

Graphic32
Использовать этот графический пакет очень просто. К обычному классу прибавляется постфикс 32 и всё. Теперь подробнее о результатах.

Присваивание переменной типа TColor32 дало результат 0.027 секунды при использовании метода TBitmap32.Pixels и самый быстрый результат - 0.02 секунды при использовании TBitmap32.Pixel. Поясняю различие: при использовании Pixels учитывается, что координаты пикселя могут выйти из граний изображения, и тогда вернётся некоторое значение OuterColor. Очевидно, что функцию замедляет проверка.

Однако использование TBitmap32.Pixel вместе с функцией WinColor дало результат 0.04 секунды на всё изображение.

← →
Mihey © (2004-03-25 17:46) [1]

Гм, я так подумал ещё. TBitmap32 работает в памяти с 32-bit битмапами, конвертируя все остальные форматы в этот. В то же время, в статье про TQuickPixels даны скорости чтения пикселей битмапов различных цветовых режимов и 32-bit"ные изображения читаются быстрее, чем 24-битные, поэтому вполне возможно, что TQuickPixels обгонит Graphic32 в этом плане.

Кроме того, функция WinColor сильно замедляет работу по чтению цвета в TColor. Вполне возможно, что и функция RGBToColor замедляет и для Scanline. Это при том, что WinColor реализована вот так:

unction WinColor(Color32: TColor32): TColor;
asm
// the alpha channel byte is set to zero!
ROL EAX,8 // ABGR -> BGRA
XOR AL,AL // BGRA -> BGR0
BSWAP EAX // BGR0 -> 0RGB
end;

Сейчас проведу дополнительные исследования.

← →
Mihey © (2004-03-25 17:55) [2]

Провёл. QPix при работе с 32-bit"ным изображением даёт 0.025 секунды, на 1/1000 меньше.

← →
MBo © (2004-03-25 18:49) [3]

Добавлю про QPixels:
Приведенные в статье времена измерены на машине P600, для разной цветовой глубины различие достигает 5 раз (для малоцветных код доступа сложнее). На компе Athlon XP 1900+ различие сильно нивелируется и составляет 2-2.5 (ок.100-240 мегапикселов/сек) - благодаря более эффективной конвейеризации время работы кода существенно быстрее, а лимитирует скорость доступа к памяти, которая возросла не столь значительно. Особенно существенно влияние доступа к памяти при случайных (не последовательных) обращениям к пикселах в разных местах больших битмапов - частично теряются преимущества кэширования. Поэтому при bulk-обработке (посчитать пикселы, найти опред.цвет и т.п.) иногда стоит организовывать "mass production" - считывание и обработку нескольких пикселов сразу, строго последовательное чтение или запись.

← →
miek © (2004-03-25 20:42) [4]

Камрады! Не поймите неправильно, но доступ к пикселям по одному (всякие SetPixel), какой метод ни используй, быстрым не будет НИГДЕ. Нефиг даже искать. Просто в Дельфи нет макросов, а любой вызов процедуры занимает много времени. Если добавить отсечение в видимой области, то вообще привет.

И, кстати, нигде он и не нужен особенно.

← →
Mihey © (2004-03-25 20:59) [5]

>И, кстати, нигде он и не нужен особенно.

Ну ты наверное мыслишь слишком по-DirectX"стски, где идёт работа с уже готовыми изображениями спрайтов. Попиксельная работа с изображением требуется и при применении фильтров (3х3, 5х5), и при создании инструментов рисования, и при анализе изображений. А по поводу скорости. Представленные скорости вполне соответсвуют требованиям. Никто ведь не будет выводить просто так растр попиксельно (хотя в том же DirectDraw это, кажется, требуется для достижения alpha-blending"а).

← →
MBo © (2004-03-25 21:06) [6]

>miek
Можешь предложить непопиксельный метод для реализации неаффинных преобразований?

← →
miek © (2004-03-25 23:08) [7]

>Ну ты наверное мыслишь слишком по-DirectX"стски

Отнюдь нет. Сейчас как раз делаю движок с комбинированным принципом: рисование софтом в системной памяти, вывод через BltFast. Проблемы доступа к пикселам вижу. Решаются они не отдельными процедурами, а групповым доступом.

>Можешь предложить непопиксельный метод для реализации неаффинных преобразований?

А где они нужны, неаффинные?

← →
Mihey © (2004-03-25 23:33) [8]

>Проблемы доступа к пикселам вижу. Решаются они не отдельными процедурами, а групповым доступом.

Расшифруй, а то может твои решения и впрямь лучше.

← →
dmk © (2004-03-25 23:59) [9]

miek © (25.03.04 23:08) [7]
>Отнюдь нет. Сейчас как раз делаю движок с комбинированным >принципом: рисование софтом в системной памяти, вывод через >BltFast. Проблемы доступа к пикселам вижу. Решаются они не >отдельными процедурами, а групповым доступом.

Абсолютна точно. У меня такая же проблема. Тружусь над
движком такого же плана. Обработка происходит регионами(блоками).
Так получается намного быстрее. Плюс использование перегрузки
функций если это выгодно. Единственный минус по сравнению с
попиксельной обработкой усложнение движка. В моем случае когда он перевалил за 30 тыс. строк, стало почти невозможно все держать в голове.

← →
MBo © (2004-03-26 05:40) [10]

Ясно, что групповая обработка быстрее (о чем я в [3] писал), но реализация ее несравненно сложнее и будет специфичной для каждого отдельного случая. Как, например, проводить аффинное преобразование. Стандартный путь - reverse mapping для того, чтобы не было дырок - обходим новое изображение, ставя каждой его точке в соответствие точку старого. Строки нового сканируем, вычисляем координаты исходных пикселов. Для ускорения можно воспользоваться тем, что прямые при А.П. переходят в прямые - можно использовать брезенхемоподобные алгоритмы. Новая картинка поблочно, последовательно проходится без проблем. Но ведь по старой мы идем наискосок!

← →
miek © (2004-03-26 14:23) [11]

>Расшифруй, а то может твои решения и впрямь лучше.

Ну как же. Берешь адрес пиксела, потом вместо обращения к SetPixel/Pixels[] просто пишешь туда, для изменения координат прост изменяешь адрес.

← →
Mihey © (2004-03-26 16:03) [12]

2 miek:

Ну я так и понял в принципе. Собственно, класс TBitmap32 пакета Graphic32 предоставляет доступ к массиву указателей Bits размером Width * Height и аналогично позволяет через Inc(P), где P - указатель на цвет пикселя, двигаться по всему массиву.

← →
Mihey © (2004-03-26 21:25) [13]

Продолжил исследования скорости доступа к пикселам различнми способами, а именно: TCanvas.Pixels, Scanline, QPixels, Graphic32. В этот раз была поставлена более практическая задача - заполнить изображение 800х600 жёлтым цветом (соответствующим константе clYellow или идентичный ему, т.е. (255, 255, 0) при реализации Scanline и clYellow32 при реализации Graphic32). Тестирование дало весьма интересные результаты.

==========

TCanvas.Pixels

Вполне ожидаемо оказался самым медленным способом. Весь цикл занял 1.58 секунды.

==========

Scanline

Scanline жив! Этот способ показал один из самых лучших результатов - 0.0096 секунды. Сравните эту скорость с TCanvas.Pixels.

==========

QPixels

Неожиданно оказался медленнее Scanline - 0.023 секунды.

==========

Graphic32

Здесь тоже свои ньюансы. Изменение цвета через TBitmap32.Pixel дало результат 0.02 секунды.

Также был использован другой способ, так как задачей стояло залить дёлтым цветом всё изображение, а именно использовался доступ к пикселам через указатели, движение по которым осуществлялось через Inc(). Этот способ показал результат, практически равный Scanline - 0.00958 секунды.

← →
Mihey © (2004-03-26 21:31) [14]

Собственно, вопросы. Почему так подкачал QPixels - неужели всё дело в RGB- и TColor-представлении цвета?

Код Scanline:

const PixelCountMax = 32768; type pRGBTripleArray = ^TRGBTripleArray; TRGBTripleArray = ARRAY[0..PixelCountMax-1] OF TRGBTriple; var Bmp: TBitmap; procedure TmainForm.btnTestClick(Sender: TObject); var x, y: Integer; i: Integer; Row: pRGBTripleArray; begin HPCounter.Start; for y := 0 TO Bmp.Height-1 DO begin Row := Bmp.Scanline[y]; for x := 0 TO Bmp.Width-1 DO begin with Row[x] do begin rgbtRed := 255; rgbtGreen := 255; rgbtBlue := 0; end end end; i := HPCounter.ReadInt; lblResult.Caption := IntToStr(i); end;

Код QPixels:

var Bmp: TBitmap; QP: TQuickPixels; procedure TmainForm.btnTestClick(Sender: TObject); var x, y: Integer; C: TColor; i: Integer; begin C := clYellow; HPCounter.Start; for y := 0 to Bmp.Height-1 do for x := 0 to Bmp.Width-1 do begin QP.setpixel(x,y,c); end; i := HPCounter.ReadInt; lblResult.Caption := IntToStr(i); end;

← →
dmk © (2004-03-26 22:13) [15]

Так в QPixels каждый раз расчет адреса идет =) Что ж тут удивительного?! А в ScanLine только адрес первого пиксела
расчитывается. Причем наверняка самым простым способом:
DestPtr := BaseAddress + (Y * ScanLineLength).
Ну и далее обращаться к этому адресу как к массиву:
DestPtr[x] := Pixel; или в случае 32 бит так:

Procedure SetDWord(DestPtr,Value:DWord);
asm
mov [eax], edx
end;

← →
miek © (2004-03-26 22:56) [16]

>была поставлена более практическая задача - заполнить изображение 800х600 жёлтым цветом

Это тоже непрактическая задача. Лучше протестируй скорость вывода 1000-5000 спрайтов (из набора общей площадью хотя бы 1/3 экрана). Вот это будет практическая задача и полезный труд.

← →
Mihey © (2004-03-26 23:40) [17]

>Это тоже непрактическая задача. Лучше протестируй скорость вывода 1000-5000 спрайтов (из набора общей площадью хотя бы 1/3 экрана). Вот это будет практическая задача и полезный труд.

Я ж говорил, что ты по-DirectX"овски мыслишь. Ну какой вывод спрайтов на пикселях??? А вот откомпилированное сравнение SpriteUtils с Graphic32 ты мне задолжал.

Ну а заполнение изображения цветом - это обычный Clear. На практике очень часто нужен.

← →
dmk © (2004-03-27 00:24) [18]

Попробуй так:

type
PixelFunc = Procedure(Addr,Value:DWord);

Procedure SetP32(Addr,Value:DWord);
asm
bswap edx
shr edx, 8
mov [eax], edx
end;

Procedure SetP24(Addr,Value:DWord);
asm
bswap edx
shr edx, 8
mov [eax], dl
shr edx, 8
mov [eax + 1], dx
end;

procedure TMainForm.ToolButton8Click(Sender: TObject);
var
bmp: TBitmap;
sT,eT: DWord;
x,y: Integer;
c: TColor;
BaseAddr: DWord;
RowAddr: DWord;
ScLen: DWord;
NumPlanes: DWord;
PFunc: PixelFunc;
bW,bH: Integer;
dc: HDC;

begin
bmp := TBitmap.Create;
bmp.LoadFromFile("d:\done\800_600.bmp");

case bmp.PixelFormat of
pf24bit:
begin
NumPlanes := 3;
PFunc := SetP24;
end;
pf32bit:
begin
NumPlanes := 4;
PFunc := SetP32;
end;
else
begin
bmp.FreeImage;
bmp.Free;
Raise Exception.Create("Unknown pixel depth!");
end;
end;

bW := bmp.Width;
bH := bmp.Height;

ScLen := DWord(bW) * NumPlanes;
BaseAddr := DWord(bmp.ScanLine[0]);

c := clYellow;

sT := GetTickCount;

For y := 0 to bH - 1 do
begin
RowAddr := BaseAddr;
For x := 0 to bW - 1 do
begin
PFunc(RowAddr, C);
Inc(RowAddr, NumPlanes);
end;
Dec(BaseAddr, ScLen);
end;

eT := GetTickCount;

dc := GetDC(0);
BitBlt(dc, 0,0, bW, bH, bmp.Canvas.Handle, 0, 0, SRCCOPY);
ReleaseDC(0, dc);
DeleteDC(dc);

bmp.FreeImage;
bmp.Free;

ShowMessage(FloatToStrF((eT - sT) / 1000, ffNumber, 18, 18) + " секунд затрачено");
end;

Ну а если надо очистить, то это еще проще =)

procedure TMainForm.ToolButton8Click(Sender: TObject);
var
bmp: TBitmap;
sT,eT: DWord;
c: ColorRef;
BaseAddr: Pointer;
ScLen: DWord;
NumPlanes: DWord;
bW,bH: Integer;
dc: HDC;
iSize: DWord;

begin
bmp := TBitmap.Create;
bmp.LoadFromFile("d:\done\800_600.bmp");

case bmp.PixelFormat of
pf24bit: NumPlanes := 3;
pf32bit: NumPlanes := 4;
else
begin
bmp.FreeImage;
bmp.Free;
Raise Exception.Create("Unknown pixel depth!");
end;
end;

bW := bmp.Width;
bH := bmp.Height;

ScLen := DWord(bW) * NumPlanes;
BaseAddr := bmp.ScanLine[bH - 1];
iSize := ScLen * DWord(bH) div NumPlanes;
c := clYellow;

sT := GetTickCount;

asm
push edi

mov eax, c
bswap eax
shr eax, 8

mov ecx, iSize
mov edi, BaseAddr

rep StosD

pop edi
end;

eT := GetTickCount;

dc := GetDC(0);
BitBlt(dc, 0,0, bW, bH, bmp.Canvas.Handle, 0, 0, SRCCOPY);
ReleaseDC(0, dc);
DeleteDC(dc);

bmp.FreeImage;
bmp.Free;

ShowMessage(FloatToStrF((eT - sT) / 1000, ffNumber, 18, 18) + " ñåêóíä ïîòðà÷åíî");
end;

← →
dmk © (2004-03-27 00:26) [19]

Быстрее последнего нет ничего, если только
не какая-нибудь супер пупер оптимизация =)

← →
Mihey © (2004-03-27 00:53) [20]

Выдаёт AV на строке:

rep StosD

Использую D5. Может из-за этого?

← →
dmk © (2004-03-27 01:08) [21]

Скорее всего у тебя формат картинки 24 бита, а я написал для
32 бит. Сейчас для 24 напишу.

← →
dmk © (2004-03-27 01:16) [22]

вместо того ассемблерного кода вставь этот.
Но этот только для 24 бит

asm
push edi

mov eax, c
bswap eax
shr eax, 8
mov dl, al
shr eax, 8

mov ecx, iSize
mov edi, BaseAddr

@@nP:
mov [edi], dl
mov [edi + 1], ax
add edi, 3

dec ecx
jnz @@nP

pop edi
end;

← →
dmk © (2004-03-27 01:23) [23]

Этот код можно ускорить практически до скорости 32 битного.
Достаточно развернуть цикл. Только не переборщи с границами
изображения, а то AV выскочит.

← →
dmk © (2004-03-27 01:26) [24]

К сожалению у меня на P4-2.53GHz прорисовка происходит настолько быстро, что результат GetTickCount после цикла возвращается тот
же самый. Поэтому у меня время исполнения равно 0.

← →
Mihey © (2004-03-27 01:34) [25]

2 dmk:

Последний код выдал 0.006 секунд на такое изображение, и, будь моя программа вирусом, испоганила бы пользователю 150 здоровенных картинок за секунду. Я попробовал тот первый код для 32-битного изображения, но получил меньшую скорость - 0.009 секунд (сравнимо с Graphic32 и Scanline).

← →
dmk © (2004-03-27 02:11) [26]

Вся беда в коде REP STOSD.
По каким то причинам она работает медленнее чем Mov.
Замени для 32 бит код на этот. Должно быть быстрее.
asm
push edi

mov eax, c
bswap eax
shr eax, 8

mov ecx, iSize
mov edi, BaseAddr

@@nP:
mov [edi], eax
add edi, 4
dec ecx
jnz @@nP

pop edi
end;

← →
dmk © (2004-03-27 02:13) [27]

А еще лучше так
asm
push edi

mov eax, c
bswap eax
shr eax, 8

mov edx, NumPlanes
mov ecx, iSize
mov edi, BaseAddr

@@nP:
mov [edi], eax
add edi, edx
dec ecx
jnz @@nP

pop edi
end;

← →
dmk © (2004-03-27 02:39) [28]

Решил я тоже потестировать скорость.
Загнал все в цикл. Вот так:
For NumCycles := 0 to 511 do
asm
end;

И у меня получилось, что для
32 бит скорость закраски = 1.14 сотых секунды
на 512 заливок 800х600 или 0,0022265625 секунды
на одну заливку.
Для 24 бит скорость закраски = 0.859 тысячных секунды
на 512 заливок 800х600 или 0,001677734375 секунды
на одну заливку.

Это говорит о том, что команда rep Stosd составная и крайне
не эффективная =(. Придется свой движок в некоторых местах переделывать.

PS. Завтра попробую развернуть цикл.
Может еще быстрее будет =)

>По каким то причинам она работает медленнее чем Mov
>команда rep Stosd составная и крайне неэффективная

Разумеется. Быстрее она будет только на x486

А разворачивать цикл эффективно только до уровня 2 DWORD-а на итерацию, шина все равно больше не возьмет.

Последний способ для 32-bit дал такой же результат на моём компе.

>>[24] dmk © (27.03.04 01:26)

Используй для подсчёта:

function GetCPUTick: int64; assembler; asm rdtsc end;

Точнее измерителя скорости не бывает ;).

Только для точных измерений лучше, я думаю, не процедуру использовать, а прямо код раскрыть.

← →
goblin (2004-03-28 00:27) [33]

<miek © (27.03.04 20:35) [32]
Только для точных измерений лучше, я думаю, не процедуру использовать, а прямо код раскрыть.>
Абсолютно правильно, необходимо также удостоверится, что кэш отдан нам - примитивно, но работает:
Sleep(0) перед вызовом процедур, у которых замеряется время....
Либо многократный вызов - чтобы отбросить влияние загрузки кеша данными (оценка только выполнения кода).
Может я и не прав ...но я пользуюсь этим способом более менее точно.
А для "групповой" забивки пикселей - лучше пользоваться коммандой MOVNTQ ...

А если нужно просто отобразить ранее подготовленный массив на экране? Возможно какая то дополнительная оптимизация?

>А если нужно просто отобразить ранее подготовленный массив на экране? Возможно какая то дополнительная оптимизация?

Практически никакой, кроме пользования MMX. Тем более, отображаешь экран не ты, а GDI (или DirectX).

2 MegaVolt © (29.03.04 15:45) [34]

Заполнение буфера изображением
24 бита использовать эффективнее

На моем P4 2.53GHz получилось
Для 10000 заполнений ушло времени 7.922 секунды
т.е. на одно перемещение буфера 0.00079 десятитысячных секунды.
Это менее 1 миллисекунды.
Или 1262,3 кадра в секунду =)
По моему очень неплохо.

Как то вроде Miek выкладывал скоростной 2D движок.
У него тоже зашкаливало за 700 fps на моей машине =)
Только разрешение было 1024х768.

procedure TMainForm.ToolButton8Click(Sender: TObject);
var
bmp: TBitmap;
sT,eT: DWord;
BaseAddr: Pointer;
ScLen: DWord;
NumPlanes: DWord;
bW,bH: Integer;
dc: HDC;
iSize: DWord;
tmp: Pointer;
NumCycles: DWord;

begin
bmp := TBitmap.Create;
bmp.LoadFromFile("d:\done\800_600_24.bmp");

case bmp.PixelFormat of
pf24bit: NumPlanes := 3;
pf32bit: NumPlanes := 4;
else
begin
bmp.FreeImage;
bmp.Free;
Raise Exception.Create("Unknown pixel depth!");
end;
end;

bW := bmp.Width;
bH := bmp.Height;

ScLen := DWord(bW) * NumPlanes;
BaseAddr := bmp.ScanLine[bH - 1];
iSize := ScLen * DWord(bH) div NumPlanes;
GetMem(Tmp, iSize * NumPlanes);

sT := GetTickCount;

For NumCycles := 0 to 9999 do
MoveBytes(DWord(BaseAddr), DWord(Tmp), iSize);

eT := GetTickCount;

FreeMem(Tmp, iSize);

dc := GetDC(0);
BitBlt(dc, 0,0, bW, bH, bmp.Canvas.Handle, 0, 0, SRCCOPY);
ReleaseDC(0, dc);
DeleteDC(dc);

bmp.FreeImage;
bmp.Free;

ShowMessage(FloatToStrF((eT - sT) / 1000, ffNumber, 18, 5) + "секунд затрачено" + #13 +
FloatToStrF((eT - sT) / 1000 / 10000, ffNumber, 18, 5) + " секунд на заливку");
end;

Ах да! Совсем забыл. Вот код MoveBytes.
Тестировал на больших и долгих циклах.
Получилось, что он на 1-2% эффективнее
чем с командой REP MOVSD.
По крайней мере на p4.

procedure MoveBytes(SrcAddr, DestAddr, NumBytes: DWord);
asm
push edi
push esi

mov esi, SrcAddr
mov edi, DestAddr
mov eax, NumBytes
mov ecx, eax
sar ecx, 2
push eax
jz @@oB

@@nP:
mov eax, [esi]
mov [edi], eax
add esi, 4
add edi, 4
dec ecx
jnz @@nP

@@oB:
pop ecx

and ecx, 03h
rep movsb

pop esi
pop edi
end;

>24 бита использовать эффективнее

Неверно. Чем меньше bpp, тем эффективнее.

>Или 1262,3 кадра в секунду =)

Это ж скорость рендеринга, а не вывода. Попробуй вывести на экран, сразу поплохеет, особенно через GDI.

>Получилось, что он на 1-2% эффективнее
чем с командой REP MOVSD.

Можно и нужно быстрее. Посмотри, как у меня (хотя там тоже не предел). www.miek.narod.ru/spriteutils2.zip
Процедура TDIB.PutFast

>Неверно. Чем меньше bpp, тем эффективнее.

Нет уж, не надо нам 16-bit. Это прошлое. Делайте движки, поддерживающие 24- или 32-bit"ные изображения.

>Неверно. Чем меньше bpp, тем эффективнее
Я имел в виду выбор между 24 и 32 битами.

В поисках пикселя - benchmark Найти похожие ветки