How to react to a collision (wall-sliding)?

[wh1t3crayon]

I'm working out the basics oof the Seperating Axis Theorem, and using this code I found http://en.sfml-dev.org/forums/index.php?topic=12063.0 I was able to create this little program that works fine, in the respect that it simply returns whether the two objects collide. My question is, what do I do next to set the two objects apart from each other, but in the shortest distance possible. Most tutorials say "project one shape onto the axis of shortest distance between the two shapes" but I'm not sure how to do that code-wise. Here is the working program

// SFML Test.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "SFML\Graphics.hpp"
#include <iostream>

class Object : public sf::Drawable, public sf::Transformable{
public:
    Object() : shape( sf::TrianglesStrip, 6 ), verts( 4 ){
                //so this would create a sword (kind of) but other objects would instantiate these points as they see fit
        shape[0].position = sf::Vector2f(80, 100);
        shape[1].position = sf::Vector2f(80, 20);
        shape[2].position = sf::Vector2f(100, 100);
        shape[3].position = sf::Vector2f(100, 20);
        shape[4].position = sf::Vector2f(90, 10);
        shape[5].position = sf::Vector2f(80, 20);
    }
    sf::VertexArray& getShape()
                {return shape;}
private:
        virtual void draw(sf::RenderTarget& target, sf::RenderStates states) const
    {
        states.transform *= getTransform();
        target.draw( shape, states);
        for( int i = 0; i < verts.size(); i++ )
        {
            target.draw( verts[i], states);
        }
    }

        //each 2d shape will be made of various points, whether it is a simple square or a shape like a sword
    sf::VertexArray shape;
        //I think this is just for decoration, nothing required
    std::vector<sf::CircleShape> verts;
};

sf::Vector2f normalize( sf::Vector2f& input )
{
    if( sqrt(input.x*input.x + input.y*input.y) == 0 )
    {
        input.x = 1;
        return input;
    }
    float length = sqrt(input.x*input.x + input.y*input.y);

    input.x /= length;
    input.y /= length;
    return input;
}

sf::Vector2f getNormalAxis( sf::VertexArray& shape, int index )
{
    sf::Vector2f vector1 = shape[index].position;
    sf::Vector2f vector2;
    if( index >= shape.getVertexCount() - 1 )
        vector2 = shape[0].position;
    else
        vector2 = shape[index+1].position;

    sf::Vector2f normalAxis( -(vector2.y - vector1.y), vector2.x - vector1.x );
    normalAxis = normalize( normalAxis );
    return normalAxis;
}

float dotProduct( sf::Vector2f& vector1, sf::Vector2f& vector2 )
{
    return vector1.x*vector2.x + vector1.y*vector2.y;
}

bool sat( Object& shape1, Object& shape2 )
{
    sf::Vector2f vectorOffset( shape1.getPosition().x - shape2.getPosition().x, shape1.getPosition().y - shape2.getPosition().y );

    for( int i = 0; i < shape1.getShape().getVertexCount(); i++ )
    {
        sf::Vector2f axis = getNormalAxis( shape1.getShape(), i );

        float min1 = dotProduct( axis, shape1.getShape()[0].position );
        float max1 = min1;

        for( int j = 1; j < shape1.getShape().getVertexCount(); j++ )
        {
            float testNum = dotProduct( axis, shape1.getShape()[j].position );
            if( testNum < min1 )
                min1 = testNum;
            if( testNum > max1 )
                max1 = testNum;
        }

        float min2 = dotProduct( axis, shape2.getShape()[0].position );
        float max2 = min2;

        for( int j = 1; j < shape2.getShape().getVertexCount(); j++ )
        {
            float testNum = dotProduct( axis, shape2.getShape()[j].position );
            if( testNum < min2 )
                min2 = testNum;
            if( testNum > max2 )
                max2 = testNum;
        }

        float offset = dotProduct( axis, vectorOffset );
        min1 += offset;
        max1 += offset;

        float test1 = min1 - max2;
        float test2 = min2 - max1;

        if( test1 > 0 || test2 > 0 )
            return 0;
    }
    return 1;
}

int _tmain(int argc, _TCHAR* argv[]){
        sf::RenderWindow window(sf::VideoMode(500, 500, 32), "Test");

        Object object;
        Object objectTwo;

        objectTwo.getShape().resize(4);

        while(window.isOpen()){
                if(sf::Keyboard::isKeyPressed(sf::Keyboard::Escape)){
                        window.close();
                }
                if(sf::Keyboard::isKeyPressed(sf::Keyboard::Right)){
                        for(int i = 0; i < objectTwo.getShape().getVertexCount(); i++){
                                objectTwo.getShape()[i].position.x += .05;
                        }
                }
                if(sf::Keyboard::isKeyPressed(sf::Keyboard::Left)){
                        for(int i = 0; i < objectTwo.getShape().getVertexCount(); i++){
                                objectTwo.getShape()[i].position.x -= .05;
                        }
                }
                if(sf::Keyboard::isKeyPressed(sf::Keyboard::Down)){
                        for(int i = 0; i < objectTwo.getShape().getVertexCount(); i++){
                                objectTwo.getShape()[i].position.y += .05;
                        }
                }
                if(sf::Keyboard::isKeyPressed(sf::Keyboard::Up)){
                        for(int i = 0; i < objectTwo.getShape().getVertexCount(); i++){
                                objectTwo.getShape()[i].position.y -= .05;
                        }
                }

                /*you may want to change this if you don't like your console being flooded with outputs*/
                std::cout << sat(object, objectTwo);

                window.clear();
                window.draw(objectTwo);
                window.draw(object);
                window.display();
        }

        return 0;
}

 

So if the moving square runs into the complex shape, how would I reset the square just outside of the other shape? References to this code would be nice, but a link to a good tutorial on this would work just as well, thanks.

[dabbertorres]

You're looking for something called the "Minimum Translation Vector".

I like this page: http://www.dyn4j.org/2010/01/sat/#sat-mtv

I linked directly to the MTV part.

Basically, you take the axis of collision, multiply it with a factor of the overlap along that axis, and adjust the position of the shape with the result.

Here's my implementation if you want to take a look (Dependent on my ECS).

[wh1t3crayon]

When calculating the overlap of the shapes, the code in the tutorial just says

double overlap = // really large number;

What the heck does "really large number" mean? How did you end up calculating the overlap of the shapes?

[dabbertorres]

If you read further, it goes into that.

To calculate an overlap, you project both shapes onto an axis. Then, it's a simple subtraction problem.
https://github.com/dabbertorres/Swift2/blob/master/src/Collision/Projection.hpp#L42

He says "really large number" since, to calculate a min, you need a starting point. So, picking a "really large number" guarantees that your calculated overlaps will be smaller than it. (Well, *should* be).

[StormWingDelta]

I'd just make the really large number Data Type Max to save on headaches for calculating min.

[wh1t3crayon]

To calculate an overlap, you project both shapes onto an axis. Then, it's a simple subtraction problem.

That's something else I've struggled with. When you say "an axis" what do you mean? How do I decide what axis to use?

[dabbertorres]

The idea of the SAT is to create a list of axes to test on. Generally, an axis per side of each shape.

"an axis" refers to one of the generated axes.

You should generally pick the axis with the smallest projected overlap, because that is the shortest distance which you have to move the two shapes to "solve" the collision.

[wh1t3crayon]

Right thanks I get what to do there now.

Okay so let's say I have shapes that overlap and I find their MTV. If both shapes are static, then I just move one along the axis for the length of the mtv. But what if one shape has a velocity? How would I alter the shape's velocity so that it doesn't bounce right back into the wall the next frame?

[dabbertorres]

Well I'd just set it to 0. Or let it bounce back. It can just calculate the collision again, right?

[wh1t3crayon]

Here's the full program again, the problem is that the moving object isn't being pushed back out, rather the moving object seems to disappear off screen. If anybody could take a look at this and offer suggestions that would be much appreciated. Collision detection has made my head almost explode at this point.

The errors were due to a couple of transposed entries. I've updated the code to the working program in case anybody else reading this wants to see the SAT in action. The response is a little buggy, but as long as you don't try  to break this demonstration, it should teach something.

Code: [Select]

// SFML Test.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "SFML\Graphics.hpp"
#include <memory>
#include <iostream>

int loops = 0;

sf::Vector2f Normalize(sf::Vector2f& input){
if(sqrt(input.x * input.x + input.y * input.y) == 0){
        input.x = 1;
        return input;
    }
    float length = sqrt(input.x * input.x + input.y * input.y);

    input.x /= length;
    input.y /= length;
    return input;
}

sf::Vector2f GetNormalAxis(sf::VertexArray &shape, int index){
sf::Vector2f vectorOne = shape[index].position;
    sf::Vector2f vectorTwo;
    if(index >= shape.getVertexCount() - 1)
        vectorTwo = shape[0].position;
    else
        vectorTwo = shape[index+1].position;

    sf::Vector2f normalAxis(-(vectorTwo.y - vectorOne.y), vectorTwo.x - vectorOne.x);
    normalAxis = Normalize(normalAxis);
    return normalAxis;
}

float DotProduct(sf::Vector2f &vectorOne, sf::Vector2f &vectorTwo){
    return vectorOne.x * vectorTwo.x + vectorOne.y * vectorTwo.y;
}

class WorldObject{
public:
WorldObject(){}
~WorldObject(){}

sf::VertexArray &GetOutline(){ return outline; }
private:
sf::VertexArray outline;
};

class Projection{
public:
Projection(sf::Vector2f &axis, sf::VertexArray &vertices){
min = DotProduct(axis, vertices[0].position);
max = min;

for(int i = 1; i < vertices.getVertexCount(); i++){
float proj = DotProduct(axis, vertices[i].position);
if(proj < min){
min = proj;
}
else if(proj > max){
max = proj;
}
}
}
~Projection(){}

float GetMin(){ return min; }
float GetMax(){ return max; }

float GetOverlap(Projection &projection){
if(projection.GetMin() <= max && max <= projection.GetMax()){
return max - projection.GetMin();
}
else if(min <= projection.GetMax() && projection.GetMax() <= max){
return projection.GetMax() - min;
}
else{
return 0;
}
}
private:
float min, max;
};

int _tmain(int argc, _TCHAR* argv[]){
sf::RenderWindow window(sf::VideoMode(500, 500, 32), "Test");

WorldObject object;
WorldObject objectTwo;

object.GetOutline().setPrimitiveType(sf::PrimitiveType::Quads);
object.GetOutline().append(sf::Vertex(sf::Vector2f(200, 180)));
object.GetOutline().append(sf::Vertex(sf::Vector2f(180, 180)));
object.GetOutline().append(sf::Vertex(sf::Vector2f(180, 200)));
object.GetOutline().append(sf::Vertex(sf::Vector2f(200, 200)));

objectTwo.GetOutline().setPrimitiveType(sf::PrimitiveType::Quads);
objectTwo.GetOutline().append(sf::Vertex(sf::Vector2f(20 + 80, 0)));
objectTwo.GetOutline().append(sf::Vertex(sf::Vector2f(0 + 80, 0)));
objectTwo.GetOutline().append(sf::Vertex(sf::Vector2f(0 + 80, 20)));
objectTwo.GetOutline().append(sf::Vertex(sf::Vector2f(20 + 80, 20)));

while(window.isOpen()){
if(sf::Keyboard::isKeyPressed(sf::Keyboard::Escape)){
window.close();
}
if(sf::Keyboard::isKeyPressed(sf::Keyboard::Right)){
for(int i = 0; i < objectTwo.GetOutline().getVertexCount(); i++){
objectTwo.GetOutline()[i].position.x += .05;
}
}
if(sf::Keyboard::isKeyPressed(sf::Keyboard::Left)){
for(int i = 0; i < objectTwo.GetOutline().getVertexCount(); i++){
objectTwo.GetOutline()[i].position.x -= .05;
}
}
if(sf::Keyboard::isKeyPressed(sf::Keyboard::Down)){
for(int i = 0; i < objectTwo.GetOutline().getVertexCount(); i++){
objectTwo.GetOutline()[i].position.y += .05;
}
}
if(sf::Keyboard::isKeyPressed(sf::Keyboard::Up)){
for(int i = 0; i < objectTwo.GetOutline().getVertexCount(); i++){
objectTwo.GetOutline()[i].position.y -= .05;
}
}

//if(sf::FloatRect(object.GetOutline().getBounds()).intersects(sf::FloatRect(objectTwo.GetOutline().getBounds()))){
std::vector<sf::Vector2f> axesOne;
std::vector<sf::Vector2f> axesTwo;
//for both shapes, get their axes
for(int i = 0; i < object.GetOutline().getVertexCount(); i++){
axesOne.push_back(GetNormalAxis(object.GetOutline(), i));
}
for(int i = 0; i < objectTwo.GetOutline().getVertexCount(); i++){
//would call collision.getnormalaxis or whatevs
axesTwo.push_back(GetNormalAxis(objectTwo.GetOutline(), i));
}

//for both sets of axes
//project
float overlap = 50000000000;
sf::Vector2f smallestAxis;

for(int i = 0; i < axesOne.size(); i++){
Projection projectionOne(axesOne[i], object.GetOutline());
Projection projectionTwo(axesOne[i], objectTwo.GetOutline());

float o = projectionOne.GetOverlap(projectionTwo);
if(o == 0.f){
//no overlap
}
if(o < overlap){
overlap = o;
smallestAxis = axesOne[i];
}
}

for(int i = 0; i < axesTwo.size(); i++){
Projection projectionOne(axesTwo[i], object.GetOutline());
Projection projectionTwo(axesTwo[i], objectTwo.GetOutline());

float o = projectionOne.GetOverlap(projectionTwo);
if(o == 0.f){
//no overlap
}
if(o < overlap){
overlap = o;
smallestAxis = axesTwo[i];
}
}

for(int i = 0; i < objectTwo.GetOutline().getVertexCount(); i++){
//if it's moving in a negative dir, do this
if(sf::Keyboard::isKeyPressed(sf::Keyboard::Left) || sf::Keyboard::isKeyPressed(sf::Keyboard::Up))
objectTwo.GetOutline()[i].position -= (smallestAxis * overlap);
//otherwise do ditto += ditto
else if(sf::Keyboard::isKeyPressed(sf::Keyboard::Right) || sf::Keyboard::isKeyPressed(sf::Keyboard::Down))
objectTwo.GetOutline()[i].position += (smallestAxis * overlap);
}
//}

window.clear();
window.draw(objectTwo.GetOutline());
window.draw(object.GetOutline());
window.display();
loops++;
}

return 0;
}