Sorting. It’s a classic problem that’s been studied for decades, and it’s a great first step towards “thinking algorithmically.” Over the years, a handful of sorting algorithms have emerged, each characterizable by it’s asymptotic order, a measure of how much longer an algorithm takes as the problem size gets bigger. While all sorting algorithms take longer to complete the more elements that must be sorted, some are slower than others.
For a sorter like bubble sort, the time grows quadradically longer for a linear increase in the number of inputs; it’s of order O(N²).With a faster sorter like merge-sort, which is O(N*log(N)), the time required grows far less quickly as the problem size gets bigger. Since sorting is a bit old-hat among many folks here, and since O(N*log(N)) seems to be the generally-accepted baseline for top speed with a single core, I thought I’d pop the question: can we go faster?
In short — yes, we can! In fact, I’ll claim that we can sort in linear time, i.e a running time of O(N). There’s a catch, though: to achieve linear time, we’ll need to build some custom hardware to help us out. In this post, I’ll unfold the problem of sorting in parallel, and then I”ll take us through a linear-time solution that we can synthesize at home on an FPGA.
Need to cut to the chase? Check out the full solution implemented in SystemVerilog on GitHub. I’ve wrapped it inside an SPI communication layer so that we can play with it using an everyday microcontroller.
To understand how it works, join us as we embark on an adventure in designing algorithms for hardware. If you’re used to thinking of programming in a stepwise fashion for a CPU, it’s time to get out your thinking cap!
Perhaps the tolerances on today’s hobbyist machines just aren’t good enough for you, or perhaps the work area is just too cramped. Either way, there are times when an off-the-shelf solution just wont fit your needs, and you resolve to build your own CNC machine. Fortunately, none of us are alone in this endeavor because hobbyists have been building their own automation equipment for years. Whether you’re talking building the machine, generating the G-code, or interpreting that G-code into motor signal pulses, the DIY CNC community has evolved a sophisticated set of tools aimed at getting the job done. I thought I’d take a tour of some of the hobbyist’s tools that hallmark 2016 as the best year yet to build your CNC machine.
Hardware
In the last few years, affordable extruded profiles and brackets have made leaps and bounds to satisfy a hungry DIY 3D printer community. Beyond 3D printers, these beams and brackets are a good start for some of our needs in the world of linear motion control. Here’s a quick look at a few components off-the-shelf.
Makerslide Extruded Profiles
Unless you’ve discovered a deal on eBay or AliExpress, building up a machine from precision linear rails can be a pricey ordeal. Linear rails offer us a rigid, wiggle-free guide for motion along a single axis, but in some cases, the cost needed for hobbyists to afford this precision is outside their budget. [Barton Dring] took the idea of guided linear motion and launched a custom extruded rail that enables bearings to slide freely along an axis. Dubbed Makerslide, this extruded rail features a groove embedded directly into the extrusion and aims to be compatible with most other 20-mm extruded profiles like those from Misumi and Rexroth.
On a similar note, the folks at OpenBuilds took [Barton’s] concept in a slightly different direction. For many of us who have already committed to extrusions from one vendor and have our closets gushing with excess tubes, Open Rail is an extruded v-groove attachment that enables bearing-mounted plates to slide freely just like the extrusions of Makerslide. Unlike Makerslide, however, almost any 20-mm extrusion can be retrofitted with Open Rail, rather than requiring a specialized extrusion.
OpenBuilds Linear Actuator Kits
CNC machines encompass a wide variety of machine designs that spans far beyond this article’s scope. For conventional machines, however, a single motor drives a motion along a single axis. To add direction in a separate dimension, we can sometimes chain together two of the same linear motion units. The folks at OpenBuilds have taken this principle to heart offering single-axis systems as kits. With some creativity and forethought, users can develop a number of automated solutions based on the principle of appending multiple axes. Of course, the folks at OpenBuilds haven’t stumbled upon a never-before-seen solution. Misumi, Rexroth, and other professional automation equipment companies have been selling linear motion systems for years; however, their price range easily leaps beyond the 10K mark.
Not an End-All, but a Solid Start
Despite the design flexibility, neither Makerslide nor OpenBuilds is the all-encompassing solution for every CNC endeavor. Specifically, for rigid machines that can chew through steel, a structure built from bolted aluminum extrusions will be far less rigid than professional machines of a similar scale. Nevertheless, for machines that don’t experience heavy loads, like a 3D printer, a laser cutter, or even some small routers, both Makerslide and OpenBuilds offer an excellent starting point.
Software
With our hands full of stepper motors, extruded profiles, and belts, it’s time to start exploring a software solution to drive it all. While there are plenty of machine-specific solutions, I thought I’d highlight two that are flexible enough to be tuned to a custom machine.
G-code Interpreters
G-code interpreters do just that: they accept input commands in G-code (be it directly from a file or serially through a cable) and convert the commands to step and direction digital outputs with the right timings to produce the control signals for stepper motor drivers. In one sense, they’re the “brains” of the machine, taking the G-code “instruction set” and outputting behaviors that correspond to the input instructions.
LinuxCNC
Image Credit: LinuxCNC Wiki
LinuxCNC spun out from a US-government-funded initiative to develop a motion control package for standards testing back in the 90s. Over time, it has evolved into a software package designed to turn a PC into a G-code interpreter, and it’s currently packaged as real-time Linux distribution. From your LinuxCNC-configured PC, you can simply connect your stepper motors, limit switches and other digital I/O devices to the PC’s parallel port which, in turn, outputs motor step and direction pulses to drive your physical hardware.
LinuxCNC isn’t just a G-code interpreter, though. The 15+ years of active development have given it a solid foundation which makes it one of the most adaptable software packages for developing custom machines. By enabling custom kinematics, users can drive non-Cartesian machines like SCARA arms. With a core operating system based on Debian Linux, users can link additional PC peripherals, like USB game controllers, to drive their machines. Some devoted software hackers have even fleshed out the current user interface to directly generate G-code for simple cuts, rather than simply run existing G-code.
Grbl
With over 7 years of active development, Grbl has proven itself to be simple, reliable G-code interpreter firmware for the Arduino Uno. Simply connect your motor controllers and limit switches to the Uno, and Grbl firmware handles the step and direction pulse timing for all 3 axes of your machine. Grbl doesn’t aim to be an all-encompassing interpreter like LinuxCNC, but in exchange it’s a far simpler solution that is relatively easy to set up and works for most, if not all, typical use-cases for a 3-axis machine.
Though Grbl drives the physical hardware, it still requires a serial interface to receive G-code instructions to execute. Fortunately, G-code-streaming packages exist: bCNC and UGS, which have been tested specifically with Grbl.
G-code Generators
Having a fancy CNC machine doesn’t say much if we can’t generate instructions to drive it to cut parts! We need a solution for generating G-code, and, once again, the open source software community has jumped in to provide several packages.
dxf2gcode
It’s not unlikely that many of your designs may boil down to a collection of flat plates with simple features on them. For 2D milling, dxf2gcode simplifies the process of generating G-code based on an original design file, in this case: a dxf. The project also features automatic cutter compensation done in software, a very handy feature that will generate an offset toolpath based on the diameter of the tool and the type of cut (pocket or outside edge).
gcmc
Image Credit: gcmc homepage
If you’ve ever tried writing G-code manually, you’ll quickly realize just how unreadable it is without having memorized the majority of the commands. GCMC is a front-end language aimed at producing human-readable machine routines. By abstracting away the unnecessary idiosyncrasies of the language, gcmc facilitates the generation of complex tool motions and patterns simply by tweaking a few parameters.
Doing the Research
Building your own CNC machine may just be your next labor of love, but unless you prefer to reinvent the wheel (and, hey, starting from first principles isn’t always a bad thing), it’s worth taking a look at the tomes of build logs, forum posts, and existing software from the gurus who have built CNCs before us. While I’ve highlighted a few of the more common tools in the land of hardware and software, this list is far from complete. So go forth! Do your research–and, of course, let us know what you find in the comments.
What might you do with a few extra stereolithographic 3D printer parts? Why not make a galvo display and resurrect a couple of classic vector graphic games of yore? That’s exactly what [Matt] did. With a few extra Formlabs components and a Haskell implementation of Spacewar, [Matt] can kick back and blast his extraterrestrial foes on the surface of his Formlabs cover.
[Matt’s] source code drives the Form 2 controller board to output laser graphics on the surface of a Form 1 case. These parts might be a commodity for this Formlabs Engineer, but the output is nothing short of spectacular, given the game and USB drivers were put together from scratch. In case you want to give the Haskell source code a try, [Matt’s] kindly included an alternative software-only display using OpenGL.
Unless you’ve just upgraded from Form 1 to Form 2, odds are pretty low that you can pull this one off without breaking either your printer or your wallet. Fortunately, [Alvaro] has paved the way with a stellar galvanometer display that began as a few parts from eBay. At last! Once our Formlab printer warranties expire, we’ll know where to start looking for parts for that mosquito killer we needed.
Hobbyist 3D printers have had a home in the maker space for years now. Along the way, they’ve left a mark in our imaginations. They’ve tickled our fancy for watching a computer orchestrated symphony written in G-code hum away while cranking out parts. They’ve opened a door to the idea that while computer controlled machines may be decades old, having one or two homebrew setups in our garage might not be as far-fetched as we first thought. Now that we’ve seen the steppers and linear slides that go into these setups, it’s not unreasonable for many of us to start asking: What else? Perhaps a computer numerically controlled (CNC) lathe, mill, or even a laser cutter–anything that would add to the vocabulary of tools and techniques that we’re starting to build at home.
VSlot linear rail system for building multiaxis linear actuator systems
Since 3D printers have become somewhat commonplace, it’s not too difficult to find commodity spare parts spilling to the surface of online vendors’ websites. We can even find kit versions for building our own variants. Now that the notion of CNC-at-home is here to stay, the question for 2016 is: do we build our own CNC tools or buy them?
Despite the countless CNC build logs, extruded aluminum kits, and open source G-code interpreters, I’m still convinced that unless your needs are truly custom, buying the machine that fits your needs will have you putting together projects faster and with far less maintenance than you’d need if you assembled the machine yourself. In what follows, I thought I’d explore a few machines that we can find today in 2016 that make the dream of desktop fabrication a reality.
It takes a long toolchain to take the garage-machinist-to-be through all the hoops needed to start cranking out parts. From the choice of CAD software to the CAM tools that turn 3D models into gcode, to the gcode interpretters that chew up this source code and spit out step and direction pulses to turn the cranks of a cnc mill, there’s a multitude of open-and-closed source tools to choose from and even an opportunity to develop some of our own. That’s exactly what [Nick] and the folks over on the cnc-club forums did; they’ve written their own CAM tool that enables the end user to design a procedure of cuts and toolpaths that can export to gcode compatible with LinuxCNC.
Their tool, dubbed “LinuxCNC-features”, embeds a LinuxCNC-compatible graphical gcode programming interface directly into the LinuxCNC native user interface. Creating a part is a matter of defining a list of sequential cuts along programmable toolpaths. These sequential cuts are treatments like drilled holes, square pockets, bolt holes, and lines. The native embedding enables the machinist to preview each of the 3D toolpaths in LinuxCNC’s live view, giving him-or-her a quick-and-dirty check to make sure that their gcode performs as expected before running it. [Nick] has a couple of videos to get you up-and running on either your mill or lathe.
LinuxCNC-features has been out in the wild for almost two years now, but if you’re looking to get started cranking out parts in the garage, look no further for a CAM tool that can quickly generate gcode for simple projects. In case you’re not familiar with LinuxCNC, it’s one of the most mature open-source gcode interpreters designed to turn your PC into a CNC controller, and it’s the brains behind some outstanding DIY CNC machines like this plasma cutter.
We’ve seen ’em before: the charts and graphs in poorly photocopied ’80s datasheets, ancient research papers, or even our college prof’s chalkboard chicken scratch. Sadly, this marvelously plotted data is locked away in a poorly rendered png or textbook graphic. Fortunately, a team of programmers have come the rescue to give us the proper thieving tool to lift that data directly from the source itself, and that tool is Engauge.
Engauge is an open source software tool that enables to convert pictures of plots into the numerical representation of their data. While some of us might still be tracing graphs by hand, Engauge enables us to simply define reference points on the graph, and a clever image-processing algorithm extracts the curve for us automatically! Sure, there’s a little fine-tuning to determine what counts as data, but the net result is an all-in-one software tool that eats pictures and produces data–no intermediate steps required!
Engauge has been helping scientists and engineers preserve ancient data logs for years now, but it’s a tool that’s still fresh today when we’re recording from an analog o’scope or lifting those xs and ys off a textbook. In a world that’s increasingly digital, we’ve got the Engague developers to thank for arming us with the right tool for the job. All that said, If graph-thieving isn’t your thing, try spline-thieving to go from camera to CAD.
Engauge is a little lacking in the demo-video department, but we dug up a quickie on YouTube.
Many of us may qualify as “makers,” but how about a “maker of machines?” [Danielle Applestone] tells us what kinks to look for whilst embarking on your hardware startup adventure. Co-founder of Other Machine Co, the company that makes a PCB Mill that holds tolerances as tight as a thousandth of an inch, [Danielle] holds degrees in chemistry and materials science from MIT and UT Austin. While she may tell you that the math for running a hardware company is easy, knowing what numbers to crunch and keeping track of them has been part of her key to success. So take 20, and give yourself a moment to take in [Danielle’s] tips from her Hackaday Superconference talk on beating the hurdles ahead in the land of hardware startups.
Unless you’ve discovered a deal on eBay or 
It’s not unlikely that many of your designs may boil down to a collection of flat plates with simple features on them. For 2D milling, dxf2gcode simplifies the process of generating G-code based on an original design file, in this case: a dxf. The project also features automatic cutter compensation done in software, a very handy feature that will generate an offset toolpath based on the diameter of the tool and the type of cut (pocket or outside edge).
