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.


Linear Extrusion of Bezier Surfaces

After about two weeks worth of work, the Bezier Mesh project has finally reached a “1.0” state.  In the end, I have a routine in OpenScad which essentially allows me to do a linear extrusion of a bezier surface, to any thickness desired.

This little project started innocently enough because I wanted to create more interesting fillets to fit within my various 3D models.  OpenScad does not have a built in fillet, and you can only go so far using the standard CSG functions (add, subtract, union, intersect) of OpenScad.  Once I had the basic Bezier calculations, I thought, “well, it’s actually not that much further to get Bezier surfaces”, and logically it wasn’t.

 The end result has been fairly satisfying.  I now have the ability to generate a surface that is controlled by a Bezier mesh.

This is somewhat interesting because Bezier curves were first used in the automotive industry to specify car body shapes and the like.  That was almost 50 years ago.  Nowadays, the various CAD and other 3D packages, have ‘curves’ as a core component, so noone really thinks of Bezier specifically.  All they know is there are various points you click on and drag them around with the mouse to get different curvy shapes.  And that’s largely how things should be.

There is a re-discovery here.  Essentially, I want to be able to do those fancy curve things as well, but I don’t want to use the fancy UI programs to do it.  So, this library is an enabler.

Now that I have the library, I’m looking at my various designs and thinking about how they can be enhanced using these curves.  One of the first things I’ve made is a toy boat.

It took me a while, using graph paper, to figure out the various points on the curves that I wanted, but I eventually got something that is a good first draft.  A boat has a bow, stern, and midships.  So, I modeled those three pieces, and then stitched it together.

Along the way, I thought of a couple more functions that would make building this sort of model in text rather easy.

This has also brought up another line of thinking in my mind.  Currently, most models on Thingiverse are distributed as .stl files.  That is, rather than the raw stuff that helps you change the original, you get the end product.  Well, as OpenScad has more features, it becomes feasible to use it as a transport mechanism.  That is, I can send around .scad files, even to a machine.  The advantage to that would be, the machine can better handle a higher level description of the thing you’re trying to produce.

At any rate, there’s more Bezier goodness to come.  The next form of surface will take into account the actual shape of the surface when determining the ‘down’ side.  Today, the ‘down’ facing surface is merely the same as the ‘top’, but dropped by the specified thickness in the z-axis.  That’s why it is ‘linear_extrude’.  The next version will include a true ‘shell_extrude’.


Mr Bezier’s New Perspective

Work on the OpenScad Bezier functions moves along apace.  It’s kind of funny how easy it is to forget the high school and college math!  I distinctly remember back in the 10th grade knowing about ‘the right hand rule’, and ‘matrix math’, and all the trig you could care to swallow.  Somehow now, even after having created a full blown 3D library in the past, I’m actually having to use graph paper to visualize what I’m doing as I do it.

The latest iteration gets one step closer to Bezier mesh perfection: http://www.thingiverse.com/thing:8643

In this version, I managed to get a Mesh function that traverses curves in one direction (u) and then uses values from that to go in the other direction (v).  It actually works, particularly if I’m just displaying the control points.

 In order for things to work somewhat correctly, I break things down into quads (4 points) and then further into triangles.  I figured I have to use triangles because then you guarantee that the points are coplanar (on the same plane), and you can calculate a surface normal, and use that to calculate the proper rotations.  So, for each quad, there are two triangles.  You place the triangles, and you’re done!

This is a nice setup because placing quads and triangles is a generic thing you want to do in 3D packages.  So, it is easily reusable.  When it comes time to implement B-Spline, or other curves, this part will be the foundation.

There are two major challenges remaining.  The first has to do with the surface normals.  At the moment, I’m getting the math wrong.  The normals are calculating correctly when they’re facing only in certain directions, otherwise they’re off.  I’m sure it has to do with how I’ve visualized the problem, and where I’m subtracting 90 degrees when I should be doing something else.  But, it’s a fairly isolated problem, and once solved, the normals will be correct, and the faces will be absolutely perfect.  The other challenge has to do with the faces meeting up at the curve control points.  They don’t always meet up.

The way in which the patches are generated is to take the 3D coordinates of the triangle, subtract the ‘center of gravity’, then use the x,y of those coordinates to create a polygon.  that polygon is then rotated according to the surface normal, and the patch is translated back into place.  The problem is, by taking the x,y coordinates, and ignoring the ‘z’, things will be too short if there’s much of a slope.  What really needs to happen is, I need to take the length of the vector from one point to the next, and use those as the lenghths of the sides.

So, in the next version, I’ll try to correct those two problems, the normal nonsense, and the lengths of the sides.  If I can do that, then I think this little baby will be useable.  It will be great because being able to get a surface generated from a parametric curve mesh will make for some very nice designs indeed.

My further thoughts, having gone through this experience so far, is that adding to OpenScad with such ‘extensions’ is a fairly straight forward task.  I thought it might be useful to integrate with other libraries, or perform ‘exec’ to call out to other programs, but realistically, it’s just not needed.  The OpenScad language itself has enough of the generic ‘C’ family of languages to create various functions.  The primary thing you have to get over is the general lack of state management, other than tree-scoped variables.  But, I’ve found ways around that by treating OpenScad as a functional language.  Everything is just a function that returns some value.

At any rate, things are moving along nicely.


Mr Bezier goes to OpenScad

I have been using OpenScad since November of 2010, when I first made this simple design: http://www.thingiverse.com/thing:4828 .  It’s been a great ride with OpenScad so far.  I wanted to learn a design tool that did not require me to climb a very steep learning curve like with Blender, or AutoCAD or SolidWorks.

Well, OpenScad has been a great tool in this regard thus far.  I’ve been able to create all manner of thing, mostly functional.  I have now gotten to the point where I’ve needed to create more intricate and elegant parts.  No longer satisfied with blocky angular designs.  I need some nice curves, and more than can be had from doing simple CSG with cyclinders and blocks.

So, I spent some time thinking about how to use Bezier curves in OpenScad.  Ideally OpenScad would have some curves built into the system, but as far as I know, it does not.  So, I created my own Bezier functions in OpenScad: http://www.thingiverse.com/thing:8443

  I did this because I simply wanted to do some nice fillets on various designs, and you can only go so far by subtracting a cylinder from a square.  With this function, I support cubic Bezier curves (start point, end point, two control points).  It’s very nice for general purpose stuff, not just fillets.

That was a good start to Bezier curves in OpenScad.  Then I went further, and added a couple more functions.  The first one was to add Bezier ribbons (http://www.thingiverse.com/thing:8454).  That is, you define two Bezier curves.  The function will create a ‘ribbon’ between the two curves.  This can be used for simple things like a ramp, or a handle to a cup, or what have you.

At the same time that I was creating the ribboning function, I realized that it would not be that hard to demonstrate how to use a Bezier curve to change colors on the image over the length of the curve.  This lead to the creation of a secondary function that can return three values along the Bezier curve.  This is handy when the control points are actually color values, and you want to smoothly interpolate between them.

This seemed to be going quite well, so I added one more function.  This last one does a rotation of a Bezier strip.

This one looks the coolest of all so far.  It demonstrates the Bezier curve, and the rotation, and the color gradient, and it all happens in just a couple lines of code.  That’s a tremendously valuable tool to have in the modeling toolchest.

Now that I have this tool, I have started to use it to improve on designs.  Here is a new version of the effector end of the PolyBot: http://www.thingiverse.com/thing:8456

This has been a good outcome so far.  I was dreading having to do the work of modeling using a different tool, or importing meshes, which I then could not easily alter.  Now that I have essentially built Bezier curves into OpenScad, I can stick with this tool longer.

I would like to explore creating Hermite curves, and then possibly dealing with C1/2 continuity of curve segments, but I’m happy with this for now.


SVG And Me

lineargradient

That’s a simple linear gradient, generated from an SVG document that looks like this:

 

<svg viewBox = '0 0 120 120' version = '1.1' xmlns = 'http://www.w3.org/2000/svg'   width = '120' height = '120' xmlns:xlink = 'http://www.w3.org/1999/xlink'>
  <defs>
    	<linearGradient id = 'MyGradient'>
      <stop stop-color = 'green' offset = '5%' />
      <stop stop-color = 'gold' offset = '95%' />
    </linearGradient>
  </defs>
  <rect x = '10' y = '10' height = '100' fill = 'url(#MyGradient)' width = '100' />
</svg>

 

Fair enough. And of course there are a thousand and one ways to generate .svg files. For various reasons, I am interested in generating .svg files on the fly in a Lua context. So, the code I used to generate this SVG document looks like this:

require("remotesvg.SVGElements")()
local FileStream = require("remotesvg.filestream")
local SVGStream = require("remotesvg.SVGStream")

local ImageStream = SVGStream(FileStream.open("test_lineargradient.svg"))

local doc = svg {
	width = "120",
	height = "120",
	viewBox = "0 0 120 120",
    ['xmlns:xlink'] ="http://www.w3.org/1999/xlink",

    defs{
        linearGradient {id="MyGradient",
            stop {offset="5%",  ['stop-color']="green"};
            stop {offset="95%", ['stop-color']="gold"};
        }
    },

    rect {
    	fill="url(#MyGradient)",
        x=10, y=10, width=100, height=100,
    },
}

doc:write(ImageStream);

This comes from my remotesvg project. If you squint your eyes, these look fairly similar I think. In the second case, it’s definitely valid Lua script. Mostly it’s nested tables with some well known types. But, where are all the parenthesis, and how can you just put a name in front of ‘{‘ and have that do anything?

OK, so Lua has some nice syntactics tricks up its sleeve that make certain things a bit easier. For example, there’s this trick that if there’s only a single parameter to a function, you can leave off the ‘()’ combination. I’ve mentioned this before way long back when I was doing some Windows code, and supporting the “L” compiler thing for unicode literals.

In this case, it’s about tables, and later we’ll see about strings. The following two things are equivalent:

local function myFunc(tbl)
  for k,v in pairs(tbl) do
    print(k,v)
  end
end


myFunc({x=1, y=1, id="MyID"})

-- Or this slightly shorter form

myFunc {x=1, y=1, id="MyID"}

OK. So that’s how we get rid of those pesky ‘()’ characters, which don’t add to the conversation. In lua, since tables are a basic type, I can easily include tables in tables, nesting as deeply as I please. So, what’s the other trick here then? The fact that all those things before the ‘{‘ are simply the names of tables. This is one area where a bit of trickery goes a long way. I created a ‘base type’ if you will, which knows how to construct these tables from a function, and do the nesting, and ultimately print out SVG. It looks like this:

--[[
	SVGElem

	A base type for all other SVG Elements.
	This can do the basic writing
--]]
local BasicElem = {}
setmetatable(BasicElem, {
	__call = function(self, ...)
		return self:new(...);
	end,
})
local BasicElem_mt = {
	__index = BasicElem;
}

function BasicElem.new(self, kind, params)
	local obj = params or {}
	obj._kind = kind;

	setmetatable(obj, BasicElem_mt);

	return obj;
end

-- Add an attribute to ourself
function BasicElem.attr(self, name, value)
	self[name] = value;
	return self;
end

-- Add a new child element
function BasicElem.append(self, name)
	-- based on the obj, find the right object
	-- to represent it.
	local child = nil;

	if type(name) == "table" then
		child = name;
	elseif type(name) == "string" then
		child = BasicElem(name);
	else
		return nil;
	end

	table.insert(self, child);

	return child;
end

function BasicElem.write(self, strm)
	strm:openElement(self._kind);

	local childcount = 0;

	for name, value in pairs(self) do
		if type(name) == "number" then
			childcount = childcount + 1;
		else
			if name ~= "_kind" then
				strm:writeAttribute(name, tostring(value));
			end
		end
	end

	-- if we have some number of child nodes
	-- then write them out 
	if childcount > 0 then
		-- first close the starting tag
		strm:closeTag();

		-- write out child nodes
		for idx, value in ipairs(self) do
			if type(value) == "table" then
				value:write(strm);
			else
				-- write out pure text nodes
				strm:write(tostring(value));
			end
		end
		
		strm:closeElement(self._kind);
	else
		strm:closeElement();
	end
end

And further on in the library, I have things like this:

defs = function(params) return BasicElem('defs', params) end;

So, ‘defs’ is a function, which takes a single parameter (typically a table), and it constructs an instance of the BasicElem ‘class’, handing in the name of the element, and the specified ‘params’. And that’s that…

BasicElem has a function ‘write(strm)’, which knows how to turn the various values and tables it contains into correct looking SVG elements and attributes. It’s all right there in the write() function. In addition, it adds a couple more tidbits, such as the attr() and append() functions.

Now that these basic constructs exist, what can be done? Well, first off all, every one of the SVG elements is covered with the simple construct we see with the ‘defs’ element. How might you used this:

	local doc = svg {
		width = "12cm", 
		height= "4cm", 
		viewBox="0 0 1200 400",
	}


	doc:append('rect')
		:attr("x", 1)
		:attr("y", 2)
		:attr("width", 1198)
		:attr("height", 398)
		:attr("fill", "none")
		:attr("stroke", "blue")
		:attr("stroke-width", 2);

   local l1 = line({x1=100, y1=300, x2=300, y2=100, stroke = "green", ["stroke-width"]=5});
   local l2 = line({x1=300, y1=300, x2=500, y2=100, stroke = "green", ["stroke-width"]=20});
   local l3 = line({x1=500, y1=300, x2=700, y2=100, stroke = "green", ["stroke-width"]=25});
   local l4 = line({x1=700, y1=300, x2=900, y2=100, stroke = "green", ["stroke-width"]=20});
   local l5 = line({x1=900, y1=300, x2=1100, y2=100, stroke = "green", ["stroke-width"]=25});


	--doc:append(r1);
	doc:append(l1);
	doc:append(l2);
	doc:append(l3);
	doc:append(l4);
	doc:append(l5);

In this case, instead of doing the ‘inlined table document’ style of the first example, I’m doing more of a ‘programmatic progressive document building’ style. I create the basic ‘svg’ element and save it in the doc variable. Then I use the ‘append()’ function, to create a ‘rect’ element. On that same element, I can use a short hand to add it’s attributes. Then, I can create separate ‘line’ elements, and append them onto the document as well. That’s pretty special if you need to construct the document based on some data you’re seeing, and you can’t use the embedded table style up front.

There are some special elements that get extra attention though. Aside from the basic table construction, and attribute setting, the ‘path’ element has a special retained mode graphics building capability.

	local p1 = path {
		fill="red", 
		stroke="blue", 
		["stroke-width"]=3
	};
	
	p1:moveTo(100, 100);
	p1:lineTo(300, 100);
	p1:lineTo(200, 300);
	p1:close();

	local doc = svg {
		width="4cm", 
		height="4cm", 
		viewBox="0 0 400 400",
		
		rect {
			x="1", y="1", 
			width="398", height="398",
        	fill="none", stroke="blue"};
	
		p1;
	}

In this case, I create my ‘path’ element, and then I use its various path construction functions such as ‘moveTo()’, and ‘lineTo()’. There’s the full set of arc, bezier curvs, and the like, so you have all the available path construction commands. Again, this works out fairly well when you are trying to build something on the fly based on some previously unknown data.

There’s one more important construct, and that’s string literals. There are cases where you might want to do something that this easy library just doesn’t make simple. In those cases, you might just want to embed some literal text into the output document. Well, luckily, Lua has a fairly easy ability to indicate single or multi-line text, and the BasicElem object knows what to do if it sees it.

    g {
      ['font-family']="Arial",
      ['font-size']="36",

      [[
      <text x="48" y="48">Test a motion path</text> 
      <text x="48" y="95" fill="red">'values' attribute.</text> 
      <path d="M90,258 L240,180 L390,180" fill="none" stroke="black" stroke-width="6" /> 
      <rect x="60" y="198" width="60" height="60" fill="#FFCCCC" stroke="black" stroke-width="6" /> 
      <text x="90" y="300" text-anchor="middle">0 sec.</text> 
      <rect x="210" y="120" width="60" height="60" fill="#FFCCCC" stroke="black" stroke-width="6" /> 
      <text x="240" y="222" text-anchor="middle">3+</text> 
      <rect x="360" y="120" width="60" height="60" fill="#FFCCCC" stroke="black" stroke-width="6" /> 
      <text x="390" y="222" text-anchor="middle">6+</text> 
      ]];

      path {
        d="M-30,0 L0,-60 L30,0 z", 
        fill="blue", 
        stroke="red", 
        ['stroke-width']=6, 
        
        animateMotion {values="90,258;240,180;390,180", begin="0s", dur="6s", calcMode="linear", fill="freeze"} 
      } 
    }

Notice the portion after the ‘font-size’ attribute is a Lua multi-line string literal. This section will be incuded in the form document verbatim. Another thing to notice here is that ‘path’ element. Although path is specialized, it still has the ability to have attributes, and even have child nodes of its own, such as for animation.

Another case where the literals may come in handy is for CSS style sheets.

	defs {
		style {type="text/css",
[[
			.land
			{
				fill: #CCCCCC;
				fill-opacity: 1;
				stroke:white;
				stroke-opacity: 1;
				stroke-width:0.5;
			}
]]
		};
	};

The ‘style’ element is well known, but the format of the actual content is a bit too specific to translate into a Lua form, so it can simply be included as a literal.

Well, that’s the beginning of this journey. Ultimately I want to view some live graphics generated from data, and send some commands back to the server to perform some functions. At this point, I can use Lua to generate the SVG on the fly, and there isn’t an SVG parser, or Javascript interpreter in sight.


Render Text like a Boss

And it looks like this:

verdana18

One of the most rewarding parts of bringing up a graphics system is when you’re able to draw some text.  I have finally reached that point with the graphicc library.  There are many twists and turns along the way, some of which are interesting, but I’ll just share a bit of the journey here.

First of all, the code that generates this image looks like this:

#include "test_common.h"
#include "animwin32.h"

struct font_entry {
	char *name;
	const uint8_t *data;
};

struct font_entry fontlist[] = {
	{"gse4x6", gse4x6 },
	{ "gse4x8", gse4x8 },
	{ "gse5x7", gse5x7 },
	{ "gse5x9", gse5x9 },
	{ "gse6x12", gse6x12 },
	{ "gse6x9", gse6x9 },
	{ "gse7x11", gse7x11 },
	{ "gse7x11_bold", gse7x11_bold },
	{ "gse7x15", gse7x15 },
	{ "gse7x15_bold", gse7x15_bold },
	{ "gse8x16", gse8x16 },
	{ "gse8x16_bold", gse8x16_bold },
	{ "mcs11_prop", mcs11_prop },
	{ "mcs11_prop_condensed", mcs11_prop_condensed },
	{ "mcs12_prop", mcs12_prop },
	{ "mcs13_prop", mcs13_prop },
	{ "mcs5x10_mono", mcs5x10_mono },
	{ "mcs5x11_mono", mcs5x11_mono },
	{ "mcs6x10_mono", mcs6x10_mono },
	{ "mcs6x11_mono", mcs6x11_mono },
	{ "mcs7x12_mono_high", mcs7x12_mono_high },
	{ "mcs7x12_mono_low", mcs7x12_mono_low },
	{ "verdana12", verdana12 },
	{ "verdana12_bold", verdana12_bold },
	{ "verdana13", verdana13 },
	{ "verdana13_bold", verdana13_bold },
	{ "verdana14", verdana14 },
	{ "verdana14_bold", verdana14_bold },
	{ "verdana16", verdana16 },
	{ "verdana16_bold", verdana16_bold },
	{ "verdana17", verdana17 },
	{ "verdana17_bold", verdana17_bold },
	{ "verdana18", verdana18 },
	{ "verdana18_bold", verdana18_bold }

};
static const int numfonts = sizeof(fontlist) / sizeof(fontlist[0]);
static int fontidx = 0;



LRESULT CALLBACK keyReleased(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam)
{
	switch (wParam)
	{
		case VK_UP:
			fontidx--;
			if (fontidx < 0) {
				fontidx = numfonts - 1;
			}
		break;

		case VK_DOWN:
			fontidx++;
			if (fontidx >= numfonts){
				fontidx = 0;
			}
		break;

		case VK_SPACE:
			write_PPM("test_agg_raster_fonts.ppm", gpb);
		break;
	}

	return 0;
}

void setup()
{
	size(640, 480);
	background(pWhite);

	setOnKeyReleasedHandler(keyReleased);
}


static char CAPS[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
static char LOWS[] = "abcdefghijklmnopqrstuvwxyz";
static char NUMS[] = "1234567890";
static char SYMS[] = "!@#$%^&*()_+-={}|[]\\:\"; '<>?,./~`";
static char SOME[] = "The quick brown fox jumped over the lazy dog.";

void draw()
{
	setFont(fontlist[fontidx].data);

	fill(pBlack);
	text(fontlist[fontidx].name, 0, 0);
	text(CAPS, 0, gfont.height * 1);

	fill(pRed);
	text(LOWS, 0, gfont.height * 2);

	fill(pGreen);
	text(NUMS, 0, gfont.height * 3);

	fill(pBlue);
	text(SYMS, 0, gfont.height * 4);

	fill(pBlack);
	text(SOME, 0, gfont.height * 5);
}

Many of the test programs in graphicc have this similar layout. If you’ve every done any programming using Processing you might be familiar with the ‘setup()’ and ‘draw()’ methods. The animwin32 file is responsible for this little construction. Basically, it provides a “Processing like” environment, which makes it really easy to play with various graphics routines. It also does mouse/keyboard handling, so you can setup to deal with key presses and mouse actions. In this case, I use the key up/down actions to change the font from a list of font data. Pressing ‘SPACE’ will take a dump of the screen.

That font data was borrowed from the Anti-Grain Geometry library, because it’s a nice compact bitmap representations of a few fonts.  Just a brief on the AGG library.  This is a fairly well written graphics library written by Maxim Shemanarev, who died way too young I think.  The library is an inspiration and source of knowledge to anyone doing 2D graphics.

The text() function will render the string using whatever is the currently selected font, fill color, and specified location. The location specified the upper left of the font box. There are various text rendering attributes which can be employed, such as alignment, a draw box, whether to use the upper left corner, or the baseline, etc. All in due time.

The guts of the text() routine look like this:

// Text Processing
void text(const char *str, const int x, const int y)
{
	scan_str(gpb, &gfont, x, y, str, fillColor);
}

void setFont(const uint8_t *fontdata)
{
	font_t_init(&gfont, fontdata);
}

Very simple yes?

And deeper into the rabbit hole…

int scan_str(pb_rgba *pb, font_t *font, const int x, const int y, const char *chars, const int color)
{
	glyph_t ginfo;

	int idx = 0;
	int dx = x;
	int dy = y;

	while (chars[idx])
	{
		glyph_t_init(font, &ginfo, chars[idx]);
		scan_glyph(pb, font, &ginfo, dx, dy, color);
		dx += ginfo.width;
		idx++;
	}

	return dx;
}

Basically, get the glyph information for each character, and scan that glyph into the pixel buffer. The scan_glyph() in turn takes the packed bitmap information, unpacks it into individual ‘cover spans’, then turns that into pixels to be placed into the pixel buffer.

Lots can be done to optimize this activity. For example, all the glyphs can be rendered into a bitmap, and then just do a blit to the pixel buffer when needed. This would essentially be a tradeoff between space and time. That’s a choice easily made at a higher level than the lowest graphics routines, so the low level graphic routines don’t make that assumption, they only deal with the packed form of the data. I find this kind of design choice to be most interesting and useful in terms of what kind of profile the overall system has, and what constraints it will adhere to in terms of what type of system it will run on.

So, there you have it.  At this point, the graphicc library can do primitives from single pixels to bezier curves, and text.  With the help of the animwin32 routines, you can do simple UI programming as if you were using the 2D portion of Processing.  I find this to be a good plateau in the development of the library.  At this point, it makes sense to reconsider the various design choices made, cleanup the API, throw in some ‘const’ here and there, consider error checking, and the like.  The next step after that is to consider higher level libraries, which might be purpose built.  I’ll want to incorporate 3D at some point, and there are hints of that already in the routines, but I don’t want to get bogged down in that just yet.  Good image scaling and rotation is probably a first priority before lighting models and 3D rendering.

I would love to be able to create graphic systems profiles, such as, can I mimic GDI, or the HTML Canvas routines.  I can already do Processing to a certain extent.  My first test of the library though is something much simpler.  I want to be able to render the state of a network of machines performing some tasks.  First pass will likely be simple 2D graphs of some sort, so time to get on it.


What that? UI Stuffs?

Pictures are always more fun than text…

One of the many graphics books I have is simply “Computer Graphics”, by: Amarendra N Sinha, and Arun D Udai.  I picked this book up in India a couple of years back.  The copyright is 2008.  It’s kind of an interesting book because it talks about quaint subjects such as cathode ray tubes, light pens, glove input devices, as well as pen plotters.

Many of the programming examples are written using TurboC! (Gasp)

But, for all it’s quaintness, it covers topics such as scan conversion of graphics primitives, mouse input, matrix math, space curves and surfaces, and the like.  All of this in about 470 pages, including pictures, and embedded code listings.  It’s quite a dense and readable book, complete with color pictures.  All this came at a price of 395 rupees (roughly $10 USD).  Considering any graphics book I purchase in the US is a minimumn of about $50, this book is quite the bargain.

One of the most nifty things I like about the book is that it has nice illustrations in it.  While I was going through different things, I got to thinking, how hard can it be to actually represent these things in Banate CAD?  Of course I’m already doing the basics to represent things like lines, curves, surfaces, and every manner of geometric object, including text with full font support, so why not basic illustrations as well?

Another book that I have is: “Algorithms In C++ (Third Edition)”, by Robert Sedgewick

Now this book is way cool.  First printing in 1998, now it’s in it’s 19th printing.  This is the source for many an algorithm study, including sorting, searching, data structures, etc.  Now, this book is very cool not only because of the treatment of the various subjects, but for the illustrations as well.  These illustrations are even more interesting because there is an animation component to them.  The above image shows the progress of a selection sort algorithm.  The code in HeadsUp is quite simple.  Basically I just map the array indices along the x-axis, and the value of the element at that position along the y-axis.  If the animation is simply run, you see the elements drop into their proper order one after another in rapid order.

This is really good because you can visually inspect whether your routine is working properly or not. You can also fairly easily calculate the order of the routines.

This is where things get much more interesting.  This is another animation.  Of course, with animations, enough words can not be used to explain what’s going on.  When you run this script in HeadsUp, you see those circles pulsating with the outline color, and the little red dots shooting from left to right.

Which begs the question.  When will BanateCAD be able to export animations as movies, or something interesting like that?  Well, wouldn’t it be interesting if one of the export formats was an animated GIF or .mpg, or something?  Well, surely that can’t be that far off.

One more for the road…

Another thing I find in a lot of the books that I read are these curly brace things.  Here’s where things get really interesting.  In order to construct such a thing, I want to actually layout a path using bezier curves, line segments, arcs, and the like.  So, there is an object for that.  The ShapeBuilder is a nice little object that has an interface like this:


AddVertex()
LineTo(pt1)
AddBezier(pt1,pt2, pt2)
AddBezier2(pt2,pt3)

With this sort of interface, you can fairly quickly layout shapes of any variety, including fancy shapes based on superellipse, and other formulas. Then of course there’s the connection to UI elements. Take for instance the lowly Button. It’s just some drawing with the ability to respond to mouse and keyboard actions. The drawing can be anything, as long as you can respond to whether or not a point is inside or outside the drawing (hit detection).  But, that’s a coming exercise.

One of the things I’ve been contemplating is how to rapidly turn some objects into graphs that I can use.  I have been considering SVG, and DrawingML primarily.  Both of these formats have tons of graphics material available.  They’re both XML formats, so they’re fairly easy to deal with.  I might lean towards DrawingML primitives first, because these shapes are more meant for graphs, and that’s what I want to use them for.  On the other hand, there are plenty of SVG parsers in the world, which makes it fairly easy to consume those.

At any rate, they both simply represent a persistant format for vector graphic information.  The core system (BanateCAD) has to be able to render the same primitives, no matter which representation.

One interesting side effect of going down this rabbit hole is that I am also able to rasterize 2D primitives.  If you’re thinking in terms of 3D printing, you know this is a good thing, because layer slicing is essentially about rasterizing on a local level.  So, we’ll see how this shapes up.

And so it goes.  Progress continues towards visualization, and 3D modeling.

As an aside, I’ve separated out the many BanateCAD examples into their own project.  I was finding that as I add more and more examples, the directories were becoming unwieldy.  Now, when there is a release, there can be a separation between the package proper, and the set of examples that one might to play with.

 


CSG for You and Me!

Here it is Monday, and where’s my new release?

Well, how about a couple of pretty pictures to look at?

What do we have here?  Well, on the left, we have a sphere with a cylinder sticking out of it.  On the right, we have a sphere with said cylinder removed through the magic of Constructive Solid Geometry (csg).

With Banate CAD, you can already create nifty solids from basics, like Bezier Surfaces, and other oddities.  But, the set of things you can construct can be dramatically improved if you can add CSG operations (union, intersect, difference).

The science of CSG has existed for a couple of decades now, with myriad implementations covering a broad spectrum of uses.  Recently, I saw an implementation in the form of the csg.js library.  That was pretty cool because it’s compact, designed to work with JavaScript for WebGL usage, and it basically gets the job done.

I thought similar could be done for Banate CAD.  My design goals for the operations are:  No external library dependencies, fast enough to render in “relative real-time”.  Robust enough to handle 90% of the things CSG is typically used for in doing simple 3D designs.

I explicitly was NOT going for the most robust and proveably complete CSG implementation.  I will be satisfied if every design I’ve implemented in OpenScad can be redone in Banate CAD.  If that turns out to be the case, then I’ll be happy enough with it.

There are a couple of usability things to consider now, before I actually release it as part of the product.

At the very core, CSG is done like this:

object1:union(object2)

or

object1:difference(object2)

etc.

But, that’s a bit clunky.  In OpenScad, I would do something like:

difference(){
functiontoinstantiateobject1()
functiontoinstantiateobject2()
}

That’s fairly easy to do, and is in line with OpenScad’s generally declarative way of doing things. But, Banate CAD does not really follow that declarative style. It is much more imperative (tell it exactly what to do). Aside from style, Banate CAD makes instancing front and center. That is, in order to make a cube, for instance, you can either do:
hexahedron(size), which will create an internal instance of a cube, and add it to the global scene, or you can be more explicit:

mycube = shape_hexahedron.new(size)
mycylinder = shape_cone.new(base, top)

Now that I’ve got an explicit instance of a cube, it makes more sense to do things with it:

myshape = mycube - mycylinder
addshape(myshape)

There are a couple of things here. First of all, overloading the ‘+’, ‘-‘, ‘%’ operators. That makes for a nice simple notation, but you’ll have to be very careful with operator precedence, and grouping with parenthesis. But, for very simple things, this might just work out.

At any rate, the basic functionality is now in hand, and it will surely show up in the release soon.


Banate CAD Third Release

Is it Monday already!

Here is the third release of Banate CAD!

 

 

This week saw multiple improvements on multiple fronts.  I can’t actually remember which features showed up between the last week’s release and today’s release, but here’s an attempt.

Generalized Bump Maps – I made this earth and moon things, and then I generalized it so that any BiParametric based shape can utilize the technique.  That’s good because everything from spheres, to bezier surfaces are based on the BiParametric object.

import_stl_mesh – You can create a single instance of an imported mesh, and then use that single instance multiple times.  That’s a great way to save on resources when you’re adding multiples of the same geometry to the scene.

Blobs – Quite a lot of work on this module.  The main thing was getting the ‘beamsearch’ algorithm working correctly.  That allows for the “real-time” viewing of metaball based objects.  This was a lot of fun to get working.  It doesn’t work in all cases, but it works in the vast majority of cases that will be used in 3D solid modeling.

Some features on way the program itself works.  I’ve added support for reading some modules in from directories at runtime.  This allows me to separate some things that are ‘core’ and MUST be in the package from a number of other things that are purely optional.  It also allows me to support users adding things, in a sane way.  They can eventually go into a “Libraries” directory.

Also, this separation, and the addition of the BAppContext object allows for the creation of tools that have nothing to do with UI.  For example, in order to write a script that just imports a mesh, performs some operations on it, then exports, does not need all the UI code.

Oh yah, and before I forget, one of the biggest additions, or rather fleshing outs, was the animation system.  The AnimationTimer object has actually been in there for a while, and the Animation menu has as well.  It’s just nothing used it.  Now, if you create shapes, and implement the Update() function, your shape will be informed whenver the clock ticks, giving you an opportunity to change things based on time.  There are a few examples included in the example files.  It’s pretty straight forward.

The animation system is quite handy for doing things like playing with metaballs, seeing how things change as you vary parameters.  This will also come in handy when describing physical things that move.  For example, I could model my Up! printer, and then actually set it in motion.  But, that’s for another time.

 

There you have it.  Another weekly release!


Banate CAD Second Release

There is a new consolidated package available here: Banate CAD 20111128

I wonder if a weekly distribution is a realistic thing to expect?

Banate CAD is maintained “Live” on GitHub, so changes that are going on in the code are reflected in GitHub fairly regularly. But, since it is live, things like the Examples get out of sync regularly as well. I am updating the Examples weekly to match the current state of the software for that week. When I bring the two in sync, I package it up in a convenient .zip and make it available for download.

This past week saw quite a lot of change in Banate CAD. Primarily, after the first release, I have been focused on reducing the amount of code that’s in the package. At the end of the day, I want the codesize to remain within about 256K. If it remains within that budget, then I have something that could possibly be hosted on a microcontroller, or other small compute devices. So far, on disk size is 133K, so I still have some room to add more functions.

One big form of reduction for this past week was further simplification and reuse of the core BiParametric object. It can be used to do anything from produce a sphere, to a Bezier surface. I also introduced the concept of “Sampler”, which is essentially just a function that you can ask “for this parametric position, what’s your value?”.

The MoonShot picture above is the epitomy of using these samplers. I use a sampler for the offsets of vertices, to do height mapping, and I use the same exact sampler to determine the color on a per facet basis. That makes for some very convenient reuse. It also demonstrates how easily samplers can be combined into super samplers.

Another usage of a functor has to do with the Torus object. The base torus on its own will only generate a circular profile. But, you can hand it a functor which will determine the outline of that profile. In this case, I’ve used the SuperEllipse formula to give shape to the profile. In this way, you can pretty much select any cross section profile you like. The core of the Torus routine remains the same, go around a ‘circle’. At some point, even that part will become a functor, and you’ll be able to generate very strange torii indeed.

As Banate CAD is meant to do ‘CAD’, I finally worked on getting the export to .stl function working properly.  Now, most models, if they are solids, can actually be exported.  The cheat at the moment is that they will always export to a file with the name “file.stl”.  There’s no reason for this other than I need to change file handling to be more robust in general, so I didn’t bother to make any attempt to improve it at the moment.  At the moment, although the .stl files will work, they certainly benefit from going through a tool like MeshLab to clean them up and remove bits and pieces, depending on the model.  Mainly removing duplicate vertices, and triangles of zero area, like at the poles of a sphere.

So, there you have it.  One week’s worth of work, and a whole bunch of new functionality.