From f56bb35301836e56582a575a75864392a0177875 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?J=C3=B8rgen=20P=2E=20Tjern=C3=B8?= Date: Mon, 2 Dec 2013 19:31:46 -0800 Subject: Fix line endings. WHAMMY. --- mp/src/utils/vbsp/csg.cpp | 1568 ++++++++++++++++++++++----------------------- 1 file changed, 784 insertions(+), 784 deletions(-) (limited to 'mp/src/utils/vbsp/csg.cpp') diff --git a/mp/src/utils/vbsp/csg.cpp b/mp/src/utils/vbsp/csg.cpp index c4b89bd9..5de1d680 100644 --- a/mp/src/utils/vbsp/csg.cpp +++ b/mp/src/utils/vbsp/csg.cpp @@ -1,784 +1,784 @@ -//========= Copyright Valve Corporation, All rights reserved. ============// -// -// Purpose: -// -// $NoKeywords: $ -// -//=============================================================================// - -#include "vbsp.h" - -/* - -tag all brushes with original contents -brushes may contain multiple contents -there will be no brush overlap after csg phase - - - - -each side has a count of the other sides it splits - -the best split will be the one that minimizes the total split counts -of all remaining sides - -precalc side on plane table - -evaluate split side -{ -cost = 0 -for all sides - for all sides - get - if side splits side and splitside is on same child - cost++; -} - - - */ - -void SplitBrush2( bspbrush_t *brush, int planenum, bspbrush_t **front, bspbrush_t **back ) -{ - SplitBrush( brush, planenum, front, back ); -#if 0 - if (*front && (*front)->sides[(*front)->numsides-1].texinfo == -1) - (*front)->sides[(*front)->numsides-1].texinfo = (*front)->sides[0].texinfo; // not -1 - if (*back && (*back)->sides[(*back)->numsides-1].texinfo == -1) - (*back)->sides[(*back)->numsides-1].texinfo = (*back)->sides[0].texinfo; // not -1 -#endif -} - -/* -=============== -SubtractBrush - -Returns a list of brushes that remain after B is subtracted from A. -May by empty if A is contained inside B. - -The originals are undisturbed. -=============== -*/ -bspbrush_t *SubtractBrush (bspbrush_t *a, bspbrush_t *b) -{ // a - b = out (list) - int i; - bspbrush_t *front, *back; - bspbrush_t *out, *in; - - in = a; - out = NULL; - for (i=0 ; inumsides && in ; i++) - { - SplitBrush2 (in, b->sides[i].planenum, &front, &back); - if (in != a) - FreeBrush (in); - if (front) - { // add to list - front->next = out; - out = front; - } - in = back; - } - if (in) - FreeBrush (in); - else - { // didn't really intersect - FreeBrushList (out); - return a; - } - return out; -} - -/* -=============== -IntersectBrush - -Returns a single brush made up by the intersection of the -two provided brushes, or NULL if they are disjoint. - -The originals are undisturbed. -=============== -*/ -bspbrush_t *IntersectBrush (bspbrush_t *a, bspbrush_t *b) -{ - int i; - bspbrush_t *front, *back; - bspbrush_t *in; - - in = a; - for (i=0 ; inumsides && in ; i++) - { - SplitBrush2 (in, b->sides[i].planenum, &front, &back); - if (in != a) - FreeBrush (in); - if (front) - FreeBrush (front); - in = back; - } - - if (in == a || !in) - return NULL; - - in->next = NULL; - return in; -} - - -/* -=============== -BrushesDisjoint - -Returns true if the two brushes definately do not intersect. -There will be false negatives for some non-axial combinations. -=============== -*/ -qboolean BrushesDisjoint (bspbrush_t *a, bspbrush_t *b) -{ - int i, j; - - // check bounding boxes - for (i=0 ; i<3 ; i++) - if (a->mins[i] >= b->maxs[i] - || a->maxs[i] <= b->mins[i]) - return true; // bounding boxes don't overlap - - // check for opposing planes - for (i=0 ; inumsides ; i++) - { - for (j=0 ; jnumsides ; j++) - { - if (a->sides[i].planenum == - (b->sides[j].planenum^1) ) - return true; // opposite planes, so not touching - } - } - - return false; // might intersect -} - - -int minplanenums[3]; -int maxplanenums[3]; - -/* -=============== -ClipBrushToBox - -Any planes shared with the box edge will be set to no texinfo -=============== -*/ -bspbrush_t *ClipBrushToBox (bspbrush_t *brush, const Vector& clipmins, const Vector& clipmaxs) -{ - int i, j; - bspbrush_t *front, *back; - int p; - - for (j=0 ; j<2 ; j++) - { - if (brush->maxs[j] > clipmaxs[j]) - { - SplitBrush (brush, maxplanenums[j], &front, &back); - if (front) - FreeBrush (front); - brush = back; - if (!brush) - return NULL; - } - if (brush->mins[j] < clipmins[j]) - { - SplitBrush (brush, minplanenums[j], &front, &back); - if (back) - FreeBrush (back); - brush = front; - if (!brush) - return NULL; - } - } - - // remove any colinear faces - - for (i=0 ; inumsides ; i++) - { - p = brush->sides[i].planenum & ~1; - if (p == maxplanenums[0] || p == maxplanenums[1] - || p == minplanenums[0] || p == minplanenums[1]) - { - brush->sides[i].texinfo = TEXINFO_NODE; - brush->sides[i].visible = false; - } - } - return brush; -} - - -//----------------------------------------------------------------------------- -// Creates a clipped brush from a map brush -//----------------------------------------------------------------------------- -static bspbrush_t *CreateClippedBrush( mapbrush_t *mb, const Vector& clipmins, const Vector& clipmaxs ) -{ - int nNumSides = mb->numsides; - if (!nNumSides) - return NULL; - - // if the brush is outside the clip area, skip it - for (int j=0 ; j<3 ; j++) - { - if (mb->mins[j] >= clipmaxs[j] || mb->maxs[j] <= clipmins[j]) - { - return NULL; - } - } - - // make a copy of the brush - bspbrush_t *newbrush = AllocBrush( nNumSides ); - newbrush->original = mb; - newbrush->numsides = nNumSides; - memcpy (newbrush->sides, mb->original_sides, nNumSides*sizeof(side_t)); - - for (int j=0 ; jsides[j].winding) - { - newbrush->sides[j].winding = CopyWinding (newbrush->sides[j].winding); - } - - if (newbrush->sides[j].surf & SURF_HINT) - { - newbrush->sides[j].visible = true; // hints are always visible - } - - // keep a pointer to the original map brush side -- use to create the original face later!! - //newbrush->sides[j].original = &mb->original_sides[j]; - } - - VectorCopy (mb->mins, newbrush->mins); - VectorCopy (mb->maxs, newbrush->maxs); - - // carve off anything outside the clip box - newbrush = ClipBrushToBox (newbrush, clipmins, clipmaxs); - return newbrush; -} - - -//----------------------------------------------------------------------------- -// Creates a clipped brush from a map brush -//----------------------------------------------------------------------------- -static void ComputeBoundingPlanes( const Vector& clipmins, const Vector& clipmaxs ) -{ - Vector normal; - float dist; - for (int i=0 ; i<2 ; i++) - { - VectorClear (normal); - normal[i] = 1; - dist = clipmaxs[i]; - maxplanenums[i] = g_MainMap->FindFloatPlane (normal, dist); - dist = clipmins[i]; - minplanenums[i] = g_MainMap->FindFloatPlane (normal, dist); - } -} - - -//----------------------------------------------------------------------------- -// This forces copies of texinfo data for matching sides of a brush -//----------------------------------------------------------------------------- -void CopyMatchingTexinfos( side_t *pDestSides, int numDestSides, const bspbrush_t *pSource ) -{ - for ( int i = 0; i < numDestSides; i++ ) - { - side_t *pSide = &pDestSides[i]; - plane_t *pPlane = &g_MainMap->mapplanes[pSide->planenum]; - - // We have to use the *original sides* because MapBSPBrushList could have generated - // splits when cutting the original brush to the block being processed. This - // will generate faces that use TEXINFO_NODE, which is definitely *not* what we want. - // If we end up with faces using TEXINFO_NODE here, the area portal will flood into - // the entire water volume intersecting the areaportal. - - mapbrush_t *pSourceBrush = pSource->original; - Assert( pSourceBrush ); - - const side_t *pSourceSide = pSourceBrush->original_sides; - const side_t *pBestSide = NULL; - float flBestDot = -1.0f; - for ( int j = 0; j < pSourceBrush->numsides; ++j, ++pSourceSide ) - { - if ( pSourceSide->texinfo == TEXINFO_NODE ) - continue; - - plane_t *pSourcePlane = &g_MainMap->mapplanes[pSourceSide->planenum]; - float flDot = DotProduct( pPlane->normal, pSourcePlane->normal ); - if ( flDot == 1.0f || pSide->planenum == pSourceSide->planenum ) - { - pBestSide = pSourceSide; - break; - } - else if ( flDot > flBestDot ) - { - pBestSide = pSourceSide; - flBestDot = flDot; - } - } - - if ( pBestSide ) - { - pSide->texinfo = pBestSide->texinfo; - if ( pSide->original ) - { - pSide->original->texinfo = pSide->texinfo; - } - } - else - { - texinfo_t *pTexInfo = &texinfo[pSide->texinfo]; - dtexdata_t *pTexData = GetTexData( pTexInfo->texdata ); - Msg("Found no matching plane for %s\n", TexDataStringTable_GetString( pTexData->nameStringTableID ) ); - } - } -} - -// This is a hack to allow areaportals to work in water -// It was done this way for ease of implementation. -// This searches a brush list to find intersecting areaportals and water -// If an areaportal is found inside water, then the water contents and -// texture information is copied over to the areaportal so that the -// resulting space has the same properties as the water (normal areaportals assume "empty" surroundings) -void FixupAreaportalWaterBrushes( bspbrush_t *pList ) -{ - for ( bspbrush_t *pAreaportal = pList; pAreaportal; pAreaportal = pAreaportal->next ) - { - if ( !(pAreaportal->original->contents & CONTENTS_AREAPORTAL) ) - continue; - - for ( bspbrush_t *pWater = pList; pWater; pWater = pWater->next ) - { - // avoid using areaportal/water combo brushes that have already been fixed up - if ( pWater->original->contents & CONTENTS_AREAPORTAL ) - continue; - - if ( !(pWater->original->contents & MASK_SPLITAREAPORTAL) ) - continue; - - if ( BrushesDisjoint( pAreaportal, pWater ) ) - continue; - - bspbrush_t *pIntersect = IntersectBrush( pAreaportal, pWater ); - if ( !pIntersect ) - continue; - FreeBrush( pIntersect ); - pAreaportal->original->contents |= pWater->original->contents; - - // HACKHACK: Ideally, this should have been done before the bspbrush_t was - // created from the map brush. But since it hasn't been, retexture the original map - // brush's sides - CopyMatchingTexinfos( pAreaportal->sides, pAreaportal->numsides, pWater ); - CopyMatchingTexinfos( pAreaportal->original->original_sides, pAreaportal->original->numsides, pWater ); - } - } -} - - -//----------------------------------------------------------------------------- -// MakeBspBrushList -//----------------------------------------------------------------------------- -// UNDONE: Put detail brushes in a separate brush array and pass that instead of "onlyDetail" ? -bspbrush_t *MakeBspBrushList (int startbrush, int endbrush, const Vector& clipmins, const Vector& clipmaxs, int detailScreen) -{ - ComputeBoundingPlanes( clipmins, clipmaxs ); - - bspbrush_t *pBrushList = NULL; - - int i; - for (i=startbrush ; imapbrushes[i]; - if ( detailScreen != FULL_DETAIL ) - { - bool onlyDetail = (detailScreen == ONLY_DETAIL); - bool detail = (mb->contents & CONTENTS_DETAIL) != 0; - if ( onlyDetail ^ detail ) - { - // both of these must have the same value or we're not interested in this brush - continue; - } - } - - bspbrush_t *pNewBrush = CreateClippedBrush( mb, clipmins, clipmaxs ); - if ( pNewBrush ) - { - pNewBrush->next = pBrushList; - pBrushList = pNewBrush; - } - } - - return pBrushList; -} - - -//----------------------------------------------------------------------------- -// A version which uses a passed-in list of brushes -//----------------------------------------------------------------------------- -bspbrush_t *MakeBspBrushList (mapbrush_t **pBrushes, int nBrushCount, const Vector& clipmins, const Vector& clipmaxs) -{ - ComputeBoundingPlanes( clipmins, clipmaxs ); - - bspbrush_t *pBrushList = NULL; - for ( int i=0; i < nBrushCount; ++i ) - { - bspbrush_t *pNewBrush = CreateClippedBrush( pBrushes[i], clipmins, clipmaxs ); - if ( pNewBrush ) - { - pNewBrush->next = pBrushList; - pBrushList = pNewBrush; - } - } - - return pBrushList; -} - - -/* -=============== -AddBspBrushListToTail -=============== -*/ -bspbrush_t *AddBrushListToTail (bspbrush_t *list, bspbrush_t *tail) -{ - bspbrush_t *walk, *next; - - for (walk=list ; walk ; walk=next) - { // add to end of list - next = walk->next; - walk->next = NULL; - tail->next = walk; - tail = walk; - } - - return tail; -} - -/* -=========== -CullList - -Builds a new list that doesn't hold the given brush -=========== -*/ -bspbrush_t *CullList (bspbrush_t *list, bspbrush_t *skip1) -{ - bspbrush_t *newlist; - bspbrush_t *next; - - newlist = NULL; - - for ( ; list ; list = next) - { - next = list->next; - if (list == skip1) - { - FreeBrush (list); - continue; - } - list->next = newlist; - newlist = list; - } - return newlist; -} - - -/* -================== -WriteBrushMap -================== -*/ -void WriteBrushMap (char *name, bspbrush_t *list) -{ - FILE *f; - side_t *s; - int i; - winding_t *w; - - Msg("writing %s\n", name); - f = fopen (name, "w"); - if (!f) - Error ("Can't write %s\b", name); - - fprintf (f, "{\n\"classname\" \"worldspawn\"\n"); - - for ( ; list ; list=list->next ) - { - fprintf (f, "{\n"); - for (i=0,s=list->sides ; inumsides ; i++,s++) - { - w = BaseWindingForPlane (g_MainMap->mapplanes[s->planenum].normal, g_MainMap->mapplanes[s->planenum].dist); - - fprintf (f,"( %i %i %i ) ", (int)w->p[0][0], (int)w->p[0][1], (int)w->p[0][2]); - fprintf (f,"( %i %i %i ) ", (int)w->p[1][0], (int)w->p[1][1], (int)w->p[1][2]); - fprintf (f,"( %i %i %i ) ", (int)w->p[2][0], (int)w->p[2][1], (int)w->p[2][2]); - - fprintf (f, "%s 0 0 0 1 1\n", TexDataStringTable_GetString( GetTexData( texinfo[s->texinfo].texdata )->nameStringTableID ) ); - FreeWinding (w); - } - fprintf (f, "}\n"); - } - fprintf (f, "}\n"); - - fclose (f); - -} - -// UNDONE: This isn't quite working yet -#if 0 -void WriteBrushVMF(char *name, bspbrush_t *list) -{ - FILE *f; - side_t *s; - int i; - winding_t *w; - Vector u, v; - - Msg("writing %s\n", name); - f = fopen (name, "w"); - if (!f) - Error ("Can't write %s\b", name); - - fprintf (f, "world\n{\n\"classname\" \"worldspawn\"\n"); - - for ( ; list ; list=list->next ) - { - fprintf (f, "\tsolid\n\t{\n"); - for (i=0,s=list->sides ; inumsides ; i++,s++) - { - fprintf( f, "\t\tside\n\t\t{\n" ); - fprintf( f, "\t\t\t\"plane\" \"" ); - w = BaseWindingForPlane (mapplanes[s->planenum].normal, mapplanes[s->planenum].dist); - - fprintf (f,"(%i %i %i) ", (int)w->p[0][0], (int)w->p[0][1], (int)w->p[0][2]); - fprintf (f,"(%i %i %i) ", (int)w->p[1][0], (int)w->p[1][1], (int)w->p[1][2]); - fprintf (f,"(%i %i %i)", (int)w->p[2][0], (int)w->p[2][1], (int)w->p[2][2]); - fprintf( f, "\"\n" ); - fprintf( f, "\t\t\t\"material\" \"%s\"\n", GetTexData( texinfo[s->texinfo].texdata )->name ); - // UNDONE: recreate correct texture axes - BasisForPlane( mapplanes[s->planenum].normal, u, v ); - fprintf( f, "\t\t\t\"uaxis\" \"[%.3f %.3f %.3f 0] 1.0\"\n", u[0], u[1], u[2] ); - fprintf( f, "\t\t\t\"vaxis\" \"[%.3f %.3f %.3f 0] 1.0\"\n", v[0], v[1], v[2] ); - - fprintf( f, "\t\t\t\"rotation\" \"0.0\"\n" ); - fprintf( f, "\t\t\t\"lightmapscale\" \"16.0\"\n" ); - - FreeWinding (w); - fprintf (f, "\t\t}\n"); - } - fprintf (f, "\t}\n"); - } - fprintf (f, "}\n"); - - fclose (f); - -} -#endif - -void PrintBrushContentsToString( int contents, char *pOut, int nMaxChars ) -{ - #define ADD_CONTENTS( flag ) \ - if ( contents & flag ) \ - Q_strncat( pOut, #flag " ", nMaxChars, COPY_ALL_CHARACTERS ); - - pOut[0] = 0; - - ADD_CONTENTS(CONTENTS_SOLID) - ADD_CONTENTS(CONTENTS_WINDOW) - ADD_CONTENTS(CONTENTS_AUX) - ADD_CONTENTS(CONTENTS_GRATE) - ADD_CONTENTS(CONTENTS_SLIME) - ADD_CONTENTS(CONTENTS_WATER) - ADD_CONTENTS(CONTENTS_BLOCKLOS) - ADD_CONTENTS(CONTENTS_OPAQUE) - ADD_CONTENTS(CONTENTS_TESTFOGVOLUME) - ADD_CONTENTS(CONTENTS_MOVEABLE) - ADD_CONTENTS(CONTENTS_AREAPORTAL) - ADD_CONTENTS(CONTENTS_PLAYERCLIP) - ADD_CONTENTS(CONTENTS_MONSTERCLIP) - ADD_CONTENTS(CONTENTS_CURRENT_0) - ADD_CONTENTS(CONTENTS_CURRENT_90) - ADD_CONTENTS(CONTENTS_CURRENT_180) - ADD_CONTENTS(CONTENTS_CURRENT_270) - ADD_CONTENTS(CONTENTS_CURRENT_UP) - ADD_CONTENTS(CONTENTS_CURRENT_DOWN) - ADD_CONTENTS(CONTENTS_ORIGIN) - ADD_CONTENTS(CONTENTS_MONSTER) - ADD_CONTENTS(CONTENTS_DEBRIS) - ADD_CONTENTS(CONTENTS_DETAIL) - ADD_CONTENTS(CONTENTS_TRANSLUCENT) - ADD_CONTENTS(CONTENTS_LADDER) - ADD_CONTENTS(CONTENTS_HITBOX) -} - -void PrintBrushContents( int contents ) -{ - char str[1024]; - PrintBrushContentsToString( contents, str, sizeof( str ) ); - Msg( "%s", str ); -} - -/* -================== -BrushGE - -Returns true if b1 is allowed to bite b2 -================== -*/ -qboolean BrushGE (bspbrush_t *b1, bspbrush_t *b2) -{ - // Areaportals are allowed to bite water + slime - // NOTE: This brush combo should have been fixed up - // in a first pass (FixupAreaportalWaterBrushes) - if( (b2->original->contents & MASK_SPLITAREAPORTAL) && - (b1->original->contents & CONTENTS_AREAPORTAL) ) - { - return true; - } - - // detail brushes never bite structural brushes - if ( (b1->original->contents & CONTENTS_DETAIL) - && !(b2->original->contents & CONTENTS_DETAIL) ) - return false; - if (b1->original->contents & CONTENTS_SOLID) - return true; - // Transparent brushes are not marked as detail anymore, so let them cut each other. - if ( (b1->original->contents & TRANSPARENT_CONTENTS) && (b2->original->contents & TRANSPARENT_CONTENTS) ) - return true; - - return false; -} - -/* -================= -ChopBrushes - -Carves any intersecting solid brushes into the minimum number -of non-intersecting brushes. -================= -*/ -bspbrush_t *ChopBrushes (bspbrush_t *head) -{ - bspbrush_t *b1, *b2, *next; - bspbrush_t *tail; - bspbrush_t *keep; - bspbrush_t *sub, *sub2; - int c1, c2; - - qprintf ("---- ChopBrushes ----\n"); - qprintf ("original brushes: %i\n", CountBrushList (head)); - -#if DEBUG_BRUSHMODEL - if (entity_num == DEBUG_BRUSHMODEL) - WriteBrushList ("before.gl", head, false); -#endif - keep = NULL; - -newlist: - // find tail - if (!head) - return NULL; - for (tail=head ; tail->next ; tail=tail->next) - ; - - for (b1=head ; b1 ; b1=next) - { - next = b1->next; - for (b2=b1->next ; b2 ; b2 = b2->next) - { - if (BrushesDisjoint (b1, b2)) - continue; - - sub = NULL; - sub2 = NULL; - c1 = 999999; - c2 = 999999; - - if ( BrushGE (b2, b1) ) - { -// printf( "b2 bites b1\n" ); - sub = SubtractBrush (b1, b2); - if (sub == b1) - continue; // didn't really intersect - if (!sub) - { // b1 is swallowed by b2 - head = CullList (b1, b1); - goto newlist; - } - c1 = CountBrushList (sub); - } - - if ( BrushGE (b1, b2) ) - { -// printf( "b1 bites b2\n" ); - sub2 = SubtractBrush (b2, b1); - if (sub2 == b2) - continue; // didn't really intersect - if (!sub2) - { // b2 is swallowed by b1 - FreeBrushList (sub); - head = CullList (b1, b2); - goto newlist; - } - c2 = CountBrushList (sub2); - } - - if (!sub && !sub2) - continue; // neither one can bite - - // only accept if it didn't fragment - // (commening this out allows full fragmentation) - if (c1 > 1 && c2 > 1) - { - const int contents1 = b1->original->contents; - const int contents2 = b2->original->contents; - // if both detail, allow fragmentation - if ( !((contents1&contents2) & CONTENTS_DETAIL) && !((contents1|contents2) & CONTENTS_AREAPORTAL) ) - { - if (sub2) - FreeBrushList (sub2); - if (sub) - FreeBrushList (sub); - continue; - } - } - - if (c1 < c2) - { - if (sub2) - FreeBrushList (sub2); - tail = AddBrushListToTail (sub, tail); - head = CullList (b1, b1); - goto newlist; - } - else - { - if (sub) - FreeBrushList (sub); - tail = AddBrushListToTail (sub2, tail); - head = CullList (b1, b2); - goto newlist; - } - } - - if (!b2) - { // b1 is no longer intersecting anything, so keep it - b1->next = keep; - keep = b1; - } - } - - qprintf ("output brushes: %i\n", CountBrushList (keep)); -#if DEBUG_BRUSHMODEL - if ( entity_num == DEBUG_BRUSHMODEL ) - { - WriteBrushList ("after.gl", keep, false); - WriteBrushMap ("after.map", keep); - } -#endif - return keep; -} - - +//========= Copyright Valve Corporation, All rights reserved. ============// +// +// Purpose: +// +// $NoKeywords: $ +// +//=============================================================================// + +#include "vbsp.h" + +/* + +tag all brushes with original contents +brushes may contain multiple contents +there will be no brush overlap after csg phase + + + + +each side has a count of the other sides it splits + +the best split will be the one that minimizes the total split counts +of all remaining sides + +precalc side on plane table + +evaluate split side +{ +cost = 0 +for all sides + for all sides + get + if side splits side and splitside is on same child + cost++; +} + + + */ + +void SplitBrush2( bspbrush_t *brush, int planenum, bspbrush_t **front, bspbrush_t **back ) +{ + SplitBrush( brush, planenum, front, back ); +#if 0 + if (*front && (*front)->sides[(*front)->numsides-1].texinfo == -1) + (*front)->sides[(*front)->numsides-1].texinfo = (*front)->sides[0].texinfo; // not -1 + if (*back && (*back)->sides[(*back)->numsides-1].texinfo == -1) + (*back)->sides[(*back)->numsides-1].texinfo = (*back)->sides[0].texinfo; // not -1 +#endif +} + +/* +=============== +SubtractBrush + +Returns a list of brushes that remain after B is subtracted from A. +May by empty if A is contained inside B. + +The originals are undisturbed. +=============== +*/ +bspbrush_t *SubtractBrush (bspbrush_t *a, bspbrush_t *b) +{ // a - b = out (list) + int i; + bspbrush_t *front, *back; + bspbrush_t *out, *in; + + in = a; + out = NULL; + for (i=0 ; inumsides && in ; i++) + { + SplitBrush2 (in, b->sides[i].planenum, &front, &back); + if (in != a) + FreeBrush (in); + if (front) + { // add to list + front->next = out; + out = front; + } + in = back; + } + if (in) + FreeBrush (in); + else + { // didn't really intersect + FreeBrushList (out); + return a; + } + return out; +} + +/* +=============== +IntersectBrush + +Returns a single brush made up by the intersection of the +two provided brushes, or NULL if they are disjoint. + +The originals are undisturbed. +=============== +*/ +bspbrush_t *IntersectBrush (bspbrush_t *a, bspbrush_t *b) +{ + int i; + bspbrush_t *front, *back; + bspbrush_t *in; + + in = a; + for (i=0 ; inumsides && in ; i++) + { + SplitBrush2 (in, b->sides[i].planenum, &front, &back); + if (in != a) + FreeBrush (in); + if (front) + FreeBrush (front); + in = back; + } + + if (in == a || !in) + return NULL; + + in->next = NULL; + return in; +} + + +/* +=============== +BrushesDisjoint + +Returns true if the two brushes definately do not intersect. +There will be false negatives for some non-axial combinations. +=============== +*/ +qboolean BrushesDisjoint (bspbrush_t *a, bspbrush_t *b) +{ + int i, j; + + // check bounding boxes + for (i=0 ; i<3 ; i++) + if (a->mins[i] >= b->maxs[i] + || a->maxs[i] <= b->mins[i]) + return true; // bounding boxes don't overlap + + // check for opposing planes + for (i=0 ; inumsides ; i++) + { + for (j=0 ; jnumsides ; j++) + { + if (a->sides[i].planenum == + (b->sides[j].planenum^1) ) + return true; // opposite planes, so not touching + } + } + + return false; // might intersect +} + + +int minplanenums[3]; +int maxplanenums[3]; + +/* +=============== +ClipBrushToBox + +Any planes shared with the box edge will be set to no texinfo +=============== +*/ +bspbrush_t *ClipBrushToBox (bspbrush_t *brush, const Vector& clipmins, const Vector& clipmaxs) +{ + int i, j; + bspbrush_t *front, *back; + int p; + + for (j=0 ; j<2 ; j++) + { + if (brush->maxs[j] > clipmaxs[j]) + { + SplitBrush (brush, maxplanenums[j], &front, &back); + if (front) + FreeBrush (front); + brush = back; + if (!brush) + return NULL; + } + if (brush->mins[j] < clipmins[j]) + { + SplitBrush (brush, minplanenums[j], &front, &back); + if (back) + FreeBrush (back); + brush = front; + if (!brush) + return NULL; + } + } + + // remove any colinear faces + + for (i=0 ; inumsides ; i++) + { + p = brush->sides[i].planenum & ~1; + if (p == maxplanenums[0] || p == maxplanenums[1] + || p == minplanenums[0] || p == minplanenums[1]) + { + brush->sides[i].texinfo = TEXINFO_NODE; + brush->sides[i].visible = false; + } + } + return brush; +} + + +//----------------------------------------------------------------------------- +// Creates a clipped brush from a map brush +//----------------------------------------------------------------------------- +static bspbrush_t *CreateClippedBrush( mapbrush_t *mb, const Vector& clipmins, const Vector& clipmaxs ) +{ + int nNumSides = mb->numsides; + if (!nNumSides) + return NULL; + + // if the brush is outside the clip area, skip it + for (int j=0 ; j<3 ; j++) + { + if (mb->mins[j] >= clipmaxs[j] || mb->maxs[j] <= clipmins[j]) + { + return NULL; + } + } + + // make a copy of the brush + bspbrush_t *newbrush = AllocBrush( nNumSides ); + newbrush->original = mb; + newbrush->numsides = nNumSides; + memcpy (newbrush->sides, mb->original_sides, nNumSides*sizeof(side_t)); + + for (int j=0 ; jsides[j].winding) + { + newbrush->sides[j].winding = CopyWinding (newbrush->sides[j].winding); + } + + if (newbrush->sides[j].surf & SURF_HINT) + { + newbrush->sides[j].visible = true; // hints are always visible + } + + // keep a pointer to the original map brush side -- use to create the original face later!! + //newbrush->sides[j].original = &mb->original_sides[j]; + } + + VectorCopy (mb->mins, newbrush->mins); + VectorCopy (mb->maxs, newbrush->maxs); + + // carve off anything outside the clip box + newbrush = ClipBrushToBox (newbrush, clipmins, clipmaxs); + return newbrush; +} + + +//----------------------------------------------------------------------------- +// Creates a clipped brush from a map brush +//----------------------------------------------------------------------------- +static void ComputeBoundingPlanes( const Vector& clipmins, const Vector& clipmaxs ) +{ + Vector normal; + float dist; + for (int i=0 ; i<2 ; i++) + { + VectorClear (normal); + normal[i] = 1; + dist = clipmaxs[i]; + maxplanenums[i] = g_MainMap->FindFloatPlane (normal, dist); + dist = clipmins[i]; + minplanenums[i] = g_MainMap->FindFloatPlane (normal, dist); + } +} + + +//----------------------------------------------------------------------------- +// This forces copies of texinfo data for matching sides of a brush +//----------------------------------------------------------------------------- +void CopyMatchingTexinfos( side_t *pDestSides, int numDestSides, const bspbrush_t *pSource ) +{ + for ( int i = 0; i < numDestSides; i++ ) + { + side_t *pSide = &pDestSides[i]; + plane_t *pPlane = &g_MainMap->mapplanes[pSide->planenum]; + + // We have to use the *original sides* because MapBSPBrushList could have generated + // splits when cutting the original brush to the block being processed. This + // will generate faces that use TEXINFO_NODE, which is definitely *not* what we want. + // If we end up with faces using TEXINFO_NODE here, the area portal will flood into + // the entire water volume intersecting the areaportal. + + mapbrush_t *pSourceBrush = pSource->original; + Assert( pSourceBrush ); + + const side_t *pSourceSide = pSourceBrush->original_sides; + const side_t *pBestSide = NULL; + float flBestDot = -1.0f; + for ( int j = 0; j < pSourceBrush->numsides; ++j, ++pSourceSide ) + { + if ( pSourceSide->texinfo == TEXINFO_NODE ) + continue; + + plane_t *pSourcePlane = &g_MainMap->mapplanes[pSourceSide->planenum]; + float flDot = DotProduct( pPlane->normal, pSourcePlane->normal ); + if ( flDot == 1.0f || pSide->planenum == pSourceSide->planenum ) + { + pBestSide = pSourceSide; + break; + } + else if ( flDot > flBestDot ) + { + pBestSide = pSourceSide; + flBestDot = flDot; + } + } + + if ( pBestSide ) + { + pSide->texinfo = pBestSide->texinfo; + if ( pSide->original ) + { + pSide->original->texinfo = pSide->texinfo; + } + } + else + { + texinfo_t *pTexInfo = &texinfo[pSide->texinfo]; + dtexdata_t *pTexData = GetTexData( pTexInfo->texdata ); + Msg("Found no matching plane for %s\n", TexDataStringTable_GetString( pTexData->nameStringTableID ) ); + } + } +} + +// This is a hack to allow areaportals to work in water +// It was done this way for ease of implementation. +// This searches a brush list to find intersecting areaportals and water +// If an areaportal is found inside water, then the water contents and +// texture information is copied over to the areaportal so that the +// resulting space has the same properties as the water (normal areaportals assume "empty" surroundings) +void FixupAreaportalWaterBrushes( bspbrush_t *pList ) +{ + for ( bspbrush_t *pAreaportal = pList; pAreaportal; pAreaportal = pAreaportal->next ) + { + if ( !(pAreaportal->original->contents & CONTENTS_AREAPORTAL) ) + continue; + + for ( bspbrush_t *pWater = pList; pWater; pWater = pWater->next ) + { + // avoid using areaportal/water combo brushes that have already been fixed up + if ( pWater->original->contents & CONTENTS_AREAPORTAL ) + continue; + + if ( !(pWater->original->contents & MASK_SPLITAREAPORTAL) ) + continue; + + if ( BrushesDisjoint( pAreaportal, pWater ) ) + continue; + + bspbrush_t *pIntersect = IntersectBrush( pAreaportal, pWater ); + if ( !pIntersect ) + continue; + FreeBrush( pIntersect ); + pAreaportal->original->contents |= pWater->original->contents; + + // HACKHACK: Ideally, this should have been done before the bspbrush_t was + // created from the map brush. But since it hasn't been, retexture the original map + // brush's sides + CopyMatchingTexinfos( pAreaportal->sides, pAreaportal->numsides, pWater ); + CopyMatchingTexinfos( pAreaportal->original->original_sides, pAreaportal->original->numsides, pWater ); + } + } +} + + +//----------------------------------------------------------------------------- +// MakeBspBrushList +//----------------------------------------------------------------------------- +// UNDONE: Put detail brushes in a separate brush array and pass that instead of "onlyDetail" ? +bspbrush_t *MakeBspBrushList (int startbrush, int endbrush, const Vector& clipmins, const Vector& clipmaxs, int detailScreen) +{ + ComputeBoundingPlanes( clipmins, clipmaxs ); + + bspbrush_t *pBrushList = NULL; + + int i; + for (i=startbrush ; imapbrushes[i]; + if ( detailScreen != FULL_DETAIL ) + { + bool onlyDetail = (detailScreen == ONLY_DETAIL); + bool detail = (mb->contents & CONTENTS_DETAIL) != 0; + if ( onlyDetail ^ detail ) + { + // both of these must have the same value or we're not interested in this brush + continue; + } + } + + bspbrush_t *pNewBrush = CreateClippedBrush( mb, clipmins, clipmaxs ); + if ( pNewBrush ) + { + pNewBrush->next = pBrushList; + pBrushList = pNewBrush; + } + } + + return pBrushList; +} + + +//----------------------------------------------------------------------------- +// A version which uses a passed-in list of brushes +//----------------------------------------------------------------------------- +bspbrush_t *MakeBspBrushList (mapbrush_t **pBrushes, int nBrushCount, const Vector& clipmins, const Vector& clipmaxs) +{ + ComputeBoundingPlanes( clipmins, clipmaxs ); + + bspbrush_t *pBrushList = NULL; + for ( int i=0; i < nBrushCount; ++i ) + { + bspbrush_t *pNewBrush = CreateClippedBrush( pBrushes[i], clipmins, clipmaxs ); + if ( pNewBrush ) + { + pNewBrush->next = pBrushList; + pBrushList = pNewBrush; + } + } + + return pBrushList; +} + + +/* +=============== +AddBspBrushListToTail +=============== +*/ +bspbrush_t *AddBrushListToTail (bspbrush_t *list, bspbrush_t *tail) +{ + bspbrush_t *walk, *next; + + for (walk=list ; walk ; walk=next) + { // add to end of list + next = walk->next; + walk->next = NULL; + tail->next = walk; + tail = walk; + } + + return tail; +} + +/* +=========== +CullList + +Builds a new list that doesn't hold the given brush +=========== +*/ +bspbrush_t *CullList (bspbrush_t *list, bspbrush_t *skip1) +{ + bspbrush_t *newlist; + bspbrush_t *next; + + newlist = NULL; + + for ( ; list ; list = next) + { + next = list->next; + if (list == skip1) + { + FreeBrush (list); + continue; + } + list->next = newlist; + newlist = list; + } + return newlist; +} + + +/* +================== +WriteBrushMap +================== +*/ +void WriteBrushMap (char *name, bspbrush_t *list) +{ + FILE *f; + side_t *s; + int i; + winding_t *w; + + Msg("writing %s\n", name); + f = fopen (name, "w"); + if (!f) + Error ("Can't write %s\b", name); + + fprintf (f, "{\n\"classname\" \"worldspawn\"\n"); + + for ( ; list ; list=list->next ) + { + fprintf (f, "{\n"); + for (i=0,s=list->sides ; inumsides ; i++,s++) + { + w = BaseWindingForPlane (g_MainMap->mapplanes[s->planenum].normal, g_MainMap->mapplanes[s->planenum].dist); + + fprintf (f,"( %i %i %i ) ", (int)w->p[0][0], (int)w->p[0][1], (int)w->p[0][2]); + fprintf (f,"( %i %i %i ) ", (int)w->p[1][0], (int)w->p[1][1], (int)w->p[1][2]); + fprintf (f,"( %i %i %i ) ", (int)w->p[2][0], (int)w->p[2][1], (int)w->p[2][2]); + + fprintf (f, "%s 0 0 0 1 1\n", TexDataStringTable_GetString( GetTexData( texinfo[s->texinfo].texdata )->nameStringTableID ) ); + FreeWinding (w); + } + fprintf (f, "}\n"); + } + fprintf (f, "}\n"); + + fclose (f); + +} + +// UNDONE: This isn't quite working yet +#if 0 +void WriteBrushVMF(char *name, bspbrush_t *list) +{ + FILE *f; + side_t *s; + int i; + winding_t *w; + Vector u, v; + + Msg("writing %s\n", name); + f = fopen (name, "w"); + if (!f) + Error ("Can't write %s\b", name); + + fprintf (f, "world\n{\n\"classname\" \"worldspawn\"\n"); + + for ( ; list ; list=list->next ) + { + fprintf (f, "\tsolid\n\t{\n"); + for (i=0,s=list->sides ; inumsides ; i++,s++) + { + fprintf( f, "\t\tside\n\t\t{\n" ); + fprintf( f, "\t\t\t\"plane\" \"" ); + w = BaseWindingForPlane (mapplanes[s->planenum].normal, mapplanes[s->planenum].dist); + + fprintf (f,"(%i %i %i) ", (int)w->p[0][0], (int)w->p[0][1], (int)w->p[0][2]); + fprintf (f,"(%i %i %i) ", (int)w->p[1][0], (int)w->p[1][1], (int)w->p[1][2]); + fprintf (f,"(%i %i %i)", (int)w->p[2][0], (int)w->p[2][1], (int)w->p[2][2]); + fprintf( f, "\"\n" ); + fprintf( f, "\t\t\t\"material\" \"%s\"\n", GetTexData( texinfo[s->texinfo].texdata )->name ); + // UNDONE: recreate correct texture axes + BasisForPlane( mapplanes[s->planenum].normal, u, v ); + fprintf( f, "\t\t\t\"uaxis\" \"[%.3f %.3f %.3f 0] 1.0\"\n", u[0], u[1], u[2] ); + fprintf( f, "\t\t\t\"vaxis\" \"[%.3f %.3f %.3f 0] 1.0\"\n", v[0], v[1], v[2] ); + + fprintf( f, "\t\t\t\"rotation\" \"0.0\"\n" ); + fprintf( f, "\t\t\t\"lightmapscale\" \"16.0\"\n" ); + + FreeWinding (w); + fprintf (f, "\t\t}\n"); + } + fprintf (f, "\t}\n"); + } + fprintf (f, "}\n"); + + fclose (f); + +} +#endif + +void PrintBrushContentsToString( int contents, char *pOut, int nMaxChars ) +{ + #define ADD_CONTENTS( flag ) \ + if ( contents & flag ) \ + Q_strncat( pOut, #flag " ", nMaxChars, COPY_ALL_CHARACTERS ); + + pOut[0] = 0; + + ADD_CONTENTS(CONTENTS_SOLID) + ADD_CONTENTS(CONTENTS_WINDOW) + ADD_CONTENTS(CONTENTS_AUX) + ADD_CONTENTS(CONTENTS_GRATE) + ADD_CONTENTS(CONTENTS_SLIME) + ADD_CONTENTS(CONTENTS_WATER) + ADD_CONTENTS(CONTENTS_BLOCKLOS) + ADD_CONTENTS(CONTENTS_OPAQUE) + ADD_CONTENTS(CONTENTS_TESTFOGVOLUME) + ADD_CONTENTS(CONTENTS_MOVEABLE) + ADD_CONTENTS(CONTENTS_AREAPORTAL) + ADD_CONTENTS(CONTENTS_PLAYERCLIP) + ADD_CONTENTS(CONTENTS_MONSTERCLIP) + ADD_CONTENTS(CONTENTS_CURRENT_0) + ADD_CONTENTS(CONTENTS_CURRENT_90) + ADD_CONTENTS(CONTENTS_CURRENT_180) + ADD_CONTENTS(CONTENTS_CURRENT_270) + ADD_CONTENTS(CONTENTS_CURRENT_UP) + ADD_CONTENTS(CONTENTS_CURRENT_DOWN) + ADD_CONTENTS(CONTENTS_ORIGIN) + ADD_CONTENTS(CONTENTS_MONSTER) + ADD_CONTENTS(CONTENTS_DEBRIS) + ADD_CONTENTS(CONTENTS_DETAIL) + ADD_CONTENTS(CONTENTS_TRANSLUCENT) + ADD_CONTENTS(CONTENTS_LADDER) + ADD_CONTENTS(CONTENTS_HITBOX) +} + +void PrintBrushContents( int contents ) +{ + char str[1024]; + PrintBrushContentsToString( contents, str, sizeof( str ) ); + Msg( "%s", str ); +} + +/* +================== +BrushGE + +Returns true if b1 is allowed to bite b2 +================== +*/ +qboolean BrushGE (bspbrush_t *b1, bspbrush_t *b2) +{ + // Areaportals are allowed to bite water + slime + // NOTE: This brush combo should have been fixed up + // in a first pass (FixupAreaportalWaterBrushes) + if( (b2->original->contents & MASK_SPLITAREAPORTAL) && + (b1->original->contents & CONTENTS_AREAPORTAL) ) + { + return true; + } + + // detail brushes never bite structural brushes + if ( (b1->original->contents & CONTENTS_DETAIL) + && !(b2->original->contents & CONTENTS_DETAIL) ) + return false; + if (b1->original->contents & CONTENTS_SOLID) + return true; + // Transparent brushes are not marked as detail anymore, so let them cut each other. + if ( (b1->original->contents & TRANSPARENT_CONTENTS) && (b2->original->contents & TRANSPARENT_CONTENTS) ) + return true; + + return false; +} + +/* +================= +ChopBrushes + +Carves any intersecting solid brushes into the minimum number +of non-intersecting brushes. +================= +*/ +bspbrush_t *ChopBrushes (bspbrush_t *head) +{ + bspbrush_t *b1, *b2, *next; + bspbrush_t *tail; + bspbrush_t *keep; + bspbrush_t *sub, *sub2; + int c1, c2; + + qprintf ("---- ChopBrushes ----\n"); + qprintf ("original brushes: %i\n", CountBrushList (head)); + +#if DEBUG_BRUSHMODEL + if (entity_num == DEBUG_BRUSHMODEL) + WriteBrushList ("before.gl", head, false); +#endif + keep = NULL; + +newlist: + // find tail + if (!head) + return NULL; + for (tail=head ; tail->next ; tail=tail->next) + ; + + for (b1=head ; b1 ; b1=next) + { + next = b1->next; + for (b2=b1->next ; b2 ; b2 = b2->next) + { + if (BrushesDisjoint (b1, b2)) + continue; + + sub = NULL; + sub2 = NULL; + c1 = 999999; + c2 = 999999; + + if ( BrushGE (b2, b1) ) + { +// printf( "b2 bites b1\n" ); + sub = SubtractBrush (b1, b2); + if (sub == b1) + continue; // didn't really intersect + if (!sub) + { // b1 is swallowed by b2 + head = CullList (b1, b1); + goto newlist; + } + c1 = CountBrushList (sub); + } + + if ( BrushGE (b1, b2) ) + { +// printf( "b1 bites b2\n" ); + sub2 = SubtractBrush (b2, b1); + if (sub2 == b2) + continue; // didn't really intersect + if (!sub2) + { // b2 is swallowed by b1 + FreeBrushList (sub); + head = CullList (b1, b2); + goto newlist; + } + c2 = CountBrushList (sub2); + } + + if (!sub && !sub2) + continue; // neither one can bite + + // only accept if it didn't fragment + // (commening this out allows full fragmentation) + if (c1 > 1 && c2 > 1) + { + const int contents1 = b1->original->contents; + const int contents2 = b2->original->contents; + // if both detail, allow fragmentation + if ( !((contents1&contents2) & CONTENTS_DETAIL) && !((contents1|contents2) & CONTENTS_AREAPORTAL) ) + { + if (sub2) + FreeBrushList (sub2); + if (sub) + FreeBrushList (sub); + continue; + } + } + + if (c1 < c2) + { + if (sub2) + FreeBrushList (sub2); + tail = AddBrushListToTail (sub, tail); + head = CullList (b1, b1); + goto newlist; + } + else + { + if (sub) + FreeBrushList (sub); + tail = AddBrushListToTail (sub2, tail); + head = CullList (b1, b2); + goto newlist; + } + } + + if (!b2) + { // b1 is no longer intersecting anything, so keep it + b1->next = keep; + keep = b1; + } + } + + qprintf ("output brushes: %i\n", CountBrushList (keep)); +#if DEBUG_BRUSHMODEL + if ( entity_num == DEBUG_BRUSHMODEL ) + { + WriteBrushList ("after.gl", keep, false); + WriteBrushMap ("after.map", keep); + } +#endif + return keep; +} + + -- cgit v1.2.3