VSD

Visible Surface Determination

Visible Surface determination (VSD) atau disebut juga dengan Hidden Surface Removal (HSR) merupakan suatu cara untuk menentukan garis atau permukaan yang terlihat pada suatu objeck 3D dan spesifikasi pandangan (kamera). Masalahnya garis atau permukaan mana yang harus dihilangkan?

Terdapat 3 pendekatan utama pada permukaan terlihat, yaitu:

1. Tes penampakan konservatif (conservative surface test)

Hanya sebatas trivial reject saja, yang tidak memberikan jawaban.

Contoh : back-free culling. Untuk mendapat penyelesaiannya harus dilakukan dengan pendekatan yang lain.

2. Ketelitian gambar (image-precission)

Bagian yang terlihat ditentukan dengan point-point pada setiap posisis pixelnya pada bidang proyeksi.

Contoh : pada raytracing, atau Z-buffer

// Image or Pixel Precision – O(p) operations

for(each pixel) {

determine the object closest to the viewer that is

pierced by the projector through the pixel;

draw the pixel in the appropriate color;     }

3. Ketelitian objek (object-precission)

Menentukan bagian mana yang terlihat dengan membandingkan objek dan bagian-bagiannya dalam layar .

Contoh : pada poly clipping, BSP trees,dll

// Object Precision – O(n2) operations

for(each object) {

determine those parts of the object whose view is

unobstructed by other parts of it or any other object;

draw those parts of appropriate color; }

Terdapat beberapa cara atau metode untuk mendeteksi suatu permukaan yang terlihat ini, yaitu:

1.     Metode Depth-Buffer

Metode ini untuk menguji dari depth-z dari masing-masing permkaan untuk menentukan permukaan terlihat. Pertama kali ditemukan oleh Catmull 74. Algoritma dari Depth-Buffer (Z-Buffer), yaitu:

1)       Menginisialisas depth-buffer dan me-refeshnya sehingga untuk semua posisi penyangga (x, y)

      depth(x,y)= 0, refresh(x,y)= I_background

2)       Menghitung kedalaman z pada setiap posisi (X,y) dalam polygon

If  z> depth(x,y), then set depth (x,y) = z, refresh(x,y)=I_surface(x,y)

3)       Hitung nilai z untuk polygon planar.

Dengan rumus Z = (-D-Ax-By)/ C, Lalu pada (x+ Dx,y), nilia dari z adalah z’=z-A/C

4)       Jika polygon tidak planar, maka di-subdivide (dibagi lagi).

Keuntungan:

a)       Presorting tidak ada dan perbandingan objek-objek diperlukan

b)      Waktu yang diambil dari perhitungan permukaan terlihat adalah konstan

c)       Merupakan implementasi yang sederhana dan mudah pada hardware

d)      Baik untuk animasi dan sangat mudah untuk diterapkan

Kekurangan

a)       Membutuhkan memori yang besar untuk Z dan Frame buffer

b)      Merupakan subjek yang menggunakan nama lain.   == > Improved by A-buffer algorithm [CARP 84]

c)       Dapat menggambarkan pixel yang sama beberapa kali

2.   Metode A-Buffer

Metode A-Buffer mewakili antialiased, daerah rata-rata, metode buffer akumulasi. Setiap posisi dari A-buffer memiliki 2 bidang, yakni:

1)     Depth field (Kedalaman bidang)

ð Memberikan nilai yag positif atau negative.

2)     Intensity filed (Intensitas diajukan)

ð Memberikan informasi intensitas dari permukaan atau merupkan nilai pointer.

3.   Metode Pohon BSP (Binary Space Partitioning)

Polygon akan scan-converted dengan benar, jika menyediakan pemesanan oklusi front-to-back, semua poligon yang ada di sisi lain dari viewer,dikonversi pertama kali dan diikuti oleh polygon tersebut, kemudian semua sisi yang sama dari viewer. Bentuk (construct) dari pohon BSP adalah:

Daun dari suatu pohon BSP merepresentasikan sebuah subspace cembung, dengan simpul yang mengikat daun dan setiap simpul dalam sebuah pohon BSP menggambarkan subspace – subspace yang terdiri dari semua node anak-anak, Keuntugan dari metode ini adalah cocok untuk aplikasi yang berhubungan dengan perubahan sudut pandang tapi tidak untuk suatu objek. Kerugiannya adalah mememrlukan preprocessing (banyak polygon yang membelah (split) daripada depth-sort), penghitungan dalam pembuatan bayangan dapat terjadi lebih dari satu kali.

4.     Metode Octree

Metode Octree direpensentasikan pada benda yang bervolume. Permukaaan yang terlihat ditentukan dengan mencari node (simpul) octree dari depan ke belakang. Terdapat 2 octree traversal, yaitu: 1)  Hierarchically recursive traversal (traversal hirarki recursif) 2)  Test octants by OQ test accelerated by GPU (Uji tes octants oleh OQ dipercepat oleh GPU)

5. Metode Ray-Casting 

Ray-Casting atau dikenal juga dengan ray-tracing merupakan metode untuk menghitung jalan gelombang atau partikel melalui suatu system. Dalam grafik computer ray–casting adalah teknik untuk menghasilkan suatu gambar dangan menelusuri jalan cahaya melalui pixel dalam gambar pesawat. Terdapat 2 bentuk metode yang berbeda, yaitu:

1)     Ray-tracing(physics)

            Untuk menganalisis system optic,

contoh : pada sinyal radio, samudera akustik, dan desain optis

2)     Ray-tracing(graphics)

            Digunakan untuk generasi gambar 3D, yang mampu menghasilkan tingkat  ketajaman yang tinggi.

Contoh algoritma dari suatu metode Ray-Casting adalah sebagai berikut :

select center of projection and window on viewplane;

for( each scan line in image) {

for (each pixel in scan line) {

determine ray from center of projection through pixel;

for (each object in scene) {

if (object is intersected and is closest considered thus far)

record intersection and object name; }

set pixel color to that at closest object intersection; }  }

6. Metode Curved Surfaces

Ada 2 cara dalam metode ini, yaitu: 1)   Catmull 74, 75 Dia menerangkan bahwa potongan kecil (patch) akan dibagi menjadi 4 potonga keci lagi secara rekursif ke dalam s dan t hingga proyeksny dapat mencakup tidak lebih dari 1 pixel. Setelah itu, metode z-buffer diterapkan.

2) Subdivisi adaptif

Pembagian patch hanya terjadi pada direksinya (arahnya), jika patch tesebut sudah cukup datar terhadap yang lainnya. Setelah pembagiannya sudah cukup, maka tiap patch dijadijkan/diperlakukan menjadi segiempat.Terakhir diterapkannya algoritma scan-line.

7. Metode Wireframe

Metode ini merupakan penyesuaian dari metode z-buffer, dimana permukaan dapat dilukiskan/digambarkan ke dalam refresh buffer sehingga permukaan interior menjadi warna latar belakangnya dan batas-batasnya menjadi warna di latar depan.

Selain itu, terdapat juga beberapa teknik untuk mengefisiensikan algoritma dari permukaan terlihat. Di antaranya adalah sebagai berikut :

a)   Koheren (Coherence)

   Objek, Face, Edge, Scan-line, Luas(Daerah), Kedalaman dan Frame

b)  Extents and Bounding Volumes

Gambar di atas menampilkan gambar segitiga dan bounding volumenya

                                   

c)    Hierarchy

Testing dimulai dari akar atau puncak dari node, yaitu: a.    ~ Jika terletak di luar, maka semua objek ditolak. b.    ~ Sebaliknya, sub-node dites berulang

d)   Spatial Partitioning

Contoh gambar:

Gambar 1	Gambar 2

e)    Back-Face Culling

Merupakan back-face penghapusan yang akan membuat tidak akan ada lagi faces (gambaran) di belakang objek yang akan ditampilkan. Batasan dari algoritma ini adalah:

1. Hanya dapat digunakan pada benda padat yang dimodelkan sebagai polygon mesh. Ini merupakan model yang paling umum untuk membangun system grafis line-scan.

2.    Bekerja baik pada polyhedral cembung, tapi belum tentu pada polyhedral cekung. Contohnya pada gambar di bawah ini, dimana bagian dari hidden face tidak akan dihapuskan oleh penghapusan back-face (pengolahan yang lebih lanjut).

Titik-titik yang terdapat pada permukaan normal dapat dikategorikan bebrapa jika dilihat dari suatu pusat proyeksi pada poligonnya.

– Positive    : poligon back-face

– Zero         : jika dilihat dari tepi

– Negative  : poligon  front-face

Referensi

http://freezcha.wordpress.com/2009/10/27/visual-surface-determination/

http://hafizh_n.staff.gunadarma.ac.id/Downloads/files/12136/VSD%28week+7%29.ppt

KONSEP MEMBUAT GARIS DAN IMPLEMENTASINYA

ALGORITMA BRESENHAM

Bresenham pada tahun 1965, melakukan perbaikan dari algoritma perhitungan koordinat piksel yang menggunakan persamaan, dengan cara menggantikan operasi bilangan riel perkalian dengan operasi penjumlahan, yang kemudian dikenal dengan Algoritma Bresenham. Pada algoritma bresenham, nilai y kedua dan seterusnya, dihitung dari nilai y sebelumnya, sehingga hanya titik y pertama yang perlu dilakukan operasi secara lengkap. Perbaikan algoritma ini ternyata tidak menghasilkan perbaikan yang cukup siginifikan. Perbaikan berikutnya dilakukan dengan cara menghilangkan operasi bilangan riel dengan operasi bilangan integer. Operasi bilangan integer jauh lebih cepat dibandingkan dengan operasi bilangan riel, terutama pada penambahan dan pengurangan.
Cara menentukan garis dengan algoritma bresenham :


1.    Tentukan koordinat awal garis (x0,y0)
2.    tentukan koordinat akhir garis (x1,y1)
3.    Hitung jarak mendatar ke 2 titik (dx)
Dx=x1-x0
4.    Hitung jarak mendatar ke 2 titik (dx)
Dy=y1-y0
5.    Tentukan faktor pembagi (mencari yg lebih panjang) 
Apakah dx>dy,bila ya
            Step=dx
             Bila tidak
            Step=dy
6.    Hitung faktor penambah ke koordinat mendatar dan vertikal titik berikut (x_tambah,y_tambah)
X_tambah=dx/step
Y_tambah=dy/step


7.    Buat loop mulai titik ke 1 sampai titik ke step
For k=1 to step
8.    Hitung koodinat titik berikutnya
X=x+x_tambah
Y=y+y_tambah
9.    gambar pikxel pada koordinat (x,y)
Catatan : koordinat x,y harus bulat (integer), sehingga hasil dari perhitungan diatas harus diinteger-kan
10.    Ulangi langkah ke 7, dan setetrrsnya sampai titik ke step 


Berikut pseudocode untuk algoritma bresenham


x0=10;y0=10;
x1=100;y1=200;
dx=x1-x0;
dy=y1-y0;
x=float(x0);y=float(y0);
if (dx>dy)
        step=dx;
else
        step=dy;
x_tambah=(float) dx/step;
y_tambah=(float) dy/step ;
 int xx,yy;
 for (k=0;k
        {
                x+=x_tambah;
                y+=y_tambah;
        Canvas->Pixels[int(x)][int(y)]=clRed;
           }
  


http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm

DDA (Digital Defferential Analyzer)

Garis merupakan kumpulan dari titik-titik, untuk membentuk garis lurus adalah dengan mengetahui titik awal dan titik akhir. Dengan mengetahui titik awal dan titik akhir maka kita dapat membentuk garis. Untuk menggambarkan proses pembuatan garis dari titik awal ke titik akhir ada berbagai algoritma. Algoritam yang umum adalah DDA dan Bresenham.

Berikur ini adalah algoritma DDA

1.      Tentukan 2 buah titik.

2.      Tentukan yang menjadi titik awal (X₀,Y₀) dan titik akhir (X₁,Y₁).

3.      Hitung Dx dan D_yD_x = X₁-X₀ dan D_y = Y₁ – Y₀

4.      Bandingkan Abs(D_x) dan Abs(D_y)Jika Abs(D_x) > Abs(D_y) makaSteps = Abs(D_x) bila tidak Steps = Abs(D_y)

5.      Hitung penambahan koordinat pixel, yaitu:X_increment = dx/steps, danY_increment = dy/steps.

6.      Koordint selanjutnya, yaituX+X_incrementY+Y_increment

7.      Posisi pixel ditentukan dengan pembulatan nilai koordinat tersebut.

8.      Ulangi langkah 6 dan 7 untuk posisi selanjutnya sampai X = X₁, Y = Y₁ 

 

IMPLEMENTASI DDA dan BRESENHAM

UNTUK ANTI-ALIASING

 

APA ITU ANTI-ALIASING 

Seperti teori diatas bahwa garis merupakan kumpulan titik yang saling terhubung. Pada pembahasan sebelumnya kelompok kami menceritakan sebuah efek yang bernama Tessellation yang digunakan untuk membuat gambar detail menjadi semakin realistik. Kali ini kelompok kami akan sedikit menjelaskan teknologi yang pada umumnya sering dipakai dalam dunia games yaitu Implementasi Dari DDA dan Bresenham. 

Selain adanya tesselltion yang digunakan untuk membuat gambar menjadi lebih realistik ada juga yang namanya anti aliasing yaitu memperhalus tampilan gambar dengan membuat sejumlah titik yang membentuk garis seperti yang ada pada gambar diatas sehingga bisa mengurangi jaggies pada sebuah games. 

Konsep DDA & Bresenham dipakai untuk menghilangkan Jaggies dalam sebuah games. Terkadang merasa kurang nyaman jika menonton film layar lebar atau bermain games tanpa anti aliasing karena adanya belahan atau jaggies ( sejumlah titik garis yang tidak terdistribusi dengan wajar).

Lihat gambar dibawah ini perbedaan penggunaan anti aliasing dan non anti aliasing :

 

Gambar sebelah kiri memperlihatkan banyaknya jaggies dan disebelah kanan memperlihatkan berkurangnya jaggies karena dibantu oleh teknologi Anti Aliasing yang diterapkan melalui konsep DDA Bresenham. 

CARA KERJA DDA & BRESENHAM 

UNTUK ANTI ALIASING

Seperti biasanya sesuai dengan konsep DDA bahwa garis adalah kumpulan titik maka untuk mengubahnya juga harus dilakukan pembentukan garis oleh banyaknya titik dan kembali kepada pembuatnya ada yang dihubungkan dengan konsep fisika mekanika ada yang secara matematis. Gambar diatas hanyalah contoh pembentukan garis secara sederhana saja. Setelah titik-titik terbuat maka akan dilanjutkan kedalam tahap penarikan garis dan lihat gambar dibawah ini :

Untuk membentuk sebuah anti aliasing DDA di convert menjadi dua bagian teknis yaitu Sebut saja namanya (Wave area dan Frequency Area) pertama setelah sebuag titik dibentuk dan dihubungkan sehingga membentuk garis maka ada yang namanya sampling image untuk dirender yang kemudian diberikan ke daerah Frequency untuk diubah menjadi algoritma diskrit.

Setelah diubah menjadi algoritma diskrit maka akan dibentuk garis lingkar untuk menghitung seberapa besar jaggies yang akan dipersempit yang intinya bagaimana sejumlah titik sembarang membentuk garis baru untuk memperhalus tampilannya.

Setelah dihitung lingkar jaggiesnya maka akan transformasikan menjadi sebuah titik pixel yang membentuk resolusi baru yang akan diberikan kembali untuk menimpa jaggies yang lama sehingga garisnya lebih sempurna sehingga akan dikembalikan lagi ke daerah wave denganukuran sampling yang lebih kecil lagi sehingga efek jaggiesnya berkurang karena sampling kecil yang baru menutupi sampling besar dengan jumlah yang banyak sehingga gambar terlihat lebih halus dan jernih.

Sekian materi yang kami sampaikan semoga bermanfaat sampai bertemu di episode menarik selanjutnya.

http://www.patentstorm.us/patents/5570463/description.html

http://slidefinder.net/s/scan_conversion_dda_line_drawing/12090680

http://www.pantherproducts.co.uk/Articles/Graphics/anti_aliasing.shtml

 

PENGARUH EFEK TESSELLATION & NON TESSELLATION

A.   Pengertian Tesselation.

Tessellation adalah membagi objek menjadi poligon (segitiga) untuk proses rendeering 3D. Untuk tiap segitiga, point sudut dan nilai warna seperti halnya nilai transparansi, jika diperlukan, bisa dideterminasikan dan umumnya diaplikasikan kedalam sebuah games baik console maupun game pc.

B. Penggunaan Efek Tessellation 

Didalam sebuah games efek tessellation digunakan untuk menyempurnakan keindahan game ketika gpu memproses karakter dengan rendering sehingga mampu menghasilkan polygon yang lebih banyak didalam sebuah game.

Dalam kesempatan ini kami mencoba untuk memberikan gambaran antara game yang menggunakan efek tessellation maupun dengan game yang tidak menggunakan efek tessellation. Syarat menggunakan tessellation adalah dukungan game sendiri dan dukungan oleh kartu grafis yang mampu menawarkan teknologi ini yaitu GPU dengan teknologi directX 11.

Contoh image prosesing dengan penggunaan efek tessellation dan non tessellation : 

Didalam gambar terlihat jelas penggunaan efek tessellation bagi pengolahan gambar terutama animasi untuk sebuah games ialah dengan merender gambar sehingga menghasilkan gambar yang memiliki banyak polygon.

Lihat gambar (a) yaitu karakter yang tidak menggunakan efek tessellation garis yangterbentuk pada sejumlah titik yang ada di badan katak tersebut tidak memiliki lekukan yang berarti seperti hanya sebuah garis lurus biasa dan tidak mengalami perenderan.

Lihat gambar (b) yaitu karakter yang menggunakan efek tessellation guratan garis yang ada di bagian lengan dan sisi perut katak telah mengalami rendering dengan efek tessellation sehingga timbulah lekukan baru / penambahan garis polygon yang dilakukan dengan real time tessellation. Penglihatan lebih jelasnya bias dilihat di gambar (c) dan (d).

C.   Peroses Tesselation.

Efek tessellation dimulai pertama kali dengan membuat sebuah polygon yang sederhana seperti jaring dengat tingkat resolusi yang sangat kecil. Unit terkecil dari jaring sederhana kemudian membuat jaringan baru yang lebih halus dimana vertex di sebagian jaringan wajah akan mengeras satu dengan yang lainnya sehingga tahap kedua ini wajah akan semakin halus. 


Didalam pengerasan ini ada yang namanya vertex shader yang digunakan untuk menempatkan titik baru kedalam jaring yang masih longgar dan menambahkannya sehingga jaring yang seolah bolong-bolong lama-lama akan menjadi tertutup oleh vertex shader.

Tahap terakhir ialah menggabungkan jaringan yang terpisah kedalam jaringan yang telah mengeras pada tahap kedua dan melakukan proses rendering dengan sempurna sehingga bisa didapatkan tessellation dengan kualitas tinggi dimana displacement digabungkan kedalam surface potition. Lihat gambar dibawah ini.

Perubahan gambar secara instan dengan penggunaan efek tessellation.

Untuk lebih memahami pengunaan dan efek dari tessellation, dapat kita lihat pada video dibawah ini, yang membandingkan sebuah video show suatu consol game (Unigane Heaven-2009), yang memakai tessellation dan tidak memakainya.

Dengan perkembangan teknologi hardware VGA, masing-masing produsen VGA card bersaing untuk menunjukkan kebolehan produk mereka dengan beradu ke halusan/ketajaman tekstur pada permaian game. Dengan memakai metode tessalation mereka mengadu keindahan tampilan produk mereka.

Sedikit info mengenai Tesselation :

-   Tesselation yang indah saat ini dapat bekerja pada DirectX 11 dan VGA yang berperforma tinggi, sebab semakin halus tekstur dan polygonal pada suatu tampilan beban Pixel dan bit akan semakin tinggi.

-    Saat ini produsen VGA card yang paling bersaing dalam hal ketajaman dan kehalusan gambar adalah NVIDIA dan ATI RADEON, dengan adanya hardware yang menunjang pada computer, maka tekhnik tessellation akan semakin baik hasilnya.

-  Software 3DMAX adalah software grafis 3 demensi yag sudah mengadopsi tekhnik tessellation, dengan memakai software ini dan spesifikasi computer yang memadai, kita dapat menciptakan suatu karakter yang tekstur yang lebih hidup.

Source :


http://www.extremetech.com/article2/0,2845,2329315,00.asp
http://en.wikipedia.org/wiki/Tessellation
http://www.gametrailers.com/user-movie/dx-11-tessellation-demo/348225