src/convexer.c

   1 /*
   2                               CONVEXER v0.8
   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       - Light patch BSP files; remove unwanted realtime effects
  15       - Fastest VTF compressor (thanks to Richgel999 and stb)
  16
  17    To come:
  18       - high quality level overviews automatically for CS:GO (csRadar)
  19
  20    Program structure:
  21
  22    File/folder       Lang     Purpose
  23    src/
  24      __init__.py     Python   Blender plugin interface
  25      convexer.c      C        Heavy lifting; brush decomp, mesh processing
  26      cxr_math.h      C        Vector maths and other handy things
  27      cxr_mem.h       C        Automatic resizing buffers
  28      nbvtf/
  29        nbvtf.h       C        VTF processing interface
  30        librgcx.h     C++      Rich Geldreich's DXT1/DXT5 compressors
  31        stb/          C        Sean Barrets image I/O
  32 */
  33
  34 #include <stdio.h>
  35 #include <math.h>
  36 #include <stdint.h>
  37 #include <stdarg.h>
  38 #include <stdlib.h>
  39 #include <string.h>
  40
  41 const char *cxr_build_time = __DATE__ " @" __TIME__;
  42
  43 typedef uint8_t         u8;
  44 typedef uint16_t        u16;
  45 typedef uint32_t        u32;
  46 typedef uint64_t        u64;
  47 typedef int8_t  i8;
  48 typedef int16_t         i16;
  49 typedef int32_t         i32;
  50 typedef int64_t         i64;
  51
  52 typedef unsigned int uint;
  53
  54 typedef double          v2f[2];
  55 typedef double          v3f[3];
  56 typedef double          v4f[4];
  57 typedef v3f                     m3x3f[3];
  58 typedef v3f                     m4x3f[4];
  59 typedef v3f                     boxf[2];
  60
  61 #define CXR_EPSILON 0.001
  62 #define CXR_INTERIOR_ANGLE_MAX 0.998
  63 #define CXR_API
  64 #define CXR_DIRTY_OPTIMISATION 1
  65 #define CXR_DEBUG_WRITE_MESH 1
  66 #define CXR_DEBUG_ALLOCATORS 1
  67 #define CXR_MANIFOLD_DEBUG 0
  68
  69 #define CXR_ERROR_DEGEN_IMPLICIT 0x1
  70 #define CXR_ERROR_BAD_MANIFOLD 0x2
  71 #define CXR_ERROR_NO_SOLIDS 0x4
  72
  73 #include "cxr_math.h"
  74 #include "cxr_mem.h"
  75
  76 // Utility
  77 // ============================================
  78
  79 static v4f colours_random[] =
  80 {
  81    { 0.863, 0.078, 0.235, 0.4 },
  82    { 0.000, 0.980, 0.604, 0.4 },
  83    { 0.118, 0.565, 1.000, 0.4 },
  84    { 0.855, 0.439, 0.839, 0.4 },
  85    { 0.824, 0.412, 0.118, 0.4 },
  86    { 0.125, 0.698, 0.667, 0.4 },
  87    { 0.541, 0.169, 0.886, 0.4 },
  88    { 1.000, 0.843, 0.000, 0.4 }
  89 };
  90
  91 static int cxr_range(int x, int bound)
  92 {
  93    if( x < 0 )
  94       x += bound * (x/bound + 1);
  95
  96    return x % bound;
  97 }
  98
  99 struct cxr_input_mesh
 100 {
 101    v3f *vertices;
 102
 103    struct cxr_edge
 104    {
 105       i32 i0, i1;
 106       i32 freestyle;
 107    }
 108    *edges;
 109
 110    struct cxr_input_loop
 111    {
 112       i32 index,
 113           edge_index;
 114       v2f uv;
 115    }
 116    *loops;
 117
 118    struct cxr_polygon
 119    {
 120       i32 loop_start, loop_total;
 121       v3f normal;
 122       v3f center;
 123       i32 material_id;  // -1: interior material
 124    }
 125    *polys;
 126
 127    struct cxr_material
 128    {
 129       i32 res[2];
 130       const char *vmt_path;
 131    }
 132    *materials;
 133
 134    i32 poly_count,
 135        vertex_count,
 136        edge_count,
 137        loop_count,
 138        material_count;
 139 };
 140
 141 struct cxr_loop
 142 {
 143    i32 poly_left,
 144        poly_right,
 145        edge_index,
 146        index;
 147    v2f uv;
 148 };
 149
 150 struct cxr_solid
 151 {
 152    i32 *polygons;
 153 };
 154
 155 struct cxr_mesh
 156 {
 157    struct cxr_auto_buffer
 158       edges,
 159       loops,
 160       polys;
 161 };
 162
 163 struct cxr_texinfo
 164 {
 165    v3f uaxis, vaxis;
 166    v2f offset, scale;
 167 };
 168
 169 // simple VDF writing interface
 170 struct cxr_vdf
 171 {
 172    FILE *fp;
 173    i32 level;
 174 };
 175
 176 static struct cxr_settings
 177 {
 178    i32 debug,
 179        lightmap_scale;
 180
 181    double light_scale;
 182 }
 183 cxr_settings = {
 184    .debug = 0,
 185    .lightmap_scale = 12,
 186
 187    .light_scale = 1.0/5.0
 188 };
 189
 190 static struct cxr_context
 191 {
 192    i32 brush_count,
 193        entity_count,
 194        face_count;
 195
 196    double scale_factor;
 197    double offset_z;
 198 }
 199 cxr_context = {
 200    .brush_count = 0,
 201    .entity_count = 0,
 202    .face_count = 0,
 203    .scale_factor = 32.0,
 204    .offset_z = 0.0
 205 };
 206
 207 static struct cxr_material cxr_nodraw = {
 208    .res = { 512, 512 },
 209    .vmt_path = "tools/toolsnodraw"
 210 };
 211
 212 // Debugging callbacks
 213 // =============================================================================
 214
 215 static v4f colour_error = { 1.0f, 0.0f, 0.0f, 1.0f };
 216 static v4f colour_face_graph = { 1.0f, 1.0f, 1.0f, 0.03f };
 217 static v4f colour_success = { 0.0f, 1.0f, 0.0f, 1.0f };
 218
 219 static void (*cxr_log_func)(const char *str);
 220 static void (*cxr_line_func)( v3f p0, v3f p1, v4f colour );
 221
 222 static void cxr_log( const char *fmt, ... )
 223 {
 224    char buf[512];
 225
 226    va_list args;
 227    va_start( args, fmt );
 228    vsnprintf( buf, sizeof(buf)-1, fmt, args );
 229    va_end(args);
 230
 231    if( cxr_log_func )
 232       cxr_log_func( buf );
 233
 234    fputs(buf,stdout);
 235 }
 236
 237 static void cxr_debug_line( v3f p0, v3f p1, v4f colour )
 238 {
 239    if( cxr_line_func )
 240       cxr_line_func( p0, p1, colour );
 241 }
 242
 243 static void cxr_debug_box( v3f p0, double sz, v4f colour )
 244 {
 245    v3f a,b,c,d,
 246        a1,b1,c1,d1;
 247    v3_add(p0, (v3f){-sz,-sz,-sz}, a);
 248    v3_add(p0, (v3f){-sz, sz,-sz}, b);
 249    v3_add(p0, (v3f){ sz, sz,-sz}, c);
 250    v3_add(p0, (v3f){ sz,-sz,-sz}, d);
 251    v3_add(p0, (v3f){-sz,-sz,sz}, a1);
 252    v3_add(p0, (v3f){-sz, sz,sz}, b1);
 253    v3_add(p0, (v3f){ sz, sz,sz}, c1);
 254    v3_add(p0, (v3f){ sz,-sz,sz}, d1);
 255
 256    cxr_debug_line( a,b, colour );
 257    cxr_debug_line( b,c, colour );
 258    cxr_debug_line( c,d, colour );
 259    cxr_debug_line( d,a, colour );
 260    cxr_debug_line( a1,b1, colour );
 261    cxr_debug_line( b1,c1, colour );
 262    cxr_debug_line( c1,d1, colour );
 263    cxr_debug_line( d1,a1, colour );
 264    cxr_debug_line( a,a1, colour );
 265    cxr_debug_line( b,b1, colour );
 266    cxr_debug_line( c,c1, colour );
 267    cxr_debug_line( d,d1, colour );
 268 }
 269
 270 static void cxr_debug_arrow( v3f p0, v3f p1, v3f normal, double sz, v4f colour )
 271 {
 272    v3f dir, tan, p2, p3;
 273    v3_sub(p1,p0,dir);
 274    v3_normalize(dir);
 275
 276    v3_cross(dir,normal,tan);
 277    v3_muladds( p1,dir, -sz, p2 );
 278    v3_muladds( p2,tan,sz,p3 );
 279    cxr_debug_line( p1, p3, colour );
 280    v3_muladds( p2,tan,-sz,p3 );
 281    cxr_debug_line( p1, p3, colour );
 282    cxr_debug_line( p0, p1, colour );
 283 }
 284
 285 // Public API
 286 // =========================================================================
 287
 288 CXR_API void cxr_context_reset(void)
 289 {
 290    cxr_context.brush_count = 0;
 291    cxr_context.entity_count = 0;
 292    cxr_context.face_count = 0;
 293    cxr_context.offset_z = 0.0;
 294    cxr_context.scale_factor = 32.0;
 295 }
 296
 297 CXR_API void cxr_set_offset(double offset)
 298 {
 299    cxr_context.offset_z = offset;
 300 }
 301
 302 CXR_API void cxr_set_scale_factor(double scale)
 303 {
 304    cxr_context.scale_factor = scale;
 305 }
 306
 307 CXR_API struct cxr_vdf *cxr_vdf_open(const char *path)
 308 {
 309    struct cxr_vdf *vdf = malloc(sizeof(struct cxr_vdf));
 310
 311    vdf->level = 0;
 312    vdf->fp = fopen( path, "w" );
 313
 314    if( !vdf->fp )
 315    {
 316       free( vdf );
 317       return NULL;
 318    }
 319
 320    return vdf;
 321 }
 322
 323 CXR_API void cxr_vdf_close(struct cxr_vdf *vdf)
 324 {
 325    fclose( vdf->fp );
 326 }
 327
 328 CXR_API void cxr_vdf_put(struct cxr_vdf *vdf, const char *str)
 329 {
 330    for( int i=0; i<vdf->level; i++ )
 331       fputs( " ", vdf->fp );
 332
 333    fputs( str, vdf->fp );
 334 }
 335
 336 static void cxr_vdf_printf( struct cxr_vdf *vdf, const char *fmt, ... )
 337 {
 338    cxr_vdf_put(vdf,"");
 339
 340    va_list args;
 341    va_start( args, fmt );
 342    vfprintf( vdf->fp, fmt, args );
 343    va_end(args);
 344 }
 345
 346 CXR_API void cxr_vdf_node(struct cxr_vdf *vdf, const char *str)
 347 {
 348    cxr_vdf_put( vdf, str );
 349    putc( (u8)'\n', vdf->fp );
 350    cxr_vdf_put( vdf, "{\n" );
 351
 352    vdf->level ++;
 353 }
 354
 355 CXR_API void cxr_vdf_edon(struct cxr_vdf *vdf)
 356 {
 357    vdf->level --;
 358    cxr_vdf_put( vdf, "}\n" );
 359 }
 360
 361 CXR_API void cxr_vdf_kv(struct cxr_vdf *vdf, const char *strk, const char *strv)
 362 {
 363    cxr_vdf_printf( vdf, "\"%s\" \"%s\"\n", strk, strv );
 364 }
 365
 366 static void cxr_vdf_ki32(struct cxr_vdf *vdf, const char *strk, i32 val)
 367 {
 368    cxr_vdf_printf( vdf, "\"%s\" \"%d\"\n", strk, val );
 369 }
 370 static void cxr_vdf_kdouble(struct cxr_vdf *vdf, const char *strk, double val)
 371 {
 372    cxr_vdf_printf( vdf, "\"%s\" \"%f\"\n", strk, val );
 373 }
 374 static void cxr_vdf_kaxis(struct cxr_vdf *vdf, const char *strk, v3f normal, double offset, double scale)
 375 {
 376    cxr_vdf_printf( vdf, "\"%s\" \"[%f %f %f %f] %f\"\n", strk, normal[0],normal[1],normal[2],offset,scale );
 377 }
 378 static void cxr_vdf_plane(struct cxr_vdf *vdf, const char *strk, v3f a, v3f b, v3f c )
 379 {
 380    cxr_vdf_printf( vdf, "\"%s\" \"(%f %f %f) (%f %f %f) (%f %f %f)\"\n",
 381          strk, a[0], a[1], a[2], b[0], b[1], b[2], c[0], c[1], c[2] );
 382 }
 383 static void cxr_vdf_colour255(struct cxr_vdf *vdf, const char *strk, v4f colour)
 384 {
 385    v4f scale;
 386    v4_muls( colour, 255.0, scale );
 387    cxr_vdf_printf( vdf, "\"%s\" \"%d %d %d %d\"\n",strk,(int)scale[0], (int)scale[1], (int)scale[2], (int)scale[3]);
 388 }
 389
 390 // Public API
 391 // =========================================================================
 392
 393 static void cxr_debug_poly(struct cxr_mesh *mesh, struct cxr_polygon *poly, v3f *verts, v4f colour )
 394 {
 395    for( int i=0; i<poly->loop_total; i++ )
 396    {
 397       struct cxr_loop *loop0 = cxr_ab_ptr(&mesh->loops,poly->loop_start+i),
 398                       *loop1 = cxr_ab_ptr(&mesh->loops,poly->loop_start+cxr_range(i+1,poly->loop_total));
 399
 400       v3f p0, p1;
 401
 402       v3_lerp( verts[loop0->index], poly->center, 0.02, p0 );
 403       v3_lerp( verts[loop1->index], poly->center, 0.02, p1 );
 404
 405       cxr_debug_arrow( p0, p1, poly->normal, 0.05, colour );
 406    }
 407
 408    v3f nrm0;
 409    v3_muladds( poly->center, poly->normal, 0.3, nrm0 );
 410
 411    cxr_debug_line( poly->center, nrm0, colour );
 412 }
 413
 414 static void cxr_debug_mesh(struct cxr_mesh *mesh, v3f *verts, v4f colour )
 415 {
 416    for( int i=0; i<mesh->polys.count; i++ )
 417    {
 418       struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys,i);
 419       cxr_debug_poly( mesh, poly, verts, colour );
 420    }
 421 }
 422
 423 static struct cxr_mesh *cxr_alloc_mesh(int edge_count, int loop_count, int poly_count )
 424 {
 425    struct cxr_mesh *mesh = malloc(sizeof(struct cxr_mesh));
 426    cxr_ab_init(&mesh->edges, sizeof(struct cxr_edge), edge_count);
 427    cxr_ab_init(&mesh->loops, sizeof(struct cxr_loop), loop_count);
 428    cxr_ab_init(&mesh->polys, sizeof(struct cxr_polygon), poly_count);
 429    return mesh;
 430 }
 431
 432 static void cxr_free_mesh(struct cxr_mesh *mesh)
 433 {
 434    cxr_ab_free(&mesh->edges);
 435    cxr_ab_free(&mesh->loops);
 436    cxr_ab_free(&mesh->polys);
 437    free(mesh);
 438 }
 439
 440 // Rebuilds edge data and reallocates
 441 //
 442 static void cxr_mesh_clean_edges(struct cxr_mesh *mesh)
 443 {
 444    struct cxr_auto_buffer new_edges;
 445    cxr_ab_init( &new_edges, sizeof(struct cxr_edge), mesh->edges.count );
 446
 447    for( int i=0; i<mesh->polys.count; i++ )
 448    {
 449       struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys,i);
 450       for( int j=0; j<poly->loop_total; j++ )
 451       {
 452          struct cxr_loop
 453             *lp0 = cxr_ab_ptr(&mesh->loops,poly->loop_start+j),
 454             *lp1 = cxr_ab_ptr(&mesh->loops,poly->loop_start+cxr_range(j+1,poly->loop_total));
 455
 456          int i0 = cxr_min(lp0->index, lp1->index),
 457              i1 = cxr_max(lp0->index, lp1->index);
 458
 459          // See if edge exists before adding it
 460          for( int k=0; k<new_edges.count; k++ )
 461          {
 462             struct cxr_edge *edge = cxr_ab_ptr(&new_edges,k);
 463
 464             if( edge->i0 == i0 && edge->i1 == i1 )
 465             {
 466                lp0->edge_index = k;
 467                goto IL_EDGE_CREATED;
 468             }
 469          }
 470
 471          int orig_edge_id = lp0->edge_index;
 472          lp0->edge_index = new_edges.count;
 473
 474          struct cxr_edge edge = { i0, i1 };
 475          // --- ! ---
 476          // Copy extra information (sharp,freestyle.. etc) here!
 477
 478          if( orig_edge_id < mesh->edges.count )
 479          {
 480             struct cxr_edge *orig_edge = cxr_ab_ptr( &mesh->edges, orig_edge_id );
 481             edge.freestyle = orig_edge->freestyle;
 482          }
 483          else
 484          {
 485             edge.freestyle = 0;
 486          }
 487
 488          // --- ! ---
 489          cxr_ab_push( &new_edges, &edge );
 490
 491 IL_EDGE_CREATED:;
 492       }
 493    }
 494
 495    cxr_ab_free( &mesh->edges );
 496    mesh->edges = new_edges;
 497 }
 498
 499 // Remove 0-length faces from mesh and correct loops
 500 //
 501 static void cxr_mesh_clean_faces(struct cxr_mesh *mesh)
 502 {
 503    struct cxr_auto_buffer loops_new;
 504    cxr_ab_init( &loops_new, sizeof(struct cxr_loop), mesh->loops.count );
 505
 506    int new_length=0;
 507    for( int i=0; i<mesh->polys.count; i++ )
 508    {
 509       struct cxr_polygon *src = cxr_ab_ptr(&mesh->polys,i),
 510                          *dst = cxr_ab_ptr(&mesh->polys,new_length);
 511
 512       if( src->loop_total > 0 )
 513       {
 514          int src_start = src->loop_start,
 515              src_total = src->loop_total;
 516
 517          *dst = *src;
 518          dst->loop_start = loops_new.count;
 519
 520          for( int j=0; j<src_total; j++ )
 521          {
 522             struct cxr_loop *loop = cxr_ab_ptr(&mesh->loops,src_start+j),
 523                             *ldst = cxr_ab_ptr(&loops_new,dst->loop_start+j);
 524             *ldst = *loop;
 525             ldst->poly_left = new_length;
 526          }
 527
 528          loops_new.count += src_total;
 529          new_length ++;
 530       }
 531    }
 532
 533    cxr_ab_free( &mesh->loops );
 534    mesh->loops = loops_new;
 535    mesh->polys.count = new_length;
 536 }
 537
 538 static i32 *cxr_mesh_link_loops(struct cxr_mesh *mesh)
 539 {
 540    i32 *polygon_edge_map = malloc(mesh->edges.count*2 *sizeof(i32));
 541
 542    for( int i = 0; i < mesh->edges.count*2; i ++ )
 543       polygon_edge_map[i] = -1;
 544
 545    for( int i = 0; i < mesh->polys.count; i ++ )
 546    {
 547       struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys, i);
 548
 549       for( int j = 0; j < poly->loop_total; j ++ )
 550       {
 551          struct cxr_loop *loop = cxr_ab_ptr(&mesh->loops, poly->loop_start+j);
 552          loop->poly_left = i;
 553
 554          for( int k = 0; k < 2; k ++ )
 555          {
 556             i32 *edge = &polygon_edge_map[loop->edge_index*2+k];
 557
 558             if( *edge == -1 )
 559             {
 560                *edge = i;
 561                break;
 562             }
 563          }
 564       }
 565    }
 566    for( int i = 0; i < mesh->polys.count; i ++ )
 567    {
 568       struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys,i);
 569
 570       for( int j = 0; j < poly->loop_total; j ++ )
 571       {
 572          struct cxr_loop *loop = cxr_ab_ptr(&mesh->loops,poly->loop_start+j);
 573
 574          i32 *face_map = &polygon_edge_map[loop->edge_index*2];
 575
 576          if( face_map[0] == loop->poly_left ) loop->poly_right = face_map[1];
 577          else loop->poly_right = face_map[0];
 578       }
 579    }
 580
 581    return polygon_edge_map;
 582 }
 583
 584 // Add polygon to mesh based on loop array
 585 static struct cxr_polygon *cxr_create_poly( struct cxr_mesh *mesh, v3f *vertices, struct cxr_loop poly[],
 586    int len, int start, int max )
 587 {
 588    if( len < 3 )
 589    {
 590       cxr_log( "tried to add new poly with length %d!\n", len );
 591
 592       if( len >= 2 )
 593       {
 594          for( int j=0; j<len; j++ )
 595          {
 596             int i0 = poly[j].index,
 597                 i1 = poly[cxr_range(j+1,len)].index;
 598             cxr_debug_line( vertices[i0], vertices[i1], colour_error );
 599          }
 600       }
 601
 602       return NULL;
 603    }
 604
 605    int nface_id = mesh->polys.count;
 606    struct cxr_polygon *new_face = cxr_ab_empty(&mesh->polys);
 607
 608    new_face->loop_start = mesh->loops.count;
 609    new_face->loop_total = len;
 610    new_face->material_id = -1;
 611
 612    // Calculate normal and center
 613    v3_zero( new_face->center );
 614
 615    for( int j=0; j<len; j++ )
 616    {
 617       int i0 = poly[cxr_range(start+j,max)].index;
 618       struct cxr_loop *new_loop = cxr_ab_empty(&mesh->loops);
 619
 620       new_loop->poly_left = nface_id;
 621       new_loop->poly_right = -1;
 622       new_loop->index = i0;
 623       new_loop->edge_index = 0;
 624       v2_zero(new_loop->uv);
 625
 626       v3_add( new_face->center, vertices[new_loop->index], new_face->center );
 627    }
 628    v3_divs( new_face->center, new_face->loop_total, new_face->center );
 629
 630    struct cxr_loop *lp0 = cxr_ab_ptr( &mesh->loops, new_face->loop_start ),
 631                    *lp1 = cxr_ab_ptr( &mesh->loops, new_face->loop_start+1 ),
 632                    *lp2 = cxr_ab_ptr( &mesh->loops, new_face->loop_start+2 );
 633
 634    tri_normal( vertices[lp0->index], vertices[lp1->index], vertices[lp2->index], new_face->normal );
 635
 636    return cxr_ab_ptr(&mesh->polys, nface_id);
 637 }
 638
 639 // Get the 'next' mesh island
 640 //
 641 // Returns NULL if there is only one island
 642 static struct cxr_mesh *cxr_pull_island(struct cxr_mesh *mesh)
 643 {
 644    free(cxr_mesh_link_loops(mesh));
 645
 646    int *island_current = malloc(mesh->polys.count*sizeof(int)),
 647         island_len = 1,
 648         loop_count = 0,
 649         last_count;
 650
 651    island_current[0] = 0;
 652
 653    IL_ISLAND_REPEAT:
 654    last_count = island_len;
 655
 656    for( int i=0; i<island_len; i++ )
 657    {
 658       struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys,island_current[i]);
 659
 660       for( int j=0; j<poly->loop_total; j++ )
 661       {
 662          struct cxr_loop *loop = cxr_ab_ptr(&mesh->loops, poly->loop_start+j);
 663
 664          if( loop->poly_right != -1 )
 665          {
 666             int face_present = 0;
 667
 668             for( int k=0; k<island_len; k++ )
 669             {
 670                if( island_current[k] == loop->poly_right )
 671                {
 672                   face_present = 1;
 673                   break;
 674                }
 675             }
 676
 677             if( !face_present )
 678             {
 679                island_current[ island_len ++ ] = loop->poly_right;
 680             }
 681          }
 682       }
 683    }
 684
 685    if( island_len > last_count )
 686       goto IL_ISLAND_REPEAT;
 687
 688    if( island_len == mesh->polys.count )
 689    {
 690       free( island_current );
 691       return NULL;
 692    }
 693
 694    for( int i=0; i<island_len; i++ )
 695    {
 696       struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys, island_current[i]);
 697       loop_count += poly->loop_total;
 698    }
 699
 700    struct cxr_mesh *newmesh = cxr_alloc_mesh( mesh->edges.count, loop_count, island_len );
 701
 702    for( int i=0; i<island_len; i++ )
 703    {
 704       struct cxr_polygon *src = cxr_ab_ptr(&mesh->polys, island_current[i]);
 705       struct cxr_polygon *dst = cxr_ab_ptr(&newmesh->polys, i);
 706
 707       *dst = *src;
 708       dst->loop_start = newmesh->loops.count;
 709
 710       for( int j=0; j<src->loop_total; j++ )
 711       {
 712          struct cxr_loop *lsrc = cxr_ab_ptr(&mesh->loops, src->loop_start+j),
 713                          *ldst = cxr_ab_ptr(&newmesh->loops, dst->loop_start+j);
 714
 715          *ldst = *lsrc;
 716          ldst->poly_left = i;
 717          ldst->poly_right = -1;
 718       }
 719
 720       newmesh->loops.count += src->loop_total;
 721       src->loop_total = -1;
 722    }
 723
 724    newmesh->polys.count = island_len;
 725    newmesh->edges.count = mesh->edges.count;
 726    memcpy(cxr_ab_ptr(&newmesh->edges,0), cxr_ab_ptr(&mesh->edges,0), mesh->edges.count*sizeof(struct cxr_edge));
 727
 728    cxr_mesh_clean_faces(mesh);
 729    cxr_mesh_clean_edges(mesh);
 730    cxr_mesh_clean_edges(newmesh);
 731    free( island_current );
 732
 733    return newmesh;
 734 }
 735
 736 // Return best availible solid from mesh, and patch existing mesh to fill the gap
 737 // creted by it.
 738 //
 739 // Returns NULL if shape is already convex or empty
 740 // Destroys edge data!
 741 static struct cxr_mesh *cxr_pull_best_solid(
 742       struct cxr_mesh *mesh,
 743       struct cxr_auto_buffer *vert_buffer,
 744       int preserve_hot_edges,
 745       u32 *error )
 746 {
 747    v3f *vertices = cxr_ab_ptr( vert_buffer, 0 );
 748
 749    i32 *polygon_edge_map = cxr_mesh_link_loops(mesh);
 750
 751    for( int i=0; i<mesh->edges.count*2; i++ )
 752       if( polygon_edge_map[i] == -1 )
 753       {
 754          cxr_log( "non-manifold edges are in the mesh; implicit internal geometry does not have full support\n" );
 755          free(polygon_edge_map);
 756          return NULL;
 757       }
 758
 759    int *vertex_tagged = malloc( vert_buffer->count*sizeof(int) );
 760    int *edge_tagged = malloc( mesh->edges.count*sizeof(int) );
 761
 762    for( int i=0; i<mesh->edges.count; i++ )
 763    {
 764       struct cxr_polygon *polya = cxr_ab_ptr(&mesh->polys, polygon_edge_map[i*2+0]),
 765                          *polyb = cxr_ab_ptr(&mesh->polys, polygon_edge_map[i*2+1]);
 766       v4f planeb;
 767       normal_to_plane(polyb->normal, polyb->center, planeb);
 768
 769       edge_tagged[i] = 0;
 770       for( int j=0; j<polya->loop_total; j++ )
 771       {
 772          struct cxr_loop *loop = cxr_ab_ptr(&mesh->loops, polya->loop_start+j);
 773          if( plane_polarity( planeb, vertices[loop->index] ) > 0.001 ||
 774              v3_dot(polya->normal,polyb->normal) > 0.98500 )
 775          {
 776             edge_tagged[i] = 1;
 777             break;
 778          }
 779       }
 780    }
 781
 782    // Tag 'reflex' vertices
 783    int *connected_planes = malloc(mesh->polys.count*sizeof(int));
 784
 785    for( int i=0; i<vert_buffer->count; i++ )
 786    {
 787       vertex_tagged[i]=0;
 788
 789       int num_connected = 0;
 790       // Create a list of polys that ref this vert
 791       for( int j=0; j<mesh->polys.count; j++ )
 792       {
 793          struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys,j);
 794          for( int k=0; k<poly->loop_total; k++ )
 795          {
 796             struct cxr_loop *loop = cxr_ab_ptr(&mesh->loops,poly->loop_start+k);
 797             if( loop->index == i )
 798             {
 799                connected_planes[num_connected ++] = j;
 800                break;
 801             }
 802          }
 803       }
 804       // Check all combinations for a similar normal
 805       for( int j=0; j<num_connected-1; j++ )
 806       {
 807          for( int k=j+1; k<num_connected; k++ )
 808          {
 809             struct cxr_polygon *polyj = cxr_ab_ptr(&mesh->polys,connected_planes[j]);
 810             struct cxr_polygon *polyk = cxr_ab_ptr(&mesh->polys,connected_planes[k]);
 811
 812             if( v3_dot(polyj->normal, polyk->normal) > 0.98500 )
 813                goto IL_TAG_VERT;
 814          }
 815       }
 816
 817       // Check if all connected planes not are:
 818       //   - bounded by other planes
 819       //   - or coplanar
 820
 821       for( int j=0; j<num_connected; j++ )
 822          for( int k=j+1; k<num_connected; k++ )
 823          {
 824             struct cxr_polygon *jpoly = cxr_ab_ptr(&mesh->polys, connected_planes[j]),
 825                                *kpoly = cxr_ab_ptr(&mesh->polys, connected_planes[k]);
 826             v4f plane;
 827             normal_to_plane( kpoly->normal, kpoly->center, plane );
 828             for( int l=0; l<jpoly->loop_total; l++ )
 829             {
 830                struct cxr_loop *loop = cxr_ab_ptr(&mesh->loops, jpoly->loop_start+l);
 831                if( plane_polarity( plane, vertices[loop->index] ) > 0.001 )
 832                   goto IL_TAG_VERT;
 833             }
 834          }
 835
 836       goto IL_TAG_NEXT_VERT;
 837 IL_TAG_VERT: vertex_tagged[i] = 1;
 838 IL_TAG_NEXT_VERT:;
 839    }
 840
 841    free( connected_planes );
 842
 843    // Connect all marked verts that share an edge
 844    //  - We must take care not to completely isolate
 845    //    a polygon with marked edges all around it
 846
 847    int *hot_edge = malloc(mesh->edges.count*sizeof(int));
 848    for( int i=0; i< mesh->edges.count; i++ )
 849       hot_edge[i] = 0;
 850
 851    for( int i=0; i<mesh->polys.count; i ++ )
 852    {
 853       struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys,i);
 854       int not_tagged = -1,
 855           tag_count = 0;
 856
 857       for( int j=0; j<poly->loop_total; j++ )
 858       {
 859          struct cxr_loop *loop = cxr_ab_ptr(&mesh->loops, poly->loop_start+j);
 860
 861          if( !edge_tagged[ loop->edge_index ] )
 862          {
 863             if( not_tagged == -1 )
 864                not_tagged = loop->edge_index;
 865             else
 866                goto IL_SKIP_NO_HOT_EDGE;
 867          }
 868       }
 869
 870       if( not_tagged != -1 )
 871          hot_edge[not_tagged]=1;
 872
 873       IL_SKIP_NO_HOT_EDGE:;
 874    }
 875
 876    // Connect edges that have verts tagged, but is not a hot edge
 877    for( int i=0; i<mesh->edges.count; i ++ )
 878    {
 879       if( hot_edge[i] && preserve_hot_edges ) continue;
 880
 881       struct cxr_edge *edge = cxr_ab_ptr(&mesh->edges,i);
 882       if( vertex_tagged[edge->i0] && vertex_tagged[edge->i1] )
 883          edge_tagged[i] = 1;
 884    }
 885
 886    /* Debug stuff --
 887    for( int i=0; i<vertex_count; i++ )
 888       if( vertex_tagged[i] )
 889          cxr_debug_box( vertices[i], 0.03, (v4f){0.0,0.0,0.0,1.0});
 890
 891    for( int i=0; i < mesh->edges.count; i++ )
 892    {
 893       struct cxr_edge *edge = cxr_ab_ptr( &mesh->edges, i );
 894       if( edge_tagged[i] )
 895          cxr_debug_line( vertices[ edge->i0 ], vertices[ edge->i1 ], (v4f){0.0,0.0,0.0,1.0});
 896
 897       if( hot_edge[i] )
 898          cxr_debug_line( vertices[ edge->i0 ], vertices[ edge->i1 ], (v4f){0.0,1.0,1.0,1.0});
 899    }
 900    */
 901
 902    // count regions
 903    int *faces_tagged = malloc(mesh->polys.count*sizeof(int));
 904    for( int i=0; i<mesh->polys.count; i++ )
 905       faces_tagged[i] = -1;
 906
 907    int *solid_buffer = malloc( mesh->polys.count*sizeof(int) );
 908    int solid_buffer_len = 0;
 909    struct csolid
 910    {
 911       int start,count,edge_count;
 912       v3f center;
 913    }
 914    *candidates = malloc( mesh->polys.count *sizeof(struct csolid) );
 915    int candidate_count = 0;
 916
 917    for( int i=0; i<mesh->polys.count; i++ )
 918    {
 919       if( faces_tagged[i] != -1 ) continue;
 920       faces_tagged[i] = i;
 921
 922       int *solid = &solid_buffer[ solid_buffer_len ];
 923       int solid_len = 0;
 924
 925       solid[solid_len++] = i;
 926
 927       int search_start = 0;
 928
 929       // Iterative search that connects regions of planes governed by rules:
 930       //   - edge can add other face if the edge has less than two reflexes
 931       //   - the face can no longer be used in future searches
 932
 933    IL_SEARCH_CONTINUE:;
 934
 935       int changed = 0;
 936       for( int j=search_start; j<solid_len; j++ )
 937       {
 938          struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys, solid[j]);
 939
 940          for( int k=0; k<poly->loop_total; k++ )
 941          {
 942             struct cxr_loop *loop = cxr_ab_ptr(&mesh->loops, poly->loop_start+k);
 943             struct cxr_edge *edge = cxr_ab_ptr(&mesh->edges, loop->edge_index );
 944
 945             if( faces_tagged[ loop->poly_right ] == -1 )
 946             {
 947                if( !edge_tagged[loop->edge_index] )
 948                {
 949                   // Need to look ahead 1 step to make sure he does not want
 950                   // to add any more planes that are coplanar with some of
 951                   // our existing group
 952                   //
 953                   // TODO: is this unused due to hotedge improvements? leaving for safety...
 954
 955                   struct cxr_polygon *poly_to_add = cxr_ab_ptr(&mesh->polys, loop->poly_right );
 956                   for( int l=0; l < poly_to_add->loop_total; l++ )
 957                   {
 958                      struct cxr_loop *loop1 = cxr_ab_ptr(&mesh->loops, poly_to_add->loop_start+l );
 959                      struct cxr_polygon *future_face = cxr_ab_ptr(&mesh->polys, loop1->poly_right );
 960
 961                      if( edge_tagged[ loop1->edge_index ] || loop1->poly_right == loop->poly_right )
 962                         goto IL_SKIP_SIMILAR_PLANES;
 963
 964                      for( int m=0; m<solid_len; m++ )
 965                         if( solid[m] == loop1->poly_right )
 966                            goto IL_SKIP_SIMILAR_PLANES;
 967
 968                      for( int m=0; m<solid_len; m++ )
 969                      {
 970                         struct cxr_polygon *polym = cxr_ab_ptr(&mesh->polys,solid[m]);
 971                         if( v3_dot( polym->normal, future_face->normal ) > 0.98500 )
 972                            goto IL_SKIP_PLANE_ADD;
 973                      }
 974
 975                      IL_SKIP_SIMILAR_PLANES:;
 976                   }
 977
 978                   // This plane passed all checks so we can add it to the current solid
 979
 980                   solid[ solid_len ++ ] = loop->poly_right;
 981                   faces_tagged[ loop->poly_right ] = i;
 982                   changed = 1;
 983                }
 984
 985                IL_SKIP_PLANE_ADD:;
 986             }
 987          }
 988       }
 989       search_start = solid_len;
 990       if(changed)
 991          goto IL_SEARCH_CONTINUE;
 992
 993       // Add entry
 994       struct csolid *csolid = &candidates[candidate_count ++];
 995       csolid->start = solid_buffer_len;
 996       csolid->count = solid_len;
 997       csolid->edge_count = 0;
 998
 999       v3_zero( csolid->center );
1000       for( int j=0; j<solid_len; j++ )
1001       {
1002          struct cxr_polygon *polyj = cxr_ab_ptr(&mesh->polys, solid[j]);
1003          v3_add( polyj->center, csolid->center, csolid->center );
1004          csolid->edge_count += polyj->loop_total;
1005       }
1006       v3_divs( csolid->center, solid_len, csolid->center );
1007
1008       solid_buffer_len += solid_len;
1009    }
1010
1011    // Create all candidates who have one or less non-manifolds edges
1012    //   Loop each candidate, determine the manifold, and pick the best one
1013
1014    struct csolid *best_solid = NULL;
1015    int fewest_manifold_splits = INT32_MAX;
1016
1017    struct cxr_loop *best_manifold = malloc( mesh->loops.count *sizeof(struct cxr_loop) );
1018    int *best_manifold_splits = malloc( mesh->loops.count *sizeof(int) );
1019    int best_manifold_len = 0;
1020    int max_solid_faces = 0;
1021
1022    int *edge_list = malloc( mesh->edges.count *sizeof(int) );
1023    int *edge_lefts = malloc( mesh->edges.count *sizeof(int) );
1024    struct cxr_loop *manifold = malloc(mesh->edges.count*2*sizeof(struct cxr_loop));
1025    int *splits = malloc(mesh->edges.count*2*sizeof(int));
1026
1027    for( int i=0; i<candidate_count; i++ )
1028    {
1029       struct csolid *solid = &candidates[i];
1030       max_solid_faces = cxr_max(max_solid_faces,solid->count);
1031
1032       if( solid->count <= 2 )
1033          continue;
1034
1035       int init_reverse = 0;
1036       int unique_edge_count = 0;
1037
1038       for( int j=0; j<solid->count; j++ )
1039       {
1040          struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys, solid_buffer[solid->start+j]);
1041
1042          for( int k=0; k<poly->loop_total; k++ )
1043          {
1044             struct cxr_loop *loop = cxr_ab_ptr(&mesh->loops, poly->loop_start+k);
1045
1046             for( int l=0; l<unique_edge_count; l++ )
1047                if( edge_list[l] == loop->edge_index )
1048                   goto IL_EDGE_ALREADY_PRESENT;
1049
1050             // Check if right edge references a polygon that is not
1051             // present inside the current solid candidate
1052             for( int l=0; l<solid->count; l++ )
1053                if( loop->poly_right == solid_buffer[solid->start+l] )
1054                   goto IL_EDGE_ALREADY_PRESENT;
1055
1056             edge_list[ unique_edge_count ] = loop->edge_index;
1057             edge_lefts[ unique_edge_count ] = loop->poly_left;
1058
1059             if( unique_edge_count == 0 )
1060             {
1061                struct cxr_edge *edgeptr = cxr_ab_ptr(&mesh->edges, loop->edge_index);
1062                if( edgeptr->i1 == loop->index )
1063                   init_reverse = 1;
1064             }
1065
1066             unique_edge_count ++;
1067             IL_EDGE_ALREADY_PRESENT:;
1068          }
1069       }
1070
1071       // This solid is already fully connected
1072       if( unique_edge_count == 0 )
1073          continue;
1074
1075       // Link edges together to create new manifold
1076       // Corners are created when two edges share a polygon face
1077       // This way we can split it into regions
1078
1079       for( int j=0; j<vert_buffer->count; j++ )
1080          vertex_tagged[j] = -1;
1081
1082       // Start with a loop edge which was tagged
1083       struct cxr_edge *current = cxr_ab_ptr(&mesh->edges, edge_list[0]);
1084
1085       int endpt = (!init_reverse)? current->i0: current->i1,
1086           start = endpt,
1087         curface = edge_lefts[0];
1088
1089       int manifold_len = 0;
1090       int split_count = 0;
1091
1092       IL_MANIFOLD_CONTINUE:
1093       for( int j=0; j<unique_edge_count; j++ )
1094       {
1095          struct cxr_edge *other = cxr_ab_ptr(&mesh->edges, edge_list[j]);
1096          if( other == current )
1097             continue;
1098
1099          if( other->i0 == endpt || other->i1 == endpt )
1100          {
1101             current = other;
1102             int lastpt = endpt;
1103
1104             if( other->i0 == endpt ) endpt = current->i1;
1105             else endpt = current->i0;
1106
1107             if( curface==edge_lefts[j] )
1108             {
1109                splits[ manifold_len ] = 1;
1110                split_count ++;
1111             }
1112             else
1113                splits[ manifold_len ] = 0;
1114
1115             // Append to intermidiary manifold
1116             manifold[ manifold_len ].edge_index = edge_list[j];
1117             manifold[ manifold_len ].poly_left = edge_lefts[j];
1118             manifold[ manifold_len ].index = lastpt;
1119             manifold[ manifold_len ].poly_right =
1120                polygon_edge_map[ edge_list[j]*2 ] == edge_lefts[j]?
1121                polygon_edge_map[ edge_list[j]*2+1 ]:
1122                polygon_edge_map[ edge_list[j]*2+0 ];
1123             manifold_len ++;
1124
1125             curface = edge_lefts[j];
1126
1127             if(endpt == start) goto IL_MANIFOLD_COMPLETE;
1128             goto IL_MANIFOLD_CONTINUE;
1129          }
1130       }
1131       cxr_log( "Failed to link manifold, count: %d\n", manifold_len );
1132
1133       for( int j=0; j<solid->count; j++ )
1134       {
1135          cxr_log( "p%d\n", solid_buffer[solid->start+j] );
1136          struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys, solid_buffer[solid->start+j]);
1137          cxr_debug_poly( mesh, poly, vertices, (v4f){0.2,0.0,0.0,1.0} );
1138       }
1139
1140       for( int j=0; j<unique_edge_count; j++ )
1141       {
1142          struct cxr_edge *uedge = cxr_ab_ptr(&mesh->edges, edge_list[j]);
1143          cxr_debug_line(vertices[uedge->i0],vertices[uedge->i1],(v4f){0.4,0.0,0.0,1.0});
1144       }
1145
1146       for( int j=0; j<manifold_len-1; j++ )
1147       {
1148          struct cxr_loop *lp0 = &manifold[j],
1149                          *lp1 = &manifold[cxr_range(j+1,manifold_len)];
1150
1151          cxr_debug_line(vertices[lp0->index],vertices[lp1->index], colour_error );
1152       }
1153
1154       cxr_debug_mesh( mesh, vertices, (v4f){0.0,0.0,0.0, 0.9} );
1155       *error = CXR_ERROR_BAD_MANIFOLD;
1156
1157       free(edge_list);
1158       free(edge_lefts);
1159       free(manifold);
1160       free(splits);
1161       free(edge_tagged);
1162       free(vertex_tagged);
1163       free(hot_edge);
1164       free(faces_tagged);
1165       free(solid_buffer);
1166       free(candidates);
1167       free(best_manifold);
1168       free(best_manifold_splits);
1169       free(polygon_edge_map);
1170       return NULL;
1171
1172       IL_MANIFOLD_COMPLETE:;
1173
1174       if( manifold_len < unique_edge_count )
1175          continue;
1176       else
1177       {
1178          if( split_count < fewest_manifold_splits )
1179          {
1180             fewest_manifold_splits = split_count;
1181             best_solid = solid;
1182
1183             for( int j=0; j<manifold_len; j++ )
1184             {
1185                best_manifold[j] = manifold[j];
1186                best_manifold_splits[j] = splits[j];
1187             }
1188             best_manifold_len = manifold_len;
1189          }
1190       }
1191    }
1192
1193    free(edge_list);
1194    free(edge_lefts);
1195    free(manifold);
1196    free(splits);
1197
1198    if( max_solid_faces < 2 )
1199    {
1200       *error = CXR_ERROR_NO_SOLIDS;
1201       free(edge_tagged);
1202       free(vertex_tagged);
1203       free(hot_edge);
1204       free(faces_tagged);
1205       free(solid_buffer);
1206       free(candidates);
1207       free(best_manifold);
1208       free(best_manifold_splits);
1209       free(polygon_edge_map);
1210       return NULL;
1211    }
1212
1213    if( best_solid != NULL )
1214    {
1215       struct cxr_mesh *pullmesh =
1216          cxr_alloc_mesh( best_solid->edge_count, best_solid->edge_count, best_solid->count );
1217
1218       // Add existing faces to pullsolid, and delete from main mesh
1219       for( int i=0; i<best_solid->count; i++ )
1220       {
1221          int nface_id = pullmesh->polys.count;
1222
1223          struct cxr_polygon *exist_face = cxr_ab_ptr(&mesh->polys, solid_buffer[best_solid->start+i]);
1224          struct cxr_polygon *new_face = cxr_ab_empty(&pullmesh->polys);
1225
1226          *new_face = *exist_face;
1227          new_face->loop_start = pullmesh->loops.count;
1228
1229          for( int j=0; j<exist_face->loop_total; j++ )
1230          {
1231             struct cxr_loop *exist_loop = cxr_ab_ptr(&mesh->loops, exist_face->loop_start+j);
1232             struct cxr_loop *new_loop = cxr_ab_empty(&pullmesh->loops);
1233
1234             new_loop->index = exist_loop->index;
1235             new_loop->poly_left = nface_id;
1236             new_loop->poly_right = -1;
1237             new_loop->edge_index = 0;
1238             v2_copy( exist_loop->uv, new_loop->uv );
1239          }
1240
1241          exist_face->loop_total = -1;
1242       }
1243
1244       // Split manifold up by unique planes if it has more than 1
1245       // otherwise, just use that face
1246       //
1247       // TODO: Need to build new manifold in sections, stably
1248       //       currently there is an unsupported case where the manifold splits
1249       //       are on located on an implicit face, causing 1-length manifolds.
1250
1251       int new_polys = 0;
1252       int pullmesh_new_start = pullmesh->polys.count;
1253
1254       if( fewest_manifold_splits != 0 )
1255       {
1256          #if CXR_MANIFOLD_DEBUG
1257          for( int i=0; i<best_manifold_len; i++ )
1258          {
1259             int i0 = i,
1260                 i1 = cxr_range(i+1,best_manifold_len);
1261
1262             cxr_debug_line( vertices[best_manifold[i0].index], vertices[best_manifold[i1].index], colour_error );
1263             if( best_manifold_splits[i] )
1264                cxr_debug_box( vertices[best_manifold[i0].index], 0.04, colour_success );
1265          }
1266          #endif
1267
1268          // This is a really strange observation, however it *seems* to apply to the kinds
1269          // of geometry we are dealing with. If the split count is odd, the manifold can be
1270          // created easily, no folding required.
1271          //
1272          // When it is even, it appears that internal implicit geometry is required, so we
1273          // need to fold the loops we create. Its really weird, but for some reason works on
1274          // the geometry rules we've defined.
1275          //   TODO: Find a well defined rule here.
1276
1277          int collapse_used_segments = (u32)fewest_manifold_splits & 0x1? 0: 1;
1278
1279          IL_MANIFOLD_BUILD_REPEAT:
1280
1281          for( int j=0; j<best_manifold_len; j++ )
1282          {
1283             if( best_manifold_splits[j] )
1284             {
1285                struct cxr_loop *loop = &best_manifold[j];
1286
1287                for( int k=1; k<best_manifold_len; k++ )
1288                {
1289                   int index1 = cxr_range(j+k,best_manifold_len);
1290                   struct cxr_loop *loop1 = &best_manifold[index1];
1291
1292                   if( best_manifold_splits[index1] )
1293                   {
1294                      if( k==1 )
1295                         break;
1296
1297                      new_polys ++;
1298
1299                      if( new_polys > best_manifold_len )
1300                      {
1301                         cxr_log( "Programming error: Too many new polys!\n" );
1302                         exit(1);
1303                      }
1304
1305                      cxr_create_poly( pullmesh, vertices, best_manifold, k+1, j, best_manifold_len );
1306
1307                      // Remove new section from manifold
1308                      if( collapse_used_segments )
1309                      {
1310                         best_manifold_splits[j] = 0;
1311                         best_manifold_splits[index1] = 0;
1312
1313                         int new_length = (best_manifold_len-(k-1));
1314
1315                         struct cxr_loop *new_manifold = malloc( new_length*sizeof(struct cxr_loop) );
1316                         int *new_manifold_splits = malloc( new_length*sizeof(int) );
1317
1318                         for( int l=0; l<new_length; l ++ )
1319                         {
1320                            int i_src = cxr_range( j+k+l, best_manifold_len );
1321                            new_manifold[l] = best_manifold[i_src];
1322                            new_manifold_splits[l] = best_manifold_splits[i_src];
1323                         }
1324
1325                         free( best_manifold );
1326                         free( best_manifold_splits );
1327                         best_manifold = new_manifold;
1328                         best_manifold_splits = new_manifold_splits;
1329
1330                         best_manifold_len = new_length;
1331
1332                         goto IL_MANIFOLD_BUILD_REPEAT;
1333                      }
1334
1335                      j=j+k-1;
1336                      break;
1337                   }
1338                }
1339             }
1340          }
1341
1342          if( best_manifold_len && collapse_used_segments )
1343          {
1344             cxr_create_poly( pullmesh, vertices, best_manifold, best_manifold_len, 0, best_manifold_len );
1345             new_polys ++;
1346          }
1347       }
1348       else
1349       {
1350          cxr_create_poly( pullmesh, vertices, best_manifold, best_manifold_len, 0, best_manifold_len );
1351          new_polys = 1;
1352       }
1353
1354       // vert_buffer may be reallocated by the next section of code,
1355       //             force a NULLref on vertices to catch any errors
1356       vertices = NULL;
1357
1358       // Implicit geometry reconstruction
1359       //   If there's 3 or more planes, collide them together to see if any new
1360       //   vertices need to be created on the mesh
1361       if( new_polys >= 3 )
1362       {
1363          for( int i=0; i<new_polys-2; i++ )
1364          {
1365             for( int j=i+1; j<new_polys-1; j++ )
1366             {
1367                for( int k=j+1; k<new_polys; k++ )
1368                {
1369                   struct cxr_polygon *ptri = cxr_ab_ptr( &pullmesh->polys, pullmesh_new_start+i ),
1370                                      *ptrj = cxr_ab_ptr( &pullmesh->polys, pullmesh_new_start+j ),
1371                                      *ptrk = cxr_ab_ptr( &pullmesh->polys, pullmesh_new_start+k );
1372
1373                   v4f planei, planej, planek;
1374                   normal_to_plane(ptri->normal,ptri->center,planei);
1375                   normal_to_plane(ptrj->normal,ptrj->center,planej);
1376                   normal_to_plane(ptrk->normal,ptrk->center,planek);
1377
1378                   v3f intersect;
1379
1380                   if( plane_intersect(planei,planej,planek,intersect) )
1381                   {
1382                      // cxr_debug_box( intersect, 0.05, colour_error );
1383
1384                      // Make sure this point is within the convex region, otherwise treat
1385                      // it as a degenerate case
1386
1387                      int point_valid = 1;
1388                      for( int l=0; l<pullmesh->polys.count; l++ )
1389                      {
1390                         struct cxr_polygon *ptrl = cxr_ab_ptr(&pullmesh->polys,l);
1391                         v4f planel;
1392
1393                         normal_to_plane(ptrl->normal, ptrl->center, planel);
1394
1395                         if( plane_polarity( planel, intersect ) > 0.01 )
1396                         {
1397                            cxr_log( "degen vert, planes %d, %d, %d [max:%d]\n", i,j,k, new_polys );
1398                            *error = CXR_ERROR_DEGEN_IMPLICIT;
1399
1400                            cxr_debug_poly( pullmesh, ptri, cxr_ab_ptr(vert_buffer,0), colours_random[3] );
1401                            cxr_debug_poly( pullmesh, ptrj, cxr_ab_ptr(vert_buffer,0), colours_random[1] );
1402                            cxr_debug_poly( pullmesh, ptrk, cxr_ab_ptr(vert_buffer,0), colours_random[2] );
1403
1404                            point_valid = 0;
1405                            break;
1406                         }
1407                      }
1408
1409                      if( !point_valid ) continue;
1410
1411                      // Extend faces to include this point
1412                      int nvertid = vert_buffer->count;
1413                      cxr_ab_push( vert_buffer, intersect );
1414
1415                      ptrj->loop_start += 1;
1416                      ptrk->loop_start += 2;
1417
1418                      cxr_ab_reserve(&pullmesh->loops, 3);
1419                      struct cxr_loop *lloopi = cxr_ab_empty_at(&pullmesh->loops, ptri->loop_start+ptri->loop_total),
1420                                      *lloopj = cxr_ab_empty_at(&pullmesh->loops, ptrj->loop_start+ptrj->loop_total),
1421                                      *lloopk = cxr_ab_empty_at(&pullmesh->loops, ptrk->loop_start+ptrk->loop_total);
1422
1423                      lloopi->index = nvertid;
1424                      lloopj->index = nvertid;
1425                      lloopk->index = nvertid;
1426                      lloopi->edge_index = 0; lloopj->edge_index = 0; lloopk->edge_index = 0;
1427                      lloopi->poly_left = pullmesh_new_start+i;
1428                      lloopj->poly_left = pullmesh_new_start+j;
1429                      lloopk->poly_left = pullmesh_new_start+k;
1430                      lloopi->poly_right = -1; lloopj->poly_right = -1; lloopk->poly_right = -1;
1431
1432                      v2_zero(lloopi->uv);
1433                      v2_zero(lloopj->uv);
1434                      v2_zero(lloopk->uv);
1435
1436                      ptri->loop_total ++;
1437                      ptrj->loop_total ++;
1438                      ptrk->loop_total ++;
1439
1440                      // Adjust centers of faces
1441                      v3_lerp( ptri->center, intersect, 1.0/(double)ptri->loop_total, ptri->center );
1442                      v3_lerp( ptrj->center, intersect, 1.0/(double)ptrj->loop_total, ptrj->center );
1443                      v3_lerp( ptrk->center, intersect, 1.0/(double)ptrk->loop_total, ptrk->center );
1444                   }
1445                }
1446             }
1447          }
1448       }
1449
1450       // Copy faces from pullsolid into orig mesh
1451
1452       for( int i=0; i<new_polys; i++ )
1453       {
1454          int rface_id = mesh->polys.count;
1455
1456          struct cxr_polygon *pface = cxr_ab_ptr(&pullmesh->polys,pullmesh_new_start+i);
1457          struct cxr_polygon *rip_face = cxr_ab_empty(&mesh->polys);
1458
1459          rip_face->loop_start = mesh->loops.count;
1460          rip_face->loop_total = pface->loop_total;
1461          rip_face->material_id = -1;
1462
1463          for( int j=0; j<rip_face->loop_total; j++ )
1464          {
1465             struct cxr_loop *ploop = cxr_ab_ptr(&pullmesh->loops, pface->loop_start+pface->loop_total-j-1),
1466                             *rloop = cxr_ab_empty(&mesh->loops);
1467
1468             rloop->index = ploop->index;
1469             rloop->poly_left = rface_id;
1470             rloop->poly_right = -1;
1471             rloop->edge_index = 0;
1472             v2_copy( ploop->uv, rloop->uv );
1473          }
1474
1475          v3_copy( pface->center, rip_face->center );
1476          v3_negate( pface->normal, rip_face->normal );
1477       }
1478
1479       cxr_mesh_clean_faces( mesh );
1480       cxr_mesh_clean_faces( pullmesh );
1481       cxr_mesh_clean_edges( mesh );
1482       cxr_mesh_clean_edges( pullmesh );
1483
1484       free(edge_tagged);
1485       free(vertex_tagged);
1486       free(hot_edge);
1487       free(faces_tagged);
1488       free(solid_buffer);
1489       free(candidates);
1490       free(best_manifold);
1491       free(best_manifold_splits);
1492       free(polygon_edge_map);
1493
1494       return pullmesh;
1495    }
1496
1497    free(edge_tagged);
1498    free(vertex_tagged);
1499    free(hot_edge);
1500    free(faces_tagged);
1501    free(solid_buffer);
1502    free(candidates);
1503    free(best_manifold);
1504    free(best_manifold_splits);
1505    free(polygon_edge_map);
1506
1507    return NULL;
1508 }
1509
1510 static struct cxr_mesh *cxr_to_internal_format(struct cxr_input_mesh *src, struct cxr_auto_buffer *abverts)
1511 {
1512    // Split mesh into islands
1513    struct cxr_mesh *mesh = cxr_alloc_mesh( src->edge_count, src->loop_count, src->poly_count );
1514    cxr_ab_init( abverts, sizeof(v3f), src->vertex_count );
1515
1516    // Copy input data into working mesh
1517    memcpy( cxr_ab_ptr( &mesh->edges, 0 ), src->edges, src->edge_count*sizeof(struct cxr_edge));
1518    memcpy( cxr_ab_ptr( &mesh->polys, 0 ), src->polys, src->poly_count*sizeof(struct cxr_polygon));
1519    memcpy( cxr_ab_ptr( abverts, 0 ), src->vertices, src->vertex_count*sizeof(v3f));
1520    mesh->edges.count = src->edge_count;
1521    mesh->loops.count = src->loop_count;
1522    mesh->polys.count = src->poly_count;
1523
1524    for( int i=0; i<src->loop_count; i++ )
1525    {
1526       struct cxr_loop *lp = cxr_ab_ptr(&mesh->loops,i);
1527       lp->index = src->loops[i].index;
1528       lp->edge_index = src->loops[i].edge_index;
1529       v2_copy( src->loops[i].uv, lp->uv );
1530    }
1531
1532    abverts->count = src->vertex_count;
1533
1534    return mesh;
1535 }
1536
1537 // Find farthest dot product along direction
1538 static double support_distance( v3f verts[3], v3f dir, double coef )
1539 {
1540    return cxr_maxf
1541    (
1542       coef * v3_dot( verts[0], dir ),
1543       cxr_maxf
1544       (
1545          coef * v3_dot( verts[1], dir ),
1546          coef * v3_dot( verts[2], dir )
1547       )
1548    );
1549 }
1550
1551 // Main function
1552 static void cxr_calculate_axis(
1553    struct cxr_texinfo *transform,
1554    v3f verts[3],
1555    v2f uvs[3],
1556    v2f texture_res
1557    )
1558 {
1559    v2f tT, bT; // Tangent/bitangent pairs for UV space and world
1560    v3f tW, bW;
1561
1562    v2_sub( uvs[0], uvs[1], tT );
1563    v2_sub( uvs[2], uvs[1], bT );
1564    v3_sub( verts[0], verts[1], tW );
1565    v3_sub( verts[2], verts[1], bW );
1566
1567    // Use arbitrary projection if there is no UV
1568    if( v2_length( tT ) < 0.0001 || v2_length( bT ) < 0.0001 )
1569    {
1570       v3f uaxis, normal, vaxis;
1571
1572       v3_copy( tW, uaxis );
1573       v3_normalize( uaxis );
1574
1575       v3_cross( tW, bW, normal );
1576       v3_cross( normal, uaxis, vaxis );
1577       v3_normalize( vaxis );
1578
1579       v3_copy( uaxis, transform->uaxis );
1580       v3_copy( vaxis, transform->vaxis );
1581       v2_zero( transform->offset );
1582
1583       v2_div( (v2f){128.0, 128.0}, texture_res, transform->scale );
1584       return;
1585    }
1586
1587    // Detect if UV is reversed
1588    double winding = v2_cross( tT, bT ) >= 0.0f? 1.0f: -1.0f;
1589
1590    // UV projection reference
1591    v2f vY, vX;
1592    v2_muls((v2f){1,0}, winding, vX);
1593    v2_muls((v2f){0,1}, winding, vY);
1594
1595    // Reproject reference into world space, including skew
1596    v3f uaxis1, vaxis1;
1597
1598    v3_muls( tW, v2_cross(vX,bT) / v2_cross(bT,tT), uaxis1 );
1599    v3_muladds( uaxis1, bW, v2_cross(vX, tT) / v2_cross(tT,bT), uaxis1 );
1600
1601    v3_muls( tW, v2_cross(vY,bT) / v2_cross(bT,tT), vaxis1 );
1602    v3_muladds( vaxis1, bW, v2_cross(vY,tT) / v2_cross(tT,bT), vaxis1 );
1603
1604    v3_normalize( uaxis1 );
1605    v3_normalize( vaxis1 );
1606
1607    // Apply source transform to axis (yes, they also need to be swapped)
1608    v3f norm, uaxis, vaxis;
1609
1610    v3_cross( bW, tW, norm );
1611    v3_normalize(norm);
1612    v3_cross( vaxis1, norm, uaxis );
1613    v3_cross( uaxis1, norm, vaxis );
1614
1615    // real UV scale
1616    v2f uvmin, uvmax, uvdelta;
1617    v2_minv( uvs[0], uvs[1], uvmin );
1618    v2_minv( uvmin, uvs[2], uvmin );
1619    v2_maxv( uvs[0], uvs[1], uvmax );
1620    v2_maxv( uvmax, uvs[2], uvmax );
1621
1622    v2_sub( uvmax, uvmin, uvdelta );
1623
1624    // world-uv scale
1625    v2f uvminw, uvmaxw, uvdeltaw;
1626    uvminw[0] = -support_distance( verts, uaxis, -1.0f );
1627    uvmaxw[0] =  support_distance( verts, uaxis,  1.0f );
1628    uvminw[1] = -support_distance( verts, vaxis, -1.0f );
1629    uvmaxw[1] =  support_distance( verts, vaxis,  1.0f );
1630
1631    v2_sub( uvmaxw, uvminw, uvdeltaw );
1632
1633    // VMf uv scale
1634    v2f uv_scale;
1635    v2_div( uvdeltaw, uvdelta, uv_scale );
1636    v2_div( uv_scale, texture_res, uv_scale );
1637
1638    // Find offset via 'natural' point
1639    v2f target_uv, natural_uv, tex_offset;
1640    v2_mul( uvs[0], texture_res, target_uv );
1641
1642    natural_uv[0] =  v3_dot( uaxis, verts[0] );
1643    natural_uv[1] = -v3_dot( vaxis, verts[0] );
1644    v2_div( natural_uv, uv_scale, natural_uv );
1645
1646    tex_offset[0] =   target_uv[0]-natural_uv[0];
1647    tex_offset[1] = -(target_uv[1]-natural_uv[1]);
1648
1649    // Copy everything into output
1650    v3_copy( uaxis, transform->uaxis );
1651    v3_copy( vaxis, transform->vaxis );
1652    v2_copy( tex_offset, transform->offset );
1653    v2_copy( uv_scale, transform->scale );
1654 }
1655
1656 CXR_API struct cxr_input_mesh *cxr_decompose(struct cxr_input_mesh *src)
1657 {
1658 #ifdef CXR_DEBUG_WRITE_MESH
1659    FILE *yeet = fopen( "/home/harry/Documents/blender_addons_remote/addons/convexer/solid.h", "w" );
1660
1661    fprintf( yeet, "v3f test_verts[] = {\n" );
1662    for( int i=0; i<src->vertex_count; i ++ )
1663    {
1664       fprintf( yeet, "   { %f, %f, %f },\n",
1665             src->vertices[i][0],
1666             src->vertices[i][1],
1667             src->vertices[i][2] );
1668    }
1669    fprintf( yeet, "};\n" );
1670
1671    fprintf( yeet, "struct cxr_input_loop test_loops[] = {\n" );
1672    for( int i=0; i<src->loop_count; i ++ )
1673    {
1674       fprintf( yeet, "   {%d, %d},\n",
1675          src->loops[i].index,
1676          src->loops[i].edge_index);
1677    }
1678    fprintf( yeet, "};\n" );
1679
1680    fprintf( yeet, "struct cxr_polygon test_polys[] = {\n" );
1681    for( int i=0; i <src->poly_count; i++ )
1682    {
1683       fprintf( yeet, "   {%d, %d, {%f, %f, %f}, {%f, %f, %f}},\n",
1684          src->polys[i].loop_start,
1685          src->polys[i].loop_total,
1686          src->polys[i].normal[0],
1687          src->polys[i].normal[1],
1688          src->polys[i].normal[2],
1689          src->polys[i].center[0],
1690          src->polys[i].center[1],
1691          src->polys[i].center[2] );
1692    }
1693    fprintf( yeet, "};\n" );
1694
1695    fprintf( yeet, "struct cxr_edge test_edges[] = {\n" );
1696    for( int i=0; i<src->edge_count; i++ )
1697    {
1698       fprintf( yeet, "   {%d, %d},\n",
1699          src->edges[i].i0,
1700          src->edges[i].i1
1701       );
1702    }
1703    fprintf( yeet, "};\n" );
1704
1705    fprintf( yeet, "struct cxr_input_mesh test_mesh = {\n" );
1706    fprintf( yeet, "   .vertices = test_verts,\n" );
1707    fprintf( yeet, "   .loops = test_loops,\n" );
1708    fprintf( yeet, "   .edges = test_edges,\n" );
1709    fprintf( yeet, "   .polys = test_polys,\n" );
1710    fprintf( yeet, "   .poly_count=%d,\n", src->poly_count );
1711    fprintf( yeet, "   .vertex_count=%d,\n", src->vertex_count );
1712    fprintf( yeet, "   .edge_count=%d,\n",src->edge_count );
1713    fprintf( yeet, "   .loop_count=%d\n", src->loop_count );
1714    fprintf( yeet, "};\n" );
1715
1716    fclose( yeet );
1717 #endif
1718
1719    struct cxr_auto_buffer abverts;
1720    struct cxr_mesh *main_mesh = cxr_to_internal_format( src, &abverts );
1721
1722    u32 error = 0x00;
1723
1724    struct cxr_auto_buffer solids;
1725    cxr_ab_init( &solids, sizeof(struct cxr_mesh *), 2 );
1726
1727    // TODO: Preprocessor stages
1728    //  - Split mesh up into islands before doing anything here
1729    //  - Snap vertices to grid (0.25u) ?
1730    while(1)
1731    {
1732       struct cxr_mesh *res = cxr_pull_best_solid( main_mesh, &abverts, 0, &error );
1733       if( res )
1734       {
1735          cxr_ab_push( &solids, &res );
1736          if( error ) break;
1737       }
1738       else
1739       {
1740          if( error )
1741          {
1742             // If no solids error we can rety while preserving 'hot' edges
1743
1744             if( error & CXR_ERROR_NO_SOLIDS )
1745             {
1746                error = 0x00;
1747                res = cxr_pull_best_solid(main_mesh, &abverts, 1, &error);
1748
1749                if( res ) cxr_ab_push( &solids, &res );
1750                else break;
1751
1752                if( error ) break;
1753             }
1754             else break;
1755          }
1756          else
1757             break;
1758       }
1759    }
1760
1761    cxr_ab_push( &solids, &main_mesh );
1762
1763    if( !error )
1764    {
1765       for( int i=0; i<solids.count; i++ )
1766       {
1767          struct cxr_mesh **mptr = cxr_ab_ptr(&solids,i);
1768          cxr_debug_mesh( *mptr, cxr_ab_ptr(&abverts,0), colours_random[cxr_range(i,8)] );
1769       }
1770    }
1771
1772    for( int i=0; i<solids.count; i++ )
1773    {
1774       struct cxr_mesh **mptr = cxr_ab_ptr(&solids,i);
1775       cxr_free_mesh( *mptr );
1776    }
1777
1778    cxr_ab_free( &abverts );
1779    cxr_ab_free( &solids );
1780
1781    return NULL;
1782 }
1783
1784 // Convert contiguous mesh to patch of displacments
1785 //
1786 static void cxr_write_disp(struct cxr_mesh *mesh, struct cxr_vdf *output,
1787    struct cxr_auto_buffer *abverts)
1788 {
1789    // Create a graph which maps vertices by their connections
1790    struct vertinfo
1791    {
1792       int con_start, con_count;     // Index into the connection graph
1793       int boundary,
1794           used,
1795           search,
1796           corner;
1797
1798       double alpha;
1799    }
1800    *vertinfo = malloc( sizeof(struct vertinfo)*abverts->count );
1801    int *graph = malloc( sizeof(int) * mesh->edges.count*2 );
1802
1803    int con_pos = 0;
1804    for( int i=0; i<abverts->count; i++ )
1805    {
1806       struct vertinfo *info = &vertinfo[i];
1807       info->con_start = con_pos;
1808       info->con_count = 0;
1809       info->boundary = 0;
1810       info->corner = 0;
1811       info->used = 0;
1812       info->search = 0;
1813       info->alpha = 0.0;
1814
1815       for( int j=0; j<mesh->edges.count; j++ )
1816       {
1817          struct cxr_edge *edge = cxr_ab_ptr(&mesh->edges,j);
1818
1819          if( edge->i0 == i || edge->i1 == i )
1820          {
1821             graph[ con_pos ++ ] = edge->i0 == i? edge->i1: edge->i0;
1822             info->con_count ++;
1823
1824             if( edge->freestyle )
1825                info->boundary = 1;
1826          }
1827       }
1828    }
1829
1830    // Find best normal for brush patch. VBSP uses the original brush
1831    // as reference for decal projection.
1832    //
1833    // These are clamped to be cardinal directions as to make the VMF somewhat
1834    // human editable.
1835
1836    v3f avg_normal;
1837
1838    for( int i=0; i<mesh->polys.count; i++ )
1839    {
1840       struct cxr_polygon *poly = cxr_ab_ptr( &mesh->polys, i );
1841       v3_add( poly->normal, avg_normal, avg_normal );
1842    }
1843    v3_divs( avg_normal, mesh->polys.count, avg_normal );
1844    v3_normalize( avg_normal );   // TODO: This can be zero length. Should add a safety check
1845                                  // normalize function that checks for small length before
1846                                  // carrying out, otherwise we get inf/nan values...
1847
1848    double component_max = fabs( avg_normal[2] );
1849    int component = 2;
1850
1851    for( int i=0; i<2; i++ )
1852    {
1853       if( fabs(avg_normal[i]) > component_max )
1854       {
1855          component_max = fabs(avg_normal[i]);
1856          component = i;
1857       }
1858    }
1859    double d = avg_normal[component] >= 0.0? 1.0: -1.0;
1860    v3_zero( avg_normal );
1861    avg_normal[component] = d;
1862
1863    // Approximately matching the area of the result brush faces to the actual area
1864    // this is to assign a 'best guess' amount of lightmap texels.
1865    //
1866    double uv_area = 0.0, face_area = 0.0, sf;
1867
1868    for( int i=0; i<mesh->polys.count; i++ )
1869    {
1870       struct cxr_polygon *poly = cxr_ab_ptr( &mesh->polys, i );
1871
1872       for( int j=0; j<poly->loop_total-2; j++ )
1873       {
1874          struct cxr_loop *lp0 = cxr_ab_ptr(&mesh->loops, poly->loop_start),
1875                          *lp1 = cxr_ab_ptr(&mesh->loops, poly->loop_start+j+1),
1876                          *lp2 = cxr_ab_ptr(&mesh->loops, poly->loop_start+j+2);
1877          v3f va, vb, orth;
1878          v3_sub( cxr_ab_ptr(abverts,lp1->index), cxr_ab_ptr(abverts,lp0->index), va );
1879          v3_sub( cxr_ab_ptr(abverts,lp2->index), cxr_ab_ptr(abverts,lp0->index), vb );
1880          v3_cross( va, vb, orth );
1881
1882          face_area += v3_length( orth ) / 2.0;
1883
1884          v2f uva, uvb;
1885          v2_sub( lp1->uv, lp0->uv, uva );
1886          v2_sub( lp2->uv, lp0->uv, uvb );
1887
1888          uv_area += fabs(v2_cross( uva, uvb )) / 2.0;
1889       }
1890    }
1891
1892    sf = sqrt( face_area / uv_area );
1893    int corner_count = 0;
1894
1895    // Vertex classification
1896    for( int i=0; i<abverts->count; i++ )
1897    {
1898       struct vertinfo *info = &vertinfo[i];
1899       if( !info->boundary ) continue;
1900
1901       int count = 0,
1902           non_manifold = 1;
1903
1904       for( int j=0; j<info->con_count; j++ )
1905       {
1906          int con = graph[info->con_start+j];
1907
1908          if( vertinfo[con].boundary )
1909             count ++;
1910          else
1911             non_manifold = 0;
1912       }
1913       if( count > 2 || non_manifold )
1914       {
1915          info->corner = 1;
1916          corner_count ++;
1917
1918          //cxr_debug_box( cxr_ab_ptr(abverts,i), 0.1, colour_success );
1919       }
1920    }
1921
1922    int dispedge[16];
1923    v2f corner_uvs[4];
1924    int dispedge_count;
1925    int disp_count = 0;
1926
1927    for( int i=0; i<mesh->polys.count; i++ )
1928    {
1929       struct cxr_polygon *basepoly = cxr_ab_ptr(&mesh->polys,i);
1930
1931       for( int h=0; h<basepoly->loop_total; h ++ )
1932       {
1933          int i0 = h,
1934              i1 = cxr_range(h+1,basepoly->loop_total);
1935
1936          struct cxr_loop *l0 = cxr_ab_ptr(&mesh->loops, basepoly->loop_start+i0),
1937                          *l1 = cxr_ab_ptr(&mesh->loops, basepoly->loop_start+i1);
1938          struct vertinfo *info = &vertinfo[ l0->index ];
1939
1940          if( info->corner )
1941          {
1942             int corner_count = 1;
1943
1944             dispedge_count = 2;
1945             dispedge[0] = l0->index;
1946             dispedge[1] = l1->index;
1947             v2_copy( l0->uv, corner_uvs[0] );
1948
1949             // Consume (remove) faces we use for corners
1950             basepoly->loop_total = -1;
1951
1952             cxr_debug_box( cxr_ab_ptr(abverts,l0->index),0.08,(v4f){0.0,0.0,1.0,1.0});
1953             disp_count ++;
1954
1955             // Collect edges
1956             // --------------------
1957
1958             while( dispedge_count < 17 )
1959             {
1960                struct vertinfo *edge_head = &vertinfo[dispedge[dispedge_count-1]];
1961                int newvert = 0;
1962
1963                if( edge_head->corner )
1964                {
1965                   // Find a polygon that has the edge C-1 -> C
1966                   for( int j=0; j<mesh->polys.count && !newvert; j++ )
1967                   {
1968                      struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys,j);
1969
1970                      for( int k=0; k<poly->loop_total; k ++ )
1971                      {
1972                         int i0 = k,
1973                             i1 = cxr_range(k+1,poly->loop_total);
1974
1975                         struct cxr_loop *l0 = cxr_ab_ptr(&mesh->loops, poly->loop_start+i0),
1976                                         *l1 = cxr_ab_ptr(&mesh->loops, poly->loop_start+i1);
1977
1978                         if( l0->index == dispedge[dispedge_count-2] &&
1979                             l1->index == dispedge[dispedge_count-1] )
1980                         {
1981                            // Take the vertex after that edge
1982                            v2_copy( l1->uv, corner_uvs[corner_count ++] );
1983
1984                            int i2 = cxr_range(i1+1,poly->loop_total);
1985                            struct cxr_loop *l2 = cxr_ab_ptr(&mesh->loops, poly->loop_start+i2);
1986
1987                            dispedge[dispedge_count ++] = l2->index;
1988                            newvert = 1;
1989                            poly->loop_total = -1;
1990                            break;
1991                         }
1992                      }
1993                   }
1994                }
1995                else
1996                {
1997                   for( int j=0; j<edge_head->con_count; j++ )
1998                   {
1999                      int con = graph[edge_head->con_start+j];
2000
2001                      if( con == -1 )
2002                         continue;
2003
2004                      if( dispedge_count > 1 )
2005                         if( con == dispedge[dispedge_count-2] )
2006                            continue;
2007
2008                      struct vertinfo *coninfo = &vertinfo[con];
2009
2010                      if( !coninfo->boundary )
2011                         continue;
2012
2013                      cxr_debug_arrow( cxr_ab_ptr(abverts,dispedge[dispedge_count-1]),
2014                                       cxr_ab_ptr(abverts,con),
2015                                       (v3f){0,0,1},
2016                                       0.1,
2017                                       colour_success );
2018
2019                      dispedge[ dispedge_count ++ ] = con;
2020                      newvert = 1;
2021
2022                      break;
2023                   }
2024                }
2025
2026                if( !newvert )
2027                {
2028                   cxr_debug_box(cxr_ab_ptr(abverts,dispedge[dispedge_count-1]), 0.1, colour_error);
2029                   break;
2030                }
2031             }
2032
2033             // --------------------
2034             // Edges collected
2035
2036             v2f va, vb;
2037             v2_sub( corner_uvs[1], corner_uvs[0], va );
2038             v2_sub( corner_uvs[2], corner_uvs[0], vb );
2039
2040             if( v2_cross( va,vb ) < 0.0 )
2041                cxr_log( "Uv is flipped!\n" );
2042             else
2043                cxr_log( "Uv is normal\n" );
2044
2045             // Connect up the grid
2046             //
2047             //   0 1 2 3 4
2048             //  15 a b c d
2049             //  14 e f g h
2050             //  13 i j k l
2051             //  12 m n o p
2052             //
2053             //  Example: a := common unused vertex that is connected to
2054             //                by 1 and 15. Or y-1, and x-1 on the grid.
2055             //           g := c and f common vert ^
2056             //
2057             int grid[25];
2058
2059             for( int j=0; j<25; j++ ) grid[j] = 0;
2060             for( int j=0; j<5; j++ )
2061             {
2062                grid[j] = dispedge[j];
2063                vertinfo[dispedge[j]].used = 1;
2064             }
2065             for( int j=1; j<5; j++ )
2066             {
2067                grid[j*5] = dispedge[16-j];
2068                vertinfo[dispedge[16-j]].used = 1;
2069             }
2070
2071             for( int j=1; j<5; j++ )
2072             {
2073                for( int k=1; k<5; k++ )
2074                {
2075                   int s0 = grid[(j-1)*5+k],
2076                       s1 = grid[j*5+k-1];
2077
2078                   struct vertinfo *va = &vertinfo[s0],
2079                                   *vb = &vertinfo[s1];
2080
2081                   // Find a common vertex between s0 and s1
2082
2083                   for( int l=0; l<va->con_count; l ++ )
2084                   {
2085                      for( int m=0; m<vb->con_count; m ++ )
2086                      {
2087                         int cona = graph[va->con_start+l],
2088                             conb = graph[vb->con_start+m];
2089
2090                         if( vertinfo[cona].used || vertinfo[conb].used )
2091                            continue;
2092
2093                         if( cona == conb )
2094                         {
2095                            grid[ j*5+k ] = cona;
2096                            vertinfo[cona].used = 1;
2097
2098                            goto IL_MATCHED_DISP_INTERIOR_VERT;
2099                         }
2100                      }
2101                   }
2102
2103                   // Broken displacement
2104                   cxr_log( "Broken displacement!\n" );
2105                   free( graph );
2106                   free( vertinfo );
2107                   return;
2108
2109                   IL_MATCHED_DISP_INTERIOR_VERT:;
2110                }
2111             }
2112
2113             // Release grid
2114             for( int j=0; j<25; j++ )
2115                vertinfo[grid[j]].used = 0;
2116          }
2117       }
2118    }
2119
2120    cxr_log( "Disp count: %d\n", disp_count );
2121
2122    // Main loop
2123 #if 0
2124    int pool[25];
2125    for( int i=0; i<abverts->count; i++ )
2126    {
2127       struct vertinfo *info = &vertinfo[i];
2128       if( info->boundary || info->used )
2129          continue;
2130
2131       // Gather all vertices in this displacement
2132       int poolcount = 1,
2133           front_start = 0,
2134           front_count = 1;
2135       pool[0] = i;
2136       info->used = 1;
2137
2138       IL_GATHER_LOOP:;
2139
2140       int new_front_start = poolcount;
2141
2142       for( int j=0; j<front_count; j++ )
2143       {
2144          struct vertinfo *frontvert = &vertinfo[pool[front_start+j]];
2145
2146          for( int k=0; k<frontvert->con_count; k++ )
2147          {
2148             int conid = graph[frontvert->con_start+k];
2149             struct vertinfo *con = &vertinfo[conid];
2150
2151             if( frontvert->boundary && !con->boundary )
2152                continue;
2153
2154             if( con->used )
2155                continue;
2156
2157             if( poolcount == 25 )
2158                goto IL_DISP_ERROR_COUNT;
2159
2160             con->used = 1;
2161             pool[ poolcount ++ ] = conid;
2162          }
2163       }
2164
2165       if( poolcount > new_front_start )
2166       {
2167          front_start = new_front_start;
2168          front_count = poolcount-front_start;
2169
2170          goto IL_GATHER_LOOP;
2171       }
2172
2173       if( poolcount != 25 )
2174       {
2175 IL_DISP_ERROR_COUNT:
2176          for( int i=0; i<poolcount; i++ )
2177             cxr_debug_box( cxr_ab_ptr(abverts,pool[i]), 0.02, colour_error );
2178
2179          free(graph);
2180          free(vertinfo);
2181
2182          cxr_log("Invalid displacement (>25 verts)\n");
2183          return;
2184       }
2185
2186       int corners[4];
2187       int corner_count = 0;
2188       struct cxr_loop *cornerloops[4];
2189
2190       // Find corners, and get their loops (for uvs)
2191       // note: the mesh must be split where there is texture seams
2192       //       so that two different uv'd loops cant ref the same vertex
2193       //
2194       for( int j=0; j<poolcount; j++ )
2195       {
2196          if( vertinfo[pool[j]].corner )
2197          {
2198             if( corner_count == 4 )
2199             {
2200                corner_count = -1;
2201                break;
2202             }
2203
2204             corners[corner_count] = j;
2205
2206             // find loop that includes this vert
2207             for( int k=0; k<mesh->loops.count; k++ )
2208             {
2209                struct cxr_loop *lp = cxr_ab_ptr(&mesh->loops,k);
2210                if( lp->index == pool[j] )
2211                {
2212                   cornerloops[corner_count] = lp;
2213                   break;
2214                }
2215             }
2216
2217             corner_count ++;
2218          }
2219       }
2220
2221       if( corner_count !=4 )
2222       {
2223          free(graph);
2224          free(vertinfo);
2225          cxr_log( "Invalid displacement (!=4 corners)\n" );
2226          return;
2227       }
2228
2229       int pivot = corners[0];
2230    }
2231 #endif
2232
2233    free( graph );
2234    free( vertinfo );
2235 }
2236
2237 CXR_API i32 cxr_convert_mesh_to_vmf(struct cxr_input_mesh *src, struct cxr_vdf *output)
2238 {
2239    // Split mesh into islands
2240    struct cxr_auto_buffer abverts;
2241    struct cxr_mesh *main_mesh = cxr_to_internal_format(src, &abverts);
2242
2243    u32 error = 0x00;
2244
2245    struct solidinf
2246    {
2247       struct cxr_mesh *pmesh;
2248       int is_displacement;
2249    };
2250
2251    struct cxr_auto_buffer solids;
2252    cxr_ab_init( &solids, sizeof(struct solidinf), 2 );
2253
2254    // TODO: Preprocessor stages
2255    //  - Split mesh up into islands before doing anything here    (DONE)
2256    //  - Snap vertices to grid (0.25u)                            ?
2257
2258    // Preprocessor 1: Island seperation
2259    //  ---------------
2260
2261    while(1)
2262    {
2263       struct cxr_mesh *res = cxr_pull_island( main_mesh );
2264       if( res )
2265       {
2266          cxr_ab_push( &solids, &(struct solidinf){ res, 0 });
2267       }
2268       else break;
2269    }
2270    cxr_ab_push( &solids, &(struct solidinf){main_mesh,0} );
2271
2272    // Preprocessor 2: Displacement break-out
2273    //  ---------------
2274    for( int i=0; i<solids.count; i++ )
2275    {
2276       struct solidinf *pinf = cxr_ab_ptr(&solids,i);
2277
2278       for( int j=0; j<pinf->pmesh->polys.count; j++ )
2279       {
2280          struct cxr_polygon *poly = cxr_ab_ptr( &pinf->pmesh->polys, j );
2281
2282          for( int k=0; k<poly->loop_total; k++ )
2283          {
2284             struct cxr_loop *lp = cxr_ab_ptr( &pinf->pmesh->loops, poly->loop_start+k );
2285             struct cxr_edge *edge = cxr_ab_ptr( &pinf->pmesh->edges, lp->edge_index );
2286
2287             if( edge->freestyle )
2288                goto IL_SOLID_IS_DISPLACEMENT;
2289          }
2290       }
2291
2292       continue;
2293       IL_SOLID_IS_DISPLACEMENT:;
2294
2295       pinf->is_displacement = 1;
2296       cxr_write_disp( pinf->pmesh, output, &abverts );
2297    }
2298
2299    // Preprocessor 3: Breakup non-convex shapes into sub-solids
2300    //  ---------------
2301    int sources_count = solids.count;
2302
2303    for( int i=0; i<sources_count; i++ )
2304    {
2305       struct solidinf pinf = *(struct solidinf *)cxr_ab_ptr(&solids, i);
2306
2307       if( pinf.is_displacement )
2308          continue;
2309
2310       while(1)
2311       {
2312          struct cxr_mesh *res = cxr_pull_best_solid( pinf.pmesh, &abverts, 0, &error );
2313
2314          if( res )
2315          {
2316             cxr_ab_push( &solids, &(struct solidinf){res,0} );
2317             if( error )
2318                break;
2319          }
2320          else
2321          {
2322             if( error )
2323             {
2324                // If no solids error we can rety while preserving 'hot' edges
2325
2326                if( error & CXR_ERROR_NO_SOLIDS )
2327                {
2328                   error = 0x00;
2329                   res = cxr_pull_best_solid(pinf.pmesh, &abverts, 1, &error);
2330
2331                   if( res ) cxr_ab_push( &solids, &(struct solidinf){res,0} );
2332                   else break;
2333
2334                   if( error ) break;
2335                }
2336             }
2337             else
2338                break;
2339          }
2340       }
2341    }
2342
2343    if( cxr_settings.debug )
2344    {
2345       for( int i=0; i<solids.count; i++ )
2346       {
2347          struct solidinf *solid = cxr_ab_ptr(&solids,i);
2348
2349          if( !solid->is_displacement )
2350             cxr_debug_mesh( solid->pmesh, cxr_ab_ptr(&abverts,0), colours_random[cxr_range(i,8)] );
2351       }
2352    }
2353
2354    // Turn all those solids into VMF brushes
2355    // --------------------------------------
2356    for( int i=0; i<solids.count; i++ )
2357    {
2358       struct solidinf *solid = cxr_ab_ptr(&solids,i);
2359
2360       if( solid->is_displacement ) continue;
2361
2362       cxr_vdf_node( output, "solid" );
2363       cxr_vdf_ki32( output, "id", ++ cxr_context.brush_count );
2364
2365       for( int j=0; j<solid->pmesh->polys.count; j++ )
2366       {
2367          struct cxr_polygon *poly = cxr_ab_ptr( &solid->pmesh->polys, j );
2368          struct cxr_loop *ploops = cxr_ab_ptr(&solid->pmesh->loops, poly->loop_start);
2369          struct cxr_material *matptr =
2370             poly->material_id < 0 || src->material_count == 0?
2371                &cxr_nodraw:
2372                &src->materials[ poly->material_id ];
2373
2374          cxr_vdf_node( output, "side" );
2375          cxr_vdf_ki32( output, "id", ++ cxr_context.face_count );
2376
2377          v3f verts[3]; v2f uvs[3];
2378
2379          v3_muls( cxr_ab_ptr(&abverts, ploops[0].index), cxr_context.scale_factor, verts[0] );
2380          v3_muls( cxr_ab_ptr(&abverts, ploops[1].index), cxr_context.scale_factor, verts[1] );
2381          v3_muls( cxr_ab_ptr(&abverts, ploops[2].index), cxr_context.scale_factor, verts[2] );
2382          verts[0][2] += cxr_context.offset_z;
2383          verts[1][2] += cxr_context.offset_z;
2384          verts[2][2] += cxr_context.offset_z;
2385
2386          v2_copy( ploops[0].uv, uvs[0] );
2387          v2_copy( ploops[1].uv, uvs[1] );
2388          v2_copy( ploops[2].uv, uvs[2] );
2389
2390          cxr_vdf_plane( output, "plane", verts[2], verts[1], verts[0] );
2391          cxr_vdf_kv( output, "material", matptr->vmt_path );
2392
2393          struct cxr_texinfo trans;
2394          cxr_calculate_axis(&trans, verts, uvs, (double[2]){ matptr->res[0], matptr->res[1] });
2395
2396          cxr_vdf_kaxis(output, "uaxis", trans.uaxis, trans.offset[0], trans.scale[0]);
2397          cxr_vdf_kaxis(output, "vaxis", trans.vaxis, trans.offset[1], trans.scale[1]);
2398
2399          cxr_vdf_kdouble(output, "rotation", 0.0 );
2400          cxr_vdf_ki32(output, "lightmapscale", cxr_settings.lightmap_scale );
2401          cxr_vdf_ki32(output, "smoothing_groups", 0);
2402
2403          cxr_vdf_edon( output );
2404       }
2405
2406       cxr_vdf_node(output, "editor");
2407       cxr_vdf_colour255(output,"color", colours_random[cxr_range(cxr_context.brush_count,8)]);
2408       cxr_vdf_ki32(output,"visgroupshown",1);
2409       cxr_vdf_ki32(output,"visgroupautoshown",1);
2410       cxr_vdf_edon(output);
2411
2412       cxr_vdf_edon( output );
2413    }
2414
2415    for( int i=0; i<solids.count; i++ )
2416    {
2417       struct solidinf *solid = cxr_ab_ptr(&solids,i);
2418       cxr_free_mesh( solid->pmesh );
2419    }
2420
2421    cxr_ab_free( &abverts );
2422    cxr_ab_free( &solids );
2423    return 0;
2424 }
2425
2426
2427 CXR_API void cxr_set_log_function( void (*func)(const char *str) )
2428 {
2429    cxr_log_func = func;
2430 }
2431
2432 CXR_API void cxr_set_line_function( void (*func)(v3f p0, v3f p1, v4f colour) )
2433 {
2434    cxr_line_func = func;
2435 }
2436
2437 CXR_API void cxr_settings_update( struct cxr_settings *settings )
2438 {
2439    cxr_settings = *settings;
2440 }
2441
2442 // Valve copyright stuff probably maybe
2443 //  whatever, my previous copyright decleration ends here
2444 // ----------------------------------------------------------
2445
2446 #define HEADER_LUMPS            64
2447 #define  LUMP_WORLDLIGHTS  54
2448
2449 #pragma pack(push,1)
2450
2451 struct header
2452 {
2453    int        ident;
2454    int        version;
2455
2456    struct lump
2457    {
2458       int fileofs, filelen;
2459       int version;
2460
2461       char fourCC[4];
2462    }
2463    lumps[ HEADER_LUMPS ];
2464
2465    int        mapRevision;
2466 };
2467
2468 struct worldlight
2469 {
2470         float              origin[3];
2471         float              intensity[3];
2472         float              normal[3];
2473         float              shadow_cast_offset[3];
2474         int                     cluster;
2475         int         type;
2476    int                  style;
2477         float              stopdot;
2478         float              stopdot2;
2479         float           exponent;
2480         float           radius;
2481         float              constant_attn;
2482         float              linear_attn;
2483         float              quadratic_attn;
2484         int                     flags;
2485         int                     texinfo;
2486         int                     owner;
2487 };
2488 #pragma pack(pop)
2489
2490 // Utility for patching BSP tools to remove -1 distance lights (we set them
2491 //  like that, because we want these lights to go away)
2492 //
2493 //  Yes, there is no way to do this in hammer
2494 //  Yes, the distance KV is unused but still gets compiled to this lump
2495 //  No, Entities only compile will not do this for you
2496 //
2497 CXR_API int cxr_lightpatch_bsp( const char *path )
2498 {
2499    printf( "Lightpatch: %s\n", path );
2500
2501    FILE *fp = fopen( path, "r+b" );
2502
2503    if( !fp )
2504    {
2505       cxr_log( "Could not open BSP file for editing (r+b)\n" );
2506       return 0;
2507    }
2508
2509    // Read bsp
2510    struct header header;
2511    fread( &header, sizeof(struct header), 1, fp );
2512    struct lump *lump = &header.lumps[ LUMP_WORLDLIGHTS ];
2513
2514    // Read worldlight array
2515    struct worldlight *lights = malloc( lump->filelen );
2516    fseek( fp, lump->fileofs, SEEK_SET );
2517    fread( lights, lump->filelen, 1, fp );
2518
2519    // Remove all marked lights
2520    int light_count = lump->filelen / sizeof(struct worldlight);
2521    int new_count = 0;
2522
2523    for( int i = 0; i < light_count; i ++ )
2524       if( lights[i].radius >= 0.0f )
2525          lights[new_count++] = lights[i];
2526
2527    lump->filelen = new_count*sizeof(struct worldlight);
2528
2529    // Write changes
2530    fseek( fp, lump->fileofs, SEEK_SET );
2531    fwrite( lights, lump->filelen, 1, fp );
2532    fseek( fp, 0, SEEK_SET );
2533    fwrite( &header, sizeof(struct header), 1, fp );
2534    cxr_log( "removed %d marked lights\n", light_count-new_count );
2535
2536    fclose( fp );
2537    free( lights );
2538
2539    return 1;
2540 }