Comment puis-je optimiser mon simulateur de physique de base ?

Question

J'ai écrit un physique simple modeler qui me permet de faire rebondir les balles autour de l'écran. Vous pouvez cliquer et faire glisser pour lancer une balle, ou vous pouvez générer des boules de centaines et de les regarder interagir avec d'autres personnes.

[Lien vers la plus grande version]

Il a été un peu de fun au programme de travail et je veux aller plus loin, si je peux. Je sais qu'ils disent que la pré-maturité d'optimisation est la racine de tous les maux, mais je suis en train de frapper les performances réelles barrières et je veux savoir si quelqu'un qui est expérimenté dans le jeu/le développement de simulateurs peuvent m'aider.

Problème:

Pour l'instant, mon programme s'étouffe si vous ajoutez trop de ballons (il n'arrive pas à gérer plus de 800 sur ma machine). Si vous le faites, la simulation n'est pas réaliste et toutes les boules se chevauchent les uns les autres sur le fond.

Le problème est dans la détection de collision. Dans la plupart des cas naïf, la détection de collision est un O(N^2) problème. Chaque boule vérifie chaque autre balle. Cela devient de la mauvaise performance, assez rapidement (même après 100 balles que vous allez faire 10k les tests de collision par itération de la boucle).

Si vous regardez ici, vous pouvez voir une capture d'écran de l'endroit où j'ai ajouté plusieurs centaines de balles. Le simulateur ne peut pas tenir en place et ils commencent à se chevaucher les uns les autres.

[Lien vers la plus grande version]

Actuellement, j'ai de détecter les collisions par la recherche de chevauchement des balles. Si je trouve deux balles qui se chevauchent, je me sépare d'eux par leur distance minimale de la traduction (DMT), ou de les pousser dehors. J'utilise ensuite un physique simple équation d'ajuster leur impulsion des vecteurs et ils s'en vont dans des directions différentes après la collision.

Il fonctionne très bien, sauf si il y a trop de balles la distance minimale de la traduction devient perceptible. Ils commencent à se chevauchent par de grandes quantités et constamment bousculer les autres sur le fond. Il y a pire plus je l'augmentation de la "gravité". La pression sur eux est augmenté et le montant qu'ils sont compressés/se chevauchent les uns les autres les augmentations.

Encore une fois, je n'ai pas de questions jusqu'à ce que j'ai touché un nombre considérable de N le nombre de boules.

Optimisation De La Méthode:

La Détection De Collision -
Balayage et taillez - (aka. De tri et de Balayage)

J'utilise un tri d'insertion sur mes couilles à chaque itération de la boucle le long de leur axe x. En raison de la nature de l'Insertion de Sorte que je peux exploiter la cohérence temporelle de mon simulateur. Un cadre à l'autre, les boules de postes de changer légèrement de sorte que le tri n'a pas beaucoup de travail à faire. Cela apporte Linéaire amorti Sortes d'exécution de O(N) ou linéaire plutôt que la moyenne des temps d'exécution de O(N^2).

Puisque les boules sont triés, je fais quelques vérifications préalables à ma deuxième boucle avant de vérifier les collisions. Maintenant je n'ai qu'à vérifier les boules à proximité les uns des autres (parce qu'ils sont classés le long de l'axe des x), et j'sortir de la seconde boucle à chaque fois que je case une balle contre un autre balle dont xmin est plus grand que le xmax de l'actuel ballon. Donc il saute des milliers de contrôles.

Quand je l'ai fait, cela a été une énorme amélioration de la vitesse. Cependant, je voudrais tout de même être en mesure de traiter plus de 600 à 800 balles. J'ai lu sur les Moteurs de Physique que de la poignée facilement la détection de collision entre 10k objets en même temps, donc j'aime à penser que je pourrais atteindre 1-2k avec un peu de travail.

Après l'exécution d'un profiler , il est apparu que la Détection de Collision est de manger d'environ 55% de mon temps alors que le rendu était en train de manger d'environ 45%. Donc, ce sont mes deux plus cher.

---

Question:

Pouvez-vous penser à une meilleure algorithmes ou des techniques qui permettraient de mon simulateur d'être capable de gérer plus de balles?

---

Code:

Ensemble Du Projet:

svn checkout http://simucal-projects.googlecode.com/svn/ballbounce/trunk/

ou, cliquez ici pour parcourir les fichiers manuellement dans votre navigateur.

Sections d'Intérêt:

• Pastebin: checkCollisions() - w/ Balayage et de Pruneau
• Pastebin: resolveCollision() - Cher vrai contrôle des collisions et de la résolution si toujours pas retirée par Balayage et de Pruneau.
• Pastebin: render() - Rendu seul, mange environ 45% de mon temps.

Answer 1

Le moyen le plus simple est de ne pas l'Objet de test vs Objet collisions, remplir un tableau avec le centre de chaque boule. Puis, à partir de chaque centre d'analyse un carré de taille 4*rayon centré sur ce point (vous pouvez l'optimiser un peu tout ça en n'utilisant pas un carré, au détriment de rendre le code plus complexe). Si il y a un autre centre dans ce carré, c'est seulement alors que vous vérifiez pour voir si elles sont dans les 2*rayon de l'autre (et donc de la collision). Vous pouvez optimiser encore ce par la réduction de la résolution, et l'arrondi de la position de la balle, de réduire le nombre de chèques que vous devez faire.

Une autre façon, est de diviser votre espace en une grille, et de stocker les objets dans la grille des régions. Vous avez uniquement besoin de vérifier les collisions entre les objets dans les zones adjacentes de grilles.

Answer 2

Garder une trace de la proximité de boules -

Tout comme l'insertion de tri est optimale en raison du changement minime par image, vous pouvez utiliser la même propriété pour garder une trace de la boule de voisins

Chaque balle ne peut interagir avec une possibilité de 6 autres boules dans les la plupart. Vous pouvez probablement exécuter un algorithme toutes les 10 images ou de sorte que les chiffres qui voisins chaque boule a, et ensuite utiliser cette information pour les dix prochaines images pour calculer les collisions réelles.

Vous pouvez également suivre les vecteurs de chaque boule, tirer des lignes virtuelles, et de voir où les lignes se croisent dans les 3-5 prochaines images et seulement calculer les collisions qui pourraient éventuellement se produire (même si quelques-uns se produire en raison d'un temps).

Tout comme vous, triés par de l'axe x, vous pouvez le "groupe" des boules dans les subdivisions à l'intérieur de la fenêtre principale. Lorsqu'une balle est à l'intérieur d'une subdivision par au moins un diamètre de la sphère, il suffit de se pencher sur les boules de la même subdivision. Si elle est plus proche d'une frontière ou deux, vous avez besoin de regarder un ou deux autres subdivisions, mais il devrait être de moins en moins de calculs.

De plus, ces subdivisions peuvent être dynamiquement trouve donc la moyenne de la subdivision a seulement 100 balles - il n'y a pas besoin d'avoir des subdivisions de la même taille avec différents nombres de boules.

En fonction de l'achalandage d'une subdivision (balles par unité carrée) vous pouvez essayer différents algorithmes - un peu remplis seule case besoins vecteur de calculs pour prédire les collisions, alors qu'une dense de subdivision peut seulement besoin d'une sorte de optimisés hexagraphic de calcul. Éparses boîtes ne peuvent pas besoin de la détection de collision pour de nombreux cadres (depuis le chevauchement ne sera pas remarqué autant que dans les zones densément peuplées, des boîtes).

La densité d'énergie d'une zone peut être déterminé - une très clairsemée zone à faible boules d'énergie a besoin de peu la collision des calculs que éparse zone de haute énergie.

Answer 3

Le noyau dur de la physique utilisation de moteurs de vectorisation de flotteurs, ce qui donne une x16 boost sur le matériel actuel si la chance, et de façon plus spécialisée en matériel. Larrabee, par exemple, peut gérer 1024 simultanée des calculs pour un theretocal x1024 coup de pouce en mathématiques de traitement (mais il a besoin de cela parce que c'est aussi le GPU)

N'ai pas regardé le code, mais êtes-vous à l'aide en mathématiques optimisations comme le fast racine carrée et binaire absolus, ou bit à bit de signe de retournement? Ces choses ne suffisent pas à aider, mais quand votre barattage de grandes quantités de données, ces techniques de rediriger certains de mathématiques pour le PROCESSEUR principal, libérant la FPU, fondamentalement, vous donnant un plus grand débit.

Aussi du CCG SIMD de génération de code littéralement suce, j'ai vu jusqu'à 16 fois plus en utilisant des VC ou IntelCompiler, cela signifie que, si vous avez prêté attention, que GCC n'était pas à l'aide de toutes les instructions SIMD à tous!

Aussi ceux allegded 10k collisions ne sont pas en rapport si étroit que vous sim, il n'est donc pas directement comparables.