[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
      - It runs at an ok speed!
      - Light patch BSP files; remove unwanted realtime effects
      - Fastest VTF compressor (thanks to Richgel999 and stb)

   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"

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

typedef struct cxr_edge cxr_edge;
typedef struct cxr_input_mesh cxr_input_mesh;
typedef struct cxr_input_loop cxr_input_loop;
typedef struct cxr_polygon cxr_polygon;
typedef struct cxr_material cxr_material;
typedef struct cxr_loop cxr_loop;
typedef struct cxr_solid cxr_solid;
typedef struct cxr_mesh cxr_mesh;
typedef struct cxr_texinfo cxr_texinfo;
typedef struct cxr_vdf cxr_vdf;

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 (nodraw) */
   }
   *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_abuffer
      abedges,
      abloops,
      abpolys,

      *p_abverts; /* This data is stored externally because the data is often
                     shared between solids. */

   /* Valid when update() is called on this mesh,
    * Invalid when data is appended to them */
   struct cxr_edge    *edges;
   struct cxr_polygon *polys;
   struct cxr_loop    *loops;
};

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

/* 
 * Simplified VDF writing interface. No allocations or nodes, just write to file
 */
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"
};

/* 
 * This should be called after appending any data to those buffers
 */
static void cxr_mesh_update( cxr_mesh *mesh )
{
   mesh->edges = cxr_ab_ptr(&mesh->abedges, 0);
   mesh->polys = cxr_ab_ptr(&mesh->abpolys, 0);
   mesh->loops = cxr_ab_ptr(&mesh->abloops, 0);
}

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

/*
 * Public API
 */

/* 
 * Main function 
 *  Breaks up geometry into solid pieces
 *  Turns marked mesh segments into displacements
 */
CXR_API i32 cxr_convert_mesh_to_vmf(cxr_input_mesh *src, cxr_vdf *output);

/* Context management */
CXR_API void cxr_context_reset(void);
CXR_API void cxr_set_offset(double offset);
CXR_API void cxr_set_scale_factor(double scale);
CXR_API void cxr_settings_update( struct cxr_settings *settings );

/* VDF interface */
CXR_API cxr_vdf *cxr_vdf_open(const char *path);
CXR_API void cxr_vdf_close(cxr_vdf *vdf);
CXR_API void cxr_vdf_put(cxr_vdf *vdf, const char *str);
CXR_API void cxr_vdf_node(cxr_vdf *vdf, const char *str);
CXR_API void cxr_vdf_edon( cxr_vdf *vdf );
CXR_API void cxr_vdf_kv( cxr_vdf *vdf, const char *strk, const char *strv );

/* Debugging */
CXR_API void cxr_set_log_function( void (*func)(const char *str) );
CXR_API void cxr_set_line_function( void (*func)(v3f p0, v3f p1, v4f colour) );
CXR_API cxr_input_mesh *cxr_write_test_data( cxr_input_mesh *src );

/* Other tools */
CXR_API int cxr_lightpatch_bsp( const char *path );

/*
 * Implementation
 */

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 cxr_vdf *cxr_vdf_open(const char *path)
{
   cxr_vdf *vdf = malloc(sizeof(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(cxr_vdf *vdf)
{
   fclose( vdf->fp );
   free( vdf );
}

CXR_API void cxr_vdf_put(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( 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(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( cxr_vdf *vdf )
{
   vdf->level --;
   cxr_vdf_put( vdf, "}\n" );
}

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

/*
 * Data-type specific Keyvalues
 */
static void cxr_vdf_ki32( cxr_vdf *vdf, const char *strk, i32 val )
{
   cxr_vdf_printf( vdf, "\"%s\" \"%d\"\n", strk, val );
}

static void cxr_vdf_kdouble( cxr_vdf *vdf, const char *strk, double val )
{
   cxr_vdf_printf( vdf, "\"%s\" \"%f\"\n", strk, val );
}

static void cxr_vdf_kaxis( 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( 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( 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( 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++ )
   {
      const char *format = i == count-1? "%f %f %f": "%f %f %f ";
      fprintf( vdf->fp, format, vecs[i][0], vecs[i][1], vecs[i][2] );
   }
   fprintf( vdf->fp, "\"\n" );
}

static void cxr_vdf_plane( 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(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]);
}

/*
 * Debugging line drawing
 */
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 );
}

/*
 * Draw arrow with the tips oriented along normal
 */
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 );
}

/*
 * Draw arrows CCW around polygon, draw normal vector from center
 */
static void cxr_debug_poly( cxr_mesh *mesh, cxr_polygon *poly, v4f colour )
{
   v3f *verts = cxr_ab_ptr( mesh->p_abverts, 0 );

   for( int i=0; i<poly->loop_total; i++ )
   {
      int lp0 = poly->loop_start+i,
          lp1 = poly->loop_start+cxr_range(i+1,poly->loop_total);

      int i0 = mesh->loops[ lp0 ].index,
          i1 = mesh->loops[ lp1 ].index;

      v3f p0, p1;
      
      v3_lerp( verts[i0], poly->center, 0.02, p0 );
      v3_lerp( verts[i1], 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(cxr_mesh *mesh, v4f colour )
{
   for( int i=0; i<mesh->abpolys.count; i++ )
   {
      cxr_polygon *poly = &mesh->polys[i];
      cxr_debug_poly( mesh, poly, colour );
   }
}

/*
 * abverts is a pointer to an existing vertex buffer
 */
static cxr_mesh *cxr_alloc_mesh( int edge_count, int loop_count, int poly_count,
      cxr_abuffer *abverts
){
   cxr_mesh *mesh = malloc(sizeof(cxr_mesh));
   cxr_ab_init(&mesh->abedges, sizeof(cxr_edge), edge_count);
   cxr_ab_init(&mesh->abloops, sizeof(cxr_loop), loop_count);
   cxr_ab_init(&mesh->abpolys, sizeof(cxr_polygon), poly_count);
   mesh->p_abverts = abverts;

   cxr_mesh_update( mesh );

   return mesh;
}

static void cxr_free_mesh( cxr_mesh *mesh )
{
   cxr_ab_free(&mesh->abedges);
   cxr_ab_free(&mesh->abloops);
   cxr_ab_free(&mesh->abpolys);
   free(mesh);
}

/*
 * Rebuilds edge data for mesh (useful to get rid of orphaned edges)
 */
static void cxr_mesh_clean_edges( cxr_mesh *mesh )
{
   cxr_abuffer new_edges;
   cxr_ab_init( &new_edges, sizeof(cxr_edge), mesh->abedges.count );

   for( int i=0; i<mesh->abpolys.count; i++ )
   {
      cxr_polygon *poly = &mesh->polys[i];
      for( int j=0; j<poly->loop_total; j++ )
      {
         cxr_loop
          *lp0 = &mesh->loops[poly->loop_start+j],
          *lp1 = &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);
         
         /* Check if edge exists before adding */
         for( int k=0; k<new_edges.count; k++ )
         {
            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;

         cxr_edge edge = { i0, i1 };

         /*
          * Copy extra information from original edges
          */

         if( orig_edge_id < mesh->abedges.count )
         {
            cxr_edge *orig_edge = &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->abedges );
   mesh->abedges = new_edges;

   cxr_mesh_update( mesh );
}

/*
 * Remove 0-length faces from mesh (we mark them light that for deletion
 * Remove all unused loops as a result of removing those faces
 */
static void cxr_mesh_clean_faces( cxr_mesh *mesh )
{
   cxr_abuffer loops_new;
   cxr_ab_init( &loops_new, sizeof(cxr_loop), mesh->abloops.count );

   int new_length=0;
   for( int i=0; i<mesh->abpolys.count; i++ )
   {
      cxr_polygon *src = &mesh->polys[i],
                  *dst = &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++ )
         {
            cxr_loop *loop = &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->abloops );
   mesh->abloops = loops_new;
   mesh->abpolys.count = new_length;

   cxr_mesh_update( mesh );
}

/*
 * Links loop's poly_left and poly_right 
 * Does not support more than 2 polys to one edge
 *
 * Returns 0 if there is non-manifold geomtry (aka: not watertight)
 */
static int cxr_mesh_link_loops( cxr_mesh *mesh )
{
   i32 *polygon_edge_map = malloc(mesh->abedges.count*2 *sizeof(i32));

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

      for( int j = 0; j < poly->loop_total; j ++ )
      {
         cxr_loop *loop = &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->abpolys.count; i ++ )
   {
      cxr_polygon *poly = &mesh->polys[i];

      for( int j = 0; j < poly->loop_total; j ++ )
      {
         cxr_loop *loop = &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];
      }
   }


   for( int i=0; i<mesh->abedges.count*2; i++ )
   {
      if( polygon_edge_map[i] == -1 )
      {
         free( polygon_edge_map );
         return 0;
      }
   }

   free( polygon_edge_map );
   return 1;
}

/* 
 * Create new empty polygon with known loop count
 * Must be filled and completed by the following functions!
 */
static int cxr_create_poly( cxr_mesh *mesh, int loop_count )
{
   v3f *verts = cxr_ab_ptr( mesh->p_abverts, 0 );

   if( loop_count < 3 )
   {
      cxr_log( "tried to add new poly with length %d!\n", loop_count );
      return 0;
   }

   cxr_ab_reserve( &mesh->abpolys, 1 );
   cxr_ab_reserve( &mesh->abloops, loop_count );
   cxr_mesh_update( mesh );

   cxr_polygon *poly = &mesh->polys[ mesh->abpolys.count ];

   poly->loop_start = mesh->abloops.count;
   poly->loop_total = 0;
   poly->material_id = -1;
   v3_zero( poly->center );

   return 1;
}

/*
 * Add one index to the polygon created by the above function
 */
static void cxr_poly_push_index( cxr_mesh *mesh, int id )
{
   v3f *verts = cxr_ab_ptr( mesh->p_abverts, 0 );

   int nface_id = mesh->abpolys.count;
   cxr_polygon *poly = &mesh->polys[ nface_id ];

   cxr_loop *new_loop = &mesh->loops[ poly->loop_start + poly->loop_total ];

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

   v3_add( poly->center, verts[new_loop->index], poly->center );

   poly->loop_total ++;
   mesh->abloops.count ++;
}

/*
 * Finalize and commit polygon into mesh 
 */
static void cxr_poly_finish( cxr_mesh *mesh )
{
   v3f *verts = cxr_ab_ptr( mesh->p_abverts, 0 );

   int nface_id = mesh->abpolys.count;
   cxr_polygon *poly = &mesh->polys[nface_id];

   /* Average center and calc normal */

   v3_divs( poly->center, poly->loop_total, poly->center );
   cxr_loop *lp0 = &mesh->loops[ poly->loop_start],
            *lp1 = &mesh->loops[ poly->loop_start+1 ],
            *lp2 = &mesh->loops[ poly->loop_start+2 ];
   
   tri_normal( 
    verts[lp0->index], verts[lp1->index], verts[lp2->index], poly->normal);

   mesh->abpolys.count ++;
}

/* 
 * Extract the next island from mesh
 *
 * Returns NULL if mesh is one contigous object
 */
static cxr_mesh *cxr_pull_island( cxr_mesh *mesh )
{
   cxr_mesh_link_loops(mesh);

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

   island_current[0] = 0;

   island_grow:
   last_count = island_len;

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

      for( int j=0; j<poly->loop_total; j++ )
      {
         cxr_loop *loop = &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 island_grow;

   /* Check for complete object */
   if( island_len == mesh->abpolys.count )
   {
      free( island_current );
      return NULL;
   }

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

   /* Create and update meshes */
   cxr_mesh *newmesh = cxr_alloc_mesh( mesh->abedges.count, 
                                              loop_count, 
                                              island_len, 
                                              mesh->p_abverts );

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

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

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

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

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

   cxr_mesh_clean_faces(mesh);
   cxr_mesh_clean_edges(mesh);
   cxr_mesh_clean_edges(newmesh);

   free( island_current );
   return newmesh;
}

/*
 * Invalid solid is when there are vertices that are coplanar to a face, but are
 * outside the polygons edges.
 */
static int cxr_valid_solid( cxr_mesh *mesh, int *solid, int len )
{
   v3f *verts = cxr_ab_ptr(mesh->p_abverts, 0);

   for( int i=0; i<len; i++ )
   {
      cxr_polygon *polyi = &mesh->polys[ solid[i] ];
      
      v4f plane;
      normal_to_plane(polyi->normal, polyi->center, plane);

      for( int j=0; j<len; j++ )
      {
         if( i==j ) continue;
         
         cxr_polygon *polyj = &mesh->polys[ solid[j] ];

         for( int k=0; k<polyj->loop_total; k++ )
         {
            cxr_loop *lpj = &mesh->loops[ polyj->loop_start+k ];
            
            /* Test if the vertex is not referenced by the polygon */
            for( int l=0; l<polyi->loop_total; l++ )
            {
               cxr_loop *lpi = &mesh->loops[ polyi->loop_start+l ];

               if( lpi->index == lpj->index )
                  goto skip_vertex;
            }
            
            if( fabs(plane_polarity(plane, verts[lpj->index])) < 0.001 )
               return 0;

            skip_vertex:;
         }
      }
   }

   return 1;
}

/*
 * Use when iterating the loops array, to get a unique set of edges
 * Better than using the edges array and doing many more checks
 */
static int cxr_loop_unique_edge( cxr_loop *lp )
{
   if( lp->poly_left > lp->poly_right )
      return 0;

   return 1;
}

/* 
 * Identify edges in the mesh where the two connected face's normals
 * are opposing eachother (or close to identical)
 */
static int *cxr_mesh_reflex_edges( cxr_mesh *mesh )
{
   v3f *verts = cxr_ab_ptr( mesh->p_abverts, 0 );
   int *edge_tagged = malloc( mesh->abedges.count * sizeof(int) );
   
   for( int i=0; i<mesh->abloops.count; i++ )
   {
      cxr_loop *lp = &mesh->loops[i];
      if( !cxr_loop_unique_edge( lp ) ) continue;
      
      edge_tagged[lp->edge_index] = 0;

      cxr_polygon *polya = &mesh->polys[ lp->poly_left ],
                         *polyb = &mesh->polys[ lp->poly_right ];

      v4f planeb;
      normal_to_plane(polyb->normal, polyb->center, planeb);

      for( int j=0; j<polya->loop_total; j++ )
      {
         cxr_loop *lp1 = &mesh->loops[ polya->loop_start+j ];

         if(( plane_polarity( planeb, verts[lp1->index] ) > 0.001 ) || 
            ( v3_dot(polya->normal,polyb->normal) > CXR_PLANE_SIMILARITY_MAX ))
         {
            edge_tagged[lp->edge_index] = 1;
            break;
         }
      }
   }

   return edge_tagged;
}

/*
 * Same logic as above function except it will apply it to each vertex
 */
static int *cxr_mesh_reflex_vertices( cxr_mesh *mesh )
{
   v3f *verts = cxr_ab_ptr( mesh->p_abverts, 0 );

   int *vertex_tagged = malloc( mesh->p_abverts->count*sizeof(int) );
   int *connected_planes = malloc( mesh->abpolys.count*sizeof(int) );

   for( int i=0; i<mesh->p_abverts->count; i++ )
   {
      vertex_tagged[i]=0;
      int num_connected = 0;

      /* Create a list of polygons that refer to this vertex */
      for( int j=0; j<mesh->abpolys.count; j++ )
      {
         cxr_polygon *poly = &mesh->polys[j]; 
         for( int k=0; k<poly->loop_total; k++ )
         {
            cxr_loop *loop = &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++ )
         {
            cxr_polygon *polyj = &mesh->polys[connected_planes[j]],
                               *polyk = &mesh->polys[connected_planes[k]];

            if( v3_dot(polyj->normal,polyk->normal) > CXR_PLANE_SIMILARITY_MAX )
               goto tag_vert;
         }
      }
      
      /*
       * Check if all connected planes either:
       *  - Bound this vert
       *  - Coplanar with it
       */
      for( int j=0; j<num_connected; j++ )
      {
         for( int k=j+1; k<num_connected; k++ )
         {
            cxr_polygon *jpoly = &mesh->polys[ connected_planes[j] ],
                               *kpoly = &mesh->polys[ connected_planes[k] ];

            v4f plane;
            normal_to_plane( kpoly->normal, kpoly->center, plane );
            for( int l=0; l<jpoly->loop_total; l++ )
            {
               cxr_loop *lp = &mesh->loops[ jpoly->loop_start+l ];

               if( plane_polarity( plane, verts[lp->index] ) > 0.001 )
                  goto tag_vert;
            }
         }
      }

      continue;
tag_vert: 
      vertex_tagged[i] = 1;
   }

   free( connected_planes );
   return vertex_tagged;
}

/*
 * Detect if potential future edges create a collision with any of the
 * existing edges in the mesh
 */
static int cxr_solid_overlap( cxr_mesh *mesh,
   cxr_polygon *pa,
   cxr_polygon *pb,
   int common_edge_index,
   int debug )
{
   v3f *verts = cxr_ab_ptr( mesh->p_abverts, 0 );
   cxr_edge *common_edge = &mesh->edges[common_edge_index];

   int unique_a = pa->loop_total-2,
       unique_b = pb->loop_total-2;

   int *unique_verts = malloc( (unique_a+unique_b)*sizeof(int) );
   int unique_total = 0;

   for( int j=0; j<2; j++ )
   {
      cxr_polygon *poly = (cxr_polygon *[2]){pa,pb}[j];

      for( int i=0; i<poly->loop_total; i++ )
      {
         cxr_loop *lp = &mesh->loops[poly->loop_start+i];
         
         if( lp->index == common_edge->i0 || lp->index == common_edge->i1 )
            continue;

         unique_verts[ unique_total ++ ] = lp->index;
      }
   }

   v3f ca, cb;

   for( int i=0; i<unique_a; i++ )
   {
      for( int j=unique_a; j<unique_total; j++ )
      {
         int i0 = unique_verts[i],
             i1 = unique_verts[j];
         
         if( debug )
            cxr_debug_line( verts[i0], verts[i1], colours_random[2] );

         for( int k=0; k<mesh->abedges.count; k++ )
         {
            cxr_edge *edge = &mesh->edges[k];
            
            if( edge->i0 == i0 || edge->i0 == i1 ||
                edge->i1 == i0 || edge->i1 == i1 ) continue;

            double *a0 = verts[i0],
                   *a1 = verts[i1],
                   *b0 = verts[edge->i0],
                   *b1 = verts[edge->i1];
            
            double dist = segment_segment_dist( a0, a1, b0, b1, ca, cb );
         
            if( dist < 0.025 )
            {
               if( debug )
               {
                  cxr_debug_box( ca, 0.025, colour_error );
                  cxr_debug_box( cb, 0.025, colour_error );
                  cxr_debug_line( a0, a1, colour_error );
                  cxr_debug_line( b0, b1, colour_error );

                  continue;
               }
               else
               {
                  free( unique_verts );
                  return 1;
               }
            }
         }
      }
   }

   if( debug )
   {
      cxr_debug_line( verts[mesh->edges[common_edge_index].i0],
                      verts[mesh->edges[common_edge_index].i1],
                      colour_success );
   }

   free( unique_verts );
   return 0;
}

/*
 * Creates the 'maximal' solid that originates from this faceid
 *
 * Returns the number of faces used
 */
static int cxr_buildsolid( 
   cxr_mesh *mesh,
   int faceid,
   int *solid,
   int *reflex_edges,
   int *faces_tagged )
{
   faces_tagged[faceid] = faceid;
   
   int solid_len = 0;
   solid[solid_len++] = faceid;
   
   int search_start = 0;
   
search_iterate:;

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

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

         if( faces_tagged[ loop->poly_right ] == -1 )
         {
            if( !reflex_edges[loop->edge_index] )
            {
               /* Check for dodgy edges */
               cxr_polygon *newpoly = &mesh->polys[loop->poly_right];
               
               if( cxr_solid_overlap(mesh,poly,newpoly,loop->edge_index,0))
                  goto skip_plane;

               /* Looking ahead by one step gives us an early out for invalid
                * configurations. This might just all be handled by the new
                * edge overlap detector, though.
                */
               for( int l=0; l < newpoly->loop_total; l++ )
               {
                  cxr_loop *lp1 = &mesh->loops[ newpoly->loop_start+l ];
                  cxr_polygon *future_face = &mesh->polys[ lp1->poly_right ];

                  if( reflex_edges[ lp1->edge_index ] 
                     || lp1->poly_right == loop->poly_right ) 
                     goto dont_check;

                  for( int m=0; m<solid_len; m++ )
                     if( solid[m] == lp1->poly_right )
                        goto dont_check;
                  
                  for( int m=0; m<solid_len; m++ )
                  {
                     cxr_polygon *polym = &mesh->polys[solid[m]];
                     double pdist = v3_dot( polym->normal,future_face->normal);

                     if( pdist > CXR_PLANE_SIMILARITY_MAX )
                        goto dont_check;
                  }

                  dont_check:;
               }

               /* Check for vertices in the new polygon that exist on a current
                * plane. This condition is invalid */
               solid[ solid_len ] = loop->poly_right;

               if( cxr_valid_solid(mesh,solid,solid_len+1 ) )
               {
                  faces_tagged[ loop->poly_right ] = faceid;
                  changed = 1;
                  solid_len ++;
               }
            }

            skip_plane:;
         }
      }
   }
   search_start = solid_len;
   if(changed) 
      goto search_iterate;

   return solid_len;
}

struct csolid
{
   int start, count, edge_count;
   v3f center;
};

struct temp_manifold
{
   struct manifold_loop
   {
      cxr_loop loop;
      int split;
   }
   *loops;

   int loop_count,
       split_count;

   enum manifold_status
   {
      k_manifold_err,
      k_manifold_none,
      k_manifold_fragmented,
      k_manifold_complete,
   }
   status;
};

/*
 * Create polygon from entire manifold structure.
 *
 * Must be completely co-planar
 */
static void cxr_create_poly_full( cxr_mesh *mesh, struct temp_manifold *src )
{
   if( cxr_create_poly( mesh, src->loop_count ) )
   {
      for( int l=0; l<src->loop_count; l++ )
         cxr_poly_push_index( mesh, src->loops[ l ].loop.index);

      cxr_poly_finish( mesh );
   }
}

/*
 * Links up all edges into a potential new manifold
 *
 * The return status can be:
 *        (err): Critical programming error
 *         none: No manifold to create
 *   fragmented: Multiple sections exist, not just one
 *     complete: Optimial manifold was created
 */
static void cxr_link_manifold( 
   cxr_mesh *mesh, 
   struct csolid *solid, 
   int *solid_buffer,
   struct temp_manifold *manifold
   )
{
   cxr_loop **edge_list = malloc( sizeof(*edge_list) * solid->edge_count );

   int init_reverse = 0;
   int unique_edge_count = 0;

   /* Gather list of unique edges */

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

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

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

         for( int l=0; l<solid->count; l++ )
            if( loop->poly_right == solid_buffer[solid->start+l] )
               goto skip_edge;
         
         edge_list[ unique_edge_count ] = loop;

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

         unique_edge_count ++;
         skip_edge:;
      }
   }
   
   if( unique_edge_count == 0 )
   {
      free( edge_list );
      manifold->status = k_manifold_none;
      return;
   }
   
   /* Link edges together to form manifold */
   manifold->loops = malloc( solid->edge_count*sizeof(struct manifold_loop));
   manifold->split_count = 0;
   manifold->loop_count = 0;

   cxr_edge *current = &mesh->edges[ edge_list[0]->edge_index ];

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

   manifold_continue:
   for( int j=0; j<unique_edge_count; j++ )
   {
      cxr_edge *other = &mesh->edges[ edge_list[j]->edge_index ];
      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;

         struct manifold_loop *ml = &manifold->loops[ manifold->loop_count ++ ];
         
         if( curface==edge_list[j]->poly_left )
         {
            ml->split = 1;
            manifold->split_count ++;
         }
         else
            ml->split = 0;
         
         ml->loop.edge_index = edge_list[j]->edge_index;
         ml->loop.poly_left = edge_list[j]->poly_left;
         ml->loop.index = lastpt;
         ml->loop.poly_right = edge_list[j]->poly_right;

         curface = edge_list[j]->poly_left;

         if(endpt == start)
         {
            if( manifold->loop_count < unique_edge_count )
               manifold->status = k_manifold_fragmented;
            else
               manifold->status = k_manifold_complete;

            goto manifold_complete;
         }

         goto manifold_continue;
      }
   }
   
   /* Incomplete links */
   manifold->status = k_manifold_err;

manifold_complete:

   free( edge_list );
   return;
}

/*
 * Reconstruct implied internal geometry where the manifold doesn't have
 * enough information (vertices) to create a full result.
 */
static int cxr_build_implicit_geo( cxr_mesh *mesh, int new_polys, int start )
{
   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++ )
         {
            cxr_polygon *ptri = &mesh->polys[ start+i ],
                        *ptrj = &mesh->polys[ start+j ],
                        *ptrk = &mesh->polys[ 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) )
            {
               /* Make sure the point is inside the convex region */
               
               int point_valid = 1;
               for( int l=0; l<mesh->abpolys.count; l++ )
               {
                  cxr_polygon *ptrl = &mesh->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 );

                     cxr_debug_poly( mesh, ptri, colours_random[3] );
                     cxr_debug_poly( mesh, ptrj, colours_random[1] );
                     cxr_debug_poly( mesh, ptrk, colours_random[2] );

                     return 0;
                  }
               }
               
               /* Extend faces to include this vert */

               int nvertid = mesh->p_abverts->count;
               cxr_ab_push( mesh->p_abverts, intersect );

               ptrj->loop_start += 1;
               ptrk->loop_start += 2;
               
               cxr_ab_reserve( &mesh->abloops, 3);

               int newi = ptri->loop_start+ptri->loop_total,
                   newj = ptrj->loop_start+ptrj->loop_total,
                   newk = ptrk->loop_start+ptrk->loop_total;

               cxr_loop 
                  *lloopi = cxr_ab_empty_at(&mesh->abloops, newi),
                  *lloopj = cxr_ab_empty_at(&mesh->abloops, newj),
                  *lloopk = cxr_ab_empty_at(&mesh->abloops, newk);

               lloopi->index = nvertid;
               lloopi->edge_index = 0; 
               lloopi->poly_left = start + i;
               lloopi->poly_right = -1; 

               lloopj->index = nvertid;
               lloopj->poly_left = start + j;
               lloopj->edge_index = 0; 
               lloopj->poly_right = -1; 

               lloopk->index = nvertid;
               lloopk->edge_index = 0;
               lloopk->poly_left = start + k;
               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 ++;

               double qi = 1.0/(double)ptri->loop_total,
                      qj = 1.0/(double)ptrj->loop_total,
                      qk = 1.0/(double)ptrk->loop_total;

               /* Adjust centers of faces */
               v3_lerp( ptri->center, intersect, qi, ptri->center );
               v3_lerp( ptrj->center, intersect, qj, ptrj->center );
               v3_lerp( ptrk->center, intersect, qk, ptrk->center );
            }
         }
      }
   }

   return 1;
}

/* 
 * Convexer's main algorithm
 *
 * Return the best availible convex solid from mesh, and patch the existing mesh
 * to fill the gap where the new mesh left it.
 *
 * Returns NULL if shape is already convex or empty.
 * This function will not preserve edge data such as freestyle, sharp etc.
 */
static cxr_mesh *cxr_pull_best_solid(
      cxr_mesh *mesh, 
      int preserve_more_edges,
      u32 *error )
{
   if( !cxr_mesh_link_loops(mesh) )
   {
      cxr_log( "non-manifold edges are in the mesh: "
               "implicit internal geometry does not have full support\n" );

      return NULL;
   }
   
   int *edge_tagged = cxr_mesh_reflex_edges( mesh );
   int *vertex_tagged = cxr_mesh_reflex_vertices( mesh );

   /*
    * Connect all marked vertices that share an edge
    */

   int *edge_important = malloc(mesh->abedges.count*sizeof(int));
   for( int i=0; i< mesh->abedges.count; i++ )
      edge_important[i] = 0;

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

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

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

      edge_unimportant:;
   }

   /*
    * Connect edges where both vertices are reflex, only if we are not
    * preserving them
    */
   for( int i=0; i<mesh->abedges.count; i ++ )
   {
      if( edge_important[i] && preserve_more_edges ) continue;

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

   free( edge_important );
   
   int *faces_tagged = malloc(mesh->abpolys.count*sizeof(int));
   for( int i=0; i<mesh->abpolys.count; i++ )
      faces_tagged[i] = -1;
   
   struct csolid *candidates;
   int *solid_buffer = malloc( mesh->abpolys.count*sizeof(int) ),
        solid_buffer_len = 0,
        candidate_count = 0;

   candidates = malloc( mesh->abpolys.count *sizeof(struct csolid) );
   
   /* 
    * Create a valid, non-overlapping solid for every face present in the mesh
    */
   for( int i=0; i<mesh->abpolys.count; i++ )
   {
      if( faces_tagged[i] != -1 ) continue;
      faces_tagged[i] = i;

      int *solid = &solid_buffer[ solid_buffer_len ];
      int len = cxr_buildsolid( mesh, i, solid, edge_tagged, faces_tagged );

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

   free( edge_tagged );
   free( vertex_tagged );
   free( faces_tagged );

   /*
    * Choosing the best solid: most defined manifold
    */
   struct csolid *best_solid = NULL;
   int fewest_manifold_splits = INT32_MAX;

   struct temp_manifold best_manifold = { .loops = NULL, .loop_count = 0 };
   int max_solid_faces = 0;
   
   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;
      
      struct temp_manifold manifold;
      cxr_link_manifold( mesh, solid, solid_buffer, &manifold);
      
      if( manifold.status == k_manifold_err )
      {
         *error = CXR_ERROR_BAD_MANIFOLD;
         free(solid_buffer);
         free(candidates);
         free(manifold.loops);
         free(best_manifold.loops);
         return NULL;
      }

      if( manifold.status == k_manifold_complete )
      {
         if( manifold.split_count < fewest_manifold_splits )
         {
            fewest_manifold_splits = manifold.split_count;
            best_solid = solid;

            free( best_manifold.loops );
            best_manifold = manifold;
            continue;
         }
      }
      
      if( manifold.status != k_manifold_none )
         free( manifold.loops );
   }

   if( max_solid_faces < 2 )
   {
      *error = CXR_ERROR_NO_SOLIDS;
      free(solid_buffer);
      free(candidates);
      free(best_manifold.loops);
      return NULL;
   }

   if( best_solid != NULL )
   {
      cxr_mesh *pullmesh = cxr_alloc_mesh( best_solid->edge_count, 
                                           best_solid->edge_count, 
                                           best_solid->count, 
                                           mesh->p_abverts );
      
      for( int i=0; i<best_solid->count; i++ )
      {
         int nface_id = pullmesh->abpolys.count;
         int exist_plane_id = solid_buffer[best_solid->start+i];

         cxr_polygon *exist_face = &mesh->polys[ exist_plane_id ],
                     *new_face = cxr_ab_empty( &pullmesh->abpolys );
         
         *new_face = *exist_face;
         new_face->loop_start = pullmesh->abloops.count;

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

            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->abpolys.count;

      if( fewest_manifold_splits != 0 )
      {
         /* Unusual observation:
          *   If the split count is odd, the manifold can be created easily
          *
          *   If it is even, implicit internal geometry is needed to be
          *   constructed. So the manifold gets folded as we create it segment
          *   by segment.
          *
          *   I'm not sure if this is a well defined rule of geometry, but seems
          *   to apply to the data we care about.
          */
         int collapse_used_segments = (u32)fewest_manifold_splits & 0x1? 0: 1;

         manifold_repeat:
         
         for( int j=0; j < best_manifold.loop_count; j++ )
         {
            if( !best_manifold.loops[j].split ) continue;

            cxr_loop *loop = &best_manifold.loops[j].loop;

            for( int k=1; k< best_manifold.loop_count; k++ )
            {
               int index1 = cxr_range(j+k, best_manifold.loop_count );
               cxr_loop *loop1 = &best_manifold.loops[index1].loop;

               if( best_manifold.loops[index1].split )
               {
                  if( k==1 )
                     break;

                  new_polys ++;

                  if( new_polys > best_manifold.loop_count )
                  {
                     cxr_log( "Programming error: Too many new polys!\n" );
                     exit(1);
                  }
                  
                  if( cxr_create_poly( pullmesh, k+1 ) )
                  {
                     for( int l=0; l<k+1; l++ )
                     {
                        int i0 = cxr_range(j+l, best_manifold.loop_count ),
                            index = best_manifold.loops[ i0 ].loop.index;

                        cxr_poly_push_index( pullmesh, index );
                     }
                     cxr_poly_finish( pullmesh );
                  }

                  /* Collapse down manifold */
                  if( collapse_used_segments )
                  {
                     best_manifold.loops[j].split = 0;
                     best_manifold.loops[index1].split = 0;

                     int new_length = (best_manifold.loop_count-(k-1));
                     
                     struct temp_manifold new_manifold = { 
                        .loop_count = new_length 
                     };
                     new_manifold.loops = 
                        malloc( new_length*sizeof(*new_manifold.loops) );
                     
                     for( int l=0; l<new_length; l ++ )
                     {
                        int i_src = cxr_range( j+k+l, best_manifold.loop_count);
                        new_manifold.loops[l] = best_manifold.loops[i_src];
                     }

                     free( best_manifold.loops );
                     best_manifold = new_manifold;

                     goto manifold_repeat;
                  }

                  j=j+k-1;
                  break;
               }
            }
         }
         
         if( best_manifold.loop_count && collapse_used_segments )
         {
            cxr_create_poly_full( pullmesh, &best_manifold );
            new_polys ++;
         }
      }
      else
      {
         cxr_create_poly_full( pullmesh, &best_manifold );
         new_polys = 1;
      }

      if( new_polys >= 3 )
      {
         if( !cxr_build_implicit_geo( pullmesh, new_polys, pullmesh_new_start ))
         {
            free(solid_buffer);
            free(candidates);
            free(best_manifold.loops);
            
            cxr_free_mesh( pullmesh );
            *error = CXR_ERROR_DEGEN_IMPLICIT;
            return NULL;
         }
      }

      /*
       * Copy faces from the pullmesh into original, to patch up where there
       * would be gaps created
       */
      for( int i=0; i<new_polys; i++ )
      {
         int rface_id = mesh->abpolys.count;
         cxr_polygon *pface = &pullmesh->polys[pullmesh_new_start+i],
                  *rip_face = cxr_ab_empty(&mesh->abpolys);

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

            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_update( mesh );
      cxr_mesh_update( pullmesh );

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

      free(solid_buffer);
      free(candidates);
      free(best_manifold.loops);
   
      return pullmesh;
   }

   free(solid_buffer);
   free(candidates);
   free(best_manifold.loops);

   return NULL;
}

/*
 * Convert from the format we recieve from blender into our internal format
 * with auto buffers.
 */
static cxr_mesh *cxr_to_internal_format( 
   cxr_input_mesh *src, 
   cxr_abuffer *abverts
){
   cxr_mesh *mesh = cxr_alloc_mesh( src->edge_count, src->loop_count, 
                                    src->poly_count, abverts );

   cxr_ab_init( abverts, sizeof(v3f), src->vertex_count );

   memcpy( mesh->abedges.arr, src->edges, src->edge_count*sizeof(cxr_edge));
   memcpy( mesh->abpolys.arr, src->polys, src->poly_count*sizeof(cxr_polygon));
   memcpy( abverts->arr, src->vertices, src->vertex_count*sizeof(v3f));
   mesh->abedges.count = src->edge_count;
   mesh->abloops.count = src->loop_count;
   mesh->abpolys.count = src->poly_count;

   cxr_mesh_update( mesh );

   for( int i=0; i<src->loop_count; i++ )
   {
      cxr_loop *lp = &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 most extreme point along a given 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 )
      )
   );
}

/*
 * Convert regular UV'd triangle int Source's u/vaxis vectors
 *
 * This supports affine move, scale, rotation, parallel skewing
 */
static void cxr_calculate_axis( 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 cxr_input_mesh *cxr_write_test_data( cxr_input_mesh *src )
{
   FILE *fp = fopen( 
      "/home/harry/Documents/blender_addons_remote/addons/convexer/src/solid.h",
      "w" );
 
   fprintf( fp, "v3f test_verts[] = {\n" );
   for( int i=0; i<src->vertex_count; i ++ )
   {
      fprintf( fp, "   { %f, %f, %f },\n",
            src->vertices[i][0],
            src->vertices[i][1],
            src->vertices[i][2] );
   }
   fprintf( fp, "};\n" );

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

   fprintf( fp, "struct cxr_polygon test_polys[] = {\n" );
   for( int i=0; i <src->poly_count; i++ )
   {
      fprintf( fp, "   {%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( fp, "};\n" );

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

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

   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 displacement patch
 */
static void cxr_write_disp( cxr_mesh *mesh, cxr_input_mesh *inputmesh, 
      cxr_vdf *output
){
   v3f *verts = cxr_ab_ptr( mesh->p_abverts, 0 );

   struct vertinfo
   {
      int con_start, con_count;
      int boundary,
          used,
          search,
          corner;

      double alpha;
   }
   *vertinfo = malloc( sizeof(struct vertinfo)*mesh->p_abverts->count );
   int *graph = malloc( sizeof(int) * mesh->abedges.count*2 );
   
   int con_pos = 0;
   for( int i=0; i<mesh->p_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->abedges.count; j++ )
      {
         cxr_edge *edge = &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 an
    * reference for decal projection in-game
    */

   v3f avg_normal, refv, refu, refn;
   v3_zero(refv); v3_zero(refu); v3_zero(refn);
   
   for( int i=0; i<mesh->abpolys.count; i++ )
   {
      cxr_polygon *poly = &mesh->polys[i];
      v3_add( poly->normal, avg_normal, avg_normal );
   }
   v3_divs( avg_normal, mesh->abpolys.count, avg_normal );

   if( v3_length( avg_normal ) <= 1e-6 )
      v3_copy( (v3f){ 0.0, 0.0, 1.0 }, avg_normal );
   else
      v3_normalize( avg_normal );      

   /*
    * Approximately match the area of the result brush faces to the actual
    * area.
    *
    * Necessary for accuracy and even lightmap texel allocation
    */

   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->abpolys.count; i++ )
   {
      cxr_polygon *poly = &mesh->polys[i];
      
      for( int j=0; j<poly->loop_total; j++ )
      {
         cxr_loop *lp0 = &mesh->loops[ poly->loop_start+j ];
         v2_minv( lp0->uv, uvboundmin, uvboundmin);
         v2_maxv( lp0->uv, uvboundmax, uvboundmax);
         v3_minv( verts[lp0->index], faceboundmin, faceboundmin );
         v3_maxv( verts[lp0->index], faceboundmax, faceboundmax );
      }

      for( int j=0; j<poly->loop_total-2; j++ )
      {
         cxr_loop *lp0 = &mesh->loops[poly->loop_start],
                  *lp1 = &mesh->loops[poly->loop_start+j+1],
                  *lp2 = &mesh->loops[poly->loop_start+j+2];

         v3f va, vb, orth;
         v3_sub( verts[lp1->index], verts[lp0->index], va );
         v3_sub( verts[lp2->index], verts[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
    *   boundary vertices:   they exist on a freestyle edge
    *   corners:             only connected to other boundaries
    */
   for( int i=0; i<mesh->p_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 ++;
      }
   }
   
   /* 
    * TODO(harry): This currently only supports power 2 displacements
    *              its quite straightforward to upgrade it.
    *
    * TODO(harry): Error checking is needed here for bad input data
    */

   int dispedge[16];
   v2f corner_uvs[4];
   int dispedge_count;
   int disp_count = 0;

   for( int i=0; i<mesh->abpolys.count; i++ )
   {
      cxr_polygon *basepoly = &mesh->polys[i];

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

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

         int corner_count = 1;
         
         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 (use) face from orignal mesh */
         basepoly->loop_total = -1;
         
         while( dispedge_count < 17 )
         {
            struct vertinfo *edge_head =
               &vertinfo[dispedge[dispedge_count-1]];

            int newvert = 0;
            
            if( edge_head->corner )
            {
               /* Find polygon that has edge C-1 -> C */
               for( int j=0; j<mesh->abpolys.count && !newvert; j++ )
               {
                  cxr_polygon *poly = &mesh->polys[j];

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

                     cxr_loop *l0 = &mesh->loops[ poly->loop_start+i0 ],
                              *l1 = &mesh->loops[ poly->loop_start+i1 ];

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

                        int i2 = cxr_range(i1+1,poly->loop_total);
                        cxr_loop *l2 = &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;
                  
                  dispedge[ dispedge_count ++ ] = con;
                  newvert = 1;

                  break;
               }
            }

            if( !newvert )
            {
               cxr_debug_box( verts[dispedge[dispedge_count-1]], 0.1, 
                     colour_error);
               break;
            }
         }
         
         /* All 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];

         /* Fill in grid */
         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 common non-used vertex */
               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 next_cell;
                     }
                  }
               }

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

               next_cell:;
            }
         }
         
         /*
         * 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 )
         {
            cxr_texinfo tx;
            v3f tri_ref[3];
            v3_copy( verts[dispedge[0]], tri_ref[0] );
            v3_copy( verts[dispedge[4]], tri_ref[1] );
            v3_copy( verts[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 );
            
            /* Computing new reference vectors */
            int n1_cardinal = cxr_cardinal( refn, v_cardinal );
            
            int u_cardinal = 0;

            for( int j=0; j<2; j++ )
               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 );
            
            /* Draw reference vectors */
            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 coordinates */
         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 )
         {
            for( int j=0; j<4; j++ )
            {
               double *p0 = world_corners[j],
                      *p1 = world_corners[cxr_range(j+1,4)];

               cxr_debug_arrow( p0, p1, avg_normal, 0.1, colour );
            }
         }
         
         /* Apply world transform */
         for( int j=0; j<8; j++ )
         {
            double *p0 = world_corners[j];
            v3_muls( p0, cxr_context.scale_factor, p0 );

            p0[2] += cxr_context.offset_z;
         }

         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( verts[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 the compilers. Opens fine in 
                * hammer
                */

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

   free( graph );
   free( vertinfo );
}

static int cxr_solid_checkerr( cxr_mesh *mesh )
{
   v3f *verts = cxr_ab_ptr( mesh->p_abverts, 0 );
   int err_count = 0;

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

      cxr_polygon *poly = &mesh->polys[i];
      v4f plane;

      normal_to_plane( poly->normal, poly->center, plane );
      
      for( int j=0; j<poly->loop_total; j++ )
      {
         cxr_loop *loop = &mesh->loops[ poly->loop_start+j ];
         double *vert = verts[ 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, colour_error );
   }
   
   return err_count;
}

CXR_API i32 cxr_convert_mesh_to_vmf(cxr_input_mesh *src, cxr_vdf *output)
{
   cxr_abuffer abverts;
   cxr_mesh *main_mesh = cxr_to_internal_format(src, &abverts);

   u32 error = 0x00;
   int invalid_count = 0;

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

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

   /* 
    * Preprocessor 1: Island seperation
    */
   while(1)
   {
      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 processing & error checks
    */
   for( int i=0; i<solids.count; i++ )
   {
      struct solidinf *pinf = cxr_ab_ptr(&solids,i);
      
      for( int j=0; j<pinf->pmesh->abpolys.count; j++ )
      {
         cxr_polygon *poly = &pinf->pmesh->polys[ j ];

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

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

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

   /*
    * Main convex decomp algorithm
    */
   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)
      {
         cxr_mesh *res = cxr_pull_best_solid( pinf.pmesh, 0, &error );

         if( res )
         {
            cxr_ab_push( &solids, &(struct solidinf){res,0} );
            if( error )
               break;
         }
         else
         {
            if( error )
            {
               /* Retry if non-critical error, with extra edges */

               if( error & CXR_ERROR_NO_SOLIDS )
               {
                  error = 0x00;
                  res = cxr_pull_best_solid(pinf.pmesh, 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, colours_random[cxr_range(i,8)] );
      }
   }
   
   if( error )
   {
      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 error;
   }

   /* Write all solids as 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->abpolys.count; j++ )
      {
         cxr_polygon *poly = &solid->pmesh->polys[j];
         cxr_loop *ploops = &solid->pmesh->loops[poly->loop_start];

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

         int i0 = ploops[0].index,
             i1 = ploops[1].index,
             i2 = ploops[2].index;

         v3_muls( cxr_ab_ptr(&abverts,i0), cxr_context.scale_factor, verts[0] );
         v3_muls( cxr_ab_ptr(&abverts,i1), cxr_context.scale_factor, verts[1] );
         v3_muls( cxr_ab_ptr(&abverts,i2), 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 );
         
         cxr_texinfo tx;
         cxr_calculate_axis( &tx, verts, uvs, 
               (double[2]){ matptr->res[0], matptr->res[1] });

         cxr_vdf_kaxis( output, "uaxis", tx.uaxis, tx.offset[0], tx.scale[0]);
         cxr_vdf_kaxis( output, "vaxis", tx.vaxis, tx.offset[1], tx.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 Source SDK 2015 CS:GO
 */
#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 back to file */
   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;
}