En informática, una estructura de datos de conjunto de niveles está diseñada para representar funciones de conjuntos de niveles dinámicos muestreados discretamente.
Un uso común de esta forma de estructura de datos es la representación eficiente de imágenes . El método subyacente construye un campo de distancia con signo que se extiende desde el límite y puede usarse para resolver el movimiento del límite en este campo.
El poderoso método de conjunto de niveles se debe a Osher y Sethian 1988. [1] Sin embargo, la implementación sencilla a través de una densa matriz d-dimensional de valores, da como resultado una complejidad tanto en el tiempo como en el almacenamiento de , donde está la resolución de la sección transversal del espacio. extensiones del dominio y es el número de dimensiones espaciales del dominio.
El método de conjunto de niveles de banda estrecha, introducido en 1995 por Adalsteinsson y Sethian, [2] restringió la mayoría de los cálculos a una banda delgada de vóxeles activos que rodean inmediatamente la interfaz, reduciendo así la complejidad temporal en tres dimensiones para la mayoría de las operaciones. Se requirieron actualizaciones periódicas de la estructura de banda estrecha para reconstruir la lista de vóxeles activos, lo que implicó una operación en la que se accedía a los vóxeles de todo el volumen. La complejidad del almacenamiento para este esquema de banda estrecha todavía era. Las construcciones diferenciales sobre el borde del dominio de banda estrecha requieren esquemas cuidadosos de interpolación y alteración de dominio para estabilizar la solución. [3]
Esta complejidad temporal se eliminó en el método aproximado de conjunto de niveles de "campo disperso" introducido por Whitaker en 1998. [4] El método de conjunto de niveles de campo disperso emplea un conjunto de listas enlazadas para rastrear los vóxeles activos alrededor de la interfaz. Esto permite una extensión incremental de la región activa según sea necesario sin incurrir en gastos generales significativos. Si bien es consistentemente eficiente en el tiempo, el método de conjunto de niveles de campo disperso aún requiere espacio de almacenamiento. Consulte [5] para obtener detalles de implementación.
El método de cuadrícula de bloques dispersos, introducido por Bridson en 2003, [6] divide todo el volumen delimitador de tamaño en pequeños bloques cúbicos de vóxeles cada uno. Luego , una cuadrícula de tamaño aproximado almacena punteros solo a aquellos bloques que intersectan la banda estrecha del conjunto de niveles. La asignación y desasignación de bloques se produce a medida que la superficie se propaga para adaptarse a las deformaciones. Este método tiene una complejidad de almacenamiento subóptima de , pero conserva el acceso en tiempo constante inherente a las redes densas.
El método de conjunto de niveles de octree , introducido por Strain en 1999 [7] y perfeccionado por Losasso, Gibou y Fedkiw, [8] y más recientemente por Min y Gibou [9] utiliza un árbol de cubos anidados cuyos nodos de hoja contienen distancias con signo. valores. Actualmente, los conjuntos de niveles de octárbol requieren un refinamiento uniforme a lo largo de la interfaz (es decir, la banda estrecha) para obtener suficiente precisión. Esta representación es eficiente en términos de almacenamiento y relativamente eficiente en términos de consultas de acceso. Una ventaja del método de nivel en estructuras de datos de octree es que se pueden resolver las ecuaciones diferenciales parciales asociadas con problemas típicos de límites libres que utilizan el método de conjunto de niveles. El grupo de investigación CASL [10] ha desarrollado esta línea de trabajo en materiales computacionales, dinámica de fluidos computacional, electrocinética, cirugía guiada por imágenes y controles.
El método de conjunto de niveles de codificación de longitud de ejecución (RLE), introducido en 2004, [11] aplica el esquema RLE para comprimir regiones alejadas de la banda estrecha solo a su representación de signos mientras se almacena con total precisión la banda estrecha. El recorrido secuencial de la banda estrecha es óptimo y la eficiencia del almacenamiento se mejora aún más con respecto al nivel de octree establecido. La adición de una tabla de búsqueda de aceleración permite un acceso aleatorio rápido, donde r es el número de ejecuciones por sección transversal. Se obtiene eficiencia adicional aplicando el esquema RLE de forma recursiva dimensional, una técnica introducida por DT-Grid similar de Nielsen & Museth. [12]
El método Hash Table Local Level Set, introducido en 2011 por Eyiyurekli y Breen [13] y ampliado en 2012 por Brun, Guittet y Gibou, [14] solo calcula los datos del conjunto de niveles en una banda alrededor de la interfaz, como en la Banda Estrecha. Método Level-Set, pero también solo almacena los datos en esa misma banda. Se utiliza una estructura de datos de tabla hash, que proporciona acceso a los datos. Sin embargo, Brun et al. Concluyen que su método, si bien es más fácil de implementar, funciona peor que una implementación de quadtree. ellos encuentran que
tal como están las cosas, una estructura de datos de cuatro árboles parece más adaptada que la estructura de datos de tabla hash para algoritmos de conjunto de niveles.
Se enumeran tres razones principales de una peor eficiencia:
Corbett en 2005 [15] introdujo el método de establecimiento de niveles basado en puntos. En lugar de utilizar un muestreo uniforme del conjunto de niveles, la función de conjunto de niveles continuo se reconstruye a partir de un conjunto de muestras puntuales no organizadas mediante mínimos cuadrados en movimiento .