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.
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.
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.
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é".
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.
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é.
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.
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.
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.
// 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.
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.
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.
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
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 :
// 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 :
// 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 :
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.
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.
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 :
// 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
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 :
// 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.
(...)
// 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.
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.
// 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.
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.
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).
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 :
// 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 !