Redzamības rēķināšana ar portāliem..

Tagad izdomāju vienu diezgan vienkāršu algoritmu (gandrīz?) nekļūdīgam redzamības testam, kuru var lietot ar portāliem PVS rēķināšanai. Nezinu, vai ideja ir 100% mana, bet vismaz neatceros to kaut kur citur.

Visiem zināmie pamatfakti:
-istabas jeb manā gadījumā BSP koka lapas ir konveksas telpas, kuras ir savienotas ar portāliem
-portāls ir konvekss daudzstūris, kurš savieno 2 istabas
-no vienas istabas ir iespējams redzēt otru istabu tad, ja taisna līnija, kuras abi gali atrodas katrs savā istabā, nekrusto nevienas citas istabas daudzstūrus, tikai to portālus…

Uzdevums: maksimāli samazināt pārbaudāmo līniju skaitu, nezaudējot aprēķinu precizitāti.

Maksimāli samazināt pagaidām nesanāca, bet nekaitētu kādam pabīdītu šo manu ideju tālāk…

Pamatalgoritms diezgan vienkāršs:

PP – visas portālu daudzstūru virsotnes
II – visas istabas
foreach room i1 in II
foreach room i2 in II, sākot no i1 + 1 indeksa
foreach point3d p1 in PP
foreach point3d p2 in PP
p1 aizstumjam līdz sadursmei ar i1 istabu, ja tās nav vai sadursme notiek ar istabas daudzstūri, ne istabas portāla daudzstūri, izlaižam šo punktu kombināciju;
p2 aizstumjam līdz sadursmei ar i2 istabu, ja tās nav vai sadursme notiek ar istabas daudzstūri, ne istabas portāla daudzstūri, izlaižam šo punktu kombināciju;
ja līnija no p1 uz p2 nesaduras ar nevienu citu istabu, šīs abas istabas ir redzamas viena no otras, var ņemt nākamo istabu kombināciju testiem;

Implementācija kaut kad sekos… 😀
Īpašām problēmām ar to nevajadzētu būt, tikai defaultais craps – epsiloni floating point operācijās utt.
EDIT: Prātā ienāca pirmā īpašā problēma – portālu vertex’i ir stūros. Raycast’ā nedrīkst lietot samazīnātus daudzstūrus, tāpēc būs jāveic papildu testi, lai uzzinātu, vai daudzstūris, ar kuru ir sadursme, neveido to sadursmi punktā, kurš atrodas pārāk tuvu portālam — tik tuvu, ka sadursmi nevajadzētu ieskaitīt..

P.S. Jā, es 6os no rīta pēc negulētas nakts domāju šādus algoritmus.. so what? 😀

P.P.S.
Šeit ir tas paša zīmētais attēls, kurš man deva šo ideju:

P.P.P.S.
Pirmais algoritms, ko lietoju, bija pārbaude tikai ar istabu portālu vertex’u veidotām līnijām.. attēlā gan var redzēt, kāpēc visos gadījumos tas nestrādātu…