nx_slice_contour.nx source
↩ module page · 266 lines · 9326 B
1// nx_slice_contour.nx -- assemble nx_slice_plane segment soup into
2// closed NxPolygon contours via endpoint-adjacency walk.
3//
4// Algorithm (per layer):
5// for each unvisited segment S:
6// start a polygon with S.A as first vertex, S.B as second
7// mark S visited
8// current_endpoint = S.B
9// loop:
10// find another unvisited segment T whose endpoint matches
11// current_endpoint
12// if T found:
13// add T's OTHER endpoint to polygon
14// mark T visited
15// current_endpoint = T's other endpoint
16// else:
17// contour is OPEN (dangling segment chain) -- emit as open
18// polygon with verdict set; slicer caller decides handling
19// if current_endpoint == S.A (start):
20// contour CLOSED -- emit as closed polygon
21// end for
22//
23// Complexity: O(n²) per layer. At slicer-typical 10K segments/layer
24// this is ~100M ops -- well within seconds for a 100-layer slice.
25// Per cardinal feedback-bits-up-exceed-never-match: O(n) hash-based
26// version queued as P2.2.opt for after this primitive's semantics
27// have been compile-validated. Correctness first, perf second --
28// per "bad prints = massive waste of time and resources" directive.
29//
30// Composes nx_slice_plane (segment soup input) + nx_polygon (closed
31// contour output). No new substrate primitives needed.
32//
33// Manifold expectation: a well-formed closed STL produces a soup
34// where every endpoint is shared by EXACTLY two segments. The
35// walk terminates by returning to the start vertex. Non-manifold
36// or open-mesh input produces dangling chains and gets flagged
37// via NX_SLICE_CONTOUR_ERR_OPEN.
38//
39// license_tier: ORIGINAL
40
41import "nx_syscalls.nx"
42import "nx_polygon.nx"
43import "nx_slice_plane.nx"
44
45// ===== verdicts ===================================================
46
47const NX_SLICE_CONTOUR_OK: i64 = 0
48const NX_SLICE_CONTOUR_ERR_OPEN: i64 = 1
49const NX_SLICE_CONTOUR_ERR_EMPTY: i64 = 2
50
51func nx_slice_contour_verdict_name(v: i64) -> *u8 {
52 if v == NX_SLICE_CONTOUR_OK { return "OK" }
53 if v == NX_SLICE_CONTOUR_ERR_OPEN { return "OPEN" }
54 if v == NX_SLICE_CONTOUR_ERR_EMPTY { return "EMPTY" }
55 return "UNKNOWN"
56}
57
58// ===== struct ======================================================
59
60struct NxSliceContours {
61 polys: *u8, // packed array of *NxPolygon (8 bytes each)
62 n_polys: i64,
63 capacity: i64,
64 n_open: i64, // count of open / dangling contours
65 verdict: i64,
66}
67
68const NX_SLICE_CONTOURS_BYTES: i64 = 40
69
70func nx_slice_contours_new(capacity: i64) -> *NxSliceContours {
71 let c: *NxSliceContours = (sys_mmap(NX_SLICE_CONTOURS_BYTES)) as *NxSliceContours
72 c.polys = sys_mmap(capacity * 8)
73 c.n_polys = 0
74 c.capacity = capacity
75 c.n_open = 0
76 c.verdict = NX_SLICE_CONTOUR_OK
77 return c
78}
79
80func nx_slice_contours_get(c: *NxSliceContours, i: i64) -> *NxPolygon {
81 let pp: *i64 = ((c.polys as i64) + i * 8) as *i64
82 return pp[0] as *NxPolygon
83}
84
85func nx_slice_contours_put(c: *NxSliceContours, i: i64, p: *NxPolygon) -> i64 {
86 let pp: *i64 = ((c.polys as i64) + i * 8) as *i64
87 pp[0] = p as i64
88 return 0
89}
90
91// ===== segment endpoint helpers ====================================
92
93func nx_slice_seg_x1(s: *NxSliceSoup, i: i64) -> i64 {
94 let p: *i64 = nx_slice_soup_seg_ptr(s, i)
95 return p[0]
96}
97func nx_slice_seg_y1(s: *NxSliceSoup, i: i64) -> i64 {
98 let p: *i64 = nx_slice_soup_seg_ptr(s, i)
99 return p[1]
100}
101func nx_slice_seg_x2(s: *NxSliceSoup, i: i64) -> i64 {
102 let p: *i64 = nx_slice_soup_seg_ptr(s, i)
103 return p[2]
104}
105func nx_slice_seg_y2(s: *NxSliceSoup, i: i64) -> i64 {
106 let p: *i64 = nx_slice_soup_seg_ptr(s, i)
107 return p[3]
108}
109
110// ===== find next segment ===========================================
111//
112// Linear scan for an unvisited segment with endpoint matching
113// (target_x, target_y). Returns (segment_idx, which_end) via
114// out parameters; -1 if none found.
115// which_end: 0 = matched endpoint A (so next vertex is B)
116// 1 = matched endpoint B (so next vertex is A)
117
118func nx_slice_find_neighbour(soup: *NxSliceSoup, visited: *u8,
119 target_x: i64, target_y: i64,
120 out_seg: *i64, out_end: *i64) -> i64 {
121 var i: i64 = 0
122 while i < soup.n_segments {
123 if visited[i] == 0 {
124 if nx_slice_seg_x1(soup, i) == target_x {
125 if nx_slice_seg_y1(soup, i) == target_y {
126 out_seg[0] = i
127 out_end[0] = 0
128 return 0
129 }
130 }
131 if nx_slice_seg_x2(soup, i) == target_x {
132 if nx_slice_seg_y2(soup, i) == target_y {
133 out_seg[0] = i
134 out_end[0] = 1
135 return 0
136 }
137 }
138 }
139 i = i + 1
140 }
141 out_seg[0] = -1
142 out_end[0] = -1
143 return -1
144}
145
146// ===== contour walk for one starting segment =======================
147//
148// Builds one polygon starting from segment `start_idx`. Walks
149// adjacency until either (a) we close the loop or (b) we hit a
150// dangling endpoint. Marks every visited segment. Returns the
151// new polygon and sets is_closed via out param.
152
153func nx_slice_walk_one(soup: *NxSliceSoup, visited: *u8,
154 start_idx: i64, max_verts: i64,
155 is_closed: *i64) -> *NxPolygon {
156 let p: *NxPolygon = nx_polygon_alloc(max_verts)
157 if (p as i64) == 0 {
158 is_closed[0] = 0
159 return p
160 }
161
162 let start_x: i64 = nx_slice_seg_x1(soup, start_idx)
163 let start_y: i64 = nx_slice_seg_y1(soup, start_idx)
164 nx_polygon_add_vert(p, start_x, start_y)
165 nx_polygon_add_vert(p, nx_slice_seg_x2(soup, start_idx),
166 nx_slice_seg_y2(soup, start_idx))
167 visited[start_idx] = 1
168
169 var cur_x: i64 = nx_slice_seg_x2(soup, start_idx)
170 var cur_y: i64 = nx_slice_seg_y2(soup, start_idx)
171 let out_seg: *i64 = (sys_mmap(8)) as *i64
172 let out_end: *i64 = (sys_mmap(8)) as *i64
173
174 var done: i64 = 0
175 while done == 0 {
176 // Closure check first
177 if cur_x == start_x {
178 if cur_y == start_y {
179 is_closed[0] = 1
180 // Drop the duplicate-start vertex we just added
181 // (polygon convention is implicit close).
182 p.n_verts = p.n_verts - 1
183 done = 1
184 }
185 }
186 if done == 0 {
187 let rc: i64 = nx_slice_find_neighbour(soup, visited,
188 cur_x, cur_y,
189 out_seg, out_end)
190 if rc != 0 {
191 // No neighbour: open / dangling.
192 is_closed[0] = 0
193 done = 1
194 }
195 if rc == 0 {
196 let ti: i64 = out_seg[0]
197 let we: i64 = out_end[0]
198 visited[ti] = 1
199 // Advance to the OTHER endpoint of segment ti
200 var next_x: i64 = 0
201 var next_y: i64 = 0
202 if we == 0 {
203 next_x = nx_slice_seg_x2(soup, ti)
204 next_y = nx_slice_seg_y2(soup, ti)
205 }
206 if we == 1 {
207 next_x = nx_slice_seg_x1(soup, ti)
208 next_y = nx_slice_seg_y1(soup, ti)
209 }
210 // Check if next vertex closes the loop -- handled
211 // at the top of the next iteration. Add it now.
212 if p.n_verts < p.capacity {
213 nx_polygon_add_vert(p, next_x, next_y)
214 }
215 cur_x = next_x
216 cur_y = next_y
217 }
218 }
219 }
220 return p
221}
222
223// ===== public entry =================================================
224//
225// Assembles every contour from the segment soup. Returns the
226// NxSliceContours collection with verdict set:
227// OK = every contour closed
228// OPEN = at least one open / dangling contour (n_open > 0)
229// EMPTY = soup had no segments
230//
231// Capacity for output: n_segments slots (each segment could in
232// principle be its own contour in pathological input).
233
234func nx_slice_contour_build(soup: *NxSliceSoup) -> *NxSliceContours {
235 let c: *NxSliceContours = nx_slice_contours_new(soup.n_segments + 1)
236 if soup.n_segments <= 0 {
237 c.verdict = NX_SLICE_CONTOUR_ERR_EMPTY
238 return c
239 }
240
241 let visited: *u8 = sys_mmap(soup.n_segments)
242 var i: i64 = 0
243 while i < soup.n_segments { visited[i] = 0; i = i + 1 }
244
245 let is_closed: *i64 = (sys_mmap(8)) as *i64
246 var s: i64 = 0
247 while s < soup.n_segments {
248 if visited[s] == 0 {
249 is_closed[0] = 0
250 let p: *NxPolygon = nx_slice_walk_one(soup, visited, s,
251 soup.n_segments + 1,
252 is_closed)
253 if (p as i64) != 0 {
254 if c.n_polys < c.capacity {
255 nx_slice_contours_put(c, c.n_polys, p)
256 c.n_polys = c.n_polys + 1
257 if is_closed[0] == 0 { c.n_open = c.n_open + 1 }
258 }
259 }
260 }
261 s = s + 1
262 }
263
264 if c.n_open > 0 { c.verdict = NX_SLICE_CONTOUR_ERR_OPEN }
265 return c
266}