Effective method of output of 2D graphics by means of CPU
Версия на русском языке
Earlier I wrote that I decided to render an animated picture as a separate project "Pixel Walker". But the most important thing is that when I was working I had to achieve the output of the image in real time.
In addition to the slow speed of generation and regeneration of objects, there was a problem with the slow output of the graphics itself, as it was used for slow default methods of displaying graphics Canvas.
The first was solved by output to a separate stream of objects generation, but this post is devoted to the method of drawing graphics.
You could use ready-made graphics libraries, opengl or directx but, inspired by the stories that modern processors are able to output 2D graphics faster than modern video cards, I decided to experiment with the capabilities of the CPU.
First, there were output tests with the help of default methods and libraries, Canvas. Special results they did not give, I decided to try to output using scanline technology. Finally decided to save the image into a byte array, process the array itself and write it back as an image.
The image is in the format Bitmap - a special bitmap format that has a header structure and an array of pixels, 4 bytes each.
This method gave the advantage that with the data of the array it was possible to work directly, without unnecessary extra calls.
This conclusion produced a good result, but hypothetically, as before, would create problems if I wanted to draw too many objects.
When a picture is drawn on each other, inevitably there are situations when one pixel "grinds" the other - is drawn over it. Consequently, all the entries, until the conclusion of the total color, were superfluous.
To solve this problem, I came up with an algorithm that fixes the color for each pixel. At the input of the algorithm, an array of images, passing through a cycle at each point, the algorithm determines its color at the output.
It would seem nothing complicated, but I had to work hard on the algorithm, so that it worked as quickly as possible, without unnecessary calls, etc., and at least justified myself.
The first pitfalls arose immediately upon realization. For example, here is the previous algorithm:
where X and Y are the coordinates of the image being drawn
R, G, B - the color of the image at the output
BitMap is an image object
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;
Same version, but with a pixel output:
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;
For clarity, here is a simplified scheme of the algorithm, without optimizations and translucency. The main difference between the output by pixels is that after we have drawn the pixel of the "upper" layer, the break operator drops the loop and we go to the next coordinate.
Digging deeper. It turned out that each time in the cycle the coordinates are recalculated, where we draw, if in the first variant it can be optimized by adding for each iteration of the delta cycle, then in the case of pixel output, it must be recalculated every time, taking into account what else each time relative coordinates are calculated!
In general, this version of the graphics output code simply could not work faster. But on the other hand, the idea with the output of only the "top" pixel is quite logical, I started to optimize it.
To solve this problem, I came up with event-lines for drawing graphics.
The image, in this context, is a continuous stream of bytes that go one after another without "dividing" the line. In the examples above, this partition can only be counted by dividing the byte order number by its width. In this case, the essence of event-lines is that one event activates the output of graphics, and creates an event to stop the output of graphics in several cycles, which in turn again creates an event for drawing graphics. Each such event-line corresponds to one row of pixels.
Imagine that you have a red felt pen that moves from left to right and top to bottom on a sheet of paper, strictly so, without the possibility of deviating from the course. And you have a task, draw a rectangle on paper, dropping it in time and lifting the marker so that it can draw or not while it "rolls" along a piece of paper. After a few rows from left to right, you realize that to reach the goal, the marker needs to be cycled down for 3 seconds so that it can draw a line of 30 centimeters, then raise it by 40 seconds so that it returns to the position of the right border of the rectangle just below the previous line. Similar events work! Only instead of seconds are used the previously calculated coefficients-counters, and instead of the marker we use the stream of bytes of the image.
Such an architecture optimizes the calculations, do not calculate the coordinates every time, but allowed for this to increment the counters inside the event loops.
In the end, I achieved the desired result. Maximum FPS images reached 150 frames per second, with an average of 100 frames per second. And the main thing was the ability to "produce" objects in hundreds in real time without fear for productivity!
In the future I will talk about another object "stone". And now, I present you a small experiment, a video with a snow theme for the Pixel Walker engine:
Click to viewIf you want to support my project, you can do it by link or by adding one of the WebMoney:
R163522901261
Z180352303030
X054099745452
I thank everyone, readers and those who leave their feedback!