LINUX.ORG.RU

Быстрое размытие.


0

2

Хайль всем.

Создаю маску для наложения тени, возникла проблема - все мои примитивы рисуются с четкой границей (just as planned). Чтобы не было такой границы света, делаю Blur для маски. Все работает. Но хочется ускорить blur раз в 10 (сейчас размытие картинки 800х600 на уровне размытия 2 занимает примерно секунду. Хочу ускорить процесс.

Как делаю размытие - Вначале создаю массив размером LEVEL * 2 + 1, который заполняю коэффициентами, потом используя данный массив заполняю копию текстуры, суммируя цвета по маске, затем деля на сумму ячеек. Потом замещаю исходное изображение измененной копией.

Есть что-то побыстрей? Снизить время надобно минимум раза в 4. Мой метод дает примерно (на изображение 800 * 600 и уровнем 2):

  • 480 000 операций деления.
  • ~ 4 320 000 операций сложения.
  • 480 000 операций копирования ячейки.
  • 9 эпических вычислений по особоизощренной негауссовой формуле.

Ответ для тех, кто спросит, зачем я работаю с копией, а потом её копирую: если работать все время с изображением, то при расчете Y+1,X ячейки она будет использовать не Y, X, а (Y,X)`, поскольку Y,X уже была изменена и перезаписана.

P.S. Если есть какой-нибудь интересный способ типа наложения битовой маски каким-нибудь изощрённым, но быстрым способом - welcome.

Ответ на: комментарий от AlexCones

Но на OpenGL будет 100500 тыщ раз быстрее. Любой CPU с любым алгоритом будет плакать и звать маму. Почему нельзя интегрировать OpenGL или OpenCL?

vertexua ★★★★★
()
Ответ на: комментарий от vertexua

Я не хочу вас обидеть или что-то такое, но гонка за компактностью - это та иллюзия в которую начинает верить девелопер, а потом его работу просто никто не юзает, потому что это никогда не есть преимуществом. Только в embedded на очень простых железках, но кто на них делает blur с такими интенсивными вычислениями? У вас не сопоставляется задача с устройством тогда

vertexua ★★★★★
()
Ответ на: комментарий от vertexua

Вообще делаю для своего удовольствия, мне доставляет орг^W радость решать такие задачи. Но в принципе было бы неплохо сохранить такой размер, ибо а вдруг.

AlexCones ★★★
() автор топика
Ответ на: комментарий от AlexCones

Если вы откажетесь от дедовских методов, то сделаете намного качественне фреймворк с более высокой производительностью, который будет аппаратно ускорен и речь будет идти скорее всего о 200 blurах в секунду. И решено будет интереснее

vertexua ★★★★★
()
Ответ на: комментарий от vertexua

>И решено будет интереснее
Ну да, очень интересно делать все в одну строку на всем готовом. И да, конечному пользователю надо будет качать Ogl, Dx или еще какого черта. Сейчас никаких требований нет.

Просто смиритесь с тем, что я пишу без использования внешних фреймворков. А то каждый, который слышит, что я не использую Ogl\Dx\NET\XNA начинает мне доказывать, что я бобер, что у всех давно стоит Dx11 с супермощными видеокартами и вообще все надо перенести в интернет на облако, поскольку у всех канал в 100 Мбит. (с) мой преподаватель.

AlexCones ★★★
() автор топика
Ответ на: комментарий от AlexCones

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

Вообще кода будет больше скорее всего. И вывернуться хитро прийдется, на CPU колбасить каждый может, школа 10 класс. А вот оптимально на GPU реализовать - это интересно и важно в современном софте.

OpenGL качать не надо.

Просто смиритесь с тем, что я пишу без использования внешних фреймворков.

Мда...

vertexua ★★★★★
()
Ответ на: комментарий от AlexCones

А то каждый, который слышит, что я не использую Ogl\Dx\NET\XNA начинает мне доказывать, что я бобер, что у всех давно стоит Dx11 с супермощными видеокартами и вообще все надо перенести в интернет на облако, поскольку у всех канал в 100 Мбит. (с) мой преподаватель.

Ну, в принципе так и есть.

power
()
Ответ на: комментарий от AlexCones

>мой преподаватель
Ах это оказывается преподаватель вас науськивает на такие неправильные методы :-).
Вообще не слушай этого вертухайа, делай без ОпенГЛ.
А еще чем не устраивает время в 1 сек? Или оно пересчитывается каждый кадр или при каждом изменении в карте?

Bad_ptr ★★★★★
()
Ответ на: комментарий от Bad_ptr

Карта разграфлена на области 40 * 30. Когда игрок покидает такую область я могу позволить только около полусекунды на раздумье, чтобы перерисовать новую область, создать ей маску освещения, наложить маску и отрисовать движущиеся объекты. Из всего этого создание маски занимает 95% времени.

AlexCones ★★★
() автор топика
Ответ на: комментарий от Ximen

Не проблемно, но много ли люди из него поймут?

Procedure FilterBlur(Level : Integer); StdCall; Export;
Var
 CopyArr : Array of RGBQuad;
 Matrix : Array of Double;
 I : Integer;
 X, Y : Integer;
 Summ : Double;
 XIn, YIn : Integer;
 ChanRed, ChanBlue, ChanGreen : Double;
 Distance : Integer;
Begin
 // Copying color array
 SetLength(CopyArr, Length(RasterEditor.SA));
 CopyArr := Copy(RasterEditor.SA, 0, Length(CopyArr));
 // Filling up factors array
 SetLength(Matrix, Level + 1);
 For I := 0 To Level Do
  Matrix[I] := 0.5 * Level * Sqrt(1 - (Sqr(I)/Sqr(Level)));
 // Apply new colors
 For Y := RasterEditor.Select.Top To RasterEditor.Select.Bottom Do
  For X := RasterEditor.Select.Left To RasterEditor.Select.Right Do
   Begin
    Summ := 0;
    ChanRed   := 0;
    ChanBlue  := 0;
    ChanGreen := 0;
    For YIn := Y - Level To Y + Level Do
     For XIn := X - Level To X + Level Do
      If InRectangle(XIn, YIn,
                     RasterEditor.Select.Left,
                     RasterEditor.Select.Top,
                     RasterEditor.Select.Right,
                     RasterEditor.Select.Bottom) Then
       Begin
        Distance := Round(Sqrt(Sqr(XIn - X) + Sqr(YIn - Y)));
        If Distance < Level Then
         Begin
          ChanBlue  := ChanBlue  + CopyArr[_XY(XIn, YIn)].rgbBlue  * Matrix[Distance];
          ChanGreen := ChanGreen + CopyArr[_XY(XIn, YIn)].rgbGreen * Matrix[Distance];
          ChanRed   := ChanRed   + CopyArr[_XY(XIn, YIn)].rgbRed   * Matrix[Distance];
          Summ := Summ + Matrix[Distance];
         End;
       End;
    ChanRed   := ChanRed   / Summ;
    ChanBlue  := ChanBlue  / Summ;
    ChanGreen := ChanGreen / Summ;
    _SetPixel(X, Y,
              RGB(Round(ChanRed),
                  Round(ChanGreen),
                  Round(ChanBlue)));
   End;
End;

AlexCones ★★★
() автор топика
Ответ на: комментарий от AlexCones

Не проблемно, но много ли люди из него поймут?

Да просто любопытно. Я вот живого паскаля уже много лет не видел, оказывается. Забавный он :) Кстати, как у него с производительностью? В своё время разница с C была колоссальная. А вещи типа

Round(Sqrt(Sqr(XIn - X) + Sqr(YIn - Y)));

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

Ximen ★★★★
()
Ответ на: комментарий от Ximen

Я вот живого паскаля уже много лет не видел

Паскаля я тоже лет 6 не видел, это лазарус, синтаксис немного отличается в плане указателей и проч.

Кстати, как у него с производительностью?

При правильных флагах у FPC все хорошо. Hedgewars не тормозят :З.

Ну и да, требуемые 4 раза можно получить банльной оптимизацией математики и прочих мелочей в циклах. Наверное.

Побольше бы конкретики...

AlexCones ★★★
() автор топика
Ответ на: комментарий от AlexCones

Ну вот можно предпросчитывать потихонечку в бэкграунде для соседних областей, например.

Bad_ptr ★★★★★
()
Ответ на: комментарий от AlexCones

Побольше бы конкретики...

Да всё просто. Для начала было бы не плохо посмотреть, что скажет профайлер на этот кусок. Мне всё же кажется, что приведённая выше строчка в двойным цикле всё и портит. Тогда просто заменяй библиотечную математику более быстрой реализацией. Можно, конечно, и более быстрый алгоритм поискать (наверняка), но на вскидку не придумаю.

Ximen ★★★★
()
Ответ на: комментарий от Ximen

>выше строчка в двойным цикле всё и портит.

А как вы предлагаете посчитать расстояние между двумя точками? Нового способа пока не придумали. И да, библиотечная функция не идеальна, но быстрее неё только голый ассемблер.

Ну вот можно предпросчитывать потихонечку в бэкграунде для соседних областей, например.


Мысль, конечно, но я плохо представляю, как мне это реализовать. Делать потоки?

AlexCones ★★★
() автор топика
Ответ на: комментарий от AlexCones

Нового способа пока не придумали. И да, библиотечная функция не идеальна, но быстрее неё только голый ассемблер.

Целочисленная математика, приближённые алгоритмы (точность же не важна), табличные данные. Куча способов избавиться и от формулы в таком виде и от квадратов с корнями даже без асма. Хотя, повторюсь, сначала надо с профайлером посоветоваться.

Делать потоки?

Потоки это хорошо. Главное, чтобы ещё тормознее не получилось.

Ximen ★★★★
()
Ответ на: комментарий от AlexCones
For I := 0 To (Level*Level) + 1 Do
begin
    val := 0.5 * Level * Sqrt(1 - (Sqr(I)/Sqr(Level)));
    Matrix[I] := val * val;
end;
...
DistanceSquared := Round(Sqr(XIn - X) + Sqr(YIn - Y));
...
Summ := Summ + Matrix[DistanceSquared];
note173 ★★★★★
()

Используй свертку с матрицей единичек размером LEVELxLEVEL, такую свертку можно вычислять за время не зависящее от LEVEL.

Если что, распишу подробнее

480 000 операций деления.

~ 4 320 000 операций сложения.

480 000 операций копирования ячейки.

9 эпических вычислений по особоизощренной негауссовой формуле.

Судя по коду, ты используешь много больше операций

Waterlaz ★★★★★
()
Ответ на: комментарий от Waterlaz

Если что, распишу подробнее

Очень хотелось бы. Независеть от размера level - это как раз то, что нужно.

AlexCones ★★★
() автор топика
Ответ на: комментарий от Ximen

Целочисленная математика, приближённые алгоритмы (точность же не важна), табличные данные.

Ума не приложу, как в данном алгоритме избавиться от дробей. Приближенные алгоритмы? Никогда не слышал. Можно подробнее? Табличные данные для каждой точки 800 * 600 по отношению к расстоянию к каждой другой? Не хилый такой массив получается. И да, а если я выставлю не 800 х 600, а запилю наонец поддержку 1024 х 768 режима?

AlexCones ★★★
() автор топика
Ответ на: комментарий от baverman

Это не ко мне, это к моему преподавателю. Моя библиотека даже на моем домашнем музейном экспонате работает.

AlexCones ★★★
() автор топика
Ответ на: комментарий от AlexCones

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

note173 ★★★★★
()
Ответ на: комментарий от AlexCones

Работает это одно, но насколько я понимаю это какой-то игровой движок, поэтому он должен работать *быстро*. Некоторые операции быстро на CPU просто невозможно сделать.

baverman ★★★
()
Ответ на: комментарий от AlexCones

Ума не приложу, как в данном алгоритме избавиться от дробей.

Ты не знаешь матчасти и начал писать графическую библиотеку? ОМГ.

baverman ★★★
()
Ответ на: комментарий от AlexCones

Идея такая. Цвет в пикселе (x, y) заменить на средний цвет в окошке (x-d, y-d)-(x+d, y+d). Это не гауссово размытие, но тоже неплохое.

Чтобы быстро считать сумму по окошку, используй http://en.wikipedia.org/wiki/Summed_area_table

Waterlaz ★★★★★
()
Ответ на: комментарий от Waterlaz

Ты и так используешь временный массив. Только теперь заполнишь его по правилу I(x,y) = i(x,y) + I(x-1,y) + I(x,y-1) - I(x-1,y-1),

Waterlaz ★★★★★
()
Ответ на: комментарий от baverman

насколько я понимаю это какой-то игровой движок

Скорее комбайн, основная функция - система управления окнами. Побочная - двухмерный и трехмерный графические движки.

Ты не знаешь матчасти и начал писать графическую библиотеку?

Что-то знаю, что-то нет. Просто пока не задумывался о модификации уже работающего алгоритма. Скорее всего сделаю две версии - одну «медленную», но с точным размытием, вторую «быструю», но с худшим размытием.

AlexCones ★★★
() автор топика
Ответ на: комментарий от Waterlaz

Алгоритм ясен. Что ж неплохая вещь, спасибо! Буду над ним думать. Есть еще какие-нибудь подобные крутые математические вещи?

AlexCones ★★★
() автор топика
Ответ на: комментарий от baverman

Во-во, некоторых кодеров надо насильно на атом пересаживать. Особенно питонистов, джавистов, и кедодевелоперов.

Kosyak ★★★★
()
Ответ на: комментарий от vertexua

А смысл делать на ОпенГЛ, если не везде он есть, а где есть, не везде ускоряется аппаратно, темболее, если можно и без него обойтись.

Bad_ptr ★★★★★
()
Ответ на: комментарий от Bad_ptr

если не везде он есть

Всего лишь на 99% целевых машин

а где есть, не везде ускоряется аппаратно

Всего лишь везде где есть

если можно и без него обойтись.

Написав код, которые будет работать 1 сек вместо 200 раз в секуну

vertexua ★★★★★
()
Ответ на: комментарий от AlexCones

разбить это:

 For Y := RasterEditor.Select.Top To RasterEditor.Select.Bottom Do
  For X := RasterEditor.Select.Left To RasterEditor.Select.Right Do
  ...

на несколько областей. в центральной:

 For Y := RasterEditor.Select.Top+Level To RasterEditor.Select.Bottom-Level Do
  For X := RasterEditor.Select.Left+Level To RasterEditor.Select.Right-Level Do
...
// подозреваю это всегда True, comment out
//      If InRectangle(XIn, YIn,
//                     RasterEditor.Select.Left,
//                     RasterEditor.Select.Top,
//                     RasterEditor.Select.Right,
//                     RasterEditor.Select.Bottom) Then
//       Begin
// Distance и Summ от X,Y и XIn,YIn не зависит , только от их разностей, нужно рассчитать снаружи
//        Distance := Round(Sqrt(Sqr(XIn - X) + Sqr(YIn - Y)));
		Distance := Distance2dArray[Abs(XIn-X)][Abs(YIn-Y)];
        If Distance < Level Then
         Begin
          ChanBlue  := ChanBlue  + CopyArr[_XY(XIn, YIn)].rgbBlue  * MatrDist; //Matrix[Distance];
          ChanGreen := ChanGreen + CopyArr[_XY(XIn, YIn)].rgbGreen * MatrDist; //Matrix[Distance];
          ChanRed   := ChanRed   + CopyArr[_XY(XIn, YIn)].rgbRed   * MatrDist; //Matrix[Distance];
//          Summ := Summ + Matrix[Distance];
         End;
//     End;
    ChanRed   := ChanRed   / Summ;
    ChanBlue  := ChanBlue  / Summ;
    ChanGreen := ChanGreen / Summ;
    _SetPixel(X, Y,
              RGB(Round(ChanRed),
                  Round(ChanGreen),
                  Round(ChanBlue)));

cool-e-bin
()
Ответ на: комментарий от AlexCones

Level ведь наверняка ограничен сверху каким-то небольшим числом? Тогда создаёшь двумерный массив DM с индексами от [0..MaxLevel][0..MaxLevel] и заносишь туда значения

DM[x, y]:= Matrix[sqrt(sqr(x) + sqr(y))]

, потом

ChanBlue := ChanBlue + CopyArr[_XY(XIn, YIn)].rgbBlue * DM[XIn - X, YIn - Y];

от условия «If Distance < Level Then» тоже избавиться можно предвычислением матрицы

unC0Rr ★★★★★
()
Ответ на: комментарий от AlexCones

Кстати, что делает _SetPixel? Помнится, если в винде попиксельно заполнять изображение, то тормоза будут просто эпические без всяких формул. Думаю, это будет верно для любого графического тулкита, ведь SetPixel должен проверить хендлы, координаты и прочую муть на каждом вызове.

unC0Rr ★★★★★
()
Ответ на: комментарий от cool-e-bin

подозреваю это всегда True, comment out

Нет, это условие очень важно. Оно позволяет не просто что-то там сделать с фильтром, а еще и использовать выделение области для работы только с ним.

// Distance и Summ от X,Y и XIn,YIn не зависит , только от их разностей, нужно рассчитать снаружи

// Distance := Round(Sqrt(Sqr(XIn - X) + Sqr(YIn - Y)));

как это не зависит?

Distance := Round(Sqrt(Sqr(XIn - <<X>>) + Sqr(YIn - <<Y>>)));

AlexCones ★★★
() автор топика
Ответ на: комментарий от cool-e-bin

>ChanRed := ChanRed + CopyArr[_XY(XIn, YIn)].rgbRed * MatrDist; //Matrix[Distance];

Имеете в виду сразу применять в нудной пропорции, чтобы избавится от последнего деления? Хм...

AlexCones ★★★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.