(1250 kelime)
(357 okuma)   

Backface Culling (Arka Yüzeylerin Ayiklanmasi)

Oyun motorunuz gitgide hizlaniyor. Bir kamera sinifiniz var ve frustum culling isini de hallettiniz. Ekranda gozukmeyen nesneleri cok hizli bir sekilde eleyebiliyorsunuz artik. Ama hala ekraninizda birsuru poligondan olusan nesneler var ve oyununuz halen yavasssss calisiyor. Nesnelerinizin poligonlarinin degismedigini dusunerek (OpenGL kullaniyorsaniz) display listler kullanmaya karar verdiniz glBegin ve glEnd yerine. Hiz artisi gayet umut verici. (yazar mesaj vermeye calisiyor glBegin/End kullanmayiiinnn!) Ama hala memnun degilsiniz. Onca doku, isik, yaratik, yuzey yine istediginiz performansta calismiyor. Ne yapabiliriz?...

Dusunelim.. Ekranda gorunmeyecek nesneleri eledik. Ama hala ekranda gorunmeyecek poligonlar var cizilmeye calisilan. Hem de neredeyse ekrana cizilmeye calisilan tum poligonlarin (kabaca) yarisi kadar. Uzatmayayim, ekrandaki her nesnenin arka yuzeylerinden bahsediyorum. Backface Culling (BFC) (Arka Yuzeylerin Ayiklanmasi diye Turkcelestirebiliriz belki), herhangi bir anda, ekrandaki bir nesnenin bize donuk olmayan, arka tarafinda kalan yuzeylerin ayiklanmasina, cizilmemesine verilen ad. Diger bir ad da Hidden Surface Removal sanirim. Her frame'de nesnemizi cizmeden once kameradan gorunmeyen yuzeyleri bulup eleyecegiz.

Eger display list kullaniyorsaniz cizim icin, bu yontemi kullanamazsiniz. Cunku bildiginiz gibi display listler ilk basta hazirlanir ve icerigini sonradan degistiremeyiz Ancak display listler ile hemen hemen ayni performansda calisabilen vertex arrayleri kullanabiliriz. Ikisi arasindaki tam performans farkini bilemiyorum, tek bildigim teoride display listlerin biraz daha hizli oldugu ancak kendimce yaptigim testlerde ikisi arasinda belirgin bir fark goremedim. Sanirim ekran kartina gore degisebiliyor performans, ama cogu yeni kart vertex arrayleri iyi destekliyor, guvenebilirsiniz.

BFC ne kadar gerekli? Bilemem, yaptiginiz oyuna cok bagli. Eger cok poligonlu nesneleriniz yoksa belki ugrasmaniza bile gerek olmaz. OpenGL'e glEnable(GL_CULL_FACE) demeyi de secebilirsiniz. Ancak “Kamera” ile ilgili yazida bahsettigim gibi problem ekran kartina poligonlarinizi gonderme sirasinda gerceklesiyor. Yani OpenGL (veya Direct3D) sizden iyi bu isi yapamaz. Hemen size bir test sonucu vereyim. 16000 kusur ucgenden olusan bir test nesnesini (tek isik altinda, tek dokulu), normal vertex array yontemi ile 150 fps, OpenGL culling'i acinca 170 fps, burada anlatacagim BFC yontemi ile 350 fps ile goruyorum. Degerler ekran kartina gore degisebilir belki ama HSR'in ne kadar onemli olabilecegini aciklayabildim umarim. Sonuc olarak eger cok yuzeyli nesneleriniz var ise mutlaka kullanmaniz gerekecek bir gun. Ve iyi bir oyun icin de ne kadar cok poligon, o kadar iyi demek gunumuzde (bu tartisilir ya neyse).

Baslamadan hemen bir not. Hep OpenGL'den bahsediyorum, ama Direct3D kullaniyorsaniz da okumaya devam edin. BFC size de gerekli. Sadece cizim isini Direct3D ile nasil yapiyorsunuz bilemem, illa ki benzer bir karsiligi vardir (vertex buffers olabilir mi?).

Once vertex array'ler ile cizim isini anlatmaya baslamistim, ama farkettim ki tahminimden de uzun surecek bu konu, vazgectim. Konu yoksa baya dagilacak, eger istek olursa onu da baska bir zaman yazabilirim.

Aslinda yontem cok basit. Nesne veri yapinizi nasil tuttugunuza gore degisebilir anlattiklarimin detaylari. Benim nesne yapimda her ucgen icin bir yuzey normali ve uc vertex tutuyorum. Ve her vertexin icinde de o ucgen icin hesaplanmis vertex normalleri de bulunuyor. Isik hesaplamalari icin malesef bu sart (baska yazi konusu yine). BFC icin gerekli olan, sonucta her ucgenin (veya poligonun) yuzey normali.

Yüzey Normali nasil hesaplanir?

Matematiksel olarak uc nokta ile bir yuzeyi tanimlayabilirsiniz. Ve bu uc nokta ile o yuzeyin normalini de bulabilirsiniz. Kod ornegi isterseniz;

/*!
	Computes the facenormal by crossing two vectors defined by (p1-p2) and (p3-p2).
*/
XVector3D ComputeFaceNormal(XVertex3D& p1, XVertex3D& p2, XVertex3D& p3)
{
	XVector3D u, v;
	u.x = p1.x - p2.x; u.y = p1.y - p2.y; u.z = p1.z - p2.z;
	v.x = p3.x - p2.x; v.y = p3.y - p2.y; v.z = p3.z - p2.z;

	XVector3D facenormal = u.Cross(v);

	return facenormal;
}

Uc noktayi kullanarak iki vektor olusturuyoruz ve bunlarin cross carpimi bize normali veriyor. Tekrar olacak ama, uc boyutlu bir oyun yaziyorsaniz Vector sinifiniz vardir (umarim). Kucuk bir not duseyim, noktalarin ve carpimlarin sirasi onemli, ters sekilde v.Cross(u) seklinde carparsaniz tam ters yonde bir vektor elde edersiniz.

Kamera nereye bakiyor?

Kameranin goremedigi yuzeyleri bulmak icin takdir edersiniz ki kameranin baktigi yonu biliyor olmamiz gerekiyor. Kamera sinifindan bahsederken kameranin baktigi yonu de bir vektor olarak tutuyorduk hatirlarsaniz. Ancak kucuk bir problem var. Kameramiz world space'de (argh) ama nesnemizin koordinatlari object space'de (nesne uzayi). Normalde cizime baslamadan once glTanslate/Rotate komutlariyla, veya glMultMatrix/LoadMatrix ile OpenGL'e istedigimiz donusumu belirtiyoruz, ardindan da noktalarimizi cizim icin yolluyoruz ekran kartina. Ekran karti gelen tum koordinatlari bu donusum matrisi ile carpip world space koordinatlarina donusturuyor. (dipnot sonkez; Direct3D de ayni isi yapiyor, kacamazsiniz) Yani nesnenizi onceden world space'e cevirmeyi aklinizdan gecirmeyin, cok carpim var. Onun yerine kucuk bir takla atip kameranin bakis vektorunu object space'e cevirecegiz. Yuzlerce noktayi donusturmektense, tek bir nokta... Peki bunu nasil yapabiliriz? Elimizde o anki object-world space donusum matrisi olmasi gerekiyor. Bunu kolaylikla alabilirsiniz OpenGL'den asagidaki komut ile.

	float camera[16];
	glGetFloatv( GL_MODELVIEW_MATRIX, camera);

Onemli Not: Bunu bu nesne icin glTranslate/glRotate komutlarini kullandiktan hemen sonra, BFC ve cizim isleminde hemen once yapmalisiniz.

Onemsiz Not: Kamera yazisinda bu matris alma isleminin performansi dusurebilecegini soylemistim, simdilik bosverin (ama ben zaten boyle yapmiyorum onu da bilin :), konuyu dagitmamak, basit tutabilmek icin bu sekilde yaziyorum.

Takla demistim az once, simdi de taklayi atiyoruz. Bakis vektorumuzu donusum matrisimizin tersi (inverse) ile carparsak vektoru object space'e gecirmis oluruz. Dusunurseniz mantikli oldugunu siz de goreceksiniz, eger bir noktayi bu matris ile carptigimizda world space'e dondurmus oluyorsak, world space'deki bir noktayi bu matris ile boldugumuzde de object space'e dondurmus oluruz. Bir vektoru matris ile bolmek diye birsey matematikte varolmadigi icin, biz de tersi ile carpiyoruz. (yazarin lineer cebir hocasinin gozleri yasariyor) (yazar kendi kendine “matematiik” “ben” “anlatiyorum” diye kekeliyor).

Bunca seyi anlattiktan sonra soylemeden gecemeyecegim, vektor kadar matris sinifinizin olmasi da sart. Ve guvenebilmelisiniz.

Matris isleri

Matris kodunu vermeden once son not. OpenGL ve Direct3D'nin donusum matrisi dizilimi (iki boyutta) birbirinin transpozu. Yani bu kodu aynen Direct3D icin kullanamazsiniz, ve kabul ediyorum, mantiksiz olan OpenGL'inki malesef. Ayrica bu matris tersi hesaplanmasi sadece rotation/translation matrisi icin gecerli, baska amaclar icin daha genel cozumlere ihtiyaciniz var. (yazar: cok mu gevezeyim, okuyan: EVEEEETTTT!)

/*!
	Gets the inverse of the transformation matrix. 
	\note Only usable for OpenGL transform matrix inverse
*/
XMatrix4 XMatrix4::GetInverseTransform() const
{
	return XMatrix4(	m_data[0],
			m_data[4],
			m_data[8],
			0.0f,
			m_data[1],
			m_data[5],
			m_data[9],
			0.0f,
			m_data[2],
			m_data[6],
			m_data[10],
			0.0f,
			-(m_data[0]*m_data[12]+m_data[1]*m_data[13]+m_data[2]*m_data[14]),
			-(m_data[4]*m_data[12]+m_data[5]*m_data[13]+m_data[6]*m_data[14]),
			-(m_data[8]*m_data[12]+m_data[9]*m_data[13]+m_data[10]*m_data[14]),
			1.0f);
}

matris vektor carpimini da yaziyorum;

/*!
	Matrix by Vector Multiplication operator overloaded.
	\warning Multiplied according to OpenGL matrix format!
*/
XVector3D XMatrix4::operator *(const XVector3D& rhs)
{
	float tx = m_data[0] * rhs.x 
		+ m_data[4] * rhs.y 
		+ m_data[8] * rhs.z 
		+ m_data[12];
	float ty = m_data[1] * rhs.x 
		+ m_data[5] * rhs.y 
		+ m_data[9] * rhs.z 
		+ m_data[13];
	float tz = m_data[2] * rhs.x 
		+ m_data[6] * rhs.y 
		+ m_data[10] * rhs.z 
		+ m_data[14];
	return XVector3D(tx,ty,tz);
}

Ve nihayet bakis vektorumuzun object space'e cevirilmesi;

	XMatrix4 invertedCamera = camera.GetInverseTransform();
	XVector3D view = invertedCamera*CameraView;

Kamera matrisimizin tersi ile bakis vektorunu carptik, hepsi bu.

Az kaldi, dayanin... Sira geldi nesnemizin yuzeylerinden hangilerini goremedigimizi bulmak kaldi. Elimizde her yuzey icin bir normali vektoru ve kameranin bakis yonu vektoru var. Bunlarin ikisinin dot carpimina bakacagiz sadece. Eger pozitif ise bu iki vektor ayni yone bakiyordur. Negatif ise zit yonlere bakiyorlardir. Bu ne demek? Negatif ise birbirlerine dogru bakiyorlardir, yani yuzey gozukuyordur, pozitif ise bu poligonu cizmemize gerek yoktur. Bu kadar basit. Kod?

for (int i = 0; i < num_face; i++) // num_face degiskeni poligon sayisina esit
{
	if(CameraView.Dot(m_pFaceNormals[i]) <= 0)
	{
		// bu yuzeyi cizebiliriz, sakla bunu
	}
}

Kendi kodum ile sizin veri yapiniz buyuk olasilikla uyusmayacagi icin yine ilgili kismi size birakiyorum. Bu kadar uzattigima degdi mi bilmiyorum, basit bir yontem, benim kendi koduma eklemem bugun 45 dakikami aldi. (15 dakikasi matris inverse fonksiyonundaki bug'i bulmak icin)

Bana ulasmak icin mentat@cfxweb.net adresini kullanabilirsiniz. Ve tabi www.oyunyapimi.org forumlarini. Umarim yazdiklarim bir isinize yarar.

mentat, 02.01.2003