From b5ba4ec14b8e215a38cd9072de17fe40f48cea48 Mon Sep 17 00:00:00 2001 From: hgn Date: Sat, 9 Apr 2022 22:54:43 +0100 Subject: [PATCH 1/1] Refactor el big #1 --- .gitignore | 2 + src/convexer.c | 1350 ++++++++++++++++++++++++++++-------------------- src/cxr_math.h | 60 +++ src/cxr_mem.h | 5 +- src/test.c | 5 +- 5 files changed, 850 insertions(+), 572 deletions(-) diff --git a/.gitignore b/.gitignore index 5f407ef..00b2e1f 100644 --- a/.gitignore +++ b/.gitignore @@ -5,3 +5,5 @@ !*.c !*.h !*.py + +Makefile diff --git a/src/convexer.c b/src/convexer.c index 28f7056..773a3d3 100644 --- a/src/convexer.c +++ b/src/convexer.c @@ -98,6 +98,18 @@ static int cxr_range(int x, int bound) 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; @@ -157,9 +169,18 @@ struct cxr_solid struct cxr_mesh { struct cxr_auto_buffer - edges, - loops, - polys; + 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 @@ -212,6 +233,16 @@ static struct cxr_material cxr_nodraw = { .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); +} + // Debugging callbacks // ============================================================================= @@ -307,9 +338,9 @@ CXR_API void cxr_set_scale_factor(double scale) cxr_context.scale_factor = scale; } -CXR_API struct cxr_vdf *cxr_vdf_open(const char *path) +CXR_API cxr_vdf *cxr_vdf_open(const char *path) { - struct cxr_vdf *vdf = malloc(sizeof(struct cxr_vdf)); + cxr_vdf *vdf = malloc(sizeof(cxr_vdf)); vdf->level = 0; vdf->fp = fopen( path, "w" ); @@ -323,12 +354,13 @@ CXR_API struct cxr_vdf *cxr_vdf_open(const char *path) return vdf; } -CXR_API void cxr_vdf_close(struct cxr_vdf *vdf) +CXR_API void cxr_vdf_close(cxr_vdf *vdf) { fclose( vdf->fp ); + free( vdf ); } -CXR_API void cxr_vdf_put(struct cxr_vdf *vdf, const char *str) +CXR_API void cxr_vdf_put(cxr_vdf *vdf, const char *str) { for( int i=0; ilevel; i++ ) fputs( " ", vdf->fp ); @@ -336,7 +368,7 @@ CXR_API void cxr_vdf_put(struct cxr_vdf *vdf, const char *str) fputs( str, vdf->fp ); } -static void cxr_vdf_printf( struct cxr_vdf *vdf, const char *fmt, ... ) +static void cxr_vdf_printf( cxr_vdf *vdf, const char *fmt, ... ) { cxr_vdf_put(vdf,""); @@ -346,7 +378,7 @@ static void cxr_vdf_printf( struct cxr_vdf *vdf, const char *fmt, ... ) va_end(args); } -CXR_API void cxr_vdf_node(struct cxr_vdf *vdf, const char *str) +CXR_API void cxr_vdf_node(cxr_vdf *vdf, const char *str) { cxr_vdf_put( vdf, str ); putc( (u8)'\n', vdf->fp ); @@ -355,34 +387,34 @@ CXR_API void cxr_vdf_node(struct cxr_vdf *vdf, const char *str) vdf->level ++; } -CXR_API void cxr_vdf_edon(struct cxr_vdf *vdf) +CXR_API void cxr_vdf_edon(cxr_vdf *vdf) { vdf->level --; cxr_vdf_put( vdf, "}\n" ); } -CXR_API void cxr_vdf_kv(struct cxr_vdf *vdf, const char *strk, const char *strv) +CXR_API void cxr_vdf_kv(cxr_vdf *vdf, const char *strk, const char *strv) { cxr_vdf_printf( vdf, "\"%s\" \"%s\"\n", strk, strv ); } -static void cxr_vdf_ki32(struct cxr_vdf *vdf, const char *strk, i32 val) +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(struct cxr_vdf *vdf, const char *strk, double 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(struct cxr_vdf *vdf, const char *strk, v3f normal, double offset, double scale) +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(struct cxr_vdf *vdf, const char *strk, v3f v) +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(struct cxr_vdf *vdf, const char *strk, int id, double *doubles, int count) +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 ); @@ -393,7 +425,7 @@ static void cxr_vdf_karrdouble(struct cxr_vdf *vdf, const char *strk, int id, do } fprintf( vdf->fp, "\"\n" ); } -static void cxr_vdf_karrv3f(struct cxr_vdf *vdf, const char *strk, int id, v3f *vecs, int count) +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 ); @@ -404,12 +436,12 @@ static void cxr_vdf_karrv3f(struct cxr_vdf *vdf, const char *strk, int id, v3f * } fprintf( vdf->fp, "\"\n" ); } -static void cxr_vdf_plane(struct cxr_vdf *vdf, const char *strk, v3f a, v3f b, v3f c ) +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(struct cxr_vdf *vdf, const char *strk, v4f colour) +static void cxr_vdf_colour255(cxr_vdf *vdf, const char *strk, v4f colour) { v4f scale; v4_muls( colour, 255.0, scale ); @@ -419,17 +451,24 @@ static void cxr_vdf_colour255(struct cxr_vdf *vdf, const char *strk, v4f colour) // Public API // ========================================================================= -static void cxr_debug_poly(struct cxr_mesh *mesh, struct cxr_polygon *poly, v3f *verts, v4f colour ) +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; iloop_total; i++ ) { - struct cxr_loop *loop0 = cxr_ab_ptr(&mesh->loops,poly->loop_start+i), - *loop1 = cxr_ab_ptr(&mesh->loops,poly->loop_start+cxr_range(i+1,poly->loop_total)); + 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[loop0->index], poly->center, 0.02, p0 ); - v3_lerp( verts[loop1->index], poly->center, 0.02, 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 ); } @@ -440,47 +479,55 @@ static void cxr_debug_poly(struct cxr_mesh *mesh, struct cxr_polygon *poly, v3f cxr_debug_line( poly->center, nrm0, colour ); } -static void cxr_debug_mesh(struct cxr_mesh *mesh, v3f *verts, v4f colour ) +static void cxr_debug_mesh(cxr_mesh *mesh, v4f colour ) { - for( int i=0; ipolys.count; i++ ) + for( int i=0; iabpolys.count; i++ ) { - struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys,i); - cxr_debug_poly( mesh, poly, verts, colour ); + cxr_polygon *poly = &mesh->polys[i]; + cxr_debug_poly( mesh, poly, colour ); } } -static struct cxr_mesh *cxr_alloc_mesh(int edge_count, int loop_count, int poly_count ) +static cxr_mesh *cxr_alloc_mesh(int edge_count, + int loop_count, + int poly_count, + cxr_auto_buffer *abverts) { - struct cxr_mesh *mesh = malloc(sizeof(struct cxr_mesh)); - cxr_ab_init(&mesh->edges, sizeof(struct cxr_edge), edge_count); - cxr_ab_init(&mesh->loops, sizeof(struct cxr_loop), loop_count); - cxr_ab_init(&mesh->polys, sizeof(struct cxr_polygon), poly_count); + 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(struct cxr_mesh *mesh) +static void cxr_free_mesh(cxr_mesh *mesh) { - cxr_ab_free(&mesh->edges); - cxr_ab_free(&mesh->loops); - cxr_ab_free(&mesh->polys); + cxr_ab_free(&mesh->abedges); + cxr_ab_free(&mesh->abloops); + cxr_ab_free(&mesh->abpolys); free(mesh); } -// Rebuilds edge data and reallocates -// -static void cxr_mesh_clean_edges(struct cxr_mesh *mesh) +/* + * Rebuilds edge data for mesh (useful to get rid of orphaned edges) + */ +static void cxr_mesh_clean_edges(cxr_mesh *mesh) { - struct cxr_auto_buffer new_edges; - cxr_ab_init( &new_edges, sizeof(struct cxr_edge), mesh->edges.count ); + cxr_auto_buffer new_edges; + cxr_ab_init( &new_edges, sizeof(cxr_edge), mesh->abedges.count ); - for( int i=0; ipolys.count; i++ ) + for( int i=0; iabpolys.count; i++ ) { - struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys,i); + cxr_polygon *poly = &mesh->polys[i]; for( int j=0; jloop_total; j++ ) { - struct cxr_loop - *lp0 = cxr_ab_ptr(&mesh->loops,poly->loop_start+j), - *lp1 = cxr_ab_ptr(&mesh->loops,poly->loop_start+cxr_range(j+1,poly->loop_total)); + 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); @@ -488,7 +535,7 @@ static void cxr_mesh_clean_edges(struct cxr_mesh *mesh) // See if edge exists before adding it for( int k=0; ki0 == i0 && edge->i1 == i1 ) { @@ -500,13 +547,13 @@ static void cxr_mesh_clean_edges(struct cxr_mesh *mesh) int orig_edge_id = lp0->edge_index; lp0->edge_index = new_edges.count; - struct cxr_edge edge = { i0, i1 }; + cxr_edge edge = { i0, i1 }; // --- ! --- // Copy extra information (sharp,freestyle.. etc) here! - if( orig_edge_id < mesh->edges.count ) + if( orig_edge_id < mesh->abedges.count ) { - struct cxr_edge *orig_edge = cxr_ab_ptr( &mesh->edges, orig_edge_id ); + cxr_edge *orig_edge = &mesh->edges[ orig_edge_id ]; edge.freestyle = orig_edge->freestyle; } else @@ -521,22 +568,26 @@ IL_EDGE_CREATED:; } } - cxr_ab_free( &mesh->edges ); - mesh->edges = new_edges; + cxr_ab_free( &mesh->abedges ); + mesh->abedges = new_edges; + + cxr_mesh_update( mesh ); } -// Remove 0-length faces from mesh and correct loops -// -static void cxr_mesh_clean_faces(struct cxr_mesh *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) { - struct cxr_auto_buffer loops_new; - cxr_ab_init( &loops_new, sizeof(struct cxr_loop), mesh->loops.count ); + cxr_auto_buffer loops_new; + cxr_ab_init( &loops_new, sizeof(cxr_loop), mesh->abloops.count ); int new_length=0; - for( int i=0; ipolys.count; i++ ) + for( int i=0; iabpolys.count; i++ ) { - struct cxr_polygon *src = cxr_ab_ptr(&mesh->polys,i), - *dst = cxr_ab_ptr(&mesh->polys,new_length); + cxr_polygon *src = &mesh->polys[i], + *dst = &mesh->polys[new_length]; if( src->loop_total > 0 ) { @@ -548,8 +599,8 @@ static void cxr_mesh_clean_faces(struct cxr_mesh *mesh) for( int j=0; jloops,src_start+j), - *ldst = cxr_ab_ptr(&loops_new,dst->loop_start+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; } @@ -559,25 +610,33 @@ static void cxr_mesh_clean_faces(struct cxr_mesh *mesh) } } - cxr_ab_free( &mesh->loops ); - mesh->loops = loops_new; - mesh->polys.count = new_length; + cxr_ab_free( &mesh->abloops ); + mesh->abloops = loops_new; + mesh->abpolys.count = new_length; + + cxr_mesh_update( mesh ); } -static i32 *cxr_mesh_link_loops(struct cxr_mesh *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->edges.count*2 *sizeof(i32)); + i32 *polygon_edge_map = malloc(mesh->abedges.count*2 *sizeof(i32)); - for( int i = 0; i < mesh->edges.count*2; i ++ ) + for( int i = 0; i < mesh->abedges.count*2; i ++ ) polygon_edge_map[i] = -1; - for( int i = 0; i < mesh->polys.count; i ++ ) + for( int i = 0; i < mesh->abpolys.count; i ++ ) { - struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys, i); + cxr_polygon *poly = &mesh->polys[i]; for( int j = 0; j < poly->loop_total; j ++ ) { - struct cxr_loop *loop = cxr_ab_ptr(&mesh->loops, poly->loop_start+j); + cxr_loop *loop = &mesh->loops[ poly->loop_start+j ]; loop->poly_left = i; for( int k = 0; k < 2; k ++ ) @@ -592,28 +651,47 @@ static i32 *cxr_mesh_link_loops(struct cxr_mesh *mesh) } } } - for( int i = 0; i < mesh->polys.count; i ++ ) + for( int i = 0; i < mesh->abpolys.count; i ++ ) { - struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys,i); + cxr_polygon *poly = &mesh->polys[i]; for( int j = 0; j < poly->loop_total; j ++ ) { - struct cxr_loop *loop = cxr_ab_ptr(&mesh->loops,poly->loop_start+j); + cxr_loop *loop = &mesh->loops[ poly->loop_start+j ]; - i32 *face_map = &polygon_edge_map[loop->edge_index*2]; + i32 *face_map = &polygon_edge_map[ loop->edge_index*2 ]; if( face_map[0] == loop->poly_left ) loop->poly_right = face_map[1]; else loop->poly_right = face_map[0]; } } - return polygon_edge_map; + + for( int i=0; iabedges.count*2; i++ ) + { + if( polygon_edge_map[i] == -1 ) + { + free( polygon_edge_map ); + return 0; + } + } + + free( polygon_edge_map ); + return 1; } -// Add polygon to mesh based on loop array -static struct cxr_polygon *cxr_create_poly( struct cxr_mesh *mesh, v3f *vertices, struct cxr_loop poly[], - int len, int start, int max ) +/* + * Add polygon to mesh based on array of loops + */ +static cxr_polygon *cxr_create_poly( + cxr_mesh *mesh, + cxr_loop poly[], + int len, + int start, + int max ) { + v3f *verts = cxr_ab_ptr( mesh->p_abverts, 0 ); + if( len < 3 ) { cxr_log( "tried to add new poly with length %d!\n", len ); @@ -624,27 +702,28 @@ static struct cxr_polygon *cxr_create_poly( struct cxr_mesh *mesh, v3f *vertices { int i0 = poly[j].index, i1 = poly[cxr_range(j+1,len)].index; - cxr_debug_line( vertices[i0], vertices[i1], colour_error ); + + cxr_debug_line( verts[i0], verts[i1], colour_error ); } } return NULL; } - int nface_id = mesh->polys.count; - struct cxr_polygon *new_face = cxr_ab_empty(&mesh->polys); + int nface_id = mesh->abpolys.count; + cxr_polygon *new_face = cxr_ab_empty(&mesh->abpolys); + + /* Calculate new face information; normal, center etc */ - new_face->loop_start = mesh->loops.count; + new_face->loop_start = mesh->abloops.count; new_face->loop_total = len; new_face->material_id = -1; - - // Calculate normal and center v3_zero( new_face->center ); for( int j=0; jloops); + cxr_loop *new_loop = cxr_ab_empty(&mesh->abloops); new_loop->poly_left = nface_id; new_loop->poly_right = -1; @@ -652,43 +731,47 @@ static struct cxr_polygon *cxr_create_poly( struct cxr_mesh *mesh, v3f *vertices new_loop->edge_index = 0; v2_zero(new_loop->uv); - v3_add( new_face->center, vertices[new_loop->index], new_face->center ); + v3_add( new_face->center, verts[new_loop->index], new_face->center ); } v3_divs( new_face->center, new_face->loop_total, new_face->center ); - struct cxr_loop *lp0 = cxr_ab_ptr( &mesh->loops, new_face->loop_start ), - *lp1 = cxr_ab_ptr( &mesh->loops, new_face->loop_start+1 ), - *lp2 = cxr_ab_ptr( &mesh->loops, new_face->loop_start+2 ); + cxr_loop *lp0 = cxr_ab_ptr( &mesh->abloops, new_face->loop_start ), + *lp1 = cxr_ab_ptr( &mesh->abloops, new_face->loop_start+1 ), + *lp2 = cxr_ab_ptr( &mesh->abloops, new_face->loop_start+2 ); - tri_normal( vertices[lp0->index], vertices[lp1->index], vertices[lp2->index], new_face->normal ); - - return cxr_ab_ptr(&mesh->polys, nface_id); + tri_normal( + verts[lp0->index], verts[lp1->index], verts[lp2->index], new_face->normal); + + cxr_mesh_update( mesh ); + return &mesh->polys[ nface_id ]; } -// Get the 'next' mesh island -// -// Returns NULL if there is only one island -static struct cxr_mesh *cxr_pull_island(struct cxr_mesh *mesh) +/* + * Extract the next island from mesh + * + * Returns NULL if mesh is one contigous object + */ +static cxr_mesh *cxr_pull_island( cxr_mesh *mesh ) { - free(cxr_mesh_link_loops(mesh)); + cxr_mesh_link_loops(mesh); - int *island_current = malloc(mesh->polys.count*sizeof(int)), + int *island_current = malloc(mesh->abpolys.count*sizeof(int)), island_len = 1, loop_count = 0, last_count; island_current[0] = 0; - IL_ISLAND_REPEAT: + island_grow: last_count = island_len; for( int i=0; ipolys,island_current[i]); + cxr_polygon *poly = &mesh->polys[ island_current[i] ]; for( int j=0; jloop_total; j++ ) { - struct cxr_loop *loop = cxr_ab_ptr(&mesh->loops, poly->loop_start+j); + cxr_loop *loop = &mesh->loops[ poly->loop_start+j ]; if( loop->poly_right != -1 ) { @@ -704,17 +787,16 @@ static struct cxr_mesh *cxr_pull_island(struct cxr_mesh *mesh) } if( !face_present ) - { island_current[ island_len ++ ] = loop->poly_right; - } } } } if( island_len > last_count ) - goto IL_ISLAND_REPEAT; + goto island_grow; - if( island_len == mesh->polys.count ) + /* Check for complete object */ + if( island_len == mesh->abpolys.count ) { free( island_current ); return NULL; @@ -722,55 +804,64 @@ static struct cxr_mesh *cxr_pull_island(struct cxr_mesh *mesh) for( int i=0; ipolys, island_current[i]); + cxr_polygon *poly = &mesh->polys[ island_current[i] ]; loop_count += poly->loop_total; } - struct cxr_mesh *newmesh = cxr_alloc_mesh( mesh->edges.count, loop_count, island_len ); + /* Create and update meshes */ + cxr_mesh *newmesh = cxr_alloc_mesh( mesh->abedges.count, + loop_count, + island_len, + mesh->p_abverts ); for( int i=0; ipolys, island_current[i]); - struct cxr_polygon *dst = cxr_ab_ptr(&newmesh->polys, i); + cxr_polygon *src = &mesh->polys[ island_current[i] ]; + cxr_polygon *dst = cxr_ab_ptr(&newmesh->abpolys, i); *dst = *src; - dst->loop_start = newmesh->loops.count; + dst->loop_start = newmesh->abloops.count; for( int j=0; jloop_total; j++ ) { - struct cxr_loop *lsrc = cxr_ab_ptr(&mesh->loops, src->loop_start+j), - *ldst = cxr_ab_ptr(&newmesh->loops, dst->loop_start+j); + 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->loops.count += src->loop_total; + newmesh->abloops.count += src->loop_total; src->loop_total = -1; } - newmesh->polys.count = island_len; - newmesh->edges.count = mesh->edges.count; - memcpy(cxr_ab_ptr(&newmesh->edges,0), cxr_ab_ptr(&mesh->edges,0), mesh->edges.count*sizeof(struct cxr_edge)); + 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 ); + free( island_current ); return newmesh; } -// Does some checks to determine if solid is valid or not -static int cxr_valid_solid( struct cxr_mesh *mesh, struct cxr_auto_buffer *abverts, int *solid, int len ) +/* + * 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 ) { - // Invalid 1: Similar normals - // Invalid 2: Co-planar point, that is not referenced by the polygon. - // + v3f *verts = cxr_ab_ptr(mesh->p_abverts, 0); + for( int i=0; ipolys,solid[i]); + cxr_polygon *polyi = &mesh->polys[ solid[i] ]; v4f plane; normal_to_plane(polyi->normal, polyi->center, plane); @@ -779,24 +870,25 @@ static int cxr_valid_solid( struct cxr_mesh *mesh, struct cxr_auto_buffer *abver { if( i==j ) continue; - struct cxr_polygon *polyj = cxr_ab_ptr(&mesh->polys,solid[j]); + cxr_polygon *polyj = &mesh->polys[ solid[j] ]; for( int k=0; kloop_total; k++ ) { - struct cxr_loop *lpj = cxr_ab_ptr(&mesh->loops, polyj->loop_start+k); + cxr_loop *lpj = &mesh->loops[ polyj->loop_start+k ]; - // Make sure this point isnt in our original poly + /* Test if the vertex is not referenced by the polygon */ for( int l=0; lloop_total; l++ ) { - struct cxr_loop *lpi = cxr_ab_ptr(&mesh->loops, polyi->loop_start+l); + cxr_loop *lpi = &mesh->loops[ polyi->loop_start+l ]; + if( lpi->index == lpj->index ) - goto IL_SKIP_VERTEX; + goto skip_vertex; } - if( fabs(plane_polarity(plane,cxr_ab_ptr(abverts,lpj->index))) < 0.001 ) + if( fabs(plane_polarity(plane, verts[lpj->index])) < 0.001 ) return 0; -IL_SKIP_VERTEX:; + skip_vertex:; } } } @@ -804,67 +896,78 @@ IL_SKIP_VERTEX:; return 1; } -// Return best availible solid from mesh, and patch existing mesh to fill the gap -// creted by it. -// -// Returns NULL if shape is already convex or empty -// Destroys edge data! -static struct cxr_mesh *cxr_pull_best_solid( - struct cxr_mesh *mesh, - struct cxr_auto_buffer *vert_buffer, - int preserve_hot_edges, - u32 *error ) +/* + * 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 ) { - v3f *vertices = cxr_ab_ptr( vert_buffer, 0 ); - - i32 *polygon_edge_map = cxr_mesh_link_loops(mesh); + if( lp->poly_left > lp->poly_right ) + return 0; - for( int i=0; iedges.count*2; i++ ) - if( polygon_edge_map[i] == -1 ) - { - cxr_log( "non-manifold edges are in the mesh; implicit internal geometry does not have full support\n" ); - free(polygon_edge_map); - return NULL; - } + return 1; +} - int *vertex_tagged = malloc( vert_buffer->count*sizeof(int) ); - int *edge_tagged = malloc( mesh->edges.count*sizeof(int) ); +/* + * 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; iedges.count; i++ ) + for( int i=0; iabloops.count; i++ ) { - struct cxr_polygon *polya = cxr_ab_ptr(&mesh->polys, polygon_edge_map[i*2+0]), - *polyb = cxr_ab_ptr(&mesh->polys, polygon_edge_map[i*2+1]); + 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); - - edge_tagged[i] = 0; + for( int j=0; jloop_total; j++ ) { - struct cxr_loop *loop = cxr_ab_ptr(&mesh->loops, polya->loop_start+j); - if( plane_polarity( planeb, vertices[loop->index] ) > 0.001 || - v3_dot(polya->normal,polyb->normal) > CXR_PLANE_SIMILARITY_MAX ) + 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[i] = 1; + edge_tagged[lp->edge_index] = 1; break; } } } - // Tag 'reflex' vertices - int *connected_planes = malloc(mesh->polys.count*sizeof(int)); + return edge_tagged; +} - for( int i=0; icount; i++ ) +/* + * 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; ip_abverts->count; i++ ) { vertex_tagged[i]=0; - int num_connected = 0; - // Create a list of polys that ref this vert - for( int j=0; jpolys.count; j++ ) + + /* Create a list of polygons that refer to this vertex */ + for( int j=0; jabpolys.count; j++ ) { - struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys,j); + cxr_polygon *poly = &mesh->polys[j]; for( int k=0; kloop_total; k++ ) { - struct cxr_loop *loop = cxr_ab_ptr(&mesh->loops,poly->loop_start+k); + cxr_loop *loop = &mesh->loops[poly->loop_start+k]; if( loop->index == i ) { connected_planes[num_connected ++] = j; @@ -872,88 +975,344 @@ static struct cxr_mesh *cxr_pull_best_solid( } } } - // Check all combinations for a similar normal + + /* Check all combinations for a similar normal */ for( int j=0; jpolys,connected_planes[j]); - struct cxr_polygon *polyk = cxr_ab_ptr(&mesh->polys,connected_planes[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 IL_TAG_VERT; + if( v3_dot(polyj->normal,polyk->normal) > CXR_PLANE_SIMILARITY_MAX ) + goto tag_vert; } } - - // Check if all connected planes not are: - // - bounded by other planes - // - or coplanar - + + /* + * Check if all connected planes either: + * - Bound this vert + * - Coplanar with it + */ for( int j=0; jpolys, connected_planes[j]), - *kpoly = cxr_ab_ptr(&mesh->polys, connected_planes[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; lloop_total; l++ ) { - struct cxr_loop *loop = cxr_ab_ptr(&mesh->loops, jpoly->loop_start+l); - if( plane_polarity( plane, vertices[loop->index] ) > 0.001 ) - goto IL_TAG_VERT; + cxr_loop *lp = &mesh->loops[ jpoly->loop_start+l ]; + + if( plane_polarity( plane, verts[lp->index] ) > 0.001 ) + goto tag_vert; } } + } - goto IL_TAG_NEXT_VERT; -IL_TAG_VERT: vertex_tagged[i] = 1; -IL_TAG_NEXT_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; iloop_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; iabedges.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 ); + } - // Connect all marked verts that share an edge - // - We must take care not to completely isolate - // a polygon with marked edges all around it + 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 *hot_edge = malloc(mesh->edges.count*sizeof(int)); - for( int i=0; i< mesh->edges.count; i++ ) - hot_edge[i] = 0; + int solid_len = 0; + solid[solid_len++] = faceid; + + int search_start = 0; + +search_iterate:; - for( int i=0; ipolys.count; i ++ ) + int changed = 0; + for( int j=search_start; jpolys[ solid[j] ]; + + for( int k=0; kloop_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; mpoly_right ) + goto dont_check; + + for( int m=0; mpolys[solid[m]]; + if( v3_dot( polym->normal,future_face->normal) > CXR_PLANE_SIMILARITY_MAX) + goto dont_check; + } + + dont_check:; + } + + // Check for vertices in the new poly that exist on a current plane. + // this condition is an invalid configuration and should not be added. + + 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; + + // The current method can create some invalid configurations + // filter those out that dont work and un-tag the faces + + /* TODO(harry): + * + * I think we have good enough filters now to ignore these, + * probably should make them show as warnings + * + */ +#if 0 + if( !cxr_valid_solid( mesh, solid, solid_len ) ) { - struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys,i); + for( int l=0; lpolys, solid[j]), + *polyk = cxr_ab_ptr(&mesh->polys, solid[k]); + + if( v3_dot( polyj->normal, polyk->normal ) > CXR_PLANE_SIMILARITY_MAX ) + { + for( int l=0; lp_abverts, 0 ); + 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; iabpolys.count; i ++ ) + { + cxr_polygon *poly = &mesh->polys[i]; int not_tagged = -1, tag_count = 0; for( int j=0; jloop_total; j++ ) { - struct cxr_loop *loop = cxr_ab_ptr(&mesh->loops, poly->loop_start+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 IL_SKIP_NO_HOT_EDGE; + goto edge_unimportant; } } if( not_tagged != -1 ) - hot_edge[not_tagged]=1; + edge_important[not_tagged]=1; - IL_SKIP_NO_HOT_EDGE:; + edge_unimportant:; } // Connect edges that have verts tagged, but is not a hot edge - for( int i=0; iedges.count; i ++ ) + for( int i=0; iabedges.count; i ++ ) { - if( hot_edge[i] && preserve_hot_edges ) continue; + if( edge_important[i] && preserve_more_edges ) continue; - struct cxr_edge *edge = cxr_ab_ptr(&mesh->edges,i); + cxr_edge *edge = &mesh->edges[i]; if( vertex_tagged[edge->i0] && vertex_tagged[edge->i1] ) edge_tagged[i] = 1; } + free( edge_important ); + #if 0 for( int i=0; icount; i++ ) if( vertex_tagged[i] ) @@ -961,7 +1320,7 @@ IL_TAG_NEXT_VERT:; for( int i=0; i < mesh->edges.count; i++ ) { - struct cxr_edge *edge = cxr_ab_ptr( &mesh->edges, i ); + cxr_edge *edge = cxr_ab_ptr( &mesh->edges, i ); if( edge_tagged[i] ) cxr_debug_line( vertices[ edge->i0 ], vertices[ edge->i1 ], (v4f){0.0,0.0,0.0,1.0}); @@ -971,27 +1330,27 @@ IL_TAG_NEXT_VERT:; #endif // count regions - int *faces_tagged = malloc(mesh->polys.count*sizeof(int)); - for( int i=0; ipolys.count; i++ ) + int *faces_tagged = malloc(mesh->abpolys.count*sizeof(int)); + for( int i=0; iabpolys.count; i++ ) faces_tagged[i] = -1; - int *solid_buffer = malloc( mesh->polys.count*sizeof(int) ); + int *solid_buffer = malloc( mesh->abpolys.count*sizeof(int) ); int solid_buffer_len = 0; struct csolid { int start,count,edge_count; v3f center; } - *candidates = malloc( mesh->polys.count *sizeof(struct csolid) ); + *candidates = malloc( mesh->abpolys.count *sizeof(struct csolid) ); int candidate_count = 0; struct tedge { int i0, i1; } - *edge_references = malloc( mesh->edges.count *sizeof(struct tedge) ); + *edge_references = malloc( mesh->abedges.count *sizeof(struct tedge) ); - for( int i=0; ipolys.count; i++ ) + for( int i=0; iabpolys.count; i++ ) { if( faces_tagged[i] != -1 ) continue; faces_tagged[i] = i; @@ -1012,12 +1371,12 @@ IL_TAG_NEXT_VERT:; int changed = 0; for( int j=search_start; jpolys, solid[j]); + cxr_polygon *poly = &mesh->polys[solid[j]]; for( int k=0; kloop_total; k++ ) { - struct cxr_loop *loop = cxr_ab_ptr(&mesh->loops, poly->loop_start+k); - struct cxr_edge *edge = cxr_ab_ptr(&mesh->edges, loop->edge_index ); + cxr_loop *loop = &mesh->loops[poly->loop_start+k]; + cxr_edge *edge = &mesh->edges[loop->edge_index]; if( faces_tagged[ loop->poly_right ] == -1 ) { @@ -1033,11 +1392,15 @@ IL_TAG_NEXT_VERT:; // It would be nice to find a more robust clustering algorithm for this. // - struct cxr_polygon *poly_to_add = cxr_ab_ptr(&mesh->polys, loop->poly_right ); + cxr_polygon *poly_to_add = &mesh->polys[loop->poly_right]; + + if( cxr_solid_overlap(mesh, poly, poly_to_add, loop->edge_index, 0 )) + goto IL_SKIP_PLANE_ADD; + for( int l=0; l < poly_to_add->loop_total; l++ ) { - struct cxr_loop *loop1 = cxr_ab_ptr(&mesh->loops, poly_to_add->loop_start+l ); - struct cxr_polygon *future_face = cxr_ab_ptr(&mesh->polys, loop1->poly_right ); + cxr_loop *loop1 = &mesh->loops[poly_to_add->loop_start+l]; + cxr_polygon *future_face = &mesh->polys[loop1->poly_right]; if( edge_tagged[ loop1->edge_index ] || loop1->poly_right == loop->poly_right ) goto IL_SKIP_SIMILAR_PLANES; @@ -1048,7 +1411,7 @@ IL_TAG_NEXT_VERT:; for( int m=0; mpolys,solid[m]); + cxr_polygon *polym = &mesh->polys[solid[m]]; if( v3_dot( polym->normal,future_face->normal) > CXR_PLANE_SIMILARITY_MAX) goto IL_SKIP_PLANE_ADD; } @@ -1061,7 +1424,8 @@ IL_TAG_NEXT_VERT:; solid[ solid_len ] = loop->poly_right; - if( cxr_valid_solid(mesh,vert_buffer,solid,solid_len+1 ) ) + + if( cxr_valid_solid(mesh,solid,solid_len+1 ) ) { faces_tagged[ loop->poly_right ] = i; changed = 1; @@ -1079,22 +1443,38 @@ IL_TAG_NEXT_VERT:; // The current method can create some invalid configurations // filter those out that dont work and un-tag the faces + + /* TODO(harry): + * + * I think we have good enough filters now to ignore these, + * probably should make them show as warnings + * + */ + if( !cxr_valid_solid( mesh, solid, solid_len ) ) + { + for( int l=0; lpolys, solid[j]), - *polyk = cxr_ab_ptr(&mesh->polys, solid[k]); + cxr_polygon *polyj = &mesh->polys[solid[j]], + *polyk = &mesh->polys[ solid[k] ]; if( v3_dot( polyj->normal, polyk->normal ) > CXR_PLANE_SIMILARITY_MAX ) { for( int l=0; lcenter ); for( int j=0; jpolys, solid[j]); + cxr_polygon *polyj = &mesh->polys[ solid[j] ]; v3_add( polyj->center, csolid->center, csolid->center ); csolid->edge_count += polyj->loop_total; } @@ -1124,15 +1504,19 @@ IL_TAG_NEXT_VERT:; struct csolid *best_solid = NULL; int fewest_manifold_splits = INT32_MAX; - struct cxr_loop *best_manifold = malloc( mesh->loops.count *sizeof(struct cxr_loop) ); - int *best_manifold_splits = malloc( mesh->loops.count *sizeof(int) ); + cxr_loop *best_manifold = malloc( mesh->abloops.count *sizeof(cxr_loop) ); + int *best_manifold_splits = malloc( mesh->abloops.count *sizeof(int) ); int best_manifold_len = 0; int max_solid_faces = 0; - + + /* int *edge_list = malloc( mesh->edges.count *sizeof(int) ); int *edge_lefts = malloc( mesh->edges.count *sizeof(int) ); - struct cxr_loop *manifold = malloc(mesh->edges.count*2*sizeof(struct cxr_loop)); - int *splits = malloc(mesh->edges.count*2*sizeof(int)); + */ + cxr_loop **edge_list = malloc( sizeof(*edge_list) *mesh->abedges.count); + + cxr_loop *manifold = malloc(mesh->abedges.count*2*sizeof(cxr_loop)); + int *splits = malloc(mesh->abedges.count*2*sizeof(int)); for( int i=0; icount; j++ ) { - struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys, solid_buffer[solid->start+j]); + cxr_polygon *poly = cxr_ab_ptr(&mesh->abpolys, solid_buffer[solid->start+j]); for( int k=0; kloop_total; k++ ) { - struct cxr_loop *loop = cxr_ab_ptr(&mesh->loops, poly->loop_start+k); + cxr_loop *loop = cxr_ab_ptr(&mesh->abloops, poly->loop_start+k); for( int l=0; ledge_index ) + if( edge_list[l]->edge_index == loop->edge_index ) goto IL_EDGE_ALREADY_PRESENT; // Check if right edge references a polygon that is not @@ -1163,12 +1547,11 @@ IL_TAG_NEXT_VERT:; if( loop->poly_right == solid_buffer[solid->start+l] ) goto IL_EDGE_ALREADY_PRESENT; - edge_list[ unique_edge_count ] = loop->edge_index; - edge_lefts[ unique_edge_count ] = loop->poly_left; + edge_list[ unique_edge_count ] = loop; if( unique_edge_count == 0 ) { - struct cxr_edge *edgeptr = cxr_ab_ptr(&mesh->edges, loop->edge_index); + cxr_edge *edgeptr = cxr_ab_ptr(&mesh->abedges, loop->edge_index); if( edgeptr->i1 == loop->index ) init_reverse = 1; } @@ -1186,15 +1569,15 @@ IL_TAG_NEXT_VERT:; // Corners are created when two edges share a polygon face // This way we can split it into regions - for( int j=0; jcount; j++ ) + for( int j=0; jp_abverts->count; j++ ) vertex_tagged[j] = -1; // Start with a loop edge which was tagged - struct cxr_edge *current = cxr_ab_ptr(&mesh->edges, edge_list[0]); + cxr_edge *current = &mesh->edges[edge_list[0]->edge_index]; int endpt = (!init_reverse)? current->i0: current->i1, start = endpt, - curface = edge_lefts[0]; + curface = edge_list[0]->poly_left; int manifold_len = 0; int split_count = 0; @@ -1202,7 +1585,7 @@ IL_TAG_NEXT_VERT:; IL_MANIFOLD_CONTINUE: for( int j=0; jedges, edge_list[j]); + cxr_edge *other = &mesh->edges[ edge_list[j]->edge_index ]; if( other == current ) continue; @@ -1214,7 +1597,7 @@ IL_TAG_NEXT_VERT:; if( other->i0 == endpt ) endpt = current->i1; else endpt = current->i0; - if( curface==edge_lefts[j] ) + if( curface==edge_list[j]->poly_left ) { splits[ manifold_len ] = 1; split_count ++; @@ -1223,16 +1606,13 @@ IL_TAG_NEXT_VERT:; splits[ manifold_len ] = 0; // Append to intermidiary manifold - manifold[ manifold_len ].edge_index = edge_list[j]; - manifold[ manifold_len ].poly_left = edge_lefts[j]; + manifold[ manifold_len ].edge_index = edge_list[j]->edge_index; + manifold[ manifold_len ].poly_left = edge_list[j]->poly_left; manifold[ manifold_len ].index = lastpt; - manifold[ manifold_len ].poly_right = - polygon_edge_map[ edge_list[j]*2 ] == edge_lefts[j]? - polygon_edge_map[ edge_list[j]*2+1 ]: - polygon_edge_map[ edge_list[j]*2+0 ]; + manifold[ manifold_len ].poly_right = edge_list[j]->poly_right; manifold_len ++; - curface = edge_lefts[j]; + curface = edge_list[j]->poly_left; if(endpt == start) goto IL_MANIFOLD_COMPLETE; goto IL_MANIFOLD_CONTINUE; @@ -1243,40 +1623,38 @@ IL_TAG_NEXT_VERT:; for( int j=0; jcount; j++ ) { cxr_log( "p%d\n", solid_buffer[solid->start+j] ); - struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys, solid_buffer[solid->start+j]); - cxr_debug_poly( mesh, poly, vertices, (v4f){0.2,0.0,0.0,1.0} ); + cxr_polygon *poly = &mesh->polys[ solid_buffer[solid->start+j] ]; + cxr_debug_poly( mesh, poly, (v4f){0.2,0.0,0.0,1.0} ); } for( int j=0; jedges, edge_list[j]); - cxr_debug_line(vertices[uedge->i0],vertices[uedge->i1],(v4f){0.4,0.0,0.0,1.0}); + cxr_edge *uedge = &mesh->edges[ edge_list[j]->edge_index ]; + cxr_debug_line( verts[uedge->i0], verts[uedge->i1], + (v4f){0.4,0.0,0.0,1.0}); } for( int j=0; jindex],vertices[lp1->index], colour_error ); + cxr_debug_line(verts[lp0->index],verts[lp1->index], colour_error ); } - cxr_debug_mesh( mesh, vertices, (v4f){0.0,0.0,0.0, 0.9} ); + cxr_debug_mesh( mesh, (v4f){0.0,0.0,0.0, 0.9} ); *error = CXR_ERROR_BAD_MANIFOLD; free(edge_list); - free(edge_lefts); free(manifold); free(splits); free(edge_tagged); free(vertex_tagged); - free(hot_edge); free(faces_tagged); free(solid_buffer); free(candidates); free(best_manifold); free(best_manifold_splits); - free(polygon_edge_map); return NULL; IL_MANIFOLD_COMPLETE:; @@ -1301,7 +1679,6 @@ IL_TAG_NEXT_VERT:; } free(edge_list); - free(edge_lefts); free(manifold); free(splits); @@ -1310,36 +1687,34 @@ IL_TAG_NEXT_VERT:; *error = CXR_ERROR_NO_SOLIDS; free(edge_tagged); free(vertex_tagged); - free(hot_edge); free(faces_tagged); free(solid_buffer); free(candidates); free(best_manifold); free(best_manifold_splits); - free(polygon_edge_map); return NULL; } if( best_solid != NULL ) { - struct cxr_mesh *pullmesh = - cxr_alloc_mesh( best_solid->edge_count, best_solid->edge_count, best_solid->count ); + cxr_mesh *pullmesh = + cxr_alloc_mesh( best_solid->edge_count, best_solid->edge_count, best_solid->count, mesh->p_abverts ); // Add existing faces to pullsolid, and delete from main mesh for( int i=0; icount; i++ ) { - int nface_id = pullmesh->polys.count; + int nface_id = pullmesh->abpolys.count; - struct cxr_polygon *exist_face = cxr_ab_ptr(&mesh->polys, solid_buffer[best_solid->start+i]); - struct cxr_polygon *new_face = cxr_ab_empty(&pullmesh->polys); + cxr_polygon *exist_face = &mesh->polys[ solid_buffer[best_solid->start+i] ]; + cxr_polygon *new_face = cxr_ab_empty( &pullmesh->abpolys ); *new_face = *exist_face; - new_face->loop_start = pullmesh->loops.count; + new_face->loop_start = pullmesh->abloops.count; for( int j=0; jloop_total; j++ ) { - struct cxr_loop *exist_loop = cxr_ab_ptr(&mesh->loops, exist_face->loop_start+j); - struct cxr_loop *new_loop = cxr_ab_empty(&pullmesh->loops); + cxr_loop *exist_loop = cxr_ab_ptr(&mesh->abloops, exist_face->loop_start+j); + cxr_loop *new_loop = cxr_ab_empty(&pullmesh->abloops); new_loop->index = exist_loop->index; new_loop->poly_left = nface_id; @@ -1352,22 +1727,10 @@ IL_TAG_NEXT_VERT:; } int new_polys = 0; - int pullmesh_new_start = pullmesh->polys.count; + int pullmesh_new_start = pullmesh->abpolys.count; if( fewest_manifold_splits != 0 ) { - #if CXR_MANIFOLD_DEBUG - for( int i=0; ip_abverts; // Implicit geometry reconstruction // If there's 3 or more planes, collide them together to see if any new @@ -1469,9 +1833,9 @@ IL_TAG_NEXT_VERT:; { for( int k=j+1; kpolys, pullmesh_new_start+i ), - *ptrj = cxr_ab_ptr( &pullmesh->polys, pullmesh_new_start+j ), - *ptrk = cxr_ab_ptr( &pullmesh->polys, pullmesh_new_start+k ); + cxr_polygon *ptri = &pullmesh->polys[ pullmesh_new_start+i ], + *ptrj = &pullmesh->polys[ pullmesh_new_start+j ], + *ptrk = &pullmesh->polys[ pullmesh_new_start+k ]; v4f planei, planej, planek; normal_to_plane(ptri->normal,ptri->center,planei); @@ -1488,9 +1852,9 @@ IL_TAG_NEXT_VERT:; // it as a degenerate case int point_valid = 1; - for( int l=0; lpolys.count; l++ ) + for( int l=0; labpolys.count; l++ ) { - struct cxr_polygon *ptrl = cxr_ab_ptr(&pullmesh->polys,l); + cxr_polygon *ptrl = &pullmesh->polys[l]; v4f planel; normal_to_plane(ptrl->normal, ptrl->center, planel); @@ -1500,9 +1864,9 @@ IL_TAG_NEXT_VERT:; cxr_log( "degen vert, planes %d, %d, %d [max:%d]\n", i,j,k, new_polys ); *error = CXR_ERROR_DEGEN_IMPLICIT; - cxr_debug_poly( pullmesh, ptri, cxr_ab_ptr(vert_buffer,0), colours_random[3] ); - cxr_debug_poly( pullmesh, ptrj, cxr_ab_ptr(vert_buffer,0), colours_random[1] ); - cxr_debug_poly( pullmesh, ptrk, cxr_ab_ptr(vert_buffer,0), colours_random[2] ); + cxr_debug_poly( pullmesh, ptri, colours_random[3] ); + cxr_debug_poly( pullmesh, ptrj, colours_random[1] ); + cxr_debug_poly( pullmesh, ptrk, colours_random[2] ); point_valid = 0; break; @@ -1512,25 +1876,37 @@ IL_TAG_NEXT_VERT:; if( !point_valid ) continue; // Extend faces to include this point - int nvertid = vert_buffer->count; - cxr_ab_push( vert_buffer, intersect ); + int nvertid = abverts->count; + cxr_ab_push( abverts, intersect ); ptrj->loop_start += 1; ptrk->loop_start += 2; - cxr_ab_reserve(&pullmesh->loops, 3); - struct cxr_loop *lloopi = cxr_ab_empty_at(&pullmesh->loops, ptri->loop_start+ptri->loop_total), - *lloopj = cxr_ab_empty_at(&pullmesh->loops, ptrj->loop_start+ptrj->loop_total), - *lloopk = cxr_ab_empty_at(&pullmesh->loops, ptrk->loop_start+ptrk->loop_total); + cxr_ab_reserve( &pullmesh->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(&pullmesh->abloops, newi), + *lloopj = cxr_ab_empty_at(&pullmesh->abloops, newj), + *lloopk = cxr_ab_empty_at(&pullmesh->abloops, newk); lloopi->index = nvertid; - lloopj->index = nvertid; - lloopk->index = nvertid; - lloopi->edge_index = 0; lloopj->edge_index = 0; lloopk->edge_index = 0; + lloopi->edge_index = 0; lloopi->poly_left = pullmesh_new_start+i; + lloopi->poly_right = -1; + + lloopj->index = nvertid; lloopj->poly_left = pullmesh_new_start+j; + lloopj->edge_index = 0; + lloopj->poly_right = -1; + + lloopk->index = nvertid; + lloopk->edge_index = 0; lloopk->poly_left = pullmesh_new_start+k; - lloopi->poly_right = -1; lloopj->poly_right = -1; lloopk->poly_right = -1; + lloopk->poly_right = -1; v2_zero(lloopi->uv); v2_zero(lloopj->uv); @@ -1554,19 +1930,19 @@ IL_TAG_NEXT_VERT:; for( int i=0; ipolys.count; + int rface_id = mesh->abpolys.count; - struct cxr_polygon *pface = cxr_ab_ptr(&pullmesh->polys,pullmesh_new_start+i); - struct cxr_polygon *rip_face = cxr_ab_empty(&mesh->polys); + cxr_polygon *pface = cxr_ab_ptr(&pullmesh->abpolys,pullmesh_new_start+i); + cxr_polygon *rip_face = cxr_ab_empty(&mesh->abpolys); - rip_face->loop_start = mesh->loops.count; + rip_face->loop_start = mesh->abloops.count; rip_face->loop_total = pface->loop_total; rip_face->material_id = -1; for( int j=0; jloop_total; j++ ) { - struct cxr_loop *ploop = cxr_ab_ptr(&pullmesh->loops, pface->loop_start+pface->loop_total-j-1), - *rloop = cxr_ab_empty(&mesh->loops); + cxr_loop *ploop = cxr_ab_ptr(&pullmesh->abloops, pface->loop_start+pface->loop_total-j-1), + *rloop = cxr_ab_empty(&mesh->abloops); rloop->index = ploop->index; rloop->poly_left = rface_id; @@ -1579,6 +1955,9 @@ IL_TAG_NEXT_VERT:; v3_negate( pface->normal, rip_face->normal ); } + cxr_mesh_update( mesh ); + cxr_mesh_update( pullmesh ); + cxr_mesh_clean_faces( mesh ); cxr_mesh_clean_faces( pullmesh ); cxr_mesh_clean_edges( mesh ); @@ -1586,58 +1965,60 @@ IL_TAG_NEXT_VERT:; free(edge_tagged); free(vertex_tagged); - free(hot_edge); free(faces_tagged); free(solid_buffer); free(candidates); free(best_manifold); free(best_manifold_splits); - free(polygon_edge_map); return pullmesh; } free(edge_tagged); free(vertex_tagged); - free(hot_edge); free(faces_tagged); free(solid_buffer); free(candidates); free(best_manifold); free(best_manifold_splits); - free(polygon_edge_map); return NULL; } -static struct cxr_mesh *cxr_to_internal_format(struct cxr_input_mesh *src, struct cxr_auto_buffer *abverts) +/* + * 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_auto_buffer *abverts) { - // Split mesh into islands - struct cxr_mesh *mesh = cxr_alloc_mesh( src->edge_count, src->loop_count, src->poly_count ); + 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 ); - // Copy input data into working mesh - memcpy( cxr_ab_ptr( &mesh->edges, 0 ), src->edges, src->edge_count*sizeof(struct cxr_edge)); - memcpy( cxr_ab_ptr( &mesh->polys, 0 ), src->polys, src->poly_count*sizeof(struct cxr_polygon)); + memcpy( cxr_ab_ptr( &mesh->abedges, 0 ), src->edges, src->edge_count*sizeof(cxr_edge)); + memcpy( cxr_ab_ptr( &mesh->abpolys, 0 ), src->polys, src->poly_count*sizeof(cxr_polygon)); memcpy( cxr_ab_ptr( abverts, 0 ), src->vertices, src->vertex_count*sizeof(v3f)); - mesh->edges.count = src->edge_count; - mesh->loops.count = src->loop_count; - mesh->polys.count = src->poly_count; + 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; iloop_count; i++ ) { - struct cxr_loop *lp = cxr_ab_ptr(&mesh->loops,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 farthest dot product along direction +/* + * Find most extreme point along a given direction + */ static double support_distance( v3f verts[3], v3f dir, double coef ) { return cxr_maxf @@ -1653,7 +2034,7 @@ static double support_distance( v3f verts[3], v3f dir, double coef ) // Main function static void cxr_calculate_axis( - struct cxr_texinfo *transform, + cxr_texinfo *transform, v3f verts[3], v2f uvs[3], v2f texture_res @@ -1758,11 +2139,10 @@ static void cxr_calculate_axis( transform->winding = winding; } -CXR_API struct cxr_input_mesh *cxr_decompose(struct cxr_input_mesh *src) +CXR_API cxr_input_mesh *cxr_decompose(cxr_input_mesh *src) { -#ifdef CXR_DEBUG_WRITE_MESH - FILE *yeet = fopen( "/home/harry/Documents/blender_addons_remote/addons/convexer/solid.h", "w" ); - + FILE *yeet = fopen( "/home/harry/Documents/blender_addons_remote/addons/convexer/src/solid.h", "w" ); + fprintf( yeet, "v3f test_verts[] = {\n" ); for( int i=0; ivertex_count; i ++ ) { @@ -1800,9 +2180,10 @@ CXR_API struct cxr_input_mesh *cxr_decompose(struct cxr_input_mesh *src) fprintf( yeet, "struct cxr_edge test_edges[] = {\n" ); for( int i=0; iedge_count; i++ ) { - fprintf( yeet, " {%d, %d},\n", + fprintf( yeet, " {%d, %d, %d},\n", src->edges[i].i0, - src->edges[i].i1 + src->edges[i].i1, + src->edges[i].freestyle ); } fprintf( yeet, "};\n" ); @@ -1817,68 +2198,8 @@ CXR_API struct cxr_input_mesh *cxr_decompose(struct cxr_input_mesh *src) fprintf( yeet, " .edge_count=%d,\n",src->edge_count ); fprintf( yeet, " .loop_count=%d\n", src->loop_count ); fprintf( yeet, "};\n" ); - + fclose( yeet ); -#endif - - struct cxr_auto_buffer abverts; - struct cxr_mesh *main_mesh = cxr_to_internal_format( src, &abverts ); - - u32 error = 0x00; - - struct cxr_auto_buffer solids; - cxr_ab_init( &solids, sizeof(struct cxr_mesh *), 2 ); - - while(1) - { - struct cxr_mesh *res = cxr_pull_best_solid( main_mesh, &abverts, 0, &error ); - if( res ) - { - cxr_ab_push( &solids, &res ); - if( error ) break; - } - else - { - if( error ) - { - // If no solids error we can rety while preserving 'hot' edges - - if( error & CXR_ERROR_NO_SOLIDS ) - { - error = 0x00; - res = cxr_pull_best_solid(main_mesh, &abverts, 1, &error); - - if( res ) cxr_ab_push( &solids, &res ); - else break; - - if( error ) break; - } - else break; - } - else - break; - } - } - - cxr_ab_push( &solids, &main_mesh ); - - if( !error ) - { - for( int i=0; ip_abverts, 0 ); + // Create a graph which maps vertices by their connections struct vertinfo { @@ -1922,11 +2244,11 @@ static void cxr_write_disp(struct cxr_mesh *mesh, struct cxr_input_mesh *inputme double alpha; } - *vertinfo = malloc( sizeof(struct vertinfo)*abverts->count ); - int *graph = malloc( sizeof(int) * mesh->edges.count*2 ); + *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; icount; i++ ) + for( int i=0; ip_abverts->count; i++ ) { struct vertinfo *info = &vertinfo[i]; info->con_start = con_pos; @@ -1937,9 +2259,9 @@ static void cxr_write_disp(struct cxr_mesh *mesh, struct cxr_input_mesh *inputme info->search = 0; info->alpha = 0.0; - for( int j=0; jedges.count; j++ ) + for( int j=0; jabedges.count; j++ ) { - struct cxr_edge *edge = cxr_ab_ptr(&mesh->edges,j); + cxr_edge *edge = &mesh->edges[j]; if( edge->i0 == i || edge->i1 == i ) { @@ -1961,12 +2283,12 @@ static void cxr_write_disp(struct cxr_mesh *mesh, struct cxr_input_mesh *inputme v3f avg_normal, refv, refu, refn; v3_zero(refv); v3_zero(refu); v3_zero(refn); - for( int i=0; ipolys.count; i++ ) + for( int i=0; iabpolys.count; i++ ) { - struct cxr_polygon *poly = cxr_ab_ptr( &mesh->polys, i ); + cxr_polygon *poly = &mesh->polys[i]; v3_add( poly->normal, avg_normal, avg_normal ); } - v3_divs( avg_normal, mesh->polys.count, avg_normal ); + v3_divs( avg_normal, mesh->abpolys.count, avg_normal ); v3_normalize( avg_normal ); // TODO(harry): This can be zero length. Should add a safety check // normalize function that checks for small length before // carrying out, otherwise we get inf/nan values... @@ -1987,27 +2309,28 @@ static void cxr_write_disp(struct cxr_mesh *mesh, struct cxr_input_mesh *inputme v3_fill( faceboundmin, CXR_BIG_NUMBER ); v3_fill( faceboundmax, -CXR_BIG_NUMBER ); - for( int i=0; ipolys.count; i++ ) + for( int i=0; iabpolys.count; i++ ) { - struct cxr_polygon *poly = cxr_ab_ptr( &mesh->polys, i ); + cxr_polygon *poly = cxr_ab_ptr( &mesh->abpolys, i ); for( int j=0; jloop_total; j++ ) { - struct cxr_loop *lp0 = cxr_ab_ptr(&mesh->loops, poly->loop_start+j); + cxr_loop *lp0 = cxr_ab_ptr(&mesh->abloops, poly->loop_start+j); v2_minv( lp0->uv, uvboundmin, uvboundmin); v2_maxv( lp0->uv, uvboundmax, uvboundmax); - v3_minv( cxr_ab_ptr(abverts,lp0->index), faceboundmin, faceboundmin ); - v3_maxv( cxr_ab_ptr(abverts,lp0->index), faceboundmax, faceboundmax ); + v3_minv( cxr_ab_ptr(mesh->p_abverts,lp0->index), faceboundmin, faceboundmin ); + v3_maxv( cxr_ab_ptr(mesh->p_abverts,lp0->index), faceboundmax, faceboundmax ); } for( int j=0; jloop_total-2; j++ ) { - struct cxr_loop *lp0 = cxr_ab_ptr(&mesh->loops, poly->loop_start), - *lp1 = cxr_ab_ptr(&mesh->loops, poly->loop_start+j+1), - *lp2 = cxr_ab_ptr(&mesh->loops, poly->loop_start+j+2); + 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( cxr_ab_ptr(abverts,lp1->index), cxr_ab_ptr(abverts,lp0->index), va ); - v3_sub( cxr_ab_ptr(abverts,lp2->index), cxr_ab_ptr(abverts,lp0->index), vb ); + v3_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; @@ -2029,7 +2352,7 @@ static void cxr_write_disp(struct cxr_mesh *mesh, struct cxr_input_mesh *inputme int corner_count = 0; // Vertex classification - for( int i=0; icount; i++ ) + for( int i=0; ip_abverts->count; i++ ) { struct vertinfo *info = &vertinfo[i]; if( !info->boundary ) continue; @@ -2063,24 +2386,24 @@ static void cxr_write_disp(struct cxr_mesh *mesh, struct cxr_input_mesh *inputme int dispedge_count; int disp_count = 0; - for( int i=0; ipolys.count; i++ ) + for( int i=0; iabpolys.count; i++ ) { - struct cxr_polygon *basepoly = cxr_ab_ptr(&mesh->polys,i); + cxr_polygon *basepoly = &mesh->polys[i]; for( int h=0; hloop_total; h ++ ) { int i0 = h, i1 = cxr_range(h+1,basepoly->loop_total); - struct cxr_loop *l0 = cxr_ab_ptr(&mesh->loops, basepoly->loop_start+i0), - *l1 = cxr_ab_ptr(&mesh->loops, basepoly->loop_start+i1); + 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 ) { int corner_count = 1; - struct cxr_material *matptr = + cxr_material *matptr = basepoly->material_id < 0 || inputmesh->material_count == 0? &cxr_nodraw: &inputmesh->materials[ basepoly->material_id ]; @@ -2106,17 +2429,17 @@ static void cxr_write_disp(struct cxr_mesh *mesh, struct cxr_input_mesh *inputme if( edge_head->corner ) { // Find a polygon that has the edge C-1 -> C - for( int j=0; jpolys.count && !newvert; j++ ) + for( int j=0; jabpolys.count && !newvert; j++ ) { - struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys,j); + cxr_polygon *poly = &mesh->polys[j]; for( int k=0; kloop_total; k ++ ) { int i0 = k, i1 = cxr_range(k+1,poly->loop_total); - struct cxr_loop *l0 = cxr_ab_ptr(&mesh->loops, poly->loop_start+i0), - *l1 = cxr_ab_ptr(&mesh->loops, poly->loop_start+i1); + 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] ) @@ -2125,7 +2448,7 @@ static void cxr_write_disp(struct cxr_mesh *mesh, struct cxr_input_mesh *inputme v2_copy( l1->uv, corner_uvs[corner_count ++] ); int i2 = cxr_range(i1+1,poly->loop_total); - struct cxr_loop *l2 = cxr_ab_ptr(&mesh->loops, poly->loop_start+i2); + cxr_loop *l2 = &mesh->loops[ poly->loop_start+i2 ]; dispedge[dispedge_count ++] = l2->index; newvert = 1; @@ -2170,7 +2493,7 @@ static void cxr_write_disp(struct cxr_mesh *mesh, struct cxr_input_mesh *inputme if( !newvert ) { - cxr_debug_box(cxr_ab_ptr(abverts,dispedge[dispedge_count-1]), 0.1, colour_error); + cxr_debug_box(verts[dispedge[dispedge_count-1]], 0.1, colour_error); break; } } @@ -2256,11 +2579,11 @@ static void cxr_write_disp(struct cxr_mesh *mesh, struct cxr_input_mesh *inputme // if( disp_count == 0 ) { - struct cxr_texinfo tx; + cxr_texinfo tx; v3f tri_ref[3]; - v3_copy( cxr_ab_ptr(abverts,dispedge[0]), tri_ref[0] ); - v3_copy( cxr_ab_ptr(abverts,dispedge[4]), tri_ref[1] ); - v3_copy( cxr_ab_ptr(abverts,dispedge[8]), tri_ref[2] ); + 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 ); @@ -2340,7 +2663,7 @@ static void cxr_write_disp(struct cxr_mesh *mesh, struct cxr_input_mesh *inputme world_corners[j][2] += cxr_context.offset_z; } - struct cxr_texinfo texinfo_shared; + cxr_texinfo texinfo_shared; cxr_calculate_axis( &texinfo_shared, world_corners, world_uv, (v2f){ matptr->res[0], matptr->res[1] } ); @@ -2375,7 +2698,7 @@ static void cxr_write_disp(struct cxr_mesh *mesh, struct cxr_input_mesh *inputme tx = (double)k/(double)(5-1); v3_lerp( lside0, lside1, tx, lref ); - v3_muls( cxr_ab_ptr(abverts, grid[index]), cxr_context.scale_factor, vworld ); + v3_muls( verts[grid[index]], cxr_context.scale_factor, vworld ); vworld[2] += cxr_context.offset_z; v3_sub( vworld, lref, vdelta ); @@ -2473,137 +2796,26 @@ static void cxr_write_disp(struct cxr_mesh *mesh, struct cxr_input_mesh *inputme } } - // Main loop -#if 0 - int pool[25]; - for( int i=0; icount; i++ ) - { - struct vertinfo *info = &vertinfo[i]; - if( info->boundary || info->used ) - continue; - - // Gather all vertices in this displacement - int poolcount = 1, - front_start = 0, - front_count = 1; - pool[0] = i; - info->used = 1; - - IL_GATHER_LOOP:; - - int new_front_start = poolcount; - - for( int j=0; jcon_count; k++ ) - { - int conid = graph[frontvert->con_start+k]; - struct vertinfo *con = &vertinfo[conid]; - - if( frontvert->boundary && !con->boundary ) - continue; - - if( con->used ) - continue; - - if( poolcount == 25 ) - goto IL_DISP_ERROR_COUNT; - - con->used = 1; - pool[ poolcount ++ ] = conid; - } - } - - if( poolcount > new_front_start ) - { - front_start = new_front_start; - front_count = poolcount-front_start; - - goto IL_GATHER_LOOP; - } - - if( poolcount != 25 ) - { -IL_DISP_ERROR_COUNT: - for( int i=0; i25 verts)\n"); - return; - } - - int corners[4]; - int corner_count = 0; - struct cxr_loop *cornerloops[4]; - - // Find corners, and get their loops (for uvs) - // note: the mesh must be split where there is texture seams - // so that two different uv'd loops cant ref the same vertex - // - for( int j=0; jloops.count; k++ ) - { - struct cxr_loop *lp = cxr_ab_ptr(&mesh->loops,k); - if( lp->index == pool[j] ) - { - cornerloops[corner_count] = lp; - break; - } - } - - corner_count ++; - } - } - - if( corner_count !=4 ) - { - free(graph); - free(vertinfo); - cxr_log( "Invalid displacement (!=4 corners)\n" ); - return; - } - - int pivot = corners[0]; - } -#endif - free( graph ); free( vertinfo ); } -static int cxr_solid_checkerr(struct cxr_mesh *mesh, struct cxr_auto_buffer *abverts ) +static int cxr_solid_checkerr(cxr_mesh *mesh, cxr_auto_buffer *abverts ) { int err_count = 0; - for( int i=0; ipolys.count; i++ ) + for( int i=0; iabpolys.count; i++ ) { int plane_err = 0; - struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys,i); + cxr_polygon *poly = &mesh->polys[i]; v4f plane; normal_to_plane( poly->normal, poly->center, plane ); for( int j=0; jloop_total; j++ ) { - struct cxr_loop *loop = cxr_ab_ptr(&mesh->loops, poly->loop_start+j); + cxr_loop *loop = &mesh->loops[ poly->loop_start+j ]; double *vert = cxr_ab_ptr(abverts,loop->index); if( fabs(plane_polarity(plane,vert)) > 0.0025 ) @@ -2620,28 +2832,28 @@ static int cxr_solid_checkerr(struct cxr_mesh *mesh, struct cxr_auto_buffer *abv } if( plane_err ) - cxr_debug_poly( mesh, poly, cxr_ab_ptr(abverts,0), colour_error ); + cxr_debug_poly( mesh, poly, colour_error ); } return err_count; } -CXR_API i32 cxr_convert_mesh_to_vmf(struct cxr_input_mesh *src, struct cxr_vdf *output) +CXR_API i32 cxr_convert_mesh_to_vmf(cxr_input_mesh *src, cxr_vdf *output) { // Split mesh into islands - struct cxr_auto_buffer abverts; - struct cxr_mesh *main_mesh = cxr_to_internal_format(src, &abverts); + cxr_auto_buffer abverts; + cxr_mesh *main_mesh = cxr_to_internal_format(src, &abverts); u32 error = 0x00; int invalid_count = 0; struct solidinf { - struct cxr_mesh *pmesh; + cxr_mesh *pmesh; int is_displacement, invalid; }; - struct cxr_auto_buffer solids; + cxr_auto_buffer solids; cxr_ab_init( &solids, sizeof(struct solidinf), 2 ); // Preprocessor 1: Island seperation @@ -2649,7 +2861,7 @@ CXR_API i32 cxr_convert_mesh_to_vmf(struct cxr_input_mesh *src, struct cxr_vdf * while(1) { - struct cxr_mesh *res = cxr_pull_island( main_mesh ); + cxr_mesh *res = cxr_pull_island( main_mesh ); if( res ) { cxr_ab_push( &solids, &(struct solidinf){ res, 0 }); @@ -2664,14 +2876,14 @@ CXR_API i32 cxr_convert_mesh_to_vmf(struct cxr_input_mesh *src, struct cxr_vdf * { struct solidinf *pinf = cxr_ab_ptr(&solids,i); - for( int j=0; jpmesh->polys.count; j++ ) + for( int j=0; jpmesh->abpolys.count; j++ ) { - struct cxr_polygon *poly = cxr_ab_ptr( &pinf->pmesh->polys, j ); + cxr_polygon *poly = cxr_ab_ptr( &pinf->pmesh->abpolys, j ); for( int k=0; kloop_total; k++ ) { - struct cxr_loop *lp = cxr_ab_ptr( &pinf->pmesh->loops, poly->loop_start+k ); - struct cxr_edge *edge = cxr_ab_ptr( &pinf->pmesh->edges, lp->edge_index ); + cxr_loop *lp = cxr_ab_ptr( &pinf->pmesh->abloops, poly->loop_start+k ); + cxr_edge *edge = cxr_ab_ptr( &pinf->pmesh->abedges, lp->edge_index ); if( edge->freestyle ) goto IL_SOLID_IS_DISPLACEMENT; @@ -2688,7 +2900,7 @@ CXR_API i32 cxr_convert_mesh_to_vmf(struct cxr_input_mesh *src, struct cxr_vdf * IL_SOLID_IS_DISPLACEMENT:; pinf->is_displacement = 1; - cxr_write_disp( pinf->pmesh, src, output, &abverts ); + cxr_write_disp( pinf->pmesh, src, output ); } // Preprocessor 3: Breakup non-convex shapes into sub-solids @@ -2704,7 +2916,7 @@ CXR_API i32 cxr_convert_mesh_to_vmf(struct cxr_input_mesh *src, struct cxr_vdf * while(1) { - struct cxr_mesh *res = cxr_pull_best_solid( pinf.pmesh, &abverts, 0, &error ); + cxr_mesh *res = cxr_pull_best_solid( pinf.pmesh, 0, &error ); if( res ) { @@ -2721,7 +2933,7 @@ CXR_API i32 cxr_convert_mesh_to_vmf(struct cxr_input_mesh *src, struct cxr_vdf * if( error & CXR_ERROR_NO_SOLIDS ) { error = 0x00; - res = cxr_pull_best_solid(pinf.pmesh, &abverts, 1, &error); + res = cxr_pull_best_solid(pinf.pmesh, 1, &error); if( res ) cxr_ab_push( &solids, &(struct solidinf){res,0} ); else break; @@ -2744,7 +2956,7 @@ CXR_API i32 cxr_convert_mesh_to_vmf(struct cxr_input_mesh *src, struct cxr_vdf * struct solidinf *solid = cxr_ab_ptr(&solids,i); if( !solid->is_displacement ) - cxr_debug_mesh( solid->pmesh, cxr_ab_ptr(&abverts,0), colours_random[cxr_range(i,8)] ); + cxr_debug_mesh( solid->pmesh, colours_random[cxr_range(i,8)] ); } } @@ -2772,11 +2984,11 @@ CXR_API i32 cxr_convert_mesh_to_vmf(struct cxr_input_mesh *src, struct cxr_vdf * cxr_vdf_node( output, "solid" ); cxr_vdf_ki32( output, "id", ++ cxr_context.brush_count ); - for( int j=0; jpmesh->polys.count; j++ ) + for( int j=0; jpmesh->abpolys.count; j++ ) { - struct cxr_polygon *poly = cxr_ab_ptr( &solid->pmesh->polys, j ); - struct cxr_loop *ploops = cxr_ab_ptr(&solid->pmesh->loops, poly->loop_start); - struct cxr_material *matptr = + cxr_polygon *poly = cxr_ab_ptr( &solid->pmesh->abpolys, j ); + cxr_loop *ploops = cxr_ab_ptr(&solid->pmesh->abloops, poly->loop_start); + cxr_material *matptr = poly->material_id < 0 || src->material_count == 0? &cxr_nodraw: &src->materials[ poly->material_id ]; @@ -2800,7 +3012,7 @@ CXR_API i32 cxr_convert_mesh_to_vmf(struct cxr_input_mesh *src, struct cxr_vdf * cxr_vdf_plane( output, "plane", verts[2], verts[1], verts[0] ); cxr_vdf_kv( output, "material", matptr->vmt_path ); - struct cxr_texinfo trans; + cxr_texinfo trans; cxr_calculate_axis(&trans, verts, uvs, (double[2]){ matptr->res[0], matptr->res[1] }); cxr_vdf_kaxis(output, "uaxis", trans.uaxis, trans.offset[0], trans.scale[0]); diff --git a/src/cxr_math.h b/src/cxr_math.h index 17c9902..031c61e 100644 --- a/src/cxr_math.h +++ b/src/cxr_math.h @@ -24,6 +24,11 @@ CXR_INLINE int cxr_max( int a, int b ) return a > b? a: b; } +CXR_INLINE double cxr_clampf( double v, double a, double b ) +{ + return cxr_minf( b, cxr_maxf( a, v ) ); +} + // Convert degrees to radians CXR_INLINE double cxr_rad( double deg ) { @@ -585,3 +590,58 @@ CXR_INLINE void plane_project_point( v4f plane, v3f a, v3f d ) v3_sub( a, ref, delta ); v3_muladds( a, plane, -v3_dot(delta,plane), d ); } + +CXR_INLINE double line_line_dist( v3f pa0, v3f pa1, v3f pb0, v3f pb1 ) +{ + v3f va, vb, n, delta; + v3_sub( pa1, pa0, va ); + v3_sub( pb1, pb0, vb ); + + v3_cross( va, vb, n ); + v3_normalize( n ); + + v3_sub( pb0, pa0, delta ); + + return fabs( v3_dot( n, delta ) ); +} + +CXR_INLINE double segment_segment_dist( v3f a0, v3f a1, v3f b0, v3f b1, + v3f a, v3f b ) +{ + v3f r,u,v; + v3_sub( b0, a0, r ); + v3_sub( a1, a0, u ); + v3_sub( b1, b0, v ); + + double ru = v3_dot( r,u ), + rv = v3_dot( r,v ), + uu = v3_dot( u,u ), + uv = v3_dot( u,v ), + vv = v3_dot( v,v ); + + double det = uu*vv - uv*uv, + s, + t; + + if( det < 1e-6 *uu*vv ) + { + s = ru/uu; + t = 0.0; + } + else + { + s = (ru*vv - rv*uv)/det; + t = (ru*uv - rv*uu)/det; + } + + s = cxr_clampf( s, 0.0, 1.0 ); + t = cxr_clampf( t, 0.0, 1.0 ); + + double S = cxr_clampf((t*uv + ru)/uu, 0.0, 1.0), + T = cxr_clampf((s*uv - rv)/vv, 0.0, 1.0); + + v3_muladds( a0, u, S, a ); + v3_muladds( b0, v, T, b ); + + return v3_dist( a, b ); +} diff --git a/src/cxr_mem.h b/src/cxr_mem.h index 64675b8..23e61c4 100644 --- a/src/cxr_mem.h +++ b/src/cxr_mem.h @@ -1,7 +1,8 @@ +typedef struct cxr_auto_buffer cxr_auto_buffer; + struct cxr_auto_buffer { - void *arr; - + u8 *arr; u32 esize, count, capacity; diff --git a/src/test.c b/src/test.c index cf4e395..1042c3a 100644 --- a/src/test.c +++ b/src/test.c @@ -3,6 +3,9 @@ int main(int arc, const char *argv[]) { - cxr_decompose( &test_mesh ); + cxr_vdf *vdo = cxr_vdf_open( "/home/harry/Documents/blender_addons_remote/addons/convexer/test.vmf" ); + + cxr_convert_mesh_to_vmf( &test_mesh, vdo ); + cxr_vdf_close(vdo); return 0; } -- 2.25.1