El procesamiento de geometría , o procesamiento de malla , es un área de investigación que utiliza conceptos de matemáticas aplicadas , informática e ingeniería para diseñar algoritmos eficientes para la adquisición, reconstrucción , análisis, manipulación, simulación y transmisión de modelos 3D complejos. Como su nombre lo indica, muchos de los conceptos, estructuras de datos y algoritmos son directamente análogos al procesamiento de señales y procesamiento de imágenes . Por ejemplo, cuando el suavizado de la imagen puede convertir una señal de intensidad con un núcleo de desenfoque formado mediante el operador de Laplace ,El suavizado geométrico puede lograrse convolucionando una geometría de superficie con un núcleo de desenfoque formado mediante el operador de Laplace-Beltrami .
Las aplicaciones de los algoritmos de procesamiento de geometría ya cubren una amplia gama de áreas, desde multimedia , entretenimiento y diseño clásico asistido por computadora , hasta computación biomédica, ingeniería inversa y computación científica . [1]
El procesamiento de geometría es un tema de investigación común en SIGGRAPH , la principal conferencia académica de gráficos por computadora y el tema principal del Simposio anual sobre procesamiento de geometría .
El procesamiento de geometrías como ciclo de vida
El procesamiento de geometría implica trabajar con una forma , generalmente en 2D o 3D, aunque la forma puede vivir en un espacio de dimensiones arbitrarias. El procesamiento de una forma implica tres etapas, lo que se conoce como su ciclo de vida. En su "nacimiento", una forma se puede instanciar a través de uno de tres métodos: un modelo , una representación matemática o un escaneo . Después de que nace una forma, se puede analizar y editar repetidamente en un ciclo. Esto suele implicar la adquisición de diferentes medidas, como las distancias entre los puntos de la forma, la suavidad de la forma o su característica de Euler . La edición puede implicar eliminar ruido, deformar o realizar transformaciones rígidas . En la etapa final de la "vida" de la forma, se consume. Esto puede significar que un espectador lo consume como un activo renderizado en un juego o película, por ejemplo. El final de la vida de una forma también se puede definir mediante una decisión sobre la forma, como si satisface o no algunos criterios. O incluso se puede fabricar en el mundo real, mediante un método como la impresión 3D o el corte por láser.
Representación discreta de una forma
Como cualquier otra forma, las formas utilizadas en el procesamiento de geometría tienen propiedades relacionadas con su geometría y topología . La geometría de una forma se refiere a la posición de los puntos de la forma en el espacio , tangentes , normales y curvatura . También incluye la dimensión en la que vive la forma (ej. o ). La topología de una forma es una colección de propiedades que no cambian incluso después de que se hayan aplicado transformaciones suaves a la forma. Se trata de dimensiones como el número de orificios y límites , así como la orientabilidad de la forma. Un ejemplo de una forma no orientable es la banda de Mobius .
En las computadoras, todo debe estar discretizado. Las formas en el procesamiento de geometría generalmente se representan como mallas triangulares , que se pueden ver como un gráfico . Cada nodo del gráfico es un vértice (generalmente en), que tiene una posición. Esto codifica la geometría de la forma. Los bordes dirigidos conectan estos vértices en triángulos, que según la regla de la mano derecha, tienen una dirección llamada normal. Cada triángulo forma una cara de la malla. Estos son de naturaleza combinatoria y codifican la topología de la forma. Además de los triángulos, también se puede utilizar una clase más general de mallas poligonales para representar una forma. Las representaciones más avanzadas, como las mallas progresivas, codifican una representación aproximada junto con una secuencia de transformaciones, que producen una representación fina o de alta resolución de la forma una vez aplicada. Estas mallas son útiles en una variedad de aplicaciones, que incluyen geomorfos, transmisión progresiva, compresión de malla y refinamiento selectivo. [2]
Propiedades de una forma
Característica de Euler
Una propiedad particularmente importante de una forma 3D es su característica de Euler , que alternativamente se puede definir en términos de su género . La fórmula para esto en el sentido continuo es, dónde es el número de componentes conectados, es el número de agujeros (como en los agujeros de rosquilla, ver toroide ), yes el número de componentes conectados del límite de la superficie. Un ejemplo concreto de esto es una malla de un par de pantalones . Hay un componente conectado, 0 agujeros y 3 componentes conectados del límite (la cintura y dos agujeros para las piernas). Entonces, en este caso, la característica de Euler es -1. Para llevar esto al mundo discreto, la característica de Euler de una malla se calcula en términos de sus vértices, aristas y caras..
Reconstrucción de superficies
Reconstrucción de Poisson desde puntos de superficie hasta malla
Dependiendo de cómo se inicialice o "nazca" una forma, la forma podría existir solo como una nebulosa de puntos muestreados que representan su superficie en el espacio. Para transformar los puntos de la superficie en una malla, se puede emplear la estrategia de reconstrucción de Poisson [3] . Este método establece que la función del indicador , una función que determina qué puntos en el espacio pertenecen a la superficie de la forma, se puede calcular realmente a partir de los puntos muestreados. El concepto clave es que el gradiente de la función del indicador es 0 en todas partes, excepto en los puntos muestreados, donde es igual a la normal de la superficie interior. Más formalmente, suponga que la colección de puntos muestreados de la superficie se denota por, cada punto en el espacio por , y la normal correspondiente en ese punto por . Entonces, el gradiente de la función del indicador se define como:
La tarea de reconstrucción se convierte entonces en un problema variacional . Para encontrar la función indicadora de la superficie, debemos encontrar una función tal que se minimiza, donde es el campo vectorial definido por las muestras. Como problema variacional, se puede ver el minimizadorcomo una solución de la ecuación de Poisson . [3] Después de obtener una buena aproximación para y un valor por lo cual los puntos con yacen en la superficie a reconstruir, el algoritmo de cubos de marcha se puede utilizar para construir una malla triangular a partir de la función , que luego se puede aplicar en aplicaciones posteriores de gráficos por computadora.
Registro
Un problema común que se encuentra en el procesamiento de geometría es cómo fusionar múltiples vistas de un solo objeto capturado desde diferentes ángulos o posiciones. Este problema se conoce como registro . En el registro, deseamos encontrar una transformación rígida óptima que alinee la superficie con superficie . Más formalmente, sies la proyección de un punto x desde la superficie en la superficie , queremos encontrar la matriz de rotación óptima y vector de traducción que minimizan la siguiente función objetivo:
Si bien las rotaciones no son lineales en general, las rotaciones pequeñas se pueden linealizar como matrices asimétricas. Además, la función de distancia es no lineal, pero es susceptible de aproximaciones lineales si el cambio en es pequeño. Por lo tanto, se emplea una solución iterativa como el punto más cercano iterativo (ICP) para resolver pequeñas transformaciones de forma iterativa, en lugar de resolver la transformación potencialmente grande de una sola vez. En ICP, n puntos muestrales aleatorios de son elegidos y proyectados sobre . Para muestrear puntos uniformemente al azar a lo largo de la superficie de la malla triangular, el muestreo aleatorio se divide en dos etapas: puntos de muestreo uniforme dentro de un triángulo; y triángulos de muestreo no uniforme, de modo que la probabilidad asociada de cada triángulo es proporcional a su área de superficie. [4] A partir de entonces, la transformación óptima se calcula en función de la diferencia entre caday su proyección. En la siguiente iteración, las proyecciones se calculan en función del resultado de aplicar la transformación anterior en las muestras. El proceso se repite hasta la convergencia.
Suavizado
Cuando se definen o escanean formas, puede haber ruido acompañante, ya sea en una señal que actúa sobre la superficie o en la geometría de la superficie real. La reducción del ruido en el primero se conoce como eliminación de ruido de datos , mientras que la reducción del ruido en el segundo se conoce como carenado de superficie . La tarea del suavizado geométrico es análoga a la reducción del ruido de la señal y, en consecuencia, emplea enfoques similares.
El Lagrangiano pertinente a minimizar se obtiene registrando la conformidad con la señal inicial. y la suavidad de la señal resultante, que se aproxima por la magnitud del gradiente con un peso :
.
Tomando una variación en emite la condición necesaria
.
Al discretizar esto en elementos constantes a trozos con nuestra señal en los vértices obtenemos
donde nuestra elección de es elegido para ser para el laplaciano cotangente y el término es mapear la imagen del laplaciano de áreas a puntos. Debido a que la variación es gratuita, esto da como resultado un problema lineal autoadjunto para resolver con un parámetro: Cuando se trabaja con mallas triangulares, una forma de determinar los valores de la matriz laplaciana es mediante el análisis de la geometría de los triángulos conectados en la malla.
Dónde y son los ángulos opuestos al borde [5] La matriz de masa M como operador calcula la integral local del valor de una función y, a menudo, se establece para una malla con m triángulos de la siguiente manera:
Parametrización
De vez en cuando, necesitamos aplanar una superficie 3D en un plano. Este proceso se conoce como parametrización . El objetivo es encontrar las coordenadas U y V en el que podemos mapear la superficie de manera que se reduzcan al mínimo las distorsiones. De esta manera, la parametrización puede verse como un problema de optimización. Una de las principales aplicaciones de la parametrización de mallas es el mapeo de texturas .
Método de resortes masivos
Una forma de medir la distorsión acumulada en el proceso de mapeo es medir cuánto difiere la longitud de los bordes en el mapeo 2D de sus longitudes en la superficie 3D original. En términos más formales, la función objetivo se puede escribir como:
Dónde es el conjunto de bordes de malla y es el conjunto de vértices. Sin embargo, la optimización de esta función objetivo daría como resultado una solución que mapea todos los vértices a un solo vértice en las coordenadas uv . Tomando prestada una idea de la teoría de grafos, aplicamos el mapeo de Tutte y restringimos los vértices de los límites de la malla en un círculo unitario u otro polígono convexo . Hacerlo evita que los vértices colapsen en un solo vértice cuando se aplica el mapeo. Los vértices no limítrofes se colocan luego en la interpolación baricéntrica de sus vecinos. Sin embargo, el mapeo de Tutte todavía sufre graves distorsiones, ya que intenta igualar las longitudes de los bordes y, por lo tanto, no tiene en cuenta correctamente los tamaños de los triángulos en la malla de superficie real.
Asignaciones conformes de mínimos cuadrados
Otra forma de medir la distorsión es considerar las variaciones en las funciones de coordenadas u y v . El bamboleo y la distorsión aparentes en los métodos de resortes de masa se deben a grandes variaciones en las funciones de coordenadas u y v . Con este enfoque, la función objetivo se convierte en la energía de Dirichlet en u y v:
Hay algunas otras cosas a considerar. Nos gustaría minimizar la distorsión del ángulo para preservar la ortogonalidad . Eso significa que nos gustaría. Además, también nos gustaría que el mapeo tuviera regiones de tamaño proporcionalmente similar al original. Esto da lugar a establecer el Jacobiano de la U y V coordinan funciones a 1.
Al juntar estos requisitos, podemos aumentar la energía de Dirichlet para que nuestra función objetivo se convierta en: [6] [7]
Para evitar el problema de tener todos los vértices mapeados en un solo punto, también requerimos que la solución al problema de optimización debe tener una norma distinta de cero y que sea ortogonal a la solución trivial.
Deformación
La deformación se ocupa de transformar alguna forma de reposo en una nueva forma. Normalmente, estas transformaciones son continuas y no alteran la topología de la forma. Los métodos modernos de deformación de formas basados en mallas satisfacen las restricciones de deformación del usuario en los controles (vértices o regiones seleccionados en la malla) y propagan estas deformaciones de los controles al resto de la forma sin problemas y sin eliminar ni distorsionar los detalles. Algunas formas comunes de deformaciones interactivas se basan en puntos, esqueletos y jaulas. [8] En la deformación basada en puntos, un usuario puede aplicar transformaciones a un pequeño conjunto de puntos, llamados identificadores, en la forma. La deformación basada en el esqueleto define un esqueleto para la forma, que permite al usuario mover los huesos y rotar las articulaciones. La deformación basada en jaulas requiere que se dibuje una jaula alrededor de la totalidad o parte de una forma para que, cuando el usuario manipule puntos en la jaula, el volumen que encierra cambie en consecuencia.
Deformación basada en puntos
Las manijas proporcionan un conjunto escaso de restricciones para la deformación: cuando el usuario mueve un punto, los otros deben permanecer en su lugar.
Una superficie de descanso inmerso en se puede describir con un mapeo , dónde es un dominio paramétrico 2D. Lo mismo se puede hacer con otro mapeo para la superficie transformada . Idealmente, la forma transformada agrega la menor distorsión posible al original. Una forma de modelar esta distorsión es en términos de desplazamientos.con una energía de origen laplaciano. [9] La aplicación del operador de Laplace a estas asignaciones nos permite medir cómo cambia la posición de un punto en relación con su vecindad, lo que mantiene los controles suaves. Por lo tanto, la energía que nos gustaría minimizar se puede escribir como:
.
Si bien este método es invariante en la traducción, no puede tener en cuenta las rotaciones. El esquema de deformación As-Rigid-As-Possible [10] aplica una transformación rígida a cada asa i, donde es una matriz de rotación y es un vector de traducción. Desafortunadamente, no hay forma de conocer las rotaciones de antemano, por lo que elegimos una "mejor" rotación que minimice los desplazamientos. Sin embargo, para lograr la invariancia de rotación local, se requiere una funciónque genera la mejor rotación para cada punto de la superficie. La energía resultante, entonces, debe optimizar tanto y :
Tenga en cuenta que el vector de traducción no está presente en la función objetivo final porque las traducciones tienen un gradiente constante.
Segmentación interior-exterior
Si bien parece trivial, en muchos casos, determinar el interior desde el exterior de una malla triangular no es un problema fácil. En general, dada una superficie planteamos este problema como determinando una función que volverá si el punto está dentro , y de lo contrario.
En el caso más simple, la forma está cerrada. En este caso, para determinar si un punto está dentro o fuera de la superficie, podemos lanzar un rayo en cualquier dirección desde un punto de consulta y cuente el número de veces pasa a través de la superficie. Si estaba afuera entonces el rayo no debe atravesar (en ese caso ) o, cada vez que entra debe pasar dos veces, porque S está acotado, por lo que cualquier rayo que entre en él debe salir. Así que si Está afuera, incluso. Del mismo modo si está adentro, la misma lógica se aplica al caso anterior, pero el rayo debe cruzarse una vez extra por primera vez que se va . Entonces:
Ahora bien, a menudo no podemos garantizar que el está cerrado. Tome el ejemplo de un par de pantalones de la parte superior de este artículo. Esta malla tiene claramente una semántica por dentro y por fuera, a pesar de que tiene agujeros en la cintura y en las piernas.
El intento ingenuo de resolver este problema es disparar muchos rayos en direcciones aleatorias y clasificar como estar adentro si y solo si la mayoría de los rayos se cruzan un número impar de veces. Para cuantificar esto, digamos que lanzamos rayos . Asociamos un numero que es el valor medio de de cada rayo. Por lo tanto:
En el límite de disparar muchos, muchos rayos, este método maneja mallas abiertas, sin embargo, para que sea preciso, se requieren demasiados rayos para que este método sea computacionalmente ideal. En cambio, un enfoque más sólido es el número de bobinado generalizado. [11] Inspirado por el número de bobinado 2D , este enfoque utiliza el ángulo sólido en de cada triángulo en la malla para determinar si está adentro o afuera. El valor del número de bobinado generalizado en, es proporcional a la suma de la contribución del ángulo sólido de cada triángulo en la malla:
Para una malla cerrada, es equivalente a la función característica para el volumen representado por . Por eso decimos:
Porque es una función armónica , se degrada con gracia, lo que significa que la segmentación de adentro hacia afuera no cambiaría mucho si hiciéramos agujeros en una malla cerrada. Por esta razón, el número de bobinado generalizado maneja mallas abiertas de manera robusta. El límite entre el interior y el exterior pasa suavemente sobre los agujeros en la malla. De hecho, en el límite, el número de bobinado generalizado es equivalente al método de proyección de rayos cuando el número de rayos llega al infinito.
Aplicaciones
- Diseño asistido por computadora (CAD)
- Reconstrucción de superficies 3D , por ejemplo , escáneres de alcance en seguridad de aeropuertos, vehículos autónomos, reconstrucción de datos de escáneres médicos
- Registro de imagen al mundo, p . Ej. , Cirugía guiada por imágenes
- Arquitectura , por ejemplo , creación, ingeniería inversa
- Simulaciones de física
- Juegos de computadora, por ejemplo, detección de colisiones
- Modelado geológico
- Visualización (gráficos), por ejemplo , visualizaciones de información , visualizaciones matemáticas
- Mapeado de texturas
- Modelado de sistemas biológicos, p . Ej. modelado de músculos y huesos, seguimiento de manos en tiempo real
Ver también
- Cálculo de variaciones
- Gráficos de computadora
- Gráficos 3D por computadora
- Unidad de procesamiento de gráficos (GPU)
- Diseño asistido por computadora (CAD)
- Imagen digital
- Procesando imagen digital
- Geometría diferencial discreta
- Glosario de topología y geometría diferencial
- Tomografía computarizada industrial
- Lista de software de geometría interactiva
- MeshLab
- Procesamiento de la señal
- Procesamiento de señales digitales
- Procesador de señal digital (DSP)
- Topología
Referencias
- ^ a b Botsch, Mario; Kobbelt, Leif; Pauly, Mark; Alliez, Pierre (2010). Procesamiento de malla poligonal . Prensa CRC . ISBN 9781568814261.
- ^ Hugues Hoppe. "Mallas progresivas" (PDF) .
- ^ a b "Reconstrucción de la superficie de Poisson" . hhoppe.com . Consultado el 26 de enero de 2017 .
- ^ Szymon Rusinkiewicz, Marc Levoy. "Variantes eficientes del algoritmo ICP" (PDF) .
- ^ "Chris Tralie: mallas laplacianas" . www.ctralie.com . Consultado el 16 de marzo de 2017 .
- ^ Desbrun, Mathieu (2002). "Parametrizaciones intrínsecas de mallas de superficie" (PDF) . Eurographics . 21 .
- ^ Levy, Bruno (2002). "Mapas conformes de mínimos cuadrados para la generación automática de atlas de texturas" (PDF) . Transacciones ACM en gráficos . 21 (3): 362–371. doi : 10.1145 / 566654.566590 .
- ^ Jacobson, Alec; Baran, Ilya; Popović, Jovan; Sorkine, Olga (2011). "Pesos biharmónicos acotados para la deformación en tiempo real" (PDF) . Transacciones ACM en gráficos . 30 (4): 1. doi : 10.1145 / 2010324.1964973 .
- ^ Marc, Alexa (2003). "Coordenadas diferenciales para el morphing y deformación de la malla local". La computadora visual . 19 (2): 105-114. doi : 10.1007 / s00371-002-0180-0 . S2CID 6847571 .
- ^ Sorkine, Olga ; Alexa, Marc (2007). "Modelado de superficies tan rígidas como sea posible" (PDF) . Actas del Simposio EUROGRAPHICS / ACM SIGGRAPH sobre procesamiento de geometría : 109-116.
- ^ Jacobson, Alec; Ladislav, Kavan; Sorkine-Hornung, Olga (2013). "Segmentación robusta interior-exterior utilizando números de bobinado generalizados" (PDF) . Transacciones ACM en gráficos . 32 (4): 1. doi : 10.1145 / 2461912.2461916 . S2CID 207202533 .
enlaces externos
- Simposio sobre procesamiento de geometría
- Grupo de modelado de resolución múltiple , Caltech
- Grupo de procesamiento de geometría matemática , Universidad Libre de Berlín
- Grupo de gráficos por computadora , Universidad RWTH Aachen
- Libro de procesamiento de malla poligonal
- Biblioteca de procesamiento de malla poligonal
- Geometría diferencial discreta: una introducción aplicada , notas del curso de Keenan Crane et al.
- Tutoriales en video de la escuela de posgrado SGP 2017
- biblioteca de procesamiento de geometría libigl
- CGAL La biblioteca de algoritmos de geometría computacional (consulte la sección sobre procesamiento de malla poligonal)