Pular para o conteúdo principal

Algoritmo de Bresenham


O algoritmo de Bresenham — em homenagem a Jack Elton Bresenham — é um algoritmo criado para o desenho de linhas, em dispositivos matriciais (como por exemplo, um monitor), que permite determinar quais os pontos numa matriz de base quadriculada que devem ser destacados para atender o grau de inclinação de um ângulo.

O Código


void bresenham1(int x1, int y1, int x2, int y2){        
        int slope;
        int dx, dy, incE, incNE, d, x, y;
        // Onde inverte a linha x1 > x2       
        if (x1 > x2){
            bresenham1(x2, y2, x1, y1);
             return;
        }        
        dx = x2 - x1;
        dy = y2 - y1;
    
        if (dy < 0){            
            slope = -1;
            dy = -dy;
        }
        else{            
           slope = 1;
        }
        // Constante de Bresenham
        incE = 2 * dy;
        incNE = 2 * dy - 2 * dx;
        d = 2 * dy - dx;
        y = y1;       
        for (x = x1; x <= x2; x++){
            putpixel(x, y);
            if (d <= 0){
              d += incE;
            }
            else{
              d += incNE;
              y += slope;
            }
        }
  }

Desenhar Reta em Java – Algoritmo de Bresenham/DDA Inteiro

O objetivo deste algoritmo é reduzir o esforço computacional para se
desenhar uma reta, bem como reduzir erros de arredondamento e operações com ponto flutuante. E, de fato, o algoritmo de Bresenham consegue fazer isso – ele se desenvolve sem nenhuma operação de ponto flutuante, nenhuma variável numérica é do tipo float ou double e, também, o algoritmo não realiza divisões entre números inteiros.
Abaixo, o algoritmo para desenhar retas em Java e, na sequência, algumas explicações.
public void draw(Graphics g){
  int x, y, erro, deltaX, deltaY;
  erro = 0;
  x = p1.x;
  y = p1.y;
  deltaX = p2.x - p1.x;
  deltaY = p2.y - p1.y;
  
  if((Math.abs(deltaY)>=Math.abs(deltaX) && p1.y>p2.y)
   ||(Math.abs(deltaY)<Math.abs(deltaX) && deltaY<0)){
   
   x = p2.x;
   y = p2.y;
   deltaX = p1.x-p2.x;
   deltaY = p1.y-p2.y;
  }
  p1.draw(g);
  if(deltaX>=0){
   if(Math.abs(deltaX)>=Math.abs(deltaY)){
    for(int i=1;i<Math.abs(deltaX);i++){
     if(erro<0){
      x++;
      new Ponto(x,y).draw(g);
      erro += deltaY;
     }else{
      x++;
      y++;
      new Ponto(x,y).draw(g);
      erro += deltaY - deltaX;
     }
    }
   }else{
    for(int i=1;i<Math.abs(deltaY);i++){
     if(erro<0){
      x++;
      y++;
      new Ponto(x,y).draw(g);
      erro += deltaY - deltaX;      
     }else{
      y++;
      new Ponto(x,y).draw(g);
      erro -= deltaX;
     }
    }
   }
  }else{ // deltaX=Math.abs(deltaY)){
    for(int i=1;i<Math.abs(deltaX);i++){
     if(erro<0){
      x--;
      new Ponto(x,y).draw(g);
      erro += deltaY;
     }else{
      x--;
      y++;
      new Ponto(x,y).draw(g);
      erro += deltaY + deltaX;
     }
    }
   }else{
    for(int i=1;i<Math.abs(deltaY);i++){
     if(erro<0){
      x--;
      y++;
      new Ponto(x,y).draw(g);
      erro += deltaY + deltaX;      
     }else{
      y++;
      new Ponto(x,y).draw(g);
      erro += deltaX;
     }
    }
   }
  }
  p2.draw(g);
 }


Detalhes sobre o DDA Inteiro de Retas


Como eu uso esse método?

Normalmente eu crio uma classe “Reta” com os atributos Ponto p1 e p2 (os pontos inicial e final da reta), o seu método construtor que recebe o ponto inicial e o final; e este método “draw” para desenhar a reta.
Importante notar que este método de desenho recebe como parâmetro o elemento Graphics g, onde o desenho de cada ponto da reta vai acontecer e o método tem a seguinte chamada:
Reta r;
r = new Reta(p1,p2);
r.draw(g);
O Ponto é definido com os atributos x e y e também possui um método para se desenhar, o draw(Graphics g). Neste método, uso o método default do java para desenhar retas, porém desenhando um ponto:
public void draw(Graphics g){
 g.setColor(Color.black);
 g.drawLine(x,y,x,y);
}

Variáveis no Bresenham

Nas primeiras linhas, apenas a definição das variáveis acontece. Os deltas servem para controlar os 4 possíveis casos do algoritmo de Bresenham; x e y vão definir os pontos da reta a ser desenhada; e erro é uma variável de controle sobre como proceder com x e y a cada ponto desenhado:
  • incrementar x?
  • incrementar y?
  • incrementar x e y?
  • decrementar…?
O seu valor muda somando ou subtraindo os deltas em seu valor atual. Mais explicações na sequência neste artigo.

Ordem dos Pontos

Nas linhas de 9 a 16, o algoritmo procura atender uma premissa para seu funcionamento correto: fazer com que os valores de y caminhem do menor para o maior entre os pontos da reta.

DDA Inteiro: Linhas 18~72

O algoritmo de Bresenham é dividido em 4 casos. O que define cada um é a identificação do maior delta (X ou Y), considerando também se deltaX é positivo ou negativo.
Por que procura-se o maior delta? O maior delta define em qual eixo (abcissas ou ordenadas) está o maior caminho a ser percorrido, pois o loop (for (…)) deverá conter tantas execuções quanto forem necessários pontos para se desenhar a reta percorrendo essa maior distância, pois cada loop desenha um único ponto.
E qual a importância do “sinal” do deltaX? Como nas linhas 9 a 16 o algoritmo força que a reta seja desenhada de tal forma que se vá do menor para o maior y, pode acontecer que o x varie do maior para o menor ao longo do desenho, e isso influi diretamente no incremento ou decremento de X, bem como no sinal do deltaX utilizado no cálculo do erro.
Ou seja, se o desenho da reta vai começar pelo maior x e ele é incrementado, nunca será alcançado o menor x e a reta seria desenhada de forma errada. E, quando deltaX>=0, significa que x1<x2 (então desenha-se do menor x para o maior x), enquanto deltaX<0 é resultado de x2<x1 (maior x para o menor x).
E por isso a diferença entre incrementar ou decrementar o valor de x nos casos do algoritmo DDA Inteiro:
  • Se x2>x1, x++;
  • Se x1>x2, x- -;
A variação do sinal do deltaX se define de modo análogo:
  • Se deltaX>=0, subtrai-se deltaX;
  • Se deltaX<0, soma-se o deltaX (no fim, está sendo somado um número negativo, ou seja, uma subtração);
O objetivo é que o deltaX seja sempre subtraído no valor do erro, mas se ele for negativo, a subtração de um valor negativo, resulta em uma soma, daí a variação no sinal de deltaX quando é calculado o erro. Como é sempre definido que y2>y1, deltaY será sempre positivo (ou zero) e basta sempre somar seu valor no erro.
O detalhe sobre a variação do erro é que ele decide quando variar x e y baseado nos deltas. A coordenada de maior delta deve variar (incrementar ou decrementar) mais vezes, pois tem um caminho maior a percorrer. O que o erro faz é controlar quantas vezes a mais uma variável é incrementada ou decrementada em relação a outra.
E assim mantém-se a coerência no algoritmo para o desenho de retas.
Detalhe importante: nas linhas 17 e 73 está o desenho do primeiro e último pontos, respectivamente.
Para finalizar, teste isso tudo em um JPanel no método paint(Graphics g):
public class Canvas extends JPanel{
  public Canvas(){
  ...
 }
 public void paint(Graphics g){
  super.paint(g);
  new Reta(new Ponto(15,10), new Ponto(400,200)).draw(g);
 }
}

Comentários

Postagens mais visitadas deste blog

Gigabyte lança placa de rede compatível com 10 Gigabit Ethernet

A Gigabyte anunciou o lançamento da sua nova placa de rede compatível com 10 Gigabit Ethernet. A placa é baseada no chip Aquantia GC-AQC 107.

A nova placa de rede possui interface PCI Express 3.0 e é compatível com os padrões 10GBASE-T (10 Gbps), 5 GBASE-T (5 Gbps), 2.5 GBASE-T (2.5 Gbps), 1000 BASE-T (1 Gbps) e 100 BASE-TX (100 Mbps).

Ela pode ser utilizada com cabos de rede das seguintes categorias:
– CAT6a*
– CAT6**
– CAT5e***
– CAT5

*Para conexão de 10Gbps, o comprimento máximo do cabo pode ser de até 100m.
**Para conexão de 10Gbps, o comprimento máximo do cabo pode ser de até 55m.
***Para conexões de 10Gbps e 5Gbps, o comprimento máximo do cabo pode ser de até 30m.

A nova placa de rede da Gigabyte deve chegar ao mercado custando US$ 99. Vale lembrar que a empresa já oferece diversas placas-mãe com conectividade 10 Gigabit Ethernet.

The Good Place - Netflix

Dias de chuva a primeira coisa que faço é, caçar algum filme ou série pra assistir na Netflix, Amazon Prime ou algum anime no Chunchyroll. Passando pela lista da Netflix, olhava para essa série mas ficava receoso de assistir e não gostar. Mas, olhando o catálogo e vendo que já assisti quase tudo de novidade resolvi dar uma chance a série mas já doido pra reprovar.

Antes de começar a falar da série, vamos falar do que sabemos da vida pós-morte. Sabemos que cada crença tem um modo de ver a vida pós-morte. Algumas acreditam em paraíso e inferno, outras tem o purgatório (uma espécie de escola de verão pra quem ficou de recuperação no teste da vida), os ateus acham que o pós-morte é mais químico e orgânico, seu corpo servirá de adubo pra natureza e, alguns acreditam em ciclo de reencarnação, onde as pessoas voltam para este mundo com uma nova identidade.

Dissertando um pouco sobre a vida pós-morte, vamos entender agora a série. No começo, quando a protagonista Eleanor morre e vai parar no &q…

Computação Gráfica: Fundamentos básicos