Wyszukiwanie binarne lub inny algorytm - Znajdowanie miejsca przeciecia terenu 3D z wiązką

[I am Lord]

Zgodnie z tym artykułem> https://gmclan.org/index.php?czytajart=74

Chciałem zrobić by wystrzelona wiązka w przestrzeni 3D znalazła najbliższe przecięcie z terenem. ( link do screena terenu )

No i algorytm mi failuje w sytuacji kiedy możliwych przecięć jest więcej niż 1.

 

Jak widać na poniższym obrazku przecięć jest 3, interesuje mnie znalezienie tego najbliżej startu wiązki, a algorytm znajduje ten najdalszy.

 

Algorytm by zadziałał gdybym zamiast sprawdzać czy badany punkt jest wyżej lub niżej od wysokości terenu to by było sprawdzane czy lina pomiędzy badanym punktem a startem się przecina z czym kolwiek. No ale tego tutaj nie osiągnę bo sprawdzanie wszystkich wierzchołków terenu po drodze było by zbyt czasochłonne.

 

Tak wygląda kod:

GML

/* zwraca długość wiązki wysłanej z pozycji x, y, z i o kierunku yaw, pitch

oraz deklaruje zmienne xRay, yRay, zRay, jest to miejsce w którym wiazka została przerwana

 

distance = ray_cast( x, y, z, yaw, pitch );*/

 

var _x, _y, _z, _hh, _yaw, _pitch, _disStart, _disEnd, _half, _cntBreak;

 

_x = argument0;

_y = argument1;

_z = argument2;

_xx = argument0;

_yy = argument1;

_zz = argument2;

_yaw = argument3;

_pitch = argument4;

_disStart = 0;

_disEnd = ray_length; // stała wynoszaca 1000

_cntBreak = 0;

do

{

// strzal w polowe dystansu

_half = floor( ( _disStart + _disEnd ) / 2 );

 

// nowy sprawdzany punkt

_xx = _x + lengthdir_x( _half, _yaw );

_yy = _y + lengthdir_y( _half, _yaw );

_zz = _z + lengthdir_y( _half, -_pitch );

 

// to znajduje wysokosc terenu pod ( lub nad ) punktem { _xx; _yy } innymi słowy nie musicie tego rozumieć :P

_hh = gMapH[ (abs(_xx) mod (mapSize*chunkSize) ) div chunkSize, (abs(_yy) mod (mapSize*chunkSize) ) div chunkSize ];

 

// główna część wyszukiwania binarnego

if ( _zz - _hh < 0 )

_disEnd = _half;

else

_disStart = _half;

 

// wyjscie z pętli na wszelki wypadek

_cntBreak += 1;

if ( _cntBreak > _disEnd/2 ) break;

 

} until ( abs( _disEnd - _disStart ) < ray_precision )

 

xRay = _xx;

yRay = _yy;

zRay = _zz;

 

return _half;

 

I tutaj pytanie może znacie jakiś lepszy algorytm który by sprawdzał wszystkie miejsca zerowe lub od razu ten najbliższy. A może da się jednak coś z tym powyższym zrobić?

[Konrad-GM]

W tym błąd, iż to nie do końca wypuszcza promień, lecz sprawdza punkt. :|

 

Zawsze można podzielić teren na sektory, i sprawdzać w którym sektorze mieści się promień. Następnie wystarczy przez serię w miarę prostych kalkulacji dot-productowych (ray-triangle-intersection) wyliczyć, z którymi trójkątami koliduje promień, i wyciągnąć z wyników najbliższy naszym wymaganiom punkt. :P

[I am Lord]

W tym błąd, iż to nie do końca wypuszcza promień, lecz sprawdza punkt. :|

No właśnie wiem że w tym jest błąd gdzieś tam napisałem dlatego szukam zamiennika jakiegoś albo modyfikacji tego mojego jak by się udało.

 

Zawsze można podzielić teren na sektory, i sprawdzać w którym sektorze mieści się promień. Następnie wystarczy przez serię w miarę prostych kalkulacji dot-productowych (ray-triangle-intersection) wyliczyć, z którymi trójkątami koliduje promień, i wyciągnąć z wyników najbliższy naszym wymaganiom punkt.

Ciekawe poczytam, na szczęście wszystkie wierzchołki mam zapisane w tablicy 128x128 może się uda to zrobić. Ale wątpię w szybkość działania tego :D