ref: 84cdb4e2e9e1712fc913c05c38f3cf94ca100e5d
dir: /code/renderer/tr_marks.c/
/*
===========================================================================
Copyright (C) 1999-2005 Id Software, Inc.
This file is part of Quake III Arena source code.
Quake III Arena source code 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.
Quake III Arena source code 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 Foobar; if not, write to the Free Software
Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
===========================================================================
*/
// tr_marks.c -- polygon projection on the world polygons
#include "tr_local.h"
//#include "assert.h"
#define MAX_VERTS_ON_POLY 64
#define MARKER_OFFSET 0 // 1
/*
=============
R_ChopPolyBehindPlane
Out must have space for two more vertexes than in
=============
*/
#define SIDE_FRONT 0
#define SIDE_BACK 1
#define SIDE_ON 2
static void R_ChopPolyBehindPlane( int numInPoints, vec3_t inPoints[MAX_VERTS_ON_POLY],
int *numOutPoints, vec3_t outPoints[MAX_VERTS_ON_POLY],
vec3_t normal, vec_t dist, vec_t epsilon) {
float dists[MAX_VERTS_ON_POLY+4];
int sides[MAX_VERTS_ON_POLY+4];
int counts[3];
float dot;
int i, j;
float *p1, *p2, *clip;
float d;
// don't clip if it might overflow
if ( numInPoints >= MAX_VERTS_ON_POLY - 2 ) {
*numOutPoints = 0;
return;
}
counts[0] = counts[1] = counts[2] = 0;
// determine sides for each point
for ( i = 0 ; i < numInPoints ; i++ ) {
dot = DotProduct( inPoints[i], normal );
dot -= dist;
dists[i] = dot;
if ( dot > epsilon ) {
sides[i] = SIDE_FRONT;
} else if ( dot < -epsilon ) {
sides[i] = SIDE_BACK;
} else {
sides[i] = SIDE_ON;
}
counts[sides[i]]++;
}
sides[i] = sides[0];
dists[i] = dists[0];
*numOutPoints = 0;
if ( !counts[0] ) {
return;
}
if ( !counts[1] ) {
*numOutPoints = numInPoints;
Com_Memcpy( outPoints, inPoints, numInPoints * sizeof(vec3_t) );
return;
}
for ( i = 0 ; i < numInPoints ; i++ ) {
p1 = inPoints[i];
clip = outPoints[ *numOutPoints ];
if ( sides[i] == SIDE_ON ) {
VectorCopy( p1, clip );
(*numOutPoints)++;
continue;
}
if ( sides[i] == SIDE_FRONT ) {
VectorCopy( p1, clip );
(*numOutPoints)++;
clip = outPoints[ *numOutPoints ];
}
if ( sides[i+1] == SIDE_ON || sides[i+1] == sides[i] ) {
continue;
}
// generate a split point
p2 = inPoints[ (i+1) % numInPoints ];
d = dists[i] - dists[i+1];
if ( d == 0 ) {
dot = 0;
} else {
dot = dists[i] / d;
}
// clip xyz
for (j=0 ; j<3 ; j++) {
clip[j] = p1[j] + dot * ( p2[j] - p1[j] );
}
(*numOutPoints)++;
}
}
/*
=================
R_BoxSurfaces_r
=================
*/
void R_BoxSurfaces_r(mnode_t *node, vec3_t mins, vec3_t maxs, surfaceType_t **list, int listsize, int *listlength, vec3_t dir) {
int s, c;
msurface_t *surf, **mark;
// do the tail recursion in a loop
while ( node->contents == -1 ) {
s = BoxOnPlaneSide( mins, maxs, node->plane );
if (s == 1) {
node = node->children[0];
} else if (s == 2) {
node = node->children[1];
} else {
R_BoxSurfaces_r(node->children[0], mins, maxs, list, listsize, listlength, dir);
node = node->children[1];
}
}
// add the individual surfaces
mark = node->firstmarksurface;
c = node->nummarksurfaces;
while (c--) {
//
if (*listlength >= listsize) break;
//
surf = *mark;
// check if the surface has NOIMPACT or NOMARKS set
if ( ( surf->shader->surfaceFlags & ( SURF_NOIMPACT | SURF_NOMARKS ) )
|| ( surf->shader->contentFlags & CONTENTS_FOG ) ) {
surf->viewCount = tr.viewCount;
}
// extra check for surfaces to avoid list overflows
else if (*(surf->data) == SF_FACE) {
// the face plane should go through the box
s = BoxOnPlaneSide( mins, maxs, &(( srfSurfaceFace_t * ) surf->data)->plane );
if (s == 1 || s == 2) {
surf->viewCount = tr.viewCount;
} else if (DotProduct((( srfSurfaceFace_t * ) surf->data)->plane.normal, dir) > -0.5) {
// don't add faces that make sharp angles with the projection direction
surf->viewCount = tr.viewCount;
}
}
else if (*(surfaceType_t *) (surf->data) != SF_GRID) surf->viewCount = tr.viewCount;
// check the viewCount because the surface may have
// already been added if it spans multiple leafs
if (surf->viewCount != tr.viewCount) {
surf->viewCount = tr.viewCount;
list[*listlength] = (surfaceType_t *) surf->data;
(*listlength)++;
}
mark++;
}
}
/*
=================
R_AddMarkFragments
=================
*/
void R_AddMarkFragments(int numClipPoints, vec3_t clipPoints[2][MAX_VERTS_ON_POLY],
int numPlanes, vec3_t *normals, float *dists,
int maxPoints, vec3_t pointBuffer,
int maxFragments, markFragment_t *fragmentBuffer,
int *returnedPoints, int *returnedFragments,
vec3_t mins, vec3_t maxs) {
int pingPong, i;
markFragment_t *mf;
// chop the surface by all the bounding planes of the to be projected polygon
pingPong = 0;
for ( i = 0 ; i < numPlanes ; i++ ) {
R_ChopPolyBehindPlane( numClipPoints, clipPoints[pingPong],
&numClipPoints, clipPoints[!pingPong],
normals[i], dists[i], 0.5 );
pingPong ^= 1;
if ( numClipPoints == 0 ) {
break;
}
}
// completely clipped away?
if ( numClipPoints == 0 ) {
return;
}
// add this fragment to the returned list
if ( numClipPoints + (*returnedPoints) > maxPoints ) {
return; // not enough space for this polygon
}
/*
// all the clip points should be within the bounding box
for ( i = 0 ; i < numClipPoints ; i++ ) {
int j;
for ( j = 0 ; j < 3 ; j++ ) {
if (clipPoints[pingPong][i][j] < mins[j] - 0.5) break;
if (clipPoints[pingPong][i][j] > maxs[j] + 0.5) break;
}
if (j < 3) break;
}
if (i < numClipPoints) return;
*/
mf = fragmentBuffer + (*returnedFragments);
mf->firstPoint = (*returnedPoints);
mf->numPoints = numClipPoints;
Com_Memcpy( pointBuffer + (*returnedPoints) * 3, clipPoints[pingPong], numClipPoints * sizeof(vec3_t) );
(*returnedPoints) += numClipPoints;
(*returnedFragments)++;
}
/*
=================
R_MarkFragments
=================
*/
int R_MarkFragments( int numPoints, const vec3_t *points, const vec3_t projection,
int maxPoints, vec3_t pointBuffer, int maxFragments, markFragment_t *fragmentBuffer ) {
int numsurfaces, numPlanes;
int i, j, k, m, n;
surfaceType_t *surfaces[64];
vec3_t mins, maxs;
int returnedFragments;
int returnedPoints;
vec3_t normals[MAX_VERTS_ON_POLY+2];
float dists[MAX_VERTS_ON_POLY+2];
vec3_t clipPoints[2][MAX_VERTS_ON_POLY];
int numClipPoints;
float *v;
srfSurfaceFace_t *surf;
srfGridMesh_t *cv;
drawVert_t *dv;
vec3_t normal;
vec3_t projectionDir;
vec3_t v1, v2;
int *indexes;
//increment view count for double check prevention
tr.viewCount++;
//
VectorNormalize2( projection, projectionDir );
// find all the brushes that are to be considered
ClearBounds( mins, maxs );
for ( i = 0 ; i < numPoints ; i++ ) {
vec3_t temp;
AddPointToBounds( points[i], mins, maxs );
VectorAdd( points[i], projection, temp );
AddPointToBounds( temp, mins, maxs );
// make sure we get all the leafs (also the one(s) in front of the hit surface)
VectorMA( points[i], -20, projectionDir, temp );
AddPointToBounds( temp, mins, maxs );
}
if (numPoints > MAX_VERTS_ON_POLY) numPoints = MAX_VERTS_ON_POLY;
// create the bounding planes for the to be projected polygon
for ( i = 0 ; i < numPoints ; i++ ) {
VectorSubtract(points[(i+1)%numPoints], points[i], v1);
VectorAdd(points[i], projection, v2);
VectorSubtract(points[i], v2, v2);
CrossProduct(v1, v2, normals[i]);
VectorNormalizeFast(normals[i]);
dists[i] = DotProduct(normals[i], points[i]);
}
// add near and far clipping planes for projection
VectorCopy(projectionDir, normals[numPoints]);
dists[numPoints] = DotProduct(normals[numPoints], points[0]) - 32;
VectorCopy(projectionDir, normals[numPoints+1]);
VectorInverse(normals[numPoints+1]);
dists[numPoints+1] = DotProduct(normals[numPoints+1], points[0]) - 20;
numPlanes = numPoints + 2;
numsurfaces = 0;
R_BoxSurfaces_r(tr.world->nodes, mins, maxs, surfaces, 64, &numsurfaces, projectionDir);
//assert(numsurfaces <= 64);
//assert(numsurfaces != 64);
returnedPoints = 0;
returnedFragments = 0;
for ( i = 0 ; i < numsurfaces ; i++ ) {
if (*surfaces[i] == SF_GRID) {
cv = (srfGridMesh_t *) surfaces[i];
for ( m = 0 ; m < cv->height - 1 ; m++ ) {
for ( n = 0 ; n < cv->width - 1 ; n++ ) {
// We triangulate the grid and chop all triangles within
// the bounding planes of the to be projected polygon.
// LOD is not taken into account, not such a big deal though.
//
// It's probably much nicer to chop the grid itself and deal
// with this grid as a normal SF_GRID surface so LOD will
// be applied. However the LOD of that chopped grid must
// be synced with the LOD of the original curve.
// One way to do this; the chopped grid shares vertices with
// the original curve. When LOD is applied to the original
// curve the unused vertices are flagged. Now the chopped curve
// should skip the flagged vertices. This still leaves the
// problems with the vertices at the chopped grid edges.
//
// To avoid issues when LOD applied to "hollow curves" (like
// the ones around many jump pads) we now just add a 2 unit
// offset to the triangle vertices.
// The offset is added in the vertex normal vector direction
// so all triangles will still fit together.
// The 2 unit offset should avoid pretty much all LOD problems.
numClipPoints = 3;
dv = cv->verts + m * cv->width + n;
VectorCopy(dv[0].xyz, clipPoints[0][0]);
VectorMA(clipPoints[0][0], MARKER_OFFSET, dv[0].normal, clipPoints[0][0]);
VectorCopy(dv[cv->width].xyz, clipPoints[0][1]);
VectorMA(clipPoints[0][1], MARKER_OFFSET, dv[cv->width].normal, clipPoints[0][1]);
VectorCopy(dv[1].xyz, clipPoints[0][2]);
VectorMA(clipPoints[0][2], MARKER_OFFSET, dv[1].normal, clipPoints[0][2]);
// check the normal of this triangle
VectorSubtract(clipPoints[0][0], clipPoints[0][1], v1);
VectorSubtract(clipPoints[0][2], clipPoints[0][1], v2);
CrossProduct(v1, v2, normal);
VectorNormalizeFast(normal);
if (DotProduct(normal, projectionDir) < -0.1) {
// add the fragments of this triangle
R_AddMarkFragments(numClipPoints, clipPoints,
numPlanes, normals, dists,
maxPoints, pointBuffer,
maxFragments, fragmentBuffer,
&returnedPoints, &returnedFragments, mins, maxs);
if ( returnedFragments == maxFragments ) {
return returnedFragments; // not enough space for more fragments
}
}
VectorCopy(dv[1].xyz, clipPoints[0][0]);
VectorMA(clipPoints[0][0], MARKER_OFFSET, dv[1].normal, clipPoints[0][0]);
VectorCopy(dv[cv->width].xyz, clipPoints[0][1]);
VectorMA(clipPoints[0][1], MARKER_OFFSET, dv[cv->width].normal, clipPoints[0][1]);
VectorCopy(dv[cv->width+1].xyz, clipPoints[0][2]);
VectorMA(clipPoints[0][2], MARKER_OFFSET, dv[cv->width+1].normal, clipPoints[0][2]);
// check the normal of this triangle
VectorSubtract(clipPoints[0][0], clipPoints[0][1], v1);
VectorSubtract(clipPoints[0][2], clipPoints[0][1], v2);
CrossProduct(v1, v2, normal);
VectorNormalizeFast(normal);
if (DotProduct(normal, projectionDir) < -0.05) {
// add the fragments of this triangle
R_AddMarkFragments(numClipPoints, clipPoints,
numPlanes, normals, dists,
maxPoints, pointBuffer,
maxFragments, fragmentBuffer,
&returnedPoints, &returnedFragments, mins, maxs);
if ( returnedFragments == maxFragments ) {
return returnedFragments; // not enough space for more fragments
}
}
}
}
}
else if (*surfaces[i] == SF_FACE) {
surf = ( srfSurfaceFace_t * ) surfaces[i];
// check the normal of this face
if (DotProduct(surf->plane.normal, projectionDir) > -0.5) {
continue;
}
/*
VectorSubtract(clipPoints[0][0], clipPoints[0][1], v1);
VectorSubtract(clipPoints[0][2], clipPoints[0][1], v2);
CrossProduct(v1, v2, normal);
VectorNormalize(normal);
if (DotProduct(normal, projectionDir) > -0.5) continue;
*/
indexes = (int *)( (byte *)surf + surf->ofsIndices );
for ( k = 0 ; k < surf->numIndices ; k += 3 ) {
for ( j = 0 ; j < 3 ; j++ ) {
v = surf->points[0] + VERTEXSIZE * indexes[k+j];;
VectorMA( v, MARKER_OFFSET, surf->plane.normal, clipPoints[0][j] );
}
// add the fragments of this face
R_AddMarkFragments( 3 , clipPoints,
numPlanes, normals, dists,
maxPoints, pointBuffer,
maxFragments, fragmentBuffer,
&returnedPoints, &returnedFragments, mins, maxs);
if ( returnedFragments == maxFragments ) {
return returnedFragments; // not enough space for more fragments
}
}
continue;
}
else {
// ignore all other world surfaces
// might be cool to also project polygons on a triangle soup
// however this will probably create huge amounts of extra polys
// even more than the projection onto curves
continue;
}
}
return returnedFragments;
}