Metafor

ULiege - Aerospace & Mechanical Engineering

User Tools

Site Tools


commit:2017:01_09

This is an old revision of the document!


Commit 2017-01-09

Ce commit est pour l'efficacité et la robustesse des opérateurs de projection sur les courbes et sur les surfaces.

Robustesse Opération de Projection

Dans le cas de la projection sur une surface ou une courbe, le problème revient à minimiser une fonction distance.

Dans le cas d'une minimisation d'une fonction non linéaire, l'utilisation d'un line search exact est totalement inefficace d'où la formulation des conditions dites de Wolfe pour garantir une décroissance suffisante de la fonction objective et de sa courbure. Inexact Line Search Methods

Deux line search inexactes sont disponibles et implémentées :

Backtracking line search (Utiliser en général pour la résolution d'équation non linéaire) : il requiert juste l'évaluation de la fonction objective et dans notre cas ici, il faut juste être capable d'évaluer un point sur une surface/une courbe. On garantit que la fonction décroit suffisamment selon la direction obtenue par la matrice hessienne (Procédure de Newton Raphson).

More Thuente line search (State of the art) (Utiliser en général pour la minimisation d'une fonction non linéaire) : il requiert juste l'évaluation de la fonction objective et son gradient et dans notre cas ici, il faut juste être capable d'évaluer un point sur une surface/une courbe et les tangentes au même point. On garantit que la fonction décroit suffisamment selon la direction obtenue par la matrice hessienne (Procédure de Newton Raphson) et aussi que l'on se trouve dans la zone du minimum par un critère sur la courbure.

Finalement, j'ai du réécrire la procédure utilisée pour l'opération de projection, pour éviter de recalculer plusieurs fois les mêmes choses pour des raisons de performances.

Pour la projection sur les NURBS, il serait peut être intéressant de faire un BFGS pour calculer les projections, celà éviterait de calculer la matrice hessienne qui est très couteuse pour ce type de surface (Polynôme de degré relativement élevé en fonction de la complexité de la surface).

Modification de la matrice hessienne

Afin de continuer à utiliser la procédure de Newton-Raphson et toujours garantir une diminution de la fonction objective, j'ai implémenté une méthode qui rend la matrice définie positive tout en conservant une matrice bien conditionnée. L'idée est tout simple : on ajoute à la matrice initiale, un multiple de la matrice identité (Ceci s'apparente fortement aux méthodes dites “Trust Region”. Elle marche dans le cas d'une matrice définie négative et semi-définie positive. En général, il faut combiner cette méthode avec un backtracking line search et une méthode qui limite la taille de la correction (obligatoire !!) : en effet une division par un nombre proche de la précision machine donne un très grand nombre ! En général, pour une matrice de dimension supérieure à 2, il faut passer par une décomposition Cholesky spéciale qui donne une matrice définie positive, même si la matrice initiale ne l'est pas !

Résumé

Que soit avec l'une ou l'autre méthode, nous avons désormais une garantie de convergence des opérateurs de projection à condition que le point de départ soit suffisamment proche de l'extremum et l'absence de point singulier dans la définition de la surface ou de la courbe (tangente égale à zéro).

Projection Nurbs Surface

J'ai nettoyé l'interface pour le calcul des tangentes, normales, dérivées des tangentes afin d'uniformiser l'ensemble surtout lors du calcul d'un point en dehors du domaine de définition [0 1]x[0 1].

J'ai fait une correction dans le cas où on évalue une tangente en dehors du domaine de définition [0 1]x[0 1]. On fait une extrapolation selon la coordonnée intrinsèque de la surface en dehors du domaine de définition. En réécrivant les équations, j'ai garanti que les tangentes soient continues partout lors de cette extrapolation mais on observe une discontinuité de la dérivée seconde.

En faisant une recherche bibliographique, je me suis rendu compte que la littérature est très peu fournie à ce niveau-là alors que les logiciels de CAO proposent une extension des surfaces/courbes en dehors de leur domaine de définition. Dans le cas d'une NURBS (les fonctions d'interpolation sont définies par une fonction rationnelle polynomiale), on ne peut pas bêtement l'évaluer en dehors du domaine de définition, car nous pouvons avoir le dénominateur égal à zéro en certains points !

Dans le cas du cas test du tube, nous observons une singularité au niveau de la définition d'une tangente, car celle-ci vaut zéro. Ceci est normal vu la définition de la surface utilisée.

Projection Multiple

En 3D dans le cas d'une projection double, nous devons recalculer l'intersection du bord commun avec le plan contenant les deux projections sur les faces incidentes à ce bord. Une fois fait, nous réalisons à nouveau une projection sur une des deux faces incidentes pour récupérer les coordonnées intrinsèques de ce point. Il n'y avait pas de point de départ et nous passons par une grille. Désormais, on part du point de départ obtenu sur la projection obtenue sur la courbe.

Visualisation

J'ai ajouté la possibilité d'étendre les surfaces et les courbes en dehors du domaine [0 1]. Ceci permet de visualiser à quoi ressemble ces entités géométriques en dehors de leur domaine de définition. Il ne faut pas oublier que dans le cas des projections multiples, on étend le domaine à [-0.1 1.1].

On peut demander aussi à calculer les tangentes et les normales par la même occasion.

Cas Test

Afin de tester les nouveaux line search, j'ai ajouté trois cas-tests dans la libraire mtMath.

Fichiers ajoutés/supprimés

[a]:
[r]:

Cas tests ajoutés/supprimés

[a]:
[r]:

gaëtan 2017/01/09 10:32

commit/2017/01_09.1483957035.txt.gz · Last modified: 2017/01/09 11:17 by wautelet

Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki