Diferença entre o DDA e o algoritmo de Bresenham

O Algoritmo Digital Diferencial (DDA) e o Algoritmo de Bresenhams são os algoritmos de desenho de linhas digitais e são usados em gráficos de computador para desenhar figuras. Anteriormente, estávamos usando analisadores analíticos para calcular os pixels e, assim, os desenhos de linhas eram possíveis. Mas esses métodos analíticos não são tão precisos quanto os métodos digitais que, com o uso desses algoritmos digitais agora e como em todos os campos, também estamos inventando métodos de qualidade superior em computação gráfica. A invenção desses algoritmos é um exemplo perfeito. Antes de prosseguir, vejamos o conceito por trás desses algoritmos. Embora pareça fora do escopo de nossa discussão, é essencial apontar as diferenças básicas entre os dois. Se você está realmente familiarizado com os algoritmos, pode pular para as diferenças reais localizadas no final desta página.

O que é algoritmo diferencial digital (DDA)?

Um DDA é usado principalmente para desenhar linhas em gráficos de computador e usa valores reais enquanto prevê os próximos valores de pixel. Vamos assumir o valor inicial do pixel como (X0, Y0) (X0, Y0) e o pixel de destino como (X1, Y1) (X1, Y1). Vamos aprender como calcular os valores do pixel de destino a partir do valor conhecido do pixel (X0, Y0) (X0, Y0), conforme abaixo.

Como calcular o valor do ponto de destino usando o DDA?

Passo 1: Aqui temos a entrada (X0, Y0) (X0, Y0) e devemos identificar se a linha é paralela ao eixo x ou ao eixo y. Para descobrir isso, vamos agora calcular a diferença entre os valores de pixel inicial e de destino.

dx = X1 - X0

dy = Y1 - Y0

Passo 2: Agora, identificamos a diferença e devemos desenhar a linha ao longo do eixo x se 'dx' for zero, caso contrário, devemos desenhar a linha paralela ao eixo y. Aqui está o cálculo real em termos da linguagem de computador.

if (absoluto (dx)> absoluto (dy))

Passos = absoluto (dx);

outro

Passos = absoluto (dy);

Etapa 3: Agora, é hora de identificar as coordenadas 'x' reais ou as coordenadas 'y' dos valores de pixel para desenhar a linha.

X incremento = dx / etapas (flutuantes);

Incremento Y = etapas dy / (flutuantes);

Passo 4: Isso deve ser calculado até chegarmos ao pixel de destino. O algoritmo DDA arredonda o valor do pixel para o valor inteiro mais próximo enquanto faz o cálculo. Aqui está o exemplo de código do que discutimos agora.

Para (int v = 0; v < Steps; v++)

x = x + X incremento;

y = y + incremento em Y;

putpixel (Round (x), Round (y));

Terminamos de desenhar a linha usando o DDA e passemos ao agora Bresenham's!

O que é o algoritmo de Bresenham?

É também um algoritmo de desenho de linha digital e foi inventado por Bresenham no ano de 1962 e é por isso que tem o mesmo nome. Este algoritmo é mais preciso e usou subtração e adição para calcular o valor de pixel enquanto desenha a linha. A precisão do algoritmo de Bresenham é confiável ao desenhar curvas e círculos também. Vejamos como esse algoritmo funciona.

Passo 1: Os algoritmos de Bresenham assumem a coordenada inicial do pixel como (x_{a + 1}, y_uma).

Passo 2: Ele calcula automaticamente o próximo valor de pixel como (x_{a + 1}, y_{a + 1}), Aqui 'a' é o valor incremental e o algoritmo o calcula adicionando ou subtraindo as equações que ele formou.

Esse algoritmo calcula valores precisos sem arredondamentos e também parece mais fácil!

Exemplo Numérico do Algoritmo de Bresenham:

Vamos agora considerar os pontos (0,0) e (-8, -4) e traçar uma linha entre esses pontos usando o algoritmo de Bresenham.

Dados dados, (x1, y1) = (0, 0) e (x2, y2) = (-8, -4).

Vamos agora calcular os valores diferenciais como abaixo.

Dê sua nota! Dê sua nota!

Portanto, o valor incremental para x = ∆x / x2 = 8 / -8 = -1.

Y = y2-y1 = -4-0 = 4

Portanto, o valor incremental para y = ∆y / y2 = 4 / -4 = -1.

Variável de decisão = e = 2 * (∆y) - (∆x)

Portanto, e = 2 * (4) - (8) = 8-8 = 0

Com o cálculo acima, vamos tabular os valores resultantes. Os valores da coordenada y são ajustados com base em uma variável de decisão e estamos apenas ignorando seu cálculo aqui.

Pixel	x	y	Variável de decisão
(0,0)	0 0	0 0	0 0
(-1,0)	-1	0 0	Um valor
(-2, -1)	-2	-1	0 0
(-3, -1)	-3	-1	Um valor
(-4, -2)	-4	-2	0 0
(-5, -2)	-5	-2	Um valor
(-6, -3)	-6	-3	0 0
(-7, -3)	-7	-3	Um valor
(-8, -4)	-8	-4	0 0

Diferenças entre o DDA e o algoritmo de Bresenham:

Cálculo aritmético:

O DDA usa valores reais em seus cálculos com o uso de pontos flutuantes. Os próximos valores de pixel ou ponto são determinados com equações diferenciais

X incremento = dx / etapas (flutuantes)

Incremento Y = etapas dy / (flutuantes)

Aqui, nenhuma constante fixa é usada, mas no algoritmo de Bresenham os pontos fixos são usados em cálculos aritméticos. O algoritmo de Bresenham usa aritmética inteira, ao contrário do DDA.

Tipo de operação utilizada:

O DDA resolve as equações diferenciais com operações de multiplicação e divisão. Você pode notar o mesmo aqui, X incremento = dx / (flutuante) etapas. O algoritmo de Bresenham usa operações de adição e subtração e você pode notar o mesmo aqui em sua próxima equação de cálculo do valor de pixel (x_{a + 1}, y_{a + 1}) A aritmética é mais simples em Bresenham quando comparada à DDA.

Eficiência:

Como discutimos anteriormente, o algoritmo de Bresenham usa aritmética mais simples que o DDA e resulta em resultados eficientes.

Rapidez: Como o DDA usa números inteiros de ponto flutuante junto com operações de multiplicação e divisão, é comparativamente mais lento, enquanto o algoritmo de Bresenham usa apenas aritmética inteira juntamente com adições e subtrações apenas. Isso reduz consideravelmente o tempo gasto em seus cálculos e, portanto, mais rápido que o DDA.
Precisão: Embora o DDA use valores de ponto flutuante, a precisão do DDA não é tão melhor quanto a de Bresenham. Vários fatores afetam esse conceito e, portanto, o Bresenham's é mais preciso que o DDA.
Arredondamento: Basta olhar para o cálculo do DDA aqui.

X incremento = dx / etapas (flutuantes)

Você pode notar o 'float' e, portanto, ele não arredonda os valores, enquanto o algoritmo de Bresenham arredonda os valores para o número inteiro mais próximo. Portanto, os valores utilizados são mais simples no algoritmo de Bresenham.

O que isso desenha?

O DDA é capaz de desenhar círculos e curvas além de desenhar linhas. O algoritmo de Bresenham também é capaz de desenhar todos os mencionados acima e sua precisão é realmente maior do que a do DDA. Da mesma forma, o algoritmo de Bresenham poderia apresentar curvas eficientes do que aquela produzida pelo DDA. Ambos os algoritmos também podem desenhar triângulos e polígonos.

O que é caro?

Como o DDA inclui também o arredondamento, é caro que o uso do algoritmo de Bresenham.

Qual é um algoritmo otimizado?

De nossa discussão acima, é muito claro que o algoritmo de Bresenham é otimizado em termos de velocidade, custo e uso das operações.

Vejamos as diferenças de forma tabular.

S.No	Diferenças em	Algoritmo Digital Diferencial	Algoritmo de Bresenham
1.	Por que o nome?	Só porque foi a implementação digital das equações, recebeu o nome.	Foi inventado por J.E. Bresenham no ano de 1962 e, portanto, o nome.
2.	Computações	Envolve cálculos mais difíceis.	Os cálculos utilizados são realmente mais simples.
3.	Tipos de operações utilizadas	Usou multiplicações e divisões. As equações diferenciais de amostra usadas aqui são etapas Xincrement = dx / (float), Yincrement = dy / etapas (flutuantes).	Ele usa adições e subtrações. O cálculo da amostra aqui pode ser indicado como (x_{a + 1}, y_{a + 1}).
4.	Valores aritméticos de computação	Ele usa valores de ponto flutuante.	Ele usa apenas os valores inteiros.
5.	Eficiência	Resultados aritméticos complexos em menor eficiência.	Aritmética mais simples resulta em mais eficiência.
6.	Rapidez	O uso de operações de multiplicação e divisão leva muito tempo para seus processos de computação.	O uso de operações de adição e subtração leva menos tempo que o DDA.
7.	Precisão	É menor em precisão.	É mais preciso.
8.	Arredondamento	Ele usa valores reais e nunca arredonda os valores.	Arredonda os valores para os valores inteiros mais próximos.
9.	Capacidade de desenho	É capaz de desenhar linhas, círculos e curvas, mas com menor precisão. Podemos até desenhar triângulos e polígonos com este algoritmo.	É capaz de desenhar linhas, círculos e curvas com maior eficiência. Também é possível desenhar triângulos e polígonos com este algoritmo.
10.	Custo dos cálculos	É caro, pois envolve arredondamento também.	O uso do algoritmo de Bresenham é mais barato que o DDA.
11.	Algoritmo otimizado	Não é um algoritmo otimizado	É um algoritmo otimizado.

Lidamos com todas as diferenças possíveis entre o DDA e o algoritmo de Bresenham. Pode até parecer repetitivo, mas há alguma razão válida para mencionar esses pontos novamente e você saberia quando entender completamente. Se você ainda acha que existe uma ambiguidade, deixe um comentário. Vamos aprender juntos compartilhando o conhecimento adequado!

Protocolos e Formatos