Where to correct position in collision detection (best practice)

Hello dear JGO :slight_smile:

It is a rather small issue, but i didn’t really find an answer for it.

After all my grinding and checking how to implement collision detection/filtering/resolution etc., i don’t know what is the best way to actually correct the position after a collision was computed:

A.) Apply all forces(gravity/player input) -> calculate collision and correct the velocity --> apply the corrected velocity to the position
or
B.) Apply all forces(gravity/player input) -> apply the velocity --> calculate collision and the impulse resolution —> correct the position on the object

So my question really is whether i should apply the impulse resolution to the velocity or the position directly.

Thank you in advance already :slight_smile:

There really isn’t a huge difference, and there is no one single correct answer. Different people will prefer different approaches.

It also depends on the game- what kinds of collisions are you talking about?

Mostly, just make sure you catch all of the collisions you care about (don’t miss instances where you move through a barrier between frames, for example), and then go with whichever approach makes the most sense in your brain.

Any good collision detection will provide you with two pieces of information, a boolean which specifies the state of intersection, whether they intersect or not, and a property called as MTV (Minimum Translation Vector). This MTV is the vector that you add to the position of the first polygon or subtract in the case of the second polygon to move it out of intersection.

The way you calculate them depends on the algorithm you are using to determine collisions, such as SAT or GJK etc., What is the algorithm that you are following?

In the past, i have found just moving out of intersection + some damped velocity works best, depending on the level of accuracy of simulation. Moving it out means you don’t get accumulated velocity added frame to frame and eventually flies off at unrealistic velocity, add some velocity means it bounces off. Damping again just prevents everything from running away due to time quantization and rounding errors.

I am assuming a game, where accuracy is generally far less important than stablity/stupid results.

Hello guys, i’m so sorry for answering so late, had too much stuff to do :confused:
I really don’t like to ask a question, and then not even answer the people who try to help me, really sorry
Also, i will deviate from my original question, since that is as some of you referred, something depending on the situation and taste, though i have another more serious issue.

@KevinWorkman
I am using what makes most sense to my brain, but then i read up on collision detection, how the ‘big boys’ do it, then see what i’m doing differently and iterate my code of what i’ve understand better that time :stuck_out_tongue:

@SHC
I’m using SAT for the time being, but i think what i do is a ‘mix’ of some sort, it goes somewhat like this:

  1. Get distances between 2 objects from center points on X and Y axis (with the objects half sizes already considdered)
  2. SAT: if any of these distances (X or Y) is >= zero, then ignore and proceed to next iteration
  3. Get the axis of least penetration and also calculate the normal vector towards the first object (first array iterattion:‘primary’ and the second time:‘secondary’)
  4. Then on the found axis:
    Primary: primary.pos += normalpenetration
    Secondary: secondary.pos += normal
    penetration
    5)Generate collision events, and add them to the collider component (kind of the way unity does it)
    Note: I do this in different iterations: 1) Apply velocity to position 2) Collision detection and Manifold(Collision objects)creation 3) Correct positions directly

All this works great but i’ve got some issues i shouldn’t have, these are:

Problem A.) The least penetration(minimum displacement) axis sucks, if you use it in, lets say a platformer, and you jump and try to land on a tile, and the x axis is of least penetration,the character would be corrected on the x axis and continue dropping on the y axis. I’ve come across the least penetration vector method a LOT when researching, but for this reason alone, i guess i heave to use a different method!? (GJK…omg please no, don’t make me learn that :stuck_out_tongue: )
Is there any understandable method to make the displacement vector, to be correct?

Problem B.) Although now, i found a way to fix it without hacks. I’ll just put it up for you to control my ‘way of though’ and for others to read.
The same reason for Problem A, that collision objects get stuck on tiles, because of this damn minimum displacement. Now in tile based games (and others off course), that shouldn’t happen by not using rectangles for collision, but instead use four lines (aka. Edges). Note the following is used AABB(Axis aligned, so no rotations yet) at the moment!. One line has two points and a surface normal and is either assigned to be on the X or Y axis. Before collision i run through the objects and remove the line of the blocks that have a neighbour, removing the issue of getting stuck anywhere. Though this is nothing really striking, I found this to be a very nice method without hacking special cases, which i told myself to not use again(Simplicity > Hacks ^^)

Problem C.) Of all the stuff i’ve read, i still don’t know if only one or both objects should be corrected at any given time during a collision!? Important in this case is:
I’m implementing it in an entity component system. A collider has some options/data: static/trigger/material and has an array of collision that occured, other entity etc.(Again the way unity does it, more or less).
Please look at what i mean: http://answers.unity3d.com/storage/temp/2050-interactionmatrix.png
When are both objects moved usually?, i tend to only correct the primary object, but i feel to be hacking myself through thing, that should be rather simple.
Both?, only primary?, only secondary?, i’m clueless, everything kind of works(but requires it’s own hacks). I don’t want to go the full body/mass/force route just yet for a platformer :stuck_out_tongue:

@delt0r

For my current projects that’s the most important thing, and the minimal displacement vector is one of the stupid result, at least in a platformer :stuck_out_tongue: you know when you jump on it that: ‘damn this! i landed right on that???’ <-- That is something i want to avoid really really badly!
Also i will try with the damped velocites after collision, that should make stuff seem more fluid, until i get my math precision and timestepping going properly.

Thank you guys so much, i hope you can read through my issues really quick, this stuff has been bothering me a lot.

Greetings and all the best, JJ

I think your approach is not right, you just don’t check on X and Y axes, but the axes are formed by the perpendiculars of the edges in the polygon. These are all the axes that you must test whether it is a separating axis.


Vector2 tmpNormal = Vector2.REUSABLE_STACK.pop();

for (int i = 0; i < a.vertexCount(); i++)
{
    Vector2 e1 = a.getVertex(i);
    Vector2 e2 = a.getVertex((i + 1) % a.vertexCount());

    Vector2 edge = tmpNormal.set(e2).subtractSelf(e1);
    Vector2 normal = edge.perpendicularSelf().normalizeSelf();

    if (isSeparatingAxis(a, b, normal, response))
    {
        Vector2.REUSABLE_STACK.push(tmpNormal);
        return false;
    }
}

In the same way, you test the polygons with the axes from polygon B too. Only thing is that keep in mind that these vertices doesn’t contain the position of the polygon. The position is kept separate from the vertices, and is tested by the [icode]isSeparatingAxis[/icode] method.

According to the statement of separating axis theorem, “an AXIS is said to be a separating axis, if that axis, when extended in both directions, does not pass through the polygons”. To do this, we project the vertices on to that axis, and measure the projection, not the distance between the centers.


private static Vector2 flattenPoints(List<Vector2> vertices, Vector2 normal, Vector2 projection)
{
    float min = Float.MAX_VALUE;
    float max = -min;

    for (Vector2 vertex : vertices)
    {
        float dot = vertex.dot(normal);

        if (dot < min) min = dot;
        if (dot > max) max = dot;
    }

    return projection.set(min, max);
}

The above method [icode]flattenPoints[/icode] does exactly the same. It takes a list of vertices, a normal (that is, the axis), and another [icode]Vector2[/icode] to store the resulting projection. Now we know on what axes we need to test, and we also know the projection. What we need to find is whether the axis is a separating axis, or whether it intersects.

Sorry if this image looked shit, I drew it in MSPaint. If you look at the projection, the [icode]min[/icode] is the [icode]x[/icode] component, and [icode]max[/icode] is the [icode]y[/icode] component of the projection vector. So we can clearly say if they are separated by checking the line intersection of the projections.


if (rangeA.x > rangeB.y || rangeB.x > rangeA.y)
    return true;

This still doesn’t solve the issue of collision detection, it works fine if both polygons are positioned in the origin (top-left corner is the position, not the center). To solve this, we calculate an offset to the [icode]rangeB[/icode] and we add that offset to it.


Vector2 offset = tmpOffset.set(b.getPosition()).subtractSelf(a.getPosition());
float projectedOffset = offset.dot(axis);

rangeB.addSelf(projectedOffset, projectedOffset);

Now the intersection test works fine, we still need to calculate the collision response. Before we do that, I will show my [icode]Response[/icode] class to you, so that you understand what is what. It is actually somewhat large, so here is a link that points to this class in my SilenceEngine repository. Now, the idea is, we calculate the overlap distance, only if the axis is not a separating axis. The collision response calculation is rather long to explain here, so here is the code.


float overlap;

if (rangeA.x < rangeB.x)
{
    response.aInB = false;

    if (rangeA.y < rangeB.y)
    {
        overlap = rangeA.y - rangeB.x;
        response.bInA = false;
    }
    else
    {
        float option1 = rangeA.y - rangeB.x;
        float option2 = rangeB.y - rangeA.x;
        overlap = option1 < option2 ? option1 : -option2;
    }
}
else
{
    response.bInA = false;

    if (rangeA.y > rangeB.y)
    {
        overlap = rangeA.y - rangeB.x;
        response.aInB = false;
    }
    else
    {
        float option1 = rangeA.y - rangeB.x;
        float option2 = rangeB.y - rangeA.x;
        overlap = option1 < option2 ? option1 : -option2;
    }
}

overlap = Math.abs(overlap);

if (overlap < response.overlap)
{
    response.overlap = overlap;
    response.overlapN.set(axis.normalizeSelf());

    if (overlap < 0)
        response.overlapN.negateSelf();
}

In this piece of code, [icode]overlapN[/icode] is just the axis on which the overlap happened. To get the MTV, you need to scale the axis with the overlap, like [icode]response.overlapV.set(response.overlapN).scaleSelf(response.overlap);[/icode]. This is the MTV value.

Hope this helps.

Sorry for answering so late again!

And thank you so much for the precise answer, this really helped me a lot!
Collision detection is a bigger beast than it seemed :stuck_out_tongue:

Thank you guys again and all the best!