Polygon software

When you slice an STL file with a plane, the result is one (or more) polygons. These have to be filled with RP goo somehow to make a solid in layers. As we are going for FDM, this means offsetting the polygon by half the width of the stream, outlining it with goo, then offsetting again and cross-hatching to fill the interior.

I have been writing Java software to do this. I have decided to do a CSG implementation of polygons as unions, intersections, and differences of planar half spaces (i.e. you treat an infinite straight line as being solid on one side and air on the other so, for example, if you intersect three such you make a triangle).

The reason for this is that, compared to the more obvious solution of storing a linked list of line segments between vertex points, once you've got it working it makes polygons that are guaranteed never to self intersect, are easy to offset correctly, and can themselves be easily combined using boolean operations. The downside is that you have to turn the original slice into a CSG form from what is basically an unstructured bunch of line segments that may join up if you're lucky. Fortunately there's an algorithm for that - Tony Woo's alternating sum of volumes algorithm. Implementing that is my next task.

The picture above shows a test polygon, and the result of offsetting it. If you increase the offset, it all behaves nicely, and automatically avoids lines crossing each other:




Cross-hatching for infill is fairly easy. Here's an inner and outer polygon, both offset, then the result cross-hatched:



Though I haven't finished that yet - it detects the region in the middle to avoid (different colour), but doesn't link up neatly around it to minimize pen-off-the-paper moves.

How do we do a whole 3D object?

Well, Java3D will read STL files. We slice them from the top down in layers. Imagine that you're at layer N, and the next layer up where you were before is layer N-1. If U is union, - is set difference, P_N is the polygon now (at layer N), and P_N-1 is the one above, then:

1. Get slice P_N.
   
2. Fill P_N with build material.
3. Fill P_N-1 - P_N with support.
4. P_N <- P_N-1 U P_N.
5. N <- N + 1.
6. If not off the bottom, go to 1.

That defines exactly what needs to happen right the way from the top to the bottom. You work it all out, then play it in reverse from the bottom to the top. This is all particularly simple if U and - are trivial operations, which they are in my implementation. Offsetting is pretty simple too, so things like being able to build slight overhangs without support can easily be accomodated by replacing Step 4. with:

4. P_N <- O{(P_N-1 U P_N), -shrink}

where O{set, distance} is the offset function, and shrink is the width of the overhang that can be sustained.

Job done...