Reprap host software
The RepRap host software.
The RepRap host software implements the "slicer" and the "G-code sender", key parts of the CAM Toolchains. For other, arguably better, implementations of a slicer or a G-code sender or both, see RepRap Options#CAM Tools.
If you want to install and use the RepRap host software, see DriverSoftware. If you want to help us make the RepRap host software better, or you are simply curious about technical details of the algorithms used internally by the RepRap host software, please read on.
The code that runs on the computer controlling a RepRap machine is written in Java. You can find the Javadocs for it here and browse all the code on Sourceforge here. For installation instructions, please see here or the pages for: Linux, Mac and Microsoft. Below is an explanation and further documentation on how the host software works.
STLs are read by a standard Java3D file format handler that returns them as Java3D objects. These are basically lists of triangles in space - three doubles per corner. When you read an STL object in, RepRap forces you to assign a material that it's made from; this is attached as a Java3D user attribute to the triangulation.
Slicing at height Z is done by running through all the triangles one material at a time (so all the printing for one material in a given layer is done before it moves on to the next material in that layer in a multi-material system). Each triangle has Z coordinates that are:
1. All below the slice - add that triangle to the triangulation of the bit already built. 2. All above the slice - forget it. 3. Two below, one above, or vice versa - add the line of intersection of the triangle with the Z plane to the list of edges of the polygons to be laid down at this layer. Add the triangle or quadrilateral (split along a diagonal to make two triangles) below the Z plane to the triangulation of the bit already built.
The triangulation of the bits already built is used in the simulation window to show the object up to the plane that is currently being laid down.
We now have a set of jumbled line segments that ought to meet end to end (roughly - floating point rounding problems etc) and that form a collection of polygons in this layer to be laid down. Polygons may be inside each other (holes in solids) and inside them (islands in holes, and so on) or disjoint. But they should never cross. This is all pretty crappy high-entropy data because of the totally useless and ustructured nature of STL files. If STL had been designed properly you'd know what connected to what all the way down.
The first problem is to join the line segments up end-to-end. The way this works is to slap a rectangle round the lot (easy, because you can track max and min X and Y coordinates as you generate the segments) and then to divide that in a quad tree. The terminating conditions for the recursive code that makes the tree is that a quad contains either no ends, or just two ends of different segments. The trick here is obviously to ensure that a quad division does not go down between two ends that really need to be joined so that they wrongly end up in two different quads.
The program then runs round the polygons from quad to quad linking the ends up.
We now have a set of polygons for RepRap to outline and to fill in. But a list of line segments is a very non-robust representation of a polygon for operations like zig-zag infill, and also it's hard to offset. You need to offset the polygons to make smaller ones inside because the stream of polymer is not zero thickness, so - for example - you need to run the write head slightly inside the polygon you're going to create to outline it. Then the zig-zag infill needs to be a zig-zag in a smaller polygon inside the first offset polygon too.
A set-theoretic (or CSG, or Boolean) polygon representation is robust and is easy to offset, so this is what RepRap creates. It uses a trick invented by Tony Woo called the alternating sum of volumes. You find the convex hull of the polygon, turn that into an intersection of linear half planes (that is things like Ax + By + C <= 0) for all the polygon edges that lie on the hull, then work out the convex hulls of the bits that wern't on the hull and subtract them, then the bits that are left from that and union them, and so on recursively.
It now has a CSG representation of the entire layer as unions and intersections of linear half planes. This can be offset simply by changing the C values - really easy. It is also easy to cross-hatch - you just generate a load of parametric lines and work out the parameter values where they cross the CSG boundaries. For each segment of hatch you membership-test its mid-point against the CSG expression to find out if it's solid or air.
All this CSG stuff is made very fast and very efficient by another quad-tree division. This time that looks at the contributions of each linear half-plane to each quad. Such a plane either cuts the quad, or contributes Universal or Null set to it. In the latter two cases the CSG expression can be simplified using De Morgan's rules inside the quad. Once again this structure can be built recursively, giving a fast-to-search structure both for outlining and infill hatching (credit for this idea: my old chum John Woodwark in the 1980s).
The outlining is done by running round the quads stitching up polygons between quads that contain an intersection or a union of just two half-planes (in other words, they contain a corner). Because of the robustness of the CSG representation this process is guaranteed not to to have any gaps or overlaps (unlike the original crappy STL file, and unlike the unstructured jumble of line segments derived from it).
The infill zig-zag has its ends stitched together by a follow-round-the-edge heuristic that reduces (though not minimises*) the in-air not-plotting movement.
[*Clearly to minimise the in-air moves would need a traveling salesman solution, so we don't have time for that :-)]
Detailed description of geometry processing
Click on the links in the following sections to go to pages describing how each stage in the geometry processing works.
Reading in 3D objects is the first step that the software needs to take. This describes how a shape is represented in a file and how that is read.
Slicing the objects to make each build layer is what needs to be done next. RepRap builds in layers. These are flat planes parallel to the XY plane. Each such plane needs to slice across the object to be built, and that slice has to be represented.
Organizing a slice into coherent 2D geometry is needed because there is almost no structure in the standard 3D descriptions (STL files) that rapid prototyping machines use. Structure has to be imposed algorithmically.
Evaluating 2D geometry has to be done because RepRap uses a CSG or Boolean or Set-Theoretic representation of shapes. Such a representation is very robust, but it is also implicit, which means that it has to be evaluated in order to do things like finding its edges.
Offsetting 2D geometry is needed because the filament that the RepRap write head extrudes has a certain thickness. To get the edge of that filament in the right place, the centre of the write head has to be offset from that edge by half that thickness.
Generating cross-hatch infill is the way that RepRap fills in areas of the slice that need to be solid in the finished part.
Arc compensation is needed when the extrude head is moving in a circular arc because the inside of the arc has a smaller area than the outside, but the extrude head puts material down evenly on either side of its centre line. This page describes how arc compensation works.
There is a page on setting up NetBeans here. This is only really useful if you want to get into GUI development, or profiling.
-- Main.AdrianBowyer - 02 Dec 2007
G code processing
(Is there a more appropriate page to summarize the algorithms used in the G code processor and other firmware than this "host software" page?)
The end result of the above "geometry processing" is a long sequence of G codes. G codes are more-or-less standardized codes that can be sent to a variety of CNC hardware.
People involved in the RepRap project typically use these G codes in one of the following ways:
- An integrated slicer & print program immediately sends each G code to the 3D printer as soon as it is generated.
- All the G codes are stored in a text file on disk. Later, a printer communication program (such as ArduinoSend) downloads those G codes, one at a time, to the 3D printer, which executes them.
- "stand alone printer": All the G codes are stored in a text file on a memory card. Later, when a person plugs that memory card into a 3D printer, the 3D printer reads G codes out, one at a time, and executes them.
Those methods require the printer to implement a G code interpreter in their firmware.
However, a few people involved in the RepRap project use a G code interpreter running on the host.
- All the G codes are stored in a text file. Later, Virtual Mendel software, including a G code interpreter, on the host lets people view a "print preview".
- "simplified electronics printer": All the G codes are stored in a text file. Later, a G code interpreter running on the host converts each G code to a easier-to-parse step sequence, and sends them to the 3D printer, which executes them. (Alas, there are a variety of incompatible ideas for this "easier-to-parse" over-the-serial-wire format, an Firmware/Alternative#alternatives to G-code. A working CAM Toolchains requires the host and the firmware to use the same format)
There's also a few people working on completely bypassing the G code layer -- rather than chop a rounded, curvy object into thousands of STL triangles which are converted to millions of tiny straight-line G code motions, perhaps it would be better to slice it into a few smooth curves and feed those curves into a elegant multispline motion controller or some other alternative to G code.
The G code interpreter (whether on the host or in the 3D printer) converts the absolute and relative motions, in units of inches or centimeters, in the G code file to absolute motions in units of "steps". The absolute position 0,0 is the "home" position. The "STEPS_PER_MM" parameter ...
other firmware processing
Most of the time, the firmware is in a tight inner loop:
- Use the Bresenham algorithm (dda) to decide which motor gets the next step pulse (nearly always it's either X, Y, or Extrude).
- wait for the stepper motors to settle to the new XYZE position
- pulse the "step" line to the pre-selected motor
Real, physical objects can't gain full speed instantly. Also, according to Teacup Firmware, "if acceleration is reliable, you can approximately double the speed of stepper motors without risking loss of steps." There seems to be several different, incompatible ways to deal with acceleration ...
The extrusion motor also can't be started and stopped instantly.
- accelerated extrusion (Repic5D)
- Mattroberts' Firmware has special extrusion "pressure management" code
The heaters, alas, also can't be instantly set to the correct temperature.
- heater control -- most implementations currently require manual PID tuning
It makes debugging the firmware, the electronics, and the other hardware much easier if the firmware supports
- a person typing commands in a serial terminal window to the 3d printer
- the 3d printer sending back status information to the serial terminal in more-or-less human readable format: absolute position, temperatures, firmware version (typically including the preprocessor variables "__DATE__" and "__TIME__" and the M115 Read Firmware Identification command ), etc.
After we install a bootloader such as Burning the Sanguino Bootloader, later updates to the firmware go much quicker.
Firmware also handles:
- endstop handling
- fixed-point math
- The Hydra-MMM Software and Firmware supports the "switch tool" commands