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

C++ Discussion :

Système de Particules


Sujet :

C++

  1. #41
    Membre averti
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Décembre 2014
    Messages
    50
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val d'Oise (Île de France)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Décembre 2014
    Messages : 50
    Par défaut
    Citation Envoyé par Kannagi Voir le message
    Je pense que si tu arrive a mettre un tableau a la place : mGrid[caseY-1][caseX+j].size() , ça optimiserait pas mal :p
    J'ai le même résultat avec un tableau simple

    Mon super code

    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
    #ifndef PARTICLESYSTEM_H
    #define PARTICLESYSTEM_H
     
    #include <vector>
    #include <deque>
    #include <algorithm>
    #include <iostream>
    #include <stdlib.h>
    #include <list>
    #include <memory>
    #include <math.h>
    #include "Particle.h"
    #include "ParticleContact.h"
    #include "Window.h"
    #include "Map.h"
    #include "Camera.h"
    #include "QuadTree.h"
     
    class ParticleSystem
    {
        public:
            ParticleSystem();
            virtual ~ParticleSystem();
     
            void displayParticle(Window *window, Camera *camera);
            void createParticle(int type, float positionX, float positionY, float velocityX, float velocityY);
            void createParticles(int type, float positionX, float positionY);
     
            void computeParticles(Map *pMap);
            void createGrid();
            void findContacts();
            void computeForces();
            void updatePosition(Map *pMap);
     
     
        protected:
     
        private:
     
            const float PI = 3.14159f;
            const float TIME_STEP = 0.1f;
            const float GRAVITY = 0.5;
            const float n = 5.0f;
            const float w0 = -0.0f;
            const float a = -45.0f;
            const float VISCOSITY = 0.1f;
            const static int MAX_PARTICLES = 8192;
     
            const static int WIDTH_PARTICLE = 10;
            const static int WIDTH_PARTICLE_2 = 100;
            const static int RADIUS_PARTICLE = 5;
     
            Particle mParticles[MAX_PARTICLES];
     
            std::vector<ParticleContact> mParticleContacts;
            std::vector<int> mGrid[96][199];
     
            int mCountParticles;
    };
     
    #endif // PARTICLESYSTEM_H
    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
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    #include "ParticleSystem.h"
     
    ParticleSystem::ParticleSystem()
    {
        mCountParticles = 0;
    }
     
    ParticleSystem::~ParticleSystem()
    {
     
    }
     
    void ParticleSystem::displayParticle(Window *window, Camera *camera)
    {
        for(int i=0; i<mCountParticles;i++){
            int posXwindow = window->getWidth()/2-(camera->getPosX() - mParticles[i].mPositionX);
            int posYwindow = window->getHeight()/2 + (camera->getPosY() - mParticles[i].mPositionY);
     
     
            window->renderImage("circle", posXwindow-RADIUS_PARTICLE, posYwindow-RADIUS_PARTICLE, WIDTH_PARTICLE, WIDTH_PARTICLE);
        }
     
        window->displayNumber(400, 400, mCountParticles, 0,400,0);
    }
     
    void ParticleSystem::createParticle(int type, float positionX, float positionY, float velocityX, float velocityY)
    {
        mParticles[mCountParticles] = Particle(type, positionX, positionY, velocityX, velocityY);
        mCountParticles ++;
    }
     
    void ParticleSystem::createParticles(int type, float positionX, float positionY)
    {
        float space = 11;
     
        for(int i=0; i< 30; i++)
            for(int j=0; j<30; j++)
                createParticle(type, positionX+space*i, positionY-j*space, 0, 0);
    }
     
    void ParticleSystem::computeParticles(Map *pMap)
    {
        createGrid();
        findContacts();
        computeForces();
        updatePosition(pMap);
    }
     
    void ParticleSystem::createGrid()
    {
        for(int caseX=0; caseX<199; caseX++)
            for(int caseY=0; caseY<96; caseY++)
                mGrid[caseY][caseX].clear();
     
        for(int i = 0; i<mCountParticles; i++){
            int x = mParticles[i].mPositionX/10;
            int y = mParticles[i].mPositionY/10;
            mGrid[y][x].push_back(i);
        }
    }
     
    void ParticleSystem::findContacts()
    {
        for(int i=0; i<mCountParticles; i++)
        {
            int caseX = mParticles[i].mPositionX/10;
            int caseY = mParticles[i].mPositionY/10;
     
     
            // same case
            for(int k=0;k<mGrid[caseY][caseX].size();k++){
                int voisin = mGrid[caseY][caseX][k];
                float dx = mParticles[voisin].mPositionX - mParticles[i].mPositionX;
                float dy = mParticles[voisin].mPositionY - mParticles[i].mPositionY;
                if(dx > 0 || (dx==0 && dy>0)){
                    float distance2 = dx * dx + dy * dy;
                    if(distance2 < WIDTH_PARTICLE_2 && distance2 != 0){
                        float distance = sqrt(distance2);
                        float weight = (1.0f-distance/WIDTH_PARTICLE);
                        mParticleContacts.emplace_back(i, voisin, distance, weight);
                        mParticles[i].mDensity += weight;
                        mParticles[voisin].mDensity += weight;
                    }
                }
            }
     
            // right case
            if(caseX+1<199){
                for(int k=0;k<mGrid[caseY][caseX+1].size();k++){
                    int voisin = mGrid[caseY][caseX+1][k];
                    float dx = mParticles[voisin].mPositionX - mParticles[i].mPositionX;
                    float dy = mParticles[voisin].mPositionY - mParticles[i].mPositionY;
                    float distance2 = dx * dx + dy * dy;
                    if(distance2 < WIDTH_PARTICLE_2 && distance2 != 0){
                        float distance = sqrt(distance2);
                        float weight = (1.0f-distance/WIDTH_PARTICLE);
                        mParticleContacts.emplace_back(i, voisin, distance, weight);
                        mParticles[i].mDensity += weight;
                        mParticles[voisin].mDensity += weight;
                    }
                }
            }
     
            //bottom cases
            for(int j=-1;j<2;j++){
                if(caseY-1>0 && caseX+j>0 && caseX + j<199){
                    for(int k=0;k<mGrid[caseY-1][caseX+j].size();k++){
                        int voisin = mGrid[caseY-1][caseX+j][k];
                        float dx = mParticles[voisin].mPositionX - mParticles[i].mPositionX;
                        float dy = mParticles[voisin].mPositionY - mParticles[i].mPositionY;
                        float distance2 = dx * dx + dy * dy;
                        if(distance2 < WIDTH_PARTICLE_2 && distance2 != 0){
                            float distance = sqrt(distance2);
                            float weight = (1.0f-distance/WIDTH_PARTICLE);
                            mParticleContacts.emplace_back(i, voisin, distance, weight);
                            mParticles[i].mDensity += weight;
                            mParticles[voisin].mDensity += weight;
                        }
                    }
                }
            }
     
            //apply gravity
            mParticles[i].mVelocityY -= GRAVITY;
            //compute pressure
            mParticles[i].mPressure = std::max(0.0f, n * (mParticles[i].mDensity - w0));
     
        }
     
    }
     
    void ParticleSystem::computeForces()
    {
        while(!mParticleContacts.empty()){
     
            ParticleContact contact = mParticleContacts.back();
            mParticleContacts.pop_back();
     
            int p1 = contact.mParticule1;
            int p2 = contact.mParticule2;
     
            //compute force
     
     
            float nX = (mParticles[p2].mPositionX - mParticles[p1].mPositionX)/contact.mDistance;
            float nY = (mParticles[p2].mPositionY - mParticles[p1].mPositionY)/contact.mDistance;
     
            float forceX = TIME_STEP * a * (mParticles[p1].mPressure + mParticles[p2].mPressure) * contact.mWeight * nX;
            float forceY = TIME_STEP * a * (mParticles[p1].mPressure + mParticles[p2].mPressure) * contact.mWeight * nY;
     
            mParticles[p1].mVelocityX += forceX;
            mParticles[p1].mVelocityY += forceY;
     
            mParticles[p2].mVelocityX -= forceX;
            mParticles[p2].mVelocityY -= forceY;
     
            mParticles[p1].mVelocityX += TIME_STEP * VISCOSITY * (mParticles[p2].mVelocityX - mParticles[p1].mVelocityX);
            mParticles[p1].mVelocityY += TIME_STEP * VISCOSITY * (mParticles[p2].mVelocityY - mParticles[p1].mVelocityY);
     
            mParticles[p2].mVelocityX += TIME_STEP * VISCOSITY * (mParticles[p1].mVelocityX - mParticles[p2].mVelocityX);
            mParticles[p2].mVelocityY += TIME_STEP * VISCOSITY * (mParticles[p1].mVelocityY - mParticles[p2].mVelocityY);
        }
    }
     
    void ParticleSystem::updatePosition(Map *pMap)
    {
        // update position
        for (int i = 0; i < mCountParticles; ++i) {
     
            if(mParticles[i].mVelocityX>50)
                mParticles[i].mVelocityX = 50;
     
            if(mParticles[i].mVelocityX<-50)
                mParticles[i].mVelocityX = -50;
     
            if(mParticles[i].mVelocityY>50)
                mParticles[i].mVelocityY = 50;
     
            if(mParticles[i].mVelocityY<-50)
                mParticles[i].mVelocityY = -50;
     
            mParticles[i].updatePosition(pMap ,TIME_STEP);
     
            //reset
            mParticles[i].mDensity=0.0f;
            mParticles[i].mPressure=0.0f;
        }
    }

  2. #42
    Expert confirmé
    Avatar de Kannagi
    Homme Profil pro
    cyber-paléontologue
    Inscrit en
    Mai 2010
    Messages
    3 226
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 37
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : cyber-paléontologue

    Informations forums :
    Inscription : Mai 2010
    Messages : 3 226
    Par défaut
    Tu m'a mal compris , je disais de remplacer mGrid[caseY][caseX].size() , par Grid[caseY][caseX] par exemple.

  3. #43
    Expert éminent
    Avatar de koala01
    Homme Profil pro
    aucun
    Inscrit en
    Octobre 2004
    Messages
    11 635
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 53
    Localisation : Belgique

    Informations professionnelles :
    Activité : aucun

    Informations forums :
    Inscription : Octobre 2004
    Messages : 11 635
    Par défaut
    Alors, concernant le code:

    Pourquoi mParticles est il un tableau de taille fixe "C style" Tôt ou tard, quand tes problèmes de performances seront résolus, tu voudras augmenter le nombre de particules au point de faire exploser ta pile!

    Utilises au minimum les fonctionnalités issues de la bibliothèque standard : std::array si tu as un nombre "relativement restreint" d'élément connu à la compilation std::vector + sa fonction reserve ou resize si le nombre devient "trop important" ou si le nombre d'éléments n'est pas connu à la compilation.

    As tu une vague idée de ce que représente ton code std::vector<int> mGrid[96][199]; c'est une matrice qui contient 19 104 tableaux d'entiers! le tout placé dans la pile (à moins que tu n'aies recours à l'allocation dynamique pour ton ParticleSystem). Heu, je veux bien, mais... t'es sur d'avoir besoin de cela

    Et puis:

    mGrid en lui-même va, effectivement, placer les 19000 std::vector l'un à la suite de l'autre en mémoire. Mais std::vector est une classe qui a recours à l'allocation dynamique de la mémoire pour pouvoir représenter les éléments qu'ils contient d'une manière contigue en mémoire. C'est à dire que les X éléments contenus par le std::vector qui se trouve en mGrid[0][0] n'ont pour ainsi dire aucune chance d'être contigus avec ceux qui se trouvent dans mGrid[0][1] (ou dans mGrid[1][0])

    Cela peut ne pas être catastrophique, ou non...

    Sans compter le fait que l'idéal est toujours de faire en sorte que toutes les notions qui apparaissent dans ton analyse des besoins / dans ton analyse fonctionnelle puissent avoir leur représentation dans le code. Tu as besoin de la notion de matrice Crée un type de donnée (une classe, en l'occurrence) qui représentera cette notion.

    Pour ce faire, il faut comprendre que, lorsque tu crées une matrice de LINES lignes et de ROWS colonnes, ce que tu veux en réalité, c'est d'être en mesure de représenter LINES * ROWS éléments (raison pour laquelle je parlais des 19000 std::vector). Tu peux donc tout à fait représenter ces éléments dans un tableau classique à une seule dimension. La formule pour accéder à l'élément se trouvant à la ligne L et à la colonne R est alors indice recherché = L * ROWS + C et, inversement, pour connaitre la ligne et la colonne à laquelle se trouve un élément donné au départ de son indice, on utilisera les formule L = indice / ROWS et C = indice % ROWS.

    De plus, dans le cas particulier qui nous occupe, ta matrice a pour objectif de représenter une grille d'éléments et donc de nous permettre d'accéder aux "cases adjacentes" à la case sur laquelle on travaille. quand on parle de case adjacente, on envisage quatre directions et les combinaisons qu'elles permettent, à savoir
    • le haut
    • le bas
    • la gauche et
    • la droite.

    Nous pouvons donc représenter ces notions sous la forme d'une énumération qui ressemblerait à
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    enum Direction{
        up    = 1 <<0,
        down  = 1<<1,
        left  = 1<<2,
        right = 1<<3
    };
    Cela pourrait se traduire en C++ par une classe proche de
    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
    template <typename T>
    class Grid{
    public:
        Grid(size_t l, size_t r, T const & t= T{}):lines_{l},rows{r}, items_{l*r, t}{
        }
        /* permet d'accéder à un élément selon la ligne et la colonne à laquelle il se trouve */
        T & operator() (size_t line, size_t row){
            assert(line < lines_ && "line index out of bound");
            assert(row < rows_ && "row index out of bound");
            return items_[line*rows + row];
        }
        /* pareil, mais la constance en plus */
        T const & operator() (size_t line, size_t row) const{
            return const_cast<Grid<T> *>(this)->operator()(line, row);
        }
        /* permet d'accéder à "l'élément adjacent" en fonction de la position courante
         * et de la direction indiquée 
         */
        T & adjacent(size_t currentLine, size_t currentRow, Direction d){
            static T empty{}; // un élément vide, pour les cas particuliers
            /* demander l'élément de gauche et de droite en même temps n'a aucun sens */
            assert(d & left && d & right && "Adjacent left + rigth has  no sense");
            /* pareil pour haut et bas */
            assert(d &up && d& down && "Adjacent up + down has no sense") ;
            /* évitons les cas particuliers */
            if(    (currentLine == 0 && d & up)  
               ||  (currentLine >= g.lines() && d & down)) // la première ou la dernière ligne
                return empty;
            if(   (currentRow == 0 && d & left)
               || (currentRow >=g.rows() && d& right) ) // la première ou la dernière colonne
                return empty;
            if(currentRow >=g.rows() && d& right)
                return empty;
            /* calcul de la position de l'élément adjacent */
            size_t adjacentRow{d& left ? --currentRow : d&right ? ++currentRow : currentRow};
            size_t adjacentLine{d& up? -- currentLine : d & down? ++currentLine : currentLine};
            return operator()(adjacentLine, adjacentRow);
        }
        /* pareil, la constance en plus */
        T const & adjacent(size_t currentLine, size_t currentRow, Direction d) const{
            return const_cast<Grid<T> *>(this)->adjacent(currentLine, currentRow, d);
        }
        size_t lines() const{
            return lines_;
        }
        size_t rows const{
            returns rows;
        }
    private:
        std::vector<T> items_;
    };
    et tu pourrais donc l'utiliser dans ta classe ParticleSystem sous la forme de
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    /* ATTENTION !!! un index est toujours positif.  Le type idéal pour le représenter
     * est size_t
     */
    Matrix<std::vector<size_t>> mGrid;
    (bien que, jusqu'ici, nous n'ayons pas changé le comportement général : les indice qui se trouve dans le std::vector se trouvant en position 0,0 sont toujours "très éloignés" de ceux se trouvant dans le std::vector de la position 0,1.)

    Quant à la fonction adjacent, son principe est simple : elle permettra toujours d'obtenir un élément, quelle que soit la position courante, quelle que soit la direction choisie. Mais, et c'est là qu'est le trait de génie, si on est dans une situation dans laquelle l'élément demandé n'existe pas (parce que l'on demande l'élément "qui se trouve au dessus" de la première ligne, par exemple), elle renverra un élément qui répondra faux à toutes les questions que nous pourrions lui poser (sauf, bien sur, aux questions négative comme empty() ).

    C'est ce que l'on appelle l'idiome de l'objet nul.

    Si bien que, à défaut d'améliorer les performances de ton algorithme, nous pourrons au moins le simplifier pour lui donner une forme qui serait proche de
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    Soient toutes les directions possibles = up, down, left, right, up|left, up|right, down|left et down|right
    soit d = la grille que l'on utilise
    Soit currentLine = ligne de la case qui nous intéresse
    Soit currentRow = la colonne de la case qui nous intéresse
    Pour chaque direction possible d
        soit temp = adjacent(currentLine, currentRow, d)
        travailler avec temp
    Fin Pour
    En C++, cela pourrait prendre la forme de
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    void ParticleSystem::someFunction(size_t currentLine, size_t currentRow){
        /* toutes les directions possibles */
        static std::array<Direction, 8> allDirections{up, down, left, right, up|left, up|right, down|left, down|right};
        for( auto d : allDirections){
            auto /* const */ & adj = mgrid.adjacent(line, roww, d);
            /* ce qu'il faut faire */
        } 
    }
    Mais, surtout, le gros problème est que tu (en fait, tu la remplis : ta fonction createGrid devrait s'appeler ... fillGrid, ce serait plus correct )ta grille à chaque fois que tu appelles computesParticles!

    Ca signifie, en gros, que chaque fois que tu va faire appel à cette fonction, tu vas devoir t'amuser à passer toutes tes particules en revues pour savoir dans quelle case tu dois les mettre; ce qui est vraiment dommage lorsqu'on sait que, quoi qu'il arrive, une particule qui va se déplacer ne pourra, au mieux, que rester dans la case dans laquelle elle se trouve, au pire que se retrouver dans une case adjacente.

    Ton objectif doit donc être d'éviter ces parcours inutiles. Et pour y arriver, il n'y a pas trente-si solutions :
    1. tu dois t'assurer de ne remplir ta grille qu'une seule fois; puis,
    2. A chaque appel à la fonction computesParticles, si la grille n'est par remplie (voir ci-dessous) la remplire, sinon, passer directement à l'étape 3
    3. chaque fois que tu déplaces une particule, poses toi la question de savoir si elle change de case dans la grille
      1. si elle ne change pas de case, tu la laisses bien où elle est
      2. si elle change de case, demande la case adjacente qui correspond à son déplacement et déplace-la dans cette case


    Pour le (1) Rajoutes, par exemple, un booleen mgridFillded initialisé à false, qui passera à true à la fin de ta fonction de remplissage

    Attention!!! Pour le (3.2) il y a une astuce à prendre en compte du fait que tu utilises un std::vector: quand tu retires un élément du tableau, tu invalide l'itérateur sur lequel tu travailles, ainsi que les itérateurs vers tous les éléments qui suivent celui que tu as supprimé dont tu pourrais disposer.

    Tu devras donc "trouver l'astuce" pour palier ce problème

    L'énorme avantage, c'est que, pour l'instant, tu parcoures au moins trois fois la liste entière de tes particules :
    1. pour remplir la grille
    2. pour calculer le déplacement de tes particules
    3. pour afficher les particules


    En faisant en sorte de ne déplacer dans ta grille que les particules qui on lieu de l'être, tu descendra à deux parcours de la liste entière. D'où, selon toutes vraisemblances, un gain de temps non négligeable

    De la même manière, il me semble que tu parcours ta grille au moins en deux occasions:
    1. pour calculer les contacts entre les particules et
    2. pour mettre ta map de particules à jour

    Pourquoi ne ferais tu pas en sorte de mettre ta map à jour pour une particule donnée une fois que tu as "fait tout ce que tu devais faire" avec cette particule Un parcours de la grille en moins == ... Beaucoup moins de particules à parcourir pour pouvoir les mettre à jour

    En un mot comme en cent : évite les "parcours à répétition" de tes collections. Dis toi qu'une simple boucle proche de
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    Tableau tab;
    for(size_t i = 0; i < tab.size(); ++i){
        auto truc =tab[1];
        /* tout ce qu'il faut faire avec truc */
    }
    va se traduire à l'exécution, pour un tableau de 200 éléments, par quelque chose comme
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    adresseDepart = 0xABCDEF
    /* ce qui suit va se répéter deux cents fois !!!
     * =======================
     */
    adresseTemporaire = adresseDeDepart + (i * taille de l'élément) // (1)
    charger (un registre quelconque) avec ce qu'il y a dans adresseTemporaire
    /* tout ce qu'il faut faire avec ce qu'il y a dans le registre */
    incrementer i
    si i < 200 retourner en (1)
    Cela devrait te permettre de te rendre compte que tu as largement intérêt à faire "tout ce que tu peux faire" avec un élément tant que "tu l'as en main", au lieu de ramasser "tous les éléments un à un" pour faire un truc puis de recommencer pour... faire autre chose

    Pourquoi passer un pointeur sur Map D'ailleurs, pourrais tu nous montrer le code complet de cette classe Comment celle que tu transmet à la fonction computeParticles est-elle créée
    A méditer: La solution la plus simple est toujours la moins compliquée
    Ce qui se conçoit bien s'énonce clairement, et les mots pour le dire vous viennent aisément. Nicolas Boileau
    Compiler Gcc sous windows avec MinGW
    Coder efficacement en C++ : dans les bacs le 17 février 2014
    mon tout nouveau blog

  4. #44
    Membre averti
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Décembre 2014
    Messages
    50
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val d'Oise (Île de France)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Décembre 2014
    Messages : 50
    Par défaut
    Re,

    Merci de votre aide, désolé pour la réponse un peu tardive


    Citation Envoyé par koala01 Voir le message
    Alors, concernant le code:

    Pourquoi mParticles est il un tableau de taille fixe "C style" Tôt ou tard, quand tes problèmes de performances seront résolus, tu voudras augmenter le nombre de particules au point de faire exploser ta pile!
    Pour le moment c'est un tableau de taille fixe mais oui après je pourrais le remplacé par un vector.

    Citation Envoyé par koala01 Voir le message

    As tu une vague idée de ce que représente ton code std::vector<int> mGrid[96][199]; c'est une matrice qui contient 19 104 tableaux d'entiers! le tout placé dans la pile (à moins que tu n'aies recours à l'allocation dynamique pour ton ParticleSystem). Heu, je veux bien, mais... t'es sur d'avoir besoin de cela
    Je peux aussi faire a la limite std::vector<int> mGrid[96*199].

    Citation Envoyé par koala01 Voir le message
    mGrid en lui-même va, effectivement, placer les 19000 std::vector l'un à la suite de l'autre en mémoire. Mais std::vector est une classe qui a recours à l'allocation dynamique de la mémoire pour pouvoir représenter les éléments qu'ils contient d'une manière contigue en mémoire. C'est à dire que les X éléments contenus par le std::vector qui se trouve en mGrid[0][0] n'ont pour ainsi dire aucune chance d'être contigus avec ceux qui se trouvent dans mGrid[0][1] (ou dans mGrid[1][0])

    Cela peut ne pas être catastrophique, ou non...
    Comment je suis censé faire alors ? Car je ne peux pas savoir combien de particules une case va contenir donc j'utilise des vectors.

    Citation Envoyé par koala01 Voir le message
    Mais, surtout, le gros problème est que tu (en fait, tu la remplis : ta fonction createGrid devrait s'appeler ... fillGrid, ce serait plus correct )ta grille à chaque fois que tu appelles computesParticles!

    Ca signifie, en gros, que chaque fois que tu va faire appel à cette fonction, tu vas devoir t'amuser à passer toutes tes particules en revues pour savoir dans quelle case tu dois les mettre; ce qui est vraiment dommage lorsqu'on sait que, quoi qu'il arrive, une particule qui va se déplacer ne pourra, au mieux, que rester dans la case dans laquelle elle se trouve, au pire que se retrouver dans une case adjacente.
    Mon but était d'éviter de devoir faire des remove d'élement qui se trouve au milieu de vector lorsqu'une particule passe d'une case à une autre.
    Après oui cela permet de gagner een temps sur la fonction qui rempli la grille.

    Citation Envoyé par koala01 Voir le message
    Cela devrait te permettre de te rendre compte que tu as largement intérêt à faire "tout ce que tu peux faire" avec un élément tant que "tu l'as en main", au lieu de ramasser "tous les éléments un à un" pour faire un truc puis de recommencer pour... faire autre chose
    Je ne peux pas traiter les particules une seule fois car ce que je fais:

    -Parcours de toute les particules pour trouver les contacts de cette particule.
    -Une fois toutes les contacts trouvés, on peux calculer la pression de la particule
    -Parcourir tous les contacts pour mettre à jour la vélocité en utilisant la pression

    Citation Envoyé par koala01 Voir le message
    Pourquoi passer un pointeur sur Map D'ailleurs, pourrais tu nous montrer le code complet de cette classe Comment celle que tu transmet à la fonction computeParticles est-elle créée .
    Je viens de mettre le code sur github ça sera plus pratique que les copier-coller en masse.
    https://github.com/AlexisMalamas/Gam...master/War_4.3

  5. #45
    Expert éminent
    Avatar de koala01
    Homme Profil pro
    aucun
    Inscrit en
    Octobre 2004
    Messages
    11 635
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 53
    Localisation : Belgique

    Informations professionnelles :
    Activité : aucun

    Informations forums :
    Inscription : Octobre 2004
    Messages : 11 635
    Par défaut
    Citation Envoyé par guppyworld Voir le message
    Je peux aussi faire a la limite std::vector<int> mGrid[96*199].
    Ce sera déjà mieux
    Comment je suis censé faire alors ? Car je ne peux pas savoir combien de particules une case va contenir donc j'utilise des vectors.
    Tu choisi la bonne manière de subdiviser ton espace.

    En gros, tu as trois possibilités majeure pour subdiviser ton espace (il n'y a que la troisième possibilité qui n'aura vraiment de sens que pour un quadtree / un octreee ):

    Ou bien tu décides de subdiviser ton espace par rapport au nombre d'éléments (tes particules, dans le cas présent) que peut contenir chaque subdivision. Tu peux définir une valeur maximale (recommandé) au delà de laquelle tu subdivise à nouveau ta division et éventuellement une valeur minimale au delà de laquelle tu décideras d'annuler la subdivision.

    Cette manière de travailler présente l'avantage d'avoir toujours "à peu près le même nombre" de particule par subdivision. Par contre, la superficie de chaque subdivision et la "densité" d'éléments par mesure de surface / de volume est variable: tu peux aussi bien te retrouver avec trois particules très éloignées les unes des autres dans une très grande subdivision que te retrouver avec le maximum de particules que tu as décidé "entassées" dans une subdivision dont sa surface / son volume suffit à peine à les contenir (voire, soit "trop petit" pour arriver à les contenir)

    Ou bien, tu décides de fixer la taille (superficie / volume) de chaque subdivision, et de subdiviser une partie de ton espace aussi longtemps que tu n'es pas descendu en dessous de cette limite. Cela te créera des subdivisions de taille égale, mais tu pourrais très bien te retrouver avec des subdivisions "pleines à craquer" et d'autres totalement vides.

    Ou bien, tu décides de limiter le nombre de fois que tu subdivise ton espace. C'est surtout pratique dans un quadtree / octree parce que cela te permet de limiter le nombre de noeuds à parcourir depuis ton "espace global" pour atteindre un "sous espace particulier".

    Mais c'est surtout nécessaire en conjonction avec au moins l'une des deux autres possibilités invoquées, de manière à pouvoir décider à un moment que "l'espace est assez subdivisé, et tant pis si certaines subdivisions dépassent le nombre d'éléments admis".
    Mon but était d'éviter de devoir faire des remove d'élement qui se trouve au milieu de vector lorsqu'une particule passe d'une case à une autre.
    Après oui cela permet de gagner een temps sur la fonction qui rempli la grille.
    De manière générale, cela te prendra toujours bien moins de temps de supprimer un élément depuis le milieu de ta collection afin de le déplacer dans ta grille que de recréer ta grille à chaque fois

    Je ne peux pas traiter les particules une seule fois car ce que je fais:

    -Parcours de toute les particules pour trouver les contacts de cette particule.
    -Une fois toutes les contacts trouvés, on peux calculer la pression de la particule
    -Parcourir tous les contacts pour mettre à jour la vélocité en utilisant la pression
    Non, ce que tu ne peux pas faire, c'est calculer les contacts qu'il y a entre les différentes particules tant que tu n'as pas évalué la position de toutes les particules. Ca, nous sommes d'accord

    Mais rien ne t'empêche, une fois que tu as évalué la position probable de toutes tes particules à l'instant T+1, de faire tous les calculs dus aux contacts en une fois pour chaque particule, ce qui sera toujours mieux que de changer ta particule de référence sans arrêt.

    Je crois aussi que tu devrais commencer par simplifier un peu les choses en ne t'attaquant qu'à un problème à la fois:

    • Commence par une seule particule qui se trouve "bloquée" dans ton espace. Quand elle rencontre la limite de l'espace, elle rebondit dessus de la même manière qu'une balle de billard (c'est relativement simple à mettre en place )
    • Une fois que tu auras quelque chose de fonctionnel, rajoute deux ou trois particules, et fait en sorte qu'elles rebondissent les unes sur les autres lorsqu'elles entrent en collision.
    • Puis rajoute la subdivision de ton espace, car tu n'aura aucun besoin de tester les collision si tes quatre particules se trouvent à une extrémité de ton espace différente.
    • Rajoutes ensuite "suffisamment de particules" (100, 200) que pour remplir correctement ton espace et voir comment cela se passe.
    • Ensuite, rajoutes les notions une à une (en testant et en observant le résultat à chaque fois): la gravité en premier, la densité (fixe) ensuite, puis la compression (quand une particule est "prise en sandwich" par deux autres), ...
    • Termines en rajoutant des particules "petit à petit" (par 100 ou 200 à la fois)


    De cette manière, tu pourras te focaliser sur un problème à la fois, mais tu auras toujours le "plaisir de voir" que le résultat correspond à tes besoins.
    A méditer: La solution la plus simple est toujours la moins compliquée
    Ce qui se conçoit bien s'énonce clairement, et les mots pour le dire vous viennent aisément. Nicolas Boileau
    Compiler Gcc sous windows avec MinGW
    Coder efficacement en C++ : dans les bacs le 17 février 2014
    mon tout nouveau blog

  6. #46
    Rédacteur/Modérateur


    Homme Profil pro
    Network game programmer
    Inscrit en
    Juin 2010
    Messages
    7 147
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 37
    Localisation : Canada

    Informations professionnelles :
    Activité : Network game programmer

    Informations forums :
    Inscription : Juin 2010
    Messages : 7 147
    Billets dans le blog
    4
    Par défaut
    C'est peut-être une connerie mais : ne pourrait-on pas avoir 1 seul vector de particule std::vector<particules> que tu tries en fonction de leur région pour que les proches dans une même région soient contigües ? plutôt que d'avoir un vector par région.
    Si non, selon la taille des particules, peut-être qu'un vector unique et un vector par région avec un simple pointeur vers les particules de la région pourrait limiter les cache miss. Selon le nombre de particules que l'on peut mettre dans le cache.
    Pensez à consulter la FAQ ou les cours et tutoriels de la section C++.
    Un peu de programmation réseau ?
    Aucune aide via MP ne sera dispensée. Merci d'utiliser les forums prévus à cet effet.

  7. #47
    Membre averti
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Décembre 2014
    Messages
    50
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val d'Oise (Île de France)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Décembre 2014
    Messages : 50
    Par défaut
    Citation Envoyé par koala01 Voir le message
    Mais rien ne t'empêche, une fois que tu as évalué la position probable de toutes tes particules à l'instant T+1, de faire tous les calculs dus aux contacts en une fois pour chaque particule, ce qui sera toujours mieux que de changer ta particule de référence sans arrêt.
    Je n'ai pas très bien compris ou est-ce que je changer la particule de référence sans arrêt. Le fait de parcourir les particules une par une ?

    Citation Envoyé par koala01 Voir le message
    Je crois aussi que tu devrais commencer par simplifier un peu les choses en ne t'attaquant qu'à un problème à la fois:

    Commence par une seule particule qui se trouve "bloquée" dans ton espace. Quand elle rencontre la limite de l'espace, elle rebondit dessus de la même manière qu'une balle de billard (c'est relativement simple à mettre en place )
    Une fois que tu auras quelque chose de fonctionnel, rajoute deux ou trois particules, et fait en sorte qu'elles rebondissent les unes sur les autres lorsqu'elles entrent en collision.
    Puis rajoute la subdivision de ton espace, car tu n'aura aucun besoin de tester les collision si tes quatre particules se trouvent à une extrémité de ton espace différente.
    Rajoutes ensuite "suffisamment de particules" (100, 200) que pour remplir correctement ton espace et voir comment cela se passe.
    Ensuite, rajoutes les notions une à une (en testant et en observant le résultat à chaque fois): la gravité en premier, la densité (fixe) ensuite, puis la compression (quand une particule est "prise en sandwich" par deux autres), ...
    Termines en rajoutant des particules "petit à petit" (par 100 ou 200 à la fois)


    De cette manière, tu pourras te focaliser sur un problème à la fois, mais tu auras toujours le "plaisir de voir" que le résultat correspond à tes besoins.
    Oui, j'ai déja fait tous ça. La simulation fonctionne bien et la seule chose que je recherche maintenant est la quantité.

    Si non, selon la taille des particules, peut-être qu'un vector unique et un vector par région avec un simple pointeur vers les particules de la région pourrait limiter les cache miss. Selon le nombre de particules que l'on peut mettre dans le cache.
    Stocker les références des particules plutôt que les indices des particules ? Mouè je sais pas trop si c'est vraiment plus efficace. Faut que je test ça.

  8. #48
    Expert éminent
    Avatar de koala01
    Homme Profil pro
    aucun
    Inscrit en
    Octobre 2004
    Messages
    11 635
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 53
    Localisation : Belgique

    Informations professionnelles :
    Activité : aucun

    Informations forums :
    Inscription : Octobre 2004
    Messages : 11 635
    Par défaut
    Citation Envoyé par guppyworld Voir le message
    Je n'ai pas très bien compris ou est-ce que je changer la particule de référence sans arrêt. Le fait de parcourir les particules une par une ?
    Imaginons que tu aies devant toi une grande table avec 100 "trucs" en bois -- de forme et de taille quelconque, mais identique -- rangés dans un ordre quasi militaire.

    Et imaginons que tu aies pour instructions quelque chose comme
    • tous les trucs doivent être dépoussiérés
    • si le vernis d'un truc est abîmé, tu dois le poncer pour retirer l'ancienne couche de vernis et le revernir

    Mais, et c'est une règle absolue, tout truc sur lequel tu n'es pas occupé à travailler doit être remis scrupuleusement à sa place. Sinon, gare à la schlakke!

    Sachant que le nettoyage d'un truc prend un temps T, que sa vérification prend un temps U, que son ponçage prend un temp V et que son vernissage prend un temps W et que tous ces temps sont constants, qu'est ce qui sera le plus rapide
    A - tu prend un truc, tu le nettoies, tu le vérifies et, si besoin, tu le ponces et tu le vernis ou
    B -
    • tu prend un truc, tu le nettoies, tu le repose pour passer au suivant, et ce pour tous les trucs
    • tu prend un truc, tu le vérifie, et tu marque "quelque part" s'il faut le poncer et le vernir avant de le poser et de passer au suivant, et ce pour tous les trucs
    • tu prends un truc qui doit être poncé, tu le ponces, puis tu le poses et passes au truc suivant qui doit être poncé, et ce pour tous les trucs qui doivent être poncés
    • tu prend un truc qui a été poncé, tu le vernis, tu le poses et tu passe au truc suivant qui a été poncé, et ce pour tous les trucs qui doivent être vernis (et qui sont donc sensés avoir été poncés au préalable)


    Je peux te garantir que la solution A sera bien plus rapide, car chaque truc ne sera pris en main et reposé qu'une seule fois, et que ca aussi ca prend du temps. Or, la solution B imposerait que chaque truc soit pris en main et reposé minimum deux fois. Et cela va monter à quatre fois pour ceux qui doivent être poncés et vernis. Et tout le temps que tu perds à prendre un truc et à le reposer, c'est du temps perdu

    Hé bien, tu peux te dire qu'il en va exactement de même pour le processeur: accéder à une donnée qui se trouve en mémoire, cela prend du temps parce que cela implique deux choses:
    • la barrette mémoire doit RAM se "brancher" de manière à fournir la donnée qui est demandée et
    • le processeur doit copier la donnée qu'il a demandé dans un registre



    Ca prend d'ailleurs tellement de temps d'obtenir une information depuis la mémoire RAM que les processeurs utilisent ce que l'on appelle la mise en cache de données. Le principe est relativement simple : une fois que la barrette mémoire a été branchée afin de lui permettre de fournir une donnée, la différence de temps nécessaire à l'obtention de 1 seul octet et le temps qu'il faut pour obtenir 1ko (1024 octets) est "minime" (au yeux de la RAM).

    Mais ne te méprends pas, cela prend quand même "un temps fou" aux yeux du processeurs, dont l'unité de temps est un bon millier de fois plus petite que celle de la RAM.

    Si bien que, lorsque le processeur à la RAM de lui fournir une donnée particulière, il ne se contente pas de la seule donnée en question: il récupère directement 1ko qu'il va placer dans une mémoire particulière appelée le cache. Il s'agit d'une très petite quantité de mémoire, mais hyper rapide (par comparaison aux barrettes de RAM qui proposent de très grands espaces de stockage mais dont l'accès est particulièrement lent).

    Le but de la manoeuvre est de se dire que, avec "un peu de chance" la donnée que l'on demandera au processeur de manipuler "la fois d'après" sera... juste à coté de celle qu'il doit manipuler pour l'instant. Evidemment, c'est un quitte ou double. Car, si la donnée que le processeur doit manipuler "après" est "à coté" de celle qu'il vient de terminer de manipuler, il n'y a même plus besoin de s'adresser à la RAM. Et plus on sera dans ce cas de figure, moins le processeur devra attendra après la donnée qu'il doit manipuler. Par contre, si la donnée dont il a besoin "après" n'est pas dans le cache, il a quand même demandé 1ko de données inutiles.

    Mais la mise en cache des données n'est que la première partie du travail, car, pour que le processeur puisse manipuler une donnée, il faut qu'il puisse y accéder au travers d'un de ses registres. Charger une donnée dans un registre depuis le cache du processeur, cela ne prend pas vraiment longtemps. Mais une goutte de pluie ne représente rien par rapport à la masse d'eau de l'océan. Et pourtant, l'océan n'est composé que de gouttes de pluie! Et tu as déjà vu les inondations et les dégats que peut provoquer la pluie

    Tu dois donc bien penser que, quelle que soit l'action que tu entreprends, elle va prendre "un certain temps" (ca me fait penser au sketche de Fernand Raynaud ca). Et, si tu multiplie suffisamment "ce certain temps", tu obtiendra une durée assez longue que pour sembler pénible à un humain (qui a pourtant déjà beaucoup de mal à entrevoir les centièmes de secondes)
    A méditer: La solution la plus simple est toujours la moins compliquée
    Ce qui se conçoit bien s'énonce clairement, et les mots pour le dire vous viennent aisément. Nicolas Boileau
    Compiler Gcc sous windows avec MinGW
    Coder efficacement en C++ : dans les bacs le 17 février 2014
    mon tout nouveau blog

Discussions similaires

  1. Unreal Engine 4 – Tutoriels pour débutants - Les systèmes de particules
    Par LittleWhite dans le forum Développement 2D, 3D et Jeux
    Réponses: 0
    Dernier message: 26/06/2016, 11h54
  2. [OpenGL 3.x] Système de particules full GPU
    Par robinsondesbois dans le forum OpenGL
    Réponses: 1
    Dernier message: 09/06/2015, 13h23
  3. Transparence sur un système de particules
    Par dream25 dans le forum OpenGL
    Réponses: 3
    Dernier message: 10/09/2011, 14h41

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