8e79244e542dbebed1661275af89e0f52ca07397
[divverent/netradiant.git] / tools / quake3 / q3map2 / light_trace.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 LIGHT_TRACE_C
33
34
35
36 /* dependencies */
37 #include "q3map2.h"
38
39
40 /* dependencies */
41 #include "q3map2.h"
42
43
44
45 #define Vector2Copy( a, b )             ((b)[ 0 ] = (a)[ 0 ], (b)[ 1 ] = (a)[ 1 ])
46 #define Vector4Copy( a, b )             ((b)[ 0 ] = (a)[ 0 ], (b)[ 1 ] = (a)[ 1 ], (b)[ 2 ] = (a)[ 2 ], (b)[ 3 ] = (a)[ 3 ])
47
48 #define MAX_NODE_ITEMS                  5
49 #define MAX_NODE_TRIANGLES              5
50 #define MAX_TRACE_DEPTH                 32
51 #define MIN_NODE_SIZE                   32.0f
52
53 #define GROW_TRACE_INFOS                32768           //%     4096
54 #define GROW_TRACE_WINDINGS             65536           //%     32768
55 #define GROW_TRACE_TRIANGLES    131072          //%     32768
56 #define GROW_TRACE_NODES                16384           //%     16384
57 #define GROW_NODE_ITEMS                 16                      //%     256
58
59 #define MAX_TW_VERTS                    24 // vortex: increased from 12 to 24 for ability co compile some insane maps with large curve count
60
61 #define TRACE_ON_EPSILON                0.1f
62
63 #define TRACE_LEAF                              -1
64 #define TRACE_LEAF_SOLID                -2
65
66 typedef struct traceVert_s
67 {
68         vec3_t                                          xyz;
69         float                                           st[ 2 ];
70 }
71 traceVert_t;
72
73 typedef struct traceInfo_s
74 {
75         shaderInfo_t                            *si;
76         int                                                     surfaceNum, castShadows, skipGrid;
77 }
78 traceInfo_t;
79
80 typedef struct traceWinding_s
81 {
82         vec4_t                                          plane;
83         int                                                     infoNum, numVerts;
84         traceVert_t                                     v[ MAX_TW_VERTS ];
85 }
86 traceWinding_t;
87
88 typedef struct traceTriangle_s
89 {
90         vec3_t                                          edge1, edge2;
91         int                                                     infoNum;
92         traceVert_t                                     v[ 3 ];
93 }
94 traceTriangle_t;
95
96 typedef struct traceNode_s
97 {
98         int                                                     type;
99         vec4_t                                          plane;
100         vec3_t                                          mins, maxs;
101         int                                                     children[ 2 ];
102         int                                                     numItems, maxItems;
103         int                                                     *items;
104 }
105 traceNode_t;
106
107
108 int                                                             noDrawContentFlags, noDrawSurfaceFlags, noDrawCompileFlags;
109
110 int                                                             numTraceInfos = 0, maxTraceInfos = 0, firstTraceInfo = 0;
111 traceInfo_t                                             *traceInfos = NULL;
112
113 int                                                             numTraceWindings = 0, maxTraceWindings = 0, deadWinding = -1;
114 traceWinding_t                                  *traceWindings = NULL;
115
116 int                                                             numTraceTriangles = 0, maxTraceTriangles = 0, deadTriangle = -1;
117 traceTriangle_t                                 *traceTriangles = NULL;
118
119 int                                                             headNodeNum = 0, skyboxNodeNum = 0, maxTraceDepth = 0, numTraceLeafNodes = 0;
120 int                                                             numTraceNodes = 0, maxTraceNodes = 0;
121 traceNode_t                                             *traceNodes = NULL;
122
123
124
125 /* -------------------------------------------------------------------------------
126
127 allocation and list management
128
129 ------------------------------------------------------------------------------- */
130
131 /*
132 AddTraceInfo() - ydnar
133 adds a trace info structure to the pool
134 */
135
136 static int AddTraceInfo( traceInfo_t *ti )
137 {
138         int             num;
139         void    *temp;
140         
141         
142         /* find an existing info */
143         for( num = firstTraceInfo; num < numTraceInfos; num++ )
144         {
145                 if( traceInfos[ num ].si == ti->si &&
146                         traceInfos[ num ].surfaceNum == ti->surfaceNum &&
147                         traceInfos[ num ].castShadows == ti->castShadows &&
148                         traceInfos[ num ].skipGrid == ti->skipGrid )
149                         return num;
150         }
151         
152         /* enough space? */
153         if( numTraceInfos >= maxTraceInfos )
154         {
155                 /* allocate more room */
156                 maxTraceInfos += GROW_TRACE_INFOS;
157                 temp = safe_malloc( maxTraceInfos * sizeof( *traceInfos ) );
158                 if( traceInfos != NULL )
159                 {
160                         memcpy( temp, traceInfos, numTraceInfos * sizeof( *traceInfos ) );
161                         free( traceInfos );
162                 }
163                 traceInfos = (traceInfo_t*) temp;
164         }
165         
166         /* add the info */
167         memcpy( &traceInfos[ num ], ti, sizeof( *traceInfos ) );
168         if( num == numTraceInfos )
169                 numTraceInfos++;
170         
171         /* return the ti number */
172         return num;
173 }
174
175
176
177 /*
178 AllocTraceNode() - ydnar
179 allocates a new trace node
180 */
181
182 static int AllocTraceNode( void )
183 {
184         traceNode_t     *temp;
185         
186         
187         /* enough space? */
188         if( numTraceNodes >= maxTraceNodes )
189         {
190                 /* reallocate more room */
191                 maxTraceNodes += GROW_TRACE_NODES;
192                 temp = safe_malloc( maxTraceNodes * sizeof( traceNode_t ) );
193                 if( traceNodes != NULL )
194                 {
195                         memcpy( temp, traceNodes, numTraceNodes * sizeof( traceNode_t ) );
196                         free( traceNodes );
197                 }
198                 traceNodes = temp;
199         }
200         
201         /* add the node */
202         memset( &traceNodes[ numTraceNodes ], 0, sizeof( traceNode_t ) );
203         traceNodes[ numTraceNodes ].type = TRACE_LEAF;
204         ClearBounds( traceNodes[ numTraceNodes ].mins, traceNodes[ numTraceNodes ].maxs );
205
206         /* Sys_Printf("alloc node %d\n", numTraceNodes); */
207
208         numTraceNodes++;
209         
210         /* return the count */
211         return (numTraceNodes - 1);
212 }
213
214
215
216 /*
217 AddTraceWinding() - ydnar
218 adds a winding to the raytracing pool
219 */
220
221 static int AddTraceWinding( traceWinding_t *tw )
222 {
223         int             num;
224         void    *temp;
225         
226         
227         /* check for a dead winding */
228         if( deadWinding >= 0 && deadWinding < numTraceWindings )
229                 num = deadWinding;
230         else
231         {
232                 /* put winding at the end of the list */
233                 num = numTraceWindings;
234                 
235                 /* enough space? */
236                 if( numTraceWindings >= maxTraceWindings )
237                 {
238                         /* allocate more room */
239                         maxTraceWindings += GROW_TRACE_WINDINGS;
240                         temp = safe_malloc( maxTraceWindings * sizeof( *traceWindings ) );
241                         if( traceWindings != NULL )
242                         {
243                                 memcpy( temp, traceWindings, numTraceWindings * sizeof( *traceWindings ) );
244                                 free( traceWindings );
245                         }
246                         traceWindings = (traceWinding_t*) temp;
247                 }
248         }
249         
250         /* add the winding */
251         memcpy( &traceWindings[ num ], tw, sizeof( *traceWindings ) );
252         if( num == numTraceWindings )
253                 numTraceWindings++;
254         deadWinding = -1;
255         
256         /* return the winding number */
257         return num;
258 }
259
260
261
262 /*
263 AddTraceTriangle() - ydnar
264 adds a triangle to the raytracing pool
265 */
266
267 static int AddTraceTriangle( traceTriangle_t *tt )
268 {
269         int             num;
270         void    *temp;
271         
272         
273         /* check for a dead triangle */
274         if( deadTriangle >= 0 && deadTriangle < numTraceTriangles )
275                 num = deadTriangle;
276         else
277         {
278                 /* put triangle at the end of the list */
279                 num = numTraceTriangles;
280                 
281                 /* enough space? */
282                 if( numTraceTriangles >= maxTraceTriangles )
283                 {
284                         /* allocate more room */
285                         maxTraceTriangles += GROW_TRACE_TRIANGLES;
286                         temp = safe_malloc( maxTraceTriangles * sizeof( *traceTriangles ) );
287                         if( traceTriangles != NULL )
288                         {
289                                 memcpy( temp, traceTriangles, numTraceTriangles * sizeof( *traceTriangles ) );
290                                 free( traceTriangles );
291                         }
292                         traceTriangles = (traceTriangle_t*) temp;
293                 }
294         }
295         
296         /* find vectors for two edges sharing the first vert */
297         VectorSubtract( tt->v[ 1 ].xyz, tt->v[ 0 ].xyz, tt->edge1 );
298         VectorSubtract( tt->v[ 2 ].xyz, tt->v[ 0 ].xyz, tt->edge2 );
299         
300         /* add the triangle */
301         memcpy( &traceTriangles[ num ], tt, sizeof( *traceTriangles ) );
302         if( num == numTraceTriangles )
303                 numTraceTriangles++;
304         deadTriangle = -1;
305         
306         /* return the triangle number */
307         return num;
308 }
309
310
311
312 /*
313 AddItemToTraceNode() - ydnar
314 adds an item reference (winding or triangle) to a trace node
315 */
316
317 static int AddItemToTraceNode( traceNode_t *node, int num )
318 {
319         void                    *temp;
320         
321         
322         /* dummy check */
323         if( num < 0 )
324                 return -1;
325         
326         /* enough space? */
327         if( node->numItems >= node->maxItems )
328         {
329                 /* allocate more room */
330                 if( node == traceNodes )
331                         node->maxItems *= 2;
332                 else
333                         node->maxItems += GROW_NODE_ITEMS;
334                 if( node->maxItems <= 0 )
335                         node->maxItems = GROW_NODE_ITEMS;
336                 temp = safe_malloc( node->maxItems * sizeof( *node->items ) );
337                 if( node->items != NULL )
338                 {
339                         memcpy( temp, node->items, node->numItems * sizeof( *node->items ) );
340                         free( node->items );
341                 }
342                 node->items = (int*) temp;
343         }
344         
345         /* add the poly */
346         node->items[ node->numItems ] = num;
347         node->numItems++;
348         
349         /* return the count */
350         return (node->numItems - 1);
351 }
352
353
354
355
356 /* -------------------------------------------------------------------------------
357
358 trace node setup
359
360 ------------------------------------------------------------------------------- */
361
362 /*
363 SetupTraceNodes_r() - ydnar
364 recursively create the initial trace node structure from the bsp tree
365 */
366
367 static int SetupTraceNodes_r( int bspNodeNum )
368 {
369         int                             i, nodeNum, bspLeafNum, newNode;
370         bspPlane_t              *plane;
371         bspNode_t               *bspNode;
372         
373         
374         /* get bsp node and plane */
375         bspNode = &bspNodes[ bspNodeNum ];
376         plane = &bspPlanes[ bspNode->planeNum ];
377         
378         /* allocate a new trace node */
379         nodeNum = AllocTraceNode();
380         
381         /* setup trace node */
382         traceNodes[ nodeNum ].type = PlaneTypeForNormal( plane->normal );
383         VectorCopy( plane->normal, traceNodes[ nodeNum ].plane );
384         traceNodes[ nodeNum ].plane[ 3 ] = plane->dist;
385         
386         /* setup children */
387         for( i = 0; i < 2; i++ )
388         {
389                 /* leafnode */
390                 if( bspNode->children[ i ] < 0 )
391                 {
392                         bspLeafNum = -bspNode->children[ i ] - 1;
393                         
394                         /* new code */
395                         newNode = AllocTraceNode();
396                         traceNodes[ nodeNum ].children[ i ] = newNode;
397                         /* have to do this separately, as gcc first executes LHS, then RHS, and if a realloc took place, this fails */
398
399                         if( bspLeafs[ bspLeafNum ].cluster == -1 )
400                                 traceNodes[ traceNodes[ nodeNum ].children[ i ] ].type = TRACE_LEAF_SOLID;
401                 }
402                 
403                 /* normal node */
404                 else
405                 {
406                         newNode = SetupTraceNodes_r( bspNode->children[ i ] );
407                         traceNodes[ nodeNum ].children[ i ] = newNode;
408                 }
409
410                 if(traceNodes[ nodeNum ].children[ i ] == 0)
411                         Error( "Invalid tracenode allocated" );
412         }
413
414         /* Sys_Printf("node %d children: %d %d\n", nodeNum, traceNodes[ nodeNum ].children[0], traceNodes[ nodeNum ].children[1]); */
415         
416         /* return node number */
417         return nodeNum;
418 }
419
420
421
422 /*
423 ClipTraceWinding() - ydnar
424 clips a trace winding against a plane into one or two parts
425 */
426
427 #define TW_ON_EPSILON   0.25f
428
429 void ClipTraceWinding( traceWinding_t *tw, vec4_t plane, traceWinding_t *front, traceWinding_t *back )
430 {
431         int                             i, j, k;
432         int                             sides[ MAX_TW_VERTS ], counts[ 3 ] = { 0, 0, 0 };
433         float                   dists[ MAX_TW_VERTS ];
434         float                   frac;
435         traceVert_t             *a, *b, mid;
436         
437         
438         /* clear front and back */
439         front->numVerts = 0;
440         back->numVerts = 0;
441         
442         /* classify points */
443         for( i = 0; i < tw->numVerts; i++ )
444         {
445                 dists[ i ] = DotProduct( tw->v[ i ].xyz, plane ) - plane[ 3 ];
446                 if( dists[ i ] < -TW_ON_EPSILON )
447                         sides[ i ] = SIDE_BACK;
448                 else if( dists[ i ] > TW_ON_EPSILON )
449                         sides[ i ] = SIDE_FRONT;
450                 else
451                         sides[ i ] = SIDE_ON;
452                 counts[ sides[ i ] ]++;
453         }
454         
455         /* entirely on front? */
456         if( counts[ SIDE_BACK ] == 0 )
457                 memcpy( front, tw, sizeof( *front ) );
458         
459         /* entirely on back? */
460         else if( counts[ SIDE_FRONT ] == 0 )
461                 memcpy( back, tw, sizeof( *back ) );
462         
463         /* straddles the plane */
464         else
465         {
466                 /* setup front and back */
467                 memcpy( front, tw, sizeof( *front ) );
468                 front->numVerts = 0;
469                 memcpy( back, tw, sizeof( *back ) ); 
470                 back->numVerts = 0;
471                 
472                 /* split the winding */
473                 for( i = 0; i < tw->numVerts; i++ )
474                 {
475                         /* radix */
476                         j = (i + 1) % tw->numVerts;
477                         
478                         /* get verts */
479                         a = &tw->v[ i ];
480                         b = &tw->v[ j ];
481                         
482                         /* handle points on the splitting plane */
483                         switch( sides[ i ] )
484                         {
485                                 case SIDE_FRONT:
486                                         if( front->numVerts >= MAX_TW_VERTS )
487                                                 Error( "MAX_TW_VERTS (%d) exceeded", MAX_TW_VERTS );
488                                         front->v[ front->numVerts++ ] = *a;
489                                         break;
490                                 
491                                 case SIDE_BACK:
492                                         if( back->numVerts >= MAX_TW_VERTS )
493                                                 Error( "MAX_TW_VERTS (%d) exceeded", MAX_TW_VERTS );
494                                         back->v[ back->numVerts++ ] = *a;
495                                         break;
496                                 
497                                 case SIDE_ON:
498                                         if( front->numVerts >= MAX_TW_VERTS || back->numVerts >= MAX_TW_VERTS )
499                                                 Error( "MAX_TW_VERTS (%d) exceeded", MAX_TW_VERTS );
500                                         front->v[ front->numVerts++ ] = *a;
501                                         back->v[ back->numVerts++ ] = *a;
502                                         continue;
503                         }
504                         
505                         /* check next point to see if we need to split the edge */
506                         if( sides[ j ] == SIDE_ON || sides[ j ] == sides[ i ] )
507                                 continue;
508                         
509                         /* check limit */
510                         if( front->numVerts >= MAX_TW_VERTS || back->numVerts >= MAX_TW_VERTS )
511                                 Error( "MAX_TW_VERTS (%d) exceeded", MAX_TW_VERTS );
512                         
513                         /* generate a split point */
514                         frac = dists[ i ] / (dists[ i ] - dists[ j ]);
515                         for( k = 0; k < 3; k++ )
516                         {
517                                 /* minimize fp precision errors */
518                                 if( plane[ k ] == 1.0f )
519                                         mid.xyz[ k ] = plane[ 3 ];
520                                 else if( plane[ k ] == -1.0f )
521                                         mid.xyz[ k ] = -plane[ 3 ];
522                                 else
523                                         mid.xyz[ k ] = a->xyz[ k ] + frac * (b->xyz[ k ] - a->xyz[ k ]);
524                         }
525                         /* set texture coordinates */
526                         mid.st[ 0 ] = a->st[ 0 ] + frac * (b->st[ 0 ] - a->st[ 0 ]);
527                         mid.st[ 1 ] = a->st[ 1 ] + frac * (b->st[ 1 ] - a->st[ 1 ]);
528                         
529                         /* copy midpoint to front and back polygons */
530                         front->v[ front->numVerts++ ] = mid;
531                         back->v[ back->numVerts++ ] = mid;
532                 }
533         }
534 }
535
536
537
538 /*
539 FilterTraceWindingIntoNodes_r() - ydnar
540 filters a trace winding into the raytracing tree
541 */
542
543 static void FilterTraceWindingIntoNodes_r( traceWinding_t *tw, int nodeNum )
544 {
545         int                             num;
546         vec4_t                  plane1, plane2, reverse;
547         traceNode_t             *node;
548         traceWinding_t  front, back;
549         
550         
551         /* don't filter if passed a bogus node (solid, etc) */
552         if( nodeNum < 0 || nodeNum >= numTraceNodes )
553                 return;
554         
555         /* get node */
556         node = &traceNodes[ nodeNum ];
557         
558         /* is this a decision node? */
559         if( node->type >= 0 )
560         {       
561                 /* create winding plane if necessary, filtering out bogus windings as well */
562                 if( nodeNum == headNodeNum )
563                 {
564                         if( !PlaneFromPoints( tw->plane, tw->v[ 0 ].xyz, tw->v[ 1 ].xyz, tw->v[ 2 ].xyz ) )
565                                 return;
566                 }
567         
568                 /* validate the node */
569                 if( node->children[ 0 ] == 0 || node->children[ 1 ] == 0 )
570                         Error( "Invalid tracenode: %d", nodeNum );
571                 
572                 /* get node plane */
573                 Vector4Copy( node->plane, plane1 );
574                 
575                 /* get winding plane */
576                 Vector4Copy( tw->plane, plane2 );
577                 
578                 /* invert surface plane */
579                 VectorSubtract( vec3_origin, plane2, reverse );
580                 reverse[ 3 ] = -plane2[ 3 ];
581                 
582                 /* front only */
583                 if( DotProduct( plane1, plane2 ) > 0.999f && fabs( plane1[ 3 ] - plane2[ 3 ] ) < 0.001f )
584                 {
585                         FilterTraceWindingIntoNodes_r( tw, node->children[ 0 ] );
586                         return;
587                 }
588                 
589                 /* back only */
590                 if( DotProduct( plane1, reverse ) > 0.999f && fabs( plane1[ 3 ] - reverse[ 3 ] ) < 0.001f )
591                 {
592                         FilterTraceWindingIntoNodes_r( tw, node->children[ 1 ] );
593                         return;
594                 }
595                 
596                 /* clip the winding by node plane */
597                 ClipTraceWinding( tw, plane1, &front, &back );
598                 
599                 /* filter by node plane */
600                 if( front.numVerts >= 3 )
601                         FilterTraceWindingIntoNodes_r( &front, node->children[ 0 ] );
602                 if( back.numVerts >= 3 )
603                         FilterTraceWindingIntoNodes_r( &back, node->children[ 1 ] );
604                 
605                 /* return to caller */
606                 return;
607         }
608         
609         /* add winding to leaf node */
610         num = AddTraceWinding( tw );
611         AddItemToTraceNode( node, num );
612 }
613
614
615
616 /*
617 SubdivideTraceNode_r() - ydnar
618 recursively subdivides a tracing node until it meets certain size and complexity criteria
619 */
620
621 static void SubdivideTraceNode_r( int nodeNum, int depth )
622 {
623         int                             i, j, count, num, frontNum, backNum, type;
624         vec3_t                  size;
625         float                   dist;
626         double                  average[ 3 ];
627         traceNode_t             *node, *frontNode, *backNode;
628         traceWinding_t  *tw, front, back;
629         
630         
631         /* dummy check */
632         if( nodeNum < 0 || nodeNum >= numTraceNodes )
633                 return;
634         
635         /* get node */
636         node = &traceNodes[ nodeNum ];
637         
638         /* runaway recursion check */
639         if( depth >= MAX_TRACE_DEPTH )
640         {
641                 //%     Sys_Printf( "Depth: (%d items)\n", node->numItems );
642                 numTraceLeafNodes++;
643                 return;
644         }
645         depth++;
646         
647         /* is this a decision node? */
648         if( node->type >= 0 )
649         {
650                 /* subdivide children */
651                 frontNum = node->children[ 0 ];
652                 backNum = node->children[ 1 ];
653                 SubdivideTraceNode_r( frontNum, depth );
654                 SubdivideTraceNode_r( backNum, depth );
655                 return;
656         }
657         
658         /* bound the node */
659         ClearBounds( node->mins, node->maxs );
660         VectorClear( average );
661         count = 0;
662         for( i = 0; i < node->numItems; i++ )
663         {
664                 /* get winding */
665                 tw = &traceWindings[ node->items[ i ] ];
666                 
667                 /* walk its verts */
668                 for( j = 0; j < tw->numVerts; j++ )
669                 {
670                         AddPointToBounds( tw->v[ j ].xyz, node->mins, node->maxs );
671                         average[ 0 ] += tw->v[ j ].xyz[ 0 ];
672                         average[ 1 ] += tw->v[ j ].xyz[ 1 ];
673                         average[ 2 ] += tw->v[ j ].xyz[ 2 ];
674                         count++;
675                 }
676         }
677         
678         /* check triangle limit */
679         //%     if( node->numItems <= MAX_NODE_ITEMS )
680         if( (count - (node->numItems * 2)) < MAX_NODE_TRIANGLES )
681         {
682                 //%     Sys_Printf( "Limit: (%d triangles)\n", (count - (node->numItems * 2)) );
683                 numTraceLeafNodes++;
684                 return;
685         }
686         
687         /* the largest dimension of the bounding box will be the split axis */
688         VectorSubtract( node->maxs, node->mins, size );
689         if( size[ 0 ] >= size[ 1 ] && size[ 0 ] >= size[ 2 ] )
690                 type = PLANE_X;
691         else if( size[ 1 ] >= size[ 0 ] && size[ 1 ] >= size[ 2 ] )
692                 type = PLANE_Y;
693         else
694                 type = PLANE_Z;
695         
696         /* don't split small nodes */
697         if( size[ type ] <= MIN_NODE_SIZE )
698         {
699                 //%     Sys_Printf( "Limit: %f %f %f (%d items)\n", size[ 0 ], size[ 1 ], size[ 2 ], node->numItems );
700                 numTraceLeafNodes++;
701                 return;
702         }
703         
704         /* set max trace depth */
705         if( depth > maxTraceDepth )
706                 maxTraceDepth = depth;
707         
708         /* snap the average */
709         dist = floor( average[ type ] / count );
710         
711         /* dummy check it */
712         if( dist <= node->mins[ type ] || dist >= node->maxs[ type ] )
713                 dist = floor( 0.5f * (node->mins[ type ] + node->maxs[ type ]) );
714         
715         /* allocate child nodes */
716         frontNum = AllocTraceNode();
717         backNum = AllocTraceNode();
718         
719         /* reset pointers */
720         node = &traceNodes[ nodeNum ];
721         frontNode = &traceNodes[ frontNum ];
722         backNode = &traceNodes[ backNum ];
723         
724         /* attach children */
725         node->type = type;
726         node->plane[ type ] = 1.0f;
727         node->plane[ 3 ] = dist;
728         node->children[ 0 ] = frontNum;
729         node->children[ 1 ] = backNum;
730         
731         /* setup front node */
732         frontNode->maxItems = (node->maxItems >> 1);
733         frontNode->items = safe_malloc( frontNode->maxItems * sizeof( *frontNode->items ) );
734         
735         /* setup back node */
736         backNode->maxItems = (node->maxItems >> 1);
737         backNode->items = safe_malloc( backNode->maxItems * sizeof( *backNode->items ) );
738         
739         /* filter windings into child nodes */
740         for( i = 0; i < node->numItems; i++ )
741         {
742                 /* get winding */
743                 tw = &traceWindings[ node->items[ i ] ];
744                 
745                 /* clip the winding by the new split plane */
746                 ClipTraceWinding( tw, node->plane, &front, &back );
747                 
748                 /* kill the existing winding */
749                 if( front.numVerts >= 3 || back.numVerts >= 3 )
750                         deadWinding = node->items[ i ];
751                 
752                 /* add front winding */
753                 if( front.numVerts >= 3 )
754                 {
755                         num = AddTraceWinding( &front );
756                         AddItemToTraceNode( frontNode, num );
757                 }
758                 
759                 /* add back winding */
760                 if( back.numVerts >= 3 )
761                 {
762                         num = AddTraceWinding( &back );
763                         AddItemToTraceNode( backNode, num );
764                 }
765         }
766         
767         /* free original node winding list */
768         node->numItems = 0;
769         node->maxItems = 0;
770         free( node->items );
771         node->items = NULL;
772         
773         /* check children */
774         if( frontNode->numItems <= 0 )
775         {
776                 frontNode->maxItems = 0;
777                 free( frontNode->items );
778                 frontNode->items = NULL;
779         }
780         
781         if( backNode->numItems <= 0 )
782         {
783                 backNode->maxItems = 0;
784                 free( backNode->items );
785                 backNode->items = NULL;
786         }
787         
788         /* subdivide children */
789         SubdivideTraceNode_r( frontNum, depth );
790         SubdivideTraceNode_r( backNum, depth );
791 }
792
793
794
795 /*
796 TriangulateTraceNode_r()
797 optimizes the tracing data by changing trace windings into triangles
798 */
799
800 static int TriangulateTraceNode_r( int nodeNum )
801 {
802         int                             i, j, num, frontNum, backNum, numWindings, *windings;
803         traceNode_t             *node;
804         traceWinding_t  *tw;
805         traceTriangle_t tt;
806         
807         
808         /* dummy check */
809         if( nodeNum < 0 || nodeNum >= numTraceNodes )
810                 return 0;
811         
812         /* get node */
813         node = &traceNodes[ nodeNum ];
814         
815         /* is this a decision node? */
816         if( node->type >= 0 )
817         {
818                 /* triangulate children */
819                 frontNum = node->children[ 0 ];
820                 backNum = node->children[ 1 ];
821                 node->numItems = TriangulateTraceNode_r( frontNum );
822                 node->numItems += TriangulateTraceNode_r( backNum );
823                 return node->numItems;
824         }
825         
826         /* empty node? */
827         if( node->numItems == 0 )
828         {
829                 node->maxItems = 0;
830                 if( node->items != NULL )
831                         free( node->items );
832                 return node->numItems;
833         }
834         
835         /* store off winding data */
836         numWindings = node->numItems;
837         windings = node->items;
838         
839         /* clear it */
840         node->numItems = 0;
841         node->maxItems = numWindings * 2;
842         node->items = safe_malloc( node->maxItems * sizeof( tt ) );
843         
844         /* walk winding list */
845         for( i = 0; i < numWindings; i++ )
846         {
847                 /* get winding */
848                 tw = &traceWindings[ windings[ i ] ];
849                 
850                 /* initial setup */
851                 tt.infoNum = tw->infoNum;
852                 tt.v[ 0 ] = tw->v[ 0 ];
853                 
854                 /* walk vertex list */
855                 for( j = 1; j + 1 < tw->numVerts; j++ )
856                 {
857                         /* set verts */
858                         tt.v[ 1 ] = tw->v[ j ];
859                         tt.v[ 2 ] = tw->v[ j + 1 ];
860                         
861                         /* find vectors for two edges sharing the first vert */
862                         VectorSubtract( tt.v[ 1 ].xyz, tt.v[ 0 ].xyz, tt.edge1 );
863                         VectorSubtract( tt.v[ 2 ].xyz, tt.v[ 0 ].xyz, tt.edge2 );
864                         
865                         /* add it to the node */
866                         num = AddTraceTriangle( &tt );
867                         AddItemToTraceNode( node, num );
868                 }
869         }
870         
871         /* free windings */
872         if( windings != NULL )
873                 free( windings );
874         
875         /* return item count */
876         return node->numItems;
877 }
878
879
880
881 /* -------------------------------------------------------------------------------
882
883 shadow casting item setup (triangles, patches, entities)
884
885 ------------------------------------------------------------------------------- */
886
887 /*
888 PopulateWithBSPModel() - ydnar
889 filters a bsp model's surfaces into the raytracing tree
890 */
891
892 static void PopulateWithBSPModel( bspModel_t *model, m4x4_t transform )
893 {
894         int                                     i, j, x, y, pw[ 5 ], r, nodeNum;
895         bspDrawSurface_t        *ds;
896         surfaceInfo_t           *info;
897         bspDrawVert_t           *verts;
898         int                                     *indexes;
899         mesh_t                          srcMesh, *mesh, *subdivided;
900         traceInfo_t                     ti;
901         traceWinding_t          tw;
902         
903         
904         /* dummy check */
905         if( model == NULL || transform == NULL )
906                 return;
907         
908         /* walk the list of surfaces in this model and fill out the info structs */
909         for( i = 0; i < model->numBSPSurfaces; i++ )
910         {
911                 /* get surface and info */
912                 ds = &bspDrawSurfaces[ model->firstBSPSurface + i ];
913                 info = &surfaceInfos[ model->firstBSPSurface + i ];
914                 if( info->si == NULL )
915                         continue;
916                 
917                 /* no shadows */
918                 if( !info->castShadows )
919                         continue;
920                 
921                 /* patchshadows? */
922                 if( ds->surfaceType == MST_PATCH && patchShadows == qfalse )
923                         continue;
924                 
925                 /* some surfaces in the bsp might have been tagged as nodraw, with a bogus shader */
926                 if( (bspShaders[ ds->shaderNum ].contentFlags & noDrawContentFlags) || 
927                         (bspShaders[ ds->shaderNum ].surfaceFlags & noDrawSurfaceFlags) )
928                         continue;
929                 
930                 /* translucent surfaces that are neither alphashadow or lightfilter don't cast shadows */
931                 if( (info->si->compileFlags & C_NODRAW) )
932                         continue;
933                 if( (info->si->compileFlags & C_TRANSLUCENT) &&
934                         !(info->si->compileFlags & C_ALPHASHADOW) && 
935                         !(info->si->compileFlags & C_LIGHTFILTER) )
936                         continue;
937                 
938                 /* setup trace info */
939                 ti.si = info->si;
940                 ti.castShadows = info->castShadows;
941                 ti.surfaceNum = model->firstBSPBrush + i;
942                 ti.skipGrid = (ds->surfaceType == MST_PATCH);
943                 
944                 /* choose which node (normal or skybox) */
945                 if( info->parentSurfaceNum >= 0 )
946                 {
947                         nodeNum = skyboxNodeNum;
948                         
949                         /* sky surfaces in portal skies are ignored */
950                         if( info->si->compileFlags & C_SKY )
951                                 continue;
952                 }
953                 else
954                         nodeNum = headNodeNum;
955                 
956                 /* setup trace winding */
957                 memset( &tw, 0, sizeof( tw ) );
958                 tw.infoNum = AddTraceInfo( &ti );
959                 tw.numVerts = 3;
960                 
961                 /* switch on type */
962                 switch( ds->surfaceType )
963                 {
964                         /* handle patches */
965                         case MST_PATCH:
966                                 /* subdivide the surface */
967                                 srcMesh.width = ds->patchWidth;
968                                 srcMesh.height = ds->patchHeight;
969                                 srcMesh.verts = &bspDrawVerts[ ds->firstVert ];
970                                 //%     subdivided = SubdivideMesh( srcMesh, 8, 512 );
971                                 subdivided = SubdivideMesh2( srcMesh, info->patchIterations );
972                                 
973                                 /* fit it to the curve and remove colinear verts on rows/columns */
974                                 PutMeshOnCurve( *subdivided );
975                                 mesh = RemoveLinearMeshColumnsRows( subdivided );
976                                 FreeMesh( subdivided );
977                                 
978                                 /* set verts */
979                                 verts = mesh->verts;
980                                 
981                                 /* subdivide each quad to place the models */
982                                 for( y = 0; y < (mesh->height - 1); y++ )
983                                 {
984                                         for( x = 0; x < (mesh->width - 1); x++ )
985                                         {
986                                                 /* set indexes */
987                                                 pw[ 0 ] = x + (y * mesh->width);
988                                                 pw[ 1 ] = x + ((y + 1) * mesh->width);
989                                                 pw[ 2 ] = x + 1 + ((y + 1) * mesh->width);
990                                                 pw[ 3 ] = x + 1 + (y * mesh->width);
991                                                 pw[ 4 ] = x + (y * mesh->width);        /* same as pw[ 0 ] */
992                                                 
993                                                 /* set radix */
994                                                 r = (x + y) & 1;
995                                                 
996                                                 /* make first triangle */
997                                                 VectorCopy( verts[ pw[ r + 0 ] ].xyz, tw.v[ 0 ].xyz );
998                                                 Vector2Copy( verts[ pw[ r + 0 ] ].st, tw.v[ 0 ].st );
999                                                 VectorCopy( verts[ pw[ r + 1 ] ].xyz, tw.v[ 1 ].xyz );
1000                                                 Vector2Copy( verts[ pw[ r + 1 ] ].st, tw.v[ 1 ].st );
1001                                                 VectorCopy( verts[ pw[ r + 2 ] ].xyz, tw.v[ 2 ].xyz );
1002                                                 Vector2Copy( verts[ pw[ r + 2 ] ].st, tw.v[ 2 ].st );
1003                                                 m4x4_transform_point( transform, tw.v[ 0 ].xyz );
1004                                                 m4x4_transform_point( transform, tw.v[ 1 ].xyz );
1005                                                 m4x4_transform_point( transform, tw.v[ 2 ].xyz );
1006                                                 FilterTraceWindingIntoNodes_r( &tw, nodeNum );
1007                                                 
1008                                                 /* make second triangle */
1009                                                 VectorCopy( verts[ pw[ r + 0 ] ].xyz, tw.v[ 0 ].xyz );
1010                                                 Vector2Copy( verts[ pw[ r + 0 ] ].st, tw.v[ 0 ].st );
1011                                                 VectorCopy( verts[ pw[ r + 2 ] ].xyz, tw.v[ 1 ].xyz );
1012                                                 Vector2Copy( verts[ pw[ r + 2 ] ].st, tw.v[ 1 ].st );
1013                                                 VectorCopy( verts[ pw[ r + 3 ] ].xyz, tw.v[ 2 ].xyz );
1014                                                 Vector2Copy( verts[ pw[ r + 3 ] ].st, tw.v[ 2 ].st );
1015                                                 m4x4_transform_point( transform, tw.v[ 0 ].xyz );
1016                                                 m4x4_transform_point( transform, tw.v[ 1 ].xyz );
1017                                                 m4x4_transform_point( transform, tw.v[ 2 ].xyz );
1018                                                 FilterTraceWindingIntoNodes_r( &tw, nodeNum );
1019                                         }
1020                                 }
1021                                 
1022                                 /* free the subdivided mesh */
1023                                 FreeMesh( mesh );
1024                                 break;
1025                         
1026                         /* handle triangle surfaces */
1027                         case MST_TRIANGLE_SOUP:
1028                         case MST_PLANAR:
1029                                 /* set verts and indexes */
1030                                 verts = &bspDrawVerts[ ds->firstVert ];
1031                                 indexes = &bspDrawIndexes[ ds->firstIndex ];
1032                                 
1033                                 /* walk the triangle list */
1034                                 for( j = 0; j < ds->numIndexes; j += 3 )
1035                                 {
1036                                         VectorCopy( verts[ indexes[ j ] ].xyz, tw.v[ 0 ].xyz );
1037                                         Vector2Copy( verts[ indexes[ j ] ].st, tw.v[ 0 ].st );
1038                                         VectorCopy( verts[ indexes[ j + 1 ] ].xyz, tw.v[ 1 ].xyz );
1039                                         Vector2Copy( verts[ indexes[ j + 1 ] ].st, tw.v[ 1 ].st );
1040                                         VectorCopy( verts[ indexes[ j + 2 ] ].xyz, tw.v[ 2 ].xyz );
1041                                         Vector2Copy( verts[ indexes[ j + 2 ] ].st, tw.v[ 2 ].st );
1042                                         m4x4_transform_point( transform, tw.v[ 0 ].xyz );
1043                                         m4x4_transform_point( transform, tw.v[ 1 ].xyz );
1044                                         m4x4_transform_point( transform, tw.v[ 2 ].xyz );
1045                                         FilterTraceWindingIntoNodes_r( &tw, nodeNum );
1046                                 }
1047                                 break;
1048                         
1049                         /* other surface types do not cast shadows */
1050                         default:
1051                                 break;
1052                 }
1053         }
1054 }
1055
1056
1057
1058 /*
1059 PopulateWithPicoModel() - ydnar
1060 filters a picomodel's surfaces into the raytracing tree
1061 */
1062
1063 static void PopulateWithPicoModel( int castShadows, picoModel_t *model, m4x4_t transform )
1064 {
1065         int                                     i, j, k, numSurfaces, numIndexes;
1066         picoSurface_t           *surface;
1067         picoShader_t            *shader;
1068         picoVec_t                       *xyz, *st;
1069         picoIndex_t                     *indexes;
1070         traceInfo_t                     ti;
1071         traceWinding_t          tw;
1072         
1073         
1074         /* dummy check */
1075         if( model == NULL || transform == NULL )
1076                 return;
1077         
1078         /* get info */
1079         numSurfaces = PicoGetModelNumSurfaces( model );
1080         
1081         /* walk the list of surfaces in this model and fill out the info structs */
1082         for( i = 0; i < numSurfaces; i++ )
1083         {
1084                 /* get surface */
1085                 surface = PicoGetModelSurface( model, i );
1086                 if( surface == NULL )
1087                         continue;
1088                 
1089                 /* only handle triangle surfaces initially (fixme: support patches) */
1090                 if( PicoGetSurfaceType( surface ) != PICO_TRIANGLES )
1091                         continue;
1092                 
1093                 /* get shader (fixme: support shader remapping) */
1094                 shader = PicoGetSurfaceShader( surface );
1095                 if( shader == NULL )
1096                         continue;
1097                 ti.si = ShaderInfoForShader( PicoGetShaderName( shader ) );
1098                 if( ti.si == NULL )
1099                         continue;
1100                 
1101                 /* translucent surfaces that are neither alphashadow or lightfilter don't cast shadows */
1102                 if( (ti.si->compileFlags & C_NODRAW) )
1103                         continue;
1104                 if( (ti.si->compileFlags & C_TRANSLUCENT) &&
1105                         !(ti.si->compileFlags & C_ALPHASHADOW) && 
1106                         !(ti.si->compileFlags & C_LIGHTFILTER) )
1107                         continue;
1108                 
1109                 /* setup trace info */
1110                 ti.castShadows = castShadows;
1111                 ti.surfaceNum = -1;
1112                 ti.skipGrid = qtrue; // also ignore picomodels when skipping patches
1113                 
1114                 /* setup trace winding */
1115                 memset( &tw, 0, sizeof( tw ) );
1116                 tw.infoNum = AddTraceInfo( &ti );
1117                 tw.numVerts = 3;
1118                 
1119                 /* get info */
1120                 numIndexes = PicoGetSurfaceNumIndexes( surface );
1121                 indexes = PicoGetSurfaceIndexes( surface, 0 );
1122                 
1123                 /* walk the triangle list */
1124                 for( j = 0; j < numIndexes; j += 3, indexes += 3 )
1125                 {
1126                         for( k = 0; k < 3; k++ )
1127                         {
1128                                 xyz = PicoGetSurfaceXYZ( surface, indexes[ k ] );
1129                                 st = PicoGetSurfaceST( surface, 0, indexes[ k ] );
1130                                 VectorCopy( xyz, tw.v[ k ].xyz );
1131                                 Vector2Copy( st, tw.v[ k ].st );
1132                                 m4x4_transform_point( transform, tw.v[ k ].xyz );
1133                         }
1134                         FilterTraceWindingIntoNodes_r( &tw, headNodeNum );
1135                 }
1136         }
1137 }
1138
1139
1140
1141 /*
1142 PopulateTraceNodes() - ydnar
1143 fills the raytracing tree with world and entity occluders
1144 */
1145
1146 static void PopulateTraceNodes( void )
1147 {
1148         int                             i, m, frame, castShadows;
1149         float                   temp;
1150         entity_t                *e;
1151         const char              *value;
1152         picoModel_t             *model;
1153         vec3_t                  origin, scale, angles;
1154         m4x4_t                  transform;
1155
1156         
1157         /* add worldspawn triangles */
1158         m4x4_identity( transform );
1159         PopulateWithBSPModel( &bspModels[ 0 ], transform );
1160         
1161         /* walk each entity list */
1162         for( i = 1; i < numEntities; i++ )
1163         {
1164                 /* get entity */
1165                 e = &entities[ i ];
1166                 
1167                 /* get shadow flags */
1168                 castShadows = ENTITY_CAST_SHADOWS;
1169                 GetEntityShadowFlags( e, NULL, &castShadows, NULL );
1170                 
1171                 /* early out? */
1172                 if( !castShadows )
1173                         continue;
1174                 
1175                 /* get entity origin */
1176                 GetVectorForKey( e, "origin", origin );
1177                 
1178                 /* get scale */
1179                 scale[ 0 ] = scale[ 1 ] = scale[ 2 ] = 1.0f;
1180                 temp = FloatForKey( e, "modelscale" );
1181                 if( temp != 0.0f )
1182                         scale[ 0 ] = scale[ 1 ] = scale[ 2 ] = temp;
1183                 value = ValueForKey( e, "modelscale_vec" );
1184                 if( value[ 0 ] != '\0' )
1185                         sscanf( value, "%f %f %f", &scale[ 0 ], &scale[ 1 ], &scale[ 2 ] );
1186                 
1187                 /* get "angle" (yaw) or "angles" (pitch yaw roll) */
1188                 angles[ 0 ] = angles[ 1 ] = angles[ 2 ] = 0.0f;
1189                 angles[ 2 ] = FloatForKey( e, "angle" );
1190                 value = ValueForKey( e, "angles" );
1191                 if( value[ 0 ] != '\0' )
1192                         sscanf( value, "%f %f %f", &angles[ 1 ], &angles[ 2 ], &angles[ 0 ] );
1193                 
1194                 /* set transform matrix (thanks spog) */
1195                 m4x4_identity( transform );
1196                 m4x4_pivoted_transform_by_vec3( transform, origin, angles, eXYZ, scale, vec3_origin );
1197                 
1198                 /* hack: Stable-1_2 and trunk have differing row/column major matrix order
1199                    this transpose is necessary with Stable-1_2
1200                    uncomment the following line with old m4x4_t (non 1.3/spog_branch) code */
1201                 //%     m4x4_transpose( transform );
1202                 
1203                 /* get model */
1204                 value = ValueForKey( e, "model" );
1205                 
1206                 /* switch on model type */
1207                 switch( value[ 0 ] )
1208                 {
1209                         /* no model */
1210                         case '\0':
1211                                 break;
1212                         
1213                         /* bsp model */
1214                         case '*':
1215                                 m = atoi( &value[ 1 ] );
1216                                 if( m <= 0 || m >= numBSPModels )
1217                                         continue;
1218                                 PopulateWithBSPModel( &bspModels[ m ], transform );
1219                                 break;
1220                         
1221                         /* external model */
1222                         default:
1223                                 frame = IntForKey( e, "_frame" );
1224                                 model = LoadModel( value, frame );
1225                                 if( model == NULL )
1226                                         continue;
1227                                 PopulateWithPicoModel( castShadows, model, transform );
1228                                 continue;
1229                 }
1230                 
1231                 /* get model2 */
1232                 value = ValueForKey( e, "model2" );
1233                 
1234                 /* switch on model type */
1235                 switch( value[ 0 ] )
1236                 {
1237                         /* no model */
1238                         case '\0':
1239                                 break;
1240                         
1241                         /* bsp model */
1242                         case '*':
1243                                 m = atoi( &value[ 1 ] );
1244                                 if( m <= 0 || m >= numBSPModels )
1245                                         continue;
1246                                 PopulateWithBSPModel( &bspModels[ m ], transform );
1247                                 break;
1248                         
1249                         /* external model */
1250                         default:
1251                                 frame = IntForKey( e, "_frame2" );
1252                                 model = LoadModel( value, frame );
1253                                 if( model == NULL )
1254                                         continue;
1255                                 PopulateWithPicoModel( castShadows, model, transform );
1256                                 continue;
1257                 }
1258         }
1259 }
1260
1261
1262
1263
1264 /* -------------------------------------------------------------------------------
1265
1266 trace initialization
1267
1268 ------------------------------------------------------------------------------- */
1269
1270 /*
1271 SetupTraceNodes() - ydnar
1272 creates a balanced bsp with axis-aligned splits for efficient raytracing
1273 */
1274
1275 void SetupTraceNodes( void )
1276 {
1277         /* note it */
1278         Sys_FPrintf( SYS_VRB, "--- SetupTraceNodes ---\n" );
1279         
1280         /* find nodraw bit */
1281         noDrawContentFlags = noDrawSurfaceFlags = noDrawCompileFlags = 0;
1282         ApplySurfaceParm( "nodraw", &noDrawContentFlags, &noDrawSurfaceFlags, &noDrawCompileFlags );
1283         
1284         /* create the baseline raytracing tree from the bsp tree */
1285         headNodeNum = SetupTraceNodes_r( 0 );
1286         
1287         /* create outside node for skybox surfaces */
1288         skyboxNodeNum = AllocTraceNode();
1289         
1290         /* populate the tree with triangles from the world and shadow casting entities */
1291         PopulateTraceNodes();
1292         
1293         /* create the raytracing bsp */
1294         if( loMem == qfalse )
1295         {
1296                 SubdivideTraceNode_r( headNodeNum, 0 );
1297                 SubdivideTraceNode_r( skyboxNodeNum, 0 );
1298         }
1299         
1300         /* create triangles from the trace windings */
1301         TriangulateTraceNode_r( headNodeNum );
1302         TriangulateTraceNode_r( skyboxNodeNum );
1303         
1304         /* emit some stats */
1305         //%     Sys_FPrintf( SYS_VRB, "%9d original triangles\n", numOriginalTriangles );
1306         Sys_FPrintf( SYS_VRB, "%9d trace windings (%.2fMB)\n", numTraceWindings, (float) (numTraceWindings * sizeof( *traceWindings )) / (1024.0f * 1024.0f) );
1307         Sys_FPrintf( SYS_VRB, "%9d trace triangles (%.2fMB)\n", numTraceTriangles, (float) (numTraceTriangles * sizeof( *traceTriangles )) / (1024.0f * 1024.0f) );
1308         Sys_FPrintf( SYS_VRB, "%9d trace nodes (%.2fMB)\n", numTraceNodes, (float) (numTraceNodes * sizeof( *traceNodes )) / (1024.0f * 1024.0f) );
1309         Sys_FPrintf( SYS_VRB, "%9d leaf nodes (%.2fMB)\n", numTraceLeafNodes, (float) (numTraceLeafNodes * sizeof( *traceNodes )) / (1024.0f * 1024.0f) );
1310         //%     Sys_FPrintf( SYS_VRB, "%9d average triangles per leaf node\n", numTraceTriangles / numTraceLeafNodes );
1311         Sys_FPrintf( SYS_VRB, "%9d average windings per leaf node\n", numTraceWindings / (numTraceLeafNodes + 1) );
1312         Sys_FPrintf( SYS_VRB, "%9d max trace depth\n", maxTraceDepth );
1313         
1314         /* free trace windings */
1315         free( traceWindings );
1316         numTraceWindings = 0;
1317         maxTraceWindings = 0;
1318         deadWinding = -1;
1319         
1320         /* debug code: write out trace triangles to an alias obj file */
1321         #if 0
1322         {
1323                 int                             i, j;
1324                 FILE                    *file;
1325                 char                    filename[ 1024 ];
1326                 traceWinding_t  *tw;
1327                 
1328                 
1329                 /* open the file */
1330                 strcpy( filename, source );
1331                 StripExtension( filename );
1332                 strcat( filename, ".lin" );
1333                 Sys_Printf( "Opening light trace file %s...\n", filename );
1334                 file = fopen( filename, "w" );
1335                 if( file == NULL )
1336                         Error( "Error opening %s for writing", filename );
1337                 
1338                 /* walk node list */
1339                 for( i = 0; i < numTraceWindings; i++ )
1340                 {
1341                         tw = &traceWindings[ i ];
1342                         for( j = 0; j < tw->numVerts + 1; j++ )
1343                                 fprintf( file, "%f %f %f\n",
1344                                         tw->v[ j % tw->numVerts ].xyz[ 0 ], tw->v[ j % tw->numVerts ].xyz[ 1 ], tw->v[ j % tw->numVerts ].xyz[ 2 ] );
1345                 }
1346                 
1347                 /* close it */
1348                 fclose( file );
1349         }
1350         #endif
1351 }
1352
1353
1354
1355 /* -------------------------------------------------------------------------------
1356
1357 raytracer
1358
1359 ------------------------------------------------------------------------------- */
1360
1361 /*
1362 TraceTriangle()
1363 based on code written by william 'spog' joseph
1364 based on code originally written by tomas moller and ben trumbore, journal of graphics tools, 2(1):21-28, 1997
1365 */
1366
1367 #define BARY_EPSILON                    0.01f
1368 #define ASLF_EPSILON                    0.0001f /* so to not get double shadows */
1369 #define COPLANAR_EPSILON                0.25f   //%     0.000001f
1370 #define NEAR_SHADOW_EPSILON             1.5f    //%     1.25f
1371 #define SELF_SHADOW_EPSILON             0.5f
1372
1373 qboolean TraceTriangle( traceInfo_t *ti, traceTriangle_t *tt, trace_t *trace )
1374 {
1375         int                             i;
1376         float                   tvec[ 3 ], pvec[ 3 ], qvec[ 3 ];
1377         float                   det, invDet, depth;
1378         float                   u, v, w, s, t;
1379         int                             is, it;
1380         byte                    *pixel;
1381         float                   shadow;
1382         shaderInfo_t    *si;
1383         
1384         
1385         /* don't double-trace against sky */
1386         si = ti->si;
1387         if( trace->compileFlags & si->compileFlags & C_SKY )
1388                 return qfalse;
1389         
1390         /* receive shadows from worldspawn group only */
1391         if( trace->recvShadows == 1 )
1392         {
1393                 if( ti->castShadows != 1 )
1394                         return qfalse;
1395         }
1396
1397         /* receive shadows from same group and worldspawn group */
1398         else if( trace->recvShadows > 1 )
1399         {
1400                 if( ti->castShadows != 1 && abs( ti->castShadows ) != abs( trace->recvShadows ) )
1401                         return qfalse;
1402                 //%     Sys_Printf( "%d:%d ", tt->castShadows, trace->recvShadows );
1403         }
1404         
1405         /* receive shadows from the same group only (< 0) */
1406         else
1407         {
1408                 if( abs( ti->castShadows ) != abs( trace->recvShadows ) )
1409                         return qfalse;
1410         }
1411         
1412         /* skip patches when doing the grid (FIXME this is an ugly hack) */
1413         if( inGrid )
1414         {
1415                 if (ti->skipGrid)
1416                         return qfalse;
1417         }
1418         
1419         /* begin calculating determinant - also used to calculate u parameter */
1420         CrossProduct( trace->direction, tt->edge2, pvec );
1421         
1422         /* if determinant is near zero, trace lies in plane of triangle */
1423         det = DotProduct( tt->edge1, pvec );
1424         
1425         /* the non-culling branch */
1426         if( fabs( det ) < COPLANAR_EPSILON )
1427                 return qfalse;
1428         invDet = 1.0f / det;
1429         
1430         /* calculate distance from first vertex to ray origin */
1431         VectorSubtract( trace->origin, tt->v[ 0 ].xyz, tvec );
1432         
1433         /* calculate u parameter and test bounds */
1434         u = DotProduct( tvec, pvec ) * invDet;
1435         if( u < -BARY_EPSILON || u > (1.0f + BARY_EPSILON) )
1436                 return qfalse;
1437         
1438         /* prepare to test v parameter */
1439         CrossProduct( tvec, tt->edge1, qvec );
1440         
1441         /* calculate v parameter and test bounds */
1442         v = DotProduct( trace->direction, qvec ) * invDet;
1443         if( v < -BARY_EPSILON || (u + v) > (1.0f + BARY_EPSILON) )
1444                 return qfalse;
1445         
1446         /* calculate t (depth) */
1447         depth = DotProduct( tt->edge2, qvec ) * invDet;
1448         if( depth <= trace->inhibitRadius || depth >= trace->distance )
1449                 return qfalse;
1450         
1451         /* if hitpoint is really close to trace origin (sample point), then check for self-shadowing */
1452         if( depth <= SELF_SHADOW_EPSILON )
1453         {
1454                 /* don't self-shadow */
1455                 for( i = 0; i < trace->numSurfaces; i++ )
1456                 {
1457                         if( ti->surfaceNum == trace->surfaces[ i ] )
1458                                 return qfalse;
1459                 }
1460         }
1461         
1462         /* stack compile flags */
1463         trace->compileFlags |= si->compileFlags;
1464         
1465         /* don't trace against sky */
1466         if( si->compileFlags & C_SKY )
1467                 return qfalse;
1468         
1469         /* most surfaces are completely opaque */
1470         if( !(si->compileFlags & (C_ALPHASHADOW | C_LIGHTFILTER)) ||
1471                 si->lightImage == NULL || si->lightImage->pixels == NULL )
1472         {
1473                 VectorMA( trace->origin, depth, trace->direction, trace->hit );
1474                 VectorClear( trace->color );
1475                 trace->opaque = qtrue;
1476                 return qtrue;
1477         }
1478
1479         /* force subsampling because the lighting is texture dependent */
1480         trace->forceSubsampling = 1.0;
1481         
1482         /* try to avoid double shadows near triangle seams */
1483         if( u < -ASLF_EPSILON || u > (1.0f + ASLF_EPSILON) ||
1484                 v < -ASLF_EPSILON || (u + v) > (1.0f + ASLF_EPSILON) )
1485                 return qfalse;
1486         
1487         /* calculate w parameter */
1488         w = 1.0f - (u + v);
1489         
1490         /* calculate st from uvw (barycentric) coordinates */
1491         s = w * tt->v[ 0 ].st[ 0 ] + u * tt->v[ 1 ].st[ 0 ] + v * tt->v[ 2 ].st[ 0 ];
1492         t = w * tt->v[ 0 ].st[ 1 ] + u * tt->v[ 1 ].st[ 1 ] + v * tt->v[ 2 ].st[ 1 ];
1493         s = s - floor( s );
1494         t = t - floor( t );
1495         is = s * si->lightImage->width;
1496         it = t * si->lightImage->height;
1497         
1498         /* get pixel */
1499         pixel = si->lightImage->pixels + 4 * (it * si->lightImage->width + is);
1500         
1501         /* ydnar: color filter */
1502         if( si->compileFlags & C_LIGHTFILTER )
1503         {
1504                 /* filter by texture color */
1505                 trace->color[ 0 ] *= ((1.0f / 255.0f) * pixel[ 0 ]);
1506                 trace->color[ 1 ] *= ((1.0f / 255.0f) * pixel[ 1 ]);
1507                 trace->color[ 2 ] *= ((1.0f / 255.0f) * pixel[ 2 ]);
1508         }
1509         
1510         /* ydnar: alpha filter */
1511         if( si->compileFlags & C_ALPHASHADOW )
1512         {
1513                 /* filter by inverse texture alpha */
1514                 shadow = (1.0f / 255.0f) * (255 - pixel[ 3 ]);
1515                 trace->color[ 0 ] *= shadow;
1516                 trace->color[ 1 ] *= shadow;
1517                 trace->color[ 2 ] *= shadow;
1518         }
1519         
1520         /* check filter for opaque */
1521         if( trace->color[ 0 ] <= 0.001f && trace->color[ 1 ] <= 0.001f && trace->color[ 2 ] <= 0.001f )
1522         {
1523                 VectorClear( trace->color );
1524                 VectorMA( trace->origin, depth, trace->direction, trace->hit );
1525                 trace->opaque = qtrue;
1526                 return qtrue;
1527         }
1528         
1529         /* continue tracing */
1530         return qfalse;
1531 }
1532
1533
1534
1535 /*
1536 TraceWinding() - ydnar
1537 temporary hack
1538 */
1539
1540 qboolean TraceWinding( traceWinding_t *tw, trace_t *trace )
1541 {
1542         int                             i;
1543         traceTriangle_t tt;
1544         
1545         
1546         /* initial setup */
1547         tt.infoNum = tw->infoNum;
1548         tt.v[ 0 ] = tw->v[ 0 ];
1549         
1550         /* walk vertex list */
1551         for( i = 1; i + 1 < tw->numVerts; i++ )
1552         {
1553                 /* set verts */
1554                 tt.v[ 1 ] = tw->v[ i ];
1555                 tt.v[ 2 ] = tw->v[ i + 1 ];
1556                 
1557                 /* find vectors for two edges sharing the first vert */
1558                 VectorSubtract( tt.v[ 1 ].xyz, tt.v[ 0 ].xyz, tt.edge1 );
1559                 VectorSubtract( tt.v[ 2 ].xyz, tt.v[ 0 ].xyz, tt.edge2 );
1560                 
1561                 /* trace it */
1562                 if( TraceTriangle( &traceInfos[ tt.infoNum ], &tt, trace ) )
1563                         return qtrue;
1564         }
1565         
1566         /* done */
1567         return qfalse;
1568 }
1569
1570
1571
1572
1573 /*
1574 TraceLine_r()
1575 returns qtrue if something is hit and tracing can stop
1576 */
1577
1578 static qboolean TraceLine_r( int nodeNum, vec3_t origin, vec3_t end, trace_t *trace )
1579 {
1580         traceNode_t             *node;
1581         int                             side;
1582         float                   front, back, frac;
1583         vec3_t                  mid;
1584         qboolean                r;
1585
1586         
1587         /* bogus node number means solid, end tracing unless testing all */
1588         if( nodeNum < 0 )
1589         {
1590                 VectorCopy( origin, trace->hit );
1591                 trace->passSolid = qtrue;
1592                 return qtrue;
1593         }
1594         
1595         /* get node */
1596         node = &traceNodes[ nodeNum ];
1597         
1598         /* solid? */
1599         if( node->type == TRACE_LEAF_SOLID )
1600         {
1601                 VectorCopy( origin, trace->hit );
1602                 trace->passSolid = qtrue;
1603                 return qtrue;
1604         }
1605         
1606         /* leafnode? */
1607         if( node->type < 0 )
1608         {
1609                 /* note leaf and return */      
1610                 if( node->numItems > 0 && trace->numTestNodes < MAX_TRACE_TEST_NODES )
1611                         trace->testNodes[ trace->numTestNodes++ ] = nodeNum;
1612                 return qfalse;
1613         }
1614         
1615         /* ydnar 2003-09-07: don't test branches of the bsp with nothing in them when testall is enabled */
1616         if( trace->testAll && node->numItems == 0 )
1617                 return qfalse;
1618         
1619         /* classify beginning and end points */
1620         switch( node->type )
1621         {
1622                 case PLANE_X:
1623                         front = origin[ 0 ] - node->plane[ 3 ];
1624                         back = end[ 0 ] - node->plane[ 3 ];
1625                         break;
1626                 
1627                 case PLANE_Y:
1628                         front = origin[ 1 ] - node->plane[ 3 ];
1629                         back = end[ 1 ] - node->plane[ 3 ];
1630                         break;
1631                 
1632                 case PLANE_Z:
1633                         front = origin[ 2 ] - node->plane[ 3 ];
1634                         back = end[ 2 ] - node->plane[ 3 ];
1635                         break;
1636                 
1637                 default:
1638                         front = DotProduct( origin, node->plane ) - node->plane[ 3 ];
1639                         back = DotProduct( end, node->plane ) - node->plane[ 3 ];
1640                         break;
1641         }
1642         
1643         /* entirely in front side? */
1644         if( front >= -TRACE_ON_EPSILON && back >= -TRACE_ON_EPSILON )
1645                 return TraceLine_r( node->children[ 0 ], origin, end, trace );
1646         
1647         /* entirely on back side? */
1648         if( front < TRACE_ON_EPSILON && back < TRACE_ON_EPSILON )
1649                 return TraceLine_r( node->children[ 1 ], origin, end, trace );
1650         
1651         /* select side */
1652         side = front < 0;
1653         
1654         /* calculate intercept point */
1655         frac = front / (front - back);
1656         mid[ 0 ] = origin[ 0 ] + (end[ 0 ] - origin[ 0 ]) * frac;
1657         mid[ 1 ] = origin[ 1 ] + (end[ 1 ] - origin[ 1 ]) * frac;
1658         mid[ 2 ] = origin[ 2 ] + (end[ 2 ] - origin[ 2 ]) * frac;
1659         
1660         /* fixme: check inhibit radius, then solid nodes and ignore */
1661         
1662         /* set trace hit here */
1663         //%     VectorCopy( mid, trace->hit );
1664         
1665         /* trace first side */
1666         r = TraceLine_r( node->children[ side ], origin, mid, trace );
1667         if( r )
1668                 return r;
1669         
1670         /* trace other side */
1671         return TraceLine_r( node->children[ !side ], mid, end, trace );
1672 }
1673
1674
1675
1676 /*
1677 TraceLine() - ydnar
1678 rewrote this function a bit :)
1679 */
1680
1681 void TraceLine( trace_t *trace )
1682 {
1683         int                             i, j;
1684         traceNode_t             *node;
1685         traceTriangle_t *tt;
1686         traceInfo_t             *ti;
1687         
1688         
1689         /* setup output (note: this code assumes the input data is completely filled out) */
1690         trace->passSolid = qfalse;
1691         trace->opaque = qfalse;
1692         trace->compileFlags = 0;
1693         trace->numTestNodes = 0;
1694         
1695         /* early outs */
1696         if( !trace->recvShadows || !trace->testOcclusion || trace->distance <= 0.00001f )
1697                 return;
1698         
1699         /* trace through nodes */
1700         TraceLine_r( headNodeNum, trace->origin, trace->end, trace );
1701         if( trace->passSolid && !trace->testAll )
1702         {
1703                 trace->opaque = qtrue;
1704                 return;
1705         }
1706         
1707         /* skip surfaces? */
1708         if( noSurfaces )
1709                 return;
1710         
1711         /* testall means trace through sky */   
1712         if( trace->testAll && trace->numTestNodes < MAX_TRACE_TEST_NODES &&
1713                 trace->compileFlags & C_SKY &&
1714                 (trace->numSurfaces == 0 || surfaceInfos[ trace->surfaces[ 0 ] ].childSurfaceNum < 0) )
1715         {
1716                 //%     trace->testNodes[ trace->numTestNodes++ ] = skyboxNodeNum;
1717                 TraceLine_r( skyboxNodeNum, trace->origin, trace->end, trace );
1718         }
1719         
1720         /* walk node list */
1721         for( i = 0; i < trace->numTestNodes; i++ )
1722         {
1723                 /* get node */
1724                 node = &traceNodes[ trace->testNodes[ i ] ];
1725                 
1726                 /* walk node item list */
1727                 for( j = 0; j < node->numItems; j++ )
1728                 {
1729                         tt = &traceTriangles[ node->items[ j ] ];
1730                         ti = &traceInfos[ tt->infoNum ];
1731                         if( TraceTriangle( ti, tt, trace ) )
1732                                 return;
1733                         //%     if( TraceWinding( &traceWindings[ node->items[ j ] ], trace ) )
1734                         //%             return;
1735                 }
1736         }
1737 }
1738
1739
1740
1741 /*
1742 SetupTrace() - ydnar
1743 sets up certain trace values
1744 */
1745
1746 float SetupTrace( trace_t *trace )
1747 {
1748         VectorSubtract( trace->end, trace->origin, trace->displacement );
1749         trace->distance = VectorNormalize( trace->displacement, trace->direction );
1750         VectorCopy( trace->origin, trace->hit );
1751         return trace->distance;
1752 }