Drawproc – Like Processing, but in C++

Triangle Strips using drawproc

trianglestrip

So, what’s the code look like to create this gem?

#include "drawproc.h"

int x;
int y;
float outsideRadius = 150;
float insideRadius = 100;


void setup() {
	size(640, 360);
	background(204);
	x = width / 2;
	y = height / 2;
}


void drawStrip()
{
	int numPoints = int(map(mouseX, 0, width, 6, 60));
	float angle = 0;
	float angleStep = 180.0 / numPoints;

	beginShape(GR_TRIANGLE_STRIP);
	for (int i = 0; i <= numPoints; i++) {
		float px = x + cos(radians(angle)) * outsideRadius;
		float py = y + sin(radians(angle)) * outsideRadius;
		angle += angleStep;
		vertex(px, py);
		px = x + cos(radians(angle)) * insideRadius;
		py = y + sin(radians(angle)) * insideRadius;
		vertex(px, py);
		angle += angleStep;
	}
	endShape();
}

void draw() {
  background(204);
  drawStrip();
}

If you’ve done any coding in Processing, you can look at the example that inspired this bit of code here: Triangle Strip

What’s notable about it is the similarity to the Java or even the JavaScript version (if processing.js). It takes about a 10 minute conversion to go from Processing to using drawproc. So, what is drawproc?

Drawproc is an application and library which facilitates the creation of interactive graphics. It is the culmination of taking the work from graphicc and encapsulating in such a way that makes it easy to use in multiple situations.

So, how does it work?  Basically, there is the drawproc.exe application.  This application contains a main(), and a primary event loop which takes care of capturing mouse and keyboard events, and issuing “draw()” calls.  Previously (Dyanmic Programming in C) I explained how that dynamic bit of machinery works. All that machinery is at work here with the addition of one more dynamic programming item.

bool InitializeInstance(const char *moduleName)
{

	// Get pointers to client setup and loop routines
	clientModule = LoadLibrary(moduleName);

	printf("modH: 0x%p\n", clientModule);

	SetupHandler procAddr = (SetupHandler)GetProcAddress(clientModule, "setup");
	printf("proc Address: 0x%p\n", procAddr);

	if (procAddr != NULL) {
		setSetupRoutine(procAddr);
	}

	LoopHandler loopAddr = (LoopHandler)GetProcAddress(clientModule, "draw");
	printf("loop Addr: 0x%p\n", loopAddr);

	if (loopAddr != NULL) {
		setLoopRoutine(loopAddr);
	}

	if ((procAddr == nullptr) && (loopAddr == nullptr))
	{
		return false;
	}

	gClock = dproc_clock_new();

	return true;
}

When invoking drawproc, you give a name of a module, which is a .dll file compiled against the .exe. Typical execution looks like this:

c:\tools>drawproc trianglestrip.dll

That ‘trianglestrip.dll’ is passed along to the InitializeInstance() call, the module is loaded, and the ‘setup()’ and ‘draw()’ functions are looked for. If neither of them is found, or the .dll doesn’t load, then the program quits. At this point, everything is the same as if you had linked the drawing module into the drawproc.exe program directly. The advantage is you have a simple small (~200K for debug version) executable (drawproc.exe) which is very slow changing. Then you have the modules, which can be numerous, and dynamic. You can create modules independently of the drawproc.exe and run as you wish. You could even write a single module which loads .lua, or any other embedded scripting environment, and write your code using that scripting language instead.

How do you create these modules? Well, you just write your code, make reference to the header files within drawproc, and use drawproc.lib as the library reference. All the relevant symbols within drawproc are exported, so this just works. At the end of the day, the drawproc.exe looks just like any other .dll that might be out there.

In case you’re still reading, here’s another picture.

SineConsoleBanate CAD 2011

This one is interesting because it’s actually an animation (SineConsole).  A few years back, when I was experimenting with BanateCAD, I had done something similar, all in Lua Banate CAD 2011.

Why bother with all this though?  Why C? What’s the point?  I had this interesting conversation last week with a co-worker.  We were discussing whether people who are coming into becoming software programmers would be better served by learning C#, or C/C++.  I think my answer was C#, simply because it seems more in fashion and more applicable to other dynamic languages than does C/C++.  But, here we’re doing a lot of ‘dynamic’ with standard C/C++.  Really the answer to that question is “you will need to learn and use many languages, frameworks, and tools in your software development.  Learning some C will likely serve you well, but be prepared to learn many different things.’

drawproc being written in C/C++ is great because it makes programming graphics fairly simple (because of the Processing mimicry).  Using the Processing API makes the graphics stuff really easy.  At the same time, since it’s written in C/C++, gaining access to the lowest level stuff of the platform is really easy as well.  For example, integrating with the Microsoft Kinect sensor is as easy as just using the Microsoft Provided SDK directly.  No shim, no translation layer, no ‘binding’ to get in the way.  That’s a very good thing.  Also, as time goes on, doing the accelerated this and that, throwing in networking and the like will be a relative no brainer.

So, there you have it.  drawproc is a new standalone tool which can be used for fiddling about with graphics.  For those who are into such things, it’s a nice tool to play with.


Dyanmic Programming in C

Certainly there must be a picture?
test_keyboard

This is a simple test app using the graphicc drawproc library.  The app is pretty simple.  It displays a background image, and as you drag the mouse over the image, the location and size of that semi-translucent square is displayed at the bottom of the window on that status line.
Here is the entirety of the program

/*
test_keyboard

Do some simple mouse and keyboard tracking

*/
#include "drawproc.h"
#include "guistyle.h"
#include &lt;stdio.h&gt;

static GUIStyle styler;
static const int gMaxMode = 3;
static int gMode = 0;

pb_rgba fb;
pb_rect keyRect = { 0, 0, 34, 34 };

void  mousePressed()
{
	gMode++;
	if (gMode &gt;= gMaxMode) {
		gMode = 0;
	}
}

void  mouseMoved()
{
	keyRect.x = mouseX - keyRect.width / 2;
	keyRect.y = mouseY - keyRect.height / 2;
}

void  keyReleased()
{
	switch (keyCode)
	{
	case VK_SPACE:
		write_PPM_binary("test_keyboard.ppm", gpb);
		break;

	case VK_RIGHT: // increase width of keyRect
		keyRect.width += 1;
		break;

	case VK_LEFT:
		keyRect.width -= 1;
		if (keyRect.width &lt; 4) keyRect.width = 4;
		break;
	case VK_UP:
		keyRect.height += 1;
		break;
	case VK_DOWN:
		keyRect.height -= 1;
		if (keyRect.height &lt; 4) keyRect.height = 4;
		break;
	}

	keyRect.x = mouseX - keyRect.width / 2;
	keyRect.y = mouseY - keyRect.height / 2;

}

// Draw information about the mouse
// location, buttons pressed, etc
void drawMouseInfo()
{
	// draw a white banner across the bottom
	noStroke();
	fill(pWhite);
	rect(0, fb.frame.height + 2, width, 24);


	// draw the key rectangle
	fill(RGBA(255, 238, 200, 180));
	stroke(pDarkGray);
	rect(keyRect.x, keyRect.y, keyRect.width, keyRect.height);

	// select verdana font
	setFont(verdana17);
	char infobuff[256];
	sprintf_s(infobuff, "Mouse X: %3d Y: %3d    Key: (%3f, %3f)(%3.0f, %3.0f)", mouseX, mouseY, keyRect.x, 
		keyRect.y, keyRect.width, keyRect.height);
	fill(pBlack);
	textAlign(TX_LEFT, TX_TOP);
	text(infobuff, 0, fb.frame.height + 2);

}

void draw()
{
	background(pLightGray);
	backgroundImage(&fb);

	drawMouseInfo();
}

void setup()
{
	int ret = PPM_read_binary("c:/repos/graphicc/Test/windows-keyboard-60-keys.ppm", &fb);

	size(fb.frame.width+4, fb.frame.height+4+30);
	background(pLightGray);
}



Of particular note, and what this article is about, are the routines to track the mouse and keyboard actions. Let’s take the mouse movement first of all.

void  mousePressed()
{
	gMode++;
	if (gMode &gt;= gMaxMode) {
		gMode = 0;
	}
}

void  mouseMoved()
{
	keyRect.x = mouseX - keyRect.width / 2;
	keyRect.y = mouseY - keyRect.height / 2;
}

Basically, every time the mouse moves, the location of the ‘keyRect’ is updated, to reflect the new mouse position. In this case, we have the reported mouse position at the center of that translucent square.

Alright, but who’s calling these routines in the first place? For that we look at the mouse handling within drawproc.cpp


LRESULT CALLBACK mouseHandler(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam)
{
	switch (message)
	{
		case WM_MOUSEWHEEL:
			if (gmouseOnWheelHandler != nullptr) {
				gmouseOnWheelHandler(); // hWnd, message, wParam, lParam);
			}
		break;


		case WM_MOUSEMOVE:
			mouseX = GET_X_LPARAM(lParam);
			mouseY = GET_Y_LPARAM(lParam);

			if (isMousePressed) {
				if (gmouseOnDraggedHandler != nullptr) {
					gmouseOnDraggedHandler();
				}
			} else if (gmouseOnMovedHandler != nullptr) {
				gmouseOnMovedHandler();
			}
		break;

		case WM_LBUTTONDOWN:
		case WM_MBUTTONDOWN:
		case WM_RBUTTONDOWN:
			isMousePressed = true;
			mouseButton = wParam;

			if (gOnMousePressedHandler != nullptr) {
				gOnMousePressedHandler();
			}
		break;

		case WM_LBUTTONUP:
		case WM_MBUTTONUP:
		case WM_RBUTTONUP:
			isMousePressed = false;

			if (gmouseReleasedHandler != nullptr) {
				gmouseReleasedHandler();
			}
		break;

		default:
			return DefWindowProc(hWnd, message, wParam, lParam);
	}

	return 0;
}

Good good, looks like a typical “Windows” mouse handling routine. But, what of these various global variables?

		case WM_MOUSEMOVE:
			mouseX = GET_X_LPARAM(lParam);
			mouseY = GET_Y_LPARAM(lParam);

			if (isMousePressed) {
				if (gmouseOnDraggedHandler != nullptr) {
					gmouseOnDraggedHandler();
				}
			} else if (gmouseOnMovedHandler != nullptr) {
				gmouseOnMovedHandler();
			}
		break;

In this case, we have mouseX, mouseY, isMousePressed, gmouseOnDraggedHandler , and gmouseOnMovedHandler. That’s a lot of global state. Of particular interest are the two that point to functions, which are gmouseOnDraggedHandler, and gmouseOnMovedHandler. These routines are called whenever there is mouse movement. The one for dragging is called if the additional global variable ‘isMousePressed’ is true.

This is nice because we’re already getting a chance at being ‘dynamic’ because the function calls are not hard coded, which means, those pointers, although they may have started with some value at compile time, can changed dynamically any time during runtime. So, let’s see how they might get set.

Before any actions occur, as part of the initialization for the drawproc routines, there is this series of calls:

void init()
{
	// Setup text
	font_t_init(&gfont, verdana12);
	gTextSize = 10;
	gTextAlignX = TX_LEFT;
	gTextAlignY = TX_TOP;


	
	HMODULE modH = GetModuleHandle(NULL);

	// Keyboard handling routines
	setOnKeyPressedHandler((EventObserverHandler)GetProcAddress(modH, "keyPressed"));
	setOnKeyReleasedHandler((EventObserverHandler)GetProcAddress(modH, "keyReleased"));
	setOnKeyTypedHandler((EventObserverHandler)GetProcAddress(modH, "keyTyped"));

	setKeyboardHandler(keyHandler);


	// Mouse Handling Routines
	setOnMousePressedHandler((EventObserverHandler)GetProcAddress(modH, "mousePressed"));
	setOnMouseReleasedHandler((EventObserverHandler)GetProcAddress(modH, "mouseReleased"));
	setOnMouseMovedHandler((EventObserverHandler)GetProcAddress(modH, "mouseMoved"));
	setOnMouseDraggedHandler((EventObserverHandler)GetProcAddress(modH, "mouseDragged"));

	setMouseHandler(mouseHandler);
}

First of all, ‘GetModuleHandle’ is the way within Windows to get a handle on one of the libraries (.dll file) which may have been loaded into the program. If you pass “NULL” as the parameter, it will get the handle for the currently running program (the .exe file) itself. This is valuable to have because with this handle, you can make the ‘GetProcAddress’ call, with the name of a function, and get a pointer to that function. Once we have that pointer, we can set it on the global variable, and the rest we’ve already seen.

So that’s it, that’s the trick. The typical way of compiling with the drawproc library is to statically link your code with it. The drawproc library comes with a ‘main’, so all you have to do is implement various bits and pieces that might not already be there.

As we saw from the test_keyboard code, mousePressed, and mouseMoved are the only two of the 4 mouse routines that were implemented. How is that possible? Well, the others will be NULL, as they won’t be found in the library, and since they’re NULL, they simply won’t be called.

There is one trick though to making this work. The GetProcAddress will only work if the routines were marked for export when compiled. This is achieved using the following in the drawproc.h header:

#define DPROC_API		__declspec(dllexport)

// IO Event Handlers
DPROC_API void keyPressed();
DPROC_API void keyReleased();
DPROC_API void keyTyped();


DPROC_API void mousePressed();
DPROC_API void mouseMoved();
DPROC_API void mouseDragged();
DPROC_API void mouseReleased();

This will essentially create function declarations for the functions we intend to implement. If your test code includes ‘drawproc.h’, and then you implement any of these routines, they will automatically be ‘exported’ when the whole is compiled. This will make it possible for them to be picked up during the ‘init()’ process, and thereby setting those global variables. This is also true of the ‘setup()’ and ‘draw()’ routines.

This is a great little trick, when you’re linking statically against the library. Another way to do it would be to put your code into a separate .dll, and run a drawproc.exe host program, giving the name of your .dll as a parameter. Then the library could be dynamically loaded, and the same hookup of routines could occur. The advantage of that setup is that you don’t need to create an entirely new .exe file for each of your test programs. Just produce the .dll. The disadvantage is you get stuck in a state when the runtime changes, and your .dll files no longer match.

So, there you have it, some amount of ‘dynamic’ programming in the little graphics engine that could, using ‘C’, which is certainly capable of supporting this pattern of dynamic programming.


graphicc – presenting a graph

The latest graphicc library is shaping up to be an almost useful thing.

The only way I know how to ensure a library actually serves a purpose is to build applications upon it.  This installment is about that sort of thing.  But first, a look at some more text.  This is basically text alignment working in graphicc.

test_text

The little bit of code that’s doing this looks like this.

void draw()
{
	background(pLightGray);

	// Draw some lines
	stroke(pBlack);
	line(width / 2, 0, width / 2, height - 1);
	line(0, height / 2, width - 1, height / 2);

	// draw some text
	int midx = width / 2;
	int midy = height / 2;
	fill(pBlack);
	textAlign(TX_LEFT);
	text("LEFT", midx, 20);
	
	textAlign(TX_CENTER);
	text("CENTER", midx, 40);
	
	textAlign(TX_RIGHT);
	text("RIGHT", midx, 60);

	// Around the center
	textAlign(TX_LEFT, TX_TOP);
	text("LEFT TOP", 0, 0);

	textAlign(TX_RIGHT, TX_TOP);
	text("RIGHT TOP",width,0);

	textAlign(TX_RIGHT, TX_BOTTOM);
	text("RIGHT BOTTOM", width,height);

	textAlign(TX_LEFT, TX_BOTTOM);
	text("LEFT BOTTOM",0,height);

	stroke(pRed);
	line(midx - 6, midy, midx + 6, midy);
	line(midx, midy - 6, midx, midy + 6);

	fill(pWhite);
	textAlign(TX_CENTER, TX_CENTER);
	text("CENTER CENTER", midx, midy);
}

But wait, this is high level stateful graphics sort of stuff, not the low level raw graphicc API. Yep, that’s right. Along the way of creating the lower level stuff, I’ve been nursing along what I call ‘drawproc’. This is essentially an interface that looks and feels very similar to the popular Processing.org environment, but it’s for C/C++ instead of Java. I also have a skin for PHIGS, but this one is a lot further along, and used constantly for test cases.

In order to work the drawproc API, and thus the low level graphicc routines, I’m going through a book on Processing: Visualizing Data which shows a lot of techniques for visualizing data sets using Processing. And here are the fruits of following one particular chapter:

timeseries

Nice usage of text, alignment, lines, rectangles, tiny circles, different sized  text, and all that.  If you were doing the interactive app, you could flip between Milk, Tea, and Coffee graphs.  The drawproc along with a shim for win32, give you keyboard and mouse control as well, so doing some interactive hover effects and the like is possible.

It’s a kind of funny thing.  In these days of HTML rendering, how could there possibly be any other way to do UI?  Well, HTML is the answer in many cases, but not all.  Having a small tight graphics library that can allow you to build interactive apps quickly and easily is still a useful thing.  Besides, it’s just plain fun.

Now that I’ve got a reasonable set of core graphics routines, I contemplated what it would be like to write a remote UI sort of thing for cloud based VMs.  Basically, just put some little engine on the VM which receives drawing commands, and allow that to be connected to via some port, which also sends/receives key and mouse stuff.  Well, isn’t that what ‘X’ does?  Yah, and a whole lot more!  Well then, surely VNC has got it covered?  Yes, as long as you’re already running X.  But, it’s a challenge.  Can I write such a small service in less than 1Mb of code?  Maybe 2Mb just to be safe?  Of course you’d have to write apps on the server side that talk to the graphics server, but that shouldn’t be too hard.  Just pick an API skin, like Processing, or GDI, or whatever, and send all the commands to the service, which will render into a buffer to be served up to whomever is looking.

One can dream…


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.


Drawing Curvy Lines with aplomb – Beziers

I have written plenty about Bezier and other curves and surfaces.  That was largely in the context of 3D printing using OpenScad, or BanateCad.  But now, I’m adding to a general low level graphics library.

test_bezier

Well well, what do we have here.  Bezier curves are one of those constructs where you lay down some ‘control points’ and then draw a line that meanders between them according to some mathematical formula.  In the picture, the green curve is represented by 4 control points, the red one is represented by 5 points, and the blue ones are each represented by 4 points.

How do you construct a Bezier curve?  Well, you don’t need much more than the following code:

void computeCoefficients(const int n, int * c)
{
	int k, i;

	for (k = 0; k <= n; k++)
	{
		// compute n!/(k!(n-k)!)
		c[k] = 1;
		for (i = n; i >= k + 1; i--)
		{
			c[k] *= i;
		}

		for (i = n - k; i >= 2; i--)
		{
			c[k] /= i;
		}
	}
}

void computePoint(const float u, Pt3 * pt, const int nControls, const Pt3 *controls, const int * c)
{
	int k;
	int n = nControls - 1;
	float blend;

	pt->x = 0.0;	// x
	pt->y = 0.0;	// y
	pt->z = 0.0;	// z
	
	// Add in influence of each control point
	for (k = 0; k < nControls; k++){
		blend = c[k] * powf(u, k) *powf(1 - u, n - k);
		pt->x += controls[k].x * blend;
		pt->y += controls[k].y * blend;
		pt->z += controls[k].z * blend;
	}
}

void bezier(const Pt3 *controls, const int nControls, const int m, Pt3 * curve)
{
	// create space for the coefficients
	int * c = (int *)malloc(nControls * sizeof(int));
	int i;

	computeCoefficients(nControls - 1, c);
	for (i = 0; i <= m; i++) {
		computePoint(i / (float)m, &curve[i], nControls, controls, c);
	}
	free(c);	
}

This is pretty much the same code you would get from any book or tutorial on fundamental computer graphics. It will allow you to calculate a Bezier curve using any number of control points.

Here’s the test case that generated the picture

typedef struct {
	REAL x;
	REAL y;
	REAL z;
} Pt3;

void polyline(pb_rgba *pb, Pt3 *curve, const int nPts, int color)
{
	for (int idx = 0; idx < nPts; idx++) {
		raster_rgba_line(pb, curve[idx].x, curve[idx].y, curve[idx + 1].x, curve[idx + 1].y, color);
	}
}

void test_bezier()
{

	size_t width = 400;
	size_t height = 400;
	int centerx = width / 2;
	int centery = height / 2;
	int xsize = (int)(centerx*0.9);
	int ysize = (int)(centery*0.9);

	pb_rgba pb;
	pb_rgba_init(&pb, width, height);

	// background color
	raster_rgba_rect_fill(&pb, 0, 0, width, height, pLightGray);

	// One curve drooping down
	Pt3 controls[4] = { { centerx - xsize, centery, 0 }, { centerx, centery + ysize, 0 }, { centerx, centery + ysize, 0 }, { centerx + xsize, centery, 0 } };
	int nControls = 4;
	int m = 60;
	Pt3 curve[100];
	bezier(controls, nControls, m, curve);
	polyline(&pb, curve, m, pGreen);

	// Several curves going up
	for (int offset = 0; offset < ysize; offset += 5) {
		Pt3 ctrls2[4] = { { centerx - xsize, centery, 0 }, { centerx, centery - offset, 0 }, { centerx, centery - offset, 0 }, { centerx + xsize, centery, 0 } };
		bezier(ctrls2, nControls, m, curve);
		polyline(&pb, curve, m, pBlue);
	}

	// one double peak through the middle
	Pt3 ctrls3[5] = { { centerx - xsize, centery, 0 }, { centerx-(xsize*0.3f), centery + ysize, 0 }, { centerx, centery - ysize, 0 }, { centerx+(xsize*0.3f), centery + ysize, 0 }, { centerx + xsize, centery, 0 } };
	int nctrls = 5;
	bezier(ctrls3, nctrls, m, curve);
	polyline(&pb, curve, m, pRed);

	// Now we have a simple image, so write it to a file
	int err = write_PPM("test_bezier.ppm", &pb);
}

From here, there are some interesting considerations. For example, you don’t want to calculate the coefficients every single time you draw a single curve. In terms of computer graphics, most Bezier curves consist of 3 or 4 points at most. Ideally, you would calculate the coefficients for those specific curves and store the values statically for later usage. This is what you’d do ideally for a small embedded library. The tradeoff in storage space is well worth the savings in compute time.

Additionally, instead of calculating all the line segments and then storing those values and using a polyline routine to draw things, you’d like want to simply have the bezier routine draw the lines directly. That would cut down on temporary allocations.

At the same time though, you want to retain the ‘computePoint’ function as independent because once you have a Bezier calculation function within the library, you’ll want to use it to do things other than just draw curved lines. Bezier, and it’s corollary Hermite, are good for calculating things like color ramps, motion, and other curvy stuff. This is all of course before you start using splines and nurbs, which are much more involved process.

There you have it, a couple of functions, and suddenly you have Bezier curves based on nothing more than the low level line drawing primitives. At the moment, this code sits in a test file, but soon enough I’ll move it into the graphicc library proper.


GraphicC – The triangle’s the thing

Pixels, lines, and squares, oh my!
test_triangle

And, finally, we come to triangles.  The demo code is thus:

#include "test_common.h"

void test_writebitmap()
{
	size_t width = 480;
	size_t height = 480;
	pb_rgba pb;
	pb_rgba_init(&pb, width, height);

	// Draw some triangles 
	size_t midx = (size_t)(width / 2);
	size_t midy = (size_t)(height / 2);

	raster_rgba_triangle_fill(&pb, 0, 0, width-1, 0, midx, midy, pRed);
	raster_rgba_triangle_fill(&pb, 0, 0, midx, midy, 0, height-1, pGreen);
	raster_rgba_triangle_fill(&pb, width-1, 0, midx, midy, width-1, height - 1, pBlue);
	raster_rgba_triangle_fill(&pb, midx, midy, 0, height-1, width - 1, height - 1, pDarkGray);

	// Now we have a simple image, so write it to a file
	int err = write_PPM("test_triangle.ppm", &pb);
}

int main(int argc, char **argv)
{
	test_writebitmap();

	return 0;
}

Why triangles? Well, beyond pixels, and lines, they are one of the most useful drawing primitives. When it finally comes to rendering in 3D for example, it will all be about triangles. Graphics hardware over the years has been optimized to render triangles as well, so it is beneficial to focus more attention to this primitive than to any other. You might think polygons are very useful, but, all polygons can be broken down into triangles, and we’re back where we started.

Here’s the triangle drawing routine:

#define swap16(a, b) { int16_t t = a; a = b; b = t; }

typedef struct _point2d
{
	int x;
	int y;
} point2d;

int FindTopmostPolyVertex(const point2d *poly, const size_t nelems)
{
	int ymin = INT32_MAX;
	int vmin = 0;

	size_t idx = 0;
	while (idx < nelems) {
		if (poly[idx].y < ymin) {
			ymin = poly[idx].y;
			vmin = idx;
		}
		idx++;
	}

	return vmin;
}

void RotateVertices(point2d *res, point2d *poly, const size_t nelems, const int starting)
{
	size_t offset = starting;
	size_t idx = 0;
	while (idx < nelems) {
		res[idx].x = poly[offset].x;
		res[idx].y = poly[offset].y;
		offset++;
		
		if (offset > nelems-1) {
			offset = 0;
		}

		idx++;
	}
}

void sortTriangle(point2d *sorted, const int x1, const int y1, const int x2, const int y2, const int x3, const int y3)
{
	point2d verts[3] = { { x1, y1 }, { x2, y2 }, { x3, y3 } };

	int topmost = FindTopmostPolyVertex(verts, 3);
	RotateVertices(sorted, verts, 3, topmost);
}

void raster_rgba_triangle_fill(pb_rgba *pb, 
	const unsigned int x1, const unsigned int  y1, 
	const unsigned int  x2, const unsigned int  y2, 
	const unsigned int  x3, const unsigned int  y3, 
	int color)
{
	int a, b, y, last;

	// sort vertices, such that 0 == y with lowest number (top)
	point2d sorted[3];
	sortTriangle(sorted, x1, y1, x2, y2, x3, y3);

	// Handle the case where points are colinear (all on same line)
	if (sorted[0].y == sorted[2].y) { 
		a = b = sorted[0].x;
		
		if (sorted[1].x < a) 
			a = sorted[1].x;
		else if (sorted[1].x > b) 
			b = sorted[1].x;

		if (sorted[2].x < a) 
			a = sorted[2].x;
		else if (sorted[2].x > b) 
			b = sorted[2].x;

		raster_rgba_hline(pb, a, sorted[0].y, b - a + 1, color);
		return;
	}

	int16_t
		dx01 = sorted[1].x - sorted[0].x,
		dy01 = sorted[1].y - sorted[0].y,
		dx02 = sorted[2].x - sorted[0].x,
		dy02 = sorted[2].y - sorted[0].y,
		dx12 = sorted[2].x - sorted[1].x,
		dy12 = sorted[2].y - sorted[1].y;
	
	int32_t sa = 0, sb = 0;

	// For upper part of triangle, find scanline crossings for segments
	// 0-1 and 0-2. If y1=y2 (flat-bottomed triangle), the scanline y1
	// is included here (and second loop will be skipped, avoiding a /0
	// error there), otherwise scanline y1 is skipped here and handled
	// in the second loop...which also avoids a /0 error here if y0=y1
	// (flat-topped triangle).
	if (sorted[1].y == sorted[2].y) 
		last = sorted[1].y; // Include y1 scanline
	else 
		last = sorted[1].y - 1; // Skip it
	
	for (y = sorted[0].y; y <= last; y++) 
	{
		a = sorted[0].x + sa / dy01;
		b = sorted[0].x + sb / dy02;
		sa += dx01;
		sb += dx02;
		/* longhand:
		a = x0 + (x1 - x0) * (y - y0) / (y1 - y0);
		b = x0 + (x2 - x0) * (y - y0) / (y2 - y0);
		*/
		
		if (a > b) swap16(a, b);
		raster_rgba_hline(pb, a, y, b - a + 1, color);
	}

	// For lower part of triangle, find scanline crossings for segments
	// 0-2 and 1-2. This loop is skipped if y1=y2.
	sa = dx12 * (y - sorted[1].y);
	sb = dx02 * (y - sorted[0].y);
	for (; y <= sorted[2].y; y++) 
	{
		a = sorted[1].x + sa / dy12;
		b = sorted[0].x + sb / dy02;
		sa += dx12;
		sb += dx02;
		/* longhand:
		a = x1 + (x2 - x1) * (y - y1) / (y2 - y1);
		b = x0 + (x2 - x0) * (y - y0) / (y2 - y0);
		*/
		if (a > b) 
			swap16(a, b);

		raster_rgba_hline(pb, a, y, b - a + 1, color);
	}
}

This seems like a lot of work to simply draw a triangle! There are lots of routines for doing this. This particular implementation borrows from a couple of different techniques. The basic idea is to first sort the vertices in scaline order, top to bottom. That is, we want to known which vertex to start from because we’re going to follow an edge down the framebuffer, drawing lines between edges as we go. In a regular triangle, without a flat top or bottom, there will be a switch between driving edges as we encounter the third point somewhere down the scan lines.

At the end, the ‘raster_rgba_hline’ function is called to actually draw a single line. If we wanted to do blending, we’d change this line. If we wanted to use a color per vertex, it would ultimately be dealt with here. All possible. Not necessary for the basic routine. With some refactoring, this could be made more general purpose, and different rendering modes could be included.

This is the only case where I use a data structure, to store the sorted points. Most of the time I just pass parameters and pointers to parameters around.

This is also a good time to mention API conventions. One of the constraints from the beginning is the need to stick with basic C constructs, and not get too fancy. In some cases this is at the expense of readability, but in general things just work out ok, as it’s simple to get used to. So, let’s look at the API here:

void raster_rgba_triangle_fill(pb_rgba *pb, 
	const unsigned int x1, const unsigned int  y1, 
	const unsigned int  x2, const unsigned int  y2, 
	const unsigned int  x3, const unsigned int  y3, 
	int color)

That’s a total of 8 parameters. If I were going for absolute speed, and I knew the platform I was running on, I might try to limit the parameters to 4, to help ensure they get passed in registers, rather than requiring the use of a stack. But, that’s an optimization that’s iffy at best, so I don’t bother. And why not use some data structures? Clearly x1, y1 is a 2D point, so why not use a ‘point’ data structure. Surely where the data comes from is structured as well. In some cases it is, and in others it is not. I figure that in the cases where the data did come from a structure, it’s fairly easy for the caller to do the dereferencing and pass in the values directly. In the cases where the data did not come from a point structure, it’s a tax to pay to stuff the data into a point structure, simply to have it pass in to a function, which may not need it in that form. So, in general, all the parameters are passed in a ‘denormalized’ form. With small numbers of easy to remember parameters, I think this is fine.

Also, I did decide that it was useful to use ‘const’ in most cases where that is applicable.  This gives the compiler some hints as to how best deal with the parameters, and allows you to specify constants inline for test cases, without compiler complaints.

There is a decided lack of error handling in most of these low level APIs.  You might think that triangle drawing would be an exception.  Shouldn’t I do some basic clipping to the framebuffer?  The answer is no, not at this level.  At a higher level, we might be drawing something larger, where a triangle is but a small part.  At that higher level we’ll know about our framebuffer, or other constraints that might cause clipping of a triangle.  At that level, we can perform the clipping, and send down new sets of triangles to be rendered by this very low level triangle drawing routine.

Of course, this routine could be made even more raw and optimized by breaking out the vertex sorting from the edge following part.  If the triangle vertices don’t change, there’s no need to sort them every time they are drawn, so making the assumption that the vertices are already in framebuffer height order can dramatically simplify the drawing portion.  Then, the consumer can call the sorting routines when they need to, and pass in the sorted vertex values.

And thus APIs evolve.  I’ll wait a little longer before making such changes as I might think of other things that I want to improve along the way.

There you have it then.  From pixels to triangles, the basic framebuffer drawing routines are now complete.  What more could be needed at this level?  Well, dealing with some curvy stuff, like ellipses and rounded rectangles might be nice, all depends on what use cases are more interesting first, drawing pies and graphs, or doing some UI stuff.  The first thing I want to do is display some data related to network traffic events, so I think I’ll focus on a little bit of text rendering first, and leave the ellipse and rounded rects for later.

So, next time around, doing simple bitmap text.


GraphicC – Random Lines

Thus far, I’ve been able to draw individual pixels, some rectangles, straight vertical and horizontal lines.  Now it’s time to tackle those lines that have an arbitrary slope.

test_writebitmap

In this case, we’re only interested in the line drawing, not the rectangles and triangles.  Here’s the example code:

 

#include &quot;test_common.h&quot;

void test_writebitmap()
{
	size_t width = 480;
	size_t height = 480;
	pb_rgba pb;
	pb_rgba_init(&amp;pb, width, height);


	// draw horizontal lines top and bottom
	raster_rgba_hline(&amp;pb, 0, 0, width - 1, pWhite);
	raster_rgba_hline(&amp;pb, 0, height - 1, width - 1, pWhite);

	// draw vertical lines left and right
	raster_rgba_vline(&amp;pb, 0, 0, height - 1, pGreen);
	raster_rgba_vline(&amp;pb, width - 1, 0, height - 1, pTurquoise);

	// draw criss cross lines
	raster_rgba_line(&amp;pb, 0, 0, width - 1, height - 1, pRed);
	raster_rgba_line(&amp;pb, width - 1, 0, 0, height - 1, pYellow);

	// draw a couple of rectangles
	raster_rgba_rect_fill(&amp;pb, 5, 5, 60, 60, pLightGray);
	raster_rgba_rect_fill(&amp;pb, width - 65, height - 65, 60, 60, pLightGray);

	// draw a rectangle in the center
	pb_rgba fpb;
	pb_rgba_get_frame(&amp;pb, (width / 2) - 100, (height / 2) - 100, 200, 200, &amp;fpb);
	raster_rgba_rect_fill(&amp;fpb, 0, 0, 200, 200, pBlue);

	// Draw triangle 
	raster_rgba_triangle_fill(&amp;pb, 0, height - 10, 0, 10, (width / 2) - 10, height / 2, pGreen);

	// Now we have a simple image, so write it to a file
	int err = write_PPM(&quot;test_writebitmap.ppm&quot;, &amp;pb);

}

int main(int argc, char **argv)
{
	test_writebitmap();

	return 0;
}

This is the part we’re interested in here:

	// draw criss cross lines
	raster_rgba_line(&amp;pb, 0, 0, width - 1, height - 1, pRed);
	raster_rgba_line(&amp;pb, width - 1, 0, 0, height - 1, pYellow);

Basically, feed in x1, y1, x2, y2 and a color, and a line will be drawn. The operation is SRCCOPY, meaning, the color is not blended, it just lays over whatever is already there. And the line drawing routine itself?

#define sgn(val) ((0 &lt; val) - (val &lt; 0))

// Bresenham simple line drawing
void raster_rgba_line(pb_rgba *pb, unsigned int x1, unsigned int y1, unsigned int x2, unsigned int y2, int color)
{
	int dx, dy;
	int i;
	int sdx, sdy, dxabs, dyabs;
	unsigned int x, y, px, py;

	dx = x2 - x1;      /* the horizontal distance of the line */
	dy = y2 - y1;      /* the vertical distance of the line */
	dxabs = abs(dx);
	dyabs = abs(dy);
	sdx = sgn(dx);
	sdy = sgn(dy);
	x = dyabs &gt;&gt; 1;
	y = dxabs &gt;&gt; 1;
	px = x1;
	py = y1;

	pb_rgba_set_pixel(pb, x1, y1, color);

	if (dxabs &gt;= dyabs) /* the line is more horizontal than vertical */
	{
		for (i = 0; i&lt;dxabs; i++)
		{
			y += dyabs;
			if (y &gt;= (unsigned int)dxabs)
			{
				y -= dxabs;
				py += sdy;
			}
			px += sdx;
			pb_rgba_set_pixel(pb, px, py, color);
		}
	}
	else /* the line is more vertical than horizontal */
	{
		for (i = 0; i&lt;dyabs; i++)
		{
			x += dxabs;
			if (x &gt;= (unsigned int)dyabs)
			{
				x -= dyabs;
				px += sdx;
			}
			py += sdy;
			pb_rgba_set_pixel(pb, px, py, color);
		}
	}
}

This is a fairly simple implementation of the well known Bresenham line drawing algorithm. It may no longer be the fastest in the world, but it’s fairly effective and compoutationally simple. If we wanted to do a blend of colors, then the ‘pb_rgba_set_pixel’ could simple be replaced with the blending routine that we saw in the other line drawing routines.

And that’s that. You could implement this as EFLA, or any number of other routines that might prove to be faster. But, why optimize too early? It might be that memory access is the bottleneck, and not the simple calculations done here. Bresenham is also fairly nice because everything is simple integer arithmetic, which is both fairly fast, as well as easy to implement on an FPGA, if it comes to that. Certainly on a microcontroller, it would be preferred to float/double.

Why we’re at it, how about that bitmap writing to file routine?

	int err = write_PPM(&quot;test_writebitmap.ppm&quot;, &amp;pb);

I’ve seen plenty of libraries that spend an inordinate amount of lines of code on the simple image load/save portion of things. That can easily dominate anything else you do. I didn’t want to really pollute the basic codebase with all that, so I chose the ‘ppm’ format as the only format that the library speaks natively. It’s a good ol’ format, nothing fancy, basic RGB dump of values, with some text at the beginning to describe the format of the image. The routine looks like this:

pbm.h

#pragma once

#ifndef PBM_H
#define PBM_H

#include &quot;pixelbuffer.h&quot;

#ifdef __cplusplus
extern &quot;C&quot; {
#endif

int write_PPM(const char *filename, pb_rgba *fb);

#ifdef __cplusplus
}
#endif

#endif

pbm.cpp

#include "pbm.h"

#include 

#pragma warning(push)
#pragma warning(disable: 4996)	// _CRT_SECURE_NO_WARNINGS (fopen) 


int write_PPM(const char *filename, pb_rgba *fb)
{
	FILE * fp = fopen(filename, "wb");
	
	if (!fp) return -1;

	// write out the image header
	fprintf(fp, "P6\n%d %d\n255\n", fb-&gt;frame.width, fb-&gt;frame.height);
	
	// write the individual pixel values in binary form
	unsigned int * pixelPtr = (unsigned int *)fb-&gt;data;

	for (size_t row = 0; row frame.height; row++) {
		for (size_t col = 0; col frame.width; col++){
			fwrite(&amp;pixelPtr[col], 3, 1, fp);
		}
		pixelPtr += fb-&gt;pixelpitch;
	}


	fclose(fp);

	return 0;
}

#pragma warning(pop)

There are lots of different ways to do this, but basically, get a pointer to the pixel values, and write out the RGB portion (ignoring the Alpha portion). The first line written is in plaintext, and it tells the format ‘P6’, followed by the width and height of the image. And that’s that. The internal format of a framebuffer is fairly simple, so writing a whole library that can read and write things like GIF, PNG, JPG and the like can be done fairly easily, and independently of the core library. And that’s probably the best way to do it. Then the consumer of this library isn’t forced to carry along complexity they don’t need, but they can simply compose what is necessary for their needs.

Alright then. There is one more primitive, the triangle, which will complete the basics of the drawing routines. So, next time.


GraphicC – Who’s line is it?

test_linespan

After pixels, drawing lines are probably the next most useful primitive in a graphics system.  Perhaps bitblt is THE most useful, but lines are certain up there.  There are a few things going on in the picture above, so I’m going to go through them bit by bit.

This is the code that does it:

#include "test_common.h"

void test_linespan()
{
	size_t width = 320;
	size_t height = 240;
	pb_rgba pb;
	pb_rgba_init(&pb, width, height);


	// Set a white background
	raster_rgba_rect_fill(&pb, 0, 0, width, height, pWhite);

	// do a horizontal fade
	int color1 = RGBA(127, 102, 0, 255);
	int color2 = RGBA(0, 127, 212, 255);

	for (size_t row = 0; row < 100; row++) {
		int x1 = 0;
		int x2 = width - 1;
		raster_rgba_hline_span(&pb, x1, color1, x2, color2, row);
	}

	// Draw a button looking thing
	// black
	raster_rgba_hline(&pb, 20, 20, 80, pBlack);
	raster_rgba_hline(&pb, 20, 21, 80, pDarkGray);
	raster_rgba_hline(&pb, 20, 22, 80, pLightGray);


	// light gray rect
	raster_rgba_rect_fill(&pb, 20, 23, 80, 24, pLightGray);

	// fade to black
	for (size_t col = 20; col < 100; col++) {
		raster_rgba_vline_span(&pb, 46, pLightGray, 77, pBlack, col);
	}

	// Draw some blended lines atop the whole
	for (size_t row = 35; row < 120; row++){
		raster_rgba_hline_blend(&pb, 45, row, 100, RGBA(0, 153, 153, 203));
	}

	// Now we have a simple image, so write it to a file
	int err = write_PPM("test_linespan.ppm", &pb);

}



int main(int argc, char **argv)
{
	test_linespan();

	return 0;
}

In most graphics systems, there are three kinds of lines;

  • horizontal
  • vertical
  • sloped

Along with the kind of line, there are typically various attributes such as thickness, color,
and in the case of joined lines, what kind of joinery (butted, mitered, rounded).

At the various lowest level though, there are simply lines, and the things I focus on are slopes and colors.

There are two basic lines kinds that are of particular interest right off the bat, those are horizontal and vertical.  They are special cases because their drawing can be easily optimized, and if you have any acceleration hardware, these are most likely included.  This kinds of brings up another design desire.

  • Can be implemented in an fpga

But, that’s for a much later time.  For now, how about those horizontal and vertical lines?
If what you want is a solid line, of a single color, ignoring any transparency, then you want a simple hline:

int raster_rgba_hline(pb_rgba *pb, unsigned int x, unsigned int y, unsigned int length, int value)
{
	size_t terminus = x + length;
	x = x < 0 ? 0 : x;
	terminus = terminus - x;

	unsigned int * data = &((unsigned int *)pb->data)[y*pb->pixelpitch+x];
	size_t count = 1;
	for (size_t idx = 0; idx < terminus; idx++)
	{
		*data = value;
		data++;
	}

	return 0;
}

This makes a simple rectangle easy to implement as well:

#define raster_rgba_rect_fill(pb, x1, y1, width, height, value) for (size_t idx = 0; idx < height; idx++){raster_rgba_hline(pb, x1, y1 + idx, width, value);	}

Simple single color horizontal lines can be drawn quickly, often times using some form of memset
on the host platform. Even in the case where a tight inner loop is used, what appears to be
fairly slow can be quite fast depending on how your compiler optimizes things.

There is a corresponding ‘vline’ routine that does similar.

int raster_rgba_vline(pb_rgba *pb, unsigned int x, unsigned int y, unsigned int length, int value)
{
    unsigned int * data = &((unsigned int *)pb->data)[y*pb->frame.width + x];
    size_t count = 1;
    while (count <= length) {
        *data = value;
        data += pb->pixelpitch;
        count++;
    }

    return 0;
}

Here, the same basic assignment is used, after determining the starting offset of the first
pixel. The pointer is advanced by the pixelpitch, which in this case is the count of 32-bit
integer values per row. If you’re rendering into a framebuffer that doesn’t conform to this,
then this offset can be adjusted accordingly.

Horizontal and vertical lines of a solid color are nice, and can go a long way towards satisfying
some very basic drawing needs. But, soon enough you’ll want those lines to do a little bit more
work for you.

void raster_rgba_hline_span(pb_rgba *pb, int x1, int color1, int x2, int color2, int y)
{
    int xdiff = x2 - x1;
    if (xdiff == 0)
        return;

    int c1rd = GET_R(color1);
    int c1gr = GET_G(color1);
    int c1bl = GET_B(color1);

    int c2rd = GET_R(color2);
    int c2gr = GET_G(color2);
    int c2bl = GET_B(color2);

    int rdx = c2rd - c1rd;
    int gdx = c2gr - c1gr;
    int bdx = c2bl - c1bl;

    float factor = 0.0f;
    float factorStep = 1.0f / (float)xdiff;

    // draw each pixel in the span
    for (int x = x1; x < x2; x++) {
        int rd = c1rd + (int)(rdx*factor);
        int gr = c1gr + (int)(gdx*factor);
        int bl = c1bl + (int)(bdx*factor);
        int fg = RGBA(rd, gr, bl, 255);
        pb_rgba_set_pixel(pb, x, y, fg);

        factor += factorStep;
    }
}

Let’s imagine you want to draw that fade from green to blue. You could do it pixel by pixel,
but it’s nice to have a simple line drawing routine that does it for you.

The ‘raster_rgba_hline_span’ routine takes two colors, as well as the x1, x2, and y values. It
will draw a horizontal line between x1 and x2 (inclusive), going from color1, to color2 in a
linear fashion. Same goes for the corresponding vline_span routine. This is nice and simple.
You could modify it a bit to change the parameters that are passed in, and fuss with trying to
optimize the loop in various ways, but this basically works.

Great, we have solid lines, line spans with color fading, what about transparency?

The individual pixels are represented with 32-bits each. There are 8-bits each for R, G, and B
color components. The ‘A’ portion of the color is not used by the frame buffer, but rather used
to represent an opacity value. The opacity just determines how much of the color will be shown
if this color is blended with another color.

In the picture above, the turquoise rectangle is blended with the pixels that are below, rather
than just copying its pixels atop the others.

In order to do that, we want to draw some horizontal lines, but we want to blend the colors
instead of copy them:

// Draw some blended lines atop the whole
for (size_t row = 35; row < 120; row++)
{
    raster_rgba_hline_blend(&pb, 45, row, 100, RGBA(0, 153, 153, 203));
}

The ‘raster_rgba_hline_blend’ routine does the needful. It takes a color with an alpha (opacity)
value of 203, and blends that with whatever is already in the specified frame buffer. It looks
like this:

#define blender(bg, fg, a) ((uint8_t)((fg*a+bg*(255-a)) / 255))

#define blend_color(bg, fg) RGBA(                \
    blender(GET_R(bg), GET_R(fg), GET_A(fg)),    \
    blender(GET_G(bg), GET_G(fg), GET_A(fg)),    \
    blender(GET_B(bg), GET_B(fg), GET_A(fg)),    255)


int raster_rgba_hline_blend(pb_rgba *pb, unsigned int x, unsigned int y, unsigned int length, int value)
{
    size_t terminus = x + length;
    x = x < 0 ? 0 : x;
    terminus = terminus - x;

    unsigned int * data = &((unsigned int *)pb->data)[y*pb->pixelpitch + x];
    size_t count = 1;
    for (size_t idx = 0; idx < terminus; idx++)
    {
        int bg = *data;
        int fg = value;

        *data = blend_color(bg, fg);
        data++;
    }

    return 0;
}

The use of macros here keeps the operations straight, and provides easy routines that can be used elsewhere.
It’s a pretty straight forward process though. Each time through the inner loop, the ‘bg’
represents the ‘background’ color, which is taken from the pixel buffer. The ‘fg’ value
represents the color that the user passed in. The new value is a blend of the two, using
the alpha component of the foreground color.

This is a fairly basic routine that can be adapted in many ways. For example, instead of
using the alpha value from the foreground color, you could just pass in a fixed alpha value
to be applied. This is useful when doing something like a ‘fade to black’, without having to
alter each of the source colors directly.

This particular routine only works with solid colors. As such, it is just like the plain
hline routine. So why not have a flag on the hline routine that says to do a blend or not?
Better still, why not have a parameter which is an operation to perform between the bg and fg
pixel values? This is how a lot of libraries work, including good ol’ GDI. I think that overly
complicates matters though. Creating a general purpose routine will introduce a giant switch
statement, or a bunch of function pointers, or something else unworldly. For now, I know I need
only two operators, SRCOPY, SRCOVER, and that’s it, I don’t currently find need for more exotic
operators. But of course, anything can be built atop or easily changed, so who knows.

And that’s about it for the first two kinds of line drawing routines. The third kind, where the
slope is neither vertical nor horizontal, is a little more work, and thus will be saved for
another time.

Woot! Raise the roof up, horizontal and vertical lines, along with pixel copying. What more
could you possibly expect from a basic low level graphics system? Well, for the longest time,
not much more than this, but there’s still some modern conveniences to discuss, such as those
sloped lines, and some more primitives such as triangles.


GraphicC – The Basics

There is one more design constraint I did not mention last time, and it’s a fairly important one for my purposes.

  • Must be easily interfaced from scripting environments

In my particular case, I’m going to favor LuaJIT and its FFI mechanism, and JavaScript, in the form of node.js.  At the very least, this means that I should not utilize too many fancy features, such as classes, operator or function overloading, templates, and the like.  These things are just nasty to deal with from script, and not really worth the benefits in such a small system.  Sticking to C89, or C99 style conventions, at least for the parts that are intended to be publicly accessible, is a good idea.

With that, how about looking at some of the basics.  First up, the most basic thing is the representation of a pixel.  For me, there is a very clear separation between a pixel and a color.  A pixel is a machine representation of a color value.  It is typically in a form that the graphics card can render directly.  Modern day representations are typically RGBA, or RGB, or BGR, BGRA.  That is, one value between 0-255 for each of the color components.  These values are arranged one way or the other, but these are the most typical.  Of course with most modern graphics cards, and leveraging an API such as OpenGL or DirectX, your pixel values can be floats, and laid out in many other forms.  But, I’ll ignore those for now.

Pixel values are constrained in a way, because they are represented by a limited set of byte values.  Colors are a completely different animal.  Then you get into various color spaces such as Cie, or XYZ, or HSL.  They all have their uses depending on the application space you’re in.  In the end though, when you want to display something, you’ve got to convert from those various color spaces to the RGB pixel values that this graphics system can support.

Since I am dealing with pixel values (and not colors), the very lowest level routines deal with pixel buffers, or pixel frames.  That is an array of pixel values.  Simple as that.

typedef struct _pix_rgba {
	unsigned char r, g, b, a;
} pix_rgba;

// On a little endian machine
// Stuff it such that 
// byte 0 == red
// byte 1 == green
// byte 2 == blue
// byte 3 == alpha
#define RGBA(r,g,b,a) ((unsigned int)(a<<24|b<<16|g<<8|r))
#define GET_R(value) ((unsigned int)value &0xff)
#define GET_G(value) (((unsigned int)value &0xff00) >> 8)
#define GET_B(value) (((unsigned int)value &0xff0000) >> 16)
#define GET_A(value) (((unsigned int)value &0xff000000) >> 24)

// pixel buffer rectangle
typedef struct _pb_rect {
	unsigned int x, y, width, height;
} pb_rect;

typedef struct _pb_rgba {
	unsigned char *		data;
	unsigned int		pixelpitch;
	int					owndata;
	pb_rect				frame;
} pb_rgba;

The ‘pb-rgba’ structure is the base of the drawing system. This is the drawing ‘surface’ if you will. It is akin to the ‘framebuffer’ if you were doing graphics in hardware. Things can only be a certain way. The buffer has a known width, height, and number of bytes per row. So far there is only one defined pixel buffer rectangle type, and that supports the rgba layout. I could create different pixel buffer types for different pixel layouts, such as rgba16, or rgb15, or bitmap. But, I don’t need those right now, so this is the only one.

I debated a long time whether the ‘pix_rgba’ structure was needed or not. As you can see from the macros ‘RGBA’ and friends, you can easily stuff the rgba values into an int32. This is good and bad, depending. The truth is, having both forms is useful depending on what you’re doing. If there are machine instructions to manipulate bytes in parallel, one form or the other might be more beneficial. This will be put to the test in blending functions later.

So, what are the most basic functions of this most basic structure?

#ifdef __cplusplus
extern "C" {
#endif

int pb_rgba_init(pb_rgba *pb, const unsigned int width, const unsigned int height);
int pb_rgba_free(pb_rgba *pb);

int pb_rgba_get_frame(pb_rgba *pb, const unsigned int x, const unsigned int y, const unsigned int width, const unsigned int height, pb_rgba *pf);


#ifdef __cplusplus
}
#endif

#define pb_rgba_get_pixel(pb, x, y, value) *value = ((unsigned int *)(pb)->data)[(y*(pb)->pixelpitch)+x]
#define pb_rgba_set_pixel(pb, x, y, value) ((unsigned int *)(pb)->data)[(y*(pb)->pixelpitch)+x] = value


#define pb_rect_contains(rect, x, y) ((x>=(rect)->x && x<= (rect)->x+(rect)->width) && ((y>=(rect)->y) && (y<=(rect)->y+(rect)->height)))
#define pb_rect_clear(rect) memset((rect), 0, sizeof(pb_rect))

The ‘pb_rgba_init’ function is the beginning. It will fill in the various fields of the structure, and most importantly allocate memory for storing the actual pixel values. This is very important. Without this, the data pointer points to nothing, or some random part of memory (badness). The corresponding ‘pb_rgba_free’ cleans things up.

The ‘pb_rgba_get_frame’ function copies a portion of a pixel array into another pixel array. You could consider this to be a ‘blit’ function in most libraries. There’s a bit of a twist here though. Instead of actually copying the data, the data pointer is set, and the fields of the receiving frame are set, and that’s it. Why? Because there are many cases where you want to move something around, without having to create multiple copies. Just think of a simple ‘sprite’ based game where you copy some fixed image to multiple places on the screen. You don’t want to have to make multiple copies to do it, just reference some part of a fixed pixel buffer, and do what you will.

Then there are the two macros ‘pb_rgba_get_pixel’, and ‘pb_rgba_set_pixel’. These will get and set a pixel value. Once you have these in hand, you have the keys to the graphics drawing kingdom. Everything else in the system can be based on these two functions. Something as simple as line drawing might use these. There may be optimizations in cases such as horizontal line drawing, but for the most part, this is all you need to write textbook perfect drawing routines.

And that pretty much rounds out the basics up to pixel setting.

It’s kind of amazing to me. Even before really getting into anything interesting, I’ve had to make decisions about some very basic data structure representations, and there are various hidden assumptions as well. For example, there is an hidden assumption that all parameters to the set/get pixel routines are bounds checked. The routines themselves will not perform any bounds checking. This is nice for a composable system, because the consumer can decide where they want to pay for such checking. Doing it per pixel might not be the best place.

There are assumptions about the endianness of the int32 value on the machine, as well as various other large and small assumptions in terms of interfacing to routines (using macros?). There are even assumptions about what the coordinate system is (cartesian), and how it is oriented (top left is 0,0). Of course all of these assumptions must be clearly documented (preferably in the code itself), to minimize the surprises as the system is built and used.

This is a good start though. Here’s how we could use what’s there so far.

#include "test_common.h"

void test_blit()
{
	size_t width = 640;
	size_t height = 480;

	pb_rgba pb;
	pb_rgba_init(&pb, width, height);

	pb_rgba fpb;
	pb_rgba_get_frame(&pb, 0, 0, width / 2, height / 2, &fpb);

	// draw into primary pixel buffer
	raster_rgba_rect_fill(&pb, 10, 10, (width / 2) - 20, (height / 2) - 20, pBlue);

	// draw the frame in another location
	raster_rgba_blit(&pb, width / 2, height / 2, &fpb);

	// Now we have a simple image, so write it to a file
	int err = write_PPM("test_blit.ppm", &pb);

}

int main(int argc, char **argv)
{
	test_blit();

	return 0;
}

Setup a pixel buffer that is 640 x 480. Draw a rectangle into the pixel buffer (blue color). Copy that frame into another location in the same pixel buffer. Write the pixel buffer out to a file.

test_blit

And that’s about it.

Some basic constants, simple data structures, core assumptions, and pixels are being stuffed into a buffered in such a way that you can view a picture on your screen.

Next up, drawing lines and rectangles, and what is a ppm file anyway?


GraphicC – What’s so special about graphics anyway?

I have done graphics libraries off and on over the past few decades of programming.  I wanted to take one more crack at it, just because it’s a fun pasttime.  My efforts are on github in the graphicc repository.  This time around, I had some loose design criteria to work from.

  • Use the simplest C constructs as possible
  • Make it small enough to work on a microcontroller
  • Make it flexible enough to be included in any project
  • Make it composable, so that different design tradeoffs can be made
  • Do 2D basics
  • Do 3D basics

These aren’t exactly hard core criteria, but they’re good enough of a constraint for me to get started.  What followed was a lot of fumbling about, writing, rewriting, trying out, testing, and rewriting.  It continues to evolve, and shrink in size.  What of the key aspects of the project is trying to discover the elegant design.  This is something that I have tried to do over the years, no matter what piece of engineering I’m working on, whether it be a machine, workbench, software system, or what have you.  It’s relatively easy to come up with brute force designs that get the job done.  It’s relatively hard to come up with the design that gets the job done with at minimal expense.

When doing a graphics system, it’s really easy to lose focus and get locked into things that you might find on the host platform.  For example, Simple Direct Media Layer (SDL) is available everywhere, so why would anyone build a window and basic graphics interface today?  Well, SDL is more than I’m shooting for.  Over time, my design constraints may line up with those of SDL, and at such time I’ll have a decision to make about switching to using it.  But, to begin, it’s more than I need.

There are tons of other libraries that might suit the bill as well:

There are literally hundreds to choose from.  Some are commercial, some very mature, some old and abandoned.  Some rely on platform specifics, whether it be X or OpenGL, or DirectX.  Some are completely independent, but are tightly integrated with frameworks.  Some are just right, and exactly what I would use, but have some very stiff license terms that are unpleasant.  This is not to say that a perfect solution does not exist, but there’s enough leeway for me to justify to myself that I can spend time on writing this code.

How to start?  Well, first, I consider my various criteria.  The 3D aspects can easily dominate the entirety of the library.  I’m not after creating a gaming library, but I have similar criteria.  I want to be able to simply display 3D models, whether they be renderings of .stl files, or simple ray traces.  I’m not after creating a library that will support the next Destiny on its own, but creating such a library should be possible standing on the shoulders of graphicc.  That means taking care of some basic linear algebra at the very least, and considering various structures.

In the beginning, there was graphicc.h

Here’s a snippet:

#pragma once 

#ifndef graphicc_h
#define graphicc_h

#include &lt;stdint.h&gt;

typedef double REAL;

// Some useful constants
#ifndef M_PI
#define M_PI			3.14159265358979323846264338327950288
#define M_ROOT_PI		1.772453850905516027
#define M_HALF_PI		1.57079632679489661923132169163975144
#define M_QUARTER_PI	0.785398163397448309615660845819875721
#define M_ONE_OVER_PI	0.318309886183790671537767526745028724

#define M_E				2.71828182845904523536
#define M_EULER			0.577215664901532860606

#define M_GOLDEN_RATIO	1.61803398874989484820458683436563811

#endif

#define DEGREES(radians) ((180 / M_PI) * radians)
#define RADIANS(degrees) ((M_PI/180)*degrees)

From the very first lines, I am making some design decisions about the language environments in which this code will operate. The ‘pragma once’ is fairly typical of modern C++ compilers. It takes care of only including a header file once in a mass compilation. But, since not all compilers deal with that, there’s the more classic ‘ifndef’ as well.

I do make other assumptions.  including stdint.h.  I’m going to assume this file exists, and contains things like uint8_t.  I’m going to assume that whomever is compiling this code can make sure stdint.h is available, or substitutes appropriate typedefs to make it so.

Then there’s those monsterous constants done as #define statements.  I could do them as const double XXX, but who knows if that’s right for the platform or not.  Again, it’s easily changeable by whomever is compiling the unit.

Then there’s the ‘typedef double REAL’.  I use ‘REAL’ throughout the library because I don’t want to assume ‘double’ is the preferred type on any given platform.  This makes it relatively easy to change to ‘typedef float REAL’ if you so choose.  Of course each one has a different level of precision, and range, so that needs to be accounted for.  The assumption here is that whomever is doing the compilation will know what they want, and if they don’t sticking with a double is a good default.

The various constants are there mainly because they come up time and again when doing simple math for graphics, so they might as well be readily available.  Same goes for the two conversion routines between degrees and radians.  Of course I should change the divisions to be constants for increased speed.

The rest of this header contains some basic types:


typedef REAL real2[2];
typedef REAL real3[3];
typedef REAL real4[4];

typedef struct _mat2 {
REAL m11, m12;
REAL m21, m22;
} mat2;

typedef struct _mat3 {
REAL m11, m12, m13;
REAL m21, m22, m23;
REAL m31, m32, m33;
} mat3;

typedef struct _mat4 {
REAL m11, m12, m13, m14;
REAL m21, m22, m23, m24;
REAL m31, m32, m33, m34;
REAL m41, m42, m43, m44;
} mat4;

enum pixellayouts {
rgba
};

All of these, except the ‘pixellayouts’ are related primarily to 3D graphics.  They are widely used though, so they find themselves in this central header.  Later, there are decisions about doing things like Catmull-Rom splines using matrices.  These are best done using 4×4 matrices, even if you’re just calculating for 2D curves.

Before I go any further, a picture is worth a thousand words no?

test_blender

This is demonstrating a few things.  Here’s the code:


#include &quot;test_common.h&quot;

void checkerboard(pb_rgba *pb, const size_t cols, const size_t rows, const size_t width, const size_t height, int color1, int color2)
{
size_t tilewidth = width / cols;
size_t tileheight = (height / rows);

for (size_t c = 0; c &lt; cols; c++){
for (size_t r = 0; r &lt; rows; r++){
raster_rgba_rect_fill(pb, c*tilewidth, r*tileheight, tilewidth / 2, tileheight / 2, color1);
raster_rgba_rect_fill(pb, (c*tilewidth) + tilewidth / 2, r*tileheight, tilewidth / 2, tileheight / 2, color2);
raster_rgba_rect_fill(pb, c*tilewidth, (r*tileheight) + tileheight / 2, tilewidth / 2, tileheight / 2, color2);
raster_rgba_rect_fill(pb, (c*tilewidth) + tilewidth / 2, (r*tileheight) + tileheight / 2, tilewidth / 2, tileheight / 2, color1);
}
}
}

void test_blender()
{
size_t width = 800;
size_t height = 600;

pb_rgba pb;
pb_rgba_init(&amp;pb, width, height);

// Red background
raster_rgba_rect_fill(&amp;pb, 0, 0, width, height, pRed);

// create checkerboard background
checkerboard(&amp;pb, 16, 16, width, height, pLightGray, pYellow);

// Draw some blended rectangles atop the whole
for (int offset = 10; offset &lt; 400; offset += 40) {
float factor = offset / 400.0f;
int alpha = (int)(factor * 255);
//printf(&quot;factor: %f alpha: %d\n&quot;, factor, alpha);

int fgColor = RGBA(0, 255, 255, alpha);
raster_rgba_rect_fill_blend(&amp;pb, offset, offset, 100, 100, fgColor);
}


// Now we have a simple image, so write it to a file
int err = write_PPM(&quot;test_blender.ppm&quot;, &amp;pb);
}

int main(int argc, char **argv)
{
test_blender();

return 0;
}

Initializing a pixel buffer (a rendering surface), filling it with a checkerboard pattern, then blending progressively opaque rectangles atop that.  Finally, it writes the result out to a ‘.ppm’ file.  There’s a long way from some constant definitions to doing blended rectangle rendering, but each step is pretty simple, and builds upon the previous.  So, that’s what I’ll focus on next.  In the meanwhile, there’s always to code.