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

Glissement d'une forme englobante contre un arbre BSP

Cet article présente les algorithmes permettant de faire glisser une forme englobante mobile contre un arbre BSP fixe, en proposant, étape par étape, une implémentation en C++. Avertissement : nous ne décrirons pas les objets et opérations géométriques de base tels que vecteurs, plans, produits scalaires, distances, etc... Nous ne détaillerons pas non plus les arbres BSP et leur principe, une connaissance minimale de ceux-ci est souhaitée.

Article lu   fois.

Les deux auteurs

Profil Pro

Liens sociaux

Viadeo Twitter Facebook Share on Google+   

I. Introduction

Depuis l'arrivée sur la scène open-source de middlewares physiques de qualité, il devient difficile d'appréhender les techniques de collisions de base, pourtant suffisantes dans de nombreux cas. Le glissement d'une forme englobante contre un arbre BSP est sans doute l'une des plus utiles d'entre elles. Il semble donc opportun d'en expliquer, étapes par étapes, le mécanisme. Nous présenterons d'abord les éléments géométriques mis en oeuvre dans ce système, puis nous déterminerons les classes correspondantes. Ensuite, nous détaillerons l'algorithme de détection des collisions. Enfin, nous détaillerons l'algorithme de glissement utilisant les résultats de la détection.

Remarque : les schémas illustrant cet article sont des représentations en 2D (pans de coupe) des mécanismes 3D décrits.

II. Eléments géométriques

II-A. Rappels sur les arbres BSP

Un arbre BSP (Binary Space Partition) est une structure récursive de partitionnement de l'espace de type arbre binaire. Les BSP sont principalement utilisés pour stocker des décors fixes car ils permettent d'y appliquer les fonctionnalités nécessaires (affichage, collisions, etc...) à l'aide d'algorithmes extrêmement rapides et efficaces.

Le principe de l'arbre est de découper l'espace en petites zones délimitées par les murs du décor. Concrètement, une instance de noeud BSP est définie par un plan, une liste de faces sur ce plan, et possède deux arbres fils : l'un représentant l'espace avant et l'autre l'espace arrière.

formes englobantes



Une face supplémentaire, selon sa position par rapport au plan, crée un nouveau noeud dans l'espace avant ou arrière, et ainsi de suite. Une face à cheval sur le plan est coupée en deux et une moitié est ajoutée de chaque côté.

Les feuilles de l'arbre sont des instances particulières ne divisant pas l'espace. Lorsque le BSP stocke des objets strictement fermés, ayant un "intérieur" bien défini (ce que nous supposerons pour cet article), elles représentent 2 types de zones :

- Les feuilles derrière leur noeud parent décrivent un espace convexe à l'intérieur d'un objet (on les appelle feuilles solides).
- Les feuilles devant leur noeud parent décrivent un espace convexe extérieur (on les appelle feuilles vides).

Exemple : Si nous ajoutons successivement les faces A, B, C, D, E, F, G, nous obtenons le découpage et l'arbre suivant.

bsp
Arbre obtenu par ajout successif des faces A, B, C, D, E, F, G.



On remarque que les 3 feuilles solides (-) correspondent bien aux 3 zones intérieures des objets.

On constate également que la structure de l'arbre dépend de l'ordre d'ajout des faces. En fait, la construction d'un BSP est un difficile compromis entre recherche d'équilibre (plus l'arbre est équilibré, plus son parcours est rapide en moyenne) et maîtrise du découpage des faces conduisant à la prolifération des instances.

Heureusement, cette difficulté de construction est compensée par l'efficacité des algorithmes que nous pouvons appliquer, efficacité due à l'importante élimination des traitements inutiles que le tri spatial des BSP permet.

II-B. Les formes englobantes

Le principe est simple : plutôt que de traiter directement des objets 3D complexes (comme des personnages animés), on les inclut dans des formes géométriques basiques (sphères, boites, etc...) manipulées plus facilement.

formes englobantes

Les formes englobantes concernées par notre système doivent avoir quelques contraintes :
- ne pas changer de forme au cours du temps
- se mouvoir uniquement par translation (les rotations ou les changements de taille ne sont pas gérés).

Ces limitations sont dues au caractère continu de notre gestion des collisions : celles-ci seront détectées sur le mouvement des formes et non sur leur position à un temps donné. Ainsi, quelle que soit la vitesse de déplacement ou le frame-rate de l'application, un impact sera toujours pris en compte. Or, la gestion de toutes les transformations complexifie le processus. Pour un maximum de clarté, nous nous cantonnerons donc aux translations.

Nos formes sont définies par 2 paramètres :
- la position spatiale
- l'épaisseur par rapport à n'importe quel plan de l'espace (distance minimale entre la position et le plan). Nous appellerons cette valeur Offset.

Par exemple, une sphère a un offset constant pour tous les plans : son rayon. Un cube aura un plus petit offset pour un plan aligné sur un côté que pour un plan "penché".

formes englobantes

Remarque : l'offset d'une forme dépend uniquement de l'orientation du plan, son calcul n'utilise que la normale de celui-ci.

II-C. Vélocité et impact

Nous désignons par le terme vélocité le vecteur 3D décrivant le déplacement de la forme englobante. Typiquement, il s'agit du déplacement prévu entre deux images d'une application temps réel.

L'impact est l'éventuel endroit où la vélocité traverse une "paroi" du BSP. Nous décrirons cet impact par un simple nombre : la fraction entre la longueur du trajet jusqu'à l'impact et la longueur totale de la vélocité. Par exemple, une fraction de 0.25 signifie qu'un impact est situé au quart de la vélocité, une fraction de 1 signifie qu'il n'y a pas d'impact.

velocité

II-D. Impact et intersection réelle

Voici une notion essentielle du système : Nous devons définir une sorte d'épaisseur devant chaque paroi du BSP, une MIN_DISTANCE infranchissable et constante. Une forme, après impact, ne sera jamais plus près d'un mur que MIN_DISTANCE, autrement dit sa position ne sera jamais plus près que (offset + MIN_DISTANCE). Cette épaisseur doit être assez grande pour bien décoller la forme de la paroi et assez petite pour être franchie d'un coup par (presque) toute vélocité.

min distance



Ainsi, un impact sera toujours défini sur cette épaisseur, légèrement devant la paroi traversée. Cela nous amène à déterminer une deuxième fraction : celle de l'intersection réelle avec la paroi, toujours légèrement supérieure à la fraction de l'impact.

impact



Distinguer ces deux fractions est indispensable pour 2 raisons :

- Gérer les arrondis de calculs : si une forme est placée exactement sur le plan après une collision, elle risque d'être considérée légèrement derrière à la frame suivante et traverser le décor.

- Gérer les collisions multiples : pour un bon fonctionnement du glissement sur les arêtes concaves ou dans les coins (souplesse du mouvement, absence de "tremblements"), on doit connaître la paroi la plus proche du déplacement de la forme. Si la forme est "collée" à tous les plans, on ne peut pas déterminer cela. Si elle est décollée, les impacts réels permettent d'indiquer le plan le plus proche.

multi impact



Pour calculer ces fractions, nous pouvons utiliser les distances entre les points de début et fin du déplacement et le plan de la paroi.

Soient les deux points : A = position initiale du déplacement, B = A + Vélocité

d1 = distance(A, plan) - offset(forme, plan)
d2 = distance(B, plan) - offset(forme, plan)
fraction_reelle = d1 / ( d1 - d2 )
fraction_impact = (d1 - MIN_DISTANCE) / ( d1 - d2 )

III. Les classes

III-A. La classe BSP

Nous donnerons ici uniquement le contenu nécessaire à notre système.

 
Sélectionnez
// Identifiant des différents types d'instance
static const int  BSP_NODE       =  0
static const int  BSP_SOLID_LEAF = -1
static const int  BSP_EMPTY_LEAF =  1

class BSP {
	
	public:
	
	// Type de l'instance
	int type;

	// Plan de découpage de l'espace
	Plane* plane;
	
	// Sous-espace arrière
	BSP* rear_child;

	// Sous-espace avant
	BSP* front_child;

};

III-B. Les classes Shape et Sphere

Nous représenterons nos formes englobantes par la classe virtuelle Shape définie par une position et un calcul d'offset selon un plan.

 
Sélectionnez
class Shape {

	public:
	
	// Retourne la position de la forme
	virtual Vect3d* getPosition();

	// Retourne l'offset de la forme selon le plan
	virtual float getOffset(Plane* plane);
};


Nous pouvons implémenter cette classe selon la forme voulue. Par exemple, définissons la plus simple de toutes : la sphère, dont l'offset est constant.

 
Sélectionnez
class Sphere : public Shape {
	
	private : 

	// Position de la sphère
	Vect3d* pos;

	// Rayon de la sphère
	float offset;

	public : 
	
	// Constructeur
	Sphere(Vect3d* spherePos, float sphereOffset);

	// Retourne la position de la sphère
	Vect3d* getPosition();

	// Retourne l'offset de la sphère selon le plan
	float getOffset(Plane* plane);
};

Sphere::Sphere(Vect3d* spherePos, float sphereOffset)
{
	pos = spherePos;
	offset = sphereOffset;
}

Vect3d* Sphere::getPosition()
{
	return pos;
}

float Sphere::getOffset(Plane* plane)
{
	// L'offset de la sphère est son rayon, quel que soit le plan
	return offset;
}

III-C. La classe Mover

C'est la classe en charge de fournir la vélocité. La manière dont celle-ci est calculée et mise à jour est à la discrétion du développeur car elle peut décrire beaucoup de types de mouvement (mouvement uniforme, accélération, gravité, etc...). Nous proposerons juste une classe virtuelle Mover qui peut retourner un vecteur 3D décrivant la translation souhaitée de la forme, à chacun de l'implémenter.

 
Sélectionnez
class Mover
{
	public virtual: Vect3d* getMove();
};

III-D. La classe Impact

Cette classe recueille les résultats d'un test de collision. Elle stocke :

- les 2 positions (initiale et après mouvement) de la forme englobante
- le vecteur de mouvement
- la normale au plan qui a subi la collision
- les 2 fractions impact et réelle

 
Sélectionnez
class Impact {

	public:

	// Position initiale
	Vect3d* point_debut;

	// Position finale après mouvement
	Vect3d* point_fin;

	// Vecteur de mouvement (point_debut, point_fin)
	Vect3d* segment;

	// Normale au plan traversé si impact
	Vect3d* normal;

	// Fraction de l'impact
	float frac_impact;

	// Fraction de l'intersection réelle
	float frac_reelle;

	// Constructeur
	Impact();

	// Initialise l'objet avec les 2 positions de la forme
	void reset(Vect3d* position_debut, Vec3d* position_fin);

	// Efface les données impact
	void clearImpact();
	
	// Retourne si un impact est stocké ou non
	bool isImpact();

	// Stocke un impact
	void setImpact(Vect3d* normal_impact, float fraction_impact, float fraction_reelle);

	// Stocke un impact si sa fraction réelle est plus près que celle stockée
	void setNearerImpact(Vect3d* normal_impact, float fraction_impact, float fraction_reelle);
};

Impact::Impact()
{
	point_debut = new Vect3d();
	point_fin = new Vect3d();
	segment = new Vect3d();

	clearImpact();
}

void Impact::reset(Vect3d* position_debut, Vec3d* position_fin)
{
	// Stocke les 2 positions
	point_debut->assign(position_debut);
	point_fin->assign(position_fin);

	// Calcule (point_fin - point_debut) et l'assigne à segment
	segment->x = point_fin->x - point_debut->x;
	segment->y = point_fin->y - point_debut->y;
	segment->z = point_fin->z - point_debut->z;

	clearImpact();
}

void Impact::clearImpact()
{
	// Fractions de 1 : pas d'impact
	frac_impact = 1;
	frac_reelle = 1;
}

bool Impact::isImpact()
{
    return (frac_reelle < 1);
}

void Impact::setImpact(Vect3d* normal_impact, float fraction_impact, float fraction_reelle)
{
	normal = normal_impact;
	frac_impact = fraction_impact;
	frac_reelle = fraction_reelle;
}

void Impact::setNearerImpact(Vect3d* normal_impact, float fraction_impact, float fraction_reelle)
{
	if (fraction_reelle < frac_reelle) {
		normal = normal_impact;
		frac_impact = fraction_impact;
		frac_reelle = fraction_reelle;
	}
}

IV. Algorithme de détection des collisions

Cet algorithme est en charge de prendre une forme englobante, un arbre BSP, un objet Impact initialisé avec le mouvement de la forme, et de stocker dans celui-ci les données d'une éventuelle collision. Il utilise également un deuxième objet Impact dont nous détaillerons le rôle ultérieurement.

L'algorithme est récursif. Son but est de parcourir les formes convexes de l'arbre (appelées brushes) et déterminer la plus proche collision et la paroi qui en a fait l'objet. D'abord, posons l'ossature générale :

 
Sélectionnez
// Récupère la plus proche collision de l'objet shape sur l'objet bsp 
// et la stocke dans l'objet impact
void getCollision(Shape* shape, BSP* bsp, Impact* impact, Impact* iBrush);


void getCollision(Shape* shape, BSP* bsp, Impact* impact, Impact* iBrush)
{
	// Fractions impact et réelle pour les collisions
	float fImpact;
	float fReelle;

	// GESTION DES FEUILLES

	// Feuille vide
	if (bsp->type == BSP_EMPTY_LEAF) {
		// Traitement
		return;
	}

	// Feuille solide
	if (bsp->type == BSP_SOLID_LEAF) {
		// Traitement
		return;
	}

	// GESTION DES NOEUDS

	// On calcule les distances entre les 2 positions et le plan
	float d1 = bsp->plane->distance(impact->point_debut);
	float d2 = bsp->plane->distance(impact->point_fin);

	// On récupère l'offset selon le plan
	float offset = shape->getOffset(bsp->plane);

	// Forme toujours devant le noeud
	if (d1 > offset && d2 > offset) {
		// On parcourt l'espace avant
		getCollision(shape, bsp->front_child, impact, iBrush);
	}
	
	bsp->plane->invert();
	float offset2 = shape->getOffset(bsp->plane);
	bsp->plane->invert();

	// Forme toujours derrière le noeud
	else if (d1 < -offset2 && d2 < -offset2) {
		// On parcourt l'espace arrière
		getCollision(shape, bsp->rear_child, impact, iBrush);
	}

	// La forme traverse le noeud
	else {
		// Ici, on stocke l'impact
		
		// On parcourt l'espace arrière
		getCollision(shape, bsp->rear_child, impact, iBrush);

		// On parcourt l'espace avant
		getCollision(shape, bsp->front_child, impact, iBrush);
	}

}



On peut résumer l'algorithme ainsi :

On teste le trajet de la forme sur le plan du noeud BSP.
- Si la forme reste devant le plan, on teste l'espace avant
- Si la forme n'est jamais devant le plan, on teste l'espace arrière
- Si la forme traverse le plan, on stocke l'impact, on teste l'espace arrière puis on teste l'espace avant

Pour le stockage de l'impact, il faut calculer les fractions impact et réelle. Nous devons pour cela définir la fameuse épaisseur minimum de nos parois, ce qui donne :

 
Sélectionnez
// Epaisseur des parois
#define MIN_DISTANCE 0.01F

// Récupère la plus proche collision de l'objet shape sur l'objet bsp 
// et la stocke dans l'objet impact
void getCollision(Shape* shape, BSP* bsp, Impact* impact, Impact* iBrush);


void getCollision(Shape* shape, BSP* bsp, Impact* impact, Impact* iBrush)
{
        (...)
        
        // La forme traverse le noeud
        else {
                // On calcule la fraction réelle
                float d1r = d1 - offset;
                float d2r = d2 - offset;
                fReelle = d1r / (d1r - d2r);
                
                // Collision seulement si la forme va de l'avant vers l'arrière
                // et si l'impact est plus près que celui déjà stocké
                if (d1 > d2 && fReelle < iBrush->frac_reelle) {
                
                        //On calcule la fraction impact
                        float d1i = d1 - MIN_DISTANCE - offset;
                        float d2i = d2 - MIN_DISTANCE - offset;
                        fImpact = d1i / (d1i - d2i);
                        
                        // On stocke l'impact
                        iBrush->setImpact(bsp->plane->normal, fImpact, fReelle);
                }
                
                // On parcourt l'espace arrière
                getCollision(shape, bsp->rear_child, impact, iBrush);
                
                // On parcourt l'espace avant
                getCollision(shape, bsp->front_child, impact, iBrush);
        }
	
}



Alors, pourquoi stocker l'impact dans iBrush ?
Ce que nous savons de notre BSP est qu'il décrit des formes convexes fermées (brushes). C'est sur elles en réalité que nous testons les collisions. Or une brush est identifiée par une feuille solide et sa forme géométrique est donnée par les plans successivement les uns derrière les autres que nous devons parcourir pour arriver à cette feuille. Ainsi, tester les collisions sur une brush consiste à chercher l'impact le plus proche en parcourant les noeuds les uns derrière les autres jusqu'à une feuille solide.
Exemple :

parcours brush 1


Dans cette configuration, l'algorithme effectue l'enchaînement suivant :

- Test du noeud A -> parcours arrière
- Test du noeud B -> parcours arrière
- Test du noeud C -> impact ! On le stocke dans iBrush puis parcours arrière
- Test du noeud D -> parcours arrière
- Feuille solide 1 -> impact contre brush 1 (les données sont stockées dans iBrush)
- Retour au noeud C et parcours avant
- Test du noeud E1 -> parcours avant
- Feuille vide, retour

On constate qu'ainsi, l'algorithme a testé la brush (A, B, C, D) en parcourant chacun de ses plans, et que l'objet iBrush a transporté les données impact depuis le noeud de la collision jusqu'à la feuille solide.

Arrivé là, la brush a été impactée, il suffit de transférer les données iBruh dans l'objet impact et de le réinitialiser.
L'algorithme nous emmène ensuite dans une feuille vide. Ici pas de traitement, on réinitialise juste iBrush.

 
Sélectionnez
void getCollision(Shape* shape, BSP* bsp, Impact* impact, Impact* iBrush)
{

        (...)
    
        // GESTION DES FEUILLES
    
        // Feuille vide
        if (bsp->type == BSP_EMPTY_LEAF) {
                // Pas d'impact, on réinitialise iBrush
                iBrush->clearImpact();
                return;
        }

        // Feuille solide
        if (bsp->type == BSP_SOLID_LEAF) {
                // On transfère iBrush dans impact si plus près
                impact->setNearerImpact(iBrush->normal, iBrush->frac_impact, iBrush->frac_reelle);
                // On réinitialise iBrush
                iBrush->clearImpact();
                return;
        }
	
        (...)
	
}



Maintenant, selon l'architecture du BSP et les positions de la forme, il n'est pas garanti que le parcours d'une brush se fasse d'arrière en arrière tout à la suite. Ainsi, lorsque la forme traverse un plan, il nous faut parcourir les 2 côtés. Nous devons donc mémoriser l'état de iBrush et le restaurer après le premier parcours. C'est d'ailleurs, malheureusement, ce qui empêche l'algorithme d'être récursif terminal.

 
Sélectionnez
void getCollision(Shape* shape, BSP* bsp, Impact* impact, Impact* iBrush)
{
	// Fractions impact et réelle pour les collisions
	float fImpact;
	float fReelle;

	// Normale d'impact iBrush
	Vect3d* normalTemp;
	
	(...)
	
        // Collision seulement si la forme va de l'avant vers l'arrière
        // et si l'impact est plus près que celui déjà stocké
        if (d1 > d2 && fReelle < iBrush->frac_reelle) {
                
                //On calcule la fraction impact
                float d1i = d1 - MIN_DISTANCE - offset;
                float d2i = d2 - MIN_DISTANCE - offset;
                fImpact = d1i / (d1i - d2i);

                // On stocke l'impact
                iBrush->setImpact(bsp->plane->normal, fImpact, fReelle);
			
                // On mémorise la normale iBrush
                normalTemp = iBrush->normal;
        }
        // Sinon, on mémorise les paramètres iBrush
        else {
                normalTemp = iBrush->normal;
                fImpact = iBrush->frac_impact;
                fReelle = iBrush->frac_reelle;
        }
        
        // On parcourt l'espace arrière
        getCollision(shape, bsp->rear_child, impact, iBrush);

        // On restaure le iBrush à ce noeud
        iBrush->setImpact(normalTemp, fImpact, fReelle);

        // On parcourt l'espace avant
        getCollision(shape, bsp->front_child, impact, iBrush);

    (...)
	
}



Voila, Nous savons récupérer un résultat de collision sur un BSP. Récapitulons l'algorithme complet :

 
Sélectionnez
// Epaisseur des parois
#define MIN_DISTANCE 0.01F

// Récupère la plus proche collision de l'objet shape sur l'objet bsp 
// et la stocke dans l'objet impact
void getCollision(Shape* shape, BSP* bsp, Impact* impact, Impact* iBrush);


void getCollision(Shape* shape, BSP* bsp, Impact* impact, Impact* iBrush)
{
	// Fractions impact et réelle pour les collisions
	float fImpact;
	float fReelle;
	
	// Normale d'impact iBrush
	Vect3d* normalTemp;
	
	// GESTION DES FEUILLES
	
	// Feuille vide
	if (bsp->type == BSP_EMPTY_LEAF) {
			// Pas d'impact, on réinitialise iBrush
			iBrush->clearImpact();
			return;
	}
	
	// Feuille solide
	if (bsp->type == BSP_SOLID_LEAF) {
			// On transfère iBrush dans impact si plus près
			impact->setNearerImpact(iBrush->normal, iBrush->frac_impact, iBrush->frac_reelle);
			// On réinitialise iBrush
			iBrush->clearImpact();
			return;
	}
	
	// GESTION DES NOEUDS

	// On calcule les distances entre les 2 positions et le plan
	float d1 = bsp->plane->distance(impact->point_debut);
	float d2 = bsp->plane->distance(impact->point_fin);

	// On récupère l'offset selon le plan
	float offset = shape->getOffset(bsp->plane);

	// Forme toujours devant le noeud
	if (d1 > offset && d2 > offset) {
		// On parcourt l'espace avant
		getCollision(shape, bsp->front_child, impact, iBrush);
	}
	
	bsp->plane->invert();
	float offset2 = shape->getOffset(bsp->plane);
	bsp->plane->invert();

	// Forme toujours derrière le noeud
	else if (d1 < -offset2 && d2 < -offset2) {
		// On parcourt l'espace arrière
		getCollision(shape, bsp->rear_child, impact, iBrush);
	}

	// La forme traverse le noeud
	else {
		// On calcule la fraction réelle
		float d1r = d1 - offset;
		float d2r = d2 - offset;
		fReelle = d1r / (d1r - d2r);
		
		// Collision seulement si la forme va de l'avant vers l'arrière
		// et si l'impact est plus près que celui déjà stocké
		if (d1 > d2 && fReelle < iBrush->frac_reelle) {
				
				//On calcule la fraction impact
				float d1i = d1 - MIN_DISTANCE - offset;
				float d2i = d2 - MIN_DISTANCE - offset;
				fImpact = d1i / (d1i - d2i);
				
				// On stocke l'impact
				iBrush->setImpact(bsp->plane->normal, fImpact, fReelle);
                
				// On mémorise la normale iBrush
				normalTemp = iBrush->normal;
		}
		// Sinon, on mémorise les paramètres iBrush
		else {
				normalTemp = iBrush->normal;
				fImpact = iBrush->frac_impact;
				fReelle = iBrush->frac_reelle;
		}
		
		// On parcourt l'espace arrière
		getCollision(shape, bsp->rear_child, impact, iBrush);
		
		// On restaure le iBrush à ce noeud
		iBrush->setImpact(normalTemp, fImpact, fReelle);
		
		// On parcourt l'espace avant
		getCollision(shape, bsp->front_child, impact, iBrush);
	}

}

V. Algorithme de glissement



Le but de l'algorithme est de prendre un objet Shape, un objet Mover, un objet BSP, et de mettre à jour la nouvelle position de l'objet Shape. Il retourne s'il y a collision.

D'abord, un peu de théorie : Comment utiliser les données impact pour décrire un glissement ? Il s'agit d'une opération en 2 étapes :
- La fraction impact permet de calculer la nouvelle position de la forme le long de sa vélocité
- Le plan d'impact permet de calculer le trajet restant par projection de la vélocité de départ

correction velocite


Ainsi, l'algorithme est itératif : Tant que le trajet de la forme rencontre une collision, on avance la forme jusqu'à l'impact, on calcule le trajet restant, on le teste.
En voici l'ossature générale :

 
Sélectionnez
// Nombre maxi de recherches d'impact
#define MAX_IMPACT 5

// Glisse l'objet shape sur l'objet bsp selon le mouvement donné par l'objet mover
bool slide(Shape* shape, Mover* mover, BSP* bsp);


// Objets de récupération d'impact
static Impact* impact = new Impact();
static Impact* iBrush = new Impact();

// Positions début et fin de la forme
static Vect3d* pos1 = new Vect3d();
static Vect3d* pos2 = new Vect3d();

// Trajet de la forme jusqu'à l'impact
static Vect3d* move = new Vect3d();

// Arête entre deux murs
static Vect3d* edge = new Vect3d();

// Vélocité originale
static Vect3d* velocity = new Vect3d();

// Trajet restant après chaque itération
static Vect3d* trajet_restant = new Vect3d();


bool slide(Shape* shape, Mover* mover, BSP* bsp)
{
        int i, j;
        float dot;
        
        // Variable de retour, indique s'il a collision
        bool isCollision = false;
        
        // On stocke la position de la forme et le vecteur mouvement de départ
        pos1->assign(shape->getPosition());
        velocity->assign(mover->getMove());
        
        // On initialise le trajet restant après chaque itération
        trajet_restant>assign(mover->getMove());
        
        // Valeur représentant la fraction restante du mouvement de départ
        float frac = 1;
        
        
        for (int loops=0; loops < MAX_IMPACT; loops++) {
        
                // On calcule le point d'arrivée de la forme
                pos2->x = pos1->x + trajet_restant>x ;
                pos2->y = pos1->y + trajet_restant>y;
                pos2->z = pos1->z + trajet_restant>z;
            
                // Initialise les objets impact
                impact->reset(pos1, pos2);
                iBrush->reset(pos1, pos2);
            
                // Recherche d'impact sur le BSP
                getCollision(shape, bsp, impact, iBrush) 
            
                // Si impact, on l'indique et on continue
                if ( impact->isImpact() ) {
                        isCollision = true;
                }
                // Sinon, on assigne le point d'arrivée à la forme et on stoppe net
                else {
                        shape->getPosition()->assign(pos2);
                        return isCollision;
                }
                
                // On met à jour la fraction restante
                frac -= frac * impact->frac_impact;
            
                // On calcule le trajet jusqu'à l'impact
                move->x = impact->segment->x * impact->frac_impact;
                move->y = impact->segment->y * impact->frac_impact;
                move->z = impact->segment->z * impact->frac_impact;
                
                // On avance le point de départ jusqu'à l'impact
                pos1->x += move->x;
                pos1->y += move->y;
                pos1->z += move->z;
            
            
            
                // *****  ON CALCULE LE TRAJET RESTANT  ***** //
            
            
            
                // On raccourci le trajet restant selon la fraction de mouvement restante
                trajet_restant->x *= frac;
                trajet_restant->y *= frac;
                trajet_restant->z *= frac;
        }
        
        // Retourne le résultat de collision, 
        // Normalement, on n'atteint pas cette ligne
        return isCollision;
}



La valeur frac est importante : elle représente la fraction restante de la vélocité originale qu'il nous reste à parcourir. elle est initialisée à 1, ce qui signifie qu'il reste la totalité de la vélocité originale à traverser. A chaque itération, on raccourcit frac selon la fraction impact que l'on a récupéré.
Par exemple si à la première itération on a fraction_impact = 0.25, on a frac = 1 - (1 * 0.25) = 0.75.
Si à la deuxième itération on a fraction_impact = 0.5, on a frac = 0.75 - (0.75 * 0.5) = 0.375.
etc...

De plus, le vecteur trajet_restant est là pour stocker la vélocité originale corrigée par les normales à l'impact (typiquement perpendiculaire à la normale d'un mur, ou parallèle à l'arête entre 2 murs).

Ainsi, en gardant frac à jour d'une part, et en recalculant une nouvelle vélocité dans trajet_restant d'autre part, on définit à chaque boucle le nouveau vecteur à parcourir comme (trajet_restant * frac).

Maintenant, introduisons une autre notion importante : pour une gestion correcte, il nous faut prendre en compte le cas des collisions sur plusieurs plans, en particulier lorsque la forme est "coincée" entre 2 murs et glisse sur l'arête. Pour cela, nous devons ajouter un tableau de normales que nous remplirons au fil des itérations et dont la taille conditionnera le calcul du trajet restant.

 
Sélectionnez
(...)

// trajet_restant après chaque itération
Vect3d* trajet_restant = new Vect3d();

// Tableau des normales de collision
static Vect3d* normals[MAX_IMPACT];
static int normals_index = 0;


bool slide(Shape* shape, Mover* mover, BSP* bsp)
{
        (...)
    
        // Indique s'il a collision
        bool isCollision = false;

        normals_index = 0;

        (...)
    
        for (int loops=0; loops < MAX_IMPACT; loops++) {
    
                (...)

                // On stocke la nouvelle normale à l'impact
                normals[normals_index] = impact->normal;
                normals_index++;


                // *****  ON CALCULE LE TRAJET RESTANT  ***** //


                (...)

        }

        // Retourne le résultat de collision, 
        // Normalement, on n'atteint pas cette ligne
        return isCollision;
}



On ajoute ainsi successivement les normales des plans qui sont impliqués dans un même calcul de vélocité. Comment reconnaît-on ceux-ci ? par le fait qu'ils sont déjà "collés" à la forme, c'est-à-dire par la petitesse du mouvement qu'il faut pour atteindre l'impact.

correction velocite



Un moyen de gérer cela est d'ajouter les normales au tableau à chaque itération, mais de vider celui-ci si la distance forme-impact excède une certaine longueur. Nous allons donc définir cette longueur dans une nouvelle constante : MIN_MOVE.

 
Sélectionnez
// Nombre maxi de recherches d'impact
#define MAX_IMPACT 5

// Mouvement minimum
#define MIN_MOVE 0.02F

// Glisse l'objet shape sur l'objet bsp selon le mouvement donné par l'objet mover
bool slide(Shape* shape, Mover* mover, BSP* bsp);

(...)

bool slide(Shape* shape, Mover* mover, BSP* bsp)
{
        (...)

        for (int loops=0; loops < MAX_IMPACT; loops++) {
    
                (...)
                
                // Si la distance forme-impact est non négligeable, on remet les normales à 0
                if (move->norm() > MIN_MOVE) {
                        normals_index = 0;
                }
                
                // On stocke la nouvelle normale à l'impact
                normals[normals_index] = impact->normal;
                normals_index++;


                // *****  ON CALCULE LE TRAJET RESTANT  ***** //


                (...)
                
        }
        
        // Retourne le résultat de collision, 
        // Normalement, on n'atteint pas cette ligne
        return isCollision;
}



Nous avons maintenant toutes les infos pour recalculer le trajet restant à chaque itération. Pour cela, nous utiliserons un excellent code en 2 parties tiré des sources de Quake. Premièrement, une boucle de tests assure que chaque normale recueillie est "valide" par rapport aux autres.

 
Sélectionnez
bool slide(Shape* shape, Mover* mover, BSP* bsp)
{
        (...)

        for (int loops=0; loops < MAX_IMPACT; loops++) {
    
                (...)
                
                // *****  ON CALCULE LE TRAJET RESTANT  ***** //
                
                for (i=0; i<normals_index; i++) {
                
                        // On projette la vélocité sur le "mur" représenté par la normale, et on la stocke dans trajet_restant
                        dot = dotProduct(velocity, normals[i]);
                        trajet_restant->x = velocity->x - (normals[i]->x * dot);
                        trajet_restant->y = velocity->y - (normals[i]->y * dot);
                        trajet_restant->z = velocity->z - (normals[i]->z * dot);
                        
                        // Si une autre normale est "en face" de trajet_restant, on sort de cette boucle
                        for (j=0; j<normals_index; j++) {
                                if (j!=i)
                                        if (dotProduct(trajet_restant, normals[j]) < 0f)
                                                break;
                        }
                
                        // Si pas toutes les normales en face de ce trajet_restant, on sort
                        if (j == normals_index)
                                break;
                }

                (...)
                
        }
        
        // Retourne le résultat de collision, 
        // Normalement, on n'atteint pas cette ligne
        return isCollision;
}



Ce bout de code est plus subtil qu'il n'y paraît. Son but est donc de projeter la vélocité parallèlement à chaque "mur" tour à tour. Pour chaque projection, on regarde si toutes les normales sont "tournées" vers elle, c'est-à-dire si tous les autres murs ont une chance d'être traversée par elle. A la sortie de la boucle, on a 2 infos : vel_temp qui contient la dernière projection avant de sortir, et la valeur de i qui indique si le test est bon ou pas. Si (i==normals_index) le test est bon, toutes les normales peuvent être prises en compte pour calculer la nouvelle vélocité, sinon vel_temp contient déjà la nouvelle vélocité qui est la projection , on n'a rien à faire. Nous remarquons que c'est le cas en particulier lorsqu'il n'y a qu'une seule normale : vel_temp contient la projection sur celle-ci, et i est à 0 (pas 1), on ne fait plus rien.

La deuxième partie concerne donc le traitement lorsque (i==normals_index). Nous distinguerons 2 cas de figure :
- i = 2 : la forme traverse 2 murs, la vélocité suit "l'arête" formée par ceux-ci.
- i > 2 : la forme est coincée dans un coin, entre 3 murs, on stoppe net l'algorithme.

 
Sélectionnez
bool slide(Shape* shape, Mover* mover, BSP* bsp)
{
        (...)

        for (int loops=0; loops < MAX_IMPACT; loops++) {
    
                (...)
                
                // *****  ON CALCULE LE TRAJET RESTANT  ***** //
                
                for (i=0; i<normals_index; i++) {
                
                        // On projette la vélocité sur le "mur" représenté par la normale, et on la stocke dans trajet_restant
                        dot = dotProduct(velocity, normals[i]);
                        trajet_restant->x = velocity->x - (normals[i]->x * dot);
                        trajet_restant->y = velocity->y - (normals[i]->y * dot);
                        trajet_restant->z = velocity->z - (normals[i]->z * dot);
                        
                        // Si une autre normale est "en face" de trajet_restant, on sort de cette boucle
                        for (j=0; j<normals_index; j++) {
                                if (j!=i)
                                        if (dotProduct(trajet_restant, normals[j]) < 0f)
                                                break;
                        }
                
                        // Si pas toutes les normales en face de ce trajet_restant, on sort
                        if (j == normals_index)
                                break;
                }
                
                // Si toutes les normales peuvent être prises en compte pour la nouvelle vélocité
                if (i == normals_index) {
                
                        // 2 normales
                        if (normals_index == 2) {
                        
                                // On calcule l'arête entre les 2 murs
                                crossProduct(normals[0], normals[1], edge);
                                edge->normalize();
                                // On projette la vélocité dessus
                                dot = dotProduct(edge, velocity);
                                trajet_restant->x = edge->x * dot;
                                trajet_restant->y = edge->y * dot;
                                trajet_restant->z = edge->z * dot;
                        }
                        // 3 normales
                        else {
                                // On stoppe net
                                shape->getPosition()->assign(pos1);
                                return isCollision;
                        }
                }
                
                (...)
                
        }
        
        // Retourne le résultat de collision, 
        // Normalement, on n'atteint pas cette ligne
        return isCollision;
}



Voilà, nous savons gérer les glissements simples, les arêtes, et les coins. L'algorithme est presque complet, il ne nous reste plus qu'à rajouter deux petits tests:

- Le trajet restant ne doit pas "revenir sur les pas" de la vélocité originale.

- Pour éviter tout risque de traverser un mur, la longueur d'un mouvement ne doit pas être plus petite que notre MIN_DISTANCE (rappelez-vous, la distance minimale entre une forme et un mur), car cela peut provoquer des anomalies dans les coins. Pour éviter tout risque, on peut prendre comme critère notre MIN_MOVE, qui doit être plus grand que MIN_DISTANCE (2 fois plus grand, par exemple, évite absolument tout problème).

 
Sélectionnez
bool slide(Shape* shape, Mover* mover, BSP* bsp)
{
        (...)

        for (int loops=0; loops < MAX_IMPACT; loops++) {
    
                (...)
                
                // Si le trajet restant va "contre" la vélocité originale ou si sa longueur est trop petite
                if (dotProduct(velocity, trajet_restant) < 0f || trajet_restant.norm() < MIN_MOVE) {
                        // On stoppe net
                        shape->getPosition()->assign(pos1);
                        return isCollision;
                }
        }
        
        // Retourne le résultat de collision, 
        // Normalement, on n'atteint pas cette ligne
        return isCollision;
}



Voilà, notre algorithme est complet, récapitulons-le en entier :

 
Sélectionnez
// Nombre maxi de recherches d'impact
#define MAX_IMPACT 5

// Mouvement minimum
#define MIN_MOVE 0.02F

// Glisse l'objet shape sur l'objet bsp selon le mouvement donné par l'objet mover
bool slide(Shape* shape, Mover* mover, BSP* bsp);


// Objets de récupération d'impact
static Impact* impact = new Impact();
static Impact* iBrush = new Impact();

// Positions début et fin de la forme
static Vect3d* pos1 = new Vect3d();
static Vect3d* pos2 = new Vect3d();

// Trajet de la forme jusqu'à l'impact
static Vect3d* move = new Vect3d();

// Arête entre deux murs
static Vect3d* edge = new Vect3d();

// Vélocité originale
static Vect3d* velocity = new Vect3d();

// Trajet restant après chaque itération
static Vect3d* trajet_restant = new Vect3d();

// Tableau des normales de collision
static Vect3d* normals[MAX_IMPACT];
static int normals_index = 0;


bool slide(Shape* shape, Mover* mover, BSP* bsp)
{
        int i, j;
        float dot;
        
        // Indique s'il a collision
        bool isCollision = false;
        
        normals_index = 0;
        
        // On stocke la position de la forme et le vecteur mouvement de départ
        pos1->assign(shape->getPosition());
        velocity->assign(mover->getMove());
        
        // On initialise le trajet restant après chaque itération
        vel_temp->assign(mover->getMove());
        
        // Valeur représentant la fraction restante du mouvement de départ
        float frac = 1;
        
        
        for (int loops=0; loops < MAX_IMPACT; loops++) {
        
                // On calcule le point d'arrivée de la forme
                pos2->x = pos1->x + trajet_restant>x ;
                pos2->y = pos1->y + trajet_restant>y;
                pos2->z = pos1->z + trajet_restant>z;
            
                // Initialise les objets impact
                impact->reset(pos1, pos2);
                iBrush->reset(pos1, pos2);
            
                // Recherche d'impact sur le BSP
                getCollision(shape, bsp, impact, iBrush) 
            
                // Si impact, on l'indique et on continue
                if ( impact->isImpact() ) {
                        isCollision = true;
                }
                // Sinon, on assigne le point d'arrivée à la forme et on stoppe net
                else {
                        shape->getPosition()->assign(pos2);
                        return isCollision;
                }
                
                // On met à jour la fraction restante
                frac -= frac * impact->frac_impact;
            
                // On calcule le trajet jusqu'à l'impact
                move->x = impact->segment->x * impact->frac_impact;
                move->y = impact->segment->y * impact->frac_impact;
                move->z = impact->segment->z * impact->frac_impact;
                
                // Si la distance forme-impact est non négligeable, on remet les normales à 0
                if (move->norm() > MIN_MOVE) {
                        normals_index = 0;
                }
                
                // On stocke la nouvelle normale à l'impact
                normals[normals_index] = impact->normal;
                normals_index++;
            
            	// On avance le point de départ jusqu'à l'impact
                pos1->x += move->x;
                pos1->y += move->y;
                pos1->z += move->z;
            
                // *****  ON CALCULE LA NOUVELLE VELOCITE  ***** //
                
                for (i=0; i<normals_index; i++) {
                
                        // On projette la vélocité sur le "mur" représenté par la normale, et on la stocke dans trajet_restant
                        dot = dotProduct(velocity, normals[i]);
                        trajet_restant->x = velocity->x - (normals[i]->x * dot);
                        trajet_restant->y = velocity->y - (normals[i]->y * dot);
                        trajet_restant->z = velocity->z - (normals[i]->z * dot);
                        
                        // Si une autre normale est "en face" de trajet_restant, on sort de cette boucle
                        for (j=0; j<normals_index; j++) {
                                if (j!=i)
                                        if (dotProduct(trajet_restant, normals[j]) < 0f)
                                                break;
                        }
                
                        // Si pas toutes les normales en face de ce trajet_restant, on sort
                        if (j == normals_index)
                                break;
                }
                
                // Si toutes les normales peuvent être prises en compte pour la nouvelle vélocité
                if (i == normals_index) {
                
                        // 2 normales
                        if (normals_index == 2) {
                        
                                // On calcule l'arête entre les 2 murs
                                crossProduct(normals[0], normals[1], edge);
                                edge->normalize();
                                // On projette la vélocité dessus
                                dot = dotProduct(edge, velocity);
                                trajet_restant->x = edge->x * dot;
                                trajet_restant->y = edge->y * dot;
                                trajet_restant->z = edge->z * dot;
                        }
                        // 3 normales
                        else {
                                // On stoppe net
                                shape->getPosition()->assign(pos1);
                                return isCollision;
                        }
                }
            
            
                // On raccourci le trajet restant selon la fraction de mouvement restante
                trajet_restant->x *= frac;
                trajet_restant->y *= frac;
                trajet_restant->z *= frac;
                
                // Si le trajet restant va "contre" la vélocité originale ou si sa longueur est trop petite
                if (dotProduct(velocity, trajet_restant) < 0f || trajet_restant.norm() < MIN_MOVE) {
                        // On stoppe net
                        shape->getPosition()->assign(pos1);
                        return isCollision;
                }
        }
        
        // Retourne le résultat de collision, 
        // Normalement, on n'atteint pas cette ligne
        return isCollision;
}

VI. Conclusion

Les algorithmes que nous avons présentés ne sont pas les seuls possibles, et sont eux-même modifiables selon les besoins. Cependant le clivage recherche de collision - traitement de trajectoire est incontournable dans ce type de système. D'ailleurs, un aspect intéressant est l'indépendance mutuelle entre les 2 notions. Une recherche de collision peut servir à toutes sortes de comportements autres que le glissement (y-compris n'ayant rien à voir avec la physique, comme les tests de visibilité). A l'inverse, l'algorithme de slide, pour peu qu'il y ait une fonction qui récupère une fraction d'impact et une normale, permet de "glisser" sur n'importe quelle structure !

Vous avez aimé ce tutoriel ? Alors partagez-le en cliquant sur les boutons suivants : Viadeo Twitter Facebook Share on Google+