arshehremen

Эффективный метод вывода 2D графики средствами СPU

Version in English

Ранее я писал о том, что я решил сделать визуализацию анимированной картинки как отдельный проект "Pixel Walker". Но самое главное, что при работе мне нужно было добиться вывода изображения в режиме реального времени.

Помимо медленной скорости генерации и перегенерации объектов, стояла проблема с медленным выводом самой графики, так как для неё использовались медленные дефолтовые методы вывода графики Canvas-ом.

Первое решалось выводом в отдельный поток генерации объектов, а вот методу вывода графики посвящен данный пост.

Можно было бы использовать готовые графические библиотеки, аля opengl или directx но, вдохновившись байками, что современные процессоры в состоянии выводить 2D графику быстрее современных видео-карт, я решил поэксперементировать с возможностями CPU.

Сперва были тесты вывода с помощью дефолтовых методов и библиотек, Canvas-ом. Особых результатов они не дали, я решил попробовать вывод с помощью технологии scanline. В итоге решил сохранять изображение в байт массив, обрабатывать сам массив и записывать его обратно как изображение.

Изображение имеет формат Bitmap — специальный формат растрового изображения, имеющий структуру заголовка и массив пикселей, по 4 байта на каждый.

Этот метод давал преимущество того, что с данными массива можно было работать напрямую, без посторонних лишних вызовов. 

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

Когда картинка рисуется друг на друге неизбежно возникают ситуации, когда один пиксель "перетирает" другой — рисуется поверх него. Следовательно все записи, до вывода итогового цвета, были лишние.

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

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

Первые подводные камни возникли сразу же при реализации. Например, вот предыдущий алгоритм:


где X и Y координаты рисуемого изображения

R, G, B цвета изображения на выходе

BitMap — объект изображения


for each BitMap in Bitmaps do

  for Y= 0 to BitMap.height do

     for X = 0 to BitMap.width do

         IDFromMass = 54 + ( Y*BitMap.width+X)*4;

         alpha = BitMap.ByteMassive[IDFromMass+3];

         if alpha < 254 then

                   R = BitMap.ByteMassive[IDFromMass+2];

                   G = BitMap.ByteMassive[IDFromMass+1];

                   B = BitMap.ByteMassive[IDFromMass];

                   apply( R, G, B );

         end if;

     end for;

  end for;

end for;


А вот та же версия, но с выводом по пикселям:


for Y= 0 to height do

  for X = 0 to width do

     for each BitMap in Bitmaps do

       DX = X - Bitmap.Left;
      DY = Y - Bitmap.Top;

         IDFromMass = 54 + ( DY*BitMap.width+DX)*4;

         alpha = BitMap.ByteMassive[IDFromMass+3];

         if alpha < 254 then

                   R = BitMap.ByteMassive[IDFromMass+2];

                   G = BitMap.ByteMassive[IDFromMass+1];

                   B = BitMap.ByteMassive[IDFromMass];

                   apply( R, G, B );

                  break;

         end if;

     end for;

  end for;

end for;


Для наглядности, здесь приведена упрощенная схема алгоритма, без оптимизаций и полупрозрачности. Главное отличие вывода по пикселям, это то, что после того, как мы нарисовали пиксель "верхнего" слоя, оператором break сбрасывается цикл и мы переходим на следующую координату.

Копаем глубже. Получилось так, что у нас каждый раз в цикле пересчитываются координаты, куда мы рисуем, если в первом варианте её можно оптимизировать прибавляя для каждой итерации цикла дельту, то в случае с выводом по пикселям её необходимо пересчитывать каждый раз, с учётом того, что ещё каждый раз рассчитываются относительные координаты!

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

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

Представьте, что у вас есть красный фломастер, который передвигается слева-направо и сверху-вниз по листу бумаги, строго так, без возможности отклонятся от курса. И у вас стоит задача, нарисовать на бумаге прямоугольник, вовремя опуская и поднимая фломастер, чтобы он мог рисовать или нет, пока он "катается" по листу бумаги. Через несколько рядов слева-направо, вы понимаете, что для достижения цели фломастер нужно циклично опускать на 3 секунды, чтобы он успел нарисовать линию 30 сантиметров, потом поднимать на 40 секунд, чтобы он вернулся на позицию правой границы прямоугольника чуть чуть ниже предыдущий линии. Примерно так же работают эвенты! Только вместо секунд используются заранее подсчитанные коэффициенты-счетчики, а вместо маркера мы используем поток байтов изображения.

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

В итоге я достиг желаемого результата. Максимальный FPS  картинки достигал 150 кадров в секунду, при среднем 100 кадров в секунду. А главное появилась возможность "плодить" объекты сотнями в режиме реального времени не боясь за производительность!

В дальнейшем я расскажу о ещё одном объекте "камень". А сейчас, представляю вам небольшой эксперимент, видео с зимней темой для движка Pixel Walker:

Если вы хотите поддержать мой проект, это можно сделать по ссылке или пополнив один из счетов WebMoney:

R163522901261

Z180352303030

X054099745452

Благодарю всех, читателей и тех, кто оставляет свои отзывы!

Error

default userpic

Your reply will be screened

When you submit the form an invisible reCAPTCHA check will be performed.
You must follow the Privacy Policy and Google Terms of use.