Ładowanie
popup

Przyspieszanie Frustum Culling

2010-12-01 15:37:00

Dziś mały tip o optymalizacji Frustum Culling(zdefiniowany jest na 6 płaszczyznach) dla OBBox i AABBox (Prostopadłościan dowolnie zorientowany i 'wyrównany' do osi układu współrzędnych). Zacznę od struktury boxów:

class AABBox{ Vec3f min; // maksymalne wartości dla każdej z osi Vec3f max; // minimalne wartości dla każdej z osi }; class OBBox{ Vec3f center; // środek prostopadłościanu Vec3f axis[3]; // wektory opisujące układ współrzędnych Vec3f size; // długośći dla każdej z osi };

Najprostszym sposobem na sprawdzenie zawierania takich boxów w frustumie jest sprawdzenie zawierania każdego z jego wierzchołków dla każdej z 6 płaszczyzn frustuma. Żeby to troszkę przyspieszyć wyznaczam jeden wierzchołek (punkt p), który jest "najdalej" wysunięty względem normalnej danej płaszczyzny i sprawdzam relację tego punktu względem tej płaszczyzny. Jeśli dany wierzchołek znajduje się "nad" płaszczyzną - box znajduje się w zasięgu widzenia. Większość tego typu implementacji np. http://www.lighthouse3d.com/opengl/viewfrustum/index.php?gatest3 oblicza niepotrzebnie czy box przecina się z płaszczyzną - co narzuca niepotrzebny drugi test punkt-płaszczyzna i jest w większości przypadków niepotrzebne.

Wyliczanie punktu p dla AABBox:

// aabb - nasz box // normal - normalna płaszczyzny Point3f p=aabb.min; if(normal.x>=0) p.x=aabb.max.x; if(normal.y>=0) p.y=aabb.max.y; if(normal.z>=0) p.z=aabb.max.z;

Wyliczanie punktu dla OBBox:

// obb - nasz box // normal - normalna płaszczyzny // definiuje punkt poczatkowy (bedziemy go przesuwac wzgledem kazdej osi o odpowienie wartosci) Point3f p=obb.center; for(int i=0;i<3;++i){ float d=obb.axis[i]^normal; // projekcja normalnej wzdluz tej osi (operator ^ wykonuje iloczyn skalarny) // jesli d jest mniejsze od 0 - szukany punkt jest po negatywnej stronie danej osi (-axis[i]) if(d>0.f) p+=obb.axis[i]*obb.size[i]; else p-=obb.axis[i]*obb.size[i]; }

Dysponując takim punktem p, wystarczy sprawdzić czy znajduje się on "nad" płaszczyznami frustuma. Przykładowy kod sprawdzający:

// dla każdej płaszczyzny frustuma: for(int i=0;i<6;++i){ // m_planes - tablica z płaszczyznami if(!m_planes[i].Distance(p)>0) // sprawdzam czy punkt p znajduje się nad płaszczyzną return false; // jeśli nie - box napewno jest niewidoczny (można przerwać sprawdzanie) } return true;

Wykonałem prosty programik testowy, gdzie można sobie sprawdzić działanie tego kodu: frustm.culling.2.zip

Demo Frustum Culling...
Demo Frustum Culling...

Jak widać na tym screenie - przyrost wydajnosci jest, ale oczywiście nie ma większego sensu się bawić w takie optymalizacje - chyba że "dla sportu" ;)

Tagi: Programowanie Engine Optymalizacja | Komentarze (1)

Jak (nie) optymalizować kodu #1

2009-10-18 01:22:00

Pierwszą próbą optymalizacji bylo użycie FPU (czyli jednostka zmiennoprzecinkowa CPU) do zbudowania funkcji zastepujacych odpowiedniki z cmath. Pierwsze testy w trybie debug z domyslnymi ustawieniami wygladaly bardzo pozytywnie. Liczyłem w pętli kilka operacji, uzywajac odpowiednio funkcji z biblioteki standardowej cmath i z moich funkcji z uzyciem FPU. Czasy moich funkcji byly około 3 razy krótsze. Po włączeniu optymalizacji w kompilatorze - /fp:fast i /Oi (ten przełacznik włącza wstawianie instrinsic-ów w miejsce niektórych funkcji, w tym wiekszości tych z cmath) czasy moich funkcji byly juz tylko 2 razy krotsze. Po przełączeniu do trybu release stało sie to czego sie spodziewałem(?), cmath był szybszy... o wiele. Opcje /fp:precise i /Ox dały od kilku do kilkusetkrotne przyspieszenie. Nie pomogło też wstawienie do funkcji __forceinline. Przełączyłem więc się na podgląd instrukcji Asemblera. Hmm... kod dla funkcji z cmath nie byl wogóle generowany (nadal mowa o trybie Release). Stąd takie kosmiczne czasy ;) Rozwiązaniem tego 'problemu' jest wyłączenie optymalizacji (C++/Optimalization/Optimalization=Disabled (/Od)) lub zmiana sposobu mierzenia obliczeń. Dla przykładu w takim kodzie NIE zostanie wywolana funkcja sqrt:

float x=std::sqrt(xxx); x=sth;

kompilator zapewne ufa że brak wywołania funkcji sqrt nie spowoduje jakiegoś błedu w dalszych obliczeniach, bo za chwile w miejsce zmiennej x zostanie zapisana nowa wartość. Więc na przykład taka metoda mierzenia wydajności jest chyba bez sensu:

TIMER_START; for(int i=0;i<99999;++i){ xx3=std::sqrt(rrr); rrr+=0.56f; } TIMER_END;

Zmiana ustawień kompilatora moze spowodować że wyniki będa troche niesprawiedliwe. Pozostaje zmiana metody mierzenia. Ustawiem spowrotem opcje (C++/Optimalization/Optimalization=Full Optimization (/Ox)). Trzeba zmusic kompilator do uruchomienia funkcji z cmath. Kod:

float sth=...; TIMER_START; for(int i=0;i<99999;++i){ xx3=std::sqrt(rrr); sth+=xx3; // np. tak rrr+=0.56f; } TIMER_END;

Dodałem zmienna sth ktora będzie zainteresowana wynikiem funkcji std::sqrt. Ale to za mało nadal funkcja sqrt nie bedzie wywołana, ba - wogóle cała pętla będzie 'wyrzucona'. Działanie programu nie zmieni sie czy będzie ta pętla czy nie. Wystarczy wypisac dalej printf("%f",sth) i juz działa... Swoją drogą spryciarz z tego kompilatora :) Ostateczne pomiary sa pozytywne:

fpu_math time= 0.004849s cmath time= 0.005963s fpu_math time= 0.004900s cmath time= 0.010668s fpu_math time= 0.001266s cmath time= 0.002462s ...

Ostatecznie można powiedzieć że przyspieszenie jest, choć nie wiem czy to wszystko warte zachodu (dla satysfakcji można duzo zrobic) :P Jeszcze dodam kilka przykładów funkcji których użyłem w teście jak kogoś to interesuje (w komentarzach bardziej złożonych funkcji opisałem zawartości stosu):

float Cosf(float x) { __asm { fld x fcos } } float Sqrtf(float x) { __asm { fld x fsqrt } } // oszczedze miejsce (wiekszosc wyglada jak powyzsze) :) i podam dalej tylko te trudniejsze do napisania: float Powf(float x,float y) { __asm { fld y fld x fyl2x ;log2(x)*y fst st(1) ;log,log frndint ;int(log),log fxch st(1) fsub st(0),st(1) ;float(log),int(log) f2xm1 ;2^float(log)-1,int(log) fld1 faddp st(1),st(0) ;2^float(log),int(log) fscale ;2^int(log)*2^float(log) } } float Expf(float x) { // exp(x) == e^x __asm { ;y==e fld x fld GE_E fyl2x ;log2(x)*y fst st(1) ;log,log frndint ;int(log),log fxch st(1) fsub st(0),st(1) ;float(log),int(log) f2xm1 ;2^float(log)-1,int(log) fld1 faddp st(1),st(0) ;2^float(log),int(log) fscale ;2^int(log)*2^float(log) } } float Logf(float x) { // ln(x) (naturalny!) __asm { fld1 fld x fyl2x ;log2(x) fldl2e ;log2(e) fdivp st(1),st(0) } } float Log10f(float x) { __asm { fld1 fld x fyl2x ;log2(x) fldl2t ;log2(10) fdivp st(1),st(0) } }

Dodatkowo funkcje których nie ma w standardowej bibliotece matematycznej, a mogą sie przydać jak ktoś sie interesuje tematem :) :

void Sincosf(float x,float *oSin,float *oCos) { // sinus i cosinus od x __asm { mov eax,oSin mov edx,oCos fld x fsincos fstp dword ptr[edx] fstp dword ptr[eax] } } float Log2f(float x) { // log2(x) __asm { fld1 fld x fyl2x ; sciagnie sam st(1) } } float Logxf(float x,float y) { /* oblicza logarytm dowolnej podstawy: logx(y) sposob liczenia: logx(y)=log2(y)/log2(x) */ __asm { fld1 fld y fyl2x ;log2(y) zwija 1 ze stosu fld1 fld x fyl2x ;log2(x) zwija 1 ze stosu fdivp st(1),st(0) } }

Tagi: Programowanie C++ Optymalizacja Asembler Visual Studio | Dodaj komentarz