Filling the void

Fourth post in the series. After perimeters, the part has walls but is hollow in the middle. Today we’ll talk about infill (and also, some optimizations)

Rectilinear infill

The simplest and most common infill pattern is a grid of straight lines, so that’s what I picked up for the moment (will try implementing some other patterns later). The algorithm is very simple:

given: infill_boundary (innermost perimeter offset), density, nozzle_width
spacing = nozzle_width / density
for each scan line at `spacing` apart, horizontal and vertical:
    clip the line against the boundary polygon
    emit each resulting segment as an InfillLine

In reality I flipped the scan lines by 45 degrees, as is the default, for strength, an infill that’s parallel to the part’s walls is more likely to yield weak spots for low density infilling.

The clipping is the only interesting part. A scan line crossing the infill region might produce multiple segments if the region has holes or concave dips (picture a scan line crossing a donut horizontally through the middle: you get two disjoint segments, one on each side of the hole). I’m relying again on i_overlay to do the clipping, using clip_by once per scan line:

for line in &scan_lines {
    let clipped = vec![line.clone()]
        .clip_by(&shapes, FillRule::EvenOdd, clip_rule);
    for segment in &clipped {
        if segment.len() >= 2 {
            all_lines.push(InfillLine {
                start: from_overlay(&segment[0]),
                end: from_overlay(segment.last().unwrap()),
            });
        }
    }
}

Need to do it twice, once in each orientation

The final output is a Vec<InfillLine> per layer. The viewer renders them in a different color than the perimeters so you can toggle them independently. I also added a --density flag to the CLI to make it parameterizable.

Slashing slowness so some STLs slice sub-second

With infill working end-to-end, slicing the liver STL took a while. I had left a TODO comment in the slicer weeks ago that I was really hoping I wouldn’t have to come back to:

// TODO: currently iterates every triangle for every layer
// (O(triangles × layers)). Optimize with a sorted sweep...

Yep. Every layer was scanning all 90k liver triangles to find which ones intersected it. That’s around 35 million triangle checks per slice. Which is dumb, because any given triangle only spans a tiny z-range and there’s no reason to ever look at it from a layer outside that range.

Sorted sweep with binary search

The fix is the classic sweep-line idea: for each triangle, pre-compute z_min and z_max, sort the list by z_min, and then for a layer at height z, every candidate triangle satisfies z_min <= z <= z_max. The lower bound lets us skip most of the list with a binary search:

struct TriZRange {
    z_min: f32,
    z_max: f32,
    tri_idx: usize,
}

// Build the index once
let mut z_index: Vec<TriZRange> = mesh.triangles.iter().enumerate()
    .map(|(i, tri)| {
        let zs = [tri.vertices[0].z, tri.vertices[1].z, tri.vertices[2].z];
        TriZRange {
            z_min: zs[0].min(zs[1]).min(zs[2]),
            z_max: zs[0].max(zs[1]).max(zs[2]),
            tri_idx: i,
        }
    })
    .collect();
z_index.sort_unstable_by(|a, b| a.z_min.partial_cmp(&b.z_min).unwrap());

// For each layer
let upper = z_index.partition_point(|t| t.z_min <= z);
for entry in &z_index[..upper] {
    if entry.z_max < z { continue; }
    // ...actual intersection logic
}

partition_point is a binary search for the first element failing a predicate. Here, it finds the index after which no triangle has z_min <= z. Within the prefix we still have to filter by z_max, but in practice the “active window” at any given height is tiny (hundreds, not thousands), so we’re effectively doing O(layers log triangles + total_active_hits) instead of O(triangles × layers). Enormous difference.

A proper interval tree would probably be cleaner, but sorted-sweep-with-filter is ~20 lines of code and already fast enough to not be the bottleneck anymore. I’ll upgrade it if it ever matters (or if I feel like implementing this type of tree in Rust), but that’s probably overkill.

HashMap for contour assembly

The other hot spot lived in assemble_contours - the function that chains raw intersection segments into closed polygons by matching endpoints. My original version did linear scans through every remaining segment to find the next one to chain, which is O(n^2) per layer. For layers with thousands of segments (dense meshes hit this easily), it was dragging.

Classic fix: hashmap from endpoint → segment index. The annoying wrinkle is that endpoints are f32 pairs, which don’t hash and aren’t exact-equal-comparable. So I quantize endpoints to integer keys at 1e-3 tolerance ,aka “close enough”:

fn quantize(v: f32) -> i64 {
    (v * 1000.0).round() as i64
}

In the end of the day, the slicing process was optimized enough as to not matter in comparison with the time it took to render the final result. That’s where my next optimization efforts will lay, and there’s a world of things to do in the renderer.

Next steps

The slicer now produces perimeters and infill for every layer, but the order they’d be printed in is essentially random. That’s fine for a preview but useless as a print. Before we can generate real G-code, we need a toolpath planner, a process that decides which segments to print when, where to travel without extruding, and how to not waste half the print time bouncing the nozzle across the bed. That’s next.

See ya!