JFA (el algoritmo descrito aquí: http://www.comp.nus.edu.sg/~tants/jfa/i3d06.pdf ) se puede usar para obtener una aproximación de un diagrama de Voronoi o una transformación de distancia. Lo hace en tiempo logarítmico basado en el tamaño de la imagen resultante, no en el número de semillas.

¿Qué haces si tu imagen no tiene el mismo tamaño en cada eje?

Si tuvieran tamaños similares, estoy seguro de que podría dejar que el eje más corto tuviera pasos JFA adicionales de tamaño 1, mientras que el eje más grande lo terminó (como tener una imagen de tamaño 512 x 256). Sin embargo, para dimensiones de eje de tamaños muy diferentes, esto podría ser mucho más ineficiente; supongamos que tenía una textura de volumen de 512 x 512 x 4.

¿Es posible ejecutar JFA en cada eje por separado y aún así obtener resultados decentes?

¿O en ese punto es un algoritmo diferente más apropiado para usar? Si es así, ¿qué algoritmo podría ser ese?

En mi situación ideal, estoy buscando apoyar tanto las semillas de un solo punto como las semillas de formas arbitrarias. Posiblemente incluso semillas ponderadas, donde la distancia a una semilla se ajusta mediante un multiplicador y / o un sumador para darle más o menos influencia.

Respuestas rápidas a sus preguntas individuales.

¿Qué haces si tu imagen no tiene el mismo tamaño en cada eje?

El documento utiliza imágenes cuadradas con longitudes laterales que son una potencia de 2. Esto es para facilitar la explicación, pero no es necesario para que el algoritmo funcione. Ver sección 3.1:

Sin pérdida de generalidad, podemos suponer que n es una potencia de 2.

Es decir, esta suposición no es necesaria para que el algoritmo funcione.

¿Es posible ejecutar JFA en cada eje por separado y aún así obtener resultados decentes?

Es probable que la ejecución en cada eje por separado proporcione resultados de píxeles más incorrectos y , en la mayoría de los casos , demore más en ejecutarse. En casos extremos donde una de las longitudes laterales de la imagen es menor que 8 (el número de direcciones de salto), puede ser más rápido ya que el algoritmo trata esas 8 direcciones secuencialmente, pero para cualquier imagen más amplia, la separación de los ejes pierde la ventaja de tratarlos. en paralelo.

En mi situación ideal, estoy buscando apoyar tanto las semillas de un solo punto como las semillas de forma arbitraria

El documento menciona semillas de formas arbitrarias en la sección 6 bajo el subtítulo "Diagrama generalizado de Voronoi":

... nuestros algoritmos tratan las semillas generalizadas como colecciones de semillas puntuales y, por lo tanto, esperan heredar el buen rendimiento obtenido para las semillas puntuales.

Por lo tanto, siempre que se adapte a su propósito de modelar formas arbitrarias como colecciones de píxeles, no necesita hacer ningún ajuste en el algoritmo. Simplemente alimente una textura que etiquete todos los píxeles en una semilla de forma arbitraria con el mismo número de semilla, pero en diferentes ubicaciones.

Posiblemente incluso semillas ponderadas, donde la distancia a una semilla se ajusta mediante un multiplicador y / o un sumador para darle más o menos influencia

Para "ponderar en semillas como multiplicativo y aditivo", el documento solo menciona la posibilidad de pasar en la sección 8, como posible trabajo futuro. Sin embargo, esto debería ser sencillo de implementar, siempre que su ponderación deseada se pueda incluir en los datos semilla que se pasan de píxel a píxel.

El algoritmo actual pasa <s, position(s)>para especificar una semilla y su posición, y solo se almacena una semilla por píxel en cualquier momento. Extender esto para almacenar <s, position(s), weight(s)>proporciona toda la información necesaria para ponderar la función de distancia y calcular si la nueva semilla que se pasa a un píxel está más cerca de la que está almacenando actualmente.

Incluso podría incluir dos pesos, uno multiplicativo y otro aditivo, y simplemente establecer el multiplicativo en 1 y el aditivo en 0 cuando no sea necesario. Luego, su algoritmo incluiría la posibilidad de ser utilizado para semillas con peso multiplicativo, semillas con peso aditivo o incluso una combinación de ambas a la vez o parte de cada una. Esto solo necesitaría

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

y el algoritmo actual sería equivalente a este nuevo algoritmo usando

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

Explicación detallada de por qué

$\log()$

El algoritmo no necesita ser adaptado para diferentes longitudes laterales

Si las longitudes de los lados no son iguales y no son potencias de 2, no hay necesidad de adaptar el algoritmo. Ya trata con píxeles en el borde de la imagen para los cuales algunas de las direcciones de salto conducen fuera de la imagen. Dado que el algoritmo ya omite la información inicial para las direcciones que conducen fuera de la imagen, un ancho o alto que no sea una potencia de 2 no será un problema. Para una imagen de ancho W y altura H, el tamaño de salto máximo requerido será

Para el caso de igual ancho y alto N, esto se reduce a

En el caso de una longitud lateral N que es una potencia de 2, esto se reduce a

como se usa en el documento.

En términos más intuitivos, redondee la longitud máxima del lado hasta la siguiente potencia de 2, y luego reduzca a la mitad eso para obtener el tamaño máximo de salto.

Esto siempre es suficiente para cubrir cada píxel en la imagen de cualquier otro píxel en la imagen, ya que el desplazamiento a cualquier píxel estará en el rango de 0 a N-1 si la longitud lateral más larga es N. Combinaciones de las potencias de 2 de 0 a N / 2 cubrirá todos los enteros hasta N-1 si N es una potencia de 2, y si N no es una potencia de 2, el rango cubierto solo puede ser mayor de lo requerido, debido a tomar el techo del logaritmo ( redondeando a la siguiente potencia de 2).

Las imágenes con lados que no tienen una potencia de 2 no serán drásticamente menos eficientes

El número de saltos depende de la longitud lateral más larga, digamos L. Si L es una potencia de 2, entonces el número de saltos es . Si L no es una potencia de 2, entonces el número de saltos es . Para una imagen razonablemente grande, esto no será una gran diferencia.$\log(L)$$\lceil\log(L)\rceil$

Por ejemplo, una imagen de 1024 por 1024 requerirá 10 iteraciones de salto. Una imagen de 512 por 512 requerirá 9 iteraciones de salto. Cualquier cosa entre los dos tamaños también requerirá 10 iteraciones. Incluso en el peor de los casos de una imagen solo por encima de una potencia de 2, como una imagen de 513 por 513, solo requerirá 1 iteración adicional, que en esta escala es aproximadamente un 11% más (10 en lugar de 9).

Las imágenes no cuadradas son menos eficientes por área

Dado que el número de iteraciones requeridas está determinado por la longitud lateral más larga, el tiempo necesario para una imagen de 1024 por 1024 será el mismo que para una imagen de 1024 por 16. Una imagen cuadrada permite cubrir un área más grande en el mismo número de iteraciones.

Es probable que la separación de ejes reduzca la calidad

La Sección 5 del documento describe posibles errores. Se puede llegar a cada píxel por una ruta desde cualquier otro píxel, pero algunas rutas no traen la semilla más cercana correcta, debido a que esa semilla no es la más cercana a un píxel anterior en la ruta. Se dice que un píxel que no permite que una semilla se propague más allá "mató" esa semilla. Si la semilla más cercana a un píxel se elimina en todas las rutas a ese píxel, entonces el píxel registrará alguna otra semilla y habrá un color incorrecto en la imagen final.

Solo debe existir un camino que no mate la semilla para que el resultado final sea correcto. Los colores incorrectos solo ocurren cuando se bloquean todas las rutas desde la semilla correcta hasta un píxel dado.

Si una ruta implica saltos horizontales y verticales alternos, la separación de los ejes hará que esta ruta sea imposible (todos los saltos horizontales se realizarán antes que todos los saltos verticales, haciendo imposible la alternancia). Los saltos diagonales no serán posibles en absoluto. Por lo tanto, se excluirá cualquier ruta que alterne o contenga saltos diagonales. Cada píxel seguirá teniendo una ruta a todos los demás píxeles, pero dado que ahora hay menos rutas, hay más posibilidades de que un píxel dado no reciba la semilla correcta, por lo que el resultado final será más propenso a errores.

Es probable que separar los ejes haga que el algoritmo tarde más

La eficiencia probablemente se reduciría separando los ejes, ya que la inundación ya no se realizaría en paralelo, sino que se repetiría para cada eje. Para 2D esto probablemente tomaría aproximadamente el doble de tiempo, y para 3D aproximadamente 3 veces más.

Esto puede ser algo mitigado por la falta de saltos diagonales, pero todavía esperaría una reducción general de la eficiencia.