1 /*
2 ===========================================================================
3 Copyright (C) 1997-2006 Id Software, Inc.
4
5 This file is part of Quake 2 Tools source code.
6
7 Quake 2 Tools source code is free software; you can redistribute it
8 and/or modify it under the terms of the GNU General Public License as
9 published by the Free Software Foundation; either version 2 of the License,
10 or (at your option) any later version.
11
12 Quake 2 Tools source code is distributed in the hope that it will be
13 useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with Quake 2 Tools source code; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
20 ===========================================================================
21 */
22
23 #include "qbsp.h"
24
25
26 int c_nodes;
27 int c_nonvis;
28 int c_active_brushes;
29
30 // if a brush just barely pokes onto the other side,
31 // let it slide by without chopping
32 #define PLANESIDE_EPSILON 0.001
33 //0.1
34
35 #define PSIDE_FRONT 1
36 #define PSIDE_BACK 2
37 #define PSIDE_BOTH (PSIDE_FRONT|PSIDE_BACK)
38 #define PSIDE_FACING 4
39
40
FindBrushInTree(node_t * node,int brushnum)41 void FindBrushInTree (node_t *node, int brushnum)
42 {
43 bspbrush_t *b;
44
45 if (node->planenum == PLANENUM_LEAF)
46 {
47 for (b=node->brushlist ; b ; b=b->next)
48 if (b->original->brushnum == brushnum)
49 printf ("here\n");
50 return;
51 }
52 FindBrushInTree (node->children[0], brushnum);
53 FindBrushInTree (node->children[1], brushnum);
54 }
55
56 //==================================================
57
58 /*
59 ================
60 DrawBrushList
61 ================
62 */
DrawBrushList(bspbrush_t * brush,node_t * node)63 void DrawBrushList (bspbrush_t *brush, node_t *node)
64 {
65 int i;
66 side_t *s;
67
68 GLS_BeginScene ();
69 for ( ; brush ; brush=brush->next)
70 {
71 for (i=0 ; i<brush->numsides ; i++)
72 {
73 s = &brush->sides[i];
74 if (!s->winding)
75 continue;
76 if (s->texinfo == TEXINFO_NODE)
77 GLS_Winding (s->winding, 1);
78 else if (!s->visible)
79 GLS_Winding (s->winding, 2);
80 else
81 GLS_Winding (s->winding, 0);
82 }
83 }
84 GLS_EndScene ();
85 }
86
87 /*
88 ================
89 WriteBrushList
90 ================
91 */
WriteBrushList(char * name,bspbrush_t * brush,qboolean onlyvis)92 void WriteBrushList (char *name, bspbrush_t *brush, qboolean onlyvis)
93 {
94 int i;
95 side_t *s;
96 FILE *f;
97
98 qprintf ("writing %s\n", name);
99 f = SafeOpenWrite (name);
100
101 for ( ; brush ; brush=brush->next)
102 {
103 for (i=0 ; i<brush->numsides ; i++)
104 {
105 s = &brush->sides[i];
106 if (!s->winding)
107 continue;
108 if (onlyvis && !s->visible)
109 continue;
110 OutputWinding (brush->sides[i].winding, f);
111 }
112 }
113
114 fclose (f);
115 }
116
PrintBrush(bspbrush_t * brush)117 void PrintBrush (bspbrush_t *brush)
118 {
119 int i;
120
121 printf ("brush: %p\n", brush);
122 for (i=0;i<brush->numsides ; i++)
123 {
124 pw(brush->sides[i].winding);
125 printf ("\n");
126 }
127 }
128
129 /*
130 ==================
131 BoundBrush
132
133 Sets the mins/maxs based on the windings
134 ==================
135 */
BoundBrush(bspbrush_t * brush)136 void BoundBrush (bspbrush_t *brush)
137 {
138 int i, j;
139 winding_t *w;
140
141 ClearBounds (brush->mins, brush->maxs);
142 for (i=0 ; i<brush->numsides ; i++)
143 {
144 w = brush->sides[i].winding;
145 if (!w)
146 continue;
147 for (j=0 ; j<w->numpoints ; j++)
148 AddPointToBounds (w->p[j], brush->mins, brush->maxs);
149 }
150 }
151
152 /*
153 ==================
154 CreateBrushWindings
155
156 ==================
157 */
CreateBrushWindings(bspbrush_t * brush)158 void CreateBrushWindings (bspbrush_t *brush)
159 {
160 int i, j;
161 winding_t *w;
162 side_t *side;
163 plane_t *plane;
164
165 for (i=0 ; i<brush->numsides ; i++)
166 {
167 side = &brush->sides[i];
168 plane = &mapplanes[side->planenum];
169 w = BaseWindingForPlane (plane->normal, plane->dist);
170 for (j=0 ; j<brush->numsides && w; j++)
171 {
172 if (i == j)
173 continue;
174 if (brush->sides[j].bevel)
175 continue;
176 plane = &mapplanes[brush->sides[j].planenum^1];
177 ChopWindingInPlace (&w, plane->normal, plane->dist, 0); //CLIP_EPSILON);
178 }
179
180 side->winding = w;
181 }
182
183 BoundBrush (brush);
184 }
185
186 /*
187 ==================
188 BrushFromBounds
189
190 Creates a new axial brush
191 ==================
192 */
BrushFromBounds(vec3_t mins,vec3_t maxs)193 bspbrush_t *BrushFromBounds (vec3_t mins, vec3_t maxs)
194 {
195 bspbrush_t *b;
196 int i;
197 vec3_t normal;
198 vec_t dist;
199
200 b = AllocBrush (6);
201 b->numsides = 6;
202 for (i=0 ; i<3 ; i++)
203 {
204 VectorClear (normal);
205 normal[i] = 1;
206 dist = maxs[i];
207 b->sides[i].planenum = FindFloatPlane (normal, dist);
208
209 normal[i] = -1;
210 dist = -mins[i];
211 b->sides[3+i].planenum = FindFloatPlane (normal, dist);
212 }
213
214 CreateBrushWindings (b);
215
216 return b;
217 }
218
219 /*
220 ==================
221 BrushVolume
222
223 ==================
224 */
BrushVolume(bspbrush_t * brush)225 vec_t BrushVolume (bspbrush_t *brush)
226 {
227 int i;
228 winding_t *w;
229 vec3_t corner;
230 vec_t d, area, volume;
231 plane_t *plane;
232
233 if (!brush)
234 return 0;
235
236 // grab the first valid point as the corner
237
238 w = NULL;
239 for (i=0 ; i<brush->numsides ; i++)
240 {
241 w = brush->sides[i].winding;
242 if (w)
243 break;
244 }
245 if (!w)
246 return 0;
247 VectorCopy (w->p[0], corner);
248
249 // make tetrahedrons to all other faces
250
251 volume = 0;
252 for ( ; i<brush->numsides ; i++)
253 {
254 w = brush->sides[i].winding;
255 if (!w)
256 continue;
257 plane = &mapplanes[brush->sides[i].planenum];
258 d = -(DotProduct (corner, plane->normal) - plane->dist);
259 area = WindingArea (w);
260 volume += d*area;
261 }
262
263 volume /= 3;
264 return volume;
265 }
266
267 /*
268 ================
269 CountBrushList
270 ================
271 */
CountBrushList(bspbrush_t * brushes)272 int CountBrushList (bspbrush_t *brushes)
273 {
274 int c;
275
276 c = 0;
277 for ( ; brushes ; brushes = brushes->next)
278 c++;
279 return c;
280 }
281
282 /*
283 ================
284 AllocTree
285 ================
286 */
AllocTree(void)287 tree_t *AllocTree (void)
288 {
289 tree_t *tree;
290
291 tree = malloc(sizeof(*tree));
292 memset (tree, 0, sizeof(*tree));
293 ClearBounds (tree->mins, tree->maxs);
294
295 return tree;
296 }
297
298 /*
299 ================
300 AllocNode
301 ================
302 */
AllocNode(void)303 node_t *AllocNode (void)
304 {
305 node_t *node;
306
307 node = malloc(sizeof(*node));
308 memset (node, 0, sizeof(*node));
309
310 return node;
311 }
312
313
314 /*
315 ================
316 AllocBrush
317 ================
318 */
AllocBrush(int numsides)319 bspbrush_t *AllocBrush (int numsides)
320 {
321 bspbrush_t *bb;
322 int c;
323
324 c = (int)&(((bspbrush_t *)0)->sides[numsides]);
325 bb = malloc(c);
326 memset (bb, 0, c);
327 if (numthreads == 1)
328 c_active_brushes++;
329 return bb;
330 }
331
332 /*
333 ================
334 FreeBrush
335 ================
336 */
FreeBrush(bspbrush_t * brushes)337 void FreeBrush (bspbrush_t *brushes)
338 {
339 int i;
340
341 for (i=0 ; i<brushes->numsides ; i++)
342 if (brushes->sides[i].winding)
343 FreeWinding(brushes->sides[i].winding);
344 free (brushes);
345 if (numthreads == 1)
346 c_active_brushes--;
347 }
348
349
350 /*
351 ================
352 FreeBrushList
353 ================
354 */
FreeBrushList(bspbrush_t * brushes)355 void FreeBrushList (bspbrush_t *brushes)
356 {
357 bspbrush_t *next;
358
359 for ( ; brushes ; brushes = next)
360 {
361 next = brushes->next;
362
363 FreeBrush (brushes);
364 }
365 }
366
367 /*
368 ==================
369 CopyBrush
370
371 Duplicates the brush, the sides, and the windings
372 ==================
373 */
CopyBrush(bspbrush_t * brush)374 bspbrush_t *CopyBrush (bspbrush_t *brush)
375 {
376 bspbrush_t *newbrush;
377 int size;
378 int i;
379
380 size = (int)&(((bspbrush_t *)0)->sides[brush->numsides]);
381
382 newbrush = AllocBrush (brush->numsides);
383 memcpy (newbrush, brush, size);
384
385 for (i=0 ; i<brush->numsides ; i++)
386 {
387 if (brush->sides[i].winding)
388 newbrush->sides[i].winding = CopyWinding (brush->sides[i].winding);
389 }
390
391 return newbrush;
392 }
393
394
395 /*
396 ==================
397 PointInLeaf
398
399 ==================
400 */
PointInLeaf(node_t * node,vec3_t point)401 node_t *PointInLeaf (node_t *node, vec3_t point)
402 {
403 vec_t d;
404 plane_t *plane;
405
406 while (node->planenum != PLANENUM_LEAF)
407 {
408 plane = &mapplanes[node->planenum];
409 d = DotProduct (point, plane->normal) - plane->dist;
410 if (d > 0)
411 node = node->children[0];
412 else
413 node = node->children[1];
414 }
415
416 return node;
417 }
418
419 //========================================================
420
421 /*
422 ==============
423 BoxOnPlaneSide
424
425 Returns PSIDE_FRONT, PSIDE_BACK, or PSIDE_BOTH
426 ==============
427 */
BoxOnPlaneSide(vec3_t mins,vec3_t maxs,plane_t * plane)428 int BoxOnPlaneSide (vec3_t mins, vec3_t maxs, plane_t *plane)
429 {
430 int side;
431 int i;
432 vec3_t corners[2];
433 vec_t dist1, dist2;
434
435 // axial planes are easy
436 if (plane->type < 3)
437 {
438 side = 0;
439 if (maxs[plane->type] > plane->dist+PLANESIDE_EPSILON)
440 side |= PSIDE_FRONT;
441 if (mins[plane->type] < plane->dist-PLANESIDE_EPSILON)
442 side |= PSIDE_BACK;
443 return side;
444 }
445
446 // create the proper leading and trailing verts for the box
447
448 for (i=0 ; i<3 ; i++)
449 {
450 if (plane->normal[i] < 0)
451 {
452 corners[0][i] = mins[i];
453 corners[1][i] = maxs[i];
454 }
455 else
456 {
457 corners[1][i] = mins[i];
458 corners[0][i] = maxs[i];
459 }
460 }
461
462 dist1 = DotProduct (plane->normal, corners[0]) - plane->dist;
463 dist2 = DotProduct (plane->normal, corners[1]) - plane->dist;
464 side = 0;
465 if (dist1 >= PLANESIDE_EPSILON)
466 side = PSIDE_FRONT;
467 if (dist2 < PLANESIDE_EPSILON)
468 side |= PSIDE_BACK;
469
470 return side;
471 }
472
473 /*
474 ============
475 QuickTestBrushToPlanenum
476
477 ============
478 */
QuickTestBrushToPlanenum(bspbrush_t * brush,int planenum,int * numsplits)479 int QuickTestBrushToPlanenum (bspbrush_t *brush, int planenum, int *numsplits)
480 {
481 int i, num;
482 plane_t *plane;
483 int s;
484
485 *numsplits = 0;
486
487 // if the brush actually uses the planenum,
488 // we can tell the side for sure
489 for (i=0 ; i<brush->numsides ; i++)
490 {
491 num = brush->sides[i].planenum;
492 if (num >= 0x10000)
493 Error ("bad planenum");
494 if (num == planenum)
495 return PSIDE_BACK|PSIDE_FACING;
496 if (num == (planenum ^ 1) )
497 return PSIDE_FRONT|PSIDE_FACING;
498 }
499
500 // box on plane side
501 plane = &mapplanes[planenum];
502 s = BoxOnPlaneSide (brush->mins, brush->maxs, plane);
503
504 // if both sides, count the visible faces split
505 if (s == PSIDE_BOTH)
506 {
507 *numsplits += 3;
508 }
509
510 return s;
511 }
512
513 /*
514 ============
515 TestBrushToPlanenum
516
517 ============
518 */
TestBrushToPlanenum(bspbrush_t * brush,int planenum,int * numsplits,qboolean * hintsplit,int * epsilonbrush)519 int TestBrushToPlanenum (bspbrush_t *brush, int planenum,
520 int *numsplits, qboolean *hintsplit, int *epsilonbrush)
521 {
522 int i, j, num;
523 plane_t *plane;
524 int s;
525 winding_t *w;
526 vec_t d, d_front, d_back;
527 int front, back;
528
529 *numsplits = 0;
530 *hintsplit = false;
531
532 // if the brush actually uses the planenum,
533 // we can tell the side for sure
534 for (i=0 ; i<brush->numsides ; i++)
535 {
536 num = brush->sides[i].planenum;
537 if (num >= 0x10000)
538 Error ("bad planenum");
539 if (num == planenum)
540 return PSIDE_BACK|PSIDE_FACING;
541 if (num == (planenum ^ 1) )
542 return PSIDE_FRONT|PSIDE_FACING;
543 }
544
545 // box on plane side
546 plane = &mapplanes[planenum];
547 s = BoxOnPlaneSide (brush->mins, brush->maxs, plane);
548
549 if (s != PSIDE_BOTH)
550 return s;
551
552 // if both sides, count the visible faces split
553 d_front = d_back = 0;
554
555 for (i=0 ; i<brush->numsides ; i++)
556 {
557 if (brush->sides[i].texinfo == TEXINFO_NODE)
558 continue; // on node, don't worry about splits
559 if (!brush->sides[i].visible)
560 continue; // we don't care about non-visible
561 w = brush->sides[i].winding;
562 if (!w)
563 continue;
564 front = back = 0;
565 for (j=0 ; j<w->numpoints; j++)
566 {
567 d = DotProduct (w->p[j], plane->normal) - plane->dist;
568 if (d > d_front)
569 d_front = d;
570 if (d < d_back)
571 d_back = d;
572
573 if (d > 0.1) // PLANESIDE_EPSILON)
574 front = 1;
575 if (d < -0.1) // PLANESIDE_EPSILON)
576 back = 1;
577 }
578 if (front && back)
579 {
580 if ( !(brush->sides[i].surf & SURF_SKIP) )
581 {
582 (*numsplits)++;
583 if (brush->sides[i].surf & SURF_HINT)
584 *hintsplit = true;
585 }
586 }
587 }
588
589 if ( (d_front > 0.0 && d_front < 1.0)
590 || (d_back < 0.0 && d_back > -1.0) )
591 (*epsilonbrush)++;
592
593 #if 0
594 if (*numsplits == 0)
595 { // didn't really need to be split
596 if (front)
597 s = PSIDE_FRONT;
598 else if (back)
599 s = PSIDE_BACK;
600 else
601 s = 0;
602 }
603 #endif
604
605 return s;
606 }
607
608 //========================================================
609
610 /*
611 ================
612 WindingIsTiny
613
614 Returns true if the winding would be crunched out of
615 existance by the vertex snapping.
616 ================
617 */
618 #define EDGE_LENGTH 0.2
WindingIsTiny(winding_t * w)619 qboolean WindingIsTiny (winding_t *w)
620 {
621 #if 0
622 if (WindingArea (w) < 1)
623 return true;
624 return false;
625 #else
626 int i, j;
627 vec_t len;
628 vec3_t delta;
629 int edges;
630
631 edges = 0;
632 for (i=0 ; i<w->numpoints ; i++)
633 {
634 j = i == w->numpoints - 1 ? 0 : i+1;
635 VectorSubtract (w->p[j], w->p[i], delta);
636 len = VectorLength (delta);
637 if (len > EDGE_LENGTH)
638 {
639 if (++edges == 3)
640 return false;
641 }
642 }
643 return true;
644 #endif
645 }
646
647 /*
648 ================
649 WindingIsHuge
650
651 Returns true if the winding still has one of the points
652 from basewinding for plane
653 ================
654 */
WindingIsHuge(winding_t * w)655 qboolean WindingIsHuge (winding_t *w)
656 {
657 int i, j;
658
659 for (i=0 ; i<w->numpoints ; i++)
660 {
661 for (j=0 ; j<3 ; j++)
662 if (w->p[i][j] < -8000 || w->p[i][j] > 8000)
663 return true;
664 }
665 return false;
666 }
667
668 //============================================================
669
670 /*
671 ================
672 Leafnode
673 ================
674 */
LeafNode(node_t * node,bspbrush_t * brushes)675 void LeafNode (node_t *node, bspbrush_t *brushes)
676 {
677 bspbrush_t *b;
678 int i;
679
680 node->planenum = PLANENUM_LEAF;
681 node->contents = 0;
682
683 for (b=brushes ; b ; b=b->next)
684 {
685 // if the brush is solid and all of its sides are on nodes,
686 // it eats everything
687 if (b->original->contents & CONTENTS_SOLID)
688 {
689 for (i=0 ; i<b->numsides ; i++)
690 if (b->sides[i].texinfo != TEXINFO_NODE)
691 break;
692 if (i == b->numsides)
693 {
694 node->contents = CONTENTS_SOLID;
695 break;
696 }
697 }
698 node->contents |= b->original->contents;
699 }
700
701 node->brushlist = brushes;
702 }
703
704
705 //============================================================
706
CheckPlaneAgainstParents(int pnum,node_t * node)707 void CheckPlaneAgainstParents (int pnum, node_t *node)
708 {
709 node_t *p;
710
711 for (p=node->parent ; p ; p=p->parent)
712 {
713 if (p->planenum == pnum)
714 Error ("Tried parent");
715 }
716 }
717
CheckPlaneAgainstVolume(int pnum,node_t * node)718 qboolean CheckPlaneAgainstVolume (int pnum, node_t *node)
719 {
720 bspbrush_t *front, *back;
721 qboolean good;
722
723 SplitBrush (node->volume, pnum, &front, &back);
724
725 good = (front && back);
726
727 if (front)
728 FreeBrush (front);
729 if (back)
730 FreeBrush (back);
731
732 return good;
733 }
734
735 /*
736 ================
737 SelectSplitSide
738
739 Using a hueristic, choses one of the sides out of the brushlist
740 to partition the brushes with.
741 Returns NULL if there are no valid planes to split with..
742 ================
743 */
SelectSplitSide(bspbrush_t * brushes,node_t * node)744 side_t *SelectSplitSide (bspbrush_t *brushes, node_t *node)
745 {
746 int value, bestvalue;
747 bspbrush_t *brush, *test;
748 side_t *side, *bestside;
749 int i, j, pass, numpasses;
750 int pnum;
751 int s;
752 int front, back, both, facing, splits;
753 int bsplits;
754 int bestsplits;
755 int epsilonbrush;
756 qboolean hintsplit;
757
758 bestside = NULL;
759 bestvalue = -99999;
760 bestsplits = 0;
761
762 // the search order goes: visible-structural, visible-detail,
763 // nonvisible-structural, nonvisible-detail.
764 // If any valid plane is available in a pass, no further
765 // passes will be tried.
766 numpasses = 4;
767 for (pass = 0 ; pass < numpasses ; pass++)
768 {
769 for (brush = brushes ; brush ; brush=brush->next)
770 {
771 if ( (pass & 1) && !(brush->original->contents & CONTENTS_DETAIL) )
772 continue;
773 if ( !(pass & 1) && (brush->original->contents & CONTENTS_DETAIL) )
774 continue;
775 for (i=0 ; i<brush->numsides ; i++)
776 {
777 side = brush->sides + i;
778 if (side->bevel)
779 continue; // never use a bevel as a spliter
780 if (!side->winding)
781 continue; // nothing visible, so it can't split
782 if (side->texinfo == TEXINFO_NODE)
783 continue; // allready a node splitter
784 if (side->tested)
785 continue; // we allready have metrics for this plane
786 if (side->surf & SURF_SKIP)
787 continue; // skip surfaces are never chosen
788 if ( side->visible ^ (pass<2) )
789 continue; // only check visible faces on first pass
790
791 pnum = side->planenum;
792 pnum &= ~1; // allways use positive facing plane
793
794 CheckPlaneAgainstParents (pnum, node);
795
796 if (!CheckPlaneAgainstVolume (pnum, node))
797 continue; // would produce a tiny volume
798
799 front = 0;
800 back = 0;
801 both = 0;
802 facing = 0;
803 splits = 0;
804 epsilonbrush = 0;
805
806 for (test = brushes ; test ; test=test->next)
807 {
808 s = TestBrushToPlanenum (test, pnum, &bsplits, &hintsplit, &epsilonbrush);
809
810 splits += bsplits;
811 if (bsplits && (s&PSIDE_FACING) )
812 Error ("PSIDE_FACING with splits");
813
814 test->testside = s;
815 // if the brush shares this face, don't bother
816 // testing that facenum as a splitter again
817 if (s & PSIDE_FACING)
818 {
819 facing++;
820 for (j=0 ; j<test->numsides ; j++)
821 {
822 if ( (test->sides[j].planenum&~1) == pnum)
823 test->sides[j].tested = true;
824 }
825 }
826 if (s & PSIDE_FRONT)
827 front++;
828 if (s & PSIDE_BACK)
829 back++;
830 if (s == PSIDE_BOTH)
831 both++;
832 }
833
834 // give a value estimate for using this plane
835
836 value = 5*facing - 5*splits - abs(front-back);
837 // value = -5*splits;
838 // value = 5*facing - 5*splits;
839 if (mapplanes[pnum].type < 3)
840 value+=5; // axial is better
841 value -= epsilonbrush*1000; // avoid!
842
843 // never split a hint side except with another hint
844 if (hintsplit && !(side->surf & SURF_HINT) )
845 value = -9999999;
846
847 // save off the side test so we don't need
848 // to recalculate it when we actually seperate
849 // the brushes
850 if (value > bestvalue)
851 {
852 bestvalue = value;
853 bestside = side;
854 bestsplits = splits;
855 for (test = brushes ; test ; test=test->next)
856 test->side = test->testside;
857 }
858 }
859 }
860
861 // if we found a good plane, don't bother trying any
862 // other passes
863 if (bestside)
864 {
865 if (pass > 1)
866 {
867 if (numthreads == 1)
868 c_nonvis++;
869 }
870 if (pass > 0)
871 node->detail_seperator = true; // not needed for vis
872 break;
873 }
874 }
875
876 //
877 // clear all the tested flags we set
878 //
879 for (brush = brushes ; brush ; brush=brush->next)
880 {
881 for (i=0 ; i<brush->numsides ; i++)
882 brush->sides[i].tested = false;
883 }
884
885 return bestside;
886 }
887
888
889 /*
890 ==================
891 BrushMostlyOnSide
892
893 ==================
894 */
BrushMostlyOnSide(bspbrush_t * brush,plane_t * plane)895 int BrushMostlyOnSide (bspbrush_t *brush, plane_t *plane)
896 {
897 int i, j;
898 winding_t *w;
899 vec_t d, max;
900 int side;
901
902 max = 0;
903 side = PSIDE_FRONT;
904 for (i=0 ; i<brush->numsides ; i++)
905 {
906 w = brush->sides[i].winding;
907 if (!w)
908 continue;
909 for (j=0 ; j<w->numpoints ; j++)
910 {
911 d = DotProduct (w->p[j], plane->normal) - plane->dist;
912 if (d > max)
913 {
914 max = d;
915 side = PSIDE_FRONT;
916 }
917 if (-d > max)
918 {
919 max = -d;
920 side = PSIDE_BACK;
921 }
922 }
923 }
924 return side;
925 }
926
927 /*
928 ================
929 SplitBrush
930
931 Generates two new brushes, leaving the original
932 unchanged
933 ================
934 */
SplitBrush(bspbrush_t * brush,int planenum,bspbrush_t ** front,bspbrush_t ** back)935 void SplitBrush (bspbrush_t *brush, int planenum,
936 bspbrush_t **front, bspbrush_t **back)
937 {
938 bspbrush_t *b[2];
939 int i, j;
940 winding_t *w, *cw[2], *midwinding;
941 plane_t *plane, *plane2;
942 side_t *s, *cs;
943 float d, d_front, d_back;
944
945 *front = *back = NULL;
946 plane = &mapplanes[planenum];
947
948 // check all points
949 d_front = d_back = 0;
950 for (i=0 ; i<brush->numsides ; i++)
951 {
952 w = brush->sides[i].winding;
953 if (!w)
954 continue;
955 for (j=0 ; j<w->numpoints ; j++)
956 {
957 d = DotProduct (w->p[j], plane->normal) - plane->dist;
958 if (d > 0 && d > d_front)
959 d_front = d;
960 if (d < 0 && d < d_back)
961 d_back = d;
962 }
963 }
964 if (d_front < 0.1) // PLANESIDE_EPSILON)
965 { // only on back
966 *back = CopyBrush (brush);
967 return;
968 }
969 if (d_back > -0.1) // PLANESIDE_EPSILON)
970 { // only on front
971 *front = CopyBrush (brush);
972 return;
973 }
974
975 // create a new winding from the split plane
976
977 w = BaseWindingForPlane (plane->normal, plane->dist);
978 for (i=0 ; i<brush->numsides && w ; i++)
979 {
980 plane2 = &mapplanes[brush->sides[i].planenum ^ 1];
981 ChopWindingInPlace (&w, plane2->normal, plane2->dist, 0); // PLANESIDE_EPSILON);
982 }
983
984 if (!w || WindingIsTiny (w) )
985 { // the brush isn't really split
986 int side;
987
988 side = BrushMostlyOnSide (brush, plane);
989 if (side == PSIDE_FRONT)
990 *front = CopyBrush (brush);
991 if (side == PSIDE_BACK)
992 *back = CopyBrush (brush);
993 return;
994 }
995
996 if (WindingIsHuge (w))
997 {
998 qprintf ("WARNING: huge winding\n");
999 }
1000
1001 midwinding = w;
1002
1003 // split it for real
1004
1005 for (i=0 ; i<2 ; i++)
1006 {
1007 b[i] = AllocBrush (brush->numsides+1);
1008 b[i]->original = brush->original;
1009 }
1010
1011 // split all the current windings
1012
1013 for (i=0 ; i<brush->numsides ; i++)
1014 {
1015 s = &brush->sides[i];
1016 w = s->winding;
1017 if (!w)
1018 continue;
1019 ClipWindingEpsilon (w, plane->normal, plane->dist,
1020 0 /*PLANESIDE_EPSILON*/, &cw[0], &cw[1]);
1021 for (j=0 ; j<2 ; j++)
1022 {
1023 if (!cw[j])
1024 continue;
1025 #if 0
1026 if (WindingIsTiny (cw[j]))
1027 {
1028 FreeWinding (cw[j]);
1029 continue;
1030 }
1031 #endif
1032 cs = &b[j]->sides[b[j]->numsides];
1033 b[j]->numsides++;
1034 *cs = *s;
1035 // cs->planenum = s->planenum;
1036 // cs->texinfo = s->texinfo;
1037 // cs->visible = s->visible;
1038 // cs->original = s->original;
1039 cs->winding = cw[j];
1040 cs->tested = false;
1041 }
1042 }
1043
1044
1045 // see if we have valid polygons on both sides
1046
1047 for (i=0 ; i<2 ; i++)
1048 {
1049 BoundBrush (b[i]);
1050 for (j=0 ; j<3 ; j++)
1051 {
1052 if (b[i]->mins[j] < -4096 || b[i]->maxs[j] > 4096)
1053 {
1054 qprintf ("bogus brush after clip\n");
1055 break;
1056 }
1057 }
1058
1059 if (b[i]->numsides < 3 || j < 3)
1060 {
1061 FreeBrush (b[i]);
1062 b[i] = NULL;
1063 }
1064 }
1065
1066 if ( !(b[0] && b[1]) )
1067 {
1068 if (!b[0] && !b[1])
1069 qprintf ("split removed brush\n");
1070 else
1071 qprintf ("split not on both sides\n");
1072 if (b[0])
1073 {
1074 FreeBrush (b[0]);
1075 *front = CopyBrush (brush);
1076 }
1077 if (b[1])
1078 {
1079 FreeBrush (b[1]);
1080 *back = CopyBrush (brush);
1081 }
1082 return;
1083 }
1084
1085 // add the midwinding to both sides
1086 for (i=0 ; i<2 ; i++)
1087 {
1088 cs = &b[i]->sides[b[i]->numsides];
1089 b[i]->numsides++;
1090
1091 cs->planenum = planenum^i^1;
1092 cs->texinfo = TEXINFO_NODE;
1093 cs->visible = false;
1094 cs->tested = false;
1095 if (i==0)
1096 cs->winding = CopyWinding (midwinding);
1097 else
1098 cs->winding = midwinding;
1099 }
1100
1101 {
1102 vec_t v1;
1103 int i;
1104
1105 for (i=0 ; i<2 ; i++)
1106 {
1107 v1 = BrushVolume (b[i]);
1108 if (v1 < 1.0)
1109 {
1110 FreeBrush (b[i]);
1111 b[i] = NULL;
1112 // qprintf ("tiny volume after clip\n");
1113 }
1114 }
1115 }
1116
1117 *front = b[0];
1118 *back = b[1];
1119 }
1120
1121 /*
1122 ================
1123 SplitBrushList
1124 ================
1125 */
SplitBrushList(bspbrush_t * brushes,node_t * node,bspbrush_t ** front,bspbrush_t ** back)1126 void SplitBrushList (bspbrush_t *brushes,
1127 node_t *node, bspbrush_t **front, bspbrush_t **back)
1128 {
1129 bspbrush_t *brush, *newbrush, *newbrush2;
1130 side_t *side;
1131 int sides;
1132 int i;
1133
1134 *front = *back = NULL;
1135
1136 for (brush = brushes ; brush ; brush=brush->next)
1137 {
1138 sides = brush->side;
1139
1140 if (sides == PSIDE_BOTH)
1141 { // split into two brushes
1142 SplitBrush (brush, node->planenum, &newbrush, &newbrush2);
1143 if (newbrush)
1144 {
1145 newbrush->next = *front;
1146 *front = newbrush;
1147 }
1148 if (newbrush2)
1149 {
1150 newbrush2->next = *back;
1151 *back = newbrush2;
1152 }
1153 continue;
1154 }
1155
1156 newbrush = CopyBrush (brush);
1157
1158 // if the planenum is actualy a part of the brush
1159 // find the plane and flag it as used so it won't be tried
1160 // as a splitter again
1161 if (sides & PSIDE_FACING)
1162 {
1163 for (i=0 ; i<newbrush->numsides ; i++)
1164 {
1165 side = newbrush->sides + i;
1166 if ( (side->planenum& ~1) == node->planenum)
1167 side->texinfo = TEXINFO_NODE;
1168 }
1169 }
1170
1171
1172 if (sides & PSIDE_FRONT)
1173 {
1174 newbrush->next = *front;
1175 *front = newbrush;
1176 continue;
1177 }
1178 if (sides & PSIDE_BACK)
1179 {
1180 newbrush->next = *back;
1181 *back = newbrush;
1182 continue;
1183 }
1184 }
1185 }
1186
1187
1188 /*
1189 ================
1190 BuildTree_r
1191 ================
1192 */
BuildTree_r(node_t * node,bspbrush_t * brushes)1193 node_t *BuildTree_r (node_t *node, bspbrush_t *brushes)
1194 {
1195 node_t *newnode;
1196 side_t *bestside;
1197 int i;
1198 bspbrush_t *children[2];
1199
1200 if (numthreads == 1)
1201 c_nodes++;
1202
1203 if (drawflag)
1204 DrawBrushList (brushes, node);
1205
1206 // find the best plane to use as a splitter
1207 bestside = SelectSplitSide (brushes, node);
1208 if (!bestside)
1209 {
1210 // leaf node
1211 node->side = NULL;
1212 node->planenum = -1;
1213 LeafNode (node, brushes);
1214 return node;
1215 }
1216
1217 // this is a splitplane node
1218 node->side = bestside;
1219 node->planenum = bestside->planenum & ~1; // always use front facing
1220
1221 SplitBrushList (brushes, node, &children[0], &children[1]);
1222 FreeBrushList (brushes);
1223
1224 // allocate children before recursing
1225 for (i=0 ; i<2 ; i++)
1226 {
1227 newnode = AllocNode ();
1228 newnode->parent = node;
1229 node->children[i] = newnode;
1230 }
1231
1232 SplitBrush (node->volume, node->planenum, &node->children[0]->volume,
1233 &node->children[1]->volume);
1234
1235 // recursively process children
1236 for (i=0 ; i<2 ; i++)
1237 {
1238 node->children[i] = BuildTree_r (node->children[i], children[i]);
1239 }
1240
1241 return node;
1242 }
1243
1244 //===========================================================
1245
1246 /*
1247 =================
1248 BrushBSP
1249
1250 The incoming list will be freed before exiting
1251 =================
1252 */
BrushBSP(bspbrush_t * brushlist,vec3_t mins,vec3_t maxs)1253 tree_t *BrushBSP (bspbrush_t *brushlist, vec3_t mins, vec3_t maxs)
1254 {
1255 node_t *node;
1256 bspbrush_t *b;
1257 int c_faces, c_nonvisfaces;
1258 int c_brushes;
1259 tree_t *tree;
1260 int i;
1261 vec_t volume;
1262
1263 qprintf ("--- BrushBSP ---\n");
1264
1265 tree = AllocTree ();
1266
1267 c_faces = 0;
1268 c_nonvisfaces = 0;
1269 c_brushes = 0;
1270 for (b=brushlist ; b ; b=b->next)
1271 {
1272 c_brushes++;
1273
1274 volume = BrushVolume (b);
1275 if (volume < microvolume)
1276 {
1277 printf ("WARNING: entity %i, brush %i: microbrush\n",
1278 b->original->entitynum, b->original->brushnum);
1279 }
1280
1281 for (i=0 ; i<b->numsides ; i++)
1282 {
1283 if (b->sides[i].bevel)
1284 continue;
1285 if (!b->sides[i].winding)
1286 continue;
1287 if (b->sides[i].texinfo == TEXINFO_NODE)
1288 continue;
1289 if (b->sides[i].visible)
1290 c_faces++;
1291 else
1292 c_nonvisfaces++;
1293 }
1294
1295 AddPointToBounds (b->mins, tree->mins, tree->maxs);
1296 AddPointToBounds (b->maxs, tree->mins, tree->maxs);
1297 }
1298
1299 qprintf ("%5i brushes\n", c_brushes);
1300 qprintf ("%5i visible faces\n", c_faces);
1301 qprintf ("%5i nonvisible faces\n", c_nonvisfaces);
1302
1303 c_nodes = 0;
1304 c_nonvis = 0;
1305 node = AllocNode ();
1306
1307 node->volume = BrushFromBounds (mins, maxs);
1308
1309 tree->headnode = node;
1310
1311 node = BuildTree_r (node, brushlist);
1312 qprintf ("%5i visible nodes\n", c_nodes/2 - c_nonvis);
1313 qprintf ("%5i nonvis nodes\n", c_nonvis);
1314 qprintf ("%5i leafs\n", (c_nodes+1)/2);
1315 #if 0
1316 { // debug code
1317 static node_t *tnode;
1318 vec3_t p;
1319
1320 p[0] = -1469;
1321 p[1] = -118;
1322 p[2] = 119;
1323 tnode = PointInLeaf (tree->headnode, p);
1324 printf ("contents: %i\n", tnode->contents);
1325 p[0] = 0;
1326 }
1327 #endif
1328 return tree;
1329 }
1330
1331