Issue with using a ConvexShape's points like a VertexArray

[wh1t3crayon]

A while back I made a crude implementation of the Separating Axis Theorem, although I used the sf::VertexArray to represent an object. When adapting this to an actual project, I found that my objects on the screen were better off as sf::ConvexShapes, not VertexArrays. So I thought the adaptation for the SAT code would be straightforward, but it's not. The new SAT code using ConvexShapes always returns the overlaps of the shapes as zero. So somewhere in these two similar blocks of code, there is a bug that I seem to have missed when turning all the VertexArray code into ConvexShape code. Maybe all I need is a second pair of eyes, or maybe there's something between these two sf classes that I don't know about, but I'd appreciate it if somebody took the time to compare the two different code blocks. I'll post the before and after code.
The working SAT code, sf::VertexArray friendly:

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

#include "stdafx.h"
#include "SFML\Graphics.hpp"

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::Triangles);
        object.GetOutline().append(sf::Vertex(sf::Vector2f(200, 180)));
        object.GetOutline().append(sf::Vertex(sf::Vector2f(10, 180)));
        object.GetOutline().append(sf::Vertex(sf::Vector2f(10, 240)));
        //object.GetOutline().append(sf::Vertex(sf::Vector2f(200, 240)));

        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++){
                                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());

                                //but here, GetOverlap() actually returns a non zero number
                                float o = projectionOne.GetOverlap(projectionTwo);
                                if(o == 0.f){
                                        //no overlap
                                }
                                if(o < overlap){
                                        overlap = o;
                                        smallestAxis = axesTwo[i];
                                }
                        }

                        sf::Vector2f distance, aPos, bPos;
                        aPos = sf::Vector2f(object.GetOutline().getBounds().left + object.GetOutline().getBounds().width / 2, object.GetOutline().getBounds().top + object.GetOutline().getBounds().height / 2);
                        bPos = sf::Vector2f(objectTwo.GetOutline().getBounds().left + objectTwo.GetOutline().getBounds().width / 2, objectTwo.GetOutline().getBounds().top + objectTwo.GetOutline().getBounds().height / 2);
                        distance = aPos - bPos;

                        if(DotProduct(distance, smallestAxis) < 0.0f){
                                smallestAxis = -smallestAxis;
                        }
                       
                        for(int i = 0; i < objectTwo.GetOutline().getVertexCount(); i++){
                                objectTwo.GetOutline()[i].position -= (smallestAxis * overlap);
                        }
                }

                window.clear();
                window.draw(objectTwo.GetOutline());
                window.draw(object.GetOutline());
                window.display();
        }
        return 0;
}

 

And the new, not working SAT code, uses sf::ConvexShape in place of the VertexArray. That's the only change.

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

#include "stdafx.h"
#include "SFML\Graphics.hpp"

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::ConvexShape &shape, int index){
        sf::Vector2f vectorOne = shape.getPoint(index);
    sf::Vector2f vectorTwo;
        if(index >= shape.getPointCount() - 1)
                vectorTwo = shape.getPoint(0);
    else
                vectorTwo = shape.getPoint(index + 1);

    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::ConvexShape &GetShape(){ return shape; }
private:
        //this is the only major change, a vertex array to a convex shape
        sf::ConvexShape shape;
};

class Projection{
public:
        Projection(sf::Vector2f &axis, sf::ConvexShape &shape){
                min = DotProduct(axis, shape.getPoint(0));
                max = min;

                for(int i = 1; i < shape.getPointCount(); i++){
                        float proj = DotProduct(axis, shape.getPoint(i));
                        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.GetShape().setPointCount(3);
        object.GetShape().setPoint(0, sf::Vector2f(200, 180));
        object.GetShape().setPoint(1, sf::Vector2f(10, 180));
        object.GetShape().setPoint(2, sf::Vector2f(10, 240));
        object.GetShape().setFillColor(sf::Color::White);

        objectTwo.GetShape().setPointCount(4);
        objectTwo.GetShape().setPoint(0, sf::Vector2f(100, 0));
        objectTwo.GetShape().setPoint(1, sf::Vector2f(80, 0));
        objectTwo.GetShape().setPoint(2, sf::Vector2f(80, 20));
        objectTwo.GetShape().setPoint(3, sf::Vector2f(100, 20));
        objectTwo.GetShape().setFillColor(sf::Color::White);

        while(window.isOpen()){
                if(sf::Keyboard::isKeyPressed(sf::Keyboard::Escape)){
                        window.close();
                }
                if(sf::Keyboard::isKeyPressed(sf::Keyboard::Right)){
                        objectTwo.GetShape().move(.05, 0);
                }
                if(sf::Keyboard::isKeyPressed(sf::Keyboard::Left)){
                        objectTwo.GetShape().move(-.05, 0);
                }
                if(sf::Keyboard::isKeyPressed(sf::Keyboard::Down)){
                        objectTwo.GetShape().move(0, .05);
                }
                if(sf::Keyboard::isKeyPressed(sf::Keyboard::Up)){
                        objectTwo.GetShape().move(0, -.05);
                }

                if(sf::FloatRect(object.GetShape().getGlobalBounds()).intersects(sf::FloatRect(objectTwo.GetShape().getGlobalBounds()))){
                        std::vector<sf::Vector2f> axesOne;
                        std::vector<sf::Vector2f> axesTwo;

                        //for both shapes, get their axes
                        for(int i = 0; i < object.GetShape().getPointCount(); i++){
                                axesOne.push_back(GetNormalAxis(object.GetShape(), i));
                        }
                        for(int i = 0; i < objectTwo.GetShape().getPointCount(); i++){
                                axesTwo.push_back(GetNormalAxis(objectTwo.GetShape(), 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.GetShape());
                                Projection projectionTwo(axesOne[i], objectTwo.GetShape());

                                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.GetShape());
                                Projection projectionTwo(axesTwo[i], objectTwo.GetShape());

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

                        sf::Vector2f distance, aPos, bPos;
                        aPos = sf::Vector2f(object.GetShape().getGlobalBounds().left + object.GetShape().getGlobalBounds().width / 2, object.GetShape().getGlobalBounds().top + object.GetShape().getGlobalBounds().height / 2);
                        bPos = sf::Vector2f(objectTwo.GetShape().getGlobalBounds().left + objectTwo.GetShape().getGlobalBounds().width / 2, objectTwo.GetShape().getGlobalBounds().top + objectTwo.GetShape().getGlobalBounds().height / 2);
                        distance = aPos - bPos;

                        if(DotProduct(distance, smallestAxis) < 0.0f){
                                smallestAxis = -smallestAxis;
                        }

                        objectTwo.GetShape().move(-smallestAxis * overlap);
                }

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

        return 0;
}

 

So the second block of code should also prevent the two shapes from colliding, but nothing happens because I found out that the GetOverlap() function always returns 0.

[Nexus]

Sorry, but we won't debug hundreds of lines of code for you

You can try to reduce the code to a minimal example and isolate the problem. Or you step through with a debugger to see what's wrong -- something that should be a very usual and daily task for programmers.

I don't know why you are using SFML's graphics classes sf::VertexArray and sf::ConvexShape for collision detection in the first place. It's of course possible, but in a game architecture it can be an advantage to have separate data structures for game logics and graphics. And you would only have the logic you write yourself, making code simpler to understand and debug -- would definitely help in this problem here.

[wh1t3crayon]

I was able to narrow it down a lot, but I'm still confused. When creating my Projection objects, I can use a ConvexShape for the stationary object, but for the moveable object I have to send the vertex array. Here is what I mean

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

        sf::ConvexShape &GetShape(){ return shape; }
        sf::VertexArray &GetOutline(){ return outline; }
private:
        //this is the only major change, a vertex array to a convex shape
        sf::ConvexShape shape;
        sf::VertexArray outline;
};

class Projection{
public:
        Projection(sf::Vector2f &axis, sf::ConvexShape &shape){
                min = DotProduct(axis, shape.getPoint(0));
                max = min;

                for(int i = 1; i < shape.getPointCount(); i++){
                        float proj = DotProduct(axis, shape.getPoint(i));
                        if(proj < min){
                                min = proj;
                        }
                        else if(proj > max){
                                max = proj;
                        }
                }
                //std::cout << min << " " << max << "\n";
        }
        Projection(sf::Vector2f &axis, sf::VertexArray &shape){
                min = DotProduct(axis, shape[0].position);
                max = min;

                for(int i = 1; i < shape.getVertexCount(); i++){
                        float proj = DotProduct(axis, shape[i].position);
                        if(proj < min){
                                min = proj;
                        }
                        else if(proj > max){
                                max = proj;
                        }
                }
                //std::cout << min << " " << max << "\n";
        }
//...

};

//later in the collision checking code
Projection projectionOne(axesOne[i], object.GetShape());
//found it. why does object two need to send its outline?
Projection projectionTwo(axesOne[i], objectTwo.GetOutline());

So why is there a difference here between using a ConvexShape and VertexArray?

[Nexus]

What primitive type does your vertex array have? Please read the corresponding section in the tutorial and make sure you understand it correctly. You can't just have a 1:1 correspondance with triangles.

[wh1t3crayon]

The I set two vertex array primitives in the initial part of the code,

object.GetOutline().setPrimitiveType(sf::PrimitiveType::Triangles);
    //append points

    objectTwo.GetOutline().setPrimitiveType(sf::PrimitiveType::Quads);
    //append points
 

Even if I set them both to Quads, the ConvexShape code is still failing. The issue is in the Projection constructor(s). In the ctor that takes a ConvexShape, when I debug to look at the variables min and max, the min for some reason wants to be -0 sometimes. But in the exact same ctor that takes a vertex array, the min is set to where it should be (around 160.f if you collide the shapes by just holding the down arrow).

Edit: particularly, the second point in the convex shape, when used in the DotProduct function in Projection's ctor, results in -0 everytime. Actually, the first point's y position of the ConvexShape (objectTwo) is always -0. I'll show where I mean in the code

Projection(sf::Vector2f &axis, sf::ConvexShape &shape){
                min = DotProduct(axis, shape.getPoint(0)); //when Projection is being created from objectTwo
//(the moving object), this line always returns -0, because objectTwo's y coord is always -0. Why?
                max = min;
/*so this loop is called for every point the convex shape has, and on the second point it screws up:
on the first point, min == -180, which is what its supposed to be. However, the second time, min == -0.
 Moreover, when passed a vertex array instead, min == -160.005f, for the second point which is what it's supposed to be.*/

                for(int i = 1; i < shape.getPointCount(); i++){
                        float proj = DotProduct(axis, shape.getPoint(i));
                        if(proj < min){
                                min = proj;
                        }
                        else if(proj > max){
                                max = proj;
                        }
                }
        }

[wh1t3crayon]

Okay so I discovered something different entirely. Whenever I move() a ConvexShape, the values that GetPoint() returns stay the same.

sf::ConvexShape shape;
shape.setPointCount(1);
shape.setPoint(0, sf::Vector2f(20, 20));

sf::VertexArray otherShape;
otherShape.setPrimitiveType(sf::PrimitiveType::Quads);
otherShape.append(sf::Vertex(sf::Vector2f(20, 20)));
otherShape.append(sf::Vertex(sf::Vector2f(20, 20)));
otherShape.append(sf::Vertex(sf::Vector2f(20, 20)));
otherShape.append(sf::Vertex(sf::Vector2f(20, 20)));

std::cout << shape.getPoint(0).y << " "; //ALWAYS 20
shape.move(0, 50);
std::cout << shape.getPoint(0).y << "\n"; //ALWAYS 20, even though the shape was explicitly moved

std::cout << otherShape[0].position.y << " "; //20...
for(int i = 0; i < otherShape.getVertexCount(); i++){
        otherShape[i].position.y += 50;
}
std::cout << otherShape[0].position.y; //then 70, as I would expect
 

This really bugs me, no pun intended. Why don't the position values of a ConvexShape's points update when the shape is moved?

[Laurent]

What about reading the doc first?

The returned point is in local coordinates, that is, the shape's transforms (position, rotation, scale) are not taken into account.

[wh1t3crayon]

Thanks for pointing that out. What is a reasonable workaround for this? How would I get the global coordinates of the shape's points?

[Laurent]

http://www.sfml-dev.org/documentation/2.2/classsf_1_1Transformable.php#a3b48c3362e3e2c14fef7551252deb7bb
http://www.sfml-dev.org/documentation/2.2/classsf_1_1Transform.php#ac322cd8f6d606598d1aacc4d1d160ad6
http://en.sfml-dev.org/forums/index.php?topic=16971.msg121973#msg121973

 

[wh1t3crayon]

Thank you so much, it's working now. Don't take this as ingratitude because I'm quite grateful for the help, but why does @Lektor get the exact line of code he needs while I just get links and angry emoticons?

[eXpl0it3r]

Who is @Lektor?

If people show no efford in trying to figure things out, i.e. looking at the tutorial, the documentation and search the forum, they'll more likely get annoyed answers.

[Laurent]

From my point of view, a link to the appropriate documentation is more helpful than a line of code to copy and paste (and it takes me more time to find than writing the code directly). So I was actually even more angry when I replied to Lektor