Kamera ve Frustum Culling
(2597 kelime) (833 okuma) ![Yazdırılabilir Sayfa](images/print.gif)
Kamera ve “Frustum Culling”
Kendinize bir 3B grafik motoru yapiyorsunuz. OpenGL (veya
Direct3D) kullanarak ekrana uc boyutlu nesneler cizmeyi ogrendiniz.
Ve farkettiniz ki hep ayni noktada duruyor olmak hic enteresan degil
bir oyunda. Bir kameraniz olsa ve oyun dunyanizin icinde hareket
etseniz iyi olur. Belki bunu da basardiniz. OpenGL glu kutuphanesinin
gluLookAt komutunu kullanarak kameranizin pozisyonunu ve baktiginiz
noktayi (ve yukari vektorunuzu) belirtip kamera efektini yarattiniz.
Sonra oyununuza onlarca yaratik eklediniz, bunlari bir sekilde (bu
baska bir yazi konusu) organize ettiniz. Ekranda o anda gozukmeyen
nesnelerin cizilmeme isini de OpenGL'e biraktiniz. Yani siz
dunyanizdaki tum nesneleri ekran kartina cizilmesi icin yolluyorsunuz
ve kameranizin gorebildigi alanin disinda kalan nesneleri akilli ve
pahali ekran kartinizin cizmeyecegini umut ediyorsunuz, hatta
biliyorsunuz. Fakat, ekraninizda sadece bir iki yaratik, agac, vs
bulunmasina ragmen bir gariplik var. Oyun yavasssss. Sorun nerede
olabilir?
Ekran kartiniz hizli. Islemciniz iyi, RAM'iniz de cok ve yine
hizli. Gercek oyunlar cok cici calismasina ragmen sizin oyununuz
yavasssss.
Bunun onlarca sebebi olabilir. Ben burada olasi sebeplerden ilki
olan frustum culling'den bahsedecegim. Ekran kartiniza
glBegin/End ile veya vertex array'ler ile veya display
list'ler ile bir suru vertex, ustune bir de kaplanacak
doku yolluyorsunuz bir nesneyi cizmek icin. Gunumuzde bu “yollama”
islemi en problemli darbogaz sistemlerde. BUS hiziniz
bilgisayarinizdaki en yavas yer. Bu yuzden AGP diye birsey cikti ve
gitgide hizlaniyor, ama halen yavas. Yani siz ekran kartiniza 100000
tane nokta yolluyorsunuz diyelim. Ancak bunlardan sadece 1000 tanesi
kameranizin icinde. Ekran karti sadece bu 1000 tanesinin cizmek icin
vakit harcasa bile siz bir suru gereksiz noktayi ekran kartiniza
yolladiniz bile. Ve iste bu yuzden yavasssss calisiyor oyun.
Amma uzattim, sonucta ekranda
cizilmeyecek nesneleri ekran kartina gondermememiz gerekiyor. Bunun
da adi frustum culling (Turkcesini bilen/uydurabilen beri
gelsin).
Frustum culling kamera ile ilgili.
Kameranizin nereyi gordugunu bir sekilde bilmeniz gerekiyor. O zaman
bu isi de kameramiza otomatik olarak yaptirabilsek guzel olur. Burada
OpenGL, Direct3D, vs'den bagimsiz, her ikisinde de calisabilecek bir
kamera sinifi yapacagiz. Ozetle yazacagimiz siniflar sunlar;
XCamera:
Kamera parametrelerimizi tutacak ve guncelleyecek, frustum culling
isi ile ilgilenecek.
XVector3D:
Vektor sinifi. Bununla ilgili hicbirseyden bahsetmeyecegim, iyi bir
is cikartmaya calisiyorsaniz coktan (en basta) bir vektor sinifi
yazmissinizdir. Her yerde lazim.
XPlane:
Bir duzlem belirtecek, kolaylik olsun diye, baska yerlerde de
isinize yarar.
XSphere:
Cizecegimiz nesnelerin kapladigi minimum kureyi tanimlayan sinif.
Burada hemen bir parantez aciyorum.
Culling islemi icin kureleri kullaniyoruz. Bir kurenin sadece merkezi
ve yaricapini bilerek basit ve hizli testlerle nesnenin kameranin
gorme alani disinda olup olmadigini anlamak mumkun. Nesnenin 1000
tane poligonunu test etmek yerine bu kure testi bize baya bi zaman
kazandirir. Baslamisken tersten gidip once bu sinifi anlatalim.
class XSphere
{
float m_radius;
XVector3D m_center;
XVector3D m_localCenter;
public:
XSphere(void);
virtual ~XSphere(void);
//! Yaricapi donduruyor
const float GetRadius()const{return m_radius;};
//! Yaricapi kaydediyor
void SetRadius(float radius){m_radius = radius;};
//! Lokal merkezi donduruyor
const XVector3D& GetLocalCenter() const {return m_localCenter;};
//! World Space'de merkezi donduruyor
const XVector3D& GetWorldCenter() const {return m_center;};
//! Lokal merkezi kaydediyor
void SetLocalCenter(const XVector3D& center){m_localCenter = center;};
void Merge(const XSphere& sphere);
void Transform(XMatrix4& trans);
};
XSphere::Merge fonksiyonundan bu yazida hic bahsetmeyecegim. Nesneniz
birden fazla alt nesneden olusuyorsa herbirine bir kure atamak ve bu
kureleri birlestirmek icin Merge islemi kullaniliyor. Fazla
karisiklik yaratmamak icin geciyorum. Bu siniftaki en onemli nokta
iki ayri merkezimizin olmasi. Birisi object space'de (nesne
uzayinda), digeri ise world space'de. Nesnelerimizi object
space'de tuttugumuz icin merkezlerini ancak bu uzayda bulabiliriz.
Ancak kameramiz world space'de oldugu icin karsilastirma islemini de
ancak world space'de yapabiliriz. Bu yuzden merkezimizi
XSphere::Tansform fonksiyonu ile her turda bu uzaya cevirmemiz
gerekiyor. Fonksiyonun yaptigi is tahmin edebileceginiz gibi
matris-vektor carpimi. O anki model matrisi ile carpiyoruz. Buradaki
onemli nokta, beni bir hafta kadar ugrastiran minik bilgi kirintisini
da yazayim. Bu fonksiyona gelen matris o anki MODELVIEW matrisi
degil. Ne peki? Ben her nesne icin kendi transform matrislerini
tutuyorum, yani glTranslate/glRotate kullanmak yerine matrisi kendim
yaratip glMultMatrix ile transformasyonu gerceklestiriyorum. Iste bu
matris o matris. Yani benim nesnemin yerini belirleyen matris. O
matrisle carpmak dogal olarak nesnenin tum koordinatlarini ve kuremi
world space'e tasimis oluyor. Biraz karisik ama malesef boyle. (scene
graph hiyerarsisi icin boyle olmasi gerekiyor). Kahve molasi..
Neredeyse merkez ve yaricapi nasil
buldugumuzu anlatmayi unutuyordum. Cok kolay aslinda, herkesin
nesnenin koordinatlarini tuttugu veri yapisi farkli oldugundan buraya
eklemedim o kodu. Tum nesne koordinatlarinin minimum ve maksimum x,
y, z degerlerini buluyorum. Bu minimum ve maksimum noktalari nesnenin
icinde bulundugu minumum diktortgenler prizmasini tanimlar degil mi?
Biraz dusunun, evet.. Bu iki noktanin tam ortasinda merkezimiz olur.
Yaricap icin de yine tum noktalarin merkeze uzakligini hesaplayip
maksimum degeri yaricap olarak atariz. Farkettiyseniz burda binlerce
carpma bolme var, o yuzden bunu en basta bir kez hesapliyoruz ve bir
daha hic hesaplamiyoruz. (Agirlik merkezini bulmak da merkez icin bir
yontem ama bence hatali).
Gelelim XPlane sinifina. Bir duzlemi
bir nokta ve duzlemin normali ile tanimlayabiliriz. Duzlem
fonksiyonumuz Ax + By + Cz = D ise normalimiz XVector3D(A, B, C) ve D
degerini tutarak bir duzlemi tanimlayabiliriz. Iste XPlane sinifinin
prototipi;
class XPlane
{
XVector3D m_Normal;
float m_Constant;
public:
float DistanceTo (const XVector3D& pnt) const ;
XPlane(void);
~XPlane(void);
};
Yaptigi pek enteresan birsey yok, normal ve bir sabit deger
(m_Constant = D) tutuyor sadece. Bir de DistanceTo fonksiyonu var, bu
fonksiyon da herhangi bir noktanin bu duzleme uzakligini hesapliyor.
Basit bir dot carpimi ama yine de buraya ekliyorum kodunu.
float XPlane::DistanceTo (const XVector3D& pnt) const
{
return m_Normal.Dot(pnt) - m_Constant;
}
Ve nihayet Kamera sinifina geldi sira.
Iste prototipi, Get/Set metodlarini kafa karistirmamak icin kaldirdim
icinden.
class XCamera
{
protected:
enum XFRUSTUMSIDE
{
XRIGHT = 0, // The RIGHT side of the frustum
XLEFT = 1, // The LEFT side of the frustum
XBOTTOM = 2, // The BOTTOM side of the frustum
XTOP = 3, // The TOP side of the frustum
XNEAR = 4, // The NEAR side of the frustum
XFAR = 5 // The FAR side of the frustum
};
XVector3D m_UpVect;
XVector3D m_PosVect;
XVector3D m_ViewVect;
XVector3D m_LeftVect;
float m_FrustumNear, m_FrustumFar,
m_FrustumLeft, m_FrustumRight,
m_FrustumTop, m_FrustumBottom;
XPlane m_WorldPlane[6];
float m_CoeffL[2], m_CoeffR[2], m_CoeffB[2], m_CoeffT[2];
public:
//! Default constructor
XCamera();
//! Destructor
virtual ~XCamera();
bool SphereInFrustum(const XSphere& sphere);
protected:
// update callbacks
virtual void OnFrustumChange ();
virtual void OnFrameChange ();
};
Hemen en bastan hizlica gecelim. Bastaki
enum tahmin edebileceginiz gibi frustum'u tanimlayan yuzeyler
icin. Boylelikle kod daha okunakli olacak.
m_UpVect,
m_PosVect, m_ViewVect, m_LeftVect kameramizin pozisyonunu ve baktigi
yonu belirleyen vektorler. Ilk ucunu gluLookAt'e yollarken de
kullanacagiz. Sonraki m_FrustumX degiskenleri de glFrustum komutuna
yolladigimiz frustum parametreleri. Bunlari PROJECTION matrisini
belirlemek icin kullaniyoruz. Genelde her programda en az bir kere ve
cogunlukla sadece bir kere bu glFrustum (veya gluPerspective ayni isi
yapiyor) fonksiyonunu cagiririz. m_WorldPlane kameramizin gordugu
alani belirleyen alti duzlemi tanimliyor. Sag, sol, alt, ust, on ve
arka yuzeyler. Ve iste bu duzlemleri dogru bir sekilde
hesaplayabilirsek kuremizi bu yuzeylerle karsilastirip kameranin
nesnemizi gorup gormedigini anlayabilecegiz. Iste SphereInFrustum
fonksiyonu bu isi yapiyor. Hemen bu fonksiyonu yazalim;
bool XCamera::SphereInFrustum(const XSphere& sphere)
{
XVector3D w = sphere.GetWorldCenter();
float r = sphere.GetRadius();
for (int i = 0; i < 6; i++)
{
if(m_WorldPlane[i].DistanceTo(w) <= -r)
return false;
}
return true;
}
Yine baya basit bir
fonksiyon bence, kuremizin merkez (dikkat! world space) ve yaricapini
aliyoruz. Kameranin 6 duzlemi ile karsilastiriyoruz. Merkez noktasi
duzlemlerden herhangi birinin arkasinda ve kurenin yaricapindan daha
uzakta ise bu nesneyi kamera gormuyordur.
Gelelim sondaki iki
fonksiyona. Nihayet, iki onemli fonksiyon. OnFrustumChange, frustum
degistigi zaman, OnFrameChange de kameramizin yeri degistigi zaman
cagiriliyorlar. Daha sonra bu cagirilma mekanizmasi icin de kendi
kullandigim yontemden bahsedecegim biraz.
OnFrustumChange
fonksiyonu normalde sadece bir kez cagiriliyor en basta. Matematiksel
detaya girmeyecegim. Kameranin bize yakin duzlemdeki dort kosesi icin
ikiser deger hesapliyoruz ve bu degerleri duzlemleri bulurken
kullanacagiz az sonra.
void XCamera::OnFrustumChange()
{
float fNSqr = m_FrustumNear*m_FrustumNear;
float fLSqr = m_FrustumLeft*m_FrustumLeft;
float fRSqr = m_FrustumRight*m_FrustumRight;
float fBSqr = m_FrustumBottom*m_FrustumBottom;
float fTSqr = m_FrustumTop*m_FrustumTop;
float fInvLength = (float)(1.0/sqrt(fNSqr + fLSqr));
m_CoeffL[0] = m_FrustumNear*fInvLength;
m_CoeffL[1] = -m_FrustumLeft*fInvLength;
fInvLength = (float)(1.0/sqrt(fNSqr + fRSqr));
m_CoeffR[0] = -m_FrustumNear*fInvLength;
m_CoeffR[1] = m_FrustumRight*fInvLength;
fInvLength = (float)(1.0/sqrt(fNSqr + fBSqr));
m_CoeffB[0] = m_FrustumNear*fInvLength;
m_CoeffB[1] = -m_FrustumBottom*fInvLength;
fInvLength = (float)(1.0/sqrt(fNSqr + fTSqr));
m_CoeffT[0] = -m_FrustumNear*fInvLength;
m_CoeffT[1] = m_FrustumTop*fInvLength;
}
OnFrameChange fonksiyonu kameranin bulundugu yer veya baktigi nokta
degistiginde cagiriliyor. Sonucta kamerayi hareket ettirdigimizde
kamera frustumu da degisir (yani alti adet duzlem). Assagida bu alti
duzlemi hesapliyoruz iste.
void XCamera::OnFrameChange()
{
float fDdE = m_ViewVect.Dot(m_PosVect);
// left plane
m_WorldPlane[XLEFT].Normal() = m_LeftVect*m_CoeffL[0] +
m_ViewVect*m_CoeffL[1];
m_WorldPlane[XLEFT].Constant() =
m_PosVect.Dot(m_WorldPlane[XLEFT].Normal());
// right plane
m_WorldPlane[XRIGHT].Normal() = m_LeftVect*m_CoeffR[0] +
m_ViewVect*m_CoeffR[1];
m_WorldPlane[XRIGHT].Constant() =
m_PosVect.Dot(m_WorldPlane[XRIGHT].Normal());
// bottom plane
m_WorldPlane[XBOTTOM].Normal() = m_UpVect*m_CoeffB[0] +
m_ViewVect*m_CoeffB[1];
m_WorldPlane[XBOTTOM].Constant() =
m_PosVect.Dot(m_WorldPlane[XBOTTOM].Normal());
// top plane
m_WorldPlane[XTOP].Normal() = m_UpVect*m_CoeffT[0] +
m_ViewVect*m_CoeffT[1];
m_WorldPlane[XTOP].Constant() =
m_PosVect.Dot(m_WorldPlane[XTOP].Normal());
// far plane
m_WorldPlane[XFAR].Normal() = -m_ViewVect;
m_WorldPlane[XFAR].Constant() = -(fDdE + m_FrustumFar);
// near plane
m_WorldPlane[XNEAR].Normal() = m_ViewVect;
m_WorldPlane[XNEAR].Constant() = fDdE + m_FrustumNear;
}
Bu kadar. Bitmistir. Alti adet kamera
duzlemimizi hesapladik, nesnemizi cevreleyen kureyi bulduk, bunlari
karsilastirip cizip cizmememiz gerektigine karar verdik.
Farkettiyseniz hic OpenGL komutu kullanmadik. Ben bu kamera sinifinin
ustune bir de XGLCamera sinifi turettim. virtual tanimli olan
OnFrustumChange ve OnFrameChange'i ise soyle yeniden yazdim;
/*!
Call this function to update the frustum if you reimplement this class.
*/
void XGLCamera::OnFrustumChange ()
{
XCamera::OnFrustumChange();
// set projection matrix
glMatrixMode(GL_PROJECTION);
glLoadIdentity();
glFrustum(m_FrustumLeft, m_FrustumRight, m_FrustumBottom,
m_FrustumTop, m_FrustumNear, m_FrustumFar);
}
/*!
Call this function to update the view if you reimplement this class.
*/
void XGLCamera::OnFrameChange ()
{
XCamera::OnFrameChange();
// set view matrix
glMatrixMode(GL_MODELVIEW);
glLoadIdentity();
XVector3D LookAt = m_PosVect + m_ViewVect;
gluLookAt(m_PosVect.x, m_PosVect.y, m_PosVect.z,
LookAt.x, LookAt.y, LookAt.z,
m_UpVect.x, m_UpVect.y, m_UpVect.z);
}
Bu siniftan yeni
kamera siniflari turetmek de size kalmis. Sadece kameranizi her
hareket ettirdiginizde OnFrameChange'i cagirmayi unutmayin.
Hemen birkac not;
Bunlari
kafamdan bulmadim tabi ki, Dave Eberly'nin 3D Game Engine Design
kitabindan alinma bir yontem. Kod oldukca modifiye ve kitap ile
gelen kod acik ama yine de kullanirken kodunuzun basinda adamdan
bahsederseniz iyi olur bence.
Alternatif yontem olarak
www.gametutorials.com
adresinde de bir frustum culling kodu var. Once onunla ugrastim,
kendi hiyerarsik yapimin icine bir turlu yerlestiremedim nedense. Ve
OpenGL'e bagimli bir kod idi o. Kabaca her frame'de
OpenGL'den MODELVIEW ve PROJECTION matrislerini geri alip bunlari
carpip 6 duzlemi hesapliyordu. OpenGL'e bagimliligi ve durmadan bu
matrisleri geri almasi hosuma gitmedi. Bir baska yerde (OpenGL.org
sanirim) bu matrisleri her framede geri almanin performansi
etkileyebilecegi yaziyordu.
Bana ulasmak icin
mentat@cfxweb.net adresini
kullanabilirsiniz. Umarim yazdiklarim bir isinize yarar.
mentat, 01.01.2003
(aa yeni yil!)
|