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