Por Mike Krus,
Patrick Bourdot,
Françoise Guisnel, and
Guillaume Thibault
Resumen
Este artículo cubre las técnicas de Simplificación Poligonal para producir Niveles de Detalle (Levels of Detail, LODs). El problema de crear LODs es complejo: ¿cómo pueden ser creadas versiones más simples de un modelo? ¿Cómo puede ser medido el error de aproximación? ¿Cómo puede ser estimada la degradación visual? ¿Puede hacerse todo esto automáticamente? Después de exponer las metas básicas y principios de simplificación poligonal, se comparan recientes algoritmos y se establecen sus cualidades y debilidades.
Los requerimientos de computación y almacenamiento para lasescenas tales como aquellas usadas en aplicaciones de realidad virtual exceden por mucho la capacidad del hardware gráfico de graficación. Estas escenas tienen una estructura compleja y su despliegue requiere un número grande de polígonos no obstante cuando se considera solo la porción de la escena que es visible para el marco dado. Tan temprano como en 1776, Clark sugirió el uso de versiones mas simples de la geometría para objetos que tuvieran menos importancia visual, tales como aquellos lejanos al observador [5].
Estas simplificaciones son llamadas Niveles de Detalle (LODs).
No se cubre aquí las condiciones reales en las cuales estos LODs debieran ser usados y solamente brevemente se mencionan los métodos usados para seleccionar un LOD al tiempo de despliegue. Brevemente, estas simplificaciones pueden ser usadas cuando el objeto aparece pequeño [11], cuando se está moviendo y cuando está en una visión periférica del observador [25]. Reddy evalúa el soporte para la administración de LOD en varios paquetes de software de realidad virtual [19].
Se cubren aquí solo los algoritmos los cuales producen LODs filtrando la geometría para producir un modelo con menos polígonos. Otras técnicas pueden ser usadas [13], tales como la estructura jerárquica [4,17] e impostores [18]. Los algoritmos mas recientes son presentados aquí. Se comparan sus opciones en heurística, y computación y se establecen sus relativas fortalezas y debilidades. Otras revisiones pueden también ser leídas en [10, 24]. Primero se estudian los conceptos básicos involucrados en los niveles de generación de detalles. Entonces discutimos las técnicas involucradas en la simplificacion poligonal y presentamos seis algoritmos recientes. Finalmente, consideramos problemas que deberían ser investigados posteriormente.
La meta de la simplificación poligonal, cuando se usa para la generación de los niveles de detalle, es remover primitivas de una malla original para producir modelos mas simples los cuales retienen la característica visual importante del objeto original. Idealmente, el resultado deberían de ser una serie completa de simplificaciones (como mostrado en la Figura 1, hecha usando [6]), la cual puede ser usada en varias condiciones. La idea, para mantener una tasa de marco constante, es encontrar un buen balance entre lo rico de los modelos y el tiempo que toma para desplegarlos.
Los algoritmos requieren alguna clase de heurística para seleccionar las primitivas relevantes y controlar la simplificación. Se presentan aquí varios criterios que los algoritmos de simplificación deberían considerar. Los identificadores de algoritmo (A1,…,A6) se refieren al número del algoritmo en la siguiente sección.
Figura 1 - Usando LODs para objetos distantes.
Como establecido anteriormente, se necesita una serie de simplificaciones a ser seleccionadas al tiempo de despliegue. Si esta lista es continua, es decir dos LODs sucesivos difieren por solamente uno o dos polígonos, es llamada geomórfica (ver Figura 2 tomada de [9]). Los algoritmos A1 y A2 producen estructuras de datos de las cuales cualquier simplificación puede ser recuperada. Tales estructuras de datos habilitan un despliegue suave de LODs y el cambio de uno al siguiente no es notable.
Figura 2 - Una sucesión de LODs
La práctica mas común es producir un número limitado de LODs. Ya que las diferencias de LODs son entonces mas grandes, la conmutación de uno a otro es comúnmente notable por el observador (esto es conocido como el efecto popping). La principal dificultad en este caso es calcular cuales niveles de simplificacion pudieran ser necesitados en la escena.
La simplificación debe de conducirse de tal forma que la forma general y las características que hacen que el objeto sea identificable fácilmente sean preservadas. Entonces, los algoritmos tienen que mirar por algunas formas distintas del objeto:
La mayoría de los algoritmos buscan bordes pronunciados (A2, A4, A6), bordes colineales conectados (A6) y caras adyacentes coplanares (A2, A3, A4, A5, A6).
Pero cuando se prueba, por ejemplo por caras coplanares, los algoritmos tienen un valor de umbral para el ángulo entre las normales, arriba del cual las caras no son consideradas planares. Mientras mas alto sea este valor, más caras serán consideradas coplanares y será simplificado. Pero ajustar el umbral no es fácil. Reddy en [20] usa las características de la percepción visual humana para estimar este umbral, pero es más a menudo dejado al usuario y es aún un asunto de prueba y error. Mientras que los algoritmos recientes son mas flexibles que los antiguos, la mayoría son apropiados para algunos tipos de objetos, como aquellos usados en aplicaciones médicas las cuales rara vez tienen bordes pronunciados.
Para controlar la simplificación, el error de aproximación debería de ser medido localmente (en cada primitiva). Pero para que el usuario sea capaz de especificar la simplificación, una cota global debería ser puesta para el error. Algunos algoritmos usan una cota para el error local (A2, A3) o una distancia a la malla original (A1, A5). Otros usan una construcción geométrica para asegurar que la simplificación no exceda un cierto límite (A4, A6). Un uso para la medida del error es determinar si una simplificación puede ser usada ya que sus diferencias con el modelo original pueden no ser notables. Pero solo A4 implementa esta en una manera útil.
La mayoría de los algoritmos permite al usuario especificar el límite superior para la aproximación del error local. Esto no es muy intuitivo y requiere alguna práctica. Alternativamente, algunos algoritmos permiten al usuario especificar cuantos polígonos deberían de ser dejados en la simplificación.
Durante el curso de la simplificación, una opción que el algoritmo puede tener es simplificar la topología. Por ejemplo, Las simplificaciones pueden conducir a llenar un hoyo o partir un objeto dentro de varias partes no conectadas. Al permitir que la topología sea modificada deja más espacio para simplificación, el resultado es raramente útil ya que las diferencias con el objeto original son demasiado notables. A2 y A3 permiten, pero desalientan, la simplificación de la topología.
Es algunas veces interesante permitir que la cantidad de simplificación varíe a través de la malla, para preservar algunas partes, no obstante simplificar otras más agresivamente. Esta clase de adaptividad involucra principalmente consideraciones visuales semánticas que pueden ser hechas a priori y son controladas por el usuario. Unos pocos algoritmos soportan este tipo de simplificación adaptable (A1, A2, A4). Otros problemas ocurren cuando el tamaño del objeto es grande con respecto a la escena. En tales condiciones, alguna parte del objeto estará constantemente en el frente y la mayoría del detalle será siempre usado. El objeto debería de partirse en varias piezas, cada una de las cuales podría tener un número de LODs de los cuales escoger. Sin embargo, no hay manera universal de partir el objeto y la continuidad deberá ser mantenida entre dos piezas adyacentes así que no aparezcan errores cuando dos piezas son simplificadas independientemente. El algoritmo de simplificacion deberá tomar cuidado de esto.
A1 y A2 permiten al usuario insertar detalles en partes específicas del modelo después que la simplificación ha tomado lugar. Otra alternativa podría ser el usar una estructura jerárquica para describir los varios niveles de detalle. Seleccionar un LOD podría entonces consistir en cortar el árbol, seleccionar los nodos detallados de bajo nivel, para las partes del objeto que son cercanas al observador y al nivel más alto, y nodos más simples para aquellos que están alejados [17].
Como establecido en [2], unos pocos operadores simples (ningún formalismo matemático es implicado aquí) puede ser usado para remover primitivas de un modelo:
Estos operadores simples aparecen en paquetes comerciales tales como SGI's Cosmo Worlds (ver http://vrml.sgi.com/worlds). Sin embargo, ellos deben ser usados dentro de alguna clase de mecanismos de control para guiar la simplificación.
Los algoritmos de simplificación poligonal caen en tres diferentes categorías. Las figuras de esta sección están inspiradas de [10].
Geometría de la Remoción
Los algoritmos en esta categoría producen una versión simplificada de un modelo mediante la selección de un número de primitivas las cuales deben ser removidas. La selección es hecha usando alguna clase de heurística. Por ejemplo, en la Figura 3, el algoritmo identifica vértices los cuales están cerca de regiones planares. Este criterio es disminuido en cada interacción hasta que ningún vértice adicional pueda ser removido. Este tipo de simplificación es la más popular entre los algoritmos recientes. Hinker y Cansen [14] usaron esta técnica con un criterio de planaridad. Muchos de los algoritmos presentados aquí son de esta categoría, pero ellos varían en sus opciones de heurística y su manera de medir la aproximación del error.
Figura 3 - Geometría de la Remoción
Subdivisión Adaptiva
Esta categoría construye una simplificación inicial la cual es la versión más simple del modelo original. Esta entoncés añade más detalles en el modelo al subdividir este así que se obtiene una cercanía al modelo original. Este entonces es subdividido y la posición de cada nuevo vértice es cambiada para tener más cercanía a la superficie original. Este tipo de simplificación no es tan popular como las previas ya que construir la simplificación inicial no es simple en el caso general. Un caso simple es los campos de altura y ha sido estudiado por De Haemer y Zyda en [7]. Solamente uno de los algoritmos presentados aquí pertenecen a esta categoría.
Figura 4 - Subdivisión Adaptativa
Muestreo
Finalmente, los algoritmos en esta categoría escogen un cierto número de primitivas que deberían de ser preservadas (como opuesto a la primera categoría, la cual escoge primitivas que deberán ser removidas). Una manera de seleccionar estas primitivas es haciendo una selección pseudoaleatoria, basada en alguna clase de heurística. Otro método más poderoso es muestrear el modelo y escoger un representativo único para cada grupo de la muestra. Por ejemplo, mientras que esté embebido el modelo en una rejilla uniforme de 3D, un vértice puede ser escogido en cada celda para reemplazar todos los otros vértices en su celda.
Rossignac y Borrel [22] pesan cada vértice usando una función de la curvatura local y la longitud de los vértices adyacentes. Entonces usando una rejilla 3D, todos los vértices en cada celda son reemplazados por el de mayor peso. Una nueva malla se genera entonces al remover todos los bordes y caras que han sido colapsadas. Esta técnica ya no se usa, debido fundamentalmente a que es difícil de escoger las muestras en una manera que preserva la forma global de los objetos.
Figura 5 - Sampling
Se presentan aquí seis algoritmos que fueron introducidos durante los dos últimos años. Se realzan sus principales características y sus opciones con respecto a las características presentadas en las secciones previas.
A1 - Análisis de Mallas Arbitrarias de Multiresolución [9]
Esto no es realmente un algoritmo de simplificación, sino un preprocesador para otro algoritmo el cual produce una representación de multiresolución de una malla [8] el cual es un geomorfo compacto conteniendo una malla base simple y una serie de coeficientes "wavelet" que son usados para introducir detalles dentro de la malla. De esta representación, una nueva malla puede usar una subdivisión recursiva (es decir, donde cada triángulo es subdividido usando un operador de partición 4 a 1) hasta que la cantidad deseada de detalle es alcanzada. Semejante malla es encodificada dentro de una representación de multiresolución. El algoritmo que se presenta aquí puede ser usado para convertir cualquier malla a una en la cual se tiene la propiedad de subdivisión recursiva.
Figura 6 - Cuatro pasos en el algoritmo MRA tomado de [9]
Este algoritmo es uno de subdivisión adaptiva el cual preserva la topología, pero identifica cualquier forma característica en la malla. El error de aproximación es medido usando la distancia a la malla original. Los mapas armónicos son usados en varios pasos para parametrizar una malla 3D dentro de una triangulación planar. El algoritmo tiene cuatro pasos principales:
Este algoritmo es atractivo en su formalismo matemático. Produce un amplio rango de simplificación y no obstante detalles que pueden ser añadidos en partes específicas de la malla. Pero esto es computacionalmente caro también. Además, extrayendo una malla válida desde una representación basada en "wavelet" es caro.
A2 - Mallas Progresivas [16]
Este algoritmo de remoción geométrico también produce geomorfas y es derivado de un algoritmo mas antiguo [15]. Este busca áreas planares y bordes característicos. La simplificación es hecha aplicando un operador colapso de borde, donde un colapso de borde produce un nuevo vértice removiendo las dos caras y un vértice. El resultado es una malla de base simplificada y series de particiones de vértice las cuales son un inverso de los colapsos de borde y son usadas para introducir detalles dentro de la base de la malla. Esto es llamada Malla Progresiva y un amplio número de simplificaciones pueden ser extraídas de este.
La característica mas importante de este algoritmo es que toma en cuenta información tal como color, textura, y discontinuidades normales sobre la superficie de cada malla. Las formas importantes del modelo las cuales son representadas por esta clase de información (y no por simple geometría) son también preservadas. Por ejemplo, la Figura 7 muestra como las ventanas de un avión son preservadas.
Figura 7 - Ejemplo de un Malla Progresiva Tomada de [16]
La minimización de una función de energía es usada para guiar la simplificación. Esta función tiene cuatro términos. El primero asegura que la malla simplificada permanece cercana a la original. La segunda favorece triángulos con mejores proporciones. El tercer término desalienta la simplificación de discontinuidades de color y textura. Finalmente, el último término desalienta la simplificación de las discontinuidades topológicas y normales.
Los pasos básicos del algoritmo son estos:
A3 - Aproximación de Rango Completo de Poliedros Triangulados [21]
Este algoritmo de remoción geométrica preserva áreas planares pero no la topología. Este usa un operador de región de combinación, el cual es burdamente equivalente a un colapso de borde. Uno de los vértices iniciales es usado como un resultado del operador. El error de aproximación es medido usando la distancia a la malla original.
Semejante al algoritmo previo, este usa una función de energía la cual tiene dos términos. El primero, el error local de teselación asegura que la orientación de las normales es preservada y que las nuevas caras no se traslapan. El segundo término, el error local geométrico, preserva a la malla de moverse demasiado lejos de la original. Los pasos básicos del algoritmo son como sigue:
No obstante las suposiciones básicas son bastante diferentes, uno puede notar que este algoritmo es muy similar al previo. Este también es mucho más eficiente en preservar las características de los objetos que lo que fue su antecesor [22].
A4 - Simplificación por Sobres [6]
Este algoritmo de remoción geométrica fue inicialmente concebido por Varshney [23]. Este preserva áreas planares y bordes agudos, tan bien como la topología. La principal meta de este algoritmo es no usar la medida del error sino solamente la construcción geométrica para controlar la simplificación. La Simplificación por Sobres son dos superficies construidas una de cada lado de la supeficie original usando un distancia (offset) especificada por el usuario y asegurando que estas superficies no se autointersectan. El espacio entre las dos superficies es entonces usado para construir una nueva superficie, la única restricción entonces es que los nuevos polígonos no deberían de intersectar con cualquier superficie. Esta reconstrucción puede ser hecha en varias maneras, de las cuales aquí se presentará solamente una.
La cantidad de simplificación es controlada por la distancia (offset) usada para construir las superficies. El caso donde las superficies del sobre son más probables a intersectarse es a lo largo de los bordes agudos de la malla original, donde no habrá mucho espacio para construir una de las superficies. Las superficies que se auto entersectan deben entonces ser movidas mas cercanas a la malla original hasta que la condición es corregida. Entonces, cerca de los bordes agudos los espacios entre las dos superficies serán mas pequeños y más pocas simplificaciones serán permitidas. Inversamente, en las áreas planares, la distancia será máxima y así será la simplificación.
Figura 8 - Construyendo sobres internos y externos para un triángulo tomado de [6].
El algoritmo inicia construyendo los sobres (Figura 8):
Esta manera interactiva de construir las superficies distancia (offset) produce resultados no óptimos, es decir los sobres son algunas veces más cercanos a la malla original que lo que ellos deberían de ser. Calcular la solución optima requiere evaluar los bordes Voronoi en el espacio 3D, el cual computacionalmente es muy caro.
El algoritmo entonces actúa generando la malla simplificada. Para cada vértice de la malla inicial:
Este algoritmo es atractivo ya que no usa cualquier medida del error. Los sobres son el único control sobre la simplificación. Es computacionalmente caro no obstante, especialmente durante la fase de construcción del sobre.
A5 - Simplificacion de Superficie Dentro de un Volumen de Tolerancia [12]
Este algoritmo de remoción geométrica es una combinación de A3 y de una versión inversa de A4. Este remueve bordes como en A3, pero el control es hecho usando la Tolerancia de Volumen. Pero, como en A4 el volumen fue construido alrededor de la superficie original, en este algoritmo es construido alrededor de la superficie simplificada y la superficie simplificada es restringida para no permitir a la superficie original salirse del volumen de tolerancia. La cantidad de simplificación es controlada por el grosor de ese volumen.
El volumen de tolerancia es calculado como una esfera alrededor de cada vértice y representa la acumulación del error introducido por simplificación el cual conduce a la creación del vértice (por la aplicación del operador de colapso de borde). Este es entonces interpolado a través de los bordes y caras Figura 9.1 y 9.2 respectivamente). Una de las propiedades agradables del algoritmo es asegurar que el volumen del objeto no es cambiado por la simplificación (dentro de una tolerancia dada). Esto es muy útil para algunos dominios de aplicación tales como la visualización de datos médicos.
Figura 9 - La construcción y el mantenimiento del volumen de tolerancia tomado de [12].
Los pasos básicos del algoritmo son los siguientes. La simplificación inicial es simplemente una copia de la malla original. Los volúmenes de error se ponen en valor nulo. Para cada borde por orden de aumento de longitud:
A6 - Simplificación de Malla [1]
Este algoritmo de remoción geométrica es original en que no mide el error de aproximación, excepto que usa un proceso de agrupamiento para asegurar que la simplificación es restringida en ciertas áreas. Este agrupamiento es hecho mediante la búsqueda de bordes característicos y áreas planares. Los bordes característicos son aquellos que están compartidos por caras las cuales forman una ángulo más grande que un umbral dado. Típicamente, hay muchos bordes característicos en áreas donde hay pocas caras coplanares.
Figura 10 - Pasos en el Algoritmo de Simplificación de Malla Inspirado por [1].
El algoritmo hace las siguientes operaciones:
Este algoritmo es atractivo por su simplicidad, pero la simplificación no es siempre óptima. Mejores resultados pueden ser obtenidos gradualmente incrementando los umbrales de planaridad y colinealidad mientras el algoritmo procede.
Deberá ser obvio de la sección previa que, no obstante la mayoría de los algoritmos tienen un único camino de controlar y aplicar la simplificación, el proceso básico es siempre el mismo: buscar áreas planares, simplificarlas, buscar bordes agudos, preservarlos. Sin embargo, otras distinciones pueden ser hechas y adicionales mejoras deberán ser estudiadas.
MEJORAS ADICIONALES
Más simplificación avanzada pudiera ser realizada si la información considerada en los algoritmos fuera diferente de la geométrica.
COLORES, TEXTURA Y OTRA INFORMACION
De los algoritmos presentados aquí, A2 es el único que usa información tal como color y textura. Pero como los modelos se mejoran, esta clase de datos serán más y más vitales al usuario. Ellos hacen el objeto más identificable y entonces debería ser preservado. Esta simplificación debería ser hecha usando la característica de la percepción visual humana.
INFORMACION TOPOLOGICA
La mayoría de los algoritmos que se vieron tratan de extraer información topológica de la geometría, tal como donde los bordes agudos pudieran ser. Sin embargo, ya que tal información no está presente en el modelo, este no puede ser simplificado como tal. Por ejemplo, si el algoritmo tuviera el conocimiento que un borde agudo era de hecho un círculo topológico, este pudiera ser capaz de cambiar dentro de algo más simple, tal como un pentágono.
Adicionalmente, los cambios en el color y las texturas deberían ser tratados en la misma manera como discontinuidades topológicas en la geometría. Un algoritmo de creación de LOD basado en un modelo topológico unificando geometría, color y textura debería de ser investigado.
RELACION A OTROS MODELOSBASADOS EN PRIMITIVOS NO POLIGONALES
Mientras que el hardware mas moderno de realidad virtual en tiempo real
usa polígonos primitivos, los modelos son comúnmente producidos usando paquetes de CAD los cuales manipulan niveles primitivos mas altos tales como superficies paramétricas. En este contexto, [3] presenta un modelo para adaptivamente seleccionar un ensamble de parches paramétricos, mediante la suavización para un punto de vista dado y produciendo una aproximación simplificada poligonal de la superficie.
Adicionalmente, estos modelos contienen información topológica la cual pudiera ser usada. Entonces, podría ser interesante concebir un modelo para la integración de modelos basados en volumen y basados en superficie así como modelos poligonales dentro del mismo algoritmo de simplificación.
CONCLUSION
Nuevos algoritmos de simplificación poligonal son ahora capaces de producir niveles satisfactorios de detalles con respecto a los requerimientos visuales y geométricos. Sin embargo, no importa cual algoritmo es usado, mucha práctica es todavía requerida antes de ser capaz de predecir la cantidad de simplificación y especificar los valores correctos para los varios parámetros. Además, los algoritmos no usan la características de la percepción humana visual para poner estos parámetros. La generación de LOD permanece mucho como una actividad de modelación.
Por otro lado, la complejidad de los objetos involucrados en simulaciones de realidad virtual aumenta cada día. La información de textura y luz (tal como la producida por el cálculo de la radiosidad) es añadida para producir presentaciones mas realísticas. Entonces los algoritmos deben evolucionar para tomar en cuenta esta información y adaptarlos durante el proceso de simplificación.
Finalmente, la creación y selección de LODs debería de ser integrada a técnicas de administración de escenas [5]. El cálculo de la relación de la partición y la visibilidad de escena puede ayudar a la simplificación en la selección de la cantidad de simplificación que es requerida para una escena particular.
Lectura adicional puede ser encontrada en la página de WWW del Nivel de Detalle del autor (http://www.limsi.fr/Individu/krus/CG/LODS/).
Mike Krus
is a PhD student of the Univerisity
Paris XI, Orsay, France. His work was initiated by the
LIMSI/CNRS, a public
research laboratory, and
Electricité de France
, a public electrical
utility.
Contact: EdF/DER - IMA/TIEM/CAO, 1, av du Gle de Gaulle, 92141 Clamart
Cedex.
Tel: +33 1 47 65 42 73. Fax: +33 1 47 65 34 24.
Email: Michael.Krus@der.edfgdf.fr
.
Patrick Bourdot
is a researcher in Computer Graphics at
LIMSI (Paris
XI University - Orsay), a laboratory of the French
National Center for Scientific
Research
(CNRS). After a diploma of Architect (1986), he obtained in 1992 a
Ph. D. in Computer
Science at the University of Aix-Marseille III. His main interests are
levels of detail on
parametric surfaces by a hierarchical and multiple sub-definition approach, 3D
reconstruction with parametric curves and surfaces from image analysis,
knowledge
representation to manage "reactive" objects in 3d modelling, multimodal user
interfaces
with vocal interaction and graphic recognition for CAD systems.
Contact: LIMSI/CNRS, BP 133, 91403 Orsay Cedex.
Tel: +33 1 69 85 81 21. Fax: +33 1 69 85 80 88.
Email: pb@limsi.fr.
Françoise Guisnel
is a researcher in virtual reality at the CAD group of
Electricité
de France's
Research and Development Division.
Contact: EdF/DER - IMA/TIEM/CAO,
1, av du Gle de Gaulle, 92141 Clamart Cedex.
Guillaume Thibault
is a researcher in virtual reality at the CAD group of
Electricité
de France's
Research and Development Division.
Contact: EdF/DER - IMA/TIEM/CAO,
1, av du Gle de Gaulle, 92141 Clamart Cedex.
![Cuatro pasos en el algoritmo MRA tomado de [9]](/crossroads/xrds3-4/gfx/lodF6.jpg)
