IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Moteurs 3D Discussion :

Type de conteneur pour un scene node


Sujet :

Moteurs 3D

  1. #1
    En attente de confirmation mail
    Profil pro
    Étudiant
    Inscrit en
    Janvier 2008
    Messages
    56
    Détails du profil
    Informations personnelles :
    Âge : 37
    Localisation : France, Calvados (Basse Normandie)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Janvier 2008
    Messages : 56
    Points : 52
    Points
    52
    Par défaut Type de conteneur pour un scene node
    Bonjour à tous

    Quel type de conteneur me conseillez-vous pour une classe SceneNode, j'entend par SceneNode un noeud qui appartiendra à un arbre binaire, ou graphe de scène, en un mot c'est le même principe que pour Ogre.

    J'utilise actuellement un std::map comme ceci
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
     
    class _tchExport_ SceneNode
    {
         ...
         typedef std::map<std::string, SceneNode*> childrenNodeMap; 
         childrenNodeMap mChildren;
         ...
    }
    J'ai entendu dire qu'il faudrait mieux créer une table de hachage, qu'en est-il selon vous?

    Dernier question : est ce qu'un SceneNode peut avoir plusieurs fois le même SceneNode enfant ?

    Merci d'avance

  2. #2
    Membre éprouvé
    Avatar de Ange_blond
    Homme Profil pro
    Ingénieur développement en 3D temps réel
    Inscrit en
    Mars 2007
    Messages
    902
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations professionnelles :
    Activité : Ingénieur développement en 3D temps réel
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Mars 2007
    Messages : 902
    Points : 1 179
    Points
    1 179
    Par défaut
    Si un node a plusieurs fois le même enfant y'a un soucis je pense... sauf erreur de ma part c'est le signe d'un probleme dans ton graph.

    et la différence entre une map et une hashmap ? par sur de la connaitre...

    Sinon tu fait un vector, et tu gonfle un peu tes classes node de champs tels que le nom, l'ID, ...

  3. #3
    Expert éminent sénior
    Avatar de Mat.M
    Profil pro
    Développeur informatique
    Inscrit en
    Novembre 2006
    Messages
    8 405
    Détails du profil
    Informations personnelles :
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : Développeur informatique

    Informations forums :
    Inscription : Novembre 2006
    Messages : 8 405
    Points : 20 534
    Points
    20 534
    Par défaut
    J'ai entendu dire qu'il faudrait mieux créer une table de hachage, qu'en est-il selon vous?
    A ma connaissance c'est un peu la même chose...std::map<=>table de hachage .

    Le principe c'est d'après une clé donnée une chaine de caractêre, un entier on va trouver l'élément correspondant dans une table.

    Sinon il ya hash_map

    http://www.sgi.com/tech/stl/hash_map.html
    Mais pourquoi as-tu besoin d'une std::map ?
    Je ne connais pas OGRE mais je trouve ça un peu lourd.
    Une std::map est moins rapide qu'un std::list ou std::vector
    Quel type de conteneur me conseillez-vous pour une classe SceneNode, j'entend par SceneNode un noeud qui appartiendra à un arbre binaire, ou graphe de scène, en un mot c'est le même principe que pour Ogre.
    Un arbre binaire ne fonctionne pas avec des Hash tables à ma connaissance sinon ce serait trop lourd à gérer.
    Un arbre binaire c'est un ensemble de noeuds de structures qui possèdent 2 pointeurs , branche fille gauche et branche fille droite pointant elles-mêmes sur d'autres noeuds.
    Excuses-moi je n'arrive pas à comprendre

  4. #4
    Membre éprouvé
    Avatar de Ange_blond
    Homme Profil pro
    Ingénieur développement en 3D temps réel
    Inscrit en
    Mars 2007
    Messages
    902
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations professionnelles :
    Activité : Ingénieur développement en 3D temps réel
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Mars 2007
    Messages : 902
    Points : 1 179
    Points
    1 179
    Par défaut
    Je pense que dans ce cas, il s'agit plus d'un graph plutot que d'un arbre binaire... car un arbre binaire est trop limité pour représenter ce genre de choses..

  5. #5
    Invité
    Invité(e)
    Par défaut
    Euh, non, une map et une hash_map, c'est différent.

    Une map, c'est un arbre binaire de recherche... donc, insertion/recherche/suppression en o(ln(n)) où n est la taille de la collection...

    une hash_map, c'est de l'accès direct via une fonction de hashage... donc, insertion/recherche en o(1), mais par contre, au niveau de la suppression, c'est souvent le drame... Il faut, selon l'implementation reconstruire l'intégralité de la table...

    Tes données, elles vont beaucoup bouger ? elle seront beaucoup ? parce que si tu as peu d'elements, un simple vector, ou bien un vector_map[1], si tu tiens à tes acces par clef peut suffir...


    [1] Alexandrescu, Andrei. "Modern C++ Design: Generic Programming and Design Patterns Applied"
    http://loki-lib.sourceforge.net/ pour l'implementation (regarder AssocVector )

  6. #6
    En attente de confirmation mail
    Profil pro
    Étudiant
    Inscrit en
    Janvier 2008
    Messages
    56
    Détails du profil
    Informations personnelles :
    Âge : 37
    Localisation : France, Calvados (Basse Normandie)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Janvier 2008
    Messages : 56
    Points : 52
    Points
    52
    Par défaut
    Merci pour toutes vos réponses

    Pour répondes aux questions de bibi.skuk : oui mes données vont bouger mais pas sur une grande échelle, par contre elle devrait être très nombreuses, du moins de quoi réaliser une scène complexe type jeux vidéos 3D.
    Après quelques recherches et aussi sur vos conseil j'ai opté pour un std::vector à la place de mon std::map.
    Voici un exemple de recherche de node par nom
    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
     
    //-----------------------------------------------------
    // Remove a child SceneNode from this SceneNode.
    //-----------------------------------------------------
    SceneNode* SceneNode::detachChildSceneNode(const std::string& childSceneNodeName)
    {
    	bool find = false;
     
    	// Find the chil SceneNode in the std::vector.
    	childrenSceneNodeVector::iterator it = mChildrenSceneNode.begin();
    	while((find == false) || (it != mChildrenSceneNode.end()))
    	{
    		if((*it)->getName() == childSceneNodeName)
    		{
    			find = true;
    			(*it)->setParentSceneNode(NULL);
    			mChildrenSceneNode.erase(it);
    		}
    		else
    			++it;
    	}
     
    	return (*it);
    }
    Sachant que chaque SceneNode à son propre nom, donc aucun autre SceneNode ne peut avoir le même.

  7. #7
    Rédacteur
    Avatar de bafman
    Profil pro
    Développeur informatique
    Inscrit en
    Novembre 2003
    Messages
    2 574
    Détails du profil
    Informations personnelles :
    Âge : 40
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Industrie

    Informations forums :
    Inscription : Novembre 2003
    Messages : 2 574
    Points : 5 323
    Points
    5 323
    Par défaut
    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
     
    //-----------------------------------------------------
    // Remove a child SceneNode from this SceneNode.
    //-----------------------------------------------------
    SceneNode* SceneNode::detachChildSceneNode(const std::string& childSceneNodeName)
    {
        for(childrenSceneNodeVector::iterator it = mChildrenSceneNode.begin(); it != mChildrenSceneNode.end(); ++it)
        {
            if((*it)->getName() == childSceneNodeName)
           {
                SceneNode* result = *it;
                mChildrenSceneNode.erase(it);
                return result ;
           }
        }
    }
    c'est quand même plus simple et compréhensible non ?

  8. #8
    Rédacteur

    Avatar de khayyam90
    Homme Profil pro
    Architecte de système d’information
    Inscrit en
    Janvier 2004
    Messages
    10 370
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France, Bas Rhin (Alsace)

    Informations professionnelles :
    Activité : Architecte de système d’information

    Informations forums :
    Inscription : Janvier 2004
    Messages : 10 370
    Points : 40 164
    Points
    40 164
    Par défaut
    arbre n-aire ou map ? je réponds les deux !

    Autant c'est vrai que le scenegraph seul n'a pas besoin d'une map, qu'une simple std::list d'éléments enfants est suffisante surtout si on compte ajouter et supprimer régulièrement des éléments, autant la recherche de noeuds à partir de leur id peut aussi être régulière.

    C'est pourquoi il est pertinent d'enrichir la racine du scenegraph (ou tout autre élément gérant le scenegraph dans sa globalité) d'une table id->noeud

  9. #9
    En attente de confirmation mail
    Profil pro
    Étudiant
    Inscrit en
    Janvier 2008
    Messages
    56
    Détails du profil
    Informations personnelles :
    Âge : 37
    Localisation : France, Calvados (Basse Normandie)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Janvier 2008
    Messages : 56
    Points : 52
    Points
    52
    Par défaut
    Dis moi bafman je voudrais être sur : avec ta technique de parcours, admettons que je trouve mon SceneNode au bout du 4ème élèments de mon vecteur (sur 50 disons), est-ce que le return quitte instantanément la boucle ?

    Et de plus pourquoi créer une objet SceneNode dans la boucle, je ne peux pas directement le retourner ? du genre
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
     
    if((*it)->getName() == childSceneNodeName)
    {
         mChildrenSceneNode.erase(it);
         return *it;
    }

  10. #10
    Invité
    Invité(e)
    Par défaut
    On peut même aller plus loin, en utilisant algorithm

    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
     
    #include <algorithm>
     
    struct Equal {
        std::string& s_;
        Equal(std::string s) : s_(s) { }
        bool operator() (SceneNode* v) {
            return v->getName() == s;
        }
    };
     
    //-----------------------------------------------------
    // Remove a child SceneNode from this SceneNode.
    //-----------------------------------------------------
    SceneNode* SceneNode::detachChildSceneNode(const std::string& childSceneNodeName)
    {
        childrenSceneNodeVector::iterator it = 
            std::find(mChildrenSceneNode.begin(), mChildrenSceneNode.end(), Equal(childSceneNodeName));
     
        if (it != mChildrenSceneNode.end())
        {
            SceneNode* result = *it;
            mChildrenSceneNode.erase(it);
            return result ;
        }
        return 0;
    }

  11. #11
    Rédacteur
    Avatar de bafman
    Profil pro
    Développeur informatique
    Inscrit en
    Novembre 2003
    Messages
    2 574
    Détails du profil
    Informations personnelles :
    Âge : 40
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : Industrie

    Informations forums :
    Inscription : Novembre 2003
    Messages : 2 574
    Points : 5 323
    Points
    5 323
    Par défaut
    Citation Envoyé par FunkyTech Voir le message
    Dis moi bafman je voudrais être sur : avec ta technique de parcours, admettons que je trouve mon SceneNode au bout du 4ème élèments de mon vecteur (sur 50 disons), est-ce que le return quitte instantanément la boucle ?
    oui bien sûre
    Citation Envoyé par FunkyTech Voir le message
    Et de plus pourquoi créer une objet SceneNode dans la boucle, je ne peux pas directement le retourner ? du genre
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
     
    if((*it)->getName() == childSceneNodeName)
    {
         mChildrenSceneNode.erase(it);
         return *it;
    }
    pas possible car ton iterateur est invalidé par le erase, il faut donc recuperer le pointeur avant le erase pour pouvoir le retourner...

  12. #12
    En attente de confirmation mail
    Profil pro
    Étudiant
    Inscrit en
    Janvier 2008
    Messages
    56
    Détails du profil
    Informations personnelles :
    Âge : 37
    Localisation : France, Calvados (Basse Normandie)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Janvier 2008
    Messages : 56
    Points : 52
    Points
    52
    Par défaut
    Lol en effet je n'ai pas fait attention^^ en tout cas merci à tous pour ces précieuses informations. Le post est pour moi résolu

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. type de colonne pour numéro de tél et code postal
    Par molesqualeux dans le forum Requêtes
    Réponses: 2
    Dernier message: 19/01/2006, 15h19
  2. Réponses: 3
    Dernier message: 01/08/2005, 13h15
  3. [type de retour pour un update]
    Par viny dans le forum PostgreSQL
    Réponses: 7
    Dernier message: 21/03/2005, 22h08

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo