Discussion :

[Nyarlathotep]

Bonjour,

Je suis en train de coder un moteur physique et j'utilise actuellement un octree pour subdiviser l'espace afin de diminuer le nombre de collisions entre objets à tester (un genre de broadphase test, donc). J'ai vu qu'il existait une méthode appelée Sweep and Prune, utilisée dans Bullet, notamment, et j'aimerai la comprendre, mais après de nombreuses et infructueuses recherches, j'en suis toujours au même point.

Il semblerait que cette méthode utilise une liste contenant les limites des boîtes englobantes pour chaque axe, et qu'ensuite un tri soit effectué. Quel algorithme de tri est le plus rapide dans ce cas, et comment déterminer les objets en collision à partir de la liste triée ?

J'ai également entendu parler de cohérence temporelle pour accélérer cet algorithme, mais là encore, dans tous les articles que j'ai lu, le concept reste un peu flou.

D'avance, merci pour vos réponses.

[Mikmacer]

Certains moteurs physiques étant open-source, est-ce que tu as regardé le code source le leurs implémentations sur le SAP? Je n'ai jamais utilisé cette méthode, mais en regardant certaines implémentations codés tu pourrais t'en faire une bonne idée.

Pour l'algorithme de tri, le quicksort est souvent une valeur sûr !

[Nyarlathotep]

Merci pour cette réponse.
J'ai en effet regardé le code de ODE et celui de Bullet mais il n'y a aucune explication quant au fonctionnement des algorithmes. D'ailleurs, j'ai remarqué que ODE utilisait non pas le quick sort, mais le radix sort, ceci étant peut-être dû à la cohérence temporelle (le quick sort est lent sur des tableaux presque ordonnés, et donc un tri de type insertion sort serait une meilleure alternative).

[Frifron]

Salut, oui en effet sur un tableau ordonnée le quicksort et moins performant que le tri par insertion mais bon il l'est beaucoup plus dans tous les autres cas et surtout avec des gros tableaux (le tri par insertion ayant une complexité de O(n²) alors que le quick sort est en O(nlogn)).

En regle général le quicksort est utilisé couramment avec un switch sur un tri par insertion lorsque les sous ensembles deviennent relativement petits. (c'est la méthode de tri utilisé en général dans les implem de la librairie standard)

Le radix sort peut etre une bonne alternative mais il demande par contre un buffer supplémentaire donc plus de mémoire.

[Nyarlathotep]

Je viens de découvrir sur wikipedia un algorithme aux performances intéressantes : le shell sort ([ame]http://fr.wikipedia.org/wiki/Algorithme_de_tri[/ame]). Apparemment, les performances sont très légèrement inférieures au quick sort, mais dans le cas d'un tableau quasiment ordonné, elles sont supérieures, je pense que j'utiliserai cet algorithme.

Mais pour le cas d'un SAP sur plusieurs dimensions, comment procéder ?
1° Faire le SAP sur tous les axes puis faire l'intersection des listes de paires ?
2° Faire les SAP simultanément ?
3° Autre solution ?

[Mikmacer]

Je viens d'annalyser l'implémentation de la librairie physique JigLibX pour le SAP :

Tu as une liste de d'ensemble physique à tester.
Tu as une liste d'ensemble physique actif.
Tout les ensembles ont un AABB(Aligned Axis Bounding Box) en world space, un espace de coordonnées commun pour les tests.

Tu dois éléminer les tests potentiels en comparant le X des AABB

Voici le pseudo code du SAP :

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
ListeElementPhysique = La liste d ensemble physique à tester
ListeElementActif = Une liste dynamique utililaire à chacune des itérations de tests
 
DétecterCollision()
{
	// Classer les éléments en ordre de grandeur des X de la position minimum des aabb englobant les éléments physique : AABB.Min.X
	ClasserToutLesÉlémentsEnOrdreCroissant(ListeElementPhysique)
	Effacer tout les éléments de ListeElementActif 
	Pour chacun des éléments I de ListeElementPhysique 
	{
		Pour chacun des éléments J de ListeElementActif 
		{
			// On efface l élément actif J pour les prochains tests, car les éléments suivant vont avoir un MINIMUM en X plus grand que le MAXIMUM en X du AABB de l'élément J
			Si J.AABB.MAX.X < I.AABB.MIN.X
			{
				ListeElementActif.Effacer(J)
			}
			Sinon
			{
				Si TesterCollision( J.AABB, I.AABB)
				{
					TesterCollision(I,J)
				}
			}
			ListeElementActif.Ajouter(I)
		}
	}
}

[Nyarlathotep]

Merci, mais l'exemple de code donné n'effectue le test que sur un seul axe, et mon problème consiste à effectuer le test sur les 3 dimensions pour diminuer le nombre de paires à tester au maximum.

Ma question est donc celle-ci : Comment réaliser le test (et donc le tri) sur les trois axes ? J'ai pensé à ajouter un compteur de collision à chaque paire, de cette façon, on n'ajoute une paire que si elle a été rencontrée lors des trois tests. Cela permettrait de faire les tests successivement, mais je me demande s'il est possible de les réaliser simultanément. C'est tout l'objet de mon post.

[Nyarlathotep]

Bon, j'ai effectué des recherches sur le sujet, et j'ai implémenté un algorithme de Sweep and Prune à partir de articles de D.Baraff et de P.Terdiman. Je me demandais si suffisamment de personnes étaient intéressées pour que j'écrive un tutoriel en français sur cette méthode (Simplement je ne sais pas comment envoyer un tutoriel sur développez.net, et, apparemment, peu de gens semblent intéressés par la programmation des parties critiques d'un moteur physique, comme l'algorithme de broadphase...)

[Mikmacer]

Salut!

Ça pourrait toujours être intéressant, mais j'aimerais savoir si tu as remarqué des différences de performances entre le SAP et l'Octree(Que tu semblais avoir implémenté) ?

[Nyarlathotep]

Les différences de performances sont assez peu flagrantes, de l'ordre de la dizaine de millisecondes (sur un Duron 1200Mhz), et en réalité, on ne peut pas vraiment dire si l'un ou l'autre des algorithmes est le plus rapide. Cela dépend de ce que l'on veut faire : dans une simulation ou les objets se déplacent rapidement, je pense qu'un octree semble être une solution viable.

Mais dans le cas où les objets ne bougent assez peu ou si l'on veut implémenter un multi-sap tirant parti de la carte graphique, on prendra plutôt un algorithme de type sweep and prune (d'autres alternatives très rapides sont utilisables : les arbres binaires dynamiques utilisés dans Bullet en sont un exemple). Dans mon cas, le passage de l'octree au sweep and prune m'a fait gagner quelques FPS.

Il faut également prendre en compte d'autres paramètres dans la création d'un algorithme de broadphase : la gestion des paires. Un "pair manager" qui est assez performant peut tout changer. L'ajout et la suppression des paires est en soi un problème au moins aussi important que l'algorithme de séparation des objets.

Pour avoir un aperçu des performances des différents algorithmes :
http://www.bulletphysics.org/mediawi...DTestFramework
http://www.codercorner.com/SweepAndPrune.htm

Le mieux reste tout de même de créer sa propre implémentation car, même si cela représente un énorme travail, on arrive à des résultats souvent meilleurs
que ceux donnés par des moteurs physiques élaborés ne serait-ce parce qu'on produit au final un code dans une optique précise, et non dans un but de réutilisation dans un contexte plus général.