nx_worley_noise.nx source
↩ module page · 268 lines · 12997 B
1// nx_worley_noise.nx -- Worley cellular noise (F1 distance) in Q10.
2//
3// Cross-cutting Substrate A primitive per
4// nxc2/docs/NISHI_GAME_ENGINE_ROADMAP.md.
5//
6// Worley 1996 "A Cellular Texture Basis Function" (SIGGRAPH '96).
7// Divide the plane into uniform cells; place one feature point per
8// cell at a hash-determined position; the noise value at any query
9// point is the distance to the nearest feature point (F1). Produces
10// natural-looking cobblestone, rock, dried-mud, water-cell, and lizard-
11// scale textures that Perlin FBM cannot.
12//
13// Algorithm:
14// 1. Cell index (cx, cy) = floor(x / Q), floor(y / Q).
15// 2. Local position within cell (fx, fy) = x - cx*Q, y - cy*Q.
16// 3. For each neighbor cell (cx+dx, cy+dy) with dx, dy in {-1, 0, 1}:
17// a. Hash (ncx, ncy, seed) to a feature-point offset in [0, Q).
18// b. Feature absolute (relative to current cell origin):
19// (dx*Q + ox, dy*Q + oy).
20// c. Squared distance from local query point to feature point.
21// 4. F1 = sqrt(min of those 9 squared distances).
22//
23// 3x3 neighborhood guarantees correctness because the feature point
24// closest to (fx, fy) cannot live more than 1 cell away in any axis
25// when feature points are confined to [0, Q) per cell.
26//
27// Determinism: hash is pure LCG over (cx, cy, seed). Same query +
28// seed -> byte-equal output everywhere.
29//
30// Fixed-point strategy: distances kept in Q20 (Q^2) until the final
31// integer-sqrt converts to Q10. Avoids the precision loss that would
32// hit a per-step Q10 divide.
33//
34// Loss audit: only information-discarding op is the integer sqrt
35// (truncates fractional bit; ~1% error worst case). All other ops
36// exact in i64.
37//
38// genealogy_id: worley_1996_cellular
39// lineage_id: nx_worley_noise_q10_f1
40//
41// nx_safety_envelope:
42// intended_use: "Worley (cellular / Voronoi) noise -- F1
43// distance field for procgen, water/stone
44// textures, organic feature placement"
45// sil_target: SIL1
46// asil_target: QM
47// dal_target: NONE
48// evidence: [Worley_1996_canonical_paper,
49// Q10_fixed_point_deterministic,
50// bit_equal_reproducible_across_runs]
51// hazard_register: [bug-tape-seed-collision,
52// bug-tape-cell-boundary-discontinuity]
53// residual_risk: "F1 only (nearest-point distance). F2/F3
54// for cellular subdivision queued."
55// verdict: NOT_YET_EVALUATED
56
57import "nx_syscalls.nx"
58import "nx_tier.nx"
59import "nx_vecmath.nx"
60const NX_MAGIC_1024: i64 = 1024
61const NX_MAGIC_16777216: i64 = 16777216
62const NX_MAGIC_1500: i64 = 1500
63const NX_MAGIC_12345: i64 = 12345
64const NX_MAGIC_1448: i64 = 1448
65
66// ===== Q10 constants ================================================
67const NX_WORLEY_Q: nx_int = 1024
68
69// Park-Miller LCG multiplier (classic 32-bit minimal-standard).
70// Modulus M = 2^31 - 1 = 0x7FFFFFFF (Mersenne prime).
71const NX_WORLEY_LCG_A: nx_int = 48271
72const NX_WORLEY_LCG_M: nx_int = 2147483647
73
74// Cell-coordinate hash mixing constants (Knuth's multiplicative-hash
75// values for 32-bit and a different prime). Spreads (cx, cy) so
76// adjacent cells get well-separated feature offsets.
77const NX_WORLEY_HASH_CX: nx_int = 2654435761
78const NX_WORLEY_HASH_CY: nx_int = 1597334677
79
80// ===== Sealed-enum verdict bands ====================================
81// Output range is [0, ~1448]: 0 = exactly at a feature point; ~1448 ~
82// sqrt(2) * Q is the worst-case distance from a query-cell corner to
83// an opposite-cell-corner feature point.
84const NX_WORLEY_BAND_AT_FEATURE: nx_int = 0 // F1 < 64 (~0.06)
85const NX_WORLEY_BAND_NEAR: nx_int = 1 // 64..255
86const NX_WORLEY_BAND_MID: nx_int = 2 // 256..639
87const NX_WORLEY_BAND_FAR: nx_int = 3 // 640..1023
88const NX_WORLEY_BAND_CORNER: nx_int = 4 // >= 1024 (cell-corner range)
89
90const NX_WORLEY_THRESH_AT: nx_int = 64
91const NX_WORLEY_THRESH_NEAR: nx_int = 256
92const NX_WORLEY_THRESH_MID: nx_int = 640
93const NX_WORLEY_THRESH_FAR: nx_int = 1024
94
95// ===== Validity predicate ==========================================
96func nx_worley_noise_band_is_valid(b: nx_int) -> nx_int {
97 if b == NX_WORLEY_BAND_AT_FEATURE { return 1 }
98 if b == NX_WORLEY_BAND_NEAR { return 1 }
99 if b == NX_WORLEY_BAND_MID { return 1 }
100 if b == NX_WORLEY_BAND_FAR { return 1 }
101 if b == NX_WORLEY_BAND_CORNER { return 1 }
102 return 0
103}
104
105// ===== Sealed-enum classifier ======================================
106func nx_worley_noise_classify(value_q10: nx_int) -> nx_int {
107 if value_q10 < NX_WORLEY_THRESH_AT { return NX_WORLEY_BAND_AT_FEATURE }
108 if value_q10 < NX_WORLEY_THRESH_NEAR { return NX_WORLEY_BAND_NEAR }
109 if value_q10 < NX_WORLEY_THRESH_MID { return NX_WORLEY_BAND_MID }
110 if value_q10 < NX_WORLEY_THRESH_FAR { return NX_WORLEY_BAND_FAR }
111 return NX_WORLEY_BAND_CORNER
112}
113
114// ===== Integer square root =========================================
115// RETIRED ONTO THE SHARED OWNER 2026-08-24. This was a digit-by-digit binary floor-sqrt, self-described as a
116// duplicate of nx_henyey_greenstein's copy "queued for consolidation into nx_isqrt.nx" -- the consolidation
117// landed in nx_vecmath (vm_isqrt, Newton, gate-proven exact floor over 20,000 inputs; same value for every
118// n >= 0 by definition of floor). This organ's own self-test is the before/after identity control.
119func _isqrt(n: nx_int) -> nx_int { return vm_isqrt(n) }
120
121// ===== Cell-coordinate hash ========================================
122// Mixes (cx, cy, seed) into a pseudorandom 31-bit value via two
123// rounds of Park-Miller LCG seeded by cell coords spread through
124// Knuth multiplicative constants. Pure function; same (cx, cy, seed)
125// always returns the same hash.
126func _hash_cell(cx: nx_int, cy: nx_int, seed: nx_int) -> nx_int {
127 var h: nx_int = seed
128 // Mix cx.
129 let mix_x: nx_int = cx * NX_WORLEY_HASH_CX
130 h = (h * NX_WORLEY_LCG_A + mix_x) % NX_WORLEY_LCG_M
131 if h < 0 { h = h + NX_WORLEY_LCG_M }
132 // Mix cy.
133 let mix_y: nx_int = cy * NX_WORLEY_HASH_CY
134 h = (h * NX_WORLEY_LCG_A + mix_y) % NX_WORLEY_LCG_M
135 if h < 0 { h = h + NX_WORLEY_LCG_M }
136 return h
137}
138
139// Extract feature-offset coordinates within a cell (0..Q-1) from a
140// 31-bit hash value. Low 10 bits -> x offset; next 10 bits -> y.
141func _hash_to_x_offset(h: nx_int) -> nx_int {
142 return h & 1023
143}
144
145func _hash_to_y_offset(h: nx_int) -> nx_int {
146 return (h / NX_MAGIC_1024) & 1023
147}
148
149// Floor-division for negative numerators. Builtin / truncates toward
150// zero; for cell-index computation we need true floor.
151func _floor_div_q(n: nx_int) -> nx_int {
152 if n >= 0 { return n / NX_WORLEY_Q }
153 let q: nx_int = (0 - (0 - n + NX_WORLEY_Q - 1)) / NX_WORLEY_Q
154 return q
155}
156
157// ===== Worley F1 noise ==============================================
158// x_q10, y_q10: query coordinates in Q10.
159// seed: deterministic seed (any i64).
160// returns: F1 distance in Q10, range [0, ~1448].
161func nx_worley_noise(x_q10: nx_int, y_q10: nx_int, seed: nx_int) -> nx_int {
162 let cx: nx_int = _floor_div_q(x_q10)
163 let cy: nx_int = _floor_div_q(y_q10)
164 let fx: nx_int = x_q10 - cx * NX_WORLEY_Q
165 let fy: nx_int = y_q10 - cy * NX_WORLEY_Q
166
167 // Initialise min_sq to a value larger than any possible
168 // 3x3-neighborhood feature distance squared. Max possible:
169 // ((2*Q)^2 + (2*Q)^2) = 8*Q^2 = 8 * 1048576 = 8388608.
170 var min_sq: nx_int = NX_MAGIC_16777216 // 16 * Q^2; comfortably above max
171
172 var dy: nx_int = 0 - 1
173 while dy <= 1 {
174 var dx: nx_int = 0 - 1
175 while dx <= 1 {
176 let ncx: nx_int = cx + dx
177 let ncy: nx_int = cy + dy
178 let h: nx_int = _hash_cell(ncx, ncy, seed)
179 let ox: nx_int = _hash_to_x_offset(h)
180 let oy: nx_int = _hash_to_y_offset(h)
181 // Feature absolute relative to current cell origin:
182 // px = dx*Q + ox, py = dy*Q + oy
183 // Distance from (fx, fy):
184 let pdx: nx_int = dx * NX_WORLEY_Q + ox - fx
185 let pdy: nx_int = dy * NX_WORLEY_Q + oy - fy
186 let sq: nx_int = pdx * pdx + pdy * pdy
187 if sq < min_sq { min_sq = sq }
188 dx = dx + 1
189 }
190 dy = dy + 1
191 }
192
193 // sqrt(Q^2-scaled value) gives Q-scale result, exactly what we
194 // want. e.g. sqrt(Q^2) = Q.
195 return _isqrt(min_sq)
196}
197
198// ===== Self-test ====================================================
199func main() -> i64 {
200 // T1: Determinism -- same (x, y, seed) -> same output.
201 let a: nx_int = nx_worley_noise(512, 512, 42)
202 let b: nx_int = nx_worley_noise(512, 512, 42)
203 if a != b { return __syscall(93, 1, 0, 0, 0, 0, 0) }
204
205 // T2: Different seeds -> generally different output (probabilistic
206 // but at this many bits the false-positive is astronomical).
207 let c: nx_int = nx_worley_noise(512, 512, 43)
208 if a == c { return __syscall(93, 2, 0, 0, 0, 0, 0) }
209
210 // T3: Output in plausible range [0, ~1500].
211 if a < 0 { return __syscall(93, 3, 0, 0, 0, 0, 0) }
212 if a > NX_MAGIC_1500 { return __syscall(93, 4, 0, 0, 0, 0, 0) }
213
214 // T4: Cell-origin query (fx=0, fy=0) is bounded by the feature
215 // distance from origin within or near that cell. Should land in
216 // AT_FEATURE / NEAR / MID bands (never CORNER).
217 let v_origin: nx_int = nx_worley_noise(0, 0, NX_MAGIC_12345)
218 if v_origin >= NX_MAGIC_1024 { return __syscall(93, 5, 0, 0, 0, 0, 0) }
219
220 // T5: Querying at the exact feature point of cell (0, 0) should
221 // return very small distance. Compute the feature point ourselves
222 // via the hash, then query there.
223 let h_origin: nx_int = _hash_cell(0, 0, NX_MAGIC_12345)
224 let fx: nx_int = _hash_to_x_offset(h_origin)
225 let fy: nx_int = _hash_to_y_offset(h_origin)
226 let v_at_feature: nx_int = nx_worley_noise(fx, fy, NX_MAGIC_12345)
227 // Expect v_at_feature == 0 because (fx, fy) IS the feature point.
228 if v_at_feature != 0 { return __syscall(93, 6, 0, 0, 0, 0, 0) }
229
230 // T6: Querying far from any feature in a regular grid: not easy
231 // to construct without knowing the hash, but at LEAST query at a
232 // cell corner (fx=Q-1, fy=Q-1) with a seed whose feature lands
233 // near the opposite corner. Sanity: output should be larger than
234 // T5's near-zero value.
235 let v_corner: nx_int = nx_worley_noise(1023, 1023, NX_MAGIC_12345)
236 if v_corner <= v_at_feature { return __syscall(93, 7, 0, 0, 0, 0, 0) }
237
238 // T7: Negative coordinates (floor-division correctness). Output
239 // should be a valid bounded distance value.
240 let v_neg: nx_int = nx_worley_noise(0 - 512, 0 - 512, 42)
241 if v_neg < 0 { return __syscall(93, 8, 0, 0, 0, 0, 0) }
242 if v_neg > NX_MAGIC_1500 { return __syscall(93, 9, 0, 0, 0, 0, 0) }
243
244 // T8: Classifier band boundaries.
245 if nx_worley_noise_classify(0) != NX_WORLEY_BAND_AT_FEATURE { return __syscall(93, 20, 0, 0, 0, 0, 0) }
246 if nx_worley_noise_classify(63) != NX_WORLEY_BAND_AT_FEATURE { return __syscall(93, 21, 0, 0, 0, 0, 0) }
247 if nx_worley_noise_classify(64) != NX_WORLEY_BAND_NEAR { return __syscall(93, 22, 0, 0, 0, 0, 0) }
248 if nx_worley_noise_classify(255) != NX_WORLEY_BAND_NEAR { return __syscall(93, 23, 0, 0, 0, 0, 0) }
249 if nx_worley_noise_classify(256) != NX_WORLEY_BAND_MID { return __syscall(93, 24, 0, 0, 0, 0, 0) }
250 if nx_worley_noise_classify(639) != NX_WORLEY_BAND_MID { return __syscall(93, 25, 0, 0, 0, 0, 0) }
251 if nx_worley_noise_classify(640) != NX_WORLEY_BAND_FAR { return __syscall(93, 26, 0, 0, 0, 0, 0) }
252 if nx_worley_noise_classify(1023) != NX_WORLEY_BAND_FAR { return __syscall(93, 27, 0, 0, 0, 0, 0) }
253 if nx_worley_noise_classify(NX_MAGIC_1024) != NX_WORLEY_BAND_CORNER { return __syscall(93, 28, 0, 0, 0, 0, 0) }
254 if nx_worley_noise_classify(NX_MAGIC_1448) != NX_WORLEY_BAND_CORNER { return __syscall(93, 29, 0, 0, 0, 0, 0) }
255
256 // T9: Validity predicate accepts every enum value and rejects
257 // out-of-band integers.
258 if nx_worley_noise_band_is_valid(NX_WORLEY_BAND_AT_FEATURE) != 1 { return __syscall(93, 30, 0, 0, 0, 0, 0) }
259 if nx_worley_noise_band_is_valid(NX_WORLEY_BAND_NEAR) != 1 { return __syscall(93, 31, 0, 0, 0, 0, 0) }
260 if nx_worley_noise_band_is_valid(NX_WORLEY_BAND_MID) != 1 { return __syscall(93, 32, 0, 0, 0, 0, 0) }
261 if nx_worley_noise_band_is_valid(NX_WORLEY_BAND_FAR) != 1 { return __syscall(93, 33, 0, 0, 0, 0, 0) }
262 if nx_worley_noise_band_is_valid(NX_WORLEY_BAND_CORNER) != 1 { return __syscall(93, 34, 0, 0, 0, 0, 0) }
263 if nx_worley_noise_band_is_valid(0 - 1) != 0 { return __syscall(93, 35, 0, 0, 0, 0, 0) }
264 if nx_worley_noise_band_is_valid(5) != 0 { return __syscall(93, 36, 0, 0, 0, 0, 0) }
265 if nx_worley_noise_band_is_valid(99) != 0 { return __syscall(93, 37, 0, 0, 0, 0, 0) }
266
267 return 0
268}