Brevet FR3038254A1 — publié le 20170106

INRIA184 FRD Dispositif de traitement de données pour fabrication additive L'invention concerne le domaine de la texturisation et en particulier le domaine de l'impression en trois dimensions. L'application d'une texture à un objet est un domaine qui est mûr. Avec l'augmentation des résolutions disponibles, de nouveaux besoins se font sentir pour améliorer la qualité du plaquage des textures ainsi que le temps nécessaire, en particulier dans le cas de textures représentant un motif, avec lesquelles les irrégularités sont encore plus voyantes. Ces problématiques sont encore plus présentes dans le domaine de l'impression en trois dimensions. Actuellement, les possibilités de personnalisation des objets imprimés en trois dimensions sont assez limitées. En effet, il n'est possible d'utiliser qu'une seule matière pour l'impression, ce qui limite grandement la créativité. Pour contourner ce problème, des techniques ont été développées pour personnaliser les impressions en trois dimensions en appliquant un motif qui définit du vide et du plein dans l'objet imprimé. Mais la tenue mécanique de tels objets est complexe à garantir. L'invention vient améliorer la situation. À cet effet, l'invention propose un dispositif de traitement de données pour fabrication additive, comprenant une mémoire pour recevoir des données de voxels d'une surface d'un objet à fabriquer, chaque voxel indiquant un emplacement plein ou vide, un générateur capable de calculer un premier graphe à partir des données de voxels en définissant chaque voxel comme formant un noeud, en reliant entre eux par des arêtes les noeuds qui correspondent à des voxels respectifs qui partagent un coin, et en affectant à chaque arête un poids calculé à partir de la distance entre les centres des voxels correspondant aux noeuds qui lui sont associés, un extracteur agencé, pour définir un deuxième graphe en définissant des noeuds à partir d'un sous-ensemble de noeuds du graphe comprenant des noeuds correspondant à des voxels indiquant un emplacement plein, et pour relier entre eux les noeuds du deuxième graphe par des premières arêtes et des deuxièmes arêtes, une première arête étant définie comme représentant un chemin au sein du premier graphe entre deux noeuds du 3038254 2 deuxième graphe, chaque noeud du premier graphe reliant ces deux noeuds correspondant à un voxel indiquant un emplacement plein, et la somme des poids des arêtes du premier graphe reliant les deux noeuds associés à la première arête définissant le poids de cette première arête, une deuxième arête étant définie comme représentant 5 un chemin au sein du premier graphe entre deux noeuds du deuxième graphe qui ne peuvent pas être reliés par une première arête, un raidisseur agencé, pour déterminer une liste de deuxièmes arêtes dépassant un seuil sur la base d'une simulation physique d'un objet correspondant au deuxième graphe, pour redéfinir certaines au moins de ces deuxièmes arêtes en tant que premières arêtes, et pour redéfinir certains au moins des 10 voxels correspondant aux noeuds du premier graphe appartenant au voisinage de ces arêtes redéfinies comme correspondant à un emplacement plein, et un pilote agencé pour appeler le générateur, l'extracteur et le raidisseur pour produire des données d'objet à imprimer. 15 Ce dispositif est particulièrement avantageux car il permet d'offrir un objet dont la tenue mécanique est sûre, tout en offrant des possibilités esthétiques inaccessibles précédemment. Selon les variantes de réalisation, le dispositif pourra présenter une ou plusieurs des 20 caractéristiques suivantes : - l'extracteur détermine dans une première opération les premières arêtes en associant à chaque noeud du premier graphe correspondant à un voxel indiquant un emplacement plein un marqueur d'un noeud dudit sous-ensemble, les marqueurs étant propagés à partir de chacun des noeuds dudit sous-ensemble en choisissant, à partir d'un noeud 25 marqué, celui des noeuds qui lui est directement relié par une arête dans le premier graphe, qui correspond à un voxel indiquant un emplacement plein et dont l'arête présente le poids le plus faible, une première arête étant créée lorsque la propagation implique le marquage d'un noeud présentant déjà un marqueur d'un noeud dudit sous-ensemble, 30 - après la première opération, l'extracteur détermine les deuxièmes arêtes en associant à chaque noeud du premier graphe un marqueur d'un noeud dudit sous-ensemble, les marqueurs étant propagés à partir de chacun des noeuds dudit sous-ensemble en 3038254 3 choisissant, à partir d'un noeud marqué, celui des noeuds qui lui est directement relié par une arête dans le premier graphe, dont l'arête présente le poids le plus faible, et qui n'appartient pas à une première arête, une deuxième arête étant créée lorsque la propagation implique le marquage d'un noeud présentant déjà un marqueur d'un noeud 5 dudit sous-ensemble, - le raidisseur exécute une boucle récursive en a) simulant par éléments finis à partir du deuxième graphe un champ de contrainte pour chacune des arêtes du deuxième graphe, b) déterminant une liste de secondes arêtes présentant une contrainte supérieure 10 à un seuil de contrainte, c) sélectionnant la seconde arête de la liste présentant la plus grande contrainte en première arête, d) redéfinissant cette seconde arête en tant que première arête si elle est à une distance choisie en termes de poids de la dernière arête redéfinie dans la boucle 15 en cours, et en répétant l'opération c) sinon, e) recommençant la boucle en a) lorsque la liste ne contient plus d'arête, jusqu'à ce que la boucle ne redéfinisse plus aucune arête, - le raidisseur exécute une boucle en a) déterminant un ratio entre la distance en termes de poids entre les noeuds de 20 chaque deuxième arête et la distance euclidienne entre ces mêmes noeuds, b) redéfinissant chaque seconde arête dont le ratio supérieur est à un seuil choisi en tant que première arête, - la mémoire reçoit en outre des données de surface en trois dimensions (22), des données de projection et des données de motif, et le dispositif comprend en outre un 25 trieur capable de sélectionner pour un voxel d'entrée des voxels entourant le voxel d'entrée qui correspondent aux données de surface en trois dimensions, un estimateur capable de calculer une valeur de similarité entre un premier voxel associé à de premières données de projection et un second voxel associé à de secondes données de projection en calculant la projection des données de surface en trois dimensions 30 associées au premier voxel et des données de surface en trois dimensions associées au deuxième voxel, respectivement sur une première surface définie par les premières données de projection et sur une deuxième surface définie par les deuxièmes données de 3038254 4 projection sur lesquelles les données de motif sont plaquées, et en calculant une valeur tirée de la différence entre la projection du premier voxel sur la première surface et la deuxième surface d'une part, et de la différence entre la projection du deuxième voxel sur la première surface et la deuxième surface d'autre part, un sélectionneur capable, 5 pour un voxel donné et à partir d'un jeu de données de projection, de déterminer celles des données de projection dudit jeu qui indiquent la meilleure similarité avec des voxels voisins du voxel donné, à partir d'une valeur tirée des valeurs de similarité obtenues en appelant l'estimateur de manière répétée avec d'une part le voxel donné comme premier voxel et des données de projection du jeu comme premières données de projection et 10 d'autre part avec certains au moins des voxels tirés de l'appel du trieur avec le premier voxel en tant que deuxième voxel, et des données de projection qui leur sont associées comme deuxièmes données de projection, et pour associer au voxel donné les données de projection déterminées, un propagateur capable, à partir d'un voxel d'une résolution donnée et de données de projection qui lui sont associées, de définir une pluralité de 15 voxels de résolution supérieure à la résolution donnée, et pour associer à certains au moins de cette pluralité de voxels les données de projection associées au voxel de résolution donnée, un pilote agencé pour appeler le propagateur avec des données de surface en trois dimensions, un voxel et des données de projection associées, et pour appeler le sélectionneur avec certains au moins de la pluralité de voxels résultante 20 auxquels sont associées des données de projection en tant que voxel donné, ainsi qu'avec un jeu de données de projection comprenant d'une part les données de projection associées à la pluralité de données de voxels résultante, et d'autre part une quantité non nulle d'autres données de projection, le pilote étant en outre agencé pour répéter l'appel du propagateur avec certains au moins des voxels associés aux données 25 de projection déterminées par le sélectionneur, ainsi que l'appel du sélectionneur sur certains au moins de la pluralité de voxels résultante jusqu'à atteindre une résolution choisie, - l'estimateur détermine la valeur tirée de la différence entre la projection d'un voxel sur la première surface et sur la deuxième surface à partir de la différence de texture 30 résultant du plaquage des données de motif sur la première surface et sur la deuxième surface pour ces projections, 3038254 5 - l'estimateur détermine la valeur de similarité en outre à partir d'une valeur tirée de la valeur de l'angle formé par la normale au plan défini par les données de surface en trois dimensions d'une part, et par la normale au plan de projection d'autre part, - la valeur de similarité est strictement positive et indique une similarité d'autant 5 meilleure que la valeur de similarité est faible, - le propagateur associe certains au moins des voxels de la pluralité de voxels de résolution supérieure avec des données de projection choisies aléatoirement, - les données de projection comprennent un identifiant de surface choisi parmi un jeu de plans et des données de transformation indiquant une translation et/ou une rotation du 10 repère de la surface désignée par l'identifiant de surface pour le plaquage des données de motif, - les données de projection sont indépendantes des données de surface en trois dimensions, - la surface définie par les données de projection est un plan, 15 - les données de surface en trois dimensions associées à un voxel donné comprennent une moyenne des normales d'une portion de surface associée au voxel donné, - les données de motif sont de nature stochastique et répétitive, - les données de voxels déterminées par le pilote sont utilisées par le générateur, - le pilote est appelé avec les données de voxels modifiées par le raidisseur, 20 - pour les données de voxels modifiées par le raidisseur, le pilote appelle le sélectionneur de manière à ne sélectionner que des données de projection telles que les données de voxels concernées indiqueront un emplacement plein après traitement, et - le raidisseur et le pilote sont appelés en boucle jusqu'à ce que le raidisseur ne modifie plus de données de voxels. 25 D'autres caractéristiques et avantages de l'invention apparaîtront mieux à la lecture de la description qui suit, tirée d'exemples donnés à titre illustratif et non limitatif, tirés des dessins sur lesquels : - la figure 1 représente un diagramme schématique d'un dispositif selon l'invention, 30 - la figure 2 représente un exemple de mise en oeuvre d'une fonction par le trieur de la figure 1, 3038254 6 - la figure 3 représente un exemple de mise en oeuvre d'une fonction par l'estimateur de la figure 1, - la figure 4 représente un exemple de mise en oeuvre d'une fonction par le sélectionneur de la figure 1, 5 - la figure 5 représente un exemple de mise en oeuvre d'une fonction par le propagateur de la figure 1, - la figure 6 représente un exemple de mise en oeuvre d'une fonction par le pilote de la figure 1, - la figure 7 représente un exemple de mise en oeuvre du dispositif de la figure 1, 10 - la figure 8 représente un exemple de mise en oeuvre d'une fonction par l'extracteur de la figure 1, - la figure 9 représente un exemple de mise en oeuvre d'une fonction par le raidisseur de la figure 1, et - la figure 10 représente un exemple de mise en oeuvre d'une variante d'une fonction par 15 le sélectionneur de la figure 1, lors d'une boucle spécifique. Les dessins et la description ci-après contiennent, pour l'essentiel, des éléments de caractère certain. Ils pourront donc non seulement servir à mieux faire comprendre la présente invention, mais aussi contribuer à sa définition, le cas échéant. 20 La présente description est de nature à faire intervenir des éléments susceptibles de protection par le droit d'auteur et/ou le copyright. Le titulaire des droits n'a pas d'objection à la reproduction à l'identique par quiconque du présent document de brevet ou de sa description, telle qu'elle apparaît dans les dossiers officiels. Pour le reste, il 25 réserve intégralement ses droits. La figure 1 représente un diagramme schématique d'un dispositif 2 selon l'invention. Le dispositif 2 comprend une mémoire 4, un trieur 6, un estimateur 8, un sélectionneur 10, un propagateur 12, un pilote 14, un générateur 16, un extracteur 18, et un raidisseur 20. 30 Dans le cadre de l'invention, la mémoire 4 peut être tout type de stockage de données propre à recevoir des données numériques : disque dur, disque dur à mémoire flash 3038254 7 (SSD en anglais), mémoire flash sous toute forme, mémoire vive, disque magnétique, stockage distribué localement ou dans le cloud, etc. Les données calculées par le dispositif peuvent être stockées sur tout type de mémoire similaire à la mémoire 2, ou sur celle-ci. Ces données peuvent être effacées après que le dispositif ait effectué ses 5 tâches ou conservées. Les données stockées dans la mémoire 4 sont de plusieurs natures. Ainsi, la mémoire 4 reçoit des données de surface en trois dimensions 22, des données de motif 24, et des données de travail 26. 10 Les données de surface en trois dimensions 22 décrivent l'objet sur lequel on souhaite appliquer une texture. Ces données peuvent être directement utilisables, c'est-à-dire avoir déjà fait l'objet d'une voxelisation, ou être des données brutes. Dans ce cas, un élément non représenté pourra réaliser la voxelisation. La voxelisation n'étant pas 15 l'objet de l'invention, il sera considéré dans la suite que les données de surface en trois dimensions 22 ont déjà fait l'objet d'une voxelisation. Dans l'exemple décrit ici, les données de surface en trois dimensions 22 contiennent pour chaque voxel la moyenne des normales de la surface de l'objet associé à ce voxel. En variante, les données de surface en trois dimensions 22 pourraient contenir les données de la surface en tant que 20 telle, ou toutes autres données qui permettent de décrire la portion de la surface d'un objet qui est associée à un voxel. Les données de surface en trois dimensions 22 permettent donc de définir l'objet par des voxels associés à des portions de la surface de 1 ' obj et. 25 Les données de motif 24 représentent le motif avec lequel on souhaite texturer les données de surface en trois dimensions 22. Dans l'exemple décrit ici, le but est de produire un motif de type « noir et blanc », qui représente du plein et du vide dans l'objet en trois dimensions à imprimer. Pour cela, les données de motif 24 peuvent directement définir un motif binaire. Lorsque les données de motif 24 ne sont pas de 30 type binaire, elles peuvent faire l'objet d'un traitement spécifique à cette fin. Enfin, dans le cas où il n'est pas recherché de produire un objet en trois dimensions composé de vide et de plein, les données de motifs 24 peuvent être colorisées afin de texturer 3038254 8 l'objet en couleurs, par exemple pour une impression tridimensionnelle multi-couleurs. Les données de motifs 24 peuvent optionnellement définir un relief sur les parties pleines. 5 Les données de travail 26 comprennent toutes les données servant à réaliser les traitements de données selon l'invention. Ces données incluent les données associant les données de surface en trois dimensions aux données définissant les voxels, des données de projection, des données de valeur de similarité et d'autres valeurs décrites dans la suite. Dans l'exemple décrit ici, les données de projection définissent d'une part un plan 10 de projection (c'est-à-dire un couple de vecteurs non colinéaires), et d'autre part une transformation dans ce plan. Ainsi, les données de motif 24 seront transformées dans un plan selon les données de transformation de ce plan pour texturer ce dernier, puis le centre du voxel concerné est 15 projeté et peut recevoir une texture associée à sa projection dans le plan texturé. Il est possible à partir d'un nombre limité de plans (26 dans l'exemple décrit ici) et d'un certain nombre de transformations de définir un très grand nombre de plans de projection possibles. Une fois les données de projection ainsi définies, il s'agit donc de choisir les meilleures paires plan/transformation pour chaque voxel. En variante, les 20 données de motif 24 peuvent être plaquées sur la portion des données de surface correspondant au voxel, et cette surface texturée peut être projetée sur le plan puis transformée selon les données de transformation. Dans certaines variantes, il est possible d'utiliser d'autres surfaces de projection qu'un 25 plan, comme des cylindres ou des sphères, ou toute autre surface qui pourra être avantageuse sur certaines géométries d'objet. Bien que l'exemple décrit ici utilise des plans comme surface de projection, il est possible d'utiliser d'autres surfaces de projection comme des cylindres ou des sphères 30 selon les géométries des objets. 3038254 9 Le trieur 6, l'estimateur 8, le sélectionneur 10, le propagateur 12, le pilote 14, le générateur 16, l'extracteur 18 et le raidisseur 20 sont des éléments accédant directement ou indirectement à la mémoire 4. Ils peuvent être réalisés sous la forme d'un code informatique approprié exécuté sur un ou plusieurs processeurs. Par processeurs, il doit 5 être compris tout processeur adapté au calcul de projection de textures sur des plans et de traitements liés aux voxels. Un tel processeur peut être réalisé de toute manière connue, sous la forme d'un microprocesseur pour ordinateur personnel, d'une puce dédiée de type FPGA ou SoC (« system on chip » en anglais), d'une ressource de calcul sur une grille, d'un microcontrôleur, ou de toute autre forme propre à fournir la 10 puissance de calcul nécessaire à la réalisation décrite plus bas. Un ou plusieurs de ces éléments peuvent également être réalisés sous la forme de circuits électroniques spécialisés tel un ASIC. Une combinaison de processeur et de circuits électroniques peut également être envisagée. 15 Comme mentionné plus haut, l'invention réalise une bonne texturisation en trouvant les bons couples plans/transformation à appliquer à chaque élément des données de surface en trois dimensions (voxels) et aux données de motifs. Plus précisément, l'invention applique une méthode par descente de résolution pour déterminer ces couples. 20 Pour cela, il est procédé en considérant que le problème est résolu pour une résolution donnée, et que l'on va chercher à résoudre ce même problème pour une résolution supérieure, c'est-à-dire dont le grain est plus fin. Pour cela, dans un premier temps, le résultat de la résolution donnée est propagé à la résolution supérieure, en découpant chacun des voxels de la résolution donnée en voxels de résolution supérieure, et en 25 appliquant à ces voxels la solution trouvée pour la résolution donnée. Puis, le problème est résolu en optimisant les couples plan/transformation ainsi affectés à la résolution supérieure. Pour cela, chaque voxel de la résolution supérieure est testé avec tous les couples plan/transformation connus pour la résolution donnée, et une valeur de similarité est déterminée en fonction des couples plan/transformation des voisins de ce 30 voxel. Finalement, chaque voxel adopte le couple plan/transformation qui indique la meilleure similarité avec ses voisins pour définir la solution pour la résolution supérieure. 3038254 10 Ces opérations sont réalisées par le trieur 6 dont le rôle est de sélectionner les voxels qui sont les voisins d'un voxel donné, l'estimateur 8 dont le rôle est de calculer une valeur de similarité entre deux voxels et leur combinaison plan/transformation associée, le sélectionneur 10 qui utilise le trieur 6 et l'estimateur 8 pour déterminer la meilleure 5 combinaison plan/transformation pour un voxel donné, le propagateur 12 qui propage la solution d'une résolution donnée à une résolution supérieure, et le pilote 14, qui active sélectivement le sélectionneur 10 et le propagateur 12 pour propager le résultat de résolution en résolution, et pour appeler le sélectionneur 10 sur les voxels résultants afin de calculer la solution pour chaque résolution supérieure. 10 Ces opérations sont décrites en rapport avec les figures 2 à 6. Une fois que la résolution souhaitée est obtenue, la projection des voxels correspondant aux données de surface sur les couples plan/transformation combinés aux données de 15 motifs 24 produit des données de résultat 28. Ensuite, le générateur 16, l'extracteur 18 et le raidisseur 20 traitent les données de résultat 28 afin de rendre la structure physique correspondante stable d'un point de vue mécanique. 20 Ces opérations sont décrites en rapport avec les figures 7 à 9. Comme cela apparaît, les opérations des figures 2 à 6 et 7 à 9, bien que synergiques pour fournir un dispositif qui part de données de surface et de données de motif pour 25 donner un objet à imprimer en trois dimensions de nature originale, sont assez indépendantes les unes des autres. Ainsi, les figures 2 à 6 décrivent un dispositif original pour produire des données de motif plaqué avantageux, tandis que les figures 7 à 9 décrivent un dispositif original pour produire un objet à imprimer en trois dimensions qui est mécaniquement solide. 30 3038254 11 Dans les figures décrites ci-dessous, une variable dont le nom est tout en majuscule désigne dans la majorité des cas une liste contenant plusieurs éléments, tandis qu'une variable dont le nom est en minuscule désigne un élément seul. 5 La figure 2 représente un exemple d'une fonction mise en oeuvre par le trieur 6 pour déterminer les voxels voisins d'un voxel donné. Dans l'exemple décrit ici, un voxel est dit voisin d'un autre lorsqu'il est inclus dans un cube dont l'arête mesure cinq voxels et dont le centre est l'autre voxel. En d'autres termes, si on définit les voxels par des coordonnées de type (x ;y ;z) où x, y et z sont des multiples d'une dimension de voxel, 10 deux voxels de coordonnées (xl ; yl ; zl) et (x2 ; y2; z2) sont voisins lorsque xl-x2, yl-y2 et zl-z2 ont une valeur absolue inférieure ou égale à 2. Cependant, seuls les voxels qui correspondent à des données de surface 22 sont intéressants. Le trieur 6 commence dans une opération 260 avec des données de surface en trois 15 dimensions 0, une variable de taille de voisinage n s, un voxel d'entrée v et une liste de voisins N initialisée à 0 (c'est-à-dire vide). Comme on l'a vu plus haut, dans le cadre de l'exemple décrit ici, la variable de taille de voisinage n s a pour valeur 5, pour désigner un voisinage en forme de cube de longueur 5 voxels. En variante, le voisinage pourrait avoir une forme différente, ainsi que des dimensions différentes. 20 Dans une opération 210, une fonction Ngb() est appelée avec le voxel d'entrée v, et la taille de voisinage n s comme variables. La fonction Ngb() sélectionne tous les voxels qui entourent le voxel v dans un cube de dimension n s et centré sur le voxel v, et les stocke ensemble dans la liste P. Comme on le verra par la suite, les voxels qui sont 25 associés à des données de surface 22 sont associés à des données de projection 26. Dans l'exemple décrit ici, la liste P reçoit à la fois les voxels voisins, mais également les données de projection 26 qui leur sont associées. En variante, la correspondance entre ces voxels et les données de projection correspondantes sont maintenues en dehors de la liste P. 30 3038254 12 La liste P contient tous les voisins du voxel v, y compris les voxels qui ne correspondent pas aux données de surface 22. Par conséquent, il ne sert à rien de conserver ces voxels, puisqu'ils ne peuvent pas servir à projeter les données de motif 24. 5 Pour cela, une boucle est lancée dans une opération 226, dans laquelle la liste P est dépilée dans un couple (x ;p dx) qui reçoit le premier voxel de la liste P ainsi que les données de projection 26 qui lui sont associées. Dans une opération 230, les données de projection p dx sont testées : si elles sont vides, cela signifie que le voxel x ne correspond pas à des données de surface 22, et inversement. Ainsi, si les données de 10 projection p dx sont présentes, alors le voxel x et ses données de projection p dx sont entrées dans la liste N dans une opération 240. Ensuite, ou lorsque le voxel x n'est pas associé à des données de surface 22, la boucle reprend avec l'opération 226. La boucle se termine lorsque la liste P est vidée, et la liste N est retournée dans une opération 250. 15 La figure 3 représente un exemple d'une fonction mise en oeuvre par l'estimateur 8 pour calculer une valeur de similarité entre un premier voxel vl auquel sont associées des premières données de projection p dl, et un deuxième voxel v2 auquel sont associées des deuxièmes données de projection p d2. 20 Les travaux de la Demanderesse l'ont amenée à considérer que la similarité entre deux voxels s'apprécie au fait que leurs projections sur les plans associés respectivement aux premières et aux deuxièmes données de projection sont assez similaires. Dit autrement, si l'on projette les données de motifs plaquées sur les données de 25 surface 22 du premier voxel d'une part avec les premières données de projection et d'autre part avec les deuxièmes données de projection, les textures résultantes doivent être similaires, et il en va de même avec le deuxième voxel. Ainsi, dans une opération 300, l'estimateur 8 reçoit un premier voxel vl, un deuxième 30 voxel v2, des premières données de projection p dl, des deuxièmes données de projection p d2, les données de motif t, les données de surface en trois dimensions 0, et une variable de valeur de similarité initialisée à 0. 3038254 13 Dans une opération 310, deux textures tl 1 et t12 sont calculées au moyen d'une fonction Proj(), de sorte que : - la texture tl 1 reçoit la texture de la projection du centre du premier voxel vl sur le plan défini par les premières données de projection p dl et texturé selon ces dernières 5 avec les données de motif 24, et - la texture t12 reçoit la texture de la projection du centre du premier voxel vl sur le plan défini par les deuxièmes données de projection p d2 et texturé selon ces dernières avec les données de motif 24. 10 Ensuite, ou en parallèle selon les variantes, dans une opération 312, deux textures t21 et t22 sont calculées au moyen d'une fonction Proj(), de sorte que : - la texture t21 reçoit la texture de la projection du centre du deuxième voxel v2 sur le plan défini par les premières données de projection p dl et texturé selon ces dernières avec les données de motif 24, et 15 - la texture t22 reçoit la texture de la projection du centre du deuxième voxel v2 sur le plan défini par les deuxièmes données de projection p d2 et texturé selon ces dernières avec les données de motif 24. Enfin, dans une opération 330, la valeur de similarité retournée d est calculée comme la 20 somme de la différence entre les textures tl 1 et t12 d'une part et entre les textures t21 et t22 d'autre part. Dans l'exemple décrit ici, la différence entre les textures est calculée au moyen d'une fonction L2() qui calcule la norme euclidienne de la différence de couleur pixel par pixel des textures respectives. 25 La figure 4 représente un exemple d'une fonction mise en oeuvre par le sélectionneur 10 pour déterminer les données de projection qui sont les plus adaptées pour un voxel donné compte tenu de son entourage. Pour cela, le sélectionneur 10 reçoit dans une opération 400 le voxel v concerné, les 30 données de projection p dv qui lui sont associées, un jeu de données de projection pouvant améliorer la situation P D, les données de motif t, les données de surface en trois dimensions 0, et une variable de valeur de meilleure similarité dm initialisée à 0. 3038254 14 Dans une première boucle, la similarité entre le voxel v et son voisinage est calculée pour les données de projection p dv qui lui sont associées. Ainsi, dans une opération 405, le sélectionneur 10 appelle le trieur 6 qui stocke le résultat dans une liste N. 5 Ensuite, une boucle est effectuée dans laquelle la liste N est dépilée dans une opération 410. Ensuite, dans une opération 415, le sélectionneur 10 appelle l'estimateur 8 avec d'une part le voxel v et ses données de projection p dv associées, et d'autre part chaque voxel voisin x dépilé et ses données de projection associées p dx. La variable de meilleure similarité dm reçoit à chaque fois la valeur de similarité ainsi 10 calculée. Lorsque la liste N est vide, la variable de meilleure similarité dm a été initialisée avec la somme des valeurs de similarité entre le voxel donné avec ses données de projection associées p dv et ses voisins avec leurs données de projection associées. 15 Ensuite, le sélectionneur 10 initialise une autre boucle dans laquelle chacune des données de projection du jeu de données de projection P D vont être appliquées au voxel donné v, pour déterminer si elles constituent une meilleure correspondance avec les voxels du voisinage du voxel v et leurs données de projection associées. 20 Pour cela, une variable de valeur de similarité d est initialisée à 0 dans une opération 426, puis le jeu P D est dépilé dans une opération 425. Ensuite, la même boucle que pour les opérations 410 et 415 est réalisée avec les opérations de dépilage 430 et de calcul de la similarité 435 entre le voxel donné v et les voxels de son 25 voisinage. Cependant, dans l'opération 435, le voxel v n'est pas appelé avec les données de projection p dv qui lui sont associées, mais avec les données de projection p dy qui ont été dépilées dans l'opération 425. Ensuite, dans une opération 440, les valeurs d et dm sont comparées. Si d est inférieure 30 à dm, cela signifie que les données de projection p dy, associées au voxel v, sont plus proches des voxels du voisinage du voxel v que les données de projection p dv. Dans ce cas, la valeur dm reçoit la valeur d comme nouvelle valeur de meilleure similarité dans 3038254 15 une opération 445, et les données de projection p dv reçoivent les données de projection p dy dans une opération 450. Ainsi, le couple dm et p dv contient en permanence la valeur de meilleure similarité entre le voxel v et les voxels de son voisinage, ainsi que les données de projection correspondantes. Ensuite, ou si d est 5 supérieure à dm, la boucle de dépilage du jeu P D reprend avec l'opération 426 et la mise à zéro de la variable d. Enfin, lorsque le jeu P D est vide, le sélectionneur 10 retourne les données de projection p dv qui correspondent le mieux au voxel v compte tenu de son voisinage. 10 De nombreuses variantes sont directement envisageables, comme la réalisation des opérations 445 et 450 en parallèle, la parallélisation des boucles de calcul de la valeur de similarité. De plus, certaines boucles de calcul de la valeur de similarité pour des données de projection p dy différentes pourraient être également réalisées en parallèle, et le meilleur candidat sélectionné à la fin. 15 Par ailleurs, la Demanderesse a identifié le fait que la valeur de similarité entre le voxel donné et son voisinage pour des données de projection données peut optionnellement dépendre d'une valeur supplémentaire, qui découle de l'angle formé entre la normale au plan défini par les données de projection données et la normale aux données de surface 20 en trois dimensions associées au voxel donné. En effet, si cet angle est grand, la projection des données de motif peut être fortement distordue, malgré une bonne similarité avec les voxels du voisinage. Ainsi, après le calcul de la similarité avec les voisins, une valeur tirée du produit scalaire de la normale aux données de surface en trois dimensions associées à v avec la normale au plan des données de projection peut 25 être ajoutée. La Demanderesse a également identifié le fait que la valeur de similarité entre le voxel donné et son voisinage pour des données de projection données peut optionnellement dépendre d'une position dans le motif, pour encourager ou décourager l'utilisation de 30 certaines portions du motif Ceci peut par exemple être utilisé lorsque le motif est répété sur le plan de projection, pour empêcher des discontinuités visuelles dues aux jonctions entre les bords du motif d'apparaître sur la surface. Les voxels qui sélectionnent une 3038254 16 projection faisant apparaître cette portion du motif sont pénalisés par un accroissement des valeurs de similarité. La figure 5 représente un exemple d'une fonction mise en oeuvre par le propagateur 12 5 pour propager la solution d'une résolution donnée à une résolution supérieure. Dans une opération 500, le propagateur 12 reçoit un voxel d'entrée v, des données de projection associées p dv, des données de surface en trois dimensions 0, une taille d'échantillonnage de résolution s, et une liste de voxels de résolution supérieure V 10 initialisée à O. Dans une opération 510, le propagateur 12 appelle un fonction Up() avec le voxel v et la taille d'échantillonnage s. La fonction Up() renvoie une liste X de voxels de résolution supérieure, selon la taille d'échantillonnage s. Dans l'exemple décrit ici, la taille 15 d'échantillonnage a pour valeur 2, de sorte que la liste X contient 8 voxels qui correspondent ensemble au voxel y. Ensuite, le propagateur 12 exécute une boucle dans laquelle les voxels de la liste X sont dépilés dans une opération 526, puis testés dans une opération 525 pour déterminer si 20 ces voxels correspondent à des données de surface en trois dimensions. Si ce n'est pas le cas, alors le voxel est stocké sans données de projection associées dans la liste V dans une opération 540. Dans le cas contraire, le voxel est stocké avec les données de projection p dv dans la liste V dans une opération 550. Enfin, lorsque la liste X est vide, le propagateur 12 retourne la liste V dans une opération 560. 25 En variante, l'opération 550 pourrait introduire du bruit améliorant la variété en affectant de manière aléatoire des données de projection distinctes des données de projection p dv à certains au moins des voxels de résolution supérieure qui correspondent à des données de surface en trois dimensions. En variante, la variété n'est 30 pas ajoutée de manière aléatoire, mais de manière déterministe. 3038254 17 La figure 6 représente un exemple d'une fonction mise en oeuvre par le pilote 14 pour calculer les données de résultat 22 à partir des données de surface en trois dimensions 22, des données de motifs 24 et d'un jeu de données de projection. 5 Dans une opération 600, le pilote 14 reçoit ces données ainsi que le niveau de résolution r recherché, la taille d'échantillonnage s et initialise une variable de boucle de résolution i à 0. Dans une opération 605, le pilote 14 exécute une fonction Init() pour lancer les 10 opérations. Cette fonction a pour rôle de déterminer le premier voxel de résolution la plus grossière qui englobe les données de surface en trois dimensions, ainsi que les données de projection correspondantes. Dans l'exemple décrit ici, il n'y a qu'un seul premier voxel, mais il pourrait y en avoir plusieurs. De plus, les données de projection associées à ce premier voxel sont choisies de manière aléatoire. En variante, la fonction 15 Init() pourrait calculer ces données de projection. Ensuite, le pilote 14 entame une série de boucles d'indice i jusqu'à ce que la résolution r soit atteinte (opération 610). Dans chaque boucle, une liste Z associant des voxels et des données de projection est initialisée à 0 dans une opération 615. Ensuite, la liste de 20 voxels de résolution correspondant à l'itération précédente V est dépilée dans une opération 626. Chaque voxel x et ses données de projection p dx sont ensuite propagées en appelant le propagateur 12 dans une opération 625 et la liste résultante est stockée dans une liste W. 25 Le jeu de données de projection P D utilisé pour faire fonctionner le sélectionneur est alors initialisé à 0 dans une opération 630, et une boucle parcourt la liste W avec une opération 635 et une opération 640 afin de remplir la liste P D avec les données de projection associées aux voxels de la liste W. 30 Ensuite, dans une opération 645, une fonction Rand() ajoute un nombre choisi de données de projection à la liste P D afin de favoriser l'exploration de nouvelles 3038254 18 solutions. Ici encore, la variété peut ne pas être ajoutée de manière aléatoire, mais de manière déterministe. Enfin, la liste W est parcourue par une boucle, à partir d'une opération 650. Le 5 sélectionneur 10 est appelé dans une opération 655 avec chaque voxel de la liste W afin de trouver les meilleures données de projection p dy de la liste P D compte tenu de son voisinage. Le résultat est stocké dans la liste Z qui constitue les données de résultat 22 pour la résolution d'indice courant i. 10 Lorsque toute la liste V a été propagée et optimisée, elle est mise à jour dans une opération 665 avec la liste Z résultante, qui représente la solution pour la résolution d'indice i, puis l'indice i est incrémenté dans une opération 670. On notera qu'afin d'explorer tous les possibles et d'enrichir l'exploration, la boucle des 15 opérations 630 à 660 peut être répétée un nombre choisi de fois, ou un nombre de fois dépendant d'un critère de convergence, afin de s'assurer que l'exploration de nouvelles solutions a été réalisée de manière optimale au sein de chaque résolution. Lorsque la résolution r est atteinte, le pilote retourne la liste V contenant les données de 20 résultat dans une opération 675. La figure 7 représente un exemple de mise en oeuvre du dispositif 2 pour transformer les données de voxels calculées précédemment en données d'objet imprimable en trois dimensions. 25 En effet, les données produites par le pilote 14 ne sont pas forcément « fiables » structurellement. Par exemple, si l'on regarde les données de résultat 22, il apparaît que les oreilles du lapin, bien que correspondant à la projection idéale des données de motif, ne sont pas attachées au reste du corps. Dans ces conditions, impossible d'imprimer un 30 objet. L'objet des figures 7 à 9 trouve son application également dans le cas où les données de voxels ne sont pas obtenues comme décrit ci-avant. 3038254 19 Ainsi, le dispositif 2 part dans une opération 700 de données de voxels V. Ces données de voxels décrivent une ébauche d'objet en trois dimensions : soit le voxel désigne un emplacement plein, soit il désigne un emplacement vide. 5 Ensuite, dans une opération 720, le générateur 16 transforme les données de voxels V en un premier graphe G. Dans l'exemple décrit ici, le graphe G est construit comme suit : - chaque voxel des données de voxels V forme un noeud, - deux voxels sont considérés comme voisins et reliés par une arête si et seulement si ils 10 partagent un coin, - le poids de l'arête dans le graphe est la longueur de l'arête, définie comme la distance entre les centres des deux voxels reliés par l'arête. L'invention propose deux méthodes pouvant être combinées pour évaluer la tenue 15 mécanique d'un objet correspondant aux données de voxels. Dans les deux cas, le nombre de noeuds dans le premier graphe G est trop important pour réussir à calculer quoi que ce soit. En effet, pour que l'objet fabriqué de manière additive soit esthétique, il faut un nombre important de voxels pour avoir une bonne résolution d'impression, ce qui rend la simulation très complexe. 20 Pour simplifier les calculs, dans une opération 740, le graphe G est « simplifié » en un deuxième graphe A au moyen d'une fonction Conn(). La fonction Conn() est réalisée par l'extracteur 18, et la figure 8 représente un exemple de mise en oeuvre de cette fonction. 25 Au préalable, dans l'opération 720, le premier graphe G fait l'objet d'un échantillonnage de Poisson, afin de définir un graphe échantillonné S de voxels qui correspondent chacun à un emplacement plein. 30 Dans une opération 800, l'extracteur 18 part des données du premier graphe G, du graphe échantillonné S, ainsi que d'un graphe de marqueurs T et d'un deuxième graphe A qui sont tous deux initialisés à 0. 3038254 20 Le but de la fonction Conn() est de relier tous les noeuds du graphe échantillonné S par des premières arêtes et des deuxièmes arêtes. Les premières arêtes sont des arêtes « solides », tandis que les deuxièmes arêtes sont des arêtes « non solides ». Cela est réalisé par la propagation de marqueurs dans le graphe de marqueurs T, en partant des 5 noeuds du graphe échantillonné S. Dans une opération 805, le graphe de marqueurs T est initialisé au moyen d'une fonction Exs() qui reçoit le graphe échantillonné S et le premier graphe G comme arguments. La fonction Exs() procède en sélectionnant, pour chaque noeud du graphe S, 10 les noeuds du premier graphe G avec lesquels il partage une arête, et pour marquer avec un marqueur identifiant le noeud respectif du graphe S celui des noeuds sélectionnées qui désigne un emplacement plein et dont l'arête présente le poids le plus faible. En d'autres termes, en itérant ce processus il s'agit de propager le graphe S dans les candidats solides du graphe G suivant une distance géodésique basée sur le poids des arêtes. 15 L'opération 805 peut être vue comme une opération d'initialisation. En effet, après celle-ci, deux boucles vont se succéder. La première boucle va déterminer les premières arêtes et la seconde boucle va déterminer les deuxièmes arêtes. 20 La première boucle commence avec une opération 810 dans laquelle la fonction Exs() est à nouveau appelée pour propager les marqueurs. Pour cela, le graphe de marqueurs T est utilisé comme argument de la fonction Exs() (au lieu du graphe échantillonné S de l'opération 805). Ainsi, ce sont les noeuds qui ont été marqués à l'itération précédente de la boucle qui sont propagés, et le résultat est réinjecté dans le 25 graphe de marqueurs T. Ensuite, dans une opération 815, une fonction Edg() teste le graphe de marqueurs T pour identifier si une arête solide a été détectée par la propagation. Une arête solide est détectée lorsque deux marqueurs différents sont associés à un même voxel du premier 30 graphe G. En effet, cela signifie que ce voxel est directement relié par un chemin de voxels désignant un emplacement solide entre deux noeuds du deuxième graphe qui désignent eux-mêmes un emplacement solide. 3038254 21 Si une ou plusieurs arêtes sont identifiées par la fonction Edg(), celles-ci sont introduites dans le deuxième graphe A dans une opération 820. Ensuite, ou lorsqu'aucune arête solide n'est détectée, une fonction Fill() détermine si tous les noeuds du graphe de marqueurs ont été propagés dans une opération 825. S'il reste possible de 5 propager des marqueurs, la boucle reprend en 810. Sinon, la deuxième boucle commence dans une opération 830 avec l'exécution d'une fonction Ex(). La fonction Ex() est similaire à la fonction Exs(), à l'exception du fait que la propagation des marqueurs peut se faire à tous les voxels du premier graphe G, et 10 non plus uniquement à ceux qui indiquent un emplacement plein. La fonction Ex() diffère également de la fonction Exs() en ce que la propagation exclut les voxels associés à une première arête. Le reste de la deuxième boucle est similaire avec des opérations 835, 840 et 845 qui sont identiques aux opérations 815, 820 et 825. 15 Lorsque tous les marqueurs ont été propagés dans la deuxième boucle, la fonction Conn() se termine dans une opération 850. Il en résulte un deuxième graphe A qui contient un ensemble de noeuds qui correspondent à un échantillonnage de Poisson de voxels indiquant un emplacement plein, et qui sont reliés entre eux par des arêtes qui reflètent le fait que les chemins de voxels entre ces noeuds indiquent des emplacements 20 pleins ou vides. L'extracteur 18 pourrait mettre en oeuvre la fonction Conn() différemment, par exemple en détectant les premières arêtes et les deuxièmes arêtes de manière simultanée, ou en utilisant une distance non géodésique ou déterminée différemment. 25 Le raidisseur 20 part du deuxième graphe A et analyse si un objet correspondant à ce graphe serait mécaniquement stable. Pour cela, le raidisseur 20 utilise deux méthodes qui peuvent être utilisées seules ou en combinaison. Ces méthodes correspondent à deux simulations physiques distinctes qui déterminent si une ou plusieurs arêtes dépassent un 30 seuil synonyme de rigidité structurelle. 3038254 22 La première méthode est une méthode basée sur une simulation par éléments finis et la figure 9 représente un exemple de mise en oeuvre de cette méthode par le raidisseur 20. Cette fonction analyse les deuxièmes arêtes, dites « non solides » et redéfinit certaines d'entre elles en tant qu'arêtes solides si cela est nécessaire pour rendre l'objet 5 mécaniquement rigide. Dans une opération 900, le raidisseur 20 part du deuxième graphe A. Ensuite, dans une opération 910, une boucle commence. Cette boucle commence par une simulation par méthodes des éléments finis de l'objet défini par le deuxième graphe A. Cette 10 simulation est réalisée par une fonction FE() qui a par ailleurs accès aux paramètres de simulation mécanique (c'est-à-dire les conditions aux limites que doit respecter l'objet imprimé pour une manipulation recherchée). Le résultat de la fonction FE() est une liste de deuxièmes arêtes W dans laquelle les 15 deuxièmes arêtes sont classées par ordre de contrainte simulée décroissante, chacune de ces arêtes ayant été déterminée comme présentant une contrainte excédant un seuil de contrainte compte tenu des conditions aux limites. Ce classement par ordre de valeur de contrainte décroissante est important car le 20 principe de la méthode appliquée par le raidisseur 20 est de rendre solide l'arête la plus contrainte, puis la deuxième arête la plus contrainte qui est à une distance donnée de l'arête précédente, etc. Par conséquent, dans une opération 920, la première arête x de la liste W est extraite, et 25 celle-ci est rendue solide par une fonction Hrd() dans une opération 930. Ensuite, dans une opération 940, il est testé si la liste W contient encore une arête. Si c'est le cas, alors l'arête y correspondante est testée par une fonction Dist() dans une opération 950 pour déterminer si elle est à une distance suffisante de l'arête x qui vient 30 d'être rendue solide. Si ce n'est pas le cas, alors l'opération 940 est répétée, jusqu'à ce qu'une arête non solide suffisamment éloignée de l'arête x soit trouvée dans W ou que la liste soit vide. 3038254 23 Ainsi, toutes les arêtes ne sont pas systématiquement rendues solides lorsqu'elles sont voisines, ce qui permet de mieux respecter la forme originelle de l'objet du deuxième graphe A. 5 Si une telle arête est trouvée, alors elle est rendue solide dans une opération 960 identique à l'opération 930, et dans une opération 970, l'arête y est stockée comme arête précédente x pour la répétition de la boucle avec l'opération 940. Lorsque la liste W est vide, une nouvelle simulation est exécutée avec l'opération 910, 10 afin de déterminer si les modifications ont été suffisantes pour rendre l'objet mécaniquement rigide. Si la liste W n'est pas vide, alors la boucle est répétée. Si la liste W est vide, alors aucune des arêtes non-solides ne présente une valeur de contrainte trop importante 15 compte tenu des conditions aux limites, et la fonction se termine avec l'opération 980, dans laquelle tous les voxels du premier graphe G correspondant aux arêtes qui ont été rendues solides sont également rendus solides. Dans l'exemple décrit ici, les 3 voisins au sens géodésique de chaque voxel de l'arête, de part et d'autre de celle-ci sont également rendus solides. En variante, les voxels voisins qui sont également rendus 20 solides pourraient être sélectionnés différemment (par exemple sur un critère géométrique et non géodésique), ou les voxels voisins pourraient ne pas être changés. La deuxième méthode que le raidisseur 20 peut appliquer est une méthode géométrique. Pour cela, le raidisseur 20 parcourt chacune des arêtes non-solides du deuxième graphe 25 A et calcule le ratio entre la distance euclidienne entre les deux noeuds de chaque arête et la distance géodésique au travers des arêtes solides qui les sépare. Si ce ratio excède un seuil choisi, alors l'arête est rendue solide, ainsi qu'optionnellement les voisins des voxels qui la composent dans le premier graphe comme décrit ci-dessus. 30 Comme mentionné plus haut, la méthode mécanique et la méthode géométrique peuvent être utilisées séparément ou en combinaison. Les travaux de la Demanderesse l'amènent dans l'état actuel de ses recherches à considérer que leur combinaison est 3038254 24 particulièrement avantageuse, bien qu'elle puisse paraître redondante à l'homme du métier. Une fois que le raidisseur 20 a redéfini les arêtes non-solides, l'objet peut être imprimé 5 sur la base des voxels correspondant au deuxième graphe A et des voxels du premier graphe G ainsi modifiés. La Demanderesse a néanmoins identifié que cette modification des arêtes, bien qu'efficace mécaniquement, peut limiter l'efficience du traitement d'image présenté 10 avec les figures 2 à 5. Pour corriger cela, la Demanderesse a découvert qu'il est possible d'exécuter le raidisseur 20 et la fonction de traitement d'image en boucle afin d'obtenir un résultat visuel optimal tout en maintenant une bonne tenue mécanique. 15 Pour cela, la Demanderesse a découvert qu'il était avantageux, après l'exécution du raidisseur 20, de rappeler le traitement d'image sur les voxels qui ont été redéfinis. Pour cela, le pilote 14 exécute à nouveau la fonction de la figure 5, uniquement sur les voxels modifiés, pour un nombre plus restreint de résolutions, et d'une manière légèrement 20 différente. Ainsi, dans un premier temps, le pilote 14 détermine pour chaque voxel modifié la liste des voxels parents pour un nombre choisi de résolutions inférieures, c'est-à-dire quels sont les voxels que le propagateur 12 a transformés en ces voxels, et ce pour une taille 25 correspondant à celle de la résolution la plus faible recherchée. Dans l'exemple décrit ici, le nombre de résolutions choisi est 2, mais il pourrait être supérieur. Par exemple, si le nombre de résolutions choisi est de 2, et que le propagateur 12 double la résolution à chaque exécution (huit fois plus de voxels), alors : 30 - la résolution la plus faible comportera un voxel, la résolution intermédiaire comportera 8 voxels, et 3038254 25 la résolution qui correspond aux voxels du deuxième graphe A comportera 64 voxels. L'exécution du pilote 14 sera réalisée à partir de chacun des voxels de résolution la plus 5 basse qui présente un fils qui a été modifié par le raidisseur 20. Dans chaque résolution, le pilote 14 indique si un voxel correspond à un voxel qui a été modifié. Lorsque ce n'est pas le cas, le sélectionneur 10 est exécuté à l'identique. En revanche, si le voxel en question correspond à un voxel qui a été modifié, alors la 10 fonction exécutée par le sélectionneur 10 est légèrement modifiée conformément à la figure 10 pour ne sélectionner comme données de projection 26 que celles qui désigneront également un emplacement plein. Ainsi, l'exécution du pilote 14 ne vient pas dégrader la structure mécanique, et seulement harmoniser visuellement l'objet afin qu'il corresponde mieux aux données de motif 24. 15 Sur la figure 10, les opérations identiques à celles de la figure 4 ont été représentées avec un suffixe numérique identique, de sorte que l'opération 410 et l'opération 1010 sont identiques, etc. Comme on peut le voir sur cette figure, seule une opération 1042 a été ajoutée, qui est un test pour déterminer si des données de projection p dy 20 susceptibles de venir améliorer le traitement d'image correspondent à un emplacement solide, ou non. Une fois que le pilote 14 a fini ce traitement, le générateur 16, l'extracteur 18 et le raidisseur 20 sont à nouveau appliqués sur les données de voxels résultantes. La boucle 25 se termine lorsque le raidisseur 20 ne modifie aucune arête, et donc aucun voxel. Ensuite, les opérations de fabrication additive, y compris la génération du support peuvent être réalisées comme cela est connu. 30 L'invention peut également être définie comme un procédé de traitement de données pour fabrication additive, comprenant les opérations suivantes : 3038254 26 a) recevoir des données de voxels d'une surface d'un objet à fabriquer, chaque voxel indiquant un emplacement plein ou vide, b) calculer un premier graphe à partir des données de voxels en définissant chaque voxel comme formant un noeud, en reliant entre eux par des arêtes les noeuds qui 5 correspondent à des voxels respectifs qui partagent un coin, et en affectant à chaque arête un poids calculé à partir de la distance entre les centres des voxels correspondant aux noeuds qui lui sont associés, c) calculer un deuxième graphe en définissant des noeuds à partir d'un sous-ensemble de noeuds du graphe comprenant des noeuds correspondant à des voxels indiquant un 10 emplacement plein, et pour relier entre eux les noeuds du deuxième graphe par des premières arêtes et des deuxièmes arêtes, une première arête étant définie comme représentant le chemin le plus court en termes de poids au sein du premier graphe entre deux noeuds du deuxième graphe, chaque noeud du premier graphe reliant ces deux noeuds correspondant à un voxel indiquant un emplacement plein, et la somme des poids 15 des arêtes du premier graphe reliant les deux noeuds associés à la première arête définissant le poids de cette première arête, une deuxième arête étant définie comme représentant le chemin le plus court en termes de poids au sein du premier graphe entre deux noeuds du deuxième graphe qui ne peuvent pas être reliés par une première arête, d) déterminer une liste de deuxièmes arêtes dépassant un seuil sur la base d'une 20 simulation physique d'un objet correspondant au deuxième graphe, et redéfinir certaines au moins de ces deuxièmes arêtes en tant que premières arêtes, et pour redéfinir certains au moins des voxels correspondant aux noeuds du premier graphe appartenant au voisinage de ces arêtes redéfinies comme correspondant à un emplacement plein. 25 Ce procédé tel peut présenter une ou plusieurs des caractéristiques suivantes : - l'opération c) comprend l'opération suivante : cl) déterminer les premières arêtes en associant à chaque noeud du premier graphe correspondant à voxel indiquant un emplacement plein un marqueur d'un noeud dudit sous-ensemble, les marqueurs étant propagés à partir de chacun des noeuds dudit 30 sous-ensemble en choisissant, à partir d'un noeud marqué, celui des noeuds qui lui est directement relié par une arête dans le premier graphe, qui correspond à un voxel indiquant un emplacement plein et dont l'arête présente le poids le plus faible, une 3038254 27 première arête étant créée lorsque la propagation implique le marquage d'un noeud présentant déjà un marqueur d'un noeud dudit sous-ensemble, - l'opération c) comprend en outre l'opération suivante : c2) déterminer les deuxièmes arêtes en associant à chaque noeud du premier 5 graphe un marqueur d'un noeud dudit sous-ensemble, les marqueurs étant propagés à partir de chacun des noeuds dudit sous-ensemble en choisissant, à partir d'un noeud marqué, celui des noeuds qui lui est directement relié par une arête dans le premier graphe, dont l'arête présente le poids le plus faible, et qui n'appartient pas à une première arête, une deuxième arête étant créée lorsque la propagation implique le 10 marquage d'un noeud présentant déjà un marqueur d'un noeud dudit sous-ensemble, - l'opération d) comprend une boucle récursive comprenant les opérations suivantes : dl) simuler par éléments finis à partir du deuxième graphe un champ de contrainte pour chacune des arêtes du deuxième graphe, d2) déterminer une liste de secondes arêtes présentant une contrainte supérieure 15 à un seuil de contrainte, d3) sélectionner la seconde arête de la liste présentant la plus grande contrainte en première arête, d4) redéfinir cette seconde arête en tant que première arête si elle est à une distance choisie en termes de poids de la dernière arête redéfinie dans la boucle 20 en court, et en répétant l'opération d3) sinon, d5) recommençant la boucle en a) lorsque la liste ne contient plus d'arête, jusqu'à ce que la boucle ne redéfinisse plus aucune arête, - l'opération d) comprend une boucle comprenant les opérations suivantes : dl) déterminer un ratio entre la distance en termes de poids entre les noeuds de 25 chaque deuxième arête et la distance euclidienne entre ces mêmes noeuds, d2) redéfinir chaque seconde arête dont le ratio supérieur est à un seuil choisi en tant que première arête, - le procédé comprend également les opérations suivantes : e) recevoir des données de surface en trois dimensions, des données de voxel 30 associées, des données de projection et des données de motif, f) à partir d'un voxel d'une résolution donnée et de données de projection qui lui sont associées, définir une pluralité de voxels de résolution supérieure à la 3038254 28 résolution donnée, et associer à certains au moins de cette pluralité de voxels les données de projection associées au voxel de résolution donnée, g) pour certains au moins de la pluralité de voxels résultante auxquels sont associées des données de projection en tant que voxel donné: 5 gl) définir un jeu de données de projection comprenant d'une part les données de projection associées à la pluralité de données de voxels résultante, et d'autre part une quantité non nulle d'autres données de projection, g2) pour certaines au moins des données de projection issues de 10 l'opération gl), et pour certains au moins des voxels voisins du voxel donné, et pour calculer une valeur de similarité entre le voxel donné et chaque voxel voisin concerné, à partir de la projection des données de surface en trois dimensions associées au voxel donné et des données de surface en trois dimensions associées au voxel voisin, respectivement sur 15 une première surface définie par des données de projection du jeu de données de projetion et sur une deuxième surface définie par les données de projection du voxel voisin sur lesquelles les données de motif sont plaquées, en calculant une valeur tirée de la différence entre la projection du voxel donné sur la première surface et la deuxième surface d'une 20 part, et de la différence entre la projection du voxel voisin sur la première surface et la deuxième surface d'autre part, g3) déterminer celles des données de projection dudit jeu qui indiquent la meilleure similarité, h) Répéter les opérations f) et g) avec certains au moins des voxels résultants, jusqu'à 25 atteindre une résolution choisie, - l'opération g) comprend la détermination de la valeur tirée de la différence entre la projection d'un voxel sur la première surface et sur la deuxième surface à partir de la différence de texture résultant du plaquage des données de motif sur la première surface et sur la deuxième surface pour ces projections, 30 - l'opération g) comprend la détermination de la valeur de similarité à partir d'une valeur tirée de la valeur de l'angle formé par la normale au plan défini par les données 3038254 29 de surface en trois dimensions d'une part, et par la normale au plan de projection d'autre part, - dans l'opération g), la valeur de similarité est strictement positive et indique une similarité d'autant meilleure que la valeur de similarité est faible, 5 - l'opération f) comprend l'association de certains au moins des voxels de la pluralité de voxels de résolution supérieure avec des données de projection choisies aléatoirement, - les données de projection comprennent un identifiant de surface choisi parmi un jeu de plans et des données de transformation indiquant une translation et/ou une rotation du repère de la surface désignée par l'identifiant de surface pour le plaquage des données 10 de motif, - les données de projection sont indépendantes des données de surface en trois dimensions, - la surface définie par les données de projection est un plan, - les données de motif sont de nature stochastique et répétitive. 15 - la valeur de similarité est strictement positive et indique une similarité d'autant meilleure que la valeur de similarité est faible, - les données de voxels de l'opération a) sont obtenues par l'application des opérations e) à h), - les opérations e) à h) sont répétées avec les données de voxels modifiées dans 20 l'opération d), - pour les données de voxels modifiées dans l'opération d), l'opération g3) est répétée de manière à ne sélectionner que des données de projection telles que les données de voxels concernées indiqueront un emplacement plein, - les opérations a) à d) et e) à h) sont répétées en boucle jusqu'à ce que l'opération d) ne 25 modifie plus de données de voxels. L'invention peut également être définie comme un produit de programme d'ordinateur comprenant des portions de code de programme pour mettre en oeuvre le dispositif ou le procédé tels que décrit plus haut lorsque ledit programme est exécuté sur un ordinateur. 30 REVENDICATIONS1. Dispositif pour fabrication additive, comprenant : - une mémoire (4) pour recevoir des données de voxels d'une surface d'un objet à fabriquer, chaque voxel indiquant un emplacement plein ou vide, - un générateur (16) capable de calculer un premier graphe (G) à partir des données de voxels en définissant chaque voxel comme formant un noeud, en reliant entre eux par des arêtes les noeuds qui correspondent à des voxels respectifs qui partagent un coin, et en affectant à chaque arête un poids calculé à partir de la distance entre les centres des voxels correspondant aux noeuds qui lui sont associés, - un extracteur (18) agencé, pour définir un deuxième graphe (A) en définissant des noeuds à partir d'un sous-ensemble de noeuds du graphe comprenant des noeuds correspondant à des voxels indiquant un emplacement plein, et pour relier entre eux les noeuds du deuxième graphe (A) par des premières arêtes et des deuxièmes arêtes, une première arête étant définie comme représentant un chemin au sein du premier graphe (G) entre deux noeuds du deuxième graphe (A), chaque noeud du premier graphe (G) reliant ces deux noeuds correspondant à un voxel indiquant un emplacement plein, et la somme des poids des arêtes du premier graphe (G) reliant les deux noeuds associés à la première arête définissant le poids de cette première arête, une deuxième arête étant définie comme représentant un chemin au sein du premier graphe (G) entre deux noeuds du deuxième graphe (A) qui ne peuvent pas être reliés par une première arête, - un raidisseur (20) agencé, pour déterminer une liste de deuxièmes arêtes dépassant un seuil sur la base d'une simulation physique d'un objet correspondant au deuxième graphe (A), pour redéfinir certaines au moins de ces deuxièmes arêtes en tant que premières arêtes, et pour redéfinir certains au moins des voxels correspondant aux noeuds du premier graphe (G) appartenant au voisinage de ces arêtes redéfinies comme correspondant à un emplacement plein, et 3038254 31 un pilote (14) agencé pour appeler le générateur (16), l'extracteur (18) et le raidisseur (20) pour produire des données d'objet à imprimer (30). 2. Dispositif selon la revendication 1, dans lequel l'extracteur (18) est agencé pour 5 déterminer dans une première opération les premières arêtes en associant à chaque noeud du premier graphe (G) correspondant à un voxel indiquant un emplacement plein un marqueur d'un noeud dudit sous-ensemble, les marqueurs étant propagés à partir de chacun des noeuds dudit sous-ensemble en choisissant, à partir d'un noeud marqué, celui des noeuds qui lui est directement relié par une 10 arête dans le premier graphe (G), qui correspond à un voxel indiquant un emplacement plein et dont l'arête présente le poids le plus faible, une première arête étant créée lorsque la propagation implique le marquage d'un noeud présentant déjà un marqueur d'un noeud dudit sous-ensemble. 15 3. Dispositif selon la revendication 2, dans lequel l'extracteur (18) est agencé pour déterminer, après la première opération, les deuxièmes arêtes en associant à chaque noeud du premier graphe (G) un marqueur d'un noeud dudit sous-ensemble, les marqueurs étant propagés à partir de chacun des noeuds dudit sous-ensemble en choisissant, à partir d'un noeud marqué, celui des noeuds qui lui est 20 directement relié par une arête dans le premier graphe (G), dont l'arête présente le poids le plus faible, et qui n'appartient pas à une première arête, une deuxième arête étant créée lorsque la propagation implique le marquage d'un noeud présentant déjà un marqueur d'un noeud dudit sous-ensemble. 25 4. Dispositif selon l'une des revendications précédentes, dans lequel le raidisseur (20) est agencé pour exécuter une boucle récursive en a) simulant par éléments finis à partir du deuxième graphe (A) un champ de contrainte pour chacune des arêtes du deuxième graphe (A), b) déterminant une liste de secondes arêtes présentant une contrainte 30 supérieure à un seuil de contrainte, c) sélectionnant la seconde arête de la liste présentant la plus grande contrainte en première arête, 3038254 32 d) redéfinissant cette seconde arête en tant que première arête si elle est à une distance choisie en termes de poids de la dernière arête redéfinie dans la boucle en cours, et en répétant l'opération c) sinon, e) recommençant la boucle en a) lorsque la liste ne contient plus d'arête, 5 jusqu'à ce que la boucle ne redéfinisse plus aucune arête. 5. Dispositif selon l'une des revendications précédentes, dans lequel le raidisseur (20) est agencé pour exécuter une boucle en a) déterminant un ratio entre la distance en termes de poids entre les 10 noeuds de chaque deuxième arête et la distance euclidienne entre ces mêmes noeuds, b) redéfinissant chaque seconde arête dont le ratio supérieur est à un seuil choisi en tant que première arête. 15 6. Dispositif selon l'une des revendications précédentes, dans lequel la mémoire (4) reçoit en outre des données de surface en trois dimensions (22), des données de projection (26) et des données de motif (24), et le dispositif comprend en outre : - un trieur (6) capable de sélectionner pour un voxel d'entrée des voxels entourant le voxel d'entrée qui correspondent aux données de surface en trois 20 dimensions, - un estimateur (8) capable de calculer une valeur de similarité entre un premier voxel associé à de premières données de projection et un second voxel associé à de secondes données de projection en calculant la projection des données de surface en trois dimensions associées au premier voxel et des 25 données de surface en trois dimensions associées au deuxième voxel, respectivement sur une première surface définie par les premières données de projection et sur une deuxième surface définie par les deuxièmes données de projection sur lesquelles les données de motif sont plaquées, et en calculant une valeur tirée de la différence entre la projection du premier voxel sur la première 30 surface et la deuxième surface d'une part, et de la différence entre la projection du deuxième voxel sur la première surface et la deuxième surface d'autre part, 3038254 33 - un sélectionneur (10) capable, pour un voxel donné et à partir d'un jeu de données de projection (26), de déterminer celles des données de projection dudit jeu qui indiquent la meilleure similarité avec des voxels voisins du voxel donné, à partir d'une valeur tirée des valeurs de similarité obtenues en appelant 5 l'estimateur (10) de manière répétée avec d'une part le voxel donné comme premier voxel et des données de projection du jeu comme premières données de projection et d'autre part avec certains au moins des voxels tirés de l'appel du trieur (6) avec le premier voxel en tant que deuxième voxel, et des données de projection (26) qui leur sont associées comme deuxièmes données de 10 projection (26), et pour associer au voxel donné les données de projection déterminées, - un propagateur (12) capable, à partir d'un voxel d'une résolution donnée et de données de projection (26) qui lui sont associées, de définir une pluralité de voxels de résolution supérieure à la résolution donnée, et pour associer à certains 15 au moins de cette pluralité de voxels les données de projection associées au voxel de résolution donnée, - un pilote (14) agencé pour appeler le propagateur (12) avec des données de surface en trois dimensions (22), un voxel (26) et des données de projection associées, et pour appeler le sélectionneur (10) avec certains au moins de la 20 pluralité de voxels résultante auxquels sont associées des données de projection en tant que voxel donné, ainsi qu'avec un jeu de données de projection (26) comprenant d'une part les données de projection associées à la pluralité de données de voxels résultante, et d'autre part une quantité non nulle d'autres données de projection, le pilote (14) étant en outre agencé pour répéter l'appel 25 du propagateur (12) avec certains au moins des voxels associés aux données de projection déterminées par le sélectionneur (10), ainsi que l'appel du sélectionneur (10) sur certains au moins de la pluralité de voxels résultante jusqu'à atteindre une résolution choisie. 30 7. Dispositif selon la revendication 6, dans lequel l'estimateur (10) est agencé pour déterminer la valeur tirée de la différence entre la projection d'un voxel sur la première surface et sur la deuxième surface à partir de la différence de texture 3038254 34 résultant du plaquage des données de motif sur la première surface et sur la deuxième surface pour ces projections. 8. Dispositif selon la revendication 6 ou 7, dans lequel l'estimateur (10) est agencé 5 pour déterminer la valeur de similarité à partir d'une valeur tirée de la valeur de l'angle formé par la normale au plan défini par les données de surface en trois dimensions d'une part, et par la normale au plan de projection d'autre part. 9. Dispositif selon l'une des revendications 6 à 8, dans lequel l'estimateur (10) est 10 agencé pour déterminer une valeur de similarité strictement positive et indiquant une similarité d'autant meilleure que la valeur de similarité est faible. 10. Dispositif selon l'une des revendications 6 à 9, dans lequel le propagateur (12) est agencé pour associer certains au moins des voxels de la pluralité de voxels de 15 résolution supérieure avec des données de projection (26) choisies aléatoirement. 11. Dispositif selon l'une des revendications 6 à 10, dans lequel la mémoire (4) est agencée pour recevoir des données de projection (26) qui comprennent un 20 identifiant de surface choisi parmi un jeu de plans et des données de transformation (26) indiquant une translation et/ou une rotation du repère de la surface désignée par l'identifiant de surface pour le plaquage des données de motif (24). 25 12. Dispositif selon l'une des revendications 6 à 11, dans lequel la mémoire (4) est agencée pour recevoir des données de projection (26) indépendantes des données de surface en trois dimensions (22). 13. Dispositif selon l'une des revendications 6 à 12, dans lequel la mémoire (4) est 30 agencée pour recevoir des données de projection définissant une surface qui est un plan. 3038254 14. Dispositif selon l'une des revendications 6 à 13, dans lequel la mémoire (4) est agencée pour recevoir des données de motif (24) de nature stochastique et répétitive. 5 15. Dispositif selon l'une des revendications 6 à 14, dans lequel le générateur (16) est agencé pour utiliser les données de voxels déterminées par le pilote (14). 16. Dispositif selon l'une des revendications 6 à 15, dans lequel le pilote (14) est agencé pour être appelé avec les données de voxels modifiées par le 10 raidisseur (20). 17. Dispositif selon la revendication 16, dans lequel le pilote (14) est agencé, pour les données de voxels modifiées par le raidisseur (20), pour appeler le sélectionneur (10) de manière à ne sélectionner que des données de 15 projection (26) telles que les données de voxels concernées indiqueront un emplacement plein après traitement. 18. Dispositif selon la revendication 17, dans lequel le raidisseur (20) et le pilote (14) sont agencés pour être appelés en boucle jusqu'à ce que le 20 raidisseur (20) ne modifie plus de données de voxels. 19. Procédé de traitement de données pour fabrication additive, comprenant les opérations suivantes : a) recevoir des données de voxels d'une surface d'un objet à fabriquer, chaque voxel 25 indiquant un emplacement plein ou vide, b) calculer un premier graphe (G) à partir des données de voxels en définissant chaque voxel comme formant un noeud, en reliant entre eux par des arêtes les noeuds qui correspondent à des voxels respectifs qui partagent un coin, et en affectant à chaque arête un poids calculé à partir de la distance entre les centres des voxels 30 correspondant aux noeuds qui lui sont associés, c) calculer un deuxième graphe (A) en définissant des noeuds à partir d'un sous- ensemble de noeuds du graphe comprenant des noeuds correspondant à des voxels 3038254 36 indiquant un emplacement plein, et pour relier entre eux les noeuds du deuxième graphe (A) par des premières arêtes et des deuxièmes arêtes, une première arête étant définie comme représentant le chemin le plus court en termes de poids au sein du premier graphe (G) entre deux noeuds du deuxième graphe (A), chaque noeud du 5 premier graphe (G) reliant ces deux noeuds correspondant à un voxel indiquant un emplacement plein, et la somme des poids des arêtes du premier graphe (G) reliant les deux noeuds associés à la première arête définissant le poids de cette première arête, une deuxième arête étant définie comme représentant le chemin le plus court en termes de poids au sein du premier graphe (G) entre deux noeuds du deuxième 10 graphe (A) qui ne peuvent pas être reliés par une première arête, d) déterminer une liste de deuxièmes arêtes dépassant un seuil sur la base d'une simulation physique d'un objet correspondant au deuxième graphe (A), et redéfinir certaines au moins de ces deuxièmes arêtes en tant que premières arêtes, et pour redéfinir certains au moins des voxels correspondant aux noeuds du premier graphe 15 (G) appartenant au voisinage de ces arêtes redéfinies comme correspondant à un emplacement plein. 20. Produit de programme d'ordinateur comprenant des portions de code de programme pour mettre en oeuvre le dispositif selon l'une des revendications 1 à 20 18 ou le procédé selon la revendication 19 lorsque ledit programme est exécuté sur un ordinateur.