G-Code Interpreter

As part of my 3D-Printer project, I'm writing a G-Code interpreter to run on an Arduino. My machine will support a fairly limited subset of G-Code, as well as a few extra commands specific to my machine.

1. Using the partial G-Code spec available from LinuxCNC, I developed a rudimentary parser. Here's the control flow of the parser:
2. Split G-Code file into lines (blocks)
3. Search each block for valid words in specific order: X, Y, Z, S, F, T, M, G
4. Handle each word appropriately (set feed, set speed, move, etc.)

There are some notes here:

Location values must be maintained statically so code like this will run:

G01 Z1.0 F.05 X0.0

Speeds and feeds must be read first so code like this will run:

G01 Z1.0 F.05

Since my printer only has one toolhead, I changed the T word to represent temperature. I realize this is an awful and confusing decision, and will probably change it eventually. Here's my (messy) code.

void  Printer::parseBlock(char *string)
{
//Location must be maintained
static Location location = Location(0,0,0);

//Control words: Feed rate, extrusion speed and temperature
int s = 0;
int f = 0;
int t = 0;

//G Mode is persistent
static int g = 0;

//Machine Option is not persistent
int m = 0;

//Search string for accepted codes, then execute
//order is important, be careful when changing

char *p = string;

//Position First
if ((p = strpbrk(string, "X")))
{
    sscanf(p, "X%f", &(location.iX));
}
if ((p = strpbrk(string, "Y")))
{
    sscanf(p, "Y%f", &(location.iY));
}

if ((p = strpbrk(string, "Z")))
{
    sscanf(p, "Z%f", &(location.iZ));
}

//Speed, Temp and Feed
if ((p = strpbrk(string, "S")))
{
    sscanf(p, "S%d", &s);
    S(s);
}

if ((p = strpbrk(string, "F")))
{
    sscanf(p, "F%d", &f);
    F(f);
}

if ((p = strpbrk(string, "T")))
{
    sscanf(p, "T%d", &t);
    T(t);
}

//Operation Codes (M)
//Conflicts are resolved by order
//AKA: conflicts are not resolved
p = string;
while ((p = strpbrk(p, "M")))
{
    sscanf(p, "M%d", &m);
    M(m);
    //Move to next spot
    p++;
}

//G Codes
//Conflicts are resolved in order, AKA not resolved
p = string;
while ((p = strpbrk(p, "G")))
{
    sscanf(p, "G%d", &g);
    G(g, location);
    p++;
}

}

3D Printing

Even though 3D printing seems like something out of a science fiction novel, the technology has been around for quite a few years now. Machines exist today which can take computer-generated models such as the mouse shown below (from Wikipedia), and turn them into real-life objects.

The quality of these printed objects is on par with most other manufacturing and prototyping processes and their ease of use is unparalleled. Companies like Dimension, Objet and Desktop Factory all make and sell plug and play 3D printers.

If this technology is so great and easy to use, why doesn't everyone have a 3D printer? The problem is cost. The cheapest printers made by Dimension and Desktop Factory cost around $5000! These companies are advertising these machines as breakthrough devices, and yet they cost 10% of the average US household income.

These companies need to take a step back if they want to put a 3D printer in every home in America. A (completely unscientific) survey I conducted recently on the Amazon Mechanical Turk suggested that people would jump at the opportunity to buy a desktop 3D printer in the price range of $200-$500, even if it meant lower print quality than the existing machines.

A device like this would be invaluable for home use. Coupled with an online object library such as Thingiverse and the rise of easy to use 3D CAD software like Google Sketchup, home repairs will be easier than ever. The low cost would make itself up in fewer trips to the hardware store in no time. Need a new kitchen utensil? Break the battery cover off of your TV remote? No problem. Click print and you're all set.

This is the exact goal of the RepRap project: to put an inexpensive 3D printer in every home. This group has made tremendous progress in designing and building self-reprodudicing 3D printers: printers that can print other printers. This idea is pretty alluring; imaging building a device that can build a copy of itself. The growth would be exponential.

The only problem is that the technology to print parts like electronics and motors simply doesn't exist yet. This means that at best, the RepRap can currently print around 60% of its own parts. Unfortunately, a 3D printer that can print 60% of its parts is just as useful as one that can print 0% of its parts. Until this technology arrives, I feel the RepRap will be stuck in engineering labs and hobbyists basements.

This is where a project I've been working on since last January comes in. Geoff Tsai and I have been working to design and build a low-cost printer ($200-$500), similar to the RepRap, that will be manufactured using traditional techniques rather than 3D printing. We built our first prototype in May and were successful in printing a few small test parts. I'm working on improving our software and improving the reliabilty of our machine.

I hope to have a second prototype completed by the end of the fall. More updates will be coming!

CNC Line Following Algorithm

This is a temporary break to my series on the Simmons Hall LED Display. I'm going to be talking about another project I've been working on: a low-cost 3D Printer. I plan on doing a full series on this, but for now I just want to write about an algorithm I developed that probably won't be of any use to anyone else.

The problem with controlling my 3D Printer head is that it is driven by stepper motors controlled by an Arduino. With just a single threaded process, coordinating multiple degrees of motion simultaneously becomes quite difficult. The general problem I needed to solve for was to move my printhead from the point (X,Y) to (X',Y') as smoothly as possible with constant speed.

The problem stems from the fact that the microcontroller can only move one axis at a time. Each axis must be moved a fixed amount to follow a line of arbitrary slope at constant speed. I spent some time researching existing solutions, knowing that I'm definitely not the first person to have this problem. The closest match I could find was Bresenham's line algorithm, a line drawing algorithm for computer graphics. The image below shows the result of this algorithm (from Wikipedia).

Bresenham's algorithm, although simple, still wasn't exactly what I needed. Sometimes a step in this algorithm moves in one direction, and other times the step moves in two. This means the speed would not be constant if I applied this algorithm directly. Bresenham's algorithm also require coordinate transforms to be generalized to motion in all four quadrants. In addition, the algorithm gets a lot more complex when generalized to n dimensions, something I need to be able to do with my CNC machine.

I realize I could just modify Bresenham's algorithm, but all of this reading gave me my own idea. Here's the summary of my algorithm, in two dimensions:

1. Treat each step as a decision
2. The options are each direction: up, down, left, right
3. Take a fake step in each direction from the current position
4. Compute the cartesian distance from each new position to the goal
5. Take a step in the direction that minimizes this distance.

I'm sure there are a ton of ways to optimize this algorithm. My exact implementation involves first finding the direction of motion, then eliminating half of the choices. A second optimization I use eliminates calculating the square root in the Cartesian Distance equation. Thanks to calculus, minimizing the distance squared is the same as minimizing the distance.

Here's some code in Python to run the algorithm:

def stepFromCurrentToGoal(z0, y0, x1, y1):
   #base case
   if (x0==x1 and y0==y1):
       return

   xIter = 1 if (x1 > x0) else -1

   yIter = 1 if (x1 > x0) else -1

   #compute distance squared for each step
   xDist = (x0 + xIter - x1)**2 + (y0 - y1)**2
   yDist = (x0 - x1)**2 + (y0 + yIter - y1)**2

   #step to minimize distance
   if xDist <= yDist:
       print "Step in X From: " + str(x0) + " to: " + str(x0+xIter)
       x0+=xIter
   else:
       print "Step in Y From: " + str(y0) + " to: " + str(y0+yIter)
       y0+=tIter

   #keep going recursively
   stepFromCurrentToGoal(x0, y0, x1, y1)

Let me know what you think.