tools/quake3/q3map2/tjunction.c

   1 /*\r
   2 Copyright (C) 1999-2007 id Software, Inc. and contributors.\r
   3 For a list of contributors, see the accompanying CONTRIBUTORS file.\r
   4 \r
   5 This file is part of GtkRadiant.\r
   6 \r
   7 GtkRadiant is free software; you can redistribute it and/or modify\r
   8 it under the terms of the GNU General Public License as published by\r
   9 the Free Software Foundation; either version 2 of the License, or\r
  10 (at your option) any later version.\r
  11 \r
  12 GtkRadiant is distributed in the hope that it will be useful,\r
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of\r
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\r
  15 GNU General Public License for more details.\r
  16 \r
  17 You should have received a copy of the GNU General Public License\r
  18 along with GtkRadiant; if not, write to the Free Software\r
  19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA\r
  20 \r
  21 ----------------------------------------------------------------------------------\r
  22 \r
  23 This code has been altered significantly from its original form, to support\r
  24 several games based on the Quake III Arena engine, in the form of "Q3Map2."\r
  25 \r
  26 ------------------------------------------------------------------------------- */\r
  27 \r
  28 \r
  29 \r
  30 /* marker */\r
  31 #define TJUNCTION_C\r
  32 \r
  33 \r
  34 \r
  35 /* dependencies */\r
  36 #include "q3map2.h"\r
  37 \r
  38 \r
  39 \r
  40 \r
  41 typedef struct edgePoint_s {\r
  42         float           intercept;\r
  43         vec3_t          xyz;\r
  44         struct edgePoint_s      *prev, *next;\r
  45 } edgePoint_t;\r
  46 \r
  47 typedef struct edgeLine_s {\r
  48         vec3_t          normal1;\r
  49         float           dist1;\r
  50         \r
  51         vec3_t          normal2;\r
  52         float           dist2;\r
  53         \r
  54         vec3_t          origin;\r
  55         vec3_t          dir;\r
  56 \r
  57         edgePoint_t     chain;          // unused element of doubly linked list\r
  58 } edgeLine_t;\r
  59 \r
  60 typedef struct {\r
  61         float           length;\r
  62         bspDrawVert_t   *dv[2];\r
  63 } originalEdge_t;\r
  64 \r
  65 #define MAX_ORIGINAL_EDGES      0x10000\r
  66 originalEdge_t  originalEdges[MAX_ORIGINAL_EDGES];\r
  67 int                             numOriginalEdges;\r
  68 \r
  69 \r
  70 #define MAX_EDGE_LINES          0x10000\r
  71 edgeLine_t              edgeLines[MAX_EDGE_LINES];\r
  72 int                             numEdgeLines;\r
  73 \r
  74 int                             c_degenerateEdges;\r
  75 int                             c_addedVerts;\r
  76 int                             c_totalVerts;\r
  77 \r
  78 int                             c_natural, c_rotate, c_cant;\r
  79 \r
  80 // these should be whatever epsilon we actually expect,\r
  81 // plus SNAP_INT_TO_FLOAT \r
  82 #define LINE_POSITION_EPSILON   0.25\r
  83 #define POINT_ON_LINE_EPSILON   0.25\r
  84 \r
  85 /*\r
  86 ====================\r
  87 InsertPointOnEdge\r
  88 ====================\r
  89 */\r
  90 void InsertPointOnEdge( vec3_t v, edgeLine_t *e ) {\r
  91         vec3_t          delta;\r
  92         float           d;\r
  93         edgePoint_t     *p, *scan;\r
  94 \r
  95         VectorSubtract( v, e->origin, delta );\r
  96         d = DotProduct( delta, e->dir );\r
  97 \r
  98         p = safe_malloc( sizeof(edgePoint_t) );\r
  99         p->intercept = d;\r
 100         VectorCopy( v, p->xyz );\r
 101 \r
 102         if ( e->chain.next == &e->chain ) {\r
 103                 e->chain.next = e->chain.prev = p;\r
 104                 p->next = p->prev = &e->chain;\r
 105                 return;\r
 106         }\r
 107 \r
 108         scan = e->chain.next;\r
 109         for ( ; scan != &e->chain ; scan = scan->next ) {\r
 110                 d = p->intercept - scan->intercept;\r
 111                 if ( d > -LINE_POSITION_EPSILON && d < LINE_POSITION_EPSILON ) {\r
 112                         free( p );\r
 113                         return;         // the point is already set\r
 114                 }\r
 115 \r
 116                 if ( p->intercept < scan->intercept ) {\r
 117                         // insert here\r
 118                         p->prev = scan->prev;\r
 119                         p->next = scan;\r
 120                         scan->prev->next = p;\r
 121                         scan->prev = p;\r
 122                         return;\r
 123                 }\r
 124         }\r
 125 \r
 126         // add at the end\r
 127         p->prev = scan->prev;\r
 128         p->next = scan;\r
 129         scan->prev->next = p;\r
 130         scan->prev = p;\r
 131 }\r
 132 \r
 133 \r
 134 /*\r
 135 ====================\r
 136 AddEdge\r
 137 ====================\r
 138 */\r
 139 int AddEdge( vec3_t v1, vec3_t v2, qboolean createNonAxial ) {\r
 140         int                     i;\r
 141         edgeLine_t      *e;\r
 142         float           d;\r
 143         vec3_t          dir;\r
 144 \r
 145         VectorSubtract( v2, v1, dir );\r
 146         d = VectorNormalize( dir, dir );\r
 147         if ( d < 0.1 ) {\r
 148                 // if we added a 0 length vector, it would make degenerate planes\r
 149                 c_degenerateEdges++;\r
 150                 return -1;\r
 151         }\r
 152 \r
 153         if ( !createNonAxial ) {\r
 154                 if ( fabs( dir[0] + dir[1] + dir[2] ) != 1.0 ) {\r
 155                         if ( numOriginalEdges == MAX_ORIGINAL_EDGES ) {\r
 156                                 Error( "MAX_ORIGINAL_EDGES" );\r
 157                         }\r
 158                         originalEdges[ numOriginalEdges ].dv[0] = (bspDrawVert_t *)v1;\r
 159                         originalEdges[ numOriginalEdges ].dv[1] = (bspDrawVert_t *)v2;\r
 160                         originalEdges[ numOriginalEdges ].length = d;\r
 161                         numOriginalEdges++;\r
 162                         return -1;\r
 163                 }\r
 164         }\r
 165 \r
 166         for ( i = 0 ; i < numEdgeLines ; i++ ) {\r
 167                 e = &edgeLines[i];\r
 168 \r
 169                 d = DotProduct( v1, e->normal1 ) - e->dist1;\r
 170                 if ( d < -POINT_ON_LINE_EPSILON || d > POINT_ON_LINE_EPSILON ) {\r
 171                         continue;\r
 172                 }\r
 173                 d = DotProduct( v1, e->normal2 ) - e->dist2;\r
 174                 if ( d < -POINT_ON_LINE_EPSILON || d > POINT_ON_LINE_EPSILON ) {\r
 175                         continue;\r
 176                 }\r
 177 \r
 178                 d = DotProduct( v2, e->normal1 ) - e->dist1;\r
 179                 if ( d < -POINT_ON_LINE_EPSILON || d > POINT_ON_LINE_EPSILON ) {\r
 180                         continue;\r
 181                 }\r
 182                 d = DotProduct( v2, e->normal2 ) - e->dist2;\r
 183                 if ( d < -POINT_ON_LINE_EPSILON || d > POINT_ON_LINE_EPSILON ) {\r
 184                         continue;\r
 185                 }\r
 186 \r
 187                 // this is the edge\r
 188                 InsertPointOnEdge( v1, e );\r
 189                 InsertPointOnEdge( v2, e );\r
 190                 return i;\r
 191         }\r
 192 \r
 193         // create a new edge\r
 194         if ( numEdgeLines >= MAX_EDGE_LINES ) {\r
 195                 Error( "MAX_EDGE_LINES" );\r
 196         }\r
 197 \r
 198         e = &edgeLines[ numEdgeLines ];\r
 199         numEdgeLines++;\r
 200 \r
 201         e->chain.next = e->chain.prev = &e->chain;\r
 202 \r
 203         VectorCopy( v1, e->origin );\r
 204         VectorCopy( dir, e->dir );\r
 205 \r
 206         MakeNormalVectors( e->dir, e->normal1, e->normal2 );\r
 207         e->dist1 = DotProduct( e->origin, e->normal1 );\r
 208         e->dist2 = DotProduct( e->origin, e->normal2 );\r
 209 \r
 210         InsertPointOnEdge( v1, e );\r
 211         InsertPointOnEdge( v2, e );\r
 212 \r
 213         return numEdgeLines - 1;\r
 214 }\r
 215 \r
 216 \r
 217 \r
 218 /*\r
 219 AddSurfaceEdges()\r
 220 adds a surface's edges\r
 221 */\r
 222 \r
 223 void AddSurfaceEdges( mapDrawSurface_t *ds )\r
 224 {\r
 225         int             i;\r
 226         \r
 227 \r
 228         for( i = 0; i < ds->numVerts; i++ )\r
 229         {\r
 230                 /* save the edge number in the lightmap field so we don't need to look it up again */\r
 231                 ds->verts[i].lightmap[ 0 ][ 0 ] = \r
 232                         AddEdge( ds->verts[ i ].xyz, ds->verts[ (i + 1) % ds->numVerts ].xyz, qfalse );\r
 233         }\r
 234 }\r
 235 \r
 236 \r
 237 \r
 238 /*\r
 239 ColinearEdge()\r
 240 determines if an edge is colinear\r
 241 */\r
 242 \r
 243 qboolean ColinearEdge( vec3_t v1, vec3_t v2, vec3_t v3 )\r
 244 {\r
 245         vec3_t  midpoint, dir, offset, on;\r
 246         float   d;\r
 247 \r
 248         VectorSubtract( v2, v1, midpoint );\r
 249         VectorSubtract( v3, v1, dir );\r
 250         d = VectorNormalize( dir, dir );\r
 251         if ( d == 0 ) {\r
 252                 return qfalse;  // degenerate\r
 253         }\r
 254 \r
 255         d = DotProduct( midpoint, dir );\r
 256         VectorScale( dir, d, on );\r
 257         VectorSubtract( midpoint, on, offset );\r
 258         d = VectorLength ( offset );\r
 259 \r
 260         if ( d < 0.1 ) {\r
 261                 return qtrue;\r
 262         }\r
 263 \r
 264         return qfalse;\r
 265 }\r
 266 \r
 267 \r
 268 \r
 269 /*\r
 270 ====================\r
 271 AddPatchEdges\r
 272 \r
 273 Add colinear border edges, which will fix some classes of patch to\r
 274 brush tjunctions\r
 275 ====================\r
 276 */\r
 277 void AddPatchEdges( mapDrawSurface_t *ds ) {\r
 278         int             i;\r
 279         float   *v1, *v2, *v3;\r
 280 \r
 281         for ( i = 0 ; i < ds->patchWidth - 2; i+=2 ) {\r
 282                 v1 = ds->verts[ i ].xyz;\r
 283                 v2 = ds->verts[ i + 1 ].xyz;\r
 284                 v3 = ds->verts[ i + 2 ].xyz;\r
 285 \r
 286                 // if v2 is the midpoint of v1 to v3, add an edge from v1 to v3\r
 287                 if ( ColinearEdge( v1, v2, v3 ) ) {\r
 288                         AddEdge( v1, v3, qfalse );\r
 289                 }\r
 290 \r
 291                 v1 = ds->verts[ ( ds->patchHeight - 1 ) * ds->patchWidth + i ].xyz;\r
 292                 v2 = ds->verts[ ( ds->patchHeight - 1 ) * ds->patchWidth + i + 1 ].xyz;\r
 293                 v3 = ds->verts[ ( ds->patchHeight - 1 ) * ds->patchWidth + i + 2 ].xyz;\r
 294 \r
 295                 // if v2 is on the v1 to v3 line, add an edge from v1 to v3\r
 296                 if ( ColinearEdge( v1, v2, v3 ) ) {\r
 297                         AddEdge( v1, v3, qfalse );\r
 298                 }\r
 299         }\r
 300 \r
 301         for ( i = 0 ; i < ds->patchHeight - 2 ; i+=2 ) {\r
 302                 v1 = ds->verts[ i * ds->patchWidth ].xyz;\r
 303                 v2 = ds->verts[ ( i + 1 ) * ds->patchWidth ].xyz;\r
 304                 v3 = ds->verts[ ( i + 2 ) * ds->patchWidth ].xyz;\r
 305 \r
 306                 // if v2 is the midpoint of v1 to v3, add an edge from v1 to v3\r
 307                 if ( ColinearEdge( v1, v2, v3 ) ) {\r
 308                         AddEdge( v1, v3, qfalse );\r
 309                 }\r
 310 \r
 311                 v1 = ds->verts[ ( ds->patchWidth - 1 ) + i * ds->patchWidth ].xyz;\r
 312                 v2 = ds->verts[ ( ds->patchWidth - 1 ) + ( i + 1 ) * ds->patchWidth ].xyz;\r
 313                 v3 = ds->verts[ ( ds->patchWidth - 1 ) + ( i + 2 ) * ds->patchWidth ].xyz;\r
 314 \r
 315                 // if v2 is the midpoint of v1 to v3, add an edge from v1 to v3\r
 316                 if ( ColinearEdge( v1, v2, v3 ) ) {\r
 317                         AddEdge( v1, v3, qfalse );\r
 318                 }\r
 319         }\r
 320 \r
 321 \r
 322 }\r
 323 \r
 324 \r
 325 /*\r
 326 ====================\r
 327 FixSurfaceJunctions\r
 328 ====================\r
 329 */\r
 330 #define MAX_SURFACE_VERTS       256\r
 331 void FixSurfaceJunctions( mapDrawSurface_t *ds ) {\r
 332         int                     i, j, k;\r
 333         edgeLine_t      *e;\r
 334         edgePoint_t     *p;\r
 335         int                     originalVerts;\r
 336         int                     counts[MAX_SURFACE_VERTS];\r
 337         int                     originals[MAX_SURFACE_VERTS];\r
 338         int                     firstVert[MAX_SURFACE_VERTS];\r
 339         bspDrawVert_t   verts[MAX_SURFACE_VERTS], *v1, *v2;\r
 340         int                     numVerts;\r
 341         float           start, end, frac, c;\r
 342         vec3_t          delta;\r
 343         \r
 344         \r
 345         originalVerts = ds->numVerts;\r
 346         \r
 347         numVerts = 0;\r
 348         for ( i = 0 ; i < ds->numVerts ; i++ )\r
 349         {\r
 350                 counts[i] = 0;\r
 351                 firstVert[i] = numVerts;\r
 352 \r
 353                 // copy first vert\r
 354                 if ( numVerts == MAX_SURFACE_VERTS ) {\r
 355                         Error( "MAX_SURFACE_VERTS" );\r
 356                 }\r
 357                 verts[numVerts] = ds->verts[i];\r
 358                 originals[numVerts] = i;\r
 359                 numVerts++;\r
 360 \r
 361                 // check to see if there are any t junctions before the next vert\r
 362                 v1 = &ds->verts[i];\r
 363                 v2 = &ds->verts[ (i+1) % ds->numVerts ];\r
 364 \r
 365                 j = (int)ds->verts[i].lightmap[ 0 ][ 0 ];\r
 366                 if ( j == -1 ) {\r
 367                         continue;               // degenerate edge\r
 368                 }\r
 369                 e = &edgeLines[ j ];\r
 370                 \r
 371                 VectorSubtract( v1->xyz, e->origin, delta );\r
 372                 start = DotProduct( delta, e->dir );\r
 373 \r
 374                 VectorSubtract( v2->xyz, e->origin, delta );\r
 375                 end = DotProduct( delta, e->dir );\r
 376 \r
 377 \r
 378                 if ( start < end ) {\r
 379                         p = e->chain.next;\r
 380                 } else {\r
 381                         p = e->chain.prev;\r
 382                 }\r
 383 \r
 384                 for (  ; p != &e->chain ;  ) {\r
 385                         if ( start < end ) {\r
 386                                 if ( p->intercept > end - ON_EPSILON ) {\r
 387                                         break;\r
 388                                 }\r
 389                         } else {\r
 390                                 if ( p->intercept < end + ON_EPSILON ) {\r
 391                                         break;\r
 392                                 }\r
 393                         }\r
 394 \r
 395                         if ( \r
 396                                 ( start < end && p->intercept > start + ON_EPSILON ) ||\r
 397                                 ( start > end && p->intercept < start - ON_EPSILON ) ) {\r
 398                                 // insert this point\r
 399                                 if ( numVerts == MAX_SURFACE_VERTS ) {\r
 400                                         Error( "MAX_SURFACE_VERTS" );\r
 401                                 }\r
 402                                 \r
 403                                 /* take the exact intercept point */\r
 404                                 VectorCopy( p->xyz, verts[ numVerts ].xyz );\r
 405                                 \r
 406                                 /* interpolate the texture coordinates */\r
 407                                 frac = ( p->intercept - start ) / ( end - start );\r
 408                                 for ( j = 0 ; j < 2 ; j++ ) {\r
 409                                         verts[ numVerts ].st[j] = v1->st[j] + \r
 410                                                 frac * ( v2->st[j] - v1->st[j] );\r
 411                                 }\r
 412                                 \r
 413                                 /* copy the normal (FIXME: what about nonplanar surfaces? */\r
 414                                 VectorCopy( v1->normal, verts[ numVerts ].normal );\r
 415                                 \r
 416                                 /* ydnar: interpolate the color */\r
 417                                 for( k = 0; k < MAX_LIGHTMAPS; k++ )\r
 418                                 {\r
 419                                         for( j = 0; j < 4; j++ )\r
 420                                         {\r
 421                                                 c = (float) v1->color[ k ][ j ] + frac * ((float) v2->color[ k ][ j ] - (float) v1->color[ k ][ j ]);\r
 422                                                 verts[ numVerts ].color[ k ][ j ] = (byte) (c < 255.0f ? c : 255);\r
 423                                         }\r
 424                                 }\r
 425                                 \r
 426                                 /* next... */\r
 427                                 originals[ numVerts ] = i;\r
 428                                 numVerts++;\r
 429                                 counts[ i ]++;\r
 430                         }\r
 431 \r
 432                         if ( start < end ) {\r
 433                                 p = p->next;\r
 434                         } else {\r
 435                                 p = p->prev;\r
 436                         }\r
 437                 }\r
 438         }\r
 439 \r
 440         c_addedVerts += numVerts - ds->numVerts;\r
 441         c_totalVerts += numVerts;\r
 442 \r
 443 \r
 444         // FIXME: check to see if the entire surface degenerated\r
 445         // after snapping\r
 446 \r
 447         // rotate the points so that the initial vertex is between\r
 448         // two non-subdivided edges\r
 449         for ( i = 0 ; i < numVerts ; i++ ) {\r
 450                 if ( originals[ (i+1) % numVerts ] == originals[ i ] ) {\r
 451                         continue;\r
 452                 }\r
 453                 j = (i + numVerts - 1 ) % numVerts;\r
 454                 k = (i + numVerts - 2 ) % numVerts;\r
 455                 if ( originals[ j ] == originals[ k ] ) {\r
 456                         continue;\r
 457                 }\r
 458                 break;\r
 459         }\r
 460 \r
 461         if ( i == 0 ) {\r
 462                 // fine the way it is\r
 463                 c_natural++;\r
 464 \r
 465                 ds->numVerts = numVerts;\r
 466                 ds->verts = safe_malloc( numVerts * sizeof( *ds->verts ) );\r
 467                 memcpy( ds->verts, verts, numVerts * sizeof( *ds->verts ) );\r
 468 \r
 469                 return;\r
 470         }\r
 471         if ( i == numVerts ) {\r
 472                 // create a vertex in the middle to start the fan\r
 473                 c_cant++;\r
 474 \r
 475 /*\r
 476                 memset ( &verts[numVerts], 0, sizeof( verts[numVerts] ) );\r
 477                 for ( i = 0 ; i < numVerts ; i++ ) {\r
 478                         for ( j = 0 ; j < 10 ; j++ ) {\r
 479                                 verts[numVerts].xyz[j] += verts[i].xyz[j];\r
 480                         }\r
 481                 }\r
 482                 for ( j = 0 ; j < 10 ; j++ ) {\r
 483                         verts[numVerts].xyz[j] /= numVerts;\r
 484                 }\r
 485 \r
 486                 i = numVerts;\r
 487                 numVerts++;\r
 488 */\r
 489         } else {\r
 490                 // just rotate the vertexes\r
 491                 c_rotate++;\r
 492 \r
 493         }\r
 494 \r
 495         ds->numVerts = numVerts;\r
 496         ds->verts = safe_malloc( numVerts * sizeof( *ds->verts ) );\r
 497 \r
 498         for ( j = 0 ; j < ds->numVerts ; j++ ) {\r
 499                 ds->verts[j] = verts[ ( j + i ) % ds->numVerts ];\r
 500         }\r
 501 }\r
 502 \r
 503 \r
 504 \r
 505 \r
 506 \r
 507 /*\r
 508 FixBrokenSurface() - ydnar\r
 509 removes nearly coincident verts from a planar winding surface\r
 510 returns qfalse if the surface is broken\r
 511 */\r
 512 \r
 513 extern void SnapWeldVector( vec3_t a, vec3_t b, vec3_t out );\r
 514 \r
 515 #define DEGENERATE_EPSILON      0.1\r
 516 \r
 517 int             c_broken = 0;\r
 518 \r
 519 qboolean FixBrokenSurface( mapDrawSurface_t *ds )\r
 520 {\r
 521         qboolean        valid = qtrue;\r
 522         bspDrawVert_t   *dv1, *dv2, avg;\r
 523         int                     i, j, k;\r
 524         float           dist;\r
 525         \r
 526         \r
 527         /* dummy check */\r
 528         if( ds == NULL )\r
 529                 return qfalse;\r
 530         if( ds->type != SURFACE_FACE )\r
 531                 return qfalse;\r
 532         \r
 533         /* check all verts */\r
 534         for( i = 0; i < ds->numVerts; i++ )\r
 535         {\r
 536                 /* don't remove points if winding is a triangle */\r
 537                 if( ds->numVerts == 3 )\r
 538                         return valid;\r
 539                 \r
 540                 /* get verts */\r
 541                 dv1 = &ds->verts[ i ];\r
 542                 dv2 = &ds->verts[ (i + 1) % ds->numVerts ];\r
 543                 \r
 544                 /* degenerate edge? */\r
 545                 VectorSubtract( dv1->xyz, dv2->xyz, avg.xyz );\r
 546                 dist = VectorLength( avg.xyz );\r
 547                 if( dist < DEGENERATE_EPSILON )\r
 548                 {\r
 549                         valid = qfalse;\r
 550                         Sys_FPrintf( SYS_VRB, "WARNING: Degenerate T-junction edge found, fixing...\n" );\r
 551 \r
 552                         /* create an average drawvert */\r
 553                         /* ydnar 2002-01-26: added nearest-integer welding preference */\r
 554                         SnapWeldVector( dv1->xyz, dv2->xyz, avg.xyz );\r
 555                         VectorAdd( dv1->normal, dv2->normal, avg.normal );\r
 556                         VectorNormalize( avg.normal, avg.normal );\r
 557                         avg.st[ 0 ] = (dv1->st[ 0 ] + dv2->st[ 0 ]) * 0.5f;\r
 558                         avg.st[ 1 ] = (dv1->st[ 1 ] + dv2->st[ 1 ]) * 0.5f;\r
 559                         \r
 560                         /* lightmap st/colors */\r
 561                         for( k = 0; k < MAX_LIGHTMAPS; k++ )\r
 562                         {\r
 563                                 avg.lightmap[ k ][ 0 ] = (dv1->lightmap[ k ][ 0 ] + dv2->lightmap[ k ][ 0 ]) * 0.5f;\r
 564                                 avg.lightmap[ k ][ 1 ] = (dv1->lightmap[ k ][ 1 ] + dv2->lightmap[ k ][ 1 ]) * 0.5f;\r
 565                                 for( j = 0; j < 4; j++ )\r
 566                                         avg.color[ k ][ j ] = (int) (dv1->color[ k ][ j ] + dv2->color[ k ][ j ]) >> 1;\r
 567                         }\r
 568                         \r
 569                         /* ydnar: der... */\r
 570                         memcpy( dv1, &avg, sizeof( avg ) );\r
 571                         \r
 572                         /* move the remaining verts */\r
 573                         for( k = i + 2; k < ds->numVerts; k++ )\r
 574                         {\r
 575                                 /* get verts */\r
 576                                 dv1 = &ds->verts[ k ];\r
 577                                 dv2 = &ds->verts[ k - 1 ];\r
 578                                 \r
 579                                 /* copy */\r
 580                                 memcpy( dv2, dv1, sizeof( bspDrawVert_t ) );\r
 581                         }\r
 582                         ds->numVerts--;\r
 583                 }\r
 584         }\r
 585         \r
 586         /* one last check and return */\r
 587         if( ds->numVerts < 3 )\r
 588                 valid = qfalse;\r
 589         return valid;\r
 590 }\r
 591 \r
 592 \r
 593 \r
 594 \r
 595 \r
 596 \r
 597 \r
 598 \r
 599 \r
 600 /*\r
 601 ================\r
 602 EdgeCompare\r
 603 ================\r
 604 */\r
 605 int EdgeCompare( const void *elem1, const void *elem2 ) {\r
 606         float   d1, d2;\r
 607 \r
 608         d1 = ((originalEdge_t *)elem1)->length;\r
 609         d2 = ((originalEdge_t *)elem2)->length;\r
 610 \r
 611         if ( d1 < d2 ) {\r
 612                 return -1;\r
 613         }\r
 614         if ( d2 > d1 ) {\r
 615                 return 1;\r
 616         }\r
 617         return 0;\r
 618 }\r
 619 \r
 620 \r
 621 \r
 622 /*\r
 623 FixTJunctions\r
 624 call after the surface list has been pruned\r
 625 */\r
 626 \r
 627 void FixTJunctions( entity_t *ent )\r
 628 {\r
 629         int                                     i;\r
 630         mapDrawSurface_t        *ds;\r
 631         shaderInfo_t            *si;\r
 632         int                                     axialEdgeLines;\r
 633         originalEdge_t          *e;\r
 634         \r
 635         \r
 636         /* meta mode has its own t-junction code (currently not as good as this code) */\r
 637         //%     if( meta )\r
 638         //%             return; \r
 639         \r
 640         /* note it */\r
 641         Sys_FPrintf( SYS_VRB, "--- FixTJunctions ---\n" );\r
 642         numEdgeLines = 0;\r
 643         numOriginalEdges = 0;\r
 644         \r
 645         // add all the edges\r
 646         // this actually creates axial edges, but it\r
 647         // only creates originalEdge_t structures\r
 648         // for non-axial edges\r
 649         for ( i = ent->firstDrawSurf ; i < numMapDrawSurfs ; i++ )\r
 650         {\r
 651                 /* get surface and early out if possible */\r
 652                 ds = &mapDrawSurfs[ i ];\r
 653                 si = ds->shaderInfo;\r
 654                 if( (si->compileFlags & C_NODRAW) || si->autosprite || si->notjunc || ds->numVerts == 0 )\r
 655                         continue;\r
 656                 \r
 657                 /* ydnar: gs mods: handle the various types of surfaces */\r
 658                 switch( ds->type )\r
 659                 {\r
 660                         /* handle brush faces */\r
 661                         case SURFACE_FACE:\r
 662                                 AddSurfaceEdges( ds );\r
 663                                 break;\r
 664                         \r
 665                         /* handle patches */\r
 666                         case SURFACE_PATCH:\r
 667                                 AddPatchEdges( ds );\r
 668                                 break;\r
 669                         \r
 670                         /* fixme: make triangle surfaces t-junction */\r
 671                         default:\r
 672                                 break;\r
 673                 }\r
 674         }\r
 675 \r
 676         axialEdgeLines = numEdgeLines;\r
 677 \r
 678         // sort the non-axial edges by length\r
 679         qsort( originalEdges, numOriginalEdges, sizeof(originalEdges[0]), EdgeCompare );\r
 680 \r
 681         // add the non-axial edges, longest first\r
 682         // this gives the most accurate edge description\r
 683         for ( i = 0 ; i < numOriginalEdges ; i++ ) {\r
 684                 e = &originalEdges[i];\r
 685                 e->dv[ 0 ]->lightmap[ 0 ][ 0 ] = AddEdge( e->dv[ 0 ]->xyz, e->dv[ 1 ]->xyz, qtrue );\r
 686         }\r
 687 \r
 688         Sys_FPrintf( SYS_VRB, "%9d axial edge lines\n", axialEdgeLines );\r
 689         Sys_FPrintf( SYS_VRB, "%9d non-axial edge lines\n", numEdgeLines - axialEdgeLines );\r
 690         Sys_FPrintf( SYS_VRB, "%9d degenerate edges\n", c_degenerateEdges );\r
 691 \r
 692         // insert any needed vertexes\r
 693         for( i = ent->firstDrawSurf; i < numMapDrawSurfs ; i++ )\r
 694         {\r
 695                 /* get surface and early out if possible */\r
 696                 ds = &mapDrawSurfs[ i ];\r
 697                 si = ds->shaderInfo;\r
 698                 if( (si->compileFlags & C_NODRAW) || si->autosprite || si->notjunc || ds->numVerts == 0 || ds->type != SURFACE_FACE )\r
 699                         continue;\r
 700                 \r
 701                 /* ydnar: gs mods: handle the various types of surfaces */\r
 702                 switch( ds->type )\r
 703                 {\r
 704                         /* handle brush faces */\r
 705                         case SURFACE_FACE:\r
 706                                 FixSurfaceJunctions( ds );\r
 707                                 if( FixBrokenSurface( ds ) == qfalse )\r
 708                                 {\r
 709                                         c_broken++;\r
 710                                         ClearSurface( ds );\r
 711                                 }\r
 712                                 break;\r
 713                         \r
 714                         /* fixme: t-junction triangle models and patches */\r
 715                         default:\r
 716                                 break;\r
 717                 }\r
 718         }\r
 719         \r
 720         /* emit some statistics */\r
 721         Sys_FPrintf( SYS_VRB, "%9d verts added for T-junctions\n", c_addedVerts );\r
 722         Sys_FPrintf( SYS_VRB, "%9d total verts\n", c_totalVerts );\r
 723         Sys_FPrintf( SYS_VRB, "%9d naturally ordered\n", c_natural );\r
 724         Sys_FPrintf( SYS_VRB, "%9d rotated orders\n", c_rotate );\r
 725         Sys_FPrintf( SYS_VRB, "%9d can't order\n", c_cant );\r
 726         Sys_FPrintf( SYS_VRB, "%9d broken (degenerate) surfaces removed\n", c_broken );\r
 727 }\r