Curvas e Superf ciesmotta/dim102/CurvasSuperficies.pdf · como achar polígonos que compartilham...

DIM102 1  

Curvas e Superfícies

35M34 – Sala 3E1Bruno Motta de Carvalho

DIMAp – Sala 15 – Ramal 227

DIM1022

Introdução

A modelagem e desenho de curvas suaves são necessárias em várias aplicações de computação gráfica, seja na modelagem de objetos já existentes ou na criação de novos objetosNós vamos abordar aqui a modelagem de curvas e superfícies e não de sólidosSuperfícies são modeladas usando­se malhas de polígonos, superfícies bicúbicas paramétricas e superfícies quádraticasCurvas cúbicas paramétricas são utilizadas na modelagem de curvas e são a base das superfícies bicúbicas paramétricas 

DIM1023

Malhas de PolígonosÉ uma coleção de vértices, arestas e polígonos conectados tal que cada aresta é compartilhada por no máximo dois polígonos, e cada vértice é compartilhado por no mínimo duas arestasTrês representações são possíveis: 

Explícita – Cada polígono é representado por uma lista de coordenadas de vérticesPonteiros para uma lista de vértices – Cada vértice é armazenado somente uma vez. Polígono é definido por uma lista de índices de vérticesPonteiros para uma lista de arestas – Cada aresta é armazenado somente uma vez. Polígono é definido por uma lista de índices de vértices e arestas

DIM1024

Representações

Representações são avaliadas de acordo com o tempo necessário para realizar tarefas comuns como achar as arestas de um polígonoRepresentação explícita é simples mas ineficiente e ocupa muito espaço. Exemplo: como achar polígonos que compartilham um vértice?Ponteiros para uma lista de vértices é mais eficiente, mas como achar polígonos que compartilham uma aresta?Usando ponteiros para uma lista de arestas, um polígono é descrito por uma lista de arestas, cujas entradas são descritas por uma lista de vértices e dos polígonos a que pertencem

DIM1025

Consistência de Representações

Malhas de polígonos geralmente são geradas interativamente, logo erros são comunsDependente da aplicação, a checagem pode obrigar que:

 os polígonos sejam fechados,  que cada vértice seja usado pelo menos duas vezesque a malha seja completamente conectada, etc. 

A representação que usa listas de arestas é a mais apropriada a este tipo de checagem pois tem mais informações

DIM1026

Curvas Cúbicas Paramétricas

Polilinhas e polígonos são aproximações lineares por partes de primeiro grau à curvas e superfícies, respectivamenteIneficientes para representação de curvas e superfícies (necessitam de muitos pontos para ter uma precisão aceitável)Pode­se usar representações explícitas, implícitas ou paramétricasRepresentações explícitas tem problemas para representar curvas arbitrárias

DIM1027

Curvas Cúbicas Paramétricas

Em representações implícitas é difícil de se controlar tangentes de curvas que se unem, ou a equação pode ter mais soluções que o desejadoAs curvas paramétricas são aproximadas por curvas polinomiais por partes. Cada segmento Q da curva é definido por três funções x, y e z, que são polinômios cúbicos no parâmetro tPolinômios cúbicos são um compromisso entre a representação de curvas arbitrárias em 3D e complexidade computacional na manipulação da representação do objeto

DIM1028

Curvas Cúbicas ParamétricasOs polinômios cúbicos que definem a curva Q(t) são

ou 

Q t x t y t z t

x t axt3 b

xt2 c

xt d

x,

y t ayt3 b

yt2 c

yt d

y,

z t azt3 b

zt2 c

zt d

z, 0 t 1

Q t x t y t z t T M G onde

T t3 t2 t 1 , C

m11

m12

m13

m14

m21

m22

m23

m24

m31

m32

m33

m34

m41

m42

m43

m44

e G

G1

G2

G3

G4

DIM1029

Curvas Cúbicas Paramétricas

A derivada de Q(t) é o vetor tangente paramétrico da curvaSe dois segmentos de curvas se encontram a curva tem continuidade geométrica G0, e se a direção de suas tangentes neste ponto tem a mesma direção a curva tem continuidade G1

Se os vetores tangentes paramétricos são iguais no ponto de encontro das curvas a curva tem continuidade paramétrica C1

Se os valores de                       são iguais até a n­ésima derivada, a curva tem continuidade Cn

d n

dtnQ t

DIM10210

Curvas Cúbicas Paramétricas

DIM10211

Curvas Cúbicas Paramétricas ­ História

• Uma spline é uma curva paramétrica definida por pontos de controle– O termo spline vem da área de 

desenho em engenharia, onde uma spline é um pedao de madeira ou metal flexível usado para desenhar curvas suaves

– Pontos de controle são ajustados pelo usuário para controlar a forma da curva usando­se pesos (ducks)

• Splines de madeira tem continuidade de segunda ordem e passam obrigatoriamente pelos pontos de controle

DIM10212

Curvas de Bézier

Segmento de curva definido por quatro pontos de controle Primeiro e quarto pontos de controle são interpoladosSegundo e terceiro pontos definem, junto com primeiro e quarto,respectivamente, tangentes da curva no primeiro e quarto pontos As funções de base são sempre positivas e sua soma é sempre 1 (polinômios de Bernstein). Por causa disso, curva está localizada no fecho convexo dos seus pontos de controle

DIM10213

Curvas de Bézier

Se dois segmentos de curva são especificados por 7 pontos de controle, a curva tem continuidade G1 se P3­P4=k(P4­P5), k>0 (se k=1 a curva tem continuidade C1)

Q t T MB

GB

onde T t3 t2 t 1 ,

MB

1 3 3 13 6 3 0

3 3 0 01 0 0 0

e GB

P1

P2

P3

P4

, logo

Q t 1 t 3 P1

3t 1 t 2 P2

3 t2 1 t P3

t3 P4

DIM10214

Curvas de Bézier

DIM10215

Curvas de Bézier

Funções de base (blending) de Bézier

DIM10216

B­Splines Uniformes Não­Racionais

B­splines, ao contrário das splines naturais, tem controle local, isto é, a mudança de um ponto de controle só afeta alguns segmentos da curvaB­splines cúbicas aproximam (ao contrário das splines naturais) uma série de m+1 pontos de controle P0, ...,Pm, m ≤ 3, por uma curva com        m ­ 2 segmentos de curvas polinomiais cúbicos  Q3, ..., Qm

O parâmetro t é definido como ti ≤ t < ti+1, para    3 ≤i ≤m. Nocaso de de m=3, existe uma única curva Q3 definida no intervalo t3 ≤ t <t4 por quatro pontos de controle P0 até P3

DIM10217

B­Splines Uniformes Não­Racionais

• Para cada i ≥ 4 existe um ponto comum ou nó entre Qi­1 e Qi no valor do parâmetro ti. Os pontos inicial e final em t3 e tm+1 também são chamados de nós

• O termo uniforme significa que os nós estão espaçados em intervalos iguais do parâmetro t

• Tem continuidade C0, C1 e C2, mas se tem menos controle da curva

DIM10218

B­Splines Uniformes Não­Racionais

MBs

1 3 3 13 6 3 03 0 3 0

1 4 1 0

Funções de base

Matriz de base

Movendo­se um ponto de controlemove­se as quatro curvas que ele afeta na mesma direção

DIM10219

B­Splines Não­Uniformes Não­Racionais

Intervalos dos parâmetros t não necessitam ser iguaisVantagens sobre as uniformes:

Continuidade em pontos de junção selecionados pode ser diminuída de C2  para C1, C0 (interpola ponto de controle sem que se torne uma reta) e nenhumaPontos iniciais e finais podem ser interpolados facilmenteMais controle na sua modificação

DIM10220

B­Splines Não­Uniformes Não­Racionais

Usam a mesma sequência de pontos de controle de P0, ...,Pm, e uma sequência de valores de nós (não­decrescente) t0 a tm+4

Nós podem ter multiplicidade maior que 1, por exemplo (0, 0, 0, 0, 1, 1, 2, 3, 4, 4, 5, 5, 5, 5)

Funções de base são definidas recursivamenteRestringindo­se intervalos de nós como 0 ou 1 pode­se pré­calcular valores das funções de blending (que são positivas e somam 1)

Qi

t Pi 3

Bi 3,4

t Pi 2

Bi 2,4

t Pi 1

Bi 1,4

t Pi

Bi ,4

t

3 i m , ti

t ti 1

DIM10221

B­Splines Não­Uniformes Não­Racionais

Nós múltiplos (efeitos) reduzem continuidadeMultiplicidade 2 – de C2  para C1

Multiplicidade 3 – de C2  para C0

Multiplicidade 4 – de C2  para sem continuidadee interpolação dos pontos de controle

Multiplicidade 2 – ti=ti+1 : nós devem estar na linha      Pi­2­Pi­1

Multiplicidade 3 – ti=ti+1=ti+2 : nós estão no ponto de controle Pi­1

Multiplicidade 4 – ti=ti+1=ti+2 =ti+3 : nós devem estar em Pi­

1 e Pi  ao mesmo tempo, logo uma descontinuidade é introduzida

DIM10222

B­Splines Não­Uniformes Não­Racionais

DIM10223

B­Splines Não­Uniformes Racionais (NURBS)

Segmentos de curvas cúbicas racionais são razões de polinômios: 

Onde X(t), X(t), X(t), X(t), são curvas polinomiais cúbicas com pontos de controle especificados em coordenadas homogêneasSão invariantes a rotação, translação, scaling e transformações perspectivasConseguem representar cônicas precisamente (importante em CAD)

x t X tW t

, y t Y tW t

, z t Z tW t

DIM10224

Outras Splines

Splines de Catmull­Rom (ou Overhauser) interpolam pontos de controle, de modo similar às splines naturaisAs β–splines controlam a forma da curva globalmente através das variáveis β1 (bias) e β2 (tensão)Bias controla influência dos vetores tangentes enquanto que tensão puxa curva para próximo das linhas que conectam os pontos de controle

DIM10225

Subdividindo Curvas

Algoritmo para subdizisão de curvas de Bézier:Encontre os pontos médios (M01, M12, M23) das linhas que ligam os pontos de controle originaisEncontre os pontos médios (M012, M123) das linhas que ligam M01 a M12 e M12 a M23

Encontre o ponto médio da linha que liga M012 a M123

A curva com os pontos de controle P0, M01, M012 e M0123 é a parte da curva original no intervalo t=[0, 0.5]A curva com os pontos de controle M0123 , M123 , M23 and P3 é a parte da curva original no intervalo t=[0.5, 1]

DIM10226

Subdividindo Curvas

P0

P1 P2

P3

M01

M12

M23

M012 M123M0123

P0

P1 P2

P3

DIM10227

Conversões Entre Representações

Conversões são feitas usando­se as matrizes de baseSubdivisão de B­splines uniformes é feita convertendo­se para Bézier e subdividindoNo caso das B­splines não­uniformes, adiciona­se múltiplos nós usando o algoritmo de Böhm ou de Oslo e converte­se para Bézier, e posteriormente para outra forma, se necessário

DIM10228

Desenhando Curvas

O método de diferenças usa a fórmula

Diferenças são computadas até o terceiro nível, onde são constantes, diminuindo­se o número de multiplicações necessárias para avaliar 

f t f t f t , 0     como

f i at3 bt2 ct df t a t 3 b t 2 c t d at 3 bt2 ct d

3 at2 t 3 a 2 2 b a 3 b 2 c

f t

DIM10229

Desenhando Curvas

• Outro método para desenho de curvas é a subdivisão recursiva, onde uma curva é subdividida até que um teste de planaridade seja satisfeito, isto é, a curva pode ser aproximada por uma linha

• Subdivisão de curvas de Bézier é rápida (conversão das outras formas antes da subdivisão)

• Evita computações desnecessárias, mas gasta tempo nos testes de planaridade

• Pode­se usar uma abordagem híbrida, combinado as duas técnicas acima

DIM10230

Superfícies Bicúbicas Paramétricas

• Superfícies bicúbicas paramétricas são generalizações de curvas cúbicas paramétricas 

• Para um valor t1 fixo, Q(s, t1) é uma curva porque G(t1) é constante

• Variando­se o argumento de G tais que as curvas sejam arbitrariamente próximas define­se uma superfície

Q s , t S M G t S M

G1

t

G2

t

G3

t

G4

t

DIM10231

Superfícies Bicúbicas Paramétricas

Como                          usando a identidade        (A • B • C)T=A T • B T • C T  temos que 

e individualmente

G t T M G ,

Q s , t S M G MT T T , 0 s , t 1onde G GT

x s ,t S M GxT M T T T ,

y s , t S M GyT MT T T ,

z s , t S M GzT MT T T , 0 s , t 1

DIM10232

Superfícies de Bézier

• Superfície de Bézier é dada por

    e é definida por 16 pontos de controle (matriz G)

x s ,t S M GxT M T T T ,

y s , t S M GyT MT T T ,

z s , t S M GzT MT T T ,

0 s , t 1

DIM10233

Superfícies de Bézier

Alguns dos pontos de controle interpolam a superfície, e tangentes podem ser controladas explicitamentePropriedade do fecho convexo e fácil subdivisão são herdadas das curvas de BézierContinuidades C0 e G0 entre patches são garantidas escolhendo­se os 4 pontos de controle iguais na bordaContinuidade G1 ocorre quando dois grupos de 4 pontos dos dois lados da borda são colineares com os pontos da borda

DIM10234

Superfícies de Bézier

DIM10235

Superfícies de B­Splines

As equações para superfícies B­splines são obtidas de modo similarEm superfícies B­splines, continuidade C2 é automática, mas deve­se evitar pontos de controle duplicados, que criam discontinuidadesSuperfícies de B­splines bicúbicas não­uniformes e racionais são análogas a suas formas cúbicas

DIM10236

Normais

Normais a uma superfície bicúbica são calculadas através do produto vetorial das derivadas da superfície Q(s,t) em relação a s e t  

sQ s, t

sS M G MT TT

sS M G M T T T

= 3 s2 2 s 1 0 M G M T T T

tQ s , t

sS M G M T T T

sS M G MT T T

= S M G MT 3 t2 2 t 1 0T

DIM10237

Desenhando Superfícies

• Superfícies podem ser desenhadas por avaliação iterativa dos polinômios bicúbicos ou por subdivisão (avaliação adaptativa dos polinômios)

• Avaliação iterativa é ideal para desenho em wireframes

DIM10238

Desenhando Superfícies

Método das diferenças é bem mais vantajoso no desenho de superfícies do que no desenho de curvasSubdivisão de superfícies também é uma extensão do procedimento para desenho de curvas, e é mais simples no caso das curvas de BézierO teste é feito calculando­se um plano que passa por 3 pontos de controle e verificando se os outros 13 pontos estão a uma distância menor que ε do mesmo 

DIM10239

Desenhando Superfícies

Subdivisão geralmente é feita em um dos parâmetros seguida da divisão das duas partes no outro parâmetro, mas pode ser feita somente em um parâmetro se a superfície for plana no outro parâmetroSubdivisão pode gerar buracos no caso de patches adjacentes terem diferentes níveis de subdivisão, e podem ser eliminados por subdivisão até um nível fixo ou escolhendo um ε suficientemente pequeno, mas ambos incorrem em subdivisões desnecessáriasOutra abordagem ajusta quadriláteros vizinhos que tem este problema

DIM10240

Desenhando Superfícies

Crack

DIM10241

Resumo

Curvas cúbicas e superfícies bicúbicas paramétricas por partes são muito usadas em CG porque:

Permitem múltiplos valores para um único valor de x ou yRepresentam inclinações infinitasPossuem controle localPodem aproximar ou interpolar pontos de controleSão computacionalmente eficientesPermitem refinamento por subdivisão e adição de nós, facilitando display e manipulação interativaSão facilmente transformados através da transformação dos pontos de controle

DIM10242

Superfícies Quádraticas

Em aplicações onde somente superfícies quadráticas são utilizadas, como modelagem molecular, pode ser vantajoso utilizar superfícies quádraticas

Vantagens:Cálculo simples da normal da superfícieTeste se um ponto está na superfície da quádricaCálculo de z dados x e yCálculo de interseções de duas superfícies

f x , y , z ax2 by2 cz2 2 dxy 2 eyz 2 fxz 2 gx 2 hy 2 jz k 0