Subdivisión Doo-Sabin

En la tercera unidad del curso de geometria computacional se vieron 3 algoritmos para subdivisión de objetos 3D (Doo- Sabin, Catmull-Clark, el esquema de Loop) Se implemento un algoritmo para laboratorio el de Doo-Sabin del cual hablare a continuación.

1. INTRODUCTION
   Subdivisión de superficies:
   Representación de superficies mediante un mallado
   Refinado de la malla mediante un proceso iterativo
   La superficie será igual al límite de refinamientos sucesivos
   Aplicaciones:
   Utilizada en el corto de animación "Geri's Game" (Pixar), y en las películas "Bichos" y "Toy Story 2" (Pixar/Disney).
   Ventajas de la subdivisión
   Permiten dibujar superficies de topología compleja
   Permiten obtener distintos niveles de detalle
   Son numéricamente estables
   Sencillas de implementar
   Se ejecutan (renderizar) directamente



2. REGLAS DE DOO-SABIN
   Se debe crear para cada cara un punto para cada uno de los puntos de la cara.
   Cada nuevo punto es el punto medio del segmento que une el centroide de una cara con cada uno de sus vértices.
   Crear con las aristas de todos los puntos internos a una cara una nueva cara.
   Crear con las aristas de todos los puntos generados de aristas adyacentes una nueva cara.
3. EJECUTABLE
   Se desarrollo en java, el objeto ya esta ingresado solo pueden variar su forma con el
   mouse para obtener otros resultados, la aplicacion se desarrollo para 3 iteraciones.

Descargar Doo-Sabin

Triangulación de Delaunay

En al segunda unidad del curso de geometría computacional se implemento los algoritmos de triangulación de polinomios (Ear Clipping, triangulación monótona) así como triangulación de una nube de puntos en este caso la triangulación de Delaunay de la que hablare a continuación

1. INTRODUCTION
   Se le denomina así por el matemático ruso Boris Nikolaevich Delone (Борис Николаевич Делоне, 1890 - 1980) quien lo inventó en 1934.
   Es una red de triángulos que cumple la condición de Delaunay. Esta condición dice que la circunferencia circunscrita de cada triángulo de la red no debe contener ningún vértice de otro triángulo.
   
   
2. CONDICIÓN DE DELAUNAY
   La condición de Delaunay dice que una red de triángulos es una triangulación de Delaunay si todas las circunferencias circunscritas de todos los triángulos de la red son vacías. Esa es la definición original para espacios bidimensionales. Es posible ampliarla para espacios tridimensionales usando la esfera circunscrita en vez de la circunferencia circunscrita. También es posible ampliarla para espacios con más dimensiones pero no se usa en la práctica.
   La arista p1p2 es legal mientras que p3p4 es una arista ilegal porque p2 cae dentro del círculo que pasa por p3p1p4.
   Cuando se detecte una arista ilegal hay que hacer un intercambio de la arista para convertirla en una legal.
   
   
3. PROPIEDADES
   · La triangulación forma la envolvente convexa del conjunto de puntos.
   · El ángulo mínimo dentro de todos los triángulos está maximizado.
   · La triangulación es unívoca si en ningún borde de circunferencia circunscrita hay más que tres vértices.
   
   
4. ALGORITMOS
   ·Incremental construction
   ·Divide and conquer
   ·Sweepline
   Algoritmo Aleatorio Incremental
   1. Introducir la nube de puntos P de tamaño n en un gran triángulo conteniendo a dicha nube de puntos Algoritmo Aleatorio Incremental
   2. Para cada uno de la n puntos de P, elegir pr de forma aleatoria y triangular:
   2.1. Encontrar el triángulo pipjpk conteniendo a pr
   2.2. SI pr cae en el interior del triángulo pipjpk ENTONCES añadir aristas desde pr hasta los vértices pi,pj,pk
   ● Legalizar_Aristas (pr, pipj)
   ● Legalizar_Aristas (pr, pjpk)
   ● Legalizar_Aristas (pr, pkpi)
   2.3. SINO pr cae en la arista pipj , que es incidente a los triángulos pipjpk y pipjpl
   ● Legalizar_Aristas (pr, pipl)
   ● Legalizar_Aristas (pr, plpj)
   ●Legalizar_Aristas (pr, pjpk)
   ● Legalizar_Aristas (pr, pkpi)
   3. Finalmente eliminar los tres puntos del gran triángulo inicial.
   
   
5. EJECUTABLE
   Se desarrollo en java, se ingresan los puntos con el Mouse ya demás tener en cuenta que una ves ejecutado Delaunay ya no se pueden seguir ingresando mas puntos se debe abrir de nuevo la aplicación.
   

Descargar Delaunay