From 5a85e81685300e2299dabfeb25d513b99df471be Mon Sep 17 00:00:00 2001 From: Paweł Redman Date: Fri, 6 Sep 2013 22:40:51 +0200 Subject: Initial commit --- src/qcommon/cm_patch.c | 1773 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 1773 insertions(+) create mode 100644 src/qcommon/cm_patch.c (limited to 'src/qcommon/cm_patch.c') diff --git a/src/qcommon/cm_patch.c b/src/qcommon/cm_patch.c new file mode 100644 index 0000000..55e2762 --- /dev/null +++ b/src/qcommon/cm_patch.c @@ -0,0 +1,1773 @@ +/* +=========================================================================== +Copyright (C) 1999-2005 Id Software, Inc. +Copyright (C) 2000-2009 Darklegion Development + +This file is part of Tremulous. + +Tremulous 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. + +Tremulous 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 Tremulous; if not, write to the Free Software +Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA +=========================================================================== +*/ + +#include "cm_local.h" +#include "cm_patch.h" + +/* + +This file does not reference any globals, and has these entry points: + +void CM_ClearLevelPatches( void ); +struct patchCollide_s *CM_GeneratePatchCollide( int width, int height, const vec3_t *points ); +void CM_TraceThroughPatchCollide( traceWork_t *tw, const struct patchCollide_s *pc ); +qboolean CM_PositionTestInPatchCollide( traceWork_t *tw, const struct patchCollide_s *pc ); +void CM_DrawDebugSurface( void (*drawPoly)(int color, int numPoints, flaot *points) ); + + +WARNING: this may misbehave with meshes that have rows or columns that only +degenerate a few triangles. Completely degenerate rows and columns are handled +properly. +*/ + +/* +#define MAX_FACETS 1024 +#define MAX_PATCH_PLANES 2048 + +typedef struct { + float plane[4]; + int signbits; // signx + (signy<<1) + (signz<<2), used as lookup during collision +} patchPlane_t; + +typedef struct { + int surfacePlane; + int numBorders; // 3 or four + 6 axial bevels + 4 or 3 * 4 edge bevels + int borderPlanes[4+6+16]; + int borderInward[4+6+16]; + qboolean borderNoAdjust[4+6+16]; +} facet_t; + +typedef struct patchCollide_s { + vec3_t bounds[2]; + int numPlanes; // surface planes plus edge planes + patchPlane_t *planes; + int numFacets; + facet_t *facets; +} patchCollide_t; + + +#define MAX_GRID_SIZE 129 + +typedef struct { + int width; + int height; + qboolean wrapWidth; + qboolean wrapHeight; + vec3_t points[MAX_GRID_SIZE][MAX_GRID_SIZE]; // [width][height] +} cGrid_t; + +#define SUBDIVIDE_DISTANCE 16 //4 // never more than this units away from curve +#define PLANE_TRI_EPSILON 0.1 +#define WRAP_POINT_EPSILON 0.1 +*/ + +int c_totalPatchBlocks; +int c_totalPatchSurfaces; +int c_totalPatchEdges; + +static const patchCollide_t *debugPatchCollide; +static const facet_t *debugFacet; +static qboolean debugBlock; +static vec3_t debugBlockPoints[4]; + +/* +================= +CM_ClearLevelPatches +================= +*/ +void CM_ClearLevelPatches( void ) { + debugPatchCollide = NULL; + debugFacet = NULL; +} + +/* +================= +CM_SignbitsForNormal +================= +*/ +static int CM_SignbitsForNormal( vec3_t normal ) { + int bits, j; + + bits = 0; + for (j=0 ; j<3 ; j++) { + if ( normal[j] < 0 ) { + bits |= 1<= SUBDIVIDE_DISTANCE; +} + +/* +=============== +CM_Subdivide + +a, b, and c are control points. +the subdivided sequence will be: a, out1, out2, out3, c +=============== +*/ +static void CM_Subdivide( vec3_t a, vec3_t b, vec3_t c, vec3_t out1, vec3_t out2, vec3_t out3 ) { + int i; + + for ( i = 0 ; i < 3 ; i++ ) { + out1[i] = 0.5 * (a[i] + b[i]); + out3[i] = 0.5 * (b[i] + c[i]); + out2[i] = 0.5 * (out1[i] + out3[i]); + } +} + +/* +================= +CM_TransposeGrid + +Swaps the rows and columns in place +================= +*/ +static void CM_TransposeGrid( cGrid_t *grid ) { + int i, j, l; + vec3_t temp; + qboolean tempWrap; + + if ( grid->width > grid->height ) { + for ( i = 0 ; i < grid->height ; i++ ) { + for ( j = i + 1 ; j < grid->width ; j++ ) { + if ( j < grid->height ) { + // swap the value + VectorCopy( grid->points[i][j], temp ); + VectorCopy( grid->points[j][i], grid->points[i][j] ); + VectorCopy( temp, grid->points[j][i] ); + } else { + // just copy + VectorCopy( grid->points[j][i], grid->points[i][j] ); + } + } + } + } else { + for ( i = 0 ; i < grid->width ; i++ ) { + for ( j = i + 1 ; j < grid->height ; j++ ) { + if ( j < grid->width ) { + // swap the value + VectorCopy( grid->points[j][i], temp ); + VectorCopy( grid->points[i][j], grid->points[j][i] ); + VectorCopy( temp, grid->points[i][j] ); + } else { + // just copy + VectorCopy( grid->points[i][j], grid->points[j][i] ); + } + } + } + } + + l = grid->width; + grid->width = grid->height; + grid->height = l; + + tempWrap = grid->wrapWidth; + grid->wrapWidth = grid->wrapHeight; + grid->wrapHeight = tempWrap; +} + +/* +=================== +CM_SetGridWrapWidth + +If the left and right columns are exactly equal, set grid->wrapWidth qtrue +=================== +*/ +static void CM_SetGridWrapWidth( cGrid_t *grid ) { + int i, j; + float d; + + for ( i = 0 ; i < grid->height ; i++ ) { + for ( j = 0 ; j < 3 ; j++ ) { + d = grid->points[0][i][j] - grid->points[grid->width-1][i][j]; + if ( d < -WRAP_POINT_EPSILON || d > WRAP_POINT_EPSILON ) { + break; + } + } + if ( j != 3 ) { + break; + } + } + if ( i == grid->height ) { + grid->wrapWidth = qtrue; + } else { + grid->wrapWidth = qfalse; + } +} + +/* +================= +CM_SubdivideGridColumns + +Adds columns as necessary to the grid until +all the aproximating points are within SUBDIVIDE_DISTANCE +from the true curve +================= +*/ +static void CM_SubdivideGridColumns( cGrid_t *grid ) { + int i, j, k; + + for ( i = 0 ; i < grid->width - 2 ; ) { + // grid->points[i][x] is an interpolating control point + // grid->points[i+1][x] is an aproximating control point + // grid->points[i+2][x] is an interpolating control point + + // + // first see if we can collapse the aproximating collumn away + // + for ( j = 0 ; j < grid->height ; j++ ) { + if ( CM_NeedsSubdivision( grid->points[i][j], grid->points[i+1][j], grid->points[i+2][j] ) ) { + break; + } + } + if ( j == grid->height ) { + // all of the points were close enough to the linear midpoints + // that we can collapse the entire column away + for ( j = 0 ; j < grid->height ; j++ ) { + // remove the column + for ( k = i + 2 ; k < grid->width ; k++ ) { + VectorCopy( grid->points[k][j], grid->points[k-1][j] ); + } + } + + grid->width--; + + // go to the next curve segment + i++; + continue; + } + + // + // we need to subdivide the curve + // + for ( j = 0 ; j < grid->height ; j++ ) { + vec3_t prev, mid, next; + + // save the control points now + VectorCopy( grid->points[i][j], prev ); + VectorCopy( grid->points[i+1][j], mid ); + VectorCopy( grid->points[i+2][j], next ); + + // make room for two additional columns in the grid + // columns i+1 will be replaced, column i+2 will become i+4 + // i+1, i+2, and i+3 will be generated + for ( k = grid->width - 1 ; k > i + 1 ; k-- ) { + VectorCopy( grid->points[k][j], grid->points[k+2][j] ); + } + + // generate the subdivided points + CM_Subdivide( prev, mid, next, grid->points[i+1][j], grid->points[i+2][j], grid->points[i+3][j] ); + } + + grid->width += 2; + + // the new aproximating point at i+1 may need to be removed + // or subdivided farther, so don't advance i + } +} + +/* +====================== +CM_ComparePoints +====================== +*/ +#define POINT_EPSILON 0.1 +static qboolean CM_ComparePoints( float *a, float *b ) { + float d; + + d = a[0] - b[0]; + if ( d < -POINT_EPSILON || d > POINT_EPSILON ) { + return qfalse; + } + d = a[1] - b[1]; + if ( d < -POINT_EPSILON || d > POINT_EPSILON ) { + return qfalse; + } + d = a[2] - b[2]; + if ( d < -POINT_EPSILON || d > POINT_EPSILON ) { + return qfalse; + } + return qtrue; +} + +/* +================= +CM_RemoveDegenerateColumns + +If there are any identical columns, remove them +================= +*/ +static void CM_RemoveDegenerateColumns( cGrid_t *grid ) { + int i, j, k; + + for ( i = 0 ; i < grid->width - 1 ; i++ ) { + for ( j = 0 ; j < grid->height ; j++ ) { + if ( !CM_ComparePoints( grid->points[i][j], grid->points[i+1][j] ) ) { + break; + } + } + + if ( j != grid->height ) { + continue; // not degenerate + } + + for ( j = 0 ; j < grid->height ; j++ ) { + // remove the column + for ( k = i + 2 ; k < grid->width ; k++ ) { + VectorCopy( grid->points[k][j], grid->points[k-1][j] ); + } + } + grid->width--; + + // check against the next column + i--; + } +} + +/* +================================================================================ + +PATCH COLLIDE GENERATION + +================================================================================ +*/ + +static int numPlanes; +static patchPlane_t planes[MAX_PATCH_PLANES]; + +static int numFacets; +static facet_t facets[MAX_PATCH_PLANES]; //maybe MAX_FACETS ?? + +#define NORMAL_EPSILON 0.0001 +#define DIST_EPSILON 0.02 + +/* +================== +CM_PlaneEqual +================== +*/ +int CM_PlaneEqual(patchPlane_t *p, float plane[4], int *flipped) { + float invplane[4]; + + if ( + fabs(p->plane[0] - plane[0]) < NORMAL_EPSILON + && fabs(p->plane[1] - plane[1]) < NORMAL_EPSILON + && fabs(p->plane[2] - plane[2]) < NORMAL_EPSILON + && fabs(p->plane[3] - plane[3]) < DIST_EPSILON ) + { + *flipped = qfalse; + return qtrue; + } + + VectorNegate(plane, invplane); + invplane[3] = -plane[3]; + + if ( + fabs(p->plane[0] - invplane[0]) < NORMAL_EPSILON + && fabs(p->plane[1] - invplane[1]) < NORMAL_EPSILON + && fabs(p->plane[2] - invplane[2]) < NORMAL_EPSILON + && fabs(p->plane[3] - invplane[3]) < DIST_EPSILON ) + { + *flipped = qtrue; + return qtrue; + } + + return qfalse; +} + +/* +================== +CM_SnapVector +================== +*/ +void CM_SnapVector(vec3_t normal) { + int i; + + for (i=0 ; i<3 ; i++) + { + if ( fabs(normal[i] - 1) < NORMAL_EPSILON ) + { + VectorClear (normal); + normal[i] = 1; + break; + } + if ( fabs(normal[i] - -1) < NORMAL_EPSILON ) + { + VectorClear (normal); + normal[i] = -1; + break; + } + } +} + +/* +================== +CM_FindPlane2 +================== +*/ +int CM_FindPlane2(float plane[4], int *flipped) { + int i; + + // see if the points are close enough to an existing plane + for ( i = 0 ; i < numPlanes ; i++ ) { + if (CM_PlaneEqual(&planes[i], plane, flipped)) return i; + } + + // add a new plane + if ( numPlanes == MAX_PATCH_PLANES ) { + Com_Error( ERR_DROP, "MAX_PATCH_PLANES" ); + } + + Vector4Copy( plane, planes[numPlanes].plane ); + planes[numPlanes].signbits = CM_SignbitsForNormal( plane ); + + numPlanes++; + + *flipped = qfalse; + + return numPlanes-1; +} + +/* +================== +CM_FindPlane +================== +*/ +static int CM_FindPlane( float *p1, float *p2, float *p3 ) { + float plane[4]; + int i; + float d; + + if ( !CM_PlaneFromPoints( plane, p1, p2, p3 ) ) { + return -1; + } + + // see if the points are close enough to an existing plane + for ( i = 0 ; i < numPlanes ; i++ ) { + if ( DotProduct( plane, planes[i].plane ) < 0 ) { + continue; // allow backwards planes? + } + + d = DotProduct( p1, planes[i].plane ) - planes[i].plane[3]; + if ( d < -PLANE_TRI_EPSILON || d > PLANE_TRI_EPSILON ) { + continue; + } + + d = DotProduct( p2, planes[i].plane ) - planes[i].plane[3]; + if ( d < -PLANE_TRI_EPSILON || d > PLANE_TRI_EPSILON ) { + continue; + } + + d = DotProduct( p3, planes[i].plane ) - planes[i].plane[3]; + if ( d < -PLANE_TRI_EPSILON || d > PLANE_TRI_EPSILON ) { + continue; + } + + // found it + return i; + } + + // add a new plane + if ( numPlanes == MAX_PATCH_PLANES ) { + Com_Error( ERR_DROP, "MAX_PATCH_PLANES" ); + } + + Vector4Copy( plane, planes[numPlanes].plane ); + planes[numPlanes].signbits = CM_SignbitsForNormal( plane ); + + numPlanes++; + + return numPlanes-1; +} + +/* +================== +CM_PointOnPlaneSide +================== +*/ +static int CM_PointOnPlaneSide( float *p, int planeNum ) { + float *plane; + float d; + + if ( planeNum == -1 ) { + return SIDE_ON; + } + plane = planes[ planeNum ].plane; + + d = DotProduct( p, plane ) - plane[3]; + + if ( d > PLANE_TRI_EPSILON ) { + return SIDE_FRONT; + } + + if ( d < -PLANE_TRI_EPSILON ) { + return SIDE_BACK; + } + + return SIDE_ON; +} + +/* +================== +CM_GridPlane +================== +*/ +static int CM_GridPlane( int gridPlanes[MAX_GRID_SIZE][MAX_GRID_SIZE][2], int i, int j, int tri ) { + int p; + + p = gridPlanes[i][j][tri]; + if ( p != -1 ) { + return p; + } + p = gridPlanes[i][j][!tri]; + if ( p != -1 ) { + return p; + } + + // should never happen + Com_Printf( "WARNING: CM_GridPlane unresolvable\n" ); + return -1; +} + +/* +================== +CM_EdgePlaneNum +================== +*/ +static int CM_EdgePlaneNum( cGrid_t *grid, int gridPlanes[MAX_GRID_SIZE][MAX_GRID_SIZE][2], int i, int j, int k ) { + float *p1, *p2; + vec3_t up; + int p; + + switch ( k ) { + case 0: // top border + p1 = grid->points[i][j]; + p2 = grid->points[i+1][j]; + p = CM_GridPlane( gridPlanes, i, j, 0 ); + VectorMA( p1, 4, planes[ p ].plane, up ); + return CM_FindPlane( p1, p2, up ); + + case 2: // bottom border + p1 = grid->points[i][j+1]; + p2 = grid->points[i+1][j+1]; + p = CM_GridPlane( gridPlanes, i, j, 1 ); + VectorMA( p1, 4, planes[ p ].plane, up ); + return CM_FindPlane( p2, p1, up ); + + case 3: // left border + p1 = grid->points[i][j]; + p2 = grid->points[i][j+1]; + p = CM_GridPlane( gridPlanes, i, j, 1 ); + VectorMA( p1, 4, planes[ p ].plane, up ); + return CM_FindPlane( p2, p1, up ); + + case 1: // right border + p1 = grid->points[i+1][j]; + p2 = grid->points[i+1][j+1]; + p = CM_GridPlane( gridPlanes, i, j, 0 ); + VectorMA( p1, 4, planes[ p ].plane, up ); + return CM_FindPlane( p1, p2, up ); + + case 4: // diagonal out of triangle 0 + p1 = grid->points[i+1][j+1]; + p2 = grid->points[i][j]; + p = CM_GridPlane( gridPlanes, i, j, 0 ); + VectorMA( p1, 4, planes[ p ].plane, up ); + return CM_FindPlane( p1, p2, up ); + + case 5: // diagonal out of triangle 1 + p1 = grid->points[i][j]; + p2 = grid->points[i+1][j+1]; + p = CM_GridPlane( gridPlanes, i, j, 1 ); + VectorMA( p1, 4, planes[ p ].plane, up ); + return CM_FindPlane( p1, p2, up ); + + } + + Com_Error( ERR_DROP, "CM_EdgePlaneNum: bad k" ); + return -1; +} + +/* +=================== +CM_SetBorderInward +=================== +*/ +static void CM_SetBorderInward( facet_t *facet, cGrid_t *grid, int gridPlanes[MAX_GRID_SIZE][MAX_GRID_SIZE][2], + int i, int j, int which ) { + int k, l; + float *points[4]; + int numPoints; + + switch ( which ) { + case -1: + points[0] = grid->points[i][j]; + points[1] = grid->points[i+1][j]; + points[2] = grid->points[i+1][j+1]; + points[3] = grid->points[i][j+1]; + numPoints = 4; + break; + case 0: + points[0] = grid->points[i][j]; + points[1] = grid->points[i+1][j]; + points[2] = grid->points[i+1][j+1]; + numPoints = 3; + break; + case 1: + points[0] = grid->points[i+1][j+1]; + points[1] = grid->points[i][j+1]; + points[2] = grid->points[i][j]; + numPoints = 3; + break; + default: + Com_Error( ERR_FATAL, "CM_SetBorderInward: bad parameter" ); + numPoints = 0; + break; + } + + for ( k = 0 ; k < facet->numBorders ; k++ ) { + int front, back; + + front = 0; + back = 0; + + for ( l = 0 ; l < numPoints ; l++ ) { + int side; + + side = CM_PointOnPlaneSide( points[l], facet->borderPlanes[k] ); + if ( side == SIDE_FRONT ) { + front++; + } if ( side == SIDE_BACK ) { + back++; + } + } + + if ( front && !back ) { + facet->borderInward[k] = qtrue; + } else if ( back && !front ) { + facet->borderInward[k] = qfalse; + } else if ( !front && !back ) { + // flat side border + facet->borderPlanes[k] = -1; + } else { + // bisecting side border + Com_DPrintf( "WARNING: CM_SetBorderInward: mixed plane sides\n" ); + facet->borderInward[k] = qfalse; + if ( !debugBlock ) { + debugBlock = qtrue; + VectorCopy( grid->points[i][j], debugBlockPoints[0] ); + VectorCopy( grid->points[i+1][j], debugBlockPoints[1] ); + VectorCopy( grid->points[i+1][j+1], debugBlockPoints[2] ); + VectorCopy( grid->points[i][j+1], debugBlockPoints[3] ); + } + } + } +} + +/* +================== +CM_ValidateFacet + +If the facet isn't bounded by its borders, we screwed up. +================== +*/ +static qboolean CM_ValidateFacet( facet_t *facet ) { + float plane[4]; + int j; + winding_t *w; + vec3_t bounds[2]; + + if ( facet->surfacePlane == -1 ) { + return qfalse; + } + + Vector4Copy( planes[ facet->surfacePlane ].plane, plane ); + w = BaseWindingForPlane( plane, plane[3] ); + for ( j = 0 ; j < facet->numBorders && w ; j++ ) { + if ( facet->borderPlanes[j] == -1 ) { + FreeWinding( w ); + return qfalse; + } + Vector4Copy( planes[ facet->borderPlanes[j] ].plane, plane ); + if ( !facet->borderInward[j] ) { + VectorSubtract( vec3_origin, plane, plane ); + plane[3] = -plane[3]; + } + ChopWindingInPlace( &w, plane, plane[3], 0.1f ); + } + + if ( !w ) { + return qfalse; // winding was completely chopped away + } + + // see if the facet is unreasonably large + WindingBounds( w, bounds[0], bounds[1] ); + FreeWinding( w ); + + for ( j = 0 ; j < 3 ; j++ ) { + if ( bounds[1][j] - bounds[0][j] > MAX_MAP_BOUNDS ) { + return qfalse; // we must be missing a plane + } + if ( bounds[0][j] >= MAX_MAP_BOUNDS ) { + return qfalse; + } + if ( bounds[1][j] <= -MAX_MAP_BOUNDS ) { + return qfalse; + } + } + return qtrue; // winding is fine +} + +/* +================== +CM_AddFacetBevels +================== +*/ +void CM_AddFacetBevels( facet_t *facet ) { + + int i, j, k, l; + int axis, dir, order, flipped; + float plane[4], d, newplane[4]; + winding_t *w, *w2; + vec3_t mins, maxs, vec, vec2; + + Vector4Copy( planes[ facet->surfacePlane ].plane, plane ); + + w = BaseWindingForPlane( plane, plane[3] ); + for ( j = 0 ; j < facet->numBorders && w ; j++ ) { + if (facet->borderPlanes[j] == facet->surfacePlane) continue; + Vector4Copy( planes[ facet->borderPlanes[j] ].plane, plane ); + + if ( !facet->borderInward[j] ) { + VectorSubtract( vec3_origin, plane, plane ); + plane[3] = -plane[3]; + } + + ChopWindingInPlace( &w, plane, plane[3], 0.1f ); + } + if ( !w ) { + return; + } + + WindingBounds(w, mins, maxs); + + // add the axial planes + order = 0; + for ( axis = 0 ; axis < 3 ; axis++ ) + { + for ( dir = -1 ; dir <= 1 ; dir += 2, order++ ) + { + VectorClear(plane); + plane[axis] = dir; + if (dir == 1) { + plane[3] = maxs[axis]; + } + else { + plane[3] = -mins[axis]; + } + //if it's the surface plane + if (CM_PlaneEqual(&planes[facet->surfacePlane], plane, &flipped)) { + continue; + } + // see if the plane is allready present + for ( i = 0 ; i < facet->numBorders ; i++ ) { + if (CM_PlaneEqual(&planes[facet->borderPlanes[i]], plane, &flipped)) + break; + } + + if ( i == facet->numBorders ) { + if (facet->numBorders > 4 + 6 + 16) Com_Printf("ERROR: too many bevels\n"); + facet->borderPlanes[facet->numBorders] = CM_FindPlane2(plane, &flipped); + facet->borderNoAdjust[facet->numBorders] = 0; + facet->borderInward[facet->numBorders] = flipped; + facet->numBorders++; + } + } + } + // + // add the edge bevels + // + // test the non-axial plane edges + for ( j = 0 ; j < w->numpoints ; j++ ) + { + k = (j+1)%w->numpoints; + VectorSubtract (w->p[j], w->p[k], vec); + //if it's a degenerate edge + if (VectorNormalize (vec) < 0.5) + continue; + CM_SnapVector(vec); + for ( k = 0; k < 3 ; k++ ) + if ( vec[k] == -1 || vec[k] == 1 ) + break; // axial + if ( k < 3 ) + continue; // only test non-axial edges + + // try the six possible slanted axials from this edge + for ( axis = 0 ; axis < 3 ; axis++ ) + { + for ( dir = -1 ; dir <= 1 ; dir += 2 ) + { + // construct a plane + VectorClear (vec2); + vec2[axis] = dir; + CrossProduct (vec, vec2, plane); + if (VectorNormalize (plane) < 0.5) + continue; + plane[3] = DotProduct (w->p[j], plane); + + // if all the points of the facet winding are + // behind this plane, it is a proper edge bevel + for ( l = 0 ; l < w->numpoints ; l++ ) + { + d = DotProduct (w->p[l], plane) - plane[3]; + if (d > 0.1) + break; // point in front + } + if ( l < w->numpoints ) + continue; + + //if it's the surface plane + if (CM_PlaneEqual(&planes[facet->surfacePlane], plane, &flipped)) { + continue; + } + // see if the plane is allready present + for ( i = 0 ; i < facet->numBorders ; i++ ) { + if (CM_PlaneEqual(&planes[facet->borderPlanes[i]], plane, &flipped)) { + break; + } + } + + if ( i == facet->numBorders ) { + if (facet->numBorders > 4 + 6 + 16) Com_Printf("ERROR: too many bevels\n"); + facet->borderPlanes[facet->numBorders] = CM_FindPlane2(plane, &flipped); + + for ( k = 0 ; k < facet->numBorders ; k++ ) { + if (facet->borderPlanes[facet->numBorders] == + facet->borderPlanes[k]) Com_Printf("WARNING: bevel plane already used\n"); + } + + facet->borderNoAdjust[facet->numBorders] = 0; + facet->borderInward[facet->numBorders] = flipped; + // + w2 = CopyWinding(w); + Vector4Copy(planes[facet->borderPlanes[facet->numBorders]].plane, newplane); + if (!facet->borderInward[facet->numBorders]) + { + VectorNegate(newplane, newplane); + newplane[3] = -newplane[3]; + } //end if + ChopWindingInPlace( &w2, newplane, newplane[3], 0.1f ); + if (!w2) { + Com_DPrintf("WARNING: CM_AddFacetBevels... invalid bevel\n"); + continue; + } + else { + FreeWinding(w2); + } + // + facet->numBorders++; + //already got a bevel +// break; + } + } + } + } + FreeWinding( w ); + +#ifndef BSPC + //add opposite plane + facet->borderPlanes[facet->numBorders] = facet->surfacePlane; + facet->borderNoAdjust[facet->numBorders] = 0; + facet->borderInward[facet->numBorders] = qtrue; + facet->numBorders++; +#endif //BSPC + +} + +typedef enum { + EN_TOP, + EN_RIGHT, + EN_BOTTOM, + EN_LEFT +} edgeName_t; + +/* +================== +CM_PatchCollideFromGrid +================== +*/ +static void CM_PatchCollideFromGrid( cGrid_t *grid, patchCollide_t *pf ) { + int i, j; + float *p1, *p2, *p3; + int gridPlanes[MAX_GRID_SIZE][MAX_GRID_SIZE][2]; + facet_t *facet; + int borders[4]; + int noAdjust[4]; + + numPlanes = 0; + numFacets = 0; + + // find the planes for each triangle of the grid + for ( i = 0 ; i < grid->width - 1 ; i++ ) { + for ( j = 0 ; j < grid->height - 1 ; j++ ) { + p1 = grid->points[i][j]; + p2 = grid->points[i+1][j]; + p3 = grid->points[i+1][j+1]; + gridPlanes[i][j][0] = CM_FindPlane( p1, p2, p3 ); + + p1 = grid->points[i+1][j+1]; + p2 = grid->points[i][j+1]; + p3 = grid->points[i][j]; + gridPlanes[i][j][1] = CM_FindPlane( p1, p2, p3 ); + } + } + + // create the borders for each facet + for ( i = 0 ; i < grid->width - 1 ; i++ ) { + for ( j = 0 ; j < grid->height - 1 ; j++ ) { + + borders[EN_TOP] = -1; + if ( j > 0 ) { + borders[EN_TOP] = gridPlanes[i][j-1][1]; + } else if ( grid->wrapHeight ) { + borders[EN_TOP] = gridPlanes[i][grid->height-2][1]; + } + noAdjust[EN_TOP] = ( borders[EN_TOP] == gridPlanes[i][j][0] ); + if ( borders[EN_TOP] == -1 || noAdjust[EN_TOP] ) { + borders[EN_TOP] = CM_EdgePlaneNum( grid, gridPlanes, i, j, 0 ); + } + + borders[EN_BOTTOM] = -1; + if ( j < grid->height - 2 ) { + borders[EN_BOTTOM] = gridPlanes[i][j+1][0]; + } else if ( grid->wrapHeight ) { + borders[EN_BOTTOM] = gridPlanes[i][0][0]; + } + noAdjust[EN_BOTTOM] = ( borders[EN_BOTTOM] == gridPlanes[i][j][1] ); + if ( borders[EN_BOTTOM] == -1 || noAdjust[EN_BOTTOM] ) { + borders[EN_BOTTOM] = CM_EdgePlaneNum( grid, gridPlanes, i, j, 2 ); + } + + borders[EN_LEFT] = -1; + if ( i > 0 ) { + borders[EN_LEFT] = gridPlanes[i-1][j][0]; + } else if ( grid->wrapWidth ) { + borders[EN_LEFT] = gridPlanes[grid->width-2][j][0]; + } + noAdjust[EN_LEFT] = ( borders[EN_LEFT] == gridPlanes[i][j][1] ); + if ( borders[EN_LEFT] == -1 || noAdjust[EN_LEFT] ) { + borders[EN_LEFT] = CM_EdgePlaneNum( grid, gridPlanes, i, j, 3 ); + } + + borders[EN_RIGHT] = -1; + if ( i < grid->width - 2 ) { + borders[EN_RIGHT] = gridPlanes[i+1][j][1]; + } else if ( grid->wrapWidth ) { + borders[EN_RIGHT] = gridPlanes[0][j][1]; + } + noAdjust[EN_RIGHT] = ( borders[EN_RIGHT] == gridPlanes[i][j][0] ); + if ( borders[EN_RIGHT] == -1 || noAdjust[EN_RIGHT] ) { + borders[EN_RIGHT] = CM_EdgePlaneNum( grid, gridPlanes, i, j, 1 ); + } + + if ( numFacets == MAX_FACETS ) { + Com_Error( ERR_DROP, "MAX_FACETS" ); + } + facet = &facets[numFacets]; + Com_Memset( facet, 0, sizeof( *facet ) ); + + if ( gridPlanes[i][j][0] == gridPlanes[i][j][1] ) { + if ( gridPlanes[i][j][0] == -1 ) { + continue; // degenrate + } + facet->surfacePlane = gridPlanes[i][j][0]; + facet->numBorders = 4; + facet->borderPlanes[0] = borders[EN_TOP]; + facet->borderNoAdjust[0] = noAdjust[EN_TOP]; + facet->borderPlanes[1] = borders[EN_RIGHT]; + facet->borderNoAdjust[1] = noAdjust[EN_RIGHT]; + facet->borderPlanes[2] = borders[EN_BOTTOM]; + facet->borderNoAdjust[2] = noAdjust[EN_BOTTOM]; + facet->borderPlanes[3] = borders[EN_LEFT]; + facet->borderNoAdjust[3] = noAdjust[EN_LEFT]; + CM_SetBorderInward( facet, grid, gridPlanes, i, j, -1 ); + if ( CM_ValidateFacet( facet ) ) { + CM_AddFacetBevels( facet ); + numFacets++; + } + } else { + // two seperate triangles + facet->surfacePlane = gridPlanes[i][j][0]; + facet->numBorders = 3; + facet->borderPlanes[0] = borders[EN_TOP]; + facet->borderNoAdjust[0] = noAdjust[EN_TOP]; + facet->borderPlanes[1] = borders[EN_RIGHT]; + facet->borderNoAdjust[1] = noAdjust[EN_RIGHT]; + facet->borderPlanes[2] = gridPlanes[i][j][1]; + if ( facet->borderPlanes[2] == -1 ) { + facet->borderPlanes[2] = borders[EN_BOTTOM]; + if ( facet->borderPlanes[2] == -1 ) { + facet->borderPlanes[2] = CM_EdgePlaneNum( grid, gridPlanes, i, j, 4 ); + } + } + CM_SetBorderInward( facet, grid, gridPlanes, i, j, 0 ); + if ( CM_ValidateFacet( facet ) ) { + CM_AddFacetBevels( facet ); + numFacets++; + } + + if ( numFacets == MAX_FACETS ) { + Com_Error( ERR_DROP, "MAX_FACETS" ); + } + facet = &facets[numFacets]; + Com_Memset( facet, 0, sizeof( *facet ) ); + + facet->surfacePlane = gridPlanes[i][j][1]; + facet->numBorders = 3; + facet->borderPlanes[0] = borders[EN_BOTTOM]; + facet->borderNoAdjust[0] = noAdjust[EN_BOTTOM]; + facet->borderPlanes[1] = borders[EN_LEFT]; + facet->borderNoAdjust[1] = noAdjust[EN_LEFT]; + facet->borderPlanes[2] = gridPlanes[i][j][0]; + if ( facet->borderPlanes[2] == -1 ) { + facet->borderPlanes[2] = borders[EN_TOP]; + if ( facet->borderPlanes[2] == -1 ) { + facet->borderPlanes[2] = CM_EdgePlaneNum( grid, gridPlanes, i, j, 5 ); + } + } + CM_SetBorderInward( facet, grid, gridPlanes, i, j, 1 ); + if ( CM_ValidateFacet( facet ) ) { + CM_AddFacetBevels( facet ); + numFacets++; + } + } + } + } + + // copy the results out + pf->numPlanes = numPlanes; + pf->numFacets = numFacets; + pf->facets = Hunk_Alloc( numFacets * sizeof( *pf->facets ), h_high ); + Com_Memcpy( pf->facets, facets, numFacets * sizeof( *pf->facets ) ); + pf->planes = Hunk_Alloc( numPlanes * sizeof( *pf->planes ), h_high ); + Com_Memcpy( pf->planes, planes, numPlanes * sizeof( *pf->planes ) ); +} + + +/* +=================== +CM_GeneratePatchCollide + +Creates an internal structure that will be used to perform +collision detection with a patch mesh. + +Points is packed as concatenated rows. +=================== +*/ +struct patchCollide_s *CM_GeneratePatchCollide( int width, int height, vec3_t *points ) { + patchCollide_t *pf; + cGrid_t grid; + int i, j; + + if ( width <= 2 || height <= 2 || !points ) { + Com_Error( ERR_DROP, "CM_GeneratePatchFacets: bad parameters: (%i, %i, %p)", + width, height, (void *)points ); + } + + if ( !(width & 1) || !(height & 1) ) { + Com_Error( ERR_DROP, "CM_GeneratePatchFacets: even sizes are invalid for quadratic meshes" ); + } + + if ( width > MAX_GRID_SIZE || height > MAX_GRID_SIZE ) { + Com_Error( ERR_DROP, "CM_GeneratePatchFacets: source is > MAX_GRID_SIZE" ); + } + + // build a grid + grid.width = width; + grid.height = height; + grid.wrapWidth = qfalse; + grid.wrapHeight = qfalse; + for ( i = 0 ; i < width ; i++ ) { + for ( j = 0 ; j < height ; j++ ) { + VectorCopy( points[j*width + i], grid.points[i][j] ); + } + } + + // subdivide the grid + CM_SetGridWrapWidth( &grid ); + CM_SubdivideGridColumns( &grid ); + CM_RemoveDegenerateColumns( &grid ); + + CM_TransposeGrid( &grid ); + + CM_SetGridWrapWidth( &grid ); + CM_SubdivideGridColumns( &grid ); + CM_RemoveDegenerateColumns( &grid ); + + // we now have a grid of points exactly on the curve + // the aproximate surface defined by these points will be + // collided against + pf = Hunk_Alloc( sizeof( *pf ), h_high ); + ClearBounds( pf->bounds[0], pf->bounds[1] ); + for ( i = 0 ; i < grid.width ; i++ ) { + for ( j = 0 ; j < grid.height ; j++ ) { + AddPointToBounds( grid.points[i][j], pf->bounds[0], pf->bounds[1] ); + } + } + + c_totalPatchBlocks += ( grid.width - 1 ) * ( grid.height - 1 ); + + // generate a bsp tree for the surface + CM_PatchCollideFromGrid( &grid, pf ); + + // expand by one unit for epsilon purposes + pf->bounds[0][0] -= 1; + pf->bounds[0][1] -= 1; + pf->bounds[0][2] -= 1; + + pf->bounds[1][0] += 1; + pf->bounds[1][1] += 1; + pf->bounds[1][2] += 1; + + return pf; +} + +/* +================================================================================ + +TRACE TESTING + +================================================================================ +*/ + +/* +==================== +CM_TracePointThroughPatchCollide + + special case for point traces because the patch collide "brushes" have no volume +==================== +*/ +void CM_TracePointThroughPatchCollide( traceWork_t *tw, const struct patchCollide_s *pc ) { + qboolean frontFacing[MAX_PATCH_PLANES]; + float intersection[MAX_PATCH_PLANES]; + float intersect; + const patchPlane_t *planes; + const facet_t *facet; + int i, j, k; + float offset; + float d1, d2; +#ifndef BSPC + static cvar_t *cv; +#endif //BSPC + +#ifndef BSPC + if ( !cm_playerCurveClip->integer || !tw->isPoint ) { + return; + } +#endif + + // determine the trace's relationship to all planes + planes = pc->planes; + for ( i = 0 ; i < pc->numPlanes ; i++, planes++ ) { + offset = DotProduct( tw->offsets[ planes->signbits ], planes->plane ); + d1 = DotProduct( tw->start, planes->plane ) - planes->plane[3] + offset; + d2 = DotProduct( tw->end, planes->plane ) - planes->plane[3] + offset; + if ( d1 <= 0 ) { + frontFacing[i] = qfalse; + } else { + frontFacing[i] = qtrue; + } + if ( d1 == d2 ) { + intersection[i] = 99999; + } else { + intersection[i] = d1 / ( d1 - d2 ); + if ( intersection[i] <= 0 ) { + intersection[i] = 99999; + } + } + } + + + // see if any of the surface planes are intersected + facet = pc->facets; + for ( i = 0 ; i < pc->numFacets ; i++, facet++ ) { + if ( !frontFacing[facet->surfacePlane] ) { + continue; + } + intersect = intersection[facet->surfacePlane]; + if ( intersect < 0 ) { + continue; // surface is behind the starting point + } + if ( intersect > tw->trace.fraction ) { + continue; // already hit something closer + } + for ( j = 0 ; j < facet->numBorders ; j++ ) { + k = facet->borderPlanes[j]; + if ( frontFacing[k] ^ facet->borderInward[j] ) { + if ( intersection[k] > intersect ) { + break; + } + } else { + if ( intersection[k] < intersect ) { + break; + } + } + } + if ( j == facet->numBorders ) { + // we hit this facet +#ifndef BSPC + if (!cv) { + cv = Cvar_Get( "r_debugSurfaceUpdate", "1", 0 ); + } + if (cv->integer) { + debugPatchCollide = pc; + debugFacet = facet; + } +#endif //BSPC + planes = &pc->planes[facet->surfacePlane]; + + // calculate intersection with a slight pushoff + offset = DotProduct( tw->offsets[ planes->signbits ], planes->plane ); + d1 = DotProduct( tw->start, planes->plane ) - planes->plane[3] + offset; + d2 = DotProduct( tw->end, planes->plane ) - planes->plane[3] + offset; + tw->trace.fraction = ( d1 - SURFACE_CLIP_EPSILON ) / ( d1 - d2 ); + + if ( tw->trace.fraction < 0 ) { + tw->trace.fraction = 0; + } + + VectorCopy( planes->plane, tw->trace.plane.normal ); + tw->trace.plane.dist = planes->plane[3]; + } + } +} + +/* +==================== +CM_CheckFacetPlane +==================== +*/ +int CM_CheckFacetPlane(float *plane, vec3_t start, vec3_t end, float *enterFrac, float *leaveFrac, int *hit) { + float d1, d2, f; + + *hit = qfalse; + + d1 = DotProduct( start, plane ) - plane[3]; + d2 = DotProduct( end, plane ) - plane[3]; + + // if completely in front of face, no intersection with the entire facet + if (d1 > 0 && ( d2 >= SURFACE_CLIP_EPSILON || d2 >= d1 ) ) { + return qfalse; + } + + // if it doesn't cross the plane, the plane isn't relevent + if (d1 <= 0 && d2 <= 0 ) { + return qtrue; + } + + // crosses face + if (d1 > d2) { // enter + f = (d1-SURFACE_CLIP_EPSILON) / (d1-d2); + if ( f < 0 ) { + f = 0; + } + //always favor previous plane hits and thus also the surface plane hit + if (f > *enterFrac) { + *enterFrac = f; + *hit = qtrue; + } + } else { // leave + f = (d1+SURFACE_CLIP_EPSILON) / (d1-d2); + if ( f > 1 ) { + f = 1; + } + if (f < *leaveFrac) { + *leaveFrac = f; + } + } + return qtrue; +} + +/* +==================== +CM_TraceThroughPatchCollide +==================== +*/ +void CM_TraceThroughPatchCollide( traceWork_t *tw, const struct patchCollide_s *pc ) { + int i, j, hit, hitnum; + float offset, enterFrac, leaveFrac, t; + patchPlane_t *planes; + facet_t *facet; + float plane[4] = {0, 0, 0, 0}, bestplane[4] = {0, 0, 0, 0}; + vec3_t startp, endp; +#ifndef BSPC + static cvar_t *cv; +#endif //BSPC + + if ( !CM_BoundsIntersect( tw->bounds[0], tw->bounds[1], + pc->bounds[0], pc->bounds[1] ) ) { + return; + } + + if (tw->isPoint) { + CM_TracePointThroughPatchCollide( tw, pc ); + return; + } + + facet = pc->facets; + for ( i = 0 ; i < pc->numFacets ; i++, facet++ ) { + enterFrac = -1.0; + leaveFrac = 1.0; + hitnum = -1; + // + planes = &pc->planes[ facet->surfacePlane ]; + VectorCopy(planes->plane, plane); + plane[3] = planes->plane[3]; + if ( tw->type == TT_CAPSULE ) { + // adjust the plane distance apropriately for radius + plane[3] += tw->sphere.radius; + + // find the closest point on the capsule to the plane + t = DotProduct( plane, tw->sphere.offset ); + if ( t > 0.0f ) { + VectorSubtract( tw->start, tw->sphere.offset, startp ); + VectorSubtract( tw->end, tw->sphere.offset, endp ); + } + else { + VectorAdd( tw->start, tw->sphere.offset, startp ); + VectorAdd( tw->end, tw->sphere.offset, endp ); + } + } + else { + offset = DotProduct( tw->offsets[ planes->signbits ], plane); + plane[3] -= offset; + VectorCopy( tw->start, startp ); + VectorCopy( tw->end, endp ); + } + + if (!CM_CheckFacetPlane(plane, startp, endp, &enterFrac, &leaveFrac, &hit)) { + continue; + } + if (hit) { + Vector4Copy(plane, bestplane); + } + + for ( j = 0; j < facet->numBorders; j++ ) { + planes = &pc->planes[ facet->borderPlanes[j] ]; + if (facet->borderInward[j]) { + VectorNegate(planes->plane, plane); + plane[3] = -planes->plane[3]; + } + else { + VectorCopy(planes->plane, plane); + plane[3] = planes->plane[3]; + } + if ( tw->type == TT_CAPSULE ) { + // adjust the plane distance apropriately for radius + plane[3] += tw->sphere.radius; + + // find the closest point on the capsule to the plane + t = DotProduct( plane, tw->sphere.offset ); + if ( t > 0.0f ) { + VectorSubtract( tw->start, tw->sphere.offset, startp ); + VectorSubtract( tw->end, tw->sphere.offset, endp ); + } + else { + VectorAdd( tw->start, tw->sphere.offset, startp ); + VectorAdd( tw->end, tw->sphere.offset, endp ); + } + } + else { + // NOTE: this works even though the plane might be flipped because the bbox is centered + offset = DotProduct( tw->offsets[ planes->signbits ], plane); + plane[3] += fabs(offset); + VectorCopy( tw->start, startp ); + VectorCopy( tw->end, endp ); + } + + if (!CM_CheckFacetPlane(plane, startp, endp, &enterFrac, &leaveFrac, &hit)) { + break; + } + if (hit) { + hitnum = j; + Vector4Copy(plane, bestplane); + } + } + if (j < facet->numBorders) continue; + //never clip against the back side + if (hitnum == facet->numBorders - 1) continue; + + if (enterFrac < leaveFrac && enterFrac >= 0) { + if (enterFrac < tw->trace.fraction) { + if (enterFrac < 0) { + enterFrac = 0; + } +#ifndef BSPC + if (!cv) { + cv = Cvar_Get( "r_debugSurfaceUpdate", "1", 0 ); + } + if (cv && cv->integer) { + debugPatchCollide = pc; + debugFacet = facet; + } +#endif //BSPC + + tw->trace.fraction = enterFrac; + VectorCopy( bestplane, tw->trace.plane.normal ); + tw->trace.plane.dist = bestplane[3]; + } + } + } +} + + +/* +======================================================================= + +POSITION TEST + +======================================================================= +*/ + +/* +==================== +CM_PositionTestInPatchCollide +==================== +*/ +qboolean CM_PositionTestInPatchCollide( traceWork_t *tw, const struct patchCollide_s *pc ) { + int i, j; + float offset, t; + patchPlane_t *planes; + facet_t *facet; + float plane[4]; + vec3_t startp; + + if (tw->isPoint) { + return qfalse; + } + // + facet = pc->facets; + for ( i = 0 ; i < pc->numFacets ; i++, facet++ ) { + planes = &pc->planes[ facet->surfacePlane ]; + VectorCopy(planes->plane, plane); + plane[3] = planes->plane[3]; + if ( tw->type == TT_CAPSULE ) { + // adjust the plane distance apropriately for radius + plane[3] += tw->sphere.radius; + + // find the closest point on the capsule to the plane + t = DotProduct( plane, tw->sphere.offset ); + if ( t > 0 ) { + VectorSubtract( tw->start, tw->sphere.offset, startp ); + } + else { + VectorAdd( tw->start, tw->sphere.offset, startp ); + } + } + else { + offset = DotProduct( tw->offsets[ planes->signbits ], plane); + plane[3] -= offset; + VectorCopy( tw->start, startp ); + } + + if ( DotProduct( plane, startp ) - plane[3] > 0.0f ) { + continue; + } + + for ( j = 0; j < facet->numBorders; j++ ) { + planes = &pc->planes[ facet->borderPlanes[j] ]; + if (facet->borderInward[j]) { + VectorNegate(planes->plane, plane); + plane[3] = -planes->plane[3]; + } + else { + VectorCopy(planes->plane, plane); + plane[3] = planes->plane[3]; + } + if ( tw->type == TT_CAPSULE ) { + // adjust the plane distance apropriately for radius + plane[3] += tw->sphere.radius; + + // find the closest point on the capsule to the plane + t = DotProduct( plane, tw->sphere.offset ); + if ( t > 0.0f ) { + VectorSubtract( tw->start, tw->sphere.offset, startp ); + } + else { + VectorAdd( tw->start, tw->sphere.offset, startp ); + } + } + else { + // NOTE: this works even though the plane might be flipped because the bbox is centered + offset = DotProduct( tw->offsets[ planes->signbits ], plane); + plane[3] += fabs(offset); + VectorCopy( tw->start, startp ); + } + + if ( DotProduct( plane, startp ) - plane[3] > 0.0f ) { + break; + } + } + if (j < facet->numBorders) { + continue; + } + // inside this patch facet + return qtrue; + } + return qfalse; +} + +/* +======================================================================= + +DEBUGGING + +======================================================================= +*/ + + +/* +================== +CM_DrawDebugSurface + +Called from the renderer +================== +*/ +void CM_DrawDebugSurface( void (*drawPoly)(int color, int numPoints, float *points) ) { + static cvar_t *cv; +#ifndef BSPC + static cvar_t *cv2; +#endif + const patchCollide_t *pc; + facet_t *facet; + winding_t *w; + int i, j, k, n; + int curplanenum, planenum, curinward, inward; + float plane[4]; + vec3_t mins = {-15, -15, -28}, maxs = {15, 15, 28}; + //vec3_t mins = {0, 0, 0}, maxs = {0, 0, 0}; + vec3_t v1, v2; + +#ifndef BSPC + if ( !cv2 ) + { + cv2 = Cvar_Get( "r_debugSurface", "0", 0 ); + } + + if (cv2->integer != 1) + { + return; + } +#endif + + if ( !debugPatchCollide ) { + return; + } + +#ifndef BSPC + if ( !cv ) { + cv = Cvar_Get( "cm_debugSize", "2", 0 ); + } +#endif + pc = debugPatchCollide; + + for ( i = 0, facet = pc->facets ; i < pc->numFacets ; i++, facet++ ) { + + for ( k = 0 ; k < facet->numBorders + 1; k++ ) { + // + if (k < facet->numBorders) { + planenum = facet->borderPlanes[k]; + inward = facet->borderInward[k]; + } + else { + planenum = facet->surfacePlane; + inward = qfalse; + //continue; + } + + Vector4Copy( pc->planes[ planenum ].plane, plane ); + + //planenum = facet->surfacePlane; + if ( inward ) { + VectorSubtract( vec3_origin, plane, plane ); + plane[3] = -plane[3]; + } + + plane[3] += cv->value; + //* + for (n = 0; n < 3; n++) + { + if (plane[n] > 0) v1[n] = maxs[n]; + else v1[n] = mins[n]; + } //end for + VectorNegate(plane, v2); + plane[3] += fabs(DotProduct(v1, v2)); + //*/ + + w = BaseWindingForPlane( plane, plane[3] ); + for ( j = 0 ; j < facet->numBorders + 1 && w; j++ ) { + // + if (j < facet->numBorders) { + curplanenum = facet->borderPlanes[j]; + curinward = facet->borderInward[j]; + } + else { + curplanenum = facet->surfacePlane; + curinward = qfalse; + //continue; + } + // + if (curplanenum == planenum) continue; + + Vector4Copy( pc->planes[ curplanenum ].plane, plane ); + if ( !curinward ) { + VectorSubtract( vec3_origin, plane, plane ); + plane[3] = -plane[3]; + } + // if ( !facet->borderNoAdjust[j] ) { + plane[3] -= cv->value; + // } + for (n = 0; n < 3; n++) + { + if (plane[n] > 0) v1[n] = maxs[n]; + else v1[n] = mins[n]; + } //end for + VectorNegate(plane, v2); + plane[3] -= fabs(DotProduct(v1, v2)); + + ChopWindingInPlace( &w, plane, plane[3], 0.1f ); + } + if ( w ) { + if ( facet == debugFacet ) { + drawPoly( 4, w->numpoints, w->p[0] ); + //Com_Printf("blue facet has %d border planes\n", facet->numBorders); + } else { + drawPoly( 1, w->numpoints, w->p[0] ); + } + FreeWinding( w ); + } + else + Com_Printf("winding chopped away by border planes\n"); + } + } + + // draw the debug block + { + vec3_t v[3]; + + VectorCopy( debugBlockPoints[0], v[0] ); + VectorCopy( debugBlockPoints[1], v[1] ); + VectorCopy( debugBlockPoints[2], v[2] ); + drawPoly( 2, 3, v[0] ); + + VectorCopy( debugBlockPoints[2], v[0] ); + VectorCopy( debugBlockPoints[3], v[1] ); + VectorCopy( debugBlockPoints[0], v[2] ); + drawPoly( 2, 3, v[0] ); + } + +#if 0 + vec3_t v[4]; + + v[0][0] = pc->bounds[1][0]; + v[0][1] = pc->bounds[1][1]; + v[0][2] = pc->bounds[1][2]; + + v[1][0] = pc->bounds[1][0]; + v[1][1] = pc->bounds[0][1]; + v[1][2] = pc->bounds[1][2]; + + v[2][0] = pc->bounds[0][0]; + v[2][1] = pc->bounds[0][1]; + v[2][2] = pc->bounds[1][2]; + + v[3][0] = pc->bounds[0][0]; + v[3][1] = pc->bounds[1][1]; + v[3][2] = pc->bounds[1][2]; + + drawPoly( 4, v[0] ); +#endif +} -- cgit