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