[csRadar.git] / vmf.h

#define SOLID_MAX_SIDES 512
#define VMF_FLAG_IS_PROP 0x1
#define VMF_FLAG_IS_INSTANCE 0x2
#define VMF_FLAG_BRUSH_ENT 0x4

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 struct vmf_userdata vmf_userdata;
typedef struct vmf_map vmf_map;

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;
};

struct vmf_map
{
        vdf_node *root;

        struct vmf_model
        {
                char *str;
                u32     hash;
                
                mdl_mesh_t mdl;
        }
        *models;
        
        struct vmf_instance
        {
                char *name;
                u32     hash;
                
                vdf_node *root;
                
                m4x3f transform;
        }
        *cache;
        
        m4x3f transform;
};

// IMPLEMENTATION

void solidgen_ctx_reset( vmf_solid *ctx )
{
        csr_sb_clear( ctx->verts );
        csr_sb_clear( ctx->indices );
}

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, boxf box )
{
        v3f mine = { INFINITY, INFINITY, INFINITY };
        v3f maxe = {-INFINITY,-INFINITY,-INFINITY };

        for( int i = 0; i < csr_sb_count( ctx->verts ); i ++ )
        {
                vmf_vert *vert = ctx->verts + i;
                v3_minv( mine, vert->co, mine );
                v3_maxv( maxe, vert->co, maxe );
        }
        
        v3_copy( mine, box[0] );
        v3_copy( maxe, box[1] );
}

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;

        double planes[ SOLID_MAX_SIDES*4 ];
        vmf_face faces[ SOLID_MAX_SIDES ];

        int is_displacement = solid_has_displacement( node );
        int num_planes = 0;
        
        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, 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( planes+i[0]*4, planes+i[1]*4, 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( 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( 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 = 0; k < num_planes; k ++ )
        {
                vmf_face *face = faces + k;
        
                if( face->blacklisted ) continue;

                if( csr_sb_count( face->indices ) < 3 )
                {
                        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( 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 )
                                {
                                        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;
                                        }
                                }
                                
                                // 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 ) );

                                // 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;
                                
                                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;
}

u32 vmf_get_mdl( vmf_map *map, const char *mdl )
{
        u32 hash = djb2( (const unsigned char *)mdl );
        
        for( u32 i = 0; i < csr_sb_count( map->models ); i ++ )
        {
                if( hash == map->models[i].hash && !strcmp( map->models[i].str, mdl ) )
                {
                        return i;
                }
        }
        
        return 0;
}

int vmf_class_is_prop( vdf_node *ent )
{
        return !strncmp( kv_get( ent, "classname", "" ), "prop_", 5 );
}

void vmf_populate_models( vdf_node *vmf, vmf_map *map )
{
        vdf_foreach( vmf, "entity", ent )
        {
                // Use any class name with prop_
                if( vmf_class_is_prop( ent ) )
                {
                        // Check if it exists
                        const char *model_path = kv_get( ent, "model", "" );
                        u32 mdl_id = vmf_get_mdl( map, model_path );
                        
                        if( !mdl_id )
                        {
                                map->models = csr_sb_reserve( map->models, 1, sizeof( struct vmf_model ));
                                
                                struct vmf_model *entry = &map->models[ csr_sb_count( map->models ) ];
                                entry->str = csr_malloc( strlen( model_path ) +1 );
                                strcpy( entry->str, model_path );
                                entry->hash = djb2( (const unsigned char *)model_path );
                                
                                mdl_id = csr_sb_count( map->models );
                                csr_sb_use( map->models );                              
                        }
                        
                        // Assign prop-ID for later use
                        ent->user = VMF_FLAG_IS_PROP;
                        ent->user1 = mdl_id;
                }
        }
}

// Load all models
void vmf_load_models( vmf_map *map )
{
        printf( "Loading all models\n" );
        
        // Error model. TODO: Maybe don't have this be junk data.
        map->models = csr_sb_reserve( map->models, 1, sizeof( struct vmf_model ));
        csr_sb_use( map->models );
        mdl_error( &map->models[0].mdl );
        
        // Create listings for each model
        vmf_populate_models( map->root, map );
        
        for( int i = 0; i < csr_sb_count( map->cache ); i ++ )
        {
                vmf_populate_models( map->cache[i].root, map );
        }
        
        printf( "Indexed (%u) models\n", csr_sb_count( map->models )-1 );
        
        u32 num_success = 0;
        
        // Load model data
        // TODO: Make nice loading bar
        for( int i = 1; i < csr_sb_count( map->models ); i ++ )
        {
                struct vmf_model *mdl = &map->models[i];
                
                if( mdl_from_find_files( mdl->str, &mdl->mdl ) )
                {
                        num_success ++;
                }
                else
                {
                        fprintf( stderr, "Failed to load model: %s\n", mdl->str );
                }
        }
        
        printf( "Done (%u of %u loaded)\n", num_success, csr_sb_count( map->models )-1 );
}

u32 vmf_init_subvmf( vmf_map *map, const char *subvmf );

void vmf_load_all_instances( vmf_map *map, vdf_node *vmf )
{
        vdf_foreach( vmf, "entity", ent )
        {
                if( !strcmp( kv_get( ent, "classname", "" ), "func_instance" ))
                {
                        // Entity is in use if file is specified, if not just ignore the entity.
                        const char *path = kv_get( ent, "file", "" );
                        if( strcmp( path, "" ) )
                        {
                                if( (ent->user1 = vmf_init_subvmf( map, path )))
                                {
                                        ent->user1 --;
                                        ent->user = VMF_FLAG_IS_INSTANCE;
                                }
                        }
                }
        }
}

// TODO: Merge this into above function.. doesnt need to be seperated
u32 vmf_init_subvmf( vmf_map *map, const char *subvmf )
{
        u32 id;
        u32 hash = djb2( (const unsigned char *)subvmf );
        
        // Check if present
        for( u32 i = 0; i < csr_sb_count( map->cache ); i ++ )
        {
                if( hash == map->cache[i].hash )
                {
                        if( !strcmp( map->cache[i].name, subvmf ) )
                        {
                                return i+1;
                        }
                }
        }
        
        printf( "Loading subvmf: %s\n", subvmf );
        
        id = csr_sb_count( map->cache );
        map->cache = csr_sb_reserve( map->cache, 1, sizeof( struct vmf_instance ));
        struct vmf_instance *inst = &map->cache[ id ];
        
        if( (inst->root = vdf_open_file( subvmf )) )
        {
                csr_sb_use( map->cache );
                
                inst->hash = hash;
                inst->name = csr_malloc( strlen( subvmf )+1 );
                strcpy( inst->name, subvmf );
                
                // Recursive load other instances
                vmf_load_all_instances( map, inst->root );
                
                return id+1;
        }
        else
        {
                fprintf( stderr, "Failed to load instance file\n" );
                return 0;
        }
}

vmf_map *vmf_init( const char *path, int load_models )
{
        vmf_map *map = csr_calloc( sizeof( vmf_map ) );
        map->root = vdf_open_file( path );
        
        if( !map->root )
        {
                free( map );
                return NULL;
        }
        
        // Prepare instances
        vmf_load_all_instances( map, map->root );
        
        // Other resources
        if( load_models )
        {
                vmf_load_models( map );
        }
        
        return map;
}

void vmf_free( vmf_map *map )
{
        for( int i = 0; i < csr_sb_count( map->cache ); i ++ )
        {
                vdf_free_r( map->cache[i].root );
                free( map->cache[i].name );
        }
        
        for( int i = 1; i < csr_sb_count( map->models ); i ++ )
        {
                free( map->models[i].str );
                mdl_free( &map->models[i].mdl );
        }

        vdf_free_r( map->root );
        csr_sb_free( map->models );
        csr_sb_free( map->cache );
        free( map );
}

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 );
        }
}

void vmf_entity_transform( vdf_node *ent, m4x3f mat )
{
        v3f angles = {0.f,0.f,0.f};
        v3f offset = {0.f,0.f,0.f};
        float scale;
        
        // Parse
        scale = kv_get_float( ent, "uniformscale", 1.f );
        kv_float_array( ent, "angles", 3, angles );
        kv_float_array( ent, "origin", 3, offset );
        
        // Translation
        m4x3_translate( mat, offset );
        
        // Make rotation ( Pitch yaw roll // YZX. Source->OpenGL ordering a lil messed up )
        m4x3_rotate_z( mat, csr_rad( angles[1] ) );
        m4x3_rotate_y( mat, csr_rad( angles[0] ) );
        m4x3_rotate_x( mat, csr_rad( angles[2] ) );
        
        // Scale
        m4x3_scale( mat, scale );
}

u32 vmf_visgroup_id( vdf_node *root, const char *name )
{
        vdf_node *dict = vdf_next( root, "visgroups", NULL );
        
        if( dict )
        {
                vdf_foreach( dict, "visgroup", group )
                {
                        if( !strcmp( kv_get( group, "name", "" ), name ) )
                        {
                                return kv_get_int( group, "visgroupid", 0 );
                        }
                }
        }
        
        return 0;
}

int vmf_visgroup_match( vdf_node *ent, u32 target )
{
        vdf_node *editor = vdf_next( ent, "editor", NULL );
        
        if( editor )
        {
                kv_foreach( editor, "visgroupid", groupe )
                {
                        if( target == atoi( groupe ) )
                                return 1;
                }
        }
        
        return 0;
}