Quake III Arena: code/renderer/tr_marks.c File Reference

00199                                              {
00200     int pingPong, i;
00201     markFragment_t  *mf;
00202 
00203     // chop the surface by all the bounding planes of the to be projected polygon
00204     pingPong = 0;
00205 
00206     for ( i = 0 ; i < numPlanes ; i++ ) {
00207 
00208         R_ChopPolyBehindPlane( numClipPoints, clipPoints[pingPong],
00209                            &numClipPoints, clipPoints[!pingPong],
00210                             normals[i], dists[i], 0.5 );
00211         pingPong ^= 1;
00212         if ( numClipPoints == 0 ) {
00213             break;
00214         }
00215     }
00216     // completely clipped away?
00217     if ( numClipPoints == 0 ) {
00218         return;
00219     }
00220 
00221     // add this fragment to the returned list
00222     if ( numClipPoints + (*returnedPoints) > maxPoints ) {
00223         return; // not enough space for this polygon
00224     }
00225     /*
00226     // all the clip points should be within the bounding box
00227     for ( i = 0 ; i < numClipPoints ; i++ ) {
00228         int j;
00229         for ( j = 0 ; j < 3 ; j++ ) {
00230             if (clipPoints[pingPong][i][j] < mins[j] - 0.5) break;
00231             if (clipPoints[pingPong][i][j] > maxs[j] + 0.5) break;
00232         }
00233         if (j < 3) break;
00234     }
00235     if (i < numClipPoints) return;
00236     */
00237 
00238     mf = fragmentBuffer + (*returnedFragments);
00239     mf->firstPoint = (*returnedPoints);
00240     mf->numPoints = numClipPoints;
00241     Com_Memcpy( pointBuffer + (*returnedPoints) * 3, clipPoints[pingPong], numClipPoints * sizeof(vec3_t) );
00242 
00243     (*returnedPoints) += numClipPoints;
00244     (*returnedFragments)++;
00245 }

00134                                                                                                                                {
00135 
00136     int         s, c;
00137     msurface_t  *surf, **mark;
00138 
00139     // do the tail recursion in a loop
00140     while ( node->contents == -1 ) {
00141         s = BoxOnPlaneSide( mins, maxs, node->plane );
00142         if (s == 1) {
00143             node = node->children[0];
00144         } else if (s == 2) {
00145             node = node->children[1];
00146         } else {
00147             R_BoxSurfaces_r(node->children[0], mins, maxs, list, listsize, listlength, dir);
00148             node = node->children[1];
00149         }
00150     }
00151 
00152     // add the individual surfaces
00153     mark = node->firstmarksurface;
00154     c = node->nummarksurfaces;
00155     while (c--) {
00156         //
00157         if (*listlength >= listsize) break;
00158         //
00159         surf = *mark;
00160         // check if the surface has NOIMPACT or NOMARKS set
00161         if ( ( surf->shader->surfaceFlags & ( SURF_NOIMPACT | SURF_NOMARKS ) )
00162             || ( surf->shader->contentFlags & CONTENTS_FOG ) ) {
00163             surf->viewCount = tr.viewCount;
00164         }
00165         // extra check for surfaces to avoid list overflows
00166         else if (*(surf->data) == SF_FACE) {
00167             // the face plane should go through the box
00168             s = BoxOnPlaneSide( mins, maxs, &(( srfSurfaceFace_t * ) surf->data)->plane );
00169             if (s == 1 || s == 2) {
00170                 surf->viewCount = tr.viewCount;
00171             } else if (DotProduct((( srfSurfaceFace_t * ) surf->data)->plane.normal, dir) > -0.5) {
00172             // don't add faces that make sharp angles with the projection direction
00173                 surf->viewCount = tr.viewCount;
00174             }
00175         }
00176         else if (*(surfaceType_t *) (surf->data) != SF_GRID) surf->viewCount = tr.viewCount;
00177         // check the viewCount because the surface may have
00178         // already been added if it spans multiple leafs
00179         if (surf->viewCount != tr.viewCount) {
00180             surf->viewCount = tr.viewCount;
00181             list[*listlength] = (surfaceType_t *) surf->data;
00182             (*listlength)++;
00183         }
00184         mark++;
00185     }
00186 }

00043                                                                       {
00044     float       dists[MAX_VERTS_ON_POLY+4];
00045     int         sides[MAX_VERTS_ON_POLY+4];
00046     int         counts[3];
00047     float       dot;
00048     int         i, j;
00049     float       *p1, *p2, *clip;
00050     float       d;
00051 
00052     // don't clip if it might overflow
00053     if ( numInPoints >= MAX_VERTS_ON_POLY - 2 ) {
00054         *numOutPoints = 0;
00055         return;
00056     }
00057 
00058     counts[0] = counts[1] = counts[2] = 0;
00059 
00060     // determine sides for each point
00061     for ( i = 0 ; i < numInPoints ; i++ ) {
00062         dot = DotProduct( inPoints[i], normal );
00063         dot -= dist;
00064         dists[i] = dot;
00065         if ( dot > epsilon ) {
00066             sides[i] = SIDE_FRONT;
00067         } else if ( dot < -epsilon ) {
00068             sides[i] = SIDE_BACK;
00069         } else {
00070             sides[i] = SIDE_ON;
00071         }
00072         counts[sides[i]]++;
00073     }
00074     sides[i] = sides[0];
00075     dists[i] = dists[0];
00076 
00077     *numOutPoints = 0;
00078 
00079     if ( !counts[0] ) {
00080         return;
00081     }
00082     if ( !counts[1] ) {
00083         *numOutPoints = numInPoints;
00084         Com_Memcpy( outPoints, inPoints, numInPoints * sizeof(vec3_t) );
00085         return;
00086     }
00087 
00088     for ( i = 0 ; i < numInPoints ; i++ ) {
00089         p1 = inPoints[i];
00090         clip = outPoints[ *numOutPoints ];
00091         
00092         if ( sides[i] == SIDE_ON ) {
00093             VectorCopy( p1, clip );
00094             (*numOutPoints)++;
00095             continue;
00096         }
00097     
00098         if ( sides[i] == SIDE_FRONT ) {
00099             VectorCopy( p1, clip );
00100             (*numOutPoints)++;
00101             clip = outPoints[ *numOutPoints ];
00102         }
00103 
00104         if ( sides[i+1] == SIDE_ON || sides[i+1] == sides[i] ) {
00105             continue;
00106         }
00107             
00108         // generate a split point
00109         p2 = inPoints[ (i+1) % numInPoints ];
00110 
00111         d = dists[i] - dists[i+1];
00112         if ( d == 0 ) {
00113             dot = 0;
00114         } else {
00115             dot = dists[i] / d;
00116         }
00117 
00118         // clip xyz
00119 
00120         for (j=0 ; j<3 ; j++) {
00121             clip[j] = p1[j] + dot * ( p2[j] - p1[j] );
00122         }
00123 
00124         (*numOutPoints)++;
00125     }
00126 }

00254                                                                                                          {
00255     int             numsurfaces, numPlanes;
00256     int             i, j, k, m, n;
00257     surfaceType_t   *surfaces[64];
00258     vec3_t          mins, maxs;
00259     int             returnedFragments;
00260     int             returnedPoints;
00261     vec3_t          normals[MAX_VERTS_ON_POLY+2];
00262     float           dists[MAX_VERTS_ON_POLY+2];
00263     vec3_t          clipPoints[2][MAX_VERTS_ON_POLY];
00264     int             numClipPoints;
00265     float           *v;
00266     srfSurfaceFace_t *surf;
00267     srfGridMesh_t   *cv;
00268     drawVert_t      *dv;
00269     vec3_t          normal;
00270     vec3_t          projectionDir;
00271     vec3_t          v1, v2;
00272     int             *indexes;
00273 
00274     //increment view count for double check prevention
00275     tr.viewCount++;
00276 
00277     //
00278     VectorNormalize2( projection, projectionDir );
00279     // find all the brushes that are to be considered
00280     ClearBounds( mins, maxs );
00281     for ( i = 0 ; i < numPoints ; i++ ) {
00282         vec3_t  temp;
00283 
00284         AddPointToBounds( points[i], mins, maxs );
00285         VectorAdd( points[i], projection, temp );
00286         AddPointToBounds( temp, mins, maxs );
00287         // make sure we get all the leafs (also the one(s) in front of the hit surface)
00288         VectorMA( points[i], -20, projectionDir, temp );
00289         AddPointToBounds( temp, mins, maxs );
00290     }
00291 
00292     if (numPoints > MAX_VERTS_ON_POLY) numPoints = MAX_VERTS_ON_POLY;
00293     // create the bounding planes for the to be projected polygon
00294     for ( i = 0 ; i < numPoints ; i++ ) {
00295         VectorSubtract(points[(i+1)%numPoints], points[i], v1);
00296         VectorAdd(points[i], projection, v2);
00297         VectorSubtract(points[i], v2, v2);
00298         CrossProduct(v1, v2, normals[i]);
00299         VectorNormalizeFast(normals[i]);
00300         dists[i] = DotProduct(normals[i], points[i]);
00301     }
00302     // add near and far clipping planes for projection
00303     VectorCopy(projectionDir, normals[numPoints]);
00304     dists[numPoints] = DotProduct(normals[numPoints], points[0]) - 32;
00305     VectorCopy(projectionDir, normals[numPoints+1]);
00306     VectorInverse(normals[numPoints+1]);
00307     dists[numPoints+1] = DotProduct(normals[numPoints+1], points[0]) - 20;
00308     numPlanes = numPoints + 2;
00309 
00310     numsurfaces = 0;
00311     R_BoxSurfaces_r(tr.world->nodes, mins, maxs, surfaces, 64, &numsurfaces, projectionDir);
00312     //assert(numsurfaces <= 64);
00313     //assert(numsurfaces != 64);
00314 
00315     returnedPoints = 0;
00316     returnedFragments = 0;
00317 
00318     for ( i = 0 ; i < numsurfaces ; i++ ) {
00319 
00320         if (*surfaces[i] == SF_GRID) {
00321 
00322             cv = (srfGridMesh_t *) surfaces[i];
00323             for ( m = 0 ; m < cv->height - 1 ; m++ ) {
00324                 for ( n = 0 ; n < cv->width - 1 ; n++ ) {
00325                     // We triangulate the grid and chop all triangles within
00326                     // the bounding planes of the to be projected polygon.
00327                     // LOD is not taken into account, not such a big deal though.
00328                     //
00329                     // It's probably much nicer to chop the grid itself and deal
00330                     // with this grid as a normal SF_GRID surface so LOD will
00331                     // be applied. However the LOD of that chopped grid must
00332                     // be synced with the LOD of the original curve.
00333                     // One way to do this; the chopped grid shares vertices with
00334                     // the original curve. When LOD is applied to the original
00335                     // curve the unused vertices are flagged. Now the chopped curve
00336                     // should skip the flagged vertices. This still leaves the
00337                     // problems with the vertices at the chopped grid edges.
00338                     //
00339                     // To avoid issues when LOD applied to "hollow curves" (like
00340                     // the ones around many jump pads) we now just add a 2 unit
00341                     // offset to the triangle vertices.
00342                     // The offset is added in the vertex normal vector direction
00343                     // so all triangles will still fit together.
00344                     // The 2 unit offset should avoid pretty much all LOD problems.
00345 
00346                     numClipPoints = 3;
00347 
00348                     dv = cv->verts + m * cv->width + n;
00349 
00350                     VectorCopy(dv[0].xyz, clipPoints[0][0]);
00351                     VectorMA(clipPoints[0][0], MARKER_OFFSET, dv[0].normal, clipPoints[0][0]);
00352                     VectorCopy(dv[cv->width].xyz, clipPoints[0][1]);
00353                     VectorMA(clipPoints[0][1], MARKER_OFFSET, dv[cv->width].normal, clipPoints[0][1]);
00354                     VectorCopy(dv[1].xyz, clipPoints[0][2]);
00355                     VectorMA(clipPoints[0][2], MARKER_OFFSET, dv[1].normal, clipPoints[0][2]);
00356                     // check the normal of this triangle
00357                     VectorSubtract(clipPoints[0][0], clipPoints[0][1], v1);
00358                     VectorSubtract(clipPoints[0][2], clipPoints[0][1], v2);
00359                     CrossProduct(v1, v2, normal);
00360                     VectorNormalizeFast(normal);
00361                     if (DotProduct(normal, projectionDir) < -0.1) {
00362                         // add the fragments of this triangle
00363                         R_AddMarkFragments(numClipPoints, clipPoints,
00364                                            numPlanes, normals, dists,
00365                                            maxPoints, pointBuffer,
00366                                            maxFragments, fragmentBuffer,
00367                                            &returnedPoints, &returnedFragments, mins, maxs);
00368 
00369                         if ( returnedFragments == maxFragments ) {
00370                             return returnedFragments;   // not enough space for more fragments
00371                         }
00372                     }
00373 
00374                     VectorCopy(dv[1].xyz, clipPoints[0][0]);
00375                     VectorMA(clipPoints[0][0], MARKER_OFFSET, dv[1].normal, clipPoints[0][0]);
00376                     VectorCopy(dv[cv->width].xyz, clipPoints[0][1]);
00377                     VectorMA(clipPoints[0][1], MARKER_OFFSET, dv[cv->width].normal, clipPoints[0][1]);
00378                     VectorCopy(dv[cv->width+1].xyz, clipPoints[0][2]);
00379                     VectorMA(clipPoints[0][2], MARKER_OFFSET, dv[cv->width+1].normal, clipPoints[0][2]);
00380                     // check the normal of this triangle
00381                     VectorSubtract(clipPoints[0][0], clipPoints[0][1], v1);
00382                     VectorSubtract(clipPoints[0][2], clipPoints[0][1], v2);
00383                     CrossProduct(v1, v2, normal);
00384                     VectorNormalizeFast(normal);
00385                     if (DotProduct(normal, projectionDir) < -0.05) {
00386                         // add the fragments of this triangle
00387                         R_AddMarkFragments(numClipPoints, clipPoints,
00388                                            numPlanes, normals, dists,
00389                                            maxPoints, pointBuffer,
00390                                            maxFragments, fragmentBuffer,
00391                                            &returnedPoints, &returnedFragments, mins, maxs);
00392 
00393                         if ( returnedFragments == maxFragments ) {
00394                             return returnedFragments;   // not enough space for more fragments
00395                         }
00396                     }
00397                 }
00398             }
00399         }
00400         else if (*surfaces[i] == SF_FACE) {
00401 
00402             surf = ( srfSurfaceFace_t * ) surfaces[i];
00403             // check the normal of this face
00404             if (DotProduct(surf->plane.normal, projectionDir) > -0.5) {
00405                 continue;
00406             }
00407 
00408             /*
00409             VectorSubtract(clipPoints[0][0], clipPoints[0][1], v1);
00410             VectorSubtract(clipPoints[0][2], clipPoints[0][1], v2);
00411             CrossProduct(v1, v2, normal);
00412             VectorNormalize(normal);
00413             if (DotProduct(normal, projectionDir) > -0.5) continue;
00414             */
00415             indexes = (int *)( (byte *)surf + surf->ofsIndices );
00416             for ( k = 0 ; k < surf->numIndices ; k += 3 ) {
00417                 for ( j = 0 ; j < 3 ; j++ ) {
00418                     v = surf->points[0] + VERTEXSIZE * indexes[k+j];;
00419                     VectorMA( v, MARKER_OFFSET, surf->plane.normal, clipPoints[0][j] );
00420                 }
00421                 // add the fragments of this face
00422                 R_AddMarkFragments( 3 , clipPoints,
00423                                    numPlanes, normals, dists,
00424                                    maxPoints, pointBuffer,
00425                                    maxFragments, fragmentBuffer,
00426                                    &returnedPoints, &returnedFragments, mins, maxs);
00427                 if ( returnedFragments == maxFragments ) {
00428                     return returnedFragments;   // not enough space for more fragments
00429                 }
00430             }
00431             continue;
00432         }
00433         else {
00434             // ignore all other world surfaces
00435             // might be cool to also project polygons on a triangle soup
00436             // however this will probably create huge amounts of extra polys
00437             // even more than the projection onto curves
00438             continue;
00439         }
00440     }
00441     return returnedFragments;
00442 }


Defines
#define	MARKER_OFFSET 0
#define	MAX_VERTS_ON_POLY 64
#define	SIDE_BACK 1
#define	SIDE_FRONT 0
#define	SIDE_ON 2
Functions
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)
void	R_BoxSurfaces_r (mnode_t node, vec3_t mins, vec3_t maxs, surfaceType_t list, int listsize, int listlength, vec3_t dir)
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)
int	R_MarkFragments (int numPoints, const vec3_t points, const vec3_t projection, int maxPoints, vec3_t pointBuffer, int maxFragments, markFragment_t fragmentBuffer)

tr_marks.c File Reference

Defines

Functions

Define Documentation

Function Documentation