Discussion :

[guppyworld]

Oui en faite ça a pas vraiment d'unité. J'avais dit ça car le système de particules est pour un jeu pixelisé

[ternel]

Alors garde en tête que les pixels, c'est une information d'affichage.
Même si tu décides d'avoir une unité = un pixel, tu dois garder une étape de conversion.

Ne serait-ce que parce que les utilisateurs ont des résolutions d'écran différentes.

[guppyworld]

Bon finalement en suivant tous les conseils je ne dépasse pas les 3 000 Particules.

J'ai pourtant bien enlevé toute les réallocations de tableau dans la boucle.

ParticleSystem.cpp

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
void ParticleSystem::computeParticles(Map *pMap)
{
    for(int i = 0; i<mCountParticles; i++){
 
        int x = mParticles[i].mPositionY/32;
        int y = mParticles[i].mPositionX/32;
 
        grid[coordToGrid(x,y)].push_back(i);
 
    }
 
    // trouver les particules voisines
    for(int i = 0; i<1920; i++)
        while(!grid[i].empty()){
            int particule = grid[i].back(); // remove particle par la fin pour O(1)
            grid[i].pop_back();
 
            mParticles[particule].mVelocityY -= GRAVITY;
 
            for(int x = -1; x<=1; x++){
                for(int y = -1; y<=1; y++){
                    int a = i + x*32 +y;
 
                    if(a < 0 || a >=1920)
                        continue;
 
                    for(int z = 0; z<grid[a].size(); z++)
                    {
                        int voisin = grid[a][z];
 
                        float dx = mParticles[voisin].mPositionX - mParticles[particule].mPositionX;
                        float dy = mParticles[voisin].mPositionY - mParticles[particule].mPositionY;
                        float distance2 = dx * dx + dy * dy;
                        if(distance2 < mParticleWidth * mParticleWidth && distance2 != 0){
                            float distance = sqrt(distance2);
                            float weight = (1.0f-distance/mParticleWidth);
                            mParticleContacts.emplace_back(particule, voisin, distance, weight);
 
                            mParticles[particule].mDensity += weight;
                            mParticles[voisin].mDensity += weight;
 
                        }
                    }
                }
            }
 
            //compute pressure
            mParticles[particule].mPressure = std::max(0.0f, n * (mParticles[particule].mDensity - w0));
 
        }
 
    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);
 
 
    }
 
    // 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;
    }
}

ParticleSystem.h

Code :

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

1
2
3
4
5
const static int MAX_PARTICLES = 6000;
 
        Particle mParticles[MAX_PARTICLES];
        std::vector<ParticleContact> mParticleContacts;
        std::vector<int> grid[1920];

[dalfab]

J'ai l'impression que les recherches ne vont pas dans le bon sens.
L'optimisation de ce code dépend plus du bon choix du pré-decoupage (et donc du choix 32x32) que des problèmes d'allocations. Pour vérifier cela, il suffirait peut-être d'utiliser un profileur de performance pour détecter s'il y a un goulet d'étranglement.
Si la grille est "sur-découpée" il sera dans les lignes de parcours
Si la grille est "sous-découpée" il sera vers la ligne if ( distance2 < mParticleWidth * mParticleWidth ).
Si c'est sur une phase d'allocation alors, il faudra améliorer les allocations.

Sinon le test if(a < 0 || a >=1920) me parait laisser passer des parcours de cases inoportunes alors que le test précédent if ( a < 0 || a >=nbCellHeight || b < 0 || b >= nbCellWidth ) était ok.
Utiliser des index, plutôt que des pointeurs bruts sur les Particle éviterait une indirection faite très fréquemment.

[Pyramidev]

EDIT 2017-08-21-03h38 : Message supprimé. Au début, j'avais cru que chaque couple (X, Y) se trouvait deux fois dans mParticleContacts, mais j'avais mal lu ton code : je n'avais pas fait assez attention à

Code :

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

grid[i].pop_back();

[ternel]

En relisant à tête reposée, je réalise que tu nous as dis avoir des cases de 32*32 avec des particules de 20*20.

Cela signifie que tes cases ne peuvent contenir que très peu de particules.
Du coup, ton découpage n'améliore rien du tout.
Tu as 1920 * 8 * (6000/1920)² tests au mieux. (et bien pire si ta "soupe" n'est pas homogène)

Essaye des cases de 100² (soit 5 fois la largeur d'une particule)

Et je continue à dire qu'il te manque des classes utilitaires (vecteur mathématique, notamment)
Est-ce qu'on pourrait voir ta classe de Particule?

[guppyworld]

Je suis sous code blocks et j'ai essayé d'utiliser le profiler mais je ne comprend pas pourquoi le gmon.out n'est pas généré. J'ai pourtant bien selectionné les options -g et -pg dans le compiler. J'ai également ajouté ces options dans les build options du projet.

-----------

Cela signifie que tes cases ne peuvent contenir que très peu de particules.
Du coup, ton découpage n'améliore rien du tout.
Tu as 1920 * 8 * (6000/1920)² tests au mieux. (et bien pire si ta "soupe" n'est pas homogène)

Essaye des cases de 100² (soit 5 fois la largeur d'une particule)

Et je continue à dire qu'il te manque des classes utilitaires (vecteur mathématique, notamment)
Est-ce qu'on pourrait voir ta classe de Particule?

En faite je me disais que plus la cellule est petite, moins il y a de particule dans chaque cellule est donc moins il y a de test de collision à faire. Après c'est vrai qu'il y a plus d'itération dans ce cas là.

Sinon ma classe Particule il n'y a pas grand chose a voir: juste la fonction updatePosition

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
void Particle::updatePosition(Map *pMap, float timeStep)
{
    float dx, dy, distance;
 
    int x, y;
 
    if(mVelocityX>0)
        x = 1;
    else
        x = -1;
 
    if(mVelocityY>0)
        y = 1;
    else
        y = -1;
 
 
    if(!pMap->verifierCollision(mPositionX + (mVelocityX*timeStep) + mWidth/2*x, mPositionY))
        mPositionX += timeStep * mVelocityX;
    else{
        int coordX = mPositionX + (mVelocityX*timeStep) + mWidth/2*x;
        if(x == -1)
            mPositionX = (coordX/32 +1) * 32 - mWidth/2*x;
        else
            mPositionX = (coordX/32) * 32 - mWidth/2*x;
        mVelocityX = -0.3f * mVelocityX;
    }
 
    if(!pMap->verifierCollision(mPositionX, mPositionY + (mVelocityY*timeStep) + mWidth/2*y))
        mPositionY += timeStep * mVelocityY;
    else{
        int coordY = mPositionY + (mVelocityY*timeStep) + mWidth/2*y;
        if(y == -1)
            mPositionY = (coordY/32 +1) * 32 - mWidth/2*y;
        else
            mPositionY = (coordY/32) * 32 - mWidth/2*y;
        mVelocityY = -0.3f * mVelocityY;
    }
}

ps: verifierCollision() est en 0(1), il s'agit simplement d'un accès dans un tableau 2d

[ternel]

Si, c'est bien sa déclaration qui m'intéresse, tout particulièrement ses membres.
Le contenu des fonctions, en effet, est probablement peu intéressant.

Quand tu me l'auras donné, je te montrerai comment faire quelque chose de beaucoup plus clair, simple, et au moins aussi efficace.

Ta détection de collision est bizarre, tu ne devrais tester que la nouvelle position complète (x+dx, y+dy), pas (x+dx, y)

[guppyworld]

Code :

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

1
2
3
4
5
6
7
8
9
bool Map::verifierCollision(int x, int y)
{
    if (x<0 || x> (32*WIDTH) || y<0 || y>(32*HEIGHT))
        return true;
    else if(backgroundMap[29-(y/32)][x/32]!=0)
        return true;
    else
        return false;
}

Ta détection de collision est bizarre, tu ne devrais tester que la nouvelle position complète (x+dx, y+dy), pas (x+dx, y)

La collision est test sur les x ensuite sur les y


Edit: J'avais pas vu que tu voulais voir les membres de la classe, désolé.

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
class Particle
{
    public:
        Particle();
        Particle(int type, float positionX, float positionY, float velocityX, float velocityY, int lifeTime, float width);
        virtual ~Particle();
 
        void updatePosition(Map *pMap, float timeStep);
 
 
        int mType;
        float mWidth;
        float mPositionX;
        float mPositionY;
        float mVelocityX;
        float mVelocityY;
        float mForceX;
        float mForceY;
        float mPressure;
        float mDensity;
        int mLifeTime;
};

Je n'ai pas fait de classe utilitaire car je ne suis pas encore a l'aise en c++ donc j'évite de compliquer le code.

[Seabirds]

Je n'ai pas fait de classe utilitaire car je ne suis pas encore a l'aise en c++ donc j'évite de compliquer le code.

Ce n'est que mon humble avis de débutant toujours pas très à l'aise en C++ :

Les multiples interventions des membres de développez.com m'ont poussé à écrire du code utilitaire (et j'avais les mêmes réticences que toi), mais au final ça a rendu mon code bien plus lisible et bien moins compliqué !
Pour reprendre leurs mots, le code restera complexe (parce que ton problème reste complexe), mais il ne sera pas tentaculairement compliqué à comprendre et tu grilleras pas 80% de tes neurones à garder à l'esprit une foultitude de détails d'implémentation qui occupe ta rame cérébrale pour quedal et t'empêchent de te concentrer sur ton problème de particules .
Cette citation que j'aime bien de Whitehead illustre bien le principe :

By relieving the brain of all unnecessary work, a good notation sets it free to concentrate on more advanced problems.

En gros ton code utilitaire deviendra un ensemble de petits mots de vocabulaires bien choisis pour représenter clairement les concepts de ton problème

D'après ce que j'ai compris on perd rarement à faire des classes utilitaires, et je ne compte plus le nombre de problèmes que les membres de la communauté ont résolu en me disant "cache ces détails dans une nouvelle classe" mais bon ça ils t'en parleront vachement mieux que moi

[ternel]

Merci Seabirds, c'est effectivement l'idée.

Je vais pouvoir te proposer diverses choses.

Pour la dynamique des sphères (sans frottement de surface), les grandeurs physiques caractéristiques sont le rayon, la position et la vitesse.
Du coup, je me pose demande ce que sont:

• la force
• la pression
• la densité
• si le "width" est un rayon ou un diamètre, sachant que le rayon est plus utile (il y a collision entre deux sphère si leur distance est inférieur à la somme de leur rayons)
• Le rôle de la durée de vie.

J'imagine que la masse est obtenue a partir de la densité et du volume.
Un corps seul n'a pas de pression, et une particule n'a pas de densité. Mais j'imagine que tes "particules" sont des billes.
A noter, la densité d'un corps homogène est sa masse volumique, divisée par celle de l'eau.

[guppyworld]

En faite pour faire le système de particule je me suis basé sur les slides de présentation de l'application LiquidFun.

https://docs.google.com/presentation...dit#slide=id.p

Bon biensur je n'obtiens pas un liquide super réaliste en utilisant uniquement les formules simpliste du slide.

ps: J'ai essayé de faire les formules venant de la methode SPH pour les particules. Mais ça na pas vraiment fonctionné, notament pour trouver la valeur des constantes.

Du coup j'utilise les formules plus simple du slide.

Oui les particules sont des billes. Mon but est d'obtenir un résultat un peu comme celui ci

http://google.github.io/liquidfun/

[ternel]

Ok, je vois l'idée.

Première chose, en parlant des slides.
Eux ont utilisés une technique de "ECS" entity component system.
A savoir qu'ils n'ont pas de classe Particle du tout. Mais une série de tableaux, voisins. C'est utile pour l'affichage sur carte graphique, pour diverses raisons interne (notamment, le transfert entre la mémoire CPU et la mémoire GPU)
C'est un "gros" détail d'implémentation, qui peut être utile par la suite.

Je t'invite à noter dans ton code (par des commentaires?) les variables constantes (nature, dimension, etc), celles relatives à "maintenant" (position, vitesse), et celles liées à l'avenir (accélération, notamment)

Ils ont modélisés des forces intéressantes, comme les collisions multiples (produisant une pression) et de viscosité (qui est normalement simplement un coefficient de frottement fluide).

Tu affiches tes particules, actuellement?
Est-ce que ce ne serait pas tout simplement ton affichage qui ralentit tout?

[guppyworld]

Tu affiches tes particules, actuellement?
Est-ce que ce ne serait pas tout simplement ton affichage qui ralentit tout?

En désactivant l'affichage des particules, on peut mettre a peine 300 particules de plus avant de ramer. Donc je pense pas que l'affichage soit en cause.

Finalement en utilisant le profiler le problème vient bien de la recherche des contacts j'ai l'impression


Avec le code suivant:

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
 
void ParticleSystem::createGrid()
{
    for(int i = 0; i<mCountParticles; i++){
 
        int x = mParticles[i].mPositionY/32;
        int y = mParticles[i].mPositionX/32;
 
        mGrid[coordToGrid(x,y)].push_back(i);
 
    }
}
void ParticleSystem::findContacts()
{
    // trouver les particules voisines
    for(int i = 0; i<1860; i++)
        while(!mGrid[i].empty()){
            int particule = mGrid[i].back(); // remove particle par la fin pour O(1)
            mGrid[i].pop_back();
 
            mParticles[particule].mVelocityY -= GRAVITY;
 
            for(int x = -1; x<=1; x++){
                for(int y = -1; y<=1; y++){
                    int a = i + x*32 +y;
 
                    if(a >= 0 && a < 1860)
                        for(int z = 0; z<mGrid[a].size(); z++)
                        {
                            int voisin = mGrid[a][z];
 
                            float dx = mParticles[voisin].mPositionX - mParticles[particule].mPositionX;
                            float dy = mParticles[voisin].mPositionY - mParticles[particule].mPositionY;
                            float distance2 = dx * dx + dy * dy;
                            if(distance2 < mParticleWidth * mParticleWidth && distance2 != 0){
                                float distance = sqrt(distance2);
                                float weight = (1.0f-distance/mParticleWidth);
                                mParticleContacts.emplace_back(particule, voisin, distance, weight);
 
                                mParticles[particule].mDensity += weight;
                                mParticles[voisin].mDensity += weight;
 
                            }
                        }
                }
            }
            //compute pressure
            mParticles[particule].mPressure = std::max(0.0f, n * (mParticles[particule].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;
    }
}
 
void ParticleSystem::computeParticles(Map *pMap)
{
    createGrid();
    findContacts();
    computeForces();
    updatePosition(pMap);
}

[guppyworld]

En testant avec un quadTree je passe de 2000 particules max à 150 particules max

[moldavi]

Bonjour.

Bonjour,

Je suis actuellement entrain d'implémenter un système de particules dans un environnement en 2D. Pour le moment le programme peut traiter environ 2 000 particules avant de commencer a ramer. Je commence a être a cours d'idée sur les optimisations que je peut faire pour augmenter le nombre de particules.

Je vais juste poser une question : "le programme peut traiter environ 2 000 particules", d'accord, mais quelle est l'objectif ? 2001 particules ? 3000 particules ? 1 millions de particules ? etc...

Je vois plein de messages pour tenter d'optimiser ton code, mais si l'objectif est 1 milliards de particules avec un Pentium 2 et 100 Mo de RAM, c'est peine perdue...

Première étape, définir le nombre de particules à atteindre. Deuxième étape, le matériel est-il capable de prendre en charge l'objectif (processeur/ram/cg/etc...). Dernière étape, optimiser le code.

Bref, vous commencez tous par la dernière étape...

PS : j'abrège le nombre des étapes, il y a en a peut-être plus, selon la réponse à la question.

[ternel]

Théoriquement, un modèle de collision doit au plus gérer N² calculs de collisions.
La mémoire requise est N * sizeof(particules) + sizeof(map)
avec 4Go de ram, on peut raisonnablement avoir 80 octets par particules (10 entiers 64bits) et donc 50000 particules.
Une itération prend alors au plus 2,5 milliards de calculs de collisions, soit à 10000 cycles processeur l'un, 25 secondes à 1Ghz, et 6s à 4Ghz.
C'est long, mais pas tant que ça.

Si on fait une optimisation qui divise par 10 le nombre de collisions à calculer, c'est déjà très intéressant. (moins d'une seconde par itération)
Si on optimise les accès mémoire pour réduire les défauts de cache, on peut gagner beaucoup aussi.

L'objectif semble être l'affichage en temps réel.
Il faut passer en dessous de 50 milli-secondes pour avoir un résultat visuellement satisfaisant.
A noter qu'il faut aussi prendre en compte le temps de dessin, mais là, on est large: 50000 cercles, c'est vite géré.

D'un point de vue technique, il faut absolument séparer la structure Particule de son évolution, ne pas mélanger les variables d'état (position, vitesse, masse) des variables de calcul comme la force appliquée à l'itération actuelle

[guppyworld]

Je pensez atteindre au moins les 20k particules.

Pour le moment, je divise la map en grille de 16 par 16 avec des particules qui ont un diamètre de 10. Et chaque particule test si elle est en collision uniquement avec les particules des cases voisines. Le problème est que cette fonction prend trop de temps.

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
void ParticleSystem::findContacts()
{
    for(int i=0; i<mCountParticles; i++)
    {
        int caseX = mParticles[i].mPositionX/16;
        int caseY = mParticles[i].mPositionY/16;
 
 
        // 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));
 
    }
}

[Kannagi]

On considérant que ton algo est correct et optimisé et que t'as mis le -O3.

Quand on vise les performances ,Il faut évité les appel de fonction et méthode , ce qui n'est pas ton cas.
Je pense que si tu arrive a mettre un tableau a la place : mGrid[caseY-1][caseX+j].size() , ça optimiserait pas mal :p
De plus que les tableaux de 'structure' qui l'obligera au compilateur forcément a faire un calcul supplémentaire (pour pointer la bonne adresse) que a un simple tableau.

Sinon tu peux gérer tout cela via ton GPU avec les shader x)

[koala01]

Salut,

As tu remarqué que le gros du temps (plus du tiers, vu qu'on est à 36.45%) se perd dans ParticleSystem::findContacts alors qu'elle n'est appelée que 2800 fois contre plusieurs millions d'appels pour certaines fonctions

Je note aussi que l'on a le même nombre d'appels (pour 1.73% du temps) à ParticlSystem::computeForces et Particle::updatePosition (pour 0.73% du temps).

J'en déduis donc que tu dois avoir "quelque part" une boucle qui contiendra un appel à ces trois fonctions.

Si tu veux améliorer les choses, il va falloir partir de cette fonction "bouffeuse de temps" et voir ce qu'elle fait afin d'améliorer son rendement.

Pourrais tu donc commencer par nous donner le code complet:

• de ta classe ParticleSystem (la définition complète de ta classe, telle qu'elle se trouve dans le fichier hpp qui lui est dévolu)
• l'implémentation de la fonction ParticlSystem::computeForces()
• des fonctions de ParticleSystem qui seraient éventuellement appelées par ParticlSystem::computeForces()

Il nous faudra surement d'autres précisions par la suite, mais ce sera déjà un bon début