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