4
\$\begingroup\$

Disclaimer: I am uncertain if this is the best place to post this question, so please advise me of how I can best find the answer if I am doing something wrong. I am asking this question because I am trying to optimize a drawing function of a PC game I am programming.

Preface: There is a matrix of blocks, that can be either on (black) or off (white). There will be different colors, but for the sake of simplicity I am presenting the problem to you as black and white only, so please imagine this matrix forming some random pattern like a QR code which would be a good example.

Problem: Instead of drawing each black block individually, I want to determine how to draw all black blocks using as minimum calls to my draw black rectangle function as possible.

Question: Is there any existing process that I can refer to so as to make my drawing process as efficient as possible, or how would I logically go about tackling this conundrum?

Edit: Tried to produce some example code for us to play with

std::vector<std::vector<bool>> matrix;

int width = 100;
int height = 100;

matrix.resize(height);

for(int h = 0; h < height; h++)
{
    matrix[h].resize(width);
    for(int w = 0; w < width; w++)
    {
        matrix[h][w] = random 1/0
    }
}

void draw()
{
    .. draw matrix using a minimum amount of calls to draw_rectangle
}

void draw_rectangle(int x, int y, int width, int height)
{
    .. draws a set of black blocks
}
\$\endgroup\$
10
  • \$\begingroup\$ You can put all your squares in a single VBO and draw it with a single call. It's going to be 2000 triangles, which is very small amount. \$\endgroup\$ Jun 11 '16 at 13:01
  • \$\begingroup\$ Would that be just as efficient as putting fewer rectangles in a VBO to make the same image and drawing it with a single call? \$\endgroup\$
    – MrNoise
    Jun 11 '16 at 13:04
  • \$\begingroup\$ I think difference would be insignificant. The problem here is only an amount of draw calls, not polygons. \$\endgroup\$ Jun 11 '16 at 13:07
  • \$\begingroup\$ Thank you for your answer, I accept your method as I believe passing this to the GPU will be quicker than performing calculations in a CPU thread and then passing it to the GPU. \$\endgroup\$
    – MrNoise
    Jun 11 '16 at 13:08
  • 2
    \$\begingroup\$ Possible duplicate of Algorithm for "healing" multiple rectangles into a smaller number of rectangles? \$\endgroup\$
    – DMGregory
    Sep 18 '16 at 23:17
-2
\$\begingroup\$

There are two really good tutorials on the internet about how to improve performance, both by a guy called ThinMatrix. The first is mostly what you are looking for, but if you want to make it SUPER efficient you can also take a look at second one:

First: https://youtu.be/X6KjDwA7mZg Second: https://youtu.be/Rm-By2NJsrc

\$\endgroup\$
1
  • 2
    \$\begingroup\$ External-link-only answers are generally discouraged on StackExchange. If those videos are ever removed or change URLs, then a visitor will not be able to glean anything from this answer. This can be improved by summarising the main points in the text of your answer itself, and using the links for support & further details only. \$\endgroup\$
    – DMGregory
    Jul 17 '16 at 13:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.