Soal 1: Algoritma DDA & Bresenham — Visualisasi Interaktif

Jawaban — Penjelasan Lengkap Kedua Algoritma

Kedua algoritma dijelaskan secara lengkap di bawah. Pilih salah satu untuk dijadikan materi video presentasi.

---

Bagian A: Algoritma DDA (Digital Differential Analyzer)

1. Konsep Dasar

DDA (Digital Differential Analyzer) adalah algoritma penggambaran garis yang bekerja secara incremental — dimulai dari titik awal, algoritma menghitung koordinat berikutnya menggunakan operasi floating-point. Secara sederhana: garis dipecah menjadi langkah-langkah kecil, kemudian setiap langkah di-plot satu per satu.

2. Cara Kerja

1. Hitung selisih: \(dx = x_2 - x_1\) dan \(dy = y_2 - y_1\)
2. Tentukan jumlah langkah (steps) = \(\max(|dx|, |dy|)\)
3. Hitung inkremen: \(x_{\text{inc}} = dx / \text{steps}\), \(y_{\text{inc}} = dy / \text{steps}\)
4. Mulai dari \((x_1, y_1)\), tambahkan inkremen setiap langkah, bulatkan ke integer terdekat untuk mendapatkan koordinat pixel.

3. Pseudocode

// DDA Algorithm
function DDA(x1, y1, x2, y2):
    dx = x2 - x1
    dy = y2 - y1

    // Determine number of steps
    if abs(dx) > abs(dy):
        steps = abs(dx)
    else:
        steps = abs(dy)

    // Calculate increments
    xInc = dx / steps
    yInc = dy / steps

    x = x1
    y = y1

    // Plot pixels
    for i = 0 to steps:
        plotPixel(round(x), round(y))
        x = x + xInc
        y = y + yInc

4. Contoh Perhitungan: Garis dari (2, 3) ke (8, 7)

• dx = 8 − 2 = 6, dy = 7 − 3 = 4
• steps = max(6, 4) = 6
• xInc = 6/6 = 1.0, yInc = 4/6 ≈ 0.667

Step	x (float)	y (float)	x (plot)	y (plot)
0	2.000	3.000	2	3
1	3.000	3.667	3	4
2	4.000	4.333	4	4
3	5.000	5.000	5	5
4	6.000	5.667	6	6
5	7.000	6.333	7	6
6	8.000	7.000	8	7

Hasil pixel: (2,3), (3,4), (4,4), (5,5), (6,6), (7,6), (8,7) — total 7 pixel.

---

Bagian B: Algoritma Bresenham

1. Konsep Dasar

Bresenham (diperkenalkan tahun 1965) menggunakan integer arithmetic sepenuhnya, tanpa satu pun operasi floating-point. Algoritma ini memanfaatkan decision parameter \(p_k\) untuk menentukan apakah pixel berikutnya bergerak ke kanan (E) atau ke kanan-atas (NE).

2. Cara Kerja

1. Hitung selisih: \(dx = |x_2 - x_1|\), \(dy = |y_2 - y_1|\)
2. Tentukan arah: \(sx = \text{sign}(x_2 - x_1)\), \(sy = \text{sign}(y_2 - y_1)\)
3. Hitung nilai awal: \(p_0 = 2dy - dx\)
4. Untuk setiap step:
   • Jika \(p_k \geq 0\): plot (x+1, y+1), \(p_{k+1} = p_k + 2dy - 2dx\) (pilih NE/pixel atas)
   • Jika \(p_k < 0\): plot (x+1, y), \(p_{k+1} = p_k + 2dy\) (pilih E/pixel kanan)

3. Pseudocode (Oktaf Pertama, 0 ≤ m ≤ 1)

// Bresenham Line Algorithm — Octant 1 (0 <= m <= 1)
function Bresenham(x1, y1, x2, y2):
    dx = abs(x2 - x1)
    dy = abs(y2 - y1)
    sx = (x1 < x2) ? 1 : -1
    sy = (y1 < y2) ? 1 : -1

    // Initial decision parameter
    p = 2 * dy - dx

    x = x1, y = y1
    plotPixel(x, y)

    for i = 0 to dx - 1:
        if p >= 0:
            y = y + sy
            p = p + 2 * dy - 2 * dx    // Choose NE pixel
        else:
            p = p + 2 * dy              // Choose E pixel
        x = x + sx
        plotPixel(x, y)

4. Contoh Perhitungan: Garis dari (2, 3) ke (8, 7)

• dx = 6, dy = 4, sx = 1, sy = 1
• p₀ = 2(4) − 6 = 8 − 6 = 2

Step	pk	pk ≥ 0?	Aksi	x	y
0	2	✓ Yes	NE (y naik)	2	3
1	2 + 8 − 12 = -2	✗ No	E (y tetap)	3	4
2	-2 + 8 = 6	✓ Yes	NE	4	4
3	6 + 8 − 12 = 2	✓ Yes	NE	5	5
4	2 + 8 − 12 = -2	✗ No	E	6	6
5	-2 + 8 = 6	✓ Yes	NE	7	6
6	—	—	End	8	7

5. Perbandingan DDA dan Bresenham

Aspek	DDA	Bresenham
Jenis Aritmatika	Floating-point (÷, +)	Integer only (+, −, ×2 = shift)
Kecepatan	Lebih lambat (operasi float)	Cepat (operasi integer, bit shift)
Akurasi	Akumulasi error pembulatan	Akurat — decision parameter integer
Pembulatan	Memerlukan round() setiap langkah	Tidak memerlukan pembulatan
Oktaf	Otomatis semua oktaf (incremental)	Memerlukan penanganan khusus per oktaf
Implementasi	Sederhana, mudah dipahami	Sedikit lebih kompleks
Penggunaan Umum	Pembelajaran, prototipe	Produksi (GPU, printer, plotter)

---

Visualisasi Interaktif

Gunakan Canvas interaktif di bawah untuk melihat kedua algoritma menggambar garis pixel per pixel. Atur koordinat, pilih algoritma, dan sesuaikan kecepatan animasi.