KenoMerckx

Homepage

Back to homepage

Page made with Jérémie Moerenhout from the The University of Auckland.

Introduction aux structures de données kinétiques

Une structure de donnée kinétique (KDS) maintient un ensemble d'attributs dans un système d'objets géométriques se déplaçant de manière continue. Les KDS ont de nombreuses applications: on les retrouve par exemple en détection de collision, en robotique ou encore en animation. Le but est de maintenir une structure donnée, qui évolue de manière discrète alors que les objets qui la composent évoluent de manière continue. Le principe de base repose principalement sur la gestion d'une liste d'évènements futures qui correspondent à des moments où la structure peut être modifiée. Intuitivement, il s'agit donc de deviner à quels moments il va se passer quelque chose et de n'agir qu'à ces instants précis. Par exemple, si deux polygones simples se déplacent dans un plan et que l'on souhaite simuler une collision, alors une KDS qui modélise cette structure devra calculer le moment où la collision aura lieu et ensuite attendre que cela arrive.

Ce projet comprend une première partie introductive dans laquelle sont données les définitions et les concepts de base et se trouve dans la suite de ce texte. La deuxième partie est divisée en trois sections, comprenant chacune un exemple d'une KDS, accessible via les menus ou en cliquant sur les liens ci-dessous:

Nous détaillons dans un premier temps le vocabulaire utilisé et expliquons le fonctionnement de base d'une KDS.

La description des attributs que l'on souhaite maintenir est appelée la fonction de configuration des données. Par exemple, la fonction de configuration peut être une liste ordonnée de points (voir exemple 1 et applet 1), une double liste triée de points (voir exemple 2) dont la première contient les points de l'enveloppe convexe supérieure, triés selon l'axe $x$ et la deuxième contient les points de l'enveloppe convexe inférieure également triés selon l'axe $x$.

Lorsque l'on souhaite maintenir une fonction de configuration d'objets se déplaçant continûment, il faut détecter les moments où la fonction de configuration est modifiée et la réparer en conséquence. Vérifier à chaque instant que la fonction de configuration est préservée et la réparer dans son entièreté est une perte de temps énorme car, d'une part, il peut se passer beaucoup de temps durant lequel la fonction de configuration n'est pas modifiée et d'autre part, réparer la fonction de configuration dans son entièreté est rarement nécessaire car les modifications sont souvent locales. Le but des implémentations utilisant les KDS est de tirer les avantages de cette précédente remarque en traitant un nombre aussi petit que possible d'évènements tout en maintenant la fonction de configuration.

Nous supposons que le mouvement de chaque objet est connu à l'avance et qu'il peut changer à certains instants isolés. Par exemple, un point peut se déplacer à vitesse constante et son mouvement est mis à jours lorsqu'il rebondit contre un "mur" ou entre en collision avec un autre objet. L'interface qui relie la KDS au mouvement des objets est présentée sous forme d'une liste d'attente globale d'évènements. Cette liste contient les évènements qui peuvent modifier la fonction de configuration. Dans l'exemple de la liste triée de points se déplaçant sur une droite, un évènement peut être du type: les points $a$ et $b$ ont la même coordonnée $x$. Un certificat est une condition algébrique impliquant un certain nombre d'objets et qui garantit que la fonction de configuration est maintenue. Par exemple, étant donnés deux points $a$ et $b$ ayant une position $a_{x}$ et $b_{x}$ respectivement, un certificat garantissant que ces deux points sont triés sera:

$a_x-b_x=0.$

Dans l'exemple de l'enveloppe convexe, un type d'évènement sera: trois points dans le plan $a$, $b$ et $c$ son alignés et un certificat sera par exemple

$ \left|\begin{matrix}a_x&a_y&1\\b_x&b_y&1\\c_x&c_y&1\end{matrix}\right|=a_xb_y+b_xc_y+c_xa_y-a_yb_x-b_yc_x-c_ya_x=0$

A chaque instant, la liste d'attente des évènements contiendra plusieurs évènements munis de l'instant (future) où le certificat est violé. Ce temps, que nous appellerons "temps d'expiration" ou "moment d'expiration", peut être calculé grâce au fait que les mouvements sont connus à l'avance. Si à un moment, le mouvement d'un objet change, alors tous les certificats impliquant cet objet sont modifiés et le temps d'expiration est mis à jour.

Une propriété primordiale d'une KDS est donc que les certificats forment à chaque instant une preuve de validité de la fonction de configuration. Le minimum des temps d'expiration représente donc le premier moment où la fonction de configuration peut changer. Ainsi, l'algorithme ne réparera la fonction de configuration qu'à ces moments clés et on évite donc des vérifications lorsqu'il ne se passe rien. Lorsqu'un certificat n'est plus valide, c'est-à-dire lorsque l'on a atteint son moment d'expiration, la KDS doit mettre à jour la liste d'évènements et réparer la fonction de configuration.

Pour mesurer les performances d'une KDS, on mesurera, entre autres, la complexité du calcul du moment d'expiration d'un certificat. Une KDS est réactive si, dans le pire des cas, la complexité du calcul de ces temps est "petit". Une deuxième mesure de performance d'une KDS consiste à regarder le nombre maximum d'évènements dans la liste d'attente. On distingue les évènements externes, c'est-à-dire ceux qui affectent la fonction de configuration, des évènements internes, c'est-à-dire ceux qui ne modifient pas la fonction de configuration. On dira qu'une KDS est efficace si le nombre d'évènements externes dans la liste d'attente est un $O$ du nombre d'évènements total dans la liste d'attente. La taille d'une KDS est le nombre maximum d'évènements dans la liste d'attente à chaque instant. Une KDS est compacte si la taille est linéaire en le nombre d'objets en mouvement. Enfin, une KDS est locale si à n'importe quel moment, le nombre d'évènements dans la liste d'attente qui concernent un objet en particulier est "petit".

Voici à présent un premier exemple d'une KDS qui a pour objectif de maintenir une liste triée de points se déplaçant sur une droite.

Pour des informations supplémentaires sur les KDS, nous vous invitons à parcourir la thése de Daniel Russel

Liste de points triée

Soit un ensemble ordonné de $n$ points sur la droite réelle. Supposons que ces $n$ points se déplacent de manière indépendante et chacun avec une vitesse constante qui lui est propre. Nous allons décrire les étapes de construction d'une KDS qui maintient une liste ordonnée contenant ces $n$ points. Un certificat est crée pour chaque paire de points $\{a,b\}\subset \mathbf{R}$ adjacents dont la relation $r$ est définie par $r\equiv a-b$. Il est clair que tant que $r$ n'est pas nul, l'ordre de $a$ et $b$ ne change pas. Donc l'ensemble des certificats pour chaque paire de points adjacents définit une preuve de conservation de la structure. Calculer le temps d'expiration d'un certificat revient à calculer le temps $t$ tel que $a(t)-b(t)$ $=0$. Comme le mouvement est rectiligne uniforme, si on note $v_a$ la vitesse de $a$ et $v_b$ la vitesse de $b$, on a $a(t)=a+v_at$ et $b(t)=b+v_bt$ et donc

$a+vt-wt-b=0$

$t(v-w)=b-a$

$ t=\frac{b - a}{v-w}$

Ainsi, pour chaque certificat dont le temps d'expiration est positif, on insère un évènement dans la liste d'attente de la KDS. Remarquons que tous les évènements sont externes car ils modifient tous l'ordre des points. Lorsqu'un évènement arrive, on met à jour les certificats de la manière suivante: supposons que l'on ait quatre points adjacents, notés $a,b,c,d$ de gauche à droite et supposons que le certificat concernant $b$ et $c$ est violé. Alors cela signifie que $b$ et $c$ vont permuter et on supprime donc le certificat entre $b$ et $c$ car ces deux points ne peuvent que s'éloigner après permutation. On supprime également les certificats entre $a$ et $b$ et entre $c$ et $d$ et on crée les certificats entre $a$ et $c$ et entre $b$ et $d$ si nécessaire (c'est-à-dire s'ils se rapprochent). Ainsi, à chaque évènement, au plus trois évènements sont détruits et au plus deux évènements sont crées. Par ailleurs, à chaque évènement, la fonction de configuration est mis à jour en permutant les deux points relatifs au certificat. On peut voir un exemple de ce procédé sur le dessin suivant qui illustre une telle situation au temps $t_0$ et $t_{0}+1$. Un trait rouge entre deux points indique qu'il existe un évènement entre ces deux points et les traits hachurés montrent comment les points se sont déplacés.

A l'instant $t_0$, le premier événement dans la liste d'attente est l'évènement $F$. Ensuite, à l'instant suivant, les évènements $F$ et $E$ sont détruits et l'événement $G$ est créé. Aucun événement n'a été créé entre $b$ et $d$ car ces deux points s'éloignent l'un de l'autre.

Voici maintenant un diagramme illustrant le fonctionnant du programme. A l'instant initial, le programme crée la liste de points, la trie et crée la liste d'évènements. Le moment d'expiration minimum vaut alors $T_0$ et le compteur est initialisé à $0$. A la prochaine étape, le programme affiche les points à l'écran et compare le compteur à $T_0$. Si, à la prochaine image, deux points vont se croiser, alors cela signifie que le compteur est plus grand que $T_0-1$; sinon, on incrémente le compteur, on déplace les points et on compare à nouveau le compteur et $T_0$. Lorsque le compteur est plus grand que $T_0-1$, alors il faut faire les mise à jour nécessaire avant d'afficher les points à l'écran. Dans un premier temps, on translate tous les temps d'expiration de sorte que le premier de ces temps soit compris entre $0$ et $1$. Ensuite, on met à jour la fonction de configuration et la liste des évènements (durant cette étape, l'évènement courant sera effacé et $T_0$ sera mis à jour). On effectue ces mises à jour tant que le temps $T_0$ est plus petit que $1$. Lorsqu'il n'y a plus d'évènements à traiter, le programme décrémente tous les temps d'expiration restant, réinitialise le compteur à $0$, déplace les points, les affiche et recommence depuis la comparaison du compteur et de $T_0$. Lorsqu'il n'y a plus d'évènement dans la liste d'attente, alors on considère que $T_0=\infty$.

Pour voir l'Applet: Liste de points, cliquez sur ce lien.

Diagramme des objets du programme:

Enveloppe convexe 2D

Voici les détails de construction d'une structure de donnée kinétique destinée à maintenir l'enveloppe convexe d'un ensemble $X$ de $n$ points se déplaçant à vitesse constante dans le plan. Nous procédons de la même manière que [BGH99] et utilisons essentiellement les mêmes notations. Le problème de l'enveloppe convexe peut être décomposé en un problème d'enveloppe convexe supérieure et un problème d'enveloppe convexe inférieure. Dans ce projet, nous nous restreignons à l'enveloppe convexe supérieure, l'autre cas étant symétrique. Tout d'abord, nous dualisons le problème, afin de le rendre plus simple. Rappelons que le dual du point $(p,q)$ est la droite d'équation $y=px+q$ et le dual de la droite d'équation $y=px+q$ est le point de coordonnées $(-p,q)$. Ainsi, le point $(p,q)$ est incident à la droite $y=rx+s$ si et seulement si la droite duale $y=px+q$ est incidente au point dual $(r,s)$. En effet, $(p,q)$ est incident à la droite $y=rx+s$ revient à écrire

$ q=-rp+s$

Donc $-rp+q=s$, qui est vrai si et seulement si le point $(-r,s)$ est incident à la droite $y=px+q$. D'autre part, si $(p,q)$ est "en-dessous" de la droite $y=rx+s$, c'est-à-dire si $q < rp+s$ , alors la droite duale de $(p,q)$ est "au-dessus" du dual de la droite $y=rx+s$ (figure suivante).

Notons $C$ la séquence des points de $X$ situés de gauche à droite sur l'enveloppe convexe supérieure. Alors les droites duales de ces points forment une séquence de droites ayant des pentes de plus en plus grande. De plus tous les points du primal qui ne sont pas dans $C$ deviennent des droites du dual situées en dessous des intersections des autres droites (figure ci-dessous). Dès lors, trouver cette séquence $C$ du primal revient à trouver la séquence des droites duales qui forment l'enveloppe supérieure.

Le principe de fonctionnement de cette KDS consiste à diviser l'ensembles des droites du duale en deux sous-ensembles qui seront eux-mêmes divisés en deux sous-ensembles et ainsi de suite formant ainsi un arbre binaire blancé (figure ci-dessous). Chaque noeud de cet arbre est un sous-ensemble de droites dont l'enveloppe supérieure peut être construite en fusionnant les enveloppes supérieures de ces deux descendants.

Nous représentons l'enveloppe supérieure des droites d'un noeud par une fonction linéaire par morceau vue comme une double liste d'arêtes et de sommets ordonnés de gauche à droite et nous appelons cette liste une chaîne. Pour le noeud $N$, on considère alors la chaîne de son descendant droit et la chaîne de son descendant gauche que l'on appelle chaîne rouge et chaîne bleue respectivement. Définir une KDS qui maintient l'enveloppe convexe supérieure de $X$ revient alors à définir, pour chaque noeud, une KDS qui maintient l'enveloppe supérieure de deux fonctions linéaires par morceau (figure suivante).

Dans la suite, on notera les arêtes par des lettres miniscules et le point à l'intersection de l'arête $a$ et de l'arête $b$ est noté $ab$. Le concurrent du sommet $ab$, c'est-à-dire l'arête située en-dessous ou au-dessus sur l'autre chaîne sera notée $\operatornam{ce}(ab)$. Par exemple $\operatorname{ce}(ab)=e$ sur la figure suivante.

On notera $\chi(ab)$ la couleur (rouge ou bleu) du sommet $ab$. Enfin, on notera $ab.\operatorname{prev}$ le sommet bleu ou rouge qui est situé à gauche de $ab$ et qui a l'abscisse la plus proche de l'abscisse de $ab$. On définit $ab.\operatorname{next}$ de manière similaire mais en regardant les sommets rouges ou bleus situés à gauche. Nous allons maintenant définir des comparateurs qui seront utiles pour décrire les certificats. Notons $ \textless_{x}$ la relation qui compare l'abscisse de deux points. Un deuxième type de comparateur, noté $\textless_y$ sera utilisé pour vérifier qu'un sommet est situé en-dessous d'une arête. Enfin le comparateur $\textless_s$ compare la pente de deux arêtes (figure). La liste des certificats de notre KDS est construite sur ces relations. Cette liste est décrite sur le tableau ci-dessous dont la première colonne contient le nom du certificat, la deuxième colonne donne la relation qui définit le certificat et la troisème colonne donne la condition sous laquelle ce certificat existe.

Certificat Comparaisons Conditions

x[ $ab$ ]

$ ab \textless_x ab.\operatorname{next}$

$ \chi(ab) \neq \chi(ab.\operatorname{next})$

yli[ $ab$]

  $ab \textless_y$ ou $\textgreater_y \operatorname{ce}(ab)$  

$b\cap \operatorname{ce}(ab)\neq \emptyset $

yri[ $ab$]

  $ab \textless_y$ ou $\textgreater_y \operatorname{ce}(ab)$  

$a\cap \operatorname{ce}(ab)\neq \emptyset $

yt[ $ab$]

$\operatorname{ce}(ab) \textless_y ab$

$a\textless_s \operatorname{ce}(ab)\textless_s b$

$\operatorname{ce}(ab)\textless_y ab$

slt[ $ab$]

$a\textless_s \operatorname{ce}(ab)$

srt[ $ab$]

$\operatorname{ce}(ab) \textless_y b$

sl[ $ab$]

$ b\textless_s \operatorname{ce}(ab)$

$ b\textless_s \operatorname{ce}(ab) \mbox{ et } ab\textless_y \operatorname{ce}(ab)$

sr[ $ab$]

  $\operatorname{ce}(ab) \textless_s a$  

  $\operatorname{ce}(ab) \textless_s a \mbox{ et } ab\textless_y \operatorname{ce}(ab)$  

Un certificat $x[ab]$ vérifie que le point $ab$ est situé à gauche du point $ab.\operatorname{next}$. Chaque intersection entre la chaîne bleue et la chaîne rouge est encadrée par les certificats $yli[ab]$ à gauche et $yri[ab]$ à droite. Le certificat $yt[ab]$ vérifie qu'un point $ab$ est au-dessus de son concurrent et que les arêtes $a$ et $b$ ont une pente respectivement plus petite et plus grande que $\operatorname{ce}[ab]$. Un certificat $yt[ab]$ est toujours accompagné des certificats $slt[ab]$ et $srt[ab]$ qui vérifient respectivement que la pente de $a$ est plus petite que la pente de $\operatorname{ce}[ab]$ et que la pente de $b$ est plus grande que la pente de $\operatorname{ce}[ab]$. Enfin, un certificat $sl[ab]$ ou $sr[ab]$ vérifie que le point $ab$ est situé en dessous de son concurrent et que la droite $a$ ou $b$ a une pente respectivement plus grande et plus petite que le concurrent de $ab$. Comme énoncé et démontré dans [BGH99], cette liste de certificat constitue une preuve de validité que $C$ forme l'enveloppe convexe supérieure, dans le sens où tant que tous les certificats de notre liste sont valides, alors l'enveloppe convexe supérieure reste inchangée. Avant de lancer le programme en bas de page, qui implémente une kds pour l'enveloppe convexe supérieure.

Avant de lancer le programme suivant, nous vous conseillons de lire le mode d'emploi ci-dessous.

Télécharger le programme pour:

Linux32, Linux64, MacOSX, Windows32, Windows64.

Voici deux captures d'écran du programme:

Collision de polygones simples 2D

Les KDS peuvent aussi être appliquées au problème de détection de collisions entre objets mobiles. Malheureusement, il devient vite difficile de gérer le cas général, c'est pourquoi, nous nous restreignons ici au cas de la détection de collision entre deux polygones simples. Le cas en dimension trois peut-être observer dans [GXZ01]. L'idée mise en place est de découper l'espace entre les polygones en cellules qui se déformeront continûment avec le mouvement des polygones, avec la propriété que si deux cellules s'intersectent, alors les polygones se superposent. Ensuite Il suffit d'utiliser ce découpage comme certificat dans notre KDS. La question centrale du problème est donc de trouver un "bon" découpage du plan. Plusieurs méthodes ont été proposés au cours des années précédentes, et il n'est pas encore clair à ce jour si une de celle-ci domine les autres en efficacité. Nous présentons ici comme méthode de découpage la "triangulation géodésique relative externe" (TGRE), proposée dans [BEG+99]. Mais avant cela, quelques définitions. Pour un polygone $P$, on appelle $\delta P$ sa frontière. Pour deux sommets de $P$: $x$ et $y$, on nomme $C(x,y)$ la chaîne polygonale (i.e. courbe constituée d'un ensemble de segments de droites reliés les uns aux autres) contenue dans $\delta P$ joignant $x$ à $y$ dans le sens trigonométrique. Définissons $\pi(x,y)$ comme étant le plus court chemin de $x$ à $y$ homotope (sans rentrer dans les détails cela veut dire continûment déformable) à $C(x,y)$ dans $P ^\complement$. Ceci est une chaîne polygonale orientée souvent appelée géodésique de $x$ à $y$. Ces notions sont illustrées par la figure ci-dessous.

Pour terminer, nous dirons qu'une géodésique est épinglée à un point du plan si celui-ci est compris dans la géodésique. Dans la figure ci-dessus, $\pi(x,y)$ est épinglée à au sommet $z$.

Nous allons à présent définir la triangulation géodésique relative externe. Pour cela, construisons un arbre binaire pour chacun des deux polygones $P$ et $Q$, dont les feuilles sont les arêtes des polygones ordonnées dans le sens trigonométrique. Ensuite fusionnons ceux-ci en un seul arbre binaire,en ajoutant un noeud racine qui aurait comme fils les deux arbres construisent précédemment. Un exemple de cette construction est donnée par les schémas suivants.

Ensuite il faut associer une géodésique à chaque noeud de cet arbre. Pour tout noeud $t$ de celui-ci (différent de la racine) considérons le sous-arbre de ses descendants, et associons à $t$ la géodésique qui relie les points points extrêmes de la chaîne constitué des feuilles de ce sous-arbre. Observons ce procédé pour une géodésique particulière associée à un noeud $t$ de $T$:

>

Pour la racine, associons la géodésique qui est homotope au bord d'un des polygones, et épinglée à un des sommets de l'autre. Ce dernier sommet doit être bien choisi de sorte que quand les enveloppes convexes des deux polygones sont disjointes, les deux propriétés suivantes sont respectées:

Ce système de géodésique forme notre division du plan en cellules. Notons que cette division dépend de l'arbre choisit. Sur la figure suivante

>

nous pouvons voir la TGRE associé à l'arbre $T$ et aux polygones $P$ et $Q$ de l'exemple précédent. La géodésique associée à la racine de $T$ est représentée en rouge. Les arêtes rouges en pointillés satisfont chacune une des conditions énoncées ci-dessus. Cette géodésique est épinglée au sommet commun aux arêtes $j$ et $k$ de $P$.

Deux arêtes adjacentes dans la division du plan définissent un coin, qui peut être concave, convexe, ou dégénéré ($0^\circ$ ou $180^\circ$). C'est sur cela que nous allons nous baser pour construire des "certificats coin" qui spécifient si un coin est concave ou convexe. Tout mouvement des polygones qui ne rend pas un des certificats invalide ne cause pas de superposition de cellules. Et donc, nous pouvons détecter les collisions en maintenant la TGRE. Pour ceci, nous plaçons tous les certificats coin dans une fille à priorités basé sur leurs moments d'expirations. Comme la TGRE reste la même tant qu'aucun certificat n'est violé, il suffit de savoir comment la mettre à jour quand un évènement arrive. Sans rentrer dans les détails, un certificat coin convex se transformera en un certificat concave spécifique, mais un certificat coin concave se transformera en certificat coin convexe (selon les noeuds de l'arbre impliqués dans les certificats se trouvent sur un même chemin). Il est possible de montrer que cette structure prend un temps $O(\log^2 n)$ pour traiter un évènement, où où $n$ est le nombre de sommets cumulé des deux polygones [BEG+99]. Comme le mouvement des polygones est rigide, ils ne rentreront jamais en collision avec eux-mêmes et donc seulement les certificats qui impliquent les $P$ et $Q$ peuvent être violé. Ce sont les évènements externes. Dans la structure kinetic, un changement de mouvement d'un des polygones oblige a recalculer les moments d'expirations de tout les évènements externes. Il est donc souhaitable que l'ensemble des évènements externes soit petit. Il est possible de montrer que ce nombre est effectivement contrôlable: il est de l'ordre de $O(n \log n)$ [BEG+99]. En conclusion, nous avons une KDS qui est à la fois efficace et réactive. Notons qu'il existe un autre découpage du plan en cellules, plus ou moins semblable à la TGRE qui permet de construire une KDS qui gère les collisions dans le plan de plusieurs polygones simples. Un exemple de telle KDS a été implémentée par Bettina Speckmann et est disponible ici.

Bonus

Collision brut force (beta test).

Pesenteur.


Back to homepage