<< Postface

Table des matières

Réponses aux exercices >>

Chapitre A

Tests géométriques

Le Chapitre 9 a discuté d’un certain nombre de calculs qui peuvent être effectués sur une seule primitive. Ici, nous présentons un certain nombre de calculs utiles qui opèrent sur plus d’une primitive. Cette annexe est une collection de divers calculs géométriques qui sont parfois utiles. Il est également instructif de parcourir ces tests, car beaucoup illustrent des principes généraux.

Une liste plus complète de méthodes d’intersection rapides peut être trouvée sur http://www.realtimerendering.com/intersections.html.

A.1Point le plus proche sur une droite implicite en 2D

Considérons une droite infinie $L$ en 2D définie implicitement par tous les points $\mathbf{p}$ tels que

$$\mathbf{p} \cdot \hat{\mathbf{n}} = d,$$

où $\hat{\mathbf{n}}$ est un vecteur unitaire. Notre objectif est de trouver, pour n’importe quel point $\mathbf{q}$, le point $\mathbf{q}^{\prime}$ qui est le point le plus proche de $\mathbf{q}$ sur $L$. C’est le résultat de la projection de $\mathbf{q}$ sur $L$. Traçons une deuxième droite $M$ passant par $\mathbf{q}$, parallèle à $L$, comme montré dans la Figure A.1.

Figure A.1 Trouver le point le plus proche sur une droite implicite en 2D

Soient ${\hat{\mathbf{n}}}_{M}$ et $d_{M}$ la normale et la valeur de $d$ respectivement de l’équation de droite pour $M$ ; puisque $L$ et $M$ sont parallèles, elles ont la même normale : ${\hat{\mathbf{n}}}_{M} = \hat{\mathbf{n}}$. Puisque $\mathbf{q}$ est sur $M$, $d_{M}$ peut être calculé comme $\mathbf{q} \cdot \hat{\mathbf{n}}$.

La distance signée de $M$ à $L$ mesurée parallèlement à $\hat{\mathbf{n}}$ est simplement

$$d - d_{M} = d - \mathbf{q} \cdot \hat{\mathbf{n}}.$$

Cette distance est évidemment la même que la distance de $\mathbf{q}$ à $\mathbf{q}^{\prime}$. (Si on a besoin uniquement de la distance et non de la valeur de $\mathbf{q}^{\prime}$, on peut s’arrêter ici.) Pour calculer la valeur de $\mathbf{q}^{\prime}$, on peut simplement prendre $\mathbf{q}$ et le déplacer d’un multiple de $\hat{\mathbf{n}}$ :

Calcul du point le plus proche sur une droite implicite en 2D

$$\begin{matrix} {\mathbf{q}^{\prime} = \mathbf{q} + (d - \mathbf{q} \cdot \hat{\mathbf{n}})\hat{\mathbf{n}}.} \\ \end{matrix}$$

A.2Point le plus proche sur un rayon paramétrique

Considérons le rayon paramétrique $R$ en 2D ou 3D défini par

$$\mathbf{p}(t) = \mathbf{p}_{org} + t\hat{\mathbf{d}},$$

Figure A.2 Trouver le point le plus proche sur un rayon

où $\hat{\mathbf{d}}$ est un vecteur unitaire, et le paramètre $t$ varie de 0 à $l$, où $l$ est la longueur de $R$. Pour un point donné $\mathbf{q}$, on souhaite trouver le point $\mathbf{q}^{\prime}$ sur $R$ qui est le plus proche de $\mathbf{q}$.

Il s’agit simplement de projeter un vecteur sur un autre, ce qui a été présenté dans la Section 2.11.2. Soit $\mathbf{v}$ le vecteur de $\mathbf{p}_{org}$ à $\mathbf{q}$. On souhaite calculer le résultat de la projection de $\mathbf{v}$ sur $\hat{\mathbf{d}}$—en d’autres termes, la composante de $\mathbf{q}$ parallèle à $\hat{\mathbf{d}}$. Ceci est illustré dans la Figure A.2.

La valeur du produit scalaire $\mathbf{v} \cdot \hat{\mathbf{d}}$ est la valeur $t$ telle que $\mathbf{p}(t) = \mathbf{q}^{\prime}$ :

Calcul du point le plus proche sur un rayon paramétrique

$$\begin{matrix} t & {= \hat{\mathbf{d}} \cdot \mathbf{v} = \hat{\mathbf{d}} \cdot (\mathbf{q} - \mathbf{p}_{org}),} \\ \mathbf{q}^{\prime} & {= \mathbf{p}(t) = \mathbf{p}_{org} + t\hat{\mathbf{d}} = \mathbf{p}_{org} + (\hat{\mathbf{d}} \cdot (\mathbf{q} - \mathbf{p}_{org}))\hat{\mathbf{d}}.} \\ \end{matrix}$$

En fait, l’Équation (A.2), pour $\mathbf{p}(t)$ calcule le point le plus proche de $\mathbf{q}$ sur la droite infinie contenant $R$. Si $t < 0$ ou $t > l$, alors $\mathbf{p}(t)$ n’est pas dans le rayon $R$, auquel cas le point le plus proche de $\mathbf{q}$ sur $R$ sera l’origine du rayon (si $t < 0$) ou l’extrémité (si $t > l$).

Si le rayon est défini où $t$ varie de 0 à 1 et où $\mathbf{d}$ n’est pas nécessairement un vecteur unitaire, alors on doit diviser par la magnitude de $\mathbf{d}$ pour calculer la valeur de $t$ :

$$t = \frac{\mathbf{d} \cdot (\mathbf{q} - \mathbf{p}_{org})}{\parallel \mathbf{d} \parallel}.$$

A.3Point le plus proche sur un plan

Considérons un plan $P$ défini de façon implicite standard comme tous les points $\mathbf{p}$ satisfaisant

$$\mathbf{p} \cdot \hat{\mathbf{n}} = d,$$

où $\hat{\mathbf{n}}$ est un vecteur unitaire. Étant donné un point $\mathbf{q}$, on souhaite trouver le point $\mathbf{q}^{\prime}$, qui est le résultat de la projection de $\mathbf{q}$ sur $P$. Le point $\mathbf{q}^{\prime}$ est le point le plus proche de $\mathbf{q}$ sur $P$.

On a montré comment calculer la distance d’un point à un plan dans la Section 9.5.4. Pour calculer $\mathbf{q}^{\prime}$, on déplace simplement $\mathbf{q}$ de cette distance, parallèlement à $\hat{\mathbf{n}}$.

Calcul du point le plus proche sur un plan

$$\mathbf{q}^{\prime} = \mathbf{q} + (d - \mathbf{q} \cdot \hat{\mathbf{n}})\hat{\mathbf{n}}$$

Notez que c’est la même chose que l’ Équation (A.1), qui calcule le point le plus proche d’une droite implicite en 2D.

A.4Point le plus proche sur un cercle ou une sphère

Figure A.3 Trouver le point le plus proche sur un cercle

Imaginons un point 2D $\mathbf{q}$ et un cercle de centre $\mathbf{c}$ et de rayon $r$. (La discussion suivante s’applique aussi à une sphère en 3D.) On souhaite trouver $\mathbf{q}^{\prime}$, qui est le point le plus proche du cercle à $\mathbf{q}$.

Soit $\mathbf{d}$ le vecteur de $\mathbf{q}$ à $\mathbf{c}$. Ce vecteur coupe le cercle en $\mathbf{q}^{\prime}$. Soit $\mathbf{b}$ le vecteur de $\mathbf{q}$ à $\mathbf{q}^{\prime}$, comme montré dans la Figure A.3.

Or, clairement, ${\parallel \mathbf{b} \parallel} = {\parallel \mathbf{d} \parallel} - r$. Donc,

$$\mathbf{b} = \frac{{\parallel \mathbf{d} \parallel} - r}{\parallel \mathbf{d} \parallel}\mathbf{d}.$$

En ajoutant ce déplacement à $\mathbf{q}$ pour projeter sur le cercle, on obtient

Calcul du point le plus proche sur un cercle ou une sphère

$$\begin{matrix} \mathbf{q}^{\prime} & {= \mathbf{q} + \mathbf{b}} \\ & {= \mathbf{q} + \frac{{\parallel \mathbf{d} \parallel} - r}{\parallel \mathbf{d} \parallel}\mathbf{d}.} \\ \end{matrix}$$

Si ${\parallel \mathbf{d} \parallel} < r$, alors $\mathbf{q}$ est à l’intérieur du cercle. Que faire dans cette situation ? Devrait-on avoir $\mathbf{q}^{\prime} = \mathbf{q}$, ou devrait-on projeter $\mathbf{q}$ vers l’extérieur sur la surface du cercle ? Certaines circonstances particulières peuvent nécessiter l’un ou l’autre comportement. Si on décide de projeter les points sur la surface du cercle, on sera forcé de prendre une décision arbitraire sur quoi faire dans le cas dégénéré où $\mathbf{q} = \mathbf{c}$.

A.5Point le plus proche dans un AABB

Soit $B$ une boîte englobante alignée sur les axes (AABB) définie par les points extrêmes $\mathbf{p}_{min}$ et $\mathbf{p}_{max}$. Pour n’importe quel point $\mathbf{q}$, on peut facilement calculer $\mathbf{q}^{\prime}$, le point le plus proche dans $B$ à $\mathbf{q}$. Cela se fait en “poussant” $\mathbf{q}$ dans $B$ le long de chaque axe, comme illustré dans le Listing A.1. Notez que si le point est déjà à l’intérieur de la boîte, ce code retourne le point original.

if (x < minX) {
    x = minX;
} else if (x > maxX) {
    x = maxX;
}

if (y < minY) {
    y = minY;
} else if (y > maxY) {
    y = maxY;
}

if (z < minZ) {
    z = minZ;
} else if (z > maxZ) {
    z = maxZ;
}

A.6Tests d’intersection

Les sections restantes de ce chapitre présentent un assortiment de tests d’intersection. Ces tests sont conçus pour déterminer si deux primitives géométriques se croisent, et (dans certains cas) pour localiser l’intersection. On va considérer deux types différents de tests d’intersection : statiques et dynamiques.

• Un test statique vérifie deux primitives immobiles et détecte si les deux primitives se croisent. C’est un test booléen—c’est-à-dire qu’il retourne généralement seulement vrai (il y a une intersection) ou faux (il n’y a pas d’intersection). Si le test retourne plus de détails sur l’ intersection, cette information supplémentaire a généralement pour but de décrire où l’intersection s’est produite.

• Un test dynamique vérifie deux primitives en mouvement et détecte si et quand deux primitives se croisent. Généralement, le mouvement est exprimé paramétriquement, et donc le résultat d’un tel test n’est pas seulement un résultat booléen vrai/faux mais aussi une valeur temporelle (la valeur du paramètre $t$) qui indique quand les primitives se croisent. Pour les tests qu’on considère ici, la valeur de mouvement est un simple déplacement linéaire—un décalage vectoriel par lequel la primitive se déplace lorsque $t$ varie de 0 à 1.
  Bien que chaque objet puisse avoir son propre déplacement sur l’intervalle de temps considéré, il sera souvent plus facile de voir le problème du point de vue de l’une des primitives, en considérant que cette primitive est “immobile” tandis que l’autre primitive fait tout le “mouvement”. On peut facilement faire cela en combinant les deux vecteurs de déplacement pour obtenir un seul vecteur de déplacement relatif qui décrit comment les deux primitives bougent l’une par rapport à l’autre. Ainsi, les tests dynamiques impliqueront généralement une primitive immobile et une primitive mobile.
  Notez que de nombreux tests importants impliquant des rayons sont en réalité des tests dynamiques, puisqu’un rayon peut être vu comme un point en mouvement.

A.7Intersection de deux droites implicites en 2D

Trouver l’intersection de deux droites définies implicitement en 2D est une simple résolution d’un système d’équations linéaires. On a deux équations (les deux équations implicites des droites) et deux inconnues (les coordonnées $x$ et $y$ du point d’intersection). Nos deux équations sont

$$\begin{matrix} {a_{1}x + b_{1}y} & {= d_{1},} \\ {a_{2}x + b_{2}y} & {= d_{2}.} \\ \end{matrix}$$

La résolution de ce système d’équations donne

Calcul de l’intersection de deux droites en 2D

$$\begin{matrix} \begin{matrix} x & {= \frac{b_{2}d_{1} - b_{1}d_{2}}{a_{1}b_{2} - a_{2}b_{1}},} \\ y & {= \frac{a_{1}d_{2} - a_{2}d_{1}}{a_{1}b_{2} - a_{2}b_{1}}.} \\ \end{matrix} \\ \end{matrix}$$

Comme pour tout système d’équations linéaires, il y a trois possibilités de solution (illustrées dans la Figure A.4) :

• Il y a une solution. Dans ce cas, les dénominateurs dans l’ Équation (A.3) seront non nuls.

• Il n’y a pas de solution. Cela indique que les droites sont parallèles et ne se croisent pas. Les dénominateurs sont nuls.

• Il y a un nombre infini de solutions. C’est le cas quand les deux droites sont confondues. Tous les numérateurs et dénominateurs sont nuls dans ce cas.

Figure A.4Intersection de deux droites en 2D—les trois cas

A.8Intersection de deux rayons en 3D

Étant donné deux rayons en 3D définis paramétriquement par

$$\begin{matrix} {\mathbf{r}_{1}(t_{1})} & {= \mathbf{p}_{1} + t_{1}\mathbf{d}_{1},} \\ {\mathbf{r}_{2}(t_{2})} & {= \mathbf{p}_{2} + t_{2}\mathbf{d}_{2},} \\ \end{matrix}$$

on peut résoudre pour leur point d’intersection. Pour l’instant, ne restreignons pas l’intervalle de $t_{1}$ et $t_{2}$ ; donc, on considère les droites infinies qui contiennent les rayons. Les vecteurs delta $\mathbf{d}_{1}$ et $\mathbf{d}_{2}$ n’ont pas nécessairement besoin d’être des vecteurs unitaires. Si les rayons se trouvent dans un plan, on a les mêmes trois cas possibles que dans la section précédente :

• Les rayons se croisent en exactement un point.

• Les rayons sont parallèles, et il n’y a pas d’intersection.

• Les rayons sont confondus, et il y a un nombre infini de solutions.

Cependant, en 3D on a un quatrième cas, où les rayons sont gauches et ne partagent pas de plan commun. Un exemple de droites gauches est illustré dans la Figure A.5.

Figure A.5Les droites gauches en 3D ne partagent pas de plan commun et ne se croisent pas.

On peut résoudre pour $t_{1}$ et $t_{2}$. Au point d’intersection,

$$\begin{matrix} {\mathbf{r}_{1}(t_{1})} & {= \mathbf{r}_{2}(t_{2}),} \\ {\mathbf{p}_{1} + t_{1}\mathbf{d}_{1}} & {= \mathbf{p}_{2} + t_{2}\mathbf{d}_{2},} \\ {t_{1}\mathbf{d}_{1}} & {= \mathbf{p}_{2} + t_{2}\mathbf{d}_{2} - \mathbf{p}_{1},} \\ {(t_{1}\mathbf{d}_{1}) \times \mathbf{d}_{2}} & {= (\mathbf{p}_{2} + t_{2}\mathbf{d}_{2} - \mathbf{p}_{1}) \times \mathbf{d}_{2},} \\ {t_{1}(\mathbf{d}_{1} \times \mathbf{d}_{2})} & {= (t_{2}\mathbf{d}_{2}) \times \mathbf{d}_{2} + (\mathbf{p}_{2} - \mathbf{p}_{1}) \times \mathbf{d}_{2},} \\ {t_{1}(\mathbf{d}_{1} \times \mathbf{d}_{2})} & {= t_{2}(\mathbf{d}_{2} \times \mathbf{d}_{2}) + (\mathbf{p}_{2} - \mathbf{p}_{1}) \times \mathbf{d}_{2},} \\ {t_{1}(\mathbf{d}_{1} \times \mathbf{d}_{2})} & {= t_{2}0 + (\mathbf{p}_{2} - \mathbf{p}_{1}) \times \mathbf{d}_{2},} \\ {t_{1}(\mathbf{d}_{1} \times \mathbf{d}_{2})} & {= (\mathbf{p}_{2} - \mathbf{p}_{1}) \times \mathbf{d}_{2},} \\ {t_{1}(\mathbf{d}_{1} \times \mathbf{d}_{2}) \cdot (\mathbf{d}_{1} \times \mathbf{d}_{2})} & {= \left( (\mathbf{p}_{2} - \mathbf{p}_{1}) \times \mathbf{d}_{2} \right) \cdot (\mathbf{d}_{1} \times \mathbf{d}_{2}),} \\ t_{1} & {= \frac{\left( (\mathbf{p}_{2} - \mathbf{p}_{1}) \times \mathbf{d}_{2} \right) \cdot (\mathbf{d}_{1} \times \mathbf{d}_{2})}{{\parallel {\mathbf{d}_{1} \times \mathbf{d}_{2}} \parallel}^{2}}.} \\ \end{matrix}$$

On obtient $t_{2}$ de façon similaire :

$$t_{2} = \frac{\left( (\mathbf{p}_{2} - \mathbf{p}_{1}) \times \mathbf{d}_{1} \right) \cdot (\mathbf{d}_{1} \times \mathbf{d}_{2})}{{\parallel {\mathbf{d}_{1} \times \mathbf{d}_{2}} \parallel}^{2}}.$$

Si les droites sont parallèles (ou confondues), alors le produit vectoriel de $\mathbf{d}_{1}$ et $\mathbf{d}_{2}$ est le vecteur nul, et donc le dénominateur des deux équations est nul. Si les droites sont gauches, alors $\mathbf{r}_{1}(t_{1})$ et $\mathbf{r}_{2}(t_{2})$ sont les points d’approche la plus proche. Pour distinguer entre les droites gauches et sécantes, on examine la distance entre $\mathbf{r}_{1}(t_{1})$ et $\mathbf{r}_{2}(t_{2})$. Bien sûr, en pratique, une intersection exacte se produit rarement en raison de l’imprécision en virgule flottante, et donc une tolérance doit être utilisée.

Cette discussion suppose que l’intervalle des paramètres $t_{1}$ et $t_{2}$ n’était pas restreint. Si les rayons ont une longueur finie (ou s’étendent dans une seule direction), alors, bien sûr, les tests de limites appropriés seraient appliqués après le calcul de $t_{1}$ et $t_{2}$.

A.9Intersection d’un rayon et d’un plan

Un rayon coupe un plan en 3D en un point. Soit le rayon défini paramétriquement par

$$\mathbf{p}(t) = \mathbf{p}_{0} + t\mathbf{d}.$$

Le plan sera défini de façon implicite standard, par tous les points $\mathbf{p}$ tels que

$$\mathbf{p} \cdot \mathbf{n} = d.$$

Bien qu’on restreigne souvent la normale de plan $\mathbf{n}$ et le vecteur direction du rayon $\mathbf{d}$ à être des vecteurs unitaires, dans ce cas aucune restriction n’est nécessaire.

Figure A.6 Intersection d’un rayon et d’un plan en 3D

Résolvons pour $t$ au point d’intersection, en supposant un rayon infini pour l’instant :

Intersection paramétrique d’un rayon et d’un plan

$$\begin{matrix} {(\mathbf{p}_{0} + t\mathbf{d}) \cdot \mathbf{n}} & {= d,} \\ {\mathbf{p}_{0} \cdot \mathbf{n} + t\mathbf{d} \cdot \mathbf{n}} & {= d,} \\ {t\mathbf{d} \cdot \mathbf{n}} & {= d - \mathbf{p}_{0} \cdot \mathbf{n},} \\ t & {= \frac{d - \mathbf{p}_{0} \cdot \mathbf{n}}{\mathbf{d} \cdot \mathbf{n}}.} \\ \end{matrix}$$

Si le rayon est parallèle au plan, alors le dénominateur $\mathbf{d} \cdot \mathbf{n}$ est nul et il n’y a pas d’intersection. Si la valeur de $t$ est hors de l’intervalle, alors le rayon ne coupe pas le plan. On peut aussi souhaiter couper seulement le côté avant du plan. Dans ce cas, on dit qu’il y a une intersection seulement si le rayon pointe dans une direction opposée à la normale du plan (c’est-à-dire, $\mathbf{d} \cdot \mathbf{n} < 0$).

A.10Intersection d’un AABB et d’un plan

Considérons une boîte englobante alignée sur les axes 3D définie par les points extrêmes $\mathbf{p}_{min}$ et $\mathbf{p}_{max}$, et un plan défini de façon implicite standard par tous les points $\mathbf{p}$ satisfaisant

$$\mathbf{p} \cdot \mathbf{n} = d,$$

où $\mathbf{n}$ n’est pas nécessairement un vecteur unitaire. Le plan doit être exprimé dans le même espace de coordonnées que l’AABB.

Une stratégie d’implémentation évidente pour un test statique serait de classer chaque point de coin comme étant d’un côté ou de l’autre du plan. On fait cela en calculant les produits scalaires des points de coin avec $\mathbf{n}$ et en comparant ces produits scalaires avec $d$. Si tous les produits scalaires sont supérieurs à $d$, alors la boîte est complètement du côté avant du plan. Si tous les produits scalaires sont inférieurs à $d$, alors la boîte est complètement du côté arrière du plan.

Il s’avère qu’on n’a pas à vérifier les huit points de coin. On va utiliser une astuce similaire à celle utilisée dans la Section 9.4.4 pour transformer un AABB. Par exemple, si $n_{x} > 0$, alors le coin avec le produit scalaire minimal a $x = x_{min}$ et le coin avec le produit scalaire maximal a $x = x_{max}$. Si $n_{x} < 0$, alors c’est le contraire. Des déclarations similaires s’appliquent à $n_{y}$ et $n_{z}$. On calcule les valeurs minimale et maximale du produit scalaire. Si la valeur minimale du produit scalaire est supérieure à $d$, ou si le produit scalaire maximal est inférieur à $d$, alors il n’y a pas d’intersection. Sinon, deux coins ont été trouvés qui sont des côtés opposés du plan, et donc une intersection est détectée. Cette stratégie est implémentée dans le Listing A.2.

// Perform static AABB-plane intersection test.  Returns:
//
// <0   Box is completely on the BACK side of the plane
// >0   Box is completely on the FRONT side of the plane
// 0    Box intersects the plane
int AABB3::classifyPlane(const Vector3 &n, float d) const {

    // Inspect the normal and compute the minimum and maximum
    // D values.
    float minD, maxD;

    if (n.x > 0.0f) {
        minD = n.x*min.x; maxD = n.x*max.x;
    } else {
        minD = n.x*max.x; maxD = n.x*min.x;
    }

    if (n.y > 0.0f) {
        minD += n.y*min.y; maxD += n.y*max.y;
    } else {
        minD += n.y*max.y; maxD += n.y*min.y;
    }

    if (n.z > 0.0f) {
        minD += n.z*min.z; maxD += n.z*max.z;
    } else {
        minD += n.z*max.z; maxD += n.z*min.z;
    }

    // Check if completely on the front side of the plane
    if (minD >= d) {
        return +1;
    }

    // Check if completely on the back side of the plane
    if (maxD <= d) {
        return -1;
    }

    // We straddle the plane
    return 0;
}

Un test dynamique n’est qu’une étape de plus. Considérons le plan comme immobile (rappelons que selon la Section A.6 il est plus simple de voir le test du cadre de référence de l’un des objets en mouvement). Le déplacement de la boîte sera défini par un vecteur unitaire $\mathbf{d}$ et une longueur $l$. Comme précédemment, on localise d’abord les coins avec les produits scalaires minimum et maximum et on vérifie une intersection à $t = 0$. Si la boîte ne coupe pas initialement le plan, alors elle doit d’abord frapper le plan au point de coin le plus proche du plan. Ce sera l’un des deux points de coin identifiés dans la première étape. Si on s’intéresse seulement à la collision avec le “côté avant” du plan, on peut toujours utiliser le coin avec la valeur minimale du produit scalaire. Une fois qu’on a déterminé quel coin frappera le plan, on utilise le test d’intersection rayon-plan de la Section A.9.

A.11Intersection de trois plans

En 3D, trois plans se croisent en un point, comme montré dans la Figure A.7.

Figure A.7 Trois plans se croisent en un point en 3D

Soient les trois plans définis implicitement comme

$$\begin{matrix} {\mathbf{p} \cdot \mathbf{n}_{1}} & {= d_{1},} & {\mathbf{p} \cdot \mathbf{n}_{2}} & {= d_{2},} & {\mathbf{p} \cdot \mathbf{n}_{3}} & {= d_{3}.} \\ \end{matrix}$$

Bien qu’on utilise généralement des vecteurs unitaires pour les normales de plan, dans ce cas il n’est pas nécessaire que $\mathbf{n}_{i}$ soit de longueur unitaire. Ces trois équations de plan nous donnent un système d’équations linéaires avec trois équations et trois inconnues (les coordonnées $x$, $y$ et $z$ du point d’intersection). La résolution de ce système d’équations donne le résultat suivant, selon Goldman [4] :

Trois plans se croisent en un point

$$\mathbf{p} = \frac{d_{1}(\mathbf{n}_{2} \times \mathbf{n}_{3}) + d_{2}(\mathbf{n}_{3} \times \mathbf{n}_{1}) + d_{3}(\mathbf{n}_{1} \times \mathbf{n}_{2})}{(\mathbf{n}_{1} \times \mathbf{n}_{2}) \cdot \mathbf{n}_{3}}.$$

Si une paire de plans est parallèle, alors le point d’intersection soit n’existe pas, soit n’est pas unique. Dans l’un ou l’autre cas, le produit triple dans le dénominateur est nul.

A.12Intersection d’un rayon et d’un cercle ou d’une sphère

Cette section explique comment calculer l’intersection d’un rayon et d’un cercle en 2D. Cela fonctionne aussi pour calculer l’intersection d’un rayon et d’une sphère en 3D, puisqu’on peut opérer dans le plan qui contient le rayon et le centre du cercle et transformer le problème 3D en un problème 2D. (Si le rayon se trouve sur une droite qui passe par le centre de la sphère, le plan n’est pas défini de façon unique. Ce n’est pas un problème, cependant, car n’importe lequel des infiniment nombreux plans qui passent par le rayon et le centre de la sphère peut être utilisé.)

Figure A.8 Intersection d’un rayon et d’une sphère

On va utiliser une construction inspirée de Hultquist [5] ; voir la Figure A.8. La sphère est définie par son centre $\mathbf{c}$ et son rayon $r$, et le rayon est défini par

$$\mathbf{p}(t) = \mathbf{p}_{0} + t\hat{\mathbf{d}}.$$

Dans ce cas, on utilise un vecteur unitaire $\hat{\mathbf{d}}$ et on fait varier $t$ de 0 à $l$, où $l$ est la longueur du rayon.

On résout pour la valeur de $t$ au point d’intersection. Clairement, $t = a - f$. On peut calculer $a$ comme suit. Soit $\mathbf{e}$ le vecteur de $\mathbf{p}_{0}$ à $\mathbf{c}$ :

$$\mathbf{e} = \mathbf{c} - \mathbf{p}_{0}.$$

On projette maintenant $\mathbf{e}$ sur $\hat{\mathbf{d}}$ (voir la Section 2.11.2). La longueur de ce vecteur est $a$, et peut être calculée par

$$a = \mathbf{e} \cdot \hat{\mathbf{d}}.$$

Il reste à calculer $f$. Premièrement, par le théorème de Pythagore, on voit clairement que

$$f^{2} + b^{2} = r^{2}.$$

On peut résoudre pour $b^{2}$ en utilisant le théorème de Pythagore sur le plus grand triangle :

$$\begin{matrix} {a^{2} + b^{2}} & {= e^{2},} \\ b^{2} & {= e^{2} - a^{2},} \\ \end{matrix}$$

où $e$ est la distance de l’origine du rayon au centre, c’est-à-dire la longueur du vecteur $\mathbf{e}$. Ainsi, $e^{2}$ peut être calculé par

$$e^{2} = \mathbf{e} \cdot \mathbf{e}.$$

En substituant et en résolvant pour $f$, on obtient

$$\begin{matrix} {f^{2} + b^{2}} & {= r^{2},} \\ {f^{2} + (e^{2} - a^{2})} & {= r^{2},} \\ f^{2} & {= r^{2} - e^{2} + a^{2},} \\ f & {= \sqrt{r^{2} - e^{2} + a^{2}}.} \\ \end{matrix}$$

Finalement, en résolvant pour $t$, on a

Intersection paramétrique d’un rayon et d’un cercle ou d’une sphère

$$\begin{matrix} t & {= a - f} \\ & {= a - \sqrt{r^{2} - e^{2} + a^{2}}.} \\ \end{matrix}$$

Si l’argument de la racine carrée ($r^{2} - e^{2} + a^{2}$) est négatif, alors le rayon ne coupe pas la sphère.

L’origine du rayon pourrait être à l’intérieur de la sphère. Ceci est indiqué par $e^{2} < r^{2}$. Le comportement approprié dans ce cas dépendrait de l’objectif du test.

A.13Intersection de deux cercles ou sphères

Figure A.9Intersection de deux sphères

Détecter l’intersection statique de deux sphères est relativement facile. (La discussion de cette section s’applique aussi aux cercles—en fait, on utilise des cercles dans les diagrammes.) Considérons deux sphères définies par leurs centres $\mathbf{c}_{1}$ et $\mathbf{c}_{2}$ et leurs rayons $r_{1}$ et $r_{2}$, comme montré dans la Figure A.9. Soit $d$ la distance entre leurs centres. Clairement, les sphères se croisent si $d < r_{1} + r_{2}$. En pratique, on peut éviter la racine carrée dans le calcul de $d$ en vérifiant que $d^{2} < (r_{1} + r_{2})^{2}$.

Détecter l’intersection de deux sphères en mouvement est légèrement plus difficile. Supposons, pour l’instant, qu’on a deux vecteurs de déplacement séparés $d_{1}$ et $d_{2}$, un pour chaque sphère, qui décrivent comment les sphères vont bouger pendant la période de temps considérée. Ceci est montré dans la Figure A.10.

Figure A.10 Deux sphères en mouvement

On peut simplifier le problème en le voyant du point de vue de la première sphère, en considérant cette sphère comme “immobile” tandis que l’autre sphère est la sphère “en mouvement”. Cela nous donne un seul vecteur de déplacement $\mathbf{d}$, calculé comme la différence des deux vecteurs de mouvement $\mathbf{d}_{2} - \mathbf{d}_{1}$. Ceci est illustré dans la Figure A.11.

Figure A.11 Combinaison des vecteurs de déplacement pour qu’une sphère soit considérée immobile

Soit la sphère immobile définie par son centre $\mathbf{c}_{s}$ et son rayon $r_{s}$. Le rayon de la sphère en mouvement est $r_{m}$. Le centre de la sphère en mouvement est $\mathbf{c}_{m}$ à $t = 0$. Plutôt que de faire varier t de 0 à 1 comme décrit précédemment, on normalise $\hat{\mathbf{d}}$ et on fait varier $t$ de 0 à $l$, où $l$ est la longueur du déplacement relatif total. Donc la position du centre de la sphère en mouvement au temps $t$ est donnée par $\mathbf{c}_{m} + t\hat{\mathbf{d}}$. Notre objectif est de trouver $t$, le temps auquel la sphère en mouvement touche la sphère immobile. La géométrie impliquée est illustrée dans la Figure A.12.

Figure A.12Intersection dynamique de cercles ou de sphères

Pour résoudre pour $t$, on commence par calculer un vecteur intermédiaire $\mathbf{e}$ comme le vecteur de $\mathbf{c}_{m}$ à $\mathbf{c}_{s}$, et on pose $r$ égal à la somme des rayons :

$$\begin{matrix} \mathbf{e} & {= \mathbf{c}_{s} - \mathbf{c}_{m},} \\ r & {= r_{m} + r_{s}.} \\ \end{matrix}$$

Selon la loi des cosinus (voir la Section 1.4.5), on a

Undefined control sequence \intertext

Quelle racine choisir ? Le nombre inférieur (la racine négative) donne la valeur de $t$ quand les sphères commencent à se croiser. Le nombre plus grand (la racine positive) est le point où les sphères cessent de se croiser. On s’intéresse à la première intersection :

$$t = \mathbf{e} \cdot \hat{\mathbf{d}} - \sqrt{(\mathbf{e} \cdot \hat{\mathbf{d}})^{2} + r^{2} - \mathbf{e} \cdot \mathbf{e}}.$$

Si ${\parallel \mathbf{e} \parallel} < r$, alors les sphères se croisent à $t = 0$. Si $t < 0$ ou $t > l$, alors l’ intersection ne se produit pas dans la période de temps considérée. Si la valeur à l’intérieur de la racine carrée est négative, alors il n’y a pas d’intersection.

A.14Intersection d’une sphère et d’un AABB

Pour détecter l’intersection statique d’une sphère et d’un AABB, on trouve d’abord le point sur la boîte le plus proche du centre de la sphère en utilisant les techniques de la Section A.5. On calcule la distance de ce point au centre de la sphère et on compare cette distance avec le rayon. (En pratique, on compare la distance au carré avec le rayon au carré pour éviter la racine carrée dans le calcul de la distance.) Si la distance est inférieure au rayon, alors la sphère coupe l’AABB.

Arvo [1] discute de cette technique, qu’il utilise pour couper des sphères avec des boîtes “pleines”. Il discute aussi de quelques astuces pour couper des sphères avec des boîtes “creuses”.

Malheureusement, le test dynamique est plus compliqué que le test statique. Pour les détails, voir Lengyel [6].

A.15Intersection d’une sphère et d’un plan

Détecter l’intersection statique d’une sphère et d’un plan est relativement facile—on calcule simplement la distance du centre de la sphère au plan en utilisant l’ Équation (9.14). Si cette distance est inférieure au rayon de la sphère, alors la sphère coupe le plan. On peut en fait faire un test plus robuste, qui classe la sphère comme étant complètement à l’avant, complètement à l’arrière, ou à cheval sur le plan. Un extrait de code est donné dans le Listing A.3.

// Given a sphere and plane, determine which side of the plane
// the sphere is on.
//
// Return values:
//
// < 0  Sphere is completely on the back
// > 0  Sphere is completely on the front
// 0    Sphere straddles plane

int classifySpherePlane(
    const Vector3 &planeNormal,  // must be normalized
    float          planeD,       // p * planeNormal = planeD
    const Vector3 &sphereCenter, // center of sphere
    float          sphereRadius  // radius of sphere
) {

    // Compute distance from center of sphere to the plane
    float d = planeNormal * sphereCenter - planeD;

    // Completely on the front side?
    if (d >= sphereRadius) {
        return +1;
    }

    // Completely on the back side?
    if (d <= -sphereRadius) {
        return -1;
    }

    // Sphere intersects the plane
    return 0;
}

La situation dynamique est seulement légèrement plus compliquée. On considère le plan immobile, en assignant tout le déplacement relatif à la sphère.

On définit le plan de la façon habituelle par une normale de surface normalisée $\hat{\mathbf{n}}$ et une valeur de distance $d$ telles que tous les points $\mathbf{p}$ dans le plan satisfont l’équation $\mathbf{p} \cdot \hat{\mathbf{n}} = d$. La sphère est définie par son rayon $r$ et la position initiale du centre, $\mathbf{c}$. Le déplacement de la sphère est donné par un vecteur unitaire $\hat{\mathbf{d}}$ spécifiant la direction, et une distance $l$. Lorsque $t$ varie de 0 à $l$, le mouvement du centre de la sphère est donné par l’équation de droite $\mathbf{c} + t\hat{\mathbf{d}}$. Cette situation est montrée, vue de profil du plan, dans la Figure A.13.

Figure A.13 Une sphère se déplaçant vers un plan

Le problème est grandement simplifié en réalisant que peu importe où sur la surface du plan l’intersection se produit, le point de contact sur la surface de la sphère est toujours le même. Ce point de contact $\mathbf{p}_{0}$ est donné par $\mathbf{c} - r\hat{\mathbf{n}}$, comme montré dans la Figure A.14.

Figure A.14 Point de contact entre une sphère et un plan

Maintenant qu’on sait quel point sur la sphère entre en contact en premier avec le plan, on peut utiliser un simple test d’intersection rayon-plan de la Section A.9. On commence avec notre solution au test d’intersection rayon-plan de l’ Équation (A.4) et on substitue $\mathbf{c} - r\hat{\mathbf{n}}$ pour $\mathbf{p}_{0}$ :

Intersection dynamique d’une sphère et d’un plan

$$\begin{matrix} t & {= \frac{d - \mathbf{p}_{0} \cdot \hat{\mathbf{n}}}{\hat{\mathbf{d}} \cdot \hat{\mathbf{n}}},} \\ & {= \frac{d - (\mathbf{c} - r\hat{\mathbf{n}}) \cdot \hat{\mathbf{n}}}{\hat{\mathbf{d}} \cdot \hat{\mathbf{n}}},} \\ & {= \frac{d - \mathbf{c} \cdot \hat{\mathbf{n}} + r}{\hat{\mathbf{d}} \cdot \hat{\mathbf{n}}}.} \\ \end{matrix}$$

A.16Intersection d’un rayon et d’un triangle

Le test d’intersection rayon-triangle est très important en infographie et en géométrie computationnelle. En l’absence d’un test de lancé de rayons spécial contre un objet complexe donné, on peut toujours représenter (ou du moins approximer) la surface d’un objet comme un maillage de triangles et ensuite lancer des rayons contre cette représentation en maillage de triangles.

On utilise ici une stratégie simple de Badouel [2]. La première étape consiste à calculer le point où le rayon coupe le plan contenant le triangle. La Section A.9 a montré comment calculer l’intersection d’un plan et d’un rayon. Ensuite, on teste si ce point est à l’intérieur du triangle en calculant les coordonnées barycentriques du point, comme discuté dans la Section 9.6.4.

Pour accélérer ce test, on utilise quelques astuces :

• Détecter et retourner un résultat négatif (pas de collision) le plus tôt possible. Ceci est connu sous le nom de “sortie précoce”.

• Différer les opérations mathématiques coûteuses, comme la division, aussi longtemps que possible. Cela se fait pour deux raisons. Premièrement, si le résultat du calcul coûteux n’est pas nécessaire (par exemple, si on prend une sortie précoce), alors le temps qu’on a passé à effectuer l’opération a été gaspillé. Deuxièmement, cela donne au compilateur beaucoup de place pour tirer parti du pipeline d’opérateurs dans les processeurs modernes. Si une opération telle que la division a une longue latence, alors le compilateur peut être capable de regarder en avant et de générer du code qui commence l’opération de division tôt. Il génère ensuite du code qui effectue d’autres tests (prenant éventuellement une sortie précoce) pendant que l’opération de division est en cours. Puis, au moment de l’exécution, si et quand le résultat de la division est vraiment nécessaire, le résultat sera disponible ou au moins partiellement complété.

• Ne détecter que les collisions où le rayon approche le triangle du côté avant. Cela nous permet de prendre une sortie précoce très tôt sur environ la moitié des triangles. Croiser avec les deux côtés est légèrement plus lent.

Le Listing A.4 implémente ces techniques. Bien que cela soit commenté dans le listing, on a choisi d’effectuer certaines comparaisons en virgule flottante “à l’envers” car cela se comporte mieux en présence de données d’entrée invalides en virgule flottante et de NaN (Not a Number).

float rayTriangleIntersect(
    const Vector3 &rayOrg,   // origin of the ray
    const Vector3 &rayDelta, // ray length and direction
    const Vector3 &p0,       // triangle vertices
    const Vector3 &p1,       // .
    const Vector3 &p2,       // .
    float minT               // closest intersection found so far.
                             // (Start with 1.0)
) {

    // We'll return this huge number of no intersection is detected
    const float kNoIntersection = FLT_MAX;

    // Compute clockwise edge vectors.
    Vector3 e1 = p1 - p0;
    Vector3 e2 = p2 - p1;

    // Compute surface normal.  (Unnormalized)
    Vector3 n = crossProduct(e1, e2);

    // Compute gradient, which tells us how steep of an angle
    // we are approaching the *front* side of the triangle
    float dot = n * rayDelta;

    // Check for a ray that is parallel to the triangle, or not
    // pointing towards the front face of the triangle.
    //
    // Note that this also will reject degenerate triangles and
    // rays as well.  We code this in a very particular
    // way so that NANs will bail here.  (I.e. this does NOT
    // behave the same as ``dot >= 0.0f'' when NANs are involved)
    if (!(dot < 0.0f)) {
        return kNoIntersection;
    }

    // Compute d value for the plane equation.  We will
    // use the plane equation with d on the right side:
    // Ax + By + Cz = d
    float d = n * p0;

    // Compute parametric point of intersection with the plane
    // containing the triangle, checking at the earliest
    // possible stages for trivial rejection
    float t = d - n * rayOrg;

    // Is ray origin on the backside of the polygon?  Again,
    // we phrase the check so that NANs will bail
    if (!(t <= 0.0f)) {
        return kNoIntersection;
    }

    // Closer intersection already found?  (Or does
    // ray not reach the plane?)
    //
    // since dot < 0:
    //
    //      t/dot > minT
    //
    // is the same as
    //
    //      t < dot*minT
    //
    // (And then we invert it for NAN checking...)
    if (!(t >= dot*minT)) {
        return kNoIntersection;
    }

    // OK, ray intersects the plane.  Compute actual parametric
    // point of intersection
    t /= dot;
    assert(t >= 0.0f);
    assert(t <= minT);

    // Compute 3D point of intersection
    Vector3 p = rayOrg + rayDelta*t;

    // Find dominant axis to select which plane
    // to project onto, and compute u's and v's
    float u0, u1, u2;
    float v0, v1, v2;
    if (fabs(n.x) > fabs(n.y)) {
        if (fabs(n.x) > fabs(n.z)) {
            u0 = p.y - p0.y;
            u1 = p1.y - p0.y;
            u2 = p2.y - p0.y;

            v0 = p.z - p0.z;
            v1 = p1.z - p0.z;
            v2 = p2.z - p0.z;
        } else {
            u0 = p.x - p0.x;
            u1 = p1.x - p0.x;
            u2 = p2.x - p0.x;

            v0 = p.y - p0.y;
            v1 = p1.y - p0.y;
            v2 = p2.y - p0.y;
        }
    } else {
        if (fabs(n.y) > fabs(n.z)) {
            u0 = p.x - p0.x;
            u1 = p1.x - p0.x;
            u2 = p2.x - p0.x;

            v0 = p.z - p0.z;
            v1 = p1.z - p0.z;
            v2 = p2.z - p0.z;
        } else {
            u0 = p.x - p0.x;
            u1 = p1.x - p0.x;
            u2 = p2.x - p0.x;

            v0 = p.y - p0.y;
            v1 = p1.y - p0.y;
            v2 = p2.y - p0.y;
        }
    }

    // Compute denominator, check for invalid
    float temp = u1 * v2 - v1 * u2;
    if (!(temp != 0.0f)) {
        return kNoIntersection;
    }
    temp = 1.0f / temp;

    // Compute barycentric coords, checking for out-of-range
    // at each step
    float alpha = (u0 * v2 - v0 * u2) * temp;
    if (!(alpha >= 0.0f)) {
        return kNoIntersection;
    }

    float beta = (u1 * v0 - v1 * u0) * temp;
    if (!(beta >= 0.0f)) {
        return kNoIntersection;
    }

    float gamma = 1.0f - alpha - beta;
    if (!(gamma >= 0.0f)) {
        return kNoIntersection;
    }

    // Return parametric point of intersection
    return t;
}

Il y a une stratégie supplémentaire significative, non illustrée dans le Listing A.4, pour optimiser les calculs coûteux : précalculer leurs résultats. Si des valeurs telles que la normale du polygone peuvent être calculées à l’avance, alors différentes stratégies peuvent être utilisées.

En raison de l’importance fondamentale de ce test, les programmeurs cherchent toujours des moyens de le rendre plus rapide. La technique que l’on a donnée ici est une technique standard qui est facile à comprendre et produit les coordonnées barycentriques, souvent un sous-produit utile. Ce n’est pas la plus rapide. Voir la collection de tests d’intersection de Tomas Akenine-Möller sur la page web de Real-Time Rendering à l’adresse http://www.realtimerendering.com/intersections.html.

A.17Intersection de deux AABB

Détecter l’intersection statique de deux AABB est une opération extrêmement importante. Heureusement, c’est plutôt trivial.1 On vérifie simplement le chevauchement des étendues sur chaque dimension indépendamment. S’il n’y a pas de chevauchement sur une dimension particulière, alors les deux AABB ne se croisent pas. Cette technique est utilisée dans le Listing A.5.

bool aabbsOverlap(const AABB3 &a, const AABB3 &b) {

    // Check for a separating axis.
    if (a.min.x >= b.max.x) return false;
    if (a.max.x <= b.min.x) return false;
    if (a.min.y >= b.max.y) return false;
    if (a.max.y <= b.min.y) return false;
    if (a.min.z >= b.max.z) return false;
    if (a.max.z <= b.min.z) return false;

    // Overlap on all three axes, so their
    // intersection must be non-empty
    return true;
}

Cette stratégie est en fait une instance d’une stratégie plus générale connue sous le nom de test de l’axe séparateur. Si deux polyèdres convexes ne se chevauchent pas, alors il existe un axe séparateur sur lequel, si on projette les deux polyèdres, leurs projections ne se chevaucheront pas. (En 3D, il est plus facile de visualiser un plan perpendiculaire à l’axe séparateur qui peut être placé entre les deux polyèdres.) La clé de la méthode de l’axe séparateur est que seul un nombre fini d’axes doivent être testés : les normales des faces et certains produits vectoriels ; pour les détails, voir Ericson [3]. Si les projections des polyèdres sur ces axes se chevauchent dans tous les cas, alors on peut supposer en toute sécurité qu’aucun axe séparateur ne peut être trouvé. Dans le cas de deux AABB, seulement les trois axes cardinaux doivent être testés. De plus, ces “projections” extraient simplement la coordonnée appropriée.

L’intersection dynamique des AABB n’est que légèrement plus compliquée. Considérons un AABB immobile défini par les points extrêmes $\mathbf{s}_{min}$ et $\mathbf{s}_{max}$, et un AABB en mouvement, qui a les points extrêmes $\mathbf{m}_{min}$ et $\mathbf{m}_{max}$ dans la position initiale à $t = 0$. L’AABB en mouvement se déplace d’un montant donné par le vecteur $\mathbf{d}$, lorsque $t$ varie de 0 à 1.

Notre tâche consiste à calculer $t$, le point paramétrique dans le temps où la boîte en mouvement entre en collision avec la boîte immobile pour la première fois. (On suppose que les boîtes ne se croisent pas initialement.) Pour ce faire, on va tenter de déterminer le premier point dans le temps où les boîtes se chevauchent sur toutes les dimensions simultanément. Puisque cela s’applique en 2D ou 3D, on illustre le problème ici en 2D ; étendre la technique en 3D est direct. On analyse chaque coordonnée séparément, résolvant deux (ou trois, en 3D) problèmes unidimensionnels séparés, et combinant ensuite ces résultats pour donner la réponse.

Le problème est maintenant unidimensionnel. On a besoin de connaître l’intervalle de temps pendant lequel les deux boîtes se chevauchent sur une dimension particulière. Imaginons projeter le problème sur l’axe $x$ (par exemple), comme montré dans la Figure A.15.

Figure A.15 Projection du problème d’intersection dynamique AABB sur un axe

En avançant dans le temps, le segment de droite représentant la boîte en mouvement va glisser le long de la droite numérique. Dans l’illustration de la Figure A.15, à $t = 0$ la boîte en mouvement est complètement à gauche de la boîte immobile, et à $t = 1$, la boîte en mouvement est complètement à droite de la boîte immobile. Il y a un point $t_{enter}$ où les boîtes commencent à se chevaucher, et un point $t_{leave}$ où les boîtes cessent de se chevaucher. Pour la dimension considérée, soit $m_{min}(t)$ et $m_{max}(t)$ les valeurs minimale et maximale respectivement de la boîte en mouvement au temps $t$, données par

$$\begin{matrix} {m_{min}(t)} & {= m_{min}(0) + td,} \\ {m_{max}(t)} & {= m_{max}(0) + td,} \\ \end{matrix}$$

où $m_{min}(0)$ et $m_{max}(0)$ sont les étendues initiales de la boîte en mouvement et $d$ est la composante du vecteur de déplacement $\mathbf{d}$ pour cet axe. Soit $s_{min}$ et $s_{max}$ des définitions similaires pour la boîte immobile. (Bien sûr, ces valeurs sont indépendantes de $t$ puisque la boîte est immobile.) Le temps $t_{enter}$ est la valeur de $t$ pour laquelle $m_{max}(t) = s_{min}$. En résolvant, on obtient

$$\begin{matrix} {m_{max}(t_{enter})} & {= s_{min},} \\ {m_{max}(0) + t_{enter}d} & {= s_{min},} \\ {t_{enter}d} & {= s_{min} - m_{max}(0),} \\ t_{enter} & {= \frac{s_{min} - m_{max}(0)}{d}.} \\ \end{matrix}$$

De même, on peut résoudre pour $t_{leave}$ :

$$\begin{matrix} {m_{min}(t_{leave})} & {= s_{max},} \\ {m_{min}(0) + t_{leave}d} & {= s_{max},} \\ {t_{leave}d} & {= s_{max} - m_{min}(0),} \\ t_{leave} & {= \frac{s_{max} - m_{min}(0)}{d}.} \\ \end{matrix}$$

Trois points importants sont notés ici :

• Si le dénominateur $d$ est nul, alors les boîtes se chevauchent toujours ou ne se chevauchent jamais.

• Si la boîte en mouvement commence à droite de la boîte immobile et se déplace vers la gauche, alors $t_{enter} > t_{leave}$. On gère ce scénario en échangeant leurs valeurs pour s’assurer que $t_{enter} < t_{leave}$.

• Les valeurs de $t_{enter}$ et $t_{leave}$ peuvent être en dehors de l’ intervalle [0,1]. Pour accommoder les valeurs de $t$ en dehors de cet intervalle, on peut penser à la boîte en mouvement comme se déplaçant le long d’une trajectoire infinie parallèle à $d$. Si $t_{enter} > 1$ ou $t_{leave} < 0$, alors il n’y a pas de chevauchement dans la période de temps considérée.

On a maintenant un moyen de trouver l’intervalle de temps, borné par $t_{enter}$ et $t_{leave}$, quand les deux boîtes se chevauchent sur une seule dimension. L’intersection de ces intervalles sur toutes les dimensions nous donne l’ intervalle de temps où les boîtes se croisent. Ceci est illustré dans la Figure A.16 pour deux intervalles de temps en 2D.

Figure A.16 Intersection de deux intervalles de temps

Ne confondez pas la Figure A.16 avec la Figure A.15. Dans la Figure A.16, l’axe est l’axe temporel ; dans la Figure A.15 l’axe est l’axe $x$.

Si l’intervalle est vide, alors les boîtes ne se collisionnent jamais. Si l’intervalle se trouve complètement en dehors de l’intervalle $0 \leq t \leq 1$, alors il n’y a pas de collision pendant la période de temps d’intérêt. En fait, l’intervalle pendant lequel les boîtes se chevauchent est plus d’information qu’on voulait, puisque on s’intéresse seulement au point dans le temps où les boîtes commencent à se croiser, pas quand elles cessent de se croiser. Néanmoins, on a besoin de maintenir cet intervalle, principalement pour déterminer s’il est vide.

Malheureusement, en pratique, les boîtes englobantes pour les objets sont rarement alignées sur les axes dans le même espace de coordonnées. Cependant, parce que ce test est relativement rapide, il est utile comme test de rejet trivial préliminaire, suivi d’un test plus spécifique (et généralement plus coûteux).

A.18Intersection d’un rayon et d’un AABB

Calculer l’intersection d’un rayon avec un AABB est un calcul important car le résultat de ce test est couramment utilisé pour le rejet trivial sur des objets plus complexes. (Par exemple, si on souhaite lancer des rayons contre plusieurs maillages de triangles, on peut d’abord lancer des rayons contre les AABB des maillages pour rejeter trivialement des maillages entiers d’un coup, plutôt que de devoir vérifier chaque triangle.)

Woo [7] décrit une méthode qui détermine d’abord quel côté de la boîte serait coupé, puis effectue un test d’intersection rayon-plan contre le plan contenant ce côté. Si le point d’intersection avec le plan est à l’intérieur de la boîte, alors il y a une intersection ; sinon, il n’y a pas d’intersection. Ceci est implémenté dans le Listing A.6.

// Return parametric point of intersection 0...1, or a really huge
// number if no intersection is found
float AABB3::rayIntersect(
    const Vector3 &rayOrg,      // orgin of the ray
    const Vector3 &rayDelta,    // length and direction of the ray
    Vector3 *returnNormal       // optionally, the normal is returned
) const {

    // We'll return this huge number if no intersection
    const float kNoIntersection = FLT_MAX;

    // Check for point inside box, trivial reject, and
    // determine parametric distance to each front face
    bool inside = true;

    float xt, xn;
    if (rayOrg.x < min.x) {
        xt = min.x - rayOrg.x;
        if (xt > rayDelta.x) return kNoIntersection;
        xt /= rayDelta.x;
        inside = false;
        xn = -1.0f;
    } else if (rayOrg.x > max.x) {
        xt = max.x - rayOrg.x;
        if (xt < rayDelta.x) return kNoIntersection;
        xt /= rayDelta.x;
        inside = false;
        xn = 1.0f;
    } else {
        xt = -1.0f;
    }

    float yt, yn;
    if (rayOrg.y < min.y) {
        yt = min.y - rayOrg.y;
        if (yt > rayDelta.y) return kNoIntersection;
        yt /= rayDelta.y;
        inside = false;
        yn = -1.0f;
    } else if (rayOrg.y > max.y) {
        yt = max.y - rayOrg.y;
        if (yt < rayDelta.y) return kNoIntersection;
        yt /= rayDelta.y;
        inside = false;
        yn = 1.0f;
    } else {
        yt = -1.0f;
    }

    float zt, zn;
    if (rayOrg.z < min.z) {
        zt = min.z - rayOrg.z;
        if (zt > rayDelta.z) return kNoIntersection;
        zt /= rayDelta.z;
        inside = false;
        zn = -1.0f;
    } else if (rayOrg.z > max.z) {
        zt = max.z - rayOrg.z;
        if (zt < rayDelta.z) return kNoIntersection;
        zt /= rayDelta.z;
        inside = false;
        zn = 1.0f;
    } else {
        zt = -1.0f;
    }

    // Ray origin inside box?
    if (inside) {
        if (returnNormal != NULL) {
            *returnNormal = -rayDelta;
            returnNormal->normalize();
        }
        return 0.0f;
    }

    // Select farthest plane - this is
    // the plane of intersection.
    int which = 0;
    float t = xt;
    if (yt > t) {
        which = 1;
        t = yt;
    }
    if (zt > t) {
        which = 2;
        t = zt;
    }
    switch (which) {

        case 0: // intersect with yz plane
        {
            float y = rayOrg.y + rayDelta.y*t;
            if (y < min.y || y > max.y) return kNoIntersection;
            float z = rayOrg.z + rayDelta.z*t;
            if (z < min.z || z > max.z) return kNoIntersection;

            if (returnNormal != NULL) {
                returnNormal->x = xn;
                returnNormal->y = 0.0f;
                returnNormal->z = 0.0f;
            }

        } break;

        case 1: // intersect with xz plane
        {
            float x = rayOrg.x + rayDelta.x*t;
            if (x < min.x || x > max.x) return kNoIntersection;
            float z = rayOrg.z + rayDelta.z*t;
            if (z < min.z || z > max.z) return kNoIntersection;

            if (returnNormal != NULL) {
                returnNormal->x = 0.0f;
                returnNormal->y = yn;
                returnNormal->z = 0.0f;
            }

        } break;

        case 2: // intersect with xy plane
        {
            float x = rayOrg.x + rayDelta.x*t;
            if (x < min.x || x > max.x) return kNoIntersection;
            float y = rayOrg.y + rayDelta.y*t;
            if (y < min.y || y > max.y) return kNoIntersection;

            if (returnNormal != NULL) {
                returnNormal->x = 0.0f;
                returnNormal->y = 0.0f;
                returnNormal->z = zn;
            }

        } break;
    }

    // Return parametric point of intersection
    return t;

}

Références

[1] James Arvo.   “A Simple Method for Box-Sphere Intersection Testing.”   In Graphics Gems, edited by Andrew S. Glassner. San Diego: Academic Press Professional, 1990.

[2] Didier Badouel.   “An Efficient Ray-Polygon Intersection.”   In Graphics Gems, edited by Andrew S. Glassner. San Diego: Academic Press Professional, 1990.

[3] Christer Ericson.   Real-Time Collision Detection.   San Francisco: Morgan Kaufmann Publishers, 2005.

[4] Ronald Goldman.   “Intersection of Three Planes.”   In Graphics Gems, edited by Andrew S. Glassner. San Diego: Academic Press Professional, 1990.

[5] Jeff Hultquist.   “Intersection of a Ray with a Sphere.”   In Graphics Gems, edited by Andrew S. Glassner. San Diego: Academic Press Professional, 1990.

[6] Eric Lengyel.   Mathematics for 3D Game Programming and Computer Graphics, deuxième édition.   Boston: Charles River Media, 2004.   http://www.terathon.com/books/mathgames2.html.

[7] Andrew Woo.   “Fast Ray-Box Intersection.”   In Graphics Gems, edited by Andrew S. Glassner. San Diego: Academic Press Professional, 1990.

1. C’est l’une des questions d’entretien préférées de Fletcher. Il est surprenant que tant de programmeurs ne sachent pas comment effectuer cette opération très simple. Ne soyez pas l’un de ces candidats !

<< Postface

Retour en haut

Réponses aux exercices >>