(i znowu sie zle poczulem, [w zwiazku z horror nudzaca
glupota ludzka], niewazne)

nigdy poki co nie robilem optymalizacji detekcji kolizji,
tylko troche sie zastanawialem ->

najprostsza wersja detekcji kolizji jest zlozonsci
n-kwadrat, ale defakto detekcja kolizji jest/moze byc
zlozonosci liniowej n-do-pierwszej,
trzeba tylko dane obiekty przestrzenne 'rejestrowac'
w jakiejs 'spacjalnej' strukturze (nazywam tu troche
dla zartu 'spacjalą kolizyjną', nie jest to zupelnie
od rzeczy nazywac strukture danych o charakterze
przestrzennym oddzielnym slowem np 'spacjala' bo to
doprecyzowuje i pomaga)


wezmy np wspominane kulki 2d
[wczesniej zle napisalem ze maja srednice 5 pix, maja
promien 5 pix a srednice 10 pix, (i kolizja nastepuje tez
przy dist <= 10 pix],

w tym wypadku tak naprawde nawet mozna by uzyc samego
rambufora z obrazem okna (jesli pixel == czarny nic nie ma,
jesli kolor to kolizja) ale jest to może trcohe brzydkie
i pozatym nie podaje informacji o indeksie tego z czym sie
zderzamy (czyli przyspieszenie jest polowiczne)

nalezaloby utworzyc odzielną 'spacjalę' i pytanie brzmi
'dokladnie jak?'

o ile pileczka ma 10 pix srednicy a okno powiedzmy rozmiar
500x400 (lub tez i jakis inny), dana komorka w takiej spacjali
powinna miec rozmiar gdzies tak pewnie 30pix x 30pix (ale
dokladnie ile?) Sa tez dwie opcje czy te komorki powinny
przylegac ale sie nie nakladac (wtedy niezrecznie trzebaby
czasem sprawdzac jedna komorke a czasem cztery) czy tez
powinny sie nakladac w taki sposob by zawsze mozna sprawdzac
tylko jedna komorke, za to przy ruchu przedmiotu trzebaby
uzupelniec informacja kilka komorek na raz

a moze jednak komorki powinna miec dokladnie 10x10 pix
i nie nakladac sie, to sie wydaje moze najprostsze?

jakies uwagi ntt?






--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

Dnia 08-12-2011 o 20:00:49 fir <f...@w...gazeta.pl> napisał(a):

> (i znowu sie zle poczulem, [w zwiazku z horror nudzaca
> glupota ludzka], niewazne)
>
> nigdy poki co nie robilem optymalizacji detekcji kolizji,
> tylko troche sie zastanawialem ->
>
> najprostsza wersja detekcji kolizji jest zlozonsci
> n-kwadrat, ale defakto detekcja kolizji jest/moze byc
> zlozonosci liniowej n-do-pierwszej,
> trzeba tylko dane obiekty przestrzenne 'rejestrowac'
> w jakiejs 'spacjalnej' strukturze (nazywam tu troche
> dla zartu 'spacjalą kolizyjną', nie jest to zupelnie
> od rzeczy nazywac strukture danych o charakterze
> przestrzennym oddzielnym slowem np 'spacjala' bo to
> doprecyzowuje i pomaga)
>
>
> wezmy np wspominane kulki 2d
> [wczesniej zle napisalem ze maja srednice 5 pix, maja
> promien 5 pix a srednice 10 pix, (i kolizja nastepuje tez
> przy dist <= 10 pix],
>
> w tym wypadku tak naprawde nawet mozna by uzyc samego
> rambufora z obrazem okna (jesli pixel == czarny nic nie ma,
> jesli kolor to kolizja) ale jest to może trcohe brzydkie
> i pozatym nie podaje informacji o indeksie tego z czym sie
> zderzamy (czyli przyspieszenie jest polowiczne)
>
> nalezaloby utworzyc odzielną 'spacjalę' i pytanie brzmi
> 'dokladnie jak?'
>
> o ile pileczka ma 10 pix srednicy a okno powiedzmy rozmiar
> 500x400 (lub tez i jakis inny), dana komorka w takiej spacjali
> powinna miec rozmiar gdzies tak pewnie 30pix x 30pix (ale
> dokladnie ile?) Sa tez dwie opcje czy te komorki powinny
> przylegac ale sie nie nakladac (wtedy niezrecznie trzebaby
> czasem sprawdzac jedna komorke a czasem cztery) czy tez
> powinny sie nakladac w taki sposob by zawsze mozna sprawdzac
> tylko jedna komorke, za to przy ruchu przedmiotu trzebaby
> uzupelniec informacja kilka komorek na raz
>
> a moze jednak komorki powinna miec dokladnie 10x10 pix
> i nie nakladac sie, to sie wydaje moze najprostsze?
>
> jakies uwagi ntt?

nie całkiem rozumiem Twój pomysł, ale chyba mi się nie podoba.

mój całkiem nieoptymalny kod analityczny (100 kulek, i czasem nie wyrabia)
wyglądał jakoś tak:
//szkic w notacji C#
delegate void Cont();
Pair<float,Cont>? findCollision(Ball a,Ball b);
//jeśli kulki się nie zderzają, to null,
//zwraca parę -- moment tego zderzenia, i procedurę modyfikująca stan
biorących udział w zderzeniu kulek, jeśli to zderzenie zajdzie
//jeśli mamy kulki a,b i c, to findCollision wołamy dla (a,b), (a,c) i
(b,c), możemy dostać od 0 do 3 procedur, ale wykonujemy najwyżej jedną --
dla pierwszego zderzenia,
//albowiem potem kulki lecą inna trasa, i pozostałe zderzenia są nieważne
(bo zakładają, że kulki lecą po niezmodyfikowanej trasie)
Pair<float,Cont>? zapCol=null;//najblizsza kolizja do wykonania,

w funkcji Update robilem cos takiego

T=now();
while(zapCol==null || zapCol.t<=T){
if(zapCol!=null){
zapCol.proc();
}
zapCol=null;//
Pair<float,Cont>? f=null;//właśnie znaleziona kolizja
for(int i=0;i<balls.length;i++){
f=null;
b=balls[i];
//tu byly testy kolizji ze scianami, pomijam dla czytelnosci
for(int j=0;j<i;j++){
a=balls[j];
f=findCollision(a,b);
if(zapCol==null || (f!=null && f.t<zapCol.t)){//jeśli znaleziona
kolizja jest bliższa w czasie niż zapamiętana
zapCol=f;//to będzie użyta
}
}
}
}

ale to robi O(n^2) dla każdej kolizji, można by znalezione kolizje (f)
zapamiętywać gdzieś, i invalidować tylko te, w których uczestniczyły kulki
dla wykonywanej (proc()) kolizji.

kod iteracyjny też się się da optymalizować, i ktoś się tym pewnie
zajmował, ale ja wolałem się pobawić analitycznym



--
Jordan Szubert

do góry

fir <f...@W...gazeta.pl> napisał(a):

> (i znowu sie zle poczulem, [w zwiazku z horror nudzaca
> glupota ludzka], niewazne)
>
> nigdy poki co nie robilem optymalizacji detekcji kolizji,
> tylko troche sie zastanawialem ->
>
> najprostsza wersja detekcji kolizji jest zlozonsci
> n-kwadrat, ale defakto detekcja kolizji jest/moze byc
> zlozonosci liniowej n-do-pierwszej,
> trzeba tylko dane obiekty przestrzenne 'rejestrowac'
> w jakiejs 'spacjalnej' strukturze

Przychodza mi do glowy dwa rozwiazania:
1) Jakas specjalna implementacja KD-Tree, tak aby uaktualnianie
obiektow dodanych wczesniej do KD-Tree mialo niski koszt.
2) Podzielic ekran na N kresek pionowych i M kresek poziomych.
Wyliczyc wsplrzedne skrzyzowan kresek. W kazdym przecieciu
wstawic liste. Potem kulke dodawac do listy w najblizszym
skrzyzowaniu. No i aby szukac kolizji, wystarczy przeszukac
kulki z kilku pobliskich skrzyzowan-list. Dodawanie do listy
to koszt O(1), usuwanie O(1), przegladanie kilku pobliskich
list to srednio... moze 2^D * X / N / M, gdzie X to ilosc kulek,
a D to ilosc wymiarow. Czyli dla 1000 kulek w 2D i podziale
ekranu na 100 kratek, mamy zlozonosc jednej "klatki fizyki"
1000 * 4 * 1000 / 100 = 40tys. Znacznie mniej niz X^2=1mln.
Pozdrawiam







--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

> > jakies uwagi ntt?
>
> nie ca=B3kiem rozumiem Tw=F3j pomys=B3, ale chyba mi si=EA nie podoba.
>
> m=F3j ca=B3kiem nieoptymalny kod analityczny (100 kulek, i czasem nie wy=
> rabia) =
>
> wygl=B1da=B3 jako=B6 tak:
> //szkic w notacji C#
> delegate void Cont();
> Pair<float,Cont>? findCollision(Ball a,Ball b);
> //je=B6li kulki si=EA nie zderzaj=B1, to null,
> //zwraca par=EA -- moment tego zderzenia, i procedur=EA modyfikuj=B1ca s=
> tan =
>
> bior=B1cych udzia=B3 w zderzeniu kulek, je=B6li to zderzenie zajdzie
> //je=B6li mamy kulki a,b i c, to findCollision wo=B3amy dla (a,b), (a,c)=
> i =
>
> (b,c), mo=BFemy dosta=E6 od 0 do 3 procedur, ale wykonujemy najwy=BFej j=
> edn=B1 -- =
>
> dla pierwszego zderzenia,
> //albowiem potem kulki lec=B1 inna trasa, i pozosta=B3e zderzenia s=B1 n=
> iewa=BFne =
>
> (bo zak=B3adaj=B1, =BFe kulki lec=B1 po niezmodyfikowanej trasie)
> Pair<float,Cont>? zapCol=3Dnull;//najblizsza kolizja do wykonania,
>
> w funkcji Update robilem cos takiego
>
> T=3Dnow();
> while(zapCol=3D=3Dnull || zapCol.t<=3DT){
> if(zapCol!=3Dnull){
> zapCol.proc();
> }
> zapCol=3Dnull;//
> Pair<float,Cont>? f=3Dnull;//w=B3a=B6nie znaleziona kolizja
> for(int i=3D0;i<balls.length;i++){
> f=3Dnull;
> b=3Dballs[i];
> //tu byly testy kolizji ze scianami, pomijam dla czytelnosci
> for(int j=3D0;j<i;j++){
> a=3Dballs[j];
> f=3DfindCollision(a,b);
> if(zapCol=3D=3Dnull || (f!=3Dnull && f.t<zapCol.t)){//
je=B6li znalezi=
> ona =
>
> kolizja jest bli=BFsza w czasie ni=BF zapami=EAtana
> zapCol=3Df;//to b=EAdzie u=BFyta
> }
> }
> }
> }
>
> ale to robi O(n^2) dla ka=BFdej kolizji, mo=BFna by znalezione kolizje (=
> f) =
>
> zapami=EAtywa=E6 gdzie=B6, i invalidowa=E6 tylko te, w kt=F3rych uczestn=
> iczy=B3y kulki =
>
> dla wykonywanej (proc()) kolizji.
>
> kod iteracyjny te=BF si=EA si=EA da optymalizowa=E6, i kto=B6 si=EA tym =
> pewnie =
>
> zajmowa=B3, ale ja wola=B3em si=EA pobawi=E6 analitycznym
>

moim zdaniem to co powyzej jest bardzo dziwne
bo nie trzeba sie tak wcale babrac z czasami itp

ja poki co uzywam tutaj

http://dl.dropbox.com/u/42887985/kulki2d.zip

tylko trywialnej 'kwadratowej' detekcji kolizji
(i to grubo bo kulek jest 200 ramek okolo 100/s
i fizyka jest 5x na ramke - czyli to leci 100tys
detekcji kolizji na sekunde)

klawisze: 't' wlacza tlumienie, spacja przelacza
grawitacje, 'z' wlacza pokazywanie wektorow predkosci
(ale nie jest to dokonczony programik (bo zrobilbym
wystrzeliwanie kulek mysza itd) tylko fragment do testu)

kolizji zreszta nie chce mi sie poprawiac (200 kulek starczy)
wolalbym dopracowac ta fizyke (bo jestem jej jakos niepewny/
niezadowolony) przed zaciemnieniem wszystkiego
optymalizacja kolizji


--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

M.M. <m...@N...gazeta.pl> napisał(a):

> fir <f...@W...gazeta.pl> napisał(a):
>
> > (i znowu sie zle poczulem, [w zwiazku z horror nudzaca
> > glupota ludzka], niewazne)
> >
> > nigdy poki co nie robilem optymalizacji detekcji kolizji,
> > tylko troche sie zastanawialem ->
> >
> > najprostsza wersja detekcji kolizji jest zlozonsci
> > n-kwadrat, ale defakto detekcja kolizji jest/moze byc
> > zlozonosci liniowej n-do-pierwszej,
> > trzeba tylko dane obiekty przestrzenne 'rejestrowac'
> > w jakiejs 'spacjalnej' strukturze
>
> Przychodza mi do glowy dwa rozwiazania:
> 1) Jakas specjalna implementacja KD-Tree, tak aby uaktualnianie
> obiektow dodanych wczesniej do KD-Tree mialo niski koszt.
> 2) Podzielic ekran na N kresek pionowych i M kresek poziomych.
> Wyliczyc wsplrzedne skrzyzowan kresek. W kazdym przecieciu
> wstawic liste. Potem kulke dodawac do listy w najblizszym
> skrzyzowaniu. No i aby szukac kolizji, wystarczy przeszukac
> kulki z kilku pobliskich skrzyzowan-list. Dodawanie do listy
> to koszt O(1), usuwanie O(1), przegladanie kilku pobliskich
> list to srednio... moze 2^D * X / N / M, gdzie X to ilosc kulek,
> a D to ilosc wymiarow. Czyli dla 1000 kulek w 2D i podziale
> ekranu na 100 kratek, mamy zlozonosc jednej "klatki fizyki"
> 1000 * 4 * 1000 / 100 = 40tys. Znacznie mniej niz X^2=1mln.
> Pozdrawiam
>
>
no pisalem wlasnie o tym - pytanie tylko o najbardziej korzystna
postac tej 'spacjali' dokladnie

chwilowo najprostsza wydaje mi sie chyba wersja z komorkami
10x10 pixeli, wtedy w takiej komorce moze byc najwiecej 4 kulki

kazda kulke przy ruchu wpisywaloby sie do najwiecej 4rech
komorek, podobnie czytaloby sie okolo 4ry komorki, mozna
zrobic na tablicy np

int spacjalaKolizyjna[40][50][4];

raczej proste i raczej szybkie, dzieki temu ze przypadek prosty










--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

>
> tylko trywialnej 'kwadratowej' detekcji kolizji
> (i to grubo bo kulek jest 200 ramek okolo 100/s
> i fizyka jest 5x na ramke - czyli to leci 100tys
> detekcji kolizji na sekunde)
>
100 tys petli - bo czastkowych sprawdzen kolizji to
wychodziloby 20 mln/sekunde

--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry