- Light patch BSP files; remove unwanted realtime effects
- Fastest VTF compressor (thanks to Richgel999 and stb)
- To come:
- - high quality level overviews automatically for CS:GO (csRadar)
-
Program structure:
File/folder Lang Purpose
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
#include "cxr_math.h"
#include "cxr_mem.h"
-// Utility
-// ============================================
-
static v4f colours_random[] =
{
{ 0.863, 0.078, 0.235, 0.4 },
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;
i32 loop_start, loop_total;
v3f normal;
v3f center;
- i32 material_id; // -1: interior material
+ i32 material_id; /* -1: interior material (nodraw) */
}
*polys;
struct cxr_mesh
{
- struct cxr_auto_buffer
- edges,
- loops,
- polys;
+ 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;
};
-// simple VDF writing interface
+/*
+ * Simplified VDF writing interface. No allocations or nodes, just write to file
+ */
struct cxr_vdf
{
FILE *fp;
.vmt_path = "tools/toolsnodraw"
};
-// Debugging callbacks
-// =============================================================================
+/*
+ * 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 };
fputs(buf,stdout);
}
-static void cxr_debug_line( v3f p0, v3f p1, v4f colour )
-{
- if( cxr_line_func )
- cxr_line_func( p0, p1, colour );
-}
-
-static void cxr_debug_box( v3f p0, double sz, v4f colour )
-{
- v3f a,b,c,d,
- a1,b1,c1,d1;
- v3_add(p0, (v3f){-sz,-sz,-sz}, a);
- v3_add(p0, (v3f){-sz, sz,-sz}, b);
- v3_add(p0, (v3f){ sz, sz,-sz}, c);
- v3_add(p0, (v3f){ sz,-sz,-sz}, d);
- v3_add(p0, (v3f){-sz,-sz,sz}, a1);
- v3_add(p0, (v3f){-sz, sz,sz}, b1);
- v3_add(p0, (v3f){ sz, sz,sz}, c1);
- v3_add(p0, (v3f){ sz,-sz,sz}, d1);
-
- cxr_debug_line( a,b, colour );
- cxr_debug_line( b,c, colour );
- cxr_debug_line( c,d, colour );
- cxr_debug_line( d,a, colour );
- cxr_debug_line( a1,b1, colour );
- cxr_debug_line( b1,c1, colour );
- cxr_debug_line( c1,d1, colour );
- cxr_debug_line( d1,a1, colour );
- cxr_debug_line( a,a1, colour );
- cxr_debug_line( b,b1, colour );
- cxr_debug_line( c,c1, colour );
- cxr_debug_line( d,d1, colour );
-}
-
-static void cxr_debug_arrow( v3f p0, v3f p1, v3f normal, double sz, v4f colour )
-{
- v3f dir, tan, p2, p3;
- v3_sub(p1,p0,dir);
- v3_normalize(dir);
-
- v3_cross(dir,normal,tan);
- v3_muladds( p1,dir, -sz, p2 );
- v3_muladds( p2,tan,sz,p3 );
- cxr_debug_line( p1, p3, colour );
- v3_muladds( p2,tan,-sz,p3 );
- cxr_debug_line( p1, p3, colour );
- cxr_debug_line( p0, p1, colour );
-}
-
-// Public API
-// =========================================================================
CXR_API void cxr_context_reset(void)
{
cxr_context.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" );
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; i<vdf->level; i++ )
fputs( " ", vdf->fp );
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,"");
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 );
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)
+/*
+ * 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(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)
-{
- cxr_vdf_printf( vdf, "\"%s\" \"[%f %f %f %f] %f\"\n", strk, normal[0],normal[1],normal[2],offset,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 );
for( int i=0; i<count; i++ )
}
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 );
for( int i=0; i<count; i++ )
{
- if( i == count-1 ) fprintf( vdf->fp, "%f %f %f", vecs[i][0], vecs[i][1], vecs[i][2] );
- else fprintf( vdf->fp, "%f %f %f ", vecs[i][0], vecs[i][1], vecs[i][2] );
+ 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(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 );
- cxr_vdf_printf( vdf, "\"%s\" \"%d %d %d %d\"\n",strk,(int)scale[0], (int)scale[1], (int)scale[2], (int)scale[3]);
+ cxr_vdf_printf( vdf, "\"%s\" \"%d %d %d %d\"\n",
+ strk,(int)scale[0], (int)scale[1], (int)scale[2], (int)scale[3]);
}
-// Public API
-// =========================================================================
+/*
+ * 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 );
+}
-static void cxr_debug_poly(struct cxr_mesh *mesh, struct cxr_polygon *poly, v3f *verts, v4f 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++ )
{
- 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 );
}
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; 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_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 )
-{
- 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);
+/*
+ * 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(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_abuffer new_edges;
+ cxr_ab_init( &new_edges, sizeof(cxr_edge), mesh->abedges.count );
- 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
- *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);
- // See if edge exists before adding it
+ /* Check if edge exists before adding */
for( int k=0; k<new_edges.count; k++ )
{
- struct cxr_edge *edge = cxr_ab_ptr(&new_edges,k);
+ cxr_edge *edge = cxr_ab_ptr(&new_edges,k);
if( edge->i0 == i0 && edge->i1 == i1 )
{
int orig_edge_id = lp0->edge_index;
lp0->edge_index = new_edges.count;
- struct cxr_edge edge = { i0, i1 };
- // --- ! ---
- // Copy extra information (sharp,freestyle.. etc) here!
+ cxr_edge edge = { i0, i1 };
- if( orig_edge_id < mesh->edges.count )
+ /*
+ * Copy extra information from original edges
+ */
+
+ 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
edge.freestyle = 0;
}
- // --- ! ---
cxr_ab_push( &new_edges, &edge );
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_abuffer loops_new;
+ cxr_ab_init( &loops_new, sizeof(cxr_loop), mesh->abloops.count );
int new_length=0;
- for( int i=0; i<mesh->polys.count; i++ )
+ for( int i=0; i<mesh->abpolys.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 )
{
for( int j=0; j<src_total; j++ )
{
- struct cxr_loop *loop = cxr_ab_ptr(&mesh->loops,src_start+j),
- *ldst = cxr_ab_ptr(&loops_new,dst->loop_start+j);
+ 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;
}
}
}
- 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 ++ )
}
}
}
- 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;
-}
-// Add polygon to mesh based on loop array
-static struct cxr_polygon *cxr_create_poly( struct cxr_mesh *mesh, v3f *vertices, struct cxr_loop poly[],
- int len, int start, int max )
-{
- if( len < 3 )
+ for( int i=0; i<mesh->abedges.count*2; i++ )
{
- cxr_log( "tried to add new poly with length %d!\n", len );
-
- if( len >= 2 )
+ if( polygon_edge_map[i] == -1 )
{
- for( int j=0; j<len; j++ )
- {
- int i0 = poly[j].index,
- i1 = poly[cxr_range(j+1,len)].index;
- cxr_debug_line( vertices[i0], vertices[i1], colour_error );
- }
+ free( polygon_edge_map );
+ return 0;
}
+ }
- return NULL;
+ 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;
}
- int nface_id = mesh->polys.count;
- struct cxr_polygon *new_face = cxr_ab_empty(&mesh->polys);
+ cxr_ab_reserve( &mesh->abpolys, 1 );
+ cxr_ab_reserve( &mesh->abloops, loop_count );
+ cxr_mesh_update( mesh );
- new_face->loop_start = mesh->loops.count;
- new_face->loop_total = len;
- new_face->material_id = -1;
+ cxr_polygon *poly = &mesh->polys[ mesh->abpolys.count ];
- // Calculate normal and center
- v3_zero( new_face->center );
+ poly->loop_start = mesh->abloops.count;
+ poly->loop_total = 0;
+ poly->material_id = -1;
+ v3_zero( poly->center );
- for( int j=0; j<len; j++ )
- {
- int i0 = poly[cxr_range(start+j,max)].index;
- struct cxr_loop *new_loop = cxr_ab_empty(&mesh->loops);
+ 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 );
- new_loop->poly_left = nface_id;
- new_loop->poly_right = -1;
- new_loop->index = i0;
- new_loop->edge_index = 0;
- v2_zero(new_loop->uv);
+ int nface_id = mesh->abpolys.count;
+ cxr_polygon *poly = &mesh->polys[ nface_id ];
- v3_add( new_face->center, vertices[new_loop->index], new_face->center );
- }
- v3_divs( new_face->center, new_face->loop_total, new_face->center );
-
- struct cxr_loop *lp0 = cxr_ab_ptr( &mesh->loops, new_face->loop_start ),
- *lp1 = cxr_ab_ptr( &mesh->loops, new_face->loop_start+1 ),
- *lp2 = cxr_ab_ptr( &mesh->loops, new_face->loop_start+2 );
+ 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( vertices[lp0->index], vertices[lp1->index], vertices[lp2->index], new_face->normal );
+ tri_normal(
+ verts[lp0->index], verts[lp1->index], verts[lp2->index], poly->normal);
- return cxr_ab_ptr(&mesh->polys, nface_id);
+ mesh->abpolys.count ++;
}
-// 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; i<island_len; i++ )
{
- struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys,island_current[i]);
+ cxr_polygon *poly = &mesh->polys[ island_current[i] ];
for( int j=0; j<poly->loop_total; j++ )
{
- struct cxr_loop *loop = cxr_ab_ptr(&mesh->loops, poly->loop_start+j);
+ cxr_loop *loop = &mesh->loops[ poly->loop_start+j ];
if( loop->poly_right != -1 )
{
}
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;
for( int i=0; i<island_len; i++ )
{
- struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys, 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; i<island_len; i++ )
{
- struct cxr_polygon *src = cxr_ab_ptr(&mesh->polys, island_current[i]);
- struct cxr_polygon *dst = cxr_ab_ptr(&newmesh->polys, i);
+ 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; j<src->loop_total; j++ )
{
- struct cxr_loop *lsrc = cxr_ab_ptr(&mesh->loops, src->loop_start+j),
- *ldst = cxr_ab_ptr(&newmesh->loops, dst->loop_start+j);
+ 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;
}
-// 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 )
+/*
+ * 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 *vertices = cxr_ab_ptr( vert_buffer, 0 );
+ v3f *verts = cxr_ab_ptr(mesh->p_abverts, 0);
- i32 *polygon_edge_map = cxr_mesh_link_loops(mesh);
+ 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 i=0; i<mesh->edges.count*2; i++ )
- if( polygon_edge_map[i] == -1 )
+ for( int j=0; j<len; j++ )
{
- cxr_log( "non-manifold edges are in the mesh; implicit internal geometry does not have full support\n" );
- free(polygon_edge_map);
- return NULL;
+ 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;
+}
- 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; i<mesh->edges.count; i++ )
+ for( int i=0; i<mesh->abloops.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; j<polya->loop_total; j++ )
{
- struct cxr_loop *loop = cxr_ab_ptr(&mesh->loops, polya->loop_start+j);
- if( plane_polarity( planeb, vertices[loop->index] ) > 0.001 ||
- v3_dot(polya->normal,polyb->normal) > 0.98500 )
+ 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;
+}
+
+/*
+ * 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<vert_buffer->count; i++ )
+ for( int i=0; i<mesh->p_abverts->count; i++ )
{
vertex_tagged[i]=0;
-
int num_connected = 0;
- // Create a list of polys that ref this vert
- for( int j=0; j<mesh->polys.count; j++ )
+
+ /* Create a list of polygons that refer to this vertex */
+ for( int j=0; j<mesh->abpolys.count; j++ )
{
- struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys,j);
+ cxr_polygon *poly = &mesh->polys[j];
for( int k=0; k<poly->loop_total; k++ )
{
- struct cxr_loop *loop = cxr_ab_ptr(&mesh->loops,poly->loop_start+k);
+ cxr_loop *loop = &mesh->loops[poly->loop_start+k];
if( loop->index == i )
{
connected_planes[num_connected ++] = j;
}
}
}
- // Check all combinations for a similar normal
+
+ /* Check all combinations for a similar normal */
for( int j=0; j<num_connected-1; j++ )
{
for( int k=j+1; k<num_connected; k++ )
{
- struct cxr_polygon *polyj = cxr_ab_ptr(&mesh->polys,connected_planes[j]);
- struct cxr_polygon *polyk = cxr_ab_ptr(&mesh->polys,connected_planes[k]);
+ cxr_polygon *polyj = &mesh->polys[connected_planes[j]],
+ *polyk = &mesh->polys[connected_planes[k]];
- if( v3_dot(polyj->normal, polyk->normal) > 0.98500 )
- 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; j<num_connected; j++ )
+ {
for( int k=j+1; k<num_connected; k++ )
{
- struct cxr_polygon *jpoly = cxr_ab_ptr(&mesh->polys, connected_planes[j]),
- *kpoly = cxr_ab_ptr(&mesh->polys, connected_planes[k]);
+ 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++ )
{
- 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;
+}
- // Connect all marked verts that share an edge
- // - We must take care not to completely isolate
- // a polygon with marked edges all around it
-
- int *hot_edge = malloc(mesh->edges.count*sizeof(int));
- for( int i=0; i< mesh->edges.count; i++ )
- hot_edge[i] = 0;
+/*
+ * 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];
- for( int i=0; i<mesh->polys.count; i ++ )
+ 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++ )
{
- struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys,i);
- int not_tagged = -1,
- tag_count = 0;
+ cxr_polygon *poly = (cxr_polygon *[2]){pa,pb}[j];
- for( int j=0; j<poly->loop_total; j++ )
+ for( int i=0; i<poly->loop_total; i++ )
{
- struct cxr_loop *loop = cxr_ab_ptr(&mesh->loops, poly->loop_start+j);
+ cxr_loop *lp = &mesh->loops[poly->loop_start+i];
+
+ if( lp->index == common_edge->i0 || lp->index == common_edge->i1 )
+ continue;
- if( !edge_tagged[ loop->edge_index ] )
- {
- if( not_tagged == -1 )
- not_tagged = loop->edge_index;
- else
- goto IL_SKIP_NO_HOT_EDGE;
- }
+ unique_verts[ unique_total ++ ] = lp->index;
}
-
- if( not_tagged != -1 )
- hot_edge[not_tagged]=1;
-
- IL_SKIP_NO_HOT_EDGE:;
}
- // Connect edges that have verts tagged, but is not a hot edge
- for( int i=0; i<mesh->edges.count; i ++ )
- {
- if( hot_edge[i] && preserve_hot_edges ) continue;
+ v3f ca, cb;
- struct cxr_edge *edge = cxr_ab_ptr(&mesh->edges,i);
- if( vertex_tagged[edge->i0] && vertex_tagged[edge->i1] )
- edge_tagged[i] = 1;
- }
+ for( int i=0; i<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] );
- /* Debug stuff --
- for( int i=0; i<vertex_count; i++ )
- if( vertex_tagged[i] )
- cxr_debug_box( vertices[i], 0.03, (v4f){0.0,0.0,0.0,1.0});
+ 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;
- for( int i=0; i < mesh->edges.count; i++ )
- {
- struct cxr_edge *edge = cxr_ab_ptr( &mesh->edges, i );
- if( edge_tagged[i] )
- cxr_debug_line( vertices[ edge->i0 ], vertices[ edge->i1 ], (v4f){0.0,0.0,0.0,1.0});
+ 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 );
- if( hot_edge[i] )
- cxr_debug_line( vertices[ edge->i0 ], vertices[ edge->i1 ], (v4f){0.0,1.0,1.0,1.0});
+ continue;
+ }
+ else
+ {
+ free( unique_verts );
+ return 1;
+ }
+ }
+ }
+ }
}
- */
- // count regions
- int *faces_tagged = malloc(mesh->polys.count*sizeof(int));
- for( int i=0; i<mesh->polys.count; i++ )
- faces_tagged[i] = -1;
-
- int *solid_buffer = malloc( mesh->polys.count*sizeof(int) );
- int solid_buffer_len = 0;
- struct csolid
+ if( debug )
{
- int start,count,edge_count;
- v3f center;
+ cxr_debug_line( verts[mesh->edges[common_edge_index].i0],
+ verts[mesh->edges[common_edge_index].i1],
+ colour_success );
}
- *candidates = malloc( mesh->polys.count *sizeof(struct csolid) );
- int candidate_count = 0;
- for( int i=0; i<mesh->polys.count; i++ )
- {
- if( faces_tagged[i] != -1 ) continue;
- faces_tagged[i] = i;
-
- int *solid = &solid_buffer[ solid_buffer_len ];
- int solid_len = 0;
-
- solid[solid_len++] = i;
-
- int search_start = 0;
-
- // Iterative search that connects regions of planes governed by rules:
- // - edge can add other face if the edge has less than two reflexes
- // - the face can no longer be used in future searches
+ free( unique_verts );
+ return 0;
+}
- IL_SEARCH_CONTINUE:;
+/*
+ * 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] ];
- int changed = 0;
- for( int j=search_start; j<solid_len; j++ )
+ for( int k=0; k<poly->loop_total; k++ )
{
- struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys, solid[j]);
+ cxr_loop *loop = &mesh->loops[ poly->loop_start+k ];
+ cxr_edge *edge = &mesh->edges[ loop->edge_index ];
- for( int k=0; k<poly->loop_total; k++ )
+ if( faces_tagged[ loop->poly_right ] == -1 )
{
- struct cxr_loop *loop = cxr_ab_ptr(&mesh->loops, poly->loop_start+k);
- struct cxr_edge *edge = cxr_ab_ptr(&mesh->edges, loop->edge_index );
-
- if( faces_tagged[ loop->poly_right ] == -1 )
+ if( !reflex_edges[loop->edge_index] )
{
- if( !edge_tagged[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++ )
{
- // Need to look ahead 1 step to make sure he does not want
- // to add any more planes that are coplanar with some of
- // our existing group
- //
- // TODO: is this unused due to hotedge improvements? leaving for safety...
-
- struct cxr_polygon *poly_to_add = cxr_ab_ptr(&mesh->polys, loop->poly_right );
- for( int l=0; l < poly_to_add->loop_total; l++ )
- {
- struct cxr_loop *loop1 = cxr_ab_ptr(&mesh->loops, poly_to_add->loop_start+l );
- struct cxr_polygon *future_face = cxr_ab_ptr(&mesh->polys, loop1->poly_right );
+ cxr_loop *lp1 = &mesh->loops[ newpoly->loop_start+l ];
+ cxr_polygon *future_face = &mesh->polys[ lp1->poly_right ];
- if( edge_tagged[ loop1->edge_index ] || loop1->poly_right == loop->poly_right )
- goto IL_SKIP_SIMILAR_PLANES;
+ 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] == loop1->poly_right )
- goto IL_SKIP_SIMILAR_PLANES;
-
- for( int m=0; m<solid_len; m++ )
- {
- struct cxr_polygon *polym = cxr_ab_ptr(&mesh->polys,solid[m]);
- if( v3_dot( polym->normal, future_face->normal ) > 0.98500 )
- goto IL_SKIP_PLANE_ADD;
- }
+ 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);
- IL_SKIP_SIMILAR_PLANES:;
+ if( pdist > CXR_PLANE_SIMILARITY_MAX )
+ goto dont_check;
}
- // This plane passed all checks so we can add it to the current solid
+ dont_check:;
+ }
- solid[ solid_len ++ ] = loop->poly_right;
- faces_tagged[ loop->poly_right ] = i;
+ /* 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 ++;
}
-
- IL_SKIP_PLANE_ADD:;
}
+
+ skip_plane:;
}
}
- search_start = solid_len;
- if(changed)
- goto IL_SEARCH_CONTINUE;
+ }
+ search_start = solid_len;
+ if(changed)
+ goto search_iterate;
- // Add entry
- struct csolid *csolid = &candidates[candidate_count ++];
- csolid->start = solid_buffer_len;
- csolid->count = solid_len;
- csolid->edge_count = 0;
-
- v3_zero( csolid->center );
- for( int j=0; j<solid_len; j++ )
- {
- struct cxr_polygon *polyj = cxr_ab_ptr(&mesh->polys, solid[j]);
- v3_add( polyj->center, csolid->center, csolid->center );
- csolid->edge_count += polyj->loop_total;
- }
- v3_divs( csolid->center, solid_len, csolid->center );
+ return solid_len;
+}
- solid_buffer_len += solid_len;
+struct csolid
+{
+ int start, count, edge_count;
+ v3f center;
+};
+
+struct temp_manifold
+{
+ struct manifold_loop
+ {
+ cxr_loop loop;
+ int split;
}
+ *loops;
- // Create all candidates who have one or less non-manifolds edges
- // Loop each candidate, determine the manifold, and pick the best one
+ int loop_count,
+ split_count;
- struct csolid *best_solid = NULL;
- int fewest_manifold_splits = INT32_MAX;
+ enum manifold_status
+ {
+ k_manifold_err,
+ k_manifold_none,
+ k_manifold_fragmented,
+ k_manifold_complete,
+ }
+ status;
+};
- struct cxr_loop *best_manifold = malloc( mesh->loops.count *sizeof(struct cxr_loop) );
- int *best_manifold_splits = malloc( mesh->loops.count *sizeof(int) );
- int best_manifold_len = 0;
- int max_solid_faces = 0;
+/*
+ * 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);
- 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_poly_finish( mesh );
+ }
+}
- for( int i=0; i<candidate_count; i++ )
+/*
+ * 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++ )
{
- struct csolid *solid = &candidates[i];
- max_solid_faces = cxr_max(max_solid_faces,solid->count);
+ cxr_polygon *poly = &mesh->polys[ solid_buffer[solid->start+j] ];
- if( solid->count <= 2 )
- continue;
+ 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;
- int init_reverse = 0;
- int unique_edge_count = 0;
+ cxr_edge *current = &mesh->edges[ edge_list[0]->edge_index ];
- for( int j=0; j<solid->count; j++ )
+ 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 )
{
- struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys, solid_buffer[solid->start+j]);
+ current = other;
+ int lastpt = endpt;
- for( int k=0; k<poly->loop_total; k++ )
+ 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 )
{
- struct cxr_loop *loop = cxr_ab_ptr(&mesh->loops, poly->loop_start+k);
+ 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;
- for( int l=0; l<unique_edge_count; l++ )
- if( edge_list[l] == loop->edge_index )
- goto IL_EDGE_ALREADY_PRESENT;
+ 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;
- // Check if right edge references a polygon that is not
- // present inside the current solid candidate
- for( int l=0; l<solid->count; l++ )
- if( loop->poly_right == solid_buffer[solid->start+l] )
- goto IL_EDGE_ALREADY_PRESENT;
+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);
- edge_list[ unique_edge_count ] = loop->edge_index;
- edge_lefts[ unique_edge_count ] = loop->poly_left;
+ v3f intersect;
- if( unique_edge_count == 0 )
+ if( plane_intersect(planei,planej,planek,intersect) )
{
- struct cxr_edge *edgeptr = cxr_ab_ptr(&mesh->edges, loop->edge_index);
- if( edgeptr->i1 == loop->index )
- init_reverse = 1;
- }
+ /* 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 );
- unique_edge_count ++;
- IL_EDGE_ALREADY_PRESENT:;
+ 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 );
+ }
}
}
-
- // This solid is already fully connected
- if( unique_edge_count == 0 )
- continue;
-
- // Link edges together to create new manifold
- // Corners are created when two edges share a polygon face
- // This way we can split it into regions
-
- for( int j=0; j<vert_buffer->count; j++ )
- vertex_tagged[j] = -1;
-
- // Start with a loop edge which was tagged
- struct cxr_edge *current = cxr_ab_ptr(&mesh->edges, edge_list[0]);
+ }
+
+ 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" );
- int endpt = (!init_reverse)? current->i0: current->i1,
- start = endpt,
- curface = edge_lefts[0];
+ return NULL;
+ }
+
+ int *edge_tagged = cxr_mesh_reflex_edges( mesh );
+ int *vertex_tagged = cxr_mesh_reflex_vertices( mesh );
- int manifold_len = 0;
- int split_count = 0;
+ /*
+ * 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;
- IL_MANIFOLD_CONTINUE:
- for( int j=0; j<unique_edge_count; j++ )
+ for( int j=0; j<poly->loop_total; j++ )
{
- struct cxr_edge *other = cxr_ab_ptr(&mesh->edges, edge_list[j]);
- if( other == current )
- continue;
+ cxr_loop *loop = &mesh->loops[ poly->loop_start+j ];
- if( other->i0 == endpt || other->i1 == endpt )
+ if( !edge_tagged[ loop->edge_index ] )
{
- current = other;
- int lastpt = endpt;
-
- if( other->i0 == endpt ) endpt = current->i1;
- else endpt = current->i0;
-
- if( curface==edge_lefts[j] )
- {
- splits[ manifold_len ] = 1;
- split_count ++;
- }
+ if( not_tagged == -1 )
+ not_tagged = loop->edge_index;
else
- splits[ manifold_len ] = 0;
-
- // Append to intermidiary manifold
- manifold[ manifold_len ].edge_index = edge_list[j];
- manifold[ manifold_len ].poly_left = edge_lefts[j];
- manifold[ manifold_len ].index = lastpt;
- manifold[ manifold_len ].poly_right =
- polygon_edge_map[ edge_list[j]*2 ] == edge_lefts[j]?
- polygon_edge_map[ edge_list[j]*2+1 ]:
- polygon_edge_map[ edge_list[j]*2+0 ];
- manifold_len ++;
-
- curface = edge_lefts[j];
-
- if(endpt == start) goto IL_MANIFOLD_COMPLETE;
- goto IL_MANIFOLD_CONTINUE;
+ goto edge_unimportant;
}
}
- cxr_log( "Failed to link manifold, count: %d\n", manifold_len );
- for( int j=0; j<solid->count; j++ )
- {
- cxr_log( "p%d\n", solid_buffer[solid->start+j] );
- struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys, solid_buffer[solid->start+j]);
- cxr_debug_poly( mesh, poly, vertices, (v4f){0.2,0.0,0.0,1.0} );
- }
+ 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;
- for( int j=0; j<unique_edge_count; j++ )
+ 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++ )
{
- struct cxr_edge *uedge = cxr_ab_ptr(&mesh->edges, edge_list[j]);
- cxr_debug_line(vertices[uedge->i0],vertices[uedge->i1],(v4f){0.4,0.0,0.0,1.0});
+ 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;
+ }
- for( int j=0; j<manifold_len-1; j++ )
- {
- struct cxr_loop *lp0 = &manifold[j],
- *lp1 = &manifold[cxr_range(j+1,manifold_len)];
+ free( edge_tagged );
+ free( vertex_tagged );
+ free( faces_tagged );
- cxr_debug_line(vertices[lp0->index],vertices[lp1->index], colour_error );
- }
+ /*
+ * Choosing the best solid: most defined manifold
+ */
+ struct csolid *best_solid = NULL;
+ int fewest_manifold_splits = INT32_MAX;
- cxr_debug_mesh( mesh, vertices, (v4f){0.0,0.0,0.0, 0.9} );
- *error = CXR_ERROR_BAD_MANIFOLD;
-
- free(edge_list);
- free(edge_lefts);
- free(manifold);
- free(splits);
- free(edge_tagged);
- free(vertex_tagged);
- free(hot_edge);
- free(faces_tagged);
- free(solid_buffer);
- free(candidates);
- free(best_manifold);
- free(best_manifold_splits);
- free(polygon_edge_map);
- return NULL;
+ 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);
- IL_MANIFOLD_COMPLETE:;
-
- if( manifold_len < unique_edge_count )
+ if( solid->count <= 2 )
continue;
- else
+
+ 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( split_count < fewest_manifold_splits )
+ if( manifold.split_count < fewest_manifold_splits )
{
- fewest_manifold_splits = split_count;
+ fewest_manifold_splits = manifold.split_count;
best_solid = solid;
- for( int j=0; j<manifold_len; j++ )
- {
- best_manifold[j] = manifold[j];
- best_manifold_splits[j] = splits[j];
- }
- best_manifold_len = manifold_len;
+ free( best_manifold.loops );
+ best_manifold = manifold;
+ continue;
}
}
+
+ if( manifold.status != k_manifold_none )
+ free( manifold.loops );
}
- free(edge_list);
- free(edge_lefts);
- free(manifold);
- free(splits);
-
if( max_solid_faces < 2 )
{
*error = CXR_ERROR_NO_SOLIDS;
- free(edge_tagged);
- free(vertex_tagged);
- free(hot_edge);
- free(faces_tagged);
free(solid_buffer);
free(candidates);
- free(best_manifold);
- free(best_manifold_splits);
- free(polygon_edge_map);
+ free(best_manifold.loops);
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; i<best_solid->count; i++ )
{
- int nface_id = pullmesh->polys.count;
+ int nface_id = pullmesh->abpolys.count;
+ int exist_plane_id = solid_buffer[best_solid->start+i];
- 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[ exist_plane_id ],
+ *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; j<exist_face->loop_total; j++ )
{
- struct cxr_loop *exist_loop = cxr_ab_ptr(&mesh->loops, exist_face->loop_start+j);
- struct cxr_loop *new_loop = cxr_ab_empty(&pullmesh->loops);
+ 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;
exist_face->loop_total = -1;
}
-
- // Split manifold up by unique planes if it has more than 1
- // otherwise, just use that face
- //
- // TODO: Need to build new manifold in sections, stably
- // currently there is an unsupported case where the manifold splits
- // are on located on an implicit face, causing 1-length manifolds.
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; i<best_manifold_len; i++ )
- {
- int i0 = i,
- i1 = cxr_range(i+1,best_manifold_len);
-
- cxr_debug_line( vertices[best_manifold[i0].index], vertices[best_manifold[i1].index], colour_error );
- if( best_manifold_splits[i] )
- cxr_debug_box( vertices[best_manifold[i0].index], 0.04, colour_success );
- }
- #endif
-
- // This is a really strange observation, however it *seems* to apply to the kinds
- // of geometry we are dealing with. If the split count is odd, the manifold can be
- // created easily, no folding required.
- //
- // When it is even, it appears that internal implicit geometry is required, so we
- // need to fold the loops we create. Its really weird, but for some reason works on
- // the geometry rules we've defined.
- // TODO: Find a well defined rule here.
-
+ /* 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;
- IL_MANIFOLD_BUILD_REPEAT:
+ manifold_repeat:
- for( int j=0; j<best_manifold_len; j++ )
+ for( int j=0; j < best_manifold.loop_count; j++ )
{
- if( best_manifold_splits[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++ )
{
- struct cxr_loop *loop = &best_manifold[j];
+ int index1 = cxr_range(j+k, best_manifold.loop_count );
+ cxr_loop *loop1 = &best_manifold.loops[index1].loop;
- for( int k=1; k<best_manifold_len; k++ )
+ if( best_manifold.loops[index1].split )
{
- int index1 = cxr_range(j+k,best_manifold_len);
- struct cxr_loop *loop1 = &best_manifold[index1];
-
- if( best_manifold_splits[index1] )
- {
- if( k==1 )
- break;
+ if( k==1 )
+ break;
- new_polys ++;
+ new_polys ++;
- if( new_polys > best_manifold_len )
+ 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++ )
{
- cxr_log( "Programming error: Too many new polys!\n" );
- exit(1);
+ 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 );
+ }
- cxr_create_poly( pullmesh, vertices, best_manifold, k+1, j, best_manifold_len );
+ /* Collapse down manifold */
+ if( collapse_used_segments )
+ {
+ best_manifold.loops[j].split = 0;
+ best_manifold.loops[index1].split = 0;
- // Remove new section from manifold
- if( collapse_used_segments )
+ 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 ++ )
{
- best_manifold_splits[j] = 0;
- best_manifold_splits[index1] = 0;
-
- int new_length = (best_manifold_len-(k-1));
-
- struct cxr_loop *new_manifold = malloc( new_length*sizeof(struct cxr_loop) );
- int *new_manifold_splits = malloc( new_length*sizeof(int) );
-
- for( int l=0; l<new_length; l ++ )
- {
- int i_src = cxr_range( j+k+l, best_manifold_len );
- new_manifold[l] = best_manifold[i_src];
- new_manifold_splits[l] = best_manifold_splits[i_src];
- }
-
- free( best_manifold );
- free( best_manifold_splits );
- best_manifold = new_manifold;
- best_manifold_splits = new_manifold_splits;
-
- best_manifold_len = new_length;
-
- goto IL_MANIFOLD_BUILD_REPEAT;
+ int i_src = cxr_range( j+k+l, best_manifold.loop_count);
+ new_manifold.loops[l] = best_manifold.loops[i_src];
}
- j=j+k-1;
- break;
+ free( best_manifold.loops );
+ best_manifold = new_manifold;
+
+ goto manifold_repeat;
}
+
+ j=j+k-1;
+ break;
}
}
}
- if( best_manifold_len && collapse_used_segments )
+ if( best_manifold.loop_count && collapse_used_segments )
{
- cxr_create_poly( pullmesh, vertices, best_manifold, best_manifold_len, 0, best_manifold_len );
+ cxr_create_poly_full( pullmesh, &best_manifold );
new_polys ++;
}
}
else
{
- cxr_create_poly( pullmesh, vertices, best_manifold, best_manifold_len, 0, best_manifold_len );
+ cxr_create_poly_full( pullmesh, &best_manifold );
new_polys = 1;
}
- // vert_buffer may be reallocated by the next section of code,
- // force a NULLref on vertices to catch any errors
- vertices = NULL;
-
- // Implicit geometry reconstruction
- // If there's 3 or more planes, collide them together to see if any new
- // vertices need to be created on the mesh
if( new_polys >= 3 )
{
- for( int i=0; i<new_polys-2; i++ )
+ if( !cxr_build_implicit_geo( pullmesh, new_polys, pullmesh_new_start ))
{
- for( int j=i+1; j<new_polys-1; j++ )
- {
- for( int k=j+1; k<new_polys; k++ )
- {
- struct cxr_polygon *ptri = cxr_ab_ptr( &pullmesh->polys, pullmesh_new_start+i ),
- *ptrj = cxr_ab_ptr( &pullmesh->polys, pullmesh_new_start+j ),
- *ptrk = cxr_ab_ptr( &pullmesh->polys, pullmesh_new_start+k );
-
- v4f planei, planej, planek;
- normal_to_plane(ptri->normal,ptri->center,planei);
- normal_to_plane(ptrj->normal,ptrj->center,planej);
- normal_to_plane(ptrk->normal,ptrk->center,planek);
-
- v3f intersect;
-
- if( plane_intersect(planei,planej,planek,intersect) )
- {
- // cxr_debug_box( intersect, 0.05, colour_error );
-
- // Make sure this point is within the convex region, otherwise treat
- // it as a degenerate case
-
- int point_valid = 1;
- for( int l=0; l<pullmesh->polys.count; l++ )
- {
- struct cxr_polygon *ptrl = cxr_ab_ptr(&pullmesh->polys,l);
- v4f planel;
-
- normal_to_plane(ptrl->normal, ptrl->center, planel);
-
- if( plane_polarity( planel, intersect ) > 0.01 )
- {
- cxr_log( "degen vert, planes %d, %d, %d [max:%d]\n", i,j,k, new_polys );
- *error = CXR_ERROR_DEGEN_IMPLICIT;
-
- cxr_debug_poly( pullmesh, ptri, cxr_ab_ptr(vert_buffer,0), colours_random[3] );
- cxr_debug_poly( pullmesh, ptrj, cxr_ab_ptr(vert_buffer,0), colours_random[1] );
- cxr_debug_poly( pullmesh, ptrk, cxr_ab_ptr(vert_buffer,0), colours_random[2] );
-
- point_valid = 0;
- break;
- }
- }
-
- if( !point_valid ) continue;
-
- // Extend faces to include this point
- int nvertid = vert_buffer->count;
- cxr_ab_push( vert_buffer, intersect );
-
- ptrj->loop_start += 1;
- ptrk->loop_start += 2;
-
- cxr_ab_reserve(&pullmesh->loops, 3);
- struct cxr_loop *lloopi = cxr_ab_empty_at(&pullmesh->loops, ptri->loop_start+ptri->loop_total),
- *lloopj = cxr_ab_empty_at(&pullmesh->loops, ptrj->loop_start+ptrj->loop_total),
- *lloopk = cxr_ab_empty_at(&pullmesh->loops, ptrk->loop_start+ptrk->loop_total);
-
- lloopi->index = nvertid;
- lloopj->index = nvertid;
- lloopk->index = nvertid;
- lloopi->edge_index = 0; lloopj->edge_index = 0; lloopk->edge_index = 0;
- lloopi->poly_left = pullmesh_new_start+i;
- lloopj->poly_left = pullmesh_new_start+j;
- lloopk->poly_left = pullmesh_new_start+k;
- lloopi->poly_right = -1; lloopj->poly_right = -1; lloopk->poly_right = -1;
-
- v2_zero(lloopi->uv);
- v2_zero(lloopj->uv);
- v2_zero(lloopk->uv);
-
- ptri->loop_total ++;
- ptrj->loop_total ++;
- ptrk->loop_total ++;
-
- // Adjust centers of faces
- v3_lerp( ptri->center, intersect, 1.0/(double)ptri->loop_total, ptri->center );
- v3_lerp( ptrj->center, intersect, 1.0/(double)ptrj->loop_total, ptrj->center );
- v3_lerp( ptrk->center, intersect, 1.0/(double)ptrk->loop_total, ptrk->center );
- }
- }
- }
+ free(solid_buffer);
+ free(candidates);
+ free(best_manifold.loops);
+
+ cxr_free_mesh( pullmesh );
+ *error = CXR_ERROR_DEGEN_IMPLICIT;
+ return NULL;
}
}
- // Copy faces from pullsolid into orig mesh
-
+ /*
+ * 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->polys.count;
-
- struct cxr_polygon *pface = cxr_ab_ptr(&pullmesh->polys,pullmesh_new_start+i);
- struct cxr_polygon *rip_face = cxr_ab_empty(&mesh->polys);
+ 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->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; j<rip_face->loop_total; j++ )
{
- struct cxr_loop *ploop = cxr_ab_ptr(&pullmesh->loops, pface->loop_start+pface->loop_total-j-1),
- *rloop = cxr_ab_empty(&mesh->loops);
+ 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;
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 );
+ cxr_mesh_clean_faces( pullmesh );
cxr_mesh_clean_edges( pullmesh );
- free(edge_tagged);
- free(vertex_tagged);
- free(hot_edge);
- free(faces_tagged);
free(solid_buffer);
free(candidates);
- free(best_manifold);
- free(best_manifold_splits);
- free(polygon_edge_map);
+ free(best_manifold.loops);
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);
+ free(best_manifold.loops);
return NULL;
}
-static struct cxr_mesh *cxr_to_internal_format(struct cxr_input_mesh *src, struct cxr_auto_buffer *abverts)
-{
- // Split mesh into islands
- struct cxr_mesh *mesh = cxr_alloc_mesh( src->edge_count, src->loop_count, src->poly_count );
+/*
+ * 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 );
- // Copy input data into working mesh
- memcpy( cxr_ab_ptr( &mesh->edges, 0 ), src->edges, src->edge_count*sizeof(struct cxr_edge));
- memcpy( cxr_ab_ptr( &mesh->polys, 0 ), src->polys, src->poly_count*sizeof(struct cxr_polygon));
- memcpy( cxr_ab_ptr( abverts, 0 ), src->vertices, src->vertex_count*sizeof(v3f));
- mesh->edges.count = src->edge_count;
- mesh->loops.count = src->loop_count;
- mesh->polys.count = src->poly_count;
+ 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++ )
{
- 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
);
}
-// Main function
-static void cxr_calculate_axis(
- struct cxr_texinfo *transform,
- v3f verts[3],
- v2f uvs[3],
- v2f texture_res
- )
-{
- v2f tT, bT; // Tangent/bitangent pairs for UV space and world
+/*
+ * 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 );
v3_sub( verts[0], verts[1], tW );
v3_sub( verts[2], verts[1], bW );
- // Use arbitrary projection if there is no UV
+ /* Use arbitrary projection if there is no UV */
if( v2_length( tT ) < 0.0001 || v2_length( bT ) < 0.0001 )
{
v3f uaxis, normal, 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
+ /* Detect if UV is reversed */
double winding = v2_cross( tT, bT ) >= 0.0f? 1.0f: -1.0f;
-
- // UV projection reference
+
+ /* 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
+ /* Reproject reference into world space, including skew */
v3f uaxis1, vaxis1;
v3_muls( tW, v2_cross(vX,bT) / v2_cross(bT,tT), uaxis1 );
v3_normalize( uaxis1 );
v3_normalize( vaxis1 );
- // Apply source transform to axis (yes, they also need to be swapped)
+ /* Apply source transform to axis (yes, they also need to be swapped) */
v3f norm, uaxis, vaxis;
v3_cross( bW, tW, norm );
v3_cross( vaxis1, norm, uaxis );
v3_cross( uaxis1, norm, vaxis );
- // real UV scale
+ /* real UV scale */
v2f uvmin, uvmax, uvdelta;
v2_minv( uvs[0], uvs[1], uvmin );
v2_minv( uvmin, uvs[2], uvmin );
v2_sub( uvmax, uvmin, uvdelta );
- // world-uv scale
+ /* world-uv scale */
v2f uvminw, uvmaxw, uvdeltaw;
uvminw[0] = -support_distance( verts, uaxis, -1.0f );
uvmaxw[0] = support_distance( verts, uaxis, 1.0f );
v2_sub( uvmaxw, uvminw, uvdeltaw );
- // VMf uv scale
+ /* 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
+ /* Find offset via 'natural' point */
v2f target_uv, natural_uv, tex_offset;
v2_mul( uvs[0], texture_res, target_uv );
tex_offset[0] = target_uv[0]-natural_uv[0];
tex_offset[1] = -(target_uv[1]-natural_uv[1]);
- // Copy everything into output
+ /* Copy everything into output */
v3_copy( uaxis, transform->uaxis );
v3_copy( vaxis, transform->vaxis );
v2_copy( tex_offset, transform->offset );
v2_copy( uv_scale, transform->scale );
+ transform->winding = winding;
}
-CXR_API struct cxr_input_mesh *cxr_decompose(struct cxr_input_mesh *src)
+CXR_API cxr_input_mesh *cxr_write_test_data( cxr_input_mesh *src )
{
-#ifdef CXR_DEBUG_WRITE_MESH
- FILE *yeet = fopen( "/home/harry/Documents/blender_addons_remote/addons/convexer/solid.h", "w" );
-
- fprintf( yeet, "v3f test_verts[] = {\n" );
+ 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( yeet, " { %f, %f, %f },\n",
+ fprintf( fp, " { %f, %f, %f },\n",
src->vertices[i][0],
src->vertices[i][1],
src->vertices[i][2] );
}
- fprintf( yeet, "};\n" );
+ fprintf( fp, "};\n" );
- fprintf( yeet, "struct cxr_input_loop test_loops[] = {\n" );
+ fprintf( fp, "struct cxr_input_loop test_loops[] = {\n" );
for( int i=0; i<src->loop_count; i ++ )
{
- fprintf( yeet, " {%d, %d},\n",
+ fprintf( fp, " {%d, %d},\n",
src->loops[i].index,
src->loops[i].edge_index);
}
- fprintf( yeet, "};\n" );
+ fprintf( fp, "};\n" );
- fprintf( yeet, "struct cxr_polygon test_polys[] = {\n" );
+ fprintf( fp, "struct cxr_polygon test_polys[] = {\n" );
for( int i=0; i <src->poly_count; i++ )
{
- fprintf( yeet, " {%d, %d, {%f, %f, %f}, {%f, %f, %f}},\n",
+ 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].center[1],
src->polys[i].center[2] );
}
- fprintf( yeet, "};\n" );
+ fprintf( fp, "};\n" );
- fprintf( yeet, "struct cxr_edge test_edges[] = {\n" );
+ fprintf( fp, "struct cxr_edge test_edges[] = {\n" );
for( int i=0; i<src->edge_count; i++ )
{
- fprintf( yeet, " {%d, %d},\n",
+ fprintf( fp, " {%d, %d, %d},\n",
src->edges[i].i0,
- src->edges[i].i1
+ src->edges[i].i1,
+ src->edges[i].freestyle
);
}
- fprintf( yeet, "};\n" );
-
- fprintf( yeet, "struct cxr_input_mesh test_mesh = {\n" );
- fprintf( yeet, " .vertices = test_verts,\n" );
- fprintf( yeet, " .loops = test_loops,\n" );
- fprintf( yeet, " .edges = test_edges,\n" );
- fprintf( yeet, " .polys = test_polys,\n" );
- fprintf( yeet, " .poly_count=%d,\n", src->poly_count );
- fprintf( yeet, " .vertex_count=%d,\n", src->vertex_count );
- fprintf( yeet, " .edge_count=%d,\n",src->edge_count );
- fprintf( yeet, " .loop_count=%d\n", src->loop_count );
- fprintf( yeet, "};\n" );
-
- fclose( yeet );
-#endif
-
- struct cxr_auto_buffer abverts;
- struct cxr_mesh *main_mesh = cxr_to_internal_format( src, &abverts );
-
- u32 error = 0x00;
-
- struct cxr_auto_buffer solids;
- cxr_ab_init( &solids, sizeof(struct cxr_mesh *), 2 );
-
- // TODO: Preprocessor stages
- // - Split mesh up into islands before doing anything here
- // - Snap vertices to grid (0.25u) ?
- while(1)
- {
- struct cxr_mesh *res = cxr_pull_best_solid( main_mesh, &abverts, 0, &error );
- if( res )
- {
- cxr_ab_push( &solids, &res );
- if( error ) break;
- }
- else
- {
- if( error )
- {
- // If no solids error we can rety while preserving 'hot' edges
-
- if( error & CXR_ERROR_NO_SOLIDS )
- {
- error = 0x00;
- res = cxr_pull_best_solid(main_mesh, &abverts, 1, &error);
-
- if( res ) cxr_ab_push( &solids, &res );
- else break;
-
- if( error ) break;
- }
- else break;
- }
- else
- break;
- }
- }
-
- cxr_ab_push( &solids, &main_mesh );
-
- if( !error )
- {
- for( int i=0; i<solids.count; i++ )
- {
- struct cxr_mesh **mptr = cxr_ab_ptr(&solids,i);
- cxr_debug_mesh( *mptr, cxr_ab_ptr(&abverts,0), colours_random[cxr_range(i,8)] );
- }
- }
-
- for( int i=0; i<solids.count; i++ )
- {
- struct cxr_mesh **mptr = cxr_ab_ptr(&solids,i);
- cxr_free_mesh( *mptr );
- }
-
- cxr_ab_free( &abverts );
- cxr_ab_free( &solids );
+ 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;
}
return component;
}
-// Convert contiguous mesh to patch of displacments
-//
-static void cxr_write_disp(struct cxr_mesh *mesh, struct cxr_input_mesh *inputmesh,
- struct cxr_vdf *output,
- struct cxr_auto_buffer *abverts)
-{
- // Create a graph which maps vertices by their connections
+/*
+ * 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; // Index into the connection graph
+ int con_start, con_count;
int boundary,
used,
search,
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; i<abverts->count; i++ )
+ for( int i=0; i<mesh->p_abverts->count; i++ )
{
struct vertinfo *info = &vertinfo[i];
info->con_start = con_pos;
info->search = 0;
info->alpha = 0.0;
- for( int j=0; j<mesh->edges.count; j++ )
+ for( int j=0; j<mesh->abedges.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 )
{
}
}
- // Find best normal for brush patch. VBSP uses the original brush
- // as reference for decal projection.
- //
- // These are clamped to be cardinal directions as to make the VMF somewhat
- // human editable.
+ /*
+ * 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); v4_zero(refn);
+ v3_zero(refv); v3_zero(refu); v3_zero(refn);
- 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];
v3_add( poly->normal, avg_normal, avg_normal );
}
- v3_divs( avg_normal, mesh->polys.count, avg_normal );
- v3_normalize( avg_normal ); // TODO: This can be zero length. Should add a safety check
- // normalize function that checks for small length before
- // carrying out, otherwise we get inf/nan values...
- int n_cardinal = cxr_cardinal( avg_normal, -1 );
-
- // Approximately matching the area of the result brush faces to the actual area
- // this is to assign a 'best guess' amount of lightmap texels.
- //
+ 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;
v3_fill( faceboundmin, CXR_BIG_NUMBER );
v3_fill( faceboundmax, -CXR_BIG_NUMBER );
- 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 *lp0 = cxr_ab_ptr(&mesh->loops, poly->loop_start+j);
+ cxr_loop *lp0 = &mesh->loops[ poly->loop_start+j ];
v2_minv( lp0->uv, uvboundmin, uvboundmin);
v2_maxv( lp0->uv, uvboundmax, uvboundmax);
- v3_minv( cxr_ab_ptr(abverts,lp0->index), faceboundmin, faceboundmin );
- v3_maxv( cxr_ab_ptr(abverts,lp0->index), faceboundmax, faceboundmax );
+ v3_minv( verts[lp0->index], faceboundmin, faceboundmin );
+ v3_maxv( verts[lp0->index], faceboundmax, faceboundmax );
}
for( int j=0; j<poly->loop_total-2; j++ )
{
- struct cxr_loop *lp0 = cxr_ab_ptr(&mesh->loops, poly->loop_start),
- *lp1 = cxr_ab_ptr(&mesh->loops, poly->loop_start+j+1),
- *lp2 = cxr_ab_ptr(&mesh->loops, poly->loop_start+j+2);
+ 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;
sf = sqrt( face_area / uv_area );
int corner_count = 0;
- // Vertex classification
- for( int i=0; i<abverts->count; i++ )
+ /*
+ * 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;
else
non_manifold = 0;
}
+
if( count > 2 || non_manifold )
{
info->corner = 1;
corner_count ++;
-
- //cxr_debug_box( cxr_ab_ptr(abverts,i), 0.1, colour_success );
}
}
+ /*
+ * TODO(harry): This currently only supports power 2 displacements
+ * its quite straightforward to upgrade it.
+ *
+ * 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;
- struct cxr_texinfo texinfo_shared;
- for( int i=0; i<mesh->polys.count; i++ )
+ for( int i=0; i<mesh->abpolys.count; i++ )
{
- struct cxr_polygon *basepoly = cxr_ab_ptr(&mesh->polys,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);
- 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 )
+ continue;
- if( info->corner )
- {
- int corner_count = 1;
-
- struct cxr_material *matptr =
- basepoly->material_id < 0 || inputmesh->material_count == 0?
- &cxr_nodraw:
- &inputmesh->materials[ basepoly->material_id ];
-
- dispedge_count = 2;
- dispedge[0] = l0->index;
- dispedge[1] = l1->index;
- v2_copy( l0->uv, corner_uvs[0] );
-
- // Consume (remove) faces we use for corners
- basepoly->loop_total = -1;
-
- cxr_debug_box( cxr_ab_ptr(abverts,l0->index),0.08,(v4f){0.0,0.0,1.0,1.0});
-
- // Collect edges
- // --------------------
+ 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]];
- while( dispedge_count < 17 )
+ int newvert = 0;
+
+ if( edge_head->corner )
{
- 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++ )
{
- // Find a polygon that has the edge C-1 -> C
- for( int j=0; j<mesh->polys.count && !newvert; j++ )
+ cxr_polygon *poly = &mesh->polys[j];
+
+ for( int k=0; k<poly->loop_total; k ++ )
{
- struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys,j);
+ int i0 = k,
+ i1 = cxr_range(k+1,poly->loop_total);
- for( int k=0; k<poly->loop_total; k ++ )
+ 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] )
{
- int i0 = k,
- i1 = cxr_range(k+1,poly->loop_total);
-
- struct cxr_loop *l0 = cxr_ab_ptr(&mesh->loops, poly->loop_start+i0),
- *l1 = cxr_ab_ptr(&mesh->loops, poly->loop_start+i1);
-
- if( l0->index == dispedge[dispedge_count-2] &&
- l1->index == dispedge[dispedge_count-1] )
- {
- // Take the vertex after that edge
- v2_copy( l1->uv, corner_uvs[corner_count ++] );
-
- int i2 = cxr_range(i1+1,poly->loop_total);
- struct cxr_loop *l2 = cxr_ab_ptr(&mesh->loops, poly->loop_start+i2);
-
- dispedge[dispedge_count ++] = l2->index;
- newvert = 1;
- poly->loop_total = -1;
- break;
- }
+ /* 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
+ }
+ else
+ {
+ for( int j=0; j<edge_head->con_count; j++ )
{
- for( int j=0; j<edge_head->con_count; j++ )
- {
- int con = graph[edge_head->con_start+j];
+ int con = graph[edge_head->con_start+j];
- if( con == -1 )
- continue;
+ if( con == -1 )
+ continue;
- if( dispedge_count > 1 )
- if( con == dispedge[dispedge_count-2] )
- continue;
-
- struct vertinfo *coninfo = &vertinfo[con];
-
- if( !coninfo->boundary )
+ if( dispedge_count > 1 )
+ if( con == dispedge[dispedge_count-2] )
continue;
-
- /*
- cxr_debug_arrow( cxr_ab_ptr(abverts,dispedge[dispedge_count-1]),
- cxr_ab_ptr(abverts,con),
- (v3f){0,0,1},
- 0.1,
- colour_success );
- */
-
- dispedge[ dispedge_count ++ ] = con;
- newvert = 1;
-
- break;
- }
- }
+
+ struct vertinfo *coninfo = &vertinfo[con];
+
+ if( !coninfo->boundary )
+ continue;
+
+ dispedge[ dispedge_count ++ ] = con;
+ newvert = 1;
- if( !newvert )
- {
- cxr_debug_box(cxr_ab_ptr(abverts,dispedge[dispedge_count-1]), 0.1, colour_error);
break;
}
}
-
- // --------------------
- // Edges collected
-
- v2f va, vb;
- v2_sub( corner_uvs[1], corner_uvs[0], va );
- v2_sub( corner_uvs[2], corner_uvs[0], vb );
-
- // Connect up the grid
- //
- // 0 1 2 3 4
- // 15 a b c d
- // 14 e f g h
- // 13 i j k l
- // 12 m n o p
- //
- // Example: a := common unused vertex that is connected to
- // by 1 and 15. Or y-1, and x-1 on the grid.
- // g := c and f common vert ^
- //
- int grid[25];
-
- for( int j=0; j<5; j++ ) grid[j] = dispedge[j];
- for( int j=1; j<5; j++ ) grid[j*5+4] = dispedge[j+4];
- for( int j=0; j<4; j++ ) grid[4*5+3-j] = dispedge[j+9];
- for( int j=1; j<4; j++ ) grid[j*5] = dispedge[16-j];
- // Grid fill
- for( int j=1; j<4; j++ )
+ if( !newvert )
{
- for( int k=1; k<4; k++ )
- {
- int s0 = grid[(j-1)*5+k],
- s1 = grid[j*5+k-1];
+ 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];
- struct vertinfo *va = &vertinfo[s0],
- *vb = &vertinfo[s1];
+ /* 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];
- // Find a common vertex between s0 and s1
-
- for( int l=0; l<va->con_count; l ++ )
+ 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 ++ )
{
- for( int m=0; m<vb->con_count; m ++ )
- {
- int cona = graph[va->con_start+l],
- conb = graph[vb->con_start+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;
+ if( cona == conb )
+ {
+ if( vertinfo[cona].used || vertinfo[cona].boundary )
+ continue;
- grid[ j*5+k ] = cona;
- vertinfo[cona].used = 1;
+ grid[ j*5+k ] = cona;
+ vertinfo[cona].used = 1;
- goto IL_MATCHED_DISP_INTERIOR_VERT;
- }
+ goto next_cell;
}
}
+ }
- // Broken displacement
- cxr_log( "Broken displacement!\n" );
- free( graph );
- free( vertinfo );
- return;
+ cxr_log( "Broken displacement!\n" );
+ free( graph );
+ free( vertinfo );
+ return;
- IL_MATCHED_DISP_INTERIOR_VERT:;
- }
+ 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<5; j++ )
- {
- cxr_log( "%d %d %d %d %d\n", grid[j*5+0],grid[j*5+1],grid[j*5+2],grid[j*5+3],grid[j*5+4]);
- }
+ 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;
- // Create brush vertices based on UV map
+ v3_copy( face_center, p0 );
+ v3_muladds( face_center, refn, 1.5, pn );
+ v3_muladds( face_center, refv, 1.5, pv );
+ v3_muladds( face_center, refu, 1.5, pu );
- // Create V reference based on first displacement.
- // TODO: This is not the most stable 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 )
+ /* Draw reference vectors */
+ if( cxr_settings.debug )
{
- struct cxr_texinfo tx;
- v3f tri_ref[3];
- v3_copy( cxr_ab_ptr(abverts,dispedge[0]), tri_ref[0] );
- v3_copy( cxr_ab_ptr(abverts,dispedge[4]), tri_ref[1] );
- v3_copy( cxr_ab_ptr(abverts,dispedge[8]), tri_ref[2] );
- cxr_calculate_axis( &tx, tri_ref, corner_uvs, (v2f){512,512} );
-
- v3_muls( tx.vaxis, -1.0, refv );
- int v_cardinal = cxr_cardinal( refv, n_cardinal );
- v3_copy( avg_normal, refn );
- int u_cardinal = 0;
- if( u_cardinal == n_cardinal || u_cardinal == v_cardinal ) u_cardinal ++;
- if( u_cardinal == n_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 );
-
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} );
+ cxr_debug_line(tri_ref[0],tri_ref[1],(v4f){1.0,1.0,1.0,1.0});
+ cxr_debug_line(tri_ref[1],tri_ref[2],(v4f){1.0,1.0,1.0,1.0});
+ cxr_debug_line(tri_ref[2],tri_ref[0],(v4f){1.0,1.0,1.0,1.0});
}
+ }
- // Create world cordinates
- v3f world_corners[8];
- v2f world_uv[4];
+ /* 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] );
- }
+ 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)];
- cxr_debug_arrow( world_corners[0], world_corners[1], avg_normal, 0.1, colour );
- cxr_debug_arrow( world_corners[1], world_corners[2], avg_normal, 0.1, colour );
- cxr_debug_arrow( world_corners[2], world_corners[3], avg_normal, 0.1, colour );
- cxr_debug_arrow( world_corners[3], world_corners[0], avg_normal, 0.1, colour );
+ 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++ )
- v3_muladds( world_corners[j], refn, -1.0, world_corners[j+4] );
-
- // Apply world transform
- for( int j=0; j<8; j++ )
{
- v3_muls( world_corners[j], cxr_context.scale_factor, world_corners[j] );
- world_corners[j][2] += cxr_context.offset_z;
- }
+ double *p0 = world_corners[j],
+ *p1 = world_corners[cxr_range(j+1,4)];
- if( disp_count == 0 )
- {
- cxr_calculate_axis( &texinfo_shared, world_corners, world_uv,
- (v2f){ matptr->res[0], matptr->res[1] } );
+ 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 );
- // 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;
+ p0[2] += cxr_context.offset_z;
+ }
- for( int j=0; j<5; j++ )
- {
- ty = (double)j/(double)(5-1);
+ 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;
- v3_lerp( world_corners[0], world_corners[3], ty, lside0 );
- v3_lerp( world_corners[1], world_corners[2], ty, lside1 );
+ for( int j=0; j<5; j++ )
+ {
+ ty = (double)j/(double)(5-1);
- for( int k=0; k<5; k++ )
- {
- int index = j*5+k;
+ v3_lerp( world_corners[0], world_corners[3], ty, lside0 );
+ v3_lerp( world_corners[1], world_corners[2], ty, lside1 );
+
+ for( int k=0; k<5; k++ )
+ {
+ int index = j*5+k;
- tx = (double)k/(double)(5-1);
- v3_lerp( lside0, lside1, tx, lref );
- v3_muls( cxr_ab_ptr(abverts, grid[index]), cxr_context.scale_factor, vworld );
- vworld[2] += cxr_context.offset_z;
+ 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] );
- }
+ 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];
- for( int j=0; j<6; 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 )
{
- int *side = sides[j];
+ 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, "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_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_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 );
+ 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 );
- if( j == 0 )
- {
- cxr_vdf_node( output, "dispinfo" );
- cxr_vdf_ki32( output, "power", 2 );
- cxr_vdf_kv3f( output, "startposition", world_corners[0] );
- cxr_vdf_ki32( output, "flags", 0 );
- cxr_vdf_kdouble( output, "elevation", 0.0 );
- cxr_vdf_ki32( output, "subdiv", 0 );
-
- cxr_vdf_node( output, "normals" );
- for( int k=0; k<5; k++ )
- cxr_vdf_karrv3f( output, "row", k, &normals[k*5], 5 );
- cxr_vdf_edon( output );
-
- cxr_vdf_node( output, "distances" );
- for( int k=0; k<5; k++ )
- cxr_vdf_karrdouble( output, "row", k, &distances[k*5], 5 );
- cxr_vdf_edon( output );
-
- // TODO: This might be needed for compiling...
- /*
- cxr_vdf_node( output, "offsets" );
- for( int k=0; k<5; k++ )
- cxr_vdf_printf( output, "\"row%d\" \"0 0 0 0 0 0 0 0 0 0 0 0 0 0 0\"\n", k );
- cxr_vdf_edon( output );
-
- cxr_vdf_node( output, "offset_normals" );
- for( int k=0; k<5; k++ )
- cxr_vdf_printf( output, "\"row%d\" \"0 0 1 0 0 1 0 0 1 0 0 1 0 0 1\"\n", k );
- cxr_vdf_edon( output );
-
- cxr_vdf_node( output, "alphas" );
- for( int k=0; k<5; k++ )
- cxr_vdf_printf( output, "\"row%d\" \"0 0 0 0 0\"\n", k );
- cxr_vdf_edon( output );
-
- cxr_vdf_node( output, "triangle_tags" );
- for( int k=0; k<5-1; k++ )
- cxr_vdf_printf( output, "\"row%d\" \"9 9 9 9 9 9 9 9\"\n", k );
- cxr_vdf_edon( output );
-
- cxr_vdf_node( output, "allowed_verts" );
- cxr_vdf_printf( output, "\"10\" \"-1 -1 -1 -1 -1 -1 -1 -1 -1 -1\"\n" );
- cxr_vdf_edon( output );
- */
- cxr_vdf_edon( output );
- }
+ cxr_vdf_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_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 ++;
}
- }
- }
-
- cxr_log( "Disp count: %d\n", disp_count );
-
- // Main loop
-#if 0
- int pool[25];
- for( int i=0; i<abverts->count; i++ )
- {
- struct vertinfo *info = &vertinfo[i];
- if( info->boundary || info->used )
- continue;
-
- // Gather all vertices in this displacement
- int poolcount = 1,
- front_start = 0,
- front_count = 1;
- pool[0] = i;
- info->used = 1;
-
- IL_GATHER_LOOP:;
-
- int new_front_start = poolcount;
-
- for( int j=0; j<front_count; j++ )
- {
- struct vertinfo *frontvert = &vertinfo[pool[front_start+j]];
-
- for( int k=0; k<frontvert->con_count; k++ )
- {
- int conid = graph[frontvert->con_start+k];
- struct vertinfo *con = &vertinfo[conid];
- if( frontvert->boundary && !con->boundary )
- continue;
+ cxr_vdf_node( output, "editor");
+ cxr_vdf_colour255( output, "color",
+ colours_random[cxr_range(cxr_context.brush_count,8)]);
- if( con->used )
- continue;
-
- if( poolcount == 25 )
- goto IL_DISP_ERROR_COUNT;
+ cxr_vdf_ki32( output, "visgroupshown",1);
+ cxr_vdf_ki32( output, "visgroupautoshown",1);
+ cxr_vdf_edon( output );
- con->used = 1;
- pool[ poolcount ++ ] = conid;
- }
+ cxr_vdf_edon( output );
+ disp_count ++;
}
+ }
- if( poolcount > new_front_start )
- {
- front_start = new_front_start;
- front_count = poolcount-front_start;
+ free( graph );
+ free( vertinfo );
+}
- goto IL_GATHER_LOOP;
- }
-
- if( poolcount != 25 )
- {
-IL_DISP_ERROR_COUNT:
- for( int i=0; i<poolcount; i++ )
- cxr_debug_box( cxr_ab_ptr(abverts,pool[i]), 0.02, colour_error );
+static int cxr_solid_checkerr( cxr_mesh *mesh )
+{
+ v3f *verts = cxr_ab_ptr( mesh->p_abverts, 0 );
+ int err_count = 0;
- free(graph);
- free(vertinfo);
+ for( int i=0; i<mesh->abpolys.count; i++ )
+ {
+ int plane_err = 0;
- cxr_log("Invalid displacement (>25 verts)\n");
- return;
- }
+ cxr_polygon *poly = &mesh->polys[i];
+ v4f plane;
- int corners[4];
- int corner_count = 0;
- struct cxr_loop *cornerloops[4];
+ normal_to_plane( poly->normal, poly->center, plane );
- // Find corners, and get their loops (for uvs)
- // note: the mesh must be split where there is texture seams
- // so that two different uv'd loops cant ref the same vertex
- //
- for( int j=0; j<poolcount; j++ )
+ for( int j=0; j<poly->loop_total; j++ )
{
- if( vertinfo[pool[j]].corner )
+ cxr_loop *loop = &mesh->loops[ poly->loop_start+j ];
+ double *vert = verts[ loop->index ];
+
+ if( fabs(plane_polarity(plane,vert)) > 0.0025 )
{
- if( corner_count == 4 )
- {
- corner_count = -1;
- break;
- }
+ err_count ++;
+ plane_err ++;
- corners[corner_count] = j;
-
- // find loop that includes this vert
- for( int k=0; k<mesh->loops.count; k++ )
- {
- struct cxr_loop *lp = cxr_ab_ptr(&mesh->loops,k);
- if( lp->index == pool[j] )
- {
- cornerloops[corner_count] = lp;
- break;
- }
- }
+ v3f ref;
+ plane_project_point( plane, vert, ref );
- corner_count ++;
+ cxr_debug_line( ref, vert, colour_error );
+ cxr_debug_box( vert, 0.1, colour_error );
}
}
- if( corner_count !=4 )
- {
- free(graph);
- free(vertinfo);
- cxr_log( "Invalid displacement (!=4 corners)\n" );
- return;
- }
-
- int pivot = corners[0];
+ if( plane_err )
+ cxr_debug_poly( mesh, poly, colour_error );
}
-#endif
-
- free( graph );
- free( vertinfo );
+
+ 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_abuffer abverts;
+ cxr_mesh *main_mesh = cxr_to_internal_format(src, &abverts);
u32 error = 0x00;
+ int invalid_count = 0;
struct solidinf
{
- struct cxr_mesh *pmesh;
- int is_displacement;
+ cxr_mesh *pmesh;
+ int is_displacement, invalid;
};
- struct cxr_auto_buffer solids;
+ cxr_abuffer solids;
cxr_ab_init( &solids, sizeof(struct solidinf), 2 );
- // TODO: Preprocessor stages
- // - Split mesh up into islands before doing anything here (DONE)
- // - Snap vertices to grid (0.25u) ?
-
- // Preprocessor 1: Island seperation
- // ---------------
-
+ /*
+ * Preprocessor 1: Island seperation
+ */
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 });
}
cxr_ab_push( &solids, &(struct solidinf){main_mesh,0} );
- // Preprocessor 2: Displacement break-out
- // ---------------
+ /*
+ * 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->polys.count; j++ )
+ for( int j=0; j<pinf->pmesh->abpolys.count; j++ )
{
- struct cxr_polygon *poly = cxr_ab_ptr( &pinf->pmesh->polys, j );
+ cxr_polygon *poly = &pinf->pmesh->polys[ j ];
for( int k=0; k<poly->loop_total; k++ )
{
- struct cxr_loop *lp = cxr_ab_ptr( &pinf->pmesh->loops, poly->loop_start+k );
- struct cxr_edge *edge = cxr_ab_ptr( &pinf->pmesh->edges, lp->edge_index );
+ 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, &abverts );
+ cxr_write_disp( pinf->pmesh, src, output );
}
- // Preprocessor 3: Breakup non-convex shapes into sub-solids
- // ---------------
+ /*
+ * 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 )
+ if( pinf.is_displacement || pinf.invalid )
continue;
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 )
{
{
if( error )
{
- // If no solids error we can rety while preserving 'hot' edges
+ /* Retry if non-critical error, with extra edges */
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;
if( error ) break;
}
+ else
+ break;
}
else
break;
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)] );
+ }
+ }
+
+ 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;
}
- // Turn all those solids into VMF brushes
- // --------------------------------------
+ /* Write all solids as VMF brushes */
for( int i=0; i<solids.count; i++ )
{
struct solidinf *solid = cxr_ab_ptr(&solids,i);
cxr_vdf_node( output, "solid" );
cxr_vdf_ki32( output, "id", ++ cxr_context.brush_count );
- for( int j=0; j<solid->pmesh->polys.count; j++ )
+ for( int j=0; j<solid->pmesh->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 = &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 ];
v3f verts[3]; v2f uvs[3];
- v3_muls( cxr_ab_ptr(&abverts, ploops[0].index), cxr_context.scale_factor, verts[0] );
- v3_muls( cxr_ab_ptr(&abverts, ploops[1].index), cxr_context.scale_factor, verts[1] );
- v3_muls( cxr_ab_ptr(&abverts, ploops[2].index), cxr_context.scale_factor, verts[2] );
+ 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;
cxr_vdf_plane( output, "plane", verts[2], verts[1], verts[0] );
cxr_vdf_kv( output, "material", matptr->vmt_path );
- struct cxr_texinfo trans;
- cxr_calculate_axis(&trans, verts, uvs, (double[2]){ matptr->res[0], matptr->res[1] });
+ cxr_texinfo tx;
+ cxr_calculate_axis( &tx, verts, uvs,
+ (double[2]){ matptr->res[0], matptr->res[1] });
- cxr_vdf_kaxis(output, "uaxis", trans.uaxis, trans.offset[0], trans.scale[0]);
- cxr_vdf_kaxis(output, "vaxis", trans.vaxis, trans.offset[1], trans.scale[1]);
+ cxr_vdf_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_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_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 );
}
cxr_settings = *settings;
}
-// Valve copyright stuff probably maybe
-// whatever, my previous copyright decleration ends here
-// ----------------------------------------------------------
-
+/*
+ * Valve Source SDK 2015 CS:GO
+ */
#define HEADER_LUMPS 64
#define LUMP_WORLDLIGHTS 54
};
#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
-//
+/*
+ * 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 );
return 0;
}
- // Read bsp
+ /* Read bsp */
struct header header;
fread( &header, sizeof(struct header), 1, fp );
struct lump *lump = &header.lumps[ LUMP_WORLDLIGHTS ];
- // Read worldlight array
+ /* 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
+ /* Remove all marked lights */
int light_count = lump->filelen / sizeof(struct worldlight);
int new_count = 0;
lump->filelen = new_count*sizeof(struct worldlight);
- // Write changes
+ /* Write changes back to file */
fseek( fp, lump->fileofs, SEEK_SET );
fwrite( lights, lump->filelen, 1, fp );
fseek( fp, 0, SEEK_SET );
projects / convexer.git / blobdiff