Commit | Line | Data |
---|---|---|
7f918cf1 CE |
1 | (* |
2 | * Translated by Stephen Weeks (sweeks@sweeks.com) 2000-10-11 from the | |
3 | * PLClub OCaml winning entry to the 2000 ICFP programming contest. | |
4 | *) | |
5 | ||
6 | (* raytrace.sml *) | |
7 | signature CAML = | |
8 | sig | |
9 | type float = real | |
10 | type int = int | |
11 | end | |
12 | ||
13 | structure Caml = | |
14 | struct | |
15 | ||
16 | type int = int | |
17 | type float = real | |
18 | ||
19 | val op div = Int.div | |
20 | ||
21 | exception Not_found | |
22 | exception Failure of string | |
23 | ||
24 | fun failwith s = raise(Failure s) | |
25 | ||
26 | structure Char = | |
27 | struct | |
28 | open Char | |
29 | val code = ord | |
30 | val chr = chr | |
31 | val unsafe_chr = chr | |
32 | val lowercase = toLower | |
33 | val uppercase = toUpper | |
34 | end | |
35 | ||
36 | local | |
37 | open TextIO | |
38 | in | |
39 | type out_channel = outstream | |
40 | val open_out = openOut | |
41 | val open_out_bin = open_out | |
42 | fun output_string (out, s) = output(out, s) | |
43 | val close_out = closeOut | |
44 | end | |
45 | ||
46 | type float = real | |
47 | ||
48 | structure Array = | |
49 | struct | |
50 | local open Array | |
51 | in | |
52 | val array = array | |
53 | val copy = copy | |
54 | val of_list = fromList | |
55 | val length = length | |
56 | val sub = sub | |
57 | val update = update | |
58 | val unsafe_get = Array.sub | |
59 | val unsafe_set = Array.update | |
60 | val make = array | |
61 | fun map f a = Array.tabulate(length a, fn i => f(Array.sub(a, i))) | |
62 | val init = tabulate | |
63 | end | |
64 | end | |
65 | ||
66 | fun for(a: int, b, f) = | |
67 | let | |
68 | fun loop a = | |
69 | if a > b | |
70 | then () | |
71 | else (f a; loop(a + 1)) | |
72 | in loop a | |
73 | end | |
74 | ||
75 | fun forDown(b: int, a, f) = | |
76 | let | |
77 | fun loop b = | |
78 | if b < a | |
79 | then () | |
80 | else (f b; loop(b - 1)) | |
81 | in loop b | |
82 | end | |
83 | ||
84 | local | |
85 | open Real | |
86 | open Math | |
87 | in | |
88 | val abs_float = abs | |
89 | val acos = acos | |
90 | val asin = asin | |
91 | val cos = cos | |
92 | val float = fromInt | |
93 | val float_of_int = float | |
94 | val sin = sin | |
95 | val sqrt = sqrt | |
96 | val tan = tan | |
97 | val truncate = trunc | |
98 | val ** = Math.pow | |
99 | infix 8 ** | |
100 | end | |
101 | ||
102 | (* A hack for hash tables with string domain where performance doesn't matter. *) | |
103 | structure Hashtbl: | |
104 | sig | |
105 | type ('a, 'b) t | |
106 | ||
107 | val add: ('a, 'b) t -> string -> 'b -> unit | |
108 | val create: int -> ('a, 'b) t | |
109 | val find: ('a, 'b) t -> string -> 'b | |
110 | end = | |
111 | struct | |
112 | datatype ('a, 'b) t = T of (string * 'b) list ref | |
113 | ||
114 | fun create _ = T (ref []) | |
115 | ||
116 | fun add (T t) k d = t := (k, d) :: !t | |
117 | ||
118 | fun find (T (ref t)) k = | |
119 | case List.find (fn (k', _) => k = k') t of | |
120 | NONE => raise Not_found | |
121 | | SOME(_, d) => d | |
122 | end | |
123 | ||
124 | structure List = | |
125 | struct | |
126 | local open List | |
127 | in | |
128 | val iter = app | |
129 | val map = map | |
130 | val filter = filter | |
131 | val nth = nth | |
132 | val rev = rev | |
133 | end | |
134 | end | |
135 | ||
136 | fun exit i = Posix.Process.exit(Word8.fromInt i) | |
137 | ||
138 | end | |
139 | structure Math = | |
140 | struct | |
141 | ||
142 | open Caml | |
143 | ||
144 | val epsilon = 1E~5 | |
145 | ||
146 | val dtr = acos (~1.0) / 180.0 | |
147 | val rtd = 180.0 / acos (~1.0) | |
148 | ||
149 | fun dcos t = cos (t * dtr) | |
150 | fun dsin t = sin (t * dtr) | |
151 | fun dtan t = tan (t * dtr) | |
152 | fun dacos x = rtd * acos x | |
153 | ||
154 | val infinity = Real.posInf | |
155 | val minus_infinity = Real.negInf | |
156 | ||
157 | fun max_float (x, y : float) = if x >= y then x else y | |
158 | ||
159 | end | |
160 | signature MATRIX = | |
161 | sig | |
162 | include CAML | |
163 | ||
164 | (**** Matrix arithmetic ****) | |
165 | ||
166 | type t = float array (* 4-dimension matrix *) | |
167 | type v = float * float * float * float (* 4-dimension vector *) | |
168 | ||
169 | (* Basic matrices *) | |
170 | val identity : t | |
171 | val translate : (*x:*)float * (*y:*)float * (*z:*)float -> t | |
172 | val scale : (*x:*)float * (*y:*)float * (*z:*)float -> t | |
173 | val uscale : float -> t | |
174 | val unscale : (*x:*)float * (*y:*)float * (*z:*)float -> t | |
175 | val unuscale : float -> t | |
176 | val rotatex : float -> t | |
177 | val rotatey : float -> t | |
178 | val rotatez : float -> t | |
179 | ||
180 | (* Operations on matrices *) | |
181 | val mul : t * t -> t | |
182 | val vmul : t * v -> v | |
183 | val transpose : t -> t | |
184 | ||
185 | val add_scaled : v * float * v -> v | |
186 | val add : v * v -> v | |
187 | val sub : v * v -> v | |
188 | val prod : v * v -> float | |
189 | val square : v -> float | |
190 | val normalize : v -> v | |
191 | val neg : v -> v | |
192 | end | |
193 | structure Matrix: MATRIX = | |
194 | struct | |
195 | ||
196 | open Caml | |
197 | open Math | |
198 | ||
199 | type t = float array | |
200 | type v = float * float * float * float | |
201 | ||
202 | (**** Basic matrices ****) | |
203 | ||
204 | val identity = | |
205 | Array.of_list[1.0, 0.0, 0.0, 0.0, | |
206 | 0.0, 1.0, 0.0, 0.0, | |
207 | 0.0, 0.0, 1.0, 0.0, | |
208 | 0.0, 0.0, 0.0, 1.0] | |
209 | ||
210 | fun translate(x, y, z) = | |
211 | Array.of_list[1.0, 0.0, 0.0, ~ x, | |
212 | 0.0, 1.0, 0.0, ~ y, | |
213 | 0.0, 0.0, 1.0, ~ z, | |
214 | 0.0, 0.0, 0.0, 1.0] | |
215 | ||
216 | fun unscale(x, y, z) = | |
217 | Array.of_list[ x, 0.0, 0.0, 0.0, | |
218 | 0.0, y, 0.0, 0.0, | |
219 | 0.0, 0.0, z, 0.0, | |
220 | 0.0, 0.0, 0.0, 1.0] | |
221 | ||
222 | fun scale(x, y, z) = unscale (1.0 / x, 1.0 / y, 1.0 / z) | |
223 | ||
224 | fun unuscale s = unscale (s, s, s) | |
225 | ||
226 | fun uscale s = scale (s, s, s) | |
227 | ||
228 | fun rotatex t = | |
229 | let | |
230 | val co = dcos t | |
231 | val si = dsin t | |
232 | in | |
233 | Array.of_list[ 1.0, 0.0, 0.0, 0.0, | |
234 | 0.0, co, si, 0.0, | |
235 | 0.0, ~ si, co, 0.0, | |
236 | 0.0, 0.0, 0.0, 1.0 ] | |
237 | end | |
238 | ||
239 | fun rotatey t = | |
240 | let | |
241 | val co = dcos t | |
242 | val si = dsin t | |
243 | in | |
244 | Array.of_list[ co, 0.0, ~ si, 0.0, | |
245 | 0.0, 1.0, 0.0, 0.0, | |
246 | si, 0.0, co, 0.0, | |
247 | 0.0, 0.0, 0.0, 1.0 ] | |
248 | end | |
249 | ||
250 | fun rotatez t = | |
251 | let | |
252 | val co = dcos t | |
253 | val si = dsin t | |
254 | in | |
255 | Array.of_list[ co, si, 0.0, 0.0, | |
256 | ~ si, co, 0.0, 0.0, | |
257 | 0.0, 0.0, 1.0, 0.0, | |
258 | 0.0, 0.0, 0.0, 1.0 ] | |
259 | end | |
260 | ||
261 | (*** Operations on matrices ***) | |
262 | ||
263 | fun get (m : t, i, j) = Array.unsafe_get (m, i * 4 + j) | |
264 | fun set (m : t, i, j, v) = Array.unsafe_set (m, i * 4 + j, v) | |
265 | ||
266 | fun mul (m, m') = | |
267 | let | |
268 | val m'' = Array.make (16, 0.0) | |
269 | in | |
270 | for(0, 3, fn i => | |
271 | for(0, 3, fn j => let | |
272 | fun lp (4, s) = s | |
273 | | lp (k, s) = lp (k+1, s + get(m, i, k) * get(m', k, j)) | |
274 | in | |
275 | set(m'', i, j, lp(0, 0.0)) | |
276 | end)) | |
277 | ; m'' | |
278 | end | |
279 | ||
280 | fun transpose m = | |
281 | let val m' = Array.make (16, 0.0) | |
282 | in for(0, 3, fn i => | |
283 | for(0, 3, fn j => | |
284 | set (m', i, j, get (m, j, i)))) | |
285 | ; m' | |
286 | end | |
287 | ||
288 | fun vmul (m, (x, y, z, t)) = | |
289 | (x * get(m, 0, 0) + y * get(m, 0, 1) + z * get(m, 0, 2) + t * get(m, 0, 3), | |
290 | x * get(m, 1, 0) + y * get(m, 1, 1) + z * get(m, 1, 2) + t * get(m, 1, 3), | |
291 | x * get(m, 2, 0) + y * get(m, 2, 1) + z * get(m, 2, 2) + t * get(m, 2, 3), | |
292 | x * get(m, 3, 0) + y * get(m, 3, 1) + z * get(m, 3, 2) + t * get(m, 3, 3)) | |
293 | ||
294 | fun add_scaled (x: v, t, v: v) : v = | |
295 | ( #1 x + t * #1 v, | |
296 | #2 x + t * #2 v, | |
297 | #3 x + t * #3 v, | |
298 | #4 x + t * #4 v ) | |
299 | ||
300 | fun add (x: v, y: v) : v = | |
301 | ( #1 x + #1 y, | |
302 | #2 x + #2 y, | |
303 | #3 x + #3 y, | |
304 | #4 x + #4 y ) | |
305 | ||
306 | fun sub (x: v, y: v) : v = | |
307 | (#1 x - #1 y, | |
308 | #2 x - #2 y, | |
309 | #3 x - #3 y, | |
310 | #4 x - #4 y) | |
311 | ||
312 | fun prod (x: v, y: v) : real = | |
313 | #1 x * #1 y + #2 x * #2 y + #3 x * #3 y + #4 x * #4 y | |
314 | ||
315 | fun square (vx, vy, vz, vt) : real = | |
316 | vx * vx + vy * vy + vz * vz + vt * vt | |
317 | ||
318 | fun normalize (x: v): v = | |
319 | let | |
320 | val nx = sqrt (prod (x, x)) | |
321 | in | |
322 | (#1 x / nx, | |
323 | #2 x / nx, | |
324 | #3 x / nx, | |
325 | #4 x / nx) | |
326 | end | |
327 | ||
328 | fun neg (x: v) : v = | |
329 | (~(#1 x), | |
330 | ~(#2 x), | |
331 | ~(#3 x), | |
332 | ~(#4 x)) | |
333 | ||
334 | end | |
335 | signature LEX_TOKEN_STRUCTS = | |
336 | sig | |
337 | end | |
338 | ||
339 | signature LEX_TOKEN = | |
340 | sig | |
341 | include LEX_TOKEN_STRUCTS | |
342 | ||
343 | datatype t = | |
344 | Binder of string | |
345 | | Bool of bool | |
346 | | Eof | |
347 | | Identifier of string | |
348 | | Int of int | |
349 | | Lbrace | |
350 | | Lbracket | |
351 | | Rbrace | |
352 | | Rbracket | |
353 | | Real of real | |
354 | | String of string | |
355 | end | |
356 | functor LexToken(S: LEX_TOKEN_STRUCTS): LEX_TOKEN = | |
357 | struct | |
358 | ||
359 | open S | |
360 | ||
361 | datatype t = | |
362 | Binder of string | |
363 | | Bool of bool | |
364 | | Eof | |
365 | | Identifier of string | |
366 | | Int of int | |
367 | | Lbrace | |
368 | | Lbracket | |
369 | | Rbrace | |
370 | | Rbracket | |
371 | | Real of real | |
372 | | String of string | |
373 | ||
374 | end | |
375 | type int = Int.int | |
376 | functor Lex(structure Token: LEX_TOKEN)= | |
377 | struct | |
378 | structure UserDeclarations = | |
379 | struct | |
380 | val chars: char list ref = ref [] | |
381 | ||
382 | type lexarg = unit | |
383 | ||
384 | type lexresult = Token.t | |
385 | ||
386 | val eof: lexarg -> lexresult = | |
387 | fn () => Token.Eof | |
388 | ||
389 | fun fail s = raise Fail s | |
390 | ||
391 | end (* end of user routines *) | |
392 | exception LexError (* raised if illegal leaf action tried *) | |
393 | structure Internal = | |
394 | struct | |
395 | ||
396 | datatype yyfinstate = N of int | |
397 | type statedata = {fin : yyfinstate list, trans: string} | |
398 | (* transition & final state table *) | |
399 | val tab = let | |
400 | val s = [ | |
401 | (0, | |
402 | "\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
403 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
404 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
405 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
406 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
407 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
408 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
409 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
410 | \\000" | |
411 | ), | |
412 | (1, | |
413 | "\000\000\000\000\000\000\000\000\000\026\026\026\000\026\000\000\ | |
414 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
415 | \\026\000\025\000\000\024\000\000\000\000\000\000\000\023\000\021\ | |
416 | \\012\012\012\012\012\012\012\012\012\012\000\000\000\000\000\000\ | |
417 | \\000\009\009\009\009\009\009\009\009\009\009\009\009\009\009\009\ | |
418 | \\009\009\009\009\009\009\009\009\009\009\009\011\000\010\000\000\ | |
419 | \\000\009\009\009\009\009\009\009\009\009\009\009\009\009\009\009\ | |
420 | \\009\009\009\009\009\009\009\009\009\009\009\008\000\007\000\000\ | |
421 | \\000" | |
422 | ), | |
423 | (3, | |
424 | "\000\000\000\000\000\000\000\000\000\027\029\029\000\028\000\000\ | |
425 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
426 | \\027\027\027\027\027\027\027\027\027\027\027\027\027\027\027\027\ | |
427 | \\027\027\027\027\027\027\027\027\027\027\027\027\027\027\027\027\ | |
428 | \\027\027\027\027\027\027\027\027\027\027\027\027\027\027\027\027\ | |
429 | \\027\027\027\027\027\027\027\027\027\027\027\027\027\027\027\027\ | |
430 | \\027\027\027\027\027\027\027\027\027\027\027\027\027\027\027\027\ | |
431 | \\027\027\027\027\027\027\027\027\027\027\027\027\027\027\027\000\ | |
432 | \\000" | |
433 | ), | |
434 | (5, | |
435 | "\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
436 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
437 | \\030\030\031\030\030\030\030\030\030\030\030\030\030\030\030\030\ | |
438 | \\030\030\030\030\030\030\030\030\030\030\030\030\030\030\030\030\ | |
439 | \\030\030\030\030\030\030\030\030\030\030\030\030\030\030\030\030\ | |
440 | \\030\030\030\030\030\030\030\030\030\030\030\030\030\030\030\030\ | |
441 | \\030\030\030\030\030\030\030\030\030\030\030\030\030\030\030\030\ | |
442 | \\030\030\030\030\030\030\030\030\030\030\030\030\030\030\030\000\ | |
443 | \\000" | |
444 | ), | |
445 | (9, | |
446 | "\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
447 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
448 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\009\000\000\ | |
449 | \\009\009\009\009\009\009\009\009\009\009\000\000\000\000\000\000\ | |
450 | \\000\009\009\009\009\009\009\009\009\009\009\009\009\009\009\009\ | |
451 | \\009\009\009\009\009\009\009\009\009\009\009\000\000\000\000\009\ | |
452 | \\000\009\009\009\009\009\009\009\009\009\009\009\009\009\009\009\ | |
453 | \\009\009\009\009\009\009\009\009\009\009\009\000\000\000\000\000\ | |
454 | \\000" | |
455 | ), | |
456 | (12, | |
457 | "\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
458 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
459 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\016\000\ | |
460 | \\012\012\012\012\012\012\012\012\012\012\000\000\000\000\000\000\ | |
461 | \\000\000\000\000\000\013\000\000\000\000\000\000\000\000\000\000\ | |
462 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
463 | \\000\000\000\000\000\013\000\000\000\000\000\000\000\000\000\000\ | |
464 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
465 | \\000" | |
466 | ), | |
467 | (13, | |
468 | "\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
469 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
470 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\015\000\000\ | |
471 | \\014\014\014\014\014\014\014\014\014\014\000\000\000\000\000\000\ | |
472 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
473 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
474 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
475 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
476 | \\000" | |
477 | ), | |
478 | (14, | |
479 | "\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
480 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
481 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
482 | \\014\014\014\014\014\014\014\014\014\014\000\000\000\000\000\000\ | |
483 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
484 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
485 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
486 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
487 | \\000" | |
488 | ), | |
489 | (16, | |
490 | "\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
491 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
492 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
493 | \\017\017\017\017\017\017\017\017\017\017\000\000\000\000\000\000\ | |
494 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
495 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
496 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
497 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
498 | \\000" | |
499 | ), | |
500 | (17, | |
501 | "\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
502 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
503 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
504 | \\017\017\017\017\017\017\017\017\017\017\000\000\000\000\000\000\ | |
505 | \\000\000\000\000\000\018\000\000\000\000\000\000\000\000\000\000\ | |
506 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
507 | \\000\000\000\000\000\018\000\000\000\000\000\000\000\000\000\000\ | |
508 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
509 | \\000" | |
510 | ), | |
511 | (18, | |
512 | "\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
513 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
514 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\020\000\000\ | |
515 | \\019\019\019\019\019\019\019\019\019\019\000\000\000\000\000\000\ | |
516 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
517 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
518 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
519 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
520 | \\000" | |
521 | ), | |
522 | (19, | |
523 | "\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
524 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
525 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
526 | \\019\019\019\019\019\019\019\019\019\019\000\000\000\000\000\000\ | |
527 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
528 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
529 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
530 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
531 | \\000" | |
532 | ), | |
533 | (21, | |
534 | "\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
535 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
536 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
537 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
538 | \\000\022\022\022\022\022\022\022\022\022\022\022\022\022\022\022\ | |
539 | \\022\022\022\022\022\022\022\022\022\022\022\000\000\000\000\000\ | |
540 | \\000\022\022\022\022\022\022\022\022\022\022\022\022\022\022\022\ | |
541 | \\022\022\022\022\022\022\022\022\022\022\022\000\000\000\000\000\ | |
542 | \\000" | |
543 | ), | |
544 | (22, | |
545 | "\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
546 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
547 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\022\000\000\ | |
548 | \\022\022\022\022\022\022\022\022\022\022\000\000\000\000\000\000\ | |
549 | \\000\022\022\022\022\022\022\022\022\022\022\022\022\022\022\022\ | |
550 | \\022\022\022\022\022\022\022\022\022\022\022\000\000\000\000\022\ | |
551 | \\000\022\022\022\022\022\022\022\022\022\022\022\022\022\022\022\ | |
552 | \\022\022\022\022\022\022\022\022\022\022\022\000\000\000\000\000\ | |
553 | \\000" | |
554 | ), | |
555 | (23, | |
556 | "\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
557 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
558 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
559 | \\012\012\012\012\012\012\012\012\012\012\000\000\000\000\000\000\ | |
560 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
561 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
562 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
563 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
564 | \\000" | |
565 | ), | |
566 | (28, | |
567 | "\000\000\000\000\000\000\000\000\000\000\029\000\000\000\000\000\ | |
568 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
569 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
570 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
571 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
572 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
573 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
574 | \\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\000\ | |
575 | \\000" | |
576 | ), | |
577 | (0, "")] | |
578 | fun f x = x | |
579 | val s = map f (rev (tl (rev s))) | |
580 | exception LexHackingError | |
581 | fun look ((j,x)::r, i) = if i = j then x else look(r, i) | |
582 | | look ([], i) = raise LexHackingError | |
583 | fun g {fin=x, trans=i} = {fin=x, trans=look(s,i)} | |
584 | in Vector.fromList(map g | |
585 | [{fin = [], trans = 0}, | |
586 | {fin = [], trans = 1}, | |
587 | {fin = [], trans = 1}, | |
588 | {fin = [], trans = 3}, | |
589 | {fin = [], trans = 3}, | |
590 | {fin = [], trans = 5}, | |
591 | {fin = [], trans = 5}, | |
592 | {fin = [(N 13)], trans = 0}, | |
593 | {fin = [(N 11)], trans = 0}, | |
594 | {fin = [(N 49)], trans = 9}, | |
595 | {fin = [(N 9)], trans = 0}, | |
596 | {fin = [(N 7)], trans = 0}, | |
597 | {fin = [(N 39)], trans = 12}, | |
598 | {fin = [], trans = 13}, | |
599 | {fin = [(N 35)], trans = 14}, | |
600 | {fin = [], trans = 14}, | |
601 | {fin = [], trans = 16}, | |
602 | {fin = [(N 35)], trans = 17}, | |
603 | {fin = [], trans = 18}, | |
604 | {fin = [(N 35)], trans = 19}, | |
605 | {fin = [], trans = 19}, | |
606 | {fin = [], trans = 21}, | |
607 | {fin = [(N 20)], trans = 22}, | |
608 | {fin = [], trans = 23}, | |
609 | {fin = [(N 43)], trans = 0}, | |
610 | {fin = [(N 41)], trans = 0}, | |
611 | {fin = [(N 5)], trans = 0}, | |
612 | {fin = [(N 58)], trans = 0}, | |
613 | {fin = [(N 55)], trans = 28}, | |
614 | {fin = [(N 55)], trans = 0}, | |
615 | {fin = [(N 62)], trans = 0}, | |
616 | {fin = [(N 60),(N 62)], trans = 0}]) | |
617 | end | |
618 | structure StartStates = | |
619 | struct | |
620 | datatype yystartstate = STARTSTATE of int | |
621 | ||
622 | (* start state definitions *) | |
623 | ||
624 | val C = STARTSTATE 3; | |
625 | val INITIAL = STARTSTATE 1; | |
626 | val S = STARTSTATE 5; | |
627 | ||
628 | end | |
629 | type result = UserDeclarations.lexresult | |
630 | exception LexerError (* raised if illegal leaf action tried *) | |
631 | end | |
632 | ||
633 | type int = Int.int | |
634 | fun makeLexer (yyinput: int -> string) = | |
635 | let val yygone0:int=1 | |
636 | val yyb = ref "\n" (* buffer *) | |
637 | val yybl: int ref = ref 1 (*buffer length *) | |
638 | val yybufpos: int ref = ref 1 (* location of next character to use *) | |
639 | val yygone: int ref = ref yygone0 (* position in file of beginning of buffer *) | |
640 | val yydone = ref false (* eof found yet? *) | |
641 | val yybegin: int ref = ref 1 (*Current 'start state' for lexer *) | |
642 | ||
643 | val YYBEGIN = fn (Internal.StartStates.STARTSTATE x) => | |
644 | yybegin := x | |
645 | ||
646 | fun lex (yyarg as (())) = | |
647 | let fun continue() : Internal.result = | |
648 | let fun scan (s,AcceptingLeaves : Internal.yyfinstate list list,l,i0: int) = | |
649 | let fun action (i: int,nil) = raise LexError | |
650 | | action (i,nil::l) = action (i-1,l) | |
651 | | action (i,(node::acts)::l) = | |
652 | case node of | |
653 | Internal.N yyk => | |
654 | (let fun yymktext() = String.substring(!yyb,i0,i-i0) | |
655 | val yypos: int = i0+ !yygone | |
656 | fun REJECT() = action(i,acts::l) | |
657 | open UserDeclarations Internal.StartStates | |
658 | in (yybufpos := i; case yyk of | |
659 | ||
660 | (* Application actions *) | |
661 | ||
662 | 11 => (Token.Lbrace) | |
663 | | 13 => (Token.Rbrace) | |
664 | | 20 => let val yytext=yymktext() in Token.Binder(String.extract(yytext, 1, NONE)) end | |
665 | | 35 => let val yytext=yymktext() in Token.Real(case Real.fromString yytext of | |
666 | NONE => | |
667 | fail(concat["bad real constant ", yytext]) | |
668 | | SOME r => r) end | |
669 | | 39 => let val yytext=yymktext() in Token.Int(case Int.fromString yytext of | |
670 | NONE => | |
671 | fail(concat["bad int constant ", yytext]) | |
672 | | SOME i => i) end | |
673 | | 41 => (chars := []; YYBEGIN S; continue()) | |
674 | | 43 => (YYBEGIN C; continue()) | |
675 | | 49 => let val yytext=yymktext() in Token.Identifier yytext end | |
676 | | 5 => (continue()) | |
677 | | 55 => (YYBEGIN INITIAL; continue()) | |
678 | | 58 => (continue()) | |
679 | | 60 => (let val s = (implode(rev(!chars)) before chars := nil) | |
680 | in YYBEGIN INITIAL | |
681 | ; Token.String s | |
682 | end) | |
683 | | 62 => let val yytext=yymktext() in chars := String.sub(yytext, 0) :: !chars | |
684 | ; continue() end | |
685 | | 7 => (Token.Lbracket) | |
686 | | 9 => (Token.Rbracket) | |
687 | | _ => raise Internal.LexerError | |
688 | ||
689 | ) end ) | |
690 | ||
691 | val {fin,trans} = Vector.sub(Internal.tab, s) | |
692 | val NewAcceptingLeaves = fin::AcceptingLeaves | |
693 | in if l = !yybl then | |
694 | if trans = #trans(Vector.sub(Internal.tab,0)) | |
695 | then action(l,NewAcceptingLeaves | |
696 | ) else let val newchars= if !yydone then "" else yyinput 1024 | |
697 | in if (String.size newchars)=0 | |
698 | then (yydone := true; | |
699 | if (l=i0) then UserDeclarations.eof yyarg | |
700 | else action(l,NewAcceptingLeaves)) | |
701 | else (if i0=l then yyb := newchars | |
702 | else yyb := String.substring(!yyb,i0,l-i0)^newchars; | |
703 | yygone := !yygone+i0; | |
704 | yybl := String.size (!yyb); | |
705 | scan (s,AcceptingLeaves,l-i0,0)) | |
706 | end | |
707 | else let val NewChar = Char.ord(CharVector.sub(!yyb,l)) | |
708 | val NewChar = if NewChar<128 then NewChar else 128 | |
709 | val NewState = Char.ord(CharVector.sub(trans,NewChar)) | |
710 | in if NewState=0 then action(l,NewAcceptingLeaves) | |
711 | else scan(NewState,NewAcceptingLeaves,l+1,i0) | |
712 | end | |
713 | end | |
714 | (* | |
715 | val start= if String.substring(!yyb,!yybufpos-1,1)="\n" | |
716 | then !yybegin+1 else !yybegin | |
717 | *) | |
718 | in scan(!yybegin (* start *),nil,!yybufpos,!yybufpos) | |
719 | end | |
720 | in continue end | |
721 | in lex | |
722 | end | |
723 | end | |
724 | signature PROGRAM = | |
725 | sig | |
726 | include CAML | |
727 | (**** Basic types: programs, values, ... ****) | |
728 | ||
729 | datatype k = | |
730 | Acos | Addi | Addf | Apply | Asin | Clampf | Cone | Cos | Cube | |
731 | | Cylinder | Difference | Divi | Divf | Eqi | Eqf | Floor | Frac | |
732 | | Get | Getx | Gety | Getz | If | Intersect | Length | Lessi | Lessf | |
733 | | Light | Modi | Muli | Mulf | Negi | Negf | Plane | Point | |
734 | | Pointlight | Real | Render | Rotatex | Rotatey | Rotatez | Scale | |
735 | | Sin | Sphere | Spotlight | Sqrt | Subi | Subf | Translate | Union | |
736 | | Uscale | |
737 | ||
738 | (* Program tokens *) | |
739 | datatype t = | |
740 | Fun of t list | |
741 | | Arr of t list | |
742 | | Ident of string | |
743 | | Binder of string | |
744 | | Int of int | |
745 | | Float of float | |
746 | | Bool of bool | |
747 | | String of string | |
748 | | Prim of k | |
749 | ||
750 | (* internal representation of program tokens *) | |
751 | datatype t' = | |
752 | Fun' of t' list | |
753 | | Arr' of t' list | |
754 | | Ident' of int (* index to environment stack *) | |
755 | | Binder' | |
756 | (* | |
757 | | Int' of int | |
758 | | Float' of float | |
759 | | Bool' of bool | |
760 | | String' of string | |
761 | *) | |
762 | | Prim' of k | |
763 | | Val' of v (* inlined value *) | |
764 | ||
765 | (* Values *) | |
766 | and v = | |
767 | VInt of int | |
768 | | VFloat of float | |
769 | | VBool of bool | |
770 | | VStr of string | |
771 | | VClos of v list * t' list | |
772 | | VFun of (v list -> v list) (* XXX for the compiler *) | |
773 | | VArr of v array | |
774 | | VPoint of v * v * v (* XXX Maybe these should be floats? *) | |
775 | | VObj of obj | |
776 | | VLight of v * v | |
777 | | VPtLight of v * v | |
778 | | VStLight of v * v * v * v * v | |
779 | ||
780 | and obj = | |
781 | OObj of kind * closure ref | |
782 | | OTransform of | |
783 | obj * | |
784 | Matrix.t * (* World to object *) | |
785 | Matrix.t * (* Object to world *) | |
786 | float * (* Scale factor *) | |
787 | bool (* Isometry? *) | |
788 | | OUnion of obj * obj | |
789 | | OInter of obj * obj | |
790 | | ODiff of obj * obj | |
791 | ||
792 | and kind = | |
793 | OSphere | |
794 | | OCube | |
795 | | OCylind | |
796 | | OCone | |
797 | | OPlane | |
798 | ||
799 | and closure = | |
800 | Unopt of v (* Unoptimized function *) | |
801 | | Opt of v | |
802 | | Cst of (float * float * float * float * float * float) | |
803 | ||
804 | (* Translation of an identifier *) | |
805 | val translate : string -> t | |
806 | ||
807 | (* Get the name of an identifier *) | |
808 | (* val name : t' -> string *) | |
809 | ||
810 | exception Stuck_computation of v list * v list * t' list | |
811 | exception Stuck_computation' (* for compiler *) | |
812 | ||
813 | val read: TextIO.instream -> t list | |
814 | end | |
815 | structure Program: PROGRAM = | |
816 | struct | |
817 | ||
818 | open Caml | |
819 | ||
820 | datatype k = | |
821 | Acos | Addi | Addf | Apply | Asin | Clampf | Cone | Cos | Cube | |
822 | | Cylinder | Difference | Divi | Divf | Eqi | Eqf | Floor | Frac | |
823 | | Get | Getx | Gety | Getz | If | Intersect | Length | Lessi | Lessf | |
824 | | Light | Modi | Muli | Mulf | Negi | Negf | Plane | Point | |
825 | | Pointlight | Real | Render | Rotatex | Rotatey | Rotatez | Scale | |
826 | | Sin | Sphere | Spotlight | Sqrt | Subi | Subf | Translate | Union | |
827 | | Uscale | |
828 | ||
829 | datatype t = | |
830 | Fun of t list | |
831 | | Arr of t list | |
832 | | Ident of string | |
833 | | Binder of string | |
834 | | Int of int | |
835 | | Float of float | |
836 | | Bool of bool | |
837 | | String of string | |
838 | | Prim of k | |
839 | ||
840 | datatype t' = | |
841 | Fun' of t' list | |
842 | | Arr' of t' list | |
843 | | Ident' of int (* index to environment stack *) | |
844 | | Binder' | |
845 | (* | |
846 | | Int' of int | |
847 | | Float' of float | |
848 | | Bool' of bool | |
849 | | String' of string | |
850 | *) | |
851 | | Prim' of k | |
852 | | Val' of v (* inlined value *) | |
853 | ||
854 | and v = | |
855 | VInt of int | |
856 | | VFloat of float | |
857 | | VBool of bool | |
858 | | VStr of string | |
859 | | VClos of v list * t' list | |
860 | | VFun of (v list -> v list) (* XXX for the compiler *) | |
861 | | VArr of v array | |
862 | | VPoint of v * v * v | |
863 | | VObj of obj | |
864 | | VLight of v * v | |
865 | | VPtLight of v * v | |
866 | | VStLight of v * v * v * v * v | |
867 | ||
868 | and obj = | |
869 | OObj of kind * closure ref | |
870 | | OTransform of | |
871 | obj * | |
872 | Matrix.t * (* World to object *) | |
873 | Matrix.t * (* Object to world *) | |
874 | float * (* Scale factor *) | |
875 | bool (* Isometry? *) | |
876 | | OUnion of obj * obj | |
877 | | OInter of obj * obj | |
878 | | ODiff of obj * obj | |
879 | ||
880 | and kind = | |
881 | OSphere | |
882 | | OCube | |
883 | | OCylind | |
884 | | OCone | |
885 | | OPlane | |
886 | ||
887 | and closure = | |
888 | Unopt of v | |
889 | | Opt of v | |
890 | | Cst of (float * float * float * float * float * float) | |
891 | ||
892 | fun create_hashtables size init = | |
893 | let | |
894 | val tbl: (string, t) Hashtbl.t = Hashtbl.create size | |
895 | (* val tbl' = Hashtbl.create size *) | |
896 | in | |
897 | List.iter (fn (key, data) => Hashtbl.add tbl key data) init; | |
898 | (* List.iter (fn (data, key) -> Hashtbl.add tbl' key data) init; *) | |
899 | tbl (*, tbl' *) | |
900 | end | |
901 | ||
902 | val keywords(*, keyword_name)*) = | |
903 | create_hashtables 101 | |
904 | (* Booleans are either the literal true or the literal false. *) | |
905 | [ ("true", Bool true), | |
906 | ("false", Bool false), | |
907 | (* Operators (see appendix) *) | |
908 | ("acos", Prim Acos), | |
909 | ("addi", Prim Addi), | |
910 | ("addf", Prim Addf), | |
911 | ("apply", Prim Apply), | |
912 | ("asin", Prim Asin), | |
913 | ("clampf", Prim Clampf), | |
914 | ("cone", Prim Cone), | |
915 | ("cos", Prim Cos), | |
916 | ("cube", Prim Cube), | |
917 | ("cylinder", Prim Cylinder), | |
918 | ("difference", Prim Difference), | |
919 | ("divi", Prim Divi), | |
920 | ("divf", Prim Divf), | |
921 | ("eqi", Prim Eqi), | |
922 | ("eqf", Prim Eqf), | |
923 | ("floor", Prim Floor), | |
924 | ("frac", Prim Frac), | |
925 | ("get", Prim Get), | |
926 | ("getx", Prim Getx), | |
927 | ("gety", Prim Gety), | |
928 | ("getz", Prim Getz), | |
929 | ("if", Prim If), | |
930 | ("intersect", Prim Intersect), | |
931 | ("length", Prim Length), | |
932 | ("lessi", Prim Lessi), | |
933 | ("lessf", Prim Lessf), | |
934 | ("light", Prim Light), | |
935 | ("modi", Prim Modi), | |
936 | ("muli", Prim Muli), | |
937 | ("mulf", Prim Mulf), | |
938 | ("negi", Prim Negi), | |
939 | ("negf", Prim Negf), | |
940 | ("plane", Prim Plane), | |
941 | ("point", Prim Point), | |
942 | ("pointlight", Prim Pointlight), | |
943 | ("real", Prim Real), | |
944 | ("render", Prim Render), | |
945 | ("rotatex", Prim Rotatex), | |
946 | ("rotatey", Prim Rotatey), | |
947 | ("rotatez", Prim Rotatez), | |
948 | ("scale", Prim Scale), | |
949 | ("sin", Prim Sin), | |
950 | ("sphere", Prim Sphere), | |
951 | ("spotlight", Prim Spotlight), | |
952 | ("sqrt", Prim Sqrt), | |
953 | ("subi", Prim Subi), | |
954 | ("subf", Prim Subf), | |
955 | ("translate", Prim Translate), | |
956 | ("union", Prim Union), | |
957 | ("uscale", Prim Uscale)] | |
958 | ||
959 | fun translate i = | |
960 | Hashtbl.find keywords i | |
961 | handle Not_found => Ident i | |
962 | ||
963 | (* fun name token = | |
964 | * Hashtbl.find keyword_name | |
965 | * (match token with | |
966 | * Prim' k -> Prim k | |
967 | * | _ -> raise Not_found) | |
968 | * | |
969 | *) | |
970 | exception Stuck_computation of v list * v list * t' list | |
971 | exception Stuck_computation' (* for compiler *) | |
972 | ||
973 | structure LexToken = LexToken() | |
974 | structure Lex = Lex(structure Token = LexToken) | |
975 | ||
976 | fun read(ins: TextIO.instream): t list = | |
977 | let | |
978 | val lex: unit -> LexToken.t = | |
979 | Lex.makeLexer(fn n => TextIO.inputN(ins, n))() | |
980 | local | |
981 | val next: LexToken.t option ref = ref NONE | |
982 | in | |
983 | fun token(): LexToken.t = | |
984 | case !next of | |
985 | NONE => lex() | |
986 | | SOME t => (next := NONE; t) | |
987 | fun save(t: LexToken.t): unit = | |
988 | next := SOME t | |
989 | end | |
990 | fun bad() = failwith "invalid input" | |
991 | fun many(done: LexToken.t -> bool): t list = | |
992 | let | |
993 | fun loop(ac: t list) = | |
994 | case one() of | |
995 | NONE => if done(token()) | |
996 | then rev ac | |
997 | else bad() | |
998 | | SOME t => loop(t :: ac) | |
999 | in loop [] | |
1000 | end | |
1001 | and one(): t option = | |
1002 | let fun tok t = SOME t | |
1003 | in case token() of | |
1004 | LexToken.Binder x => tok(Binder x) | |
1005 | | LexToken.Bool b => tok(Bool b) | |
1006 | | LexToken.Identifier x => tok(translate x) | |
1007 | | LexToken.Int i => tok(Int i) | |
1008 | | LexToken.Lbrace => | |
1009 | SOME(Fun(many(fn LexToken.Rbrace => true | _ => false))) | |
1010 | | LexToken.Lbracket => | |
1011 | SOME(Arr(many(fn LexToken.Rbracket => true | _ =>false))) | |
1012 | | LexToken.Real r => tok(Float r) | |
1013 | | LexToken.String s => tok(String s) | |
1014 | | t => (save t; NONE) | |
1015 | end | |
1016 | in many(fn LexToken.Eof => true | _ => false) | |
1017 | end | |
1018 | ||
1019 | end | |
1020 | signature PPM = | |
1021 | sig | |
1022 | include CAML | |
1023 | ||
1024 | type pixmap | |
1025 | ||
1026 | val init : (*width:*)int * (*height:*)int -> pixmap | |
1027 | val dump : string * pixmap -> unit | |
1028 | (* val load : string -> pixmap *) | |
1029 | ||
1030 | val width : pixmap -> int | |
1031 | val height : pixmap -> int | |
1032 | ||
1033 | val get : pixmap * int * int * int -> int | |
1034 | val set : pixmap * int * int * int * int -> unit | |
1035 | val setp : pixmap * int * int * int * int * int -> unit | |
1036 | end | |
1037 | structure Ppm: PPM = | |
1038 | struct | |
1039 | ||
1040 | open Caml | |
1041 | ||
1042 | structure Array = Word8Array | |
1043 | structure Word = Word8 | |
1044 | ||
1045 | type pixmap = Array.array * int | |
1046 | ||
1047 | fun get ((img, width), i, j, k) = | |
1048 | Word.toInt (Array.sub (img, ((j * width) + i) * 3 + k)) | |
1049 | ||
1050 | fun set ((img, width), i, j, k, v) = | |
1051 | Array.update (img, ((j * width) + i) * 3 + k, Word.fromInt v) | |
1052 | ||
1053 | fun setp ((img, width), i, j, r, g, b) = | |
1054 | let val p = ((j * width) + i) * 3 | |
1055 | in Array.update(img, p, Word.fromInt r) | |
1056 | ; Array.update(img, p + 1, Word.fromInt g) | |
1057 | ; Array.update(img, p + 2, Word.fromInt b) | |
1058 | end | |
1059 | ||
1060 | fun init (width, height) = | |
1061 | (Array.array(height * width * 3, 0w0), width) | |
1062 | ||
1063 | fun width (s, width) = width | |
1064 | fun height (s, width) = Array.length s div width div 3 | |
1065 | ||
1066 | fun dump (file, (img, width)) = | |
1067 | let | |
1068 | val sz = Array.length img | |
1069 | val height = sz div 3 div width | |
1070 | val f = open_out_bin file | |
1071 | in output_string (f, "P6\n# PL Club - translated to SML\n") | |
1072 | ; output_string (f, concat[Int.toString width, " ", | |
1073 | Int.toString height, "\n255\n"]) | |
1074 | ; output_string (f, Byte.unpackString (Word8ArraySlice.slice | |
1075 | (img, 0, NONE))) | |
1076 | ; close_out f | |
1077 | end | |
1078 | ||
1079 | (* fun load file = | |
1080 | * let f = open_in_bin file in | |
1081 | * assert (input_line f = "P6"); | |
1082 | * assert ((input_line f).[0] = '#'); | |
1083 | * let s = input_line f in | |
1084 | * let i = ref 0 in | |
1085 | * while s.[!i] >= '0' && s.[!i] <= '9' do incr i done; | |
1086 | * let width = int_of_string (String.sub s 0 !i) in | |
1087 | * let height = | |
1088 | * int_of_string (String.sub s (!i + 1) (String.length s - !i - 1)) in | |
1089 | * assert (input_line f = "255"); | |
1090 | * let (s, _) as img = init width height in | |
1091 | * really_input f s 0 (String.length s); | |
1092 | * close_in f; | |
1093 | * img | |
1094 | *) | |
1095 | end | |
1096 | signature RENDER = | |
1097 | sig | |
1098 | include CAML | |
1099 | ||
1100 | val apply : (Program.v * Program.v list -> Program.v list) ref | |
1101 | val inline_closure : (Program.v -> Program.v) ref | |
1102 | ||
1103 | val f : | |
1104 | (*amb:*)(float * float * float) * (*lights:*) Program.v array * | |
1105 | (*obj:*)Program.obj * (*depth:*)int * (*fov:*)float * | |
1106 | (*wid:*)int * (*ht:*)int * | |
1107 | (*file:*)string -> unit | |
1108 | end | |
1109 | structure Render: RENDER = | |
1110 | struct | |
1111 | ||
1112 | open Caml | |
1113 | infix 9 ** | |
1114 | open Program | |
1115 | ||
1116 | (* Scene description *) | |
1117 | datatype kind = (* section 3.2 *) | |
1118 | SSphere of Matrix.v (* Center *) * float (* Square of the radius *) | |
1119 | | SEllips | |
1120 | | SCube of Matrix.v (* Normal x = 0 *) * | |
1121 | Matrix.v (* Normal y = 0 *) * | |
1122 | Matrix.v (* Normal z = 0 *) | |
1123 | | SCylind of Matrix.v (* Normal *) | |
1124 | | SCone of Matrix.v (* Normal *) | |
1125 | | SPlane of Matrix.v (* Equation *) * Matrix.v (* Normal *) | |
1126 | ||
1127 | datatype scene = (* section 3.7 *) | |
1128 | SObj of kind * closure ref (* surface function *) * Matrix.t | |
1129 | | SBound of scene * Matrix.v (* Center *) * float (* Square of the radius *) | |
1130 | | SUnion of scene * scene | |
1131 | | SInter of scene * scene | |
1132 | | SDiff of scene * scene | |
1133 | ||
1134 | datatype light = (* section 3.5 *) | |
1135 | Light of Matrix.v (* negated & normalized *) * (float * float * float) | |
1136 | | PtLight of Matrix.v * (float * float * float) | |
1137 | | StLight of Matrix.v * Matrix.v (* negated & normalized *) * | |
1138 | (float * float * float) * float (* cos *) * float | |
1139 | ||
1140 | type desc = | |
1141 | { amb : float * float * float, | |
1142 | lights : light array, | |
1143 | scene : scene } | |
1144 | ||
1145 | open Math | |
1146 | open Matrix | |
1147 | ||
1148 | (**** Scene calculation ****) | |
1149 | ||
1150 | (* Plane equation and normal in world coordinates *) | |
1151 | fun plane_eq(m, v) = | |
1152 | let | |
1153 | val n = vmul (transpose m, v ) | |
1154 | in | |
1155 | (n, normalize(#1 n, #2 n, #3 n, 0.0)) | |
1156 | end | |
1157 | ||
1158 | val origin = ( 0.0, 0.0, 0.0, 1.0 ) | |
1159 | val cube_center = ( 0.5, 0.5, 0.5, 1.0 ) | |
1160 | val cylinder_center = ( 0.0, 0.5, 0.0, 1.0 ) | |
1161 | val cone_center = ( 0.0, 1.0, 0.0, 1.0 ) | |
1162 | ||
1163 | fun intern_obj(m, m1, scale, isom, ob) = | |
1164 | (* apply transformations *) | |
1165 | case ob of | |
1166 | OObj (OSphere, f) => | |
1167 | if isom | |
1168 | then | |
1169 | let | |
1170 | val center = vmul (m1, origin) | |
1171 | val radius = scale * scale | |
1172 | in | |
1173 | SBound (SObj (SSphere (center, radius), f, m), center, radius) | |
1174 | end | |
1175 | else | |
1176 | let | |
1177 | val center = vmul (m1, origin) | |
1178 | val radius = scale * scale | |
1179 | in | |
1180 | SBound (SObj (SEllips, f, m), center, radius) | |
1181 | end | |
1182 | | OObj (OCube, f) => | |
1183 | let | |
1184 | val (nx, nx') = plane_eq(m, (1.0, 0.0, 0.0, 0.0)) | |
1185 | val (ny, ny') = plane_eq(m, (0.0, 1.0, 0.0, 0.0)) | |
1186 | val (nz, nz') = plane_eq(m, (0.0, 0.0, 1.0, 0.0)) | |
1187 | val c = SObj (SCube (nx', ny', nz'), f, m) | |
1188 | in | |
1189 | SBound (c, vmul (m1, cube_center), scale * scale * 0.75) | |
1190 | end | |
1191 | | OObj (OCylind, f) => | |
1192 | let | |
1193 | val (n, n') = plane_eq(m, (0.0, 1.0, 0.0, 0.0)) | |
1194 | val c = SObj (SCylind n', f, m) | |
1195 | in | |
1196 | SBound (c, vmul(m1, cylinder_center), scale * scale * 1.25) | |
1197 | end | |
1198 | | OObj (OCone, f) => | |
1199 | let | |
1200 | val (n, n') = plane_eq(m, (0.0, 1.0, 0.0, 0.0)) | |
1201 | val c = SObj (SCone n', f, m) | |
1202 | in | |
1203 | SBound (c, vmul(m1, cone_center), scale * scale) | |
1204 | end | |
1205 | | OObj (OPlane, f) => | |
1206 | let | |
1207 | val (n, n') = plane_eq(m, (0.0, 1.0, 0.0, 0.0)) | |
1208 | in | |
1209 | SObj (SPlane (n, n'), f, m) | |
1210 | end | |
1211 | | OTransform (o', m', m'1, scale', isom') => | |
1212 | intern_obj | |
1213 | (Matrix.mul(m', m), Matrix.mul(m1, m'1), | |
1214 | scale * scale', isom andalso isom', o') | |
1215 | | OUnion (o1, o2) => | |
1216 | SUnion (intern_obj(m, m1, scale, isom, o1), | |
1217 | intern_obj(m, m1, scale, isom, o2)) | |
1218 | | OInter (o1, o2) => | |
1219 | SInter (intern_obj(m, m1, scale, isom, o1), | |
1220 | intern_obj(m, m1, scale, isom, o2)) | |
1221 | | ODiff (ODiff (o1, o2), o3) => | |
1222 | (* Better to have unions that diffs for introducing bounds *) | |
1223 | intern_obj(m, m1, scale, isom, (ODiff (o1, OUnion (o2, o3)))) | |
1224 | | ODiff (o1, o2) => | |
1225 | SDiff (intern_obj(m, m1, scale, isom, o1), | |
1226 | intern_obj(m, m1, scale, isom, o2)) | |
1227 | ||
1228 | fun intern_lights a = | |
1229 | Array.map | |
1230 | (fn VLight (VPoint (VFloat x, VFloat y, VFloat z), | |
1231 | VPoint (VFloat r, VFloat g, VFloat b)) => | |
1232 | Light (normalize (neg (x, y, z, 0.0)), (r, g, b)) | |
1233 | | VPtLight (VPoint (VFloat x, VFloat y, VFloat z), | |
1234 | VPoint (VFloat r, VFloat g, VFloat b)) => | |
1235 | PtLight ((x, y, z, 1.0), (r, g, b)) | |
1236 | | VStLight (VPoint (VFloat x, VFloat y, VFloat z), | |
1237 | VPoint (VFloat x', VFloat y', VFloat z'), | |
1238 | VPoint (VFloat r, VFloat g, VFloat b), | |
1239 | VFloat cutoff, VFloat exp) => | |
1240 | StLight ((x, y, z, 1.0), | |
1241 | normalize (x - x', y - y', z - z', 0.0), | |
1242 | (r, g, b), dcos cutoff, exp) | |
1243 | | _ => | |
1244 | raise(Fail "assert false")) | |
1245 | a | |
1246 | ||
1247 | (**** Scene optimization ****) | |
1248 | ||
1249 | fun flatten_rec(sc, rem) = | |
1250 | case sc of | |
1251 | SUnion (sc1, sc2) => flatten_rec(sc1, flatten_rec(sc2, rem)) | |
1252 | | sc => sc :: rem | |
1253 | ||
1254 | fun flatten_union sc = flatten_rec(sc, []) | |
1255 | ||
1256 | fun object_cost k : int = | |
1257 | case k of | |
1258 | SSphere _ => 1 | |
1259 | | SEllips => 2 | |
1260 | | SCube _ => 4 | |
1261 | | SCylind _ => 2 | |
1262 | | SCone _ => 2 | |
1263 | | SPlane _ => 0 (* Planes do not have a bounding box anyway *) | |
1264 | ||
1265 | fun add_bound (r0, (x, r, cost, sc)) = | |
1266 | if r0 < 0.0 | |
1267 | then | |
1268 | if r < 0.0 orelse cost <= 1 | |
1269 | then (cost, sc) | |
1270 | else | |
1271 | (1, SBound (sc, x, r)) | |
1272 | else | |
1273 | (* Cost of bounds *) | |
1274 | let | |
1275 | val c0 = r0 + r * float cost | |
1276 | (* Cost ofout bounds *) | |
1277 | val c1 = r0 * float cost | |
1278 | in | |
1279 | if c0 < c1 then | |
1280 | (1, SBound (sc, x, r)) | |
1281 | else | |
1282 | (cost, sc) | |
1283 | end | |
1284 | ||
1285 | fun union_bound (dsc1 as (x1, r1, cost1, sc1), | |
1286 | dsc2 as (x2, r2, cost2, sc2)) = | |
1287 | if r1 < 0.0 then | |
1288 | let | |
1289 | val (cost2', sc2') = add_bound(r1, dsc2) | |
1290 | in | |
1291 | (x1, r1, cost1, SUnion (sc1, sc2')) | |
1292 | end | |
1293 | else if r2 < 0.0 then | |
1294 | let | |
1295 | val (cost1', sc1') = add_bound (r2, dsc1) | |
1296 | in | |
1297 | (x2, r2, cost2, SUnion (sc1', sc2)) | |
1298 | end | |
1299 | else | |
1300 | let | |
1301 | val d = sqrt (square (sub(x2, x1))) | |
1302 | val r1' = sqrt r1 | |
1303 | val r2' = sqrt r2 | |
1304 | in | |
1305 | if d + r2' <= r1' then | |
1306 | let | |
1307 | val (cost2', sc2') = add_bound (r1, dsc2) | |
1308 | in | |
1309 | (x1, r1, cost1 + cost2', SUnion (sc1, sc2')) | |
1310 | end | |
1311 | else if d + r1' <= r2' then | |
1312 | let | |
1313 | val (cost1', sc1') = add_bound (r2, dsc1) | |
1314 | in | |
1315 | (x2, r2, cost1' + cost2, SUnion (sc1', sc2)) | |
1316 | end | |
1317 | else | |
1318 | let | |
1319 | val r' = (r1' + r2' + d) * 0.5 | |
1320 | val r = r' * r' | |
1321 | val x = add_scaled (x1, (r' - r1') / d, sub(x2, x1)) | |
1322 | val (cost1', sc1') = add_bound (r, dsc1) | |
1323 | val (cost2', sc2') = add_bound (r, dsc2) | |
1324 | in | |
1325 | (x, r, cost1' + cost2', SUnion (sc1', sc2')) | |
1326 | end | |
1327 | end | |
1328 | ||
1329 | fun union_radius (dsc1 as (x1, r1, cost1, sc1), | |
1330 | dsc2 as (x2, r2, cost2, sc2)) = | |
1331 | let | |
1332 | val d = sqrt (square (sub (x2, x1))) | |
1333 | val r1' = sqrt r1 | |
1334 | val r2' = sqrt r2 | |
1335 | in | |
1336 | if d + r2' <= r1' then r1 else | |
1337 | if d + r1' <= r2' then r2 else | |
1338 | let | |
1339 | val r' = (r1' + r2' + d) * 0.5 | |
1340 | in | |
1341 | r' * r' | |
1342 | end | |
1343 | end | |
1344 | ||
1345 | fun merge2 l = | |
1346 | case l of | |
1347 | sc1 :: sc2 :: r => union_bound (sc1, sc2) :: merge2 r | |
1348 | | _ => l | |
1349 | ||
1350 | fun merge_union l = | |
1351 | case l of | |
1352 | [] => raise(Fail "assert false") | |
1353 | | [sc1] => sc1 | |
1354 | | l => merge_union (merge2 l) | |
1355 | ||
1356 | fun opt_union l = | |
1357 | case l of | |
1358 | [] => l | |
1359 | | [_] => l | |
1360 | | [sc1, sc2] => [union_bound(sc1, sc2)] | |
1361 | | _ => | |
1362 | let | |
1363 | val c = Array.of_list l | |
1364 | val n = Array.length c | |
1365 | val m = Array2.array(n, n, infinity) | |
1366 | val _ = | |
1367 | for(0, n - 1, fn i => | |
1368 | for(0, n - 1, fn j => | |
1369 | if i <> j | |
1370 | then Array2.update(m, i, j, | |
1371 | union_radius | |
1372 | (Array.sub(c, i), Array.sub(c, j))) | |
1373 | else ())) | |
1374 | val remain = Array.init (n, fn i => i) | |
1375 | val _ = | |
1376 | forDown | |
1377 | (n - 1, 1, fn k => | |
1378 | let | |
1379 | val gain = ref infinity | |
1380 | val i0 = ref 0 | |
1381 | val j0 = ref 0 | |
1382 | val _ = | |
1383 | for(0, k, fn i => | |
1384 | for(0, k, fn j => | |
1385 | let | |
1386 | val i' = Array.sub(remain, i) | |
1387 | val j' = Array.sub(remain, j) | |
1388 | in | |
1389 | if Array2.sub(m, i', j') < !gain | |
1390 | then | |
1391 | (gain := Array2.sub(m, i', j') | |
1392 | ; i0 := i | |
1393 | ; j0 := j) | |
1394 | else () | |
1395 | end)) | |
1396 | val i = Array.sub(remain, !i0) | |
1397 | val j = Array.sub(remain, !j0) | |
1398 | in | |
1399 | Array.update(remain, !j0, Array.sub(remain, k)); | |
1400 | Array.update(c, i, | |
1401 | union_bound (Array.sub(c, i), Array.sub(c, j))); | |
1402 | for(0, k - 1, fn j0 => | |
1403 | let | |
1404 | val j = Array.sub(remain, j0) | |
1405 | in | |
1406 | if i <> j | |
1407 | then | |
1408 | ( | |
1409 | Array2.update | |
1410 | (m, i, j, | |
1411 | union_radius | |
1412 | (Array.sub(c, i), Array.sub(c, j))); | |
1413 | Array2.update | |
1414 | (m, j, i, | |
1415 | union_radius | |
1416 | (Array.sub(c, i), Array.sub(c, j)))) | |
1417 | else () | |
1418 | end) | |
1419 | end) | |
1420 | in [Array.sub(c, Array.sub(remain, 0))] | |
1421 | end | |
1422 | ||
1423 | fun optimize_rec sc = | |
1424 | case sc of | |
1425 | SObj (kind, _, _) => | |
1426 | (origin, ~1.0, object_cost kind, sc) | |
1427 | | SUnion _ => | |
1428 | let | |
1429 | val l = List.map optimize_rec (flatten_union sc) | |
1430 | val unbounded = List.filter (fn (_, r, _, _) => r < 0.0) l | |
1431 | val bounded = List.filter (fn (_, r, _, _) => r >= 0.0) l | |
1432 | in | |
1433 | merge_union (opt_union bounded @ unbounded) | |
1434 | end | |
1435 | | SInter (sc1, sc2) => | |
1436 | let | |
1437 | val (x1, r1, cost1, sc1) = optimize_rec sc1 | |
1438 | val (x2, r2, cost2, sc2) = optimize_rec sc2 | |
1439 | in | |
1440 | (* XXX We could have a tighter bound... *) | |
1441 | if r2 < 0.0 then | |
1442 | (x2, r2, cost2, SInter (sc1, sc2)) | |
1443 | else if r1 < 0.0 then | |
1444 | (x1, r1, cost1, SInter (sc2, sc1)) | |
1445 | else if r1 < r2 then | |
1446 | (x1, r1, cost1, SInter (sc1, sc2)) | |
1447 | else | |
1448 | (x2, r2, cost1, SInter (sc2, sc1)) | |
1449 | end | |
1450 | | SDiff (sc1, sc2) => | |
1451 | let | |
1452 | val (x1, r1, cost1, sc1) = optimize_rec sc1 | |
1453 | val dsc2 as (x2, r2, cost2, sc2) = optimize_rec sc2 | |
1454 | val (cost2', sc2') = add_bound (r1, dsc2) | |
1455 | in | |
1456 | (x1, r1, cost1, SDiff (sc1, sc2')) | |
1457 | end | |
1458 | | SBound (sc1, x, r) => | |
1459 | let | |
1460 | val (_, _, cost1, sc1) = optimize_rec sc1 | |
1461 | in | |
1462 | (x, r, cost1, sc1) | |
1463 | end | |
1464 | ||
1465 | fun optimize sc = #2 (add_bound (~1.0, optimize_rec sc)) | |
1466 | ||
1467 | (**** Rendering ****) | |
1468 | ||
1469 | (* operations for intervals *) | |
1470 | fun union (l1, l2) : (float * scene * float * scene) list = (* ES: checked *) | |
1471 | case (l1, l2) of | |
1472 | ([], _) => l2 | |
1473 | | (_, []) => l1 | |
1474 | | ((i1 as (t1, o1, t1', o1')) :: r1, | |
1475 | (i2 as (t2, o2, t2', o2')) :: r2) => | |
1476 | if t1' < t2 | |
1477 | then i1 :: union(r1, l2) | |
1478 | else if t2' < t1 | |
1479 | then i2 :: union(l1, r2) | |
1480 | else | |
1481 | if t1 < t2 then | |
1482 | if t1' < t2' then | |
1483 | union(r1, (t1, o1, t2', o2')::r2) | |
1484 | else | |
1485 | union((t1, o1, t1', o1')::r1, r2) | |
1486 | else | |
1487 | if t1' < t2' then | |
1488 | union(r1, ((t2, o2, t2', o2')::r2)) | |
1489 | else | |
1490 | union((t2, o2, t1', o1')::r1, r2) | |
1491 | ||
1492 | fun inter (l1, l2) : (float * scene * float * scene) list = (* ES: checked *) | |
1493 | case (l1, l2) of | |
1494 | ([], _) => [] | |
1495 | | (_, []) => [] | |
1496 | | ((i1 as (t1, o1, t1', o1')) :: r1, | |
1497 | (i2 as (t2, o2, t2', o2')) :: r2) => | |
1498 | if t1' <= t2 | |
1499 | then inter(r1, l2) | |
1500 | else if t2' <= t1 | |
1501 | then inter(l1, r2) | |
1502 | else | |
1503 | if t1 < t2 then | |
1504 | if t1' < t2' then | |
1505 | (t2, o2, t1', o1') :: inter(r1, l2) | |
1506 | else | |
1507 | i2 :: inter(l1, r2) | |
1508 | else | |
1509 | if t1' < t2' then | |
1510 | i1 :: inter(r1, l2) | |
1511 | else | |
1512 | (t1, o1, t2', o2') :: inter(l1, r2) | |
1513 | ||
1514 | fun diff (l1, l2) : (float * scene * float * scene) list = (* ES: checked *) | |
1515 | case (l1, l2) of | |
1516 | ([], _) => [] | |
1517 | | (_, []) => l1 | |
1518 | | ((i1 as (t1, o1, t1', o1')) :: r1, | |
1519 | (i2 as (t2, o2, t2', o2')) :: r2) => | |
1520 | if t1' <= t2 | |
1521 | then i1 :: diff(r1, l2) | |
1522 | else if t2' <= t1 | |
1523 | then diff(l1, r2) | |
1524 | else | |
1525 | if t1 < t2 then | |
1526 | if t1' < t2' then | |
1527 | (t1, o1, t2, o2) :: diff(r1, l2) | |
1528 | else | |
1529 | (t1, o1, t2, o2) :: diff((t2', o2', t1', o1') :: r1, r2) | |
1530 | else | |
1531 | if t1' < t2' then | |
1532 | diff(r1, l2) | |
1533 | else | |
1534 | diff((t2', o2', t1', o1') :: r1, r2) | |
1535 | ||
1536 | (* intersection of ray and object *) | |
1537 | fun plane (orig, dir, scene, eq) : (float * scene * float * scene) list = | |
1538 | (* XXX Need to be checked *) | |
1539 | let | |
1540 | val porig = prod (eq, orig) | |
1541 | val pdir = prod (eq, dir) | |
1542 | val t = ~ porig / pdir | |
1543 | in | |
1544 | if porig < 0.0 then | |
1545 | if t > 0.0 then | |
1546 | [(0.0, scene, t, scene)] | |
1547 | else | |
1548 | [(0.0, scene, infinity, scene)] | |
1549 | else | |
1550 | if t > 0.0 then | |
1551 | [(t, scene, infinity, scene)] | |
1552 | else | |
1553 | [] | |
1554 | end | |
1555 | ||
1556 | fun band (obj, x, v, i) : (float * scene * float * scene) list = (* ES: checked *) | |
1557 | let | |
1558 | val t1 = ~ (i x) / (i v) | |
1559 | val t2 = (1.0 - (i x)) / (i v) | |
1560 | val t2' = if t1 >= t2 then t1 else t2 | |
1561 | in | |
1562 | if t2' < 0.0 then | |
1563 | [] | |
1564 | else | |
1565 | let val t1' = if t1 <= t2 then t1 else t2 | |
1566 | in | |
1567 | if t1' < 0.0 then | |
1568 | [(0.0, obj, t2', obj)] | |
1569 | else | |
1570 | [(t1', obj, t2', obj)] | |
1571 | end | |
1572 | end | |
1573 | ||
1574 | fun cube (orig, dir, scene, m): (float * scene * float * scene) list = | |
1575 | (* ES: checked *) | |
1576 | let | |
1577 | val x = vmul (m, orig) | |
1578 | val v = vmul (m, dir) | |
1579 | in | |
1580 | case band (scene, x, v, #1) of | |
1581 | [] => [] | |
1582 | | l0 => | |
1583 | case inter (l0, band (scene, x, v, #2)) of | |
1584 | [] => [] | |
1585 | | l1 => inter (l1, band (scene, x, v, #3)) | |
1586 | end | |
1587 | ||
1588 | fun sphere (orig, dir, scene, x, r2): (float * scene * float * scene) list = | |
1589 | let | |
1590 | val v = sub (x, orig) | |
1591 | (* Square of the distance between the origin and the center of the sphere *) | |
1592 | val v2 = square v | |
1593 | val dir2 = square dir | |
1594 | val p = prod (v, dir) | |
1595 | (* Square of the distance between the ray and the center *) | |
1596 | val d2 = v2 - p * p / dir2 | |
1597 | val delta = r2 - d2 | |
1598 | in if delta <= 0.0 | |
1599 | then [] | |
1600 | else | |
1601 | let | |
1602 | val sq = sqrt (delta / dir2) | |
1603 | val t1 = p / dir2 - sq | |
1604 | val t2 = p / dir2 + sq | |
1605 | in | |
1606 | if t2 < 0.0 | |
1607 | then [] | |
1608 | else | |
1609 | [(max_float (0.0, t1), scene, t2, scene)] | |
1610 | end | |
1611 | end | |
1612 | ||
1613 | fun ellipsoid (orig, dir, scene, m): (float * scene * float * scene) list = | |
1614 | (* ES: checked *) | |
1615 | let | |
1616 | val x = vmul (m, orig) | |
1617 | val v = vmul (m, dir) | |
1618 | val x2 = square x | |
1619 | val v2 = square v | |
1620 | val xv = prod (x, v) | |
1621 | val delta = xv * xv - v2 * (x2 - 2.0) | |
1622 | in | |
1623 | if delta <= 0.0 then | |
1624 | [] | |
1625 | else | |
1626 | let | |
1627 | val sq = sqrt delta | |
1628 | val t1 = (~ xv - sq) / v2 | |
1629 | val t2 = (~ xv + sq) / v2 | |
1630 | in if t2 < 0.0 then | |
1631 | [] | |
1632 | else | |
1633 | [(max_float (0.0, t1), scene, t2, scene)] | |
1634 | end | |
1635 | end | |
1636 | ||
1637 | fun cylinder (orig, dir, scene, m): (float * scene * float * scene) list = | |
1638 | let | |
1639 | val x = vmul (m, orig) | |
1640 | val v = vmul (m, dir) | |
1641 | val x2 = #1 x * #1 x + #3 x * #3 x - 1.0 | |
1642 | val v2 = #1 v * #1 v + #3 v * #3 v | |
1643 | val xv = #1 x * #1 v + #3 x * #3 v | |
1644 | val delta = xv * xv - v2 * x2 | |
1645 | in | |
1646 | if delta <= 0.0 then | |
1647 | [] | |
1648 | else | |
1649 | let | |
1650 | val sq = sqrt delta | |
1651 | val t1 = (~ xv - sq) / v2 | |
1652 | val t2 = (~ xv + sq) / v2 | |
1653 | in if t2 < 0.0 then | |
1654 | [] | |
1655 | else | |
1656 | inter | |
1657 | ([(max_float (0.0, t1), scene, t2, scene)], | |
1658 | band (scene, x, v, #2)) | |
1659 | end | |
1660 | end | |
1661 | ||
1662 | fun cone (orig, dir, scene, m): (float * scene * float * scene) list = | |
1663 | let | |
1664 | val x = vmul (m, orig) | |
1665 | val v = vmul (m, dir) | |
1666 | val x2 = #1 x * #1 x + #3 x * #3 x - #2 x * #2 x | |
1667 | val v2 = #1 v * #1 v + #3 v * #3 v - #2 v * #2 v | |
1668 | val xv = #1 x * #1 v + #3 x * #3 v - #2 x * #2 v | |
1669 | val delta = xv * xv - v2 * x2 | |
1670 | in | |
1671 | if delta <= 0.0 then | |
1672 | [] | |
1673 | else | |
1674 | let | |
1675 | val sq = sqrt delta | |
1676 | val t1 = (~ xv - sq) / v2 | |
1677 | val t2 = (~ xv + sq) / v2 | |
1678 | in | |
1679 | if t1 <= t2 then | |
1680 | if t2 < 0.0 then | |
1681 | [] | |
1682 | else | |
1683 | inter | |
1684 | ([(max_float(0.0, t1), scene, t2, scene)], | |
1685 | band (scene, x, v, #2)) | |
1686 | else | |
1687 | inter | |
1688 | (if t1 <= 0.0 then | |
1689 | [(0.0, scene, infinity, scene)] | |
1690 | else if t2 <= 0.0 then | |
1691 | [(t1, scene, infinity, scene)] | |
1692 | else | |
1693 | [(0.0, scene, t2, scene), (t1, scene, infinity, scene)], | |
1694 | band (scene, x, v, #2)) | |
1695 | end | |
1696 | end | |
1697 | ||
1698 | (* XXX Maybe we should check whether the sphere is completely behind us ? *) | |
1699 | fun intersect (orig, dir, x, r2) = | |
1700 | let | |
1701 | val (vx, vy, vz, vt) = sub (x, orig) | |
1702 | (* Square of the distance between the origin and the center of the sphere *) | |
1703 | val v2 = vx * vx + vy * vy + vz * vz + vt * vt | |
1704 | val (dx, dy, dz, dt) = dir | |
1705 | val dir2 = dx * dx + dy * dy + dz * dz + dt * dt | |
1706 | val p = vx * dx + vy * dy + vz * dz + vt * dt | |
1707 | (* Square of the distance between the ray and the center *) | |
1708 | val d2 = v2 - p * p / dir2 | |
1709 | in r2 > d2 | |
1710 | end | |
1711 | ||
1712 | fun find_all (orig, dir, scene) = | |
1713 | case scene of | |
1714 | SObj (SSphere (x, r2), _, m) => | |
1715 | sphere (orig, dir, scene, x, r2) | |
1716 | | SObj (SEllips, _, m) => | |
1717 | ellipsoid (orig, dir, scene, m) | |
1718 | | SObj (SCube _, _, m) => | |
1719 | cube (orig, dir, scene, m) | |
1720 | | SObj (SCylind _, _, m) => | |
1721 | cylinder (orig, dir, scene, m) | |
1722 | | SObj (SCone _, _, m) => | |
1723 | cone (orig, dir, scene, m) | |
1724 | | SObj (SPlane (eq, _), _, m) => | |
1725 | plane (orig, dir, scene, eq) | |
1726 | | SBound (sc, x, r2) => | |
1727 | if intersect (orig, dir, x, r2) | |
1728 | then find_all (orig, dir, sc) | |
1729 | else [] | |
1730 | | SUnion (sc1, sc2) => | |
1731 | union (find_all (orig, dir, sc1), find_all (orig, dir, sc2)) | |
1732 | | SInter (sc1, sc2) => | |
1733 | let val l1 = find_all (orig, dir, sc1) | |
1734 | in | |
1735 | case l1 of | |
1736 | [] => [] | |
1737 | | _ => inter(l1, find_all (orig, dir, sc2)) | |
1738 | end | |
1739 | | SDiff (sc1, sc2) => | |
1740 | let val l1 = find_all(orig, dir, sc1) | |
1741 | in | |
1742 | case l1 of | |
1743 | [] => [] | |
1744 | | _ => diff(l1, find_all(orig, dir, sc2)) | |
1745 | end | |
1746 | ||
1747 | fun filter_inter_list l = | |
1748 | case l of | |
1749 | (t, _, _, _)::r => | |
1750 | if t < epsilon | |
1751 | then filter_inter_list r | |
1752 | else l | |
1753 | | _ => l | |
1754 | ||
1755 | fun hit_from_inter bounded l0 = | |
1756 | let val l = filter_inter_list l0 | |
1757 | in | |
1758 | case l of | |
1759 | [] => false | |
1760 | | (t, _, _, _)::r => (not bounded orelse t <= 1.0) | |
1761 | end | |
1762 | ||
1763 | fun hit(orig, dir, scene, bounded) = | |
1764 | case scene of | |
1765 | SObj (kind, _, m) => | |
1766 | (case | |
1767 | (case kind of | |
1768 | SSphere (x, r2) => sphere (orig, dir, scene, x, r2) | |
1769 | | SEllips => ellipsoid (orig, dir, scene, m) | |
1770 | | SCube _ => cube (orig, dir, scene, m) | |
1771 | | SCylind _ => cylinder (orig, dir, scene, m) | |
1772 | | SCone _ => cone (orig, dir, scene, m) | |
1773 | | SPlane (eq, _) => plane (orig, dir, scene, eq)) of | |
1774 | [] => false | |
1775 | | [(t, _, _, _)] => | |
1776 | if bounded andalso t > 1.0 | |
1777 | then false | |
1778 | else if t < epsilon | |
1779 | then false | |
1780 | else true | |
1781 | | _ => true) | |
1782 | | SBound (sc, x, r2) => | |
1783 | intersect (orig, dir, x, r2) andalso hit (orig, dir, sc, bounded) | |
1784 | | SUnion (sc1, sc2) => | |
1785 | hit (orig, dir, sc1, bounded) orelse hit (orig, dir, sc2, bounded) | |
1786 | | SInter (sc1, sc2) => | |
1787 | let val l1 = find_all (orig, dir, sc1) | |
1788 | in | |
1789 | case l1 of | |
1790 | [] => false | |
1791 | | _ => hit_from_inter bounded (inter(l1, find_all (orig, dir, sc2))) | |
1792 | end | |
1793 | | SDiff (sc1, sc2) => | |
1794 | let | |
1795 | val l1 = find_all(orig, dir, sc1) | |
1796 | in | |
1797 | case l1 of | |
1798 | [] => false | |
1799 | | _ => hit_from_inter bounded (diff(l1, find_all(orig, dir, sc2))) | |
1800 | end | |
1801 | ||
1802 | fun visible (desc: desc, orig, dir, bounded) = | |
1803 | not (hit(orig, dir, #scene desc, bounded)) | |
1804 | ||
1805 | val black = (0.0, 0.0, 0.0) | |
1806 | ||
1807 | val apply : ((Program.v * Program.v list) -> Program.v list) ref = | |
1808 | ref (fn _ => raise(Fail "assert false")) | |
1809 | val inline_closure : (Program.v -> Program.v) ref = | |
1810 | ref (fn _ => raise(Fail "assert false")) | |
1811 | ||
1812 | (* Value between 0 and 1 from the sinus and cosinus *) | |
1813 | (* Actually, only the sign of the sinus is used *) | |
1814 | fun angle (si, co) = | |
1815 | let | |
1816 | val u = dacos co / 360.0 | |
1817 | in | |
1818 | if si > 0.0 then u else 1.0 - u | |
1819 | end | |
1820 | ||
1821 | (* XXX Check that 0 <= u,v <= 1 *) | |
1822 | fun texture_coord (kind, x: v) = (* section 3.6 *) (* ES: checked *) | |
1823 | let | |
1824 | fun ellipsOrSphere() = | |
1825 | let | |
1826 | val y = #2 x | |
1827 | val v = (y + 1.0) * 0.5 | |
1828 | in | |
1829 | if v < epsilon | |
1830 | then [VFloat v, VFloat 0.0, VInt 0] | |
1831 | else | |
1832 | let | |
1833 | val u = angle (#1 x, #3 x / sqrt (1.0 - y * y)) | |
1834 | in | |
1835 | [VFloat v, VFloat u, VInt 0] | |
1836 | end | |
1837 | end | |
1838 | in (* [v; u; face] *) | |
1839 | case kind of | |
1840 | SEllips => ellipsOrSphere() | |
1841 | | SSphere _ => ellipsOrSphere() | |
1842 | | SCube _ => | |
1843 | if abs_float (#3 x) < epsilon then | |
1844 | [VFloat (#2 x), VFloat (#1 x), VInt 0] | |
1845 | else if abs_float ((#3 x) - 1.0) < epsilon then | |
1846 | [VFloat (#2 x), VFloat (#1 x), VInt 1] | |
1847 | else if abs_float (#1 x) < epsilon then | |
1848 | [VFloat (#2 x), VFloat (#3 x), VInt 2] | |
1849 | else if abs_float ((#1 x) - 1.0) < epsilon then | |
1850 | [VFloat (#2 x), VFloat (#3 x), VInt 3] | |
1851 | else if abs_float ((#2 x) - 1.0) < epsilon then | |
1852 | [VFloat (#3 x), VFloat (#1 x), VInt 4] | |
1853 | else (* if abs_float (#2 x) < epsilon then *) | |
1854 | [VFloat (#3 x), VFloat (#1 x), VInt 5] | |
1855 | | SCylind _ => | |
1856 | if abs_float (#2 x) < epsilon then | |
1857 | [VFloat (((#3 x) + 1.0) * 0.5), VFloat (((#1 x) + 1.0) * 0.5), VInt 2] | |
1858 | else if abs_float ((#2 x) - 1.0) < epsilon then | |
1859 | [VFloat (((#3 x) + 1.0) * 0.5), VFloat (((#1 x) + 1.0) * 0.5), VInt 1] | |
1860 | else | |
1861 | let | |
1862 | val u = angle (#1 x, #3 x) | |
1863 | in | |
1864 | [VFloat (#2 x), VFloat u, VInt 0] | |
1865 | end | |
1866 | | SCone _ => | |
1867 | let val v = (#2 x) | |
1868 | in | |
1869 | if abs_float v < epsilon then | |
1870 | [VFloat v, VFloat 0.0, VInt 0] | |
1871 | else | |
1872 | if abs_float ((#2 x) - 1.0) < epsilon | |
1873 | then | |
1874 | [VFloat (((#3 x) + 1.0) * 0.5), | |
1875 | VFloat (((#1 x) + 1.0) * 0.5), | |
1876 | VInt 1] | |
1877 | else | |
1878 | let | |
1879 | val u = angle (#1 x, (#3 x) / v) | |
1880 | in | |
1881 | [VFloat v, VFloat u, VInt 0] | |
1882 | end | |
1883 | end | |
1884 | | SPlane _ => | |
1885 | [VFloat (#3 x), VFloat (#1 x), VInt 0] | |
1886 | end | |
1887 | ||
1888 | fun normal (kind, m, x', x) = | |
1889 | case kind of | |
1890 | SSphere (x0, _) => | |
1891 | normalize (sub (x, x0)) | |
1892 | | SEllips => | |
1893 | let val (n0, n1, n2, _) = vmul (transpose m, x') | |
1894 | in | |
1895 | normalize(n0, n1, n2, 0.0) | |
1896 | end | |
1897 | | SCylind n => | |
1898 | if abs_float (#2 x') < epsilon | |
1899 | orelse abs_float (#2 x') - 1.0 < epsilon then | |
1900 | n | |
1901 | else | |
1902 | (* XXX Could be optimized... *) | |
1903 | let | |
1904 | val (n0, n1, n2, _) = vmul (transpose m, (#1 x', 0.0, #3 x', 0.0)) | |
1905 | in | |
1906 | normalize(n0, n1, n2, 0.0) | |
1907 | end | |
1908 | | SCone n => | |
1909 | if abs_float (#2 x') - 1.0 < epsilon | |
1910 | then n | |
1911 | else | |
1912 | let | |
1913 | val (n0, n1, n2, _) = | |
1914 | vmul (transpose m, (#1 x', ~(#2 x'), #3 x', 0.0)) | |
1915 | in | |
1916 | normalize(n0, n1, n2, 0.0) | |
1917 | end | |
1918 | | SCube (nx, ny, nz) => | |
1919 | if abs_float (#3 x') < epsilon | |
1920 | orelse abs_float (#3 x') - 1.0 < epsilon | |
1921 | then nz | |
1922 | else if abs_float (#1 x') < epsilon | |
1923 | orelse abs_float (#1 x') - 1.0 < epsilon | |
1924 | then nx | |
1925 | else ny | |
1926 | | SPlane (_, n) => | |
1927 | n | |
1928 | ||
1929 | fun apply_surface_fun (f, v) = | |
1930 | case !apply(f, v) of | |
1931 | [VFloat n, VFloat ks, VFloat kd, | |
1932 | VPoint (VFloat cr, VFloat cg, VFloat cb)] => | |
1933 | (n, ks, kd, cr, cg, cb) | |
1934 | | _ => | |
1935 | failwith "A surface function returns some incorrect values" | |
1936 | ||
1937 | fun trace (desc: desc, depth: int, orig, dir) = | |
1938 | let | |
1939 | val dir = normalize dir | |
1940 | in | |
1941 | case filter_inter_list (find_all(orig, dir, #scene desc)) of | |
1942 | [] => black | |
1943 | | (t, ob, _, _) :: _ => trace_2(desc, depth, orig, dir, t, ob) | |
1944 | end | |
1945 | ||
1946 | and trace_2 (desc, depth: int, orig, dir, t, obj) = | |
1947 | let | |
1948 | val x = add_scaled (orig, t, dir) | |
1949 | in | |
1950 | case obj of | |
1951 | SObj (kind, f, m) => | |
1952 | let | |
1953 | val x' = vmul (m, x) | |
1954 | val (n, ks, kd, cr, cg, cb) = | |
1955 | (case !f of | |
1956 | Unopt g => | |
1957 | (* First we check whether the function would fail *) | |
1958 | let | |
1959 | val res = apply_surface_fun(g, texture_coord(kind, x')) | |
1960 | fun stuck() = f := Opt (!inline_closure g) | |
1961 | in | |
1962 | (* Then, we check whether it is a constant function *) | |
1963 | ((ignore (apply_surface_fun(g, | |
1964 | [VInt 0, VInt 0, VFloat 0.0])) | |
1965 | ; f := Cst res) | |
1966 | handle Stuck_computation _ => stuck() | |
1967 | | Stuck_computation' => stuck()) | |
1968 | ; res | |
1969 | end | |
1970 | | Opt g => | |
1971 | apply_surface_fun (g, texture_coord (kind, x')) | |
1972 | | Cst res => | |
1973 | res) | |
1974 | val nm = normal (kind, m, x', x) | |
1975 | val p = prod (dir, nm) | |
1976 | val nm = if p > 0.0 then neg nm else nm | |
1977 | val p = ~(abs_float p) | |
1978 | (* Ambient composant *) | |
1979 | val (ar, ag, ab) = #amb desc | |
1980 | val r = ref (kd * ar) | |
1981 | val g = ref (kd * ag) | |
1982 | val b = ref (kd * ab) | |
1983 | (* Lights *) | |
1984 | val lights = #lights desc | |
1985 | val _ = | |
1986 | for(0, Array.length lights - 1, fn i => | |
1987 | case (Array.sub(lights, i)) of | |
1988 | Light (ldir, (lr, lg, lb)) => | |
1989 | let | |
1990 | val p' = prod (ldir, nm) | |
1991 | in | |
1992 | if p' > 0.0 andalso visible (desc, x, ldir, false) | |
1993 | then | |
1994 | let | |
1995 | val int = | |
1996 | if ks > epsilon then | |
1997 | kd * p' + | |
1998 | ks * prod (normalize | |
1999 | (sub (ldir, dir)), | |
2000 | nm) ** n | |
2001 | else | |
2002 | kd * p' | |
2003 | in | |
2004 | r := !r + int * lr; | |
2005 | g := !g + int * lg; | |
2006 | b := !b + int * lb | |
2007 | end | |
2008 | else () | |
2009 | end | |
2010 | | PtLight (src, (lr, lg, lb)) => | |
2011 | let | |
2012 | val ldir = sub (src, x) | |
2013 | val ldir' = normalize ldir | |
2014 | val p' = prod (ldir', nm) | |
2015 | in | |
2016 | if p' > 0.0 andalso visible(desc, x, ldir, true) | |
2017 | then | |
2018 | let | |
2019 | val int = | |
2020 | if ks > epsilon | |
2021 | then | |
2022 | kd * p' + | |
2023 | ks * prod (normalize (sub (ldir', dir)), | |
2024 | nm) ** n | |
2025 | else | |
2026 | kd * p' | |
2027 | val int = 100.0 * int / (99.0 + square ldir) | |
2028 | in | |
2029 | r := !r + int * lr; | |
2030 | g := !g + int * lg; | |
2031 | b := !b + int * lb | |
2032 | end | |
2033 | else () | |
2034 | end | |
2035 | | StLight (src, maindir, (lr, lg, lb), cutoff, exp) => | |
2036 | let | |
2037 | val ldir = sub (src, x) | |
2038 | val ldir' = normalize ldir | |
2039 | val p' = prod (ldir', nm) | |
2040 | val p'' = prod (ldir', maindir) | |
2041 | in | |
2042 | if p' > 0.0 andalso p'' > cutoff | |
2043 | andalso visible(desc, x, ldir, true) | |
2044 | then | |
2045 | let | |
2046 | val int = | |
2047 | if ks > epsilon | |
2048 | then | |
2049 | kd * p' + | |
2050 | ks * prod (normalize (sub(ldir', dir)), | |
2051 | nm) ** n | |
2052 | else | |
2053 | kd * p' | |
2054 | val int = | |
2055 | 100.0 * int / (99.0 + square ldir) * | |
2056 | (p'' ** exp) | |
2057 | in | |
2058 | r := !r + int * lr; | |
2059 | g := !g + int * lg; | |
2060 | b := !b + int * lb | |
2061 | end | |
2062 | else () | |
2063 | end) | |
2064 | val _ = | |
2065 | (* Reflexion *) | |
2066 | if ks > epsilon andalso depth > 0 | |
2067 | then | |
2068 | let | |
2069 | val dir' = add_scaled (dir, ~2.0 * p, nm) | |
2070 | val (r', g', b') = trace(desc, depth - 1, x, dir') | |
2071 | in | |
2072 | r := !r + ks * r'; | |
2073 | g := !g + ks * g'; | |
2074 | b := !b + ks * b' | |
2075 | end | |
2076 | else () | |
2077 | in (!r * cr, !g * cg, !b * cb) | |
2078 | end | |
2079 | | _ => raise(Fail "assert false") | |
2080 | end | |
2081 | ||
2082 | fun conv c : int = | |
2083 | let | |
2084 | val i = truncate (c * 256.0) | |
2085 | in | |
2086 | if i < 0 then 0 else | |
2087 | if i >= 256 then 255 else | |
2088 | i | |
2089 | end | |
2090 | ||
2091 | fun f (amb, lights, obj, depth: int, fov, wid, ht, file) = | |
2092 | let | |
2093 | val scene = intern_obj(Matrix.identity, Matrix.identity, 1.0, true, obj) | |
2094 | val scene = optimize scene | |
2095 | val img = Ppm.init (wid, ht) | |
2096 | val orig = ( 0.0, 0.0, ~1.0, 1.0 ) | |
2097 | val width = 2.0 * dtan (0.5 * fov) | |
2098 | val delta = width / float wid | |
2099 | val x0 = ~ width / 2.0 | |
2100 | val y0 = delta * float ht / 2.0 | |
2101 | val desc = { amb = amb, lights = intern_lights lights, scene = scene } | |
2102 | in | |
2103 | for(0, ht - 1, fn j => | |
2104 | for(0, wid - 1, fn i => | |
2105 | let | |
2106 | val dir = | |
2107 | (x0 + (float i + 0.5) * delta, | |
2108 | y0 - (float j + 0.5) * delta, | |
2109 | 1.0, | |
2110 | 0.0) | |
2111 | val (r, g, b) = trace(desc, depth, orig, dir) | |
2112 | in | |
2113 | Ppm.setp (img, i, j, conv r, conv g, conv b) | |
2114 | end)) | |
2115 | ; Ppm.dump (file, img) | |
2116 | end | |
2117 | ||
2118 | end | |
2119 | signature EVAL = | |
2120 | sig | |
2121 | val f : Program.t list -> unit | |
2122 | end | |
2123 | structure Eval: EVAL = | |
2124 | struct | |
2125 | ||
2126 | open Caml | |
2127 | open Program | |
2128 | ||
2129 | val rtd = 180.0 / acos (~1.0) | |
2130 | val dtr = acos (~1.0) / 180.0 | |
2131 | fun deg x = rtd * x | |
2132 | fun rad x = dtr * x | |
2133 | val zero = VFloat 0.0 | |
2134 | val one = VFloat 1.0 | |
2135 | ||
2136 | fun lookup (env, s) : int = | |
2137 | case env of | |
2138 | [] => failwith ("Unbound variable \"" ^ s ^ "\"") | |
2139 | | s' :: env' => | |
2140 | if s = s' | |
2141 | then 0 | |
2142 | else 1 + (lookup(env', s)) | |
2143 | ||
2144 | (* XXX embed values *) | |
2145 | fun conv (absenv, p) = | |
2146 | case p of | |
2147 | [] => [] | |
2148 | | Float x :: Float y :: Float z :: Prim Point :: r => | |
2149 | Val' (VPoint (VFloat x, VFloat y, VFloat z)) :: conv(absenv, r) | |
2150 | | t :: r => | |
2151 | (case t of | |
2152 | Fun p' => Fun' (conv(absenv, p')) :: conv(absenv, r) | |
2153 | | Arr p' => Arr' (conv(absenv, p')) :: conv(absenv, r) | |
2154 | | Ident s => Ident' (lookup(absenv, s)) :: conv(absenv, r) | |
2155 | | Binder s => Binder' :: conv (s :: absenv, r) | |
2156 | | Int i => Val' (VInt i) :: conv(absenv, r) | |
2157 | | Float f => Val' (VFloat f) :: conv(absenv, r) | |
2158 | | Bool b => Val' (VBool b) :: conv(absenv, r) | |
2159 | | String s => Val' (VStr s) :: conv(absenv, r) | |
2160 | | Prim k => Prim' k :: conv(absenv, r)) | |
2161 | ||
2162 | fun inline (offset, env, p) = | |
2163 | case p of | |
2164 | [] => [] | |
2165 | | t :: r => | |
2166 | let | |
2167 | fun normal() = t :: inline(offset, env, r) | |
2168 | in case t of | |
2169 | Fun' p' => Fun' (inline(offset, env, p')) :: inline(offset, env, r) | |
2170 | | Arr' p' => Arr' (inline(offset, env, p')) :: inline(offset, env, r) | |
2171 | | Ident' i => | |
2172 | if i >= offset | |
2173 | then Val' (List.nth (env, i - offset)) :: inline(offset, env, r) | |
2174 | else normal() | |
2175 | | Binder' => Binder' :: inline (1 + offset, env, r) | |
2176 | | Prim' _ => normal() | |
2177 | | Val' _ => normal() | |
2178 | end | |
2179 | ||
2180 | val inline_closure = | |
2181 | fn (VClos (env, p)) => VClos ([], inline(0, env, p)) | |
2182 | | _ => failwith "a surface function was actually not a function" | |
2183 | ||
2184 | val _ = Render.inline_closure := inline_closure | |
2185 | ||
2186 | fun eval (env, st, p) = | |
2187 | case (st, p) of | |
2188 | (* inlined value *) | |
2189 | (_, Val' v :: r) => eval(env, (v :: st), r) | |
2190 | (* Rule 1 *) | |
2191 | (* Rule 2 *) | |
2192 | | (v::st', Binder' :: r) => eval((v :: env), st', r) | |
2193 | (* Rule 3 *) | |
2194 | | (_, Ident' i :: r) => | |
2195 | let val v = List.nth(env, i) | |
2196 | in eval(env, (v :: st), r) | |
2197 | end | |
2198 | (* Rule 4 *) | |
2199 | | (_, Fun' f :: r) => eval(env, (VClos (env, f) :: st), r) | |
2200 | (* Rule 5 *) | |
2201 | | (VClos (env', f) :: st', Prim' Apply :: r) => | |
2202 | eval(env, eval(env', st', f), r) | |
2203 | (* Rule 6 *) | |
2204 | | (_, Arr' a :: r) => | |
2205 | eval(env, (VArr (Array.of_list (List.rev (eval(env, [], a))))) :: st, r) | |
2206 | (* Rules 7 and 8 *) | |
2207 | | (VClos _ :: VClos (env', iftrue) :: VBool true :: st', Prim' If :: r) => | |
2208 | eval(env, eval(env', st', iftrue), r) | |
2209 | | (VClos (env', iffalse) :: VClos _ :: VBool false :: st', Prim' If :: r) => | |
2210 | eval(env, eval(env', st', iffalse), r) | |
2211 | (* Operations on numbers *) | |
2212 | | (VInt n2 :: VInt n1 :: st', Prim' Addi :: r) => | |
2213 | eval(env, (VInt (n1 + n2) :: st'), r) | |
2214 | | (VFloat f2 :: VFloat f1 :: st', Prim' Addf :: r) => | |
2215 | eval(env, (VFloat (f1 + f2) :: st'), r) | |
2216 | | (VFloat f :: st', Prim' Acos :: r) => | |
2217 | eval(env, (VFloat (deg (acos f)) :: st'), r) | |
2218 | | (VFloat f :: st', Prim' Asin :: r) => | |
2219 | eval(env, (VFloat (deg (asin f)) :: st'), r) | |
2220 | | ((vf as VFloat f):: st', Prim' Clampf :: r) => | |
2221 | let val f' = if f < 0.0 then zero else if f > 1.0 then one else vf | |
2222 | in eval(env, (f' :: st'), r) | |
2223 | end | |
2224 | | (VFloat f :: st', Prim' Cos :: r) => | |
2225 | eval(env, (VFloat (cos (rad f)) :: st'), r) | |
2226 | | (VInt n2 :: VInt n1 :: st', Prim' Divi :: r) => | |
2227 | eval(env, (VInt (n1 div n2) :: st'), r) | |
2228 | | (VFloat f2 :: VFloat f1 :: st', Prim' Divf :: r) => | |
2229 | eval(env, (VFloat (f1 / f2) :: st'), r) | |
2230 | | (VInt n2 :: VInt n1 :: st', Prim' Eqi :: r) => | |
2231 | eval(env, (VBool (n1 = n2) :: st'), r) | |
2232 | | (VFloat f2 :: VFloat f1 :: st', Prim' Eqf :: r) => | |
2233 | eval(env, (VBool (Real.==(f1, f2)) :: st'), r) | |
2234 | | (VFloat f :: st', Prim' Floor :: r) => | |
2235 | eval(env, (VInt (Real.floor f) :: st'), r) | |
2236 | | (VFloat f :: st', Prim' Frac :: r) => | |
2237 | eval(env, (VFloat (Real.realMod f) :: st'), r) | |
2238 | | (VInt n2 :: VInt n1 :: st', Prim' Lessi :: r) => | |
2239 | eval(env, (VBool (n1 < n2) :: st'), r) | |
2240 | | (VFloat f2 :: VFloat f1 :: st', Prim' Lessf :: r) => | |
2241 | eval(env, (VBool (f1 < f2) :: st'), r) | |
2242 | | (VInt n2 :: VInt n1 :: st', Prim' Modi :: r) => | |
2243 | eval(env, (VInt (n1 mod n2) :: st'), r) | |
2244 | | (VInt n2 :: VInt n1 :: st', Prim' Muli :: r) => | |
2245 | eval(env, (VInt (n1 * n2) :: st'), r) | |
2246 | | (VFloat f2 :: VFloat f1 :: st', Prim' Mulf :: r) => | |
2247 | eval(env, (VFloat (f1 * f2) :: st'), r) | |
2248 | | (VInt n :: st', Prim' Negi :: r) => eval(env, (VInt (~ n) :: st'), r) | |
2249 | | (VFloat f :: st', Prim' Negf :: r) => eval(env, (VFloat (~ f) :: st'), r) | |
2250 | | (VInt n :: st', Prim' Real :: r) => eval(env, (VFloat (float n) :: st'), r) | |
2251 | | (VFloat f :: st', Prim' Sin :: r) => eval(env, (VFloat (sin (rad f)) :: st'), r) | |
2252 | | (VFloat f :: st', Prim' Sqrt :: r) => eval(env, (VFloat (sqrt f) :: st'), r) | |
2253 | | (VInt n2 :: VInt n1 :: st', Prim' Subi :: r) => eval(env, (VInt (n1 - n2) :: st'), r) | |
2254 | | (VFloat f2 :: VFloat f1 :: st', Prim' Subf :: r) => | |
2255 | eval(env, (VFloat (f1 - f2) :: st'), r) | |
2256 | (* Operations on points *) | |
2257 | | (VPoint (x, _, _) :: st', Prim' Getx :: r ) => eval(env, (x :: st'), r) | |
2258 | | (VPoint (_, y, _) :: st', Prim' Gety :: r ) => eval(env, (y :: st'), r) | |
2259 | | (VPoint (_, _, z) :: st', Prim' Getz :: r ) => eval(env, (z :: st'), r) | |
2260 | | ((z as VFloat _) :: (y as VFloat _) :: (x as VFloat _) :: st', | |
2261 | Prim' Point :: r) => | |
2262 | eval(env, (VPoint (x, y, z) :: st'), r) | |
2263 | | (VInt i :: VArr a :: st', Prim' Get :: r) => | |
2264 | (* if compiled of "-unsafe" *) | |
2265 | if i < 0 orelse i >= Array.length a | |
2266 | then failwith "illegal access beyond array boundary" | |
2267 | else eval(env, (Array.sub(a, i) :: st'), r) | |
2268 | | (VArr a :: st', Prim' Length :: r) => | |
2269 | eval(env, (VInt (Array.length a) :: st'), r) | |
2270 | (* Geometric primitives *) | |
2271 | | ((f as VClos _) :: st', Prim' Sphere :: r ) => | |
2272 | eval(env, (VObj (OObj (OSphere, ref (Unopt f))) :: st'), r) | |
2273 | | ((f as VClos _) :: st', Prim' Cube :: r ) => | |
2274 | eval(env, (VObj (OObj (OCube, ref (Unopt f))) :: st'), r) | |
2275 | | ((f as VClos _) :: st', Prim' Cylinder :: r) => | |
2276 | eval(env, (VObj (OObj (OCylind, ref (Unopt f))) :: st'), r) | |
2277 | | ((f as VClos _) :: st', Prim' Cone :: r ) => | |
2278 | eval(env, (VObj (OObj (OCone, ref (Unopt f))) :: st'), r) | |
2279 | | ((f as VClos _) :: st', Prim' Plane :: r ) => | |
2280 | eval(env, (VObj (OObj (OPlane, ref (Unopt f))) :: st'), r) | |
2281 | (* Transformations *) | |
2282 | | (VFloat z :: VFloat y :: VFloat x :: VObj ob :: st', Prim' Translate :: r) => | |
2283 | eval(env, | |
2284 | (VObj (OTransform (ob, | |
2285 | Matrix.translate (x, y, z), | |
2286 | Matrix.translate (~ x, ~ y, ~ z), | |
2287 | 1.0, true)) :: st'), | |
2288 | r) | |
2289 | | (VFloat z :: VFloat y :: VFloat x :: VObj ob :: st', Prim' Scale :: r) => | |
2290 | eval( env, | |
2291 | (VObj (OTransform (ob, | |
2292 | Matrix.scale (x, y, z), | |
2293 | Matrix.unscale (x, y, z), | |
2294 | Real.max (abs_float x, | |
2295 | (Real.max (abs_float y, abs_float z))), | |
2296 | false)) :: st'), | |
2297 | r) | |
2298 | | (VFloat s :: VObj ob :: st', Prim' Uscale :: r) => | |
2299 | eval(env, | |
2300 | (VObj (OTransform (ob, Matrix.uscale s, Matrix.unuscale s, | |
2301 | abs_float s, true)) :: st'), | |
2302 | r) | |
2303 | | (VFloat t :: VObj ob :: st', Prim' Rotatex :: r) => | |
2304 | eval(env, | |
2305 | (VObj (OTransform (ob, Matrix.rotatex t, Matrix.rotatex (~ t), | |
2306 | 1.0, true)) :: st'), | |
2307 | r) | |
2308 | | (VFloat t :: VObj ob :: st', Prim' Rotatey :: r) => | |
2309 | eval(env, | |
2310 | (VObj (OTransform (ob, Matrix.rotatey t, Matrix.rotatey (~ t), | |
2311 | 1.0, true)) :: st'), | |
2312 | r) | |
2313 | | (VFloat t :: VObj ob :: st', Prim' Rotatez :: r) => | |
2314 | eval(env, | |
2315 | (VObj (OTransform (ob, Matrix.rotatez t, Matrix.rotatez (~ t), | |
2316 | 1.0, true)) :: st'), | |
2317 | r) | |
2318 | (* Lights *) | |
2319 | | ((color as VPoint _) :: (dir as VPoint _) :: st', Prim' Light :: r) => | |
2320 | eval(env, (VLight (dir, color) :: st'), r) | |
2321 | | ((color as VPoint _) :: (pos as VPoint _) :: st', Prim' Pointlight :: r) => | |
2322 | eval(env, (VPtLight (pos, color) :: st'), r) | |
2323 | | ((expon as VFloat _) :: (cutoff as VFloat _) :: (color as VPoint _) :: | |
2324 | (at as VPoint _) :: (pos as VPoint _) :: st', Prim' Spotlight :: r) => | |
2325 | eval(env, (VStLight (pos, at, color, cutoff, expon) :: st'), r) | |
2326 | (* Constructive geometry *) | |
2327 | | ((VObj o2) :: (VObj o1) :: st', Prim' Union :: r) => | |
2328 | eval(env, (VObj (OUnion (o1, o2)) :: st'), r) | |
2329 | | ((VObj o2) :: (VObj o1) :: st', Prim' Intersect :: r) => | |
2330 | eval(env, (VObj (OInter (o1, o2)) :: st'), r) | |
2331 | | ((VObj o2) :: (VObj o1) :: st', Prim' Difference :: r) => | |
2332 | eval(env, (VObj (ODiff (o1, o2)) :: st'), r) | |
2333 | (* Rendering *) | |
2334 | | (VStr file :: VInt ht :: VInt wid :: VFloat fov :: VInt depth :: | |
2335 | VObj obj :: VArr lights :: VPoint (VFloat ax, VFloat ay, VFloat az) :: | |
2336 | st', Prim' Render :: r) => | |
2337 | (* | |
2338 | amb the intensity of ambient light (a point). | |
2339 | lights is an array of lights used to illuminate the scene. | |
2340 | obj is the scene to render. | |
2341 | depth is an integer limit on the recursive depth of the ray tracing. | |
2342 | fov is the horizontal field of view in degrees (a real number). | |
2343 | wid is the width of the rendered image in pixels (an integer). | |
2344 | ht is the height of the rendered image in pixels (an integer). | |
2345 | file is a string specifying output file for the rendered image. | |
2346 | *) | |
2347 | (Render.f ((ax, ay, az), lights, obj, depth, fov, wid, ht, file) | |
2348 | ; eval(env, st', r)) | |
2349 | (* Termination *) | |
2350 | | (_, []) => st | |
2351 | (* Failure *) | |
2352 | | _ => | |
2353 | raise (Stuck_computation (env, st, p)) | |
2354 | ||
2355 | fun apply (f, st) = | |
2356 | case f of | |
2357 | VClos (env, p) => eval(env, st, p) | |
2358 | | _ => raise Fail "assert false" | |
2359 | ||
2360 | val _ = Render.apply := apply | |
2361 | ||
2362 | fun f p = | |
2363 | let | |
2364 | val st = eval([], [], (conv([], p))) | |
2365 | in | |
2366 | case st of | |
2367 | [] => () | |
2368 | | _ => failwith "error" | |
2369 | end handle Stuck_computation (env, st, p) => failwith "stuck" | |
2370 | ||
2371 | end | |
2372 | structure Main = | |
2373 | struct | |
2374 | fun doit () = | |
2375 | Eval.f (Program.read (TextIO.openIn "DATA/chess.gml")) | |
2376 | handle _ => () | |
2377 | ||
2378 | val doit = | |
2379 | fn n => | |
2380 | let | |
2381 | fun loop n = | |
2382 | if n = 0 | |
2383 | then () | |
2384 | else (doit(); | |
2385 | loop(n-1)) | |
2386 | in loop n | |
2387 | end | |
2388 | end |