86421b95bc387a4464424fb9759d90f34eaa1402
[xonotic/netradiant.git] / 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 }