Cropping a window out of chunks

Question

This code is for procedural terrain generation in a game. The generation happens in form of a grid of so called "chunks". Each chunk has the same size and has its column and row index in the grid associated with it. The grid of chunks expands into the negative dimension as well. The chunk data itself is a 2D array of char values.

Now to actually render the terrain, I have a "window" around the player. That window is larger than a couple of chunks and this window also has a char array for the terrain data. It's important that the window does not necessarily need to be snapped to the grid!

What this function does now is copy the corresponding parts of the chunks and insert the data into the window array at the right place. The code is currently quite inefficient because after a lot of trouble with more sophisticated approaches, I am effectively looping through the entire window once for each chunk. Then I have four IFs that ensure that only the pixels are copied that actually are inside the window.

void ExtWindow::RecalculateWindow(ExtWorld world, Point2D window_center, int width, int height, CharGridAcc window_data)
{
    // Size of a chunk
    const int chunk_w = world.chunk_w;
    const int chunk_h = world.chunk_h;


    // Window borders
    int left_border = window_center.x - width / 2;
    int top_border = window_center.y - height / 2;

    int right_border = window_center.x + width / 2;
    int bottom_border = window_center.y + height / 2;


    // Find the minimal and maximal needed chunk indices

    int min_chunk_x = left_border / chunk_w;
    if (left_border < 0) // Correction for negative positions
        min_chunk_x--;

    int max_chunk_x = right_border / chunk_w;
    if (right_border < 0) // Correction for negative positions
        max_chunk_x--;

    int min_chunk_y = top_border / chunk_h;
    if (top_border < 0) // Correction for negative positions
        min_chunk_y--;

    int max_chunk_y = bottom_border / chunk_h;
    if (bottom_border < 0) // Correction for negative positions
        max_chunk_y--;


    // Loop through every required chunk
    for (int chunk_x = min_chunk_x; chunk_x <= max_chunk_x; chunk_x++)
        for (int chunk_y = min_chunk_y; chunk_y <= max_chunk_y; chunk_y++)
        {
            // Minimal and maximal pixels for both axis for the current chunk
            // The pixels are in the real coordinate system
            int chunk_min_pixel_x = chunk_x * chunk_w;
            int chunk_min_pixel_y = chunk_y * chunk_h;
            int chunk_max_pixel_x = (chunk_x + 1) * chunk_w;
            int chunk_max_pixel_y = (chunk_y + 1) * chunk_h;

            // Generate the chunk data
            CharGridAcc cur_chunk = world.AquireChunk(chunk_x, chunk_y)->GetData();

            // Loop through the entire window (since this happens for every chunk, that is obviously unperformant on large windows)
            for (int x = 0; x < width; x++)
                for (int y = 0; y < height; y++)
                {
                    // The current real world pixel coordinate
                    int true_pixel_x = left_border + x;
                    int true_pixel_y = top_border + y;

                    // Several IFs that effectively constrain the segment below to only execute for
                    // those pixels in the chunk that are actually part of the window
                    if (true_pixel_x >= chunk_min_pixel_x)
                        if (true_pixel_y >= chunk_min_pixel_y)
                            if (true_pixel_x < chunk_max_pixel_x)
                                if (true_pixel_y < chunk_max_pixel_y)
                                {
                                    int pixel_in_chunk_x = true_pixel_x - chunk_min_pixel_x;
                                    int pixel_in_chunk_y = true_pixel_y - chunk_min_pixel_y;

                                    window_data[x][y] = cur_chunk[pixel_in_chunk_x][pixel_in_chunk_y];
                                }
                }
        }

}

Does someone have an idea how to optimize this? Is there some sort of standard algorithm for such a task that requires cropping from multiple sources? Huge thanks in advance!

Answer 1

Much of your work with X values can be lifted out of the Y loops, since they are invariant within the Y loop. This means that all the calculations of the various pixel_x values should be done before starting .

Also the four nested if statements could be a bit cleaner as one big if. However, the two conditions that test the X values should be done before the Y loop, since if they are true the Y loop won't do anything.

The conditions with that if can be handled before the loop starts by adjusting the loop starting and/or end values. This is similar to clipping graphics at the edge of a screen (or window). For example, if true_pixel_x is less than chunk_min_pixel_x, your loop won't do anything. If you start x at an appropriate value that condition can be skipped entirely.

int x = left_border < chunk_min_pixel_x ? chunk_min_pixel_x - left_border : 0;

What that does is if the first X value will be out of range, we start x at the first value that is in range, otherwise we start at 0.

Similar conditions can be done to determine the end X, start Y, and end Y values. Once that is done then your loop won't have any extra conditions in it and you won't need the if check.