try to eliminate MAX_MAP_PLANES limits
[divverent/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                 ClipWindingEpsilon( w, dp->planes[ i ], dp->planes[ i ][ 3 ], 0.0625f, &front, &back );
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->numVerts = w->numpoints;
630         ds2->verts = safe_malloc( ds2->numVerts * sizeof( *ds2->verts ) );
631         memset( ds2->verts, 0, ds2->numVerts * sizeof( *ds2->verts ) );
632         
633         /* set vertexes */
634         for( i = 0; i < ds2->numVerts; i++ )
635         {
636                 /* get vertex */
637                 dv = &ds2->verts[ i ];
638                 
639                 /* set alpha */
640                 d = DotProduct( w->p[ i ], dp->planes[ 0 ] ) - dp->planes[ 0 ][ 3 ];
641                 d2 = DotProduct( w->p[ i ], dp->planes[ 1 ] ) - dp->planes[ 1 ][ 3 ];
642                 alpha = 255.0f * d2 / (d + d2);
643                 if( alpha > 255 )
644                         alpha = 255;
645                 else if( alpha < 0 )
646                         alpha = 0;
647                 
648                 /* set misc */
649                 VectorSubtract( w->p[ i ], entityOrigin, dv->xyz );
650                 VectorCopy( plane, dv->normal );
651                 dv->st[ 0 ] = DotProduct( dv->xyz, dp->texMat[ 0 ] ) + dp->texMat[ 0 ][ 3 ];
652                 dv->st[ 1 ] = DotProduct( dv->xyz, dp->texMat[ 1 ] ) + dp->texMat[ 1 ][ 3 ];
653                 
654                 /* set color */
655                 for( j = 0; j < MAX_LIGHTMAPS; j++ )
656                 {
657                         dv->color[ j ][ 0 ] = 255;
658                         dv->color[ j ][ 1 ] = 255;
659                         dv->color[ j ][ 2 ] = 255;
660                         dv->color[ j ][ 3 ] = alpha;
661                 }
662         }
663 }
664
665
666
667 /*
668 ProjectDecalOntoFace()
669 projects a decal onto a brushface surface
670 */
671
672 static void ProjectDecalOntoFace( decalProjector_t *dp, mapDrawSurface_t *ds )
673 {
674         vec4_t          plane;
675         float           d;
676         winding_t       *w;
677         
678         
679         /* dummy check */
680         if( ds->sideRef == NULL || ds->sideRef->side == NULL )
681                 return;
682         
683         /* backface check */
684         if( ds->planar )
685         {
686                 VectorCopy( mapplanes[ ds->planeNum ].normal, plane );
687                 plane[ 3 ] = mapplanes[ ds->planeNum ].dist + DotProduct( plane, entityOrigin );
688                 d = DotProduct( dp->planes[ 0 ], plane );
689                 if( d < -0.0001f )
690                         return;
691         }
692         
693         /* generate decal */
694         w = WindingFromDrawSurf( ds );
695         ProjectDecalOntoWinding( dp, ds, w );
696 }
697
698
699
700 /*
701 ProjectDecalOntoPatch()
702 projects a decal onto a patch surface
703 */
704
705 static void ProjectDecalOntoPatch( decalProjector_t *dp, mapDrawSurface_t *ds )
706 {
707         int                     x, y, pw[ 5 ], r, iterations;
708         vec4_t          plane;
709         float           d;
710         mesh_t          src, *mesh, *subdivided;
711         winding_t       *w;
712         
713         
714         /* backface check */
715         if( ds->planar )
716         {
717                 VectorCopy( mapplanes[ ds->planeNum ].normal, plane );
718                 plane[ 3 ] = mapplanes[ ds->planeNum ].dist + DotProduct( plane, entityOrigin );
719                 d = DotProduct( dp->planes[ 0 ], plane );
720                 if( d < -0.0001f )
721                         return;
722         }
723         
724         /* tesselate the patch */
725         src.width = ds->patchWidth;
726         src.height = ds->patchHeight;
727         src.verts = ds->verts;
728         iterations = IterationsForCurve( ds->longestCurve, patchSubdivisions );
729         subdivided = SubdivideMesh2( src, iterations );
730         
731         /* fit it to the curve and remove colinear verts on rows/columns */
732         PutMeshOnCurve( *subdivided );
733         mesh = RemoveLinearMeshColumnsRows( subdivided );
734         FreeMesh( subdivided );
735         
736         /* iterate through the mesh quads */
737         for( y = 0; y < (mesh->height - 1); y++ )
738         {
739                 for( x = 0; x < (mesh->width - 1); x++ )
740                 {
741                         /* set indexes */
742                         pw[ 0 ] = x + (y * mesh->width);
743                         pw[ 1 ] = x + ((y + 1) * mesh->width);
744                         pw[ 2 ] = x + 1 + ((y + 1) * mesh->width);
745                         pw[ 3 ] = x + 1 + (y * mesh->width);
746                         pw[ 4 ] = x + (y * mesh->width);        /* same as pw[ 0 ] */
747                         
748                         /* set radix */
749                         r = (x + y) & 1;
750                         
751                         /* generate decal for first triangle */
752                         w = AllocWinding( 3 );
753                         w->numpoints = 3;
754                         VectorCopy( mesh->verts[ pw[ r + 0 ] ].xyz, w->p[ 0 ] );
755                         VectorCopy( mesh->verts[ pw[ r + 1 ] ].xyz, w->p[ 1 ] );
756                         VectorCopy( mesh->verts[ pw[ r + 2 ] ].xyz, w->p[ 2 ] );
757                         ProjectDecalOntoWinding( dp, ds, w );
758                         
759                         /* generate decal for second triangle */
760                         w = AllocWinding( 3 );
761                         w->numpoints = 3;
762                         VectorCopy( mesh->verts[ pw[ r + 0 ] ].xyz, w->p[ 0 ] );
763                         VectorCopy( mesh->verts[ pw[ r + 2 ] ].xyz, w->p[ 1 ] );
764                         VectorCopy( mesh->verts[ pw[ r + 3 ] ].xyz, w->p[ 2 ] );
765                         ProjectDecalOntoWinding( dp, ds, w );
766                 }
767         }
768         
769         /* clean up */
770         free( mesh );
771 }
772
773
774
775 /*
776 ProjectDecalOntoTriangles()
777 projects a decal onto a triangle surface
778 */
779
780 static void ProjectDecalOntoTriangles( decalProjector_t *dp, mapDrawSurface_t *ds )
781 {
782         int                     i;
783         vec4_t          plane;
784         float           d;
785         winding_t       *w;
786         
787         
788         /* triangle surfaces without shaders don't get marks by default */
789         if( ds->type == SURFACE_TRIANGLES && ds->shaderInfo->shaderText == NULL )
790                 return;
791         
792         /* backface check */
793         if( ds->planar )
794         {
795                 VectorCopy( mapplanes[ ds->planeNum ].normal, plane );
796                 plane[ 3 ] = mapplanes[ ds->planeNum ].dist + DotProduct( plane, entityOrigin );
797                 d = DotProduct( dp->planes[ 0 ], plane );
798                 if( d < -0.0001f )
799                         return;
800         }
801         
802         /* iterate through triangles */
803         for( i = 0; i < ds->numIndexes; i += 3 )
804         {
805                 /* generate decal */
806                 w = AllocWinding( 3 );
807                 w->numpoints = 3;
808                 VectorCopy( ds->verts[ ds->indexes[ i ] ].xyz, w->p[ 0 ] );
809                 VectorCopy( ds->verts[ ds->indexes[ i + 1 ] ].xyz, w->p[ 1 ] );
810                 VectorCopy( ds->verts[ ds->indexes[ i + 2 ] ].xyz, w->p[ 2 ] );
811                 ProjectDecalOntoWinding( dp, ds, w );
812         }
813 }
814
815
816
817 /*
818 MakeEntityDecals()
819 projects decals onto world surfaces
820 */
821
822 void MakeEntityDecals( entity_t *e )
823 {
824         int                                     i, j, k, f, fOld, start;
825         decalProjector_t        dp;
826         mapDrawSurface_t        *ds;
827         vec3_t                          identityAxis[ 3 ] = { { 1, 0, 0 }, { 0, 1, 0 }, { 0, 0, 1 } };
828         
829         
830         /* note it */
831         Sys_FPrintf( SYS_VRB, "--- MakeEntityDecals ---\n" );
832         
833         /* set entity origin */
834         VectorCopy( e->origin, entityOrigin );
835         
836         /* transform projector instead of geometry */
837         VectorClear( entityOrigin );
838         
839         /* init pacifier */
840         fOld = -1;
841         start = I_FloatTime();
842         
843         /* walk the list of decal projectors */
844         for( i = 0; i < numProjectors; i++ )
845         {
846                 /* print pacifier */
847                 f = 10 * i / numProjectors;
848                 if( f != fOld )
849                 {
850                         fOld = f;
851                         Sys_FPrintf( SYS_VRB, "%d...", f );
852                 }
853                 
854                 /* get projector */
855                 TransformDecalProjector( &projectors[ i ], identityAxis, e->origin, &dp );
856                 
857                 /* walk the list of surfaces in the entity */
858                 for( j = e->firstDrawSurf; j < numMapDrawSurfs; j++ )
859                 {
860                         /* get surface */
861                         ds = &mapDrawSurfs[ j ];
862                         if( ds->numVerts <= 0 )
863                                 continue;
864                         
865                         /* ignore autosprite or nomarks */
866                         if( ds->shaderInfo->autosprite || (ds->shaderInfo->compileFlags & C_NOMARKS) )
867                                 continue;
868                         
869                         /* bounds check */
870                         for( k = 0; k < 3; k++ )
871                                 if( ds->mins[ k ] >= (dp.center[ k ] + dp.radius) ||
872                                         ds->maxs[ k ] <= (dp.center[ k ] - dp.radius) )
873                                         break;
874                         if( k < 3 )
875                                 continue;
876                         
877                         /* switch on type */
878                         switch( ds->type )
879                         {
880                                 case SURFACE_FACE:
881                                         ProjectDecalOntoFace( &dp, ds );
882                                         break;
883                                 
884                                 case SURFACE_PATCH:
885                                         ProjectDecalOntoPatch( &dp, ds );
886                                         break;
887                                 
888                                 case SURFACE_TRIANGLES:
889                                 case SURFACE_FORCED_META:
890                                 case SURFACE_META:
891                                         ProjectDecalOntoTriangles( &dp, ds );
892                                         break;
893                                 
894                                 default:
895                                         break;
896                         }
897                 }
898         }
899         
900         /* print time */
901         Sys_FPrintf( SYS_VRB, " (%d)\n", (int) (I_FloatTime() - start) );
902         
903         /* emit some stats */
904         Sys_FPrintf( SYS_VRB, "%9d decal surfaces\n", numDecalSurfaces );
905 }