Pvs.cpp 34 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422
  1. /*
  2. ===========================================================================
  3. Doom 3 BFG Edition GPL Source Code
  4. Copyright (C) 1993-2012 id Software LLC, a ZeniMax Media company.
  5. This file is part of the Doom 3 BFG Edition GPL Source Code ("Doom 3 BFG Edition Source Code").
  6. Doom 3 BFG Edition Source Code is free software: you can redistribute it and/or modify
  7. it under the terms of the GNU General Public License as published by
  8. the Free Software Foundation, either version 3 of the License, or
  9. (at your option) any later version.
  10. Doom 3 BFG Edition Source Code is distributed in the hope that it will be useful,
  11. but WITHOUT ANY WARRANTY; without even the implied warranty of
  12. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  13. GNU General Public License for more details.
  14. You should have received a copy of the GNU General Public License
  15. along with Doom 3 BFG Edition Source Code. If not, see <http://www.gnu.org/licenses/>.
  16. In addition, the Doom 3 BFG Edition Source Code is also subject to certain additional terms. You should have received a copy of these additional terms immediately following the terms and conditions of the GNU General Public License which accompanied the Doom 3 BFG Edition Source Code. If not, please request a copy in writing from id Software at the address below.
  17. If you have questions concerning this license or the applicable additional terms, you may contact in writing id Software LLC, c/o ZeniMax Media Inc., Suite 120, Rockville, Maryland 20850 USA.
  18. ===========================================================================
  19. */
  20. #include "../idlib/precompiled.h"
  21. #pragma hdrstop
  22. #include "Game_local.h"
  23. #define MAX_BOUNDS_AREAS 16
  24. typedef struct pvsPassage_s {
  25. byte * canSee; // bit set for all portals that can be seen through this passage
  26. } pvsPassage_t;
  27. typedef struct pvsPortal_s {
  28. int areaNum; // area this portal leads to
  29. idWinding * w; // winding goes counter clockwise seen from the area this portal is part of
  30. idBounds bounds; // winding bounds
  31. idPlane plane; // winding plane, normal points towards the area this portal leads to
  32. pvsPassage_t * passages; // passages to portals in the area this portal leads to
  33. bool done; // true if pvs is calculated for this portal
  34. byte * vis; // PVS for this portal
  35. byte * mightSee; // used during construction
  36. } pvsPortal_t;
  37. typedef struct pvsArea_s {
  38. int numPortals; // number of portals in this area
  39. idBounds bounds; // bounds of the whole area
  40. pvsPortal_t ** portals; // array with pointers to the portals of this area
  41. } pvsArea_t;
  42. typedef struct pvsStack_s {
  43. struct pvsStack_s * next; // next stack entry
  44. byte * mightSee; // bit set for all portals that might be visible through this passage/portal stack
  45. } pvsStack_t;
  46. /*
  47. ================
  48. idPVS::idPVS
  49. ================
  50. */
  51. idPVS::idPVS() {
  52. int i;
  53. numAreas = 0;
  54. numPortals = 0;
  55. connectedAreas = NULL;
  56. areaQueue = NULL;
  57. areaPVS = NULL;
  58. for ( i = 0; i < MAX_CURRENT_PVS; i++ ) {
  59. currentPVS[i].handle.i = -1;
  60. currentPVS[i].handle.h = 0;
  61. currentPVS[i].pvs = NULL;
  62. }
  63. pvsAreas = NULL;
  64. pvsPortals = NULL;
  65. }
  66. /*
  67. ================
  68. idPVS::~idPVS
  69. ================
  70. */
  71. idPVS::~idPVS() {
  72. Shutdown();
  73. }
  74. /*
  75. ================
  76. idPVS::GetPortalCount
  77. ================
  78. */
  79. int idPVS::GetPortalCount() const {
  80. int i, na, np;
  81. na = gameRenderWorld->NumAreas();
  82. np = 0;
  83. for ( i = 0; i < na; i++ ) {
  84. np += gameRenderWorld->NumPortalsInArea( i );
  85. }
  86. return np;
  87. }
  88. /*
  89. ================
  90. idPVS::CreatePVSData
  91. ================
  92. */
  93. void idPVS::CreatePVSData() {
  94. int i, j, n, cp;
  95. exitPortal_t portal;
  96. pvsArea_t *area;
  97. pvsPortal_t *p, **portalPtrs;
  98. if ( !numPortals ) {
  99. return;
  100. }
  101. pvsPortals = new (TAG_PVS) pvsPortal_t[numPortals];
  102. pvsAreas = new (TAG_PVS) pvsArea_t[numAreas];
  103. memset( pvsAreas, 0, numAreas * sizeof( *pvsAreas ) );
  104. cp = 0;
  105. portalPtrs = new (TAG_PVS) pvsPortal_t*[numPortals];
  106. for ( i = 0; i < numAreas; i++ ) {
  107. area = &pvsAreas[i];
  108. area->bounds.Clear();
  109. area->portals = portalPtrs + cp;
  110. n = gameRenderWorld->NumPortalsInArea( i );
  111. for ( j = 0; j < n; j++ ) {
  112. portal = gameRenderWorld->GetPortal( i, j );
  113. p = &pvsPortals[cp++];
  114. // the winding goes counter clockwise seen from this area
  115. p->w = portal.w->Copy();
  116. p->areaNum = portal.areas[1]; // area[1] is always the area the portal leads to
  117. p->vis = new (TAG_PVS) byte[portalVisBytes];
  118. memset( p->vis, 0, portalVisBytes );
  119. p->mightSee = new (TAG_PVS) byte[portalVisBytes];
  120. memset( p->mightSee, 0, portalVisBytes );
  121. p->w->GetBounds( p->bounds );
  122. p->w->GetPlane( p->plane );
  123. // plane normal points to outside the area
  124. p->plane = -p->plane;
  125. // no PVS calculated for this portal yet
  126. p->done = false;
  127. area->portals[area->numPortals] = p;
  128. area->numPortals++;
  129. area->bounds += p->bounds;
  130. }
  131. }
  132. }
  133. /*
  134. ================
  135. idPVS::DestroyPVSData
  136. ================
  137. */
  138. void idPVS::DestroyPVSData() {
  139. int i;
  140. if ( !pvsAreas ) {
  141. return;
  142. }
  143. // delete portal pointer array
  144. delete[] pvsAreas[0].portals;
  145. // delete all areas
  146. delete[] pvsAreas;
  147. pvsAreas = NULL;
  148. // delete portal data
  149. for ( i = 0; i < numPortals; i++ ) {
  150. delete[] pvsPortals[i].vis;
  151. delete[] pvsPortals[i].mightSee;
  152. delete pvsPortals[i].w;
  153. }
  154. // delete portals
  155. delete[] pvsPortals;
  156. pvsPortals = NULL;
  157. }
  158. /*
  159. ================
  160. idPVS::FloodFrontPortalPVS_r
  161. ================
  162. */
  163. void idPVS::FloodFrontPortalPVS_r( pvsPortal_t *portal, int areaNum ) const {
  164. int i, n;
  165. pvsArea_t *area;
  166. pvsPortal_t *p;
  167. area = &pvsAreas[ areaNum ];
  168. for ( i = 0; i < area->numPortals; i++ ) {
  169. p = area->portals[i];
  170. n = p - pvsPortals;
  171. // don't flood through if this portal is not at the front
  172. if ( !( portal->mightSee[ n>>3 ] & (1 << (n&7)) ) ) {
  173. continue;
  174. }
  175. // don't flood through if already visited this portal
  176. if ( portal->vis[ n>>3 ] & (1 << (n&7)) ) {
  177. continue;
  178. }
  179. // this portal might be visible
  180. portal->vis[ n>>3 ] |= (1 << (n&7));
  181. // flood through the portal
  182. FloodFrontPortalPVS_r( portal, p->areaNum );
  183. }
  184. }
  185. /*
  186. ================
  187. idPVS::FrontPortalPVS
  188. ================
  189. */
  190. void idPVS::FrontPortalPVS() const {
  191. int i, j, k, n, p, side1, side2, areaSide;
  192. pvsPortal_t *p1, *p2;
  193. pvsArea_t *area;
  194. for ( i = 0; i < numPortals; i++ ) {
  195. p1 = &pvsPortals[i];
  196. for ( j = 0; j < numAreas; j++ ) {
  197. area = &pvsAreas[j];
  198. areaSide = side1 = area->bounds.PlaneSide( p1->plane );
  199. // if the whole area is at the back side of the portal
  200. if ( areaSide == PLANESIDE_BACK ) {
  201. continue;
  202. }
  203. for ( p = 0; p < area->numPortals; p++ ) {
  204. p2 = area->portals[p];
  205. // if we the whole area is not at the front we need to check
  206. if ( areaSide != PLANESIDE_FRONT ) {
  207. // if the second portal is completely at the back side of the first portal
  208. side1 = p2->bounds.PlaneSide( p1->plane );
  209. if ( side1 == PLANESIDE_BACK ) {
  210. continue;
  211. }
  212. }
  213. // if the first portal is completely at the front of the second portal
  214. side2 = p1->bounds.PlaneSide( p2->plane );
  215. if ( side2 == PLANESIDE_FRONT ) {
  216. continue;
  217. }
  218. // if the second portal is not completely at the front of the first portal
  219. if ( side1 != PLANESIDE_FRONT ) {
  220. // more accurate check
  221. for ( k = 0; k < p2->w->GetNumPoints(); k++ ) {
  222. // if more than an epsilon at the front side
  223. if ( p1->plane.Side( (*p2->w)[k].ToVec3(), ON_EPSILON ) == PLANESIDE_FRONT ) {
  224. break;
  225. }
  226. }
  227. if ( k >= p2->w->GetNumPoints() ) {
  228. continue; // second portal is at the back of the first portal
  229. }
  230. }
  231. // if the first portal is not completely at the back side of the second portal
  232. if ( side2 != PLANESIDE_BACK ) {
  233. // more accurate check
  234. for ( k = 0; k < p1->w->GetNumPoints(); k++ ) {
  235. // if more than an epsilon at the back side
  236. if ( p2->plane.Side( (*p1->w)[k].ToVec3(), ON_EPSILON ) == PLANESIDE_BACK ) {
  237. break;
  238. }
  239. }
  240. if ( k >= p1->w->GetNumPoints() ) {
  241. continue; // first portal is at the front of the second portal
  242. }
  243. }
  244. // the portal might be visible at the front
  245. n = p2 - pvsPortals;
  246. p1->mightSee[ n >> 3 ] |= 1 << (n&7);
  247. }
  248. }
  249. }
  250. // flood the front portal pvs for all portals
  251. for ( i = 0; i < numPortals; i++ ) {
  252. p1 = &pvsPortals[i];
  253. FloodFrontPortalPVS_r( p1, p1->areaNum );
  254. }
  255. }
  256. /*
  257. ===============
  258. idPVS::FloodPassagePVS_r
  259. ===============
  260. */
  261. pvsStack_t *idPVS::FloodPassagePVS_r( pvsPortal_t *source, const pvsPortal_t *portal, pvsStack_t *prevStack ) const {
  262. int i, j, n, m;
  263. pvsPortal_t *p;
  264. pvsArea_t *area;
  265. pvsStack_t *stack;
  266. pvsPassage_t *passage;
  267. long *sourceVis, *passageVis, *portalVis, *mightSee, *prevMightSee, more;
  268. area = &pvsAreas[portal->areaNum];
  269. stack = prevStack->next;
  270. // if no next stack entry allocated
  271. if ( !stack ) {
  272. stack = reinterpret_cast<pvsStack_t*>(new byte[sizeof(pvsStack_t) + portalVisBytes]);
  273. stack->mightSee = (reinterpret_cast<byte *>(stack)) + sizeof(pvsStack_t);
  274. stack->next = NULL;
  275. prevStack->next = stack;
  276. }
  277. // check all portals for flooding into other areas
  278. for ( i = 0; i < area->numPortals; i++ ) {
  279. passage = &portal->passages[i];
  280. // if this passage is completely empty
  281. if ( !passage->canSee ) {
  282. continue;
  283. }
  284. p = area->portals[i];
  285. n = p - pvsPortals;
  286. // if this portal cannot be seen through our current portal/passage stack
  287. if ( !( prevStack->mightSee[n >> 3] & (1 << (n & 7)) ) ) {
  288. continue;
  289. }
  290. // mark the portal as visible
  291. source->vis[n >> 3] |= (1 << (n & 7));
  292. // get pointers to vis data
  293. prevMightSee = reinterpret_cast<long *>(prevStack->mightSee);
  294. passageVis = reinterpret_cast<long *>(passage->canSee);
  295. sourceVis = reinterpret_cast<long *>(source->vis);
  296. mightSee = reinterpret_cast<long *>(stack->mightSee);
  297. more = 0;
  298. // use the portal PVS if it has been calculated
  299. if ( p->done ) {
  300. portalVis = reinterpret_cast<long *>(p->vis);
  301. for ( j = 0; j < portalVisLongs; j++ ) {
  302. // get new PVS which is decreased by going through this passage
  303. m = *prevMightSee++ & *passageVis++ & *portalVis++;
  304. // check if anything might be visible through this passage that wasn't yet visible
  305. more |= (m & ~(*sourceVis++));
  306. // store new PVS
  307. *mightSee++ = m;
  308. }
  309. }
  310. else {
  311. // the p->mightSee is implicitely stored in the passageVis
  312. for ( j = 0; j < portalVisLongs; j++ ) {
  313. // get new PVS which is decreased by going through this passage
  314. m = *prevMightSee++ & *passageVis++;
  315. // check if anything might be visible through this passage that wasn't yet visible
  316. more |= (m & ~(*sourceVis++));
  317. // store new PVS
  318. *mightSee++ = m;
  319. }
  320. }
  321. // if nothing more can be seen
  322. if ( !more ) {
  323. continue;
  324. }
  325. // go through the portal
  326. stack->next = FloodPassagePVS_r( source, p, stack );
  327. }
  328. return stack;
  329. }
  330. /*
  331. ===============
  332. idPVS::PassagePVS
  333. ===============
  334. */
  335. void idPVS::PassagePVS() const {
  336. int i;
  337. pvsPortal_t *source;
  338. pvsStack_t *stack, *s;
  339. // create the passages
  340. CreatePassages();
  341. // allocate first stack entry
  342. stack = reinterpret_cast<pvsStack_t*>(new byte[sizeof(pvsStack_t) + portalVisBytes]);
  343. stack->mightSee = (reinterpret_cast<byte *>(stack)) + sizeof(pvsStack_t);
  344. stack->next = NULL;
  345. // calculate portal PVS by flooding through the passages
  346. for ( i = 0; i < numPortals; i++ ) {
  347. source = &pvsPortals[i];
  348. memset( source->vis, 0, portalVisBytes );
  349. memcpy( stack->mightSee, source->mightSee, portalVisBytes );
  350. FloodPassagePVS_r( source, source, stack );
  351. source->done = true;
  352. }
  353. // free the allocated stack
  354. for ( s = stack; s; s = stack ) {
  355. stack = stack->next;
  356. delete[] s;
  357. }
  358. // destroy the passages
  359. DestroyPassages();
  360. }
  361. /*
  362. ===============
  363. idPVS::AddPassageBoundaries
  364. ===============
  365. */
  366. void idPVS::AddPassageBoundaries( const idWinding &source, const idWinding &pass, bool flipClip, idPlane *bounds, int &numBounds, int maxBounds ) const {
  367. int i, j, k, l;
  368. idVec3 v1, v2, normal;
  369. float d, dist;
  370. bool flipTest, front;
  371. idPlane plane;
  372. // check all combinations
  373. for ( i = 0; i < source.GetNumPoints(); i++ ) {
  374. l = (i + 1) % source.GetNumPoints();
  375. v1 = source[l].ToVec3() - source[i].ToVec3();
  376. // find a vertex of pass that makes a plane that puts all of the
  377. // vertices of pass on the front side and all of the vertices of
  378. // source on the back side
  379. for ( j = 0; j < pass.GetNumPoints(); j++ ) {
  380. v2 = pass[j].ToVec3() - source[i].ToVec3();
  381. normal = v1.Cross( v2 );
  382. if ( normal.Normalize() < 0.01f ) {
  383. continue;
  384. }
  385. dist = normal * pass[j].ToVec3();
  386. //
  387. // find out which side of the generated seperating plane has the
  388. // source portal
  389. //
  390. flipTest = false;
  391. for ( k = 0; k < source.GetNumPoints(); k++ ) {
  392. if ( k == i || k == l ) {
  393. continue;
  394. }
  395. d = source[k].ToVec3() * normal - dist;
  396. if ( d < -ON_EPSILON ) {
  397. // source is on the negative side, so we want all
  398. // pass and target on the positive side
  399. flipTest = false;
  400. break;
  401. }
  402. else if ( d > ON_EPSILON ) {
  403. // source is on the positive side, so we want all
  404. // pass and target on the negative side
  405. flipTest = true;
  406. break;
  407. }
  408. }
  409. if ( k == source.GetNumPoints() ) {
  410. continue; // planar with source portal
  411. }
  412. // flip the normal if the source portal is backwards
  413. if (flipTest) {
  414. normal = -normal;
  415. dist = -dist;
  416. }
  417. // if all of the pass portal points are now on the positive side,
  418. // this is the seperating plane
  419. front = false;
  420. for ( k = 0; k < pass.GetNumPoints(); k++ ) {
  421. if ( k == j ) {
  422. continue;
  423. }
  424. d = pass[k].ToVec3() * normal - dist;
  425. if ( d < -ON_EPSILON ) {
  426. break;
  427. }
  428. else if ( d > ON_EPSILON ) {
  429. front = true;
  430. }
  431. }
  432. if ( k < pass.GetNumPoints() ) {
  433. continue; // points on negative side, not a seperating plane
  434. }
  435. if ( !front ) {
  436. continue; // planar with seperating plane
  437. }
  438. // flip the normal if we want the back side
  439. if ( flipClip ) {
  440. plane.SetNormal( -normal );
  441. plane.SetDist( -dist );
  442. }
  443. else {
  444. plane.SetNormal( normal );
  445. plane.SetDist( dist );
  446. }
  447. // check if the plane is already a passage boundary
  448. for ( k = 0; k < numBounds; k++ ) {
  449. if ( plane.Compare( bounds[k], 0.001f, 0.01f ) ) {
  450. break;
  451. }
  452. }
  453. if ( k < numBounds ) {
  454. break;
  455. }
  456. if ( numBounds >= maxBounds ) {
  457. gameLocal.Warning( "max passage boundaries." );
  458. break;
  459. }
  460. bounds[numBounds] = plane;
  461. numBounds++;
  462. break;
  463. }
  464. }
  465. }
  466. /*
  467. ================
  468. idPVS::CreatePassages
  469. ================
  470. */
  471. #define MAX_PASSAGE_BOUNDS 128
  472. void idPVS::CreatePassages() const {
  473. int i, j, l, n, numBounds, front, passageMemory, byteNum, bitNum;
  474. int sides[MAX_PASSAGE_BOUNDS];
  475. idPlane passageBounds[MAX_PASSAGE_BOUNDS];
  476. pvsPortal_t *source, *target, *p;
  477. pvsArea_t *area;
  478. pvsPassage_t *passage;
  479. idFixedWinding winding;
  480. byte canSee, mightSee, bit;
  481. passageMemory = 0;
  482. for ( i = 0; i < numPortals; i++ ) {
  483. source = &pvsPortals[i];
  484. area = &pvsAreas[source->areaNum];
  485. source->passages = new (TAG_PVS) pvsPassage_t[area->numPortals];
  486. for ( j = 0; j < area->numPortals; j++ ) {
  487. target = area->portals[j];
  488. n = target - pvsPortals;
  489. passage = &source->passages[j];
  490. // if the source portal cannot see this portal
  491. if ( !( source->mightSee[ n>>3 ] & (1 << (n&7)) ) ) {
  492. // not all portals in the area have to be visible because areas are not necesarily convex
  493. // also no passage has to be created for the portal which is the opposite of the source
  494. passage->canSee = NULL;
  495. continue;
  496. }
  497. passage->canSee = new (TAG_PVS) byte[portalVisBytes];
  498. passageMemory += portalVisBytes;
  499. // boundary plane normals point inwards
  500. numBounds = 0;
  501. AddPassageBoundaries( *(source->w), *(target->w), false, passageBounds, numBounds, MAX_PASSAGE_BOUNDS );
  502. AddPassageBoundaries( *(target->w), *(source->w), true, passageBounds, numBounds, MAX_PASSAGE_BOUNDS );
  503. // get all portals visible through this passage
  504. for ( byteNum = 0; byteNum < portalVisBytes; byteNum++) {
  505. canSee = 0;
  506. mightSee = source->mightSee[byteNum] & target->mightSee[byteNum];
  507. // go through eight portals at a time to speed things up
  508. for ( bitNum = 0; bitNum < 8; bitNum++ ) {
  509. bit = 1 << bitNum;
  510. if ( !( mightSee & bit ) ) {
  511. continue;
  512. }
  513. p = &pvsPortals[(byteNum << 3) + bitNum];
  514. if ( p->areaNum == source->areaNum ) {
  515. continue;
  516. }
  517. for ( front = 0, l = 0; l < numBounds; l++ ) {
  518. sides[l] = p->bounds.PlaneSide( passageBounds[l] );
  519. // if completely at the back of the passage bounding plane
  520. if ( sides[l] == PLANESIDE_BACK ) {
  521. break;
  522. }
  523. // if completely at the front
  524. if ( sides[l] == PLANESIDE_FRONT ) {
  525. front++;
  526. }
  527. }
  528. // if completely outside the passage
  529. if ( l < numBounds ) {
  530. continue;
  531. }
  532. // if not at the front of all bounding planes and thus not completely inside the passage
  533. if ( front != numBounds ) {
  534. winding = *p->w;
  535. for ( l = 0; l < numBounds; l++ ) {
  536. // only clip if the winding possibly crosses this plane
  537. if ( sides[l] != PLANESIDE_CROSS ) {
  538. continue;
  539. }
  540. // clip away the part at the back of the bounding plane
  541. winding.ClipInPlace( passageBounds[l] );
  542. // if completely clipped away
  543. if ( !winding.GetNumPoints() ) {
  544. break;
  545. }
  546. }
  547. // if completely outside the passage
  548. if ( l < numBounds ) {
  549. continue;
  550. }
  551. }
  552. canSee |= bit;
  553. }
  554. // store results of all eight portals
  555. passage->canSee[byteNum] = canSee;
  556. }
  557. // can always see the target portal
  558. passage->canSee[n >> 3] |= (1 << (n&7));
  559. }
  560. }
  561. if ( passageMemory < 1024 ) {
  562. gameLocal.Printf( "%5d bytes passage memory used to build PVS\n", passageMemory );
  563. }
  564. else {
  565. gameLocal.Printf( "%5d KB passage memory used to build PVS\n", passageMemory>>10 );
  566. }
  567. }
  568. /*
  569. ================
  570. idPVS::DestroyPassages
  571. ================
  572. */
  573. void idPVS::DestroyPassages() const {
  574. int i, j;
  575. pvsPortal_t *p;
  576. pvsArea_t *area;
  577. for ( i = 0; i < numPortals; i++ ) {
  578. p = &pvsPortals[i];
  579. area = &pvsAreas[p->areaNum];
  580. for ( j = 0; j < area->numPortals; j++ ) {
  581. if ( p->passages[j].canSee ) {
  582. delete[] p->passages[j].canSee;
  583. }
  584. }
  585. delete[] p->passages;
  586. }
  587. }
  588. /*
  589. ================
  590. idPVS::CopyPortalPVSToMightSee
  591. ================
  592. */
  593. void idPVS::CopyPortalPVSToMightSee() const {
  594. int i;
  595. pvsPortal_t *p;
  596. for ( i = 0; i < numPortals; i++ ) {
  597. p = &pvsPortals[i];
  598. memcpy( p->mightSee, p->vis, portalVisBytes );
  599. }
  600. }
  601. /*
  602. ================
  603. idPVS::AreaPVSFromPortalPVS
  604. ================
  605. */
  606. int idPVS::AreaPVSFromPortalPVS() const {
  607. int i, j, k, areaNum, totalVisibleAreas;
  608. long *p1, *p2;
  609. byte *pvs, *portalPVS;
  610. pvsArea_t *area;
  611. totalVisibleAreas = 0;
  612. if ( !numPortals ) {
  613. return totalVisibleAreas;
  614. }
  615. memset( areaPVS, 0, numAreas * areaVisBytes );
  616. for ( i = 0; i < numAreas; i++ ) {
  617. area = &pvsAreas[i];
  618. pvs = areaPVS + i * areaVisBytes;
  619. // the area is visible to itself
  620. pvs[ i >> 3 ] |= 1 << (i & 7);
  621. if ( !area->numPortals ) {
  622. continue;
  623. }
  624. // store the PVS of all portals in this area at the first portal
  625. for ( j = 1; j < area->numPortals; j++ ) {
  626. p1 = reinterpret_cast<long *>(area->portals[0]->vis);
  627. p2 = reinterpret_cast<long *>(area->portals[j]->vis);
  628. for ( k = 0; k < portalVisLongs; k++ ) {
  629. *p1++ |= *p2++;
  630. }
  631. }
  632. // the portals of this area are always visible
  633. for ( j = 0; j < area->numPortals; j++ ) {
  634. k = area->portals[j] - pvsPortals;
  635. area->portals[0]->vis[ k >> 3 ] |= 1 << (k & 7);
  636. }
  637. // set all areas to visible that can be seen from the portals of this area
  638. portalPVS = area->portals[0]->vis;
  639. for ( j = 0; j < numPortals; j++ ) {
  640. // if this portal is visible
  641. if ( portalPVS[j>>3] & (1 << (j&7)) ) {
  642. areaNum = pvsPortals[j].areaNum;
  643. pvs[ areaNum >> 3 ] |= 1 << (areaNum & 7);
  644. }
  645. }
  646. // count the number of visible areas
  647. for ( j = 0; j < numAreas; j++ ) {
  648. if ( pvs[j>>3] & (1 << (j&7)) ) {
  649. totalVisibleAreas++;
  650. }
  651. }
  652. }
  653. return totalVisibleAreas;
  654. }
  655. /*
  656. ================
  657. idPVS::Init
  658. ================
  659. */
  660. void idPVS::Init() {
  661. int totalVisibleAreas;
  662. Shutdown();
  663. numAreas = gameRenderWorld->NumAreas();
  664. if ( numAreas <= 0 ) {
  665. return;
  666. }
  667. connectedAreas = new (TAG_PVS) bool[numAreas];
  668. areaQueue = new (TAG_PVS) int[numAreas];
  669. areaVisBytes = ( ((numAreas+31)&~31) >> 3);
  670. areaVisLongs = areaVisBytes/sizeof(long);
  671. areaPVS = new (TAG_PVS) byte[numAreas * areaVisBytes];
  672. memset( areaPVS, 0xFF, numAreas * areaVisBytes );
  673. numPortals = GetPortalCount();
  674. portalVisBytes = ( ((numPortals+31)&~31) >> 3);
  675. portalVisLongs = portalVisBytes/sizeof(long);
  676. for ( int i = 0; i < MAX_CURRENT_PVS; i++ ) {
  677. currentPVS[i].handle.i = -1;
  678. currentPVS[i].handle.h = 0;
  679. currentPVS[i].pvs = new (TAG_PVS) byte[areaVisBytes];
  680. memset( currentPVS[i].pvs, 0, areaVisBytes );
  681. }
  682. idTimer timer;
  683. timer.Start();
  684. CreatePVSData();
  685. FrontPortalPVS();
  686. CopyPortalPVSToMightSee();
  687. PassagePVS();
  688. totalVisibleAreas = AreaPVSFromPortalPVS();
  689. DestroyPVSData();
  690. timer.Stop();
  691. gameLocal.Printf( "%5.0f msec to calculate PVS\n", timer.Milliseconds() );
  692. gameLocal.Printf( "%5d areas\n", numAreas );
  693. gameLocal.Printf( "%5d portals\n", numPortals );
  694. gameLocal.Printf( "%5d areas visible on average\n", totalVisibleAreas / numAreas );
  695. if ( numAreas * areaVisBytes < 1024 ) {
  696. gameLocal.Printf( "%5d bytes PVS data\n", numAreas * areaVisBytes );
  697. }
  698. else {
  699. gameLocal.Printf( "%5d KB PVS data\n", (numAreas * areaVisBytes) >> 10 );
  700. }
  701. }
  702. /*
  703. ================
  704. idPVS::Shutdown
  705. ================
  706. */
  707. void idPVS::Shutdown() {
  708. if ( connectedAreas ) {
  709. delete connectedAreas;
  710. connectedAreas = NULL;
  711. }
  712. if ( areaQueue ) {
  713. delete areaQueue;
  714. areaQueue = NULL;
  715. }
  716. if ( areaPVS ) {
  717. delete areaPVS;
  718. areaPVS = NULL;
  719. }
  720. for ( int i = 0; i < MAX_CURRENT_PVS; i++ ) {
  721. delete currentPVS[i].pvs;
  722. currentPVS[i].pvs = NULL;
  723. }
  724. }
  725. /*
  726. ================
  727. idPVS::GetConnectedAreas
  728. assumes the 'areas' array is initialized to false
  729. ================
  730. */
  731. void idPVS::GetConnectedAreas( int srcArea, bool *areas ) const {
  732. int curArea, nextArea;
  733. int queueStart, queueEnd;
  734. int i, n;
  735. exitPortal_t portal;
  736. queueStart = -1;
  737. queueEnd = 0;
  738. areas[srcArea] = true;
  739. for ( curArea = srcArea; queueStart < queueEnd; curArea = areaQueue[++queueStart] ) {
  740. n = gameRenderWorld->NumPortalsInArea( curArea );
  741. for ( i = 0; i < n; i++ ) {
  742. portal = gameRenderWorld->GetPortal( curArea, i );
  743. if ( portal.blockingBits & PS_BLOCK_VIEW ) {
  744. continue;
  745. }
  746. // area[1] is always the area the portal leads to
  747. nextArea = portal.areas[1];
  748. // if already visited this area
  749. if ( areas[nextArea] ) {
  750. continue;
  751. }
  752. // add area to queue
  753. areaQueue[queueEnd++] = nextArea;
  754. areas[nextArea] = true;
  755. }
  756. }
  757. }
  758. /*
  759. ================
  760. idPVS::GetPVSArea
  761. ================
  762. */
  763. int idPVS::GetPVSArea( const idVec3 &point ) const {
  764. return gameRenderWorld->PointInArea( point );
  765. }
  766. /*
  767. ================
  768. idPVS::GetPVSAreas
  769. ================
  770. */
  771. int idPVS::GetPVSAreas( const idBounds &bounds, int *areas, int maxAreas ) const {
  772. return gameRenderWorld->BoundsInAreas( bounds, areas, maxAreas );
  773. }
  774. /*
  775. ================
  776. idPVS::SetupCurrentPVS
  777. ================
  778. */
  779. pvsHandle_t idPVS::SetupCurrentPVS( const idVec3 &source, const pvsType_t type ) const {
  780. int sourceArea;
  781. sourceArea = gameRenderWorld->PointInArea( source );
  782. return SetupCurrentPVS( sourceArea, type );
  783. }
  784. /*
  785. ================
  786. idPVS::SetupCurrentPVS
  787. ================
  788. */
  789. pvsHandle_t idPVS::SetupCurrentPVS( const idBounds &source, const pvsType_t type ) const {
  790. int numSourceAreas, sourceAreas[MAX_BOUNDS_AREAS];
  791. numSourceAreas = gameRenderWorld->BoundsInAreas( source, sourceAreas, MAX_BOUNDS_AREAS );
  792. return SetupCurrentPVS( sourceAreas, numSourceAreas, type );
  793. }
  794. /*
  795. ================
  796. idPVS::SetupCurrentPVS
  797. ================
  798. */
  799. pvsHandle_t idPVS::SetupCurrentPVS( const int sourceArea, const pvsType_t type ) const {
  800. int i;
  801. pvsHandle_t handle;
  802. handle = AllocCurrentPVS( *reinterpret_cast<const unsigned int *>(&sourceArea) );
  803. if ( sourceArea < 0 || sourceArea >= numAreas ) {
  804. memset( currentPVS[handle.i].pvs, 0, areaVisBytes );
  805. return handle;
  806. }
  807. if ( type != PVS_CONNECTED_AREAS ) {
  808. memcpy( currentPVS[handle.i].pvs, areaPVS + sourceArea * areaVisBytes, areaVisBytes );
  809. } else {
  810. memset( currentPVS[handle.i].pvs, -1, areaVisBytes );
  811. }
  812. if ( type == PVS_ALL_PORTALS_OPEN ) {
  813. return handle;
  814. }
  815. memset( connectedAreas, 0, numAreas * sizeof( *connectedAreas ) );
  816. GetConnectedAreas( sourceArea, connectedAreas );
  817. for ( i = 0; i < numAreas; i++ ) {
  818. if ( !connectedAreas[i] ) {
  819. currentPVS[handle.i].pvs[i>>3] &= ~(1 << (i&7));
  820. }
  821. }
  822. return handle;
  823. }
  824. /*
  825. ================
  826. idPVS::SetupCurrentPVS
  827. ================
  828. */
  829. pvsHandle_t idPVS::SetupCurrentPVS( const int *sourceAreas, const int numSourceAreas, const pvsType_t type ) const {
  830. int i, j;
  831. unsigned int h;
  832. long *vis, *pvs;
  833. pvsHandle_t handle;
  834. h = 0;
  835. for ( i = 0; i < numSourceAreas; i++ ) {
  836. h ^= *reinterpret_cast<const unsigned int *>(&sourceAreas[i]);
  837. }
  838. handle = AllocCurrentPVS( h );
  839. if ( !numSourceAreas || sourceAreas[0] < 0 || sourceAreas[0] >= numAreas) {
  840. memset( currentPVS[handle.i].pvs, 0, areaVisBytes );
  841. return handle;
  842. }
  843. if ( type != PVS_CONNECTED_AREAS ) {
  844. // merge PVS of all areas the source is in
  845. memcpy( currentPVS[handle.i].pvs, areaPVS + sourceAreas[0] * areaVisBytes, areaVisBytes );
  846. for ( i = 1; i < numSourceAreas; i++ ) {
  847. assert( sourceAreas[i] >= 0 && sourceAreas[i] < numAreas );
  848. vis = reinterpret_cast<long*>(areaPVS + sourceAreas[i] * areaVisBytes);
  849. pvs = reinterpret_cast<long*>(currentPVS[handle.i].pvs);
  850. for ( j = 0; j < areaVisLongs; j++ ) {
  851. *pvs++ |= *vis++;
  852. }
  853. }
  854. } else {
  855. memset( currentPVS[handle.i].pvs, -1, areaVisBytes );
  856. }
  857. if ( type == PVS_ALL_PORTALS_OPEN ) {
  858. return handle;
  859. }
  860. memset( connectedAreas, 0, numAreas * sizeof( *connectedAreas ) );
  861. // get all areas connected to any of the source areas
  862. for ( i = 0; i < numSourceAreas; i++ ) {
  863. if ( !connectedAreas[sourceAreas[i]] ) {
  864. GetConnectedAreas( sourceAreas[i], connectedAreas );
  865. }
  866. }
  867. // remove unconnected areas from the PVS
  868. for ( i = 0; i < numAreas; i++ ) {
  869. if ( !connectedAreas[i] ) {
  870. currentPVS[handle.i].pvs[i>>3] &= ~(1 << (i&7));
  871. }
  872. }
  873. return handle;
  874. }
  875. /*
  876. ================
  877. idPVS::MergeCurrentPVS
  878. ================
  879. */
  880. pvsHandle_t idPVS::MergeCurrentPVS( pvsHandle_t pvs1, pvsHandle_t pvs2 ) const {
  881. int i;
  882. long *pvs1Ptr, *pvs2Ptr, *ptr;
  883. pvsHandle_t handle = { 0 };
  884. if ( pvs1.i < 0 || pvs1.i >= MAX_CURRENT_PVS || pvs1.h != currentPVS[pvs1.i].handle.h ||
  885. pvs2.i < 0 || pvs2.i >= MAX_CURRENT_PVS || pvs2.h != currentPVS[pvs2.i].handle.h ) {
  886. gameLocal.Error( "idPVS::MergeCurrentPVS: invalid handle" );
  887. return handle;
  888. }
  889. handle = AllocCurrentPVS( pvs1.h ^ pvs2.h );
  890. ptr = reinterpret_cast<long*>(currentPVS[handle.i].pvs);
  891. pvs1Ptr = reinterpret_cast<long*>(currentPVS[pvs1.i].pvs);
  892. pvs2Ptr = reinterpret_cast<long*>(currentPVS[pvs2.i].pvs);
  893. for ( i = 0; i < areaVisLongs; i++ ) {
  894. *ptr++ = *pvs1Ptr++ | *pvs2Ptr++;
  895. }
  896. return handle;
  897. }
  898. /*
  899. ================
  900. idPVS::AllocCurrentPVS
  901. ================
  902. */
  903. pvsHandle_t idPVS::AllocCurrentPVS( unsigned int h ) const {
  904. int i;
  905. pvsHandle_t handle;
  906. for ( i = 0; i < MAX_CURRENT_PVS; i++ ) {
  907. if ( currentPVS[i].handle.i == -1 ) {
  908. currentPVS[i].handle.i = i;
  909. currentPVS[i].handle.h = h;
  910. return currentPVS[i].handle;
  911. }
  912. }
  913. gameLocal.Error( "idPVS::AllocCurrentPVS: no free PVS left" );
  914. handle.i = -1;
  915. handle.h = 0;
  916. return handle;
  917. }
  918. /*
  919. ================
  920. idPVS::FreeCurrentPVS
  921. ================
  922. */
  923. void idPVS::FreeCurrentPVS( pvsHandle_t handle ) const {
  924. if ( handle.i < 0 || handle.i >= MAX_CURRENT_PVS || handle.h != currentPVS[handle.i].handle.h ) {
  925. gameLocal.Error( "idPVS::FreeCurrentPVS: invalid handle" );
  926. return;
  927. }
  928. currentPVS[handle.i].handle.i = -1;
  929. }
  930. /*
  931. ================
  932. idPVS::InCurrentPVS
  933. ================
  934. */
  935. bool idPVS::InCurrentPVS( const pvsHandle_t handle, const idVec3 &target ) const {
  936. int targetArea;
  937. if ( handle.i < 0 || handle.i >= MAX_CURRENT_PVS ||
  938. handle.h != currentPVS[handle.i].handle.h ) {
  939. gameLocal.Warning( "idPVS::InCurrentPVS: invalid handle" );
  940. return false;
  941. }
  942. targetArea = gameRenderWorld->PointInArea( target );
  943. if ( targetArea == -1 ) {
  944. return false;
  945. }
  946. return ( ( currentPVS[handle.i].pvs[targetArea>>3] & (1 << (targetArea&7)) ) != 0 );
  947. }
  948. /*
  949. ================
  950. idPVS::InCurrentPVS
  951. ================
  952. */
  953. bool idPVS::InCurrentPVS( const pvsHandle_t handle, const idBounds &target ) const {
  954. int i, numTargetAreas, targetAreas[MAX_BOUNDS_AREAS];
  955. if ( handle.i < 0 || handle.i >= MAX_CURRENT_PVS ||
  956. handle.h != currentPVS[handle.i].handle.h ) {
  957. gameLocal.Warning( "idPVS::InCurrentPVS: invalid handle" );
  958. return false;
  959. }
  960. numTargetAreas = gameRenderWorld->BoundsInAreas( target, targetAreas, MAX_BOUNDS_AREAS );
  961. for ( i = 0; i < numTargetAreas; i++ ) {
  962. if ( currentPVS[handle.i].pvs[targetAreas[i]>>3] & (1 << (targetAreas[i]&7)) ) {
  963. return true;
  964. }
  965. }
  966. return false;
  967. }
  968. /*
  969. ================
  970. idPVS::InCurrentPVS
  971. ================
  972. */
  973. bool idPVS::InCurrentPVS( const pvsHandle_t handle, const int targetArea ) const {
  974. if ( handle.i < 0 || handle.i >= MAX_CURRENT_PVS ||
  975. handle.h != currentPVS[handle.i].handle.h ) {
  976. gameLocal.Warning( "idPVS::InCurrentPVS: invalid handle" );
  977. return false;
  978. }
  979. if ( targetArea < 0 || targetArea >= numAreas ) {
  980. return false;
  981. }
  982. return ( ( currentPVS[handle.i].pvs[targetArea>>3] & (1 << (targetArea&7)) ) != 0 );
  983. }
  984. /*
  985. ================
  986. idPVS::InCurrentPVS
  987. ================
  988. */
  989. bool idPVS::InCurrentPVS( const pvsHandle_t handle, const int *targetAreas, int numTargetAreas ) const {
  990. int i;
  991. if ( handle.i < 0 || handle.i >= MAX_CURRENT_PVS ||
  992. handle.h != currentPVS[handle.i].handle.h ) {
  993. gameLocal.Warning( "idPVS::InCurrentPVS: invalid handle" );
  994. return false;
  995. }
  996. for ( i = 0; i < numTargetAreas; i++ ) {
  997. if ( targetAreas[i] < 0 || targetAreas[i] >= numAreas ) {
  998. continue;
  999. }
  1000. if ( currentPVS[handle.i].pvs[targetAreas[i]>>3] & (1 << (targetAreas[i]&7)) ) {
  1001. return true;
  1002. }
  1003. }
  1004. return false;
  1005. }
  1006. /*
  1007. ================
  1008. idPVS::DrawPVS
  1009. ================
  1010. */
  1011. void idPVS::DrawPVS( const idVec3 &source, const pvsType_t type ) const {
  1012. int i, j, k, numPoints, n, sourceArea;
  1013. exitPortal_t portal;
  1014. idPlane plane;
  1015. idVec3 offset;
  1016. idVec4 *color;
  1017. pvsHandle_t handle;
  1018. sourceArea = gameRenderWorld->PointInArea( source );
  1019. if ( sourceArea == -1 ) {
  1020. return;
  1021. }
  1022. handle = SetupCurrentPVS( source, type );
  1023. for ( j = 0; j < numAreas; j++ ) {
  1024. if ( !( currentPVS[handle.i].pvs[j>>3] & (1 << (j&7)) ) ) {
  1025. continue;
  1026. }
  1027. if ( j == sourceArea ) {
  1028. color = &colorRed;
  1029. }
  1030. else {
  1031. color = &colorCyan;
  1032. }
  1033. n = gameRenderWorld->NumPortalsInArea( j );
  1034. // draw all the portals of the area
  1035. for ( i = 0; i < n; i++ ) {
  1036. portal = gameRenderWorld->GetPortal( j, i );
  1037. numPoints = portal.w->GetNumPoints();
  1038. portal.w->GetPlane( plane );
  1039. offset = plane.Normal() * 4.0f;
  1040. for ( k = 0; k < numPoints; k++ ) {
  1041. gameRenderWorld->DebugLine( *color, (*portal.w)[k].ToVec3() + offset, (*portal.w)[(k+1)%numPoints].ToVec3() + offset );
  1042. }
  1043. }
  1044. }
  1045. FreeCurrentPVS( handle );
  1046. }
  1047. /*
  1048. ================
  1049. idPVS::DrawPVS
  1050. ================
  1051. */
  1052. void idPVS::DrawPVS( const idBounds &source, const pvsType_t type ) const {
  1053. int i, j, k, numPoints, n, num, areas[MAX_BOUNDS_AREAS];
  1054. exitPortal_t portal;
  1055. idPlane plane;
  1056. idVec3 offset;
  1057. idVec4 *color;
  1058. pvsHandle_t handle;
  1059. num = gameRenderWorld->BoundsInAreas( source, areas, MAX_BOUNDS_AREAS );
  1060. if ( !num ) {
  1061. return;
  1062. }
  1063. handle = SetupCurrentPVS( source, type );
  1064. for ( j = 0; j < numAreas; j++ ) {
  1065. if ( !( currentPVS[handle.i].pvs[j>>3] & (1 << (j&7)) ) ) {
  1066. continue;
  1067. }
  1068. for ( i = 0; i < num; i++ ) {
  1069. if ( j == areas[i] ) {
  1070. break;
  1071. }
  1072. }
  1073. if ( i < num ) {
  1074. color = &colorRed;
  1075. }
  1076. else {
  1077. color = &colorCyan;
  1078. }
  1079. n = gameRenderWorld->NumPortalsInArea( j );
  1080. // draw all the portals of the area
  1081. for ( i = 0; i < n; i++ ) {
  1082. portal = gameRenderWorld->GetPortal( j, i );
  1083. numPoints = portal.w->GetNumPoints();
  1084. portal.w->GetPlane( plane );
  1085. offset = plane.Normal() * 4.0f;
  1086. for ( k = 0; k < numPoints; k++ ) {
  1087. gameRenderWorld->DebugLine( *color, (*portal.w)[k].ToVec3() + offset, (*portal.w)[(k+1)%numPoints].ToVec3() + offset );
  1088. }
  1089. }
  1090. }
  1091. FreeCurrentPVS( handle );
  1092. }
  1093. /*
  1094. ================
  1095. idPVS::DrawPVS
  1096. ================
  1097. */
  1098. void idPVS::DrawCurrentPVS( const pvsHandle_t handle, const idVec3 &source ) const {
  1099. int i, j, k, numPoints, n, sourceArea;
  1100. exitPortal_t portal;
  1101. idPlane plane;
  1102. idVec3 offset;
  1103. idVec4 *color;
  1104. if ( handle.i < 0 || handle.i >= MAX_CURRENT_PVS ||
  1105. handle.h != currentPVS[handle.i].handle.h ) {
  1106. gameLocal.Error( "idPVS::DrawCurrentPVS: invalid handle" );
  1107. return;
  1108. }
  1109. sourceArea = gameRenderWorld->PointInArea( source );
  1110. if ( sourceArea == -1 ) {
  1111. return;
  1112. }
  1113. for ( j = 0; j < numAreas; j++ ) {
  1114. if ( !( currentPVS[handle.i].pvs[j>>3] & (1 << (j&7)) ) ) {
  1115. continue;
  1116. }
  1117. if ( j == sourceArea ) {
  1118. color = &colorRed;
  1119. }
  1120. else {
  1121. color = &colorCyan;
  1122. }
  1123. n = gameRenderWorld->NumPortalsInArea( j );
  1124. // draw all the portals of the area
  1125. for ( i = 0; i < n; i++ ) {
  1126. portal = gameRenderWorld->GetPortal( j, i );
  1127. numPoints = portal.w->GetNumPoints();
  1128. portal.w->GetPlane( plane );
  1129. offset = plane.Normal() * 4.0f;
  1130. for ( k = 0; k < numPoints; k++ ) {
  1131. gameRenderWorld->DebugLine( *color, (*portal.w)[k].ToVec3() + offset, (*portal.w)[(k+1)%numPoints].ToVec3() + offset );
  1132. }
  1133. }
  1134. }
  1135. }
  1136. /*
  1137. ================
  1138. idPVS::CheckAreasForPortalSky
  1139. ================
  1140. */
  1141. bool idPVS::CheckAreasForPortalSky( const pvsHandle_t handle, const idVec3 &origin ) {
  1142. int j, sourceArea;
  1143. if ( handle.i < 0 || handle.i >= MAX_CURRENT_PVS || handle.h != currentPVS[handle.i].handle.h ) {
  1144. return false;
  1145. }
  1146. sourceArea = gameRenderWorld->PointInArea( origin );
  1147. if ( sourceArea == -1 ) {
  1148. return false;
  1149. }
  1150. for ( j = 0; j < numAreas; j++ ) {
  1151. if ( !( currentPVS[handle.i].pvs[j>>3] & (1 << (j&7)) ) ) {
  1152. continue;
  1153. }
  1154. if ( gameRenderWorld->CheckAreaForPortalSky( j ) ) {
  1155. return true;
  1156. }
  1157. }
  1158. return false;
  1159. }