Reprap host software

The RepRap host software.

The code that runs on the computer controlling a RepRap machine is written in Java. You can find the Javadocs for it here. These pages describe how it all works.

Overview

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 - it is in this code that Vik's bug lies. 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; it is in this bit that I am bug hunting.

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 :-)]

-- Main.AdrianBowyer - 02 Dec 2007