sergio/takana

1<!DOCTYPE html>
2<head>
3<!--
4 Copyright (C) 2007 Apple Inc.  All rights reserved.
5
6 Redistribution and use in source and binary forms, with or without
7 modification, are permitted provided that the following conditions
8 are met:
9 1. Redistributions of source code must retain the above copyright
10    notice, this list of conditions and the following disclaimer.
11 2. Redistributions in binary form must reproduce the above copyright
12    notice, this list of conditions and the following disclaimer in the
13    documentation and/or other materials provided with the distribution.
14
15 THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY
16 EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
17 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
18 PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE COMPUTER, INC. OR
19 CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
20 EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
21 PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
22 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
23 OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
25 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
26-->
27
28<title>SunSpider 3d-raytrace</title>
29</head>
30
31<body>
32<h3>3d-raytrace</h3>
33<div id="console">
34</div>
35
36<script>
37
38var _sunSpiderStartDate = new Date();
39
40/*
41 * Copyright (C) 2007 Apple Inc.  All rights reserved.
42 *
43 * Redistribution and use in source and binary forms, with or without
44 * modification, are permitted provided that the following conditions
45 * are met:
46 * 1. Redistributions of source code must retain the above copyright
47 *    notice, this list of conditions and the following disclaimer.
48 * 2. Redistributions in binary form must reproduce the above copyright
49 *    notice, this list of conditions and the following disclaimer in the
50 *    documentation and/or other materials provided with the distribution.
51 *
52 * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY
53 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
54 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
55 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE COMPUTER, INC. OR
56 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
57 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
58 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
59 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
60 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
61 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
62 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
63 */
64
65function createVector(x,y,z) {
66    return new Array(x,y,z);
67}
68
69function sqrLengthVector(self) {
70    return self[0] * self[0] + self[1] * self[1] + self[2] * self[2];
71}
72
73function lengthVector(self) {
74    return Math.sqrt(self[0] * self[0] + self[1] * self[1] + self[2] * self[2]);
75}
76
77function addVector(self, v) {
78    self[0] += v[0];
79    self[1] += v[1];
80    self[2] += v[2];
81    return self;
82}
83
84function subVector(self, v) {
85    self[0] -= v[0];
86    self[1] -= v[1];
87    self[2] -= v[2];
88    return self;
89}
90
91function scaleVector(self, scale) {
92    self[0] *= scale;
93    self[1] *= scale;
94    self[2] *= scale;
95    return self;
96}
97
98function normaliseVector(self) {
99    var len = Math.sqrt(self[0] * self[0] + self[1] * self[1] + self[2] * self[2]);
100    self[0] /= len;
101    self[1] /= len;
102    self[2] /= len;
103    return self;
104}
105
106function add(v1, v2) {
107    return new Array(v1[0] + v2[0], v1[1] + v2[1], v1[2] + v2[2]);
108}
109
110function sub(v1, v2) {
111    return new Array(v1[0] - v2[0], v1[1] - v2[1], v1[2] - v2[2]);
112}
113
114function scalev(v1, v2) {
115    return new Array(v1[0] * v2[0], v1[1] * v2[1], v1[2] * v2[2]);
116}
117
118function dot(v1, v2) {
119    return v1[0] * v2[0] + v1[1] * v2[1] + v1[2] * v2[2];
120}
121
122function scale(v, scale) {
123    return [v[0] * scale, v[1] * scale, v[2] * scale];
124}
125
126function cross(v1, v2) {
127    return [v1[1] * v2[2] - v1[2] * v2[1], 
128            v1[2] * v2[0] - v1[0] * v2[2],
129            v1[0] * v2[1] - v1[1] * v2[0]];
130
131}
132
133function normalise(v) {
134    var len = lengthVector(v);
135    return [v[0] / len, v[1] / len, v[2] / len];
136}
137
138function transformMatrix(self, v) {
139    var vals = self;
140    var x  = vals[0] * v[0] + vals[1] * v[1] + vals[2] * v[2] + vals[3];
141    var y  = vals[4] * v[0] + vals[5] * v[1] + vals[6] * v[2] + vals[7];
142    var z  = vals[8] * v[0] + vals[9] * v[1] + vals[10] * v[2] + vals[11];
143    return [x, y, z];
144}
145
146function invertMatrix(self) {
147    var temp = new Array(16);
148    var tx = -self[3];
149    var ty = -self[7];
150    var tz = -self[11];
151    for (h = 0; h < 3; h++) 
152        for (v = 0; v < 3; v++) 
153            temp[h + v * 4] = self[v + h * 4];
154    for (i = 0; i < 11; i++)
155        self[i] = temp[i];
156    self[3] = tx * self[0] + ty * self[1] + tz * self[2];
157    self[7] = tx * self[4] + ty * self[5] + tz * self[6];
158    self[11] = tx * self[8] + ty * self[9] + tz * self[10];
159    return self;
160}
161
162
163// Triangle intersection using barycentric coord method
164function Triangle(p1, p2, p3) {
165    var edge1 = sub(p3, p1);
166    var edge2 = sub(p2, p1);
167    var normal = cross(edge1, edge2);
168    if (Math.abs(normal[0]) > Math.abs(normal[1]))
169        if (Math.abs(normal[0]) > Math.abs(normal[2]))
170            this.axis = 0; 
171        else 
172            this.axis = 2;
173    else
174        if (Math.abs(normal[1]) > Math.abs(normal[2])) 
175            this.axis = 1;
176        else 
177            this.axis = 2;
178    var u = (this.axis + 1) % 3;
179    var v = (this.axis + 2) % 3;
180    var u1 = edge1[u];
181    var v1 = edge1[v];
182    
183    var u2 = edge2[u];
184    var v2 = edge2[v];
185    this.normal = normalise(normal);
186    this.nu = normal[u] / normal[this.axis];
187    this.nv = normal[v] / normal[this.axis];
188    this.nd = dot(normal, p1) / normal[this.axis];
189    var det = u1 * v2 - v1 * u2;
190    this.eu = p1[u];
191    this.ev = p1[v]; 
192    this.nu1 = u1 / det;
193    this.nv1 = -v1 / det;
194    this.nu2 = v2 / det;
195    this.nv2 = -u2 / det; 
196    this.material = [0.7, 0.7, 0.7];
197}
198
199Triangle.prototype.intersect = function(orig, dir, near, far) {
200    var u = (this.axis + 1) % 3;
201    var v = (this.axis + 2) % 3;
202    var d = dir[this.axis] + this.nu * dir[u] + this.nv * dir[v];
203    var t = (this.nd - orig[this.axis] - this.nu * orig[u] - this.nv * orig[v]) / d;
204    if (t < near || t > far)
205        return null;
206    var Pu = orig[u] + t * dir[u] - this.eu;
207    var Pv = orig[v] + t * dir[v] - this.ev;
208    var a2 = Pv * this.nu1 + Pu * this.nv1;
209    if (a2 < 0) 
210        return null;
211    var a3 = Pu * this.nu2 + Pv * this.nv2;
212    if (a3 < 0) 
213        return null;
214
215    if ((a2 + a3) > 1) 
216        return null;
217    return t;
218}
219
220function Scene(a_triangles) {
221    this.triangles = a_triangles;
222    this.lights = [];
223    this.ambient = [0,0,0];
224    this.background = [0.8,0.8,1];
225}
226var zero = new Array(0,0,0);
227
228Scene.prototype.intersect = function(origin, dir, near, far) {
229    var closest = null;
230    for (i = 0; i < this.triangles.length; i++) {
231        var triangle = this.triangles[i];   
232        var d = triangle.intersect(origin, dir, near, far);
233        if (d == null || d > far || d < near)
234            continue;
235        far = d;
236        closest = triangle;
237    }
238    
239    if (!closest)
240        return [this.background[0],this.background[1],this.background[2]];
241        
242    var normal = closest.normal;
243    var hit = add(origin, scale(dir, far)); 
244    if (dot(dir, normal) > 0)
245        normal = [-normal[0], -normal[1], -normal[2]];
246    
247    var colour = null;
248    if (closest.shader) {
249        colour = closest.shader(closest, hit, dir);
250    } else {
251        colour = closest.material;
252    }
253    
254    // do reflection
255    var reflected = null;
256    if (colour.reflection > 0.001) {
257        var reflection = addVector(scale(normal, -2*dot(dir, normal)), dir);
258        reflected = this.intersect(hit, reflection, 0.0001, 1000000);
259        if (colour.reflection >= 0.999999)
260            return reflected;
261    }
262    
263    var l = [this.ambient[0], this.ambient[1], this.ambient[2]];
264    for (var i = 0; i < this.lights.length; i++) {
265        var light = this.lights[i];
266        var toLight = sub(light, hit);
267        var distance = lengthVector(toLight);
268        scaleVector(toLight, 1.0/distance);
269        distance -= 0.0001;
270        if (this.blocked(hit, toLight, distance))
271            continue;
272        var nl = dot(normal, toLight);
273        if (nl > 0)
274            addVector(l, scale(light.colour, nl));
275    }
276    l = scalev(l, colour);
277    if (reflected) {
278        l = addVector(scaleVector(l, 1 - colour.reflection), scaleVector(reflected, colour.reflection));
279    }
280    return l;
281}
282
283Scene.prototype.blocked = function(O, D, far) {
284    var near = 0.0001;
285    var closest = null;
286    for (i = 0; i < this.triangles.length; i++) {
287        var triangle = this.triangles[i];   
288        var d = triangle.intersect(O, D, near, far);
289        if (d == null || d > far || d < near)
290            continue;
291        return true;
292    }
293    
294    return false;
295}
296
297
298// this camera code is from notes i made ages ago, it is from *somewhere* -- i cannot remember where
299// that somewhere is
300function Camera(origin, lookat, up) {
301    var zaxis = normaliseVector(subVector(lookat, origin));
302    var xaxis = normaliseVector(cross(up, zaxis));
303    var yaxis = normaliseVector(cross(xaxis, subVector([0,0,0], zaxis)));
304    var m = new Array(16);
305    m[0] = xaxis[0]; m[1] = xaxis[1]; m[2] = xaxis[2];
306    m[4] = yaxis[0]; m[5] = yaxis[1]; m[6] = yaxis[2];
307    m[8] = zaxis[0]; m[9] = zaxis[1]; m[10] = zaxis[2];
308    invertMatrix(m);
309    m[3] = 0; m[7] = 0; m[11] = 0;
310    this.origin = origin;
311    this.directions = new Array(4);
312    this.directions[0] = normalise([-0.7,  0.7, 1]);
313    this.directions[1] = normalise([ 0.7,  0.7, 1]);
314    this.directions[2] = normalise([ 0.7, -0.7, 1]);
315    this.directions[3] = normalise([-0.7, -0.7, 1]);
316    this.directions[0] = transformMatrix(m, this.directions[0]);
317    this.directions[1] = transformMatrix(m, this.directions[1]);
318    this.directions[2] = transformMatrix(m, this.directions[2]);
319    this.directions[3] = transformMatrix(m, this.directions[3]);
320}
321
322Camera.prototype.generateRayPair = function(y) {
323    rays = new Array(new Object(), new Object());
324    rays[0].origin = this.origin;
325    rays[1].origin = this.origin;
326    rays[0].dir = addVector(scale(this.directions[0], y), scale(this.directions[3], 1 - y));
327    rays[1].dir = addVector(scale(this.directions[1], y), scale(this.directions[2], 1 - y));
328    return rays;
329}
330
331function renderRows(camera, scene, pixels, width, height, starty, stopy) {
332    for (var y = starty; y < stopy; y++) {
333        var rays = camera.generateRayPair(y / height);
334        for (var x = 0; x < width; x++) {
335            var xp = x / width;
336            var origin = addVector(scale(rays[0].origin, xp), scale(rays[1].origin, 1 - xp));
337            var dir = normaliseVector(addVector(scale(rays[0].dir, xp), scale(rays[1].dir, 1 - xp)));
338            var l = scene.intersect(origin, dir);
339            pixels[y][x] = l;
340        }
341    }
342}
343
344Camera.prototype.render = function(scene, pixels, width, height) {
345    var cam = this;
346    var row = 0;
347    renderRows(cam, scene, pixels, width, height, 0, height);
348}
349
350
351
352function raytraceScene()
353{
354    var startDate = new Date().getTime();
355    var numTriangles = 2 * 6;
356    var triangles = new Array();//numTriangles);
357    var tfl = createVector(-10,  10, -10);
358    var tfr = createVector( 10,  10, -10);
359    var tbl = createVector(-10,  10,  10);
360    var tbr = createVector( 10,  10,  10);
361    var bfl = createVector(-10, -10, -10);
362    var bfr = createVector( 10, -10, -10);
363    var bbl = createVector(-10, -10,  10);
364    var bbr = createVector( 10, -10,  10);
365    
366    // cube!!!
367    // front
368    var i = 0;
369    
370    triangles[i++] = new Triangle(tfl, tfr, bfr);
371    triangles[i++] = new Triangle(tfl, bfr, bfl);
372    // back
373    triangles[i++] = new Triangle(tbl, tbr, bbr);
374    triangles[i++] = new Triangle(tbl, bbr, bbl);
375    //        triangles[i-1].material = [0.7,0.2,0.2];
376    //            triangles[i-1].material.reflection = 0.8;
377    // left
378    triangles[i++] = new Triangle(tbl, tfl, bbl);
379    //            triangles[i-1].reflection = 0.6;
380    triangles[i++] = new Triangle(tfl, bfl, bbl);
381    //            triangles[i-1].reflection = 0.6;
382    // right
383    triangles[i++] = new Triangle(tbr, tfr, bbr);
384    triangles[i++] = new Triangle(tfr, bfr, bbr);
385    // top
386    triangles[i++] = new Triangle(tbl, tbr, tfr);
387    triangles[i++] = new Triangle(tbl, tfr, tfl);
388    // bottom
389    triangles[i++] = new Triangle(bbl, bbr, bfr);
390    triangles[i++] = new Triangle(bbl, bfr, bfl);
391    
392    //Floor!!!!
393    var green = createVector(0.0, 0.4, 0.0);
394    var grey = createVector(0.4, 0.4, 0.4);
395    grey.reflection = 1.0;
396    var floorShader = function(tri, pos, view) {
397        var x = ((pos[0]/32) % 2 + 2) % 2;
398        var z = ((pos[2]/32 + 0.3) % 2 + 2) % 2;
399        if (x < 1 != z < 1) {
400            //in the real world we use the fresnel term...
401            //    var angle = 1-dot(view, tri.normal);
402            //   angle *= angle;
403            //  angle *= angle;
404            // angle *= angle;
405            //grey.reflection = angle;
406            return grey;
407        } else 
408            return green;
409    }
410    var ffl = createVector(-1000, -30, -1000);
411    var ffr = createVector( 1000, -30, -1000);
412    var fbl = createVector(-1000, -30,  1000);
413    var fbr = createVector( 1000, -30,  1000);
414    triangles[i++] = new Triangle(fbl, fbr, ffr);
415    triangles[i-1].shader = floorShader;
416    triangles[i++] = new Triangle(fbl, ffr, ffl);
417    triangles[i-1].shader = floorShader;
418    
419    var _scene = new Scene(triangles);
420    _scene.lights[0] = createVector(20, 38, -22);
421    _scene.lights[0].colour = createVector(0.7, 0.3, 0.3);
422    _scene.lights[1] = createVector(-23, 40, 17);
423    _scene.lights[1].colour = createVector(0.7, 0.3, 0.3);
424    _scene.lights[2] = createVector(23, 20, 17);
425    _scene.lights[2].colour = createVector(0.7, 0.7, 0.7);
426    _scene.ambient = createVector(0.1, 0.1, 0.1);
427    //  _scene.background = createVector(0.7, 0.7, 1.0);
428    
429    var size = 30;
430    var pixels = new Array();
431    for (var y = 0; y < size; y++) {
432        pixels[y] = new Array();
433        for (var x = 0; x < size; x++) {
434            pixels[y][x] = 0;
435        }
436    }
437
438    var _camera = new Camera(createVector(-40, 40, 40), createVector(0, 0, 0), createVector(0, 1, 0));
439    _camera.render(_scene, pixels, size, size);
440
441    return pixels;
442}
443
444function arrayToCanvasCommands(pixels)
445{
446    var s = '<canvas id="renderCanvas" width="30px" height="30px"></canvas><scr' + 'ipt>\nvar pixels = [';
447    var size = 30;
448    for (var y = 0; y < size; y++) {
449        s += "[";
450        for (var x = 0; x < size; x++) {
451            s += "[" + pixels[y][x] + "],";
452        }
453        s+= "],";
454    }
455    s += '];\n    var canvas = document.getElementById("renderCanvas").getContext("2d");\n\
456\n\
457\n\
458    var size = 30;\n\
459    canvas.fillStyle = "red";\n\
460    canvas.fillRect(0, 0, size, size);\n\
461    canvas.scale(1, -1);\n\
462    canvas.translate(0, -size);\n\
463\n\
464    if (!canvas.setFillColor)\n\
465        canvas.setFillColor = function(r, g, b, a) {\n\
466            this.fillStyle = "rgb("+[Math.floor(r * 255), Math.floor(g * 255), Math.floor(b * 255)]+")";\n\
467    }\n\
468\n\
469for (var y = 0; y < size; y++) {\n\
470  for (var x = 0; x < size; x++) {\n\
471    var l = pixels[y][x];\n\
472    canvas.setFillColor(l[0], l[1], l[2], 1);\n\
473    canvas.fillRect(x, y, 1, 1);\n\
474  }\n\
475}</scr' + 'ipt>';
476
477    return s;
478}
479
480testOutput = arrayToCanvasCommands(raytraceScene());
481
482
483var _sunSpiderInterval = new Date() - _sunSpiderStartDate;
484
485document.getElementById("console").innerHTML = _sunSpiderInterval;
486</script>
487
488
489</body>
490</html>