Loading
Nota de Estudos
Study Reminders
Support
Text Version

Introdução a Splines

Set your study reminders

We will email you at these times to remind you to study.
  • Monday

    -

    7am

    +

    Tuesday

    -

    7am

    +

    Wednesday

    -

    7am

    +

    Thursday

    -

    7am

    +

    Friday

    -

    7am

    +

    Saturday

    -

    7am

    +

    Sunday

    -

    7am

    +

Olá e bem-vindo a palestra número 7 no curso Computer Graphics.
Como já falamos nas técnicas de representação de objeto há amplamente 5 categorias, uma é a renderização de amostra de pontos. A segunda é a representação de limite, então particionamento espacial, então representação de varredura e, finalmente, algumas outras técnicas de representação específicas que são aplicáveis-específicas ou encaminadas para algumas técnicas avançadas, tais como gráficos de cena, modelo esquelético e outras técnicas avançadas de modelagem, como representação fractal e sistemas de partículas.
Na representação de limite, lá 3 amplos grupos de técnicas. Uma é a representação mesh, uma é a representação paramétrica, e uma é representação implícita. Da mesma forma, na representação de particionamento espacial, há 3 técnicas amplas de representação baseada em ocárvore BSP ou árvores de particionamento de espaço binário e técnicas de CSG. Agora, entre todos estes, estamos atualmente discutindo as técnicas de representação limite e continuaremos nossa discussão sobre essa técnica.
Nas técnicas de representação de limites. Na última palestra, o último par de palestras, cobrimos a representação de mesh e introduzimos a ideia de representação paramétrica, bem como representação implícita. Hoje continuaremos nossa discussão sobre a representação de limite hoje nos concentraremos em uma técnica de representação de limite específica e popular, que é chamada de representação spline.
Por isso, para entender a técnica de representação spline, precisamos entender como representamos a curva. A curva é muito comum, uma forma primitiva que é necessária em muitos lugares para representar objetos, principalmente no contexto de formas complexas não podemos evitar representar curvas apenas com linhas ou pontos, pode não ser possível representar formas complexas, e temos que levar em conta curvas.
Para simplificar a nossa discussão incidirá aqui apenas sobre a representação paramétrica das curvas, embora antes tenhamos introduzido tanto os tipos, nomeadamente a representação paramétrica e a representação implícita. Como podemos representar curvas, em geral, usando a forma paramétrica, podemos usar um único parâmetro u será indicado por u para representar curvas ou suas coordenadas cartesianas usando essas equações. Esta aqui é por representar a coordenada X. O outro é por representar a coordenada Y onde X é uma função de u e Y é outra função de u. Vamos tentar entender a intuição por trás dessa representação. Podemos supor que u está denotando tempo. Podemos pensar nisso desta forma, estamos desenhando a curva em um espaço 2D Cartesiano ao longo de um período de tempo agora em um instante de tempo, colocamo-nos um ponto cartesiano. Depois, podemos dizer que nesse ponto do tempo o ponto cartesiano é que, em outras palavras, o ponto cartesiano é caracterizado pelo instante do tempo, que é u. Então, essencialmente u denota instante específico do tempo, em que ponto podemos determinar os valores de coordenadas correspondentes usando a equação. Esta é a intuição simples por trás da ideia da representação paramétrica de uma curva.
Então, isso é sobre entender como a representação curva parametralmente. Agora, nosso objetivo é representar a curva com facilidade e eficiência. Vamos elaborar sobre isso um pouco mais.
Como todos sabemos, podemos aproximar uma curva em termos de um conjunto de segmentos de linha pequena, é claro que aqui os segmentos têm de ser muito pequenos para fazer a curva parecer lisa, caso contrário, a curva faz com que ele seja uma aparência jagada. Agora, claramente, isso é muito fácil, intuitivo mas pode não ser eficiente. Podemos ter que fornecer um grande número de pontos para traçar pequenas linhas julgadas.
Pode haver outra alternativa. Podemos trabalhar a equação da curva e aplicar a equação para descobrir qualquer ponto da curva. Então, isso claramente é melhor do que especificar um número manualmente grande de pontos para aproximar a curva na forma de um conjunto de segmentos de linha. Então, claramente, isso é fácil e pode se transformar em eficiente também. Mas o problema aqui é que para muitas curvas podemos não ser capazes de encontrar a equação em si. É muito difícil para qualquer curva arbitrariamente definida para descobrir a questão da curva. Por isso, vamos tentar entender esses problemas a partir desse ponto de vista de um usuário, o que o usuário pensa.
E quais são os problemas que o usuário enfrenta? Agora o usuário quer gerar uma curva de qualquer forma arbitrária. Se estamos tentando representar a curva em forma de um grande número de segmentos de linha pequena, então o usuário tem que inserir um número muito grande desses pontos através dos quais os segmentos de linha podem ser gerados. Claramente, nenhum usuário estaria interessado em inserir um número muito grande de tais pontos. Por outro lado, para um usuário. Pode ser difícil ou até mesmo impossível descobrir uma equação precisa da curva. Assim, portanto, em ambos o usuário de abordagens não vai ser beneficiado.
Idealmente, o que um usuário deve fazer ou o que um usuário deseja fazer, o usuário quer fornecer um conjunto limitado de pontos. Agora, esses pontos definem a curva. Assim, essencialmente, o usuário não está fornecendo todos os segmentos de linha possíveis para aproximar a curva ou fornecer uma equação precisa para descobrir pontos na curva. Em vez disso, o usuário está fornecendo um conjunto pequeno ou limitado de pontos que define a curva. Em outras palavras, esses pontos um escolhido tal que a curva passa por ou próximo desses pontos, esses pontos também são conhecidos como pontos de controle.
Então, a alternativa para o usuário é fornecer um pequeno conjunto de pontos de controle em vez de fornecer um grande conjunto de pontos através dos quais os segmentos de linha podem ser desenhados ou dar uma equação de curva precisa. Então, o usuário forneceu um conjunto de pontos de controle. E o usuário espera que o sistema desenhe a curva pela interpolação, interpolando esses pontos de controle. Por isso, vamos tentar entender brevemente qual é a ideia de interpolação, muitos de vocês ou talvez todos vocês já possam saber o que é interpolação, mas não há mal algum em refrescar nosso conhecimento.
Portanto, essencialmente, quando falamos de interpolação, o que queremos dizer, significamos essencialmente por ajuste de interpolação de uma curva que passa ou nas proximidades do conjunto de pontos fornecidos ou dos pontos de controle. Uma forma de interpolação é uma interpolação polinomial. Nessa interpolação o que fazemos, tentamos encaixar uma curva polinomial através do determinado conjunto de pontos de controle. Ora, a interpolação polinomial é muito popular porque geralmente se considera que tais interpolações são simples, eficientes e fáceis de manipular. Então, nós vamos focar aqui na interpolação polinomial. Agora, dependendo do número de pontos de controle, decide-se o grau de polinomial interpolante. Assim, quando falamos de interpolação polinomial, uma preocupação é o que deve ser o grau de polinomial agora que pode ser decidido com base no número de pontos de controle fornecidos.
Tomemos um exemplo, suponhamos que nos sejam dados 2 pontos de controle em tal situação, é aconselhável ir para interpolação linear em vez de qualquer outra forma superior de interpolação porque temos apenas dois pontos de controle. Da mesma forma, se houver 3 pontos de controle, então podemos ir para polinômios quadráticos. Existem 4 pontos de controle que utilizam o grau em conformidade e assim por diante. Portanto, podemos dizer que em geral para n + 1 pontos de controle, podemos tentar encaixar polinomial de grau n que é pictorialmente retratado aqui nesta figura, somos dados esses pontos de controle através dos quais estamos tentando encaixar uma curva. E se o número de pontos de controle for n + 1, então a curva com a qual devemos trabalhar ou o polinomial que devemos trabalhar deveria ter grau n idealmente. Nota no sistema de equações que mencionamos aqui. Esta é para coordenada X, similarmente para coordenada Y, podemos ter um conjunto semelhante de sistemas. Agora já que eles são n pontos de controle dado temos n x valores de coordenadas para cada uma dessas coordenadas. Nós temos 1 equação da curva em termos do parâmetro e assim para o n número de pontos de controle, temos n número de equações.
Agora, naquelas são equações existem termos constantes, esses são os coeficientes como um 0, a1 a an-1.
Se decidirmos essas coordenadas, então podemos definir a polinomial. Então, para obter os valores dessa coordenada esses coeficientes o que precisamos fazer, precisamos resolver o conjunto de equações. A n mais uma equação que já vimos anteriormente. Se resolvemos isso, então obteremos esses valores dos coeficientes que define a polinomial.
Mas há um problema, se nós temos um n muito grande se temos muitos pontos de controle, um grande número de n. Depois, é preciso resolver um número muito grande de equações, o que não é fácil. Em cima dele, precisamos ter em mente que existem dois conjuntos separados de equações, um para X e outro para Y. Então, precisamos resolver de fato dois conjuntos de equações em vez de um e para grandes e, isso se torna muito incômodo para fazer.
Junto com isso, há mais um problema, que é chamado de questão de controlabilidade local. Suponhamos que você ou o usuário deseje alterar a forma um pouco. Assim, com a equação polinomial obterá uma curva que representa uma forma.
Agora, eu quero mudar um pouco. Então, idealmente, o que devo fazer? Uma mudança de um ou de alguns pontos de controle para denotar a pequena mudança. Mas, se nós vamos para a interpolação polinomial, então para obter a nova curva, podemos ter que recalcular a coisa toda novamente. Então, a curva inteira pode ter que ser recalculada. O que é, obviamente, não uma coisa boa porque mudamos alguns pontos e idealmente devemos ser capazes de restringir nosso esforço de pré-cálculos a esses poucos pontos apenas, mas em vez disso temos que resolver todo o conjunto de equações novamente, o que não é uma abordagem eficiente.
Então, esse problema é conhecido como controlabilidade local, onde somos incapazes de controlar as mudanças locais localmente. Temos que controlar as mudanças locais através de recálculo global da curva. Agora, para abordar estas questões, há outra solução que vamos discutir.
Agora, qual é essa abordagem alternativa? Suponhamos que nos sejam dados novamente n mais um pontos de controle independentemente do valor de n, podemos particionar o conjunto inteiro em subconjuntos com menos pontos.
Tipicamente, esses menos pontos em 3. Por isso, dado um conjunto de n mais um ponto, podemos gostar de ter subconjuntos onde cada subconjunto contém três pontos de controle. Agora para cada um desses subconjuntos, podemos encaixar polinômios de grau inferior. Neste caso, o grau 2 polinômios para cada um dos subconjuntos.
E então esses polinômios individuais de menor grau, que também são chamados de peças polinomiais, quando se unem, dão a curvação geral. Então, a ideia é muito simples. Você recebe um grande número de pontos de controle, mas não é necessário se encaixar em uma única curva polinomial usando todo o conjunto de pontos de controle. Em vez disso, o que fazemos, dividimos o conjunto de pontos de controle inteiro em subconjuntos de números menores. Cada subconjunto contém muito poucos pontos de controle.
Um valor típico usado são três e para cada um desses subconjuntos, nós encaixamos ou interpolamos um polinomial de grau menor. E esses polinômios, quando se unem, dão a curvação geral. Então, esses polinômios individuais também são conhecidos como peças polinomiais. Então, toda a curva que estamos representando em termos de peças polinomiais. Vejamos um exemplo, considere esta figura aqui. Existem 5 pontos de controle p0 a p4 como você pode ver, p0, p1, p2, p4 p3 e p4. Agora, esses 5 pontos precisam não ser usados para traçar um único polinômio.
Que neste caso seria de grau 4 em vez disso o que podemos fazer, podemos subdividir as curvas ou o conjunto de pontos de controle em subconjuntos. Assim como os dois subconjuntos mostrados aqui em um subconjunto, temos três pontos de controle p0, p1, p2 outro subconjunto temos outros 3 pontos de controle p2, p3, p4.
Para cada um desses subconjuntos, traçamos um polinomial quadrático ou grau 2 e então quando eles se unem, obtemos a curva geral interpolada. Essa é a ideia básica.
Agora, essa ideia de encaixar um conjunto de pontos de controle com vários polinômios de grau inferior do que um único polinômio de grau superior é conhecida como representação spline. Assim, quando falamos de representação spline, estamos essencialmente nos referindo ao fato de que há um conjunto de pontos de controle, mas não estamos interpolando todo o conjunto com uma única curva polinomial. Em vez disso, estamos a representá-lo em termos de várias peças polinomiais. Agora a carva inteira é chamada de curva de espinha simplesmente spline.
Esta é uma técnica de representação de curva muito popular usada em computação gráfica.
Em gráficos, é muito comum o uso de splines feitos de terceiro grau ou n = 3 polinômios, também conhecidos como polinômios cúbicos. Em nossa discussão subsequente, nos concentramos. Vamos nos concentrar nestes polinômios apenas e nas splines correspondentes apenas. Há uma coisa importante na representação spline que temos que ter em mente que é chamada de condição de continuidade. Agora splines, como já discutimos, refere-se à junção de vários polinômios. Por isso, claramente, é importante garantir que eles se articulem tranquilamente. Para fazer a curva resultante parecer suave.
Agora, como garantir isso? Para garantir que isso aconteça, as splines devem estar em conformidade com o que é conhecido como condição de continuidade. Existem várias tais condições de forma ampla, elas são de dois tipos, uma é condição de continuidade paramétrica e a outra é condições geométricas de continuidade. Assim, em geral, a nsima ordem de continuidade paramétrica de ordem denotada por Cn afirma que as curvas adjacentes atendem e primeiro à nsima ordem derivativos paramétricos das funções de curva adjacentes são iguais em seu limite comum que é a definição geral. Agora, vejamos o que eles se referem em termos simples.
Assim, a primeira condição de continuidade paramétrica é o C0, a condição de ordem zerada, que simplesmente afirma que a curva adjacentes se encontra. É só que a condição simples.
Agora, a condição paramétrica de primeira ordem C1 indica que os derivados de primeira ordem de curvas de adjunta em limite comum são iguais. Então, essencialmente ele conta que, no limite comum, temos que garantir que a primeira encomenda paramétrica derivada. Isso significa que a derivada com relação ao parâmetro u da curva deve ser igual. De forma semelhante C2 indica que tanto o primeiro quanto os derivados de segunda ordem são iguais no limite comum. E, desta forma, podemos continuar. Mas já que em gráficos nos concentramos principalmente em polinômios de terceiro grau, portanto, estamos principalmente preocupados com essas condições de continuidade até C2. Agora, essas condições de continuidade paramétrica são suficientes, mas não necessárias para garantir alisamento geométrico da esplina. Para isso, o que precisamos é nos conformar com o outro conjunto de condições de continuidade chamadas condições geométricas de continuidade. Agora, o que são esses? A condição de ordem de 0 é denotada por G0. Esta é a condição de ordem zerada que é semelhante a C0, que simplesmente afirma que as curvas devem atender. Da mesma forma, G1 ou a condição de continuidade geométrica de primeira ordem diz que as direções tangente no limite comum devem ser iguais, embora sejam magnitudes podem ser diferentes para que as direções devem ser iguais mas as magnitudes podem variar no limite que é a condição de continuidade geométrica G1 ou de primeira ordem.
A condição de segunda ordem ou G2 indica que ambas as direções tangente e curvaturas no limite comum das curvas adjunta devem ser iguais. Novamente, podemos continuar assim até qualquer ordem, mas já que estamos principalmente preocupados com polinômios cúbicos, até G2 deve ser suficiente para o nosso entendimento. Então, esse é um conhecimento básico que devemos ter sobre splines que é, se quisermos representar qualquer curva como splines, isso significa em termos de peças polinomiais menores, devemos garantir que as curvas se adequam às condições de continuidade, às condições de continuidade paramétrica e geométrica.
Agora, vamos tentar ver quais são os diferentes tipos de representações de Spline que podemos usar. Há, de forma geral, dois tipos. Uma está interpolando splines. Outra é a aproximação splines.
Agora, em caso de splines interpolantes, o que queremos? Nós essencialmente tentamos encaixar a curva tal que ela passa por todos os pontos de controle. Assim, essencialmente nos é dado um conjunto de pontos de controle e estamos representando a curva em forma de splines, de uma forma tal que as peças polinomiais da spline passam por todos os pontos de controle conforme mostrado nesta figura.
Agora, as splines interpolantes comumente usadas em computação gráfica são splines cúbicas naturais, splines cúbicas hermitas e splines cúbicas cardinais. Então, nós vamos discutir sobre essas splines em detalhes depois.
O outro tipo de curvas Spline são chamadas de splines aproximadas aqui. Pontos de controle são usados para definir um casco de limite ou convexo, a própria spline não passa por todos os pontos de controle.
Em vez disso, restringe-se dentro do limite definido pelos pontos de controle. Veja o mesmo exemplo aqui temos 4 pontos de controle. Mas aqui, a curva não está passando pelos 4 pontos de controle, diferentemente do que ocorre anteriormente em caso de splines interpolantes, o que está acontecendo aqui é que esses pontos de controle estão definindo uma região de ligação, um limite que é popularmente chamado de casco convexo, e a esplina fica dentro deste limite.
Em outras palavras, a forma Spline é determinada pela convecção. Agora, há algumas splines comuns e populares aproximado de splines usadas em aplicações, a saber, as curvas de bezier Cubic e as splines Cubic B, novamente discutirão sobre aqueles posteriores. Então, essa é a ideia básica de spline.
O que é e o que os torna bons por representar qualquer curva.
Então, o que é ele é essencialmente representando uma forma complexa em termos de polinômios menores, gerenciáveis, de grau inferior ou de polinomiais. E é capaz de representar tranquilamente as Curvas porque as splines devem se adequar às condições de continuidade. Agora, vamos tentar entender como representamos a spline. Isso é o mesmo que saber como representar os objetos que são representados por splines.
Como podemos representar splines? Há duas maneiras, amplamente uma é base ou representação baseada em função. Outra é a representação baseada em métricas de base. E esses dois são equivalentes. É claro que isso é bastante óbvio e um pode ser convertido para o outro e vice-versa.
Vejamos alguns exemplos para entender a representação assim iniciaremos com métricas básicas, representação de splines. E começaremos com um exemplo simples. Considere um polinomial de grau um que é um polinomial linear, que na forma paramétrica podemos representar como um f u igual a a0 mais ua1. Agora a0, a1 são coeficientes. E u é o parâmetro devemos ter em mente aqui que esta é uma representação compacta. ai como a0, a1 na verdade representa vetores compreendendo de dois componentes, um cada um para as coordenadas correspondentes. Por isso, a0 realmente tem a0x, valores de a0y separados para coordenadas x e y.
Da mesma forma, o fu deverá ter expressões correspondentes, nomeadamente fxu e fyu. No entanto pela simplicidade trabalharemos com esta forma compacta em vez da forma expandida. Agora, essa equação paramétrica podemos representar na forma de matriz U.A. Então, este é um produto ponto de duas matrizes, U e A. U são as métricas de parâmetro e A são as métricas coeficientes.
Onde U é denotado na forma deste vetor 1, u e as métricas A são denotadas neste formulário de vetor de coluna. Tendo os dois coeficientes a0, a1 no nosso exemplo. Agora, uma vez que este é um polinômio de grau 1, por isso precisamos de pelo menos dois pontos de controle para determinar f. Vamos denotar aqueles dois por p0 e p1.
Agora, esses pontos utilizaremos para parametrizar o polinômio, ou seja, vamos supor que determinados valores de parâmetro e, portanto, esses pontos de controle, por exemplo, podemos supor que os pontos de controle denotam valores da função no limite onde podemos definir a fronteira como os pontos em que o parâmetro valoriza texto do valor 0 e 1.
Se for esse o caso, então podemos configurar o nosso sistema de equações como mostrado aqui, dois-equação. Uma para p0, uma para p1 com o valor do parâmetro fixo. Agora, ao resolver essas equações podemos obter os coeficientes.
No entanto, se olarmos de perto então podemos ver que o mesmo sistema de equação que podemos representar na forma de matrizes. Agora, o que é essa representação matricial podemos representá-la como sendo capaz de C.A. Onde p é definido como um vetor de coluna C é definido como outro vetor de coluna e A é definido como mais um vetor de coluna.
Então, como construímos a matriz C, pegamos os coeficientes de ai. Isso significa de a1 para um nessa ordem. Esses termos em cada equação a partir da linha correspondente da matriz C. Então, a primeira equação que tiramos para a primeira fila e assim por diante. Em outras palavras, impusemos certas restrições. Condições de parametrização como restrições para obter C. Em conformidade, C é chamada de matriz de restrição. Agora sabemos P igual a C.A assim podemos dizer que Um igual a C-1.P. Agora, esse inverso da matriz constante é chamado de matriz de base. Então, podemos representar f como U.A que pode ser despendida, como U.C-1.P ou UBP. Então, essa é a maneira de representar f em termos de multiplicação matricial. Agora, uma coisa que temos que observar aqui é que a matriz de base. Para um polinomial interpolante que satisfaça as condições de parametrização é fixado. Em outras palavras, a matriz ou a matriz de base caracteriza a polinomial. Então, se usarmos a matriz base B em vez da equação polinomial, então isso é tão bom quanto representar o polinômio porque B é fixo para o polinomial particular.
Agora, sabemos que a spline é feita de peças polinomiais. Agora, se cada peça é feita do mesmo tipo de polinomial, isso significa que o grau e as restrições são iguais. Então, então no geral, Spline pode ser exclusivamente caracterizado por cada peça. E já que já mencionamos que uma peça polinomial pode ser caracterizada pela matriz de base, então a matriz de base também pode ser usada para caracterizar com exclusividade toda a esplina. Por isso, quando estamos representando a esplina, podemos simplesmente representá-la em termos de matriz de base.
Agora essa é a base matriz de matriz de spline. Assim, para recapitular dado um polinômio, podemos ter uma matriz de base única para aquela polinomial sob certas restrições. Assim, a matriz de base é adequada para representar a polinomial. Agora as mesmas peças polinomiais são usadas para representar uma esplina. Assim, para cada peça polinomial, temos as mesmas métricas para que possamos utilizar uma matriz de base única para representar o Spline geral, pois a matriz de base nos dirá que peças polinomiais particulares são usadas para representar o spline. Esta é a representação matricial de base de splines.
Esta explicação que acabamos de mencionar, então matriz de base refere-se a peças polinomiais desta spline, estamos assumindo que todas as peças são feitas de um mesmo polinomial. Assim, a matriz de base polinomial representa toda a esplina. Agora, vamos concentrar a atenção para o outro tipo de representação da spline, a saber, a representação da função de mistura. Agora, mais cedo, vimos que podemos representar f em termos de matriz de base, como U.B.P. Agora, se expandiremos o lado direito, obtemos a soma ponderada de polinômios com os pontos de controle sendo os pesos. Por isso, no nosso exemplo vamos derivá-lo e ver o que acontece. Por isso, no nosso exemplo temos um polinomial de grau 1 e temos as matrizes nesta de u é esta. B, é esta Matrix e C são as métricas de ponto de controle. Agora se expandimos, obteremos essa equação em termos de points.Now, os polinômios individuais na soma ponderada, como o termo 1-u e u são as funções blending. Assim, a função geral é representada como uma soma ponderada de polinômios. E esses polinômios individuais são chamados de função de base ou das funções de mistura.
Agora, para um dado polinômio, as funções de mistura também são fixas para que possamos usá-las para caracterizar a polinomial. Assim, para um determinado polinomial com restrições, as funções que podem ser usadas para representá-lo são fixas. Então, esse conjunto de função de mistura pode ser usado para caracterizar o polinomial para que possamos aplicar a mesma lógica aqui. Spline composto por várias peças do mesmo tipo polinomial. Por isso, também podem ser representados em termos das funções de mistura, uma vez que eles estão caracterizando exclusivamente as peças polinomiais constituintes.
Assim, de forma compacta, podemos representar um Spline ou a curva f desta forma em que pi é o i-ésimo ponto de controle e bi é a função de mistura.