{"id":287,"date":"2022-12-01T10:18:01","date_gmt":"2022-12-01T09:18:01","guid":{"rendered":"https:\/\/lacuisine.tech\/fr\/?p=287"},"modified":"2022-12-01T10:29:57","modified_gmt":"2022-12-01T09:29:57","slug":"triangulation-3d-dun-trace-grease-pencil","status":"publish","type":"post","link":"https:\/\/lacuisine.tech\/fr\/triangulation-3d-dun-trace-grease-pencil\/","title":{"rendered":"Triangulation 3D d’un trac\u00e9 Grease Pencil"},"content":{"rendered":"\nVous l\u2019aurez compris, au F\u00e9es Sp\u00e9ciales, nous sommes f\u00e9rus de Grease Pencil, cet outil de dessin int\u00e9gr\u00e9 \u00e0 Blender. Non seulement il permet de dessiner et animer en 2D, mais il permet aussi de dessiner en 3D directement dans la sc\u00e8ne Blender. Pourquoi alors ne pas l\u2019utiliser pour dessiner des surfaces 3D ? En quelques gestes, nous pourrions ainsi cr\u00e9er des \u00e9l\u00e9ments de FX dans des animations 3D par exemple. Afin de r\u00e9pondre \u00e0 cette question, nous avons impl\u00e9ment\u00e9 un algorithme de triangulation \u00e0 partir d\u2019un trac\u00e9 grease pencil.\n\n\n
\n
\"\"<\/figure><\/div>\n\n\nThis article also exists in English<\/a><\/em>.\n\n\n\n\n\n\n
\n
\"\"<\/figure><\/div>\n\n\n\n

Exemple de courbe non plane dans une sc\u00e8ne 3D<\/em><\/p>\n\n\n\n\nEn fait, chaque objet grease pencil contient un maillage triangulaire qui sert de support pour le rendu, et qui est accessible depuis l\u2019API python.\n\n\n\n\n

\n
\n
\"\"<\/figure>\n<\/div>\n\n\n\n
\nCependant, ce maillage n\u2019est pas satisfaisant en termes de topologie : beaucoup de triangles d\u00e9g\u00e9n\u00e9r\u00e9s qui repr\u00e9sentent une g\u00e9om\u00e9trie parfois discontinue. Une des raisons est que cette triangulation se base uniquement sur les points du trac\u00e9, qui repr\u00e9sentent donc la bordure de la surface, ce qui l\u2019emp\u00eache de repr\u00e9senter une surface lisse dans le cas de courbes non planes.\n<\/div>\n<\/div>\n\n\n\n\nUne solution pour avoir des triangles plus r\u00e9guliers, nous pouvons ajouter des sommets dans chacune des faces de cette triangulation. En utilisant quelques op\u00e9rateurs Blender (beautify faces, triangles to quad..), la topologie peut \u00eatre l\u00e9g\u00e8rement am\u00e9lior\u00e9e. Ce n\u2019est souvent pas suffisant pour avoir un maillage d\u2019une bonne qualit\u00e9.\n\n\n\nNous pr\u00e9sentons ici une m\u00e9thode que nous avons impl\u00e9ment\u00e9e pour r\u00e9soudre ce probl\u00e8me. Cette m\u00e9thode n\u2019est pas nouvelle, et est inspir\u00e9e par la litt\u00e9rature scientifique cit\u00e9e dans le texte. Une telle m\u00e9thode a notamment \u00e9t\u00e9 utilis\u00e9e dans le cadre de la triangulation de r\u00e9seaux de courbes 3D [Stanko et al. 16]<\/a>.\n\n\n
\n
\"\"<\/figure><\/div>\n\n\n\n

Aper\u00e7u de la m\u00e9thode de triangulation 3D<\/em><\/p>\n\n\n\n\n\n

Rep\u00e8re local<\/h2>\n\n\n\n\nDans un premier temps, nous allons approximer un plan qui nous servira de support \u00e0 une triangulation 2D de base. Nous pouvons calculer le plan approximant au mieux les coordonn\u00e9es du trac\u00e9 en calculant les vecteurs propres de la matrice de covariance des coordonn\u00e9es. Pas de panique si vous n\u2019avez aucune id\u00e9e de ce que \u00e7a veut dire, la librairie numpy de python va faire ce calcul pour nous. Pour vous faire une id\u00e9e, la matrice de covariance des points du trac\u00e9 repr\u00e9sente les variations des coordonn\u00e9es des points du trac\u00e9 dans les diff\u00e9rentes directions de l\u2019espace. Les vecteurs propres de cette matrice forment un ensemble de 3 directions de l\u2019espace, orthogonales entre elles, et qui repr\u00e9sentent les directions dans lesquelles les coordonn\u00e9es des points varient du plus au moins. Le plan qui approxime au mieux les points du trac\u00e9 est normal \u00e0 la direction dans laquelle les points varient le moins. \n\n\n\n\n
 # Calcul du barycentre et coordonn\u00e9es centr\u00e9es<\/strong>\nbar = barycenter(verts)\nx = np.asarray([v - bar for v in verts])\n \n # Matrice de covariance et vecteurs propres<\/strong>\nM = np.cov(x.T)\neigenvalues,eigenvectors = np.linalg.eig(M) \n\n # Rep\u00e8re local\n # u : direction de plus grande variance des coordonn\u00e9es\n # n : direction de moindre variance des coordonn\u00e9es\n #     => normale du plan \n # v : vecteur orthogonal \u00e0 u et n<\/strong>\nu = Vector(eigenvectors[:,eigenvalues.argmax()])\nn = Vector(eigenvectors[:,eigenvalues.argmin()])\nv = n.cross(u)<\/code><\/pre>\n\n\n\n\nLes vecteurs (u,v,n) forment une base orthonorm\u00e9e de l\u2019espace. Avec le barycentre des points \u03a9 comme centre, nous pouvons d\u00e9finir un rep\u00e8re local associ\u00e9 \u00e0 cette base. 
Tout point de l\u2019espace d\u00e9fini par des coordonn\u00e9es globales (x,y,z) peut ainsi s\u2019exprimer en coordonn\u00e9es locales relative \u00e0 cette base \u00e0 l\u2019aide de la matrice de passage M=[u v n] et de la formule suivante.\n\n\n\n\n
\n
\n
\"\"<\/figure>\n<\/div>\n\n\n\n
\n
\"\"<\/figure>\n<\/div>\n<\/div>\n\n\n\n\n\n
Triangulation 2D<\/h2>\n\n\n\n\nA l\u2019aide de cette formule, nous pouvons calculer la projection de la courbe sur le plan sous forme de coordonn\u00e9es 2D, en prenant uniquement les deux premi\u00e8res coordonn\u00e9es (\u02dcx, \u02dcy) de chaque point dans le rep\u00e8re local. 
Nous calculons une triangulation 2D \u00e0 partir de ces donn\u00e9es en utilisant la biblioth\u00e8que Triangle<\/a> pour python, qui est bas\u00e9e sur un algorithme et un code C cr\u00e9\u00e9s par Jonathan Shewchuk <\/a>[Shewchuk 96]<\/a>. Elle peut \u00eatre simplement install\u00e9e avec pip :\n\n\n\n\n
pip install triangle<\/code><\/pre>\n\n\n\n\nComme d\u00e9crit dans la documentation<\/a>, la fonction de triangulation poss\u00e8de de multiples param\u00e8tres. Nous utilisons les param\u00e8tres -p<\/code>, -q<\/code>, et -a0.05<\/code>.\n\n\n\n\n
triangle.triangulate(strokes, 'pqa0.05')<\/code><\/pre>\n\n\n\n\nLe param\u00e8tre -p<\/code> signifie \u2018Planar Straight Line Graph\u2019, il permet de prendre en compte les formes concaves. Sans ce param\u00e8tre, la triangulation couvre l\u2019ensemble de l\u2019enveloppe convexe des points, comme ici :\n\n\n\n
\"\"\n\n
Triangulation sans le param\u00e8tre -p<\/strong><\/figcaption>\n\n<\/figure>\n\n\n\nLe param\u00e8tre -q<\/code> permet de maintenir les angles des triangles en dessous d\u2019un seuil de 20\u00b0. Il permet d\u2019\u00e9viter l\u2019apparition de triangles allong\u00e9s, presque d\u00e9g\u00e9n\u00e9r\u00e9s, comme ici :\n\n\n\n
\"\"\n\n
Triangulation sans le param\u00e8tre –<\/strong>q<\/figcaption>\n\n<\/figure>\n\n\n\nEnfin, le param\u00e8tre -a<\/code> permet de limiter l\u2019aire des triangles. Le seuil est choisi ici arbitrairement \u00e0 0.05, mais la valeur est \u00e0 ajuster selon la dimension de l\u2019objet ou de la sc\u00e8ne.\n\n\n
\n
\"\"<\/figure><\/div>\n\n\n\n
Vers un maillage 3D<\/h2>\n\n\n\n\nNous avons maintenant une triangulation en 2D, exprim\u00e9e dans le rep\u00e8re local du plan approxim\u00e9. Nous pouvons convertir ces coordonn\u00e9es dans le rep\u00e8re monde, gr\u00e2ce aux \u00e9quations vues pr\u00e9c\u00e9demment, et ainsi obtenir un maillage 3D plan. \n\n\n\nDans le cas o\u00f9 le trac\u00e9 initial est contenu dans un plan, alors ce maillage r\u00e9pond au probl\u00e8me pos\u00e9 : il est r\u00e9gulier et sa bordure correspond au trac\u00e9. Si au contraire le trac\u00e9 est \u2018gauche\u2019, c\u2019est-\u00e0-dire qu\u2019il n\u2019est pas contenu dans un plan, alors le maillage obtenu doit \u00eatre modifi\u00e9 afin que sa bordure corresponde au trac\u00e9, tout en conservant un maillage de bonne qualit\u00e9. En particulier, nous voudrions obtenir une surface lisse, sans discontinuit\u00e9s.\n\n\n\n\n
Surfaces Minimales<\/strong><\/h3>\n\n\n\n\nPlusieurs solutions \u00e0 ce probl\u00e8me existent, par cons\u00e9quent il nous faut d\u00e9finir un crit\u00e8re qui guidera la d\u00e9formation du maillage. Ici, nous utilisons un proc\u00e9d\u00e9 dit de minimisation du Laplacien, qui permet d\u2019obtenir une surface \u00e0 la courbure moyenne minimale, que l\u2019on appelle aussi surface minimale<\/a>.\n\n\n\nPour avoir une id\u00e9e plus visuelle, imaginez que le trac\u00e9 initial soit fait en fil de fer. Si vous plongez ce fil de fer dans une eau savonneuse, alors la membrane enveloppant alors votre fil de fer repr\u00e9sentera une surface minimale. Comme ici<\/a> par exemple.\n\n\n\n\n
Impl\u00e9mentation<\/h2>\n\n\n\n\nLa m\u00e9thode est d\u00e9crite plus en d\u00e9tail dans l\u2019article [Botsch and Sorkine 07]<\/a>. Nous vous proposons ici un r\u00e9sum\u00e9, en essayant de vulgariser au maximum la partie math\u00e9matique.\n\n\n\nNotre entr\u00e9e est un maillage 3D contenu dans un plan, qui se traduit par un ensemble de points de l\u2019espace  { vi<\/sub>=(xi<\/sub>, yi<\/sub>, zi<\/sub>) }i\u2208{0..n-1}<\/sub> et un ensemble de faces triangulaires. Notre but est de d\u00e9placer les points du maillage afin que sa bordure corresponde au trac\u00e9 3D du grease pencil tout en minimisant sa courbure moyenne. 
Ce probl\u00e8me est formul\u00e9 comme une minimisation des moindres carr\u00e9s. Ceci implique de d\u00e9finir un ensemble d\u2019inconnues x et un ensemble de contraintes lin\u00e9aires exprim\u00e9es sous forme de matrices A et b, afin de r\u00e9soudre l\u2019\u00e9quation Ax=b. Ici, nos inconnues sont l\u2019ensemble des d\u00e9placements di<\/sub>=(dxi<\/sub>,dyi<\/sub>,dzi<\/sub>) que l\u2019on doit appliquer aux sommets du maillage 3D pour obtenir la surface cible.\n\n\n
\n
\"\"<\/figure><\/div>\n\n\nLes matrices A et b d\u00e9finissent un ensemble de contraintes de la forme: a0<\/sub>k<\/sup>*d0<\/sub> + ... an-1<\/sub>k<\/sup>*dn-1<\/sub> = bk<\/sup><\/code>. Un syst\u00e8me de ce type peut \u00eatre r\u00e9solu \u00e0 l\u2019aide de la fonction numpy de r\u00e9solution aux moindres carr\u00e9s linalg.lstsq<\/a>, qui nous retourne les valeurs de x satisfaisant au mieux l\u2019\u00e9galit\u00e9 Ax=b. Nous pourrons ensuite calculer le maillage d\u00e9form\u00e9 en appliquant les d\u00e9placements obtenus sur chacun des sommets.
En pratique, l\u2019\u00e9galit\u00e9 Ax=b ne peut pas toujours \u00eatre r\u00e9solue, notamment car certaines contraintes peuvent \u00eatre en conflit. La m\u00e9thode des moindres carr\u00e9s renvoie en fait la valeur de x qui minimise \u2211k<\/sub>|| \u2211i<\/sub> ai<\/sub>k<\/sup> di<\/sub> -bk<\/sup> ||2<\/sup><\/code>.\n\n\n\nLa minimisation laplacienne est donc exprim\u00e9e par le biais des matrices A et b. Ces matrices doivent exprimer la contrainte de minimisation de la courbure moyenne<\/a> de la surface en chaque sommet du maillage. La courbure moyenne est approxim\u00e9e par la discr\u00e9tisation de l\u2019op\u00e9rateur de Laplace-Beltrami<\/a>, qui est bas\u00e9 sur le calcul de l\u2019aire de Voronoi relative \u00e0 chaque point du maillage (c\u2019est l\u2019aire du voisinage proche de chacun des sommets sur le maillage).\n\n\n\nCes contraintes sont exprim\u00e9es sous forme matricielle : \n\n\n\n\n
(-ks<\/sub> Ls<\/sub> + kb<\/sub> Ls<\/sub> M-1<\/sup> Ls<\/sub>) x = 0,<\/code><\/p>\n\n\n\n\no\u00f9 :
\u2013 ks<\/sub>, kb<\/sub> sont les poids d\u2019\u00e9tirements (stretch<\/em>) et de m\u00e9lange (blend<\/em>), dans notre impl\u00e9mentation, ils valent tous deux 0.5.
\u2013 M est une matrice diagonale qui contient les aires de Voronoi de chaque sommet du maillage,
\u2013 Ls<\/sub> est une matrice de coefficients {\u03c9ij<\/sub>} pour i\u2260j et {-\u2211 k\u2260i<\/sub> \u03c9ki<\/sub>} sur la diagonale,
\u2013 et \u03c9ij<\/sub> = 0.5*( cotan \u03b1ij<\/sub> + cotan \u03b2ij<\/sub> ) si (i, j) correspondent \u00e0 des sommets adjacents sur le maillage, avec ( \u03b1ij<\/sub>, \u03b2ij<\/sub> ) les angles oppos\u00e9s \u00e0 l\u2019ar\u00eate (i,j), et \u03c9ij<\/sub> = 0 sinon.\n\n\n\nN\u2019h\u00e9sitez pas \u00e0 vous r\u00e9f\u00e9rer \u00e0 l\u2019article pour plus de d\u00e9tails.\n\n\n\nCette \u00e9quation est une bonne base pour constituer un syst\u00e8me de moindres carr\u00e9s qui minimise la courbure moyenne d\u2019un maillage, en notant A= (-ks<\/sub> Ls<\/sub> + kb<\/sub> Ls<\/sub> M-1<\/sup> Ls<\/sub>), et b = 0. En r\u00e9solvant ce syst\u00e8me tel quel, le r\u00e9sultat sera probablement x=0, ce qui correspond \u00e0 un d\u00e9placement nul des sommets du maillage. En effet, le maillage initial \u00e9tant contenu dans un plan, il correspond \u00e0 une surface plane, donc de courbure moyenne 0 en tout point. En ajoutant une contrainte sur la bordure du maillage, nous pouvons contrebalancer la contrainte laplacienne et pousser le maillage \u00e0 sortir du plan pour coller au trac\u00e9 initial du bord.
La contrainte de bord peut \u00eatre ajout\u00e9e de deux mani\u00e8res diff\u00e9rentes au syst\u00e8me :\n\n\n\n1. Contrainte faible<\/strong>.
Une premi\u00e8re m\u00e9thode consiste \u00e0 ajouter des lignes aux matrices A et b pour exprimer de nouvelles contraintes de la forme : di<\/sub> = bi<\/sub> \u2013 vi<\/sub> , pour chaque sommet du maillage qui appartient au bord du maillage, en notant vi<\/sub> sont les coordonn\u00e9es du sommet dans la triangulation plane, et bi<\/sub> sont les coordonn\u00e9es du sommet correspondant sur le trac\u00e9 grease pencil.\n\n\n\n2. Contrainte forte<\/strong>.
Une autre m\u00e9thode consiste \u00e0 consid\u00e9rer les coordonn\u00e9es des sommets qui appartiennent au bord du maillage comme en dehors de l\u2019ensemble des inconnues, mais comme des constantes connues du syst\u00e8me. Dans ce cas, nous n\u2019avons pas besoin d\u2019ajouter de lignes aux matrices A et b, mais nous devons r\u00e9arranger les colonnes afin que tous les coefficients correspondants aux sommets du bord soient d\u00e9plac\u00e9s sur la partie droite de l\u2019\u00e9quation. De fait, apr\u00e8s cette manipulation, la matrice A contient moins de colonnes, le syst\u00e8me poss\u00e9dant moins d\u2019inconnues.\n\n\n\nNous avons impl\u00e9ment\u00e9 les deux m\u00e9thodes, et n\u2019avons pas observ\u00e9 de diff\u00e9rence notable au niveau de la performance de l\u2019op\u00e9ration, sur les exemples que nous avions. En th\u00e9orie, la deuxi\u00e8me m\u00e9thode devrait \u00eatre plus performante \u00e9tant donn\u00e9 que le syst\u00e8me \u00e0 r\u00e9soudre est plus petit que dans la premi\u00e8re m\u00e9thode. De plus, la contrainte forte garantit que les sommets du bord se trouvent effectivement sur le trac\u00e9 du grease pencil. \n\n\n\n\n
R\u00e9sultats<\/h2>\n\n\n\n
\n
\"\"<\/figure><\/div>\n\n\nLes r\u00e9sultats sont satisfaisants : pour la plupart des courbes, le maillage obtenu est r\u00e9gulier, la surface est lisse et le bord est toujours fid\u00e8le au trac\u00e9 grease pencil. A l’aide de modifieurs, il est possible ensuite d’ajouter de l’\u00e9paisseur et du biseau au r\u00e9sultat pour obtenir un \u00e9l\u00e9ment 3D pouvant s’int\u00e9grer dans une animation 3D, comme dans l’exemple suivant.\n\n\n
\n
\"\"<\/figure><\/div>\n\n
\n
\"\"<\/figure><\/div>\n\n\nDes limites apparaissent principalement lorsque la projection de la courbe sur le plan s\u2019auto-chevauche.\u00a0Dans ce cas, la r\u00e9gularit\u00e9 du maillage obtenu via la triangulation 2D est perdue, comme dans l’exemple ci-dessous.\n\n\n
\n
\"\"<\/figure><\/div>\n\n\nNotre algorithme ne g\u00e8re pas encore les trous dans les maillages. Au niveau de la performance, la partie la plus co\u00fbteuse de l\u2019algorithme est la minimisation Laplacienne. Il est donc important d\u2019effectuer cette \u00e9tape uniquement si la courbe n\u2019est pas contenue dans un plan.\u00a0\n\n\n\n\n
Comment se procurer le code ? <\/h2>\n\n\n\n\nLe code est disponible sous forme d\u2019add-on Blender en acc\u00e8s libre sur GitLab : https:\/\/gitlab.com\/lfs.coop\/blender\/gp-triangulation<\/a>. \n\n\n\nA noter que les impl\u00e9mentations de la triangulation et l\u2019optimisation laplacienne sont contenues dans le fichier laplacian.py<\/a> et par la fonction laplacian_triangulation<\/code> (son ex\u00e9cution n\u00e9cessite quelques fonctions du fichier utils.py<\/a>).\n\n\n\n\n
R\u00e9f\u00e9rences<\/h2>\n\n\n\n\n[Stanko et al. 16]<\/a> Stanko, T., Hahmann, S., Bonneau, G. P., & Saguin-Sprynski, N. (2016). Surfacing curve networks with normal control. Computers & Graphics<\/em>, 60<\/em>, 1-8.\n\n\n\n[Shewchuk 96]<\/a> Shewchuk, J. R. (1996, May). Triangle: Engineering a 2D quality mesh generator and Delaunay triangulator. In Workshop on Applied Computational Geometry<\/em> (pp. 203-222). Springer, Berlin, Heidelberg.\n\n\n\n[Botsch and Sorkine 07]<\/a> Botsch, M., & Sorkine, O. (2007). On linear variational surface deformation methods. IEEE transactions on visualization and computer graphics<\/em>, 14<\/em>(1), 213-230.\n","protected":false},"excerpt":{"rendered":"
Vous l\u2019aurez compris, au F\u00e9es Sp\u00e9ciales, nous sommes f\u00e9rus de Grease Pencil, cet outil de dessin int\u00e9gr\u00e9 \u00e0 Blender. Non seulement il permet de dessiner et animer en 2D, mais il permet aussi de dessiner en 3D directement dans la sc\u00e8ne Blender. Pourquoi alors ne pas l\u2019utiliser pour dessiner des surfaces 3D ? En quelques gestes, nous pourrions ainsi cr\u00e9er des \u00e9l\u00e9ments…<\/p>\n","protected":false},"author":6,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_coblocks_attr":"","_coblocks_dimensions":"","_coblocks_responsive_height":"","_coblocks_accordion_ie_support":""},"categories":[19,17,18],"tags":[],"_links":{"self":[{"href":"https:\/\/lacuisine.tech\/fr\/wp-json\/wp\/v2\/posts\/287"}],"collection":[{"href":"https:\/\/lacuisine.tech\/fr\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/lacuisine.tech\/fr\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/lacuisine.tech\/fr\/wp-json\/wp\/v2\/users\/6"}],"replies":[{"embeddable":true,"href":"https:\/\/lacuisine.tech\/fr\/wp-json\/wp\/v2\/comments?post=287"}],"version-history":[{"count":48,"href":"https:\/\/lacuisine.tech\/fr\/wp-json\/wp\/v2\/posts\/287\/revisions"}],"predecessor-version":[{"id":352,"href":"https:\/\/lacuisine.tech\/fr\/wp-json\/wp\/v2\/posts\/287\/revisions\/352"}],"wp:attachment":[{"href":"https:\/\/lacuisine.tech\/fr\/wp-json\/wp\/v2\/media?parent=287"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/lacuisine.tech\/fr\/wp-json\/wp\/v2\/categories?post=287"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/lacuisine.tech\/fr\/wp-json\/wp\/v2\/tags?post=287"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}