1 /*
2 ===========================================================================
3 Copyright (C) 1999-2005 Id Software, Inc.
4
5 This file is part of Quake III Arena source code.
6
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.
11
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.
16
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 ===========================================================================
21 */
22 // tr_marks.c -- polygon projection on the world polygons
23
24 #include "tr_local.h"
25 //#include "assert.h"
26
27 #define MAX_VERTS_ON_POLY 64
28
29 #define MARKER_OFFSET 0 // 1
30
31 /*
32 =============
33 R_ChopPolyBehindPlane
34
35 Out must have space for two more vertexes than in
36 =============
37 */
38 #define SIDE_FRONT 0
39 #define SIDE_BACK 1
40 #define SIDE_ON 2
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)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];
46 int counts[3];
47 float dot;
48 int i, j;
49 float *p1, *p2, *clip;
50 float d;
51
52 // don't clip if it might overflow
53 if ( numInPoints >= MAX_VERTS_ON_POLY - 2 ) {
54 *numOutPoints = 0;
55 return;
56 }
57
58 counts[0] = counts[1] = counts[2] = 0;
59
60 // determine sides for each point
61 for ( i = 0 ; i < numInPoints ; i++ ) {
62 dot = DotProduct( inPoints[i], normal );
63 dot -= dist;
64 dists[i] = dot;
65 if ( dot > epsilon ) {
66 sides[i] = SIDE_FRONT;
67 } else if ( dot < -epsilon ) {
68 sides[i] = SIDE_BACK;
69 } else {
70 sides[i] = SIDE_ON;
71 }
72 counts[sides[i]]++;
73 }
74 sides[i] = sides[0];
75 dists[i] = dists[0];
76
77 *numOutPoints = 0;
78
79 if ( !counts[0] ) {
80 return;
81 }
82 if ( !counts[1] ) {
83 *numOutPoints = numInPoints;
84 Com_Memcpy( outPoints, inPoints, numInPoints * sizeof(vec3_t) );
85 return;
86 }
87
88 for ( i = 0 ; i < numInPoints ; i++ ) {
89 p1 = inPoints[i];
90 clip = outPoints[ *numOutPoints ];
91
92 if ( sides[i] == SIDE_ON ) {
93 VectorCopy( p1, clip );
94 (*numOutPoints)++;
95 continue;
96 }
97
98 if ( sides[i] == SIDE_FRONT ) {
99 VectorCopy( p1, clip );
100 (*numOutPoints)++;
101 clip = outPoints[ *numOutPoints ];
102 }
103
104 if ( sides[i+1] == SIDE_ON || sides[i+1] == sides[i] ) {
105 continue;
106 }
107
108 // generate a split point
109 p2 = inPoints[ (i+1) % numInPoints ];
110
111 d = dists[i] - dists[i+1];
112 if ( d == 0 ) {
113 dot = 0;
114 } else {
115 dot = dists[i] / d;
116 }
117
118 // clip xyz
119
120 for (j=0 ; j<3 ; j++) {
121 clip[j] = p1[j] + dot * ( p2[j] - p1[j] );
122 }
123
124 (*numOutPoints)++;
125 }
126 }
127
128 /*
129 =================
130 R_BoxSurfaces_r
131
132 =================
133 */
R_BoxSurfaces_r(mnode_t * node,vec3_t mins,vec3_t maxs,surfaceType_t ** list,int listsize,int * listlength,vec3_t dir)134 void R_BoxSurfaces_r(mnode_t *node, vec3_t mins, vec3_t maxs, surfaceType_t **list, int listsize, int *listlength, vec3_t dir) {
135
136 int s, c;
137 msurface_t *surf, **mark;
138
139 // do the tail recursion in a loop
140 while ( node->contents == -1 ) {
141 s = BoxOnPlaneSide( mins, maxs, node->plane );
142 if (s == 1) {
143 node = node->children[0];
144 } else if (s == 2) {
145 node = node->children[1];
146 } else {
147 R_BoxSurfaces_r(node->children[0], mins, maxs, list, listsize, listlength, dir);
148 node = node->children[1];
149 }
150 }
151
152 // add the individual surfaces
153 mark = node->firstmarksurface;
154 c = node->nummarksurfaces;
155 while (c--) {
156 //
157 if (*listlength >= listsize) break;
158 //
159 surf = *mark;
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;
164 }
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;
174 }
175 }
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;
182 (*listlength)++;
183 }
184 mark++;
185 }
186 }
187
188 /*
189 =================
190 R_AddMarkFragments
191
192 =================
193 */
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)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) {
200 int pingPong, i;
201 markFragment_t *mf;
202
203 // chop the surface by all the bounding planes of the to be projected polygon
204 pingPong = 0;
205
206 for ( i = 0 ; i < numPlanes ; i++ ) {
207
208 R_ChopPolyBehindPlane( numClipPoints, clipPoints[pingPong],
209 &numClipPoints, clipPoints[!pingPong],
210 normals[i], dists[i], 0.5 );
211 pingPong ^= 1;
212 if ( numClipPoints == 0 ) {
213 break;
214 }
215 }
216 // completely clipped away?
217 if ( numClipPoints == 0 ) {
218 return;
219 }
220
221 // add this fragment to the returned list
222 if ( numClipPoints + (*returnedPoints) > maxPoints ) {
223 return; // not enough space for this polygon
224 }
225 /*
226 // all the clip points should be within the bounding box
227 for ( i = 0 ; i < numClipPoints ; i++ ) {
228 int j;
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;
232 }
233 if (j < 3) break;
234 }
235 if (i < numClipPoints) return;
236 */
237
238 mf = fragmentBuffer + (*returnedFragments);
239 mf->firstPoint = (*returnedPoints);
240 mf->numPoints = numClipPoints;
241 Com_Memcpy( pointBuffer + (*returnedPoints) * 3, clipPoints[pingPong], numClipPoints * sizeof(vec3_t) );
242
243 (*returnedPoints) += numClipPoints;
244 (*returnedFragments)++;
245 }
246
247 /*
248 =================
249 R_MarkFragments
250
251 =================
252 */
R_MarkFragments(int numPoints,const vec3_t * points,const vec3_t projection,int maxPoints,vec3_t pointBuffer,int maxFragments,markFragment_t * fragmentBuffer)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;
256 int i, j, k, m, n;
257 surfaceType_t *surfaces[64];
258 vec3_t mins, maxs;
259 int returnedFragments;
260 int returnedPoints;
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];
264 int numClipPoints;
265 float *v;
266 srfSurfaceFace_t *surf;
267 srfGridMesh_t *cv;
268 drawVert_t *dv;
269 vec3_t normal;
270 vec3_t projectionDir;
271 vec3_t v1, v2;
272 int *indexes;
273
274 //increment view count for double check prevention
275 tr.viewCount++;
276
277 //
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++ ) {
282 vec3_t temp;
283
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 );
290 }
291
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]);
301 }
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;
309
310 numsurfaces = 0;
311 R_BoxSurfaces_r(tr.world->nodes, mins, maxs, surfaces, 64, &numsurfaces, projectionDir);
312 //assert(numsurfaces <= 64);
313 //assert(numsurfaces != 64);
314
315 returnedPoints = 0;
316 returnedFragments = 0;
317
318 for ( i = 0 ; i < numsurfaces ; i++ ) {
319
320 if (*surfaces[i] == SF_GRID) {
321
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.
328 //
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.
338 //
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.
345
346 numClipPoints = 3;
347
348 dv = cv->verts + m * cv->width + n;
349
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);
368
369 if ( returnedFragments == maxFragments ) {
370 return returnedFragments; // not enough space for more fragments
371 }
372 }
373
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);
392
393 if ( returnedFragments == maxFragments ) {
394 return returnedFragments; // not enough space for more fragments
395 }
396 }
397 }
398 }
399 }
400 else if (*surfaces[i] == SF_FACE) {
401
402 surf = ( srfSurfaceFace_t * ) surfaces[i];
403 // check the normal of this face
404 if (DotProduct(surf->plane.normal, projectionDir) > -0.5) {
405 continue;
406 }
407
408 /*
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;
414 */
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] );
420 }
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
429 }
430 }
431 continue;
432 }
433 else {
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
438 continue;
439 }
440 }
441 return returnedFragments;
442 }
443
444