Teknik Kliping Garis dan Polygon
Pemotongan poligon atau biasa disebut clipping merupakan suatu proses yang sangat penting dalam aplikasi komputer grafik. Clipping juga merupakan suatu algoritma yang kompleks. Saat ini masih banyak penelitian yang dilakukan untuk menemukan suatu algoritma yang lebih baik dari yang telah ada.
Dalam gambar 2D misalnya, jika menggunakan program editing gambar, pengguna memodifikasi gambar dan melakukan perbesaran gambar melihat untuk hanya menampilkan bagian atas gambar, CPU tidak perlu melakukan perhitungan untuk memeproses perbesaran gambar bagian bawah. Dengan mengkliping gambar bagian bawah, perhitungan yg kompleks bisa dihindari sehingga program menjadi lebih cepat dan lebih ringan karena menggunakan lebih sedikit memori.
Dalam gambar 3D misalnya, gambar suatu kota di dalam komputer dapat memiliki model, tekstur, dan data shader dalam memori untuk setiap bangunan di kota itu. Tetapi sejak kamera mampu menampilkan gambar dari sudut 90° atau dari sudut pandang lain. Komputer tidak perlu mengubah, tekstur, dan bangunan yang berada di belakang objek/menghadap jauh dari kamera. Algoritma kliping memungkinkan prosese render mengabaikan semua perhitungan tersebut, dan program berjalan lebih cepat.
Teknik kliping yang baik sangat penting dalam perkembangan video game terutama untuk memaksimalkan frame rate dan kualitas visual.

Beberapa algoritma kliping yang telah ada:
Algoritma Line Kliping:
Cohen-Sutherland
Liang-Barsky
Cepat-kliping
Cyrus-Beck
Nicholl-Lee-Nicholl
Pemusnahan cepat untuk permainan samping bergulir 2D
Circle dan B-Spline kliping algoritma
Patrick-Gilles Maillot's Skripsi
Polygon kliping algoritma:
Sutherland-Hodgman
Weiler-Atherton
gVatti
Polygon Struktur kliping algoritma:
Segitiga strip dan-Quad jerat 3D Kliping Homogen (Patrick-Gilles Maillot)

Bab ini akan membahas algoritma dari Sutherland - Hodgman
Algoritma Sutherland - Hodgman Polygon Clipping melakukan kliping poligon terhadap setiap tepi sisi jendela pada gilirannya.
tampilan garis dibagi menjdi 3, yaitu:
1. Garis yang terlihat seluruhnya (fully visible) –> garis tidak perlu dipotong
2. Garis yang hanya terlihat sebagian (partially visible) –> garis yang perlu dipotong
3. Garis yang tidak terlihat sama sekali (fully invisible) –> garis tidak perlu digambar

Contoh gambar sebelum diklipping :


Gambar dibawah menunjukkan bagian-bagian yang sudah diklipping

a. Memotong bagian kiri dari window.
b. Memotong bagian atas dari window.
c. Memotong bagian kanan dari window.
d. Memotong bagian bawah dari window.
Untuk mempermudah perhitungan, kami memperpanjang potongan sisi persegi panjang dan membaginya menjadi sembilan daerah. Setiap daerah diberi kode 4-bit deteermined oleh dimana daerah tersebut terletak sehubungan dengan halfplanes luar tepi klip-persegi panjang. Setiap bit pada outcode diatur baik 1 (benar) atau 0 (false), sedangkan 4 bit dalam kode sesuai dengan kondisi berikut:
Bit 1 : sisi luar dari window, dan berada di bagian atas garis
Y > Ymax
Bit 2 : sisi luar dari window, dan berada di bagian bawah garis
Y <> Xmax
Bit 4 : ssi luar dari window, dan berada di bagian kiri garis
X <> xmax
0 apabila x ≤ xmax
2
B
1 apabila y <> ymax
0 apabila y ≤ ymax



Cara Menghitung Intersections
Asumsikan bahwa kita akan mengkliping sebuah polgon dengan simpul di (x1, y1) dan (x2, y2) terhadap jendela klip dengan simpul di (xmin, ymin) dan (Xmax, ymax).

Lokasi (IX, IY) dari tepi persimpangan dengan sisi kiri jendela adalah:
IX = xmin
IY = kemiringan * (xmin-x1) + y1, di mana kemiringan = (y2-y1) / (x2-x1)\
Lokasi perpotongan dari sisi kanan jendela adalah:
IX = Xmax
IY = kemiringan * (Xmax-x1) + y1, di mana kemiringan = (y2-y1) / (x2-x1)
Lokasi perpotongan dari sisi atas jendela adalah:
IX = x1 + (ymax - y1)
IY = ymax
Lokasi perpotongan dari sisi bawah jendela adalah:
IX = x1 + (ymin - y1)
IY = ymin

Dibawah ini adalah contoh kasus dalam bentuk segitiga :

Untuk mempermudah pengerjaan, penghitungan koordinat potongnya dibagi menjadi 3 bagian, yaitu bagian atas, kiri, dan kana.
Perpotongan bagian atas
Untuk titik A(0,5) terhubung oleh edge AB dan AC. Sehingga vertex yang terlibat adalah C(-5,2) dan B(5,-2). Sehingga perhitungannya :


Untuk perpotongan antara vertex A dan C adalah:
IY=Ymax=3
slope = (y2-y1)/(x2-x1)=(-2-5)/(5+0)=7/-5=-1.4
IX =(ymax-y1) /slope + x1= ((3-5) / (-1.4)) + 0 = 1.42 + 0 = 1.42
Sehingga didapat titik baru yaitu (1.42, 3)

Untuk perpotongan antara vertex A dan B adalah:
IY=Ymax=4
slope = (y2-y1)/(x2-x1)=(-2-5)/(-5+0)=-7/-5= 1.4
IX =(ymax-y1) /slope + x1= ((3-5) / (1.4)) + 0 = -1.42 + 0 = -1.42
Sehingga didapat titik baru yaitu (1.42, 3)

Perpotongan bagian kanan
Untuk titik B(5,2) terhubung oleh edge BA dan BC. Sehingga vertex yang terlibat adalah A(0,5) dan C(-5,-2). Sehingga perhitungannya :

Untuk perpotongan antara vertex B dan A adalah:
IX=Xmax=4
slope = (y2-y1)/(x2-x1) = (5-(-2))/(0-5) = 7/-5 = -1.4
IY =(xmax-x1) *slope + y1= ((4-5) *(-1.4)) + (-2) = 1.4 + -2 = -0.6
Sehingga didapat titik baru yaitu (4,-0.6)

Untuk perpotongan antara vertex B dan C adalah:
IY=Xmax=4
slope = (y2-y1)/(x2-x1) = (-2-(-2))/(-5-5) = 0/-10 = 0
IY =(xmax-x1) *slope + y1= ((4-5) *(0)) + (-2) = 0 + -2 = -2
Sehingga didapat titik baru yaitu (4,2)

Perpotongan bagian kiri
Untuk titik B(5,2) terhubung oleh edge BA dan BC. Sehingga vertex yang terlibat adalah A(0,5) dan C(-5,-2). Sehingga perhitungannya :

Untuk perpotongan antara vertex C dan A adalah:
IX=Xmin=-4
slope = (y2-y1)/(x2-x1) = (5-(-2))/(0+) = 7/5 = 1.4
IY =(xmin-x1) *slope + y1= ((-4 + 5) * (1.4)) + (-2) = 1.4 + -2 = -0.6
Sehingga didapat titik baru yaitu (-4,-0.6)

Untuk perpotongan antara vertex C dan B adalah:
IY=Xmin=-4
slope = (y2-y1)/(x2-x1) = (-2-(-2))/(-5-5) = 0/-5 = 0
IY =(xmax-x1) *slope + y1= ((4-5) *(0)) + (-2) = 0 + -2 = -2
Sehingga didapat titik baru yaitu (-4,-2)