ES2251497T3 - Refinamiento de una malla triangular en tres dimensiones. - Google Patents

Abstract

Procedimiento de refinamiento de una malla representativa de un objeto en tres dimensiones, estando dicha malla constituida por una disposición de vértices y caras, comprendiendo dicho procedimiento una etapa de selección de al menos una región de interés sobre la cual se efectúa localmente el citado refinamiento de la malla, caracterizado porque la o las citadas regiones de interés pertenecen a un grupo que comprende: - al menos una silueta de dicho objeto en tres dimensiones; - caras de dicha malla que pertenecen a una zona animada de dicho objeto.

Description

Refinamiento de una malla triangular en tres dimensiones.

El campo de la invención es el del tratamiento de imágenes. Más precisamente, la invención se refiere al tratamiento de imágenes producidas a partir de mallas poligonales, y particularmente de mallas triangulares. Más precisamente aún, la invención se refiere al refinamiento de mallas triangulares o trianguladas representativas de objetos en tres dimensiones.

La invención permite el desarrollo de servicios de gran valor añadido y de interfaces hombre máquina evolucionadas. Encuentra particularmente aplicaciones en el campo de la transmisión de contenidos interactivos, de telecomercio, de las aplicaciones culturales, del juego y/o del trabajo colaborador.

Las mallas constituyen cada vez más frecuentemente el soporte de representaciones de los objetos, particularmente en una escena de realidad virtual. Representan así la mayor parte de la cantidad de información que describe una tal escena. De manera clásica, una malla se define por un conjunto de vértices y de caras (o un conjunto de vértices, de aristas y de orientaciones) que definen una topología.

Son conocidas muy numerosas técnica de compresión de imágenes, para reducir la cantidad de datos necesaria para representar una imagen o una secuencia de imágenes animadas. Se busca así, particularmente, reducir los caudales de señales numéricas, en vista de su transmisión y/o su almacenamiento en un soporte de datos.

Conjuntamente, la imagen o la secuencia de imágenes visuales sobre un terminal de destino debe ser de la mejor calidad posible, o como mínimo, de un nivel de calidad predeterminado.

Es pues particularmente importante mejorar la calidad de percepción de las imágenes producidas a partir de mallas, al tiempo que se reduce al mínimo la cantidad de informaciones producidas.

La invención se aplica principalmente, pero no exclusivamente, a la visualización de imágenes en un terminal, o a la visualización de objetos que componen una escena tridimensional en el curso de la transmisión progresiva.

La invención se aplica igualmente a cualquier tipo de formación de mallas poligonal vinculada a datos del tipo de imagen o vídeo, que pueda constituir el objeto de una triangulación.

Las superficies de subdivisión son cada vez más ampliamente utilizadas en el campo de la información gráfica, en razón de su gran eficacia para mejorar el resultado de las superficies curvas, la codificación, la transmisión y la modelación de las imágenes.

Las técnicas de subdivisión de superficies definidas por mallas triangulares son particularmente descritas en el documento SIGGRAFH 99 ("Subdivision for Modeling and Animation" ("Subdivisión para la modelación y animación"), por Denis Zorin). Las mallas o formaciones de mallas triangulares pueden ser seguidamente refinadas por interpolación, que conserva los vértices de la formación de mallas original y genera una superficie que posee una C^{1}-diferenciabilidad (Dyn, Levin y Grgory, "A butterfly subdivision scheme for suface interpolation with tension control" ("Procedimiento de subdivisión en mariposa para interpolación de superficie con control de tensión"), ACM Transaction on Graphics 9, 2 (Abril 90), 160-169), o por aproximación.

Loop (Smooth Surface Subdivision based on Triangles'' ("Subdivisión regular de superficie basada en triángulos"), University of Utah, Department of Mathematics, Master's Thesis, 1987)) ha propuesto, en 1987, un método de generación de mallas triangulares por subdivisión global 1 en 4. La superficie así obtenida posee entonces C^{2}-diferenciabilidad sobre cada uno de sus vértices, salvo en los vértices extraordinarios de la malla original, que presentan una C^{1}-diferenciabilidad (se define un vértice ordinario como un vértice que posee una valencia igual a 6, y un vértice extraordinario de una malla triangular, como un vértice que posee una valencia diferente de 6).

Por consiguiente, Hoppe (Hoppe et al., "Piecewise Smooth Reconstruction" ("Reconstrucción regular de superficie por partes"), SIGGRAPH 94 Conferencia Proceedings) ha desarrollado en 1994 una versión adaptativa del método propuesto por Loop. La ejecución de una tal técnica permite obtener una superficie que conserva y reconstruye las singularidades geométricas tales como las aristas vivas, las esquinas y las puntas de los objetos. Se construye así una superficie lisa por partes que posee una continuidad sobre las curvas que componen las aristas vivas, proporcionando al propio tiempo una diferenciabilidad sobre los elementos de superficie que componen la malla.

Un inconveniente de estas técnicas de la tecnología anterior es que no permiten adaptar la imagen al punto de vista de un observador virtual. En efecto, tales técnicas no tienen particularmente en cuenta las siluetas (por silueta se entiende aquí el conjunto de las aristas de la malla que pertenecen a dos caras, una de las cuales está orientada frente a una cámara virtual, y la otra está orientada en sentido opuesto), la pirámide de visión y la orientación de las caras de los objetos frente a una cámara o al ojo de un observador. De ello resulta principalmente una "sobrecodificación" de las zonas poco o nada visibles, o menos pertinentes, en detrimento de las zonas importantes sobre el plano
visual.

Otro inconveniente de estas técnicas de la tecnología anterior es que no permiten hacer coexistir diferentes niveles de detalle en una malla triangular representativa de un objeto.

Todavía otro inconveniente de estas técnicas de la tecnología anterior es que no permiten hacer óptima la relación de la calidad perceptible a la calidad de información necesaria (es decir, al número de triángulos necesarios a la visualización de una imagen sobre un terminal gráfico, por ejemplo).

Estas técnicas tienen todavía por inconveniente, en su mayor parte, el poner en marcha un operador de subdivisión 1 en 4. Un tal operador presenta en efecto un coeficiente multiplicador de 4, lo que limita la coexistencia armoniosa de las diferentes densidades de detalle en el seno de la imagen, y genera una representación del objeto de granularidad grosera. Además, si se desea afinar la granularidad del objeto, estas técnicas resultan muy rápidamente costosas en memoria.

La invención tiene principalmente por objetivo paliar estos inconvenientes de la técnica anterior.

Más precisamente, un objetivo de la invención es el de suministrar un procedimiento de refinamiento visual continuo de mallas triangulares.

Otro objetivo de la invención es poner en marcha un procedimiento de refinamiento de mallas triangulares que dependa del punto de vista de un observador virtual.

La invención tiene todavía por objetivo proporcionar un procedimiento de refinamiento de mallas triangulares que permita optimizar la relación de la calidad de percepción a la cantidad de información.

La invención tiene igualmente por objetivo poner en marcha un procedimiento de refinamiento de mallas triangulares particularmente bien adaptado a las superficies curvas.

Todavía otro objetivo de la invención es proporcionar un procedimiento de refinamiento de mallas triangulares adaptado a las superficies que comprenden zonas triangulares a conservar, y que permite preservar singularidades geométricas tales como esquinas o aristas vivas.

La invención tiene todavía por objetivo realizar un procedimiento de refinamiento de mallas triangulares rápido, robusto y reversible.

Otro objetivo de la invención es el de proporcionar un procedimiento de refinamiento de mallas triangulares simple y poco costoso de realizar.

Todavía otro objetivo de la invención es realizar un procedimiento de refinamiento de mallas triangulares que pueda ser adaptado al terminal en el cual la imagen o la secuencia de imágenes es sintetizada y después visualiza-
da.

La invención tiene todavía por objetivo suministrar un procedimiento de refinamiento de mallas triangulares que permita obtener una granularidad fina de refinamiento.

La invención tiene igualmente por objetivo realizar un procedimiento de refinamiento de mallas triangulares que permita obtener una coexistencia armoniosa de diferentes niveles de detalle en el seno de la imagen visualiza-
da.

Estos objetivos, así como otros que aparecerán a continuación se consiguen con la ayuda de un procedimiento de refinamiento de una malla triangular representativa de un objeto en tres dimensiones (3D), estando dicha malla constituida por una disposición de vértices y de caras triangulares, definidas cada una por tres referencias a los vértices que une, y que presenta tres aristas que unen cada una dos de los citados vértices.

Un tal procedimiento comprende, según la invención, una etapa de selección de al menos una región de interés, siendo efectuado dicho refinamiento localmente sobre dicha al menos una región de interés.

Así, la invención reposa sobre una solución completamente nueva e inventiva del refinamiento de una malla triangular representativa de un objeto en tres dimensiones. En efecto, la invención reposa principalmente en la puesta en marcha de un refinamiento localizado sobre las regiones pertinentes de los objetos desde el punto de vista de la percepción, no en el refinamiento global del conjunto de las mallas. Una tal localización del refinamiento sobre ciertas regiones de interés permite así optimizar la relación calidad de percepción sobre cantidad de información producida, siendo fuertemente tratadas únicamente las regiones importantes desde el punto de vista de la percep-
ción.

Ventajosamente, un tal procedimiento según la invención comprende además una etapa de subdivisión híbrida de al menos ciertas de las citadas caras triangulares, poniendo en ejecución una operación de subdivisión 1 en 3 baricéntrica, de manera que se divide cada una de dichas caras en tres caras triangulares por la adición de un vértice.

Una subdivisión de 1 en 3 presenta, en efecto, un coeficiente multiplicador inferior a los coeficientes de las técnicas de la tecnología anterior (generalmente 4) y permite así obtener una granularidad más fina de las imágenes. El coste en memoria, evaluado en número de triángulos necesarios para la constitución de la malla, es igualmente menor y crece menos rápidamente que con un operador de subdivisión uno en cuatro.

Según una primera característica ventajosa de la invención, un tal procedimiento comprende además una etapa de permutación de aristas de al menos algunas de dichas caras triangulares subdivididas, consistente en suprimir cada arista de la cara triangular antes de la subdivisión y en sustituirla por una arista que une el vértice añadido al vértice opuesto a la arista suprimida de la cara triangular adyacente.

La puesta en ejecución de una operación de permutación de aristas, combinada con la subdivisión 1 en 3 baricéntrica permite, en efecto, una coexistencia armoniosa de los diferentes niveles de detalle inducidos por la realización de un refinamiento local de las mallas. Además, incrementando la subdivisión triangular 1 en 3 la valencia de los vértices de la malla original (es decir, el número de aristas que llegan a los vértices), la operación de permutación de arista permite simultáneamente evitar una degeneración de los triángulos constitutivos de la malla.

Preferentemente, la citada etapa de selección es puesta en ejecución por un operador y/o según un criterio de detección predeterminado.

En efecto, las regiones de interés pueden ser definidas explícitamente por un operador (es decir un usuario de un terminal en el cual es visualizada la imagen fuente, o un infografista, por ejemplo) y/o deducidas de una fase de detección de las regiones juzgadas visualmente pertinentes, tales como las regiones de fuerte gradiente de claridad, o las siluetas, por ejemplo.

Ventajosamente, cuando dicha etapa de selección es puesta en ejecución según un criterio de detección predeterminado, dicha al menos una región de interés pertenece a un grupo que comprende:

-

caras triangulares situadas en el interior de una pirámide de visión definida por el ojo de un observador y una ventana de visualización;

-

caras triangulares orientadas frente al ojo del observador;

-

caras triangulares adyacentes a un conjunto de aristas que comparten cada una dos caras triangulares, estando una primera cara orientada frente al ojo de un observador y estando una segunda cara en orientación opuesta;

-

caras triangulares que pertenecen a zonas animadas de dicho objeto (los labios de un clon virtual, los arcos de las pestañas durante una mímica de un personaje, etc.).

Así, las regiones de interés seleccionadas son regiones juzgadas visualmente pertinentes para un observador de la malla. Puede, en efecto, parecer inútil refinar las zonas de la malla que no sean visibles o sean poco visibles para el observador, teniendo en cuenta el punto de vista corriente. Las regiones de interés seleccionadas pueden ser igualmente las siluetas de los objetos observados, que juegan un papel privilegiado en los procesos cognoscitivos. Es, en efecto, particularmente importante refinar las superficies curvas de la silueta del objeto, que aparecen bajo la forma poligonal cuando se describen de manera demasiado sucinta para una red de mallas.

Las regiones de interés pueden también ser regiones animadas del objeto visualizado, fijándose la mirada de un observador preferentemente sobre tales regiones.

Según una segunda característica ventajosa de la invención, un tal procedimiento comprende además una etapa de filtrado de la posición de antes de la subdivisión de al menos algunos vértices de la malla.

Un filtrado de la geometría de la malla permite así obtener constricciones diferenciales del tipo C^{2} sobre la región de interés obtenida después de una infinidad de subdivisiones triangulares 1 en 3. Aquel permite principalmente suavizar las siluetas de los objetos refinados.

Según una técnica ventajosa, la citada etapa de filtrado de la posición antes de la subdivisión de un vértice de la malla tiene en cuenta la valencia de dicho vértice y la valencia de los vértices adyacentes, siendo la valencia el número de aristas que llegan a un vértice.

Según un modo de realización preferida de la invención, la citada etapa de filtrado pone en ejecución un cálculo de coeficientes de ponderación para cada valencia, obtenido por análisis del comportamiento asintótico de una matriz de subdivisión global estocástica.

Ventajosamente, un tal procedimiento según la invención pone en ejecución al menos una constricción que permite impedir la puesta en ejecución de la citada etapa de subdivisión sobre una cara dada y/o de dicha etapa de permutación sobre una arista dada y/o de la citada etapa de filtrado sobre un vértice dado.

En efecto, se puede desear añadir constricciones o limitaciones en la superficie del objeto observado si se considera que ciertas regiones de la imagen no deben ser modificadas. Se puede desear particularmente conservar las singularidades geométricas del objeto, tales como las esquinas o las aristas vivas, por ejemplo.

Según un modo de realización ventajoso de la invención, la citada al menos una constricción permite impedir la puesta en ejecución de una etapa que pertenece a un grupo que comprende:

-

una etapa de permutación de una arista viva;

-

una etapa de filtrado de la posición de un vértice que forma una esquina;

-

una etapa de subdivisión de una cara triangular situada en una región plana del citado objeto (el refinamiento es entonces inútil).

Impidiendo subdividir una cara triangular situada en una región plana del objeto, se evita así la puesta en ejecución de operaciones costosas e inútiles, al tiempo que se privilegia la restitución de percepción.

Para poner en ejecución estas constricciones diferentes, se puede contemplar hacer preceder el procedimiento de refinamiento según la invención de una fase previa de detección de las singularidades geométricas correspondientes.

Según un modo de realización preferente de la invención, un tal procedimiento pone en ejecución una etapa de alisado de al menos una arista viva, que consiste en entrelazar un proceso de aproximación de curva con un proceso de aproximación de superficies, poniendo en ejecución una operación de subdivisión de la citada artista viva y/o una operación de filtrado.

En efecto, una tal operación de alisado permite atenuar el aspecto poligonal que tienen las aristas vivas cuando se describen de manera demasiado sucinta por una red de mallas, y por tanto acrecentar la calidad de percepción de la imagen.

Preferentemente, un tal procedimiento comprende además una etapa de interpolación de las normales y/o de las posiciones de los vértices entre las posiciones inicial y final de los citados vértices añadidos.

Se obtiene así una continuidad de refinamiento, que se efectúa sin aberraciones ni modificaciones bruscas de la geometría de las superficies del objeto considerado. Un espectador asiste pues a un refinamiento virtualmente continuo de la imagen presentada en la pantalla de su terminal.

La invención se refiere igualmente a una formación de mallas triangulares representativa de un objeto en tres dimensiones obtenido según un procedimiento de refinamiento tal como se ha descrito en lo que antecede, y las aplicaciones de un tal procedimiento.

La invención se refiere todavía a un sistema de transmisión de una formación de mallas triangulares, así como a un dispositivo de descodificación de una formación de mallas triangulares en un terminal de visualización de una representación de un objeto en tres dimensiones.

La invención se refiere igualmente a un procedimiento de refinamiento de la codificación de una imagen, que comprende una etapa de selección de al menos una silueta de dicha imagen, siendo efectuado dicho refinamiento de la codificación de la citada imagen localmente sobre dicha al menos una silueta.

Otras características y ventajas de la invención se pondrán más claramente de manifiesto con la lectura de la descripción siguiente de un modo de realización preferente, dado a título de simple ejemplo ilustrativo y no limitativo, y de los dibujos adjuntos, entre los cuales:

- La figura 1 presenta un sinóptico de las diferentes etapas puestas en ejecución en el curso del procedimiento de refinamiento de la formación de mallas triangulares según la invención;

- La figura 2 ilustra un ejemplo de pirámide de visión, utilizada para determinar las regiones visualmente pertinentes que pueden ser refinadas según el procedimiento de la figura 1;

- Las figuras 3a y 3b representan un primer criterio de selección de las regiones de interés refinadas según el procedimiento de la figura 1;

- La figura 4 presenta la definición clásica de una silueta;

- Las figuras 5a y 5b ilustran una definición extendida de la silueta representada en la figura 4;

- La figura 6 presenta un ejemplo de subdivisión híbrida y de permutación de aristas de una cara de una formación de mallas triangulares, según el procedimiento ilustrado en la figura 1;

- Las figuras 7 a 10 representan un ejemplo de realización del filtrado de la posición antes de la subdivisión de un vértice de valencia 5 (a título de ejemplo) de la formación de mallas triangulares;

- Las figuras 11a y 11b ilustran la adición de constricciones que permiten impedir la puesta en ejecución de ciertas etapas del procedimiento de refinamiento de la figura 1;

- Las figuras 12 y 13 presentan un ejemplo de realización de una etapa de alisado de una arista viva;

- Las figuras 14a y 14b ilustran respectivamente ejemplos de realización de una subdivisión 1 en 3 centrada y de una interpolación geométrica de la posición de los vértices de la formación de mallas;

- La figura 15 presenta un ejemplo de realización de una interpolación de las normales durante la doble operación de subdivisión y de filtrado;

- La figura 16 representa un ejemplo de realización de una interpolación de las normales durante la permutación de aristas;

- Las figuras 17a a 17c ilustran los resultados obtenidos por la puesta en ejecución del procedimiento según la invención para el refinamiento de una esfera;

- Las figuras 18a a 18c presentan los resultados obtenidos por la puesta en ejecución del procedimiento según la invención para el refinamiento de una formación de mallas representativa de un rostro;

- Las figuras 19a a 19c ilustran el comportamiento adaptativo del procedimiento según la invención sobre una formación de mallas que comprende aristas vivas que se han de subdividir.

El principio general de la invención se basa en el refinamiento local adaptativo de mallas triangulares, poniendo en ejecución una técnica de subdivisión localizada de las mallas, combinada con un filtrado de las posiciones de los vértices.

Se presenta, en relación con la figura 1, un modo de realización de un tal procedimiento de refinamiento según la invención.

La técnica puesta en ejecución según la invención utiliza iterativamente un algoritmo genérico de refinamiento adaptativo 11, que comprende cuatro etapas principales:

-

una etapa, no representada, de recepción de una objeto mallado, por ejemplo según una técnica similar a la descrita en la solicitud de patente francesa FR 9907608, a nombre de los mismos titulares que la presente solicitud de patente y que tiene por título "Procedimiento de codificación de una formación de mallas por toma sobre las aristas, privilegiando un vértice completo como pivote, y procedimiento de descodificación correspondiente";

-

una etapa, con referencia 12, de detección de al menos una región de interés, por ejemplo dependiente de un punto de vista;

-

una etapa, con referencia 13, de subdivisión híbrida de al menos algunas caras de la formación de mallas triangulares;

-

una etapa, con referencia 14, de filtrado adaptativo de la geometría de la formación de mallas.

La etapa 12 de detección de al menos una región de interés de imagen fuente puede ser definida explícitamente por el usuario (por ejemplo, una región de la imagen sobre la cual es interesante aplicar el zoom) o deducida de una fase de detección de regiones juzgadas visualmente pertinentes en el seno de la imagen fuente.

Una tal fase de detección necesita introducir un punto de vista 31, ilustrado en la figura 3a. Un tal punto de vista 31 puede ser una cámara virtual, definida, por ejemplo por su centro, y una pirámide de visión formada por el ojo de un observador y la ventana de visualización de la imagen.

Estando definido el punto de vista 31, las regiones de interés pueden ser entonces seleccionadas entre las regiones siguientes de la imagen fuente:

-

las caras 21 de la malla de la imagen 23 situada en el interior de la pirámide de visión 22, representadas en la figura 2;

-

las caras 32 orientadas frente a la cámara o al punto de vista 31, no estando las otras caras 33 visibles para el usuario, por convención con los infográficos encargados del tratamiento de la imagen fuente (tales caras están ilustradas en la figura 3);

-

las caras que pertenecen a la silueta del objeto representado.

Una definición clásica de la silueta de un objeto se ilustra en la figura 4. El objeto representado aquí es una esfera, visualizada con la ayuda de una cámara 41. Una arista de la malla representativa de la esfera pertenece a la silueta 42 si comparte dos caras, de las cuales una está orientada frente a la cámara 41, y la otra es de orientación opues-
ta.

Las figuras 5a y 5b presentan una definición aumentada de la silueta de un objeto. Particularmente, la figura 5b presenta un detalle de la silueta ilustrada en la figura 5a. Aquí, y en todo lo que sigue del documento, se entenderá por silueta la banda de triángulos 51 adyacentes al subconjunto de aristas que forman la silueta de la malla (en el sentido clásico del párrafo precedente) para el punto de vista corriente.

Después de la selección de una región de interés en el curso de la etapa con la referencia 12, se opera una subdivisión híbrida 13 sobre las caras de la malla comprendidas en la región de interés seleccionada. Una tal subdivisión se ilustra en la figura 6.

La malla es iterativamente refinada por subdivisión uno en tres 61 de sus elementos y por permutación 62 de las aristas de la malla original, con el fin de evitar una degeneración de los triángulos constitutivos de la malla. En efecto, la subdivisión triangular uno en tres tiene por efecto incrementar la valencia de los vértices de la malla original, es decir, el número de aristas que llegan a los vértices de la malla, y la permutación 62 permite así paliar la degeneración de la malla.

Una cara 63 es pues subdividida en tres caras por inserción en un vértice 64 en su centro, y por creación de dos nuevas caras 65 y 66.

Se opera seguidamente una permutación suprimiendo las aristas de la cara 63 antes de la subdivisión y creando tres nuevas aristas 67 que unen el vértice insertado 64 a los vértices de las caras adyacentes a la cara 63 opuestas a las aristas suprimidas.

A la salida de la etapa 13 de subdivisión, se pone en ejecución una etapa 14 de filtrado adaptativo de la geometría de la malla.

Una tal etapa de filtrado adaptativo 14 consiste, en cada etapa 13 de subdivisión, en posicionar los vértices de la malla original de manera que se obtengan constricciones diferenciales del tipo C^{1} ó C^{2} diferenciables sobre la región de interés obtenida después de una infinidad de subdivisiones. Por ejemplo, según la figura 7a, la nueva posición del vértice 71 de valencia 5 es deducida de su posición inicial y de las posiciones de sus 5 vértices adyacentes en la malla inicial por la desviación de los coeficientes de filtrado 72 ilustrados en la figura 7b. En otros términos, se calcula nuevamente la posición de un vértice 71 dado realizando una suma de las posiciones ponderadas de sus vértices próximos y de él mismo. Así, en la figura 7b, n representa la valencia del vértice 71, y \alpha(n) corresponde al coeficiente de ponderación puesto en ejecución.

El cálculo de los coeficientes de ponderación \alpha(n) para cada valencia n se obtiene por el análisis del comportamiento asintótico de una matriz de subdivisión global estocástica C, obtenida por numeración de los vértices y la expresión matricial de dos iteraciones de subdivisión uno en tres sucesivas de orientación inversa representadas en las figuras 8a y 9a. Esta expresión se formaliza por la creación de dos matrices A y B ilustradas respectivamente en las figuras 8b y 9b. Las matrices A, B y C están así vinculadas por la relación C=A*B de acuerdo con la figura 10. Los valores propios múltiples de la matriz C son seguidamente obtenidos bajo una forma simbólica, y las constricciones diferenciales investigadas sobre la región de interés son obtenidas por la resolución de la ecuación \lambda_{1}^{2} = \lambda_{3} (en la que \lambda_{1} y \lambda_{3} son valores propios de C) después de la ordenación decreciente de los valores propios, así como se describe por Hartmut Prautzsch en el documento "Smoothness of subdivision surfaces at extraordinary points" ("Regularidad de las superficies de subdivisión en los puntos extraordinarios", Adv. In Comp. Math., Páginas 377-390, vol. 9,
1998).

El pseudo-código siguiente describe el proceso de subdivisión híbrido con el filtrado de una región de interés de una malla M:

M: malla que comprende F caras y S vértices

Sea F' (F'<=F) el número de caras que se han de subdividir

Subdivisión uno-en-tres:

Para (F' iteraciones)

{

f: cara corriente a subdividir compuesta de triplete ordenado {s1;s2;s3}

añadir un vértice s al centro de la cara f

marcar los vértices s1, s2, s3 a filtrar

añadir una cara f1 formada por el triplete {s2, s3, s}

añadir una cara f2 formada por el triplete {s3, s1, s}

añadir la cara f, ahora formada por el triplete {s1, s2, s}

poner al día las adyacencias vértices/caras y caras/caras

calcular las normales a los vértices

calcular las normales a las caras

marcar las caras f, f1 y f2 cuya arista está para permutar

}

La malla comprende ahora F'' = F + 2 * F' caras

Filtrado de las posiciones:

desnumerar los vértices a filtrar

temp: estructura temporal de almacenamiento de las nuevas posiciones

tanto como (quedan vértices para reposicionar)

{

s: vértice corriente para reposicionar

n: valencia del vértice s memorizada antes de la subdivisión uno-en-tres

p: calcular la nueva posición del vértice s a partir del coeficiente \alpha(n), de la

posición de s y de sus vértices adyacentes

almacenar p en la estructura temporal temp

}

tanto como (quedan vértices para reposicionar)

{

s: vértice corriente para reposicionar

aplicar la nueva posición p al vértice corriente

}

Permutación de aristas:

tanto como (quedan caras cuya arista está para permutar)

{

f: caras corrientes cuyas aristas son candidatas a la permutación

por (cada cara f' adyacente a f no marcada)

si (f' ha sido obtenida por subdivisión uno-en-tres)

permutar la arista que comparte f y f' para intercambio de vértices

marcar la cara f

}

volver a calcular las normales de M por cara

volver a calcular las normales de M por vértice

Cuando se desea que ciertas regiones del objeto no sean modificadas en el curso de las diferentes etapas del procedimiento de refinamiento según la invención, se pueden añadir ciertas constricciones sobre la superficie del objeto considerado, así como se ilustra en la figura 11a.

Así se puede desear conservar las aristas vivas 112 y las esquinas 111, de manera que se obtenga una representación del objeto considerado más próxima a la realidad que la malla 115 de la figura 11b, en la cual las aristas vivas 112 y las esquinas 111 han sido suprimidas. En este dibujo, es necesario marcar las aristas, los vértices o las caras, respectivamente, que no se han de permutar, desplazar o subdividir. El procedimiento de refinamiento puede ser así precedido de una fase previa (interactiva o automática) de detección de las esquinas, de las aristas vivas o de las regiones planas.

Se podría, por ejemplo, impedir:

-

la permutación de las aristas vivas 112;

-

el desplazamiento de los vértices 111 que forman esquinas de la malla;

-

la subdivisión de las caras 113 situadas en una región plana de la malla.

En efecto, una tal subdivisión es inútil y no permite refinar la malla considerada.

Por otra parte, se puede desear refinar una malla alisando una arista viva 112 en su propia dirección, con el fin de obtener una curva de aspecto menos poligonal. Se interpola entonces la curva formada por los vértices clasificados sobre una arista viva regular, tales como el vértice 114. Se entrelaza pues un proceso de aproximación de curva (a saber, la arista viva regular considerada, a la cual pertenece el vértice 114) con una aproximación de superfi-
cies.

Se describe con más detalles esta operación de alisado de una arista viva en relación con las figuras 12 y 13a a 13c. Una tal operación necesita la puesta en ejecución de un operador de la arista viva regular 121 de un operador de filtrado.

Se considera la formación de mallas triangulares 120 de la figura 12. En el curso de una etapa de referencia 125 se opera una subdivisión uno en tres de la formación de mallas 120, así como una permutación de las aristas, según una técnica similar a la descrita anteriormente en este documento. Se observará que una constricción o limitación se aplica sobre la arista viva 121, de manera que se impide su permutación en el curso del refinamiento de la ma-
lla.

En el curso de una etapa de referencia 126, se opera seguidamente una subdivisión baricéntrica de la arista viva regular 121 por inserción de un vértice 122 y de dos aristas de regularización 123 y 124. Así, un vértice 131, ilustrado en la figura 13a, que pertenece a una arista viva regular (por tanto con dos aristas adyacentes) se sitúa según la máscara de ponderación 132 representada en la figura 13b, mientras que el nuevo vértice 133 insertado sobre la arista viva se sitúa según la máscara de ponderación 134 de la figura 13c, es decir en el medio de la arista antes del desplazamiento de los vértices de la malla original.

Se obtiene así un efecto de alisado de las aristas vivas, que tienen pues un aspecto menos poligonal.

Es igualmente muy importante que el refinamiento de la malla representativa del objeto considerado se efectúe sin aberraciones visuales ni modificaciones bruscas de la geometría de las superficies, de manera que sea perceptible, o que sea poco perceptible, para un observador que visualiza el objeto en un terminal adaptado. Particularmente, la subdivisión híbrida combinada con el filtrado de la geometría de la malla debe efectuarse de manera visualmente continua.

En el modo de realización descrito en lo que sigue del documento, la continuidad del refinamiento es obtenida por interpolación conjunta de la geometría de la malla en el curso del tiempo, según se ilustra en las figuras 14a, 14b, 15 y 16.

Según la invención, la subdivisión híbrida se descompone en tres etapas:

-

una subdivisión uno en tres centrada 141, ilustrada en la figura 14a;

-

un filtrado de las posiciones;

-

una permutación de las aristas.

Así, según la figura 14b, la inserción de un vértice S en el centro de una cara F consiste en insertar un vértice superponiéndolo a uno de los tres vértices de la cara F considerada, llamado S_{j}, y elegido arbitrariamente, y en crear dos nuevas caras correspondientes. La interpolación geométrica es seguidamente realizada por interpolación lineal 142 entre las posiciones inicial y final del vértice S, y entre las posiciones iniciales y después del filtrado de los vértices de la malla original.

Esta interpolación se efectúa de manera simultánea con una interpolación de las normales 151 de los vértices situados en la región pertinente por la subdivisión, sucediendo el vértice S a la salida de la normal al vértice S_{i}. Una tal operación de interpolación de las normales se ilustra en la figura 15, y necesita el cálculo de las normales después de la simulación de la doble operación subdivisión/filtrado.

La interpolación de las normales puede efectuarse bajo una forma lineal. Aquella puede igualmente, por supuesto, efectuarse bajo cualquier otra forma adaptada, tal como, por ejemplo, la interpolación sobre la esfera unidad.

Según un modo de realización preferente de la invención, la permutación de arista, ilustrada en la figura 16, no es operada más que durante el anuncio de la última iteración de la interpolación 161, de manera que resulte la modificación visual imperceptible para un observador.

Se describe a continuación un ejemplo de realización de la invención, que consiste en aplicar la técnica de subdivisión descrita anteriormente a la malla que componen los objetos de una escena tridimensional.

Sólo son calculados nuevos coeficientes de filtrado \alpha(3...11), definidos por la tabla que sigue, no siendo los vértices de valencia superior o igual a 12 desplazados en el curso de la subdivisión. En efecto, la distribución de las valencias de una malla está generalmente centrada en el valor 6, y son raros los vértices de valencia superior a
11.

\vskip1.000000\baselineskip

Valencia n	\alpha(n)
3	1,5
4	5
5	8,30585
6	12
7	15,8839
8	19,844526
9	23,8213
10	27,7839
11	11,221

\vskip1.000000\baselineskip

Los números de iteraciones de subdivisión v y s, respectivamente, en el campo de visión y sobre la silueta del objeto son fijados por el usuario en función de las capacidades gráficas del terminal utilizado, y de la calidad de interpolación geométrica deseada.

Puede igualmente considerarse apropiado refinar las regiones adyacentes a las siluetas, hasta la obtención de una longitud de arista inferior a la resolución del periférico de salida (a la sazón, un pixel).

El pseudo-código siguiente describe el refinamiento adaptativo puesto en ejecución.

\newpage

M: malla que comprende F caras y S vértices

peticiones:

v iteraciones en el campo de visión

s iteraciones en la silueta

anular el último refinamiento adaptativo

para (v iteraciones)

{

marcar las caras de M en el campo de visión

lanzar una subdivisión híbrida sobre las caras marcadas

}

para (s iteraciones)

{

marcar las caras de M en la proximidad de la silueta

lanzar una subdivisión híbrida sobre las caras marcadas

}

volver a calcular las normales de M por cara

volver a calcular las normales de M por vértice.

Las figuras 17 a 19 presentan resultados obtenidos a partir del procedimiento de refinamiento según la invención.

Así, las figuras 17a a 17c ilustran un ejemplo de puesta en ejecución del procedimiento de refinamiento según la invención sobre un objeto esférico, presentado en la figura 17a. Las mallas de las figuras 17b y 17c son obtenidas después de dos iteraciones del procedimiento en el campo de visión de un observador, y después de cinco iteraciones sobre la silueta de la esfera. Se observa en la figura 17b que el aspecto poligonal del contorno de la esfera ilustrada en la figura 17a se ha difuminado sensiblemente gracias al procedimiento de refinamiento según la invención.

Las figuras 18a a 18c presentan los resultados obtenidos al poner en ejecución el procedimiento de refinamiento según la invención sobre una malla tipo, representativa de una cara. Se representa en la figura 18a la malla original 181, antes de la puesta en ejecución del procedimiento según la invención. La figura 18b representa la imagen 182 obtenida después de cuatro iteraciones del procedimiento de refinamiento en el campo de visión de un observador y ocho iteraciones sobre la silueta de la cara 181.

Se observa, en la figura 18c, que el aspecto poligonal de la silueta ha sido suprimido, y que la geometría de la malla no ha sido refinada más que sobre las regiones visualmente pertinentes de la imagen 183.

Se presenta en lo que sigue, en relación con las figuras 19a a 19c, los resultados obtenidos al poner en ejecución el algoritmo adaptativo según la invención sobre una malla 191 que comprende aristas vivas para subdividir.

La malla 192 de la figura 19b corresponde a la malla obtenida sin detección previa a la puesta en ejecución del procedimiento de refinamiento, de las esquinas y de las aristas de la malla 191. Se constata entonces la obtención de una superficie alisada.

Por el contrario, la malla 193 de la figura 19c ha sido subdividida de manera adaptativa preservando las esquinas e interpolando las aristas vivas regulares. Se constata la supresión del aspecto poligonal de las aristas vivas regulares sobre la malla original, así como una interpolación de la superficie original.

Claims (17)

1. Procedimiento de refinamiento de una malla representativa de un objeto en tres dimensiones, estando dicha malla constituida por una disposición de vértices y caras, comprendiendo dicho procedimiento una etapa de selección de al menos una región de interés sobre la cual se efectúa localmente el citado refinamiento de la malla,

caracterizado porque la o las citadas regiones de interés pertenecen a un grupo que comprende:

-

al menos una silueta de dicho objeto en tres dimensiones;

-

caras de dicha malla que pertenecen a una zona animada de dicho objeto.

2. Procedimiento de refinamiento según la reivindicación 1, caracterizado porque la citada malla es una malla triangular (120) constituida por una disposición de vértices (71; 111; 114; 131; S) y de caras triangulares (F), cada una definida por tres referencias en los vértices que une, y que presentan tres aristas (121) que une cada una a dos de dichos vértices,

y porque la citada silueta comprende dos caras triangulares (51) adyacentes a un conjunto de aristas (42), cada una de las cuales pertenece a dos caras triangulares, estando una primera cara orientada frente al ojo de un observador (41) y estando una segunda cara orientada en sentido opuesto.

3. Procedimiento según la reivindicación 2, caracterizado porque comprende además una etapa (13; 16) de subdivisión híbrida de al menos algunas de dichas caras triangulares (63), que pone en ejecución una operación de subdivisión 1 en 3 baricéntrica, de manera que se divide cada una de dichas caras en tres caras triangulares (65, 66) por adición de un vértice (64).

4. Procedimiento según la reivindicación 3, caracterizado porque comprende además una etapa (62) de permutación de aristas de al menos algunas de dichas caras triangulares subdivididas, que consiste en suprimir cada arista de la cara triangular antes de la subdivisión y en sustituirla por una arista (67) que une el vértice añadido al vértice opuesto a la arista suprimida de la cara triangular adyacente.

5. Procedimiento según una cualquiera de las reivindicaciones 2 a 4, caracterizado porque la citada etapa de selección es puesta en ejecución por un operador y/o según un criterio de detección predeterminado.

6. Procedimiento según la reivindicación 5, caracterizado porque la citada etapa de selección, al ser puesta en ejecución según un criterio de detección predeterminado, al menos una de las citadas regiones de interés pertenece al grupo que comprende:

-

caras triangulares (21) situadas en el interior de una pirámide de visión (22) definida por el ojo del observador y una ventana de visualización;

-

caras triangulares (32) orientadas frente al ojo de un observador, perteneciendo la o las citadas regiones de interés (21) al grupo que comprende:

-

caras triangulares (51) adyacentes a un conjunto de aristas (42) cada una de las cuales comparte dos caras triangulares, estando una primera cara orientada frente al ojo de un observador (41) y estando una segunda cara en orientación opuesta;

-

caras triangulares que pertenecen a una zona animada de dicho objeto.

7. Procedimiento según una cualquiera de las reivindicaciones 3 a 6, caracterizado porque comprende además una etapa de filtrado (14) de la posición antes de la subdivisión de al menos algunos de dichos vértices de la ma-
lla.

8. Procedimiento según la reivindicación 7, caracterizado porque la citada etapa de filtrado de la posición antes de la subdivisión de un vértice de la malla tiene en cuenta la valencia de dicho vértice y la valencia de sus vértices próximos, siendo la valencia el número de aristas que llegan a un vértice.

9. Procedimiento según la reivindicación 8, caracterizado porque la citada etapa de filtrado pone en ejecución un cálculo de coeficientes de ponderación por cada valencia, obtenido por análisis del comportamiento asintótico de una matriz de subdivisión global estocástica.

10. Procedimiento según una cualquiera de las reivindicaciones 3 a 9, caracterizado porque pone en ejecución al menos una constricción o limitación que permite impedir la puesta en ejecución de dicha etapa de subdivisión sobre una cara dada y/o de la citada etapa de permutación sobre una arista dada y/o de dicha etapa de filtrado sobre un vértice dado.

11. Procedimiento según la reivindicación 10, caracterizado porque la citada al menos una constricción permite impedir la puesta en ejecución de una etapa que pertenece a un grupo que comprende:

-

una etapa de permutación de una arista viva;

-

una etapa de filtrado de la posición de un vértice que forma una esquina;

-

una etapa de subdivisión de una cara triangular situada en una región plana de dicho objeto.

12. Procedimiento según una cualquiera de las reivindicaciones 2 a 11, caracterizado porque pone en ejecución una etapa de alisado de al menos una arista viva, que consiste en entrelazar un proceso de aproximación de curva con un proceso de aproximación de superficies, poniendo en ejecución una operación de subdivisión de dicha arista viva y/o una operación de filtrado.

13. Procedimiento según una cualquiera de las reivindicaciones 3 a 12, caracterizado porque comprende además una etapa de interpolación de las normales y/o de las posiciones de los vértices entre las posiciones inicial y final de los citados vértices añadidos.

14. Aplicación del procedimiento según una cualquiera de las reivindicaciones 2 a 13 a una cualquiera de las operaciones siguientes:

-

transmisión de datos sobre una red del tipo internet y/o intranet;

-

visualización de imágenes relativas a aplicaciones culturales;

-

visualización de imágenes y/o de secuencias de imágenes relativas a un juego colaborador;

-

transmisión y/o visualización de datos relativos a un trabajo colaborador;

-

telecomercio.

15. Sistema de transmisión de una malla triangular representativa de un objeto en tres dimensiones (3D), entre, por una parte, al menos un codificador y/o al menos un soporte de datos, y, por otra parte, al menos un terminal de visualización,

estando dicha malla constituida por una disposición de vértices y de caras triangulares, definidas cada una por tres referencias a los vértices que une, y que presenta tres aristas que unen cada una dos de dichos vértices,

siendo refinada dicha malla localmente sobre al menos una región de interés seleccionada,

caracterizado porque los citados medios de selección de dicha al menos una región de interés son puestos en ejecución por al menos uno de los citados terminales de visualización,

y porque la o las citadas regiones de interés (21) pertenecen al grupo que comprende:

-

caras triangulares (51) adyacentes a un conjunto de aristas (42) que comparten cada una dos caras triangulares, estando una primera cara orientada frente al ojo de un observador (41) y estando una segunda cara orientada en sentido opuesto;

-

caras triangulares que pertenecen a una zona animada de dicho objeto.

16. Dispositivo de refinamiento de una malla representativa de un objeto en tres dimensiones, estando dicha malla constituida por una disposición de vértices y de caras, comprendiendo dicho dispositivo medios de selección de al menos una región de interés sobre la cual es efectuado localmente dicho refinamiento de la malla,

caracterizado porque la o las citadas regiones de interés pertenecen al grupo que comprende:

-

al menos una silueta de dicho objeto en tres dimensiones;

-

caras de dicha malla que pertenecen a una zona animada de dicho objeto.

17. Terminal de visualización de una representación de un objeto en tres dimensiones (3D), estando dicha representación asociada a una malla constituida por una disposición de vértices y de caras, poniendo dicho terminal en ejecución medios de refinamiento localizado de la citada representación, de manera que se sintetiza y/o se visualiza al menos una región de interés predeterminada de dicho objeto de manera refinada,

\newpage

caracterizado porque la o las citadas regiones de interés (21) pertenecen al grupo que comprende:

-

caras triangulares (51) adyacentes a un conjunto de aristas (42) que comparten cada una dos caras triangulares, estando una primera cara orientada frente al ojo de un observador (41) y estando una segunda cara orientada en sentido opuesto;

-

caras triangulares que pertenecen a una zona animada de dicho objeto.