tools/quake3/q3map2/decals.c

   1 /*
   2 Copyright (C) 1999-2007 id Software, Inc. and contributors.
   3 For a list of contributors, see the accompanying CONTRIBUTORS file.
   4
   5 This file is part of GtkRadiant.
   6
   7 GtkRadiant is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2 of the License, or
  10 (at your option) any later version.
  11
  12 GtkRadiant is distributed in the hope that it will be useful,
  13 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 GtkRadiant; if not, write to the Free Software
  19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  20
  21 ----------------------------------------------------------------------------------
  22
  23 This code has been altered significantly from its original form, to support
  24 several games based on the Quake III Arena engine, in the form of "Q3Map2."
  25
  26 ------------------------------------------------------------------------------- */
  27
  28
  29
  30 /* marker */
  31 #define DECALS_C
  32
  33
  34
  35 /* dependencies */
  36 #include "q3map2.h"
  37
  38
  39
  40 #define MAX_PROJECTORS          1024
  41
  42 typedef struct decalProjector_s
  43 {
  44         shaderInfo_t                    *si;
  45         vec3_t                                  mins, maxs;
  46         vec3_t                                  center;
  47         float                                   radius, radius2;
  48         int                                             numPlanes;      /* either 5 or 6, for quad or triangle projectors */
  49         vec4_t                                  planes[ 6 ];
  50         vec4_t                                  texMat[ 2 ];
  51 }
  52 decalProjector_t;
  53
  54 static int                                      numProjectors = 0;
  55 static decalProjector_t         projectors[ MAX_PROJECTORS ];
  56
  57 static int                                      numDecalSurfaces = 0;
  58
  59 static vec3_t                           entityOrigin;
  60
  61
  62
  63 /*
  64 DVectorNormalize()
  65 normalizes a vector, returns the length, operates using doubles
  66 */
  67
  68 typedef double  dvec_t;
  69 typedef dvec_t  dvec3_t[ 3 ];
  70
  71 dvec_t DVectorNormalize( dvec3_t in, dvec3_t out )
  72 {
  73         dvec_t  len, ilen;
  74
  75
  76         len = (dvec_t) sqrt( in[ 0 ] * in[ 0 ] + in[ 1 ] * in[ 1 ] + in[ 2 ] * in[ 2 ] );
  77         if( len == 0.0 )
  78         {
  79                 VectorClear( out );
  80                 return 0.0;
  81         }
  82
  83         ilen = 1.0 / len;
  84         out[ 0 ] = in[ 0 ] * ilen;
  85         out[ 1 ] = in[ 1 ] * ilen;
  86         out[ 2 ] = in[ 2 ] * ilen;
  87
  88         return len;
  89 }
  90
  91
  92
  93 /*
  94 MakeTextureMatrix()
  95 generates a texture projection matrix for a triangle
  96 returns qfalse if a texture matrix cannot be created
  97 */
  98
  99 #define Vector2Subtract(a,b,c)  ((c)[ 0 ] = (a)[ 0 ] - (b)[ 0 ], (c)[ 1 ] = (a)[ 1 ] - (b)[ 1 ])
 100
 101 static qboolean MakeTextureMatrix( decalProjector_t *dp, vec4_t projection, bspDrawVert_t *a, bspDrawVert_t *b, bspDrawVert_t *c )
 102 {
 103         int                     i, j;
 104         double          bb, s, t, d;
 105         dvec3_t         pa, pb, pc;
 106         dvec3_t         bary, xyz;
 107         dvec3_t         vecs[ 3 ], axis[ 3 ], lengths;
 108
 109
 110         /* project triangle onto plane of projection */
 111         d = DotProduct( a->xyz, projection ) - projection[ 3 ];
 112         VectorMA( a->xyz, -d, projection, pa );
 113         d = DotProduct( b->xyz, projection ) - projection[ 3 ];
 114         VectorMA( b->xyz, -d, projection, pb );
 115         d = DotProduct( c->xyz, projection ) - projection[ 3 ];
 116         VectorMA( c->xyz, -d, projection, pc );
 117
 118         /* two methods */
 119         #if 1
 120         {
 121                 /* old code */
 122
 123                 /* calculate barycentric basis for the triangle */
 124                 bb = (b->st[ 0 ] - a->st[ 0 ]) * (c->st[ 1 ] - a->st[ 1 ]) - (c->st[ 0 ] - a->st[ 0 ]) * (b->st[ 1 ] - a->st[ 1 ]);
 125                 if( fabs( bb ) < 0.00000001 )
 126                         return qfalse;
 127
 128                 /* calculate texture origin */
 129                 #if 0
 130                 s = 0.0;
 131                 t = 0.0;
 132                 bary[ 0 ] = ((b->st[ 0 ] - s) * (c->st[ 1 ] - t) - (c->st[ 0 ] - s) * (b->st[ 1 ] - t)) / bb;
 133                 bary[ 1 ] = ((c->st[ 0 ] - s) * (a->st[ 1 ] - t) - (a->st[ 0 ] - s) * (c->st[ 1 ] - t)) / bb;
 134                 bary[ 2 ] = ((a->st[ 0 ] - s) * (b->st[ 1 ] - t) - (b->st[ 0 ] - s) * (a->st[ 1 ] - t)) / bb;
 135
 136                 origin[ 0 ] = bary[ 0 ] * pa[ 0 ] + bary[ 1 ] * pb[ 0 ] + bary[ 2 ] * pc[ 0 ];
 137                 origin[ 1 ] = bary[ 0 ] * pa[ 1 ] + bary[ 1 ] * pb[ 1 ] + bary[ 2 ] * pc[ 1 ];
 138                 origin[ 2 ] = bary[ 0 ] * pa[ 2 ] + bary[ 1 ] * pb[ 2 ] + bary[ 2 ] * pc[ 2 ];
 139                 #endif
 140
 141                 /* calculate s vector */
 142                 s = a->st[ 0 ] + 1.0;
 143                 t = a->st[ 1 ] + 0.0;
 144                 bary[ 0 ] = ((b->st[ 0 ] - s) * (c->st[ 1 ] - t) - (c->st[ 0 ] - s) * (b->st[ 1 ] - t)) / bb;
 145                 bary[ 1 ] = ((c->st[ 0 ] - s) * (a->st[ 1 ] - t) - (a->st[ 0 ] - s) * (c->st[ 1 ] - t)) / bb;
 146                 bary[ 2 ] = ((a->st[ 0 ] - s) * (b->st[ 1 ] - t) - (b->st[ 0 ] - s) * (a->st[ 1 ] - t)) / bb;
 147
 148                 xyz[ 0 ] = bary[ 0 ] * pa[ 0 ] + bary[ 1 ] * pb[ 0 ] + bary[ 2 ] * pc[ 0 ];
 149                 xyz[ 1 ] = bary[ 0 ] * pa[ 1 ] + bary[ 1 ] * pb[ 1 ] + bary[ 2 ] * pc[ 1 ];
 150                 xyz[ 2 ] = bary[ 0 ] * pa[ 2 ] + bary[ 1 ] * pb[ 2 ] + bary[ 2 ] * pc[ 2 ];
 151
 152                 //%     VectorSubtract( xyz, origin, vecs[ 0 ] );
 153                 VectorSubtract( xyz, pa, vecs[ 0 ] );
 154
 155                 /* calculate t vector */
 156                 s = a->st[ 0 ] + 0.0;
 157                 t = a->st[ 1 ] + 1.0;
 158                 bary[ 0 ] = ((b->st[ 0 ] - s) * (c->st[ 1 ] - t) - (c->st[ 0 ] - s) * (b->st[ 1 ] - t)) / bb;
 159                 bary[ 1 ] = ((c->st[ 0 ] - s) * (a->st[ 1 ] - t) - (a->st[ 0 ] - s) * (c->st[ 1 ] - t)) / bb;
 160                 bary[ 2 ] = ((a->st[ 0 ] - s) * (b->st[ 1 ] - t) - (b->st[ 0 ] - s) * (a->st[ 1 ] - t)) / bb;
 161
 162                 xyz[ 0 ] = bary[ 0 ] * pa[ 0 ] + bary[ 1 ] * pb[ 0 ] + bary[ 2 ] * pc[ 0 ];
 163                 xyz[ 1 ] = bary[ 0 ] * pa[ 1 ] + bary[ 1 ] * pb[ 1 ] + bary[ 2 ] * pc[ 1 ];
 164                 xyz[ 2 ] = bary[ 0 ] * pa[ 2 ] + bary[ 1 ] * pb[ 2 ] + bary[ 2 ] * pc[ 2 ];
 165
 166                 //%     VectorSubtract( xyz, origin, vecs[ 1 ] );
 167                 VectorSubtract( xyz, pa, vecs[ 1 ] );
 168
 169                 /* calcuate r vector */
 170                 VectorScale( projection, -1.0, vecs[ 2 ] );
 171
 172                 /* calculate transform axis */
 173                 for( i = 0; i < 3; i++ )
 174                         lengths[ i ] = DVectorNormalize( vecs[ i ], axis[ i ] );
 175                 for( i = 0; i < 2; i++ )
 176                         for( j = 0; j < 3; j++ )
 177                                 dp->texMat[ i ][ j ] = lengths[ i ] > 0.0 ? (axis[ i ][ j ] / lengths[ i ]) : 0.0;
 178                                 //%     dp->texMat[ i ][ j ] = fabs( vecs[ i ][ j ] ) > 0.0 ? (1.0 / vecs[ i ][ j ]) : 0.0;
 179                                 //%     dp->texMat[ i ][ j ] = axis[ i ][ j ] > 0.0 ? (1.0 / axis[ i ][ j ]) : 0.0;
 180
 181                 /* calculalate translation component */
 182                 dp->texMat[ 0 ][ 3 ] = a->st[ 0 ] - DotProduct( a->xyz, dp->texMat[ 0 ] );
 183                 dp->texMat[ 1 ][ 3 ] = a->st[ 1 ] - DotProduct( a->xyz, dp->texMat[ 1 ] );
 184         }
 185         #else
 186         {
 187                 int                     k;
 188                 dvec3_t         origin, deltas[ 3 ];
 189                 double          texDeltas[ 3 ][ 2 ];
 190                 double          delta, texDelta;
 191
 192
 193                 /* new code */
 194
 195                 /* calculate deltas */
 196                 VectorSubtract( pa, pb, deltas[ 0 ] );
 197                 VectorSubtract( pa, pc, deltas[ 1 ] );
 198                 VectorSubtract( pb, pc, deltas[ 2 ] );
 199                 Vector2Subtract( a->st, b->st, texDeltas[ 0 ] );
 200                 Vector2Subtract( a->st, c->st, texDeltas[ 1 ] );
 201                 Vector2Subtract( b->st, c->st, texDeltas[ 2 ] );
 202
 203                 /* walk st */
 204                 for( i = 0; i < 2; i++ )
 205                 {
 206                         /* walk xyz */
 207                         for( j = 0; j < 3; j++ )
 208                         {
 209                                 /* clear deltas */
 210                                 delta = 0.0;
 211                                 texDelta = 0.0;
 212
 213                                 /* walk deltas */
 214                                 for( k = 0; k < 3; k++ )
 215                                 {
 216                                         if( fabs( deltas[ k ][ j ] ) > delta &&
 217                                                 fabs( texDeltas[ k ][ i ] ) > texDelta  )
 218                                         {
 219                                                 delta = deltas[ k ][ j ];
 220                                                 texDelta = texDeltas[ k ][ i ];
 221                                         }
 222                                 }
 223
 224                                 /* set texture matrix component */
 225                                 if( fabs( delta ) > 0.0 )
 226                                         dp->texMat[ i ][ j ] = texDelta / delta;
 227                                 else
 228                                         dp->texMat[ i ][ j ] = 0.0;
 229                         }
 230
 231                         /* set translation component */
 232                         dp->texMat[ i ][ 3 ] = a->st[ i ] - DotProduct( pa, dp->texMat[ i ] );
 233                 }
 234         }
 235         #endif
 236
 237         /* debug code */
 238         #if 1
 239                 Sys_Printf( "Mat: [ %f %f %f %f ] [ %f %f %f %f ] Theta: %f (%f)\n",
 240                         dp->texMat[ 0 ][ 0 ], dp->texMat[ 0 ][ 1 ], dp->texMat[ 0 ][ 2 ], dp->texMat[ 0 ][ 3 ],
 241                         dp->texMat[ 1 ][ 0 ], dp->texMat[ 1 ][ 1 ], dp->texMat[ 1 ][ 2 ], dp->texMat[ 1 ][ 3 ],
 242                         RAD2DEG( acos( DotProduct( dp->texMat[ 0 ], dp->texMat[ 1 ] ) ) ),
 243                         RAD2DEG( acos( DotProduct( axis[ 0 ], axis[ 1 ] ) ) ) );
 244
 245                 Sys_Printf( "XYZ: %f %f %f ST: %f %f ST(t): %f %f\n",
 246                         a->xyz[ 0 ], a->xyz[ 1 ], a->xyz[ 2 ],
 247                         a->st[ 0 ], a->st[ 1 ],
 248                         DotProduct( a->xyz, dp->texMat[ 0 ] ) + dp->texMat[ 0 ][ 3 ], DotProduct( a->xyz, dp->texMat[ 1 ] ) + dp->texMat[ 1 ][ 3 ] );
 249         #endif
 250
 251         /* test texture matrix */
 252         s = DotProduct( a->xyz, dp->texMat[ 0 ] ) + dp->texMat[ 0 ][ 3 ];
 253         t = DotProduct( a->xyz, dp->texMat[ 1 ] ) + dp->texMat[ 1 ][ 3 ];
 254         if( fabs( s - a->st[ 0 ] ) > 0.01 || fabs( t - a->st[ 1 ] ) > 0.01 )
 255         {
 256                 Sys_Printf( "Bad texture matrix! (A) (%f, %f) != (%f, %f)\n",
 257                         s, t, a->st[ 0 ], a->st[ 1 ] );
 258                 //%     return qfalse;
 259         }
 260         s = DotProduct( b->xyz, dp->texMat[ 0 ] ) + dp->texMat[ 0 ][ 3 ];
 261         t = DotProduct( b->xyz, dp->texMat[ 1 ] ) + dp->texMat[ 1 ][ 3 ];
 262         if( fabs( s - b->st[ 0 ] ) > 0.01 || fabs( t - b->st[ 1 ] ) > 0.01 )
 263         {
 264                 Sys_Printf( "Bad texture matrix! (B) (%f, %f) != (%f, %f)\n",
 265                         s, t, b->st[ 0 ], b->st[ 1 ] );
 266                 //%     return qfalse;
 267         }
 268         s = DotProduct( c->xyz, dp->texMat[ 0 ] ) + dp->texMat[ 0 ][ 3 ];
 269         t = DotProduct( c->xyz, dp->texMat[ 1 ] ) + dp->texMat[ 1 ][ 3 ];
 270         if( fabs( s - c->st[ 0 ] ) > 0.01 || fabs( t - c->st[ 1 ] ) > 0.01 )
 271         {
 272                 Sys_Printf( "Bad texture matrix! (C) (%f, %f) != (%f, %f)\n",
 273                         s, t, c->st[ 0 ], c->st[ 1 ] );
 274                 //%     return qfalse;
 275         }
 276
 277         /* disco */
 278         return qtrue;
 279 }
 280
 281
 282
 283 /*
 284 TransformDecalProjector()
 285 transforms a decal projector
 286 note: non-normalized axes will screw up the plane transform
 287 */
 288
 289 static void TransformDecalProjector( decalProjector_t *in, vec3_t axis[ 3 ], vec3_t origin, decalProjector_t *out )
 290 {
 291         int             i;
 292
 293
 294         /* copy misc stuff */
 295         out->si = in->si;
 296         out->numPlanes = in->numPlanes;
 297
 298         /* translate bounding box and sphere (note: rotated projector bounding box will be invalid!) */
 299         VectorSubtract( in->mins, origin, out->mins );
 300         VectorSubtract( in->maxs, origin, out->maxs );
 301         VectorSubtract( in->center, origin, out->center );
 302         out->radius = in->radius;
 303         out->radius2 = in->radius2;
 304
 305         /* translate planes */
 306         for( i = 0; i < in->numPlanes; i++ )
 307         {
 308                 out->planes[ i ][ 0 ] = DotProduct( in->planes[ i ], axis[ 0 ] );
 309                 out->planes[ i ][ 1 ] = DotProduct( in->planes[ i ], axis[ 1 ] );
 310                 out->planes[ i ][ 2 ] = DotProduct( in->planes[ i ], axis[ 2 ] );
 311                 out->planes[ i ][ 3 ] = in->planes[ i ][ 3 ] - DotProduct( out->planes[ i ], origin );
 312         }
 313
 314         /* translate texture matrix */
 315         for( i = 0; i < 2; i++ )
 316         {
 317                 out->texMat[ i ][ 0 ] = DotProduct( in->texMat[ i ], axis[ 0 ] );
 318                 out->texMat[ i ][ 1 ] = DotProduct( in->texMat[ i ], axis[ 1 ] );
 319                 out->texMat[ i ][ 2 ] = DotProduct( in->texMat[ i ], axis[ 2 ] );
 320                 out->texMat[ i ][ 3 ] = in->texMat[ i ][ 3 ] + DotProduct( out->texMat[ i ], origin );
 321         }
 322 }
 323
 324
 325
 326 /*
 327 MakeDecalProjector()
 328 creates a new decal projector from a triangle
 329 */
 330
 331 static int MakeDecalProjector( shaderInfo_t *si, vec4_t projection, float distance, int numVerts, bspDrawVert_t **dv )
 332 {
 333         int                                     i, j;
 334         decalProjector_t        *dp;
 335         vec3_t                          xyz;
 336
 337
 338         /* dummy check */
 339         if( numVerts != 3 && numVerts != 4 )
 340                 return -1;
 341
 342         /* limit check */
 343         if( numProjectors >= MAX_PROJECTORS )
 344         {
 345                 Sys_Printf( "WARNING: MAX_PROJECTORS (%d) exceeded, no more decal projectors available.\n", MAX_PROJECTORS );
 346                 return -2;
 347         }
 348
 349         /* create a new projector */
 350         dp = &projectors[ numProjectors ];
 351         memset( dp, 0, sizeof( *dp ) );
 352
 353         /* basic setup */
 354         dp->si = si;
 355         dp->numPlanes = numVerts + 2;
 356
 357         /* make texture matrix */
 358         if( !MakeTextureMatrix( dp, projection, dv[ 0 ], dv[ 1 ], dv[ 2 ] ) )
 359                 return -1;
 360
 361         /* bound the projector */
 362         ClearBounds( dp->mins, dp->maxs );
 363         for( i = 0; i < numVerts; i++ )
 364         {
 365                 AddPointToBounds( dv[ i ]->xyz, dp->mins, dp->maxs );
 366                 VectorMA( dv[ i ]->xyz, distance, projection, xyz );
 367                 AddPointToBounds( xyz, dp->mins, dp->maxs );
 368         }
 369
 370         /* make bouding sphere */
 371         VectorAdd( dp->mins, dp->maxs, dp->center );
 372         VectorScale( dp->center, 0.5f, dp->center );
 373         VectorSubtract( dp->maxs, dp->center, xyz );
 374         dp->radius = VectorLength( xyz );
 375         dp->radius2 = dp->radius * dp->radius;
 376
 377         /* make the front plane */
 378         if( !PlaneFromPoints( dp->planes[ 0 ], dv[ 0 ]->xyz, dv[ 1 ]->xyz, dv[ 2 ]->xyz ) )
 379                 return -1;
 380
 381         /* make the back plane */
 382         VectorSubtract( vec3_origin, dp->planes[ 0 ], dp->planes[ 1 ] );
 383         VectorMA( dv[ 0 ]->xyz, distance, projection, xyz );
 384         dp->planes[ 1 ][ 3 ] = DotProduct( xyz, dp->planes[ 1 ] );
 385
 386         /* make the side planes */
 387         for( i = 0; i < numVerts; i++ )
 388         {
 389                 j = (i + 1) % numVerts;
 390                 VectorMA( dv[ i ]->xyz, distance, projection, xyz );
 391                 if( !PlaneFromPoints( dp->planes[ i + 2 ], dv[ j ]->xyz, dv[ i ]->xyz, xyz ) )
 392                         return -1;
 393         }
 394
 395         /* return ok */
 396         numProjectors++;
 397         return numProjectors - 1;
 398 }
 399
 400
 401
 402 /*
 403 ProcessDecals()
 404 finds all decal entities and creates decal projectors
 405 */
 406
 407 #define PLANAR_EPSILON  0.5f
 408
 409 void ProcessDecals( void )
 410 {
 411         int                                     i, j, x, y, pw[ 5 ], r, iterations;
 412         float                           distance;
 413         vec4_t                          projection, plane;
 414         vec3_t                          origin, target, delta;
 415         entity_t                        *e, *e2;
 416         parseMesh_t                     *p;
 417         mesh_t                          *mesh, *subdivided;
 418         bspDrawVert_t           *dv[ 4 ];
 419         const char                      *value;
 420
 421
 422         /* note it */
 423         Sys_FPrintf( SYS_VRB, "--- ProcessDecals ---\n" );
 424
 425         /* walk entity list */
 426         for( i = 0; i < numEntities; i++ )
 427         {
 428                 /* get entity */
 429                 e = &entities[ i ];
 430                 value = ValueForKey( e, "classname" );
 431                 if( Q_stricmp( value, "_decal" ) )
 432                         continue;
 433
 434                 /* any patches? */
 435                 if( e->patches == NULL )
 436                 {
 437                         Sys_Printf( "WARNING: Decal entity without any patch meshes, ignoring.\n" );
 438                         e->epairs = NULL;       /* fixme: leak! */
 439                         continue;
 440                 }
 441
 442                 /* find target */
 443                 value = ValueForKey( e, "target" );
 444                 e2 = FindTargetEntity( value );
 445
 446                 /* no target? */
 447                 if( e2 == NULL )
 448                 {
 449                         Sys_Printf( "WARNING: Decal entity without a valid target, ignoring.\n" );
 450                         continue;
 451                 }
 452
 453                 /* walk entity patches */
 454                 for( p = e->patches; p != NULL; p = e->patches )
 455                 {
 456                         /* setup projector */
 457                         if( VectorCompare( e->origin, vec3_origin ) )
 458                         {
 459                                 VectorAdd( p->eMins, p->eMaxs, origin );
 460                                 VectorScale( origin, 0.5f, origin );
 461                         }
 462                         else
 463                                 VectorCopy( e->origin, origin );
 464
 465                         VectorCopy( e2->origin, target );
 466                         VectorSubtract( target, origin, delta );
 467
 468                         /* setup projection plane */
 469                         distance = VectorNormalize( delta, projection );
 470                         projection[ 3 ] = DotProduct( origin, projection );
 471
 472                         /* create projectors */
 473                         if( distance > 0.125f )
 474                         {
 475                                 /* tesselate the patch */
 476                                 iterations = IterationsForCurve( p->longestCurve, patchSubdivisions );
 477                                 subdivided = SubdivideMesh2( p->mesh, iterations );
 478
 479                                 /* fit it to the curve and remove colinear verts on rows/columns */
 480                                 PutMeshOnCurve( *subdivided );
 481                                 mesh = RemoveLinearMeshColumnsRows( subdivided );
 482                                 FreeMesh( subdivided );
 483
 484                                 /* offset by projector origin */
 485                                 for( j = 0; j < (mesh->width * mesh->height); j++ )
 486                                         VectorAdd( mesh->verts[ j ].xyz, e->origin, mesh->verts[ j ].xyz );
 487
 488                                 /* iterate through the mesh quads */
 489                                 for( y = 0; y < (mesh->height - 1); y++ )
 490                                 {
 491                                         for( x = 0; x < (mesh->width - 1); x++ )
 492                                         {
 493                                                 /* set indexes */
 494                                                 pw[ 0 ] = x + (y * mesh->width);
 495                                                 pw[ 1 ] = x + ((y + 1) * mesh->width);
 496                                                 pw[ 2 ] = x + 1 + ((y + 1) * mesh->width);
 497                                                 pw[ 3 ] = x + 1 + (y * mesh->width);
 498                                                 pw[ 4 ] = x + (y * mesh->width);        /* same as pw[ 0 ] */
 499
 500                                                 /* set radix */
 501                                                 r = (x + y) & 1;
 502
 503                                                 /* get drawverts */
 504                                                 dv[ 0 ] = &mesh->verts[ pw[ r + 0 ] ];
 505                                                 dv[ 1 ] = &mesh->verts[ pw[ r + 1 ] ];
 506                                                 dv[ 2 ] = &mesh->verts[ pw[ r + 2 ] ];
 507                                                 dv[ 3 ] = &mesh->verts[ pw[ r + 3 ] ];
 508
 509                                                 /* planar? (nuking this optimization as it doesn't work on non-rectangular quads) */
 510                                                 plane[ 0 ] = 0.0f;      /* stupid msvc */
 511                                                 if( 0 && PlaneFromPoints( plane, dv[ 0 ]->xyz, dv[ 1 ]->xyz, dv[ 2 ]->xyz ) &&
 512                                                         fabs( DotProduct( dv[ 1 ]->xyz, plane ) - plane[ 3 ] ) <= PLANAR_EPSILON )
 513                                                 {
 514                                                         /* make a quad projector */
 515                                                         MakeDecalProjector( p->shaderInfo, projection, distance, 4, dv );
 516                                                 }
 517                                                 else
 518                                                 {
 519                                                         /* make first triangle */
 520                                                         MakeDecalProjector( p->shaderInfo, projection, distance, 3, dv );
 521
 522                                                         /* make second triangle */
 523                                                         dv[ 1 ] = dv[ 2 ];
 524                                                         dv[ 2 ] = dv[ 3 ];
 525                                                         MakeDecalProjector( p->shaderInfo, projection, distance, 3, dv );
 526                                                 }
 527                                         }
 528                                 }
 529
 530                                 /* clean up */
 531                                 free( mesh );
 532                         }
 533
 534                         /* remove patch from entity (fixme: leak!) */
 535                         e->patches = p->next;
 536
 537                         /* push patch to worldspawn (enable this to debug projectors) */
 538                         #if 0
 539                                 p->next = entities[ 0 ].patches;
 540                                 entities[ 0 ].patches = p;
 541                         #endif
 542                 }
 543         }
 544
 545         /* emit some stats */
 546         Sys_FPrintf( SYS_VRB, "%9d decal projectors\n", numProjectors );
 547 }
 548
 549
 550
 551 /*
 552 ProjectDecalOntoWinding()
 553 projects a decal onto a winding
 554 */
 555
 556 static void ProjectDecalOntoWinding( decalProjector_t *dp, mapDrawSurface_t *ds, winding_t *w )
 557 {
 558         int                                     i, j;
 559         float                           d, d2, alpha;
 560         winding_t                       *front, *back;
 561         mapDrawSurface_t        *ds2;
 562         bspDrawVert_t           *dv;
 563         vec4_t                          plane;
 564
 565
 566         /* dummy check */
 567         if( w->numpoints < 3 )
 568         {
 569                 FreeWinding( w );
 570                 return;
 571         }
 572
 573         /* offset by entity origin */
 574         for( i = 0; i < w->numpoints; i++ )
 575                 VectorAdd( w->p[ i ], entityOrigin, w->p[ i ] );
 576
 577         /* make a plane from the winding */
 578         if( !PlaneFromPoints( plane, w->p[ 0 ], w->p[ 1 ], w->p[ 2 ] ) )
 579         {
 580                 FreeWinding( w );
 581                 return;
 582         }
 583
 584         /* backface check */
 585         d = DotProduct( dp->planes[ 0 ], plane );
 586         if( d < -0.0001f )
 587         {
 588                 FreeWinding( w );
 589                 return;
 590         }
 591
 592         /* walk list of planes */
 593         for( i = 0; i < dp->numPlanes; i++ )
 594         {
 595                 /* chop winding by the plane */
 596                 ClipWindingEpsilon( w, dp->planes[ i ], dp->planes[ i ][ 3 ], 0.0625f, &front, &back );
 597                 FreeWinding( w );
 598
 599                 /* lose the front fragment */
 600                 if( front != NULL )
 601                         FreeWinding( front );
 602
 603                 /* if nothing left in back, then bail */
 604                 if( back == NULL )
 605                         return;
 606
 607                 /* reset winding */
 608                 w = back;
 609         }
 610
 611         /* nothing left? */
 612         if( w == NULL || w->numpoints < 3 )
 613                 return;
 614
 615         /* add to counts */
 616         numDecalSurfaces++;
 617
 618         /* make a new surface */
 619         ds2 = AllocDrawSurface( SURFACE_DECAL );
 620
 621         /* set it up */
 622         ds2->entityNum = ds->entityNum;
 623         ds2->castShadows = ds->castShadows;
 624         ds2->recvShadows = ds->recvShadows;
 625         ds2->shaderInfo = dp->si;
 626         ds2->fogNum = ds->fogNum;       /* why was this -1? */
 627         ds2->lightmapScale = ds->lightmapScale;
 628         ds2->numVerts = w->numpoints;
 629         ds2->verts = safe_malloc( ds2->numVerts * sizeof( *ds2->verts ) );
 630         memset( ds2->verts, 0, ds2->numVerts * sizeof( *ds2->verts ) );
 631
 632         /* set vertexes */
 633         for( i = 0; i < ds2->numVerts; i++ )
 634         {
 635                 /* get vertex */
 636                 dv = &ds2->verts[ i ];
 637
 638                 /* set alpha */
 639                 d = DotProduct( w->p[ i ], dp->planes[ 0 ] ) - dp->planes[ 0 ][ 3 ];
 640                 d2 = DotProduct( w->p[ i ], dp->planes[ 1 ] ) - dp->planes[ 1 ][ 3 ];
 641                 alpha = 255.0f * d2 / (d + d2);
 642                 if( alpha > 255 )
 643                         alpha = 255;
 644                 else if( alpha < 0 )
 645                         alpha = 0;
 646
 647                 /* set misc */
 648                 VectorSubtract( w->p[ i ], entityOrigin, dv->xyz );
 649                 VectorCopy( plane, dv->normal );
 650                 dv->st[ 0 ] = DotProduct( dv->xyz, dp->texMat[ 0 ] ) + dp->texMat[ 0 ][ 3 ];
 651                 dv->st[ 1 ] = DotProduct( dv->xyz, dp->texMat[ 1 ] ) + dp->texMat[ 1 ][ 3 ];
 652
 653                 /* set color */
 654                 for( j = 0; j < MAX_LIGHTMAPS; j++ )
 655                 {
 656                         dv->color[ j ][ 0 ] = 255;
 657                         dv->color[ j ][ 1 ] = 255;
 658                         dv->color[ j ][ 2 ] = 255;
 659                         dv->color[ j ][ 3 ] = alpha;
 660                 }
 661         }
 662
 663         /* ydnar: finish the surface */
 664         FinishSurface( ds2 );
 665 }
 666
 667
 668
 669 /*
 670 ProjectDecalOntoFace()
 671 projects a decal onto a brushface surface
 672 */
 673
 674 static void ProjectDecalOntoFace( decalProjector_t *dp, mapDrawSurface_t *ds )
 675 {
 676         vec4_t          plane;
 677         float           d;
 678         winding_t       *w;
 679
 680
 681         /* dummy check */
 682         if( ds->sideRef == NULL || ds->sideRef->side == NULL )
 683                 return;
 684
 685         /* backface check */
 686         if( ds->planar )
 687         {
 688                 VectorCopy( mapplanes[ ds->planeNum ].normal, plane );
 689                 plane[ 3 ] = mapplanes[ ds->planeNum ].dist + DotProduct( plane, entityOrigin );
 690                 d = DotProduct( dp->planes[ 0 ], plane );
 691                 if( d < -0.0001f )
 692                         return;
 693         }
 694
 695         /* generate decal */
 696         w = WindingFromDrawSurf( ds );
 697         ProjectDecalOntoWinding( dp, ds, w );
 698 }
 699
 700
 701
 702 /*
 703 ProjectDecalOntoPatch()
 704 projects a decal onto a patch surface
 705 */
 706
 707 static void ProjectDecalOntoPatch( decalProjector_t *dp, mapDrawSurface_t *ds )
 708 {
 709         int                     x, y, pw[ 5 ], r, iterations;
 710         vec4_t          plane;
 711         float           d;
 712         mesh_t          src, *mesh, *subdivided;
 713         winding_t       *w;
 714
 715
 716         /* backface check */
 717         if( ds->planar )
 718         {
 719                 VectorCopy( mapplanes[ ds->planeNum ].normal, plane );
 720                 plane[ 3 ] = mapplanes[ ds->planeNum ].dist + DotProduct( plane, entityOrigin );
 721                 d = DotProduct( dp->planes[ 0 ], plane );
 722                 if( d < -0.0001f )
 723                         return;
 724         }
 725
 726         /* tesselate the patch */
 727         src.width = ds->patchWidth;
 728         src.height = ds->patchHeight;
 729         src.verts = ds->verts;
 730         iterations = IterationsForCurve( ds->longestCurve, patchSubdivisions );
 731         subdivided = SubdivideMesh2( src, iterations );
 732
 733         /* fit it to the curve and remove colinear verts on rows/columns */
 734         PutMeshOnCurve( *subdivided );
 735         mesh = RemoveLinearMeshColumnsRows( subdivided );
 736         FreeMesh( subdivided );
 737
 738         /* iterate through the mesh quads */
 739         for( y = 0; y < (mesh->height - 1); y++ )
 740         {
 741                 for( x = 0; x < (mesh->width - 1); x++ )
 742                 {
 743                         /* set indexes */
 744                         pw[ 0 ] = x + (y * mesh->width);
 745                         pw[ 1 ] = x + ((y + 1) * mesh->width);
 746                         pw[ 2 ] = x + 1 + ((y + 1) * mesh->width);
 747                         pw[ 3 ] = x + 1 + (y * mesh->width);
 748                         pw[ 4 ] = x + (y * mesh->width);        /* same as pw[ 0 ] */
 749
 750                         /* set radix */
 751                         r = (x + y) & 1;
 752
 753                         /* generate decal for first triangle */
 754                         w = AllocWinding( 3 );
 755                         w->numpoints = 3;
 756                         VectorCopy( mesh->verts[ pw[ r + 0 ] ].xyz, w->p[ 0 ] );
 757                         VectorCopy( mesh->verts[ pw[ r + 1 ] ].xyz, w->p[ 1 ] );
 758                         VectorCopy( mesh->verts[ pw[ r + 2 ] ].xyz, w->p[ 2 ] );
 759                         ProjectDecalOntoWinding( dp, ds, w );
 760
 761                         /* generate decal for second triangle */
 762                         w = AllocWinding( 3 );
 763                         w->numpoints = 3;
 764                         VectorCopy( mesh->verts[ pw[ r + 0 ] ].xyz, w->p[ 0 ] );
 765                         VectorCopy( mesh->verts[ pw[ r + 2 ] ].xyz, w->p[ 1 ] );
 766                         VectorCopy( mesh->verts[ pw[ r + 3 ] ].xyz, w->p[ 2 ] );
 767                         ProjectDecalOntoWinding( dp, ds, w );
 768                 }
 769         }
 770
 771         /* clean up */
 772         free( mesh );
 773 }
 774
 775
 776
 777 /*
 778 ProjectDecalOntoTriangles()
 779 projects a decal onto a triangle surface
 780 */
 781
 782 static void ProjectDecalOntoTriangles( decalProjector_t *dp, mapDrawSurface_t *ds )
 783 {
 784         int                     i;
 785         vec4_t          plane;
 786         float           d;
 787         winding_t       *w;
 788
 789
 790         /* triangle surfaces without shaders don't get marks by default */
 791         if( (ds->type == SURFACE_TRIANGLES || ds->type == SURFACE_FORCED_META) &&
 792                 ds->shaderInfo->shaderText == NULL )
 793                 return;
 794
 795         /* backface check */
 796         if( ds->planar )
 797         {
 798                 VectorCopy( mapplanes[ ds->planeNum ].normal, plane );
 799                 plane[ 3 ] = mapplanes[ ds->planeNum ].dist + DotProduct( plane, entityOrigin );
 800                 d = DotProduct( dp->planes[ 0 ], plane );
 801                 if( d < -0.0001f )
 802                         return;
 803         }
 804
 805         /* iterate through triangles */
 806         for( i = 0; i < ds->numIndexes; i += 3 )
 807         {
 808                 /* generate decal */
 809                 w = AllocWinding( 3 );
 810                 w->numpoints = 3;
 811                 VectorCopy( ds->verts[ ds->indexes[ i ] ].xyz, w->p[ 0 ] );
 812                 VectorCopy( ds->verts[ ds->indexes[ i + 1 ] ].xyz, w->p[ 1 ] );
 813                 VectorCopy( ds->verts[ ds->indexes[ i + 2 ] ].xyz, w->p[ 2 ] );
 814                 ProjectDecalOntoWinding( dp, ds, w );
 815         }
 816 }
 817
 818
 819
 820 /*
 821 MakeEntityDecals()
 822 projects decals onto world surfaces
 823 */
 824
 825 void MakeEntityDecals( entity_t *e )
 826 {
 827         int                                     i, j, k, f, fOld, start;
 828         decalProjector_t        dp;
 829         mapDrawSurface_t        *ds;
 830         vec3_t                          identityAxis[ 3 ] = { { 1, 0, 0 }, { 0, 1, 0 }, { 0, 0, 1 } };
 831
 832
 833         /* note it */
 834         Sys_FPrintf( SYS_VRB, "--- MakeEntityDecals ---\n" );
 835
 836         /* set entity origin */
 837         VectorCopy( e->origin, entityOrigin );
 838
 839         /* transform projector instead of geometry */
 840         VectorClear( entityOrigin );
 841
 842         /* init pacifier */
 843         fOld = -1;
 844         start = I_FloatTime();
 845
 846         /* walk the list of decal projectors */
 847         for( i = 0; i < numProjectors; i++ )
 848         {
 849                 /* print pacifier */
 850                 f = 10 * i / numProjectors;
 851                 if( f != fOld )
 852                 {
 853                         fOld = f;
 854                         Sys_FPrintf( SYS_VRB, "%d...", f );
 855                 }
 856
 857                 /* get projector */
 858                 TransformDecalProjector( &projectors[ i ], identityAxis, e->origin, &dp );
 859
 860                 /* walk the list of surfaces in the entity */
 861                 for( j = e->firstDrawSurf; j < numMapDrawSurfs; j++ )
 862                 {
 863                         /* get surface */
 864                         ds = &mapDrawSurfs[ j ];
 865                         if( ds->numVerts <= 0 )
 866                                 continue;
 867
 868                         /* ignore autosprite or nomarks */
 869                         if( ds->shaderInfo->autosprite || (ds->shaderInfo->compileFlags & C_NOMARKS) )
 870                                 continue;
 871
 872                         /* bounds check */
 873                         for( k = 0; k < 3; k++ )
 874                                 if( ds->mins[ k ] >= (dp.center[ k ] + dp.radius) ||
 875                                         ds->maxs[ k ] <= (dp.center[ k ] - dp.radius) )
 876                                         break;
 877                         if( k < 3 )
 878                                 continue;
 879
 880                         /* switch on type */
 881                         switch( ds->type )
 882                         {
 883                                 case SURFACE_FACE:
 884                                         ProjectDecalOntoFace( &dp, ds );
 885                                         break;
 886
 887                                 case SURFACE_PATCH:
 888                                         ProjectDecalOntoPatch( &dp, ds );
 889                                         break;
 890
 891                                 case SURFACE_TRIANGLES:
 892                                 case SURFACE_FORCED_META:
 893                                 case SURFACE_META:
 894                                         ProjectDecalOntoTriangles( &dp, ds );
 895                                         break;
 896
 897                                 default:
 898                                         break;
 899                         }
 900                 }
 901         }
 902
 903         /* print time */
 904         Sys_FPrintf( SYS_VRB, " (%d)\n", (int) (I_FloatTime() - start) );
 905
 906         /* emit some stats */
 907         Sys_FPrintf( SYS_VRB, "%9d decal surfaces\n", numDecalSurfaces );
 908 }