Custom Components: React & x-tags

Using x-tags from Mozilla, we can write custom tags within the DOM. This is a great opportunity to be able to write reusable components without being tied to a particular library. I wrote x-react to have them being rendered in React.

Example

We’re first going to write a regular React component.

var Hello = React.createClass({
  render: function() { return <div>{'Hello ' + this.props.name}</div>; }
});

Then, we use xreact.register to bind a React component to a custom tag name.

xreact.register('x-hello', Hello);

At this point, any DOM element will be rendered using React.

<x-hello name="World"></x-hello>

The rendered DOM tree lives in the shadow DOM. This lets us manipulate both the component as well as the rendered <div> using Web Inspector.

Anytime you modify the component, whether it is in the inspector or in Javascript with the regular DOM API, React is going to be invoked to update the rendered version.

Behind the scenes

When you call xreact.register, we call xtag.register saying that whenever an DOM element is created, we render a special component called XReact in the shadow root of <x-hello>.

xtag.register('x-hello', {
  lifecycle: {
    created: function() {
      React.renderComponent(
        XReact({element: this}),
        this.createShadowRoot()
      );
    }
  }
});

XReact is a really simple component that takes a DOM node, in this case <x-hello name="World" /> and converts it to the React equivalent: Hello({name: 'World'}).

var XReact = React.createClass({
  render: function() {
    return convertDOMToReact(this.props.element);
  }

MutationObserver gives us a callback whenever the DOM element is changed. We just have to call this.forceUpdate() to make sure the React rendered version stays in sync.

  componentDidMount: function() {
    new MutationObserver(this.forceUpdate.bind(this)).observe(
      this.props.element, {/* all the possible mutations */}
    );
  }
);

That’s it πŸ™‚

Conclusion

It was really easy to make this small bridge in order to be able to create custom tags and have them rendered using React. Unfortunately, this experiment is only working on Chrome as it is relying on MutationObserver and Shadow DOM.

In 2001, Douglas Crockford evangelized private members design pattern and since then has been widely adopted by the Javascript community. However, are they really private?

Javascript is an extremely dynamic language in which it is possible to access a lot of things on way or another. We’ll see how to get a reference to most of the “private” methods you can find in the wild.

Example

Here’s a snippet of code from underscore.js. We are interested in getting a reference to the following “private” functions: lookupIterator and group.

(function() {
  /* ... */
 
  // An internal function to generate lookup iterators.
  var lookupIterator = function(value) {
    return _.isFunction(value) ? value : function(obj){ return obj[value]; };
  };
 
  // An internal function used for aggregate "group by" operations.
  var group = function(obj, value, context, behavior) {
    var result = {};
    var iterator = lookupIterator(value || _.identity);
    each(obj, function(value, index) {
      var key = iterator.call(context, value, index, obj);
      behavior(result, key, value);
    });
    return result;
  };
 
  // Groups the object's values by a criterion. Pass either a string attribute
  // to group by, or a function that returns the criterion.
  _.groupBy = function(obj, value, context) {
    return group(obj, value, context, function(result, key, value) {
      (_.has(result, key) ? result[key] : (result[key] = [])).push(value);
    });
  };
 
  /* ... */
}).call(this);

// An internal function to generate lookup iterators.
var lookupIterator = function(value) {
return _.isFunction(value) ? value : function(obj){ return obj[value]; };
};

// An internal function used for aggregate "group by" operations.
var group = function(obj, value, context, behavior) {
var result = {};
var iterator = lookupIterator(value || _.identity);
each(obj, function(value, index) {
var key = iterator.call(context, value, index, obj);
behavior(result, key, value);
});
return result;
};

// Groups the object’s values by a criterion. Pass either a string attribute
// to group by, or a function that returns the criterion.
_.groupBy = function(obj, value, context) {
return group(obj, value, context, function(result, key, value) {
(_.has(result, key) ? result[key] : (result[key] = [])).push(value);
});
};

/* … */
}).call(this);

Here’s the code to do it: (Demo on JSFiddle)

var lookupIterator;
var group;
 
_.isFunction = function() {
  lookupIterator = arguments.callee.caller;
  group = lookupIterator.caller;
};
_.groupBy();
 
console.log('lookupIterator', lookupIterator);
console.log('group', group);

_.isFunction = function() {
lookupIterator = arguments.callee.caller;
group = lookupIterator.caller;
};
_.groupBy();

console.log(‘lookupIterator’, lookupIterator);
console.log(‘group’, group);

The way it works is by hooking a function deep inside the internals of the module you want to break into and use arguments.callee.caller to get references to all the functions upward.

In this case, it was easy as we could hook _.isFunction. You can break into a lot of functions overriding String.prototype and using __defineGetter__.

Conclusion

Trying to break into existing Javascript code and make it do what you want is an extremely fun exercise. If this topic is of interest to you, take a look at this big list of Javascript attack vectors written by Google Caja team.

Conversion from uint8 to int8 (x 24)

Daniel Baulig, a co-worker at Facebook, told me a little trick related to jDataView function to convert from a uint8 to a int8 in Javascript.

Here’s the version I had:

function getInt8() {
  var b = this.getUint8();
  if (b > Math.pow(2, 7) - 1) {
    return b - Math.pow(2, 8);
  }
  return b;
}

Compare it to his version:

< <function getInt8() {
  return this.getUint8() << 24 >> 24;
}

I was really confused because it seems like it’s doing a no-op. Here’s the full explanation of why the two versions are working.

How it works?

The following table (borrowed from Wikipedia) shows how various 8 bits values are in represented with bits and how they are interpreted in unsigned and signed (using two-complement rule).

.uint8table {margin: 0 auto; border-collapse: collapse; }
.uint8table td, .uint8table th { padding: 2px 5px; border: 1px solid #ccc; text-align: center; }
.uint8table b { background-color: #FFE0ED; font-weight: normal; }
.uint8table i { color: purple; font-style: normal; }
.uint8table .sep td { border-bottom: 2px solid #bbb; }
#hidefirsttwo span:nth-child(1), #hidefirsttwo span:nth-child(2) { display: none; }
#hidefirsttwo span:nth-child(3) { margin-left: -7px; }

Bits uint8 int8
0000 0000 0 0
0000 0001 1 1
0000 0010 2 2
0111 1110 126 126
0111 1111 127 127
1000 0000 128 βˆ’128
1000 0001 129 βˆ’127
1000 0010 130 βˆ’126
1111 1110 254 βˆ’2
1111 1111 255 βˆ’1

Javascript doesn’t natively have a 8 bit integer type, it only has a 32 bits one. When you put a 8 bit integer into a 32 bits one, Javascript is going to fill the remaining bits on the left with zeros as the following table shows.

Bits int32
0000 0000 … 0000 0000 0
0000 0000 … 0000 0001 1
0000 0000 … 0000 0010 2
0000 0000 … 0111 1110 126
0000 0000 … 0111 1111 127
0000 0000 … 1000 0000 128
0000 0000 … 1000 0001 129
0000 0000 … 1000 0010 130
0000 0000 … 1111 1110 254
0000 0000 … 1111 1111 255

Unfortunately, this doesn’t properly handle negative numbers. Because we use two-complement, we’ve got to fill all the bits with 1 for negative numbers in order to have the same number in a signed 32 bits representation.

Bits int32
0000 0000 … 0000 0000 0
0000 0000 … 0000 0001 1
0000 0000 … 0000 0010 2
0000 0000 … 0111 1110 126
0000 0000 … 0111 1111 127
1111 1111 … 1000 0000 βˆ’128
1111 1111 … 1000 0001 βˆ’127
1111 1111 … 1000 0010 βˆ’126
1111 1111 … 1111 1110 βˆ’2
1111 1111 … 1111 1111 βˆ’1

So basically, we’ve got to fill the 24 remaining bits on the left with the same first bit we have: 0 for positive numbers and 1 for negative numbers.

This is when the trick comes into place. In javascript, there’s a binary operator: >> >_(Sign-propagating_right_shift)”>Sign-propagating right shift that moves all the bits to the right and fills the missing bits with the first bit.

So all we have to do is to put our 8 good digits to the far left using << and then use the previous trick to fill the bits with the proper ones πŸ™‚

x x < < 24 (x <> 24
0000 0000 … 0000 0000 0000 0000 … 0000 0000 0000 0000 … 0000 0000
0000 0000 … 0000 0001 0000 0001 … 0000 0000 0000 0000 … 0000 0001
0000 0000 … 0000 0010 0000 0010 … 0000 0000 0000 0000 … 0000 0010
0000 0000 … 0111 1110 0111 1110 … 0000 0000 0000 0000 … 0111 1110
0000 0000 … 0111 1111 0111 1111 … 0000 0000 0000 0000 … 0111 1111
0000 0000 … 1000 0000 1000 0000 … 0000 0000 1111 1111 … 1000 0000
0000 0000 … 1000 0001 1000 0001 … 0000 0000 1111 1111 … 1000 0001
0000 0000 … 1000 0010 1000 0010 … 0000 0000 1111 1111 … 1000 0010
0000 0000 … 1111 1110 1111 1110 … 0000 0000 1111 1111 … 1111 1110
0000 0000 … 1111 1111 1111 1111 … 0000 0000 1111 1111 … 1111 1111

It’s often said that XML is very verbose and therefore JSON is better. I wanted to challenge that assumption and find the smallest way to represent any JSON value using XML.

table#xson { border-collapse: collapse; margin: 0 auto; }
table#xson td, table#xson th { border: 1px solid #999; padding: 5px 10px; background-color: transparent; }
table#xson th { text-align: center; }
table#xson .wp_syntax { border: none; background-color: transparent; margin: 0; }
table#xson strong { font-family: monospace; color: black; font-size: 12px; padding-left: 5px; }

Constants
true
<t/> 0
false
<f/> – 1
null
<l/> 0
Number
NaN
<n/> + 1
123.45
<n>123.45</n>
+ 6
String

""
<s/> + 2
"Abcd"
<s>Abcd</s>
+ 4
Array
[]
<a/> + 2
[1, "two", false]
<a>
  <n>1</n>
  <s>two</s>
  <f></f>
</a>
+ 4 – n
Object
{}
<o/> + 2
{
  "first": 1,
  "second": "two",
  "third": false
}
<o>
  <n k="first">1</n>
  <s k="second">two</s>
  <f k="third"></f>
</o>
+ 5 + n

As you can see, the XML counter part is a bit more verbose and less readable because of the way syntax highlighting is setup. However, while it is bigger, it isn’t out of proportion bigger. The structure can be at most twice as big.

Implementation

In order to implement it, I decided to go with the same API as JSON:

  • XSON.stringify(object, formatter, space)
  • XSON.parse(string)

You can play with it on this current page or can check it out on GitHub.

The implementation was more straightforward than I expected thanks to the fact that there’s a XML Parser inside browsers. However, I had to deal with nasty encoding issues πŸ™

String encoding

There are some characters such as < and that we want to escape because otherwise they are likely to be problematic while parsing the XML. The way to encode those characters in XML is to use the &#number; notation where number is the character code. For example a is represented by a:

> new DOMParser().parseFromString('<a>&#97;</a>', 'text/xml')
    .getElementsByTagName('a')[0].textContent
"a"

Unfortunately, you cannot express all the characters with this notation. The XML specification introduces Restricted Characters in the following ranges: [#x1-#x8], [#xB-#xC], [#xE-#x1F], [#x7F-#x84] and [#x86-#x9F]. When you try to read those characters, then the XML parser generates an error.

> new DOMParser().parseFromString('<a>&#0;</a>', 'text/xml')
    .getElementsByTagName('a')[0].textContent
"error on line 1 at column 8: xmlParseCharRef: invalid xmlChar value 0"

Instead of fighting with the XML spec, I decided to use my own encoding. I replace the character by u0000. Where the number is an hexadecimal representation of the number padding so it has exactly four digits.

To do that, we need first to escape all the and can use a regex to do it in few lines of code πŸ™‚

function encode(str) {
   return str
     .replace(/\/g, '\\')
     .replace(/[u0000-u0008u000b-u001f&<>"nt]/g, function(c) {
       var hex = c.charCodeAt(0).toString(16);
       while (hex.length < 4) {
         hex = '0' + hex;
       }
       return '\u' + hex;
     });
 }

Then, in order to decode it, we do the opposite: we first decode all the unicode characters and remove the escapes. In order to make sure that the unicode character was not escape, I’m using a small trick. You can count the number of . If it’s an even number, then it is not escaped, otherwise it is escaped!

function decode(str) {
  return str
    .replace(/(\*)\u([0-9a-f]{4})/g, function(match, backslash, n) {
      if (backslash.length % 2 !== 0) {
        return match;
      }
      return backslash + String.fromCharCode(parseInt(n, 16));
    })
    .replace(/\\/g, '\');
}

I’m working on an application in the browser that lets you take notes. I don’t want to have the burden to save them on my own server therefore I want to use Github Gists as storage. The challenge is to be able to communicate with the Github API 100% inside the browser.

Since it is a difficult task due to Cross-origin resource sharing limitations and multi-step OAuth process, I decided to share with you a working procedure I found. It involves different communication protocols such as HTTP Redirect, window.postMessage, Ajax post and get and a small PHP proxy using cURL.

Login Phase

Phase 0 – Create an application

Before doing anything, you have to create a Github application. It will provide you the client_id and client_secret as well as an admin to put the redirect URL.

Phase 1 – Get authentication code

Using Github API OAuth guide we learn that we have to redirect the user to a page on github server. After the user authorizes the application, the page is redirected to one of our page with a code.

Since we do not want to leave the current page (it would make all the user changes vanish) we must open the page in another context. The first one I tried was an iframe but github has the X-Frame-Options header set that prevents embedding the page in the iframe.

So the other option was to open a new window. With window.open it was really easy to do so. The only tricky part was to actually give back the result to the main window. After digging, I found the following snippet of code that works well: window.opener.postMessage(message, window.location).

Phase 2 – Get access token

We are back in the main window and have the code. We now need to exchange this code for a token. I really wonder why they didn’t give us the token already but well, there must be a reason! In order to get the token, we must send a POST request to a page on github.

However another difficulty comes in, this one page does not have a Access-Control-Allow-Origin header set to our domain. So basically, we cannot access it from the browser using AJAX. Since it’s a POST request, we cannot even use JSON-P to bypass it.

I did not want to have a server but I am resigned to write a small PHP proxy that will forward the call. I believe that the main reason why they blocked it was because they ask for the client_secret. They don’t want us to write it down in our Javascript in plain sight.

Phase 3 – Enjoy!

Now that we have got our token, we can call all the APIs on Github using post and get AJAX requests and they all work fine. One good thing is the fact that the token is permanent. Unless you change the permissions you request or the user revokes your application, every time the user logs in, he will be associated the same token.

You can safely store the token in the user’s browser with localStorage in order to keep them logged when they come back to the application. Just make sure to catch 401 Unauthorized error on requests in case the token is no longer valid and ask the user to log in again.

Demo

And here’s the demo! The source code is really small and available on github. If you plan to integrate an in-browser login, it can be used as a starting point.

You might want the link to revoke the access from the dummy application for testing purposes.

Conclusion

At first glance, the login process seemed to be really straightforward, you just had 2 requests to get your code and token and you are good to go. But doing so in the browser revealed itself to be a lot harder. I’m not satisfied with the process as it involves many different technologies but that’s the best I could find. If you handled things differently please tell me πŸ™‚

I recently had the chance to do a 2-hour Javascript evangelism talk at Dassault SystΓ¨mes. Unfortunately the presentation has not been recorded. I reused my the presentation I did at EPITA at the beginning and added a second part with a lot of demos. I’ve written down notes about the second part so you can get an idea.

Developer Tools

  • Web Inspector. It is integrated into Google Chrome and has all the features you would be expecting in an IDE. The console is really powerful as it lets you browse through the Javascript objects. You no longer need to write endless printing functions. You can edit the HTML and CSS without a page reload, it makes designing interfaces a lot more efficient. There is also a full panel dedicated to profiling both Javascript and DOM events.
  • JSFiddle. Web programming is all about interactivity. Not only you with the program (REPL) but also with other people. Everything you do can be one link away. JSFiddle lets you try and experiment things without the need of an IDE and allows you to show it to the world easily.
  • JSHint. Because Javascript, the language, has design issues and is highly dynamic, it is useful to enforce good practices and to set common programming rules when working together. Always in the spirit of the web, you can just copy and paste your code to check it. Note that JSHint can also be integrated in all major text editors and IDEs.

CSS

HTML and CSS were traditionally used to make websites and forms. We can now make completely different things.

  • jmpress.js. Here’s an example of how to use 3D in CSS in order to make animated presentation. One important thing to notice is how easy it is to use it. Just include jmpress.js in the page and add data-x="-5000" data-rotate="180" attributes to your HTML. It just works!
  • CSS Panic. In order to show how powerful CSS got those days, here’s a game completely written in HTML + CSS. There is 0 lines of Javascript!

Canvas

Canvas is just a rectangle where you can manipulate each pixel’s color.

  • RayTracer. Ray Tracer is a common computer science school project. Usually, you write it on your computer and sometimes share the resulting image but you don’t really share it because no one want to take the pain of compiling it on their machine. With Javascript, you can just share a link and everyone can test it!
  • Canvas Rider. You can now create games in the browser. There is even a level editor implemented that follows principle of the web: interactivity. You can draw the map and move your character at the same time. When you are done, you are a single click away from saving the map and sharing it to people.
  • pdf.js. The browser is now able to create applications that have always been restricted to native ones. The perfect example is this demo by Mozilla of a pdf renderer written exclusively in Javascript!

SVG

SVG let you manipulate vector graphics such as line, curve, circle …

  • Cloth Simulation. Javascript implementations have gotten fast enough to do real time constraint solving simulations such as this one. It uses SVG to easily render the graph.
  • Simulated Annealing. It’s another school project that gains from being written in the web. This would have probably been written in console mode, using ascii art and generating images as output. The parameters would have been entered in the command line. We can instead exploit HTML to make forms that update in real time, and SVG to render the problem and a graph to display the progress.

WebGL

WebGL is an implementation of OpenGL in the browser. It let us use the graphical card from Javascript.

  • 3D Simulated Annealing. Same as previous demo but this time there is a 3D representation of the progress. It also follows the interactivity rule, you can use your mouse and WASD to explore the scene. This demo uses Web Workers to exploit multiple cores.
  • WebGL Maps. The graphical card is dedicated to manipulate images, therefore you can use it to improve performance on image intensive applications such as Google Maps.
  • Bevelity. Ever wondered if it was possible to write a complex application such as 3DSMax in the browser? Bevelity is an attempt to prove it true.
  • Water Simulation. Another physics simulation demo with always the web plus: you can move the ball πŸ™‚
  • Hello Racer. This is one of the thousand demos that shows you a beautiful car with glossy reflects … This one has a unique feature: you can move the car! This must not have taken more than a few dozens of lines and yet has a huge impact!
  • Morph Target. Pixar also find uses for the web. Here’s a demo to create facial expressions.
  • Rome. Browsers now embed a video tag. Using it in combination with WebGL, Google made a wonderful 3-minute animation. You can use the mouse to interact with it. It moves the camera, pixelate the video and even make appear various monsters.

Performance

Javascript performance are impressively improving from months to months. It is now possible to write computing intensive programs and make them run at decent speed.

  • JSPerf. If you have a doubt on which browser is faster for a specific feature or when you have two ways to do things, which one is faster, JSPerf is made for you!
  • JSLinux. Typed Arrays introduced for WebGL made possible to write a CPU Virtual Machine able to run a copy of linux in under 7 seconds.
  • repl.it. Emscriptem is a wonderful tool that translates LLVM assembly code into Javascript. It made possible to compile Ruby, Python, Lua and Scheme directly from their sources to Javascript.
  • Broadway. Last but not least, a H.264 video decoder has been compiled to Javascript using Emscriptem. It manages to decode the sample videos at 60 frames per second. This is an exceptional feat for a scripting language!

Conclusion

It is now possible to write the same complex applications we seen in the past in the browser. And it gives one huge added value: interactivity. There’s absolutely nothing to install, you just have to give a link! You can combine all the render options such as HTML, CSS, Canvas, SVG and WebGL to make your program.

The next talk I’m going to do is at the JSConf! I hope to see you there!

Javascript Ray Tracer

Here is a report of the Ray Tracer written by myself Christopher Chedeau. I’ve taken the file format and most of the examples from the Ray Tracer of our friends Maxime Mouial and ClΓ©ment BΕ“sch. The source is available on Github.

It is powered by Open Source technologies: glMatrix, CodeMirror, CoffeeScript, Twitter Bootstrap, jQuery and Web Workers.

Check out the demo, or click on any of the images.

Objects

Our Ray Tracer supports 4 object types: Plane, Sphere, Cylinder and Cone.

The core idea of the Ray Tracer is to send rays that will be reflected on items. Given a ray (origin and direction), we need to know if it intersect an object on the scene, and if it does, how to get a ray’ that will be reflected on the object.

Knowing that, we open up our high school math book and come up with all the following formulas.

Legend: Ray Origin (O), Ray Direction (D), Intersection Position (O’), Intersection Normal (N) and Item Radius (r).

.eq { width: 100%; } .eq th { text-align: center; }

Intersection Normal
Plane [t = frac{O_z}{D_z}] [
N = left{
begin{array}{l}
x = 0 \
y = 0 \
z = -sign(D_z)
end{array} right.
]
Sphere [
begin{array}{l l l}
& t^2 & (O cdot O) \
+ & 2t & (O cdot D) \
+ & & (O cdot O) – r^2
end{array}
= 0]
[
N = left{
begin{array}{l}
x = O’_x \
y = O’_y \
z = O’_z
end{array} right.
]
Cylinder [
begin{array}{l l l}
& t^2 & (D_x D_x + D_y D_y) \
+ & 2t & (O_x D_x + O_y D_y) \
+ & & (O_x O_x + O_y O_y – r^2)
end{array}
= 0]
[
N = left{
begin{array}{l}
x = O’_x \
y = O’_y \
z = 0
end{array} right.
]
Cone [
begin{array}{l l l}
& t^2 & (D_x D_x + D_y D_y – r^2 D_z D_z) \
+ & 2t & (O_x D_x + O_y D_y – r^2 O_z D_z) \
+ & & (O_x O_x + O_y O_y – r^2 O_z O_z)
end{array}
= 0]
[
N = left{
begin{array}{l}
x = O’_x \
y = O’_y \
z = – O’_z * tan(r^2)
end{array} right.
]

In order to solve the equation (at^2 + bt + c = 0), we use
[Delta = b^2 – 4ac ][
begin{array}{c c c}
Delta geq 0 & t_1 = frac{-b – sqrt{Delta}}{2a} & t_2 = frac{-b + sqrt{Delta}}{2a}
end{array}
]

And here is the formula for the reflected ray:

[
left{
begin{array}{l}
O’ = O + tD + varepsilon D’ \
D’ = D – 2 (D cdot N) * N
end{array}
right.
]

In order to fight numerical precision errors, we are going to move the origin of the reflected point a little bit in the direction of the reflected ray ((varepsilon D’)). It will avoid to falsely detect a collision with the current object.

Coordinates, Groups and Rotations

We want to move and rotate objects. In order to do that, we compute a transformation matrix (and it’s inverse) for each object in the scene using the following code:

[
T = begin{array}{l}
(Identity * Translate_g * RotateX_g * RotateY_g * RotateZ_g) * \
(Identity * Translate_i * RotateX_i * RotateY_i * RotateZ_i)
end{array}
][ I = T^{-1} ]

[Translate(x, y, z) = left(begin{array}{c c c c}
1 & 0 & 0 & x \
0 & 1 & 0 & y \
0 & 0 & 1 & z \
0 & 0 & 0 & 1
end{array}right)]
[RotateX(alpha) = left(begin{array}{c c c c}
1 & 0 & 0 & 0 \
0 & cos(alpha) & -sin(alpha) & 0 \
0 & sin(alpha) & cos(alpha) & 0 \
0 & 0 & 0 & 1
end{array}right)]
[RotateY(alpha) = left(begin{array}{c c c c}
cos(alpha) & 0 & sin(alpha) & 0 \
0 & 1 & 0 & 0 \
-sin(alpha) & 0 & cos(alpha) & 0 \
0 & 0 & 0 & 1
end{array}right)]
[RotateZ(alpha) = left(begin{array}{c c c c}
cos(alpha) & -sin(alpha) & 0 & 0 \
sin(alpha) & cos(alpha) & 0 & 0 \
0 & 0 & 1 & 0 \
0 & 0 & 0 & 1
end{array}right)]

We have written the intersection and normal calculations in the object’s coordinate system instead of the world’s coordinate system. It makes them easier to write. We use the transformation matrix to do object -> world and the inverse matrix to do world -> object.

[
left{begin{array}{l}
O_{world} = T * O_{object} \
D_{world} = (T * D_{object}) – (T * 0_4)
end{array}right.
]
[
left{begin{array}{l}
O_{object} = I * O_{world} \
D_{object} = (I * D_{world}) – (I * 0_4)
end{array}right.
]
[0_4 = left(begin{array}{c} 0 \
0 \
0 \
1
end{array}right)
]


Bounding Box

The previous equations give us objects with infinite dimensions (except for the sphere) whereas objects in real life have finite dimensions. To simulate this, it is possible to provide two points that will form a bounding box around the object. On the intersection test, we are going to use the nearest point that is inside the bounding box.

This gives us the ability to do various objects such as mirrors, table surface and legs, light bubbles and even a Pokeball!


Light

An object is composed of an Intensity (I_o), a Color (C_o) and a Brightness (B_o). Each light has a Color (C_l) and there is an ambient color (C_a). Using all those properties, we can calculate the color of a point using the following formula:

[
I_o * (C_o + B_o) * left(C_a + sum_{l}{(N cdot D) * C_l}right)
]

Only the lights visible from the intersection point are used in the sum. In order to check this, we send a shadow ray from the intersection point to the light and see if it intersects any object.

The following images are examples to demonstrate the lights.


Textures

In order to put a texture on an object, we need to map a point ((x, y, z)) in the object’s coordinate system into a point ((x, y)) in the texture’s coordinate system. For planes, it is straightforward, we just the (z) coordinate (which is equal to zero anyway). For spheres, cylinders and cones it is a bit more involved. Here is the formula where (w) and (h) are the width and height of the texture.

[
begin{array}{c c}
phi = acos(frac{O’_y}{r}) & theta = frac{acosleft(frac{O’_x}{r * sin(phi)}right)}{2pi}
end{array}
][
begin{array}{c c}
x = w * left{begin{array}{l l} theta & text{if } O’_x < 0 \
1 – theta & text{else}end{array}right. & y = h * frac{phi}{pi}
end{array}
]

Once we have the texture coordinates, we can easily create a checkerboard or put a texture. We added options such as scaling and repeat in order to control how the texture is placed.


We also support the alpha mask in order to make a color from a texture transparent.

Progressive Rendering

Ray tracing is a slow technique. At first, I generated pixels line by line, but I found out that the first few lines do not hold much information.

Instead, what we want to do is to have a fast overview of the scene and then improve on the details. In order to do that, during the first iteration we are only generating 1 pixel for a 32×32 square. Then we generate 1 pixel for a 16×16 square and so on … We generate the top-left pixel and fill all the unknown pixels with it.

In order not to regenerate pixels we already seen, I came up with a condition to know if a pixel has already been generated. (size) is the current square size (32, 16, …).

[left{begin{array}{l}
x equiv 0 pmod{size * 2}\
y equiv 0 pmod{size * 2}
end{array}right.
]

Supersampling

Aliasing is a problem with Ray Tracing and we solve this issue using supersampling. Basically, we send more than one ray for each pixel. We have to chose representative points from a square. There are multiple strategies: in the middle, in a grid or random. Check the result of various combinations in the following image:

#supersampling-links strong { display: inline-block; width: 23px; text-align: right; }

$(‘#supersampling-links span’).click(function () {
$(‘#supersampling’).css(‘background-position’, ‘0px ‘ + (- 300 * +$(this).attr(‘data-id’)) + ‘px’);
});

Perlin Noise

We can generate random textures using Perlin Noise. We can control several parameters such as (octaves), the number of basic noise, the initial scale (f) and the factor of contribution (p) of the high frequency noises.

[ noise(x, y, z) = sum_{i = 0}^{octaves}{p^i * PerlinNoise(frac{2^i}{f}x, frac{2^i}{f}y, frac{2^i}{f}z)} ]

[noise] [noise * 20 – lfloor noise * 20 rfloor] [frac{cos(noise) + 1}{2}]

As seen in the example, we can apply additional functions after the noise has been generated to make interesting effects.

Portal

Last but not least, Portals from the self-titled game. They are easy to reproduce in a Ray Tracer and yet, I haven’t seen any done.

If a ray enters portal A, it will go out from portal B. It is trivial to implement it, it is just a coordinates system transformation. Like we did for world and object transformation, we do it between A and B using their transformation matrix.

[
left{begin{array}{l}
O_{a}’ = T * O_{b} \
D_{a}’ = (T * D_{b}) – (T * 0_4)
end{array}right.
]
[
left{begin{array}{l}
O_{b}’ = T * O_{a} \
D_{b}’ = (T * D_{a}) – (T * 0_4)
end{array}right.
]

Scene Editor

In order to create scenes more easily, we have defined a scene description language. We developed a basic CodeMirror syntax highlighting script. Just enter write your scene down and press Ray Trace πŸ™‚

I’ve been working on code that works on Browser, Web Workers and NodeJS. In order to export my module, I’ve been writing ugly code like this one:

(function () {
  /* ... Code that defines MyModule ... */
 
  var all;
  if (typeof self !== 'undefined') {
    all = self; // Web Worker
  } else if (typeof window !== 'undefined') {
    all = window; // Browser
  } else if (typeof global !== 'undefined') {
    all = global; // NodeJS
  }
  all.MyModule = MyModule;
 
  if (typeof module !== 'undefined') {
    module.exports = MyModule;
  }
})();

var all;
if (typeof self !== ‘undefined’) {
all = self; // Web Worker
} else if (typeof window !== ‘undefined’) {
all = window; // Browser
} else if (typeof global !== ‘undefined’) {
all = global; // NodeJS
}
all.MyModule = MyModule;

if (typeof module !== ‘undefined’) {
module.exports = MyModule;
}
})();

One-line Solution

Guillaume Marty showed me that sink.js uses this as a replacement for self, window and global. I managed to add support for module.exports in a one-liner!

(function (global) {
  /* ... Code that defines MyModule ... */
 
  global.MyModule = (global.module || {}).exports = MyModule;
})(this);

global.MyModule = (global.module || {}).exports = MyModule;
})(this);

I have been looking for this magic line for a long time, I hope it will be useful to you too πŸ™‚

Simulated Annealing Project

For a school project, I have to implement Simulated Annealing meta heuristic.

Thanks to many open source web tools, I’ve been able to quickly do the project and have a pretty display. CoffeeScript, Raphael, Highcharts, Three.js, Twitter Bootstrap, jQuery and Web Workers.

.hover-border img { border: 1px solid transparent; } .hover-border a:hover img { border: 1px solid #DB5104; }

2D Demo

You have a shuffled grid and you have to find the original grid. The only operation available is to swap 2 random elements. The cost function is the distance of the point with their original neighbors.

3D Demo

On this one, we are given many functions and we have to find the global minimum. The challenge was to be able to display the evolution of the algorithm, as it traverses 200k points per second.

CoffeeScript Sexyness

I’ve written the project in CoffeeScript and I don’t regret it. I find myself writing code a lot faster because I have a lot less to type. Most of the Javascript syntax is either shortened (function to ->) or optional (parenthesis, curly brackets …) in CoffeeScript. There are also handy features such as splats, generators …

Destructuring Assignment

worker.onmessage = (data: [id, rest...]) ->
  switch id
    when 'update'
      [cost, temperature, accepted, tried, data, force] = rest

Trimmed JSON

chart = new Highcharts.Chart
  chart:
    renderTo: 'container'
  yAxis: [
    title:
      text: 'Cost'
  ]
  tooltip:
    formatter: ->
      this.series.name + ': ' + this.y

Report

Felix Abecassis wrote a report that explains everything πŸ™‚ It’s in French, sorry!

Download PDF

6 months ago, I wrote the blog post “JSPP – Morph C++ into Javascript“. My supervisor at the LRDE (R&D Lab of EPITA), Didier Verna, found it interesting and told me that it could be worth a publication. With his great help, I’ve written my first article. We have submitted it to two conferences (one after the other) and received two refusals.

Overall, the reviewers said the article was well written and the implementation interesting but since it has no practical use, it does not deserve a publication.

Even if it didn’t make it, I’m really proud of the article. If you are interested in the implementation of JSPP, it can be an enlightening read πŸ™‚

Download PDF

(For copyright issue, this is not the submitted version of the file. There are still some minor wording issues)