Friday, January 15, 2010

Bresenham's circle, Open GL and blowing holes in textures

Bresenham's circle algorithm is actually a variation on Bresenham's line drawing algorithm and as such it gets it's name, even though Bresenham didn't really invent the circle part.

Playing with destructable terrain I wanted to be able to blow circular holes in a texture. I succeeded by fetching a texture with Open GL and twiddling the bytes with the circle algorithm to do so.

The code below is in the spirit of what I did. Below is the main meat method on the algorthim, you might call it DrawFilledCircle() or some such.

..

/*

Input Parameters:

Vector2 pos; // The position of the explosion/circle center in texture pixel space.
float radius; // The radius of the explosion/circle in pixels
unsigned char* buf; // The pixel array - pixels are in RGBA format
Texture* texure; // a texture or texture info pointer
Colour colour; // the colour RGBA that you want the circle to be
*/

int width = texture->GetWidth();
int height = texture->GetHeight();

int left = int(pos.x - radius);
int right = int(pos.x + radius);
int top = int(pos.y + radius);
int bottom = int(pos.y - radius);

// check to see the circle will even touch the texture
if (!((left < width && right > 0) && (bottom < height && top > 0)))
{
return;
}

int max_x = std::min(right, width);
int max_y = std::min(top, height);

int r = (int)radius;
int x = 0;
int y = r;

float p = 1 - r;

while (x < y)
{
if (p < 0)
{
x += 1;
p = p + 2 * x + 1;
}
else
{
x += 1;
y -= 1;
p = p + 2 * (x - y) + 1;
}
CircleLineFill(buf, width, -x + pos.x, y + pos.y, x*2, colour, max_x, max_y);
CircleLineFill(buf, width, -x + pos.x, -y + pos.y, x*2, colour, max_x, max_y);
CircleLineFill(buf, width, -y + pos.x, x + pos.y, y*2, colour, max_x, max_y);
CircleLineFill(buf, width, -y + pos.x, -x + pos.y, y*2, colour, max_x, max_y);
}

The next method is CircleLineFill. This is a slight variation of the normal algorithm that draws just the outline of a circle, it doesn't fill the circle. This method fills the entire circle, leaving the edges of the intersection with a black edge.


void CircleLineFill((unsigned char* buf, int width, int x, int y, int length, Colour col, int max_x, int max_y))
{
if ((y < 0 || y >= max_y) ||
(x + length < 0) ||
(x >= max_x ))
return;

int right = std::min(x + length - 1, max_x);
int left = std::max(0, x + 1);

Colour* pixel = NULL;
if (x >= 0)
{
pixel = (Colour*)((char*)buf + (y * width * sizeof(Colour) + sizeof(Colour)*x));
if (pixel->a != 0)
{
*pixel = Colour(0, 0, 0, 255);
}
}
int dwords = right - left;
if (dwords > 0)
{
pixel = (Colour*)((char*)buf + (y * width * sizeof(Colour) + sizeof(Colour)*(left)));
memset(pixel, col.c, (dwords*sizeof(Colour)));
}
if (right > 0 && right < max_x)
{
pixel = (Colour*)((char*)buf + (y * width * sizeof(Colour) + sizeof(Colour)*(right)));
if (pixel->a != 0)
{
*pixel = Colour(0, 0, 0, 255);
}
}
}

1 comment:

  1. This comment has been removed by a blog administrator.

    ReplyDelete