1 /*
2 ===========================================================================
3 Copyright (C) 1999-2005 Id Software, Inc.
4 Copyright (C) 2006 Robert Beckebans <trebor_7@users.sourceforge.net>
5
6 This file is part of XreaL source code.
7
8 XreaL source code is free software; you can redistribute it
9 and/or modify it under the terms of the GNU General Public License as
10 published by the Free Software Foundation; either version 2 of the License,
11 or (at your option) any later version.
12
13 XreaL source code is distributed in the hope that it will be
14 useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with XreaL source code; if not, write to the Free Software
20 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
21 ===========================================================================
22 */
23 // tr_marks.c -- polygon projection on the world polygons
24 #include "tr_local.h"
25
26 #define MAX_VERTS_ON_POLY 64
27
28 #define MARKER_OFFSET 0
29
30 /*
31 =============
32 R_ChopPolyBehindPlane
33
34 Out must have space for two more vertexes than in
35 =============
36 */
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)37 static void R_ChopPolyBehindPlane(int numInPoints, vec3_t inPoints[MAX_VERTS_ON_POLY],
38 int *numOutPoints, vec3_t outPoints[MAX_VERTS_ON_POLY],
39 vec3_t normal, vec_t dist, vec_t epsilon)
40 {
41 float dists[MAX_VERTS_ON_POLY + 4];
42 int sides[MAX_VERTS_ON_POLY + 4];
43 int counts[3];
44 float dot;
45 int i, j;
46 float *p1, *p2, *clip;
47 float d;
48
49 // don't clip if it might overflow
50 if(numInPoints >= MAX_VERTS_ON_POLY - 2)
51 {
52 *numOutPoints = 0;
53 return;
54 }
55
56 counts[0] = counts[1] = counts[2] = 0;
57
58 // determine sides for each point
59 for(i = 0; i < numInPoints; i++)
60 {
61 dot = DotProduct(inPoints[i], normal);
62 dot -= dist;
63 dists[i] = dot;
64 if(dot > epsilon)
65 {
66 sides[i] = SIDE_FRONT;
67 }
68 else if(dot < -epsilon)
69 {
70 sides[i] = SIDE_BACK;
71 }
72 else
73 {
74 sides[i] = SIDE_ON;
75 }
76 counts[sides[i]]++;
77 }
78 sides[i] = sides[0];
79 dists[i] = dists[0];
80
81 *numOutPoints = 0;
82
83 if(!counts[0])
84 {
85 return;
86 }
87 if(!counts[1])
88 {
89 *numOutPoints = numInPoints;
90 Com_Memcpy(outPoints, inPoints, numInPoints * sizeof(vec3_t));
91 return;
92 }
93
94 for(i = 0; i < numInPoints; i++)
95 {
96 p1 = inPoints[i];
97 clip = outPoints[*numOutPoints];
98
99 if(sides[i] == SIDE_ON)
100 {
101 VectorCopy(p1, clip);
102 (*numOutPoints)++;
103 continue;
104 }
105
106 if(sides[i] == SIDE_FRONT)
107 {
108 VectorCopy(p1, clip);
109 (*numOutPoints)++;
110 clip = outPoints[*numOutPoints];
111 }
112
113 if(sides[i + 1] == SIDE_ON || sides[i + 1] == sides[i])
114 {
115 continue;
116 }
117
118 // generate a split point
119 p2 = inPoints[(i + 1) % numInPoints];
120
121 d = dists[i] - dists[i + 1];
122 if(d == 0)
123 {
124 dot = 0;
125 }
126 else
127 {
128 dot = dists[i] / d;
129 }
130
131 // clip xyz
132
133 for(j = 0; j < 3; j++)
134 {
135 clip[j] = p1[j] + dot * (p2[j] - p1[j]);
136 }
137
138 (*numOutPoints)++;
139 }
140 }
141
142 /*
143 =================
144 R_BoxSurfaces_r
145 =================
146 */
R_BoxSurfaces_r(mnode_t * node,vec3_t mins,vec3_t maxs,surfaceType_t ** list,int listsize,int * listlength,vec3_t dir)147 void R_BoxSurfaces_r(mnode_t * node, vec3_t mins, vec3_t maxs, surfaceType_t ** list, int listsize,
148 int *listlength, vec3_t dir)
149 {
150
151 int s, c;
152 msurface_t *surf, **mark;
153
154 // do the tail recursion in a loop
155 while(node->contents == -1)
156 {
157 s = BoxOnPlaneSide(mins, maxs, node->plane);
158 if(s == 1)
159 {
160 node = node->children[0];
161 }
162 else if(s == 2)
163 {
164 node = node->children[1];
165 }
166 else
167 {
168 R_BoxSurfaces_r(node->children[0], mins, maxs, list, listsize, listlength, dir);
169 node = node->children[1];
170 }
171 }
172
173 // add the individual surfaces
174 mark = node->firstmarksurface;
175 c = node->nummarksurfaces;
176 while(c--)
177 {
178 //
179 if(*listlength >= listsize)
180 break;
181 //
182 surf = *mark;
183 // check if the surface has NOIMPACT or NOMARKS set
184 if((surf->shader->surfaceFlags & (SURF_NOIMPACT | SURF_NOMARKS))
185 || (surf->shader->contentFlags & CONTENTS_FOG))
186 {
187 surf->viewCount = tr.viewCount;
188 }
189 // extra check for surfaces to avoid list overflows
190 else if(*(surf->data) == SF_FACE)
191 {
192 // the face plane should go through the box
193 s = BoxOnPlaneSide(mins, maxs, &((srfSurfaceFace_t *) surf->data)->plane);
194 if(s == 1 || s == 2)
195 {
196 surf->viewCount = tr.viewCount;
197 }
198 else if(DotProduct(((srfSurfaceFace_t *) surf->data)->plane.normal, dir) > -0.5)
199 {
200 // don't add faces that make sharp angles with the projection direction
201 surf->viewCount = tr.viewCount;
202 }
203 }
204 else if(*(surfaceType_t *) (surf->data) != SF_GRID)
205 surf->viewCount = tr.viewCount;
206 // check the viewCount because the surface may have
207 // already been added if it spans multiple leafs
208 if(surf->viewCount != tr.viewCount)
209 {
210 surf->viewCount = tr.viewCount;
211 list[*listlength] = (surfaceType_t *) surf->data;
212 (*listlength)++;
213 }
214 mark++;
215 }
216 }
217
218 /*
219 =================
220 R_AddMarkFragments
221
222 =================
223 */
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)224 void R_AddMarkFragments(int numClipPoints, vec3_t clipPoints[2][MAX_VERTS_ON_POLY],
225 int numPlanes, vec3_t * normals, float *dists,
226 int maxPoints, vec3_t pointBuffer,
227 int maxFragments, markFragment_t * fragmentBuffer,
228 int *returnedPoints, int *returnedFragments, vec3_t mins, vec3_t maxs)
229 {
230 int pingPong, i;
231 markFragment_t *mf;
232
233 // chop the surface by all the bounding planes of the to be projected polygon
234 pingPong = 0;
235
236 for(i = 0; i < numPlanes; i++)
237 {
238
239 R_ChopPolyBehindPlane(numClipPoints, clipPoints[pingPong],
240 &numClipPoints, clipPoints[!pingPong], normals[i], dists[i], 0.5);
241 pingPong ^= 1;
242 if(numClipPoints == 0)
243 {
244 break;
245 }
246 }
247 // completely clipped away?
248 if(numClipPoints == 0)
249 {
250 return;
251 }
252
253 // add this fragment to the returned list
254 if(numClipPoints + (*returnedPoints) > maxPoints)
255 {
256 return; // not enough space for this polygon
257 }
258 /*
259 // all the clip points should be within the bounding box
260 for ( i = 0 ; i < numClipPoints ; i++ ) {
261 int j;
262 for ( j = 0 ; j < 3 ; j++ ) {
263 if (clipPoints[pingPong][i][j] < mins[j] - 0.5) break;
264 if (clipPoints[pingPong][i][j] > maxs[j] + 0.5) break;
265 }
266 if (j < 3) break;
267 }
268 if (i < numClipPoints) return;
269 */
270
271 mf = fragmentBuffer + (*returnedFragments);
272 mf->firstPoint = (*returnedPoints);
273 mf->numPoints = numClipPoints;
274 Com_Memcpy(pointBuffer + (*returnedPoints) * 3, clipPoints[pingPong], numClipPoints * sizeof(vec3_t));
275
276 (*returnedPoints) += numClipPoints;
277 (*returnedFragments)++;
278 }
279
280 /*
281 =================
282 R_MarkFragments
283
284 =================
285 */
R_MarkFragments(int numPoints,const vec3_t * points,const vec3_t projection,int maxPoints,vec3_t pointBuffer,int maxFragments,markFragment_t * fragmentBuffer)286 int R_MarkFragments(int numPoints, const vec3_t * points, const vec3_t projection,
287 int maxPoints, vec3_t pointBuffer, int maxFragments, markFragment_t * fragmentBuffer)
288 {
289 int numsurfaces, numPlanes;
290 int i, j, k, m, n;
291 surfaceType_t *surfaces[64];
292 vec3_t mins, maxs;
293 int returnedFragments;
294 int returnedPoints;
295 vec3_t normals[MAX_VERTS_ON_POLY + 2];
296 float dists[MAX_VERTS_ON_POLY + 2];
297 vec3_t clipPoints[2][MAX_VERTS_ON_POLY];
298 int numClipPoints;
299 float *v;
300 srfSurfaceFace_t *surf;
301 srfGridMesh_t *cv;
302 srfVert_t *dv;
303 srfTriangle_t *tri;
304 vec3_t normal;
305 vec3_t projectionDir;
306 vec3_t v1, v2;
307
308 //increment view count for double check prevention
309 tr.viewCount++;
310
311 //
312 VectorNormalize2(projection, projectionDir);
313 // find all the brushes that are to be considered
314 ClearBounds(mins, maxs);
315 for(i = 0; i < numPoints; i++)
316 {
317 vec3_t temp;
318
319 AddPointToBounds(points[i], mins, maxs);
320 VectorAdd(points[i], projection, temp);
321 AddPointToBounds(temp, mins, maxs);
322 // make sure we get all the leafs (also the one(s) in front of the hit surface)
323 VectorMA(points[i], -20, projectionDir, temp);
324 AddPointToBounds(temp, mins, maxs);
325 }
326
327 if(numPoints > MAX_VERTS_ON_POLY)
328 numPoints = MAX_VERTS_ON_POLY;
329 // create the bounding planes for the to be projected polygon
330 for(i = 0; i < numPoints; i++)
331 {
332 VectorSubtract(points[(i + 1) % numPoints], points[i], v1);
333 VectorAdd(points[i], projection, v2);
334 VectorSubtract(points[i], v2, v2);
335 CrossProduct(v1, v2, normals[i]);
336 VectorNormalizeFast(normals[i]);
337 dists[i] = DotProduct(normals[i], points[i]);
338 }
339 // add near and far clipping planes for projection
340 VectorCopy(projectionDir, normals[numPoints]);
341 dists[numPoints] = DotProduct(normals[numPoints], points[0]) - 32;
342 VectorCopy(projectionDir, normals[numPoints + 1]);
343 VectorInverse(normals[numPoints + 1]);
344 dists[numPoints + 1] = DotProduct(normals[numPoints + 1], points[0]) - 20;
345 numPlanes = numPoints + 2;
346
347 numsurfaces = 0;
348 R_BoxSurfaces_r(tr.world->nodes, mins, maxs, surfaces, 64, &numsurfaces, projectionDir);
349 //assert(numsurfaces <= 64);
350 //assert(numsurfaces != 64);
351
352 returnedPoints = 0;
353 returnedFragments = 0;
354
355 for(i = 0; i < numsurfaces; i++)
356 {
357 if(*surfaces[i] == SF_GRID)
358 {
359 cv = (srfGridMesh_t *) surfaces[i];
360 for(m = 0; m < cv->height - 1; m++)
361 {
362 for(n = 0; n < cv->width - 1; n++)
363 {
364 // We triangulate the grid and chop all triangles within
365 // the bounding planes of the to be projected polygon.
366 // LOD is not taken into account, not such a big deal though.
367 //
368 // It's probably much nicer to chop the grid itself and deal
369 // with this grid as a normal SF_GRID surface so LOD will
370 // be applied. However the LOD of that chopped grid must
371 // be synced with the LOD of the original curve.
372 // One way to do this; the chopped grid shares vertices with
373 // the original curve. When LOD is applied to the original
374 // curve the unused vertices are flagged. Now the chopped curve
375 // should skip the flagged vertices. This still leaves the
376 // problems with the vertices at the chopped grid edges.
377 //
378 // To avoid issues when LOD applied to "hollow curves" (like
379 // the ones around many jump pads) we now just add a 2 unit
380 // offset to the triangle vertices.
381 // The offset is added in the vertex normal vector direction
382 // so all triangles will still fit together.
383 // The 2 unit offset should avoid pretty much all LOD problems.
384
385 numClipPoints = 3;
386
387 dv = cv->verts + m * cv->width + n;
388
389 VectorCopy(dv[0].xyz, clipPoints[0][0]);
390 VectorMA(clipPoints[0][0], MARKER_OFFSET, dv[0].normal, clipPoints[0][0]);
391 VectorCopy(dv[cv->width].xyz, clipPoints[0][1]);
392 VectorMA(clipPoints[0][1], MARKER_OFFSET, dv[cv->width].normal, clipPoints[0][1]);
393 VectorCopy(dv[1].xyz, clipPoints[0][2]);
394 VectorMA(clipPoints[0][2], MARKER_OFFSET, dv[1].normal, clipPoints[0][2]);
395 // check the normal of this triangle
396 VectorSubtract(clipPoints[0][0], clipPoints[0][1], v1);
397 VectorSubtract(clipPoints[0][2], clipPoints[0][1], v2);
398 CrossProduct(v1, v2, normal);
399 VectorNormalizeFast(normal);
400 if(DotProduct(normal, projectionDir) < -0.1)
401 {
402 // add the fragments of this triangle
403 R_AddMarkFragments(numClipPoints, clipPoints,
404 numPlanes, normals, dists,
405 maxPoints, pointBuffer,
406 maxFragments, fragmentBuffer,
407 &returnedPoints, &returnedFragments, mins, maxs);
408
409 if(returnedFragments == maxFragments)
410 {
411 return returnedFragments; // not enough space for more fragments
412 }
413 }
414
415 VectorCopy(dv[1].xyz, clipPoints[0][0]);
416 VectorMA(clipPoints[0][0], MARKER_OFFSET, dv[1].normal, clipPoints[0][0]);
417 VectorCopy(dv[cv->width].xyz, clipPoints[0][1]);
418 VectorMA(clipPoints[0][1], MARKER_OFFSET, dv[cv->width].normal, clipPoints[0][1]);
419 VectorCopy(dv[cv->width + 1].xyz, clipPoints[0][2]);
420 VectorMA(clipPoints[0][2], MARKER_OFFSET, dv[cv->width + 1].normal, clipPoints[0][2]);
421 // check the normal of this triangle
422 VectorSubtract(clipPoints[0][0], clipPoints[0][1], v1);
423 VectorSubtract(clipPoints[0][2], clipPoints[0][1], v2);
424 CrossProduct(v1, v2, normal);
425 VectorNormalizeFast(normal);
426 if(DotProduct(normal, projectionDir) < -0.05)
427 {
428 // add the fragments of this triangle
429 R_AddMarkFragments(numClipPoints, clipPoints,
430 numPlanes, normals, dists,
431 maxPoints, pointBuffer,
432 maxFragments, fragmentBuffer,
433 &returnedPoints, &returnedFragments, mins, maxs);
434
435 if(returnedFragments == maxFragments)
436 {
437 return returnedFragments; // not enough space for more fragments
438 }
439 }
440 }
441 }
442 }
443 else if(*surfaces[i] == SF_FACE)
444 {
445 surf = (srfSurfaceFace_t *) surfaces[i];
446
447 // check the normal of this face
448 if(DotProduct(surf->plane.normal, projectionDir) > -0.5)
449 {
450 continue;
451 }
452
453 /*
454 VectorSubtract(clipPoints[0][0], clipPoints[0][1], v1);
455 VectorSubtract(clipPoints[0][2], clipPoints[0][1], v2);
456 CrossProduct(v1, v2, normal);
457 VectorNormalize(normal);
458 if (DotProduct(normal, projectionDir) > -0.5) continue;
459 */
460 for(k = 0, tri = surf->triangles; k < surf->numTriangles; k++, tri++)
461 {
462 for(j = 0; j < 3; j++)
463 {
464 v = surf->verts[tri->indexes[j]].xyz;
465 VectorMA(v, MARKER_OFFSET, surf->plane.normal, clipPoints[0][j]);
466 }
467 // add the fragments of this face
468 R_AddMarkFragments(3, clipPoints,
469 numPlanes, normals, dists,
470 maxPoints, pointBuffer,
471 maxFragments, fragmentBuffer,
472 &returnedPoints, &returnedFragments, mins, maxs);
473 if(returnedFragments == maxFragments)
474 {
475 return returnedFragments; // not enough space for more fragments
476 }
477 }
478 continue;
479 }
480 else
481 {
482 // ignore all other world surfaces
483 // might be cool to also project polygons on a triangle soup
484 // however this will probably create huge amounts of extra polys
485 // even more than the projection onto curves
486 continue;
487 }
488 }
489 return returnedFragments;
490 }
491