1 Computación Gráfica 12 Curvas y Superficies

2 Temario Representaciones de curvas y de superficiesSplines y otras bases polinomial Puntos

3 Representaciones GeométricasGeometría Sólida Constructiva (Constructive Solid Geometry CSG) – operadores booleanos (o de conjunto Representaciones Paramétricas Polígonos - mallados Subdivision de superficies Superficies Implícitas Superficies basadas en puntos

4 Representaciones GeométricasObjeto construído mediante CSG convertido a polígonos

5 Idem, convertido a superficie implícita

6 D(A) Morphological Domain2D, Signed Euclidean Distance Fields D(A) D(A) +128 -127 A A D(A) Morphological Domain +128 -128

7 Geometry representaciónesOperadores de CSG aplicados a superficies implícitas

8 Representaciones GeométricasDescripciones de superficies basadas en puntos Ohtake, et al., SIGGRAPH 2003

9 Subdivisión del icosahedro = Esfera geodésica (R. Buckminster Fuller)“Spaceship Earth”, Epcot, Walt Disney World

10 Projecto Eden: bioma tropicalBiosfera de Montreal Projecto Eden: bioma tropical Grimshaw Architects, 2001

11 Proyecto “Houston Dome” (Discovery Channel )

12 Representaciones GeométricasSubdivisión de superficie Catmull-Clark de un cubo

13 Representaciones GeométricasSubdivisión de superficie (diferentes niveles de refinamiento) (ver Sierpiński…) Gráficos tomados de Subdivision.org

14 Subdivisión no uniforme y controlada

15 Subdivisión interpolando normales – transición suave

16 Jorge Márquez - IPCYL: Image Processing of Cylindrical Range DataJorge Márquez Flores, Isabelle Bloch and Francis Schmitt Jorge Márquez -

17 Combining Voxel Grid Data and Mesh Model

18 Geometrías de Mallado Global para Imágenes de Profundidad de Escenas 3D

19 Subdivisión de superficieCarpeta de Sierpiński – Subdivisión recursiva de un triángulo (en este caso no produce un mallado Euleriano – ver abajo) Otras aplicaciones de la subdivisión recursiva: voxelización de un mallado arbitrario (Derecha: ejemplo a dos órdenes de subdivisión) Nota: la subdivisión que presentan los cuadtrees (u octrees en 3D) no es Euleriana, pero no es el mallado de ninguna superficie; es una representación de árbol compacta de ocupación espacial.

20 Combinando dos resoluciones en un solo mallado Euleriano (a la derecha, ídem pero triangular)

21 Anidamiento de mallas en tres resoluciones

22 Voxeles dentro del objetoConstrucción de mallados triangulares a partir de un campo escalar o binario: Marching Cubes Voxeles dentro del objeto Cada configuración de ‘s determina un “parche” del mallado de la superficie

23 Marching-cubes segmentationCONSTRUCTION OF A MODEL OF THE HIGH GASTROINTESTINAL SYSTEM FOR THE SIMULATION OF UPPER ENDOSCOPY PROCEDURES Alfonso Gastelum, Lucely Mata Castro, Jorge Márquez Marching-cubes segmentation

24 Representaciones GeométricasVentajas y desventajas Facilidad de uso para diseño Facilidad y rapidez para renderizado Simplicidad Suavidad Detección de colisiones Flexibilidad (en muchos sentidos) Adecuadas para simulaciones Costo en memoria No adecuadas para objetos complejos Difícil usar Ray Tracing en algunos casos No funcionan bien con objetos muy irregulares

25 Modelado de superfices mediante mallados poligonales

26 Representaciones ParamétricasCurvas: Superficies: Volúmenes: etcétera... Nota: una función vectorial en de variable escalar (curva en el espacio) comprende n funciones escalares

27 Representaciones Paramétricas - No son únicas -Una misma Curva/superficie puede tener múltiples representaciones (diferencias resultan irrelevantes)

28 Geometría Diferencial SimpleTangente a una curva Tangentes a superficie Normal a una superficie También: curvatura, normales de una curva, vector bi-normal de una curva, etcétera... Casos degenerados: ó: Draw examples of degeneracies on board, Curva was shown in last slide...

29 Discretización Curvas arbitrarias tienen un incontable número de parámetros i.e. se especifican valores de coeficientes de las funciones en todos los puntos de una línea de números reales (como un espectro contínuo de Fourier).

30 Discretización Curvas arbitrarias tienen un incontable número de parámetros, formando un contínuo (espectro). Escoger un conjunto completo de bases de funciones Polinomios, series de Fourier, etc. Truncar el conjunto a un grado razonable, por ejemplo: Función representada por el vector (lista) de Las pueden ser vectores

31 Bases polinomiales Bases de potenciasLos elementos de son linealmente independientes, i.e. no es buena aproximación Si no se consideran varios aspectos se obtienen resultados mediocres, por ejemplo una rigidez extraña

32 Especificando una CurvaDados valores deseados (constricciones) cómo determinar Los coeficientes para una base de potencas cúbicas? Por lo pronto asumimos

33 Especificando una CurvaDados valores deseados (constricciones) cómo determinar Los coeficientes para una base de potencas cúbicas?

34 Especificando una CurvaDados valores deseados (constricciones) cómo determinar Los coeficientes para una base de potencas cúbicas?

35 Especificando una CurvaDados valores deseados (constricciones) cómo determinar Los coeficientes para una base de potencas cúbicas?

36 Especificando una CurvaDados valores deseados (constricciones) cómo determinar Los coeficientes para una base de potencas cúbicas?

37 Especificando una CurvaDados valores deseados (constricciones) cómo determinar Los coeficientes para una base de potencas cúbicas? Base de funciones de Hermite

38 Especificando una CurvaDados valores deseados (constricciones) cómo determinar Los coeficientes para una base de potencas cúbicas? Probably not a scale. Base de funciones de Hermite

39 Base de Hermite Curva especificada porValores de puntos esquina (end-points) Tangentes en dichos puntos (derivadas) Intervalo de parámetros arbitrario (casi siempre) No es necesario recalcular las bases de funciones Hermite cúbico Puede construirse para cualquier grado impar Derivadas en los puntos esquina o finales

40 Bézier Cúbico Similar a Hermite, pero especificando las tangentes indirectamente Nota: todos los puntos de control son puntos en el espacio, no tangentes.

41 Bézier Cúbico Similar a Hermite, pero especificando las tangentes indirectamente Relación entre coeficientes polinomiales y de Bézier:

42 Bézier Cúbico (d=3) Elementos de la base de funciones Bézier

43 Funciones Base (o base de funciones)Un punto en una curva de Hermite se obtiene multiplicando cada punto de control por una función y sumando todo Las funciones constituyendo una base de funciones

44 Superficies con Base de Polinomios Bézier

45 Cambiando Bases Bases de potencias, de Hermite y de Bézier son sólamente polinomios cúbicos Las tres bases generan el mismo espacio Como ejes diferentes en Cambios de base

46 Propiedades utiles de una baseConvex Hull (Carcasa convexa) Todos los puntos en curva quedan dentro de la caracasa convexa de los puntos de control La base de Bézier tiene la propiedad de carcasa convexa

47 Propiedades utiles de una baseInvariancia bajo clases de transformaciones Transformar curvas es lo mismo que transformar puntos de control Base de Bézier invariante para transformaciones afines Base de Bézier NO es invariante para transformaciones de perspectiva NURBS (Non-Uniform Rational Bézier Splines) son en extremo difíciles...

48 Propiedades utiles de una baseSoporte local Cambiar UN punto de control Punto tiene poco impacto en toda la curva Reglas de subdivisión muy convenientes Esquema de evaluación rápido Interpolación -vs- aproximación

49 Evaluación de DeCasteljauUn esquema de evaluación geométrica para Bézier

50 Uniendo Si se cambian a, b, o c hay que cambiar los demásPero si se cambian a, b, o c no se tienen cambios más allá de esos tres. *Soporte Local*

51 Superficies de Productos TensorSuperficie es una curva barrida a través del espacio Remplazar puntos de control de la curva con otras curvas

52 Bases de Superficie HermiteMas simetrías...

53 Funciones de Superficies Hermite-HumpMas simetrías...

54 Imágenes de una base de funciones armónicas en 2D (seno  seno)A través de estas funciones armónicas 2D se generan campos de desplazamiento que modelan la distorsión que se obtienen en las imágenes.

55 seno  seno

56 Interpolación BilinealParches-Spline de Coons bilinearmente mezclados (blended) usando Lifting ortogonal 4 perfiles (lados) f1 (x1,y) f2 (x2,y) f3 (x,y1) f4 (x,y2) f1 f3 f2 f4 p1 = f1(x1,y1) = f3(x1,y1) p2 = f2(x2,y1) = f3(x2,y1) p3 = f1(x2,y1) = f4(x2,y1) p4 = f2(x2,y2) = f4(x2,y2) pd = pa + pb – pc pd  f1  f3 … Interpolación Bilineal

57 Superficie Interpolada del Cráneo Usando Parches del Spline de Coons

58 En 3D hay Puntos y Polígonos de ControlPunto de control Polígono de control

59 NURBS

60 Representaciones por Puntos

61 Experimento Mental Adquisición de formas usando escáners Láser en 3DDe milliones a miles de millones de puntos Imagen típica (del objeto escaneado): A lo mucho algunos milliones de pixels (v.g ) ¡Más puntos que pixeles para representarlos...!

62 “Gráficos basados en puntos (point-based)”Superficies representadas sólo por puntos Quizás incluyendo normales SIN topología (=relaciones de conectividad) ¿Cómo realizar…? Renderizado (condicionamiento, transfos y despliegue) Operaciones de modelado, texturas, materiales, etc. Simulación (interacciones, deformaciones, animación)

63 Renderizado Para cada punto pintar una manchita (“splat”)Usar normales asociadas para sombreado Aplicar (quizás) textura Si los “splats” son más pequeños que el espaciamiento entre ellos, se producen agujeros (gaps). Y al contrario, el “splatting” de demasiados puntos es ineficiente (hay traslape o repetición). Ohtake, et al., SIGGRAPH 2003

64 From Rusinkiewicz y Levoy, SIGGRAPH 2000.Renderizado Algoritmo “QSplat” Construir árbol jerárgico de los puntos Cubrir con esferas un estimado tamaño de racimos (clusters) Renderizar los racimos basándose en el tamaño de la pantalla Usar las normales de los racimos para nodos internos From Rusinkiewicz y Levoy, SIGGRAPH 2000.

65 From Rusinkiewicz y Levoy, SIGGRAPH 2000.Renderizado From Rusinkiewicz y Levoy, SIGGRAPH 2000.

66 From Rusinkiewicz y Levoy, SIGGRAPH 2000.Renderizado Choices for splat shape. We show a scene rendered using squares, circles, y Gaussians as splat kernels. In the top row, each image uses the same recursion threshold of 20 pixels. Relative a squares, circles take roughly twice as long a render, y Gaussians take approximately four times as long. The Gaussians, however, exhibit significantly less aliasing. In the bottom row, the threshold for each image is adjusted a produce the same rendering time in each case. According a this criterion, the square kernels appear a offer the highest quality. From Rusinkiewicz y Levoy, SIGGRAPH 2000.

67 From Rusinkiewicz y Levoy, SIGGRAPH 2000.Renderizado From Rusinkiewicz y Levoy, SIGGRAPH 2000.

68 From Rusinkiewicz y Levoy, SIGGRAPH 2000.Renderizado From Rusinkiewicz y Levoy, SIGGRAPH 2000.

69 Definiendo una SuperficieDos métodos relacionados La superficie es como un “punto atractor” Superficies como conjuntos de puntos (point-set) Superficie Implícita Partición multi-nivel de implícitas unitarias Mínimos cuadrados móviles (MLS) implícitos (IMLS = Implicit Moving Least-Squares)

70 Superficies de Conjuntos de Puntos (Point-Set surfaces)La superficie es el atractor de un proceso de proyección iterado Hallar puntos cercanos Ajustar un plano (ponderado) Proyectar en el plano Repetir (iterar) ¿Converge? ¿Cómo ponderar los puntos? From Amenta y Kil, SIGGRAPH 2004.

71 Mínimos Cuadrados Móviles ImplícitosDefinir una función escalar que es cero cuando pasa a través de todos los puntos: Puntos muestra Vectores normales From Shen, et al., SIGGRAPH, 2004.

72 Mínimos Cuadrados Móviles ImplícitosLa función es cero en la frontera Decrece hacia afuera (inverso de la distancia) De Shen, et al., SIGGRAPH, 2004.

73 Mínimos Cuadrados Móviles ImplícitosMínimos Cuadrados Estándar

74 Interpolación de Mínimos Cuadrados Móviles

75 Interpolación de Mínimos Cuadrados MóvilesInterpolating Approximating

76 Interpolación de Mínimos Cuadrados MóvilesMínimos cuadrados estándar

77 Interpolación de Mínimos Cuadrados MóvilesMínimos cuadrados móviles (MLS) pi x

78 Interpolación de Mínimos Cuadrados MóvilesInterpolando Aproximando

79 Operaciones de EdiciónUna función implícita puede: Combinarse con operaciones booleanas Deformarse “Trasladarse” Componerse y más... Ohtake, et al., SIGGRAPH 2003

80 Operaciones de EdiciónOhtake, et al., SIGGRAPH 2003

81 Operaciones de EdiciónOhtake, et al., SIGGRAPH 2003

82 Simulación Basada en PuntosMLS originados en la literatura de Ing. mecánica Uso natural en gráficos para animación From Mueller, et al., SCA, 2004.

83

84 Non-uniform, rational B-spline (NURBS) is a mathematical model commonly used in computer graphics for generating and representing curves and surfaces • The control points determine the shape of the curve.

85 A subdivision surface is a method of representing a smooth surface via the specification of a coarser polygon mesh. • A Refinement Scheme is then applied to this mesh. • This process takes that mesh and subdivides it, creating new vertices and new faces.

86

87