Discussion :

[Invité]

Salut à tous!

Je suis actuellement entrain de finir mon moteur de jeux que j'ai commencé il y a déjà, quelques années en vue de développez un jeux.

Ayant presque terminé le moteur graphique (à part quelque trucs plus compliqués comme par exemple le chargement de modèles 3D, la génération de terrain en 3D, l'éclairage et le shading par pixel, etc...)
Que je ne compte pas faire tout de suite car je compte rester en 3D isométrique simple pour le moment. (Donc le rendu d'images en 3D dans un monde en 2D)

Le truc c'est que la caméra et les sommets sont en 3D mais la caméra reste en vue du dessus et je me sert de la position z comme hauteur, et plus les objets sont bas en y, plus ils sont haut en z. (Je me sert du z pour générer la heightmap, ainsi que la normal map à l'aide d'un shader et du rendu multi-passe)

Car je veux un moteur généraliste qui utilise le maximum de techniques qui sont similaire pour la 3D ainsi que pour la 2D.

Je suis entrain de faire le moteur physique, alors, j'ai visité ce lien (en Anglais) avec des exemples en flash : ici

Voici un autre lien inspiré du précédent : http://www.codezealot.org/archives/55 pour avoir un moteur qui gère à la fois les collisions en 2D et en 3D à l'aide d'une seule et même technique.

Mais je sèche un peu, en effet, le théorème de SAT est un peu long, et de plus, il ne fonctionne pas pour tester par exemple si un point est dans un polygone, est encore moins avec les sphere et les ellipsoïdes ou là, ça devient carrément plus compliqué.

J'ai donc décidé d'optimiser SAT en ramenant tout les test à un test du style rayon shere et ce pour toutes les formes.

Bref, j'ai donc tenter de faire un algorithme qui projette toutes les normales et les sommets du polygone sur le vecteur entre le centre du polygone et un autre point quelconque, voici l'algorithme qui se charge de ça :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
 static Vec2f projectShapeOnVector(Vec3f vector, std::vector<Vec3f> vertices) {
        float max = 0.f, min = 0.f;
 
        if (vertices.size() > 0) {
            Vec3f v = vertices[0].projOnVector(vector);
            max = v.projOnAxis(vector);
            if (max < min)
                min = max;
            for (int i = 1; i < vertices.size(); i++) {
                  Vec3f v = vertices[i].projOnVector(vector);
                  float p = v.projOnAxis(vector);
                  if (p < 0 && p < min)
                      min = p;
                  if (p > max)
                      max = p;
                }
            }
        }
        return Vec2f(min, max);
    }

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
bool BoundingPolyhedron::isPointInside(Vec3f p) {
     Vec3f d = p - center;
     float c = d.magnitude();   
     std::vector<Vec3f> v;
     for (unsigned int i = 0; i < points.size(); i++) {
        v.push_back(points[i] - center);
        v.push_back(normals[i]);
     }
     Vec2f pr = Computer::projectShapeOnVector(d, v);
     float r = Math::abs(pr.x) + Math::abs(pr.y);
     std::cout<<"rsum : "<<r<<" c : "<<c<<std::endl;
     if (r != 0 && r - c < 0)
         return false;
     return true;
}

Je redimensionne donc toutes les diagonales et les médianes du polygone suivant le cosinus de l'angle entre le vecteur d (vecteur entre le centre du polygone et un autre point) et la diagonale ou bien la médiane du polygone.
Je projette ensuite tout les vecteurs redimensionnés sur l'axe d.

Je recherche le maximum (il doit toujours être > 0) ainsi que le minimum (il doit toujours être < 0) par rapport à tout les vecteurs projetés.

Je prend la somme des deux (en prenant les valeurs absolue) et je la test avec la distance entre le centre du polygone et l'autre point.

Et enfin je compare ces 2 valeurs comme si je faisait un test pour savoir si un point est dans une sphere.

La deuxième technique concerne l'intersection d'un rayon avec une sphere :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
bool BoundingSphere::intersects (Ray &ray) {
    Vec3f d1 = ray.getExt() - center;
    Vec3f d2 = ray.getOrig() - center;
    Vec3f di[3], di2[3];
    float c = radius;
    di[0] = Vec3f(d1.x, 0, 0);
    di[1] = Vec3f(0, d1.y, 0);
    di[2] = Vec3f(0, 0, d1.z);
    di2[0] = Vec3f(d2.x, 0, 0);
    di2[1] = Vec3f(0, d2.y, 0);
    di2[2] = Vec3f(0, 0, d2.z);
    Vec3f di3[3];
    di3[0] = Vec3f (radius, 0, 0);
    di3[1] = Vec3f (0, radius, 0);
    di3[2] = Vec3f (0, 0, radius);
    for (unsigned int i = 0; i < 3; i++) {
        float r1 = di[i].projOnAxis(di3[i]);
        float r2 = di2[i].projOnAxis(di3[i]);
        float rSum = r1 + r2;
        if (rSum != 0 && c - rSum < 0)
            return false;
    }
    return true;
}

Et un autre pour l'intersection rayon, rayon :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
float Ray::intersectsWhere (Ray &other) {   
    Vec3f da = dir;
    Vec3f db = other.dir;
    Vec3f dc = other.orig - orig;
 
    if (dc.dot(da.cross(db)) != 0.f) // lines are not coplanar
        return -1;
 
    float s = dc.cross(db).dot2(da.cross(db)) / da.cross(db).magnSquared();
    if (s < 0 || s > 1)
    {
        return -1;
    }
    return s;
}

Voilà donc si quelqu'un peut corriger ou bien détecter des erreurs éventuelles je suis preneur, car, je sèche un peu. :/ (Je dois encore faire les tests entre sphere/polygone, polygone/polygone avec ma méthode de SAT optimisée, ainsi que ellipsoid/sphere, polygone et rayon (car la méthode de SAT doit faire beaucoup de tests sur beaucoup de normales surtout en 3D), mais je pense que j'ai trouvé comment géré cela en projetant les normales et vertex des 2 formes sur d et en faisant un test du genre collision entre 2 sphères.

Les méthodes :

cross calcule le produis en croix entre 2 vecteur.
dot : calcule le produit scalaire entre 2 vecteurs normalisés. (de longueur 1)
normals : ce sont les médianes des vecteurs. (les vecteurs entre les milieux des côtés du polygone et le centre du polygone)
points : ce sont les diagonales des vecteurs. (les vecteurs entre les sommets du polygone et le contre du polygone)
dot2 : même chose que dot mais ne normalise pas les vecteurs.
projectOnVector : projette un vecteur "a" sur un autre vecteur "b". (= a.dot(b) * a)
projectOnAxis : projette un vecteur "a" sur un axe "b". (= a.dot(b) * a.longueur())
magnitude : calcule la longueur du vecteur.
magnSquared : calcule la longueur du vecteur mise au carré.

Voilà si quelqu'un pense pouvoir optimisé ou remarque une erreur dans ces algorithmes je suis preneur.

Car je galère un petit peut pour faire ça de manière simple et généraliste.

[Kannagi]

Je suis étonné de lire que le chargement de modèle 3D est compliqué mais bref passons,
Sinon j'ai pas compris la démarche je suis pas doué en math mais si ton algo marche et que tu l'as testé je vois pas le souci , après chaqu'un a sa méthode.
Qu'appelle tu généraliste ? , bon parce que les type de collision en 2D marche en 3D , et inversement , en général le 'moteur physique' chez moi c'est juste un ensemble de test de collision (en 3D c'est seulement point/triangle ,cercle/triangle ,segment/segment et quelque autre).

si un point est dans un polygone

Bon ce test est facile a mettre en place ,et demande vraiment aucune connaissance particulière en math.

[Invité]

Bon, j'ai corrigé mon algorithme qui recherche si un point est dans un polygone : (En fait il y avait une erreur)

Il suffisait de projeter toutes les diagonales du polygone sur le vecteur entre le centre du polygone et le points, et rechercher la distance maximum parmi les vecteurs projetés.

Ainsi j'obtiens le rayon du polygone le plus proche du point p et je le compare avec la distance entre le centre du polygone et le point p.

Code cpp :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
static float projectShapeOnVector(Vec3f vector, std::vector<Vec3f> vertices) {
        float max = 0.f;
 
        if (vertices.size() > 0) {
            Vec3f v = vertices[0].projOnVector(vector);
            float p = v.magnitude();
            if (p > max)
                max = p;
            for (int i = 0; i < vertices.size(); i++) {
                Vec3f v = vertices[i].projOnVector(vector);
                float p = v.magnitude();
                if (p > max)
                    max = p;
 
            }
        }
        return max;
    }

Code cpp :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
 
Vec3f d = p - center;
     if (d.isNulVector())
        return true;
     float c = d.magnitude();
     std::vector<Vec3f> v;
     for (unsigned int i = 0; i < points.size(); i++) {
        v.push_back(points[i] - center);
     }
     float r = Computer::projectShapeOnVector(d, v);
     if (r != 0.f && r - c < 0.f)
         return false;
     return true;

Mais je pense qu'il y a moyen de réduire le nombre de projection avec la technique de Vorronoi en recherchant le point du polygone le plus proche du point p mais je sais pas de trop comment m'y prendre. :/

A part ça si j'applique cette technique pour toutes mes shapes ça baigne.

Un autre truc : cet algorithme ne semble pas fonctionner :

Code cpp :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
float Ray::intersectsWhere (Ray &other) {
    Vec3f da = dir;
    Vec3f db = other.dir;
    Vec3f dc = other.orig - orig;
 
    if (dc.dot(da.cross(db)) != 0.f) // lines are not coplanar
        return -1;
 
    float s = dc.cross(db).dot2(da.cross(db)) / da.cross(db).magnSquared();
    if (s < 0 || s > 1)
    {
        return -1;
    }
    return s;
}

Et je sèche un peu pour l'intersection entre 2 lignes en 3D.

Bref ce n'est pas que cela ne fonctionne pas en console mais ici je me retrouve avec des intersections là ou il y en a pas :

Code cpp :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
 
//Recherche l'intersection entre le triangle numéro n de la lumière et le segment s1.
void PonctualLight::checkInterTri (int n, Ray &s1) {
 
    int  i1 = -1, i2 = -1;
    Vec3f pointI1, pointI2;
    Ray s2;
    BoundingPolyhedron bp;
    //On crée un polygon qui est le triangle lumineux et on cherche si les côtés du triangle intersecte le segment.
    for (int k = 0; k < 3; k++) {
 
        Vec3f a ((*triangles[n])[k].position.x, (*triangles[n])[k].position.y, 0);
        Vec3f b;
        bp.addPoint(a);
        if (k == 2) {
 
            b = Vec3f ((*triangles[n])[0].position.x, (*triangles[n])[0].position.y, 0);
 
        } else {
 
            b = Vec3f ((*triangles[n])[k + 1].position.x, (*triangles[n])[k + 1].position.y, 0);
        }
 
        s2 = Ray (a, b);
 
        float iseg = s1.intersectsWhere(s2);
        float iseg2 = s2.intersectsWhere(s1);
        //std::cout<<iseg<<" "<<iseg2<<std::endl;
        //Si les segments sont en intersection, on recherche le(s) point(s) d'intersection. (2 points d'intersection maximum.)
        if (iseg > 0.f && iseg < 1.f || iseg2 > 0.f && iseg2 < 1.f) {
 
            if (i1 == -1) {
 
                i1 = k;
                if (iseg != -1)
                    pointI1 = s1.getOrig() + s1.getDir() * iseg;
                else
                    pointI1 = s2.getOrig() + s2.getDir() * iseg2;
            } else if (i2 == -1) {
 
                i2 = k;
                if (iseg != -1)
                    pointI2 = s1.getOrig() + s1.getDir() * iseg;
                else
                    pointI2 = s2.getOrig() + s2.getDir() * iseg2;
            }
        }
    }
    //Si il y a 2 intersection alors le segment intersecte le triangle complètement.
    //Sinon l'extrêmité du segment est dans le triangle.
    if (i1 != -1 && i2 != -1) {
        //On découpe les triangles.
        intersectsWallCompletely(pointI1, pointI2, i1, i2, n);
    } else if (i1 != -1 && i2 == -1) {
        //On recherche quel extrêmité du segment est dans le triangle.
        Vec3f orig = s1.getOrig();
        Vec3f ext = s1.getExt();
        std::cout<<"wall corner"<<std::endl;
        if (bp.isPointInside(orig)) {
            std::cout<<"orig inside"<<std::endl;
            std::cout<<"point : "<<pointI1<<std::endl;
            pointI2 = orig;
            intersectsWallCorner(pointI1, pointI2, n, s1, i1);
        } else if (bp.isPointInside(ext)) {
            std::cout<<"ext inside"<<std::endl;
            std::cout<<"point : "<<pointI1<<std::endl;
            pointI2 = ext;
            intersectsWallCorner(pointI1, pointI2, n, s1, i1);
        }
        //On découpe les triangles.
 
 
    }
}

Il me dit que je n'ai une seule intersection hors que aucun des 2 coins du segment n'est dans le triangle. (Ce qui est bien sûr impossible)
Du coup j'ai des triangles qui ne s'affichent pas.

[Kannagi]

La je suis étonné , je pensais pas qu'on pouvait sortir tout artillerie pour savoir si un point se trouve dans un triangle ,il y a pas mal de ressource sur le net qui traite du sujet.
Mais il y a une autre méthode plus simple (sans a avoir besoin d'utiliser Voronoi ), il suffit simplement de regarder si le point se trouve entre deux points des segments du triangle , puis de faire une simple comparaison.
En image ça donne ça :
Les coordonnées des points sont facile a connaitre , un segment est linéaire donc proportionnel.

Pour intersection de 2 lignes en 3d c'est assez particuliers comme situation (dans le sens en as tu réellement besoin ?) , jamais testé mais par logique je regarderai sur 2 vues différente intersection des 2 droite en 2D , et donc elle devrait avoir des coordonnées (en intersection communes) si c'est pas le cas elle ne se coupe pas.

[Invité]

Bon, j'ai corrigé mon algorithme pour savoir si un point est dans un polygone, ça ne marchait en effet pas avec les polygones qui n'ont aucun côté parallèle comme le triangle par exemple :

Code cpp :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
 static Vec2f projectShapeOnVector(Vec3f vector, std::vector<Vec3f> vertices, std::vector<Vec3f> normals) {
        float p1 = 0.f, p2 = 0.f;
        float dpMax = 0.f;
        int ind = 0;
        for (int i = 0; i < vertices.size(); i++) {
            float dp = vertices[i].dot(vector);
            if (dp > 0 && dp > dpMax) {
                Vec3f v = vertices[i].projOnVector(vector);
                p2 = v.magnitude();
                dpMax = dp;
                ind = i;
            }
        }
        float min = (int) normals[ind].projOnVector(vector).magnitude();
        float max = min;
        Vec3f n = (ind + 1 == normals.size()) ? normals[0] : normals[ind+1];
        Vec3f v = n.projOnVector(vector);
        if (v.magnitude() < min)
            min = (int) v.magnitude();
        if (v.magnitude() > max)
            max = (int) v.magnitude();
        float p = max - min;
        p1 = (p2 - p > 0) ? p : 0;
        return Vec2f(p1, p2);
    }

Code cpp :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
bool BoundingPolyhedron::isPointInside(Vec3f p) {
     Vec3f d = p - center;
     if (d.isNulVector())
        return true;
     float c = d.magnitude();
     std::vector<Vec3f> v;
     for (unsigned int i = 0; i < points.size(); i++) {
        v.push_back(points[i] - center);
     }
     Vec2f pr = Computer::projectShapeOnVector(d, v, normals);
     float r = pr.y - pr.x;
     if (r != 0.f && r - c < 0.f)
        return false;
     return true;
}

Suffit de prendre le sommet le plus proche du point, et les normales des segments partagé par ce point, projeter tout ça et retirer ce qui il y a de trop pour les polygone qui n'ont pas de côté parallèle comme par exemple, le triangle.

Je pense que je vais essayer de trouver un autre moyen plutôt que de faire un test d'intersection entre lignes 3D, le fait est que j'ai besoin des 2 intersections entre le rayon et le triangle si il y en a 2 ou bien d'une si il y en a qu'une seule.

J'ai donc pensé que itérer sur les segments du triangles et de chercher les intersections entre chaque segment du triangle et le rayon serait une bonne idée, c'est un cas un peu particulier. :X

Car j'ai besoin de chercher l'intersection avec les segments du triangles, et non pas le triangle lui même.

[Invité]

Bon finalement j'ai trouvé la solution :

Code cpp :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
float Ray::intersectsWhereOther (Ray &other) {  
    Vec3f da = dir;
    Vec3f db = other.dir;
    Vec3f dc = other.orig - orig;
    if (dc.dot(da.cross(db)) != 0.f) // lines are not coplanar
        return -1;   
    float s = da.cross(db).dot2(dc.cross(db)) / da.cross(db).magnSquared();
    float t = da.cross(db).dot2(dc.cross(da)) / da.cross(db).magnSquared();
    if ((s >= 0 && s <= 1) && (t >= 0 && t <= 1))
    {
        return t;
    }
    return -1;
}

Il fallait juste que je fasse un test supplémentaire, le 1er test n'étant pas suffisant.

Sinon, ce code-ci n'est pas encore très précis, mais je vois pas du tout comment projeter un triangle sur un vecteur et je n'ai trouvé aucune source là dessus. (J'ai juste trouvé des sources pour projeter un triangle sur un axe)

Code cpp :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
 static Vec2f projectShapeOnVector(Vec3f vector, std::vector<Vec3f> vertices, std::vector<Vec3f> normals) {
        float p1 = 0.f, p2 = 0.f;
        float dpMax = 0.f;
        int ind = 0;
        for (int i = 0; i < vertices.size(); i++) {
            float dp = vertices[i].dot(vector);
            if (dp > 0 && dp > dpMax) {
                p2 = vertices[i].projOnAxis(vector);
                dpMax = dp;
                ind = i;
            }
        }
        float min = (int) normals[ind].projOnAxis(vector);
        float max = min;
        Vec3f n = (ind + 1 == normals.size()) ? normals[0] : normals[ind+1];
        if (n.projOnAxis(vector) < min)
            min = (int) n.projOnAxis(vector);
        if (n.projOnAxis(vector) > max)
            max = (int) n.projOnAxis(vector);
        float p = max - min;
        //Si p2 - p vaut 0 ça veut dire que les segments partagé par la même diagonale sont symétrique par rapport à la //diagonale, dans ce cas il ne faut rien retrancher.
        p1 = (p2 - p > 0) ? p : 0;
        return Vec2f(p1, p2);
    }

[Invité]

Hé bah je suis bête.

Je n'ai qu'à réutiliser mon algorithme d'intersection entre rayons.

Code cpp :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
static float projectShapeOnVector(Vec3f vector, std::vector<Vec3f> vertices, std::vector<Vec3f> normals) {
        float dpMin = 0.f;
        int ind = 0;
        for (int i = 0; i < normals.size(); i++) {
            float dp = normals[i].dot(vector);
            if (dp > dpMin) {
                dpMin = dp;
                ind = i;
            }
        }
        Vec3f v1 = vertices[ind];
        Vec3f v2 = (ind + 1 == vertices.size()) ? vertices[0] : vertices[ind+1];
        Ray r1 (Vec3f(0, 0, 0), vector);
        Ray r2 (v1, v2);
        float s = r1.intersectsWhere(r2);
        if (s != -1) {
            Vec3f pi = r1.getOrig() + r1.getDir() * s;
            return pi.magnitude();
        }
        return 0;
    }

Voilà je prend le côté le plus prêt du point et je cherche l'intersection entre celui-ci et le rayon entre le centre du polygone et le point.

Ca me semble déjà plus correct et mon polygone est enfin projeté correctement!