[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
*/

const char *cxr_build_time = __DATE__ " @" __TIME__;

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

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_PLANE_SIMILARITY_MAX 0.998
#define CXR_BIG_NUMBER 1e300
#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;
      i32 freestyle;
   }
   *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;
   double winding;
};

// 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_kv3f(struct cxr_vdf *vdf, const char *strk, v3f v)
{
   cxr_vdf_printf( vdf, "\"%s\" \"[%f %f %f]\"\n", strk, v[0], v[1], v[2] );
}
static void cxr_vdf_karrdouble(struct cxr_vdf *vdf, const char *strk, int id, double *doubles, int count)
{
   cxr_vdf_put(vdf,"");
   fprintf( vdf->fp, "\"%s%d\" \"", strk, id );
   for( int i=0; i<count; i++ )
   {
      if( i == count-1 ) fprintf( vdf->fp, "%f", doubles[i] );
      else fprintf( vdf->fp, "%f ", doubles[i] );
   }
   fprintf( vdf->fp, "\"\n" );
}
static void cxr_vdf_karrv3f(struct cxr_vdf *vdf, const char *strk, int id, v3f *vecs, int count)
{
   cxr_vdf_put(vdf,"");
   fprintf( vdf->fp, "\"%s%d\" \"", strk, id );
   for( int i=0; i<count; i++ )
   {
      if( i == count-1 ) fprintf( vdf->fp, "%f %f %f", vecs[i][0], vecs[i][1], vecs[i][2] );
      else fprintf( vdf->fp, "%f %f %f ", vecs[i][0], vecs[i][1], vecs[i][2] );
   }
   fprintf( vdf->fp, "\"\n" );
}
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 )
         {
            struct cxr_edge *orig_edge = cxr_ab_ptr( &mesh->edges, orig_edge_id );
            edge.freestyle = orig_edge->freestyle;
         }
         else
         {
            edge.freestyle = 0;
         }

         // --- ! ---
         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) > CXR_PLANE_SIMILARITY_MAX )
         {
            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) > CXR_PLANE_SIMILARITY_MAX )
               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;
   }

   
   for( int i=0; i<vert_buffer->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;
   
   struct tedge
   {
      int i0, i1;
   } 
   *edge_references = malloc( mesh->edges.count *sizeof(struct tedge) );

   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] )
               {
                  // TODO(harry):
                  // 
                  // 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
                  //
                  // This can sort out SOME invalid configs, but not all.
                  // It would be nice to find a more robust clustering algorithm for this.
                  //

                  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) > CXR_PLANE_SIMILARITY_MAX)
                           goto IL_SKIP_PLANE_ADD;
                     }

                     IL_SKIP_SIMILAR_PLANES:;
                  }

                  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;

      // The current method can create some invalid configurations
      // filter those out that dont work and un-tag the faces
      for( int j=0; j<solid_len-1; j++ )
      {
         for( int k=j+1; k<solid_len; k++ )
         {
            struct cxr_polygon *polyj = cxr_ab_ptr(&mesh->polys, solid[j]),
                               *polyk = cxr_ab_ptr(&mesh->polys, solid[k]);
            
            if( v3_dot( polyj->normal, polyk->normal ) > CXR_PLANE_SIMILARITY_MAX )
            {
               for( int l=0; l<solid_len; l++ )
                  faces_tagged[ solid[l] ] = -1;

               goto IL_CANCEL_SOLID;
            }
         }
      }

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

      IL_CANCEL_SOLID:;
   }

   free( edge_references );

   // 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;
      }
      
      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(harry): 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 );
      transform->winding = 1.0;
      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 );
   transform->winding = winding;
}

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

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

static int cxr_cardinal( v3f a, int ignore )
{
   int component = 0;
   double component_max = -CXR_BIG_NUMBER;

   for( int i=0; i<3; i++ )
   {
      if( i == ignore ) continue;

      if( fabs(a[i]) > component_max )
      {
         component_max = fabs(a[i]);
         component = i;
      }
   }
   double d = a[component] >= 0.0? 1.0: -1.0;
   v3_zero( a );
   a[component] = d;

   return component;
}

// Convert contiguous mesh to patch of displacments
//
static void cxr_write_disp(struct cxr_mesh *mesh, struct cxr_input_mesh *inputmesh, 
   struct cxr_vdf *output, 
   struct cxr_auto_buffer *abverts)
{
   // Create a graph which maps vertices by their connections
   struct vertinfo
   {
      int con_start, con_count;     // Index into the connection graph
      int boundary,
          used,
          search,
          corner;

      double alpha;
   }
   *vertinfo = malloc( sizeof(struct vertinfo)*abverts->count );
   int *graph = malloc( sizeof(int) * mesh->edges.count*2 );
   
   int con_pos = 0;
   for( int i=0; i<abverts->count; i++ )
   {
      struct vertinfo *info = &vertinfo[i];
      info->con_start = con_pos;
      info->con_count = 0;
      info->boundary = 0;
      info->corner = 0;
      info->used = 0;
      info->search = 0;
      info->alpha = 0.0;

      for( int j=0; j<mesh->edges.count; j++ )
      {
         struct cxr_edge *edge = cxr_ab_ptr(&mesh->edges,j);

         if( edge->i0 == i || edge->i1 == i )
         {
            graph[ con_pos ++ ] = edge->i0 == i? edge->i1: edge->i0;
            info->con_count ++;

            if( edge->freestyle )
               info->boundary = 1;
         }
      }
   }

   // Find best normal for brush patch. VBSP uses the original brush
   // as reference for decal projection.
   //
   // These are clamped to be cardinal directions as to make the VMF somewhat
   // human editable.

   v3f avg_normal, refv, refu, refn;
   v3_zero(refv); v3_zero(refu); v3_zero(refn);
   
   for( int i=0; i<mesh->polys.count; i++ )
   {
      struct cxr_polygon *poly = cxr_ab_ptr( &mesh->polys, i );
      v3_add( poly->normal, avg_normal, avg_normal );
   }
   v3_divs( avg_normal, mesh->polys.count, avg_normal );
   v3_normalize( avg_normal );   // TODO(harry): This can be zero length. Should add a safety check
                                 // normalize function that checks for small length before
                                 // carrying out, otherwise we get inf/nan values...

   int n_cardinal = cxr_cardinal( avg_normal, -1 );

   // Approximately matching the area of the result brush faces to the actual area
   // this is to assign a 'best guess' amount of lightmap texels.
   //
   double uv_area = 0.0, face_area = 0.0, sf;
   v2f uvboundmin, uvboundmax;
   v3f faceboundmin, faceboundmax;
   v2f uv_center;
   v3f face_center;

   v2_fill( uvboundmin,  CXR_BIG_NUMBER );
   v2_fill( uvboundmax, -CXR_BIG_NUMBER );
   v3_fill( faceboundmin,  CXR_BIG_NUMBER );
   v3_fill( faceboundmax, -CXR_BIG_NUMBER );

   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);
         v2_minv( lp0->uv, uvboundmin, uvboundmin);
         v2_maxv( lp0->uv, uvboundmax, uvboundmax);
         v3_minv( cxr_ab_ptr(abverts,lp0->index), faceboundmin, faceboundmin );
         v3_maxv( cxr_ab_ptr(abverts,lp0->index), faceboundmax, faceboundmax );
      }

      for( int j=0; j<poly->loop_total-2; j++ )
      {
         struct cxr_loop *lp0 = cxr_ab_ptr(&mesh->loops, poly->loop_start),
                         *lp1 = cxr_ab_ptr(&mesh->loops, poly->loop_start+j+1),
                         *lp2 = cxr_ab_ptr(&mesh->loops, poly->loop_start+j+2);
         v3f va, vb, orth;
         v3_sub( cxr_ab_ptr(abverts,lp1->index), cxr_ab_ptr(abverts,lp0->index), va );
         v3_sub( cxr_ab_ptr(abverts,lp2->index), cxr_ab_ptr(abverts,lp0->index), vb );
         v3_cross( va, vb, orth );
         
         face_area += v3_length( orth ) / 2.0;
         
         v2f uva, uvb;
         v2_sub( lp1->uv, lp0->uv, uva );
         v2_sub( lp2->uv, lp0->uv, uvb );
         
         uv_area += fabs(v2_cross( uva, uvb )) / 2.0;
      }
   }

   v3_add( faceboundmax, faceboundmin, face_center );
   v3_muls( face_center, 0.5, face_center );
   v2_add( uvboundmin, uvboundmax, uv_center );
   v2_muls( uv_center, 0.5, uv_center );

   sf = sqrt( face_area / uv_area );
   int corner_count = 0;

   // Vertex classification
   for( int i=0; i<abverts->count; i++ )
   {
      struct vertinfo *info = &vertinfo[i];
      if( !info->boundary ) continue;

      int count = 0,
          non_manifold = 1;

      for( int j=0; j<info->con_count; j++ )
      {
         int con = graph[info->con_start+j];

         if( vertinfo[con].boundary )
            count ++;
         else
            non_manifold = 0;
      }
      if( count > 2 || non_manifold )
      {
         info->corner = 1;
         corner_count ++;

         //cxr_debug_box( cxr_ab_ptr(abverts,i), 0.1, colour_success );
      }
   }
   
   // TODO(harry): This currently only supports power 2 displacements
   //              its quite straightforward to upgrade it.
   //
   int dispedge[16];
   v2f corner_uvs[4];
   int dispedge_count;
   int disp_count = 0;

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

      for( int h=0; h<basepoly->loop_total; h ++ )
      {
         int i0 = h,
             i1 = cxr_range(h+1,basepoly->loop_total);

         struct cxr_loop *l0 = cxr_ab_ptr(&mesh->loops, basepoly->loop_start+i0),
                         *l1 = cxr_ab_ptr(&mesh->loops, basepoly->loop_start+i1);
         struct vertinfo *info = &vertinfo[ l0->index ];

         if( info->corner )
         { 
            int corner_count = 1;
            
            struct cxr_material *matptr = 
               basepoly->material_id < 0 || inputmesh->material_count == 0? 
                  &cxr_nodraw:
                  &inputmesh->materials[ basepoly->material_id ];

            dispedge_count = 2;
            dispedge[0] = l0->index;
            dispedge[1] = l1->index;
            v2_copy( l0->uv, corner_uvs[0] );
            
            // Consume (remove) faces we use for corners
            basepoly->loop_total = -1;
            
            //cxr_debug_box( cxr_ab_ptr(abverts,l0->index),0.08,(v4f){0.0,0.0,1.0,1.0});

            // Collect edges 
            // --------------------

            while( dispedge_count < 17 )
            {
               struct vertinfo *edge_head = &vertinfo[dispedge[dispedge_count-1]];
               int newvert = 0;
               
               if( edge_head->corner )
               {
                  // Find a polygon that has the edge C-1 -> C
                  for( int j=0; j<mesh->polys.count && !newvert; j++ )
                  {
                     struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys,j);

                     for( int k=0; k<poly->loop_total; k ++ )
                     {
                        int i0 = k,
                            i1 = cxr_range(k+1,poly->loop_total);

                        struct cxr_loop *l0 = cxr_ab_ptr(&mesh->loops, poly->loop_start+i0),
                                        *l1 = cxr_ab_ptr(&mesh->loops, poly->loop_start+i1);

                        if( l0->index == dispedge[dispedge_count-2] &&
                            l1->index == dispedge[dispedge_count-1] )
                        {
                           // Take the vertex after that edge
                           v2_copy( l1->uv, corner_uvs[corner_count ++] );

                           int i2 = cxr_range(i1+1,poly->loop_total);
                           struct cxr_loop *l2 = cxr_ab_ptr(&mesh->loops, poly->loop_start+i2);

                           dispedge[dispedge_count ++] = l2->index;
                           newvert = 1;
                           poly->loop_total = -1;
                           break;
                        }
                     }
                  }
               }
               else
               {
                  for( int j=0; j<edge_head->con_count; j++ )
                  {
                     int con = graph[edge_head->con_start+j];

                     if( con == -1 )
                        continue;

                     if( dispedge_count > 1 )
                        if( con == dispedge[dispedge_count-2] )
                           continue;
                     
                     struct vertinfo *coninfo = &vertinfo[con];
                     
                     if( !coninfo->boundary )
                        continue;
                     
                     /*
                     cxr_debug_arrow( cxr_ab_ptr(abverts,dispedge[dispedge_count-1]),
                                      cxr_ab_ptr(abverts,con),
                                      (v3f){0,0,1},
                                      0.1,
                                      colour_success );
                     */

                     dispedge[ dispedge_count ++ ] = con;
                     newvert = 1;

                     break;
                  }
               }

               if( !newvert )
               {
                  cxr_debug_box(cxr_ab_ptr(abverts,dispedge[dispedge_count-1]), 0.1, colour_error);
                  break;
               }
            }
            
            // --------------------
            // Edges collected
            
            v2f va, vb;
            v2_sub( corner_uvs[1], corner_uvs[0], va );
            v2_sub( corner_uvs[2], corner_uvs[0], vb );
            
            // Connect up the grid
            //
            //   0 1 2 3 4
            //  15 a b c d
            //  14 e f g h
            //  13 i j k l
            //  12 m n o p
            //
            //  Example: a := common unused vertex that is connected to
            //                by 1 and 15. Or y-1, and x-1 on the grid.
            //           g := c and f common vert ^
            //
            int grid[25];
            
            for( int j=0; j<5; j++ ) grid[j] = dispedge[j];
            for( int j=1; j<5; j++ ) grid[j*5+4] = dispedge[j+4];
            for( int j=0; j<4; j++ ) grid[4*5+3-j] = dispedge[j+9];
            for( int j=1; j<4; j++ ) grid[j*5] = dispedge[16-j];

            // Grid fill
            for( int j=1; j<4; j++ )
            {
               for( int k=1; k<4; k++ )
               {
                  int s0 = grid[(j-1)*5+k],
                      s1 = grid[j*5+k-1];

                  struct vertinfo *va = &vertinfo[s0],
                                  *vb = &vertinfo[s1];

                  // Find a common vertex between s0 and s1
                  
                  for( int l=0; l<va->con_count; l ++ )
                  {
                     for( int m=0; m<vb->con_count; m ++ )
                     {
                        int cona = graph[va->con_start+l],
                            conb = graph[vb->con_start+m];

                        if( cona == conb )
                        {
                           if( vertinfo[cona].used || vertinfo[cona].boundary )
                              continue;

                           grid[ j*5+k ] = cona;
                           vertinfo[cona].used = 1;

                           goto IL_MATCHED_DISP_INTERIOR_VERT;
                        }
                     }
                  }

                  // Broken displacement
                  cxr_log( "Broken displacement!\n" );
                  free( graph );
                  free( vertinfo );
                  return;

                  IL_MATCHED_DISP_INTERIOR_VERT:;
               }
            }

            // Create brush vertices based on UV map
            
            // Create V reference based on first displacement.
            // TODO(harry): This is not the moststable selection method!
            //       faces can come in any order, so the first disp will of course
            //       always vary. Additionaly the triangle can be oriented differently.
            //
            //       Improvement can be made by selecting a first disp/triangle based
            //       on deterministic factors.
            //
            if( disp_count == 0 )
            {
               struct cxr_texinfo tx;
               v3f tri_ref[3];
               v3_copy( cxr_ab_ptr(abverts,dispedge[0]), tri_ref[0] );
               v3_copy( cxr_ab_ptr(abverts,dispedge[4]), tri_ref[1] );
               v3_copy( cxr_ab_ptr(abverts,dispedge[8]), tri_ref[2] );
               cxr_calculate_axis( &tx, tri_ref, corner_uvs, (v2f){512,512} );

               v3_muls( tx.vaxis, -1.0, refv );
               int v_cardinal = cxr_cardinal( refv, -1 );

               v3_cross( tx.vaxis, tx.uaxis, refn );
               v3_muls( refn, -tx.winding, refn );

               int n1_cardinal = cxr_cardinal( refn, v_cardinal );
               
               //v3_copy( avg_normal, refn );
               int u_cardinal = 0;
               if( u_cardinal == n1_cardinal || u_cardinal == v_cardinal ) u_cardinal ++;
               if( u_cardinal == n1_cardinal || u_cardinal == v_cardinal ) u_cardinal ++;

               v3_zero(refu);
               refu[u_cardinal] = tx.uaxis[u_cardinal] > 0.0? 1.0: -1.0;

               v3f p0, pv, pu, pn;

               v3_copy( face_center, p0 );
               v3_muladds( face_center, refn, 1.5, pn );
               v3_muladds( face_center, refv, 1.5, pv );
               v3_muladds( face_center, refu, 1.5, pu );
               
               if( cxr_settings.debug )
               {
                  cxr_debug_line( p0, pn, (v4f){0.0,0.0,1.0,1.0});
                  cxr_debug_line( p0, pv, (v4f){0.0,1.0,0.0,1.0});
                  cxr_debug_line( p0, pu, (v4f){1.0,0.0,0.0,1.0});
                  cxr_debug_line( tri_ref[0], tri_ref[1], (v4f){1.0,1.0,1.0,1.0} );
                  cxr_debug_line( tri_ref[1], tri_ref[2], (v4f){1.0,1.0,1.0,1.0} );
                  cxr_debug_line( tri_ref[2], tri_ref[0], (v4f){1.0,1.0,1.0,1.0} );
               }
            }

            // Create world cordinates
            v3f world_corners[8];
            v2f world_uv[4];

            for( int j=0; j<4; j++ )
            {
               v2f local_uv;
               v2_sub( corner_uvs[j], uv_center, local_uv );
               v2_copy( corner_uvs[j], world_uv[j] );
               v2_muls( local_uv, sf, local_uv );

               v3_muls( refu, local_uv[0], world_corners[j] );
               v3_muladds( world_corners[j], refv, local_uv[1], world_corners[j] );
               v3_add( face_center, world_corners[j], world_corners[j] );
            }

            double *colour = colours_random[cxr_range(disp_count,8)];

            for( int j=0; j<4; j++ )
               v3_muladds( world_corners[j], refn, -1.0, world_corners[j+4] );
            
            if( cxr_settings.debug )
            {
               cxr_debug_arrow( world_corners[0], world_corners[1], avg_normal, 0.1, colour );
               cxr_debug_arrow( world_corners[1], world_corners[2], avg_normal, 0.1, colour );
               cxr_debug_arrow( world_corners[2], world_corners[3], avg_normal, 0.1, colour );
               cxr_debug_arrow( world_corners[3], world_corners[0], avg_normal, 0.1, colour );
            }

            /*
            cxr_debug_arrow( world_corners[0+4], world_corners[1+4], avg_normal, 0.1, colour );
            cxr_debug_arrow( world_corners[1+4], world_corners[2+4], avg_normal, 0.1, colour );
            cxr_debug_arrow( world_corners[2+4], world_corners[3+4], avg_normal, 0.1, colour );
            cxr_debug_arrow( world_corners[3+4], world_corners[0+4], avg_normal, 0.1, colour );
            */

            // Apply world transform
            for( int j=0; j<8; j++ )
            {
               v3_muls( world_corners[j], cxr_context.scale_factor, world_corners[j] );
               world_corners[j][2] += cxr_context.offset_z;
            }

            struct cxr_texinfo texinfo_shared;
            cxr_calculate_axis( &texinfo_shared, world_corners, world_uv, 
               (v2f){ matptr->res[0], matptr->res[1] } );

            // Write brush
            cxr_vdf_node( output, "solid" );
            cxr_vdf_ki32( output, "id", ++ cxr_context.brush_count ); 

            int sides[6][3] =
            {{ 0, 1, 2 },
             { 4, 6, 5 },
             { 4, 1, 0 },
             { 7, 0, 3 },
             { 6, 2, 1 },
             { 6, 3, 2 }};
            
            v3f normals[25];
            double distances[25];
            
            v3f lside0, lside1, lref, vdelta, vworld;
            double tx, ty;

            for( int j=0; j<5; j++ )
            {
               ty = (double)j/(double)(5-1);

               v3_lerp( world_corners[0], world_corners[3], ty, lside0 );
               v3_lerp( world_corners[1], world_corners[2], ty, lside1 );

               for( int k=0; k<5; k++ )
               {
                  int index = j*5+k;

                  tx = (double)k/(double)(5-1);
                  v3_lerp( lside0, lside1, tx, lref );
                  v3_muls( cxr_ab_ptr(abverts, grid[index]), cxr_context.scale_factor, vworld );
                  vworld[2] += cxr_context.offset_z;

                  v3_sub( vworld, lref, vdelta );
                  v3_copy( vdelta, normals[index] );
                  v3_normalize( normals[index] );
                  distances[index] = v3_dot( vdelta, normals[index] );
               }
            }

            for( int j=0; j<6; j++ )
            {
               int *side = sides[j];

               cxr_vdf_node( output, "side" );
               cxr_vdf_ki32( output, "id", ++ cxr_context.face_count );
               cxr_vdf_plane( output, "plane", world_corners[side[2]],
                                               world_corners[side[1]],
                                               world_corners[side[0]] );
               
               cxr_vdf_kv( output, "material", matptr->vmt_path );

               cxr_vdf_kaxis( output, "uaxis", 
                     texinfo_shared.uaxis, 
                     texinfo_shared.offset[0], 
                     texinfo_shared.scale[0] );
               cxr_vdf_kaxis( output, "vaxis", 
                     texinfo_shared.vaxis, 
                     texinfo_shared.offset[1], 
                     texinfo_shared.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 );
               
               if( j == 0 )
               {
                  cxr_vdf_node( output, "dispinfo" );
                  cxr_vdf_ki32( output, "power", 2 );
                  cxr_vdf_kv3f( output, "startposition", world_corners[0] );
                  cxr_vdf_ki32( output, "flags", 0 );
                  cxr_vdf_kdouble( output, "elevation", 0.0 );
                  cxr_vdf_ki32( output, "subdiv", 0 );
                  
                  cxr_vdf_node( output, "normals" );
                  for( int k=0; k<5; k++ )
                     cxr_vdf_karrv3f( output, "row", k, &normals[k*5], 5 );
                  cxr_vdf_edon( output );
                  
                  cxr_vdf_node( output, "distances" );
                  for( int k=0; k<5; k++ )
                     cxr_vdf_karrdouble( output, "row", k, &distances[k*5], 5 );
                  cxr_vdf_edon( output );
                  
                  // TODO: This might be needed for compiling...
                  /*
                  cxr_vdf_node( output, "offsets" );
                  for( int k=0; k<5; k++ )
                     cxr_vdf_printf( output, "\"row%d\" \"0 0 0 0 0 0 0 0 0 0 0 0 0 0 0\"\n", k );
                  cxr_vdf_edon( output );

                  cxr_vdf_node( output, "offset_normals" );
                  for( int k=0; k<5; k++ )
                     cxr_vdf_printf( output, "\"row%d\" \"0 0 1 0 0 1 0 0 1 0 0 1 0 0 1\"\n", k );
                  cxr_vdf_edon( output );
                  
                  cxr_vdf_node( output, "alphas" );
                  for( int k=0; k<5; k++ )
                     cxr_vdf_printf( output, "\"row%d\" \"0 0 0 0 0\"\n", k );
                  cxr_vdf_edon( output );
                  
                  cxr_vdf_node( output, "triangle_tags" );
                  for( int k=0; k<5-1; k++ )
                     cxr_vdf_printf( output, "\"row%d\" \"9 9 9 9 9 9 9 9\"\n", k );
                  cxr_vdf_edon( output );
                  
                  cxr_vdf_node( output, "allowed_verts" );
                  cxr_vdf_printf( output, "\"10\" \"-1 -1 -1 -1 -1 -1 -1 -1 -1 -1\"\n" );
                  cxr_vdf_edon( output );
                  */
                  cxr_vdf_edon( output );
               }

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

   // Main loop
#if 0
   int pool[25];
   for( int i=0; i<abverts->count; i++ )
   {
      struct vertinfo *info = &vertinfo[i];
      if( info->boundary || info->used )
         continue;

      // Gather all vertices in this displacement
      int poolcount = 1,
          front_start = 0,
          front_count = 1;
      pool[0] = i;
      info->used = 1;

      IL_GATHER_LOOP:;
      
      int new_front_start = poolcount;

      for( int j=0; j<front_count; j++ )
      {
         struct vertinfo *frontvert = &vertinfo[pool[front_start+j]];

         for( int k=0; k<frontvert->con_count; k++ )
         {
            int conid = graph[frontvert->con_start+k];
            struct vertinfo *con = &vertinfo[conid];

            if( frontvert->boundary && !con->boundary )
               continue;

            if( con->used )
               continue;
            
            if( poolcount == 25 )
               goto IL_DISP_ERROR_COUNT;

            con->used = 1;
            pool[ poolcount ++ ] = conid;
         }
      }

      if( poolcount > new_front_start )
      {
         front_start = new_front_start;
         front_count = poolcount-front_start;

         goto IL_GATHER_LOOP;
      }
      
      if( poolcount != 25 )
      {
IL_DISP_ERROR_COUNT:
         for( int i=0; i<poolcount; i++ )
            cxr_debug_box( cxr_ab_ptr(abverts,pool[i]), 0.02, colour_error );

         free(graph);
         free(vertinfo);

         cxr_log("Invalid displacement (>25 verts)\n");
         return;
      }

      int corners[4];
      int corner_count = 0;
      struct cxr_loop *cornerloops[4];
      
      // Find corners, and get their loops (for uvs)
      // note: the mesh must be split where there is texture seams
      //       so that two different uv'd loops cant ref the same vertex
      //
      for( int j=0; j<poolcount; j++ )
      {
         if( vertinfo[pool[j]].corner )
         {
            if( corner_count == 4 )
            {
               corner_count = -1;
               break;
            }

            corners[corner_count] = j;
            
            // find loop that includes this vert
            for( int k=0; k<mesh->loops.count; k++ )
            {
               struct cxr_loop *lp = cxr_ab_ptr(&mesh->loops,k);
               if( lp->index == pool[j] )
               {
                  cornerloops[corner_count] = lp;
                  break;
               }
            }

            corner_count ++;
         }
      }

      if( corner_count !=4 )
      {
         free(graph);
         free(vertinfo);
         cxr_log( "Invalid displacement (!=4 corners)\n" );
         return;
      }

      int pivot = corners[0];
   }
#endif

   free( graph );
   free( vertinfo );
}

static int cxr_solid_checkerr(struct cxr_mesh *mesh, struct cxr_auto_buffer *abverts )
{
   int err_count = 0;

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

      struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys,i);
      v4f plane;

      normal_to_plane( poly->normal, poly->center, plane );
      
      for( int j=0; j<poly->loop_total; j++ )
      {
         struct cxr_loop *loop = cxr_ab_ptr(&mesh->loops, poly->loop_start+j);
         double *vert = cxr_ab_ptr(abverts,loop->index);

         if( fabs(plane_polarity(plane,vert)) > 0.0025 )
         {
            err_count ++;
            plane_err ++;

            v3f ref;
            plane_project_point( plane, vert, ref );

            cxr_debug_line( ref, vert, colour_error );
            cxr_debug_box( vert, 0.1, colour_error );
         }
      }

      if( plane_err )
         cxr_debug_poly( mesh, poly, cxr_ab_ptr(abverts,0), colour_error );
   }
   
   return err_count;
}

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;
   int invalid_count = 0;

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

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

   // 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 and error checking
   //  ---------------
   for( int i=0; i<solids.count; i++ )
   {
      struct solidinf *pinf = cxr_ab_ptr(&solids,i);
      
      for( int j=0; j<pinf->pmesh->polys.count; j++ )
      {
         struct cxr_polygon *poly = cxr_ab_ptr( &pinf->pmesh->polys, j );

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

            if( edge->freestyle )
               goto IL_SOLID_IS_DISPLACEMENT;
         }
      }
      
      if( cxr_solid_checkerr( pinf->pmesh, &abverts ) )
      {
         pinf->invalid = 1;
         invalid_count ++;
      }

      continue;
      IL_SOLID_IS_DISPLACEMENT:;
      
      pinf->is_displacement = 1;
      cxr_write_disp( pinf->pmesh, src, output, &abverts );
   }

   // 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 || pinf.invalid )
         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;
            }
            else 
               break;
         }
      }
   }
   
   if( cxr_settings.debug )
   {
      for( int i=0; i<solids.count; i++ )
      {
         struct solidinf *solid = cxr_ab_ptr(&solids,i);

         if( !solid->is_displacement )
            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;
}