Composition at What Level?

barpoly

That picture’s got a lot going on.  In Render Text like a Boss, I was rendering text, which is a pretty exciting milestone.  The only thing more exciting to do with text is render based on vectors, and being able to scale and rotate, but there are other fish to fry in the meanwhile.  I find that polygons are fairly useful as a primitive.

The above picture shows a whole bunch of primitives rendering with varying degrees of transparency.  Those random rectangles in the background are just making things look interesting.  Next are some random bars, with varying degrees of transparency, again just to make things look interesting.  And then comes that orange tinted polygon thing that lays atop the bars.  The polygon is simply constructed by taking the midpoint of the top edge of the bar as a vertex.  The two bottom vertices (left and right) close out the polygon.

But wait a minute, I see a bunch of triangles in there?  Well, just for the purposes of this article, I’m showing how the polygon is broken down into triangles (triangulated).  Triangles?  what the heck?  Well, you see, it’s like this.  There is more than one way to skin a cat, or render a polygon.  You can search the interwebs and find as many ways to do it as there are graphics libraries.  The ‘direct’ method would have you go scan line by line, calculating even and odd line crossings to determine whether individual pixels were ‘inside’ or ‘outside’ the polygon, and thus color the pixel.  You could traverse down edges, creating horizontal line spans, and then render those spans.  Well, these both look fairly similar to the choices made when rendering a triangle.  So, maybe it’s easier to simply break the polygon down into triangles, and then render the resultant triangles.  I’m sure there’s some math theorem somewhere that can be used to prove that any polygon > 3 points can be broken up into nice sets of triangles.  Equivalently, there are numerous coding algorithms which will do the same.  For graphic, I found a nice public domain triangulator, and incorporated it into the library.  Pass it some points, it breaks them down into triangles, and the triangles are rendered.

Great.  This has a couple of nice implications.  First of all, triangles (and ultimately horizontal lines) remain a useful primitive in the core of the graphics library.  I did not actually add a polygon capability to the core, just keep the triangles there, and anyone who needs polygons can easily break them down into triangles.  That leaves me with a single complex primitive to optimize.  I do the same for quads.  Rectangles are a special case, in that they may be optimized separately to come up with faster behavior than the triangulation would deliver.

ellipses

What about the ellipse?  Hmmm.  There are faily fast ellipse drawing routines in the world.  The most interesting for drawing ellipse outlines looks like this:

 

void raster_rgba_ellipse_stroke(pb_rgba *pb, const uint32_t cx, const uint32_t cy, const size_t xradius, size_t yradius, const uint32_t color)
{
	int x, y;
	int xchange, ychange;
	int ellipseerror;
	int twoasquare, twobsquare;
	int stoppingx, stoppingy;

	twoasquare = 2 * xradius*xradius;
	twobsquare = 2 * yradius*yradius;

	x = xradius;
	y = 0;

	xchange = yradius*yradius*(1 - 2 * xradius);
	ychange = xradius*xradius;
	ellipseerror = 0;
	stoppingx = twobsquare*xradius;
	stoppingy = 0;

	// first set of points, sides
	while (stoppingx >= stoppingy)
	{
		Plot4EllipsePoints(pb, cx, cy, x, y, color);
		y++;
		stoppingy += twoasquare;
		ellipseerror += ychange;
		ychange += twoasquare;
		if ((2 * ellipseerror + xchange) > 0) {
			x--;
			stoppingx -= twobsquare;
			ellipseerror += xchange;
			xchange += twobsquare;
		}
	}

	// second set of points, top and bottom
	x = 0;
	y = yradius;
	xchange = yradius*yradius;
	ychange = xradius*xradius*(1 - 2 * yradius);
	ellipseerror = 0;
	stoppingx = 0;
	stoppingy = twoasquare*yradius;

	while (stoppingx <= stoppingy) {
		Plot4EllipsePoints(pb, cx, cy, x, y, color);
		x++;
		stoppingx += twobsquare;
		ellipseerror += xchange;
		xchange += twobsquare;
		if ((2 * ellipseerror + ychange) > 0) {
			y--;
			stoppingy -= twoasquare;
			ellipseerror += ychange;
			ychange += twoasquare;
		}
	}
}

This is one of those routines that takes advantage of the fact that axis aligned ellipses have a lot of symmetry, so 4 pointes are plotted at the same time. Well, it’s not a big leap to think that this technique can be extended. For filling the ellipse, you can simply draw horizontal lines between the symmetrical points, and you end up with a solid ellipse.

inline void fill2EllipseLines(pb_rgba *pb, const uint32_t cx, const uint32_t cy, const unsigned int x, const unsigned int y, const uint32_t color)
{
	raster_rgba_hline_blend(pb, cx - x, cy + y, 2*x, color);
	raster_rgba_hline_blend(pb, cx - x, cy - y, 2 * x, color);
}

void raster_rgba_ellipse_fill(pb_rgba *pb, const uint32_t cx, const uint32_t cy, const size_t xradius, size_t yradius, const uint32_t color)
{
	int x, y;
	int xchange, ychange;
	int ellipseerror;
	int twoasquare, twobsquare;
	int stoppingx, stoppingy;

	twoasquare = 2 * xradius*xradius;
	twobsquare = 2 * yradius*yradius;

	x = xradius;
	y = 0;

	xchange = yradius*yradius*(1 - 2 * xradius);
	ychange = xradius*xradius;
	ellipseerror = 0;
	stoppingx = twobsquare*xradius;
	stoppingy = 0;

	// first set of points, sides
	while (stoppingx >= stoppingy)
	{
		//Plot4EllipsePoints(pb, cx, cy, x, y, color);
		fill2EllipseLines(pb, cx, cy, x, y, color);
		y++;
		stoppingy += twoasquare;
		ellipseerror += ychange;
		ychange += twoasquare;
		if ((2 * ellipseerror + xchange) > 0) {
			x--;
			stoppingx -= twobsquare;
			ellipseerror += xchange;
			xchange += twobsquare;
		}
	}

	// second set of points, top and bottom
	x = 0;
	y = yradius;
	xchange = yradius*yradius;
	ychange = xradius*xradius*(1 - 2 * yradius);
	ellipseerror = 0;
	stoppingx = 0;
	stoppingy = twoasquare*yradius;

	while (stoppingx <= stoppingy) {
		fill2EllipseLines(pb, cx, cy, x, y, color);
		x++;
		stoppingx += twobsquare;
		ellipseerror += xchange;
		xchange += twobsquare;
		if ((2 * ellipseerror + ychange) > 0) {
			y--;
			stoppingy -= twoasquare;
			ellipseerror += ychange;
			ychange += twoasquare;
		}
	}
}

In this context, the ellipse is kind of like the rectangle. There is an easy optimization at hand, so the benefits of employing triangulation might not be worth the effort. Then again, if you wanted to maintain a smaller codebase, then you might want to triangulate even this ellipse. You’d still be stuck with using the straight up code to draw the ellipse outline, and with a little bit of refactoring, you could use the exact same code for the outline and the fill. The routine to be utilized for the symmetrical points could be passed in as a function pointer, and that would be that. That makes for easy composition, code reuse, and the like.

I’m not actually sure how much I tend to use ellipses in realistic drawing anyway. I suppose there are circles here and there, but eh, there you go.

The theme of this article was composition. There is a bit of code reuse, composition in how you build larger things from smaller things, and simply trying to maintain a constraint of a small codebase, requires that higher order elements are composed from smaller simpler elements. The triangulation code currently relies on some C++ (for vector), so it can’t go into the core library as yet (straight C only), but I’m sure it will get there.

Well, there you have it, the little library that could is gaining more capabilities all the time. Soon enough, these capabilities will allow the composition of some fairly complex UI elements.

Advertisements


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s