vmf.h

   1 #include "csrTypes.h"
   2 #include "csrComb.h"
   3
   4 #define SOLID_MAX_SIDES 512
   5
   6 typedef struct vmf_solid vmf_solid;
   7 typedef struct vmf_vert vmf_vert;
   8 typedef struct vmf_mat vmf_mat;
   9 typedef struct vmf_face vmf_face;
  10
  11 typedef enum ESolidResult ESolidResult;
  12
  13 enum ESolidResult
  14 {
  15         k_ESolidResult_valid,
  16         k_ESolidResult_maxsides,
  17         k_ESolidResult_invalid,
  18         k_ESolidResult_errnomem,
  19         k_ESolidResult_corrupt,
  20         k_ESolidResult_degenerate
  21 };
  22
  23 struct vmf_vert
  24 {
  25         v3f     co;
  26         v3f     nrm;
  27         v2f     xy;
  28 };
  29
  30 struct vmf_face
  31 {
  32         u32                     *indices;
  33
  34         vdf_node        *dispinfo;
  35
  36         const char      *material;
  37         int                     blacklisted;
  38 };
  39
  40 struct vmf_solid
  41 {
  42         vmf_vert *verts;
  43         u32 *indices;
  44 };
  45
  46 struct vmf_mat
  47 {
  48         char    *str;
  49         u32     hash;
  50 };
  51
  52 // IMPLEMENTATION
  53
  54 void solidgen_ctx_init( vmf_solid *ctx )
  55 {
  56         const u32 init_size = 128;
  57
  58         ctx->verts = csr_sb_reserve( NULL, init_size, sizeof(vmf_vert) );
  59         ctx->indices = csr_sb_reserve( NULL, init_size, sizeof(u32) );
  60 }
  61
  62 void solidgen_ctx_free( vmf_solid *ctx )
  63 {
  64         csr_sb_free( ctx->verts );
  65         csr_sb_free( ctx->indices );
  66 }
  67
  68 // Compute bounds of solid gen ctx
  69 void solidgen_bounds( vmf_solid *ctx, u32 start, u32 end, v3f min, v3f max )
  70 {
  71         v3f mine = { INFINITY, INFINITY, INFINITY };
  72         v3f maxe = {-INFINITY,-INFINITY,-INFINITY };
  73
  74         for( int i = start; i < end; i ++ )
  75         {
  76                 vmf_vert *vert = ctx->verts + i;
  77                 float *co = vert->co;
  78
  79                 mine[0] = fminf( mine[0], co[0] );
  80                 mine[1] = fminf( mine[1], co[1] );
  81                 mine[2] = fminf( mine[2], co[2] );
  82
  83                 maxe[0] = fmaxf( maxe[0], co[0] );
  84                 maxe[1] = fmaxf( maxe[1], co[1] );
  85                 maxe[2] = fmaxf( maxe[2], co[2] );
  86         }
  87
  88         v3_copy( mine, min );
  89         v3_copy( maxe, max );
  90 }
  91
  92 struct
  93 {
  94         vmf_mat *blacklist;
  95
  96         double planes[ SOLID_MAX_SIDES*4 ];
  97         u32 bisectors;
  98 }
  99 vmf_api;
 100
 101 // put an extra plane into the planes list
 102 void vmf_addbisector( double p[4] )
 103 {
 104         double *plane = vmf_api.planes + vmf_api.bisectors * 4;
 105
 106         plane[0] = p[0];
 107         plane[1] = p[1];
 108         plane[2] = p[2];
 109         plane[3] = p[3];
 110
 111         vmf_api.bisectors ++;
 112 }
 113
 114 void vmf_clearbisectors( void )
 115 {
 116         vmf_api.bisectors = 0;
 117 }
 118
 119 void vmf_ignore_mat( const char *material )
 120 {
 121         vmf_api.blacklist = csr_sb_reserve( vmf_api.blacklist, 1, sizeof( vmf_mat ) );
 122         vmf_mat *mat = (vmf_mat *)csr_sb_use( vmf_api.blacklist );
 123
 124         mat->str = csr_malloc( strlen( material ) + 1 );
 125         strcpy( mat->str, material );
 126
 127         mat->hash = djb2( ( const unsigned char * )material );
 128 }
 129
 130 void vmf_clearignore( void )
 131 {
 132         for( int i = 0; i < csr_sb_count( vmf_api.blacklist ); i ++ )
 133         {
 134                 free( vmf_api.blacklist[ i ].str );
 135         }
 136
 137         csr_sb_free( vmf_api.blacklist );
 138         vmf_api.blacklist = NULL;
 139 }
 140
 141 int mat_blacklisted( const char *material )
 142 {
 143         u32 hash = djb2((const u8 *)material);
 144
 145         for( int j = 0; j < csr_sb_count( vmf_api.blacklist ); j ++ )
 146         {
 147                 if( vmf_api.blacklist[ j ].hash == hash )
 148                 {
 149                         if( !strcmp( material, vmf_api.blacklist[ j ].str ) )
 150                         {
 151                                 return 1;
 152                         }
 153                 }
 154         }
 155
 156         return 0;
 157 }
 158
 159 void sort_coplanar( double p[4], vmf_vert *points, u32 *indices, u32 count )
 160 {
 161         v3f center = {0.f, 0.f, 0.f};
 162         v3f norm;
 163         v3d_v3f( p, norm );
 164         v3_normalize( norm );
 165
 166         for( int i = 0; i < count; i ++ )
 167         {
 168                 v3_add( points[ indices[i] ].co, center, center );
 169         }
 170         v3_divs( center, count, center );
 171
 172         v3f ref;
 173         v3_sub( points[ indices[0] ].co, center, ref );
 174
 175         // Calc angles compared to ref
 176         float *angles = (float*)alloca( sizeof(float)*count );
 177         for( int i = 0; i < count; i ++ )
 178         {
 179                 v3f diff;
 180                 v3f c;
 181
 182                 v3_sub( points[ indices[i] ].co, center, diff );
 183                 v3_cross( diff, ref, c );
 184
 185                 angles[i] =
 186                         atan2f( v3_length(c), v3_dot( diff, ref ) )
 187                         * (v3_dot( c, norm ) < 0.f ? -1.f: 1.f);
 188         }
 189
 190         // Temporary local indexes
 191         u32 *temp_indices = (u32 *)alloca( sizeof(u32)*count );
 192         for( u32 i = 0; i < count; i ++ ) temp_indices[i] = i;
 193
 194         // Slow sort on large vertex counts
 195         int it = 0;
 196         while(1)
 197         {
 198                 int modified = 0;
 199                 for( int i = 0; i < count-1; i ++ )
 200                 {
 201                         int s0 = i; int s1 = i + 1;
 202
 203                         if( angles[temp_indices[s0]] > angles[temp_indices[s1]] )
 204                         {
 205                                 // swap indices and mirror on local
 206                                 u32 temp = indices[s1];
 207                                 indices[s1] = indices[s0];
 208                                 indices[s0] = temp;
 209
 210                                 temp = temp_indices[s1];
 211                                 temp_indices[s1] = temp_indices[s0];
 212                                 temp_indices[s0] = temp;
 213
 214                                 modified = 1;
 215                         }
 216                 }
 217
 218                 it ++;
 219                 if( !modified ) break;
 220         }
 221 }
 222
 223 int solid_has_displacement( vdf_node *node )
 224 {
 225         int it = 0;
 226         vdf_node *pSide;
 227
 228         while( (pSide = vdf_next(node, "side", &it)) )
 229         {
 230                 if( vdf_next( pSide, "dispinfo", NULL ) )
 231                 {
 232                         return 1;
 233                 }
 234         }
 235         return 0;
 236 }
 237
 238 void solid_disp_tri( vmf_solid *ctx, u32 a, u32 b, u32 c )
 239 {
 240         *((u32 *)csr_sb_use( ctx->indices )) = a;
 241         *((u32 *)csr_sb_use( ctx->indices )) = b;
 242         *((u32 *)csr_sb_use( ctx->indices )) = c;
 243 }
 244
 245 void face_add_indice( vmf_face *f, u32 idx )
 246 {
 247         f->indices = csr_sb_reserve( f->indices, 1, sizeof( u32 ) );
 248         *((u32 *)csr_sb_use( f->indices )) = idx;
 249 }
 250
 251 ESolidResult solidgen_push( vmf_solid *ctx, vdf_node *node )
 252 {
 253         ESolidResult flag = k_ESolidResult_valid;
 254
 255         vmf_face faces[ SOLID_MAX_SIDES ];
 256
 257         int is_displacement = 0;
 258         int num_planes = 0;
 259
 260         // TODO: What is this for again? surely it should be the other way around... i think...
 261         if( solid_has_displacement( node ) )
 262         {
 263                 printf( "solid_has_displacement\n" );
 264                 num_planes = vmf_api.bisectors;
 265
 266                 // Add dummy stuff for globals
 267                 // ???
 268                 for( int k = 0; k < vmf_api.bisectors; k ++ )
 269                 {
 270                         vmf_face *dummy = faces + k;
 271                         dummy->indices = NULL;
 272                         dummy->dispinfo = NULL;
 273                         dummy->material = NULL;
 274                 }
 275
 276                 is_displacement = 1;
 277         }
 278
 279         int it = 0;
 280         vdf_node *pSide;
 281         while( (pSide = vdf_next(node, "side", &it)) )
 282         {
 283                 if( num_planes >= SOLID_MAX_SIDES )
 284                 {
 285                         flag = k_ESolidResult_maxsides;
 286                         fprintf( stderr, "Solid over maxsides limit (%i)\n", SOLID_MAX_SIDES );
 287                         break;
 288                 }
 289
 290                 double points[3*3];
 291
 292                 vmf_face *face = faces + num_planes;
 293                 face->indices = NULL;
 294                 face->dispinfo = vdf_next( pSide, "dispinfo", NULL );
 295                 face->material = kv_get( pSide, "material", "" );
 296                 face->blacklisted = mat_blacklisted( face->material );
 297
 298                 kv_double_array( pSide, "plane", 9, points );
 299
 300                 tri_to_plane( points+6, points+3, points+0, vmf_api.planes + num_planes * 4 );
 301                 num_planes ++;
 302         }
 303
 304         // Compute plane intersections
 305         int i[3];
 306         csr_comb_init( 3, i );
 307
 308         v3f center = { 0.f, 0.f, 0.f };
 309         int numpoints = 0;
 310         u32 vert_start = csr_sb_count( ctx->verts );
 311
 312         do
 313         {
 314                 // DO something with i j k
 315                 double p[3];
 316
 317                 if( (faces[ i[0] ].blacklisted && faces[ i[1] ].blacklisted && faces[ i[2] ].blacklisted) )
 318                         continue;
 319
 320                 if( !plane_intersect( vmf_api.planes+i[0]*4, vmf_api.planes+i[1]*4, vmf_api.planes+i[2]*4, p ) )
 321                         continue;
 322
 323                 // Check for illegal verts (eg: got clipped by bisectors)
 324                 int valid = 1;
 325                 for( int m = 0; m < num_planes; m ++ )
 326                 {
 327                         if( plane_polarity( vmf_api.planes+m*4, p ) > 1e-6f )
 328                         {
 329                                 valid = 0;
 330                                 break;
 331                         }
 332                 }
 333
 334                 if( valid )
 335                 {
 336                         ctx->verts = csr_sb_reserve( ctx->verts, 3, sizeof( vmf_vert ) );
 337
 338                         // Take the vertex position and add it for centering base on average
 339                         numpoints ++;
 340                         v3_add( (v3f){ p[0], p[1], p[2] }, center, center );
 341
 342                         // Store point / respecive normal for each plane that triggered the collision
 343                         for( int k = 0; k < 3; k ++ )
 344                         {
 345                                 if( !faces[ i[k] ].blacklisted )
 346                                 {
 347                                         u32 c = csr_sb_count( ctx->verts );
 348
 349                                         face_add_indice( faces + i[k], c );
 350
 351                                         v3d_v3f( p, ctx->verts[ c ].co );
 352                                         v3d_v3f( vmf_api.planes+i[k]*4, ctx->verts[ c ].nrm );
 353
 354                                         csr_sb_inc( ctx->verts, 1 );
 355                                 }
 356                         }
 357                 }
 358         }
 359         while( csr_comb( 3, num_planes, i ) );
 360
 361         // Retrospectively set the center for each point
 362         v3_divs( center, (float)numpoints, center );
 363         for( ; vert_start < csr_sb_count( ctx->verts ); vert_start ++ )
 364         {
 365                 v2_copy( center, ctx->verts[ vert_start ].xy );
 366         }
 367
 368         // Sort each faces and trianglulalate them
 369         for( int k = vmf_api.bisectors; k < num_planes; k ++ )
 370         {
 371                 vmf_face *face = faces + k;
 372
 373                 if( face->blacklisted ) continue;
 374
 375                 if( csr_sb_count( face->indices ) < 3 )
 376                 {
 377                         if( !vmf_api.bisectors )
 378                         {
 379                                 flag = k_ESolidResult_degenerate;
 380                                 fprintf( stderr, "Skipping degenerate face\n" );
 381                         }
 382                         continue;
 383                 }
 384
 385                 // Sort only if there is no displacements, or if this side is
 386                 if( !is_displacement || ( is_displacement && face->dispinfo ) )
 387                 {
 388                         sort_coplanar( vmf_api.planes+k*4, ctx->verts, face->indices, csr_sb_count( face->indices ) );
 389                 }
 390
 391                 if( is_displacement )
 392                 {
 393                         // Compute displacement
 394                         if( face->dispinfo )
 395                         {
 396                                 if( csr_sb_count( face->indices ) != 4 )
 397                                 {
 398                                         // Mute error if we have global planes cause they
 399                                         // are of course gonna fuck things up here
 400                                         if( !vmf_api.bisectors )
 401                                         {
 402                                                 flag = k_ESolidResult_degenerate;
 403                                                 fprintf( stderr, "Skipping degenerate displacement\n" );
 404                                         }
 405                                         continue;
 406                                 }
 407
 408                                 // Match starting position
 409                                 v3f start;
 410                                 int sw = 0;
 411                                 float dmin = 999999.f;
 412
 413                                 vdf_node *dispinfo = face->dispinfo;
 414                                 vdf_node *vdf_normals = vdf_next( dispinfo, "normals", NULL );
 415                                 vdf_node *vdf_distances = vdf_next( dispinfo, "distances", NULL );
 416
 417                                 kv_float_array( dispinfo, "startposition", 3, start );
 418
 419                                 for( int j = 0; j < csr_sb_count( face->indices ); j ++ )
 420                                 {
 421                                         float d2 = v3_dist2( start, ctx->verts[ face->indices[ j ] ].co );
 422                                         if( d2 < dmin )
 423                                         {
 424                                                 dmin = d2;
 425                                                 sw = j;
 426                                         }
 427                                 }
 428
 429                                 // Get corners of displacement
 430                                 float *SW = ctx->verts[ face->indices[ sw ] ].co;
 431                                 float *NW = ctx->verts[ face->indices[ (sw+1) % 4] ].co;
 432                                 float *NE = ctx->verts[ face->indices[ (sw+2) % 4] ].co;
 433                                 float *SE = ctx->verts[ face->indices[ (sw+3) % 4] ].co;
 434
 435                                 // Can be either 5, 9, 17
 436                                 numpoints = pow( 2, kv_get_int( dispinfo, "power", 2 ) ) + 1;
 437                                 u32 reqverts = numpoints*numpoints;
 438                                 u32 reqidx = (numpoints-1)*(numpoints-1)*6;
 439
 440                                 ctx->verts = csr_sb_reserve( ctx->verts, reqverts, sizeof( vmf_vert ) );
 441                                 ctx->indices = csr_sb_reserve( ctx->indices, reqidx, sizeof( u32 ) );
 442
 443                                 float normals[ 17*3 ];
 444                                 float distances[ 17 ];
 445
 446                                 // Calculate displacement positions
 447                                 for( int j = 0; j < numpoints; j ++ )
 448                                 {
 449                                         char key[14];
 450                                         sprintf( key, "row%i", j );
 451
 452                                         kv_float_array( vdf_normals, key, 17*3, normals );
 453                                         kv_float_array( vdf_distances, key, 17, distances );
 454
 455                                         float dx = (float)j / (float)(numpoints - 1); //Time values for linear interpolation
 456
 457                                         for( int m = 0; m < numpoints; m ++ )
 458                                         {
 459                                                 vmf_vert *vert = &ctx->verts[ csr_sb_count( ctx->verts ) + j*numpoints + m ];
 460
 461                                                 float dy = (float)m / (float)(numpoints - 1);
 462
 463                                                 v3f lwr; v3f upr;
 464
 465                                                 v3_lerp( SW, SE, dx, lwr );
 466                                                 v3_lerp( NW, NE, dx, upr );
 467                                                 v3_lerp( lwr, upr, dy, vert->co );
 468
 469                                                 v3_muladds( vert->co, normals + m * 3, distances[ m ], vert->co );
 470
 471                                                 // Todo, put correct normal
 472                                                 v3_copy( (v3f){ 0.f, 0.f, 1.f }, vert->nrm );
 473                                         }
 474                                 }
 475
 476                                 // Build displacement indices
 477                                 int condition = 0;
 478                                 for( int row = 0; row < numpoints - 1; row ++ )
 479                                 {
 480                                         for( int col = 0; col < numpoints - 1; col ++ )
 481                                         {
 482                                                 u32 c = csr_sb_count( ctx->verts );
 483
 484                                                 u32 idxsw = c + ( row + 0 ) * numpoints + col + 0 ;
 485                                                 u32 idxse = c + ( row + 0 ) * numpoints + col + 1 ;
 486                                                 u32 idxnw = c + ( row + 1 ) * numpoints + col + 0 ;
 487                                                 u32 idxne = c + ( row + 1 ) * numpoints + col + 1 ;
 488
 489                                                 if( (condition ++) % 2 == 0 )
 490                                                 {
 491                                                         solid_disp_tri( ctx, idxne, idxnw, idxsw );
 492                                                         solid_disp_tri( ctx, idxse, idxne, idxsw );
 493                                                 }
 494                                                 else
 495                                                 {
 496                                                         solid_disp_tri( ctx, idxse, idxnw, idxsw );
 497                                                         solid_disp_tri( ctx, idxse, idxne, idxnw );
 498                                                 }
 499                                         }
 500                                         condition ++;
 501                                 }
 502
 503                                 csr_sb_inc( ctx->verts, numpoints*numpoints );
 504                         }
 505                 }
 506                 else
 507                 {
 508                         u32 tris = csr_sb_count( face->indices ) -2;
 509                         ctx->indices = csr_sb_reserve( ctx->indices, tris*3, sizeof( u32 ) );
 510
 511                         u32 c = csr_sb_count( ctx->indices );
 512
 513                         for( int j = 0; j < tris; j ++ )
 514                         {
 515                                 ctx->indices[ c +j*3 +0 ] = face->indices[ 0 ];
 516                                 ctx->indices[ c +j*3 +1 ] = face->indices[ j+1 ];
 517                                 ctx->indices[ c +j*3 +2 ] = face->indices[ j+2 ];
 518
 519                                 //   A                  0,1,2:: A,B,C
 520                                 // D    B               0,2,3:: A,C,D
 521                                 //   C
 522                         }
 523
 524                         csr_sb_inc( ctx->indices, tris*3 );
 525                 }
 526         }
 527
 528         // Free temp polyon buffers
 529         for( int j = 0; j < num_planes; j ++ )
 530         {
 531                 csr_sb_free( faces[ j ].indices );
 532         }
 533
 534         return flag;
 535 }
 536
 537 void solidgen_to_obj( vmf_solid *ctx, const char *path )
 538 {
 539         FILE *fp = fopen( path, "w" );
 540
 541         if( fp )
 542         {
 543                 fprintf( fp, "o vmf_export\n" );
 544
 545                 vmf_vert *vert;
 546
 547                 // Write vertex block
 548                 for( int i = 0; i < csr_sb_count( ctx->verts ); i ++ )
 549                 {
 550                         vert = &ctx->verts[i];
 551                         fprintf( fp, "v %f %f %f\n", vert->co[0], vert->co[1], vert->co[2] );
 552                 }
 553
 554                 // Write normals block
 555                 for( int i = 0; i < csr_sb_count( ctx->verts ); i ++ )
 556                 {
 557                         vert = &ctx->verts[i];
 558                         fprintf( fp, "vn %f %f %f\n", vert->nrm[0], vert->nrm[1], vert->nrm[2] );
 559                 }
 560
 561                 fprintf( fp, "s off\n" );
 562
 563                 // Indices
 564                 for( int i = 0; i < csr_sb_count( ctx->indices )/3; i ++ )
 565                 {
 566                         u32 * base = ctx->indices + i*3;
 567                         fprintf( fp, "f %u//%u %u//%u %u//%u\n",
 568                                 base[2]+1, base[2]+1,
 569                                 base[1]+1, base[1]+1,
 570                                 base[0]+1, base[0]+1
 571                         );
 572                 }
 573
 574                 fclose( fp );
 575         }
 576         else
 577         {
 578                 fprintf( stderr, "Could not open %s for writing\n", path );
 579         }
 580 }