Canvas is a javascript utility that allows one to create a fully interactive media environment inside a web browser, without the help of flash or any other sort of required plug-in. Consider the example you can find at this site, which simulates a bunch of blobs that behave according to physics.

An excellent tutorial on physics on Canvas is written by the same guy who created the blobs. This project is meant to further explore the means of physics in games. In the format of a number of small tutorials, we will be attempting to make the method of separating axes work in Canvas, and then, depending on time constraints, create a few small applications to show the things that are possible with it. Perhaps also making use of css. For a small explanation of how the Method of Separating axes works, this document might be helpful.

First we have to create a basis to start off with. For that, we will use a modified version of a simplified version used in the Blob Sallad-application, which you can find here. It operates in pretty much in the same way as the particle system of Thomas Jakobsen: there are a number of particles, connected by joints.

This version should be adequate and yet simple enough to start playing with the method of separating axes. Some modifications are that the particles and joints are stored in arrays, and some of the spring constraints are toned down, since they are not important for the subject of this tutorial. All the data structures of Pointmasses and Joints can be found in the file article.js, and you can find the page with the example here (.txt).

The first thing that now needs to be done in order to make the method of separating axes work is that given an axis and a point, you need to determine whether that point is on the left or the right side of that axis. In the context of this project, this means that we need to determine for an edge of the triangle and a point of the other triangle, whether or not this point lies on one side of the edge, or the other.

This is done with the help of vectors. We first compute the normal vector of the edge. If the edge has coordinates (x,y), then the normal vector has the coordinates(y,-x). Then we take the vector of the distance between one of the outer points of the edge and the point we already had, and compute the dot product of this vector and the normal vector. The result is positive if the point is on one side of the edge, and negative on the other.

To watch a demonstration of this, just go to the following page (.txt). The value on the top is this dot product, and it becomes positive if the top point of the larger triangle is on the opposite side of the long edge of the smaller triangle, compared to the rest of the body of the triangle. Do note for some reason, firefox doesn't like the ctx.filltext() command, and it has its own command for making text appear on the screen. You need to take that into account when working with Canvas.

In order to achieve collision detection, we need to make use of a number of for-statements: for every edge of both of the shapes, we need to check whether all of the points of the opposing shape are positioned outside of the edge. If there is such an edge, then that means that there is an axis so that all of the points of the first shape fall on one side of the axis, and all of the points of the second shape fall on the other side of this axis. And that means that there is a collision.

This is illustrated in the following example (.txt). Here we have the two triangles again, and this time the text on the top-left of the page shows the text "A collision" when the two shapes have collided or overlapped with each other, while it shows the text "No collision" when they don't.

There is however one nasty bug that you need to take into account. With blobsallad's base that we chose for this algorithm, it's possible to turn triangles inside-out fairly easily. Making sure that this same method works with inside-out triangles isn't trivial. For example, you can make the algorithm work correctly by reversing the array that contains the points for this triangle (which is possible because of the the algorithm presented by Eberly dictates that the points need to be ordered counter-clockwise), but how do you determine whether a triangle is normal, or inside-out?

The solution we propose is not a perfect one, but it will suffice for now. Generally, when a triangle flips inside-out, in the transition it will have a point at which its three points form one line. This point is easy to check: just check whether or not the sum of the two short edges is the same as the long edge. This method works reasonably well as long as you don't try to flip the triangles too fast, or try to make them bounce into walls too hard. In practice, you're going to need to implement a constraint that will never allow a joint to shrink below a certain size, but that is beyond the scope of this tutorial.

Now that we know when a collision happens, this section will discuss the collision reaction, so that our two objects interact with each other. You can find the example here (.txt). The example mentioned isn't perfect; there's one bug that prevents the collision reaction from working properly around the parts of the edges very close to the points of their respective triangle, but more on that later. This should be good enough to explain some of the principles.

For collision reaction, it is not sufficient anymore to just know when a collision has happened, but you also need to know which point has collided with which side. One way to do this is that, whenever a collision is known, to check for each edge whether there exists a point on the opposite triangle that lies on the same line as that edge (simply by checking whether |edge| - distance(point, edgePointX) - distance(point, edgePointY) is larger than a certain number).

Once you have found this edge, you need to adjust the position of both the triangles so that they don't collide with each other anymore. we chose to simply move both triangles with a fixed value, with the movement of the edge adjusted with the value as explained in section five in Thomas Jakobsen's article: suppose the point hits the edge 25% to the right, then the right side of the edge will be adjusted by 0.75 times a certain value, and the left side will be adjusted by 0.25 times that certain value.

Through trial and error, we found that this value is 0.04, and during each loop, the position of both triangles get adjusted with this value or the opposite of this value, respectively. Because the pointmasses don't store their velocity, but only their current and previous position, in order to stop their movement we simply change the previous position to have the same values as the current position (we had to edit article.js slightly in order to provide a function for Pointmasses to be able to do such a thing).

However, there still are a number of constraints that need to be taken into account. For example, when the point comes too close to a second edge (which is often the case when it hits the triangle near one of its points), the algorithm will also be executed for this edge. That's why a constraint is implemented that checks which edge is closest to the point, and then executes the algorithm on that side, and that side only.

As the final part of this tutorial, we show an example of a small game in which this algorithm is used. It's a very simple game in which the user has to control one of the triangles with the arrow-keys, while avoiding the other triangle for as long as possible. This is simply done by adding a force to the triangle you're controlling when one of the arrow keys is pushed in. Every iteration, the other triangle moves slightly towards one of the points of the triangle you're controlling, giving the illusion that it's constantly following it.

When the game is completed, the player is directed to a page of high scores. the highscorse are simply stored in a plaintext file, and the page shows the ten highest scores. Sending the data through the pgp _GET-function is a very unsafe way, but it is one of most simple ways to write data to a file, especially since Javascript requires different functions for different browsers and operating systems in order to accomplish the same.

You can find the game here (.txt). The page with highscores can be found here (.txt).

The provided examples are by no means perfect. Especially the example of section four has one major bug in that when the point of collision on an edge gets too close to the edge's points, the algorithm fails. The reason for this is simple: because of the shaking that comes from the very unstable collision reaction, there actually comes a point at which one of the opposing edges of the triangle becomes the closest the point in question (because the differences in distance around the points of the triangle are so small already, a small shock can make the algorithm think that triangle has collided with a completely different edge). Due to time constraints, I have been unable to implement a good solution for this problem.

Therefore, one of the most important things to take into account when creating a collision detection system is the frame rate. Most of the bugs, problems and inaccuracies in this project were caused by the low frame-rate, which made it very difficult to accurately predict when a collision exactly happened, especially at high speeds. In contrast, when you work in a fast environment that can handle a fast frame-rate, your code will look much more simple and concise, and the collision detection will also look much more smooth.

One suggestion for future improvement would be to modify the article.js, so that each pointmass doesn't just store its current and previous position, but also its next, so that you'd be able to know in advance when a collision is going to happen. If you know that in the next frame, a collision is going to happen, you can simply halt the movement of the point in question, without having to adjust its position, and this will eliminate the shaky movement that you can see in the fourth example.

Once you have the collision detection working properly, the challenge is going to be make the system work with more than two objects, which will also bring its share of challenges. A simple 2-dimensional array will be able to store all of the position of the shapes you're working with, but a major issue becomes efficiency: canvas already isn't the fastest application around, and if you want to check whether a large amount of objects are colliding, you will have to implement some smart optimization algorithm to keep everything running smoothly. The method for separating axes is short enough to handle it, but when taking the rest of the code used to satisfy the collision reaction into account, the algorithm will start lagging with only relatively few objects.

I personally learned a lot creating this semi-tutorial. Before starting this project, I already studied the theory of Eberly's Method of Separating Axes, and from the outside it seemed like an easy task to implement. However, these expectations turned out to be completely wrong when I kept running into problems, bugs and things I overlooked while studying the algorithm. Actually implementing the method has taught me a lot about how collision detection actually works.

I could have chosen a more stable environment than Blobsallad, but on the other hand working in such a limited environment as Canvas has shown me much more of much more of the ins and outs of collision detection. If I tried to implement it in, for example OpenGL, it would have looked much more like an average programming exercise.

It was also a valuable experience getting to know the Canvas environment, and the way it can display all kinds of graphics in a simple javascript browser. It's not perfect yet, but it has a lot of potential for the future. My biggest issue was that Firefox didn't seem to accept the filltext() command (the command that puts text on the screen), and has its own methods for that. Even if Firefox for some reason couldn't handle the command with that particular syntax, wouldn't it have been relatively easy for the developers to just route the filltext(text, x, y)-syntax to a syntax it can handle, instead of completely rejecting it and causing many potential compatibility issues?