--- /dev/null
+/*
+ CONVEXER v0.9
+
+ 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
+
+ __init__.py Python Blender plugin interface
+
+ cxr/
+ cxr.h C Heavy lifting; brush decomp, mesh processing
+ cxr_math.h C Vector maths and other handy things
+ cxr_mem.h C Automatic resizing buffers
+ libcxr.c C Compile as SO
+
+ nbvtf/
+ nbvtf.h C VTF processing interface
+ librgcx.h C++ Rich Geldreich's DXT1/DXT5 compressors
+ stb/ C Sean Barrets image I/O
+
+
+ HEADER
+ MACROS
+ STD INCLUDE
+ TYPEDEFS
+ INCLUDE
+ STRUCTURE DEFS
+
+ API
+
+ IMPLEMENTATION
+*/
+
+#define CXR_API
+#define CXR_EPSILON 0.001
+#define CXR_PLANE_SIMILARITY_MAX 0.998
+#define CXR_BIG_NUMBER 1e300
+#define CXR_INTERIOR_ANGLE_MAX 0.998
+
+#ifdef CXR_SO
+ #define CXR_IMPLEMENTATION
+#endif
+
+#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];
+
+#include "cxr_math.h"
+#include "cxr_mem.h"
+
+typedef struct cxr_world cxr_world;
+typedef struct cxr_solid cxr_solid;
+
+typedef struct cxr_mesh cxr_mesh;
+typedef struct cxr_edge cxr_edge;
+typedef struct cxr_polygon cxr_polygon;
+typedef struct cxr_static_mesh cxr_static_mesh;
+typedef struct cxr_loop cxr_loop;
+typedef struct cxr_static_loop cxr_static_loop;
+typedef struct cxr_material cxr_material;
+typedef struct cxr_tri_mesh cxr_tri_mesh;
+
+#ifdef CXR_VALVE_MAP_FILE
+ typedef struct cxr_vdf cxr_vdf;
+ typedef struct cxr_texinfo cxr_texinfo;
+ typedef struct cxr_vmf_context cxr_vmf_context;
+#endif /* CXR_VALVE_MAP_FILE */
+
+/*
+ * Public API
+ */
+
+/* Main convexer algorithms */
+/* Convex decomp from mesh */
+CXR_API cxr_world *cxr_decompose( cxr_static_mesh *src );
+CXR_API void cxr_free_world( cxr_world *world );
+CXR_API cxr_tri_mesh *cxr_world_preview( cxr_world *world );
+CXR_API void cxr_free_tri_mesh( cxr_tri_mesh *mesh );
+
+#ifdef CXR_VALVE_MAP_FILE
+/* VMF interface */
+CXR_API void cxr_begin_vmf( cxr_vmf_context *ctx, cxr_vdf *vdf );
+CXR_API void cxr_vmf_begin_entities( cxr_vmf_context *ctx, cxr_vdf *vdf );
+CXR_API void cxr_push_world_vmf(
+ cxr_world *world, cxr_vmf_context *ctx, cxr_vdf *vdf);
+CXR_API void cxr_end_vmf( cxr_vmf_context *ctx, cxr_vdf *vdf );
+
+/* 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 );
+
+/* Other tools */
+CXR_API int cxr_lightpatch_bsp( const char *path );
+#endif /* CXR_VALVE_MAP_FILE */
+
+#ifdef CXR_DEBUG
+/* 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 void cxr_write_test_data( cxr_static_mesh *src );
+#endif /* CXR_DEBUG */
+
+struct cxr_static_mesh
+{
+ v3f *vertices;
+
+ struct cxr_edge
+ {
+ i32 i0, i1;
+ i32 freestyle;
+ }
+ *edges;
+
+ struct cxr_static_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 *name;
+ }
+ *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
+{
+ cxr_mesh *pmesh;
+ int displacement,
+ invalid;
+};
+
+struct cxr_world
+{
+ cxr_abuffer abverts,
+ absolids;
+
+ cxr_material *materials;
+ int material_count;
+};
+
+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;
+};
+
+/* Simple mesh type mainly for debugging */
+struct cxr_tri_mesh
+{
+ v3f *vertices;
+ v4f *colours;
+ i32 *indices,
+ indices_count,
+ vertex_count;
+};
+
+#ifdef CXR_VALVE_MAP_FILE
+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;
+};
+
+struct cxr_vmf_context
+{
+ /* File info */
+ i32 mapversion;
+ const char *skyname,
+ *detailvbsp,
+ *detailmaterial;
+
+ /* Transform settings */
+ double scale;
+ v3f offset;
+ i32 lightmap_scale;
+
+ /* Current stats */
+ i32 brush_count,
+ entity_count,
+ face_count;
+};
+#endif /* CXR_VALVE_MAP_FILE */
+
+enum cxr_soliderr
+{
+ k_soliderr_none = 0,
+ k_soliderr_non_manifold,
+ k_soliderr_bad_manifold,
+ k_soliderr_no_solids,
+ k_soliderr_degenerate_implicit
+};
+
+/*
+ * Implementation
+ * -----------------------------------------------------------------------------
+ */
+#ifdef CXR_IMPLEMENTATION
+ #ifdef CXR_SO
+ const char *cxr_build_time = __DATE__ " @" __TIME__;
+ #endif
+
+static void (*cxr_log_func)(const char *str);
+static void (*cxr_line_func)( v3f p0, v3f p1, v4f colour );
+
+static int cxr_range(int x, int bound)
+{
+ if( x < 0 )
+ x += bound * (x/bound + 1);
+
+ return x % bound;
+}
+
+/*
+ * 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 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 v4f colours_solids[] =
+{
+ { 100, 143, 255, 200 },
+ { 120, 94, 240, 200 },
+ { 220, 38, 127, 200 },
+ { 254, 97, 0, 200 },
+ { 255, 176, 0, 200 }
+};
+
+static v4f colour_entity = { 37, 241, 122, 255 };
+static v4f colour_displacement_solid = { 146, 146, 146, 120 };
+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 value_random(int n, v4f colour)
+{
+ double val = cxr_range(n,8);
+ val /= 16.0;
+ val += 0.75;
+
+ v3_muls( colour, val, colour );
+}
+
+static void colour_random_brush(int n, v4f colour)
+{
+#if 1
+ int value_n = n / 5;
+ int colour_n = cxr_range( n, 5 );
+ v4_muls( colours_solids[ colour_n ], 1.0/255.0, colour );
+ value_random( value_n, colour );
+#else
+ int colour_n = cxr_range( n, 8 );
+ v4_copy( colours_random[ colour_n ], colour );
+#endif
+}
+
+/*
+ * Debugging and diagnostic utilities
+ * -----------------------------------------------------------------------------
+ */
+
+#ifdef CXR_DEBUG
+
+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 );
+}
+
+/*
+ * 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.0075, p0 );
+ v3_lerp( verts[i1], poly->center, 0.0075, p1 );
+ v3_muladds( p0, poly->normal, 0.01, p0 );
+ v3_muladds( p1, poly->normal, 0.01, 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 );
+ }
+}
+
+CXR_API void cxr_write_test_data( cxr_static_mesh *src )
+{
+ FILE *fp = fopen(
+ "/home/harry/Documents/blender_addons_remote/addons/convexer/cxr/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_static_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_static_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 );
+}
+
+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;
+}
+
+#endif /* CXR_DEBUG */
+
+
+/*
+ * 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 )
+ {
+#ifdef CXR_DEBUG
+ cxr_log( "tried to add new poly with length %d!\n", loop_count );
+#endif
+ 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
+){
+ 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];
+
+ 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 )
+ {
+ free( unique_verts );
+ return 1;
+ }
+ }
+ }
+ }
+
+ 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))
+ 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 )
+ {
+#ifdef CXR_DEBUG
+ 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] );
+#endif
+
+ 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,
+ enum cxr_soliderr *err )
+{
+ *err = k_soliderr_none;
+
+ if( !cxr_mesh_link_loops(mesh) )
+ {
+#ifdef CXR_DEBUG
+ cxr_log( "non-manifold edges are in the mesh: "
+ "implicit internal geometry does not have full support\n" );
+#endif
+ *err = k_soliderr_non_manifold;
+ 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 )
+ {
+ *err = k_soliderr_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 )
+ {
+ *err = k_soliderr_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 )
+ {
+#ifdef CXR_DEBUG
+ cxr_log( "Programming error: Too many new polys!\n" );
+#endif
+ 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 );
+ *err = k_soliderr_degenerate_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_static_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;
+}
+
+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 );
+
+#ifdef CXR_DEBUG
+ cxr_debug_line( ref, vert, colour_error );
+ cxr_debug_box( vert, 0.1, colour_error );
+#endif
+ }
+ }
+
+#ifdef CXR_DEBUG
+ if( plane_err )
+ cxr_debug_poly( mesh, poly, colour_error );
+#endif
+ }
+
+ return err_count;
+}
+
+CXR_API void cxr_free_world( cxr_world *world )
+{
+ for( int i=0; i<world->absolids.count; i++ )
+ {
+ cxr_solid *solid = cxr_ab_ptr( &world->absolids, i );
+ cxr_free_mesh( solid->pmesh );
+ }
+
+ cxr_ab_free( &world->abverts );
+ cxr_ab_free( &world->absolids );
+ free( world->materials );
+ free( world );
+}
+
+CXR_API cxr_tri_mesh *cxr_world_preview( cxr_world *world )
+{
+ cxr_tri_mesh *out = malloc( sizeof(cxr_tri_mesh) );
+ out->vertex_count = 0;
+ out->indices_count = 0;
+
+ for( int i=0; i<world->absolids.count; i++ )
+ {
+ cxr_solid *solid = cxr_ab_ptr( &world->absolids, i );
+ cxr_mesh *mesh = solid->pmesh;
+
+ for( int j=0; j<mesh->abpolys.count; j ++ )
+ {
+ cxr_polygon *poly = &mesh->polys[j];
+
+ out->vertex_count += poly->loop_total * 3; /* Polygon, edge strip */
+ out->indices_count += (poly->loop_total -2) * 3; /* Polygon */
+ out->indices_count += poly->loop_total * 2 * 3; /* Edge strip */
+ }
+ }
+
+ out->colours = malloc( sizeof(v4f)*out->vertex_count );
+ out->vertices = malloc( sizeof(v3f)*out->vertex_count );
+ out->indices = malloc( sizeof(i32)*out->indices_count );
+
+ v3f *overts = out->vertices;
+ v4f *colours = out->colours;
+ i32 *indices = out->indices;
+
+ int vi = 0,
+ ii = 0;
+
+ for( int i=0; i<world->absolids.count; i++ )
+ {
+ cxr_solid *solid = cxr_ab_ptr( &world->absolids, i );
+ cxr_mesh *mesh = solid->pmesh;
+
+ v3f *verts = cxr_ab_ptr( mesh->p_abverts, 0 );
+ v4f colour;
+
+ colour_random_brush( i, colour );
+
+ for( int j=0; j<mesh->abpolys.count; j ++ )
+ {
+ cxr_polygon *poly = &mesh->polys[j];
+
+ int istart = vi;
+
+ for( int k=0; k<poly->loop_total-2; k++ )
+ {
+ int i0 = 0,
+ i1 = (k+1)*3,
+ i2 = (k+2)*3;
+
+ indices[ ii ++ ] = istart+i0;
+ indices[ ii ++ ] = istart+i1;
+ indices[ ii ++ ] = istart+i2;
+ }
+
+ for( int k=0; k<poly->loop_total; k++ )
+ {
+ cxr_loop *lp = &mesh->loops[poly->loop_start+k];
+
+ int i0r = k*3+1,
+ i1r = cxr_range(k+1,poly->loop_total)*3+1,
+ i0i = k*3+2,
+ i1i = cxr_range(k+1,poly->loop_total)*3+2;
+
+ indices[ ii ++ ] = istart+i0i;
+ indices[ ii ++ ] = istart+i1i;
+ indices[ ii ++ ] = istart+i1r;
+
+ indices[ ii ++ ] = istart+i0i;
+ indices[ ii ++ ] = istart+i1r;
+ indices[ ii ++ ] = istart+i0r;
+
+ /* Main */
+ v3_muladds( verts[lp->index], poly->normal, 0.02, overts[vi] );
+ v4_copy( colour, colours[ vi ] );
+ vi ++;
+
+ /* Trim */
+ v3f inner;
+ v3_lerp( verts[lp->index], poly->center, 0.2, inner );
+ v3_muladds( inner, poly->normal, 0.015, overts[ vi ] );
+ v4_copy( colour, colours[ vi ] );
+ v4_copy( (v4f){ 0.0, 0.0, 0.0, 0.0 }, colours[vi] );
+ vi ++;
+
+ v3_muladds(verts[lp->index], poly->normal, 0.0, overts[ vi ] );
+ v4_copy( colour, colours[ vi ] );
+ v4_copy( (v4f){ 1.0, 1.0, 1.0, 0.125 }, colours[vi] );
+ vi ++;
+ }
+ }
+ }
+
+ return out;
+}
+
+CXR_API void cxr_free_tri_mesh( cxr_tri_mesh *mesh )
+{
+ free( mesh->colours );
+ free( mesh->indices );
+ free( mesh->vertices );
+ free( mesh );
+}
+
+CXR_API cxr_world *cxr_decompose( cxr_static_mesh *src )
+{
+ cxr_world *world = malloc( sizeof(*world) );
+
+ /* Copy data to internal formats */
+ cxr_mesh *main_mesh = cxr_to_internal_format( src, &world->abverts );
+ cxr_ab_init( &world->absolids, sizeof(cxr_solid), 2 );
+
+ if( src->material_count )
+ {
+ size_t dsize = sizeof(cxr_material) * src->material_count;
+ world->materials = malloc( dsize );
+ memcpy( world->materials, src->materials, dsize );
+ }
+ else world->materials = NULL;
+
+ int invalid_count = 0;
+
+ /*
+ * Preprocessor 1: Island seperation
+ */
+ while(1)
+ {
+ cxr_mesh *res = cxr_pull_island( main_mesh );
+ if( res )
+ {
+ cxr_ab_push( &world->absolids, &(cxr_solid){ res, 0, 0 });
+ }
+ else break;
+ }
+ cxr_ab_push( &world->absolids, &(cxr_solid){ main_mesh, 0, 0 } );
+
+ /*
+ * Preprocessor 2: Displacement processing & error checks
+ */
+ for( int i=0; i<world->absolids.count; i++ )
+ {
+ cxr_solid *pinf = cxr_ab_ptr(&world->absolids,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 displacement;
+ }
+ }
+
+ if( cxr_solid_checkerr( pinf->pmesh ) )
+ {
+ pinf->invalid = 1;
+ invalid_count ++;
+ }
+
+ continue;
+
+ displacement:
+ pinf->displacement = 1;
+ }
+
+ /*
+ * Main convex decomp algorithm
+ */
+ int sources_count = world->absolids.count;
+ u32 error = 0x00;
+
+ if( invalid_count )
+ goto decomp_failed;
+
+ for( int i=0; i<sources_count; i++ )
+ {
+ cxr_solid pinf = *(cxr_solid *)cxr_ab_ptr(&world->absolids, i);
+
+ if( pinf.displacement || pinf.invalid )
+ continue;
+
+ while(1)
+ {
+ cxr_mesh *res = cxr_pull_best_solid( pinf.pmesh, 0, &error );
+
+ if( res )
+ {
+ cxr_ab_push( &world->absolids, &(cxr_solid){ res, 0, 0 } );
+ }
+ else
+ {
+ if( error == k_soliderr_no_solids )
+ {
+ /* Retry if non-critical error, with extra edges */
+ res = cxr_pull_best_solid(pinf.pmesh, 1, &error);
+
+ if( res )
+ cxr_ab_push( &world->absolids, &(cxr_solid){ res, 0, 0 } );
+ else
+ goto decomp_failed;
+ }
+ else
+ if( error )
+ goto decomp_failed;
+ else
+ break;
+ }
+ }
+ }
+
+ return world;
+
+decomp_failed:
+ cxr_log( "Error %d\n", error );
+ cxr_free_world( world );
+ return NULL;
+}
+
+/*
+ * format specific functions: vdf, vmf, (v)bsp
+ * ----------------------------------------------------------------------------
+ */
+#ifdef CXR_VALVE_MAP_FILE
+
+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]);
+}
+
+static struct cxr_material cxr_nodraw =
+{
+ .res = { 512, 512 },
+ .name = "tools/toolsnodraw"
+};
+
+/*
+ * 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;
+}
+
+/*
+ * Get the maximal direction of a vector, while also ignoring an axis
+ * specified
+ */
+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 int cxr_write_disp( cxr_mesh *mesh, cxr_world *world,
+ cxr_vmf_context *ctx, 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;
+ }
+ }
+ }
+
+ v3f refv, refu, refn;
+ v3_zero(refv); v3_zero(refu); v3_zero(refn);
+
+ /*
+ * 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 || !world->materials?
+ &cxr_nodraw:
+ &world->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 )
+ {
+ return 0;
+ }
+ }
+
+ /* 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;
+ }
+ }
+ }
+
+#ifdef CXR_DEBUG
+ cxr_log( "Broken displacement!\n" );
+#endif
+ free( graph );
+ free( vertinfo );
+ return 0;
+
+ 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 );
+ }
+
+ /* 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] );
+
+ /* Apply world transform */
+ for( int j=0; j<8; j++ )
+ {
+ double *p0 = world_corners[j];
+ v3_muls( p0, ctx->scale, p0 );
+ v3_add( p0, ctx->offset, p0 );
+ }
+
+ 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", ++ ctx->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]], ctx->scale, vworld );
+ v3_add( ctx->offset, vworld, ctx->offset );
+
+ 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", ++ ctx->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->name );
+
+ 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", ctx->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(ctx->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 );
+
+ return 1;
+}
+
+/*
+ * Write header information for a vmf to vdf
+ */
+CXR_API void cxr_begin_vmf( cxr_vmf_context *ctx, cxr_vdf *output )
+{
+ cxr_vdf_node( output, "versioninfo" );
+ cxr_vdf_ki32( output, "editorversion", 400 );
+ cxr_vdf_ki32( output, "editorbuild", 8456 );
+ cxr_vdf_ki32( output, "mapversion", ctx->mapversion );
+ cxr_vdf_ki32( output, "formatversion", 100 );
+ cxr_vdf_ki32( output, "prefab", 0 );
+ cxr_vdf_edon( output );
+
+ cxr_vdf_node( output, "visgroups" );
+ cxr_vdf_edon( output );
+
+ cxr_vdf_node( output, "viewsettings" );
+ cxr_vdf_ki32( output, "bSnapToGrid", 1 );
+ cxr_vdf_ki32( output, "bShowGrid", 1 );
+ cxr_vdf_ki32( output, "bShowLogicalGrid", 0 );
+ cxr_vdf_ki32( output, "nGridSpacing", 64 );
+ cxr_vdf_ki32( output, "bShow3DGrid", 0 );
+ cxr_vdf_edon( output );
+
+ cxr_vdf_node( output, "world" );
+ cxr_vdf_ki32( output, "id", 1 );
+ cxr_vdf_ki32( output, "mapversion", 1 ); /* ?? */
+ cxr_vdf_kv( output, "classname", "worldspawn" );
+ cxr_vdf_kv( output, "skyname", ctx->skyname );
+ cxr_vdf_ki32( output, "maxpropscreenwidth", -1 );
+ cxr_vdf_kv( output, "detailvbsp", ctx->detailvbsp );
+ cxr_vdf_kv( output, "detailmaterial", ctx->detailmaterial );
+}
+
+/* Fairly useless but might need in the future */
+CXR_API void cxr_vmf_begin_entities( cxr_vmf_context *ctx, cxr_vdf *vdf )
+{
+ cxr_vdf_edon( vdf );
+}
+
+CXR_API void cxr_end_vmf( cxr_vmf_context *ctx, cxr_vdf *vdf )
+{
+}
+
+/*
+ * Write solids (and displacements) to VMF file
+ */
+CXR_API void cxr_push_world_vmf( cxr_world *world, cxr_vmf_context *ctx,
+ cxr_vdf *output
+){
+ v3f *verts = cxr_ab_ptr( &world->abverts, 0 );
+
+ /* Write all solids as VMF brushes */
+ for( int i=0; i<world->absolids.count; i++ )
+ {
+ cxr_solid *solid = cxr_ab_ptr(&world->absolids,i);
+
+ if( solid->displacement )
+ {
+ cxr_write_disp( solid->pmesh, world, ctx, output );
+ continue;
+ }
+
+ cxr_vdf_node( output, "solid" );
+ cxr_vdf_ki32( output, "id", ++ ctx->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 || !world->materials?
+ &cxr_nodraw:
+ &world->materials[ poly->material_id ];
+
+ cxr_vdf_node( output, "side" );
+ cxr_vdf_ki32( output, "id", ++ ctx->face_count );
+
+ v3f tri[3]; v2f uvs[3];
+
+ int i0 = ploops[0].index,
+ i1 = ploops[1].index,
+ i2 = ploops[2].index;
+
+ v3_muls( verts[i0], ctx->scale, tri[0] );
+ v3_muls( verts[i1], ctx->scale, tri[1] );
+ v3_muls( verts[i2], ctx->scale, tri[2] );
+
+ v3_add( ctx->offset, tri[0], tri[0] );
+ v3_add( ctx->offset, tri[1], tri[1] );
+ v3_add( ctx->offset, tri[2], tri[2] );
+
+ 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", tri[2], tri[1], tri[0] );
+ cxr_vdf_kv( output, "material", matptr->name );
+
+ cxr_texinfo tx;
+ cxr_calculate_axis( &tx, tri, 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", ctx->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(ctx->brush_count,8)]);
+
+ cxr_vdf_ki32( output, "visgroupshown", 1 );
+ cxr_vdf_ki32( output, "visgroupautoshown", 1 );
+ cxr_vdf_edon( output );
+
+ cxr_vdf_edon( output );
+ }
+}
+
+/*
+ * 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 )
+ {
+#ifdef CXR_DEBUG
+ cxr_log( "Could not open BSP file for editing (r+b)\n" );
+#endif
+ 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 );
+
+#ifdef CXR_DEBUG
+ cxr_log( "removed %d marked lights\n", light_count-new_count );
+#endif
+
+ fclose( fp );
+ free( lights );
+
+ return 1;
+}
+#endif /* CXR_VALVE_MAP_FILE */
+#endif /* CXR_IMPLEMENTATION */