1 /*
2 ===========================================================================
3
4 Doom 3 GPL Source Code
5 Copyright (C) 1999-2011 id Software LLC, a ZeniMax Media company.
6
7 This file is part of the Doom 3 GPL Source Code ("Doom 3 Source Code").
8
9 Doom 3 Source Code is free software: you can redistribute it and/or modify
10 it under the terms of the GNU General Public License as published by
11 the Free Software Foundation, either version 3 of the License, or
12 (at your option) any later version.
13
14 Doom 3 Source Code is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with Doom 3 Source Code. If not, see <http://www.gnu.org/licenses/>.
21
22 In addition, the Doom 3 Source Code is also subject to certain additional terms. You should have received a copy of these additional terms immediately following the terms and conditions of the GNU General Public License which accompanied the Doom 3 Source Code. If not, please request a copy in writing from id Software at the address below.
23
24 If you have questions concerning this license or the applicable additional terms, you may contact in writing id Software LLC, c/o ZeniMax Media Inc., Suite 120, Rockville, Maryland 20850 USA.
25
26 ===========================================================================
27 */
28
29 #include "sys/platform.h"
30 #include "renderer/VertexCache.h"
31
32 #include "renderer/tr_local.h"
33
34 /*
35 ==============================================================================
36
37 TRIANGLE MESH PROCESSING
38
39 The functions in this file have no vertex / index count limits.
40
41 Truly identical vertexes that match in position, normal, and texcoord can
42 be merged away.
43
44 Vertexes that match in position and texcoord, but have distinct normals will
45 remain distinct for all purposes. This is usually a poor choice for models,
46 as adding a bevel face will not add any more vertexes, and will tend to
47 look better.
48
49 Match in position and normal, but differ in texcoords are referenced together
50 for calculating tangent vectors for bump mapping.
51 Artists should take care to have identical texels in all maps (bump/diffuse/specular)
52 in this case
53
54 Vertexes that only match in position are merged for shadow edge finding.
55
56 Degenerate triangles.
57
58 Overlapped triangles, even if normals or texcoords differ, must be removed.
59 for the silhoette based stencil shadow algorithm to function properly.
60 Is this true???
61 Is the overlapped triangle problem just an example of the trippled edge problem?
62
63 Interpenetrating triangles are not currently clipped to surfaces.
64 Do they effect the shadows?
65
66 if vertexes are intended to deform apart, make sure that no vertexes
67 are on top of each other in the base frame, or the sil edges may be
68 calculated incorrectly.
69
70 We might be able to identify this from topology.
71
72 Dangling edges are acceptable, but three way edges are not.
73
74 Are any combinations of two way edges unacceptable, like one facing
75 the backside of the other?
76
77
78 Topology is determined by a collection of triangle indexes.
79
80 The edge list can be built up from this, and stays valid even under
81 deformations.
82
83 Somewhat non-intuitively, concave edges cannot be optimized away, or the
84 stencil shadow algorithm miscounts.
85
86 Face normals are needed for generating shadow volumes and for calculating
87 the silhouette, but they will change with any deformation.
88
89 Vertex normals and vertex tangents will change with each deformation,
90 but they may be able to be transformed instead of recalculated.
91
92 bounding volume, both box and sphere will change with deformation.
93
94 silhouette indexes
95 shade indexes
96 texture indexes
97
98 shade indexes will only be > silhouette indexes if there is facet shading present
99
100 lookups from texture to sil and texture to shade?
101
102 The normal and tangent vector smoothing is simple averaging, no attempt is
103 made to better handle the cases where the distribution around the shared vertex
104 is highly uneven.
105
106
107 we may get degenerate triangles even with the uniquing and removal
108 if the vertexes have different texcoords.
109
110 ==============================================================================
111 */
112
113 // this shouldn't change anything, but previously renderbumped models seem to need it
114 #define USE_INVA
115
116 // instead of using the texture T vector, cross the normal and S vector for an orthogonal axis
117 #define DERIVE_UNSMOOTHED_BITANGENT
118
119 const int MAX_SIL_EDGES = 0x10000;
120 const int SILEDGE_HASH_SIZE = 1024;
121
122 static int numSilEdges;
123 static silEdge_t * silEdges;
124 static idHashIndex silEdgeHash( SILEDGE_HASH_SIZE, MAX_SIL_EDGES );
125 static int numPlanes;
126
127 static idBlockAlloc<srfTriangles_t, 1<<8> srfTrianglesAllocator;
128
129 #ifdef USE_TRI_DATA_ALLOCATOR
130 static idDynamicBlockAlloc<idDrawVert, 1<<20, 1<<10> triVertexAllocator;
131 static idDynamicBlockAlloc<glIndex_t, 1<<18, 1<<10> triIndexAllocator;
132 static idDynamicBlockAlloc<shadowCache_t, 1<<18, 1<<10> triShadowVertexAllocator;
133 static idDynamicBlockAlloc<idPlane, 1<<17, 1<<10> triPlaneAllocator;
134 static idDynamicBlockAlloc<glIndex_t, 1<<17, 1<<10> triSilIndexAllocator;
135 static idDynamicBlockAlloc<silEdge_t, 1<<17, 1<<10> triSilEdgeAllocator;
136 static idDynamicBlockAlloc<dominantTri_t, 1<<16, 1<<10> triDominantTrisAllocator;
137 static idDynamicBlockAlloc<int, 1<<16, 1<<10> triMirroredVertAllocator;
138 static idDynamicBlockAlloc<int, 1<<16, 1<<10> triDupVertAllocator;
139 #else
140 static idDynamicAlloc<idDrawVert, 1<<20, 1<<10> triVertexAllocator;
141 static idDynamicAlloc<glIndex_t, 1<<18, 1<<10> triIndexAllocator;
142 static idDynamicAlloc<shadowCache_t, 1<<18, 1<<10> triShadowVertexAllocator;
143 static idDynamicAlloc<idPlane, 1<<17, 1<<10> triPlaneAllocator;
144 static idDynamicAlloc<glIndex_t, 1<<17, 1<<10> triSilIndexAllocator;
145 static idDynamicAlloc<silEdge_t, 1<<17, 1<<10> triSilEdgeAllocator;
146 static idDynamicAlloc<dominantTri_t, 1<<16, 1<<10> triDominantTrisAllocator;
147 static idDynamicAlloc<int, 1<<16, 1<<10> triMirroredVertAllocator;
148 static idDynamicAlloc<int, 1<<16, 1<<10> triDupVertAllocator;
149 #endif
150
151
152 /*
153 ===============
154 R_InitTriSurfData
155 ===============
156 */
R_InitTriSurfData(void)157 void R_InitTriSurfData( void ) {
158 silEdges = (silEdge_t *)R_StaticAlloc( MAX_SIL_EDGES * sizeof( silEdges[0] ) );
159
160 // initialize allocators for triangle surfaces
161 triVertexAllocator.Init();
162 triIndexAllocator.Init();
163 triShadowVertexAllocator.Init();
164 triPlaneAllocator.Init();
165 triSilIndexAllocator.Init();
166 triSilEdgeAllocator.Init();
167 triDominantTrisAllocator.Init();
168 triMirroredVertAllocator.Init();
169 triDupVertAllocator.Init();
170
171 // never swap out triangle surfaces
172 triVertexAllocator.SetLockMemory( true );
173 triIndexAllocator.SetLockMemory( true );
174 triShadowVertexAllocator.SetLockMemory( true );
175 triPlaneAllocator.SetLockMemory( true );
176 triSilIndexAllocator.SetLockMemory( true );
177 triSilEdgeAllocator.SetLockMemory( true );
178 triDominantTrisAllocator.SetLockMemory( true );
179 triMirroredVertAllocator.SetLockMemory( true );
180 triDupVertAllocator.SetLockMemory( true );
181 }
182
183 /*
184 ===============
185 R_ShutdownTriSurfData
186 ===============
187 */
R_ShutdownTriSurfData(void)188 void R_ShutdownTriSurfData( void ) {
189 R_StaticFree( silEdges );
190 silEdgeHash.Free();
191 srfTrianglesAllocator.Shutdown();
192 triVertexAllocator.Shutdown();
193 triIndexAllocator.Shutdown();
194 triShadowVertexAllocator.Shutdown();
195 triPlaneAllocator.Shutdown();
196 triSilIndexAllocator.Shutdown();
197 triSilEdgeAllocator.Shutdown();
198 triDominantTrisAllocator.Shutdown();
199 triMirroredVertAllocator.Shutdown();
200 triDupVertAllocator.Shutdown();
201 }
202
203 /*
204 ===============
205 R_PurgeTriSurfData
206 ===============
207 */
R_PurgeTriSurfData(frameData_t * frame)208 void R_PurgeTriSurfData( frameData_t *frame ) {
209 // free deferred triangle surfaces
210 R_FreeDeferredTriSurfs( frame );
211
212 // free empty base blocks
213 triVertexAllocator.FreeEmptyBaseBlocks();
214 triIndexAllocator.FreeEmptyBaseBlocks();
215 triShadowVertexAllocator.FreeEmptyBaseBlocks();
216 triPlaneAllocator.FreeEmptyBaseBlocks();
217 triSilIndexAllocator.FreeEmptyBaseBlocks();
218 triSilEdgeAllocator.FreeEmptyBaseBlocks();
219 triDominantTrisAllocator.FreeEmptyBaseBlocks();
220 triMirroredVertAllocator.FreeEmptyBaseBlocks();
221 triDupVertAllocator.FreeEmptyBaseBlocks();
222 }
223
224 /*
225 ===============
226 R_ShowTriMemory_f
227 ===============
228 */
R_ShowTriSurfMemory_f(const idCmdArgs & args)229 void R_ShowTriSurfMemory_f( const idCmdArgs &args ) {
230 common->Printf( "%6zd kB in %d triangle surfaces\n",
231 ( srfTrianglesAllocator.GetAllocCount() * sizeof( srfTriangles_t ) ) >> 10,
232 srfTrianglesAllocator.GetAllocCount() );
233
234 common->Printf( "%6d kB vertex memory (%d kB free in %d blocks, %d empty base blocks)\n",
235 triVertexAllocator.GetBaseBlockMemory() >> 10, triVertexAllocator.GetFreeBlockMemory() >> 10,
236 triVertexAllocator.GetNumFreeBlocks(), triVertexAllocator.GetNumEmptyBaseBlocks() );
237
238 common->Printf( "%6d kB index memory (%d kB free in %d blocks, %d empty base blocks)\n",
239 triIndexAllocator.GetBaseBlockMemory() >> 10, triIndexAllocator.GetFreeBlockMemory() >> 10,
240 triIndexAllocator.GetNumFreeBlocks(), triIndexAllocator.GetNumEmptyBaseBlocks() );
241
242 common->Printf( "%6d kB shadow vert memory (%d kB free in %d blocks, %d empty base blocks)\n",
243 triShadowVertexAllocator.GetBaseBlockMemory() >> 10, triShadowVertexAllocator.GetFreeBlockMemory() >> 10,
244 triShadowVertexAllocator.GetNumFreeBlocks(), triShadowVertexAllocator.GetNumEmptyBaseBlocks() );
245
246 common->Printf( "%6d kB tri plane memory (%d kB free in %d blocks, %d empty base blocks)\n",
247 triPlaneAllocator.GetBaseBlockMemory() >> 10, triPlaneAllocator.GetFreeBlockMemory() >> 10,
248 triPlaneAllocator.GetNumFreeBlocks(), triPlaneAllocator.GetNumEmptyBaseBlocks() );
249
250 common->Printf( "%6d kB sil index memory (%d kB free in %d blocks, %d empty base blocks)\n",
251 triSilIndexAllocator.GetBaseBlockMemory() >> 10, triSilIndexAllocator.GetFreeBlockMemory() >> 10,
252 triSilIndexAllocator.GetNumFreeBlocks(), triSilIndexAllocator.GetNumEmptyBaseBlocks() );
253
254 common->Printf( "%6d kB sil edge memory (%d kB free in %d blocks, %d empty base blocks)\n",
255 triSilEdgeAllocator.GetBaseBlockMemory() >> 10, triSilEdgeAllocator.GetFreeBlockMemory() >> 10,
256 triSilEdgeAllocator.GetNumFreeBlocks(), triSilEdgeAllocator.GetNumEmptyBaseBlocks() );
257
258 common->Printf( "%6d kB dominant tri memory (%d kB free in %d blocks, %d empty base blocks)\n",
259 triDominantTrisAllocator.GetBaseBlockMemory() >> 10, triDominantTrisAllocator.GetFreeBlockMemory() >> 10,
260 triDominantTrisAllocator.GetNumFreeBlocks(), triDominantTrisAllocator.GetNumEmptyBaseBlocks() );
261
262 common->Printf( "%6d kB mirror vert memory (%d kB free in %d blocks, %d empty base blocks)\n",
263 triMirroredVertAllocator.GetBaseBlockMemory() >> 10, triMirroredVertAllocator.GetFreeBlockMemory() >> 10,
264 triMirroredVertAllocator.GetNumFreeBlocks(), triMirroredVertAllocator.GetNumEmptyBaseBlocks() );
265
266 common->Printf( "%6d kB dup vert memory (%d kB free in %d blocks, %d empty base blocks)\n",
267 triDupVertAllocator.GetBaseBlockMemory() >> 10, triDupVertAllocator.GetFreeBlockMemory() >> 10,
268 triDupVertAllocator.GetNumFreeBlocks(), triDupVertAllocator.GetNumEmptyBaseBlocks() );
269
270 common->Printf( "%6zu kB total triangle memory\n",
271 ( srfTrianglesAllocator.GetAllocCount() * sizeof( srfTriangles_t ) +
272 triVertexAllocator.GetBaseBlockMemory() +
273 triIndexAllocator.GetBaseBlockMemory() +
274 triShadowVertexAllocator.GetBaseBlockMemory() +
275 triPlaneAllocator.GetBaseBlockMemory() +
276 triSilIndexAllocator.GetBaseBlockMemory() +
277 triSilEdgeAllocator.GetBaseBlockMemory() +
278 triDominantTrisAllocator.GetBaseBlockMemory() +
279 triMirroredVertAllocator.GetBaseBlockMemory() +
280 triDupVertAllocator.GetBaseBlockMemory() ) >> 10 );
281 }
282
283 /*
284 =================
285 R_TriSurfMemory
286
287 For memory profiling
288 =================
289 */
R_TriSurfMemory(const srfTriangles_t * tri)290 int R_TriSurfMemory( const srfTriangles_t *tri ) {
291 int total = 0;
292
293 if ( !tri ) {
294 return total;
295 }
296
297 // used as a flag in interations
298 if ( tri == LIGHT_TRIS_DEFERRED ) {
299 return total;
300 }
301
302 if ( tri->shadowVertexes != NULL ) {
303 total += tri->numVerts * sizeof( tri->shadowVertexes[0] );
304 } else if ( tri->verts != NULL ) {
305 if ( tri->ambientSurface == NULL || tri->verts != tri->ambientSurface->verts ) {
306 total += tri->numVerts * sizeof( tri->verts[0] );
307 }
308 }
309 if ( tri->facePlanes != NULL ) {
310 total += tri->numIndexes / 3 * sizeof( tri->facePlanes[0] );
311 }
312 if ( tri->indexes != NULL ) {
313 if ( tri->ambientSurface == NULL || tri->indexes != tri->ambientSurface->indexes ) {
314 total += tri->numIndexes * sizeof( tri->indexes[0] );
315 }
316 }
317 if ( tri->silIndexes != NULL ) {
318 total += tri->numIndexes * sizeof( tri->silIndexes[0] );
319 }
320 if ( tri->silEdges != NULL ) {
321 total += tri->numSilEdges * sizeof( tri->silEdges[0] );
322 }
323 if ( tri->dominantTris != NULL ) {
324 total += tri->numVerts * sizeof( tri->dominantTris[0] );
325 }
326 if ( tri->mirroredVerts != NULL ) {
327 total += tri->numMirroredVerts * sizeof( tri->mirroredVerts[0] );
328 }
329 if ( tri->dupVerts != NULL ) {
330 total += tri->numDupVerts * sizeof( tri->dupVerts[0] );
331 }
332
333 total += sizeof( *tri );
334
335 return total;
336 }
337
338 /*
339 ==============
340 R_FreeStaticTriSurfVertexCaches
341 ==============
342 */
R_FreeStaticTriSurfVertexCaches(srfTriangles_t * tri)343 void R_FreeStaticTriSurfVertexCaches( srfTriangles_t *tri ) {
344 if ( tri->ambientSurface == NULL ) {
345 // this is a real model surface
346 vertexCache.Free( tri->ambientCache );
347 tri->ambientCache = NULL;
348 } else {
349 // this is a light interaction surface that references
350 // a different ambient model surface
351 vertexCache.Free( tri->lightingCache );
352 tri->lightingCache = NULL;
353 }
354 if ( tri->indexCache ) {
355 vertexCache.Free( tri->indexCache );
356 tri->indexCache = NULL;
357 }
358 if ( tri->shadowCache && ( tri->shadowVertexes != NULL || tri->verts != NULL ) ) {
359 // if we don't have tri->shadowVertexes, these are a reference to a
360 // shadowCache on the original surface, which a vertex program
361 // will take care of making unique for each light
362 vertexCache.Free( tri->shadowCache );
363 tri->shadowCache = NULL;
364 }
365 }
366
367 /*
368 ==============
369 R_ReallyFreeStaticTriSurf
370
371 This does the actual free
372 ==============
373 */
R_ReallyFreeStaticTriSurf(srfTriangles_t * tri)374 void R_ReallyFreeStaticTriSurf( srfTriangles_t *tri ) {
375 if ( !tri ) {
376 return;
377 }
378
379 R_FreeStaticTriSurfVertexCaches( tri );
380
381 if ( tri->verts != NULL ) {
382 // R_CreateLightTris points tri->verts at the verts of the ambient surface
383 if ( tri->ambientSurface == NULL || tri->verts != tri->ambientSurface->verts ) {
384 triVertexAllocator.Free( tri->verts );
385 }
386 }
387
388 if ( !tri->deformedSurface ) {
389 if ( tri->indexes != NULL ) {
390 // if a surface is completely inside a light volume R_CreateLightTris points tri->indexes at the indexes of the ambient surface
391 if ( tri->ambientSurface == NULL || tri->indexes != tri->ambientSurface->indexes ) {
392 triIndexAllocator.Free( tri->indexes );
393 }
394 }
395 if ( tri->silIndexes != NULL ) {
396 triSilIndexAllocator.Free( tri->silIndexes );
397 }
398 if ( tri->silEdges != NULL ) {
399 triSilEdgeAllocator.Free( tri->silEdges );
400 }
401 if ( tri->dominantTris != NULL ) {
402 triDominantTrisAllocator.Free( tri->dominantTris );
403 }
404 if ( tri->mirroredVerts != NULL ) {
405 triMirroredVertAllocator.Free( tri->mirroredVerts );
406 }
407 if ( tri->dupVerts != NULL ) {
408 triDupVertAllocator.Free( tri->dupVerts );
409 }
410 }
411
412 if ( tri->facePlanes != NULL ) {
413 triPlaneAllocator.Free( tri->facePlanes );
414 }
415
416 if ( tri->shadowVertexes != NULL ) {
417 triShadowVertexAllocator.Free( tri->shadowVertexes );
418 }
419
420 #ifdef _DEBUG
421 memset( tri, 0, sizeof( srfTriangles_t ) );
422 #endif
423
424 srfTrianglesAllocator.Free( tri );
425 }
426
427 /*
428 ==============
429 R_CheckStaticTriSurfMemory
430 ==============
431 */
R_CheckStaticTriSurfMemory(const srfTriangles_t * tri)432 void R_CheckStaticTriSurfMemory( const srfTriangles_t *tri ) {
433 if ( !tri ) {
434 return;
435 }
436
437 if ( tri->verts != NULL ) {
438 // R_CreateLightTris points tri->verts at the verts of the ambient surface
439 if ( tri->ambientSurface == NULL || tri->verts != tri->ambientSurface->verts ) {
440 const char *error id_attribute((unused)) = triVertexAllocator.CheckMemory( tri->verts );
441 assert( error == NULL );
442 }
443 }
444
445 if ( !tri->deformedSurface ) {
446 if ( tri->indexes != NULL ) {
447 // if a surface is completely inside a light volume R_CreateLightTris points tri->indexes at the indexes of the ambient surface
448 if ( tri->ambientSurface == NULL || tri->indexes != tri->ambientSurface->indexes ) {
449 const char *error id_attribute((unused)) = triIndexAllocator.CheckMemory( tri->indexes );
450 assert( error == NULL );
451 }
452 }
453 }
454
455 if ( tri->shadowVertexes != NULL ) {
456 const char *error id_attribute((unused)) = triShadowVertexAllocator.CheckMemory( tri->shadowVertexes );
457 assert( error == NULL );
458 }
459 }
460
461 /*
462 ==================
463 R_FreeDeferredTriSurfs
464 ==================
465 */
R_FreeDeferredTriSurfs(frameData_t * frame)466 void R_FreeDeferredTriSurfs( frameData_t *frame ) {
467 srfTriangles_t *tri, *next;
468
469 if ( !frame ) {
470 return;
471 }
472
473 for ( tri = frame->firstDeferredFreeTriSurf; tri; tri = next ) {
474 next = tri->nextDeferredFree;
475 R_ReallyFreeStaticTriSurf( tri );
476 }
477
478 frame->firstDeferredFreeTriSurf = NULL;
479 frame->lastDeferredFreeTriSurf = NULL;
480 }
481
482 /*
483 ==============
484 R_FreeStaticTriSurf
485
486 This will defer the free until the current frame has run through the back end.
487 ==============
488 */
R_FreeStaticTriSurf(srfTriangles_t * tri)489 void R_FreeStaticTriSurf( srfTriangles_t *tri ) {
490 frameData_t *frame;
491
492 if ( !tri ) {
493 return;
494 }
495
496 if ( tri->nextDeferredFree ) {
497 common->Error( "R_FreeStaticTriSurf: freed a freed triangle" );
498 }
499 frame = frameData;
500
501 if ( !frame ) {
502 // command line utility, or rendering in editor preview mode ( force )
503 R_ReallyFreeStaticTriSurf( tri );
504 } else {
505 #ifdef ID_DEBUG_MEMORY
506 R_CheckStaticTriSurfMemory( tri );
507 #endif
508 tri->nextDeferredFree = NULL;
509 if ( frame->lastDeferredFreeTriSurf ) {
510 frame->lastDeferredFreeTriSurf->nextDeferredFree = tri;
511 } else {
512 frame->firstDeferredFreeTriSurf = tri;
513 }
514 frame->lastDeferredFreeTriSurf = tri;
515 }
516 }
517
518 /*
519 ==============
520 R_AllocStaticTriSurf
521 ==============
522 */
R_AllocStaticTriSurf(void)523 srfTriangles_t *R_AllocStaticTriSurf( void ) {
524 srfTriangles_t *tris = srfTrianglesAllocator.Alloc();
525 memset( tris, 0, sizeof( srfTriangles_t ) );
526 return tris;
527 }
528
529 /*
530 =================
531 R_CopyStaticTriSurf
532
533 This only duplicates the indexes and verts, not any of the derived data.
534 =================
535 */
R_CopyStaticTriSurf(const srfTriangles_t * tri)536 srfTriangles_t *R_CopyStaticTriSurf( const srfTriangles_t *tri ) {
537 srfTriangles_t *newTri;
538
539 newTri = R_AllocStaticTriSurf();
540 R_AllocStaticTriSurfVerts( newTri, tri->numVerts );
541 R_AllocStaticTriSurfIndexes( newTri, tri->numIndexes );
542 newTri->numVerts = tri->numVerts;
543 newTri->numIndexes = tri->numIndexes;
544 memcpy( newTri->verts, tri->verts, tri->numVerts * sizeof( newTri->verts[0] ) );
545 memcpy( newTri->indexes, tri->indexes, tri->numIndexes * sizeof( newTri->indexes[0] ) );
546
547 return newTri;
548 }
549
550 /*
551 =================
552 R_AllocStaticTriSurfVerts
553 =================
554 */
R_AllocStaticTriSurfVerts(srfTriangles_t * tri,int numVerts)555 void R_AllocStaticTriSurfVerts( srfTriangles_t *tri, int numVerts ) {
556 assert( tri->verts == NULL );
557 tri->verts = triVertexAllocator.Alloc( numVerts );
558 }
559
560 /*
561 =================
562 R_AllocStaticTriSurfIndexes
563 =================
564 */
R_AllocStaticTriSurfIndexes(srfTriangles_t * tri,int numIndexes)565 void R_AllocStaticTriSurfIndexes( srfTriangles_t *tri, int numIndexes ) {
566 assert( tri->indexes == NULL );
567 tri->indexes = triIndexAllocator.Alloc( numIndexes );
568 }
569
570 /*
571 =================
572 R_AllocStaticTriSurfShadowVerts
573 =================
574 */
R_AllocStaticTriSurfShadowVerts(srfTriangles_t * tri,int numVerts)575 void R_AllocStaticTriSurfShadowVerts( srfTriangles_t *tri, int numVerts ) {
576 assert( tri->shadowVertexes == NULL );
577 tri->shadowVertexes = triShadowVertexAllocator.Alloc( numVerts );
578 }
579
580 /*
581 =================
582 R_AllocStaticTriSurfPlanes
583 =================
584 */
R_AllocStaticTriSurfPlanes(srfTriangles_t * tri,int numIndexes)585 void R_AllocStaticTriSurfPlanes( srfTriangles_t *tri, int numIndexes ) {
586 if ( tri->facePlanes ) {
587 triPlaneAllocator.Free( tri->facePlanes );
588 }
589 tri->facePlanes = triPlaneAllocator.Alloc( numIndexes / 3 );
590 }
591
592 /*
593 =================
594 R_ResizeStaticTriSurfVerts
595 =================
596 */
R_ResizeStaticTriSurfVerts(srfTriangles_t * tri,int numVerts)597 void R_ResizeStaticTriSurfVerts( srfTriangles_t *tri, int numVerts ) {
598 #ifdef USE_TRI_DATA_ALLOCATOR
599 tri->verts = triVertexAllocator.Resize( tri->verts, numVerts );
600 #else
601 assert( false );
602 #endif
603 }
604
605 /*
606 =================
607 R_ResizeStaticTriSurfIndexes
608 =================
609 */
R_ResizeStaticTriSurfIndexes(srfTriangles_t * tri,int numIndexes)610 void R_ResizeStaticTriSurfIndexes( srfTriangles_t *tri, int numIndexes ) {
611 #ifdef USE_TRI_DATA_ALLOCATOR
612 tri->indexes = triIndexAllocator.Resize( tri->indexes, numIndexes );
613 #else
614 assert( false );
615 #endif
616 }
617
618 /*
619 =================
620 R_ResizeStaticTriSurfShadowVerts
621 =================
622 */
R_ResizeStaticTriSurfShadowVerts(srfTriangles_t * tri,int numVerts)623 void R_ResizeStaticTriSurfShadowVerts( srfTriangles_t *tri, int numVerts ) {
624 #ifdef USE_TRI_DATA_ALLOCATOR
625 tri->shadowVertexes = triShadowVertexAllocator.Resize( tri->shadowVertexes, numVerts );
626 #else
627 assert( false );
628 #endif
629 }
630
631 /*
632 =================
633 R_ReferenceStaticTriSurfVerts
634 =================
635 */
R_ReferenceStaticTriSurfVerts(srfTriangles_t * tri,const srfTriangles_t * reference)636 void R_ReferenceStaticTriSurfVerts( srfTriangles_t *tri, const srfTriangles_t *reference ) {
637 tri->verts = reference->verts;
638 }
639
640 /*
641 =================
642 R_ReferenceStaticTriSurfIndexes
643 =================
644 */
R_ReferenceStaticTriSurfIndexes(srfTriangles_t * tri,const srfTriangles_t * reference)645 void R_ReferenceStaticTriSurfIndexes( srfTriangles_t *tri, const srfTriangles_t *reference ) {
646 tri->indexes = reference->indexes;
647 }
648
649 /*
650 =================
651 R_FreeStaticTriSurfSilIndexes
652 =================
653 */
R_FreeStaticTriSurfSilIndexes(srfTriangles_t * tri)654 void R_FreeStaticTriSurfSilIndexes( srfTriangles_t *tri ) {
655 triSilIndexAllocator.Free( tri->silIndexes );
656 tri->silIndexes = NULL;
657 }
658
659 /*
660 ===============
661 R_RangeCheckIndexes
662
663 Check for syntactically incorrect indexes, like out of range values.
664 Does not check for semantics, like degenerate triangles.
665
666 No vertexes is acceptable if no indexes.
667 No indexes is acceptable.
668 More vertexes than are referenced by indexes are acceptable.
669 ===============
670 */
R_RangeCheckIndexes(const srfTriangles_t * tri)671 void R_RangeCheckIndexes( const srfTriangles_t *tri ) {
672 int i;
673
674 if ( tri->numIndexes < 0 ) {
675 common->Error( "R_RangeCheckIndexes: numIndexes < 0" );
676 }
677 if ( tri->numVerts < 0 ) {
678 common->Error( "R_RangeCheckIndexes: numVerts < 0" );
679 }
680
681 // must specify an integral number of triangles
682 if ( tri->numIndexes % 3 != 0 ) {
683 common->Error( "R_RangeCheckIndexes: numIndexes %% 3" );
684 }
685
686 for ( i = 0 ; i < tri->numIndexes ; i++ ) {
687 if ( tri->indexes[i] < 0 || tri->indexes[i] >= tri->numVerts ) {
688 common->Error( "R_RangeCheckIndexes: index out of range" );
689 }
690 }
691
692 // this should not be possible unless there are unused verts
693 if ( tri->numVerts > tri->numIndexes ) {
694 // FIXME: find the causes of these
695 // common->Printf( "R_RangeCheckIndexes: tri->numVerts > tri->numIndexes\n" );
696 }
697 }
698
699 /*
700 =================
701 R_BoundTriSurf
702 =================
703 */
R_BoundTriSurf(srfTriangles_t * tri)704 void R_BoundTriSurf( srfTriangles_t *tri ) {
705 SIMDProcessor->MinMax( tri->bounds[0], tri->bounds[1], tri->verts, tri->numVerts );
706 }
707
708 /*
709 =================
710 R_CreateSilRemap
711 =================
712 */
R_CreateSilRemap(const srfTriangles_t * tri)713 static int *R_CreateSilRemap( const srfTriangles_t *tri ) {
714 int c_removed, c_unique;
715 int *remap;
716 int i, j, hashKey;
717 const idDrawVert *v1, *v2;
718
719 remap = (int *)R_ClearedStaticAlloc( tri->numVerts * sizeof( remap[0] ) );
720
721 if ( !r_useSilRemap.GetBool() ) {
722 for ( i = 0 ; i < tri->numVerts ; i++ ) {
723 remap[i] = i;
724 }
725 return remap;
726 }
727
728 idHashIndex hash( 1024, tri->numVerts );
729
730 c_removed = 0;
731 c_unique = 0;
732 for ( i = 0 ; i < tri->numVerts ; i++ ) {
733 v1 = &tri->verts[i];
734
735 // see if there is an earlier vert that it can map to
736 hashKey = hash.GenerateKey( v1->xyz );
737 for ( j = hash.First( hashKey ); j >= 0; j = hash.Next( j ) ) {
738 v2 = &tri->verts[j];
739 if ( v2->xyz[0] == v1->xyz[0]
740 && v2->xyz[1] == v1->xyz[1]
741 && v2->xyz[2] == v1->xyz[2] ) {
742 c_removed++;
743 remap[i] = j;
744 break;
745 }
746 }
747 if ( j < 0 ) {
748 c_unique++;
749 remap[i] = i;
750 hash.Add( hashKey, i );
751 }
752 }
753
754 return remap;
755 }
756
757 /*
758 =================
759 R_CreateSilIndexes
760
761 Uniquing vertexes only on xyz before creating sil edges reduces
762 the edge count by about 20% on Q3 models
763 =================
764 */
R_CreateSilIndexes(srfTriangles_t * tri)765 void R_CreateSilIndexes( srfTriangles_t *tri ) {
766 int i;
767 int *remap;
768
769 if ( tri->silIndexes ) {
770 triSilIndexAllocator.Free( tri->silIndexes );
771 tri->silIndexes = NULL;
772 }
773
774 remap = R_CreateSilRemap( tri );
775
776 // remap indexes to the first one
777 tri->silIndexes = triSilIndexAllocator.Alloc( tri->numIndexes );
778 for ( i = 0; i < tri->numIndexes; i++ ) {
779 tri->silIndexes[i] = remap[tri->indexes[i]];
780 }
781
782 R_StaticFree( remap );
783 }
784
785 /*
786 =====================
787 R_CreateDupVerts
788 =====================
789 */
R_CreateDupVerts(srfTriangles_t * tri)790 void R_CreateDupVerts( srfTriangles_t *tri ) {
791 int i;
792
793 int *remap = (int *) _alloca16( tri->numVerts * sizeof( remap[0] ) );
794
795 // initialize vertex remap in case there are unused verts
796 for ( i = 0; i < tri->numVerts; i++ ) {
797 remap[i] = i;
798 }
799
800 // set the remap based on how the silhouette indexes are remapped
801 for ( i = 0; i < tri->numIndexes; i++ ) {
802 remap[tri->indexes[i]] = tri->silIndexes[i];
803 }
804
805 // create duplicate vertex index based on the vertex remap
806 int * tempDupVerts = (int *) _alloca16( tri->numVerts * 2 * sizeof( tempDupVerts[0] ) );
807 tri->numDupVerts = 0;
808 for ( i = 0; i < tri->numVerts; i++ ) {
809 if ( remap[i] != i ) {
810 tempDupVerts[tri->numDupVerts*2+0] = i;
811 tempDupVerts[tri->numDupVerts*2+1] = remap[i];
812 tri->numDupVerts++;
813 }
814 }
815
816 tri->dupVerts = triDupVertAllocator.Alloc( tri->numDupVerts * 2 );
817 memcpy( tri->dupVerts, tempDupVerts, tri->numDupVerts * 2 * sizeof( tri->dupVerts[0] ) );
818 }
819
820 /*
821 =====================
822 R_DeriveFacePlanes
823
824 Writes the facePlanes values, overwriting existing ones if present
825 =====================
826 */
R_DeriveFacePlanes(srfTriangles_t * tri)827 void R_DeriveFacePlanes( srfTriangles_t *tri ) {
828 idPlane * planes;
829
830 if ( !tri->facePlanes ) {
831 R_AllocStaticTriSurfPlanes( tri, tri->numIndexes );
832 }
833 planes = tri->facePlanes;
834
835 #if 1
836
837 SIMDProcessor->DeriveTriPlanes( planes, tri->verts, tri->numVerts, tri->indexes, tri->numIndexes );
838
839 #else
840
841 for ( int i = 0; i < tri->numIndexes; i+= 3, planes++ ) {
842 int i1, i2, i3;
843 idVec3 d1, d2, normal;
844 idVec3 *v1, *v2, *v3;
845
846 i1 = tri->indexes[i + 0];
847 i2 = tri->indexes[i + 1];
848 i3 = tri->indexes[i + 2];
849
850 v1 = &tri->verts[i1].xyz;
851 v2 = &tri->verts[i2].xyz;
852 v3 = &tri->verts[i3].xyz;
853
854 d1[0] = v2->x - v1->x;
855 d1[1] = v2->y - v1->y;
856 d1[2] = v2->z - v1->z;
857
858 d2[0] = v3->x - v1->x;
859 d2[1] = v3->y - v1->y;
860 d2[2] = v3->z - v1->z;
861
862 normal[0] = d2.y * d1.z - d2.z * d1.y;
863 normal[1] = d2.z * d1.x - d2.x * d1.z;
864 normal[2] = d2.x * d1.y - d2.y * d1.x;
865
866 float sqrLength, invLength;
867
868 sqrLength = normal.x * normal.x + normal.y * normal.y + normal.z * normal.z;
869 invLength = idMath::RSqrt( sqrLength );
870
871 (*planes)[0] = normal[0] * invLength;
872 (*planes)[1] = normal[1] * invLength;
873 (*planes)[2] = normal[2] * invLength;
874
875 planes->FitThroughPoint( *v1 );
876 }
877
878 #endif
879
880 tri->facePlanesCalculated = true;
881 }
882
883 /*
884 =====================
885 R_CreateVertexNormals
886
887 Averages together the contributions of all faces that are
888 used by a vertex, creating drawVert->normal
889 =====================
890 */
R_CreateVertexNormals(srfTriangles_t * tri)891 void R_CreateVertexNormals( srfTriangles_t *tri ) {
892 int i, j;
893 const idPlane *planes;
894
895 for ( i = 0 ; i < tri->numVerts ; i++ ) {
896 tri->verts[i].normal.Zero();
897 }
898
899 if ( !tri->facePlanes || !tri->facePlanesCalculated ) {
900 R_DeriveFacePlanes( tri );
901 }
902 if ( !tri->silIndexes ) {
903 R_CreateSilIndexes( tri );
904 }
905 planes = tri->facePlanes;
906 for ( i = 0 ; i < tri->numIndexes ; i += 3, planes++ ) {
907 for ( j = 0 ; j < 3 ; j++ ) {
908 int index = tri->silIndexes[i+j];
909 tri->verts[index].normal += planes->Normal();
910 }
911 }
912
913 // normalize and replicate from silIndexes to all indexes
914 for ( i = 0 ; i < tri->numIndexes ; i++ ) {
915 tri->verts[tri->indexes[i]].normal = tri->verts[tri->silIndexes[i]].normal;
916 tri->verts[tri->indexes[i]].normal.Normalize();
917 }
918 }
919
920 /*
921 ===============
922 R_DefineEdge
923 ===============
924 */
925 static int c_duplicatedEdges, c_tripledEdges;
926
R_DefineEdge(int v1,int v2,int planeNum)927 static void R_DefineEdge( int v1, int v2, int planeNum ) {
928 int i, hashKey;
929
930 // check for degenerate edge
931 if ( v1 == v2 ) {
932 return;
933 }
934 hashKey = silEdgeHash.GenerateKey( v1, v2 );
935 // search for a matching other side
936 for ( i = silEdgeHash.First( hashKey ); i >= 0 && i < MAX_SIL_EDGES; i = silEdgeHash.Next( i ) ) {
937 if ( silEdges[i].v1 == v1 && silEdges[i].v2 == v2 ) {
938 c_duplicatedEdges++;
939 // allow it to still create a new edge
940 continue;
941 }
942 if ( silEdges[i].v2 == v1 && silEdges[i].v1 == v2 ) {
943 if ( silEdges[i].p2 != numPlanes ) {
944 c_tripledEdges++;
945 // allow it to still create a new edge
946 continue;
947 }
948 // this is a matching back side
949 silEdges[i].p2 = planeNum;
950 return;
951 }
952
953 }
954
955 // define the new edge
956 if ( numSilEdges == MAX_SIL_EDGES ) {
957 common->DWarning( "MAX_SIL_EDGES" );
958 return;
959 }
960
961 silEdgeHash.Add( hashKey, numSilEdges );
962
963 silEdges[numSilEdges].p1 = planeNum;
964 silEdges[numSilEdges].p2 = numPlanes;
965 silEdges[numSilEdges].v1 = v1;
966 silEdges[numSilEdges].v2 = v2;
967
968 numSilEdges++;
969 }
970
971 /*
972 =================
973 SilEdgeSort
974 =================
975 */
SilEdgeSort(const void * a,const void * b)976 static int SilEdgeSort( const void *a, const void *b ) {
977 if ( ((silEdge_t *)a)->p1 < ((silEdge_t *)b)->p1 ) {
978 return -1;
979 }
980 if ( ((silEdge_t *)a)->p1 > ((silEdge_t *)b)->p1 ) {
981 return 1;
982 }
983 if ( ((silEdge_t *)a)->p2 < ((silEdge_t *)b)->p2 ) {
984 return -1;
985 }
986 if ( ((silEdge_t *)a)->p2 > ((silEdge_t *)b)->p2 ) {
987 return 1;
988 }
989 return 0;
990 }
991
992 /*
993 =================
994 R_IdentifySilEdges
995
996 If the surface will not deform, coplanar edges (polygon interiors)
997 can never create silhouette plains, and can be omited
998 =================
999 */
1000 int c_coplanarSilEdges;
1001 int c_totalSilEdges;
1002
R_IdentifySilEdges(srfTriangles_t * tri,bool omitCoplanarEdges)1003 void R_IdentifySilEdges( srfTriangles_t *tri, bool omitCoplanarEdges ) {
1004 int i;
1005 int numTris;
1006 int shared, single;
1007
1008 omitCoplanarEdges = false; // optimization doesn't work for some reason
1009
1010 numTris = tri->numIndexes / 3;
1011
1012 numSilEdges = 0;
1013 silEdgeHash.Clear();
1014 numPlanes = numTris;
1015
1016 c_duplicatedEdges = 0;
1017 c_tripledEdges = 0;
1018
1019 for ( i = 0 ; i < numTris ; i++ ) {
1020 int i1, i2, i3;
1021
1022 i1 = tri->silIndexes[ i*3 + 0 ];
1023 i2 = tri->silIndexes[ i*3 + 1 ];
1024 i3 = tri->silIndexes[ i*3 + 2 ];
1025
1026 // create the edges
1027 R_DefineEdge( i1, i2, i );
1028 R_DefineEdge( i2, i3, i );
1029 R_DefineEdge( i3, i1, i );
1030 }
1031
1032 if ( c_duplicatedEdges || c_tripledEdges ) {
1033 common->DWarning( "%i duplicated edge directions, %i tripled edges", c_duplicatedEdges, c_tripledEdges );
1034 }
1035
1036 // if we know that the vertexes aren't going
1037 // to deform, we can remove interior triangulation edges
1038 // on otherwise planar polygons.
1039 // I earlier believed that I could also remove concave
1040 // edges, because they are never silhouettes in the conventional sense,
1041 // but they are still needed to balance out all the true sil edges
1042 // for the shadow algorithm to function
1043 int c_coplanarCulled;
1044
1045 c_coplanarCulled = 0;
1046 if ( omitCoplanarEdges ) {
1047 for ( i = 0 ; i < numSilEdges ; i++ ) {
1048 int i1, i2, i3;
1049 idPlane plane;
1050 int base;
1051 int j;
1052 float d;
1053
1054 if ( silEdges[i].p2 == numPlanes ) { // the fake dangling edge
1055 continue;
1056 }
1057
1058 base = silEdges[i].p1 * 3;
1059 i1 = tri->silIndexes[ base + 0 ];
1060 i2 = tri->silIndexes[ base + 1 ];
1061 i3 = tri->silIndexes[ base + 2 ];
1062
1063 plane.FromPoints( tri->verts[i1].xyz, tri->verts[i2].xyz, tri->verts[i3].xyz );
1064
1065 // check to see if points of second triangle are not coplanar
1066 base = silEdges[i].p2 * 3;
1067 for ( j = 0 ; j < 3 ; j++ ) {
1068 i1 = tri->silIndexes[ base + j ];
1069 d = plane.Distance( tri->verts[i1].xyz );
1070 if ( d != 0 ) { // even a small epsilon causes problems
1071 break;
1072 }
1073 }
1074
1075 if ( j == 3 ) {
1076 // we can cull this sil edge
1077 memmove( &silEdges[i], &silEdges[i+1], (numSilEdges-i-1) * sizeof( silEdges[i] ) );
1078 c_coplanarCulled++;
1079 numSilEdges--;
1080 i--;
1081 }
1082 }
1083 if ( c_coplanarCulled ) {
1084 c_coplanarSilEdges += c_coplanarCulled;
1085 // common->Printf( "%i of %i sil edges coplanar culled\n", c_coplanarCulled,
1086 // c_coplanarCulled + numSilEdges );
1087 }
1088 }
1089 c_totalSilEdges += numSilEdges;
1090
1091 // sort the sil edges based on plane number
1092 qsort( silEdges, numSilEdges, sizeof( silEdges[0] ), SilEdgeSort );
1093
1094 // count up the distribution.
1095 // a perfectly built model should only have shared
1096 // edges, but most models will have some interpenetration
1097 // and dangling edges
1098 shared = 0;
1099 single = 0;
1100 for ( i = 0 ; i < numSilEdges ; i++ ) {
1101 if ( silEdges[i].p2 == numPlanes ) {
1102 single++;
1103 } else {
1104 shared++;
1105 }
1106 }
1107
1108 if ( !single ) {
1109 tri->perfectHull = true;
1110 } else {
1111 tri->perfectHull = false;
1112 }
1113
1114 tri->numSilEdges = numSilEdges;
1115 tri->silEdges = triSilEdgeAllocator.Alloc( numSilEdges );
1116 memcpy( tri->silEdges, silEdges, numSilEdges * sizeof( tri->silEdges[0] ) );
1117 }
1118
1119 /*
1120 ===============
1121 R_FaceNegativePolarity
1122
1123 Returns true if the texture polarity of the face is negative, false if it is positive or zero
1124 ===============
1125 */
R_FaceNegativePolarity(const srfTriangles_t * tri,int firstIndex)1126 static bool R_FaceNegativePolarity( const srfTriangles_t *tri, int firstIndex ) {
1127 idDrawVert *a, *b, *c;
1128 float area;
1129 float d0[5], d1[5];
1130
1131 a = tri->verts + tri->indexes[firstIndex + 0];
1132 b = tri->verts + tri->indexes[firstIndex + 1];
1133 c = tri->verts + tri->indexes[firstIndex + 2];
1134
1135 d0[3] = b->st[0] - a->st[0];
1136 d0[4] = b->st[1] - a->st[1];
1137
1138 d1[3] = c->st[0] - a->st[0];
1139 d1[4] = c->st[1] - a->st[1];
1140
1141 area = d0[3] * d1[4] - d0[4] * d1[3];
1142 if ( area >= 0 ) {
1143 return false;
1144 }
1145 return true;
1146 }
1147
1148 /*
1149 ==================
1150 R_DeriveFaceTangents
1151 ==================
1152 */
1153 typedef struct {
1154 idVec3 tangents[2];
1155 bool negativePolarity;
1156 bool degenerate;
1157 } faceTangents_t;
1158
R_DeriveFaceTangents(const srfTriangles_t * tri,faceTangents_t * faceTangents)1159 static void R_DeriveFaceTangents( const srfTriangles_t *tri, faceTangents_t *faceTangents ) {
1160 int i;
1161 int c_textureDegenerateFaces;
1162 int c_positive, c_negative;
1163 faceTangents_t *ft;
1164 idDrawVert *a, *b, *c;
1165
1166 //
1167 // calculate tangent vectors for each face in isolation
1168 //
1169 c_positive = 0;
1170 c_negative = 0;
1171 c_textureDegenerateFaces = 0;
1172 for ( i = 0 ; i < tri->numIndexes ; i+=3 ) {
1173 float area;
1174 idVec3 temp;
1175 float d0[5], d1[5];
1176
1177 ft = &faceTangents[i/3];
1178
1179 a = tri->verts + tri->indexes[i + 0];
1180 b = tri->verts + tri->indexes[i + 1];
1181 c = tri->verts + tri->indexes[i + 2];
1182
1183 d0[0] = b->xyz[0] - a->xyz[0];
1184 d0[1] = b->xyz[1] - a->xyz[1];
1185 d0[2] = b->xyz[2] - a->xyz[2];
1186 d0[3] = b->st[0] - a->st[0];
1187 d0[4] = b->st[1] - a->st[1];
1188
1189 d1[0] = c->xyz[0] - a->xyz[0];
1190 d1[1] = c->xyz[1] - a->xyz[1];
1191 d1[2] = c->xyz[2] - a->xyz[2];
1192 d1[3] = c->st[0] - a->st[0];
1193 d1[4] = c->st[1] - a->st[1];
1194
1195 area = d0[3] * d1[4] - d0[4] * d1[3];
1196 if ( fabs( area ) < 1e-20f ) {
1197 ft->negativePolarity = false;
1198 ft->degenerate = true;
1199 ft->tangents[0].Zero();
1200 ft->tangents[1].Zero();
1201 c_textureDegenerateFaces++;
1202 continue;
1203 }
1204 if ( area > 0.0f ) {
1205 ft->negativePolarity = false;
1206 c_positive++;
1207 } else {
1208 ft->negativePolarity = true;
1209 c_negative++;
1210 }
1211 ft->degenerate = false;
1212
1213 #ifdef USE_INVA
1214 float inva = area < 0.0f ? -1 : 1; // was = 1.0f / area;
1215
1216 temp[0] = (d0[0] * d1[4] - d0[4] * d1[0]) * inva;
1217 temp[1] = (d0[1] * d1[4] - d0[4] * d1[1]) * inva;
1218 temp[2] = (d0[2] * d1[4] - d0[4] * d1[2]) * inva;
1219 temp.Normalize();
1220 ft->tangents[0] = temp;
1221
1222 temp[0] = (d0[3] * d1[0] - d0[0] * d1[3]) * inva;
1223 temp[1] = (d0[3] * d1[1] - d0[1] * d1[3]) * inva;
1224 temp[2] = (d0[3] * d1[2] - d0[2] * d1[3]) * inva;
1225 temp.Normalize();
1226 ft->tangents[1] = temp;
1227 #else
1228 temp[0] = (d0[0] * d1[4] - d0[4] * d1[0]);
1229 temp[1] = (d0[1] * d1[4] - d0[4] * d1[1]);
1230 temp[2] = (d0[2] * d1[4] - d0[4] * d1[2]);
1231 temp.Normalize();
1232 ft->tangents[0] = temp;
1233
1234 temp[0] = (d0[3] * d1[0] - d0[0] * d1[3]);
1235 temp[1] = (d0[3] * d1[1] - d0[1] * d1[3]);
1236 temp[2] = (d0[3] * d1[2] - d0[2] * d1[3]);
1237 temp.Normalize();
1238 ft->tangents[1] = temp;
1239 #endif
1240 }
1241 }
1242
1243
1244
1245 /*
1246 ===================
1247 R_DuplicateMirroredVertexes
1248
1249 Modifies the surface to bust apart any verts that are shared by both positive and
1250 negative texture polarities, so tangent space smoothing at the vertex doesn't
1251 degenerate.
1252
1253 This will create some identical vertexes (which will eventually get different tangent
1254 vectors), so never optimize the resulting mesh, or it will get the mirrored edges back.
1255
1256 Reallocates tri->verts and changes tri->indexes in place
1257 Silindexes are unchanged by this.
1258
1259 sets mirroredVerts and mirroredVerts[]
1260
1261 ===================
1262 */
1263 typedef struct {
1264 bool polarityUsed[2];
1265 int negativeRemap;
1266 } tangentVert_t;
1267
R_DuplicateMirroredVertexes(srfTriangles_t * tri)1268 static void R_DuplicateMirroredVertexes( srfTriangles_t *tri ) {
1269 tangentVert_t *tverts, *vert;
1270 int i, j;
1271 int totalVerts;
1272 int numMirror;
1273
1274 tverts = (tangentVert_t *)_alloca16( tri->numVerts * sizeof( *tverts ) );
1275 memset( tverts, 0, tri->numVerts * sizeof( *tverts ) );
1276
1277 // determine texture polarity of each surface
1278
1279 // mark each vert with the polarities it uses
1280 for ( i = 0 ; i < tri->numIndexes ; i+=3 ) {
1281 int polarity;
1282
1283 polarity = R_FaceNegativePolarity( tri, i );
1284 for ( j = 0 ; j < 3 ; j++ ) {
1285 tverts[tri->indexes[i+j]].polarityUsed[ polarity ] = true;
1286 }
1287 }
1288
1289 // now create new verts as needed
1290 totalVerts = tri->numVerts;
1291 for ( i = 0 ; i < tri->numVerts ; i++ ) {
1292 vert = &tverts[i];
1293 if ( vert->polarityUsed[0] && vert->polarityUsed[1] ) {
1294 vert->negativeRemap = totalVerts;
1295 totalVerts++;
1296 }
1297 }
1298
1299 tri->numMirroredVerts = totalVerts - tri->numVerts;
1300
1301 // now create the new list
1302 if ( totalVerts == tri->numVerts ) {
1303 tri->mirroredVerts = NULL;
1304 return;
1305 }
1306
1307 tri->mirroredVerts = triMirroredVertAllocator.Alloc( tri->numMirroredVerts );
1308
1309 #ifdef USE_TRI_DATA_ALLOCATOR
1310 tri->verts = triVertexAllocator.Resize( tri->verts, totalVerts );
1311 #else
1312 idDrawVert *oldVerts = tri->verts;
1313 R_AllocStaticTriSurfVerts( tri, totalVerts );
1314 memcpy( tri->verts, oldVerts, tri->numVerts * sizeof( tri->verts[0] ) );
1315 triVertexAllocator.Free( oldVerts );
1316 #endif
1317
1318 // create the duplicates
1319 numMirror = 0;
1320 for ( i = 0 ; i < tri->numVerts ; i++ ) {
1321 j = tverts[i].negativeRemap;
1322 if ( j ) {
1323 tri->verts[j] = tri->verts[i];
1324 tri->mirroredVerts[numMirror] = i;
1325 numMirror++;
1326 }
1327 }
1328
1329 tri->numVerts = totalVerts;
1330 // change the indexes
1331 for ( i = 0 ; i < tri->numIndexes ; i++ ) {
1332 if ( tverts[tri->indexes[i]].negativeRemap &&
1333 R_FaceNegativePolarity( tri, 3*(i/3) ) ) {
1334 tri->indexes[i] = tverts[tri->indexes[i]].negativeRemap;
1335 }
1336 }
1337
1338 tri->numVerts = totalVerts;
1339 }
1340
1341 /*
1342 =================
1343 R_DeriveTangentsWithoutNormals
1344
1345 Build texture space tangents for bump mapping
1346 If a surface is deformed, this must be recalculated
1347
1348 This assumes that any mirrored vertexes have already been duplicated, so
1349 any shared vertexes will have the tangent spaces smoothed across.
1350
1351 Texture wrapping slightly complicates this, but as long as the normals
1352 are shared, and the tangent vectors are projected onto the normals, the
1353 separate vertexes should wind up with identical tangent spaces.
1354
1355 mirroring a normalmap WILL cause a slightly visible seam unless the normals
1356 are completely flat around the edge's full bilerp support.
1357
1358 Vertexes which are smooth shaded must have their tangent vectors
1359 in the same plane, which will allow a seamless
1360 rendering as long as the normal map is even on both sides of the
1361 seam.
1362
1363 A smooth shaded surface may have multiple tangent vectors at a vertex
1364 due to texture seams or mirroring, but it should only have a single
1365 normal vector.
1366
1367 Each triangle has a pair of tangent vectors in it's plane
1368
1369 Should we consider having vertexes point at shared tangent spaces
1370 to save space or speed transforms?
1371
1372 this version only handles bilateral symetry
1373 =================
1374 */
R_DeriveTangentsWithoutNormals(srfTriangles_t * tri)1375 void R_DeriveTangentsWithoutNormals( srfTriangles_t *tri ) {
1376 int i, j;
1377 faceTangents_t *faceTangents;
1378 faceTangents_t *ft;
1379 idDrawVert *vert;
1380
1381 // DG: windows only has a 1MB stack and it could happen that we try to allocate >1MB here
1382 // (in lost mission mod, game/le_hell map), causing a stack overflow
1383 // to prevent that, use heap allocation if it's >600KB
1384 size_t allocaSize = sizeof(faceTangents[0]) * tri->numIndexes/3;
1385 if(allocaSize < 600000)
1386 faceTangents = (faceTangents_t *)_alloca16( allocaSize );
1387 else
1388 faceTangents = (faceTangents_t *)Mem_Alloc16( allocaSize );
1389
1390 R_DeriveFaceTangents( tri, faceTangents );
1391
1392 // clear the tangents
1393 for ( i = 0 ; i < tri->numVerts ; i++ ) {
1394 tri->verts[i].tangents[0].Zero();
1395 tri->verts[i].tangents[1].Zero();
1396 }
1397
1398 // sum up the neighbors
1399 for ( i = 0 ; i < tri->numIndexes ; i+=3 ) {
1400 ft = &faceTangents[i/3];
1401
1402 // for each vertex on this face
1403 for ( j = 0 ; j < 3 ; j++ ) {
1404 vert = &tri->verts[tri->indexes[i+j]];
1405
1406 vert->tangents[0] += ft->tangents[0];
1407 vert->tangents[1] += ft->tangents[1];
1408 }
1409 }
1410
1411 #if 0
1412 // sum up both sides of the mirrored verts
1413 // so the S vectors exactly mirror, and the T vectors are equal
1414 for ( i = 0 ; i < tri->numMirroredVerts ; i++ ) {
1415 idDrawVert *v1, *v2;
1416
1417 v1 = &tri->verts[ tri->numVerts - tri->numMirroredVerts + i ];
1418 v2 = &tri->verts[ tri->mirroredVerts[i] ];
1419
1420 v1->tangents[0] -= v2->tangents[0];
1421 v1->tangents[1] += v2->tangents[1];
1422
1423 v2->tangents[0] = vec3_origin - v1->tangents[0];
1424 v2->tangents[1] = v1->tangents[1];
1425 }
1426 #endif
1427
1428
1429 // project the summed vectors onto the normal plane
1430 // and normalize. The tangent vectors will not necessarily
1431 // be orthogonal to each other, but they will be orthogonal
1432 // to the surface normal.
1433 for ( i = 0 ; i < tri->numVerts ; i++ ) {
1434 vert = &tri->verts[i];
1435 for ( j = 0 ; j < 2 ; j++ ) {
1436 float d;
1437
1438 d = vert->tangents[j] * vert->normal;
1439 vert->tangents[j] = vert->tangents[j] - d * vert->normal;
1440 vert->tangents[j].Normalize();
1441 }
1442 }
1443
1444 tri->tangentsCalculated = true;
1445
1446 if(allocaSize >= 600000)
1447 Mem_Free16( faceTangents );
1448 }
1449
VectorNormalizeFast2(const idVec3 & v,idVec3 & out)1450 static ID_INLINE void VectorNormalizeFast2( const idVec3 &v, idVec3 &out) {
1451 float ilength;
1452
1453 ilength = idMath::RSqrt( v[0]*v[0] + v[1]*v[1] + v[2]*v[2] );
1454 out[0] = v[0] * ilength;
1455 out[1] = v[1] * ilength;
1456 out[2] = v[2] * ilength;
1457 }
1458
1459 /*
1460 ===================
1461 R_BuildDominantTris
1462
1463 Find the largest triangle that uses each vertex
1464 ===================
1465 */
1466 typedef struct {
1467 int vertexNum;
1468 int faceNum;
1469 } indexSort_t;
1470
IndexSort(const void * a,const void * b)1471 static int IndexSort( const void *a, const void *b ) {
1472 if ( ((indexSort_t *)a)->vertexNum < ((indexSort_t *)b)->vertexNum ) {
1473 return -1;
1474 }
1475 if ( ((indexSort_t *)a)->vertexNum > ((indexSort_t *)b)->vertexNum ) {
1476 return 1;
1477 }
1478 return 0;
1479 }
1480
R_BuildDominantTris(srfTriangles_t * tri)1481 void R_BuildDominantTris( srfTriangles_t *tri ) {
1482 int i, j;
1483 dominantTri_t *dt;
1484 indexSort_t *ind = (indexSort_t *)R_StaticAlloc( tri->numIndexes * sizeof( *ind ) );
1485
1486 for ( i = 0; i < tri->numIndexes; i++ ) {
1487 ind[i].vertexNum = tri->indexes[i];
1488 ind[i].faceNum = i / 3;
1489 }
1490 qsort( ind, tri->numIndexes, sizeof( *ind ), IndexSort );
1491
1492 tri->dominantTris = dt = triDominantTrisAllocator.Alloc( tri->numVerts );
1493 memset( dt, 0, tri->numVerts * sizeof( dt[0] ) );
1494
1495 for ( i = 0; i < tri->numIndexes; i += j ) {
1496 float maxArea = 0;
1497 int vertNum = ind[i].vertexNum;
1498 for ( j = 0; i + j < tri->numIndexes && ind[i+j].vertexNum == vertNum; j++ ) {
1499 float d0[5], d1[5];
1500 idDrawVert *a, *b, *c;
1501 idVec3 normal, tangent, bitangent;
1502
1503 int i1 = tri->indexes[ind[i+j].faceNum * 3 + 0];
1504 int i2 = tri->indexes[ind[i+j].faceNum * 3 + 1];
1505 int i3 = tri->indexes[ind[i+j].faceNum * 3 + 2];
1506
1507 a = tri->verts + i1;
1508 b = tri->verts + i2;
1509 c = tri->verts + i3;
1510
1511 d0[0] = b->xyz[0] - a->xyz[0];
1512 d0[1] = b->xyz[1] - a->xyz[1];
1513 d0[2] = b->xyz[2] - a->xyz[2];
1514 d0[3] = b->st[0] - a->st[0];
1515 d0[4] = b->st[1] - a->st[1];
1516
1517 d1[0] = c->xyz[0] - a->xyz[0];
1518 d1[1] = c->xyz[1] - a->xyz[1];
1519 d1[2] = c->xyz[2] - a->xyz[2];
1520 d1[3] = c->st[0] - a->st[0];
1521 d1[4] = c->st[1] - a->st[1];
1522
1523 normal[0] = ( d1[1] * d0[2] - d1[2] * d0[1] );
1524 normal[1] = ( d1[2] * d0[0] - d1[0] * d0[2] );
1525 normal[2] = ( d1[0] * d0[1] - d1[1] * d0[0] );
1526
1527 float area = normal.Length();
1528
1529 // if this is smaller than what we already have, skip it
1530 if ( area < maxArea ) {
1531 continue;
1532 }
1533 maxArea = area;
1534
1535 if ( i1 == vertNum ) {
1536 dt[vertNum].v2 = i2;
1537 dt[vertNum].v3 = i3;
1538 } else if ( i2 == vertNum ) {
1539 dt[vertNum].v2 = i3;
1540 dt[vertNum].v3 = i1;
1541 } else {
1542 dt[vertNum].v2 = i1;
1543 dt[vertNum].v3 = i2;
1544 }
1545
1546 float len = area;
1547 if ( len < 0.001f ) {
1548 len = 0.001f;
1549 }
1550 dt[vertNum].normalizationScale[2] = 1.0f / len; // normal
1551
1552 // texture area
1553 area = d0[3] * d1[4] - d0[4] * d1[3];
1554
1555 tangent[0] = ( d0[0] * d1[4] - d0[4] * d1[0] );
1556 tangent[1] = ( d0[1] * d1[4] - d0[4] * d1[1] );
1557 tangent[2] = ( d0[2] * d1[4] - d0[4] * d1[2] );
1558 len = tangent.Length();
1559 if ( len < 0.001f ) {
1560 len = 0.001f;
1561 }
1562 dt[vertNum].normalizationScale[0] = ( area > 0 ? 1 : -1 ) / len; // tangents[0]
1563
1564 bitangent[0] = ( d0[3] * d1[0] - d0[0] * d1[3] );
1565 bitangent[1] = ( d0[3] * d1[1] - d0[1] * d1[3] );
1566 bitangent[2] = ( d0[3] * d1[2] - d0[2] * d1[3] );
1567 len = bitangent.Length();
1568 if ( len < 0.001f ) {
1569 len = 0.001f;
1570 }
1571 #ifdef DERIVE_UNSMOOTHED_BITANGENT
1572 dt[vertNum].normalizationScale[1] = ( area > 0 ? 1 : -1 );
1573 #else
1574 dt[vertNum].normalizationScale[1] = ( area > 0 ? 1 : -1 ) / len; // tangents[1]
1575 #endif
1576 }
1577 }
1578
1579 R_StaticFree( ind );
1580 }
1581
1582 /*
1583 ====================
1584 R_DeriveUnsmoothedTangents
1585
1586 Uses the single largest area triangle for each vertex, instead of smoothing over all
1587 ====================
1588 */
R_DeriveUnsmoothedTangents(srfTriangles_t * tri)1589 void R_DeriveUnsmoothedTangents( srfTriangles_t *tri ) {
1590 if ( tri->tangentsCalculated ) {
1591 return;
1592 }
1593
1594 #if 1
1595
1596 SIMDProcessor->DeriveUnsmoothedTangents( tri->verts, tri->dominantTris, tri->numVerts );
1597
1598 #else
1599
1600 for ( int i = 0 ; i < tri->numVerts ; i++ ) {
1601 idVec3 temp;
1602 float d0[5], d1[5];
1603 idDrawVert *a, *b, *c;
1604 dominantTri_t *dt = &tri->dominantTris[i];
1605
1606 a = tri->verts + i;
1607 b = tri->verts + dt->v2;
1608 c = tri->verts + dt->v3;
1609
1610 d0[0] = b->xyz[0] - a->xyz[0];
1611 d0[1] = b->xyz[1] - a->xyz[1];
1612 d0[2] = b->xyz[2] - a->xyz[2];
1613 d0[3] = b->st[0] - a->st[0];
1614 d0[4] = b->st[1] - a->st[1];
1615
1616 d1[0] = c->xyz[0] - a->xyz[0];
1617 d1[1] = c->xyz[1] - a->xyz[1];
1618 d1[2] = c->xyz[2] - a->xyz[2];
1619 d1[3] = c->st[0] - a->st[0];
1620 d1[4] = c->st[1] - a->st[1];
1621
1622 a->normal[0] = dt->normalizationScale[2] * ( d1[1] * d0[2] - d1[2] * d0[1] );
1623 a->normal[1] = dt->normalizationScale[2] * ( d1[2] * d0[0] - d1[0] * d0[2] );
1624 a->normal[2] = dt->normalizationScale[2] * ( d1[0] * d0[1] - d1[1] * d0[0] );
1625
1626 a->tangents[0][0] = dt->normalizationScale[0] * ( d0[0] * d1[4] - d0[4] * d1[0] );
1627 a->tangents[0][1] = dt->normalizationScale[0] * ( d0[1] * d1[4] - d0[4] * d1[1] );
1628 a->tangents[0][2] = dt->normalizationScale[0] * ( d0[2] * d1[4] - d0[4] * d1[2] );
1629
1630 #ifdef DERIVE_UNSMOOTHED_BITANGENT
1631 // derive the bitangent for a completely orthogonal axis,
1632 // instead of using the texture T vector
1633 a->tangents[1][0] = dt->normalizationScale[1] * ( a->normal[2] * a->tangents[0][1] - a->normal[1] * a->tangents[0][2] );
1634 a->tangents[1][1] = dt->normalizationScale[1] * ( a->normal[0] * a->tangents[0][2] - a->normal[2] * a->tangents[0][0] );
1635 a->tangents[1][2] = dt->normalizationScale[1] * ( a->normal[1] * a->tangents[0][0] - a->normal[0] * a->tangents[0][1] );
1636 #else
1637 // calculate the bitangent from the texture T vector
1638 a->tangents[1][0] = dt->normalizationScale[1] * ( d0[3] * d1[0] - d0[0] * d1[3] );
1639 a->tangents[1][1] = dt->normalizationScale[1] * ( d0[3] * d1[1] - d0[1] * d1[3] );
1640 a->tangents[1][2] = dt->normalizationScale[1] * ( d0[3] * d1[2] - d0[2] * d1[3] );
1641 #endif
1642 }
1643
1644 #endif
1645
1646 tri->tangentsCalculated = true;
1647 }
1648
1649 /*
1650 ==================
1651 R_DeriveTangents
1652
1653 This is called once for static surfaces, and every frame for deforming surfaces
1654
1655 Builds tangents, normals, and face planes
1656 ==================
1657 */
R_DeriveTangents(srfTriangles_t * tri,bool allocFacePlanes)1658 void R_DeriveTangents( srfTriangles_t *tri, bool allocFacePlanes ) {
1659 int i;
1660 idPlane *planes;
1661
1662 if ( tri->dominantTris != NULL ) {
1663 R_DeriveUnsmoothedTangents( tri );
1664 return;
1665 }
1666
1667 if ( tri->tangentsCalculated ) {
1668 return;
1669 }
1670
1671 tr.pc.c_tangentIndexes += tri->numIndexes;
1672
1673 if ( !tri->facePlanes && allocFacePlanes ) {
1674 R_AllocStaticTriSurfPlanes( tri, tri->numIndexes );
1675 }
1676 planes = tri->facePlanes;
1677
1678 #if 1
1679
1680 if ( !planes ) {
1681 planes = (idPlane *)_alloca16( ( tri->numIndexes / 3 ) * sizeof( planes[0] ) );
1682 }
1683
1684 SIMDProcessor->DeriveTangents( planes, tri->verts, tri->numVerts, tri->indexes, tri->numIndexes );
1685
1686 #else
1687
1688 for ( i = 0; i < tri->numVerts; i++ ) {
1689 tri->verts[i].normal.Zero();
1690 tri->verts[i].tangents[0].Zero();
1691 tri->verts[i].tangents[1].Zero();
1692 }
1693
1694 for ( i = 0; i < tri->numIndexes; i += 3 ) {
1695 // make face tangents
1696 float d0[5], d1[5];
1697 idDrawVert *a, *b, *c;
1698 idVec3 temp, normal, tangents[2];
1699
1700 a = tri->verts + tri->indexes[i + 0];
1701 b = tri->verts + tri->indexes[i + 1];
1702 c = tri->verts + tri->indexes[i + 2];
1703
1704 d0[0] = b->xyz[0] - a->xyz[0];
1705 d0[1] = b->xyz[1] - a->xyz[1];
1706 d0[2] = b->xyz[2] - a->xyz[2];
1707 d0[3] = b->st[0] - a->st[0];
1708 d0[4] = b->st[1] - a->st[1];
1709
1710 d1[0] = c->xyz[0] - a->xyz[0];
1711 d1[1] = c->xyz[1] - a->xyz[1];
1712 d1[2] = c->xyz[2] - a->xyz[2];
1713 d1[3] = c->st[0] - a->st[0];
1714 d1[4] = c->st[1] - a->st[1];
1715
1716 // normal
1717 temp[0] = d1[1] * d0[2] - d1[2] * d0[1];
1718 temp[1] = d1[2] * d0[0] - d1[0] * d0[2];
1719 temp[2] = d1[0] * d0[1] - d1[1] * d0[0];
1720 VectorNormalizeFast2( temp, normal );
1721
1722 #ifdef USE_INVA
1723 float area = d0[3] * d1[4] - d0[4] * d1[3];
1724 float inva = area < 0.0f ? -1 : 1; // was = 1.0f / area;
1725
1726 temp[0] = (d0[0] * d1[4] - d0[4] * d1[0]) * inva;
1727 temp[1] = (d0[1] * d1[4] - d0[4] * d1[1]) * inva;
1728 temp[2] = (d0[2] * d1[4] - d0[4] * d1[2]) * inva;
1729 VectorNormalizeFast2( temp, tangents[0] );
1730
1731 temp[0] = (d0[3] * d1[0] - d0[0] * d1[3]) * inva;
1732 temp[1] = (d0[3] * d1[1] - d0[1] * d1[3]) * inva;
1733 temp[2] = (d0[3] * d1[2] - d0[2] * d1[3]) * inva;
1734 VectorNormalizeFast2( temp, tangents[1] );
1735 #else
1736 temp[0] = (d0[0] * d1[4] - d0[4] * d1[0]);
1737 temp[1] = (d0[1] * d1[4] - d0[4] * d1[1]);
1738 temp[2] = (d0[2] * d1[4] - d0[4] * d1[2]);
1739 VectorNormalizeFast2( temp, tangents[0] );
1740
1741 temp[0] = (d0[3] * d1[0] - d0[0] * d1[3]);
1742 temp[1] = (d0[3] * d1[1] - d0[1] * d1[3]);
1743 temp[2] = (d0[3] * d1[2] - d0[2] * d1[3]);
1744 VectorNormalizeFast2( temp, tangents[1] );
1745 #endif
1746
1747 // sum up the tangents and normals for each vertex on this face
1748 for ( int j = 0 ; j < 3 ; j++ ) {
1749 vert = &tri->verts[tri->indexes[i+j]];
1750 vert->normal += normal;
1751 vert->tangents[0] += tangents[0];
1752 vert->tangents[1] += tangents[1];
1753 }
1754
1755 if ( planes ) {
1756 planes->Normal() = normal;
1757 planes->FitThroughPoint( a->xyz );
1758 planes++;
1759 }
1760 }
1761
1762 #endif
1763
1764 #if 0
1765
1766 if ( tri->silIndexes != NULL ) {
1767 for ( i = 0; i < tri->numVerts; i++ ) {
1768 tri->verts[i].normal.Zero();
1769 }
1770 for ( i = 0; i < tri->numIndexes; i++ ) {
1771 tri->verts[tri->silIndexes[i]].normal += planes[i/3].Normal();
1772 }
1773 for ( i = 0 ; i < tri->numIndexes ; i++ ) {
1774 tri->verts[tri->indexes[i]].normal = tri->verts[tri->silIndexes[i]].normal;
1775 }
1776 }
1777
1778 #else
1779
1780 int *dupVerts = tri->dupVerts;
1781 idDrawVert *verts = tri->verts;
1782
1783 // add the normal of a duplicated vertex to the normal of the first vertex with the same XYZ
1784 for ( i = 0; i < tri->numDupVerts; i++ ) {
1785 verts[dupVerts[i*2+0]].normal += verts[dupVerts[i*2+1]].normal;
1786 }
1787
1788 // copy vertex normals to duplicated vertices
1789 for ( i = 0; i < tri->numDupVerts; i++ ) {
1790 verts[dupVerts[i*2+1]].normal = verts[dupVerts[i*2+0]].normal;
1791 }
1792
1793 #endif
1794
1795 #if 0
1796 // sum up both sides of the mirrored verts
1797 // so the S vectors exactly mirror, and the T vectors are equal
1798 for ( i = 0 ; i < tri->numMirroredVerts ; i++ ) {
1799 idDrawVert *v1, *v2;
1800
1801 v1 = &tri->verts[ tri->numVerts - tri->numMirroredVerts + i ];
1802 v2 = &tri->verts[ tri->mirroredVerts[i] ];
1803
1804 v1->tangents[0] -= v2->tangents[0];
1805 v1->tangents[1] += v2->tangents[1];
1806
1807 v2->tangents[0] = vec3_origin - v1->tangents[0];
1808 v2->tangents[1] = v1->tangents[1];
1809 }
1810 #endif
1811
1812 // project the summed vectors onto the normal plane
1813 // and normalize. The tangent vectors will not necessarily
1814 // be orthogonal to each other, but they will be orthogonal
1815 // to the surface normal.
1816 #if 1
1817
1818 SIMDProcessor->NormalizeTangents( tri->verts, tri->numVerts );
1819
1820 #else
1821
1822 for ( i = 0 ; i < tri->numVerts ; i++ ) {
1823 idDrawVert *vert = &tri->verts[i];
1824
1825 VectorNormalizeFast2( vert->normal, vert->normal );
1826
1827 // project the tangent vectors
1828 for ( int j = 0 ; j < 2 ; j++ ) {
1829 float d;
1830
1831 d = vert->tangents[j] * vert->normal;
1832 vert->tangents[j] = vert->tangents[j] - d * vert->normal;
1833 VectorNormalizeFast2( vert->tangents[j], vert->tangents[j] );
1834 }
1835 }
1836
1837 #endif
1838
1839 tri->tangentsCalculated = true;
1840 tri->facePlanesCalculated = true;
1841 }
1842
1843 /*
1844 =================
1845 R_RemoveDuplicatedTriangles
1846
1847 silIndexes must have already been calculated
1848
1849 silIndexes are used instead of indexes, because duplicated
1850 triangles could have different texture coordinates.
1851 =================
1852 */
R_RemoveDuplicatedTriangles(srfTriangles_t * tri)1853 void R_RemoveDuplicatedTriangles( srfTriangles_t *tri ) {
1854 int c_removed;
1855 int i, j, r;
1856 int a, b, c;
1857
1858 c_removed = 0;
1859
1860 // check for completely duplicated triangles
1861 // any rotation of the triangle is still the same, but a mirroring
1862 // is considered different
1863 for ( i = 0 ; i < tri->numIndexes ; i+=3 ) {
1864 for ( r = 0 ; r < 3 ; r++ ) {
1865 a = tri->silIndexes[i+r];
1866 b = tri->silIndexes[i+(r+1)%3];
1867 c = tri->silIndexes[i+(r+2)%3];
1868 for ( j = i + 3 ; j < tri->numIndexes ; j+=3 ) {
1869 if ( tri->silIndexes[j] == a && tri->silIndexes[j+1] == b && tri->silIndexes[j+2] == c ) {
1870 c_removed++;
1871 memmove( tri->indexes + j, tri->indexes + j + 3, ( tri->numIndexes - j - 3 ) * sizeof( tri->indexes[0] ) );
1872 memmove( tri->silIndexes + j, tri->silIndexes + j + 3, ( tri->numIndexes - j - 3 ) * sizeof( tri->silIndexes[0] ) );
1873 tri->numIndexes -= 3;
1874 j -= 3;
1875 }
1876 }
1877 }
1878 }
1879
1880 if ( c_removed ) {
1881 common->Printf( "removed %i duplicated triangles\n", c_removed );
1882 }
1883
1884 }
1885
1886 /*
1887 =================
1888 R_RemoveDegenerateTriangles
1889
1890 silIndexes must have already been calculated
1891 =================
1892 */
R_RemoveDegenerateTriangles(srfTriangles_t * tri)1893 void R_RemoveDegenerateTriangles( srfTriangles_t *tri ) {
1894 int c_removed;
1895 int i;
1896 int a, b, c;
1897
1898 // check for completely degenerate triangles
1899 c_removed = 0;
1900 for ( i = 0; i < tri->numIndexes; i += 3 ) {
1901 a = tri->silIndexes[i];
1902 b = tri->silIndexes[i+1];
1903 c = tri->silIndexes[i+2];
1904 if ( a == b || a == c || b == c ) {
1905 c_removed++;
1906 memmove( tri->indexes + i, tri->indexes + i + 3, ( tri->numIndexes - i - 3 ) * sizeof( tri->indexes[0] ) );
1907 if ( tri->silIndexes ) {
1908 memmove( tri->silIndexes + i, tri->silIndexes + i + 3, ( tri->numIndexes - i - 3 ) * sizeof( tri->silIndexes[0] ) );
1909 }
1910 tri->numIndexes -= 3;
1911 i -= 3;
1912 }
1913 }
1914
1915 // this doesn't free the memory used by the unused verts
1916
1917 if ( c_removed ) {
1918 common->Printf( "removed %i degenerate triangles\n", c_removed );
1919 }
1920 }
1921
1922 /*
1923 =================
1924 R_TestDegenerateTextureSpace
1925 =================
1926 */
R_TestDegenerateTextureSpace(srfTriangles_t * tri)1927 void R_TestDegenerateTextureSpace( srfTriangles_t *tri ) {
1928 int c_degenerate;
1929 int i;
1930
1931 // check for triangles with a degenerate texture space
1932 c_degenerate = 0;
1933 for ( i = 0; i < tri->numIndexes; i += 3 ) {
1934 const idDrawVert &a = tri->verts[tri->indexes[i+0]];
1935 const idDrawVert &b = tri->verts[tri->indexes[i+1]];
1936 const idDrawVert &c = tri->verts[tri->indexes[i+2]];
1937
1938 if ( a.st == b.st || b.st == c.st || c.st == a.st ) {
1939 c_degenerate++;
1940 }
1941 }
1942
1943 if ( c_degenerate ) {
1944 // common->Printf( "%d triangles with a degenerate texture space\n", c_degenerate );
1945 }
1946 }
1947
1948 /*
1949 =================
1950 R_RemoveUnusedVerts
1951 =================
1952 */
R_RemoveUnusedVerts(srfTriangles_t * tri)1953 void R_RemoveUnusedVerts( srfTriangles_t *tri ) {
1954 int i;
1955 int *mark;
1956 int index;
1957 int used;
1958
1959 mark = (int *)R_ClearedStaticAlloc( tri->numVerts * sizeof( *mark ) );
1960
1961 for ( i = 0 ; i < tri->numIndexes ; i++ ) {
1962 index = tri->indexes[i];
1963 if ( index < 0 || index >= tri->numVerts ) {
1964 common->Error( "R_RemoveUnusedVerts: bad index" );
1965 }
1966 mark[ index ] = 1;
1967
1968 if ( tri->silIndexes ) {
1969 index = tri->silIndexes[i];
1970 if ( index < 0 || index >= tri->numVerts ) {
1971 common->Error( "R_RemoveUnusedVerts: bad index" );
1972 }
1973 mark[ index ] = 1;
1974 }
1975 }
1976
1977 used = 0;
1978 for ( i = 0 ; i < tri->numVerts ; i++ ) {
1979 if ( !mark[i] ) {
1980 continue;
1981 }
1982 mark[i] = used + 1;
1983 used++;
1984 }
1985
1986 if ( used != tri->numVerts ) {
1987 for ( i = 0 ; i < tri->numIndexes ; i++ ) {
1988 tri->indexes[i] = mark[ tri->indexes[i] ] - 1;
1989 if ( tri->silIndexes ) {
1990 tri->silIndexes[i] = mark[ tri->silIndexes[i] ] - 1;
1991 }
1992 }
1993 tri->numVerts = used;
1994
1995 for ( i = 0 ; i < tri->numVerts ; i++ ) {
1996 index = mark[ i ];
1997 if ( !index ) {
1998 continue;
1999 }
2000 tri->verts[ index - 1 ] = tri->verts[i];
2001 }
2002
2003 // this doesn't realloc the arrays to save the memory used by the unused verts
2004 }
2005
2006 R_StaticFree( mark );
2007 }
2008
2009 /*
2010 =================
2011 R_MergeSurfaceList
2012
2013 Only deals with vertexes and indexes, not silhouettes, planes, etc.
2014 Does NOT perform a cleanup triangles, so there may be duplicated verts in the result.
2015 =================
2016 */
R_MergeSurfaceList(const srfTriangles_t ** surfaces,int numSurfaces)2017 srfTriangles_t *R_MergeSurfaceList( const srfTriangles_t **surfaces, int numSurfaces ) {
2018 srfTriangles_t *newTri;
2019 const srfTriangles_t *tri;
2020 int i, j;
2021 int totalVerts;
2022 int totalIndexes;
2023
2024 totalVerts = 0;
2025 totalIndexes = 0;
2026 for ( i = 0 ; i < numSurfaces ; i++ ) {
2027 totalVerts += surfaces[i]->numVerts;
2028 totalIndexes += surfaces[i]->numIndexes;
2029 }
2030
2031 newTri = R_AllocStaticTriSurf();
2032 newTri->numVerts = totalVerts;
2033 newTri->numIndexes = totalIndexes;
2034 R_AllocStaticTriSurfVerts( newTri, newTri->numVerts );
2035 R_AllocStaticTriSurfIndexes( newTri, newTri->numIndexes );
2036
2037 totalVerts = 0;
2038 totalIndexes = 0;
2039 for ( i = 0 ; i < numSurfaces ; i++ ) {
2040 tri = surfaces[i];
2041 memcpy( newTri->verts + totalVerts, tri->verts, tri->numVerts * sizeof( *tri->verts ) );
2042 for ( j = 0 ; j < tri->numIndexes ; j++ ) {
2043 newTri->indexes[ totalIndexes + j ] = totalVerts + tri->indexes[j];
2044 }
2045 totalVerts += tri->numVerts;
2046 totalIndexes += tri->numIndexes;
2047 }
2048
2049 return newTri;
2050 }
2051
2052 /*
2053 =================
2054 R_MergeTriangles
2055
2056 Only deals with vertexes and indexes, not silhouettes, planes, etc.
2057 Does NOT perform a cleanup triangles, so there may be duplicated verts in the result.
2058 =================
2059 */
R_MergeTriangles(const srfTriangles_t * tri1,const srfTriangles_t * tri2)2060 srfTriangles_t *R_MergeTriangles( const srfTriangles_t *tri1, const srfTriangles_t *tri2 ) {
2061 const srfTriangles_t *tris[2];
2062
2063 tris[0] = tri1;
2064 tris[1] = tri2;
2065
2066 return R_MergeSurfaceList( tris, 2 );
2067 }
2068
2069 /*
2070 =================
2071 R_ReverseTriangles
2072
2073 Lit two sided surfaces need to have the triangles actually duplicated,
2074 they can't just turn on two sided lighting, because the normal and tangents
2075 are wrong on the other sides.
2076
2077 This should be called before R_CleanupTriangles
2078 =================
2079 */
R_ReverseTriangles(srfTriangles_t * tri)2080 void R_ReverseTriangles( srfTriangles_t *tri ) {
2081 int i;
2082
2083 // flip the normal on each vertex
2084 // If the surface is going to have generated normals, this won't matter,
2085 // but if it has explicit normals, this will keep it on the correct side
2086 for ( i = 0 ; i < tri->numVerts ; i++ ) {
2087 tri->verts[i].normal = vec3_origin - tri->verts[i].normal;
2088 }
2089
2090 // flip the index order to make them back sided
2091 for ( i = 0 ; i < tri->numIndexes ; i+= 3 ) {
2092 glIndex_t temp;
2093
2094 temp = tri->indexes[ i + 0 ];
2095 tri->indexes[ i + 0 ] = tri->indexes[ i + 1 ];
2096 tri->indexes[ i + 1 ] = temp;
2097 }
2098 }
2099
2100 /*
2101 =================
2102 R_CleanupTriangles
2103
2104 FIXME: allow createFlat and createSmooth normals, as well as explicit
2105 =================
2106 */
R_CleanupTriangles(srfTriangles_t * tri,bool createNormals,bool identifySilEdges,bool useUnsmoothedTangents)2107 void R_CleanupTriangles( srfTriangles_t *tri, bool createNormals, bool identifySilEdges, bool useUnsmoothedTangents ) {
2108 R_RangeCheckIndexes( tri );
2109
2110 R_CreateSilIndexes( tri );
2111
2112 // R_RemoveDuplicatedTriangles( tri ); // this may remove valid overlapped transparent triangles
2113
2114 R_RemoveDegenerateTriangles( tri );
2115
2116 R_TestDegenerateTextureSpace( tri );
2117
2118 // R_RemoveUnusedVerts( tri );
2119
2120 if ( identifySilEdges ) {
2121 R_IdentifySilEdges( tri, true ); // assume it is non-deformable, and omit coplanar edges
2122 }
2123
2124 // bust vertexes that share a mirrored edge into separate vertexes
2125 R_DuplicateMirroredVertexes( tri );
2126
2127 // optimize the index order (not working?)
2128 // R_OrderIndexes( tri->numIndexes, tri->indexes );
2129
2130 R_CreateDupVerts( tri );
2131
2132 R_BoundTriSurf( tri );
2133
2134 if ( useUnsmoothedTangents ) {
2135 R_BuildDominantTris( tri );
2136 R_DeriveUnsmoothedTangents( tri );
2137 } else if ( !createNormals ) {
2138 R_DeriveFacePlanes( tri );
2139 R_DeriveTangentsWithoutNormals( tri );
2140 } else {
2141 R_DeriveTangents( tri );
2142 }
2143 }
2144
2145 /*
2146 ===================================================================================
2147
2148 DEFORMED SURFACES
2149
2150 ===================================================================================
2151 */
2152
2153 /*
2154 ===================
2155 R_BuildDeformInfo
2156 ===================
2157 */
R_BuildDeformInfo(int numVerts,const idDrawVert * verts,int numIndexes,const int * indexes,bool useUnsmoothedTangents)2158 deformInfo_t *R_BuildDeformInfo( int numVerts, const idDrawVert *verts, int numIndexes, const int *indexes, bool useUnsmoothedTangents ) {
2159 deformInfo_t *deform;
2160 srfTriangles_t tri;
2161 int i;
2162
2163 memset( &tri, 0, sizeof( tri ) );
2164
2165 tri.numVerts = numVerts;
2166 R_AllocStaticTriSurfVerts( &tri, tri.numVerts );
2167 SIMDProcessor->Memcpy( tri.verts, verts, tri.numVerts * sizeof( tri.verts[0] ) );
2168
2169 tri.numIndexes = numIndexes;
2170 R_AllocStaticTriSurfIndexes( &tri, tri.numIndexes );
2171
2172 // don't memcpy, so we can change the index type from int to short without changing the interface
2173 for ( i = 0 ; i < tri.numIndexes ; i++ ) {
2174 tri.indexes[i] = indexes[i];
2175 }
2176
2177 R_RangeCheckIndexes( &tri );
2178 R_CreateSilIndexes( &tri );
2179
2180 // should we order the indexes here?
2181
2182 // R_RemoveDuplicatedTriangles( &tri );
2183 // R_RemoveDegenerateTriangles( &tri );
2184 // R_RemoveUnusedVerts( &tri );
2185 R_IdentifySilEdges( &tri, false ); // we cannot remove coplanar edges, because
2186 // they can deform to silhouettes
2187
2188 R_DuplicateMirroredVertexes( &tri ); // split mirror points into multiple points
2189
2190 R_CreateDupVerts( &tri );
2191
2192 if ( useUnsmoothedTangents ) {
2193 R_BuildDominantTris( &tri );
2194 }
2195
2196 deform = (deformInfo_t *)R_ClearedStaticAlloc( sizeof( *deform ) );
2197
2198 deform->numSourceVerts = numVerts;
2199 deform->numOutputVerts = tri.numVerts;
2200
2201 deform->numIndexes = numIndexes;
2202 deform->indexes = tri.indexes;
2203
2204 deform->silIndexes = tri.silIndexes;
2205
2206 deform->numSilEdges = tri.numSilEdges;
2207 deform->silEdges = tri.silEdges;
2208
2209 deform->dominantTris = tri.dominantTris;
2210
2211 deform->numMirroredVerts = tri.numMirroredVerts;
2212 deform->mirroredVerts = tri.mirroredVerts;
2213
2214 deform->numDupVerts = tri.numDupVerts;
2215 deform->dupVerts = tri.dupVerts;
2216
2217 if ( tri.verts ) {
2218 triVertexAllocator.Free( tri.verts );
2219 }
2220
2221 if ( tri.facePlanes ) {
2222 triPlaneAllocator.Free( tri.facePlanes );
2223 }
2224
2225 return deform;
2226 }
2227
2228 /*
2229 ===================
2230 R_FreeDeformInfo
2231 ===================
2232 */
R_FreeDeformInfo(deformInfo_t * deformInfo)2233 void R_FreeDeformInfo( deformInfo_t *deformInfo ) {
2234 if ( deformInfo->indexes != NULL ) {
2235 triIndexAllocator.Free( deformInfo->indexes );
2236 }
2237 if ( deformInfo->silIndexes != NULL ) {
2238 triSilIndexAllocator.Free( deformInfo->silIndexes );
2239 }
2240 if ( deformInfo->silEdges != NULL ) {
2241 triSilEdgeAllocator.Free( deformInfo->silEdges );
2242 }
2243 if ( deformInfo->dominantTris != NULL ) {
2244 triDominantTrisAllocator.Free( deformInfo->dominantTris );
2245 }
2246 if ( deformInfo->mirroredVerts != NULL ) {
2247 triMirroredVertAllocator.Free( deformInfo->mirroredVerts );
2248 }
2249 if ( deformInfo->dupVerts != NULL ) {
2250 triDupVertAllocator.Free( deformInfo->dupVerts );
2251 }
2252 R_StaticFree( deformInfo );
2253 }
2254
2255 /*
2256 ===================
2257 R_DeformInfoMemoryUsed
2258 ===================
2259 */
R_DeformInfoMemoryUsed(deformInfo_t * deformInfo)2260 int R_DeformInfoMemoryUsed( deformInfo_t *deformInfo ) {
2261 int total = 0;
2262
2263 if ( deformInfo->indexes != NULL ) {
2264 total += deformInfo->numIndexes * sizeof( deformInfo->indexes[0] );
2265 }
2266 if ( deformInfo->silIndexes != NULL ) {
2267 total += deformInfo->numIndexes * sizeof( deformInfo->silIndexes[0] );
2268 }
2269 if ( deformInfo->silEdges != NULL ) {
2270 total += deformInfo->numSilEdges * sizeof( deformInfo->silEdges[0] );
2271 }
2272 if ( deformInfo->dominantTris != NULL ) {
2273 total += deformInfo->numSourceVerts * sizeof( deformInfo->dominantTris[0] );
2274 }
2275 if ( deformInfo->mirroredVerts != NULL ) {
2276 total += deformInfo->numMirroredVerts * sizeof( deformInfo->mirroredVerts[0] );
2277 }
2278 if ( deformInfo->dupVerts != NULL ) {
2279 total += deformInfo->numDupVerts * sizeof( deformInfo->dupVerts[0] );
2280 }
2281
2282 total += sizeof( *deformInfo );
2283 return total;
2284 }
2285