Walls and winding

Third post in the Katana series. Post 1 was the basic slicer, Post 2 was the viewer. The viewer made things pretty, but the output is still just a bunch of sliced contours, which is far from useful still.

If you tell the nozzle to follow the contour exactly, it won’t print the part you want. The extruded bead of plastic has width (~0.4mm for a typical nozzle), so if the contour sits on the actual edge of the part and the nozzle is centered on the contour, half the bead ends up outside the part. To fix this we need to shift the contour inward by half the nozzle diameter before printing. That operation is called polygon offsetting, and it’s the first piece of genuinely printer-specific logic Katana needs.

For multiple walls instead of just one line, we keep offsetting inward by a full nozzle width for each additional perimeter. Three perimeters is the usual sweet spot - one for the visible outer surface and two more for structural strength, but we’ll need to make this parameterizable. Also, another complication is that a layer may have multiple concentric contours, which means the outermost is “positive” (we deposit material on the inside) and the innermost is “negative” (it’s an inner layer limit, or a hole). So we also need to classify those, and offset the positive contours inwards, and the negative contours outward.

Not writing this from scratch

Polygon offsetting is one of those problems that looks trivial for about ten seconds and then descends into madness. Self-intersections, cusps, collapsing holes, islands that pinch into multiple pieces as they shrink… it’s a proper minefield. I didn’t even attempt to implement it by hand, so I pulled in the i_overlay library, which handles 2D boolean ops and offsetting and is really well optimized.

To define perimeters, this is what I ended up on:

pub struct Perimeter {
    pub points: Vec<Point2<f32>>,
}

pub struct PerimeterSet {
    /// Ordered from outermost (index 0) to innermost.
    /// Each level may contain multiple disjoint loops.
    pub perimeters: Vec<Vec<Perimeter>>,
    /// The innermost offset boundary, where we add infill
    pub infill_boundary: Vec<Contour>,
}

pub struct ToolpathLayer {
    pub z: f32,
    pub perimeter_sets: Vec<PerimeterSet>,
}

A PerimeterSet is everything that comes out of one shape - an outer contour with any holes inside it. A single layer can have multiple disjoint shapes.

Why Vec<Vec<Perimeter>> instead of just Vec<Perimeter>? Because as you offset a shape inward, it can pinch in the middle and split into multiple disjoint loops at the same perimeter level. Picture offsetting a thick H - at some point the crossbar detaches from the legs, and you have three separate loops where there used to be one. Each “level” therefore needs to be a Vec<Perimeter>, not a single one.

The shoelace formula

The offsetting library needs to know which loops are outer contours and which are holes. The convention in 2D geometry is that outers are wound counter-clockwise (CCW) and holes clockwise (CW). But my slicer just spits out contours in whatever order the triangle intersections happen to walk around the mesh, so there’s no guarantee either way.

To compute the winding of a polygon, we need to learn about the shoelace formula:

fn signed_area(points: &[Point2<f32>]) -> f32 {
    let mut area = 0.0f32;
    let n = points.len();
    for i in 0..n {
        let j = (i + 1) % n;
        area += points[i].x * points[j].y;
        area -= points[j].x * points[i].y;
    }
    area / 2.0
}

This is just a math trick to use the Gauss polygon calculation formula, you can calculate the area of any polygon defined by a set of points in space, and it might wind up positive or negative. By definition, positive area = CCW, negative area = CW. If a contour has the wrong winding for its role, we reverse the point list, done.

Took some time to figure it out, but the basic algo for offsetting came down to this:

for each layer:
    shapes = classify(layer.contours)
    result = []

    for each shape in shapes:
        current = [shape]
        perimeters = []

        loop up to config.perimeter_count:
            next = []
            rings = []

            for each s in current:
                offsets = inset_shape(s)

                collect valid rings from offsets into rings
                add offsets to next

            if rings is empty:
                stop loop

            add rings to perimeters
            current = next
        boundary = collect valid rings from current
        add (perimeters, boundary) to result
    return result

Going parallel

At this point, slicing the liver STL + generating toolpaths was taking noticeably long. The outer loop (over layers) is very parallelizable, because each layer is independent, so I used rayon to swap the iter() calls for par_iter(). Basically a 3-line diff for a near-linear speedup on my 10-core machine.

Next I need to look at building the infill logic, and displaying the toolpath in the viewer.