Discussion :

[MrPchoun]

Hello,

Je suis actuellement en train de coder une sorte de NavMesh : l'objectif est de réaliser la triangulation d'un espace en tenant compte d'éventuelles contraintes (des murs). Chaque triangle est stocké de la manière suivante : ses trois côtés sont représentés sous la forme d'HalfEdge, en gros, des cotés orientés. Un triangle est donc stocké sous forme de 3 vecteurs, chacun représentant un coté. Ces vecteurs sont créés de telle sorte que les points du triangle soient dans le sens des aiguilles d'une montre. Mais un schéma sera plus clair :

http://www.google.fr/imgres?imgurl=h...ed=0CHkQrQMwCw

Voilà. Sauf qu'ici les HalfEdge sont orientés dans le sens inverse des aiguilles d'une montre. Mais mon problème est très sommaire, en fait.

Voici ma classe Mesh, commentée et volontairement simplifiée :

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
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
 
class Mesh
{
 
private:
 
    struct HalfEdge
    {
        // first, c'est les coordonnées du point de départ de l'HalfEdge. Il pointe sur un élément de "points".
        sf::Vector2i* first;
        HalfEdge* next;
        HalfEdge* pair;
        bool fixed; // inutile ici, c'est juste pour savoir si l'HalfEdge est un mur ou non.
    };
 
    std::vector<HalfEdge> mesh;
    std::vector<sf::Vector2i> points;
 
public:
 
    /* IntRect est une classe de la bibli SFML : c'est un simple rectangle. left = coordonnées x du coté de tout à gauche, top = coordonnées en y du coté tout en haut, width = longueur et height = hauteur */
/* ce superRectangle que je construit est destiné à recevoir tous les autres points que j'insèrerai par la suite et qui devront être triangulés. */
    Mesh(sf::IntRect const &superRectangle)
    {
        // Encore une classe de la SFML : sf::Vector2i c'est comme un std::pair<int,int>, sauf qu'on écrit .x et .y pour .first et .second
        sf::Vector2i A,B,C,D;
 
        A = {superRectangle.left,superRectangle.top};                                               // haut-gauche
        B = {superRectangle.left+superRectangle.width,superRectangle.top};                          // haut-droite
        C = {superRectangle.left,superRectangle.top+superRectangle.height};                         // bas-gauche
        D = {superRectangle.left+superRectangle.width,superRectangle.top+superRectangle.height};    // bas-droite
 
        points = {A,B,C,D};
 
        // ici, je suis obligé de créer en avance les 6 éléments du vector, parce que les tous éléments pointent sur les autres.
        mesh.resize(6);
 
        mesh[0] = {&points[0],&mesh[1],NULL,true};          // 0
        mesh[1] = {&points[1],&mesh[2],&mesh[3],false};     // 1
        mesh[2] = {&points[2],&mesh[0],NULL,true};          // 2
        mesh[3] = {&points[2],&mesh[4],&mesh[1],false};     // 3
        mesh[4] = {&points[1],&mesh[5],NULL,true};          // 4
        mesh[5] = {&points[3],&mesh[3],NULL,true};          // 5
 
        /* Supposons maintenant que je veuille ajouter un HalfEdge qui partirait du point {50,50}, et dont le HalfEdge suivant serait celui qui part du point {0,0}. Voici ce que ça donne : */
        points.push_back({50,50});
        mesh.push_back({&points[4],&mesh[0],NULL,false});   // 6
 
        /* on vérifie que les insertions se sont faites normalement, et là c'est le drame... */
        this->test();
    }
 
    void test()
    {
        for (auto i : mesh)
        {
            std::cout<<"edge("<<i.first->x<<","<<i.first->y<<")->("<<i.next->first->x<<","<<i.next->first->y<<") | ";
            std::cout<<std::endl;
        }
    }
};
 
int main()
{
    Mesh mesh(sf::IntRect(0,0,800,600));
 
return 0;
}

L'insertion du 7ème HalfEdge ne semble pas se faire correctement, et je ne comprends vraiment pas d'où pourrait venir le problème.. Pourriez vous m'aider s'il vous plait

Cordialement,

[jo_link_noir]

Salut,

J'aurais tendance à dire que tous les points sauf le dernier sont valide. Quand un push_back est fait sur un std::vector, se dernier peut redimensionner sa taille et par conséquent invalider tous les itérateurs et pointeurs sur les éléments.
Par conséquent, les meshs précédent possèdent des pointeurs sur des valeurs de `points` qui n'existe plus.

[MrPchoun]

Salut,

Merci de ta réponse. En effet, je n'avais pas pensé à ça.. Du coup, dans ma structure HalfEdge, j'ai remplacé sf::Vector2i* first par sf::Vector2i first, et les points sont stockés directement dedans, au lieu de passer par un pointeur sur un vector de sf::Vector2i. Mais ça m'embête, ma structure devient plus lourde. Y aurait-il une autre solution, pour que ma structure garde sa légèreté, mais que le code reste aussi rapide ? Je les aimais bien moi, mes petits pointeurs

Cordialement,

[foetus]

Cela dépend si tu connais le nombre de points et de segments pour ta class Mesh dès le début, tu peux faire directement des tableaux C, alloués avec la bonne taille

[MrPchoun]

Justement, je ne le connais pas
Bon tant pis, c'est très bien comme ça de toutes façons, au moins, ça marche maintenant

Merci à tous les deux !

[foetus]

Sinon, ensuite tu peux simuler un std::vector

Un exemple

Code :

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

1
2
3
4
5
class Elt {
  sf::Vector2i points[X]:
 
  Elt* next;
};

Avec X à déterminer