Cubrí esto un poco en mi otro comentario, pero creo que aquí estás pensando en la clasificación externa / interna. Al eliminar un vóxel, está cambiando los vóxeles a su alrededor en vóxeles "de borde" (si aún no lo estaban). Esto debería reducirse a 3 casos reales (la simetría le proporciona el resto de ellos): en el ejemplo a continuación, los números son las ID de grupo, el - es el vóxel que se elimina
11 2
1- 1- 1-2
El primer caso es trivial: es una esquina, pero los vóxeles superiores y a la izquierda permanecen completamente conectados a través del otro vóxel.
El segundo caso: es una esquina y el vóxel eliminado ha desconectado los vóxeles superiores e izquierdos que estaban conectados anteriormente
El tercer caso: es una línea, y el vóxel eliminado ha desconectado los vóxeles izquierdo y derecho previamente conectados.
Si identifica que han ocurrido los casos 2º o 3º, necesita hacer una búsqueda de ruta para ver si 1 y 2 todavía están conectados a través de sus otros vóxeles adyacentes.
Sin embargo, puede obtener algo de eficiencia aquí. Si un vóxel es completamente interno a un grupo (es decir, sus 8 vecinos son parte del mismo grupo), entonces se puede descontar. ¿Por qué? Es una cuestión de topología. Imagine el caso 2D: solo hay dos posibilidades. O bien hay un borde único que, independientemente de cómo se tuerce y gire, todavía forma un anillo de vóxeles. O bien, hay dos anillos, uno que contiene un vóxel y otro que contiene el otro. P.ej:
xxx xxx
x x-x x
xxx xxx
o
xxxxxxx
x x
xxx xxx
x-x
xxx xxx
Eso también debería extenderse a 3D, excepto que en lugar de un anillo de límite, tendría una superficie de límite. Entonces, cuando intenta determinar si los dos vóxeles desconectados recientemente todavía están conectados, puede excluir todos los vóxeles internos de su recorrido, porque, por definición, si un vóxel está conectado a cualquiera de los vóxeles límite de un grupo, también es conectado a todos los vóxeles internos en ese grupo.
Es una especie de efecto inverso de los vóxeles del centro del que hablé en mi respuesta a la otra pregunta: no tiene que encontrar el camino de cada vóxel a todos los vóxeles , solo tiene que encontrar el camino hacia los vóxeles interesantes .
Si está utilizando A *, puede utilizarlo aquí.
Comenzando con una lista de los vóxeles que estaban conectados al vóxel eliminado. Comience con el primero en la lista, use A * para encontrar una ruta al segundo en la lista. Si existe una ruta, busque una ruta del segundo al tercero, del tercero al cuarto y así sucesivamente.
La mayoría de esas búsquedas serán muy rápidas, porque los vóxeles estarán uno al lado del otro. Si hay alguna ruta que falla, significa que se ha creado una discontinuidad.
Esto debería ser bastante fácil de implementar si ya tiene implementada la funcionalidad A *.
fuente