tools/quake3/q3map2/decals.c

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