init

[convexer.git] / src / convexer.c

/*
                              CONVEXER v0.8

               A GNU/Linux-first Source1 Hammer replacement
                    built with Blender, for mapmakers

                  Copyright (C) 2022 Harry Godden (hgn)

   Features:
      - Brush decomposition into convex pieces for well defined geometry
      - Freely form displacements without limits
      - Build your entire map in Blender
      - Compile models and model groups easily
      - Light patch BSP files; remove unwanted realtime effects
      - Fastest VTF compressor (thanks to Richgel999 and stb)

   To come:
      - high quality level overviews automatically for CS:GO (csRadar)

   Program structure:

   File/folder       Lang     Purpose
   src/
     __init__.py     Python   Blender plugin interface
     convexer.c      C        Heavy lifting; brush decomp, mesh processing
     cxr_math.h      C        Vector maths and other handy things
     cxr_mem.h       C        Automatic resizing buffers
     nbvtf/
       nbvtf.h       C        VTF processing interface
       librgcx.h     C++      Rich Geldreich's DXT1/DXT5 compressors
       stb/          C        Sean Barrets image I/O
*/

#include <stdio.h>
#include <math.h>
#include <stdint.h>
#include <stdarg.h>
#include <stdlib.h>
#include <string.h>

const char *cxr_build_time = __DATE__ " @" __TIME__;

typedef uint8_t         u8;
typedef uint16_t        u16;
typedef uint32_t        u32;
typedef uint64_t        u64;
typedef int8_t  i8;
typedef int16_t         i16;
typedef int32_t         i32;
typedef int64_t         i64;

typedef unsigned int uint;

typedef double          v2f[2];
typedef double          v3f[3];
typedef double          v4f[4];
typedef v3f                     m3x3f[3];
typedef v3f                     m4x3f[4];
typedef v3f                     boxf[2];

#define CXR_EPSILON 0.001
#define CXR_INTERIOR_ANGLE_MAX 0.998
#define CXR_API 
#define CXR_DIRTY_OPTIMISATION 1
#define CXR_DEBUG_WRITE_MESH 1
#define CXR_DEBUG_ALLOCATORS 1
#define CXR_MANIFOLD_DEBUG 0

#define CXR_ERROR_DEGEN_IMPLICIT 0x1
#define CXR_ERROR_BAD_MANIFOLD 0x2
#define CXR_ERROR_NO_SOLIDS 0x4

#include "cxr_math.h"
#include "cxr_mem.h"

// Utility
// ============================================

static v4f colours_random[] = 
{
   { 0.863, 0.078, 0.235, 0.4 },
   { 0.000, 0.980, 0.604, 0.4 },
   { 0.118, 0.565, 1.000, 0.4 },
   { 0.855, 0.439, 0.839, 0.4 },
   { 0.824, 0.412, 0.118, 0.4 },
   { 0.125, 0.698, 0.667, 0.4 },
   { 0.541, 0.169, 0.886, 0.4 },
   { 1.000, 0.843, 0.000, 0.4 }
};

static int cxr_range(int x, int bound)
{
   if( x < 0 )
      x += bound * (x/bound + 1);
   
   return x % bound;
}

struct cxr_input_mesh
{
   v3f *vertices;
   
   struct cxr_edge
   {
      i32 i0, i1;
   }
   *edges;

   struct cxr_input_loop
   {
      i32 index,
          edge_index;
      v2f uv;
   }
   *loops;

   struct cxr_polygon
   {
      i32 loop_start, loop_total;
      v3f normal;
      v3f center;
      i32 material_id;  // -1: interior material
   }
   *polys;
   
   struct cxr_material
   {
      i32 res[2];
      const char *vmt_path;
   }
   *materials;

   i32 poly_count,
       vertex_count,
       edge_count,
       loop_count,
       material_count;
};

struct cxr_loop
{
   i32 poly_left,
       poly_right,
       edge_index,
       index;
   v2f uv;
};

struct cxr_solid
{
   i32 *polygons;
};

struct cxr_mesh
{
   struct cxr_auto_buffer
      edges,
      loops,
      polys;
};

struct cxr_texinfo
{
   v3f uaxis, vaxis;
   v2f offset, scale;
};

// simple VDF writing interface
struct cxr_vdf
{
   FILE *fp;
   i32 level;
};

static struct cxr_settings
{
   i32 debug,
       lightmap_scale;

   double light_scale;
}
cxr_settings = {
   .debug = 0,
   .lightmap_scale = 12,

   .light_scale = 1.0/5.0
};

static struct cxr_context
{
   i32 brush_count,
       entity_count,
       face_count;

   double scale_factor;
   double offset_z;
}
cxr_context = {
   .brush_count = 0,
   .entity_count = 0,
   .face_count = 0,
   .scale_factor = 32.0,
   .offset_z = 0.0
};

static struct cxr_material cxr_nodraw = {
   .res = { 512, 512 },
   .vmt_path = "tools/toolsnodraw"
};

// Debugging callbacks
// =============================================================================

static v4f colour_error = { 1.0f, 0.0f, 0.0f, 1.0f };
static v4f colour_face_graph = { 1.0f, 1.0f, 1.0f, 0.03f };
static v4f colour_success = { 0.0f, 1.0f, 0.0f, 1.0f };

static void (*cxr_log_func)(const char *str);
static void (*cxr_line_func)( v3f p0, v3f p1, v4f colour );

static void cxr_log( const char *fmt, ... )
{
   char buf[512];

   va_list args;
   va_start( args, fmt );
   vsnprintf( buf, sizeof(buf)-1, fmt, args );
   va_end(args);

   if( cxr_log_func )
      cxr_log_func( buf );

   fputs(buf,stdout);
}

static void cxr_debug_line( v3f p0, v3f p1, v4f colour )
{
   if( cxr_line_func )
      cxr_line_func( p0, p1, colour );
}

static void cxr_debug_box( v3f p0, double sz, v4f colour )
{
   v3f a,b,c,d,
       a1,b1,c1,d1;
   v3_add(p0, (v3f){-sz,-sz,-sz}, a);
   v3_add(p0, (v3f){-sz, sz,-sz}, b);
   v3_add(p0, (v3f){ sz, sz,-sz}, c);
   v3_add(p0, (v3f){ sz,-sz,-sz}, d);
   v3_add(p0, (v3f){-sz,-sz,sz}, a1);
   v3_add(p0, (v3f){-sz, sz,sz}, b1);
   v3_add(p0, (v3f){ sz, sz,sz}, c1);
   v3_add(p0, (v3f){ sz,-sz,sz}, d1);

   cxr_debug_line( a,b, colour );
   cxr_debug_line( b,c, colour );
   cxr_debug_line( c,d, colour );
   cxr_debug_line( d,a, colour );
   cxr_debug_line( a1,b1, colour );
   cxr_debug_line( b1,c1, colour );
   cxr_debug_line( c1,d1, colour );
   cxr_debug_line( d1,a1, colour );
   cxr_debug_line( a,a1, colour );
   cxr_debug_line( b,b1, colour );
   cxr_debug_line( c,c1, colour );
   cxr_debug_line( d,d1, colour );
}

static void cxr_debug_arrow( v3f p0, v3f p1, v3f normal, double sz, v4f colour )
{
   v3f dir, tan, p2, p3;
   v3_sub(p1,p0,dir);
   v3_normalize(dir);

   v3_cross(dir,normal,tan);
   v3_muladds( p1,dir, -sz, p2 );
   v3_muladds( p2,tan,sz,p3 );
   cxr_debug_line( p1, p3, colour );
   v3_muladds( p2,tan,-sz,p3 );
   cxr_debug_line( p1, p3, colour );
   cxr_debug_line( p0, p1, colour );
}

// Public API
// =========================================================================

CXR_API void cxr_context_reset(void)
{
   cxr_context.brush_count = 0;
   cxr_context.entity_count = 0;
   cxr_context.face_count = 0;
   cxr_context.offset_z = 0.0;
   cxr_context.scale_factor = 32.0;
}

CXR_API void cxr_set_offset(double offset)
{
   cxr_context.offset_z = offset;
}

CXR_API void cxr_set_scale_factor(double scale)
{
   cxr_context.scale_factor = scale;
}

CXR_API struct cxr_vdf *cxr_vdf_open(const char *path)
{
   struct cxr_vdf *vdf = malloc(sizeof(struct cxr_vdf));

   vdf->level = 0;
   vdf->fp = fopen( path, "w" );

   if( !vdf->fp )
   {
      free( vdf );
      return NULL;
   }

   return vdf;
}

CXR_API void cxr_vdf_close(struct cxr_vdf *vdf)
{
   fclose( vdf->fp );
}

CXR_API void cxr_vdf_put(struct cxr_vdf *vdf, const char *str)
{
   for( int i=0; i<vdf->level; i++ )
      fputs( " ", vdf->fp );

   fputs( str, vdf->fp );
}

static void cxr_vdf_printf( struct cxr_vdf *vdf, const char *fmt, ... )
{
   cxr_vdf_put(vdf,"");

   va_list args;
   va_start( args, fmt );
   vfprintf( vdf->fp, fmt, args );
   va_end(args);
}

CXR_API void cxr_vdf_node(struct cxr_vdf *vdf, const char *str)
{
   cxr_vdf_put( vdf, str );
   putc( (u8)'\n', vdf->fp );
   cxr_vdf_put( vdf, "{\n" );

   vdf->level ++;
}

CXR_API void cxr_vdf_edon(struct cxr_vdf *vdf)
{
   vdf->level --;
   cxr_vdf_put( vdf, "}\n" );
}

CXR_API void cxr_vdf_kv(struct cxr_vdf *vdf, const char *strk, const char *strv)
{
   cxr_vdf_printf( vdf, "\"%s\" \"%s\"\n", strk, strv );
}

static void cxr_vdf_ki32(struct cxr_vdf *vdf, const char *strk, i32 val)
{
   cxr_vdf_printf( vdf, "\"%s\" \"%d\"\n", strk, val );
}
static void cxr_vdf_kdouble(struct cxr_vdf *vdf, const char *strk, double val)
{
   cxr_vdf_printf( vdf, "\"%s\" \"%f\"\n", strk, val );
}
static void cxr_vdf_kaxis(struct cxr_vdf *vdf, const char *strk, v3f normal, double offset, double scale)
{
   cxr_vdf_printf( vdf, "\"%s\" \"[%f %f %f %f] %f\"\n", strk, normal[0],normal[1],normal[2],offset,scale );
}
static void cxr_vdf_plane(struct cxr_vdf *vdf, const char *strk, v3f a, v3f b, v3f c )
{
   cxr_vdf_printf( vdf, "\"%s\" \"(%f %f %f) (%f %f %f) (%f %f %f)\"\n",
         strk, a[0], a[1], a[2], b[0], b[1], b[2], c[0], c[1], c[2] );
}
static void cxr_vdf_colour255(struct cxr_vdf *vdf, const char *strk, v4f colour)
{
   v4f scale;
   v4_muls( colour, 255.0, scale );
   cxr_vdf_printf( vdf, "\"%s\" \"%d %d %d %d\"\n",strk,(int)scale[0], (int)scale[1], (int)scale[2], (int)scale[3]);
}

// Public API
// =========================================================================

static void cxr_debug_poly(struct cxr_mesh *mesh, struct cxr_polygon *poly, v3f *verts, v4f colour )
{
   for( int i=0; i<poly->loop_total; i++ )
   {
      struct cxr_loop *loop0 = cxr_ab_ptr(&mesh->loops,poly->loop_start+i),
                      *loop1 = cxr_ab_ptr(&mesh->loops,poly->loop_start+cxr_range(i+1,poly->loop_total));

      v3f p0, p1;
      
      v3_lerp( verts[loop0->index], poly->center, 0.02, p0 );
      v3_lerp( verts[loop1->index], poly->center, 0.02, p1 );

      cxr_debug_arrow( p0, p1, poly->normal, 0.05, colour );
   }

   v3f nrm0;
   v3_muladds( poly->center, poly->normal, 0.3, nrm0 );

   cxr_debug_line( poly->center, nrm0, colour );
}

static void cxr_debug_mesh(struct cxr_mesh *mesh, v3f *verts, v4f colour )
{
   for( int i=0; i<mesh->polys.count; i++ )
   {
      struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys,i);
      cxr_debug_poly( mesh, poly, verts, colour );
   }
}

static struct cxr_mesh *cxr_alloc_mesh(int edge_count, int loop_count, int poly_count )
{
   struct cxr_mesh *mesh = malloc(sizeof(struct cxr_mesh));
   cxr_ab_init(&mesh->edges, sizeof(struct cxr_edge), edge_count);
   cxr_ab_init(&mesh->loops, sizeof(struct cxr_loop), loop_count);
   cxr_ab_init(&mesh->polys, sizeof(struct cxr_polygon), poly_count);
   return mesh;
}

static void cxr_free_mesh(struct cxr_mesh *mesh)
{
   cxr_ab_free(&mesh->edges);
   cxr_ab_free(&mesh->loops);
   cxr_ab_free(&mesh->polys);
   free(mesh);
}

// Rebuilds edge data and reallocates
//
static void cxr_mesh_clean_edges(struct cxr_mesh *mesh)
{
   struct cxr_auto_buffer new_edges;
   cxr_ab_init( &new_edges, sizeof(struct cxr_edge), mesh->edges.count );

   for( int i=0; i<mesh->polys.count; i++ )
   {
      struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys,i);
      for( int j=0; j<poly->loop_total; j++ )
      {
         struct cxr_loop
            *lp0 = cxr_ab_ptr(&mesh->loops,poly->loop_start+j),
            *lp1 = cxr_ab_ptr(&mesh->loops,poly->loop_start+cxr_range(j+1,poly->loop_total));
         
         int i0 = cxr_min(lp0->index, lp1->index),
             i1 = cxr_max(lp0->index, lp1->index);
         
         // See if edge exists before adding it
         for( int k=0; k<new_edges.count; k++ )
         {
            struct cxr_edge *edge = cxr_ab_ptr(&new_edges,k);

            if( edge->i0 == i0 && edge->i1 == i1 )
            {
               lp0->edge_index = k;
               goto IL_EDGE_CREATED;
            }
         }
         
         int orig_edge_id = lp0->edge_index;
         lp0->edge_index = new_edges.count;

         struct cxr_edge edge = { i0, i1 };
         // --- ! ---
         // Copy extra information (sharp,freestyle.. etc) here!
         //
         // if orig_edge_id < mesh->edges.count: edge.foo = mesh->edges[orig].foo
         // --- ! ---
         cxr_ab_push( &new_edges, &edge );

IL_EDGE_CREATED:;
      }
   }

   cxr_ab_free( &mesh->edges );
   mesh->edges = new_edges;
}

// Remove 0-length faces from mesh and correct loops
//
static void cxr_mesh_clean_faces(struct cxr_mesh *mesh)
{
   struct cxr_auto_buffer loops_new;
   cxr_ab_init( &loops_new, sizeof(struct cxr_loop), mesh->loops.count );

   int new_length=0;
   for( int i=0; i<mesh->polys.count; i++ )
   {
      struct cxr_polygon *src = cxr_ab_ptr(&mesh->polys,i),
                         *dst = cxr_ab_ptr(&mesh->polys,new_length);

      if( src->loop_total > 0 )
      {
         int src_start = src->loop_start,
             src_total = src->loop_total;

         *dst = *src;
         dst->loop_start = loops_new.count;
         
         for( int j=0; j<src_total; j++ )
         {
            struct cxr_loop *loop = cxr_ab_ptr(&mesh->loops,src_start+j),
                            *ldst = cxr_ab_ptr(&loops_new,dst->loop_start+j);
            *ldst = *loop;
            ldst->poly_left = new_length;
         }
         
         loops_new.count += src_total;
         new_length ++;
      }
   }

   cxr_ab_free( &mesh->loops );
   mesh->loops = loops_new;
   mesh->polys.count = new_length;
}

static i32 *cxr_mesh_link_loops(struct cxr_mesh *mesh)
{
   i32 *polygon_edge_map = malloc(mesh->edges.count*2 *sizeof(i32));

   for( int i = 0; i < mesh->edges.count*2; i ++ )
      polygon_edge_map[i] = -1;
   
   for( int i = 0; i < mesh->polys.count; i ++ )
   {
      struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys, i);

      for( int j = 0; j < poly->loop_total; j ++ )
      {
         struct cxr_loop *loop = cxr_ab_ptr(&mesh->loops, poly->loop_start+j);
         loop->poly_left = i;

         for( int k = 0; k < 2; k ++ )
         {
            i32 *edge = &polygon_edge_map[loop->edge_index*2+k];

            if( *edge == -1 )
            {
               *edge = i;
               break;
            }
         }
      }
   }
   for( int i = 0; i < mesh->polys.count; i ++ )
   {
      struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys,i);

      for( int j = 0; j < poly->loop_total; j ++ )
      {
         struct cxr_loop *loop = cxr_ab_ptr(&mesh->loops,poly->loop_start+j);

         i32 *face_map = &polygon_edge_map[loop->edge_index*2];

         if( face_map[0] == loop->poly_left ) loop->poly_right = face_map[1];
         else loop->poly_right = face_map[0];
      }
   }

   return polygon_edge_map;
}

// Add polygon to mesh based on loop array
static struct cxr_polygon *cxr_create_poly( struct cxr_mesh *mesh, v3f *vertices, struct cxr_loop poly[],
   int len, int start, int max )
{
   if( len < 3 )
   {
      cxr_log( "tried to add new poly with length %d!\n", len );
      
      if( len >= 2 )
      {
         for( int j=0; j<len; j++ )
         {
            int i0 = poly[j].index,
                i1 = poly[cxr_range(j+1,len)].index;
            cxr_debug_line( vertices[i0], vertices[i1], colour_error );
         }
      }

      return NULL;
   }

   int nface_id = mesh->polys.count;
   struct cxr_polygon *new_face = cxr_ab_empty(&mesh->polys);

   new_face->loop_start = mesh->loops.count;
   new_face->loop_total = len;
   new_face->material_id = -1;

   // Calculate normal and center
   v3_zero( new_face->center );

   for( int j=0; j<len; j++ )
   {
      int i0 = poly[cxr_range(start+j,max)].index;
      struct cxr_loop *new_loop = cxr_ab_empty(&mesh->loops);

      new_loop->poly_left = nface_id;
      new_loop->poly_right = -1;
      new_loop->index = i0;
      new_loop->edge_index = 0;
      v2_zero(new_loop->uv);

      v3_add( new_face->center, vertices[new_loop->index], new_face->center );
   }
   v3_divs( new_face->center, new_face->loop_total, new_face->center );
   
   struct cxr_loop *lp0 = cxr_ab_ptr( &mesh->loops, new_face->loop_start ),
                   *lp1 = cxr_ab_ptr( &mesh->loops, new_face->loop_start+1 ),
                   *lp2 = cxr_ab_ptr( &mesh->loops, new_face->loop_start+2 );
   
   tri_normal( vertices[lp0->index], vertices[lp1->index], vertices[lp2->index], new_face->normal );

   return cxr_ab_ptr(&mesh->polys, nface_id);
}

// Get the 'next' mesh island
//
// Returns NULL if there is only one island
static struct cxr_mesh *cxr_pull_island(struct cxr_mesh *mesh)
{
   free(cxr_mesh_link_loops(mesh));

   int *island_current = malloc(mesh->polys.count*sizeof(int)),
        island_len = 1,
        loop_count = 0,
        last_count;

   island_current[0] = 0;

   IL_ISLAND_REPEAT:
   last_count = island_len;

   for( int i=0; i<island_len; i++ )
   {
      struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys,island_current[i]);

      for( int j=0; j<poly->loop_total; j++ )
      {
         struct cxr_loop *loop = cxr_ab_ptr(&mesh->loops, poly->loop_start+j);

         if( loop->poly_right != -1 )
         {
            int face_present = 0;

            for( int k=0; k<island_len; k++ )
            {
               if( island_current[k] == loop->poly_right )
               {
                  face_present = 1;
                  break;
               }
            }

            if( !face_present )
            {
               island_current[ island_len ++ ] = loop->poly_right;
            }
         }
      }
   }

   if( island_len > last_count )
      goto IL_ISLAND_REPEAT;

   if( island_len == mesh->polys.count )
   {
      free( island_current );
      return NULL;
   }

   for( int i=0; i<island_len; i++ )
   {
      struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys, island_current[i]);
      loop_count += poly->loop_total;
   }

   struct cxr_mesh *newmesh = cxr_alloc_mesh( mesh->edges.count, loop_count, island_len );

   for( int i=0; i<island_len; i++ )
   {
      struct cxr_polygon *src = cxr_ab_ptr(&mesh->polys, island_current[i]);
      struct cxr_polygon *dst = cxr_ab_ptr(&newmesh->polys, i);
      
      *dst = *src;
      dst->loop_start = newmesh->loops.count;

      for( int j=0; j<src->loop_total; j++ )
      {
         struct cxr_loop *lsrc = cxr_ab_ptr(&mesh->loops, src->loop_start+j),
                         *ldst = cxr_ab_ptr(&newmesh->loops, dst->loop_start+j);

         *ldst = *lsrc;
         ldst->poly_left = i;
         ldst->poly_right = -1;
      }

      newmesh->loops.count += src->loop_total;
      src->loop_total = -1;
   }

   newmesh->polys.count = island_len;
   newmesh->edges.count = mesh->edges.count;
   memcpy(cxr_ab_ptr(&newmesh->edges,0), cxr_ab_ptr(&mesh->edges,0), mesh->edges.count*sizeof(struct cxr_edge));

   cxr_mesh_clean_faces(mesh);
   cxr_mesh_clean_edges(mesh);
   cxr_mesh_clean_edges(newmesh);
   free( island_current );

   return newmesh;
}

// Return best availible solid from mesh, and patch existing mesh to fill the gap
// creted by it. 
//
// Returns NULL if shape is already convex or empty
// Destroys edge data!
static struct cxr_mesh *cxr_pull_best_solid(
      struct cxr_mesh *mesh, 
      struct cxr_auto_buffer *vert_buffer, 
      int preserve_hot_edges,
      u32 *error )
{
   v3f *vertices = cxr_ab_ptr( vert_buffer, 0 );

   i32 *polygon_edge_map = cxr_mesh_link_loops(mesh);

   for( int i=0; i<mesh->edges.count*2; i++ )
      if( polygon_edge_map[i] == -1 )
      {
         cxr_log( "non-manifold edges are in the mesh; implicit internal geometry does not have full support\n" );
         free(polygon_edge_map);
         return NULL;
      }

   int *vertex_tagged = malloc( vert_buffer->count*sizeof(int) );
   int *edge_tagged = malloc( mesh->edges.count*sizeof(int) );
   
   for( int i=0; i<mesh->edges.count; i++ )
   {
      struct cxr_polygon *polya = cxr_ab_ptr(&mesh->polys, polygon_edge_map[i*2+0]),
                         *polyb = cxr_ab_ptr(&mesh->polys, polygon_edge_map[i*2+1]);
      v4f planeb;
      normal_to_plane(polyb->normal, polyb->center, planeb);
      
      edge_tagged[i] = 0;
      for( int j=0; j<polya->loop_total; j++ )
      {
         struct cxr_loop *loop = cxr_ab_ptr(&mesh->loops, polya->loop_start+j);
         if( plane_polarity( planeb, vertices[loop->index] ) > 0.001 ||
             v3_dot(polya->normal,polyb->normal) > 0.98500 )
         {
            edge_tagged[i] = 1;
            break;
         }
      }
   }

   // Tag 'reflex' vertices
   int *connected_planes = malloc(mesh->polys.count*sizeof(int));

   for( int i=0; i<vert_buffer->count; i++ )
   {
      vertex_tagged[i]=0;
      
      int num_connected = 0;
      // Create a list of polys that ref this vert
      for( int j=0; j<mesh->polys.count; j++ )
      {
         struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys,j);
         for( int k=0; k<poly->loop_total; k++ )
         {
            struct cxr_loop *loop = cxr_ab_ptr(&mesh->loops,poly->loop_start+k);
            if( loop->index == i )
            {
               connected_planes[num_connected ++] = j;
               break;
            }
         }
      }
      // Check all combinations for a similar normal
      for( int j=0; j<num_connected-1; j++ )
      {
         for( int k=j+1; k<num_connected; k++ )
         {
            struct cxr_polygon *polyj = cxr_ab_ptr(&mesh->polys,connected_planes[j]);
            struct cxr_polygon *polyk = cxr_ab_ptr(&mesh->polys,connected_planes[k]);

            if( v3_dot(polyj->normal, polyk->normal) > 0.98500 )
               goto IL_TAG_VERT;
         }
      }

      // Check if all connected planes not are:
      //   - bounded by other planes
      //   - or coplanar

      for( int j=0; j<num_connected; j++ )
         for( int k=j+1; k<num_connected; k++ )
         {
            struct cxr_polygon *jpoly = cxr_ab_ptr(&mesh->polys, connected_planes[j]),
                               *kpoly = cxr_ab_ptr(&mesh->polys, connected_planes[k]);
            v4f plane;
            normal_to_plane( kpoly->normal, kpoly->center, plane );
            for( int l=0; l<jpoly->loop_total; l++ )
            {
               struct cxr_loop *loop = cxr_ab_ptr(&mesh->loops, jpoly->loop_start+l);
               if( plane_polarity( plane, vertices[loop->index] ) > 0.001 )
                  goto IL_TAG_VERT;
            }
         }

      goto IL_TAG_NEXT_VERT;
IL_TAG_VERT: vertex_tagged[i] = 1;
IL_TAG_NEXT_VERT:;
   }

   free( connected_planes );

   // Connect all marked verts that share an edge
   //  - We must take care not to completely isolate
   //    a polygon with marked edges all around it
   
   int *hot_edge = malloc(mesh->edges.count*sizeof(int));
   for( int i=0; i< mesh->edges.count; i++ )
      hot_edge[i] = 0;

   for( int i=0; i<mesh->polys.count; i ++ )
   {
      struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys,i);
      int not_tagged = -1,
          tag_count = 0;

      for( int j=0; j<poly->loop_total; j++ )
      {
         struct cxr_loop *loop = cxr_ab_ptr(&mesh->loops, poly->loop_start+j);

         if( !edge_tagged[ loop->edge_index ] )
         {
            if( not_tagged == -1 )
               not_tagged = loop->edge_index;
            else
               goto IL_SKIP_NO_HOT_EDGE;
         }
      }
      
      if( not_tagged != -1 )
         hot_edge[not_tagged]=1;

      IL_SKIP_NO_HOT_EDGE:;
   }

   // Connect edges that have verts tagged, but is not a hot edge
   for( int i=0; i<mesh->edges.count; i ++ )
   {
      if( hot_edge[i] && preserve_hot_edges ) continue;

      struct cxr_edge *edge = cxr_ab_ptr(&mesh->edges,i);
      if( vertex_tagged[edge->i0] && vertex_tagged[edge->i1] )
         edge_tagged[i] = 1;
   }

   /* Debug stuff -- 
   for( int i=0; i<vertex_count; i++ )
      if( vertex_tagged[i] )
         cxr_debug_box( vertices[i], 0.03, (v4f){0.0,0.0,0.0,1.0});

   for( int i=0; i < mesh->edges.count; i++ )
   {
      struct cxr_edge *edge = cxr_ab_ptr( &mesh->edges, i );
      if( edge_tagged[i] )
         cxr_debug_line( vertices[ edge->i0 ], vertices[ edge->i1 ], (v4f){0.0,0.0,0.0,1.0});

      if( hot_edge[i] )
         cxr_debug_line( vertices[ edge->i0 ], vertices[ edge->i1 ], (v4f){0.0,1.0,1.0,1.0});
   }
   */

   // count regions
   int *faces_tagged = malloc(mesh->polys.count*sizeof(int));
   for( int i=0; i<mesh->polys.count; i++ )
      faces_tagged[i] = -1;
   
   int *solid_buffer = malloc( mesh->polys.count*sizeof(int) );
   int solid_buffer_len = 0;
   struct csolid
   {
      int start,count,edge_count;
      v3f center;
   }
   *candidates = malloc( mesh->polys.count *sizeof(struct csolid) );
   int candidate_count = 0;

   for( int i=0; i<mesh->polys.count; i++ )
   {
      if( faces_tagged[i] != -1 ) continue;
      faces_tagged[i] = i;
      
      int *solid = &solid_buffer[ solid_buffer_len ];
      int solid_len = 0;
      
      solid[solid_len++] = i;
      
      int search_start = 0;
      
      // Iterative search that connects regions of planes governed by rules:
      //   - edge can add other face if the edge has less than two reflexes
      //   - the face can no longer be used in future searches

   IL_SEARCH_CONTINUE:;

      int changed = 0;
      for( int j=search_start; j<solid_len; j++ )
      {
         struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys, solid[j]);

         for( int k=0; k<poly->loop_total; k++ )
         {
            struct cxr_loop *loop = cxr_ab_ptr(&mesh->loops, poly->loop_start+k);
            struct cxr_edge *edge = cxr_ab_ptr(&mesh->edges, loop->edge_index );

            if( faces_tagged[ loop->poly_right ] == -1 )
            {
               if( !edge_tagged[loop->edge_index] )
               {
                  // Need to look ahead 1 step to make sure he does not want
                  // to add any more planes that are coplanar with some of 
                  // our existing group
                  //
                  // TODO: is this unused due to hotedge improvements? leaving for safety...

                  struct cxr_polygon *poly_to_add = cxr_ab_ptr(&mesh->polys, loop->poly_right );
                  for( int l=0; l < poly_to_add->loop_total; l++ )
                  {
                     struct cxr_loop *loop1 = cxr_ab_ptr(&mesh->loops, poly_to_add->loop_start+l );
                     struct cxr_polygon *future_face = cxr_ab_ptr(&mesh->polys, loop1->poly_right );

                     if( edge_tagged[ loop1->edge_index ] || loop1->poly_right == loop->poly_right ) 
                        goto IL_SKIP_SIMILAR_PLANES;

                     for( int m=0; m<solid_len; m++ )
                        if( solid[m] == loop1->poly_right )
                           goto IL_SKIP_SIMILAR_PLANES;
                     
                     for( int m=0; m<solid_len; m++ )
                     {
                        struct cxr_polygon *polym = cxr_ab_ptr(&mesh->polys,solid[m]);
                        if( v3_dot( polym->normal, future_face->normal ) > 0.98500 )
                           goto IL_SKIP_PLANE_ADD;
                     }

                     IL_SKIP_SIMILAR_PLANES:;
                  }

                  // This plane passed all checks so we can add it to the current solid

                  solid[ solid_len ++ ] = loop->poly_right;
                  faces_tagged[ loop->poly_right ] = i;
                  changed = 1;
               }

               IL_SKIP_PLANE_ADD:;
            }
         }
      }
      search_start = solid_len;
      if(changed) 
         goto IL_SEARCH_CONTINUE;

      // Add entry
      struct csolid *csolid = &candidates[candidate_count ++];
      csolid->start = solid_buffer_len;
      csolid->count = solid_len;
      csolid->edge_count = 0;
      
      v3_zero( csolid->center );
      for( int j=0; j<solid_len; j++ )
      {
         struct cxr_polygon *polyj = cxr_ab_ptr(&mesh->polys, solid[j]);
         v3_add( polyj->center, csolid->center, csolid->center );
         csolid->edge_count += polyj->loop_total;
      }
      v3_divs( csolid->center, solid_len, csolid->center );

      solid_buffer_len += solid_len;
   }

   // Create all candidates who have one or less non-manifolds edges
   //   Loop each candidate, determine the manifold, and pick the best one

   struct csolid *best_solid = NULL;
   int fewest_manifold_splits = INT32_MAX;

   struct cxr_loop *best_manifold = malloc( mesh->loops.count *sizeof(struct cxr_loop) );
   int *best_manifold_splits = malloc( mesh->loops.count *sizeof(int) );
   int best_manifold_len = 0;
   int max_solid_faces = 0;

   int *edge_list = malloc( mesh->edges.count *sizeof(int) );
   int *edge_lefts = malloc( mesh->edges.count *sizeof(int) );
   struct cxr_loop *manifold = malloc(mesh->edges.count*2*sizeof(struct cxr_loop));
   int *splits = malloc(mesh->edges.count*2*sizeof(int));

   for( int i=0; i<candidate_count; i++ )
   {
      struct csolid *solid = &candidates[i];
      max_solid_faces = cxr_max(max_solid_faces,solid->count);

      if( solid->count <= 2 )
         continue;

      int init_reverse = 0;
      int unique_edge_count = 0;

      for( int j=0; j<solid->count; j++ )
      {
         struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys, solid_buffer[solid->start+j]);

         for( int k=0; k<poly->loop_total; k++ )
         {
            struct cxr_loop *loop = cxr_ab_ptr(&mesh->loops, poly->loop_start+k);

            for( int l=0; l<unique_edge_count; l++ )
               if( edge_list[l] == loop->edge_index )
                  goto IL_EDGE_ALREADY_PRESENT;

            // Check if right edge references a polygon that is not 
            // present inside the current solid candidate
            for( int l=0; l<solid->count; l++ )
               if( loop->poly_right == solid_buffer[solid->start+l] )
                  goto IL_EDGE_ALREADY_PRESENT;
            
            edge_list[ unique_edge_count ] = loop->edge_index;
            edge_lefts[ unique_edge_count ] = loop->poly_left;

            if( unique_edge_count == 0 )
            {
               struct cxr_edge *edgeptr = cxr_ab_ptr(&mesh->edges, loop->edge_index);
               if( edgeptr->i1 == loop->index )
                  init_reverse = 1;
            }

            unique_edge_count ++;
            IL_EDGE_ALREADY_PRESENT:;
         }
      }
      
      // This solid is already fully connected
      if( unique_edge_count == 0 )
         continue;
      
      // Link edges together to create new manifold
      // Corners are created when two edges share a polygon face
      // This way we can split it into regions
      
      for( int j=0; j<vert_buffer->count; j++ )
         vertex_tagged[j] = -1;
      
      // Start with a loop edge which was tagged
      struct cxr_edge *current = cxr_ab_ptr(&mesh->edges, edge_list[0]);

      int endpt = (!init_reverse)? current->i0: current->i1,
          start = endpt,
        curface = edge_lefts[0];

      int manifold_len = 0;
      int split_count = 0;

      IL_MANIFOLD_CONTINUE:
      for( int j=0; j<unique_edge_count; j++ )
      {
         struct cxr_edge *other = cxr_ab_ptr(&mesh->edges, edge_list[j]);
         if( other == current )
            continue;

         if( other->i0 == endpt || other->i1 == endpt )
         {
            current = other;
            int lastpt = endpt;

            if( other->i0 == endpt ) endpt = current->i1;
            else endpt = current->i0;
            
            if( curface==edge_lefts[j] )
            {
               splits[ manifold_len ] = 1;
               split_count ++;
            }
            else
               splits[ manifold_len ] = 0;
            
            // Append to intermidiary manifold
            manifold[ manifold_len ].edge_index = edge_list[j];
            manifold[ manifold_len ].poly_left = edge_lefts[j];
            manifold[ manifold_len ].index = lastpt;
            manifold[ manifold_len ].poly_right = 
               polygon_edge_map[ edge_list[j]*2 ] == edge_lefts[j]?
               polygon_edge_map[ edge_list[j]*2+1 ]:
               polygon_edge_map[ edge_list[j]*2+0 ];
            manifold_len ++;

            curface = edge_lefts[j];

            if(endpt == start) goto IL_MANIFOLD_COMPLETE;
            goto IL_MANIFOLD_CONTINUE;
         }
      }
      cxr_log( "Failed to link manifold, count: %d\n", manifold_len );
      
      for( int j=0; j<solid->count; j++ )
      {
         cxr_log( "p%d\n", solid_buffer[solid->start+j] );
         struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys, solid_buffer[solid->start+j]);
         cxr_debug_poly( mesh, poly, vertices, (v4f){0.2,0.0,0.0,1.0} );
      }

      for( int j=0; j<unique_edge_count; j++ )
      {
         struct cxr_edge *uedge = cxr_ab_ptr(&mesh->edges, edge_list[j]);
         cxr_debug_line(vertices[uedge->i0],vertices[uedge->i1],(v4f){0.4,0.0,0.0,1.0});
      }

      for( int j=0; j<manifold_len-1; j++ )
      {
         struct cxr_loop *lp0 = &manifold[j],
                         *lp1 = &manifold[cxr_range(j+1,manifold_len)];

         cxr_debug_line(vertices[lp0->index],vertices[lp1->index], colour_error );
      }

      cxr_debug_mesh( mesh, vertices, (v4f){0.0,0.0,0.0, 0.9} );
      *error = CXR_ERROR_BAD_MANIFOLD;

      free(edge_list);
      free(edge_lefts);
      free(manifold);
      free(splits);
      free(edge_tagged);
      free(vertex_tagged);
      free(hot_edge);
      free(faces_tagged);
      free(solid_buffer);
      free(candidates);
      free(best_manifold);
      free(best_manifold_splits);
      free(polygon_edge_map);
      return NULL;

      IL_MANIFOLD_COMPLETE:;
      
      if( manifold_len < unique_edge_count )
         continue;
      else
      {
         if( split_count < fewest_manifold_splits )
         {
            fewest_manifold_splits = split_count;
            best_solid = solid;

            for( int j=0; j<manifold_len; j++ )
            {
               best_manifold[j] = manifold[j];
               best_manifold_splits[j] = splits[j];
            }
            best_manifold_len = manifold_len;
         }
      }
   }

   free(edge_list);
   free(edge_lefts);
   free(manifold);
   free(splits);

   if( max_solid_faces < 2 )
   {
      *error = CXR_ERROR_NO_SOLIDS;
      free(edge_tagged);
      free(vertex_tagged);
      free(hot_edge);
      free(faces_tagged);
      free(solid_buffer);
      free(candidates);
      free(best_manifold);
      free(best_manifold_splits);
      free(polygon_edge_map);
      return NULL;
   }

   if( best_solid != NULL )
   {
      struct cxr_mesh *pullmesh = 
         cxr_alloc_mesh( best_solid->edge_count, best_solid->edge_count, best_solid->count );
      
      // Add existing faces to pullsolid, and delete from main mesh
      for( int i=0; i<best_solid->count; i++ )
      {
         int nface_id = pullmesh->polys.count;

         struct cxr_polygon *exist_face = cxr_ab_ptr(&mesh->polys, solid_buffer[best_solid->start+i]);
         struct cxr_polygon *new_face = cxr_ab_empty(&pullmesh->polys);
         
         *new_face = *exist_face;
         new_face->loop_start = pullmesh->loops.count;

         for( int j=0; j<exist_face->loop_total; j++ )
         {
            struct cxr_loop *exist_loop = cxr_ab_ptr(&mesh->loops, exist_face->loop_start+j);
            struct cxr_loop *new_loop = cxr_ab_empty(&pullmesh->loops);

            new_loop->index = exist_loop->index;
            new_loop->poly_left = nface_id;
            new_loop->poly_right = -1;
            new_loop->edge_index = 0;
            v2_copy( exist_loop->uv, new_loop->uv );
         }

         exist_face->loop_total = -1;
      }

      // Split manifold up by unique planes if it has more than 1
      // otherwise, just use that face
      //
      // TODO: Need to build new manifold in sections, stably
      //       currently there is an unsupported case where the manifold splits
      //       are on located on an implicit face, causing 1-length manifolds.
      
      int new_polys = 0;
      int pullmesh_new_start = pullmesh->polys.count;

      if( fewest_manifold_splits != 0 )
      {
         #if CXR_MANIFOLD_DEBUG
         for( int i=0; i<best_manifold_len; i++ )
         {
            int i0 = i,
                i1 = cxr_range(i+1,best_manifold_len);

            cxr_debug_line( vertices[best_manifold[i0].index], vertices[best_manifold[i1].index], colour_error );
            if( best_manifold_splits[i] )
               cxr_debug_box( vertices[best_manifold[i0].index], 0.04, colour_success );
         }
         #endif
         
         // This is a really strange observation, however it *seems* to apply to the kinds
         // of geometry we are dealing with. If the split count is odd, the manifold can be
         // created easily, no folding required.
         //
         // When it is even, it appears that internal implicit geometry is required, so we
         // need to fold the loops we create. Its really weird, but for some reason works on 
         // the geometry rules we've defined.
         //   TODO: Find a well defined rule here.

         int collapse_used_segments = (u32)fewest_manifold_splits & 0x1? 0: 1;

         IL_MANIFOLD_BUILD_REPEAT:
         
         for( int j=0; j<best_manifold_len; j++ )
         {
            if( best_manifold_splits[j] )
            {
               struct cxr_loop *loop = &best_manifold[j];

               for( int k=1; k<best_manifold_len; k++ )
               {
                  int index1 = cxr_range(j+k,best_manifold_len);
                  struct cxr_loop *loop1 = &best_manifold[index1];

                  if( best_manifold_splits[index1] )
                  {
                     if( k==1 )
                        break;

                     new_polys ++;

                     if( new_polys > best_manifold_len )
                     {
                        cxr_log( "Programming error: Too many new polys!\n" );
                        exit(1);
                     }

                     cxr_create_poly( pullmesh, vertices, best_manifold, k+1, j, best_manifold_len );

                     // Remove new section from manifold
                     if( collapse_used_segments )
                     {
                        best_manifold_splits[j] = 0;
                        best_manifold_splits[index1] = 0;

                        int new_length = (best_manifold_len-(k-1));

                        struct cxr_loop *new_manifold = malloc( new_length*sizeof(struct cxr_loop) );
                        int *new_manifold_splits = malloc( new_length*sizeof(int) );

                        for( int l=0; l<new_length; l ++ )
                        {
                           int i_src = cxr_range( j+k+l, best_manifold_len );
                           new_manifold[l] = best_manifold[i_src];
                           new_manifold_splits[l] = best_manifold_splits[i_src];
                        }

                        free( best_manifold );
                        free( best_manifold_splits );
                        best_manifold = new_manifold;
                        best_manifold_splits = new_manifold_splits;

                        best_manifold_len = new_length;

                        goto IL_MANIFOLD_BUILD_REPEAT;
                     }

                     j=j+k-1;
                     break;
                  }
               }
            }
         }
         
         if( best_manifold_len && collapse_used_segments )
         {
            cxr_create_poly( pullmesh, vertices, best_manifold, best_manifold_len, 0, best_manifold_len );
            new_polys ++;
         }
      }
      else
      {
         cxr_create_poly( pullmesh, vertices, best_manifold, best_manifold_len, 0, best_manifold_len );
         new_polys = 1;
      }

      // vert_buffer may be reallocated by the next section of code,
      //             force a NULLref on vertices to catch any errors
      vertices = NULL;

      // Implicit geometry reconstruction
      //   If there's 3 or more planes, collide them together to see if any new
      //   vertices need to be created on the mesh
      if( new_polys >= 3 )
      {
         for( int i=0; i<new_polys-2; i++ )
         {
            for( int j=i+1; j<new_polys-1; j++ )
            {
               for( int k=j+1; k<new_polys; k++ )
               {
                  struct cxr_polygon *ptri = cxr_ab_ptr( &pullmesh->polys, pullmesh_new_start+i ),
                                     *ptrj = cxr_ab_ptr( &pullmesh->polys, pullmesh_new_start+j ),
                                     *ptrk = cxr_ab_ptr( &pullmesh->polys, pullmesh_new_start+k );

                  v4f planei, planej, planek;
                  normal_to_plane(ptri->normal,ptri->center,planei);
                  normal_to_plane(ptrj->normal,ptrj->center,planej);
                  normal_to_plane(ptrk->normal,ptrk->center,planek);
                  
                  v3f intersect;

                  if( plane_intersect(planei,planej,planek,intersect) )
                  {
                     // cxr_debug_box( intersect, 0.05, colour_error );

                     // Make sure this point is within the convex region, otherwise treat
                     // it as a degenerate case
                     
                     int point_valid = 1;
                     for( int l=0; l<pullmesh->polys.count; l++ )
                     {
                        struct cxr_polygon *ptrl = cxr_ab_ptr(&pullmesh->polys,l);
                        v4f planel;

                        normal_to_plane(ptrl->normal, ptrl->center, planel);

                        if( plane_polarity( planel, intersect ) > 0.01 )
                        {
                           cxr_log( "degen vert, planes %d, %d, %d [max:%d]\n", i,j,k, new_polys );
                           *error = CXR_ERROR_DEGEN_IMPLICIT;

                           cxr_debug_poly( pullmesh, ptri, cxr_ab_ptr(vert_buffer,0), colours_random[3] );
                           cxr_debug_poly( pullmesh, ptrj, cxr_ab_ptr(vert_buffer,0), colours_random[1] );
                           cxr_debug_poly( pullmesh, ptrk, cxr_ab_ptr(vert_buffer,0), colours_random[2] );

                           point_valid = 0;
                           break;
                        }
                     }
                     
                     if( !point_valid ) continue;

                     // Extend faces to include this point
                     int nvertid = vert_buffer->count;
                     cxr_ab_push( vert_buffer, intersect );
   
                     ptrj->loop_start += 1;
                     ptrk->loop_start += 2;
                     
                     cxr_ab_reserve(&pullmesh->loops, 3);
                     struct cxr_loop *lloopi = cxr_ab_empty_at(&pullmesh->loops, ptri->loop_start+ptri->loop_total),
                                     *lloopj = cxr_ab_empty_at(&pullmesh->loops, ptrj->loop_start+ptrj->loop_total),
                                     *lloopk = cxr_ab_empty_at(&pullmesh->loops, ptrk->loop_start+ptrk->loop_total);
                     
                     lloopi->index = nvertid;
                     lloopj->index = nvertid;
                     lloopk->index = nvertid;
                     lloopi->edge_index = 0; lloopj->edge_index = 0; lloopk->edge_index = 0;
                     lloopi->poly_left = pullmesh_new_start+i;
                     lloopj->poly_left = pullmesh_new_start+j;
                     lloopk->poly_left = pullmesh_new_start+k;
                     lloopi->poly_right = -1; lloopj->poly_right = -1; lloopk->poly_right = -1;
                     
                     v2_zero(lloopi->uv);
                     v2_zero(lloopj->uv);
                     v2_zero(lloopk->uv);

                     ptri->loop_total ++;
                     ptrj->loop_total ++;
                     ptrk->loop_total ++;

                     // Adjust centers of faces
                     v3_lerp( ptri->center, intersect, 1.0/(double)ptri->loop_total, ptri->center );
                     v3_lerp( ptrj->center, intersect, 1.0/(double)ptrj->loop_total, ptrj->center );
                     v3_lerp( ptrk->center, intersect, 1.0/(double)ptrk->loop_total, ptrk->center );
                  }
               }
            }
         }
      }

      // Copy faces from pullsolid into orig mesh

      for( int i=0; i<new_polys; i++ )
      {
         int rface_id = mesh->polys.count;

         struct cxr_polygon *pface = cxr_ab_ptr(&pullmesh->polys,pullmesh_new_start+i);
         struct cxr_polygon *rip_face = cxr_ab_empty(&mesh->polys);

         rip_face->loop_start = mesh->loops.count;
         rip_face->loop_total = pface->loop_total;
         rip_face->material_id = -1;
         
         for( int j=0; j<rip_face->loop_total; j++ )
         {
            struct cxr_loop *ploop = cxr_ab_ptr(&pullmesh->loops, pface->loop_start+pface->loop_total-j-1),
                            *rloop = cxr_ab_empty(&mesh->loops);

            rloop->index = ploop->index;
            rloop->poly_left = rface_id;
            rloop->poly_right = -1;
            rloop->edge_index = 0;
            v2_copy( ploop->uv, rloop->uv );
         }

         v3_copy( pface->center, rip_face->center );
         v3_negate( pface->normal, rip_face->normal );
      }

      cxr_mesh_clean_faces( mesh );
      cxr_mesh_clean_faces( pullmesh );
      cxr_mesh_clean_edges( mesh );
      cxr_mesh_clean_edges( pullmesh );

      free(edge_tagged);
      free(vertex_tagged);
      free(hot_edge);
      free(faces_tagged);
      free(solid_buffer);
      free(candidates);
      free(best_manifold);
      free(best_manifold_splits);
      free(polygon_edge_map);
   
      return pullmesh;
   }

   free(edge_tagged);
   free(vertex_tagged);
   free(hot_edge);
   free(faces_tagged);
   free(solid_buffer);
   free(candidates);
   free(best_manifold);
   free(best_manifold_splits);
   free(polygon_edge_map);

   return NULL;
}

static struct cxr_mesh *cxr_to_internal_format(struct cxr_input_mesh *src, struct cxr_auto_buffer *abverts)
{
   // Split mesh into islands
   struct cxr_mesh *mesh = cxr_alloc_mesh( src->edge_count, src->loop_count, src->poly_count );
   cxr_ab_init( abverts, sizeof(v3f), src->vertex_count );

   // Copy input data into working mesh
   memcpy( cxr_ab_ptr( &mesh->edges, 0 ), src->edges, src->edge_count*sizeof(struct cxr_edge));
   memcpy( cxr_ab_ptr( &mesh->polys, 0 ), src->polys, src->poly_count*sizeof(struct cxr_polygon));
   memcpy( cxr_ab_ptr( abverts, 0 ), src->vertices, src->vertex_count*sizeof(v3f));
   mesh->edges.count = src->edge_count;
   mesh->loops.count = src->loop_count;
   mesh->polys.count = src->poly_count;

   for( int i=0; i<src->loop_count; i++ )
   {
      struct cxr_loop *lp = cxr_ab_ptr(&mesh->loops,i);
      lp->index = src->loops[i].index;
      lp->edge_index = src->loops[i].edge_index;
      v2_copy( src->loops[i].uv, lp->uv );
   }

   abverts->count = src->vertex_count;

   return mesh;
}

// Find farthest dot product along direction
static double support_distance( v3f verts[3], v3f dir, double coef )
{
   return cxr_maxf
   ( 
      coef * v3_dot( verts[0], dir ), 
      cxr_maxf
      (
         coef * v3_dot( verts[1], dir ),
         coef * v3_dot( verts[2], dir )
      )
   );
}

// Main function
static void cxr_calculate_axis( 
   struct cxr_texinfo *transform,
   v3f verts[3],
   v2f uvs[3],
   v2f texture_res
   )
{
   v2f tT, bT; // Tangent/bitangent pairs for UV space and world
   v3f tW, bW;

   v2_sub( uvs[0], uvs[1], tT );
   v2_sub( uvs[2], uvs[1], bT );
   v3_sub( verts[0], verts[1], tW );
   v3_sub( verts[2], verts[1], bW );

   // Use arbitrary projection if there is no UV 
   if( v2_length( tT ) < 0.0001 || v2_length( bT ) < 0.0001 )
   {
      v3f uaxis, normal, vaxis;

      v3_copy( tW, uaxis );
      v3_normalize( uaxis );

      v3_cross( tW, bW, normal );
      v3_cross( normal, uaxis, vaxis );
      v3_normalize( vaxis );

      v3_copy( uaxis, transform->uaxis );
      v3_copy( vaxis, transform->vaxis );
      v2_zero( transform->offset );

      v2_div( (v2f){128.0, 128.0}, texture_res, transform->scale );
      return;
   }
   
   // Detect if UV is reversed
   double winding = v2_cross( tT, bT ) >= 0.0f? 1.0f: -1.0f;

   // UV projection reference
   v2f vY, vX;
   v2_muls((v2f){1,0}, winding, vX);
   v2_muls((v2f){0,1}, winding, vY);

   // Reproject reference into world space, including skew
   v3f uaxis1, vaxis1;

   v3_muls( tW, v2_cross(vX,bT) / v2_cross(bT,tT), uaxis1 );
   v3_muladds( uaxis1, bW, v2_cross(vX, tT) / v2_cross(tT,bT), uaxis1 );

   v3_muls( tW, v2_cross(vY,bT) / v2_cross(bT,tT), vaxis1 );
   v3_muladds( vaxis1, bW, v2_cross(vY,tT) / v2_cross(tT,bT), vaxis1 );

   v3_normalize( uaxis1 );
   v3_normalize( vaxis1 );

   // Apply source transform to axis (yes, they also need to be swapped)
   v3f norm, uaxis, vaxis;

   v3_cross( bW, tW, norm );
   v3_normalize(norm);
   v3_cross( vaxis1, norm, uaxis );
   v3_cross( uaxis1, norm, vaxis );

   // real UV scale
   v2f uvmin, uvmax, uvdelta;
   v2_minv( uvs[0], uvs[1], uvmin );
   v2_minv( uvmin, uvs[2], uvmin );
   v2_maxv( uvs[0], uvs[1], uvmax );
   v2_maxv( uvmax, uvs[2], uvmax );
   
   v2_sub( uvmax, uvmin, uvdelta );

   // world-uv scale
   v2f uvminw, uvmaxw, uvdeltaw;
   uvminw[0] = -support_distance( verts, uaxis, -1.0f );
   uvmaxw[0] =  support_distance( verts, uaxis,  1.0f );
   uvminw[1] = -support_distance( verts, vaxis, -1.0f );
   uvmaxw[1] =  support_distance( verts, vaxis,  1.0f );

   v2_sub( uvmaxw, uvminw, uvdeltaw );
   
   // VMf uv scale
   v2f uv_scale;
   v2_div( uvdeltaw, uvdelta, uv_scale );
   v2_div( uv_scale, texture_res, uv_scale );

   // Find offset via 'natural' point
   v2f target_uv, natural_uv, tex_offset;
   v2_mul( uvs[0], texture_res, target_uv );
   
   natural_uv[0] =  v3_dot( uaxis, verts[0] );
   natural_uv[1] = -v3_dot( vaxis, verts[0] );
   v2_div( natural_uv, uv_scale, natural_uv );

   tex_offset[0] =   target_uv[0]-natural_uv[0];
   tex_offset[1] = -(target_uv[1]-natural_uv[1]);

   // Copy everything into output
   v3_copy( uaxis, transform->uaxis );
   v3_copy( vaxis, transform->vaxis );
   v2_copy( tex_offset, transform->offset );
   v2_copy( uv_scale, transform->scale );
}

CXR_API struct cxr_input_mesh *cxr_decompose(struct cxr_input_mesh *src)
{
#ifdef CXR_DEBUG_WRITE_MESH
   FILE *yeet = fopen( "/home/harry/Documents/blender_addons_remote/addons/convexer/solid.h", "w" );

   fprintf( yeet, "v3f test_verts[] = {\n" );
   for( int i=0; i<src->vertex_count; i ++ )
   {
      fprintf( yeet, "   { %f, %f, %f },\n",
            src->vertices[i][0],
            src->vertices[i][1],
            src->vertices[i][2] );
   }
   fprintf( yeet, "};\n" );

   fprintf( yeet, "struct cxr_input_loop test_loops[] = {\n" );
   for( int i=0; i<src->loop_count; i ++ )
   {
      fprintf( yeet, "   {%d, %d},\n",
         src->loops[i].index,
         src->loops[i].edge_index);
   }
   fprintf( yeet, "};\n" );

   fprintf( yeet, "struct cxr_polygon test_polys[] = {\n" );
   for( int i=0; i <src->poly_count; i++ )
   {
      fprintf( yeet, "   {%d, %d, {%f, %f, %f}, {%f, %f, %f}},\n",
         src->polys[i].loop_start,
         src->polys[i].loop_total,
         src->polys[i].normal[0],
         src->polys[i].normal[1],
         src->polys[i].normal[2],
         src->polys[i].center[0],
         src->polys[i].center[1],
         src->polys[i].center[2] );
   }
   fprintf( yeet, "};\n" );

   fprintf( yeet, "struct cxr_edge test_edges[] = {\n" );
   for( int i=0; i<src->edge_count; i++ )
   {
      fprintf( yeet, "   {%d, %d},\n",
         src->edges[i].i0,
         src->edges[i].i1
      );
   }
   fprintf( yeet, "};\n" );

   fprintf( yeet, "struct cxr_input_mesh test_mesh = {\n" );
   fprintf( yeet, "   .vertices = test_verts,\n" );
   fprintf( yeet, "   .loops = test_loops,\n" );
   fprintf( yeet, "   .edges = test_edges,\n" );
   fprintf( yeet, "   .polys = test_polys,\n" );
   fprintf( yeet, "   .poly_count=%d,\n", src->poly_count );
   fprintf( yeet, "   .vertex_count=%d,\n", src->vertex_count );
   fprintf( yeet, "   .edge_count=%d,\n",src->edge_count );
   fprintf( yeet, "   .loop_count=%d\n", src->loop_count );
   fprintf( yeet, "};\n" );

   fclose( yeet );
#endif

   struct cxr_auto_buffer abverts;
   struct cxr_mesh *main_mesh = cxr_to_internal_format( src, &abverts );

   u32 error = 0x00;

   struct cxr_auto_buffer solids;
   cxr_ab_init( &solids, sizeof(struct cxr_mesh *), 2 );

   // TODO: Preprocessor stages
   //  - Split mesh up into islands before doing anything here
   //  - Snap vertices to grid (0.25u) ?
   while(1)
   {
      struct cxr_mesh *res = cxr_pull_best_solid( main_mesh, &abverts, 0, &error );
      if( res )
      {
         cxr_ab_push( &solids, &res );
         if( error ) break;
      }
      else
      {
         if( error )
         {
            // If no solids error we can rety while preserving 'hot' edges

            if( error & CXR_ERROR_NO_SOLIDS )
            {
               error = 0x00;
               res = cxr_pull_best_solid(main_mesh, &abverts, 1, &error);

               if( res ) cxr_ab_push( &solids, &res );
               else break;

               if( error ) break;
            }
            else break;
         }
         else 
            break;
      }
   }

   cxr_ab_push( &solids, &main_mesh );

   if( !error )
   {
      for( int i=0; i<solids.count; i++ )
      {
         struct cxr_mesh **mptr = cxr_ab_ptr(&solids,i);
         cxr_debug_mesh( *mptr, cxr_ab_ptr(&abverts,0), colours_random[cxr_range(i,8)] );
      }
   }

   for( int i=0; i<solids.count; i++ )
   {
      struct cxr_mesh **mptr = cxr_ab_ptr(&solids,i);
      cxr_free_mesh( *mptr );
   }

   cxr_ab_free( &abverts );
   cxr_ab_free( &solids );

   return NULL;
}

CXR_API i32 cxr_convert_mesh_to_vmf(struct cxr_input_mesh *src, struct cxr_vdf *output)
{
   // Split mesh into islands
   struct cxr_auto_buffer abverts;
   struct cxr_mesh *main_mesh = cxr_to_internal_format(src, &abverts);

   u32 error = 0x00;

   struct solidinf
   {
      struct cxr_mesh *pmesh;
      int is_displacement;
   };

   struct cxr_auto_buffer solids;
   cxr_ab_init( &solids, sizeof(struct solidinf), 2 );

   // TODO: Preprocessor stages
   //  - Split mesh up into islands before doing anything here    (DONE)
   //  - Snap vertices to grid (0.25u)                            ?
   
   // Preprocessor 1: Island seperation
   //  ---------------

   while(1)
   {
      struct cxr_mesh *res = cxr_pull_island( main_mesh );
      if( res )
      {
         cxr_ab_push( &solids, &(struct solidinf){ res, 0 });
      }
      else break;
   }
   cxr_ab_push( &solids, &(struct solidinf){main_mesh,0} );
   
   // Preprocessor 2: Displacement break-out
   //  ---------------

   // Preprocessor 3: Breakup non-convex shapes into sub-solids
   //  ---------------
   int sources_count = solids.count;
   
   for( int i=0; i<sources_count; i++ )
   {
      struct solidinf pinf = *(struct solidinf *)cxr_ab_ptr(&solids, i);

      if( pinf.is_displacement )
         // TODO: write displacements here... 
         continue;

      while(1)
      {
         struct cxr_mesh *res = cxr_pull_best_solid( pinf.pmesh, &abverts, 0, &error );

         if( res )
         {
            cxr_ab_push( &solids, &(struct solidinf){res,0} );
            if( error )
               break;
         }
         else
         {
            if( error )
            {
               // If no solids error we can rety while preserving 'hot' edges

               if( error & CXR_ERROR_NO_SOLIDS )
               {
                  error = 0x00;
                  res = cxr_pull_best_solid(pinf.pmesh, &abverts, 1, &error);

                  if( res ) cxr_ab_push( &solids, &(struct solidinf){res,0} );
                  else break;

                  if( error ) break;
               }
            }
            else 
               break;
         }
      }
   }
   
   if( cxr_settings.debug )
   {
      for( int i=0; i<solids.count; i++ )
      {
         struct solidinf *solid = cxr_ab_ptr(&solids,i);
         cxr_debug_mesh( solid->pmesh, cxr_ab_ptr(&abverts,0), colours_random[cxr_range(i,8)] );
      }
   }

   // Turn all those solids into VMF brushes
   // --------------------------------------
   for( int i=0; i<solids.count; i++ )
   {
      struct solidinf *solid = cxr_ab_ptr(&solids,i);

      if( solid->is_displacement ) continue;

      cxr_vdf_node( output, "solid" );
      cxr_vdf_ki32( output, "id", ++ cxr_context.brush_count ); 
      
      for( int j=0; j<solid->pmesh->polys.count; j++ )
      {
         struct cxr_polygon *poly = cxr_ab_ptr( &solid->pmesh->polys, j );
         struct cxr_loop *ploops = cxr_ab_ptr(&solid->pmesh->loops, poly->loop_start);
         struct cxr_material *matptr = 
            poly->material_id < 0 || src->material_count == 0? 
               &cxr_nodraw:
               &src->materials[ poly->material_id ];

         cxr_vdf_node( output, "side" );
         cxr_vdf_ki32( output, "id", ++ cxr_context.face_count );

         v3f verts[3]; v2f uvs[3];

         v3_muls( cxr_ab_ptr(&abverts, ploops[0].index), cxr_context.scale_factor, verts[0] );
         v3_muls( cxr_ab_ptr(&abverts, ploops[1].index), cxr_context.scale_factor, verts[1] );
         v3_muls( cxr_ab_ptr(&abverts, ploops[2].index), cxr_context.scale_factor, verts[2] );
         verts[0][2] += cxr_context.offset_z;
         verts[1][2] += cxr_context.offset_z;
         verts[2][2] += cxr_context.offset_z;

         v2_copy( ploops[0].uv, uvs[0] );
         v2_copy( ploops[1].uv, uvs[1] );
         v2_copy( ploops[2].uv, uvs[2] );

         cxr_vdf_plane( output, "plane", verts[2], verts[1], verts[0] );
         cxr_vdf_kv( output, "material", matptr->vmt_path );
         
         struct cxr_texinfo trans;
         cxr_calculate_axis(&trans, verts, uvs, (double[2]){ matptr->res[0], matptr->res[1] });

         cxr_vdf_kaxis(output, "uaxis", trans.uaxis, trans.offset[0], trans.scale[0]);
         cxr_vdf_kaxis(output, "vaxis", trans.vaxis, trans.offset[1], trans.scale[1]);

         cxr_vdf_kdouble(output, "rotation", 0.0 );
         cxr_vdf_ki32(output, "lightmapscale", cxr_settings.lightmap_scale );
         cxr_vdf_ki32(output, "smoothing_groups", 0);

         cxr_vdf_edon( output );
      }

      cxr_vdf_node(output, "editor");
      cxr_vdf_colour255(output,"color", colours_random[cxr_range(cxr_context.brush_count,8)]);
      cxr_vdf_ki32(output,"visgroupshown",1);
      cxr_vdf_ki32(output,"visgroupautoshown",1);
      cxr_vdf_edon(output);

      cxr_vdf_edon( output );
   }
   
   for( int i=0; i<solids.count; i++ )
   {
      struct solidinf *solid = cxr_ab_ptr(&solids,i);
      cxr_free_mesh( solid->pmesh );
   }

   cxr_ab_free( &abverts );
   cxr_ab_free( &solids );
   return 0;
}


CXR_API void cxr_set_log_function( void (*func)(const char *str) )
{
   cxr_log_func = func;
}

CXR_API void cxr_set_line_function( void (*func)(v3f p0, v3f p1, v4f colour) )
{
   cxr_line_func = func;
}

CXR_API void cxr_settings_update( struct cxr_settings *settings )
{
   cxr_settings = *settings;
}

// Valve copyright stuff probably maybe
//  whatever, my previous copyright decleration ends here
// ----------------------------------------------------------

#define HEADER_LUMPS            64
#define  LUMP_WORLDLIGHTS  54

#pragma pack(push,1)

struct header
{
   int        ident;
   int        version;

   struct lump 
   {
      int fileofs, filelen;
      int version;

      char fourCC[4];
   }
   lumps[ HEADER_LUMPS ];

   int        mapRevision;
};

struct worldlight
{
        float              origin[3];
        float              intensity[3];
        float              normal[3];
        float              shadow_cast_offset[3];
        int                     cluster;
        int         type;
   int                  style;
        float              stopdot;
        float              stopdot2;
        float           exponent;
        float           radius;
        float              constant_attn;       
        float              linear_attn;
        float              quadratic_attn;
        int                     flags;
        int                     texinfo;        
        int                     owner;
};
#pragma pack(pop)

// Utility for patching BSP tools to remove -1 distance lights (we set them
//  like that, because we want these lights to go away)
//
//  Yes, there is no way to do this in hammer
//  Yes, the distance KV is unused but still gets compiled to this lump
//  No, Entities only compile will not do this for you
//
CXR_API int cxr_lightpatch_bsp( const char *path )
{
   printf( "Lightpatch: %s\n", path );

   FILE *fp = fopen( path, "r+b" );

   if( !fp )
   {
      cxr_log( "Could not open BSP file for editing (r+b)\n" );
      return 0;
   }

   // Read bsp
   struct header header;
   fread( &header, sizeof(struct header), 1, fp );
   struct lump *lump = &header.lumps[ LUMP_WORLDLIGHTS ];

   // Read worldlight array
   struct worldlight *lights = malloc( lump->filelen );
   fseek( fp, lump->fileofs, SEEK_SET );
   fread( lights, lump->filelen, 1, fp );

   // Remove all marked lights
   int light_count = lump->filelen / sizeof(struct worldlight);
   int new_count = 0;

   for( int i = 0; i < light_count; i ++ )
      if( lights[i].radius >= 0.0f )
         lights[new_count++] = lights[i];
   
   lump->filelen = new_count*sizeof(struct worldlight);

   // Write changes
   fseek( fp, lump->fileofs, SEEK_SET );
   fwrite( lights, lump->filelen, 1, fp );
   fseek( fp, 0, SEEK_SET );
   fwrite( &header, sizeof(struct header), 1, fp );
   cxr_log( "removed %d marked lights\n", light_count-new_count );

   fclose( fp );
   free( lights );

   return 1;
}