+++ /dev/null
-/*
- 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;
-}
projects / convexer.git / blobdiff