Un método para redondear un borde (403) entre dos lados (501, 502) de una superficie de un modelo, en donde la mencionada superficie comprende una pluralidad de puntos conectados para formar una malla de triángulos, en donde el mencionado método comprende:

desplazar una representación de una bola (701) a lo largo del mencionado borde en una direccion predeterminada (602); definir un túnel virtual (801) a través del cual pase la bola al moverse a lo largo del mencionado borde; identificar una pluralidad de puntos proyectados (901A-904A) por la proyección de una pluralidad de puntos del margen (901-904) a una superficie del túnel virtual; y conectar los mencionados puntos proyectados en la mencionada pluralidad de los puntos proyectados; en donde la etapa de mover la bola comprende: identificar un triangulo de semilla (302) en donde los puntos en cada uno de los vértices del triángulo son puntos sobre las superficies de los dos lados (501, 502); posicionar la bola de forma tal que los mencionados puntos en cada uno de los vértices estén dispuestos sobre una superficie de la bola; seleccionar una pata (307) entre dos de los mencionados vértices del mencionado triángulo de semilla; y pivotar la mencionada bola alrededor de la mencionada pata de una forma tal que los puntos de los mencionados vértices (304, 305) permanezcan dispuesto sobre la mencionada superficie de la bola; en donde el radio de la bola se selecciona tal que solo los puntos en los vértices del triangulo de semilla estén en contacto con la superficie de la bola y sin puntos dispuestos en cualquiera de los dos lados posicionados dentro del volumen de la bola

Esta solicitud de patente reivindica los beneficios de la solicitud provisional de los EE.UU. número 60/742440, registrada el 5 de Diciembre de 2005, la cual se incorpora aquí como referencia en su totalidad. REFERENCIA CRUZADA CON LAS SOLICITUDES RELACIONADAS.

La presente solicitud está relacionada también con la solicitud de la patente de los EE.UU. numero de serie 60/740366, titulada Método y Aparato para el alisamiento de mallas no encogibles, utilizando el encaje local (numero de expediente de abogado 2005P21689US); y la solicitud de patente de los EE.UU. número 60/742503, titulada Método y Aparato para la simplificación eficiente y rápida de mallas (numero de expediente de abogado 2005P22087US), en donde ambas solicitudes están incorporadas y registradas simultáneamente con la presente solicitud, con referencia a las mismas en su totalidad.

ANTECEDENTES DE LA INVENCIÓN

La presente invención está relacionada en general con las formas de mallas en tres dimensiones, y más en particular con el fileteado y redondeo de bordes afilados de tales formas de mallas.

Muchas aplicaciones, tales como en las aplicaciones médicas y de diseño industrial de fabricación, incluyen la manipulación y edición de modelos digitales que hayan sido escaneados por medios ilustrativos en 3D del objeto. Tal como podrá comprender cualquier técnico especialista en la técnica, tales modelos digitales comprenden una representación de nubes de puntos del objeto, en donde el número de puntos depende de la resolución del proceso de escaneado. Una vez obtenido dicha representación de la nube de puntos, la superficie del objeto, en muchos casos, se consigue aproximadamente por la conexión de los puntos de la nube de puntos, para formar una malla de triángulos de la superficie de la representación de la nube de puntos. Esta superficie puede ser editada por el uso, por ejemplo, de programas de software de diseño asistido por ordenador (CAD), o bien por programas de software de manipulación de imágenes especializados.

Muchas operaciones de edición son perfectamente conocidas, y están integradas en la mayor parte de los programas de software (CAD) de diseño asistido por ordenador. Dos operaciones ilustrativas y bien conocidas, denominadas aquí como el fileteado y el redondeo, se aplican frecuentemente a los modelos digitales de una forma de tres dimensiones para alisar, o bien redondear un borde agudo del modelo en un borde más alisado. La figura 1 muestra un ejemplo ilustrativo de dicho proceso de fileteado y redondeo. Con referencia a dicha figura, la forma 101 es ilustrativamente una sección transversal de un objeto de tres dimensiones tal como el modelo antes mencionado de una forma almacenada en la memoria de un ordenador. La forma 101 tiene por ejemplo la esquina 102 y la esquina 103 en donde se desean el redondeado y fileteado para alisar las esquinas. Mediante la eliminación de las esquinas 102 y 103 y por la mezcla de las superficies adyacentes, se obtienen las superficies alisadas 104 y 105. La superficie 104 se denomina aquí como una superficie “redondeada”, puesto que dicha superficie es convexa. Por el contrario, el área de la superficie 105 se denomina aquí como “fileteada”, puesto que dicha superficie es cóncava.

En muchas situaciones, la edición del modelo de la malla de triángulos, tal como el modelo antes mencionado creado a partir de la conexión de los puntos obtenidos por el escaneado de un objeto, dará lugar a unos bordes afilados. Por ejemplo, la figura 2 muestra una forma ilustrativa 201 en 3D, que ha sido editada por el corte la forma 201 con el plano de corte 202. Dicha operación de corte produce un borde afilado 203 para el cual puede ser deseable ilustrativamente un borde redondeado.

Yu-Shen Liu y otros, en el documento titulado “Mezcla de mallas”, Visual Comput. (2005) 21:915-927, exponen un algoritmo de bola rodante para redondear los bordes que se exigen en el calculo por ordenador a lo largo del recorrido que la bota tiene que rodar. SUMARIO DE LA INVENCIÓN

Los presentes inventores han reconocido que aunque los métodos anteriores para el fileteado y redondeado son ventajosos en muchos aspectos, son también inconvenientes en algunos aspectos. En particular, aunque los anteriores intentos del fileteado y redondeado son bien conocidos, tales técnicas son principalmente útiles en modelos que tengan superficies continuas. Para los modelos que no tienen superficies continuas, tales como las superficies de las mallas de los triángulos de la forma 201, tales técnicas no son típicamente satisfactorias, ya que dichas superficies no son computables analíticamente. Así pues, tal como reconocerá cualquier técnico especializado, tales técnicas anteriores de fileteado y redondeado pueden producir una superficie rugosa y desigual, y no una superficie continuamente suave, tal como es la salida deseada de tales técnicas de redondeado y fileteado.

De acuerdo con un primer aspecto de la invención, un método para redondear un borde entre dos lados de una superficie de un modelo comprende las etapas expuestas en la reivindicación 1 adjunta.

De acuerdo con un segundo aspecto de la invención, el aparato para redondear un borde entre dos lados de una superficie de un modelo comprende las características expuestas en la reivindicación 5 adjunta. BREVE DESCRIPCIÓN DE LOS DIBUJOS

La figura 1 muestra una sección transversal de una forma en 3D que tiene unas esquinas afiladas que se redondean y se filetean;

la figura 2 muestra una forma en 3D ilustrativa de forma tal que se producen bordes afilados;

la figura 3A muestra una bola en una posición inicial con respecto a un triángulo con respecto a un triangulo de semilla en el inicio de un algoritmo de pivotado de bola anterior;

la figura 3B muestra como la bola de la figura 3A se hace pivotar alrededor de una pata del triangulo de semilla para construir una superficie de malla de triángulos de acuerdo con un algoritmo de pivotado de bola anterior;

la figura 4 muestra la forma ilustrativa en 3D de la figura 2, y los bordes agudos resultantes;

la figura 5 muestra una representación de un borde agudo de la forma en 3D de la figura 4;

la figura 6 muestra una representación general de cómo un nuevo algoritmo de pivotado de bola puede mover una bola a lo largo de un borde afilado de la forma en 3D de la figura 4, de acuerdo con una realización de la presente invención;

la figura 7A muestra como una bola puede posicionarse con respecto a un triángulo de semilla en la representación de la figura 5, en el inicio de un método de redondeado de un método de redondeo de acuerdo con una realización de la presente invención;

la figura 7B muestra como la bola de la figura 7A puede pivotar a lo largo de un borde afilado en una direccion deseada alrededor de una pata de un triangulo de semilla;

la figura 8 muestra un túnel virtual que puede crearse como el resultado de hacer pivotar la bola a lo largo de un borde afilado tal como se muestra en la figura 7B;

la figura 9 muestra como los puntos en la proximidad de un borde afilado pueden ser proyectados sobre la superficie del túnel virtual de la figura 8;

la figura 10 muestra como un borde afilado puede ser redondeado como el resultado de la proyección de la figura 9;

la figura 11 muestra el borde redondeado resultante de una forma en 3D después de la reconstrucción superficial del borde;

la figura 12 es un diagrama de flujo que muestra las etapas de un método de acuerdo con una realización de la presente invención; y

la figura 13 muestra un ordenador adaptado para ejecutar las etapas ilustrativas del método de

la figura 12, así como también de otras funciones asociadas con el redondeado y fileteado de los bordes afilados de las formas en 3D. DESCRIPCIÓN DETALLADA

Las figuras 3A y 3B ilustran como puede utilizarse para construir una superficie de malla de triángulos para conseguir la aproximación de la superficie de un objeto.

Específicamente, con referencia a la figura 3A, los vértices del triangulo 202, los puntos 303, 304 y 305, son puntos en una representación de nubes de puntos de un objeto, y situados sobre la superficie de un modelo de un objeto 3D para el cual se desea una aproximación de la malla de los triángulos de la superficie del objeto. El triángulo 302 se denomina aquí...

1. Un método para redondear un borde (403) entre dos lados (501, 502) de una superficie de un modelo, en donde la mencionada superficie comprende una pluralidad de puntos conectados para formar una malla de triángulos, en donde el mencionado método comprende:

desplazar una representación de una bola (701) a lo largo del mencionado borde en una direccion predeterminada (602);

definir un túnel virtual (801) a través del cual pase la bola al moverse a lo largo del mencionado borde;

identificar una pluralidad de puntos proyectados (901A-904A) por la proyección de una pluralidad de puntos del margen (901-904) a una superficie del túnel virtual; y

conectar los mencionados puntos proyectados en la mencionada pluralidad de los puntos proyectados; en donde la etapa de mover la bola comprende:

identificar un triangulo de semilla (302) en donde los puntos en cada uno de los vértices del triángulo son puntos sobre las superficies de los dos lados (501, 502);

posicionar la bola de forma tal que los mencionados puntos en cada uno de los vértices estén dispuestos sobre una superficie de la bola;

seleccionar una pata (307) entre dos de los mencionados vértices del mencionado triángulo de semilla; y

pivotar la mencionada bola alrededor de la mencionada pata de una forma tal que los puntos de los mencionados vértices (304, 305) permanezcan dispuesto sobre la mencionada superficie de la bola;

en donde el radio de la bola se selecciona tal que solo los puntos en los vértices del triangulo de semilla estén en contacto con la superficie de la bola y sin puntos dispuestos en cualquiera de los dos lados posicionados dentro del volumen de la bola.

2. El método de la reivindicación 1, en donde un punto de un vértice del mencionado triangulo de semilla está sobre un primer lado de los mencionados dos lados, y un segundo vértice que se encuentra sobre un segundo lado de los mencionados dos lados.

3. El método de la reivindicación 1, en donde la mencionada etapa de identificación de una pluralidad de puntos proyectados comprende:

identificar una pluralidad de intersecciones de una pluralidad de líneas con la mencionada superficie del mencionado túnel virtual, en donde la mencionada pluralidad de líneas comprenden líneas entre la mencionada pluralidad de puntos del borde y un centro del mencionado túnel virtual; y

disponer los puntos sobre la mencionada superficie del mencionado túnel virtual en cada intersección en la mencionada pluralidad de las intersecciones.

4. El método de la reivindicación 1, en donde la mencionada etapa de conectar los mencionados puntos proyectados comprende el crecimiento de una malla de triángulos.

5. Un aparato para su uso en el redondeado de un borde entre dos lados de una superficie de un modelo, en donde la mencionada superficie comprende una pluralidad de puntos conectados para formar una malla de triángulos, en donde el mencionado aparato comprende:

medios para mover una representación de una bola a lo largo del mencionado borde en una dirección predeterminada;

medios para definir un túnel virtual a través del cual haya pasado la bola al moverse a lo largo del mencionado borde;

medios para identificar una pluralidad de punto proyectados para identificar una pluralidad de puntos proyectados mediante la proyección de una pluralidad de puntos del borde a una superficie del mencionado túnel virtual; y

medios para la conexión de los mencionados puntos proyectados en la mencionada pluralidad de los puntos proyectados;

en donde los medios para mover la bola comprenden:

medios para identificar un triangulo de semilla en donde los puntos en

cada uno de los vértices del triángulo son puntos sobre las superficies de los

dos lados;

medios para posicionar la mencionada bola de una forma tal que los puntos en cada uno de los vértices del mencionado triangulo de semilla están dispuestos sobre una superficie de la mencionada bola;

medios para seleccionar una pata entre dos de los mencionados

vértices del triangulo de semilla; y

medios para pivotar la mencionada bola alrededor de la mencionada pata de una forma tal que los puntos de los mencionados vértices permanezcan dispuestos sobre la mencionada superficie de la bola;

medios para seleccionar un radio de la mencionada bola, tal que solo los puntos en los vértices del triangulo de semilla estén en contacto con la superficie de la bola, y sin ningún punto dispuesto sobre cualquiera de los mencionados dos lados posicionados dentro del volumen de la mencionada bola.

6. El aparato de la reivindicación 5, en donde los mencionados medios para posicionar la bola comprenden medios para posicionar la bola, de forma tal que un punto de un vértice del mencionado triangulo de semilla se encuentre sobre un primer lado de los dos mencionados lado y un segundo vértice se encuentra sobre un segundo lado de los mencionados dos lados.

7. El aparato de la reivindicación 5, en donde los mencionados medios para la identificación de una pluralidad de puntos proyectados comprende:

medios para identificar una pluralidad de intersecciones de una pluralidad de líneas con la mencionada superficie del mencionado túnel virtual, en donde la mencionada pluralidad de líneas comprenden líneas entre la mencionada pluralidad de puntos del borde y un centro del mencionado túnel virtual; y

medios para disponer puntos sobre la mencionada superficie del mencionado túnel virtual en cada intersección en la mencionada pluralidad de intersecciones.

8. El aparato de la reivindicación 5 en donde los mencionados medios para conectar los mencionados puntos proyectados comprenden medios para hacer crecer una malla de triángulos.

9. Un medio legible por ordenador que comprende unas instrucciones de un programa por ordenador, el cual al ejecutarse por un procesador, define las etapas para redondear un borde entre dos lados de una superficie de un modelo, en donde la mencionada superficie comprende una pluralidad de puntos conectados para formar una malla de triángulos, en donde las mencionadas etapas comprenden:

mover una representación de una bola a lo largo del mencionado borde en una direccion predeterminada;

definir un túnel virtual a través del cual haya pasado la bola al moverse a lo largo del mencionado borde;

identificar una pluralidad de puntos proyectados por la proyección de una pluralidad de puntos del borde a una superficie del túnel virtual; y

conectar los mencionados puntos proyectados en la mencionada pluralidad de los puntos proyectados:

en donde la etapa de mover la bola comprende:

identificar un triangulo de semilla en donde los puntos en cada uno de los vértices del triangulo son puntos sobre las superficies de los dos lados;

posicionar la bola de forma tal que los mencionados puntos en cada uno de los vértices están dispuestos sobre una superficie de la bola;

seleccionar una pata entre dos de los mencionados vértices del mencionado triángulo de semilla; y

pivotar la mencionada bola alrededor de la mencionada pata de una forma tal que los puntos de los mencionados vértices permanecen dispuestos sobre la mencionada superficie de la bola;

en donde el radio de la bola se selecciona de forma tal que solo los puntos en los vértices del triangulo de semilla estén en contacto con la superficie de la bola, y sin puntos dispuestos en cualquiera de los dos lados, en posición dentro del volumen de la bola.

10. El medio legible por ordenador de la reivindicación 9, que comprende además unas instrucciones del programa por ordenador para asegurar que un punto de un vértice del mencionado triangulo de semilla se encuentra en un primer lado de los mencionados dos lados y en donde un segundo vértice está sobre un segundo lado de los mencionados dos lados.

11. El medio legible por ordenador de la reivindicación 9, en donde las mencionadas instrucciones del programa de ordenador definen la etapa de identificar una pluralidad de puntos proyectados que comprenden las instrucciones del programa de ordenador que definen las etapas de:

identificar una pluralidad de intersecciones de una pluralidad de líneas con la mencionada superficie del mencionado túnel virtual, en donde la mencionada pluralidad de líneas comprende líneas entre la mencionada pluralidad de los puntos del borde y un centro del mencionado túnel virtual; y

5 disponer los puntos sobre la mencionada superficie del mencionado túnel virtual en cada intersección en la mencionada pluralidad de las intersecciones.

12. El medio legible por ordenador de la reivindicación 9, en donde las mencionadas instrucciones de los programas del ordenador, que definen la etapa de conectar los mencionados puntos proyectados comprenden las instrucciones del programa del ordenador que definen la etapa de crecimiento de una malla de triángulos.