Click here to Skip to main content
13,088,701 members (56,324 online)
Rate this:
Please Sign up or sign in to vote.
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
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?
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: bad
Please Sign up or sign in to vote.

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: bad
Please Sign up or sign in to vote.

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.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

  Print Answers RSS
Top Experts
Last 24hrsThis month

Advertise | Privacy |
Web01 | 2.8.170813.1 | Last Updated 12 Mar 2013
Copyright © CodeProject, 1999-2017
All Rights Reserved. Terms of Service
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100