nx_infill.nx source

1// nx_infill.nx -- scan-line infill pattern generator for closed 2// NxPolygon contours. Produces line segments that the G-code 3// emitter prints as rectilinear infill inside the perimeter. 4// 5// Algorithm: classical scan-line fill (Foley/van Dam 1990). 6// 1. compute polygon bbox 7// 2. for each horizontal scan line at y = bbox.min_y + k*spacing: 8// a. find x-coord where each polygon edge crosses y 9// (skip horizontal edges; integer cross-multiply form) 10// b. sort x-coords ascending 11// c. pair consecutive crossings; emit segment per pair 12// 13// Spacing derived from line_width + density_pct: 14// spacing_mm = (line_width_mm * 100) / density_pct 15// Density 100% = touching lines, 50% = 50% air, 25% = 75% air. 16// 17// Grid pattern (perpendicular alternation per layer for better 18// mechanical isotropy): when called with vertical=1, the algorithm 19// runs on a transposed (x<->y) coordinate system, producing 20// vertical scan lines. Caller toggles `vertical` per layer index. 21// 22// Reuses NxSliceSoup as output (same flat-segment shape as 23// nx_slice_plane; downstream G-code emitter consumes either). 24// 25// Composes nx_polygon (closed contour input) + nx_qsort_i64 26// (crossing-coord sort) + nx_slice_plane (segment soup output type). 27// 28// Per cardinal NISHI_3D_PRINT_ROADMAP §2.x infill: lines pattern v1 29// is the substrate floor. Honeycomb / gyroid / cubic are future 30// patterns queued for after this primitive validates on real prints. 31// Per cardinal feedback-bits-up-exceed-never-match: substrate ships 32// the universal scan-line core; richer patterns layer on top, NOT 33// instead of, this primitive. 34// 35// Pure i64 arithmetic throughout (integer cross-multiply avoids 36// division during the straddle test; one division per crossing for 37// the x-coord computation). 38// 39// license_tier: ORIGINAL 40 41import "nx_syscalls.nx" 42import "nx_polygon.nx" 43import "nx_slice_plane.nx" 44import "nx_qsort.nx" 45 46// ===== sealed-enum patterns ======================================== 47 48const NX_INFILL_PATTERN_LINES: i64 = 0 49const NX_INFILL_PATTERN_GRID: i64 = 1 // alternating dir/layer 50const NX_INFILL_PATTERN_HONEYCOMB: i64 = 2 // queued 51const NX_INFILL_PATTERN_GYROID: i64 = 3 // queued 52 53// ===== verdicts ==================================================== 54 55const NX_INFILL_OK: i64 = 0 56const NX_INFILL_ERR_BAD_POLYGON: i64 = 1 57const NX_INFILL_ERR_BAD_DENSITY: i64 = 2 58const NX_INFILL_ERR_BAD_PATTERN: i64 = 3 59const NX_INFILL_ERR_CAPACITY: i64 = 4 60 61func nx_infill_verdict_name(v: i64) -> *u8 { 62 if v == NX_INFILL_OK { return "OK" } 63 if v == NX_INFILL_ERR_BAD_POLYGON { return "BAD_POLYGON" } 64 if v == NX_INFILL_ERR_BAD_DENSITY { return "BAD_DENSITY" } 65 if v == NX_INFILL_ERR_BAD_PATTERN { return "BAD_PATTERN" } 66 if v == NX_INFILL_ERR_CAPACITY { return "CAPACITY" } 67 return "UNKNOWN" 68} 69 70// ===== scan-line implementation =================================== 71// 72// Given a polygon and a horizontal scan line y, fills `out_xs` with 73// the x-coordinates of crossings (sorted ascending) and returns the 74// crossing count. Skips horizontal polygon edges to avoid div/0. 75// 76// The integer cross-multiply form is used to compare: 77// x_crossing = xi + (y - yi) * (xj - xi) / (yj - yi) 78// The division is only done ONCE per crossing (when we materialize 79// x_crossing for sorting + emit). No floating point. 80 81func nx_infill_scanline_xs(poly: *NxPolygon, y: i64, 82 out_xs: *i64, max_xs: i64) -> i64 { 83 var count: i64 = 0 84 var i: i64 = 0 85 while i < poly.n_verts { 86 var j: i64 = i + 1 87 if j >= poly.n_verts { j = 0 } 88 let xi: i64 = nx_polygon_get_x(poly, i) 89 let yi: i64 = nx_polygon_get_y(poly, i) 90 let xj: i64 = nx_polygon_get_x(poly, j) 91 let yj: i64 = nx_polygon_get_y(poly, j) 92 // Strict straddle: (yi > y) != (yj > y). Horizontal edges 93 // (yi == yj) fall out naturally -- both > y conditions 94 // identical -> NOT a crossing. 95 var yi_above: i64 = 0 96 if yi > y { yi_above = 1 } 97 var yj_above: i64 = 0 98 if yj > y { yj_above = 1 } 99 if yi_above != yj_above { 100 let dy: i64 = yj - yi 101 let dx: i64 = xj - xi 102 // dy != 0 here because yi != yj (otherwise both `_above` 103 // would be identical). Safe to divide. 104 let x_cross: i64 = xi + (y - yi) * dx / dy 105 if count < max_xs { 106 out_xs[count] = x_cross 107 count = count + 1 108 } 109 } 110 i = i + 1 111 } 112 return count 113} 114 115// Transposed variant: same algorithm but swap x<->y. Used when 116// `vertical = 1` to produce vertical scan lines. Returns y-coords 117// of crossings for a given scan x. 118 119func nx_infill_scanline_ys(poly: *NxPolygon, x: i64, 120 out_ys: *i64, max_ys: i64) -> i64 { 121 var count: i64 = 0 122 var i: i64 = 0 123 while i < poly.n_verts { 124 var j: i64 = i + 1 125 if j >= poly.n_verts { j = 0 } 126 let xi: i64 = nx_polygon_get_x(poly, i) 127 let yi: i64 = nx_polygon_get_y(poly, i) 128 let xj: i64 = nx_polygon_get_x(poly, j) 129 let yj: i64 = nx_polygon_get_y(poly, j) 130 var xi_right: i64 = 0 131 if xi > x { xi_right = 1 } 132 var xj_right: i64 = 0 133 if xj > x { xj_right = 1 } 134 if xi_right != xj_right { 135 let dx: i64 = xj - xi 136 let dy: i64 = yj - yi 137 let y_cross: i64 = yi + (x - xi) * dy / dx 138 if count < max_ys { 139 out_ys[count] = y_cross 140 count = count + 1 141 } 142 } 143 i = i + 1 144 } 145 return count 146} 147 148// ===== main entry ================================================= 149// 150// Generates lines / grid infill segments for `poly` at `density_pct` 151// fill density, writing into `out` (which the caller pre-allocates 152// with sufficient capacity). 153// 154// `vertical = 0` -> horizontal scan lines (typical even layer). 155// `vertical = 1` -> vertical scan lines (typical odd layer for grid). 156// 157// `line_width_q14` = the width of the extruded bead, used to derive 158// scan spacing. Caller passes the same value used by the G-code 159// emitter for consistency. 160 161func nx_infill_lines(poly: *NxPolygon, density_pct: i64, 162 line_width_q14: i64, vertical: i64, 163 out: *NxSliceSoup) -> i64 { 164 if (poly as i64) == 0 { return NX_INFILL_ERR_BAD_POLYGON } 165 if poly.n_verts < 3 { return NX_INFILL_ERR_BAD_POLYGON } 166 if density_pct <= 0 { return NX_INFILL_ERR_BAD_DENSITY } 167 if density_pct > 100 { return NX_INFILL_ERR_BAD_DENSITY } 168 if line_width_q14 <= 0 { return NX_INFILL_ERR_BAD_DENSITY } 169 170 let spacing_q14: i64 = line_width_q14 * 100 / density_pct 171 if spacing_q14 <= 0 { return NX_INFILL_ERR_BAD_DENSITY } 172 173 // BBox in Q14 174 let bb: *i64 = (sys_mmap(32)) as *i64 175 if nx_polygon_bbox(poly, bb) != NX_POLYGON_OK { 176 return NX_INFILL_ERR_BAD_POLYGON 177 } 178 let bb_min_x: i64 = bb[0] 179 let bb_min_y: i64 = bb[1] 180 let bb_max_x: i64 = bb[2] 181 let bb_max_y: i64 = bb[3] 182 183 // Per-scanline scratch: at most n_verts crossings on a convex 184 // boundary, more on concave. Allocate n_verts*2 to be safe. 185 let max_xs: i64 = poly.n_verts * 2 186 let xs: *i64 = (sys_mmap(max_xs * 8)) as *i64 187 188 var scan: i64 = 0 189 if vertical == 0 { scan = bb_min_y } 190 if vertical == 1 { scan = bb_min_x } 191 let scan_max: i64 = bb_max_y * (1 - vertical) + bb_max_x * vertical 192 let scan_min: i64 = bb_min_y * (1 - vertical) + bb_min_x * vertical 193 194 while scan <= scan_max { 195 var n_xs: i64 = 0 196 if vertical == 0 { 197 n_xs = nx_infill_scanline_xs(poly, scan, xs, max_xs) 198 } 199 if vertical == 1 { 200 n_xs = nx_infill_scanline_ys(poly, scan, xs, max_xs) 201 } 202 // Sort the crossing coords ascending (in-place i64 sort). 203 if n_xs > 1 { nx_qsort_i64(xs, n_xs) } 204 205 // Pair consecutive crossings into in/out segment endpoints. 206 var k: i64 = 0 207 while k + 1 < n_xs { 208 let a: i64 = xs[k] 209 let b: i64 = xs[k + 1] 210 var rc: i64 = 0 211 if vertical == 0 { 212 rc = nx_slice_soup_emit(out, a, scan, b, scan) 213 } 214 if vertical == 1 { 215 rc = nx_slice_soup_emit(out, scan, a, scan, b) 216 } 217 if rc != 0 { return NX_INFILL_ERR_CAPACITY } 218 k = k + 2 219 } 220 scan = scan + spacing_q14 221 } 222 223 return NX_INFILL_OK 224}