--- /dev/null
+/* -------------------------------------------------------------------------------
+
+Copyright (C) 1999-2007 id Software, Inc. and contributors.
+For a list of contributors, see the accompanying CONTRIBUTORS file.
+
+This file is part of GtkRadiant.
+
+GtkRadiant is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 2 of the License, or
+(at your option) any later version.
+
+GtkRadiant is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GtkRadiant; if not, write to the Free Software
+Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+
+----------------------------------------------------------------------------------
+
+This code has been altered significantly from its original form, to support
+several games based on the Quake III Arena engine, in the form of "Q3Map2."
+
+------------------------------------------------------------------------------- */
+
+
+
+/* marker */
+#define FACEBSP_C
+
+
+
+/* dependencies */
+#include "q3map2.h"
+
+
+
+int c_faceLeafs;
+
+
+/*
+================
+AllocBspFace
+================
+*/
+face_t *AllocBspFace( void ) {
+ face_t *f;
+
+ f = safe_malloc(sizeof(*f));
+ memset( f, 0, sizeof(*f) );
+
+ return f;
+}
+
+
+
+/*
+================
+FreeBspFace
+================
+*/
+void FreeBspFace( face_t *f ) {
+ if ( f->w ) {
+ FreeWinding( f->w );
+ }
+ free( f );
+}
+
+
+
+/*
+SelectSplitPlaneNum()
+finds the best split plane for this node
+*/
+
+static void SelectSplitPlaneNum( node_t *node, face_t *list, int *splitPlaneNum, int *compileFlags )
+{
+ face_t *split;
+ face_t *check;
+ face_t *bestSplit;
+ int splits, facing, front, back;
+ int side;
+ plane_t *plane;
+ int value, bestValue;
+ int i;
+ vec3_t normal;
+ float dist;
+ int planenum;
+ float sizeBias;
+
+ //int frontC,backC,splitsC,facingC;
+
+
+ /* ydnar: set some defaults */
+ *splitPlaneNum = -1; /* leaf */
+ *compileFlags = 0;
+
+ /* ydnar 2002-06-24: changed this to split on z-axis as well */
+ /* ydnar 2002-09-21: changed blocksize to be a vector, so mappers can specify a 3 element value */
+
+ /* if it is crossing a block boundary, force a split */
+ for( i = 0; i < 3; i++ )
+ {
+ if( blockSize[ i ] <= 0 )
+ continue;
+ dist = blockSize[ i ] * (floor( node->mins[ i ] / blockSize[ i ] ) + 1);
+ if( node->maxs[ i ] > dist )
+ {
+ VectorClear( normal );
+ normal[ i ] = 1;
+ planenum = FindFloatPlane( normal, dist, 0, NULL );
+ *splitPlaneNum = planenum;
+ return;
+ }
+ }
+
+ /* pick one of the face planes */
+ bestValue = -99999;
+ bestSplit = list;
+
+
+ // div0: this check causes detail/structural mixes
+ //for( split = list; split; split = split->next )
+ // split->checked = qfalse;
+
+ for( split = list; split; split = split->next )
+ {
+ //if ( split->checked )
+ // continue;
+
+ plane = &mapplanes[ split->planenum ];
+ splits = 0;
+ facing = 0;
+ front = 0;
+ back = 0;
+ for ( check = list ; check ; check = check->next ) {
+ if ( check->planenum == split->planenum ) {
+ facing++;
+ //check->checked = qtrue; // won't need to test this plane again
+ continue;
+ }
+ side = WindingOnPlaneSide( check->w, plane->normal, plane->dist );
+ if ( side == SIDE_CROSS ) {
+ splits++;
+ } else if ( side == SIDE_FRONT ) {
+ front++;
+ } else if ( side == SIDE_BACK ) {
+ back++;
+ }
+ }
+
+ if(bspAlternateSplitWeights)
+ {
+ // from 27
+
+ //Bigger is better
+ sizeBias=WindingArea(split->w);
+
+ //Base score = 20000 perfectly balanced
+ value = 20000-(abs(front-back));
+ value -= plane->counter;// If we've already used this plane sometime in the past try not to use it again
+ value -= facing ; // if we're going to have alot of other surfs use this plane, we want to get it in quickly.
+ value -= splits*5; //more splits = bad
+ value += sizeBias*10; //We want a huge score bias based on plane size
+ }
+ else
+ {
+ value = 5*facing - 5*splits; // - abs(front-back);
+ if ( plane->type < 3 ) {
+ value+=5; // axial is better
+ }
+ }
+
+ value += split->priority; // prioritize hints higher
+
+ if ( value > bestValue ) {
+ bestValue = value;
+ bestSplit = split;
+ //frontC=front;
+ //backC=back;
+ //splitsC=splits;
+ //facingC=facing;
+ }
+ }
+
+ /* nothing, we have a leaf */
+ if( bestValue == -99999 )
+ return;
+
+ //Sys_FPrintf (SYS_VRB, "F: %d B:%d S:%d FA:%ds\n",frontC,backC,splitsC,facingC );
+
+ /* set best split data */
+ *splitPlaneNum = bestSplit->planenum;
+ *compileFlags = bestSplit->compileFlags;
+
+#if 0
+ if(bestSplit->compileFlags & C_DETAIL)
+ for( split = list; split; split = split->next )
+ if(!(split->compileFlags & C_DETAIL))
+ Sys_FPrintf(SYS_ERR, "DON'T DO SUCH SPLITS (1)\n");
+ if((node->compileFlags & C_DETAIL) && !(bestSplit->compileFlags & C_DETAIL))
+ Sys_FPrintf(SYS_ERR, "DON'T DO SUCH SPLITS (2)\n");
+#endif
+
+ if (*splitPlaneNum>-1) mapplanes[ *splitPlaneNum ].counter++;
+}
+
+
+
+/*
+CountFaceList()
+counts bsp faces in the linked list
+*/
+
+int CountFaceList( face_t *list )
+{
+ int c;
+
+
+ c = 0;
+ for( ; list != NULL; list = list->next )
+ c++;
+ return c;
+}
+
+
+
+/*
+BuildFaceTree_r()
+recursively builds the bsp, splitting on face planes
+*/
+
+void BuildFaceTree_r( node_t *node, face_t *list )
+{
+ face_t *split;
+ face_t *next;
+ int side;
+ plane_t *plane;
+ face_t *newFace;
+ face_t *childLists[2];
+ winding_t *frontWinding, *backWinding;
+ int i;
+ int splitPlaneNum, compileFlags;
+ qboolean isstruct = qfalse;
+
+
+ /* count faces left */
+ i = CountFaceList( list );
+
+ /* select the best split plane */
+ SelectSplitPlaneNum( node, list, &splitPlaneNum, &compileFlags );
+
+ /* if we don't have any more faces, this is a node */
+ if ( splitPlaneNum == -1 )
+ {
+ node->planenum = PLANENUM_LEAF;
+ node->has_structural_children = qfalse;
+ c_faceLeafs++;
+ return;
+ }
+
+ /* partition the list */
+ node->planenum = splitPlaneNum;
+ node->compileFlags = compileFlags;
+ node->has_structural_children = !(compileFlags & C_DETAIL) && !node->opaque;
+ plane = &mapplanes[ splitPlaneNum ];
+ childLists[0] = NULL;
+ childLists[1] = NULL;
+
+ for( split = list; split; split = next )
+ {
+ /* set next */
+ next = split->next;
+
+ /* don't split by identical plane */
+ if( split->planenum == node->planenum )
+ {
+ FreeBspFace( split );
+ continue;
+ }
+
+ if(!(split->compileFlags & C_DETAIL))
+ isstruct = 1;
+
+ /* determine which side the face falls on */
+ side = WindingOnPlaneSide( split->w, plane->normal, plane->dist );
+
+ /* switch on side */
+ if( side == SIDE_CROSS )
+ {
+ ClipWindingEpsilon( split->w, plane->normal, plane->dist, CLIP_EPSILON * 2,
+ &frontWinding, &backWinding );
+ if( frontWinding ) {
+ newFace = AllocBspFace();
+ newFace->w = frontWinding;
+ newFace->next = childLists[0];
+ newFace->planenum = split->planenum;
+ newFace->priority = split->priority;
+ newFace->compileFlags = split->compileFlags;
+ childLists[0] = newFace;
+ }
+ if( backWinding ) {
+ newFace = AllocBspFace();
+ newFace->w = backWinding;
+ newFace->next = childLists[1];
+ newFace->planenum = split->planenum;
+ newFace->priority = split->priority;
+ newFace->compileFlags = split->compileFlags;
+ childLists[1] = newFace;
+ }
+ FreeBspFace( split );
+ } else if ( side == SIDE_FRONT ) {
+ split->next = childLists[0];
+ childLists[0] = split;
+ } else if ( side == SIDE_BACK ) {
+ split->next = childLists[1];
+ childLists[1] = split;
+ }
+ }
+
+
+ // recursively process children
+ for ( i = 0 ; i < 2 ; i++ ) {
+ node->children[i] = AllocNode();
+ node->children[i]->parent = node;
+ VectorCopy( node->mins, node->children[i]->mins );
+ VectorCopy( node->maxs, node->children[i]->maxs );
+ }
+
+ for ( i = 0 ; i < 3 ; i++ ) {
+ if ( plane->normal[i] == 1 ) {
+ node->children[0]->mins[i] = plane->dist;
+ node->children[1]->maxs[i] = plane->dist;
+ break;
+ }
+ }
+
+#if 0
+ if((node->compileFlags & C_DETAIL) && isstruct)
+ Sys_FPrintf(SYS_ERR, "I am detail, my child is structural, this is a wtf1\n", node->has_structural_children);
+#endif
+
+ for ( i = 0 ; i < 2 ; i++ ) {
+ BuildFaceTree_r ( node->children[i], childLists[i]);
+ node->has_structural_children |= node->children[i]->has_structural_children;
+ }
+
+#if 0
+ if((node->compileFlags & C_DETAIL) && !(node->children[0]->compileFlags & C_DETAIL) && node->children[0]->planenum != PLANENUM_LEAF)
+ Sys_FPrintf(SYS_ERR, "I am detail, my child is structural\n", node->has_structural_children);
+ if((node->compileFlags & C_DETAIL) && isstruct)
+ Sys_FPrintf(SYS_ERR, "I am detail, my child is structural, this is a wtf2\n", node->has_structural_children);
+#endif
+}
+
+
+/*
+================
+FaceBSP
+
+List will be freed before returning
+================
+*/
+tree_t *FaceBSP( face_t *list ) {
+ tree_t *tree;
+ face_t *face;
+ int i;
+ int count;
+
+ Sys_FPrintf (SYS_VRB, "--- FaceBSP ---\n" );
+
+ tree = AllocTree ();
+
+ count = 0;
+ for( face = list; face != NULL; face = face->next )
+ {
+ count++;
+ for( i = 0; i < face->w->numpoints; i++ )
+ {
+ AddPointToBounds( face->w->p[ i ], tree->mins, tree->maxs );
+ }
+ }
+ Sys_FPrintf( SYS_VRB, "%9d faces\n", count );
+
+ for( i = 0; i < nummapplanes; i++)
+ {
+ mapplanes[ i ].counter=0;
+ }
+
+ tree->headnode = AllocNode();
+ VectorCopy( tree->mins, tree->headnode->mins );
+ VectorCopy( tree->maxs, tree->headnode->maxs );
+ c_faceLeafs = 0;
+
+ BuildFaceTree_r ( tree->headnode, list );
+
+ Sys_FPrintf( SYS_VRB, "%9d leafs\n", c_faceLeafs );
+
+ return tree;
+}
+
+
+
+/*
+MakeStructuralBSPFaceList()
+get structural brush faces
+*/
+
+face_t *MakeStructuralBSPFaceList( brush_t *list )
+{
+ brush_t *b;
+ int i;
+ side_t *s;
+ winding_t *w;
+ face_t *f, *flist;
+
+
+ flist = NULL;
+ for( b = list; b != NULL; b = b->next )
+ {
+ if( !deepBSP && b->detail )
+ continue;
+
+ for( i = 0; i < b->numsides; i++ )
+ {
+ /* get side and winding */
+ s = &b->sides[ i ];
+ w = s->winding;
+ if( w == NULL )
+ continue;
+
+ /* ydnar: skip certain faces */
+ if( s->compileFlags & C_SKIP )
+ continue;
+
+ /* allocate a face */
+ f = AllocBspFace();
+ f->w = CopyWinding( w );
+ f->planenum = s->planenum & ~1;
+ f->compileFlags = s->compileFlags; /* ydnar */
+ if(b->detail)
+ f->compileFlags |= C_DETAIL;
+
+ /* ydnar: set priority */
+ f->priority = 0;
+ if( f->compileFlags & C_HINT )
+ f->priority += HINT_PRIORITY;
+ if( f->compileFlags & C_ANTIPORTAL )
+ f->priority += ANTIPORTAL_PRIORITY;
+ if( f->compileFlags & C_AREAPORTAL )
+ f->priority += AREAPORTAL_PRIORITY;
+ if( f->compileFlags & C_DETAIL )
+ f->priority += DETAIL_PRIORITY;
+
+ /* get next face */
+ f->next = flist;
+ flist = f;
+ }
+ }
+
+ return flist;
+}
+
+
+
+/*
+MakeVisibleBSPFaceList()
+get visible brush faces
+*/
+
+face_t *MakeVisibleBSPFaceList( brush_t *list )
+{
+ brush_t *b;
+ int i;
+ side_t *s;
+ winding_t *w;
+ face_t *f, *flist;
+
+
+ flist = NULL;
+ for( b = list; b != NULL; b = b->next )
+ {
+ if( !deepBSP && b->detail )
+ continue;
+
+ for( i = 0; i < b->numsides; i++ )
+ {
+ /* get side and winding */
+ s = &b->sides[ i ];
+ w = s->visibleHull;
+ if( w == NULL )
+ continue;
+
+ /* ydnar: skip certain faces */
+ if( s->compileFlags & C_SKIP )
+ continue;
+
+ /* allocate a face */
+ f = AllocBspFace();
+ f->w = CopyWinding( w );
+ f->planenum = s->planenum & ~1;
+ f->compileFlags = s->compileFlags; /* ydnar */
+ if(b->detail)
+ f->compileFlags |= C_DETAIL;
+
+ /* ydnar: set priority */
+ f->priority = 0;
+ if( f->compileFlags & C_HINT )
+ f->priority += HINT_PRIORITY;
+ if( f->compileFlags & C_ANTIPORTAL )
+ f->priority += ANTIPORTAL_PRIORITY;
+ if( f->compileFlags & C_AREAPORTAL )
+ f->priority += AREAPORTAL_PRIORITY;
+ if( f->compileFlags & C_DETAIL )
+ f->priority += DETAIL_PRIORITY;
+
+ /* get next face */
+ f->next = flist;
+ flist = f;
+ }
+ }
+
+ return flist;
+}
+
projects / voretournament / voretournament.git / blobdiff