Curvas e Superfícies Paramétricas Prof. João Madeiras Pereira Instituto Superior Técnico ©João Madeiras Pereira & IST 1ª versão: Novembro 2001 2ª versão: Novembro 2002 3ª versão: Outubro 2005 Bibliografia: “Computer Graphics: Principles and Practice”, Foley, van Dam, Feiner and Hughes; Capítulo 11 “3D Computer Graphics”, A. Watt, Capítulo 6 ©João Madeiras Pereira & IST 1.Introdução Modelação Sólida -> Representação de um objecto através da composição de objectos primitivos através de operações booleanas (CSG); Modelação da Fronteira (B-Rep)-> Representação pela descrição paramétrica da sua superfície; ©João Madeiras Pereira & IST Modelação da Fronteira Superfícies Paramétricas: fácil de modelar objectos deformáveis; Malha de Facetas: Menos versátil; ©João Madeiras Pereira & IST Representações Analítica Paramétrica -> Espaço Objecto -> Espaço Paramétrico Espaço Objecto: Coordenadas cartesianas. Espaço Paramétrico: Conjunto dos espaços bidimensionais (x, u) e (y,u) resultantes da decomposição da curva nas suas componentes cartesianas (variáveis dependentes), traduzidas através de um mesmo parâmetro u (variável independente). ©João Madeiras Pereira & IST Representação Analítica Explícita: x = x; y = f(x); Desvantagens: Representação dependente do sistema de coordenadas adoptado Dificuldade de representação de declives infinitos Tratamento computacional complicado Dificuldade de representar curvas fechadas (pelo menos explicitamente) Informação adicional para definir os limites da curva Implícita: Mais flexível Função de teste Não determina pontos ©João Madeiras Pereira & IST f(x, y) = 0; Representação Paramétrica ©João Madeiras Pereira & IST Exemplo Curva polinomial paramétrica: ©João Madeiras Pereira & IST Vantagens Mais níveis de liberdade para controlo da forma da curva (mais parâmetros a concretizar). Exemplo: no caso anterior, uma curva cúbica tem 12 parâmetros As expressões paramétricas suportam declives infinitos, curvas fechadas ou multi-valor. dy/dx = (dy/du) / (dx/du) dy/dx = infinito => dx/du = 0 ©João Madeiras Pereira & IST Vantagens (cont.) Elementos geométricos definidos parametricamente são inerentemente limitados (0 <= u <= 1). As expressões paramétricas são facilmente traduzidas na forma de vectores e matrizes. Utilização de um só modelo matemático para representar qualquer curva ou superfície. ©João Madeiras Pereira & IST Exemplos a) Linha Recta (problema dos declives infinitos) x = a + l*u y = b + m*u z = c + n *u Z The image cannot be displayed. Your computer may not have enough memory to open the image, or ANALITICA: zp u=1 Z = f (x,y) ???? PARAMETRICA: yp The image cannot be displayed. Your computer may not have enough memory to open the image, or the image may have been corrupted. Restart your computer, and then open the file X xp u=0 ©João Madeiras Pereira & IST Y x = xp y = yp z = zpu 0≤u ≤ 1 Exemplos (cont.) Curva Helicoidal ao longo de zz' (funções multi -valor) x = a*cos (Ku) ©João Madeiras Pereira & IST y = a*sin (Ku) z = b*u Curva polinomial paramétrica Polinómio de grau k=2: pouca flexibilidade na definição da forma; Polinómio de grau k> 3: demasiado número de coeficientes e formas com oscilações. ©João Madeiras Pereira & IST Definição de uma curva paramétrica A definição natural de uma curva é feita através da imposição de condições de posição, tangência, curvatura e de um conjunto de pontos denominados pontos de controlo. Interpolação versus aproximação Segmentos de curva e pontos de junção Suavidade (smoothness) – derivadas contínuas nos pontos de junção Controlo local –alteração de um ponto de controlo deve-se reflectir localmente (porção de curva) e não em toda a curva melhor interactividade na definição da curva ©João Madeiras Pereira & IST Curva polinomial cúbica paramétrica ©João Madeiras Pereira & IST Curva polinomial cúbica paramétrica (cont.) ©João Madeiras Pereira & IST Uma Curva polinomial cúbica paramétrica • Caso particular (pouco utilizado): curva interpola 4 pontos de controlo, p0, p1, p2, e p3. Considere-se o intervalo de u igualmente espaçado: u = 0, 1/3, 2/3, 1 ©João Madeiras Pereira & IST Uma Curva polinomial cúbica paramétrica (cont.) ©João Madeiras Pereira & IST Funções de Mistura • M – Matriz base: transforma os constrangimentos geométricos (condições fronteira) nos coeficientes polinomiais e caracteriza a curva. • p(u) = uT c = uT M p • p(u) = b(u) p com b(u) = uT M • b(u) matriz com as funções de mistura polinomiais ©João Madeiras Pereira & IST Funções de Mistura (cont.) No caso em estudo: ©João Madeiras Pereira & IST Funções de Mistura (cont.) • Problemas: • Os zeros das funções de mistura situam-se no intervalo [0, 1] logo pouco suave e propensa a oscilações (mais grave em polinómios de maior grau) • Não tem continuidade de derivada nas junções • Conclusão: curva pouco utilizada em CG ©João Madeiras Pereira & IST Superfícies Paramétricas • Retalho (patch) é um troço de superfície com u e v definido no domínio (0,1). • Manta de retalhos são usadas para modelar as fronteiras de objectos 3D complexos: ©João Madeiras Pereira & IST Tipos de Curvas Com diferentes Funções de Mistura e diferentes Coeficientes Geométricos constroem-se curvas do tipo: HERMITE: Definidas pela posição e vectores tangentes dos pontos extremos; BEZIER: Definidas pela posição dos pontos extremos e utilizando dois pontos adicionais para definir indirectamente as tangentes à curva nas suas extremidades; B-SPLINE: Constrói uma curva aproximada aos pontos extremos mas sem passar por eles. Este grau de liberdade permite a obtenção de continuidade à primeira e segunda derivadas nos pontos de junção entre segmentos de curva. ©João Madeiras Pereira & IST Curva Hermite Coeficientes Geométricos: p(0), p(1), pu(0), pu(1): Funções de Mistura: F1(u) = (2u3 - 3u2 + 1) F2(u) = (-2u3 + 3u2) F3(u) = (u3 - 2u2 + u) F4(u) = (u3 - u2) p(u) = ©João Madeiras Pereira & IST F1.p(0) + F2.p(1) + F3.p´(0) + F4.p´(1) Curva Hermite: definição p(u) = uT c = uT MH p ©João Madeiras Pereira & IST Funções Mistura Hermite 1 1 F1 0 F2 1 0 1 0,2 F3 F4 1 0 1 0 -0,2 ©João Madeiras Pereira & IST Curva Bézier: Critérios As funções devem interpolar a curva nos pontos inicial e final do polígono de controlo (controlo directo dos extremos da curva) Os vectores tangentes nos extremos devem ser dados respectivamente por (p1 – p0) e (pn - p(n-1)). (controlo directo dos declives da curva nos pontos extremos). Deve ser possível a generalização da propriedade anterior às derivadas de grau superior. A segunda derivada em po depende de (p0,p1,p2) e assim sucessivamente. (permite o controlo "ilimitado" de continuidade nas junções entre troços de curva). As funções devem ter um comportamento simétrico com respeito a (u) e (1 - u). Esta propriedade faz com que seja possível inverter a ordem dos vértices do polígono de controlo sem que haja alteração da forma da curva aproximada. ©João Madeiras Pereira & IST Curva Bézier cúbica: definição ©João Madeiras Pereira & IST Funções de Mistura (Bezier cúbica) Grau da curva depende do número de Pontos de Controlo: (n+1) pontos de controlo -> Bi,n(u) = polinómios de grau n Exemplo de curvas de Bézier cúbica 1 (grau n=3) B3,3 B0,3 Funções de Mistura: B2,3 B1,3 0 ©João Madeiras Pereira & IST u 1 Curvas de Bézier de grau n • Curvas aproximadas • Curva Bezier de grau n pi: Coeficientes geométricos ou pontos de controlo {p0, p1, p2, ..., pn} ou polígono característico Funções de Mistura: polinómios de Bernstein ©João Madeiras Pereira & IST Invariantes a) Para u = 0: B0,n (u) é sempre igual `a unidade. Bi,n (u) é sempre nula quando i <> 0. Confirma-se que o primeiro ponto de controlo determina o primeiro extremo da curva. b) Para u = 1 Bn,n (u) é sempre unitária Bi,n (u) é sempre nula quando i <> n. Confirma-se que o ultimo ponto de controlo determina o segundo extremo da curva. c) Cada ponto pi tem a sua máxima influência para a definição da curva (máximos das funções de mistura) quando: u = i/n ©João Madeiras Pereira & IST Continuidade C1 e G1 • Construção de uma curva mais complicada (vários pts. de controlo) à custa de várias secções Bézier. • Seja pn-1 e pn de uma secção e q0 e q1 da próxima secção. Para obter G1: Os pts q0 e q1 têm de ser colineares com pn-1 e pn (e claro que pn = q0) q1 = pn + K (pn – pn-1) ©João Madeiras Pereira & IST Continuidade C1 e G1 (cont.) ©João Madeiras Pereira & IST Curvas Fechadas 1) Curvas fechadas com continuidade de posição (curvas G0). p0 = pn 2) Com continuidade de posição e declive (curvas C1). ( p1 - p0 ) colinear com ( pn - pn-1) ©João Madeiras Pereira & IST Propriedades • Os extremos coincidem com os vértices extremos do polígono de controlo • Os declives nos extremos, são dados directamente pelos lados extremos do polígono de controlo • Uma curva Bézier está sempre contida no polígono convexo definido pelos seus pontos de controlo. • Se não forem utilizados polinómios de grau muito elevado, a curva segue razoavelmente o andamento do polígono de controlo, sem oscilações indesejadas. • A definição da curva é feita por mera enumeração dos pontos de controlo, não exigindo a introdução de declives (interface simples). ©João Madeiras Pereira & IST Desvantagens • O grau do polinómio depende do número de pontos de controlo e para graus muito elevados surgem oscilações. • Não é possível o controlo local (a movimentação de um ponto de controlo provoca o recalcular de toda a curva, pois a correspondente função de mistura é não-nula no intervalo ]0, 1[). ©João Madeiras Pereira & IST B-Splines • Curva aproximada • Quaisquer número de pts de controlo: (m+1) • O grau da curva não é determinado pelos número de pts de controlo mas sim por K (ordem da curva): grau da curva = K –1 (curva cúbica implica K = 4) • A curva B-spline é uma série de segmentos de curva Qi (u) (no contexto da curva o parâmetro u é global; no contexto de um segmento u é local) • Cada Qi é determinado (ou definido) por K pts de controlo • Constrangimento C2 ou G2 nos pts de ligação dos Qi ©João Madeiras Pereira & IST Segmento de Curva Para uma curva cúbica, um segmento de curva é dado por: i é o número do segmento Representa apenas o segmento Qi u varia no intervalo [0, 1] – parâmetro local ©João Madeiras Pereira & IST Funções de Base num Segmento de Curva (local) No contexto das B-splines, a função de mistura da curva Bézier assume normalmente a designação de função de base ©João Madeiras Pereira & IST Número de segmentos de curva • Considere-se uma curva B-Spline com m+1 pts de controlo e ordem K: o número de segmentos de curva Qi é dado por: Por convenção: • Curva cúbica B-Spline: Cada Qi determinado por 4 pts de cntrl – propriedade de controlo local: alterar 1 pt de cntrl influencia apenas 4 segmentos de curva m – 2 segmentos de curva que convencionalmente se designarão por: ©João Madeiras Pereira & IST Número de Segmentos de Curva (cont.) Exemplo: curva cúbica com 6 pts de cntrl (m=5 e K=4) Temos 3 Qi e: ©João Madeiras Pereira & IST Exemplo ©João Madeiras Pereira & IST Controlo Local Altera-se P4: “puxa” Q5 e afecta, em menor extensão Q4. Q3 não se altera! ©João Madeiras Pereira & IST Segmentos de Curva e nós de ligação • No espaço paramétrico global temos nós ou knots que representam os valores de u onde os segmentos Qi têm os seus extremos. Também são designados por nós de ligação uma vez que são os valores de u onde os seg. de curva se unem • Por definição um Qi é definido entre 2 nós consecutivos: Qi define um intervalo paramétrico ui ≤ u ≤ ui+1 (espaço de u global) • B-Spline uniforme: assume-se que esses nós têm valores inteiros e que o espaçamento entre nós é igual a 1 (0, 1, 2,...) ©João Madeiras Pereira & IST Função de Base da B-Spline Cúbica • Cada função de base “cobre” K intervalos • Curva B-Spline ordem 4: cada função de base é, ela própria, uma B-Spline cúbica, constituída por 4 segmentos, e simétrica ©João Madeiras Pereira & IST Funções de Base de uma B-Spline Cúbica Uniforme Exemplo: curva cúbica com 6 pts de cntrl (m=5 e K=4) Nós uniformemente espaçados (vector de nós uniforme): cada função de base é uma cópia transladada de um nó (funções de base periódicas). Número total de nós: 10 Uma curva B-Spline é calculada por: ©João Madeiras Pereira & IST Número de Knots • Cada função de mistura Bi é suportada no intervalo ui - > ui+K • Temos m+1 funções de mistura; • Logo: m + 1 + k knots (u0 -> um+k) Número de nós: nº de pts de cntrl + ordem da curva ©João Madeiras Pereira & IST Intervalo do parâmetro u global Mas só interessa para a definição da curva o espaço paramétrico [3, 6] ©João Madeiras Pereira & IST Intervalo do parâmetro u global • O parâmetro u global, no contexto da curva B-Spline Q(u), deve variar entre: • Então uma B-Spline é definida por • No caso de uma B-Spline cúbica uniforme o valor mínimo de u é sempre 3 (ou u3 no caso de uma não-uniforme) ©João Madeiras Pereira & IST Cáculo do Segmento de Curva da B-Spline cúbica • Em uK-1 ≤ u ≤ um+1, verifica-se que para valores de u que não são nós, estão sempre activas K funções de base e somam a unidade. Nos nós, só existem K-1 funções não-nulas e que somam a unidade. Quando se atinge um nó ui, uma função de base anula-se e “nasce” outra. • Mas Q(u) também pode ser o somatório dos vários Qi • Qi define um intervalo paramétrico ui ≤ u ≤ ui+1 • Qi é determinado pelas funções de base Bi-3, Bi-2, Bi-1 e Bi ©João Madeiras Pereira & IST Cáculo do Segmento de Curva da B-Spline cúbica (cont.) Calcula um simples segmento de curva a partir das 4 funções de base no intervalo 0≤ u ≤ 1 (local). O cálculo de Q3 (3≤ u ≤ 4) implicaria o cálculo das funções acima, substituindo u por (u-3). No exemplo anterior (6 nós, m=5) ter-se-ia: Q(u) = Q3 + Q4 + Q5 ©João Madeiras Pereira & IST Curva B-Spline Numa B-Spline uniforme: ©João Madeiras Pereira & IST Cálculo da função de base B-Spline cúbica uniforme Esta definição calcula um simples segmento de curva a partir das 4 funções de base no intervalo 0≤ u ≤ 1 (local). Não define a função de base cúbica B0, a qual consiste de 4 segmentos no intervalo 0≤ u ≤ 4. ©João Madeiras Pereira & IST Cálculo da função de base B-Spline cúbica uniforme (cont.) Usando as equações do acetato anterior, e transladando cada segmento cúbico de 0, 1, 2 e 3 em u, obtém-se: Se se usar a fórmula recursiva Cox-deBoor para a derivação das funções de mistura, as quais geram curvas B-Splines uniformes ou não-uniformes de grau K, o resultado é exactamente o mesmo. ©João Madeiras Pereira & IST Fórmula Recursiva Cox-deBoor Método alternativo para o cálculo das funções de mistura de curvas B-Spline, grau K, uniformes ou não-uniformes: ©João Madeiras Pereira & IST Múltiplos Pontos de Controlo Três P5 coincidentes: 8 pts de controlo, 6 Qi, 3≤ u ≤ 8 Q7 (7 ≤ u ≤ 8) determinado por P4P5P5P5. Em u=8 interpola P5 ©João Madeiras Pereira & IST Múltiplos Pontos de Controlo Interiores Perda de continuidade a) ponto duplo -G1 b) Ponto triplo - G0 ©João Madeiras Pereira & IST Múltiplos Pontos de Controlo Interiores (cont.) ©João Madeiras Pereira & IST B-Splines não-uniformes Vantagens: Se a continuidade é reduzida para C0, então a curva interpola um pt de controlo, mas sem aquele inconveniente de ter seg. recta em ambos os lados do pt de controlo interpolado Pts extremos interpolados mas sem introduzir segmentos lineares ©João Madeiras Pereira & IST Vector de Knots Não Uniforme Define-se que os knots dos extremos da curva têm multiplicidade k. Para k=4 (grau 3) temos o vector de knots: T=(0, 0, 0, 0, 1, ...., n-1, n, n, n,n) Quando 2 knots são idênticos a curva reduz-se a um ponto. ©João Madeiras Pereira & IST B-Splines não-uniformes Vector de knots: [0, 0, 0, 0, 1, 2, 3, 3, 3, 3]; 6 pts ctrl; 3 seg. curva 9 segmentos, Q0 a Q8. Mas a curva reduz-se a Q3, Q4 e Q5 em que 0 ≤ u ≤ 3 (u3 ≤ u ≤ u6) . Nos extremos, todas as funções de base são nulas, excepto B0 e B5, ambas unitárias, o que faz com que a curva interpole P0 e P5 ©João Madeiras Pereira & IST B-Splines não-uniformes 9 pts de cntl; 13 nós ©João Madeiras Pereira & IST Efeito da multiplicidade numa função de base B -Spline a) Multiplicidade 1: [0, 1, 2, 3, 4] b) Multiplicidade 2: [0, 1, 1, 2, 3] c) Multiplicidade 3: [0, 1, 1, 1, 2] d) Multiplicidade 4: [0, 1, 1, 1, 1] ©João Madeiras Pereira & IST Transformar B-Spline em Bézier • Curva cúbica com 4 pts de cntrl • Interpola os extremos • Logo: vector knots = [0, 0, 0,0, 1, 1, 1, 1] • Curva com apenas um segmento de curva Q, que interpola os pts de cntrl extremos e cujas funções de base são as funções de mistura da curva cúbica de Bézier ©João Madeiras Pereira & IST Transformar B-Spline em Bézier ©João Madeiras Pereira & IST Propriedades • Novos knots podem ser inseridos no troço que necessita de refinamento; • Aumentar a multiplicidade m de um knot reduz a continuidade da paramétrica k-m-1; • Um knot interior de multiplicidade k transforma uma B-spline em duas B-Splines distintas cada um com o seu conjunto de pontos de controlo. ©João Madeiras Pereira & IST Multiplicidade em pontos interiores (1) ©João Madeiras Pereira & IST Multiplicidade em pontos interiores (2) ©João Madeiras Pereira & IST Multiplicidade em pontos interiores (3) ©João Madeiras Pereira & IST Multiplicidade em pontos interiores (4) ©João Madeiras Pereira & IST NURBS A curva Rational cúbica é dada pelas seguintes razões: Onde X(u), Y(u), Z(u) e W(u) são curvas cúbicas polinomiais cujos pts. de ctrl são definidos em coordenadas homogéneas. Curva no espaço homogéneo: Q(u) = [X(u) Y(u) Z(u) W(u)] Para passar para o espaço cartesiano divide-se por W(u) ©João Madeiras Pereira & IST NURBS • 2 vantagens: • Invariantes após a aplicação de transformações geométricas simples e a transformação perspectiva (as não racionais “alteram” com a transformação perspectiva). Isto significa que a transformação perspectiva é aplicada apenas aos pts de controlo, os quais podem ser usados para gerar a curva que representa a transf. Perspectiva da curva original. • Definir com precisão secções cónicas (polinómios quadráticos) ©João Madeiras Pereira & IST Superfícies Paramétricas • Definir pontos na superfície em termos de dois parâmetros (u, v) • Caso mais simples: interpolação bilinear s x(s,1) P0,1 P1,1 x(s,t) t P0,0 s ©João Madeiras Pereira & IST x(s,0) P1,0 Bezier Patches • As with Bezier curves, Bin(u) and Bjm(v) are the Bernstein polynomials of degree n and m respectively – Need 4x4=16 control points, Pi,j • Most frequently, use n=m=3: cubic Bezier patch ©João Madeiras Pereira & IST Evaluators em OpenGL void glMap2f(GLenum target, GLdouble u1, GLdouble u2, GLint ustride, GLint uorder, GLdouble v1, GLdouble v2, GLint vstride, GLint vorder, const GLfloat *points) Target: GL_MAP2_VERTEX_3, GL_MAP2_VERTEX_4 ustride: Especifica o número de floats ou de doubles entre o ínicio da posição do ponto de controlo Pij e o ínicio da posição do ponto de controlo P(i+1)j no array de pts introduzidos pelo utilizador. vstride: Especifica o número de floats ou de doubles entre o ínicio da posição do ponto de controlo Pij e o ínicio da posição do ponto de controlo Pi(j+1) no array de pts introduzidos pelo utilizador. i e j representam os índices de u e v dos pts de controlo: indice i corresponde à função Bi(u) e o índice j corresponde à função de base Bj(v).Este esquema de endereçamento permite que seja especificado um array de pts cujo número seja bastante superior ao número de pts de controlo necessários para definir a superfície, ou seja contém potenciais pontos de controlos. Utilizando um ponteiro e os dois strides, o utilizador pode especificar um sub-array rectangular de mxn pts de controlo. A única restrição é que os potenciais pts de controlo estejam em posições adjacentes na memória. EXEMPLO: GLfloat array[100][100][3]; array de potenciais pts de controlo Utilizar para uma superfície cúbica de Bézier um array de pts de controlo a começar pelo pt na posição (20,30) do aray. Se é cúbica, isto significaria que a API utilizaria um array de 4 x 4 pontos. Assim, indicar-se-ia: glMap2f(GL_MAP2_VERTEX_3, 0, 1, 100*3, 4, 0, 1, 3, 4, &array[20][30][0]) ©João Madeiras Pereira & IST NURBS em OpenGL • Ver exemplo do livro: surface.c • Tal como uma Textura uma Nurbs é um objecto que pode ser criado (gluNewNurbsRenderer), destruído (gluDeleteNurbsRenderer) e especificado (gluNurbsCurve, gluNurbsSurface). • Podem ainda ser criada uma parte de uma paramétrica (gluBeginTrim, gluPwlCurve, gluNurbsCurve, gluEndTrim). ©João Madeiras Pereira & IST Especificação de Curva Tem que se definir: – Nº de knots (= nº de pontos de controlo + ordem da curva) – Array de knots (com valores crescentes ou não: curva uniforme ou não-uniforme) – Apontador para array de pontos de controlo; – Número de floats a percorrer no array de pontos de controlo de modo de modo a aceder ao ponto de controlo seguinte – Ordem da curva (= ordem do polinómio + 1); – Tipo de avaliação da curva (por exemplo, GL_MAP1_VERTEX_3 or GL_MAP1_COLOR_4). ©João Madeiras Pereira & IST Parâmetros Pode controlar-se: • A tolerância de amostragem, em quadrículas; • O modo de desenho (fill, fronteira do retalho, fronteira do polígono); • Modo de amostragem (comprimento em quadrículas, distância da superfície ao polígono, comprimento em coordenadas u, v); • No 3º modo, de amostragem, tem que se fornecer o passo em u e o passo em v. ©João Madeiras Pereira & IST GLU_FILL ©João Madeiras Pereira & IST GLU_OUTLINE_POLYGON ©João Madeiras Pereira & IST