We were given a program that’s only function was to draw out a series of circles with varying gradients and radii. The entire process was slow, with every pixel calculating the magnitude between itself and every other circle in the space. We can speed this up significantly by reducing the space of checks that the circles need to do.

This is the unedited code that we have to beat.

At a time of almost 4 seconds, we can do much better.

First, I made a Quad class, that functions as an min and max for both the x and y, and has a list of all the circles that it contains.

class Quad
{
public:
float xMin;
float xMax;
float yMin;
float yMax;

std::vector<Circle> circleInside;
};

The Quad then sets its min and max based on how many segments I want the screen to be split up by.

int divisionNumber = 3;//number of squares across and down

//total number of quads
std::vector<Quad> quads = std::vector<Quad>(divisionNumber * divisionNumber);

//the dimensions to use
double widthDivided = g_windowWidth / divisionNumber;
double heightDivided = g_windowHeight / divisionNumber;

for (int y = 0; y < divisionNumber; ++y)//set the sizes for the quads
{
for (int x = 0; x < divisionNumber; ++x)
{
int index = x + y * divisionNumber;//gets index of quad

quads[index].xMin = widthDivided * x;
quads[index].yMin = heightDivided * y;
quads[index].xMax = widthDivided * (x + 1);
quads[index].yMax = heightDivided * (y + 1);
}
}

This allows me to dynamically create the quads for easy testing with no magic numbers.

Next, we create the circles to be tested against. The circles have their positions and radius randomised. I then create a bounding box based on their radius.

        Circle c;
c.m_pos.x = rand() % g_windowWidth;
c.m_pos.y = rand() % g_windowHeight;
c.m_radius = rand() % 50;

c.xMin = c.m_pos.x – c.m_radius;
c.xMax = c.m_pos.x + c.m_radius;
c.yMin = c.m_pos.y – c.m_radius;
c.yMax = c.m_pos.y + c.m_radius;

Then, I check the circle against all the quads to see if its bounding box is inside one or more of them.

        for (int index = 0; index < quads.size(); ++index)
{
if ((c.xMin > quads[index].xMax) || (quads[index].xMin > c.xMax))
continue;

if ((c.yMin > quads[index].yMax) || (quads[index].yMin > c.yMax))
continue;

quads[index].circleInside.push_back(c);
continue;
}

By allowing circles to belong to multiple quads, this allows the renderer to draw the entire circle when there’s overlap.

Now we tell each quad to render out its circles.

    for each (Quad q in quads)
{
for (int y = q.yMin; y < q.yMax; ++y)
{
for (int x = q.xMin; x < q.xMax; ++x)

This code means that each pixel is only ever checking against circles inside their quad, speeding up processing significantly.

Next, the pixel checks to see if its inside a circles radius to start rendering the white.

By changing the original magnitude check to a squared magnitude, we can speed up the checks. Once we’ve determined that we are in fact inside a circle, THEN we get the actual magnitude to get the correct distance value.

                for (int i = 0; i < q.circleInside.size(); ++i)
{
if ((kf::Vector2(x, y) – q.circleInside[i].m_pos).lengthSquared() <= q.circleInside[i].m_radius*q.circleInside[i].m_radius)
{
float d = (kf::Vector2(x, y) – q.circleInside[i].m_pos).length();
e = e + (1.0 – d / q.circleInside[i].m_radius);
}
}

The rest of the code is simply rendering that pixel. Now lets see how much timer we’ve saved with this code.

Old Time: 3.948 seconds

New Time: 1.117 seconds

Shaving 3 seconds off the total time, this is a big improvement from the original code.