novida.jtk11@gmail.com
Please contact me for more correction about this blog

Sunday, April 13, 2014

Computer Graphics - Bresenham Algorithm for Making Line

Assalamualaikum. Konnichiwa, mina!
Kalau postingan sebelumnya membahas bagaimana membuat garis dengan menggunakan Algoritma DDA, maka sekarang saya akan memberikan algoritma untuk membuat garis dengan menggunakan algoritma Bresenham. Berikut algoritmanya:

Bresenham untuk gradien garis <1:

  1. start point (x0,y0) dan end point(x1,y1)
  2. gradien (m) = (y1-y0)/(x1-x0) harus < 1
  3. hitung deltaX=x1-x0
  4. hitung deltaY=y1-y0
  5. hitung 2.deltaY
  6. hitung 2.deltaY-2.deltaX
  7. hitung p0=2.deltaY-deltaX
  8. k=0
  9. jika pk<0, (xk,yk) = xk+1,yk
  10. dan p(k+1)=pk+2.deltaY
  11. jika tidak, (xk,yk) = xk+1,yk+1
  12. dan p(k+1)=pk+2.deltaY-2.deltaX
  13. k=k+1
  14. ulangi langkah ke 9 hingga 13 selama deltaX kali
contoh:

Diketahui sebuah sumbu dengan titik koordinat (10,15) dan (20,12). Gambarkan garis tersebut dengan menggunakan Algoritma Bresenham. 

Penyelesaian :
  1. (X1, Y1) dan (X2, Y2)
  2. ΔX  = X2 – X1 = 20 – 10 = 10
  3. ΔY = Y2 – Y1 = 12 – 5 = 7
  4. P0  = 2ΔY – ΔX = 2(7) – 10 = 4
  5. A = 2ΔY = 14
  6. B = 2ΔY - 2ΔX = -6
  7. Tabel Iterasi (putara)
K
Pk
(Xk+1, Yk+1)
0
4
(11 , 6)
1
-2
(12 , 6)
2
12
(13 , 7)
3
6
(14 , 8)
4
0
(15 , 9)
5
-6
(16 , 9)
6
8
(17 , 10)
7
2
(18 , 11)
8
-4
(19 , 11)
9
10
(20 , 12)

Aturan :
  1. Jika Pk bernilai positif, maka tambahkan hasilnya dengan B dan nilai X dan Y ditambah 1.
  2. Jika Pk bernilai negatif, maka tambahkan hasilnya dengan A dan nilai X ditambah 1, sedangkan Y ditambah 0 (tetap).
  3. Putaran dihentikan jika koordinat X dan Y sudah mencapai batas Akhir, dalam kasusu ini (20 , 12).


Berikut ini adalah hasil garisnya . 

contoh algoritma Bresenham, bresenham, algoritma, panduan, latihan, kasus

Gambar dengan Pixel diperbesar.


PRAKTIKUM
Membuat aplikasi sederhana pembuat garis dengan algoritma Bresenham. Bahasa pemrograman yang digunakan adalah Java dengan IDE Eclipse.

1. Buat class Bresenham.java dengan source code sebagai berikut:

package graphics;
import java.awt.Graphics;
public class Bresenham {
public int x_awal;
    public int y_awal;
    public int x_akhir;
    public int y_akhir;
    public int dx;
    public int dy;
    public int dx2;
    public int dy2;
    public int dy2mindx2;
    public int pk;
public void drawBresenham(Graphics g,int x0, int y0, int x1, int y1){
this.x_awal=x0;
this.y_awal=y0;
this.x_akhir=x1;
this.y_akhir=y1;
this.dx=Math.abs(this.x_awal-this.x_akhir);
this.dy=Math.abs(this.y_awal-this.y_akhir);
this.dx2=this.dx*2;
this.dy2=this.dy*2;
if(this.dx>=this.dy){
this.dy2mindx2=this.dy2-this.dx2;
this.pk=this.dy2-this.dx;
while(this.x_awal!=this.x_akhir && this.y_awal!=this.y_akhir){
g.fillRect(this.x_awal, this.y_awal, 2, 2);
if(this.x_akhir>this.x_awal){
this.x_awal++;
}else{
this.x_awal--;
}
if(this.pk>=0){
if(this.y_akhir>this.y_awal){
this.y_awal++;
}else{
this.y_awal--;
}
this.pk=this.pk+this.dy2mindx2;
}else{
this.pk=this.pk+this.dy2;
}
}
}else{
this.dy2mindx2=this.dx2-this.dy2;
this.pk=this.dx2-this.dy;
while(this.x_awal!=this.x_akhir && this.y_awal!=this.y_akhir){
g.fillRect(this.x_awal, this.y_awal, 2, 2);
if(this.y_akhir>this.y_awal){
this.y_awal++;
}else{
this.y_awal--;
}
if(this.pk>=0){
if(this.x_akhir>this.x_awal){
this.x_awal++;
}else{
this.x_awal--;
}
this.pk=this.pk+this.dy2mindx2;
}else{
this.pk=this.pk+this.dx2;
}
}
}
}
}

2. Kemudian buat class Main.java yang digunakan untuk membuat boad atau papan gambar sebagai berikut:

package graphics;
/*
 * Author : Novida Wayan Sari
 * Program Name : Main
 * Description : This program integrate component JPanel 
 *  that used for drawing graphics like
 *  Line Bresenham and also
 *  coloring the component
 */
import java.awt.Color;
import java.awt.Graphics;
import java.awt.Point;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.awt.event.MouseAdapter;
import java.awt.event.MouseEvent;
import java.util.ArrayList;
import javax.swing.ImageIcon;
import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JPanel;

public class Main implements ActionListener{
//Attributes
private static ArrayList<int[]> coord = new ArrayList<int[]>();
private static ArrayList<int[]> coord2 = new ArrayList<int[]>();
//Main Program
public static void main(String [] Args) throws Exception{
JFrame frame=new JFrame("My Graphics Board");
frame.setSize(700, 500);
frame.setVisible(true);
frame.getContentPane().setBackground(Color.BLACK);
//Buttons Declaration
final JButton btn_color1=new JButton();
final JButton btn_color2=new JButton();
final JButton btn_color3=new JButton();
final JButton btn_color4=new JButton();
//Panel Component as Board for drawing
JPanel panel=new JPanel(){
/**
* 
*/
private static final long serialVersionUID = 1L;
Point point_start=null; //for collect point value when mouse pressed
Point point_end=null; //for collect point value when mouse Released
Point point_end2=null; //for collect point value when mouse Dragged
//it need for animation when mouse Dragged
int status_graph=1;
int status_color=1;
//Mouse Listener for Button
{
btn_color1.addMouseListener(new MouseAdapter() {
public void mouseClicked(MouseEvent evt) {
status_color=1;
}
});
btn_color2.addMouseListener(new java.awt.event.MouseAdapter() {
public void mouseClicked(MouseEvent evt) {
status_color=2;
}
});
btn_color3.addMouseListener(new java.awt.event.MouseAdapter() {
public void mouseClicked(MouseEvent evt) {
status_color=3;
}
});
btn_color4.addMouseListener(new java.awt.event.MouseAdapter() {
public void mouseClicked(MouseEvent evt) {
status_color=4;
}
});
}
Bresenham bresenham=new Bresenham();
{
addMouseListener(new MouseAdapter(){
public void mousePressed(MouseEvent e){
point_start=e.getPoint();
}
public void mouseReleased(MouseEvent e){
point_end=e.getPoint();
                        int[] points = {(int)point_start.getX(),(int)point_start.getY(),(int)point_end.getX(),(int)point_end.getY(),status_graph,status_color};
                        coord.add(points);
                        repaint();
}
});
addMouseMotionListener(new MouseAdapter(){
public void mouseDragged(MouseEvent e){
point_end2=e.getPoint();
int[] points2 = {(int)point_start.getX(),(int)point_start.getY(),(int)point_end2.getX(),(int)point_end2.getY(),status_graph,status_color};
coord2.add(points2);
repaint();
}
});
}
public void paintComponent(Graphics g){
                for (int[] points2 : coord2) {
                if((int)points2[5]==1){
g.setColor(Color.BLUE);
}else if((int)points2[5]==2){
g.setColor(Color.GREEN);
}else if((int)points2[5]==3){
g.setColor(Color.RED);
}else{
g.setColor(Color.YELLOW);
}
                super.paintComponent(g);
                bresenham.drawBresenham(g, (int)points2[0], (int)points2[1], (int)points2[2], (int)points2[3]);
                } 
                g.drawString("   ------", 0, 15);
                g.drawString("   ------", 0, 30);
                g.drawString("   ------", 0, 45);
                g.drawString("   ------", 0, 60);
                g.drawString("Novida's Paint Board", 480, 15);
                g.drawString("Choose Color", 500, 65);
}
public void paint(Graphics i){
super.paint(i);
for (int[] points : coord) {
if((int)points[5]==1){
i.setColor(Color.BLUE);
}else if((int)points[5]==2){
i.setColor(Color.GREEN);
}else if((int)points[5]==3){
i.setColor(Color.RED);
}else{
i.setColor(Color.YELLOW);
}
bresenham.drawBresenham(i, (int)points[0], (int)points[1], (int)points[2], (int)points[3]);
} 
}
}; //End of Panel
panel.add(btn_color1);
panel.add(btn_color2);
panel.add(btn_color3);
panel.add(btn_color4);
ImageIcon icon5=new ImageIcon("images/color_blue.png");
ImageIcon icon6=new ImageIcon("images/color_orange.png");
ImageIcon icon7=new ImageIcon("images/color_red.png");
ImageIcon icon8=new ImageIcon("images/color_yellow.png"); 
btn_color1.setIcon(icon5);
btn_color1.setContentAreaFilled( false ); 
btn_color2.setIcon(icon6);
btn_color2.setContentAreaFilled( false ); 
btn_color3.setIcon(icon7);
btn_color3.setContentAreaFilled( false ); 
btn_color4.setIcon(icon8);
btn_color4.setContentAreaFilled( false ); 
panel.setBackground(Color.BLACK);
panel.setForeground(Color.BLACK);
frame.add(panel);
frame.setVisible(true);
}
@Override
public void actionPerformed(ActionEvent e) {
// TODO Auto-generated method stub
}
}

hasil dari program diatas adalah


Gambar 1. Papan Gambar


Algoritma di atas sudah dikembangkan untuk semua nilai gradien.

Selamat Bereksperimen!

1 comments:

  1. UnknownOctober 24, 2020 at 1:09 PM

    soalnya beda dengan hasil tabel perhitungan. itu gradiennya bukannya jadi positif ya/lebih dari 1?

    ReplyDelete

Subscribe to: Post Comments (Atom)

 

About Metro UI Theme

Metro and Classical Theme of Blogger