Prosba o przetestowanie poczatkow frameworka/engine'a

[Sebastian]

FPS: ~2600, ~5600 bez podłogi
2x HD3870, Q6600

[Mr. Spam]

[Syriusz]

GeForce 9800 GT
Pentium Core2Duo 2,53
Vista
normalnie 2446
bez podłogi 5945
bez niczego 6300

[soku11]

Mam pytanie odnosnie tych drzew osemkowych, bo chyba nie za bardzo to rozumiem... Majac swoja mape z jakimis modelami(obiektami x lub zwyklymi) musze w jakis sposob znalezc rozmiar calej mapy, tak by objac ja szescianem. Pozniej dziele ten szescian na 8, i tak dalej... Pierwsze pytanie - czy obszar dzieli sie tylko raz, czy co klatke ?? Drugie pytanie - dokad mam to tak dzielic ?? Trzecie pytanie - co takie drzewo ma w sobie przechowywac?? Czwarte pytanie - jak majac pozycje kamery i kierunek w ktory sie patrze odrzucac te zbedne geometrie ?? Z gory dziekuje za jakies wyjasnienia, ewentualnie link do artykulu gdzie jest to opisane pod wzgledem programowania takich map... Pozdrawiam.

[Reg]

1. Tylko raz. Co klatkę to marnowanie czasu. Jeśli obiekty są nieruchome, nowe nie przybywają, nie są usuwane, nie zmieniają rozmiaru (słowem - są statyczne), to podziel raz, na początku i potem korzystaj z tego drzewa. Jeśli są dynamiczne, to musisz dopisać funkcję wstawiania i usuwania obiektów z istniejącego drzewa, najlepiej z automatycznym rozbijaniem i łączeniem węzłów - nieproste, ale da się zrobić. Z resztą na początek tego nie musisz robić.

2. Proponuję zatrzymać rekurencyjne dzielenie, kiedy spełniony jest co najmniej jeden z tych warunków:
a) Rekurencja osiągnęła pewną głębokość (np. 6 czy 8 poziomów).
b) Liczba obiektów w bieżącym węźle (tym co byśmy go ewentualnie dalej podzielili) jest już mała, np. 16.

3. Co chcesz :) Najlepiej wskaźniki do tych obiektów albo jakieś inne odniesienia do nich.

4. Musisz opisać kształt pola widzenia kamery frustumem, czyli taką bryłą co ma taki kształt, jak pole widzenia takiej kamery :) A potem testować kolizję, czyli sprawdzać specjalną magiczną funkcją matematyczną, czy frustum przecina się z prostopadłościanem opisującym dany węzeł drzewa. Jeśli tak, to wchodzimy do tego węzła, rysujemy zgromadzone w nim obiekty i testujemy frustum dalej rekurencyjnie z jego podwęzłami. Jeśli nie, to cały ten węzeł razem z podwęzłami ignorujemy. Zobacz mój artykuł:
http://www.warsztat.gd/articles.php?x=view&id=279

[soku11]

Dzieki wielkie juz mi troche rozjasniles :) Artykul na pewno nie omieszkam przeczytac.
Jeszcze mi tak w miedzyczasie pojawilo sie jedno pytanko.
Zalozmy, ze mapa to tylko zwykly dlugi plane, np. 500x10. Wtedy dzielac przestrzen co kawalek na 8 (majac najpierw szescian w srodku plane'a o boku dlugosci 500) otrzymuje puste wezly. Rozumiem, ze tez wypada je przechowywac, tylko beda mialy poprostu pusta tablice/wektor obiektow statycznych do wyswietlenia. Jednak wskazniki na plane'a beda istnialy w kilku wezlach. Jak sobie wtedy poradzic z renderingiem tak, zeby rysowac tylko raz jeden obiekt ?? Czy zrobic cos na ksztalt 'ogolnej' tablicy, do ktorej bym co klatke wrzucal widoczne elementy sprawdzajac, czy czasami nie jest on juz w niej umieszczony ??

Pozdrawiam.

[counterClockWise]

Dzieki wielkie juz mi troche rozjasniles :) Artykul na pewno nie omieszkam przeczytac.
Jeszcze mi tak w miedzyczasie pojawilo sie jedno pytanko.
Zalozmy, ze mapa to tylko zwykly dlugi plane, np. 500x10. Wtedy dzielac przestrzen co kawalek na 8 (majac najpierw szescian w srodku plane'a o boku dlugosci 500) otrzymuje puste wezly. Rozumiem, ze tez wypada je przechowywac, tylko beda mialy poprostu pusta tablice/wektor obiektow statycznych do wyswietlenia. Jednak wskazniki na plane'a beda istnialy w kilku wezlach. Jak sobie wtedy poradzic z renderingiem tak, zeby rysowac tylko raz jeden obiekt ?? Czy zrobic cos na ksztalt 'ogolnej' tablicy, do ktorej bym co klatke wrzucal widoczne elementy sprawdzajac, czy czasami nie jest on juz w niej umieszczony ??

Pozdrawiam.

W przypadku takiego "plane 500x10" octree nie jest optymalnym wyborem, ale rezygnując z np. drzewa ósemkowego na rzecz czegoś bardziej wyspecjalizowanego pod problem tracisz na ogólności - a co jeśli nagle będziesz chciał zmienić mapę?

Dla takiego przypadku proponuję:
a) zrezygnować ze struktury 3d (skoro to plane-płaszczyzna, to od drzewa ósemkowego lepsze byłoby czwórkowe).
b) Możesz zrobić takie drzewo:
- węzeł reprezentuje prostokątny obszar o boku (a,b) - zależność między a i b niezdefiniowana
- każdy węzeł, który nie jest liściem ma 4 dzieciaki
- każdy węzeł, który nie jest korzeniem ma 1 rodzica
- Jeśli węzeł ma prostokąt o środku [x,y] i długości boków (a,b) to dzieci mają środki [x +- a/4, y +- b/4] i boki (a/2, b/2)

[soku11]

Czyli w przypadku takim bardziej 'plaskim' stosujac to drzewo ma ono byc takie nieregularne ?? W sensie, ze majac wspomnianego wczesniej 'plane 500x10' oraz obok niego jakiegos boxa, to najpierw ograniczam obie te geometrie, a pozniej dziele na dwie czesci jedna dla boxa a jedna dla plane'a ?? Pozdrawiam.

[Reg]

Jeśli przestrzeń sceny nie jest w miarę sześcienna tylko raczej płaska, to zamiast octree rozważ użycie innej struktury danych, np. quadtree - drzewa czwórkowego albo k-d tree - drzewa binarnego, które za każdym razem dynamicznie dobiera płaszczyznę podziału.

Natomiast jeśli dobrze rozumiem że pytasz o problem kiedy obiekt nie mieści się w całości w jednym z podwęzłów, bo jest duży albo leży na granicy, to możesz to rozwiązać na dwa sposoby:

1. (Ja preferuję ten) Umieszczasz obiekt w węźle nadrzędnym, w tym w którym mieści się w całości wewnątrz. Po prostu zakładasz, że nie tylko liście drzewa, ale każdy węzeł może posiadać listę obiektów które w nim leżą. To niczego nie komplikuje, a rozwiązuje problem.
2. Umieść wskaźnik do tego obiektu w każdym z podwęzłów, z którym się przecina. Wtedy podczas renderowania czy innego przechodzenia musisz sobie każdy obiekt jakoś zaznaczać (pole bool CzyOdwiedzone albo lepiej int NumerKlatkiWKtorejOdwiedzony), żeby go nie rozpatrywać dwa razy.

[soku11]

Wlasnie tak myslalem nad tym drugim rozwiazaniem, ale rzeczywiscie za duzo by bylo roboty z tym oznaczaniem itd. Tylko dalej cos mi sie ta pierwsza metoda nie podoba :/ Bo wedlug ciebie bede mial wskaznik na ten obiekt TYLKO w nadrzednym wezle. Tak wiec jak bede badal frustuma kamery i bedzie on miescil sie w mniejszych kwadratach, to przeciez obiekt ten nie bedzie widoczny 'nizej' w hierarchi... A jesli zrobic, ze kazdy taki wezel bedzie mial oddzilne wskazniki, to bede rysowal kilkakrotnie :/ Nie wiem czy ja cos zle mysle dzis, czy co :/

Jeszcze jedno pytanie dodatkowe:
Jak bedzie teraz wygladac renderowanie ?? Zalozmy, ze mam juz podzielony caly obszar i kazdy wezel ma wskazniki na dane obiekty w nim widoczne. Teraz jesli chce wyrysowac na ekranie cos z widoku danej kamery, to buduje sobie jej frustuma, a nastepnie przeszukuje od roota do lisci odrzucajac cale kwadraty geometrii. Jesli dany kwadrat jest we frustumie, to poprostu mam wyrenderowac wszystkie jego obiekty metoda render ?? Dobrze to rozumiem??

Reg karma ++ ile tam mam, bo naprawde duzo mi pomagasz :)
BTW. Zdaje mi sie, ze troche zeszlismy z tematu, takze prosilbym jakiegos moda o stworzenie nowego tematu o nazwie w stylu Quadtrees i wrzucenie tam postow dotyczacych tematu. Z gory dziekuje.
Pozdrawiam.

[Daro (RDG)]

GeForce 9800 GT
Pentium Core2Duo 2,53
Vista
normalnie 2446
bez podłogi 5945
bez niczego 6300

9600GT @ 730Mhz/1900Mhz/2050Mhz
Athlon 64 X2 5200XP+ @ 2.78Mhz
XP SP3
normalnie 2700
bez niczego 7000

Vista ścina osiągi kart ...  :(

[Reg]

Wlasnie tak myslalem nad tym drugim rozwiazaniem, ale rzeczywiscie za duzo by bylo roboty z tym oznaczaniem itd. Tylko dalej cos mi sie ta pierwsza metoda nie podoba :/ Bo wedlug ciebie bede mial wskaznik na ten obiekt TYLKO w nadrzednym wezle. Tak wiec jak bede badal frustuma kamery i bedzie on miescil sie w mniejszych kwadratach, to przeciez obiekt ten nie bedzie widoczny 'nizej' w hierarchi... A jesli zrobic, ze kazdy taki wezel bedzie mial oddzilne wskazniki, to bede rysowal kilkakrotnie :/ Nie wiem czy ja cos zle mysle dzis, czy co :/

Jeszcze jedno pytanie dodatkowe:
Jak bedzie teraz wygladac renderowanie ?? Zalozmy, ze mam juz podzielony caly obszar i kazdy wezel ma wskazniki na dane obiekty w nim widoczne. Teraz jesli chce wyrysowac na ekranie cos z widoku danej kamery, to buduje sobie jej frustuma, a nastepnie przeszukuje od roota do lisci odrzucajac cale kwadraty geometrii. Jesli dany kwadrat jest we frustumie, to poprostu mam wyrenderowac wszystkie jego obiekty metoda render ?? Dobrze to rozumiem??

Tak, źle myślisz. Procedura do renderowania obiektów z drzewa z użyciem frustum culling wygląda tak:

Kod: [Zaznacz]

function RenderujDrzewo()
{
  RenderujWęzeł(Korzeń);
}

function RenderujWęzeł(węzeł)
{
  foreach (Obiekt "obj" z listy obiektów w tym węźle)
    obj.Renderuj();
  foreach (Węzeł "podwęzeł" z listy podwęzłów tego węzła)
    if (Frustum przecina podwęzeł.AABB)
      RenderujWęzeł(podwęzeł);
}

[soku11]

Napisz jak mozesz czy dobrze zrozumialem:
Tworze drzewo i zapisuje w kazdym z jego wezlow i lisci obiekt, ktory sie miesci w nim maksymalnie. Czyli majac np. teren jako cala mape bedzie sie on znajdywal w korzeniu. a obiekty malutkie beda w lisciach, a te srednie gdzies w innych wezlach.
Troche trudno bedzie napisac to zeby tak sie ladnie posegregowalo, no ale sprobuje. Bo to pewnie trzeba poznajdowac ograniczajacy box dla kazdego obiektu i go wrzucac dopiero do drzewa. Wniosek - najpierw stworzyc drzewo ??
I rzeczywiscie dla tego sposobu ten pseudokod by sie sprawdzal :) Jeszcze tylko pytanie - co to jest AABB ?? Nigdy o czyms takim nie slyszalem :) Pozdrawiam.

BTW. Co prawda mam odzielny temat o Quad/Octrees, no ale...

[voytech]

AABB - axis-aligned bounding box, czyli takie bryły, których płaszczyzny ograniczające są prostopadłe do osi współrzędnych.