2
===========================================================================
3
Copyright (C) 1999-2005 Id Software, Inc.
5
This file is part of Quake III Arena source code.
7
Quake III Arena source code is free software; you can redistribute it
8
and/or modify it under the terms of the GNU General Public License as
9
published by the Free Software Foundation; either version 2 of the License,
10
or (at your option) any later version.
12
Quake III Arena source code is distributed in the hope that it will be
13
useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
14
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15
GNU General Public License for more details.
17
You should have received a copy of the GNU General Public License
18
along with Quake III Arena source code; if not, write to the Free Software
19
Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
20
===========================================================================
22
// tr_marks.c -- polygon projection on the world polygons
27
#define MAX_VERTS_ON_POLY 64
29
#define MARKER_OFFSET 0 // 1
35
Out must have space for two more vertexes than in
41
static void R_ChopPolyBehindPlane( int numInPoints, vec3_t inPoints[MAX_VERTS_ON_POLY],
42
int *numOutPoints, vec3_t outPoints[MAX_VERTS_ON_POLY],
43
vec3_t normal, vec_t dist, vec_t epsilon) {
44
float dists[MAX_VERTS_ON_POLY+4];
45
int sides[MAX_VERTS_ON_POLY+4];
49
float *p1, *p2, *clip;
52
// don't clip if it might overflow
53
if ( numInPoints >= MAX_VERTS_ON_POLY - 2 ) {
58
counts[0] = counts[1] = counts[2] = 0;
60
// determine sides for each point
61
for ( i = 0 ; i < numInPoints ; i++ ) {
62
dot = DotProduct( inPoints[i], normal );
65
if ( dot > epsilon ) {
66
sides[i] = SIDE_FRONT;
67
} else if ( dot < -epsilon ) {
83
*numOutPoints = numInPoints;
84
Com_Memcpy( outPoints, inPoints, numInPoints * sizeof(vec3_t) );
88
for ( i = 0 ; i < numInPoints ; i++ ) {
90
clip = outPoints[ *numOutPoints ];
92
if ( sides[i] == SIDE_ON ) {
93
VectorCopy( p1, clip );
98
if ( sides[i] == SIDE_FRONT ) {
99
VectorCopy( p1, clip );
101
clip = outPoints[ *numOutPoints ];
104
if ( sides[i+1] == SIDE_ON || sides[i+1] == sides[i] ) {
108
// generate a split point
109
p2 = inPoints[ (i+1) % numInPoints ];
111
d = dists[i] - dists[i+1];
120
for (j=0 ; j<3 ; j++) {
121
clip[j] = p1[j] + dot * ( p2[j] - p1[j] );
134
void R_BoxSurfaces_r(mnode_t *node, vec3_t mins, vec3_t maxs, surfaceType_t **list, int listsize, int *listlength, vec3_t dir) {
137
msurface_t *surf, **mark;
139
// do the tail recursion in a loop
140
while ( node->contents == -1 ) {
141
s = BoxOnPlaneSide( mins, maxs, node->plane );
143
node = node->children[0];
145
node = node->children[1];
147
R_BoxSurfaces_r(node->children[0], mins, maxs, list, listsize, listlength, dir);
148
node = node->children[1];
152
// add the individual surfaces
153
mark = node->firstmarksurface;
154
c = node->nummarksurfaces;
157
if (*listlength >= listsize) break;
160
// check if the surface has NOIMPACT or NOMARKS set
161
if ( ( surf->shader->surfaceFlags & ( SURF_NOIMPACT | SURF_NOMARKS ) )
162
|| ( surf->shader->contentFlags & CONTENTS_FOG ) ) {
163
surf->viewCount = tr.viewCount;
165
// extra check for surfaces to avoid list overflows
166
else if (*(surf->data) == SF_FACE) {
167
// the face plane should go through the box
168
s = BoxOnPlaneSide( mins, maxs, &(( srfSurfaceFace_t * ) surf->data)->plane );
169
if (s == 1 || s == 2) {
170
surf->viewCount = tr.viewCount;
171
} else if (DotProduct((( srfSurfaceFace_t * ) surf->data)->plane.normal, dir) > -0.5) {
172
// don't add faces that make sharp angles with the projection direction
173
surf->viewCount = tr.viewCount;
176
else if (*(surfaceType_t *) (surf->data) != SF_GRID) surf->viewCount = tr.viewCount;
177
// check the viewCount because the surface may have
178
// already been added if it spans multiple leafs
179
if (surf->viewCount != tr.viewCount) {
180
surf->viewCount = tr.viewCount;
181
list[*listlength] = (surfaceType_t *) surf->data;
194
void R_AddMarkFragments(int numClipPoints, vec3_t clipPoints[2][MAX_VERTS_ON_POLY],
195
int numPlanes, vec3_t *normals, float *dists,
196
int maxPoints, vec3_t pointBuffer,
197
int maxFragments, markFragment_t *fragmentBuffer,
198
int *returnedPoints, int *returnedFragments,
199
vec3_t mins, vec3_t maxs) {
203
// chop the surface by all the bounding planes of the to be projected polygon
206
for ( i = 0 ; i < numPlanes ; i++ ) {
208
R_ChopPolyBehindPlane( numClipPoints, clipPoints[pingPong],
209
&numClipPoints, clipPoints[!pingPong],
210
normals[i], dists[i], 0.5 );
212
if ( numClipPoints == 0 ) {
216
// completely clipped away?
217
if ( numClipPoints == 0 ) {
221
// add this fragment to the returned list
222
if ( numClipPoints + (*returnedPoints) > maxPoints ) {
223
return; // not enough space for this polygon
226
// all the clip points should be within the bounding box
227
for ( i = 0 ; i < numClipPoints ; i++ ) {
229
for ( j = 0 ; j < 3 ; j++ ) {
230
if (clipPoints[pingPong][i][j] < mins[j] - 0.5) break;
231
if (clipPoints[pingPong][i][j] > maxs[j] + 0.5) break;
235
if (i < numClipPoints) return;
238
mf = fragmentBuffer + (*returnedFragments);
239
mf->firstPoint = (*returnedPoints);
240
mf->numPoints = numClipPoints;
241
Com_Memcpy( pointBuffer + (*returnedPoints) * 3, clipPoints[pingPong], numClipPoints * sizeof(vec3_t) );
243
(*returnedPoints) += numClipPoints;
244
(*returnedFragments)++;
253
int R_MarkFragments( int numPoints, const vec3_t *points, const vec3_t projection,
254
int maxPoints, vec3_t pointBuffer, int maxFragments, markFragment_t *fragmentBuffer ) {
255
int numsurfaces, numPlanes;
257
surfaceType_t *surfaces[64];
259
int returnedFragments;
261
vec3_t normals[MAX_VERTS_ON_POLY+2];
262
float dists[MAX_VERTS_ON_POLY+2];
263
vec3_t clipPoints[2][MAX_VERTS_ON_POLY];
266
srfSurfaceFace_t *surf;
270
vec3_t projectionDir;
274
//increment view count for double check prevention
278
VectorNormalize2( projection, projectionDir );
279
// find all the brushes that are to be considered
280
ClearBounds( mins, maxs );
281
for ( i = 0 ; i < numPoints ; i++ ) {
284
AddPointToBounds( points[i], mins, maxs );
285
VectorAdd( points[i], projection, temp );
286
AddPointToBounds( temp, mins, maxs );
287
// make sure we get all the leafs (also the one(s) in front of the hit surface)
288
VectorMA( points[i], -20, projectionDir, temp );
289
AddPointToBounds( temp, mins, maxs );
292
if (numPoints > MAX_VERTS_ON_POLY) numPoints = MAX_VERTS_ON_POLY;
293
// create the bounding planes for the to be projected polygon
294
for ( i = 0 ; i < numPoints ; i++ ) {
295
VectorSubtract(points[(i+1)%numPoints], points[i], v1);
296
VectorAdd(points[i], projection, v2);
297
VectorSubtract(points[i], v2, v2);
298
CrossProduct(v1, v2, normals[i]);
299
VectorNormalizeFast(normals[i]);
300
dists[i] = DotProduct(normals[i], points[i]);
302
// add near and far clipping planes for projection
303
VectorCopy(projectionDir, normals[numPoints]);
304
dists[numPoints] = DotProduct(normals[numPoints], points[0]) - 32;
305
VectorCopy(projectionDir, normals[numPoints+1]);
306
VectorInverse(normals[numPoints+1]);
307
dists[numPoints+1] = DotProduct(normals[numPoints+1], points[0]) - 20;
308
numPlanes = numPoints + 2;
311
R_BoxSurfaces_r(tr.world->nodes, mins, maxs, surfaces, 64, &numsurfaces, projectionDir);
312
//assert(numsurfaces <= 64);
313
//assert(numsurfaces != 64);
316
returnedFragments = 0;
318
for ( i = 0 ; i < numsurfaces ; i++ ) {
320
if (*surfaces[i] == SF_GRID) {
322
cv = (srfGridMesh_t *) surfaces[i];
323
for ( m = 0 ; m < cv->height - 1 ; m++ ) {
324
for ( n = 0 ; n < cv->width - 1 ; n++ ) {
325
// We triangulate the grid and chop all triangles within
326
// the bounding planes of the to be projected polygon.
327
// LOD is not taken into account, not such a big deal though.
329
// It's probably much nicer to chop the grid itself and deal
330
// with this grid as a normal SF_GRID surface so LOD will
331
// be applied. However the LOD of that chopped grid must
332
// be synced with the LOD of the original curve.
333
// One way to do this; the chopped grid shares vertices with
334
// the original curve. When LOD is applied to the original
335
// curve the unused vertices are flagged. Now the chopped curve
336
// should skip the flagged vertices. This still leaves the
337
// problems with the vertices at the chopped grid edges.
339
// To avoid issues when LOD applied to "hollow curves" (like
340
// the ones around many jump pads) we now just add a 2 unit
341
// offset to the triangle vertices.
342
// The offset is added in the vertex normal vector direction
343
// so all triangles will still fit together.
344
// The 2 unit offset should avoid pretty much all LOD problems.
348
dv = cv->verts + m * cv->width + n;
350
VectorCopy(dv[0].xyz, clipPoints[0][0]);
351
VectorMA(clipPoints[0][0], MARKER_OFFSET, dv[0].normal, clipPoints[0][0]);
352
VectorCopy(dv[cv->width].xyz, clipPoints[0][1]);
353
VectorMA(clipPoints[0][1], MARKER_OFFSET, dv[cv->width].normal, clipPoints[0][1]);
354
VectorCopy(dv[1].xyz, clipPoints[0][2]);
355
VectorMA(clipPoints[0][2], MARKER_OFFSET, dv[1].normal, clipPoints[0][2]);
356
// check the normal of this triangle
357
VectorSubtract(clipPoints[0][0], clipPoints[0][1], v1);
358
VectorSubtract(clipPoints[0][2], clipPoints[0][1], v2);
359
CrossProduct(v1, v2, normal);
360
VectorNormalizeFast(normal);
361
if (DotProduct(normal, projectionDir) < -0.1) {
362
// add the fragments of this triangle
363
R_AddMarkFragments(numClipPoints, clipPoints,
364
numPlanes, normals, dists,
365
maxPoints, pointBuffer,
366
maxFragments, fragmentBuffer,
367
&returnedPoints, &returnedFragments, mins, maxs);
369
if ( returnedFragments == maxFragments ) {
370
return returnedFragments; // not enough space for more fragments
374
VectorCopy(dv[1].xyz, clipPoints[0][0]);
375
VectorMA(clipPoints[0][0], MARKER_OFFSET, dv[1].normal, clipPoints[0][0]);
376
VectorCopy(dv[cv->width].xyz, clipPoints[0][1]);
377
VectorMA(clipPoints[0][1], MARKER_OFFSET, dv[cv->width].normal, clipPoints[0][1]);
378
VectorCopy(dv[cv->width+1].xyz, clipPoints[0][2]);
379
VectorMA(clipPoints[0][2], MARKER_OFFSET, dv[cv->width+1].normal, clipPoints[0][2]);
380
// check the normal of this triangle
381
VectorSubtract(clipPoints[0][0], clipPoints[0][1], v1);
382
VectorSubtract(clipPoints[0][2], clipPoints[0][1], v2);
383
CrossProduct(v1, v2, normal);
384
VectorNormalizeFast(normal);
385
if (DotProduct(normal, projectionDir) < -0.05) {
386
// add the fragments of this triangle
387
R_AddMarkFragments(numClipPoints, clipPoints,
388
numPlanes, normals, dists,
389
maxPoints, pointBuffer,
390
maxFragments, fragmentBuffer,
391
&returnedPoints, &returnedFragments, mins, maxs);
393
if ( returnedFragments == maxFragments ) {
394
return returnedFragments; // not enough space for more fragments
400
else if (*surfaces[i] == SF_FACE) {
402
surf = ( srfSurfaceFace_t * ) surfaces[i];
403
// check the normal of this face
404
if (DotProduct(surf->plane.normal, projectionDir) > -0.5) {
409
VectorSubtract(clipPoints[0][0], clipPoints[0][1], v1);
410
VectorSubtract(clipPoints[0][2], clipPoints[0][1], v2);
411
CrossProduct(v1, v2, normal);
412
VectorNormalize(normal);
413
if (DotProduct(normal, projectionDir) > -0.5) continue;
415
indexes = (int *)( (byte *)surf + surf->ofsIndices );
416
for ( k = 0 ; k < surf->numIndices ; k += 3 ) {
417
for ( j = 0 ; j < 3 ; j++ ) {
418
v = surf->points[0] + VERTEXSIZE * indexes[k+j];;
419
VectorMA( v, MARKER_OFFSET, surf->plane.normal, clipPoints[0][j] );
421
// add the fragments of this face
422
R_AddMarkFragments( 3 , clipPoints,
423
numPlanes, normals, dists,
424
maxPoints, pointBuffer,
425
maxFragments, fragmentBuffer,
426
&returnedPoints, &returnedFragments, mins, maxs);
427
if ( returnedFragments == maxFragments ) {
428
return returnedFragments; // not enough space for more fragments
434
// ignore all other world surfaces
435
// might be cool to also project polygons on a triangle soup
436
// however this will probably create huge amounts of extra polys
437
// even more than the projection onto curves
441
return returnedFragments;