1 /*
2 * portals.c
3 * $Id: portals.c,v 1.9 2007-12-14 16:41:25 sezero Exp $
4 *
5 * Copyright (C) 1996-1997 Id Software, Inc.
6 * Copyright (C) 1997-1998 Raven Software Corp.
7 *
8 * This program is free software; you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License as published by
10 * the Free Software Foundation; either version 2 of the License, or (at
11 * your option) any later version.
12 *
13 * This program is distributed in the hope that it will be useful, but
14 * WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
16 *
17 * See the GNU General Public License for more details.
18 *
19 * You should have received a copy of the GNU General Public License along
20 * with this program; if not, write to the Free Software Foundation, Inc.,
21 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
22 */
23
24 #include "q_stdinc.h"
25 #include "compiler.h"
26 #include "arch_def.h"
27 #include "cmdlib.h"
28 #include "mathlib.h"
29 #include "bspfile.h"
30 #include "bsp5.h"
31
32
33 node_t outside_node; // portals outside the world face this
34
35 //=============================================================================
36
37 /*
38 =============
39 AddPortalToNodes
40 =============
41 */
AddPortalToNodes(portal_t * p,node_t * front,node_t * back)42 static void AddPortalToNodes (portal_t *p, node_t *front, node_t *back)
43 {
44 if (p->nodes[0] || p->nodes[1])
45 COM_Error ("%s: already included", __thisfunc__);
46
47 p->nodes[0] = front;
48 p->next[0] = front->portals;
49 front->portals = p;
50
51 p->nodes[1] = back;
52 p->next[1] = back->portals;
53 back->portals = p;
54 }
55
56
57 /*
58 =============
59 RemovePortalFromNode
60 =============
61 */
RemovePortalFromNode(portal_t * portal,node_t * l)62 static void RemovePortalFromNode (portal_t *portal, node_t *l)
63 {
64 portal_t **pp, *t;
65
66 // remove reference to the current portal
67 pp = &l->portals;
68 while (1)
69 {
70 t = *pp;
71 if (!t)
72 COM_Error ("%s: portal not in leaf", __thisfunc__);
73
74 if (t == portal)
75 break;
76
77 if (t->nodes[0] == l)
78 pp = &t->next[0];
79 else if (t->nodes[1] == l)
80 pp = &t->next[1];
81 else
82 COM_Error ("%s: portal not bounding leaf", __thisfunc__);
83 }
84
85 if (portal->nodes[0] == l)
86 {
87 *pp = portal->next[0];
88 portal->nodes[0] = NULL;
89 }
90 else if (portal->nodes[1] == l)
91 {
92 *pp = portal->next[1];
93 portal->nodes[1] = NULL;
94 }
95 }
96
97 //============================================================================
98
99 #if 0 // no users
100 void PrintPortal (portal_t *p)
101 {
102 int i;
103 winding_t *w;
104
105 w = p->winding;
106 for (i = 0 ; i < w->numpoints ; i++)
107 printf ("(%5.0f,%5.0f,%5.0f)\n",w->points[i][0],
108 w->points[i][1], w->points[i][2]);
109 }
110 #endif
111
112 /*
113 ================
114 MakeHeadnodePortals
115
116 The created portals will face the global outside_node
117 ================
118 */
MakeHeadnodePortals(node_t * node)119 static void MakeHeadnodePortals (node_t *node)
120 {
121 vec3_t bounds[2];
122 int i, j, n;
123 portal_t *p, *portals[6];
124 plane_t bplanes[6], *pl;
125 int side;
126
127 Draw_ClearWindow ();
128
129 // pad with some space so there will never be null volume leafs
130 for (i = 0 ; i < 3 ; i++)
131 {
132 bounds[0][i] = brushset->mins[i] - SIDESPACE;
133 bounds[1][i] = brushset->maxs[i] + SIDESPACE;
134 }
135
136 outside_node.contents = CONTENTS_SOLID;
137 outside_node.portals = NULL;
138
139 for (i = 0 ; i < 3 ; i++)
140 {
141 for (j = 0 ; j < 2 ; j++)
142 {
143 n = j*3 + i;
144
145 p = AllocPortal ();
146 portals[n] = p;
147
148 pl = &bplanes[n];
149 memset (pl, 0, sizeof(*pl));
150 if (j)
151 {
152 pl->normal[i] = -1;
153 pl->dist = -bounds[j][i];
154 }
155 else
156 {
157 pl->normal[i] = 1;
158 pl->dist = bounds[j][i];
159 }
160 p->planenum = FindPlane (pl, &side);
161
162 p->winding = BaseWindingForPlane (pl);
163 if (side)
164 AddPortalToNodes (p, &outside_node, node);
165 else
166 AddPortalToNodes (p, node, &outside_node);
167 }
168 }
169
170 // clip the basewindings by all the other planes
171 for (i = 0 ; i < 6 ; i++)
172 {
173 for (j = 0 ; j < 6 ; j++)
174 {
175 if (j == i)
176 continue;
177 portals[i]->winding = ClipWinding (portals[i]->winding, &bplanes[j], true);
178 }
179 }
180 }
181
182 //============================================================================
183
PlaneFromWinding(winding_t * w,plane_t * plane)184 static void PlaneFromWinding (winding_t *w, plane_t *plane)
185 {
186 vec3_t v1, v2;
187
188 // calc plane
189 VectorSubtract (w->points[2], w->points[1], v1);
190 VectorSubtract (w->points[0], w->points[1], v2);
191 CrossProduct (v2, v1, plane->normal);
192 VectorNormalize (plane->normal);
193 plane->dist = DotProduct (w->points[0], plane->normal);
194 }
195
196 #if 0 // all uses are commented out
197 static void CheckWindingInNode (winding_t *w, node_t *node)
198 {
199 int i, j;
200
201 for (i = 0 ; i < w->numpoints ; i++)
202 {
203 for (j = 0 ; j < 3 ; j++)
204 {
205 if (w->points[i][j] < node->mins[j] - 1
206 || w->points[i][j] > node->maxs[j] + 1)
207 {
208 printf ("WARNING: %s: outside\n", __thisfunc__);
209 return;
210 }
211 }
212 }
213 }
214
215 static void CheckWindingArea (winding_t *w)
216 {
217 int i;
218 float total, add;
219 vec3_t v1, v2, cross;
220
221 total = 0.0F;
222 for (i = 1 ; i < w->numpoints ; i++)
223 {
224 VectorSubtract (w->points[i], w->points[0], v1);
225 VectorSubtract (w->points[i+1], w->points[0], v2);
226 CrossProduct (v1, v2, cross);
227 add = VectorLength (cross);
228 total += add*0.5;
229 }
230 if (total < 16)
231 printf ("WARNING: winding area %f\n", total);
232 }
233
234 static void CheckLeafPortalConsistancy (node_t *node)
235 {
236 int side, side2;
237 portal_t *p, *p2;
238 plane_t plane, plane2;
239 int i;
240 winding_t *w;
241 float dist;
242
243 side = side2 = 0; // quiet compiler warning
244
245 for (p = node->portals ; p ; p = p->next[side])
246 {
247 if (p->nodes[0] == node)
248 side = 0;
249 else if (p->nodes[1] == node)
250 side = 1;
251 else
252 COM_Error ("%s: mislinked portal", __thisfunc__);
253 CheckWindingInNode (p->winding, node);
254 CheckWindingArea (p->winding);
255
256 // check that the side orders are correct
257 plane = planes[p->planenum];
258 PlaneFromWinding (p->winding, &plane2);
259
260 for (p2 = node->portals ; p2 ; p2 = p2->next[side2])
261 {
262 if (p2->nodes[0] == node)
263 side2 = 0;
264 else if (p2->nodes[1] == node)
265 side2 = 1;
266 else
267 COM_Error ("%s: mislinked portal", __thisfunc__);
268 w = p2->winding;
269 for (i = 0 ; i < w->numpoints ; i++)
270 {
271 dist = DotProduct (w->points[i], plane.normal) - plane.dist;
272 if ( (side == 0 && dist < -1) || (side == 1 && dist > 1) )
273 {
274 printf ("WARNING: portal siding direction is wrong\n");
275 return;
276 }
277 }
278 }
279 }
280 }
281 #endif
282
283 //============================================================================
284
285 /*
286 ================
287 CutNodePortals_r
288
289 ================
290 */
CutNodePortals_r(node_t * node)291 static void CutNodePortals_r (node_t *node)
292 {
293 plane_t *plane, clipplane;
294 node_t *f, *b, *other_node;
295 portal_t *p, *new_portal, *next_portal;
296 winding_t *w, *frontwinding, *backwinding;
297 int side;
298
299 // CheckLeafPortalConsistancy (node);
300
301 //
302 // seperate the portals on node into it's children
303 //
304 if (node->contents)
305 {
306 return; // at a leaf, no more dividing
307 }
308
309 plane = &planes[node->planenum];
310
311 f = node->children[0];
312 b = node->children[1];
313
314 //
315 // create the new portal by taking the full plane winding for the cutting plane
316 // and clipping it by all of the planes from the other portals
317 //
318 new_portal = AllocPortal ();
319 new_portal->planenum = node->planenum;
320
321 w = BaseWindingForPlane (&planes[node->planenum]);
322 for (p = node->portals ; p ; p = p->next[side])
323 {
324 clipplane = planes[p->planenum];
325 if (p->nodes[0] == node)
326 side = 0;
327 else if (p->nodes[1] == node)
328 {
329 clipplane.dist = -clipplane.dist;
330 VectorNegate (clipplane.normal, clipplane.normal);
331 side = 1;
332 }
333 else
334 {
335 COM_Error ("%s: mislinked portal", __thisfunc__);
336 return; /* silence compiler */
337 }
338
339 w = ClipWinding (w, &clipplane, true);
340 if (!w)
341 {
342 printf ("WARNING: %s: new portal was clipped away\n", __thisfunc__);
343 break;
344 }
345 }
346
347 if (w)
348 {
349 // if the plane was not clipped on all sides, there was an error
350 new_portal->winding = w;
351 AddPortalToNodes (new_portal, f, b);
352 }
353
354 //
355 // partition the portals
356 //
357 for (p = node->portals ; p ; p = next_portal)
358 {
359 if (p->nodes[0] == node)
360 side = 0;
361 else if (p->nodes[1] == node)
362 side = 1;
363 else
364 COM_Error ("%s: mislinked portal", __thisfunc__);
365 next_portal = p->next[side];
366
367 other_node = p->nodes[!side];
368 RemovePortalFromNode (p, p->nodes[0]);
369 RemovePortalFromNode (p, p->nodes[1]);
370
371 //
372 // cut the portal into two portals, one on each side of the cut plane
373 //
374 DivideWinding (p->winding, plane, &frontwinding, &backwinding);
375
376 if (!frontwinding)
377 {
378 if (side == 0)
379 AddPortalToNodes (p, b, other_node);
380 else
381 AddPortalToNodes (p, other_node, b);
382 continue;
383 }
384 if (!backwinding)
385 {
386 if (side == 0)
387 AddPortalToNodes (p, f, other_node);
388 else
389 AddPortalToNodes (p, other_node, f);
390 continue;
391 }
392
393 // the winding is split
394 new_portal = AllocPortal ();
395 *new_portal = *p;
396 new_portal->winding = backwinding;
397 FreeWinding (p->winding);
398 p->winding = frontwinding;
399
400 if (side == 0)
401 {
402 AddPortalToNodes (p, f, other_node);
403 AddPortalToNodes (new_portal, b, other_node);
404 }
405 else
406 {
407 AddPortalToNodes (p, other_node, f);
408 AddPortalToNodes (new_portal, other_node, b);
409 }
410 }
411
412 DrawLeaf (f,1);
413 DrawLeaf (b,2);
414
415 CutNodePortals_r (f);
416 CutNodePortals_r (b);
417 }
418
419
420 /*
421 ==================
422 PortalizeWorld
423
424 Builds the exact polyhedrons for the nodes and leafs
425 ==================
426 */
PortalizeWorld(node_t * headnode)427 void PortalizeWorld (node_t *headnode)
428 {
429 qprintf ("----- portalize ----\n");
430
431 MakeHeadnodePortals (headnode);
432 CutNodePortals_r (headnode);
433 }
434
435
436 /*
437 ==================
438 FreeAllPortals
439
440 ==================
441 */
FreeAllPortals(node_t * node)442 void FreeAllPortals (node_t *node)
443 {
444 portal_t *p, *nextp;
445
446 if (!node->contents)
447 {
448 FreeAllPortals (node->children[0]);
449 FreeAllPortals (node->children[1]);
450 }
451
452 for (p = node->portals ; p ; p = nextp)
453 {
454 if (p->nodes[0] == node)
455 nextp = p->next[0];
456 else
457 nextp = p->next[1];
458 RemovePortalFromNode (p, p->nodes[0]);
459 RemovePortalFromNode (p, p->nodes[1]);
460 FreeWinding (p->winding);
461 FreePortal (p);
462 }
463 }
464
465 /*
466 ==============================================================================
467
468 PORTAL FILE GENERATION
469
470 ==============================================================================
471 */
472
473 #define PORTALFILE "PRT1"
474
475 static FILE *pf;
476 static int num_visleafs; // leafs the player can be in
477 static int num_visportals;
478
WriteFloat(FILE * f,double v)479 static void WriteFloat (FILE *f, double v)
480 {
481 if ( fabs(v - Q_rint(v)) < 0.001 )
482 fprintf (f,"%i ",(int)Q_rint(v));
483 else
484 fprintf (f,"%f ",v);
485 }
486
487 extern qboolean watervis;
488
WritePortalFile_r(node_t * node)489 static void WritePortalFile_r (node_t *node)
490 {
491 int i;
492 portal_t *p;
493 winding_t *w;
494 plane_t *pl, plane2;
495
496 if (!node->contents)
497 {
498 WritePortalFile_r (node->children[0]);
499 WritePortalFile_r (node->children[1]);
500 return;
501 }
502
503 if (node->contents == CONTENTS_SOLID)
504 return;
505
506 for (p = node->portals ; p ; )
507 {
508 w = p->winding;
509 if (w && p->nodes[0] == node)
510 {
511 if ( (watervis &&
512 ((p->nodes[0]->contents == CONTENTS_WATER && p->nodes[1]->contents == CONTENTS_EMPTY) ||
513 (p->nodes[0]->contents == CONTENTS_EMPTY && p->nodes[1]->contents == CONTENTS_WATER)) )
514 || (p->nodes[0]->contents == p->nodes[1]->contents) )
515 {
516 // write out to the file
517
518 // sometimes planes get turned around when they are very near
519 // the changeover point between different axis. interpret the
520 // plane the same way vis will, and flip the side orders if needed
521 pl = &planes[p->planenum];
522 PlaneFromWinding (w, &plane2);
523 if ( DotProduct (pl->normal, plane2.normal) < 0.99 )
524 { // backwards...
525 fprintf (pf,"%i %i %i ",w->numpoints, p->nodes[1]->visleafnum, p->nodes[0]->visleafnum);
526 }
527 else
528 fprintf (pf,"%i %i %i ",w->numpoints, p->nodes[0]->visleafnum, p->nodes[1]->visleafnum);
529 for (i = 0 ; i < w->numpoints ; i++)
530 {
531 fprintf (pf,"(");
532 WriteFloat (pf, w->points[i][0]);
533 WriteFloat (pf, w->points[i][1]);
534 WriteFloat (pf, w->points[i][2]);
535 fprintf (pf,") ");
536 }
537 fprintf (pf,"\n");
538 }
539 }
540
541 if (p->nodes[0] == node)
542 p = p->next[0];
543 else
544 p = p->next[1];
545 }
546 }
547
548 /*
549 ================
550 NumberLeafs_r
551 ================
552 */
NumberLeafs_r(node_t * node)553 static void NumberLeafs_r (node_t *node)
554 {
555 portal_t *p;
556
557 if (!node->contents)
558 { // decision node
559 node->visleafnum = -99;
560 NumberLeafs_r (node->children[0]);
561 NumberLeafs_r (node->children[1]);
562 return;
563 }
564
565 Draw_ClearWindow ();
566 DrawLeaf (node, 1);
567
568 if (node->contents == CONTENTS_SOLID)
569 { // solid block, viewpoint never inside
570 node->visleafnum = -1;
571 return;
572 }
573
574 node->visleafnum = num_visleafs++;
575
576 for (p = node->portals ; p ; )
577 {
578 if (p->nodes[0] == node) // only write out from first leaf
579 {
580 if ( (watervis &&
581 ((p->nodes[0]->contents == CONTENTS_WATER && p->nodes[1]->contents == CONTENTS_EMPTY) ||
582 (p->nodes[0]->contents == CONTENTS_EMPTY && p->nodes[1]->contents == CONTENTS_WATER)) )
583 || (p->nodes[0]->contents == p->nodes[1]->contents) )
584 num_visportals++;
585
586 p = p->next[0];
587 }
588 else
589 p = p->next[1];
590 }
591 }
592
593
594 /*
595 ================
596 WritePortalfile
597 ================
598 */
WritePortalfile(node_t * headnode)599 void WritePortalfile (node_t *headnode)
600 {
601 // set the visleafnum field in every leaf and count the total number of portals
602 num_visleafs = 0;
603 num_visportals = 0;
604 NumberLeafs_r (headnode);
605
606 // write the file
607 printf ("writing %s\n", portfilename);
608 pf = fopen (portfilename, "w");
609 if (!pf)
610 COM_Error ("Error opening %s", portfilename);
611
612 fprintf (pf, "%s\n", PORTALFILE);
613 fprintf (pf, "%i\n", num_visleafs);
614 fprintf (pf, "%i\n", num_visportals);
615
616 WritePortalFile_r (headnode);
617
618 fclose (pf);
619 }
620
621