Kamera ve Frustum Culling

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;

  1. 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.

  2. 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.

  3. Bana ulasmak icin mentat@cfxweb.net adresini kullanabilirsiniz. Umarim yazdiklarim bir isinize yarar.


mentat, 01.01.2003 (aa yeni yil!)





Bu yazının bulunduğu site: OyunYapimi.org
http://www.oyunyapimi.org

Bu yazı için adres:
http://www.oyunyapimi.org/modules.php?name=Sections&op=viewarticle&artid=20