Algoritmo de Chaikin para desenho de curvas
Sendo um programador que adora gerar arte via código, ou um artista que se aventura na área da programação, você precisa dominar alguns algoritmos simples de desenho.
Hoje em dia, temos vários frameworks que nos ajudam a trabalhar com a arte generativa de forma simplificada. Mas se você, assim como eu, prefere criar os seus próprios métodos, provavelmente já começou a estudar algumas formas matemáticas para desenho de curvas.
Uma das formas mais utilizadas hoje em dia é a Curva de Bézier, pois ela leva em consideração dois ou três pontos de controle além dos pontos principais e, por meio de cálculos matemáticos, determina todos os pontos intermediários da curva.
Este tipo de curva requer um cálculo matemático relativamente simples, mas pode assustar um pouco aqueles que não se dão tão bem com as equações paramétricas.
Mas existem outros métodos interessantes. Quero te apresentar uma abordagem interessante que é um método numérico. Por meio de algumas iterações de um algoritmo simples, é possível gerar uma curva simples e suave.
George Chaikin
George Chaikin foi professor de Arte e Matemática na Lehman College of the City University of New York. Mais do que um professor, ele foi um cientista e um artista e trouxe grandes contribuições para a Computação Gráfica.
Em 1974 ele apresentou um método inovador de refinamento de curvas por meio de cortes nos segmentos de reta que compõem a curva. Depois de um tempo este algoritmo foi deixado de lado porque surgiram outros mais eficientes. Entretanto, por sua simplicidade, pode ser implementado rapidamente em sistemas que não precisam de um poder de cômputo muito grande.
A curva de Bézier, citada anteriormente já havia surgido no meio acadêmico desde os anos 60, mas Chaikin resolveu abordar a suavização de curvas por uma nova perspectiva. Em vez de utilizar pontos de controle, ele resolveu trabalhar com cortes nos segmentos de reta que compõem um polígono.
O algoritmo
O algoritmo de Chaikin é bem simples e produz um resultado interessante dependendo do número de iterações que usamos.
Passo 1
Para começar, traçamos uma linha que representará um polígono (aberto ou fechado) que encapsula a nossa curva. Na Figura 2, foram traçados os quatro pontos principais (P1 a P4).
Passo 2
Em seguida, devemos criar novos pontos em cada segmento de reta (formado pelos pontos em sequência, tomados dois a dois), de modo que eles estejam a 25% e a 75% do tamanho do segmento. Veja na Figura 3 que foram desenhados todos os pontos que atendem a essa demanda:
Passo 3
O próximo passo do algoritmo é conectar os pontos, de forma que o segundo ponto de um segmento se conecte ao primeiro ponto de controle do próximo segmento, como mostra a Figura 4.
Passo 4
Agora podemos ligar os pontos para termos uma curva aproximada. Por conveniência, movemos o primeiro ponto de controle para a posição do primeiro ponto do polígono e o último ponto de controle para o último ponto do polígono, como mostra a Figura 5.
E pronto, este é o algoritmo.
Para que a curva seja mais suave, basta repetir o processo recursivamente, considerando os novos segmentos gerados como parte do polígono inicial. Veja como a curva já fica muito mais suave com duas iterações do algoritmo. Na Figura 6, temos a figura inicial sendo o polígono em vermelho (resultado da primeira iteração) e, em azul, o resultado da segunda iteração.
Testando
Quer testar as suas habilidades de desenho e ver como o algoritmo se comporta com diferentes parâmetros de entrada? Fiz um playground específico para isso:
Você também pode clonar este projeto feito em javascript no GitHub:
https://github.com/phcacique/chaikin
Divirta-se!
