+#include "csrTypes.h"
+#include "csrComb.h"
+
+#define SOLID_MAX_SIDES 512
+
+typedef struct vmf_solid vmf_solid;
+typedef struct vmf_vert vmf_vert;
+typedef struct vmf_mat vmf_mat;
+typedef struct vmf_face vmf_face;
+
+typedef enum ESolidResult ESolidResult;
+
+enum ESolidResult
+{
+ k_ESolidResult_valid,
+ k_ESolidResult_maxsides,
+ k_ESolidResult_invalid,
+ k_ESolidResult_errnomem,
+ k_ESolidResult_corrupt,
+ k_ESolidResult_degenerate
+};
+
+struct vmf_vert
+{
+ v3f co;
+ v3f nrm;
+ v2f xy;
+};
+
+struct vmf_face
+{
+ u32 *indices;
+
+ vdf_node *dispinfo;
+
+ const char *material;
+ int blacklisted;
+};
+
+struct vmf_solid
+{
+ vmf_vert *verts;
+ u32 *indices;
+};
+
+struct vmf_mat
+{
+ char *str;
+ u32 hash;
+};
+
+// IMPLEMENTATION
+
+void solidgen_ctx_init( vmf_solid *ctx )
+{
+ const u32 init_size = 128;
+
+ ctx->verts = csr_sb_reserve( NULL, init_size, sizeof(vmf_vert) );
+ ctx->indices = csr_sb_reserve( NULL, init_size, sizeof(u32) );
+}
+
+void solidgen_ctx_free( vmf_solid *ctx )
+{
+ csr_sb_free( ctx->verts );
+ csr_sb_free( ctx->indices );
+}
+
+// Compute bounds of solid gen ctx
+void solidgen_bounds( vmf_solid *ctx, u32 start, u32 end, v3f min, v3f max )
+{
+ v3f mine = { INFINITY, INFINITY, INFINITY };
+ v3f maxe = {-INFINITY,-INFINITY,-INFINITY };
+
+ for( int i = start; i < end; i ++ )
+ {
+ vmf_vert *vert = ctx->verts + i;
+ float *co = vert->co;
+
+ mine[0] = fminf( mine[0], co[0] );
+ mine[1] = fminf( mine[1], co[1] );
+ mine[2] = fminf( mine[2], co[2] );
+
+ maxe[0] = fmaxf( maxe[0], co[0] );
+ maxe[1] = fmaxf( maxe[1], co[1] );
+ maxe[2] = fmaxf( maxe[2], co[2] );
+ }
+
+ v3_copy( mine, min );
+ v3_copy( maxe, max );
+}
+
+struct
+{
+ vmf_mat *blacklist;
+
+ double planes[ SOLID_MAX_SIDES*4 ];
+ u32 bisectors;
+}
+vmf_api;
+
+// put an extra plane into the planes list
+void vmf_addbisector( double p[4] )
+{
+ double *plane = vmf_api.planes + vmf_api.bisectors * 4;
+
+ plane[0] = p[0];
+ plane[1] = p[1];
+ plane[2] = p[2];
+ plane[3] = p[3];
+
+ vmf_api.bisectors ++;
+}
+
+void vmf_clearbisectors( void )
+{
+ vmf_api.bisectors = 0;
+}
+
+void vmf_ignore_mat( const char *material )
+{
+ vmf_api.blacklist = csr_sb_reserve( vmf_api.blacklist, 1, sizeof( vmf_mat ) );
+ vmf_mat *mat = (vmf_mat *)csr_sb_use( vmf_api.blacklist );
+
+ mat->str = csr_malloc( strlen( material ) + 1 );
+ strcpy( mat->str, material );
+
+ mat->hash = djb2( ( const unsigned char * )material );
+}
+
+void vmf_clearignore( void )
+{
+ for( int i = 0; i < csr_sb_count( vmf_api.blacklist ); i ++ )
+ {
+ free( vmf_api.blacklist[ i ].str );
+ }
+
+ csr_sb_free( vmf_api.blacklist );
+ vmf_api.blacklist = NULL;
+}
+
+int mat_blacklisted( const char *material )
+{
+ u32 hash = djb2((const u8 *)material);
+
+ for( int j = 0; j < csr_sb_count( vmf_api.blacklist ); j ++ )
+ {
+ if( vmf_api.blacklist[ j ].hash == hash )
+ {
+ if( !strcmp( material, vmf_api.blacklist[ j ].str ) )
+ {
+ return 1;
+ }
+ }
+ }
+
+ return 0;
+}
+
+void sort_coplanar( double p[4], vmf_vert *points, u32 *indices, u32 count )
+{
+ v3f center = {0.f, 0.f, 0.f};
+ v3f norm;
+ v3d_v3f( p, norm );
+ v3_normalize( norm );
+
+ for( int i = 0; i < count; i ++ )
+ {
+ v3_add( points[ indices[i] ].co, center, center );
+ }
+ v3_divs( center, count, center );
+
+ v3f ref;
+ v3_sub( points[ indices[0] ].co, center, ref );
+
+ // Calc angles compared to ref
+ float *angles = (float*)alloca( sizeof(float)*count );
+ for( int i = 0; i < count; i ++ )
+ {
+ v3f diff;
+ v3f c;
+
+ v3_sub( points[ indices[i] ].co, center, diff );
+ v3_cross( diff, ref, c );
+
+ angles[i] =
+ atan2f( v3_length(c), v3_dot( diff, ref ) )
+ * (v3_dot( c, norm ) < 0.f ? -1.f: 1.f);
+ }
+
+ // Temporary local indexes
+ u32 *temp_indices = (u32 *)alloca( sizeof(u32)*count );
+ for( u32 i = 0; i < count; i ++ ) temp_indices[i] = i;
+
+ // Slow sort on large vertex counts
+ int it = 0;
+ while(1)
+ {
+ int modified = 0;
+ for( int i = 0; i < count-1; i ++ )
+ {
+ int s0 = i; int s1 = i + 1;
+
+ if( angles[temp_indices[s0]] > angles[temp_indices[s1]] )
+ {
+ // swap indices and mirror on local
+ u32 temp = indices[s1];
+ indices[s1] = indices[s0];
+ indices[s0] = temp;
+
+ temp = temp_indices[s1];
+ temp_indices[s1] = temp_indices[s0];
+ temp_indices[s0] = temp;
+
+ modified = 1;
+ }
+ }
+
+ it ++;
+ if( !modified ) break;
+ }
+}
+
+int solid_has_displacement( vdf_node *node )
+{
+ int it = 0;
+ vdf_node *pSide;
+
+ while( (pSide = vdf_next(node, "side", &it)) )
+ {
+ if( vdf_next( pSide, "dispinfo", NULL ) )
+ {
+ return 1;
+ }
+ }
+ return 0;
+}
+
+void solid_disp_tri( vmf_solid *ctx, u32 a, u32 b, u32 c )
+{
+ *((u32 *)csr_sb_use( ctx->indices )) = a;
+ *((u32 *)csr_sb_use( ctx->indices )) = b;
+ *((u32 *)csr_sb_use( ctx->indices )) = c;
+}
+
+void face_add_indice( vmf_face *f, u32 idx )
+{
+ f->indices = csr_sb_reserve( f->indices, 1, sizeof( u32 ) );
+ *((u32 *)csr_sb_use( f->indices )) = idx;
+}
+
+ESolidResult solidgen_push( vmf_solid *ctx, vdf_node *node )
+{
+ ESolidResult flag = k_ESolidResult_valid;
+
+ vmf_face faces[ SOLID_MAX_SIDES ];
+
+ int is_displacement = 0;
+ int num_planes = 0;
+
+ // TODO: What is this for again? surely it should be the other way around... i think...
+ if( solid_has_displacement( node ) )
+ {
+ printf( "solid_has_displacement\n" );
+ num_planes = vmf_api.bisectors;
+
+ // Add dummy stuff for globals
+ // ???
+ for( int k = 0; k < vmf_api.bisectors; k ++ )
+ {
+ vmf_face *dummy = faces + k;
+ dummy->indices = NULL;
+ dummy->dispinfo = NULL;
+ dummy->material = NULL;
+ }
+
+ is_displacement = 1;
+ }
+
+ int it = 0;
+ vdf_node *pSide;
+ while( (pSide = vdf_next(node, "side", &it)) )
+ {
+ if( num_planes >= SOLID_MAX_SIDES )
+ {
+ flag = k_ESolidResult_maxsides;
+ fprintf( stderr, "Solid over maxsides limit (%i)\n", SOLID_MAX_SIDES );
+ break;
+ }
+
+ double points[3*3];
+
+ vmf_face *face = faces + num_planes;
+ face->indices = NULL;
+ face->dispinfo = vdf_next( pSide, "dispinfo", NULL );
+ face->material = kv_get( pSide, "material", "" );
+ face->blacklisted = mat_blacklisted( face->material );
+
+ kv_double_array( pSide, "plane", 9, points );
+
+ tri_to_plane( points+6, points+3, points+0, vmf_api.planes + num_planes * 4 );
+ num_planes ++;
+ }
+
+ // Compute plane intersections
+ int i[3];
+ csr_comb_init( 3, i );
+
+ v3f center = { 0.f, 0.f, 0.f };
+ int numpoints = 0;
+ u32 vert_start = csr_sb_count( ctx->verts );
+
+ do
+ {
+ // DO something with i j k
+ double p[3];
+
+ if( (faces[ i[0] ].blacklisted && faces[ i[1] ].blacklisted && faces[ i[2] ].blacklisted) )
+ continue;
+
+ if( !plane_intersect( vmf_api.planes+i[0]*4, vmf_api.planes+i[1]*4, vmf_api.planes+i[2]*4, p ) )
+ continue;
+
+ // Check for illegal verts (eg: got clipped by bisectors)
+ int valid = 1;
+ for( int m = 0; m < num_planes; m ++ )
+ {
+ if( plane_polarity( vmf_api.planes+m*4, p ) > 1e-6f )
+ {
+ valid = 0;
+ break;
+ }
+ }
+
+ if( valid )
+ {
+ ctx->verts = csr_sb_reserve( ctx->verts, 3, sizeof( vmf_vert ) );
+
+ // Take the vertex position and add it for centering base on average
+ numpoints ++;
+ v3_add( (v3f){ p[0], p[1], p[2] }, center, center );
+
+ // Store point / respecive normal for each plane that triggered the collision
+ for( int k = 0; k < 3; k ++ )
+ {
+ if( !faces[ i[k] ].blacklisted )
+ {
+ u32 c = csr_sb_count( ctx->verts );
+
+ face_add_indice( faces + i[k], c );
+
+ v3d_v3f( p, ctx->verts[ c ].co );
+ v3d_v3f( vmf_api.planes+i[k]*4, ctx->verts[ c ].nrm );
+
+ csr_sb_inc( ctx->verts, 1 );
+ }
+ }
+ }
+ }
+ while( csr_comb( 3, num_planes, i ) );
+
+ // Retrospectively set the center for each point
+ v3_divs( center, (float)numpoints, center );
+ for( ; vert_start < csr_sb_count( ctx->verts ); vert_start ++ )
+ {
+ v2_copy( center, ctx->verts[ vert_start ].xy );
+ }
+
+ // Sort each faces and trianglulalate them
+ for( int k = vmf_api.bisectors; k < num_planes; k ++ )
+ {
+ vmf_face *face = faces + k;
+
+ if( face->blacklisted ) continue;
+
+ if( csr_sb_count( face->indices ) < 3 )
+ {
+ if( !vmf_api.bisectors )
+ {
+ flag = k_ESolidResult_degenerate;
+ fprintf( stderr, "Skipping degenerate face\n" );
+ }
+ continue;
+ }
+
+ // Sort only if there is no displacements, or if this side is
+ if( !is_displacement || ( is_displacement && face->dispinfo ) )
+ {
+ sort_coplanar( vmf_api.planes+k*4, ctx->verts, face->indices, csr_sb_count( face->indices ) );
+ }
+
+ if( is_displacement )
+ {
+ // Compute displacement
+ if( face->dispinfo )
+ {
+ if( csr_sb_count( face->indices ) != 4 )
+ {
+ // Mute error if we have global planes cause they
+ // are of course gonna fuck things up here
+ if( !vmf_api.bisectors )
+ {
+ flag = k_ESolidResult_degenerate;
+ fprintf( stderr, "Skipping degenerate displacement\n" );
+ }
+ continue;
+ }
+
+ // Match starting position
+ v3f start;
+ int sw = 0;
+ float dmin = 999999.f;
+
+ vdf_node *dispinfo = face->dispinfo;
+ vdf_node *vdf_normals = vdf_next( dispinfo, "normals", NULL );
+ vdf_node *vdf_distances = vdf_next( dispinfo, "distances", NULL );
+
+ kv_float_array( dispinfo, "startposition", 3, start );
+
+ for( int j = 0; j < csr_sb_count( face->indices ); j ++ )
+ {
+ float d2 = v3_dist2( start, ctx->verts[ face->indices[ j ] ].co );
+ if( d2 < dmin )
+ {
+ dmin = d2;
+ sw = j;
+ }
+ }
+
+ // Get corners of displacement
+ float *SW = ctx->verts[ face->indices[ sw ] ].co;
+ float *NW = ctx->verts[ face->indices[ (sw+1) % 4] ].co;
+ float *NE = ctx->verts[ face->indices[ (sw+2) % 4] ].co;
+ float *SE = ctx->verts[ face->indices[ (sw+3) % 4] ].co;
+
+ // Can be either 5, 9, 17
+ numpoints = pow( 2, kv_get_int( dispinfo, "power", 2 ) ) + 1;
+ u32 reqverts = numpoints*numpoints;
+ u32 reqidx = (numpoints-1)*(numpoints-1)*6;
+
+ ctx->verts = csr_sb_reserve( ctx->verts, reqverts, sizeof( vmf_vert ) );
+ ctx->indices = csr_sb_reserve( ctx->indices, reqidx, sizeof( u32 ) );
+
+ float normals[ 17*3 ];
+ float distances[ 17 ];
+
+ // Calculate displacement positions
+ for( int j = 0; j < numpoints; j ++ )
+ {
+ char key[14];
+ sprintf( key, "row%i", j );
+
+ kv_float_array( vdf_normals, key, 17*3, normals );
+ kv_float_array( vdf_distances, key, 17, distances );
+
+ float dx = (float)j / (float)(numpoints - 1); //Time values for linear interpolation
+
+ for( int m = 0; m < numpoints; m ++ )
+ {
+ vmf_vert *vert = &ctx->verts[ csr_sb_count( ctx->verts ) + j*numpoints + m ];
+
+ float dy = (float)m / (float)(numpoints - 1);
+
+ v3f lwr; v3f upr;
+
+ v3_lerp( SW, SE, dx, lwr );
+ v3_lerp( NW, NE, dx, upr );
+ v3_lerp( lwr, upr, dy, vert->co );
+
+ v3_muladds( vert->co, normals + m * 3, distances[ m ], vert->co );
+
+ // Todo, put correct normal
+ v3_copy( (v3f){ 0.f, 0.f, 1.f }, vert->nrm );
+ }
+ }
+
+ // Build displacement indices
+ int condition = 0;
+ for( int row = 0; row < numpoints - 1; row ++ )
+ {
+ for( int col = 0; col < numpoints - 1; col ++ )
+ {
+ u32 c = csr_sb_count( ctx->verts );
+
+ u32 idxsw = c + ( row + 0 ) * numpoints + col + 0 ;
+ u32 idxse = c + ( row + 0 ) * numpoints + col + 1 ;
+ u32 idxnw = c + ( row + 1 ) * numpoints + col + 0 ;
+ u32 idxne = c + ( row + 1 ) * numpoints + col + 1 ;
+
+ if( (condition ++) % 2 == 0 )
+ {
+ solid_disp_tri( ctx, idxne, idxnw, idxsw );
+ solid_disp_tri( ctx, idxse, idxne, idxsw );
+ }
+ else
+ {
+ solid_disp_tri( ctx, idxse, idxnw, idxsw );
+ solid_disp_tri( ctx, idxse, idxne, idxnw );
+ }
+ }
+ condition ++;
+ }
+
+ csr_sb_inc( ctx->verts, numpoints*numpoints );
+ }
+ }
+ else
+ {
+ u32 tris = csr_sb_count( face->indices ) -2;
+ ctx->indices = csr_sb_reserve( ctx->indices, tris*3, sizeof( u32 ) );
+
+ u32 c = csr_sb_count( ctx->indices );
+
+ for( int j = 0; j < tris; j ++ )
+ {
+ ctx->indices[ c +j*3 +0 ] = face->indices[ 0 ];
+ ctx->indices[ c +j*3 +1 ] = face->indices[ j+1 ];
+ ctx->indices[ c +j*3 +2 ] = face->indices[ j+2 ];
+
+ // A 0,1,2:: A,B,C
+ // D B 0,2,3:: A,C,D
+ // C
+ }
+
+ csr_sb_inc( ctx->indices, tris*3 );
+ }
+ }
+
+ // Free temp polyon buffers
+ for( int j = 0; j < num_planes; j ++ )
+ {
+ csr_sb_free( faces[ j ].indices );
+ }
+
+ return flag;
+}
+
+void solidgen_to_obj( vmf_solid *ctx, const char *path )
+{
+ FILE *fp = fopen( path, "w" );
+
+ if( fp )
+ {
+ fprintf( fp, "o vmf_export\n" );
+
+ vmf_vert *vert;
+
+ // Write vertex block
+ for( int i = 0; i < csr_sb_count( ctx->verts ); i ++ )
+ {
+ vert = &ctx->verts[i];
+ fprintf( fp, "v %f %f %f\n", vert->co[0], vert->co[1], vert->co[2] );
+ }
+
+ // Write normals block
+ for( int i = 0; i < csr_sb_count( ctx->verts ); i ++ )
+ {
+ vert = &ctx->verts[i];
+ fprintf( fp, "vn %f %f %f\n", vert->nrm[0], vert->nrm[1], vert->nrm[2] );
+ }
+
+ fprintf( fp, "s off\n" );
+
+ // Indices
+ for( int i = 0; i < csr_sb_count( ctx->indices )/3; i ++ )
+ {
+ u32 * base = ctx->indices + i*3;
+ fprintf( fp, "f %u//%u %u//%u %u//%u\n",
+ base[2]+1, base[2]+1,
+ base[1]+1, base[1]+1,
+ base[0]+1, base[0]+1
+ );
+ }
+
+ fclose( fp );
+ }
+ else
+ {
+ fprintf( stderr, "Could not open %s for writing\n", path );
+ }
+}