Metafor

ULiege - Aerospace & Mechanical Engineering

User Tools

Site Tools


commit:2017:08_16

This is an old revision of the document!


Commit 2017-08-16

Ce commit est pour améliorer quelques routines liées au contact et pour mettre progressivement mes développements sur la version courante.

Cas Test - Schéma d'augmentation alternative

Afin de conserver une trace de l'interface des nouvelles méthodologies, j'ai ajouté les cas tests implémentés et présentés lors de la conférence ICCCM 2017.

Boundary Volume Hierarchy

La détection du contact dans Metafor peut être séparée en deux phases distinctes : détection globale et détection locale. La détection globale indique grossièrement sur quelle portion de l'entité maître le nœud esclave sera potentiellement en contact tandis que la détection locale détermine la projection du nœud esclave sur cette portion de l'entité maître. La phase de détection globale se fait en général à l'aide de boites alignées selon les axes Cartésiens et elle est critique dans le cas du contact entre corps déformable. En effet, dans ce cas là, nous devons parcourir l'ensemble des facettes du corps maître et répertorier toutes les projections valides avant décider laquelle d'entre elles sera la bonne projection. Dans ce cas là, on constate que le temps de calcul peut littéralement exploser si on augmente le nombre d'éléments sur la surface du corps maître, car on a une tendance du type O(N*M) avec N = le nombre de facettes du corps maître et M = le nombre de nœuds du corps esclave.

Pour améliorer l'efficacité de l'algorithme de détection du contact, un algorithme de recherche sous forme d'arbre binaire a été implémenté dans Metafor. Cet algorithme permet de récupérer aisément les facettes sur laquelle nous devons effectuer la détection locale.

Je vous fournis aussi les références utilisées pour l'implémentation :

Détails d'implémentation

Les routines de parcours sur l'arbre se fait au moyen d'un appel à fonction récursif au lieu de l'utilisation d'une queue.

L'arbre se trouve sous forme d'un std::vector organisé d'un manière telle que les nœuds gauche et droite sont directement contigus.

La construction de l'arbre se fait au moyen d'une approche dite top-down. A partir du centre géométrique des objets, on définit un plan de partitionnement à partir duquel on sépare les objets de part et d'autre de ce plan pour former les nœuds intérieurs gauche et droite de l'arbre. On procède récursivement jusqu'à ce que nous n'ayons plus que deux objets à partitionner.

Chaque nœud de l'arbre possède un volume d'approximation (Bounding Volume), ce qui permet aisément de mettre à jour tous les volumes d'approximation à partir des feuilles de l'arbre vers la racine de l'arbre (Approche bottom-up), puisque les feuilles contiennent les entités géométriques. Au niveau des feuilles de l'arbre, on a le calcul d'un volume d'approximation et ensuite on a une union des volumes d'approximation pour les volumes pour les nœuds intermédiaires.

Finalement, les classes liées à la gestion d'un arbre des volumes d'approximation ont été implémentées sous forme de template.

Cas Test

Le système de recherche sous forme d'arbre s'active par la commande suivante :

Je vous indique ici les différentes performances observées avec quelques cas-tests de la batterie :

Finalement, il est très recommandé d'utiliser cet algorithme d'arbre lors d'un cas test de contact en défo-défo.

Etant donné la procédure de sélection d'une projection valide en trois dimensions ou deux dimensions, on peut observer une différence entre une execution avec arbre et sans arbre. La raison de cette différence réside dans la présence de tolérance pour effectuer ce choix.

Visualisation Graphique

J'ai ajouté la possibilité de voir les arbres dans Metafor. Je vous fournis ici quelques captures d'écran :

Extensions possibles

Il y a trois aspects sur lesquels on peut encore améliorer la recherche sous forme d'arbre pour la détection globale :

  • Parcourir/Mettre à jour l'arbre à l'aide d'une boucle parallélisée en utilisant l'outil TBB : pour se faire, il faudra surement réécrire la routine à l'aide d'une queue pour facilement pouvoir paralléliser;
  • Utiliser des volumes d'approximation d'un ordre supérieur à la boite (k-DOP);
  • Mettre à jour l'arbre sous forme de rotation/déplacement rigide dès que possible (pour le contact rigide déformable permettra de gagner du temps, car les boites seront calculées uniquement lors de la phase d'initialisation et déplacer ensuite par l'intermédiaire cette transformation géométrique). Ceci est facilement conceptuellement mais délicat à implémenter proprement dans Metafor.

Finalement, une autre manière d'accélérer le calcul des projections dans le cas de surface ou courbe de type NURBS est de proposer une approximation de la surface/la courbe à l'aide d'une triangularisation/segmentation et de construire un arbre sur cette approximation pour procéder aux calculs des projections.

Fichiers ajoutés/supprimés

[a]:
[r]:

Cas tests ajoutés/supprimés

[a]:
[r]:

gaëtan 2017/08/16 12:00

commit/2017/08_16.1502884280.txt.gz · Last modified: 2017/08/16 13:51 by wautelet

Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki