13,088,701 members (56,324 online)
Rate this:
See more:
I'm currently writing my own bitmap library to hone my computer graphics skills. I've been able to code the majority of it, however, I still have to code the functions that'll render solid shapes like discs, polygons...etc.
I'm having difficulties deciding how to tackle this. Should I use a boolean matrix to render the full thing using flood fill algorithm, then copying it back to the original bitmap data matrix? Or should I look for a "mathy" way to fill the shapes I want to render?

Here is my code to render polygons:
```void Bitmap::polygon(Point point, const unsigned int radius, const unsigned int sides, const unsigned char red, const unsigned char green, const unsigned char blue)
{
float s = (float)sides;

if((s >= 3) && (0 < radius))
{
const double spi = PI / 2;
const double epi = -PI * 3 / 2;
int x1;
int y1;
int x2;
int y2;

s = (float)(PI * 2 / s);

x1 = point.x + (int)(cos(spi) * radius);
y1 = point.y + (int)(sin(spi) * radius);

{
int j = 0;
for(double i = spi - s; i >= epi; i -= s, j++)
{
x2 = point.x + (int)(cos(i) * radius);
y2 = point.y + (int)(sin(i) * radius);
bresenhamLine(this, x1, y1, x2, y2, red, green, blue);
x1 = x2;
y1 = y2;
}
}

x2 = point.x + (int)(cos(spi) * radius);
y2 = point.y + (int)(sin(spi) * radius);
bresenhamLine(this, x1, y1, x2, y2, red, green, blue);
}
}```
Posted 26-Feb-13 8:30am
Updated 11-Mar-13 14:40pm
v3
Sergey Alexandrovich Kryukov 26-Feb-13 14:34pm

Not clear. Why Boolean matrix, what could it possibly specify? Your signature for shapes are really not good. Why not having just the vector or array of points?
—SA
enhzflep 11-Mar-13 21:50pm

The way to do it s to fill horizontal lines in your polygons. This avoids the cache misses (=speed loss) and the memory consumption (= possible stack overflow) of a flood fill.

You can work out the slope of each edge of the polygon, before calculating all of the points that lie on them. So long as the vertexes have been sorted first (in order of y value), it's farly easy to loop through all of the y values of the polygon, calculating a left boundary and a right boundary. You then iterate through this list, drawing a horizontal line between the left and right boundaries. This page may provide some insight: Gouraud & Phong shadng polygons

Rate this:

## Solution 1

Your instinct is right: High quality graphics libraries do the filling usually the "mathy" way and not via an auxiliary bitmap and flood fill. For a circle the filling algorithm is not overly complex. Filling an arbitrary polygon is somewhat more difficult.

Look into the versions of the Bresenham algorithm for circles and ellipses for a fast way to find the border points. That saves you a lot of sin and cos calls and you might even get away with pure integer arithmetic.

For polygon filling I would (as always) start with a Google search. There are quite some interesting algorithms around for that.

Good luck; you chose an interesting subject.
Rate this:

## Solution 2

Probably the easiest way to do arbitrary polygon filling is the old trick of dividing everything into triangles and then doing one triangular segment at a time. It's probably not ideal for circles but for everything else it's reasonably quick and the maths is reasonably simple.

From memory you iterate points along the longest side of the triangle and calculate the correct length at each point for a line drawn at right angles to the longest side to intersect the outside of the triangle. I'm sure there are optimisations to give you each line length without a full recalcuation.

Top Experts
Last 24hrsThis month
 Jochen Arndt 250 Graeme_Grant 195 OriginalGriff 137 ppolymorphe 120 RyanDev 106
 OriginalGriff 3,247 Graeme_Grant 1,644 Jochen Arndt 1,485 ProgramFOX 1,437 ppolymorphe 1,367