nx_perlin.nx source
↩ module page · 292 lines · 11959 B
1// nx_perlin.nx -- seeded Perlin noise primitive.
2//
3// Foundational procgen primitive. Every higher-level generative
4// thing (terrain, clouds, marble, organic textures, agent trajectories,
5// node-graph composition like Houdini engine) composes noise as a
6// building block. This file ships the seed -> permutation table ->
7// gradient -> bilinear-blend chain in pure Q10 integer math, no f64.
8//
9// Pattern parity with Houdini's noise SOP: stateful (allocated once),
10// position-keyed (lookup at any 2D point), seamless (continuous across
11// integer-cell boundaries via gradient interpolation), deterministic
12// from seed (same seed -> same noise field forever).
13//
14// 1D + 2D + FBM 2D (fractional Brownian motion -- multi-octave sum).
15// 3D Perlin / simplex / worley queued for follow-up files.
16//
17// genealogy_id: perlin_1985_image_synthesizer + perlin_2002_improved +
18// mandelbrot_1982_fractal_geometry_nature
19// lineage_id: perlin_2d_q10_int
20//
21// nx_safety_envelope:
22// intended_use: "Perlin 2D noise (Q10 fixed-point) -- ground
23// truth for substrate procgen. Composes with
24// biome_classifier / world_event / kind-specific
25// generators per cardinal feedback-kind-
26// specific-generators-not-broad-noise."
27// sil_target: SIL1 (procgen quality; not safety-runtime)
28// asil_target: QM
29// dal_target: NONE
30// evidence: [Perlin_1985_canonical_paper,
31// Q10_fixed_point_deterministic,
32// bit_equal_reproducible_across_runs,
33// seed_deterministic_no_global_state]
34// hazard_register: [bug-tape-seed-collision-low-entropy-source,
35// bug-tape-Q10-saturation-at-extreme-coords]
36// residual_risk: "Q10 saturates at coord magnitude > 2^21;
37// substrate-acceptable for world coords in
38// the [-1M, 1M] range. Caller MUST tile
39// for larger worlds (queued: nx_perlin_tile)."
40// verdict: NOT_YET_EVALUATED
41
42import "nx_syscalls.nx"
43import "nx_tier.nx"
44const NX_MAGIC_48271: i64 = 48271
45const NX_MAGIC_2147483647: i64 = 2147483647
46
47const NX_PERLIN_Q: nx_int = 1024
48const NX_PERLIN_TABLE_SIZE: nx_int = 256
49const NX_PERLIN_TABLE_MASK: nx_int = 255
50// sqrt(2)/2 in Q10: ~ 0.7071 * 1024 = 724
51const NX_PERLIN_DIAG_Q10: nx_int = 724
52
53struct PerlinState {
54 perm: *i64, // 256 entries each in [0, 255]
55 seeded: nx_int, // 1 once initialized
56}
57
58// LCG used for permutation-table seeding. Park-Miller minimal
59// standard: a = 48271, m = 2^31 - 1. Deterministic + portable.
60func _perlin_lcg_step(state: nx_int) -> nx_int {
61 let a: nx_int = NX_MAGIC_48271
62 let m: nx_int = NX_MAGIC_2147483647
63 return (state * a) - ((state * a) / m) * m
64}
65
66// ===== Allocation + seeding ===========================================
67//
68// Build the 256-entry permutation table via Fisher-Yates shuffle
69// using the LCG seeded with `seed`. Identical seeds always produce
70// identical tables -> deterministic noise fields across runs and
71// machines.
72
73func nx_perlin_alloc(seed: nx_int) -> *PerlinState {
74 let perm: *i64 = (sys_mmap(NX_PERLIN_TABLE_SIZE * NX_SIZEOF_NX_INT)) as *i64
75 var i: nx_int = 0
76 while i < NX_PERLIN_TABLE_SIZE {
77 perm[i] = i
78 i = i + 1
79 }
80 // Fisher-Yates shuffle driven by the LCG.
81 var rng: nx_int = seed
82 if rng <= 0 { rng = 1 } // LCG state must be positive
83 var j: nx_int = NX_PERLIN_TABLE_SIZE - 1
84 while j > 0 {
85 rng = _perlin_lcg_step(rng)
86 let k: nx_int = rng - (rng / (j + 1)) * (j + 1) // rng % (j+1) without modulo op
87 let tmp: nx_int = perm[j]
88 perm[j] = perm[k]
89 perm[k] = tmp
90 j = j - 1
91 }
92 let raw: *u8 = sys_mmap(2 * NX_SIZEOF_NX_INT)
93 let s: *PerlinState = raw as *PerlinState
94 s.perm = perm
95 s.seeded = 1
96 return s
97}
98
99// ===== Hermite smoothstep =============================================
100//
101// ease(t) = 3*t^2 - 2*t^3, all in Q10. Standard for Perlin's smooth
102// inter-cell blending. Quintic (6t^5 - 15t^4 + 10t^3) gives C2
103// continuity but Hermite is enough for visual procgen.
104
105func _perlin_ease(t_q10: nx_int) -> nx_int {
106 let t2: nx_int = (t_q10 * t_q10) / NX_PERLIN_Q
107 let t3: nx_int = (t2 * t_q10) / NX_PERLIN_Q
108 return 3 * t2 - 2 * t3
109}
110
111// Lerp(a, b, t) in Q10: a + (b - a) * t.
112func _perlin_lerp(a: nx_int, b: nx_int, t_q10: nx_int) -> nx_int {
113 return a + ((b - a) * t_q10) / NX_PERLIN_Q
114}
115
116// ===== 1D noise =======================================================
117
118func _perlin_grad_1d(hash: nx_int, x_frac_q10: nx_int) -> nx_int {
119 // 1D: gradient is +1 or -1 depending on hash parity.
120 if (hash - (hash / 2) * 2) == 0 {
121 return x_frac_q10
122 }
123 return 0 - x_frac_q10
124}
125
126// 1D Perlin at fractional position x (in arbitrary i64 Q10 of cells).
127// Returns Q10 noise nominally in [-Q10, Q10].
128func nx_perlin_1d(s: *PerlinState, x_q10: nx_int) -> nx_int {
129 let xi: nx_int = x_q10 / NX_PERLIN_Q
130 let xf: nx_int = x_q10 - xi * NX_PERLIN_Q
131 let xi_masked: nx_int = xi - (xi / NX_PERLIN_TABLE_SIZE) * NX_PERLIN_TABLE_SIZE
132 var xi_norm: nx_int = xi_masked
133 if xi_norm < 0 { xi_norm = xi_norm + NX_PERLIN_TABLE_SIZE }
134 let h0: nx_int = s.perm[xi_norm]
135 let next_idx: nx_int = (xi_norm + 1) - ((xi_norm + 1) / NX_PERLIN_TABLE_SIZE) * NX_PERLIN_TABLE_SIZE
136 let h1: nx_int = s.perm[next_idx]
137 let g0: nx_int = _perlin_grad_1d(h0, xf)
138 let g1: nx_int = _perlin_grad_1d(h1, xf - NX_PERLIN_Q)
139 let u: nx_int = _perlin_ease(xf)
140 return _perlin_lerp(g0, g1, u)
141}
142
143// ===== 2D noise =======================================================
144//
145// 2D gradient vectors (8 directions, axis-aligned + diagonal):
146// 0: ( 1, 0)
147// 1: (-1, 0)
148// 2: ( 0, 1)
149// 3: ( 0, -1)
150// 4: ( s, s)
151// 5: (-s, s)
152// 6: ( s, -s)
153// 7: (-s, -s)
154// where s = sqrt(2)/2 ~ 724 in Q10. hash % 8 selects.
155
156func _perlin_grad_2d_x(hash: nx_int) -> nx_int {
157 let h: nx_int = hash - (hash / 8) * 8
158 if h == 0 { return NX_PERLIN_Q }
159 if h == 1 { return 0 - NX_PERLIN_Q }
160 if h == 2 { return 0 }
161 if h == 3 { return 0 }
162 if h == 4 { return NX_PERLIN_DIAG_Q10 }
163 if h == 5 { return 0 - NX_PERLIN_DIAG_Q10 }
164 if h == 6 { return NX_PERLIN_DIAG_Q10 }
165 return 0 - NX_PERLIN_DIAG_Q10
166}
167
168func _perlin_grad_2d_y(hash: nx_int) -> nx_int {
169 let h: nx_int = hash - (hash / 8) * 8
170 if h == 0 { return 0 }
171 if h == 1 { return 0 }
172 if h == 2 { return NX_PERLIN_Q }
173 if h == 3 { return 0 - NX_PERLIN_Q }
174 if h == 4 { return NX_PERLIN_DIAG_Q10 }
175 if h == 5 { return NX_PERLIN_DIAG_Q10 }
176 if h == 6 { return 0 - NX_PERLIN_DIAG_Q10 }
177 return 0 - NX_PERLIN_DIAG_Q10
178}
179
180// Dot-product of (grad_x, grad_y) with (dx, dy) -- all in Q10.
181// Result is Q20 / Q10 -> Q10.
182func _perlin_dot_2d(gx: nx_int, gy: nx_int, dx: nx_int, dy: nx_int) -> nx_int {
183 return (gx * dx + gy * dy) / NX_PERLIN_Q
184}
185
186// Permutation-table double-lookup for 2D coordinates.
187func _perlin_hash_2d(s: *PerlinState, xi: nx_int, yi: nx_int) -> nx_int {
188 var xn: nx_int = xi - (xi / NX_PERLIN_TABLE_SIZE) * NX_PERLIN_TABLE_SIZE
189 if xn < 0 { xn = xn + NX_PERLIN_TABLE_SIZE }
190 var yn: nx_int = yi - (yi / NX_PERLIN_TABLE_SIZE) * NX_PERLIN_TABLE_SIZE
191 if yn < 0 { yn = yn + NX_PERLIN_TABLE_SIZE }
192 let p0: nx_int = s.perm[xn]
193 let folded: nx_int = (p0 + yn) - ((p0 + yn) / NX_PERLIN_TABLE_SIZE) * NX_PERLIN_TABLE_SIZE
194 return s.perm[folded]
195}
196
197// 2D Perlin at fractional position (x, y). Returns Q10 noise nominally
198// in [-Q10, Q10].
199func nx_perlin_2d(s: *PerlinState, x_q10: nx_int, y_q10: nx_int) -> nx_int {
200 let xi: nx_int = x_q10 / NX_PERLIN_Q
201 let yi: nx_int = y_q10 / NX_PERLIN_Q
202 let xf: nx_int = x_q10 - xi * NX_PERLIN_Q
203 let yf: nx_int = y_q10 - yi * NX_PERLIN_Q
204
205 let h00: nx_int = _perlin_hash_2d(s, xi, yi )
206 let h10: nx_int = _perlin_hash_2d(s, xi + 1, yi )
207 let h01: nx_int = _perlin_hash_2d(s, xi, yi + 1)
208 let h11: nx_int = _perlin_hash_2d(s, xi + 1, yi + 1)
209
210 let n00: nx_int = _perlin_dot_2d(_perlin_grad_2d_x(h00), _perlin_grad_2d_y(h00),
211 xf, yf )
212 let n10: nx_int = _perlin_dot_2d(_perlin_grad_2d_x(h10), _perlin_grad_2d_y(h10),
213 xf - NX_PERLIN_Q, yf )
214 let n01: nx_int = _perlin_dot_2d(_perlin_grad_2d_x(h01), _perlin_grad_2d_y(h01),
215 xf, yf - NX_PERLIN_Q)
216 let n11: nx_int = _perlin_dot_2d(_perlin_grad_2d_x(h11), _perlin_grad_2d_y(h11),
217 xf - NX_PERLIN_Q, yf - NX_PERLIN_Q)
218
219 let u: nx_int = _perlin_ease(xf)
220 let v: nx_int = _perlin_ease(yf)
221
222 let nx0: nx_int = _perlin_lerp(n00, n10, u)
223 let nx1: nx_int = _perlin_lerp(n01, n11, u)
224 return _perlin_lerp(nx0, nx1, v)
225}
226
227// ===== Fractional Brownian motion (FBM) ===============================
228//
229// Sum N octaves: each octave doubles the frequency and multiplies the
230// amplitude by `persistence_q10`. Classic procgen "natural-looking
231// terrain" texture.
232//
233// persistence_q10 typically in [256, 768] -- 0.25-0.75. Lower =
234// smoother high-level shape; higher = rougher.
235
236func nx_perlin_fbm_2d(s: *PerlinState, x_q10: nx_int, y_q10: nx_int,
237 octaves: nx_int, persistence_q10: nx_int) -> nx_int {
238 var total: nx_int = 0
239 var freq: nx_int = NX_PERLIN_Q
240 var amp: nx_int = NX_PERLIN_Q
241 var max_amp: nx_int = 0
242 var i: nx_int = 0
243 while i < octaves {
244 let sx: nx_int = (x_q10 * freq) / NX_PERLIN_Q
245 let sy: nx_int = (y_q10 * freq) / NX_PERLIN_Q
246 let n: nx_int = nx_perlin_2d(s, sx, sy)
247 total = total + (n * amp) / NX_PERLIN_Q
248 max_amp = max_amp + amp
249 amp = (amp * persistence_q10) / NX_PERLIN_Q
250 freq = freq * 2
251 i = i + 1
252 }
253 if max_amp == 0 { return 0 }
254 return (total * NX_PERLIN_Q) / max_amp
255}
256
257// ===== Qualitative classification =====================================
258//
259// Per the cardinal "every primitive carries both quantitative AND
260// qualitative readings": the quantitative noise value is a Q10 number;
261// the qualitative reading is the sealed-enum intensity band the value
262// falls into. Downstream tooling consumes the band without re-deriving.
263//
264// Band convention (signed Q10 in [-Q10, Q10] mapped to 5 bands):
265// VOID |value| < 102 (~ |10%| -- near zero, noise floor)
266// QUIET 102 <= |value| < 307 (mild signal)
267// MODERATE 307 <= |value| < 614 (clear signal)
268// STRONG 614 <= |value| < 870 (high amplitude)
269// SATURATED 870 <= |value| (peak amplitude, often clipping)
270
271const NX_PERLIN_BAND_VOID: nx_int = 0
272const NX_PERLIN_BAND_QUIET: nx_int = 1
273const NX_PERLIN_BAND_MODERATE: nx_int = 2
274const NX_PERLIN_BAND_STRONG: nx_int = 3
275const NX_PERLIN_BAND_SATURATED: nx_int = 4
276const NX_PERLIN_N_BANDS: nx_int = 5
277
278func nx_perlin_classify(noise_q10: nx_int) -> nx_int {
279 var a: nx_int = noise_q10
280 if a < 0 { a = 0 - a }
281 if a < 102 { return NX_PERLIN_BAND_VOID }
282 if a < 307 { return NX_PERLIN_BAND_QUIET }
283 if a < 614 { return NX_PERLIN_BAND_MODERATE }
284 if a < 870 { return NX_PERLIN_BAND_STRONG }
285 return NX_PERLIN_BAND_SATURATED
286}
287
288func nx_perlin_band_is_valid(band: nx_int) -> nx_int {
289 if band < 0 { return 0 }
290 if band >= NX_PERLIN_N_BANDS { return 0 }
291 return 1
292}