JFA (l'algorithme décrit ici: http://www.comp.nus.edu.sg/~tants/jfa/i3d06.pdf ) peut être utilisé pour obtenir une approximation d'un diagramme de Voronoï ou une transformation de distance. Il le fait en temps logarithmique en fonction de la taille de l'image résultante, et non du nombre de graines.

Que faites-vous si votre image n'est pas de la même taille sur chaque axe?

S'ils étaient de tailles similaires, je suis sûr que vous pourriez simplement laisser l'axe plus court avoir des étapes JFA supplémentaires de taille 1, tandis que l'axe plus grand a fini de fonctionner (comme avoir une image de taille 512 x 256). Pour des dimensions d'axe de tailles très différentes, cela pourrait être beaucoup plus inefficace - disons que vous aviez une texture de volume de 512 x 512 x 4.

Est-il possible d'exécuter JFA sur chaque axe séparément et d'obtenir toujours des résultats décents?

Ou à ce stade, un algorithme différent est-il plus approprié à utiliser? Si oui, quel algorithme cela pourrait-il être?

Dans ma situation, idéalement, je cherche à prendre en charge les graines à point unique, ainsi que les graines de forme arbitraire. Peut-être même des graines pondérées, où la distance à une graine est ajustée par un multiplicateur et / ou un additionneur pour lui donner plus ou moins d'influence.

Réponses rapides à vos questions individuelles

Que faites-vous si votre image n'est pas de la même taille sur chaque axe?

Le papier utilise des images carrées avec des longueurs de côté qui sont une puissance de 2. C'est pour faciliter l'explication, mais ce n'est pas nécessaire pour que l'algorithme fonctionne. Voir section 3.1:

Sans perte de généralité, nous pouvons supposer que n est une puissance de 2.

Autrement dit, cette hypothèse n'est pas requise pour que l'algorithme fonctionne.

Est-il possible d'exécuter JFA sur chaque axe séparément et d'obtenir toujours des résultats décents?

L'exécution séparée sur chaque axe est susceptible de donner des résultats de pixels plus incorrects et de prendre plus de temps dans la plupart des cas. Dans les cas extrêmes où l'une des longueurs des côtés de l'image est inférieure à 8 (le nombre de directions de saut), cela peut être plus rapide car l'algorithme traite ces 8 directions séquentiellement, mais pour toute image plus large, la séparation des axes perd l'avantage de les traiter en parallèle.

Dans ma situation, idéalement, je cherche à prendre en charge les graines à point unique, ainsi que les graines de forme arbitraire

L'article mentionne des graines de forme arbitraire dans la section 6 sous la sous-rubrique "Diagramme de Voronoï généralisé":

... nos algorithmes traitent ces graines généralisées comme des collections de graines ponctuelles et s'attendent donc à hériter des bonnes performances obtenues pour les graines ponctuelles.

Donc, à condition que cela corresponde à votre objectif de modéliser des formes arbitraires en tant que collections de pixels, vous n'avez pas besoin d'ajuster l'algorithme. Introduisez simplement une texture qui étiquette tous les pixels dans une graine de forme arbitraire avec le même numéro de graine, mais des emplacements différents.

Peut-être même des graines pondérées, où la distance à une graine est ajustée par un multiplicateur et / ou un additionneur pour lui donner plus ou moins d'influence

Pour la "pondération sur les semences telles que multiplicatives et additives", le document mentionne seulement la possibilité en passant dans la section 8, comme travaux futurs potentiels. Cependant, cela devrait être simple à mettre en œuvre à condition que votre pondération souhaitée puisse être incluse dans les données de départ qui sont transmises de pixel en pixel.

L'algorithme actuel passe <s, position(s)>pour spécifier une graine et sa position, et une seule graine est stockée par pixel à la fois. L'extension pour stocker <s, position(s), weight(s)>fournit toutes les informations nécessaires pour pondérer la fonction de distance et calculer si la nouvelle graine transmise à un pixel est plus proche de celle qu'elle stocke actuellement.

Vous pouvez même inclure deux poids, un multiplicatif et un additif, et définir simplement le multiplicatif à 1 et l'additif à 0 lorsqu'il n'est pas requis. Ensuite, votre algorithme inclurait la possibilité d'être utilisé pour des graines pondérées multiplicativement, des graines pondérées additivement, ou même une combinaison des deux à la fois ou une partie de chacune. Cela aurait juste besoin

<s, position(s), multiplicative(s), additive(s)>

et l'algorithme actuel serait équivalent à ce nouvel algorithme utilisant

<s, position(s), 1, 0>

Explication détaillée des raisons

Comme dans l'article, toutes les utilisations de réfèrent au logarithme de base 2.$\log()$

L'algorithme n'a pas besoin d'être adapté pour différentes longueurs de côté

Si les longueurs des côtés ne sont pas égales et ne sont pas des puissances de 2, il n'est pas nécessaire d'adapter l'algorithme. Il traite déjà des pixels sur le bord de l'image pour lesquels certaines des directions de saut mènent à l'extérieur de l'image. Puisque l'algorithme omet déjà les informations de départ pour les directions qui mènent à l'extérieur de l'image, une largeur ou une hauteur qui n'est pas une puissance de 2 ne sera pas un problème. Pour une image de largeur W et de hauteur H, la taille de saut maximale requise sera

Dans le cas d'une largeur et d'une hauteur égales N, cela se réduit à

Dans le cas d'une longueur de côté N qui est une puissance de 2, cela se réduit à

comme utilisé dans le document.

En termes plus intuitifs, arrondissez la longueur maximale du côté jusqu'à la puissance suivante de 2, puis divisez-la par deux pour obtenir la taille de saut maximale.

Ceci est toujours suffisant pour couvrir chaque pixel de l'image à partir de chaque autre pixel de l'image, car le décalage par rapport à n'importe quel pixel sera compris entre 0 et N-1 si la longueur du côté le plus long est N. Combinaisons des puissances de 2 à partir de 0 à N / 2 couvrira chaque entier jusqu'à N-1 si N est une puissance de 2, et si N n'est pas une puissance de 2, la plage couverte ne peut être plus grande que nécessaire, en raison de la prise du plafond du logarithme ( arrondi à la puissance suivante de 2).

Les images dont les côtés n'ont pas une puissance de 2 ne seront pas considérablement moins efficaces

Le nombre de sauts dépend de la longueur du côté le plus long, disons L. Si L est une puissance de 2, alors le nombre de sauts est . Si L n'est pas une puissance de 2, le nombre de sauts est . Pour une image raisonnablement grande, cela ne fera pas une grande différence.$\log(L)$$\lceil\log(L)\rceil$

Par exemple, une image 1024 x 1024 nécessitera 10 itérations de saut. Une image 512 par 512 nécessitera 9 itérations de saut. Tout élément entre les deux tailles nécessitera également 10 itérations. Même dans le pire des cas, une image juste au-dessus d'une puissance de 2, comme une image 513 par 513, ne nécessitera qu'une seule itération supplémentaire, ce qui à cette échelle représente environ 11% de plus (10 au lieu de 9).

Les images non carrées sont moins efficaces par zone

Étant donné que le nombre d'itérations nécessaires est déterminé par la longueur de côté la plus longue, le temps nécessaire pour une image 1024 x 1024 sera le même que pour une image 1024 x 16. Une image carrée permet de couvrir une plus grande zone avec le même nombre d'itérations.

La séparation des axes est susceptible de réduire la qualité

La section 5 du document décrit les erreurs possibles. Chaque pixel est accessible par un chemin à partir de chaque autre pixel, mais certains chemins n'apportent pas la graine la plus proche correcte, car cette graine n'est pas la plus proche d'un pixel précédent dans le chemin. Un pixel qui ne permet pas à une graine de se propager au-delà aurait "tué" cette graine. Si la graine la plus proche d'un pixel est tuée sur tous les chemins vers ce pixel, alors le pixel enregistrera une autre graine et il y aura une couleur incorrecte dans l'image finale.

Un seul chemin doit exister qui ne tue pas la graine pour que le résultat final soit correct. Des couleurs incorrectes ne se produisent que lorsque tous les chemins entre la graine correcte et un pixel donné sont bloqués.

Si un chemin implique l'alternance de sauts horizontaux et verticaux, la séparation des axes rendra ce chemin impossible (tous les sauts horizontaux seront effectués avant tous les sauts verticaux, rendant l'alternance impossible). Les sauts en diagonale ne seront pas possibles du tout. Ainsi, tout chemin alternant ou contenant des sauts diagonaux sera exclu. Chaque pixel aura toujours un chemin vers tous les autres pixels, mais comme il y a maintenant moins de chemins, il y a plus de chances qu'un pixel donné soit bloqué de recevoir la bonne graine, donc le résultat final sera plus sujet aux erreurs.

La séparation des axes risque de rallonger l'algorithme

L'efficacité serait probablement réduite en séparant les axes, car l'inondation ne se ferait plus en parallèle, mais serait plutôt répétée pour chaque axe. Pour la 2D, cela prendrait probablement environ deux fois plus longtemps, et pour la 3D environ 3 fois plus longtemps.

Cela peut être quelque peu atténué par le manque de sauts diagonaux, mais je m'attendrais quand même à une réduction globale de l'efficacité.