Simulación de las Formas

Dpto. de Informática Fac. Cs. Físico-Mat. y Nat. Universidad Nacional De San Luis Argentina

Modeling

Computación Gráfica 



Según Fetter, CG referencia a la creación, almacenamiento y manipulación de modelos de objetos e imágenes. Simular un mundo 3D por medio de fórmulas matemáticas que describan la forma y el aspecto de los objetos. 



Los modelos deben ser susceptibles de ser manipulados de forma efectiva por un computador

Tres grandes aspectos a considerar:

- Modelado de las Formas - Modelado de la Apariencia - Visualización

Rio 14 - Roberto Guerrero @ 2014

2

Modeling

Simulación de la Forma Qué es un modelo? 

Captura las características sobresalientes (dato y comportamiento) de un objeto/fenómeno que esta siendo modelado. 



Modelo real: geometría intrínseca.  



Física (objetos reales) No física: funciones matemáticas, datos del tiempo.

Modelo abstracto: no tiene geometría intrínseca, pero puede visualizarse.  



Dato: geometría, apariencia, atributos, etc...

Por su disposición (organización de una compañía, diagramas) Cuantitativo (gráficos de ventas de stock)

Modelar es copiar con complejidad

Rio 14 - Roberto Guerrero @ 2014

3

Modeling

Estrategias Descomposición 

Usar la técnica de Divide y Vencerás.



Establecer una jerarquía de componentes geométricos.



Reducir a un conjunto de primitivas



Modelar objetos no simples mediante objetos simples.

cabeza tronco

punta

Rio 14 - Roberto Guerrero @ 2014

Composición

Descomposición

4

Modeling

Estrategias Organización 

Las formas primitivas deben estructurarse para establecer las relaciones de composición.

tornillo

cabeza (cilindro)

tronco (cilindro)

Rio 14 - Roberto Guerrero @ 2014

raíz

cuerpo

punta (cono)

hojas

5

Modeling

Estrategias Composición 

Las formas primitivas deben ser “manipuladas” matemáticamente para ensamblar el objeto final. trasladar trasladar y escalar

trasladar y rotar

Primitivas en su propio sistema de coordenadas de modelado

Rio 14 - Roberto Guerrero @ 2014

Composición (raíz) en un sistema de coordenadas común

6

Modeling

Representaciones Geométricas Primitivas 3D 

El mínimo dato es un punto en el espacio (x,y,z).



Cómo se arma la red de puntos para aproximar el objeto?



Rio 14 - Roberto Guerrero @ 2014

7

Modeling

Representaciones Geométricas Polilíneas

Poliedros

Funciones Explícitas

Funciones Paramétricas

Rio 14 - Roberto Guerrero @ 2014

8

Modeling

Representaciones Geométricas 

Una variedad de métodos de representación surgen a partir de las aplicaciones y la estructura de datos involucrada para su almacenamiento depende de la estrategia de modelado.

Design Elements Dimensions

1D



2D

Lineal 2D Models Draw

Polygonal Draw

Wireframe 3D Models

Surfaces

3D

Solids

Algunos métodos de modelado particulares se han desarrollado para contextos específicos.

Rio 14 - Roberto Guerrero @ 2014

9

Modeling

Representaciones Geométricas P. Mondrian, Composición en rojo, amarillo y azul, 1921, óleo sobre lienzo. (1D-2D - dibujo lineal)

V. Vasarely, Cheyt M. (2D-2D - dibujo poligonal)

Farolas en Gran Vía de los Reyes Católicos- Granada (1D-3D - wireframe)

Rio 14 - Roberto Guerrero @ 2014

10

Modeling

Representaciones Geométricas 2D Model / 1D Elements. Dibujo Lineal.

3D Model / 1D Elements. Wireframe. 3D Model / 2D Elements. Surfaces.

Rio 14 - Roberto Guerrero @ 2014

11

Modeling

Representaciones Geométricas 3D 

Es el método utilizado por el cual se intenta representar la forma de un objeto 3D dentro de un programa.



El método depende de:   



Estas características en conjunto con la representación elegida determinan: 

  



la naturaleza del objeto. la técnica utilizada para dar vida al objeto. la aplicación.

la estructura de datos, la forma de los algoritmos de procesamiento y el diseño de los programas en hardware (si existieran). el costo del procesamiento de un objeto a lo largo del pipeline 3D. la apariencia final del objeto, algunas formas son aproximadas mejor que otras. la facilidad de edición de la forma del objeto.

Las representaciones pueden clasificarse según si:  

modelan la superficie o el volumen total del objeto. modelan el objeto por representación aproximada o exacta.

Rio 14 - Roberto Guerrero @ 2014

12

Modeling

Clasificación De acuerdo con la frecuencia de uso:

Poligonal 

Los objetos son aproximados por medio de una malla de facetas poligonales planas.

Parches paramétricos Bicúbicos 

La representación es similar a la malla poligonal excepto que los polígonos individuales son superficies curvas (cuadriláteros curvos).

Geometría Sólida constructiva 

El objeto manufacturado surge de una “combinación” de formas elementales o primitivas geométricas.

Técnicas de subdivisión del espacio 

Divide el espacio del objeto en cubos elementales conocidos como voxels.

Rio 14 - Roberto Guerrero @ 2014

13

Modeling

Representación Poligonal 

Usualmente denominada Representación de Contorno debido a que es una descripción geométrica y topológica de la superficie de un objeto.



Permite representar con gran fidelidad un objeto con cualquier forma.



La superficie del objeto es aproximada por medio de una secuencia de polígonos.



Los polígonos son estructurados jerárquicamente: los polígonos se agrupan en facetas (caras), las caras en superficies y las superficies en objetos.

vértices

Rio 14 - Roberto Guerrero @ 2014

bordes

polígonos

caras

superficies

objeto

14

Modeling

Representación Poligonal Ventajas  El proceso de creación es simple.  Los polígonos pueden ser tratados como entidades independientes.  Ampliamente utilizado para eficiencia de algoritmos. Desventajas  En la reproducción de las superficies curvas de un objeto debido a la representación facetada, se debe acomodar el tamaño de los polígonos individuales dependiendo de la curvatura local del espacio a representar.  Problemas de escalabilidad. A gran distancia, los objetos con gran cantidad de polígonos tienden a verse como un solo polígono.... o un punto.  En la creación de objetos complejos. Puede implicar gran cantidad de tiempo y costo.  Se debe almacenar las relaciones topológicas de los elementos en una base asociada.

Rio 14 - Roberto Guerrero @ 2014

15

Modeling

Rio 14 - Roberto Guerrero @ 2014

16

Modeling

Modelado de Objetos Poligonales  



Las estrategias de modelado son básicamente fuerza bruta. El desarrollo de un modelo poligonal se basa en “colocar” puntos (vértices) por medio de algún dispositivo 3D. Es necesario asegurar una aproximación “adecuada” del objeto que se esta pretendiendo modelar.

Diferentes estrategias 1- Utilizar un digitalizador 3D o cualquier estrategia manual equivalente. 2- Utilizar un dispositivo automático (explorador láser). 3- Generar un objeto a partir de una descripción matemática. 4- Generar un objeto por medio de barrido.

Rio 14 - Roberto Guerrero @ 2014

17

Modeling

Modelado Manual  



Utiliza un digitalizador 3D. El operador usa su experiencia y buen juicio para la captura de puntos del objeto, los cuales serán los vértices de los polígonos. Una estrategia muy común que asegura una buena representación consiste en dibujar una malla sobre la superficie del objeto.

Rio 14 - Roberto Guerrero @ 2014

18

Modeling

Modelado Manual

Inition Digiscan

Rio 14 - Roberto Guerrero @ 2014

19

Modeling

Modelado Automático 

  

Utiliza un explorador láser el cual asegura una malla de polígonos de alta resolución y muy confiable. Usualmente el objeto es colocado en una base rotativa interceptando la ruta del rayo. El láser retorna un conjunto de curvas de contorno (planos paralelos) (fig. 15-b). Se requiere de un algoritmo de “skinning” (fig. 15-a). Une para de puntos de contornos consecutivos y los convierte en polígonos (fig. 15-c).

Rio 14 - Roberto Guerrero @ 2014

20

Modeling

Modelado Automático

Fig. 15-a Rio 14 - Roberto Guerrero @ 2014

Fig. 15-b

Fig. 15-c 21

Modeling

Modelado Automático

Inition Digiscan

Rio 14 - Roberto Guerrero @ 2014

22

Modeling

Modelado Matemático 

 

El objeto es generado por medio de una descripción matemática que es barrida a lo largo de una ruta. Los sólidos de revolución son un caso especial de este método. La resolución poligonal es controlado fácilmente por el algoritmo que lo genera.

Rio 14 - Roberto Guerrero @ 2014

23

Modeling

Modelado por Barrido  





Conserva la idea previa y la generaliza. En el modelado matemático, tanto la sección de barrido como su ruta son especificados por medio de una fórmula matemática. La generalización implica que la sección de barrido y la ruta (curva) pueden tomar cualquier forma. Éstas son curvas paramétricas que pueden variar en su descripción.

Q(u) = au3 + bu2 + cu + d 

Los objetos generados son denominados “sólidos de canal”.

Rio 14 - Roberto Guerrero @ 2014

24

Modeling

Modelado por Barrido Presentan dos problemas: 



Cuáles deberían ser los intervalos entre los puntos ubicados a lo largo de la sección de barrido?. Cual debería ser la orientación de la sección a lo largo de la ruta (curva)?.

Rio 14 - Roberto Guerrero @ 2014

25

Modeling

Parches Paramétricos Bicúbicos 

4 vértices unidos por 4 lados que constituyen curvas bicúbicas. El interior de el parche es una superficie curva bicúbica.



La superficie del objeto puede ser interpolada o aproximada por la malla del parche.



Usualmente el parche se define como Q(u,v), donde u,v son parámetros y Q es un polinomio cúbico.



Un tamaño conveniente para los parches es de 16 puntos 3D, denominados puntos de control.



Estos puntos de control son utilizados por funciones polinomiales predefinidas denominadas funciones bases.

Rio 14 - Roberto Guerrero @ 2014

26

Modeling

Parches Paramétricos Bicúbicos Ventajas  La representación es “fluída”, mas aún si los puntos de control de los parches se ajustan por medio de software.  Permiten obtener información de propiedades de masa del objeto tales como volumen, superficie del área, momento e inercia. Desventajas  Modelara la estructura de datos es dificultosa.  Es dificil mantener la integridad del modelo.  Demanda grandes volúmenes de memoria con penalidades por tiempo de transferencia de base de datos y uso de memoria.

Rio 14 - Roberto Guerrero @ 2014

27

Modeling

Modelado con mallas de parches Modelar con este método implica tener un conocimiento detallado de la teoría asociada a los parches paramétricos bicúbicos.



Diferentes estratégias  Trabajar con un único parche como un objeto en sí mismo. Es directo, aunque no simple, ej: el cuerpo de un auto. 

Crear una malla de parches a partir del objeto real. Se establecen un conjunto de puntos que se encuentran en la superficie del objeto a ser representado. Luego el parche es regenerado a partir de estos puntos.



Utilizar técnicas de barrido de parches. El parche paramétrico es considerado como la sección que debe ser barrida a lo largo de un ruta.

Rio 14 - Roberto Guerrero @ 2014

28

Modeling

Modelado con mallas de parches

Rio 14 - Roberto Guerrero @ 2014

29

Modeling

Ejemplo 

La tetera de Utah. –

Una malla “rasonable” de polígonos. 2048 vértices x 3 números reales.

–

Una malla de 32 parches. 32 parches x 16 puntos de control/parche. Los parches comparten 12 puntos para asegurar la continuidad con los vecinos. 306 vértices x 3 números reales.

Rio 14 - Roberto Guerrero @ 2014

30

Modeling

Geometría de Sólido Constructiva  







Es una representación volumétrica. Es una representación exacta dentro de los límites de formas específicas. Usualmente, los objetos son partes que serán manufacturadas por fundición, mecánicamente o por extrusión. Se construyen a partir de operaciones que combinan objetos sólidos elementales denominados primitivas geométricas Las operaciones realizadas son un Conjunto de operadores Booleanos y Transformaciones Lineales.

Rio 14 - Roberto Guerrero @ 2014

31

Modeling

Geometría de Sólido Constructiva Ventajas  Es simple.  La representación define tanto la forma del objeto como su historia de modelado.  Los cambios en el modelo implican cambios triviales en el proceso de modelado. Desventajas  Se requierre mucho tiempo computacional para generar una imagen del modelo..  Las operaciones booleanas son globales, afectan al sólido en su totalidad. Las operaciones locales no son simples de implementar Ej.: la unión de superficies afiladas.

Rio 14 - Roberto Guerrero @ 2014

32

Modeling

Geometría de Sólido Constructiva

Rio 14 - Roberto Guerrero @ 2014

33

Modeling

Subdivisión del Espacio  



Es una representación volumétrica basada en elementos cúbicos denominados voxels. Se considera el espacio del objeto en su totalidad y se rotula cada punto en el espacio acorde con su ocupación del espacio. Se rotula cada voxel según pertenezca al objeto o se encuentre en un espacio vacío.

Rio 14 - Roberto Guerrero @ 2014

34

Modeling

Subdivisión del Espacio Ventajas  Es muy significativo en ciertos estadios del proceso de rendering.  Puede ser utilizado como una representación intermedia: establecer la distribución de los objetos en la escena..  Este esquema es utilizado solamente en contextos donde los beneficios superan su costo. Ej.: rendering de volúmenes en imágenes médicas. Desventajas  Es muy costoso en concepto de consumo de memoria..





Un octree es una estructura de datos jerárquica que especifica la apropiación de espacio del objeto por parte de las regiones cúbicas. El concepto de octree puede representarse fácilmente mediante un quadtree que representa la apropiación de espacio de una región 2D.

Rio 14 - Roberto Guerrero @ 2014

35

Modeling

Subdivision del Espacio

Rio 14 - Roberto Guerrero @ 2014

36

Modeling

Rendering de volúmenes en Imágenes Médicas

(a)

Rio 14 - Roberto Guerrero @ 2014

(b)

37

Modeling

Computación Gráfica 



Según Fetter, CG referencia a la creación, almacenamiento y manipulación de modelos de objetos e imágenes. Simular un mundo 3D por medio de fórmulas matemáticas que describan la forma y el aspecto de los objetos. 



Los modelos deben ser susceptibles de ser manipulados de forma efectiva por un computador

Tres grandes aspectos a considerar:

- Modelado de las Formas - Modelado de la Apariencia - Visualización

Rio 14 - Roberto Guerrero @ 2014

38

Modeling

Manipulación de los Objetos 

Los objetos deben ser “manipulados”, preferentemente operados matemáticamente.

Rio 14 - Roberto Guerrero @ 2014

39

Modeling

Vértices en movimiento Un objeto puede considerarse como un conjunto de puntos que se desplazan.  







Una línea es dibujada trazando la ruta de un punto que se desplaza (entidad de 1D). Un cuadrado es dibujado trazando la ruta de los vértices de una línea que se desplaza perpendicularmente a sí misma (entidad 2D).

Un cubo es dibujado trazando la ruta de los vértices de un cuadrado que se desplaza perpendicularmente a si mismo (entidad 3D). Un círculo es dibujado desplazando un punto alrededor de un punto central y a una longitud fija. Los vértices son la información crítica en la definición de un objeto. Cómo se mueven??

Rio 14 - Roberto Guerrero @ 2014

40

Modeling

Transformaciones Geométricas 

Las transformaciones geométricas mapean puntos desde un espacio a puntos en otro espacio: (x',y',z') = f(x,y,z).



Las transformaciones pueden ser muy simples, tales como escalar cada coordenada, o complejas, tales como giros y curvas no lineales.



Nos concentraremos en las transformaciones que pueden ser representadas fácilmente mediante operaciones matriciales.

Representación 

Se puede representar un punto, p = (x,y), en el plano Como un vector columna

O como un vector fila Rio 14 - Roberto Guerrero @ 2014

41

Modeling

Transformaciones Geométricas 

Se puede representar una transformación 2D M por medio de una matriz



Si p es un vector columna, M debe colocarse a la izquierda:



Si p es un vector fila,

Rio 14 - Roberto Guerrero @ 2014

debe colocarse a la derecha:

42

Modeling

Traslación 

Para mover un punto se realiza la suma de un escalar a cada una de las componentes del vector v’ = v + t donde y

v=

[] [ ] [ ] x x' dx ,v' = ,t = y y' dy

x’ = x + dx y’ = y + dy



Para mover polígonos: simplemente se trasladan los vértices y luego se redibujan las líneas entre ellos



Preserva las longitudes (isométrica)



Preserva los ángulos (conforme)

Y

6 5

[] 4 4

4

dx = 2 dy = 3

3 2

[] 2 1

1 0 1

2

3

4

5

6

7

8

9

10

X Nota: La casa se desplaza en forma relativa al origen Rio 14 - Roberto Guerrero @ 2014

43

Modeling

Escalado 

Se multiplica cada una de las componentes del vector por un escalar v’ = Sv donde

y

[] [ ]

v=

S=

x x' , v '= y y'

[ ] Sx 0

0 Sy

x ' =S x x y ' =S y y Y 

No preserva las longitudes



No preserva los ángulos (excepto si el escalado es uniforme)

6 5 4 3

sx = 3

2

sy = 2

1

[] 2 1

[] 9 2

[] 6 2

[] 3 1

0 1

2

3

4

5

6

7

8

9

10

X

Nota: La casa se desplaza en forma relativa al origen Rio 14 - Roberto Guerrero @ 2014

44

Modeling

Rotación 

La rotación de un vector a lo largo de un ángulo  v’ = R v

donde

v=

[] [ ] x x' ,v' = y y'

v’ v r

x’ = x cos– y sin y’ = x sin+ y cos Rio 14 - Roberto Guerrero @ 2014

[

R =

cos  −sin  sin  cos 

] 45

Modeling

Rotación 

Preserva las longitudes y los ángulos Y

6 5

θ=

π 6

4 3 2

θ

1

0 1

2

3

4

5

6

7

8

9

10

X

Nota: La casa se desplaza en forma relativa al origen

Rio 14 - Roberto Guerrero @ 2014

46

Modeling

Coordenadas Homogéneas 

Las operaciones de traslación, escalado y rotación están expresadas como (no homogéneo): traslación:

v’ = v + t

escala:

v’ = Sv

rotación:

v’ = R v



La composición entre ellas es difícil de expresar dado que la traslación no esta expresada como una multiplicación de matrices.



Las coordenadas homogénas permiten que las tres operaciones sean expresadas de la misma manera, permitiendo la composición de las mismas mediante multiplicación de matrices P 2d  x , y   P h  wx , wy , w  , w≠0 P h  x ', y ', w  , w≠0 P 2d  x , y =P 2d



x' y' , w w



w es 1 para poder realizar transformaciones afines Rio 14 - Roberto Guerrero @ 2014

47

Modeling

Qué es 

[] x y w

?

P2d es la intersección de la línea determinada por P h con el plano w = 1 W

Ph (x,y,w) 1

P2d (x/w,y/w,1) X

Y 

Por lo tanto, un número infinito de puntos corresponden a (x, y, 1): ellos constituyen la línea completa (tx, ty, tw)

Rio 14 - Roberto Guerrero @ 2014

48

Modeling

Transformaciones en Coordenadas Homogéneas 

Para los puntos escritos en formato homogéneo con coordenadas

[]

x y , 1

La traslación, escalado y rotación relativos al origen son expresados en forma homogénea de la siguiente manera: 1 0 dx T  dx , dy = 0 1 dy ; v ' =T  dx , dy  v 0 0 1

[

]

[ ]

sx S  s x , s y = 0 0

[

cos φ R  φ = sin φ 0 Rio 14 - Roberto Guerrero @ 2014

0 sy 0

0 0 ; v ' =S  s x , s y  v 1

−sin φ cos φ 0

]

0 0 ; v '= R  φ  v 1 49

Modeling

Rotación y Escalado 2D - Particularidades 

La Rotación y el Escalado estan definidos respecto del origen del sistema de coordenadas. Casa (C)



S(1,2)C

R(π/2)S(1,2)C

Supongamos un objeto no centrado en el origen. ¿Cómo lo rotamos sobre su centro?

(q es el centro de definición del objeto) Rio 14 - Roberto Guerrero @ 2014

50

Modeling

Rotación y Escalado 2D - Particularidades 

Un objeto no centrado en el origen debe ser rotado un ángulo θ



Solución: mover el objeto al origen, luego rotarlo, luego retornarlo a su posición original.



Es deseable poder componer transformaciones sucesivas…

Rio 14 - Roberto Guerrero @ 2014

51

Modeling

Rotación y Escalado 2D - Particularidades 

Problema: rotar la casa en un ángulo θ y duplicar su altura en “su posición” (su centro de coordenadas).

dy dx





La matriz T permite evitar traslaciones no deseadas que suceden cuando se escala y rota un objeto no centrado en el origen. T(dx,dy)S(1,2)R(θ)T(-dx,-dy)C R(θ)T(-dx,-dy)C S(1,2)R(θ)T(-dx,-dy)C Casa (C) T(-dx,-dy)C

Importante: la multiplicación de matrices no es conmutativa!!.. El orden es importante!!

Rio 14 - Roberto Guerrero @ 2014

52

Modeling

Transformaciones 3D Básicas (sistema de coordenadas dextrógiro)

y

x z



Traslación

Rio 14 - Roberto Guerrero @ 2014

53

Modeling

Transformaciones 3D Básicas (sistema de coordenadas dextrógiro)

y

x z



Escalado

Rio 14 - Roberto Guerrero @ 2014

54

Modeling

Transformaciones 3D Básicas (sistema de coordenadas dextrógiro)



Rotación en eje X



Rotación en eje Y



Rotación en eje Z

Rio 14 - Roberto Guerrero @ 2014

[ [ [

1 0 0 0

0 cos θ sin θ 0

cos θ 0 −sin θ 0 cos θ sin θ 0 0

0 1 0 0

0 −sin θ cos θ 0

0 0 0 1

sin θ 0 cos θ 0

0 0 0 1

0 0 1 0

0 0 0 1

−sin θ cos θ 0 0

] ] ] 55

Modeling

Oblicuidad/Cizalla/Traslación 

Deforma un objeto hacia un lado (“lo aplasta”) Skew θ =

[ ] 1 tan θ 1

1 0



Los cuadrados se convienten en paralelogramos – las coordenadas x se desplazan hacia la derecha, mientras las coordenadas y permanecen iguales.



El ángulo de 90° se convierte en θ .



Simula “aplastar” un mazo de cartas desplazando a las cartas hacia un lado – las cartas se dezplazan respecto de la base.

Y

6 5 4

θ=

π 4

3



La base permanece horizontal (y=1) pero se dezplaza hacia la derecha...

2

θ

1 0 1

Rio 14 - Roberto Guerrero @ 2014

2

3

4

5

6

7

8

9

10

X 56

Modeling

Oblicuidad/Cizalla/Traslación 

Los puntos en y=1 permanecen en y=1, pero son trasladados hacia la derecha.



Se preservan las distancias entre los puntos en esta línea.



Una traslación homogénea de 1D es similar a una trasnformacion de cizalla 2D.

[ ][ 1 0

1 1 tan θ ≡ 0 1

dx 1

] original y-axis T=

[ ] 1 0

1 1

T

Rio 14 - Roberto Guerrero @ 2014

57

Modeling

Oblicuidad/Cizalla/Traslación  

Un poco mas complicado en 3D. Una transformación de cizalla respecto del plano x-z.

P’ = (Px + bPy , Py , Pz)

Rio 14 - Roberto Guerrero @ 2014

58

Modeling

Resumen Dónde estamos?

Espacio del Modelo

escalado, traslación, rotación, ....

Espacio del Mundo

Rio 14 - Roberto Guerrero @ 2014

59

Modeling

Rio 14 - Roberto Guerrero @ 2014

60