cxr/cxr.h

   1 /*
   2                               CONVEXER v0.91
   3
   4                A GNU/Linux-first Source1 Hammer replacement
   5                     built with Blender, for mapmakers
   6
   7                   Copyright (C) 2022 Harry Godden (hgn)
   8
   9    Features:
  10       - Brush decomposition into convex pieces for well defined geometry
  11       - Freely form displacements without limits
  12       - Build your entire map in Blender
  13       - Compile models and model groups easily
  14       - It runs at an ok speed!
  15       - Light patch BSP files; remove unwanted realtime effects
  16       - Bestest VTF compressor (thanks to Richgel999 and stb)
  17       - Pack content automatically
  18
  19    Program structure:
  20
  21    File/folder       Lang     Purpose
  22
  23    __init__.py       Python   Blender plugin interface
  24
  25    cxr/
  26      cxr.h           C        Heavy lifting; brush decomp, mesh processing
  27      cxr_math.h      C        Vector maths and other handy things
  28      cxr_mem.h       C        Automatic resizing buffers
  29      libcxr.c        C        Compile as SO
  30
  31    nbvtf/
  32      nbvtf.h         C        VTF processing interface
  33      librgcx.h       C++      Rich Geldreich's DXT1/DXT5 compressors
  34      stb/            C        Sean Barrets image I/O
  35
  36
  37    HEADER
  38    MACROS
  39    STD INCLUDE
  40    TYPEDEFS
  41    INCLUDE
  42    STRUCTURE DEFS
  43
  44    API
  45
  46    IMPLEMENTATION
  47 */
  48
  49 #define CXR_API
  50 #define CXR_EPSILON 0.001
  51 #define CXR_PLANE_SIMILARITY_MAX 0.998
  52 #define CXR_BIG_NUMBER 1e300
  53 #define CXR_INTERIOR_ANGLE_MAX 0.998
  54
  55 #ifdef CXR_SO
  56  #define CXR_IMPLEMENTATION
  57 #endif
  58
  59 #include <stdio.h>
  60 #include <math.h>
  61 #include <stdint.h>
  62 #include <stdarg.h>
  63 #include <stdlib.h>
  64 #include <string.h>
  65
  66 typedef uint8_t         u8;
  67 typedef uint16_t        u16;
  68 typedef uint32_t        u32;
  69 typedef uint64_t        u64;
  70 typedef int8_t  i8;
  71 typedef int16_t         i16;
  72 typedef int32_t         i32;
  73 typedef int64_t         i64;
  74
  75 typedef unsigned int uint;
  76
  77 typedef double          v2f[2];
  78 typedef double          v3f[3];
  79 typedef double          v4f[4];
  80 typedef v3f                     m3x3f[3];
  81 typedef v3f                     m4x3f[4];
  82 typedef v3f                     boxf[2];
  83
  84 #include "cxr_math.h"
  85 #include "cxr_mem.h"
  86
  87 typedef struct cxr_world cxr_world;
  88 typedef struct cxr_solid cxr_solid;
  89
  90 typedef struct cxr_mesh cxr_mesh;
  91 typedef struct cxr_edge cxr_edge;
  92 typedef struct cxr_polygon cxr_polygon;
  93 typedef struct cxr_static_mesh cxr_static_mesh;
  94 typedef struct cxr_loop cxr_loop;
  95 typedef struct cxr_static_loop cxr_static_loop;
  96 typedef struct cxr_material cxr_material;
  97 typedef struct cxr_tri_mesh cxr_tri_mesh;
  98
  99 #ifdef CXR_VALVE_MAP_FILE
 100  typedef struct cxr_vdf cxr_vdf;
 101  typedef struct cxr_texinfo cxr_texinfo;
 102  typedef struct cxr_visgroup cxr_visgroup;
 103  typedef struct cxr_vmf_context cxr_vmf_context;
 104 #endif /* CXR_VALVE_MAP_FILE */
 105
 106 /*
 107  * Public API
 108  */
 109
 110 /* Main convexer algorithms */
 111 /* Convex decomp from mesh */
 112 CXR_API cxr_world *cxr_decompose( cxr_static_mesh *src, i32 *perrcode );
 113 CXR_API void cxr_free_world( cxr_world *world );
 114 CXR_API cxr_tri_mesh *cxr_world_preview( cxr_world *world );
 115 CXR_API void cxr_free_tri_mesh( cxr_tri_mesh *mesh );
 116
 117 #ifdef CXR_VALVE_MAP_FILE
 118 /* VMF interface */
 119 CXR_API void cxr_begin_vmf( cxr_vmf_context *ctx, cxr_vdf *vdf );
 120 CXR_API void cxr_vmf_begin_entities( cxr_vmf_context *ctx, cxr_vdf *vdf );
 121 CXR_API void cxr_push_world_vmf(
 122       cxr_world *world, cxr_vmf_context *ctx, cxr_vdf *vdf);
 123 CXR_API void cxr_end_vmf( cxr_vmf_context *ctx, cxr_vdf *vdf );
 124
 125 /* VDF interface */
 126 CXR_API cxr_vdf *cxr_vdf_open( const char *path );
 127 CXR_API void cxr_vdf_close( cxr_vdf *vdf );
 128 CXR_API void cxr_vdf_put( cxr_vdf *vdf, const char *str );
 129 CXR_API void cxr_vdf_node( cxr_vdf *vdf, const char *str );
 130 CXR_API void cxr_vdf_edon( cxr_vdf *vdf );
 131 CXR_API void cxr_vdf_kv( cxr_vdf *vdf, const char *strk, const char *strv );
 132
 133 /* Other tools */
 134 CXR_API int cxr_lightpatch_bsp( const char *path );
 135 #endif /* CXR_VALVE_MAP_FILE */
 136
 137 #ifdef CXR_DEBUG
 138 /* Debugging */
 139 CXR_API void cxr_set_log_function( void (*func)(const char *str) );
 140 CXR_API void cxr_set_line_function( void (*func)(v3f p0, v3f p1, v4f colour) );
 141 CXR_API void cxr_write_test_data( cxr_static_mesh *src );
 142 #endif /* CXR_DEBUG */
 143
 144 struct cxr_static_mesh
 145 {
 146    v3f *vertices;
 147
 148    struct cxr_edge
 149    {
 150       i32 i0, i1;
 151       i32 freestyle, sharp;
 152    }
 153    *edges;
 154
 155    struct cxr_static_loop
 156    {
 157       i32 index,
 158           edge_index;
 159       v2f uv;
 160    }
 161    *loops;
 162
 163    struct cxr_polygon
 164    {
 165       i32 loop_start, loop_total;
 166       v3f normal;
 167       v3f center;
 168       i32 material_id; /* -1: interior material (nodraw) */
 169    }
 170    *polys;
 171
 172    struct cxr_material
 173    {
 174       i32 res[2];
 175       char *name;
 176    }
 177    *materials;
 178
 179    i32 poly_count,
 180        vertex_count,
 181        edge_count,
 182        loop_count,
 183        material_count;
 184 };
 185
 186 struct cxr_loop
 187 {
 188    i32 poly_left,
 189        poly_right,
 190        edge_index,
 191        index;
 192    v2f uv;
 193 };
 194
 195 struct cxr_solid
 196 {
 197    cxr_mesh *pmesh;
 198    int displacement,
 199        invalid;
 200 };
 201
 202 struct cxr_world
 203 {
 204    cxr_abuffer abverts,
 205                absolids;
 206
 207    cxr_material *materials;
 208    int material_count;
 209 };
 210
 211 struct cxr_mesh
 212 {
 213    struct cxr_abuffer
 214       abedges,
 215       abloops,
 216       abpolys,
 217
 218       *p_abverts; /* This data is stored externally because the data is often
 219                      shared between solids. */
 220
 221    /* Valid when update() is called on this mesh,
 222     * Invalid when data is appended to them */
 223    struct cxr_edge    *edges;
 224    struct cxr_polygon *polys;
 225    struct cxr_loop    *loops;
 226 };
 227
 228 /* Simple mesh type mainly for debugging */
 229 struct cxr_tri_mesh
 230 {
 231    v3f *vertices;
 232    v4f *colours;
 233    i32 *indices,
 234         indices_count,
 235         vertex_count;
 236 };
 237
 238 #ifdef CXR_VALVE_MAP_FILE
 239 struct cxr_texinfo
 240 {
 241    v3f uaxis, vaxis;
 242    v2f offset, scale;
 243    double winding;
 244 };
 245
 246 struct cxr_visgroup
 247 {
 248    const char *name;
 249 };
 250
 251 /*
 252  * Simplified VDF writing interface. No allocations or nodes, just write to file
 253  */
 254 struct cxr_vdf
 255 {
 256    FILE *fp;
 257    i32 level;
 258 };
 259
 260 struct cxr_vmf_context
 261 {
 262    /* File info */
 263    i32 mapversion;
 264    const char *skyname,
 265               *detailvbsp,
 266               *detailmaterial;
 267
 268    cxr_visgroup *visgroups;
 269    i32 visgroup_count;
 270
 271    /* Transform settings */
 272    double scale;
 273    v3f offset;
 274    i32 lightmap_scale,
 275        visgroupid;
 276
 277    /* Current stats */
 278    i32 brush_count,
 279        entity_count,
 280        face_count;
 281 };
 282 #endif /* CXR_VALVE_MAP_FILE */
 283
 284 enum cxr_soliderr
 285 {
 286    k_soliderr_none = 0,
 287    k_soliderr_non_manifold,
 288    k_soliderr_bad_manifold,
 289    k_soliderr_no_solids,
 290    k_soliderr_degenerate_implicit,
 291    k_soliderr_non_coplanar_vertices,
 292    k_soliderr_non_convex_poly,
 293    k_soliderr_bad_result,
 294    k_soliderr_invalid_input
 295 };
 296
 297 /*
 298  * Implementation
 299  * -----------------------------------------------------------------------------
 300  */
 301 #ifdef CXR_IMPLEMENTATION
 302  #ifdef CXR_SO
 303   const char *cxr_build_time = __DATE__ " @" __TIME__;
 304  #endif
 305
 306 static void (*cxr_log_func)(const char *str);
 307 static void (*cxr_line_func)( v3f p0, v3f p1, v4f colour );
 308
 309 static int cxr_range(int x, int bound)
 310 {
 311    if( x < 0 )
 312       x += bound * (x/bound + 1);
 313
 314    return x % bound;
 315 }
 316
 317 /*
 318  * This should be called after appending any data to those buffers
 319  */
 320 static void cxr_mesh_update( cxr_mesh *mesh )
 321 {
 322    mesh->edges = cxr_ab_ptr(&mesh->abedges, 0);
 323    mesh->polys = cxr_ab_ptr(&mesh->abpolys, 0);
 324    mesh->loops = cxr_ab_ptr(&mesh->abloops, 0);
 325 }
 326
 327 static v4f colours_random[] =
 328 {
 329    { 0.863, 0.078, 0.235, 0.4 },
 330    { 0.000, 0.980, 0.604, 0.4 },
 331    { 0.118, 0.565, 1.000, 0.4 },
 332    { 0.855, 0.439, 0.839, 0.4 },
 333    { 0.824, 0.412, 0.118, 0.4 },
 334    { 0.125, 0.698, 0.667, 0.4 },
 335    { 0.541, 0.169, 0.886, 0.4 },
 336    { 1.000, 0.843, 0.000, 0.4 }
 337 };
 338
 339 static v4f colours_solids[] =
 340 {
 341    { 100, 143, 255, 200 },
 342    { 120,  94, 240, 200 },
 343    { 220,  38, 127, 200 },
 344    { 254,  97,   0, 200 },
 345    { 255, 176,   0, 200 }
 346 };
 347
 348 static v4f colour_entity = { 37, 241, 122, 255 };
 349 static v4f colour_displacement_solid = { 146, 146, 146, 120 };
 350 static v4f colour_error = { 1.0f, 0.0f, 0.0f, 1.0f };
 351 static v4f colour_face_graph = { 1.0f, 1.0f, 1.0f, 0.03f };
 352 static v4f colour_success = { 0.0f, 1.0f, 0.0f, 1.0f };
 353
 354 static void value_random(int n, v4f colour)
 355 {
 356    double val = cxr_range(n,8);
 357    val /= 16.0;
 358    val += 0.75;
 359
 360    v3_muls( colour, val, colour );
 361 }
 362
 363 static void colour_random_brush(int n, v4f colour)
 364 {
 365 #if 1
 366    int value_n = n / 5;
 367    int colour_n = cxr_range( n, 5 );
 368    v4_muls( colours_solids[ colour_n ], 1.0/255.0, colour );
 369    value_random( value_n, colour );
 370 #else
 371    int colour_n = cxr_range( n, 8 );
 372    v4_copy( colours_random[ colour_n ], colour );
 373 #endif
 374 }
 375
 376 /*
 377  * Debugging and diagnostic utilities
 378  * -----------------------------------------------------------------------------
 379  */
 380
 381 #ifdef CXR_DEBUG
 382
 383 static void cxr_log( const char *fmt, ... )
 384 {
 385    char buf[512];
 386
 387    va_list args;
 388    va_start( args, fmt );
 389    vsnprintf( buf, sizeof(buf)-1, fmt, args );
 390    va_end(args);
 391
 392    if( cxr_log_func )
 393       cxr_log_func( buf );
 394
 395    fputs(buf,stdout);
 396 }
 397
 398 static void cxr_debug_line( v3f p0, v3f p1, v4f colour )
 399 {
 400    if( cxr_line_func )
 401       cxr_line_func( p0, p1, colour );
 402 }
 403
 404 static void cxr_debug_box( v3f p0, double sz, v4f colour )
 405 {
 406    v3f a,b,c,d,
 407        a1,b1,c1,d1;
 408    v3_add(p0, (v3f){-sz,-sz,-sz}, a);
 409    v3_add(p0, (v3f){-sz, sz,-sz}, b);
 410    v3_add(p0, (v3f){ sz, sz,-sz}, c);
 411    v3_add(p0, (v3f){ sz,-sz,-sz}, d);
 412    v3_add(p0, (v3f){-sz,-sz,sz}, a1);
 413    v3_add(p0, (v3f){-sz, sz,sz}, b1);
 414    v3_add(p0, (v3f){ sz, sz,sz}, c1);
 415    v3_add(p0, (v3f){ sz,-sz,sz}, d1);
 416
 417    cxr_debug_line( a,b, colour );
 418    cxr_debug_line( b,c, colour );
 419    cxr_debug_line( c,d, colour );
 420    cxr_debug_line( d,a, colour );
 421    cxr_debug_line( a1,b1, colour );
 422    cxr_debug_line( b1,c1, colour );
 423    cxr_debug_line( c1,d1, colour );
 424    cxr_debug_line( d1,a1, colour );
 425    cxr_debug_line( a,a1, colour );
 426    cxr_debug_line( b,b1, colour );
 427    cxr_debug_line( c,c1, colour );
 428    cxr_debug_line( d,d1, colour );
 429 }
 430
 431 /*
 432  * Draw arrow with the tips oriented along normal
 433  */
 434 static void cxr_debug_arrow( v3f p0, v3f p1, v3f normal, double sz, v4f colour )
 435 {
 436    v3f dir, tan, p2, p3;
 437    v3_sub(p1,p0,dir);
 438    v3_normalize(dir);
 439
 440    v3_cross(dir,normal,tan);
 441    v3_muladds( p1,dir, -sz, p2 );
 442    v3_muladds( p2,tan,sz,p3 );
 443    cxr_debug_line( p1, p3, colour );
 444    v3_muladds( p2,tan,-sz,p3 );
 445    cxr_debug_line( p1, p3, colour );
 446    cxr_debug_line( p0, p1, colour );
 447 }
 448
 449 /*
 450  * Draw arrows CCW around polygon, draw normal vector from center
 451  */
 452 static void cxr_debug_poly( cxr_mesh *mesh, cxr_polygon *poly, v4f colour )
 453 {
 454    v3f *verts = cxr_ab_ptr( mesh->p_abverts, 0 );
 455
 456    for( int i=0; i<poly->loop_total; i++ )
 457    {
 458       int lp0 = poly->loop_start+i,
 459           lp1 = poly->loop_start+cxr_range(i+1,poly->loop_total);
 460
 461       int i0 = mesh->loops[ lp0 ].index,
 462           i1 = mesh->loops[ lp1 ].index;
 463
 464       v3f p0, p1;
 465
 466       v3_lerp( verts[i0], poly->center, 0.0075, p0 );
 467       v3_lerp( verts[i1], poly->center, 0.0075, p1 );
 468       v3_muladds( p0, poly->normal, 0.01, p0 );
 469       v3_muladds( p1, poly->normal, 0.01, p1 );
 470
 471       cxr_debug_arrow( p0, p1, poly->normal, 0.05, colour );
 472    }
 473
 474    v3f nrm0;
 475    v3_muladds( poly->center, poly->normal, 0.3, nrm0 );
 476
 477    cxr_debug_line( poly->center, nrm0, colour );
 478 }
 479
 480 static void cxr_debug_mesh(cxr_mesh *mesh, v4f colour )
 481 {
 482    for( int i=0; i<mesh->abpolys.count; i++ )
 483    {
 484       cxr_polygon *poly = &mesh->polys[i];
 485       cxr_debug_poly( mesh, poly, colour );
 486    }
 487 }
 488
 489 CXR_API void cxr_write_test_data( cxr_static_mesh *src )
 490 {
 491    FILE *fp = fopen(
 492       "/home/harry/Documents/blender_addons_remote/addons/convexer/cxr/solid.h",
 493       "w" );
 494
 495    fprintf( fp, "v3f test_verts[] = {\n" );
 496    for( int i=0; i<src->vertex_count; i ++ )
 497    {
 498       fprintf( fp, "   { %f, %f, %f },\n",
 499             src->vertices[i][0],
 500             src->vertices[i][1],
 501             src->vertices[i][2] );
 502    }
 503    fprintf( fp, "};\n" );
 504
 505    fprintf( fp, "cxr_static_loop test_loops[] = {\n" );
 506    for( int i=0; i<src->loop_count; i ++ )
 507    {
 508       fprintf( fp, "   {%d, %d},\n",
 509          src->loops[i].index,
 510          src->loops[i].edge_index);
 511    }
 512    fprintf( fp, "};\n" );
 513
 514    fprintf( fp, "cxr_polygon test_polys[] = {\n" );
 515    for( int i=0; i <src->poly_count; i++ )
 516    {
 517       fprintf( fp, "   {%d, %d, {%f, %f, %f}, {%f, %f, %f}},\n",
 518          src->polys[i].loop_start,
 519          src->polys[i].loop_total,
 520          src->polys[i].normal[0],
 521          src->polys[i].normal[1],
 522          src->polys[i].normal[2],
 523          src->polys[i].center[0],
 524          src->polys[i].center[1],
 525          src->polys[i].center[2] );
 526    }
 527    fprintf( fp, "};\n" );
 528
 529    fprintf( fp, "cxr_edge test_edges[] = {\n" );
 530    for( int i=0; i<src->edge_count; i++ )
 531    {
 532       fprintf( fp, "   {%d, %d, %d, %d},\n",
 533          src->edges[i].i0,
 534          src->edges[i].i1,
 535          src->edges[i].freestyle,
 536          src->edges[i].sharp
 537       );
 538    }
 539    fprintf( fp, "};\n" );
 540
 541    fprintf( fp, "cxr_static_mesh test_mesh = {\n" );
 542    fprintf( fp, "   .vertices = test_verts,\n" );
 543    fprintf( fp, "   .loops = test_loops,\n" );
 544    fprintf( fp, "   .edges = test_edges,\n" );
 545    fprintf( fp, "   .polys = test_polys,\n" );
 546    fprintf( fp, "   .poly_count=%d,\n", src->poly_count );
 547    fprintf( fp, "   .vertex_count=%d,\n", src->vertex_count );
 548    fprintf( fp, "   .edge_count=%d,\n",src->edge_count );
 549    fprintf( fp, "   .loop_count=%d\n", src->loop_count );
 550    fprintf( fp, "};\n" );
 551
 552    fclose( fp );
 553 }
 554
 555 CXR_API void cxr_set_log_function( void (*func)(const char *str) )
 556 {
 557    cxr_log_func = func;
 558 }
 559
 560 CXR_API void cxr_set_line_function( void (*func)(v3f p0, v3f p1, v4f colour) )
 561 {
 562    cxr_line_func = func;
 563 }
 564
 565 #endif /* CXR_DEBUG */
 566
 567
 568 /*
 569  * abverts is a pointer to an existing vertex buffer
 570  */
 571 static cxr_mesh *cxr_alloc_mesh( int edge_count, int loop_count, int poly_count,
 572       cxr_abuffer *abverts
 573 ){
 574    cxr_mesh *mesh = malloc(sizeof(cxr_mesh));
 575    cxr_ab_init(&mesh->abedges, sizeof(cxr_edge), edge_count);
 576    cxr_ab_init(&mesh->abloops, sizeof(cxr_loop), loop_count);
 577    cxr_ab_init(&mesh->abpolys, sizeof(cxr_polygon), poly_count);
 578    mesh->p_abverts = abverts;
 579
 580    cxr_mesh_update( mesh );
 581
 582    return mesh;
 583 }
 584
 585 static void cxr_free_mesh( cxr_mesh *mesh )
 586 {
 587    cxr_ab_free(&mesh->abedges);
 588    cxr_ab_free(&mesh->abloops);
 589    cxr_ab_free(&mesh->abpolys);
 590    free(mesh);
 591 }
 592
 593 /*
 594  * Rebuilds edge data for mesh (useful to get rid of orphaned edges)
 595  */
 596 static void cxr_mesh_clean_edges( cxr_mesh *mesh )
 597 {
 598    cxr_abuffer new_edges;
 599    cxr_ab_init( &new_edges, sizeof(cxr_edge), mesh->abedges.count );
 600
 601    for( int i=0; i<mesh->abpolys.count; i++ )
 602    {
 603       cxr_polygon *poly = &mesh->polys[i];
 604       for( int j=0; j<poly->loop_total; j++ )
 605       {
 606          cxr_loop
 607           *lp0 = &mesh->loops[poly->loop_start+j],
 608           *lp1 = &mesh->loops[poly->loop_start+cxr_range(j+1,poly->loop_total)];
 609
 610          int i0 = cxr_min(lp0->index, lp1->index),
 611              i1 = cxr_max(lp0->index, lp1->index);
 612
 613          /* Check if edge exists before adding */
 614          for( int k=0; k<new_edges.count; k++ )
 615          {
 616             cxr_edge *edge = cxr_ab_ptr(&new_edges,k);
 617
 618             if( edge->i0 == i0 && edge->i1 == i1 )
 619             {
 620                lp0->edge_index = k;
 621                goto IL_EDGE_CREATED;
 622             }
 623          }
 624
 625          int orig_edge_id = lp0->edge_index;
 626          lp0->edge_index = new_edges.count;
 627
 628          cxr_edge edge = { i0, i1 };
 629
 630          /*
 631           * Copy extra information from original edges
 632           */
 633
 634          if( orig_edge_id < mesh->abedges.count )
 635          {
 636             cxr_edge *orig_edge = &mesh->edges[ orig_edge_id ];
 637             edge.freestyle = orig_edge->freestyle;
 638             edge.sharp = orig_edge->sharp;
 639          }
 640          else
 641          {
 642             edge.freestyle = 0;
 643             edge.sharp = 0;
 644          }
 645
 646          cxr_ab_push( &new_edges, &edge );
 647
 648 IL_EDGE_CREATED:;
 649       }
 650    }
 651
 652    cxr_ab_free( &mesh->abedges );
 653    mesh->abedges = new_edges;
 654
 655    cxr_mesh_update( mesh );
 656 }
 657
 658 /*
 659  * Remove 0-length faces from mesh (we mark them light that for deletion
 660  * Remove all unused loops as a result of removing those faces
 661  */
 662 static void cxr_mesh_clean_faces( cxr_mesh *mesh )
 663 {
 664    cxr_abuffer loops_new;
 665    cxr_ab_init( &loops_new, sizeof(cxr_loop), mesh->abloops.count );
 666
 667    int new_length=0;
 668    for( int i=0; i<mesh->abpolys.count; i++ )
 669    {
 670       cxr_polygon *src = &mesh->polys[i],
 671                   *dst = &mesh->polys[new_length];
 672
 673       if( src->loop_total > 0 )
 674       {
 675          int src_start = src->loop_start,
 676              src_total = src->loop_total;
 677
 678          *dst = *src;
 679          dst->loop_start = loops_new.count;
 680
 681          for( int j=0; j<src_total; j++ )
 682          {
 683             cxr_loop *loop = &mesh->loops[src_start+j],
 684                      *ldst = cxr_ab_ptr(&loops_new,dst->loop_start+j);
 685             *ldst = *loop;
 686             ldst->poly_left = new_length;
 687          }
 688
 689          loops_new.count += src_total;
 690          new_length ++;
 691       }
 692    }
 693
 694    cxr_ab_free( &mesh->abloops );
 695    mesh->abloops = loops_new;
 696    mesh->abpolys.count = new_length;
 697
 698    cxr_mesh_update( mesh );
 699 }
 700
 701 /*
 702  * Links loop's poly_left and poly_right
 703  * Does not support more than 2 polys to one edge
 704  *
 705  * Returns 0 if there is non-manifold geomtry (aka: not watertight)
 706  */
 707 static int cxr_mesh_link_loops( cxr_mesh *mesh )
 708 {
 709    i32 *polygon_edge_map = malloc(mesh->abedges.count*2 *sizeof(i32));
 710
 711    for( int i = 0; i < mesh->abedges.count*2; i ++ )
 712       polygon_edge_map[i] = -1;
 713
 714    for( int i = 0; i < mesh->abpolys.count; i ++ )
 715    {
 716       cxr_polygon *poly = &mesh->polys[i];
 717
 718       for( int j = 0; j < poly->loop_total; j ++ )
 719       {
 720          cxr_loop *loop = &mesh->loops[ poly->loop_start+j ];
 721          loop->poly_left = i;
 722
 723          for( int k = 0; k < 2; k ++ )
 724          {
 725             i32 *edge = &polygon_edge_map[loop->edge_index*2+k];
 726
 727             if( *edge == -1 )
 728             {
 729                *edge = i;
 730                goto next;
 731             }
 732          }
 733
 734          /* Overflowed edge mapping... Duplicated faces. */
 735          free( polygon_edge_map );
 736          return 0;
 737
 738          next:;
 739       }
 740    }
 741    for( int i = 0; i < mesh->abpolys.count; i ++ )
 742    {
 743       cxr_polygon *poly = &mesh->polys[i];
 744
 745       for( int j = 0; j < poly->loop_total; j ++ )
 746       {
 747          cxr_loop *loop = &mesh->loops[ poly->loop_start+j ];
 748
 749          i32 *face_map = &polygon_edge_map[ loop->edge_index*2 ];
 750
 751          if( face_map[0] == loop->poly_left ) loop->poly_right = face_map[1];
 752          else loop->poly_right = face_map[0];
 753       }
 754    }
 755
 756
 757    for( int i=0; i<mesh->abedges.count*2; i++ )
 758    {
 759       if( polygon_edge_map[i] == -1 )
 760       {
 761          free( polygon_edge_map );
 762          return 0;
 763       }
 764    }
 765
 766    free( polygon_edge_map );
 767    return 1;
 768 }
 769
 770 /*
 771  * Create new empty polygon with known loop count
 772  * Must be filled and completed by the following functions!
 773  */
 774 static int cxr_create_poly( cxr_mesh *mesh, int loop_count )
 775 {
 776    v3f *verts = cxr_ab_ptr( mesh->p_abverts, 0 );
 777
 778    if( loop_count < 3 )
 779    {
 780 #ifdef CXR_DEBUG
 781       cxr_log( "tried to add new poly with length %d!\n", loop_count );
 782 #endif
 783       return 0;
 784    }
 785
 786    cxr_ab_reserve( &mesh->abpolys, 1 );
 787    cxr_ab_reserve( &mesh->abloops, loop_count );
 788    cxr_mesh_update( mesh );
 789
 790    cxr_polygon *poly = &mesh->polys[ mesh->abpolys.count ];
 791
 792    poly->loop_start = mesh->abloops.count;
 793    poly->loop_total = 0;
 794    poly->material_id = -1;
 795    v3_zero( poly->center );
 796
 797    return 1;
 798 }
 799
 800 /*
 801  * Add one index to the polygon created by the above function
 802  */
 803 static void cxr_poly_push_index( cxr_mesh *mesh, int id )
 804 {
 805    v3f *verts = cxr_ab_ptr( mesh->p_abverts, 0 );
 806
 807    int nface_id = mesh->abpolys.count;
 808    cxr_polygon *poly = &mesh->polys[ nface_id ];
 809
 810    cxr_loop *new_loop = &mesh->loops[ poly->loop_start + poly->loop_total ];
 811
 812    new_loop->poly_left = nface_id;
 813    new_loop->poly_right = -1;
 814    new_loop->index = id;
 815    new_loop->edge_index = 0;
 816    v2_zero(new_loop->uv);
 817
 818    v3_add( poly->center, verts[new_loop->index], poly->center );
 819
 820    poly->loop_total ++;
 821    mesh->abloops.count ++;
 822 }
 823
 824 /*
 825  * Finalize and commit polygon into mesh
 826  */
 827 static void cxr_poly_finish( cxr_mesh *mesh )
 828 {
 829    v3f *verts = cxr_ab_ptr( mesh->p_abverts, 0 );
 830
 831    int nface_id = mesh->abpolys.count;
 832    cxr_polygon *poly = &mesh->polys[nface_id];
 833
 834    /* Average center and calc normal */
 835
 836    v3_divs( poly->center, poly->loop_total, poly->center );
 837    cxr_loop *lp0 = &mesh->loops[ poly->loop_start],
 838             *lp1 = &mesh->loops[ poly->loop_start+1 ],
 839             *lp2 = &mesh->loops[ poly->loop_start+2 ];
 840
 841    tri_normal(
 842     verts[lp0->index], verts[lp1->index], verts[lp2->index], poly->normal);
 843
 844    mesh->abpolys.count ++;
 845 }
 846
 847 /*
 848  * Extract the next island from mesh
 849  *
 850  * Returns NULL if mesh is one contigous object
 851  */
 852 static cxr_mesh *cxr_pull_island( cxr_mesh *mesh )
 853 {
 854    cxr_mesh_link_loops(mesh);
 855
 856    int *island_current = malloc(mesh->abpolys.count*sizeof(int)),
 857         island_len = 1,
 858         loop_count = 0,
 859         last_count;
 860
 861    island_current[0] = 0;
 862
 863    island_grow:
 864    last_count = island_len;
 865
 866    for( int i=0; i<island_len; i++ )
 867    {
 868       cxr_polygon *poly = &mesh->polys[ island_current[i] ];
 869
 870       for( int j=0; j<poly->loop_total; j++ )
 871       {
 872          cxr_loop *loop = &mesh->loops[ poly->loop_start+j ];
 873
 874          if( loop->poly_right != -1 )
 875          {
 876             int face_present = 0;
 877
 878             for( int k=0; k<island_len; k++ )
 879             {
 880                if( island_current[k] == loop->poly_right )
 881                {
 882                   face_present = 1;
 883                   break;
 884                }
 885             }
 886
 887             if( !face_present )
 888                island_current[ island_len ++ ] = loop->poly_right;
 889          }
 890       }
 891    }
 892
 893    if( island_len > last_count )
 894       goto island_grow;
 895
 896    /* Check for complete object */
 897    if( island_len == mesh->abpolys.count )
 898    {
 899       free( island_current );
 900       return NULL;
 901    }
 902
 903    for( int i=0; i<island_len; i++ )
 904    {
 905       cxr_polygon *poly = &mesh->polys[ island_current[i] ];
 906       loop_count += poly->loop_total;
 907    }
 908
 909    /* Create and update meshes */
 910    cxr_mesh *newmesh = cxr_alloc_mesh( mesh->abedges.count,
 911                                               loop_count,
 912                                               island_len,
 913                                               mesh->p_abverts );
 914
 915    for( int i=0; i<island_len; i++ )
 916    {
 917       cxr_polygon *src = &mesh->polys[ island_current[i] ];
 918       cxr_polygon *dst = cxr_ab_ptr(&newmesh->abpolys, i);
 919
 920       *dst = *src;
 921       dst->loop_start = newmesh->abloops.count;
 922
 923       for( int j=0; j<src->loop_total; j++ )
 924       {
 925          cxr_loop
 926             *lsrc = &mesh->loops[ src->loop_start+j ],
 927             *ldst = cxr_ab_ptr(&newmesh->abloops, dst->loop_start+j);
 928
 929          *ldst = *lsrc;
 930          ldst->poly_left = i;
 931          ldst->poly_right = -1;
 932       }
 933
 934       newmesh->abloops.count += src->loop_total;
 935       src->loop_total = -1;
 936    }
 937
 938    newmesh->abpolys.count = island_len;
 939    newmesh->abedges.count = mesh->abedges.count;
 940    memcpy( cxr_ab_ptr(&newmesh->abedges,0),
 941            mesh->edges,
 942            mesh->abedges.count * sizeof(cxr_edge));
 943
 944    cxr_mesh_clean_faces(mesh);
 945    cxr_mesh_clean_edges(mesh);
 946    cxr_mesh_clean_edges(newmesh);
 947
 948    free( island_current );
 949    return newmesh;
 950 }
 951
 952 /*
 953  * Invalid solid is when there are vertices that are coplanar to a face, but are
 954  * outside the polygons edges.
 955  */
 956 static int cxr_valid_solid( cxr_mesh *mesh, int *solid, int len )
 957 {
 958    v3f *verts = cxr_ab_ptr(mesh->p_abverts, 0);
 959
 960    for( int i=0; i<len; i++ )
 961    {
 962       cxr_polygon *polyi = &mesh->polys[ solid[i] ];
 963
 964       v4f plane;
 965       normal_to_plane(polyi->normal, polyi->center, plane);
 966
 967       for( int j=0; j<len; j++ )
 968       {
 969          if( i==j ) continue;
 970
 971          cxr_polygon *polyj = &mesh->polys[ solid[j] ];
 972
 973          for( int k=0; k<polyj->loop_total; k++ )
 974          {
 975             cxr_loop *lpj = &mesh->loops[ polyj->loop_start+k ];
 976
 977             /* Test if the vertex is not referenced by the polygon */
 978             for( int l=0; l<polyi->loop_total; l++ )
 979             {
 980                cxr_loop *lpi = &mesh->loops[ polyi->loop_start+l ];
 981
 982                if( lpi->index == lpj->index )
 983                   goto skip_vertex;
 984             }
 985
 986             if( fabs(plane_polarity(plane, verts[lpj->index])) < 0.001 )
 987                return 0;
 988
 989             skip_vertex:;
 990          }
 991       }
 992    }
 993
 994    return 1;
 995 }
 996
 997 /*
 998  * Use when iterating the loops array, to get a unique set of edges
 999  * Better than using the edges array and doing many more checks
1000  */
1001 static int cxr_loop_unique_edge( cxr_loop *lp )
1002 {
1003    if( lp->poly_left > lp->poly_right )
1004       return 0;
1005
1006    return 1;
1007 }
1008
1009 /*
1010  * Identify edges in the mesh where the two connected face's normals
1011  * are opposing eachother (or close to identical)
1012  */
1013 static int *cxr_mesh_reflex_edges( cxr_mesh *mesh )
1014 {
1015    v3f *verts = cxr_ab_ptr( mesh->p_abverts, 0 );
1016    int *edge_tagged = malloc( mesh->abedges.count * sizeof(int) );
1017
1018    for( int i=0; i<mesh->abloops.count; i++ )
1019    {
1020       cxr_loop *lp = &mesh->loops[i];
1021       if( !cxr_loop_unique_edge( lp ) ) continue;
1022
1023       edge_tagged[lp->edge_index] = 0;
1024
1025       cxr_polygon *polya = &mesh->polys[ lp->poly_left ],
1026                   *polyb = &mesh->polys[ lp->poly_right ];
1027
1028       v4f planeb;
1029       normal_to_plane(polyb->normal, polyb->center, planeb);
1030
1031       for( int j=0; j<polya->loop_total; j++ )
1032       {
1033          cxr_loop *lp1 = &mesh->loops[ polya->loop_start+j ];
1034
1035          if(( plane_polarity( planeb, verts[lp1->index] ) > 0.001 ) ||
1036             ( v3_dot(polya->normal,polyb->normal) > CXR_PLANE_SIMILARITY_MAX ))
1037          {
1038             edge_tagged[lp->edge_index] = 1;
1039             break;
1040          }
1041       }
1042    }
1043
1044    return edge_tagged;
1045 }
1046
1047 /*
1048  * Same logic as above function except it will apply it to each vertex
1049  */
1050 static int *cxr_mesh_reflex_vertices( cxr_mesh *mesh )
1051 {
1052    v3f *verts = cxr_ab_ptr( mesh->p_abverts, 0 );
1053
1054    int *vertex_tagged = malloc( mesh->p_abverts->count*sizeof(int) );
1055    int *connected_planes = malloc( mesh->abpolys.count*sizeof(int) );
1056
1057    for( int i=0; i<mesh->p_abverts->count; i++ )
1058    {
1059       vertex_tagged[i]=0;
1060       int num_connected = 0;
1061
1062       /* Create a list of polygons that refer to this vertex */
1063       for( int j=0; j<mesh->abpolys.count; j++ )
1064       {
1065          cxr_polygon *poly = &mesh->polys[j];
1066          for( int k=0; k<poly->loop_total; k++ )
1067          {
1068             cxr_loop *loop = &mesh->loops[poly->loop_start+k];
1069             if( loop->index == i )
1070             {
1071                connected_planes[num_connected ++] = j;
1072                break;
1073             }
1074          }
1075       }
1076
1077       /* Check all combinations for a similar normal */
1078       for( int j=0; j<num_connected-1; j++ )
1079       {
1080          for( int k=j+1; k<num_connected; k++ )
1081          {
1082             cxr_polygon *polyj = &mesh->polys[connected_planes[j]],
1083                                *polyk = &mesh->polys[connected_planes[k]];
1084
1085             if( v3_dot(polyj->normal,polyk->normal) > CXR_PLANE_SIMILARITY_MAX )
1086                goto tag_vert;
1087          }
1088       }
1089
1090       /*
1091        * Check if all connected planes either:
1092        *  - Bound this vert
1093        *  - Coplanar with it
1094        */
1095       for( int j=0; j<num_connected; j++ )
1096       {
1097          for( int k=j+1; k<num_connected; k++ )
1098          {
1099             cxr_polygon *jpoly = &mesh->polys[ connected_planes[j] ],
1100                                *kpoly = &mesh->polys[ connected_planes[k] ];
1101
1102             v4f plane;
1103             normal_to_plane( kpoly->normal, kpoly->center, plane );
1104             for( int l=0; l<jpoly->loop_total; l++ )
1105             {
1106                cxr_loop *lp = &mesh->loops[ jpoly->loop_start+l ];
1107
1108                if( plane_polarity( plane, verts[lp->index] ) > 0.001 )
1109                   goto tag_vert;
1110             }
1111          }
1112       }
1113
1114       continue;
1115 tag_vert:
1116       vertex_tagged[i] = 1;
1117    }
1118
1119    free( connected_planes );
1120    return vertex_tagged;
1121 }
1122
1123 /*
1124  * Detect if potential future edges create a collision with any of the
1125  * existing edges in the mesh
1126  */
1127 static int cxr_solid_overlap( cxr_mesh *mesh,
1128    cxr_polygon *pa,
1129    cxr_polygon *pb,
1130    int common_edge_index
1131 ){
1132    v3f *verts = cxr_ab_ptr( mesh->p_abverts, 0 );
1133    cxr_edge *common_edge = &mesh->edges[common_edge_index];
1134
1135    int unique_a = pa->loop_total-2,
1136        unique_b = pb->loop_total-2;
1137
1138    int *unique_verts = malloc( (unique_a+unique_b)*sizeof(int) );
1139    int unique_total = 0;
1140
1141    for( int j=0; j<2; j++ )
1142    {
1143       cxr_polygon *poly = (cxr_polygon *[2]){pa,pb}[j];
1144
1145       for( int i=0; i<poly->loop_total; i++ )
1146       {
1147          cxr_loop *lp = &mesh->loops[poly->loop_start+i];
1148
1149          if( lp->index == common_edge->i0 || lp->index == common_edge->i1 )
1150             continue;
1151
1152          unique_verts[ unique_total ++ ] = lp->index;
1153       }
1154    }
1155
1156    v3f ca, cb;
1157
1158    for( int i=0; i<unique_a; i++ )
1159    {
1160       for( int j=unique_a; j<unique_total; j++ )
1161       {
1162          int i0 = unique_verts[i],
1163              i1 = unique_verts[j];
1164
1165          for( int k=0; k<mesh->abedges.count; k++ )
1166          {
1167             cxr_edge *edge = &mesh->edges[k];
1168
1169             if( edge->i0 == i0 || edge->i0 == i1 ||
1170                 edge->i1 == i0 || edge->i1 == i1 ) continue;
1171
1172             double *a0 = verts[i0],
1173                    *a1 = verts[i1],
1174                    *b0 = verts[edge->i0],
1175                    *b1 = verts[edge->i1];
1176
1177             double dist = segment_segment_dist( a0, a1, b0, b1, ca, cb );
1178
1179             if( dist < 0.025 )
1180             {
1181                free( unique_verts );
1182                return 1;
1183             }
1184          }
1185       }
1186    }
1187
1188    free( unique_verts );
1189    return 0;
1190 }
1191
1192 /*
1193  * Creates the 'maximal' solid that originates from this faceid
1194  *
1195  * Returns the number of faces used
1196  */
1197 static int cxr_buildsolid(
1198    cxr_mesh *mesh,
1199    int faceid,
1200    int *solid,
1201    int *reflex_edges,
1202    int *faces_tagged )
1203 {
1204    faces_tagged[faceid] = faceid;
1205
1206    int solid_len = 0;
1207    solid[solid_len++] = faceid;
1208
1209    int search_start = 0;
1210
1211 search_iterate:;
1212
1213    int changed = 0;
1214    for( int j=search_start; j<solid_len; j++ )
1215    {
1216       cxr_polygon *poly = &mesh->polys[ solid[j] ];
1217
1218       for( int k=0; k<poly->loop_total; k++ )
1219       {
1220          cxr_loop *loop = &mesh->loops[ poly->loop_start+k ];
1221          cxr_edge *edge = &mesh->edges[ loop->edge_index ];
1222
1223          if( faces_tagged[ loop->poly_right ] == -1 )
1224          {
1225             if( !reflex_edges[loop->edge_index] )
1226             {
1227                /* Check for dodgy edges */
1228                cxr_polygon *newpoly = &mesh->polys[loop->poly_right];
1229
1230                if( cxr_solid_overlap(mesh,poly,newpoly,loop->edge_index))
1231                   goto skip_plane;
1232
1233                /* Looking ahead by one step gives us an early out for invalid
1234                 * configurations. This might just all be handled by the new
1235                 * edge overlap detector, though.
1236                 */
1237                for( int l=0; l < newpoly->loop_total; l++ )
1238                {
1239                   cxr_loop *lp1 = &mesh->loops[ newpoly->loop_start+l ];
1240                   cxr_polygon *future_face = &mesh->polys[ lp1->poly_right ];
1241
1242                   if( reflex_edges[ lp1->edge_index ]
1243                      || lp1->poly_right == loop->poly_right )
1244                      goto dont_check;
1245
1246                   for( int m=0; m<solid_len; m++ )
1247                      if( solid[m] == lp1->poly_right )
1248                         goto dont_check;
1249
1250                   for( int m=0; m<solid_len; m++ )
1251                   {
1252                      cxr_polygon *polym = &mesh->polys[solid[m]];
1253                      double pdist = v3_dot( polym->normal,future_face->normal);
1254
1255                      if( pdist > CXR_PLANE_SIMILARITY_MAX )
1256                         goto dont_check;
1257                   }
1258
1259                   dont_check:;
1260                }
1261
1262                /* Check for vertices in the new polygon that exist on a current
1263                 * plane. This condition is invalid */
1264                solid[ solid_len ] = loop->poly_right;
1265
1266                if( cxr_valid_solid(mesh,solid,solid_len+1 ) )
1267                {
1268                   faces_tagged[ loop->poly_right ] = faceid;
1269                   changed = 1;
1270                   solid_len ++;
1271                }
1272             }
1273
1274             skip_plane:;
1275          }
1276       }
1277    }
1278    search_start = solid_len;
1279    if(changed)
1280       goto search_iterate;
1281
1282    return solid_len;
1283 }
1284
1285 struct csolid
1286 {
1287    int start, count, edge_count;
1288    v3f center;
1289 };
1290
1291 struct temp_manifold
1292 {
1293    struct manifold_loop
1294    {
1295       cxr_loop loop;
1296       int split;
1297    }
1298    *loops;
1299
1300    int loop_count,
1301        split_count;
1302
1303    enum manifold_status
1304    {
1305       k_manifold_err,
1306       k_manifold_none,
1307       k_manifold_fragmented,
1308       k_manifold_complete,
1309    }
1310    status;
1311 };
1312
1313 /*
1314  * Create polygon from entire manifold structure.
1315  *
1316  * Must be completely co-planar
1317  */
1318 static void cxr_create_poly_full( cxr_mesh *mesh, struct temp_manifold *src )
1319 {
1320    if( cxr_create_poly( mesh, src->loop_count ) )
1321    {
1322       for( int l=0; l<src->loop_count; l++ )
1323          cxr_poly_push_index( mesh, src->loops[ l ].loop.index);
1324
1325       cxr_poly_finish( mesh );
1326    }
1327 }
1328
1329 /*
1330  * Links up all edges into a potential new manifold
1331  *
1332  * The return status can be:
1333  *        (err): Critical programming error
1334  *         none: No manifold to create
1335  *   fragmented: Multiple sections exist, not just one
1336  *     complete: Optimial manifold was created
1337  */
1338 static void cxr_link_manifold(
1339    cxr_mesh *mesh,
1340    struct csolid *solid,
1341    int *solid_buffer,
1342    struct temp_manifold *manifold
1343 ){
1344    cxr_loop **edge_list = malloc( sizeof(*edge_list) * solid->edge_count );
1345    int *temp_solid = malloc( solid->count *sizeof(int) );
1346    int  temp_solid_len = 0;
1347
1348    int init_reverse = 0;
1349    int unique_edge_count = 0;
1350
1351    /* Try remove splitting faces first */
1352    {
1353       int split_total = 0;
1354       for( int j=0; j<solid->count; j++ )
1355       {
1356          cxr_polygon *poly = &mesh->polys[ solid_buffer[solid->start+j] ];
1357          int interior_count = 0;
1358
1359          for( int k=0; k<poly->loop_total; k++ )
1360          {
1361             cxr_loop *loop = &mesh->loops[ poly->loop_start+k ];
1362
1363             for( int l=0; l<solid->count; l++ )
1364                if( loop->poly_right == solid_buffer[solid->start+l] )
1365                {
1366                   interior_count ++;
1367                   goto next;
1368                }
1369
1370             next:;
1371          }
1372
1373          if( interior_count < poly->loop_total-1 )
1374          {
1375             split_total ++;
1376             continue;
1377          }
1378
1379          temp_solid[ temp_solid_len ++ ] = solid_buffer[solid->start+j];
1380       }
1381
1382       if( temp_solid_len < 3 || (split_total & 0x2) /* unkown reasons */ )
1383       {
1384       }
1385       else
1386       {
1387          /* Overwrite original solid */
1388          for( int j=0; j<temp_solid_len; j++ )
1389             solid_buffer[ solid->start+j ] = temp_solid[ j ];
1390
1391          solid->count = temp_solid_len;
1392       }
1393
1394       free( temp_solid );
1395    }
1396
1397    for( int j=0; j<solid->count; j++ )
1398    {
1399       cxr_polygon *poly = &mesh->polys[ solid_buffer[solid->start+j] ];
1400
1401       /* when discarding, if a face has only one loop that points outwards,
1402        * we keep it */
1403
1404
1405       for( int k=0; k<poly->loop_total; k++ )
1406       {
1407          cxr_loop *loop = &mesh->loops[ poly->loop_start+k ];
1408
1409          for( int l=0; l<unique_edge_count; l++ )
1410             if( edge_list[l]->edge_index == loop->edge_index )
1411                goto skip_edge;
1412
1413          for( int l=0; l<solid->count; l++ )
1414             if( loop->poly_right == solid_buffer[solid->start+l] )
1415                goto skip_edge;
1416
1417          edge_list[ unique_edge_count ] = loop;
1418
1419          if( unique_edge_count == 0 )
1420          {
1421             cxr_edge *edgeptr = &mesh->edges[ loop->edge_index ];
1422             if( edgeptr->i1 == loop->index )
1423                init_reverse = 1;
1424          }
1425
1426          unique_edge_count ++;
1427          skip_edge:;
1428       }
1429    }
1430
1431    if( unique_edge_count == 0 )
1432    {
1433       free( edge_list );
1434       manifold->status = k_manifold_none;
1435       return;
1436    }
1437
1438    /* Link edges together to form manifold */
1439    manifold->loops = malloc( solid->edge_count*sizeof(struct manifold_loop));
1440    manifold->split_count = 0;
1441    manifold->loop_count = 0;
1442
1443    cxr_edge *current = &mesh->edges[ edge_list[0]->edge_index ];
1444
1445    int endpt = (!init_reverse)? current->i0: current->i1,
1446        start = endpt,
1447      curface = edge_list[0]->poly_left;
1448
1449    manifold_continue:
1450    for( int j=0; j<unique_edge_count; j++ )
1451    {
1452       cxr_edge *other = &mesh->edges[ edge_list[j]->edge_index ];
1453       if( other == current )
1454          continue;
1455
1456       if( other->i0 == endpt || other->i1 == endpt )
1457       {
1458          current = other;
1459          int lastpt = endpt;
1460
1461          if( other->i0 == endpt ) endpt = current->i1;
1462          else endpt = current->i0;
1463
1464          struct manifold_loop *ml = &manifold->loops[ manifold->loop_count ++ ];
1465
1466          if( curface==edge_list[j]->poly_left )
1467          {
1468             ml->split = 1;
1469             manifold->split_count ++;
1470          }
1471          else
1472             ml->split = 0;
1473
1474          ml->loop.edge_index = edge_list[j]->edge_index;
1475          ml->loop.poly_left = edge_list[j]->poly_left;
1476          ml->loop.index = lastpt;
1477          ml->loop.poly_right = edge_list[j]->poly_right;
1478
1479          curface = edge_list[j]->poly_left;
1480
1481          if(endpt == start)
1482          {
1483             if( manifold->loop_count < unique_edge_count )
1484                manifold->status = k_manifold_fragmented;
1485             else
1486                manifold->status = k_manifold_complete;
1487
1488             goto manifold_complete;
1489          }
1490
1491          goto manifold_continue;
1492       }
1493    }
1494
1495    /* Incomplete links */
1496    manifold->status = k_manifold_err;
1497
1498 manifold_complete:
1499
1500    free( edge_list );
1501    return;
1502 }
1503
1504 /*
1505  * Reconstruct implied internal geometry where the manifold doesn't have
1506  * enough information (vertices) to create a full result.
1507  */
1508 static int cxr_build_implicit_geo( cxr_mesh *mesh, int new_polys, int start )
1509 {
1510    for( int i=0; i<new_polys-2; i++ )
1511    {
1512       for( int j=i+1; j<new_polys-1; j++ )
1513       {
1514          for( int k=j+1; k<new_polys; k++ )
1515          {
1516             cxr_polygon *ptri = &mesh->polys[ start+i ],
1517                         *ptrj = &mesh->polys[ start+j ],
1518                         *ptrk = &mesh->polys[ start+k ];
1519
1520             v4f planei, planej, planek;
1521             normal_to_plane(ptri->normal,ptri->center,planei);
1522             normal_to_plane(ptrj->normal,ptrj->center,planej);
1523             normal_to_plane(ptrk->normal,ptrk->center,planek);
1524
1525             v3f intersect;
1526
1527             if( plane_intersect(planei,planej,planek,intersect) )
1528             {
1529                /* Make sure the point is inside the convex region */
1530
1531                int point_valid = 1;
1532                for( int l=0; l<mesh->abpolys.count; l++ )
1533                {
1534                   cxr_polygon *ptrl = &mesh->polys[l];
1535                   v4f planel;
1536
1537                   normal_to_plane(ptrl->normal, ptrl->center, planel);
1538
1539                   if( plane_polarity( planel, intersect ) > 0.01 )
1540                   {
1541 #ifdef CXR_DEBUG
1542                      cxr_log( "degen vert, planes %d, %d, %d [max:%d]\n",
1543                                i,j,k, new_polys );
1544
1545                      cxr_debug_poly( mesh, ptri, colours_random[3] );
1546                      cxr_debug_poly( mesh, ptrj, colours_random[1] );
1547                      cxr_debug_poly( mesh, ptrk, colours_random[2] );
1548 #endif
1549
1550                      return 0;
1551                   }
1552                }
1553
1554                /* Extend faces to include this vert */
1555
1556                int nvertid = mesh->p_abverts->count;
1557                cxr_ab_push( mesh->p_abverts, intersect );
1558
1559                ptrj->loop_start += 1;
1560                ptrk->loop_start += 2;
1561
1562                cxr_ab_reserve( &mesh->abloops, 3);
1563
1564                int newi = ptri->loop_start+ptri->loop_total,
1565                    newj = ptrj->loop_start+ptrj->loop_total,
1566                    newk = ptrk->loop_start+ptrk->loop_total;
1567
1568                cxr_loop
1569                   *lloopi = cxr_ab_empty_at(&mesh->abloops, newi),
1570                   *lloopj = cxr_ab_empty_at(&mesh->abloops, newj),
1571                   *lloopk = cxr_ab_empty_at(&mesh->abloops, newk);
1572
1573                lloopi->index = nvertid;
1574                lloopi->edge_index = 0;
1575                lloopi->poly_left = start + i;
1576                lloopi->poly_right = -1;
1577
1578                lloopj->index = nvertid;
1579                lloopj->poly_left = start + j;
1580                lloopj->edge_index = 0;
1581                lloopj->poly_right = -1;
1582
1583                lloopk->index = nvertid;
1584                lloopk->edge_index = 0;
1585                lloopk->poly_left = start + k;
1586                lloopk->poly_right = -1;
1587
1588                v2_zero(lloopi->uv);
1589                v2_zero(lloopj->uv);
1590                v2_zero(lloopk->uv);
1591
1592                ptri->loop_total ++;
1593                ptrj->loop_total ++;
1594                ptrk->loop_total ++;
1595
1596                double qi = 1.0/(double)ptri->loop_total,
1597                       qj = 1.0/(double)ptrj->loop_total,
1598                       qk = 1.0/(double)ptrk->loop_total;
1599
1600                /* Adjust centers of faces */
1601                v3_lerp( ptri->center, intersect, qi, ptri->center );
1602                v3_lerp( ptrj->center, intersect, qj, ptrj->center );
1603                v3_lerp( ptrk->center, intersect, qk, ptrk->center );
1604             }
1605          }
1606       }
1607    }
1608
1609    return 1;
1610 }
1611
1612 static int cxr_reflex_err( cxr_mesh *mesh )
1613 {
1614    int error = 0;
1615    int *reflex_check = cxr_mesh_reflex_edges( mesh );
1616
1617    v3f *temp = cxr_ab_ptr(mesh->p_abverts, 0);
1618
1619    for( int i=0; i<mesh->abedges.count; i++ )
1620    {
1621       if( reflex_check[i] )
1622       {
1623          cxr_debug_line( temp[mesh->edges[i].i0],
1624                          temp[mesh->edges[i].i1],
1625                          colour_error );
1626          error ++;
1627       }
1628    }
1629
1630    free( reflex_check );
1631    return error;
1632 }
1633
1634 static int cxr_non_manifold_err( cxr_mesh *mesh )
1635 {
1636    if( !cxr_mesh_link_loops(mesh) )
1637    {
1638 #ifdef CXR_DEBUG
1639       cxr_log( "non-manifold edges are in the mesh: "
1640                "implicit internal geometry does not have full support\n" );
1641
1642       v3f *verts = cxr_ab_ptr( mesh->p_abverts, 0 );
1643
1644       for( int i=0; i<mesh->abloops.count; i++ )
1645       {
1646          cxr_loop *lp = &mesh->loops[i];
1647          cxr_edge *edge = &mesh->edges[lp->edge_index];
1648          cxr_debug_line( verts[edge->i0], verts[edge->i1], colours_random[1] );
1649
1650          if( lp->poly_left == -1 || lp->poly_right == -1 )
1651          {
1652             cxr_debug_line( verts[edge->i0], verts[edge->i1], colour_error );
1653          }
1654       }
1655 #endif
1656       return 1;
1657    }
1658
1659    return 0;
1660 }
1661
1662 /*
1663  * Convexer's main algorithm
1664  *
1665  * Return the best availible convex solid from mesh, and patch the existing mesh
1666  * to fill the gap where the new mesh left it.
1667  *
1668  * Returns NULL if shape is already convex or empty.
1669  * This function will not preserve edge data such as freestyle, sharp etc.
1670  */
1671 static cxr_mesh *cxr_pull_best_solid(
1672       cxr_mesh *mesh,
1673       int preserve_more_edges,
1674       enum cxr_soliderr *err )
1675 {
1676    *err = k_soliderr_none;
1677
1678    if( cxr_non_manifold_err( mesh ) )
1679    {
1680       *err = k_soliderr_non_manifold;
1681       return NULL;
1682    }
1683
1684    int *edge_tagged = cxr_mesh_reflex_edges( mesh );
1685    int *vertex_tagged = cxr_mesh_reflex_vertices( mesh );
1686
1687    /*
1688     * Connect all marked vertices that share an edge
1689     */
1690
1691    int *edge_important = malloc(mesh->abedges.count*sizeof(int));
1692    for( int i=0; i< mesh->abedges.count; i++ )
1693       edge_important[i] = 0;
1694
1695    for( int i=0; i<mesh->abpolys.count; i ++ )
1696    {
1697       cxr_polygon *poly = &mesh->polys[i];
1698       int not_tagged = -1,
1699           tag_count = 0;
1700
1701       for( int j=0; j<poly->loop_total; j++ )
1702       {
1703          cxr_loop *loop = &mesh->loops[ poly->loop_start+j ];
1704
1705          if( !edge_tagged[ loop->edge_index ] )
1706          {
1707             if( not_tagged == -1 )
1708                not_tagged = loop->edge_index;
1709             else
1710                goto edge_unimportant;
1711          }
1712       }
1713
1714       if( not_tagged != -1 )
1715          edge_important[not_tagged]=1;
1716
1717       edge_unimportant:;
1718    }
1719
1720    /*
1721     * Connect edges where both vertices are reflex, only if we are not
1722     * preserving them
1723     */
1724    for( int i=0; i<mesh->abedges.count; i ++ )
1725    {
1726       if( edge_important[i] && preserve_more_edges ) continue;
1727
1728       cxr_edge *edge = &mesh->edges[i];
1729       if( vertex_tagged[edge->i0] && vertex_tagged[edge->i1] )
1730          edge_tagged[i] = 1;
1731    }
1732
1733    free( edge_important );
1734
1735    int *faces_tagged = malloc(mesh->abpolys.count*sizeof(int));
1736    for( int i=0; i<mesh->abpolys.count; i++ )
1737       faces_tagged[i] = -1;
1738
1739    struct csolid *candidates;
1740    int *solid_buffer = malloc( mesh->abpolys.count*sizeof(int) ),
1741         solid_buffer_len = 0,
1742         candidate_count = 0;
1743
1744    candidates = malloc( mesh->abpolys.count *sizeof(struct csolid) );
1745
1746    /*
1747     * Create a valid, non-overlapping solid for every face present in the mesh
1748     */
1749    for( int i=0; i<mesh->abpolys.count; i++ )
1750    {
1751       if( faces_tagged[i] != -1 ) continue;
1752       faces_tagged[i] = i;
1753
1754       int *solid = &solid_buffer[ solid_buffer_len ];
1755       int len = cxr_buildsolid( mesh, i, solid, edge_tagged, faces_tagged );
1756
1757       /* add entry */
1758       struct csolid *csolid = &candidates[candidate_count ++];
1759       csolid->start = solid_buffer_len;
1760       csolid->count = len;
1761       csolid->edge_count = 0;
1762
1763       v3_zero( csolid->center );
1764       for( int j=0; j<len; j++ )
1765       {
1766          cxr_polygon *polyj = &mesh->polys[ solid[j] ];
1767          v3_add( polyj->center, csolid->center, csolid->center );
1768          csolid->edge_count += polyj->loop_total;
1769       }
1770       v3_divs( csolid->center, len, csolid->center );
1771       solid_buffer_len += len;
1772    }
1773
1774    free( edge_tagged );
1775    free( vertex_tagged );
1776    free( faces_tagged );
1777
1778    /*
1779     * Choosing the best solid: most defined manifold
1780     */
1781    struct csolid *best_solid = NULL;
1782    int fewest_manifold_splits = INT32_MAX;
1783
1784    struct temp_manifold best_manifold = { .loops = NULL, .loop_count = 0 };
1785    int max_solid_faces = 0;
1786
1787    for( int i=0; i<candidate_count; i++ )
1788    {
1789       struct csolid *solid = &candidates[i];
1790       max_solid_faces = cxr_max(max_solid_faces,solid->count);
1791
1792       if( solid->count <= 2 )
1793          continue;
1794
1795       struct temp_manifold manifold;
1796       cxr_link_manifold( mesh, solid, solid_buffer, &manifold);
1797
1798       if( manifold.status == k_manifold_err )
1799       {
1800          *err = k_soliderr_bad_manifold;
1801
1802          free(solid_buffer);
1803          free(candidates);
1804          free(manifold.loops);
1805          free(best_manifold.loops);
1806          return NULL;
1807       }
1808
1809       if( manifold.status == k_manifold_complete )
1810       {
1811          if( manifold.split_count < fewest_manifold_splits )
1812          {
1813             fewest_manifold_splits = manifold.split_count;
1814             best_solid = solid;
1815
1816             free( best_manifold.loops );
1817             best_manifold = manifold;
1818             continue;
1819          }
1820       }
1821
1822       if( manifold.status != k_manifold_none )
1823          free( manifold.loops );
1824    }
1825
1826    if( max_solid_faces < 2 )
1827    {
1828       *err = k_soliderr_no_solids;
1829       free(solid_buffer);
1830       free(candidates);
1831       free(best_manifold.loops);
1832       return NULL;
1833    }
1834
1835    if( best_solid != NULL )
1836    {
1837       cxr_mesh *pullmesh = cxr_alloc_mesh( best_solid->edge_count,
1838                                            best_solid->edge_count,
1839                                            best_solid->count,
1840                                            mesh->p_abverts );
1841
1842       for( int i=0; i<best_solid->count; i++ )
1843       {
1844          int nface_id = pullmesh->abpolys.count;
1845          int exist_plane_id = solid_buffer[best_solid->start+i];
1846
1847          cxr_polygon *exist_face = &mesh->polys[ exist_plane_id ],
1848                      *new_face = cxr_ab_empty( &pullmesh->abpolys );
1849
1850          *new_face = *exist_face;
1851          new_face->loop_start = pullmesh->abloops.count;
1852
1853          for( int j=0; j<exist_face->loop_total; j++ )
1854          {
1855             cxr_loop *exist_loop = &mesh->loops[ exist_face->loop_start+j ],
1856                      *new_loop = cxr_ab_empty(&pullmesh->abloops);
1857
1858             new_loop->index = exist_loop->index;
1859             new_loop->poly_left = nface_id;
1860             new_loop->poly_right = -1;
1861             new_loop->edge_index = 0;
1862             v2_copy( exist_loop->uv, new_loop->uv );
1863          }
1864
1865          exist_face->loop_total = -1;
1866       }
1867
1868       int new_polys = 0;
1869       int pullmesh_new_start = pullmesh->abpolys.count;
1870
1871       if( fewest_manifold_splits != 0 )
1872       {
1873          /* Unusual observation:
1874           *   If the split count is odd, the manifold can be created easily
1875           *
1876           *   If it is even, implicit internal geometry is needed to be
1877           *   constructed. So the manifold gets folded as we create it segment
1878           *   by segment.
1879           *
1880           *   I'm not sure if this is a well defined rule of geometry, but seems
1881           *   to apply to the data we care about.
1882           */
1883          int collapse_used_segments = (u32)fewest_manifold_splits & 0x1? 0: 1;
1884
1885          manifold_repeat:
1886
1887          for( int j=0; j < best_manifold.loop_count; j++ )
1888          {
1889             if( !best_manifold.loops[j].split ) continue;
1890
1891             cxr_loop *loop = &best_manifold.loops[j].loop;
1892
1893             for( int k=1; k< best_manifold.loop_count; k++ )
1894             {
1895                int index1 = cxr_range(j+k, best_manifold.loop_count );
1896                cxr_loop *loop1 = &best_manifold.loops[index1].loop;
1897
1898                if( best_manifold.loops[index1].split )
1899                {
1900                   if( k==1 )
1901                      break;
1902
1903                   new_polys ++;
1904
1905                   if( new_polys > best_manifold.loop_count )
1906                   {
1907 #ifdef CXR_DEBUG
1908                      cxr_log( "Programming error: Too many new polys!\n" );
1909 #endif
1910                      exit(1);
1911                   }
1912
1913                   if( cxr_create_poly( pullmesh, k+1 ) )
1914                   {
1915                      for( int l=0; l<k+1; l++ )
1916                      {
1917                         int i0 = cxr_range(j+l, best_manifold.loop_count ),
1918                             index = best_manifold.loops[ i0 ].loop.index;
1919
1920                         cxr_poly_push_index( pullmesh, index );
1921                      }
1922                      cxr_poly_finish( pullmesh );
1923                   }
1924
1925                   /* Collapse down manifold */
1926                   if( collapse_used_segments )
1927                   {
1928                      best_manifold.loops[j].split = 0;
1929                      best_manifold.loops[index1].split = 0;
1930
1931                      int new_length = (best_manifold.loop_count-(k-1));
1932
1933                      struct temp_manifold new_manifold = {
1934                         .loop_count = new_length
1935                      };
1936                      new_manifold.loops =
1937                         malloc( new_length*sizeof(*new_manifold.loops) );
1938
1939                      for( int l=0; l<new_length; l ++ )
1940                      {
1941                         int i_src = cxr_range( j+k+l, best_manifold.loop_count);
1942                         new_manifold.loops[l] = best_manifold.loops[i_src];
1943                      }
1944
1945                      free( best_manifold.loops );
1946                      best_manifold = new_manifold;
1947
1948                      goto manifold_repeat;
1949                   }
1950
1951                   j=j+k-1;
1952                   break;
1953                }
1954             }
1955          }
1956
1957          if( best_manifold.loop_count && collapse_used_segments )
1958          {
1959             cxr_create_poly_full( pullmesh, &best_manifold );
1960             new_polys ++;
1961          }
1962       }
1963       else
1964       {
1965          cxr_create_poly_full( pullmesh, &best_manifold );
1966          new_polys = 1;
1967       }
1968
1969       if( new_polys >= 3 )
1970       {
1971          if( !cxr_build_implicit_geo( pullmesh, new_polys, pullmesh_new_start ))
1972          {
1973             free(solid_buffer);
1974             free(candidates);
1975             free(best_manifold.loops);
1976
1977             cxr_free_mesh( pullmesh );
1978             *err = k_soliderr_degenerate_implicit;
1979             return NULL;
1980          }
1981       }
1982
1983       /*
1984        * Copy faces from the pullmesh into original, to patch up where there
1985        * would be gaps created
1986        */
1987       for( int i=0; i<new_polys; i++ )
1988       {
1989          int rface_id = mesh->abpolys.count;
1990          cxr_polygon *pface = &pullmesh->polys[pullmesh_new_start+i],
1991                   *rip_face = cxr_ab_empty(&mesh->abpolys);
1992
1993          rip_face->loop_start = mesh->abloops.count;
1994          rip_face->loop_total = pface->loop_total;
1995          rip_face->material_id = -1;
1996
1997          for( int j=0; j<rip_face->loop_total; j++ )
1998          {
1999             cxr_loop *ploop =
2000                &pullmesh->loops[ pface->loop_start+pface->loop_total-j-1 ],
2001                *rloop = cxr_ab_empty(&mesh->abloops);
2002
2003             rloop->index = ploop->index;
2004             rloop->poly_left = rface_id;
2005             rloop->poly_right = -1;
2006             rloop->edge_index = 0;
2007             v2_copy( ploop->uv, rloop->uv );
2008          }
2009
2010          v3_copy( pface->center, rip_face->center );
2011          v3_negate( pface->normal, rip_face->normal );
2012       }
2013
2014       cxr_mesh_update( mesh );
2015       cxr_mesh_update( pullmesh );
2016
2017       cxr_mesh_clean_faces( mesh );
2018       cxr_mesh_clean_edges( mesh );
2019       cxr_mesh_clean_faces( pullmesh );
2020       cxr_mesh_clean_edges( pullmesh );
2021
2022       free(solid_buffer);
2023       free(candidates);
2024       free(best_manifold.loops);
2025
2026       /*
2027        * Do final checks on the mesh to make sure we diddn't introduce any
2028        * errors
2029        */
2030       if( cxr_non_manifold_err( pullmesh ) || cxr_reflex_err( pullmesh ) )
2031       {
2032          *err = k_soliderr_bad_result;
2033          return NULL;
2034       }
2035
2036       return pullmesh;
2037    }
2038
2039    free(solid_buffer);
2040    free(candidates);
2041    free(best_manifold.loops);
2042
2043    if( cxr_non_manifold_err( mesh ) || cxr_reflex_err( mesh ) )
2044       *err = k_soliderr_bad_result;
2045
2046    return NULL;
2047 }
2048
2049 /*
2050  * Convert from the format we recieve from blender into our internal format
2051  * with auto buffers.
2052  */
2053 static cxr_mesh *cxr_to_internal_format(
2054    cxr_static_mesh *src,
2055    cxr_abuffer *abverts
2056 ){
2057    cxr_mesh *mesh = cxr_alloc_mesh( src->edge_count, src->loop_count,
2058                                     src->poly_count, abverts );
2059
2060    cxr_ab_init( abverts, sizeof(v3f), src->vertex_count );
2061
2062    memcpy( mesh->abedges.arr, src->edges, src->edge_count*sizeof(cxr_edge));
2063    memcpy( mesh->abpolys.arr, src->polys, src->poly_count*sizeof(cxr_polygon));
2064    memcpy( abverts->arr, src->vertices, src->vertex_count*sizeof(v3f));
2065    mesh->abedges.count = src->edge_count;
2066    mesh->abloops.count = src->loop_count;
2067    mesh->abpolys.count = src->poly_count;
2068
2069    cxr_mesh_update( mesh );
2070
2071    for( int i=0; i<src->loop_count; i++ )
2072    {
2073       cxr_loop *lp = &mesh->loops[i];
2074
2075       lp->index = src->loops[i].index;
2076       lp->edge_index = src->loops[i].edge_index;
2077       v2_copy( src->loops[i].uv, lp->uv );
2078    }
2079
2080    abverts->count = src->vertex_count;
2081    return mesh;
2082 }
2083
2084 static int cxr_poly_convex( cxr_mesh *mesh, cxr_polygon *poly )
2085 {
2086    v3f *verts = cxr_ab_ptr( mesh->p_abverts, 0 );
2087
2088    for( int i=0; i<poly->loop_total; i++ )
2089    {
2090       int li0 = poly->loop_start + i,
2091           li1 = poly->loop_start + cxr_range( i+1, poly->loop_total ),
2092           li2 = poly->loop_start + cxr_range( i+2, poly->loop_total );
2093       int i0 = mesh->loops[li0].index,
2094           i1 = mesh->loops[li1].index,
2095           i2 = mesh->loops[li2].index;
2096
2097       v3f v0, v1, c;
2098
2099       v3_sub( verts[i1], verts[i0], v0 );
2100       v3_sub( verts[i2], verts[i1], v1 );
2101
2102       v3_cross( v0, v1, c );
2103       if( v3_dot( c, poly->normal ) <= 0.0 )
2104       {
2105 #if CXR_DEBUG
2106          cxr_debug_line( verts[i0], verts[i1], colour_error );
2107          cxr_debug_box( verts[i1], 0.1, colour_error );
2108          cxr_debug_line( verts[i1], verts[i2], colour_error );
2109          cxr_debug_line( verts[i1], poly->center, colour_error );
2110 #endif
2111          return 0;
2112       }
2113    }
2114
2115    return 1;
2116 }
2117
2118 static int cxr_solid_checkerr( cxr_mesh *mesh )
2119 {
2120    v3f *verts = cxr_ab_ptr( mesh->p_abverts, 0 );
2121    int err_count = 0;
2122
2123    for( int i=0; i<mesh->abpolys.count; i++ )
2124    {
2125       int plane_err = 0;
2126
2127       cxr_polygon *poly = &mesh->polys[i];
2128       v4f plane;
2129
2130       normal_to_plane( poly->normal, poly->center, plane );
2131
2132       for( int j=0; j<poly->loop_total; j++ )
2133       {
2134          cxr_loop *loop = &mesh->loops[ poly->loop_start+j ];
2135          double *vert = verts[ loop->index ];
2136
2137          if( fabs(plane_polarity(plane,vert)) > 0.0025 )
2138          {
2139             err_count ++;
2140             plane_err ++;
2141
2142             v3f ref;
2143             plane_project_point( plane, vert, ref );
2144
2145 #ifdef CXR_DEBUG
2146             cxr_debug_line( ref, vert, colour_error );
2147             cxr_debug_box( vert, 0.1, colour_error );
2148 #endif
2149          }
2150       }
2151
2152 #ifdef CXR_DEBUG
2153       if( plane_err )
2154          cxr_debug_poly( mesh, poly, colour_error );
2155 #endif
2156    }
2157
2158    return err_count;
2159 }
2160
2161 CXR_API void cxr_free_world( cxr_world *world )
2162 {
2163    for( int i=0; i<world->absolids.count; i++ )
2164    {
2165       cxr_solid *solid = cxr_ab_ptr( &world->absolids, i );
2166       cxr_free_mesh( solid->pmesh );
2167    }
2168
2169    cxr_ab_free( &world->abverts );
2170    cxr_ab_free( &world->absolids );
2171
2172    if( world->materials )
2173    {
2174       for( int i=0; i<world->material_count; i++ )
2175          free( world->materials[i].name );
2176
2177       free( world->materials );
2178    }
2179    free( world );
2180 }
2181
2182 CXR_API cxr_tri_mesh *cxr_world_preview( cxr_world *world )
2183 {
2184    cxr_tri_mesh *out = malloc( sizeof(cxr_tri_mesh) );
2185    out->vertex_count = 0;
2186    out->indices_count = 0;
2187
2188    for( int i=0; i<world->absolids.count; i++ )
2189    {
2190       cxr_solid *solid = cxr_ab_ptr( &world->absolids, i );
2191       cxr_mesh *mesh = solid->pmesh;
2192
2193       for( int j=0; j<mesh->abpolys.count; j ++ )
2194       {
2195          cxr_polygon *poly = &mesh->polys[j];
2196
2197          out->vertex_count += poly->loop_total * 3; /* Polygon, edge strip */
2198          out->indices_count += (poly->loop_total -2) * 3;   /* Polygon */
2199          out->indices_count += poly->loop_total * 2 * 3;    /* Edge strip */
2200       }
2201    }
2202
2203    out->colours = malloc( sizeof(v4f)*out->vertex_count );
2204    out->vertices = malloc( sizeof(v3f)*out->vertex_count );
2205    out->indices = malloc( sizeof(i32)*out->indices_count );
2206
2207    v3f *overts = out->vertices;
2208    v4f *colours = out->colours;
2209    i32 *indices = out->indices;
2210
2211    int vi = 0,
2212        ii = 0;
2213
2214    for( int i=0; i<world->absolids.count; i++ )
2215    {
2216       cxr_solid *solid = cxr_ab_ptr( &world->absolids, i );
2217       cxr_mesh *mesh = solid->pmesh;
2218
2219       v3f *verts = cxr_ab_ptr( mesh->p_abverts, 0 );
2220       v4f colour;
2221
2222       colour_random_brush( i, colour );
2223
2224       for( int j=0; j<mesh->abpolys.count; j ++ )
2225       {
2226          cxr_polygon *poly = &mesh->polys[j];
2227
2228          int istart = vi;
2229
2230          for( int k=0; k<poly->loop_total-2; k++ )
2231          {
2232             int i0 = 0,
2233                 i1 = (k+1)*3,
2234                 i2 = (k+2)*3;
2235
2236             indices[ ii ++ ] = istart+i0;
2237             indices[ ii ++ ] = istart+i1;
2238             indices[ ii ++ ] = istart+i2;
2239          }
2240
2241          for( int k=0; k<poly->loop_total; k++ )
2242          {
2243             cxr_loop *lp = &mesh->loops[poly->loop_start+k];
2244
2245             int i0r = k*3+1,
2246                 i1r = cxr_range(k+1,poly->loop_total)*3+1,
2247                 i0i = k*3+2,
2248                 i1i = cxr_range(k+1,poly->loop_total)*3+2;
2249
2250             indices[ ii ++ ] = istart+i0i;
2251             indices[ ii ++ ] = istart+i1i;
2252             indices[ ii ++ ] = istart+i1r;
2253
2254             indices[ ii ++ ] = istart+i0i;
2255             indices[ ii ++ ] = istart+i1r;
2256             indices[ ii ++ ] = istart+i0r;
2257
2258             /* Main */
2259             v3_muladds( verts[lp->index], poly->normal, 0.02, overts[vi] );
2260             v4_copy( colour, colours[ vi ] );
2261             vi ++;
2262
2263             /* Trim */
2264             v3f inner;
2265             v3_lerp( verts[lp->index], poly->center, 0.2, inner );
2266             v3_muladds( inner, poly->normal, 0.015, overts[ vi ] );
2267             v4_copy( colour, colours[ vi ] );
2268             v4_copy( (v4f){ 0.0, 0.0, 0.0, 0.0 }, colours[vi] );
2269             vi ++;
2270
2271             v3_muladds(verts[lp->index], poly->normal, 0.0, overts[ vi ] );
2272             v4_copy( colour, colours[ vi ] );
2273             v4_copy( (v4f){ 1.0, 1.0, 1.0, 0.125 }, colours[vi] );
2274             vi ++;
2275          }
2276       }
2277    }
2278
2279    return out;
2280 }
2281
2282 CXR_API void cxr_free_tri_mesh( cxr_tri_mesh *mesh )
2283 {
2284    free( mesh->colours );
2285    free( mesh->indices );
2286    free( mesh->vertices );
2287    free( mesh );
2288 }
2289
2290 CXR_API cxr_world *cxr_decompose( cxr_static_mesh *src, i32 *perrcode )
2291 {
2292    /* Make sure data is in the mesh and isn't empty */
2293    if( !src->edge_count || !src->loop_count || !src->poly_count )
2294    {
2295       cxr_log( "Error %d\n", k_soliderr_invalid_input );
2296       if( perrcode )
2297          *perrcode = k_soliderr_invalid_input;
2298
2299       return NULL;
2300    }
2301
2302    u32 error = 0x00;
2303    cxr_world *world = malloc( sizeof(*world) );
2304
2305    /* Copy data to internal formats */
2306    cxr_mesh *main_mesh = cxr_to_internal_format( src, &world->abverts );
2307    cxr_ab_init( &world->absolids, sizeof(cxr_solid), 2 );
2308
2309    if( src->material_count )
2310    {
2311       size_t dsize = sizeof(cxr_material) * src->material_count;
2312       world->materials = malloc( dsize );
2313       memcpy( world->materials, src->materials, dsize );
2314
2315       for( int i=0; i<src->material_count; i++ )
2316       {
2317          world->materials[i].name = malloc(strlen(src->materials[i].name) +1);
2318          strcpy( world->materials[i].name, src->materials[i].name );
2319       }
2320       world->material_count = src->material_count;
2321    }
2322    else world->materials = NULL;
2323
2324    int invalid_count = 0;
2325
2326    /*
2327     * Preprocessor 1: Island seperation
2328     */
2329    while(1)
2330    {
2331       cxr_mesh *res = cxr_pull_island( main_mesh );
2332       if( res )
2333       {
2334          cxr_ab_push( &world->absolids, &(cxr_solid){ res, 0, 0 });
2335       }
2336       else break;
2337    }
2338    cxr_ab_push( &world->absolids, &(cxr_solid){ main_mesh, 0, 0 } );
2339
2340    /*
2341     * Preprocessor 2: Displacement processing & error checks
2342     */
2343    for( int i=0; i<world->absolids.count; i++ )
2344    {
2345       cxr_solid *pinf = cxr_ab_ptr(&world->absolids,i);
2346
2347       for( int j=0; j<pinf->pmesh->abpolys.count; j++ )
2348       {
2349          cxr_polygon *poly = &pinf->pmesh->polys[ j ];
2350
2351          for( int k=0; k<poly->loop_total; k++ )
2352          {
2353             cxr_loop *lp = &pinf->pmesh->loops[ poly->loop_start+k ];
2354             cxr_edge *edge = &pinf->pmesh->edges[ lp->edge_index ];
2355
2356             if( edge->freestyle )
2357                goto displacement;
2358          }
2359
2360          if( !cxr_poly_convex( pinf->pmesh, poly ) )
2361          {
2362             pinf->invalid = 1;
2363             invalid_count ++;
2364             error = k_soliderr_non_convex_poly;
2365          }
2366       }
2367
2368       if( cxr_solid_checkerr( pinf->pmesh ) )
2369       {
2370          pinf->invalid = 1;
2371          invalid_count ++;
2372          error = k_soliderr_non_coplanar_vertices;
2373       }
2374
2375       continue;
2376
2377    displacement:
2378       pinf->displacement = 1;
2379    }
2380
2381    /*
2382     * Main convex decomp algorithm
2383     */
2384    int sources_count = world->absolids.count;
2385
2386    if( invalid_count )
2387       goto decomp_failed;
2388
2389    for( int i=0; i<sources_count; i++ )
2390    {
2391       cxr_solid pinf = *(cxr_solid *)cxr_ab_ptr(&world->absolids, i);
2392
2393       if( pinf.displacement || pinf.invalid )
2394          continue;
2395
2396       while(1)
2397       {
2398          cxr_mesh *res = cxr_pull_best_solid( pinf.pmesh, 0, &error );
2399
2400          if( res )
2401          {
2402             cxr_ab_push( &world->absolids, &(cxr_solid){ res, 0, 0 } );
2403          }
2404          else
2405          {
2406             if( error == k_soliderr_no_solids )
2407             {
2408                /* Retry if non-critical error, with extra edges */
2409                res = cxr_pull_best_solid(pinf.pmesh, 1, &error);
2410
2411                if( res )
2412                   cxr_ab_push( &world->absolids, &(cxr_solid){ res, 0, 0 } );
2413                else
2414                   goto decomp_failed;
2415             }
2416             else
2417                if( error )
2418                   goto decomp_failed;
2419                else
2420                   break;
2421          }
2422       }
2423    }
2424
2425    return world;
2426
2427 decomp_failed:
2428    cxr_log( "Error %d\n", error );
2429    cxr_free_world( world );
2430
2431    if( perrcode )
2432       *perrcode = error;
2433
2434    return NULL;
2435 }
2436
2437 /*
2438  *  format specific functions: vdf, vmf, (v)bsp
2439  *  ----------------------------------------------------------------------------
2440  */
2441 #ifdef CXR_VALVE_MAP_FILE
2442
2443 CXR_API cxr_vdf *cxr_vdf_open(const char *path)
2444 {
2445    cxr_vdf *vdf = malloc(sizeof(cxr_vdf));
2446
2447    vdf->level = 0;
2448    vdf->fp = fopen( path, "w" );
2449
2450    if( !vdf->fp )
2451    {
2452       free( vdf );
2453       return NULL;
2454    }
2455
2456    return vdf;
2457 }
2458
2459 CXR_API void cxr_vdf_close(cxr_vdf *vdf)
2460 {
2461    fclose( vdf->fp );
2462    free( vdf );
2463 }
2464
2465 CXR_API void cxr_vdf_put(cxr_vdf *vdf, const char *str)
2466 {
2467    for( int i=0; i<vdf->level; i++ )
2468       fputs( " ", vdf->fp );
2469
2470    fputs( str, vdf->fp );
2471 }
2472
2473 static void cxr_vdf_printf( cxr_vdf *vdf, const char *fmt, ... )
2474 {
2475    cxr_vdf_put(vdf,"");
2476
2477    va_list args;
2478    va_start( args, fmt );
2479    vfprintf( vdf->fp, fmt, args );
2480    va_end(args);
2481 }
2482
2483 CXR_API void cxr_vdf_node(cxr_vdf *vdf, const char *str)
2484 {
2485    cxr_vdf_put( vdf, str );
2486    putc( (u8)'\n', vdf->fp );
2487    cxr_vdf_put( vdf, "{\n" );
2488
2489    vdf->level ++;
2490 }
2491
2492 CXR_API void cxr_vdf_edon( cxr_vdf *vdf )
2493 {
2494    vdf->level --;
2495    cxr_vdf_put( vdf, "}\n" );
2496 }
2497
2498 CXR_API void cxr_vdf_kv( cxr_vdf *vdf, const char *strk, const char *strv )
2499 {
2500    cxr_vdf_printf( vdf, "\"%s\" \"%s\"\n", strk, strv );
2501 }
2502
2503 /*
2504  * Data-type specific Keyvalues
2505  */
2506 static void cxr_vdf_ki32( cxr_vdf *vdf, const char *strk, i32 val )
2507 {
2508    cxr_vdf_printf( vdf, "\"%s\" \"%d\"\n", strk, val );
2509 }
2510
2511 static void cxr_vdf_kdouble( cxr_vdf *vdf, const char *strk, double val )
2512 {
2513    cxr_vdf_printf( vdf, "\"%s\" \"%f\"\n", strk, val );
2514 }
2515
2516 static void cxr_vdf_kaxis( cxr_vdf *vdf, const char *strk,
2517       v3f normal, double offset, double scale
2518 ){
2519    cxr_vdf_printf( vdf, "\"%s\" \"[%f %f %f %f] %f\"\n",
2520          strk, normal[0], normal[1],normal[2], offset, scale );
2521 }
2522
2523 static void cxr_vdf_kv3f( cxr_vdf *vdf, const char *strk, v3f v )
2524 {
2525    cxr_vdf_printf( vdf, "\"%s\" \"[%f %f %f]\"\n", strk, v[0], v[1], v[2] );
2526 }
2527
2528 static void cxr_vdf_karrdouble( cxr_vdf *vdf, const char *strk,
2529       int id, double *doubles, int count
2530 ){
2531    cxr_vdf_put(vdf,"");
2532    fprintf( vdf->fp, "\"%s%d\" \"", strk, id );
2533    for( int i=0; i<count; i++ )
2534    {
2535       if( i == count-1 ) fprintf( vdf->fp, "%f", doubles[i] );
2536       else fprintf( vdf->fp, "%f ", doubles[i] );
2537    }
2538    fprintf( vdf->fp, "\"\n" );
2539 }
2540
2541 static void cxr_vdf_karrv3f( cxr_vdf *vdf, const char *strk,
2542       int id, v3f *vecs, int count
2543 ){
2544    cxr_vdf_put(vdf,"");
2545    fprintf( vdf->fp, "\"%s%d\" \"", strk, id );
2546    for( int i=0; i<count; i++ )
2547    {
2548       const char *format = i == count-1? "%f %f %f": "%f %f %f ";
2549       fprintf( vdf->fp, format, vecs[i][0], vecs[i][1], vecs[i][2] );
2550    }
2551    fprintf( vdf->fp, "\"\n" );
2552 }
2553
2554 static void cxr_vdf_plane( cxr_vdf *vdf, const char *strk, v3f a, v3f b, v3f c )
2555 {
2556    cxr_vdf_printf( vdf, "\"%s\" \"(%f %f %f) (%f %f %f) (%f %f %f)\"\n",
2557          strk, a[0], a[1], a[2], b[0], b[1], b[2], c[0], c[1], c[2] );
2558 }
2559
2560 static void cxr_vdf_colour255(cxr_vdf *vdf, const char *strk, v4f colour)
2561 {
2562    v4f scale;
2563    v4_muls( colour, 255.0, scale );
2564    cxr_vdf_printf( vdf, "\"%s\" \"%d %d %d %d\"\n",
2565          strk,(int)scale[0], (int)scale[1], (int)scale[2], (int)scale[3]);
2566 }
2567
2568 static struct cxr_material cxr_nodraw =
2569 {
2570    .res = { 512, 512 },
2571    .name = "tools/toolsnodraw"
2572 };
2573
2574 /*
2575  * Find most extreme point along a given direction
2576  */
2577 static double support_distance( v3f verts[3], v3f dir, double coef )
2578 {
2579    return cxr_maxf
2580    (
2581       coef * v3_dot( verts[0], dir ),
2582       cxr_maxf
2583       (
2584          coef * v3_dot( verts[1], dir ),
2585          coef * v3_dot( verts[2], dir )
2586       )
2587    );
2588 }
2589
2590 /*
2591  * Convert regular UV'd triangle int Source's u/vaxis vectors
2592  *
2593  * This supports affine move, scale, rotation, parallel skewing
2594  */
2595 static void cxr_calculate_axis( cxr_texinfo *transform, v3f verts[3],
2596    v2f uvs[3], v2f texture_res
2597 ){
2598    v2f tT, bT; /* Tangent/bitangent pairs for UV space and world */
2599    v3f tW, bW;
2600
2601    v2_sub( uvs[0], uvs[1], tT );
2602    v2_sub( uvs[2], uvs[1], bT );
2603    v3_sub( verts[0], verts[1], tW );
2604    v3_sub( verts[2], verts[1], bW );
2605
2606    /* Use arbitrary projection if there is no UV */
2607    if( v2_length( tT ) < 0.0001 || v2_length( bT ) < 0.0001 )
2608    {
2609       v3f uaxis, normal, vaxis;
2610
2611       v3_copy( tW, uaxis );
2612       v3_normalize( uaxis );
2613
2614       v3_cross( tW, bW, normal );
2615       v3_cross( normal, uaxis, vaxis );
2616       v3_normalize( vaxis );
2617
2618       v3_copy( uaxis, transform->uaxis );
2619       v3_copy( vaxis, transform->vaxis );
2620       v2_zero( transform->offset );
2621
2622       v2_div( (v2f){128.0, 128.0}, texture_res, transform->scale );
2623       transform->winding = 1.0;
2624       return;
2625    }
2626
2627    /* Detect if UV is reversed */
2628    double winding = v2_cross( tT, bT ) >= 0.0f? 1.0f: -1.0f;
2629
2630    /* UV projection reference */
2631    v2f vY, vX;
2632    v2_muls((v2f){1,0}, winding, vX);
2633    v2_muls((v2f){0,1}, winding, vY);
2634
2635    /* Reproject reference into world space, including skew */
2636    v3f uaxis1, vaxis1;
2637
2638    v3_muls( tW, v2_cross(vX,bT) / v2_cross(bT,tT), uaxis1 );
2639    v3_muladds( uaxis1, bW, v2_cross(vX, tT) / v2_cross(tT,bT), uaxis1 );
2640
2641    v3_muls( tW, v2_cross(vY,bT) / v2_cross(bT,tT), vaxis1 );
2642    v3_muladds( vaxis1, bW, v2_cross(vY,tT) / v2_cross(tT,bT), vaxis1 );
2643
2644    v3_normalize( uaxis1 );
2645    v3_normalize( vaxis1 );
2646
2647    /* Apply source transform to axis (yes, they also need to be swapped) */
2648    v3f norm, uaxis, vaxis;
2649
2650    v3_cross( bW, tW, norm );
2651    v3_normalize(norm);
2652    v3_cross( vaxis1, norm, uaxis );
2653    v3_cross( uaxis1, norm, vaxis );
2654
2655    /* real UV scale */
2656    v2f uvmin, uvmax, uvdelta;
2657    v2_minv( uvs[0], uvs[1], uvmin );
2658    v2_minv( uvmin, uvs[2], uvmin );
2659    v2_maxv( uvs[0], uvs[1], uvmax );
2660    v2_maxv( uvmax, uvs[2], uvmax );
2661
2662    v2_sub( uvmax, uvmin, uvdelta );
2663
2664    /* world-uv scale */
2665    v2f uvminw, uvmaxw, uvdeltaw;
2666    uvminw[0] = -support_distance( verts, uaxis, -1.0f );
2667    uvmaxw[0] =  support_distance( verts, uaxis,  1.0f );
2668    uvminw[1] = -support_distance( verts, vaxis, -1.0f );
2669    uvmaxw[1] =  support_distance( verts, vaxis,  1.0f );
2670
2671    v2_sub( uvmaxw, uvminw, uvdeltaw );
2672
2673    /* VMf uv scale */
2674    v2f uv_scale;
2675    v2_div( uvdeltaw, uvdelta, uv_scale );
2676    v2_div( uv_scale, texture_res, uv_scale );
2677
2678    /* Find offset via 'natural' point */
2679    v2f target_uv, natural_uv, tex_offset;
2680    v2_mul( uvs[0], texture_res, target_uv );
2681
2682    natural_uv[0] =  v3_dot( uaxis, verts[0] );
2683    natural_uv[1] = -v3_dot( vaxis, verts[0] );
2684    v2_div( natural_uv, uv_scale, natural_uv );
2685
2686    tex_offset[0] =   target_uv[0]-natural_uv[0];
2687    tex_offset[1] = -(target_uv[1]-natural_uv[1]);
2688
2689    /* Copy everything into output */
2690    v3_copy( uaxis, transform->uaxis );
2691    v3_copy( vaxis, transform->vaxis );
2692    v2_copy( tex_offset, transform->offset );
2693    v2_copy( uv_scale, transform->scale );
2694    transform->winding = winding;
2695 }
2696
2697 /*
2698  * Get the maximal direction of a vector, while also ignoring an axis
2699  * specified
2700  */
2701 static int cxr_cardinal( v3f a, int ignore )
2702 {
2703    int component = 0;
2704    double component_max = -CXR_BIG_NUMBER;
2705
2706    for( int i=0; i<3; i++ )
2707    {
2708       if( i == ignore ) continue;
2709
2710       if( fabs(a[i]) > component_max )
2711       {
2712          component_max = fabs(a[i]);
2713          component = i;
2714       }
2715    }
2716    double d = a[component] >= 0.0? 1.0: -1.0;
2717    v3_zero( a );
2718    a[component] = d;
2719
2720    return component;
2721 }
2722
2723 /*
2724  * Convert contiguous mesh to displacement patch
2725  */
2726 static int cxr_write_disp( cxr_mesh *mesh, cxr_world *world,
2727       cxr_vmf_context *ctx, cxr_vdf *output
2728 ){
2729    v3f *verts = cxr_ab_ptr( mesh->p_abverts, 0 );
2730
2731    struct vertinfo
2732    {
2733       int con_start, con_count;
2734       int boundary,
2735           used,
2736           search,
2737           corner;
2738
2739       double alpha;
2740    }
2741    *vertinfo = malloc( sizeof(struct vertinfo)*mesh->p_abverts->count );
2742    int *graph = malloc( sizeof(int) * mesh->abedges.count*2 );
2743
2744    int con_pos = 0;
2745    for( int i=0; i<mesh->p_abverts->count; i++ )
2746    {
2747       struct vertinfo *info = &vertinfo[i];
2748       info->con_start = con_pos;
2749       info->con_count = 0;
2750       info->boundary = 0;
2751       info->corner = 0;
2752       info->used = 0;
2753       info->search = 0;
2754       info->alpha = 0.0;
2755
2756       for( int j=0; j<mesh->abedges.count; j++ )
2757       {
2758          cxr_edge *edge = &mesh->edges[j];
2759
2760          if( edge->i0 == i || edge->i1 == i )
2761          {
2762             graph[ con_pos ++ ] = edge->i0 == i? edge->i1: edge->i0;
2763             info->con_count ++;
2764
2765             if( edge->freestyle )
2766                info->boundary = 1;
2767          }
2768       }
2769    }
2770
2771    v3f  refv, refu, refn;
2772    v3_zero(refv); v3_zero(refu); v3_zero(refn);
2773
2774    /*
2775     * Approximately match the area of the result brush faces to the actual
2776     * area.
2777     *
2778     * Necessary for accuracy and even lightmap texel allocation
2779     */
2780
2781    double uv_area = 0.0, face_area = 0.0, sf;
2782    v2f uvboundmin, uvboundmax;
2783    v3f faceboundmin, faceboundmax;
2784    v2f uv_center;
2785    v3f face_center;
2786
2787    v2_fill( uvboundmin,  CXR_BIG_NUMBER );
2788    v2_fill( uvboundmax, -CXR_BIG_NUMBER );
2789    v3_fill( faceboundmin,  CXR_BIG_NUMBER );
2790    v3_fill( faceboundmax, -CXR_BIG_NUMBER );
2791
2792    for( int i=0; i<mesh->abpolys.count; i++ )
2793    {
2794       cxr_polygon *poly = &mesh->polys[i];
2795
2796       for( int j=0; j<poly->loop_total; j++ )
2797       {
2798          cxr_loop *lp0 = &mesh->loops[ poly->loop_start+j ];
2799          v2_minv( lp0->uv, uvboundmin, uvboundmin);
2800          v2_maxv( lp0->uv, uvboundmax, uvboundmax);
2801          v3_minv( verts[lp0->index], faceboundmin, faceboundmin );
2802          v3_maxv( verts[lp0->index], faceboundmax, faceboundmax );
2803       }
2804
2805       for( int j=0; j<poly->loop_total-2; j++ )
2806       {
2807          cxr_loop *lp0 = &mesh->loops[poly->loop_start],
2808                   *lp1 = &mesh->loops[poly->loop_start+j+1],
2809                   *lp2 = &mesh->loops[poly->loop_start+j+2];
2810
2811          v3f va, vb, orth;
2812          v3_sub( verts[lp1->index], verts[lp0->index], va );
2813          v3_sub( verts[lp2->index], verts[lp0->index], vb );
2814          v3_cross( va, vb, orth );
2815
2816          face_area += v3_length( orth ) / 2.0;
2817
2818          v2f uva, uvb;
2819          v2_sub( lp1->uv, lp0->uv, uva );
2820          v2_sub( lp2->uv, lp0->uv, uvb );
2821
2822          uv_area += fabs(v2_cross( uva, uvb )) / 2.0;
2823       }
2824    }
2825
2826    v3_add( faceboundmax, faceboundmin, face_center );
2827    v3_muls( face_center, 0.5, face_center );
2828    v2_add( uvboundmin, uvboundmax, uv_center );
2829    v2_muls( uv_center, 0.5, uv_center );
2830
2831    sf = sqrt( face_area / uv_area );
2832    int corner_count = 0;
2833
2834    /*
2835     * Vertex classification
2836     *   boundary vertices:   they exist on a freestyle edge
2837     *   corners:             only connected to other boundaries
2838     */
2839    for( int i=0; i<mesh->p_abverts->count; i++ )
2840    {
2841       struct vertinfo *info = &vertinfo[i];
2842       if( !info->boundary ) continue;
2843
2844       int count = 0,
2845           non_manifold = 1;
2846
2847       for( int j=0; j<info->con_count; j++ )
2848       {
2849          int con = graph[info->con_start+j];
2850
2851          if( vertinfo[con].boundary )
2852             count ++;
2853          else
2854             non_manifold = 0;
2855       }
2856
2857       if( count > 2 || non_manifold )
2858       {
2859          info->corner = 1;
2860          corner_count ++;
2861       }
2862    }
2863
2864    /*
2865     * TODO(harry): This currently only supports power 2 displacements
2866     *              its quite straightforward to upgrade it.
2867     *
2868     * TODO(harry): Error checking is needed here for bad input data
2869     */
2870
2871    int dispedge[17];
2872    v2f corner_uvs[4];
2873    int dispedge_count;
2874    int disp_count = 0;
2875
2876    for( int i=0; i<mesh->abpolys.count; i++ )
2877    {
2878       cxr_polygon *basepoly = &mesh->polys[i];
2879
2880       for( int h=0; h<basepoly->loop_total; h ++ )
2881       {
2882          int i0 = h,
2883              i1 = cxr_range(h+1,basepoly->loop_total);
2884
2885          cxr_loop *l0 = &mesh->loops[ basepoly->loop_start+i0 ],
2886                   *l1 = &mesh->loops[ basepoly->loop_start+i1 ];
2887          struct vertinfo *info = &vertinfo[ l0->index ];
2888
2889          if( !info->corner )
2890             continue;
2891
2892          int corner_count = 1;
2893
2894          cxr_material *matptr =
2895             basepoly->material_id < 0 || !world->materials?
2896                &cxr_nodraw:
2897                &world->materials[ basepoly->material_id ];
2898
2899          dispedge_count = 2;
2900          dispedge[0] = l0->index;
2901          dispedge[1] = l1->index;
2902          v2_copy( l0->uv, corner_uvs[0] );
2903
2904          /* Consume (use) face from orignal mesh */
2905          basepoly->loop_total = -1;
2906
2907          while( dispedge_count < 17 )
2908          {
2909             struct vertinfo *edge_head =
2910                &vertinfo[dispedge[dispedge_count-1]];
2911
2912             int newvert = 0;
2913
2914             if( edge_head->corner )
2915             {
2916                /* Find polygon that has edge C-1 -> C */
2917                for( int j=0; j<mesh->abpolys.count && !newvert; j++ )
2918                {
2919                   cxr_polygon *poly = &mesh->polys[j];
2920
2921                   for( int k=0; k<poly->loop_total; k ++ )
2922                   {
2923                      int i0 = k,
2924                          i1 = cxr_range(k+1,poly->loop_total);
2925
2926                      cxr_loop *l0 = &mesh->loops[ poly->loop_start+i0 ],
2927                               *l1 = &mesh->loops[ poly->loop_start+i1 ];
2928
2929                      if( l0->index == dispedge[dispedge_count-2] &&
2930                          l1->index == dispedge[dispedge_count-1] )
2931                      {
2932                         /* Take the next edge */
2933                         v2_copy( l1->uv, corner_uvs[corner_count ++] );
2934
2935                         int i2 = cxr_range(i1+1,poly->loop_total);
2936                         cxr_loop *l2 = &mesh->loops[ poly->loop_start+i2 ];
2937
2938                         dispedge[dispedge_count ++] = l2->index;
2939                         newvert = 1;
2940                         poly->loop_total = -1;
2941                         break;
2942                      }
2943                   }
2944                }
2945             }
2946             else
2947             {
2948                for( int j=0; j<edge_head->con_count; j++ )
2949                {
2950                   int con = graph[edge_head->con_start+j];
2951
2952                   if( con == -1 )
2953                      continue;
2954
2955                   if( dispedge_count > 1 )
2956                      if( con == dispedge[dispedge_count-2] )
2957                         continue;
2958
2959                   struct vertinfo *coninfo = &vertinfo[con];
2960
2961                   if( !coninfo->boundary )
2962                      continue;
2963
2964                   dispedge[ dispedge_count ++ ] = con;
2965                   newvert = 1;
2966
2967                   break;
2968                }
2969             }
2970
2971             if( !newvert )
2972             {
2973                return 0;
2974             }
2975          }
2976
2977          /* All edges collected */
2978
2979          v2f va, vb;
2980          v2_sub( corner_uvs[1], corner_uvs[0], va );
2981          v2_sub( corner_uvs[2], corner_uvs[0], vb );
2982
2983          /* Connect up the grid
2984           *
2985           *   0 1 2 3 4
2986           *  15 a b c d
2987           *  14 e f g h
2988           *  13 i j k l
2989           *  12 m n o p
2990           *
2991           *  Example: a := common unused vertex that is connected to
2992           *                by 1 and 15. Or y-1, and x-1 on the grid.
2993           *           g := c and f common vert ^
2994           */
2995
2996          int grid[25];
2997
2998          for( int j=0; j<5; j++ ) grid[j] = dispedge[j];
2999          for( int j=1; j<5; j++ ) grid[j*5+4] = dispedge[j+4];
3000          for( int j=0; j<4; j++ ) grid[4*5+3-j] = dispedge[j+9];
3001          for( int j=1; j<4; j++ ) grid[j*5] = dispedge[16-j];
3002
3003          /* Fill in grid */
3004          for( int j=1; j<4; j++ )
3005          {
3006             for( int k=1; k<4; k++ )
3007             {
3008                int s0 = grid[(j-1)*5+k],
3009                    s1 = grid[j*5+k-1];
3010
3011                struct vertinfo *va = &vertinfo[s0],
3012                                *vb = &vertinfo[s1];
3013
3014                /* Find common non-used vertex */
3015                for( int l=0; l<va->con_count; l ++ )
3016                {
3017                   for( int m=0; m<vb->con_count; m ++ )
3018                   {
3019                      int cona = graph[va->con_start+l],
3020                          conb = graph[vb->con_start+m];
3021
3022                      if( cona == conb )
3023                      {
3024                         if( vertinfo[cona].used || vertinfo[cona].boundary )
3025                            continue;
3026
3027                         grid[ j*5+k ] = cona;
3028                         vertinfo[cona].used = 1;
3029
3030                         goto next_cell;
3031                      }
3032                   }
3033                }
3034
3035 #ifdef CXR_DEBUG
3036                cxr_log( "Broken displacement!\n" );
3037 #endif
3038                free( graph );
3039                free( vertinfo );
3040                return 0;
3041
3042                next_cell:;
3043             }
3044          }
3045
3046          /*
3047          * Create V reference based on first displacement.
3048          * TODO(harry): This is not the moststable selection method!
3049          *       faces can come in any order, so the first disp will of
3050          *       course always vary. Additionaly the triangle can be oriented
3051          *       differently.
3052          *
3053          *       Improvement can be made by selecting a first disp/triangle
3054          *       based on deterministic factors.
3055          */
3056          if( disp_count == 0 )
3057          {
3058             cxr_texinfo tx;
3059             v3f tri_ref[3];
3060             v3_copy( verts[dispedge[0]], tri_ref[0] );
3061             v3_copy( verts[dispedge[4]], tri_ref[1] );
3062             v3_copy( verts[dispedge[8]], tri_ref[2] );
3063             cxr_calculate_axis( &tx, tri_ref, corner_uvs, (v2f){512,512} );
3064
3065             v3_muls( tx.vaxis, -1.0, refv );
3066             int v_cardinal = cxr_cardinal( refv, -1 );
3067
3068             v3_cross( tx.vaxis, tx.uaxis, refn );
3069             v3_muls( refn, -tx.winding, refn );
3070
3071             /* Computing new reference vectors */
3072             int n1_cardinal = cxr_cardinal( refn, v_cardinal );
3073
3074             int u_cardinal = 0;
3075
3076             for( int j=0; j<2; j++ )
3077                if( u_cardinal == n1_cardinal || u_cardinal == v_cardinal )
3078                   u_cardinal ++;
3079
3080             v3_zero(refu);
3081             refu[u_cardinal] = tx.uaxis[u_cardinal] > 0.0? 1.0: -1.0;
3082
3083             v3f p0, pv, pu, pn;
3084
3085             v3_copy( face_center, p0 );
3086             v3_muladds( face_center, refn, 1.5, pn );
3087             v3_muladds( face_center, refv, 1.5, pv );
3088             v3_muladds( face_center, refu, 1.5, pu );
3089
3090             v3_muladds( face_center, refn, 2.0, face_center );
3091          }
3092
3093          /* Create world coordinates */
3094          v3f world_corners[8];
3095          v2f world_uv[4];
3096
3097          for( int j=0; j<4; j++ )
3098          {
3099             v2f local_uv;
3100             v2_sub( corner_uvs[j], uv_center, local_uv );
3101             v2_copy( corner_uvs[j], world_uv[j] );
3102             v2_muls( local_uv, sf, local_uv );
3103
3104             v3_muls( refu, local_uv[0], world_corners[j] );
3105             v3_muladds( world_corners[j],refv,local_uv[1],world_corners[j] );
3106             v3_add( face_center, world_corners[j], world_corners[j] );
3107          }
3108
3109          double *colour = colours_random[cxr_range(disp_count,8)];
3110
3111          for( int j=0; j<4; j++ )
3112             v3_muladds( world_corners[j], refn, -1.0, world_corners[j+4] );
3113
3114          /* Apply world transform */
3115          for( int j=0; j<8; j++ )
3116          {
3117             double *p0 = world_corners[j];
3118             v3_muls( p0, ctx->scale, p0 );
3119             v3_add( p0, ctx->offset, p0 );
3120          }
3121
3122          cxr_texinfo texinfo_shared;
3123          cxr_calculate_axis( &texinfo_shared, world_corners, world_uv,
3124             (v2f){ matptr->res[0], matptr->res[1] } );
3125
3126          /* Write brush */
3127          cxr_vdf_node( output, "solid" );
3128          cxr_vdf_ki32( output, "id", ++ ctx->brush_count );
3129
3130          int sides[6][3] =
3131          {{ 0, 1, 2 },
3132           { 4, 6, 5 },
3133           { 4, 1, 0 },
3134           { 7, 0, 3 },
3135           { 6, 2, 1 },
3136           { 6, 3, 2 }};
3137
3138          v3f normals[25];
3139          double distances[25];
3140
3141          v3f lside0, lside1, lref, vdelta, vworld;
3142          double tx, ty;
3143
3144          for( int j=0; j<5; j++ )
3145          {
3146             ty = (double)j/(double)(5-1);
3147
3148             v3_lerp( world_corners[0], world_corners[3], ty, lside0 );
3149             v3_lerp( world_corners[1], world_corners[2], ty, lside1 );
3150
3151             for( int k=0; k<5; k++ )
3152             {
3153                int index = j*5+k;
3154
3155                tx = (double)k/(double)(5-1);
3156                v3_lerp( lside0, lside1, tx, lref );
3157                v3_muls( verts[grid[index]], ctx->scale, vworld );
3158                v3_add( ctx->offset, vworld, vworld );
3159
3160                v3_sub( vworld, lref, vdelta );
3161                v3_copy( vdelta, normals[index] );
3162                v3_normalize( normals[index] );
3163                distances[index] = v3_dot( vdelta, normals[index] );
3164             }
3165          }
3166
3167          for( int j=0; j<6; j++ )
3168          {
3169             int *side = sides[j];
3170
3171             cxr_vdf_node( output, "side" );
3172             cxr_vdf_ki32( output, "id", ++ ctx->face_count );
3173             cxr_vdf_plane( output, "plane", world_corners[side[2]],
3174                                             world_corners[side[1]],
3175                                             world_corners[side[0]] );
3176
3177             cxr_vdf_kv( output, "material", matptr->name );
3178             cxr_vdf_kaxis( output, "uaxis",
3179                   texinfo_shared.uaxis,
3180                   texinfo_shared.offset[0],
3181                   texinfo_shared.scale[0] );
3182             cxr_vdf_kaxis( output, "vaxis",
3183                   texinfo_shared.vaxis,
3184                   texinfo_shared.offset[1],
3185                   texinfo_shared.scale[1] );
3186
3187             cxr_vdf_kdouble( output, "rotation", 0.0 );
3188             cxr_vdf_ki32( output, "lightmapscale", ctx->lightmap_scale);
3189             cxr_vdf_ki32( output, "smoothing_groups", 0 );
3190
3191             if( j == 0 )
3192             {
3193                cxr_vdf_node( output, "dispinfo" );
3194                cxr_vdf_ki32( output, "power", 2 );
3195                cxr_vdf_kv3f( output, "startposition", world_corners[0] );
3196                cxr_vdf_ki32( output, "flags", 0 );
3197                cxr_vdf_kdouble( output, "elevation", 0.0 );
3198                cxr_vdf_ki32( output, "subdiv", 0 );
3199
3200                cxr_vdf_node( output, "normals" );
3201                for( int k=0; k<5; k++ )
3202                   cxr_vdf_karrv3f( output, "row", k, &normals[k*5], 5 );
3203                cxr_vdf_edon( output );
3204
3205                cxr_vdf_node( output, "distances" );
3206                for( int k=0; k<5; k++ )
3207                   cxr_vdf_karrdouble( output, "row", k, &distances[k*5], 5 );
3208                cxr_vdf_edon( output );
3209
3210                /*
3211                 * TODO: This might be needed for the compilers. Opens fine in
3212                 * hammer
3213                 */
3214
3215                /*
3216                cxr_vdf_node( output, "offsets" );
3217                for( int k=0; k<5; k++ )
3218                   cxr_vdf_printf( output,
3219                      "\"row%d\" \"0 0 0 0 0 0 0 0 0 0 0 0 0 0 0\"\n", k );
3220                cxr_vdf_edon( output );
3221
3222                cxr_vdf_node( output, "offset_normals" );
3223                for( int k=0; k<5; k++ )
3224                   cxr_vdf_printf( output,
3225                      "\"row%d\" \"0 0 1 0 0 1 0 0 1 0 0 1 0 0 1\"\n", k );
3226                cxr_vdf_edon( output );
3227
3228                cxr_vdf_node( output, "alphas" );
3229                for( int k=0; k<5; k++ )
3230                   cxr_vdf_printf( output, "\"row%d\" \"0 0 0 0 0\"\n", k );
3231                cxr_vdf_edon( output );
3232
3233                cxr_vdf_node( output, "triangle_tags" );
3234                for( int k=0; k<5-1; k++ )
3235                   cxr_vdf_printf( output,
3236                      "\"row%d\" \"9 9 9 9 9 9 9 9\"\n", k );
3237                cxr_vdf_edon( output );
3238
3239                cxr_vdf_node( output, "allowed_verts" );
3240                cxr_vdf_printf( output,
3241                   "\"10\" \"-1 -1 -1 -1 -1 -1 -1 -1 -1 -1\"\n" );
3242                cxr_vdf_edon( output );
3243                */
3244
3245                cxr_vdf_edon( output );
3246             }
3247
3248             cxr_vdf_edon( output );
3249          }
3250
3251          cxr_vdf_node( output, "editor");
3252          cxr_vdf_colour255( output, "color",
3253                colours_random[cxr_range(ctx->brush_count,8)]);
3254
3255          cxr_vdf_ki32( output, "visgroupid", ctx->visgroupid );
3256          cxr_vdf_ki32( output, "visgroupshown",1);
3257          cxr_vdf_ki32( output, "visgroupautoshown",1);
3258          cxr_vdf_edon( output );
3259
3260          cxr_vdf_edon( output );
3261          disp_count ++;
3262       }
3263    }
3264
3265    free( graph );
3266    free( vertinfo );
3267
3268    return 1;
3269 }
3270
3271 /*
3272  * Write header information for a vmf to vdf
3273  */
3274 CXR_API void cxr_begin_vmf( cxr_vmf_context *ctx, cxr_vdf *output )
3275 {
3276    cxr_vdf_node( output, "versioninfo" );
3277    cxr_vdf_ki32( output, "editorversion", 400 );
3278    cxr_vdf_ki32( output, "editorbuild", 8456 );
3279    cxr_vdf_ki32( output, "mapversion", ctx->mapversion );
3280    cxr_vdf_ki32( output, "formatversion", 100 );
3281    cxr_vdf_ki32( output, "prefab", 0 );
3282    cxr_vdf_edon( output );
3283
3284    cxr_vdf_node( output, "visgroups" );
3285
3286    for( int i=0; i<ctx->visgroup_count; i++ )
3287    {
3288       cxr_vdf_node( output, "visgroup" );
3289       cxr_vdf_kv( output, "name", ctx->visgroups[i].name );
3290       cxr_vdf_ki32( output, "visgroupid", i+1 );
3291       cxr_vdf_edon( output );
3292    }
3293
3294    cxr_vdf_edon( output );
3295
3296    cxr_vdf_node( output, "viewsettings" );
3297    cxr_vdf_ki32( output, "bSnapToGrid", 1 );
3298    cxr_vdf_ki32( output, "bShowGrid", 1 );
3299    cxr_vdf_ki32( output, "bShowLogicalGrid", 0 );
3300    cxr_vdf_ki32( output, "nGridSpacing", 64 );
3301    cxr_vdf_ki32( output, "bShow3DGrid", 0 );
3302    cxr_vdf_edon( output );
3303
3304    cxr_vdf_node( output, "world" );
3305    cxr_vdf_ki32( output, "id", 1 );
3306    cxr_vdf_ki32( output, "mapversion", 1 ); /* ?? */
3307    cxr_vdf_kv( output, "classname", "worldspawn" );
3308    cxr_vdf_kv( output, "skyname", ctx->skyname );
3309    cxr_vdf_ki32( output, "maxpropscreenwidth", -1 );
3310    cxr_vdf_kv( output, "detailvbsp", ctx->detailvbsp );
3311    cxr_vdf_kv( output, "detailmaterial", ctx->detailmaterial );
3312 }
3313
3314 /* Fairly useless but might need in the future */
3315 CXR_API void cxr_vmf_begin_entities( cxr_vmf_context *ctx, cxr_vdf *vdf )
3316 {
3317    cxr_vdf_edon( vdf );
3318 }
3319
3320 CXR_API void cxr_end_vmf( cxr_vmf_context *ctx, cxr_vdf *vdf )
3321 {
3322 }
3323
3324 /*
3325  * Write solids (and displacements) to VMF file
3326  */
3327 CXR_API void cxr_push_world_vmf( cxr_world *world, cxr_vmf_context *ctx,
3328       cxr_vdf *output
3329 ){
3330    v3f *verts = cxr_ab_ptr( &world->abverts, 0 );
3331
3332    /* Write all solids as VMF brushes */
3333    for( int i=0; i<world->absolids.count; i++ )
3334    {
3335       cxr_solid *solid = cxr_ab_ptr(&world->absolids,i);
3336
3337       if( solid->displacement )
3338       {
3339          cxr_write_disp( solid->pmesh, world, ctx, output );
3340          continue;
3341       }
3342
3343       cxr_vdf_node( output, "solid" );
3344       cxr_vdf_ki32( output, "id", ++ ctx->brush_count );
3345
3346       for( int j=0; j<solid->pmesh->abpolys.count; j++ )
3347       {
3348          cxr_polygon *poly = &solid->pmesh->polys[j];
3349          cxr_loop *ploops = &solid->pmesh->loops[poly->loop_start];
3350
3351          cxr_material *matptr =
3352             poly->material_id < 0 || !world->materials?
3353                &cxr_nodraw:
3354                &world->materials[ poly->material_id ];
3355
3356          cxr_vdf_node( output, "side" );
3357          cxr_vdf_ki32( output, "id", ++ ctx->face_count );
3358
3359          v3f tri[3]; v2f uvs[3];
3360
3361          int i0 = ploops[0].index,
3362              i1 = ploops[1].index,
3363              i2 = ploops[2].index;
3364
3365          v3_muls( verts[i0], ctx->scale, tri[0] );
3366          v3_muls( verts[i1], ctx->scale, tri[1] );
3367          v3_muls( verts[i2], ctx->scale, tri[2] );
3368
3369          v3_add( ctx->offset, tri[0], tri[0] );
3370          v3_add( ctx->offset, tri[1], tri[1] );
3371          v3_add( ctx->offset, tri[2], tri[2] );
3372
3373          v2_copy( ploops[0].uv, uvs[0] );
3374          v2_copy( ploops[1].uv, uvs[1] );
3375          v2_copy( ploops[2].uv, uvs[2] );
3376
3377          cxr_vdf_plane( output, "plane", tri[2], tri[1], tri[0] );
3378          cxr_vdf_kv( output, "material", matptr->name );
3379
3380          cxr_texinfo tx;
3381          cxr_calculate_axis( &tx, tri, uvs,
3382                (double[2]){ matptr->res[0], matptr->res[1] });
3383
3384          cxr_vdf_kaxis( output, "uaxis", tx.uaxis, tx.offset[0], tx.scale[0]);
3385          cxr_vdf_kaxis( output, "vaxis", tx.vaxis, tx.offset[1], tx.scale[1]);
3386
3387          cxr_vdf_kdouble( output, "rotation", 0.0 );
3388          cxr_vdf_ki32( output, "lightmapscale", ctx->lightmap_scale );
3389          cxr_vdf_ki32( output, "smoothing_groups", 0);
3390
3391          cxr_vdf_edon( output );
3392       }
3393
3394       cxr_vdf_node( output, "editor" );
3395       cxr_vdf_colour255( output, "color",
3396             colours_random[cxr_range(ctx->brush_count,8)]);
3397
3398       cxr_vdf_ki32( output, "visgroupid", ctx->visgroupid );
3399       cxr_vdf_ki32( output, "visgroupshown", 1 );
3400       cxr_vdf_ki32( output, "visgroupautoshown", 1 );
3401       cxr_vdf_edon( output );
3402
3403       cxr_vdf_edon( output );
3404    }
3405 }
3406
3407 /*
3408  * Valve Source SDK 2015 CS:GO
3409  */
3410 #define HEADER_LUMPS            64
3411 #define  LUMP_WORLDLIGHTS  54
3412
3413 #pragma pack(push,1)
3414
3415 struct header
3416 {
3417    int        ident;
3418    int        version;
3419
3420    struct lump
3421    {
3422       int fileofs, filelen;
3423       int version;
3424
3425       char fourCC[4];
3426    }
3427    lumps[ HEADER_LUMPS ];
3428
3429    int        mapRevision;
3430 };
3431
3432 struct worldlight
3433 {
3434         float              origin[3];
3435         float              intensity[3];
3436         float              normal[3];
3437         float              shadow_cast_offset[3];
3438         int                     cluster;
3439         int         type;
3440    int                  style;
3441         float              stopdot;
3442         float              stopdot2;
3443         float           exponent;
3444         float           radius;
3445         float              constant_attn;
3446         float              linear_attn;
3447         float              quadratic_attn;
3448         int                     flags;
3449         int                     texinfo;
3450         int                     owner;
3451 };
3452 #pragma pack(pop)
3453
3454 /*
3455  * Utility for patching BSP tools to remove -1 distance lights (we set them
3456  *  like that, because we want these lights to go away)
3457  *
3458  *  Yes, there is no way to do this in hammer
3459  *  Yes, the distance KV is unused but still gets compiled to this lump
3460  *  No, Entities only compile will not do this for you
3461  */
3462 CXR_API int cxr_lightpatch_bsp( const char *path )
3463 {
3464    printf( "Lightpatch: %s\n", path );
3465
3466    FILE *fp = fopen( path, "r+b" );
3467
3468    if( !fp )
3469    {
3470 #ifdef CXR_DEBUG
3471       cxr_log( "Could not open BSP file for editing (r+b)\n" );
3472 #endif
3473       return 0;
3474    }
3475
3476    /* Read bsp */
3477    struct header header;
3478    fread( &header, sizeof(struct header), 1, fp );
3479    struct lump *lump = &header.lumps[ LUMP_WORLDLIGHTS ];
3480
3481    /* Read worldlight array */
3482    struct worldlight *lights = malloc( lump->filelen );
3483    fseek( fp, lump->fileofs, SEEK_SET );
3484    fread( lights, lump->filelen, 1, fp );
3485
3486    /* Remove all marked lights */
3487    int light_count = lump->filelen / sizeof(struct worldlight);
3488    int new_count = 0;
3489
3490    for( int i = 0; i < light_count; i ++ )
3491       if( lights[i].radius >= 0.0f )
3492          lights[new_count++] = lights[i];
3493
3494    lump->filelen = new_count*sizeof(struct worldlight);
3495
3496    /* Write changes back to file */
3497    fseek( fp, lump->fileofs, SEEK_SET );
3498    fwrite( lights, lump->filelen, 1, fp );
3499    fseek( fp, 0, SEEK_SET );
3500    fwrite( &header, sizeof(struct header), 1, fp );
3501
3502 #ifdef CXR_DEBUG
3503    cxr_log( "removed %d marked lights\n", light_count-new_count );
3504 #endif
3505
3506    fclose( fp );
3507    free( lights );
3508
3509    return 1;
3510 }
3511 #endif /* CXR_VALVE_MAP_FILE */
3512 #endif /* CXR_IMPLEMENTATION */