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 SURFACE_META_C
33
34
35
36 /* dependencies */
37 #include "q3map2.h"
38
39
40
41 #define LIGHTMAP_EXCEEDED -1
42 #define S_EXCEEDED -2
43 #define T_EXCEEDED -3
44 #define ST_EXCEEDED -4
45 #define UNSUITABLE_TRIANGLE -10
46 #define VERTS_EXCEEDED -1000
47 #define INDEXES_EXCEEDED -2000
48
49 #define GROW_META_VERTS 1024
50 #define GROW_META_TRIANGLES 1024
51
52 static int numMetaSurfaces, numPatchMetaSurfaces;
53
54 static int maxMetaVerts = 0;
55 static int numMetaVerts = 0;
56 static int firstSearchMetaVert = 0;
57 static bspDrawVert_t *metaVerts = NULL;
58
59 static int maxMetaTriangles = 0;
60 static int numMetaTriangles = 0;
61 static metaTriangle_t *metaTriangles = NULL;
62
63
64
65 /*
66 ClearMetaVertexes()
67 called before staring a new entity to clear out the triangle list
68 */
69
ClearMetaTriangles(void)70 void ClearMetaTriangles( void ){
71 numMetaVerts = 0;
72 numMetaTriangles = 0;
73 }
74
75
76
77 /*
78 FindMetaVertex()
79 finds a matching metavertex in the global list, returning its index
80 */
81
FindMetaVertex(bspDrawVert_t * src)82 static int FindMetaVertex( bspDrawVert_t *src ){
83 int i;
84 bspDrawVert_t *v, *temp;
85
86
87 /* try to find an existing drawvert */
88 for ( i = firstSearchMetaVert, v = &metaVerts[ i ]; i < numMetaVerts; i++, v++ )
89 {
90 if ( memcmp( src, v, sizeof( bspDrawVert_t ) ) == 0 ) {
91 return i;
92 }
93 }
94
95 /* enough space? */
96 if ( numMetaVerts >= maxMetaVerts ) {
97 /* reallocate more room */
98 maxMetaVerts += GROW_META_VERTS;
99 temp = safe_malloc( maxMetaVerts * sizeof( bspDrawVert_t ) );
100 if ( metaVerts != NULL ) {
101 memcpy( temp, metaVerts, numMetaVerts * sizeof( bspDrawVert_t ) );
102 free( metaVerts );
103 }
104 metaVerts = temp;
105 }
106
107 /* add the triangle */
108 memcpy( &metaVerts[ numMetaVerts ], src, sizeof( bspDrawVert_t ) );
109 numMetaVerts++;
110
111 /* return the count */
112 return ( numMetaVerts - 1 );
113 }
114
115
116
117 /*
118 AddMetaTriangle()
119 adds a new meta triangle, allocating more memory if necessary
120 */
121
AddMetaTriangle(void)122 static int AddMetaTriangle( void ){
123 metaTriangle_t *temp;
124
125
126 /* enough space? */
127 if ( numMetaTriangles >= maxMetaTriangles ) {
128 /* reallocate more room */
129 maxMetaTriangles += GROW_META_TRIANGLES;
130 temp = safe_malloc( maxMetaTriangles * sizeof( metaTriangle_t ) );
131 if ( metaTriangles != NULL ) {
132 memcpy( temp, metaTriangles, numMetaTriangles * sizeof( metaTriangle_t ) );
133 free( metaTriangles );
134 }
135 metaTriangles = temp;
136 }
137
138 /* increment and return */
139 numMetaTriangles++;
140 return numMetaTriangles - 1;
141 }
142
143
144
145 /*
146 FindMetaTriangle()
147 finds a matching metatriangle in the global list,
148 otherwise adds it and returns the index to the metatriangle
149 */
150
FindMetaTriangle(metaTriangle_t * src,bspDrawVert_t * a,bspDrawVert_t * b,bspDrawVert_t * c,int planeNum)151 int FindMetaTriangle( metaTriangle_t *src, bspDrawVert_t *a, bspDrawVert_t *b, bspDrawVert_t *c, int planeNum ){
152 int triIndex;
153 vec3_t dir;
154
155
156
157 /* detect degenerate triangles fixme: do something proper here */
158 VectorSubtract( a->xyz, b->xyz, dir );
159 if ( VectorLength( dir ) < 0.125f ) {
160 return -1;
161 }
162 VectorSubtract( b->xyz, c->xyz, dir );
163 if ( VectorLength( dir ) < 0.125f ) {
164 return -1;
165 }
166 VectorSubtract( c->xyz, a->xyz, dir );
167 if ( VectorLength( dir ) < 0.125f ) {
168 return -1;
169 }
170
171 /* find plane */
172 if ( planeNum >= 0 ) {
173 /* because of precision issues with small triangles, try to use the specified plane */
174 src->planeNum = planeNum;
175 VectorCopy( mapplanes[ planeNum ].normal, src->plane );
176 src->plane[ 3 ] = mapplanes[ planeNum ].dist;
177 }
178 else
179 {
180 /* calculate a plane from the triangle's points (and bail if a plane can't be constructed) */
181 src->planeNum = -1;
182 if ( PlaneFromPoints( src->plane, a->xyz, b->xyz, c->xyz ) == qfalse ) {
183 return -1;
184 }
185 }
186
187 /* ydnar 2002-10-03: repair any bogus normals (busted ase import kludge) */
188 if ( VectorLength( a->normal ) <= 0.0f ) {
189 VectorCopy( src->plane, a->normal );
190 }
191 if ( VectorLength( b->normal ) <= 0.0f ) {
192 VectorCopy( src->plane, b->normal );
193 }
194 if ( VectorLength( c->normal ) <= 0.0f ) {
195 VectorCopy( src->plane, c->normal );
196 }
197
198 /* ydnar 2002-10-04: set lightmap axis if not already set */
199 if ( !( src->si->compileFlags & C_VERTEXLIT ) &&
200 src->lightmapAxis[ 0 ] == 0.0f && src->lightmapAxis[ 1 ] == 0.0f && src->lightmapAxis[ 2 ] == 0.0f ) {
201 /* the shader can specify an explicit lightmap axis */
202 if ( src->si->lightmapAxis[ 0 ] || src->si->lightmapAxis[ 1 ] || src->si->lightmapAxis[ 2 ] ) {
203 VectorCopy( src->si->lightmapAxis, src->lightmapAxis );
204 }
205
206 /* new axis-finding code */
207 else{
208 CalcLightmapAxis( src->plane, src->lightmapAxis );
209 }
210 }
211
212 /* fill out the src triangle */
213 src->indexes[ 0 ] = FindMetaVertex( a );
214 src->indexes[ 1 ] = FindMetaVertex( b );
215 src->indexes[ 2 ] = FindMetaVertex( c );
216
217 /* try to find an existing triangle */
218 #ifdef USE_EXHAUSTIVE_SEARCH
219 {
220 int i;
221 metaTriangle_t *tri;
222
223
224 for ( i = 0, tri = metaTriangles; i < numMetaTriangles; i++, tri++ )
225 {
226 if ( memcmp( src, tri, sizeof( metaTriangle_t ) ) == 0 ) {
227 return i;
228 }
229 }
230 }
231 #endif
232
233 /* get a new triangle */
234 triIndex = AddMetaTriangle();
235
236 /* add the triangle */
237 memcpy( &metaTriangles[ triIndex ], src, sizeof( metaTriangle_t ) );
238
239 /* return the triangle index */
240 return triIndex;
241 }
242
243
244
245 /*
246 SurfaceToMetaTriangles()
247 converts a classified surface to metatriangles
248 */
249
SurfaceToMetaTriangles(mapDrawSurface_t * ds)250 static void SurfaceToMetaTriangles( mapDrawSurface_t *ds ){
251 int i;
252 metaTriangle_t src;
253 bspDrawVert_t a, b, c;
254
255
256 /* only handle certain types of surfaces */
257 if ( ds->type != SURFACE_FACE &&
258 ds->type != SURFACE_META &&
259 ds->type != SURFACE_FORCED_META &&
260 ds->type != SURFACE_DECAL ) {
261 return;
262 }
263
264 /* speed at the expense of memory */
265 firstSearchMetaVert = numMetaVerts;
266
267 /* only handle valid surfaces */
268 if ( ds->type != SURFACE_BAD && ds->numVerts >= 3 && ds->numIndexes >= 3 ) {
269 /* walk the indexes and create triangles */
270 for ( i = 0; i < ds->numIndexes; i += 3 )
271 {
272 /* sanity check the indexes */
273 if ( ds->indexes[ i ] == ds->indexes[ i + 1 ] ||
274 ds->indexes[ i ] == ds->indexes[ i + 2 ] ||
275 ds->indexes[ i + 1 ] == ds->indexes[ i + 2 ] ) {
276 //% Sys_Printf( "%d! ", ds->numVerts );
277 continue;
278 }
279
280 /* build a metatriangle */
281 src.si = ds->shaderInfo;
282 src.side = ( ds->sideRef != NULL ? ds->sideRef->side : NULL );
283 src.entityNum = ds->entityNum;
284 src.surfaceNum = ds->surfaceNum;
285 src.planeNum = ds->planeNum;
286 src.castShadows = ds->castShadows;
287 src.recvShadows = ds->recvShadows;
288 src.fogNum = ds->fogNum;
289 src.sampleSize = ds->sampleSize;
290 src.shadeAngleDegrees = ds->shadeAngleDegrees;
291 VectorCopy( ds->lightmapAxis, src.lightmapAxis );
292
293 /* copy drawverts */
294 memcpy( &a, &ds->verts[ ds->indexes[ i ] ], sizeof( a ) );
295 memcpy( &b, &ds->verts[ ds->indexes[ i + 1 ] ], sizeof( b ) );
296 memcpy( &c, &ds->verts[ ds->indexes[ i + 2 ] ], sizeof( c ) );
297 FindMetaTriangle( &src, &a, &b, &c, ds->planeNum );
298 }
299
300 /* add to count */
301 numMetaSurfaces++;
302 }
303
304 /* clear the surface (free verts and indexes, sets it to SURFACE_BAD) */
305 ClearSurface( ds );
306 }
307
308
309
310 /*
311 TriangulatePatchSurface()
312 creates triangles from a patch
313 */
314
TriangulatePatchSurface(entity_t * e,mapDrawSurface_t * ds)315 void TriangulatePatchSurface( entity_t *e, mapDrawSurface_t *ds ){
316 int iterations, x, y, pw[ 5 ], r;
317 mapDrawSurface_t *dsNew;
318 mesh_t src, *subdivided, *mesh;
319 int forcePatchMeta;
320 int patchQuality;
321 int patchSubdivision;
322
323 /* vortex: _patchMeta, _patchQuality, _patchSubdivide support */
324 forcePatchMeta = IntForKey( e, "_patchMeta" );
325 if ( !forcePatchMeta ) {
326 forcePatchMeta = IntForKey( e, "patchMeta" );
327 }
328 patchQuality = IntForKey( e, "_patchQuality" );
329 if ( !patchQuality ) {
330 patchQuality = IntForKey( e, "patchQuality" );
331 }
332 if ( !patchQuality ) {
333 patchQuality = 1.0;
334 }
335 patchSubdivision = IntForKey( e, "_patchSubdivide" );
336 if ( !patchSubdivision ) {
337 patchSubdivision = IntForKey( e, "patchSubdivide" );
338 }
339
340 /* try to early out */
341 if ( ds->numVerts == 0 || ds->type != SURFACE_PATCH || ( patchMeta == qfalse && !forcePatchMeta ) ) {
342 return;
343 }
344 /* make a mesh from the drawsurf */
345 src.width = ds->patchWidth;
346 src.height = ds->patchHeight;
347 src.verts = ds->verts;
348 //% subdivided = SubdivideMesh( src, 8, 999 );
349 if ( patchSubdivision ) {
350 iterations = IterationsForCurve( ds->longestCurve, patchSubdivision );
351 }
352 else{
353 iterations = IterationsForCurve( ds->longestCurve, patchSubdivisions / patchQuality );
354 }
355
356 subdivided = SubdivideMesh2( src, iterations ); //% ds->maxIterations
357
358 /* fit it to the curve and remove colinear verts on rows/columns */
359 PutMeshOnCurve( *subdivided );
360 mesh = RemoveLinearMeshColumnsRows( subdivided );
361 FreeMesh( subdivided );
362 //% MakeMeshNormals( mesh );
363
364 /* make a copy of the drawsurface */
365 dsNew = AllocDrawSurface( SURFACE_META );
366 memcpy( dsNew, ds, sizeof( *ds ) );
367
368 /* if the patch is nonsolid, then discard it */
369 if ( !( ds->shaderInfo->compileFlags & C_SOLID ) ) {
370 ClearSurface( ds );
371 }
372
373 /* set new pointer */
374 ds = dsNew;
375
376 /* basic transmogrification */
377 ds->type = SURFACE_META;
378 ds->numIndexes = 0;
379 ds->indexes = safe_malloc( mesh->width * mesh->height * 6 * sizeof( int ) );
380
381 /* copy the verts in */
382 ds->numVerts = ( mesh->width * mesh->height );
383 ds->verts = mesh->verts;
384
385 /* iterate through the mesh quads */
386 for ( y = 0; y < ( mesh->height - 1 ); y++ )
387 {
388 for ( x = 0; x < ( mesh->width - 1 ); x++ )
389 {
390 /* set indexes */
391 pw[ 0 ] = x + ( y * mesh->width );
392 pw[ 1 ] = x + ( ( y + 1 ) * mesh->width );
393 pw[ 2 ] = x + 1 + ( ( y + 1 ) * mesh->width );
394 pw[ 3 ] = x + 1 + ( y * mesh->width );
395 pw[ 4 ] = x + ( y * mesh->width ); /* same as pw[ 0 ] */
396
397 /* set radix */
398 r = ( x + y ) & 1;
399
400 /* make first triangle */
401 ds->indexes[ ds->numIndexes++ ] = pw[ r + 0 ];
402 ds->indexes[ ds->numIndexes++ ] = pw[ r + 1 ];
403 ds->indexes[ ds->numIndexes++ ] = pw[ r + 2 ];
404
405 /* make second triangle */
406 ds->indexes[ ds->numIndexes++ ] = pw[ r + 0 ];
407 ds->indexes[ ds->numIndexes++ ] = pw[ r + 2 ];
408 ds->indexes[ ds->numIndexes++ ] = pw[ r + 3 ];
409 }
410 }
411
412 /* free the mesh, but not the verts */
413 free( mesh );
414
415 /* add to count */
416 numPatchMetaSurfaces++;
417
418 /* classify it */
419 ClassifySurfaces( 1, ds );
420 }
421
422 #define TINY_AREA 1.0f
423 #define MAXAREA_MAXTRIES 8
MaxAreaIndexes(bspDrawVert_t * vert,int cnt,int * indexes)424 int MaxAreaIndexes( bspDrawVert_t *vert, int cnt, int *indexes ){
425 int r, s, t, bestR = 0, bestS = 1, bestT = 2;
426 int i, j, try;
427 double A, bestA = -1, V, bestV = -1;
428 vec3_t ab, ac, bc, cross;
429 bspDrawVert_t *buf;
430 double shiftWidth;
431
432 if ( cnt < 3 ) {
433 return 0;
434 }
435
436 /* calculate total area */
437 A = 0;
438 for ( i = 1; i + 1 < cnt; ++i )
439 {
440 VectorSubtract( vert[i].xyz, vert[0].xyz, ab );
441 VectorSubtract( vert[i + 1].xyz, vert[0].xyz, ac );
442 CrossProduct( ab, ac, cross );
443 A += VectorLength( cross );
444 }
445 V = 0;
446 for ( i = 0; i < cnt; ++i )
447 {
448 VectorSubtract( vert[( i + 1 ) % cnt].xyz, vert[i].xyz, ab );
449 V += VectorLength( ab );
450 }
451
452 /* calculate shift width from the area sensibly, assuming the polygon
453 * fits about 25% of the screen in both dimensions
454 * we assume 1280x1024
455 * 1 pixel is then about sqrt(A) / (0.25 * screenwidth)
456 * 8 pixels are then about sqrt(A) / (0.25 * 1280) * 8
457 * 8 pixels are then about sqrt(A) * 0.025
458 * */
459 shiftWidth = sqrt( A ) * 0.0125;
460 /* 3->1 6->2 12->3 ... */
461 if ( A - ceil( log( cnt / 1.5 ) / log( 2 ) ) * V * shiftWidth * 2 < 0 ) {
462 /* printf("Small triangle detected (area %f, circumference %f), adjusting shiftWidth from %f to ", A, V, shiftWidth); */
463 shiftWidth = A / ( ceil( log( cnt / 1.5 ) / log( 2 ) ) * V * 2 );
464 /* printf("%f\n", shiftWidth); */
465 }
466
467 /* find the triangle with highest area */
468 for ( r = 0; r + 2 < cnt; ++r )
469 for ( s = r + 1; s + 1 < cnt; ++s )
470 for ( t = s + 1; t < cnt; ++t )
471 {
472 VectorSubtract( vert[s].xyz, vert[r].xyz, ab );
473 VectorSubtract( vert[t].xyz, vert[r].xyz, ac );
474 VectorSubtract( vert[t].xyz, vert[s].xyz, bc );
475 CrossProduct( ab, ac, cross );
476 A = VectorLength( cross );
477
478 V = A - ( VectorLength( ab ) - VectorLength( ac ) - VectorLength( bc ) ) * shiftWidth;
479 /* value = A - circumference * shiftWidth, i.e. we back out by shiftWidth units from each side, to prevent too acute triangles */
480 /* this kind of simulates "number of shiftWidth*shiftWidth fragments in the triangle not touched by an edge" */
481
482 if ( bestA < 0 || V > bestV ) {
483 bestA = A;
484 bestV = V;
485 bestR = r;
486 bestS = s;
487 bestT = t;
488 }
489 }
490
491 /*
492 if(bestV < 0)
493 printf("value was REALLY bad\n");
494 */
495
496 for ( try = 0; try < MAXAREA_MAXTRIES; ++try )
497 {
498 if ( try ) {
499 bestR = rand() % cnt;
500 bestS = rand() % cnt;
501 bestT = rand() % cnt;
502 if ( bestR == bestS || bestR == bestT || bestS == bestT ) {
503 continue;
504 }
505 // bubblesort inline
506 // abc acb bac bca cab cba
507 if ( bestR > bestS ) {
508 j = bestR;
509 bestR = bestS;
510 bestS = j;
511 }
512 // abc acb abc bca acb bca
513 if ( bestS > bestT ) {
514 j = bestS;
515 bestS = bestT;
516 bestT = j;
517 }
518 // abc abc abc bac abc bac
519 if ( bestR > bestS ) {
520 j = bestR;
521 bestR = bestS;
522 bestS = j;
523 }
524 // abc abc abc abc abc abc
525
526 VectorSubtract( vert[bestS].xyz, vert[bestR].xyz, ab );
527 VectorSubtract( vert[bestT].xyz, vert[bestR].xyz, ac );
528 CrossProduct( ab, ac, cross );
529 bestA = VectorLength( cross );
530 }
531
532 if ( bestA < TINY_AREA ) {
533 /* the biggest triangle is degenerate - then every other is too, and the other algorithms wouldn't generate anything useful either */
534 continue;
535 }
536
537 i = 0;
538 indexes[i++] = bestR;
539 indexes[i++] = bestS;
540 indexes[i++] = bestT;
541 /* uses 3 */
542
543 /* identify the other fragments */
544
545 /* full polygon without triangle (bestR,bestS,bestT) = three new polygons:
546 * 1. bestR..bestS
547 * 2. bestS..bestT
548 * 3. bestT..bestR
549 */
550
551 j = MaxAreaIndexes( vert + bestR, bestS - bestR + 1, indexes + i );
552 if ( j < 0 ) {
553 continue;
554 }
555 j += i;
556 for (; i < j; ++i )
557 indexes[i] += bestR;
558 /* uses 3*(bestS-bestR+1)-6 */
559 j = MaxAreaIndexes( vert + bestS, bestT - bestS + 1, indexes + i );
560 if ( j < 0 ) {
561 continue;
562 }
563 j += i;
564 for (; i < j; ++i )
565 indexes[i] += bestS;
566 /* uses 3*(bestT-bestS+1)-6 */
567
568 /* can'bestT recurse this one directly... therefore, buffering */
569 if ( cnt + bestR - bestT + 1 >= 3 ) {
570 buf = safe_malloc( sizeof( *vert ) * ( cnt + bestR - bestT + 1 ) );
571 memcpy( buf, vert + bestT, sizeof( *vert ) * ( cnt - bestT ) );
572 memcpy( buf + ( cnt - bestT ), vert, sizeof( *vert ) * ( bestR + 1 ) );
573 j = MaxAreaIndexes( buf, cnt + bestR - bestT + 1, indexes + i );
574 if ( j < 0 ) {
575 free( buf );
576 continue;
577 }
578 j += i;
579 for (; i < j; ++i )
580 indexes[i] = ( indexes[i] + bestT ) % cnt;
581 /* uses 3*(cnt+bestR-bestT+1)-6 */
582 free( buf );
583 }
584
585 /* together 3 + 3*(cnt+3) - 18 = 3*cnt-6 q.e.d. */
586 return i;
587 }
588
589 return -1;
590 }
591
592 /*
593 MaxAreaFaceSurface() - divVerent
594 creates a triangle list using max area indexes
595 */
596
MaxAreaFaceSurface(mapDrawSurface_t * ds)597 void MaxAreaFaceSurface( mapDrawSurface_t *ds ){
598 int n;
599 /* try to early out */
600 if ( !ds->numVerts || ( ds->type != SURFACE_FACE && ds->type != SURFACE_DECAL ) ) {
601 return;
602 }
603
604 /* is this a simple triangle? */
605 if ( ds->numVerts == 3 ) {
606 ds->numIndexes = 3;
607 ds->indexes = safe_malloc( ds->numIndexes * sizeof( int ) );
608 VectorSet( ds->indexes, 0, 1, 2 );
609 numMaxAreaSurfaces++;
610 return;
611 }
612
613 /* do it! */
614 ds->numIndexes = 3 * ds->numVerts - 6;
615 ds->indexes = safe_malloc( ds->numIndexes * sizeof( int ) );
616 n = MaxAreaIndexes( ds->verts, ds->numVerts, ds->indexes );
617 if ( n < 0 ) {
618 /* whatever we do, it's degenerate */
619 free( ds->indexes );
620 ds->numIndexes = 0;
621 StripFaceSurface( ds );
622 return;
623 }
624 ds->numIndexes = n;
625
626 /* add to count */
627 numMaxAreaSurfaces++;
628
629 /* classify it */
630 ClassifySurfaces( 1, ds );
631 }
632
633
634 /*
635 FanFaceSurface() - ydnar
636 creates a tri-fan from a brush face winding
637 loosely based on SurfaceAsTriFan()
638 */
639
FanFaceSurface(mapDrawSurface_t * ds)640 void FanFaceSurface( mapDrawSurface_t *ds ){
641 int i, j, k, a, b, c, color[ MAX_LIGHTMAPS ][ 4 ];
642 bspDrawVert_t *verts, *centroid, *dv;
643 double iv;
644
645
646 /* try to early out */
647 if ( !ds->numVerts || ( ds->type != SURFACE_FACE && ds->type != SURFACE_DECAL ) ) {
648 return;
649 }
650
651 /* add a new vertex at the beginning of the surface */
652 verts = safe_malloc( ( ds->numVerts + 1 ) * sizeof( bspDrawVert_t ) );
653 memset( verts, 0, sizeof( bspDrawVert_t ) );
654 memcpy( &verts[ 1 ], ds->verts, ds->numVerts * sizeof( bspDrawVert_t ) );
655 free( ds->verts );
656 ds->verts = verts;
657
658 /* add up the drawverts to create a centroid */
659 centroid = &verts[ 0 ];
660 memset( color, 0, 4 * MAX_LIGHTMAPS * sizeof( int ) );
661 for ( i = 1, dv = &verts[ 1 ]; i < ( ds->numVerts + 1 ); i++, dv++ )
662 {
663 VectorAdd( centroid->xyz, dv->xyz, centroid->xyz );
664 VectorAdd( centroid->normal, dv->normal, centroid->normal );
665 for ( j = 0; j < 4; j++ )
666 {
667 for ( k = 0; k < MAX_LIGHTMAPS; k++ )
668 color[ k ][ j ] += dv->color[ k ][ j ];
669 if ( j < 2 ) {
670 centroid->st[ j ] += dv->st[ j ];
671 for ( k = 0; k < MAX_LIGHTMAPS; k++ )
672 centroid->lightmap[ k ][ j ] += dv->lightmap[ k ][ j ];
673 }
674 }
675 }
676
677 /* average the centroid */
678 iv = 1.0f / ds->numVerts;
679 VectorScale( centroid->xyz, iv, centroid->xyz );
680 if ( VectorNormalize( centroid->normal, centroid->normal ) <= 0 ) {
681 VectorCopy( verts[ 1 ].normal, centroid->normal );
682 }
683 for ( j = 0; j < 4; j++ )
684 {
685 for ( k = 0; k < MAX_LIGHTMAPS; k++ )
686 {
687 color[ k ][ j ] /= ds->numVerts;
688 centroid->color[ k ][ j ] = ( color[ k ][ j ] < 255.0f ? color[ k ][ j ] : 255 );
689 }
690 if ( j < 2 ) {
691 centroid->st[ j ] *= iv;
692 for ( k = 0; k < MAX_LIGHTMAPS; k++ )
693 centroid->lightmap[ k ][ j ] *= iv;
694 }
695 }
696
697 /* add to vert count */
698 ds->numVerts++;
699
700 /* fill indexes in triangle fan order */
701 ds->numIndexes = 0;
702 ds->indexes = safe_malloc( ds->numVerts * 3 * sizeof( int ) );
703 for ( i = 1; i < ds->numVerts; i++ )
704 {
705 a = 0;
706 b = i;
707 c = ( i + 1 ) % ds->numVerts;
708 c = c ? c : 1;
709 ds->indexes[ ds->numIndexes++ ] = a;
710 ds->indexes[ ds->numIndexes++ ] = b;
711 ds->indexes[ ds->numIndexes++ ] = c;
712 }
713
714 /* add to count */
715 numFanSurfaces++;
716
717 /* classify it */
718 ClassifySurfaces( 1, ds );
719 }
720
721
722
723 /*
724 StripFaceSurface() - ydnar
725 attempts to create a valid tri-strip w/o degenerate triangles from a brush face winding
726 based on SurfaceAsTriStrip()
727 */
728
729 #define MAX_INDEXES 1024
730
StripFaceSurface(mapDrawSurface_t * ds)731 void StripFaceSurface( mapDrawSurface_t *ds ){
732 int i, r, least, rotate, numIndexes, ni, a, b, c, indexes[ MAX_INDEXES ];
733 vec_t *v1, *v2;
734
735
736 /* try to early out */
737 if ( !ds->numVerts || ( ds->type != SURFACE_FACE && ds->type != SURFACE_DECAL ) ) {
738 return;
739 }
740
741 /* is this a simple triangle? */
742 if ( ds->numVerts == 3 ) {
743 numIndexes = 3;
744 VectorSet( indexes, 0, 1, 2 );
745 }
746 else
747 {
748 /* ydnar: find smallest coordinate */
749 least = 0;
750 if ( ds->shaderInfo != NULL && ds->shaderInfo->autosprite == qfalse ) {
751 for ( i = 0; i < ds->numVerts; i++ )
752 {
753 /* get points */
754 v1 = ds->verts[ i ].xyz;
755 v2 = ds->verts[ least ].xyz;
756
757 /* compare */
758 if ( v1[ 0 ] < v2[ 0 ] ||
759 ( v1[ 0 ] == v2[ 0 ] && v1[ 1 ] < v2[ 1 ] ) ||
760 ( v1[ 0 ] == v2[ 0 ] && v1[ 1 ] == v2[ 1 ] && v1[ 2 ] < v2[ 2 ] ) ) {
761 least = i;
762 }
763 }
764 }
765
766 /* determine the triangle strip order */
767 numIndexes = ( ds->numVerts - 2 ) * 3;
768 if ( numIndexes > MAX_INDEXES ) {
769 Error( "MAX_INDEXES exceeded for surface (%d > %d) (%d verts)", numIndexes, MAX_INDEXES, ds->numVerts );
770 }
771
772 /* try all possible orderings of the points looking for a non-degenerate strip order */
773 ni = 0;
774 for ( r = 0; r < ds->numVerts; r++ )
775 {
776 /* set rotation */
777 rotate = ( r + least ) % ds->numVerts;
778
779 /* walk the winding in both directions */
780 for ( ni = 0, i = 0; i < ds->numVerts - 2 - i; i++ )
781 {
782 /* make indexes */
783 a = ( ds->numVerts - 1 - i + rotate ) % ds->numVerts;
784 b = ( i + rotate ) % ds->numVerts;
785 c = ( ds->numVerts - 2 - i + rotate ) % ds->numVerts;
786
787 /* test this triangle */
788 if ( ds->numVerts > 4 && IsTriangleDegenerate( ds->verts, a, b, c ) ) {
789 break;
790 }
791 indexes[ ni++ ] = a;
792 indexes[ ni++ ] = b;
793 indexes[ ni++ ] = c;
794
795 /* handle end case */
796 if ( i + 1 != ds->numVerts - 1 - i ) {
797 /* make indexes */
798 a = ( ds->numVerts - 2 - i + rotate ) % ds->numVerts;
799 b = ( i + rotate ) % ds->numVerts;
800 c = ( i + 1 + rotate ) % ds->numVerts;
801
802 /* test triangle */
803 if ( ds->numVerts > 4 && IsTriangleDegenerate( ds->verts, a, b, c ) ) {
804 break;
805 }
806 indexes[ ni++ ] = a;
807 indexes[ ni++ ] = b;
808 indexes[ ni++ ] = c;
809 }
810 }
811
812 /* valid strip? */
813 if ( ni == numIndexes ) {
814 break;
815 }
816 }
817
818 /* if any triangle in the strip is degenerate, render from a centered fan point instead */
819 if ( ni < numIndexes ) {
820 FanFaceSurface( ds );
821 return;
822 }
823 }
824
825 /* copy strip triangle indexes */
826 ds->numIndexes = numIndexes;
827 ds->indexes = safe_malloc( ds->numIndexes * sizeof( int ) );
828 memcpy( ds->indexes, indexes, ds->numIndexes * sizeof( int ) );
829
830 /* add to count */
831 numStripSurfaces++;
832
833 /* classify it */
834 ClassifySurfaces( 1, ds );
835 }
836
837
838 /*
839 EmitMetaStatictics
840 vortex: prints meta statistics in general output
841 */
842
EmitMetaStats()843 void EmitMetaStats(){
844 Sys_Printf( "--- EmitMetaStats ---\n" );
845 Sys_Printf( "%9d total meta surfaces\n", numMetaSurfaces );
846 Sys_Printf( "%9d stripped surfaces\n", numStripSurfaces );
847 Sys_Printf( "%9d fanned surfaces\n", numFanSurfaces );
848 Sys_Printf( "%9d maxarea'd surfaces\n", numMaxAreaSurfaces );
849 Sys_Printf( "%9d patch meta surfaces\n", numPatchMetaSurfaces );
850 Sys_Printf( "%9d meta verts\n", numMetaVerts );
851 Sys_Printf( "%9d meta triangles\n", numMetaTriangles );
852 }
853
854 /*
855 MakeEntityMetaTriangles()
856 builds meta triangles from brush faces (tristrips and fans)
857 */
858
MakeEntityMetaTriangles(entity_t * e)859 void MakeEntityMetaTriangles( entity_t *e ){
860 int i, f, fOld, start;
861 mapDrawSurface_t *ds;
862
863
864 /* note it */
865 Sys_FPrintf( SYS_VRB, "--- MakeEntityMetaTriangles ---\n" );
866
867 /* init pacifier */
868 fOld = -1;
869 start = I_FloatTime();
870
871 /* walk the list of surfaces in the entity */
872 for ( i = e->firstDrawSurf; i < numMapDrawSurfs; i++ )
873 {
874 /* print pacifier */
875 f = 10 * ( i - e->firstDrawSurf ) / ( numMapDrawSurfs - e->firstDrawSurf );
876 if ( f != fOld ) {
877 fOld = f;
878 Sys_FPrintf( SYS_VRB, "%d...", f );
879 }
880
881 /* get surface */
882 ds = &mapDrawSurfs[ i ];
883 if ( ds->numVerts <= 0 ) {
884 continue;
885 }
886
887 /* ignore autosprite surfaces */
888 if ( ds->shaderInfo->autosprite ) {
889 continue;
890 }
891
892 /* meta this surface? */
893 if ( meta == qfalse && ds->shaderInfo->forceMeta == qfalse ) {
894 continue;
895 }
896
897 /* switch on type */
898 switch ( ds->type )
899 {
900 case SURFACE_FACE:
901 case SURFACE_DECAL:
902 if ( maxAreaFaceSurface ) {
903 MaxAreaFaceSurface( ds );
904 }
905 else{
906 StripFaceSurface( ds );
907 }
908 SurfaceToMetaTriangles( ds );
909 break;
910
911 case SURFACE_PATCH:
912 TriangulatePatchSurface( e, ds );
913 break;
914
915 case SURFACE_TRIANGLES:
916 break;
917
918 case SURFACE_FORCED_META:
919 case SURFACE_META:
920 SurfaceToMetaTriangles( ds );
921 break;
922
923 default:
924 break;
925 }
926 }
927
928 /* print time */
929 if ( ( numMapDrawSurfs - e->firstDrawSurf ) ) {
930 Sys_FPrintf( SYS_VRB, " (%d)\n", (int) ( I_FloatTime() - start ) );
931 }
932
933 /* emit some stats */
934 Sys_FPrintf( SYS_VRB, "%9d total meta surfaces\n", numMetaSurfaces );
935 Sys_FPrintf( SYS_VRB, "%9d stripped surfaces\n", numStripSurfaces );
936 Sys_FPrintf( SYS_VRB, "%9d fanned surfaces\n", numFanSurfaces );
937 Sys_FPrintf( SYS_VRB, "%9d maxarea'd surfaces\n", numMaxAreaSurfaces );
938 Sys_FPrintf( SYS_VRB, "%9d patch meta surfaces\n", numPatchMetaSurfaces );
939 Sys_FPrintf( SYS_VRB, "%9d meta verts\n", numMetaVerts );
940 Sys_FPrintf( SYS_VRB, "%9d meta triangles\n", numMetaTriangles );
941
942 /* tidy things up */
943 TidyEntitySurfaces( e );
944 }
945
946
947
948 /*
949 CreateEdge()
950 sets up an edge structure from a plane and 2 points that the edge ab falls lies in
951 */
952
953 typedef struct edge_s
954 {
955 vec3_t origin, edge;
956 vec_t length, kingpinLength;
957 int kingpin;
958 vec4_t plane;
959 }
960 edge_t;
961
CreateEdge(vec4_t plane,vec3_t a,vec3_t b,edge_t * edge)962 void CreateEdge( vec4_t plane, vec3_t a, vec3_t b, edge_t *edge ){
963 /* copy edge origin */
964 VectorCopy( a, edge->origin );
965
966 /* create vector aligned with winding direction of edge */
967 VectorSubtract( b, a, edge->edge );
968
969 if ( fabs( edge->edge[ 0 ] ) > fabs( edge->edge[ 1 ] ) && fabs( edge->edge[ 0 ] ) > fabs( edge->edge[ 2 ] ) ) {
970 edge->kingpin = 0;
971 }
972 else if ( fabs( edge->edge[ 1 ] ) > fabs( edge->edge[ 0 ] ) && fabs( edge->edge[ 1 ] ) > fabs( edge->edge[ 2 ] ) ) {
973 edge->kingpin = 1;
974 }
975 else{
976 edge->kingpin = 2;
977 }
978 edge->kingpinLength = edge->edge[ edge->kingpin ];
979
980 VectorNormalize( edge->edge, edge->edge );
981 edge->edge[ 3 ] = DotProduct( a, edge->edge );
982 edge->length = DotProduct( b, edge->edge ) - edge->edge[ 3 ];
983
984 /* create perpendicular plane that edge lies in */
985 CrossProduct( plane, edge->edge, edge->plane );
986 edge->plane[ 3 ] = DotProduct( a, edge->plane );
987 }
988
989
990
991 /*
992 FixMetaTJunctions()
993 fixes t-junctions on meta triangles
994 */
995
996 #define TJ_PLANE_EPSILON ( 1.0f / 8.0f )
997 #define TJ_EDGE_EPSILON ( 1.0f / 8.0f )
998 #define TJ_POINT_EPSILON ( 1.0f / 8.0f )
999
FixMetaTJunctions(void)1000 void FixMetaTJunctions( void ){
1001 int i, j, k, f, fOld, start, vertIndex, triIndex, numTJuncs;
1002 metaTriangle_t *tri, *newTri;
1003 shaderInfo_t *si;
1004 bspDrawVert_t *a, *b, *c, junc;
1005 float dist, amount;
1006 vec3_t pt;
1007 vec4_t plane;
1008 edge_t edges[ 3 ];
1009
1010
1011 /* this code is crap; revisit later */
1012 return;
1013
1014 /* note it */
1015 Sys_FPrintf( SYS_VRB, "--- FixMetaTJunctions ---\n" );
1016
1017 /* init pacifier */
1018 fOld = -1;
1019 start = I_FloatTime();
1020
1021 /* walk triangle list */
1022 numTJuncs = 0;
1023 for ( i = 0; i < numMetaTriangles; i++ )
1024 {
1025 /* get triangle */
1026 tri = &metaTriangles[ i ];
1027
1028 /* print pacifier */
1029 f = 10 * i / numMetaTriangles;
1030 if ( f != fOld ) {
1031 fOld = f;
1032 Sys_FPrintf( SYS_VRB, "%d...", f );
1033 }
1034
1035 /* attempt to early out */
1036 si = tri->si;
1037 if ( ( si->compileFlags & C_NODRAW ) || si->autosprite || si->notjunc ) {
1038 continue;
1039 }
1040
1041 /* calculate planes */
1042 VectorCopy( tri->plane, plane );
1043 plane[ 3 ] = tri->plane[ 3 ];
1044 CreateEdge( plane, metaVerts[ tri->indexes[ 0 ] ].xyz, metaVerts[ tri->indexes[ 1 ] ].xyz, &edges[ 0 ] );
1045 CreateEdge( plane, metaVerts[ tri->indexes[ 1 ] ].xyz, metaVerts[ tri->indexes[ 2 ] ].xyz, &edges[ 1 ] );
1046 CreateEdge( plane, metaVerts[ tri->indexes[ 2 ] ].xyz, metaVerts[ tri->indexes[ 0 ] ].xyz, &edges[ 2 ] );
1047
1048 /* walk meta vert list */
1049 for ( j = 0; j < numMetaVerts; j++ )
1050 {
1051 /* get vert */
1052 VectorCopy( metaVerts[ j ].xyz, pt );
1053
1054 /* determine if point lies in the triangle's plane */
1055 dist = DotProduct( pt, plane ) - plane[ 3 ];
1056 if ( fabs( dist ) > TJ_PLANE_EPSILON ) {
1057 continue;
1058 }
1059
1060 /* skip this point if it already exists in the triangle */
1061 for ( k = 0; k < 3; k++ )
1062 {
1063 if ( fabs( pt[ 0 ] - metaVerts[ tri->indexes[ k ] ].xyz[ 0 ] ) <= TJ_POINT_EPSILON &&
1064 fabs( pt[ 1 ] - metaVerts[ tri->indexes[ k ] ].xyz[ 1 ] ) <= TJ_POINT_EPSILON &&
1065 fabs( pt[ 2 ] - metaVerts[ tri->indexes[ k ] ].xyz[ 2 ] ) <= TJ_POINT_EPSILON ) {
1066 break;
1067 }
1068 }
1069 if ( k < 3 ) {
1070 continue;
1071 }
1072
1073 /* walk edges */
1074 for ( k = 0; k < 3; k++ )
1075 {
1076 /* ignore bogus edges */
1077 if ( fabs( edges[ k ].kingpinLength ) < TJ_EDGE_EPSILON ) {
1078 continue;
1079 }
1080
1081 /* determine if point lies on the edge */
1082 dist = DotProduct( pt, edges[ k ].plane ) - edges[ k ].plane[ 3 ];
1083 if ( fabs( dist ) > TJ_EDGE_EPSILON ) {
1084 continue;
1085 }
1086
1087 /* determine how far along the edge the point lies */
1088 amount = ( pt[ edges[ k ].kingpin ] - edges[ k ].origin[ edges[ k ].kingpin ] ) / edges[ k ].kingpinLength;
1089 if ( amount <= 0.0f || amount >= 1.0f ) {
1090 continue;
1091 }
1092
1093 #if 0
1094 dist = DotProduct( pt, edges[ k ].edge ) - edges[ k ].edge[ 3 ];
1095 if ( dist <= -0.0f || dist >= edges[ k ].length ) {
1096 continue;
1097 }
1098 amount = dist / edges[ k ].length;
1099 #endif
1100
1101 /* the edge opposite the zero-weighted vertex was hit, so use that as an amount */
1102 a = &metaVerts[ tri->indexes[ k % 3 ] ];
1103 b = &metaVerts[ tri->indexes[ ( k + 1 ) % 3 ] ];
1104 c = &metaVerts[ tri->indexes[ ( k + 2 ) % 3 ] ];
1105
1106 /* make new vert */
1107 LerpDrawVertAmount( a, b, amount, &junc );
1108 VectorCopy( pt, junc.xyz );
1109
1110 /* compare against existing verts */
1111 if ( VectorCompare( junc.xyz, a->xyz ) || VectorCompare( junc.xyz, b->xyz ) || VectorCompare( junc.xyz, c->xyz ) ) {
1112 continue;
1113 }
1114
1115 /* see if we can just re-use the existing vert */
1116 if ( !memcmp( &metaVerts[ j ], &junc, sizeof( junc ) ) ) {
1117 vertIndex = j;
1118 }
1119 else
1120 {
1121 /* find new vertex (note: a and b are invalid pointers after this) */
1122 firstSearchMetaVert = numMetaVerts;
1123 vertIndex = FindMetaVertex( &junc );
1124 if ( vertIndex < 0 ) {
1125 continue;
1126 }
1127 }
1128
1129 /* make new triangle */
1130 triIndex = AddMetaTriangle();
1131 if ( triIndex < 0 ) {
1132 continue;
1133 }
1134
1135 /* get triangles */
1136 tri = &metaTriangles[ i ];
1137 newTri = &metaTriangles[ triIndex ];
1138
1139 /* copy the triangle */
1140 memcpy( newTri, tri, sizeof( *tri ) );
1141
1142 /* fix verts */
1143 tri->indexes[ ( k + 1 ) % 3 ] = vertIndex;
1144 newTri->indexes[ k ] = vertIndex;
1145
1146 /* recalculate edges */
1147 CreateEdge( plane, metaVerts[ tri->indexes[ 0 ] ].xyz, metaVerts[ tri->indexes[ 1 ] ].xyz, &edges[ 0 ] );
1148 CreateEdge( plane, metaVerts[ tri->indexes[ 1 ] ].xyz, metaVerts[ tri->indexes[ 2 ] ].xyz, &edges[ 1 ] );
1149 CreateEdge( plane, metaVerts[ tri->indexes[ 2 ] ].xyz, metaVerts[ tri->indexes[ 0 ] ].xyz, &edges[ 2 ] );
1150
1151 /* debug code */
1152 metaVerts[ vertIndex ].color[ 0 ][ 0 ] = 255;
1153 metaVerts[ vertIndex ].color[ 0 ][ 1 ] = 204;
1154 metaVerts[ vertIndex ].color[ 0 ][ 2 ] = 0;
1155
1156 /* add to counter and end processing of this vert */
1157 numTJuncs++;
1158 break;
1159 }
1160 }
1161 }
1162
1163 /* print time */
1164 Sys_FPrintf( SYS_VRB, " (%d)\n", (int) ( I_FloatTime() - start ) );
1165
1166 /* emit some stats */
1167 Sys_FPrintf( SYS_VRB, "%9d T-junctions added\n", numTJuncs );
1168 }
1169
1170
1171
1172 /*
1173 SmoothMetaTriangles()
1174 averages coincident vertex normals in the meta triangles
1175 */
1176
1177 #define MAX_SAMPLES 256
1178 #define THETA_EPSILON 0.000001
1179 #define EQUAL_NORMAL_EPSILON 0.01
1180
SmoothMetaTriangles(void)1181 void SmoothMetaTriangles( void ){
1182 int i, j, k, f, fOld, start, cs, numVerts, numVotes, numSmoothed;
1183 float shadeAngle, defaultShadeAngle, maxShadeAngle, dot, testAngle;
1184 metaTriangle_t *tri;
1185 float *shadeAngles;
1186 byte *smoothed;
1187 vec3_t average, diff;
1188 int indexes[ MAX_SAMPLES ];
1189 vec3_t votes[ MAX_SAMPLES ];
1190
1191 /* note it */
1192 Sys_FPrintf( SYS_VRB, "--- SmoothMetaTriangles ---\n" );
1193
1194 /* allocate shade angle table */
1195 shadeAngles = safe_malloc( numMetaVerts * sizeof( float ) );
1196 memset( shadeAngles, 0, numMetaVerts * sizeof( float ) );
1197
1198 /* allocate smoothed table */
1199 cs = ( numMetaVerts / 8 ) + 1;
1200 smoothed = safe_malloc( cs );
1201 memset( smoothed, 0, cs );
1202
1203 /* set default shade angle */
1204 defaultShadeAngle = DEG2RAD( npDegrees );
1205 maxShadeAngle = 0.0f;
1206
1207 /* run through every surface and flag verts belonging to non-lightmapped surfaces
1208 and set per-vertex smoothing angle */
1209 for ( i = 0, tri = &metaTriangles[ i ]; i < numMetaTriangles; i++, tri++ )
1210 {
1211 shadeAngle = defaultShadeAngle;
1212
1213 /* get shade angle from shader */
1214 if ( tri->si->shadeAngleDegrees > 0.0f ) {
1215 shadeAngle = DEG2RAD( tri->si->shadeAngleDegrees );
1216 }
1217 /* get shade angle from entity */
1218 else if ( tri->shadeAngleDegrees > 0.0f ) {
1219 shadeAngle = DEG2RAD( tri->shadeAngleDegrees );
1220 }
1221
1222 if ( shadeAngle <= 0.0f ) {
1223 shadeAngle = defaultShadeAngle;
1224 }
1225
1226 if ( shadeAngle > maxShadeAngle ) {
1227 maxShadeAngle = shadeAngle;
1228 }
1229
1230 /* flag its verts */
1231 for ( j = 0; j < 3; j++ )
1232 {
1233 shadeAngles[ tri->indexes[ j ] ] = shadeAngle;
1234 if ( shadeAngle <= 0 ) {
1235 smoothed[ tri->indexes[ j ] >> 3 ] |= ( 1 << ( tri->indexes[ j ] & 7 ) );
1236 }
1237 }
1238 }
1239
1240 /* bail if no surfaces have a shade angle */
1241 if ( maxShadeAngle <= 0 ) {
1242 Sys_FPrintf( SYS_VRB, "No smoothing angles specified, aborting\n" );
1243 free( shadeAngles );
1244 free( smoothed );
1245 return;
1246 }
1247
1248 /* init pacifier */
1249 fOld = -1;
1250 start = I_FloatTime();
1251
1252 /* go through the list of vertexes */
1253 numSmoothed = 0;
1254 for ( i = 0; i < numMetaVerts; i++ )
1255 {
1256 /* print pacifier */
1257 f = 10 * i / numMetaVerts;
1258 if ( f != fOld ) {
1259 fOld = f;
1260 Sys_FPrintf( SYS_VRB, "%d...", f );
1261 }
1262
1263 /* already smoothed? */
1264 if ( smoothed[ i >> 3 ] & ( 1 << ( i & 7 ) ) ) {
1265 continue;
1266 }
1267
1268 /* clear */
1269 VectorClear( average );
1270 numVerts = 0;
1271 numVotes = 0;
1272
1273 /* build a table of coincident vertexes */
1274 for ( j = i; j < numMetaVerts && numVerts < MAX_SAMPLES; j++ )
1275 {
1276 /* already smoothed? */
1277 if ( smoothed[ j >> 3 ] & ( 1 << ( j & 7 ) ) ) {
1278 continue;
1279 }
1280
1281 /* test vertexes */
1282 if ( VectorCompare( metaVerts[ i ].xyz, metaVerts[ j ].xyz ) == qfalse ) {
1283 continue;
1284 }
1285
1286 /* use smallest shade angle */
1287 shadeAngle = ( shadeAngles[ i ] < shadeAngles[ j ] ? shadeAngles[ i ] : shadeAngles[ j ] );
1288
1289 /* check shade angle */
1290 dot = DotProduct( metaVerts[ i ].normal, metaVerts[ j ].normal );
1291 if ( dot > 1.0 ) {
1292 dot = 1.0;
1293 }
1294 else if ( dot < -1.0 ) {
1295 dot = -1.0;
1296 }
1297 testAngle = acos( dot ) + THETA_EPSILON;
1298 if ( testAngle >= shadeAngle ) {
1299 continue;
1300 }
1301
1302 /* add to the list */
1303 indexes[ numVerts++ ] = j;
1304
1305 /* flag vertex */
1306 smoothed[ j >> 3 ] |= ( 1 << ( j & 7 ) );
1307
1308 /* see if this normal has already been voted */
1309 for ( k = 0; k < numVotes; k++ )
1310 {
1311 VectorSubtract( metaVerts[ j ].normal, votes[ k ], diff );
1312 if ( fabs( diff[ 0 ] ) < EQUAL_NORMAL_EPSILON &&
1313 fabs( diff[ 1 ] ) < EQUAL_NORMAL_EPSILON &&
1314 fabs( diff[ 2 ] ) < EQUAL_NORMAL_EPSILON ) {
1315 break;
1316 }
1317 }
1318
1319 /* add a new vote? */
1320 if ( k == numVotes && numVotes < MAX_SAMPLES ) {
1321 VectorAdd( average, metaVerts[ j ].normal, average );
1322 VectorCopy( metaVerts[ j ].normal, votes[ numVotes ] );
1323 numVotes++;
1324 }
1325 }
1326
1327 /* don't average for less than 2 verts */
1328 if ( numVerts < 2 ) {
1329 continue;
1330 }
1331
1332 /* average normal */
1333 if ( VectorNormalize( average, average ) > 0 ) {
1334 /* smooth */
1335 for ( j = 0; j < numVerts; j++ )
1336 VectorCopy( average, metaVerts[ indexes[ j ] ].normal );
1337 numSmoothed++;
1338 }
1339 }
1340
1341 /* free the tables */
1342 free( shadeAngles );
1343 free( smoothed );
1344
1345 /* print time */
1346 Sys_FPrintf( SYS_VRB, " (%d)\n", (int) ( I_FloatTime() - start ) );
1347
1348 /* emit some stats */
1349 Sys_FPrintf( SYS_VRB, "%9d smoothed vertexes\n", numSmoothed );
1350 }
1351
1352
1353
1354 /*
1355 AddMetaVertToSurface()
1356 adds a drawvert to a surface unless an existing vert matching already exists
1357 returns the index of that vert (or < 0 on failure)
1358 */
1359
AddMetaVertToSurface(mapDrawSurface_t * ds,bspDrawVert_t * dv1,int * coincident)1360 int AddMetaVertToSurface( mapDrawSurface_t *ds, bspDrawVert_t *dv1, int *coincident ){
1361 int i;
1362 bspDrawVert_t *dv2;
1363
1364
1365 /* go through the verts and find a suitable candidate */
1366 for ( i = 0; i < ds->numVerts; i++ )
1367 {
1368 /* get test vert */
1369 dv2 = &ds->verts[ i ];
1370
1371 /* compare xyz and normal */
1372 if ( VectorCompare( dv1->xyz, dv2->xyz ) == qfalse ) {
1373 continue;
1374 }
1375 if ( VectorCompare( dv1->normal, dv2->normal ) == qfalse ) {
1376 continue;
1377 }
1378
1379 /* good enough at this point */
1380 ( *coincident )++;
1381
1382 /* compare texture coordinates and color */
1383 if ( dv1->st[ 0 ] != dv2->st[ 0 ] || dv1->st[ 1 ] != dv2->st[ 1 ] ) {
1384 continue;
1385 }
1386 if ( dv1->color[ 0 ][ 3 ] != dv2->color[ 0 ][ 3 ] ) {
1387 continue;
1388 }
1389
1390 /* found a winner */
1391 numMergedVerts++;
1392 return i;
1393 }
1394
1395 /* overflow check */
1396 if ( ds->numVerts >= ( ( ds->shaderInfo->compileFlags & C_VERTEXLIT ) ? maxSurfaceVerts : maxLMSurfaceVerts ) ) {
1397 return VERTS_EXCEEDED;
1398 }
1399
1400 /* made it this far, add the vert and return */
1401 dv2 = &ds->verts[ ds->numVerts++ ];
1402 *dv2 = *dv1;
1403 return ( ds->numVerts - 1 );
1404 }
1405
1406
1407
1408
1409 /*
1410 AddMetaTriangleToSurface()
1411 attempts to add a metatriangle to a surface
1412 returns the score of the triangle added
1413 */
1414
1415 #define AXIS_SCORE 100000
1416 #define AXIS_MIN 100000
1417 #define VERT_SCORE 10000
1418 #define SURFACE_SCORE 1000
1419 #define ST_SCORE 50
1420 #define ST_SCORE2 ( 2 * ( ST_SCORE ) )
1421
1422 #define DEFAULT_ADEQUATE_SCORE ( (AXIS_MIN) +1 * ( VERT_SCORE ) )
1423 #define DEFAULT_GOOD_SCORE ( (AXIS_MIN) +2 * (VERT_SCORE) +4 * ( ST_SCORE ) )
1424 #define PERFECT_SCORE ( (AXIS_MIN) +3 * ( VERT_SCORE ) + (SURFACE_SCORE) +4 * ( ST_SCORE ) )
1425
1426 #define ADEQUATE_SCORE ( metaAdequateScore >= 0 ? metaAdequateScore : DEFAULT_ADEQUATE_SCORE )
1427 #define GOOD_SCORE ( metaGoodScore >= 0 ? metaGoodScore : DEFAULT_GOOD_SCORE )
1428
AddMetaTriangleToSurface(mapDrawSurface_t * ds,metaTriangle_t * tri,qboolean testAdd)1429 static int AddMetaTriangleToSurface( mapDrawSurface_t *ds, metaTriangle_t *tri, qboolean testAdd ){
1430 vec3_t p;
1431 int i, score, coincident, ai, bi, ci, oldTexRange[ 2 ];
1432 float lmMax;
1433 vec3_t mins, maxs;
1434 qboolean inTexRange;
1435 mapDrawSurface_t old;
1436
1437
1438 /* overflow check */
1439 if ( ds->numIndexes >= maxSurfaceIndexes ) {
1440 return 0;
1441 }
1442
1443 /* test the triangle */
1444 if ( ds->entityNum != tri->entityNum ) { /* ydnar: added 2002-07-06 */
1445 return 0;
1446 }
1447 if ( ds->castShadows != tri->castShadows || ds->recvShadows != tri->recvShadows ) {
1448 return 0;
1449 }
1450 if ( ds->shaderInfo != tri->si || ds->fogNum != tri->fogNum || ds->sampleSize != tri->sampleSize ) {
1451 return 0;
1452 }
1453 #if 0
1454 if ( !( ds->shaderInfo->compileFlags & C_VERTEXLIT ) &&
1455 //% VectorCompare( ds->lightmapAxis, tri->lightmapAxis ) == qfalse )
1456 DotProduct( ds->lightmapAxis, tri->plane ) < 0.25f ) {
1457 return 0;
1458 }
1459 #endif
1460
1461 /* planar surfaces will only merge with triangles in the same plane */
1462 if ( npDegrees == 0.0f && ds->shaderInfo->nonplanar == qfalse && ds->planeNum >= 0 ) {
1463 if ( VectorCompare( mapplanes[ ds->planeNum ].normal, tri->plane ) == qfalse || mapplanes[ ds->planeNum ].dist != tri->plane[ 3 ] ) {
1464 return 0;
1465 }
1466 if ( tri->planeNum >= 0 && tri->planeNum != ds->planeNum ) {
1467 return 0;
1468 }
1469 }
1470
1471
1472
1473 if ( metaMaxBBoxDistance >= 0 ) {
1474 if ( ds->numIndexes > 0 ) {
1475 VectorCopy( ds->mins, mins );
1476 VectorCopy( ds->maxs, maxs );
1477 mins[0] -= metaMaxBBoxDistance;
1478 mins[1] -= metaMaxBBoxDistance;
1479 mins[2] -= metaMaxBBoxDistance;
1480 maxs[0] += metaMaxBBoxDistance;
1481 maxs[1] += metaMaxBBoxDistance;
1482 maxs[2] += metaMaxBBoxDistance;
1483 #define CHECK_1D( mins, v, maxs ) ( ( mins ) <= ( v ) && ( v ) <= ( maxs ) )
1484 #define CHECK_3D( mins, v, maxs ) ( CHECK_1D( ( mins )[0], ( v )[0], ( maxs )[0] ) && CHECK_1D( ( mins )[1], ( v )[1], ( maxs )[1] ) && CHECK_1D( ( mins )[2], ( v )[2], ( maxs )[2] ) )
1485 VectorCopy( metaVerts[ tri->indexes[ 0 ] ].xyz, p );
1486 if ( !CHECK_3D( mins, p, maxs ) ) {
1487 VectorCopy( metaVerts[ tri->indexes[ 1 ] ].xyz, p );
1488 if ( !CHECK_3D( mins, p, maxs ) ) {
1489 VectorCopy( metaVerts[ tri->indexes[ 2 ] ].xyz, p );
1490 if ( !CHECK_3D( mins, p, maxs ) ) {
1491 return 0;
1492 }
1493 }
1494 }
1495 #undef CHECK_3D
1496 #undef CHECK_1D
1497 }
1498 }
1499
1500 /* set initial score */
1501 score = tri->surfaceNum == ds->surfaceNum ? SURFACE_SCORE : 0;
1502
1503 /* score the the dot product of lightmap axis to plane */
1504 if ( ( ds->shaderInfo->compileFlags & C_VERTEXLIT ) || VectorCompare( ds->lightmapAxis, tri->lightmapAxis ) ) {
1505 score += AXIS_SCORE;
1506 }
1507 else{
1508 score += AXIS_SCORE * DotProduct( ds->lightmapAxis, tri->plane );
1509 }
1510
1511 /* preserve old drawsurface if this fails */
1512 memcpy( &old, ds, sizeof( *ds ) );
1513
1514 /* attempt to add the verts */
1515 coincident = 0;
1516 ai = AddMetaVertToSurface( ds, &metaVerts[ tri->indexes[ 0 ] ], &coincident );
1517 bi = AddMetaVertToSurface( ds, &metaVerts[ tri->indexes[ 1 ] ], &coincident );
1518 ci = AddMetaVertToSurface( ds, &metaVerts[ tri->indexes[ 2 ] ], &coincident );
1519
1520 /* check vertex underflow */
1521 if ( ai < 0 || bi < 0 || ci < 0 ) {
1522 memcpy( ds, &old, sizeof( *ds ) );
1523 return 0;
1524 }
1525
1526 /* score coincident vertex count (2003-02-14: changed so this only matters on planar surfaces) */
1527 score += ( coincident * VERT_SCORE );
1528
1529 /* add new vertex bounds to mins/maxs */
1530 VectorCopy( ds->mins, mins );
1531 VectorCopy( ds->maxs, maxs );
1532 AddPointToBounds( metaVerts[ tri->indexes[ 0 ] ].xyz, mins, maxs );
1533 AddPointToBounds( metaVerts[ tri->indexes[ 1 ] ].xyz, mins, maxs );
1534 AddPointToBounds( metaVerts[ tri->indexes[ 2 ] ].xyz, mins, maxs );
1535
1536 /* check lightmap bounds overflow (after at least 1 triangle has been added) */
1537 if ( !( ds->shaderInfo->compileFlags & C_VERTEXLIT ) &&
1538 ds->numIndexes > 0 && VectorLength( ds->lightmapAxis ) > 0.0f &&
1539 ( VectorCompare( ds->mins, mins ) == qfalse || VectorCompare( ds->maxs, maxs ) == qfalse ) ) {
1540 /* set maximum size before lightmap scaling (normally 2032 units) */
1541 /* 2004-02-24: scale lightmap test size by 2 to catch larger brush faces */
1542 /* 2004-04-11: reverting to actual lightmap size */
1543 lmMax = ( ds->sampleSize * ( ds->shaderInfo->lmCustomWidth - 1 ) );
1544 for ( i = 0; i < 3; i++ )
1545 {
1546 if ( ( maxs[ i ] - mins[ i ] ) > lmMax ) {
1547 memcpy( ds, &old, sizeof( *ds ) );
1548 return 0;
1549 }
1550 }
1551 }
1552
1553 /* check texture range overflow */
1554 oldTexRange[ 0 ] = ds->texRange[ 0 ];
1555 oldTexRange[ 1 ] = ds->texRange[ 1 ];
1556 inTexRange = CalcSurfaceTextureRange( ds );
1557
1558 if ( inTexRange == qfalse && ds->numIndexes > 0 ) {
1559 memcpy( ds, &old, sizeof( *ds ) );
1560 return UNSUITABLE_TRIANGLE;
1561 }
1562
1563 /* score texture range */
1564 if ( ds->texRange[ 0 ] <= oldTexRange[ 0 ] ) {
1565 score += ST_SCORE2;
1566 }
1567 else if ( ds->texRange[ 0 ] > oldTexRange[ 0 ] && oldTexRange[ 1 ] > oldTexRange[ 0 ] ) {
1568 score += ST_SCORE;
1569 }
1570
1571 if ( ds->texRange[ 1 ] <= oldTexRange[ 1 ] ) {
1572 score += ST_SCORE2;
1573 }
1574 else if ( ds->texRange[ 1 ] > oldTexRange[ 1 ] && oldTexRange[ 0 ] > oldTexRange[ 1 ] ) {
1575 score += ST_SCORE;
1576 }
1577
1578
1579 /* go through the indexes and try to find an existing triangle that matches abc */
1580 for ( i = 0; i < ds->numIndexes; i += 3 )
1581 {
1582 /* 2002-03-11 (birthday!): rotate the triangle 3x to find an existing triangle */
1583 if ( ( ai == ds->indexes[ i ] && bi == ds->indexes[ i + 1 ] && ci == ds->indexes[ i + 2 ] ) ||
1584 ( bi == ds->indexes[ i ] && ci == ds->indexes[ i + 1 ] && ai == ds->indexes[ i + 2 ] ) ||
1585 ( ci == ds->indexes[ i ] && ai == ds->indexes[ i + 1 ] && bi == ds->indexes[ i + 2 ] ) ) {
1586 /* triangle already present */
1587 memcpy( ds, &old, sizeof( *ds ) );
1588 tri->si = NULL;
1589 return 0;
1590 }
1591
1592 /* rotate the triangle 3x to find an inverse triangle (error case) */
1593 if ( ( ai == ds->indexes[ i ] && bi == ds->indexes[ i + 2 ] && ci == ds->indexes[ i + 1 ] ) ||
1594 ( bi == ds->indexes[ i ] && ci == ds->indexes[ i + 2 ] && ai == ds->indexes[ i + 1 ] ) ||
1595 ( ci == ds->indexes[ i ] && ai == ds->indexes[ i + 2 ] && bi == ds->indexes[ i + 1 ] ) ) {
1596 /* warn about it */
1597 Sys_Printf( "WARNING: Flipped triangle: (%6.0f %6.0f %6.0f) (%6.0f %6.0f %6.0f) (%6.0f %6.0f %6.0f)\n",
1598 ds->verts[ ai ].xyz[ 0 ], ds->verts[ ai ].xyz[ 1 ], ds->verts[ ai ].xyz[ 2 ],
1599 ds->verts[ bi ].xyz[ 0 ], ds->verts[ bi ].xyz[ 1 ], ds->verts[ bi ].xyz[ 2 ],
1600 ds->verts[ ci ].xyz[ 0 ], ds->verts[ ci ].xyz[ 1 ], ds->verts[ ci ].xyz[ 2 ] );
1601
1602 /* reverse triangle already present */
1603 memcpy( ds, &old, sizeof( *ds ) );
1604 tri->si = NULL;
1605 return 0;
1606 }
1607 }
1608
1609 /* add the triangle indexes */
1610 if ( ds->numIndexes < maxSurfaceIndexes ) {
1611 ds->indexes[ ds->numIndexes++ ] = ai;
1612 }
1613 if ( ds->numIndexes < maxSurfaceIndexes ) {
1614 ds->indexes[ ds->numIndexes++ ] = bi;
1615 }
1616 if ( ds->numIndexes < maxSurfaceIndexes ) {
1617 ds->indexes[ ds->numIndexes++ ] = ci;
1618 }
1619
1620 /* check index overflow */
1621 if ( ds->numIndexes >= maxSurfaceIndexes ) {
1622 memcpy( ds, &old, sizeof( *ds ) );
1623 return 0;
1624 }
1625
1626 /* sanity check the indexes */
1627 if ( ds->numIndexes >= 3 &&
1628 ( ds->indexes[ ds->numIndexes - 3 ] == ds->indexes[ ds->numIndexes - 2 ] ||
1629 ds->indexes[ ds->numIndexes - 3 ] == ds->indexes[ ds->numIndexes - 1 ] ||
1630 ds->indexes[ ds->numIndexes - 2 ] == ds->indexes[ ds->numIndexes - 1 ] ) ) {
1631 Sys_Printf( "DEG:%d! ", ds->numVerts );
1632 }
1633
1634 /* testing only? */
1635 if ( testAdd ) {
1636 memcpy( ds, &old, sizeof( *ds ) );
1637 }
1638 else
1639 {
1640 /* copy bounds back to surface */
1641 VectorCopy( mins, ds->mins );
1642 VectorCopy( maxs, ds->maxs );
1643
1644 /* mark triangle as used */
1645 tri->si = NULL;
1646 }
1647
1648 /* add a side reference */
1649 ds->sideRef = AllocSideRef( tri->side, ds->sideRef );
1650
1651 /* return to sender */
1652 return score;
1653 }
1654
1655
1656
1657 /*
1658 MetaTrianglesToSurface()
1659 creates map drawsurface(s) from the list of possibles
1660 */
1661
MetaTrianglesToSurface(int numPossibles,metaTriangle_t * possibles,int * fOld,int * numAdded)1662 static void MetaTrianglesToSurface( int numPossibles, metaTriangle_t *possibles, int *fOld, int *numAdded ){
1663 int i, j, f, best, score, bestScore;
1664 metaTriangle_t *seed, *test;
1665 mapDrawSurface_t *ds;
1666 bspDrawVert_t *verts;
1667 int *indexes;
1668 qboolean added;
1669
1670
1671 /* allocate arrays */
1672 verts = safe_malloc( sizeof( *verts ) * maxSurfaceVerts );
1673 indexes = safe_malloc( sizeof( *indexes ) * maxSurfaceIndexes );
1674
1675 /* walk the list of triangles */
1676 for ( i = 0, seed = possibles; i < numPossibles; i++, seed++ )
1677 {
1678 /* skip this triangle if it has already been merged */
1679 if ( seed->si == NULL ) {
1680 continue;
1681 }
1682
1683 /* -----------------------------------------------------------------
1684 initial drawsurf construction
1685 ----------------------------------------------------------------- */
1686
1687 /* start a new drawsurface */
1688 ds = AllocDrawSurface( SURFACE_META );
1689 ds->entityNum = seed->entityNum;
1690 ds->surfaceNum = seed->surfaceNum;
1691 ds->castShadows = seed->castShadows;
1692 ds->recvShadows = seed->recvShadows;
1693
1694 ds->shaderInfo = seed->si;
1695 ds->planeNum = seed->planeNum;
1696 ds->fogNum = seed->fogNum;
1697 ds->sampleSize = seed->sampleSize;
1698 ds->shadeAngleDegrees = seed->shadeAngleDegrees;
1699 ds->verts = verts;
1700 ds->indexes = indexes;
1701 VectorCopy( seed->lightmapAxis, ds->lightmapAxis );
1702 ds->sideRef = AllocSideRef( seed->side, NULL );
1703
1704 ClearBounds( ds->mins, ds->maxs );
1705
1706 /* clear verts/indexes */
1707 memset( verts, 0, sizeof( verts ) );
1708 memset( indexes, 0, sizeof( indexes ) );
1709
1710 /* add the first triangle */
1711 if ( AddMetaTriangleToSurface( ds, seed, qfalse ) ) {
1712 ( *numAdded )++;
1713 }
1714
1715 /* -----------------------------------------------------------------
1716 add triangles
1717 ----------------------------------------------------------------- */
1718
1719 /* progressively walk the list until no more triangles can be added */
1720 added = qtrue;
1721 while ( added )
1722 {
1723 /* print pacifier */
1724 f = 10 * *numAdded / numMetaTriangles;
1725 if ( f > *fOld ) {
1726 *fOld = f;
1727 Sys_FPrintf( SYS_VRB, "%d...", f );
1728 }
1729
1730 /* reset best score */
1731 best = -1;
1732 bestScore = 0;
1733 added = qfalse;
1734
1735 /* walk the list of possible candidates for merging */
1736 for ( j = i + 1, test = &possibles[ j ]; j < numPossibles; j++, test++ )
1737 {
1738 /* skip this triangle if it has already been merged */
1739 if ( test->si == NULL ) {
1740 continue;
1741 }
1742
1743 /* score this triangle */
1744 score = AddMetaTriangleToSurface( ds, test, qtrue );
1745 if ( score > bestScore ) {
1746 best = j;
1747 bestScore = score;
1748
1749 /* if we have a score over a certain threshold, just use it */
1750 if ( bestScore >= GOOD_SCORE ) {
1751 if ( AddMetaTriangleToSurface( ds, &possibles[ best ], qfalse ) ) {
1752 ( *numAdded )++;
1753 }
1754
1755 /* reset */
1756 best = -1;
1757 bestScore = 0;
1758 added = qtrue;
1759 }
1760 }
1761 }
1762
1763 /* add best candidate */
1764 if ( best >= 0 && bestScore > ADEQUATE_SCORE ) {
1765 if ( AddMetaTriangleToSurface( ds, &possibles[ best ], qfalse ) ) {
1766 ( *numAdded )++;
1767 }
1768
1769 /* reset */
1770 added = qtrue;
1771 }
1772 }
1773
1774 /* copy the verts and indexes to the new surface */
1775 ds->verts = safe_malloc( ds->numVerts * sizeof( bspDrawVert_t ) );
1776 memcpy( ds->verts, verts, ds->numVerts * sizeof( bspDrawVert_t ) );
1777 ds->indexes = safe_malloc( ds->numIndexes * sizeof( int ) );
1778 memcpy( ds->indexes, indexes, ds->numIndexes * sizeof( int ) );
1779
1780 /* classify the surface */
1781 ClassifySurfaces( 1, ds );
1782
1783 /* add to count */
1784 numMergedSurfaces++;
1785 }
1786
1787 /* free arrays */
1788 free( verts );
1789 free( indexes );
1790 }
1791
1792
1793
1794 /*
1795 CompareMetaTriangles()
1796 compare function for qsort()
1797 */
1798
CompareMetaTriangles(const void * a,const void * b)1799 static int CompareMetaTriangles( const void *a, const void *b ){
1800 int i, j, av, bv;
1801 vec3_t aMins, bMins;
1802
1803
1804 /* shader first */
1805 if ( ( (const metaTriangle_t*) a )->si < ( (const metaTriangle_t*) b )->si ) {
1806 return 1;
1807 }
1808 else if ( ( (const metaTriangle_t*) a )->si > ( (const metaTriangle_t*) b )->si ) {
1809 return -1;
1810 }
1811
1812 /* then fog */
1813 else if ( ( (const metaTriangle_t*) a )->fogNum < ( (const metaTriangle_t*) b )->fogNum ) {
1814 return 1;
1815 }
1816 else if ( ( (const metaTriangle_t*) a )->fogNum > ( (const metaTriangle_t*) b )->fogNum ) {
1817 return -1;
1818 }
1819
1820 /* then plane */
1821 #if 0
1822 else if ( npDegrees == 0.0f && ( (const metaTriangle_t*) a )->si->nonplanar == qfalse &&
1823 ( (const metaTriangle_t*) a )->planeNum >= 0 && ( (const metaTriangle_t*) a )->planeNum >= 0 ) {
1824 if ( ( (const metaTriangle_t*) a )->plane[ 3 ] < ( (const metaTriangle_t*) b )->plane[ 3 ] ) {
1825 return 1;
1826 }
1827 else if ( ( (const metaTriangle_t*) a )->plane[ 3 ] > ( (const metaTriangle_t*) b )->plane[ 3 ] ) {
1828 return -1;
1829 }
1830 else if ( ( (const metaTriangle_t*) a )->plane[ 0 ] < ( (const metaTriangle_t*) b )->plane[ 0 ] ) {
1831 return 1;
1832 }
1833 else if ( ( (const metaTriangle_t*) a )->plane[ 0 ] > ( (const metaTriangle_t*) b )->plane[ 0 ] ) {
1834 return -1;
1835 }
1836 else if ( ( (const metaTriangle_t*) a )->plane[ 1 ] < ( (const metaTriangle_t*) b )->plane[ 1 ] ) {
1837 return 1;
1838 }
1839 else if ( ( (const metaTriangle_t*) a )->plane[ 1 ] > ( (const metaTriangle_t*) b )->plane[ 1 ] ) {
1840 return -1;
1841 }
1842 else if ( ( (const metaTriangle_t*) a )->plane[ 2 ] < ( (const metaTriangle_t*) b )->plane[ 2 ] ) {
1843 return 1;
1844 }
1845 else if ( ( (const metaTriangle_t*) a )->plane[ 2 ] > ( (const metaTriangle_t*) b )->plane[ 2 ] ) {
1846 return -1;
1847 }
1848 }
1849 #endif
1850
1851 /* then position in world */
1852
1853 /* find mins */
1854 VectorSet( aMins, 999999, 999999, 999999 );
1855 VectorSet( bMins, 999999, 999999, 999999 );
1856 for ( i = 0; i < 3; i++ )
1857 {
1858 av = ( (const metaTriangle_t*) a )->indexes[ i ];
1859 bv = ( (const metaTriangle_t*) b )->indexes[ i ];
1860 for ( j = 0; j < 3; j++ )
1861 {
1862 if ( metaVerts[ av ].xyz[ j ] < aMins[ j ] ) {
1863 aMins[ j ] = metaVerts[ av ].xyz[ j ];
1864 }
1865 if ( metaVerts[ bv ].xyz[ j ] < bMins[ j ] ) {
1866 bMins[ j ] = metaVerts[ bv ].xyz[ j ];
1867 }
1868 }
1869 }
1870
1871 /* test it */
1872 for ( i = 0; i < 3; i++ )
1873 {
1874 if ( aMins[ i ] < bMins[ i ] ) {
1875 return 1;
1876 }
1877 else if ( aMins[ i ] > bMins[ i ] ) {
1878 return -1;
1879 }
1880 }
1881
1882 /* functionally equivalent */
1883 return 0;
1884 }
1885
1886
1887
1888 /*
1889 MergeMetaTriangles()
1890 merges meta triangles into drawsurfaces
1891 */
1892
MergeMetaTriangles(void)1893 void MergeMetaTriangles( void ){
1894 int i, j, fOld, start, numAdded;
1895 metaTriangle_t *head, *end;
1896
1897
1898 /* only do this if there are meta triangles */
1899 if ( numMetaTriangles <= 0 ) {
1900 return;
1901 }
1902
1903 /* note it */
1904 Sys_FPrintf( SYS_VRB, "--- MergeMetaTriangles ---\n" );
1905
1906 /* sort the triangles by shader major, fognum minor */
1907 qsort( metaTriangles, numMetaTriangles, sizeof( metaTriangle_t ), CompareMetaTriangles );
1908
1909 /* init pacifier */
1910 fOld = -1;
1911 start = I_FloatTime();
1912 numAdded = 0;
1913
1914 /* merge */
1915 for ( i = 0, j = 0; i < numMetaTriangles; i = j )
1916 {
1917 /* get head of list */
1918 head = &metaTriangles[ i ];
1919
1920 /* skip this triangle if it has already been merged */
1921 if ( head->si == NULL ) {
1922 continue;
1923 }
1924
1925 /* find end */
1926 if ( j <= i ) {
1927 for ( j = i + 1; j < numMetaTriangles; j++ )
1928 {
1929 /* get end of list */
1930 end = &metaTriangles[ j ];
1931 if ( head->si != end->si || head->fogNum != end->fogNum ) {
1932 break;
1933 }
1934 }
1935 }
1936
1937 /* try to merge this list of possible merge candidates */
1938 MetaTrianglesToSurface( ( j - i ), head, &fOld, &numAdded );
1939 }
1940
1941 /* clear meta triangle list */
1942 ClearMetaTriangles();
1943
1944 /* print time */
1945 if ( i ) {
1946 Sys_FPrintf( SYS_VRB, " (%d)\n", (int) ( I_FloatTime() - start ) );
1947 }
1948
1949 /* emit some stats */
1950 Sys_FPrintf( SYS_VRB, "%9d surfaces merged\n", numMergedSurfaces );
1951 Sys_FPrintf( SYS_VRB, "%9d vertexes merged\n", numMergedVerts );
1952 }
1953