Download - Computación Gráfica 12
Computación Gráfica 12
Curvas y Superficies
Temario
Representaciones de curvas y de superficies
Splines y otras bases polinomial
Puntos
22
Representaciones Geométricas
• Geometrí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
33
Representaciones Geométricas
Objeto construído mediante CSG convertido a polígonos
44
Idem, convertido a superficie implícita
55
66
2D, Signed Euclidean Distance Fields D(A)
+12+1288
00
--128128
AA AA DD(A)(A)+128+128
0 0
--127127
00
D(A) Morphological Domain
Geometry representaciónes
Operadores de CSG aplicados a superficies implícitas
77
Descripciones de superficies basadas en
puntos
Ohtake, et al., SIGGRAPH 2003
Representaciones Geométricas
88
99
Subdivisión del icosahedro = Esfera geodésica (R. Buckminster Fuller)
“Spaceship Earth”, Epcot, Walt Disney World
1010
Projecto Eden: bioma tropicalGrimshaw Architects, 2001
Biosfera de Montreal
1111
Proyecto “Houston Dome” (Discovery Channel )
Representaciones Geométricas
Subdivisión de superficie Catmull-Clark de un cubo
1212
Subdivisión de superficie(diferentes niveles de refinamiento)
Gráficos tomados de Subdivision.org
(ver Sierpiński…)
Representaciones Geométricas
1313
Subdivisión no uniforme y controlada
1414
Subdivisión interpolando normales – transición suave
1515
1616Jorge Márquez -
IPCYL: Image Processing of Cylindrical Range Data Jorge Márquez Flores, Isabelle Bloch and Francis Schmitt
Combining Voxel Grid Data and Mesh Model
1818
Geometrías de Mallado Global para Imágenes de Profundidad de Escenas 3D
Carpeta 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.
Subdivisión de superficie
Combinando dos resoluciones en un solo malladoEuleriano (a la derecha, ídem pero triangular)
Anidamiento de mallas en tres resoluciones
Construcción de mallados triangulares a partir de un campo escalar o binario:
Marching CubesVoxeles dentro del objeto
Cada configuración de ‘s determina un “parche” del mallado de la superficie2222
2323
CONSTRUCTION OF A MODEL OF THE HIGH GASTROINTESTINAL SYSTEM FOR THE CONSTRUCTION OF A MODEL OF THE HIGH GASTROINTESTINAL SYSTEM FOR THE SIMULATION OF UPPER ENDOSCOPY PROCEDURESSIMULATION OF UPPER ENDOSCOPY PROCEDURES
Alfonso Gastelum, Lucely Mata Castro, Jorge MárquezAlfonso Gastelum, Lucely Mata Castro, Jorge Márquez
Marching-cubes segmentation
Ventajas 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
Representaciones Geométricas
2424
Modelado de superfices mediante mallados poligonales
n
2525
( )( ) ( )
( )
x uu y u
z u
x
Representaciones Paramétricas
( ), ,nu u x x x
n
2
2( , ), , , o: ( , )( ), ,
n
nu v u v u v
x x xx x u x u
3
3( , , ), , , , o: ( , , )( ), ,
n
nu v w u v w u v w
x x xx x u x u
Nota: una función vectorial en de variable escalar (curva en el espacio) comprende n funciones escalares
etcétera...
Curvas:
Superficies:
Volúmenes:
• Una misma Curva/superficie puede tener múltiples representaciones (diferencias resultan irrelevantes)
( ) ( , )u u ux
Representaciones Paramétricas- No son únicas -
3 3( ) ( , )u u ux
Geometría Diferencial Simple
Tangente 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: ó:
2828
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).
2929
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
o 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
0
( ) ( )i ii
u c u
x
3 3
0 0
( ) ( ) ii i i
i i
y u c u c u
ic
ic
3
03 3
0 03
0
( )
( ) ( ) ( )
( )
xi ii
i i yi ii i
zi ii
c u
u u c u
c u
x c
Bases polinomiales
Bases de potencias
Los elementos de son linealmente independientes, i.e. no es buena aproximación
Si no se consideran varios aspectos se obtienen resultadosmediocres, por ejemplo una rigidez extraña
3131
Especificando una Curva
Dados valores deseados (constricciones) cómo determinar Los coeficientes para una base de potencas cúbicas?
Por lo pronto asumimos
3232
Dados valores deseados (constricciones) cómo determinar Los coeficientes para una base de potencas cúbicas?
Especificando una Curva
3333
Dados valores deseados (constricciones) cómo determinar Los coeficientes para una base de potencas cúbicas?
Especificando una Curva
3434
Dados valores deseados (constricciones) cómo determinar Los coeficientes para una base de potencas cúbicas?
Especificando una Curva
3535
Dados valores deseados (constricciones) cómo determinar Los coeficientes para una base de potencas cúbicas?
Especificando una Curva
3636
Dados valores deseados (constricciones) cómo determinar Los coeficientes para una base de potencas cúbicas?
Base de funciones de Hermite
Especificando una Curva
3737
Dados valores deseados (constricciones) cómo determinar Los coeficientes para una base de potencas cúbicas?
Base de funciones de Hermite
Probably not a scale.
Especificando una Curva
3838
Base de Hermite• Curva especificada por
Valores 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
3939
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.
4040
Bézier CúbicoSimilar a Hermite, pero especificando las tangentes indirectamente
Relación entre coeficientes polinomiales y de Bézier:
4141
Bézier Cúbico (d=3)
Elementos de la base de funciones Bézier
0
0.2
0.4
0.6
0.8
1
1.2
B0
B1
B2
B3
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
-0.4
-0.2
0
0.2
0.4
0.6
0.8
1
1.2
x1
x0
x'1
x'0
Superficies con Base de Polinomios Bézier
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
4545
Propiedades utiles de una base
Convex 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
4646
Propiedades utiles de una base
Invariancia 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...
4747
Propiedades utiles de una base
• Soporte 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
4848
Evaluación de DeCasteljau
Un esquema de evaluación geométrica para Bézier
4949
Uniendo
Si se cambian a, b, o c hay que cambiar los demás
Pero si se cambian a, b, o c no se tienen cambios más allá de esos tres. *Soporte Local*
5050
Superficies de Productos Tensor
Superficie es una curva barrida a través del espacio
Remplazar puntos de control de la curva con otras curvas
5151
Bases de Superficie Hermite
Mas simetrías...5252
Funciones de Superficies Hermite-Hump
Mas simetrías...5353
5454
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.
5555
seno seno
Parches-Spline de Coons bilinearmente mezclados (blended) usando Lifting ortogonal
4 perfiles (lados)f1 (x1,y)f2 (x2,y)f3 (x,y1)f4 (x,y2)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)
Interpolación Bilineal
f1
f2
f3
f4
pd = pa + pb – pc
pd f1 f3 …
Superficie Interpolada del Cráneo UsandoParches del Spline de Coons
Punto de control
Polígono de control
En 3D hay Puntos y Polígonos de Control
NURBS
6060
Representaciones por Puntos
Experimento Mental
• Adquisición de formas usando escáners Láser en 3Do De milliones a miles de millones de puntos
• Imagen típica (del objeto escaneado):o A lo mucho algunos milliones de pixels (v.g. 20482)
• ¡Más puntos que pixeles para representarlos...!
“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)
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
Renderizado• Algoritmo “QSplat”
Construir árbol jerárgico de los puntosCubrir con esferas un estimado tamaño de racimos (clusters)Renderizar los racimos basándose en el tamaño de la pantallaUsar las normales de los racimos para nodos internos
From Rusinkiewicz y Levoy, SIGGRAPH 2000.
6464
Renderizado
From Rusinkiewicz y Levoy, SIGGRAPH 2000. 6565
Renderizado
From Rusinkiewicz y Levoy, SIGGRAPH 2000. 6666
Renderizado
From Rusinkiewicz y Levoy, SIGGRAPH 2000. 6767
Renderizado
From Rusinkiewicz y Levoy, SIGGRAPH 2000. 6868
Definiendo una Superficie
Dos 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)
6969
Superficies de Conjuntos de Puntos
(Point-Set surfaces)• La superficie es el atractor de un proceso
de proyección iteradoHallar puntos cercanos
Ajustar un plano (ponderado)
Proyectar en el plano
Repetir (iterar)
• ¿Converge?
• ¿Cómo ponderar los puntos?
From Amenta y Kil, SIGGRAPH 2004. 7070
Mínimos Cuadrados Móviles Implícitos
Definir una función escalar que es cero cuando pasa a través de todos los puntos:
From Shen, et al., SIGGRAPH, 2004.
( ) 0if p
7171
Puntos muestra
Vectores normales
Mínimos Cuadrados Móviles Implícitos
De Shen, et al., SIGGRAPH, 2004.
La función es cero en la fronteraDecrece hacia afuera (inverso de la distancia)
Mínimos Cuadrados EstándarMínimos Cuadrados Estándar
Mínimos Cuadrados Móviles Implícitos
7373
Mínimos Cuadrados MóvilesMínimos Cuadrados Móviles
Interpolación de Mínimos Cuadrados Móviles
7474
Interpolación de Mínimos Cuadrados Móviles
Mínimos CuadradosMínimos Cuadrados
Móviles
InterpolatingInterpolating
ApproximatingApproximating
7575
Interpolación de Mínimos Cuadrados Móviles
1 1( )
( ) NN
bc
b
p
p
T
T
Mínimos cuadrados estándar
c T TB B Bc T TB B B
2 2( ( )) ( ) ( ( ))W c W x x xB B BT T
2 2
1( )
( )w r
r
Interpolación de Mínimos Cuadrados Móviles
Mínimos cuadrados móviles (MLS)
1 1 1 1( , ) ( ) ( , )
( , ) ( , )( )N N NN
w b wc
w wb
x p p x p
x p x pp
T
T
xpi
Interpolación de Mínimos Cuadrados Móviles
Mínimos cuadrados móviles
Mínimos cuadrados
Interpolando
Aproximando
Operaciones de Edición
• Una función implícita puede:
Combinarse con operaciones booleanas
Deformarse
“Trasladarse”
Componerse
y más...
Ohtake, et al., SIGGRAPH 2003
Operaciones de Edición
Ohtake, et al., SIGGRAPH 2003 8080
Ohtake, et al., SIGGRAPH 2003
Operaciones de Edición
8181
Simulación Basada en Puntos
MLS originados en la literatura de Ing. mecánica
Uso natural en gráficos para animación
From Mueller, et al., SCA, 2004. 8282
8383
Non-uniform, rational B-spline(NURBS) is a mathematicalmodel commonly used in
computer graphics forgenerating and representing
curves and surfaces• The control points determine
the shape of the curve.
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 subdividesit, creating new vertices
and new faces.