1 /*

     2  * Copyright (C) 2007 Apple Inc.  All rights reserved.

     3  *

     4  * Redistribution and use in source and binary forms, with or without

     5  * modification, are permitted provided that the following conditions

     6  * are met:

     7  * 1. Redistributions of source code must retain the above copyright

     8  *    notice, this list of conditions and the following disclaimer.

     9  * 2. Redistributions in binary form must reproduce the above copyright

    10  *    notice, this list of conditions and the following disclaimer in the

    11  *    documentation and/or other materials provided with the distribution.

    12  *

    13  * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY

    14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE

    15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR

    16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE COMPUTER, INC. OR

    17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,

    18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,

    19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR

    20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY

    21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT

    22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE

    23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 

    24  */

    25 

    26 function createVector(x,y,z) {

    27     return new Array(x,y,z);

    28 }

    29 

    30 function sqrLengthVector(self) {

    31     return self[0] * self[0] + self[1] * self[1] + self[2] * self[2];

    32 }

    33 

    34 function lengthVector(self) {

    35     return Math.sqrt(self[0] * self[0] + self[1] * self[1] + self[2] * self[2]);

    36 }

    37 

    38 function addVector(self, v) {

    39     self[0] += v[0];

    40     self[1] += v[1];

    41     self[2] += v[2];

    42     return self;

    43 }

    44 

    45 function subVector(self, v) {

    46     self[0] -= v[0];

    47     self[1] -= v[1];

    48     self[2] -= v[2];

    49     return self;

    50 }

    51 

    52 function scaleVector(self, scale) {

    53     self[0] *= scale;

    54     self[1] *= scale;

    55     self[2] *= scale;

    56     return self;

    57 }

    58 

    59 function normaliseVector(self) {

    60     var len = Math.sqrt(self[0] * self[0] + self[1] * self[1] + self[2] * self[2]);

    61     self[0] /= len;

    62     self[1] /= len;

    63     self[2] /= len;

    64     return self;

    65 }

    66 

    67 function add(v1, v2) {

    68     return new Array(v1[0] + v2[0], v1[1] + v2[1], v1[2] + v2[2]);

    69 }

    70 

    71 function sub(v1, v2) {

    72     return new Array(v1[0] - v2[0], v1[1] - v2[1], v1[2] - v2[2]);

    73 }

    74 

    75 function scalev(v1, v2) {

    76     return new Array(v1[0] * v2[0], v1[1] * v2[1], v1[2] * v2[2]);

    77 }

    78 

    79 function dot(v1, v2) {

    80     return v1[0] * v2[0] + v1[1] * v2[1] + v1[2] * v2[2];

    81 }

    82 

    83 function scale(v, scale) {

    84     return [v[0] * scale, v[1] * scale, v[2] * scale];

    85 }

    86 

    87 function cross(v1, v2) {

    88     return [v1[1] * v2[2] - v1[2] * v2[1], 

    89             v1[2] * v2[0] - v1[0] * v2[2],

    90             v1[0] * v2[1] - v1[1] * v2[0]];

    91 

    92 }

    93 

    94 function normalise(v) {

    95     var len = lengthVector(v);

    96     return [v[0] / len, v[1] / len, v[2] / len];

    97 }

    98 

    99 function transformMatrix(self, v) {

   100     var vals = self;

   101     var x  = vals[0] * v[0] + vals[1] * v[1] + vals[2] * v[2] + vals[3];

   102     var y  = vals[4] * v[0] + vals[5] * v[1] + vals[6] * v[2] + vals[7];

   103     var z  = vals[8] * v[0] + vals[9] * v[1] + vals[10] * v[2] + vals[11];

   104     return [x, y, z];

   105 }

   106 

   107 function invertMatrix(self) {

   108     var temp = new Array(16);

   109     var tx = -self[3];

   110     var ty = -self[7];

   111     var tz = -self[11];

   112     for (h = 0; h < 3; h++) 

   113         for (v = 0; v < 3; v++) 

   114             temp[h + v * 4] = self[v + h * 4];

   115     for (i = 0; i < 11; i++)

   116         self[i] = temp[i];

   117     self[3] = tx * self[0] + ty * self[1] + tz * self[2];

   118     self[7] = tx * self[4] + ty * self[5] + tz * self[6];

   119     self[11] = tx * self[8] + ty * self[9] + tz * self[10];

   120     return self;

   121 }

   122 

   123 

   124 // Triangle intersection using barycentric coord method

   125 function Triangle(p1, p2, p3) {

   126     var edge1 = sub(p3, p1);

   127     var edge2 = sub(p2, p1);

   128     var normal = cross(edge1, edge2);

   129     if (Math.abs(normal[0]) > Math.abs(normal[1]))

   130         if (Math.abs(normal[0]) > Math.abs(normal[2]))

   131             this.axis = 0; 

   132         else 

   133             this.axis = 2;

   134     else

   135         if (Math.abs(normal[1]) > Math.abs(normal[2])) 

   136             this.axis = 1;

   137         else 

   138             this.axis = 2;

   139     var u = (this.axis + 1) % 3;

   140     var v = (this.axis + 2) % 3;

   141     var u1 = edge1[u];

   142     var v1 = edge1[v];

   143     

   144     var u2 = edge2[u];

   145     var v2 = edge2[v];

   146     this.normal = normalise(normal);

   147     this.nu = normal[u] / normal[this.axis];

   148     this.nv = normal[v] / normal[this.axis];

   149     this.nd = dot(normal, p1) / normal[this.axis];

   150     var det = u1 * v2 - v1 * u2;

   151     this.eu = p1[u];

   152     this.ev = p1[v]; 

   153     this.nu1 = u1 / det;

   154     this.nv1 = -v1 / det;

   155     this.nu2 = v2 / det;

   156     this.nv2 = -u2 / det; 

   157     this.material = [0.7, 0.7, 0.7];

   158 }

   159 

   160 Triangle.prototype.intersect = function(orig, dir, near, far) {

   161     var u = (this.axis + 1) % 3;

   162     var v = (this.axis + 2) % 3;

   163     var d = dir[this.axis] + this.nu * dir[u] + this.nv * dir[v];

   164     var t = (this.nd - orig[this.axis] - this.nu * orig[u] - this.nv * orig[v]) / d;

   165     if (t < near || t > far)

   166         return null;

   167     var Pu = orig[u] + t * dir[u] - this.eu;

   168     var Pv = orig[v] + t * dir[v] - this.ev;

   169     var a2 = Pv * this.nu1 + Pu * this.nv1;

   170     if (a2 < 0) 

   171         return null;

   172     var a3 = Pu * this.nu2 + Pv * this.nv2;

   173     if (a3 < 0) 

   174         return null;

   175 

   176     if ((a2 + a3) > 1) 

   177         return null;

   178     return t;

   179 }

   180 

   181 function Scene(a_triangles) {

   182     this.triangles = a_triangles;

   183     this.lights = [];

   184     this.ambient = [0,0,0];

   185     this.background = [0.8,0.8,1];

   186 }

   187 var zero = new Array(0,0,0);

   188 

   189 Scene.prototype.intersect = function(origin, dir, near, far) {

   190     var closest = null;

   191     for (i = 0; i < this.triangles.length; i++) {

   192         var triangle = this.triangles[i];   

   193         var d = triangle.intersect(origin, dir, near, far);

   194         if (d == null || d > far || d < near)

   195             continue;

   196         far = d;

   197         closest = triangle;

   198     }

   199     

   200     if (!closest)

   201         return [this.background[0],this.background[1],this.background[2]];

   202         

   203     var normal = closest.normal;

   204     var hit = add(origin, scale(dir, far)); 

   205     if (dot(dir, normal) > 0)

   206         normal = [-normal[0], -normal[1], -normal[2]];

   207     

   208     var colour = null;

   209     if (closest.shader) {

   210         colour = closest.shader(closest, hit, dir);

   211     } else {

   212         colour = closest.material;

   213     }

   214     

   215     // do reflection

   216     var reflected = null;

   217     if (colour.reflection > 0.001) {

   218         var reflection = addVector(scale(normal, -2*dot(dir, normal)), dir);

   219         reflected = this.intersect(hit, reflection, 0.0001, 1000000);

   220         if (colour.reflection >= 0.999999)

   221             return reflected;

   222     }

   223     

   224     var l = [this.ambient[0], this.ambient[1], this.ambient[2]];

   225     for (var i = 0; i < this.lights.length; i++) {

   226         var light = this.lights[i];

   227         var toLight = sub(light, hit);

   228         var distance = lengthVector(toLight);

   229         scaleVector(toLight, 1.0/distance);

   230         distance -= 0.0001;

   231         if (this.blocked(hit, toLight, distance))

   232             continue;

   233         var nl = dot(normal, toLight);

   234         if (nl > 0)

   235             addVector(l, scale(light.colour, nl));

   236     }

   237     l = scalev(l, colour);

   238     if (reflected) {

   239         l = addVector(scaleVector(l, 1 - colour.reflection), scaleVector(reflected, colour.reflection));

   240     }

   241     return l;

   242 }

   243 

   244 Scene.prototype.blocked = function(O, D, far) {

   245     var near = 0.0001;

   246     var closest = null;

   247     for (i = 0; i < this.triangles.length; i++) {

   248         var triangle = this.triangles[i];   

   249         var d = triangle.intersect(O, D, near, far);

   250         if (d == null || d > far || d < near)

   251             continue;

   252         return true;

   253     }

   254     

   255     return false;

   256 }

   257 

   258 

   259 // this camera code is from notes i made ages ago, it is from *somewhere* -- i cannot remember where

   260 // that somewhere is

   261 function Camera(origin, lookat, up) {

   262     var zaxis = normaliseVector(subVector(lookat, origin));

   263     var xaxis = normaliseVector(cross(up, zaxis));

   264     var yaxis = normaliseVector(cross(xaxis, subVector([0,0,0], zaxis)));

   265     var m = new Array(16);

   266     m[0] = xaxis[0]; m[1] = xaxis[1]; m[2] = xaxis[2];

   267     m[4] = yaxis[0]; m[5] = yaxis[1]; m[6] = yaxis[2];

   268     m[8] = zaxis[0]; m[9] = zaxis[1]; m[10] = zaxis[2];

   269     invertMatrix(m);

   270     m[3] = 0; m[7] = 0; m[11] = 0;

   271     this.origin = origin;

   272     this.directions = new Array(4);

   273     this.directions[0] = normalise([-0.7,  0.7, 1]);

   274     this.directions[1] = normalise([ 0.7,  0.7, 1]);

   275     this.directions[2] = normalise([ 0.7, -0.7, 1]);

   276     this.directions[3] = normalise([-0.7, -0.7, 1]);

   277     this.directions[0] = transformMatrix(m, this.directions[0]);

   278     this.directions[1] = transformMatrix(m, this.directions[1]);

   279     this.directions[2] = transformMatrix(m, this.directions[2]);

   280     this.directions[3] = transformMatrix(m, this.directions[3]);

   281 }

   282 

   283 Camera.prototype.generateRayPair = function(y) {

   284     rays = new Array(new Object(), new Object());

   285     rays[0].origin = this.origin;

   286     rays[1].origin = this.origin;

   287     rays[0].dir = addVector(scale(this.directions[0], y), scale(this.directions[3], 1 - y));

   288     rays[1].dir = addVector(scale(this.directions[1], y), scale(this.directions[2], 1 - y));

   289     return rays;

   290 }

   291 

   292 function renderRows(camera, scene, pixels, width, height, starty, stopy) {

   293     for (var y = starty; y < stopy; y++) {

   294         var rays = camera.generateRayPair(y / height);

   295         for (var x = 0; x < width; x++) {

   296             var xp = x / width;

   297             var origin = addVector(scale(rays[0].origin, xp), scale(rays[1].origin, 1 - xp));

   298             var dir = normaliseVector(addVector(scale(rays[0].dir, xp), scale(rays[1].dir, 1 - xp)));

   299             var l = scene.intersect(origin, dir);

   300             pixels[y][x] = l;

   301         }

   302     }

   303 }

   304 

   305 Camera.prototype.render = function(scene, pixels, width, height) {

   306     var cam = this;

   307     var row = 0;

   308     renderRows(cam, scene, pixels, width, height, 0, height);

   309 }

   310 

   311 

   312 

   313 function raytraceScene()

   314 {

   315     var startDate = new Date().getTime();

   316     var numTriangles = 2 * 6;

   317     var triangles = new Array();//numTriangles);

   318     var tfl = createVector(-10,  10, -10);

   319     var tfr = createVector( 10,  10, -10);

   320     var tbl = createVector(-10,  10,  10);

   321     var tbr = createVector( 10,  10,  10);

   322     var bfl = createVector(-10, -10, -10);

   323     var bfr = createVector( 10, -10, -10);

   324     var bbl = createVector(-10, -10,  10);

   325     var bbr = createVector( 10, -10,  10);

   326     

   327     // cube!!!

   328     // front

   329     var i = 0;

   330     

   331     triangles[i++] = new Triangle(tfl, tfr, bfr);

   332     triangles[i++] = new Triangle(tfl, bfr, bfl);

   333     // back

   334     triangles[i++] = new Triangle(tbl, tbr, bbr);

   335     triangles[i++] = new Triangle(tbl, bbr, bbl);

   336     //        triangles[i-1].material = [0.7,0.2,0.2];

   337     //            triangles[i-1].material.reflection = 0.8;

   338     // left

   339     triangles[i++] = new Triangle(tbl, tfl, bbl);

   340     //            triangles[i-1].reflection = 0.6;

   341     triangles[i++] = new Triangle(tfl, bfl, bbl);

   342     //            triangles[i-1].reflection = 0.6;

   343     // right

   344     triangles[i++] = new Triangle(tbr, tfr, bbr);

   345     triangles[i++] = new Triangle(tfr, bfr, bbr);

   346     // top

   347     triangles[i++] = new Triangle(tbl, tbr, tfr);

   348     triangles[i++] = new Triangle(tbl, tfr, tfl);

   349     // bottom

   350     triangles[i++] = new Triangle(bbl, bbr, bfr);

   351     triangles[i++] = new Triangle(bbl, bfr, bfl);

   352     

   353     //Floor!!!!

   354     var green = createVector(0.0, 0.4, 0.0);

   355     var grey = createVector(0.4, 0.4, 0.4);

   356     grey.reflection = 1.0;

   357     var floorShader = function(tri, pos, view) {

   358         var x = ((pos[0]/32) % 2 + 2) % 2;

   359         var z = ((pos[2]/32 + 0.3) % 2 + 2) % 2;

   360         if (x < 1 != z < 1) {

   361             //in the real world we use the fresnel term...

   362             //    var angle = 1-dot(view, tri.normal);

   363             //   angle *= angle;

   364             //  angle *= angle;

   365             // angle *= angle;

   366             //grey.reflection = angle;

   367             return grey;

   368         } else 

   369             return green;

   370     }

   371     var ffl = createVector(-1000, -30, -1000);

   372     var ffr = createVector( 1000, -30, -1000);

   373     var fbl = createVector(-1000, -30,  1000);

   374     var fbr = createVector( 1000, -30,  1000);

   375     triangles[i++] = new Triangle(fbl, fbr, ffr);

   376     triangles[i-1].shader = floorShader;

   377     triangles[i++] = new Triangle(fbl, ffr, ffl);

   378     triangles[i-1].shader = floorShader;

   379     

   380     var _scene = new Scene(triangles);

   381     _scene.lights[0] = createVector(20, 38, -22);

   382     _scene.lights[0].colour = createVector(0.7, 0.3, 0.3);

   383     _scene.lights[1] = createVector(-23, 40, 17);

   384     _scene.lights[1].colour = createVector(0.7, 0.3, 0.3);

   385     _scene.lights[2] = createVector(23, 20, 17);

   386     _scene.lights[2].colour = createVector(0.7, 0.7, 0.7);

   387     _scene.ambient = createVector(0.1, 0.1, 0.1);

   388     //  _scene.background = createVector(0.7, 0.7, 1.0);

   389     

   390     var size = 30;

   391     var pixels = new Array();

   392     for (var y = 0; y < size; y++) {

   393         pixels[y] = new Array();

   394         for (var x = 0; x < size; x++) {

   395             pixels[y][x] = 0;

   396         }

   397     }

   398 

   399     var _camera = new Camera(createVector(-40, 40, 40), createVector(0, 0, 0), createVector(0, 1, 0));

   400     _camera.render(_scene, pixels, size, size);

   401 

   402     return pixels;

   403 }

   404 

   405 function arrayToCanvasCommands(pixels)

   406 {

   407     var s = '<canvas id="renderCanvas" width="30px" height="30px"></canvas><scr' + 'ipt>\nvar pixels = [';

   408     var size = 30;

   409     for (var y = 0; y < size; y++) {

   410         s += "[";

   411         for (var x = 0; x < size; x++) {

   412             s += "[" + pixels[y][x] + "],";

   413         }

   414         s+= "],";

   415     }

   416     s += '];\n    var canvas = document.getElementById("renderCanvas").getContext("2d");\n\

   417 \n\

   418 \n\

   419     var size = 30;\n\

   420     canvas.fillStyle = "red";\n\

   421     canvas.fillRect(0, 0, size, size);\n\

   422     canvas.scale(1, -1);\n\

   423     canvas.translate(0, -size);\n\

   424 \n\

   425     if (!canvas.setFillColor)\n\

   426         canvas.setFillColor = function(r, g, b, a) {\n\

   427             this.fillStyle = "rgb("+[Math.floor(r * 255), Math.floor(g * 255), Math.floor(b * 255)]+")";\n\

   428     }\n\

   429 \n\

   430 for (var y = 0; y < size; y++) {\n\

   431   for (var x = 0; x < size; x++) {\n\

   432     var l = pixels[y][x];\n\

   433     canvas.setFillColor(l[0], l[1], l[2], 1);\n\

   434     canvas.fillRect(x, y, 1, 1);\n\

   435   }\n\

   436 }</scr' + 'ipt>';

   437 

   438     return s;

   439 }

   440 

   441 testOutput = arrayToCanvasCommands(raytraceScene());