JavaScript - Separating Axis Theorem - Collision working, but not Response?

Question

So, I am trying to apply response to my SAT, Circle - Poly, Poly - Poly collisions. I ported this code on this article to JavaScript:

http://rocketmandevelopment.com/blog/separation-of-axis-theorem-for-collision-detection/

Now, the detection works on all types, but the response fails and goes with an insane speed and in wrong angle, it's not dependent by the mass of the objects (area^2 instead of mass) and angular velocity isn't applied

JSFiddle (gravity not applied for simulation, move with arrow keys), the first part in JS is the Vectors then the Physics and then the Main.

This is my definition of shapes: (had to add some code for "JSFiddle" link :P)

var Circle = function(body, c, r, cor, cof) {
    this.body = body // Static or dynamic
    this.c = c; // Center
    this.r = r; // Radius
    this.m = getCMass(r); // Mass = Area
    this.v = new Vector(); // Velocity
    this.cor = cor; // Coefficient of restitution
    this.cof = cof; // Coefficient of friction
    this.a = 0; // Angle
    this.av = 0; // Angular velocity
    this.type = "Circle";
}

var Polygon = function(body, c, vs, cor, cof) {
    this.body = body // Static or dynamic
    this.c = c; // Center
    this.vs = vs; // Vertices
    this.m = getPMass(vs); // Mass = Area
    this.v = new Vector(); // Velocity
    this.cor = cor; // Coefficient of restitution
    this.cof = cof; // Coefficient of friction
    this.a = 0; // Angle
    this.av = 0; // Angular velocity
    this.type = "Polygon";
}

function getCMass(r) { // More like, getCArea
    return (r * r * Math.PI);
}

function getPMass(vs) {
    var area = 0;
    var j = vs.length - 1;

    for (var i = 0; i < vs.length; i++) {
        area += (vs[j].x + vs[i].x) * (vs[j].y - vs[i].y); 
        j = i;
    }

    return (area / 2);
}

All Collision functions give failed response results so there must be some kind of connection.

Back to the angular velocity I know how to rotate polygons, but I am looking to get the new av after the collision:

px = x * cos(a) - y * sin(a); 
py = x * sin(a) + y * cos(a);

Also I made a nice physics simulator for lines and beziers it might help: http://murplyx.net/projects/csb/

So the most important part in this for me is how am I going to fix so that the velocity goes correctly by speed and angle? (I am using Vectors not Trigonometry -.-) Then I can think about mass and angular velocities. Thanks. I stay out of the Box2D box.

EDIT: Added functions that calculate the area^2 to set the mass as equal.

Nittygritty

270 -` 200` = 70 (rep) O_o – Unquote

O_o I had 470 rep in the beginning 270 + 200 = 470 :P – Nittygritty

Good Job.You are earning and selling :) – Unquote

Answer 1

In the circle circle collision function getCCCol(a, b) you are calculating a.center - b.center which is the vector between the centers and you are then scaling it by a scalar representing the overlap of the two circles measured in units of length along the vector between the centers of the circles. I am unable to understand what this vector is supposed to mean but it is something representing a length or a kind of oriented area.

In update() you then add - in case of a collision - the valued mentioned above to the velocity of the circles if they are not fixed. Adding velocities and lengths (or areas) makes no sense. What you really want to do is to change the velocity vectors of the objects depending on their current velocities, the contact plane between them, their masses and maybe their elasticizes. This may also require running the simulation backwards for some time to remove the overlap of the objects due to your fixed time steps. So for example for two fully elastic circles of equal mass colliding head on you just want to reverse the velocity vectors but not add anything to them depending on the geometry of the collision.

The same goes for getPCCol(p, c) and getPPCol(a, b) where you are again calculating some kind of distance that gets then added to the velocities in case of an collision. What are those values intended to represent?

In the end there is not a single issue I can point you at that will fix the problems. The code updating the velocities in case of a collision does not match the physics behind that process. I also really suggest to explicitly introduce a time step because your position update step position = position + velocity really should be position = position + velocity x timestep. By making this explicit, even if you choose it to be one, you can more easily check if the units of your calculations make sense.

It is probably also a good idea to rethink how you are performing the simulation. Instead of going forward one fixed time step and then backing up in the case of a collision - you are currently not doing this but you probably will have to do this sooner or later - first calculate the time of the next collision and then only advance the simulation to this point. Right now, if velocities are high or objects small enough, your objects can pass through each other if one time step advances an object a distance larger than the dimensions of the supposed collision partner in the direction of the velocity. Your fixed time step approach can be good enough if you are simulating particles and therefore collisions are not an (big) issue, but if you have to handle collisions using a fixed time step is just not good enough.

I hope this helps and of course feel free to ask if something is unclear or requires further elaboration.

---

This is how I would probably try to implement rigid body dynamics, i.e. the order in which I would add features. Every step adds more or less just one feature but they are all way more complex then it may sound. There are thousands of pages of research for every step and tens or hundreds of implementation alternatives.

1. Particle dynamics without angular momentum

   Define particles with their mass, (center of mass) location and velocity. Simulate their movement and the response to a force acting on the center of mass with a simple integration algorithm.

2. Particle dynamics with angular momentum

   Add the inertia tensor and angular velocities. Consider using quaternions. Implement response to a force acting on any point instead of just the center of mass.

3. Rigid body dynamics with collisions

   Implement a collision search algorithm that predicts the time of collisions and the collision point. Calculate the collision response using a simple model like the impulse-based contact model. This will probably require introducing time step subdivision.

4. Rigid body dynamics with friction

   Add a simple model of friction like Coloumb friction.

5. Add gravity and other force fields

   Here you have to decide if you want to have just a constant gravitational force or if you also want to calculate gravitational forces between objects. You could add gravity right after step 1 because it is just a force acting on the center of mass but because the gravitational force becomes infinite as two objects get closer and closer together the whole simulation easily explodes, i.e. your objects fly away with large velocities. Simulating gravity and other force fields usually requires more advanced integration algorithms. In general you will see that adding more features to the simulation usually increases the demands on the integration algorithm and you will get instabilities.

Cult

You are right about checking the old velocities and adding new, that's what I do in the resCCCol here: jsfiddle.net/4M94x. So we can skip the circle part then but both the PC and the PP still have the same problem. If you don't understand what they output you might want to go to the article link and check the // notes. I still don't understand how to implement the same thing as I did in my own resCCCol in the fiddle below as the polygons? – Nittygritty

Also thanks, that the velocity timestep might be too high and miss the collision I don't really care about now so that will be later, the most important thing is pretty much to get the new correct velocity. – Nittygritty

Good hint with the comments, sometimes you miss the obvious things. It turns out that the returned value is what I supposed but the linked article already contains a bug in the circle circle collision code (or omitted some pieces) and that confused me. I will update my answer later but in essence its the following - you have only code to detect collisions but no code at all to handle them. Your other working simulation made me believe you are experienced with physics simulations and therefore I did not look for something like that. – Hayseed

Well the Beziers are obviously not my code, but I ported it and implemented response. But I'm not really a physics master. So how should my code look like? Because I don't understand how it should look like. – Nittygritty

Without good understanding of physics you can not do this unless you find some code you can just port. You are missing collision response code and if you just have a look at Wikipedia you will realize that it is not really trivial. I can not provide you any code that you can just plug into your program because implementing that would probably take several days if not weeks to achieve good results. Realistically simulating physics is quite a hard problem. – Hayseed

I just need somewhere to start, any algorithm to find the intersection point. You don't have to give me code, but I just need to know how to do it and then I can code in several weeks what ever it takes it does not matter to me. An answer for this question would be to explain it not do it, but I need somewhat an explaination of how. – Nittygritty

The current algorithm is not really good for finding collision points because after one time step to objects will usually already overlap. You have to predict the time and position at which two objects will collide given their current positions, velocities and angular velocities. The internet is full of articles and papers but there is no single best solution. Here is an article for the simplest case of two circles because rotations don't matter in this case. – Hayseed

Here is a paper comparing different collision detection techniques. Here is a more informal comparison. Note that I just picked more or less random search results and can not really judge how good they are by just skimming them. But also note that this is all still collision detection; collision response calculations are only the next step. – Hayseed

You should also consider getting rid of your circles and approximate them with polygons because only having to deal with one kind of objects will probably make your code a lot simpler. Or start with circles only because they are much simpler to handle. – Hayseed

Have you read the papers? But circles are done as I said, but really, 192 pages? As well as approximating circles with polygons I can approximate polygons with circles. – Nittygritty

Polygons is the current problem at 100%, I can calculate new velocity, mass and even angular velocity with circles, c.av = col.normalize().cross(c.v) / c.r – Nittygritty

No, I only read a couple of interesting pages. And I don't think you will get away with 192 pages; I have never implemented rigid body dynamics, only particle dynamics but I am pretty sure I have read 1000+ pages to figure out what will and what will not work for my scenario. And particles are extremely easy compared to rigid bodies. I don't think you can approximate polygons easily with circles because you would have to introduce constraints preventing them from falling apart making the task even more complex. – Hayseed

So what am I going to do then to solve this problem? – Nittygritty

What do you want to use the code for? How exact and realistic does it have to be? Do you need friction? Is conservation of energy and (angular) momentum an issue? Gravity? Do you have to simulate contact times for angular momentum transfer of rotating circles? Can the geometry of objects change? Is the mass distribution of the objects uniform? I am asking because without knowing what the goal is it is hard to tell what to do next. – Hayseed

I just do it for fun, it don't have to be like Box2D at 101% but something like this: youtube.com/watch?v=qTV3ZQgTnkg – Nittygritty

Friction and power implementations go after – Nittygritty

Something like that in that video that you can "play around" with lol – Nittygritty

I added an outline of how I would probably go about such an implementation to my answer. It's really extremely rough because there are so many options for everything that I really can't say I would use this or that model. Most likely I would read papers and articles for weeks to figure out what may be a good choice at each step. The alternative is to look at an existing implementation and just copy their choices. – Hayseed

So you are saying that you do not know how to fix this problem? – Nittygritty

It's not about fixing a problem in your code; you have not implemented any collision response at all. So this is not a real bug, it is a missing feature. – Hayseed

A missing feature is also a problem. – Nittygritty

What's the problem then if you know what it's about? – Nittygritty

You are probably underestimating the amount of work required. It will probably take a whole day to get this working for circle circle collisions only. If I find enough time I will post a solution but I am not sure if I can manage to do this. – Hayseed

It would take no time for circle-circle collision because that's already done. It will take time for polygons, but that's the bounty. – Nittygritty

Do you have a newer version than what's on the linked JSFiddle? Because there it is obviously not working. – Hayseed

Obviosly that's why I asked the question -.- – Nittygritty

You just said it takes no time for circles because it is already done. Where? – Hayseed

Or no, why should I even? When I know that I know it works? Ok I just need the poly - poly and poly - circle now. – Nittygritty

jsfiddle.net/4M94x Here, as I said just leave the circle - circle part I don't need that anymore. – Nittygritty

Hello? The bounty ends in 4H – Nittygritty

All these, then you add I don't understand, can't you explain how? An answer means 1 answer and not 1000, 100 or 10 answers. – Nittygritty

Yes, you still need to correct that one, for instance as in jsfiddle.net/4XVPH. You are mixing a lot of different functionalities in your kitchen sink named update(). – Underpart

Yes the gravity calculation is wrong but collision is totally correct and that's the main thing. – Nittygritty

For simplicity I only want the collision resolution, gravity between bodies and timesteps are the next problem and have nothing to do with the current problem. – Nittygritty

I won't finish what I am working on until the bounty ends but I will update the answer once I am done and happy with the solution. Keep an eye on the question during the next week. – Hayseed

Hello? One week have gone -.- – Nittygritty

It have gone like a month, hello!?!?! – Nittygritty