[Résolu]Problème de collisions

[yhu420]

Bonjour tout le monde,

Je viens d'implémenter une fonction pour gérer les collisions entre deux formes convexes. Après deux heures de relecture, je ne parviens toujours pas à trouver le problème, pourtant je suis certain que ça ne tient pas à grand chose.
La fonction suivante renvoie systématiquement 'false'.

bool shapesCollideCustom(const sf::ConvexShape & first, const sf::ConvexShape & second)
{
        //https://openclassrooms.com/courses/theorie-des-collisions/formes-plus-complexes
        //article is in french, but is really helpful
        //Way easier and faster than the SAT everyone seem to talk about

        const std::size_t pointCount1 = first.getPointCount();
        const std::size_t pointCount2 = second.getPointCount();

        for (std::size_t i = 0; i < pointCount2; i++)
        {
                //Vector AB is vector point[i]point[i+1]
                //Here we are setting point A and point B

                //Point A = tab[i];
                sf::Vector2f B;
                if (i == pointCount2 - 1)  // si c'est le dernier point, on relie au premier
                        B = second.getTransform().transformPoint(second.getPoint(0));
                else           // sinon on relie au suivant.
                        B = second.getTransform().transformPoint(second.getPoint(i + 1));

                //vector D = vector AB
                const sf::Vector2f D(getVectorTwoPoints(second.getTransform().transformPoint(second.getPoint(i)), B));

                //Vector T = vector AP
                for (std::size_t j = 0; j < pointCount1; j++)
                {
                        const sf::Vector2f T(getVectorTwoPoints(second.getTransform().transformPoint(second.getPoint(i)), first.getTransform().transformPoint(first.getPoint(j))));

                        if (D.x*T.y - D.y*T.x < 0)
                                return false;  // un point à droite et on arrête tout.
                }
        }
        return true;  // si on sort du for, c'est qu'aucun point n'est à gauche, donc c'est bon.
}

Je vous remercie d'avance pour vos suggestions! 

[kimci86]

Il me semble que ta fonction vérifie que chaque sommet du polygone convexe A est contenu dans le polygone convexe B.
Cela est équivalent à tester si A est inclus dans B, pas à tester l'intersection.

Je crois que le plus simple serait de se baser sur le Separating Axis Theorem.

[victorlevasseur]

Mais le Separating Axis Theorem ne marche pas pour tous les polygones convexes.

[yhu420]

Ok, désolé pour la réponse plutôt lente, mais j'ai finalement trouvé la source du problème

Voilà la fonction corrigée:

//this will check if any point of second is inside first
bool shapesCollideCustom(const sf::ConvexShape & first, const sf::ConvexShape & second)
{
        for (std::size_t i = 0; i < first.getPointCount(); i++)
        {
                //Point A = tab[i];
                sf::Vector2f B;
                if (i == first.getPointCount() - 1)  // si c'est le dernier point, on relie au premier
                        B = first.getTransform().transformPoint(first.getPoint(0));
                else           // sinon on relie au suivant.
                        B = first.getTransform().transformPoint(first.getPoint(i + 1));

                const sf::Vector2f A(first.getTransform().transformPoint(first.getPoint(i)));

                //vector D = vector AB
                const sf::Vector2f D(getVectorTwoPoints(A, B));

               
                for (std::size_t j = 0; j < second.getPointCount(); j++)
                {
                        const sf::Vector2f T(getVectorTwoPoints(A, second.getTransform().transformPoint(second.getPoint(j))));
                        if (D.x*T.y - D.y*T.x < 0)
                        {
                                if (j == second.getPointCount() - 1)
                                        return false;
                        }
                        else
                        {
                                j = second.getPointCount();
                        }
                }
        }
        return true;
}

avec

sf::Vector2f inline getVectorTwoPoints(const sf::Vector2f& A, const sf::Vector2f& B)
{
        return sf::Vector2f(B.x - A.x, B.y - A.y);
}