4 A GNU/Linux-first Source1 Hammer replacement
5 built with Blender, for mapmakers
7 Copyright (C) 2022 Harry Godden (hgn)
10 - Brush decomposition into convex pieces for well defined geometry
11 - Freely form displacements without limits
12 - Build your entire map in Blender
13 - Compile models and model groups easily
14 - Light patch BSP files; remove unwanted realtime effects
15 - Fastest VTF compressor (thanks to Richgel999 and stb)
18 - high quality level overviews automatically for CS:GO (csRadar)
22 File/folder Lang Purpose
24 __init__.py Python Blender plugin interface
25 convexer.c C Heavy lifting; brush decomp, mesh processing
26 cxr_math.h C Vector maths and other handy things
27 cxr_mem.h C Automatic resizing buffers
29 nbvtf.h C VTF processing interface
30 librgcx.h C++ Rich Geldreich's DXT1/DXT5 compressors
31 stb/ C Sean Barrets image I/O
41 const char *cxr_build_time
= __DATE__
" @" __TIME__
;
52 typedef unsigned int uint
;
54 typedef double v2f
[2];
55 typedef double v3f
[3];
56 typedef double v4f
[4];
61 #define CXR_EPSILON 0.001
62 #define CXR_INTERIOR_ANGLE_MAX 0.998
64 #define CXR_DIRTY_OPTIMISATION 1
65 #define CXR_DEBUG_WRITE_MESH 1
66 #define CXR_DEBUG_ALLOCATORS 1
67 #define CXR_MANIFOLD_DEBUG 0
69 #define CXR_ERROR_DEGEN_IMPLICIT 0x1
70 #define CXR_ERROR_BAD_MANIFOLD 0x2
71 #define CXR_ERROR_NO_SOLIDS 0x4
77 // ============================================
79 static v4f colours_random
[] =
81 { 0.863, 0.078, 0.235, 0.4 },
82 { 0.000, 0.980, 0.604, 0.4 },
83 { 0.118, 0.565, 1.000, 0.4 },
84 { 0.855, 0.439, 0.839, 0.4 },
85 { 0.824, 0.412, 0.118, 0.4 },
86 { 0.125, 0.698, 0.667, 0.4 },
87 { 0.541, 0.169, 0.886, 0.4 },
88 { 1.000, 0.843, 0.000, 0.4 }
91 static int cxr_range(int x
, int bound
)
94 x
+= bound
* (x
/bound
+ 1);
109 struct cxr_input_loop
119 i32 loop_start
, loop_total
;
122 i32 material_id
; // -1: interior material
129 const char *vmt_path
;
156 struct cxr_auto_buffer
168 // simple VDF writing interface
175 static struct cxr_settings
184 .lightmap_scale
= 12,
186 .light_scale
= 1.0/5.0
189 static struct cxr_context
202 .scale_factor
= 32.0,
206 static struct cxr_material cxr_nodraw
= {
208 .vmt_path
= "tools/toolsnodraw"
211 // Debugging callbacks
212 // =============================================================================
214 static v4f colour_error
= { 1.0f
, 0.0f
, 0.0f
, 1.0f
};
215 static v4f colour_face_graph
= { 1.0f
, 1.0f
, 1.0f
, 0.03f
};
216 static v4f colour_success
= { 0.0f
, 1.0f
, 0.0f
, 1.0f
};
218 static void (*cxr_log_func
)(const char *str
);
219 static void (*cxr_line_func
)( v3f p0
, v3f p1
, v4f colour
);
221 static void cxr_log( const char *fmt
, ... )
226 va_start( args
, fmt
);
227 vsnprintf( buf
, sizeof(buf
)-1, fmt
, args
);
236 static void cxr_debug_line( v3f p0
, v3f p1
, v4f colour
)
239 cxr_line_func( p0
, p1
, colour
);
242 static void cxr_debug_box( v3f p0
, double sz
, v4f colour
)
246 v3_add(p0
, (v3f
){-sz
,-sz
,-sz
}, a
);
247 v3_add(p0
, (v3f
){-sz
, sz
,-sz
}, b
);
248 v3_add(p0
, (v3f
){ sz
, sz
,-sz
}, c
);
249 v3_add(p0
, (v3f
){ sz
,-sz
,-sz
}, d
);
250 v3_add(p0
, (v3f
){-sz
,-sz
,sz
}, a1
);
251 v3_add(p0
, (v3f
){-sz
, sz
,sz
}, b1
);
252 v3_add(p0
, (v3f
){ sz
, sz
,sz
}, c1
);
253 v3_add(p0
, (v3f
){ sz
,-sz
,sz
}, d1
);
255 cxr_debug_line( a
,b
, colour
);
256 cxr_debug_line( b
,c
, colour
);
257 cxr_debug_line( c
,d
, colour
);
258 cxr_debug_line( d
,a
, colour
);
259 cxr_debug_line( a1
,b1
, colour
);
260 cxr_debug_line( b1
,c1
, colour
);
261 cxr_debug_line( c1
,d1
, colour
);
262 cxr_debug_line( d1
,a1
, colour
);
263 cxr_debug_line( a
,a1
, colour
);
264 cxr_debug_line( b
,b1
, colour
);
265 cxr_debug_line( c
,c1
, colour
);
266 cxr_debug_line( d
,d1
, colour
);
269 static void cxr_debug_arrow( v3f p0
, v3f p1
, v3f normal
, double sz
, v4f colour
)
271 v3f dir
, tan
, p2
, p3
;
275 v3_cross(dir
,normal
,tan
);
276 v3_muladds( p1
,dir
, -sz
, p2
);
277 v3_muladds( p2
,tan
,sz
,p3
);
278 cxr_debug_line( p1
, p3
, colour
);
279 v3_muladds( p2
,tan
,-sz
,p3
);
280 cxr_debug_line( p1
, p3
, colour
);
281 cxr_debug_line( p0
, p1
, colour
);
285 // =========================================================================
287 CXR_API
void cxr_context_reset(void)
289 cxr_context
.brush_count
= 0;
290 cxr_context
.entity_count
= 0;
291 cxr_context
.face_count
= 0;
292 cxr_context
.offset_z
= 0.0;
293 cxr_context
.scale_factor
= 32.0;
296 CXR_API
void cxr_set_offset(double offset
)
298 cxr_context
.offset_z
= offset
;
301 CXR_API
void cxr_set_scale_factor(double scale
)
303 cxr_context
.scale_factor
= scale
;
306 CXR_API
struct cxr_vdf
*cxr_vdf_open(const char *path
)
308 struct cxr_vdf
*vdf
= malloc(sizeof(struct cxr_vdf
));
311 vdf
->fp
= fopen( path
, "w" );
322 CXR_API
void cxr_vdf_close(struct cxr_vdf
*vdf
)
327 CXR_API
void cxr_vdf_put(struct cxr_vdf
*vdf
, const char *str
)
329 for( int i
=0; i
<vdf
->level
; i
++ )
330 fputs( " ", vdf
->fp
);
332 fputs( str
, vdf
->fp
);
335 static void cxr_vdf_printf( struct cxr_vdf
*vdf
, const char *fmt
, ... )
340 va_start( args
, fmt
);
341 vfprintf( vdf
->fp
, fmt
, args
);
345 CXR_API
void cxr_vdf_node(struct cxr_vdf
*vdf
, const char *str
)
347 cxr_vdf_put( vdf
, str
);
348 putc( (u8
)'\n', vdf
->fp
);
349 cxr_vdf_put( vdf
, "{\n" );
354 CXR_API
void cxr_vdf_edon(struct cxr_vdf
*vdf
)
357 cxr_vdf_put( vdf
, "}\n" );
360 CXR_API
void cxr_vdf_kv(struct cxr_vdf
*vdf
, const char *strk
, const char *strv
)
362 cxr_vdf_printf( vdf
, "\"%s\" \"%s\"\n", strk
, strv
);
365 static void cxr_vdf_ki32(struct cxr_vdf
*vdf
, const char *strk
, i32 val
)
367 cxr_vdf_printf( vdf
, "\"%s\" \"%d\"\n", strk
, val
);
369 static void cxr_vdf_kdouble(struct cxr_vdf
*vdf
, const char *strk
, double val
)
371 cxr_vdf_printf( vdf
, "\"%s\" \"%f\"\n", strk
, val
);
373 static void cxr_vdf_kaxis(struct cxr_vdf
*vdf
, const char *strk
, v3f normal
, double offset
, double scale
)
375 cxr_vdf_printf( vdf
, "\"%s\" \"[%f %f %f %f] %f\"\n", strk
, normal
[0],normal
[1],normal
[2],offset
,scale
);
377 static void cxr_vdf_plane(struct cxr_vdf
*vdf
, const char *strk
, v3f a
, v3f b
, v3f c
)
379 cxr_vdf_printf( vdf
, "\"%s\" \"(%f %f %f) (%f %f %f) (%f %f %f)\"\n",
380 strk
, a
[0], a
[1], a
[2], b
[0], b
[1], b
[2], c
[0], c
[1], c
[2] );
382 static void cxr_vdf_colour255(struct cxr_vdf
*vdf
, const char *strk
, v4f colour
)
385 v4_muls( colour
, 255.0, scale
);
386 cxr_vdf_printf( vdf
, "\"%s\" \"%d %d %d %d\"\n",strk
,(int)scale
[0], (int)scale
[1], (int)scale
[2], (int)scale
[3]);
390 // =========================================================================
392 static void cxr_debug_poly(struct cxr_mesh
*mesh
, struct cxr_polygon
*poly
, v3f
*verts
, v4f colour
)
394 for( int i
=0; i
<poly
->loop_total
; i
++ )
396 struct cxr_loop
*loop0
= cxr_ab_ptr(&mesh
->loops
,poly
->loop_start
+i
),
397 *loop1
= cxr_ab_ptr(&mesh
->loops
,poly
->loop_start
+cxr_range(i
+1,poly
->loop_total
));
401 v3_lerp( verts
[loop0
->index
], poly
->center
, 0.02, p0
);
402 v3_lerp( verts
[loop1
->index
], poly
->center
, 0.02, p1
);
404 cxr_debug_arrow( p0
, p1
, poly
->normal
, 0.05, colour
);
408 v3_muladds( poly
->center
, poly
->normal
, 0.3, nrm0
);
410 cxr_debug_line( poly
->center
, nrm0
, colour
);
413 static void cxr_debug_mesh(struct cxr_mesh
*mesh
, v3f
*verts
, v4f colour
)
415 for( int i
=0; i
<mesh
->polys
.count
; i
++ )
417 struct cxr_polygon
*poly
= cxr_ab_ptr(&mesh
->polys
,i
);
418 cxr_debug_poly( mesh
, poly
, verts
, colour
);
422 static struct cxr_mesh
*cxr_alloc_mesh(int edge_count
, int loop_count
, int poly_count
)
424 struct cxr_mesh
*mesh
= malloc(sizeof(struct cxr_mesh
));
425 cxr_ab_init(&mesh
->edges
, sizeof(struct cxr_edge
), edge_count
);
426 cxr_ab_init(&mesh
->loops
, sizeof(struct cxr_loop
), loop_count
);
427 cxr_ab_init(&mesh
->polys
, sizeof(struct cxr_polygon
), poly_count
);
431 static void cxr_free_mesh(struct cxr_mesh
*mesh
)
433 cxr_ab_free(&mesh
->edges
);
434 cxr_ab_free(&mesh
->loops
);
435 cxr_ab_free(&mesh
->polys
);
439 // Rebuilds edge data and reallocates
441 static void cxr_mesh_clean_edges(struct cxr_mesh
*mesh
)
443 struct cxr_auto_buffer new_edges
;
444 cxr_ab_init( &new_edges
, sizeof(struct cxr_edge
), mesh
->edges
.count
);
446 for( int i
=0; i
<mesh
->polys
.count
; i
++ )
448 struct cxr_polygon
*poly
= cxr_ab_ptr(&mesh
->polys
,i
);
449 for( int j
=0; j
<poly
->loop_total
; j
++ )
452 *lp0
= cxr_ab_ptr(&mesh
->loops
,poly
->loop_start
+j
),
453 *lp1
= cxr_ab_ptr(&mesh
->loops
,poly
->loop_start
+cxr_range(j
+1,poly
->loop_total
));
455 int i0
= cxr_min(lp0
->index
, lp1
->index
),
456 i1
= cxr_max(lp0
->index
, lp1
->index
);
458 // See if edge exists before adding it
459 for( int k
=0; k
<new_edges
.count
; k
++ )
461 struct cxr_edge
*edge
= cxr_ab_ptr(&new_edges
,k
);
463 if( edge
->i0
== i0
&& edge
->i1
== i1
)
466 goto IL_EDGE_CREATED
;
470 int orig_edge_id
= lp0
->edge_index
;
471 lp0
->edge_index
= new_edges
.count
;
473 struct cxr_edge edge
= { i0
, i1
};
475 // Copy extra information (sharp,freestyle.. etc) here!
477 // if orig_edge_id < mesh->edges.count: edge.foo = mesh->edges[orig].foo
479 cxr_ab_push( &new_edges
, &edge
);
485 cxr_ab_free( &mesh
->edges
);
486 mesh
->edges
= new_edges
;
489 // Remove 0-length faces from mesh and correct loops
491 static void cxr_mesh_clean_faces(struct cxr_mesh
*mesh
)
493 struct cxr_auto_buffer loops_new
;
494 cxr_ab_init( &loops_new
, sizeof(struct cxr_loop
), mesh
->loops
.count
);
497 for( int i
=0; i
<mesh
->polys
.count
; i
++ )
499 struct cxr_polygon
*src
= cxr_ab_ptr(&mesh
->polys
,i
),
500 *dst
= cxr_ab_ptr(&mesh
->polys
,new_length
);
502 if( src
->loop_total
> 0 )
504 int src_start
= src
->loop_start
,
505 src_total
= src
->loop_total
;
508 dst
->loop_start
= loops_new
.count
;
510 for( int j
=0; j
<src_total
; j
++ )
512 struct cxr_loop
*loop
= cxr_ab_ptr(&mesh
->loops
,src_start
+j
),
513 *ldst
= cxr_ab_ptr(&loops_new
,dst
->loop_start
+j
);
515 ldst
->poly_left
= new_length
;
518 loops_new
.count
+= src_total
;
523 cxr_ab_free( &mesh
->loops
);
524 mesh
->loops
= loops_new
;
525 mesh
->polys
.count
= new_length
;
528 static i32
*cxr_mesh_link_loops(struct cxr_mesh
*mesh
)
530 i32
*polygon_edge_map
= malloc(mesh
->edges
.count
*2 *sizeof(i32
));
532 for( int i
= 0; i
< mesh
->edges
.count
*2; i
++ )
533 polygon_edge_map
[i
] = -1;
535 for( int i
= 0; i
< mesh
->polys
.count
; i
++ )
537 struct cxr_polygon
*poly
= cxr_ab_ptr(&mesh
->polys
, i
);
539 for( int j
= 0; j
< poly
->loop_total
; j
++ )
541 struct cxr_loop
*loop
= cxr_ab_ptr(&mesh
->loops
, poly
->loop_start
+j
);
544 for( int k
= 0; k
< 2; k
++ )
546 i32
*edge
= &polygon_edge_map
[loop
->edge_index
*2+k
];
556 for( int i
= 0; i
< mesh
->polys
.count
; i
++ )
558 struct cxr_polygon
*poly
= cxr_ab_ptr(&mesh
->polys
,i
);
560 for( int j
= 0; j
< poly
->loop_total
; j
++ )
562 struct cxr_loop
*loop
= cxr_ab_ptr(&mesh
->loops
,poly
->loop_start
+j
);
564 i32
*face_map
= &polygon_edge_map
[loop
->edge_index
*2];
566 if( face_map
[0] == loop
->poly_left
) loop
->poly_right
= face_map
[1];
567 else loop
->poly_right
= face_map
[0];
571 return polygon_edge_map
;
574 // Add polygon to mesh based on loop array
575 static struct cxr_polygon
*cxr_create_poly( struct cxr_mesh
*mesh
, v3f
*vertices
, struct cxr_loop poly
[],
576 int len
, int start
, int max
)
580 cxr_log( "tried to add new poly with length %d!\n", len
);
584 for( int j
=0; j
<len
; j
++ )
586 int i0
= poly
[j
].index
,
587 i1
= poly
[cxr_range(j
+1,len
)].index
;
588 cxr_debug_line( vertices
[i0
], vertices
[i1
], colour_error
);
595 int nface_id
= mesh
->polys
.count
;
596 struct cxr_polygon
*new_face
= cxr_ab_empty(&mesh
->polys
);
598 new_face
->loop_start
= mesh
->loops
.count
;
599 new_face
->loop_total
= len
;
600 new_face
->material_id
= -1;
602 // Calculate normal and center
603 v3_zero( new_face
->center
);
605 for( int j
=0; j
<len
; j
++ )
607 int i0
= poly
[cxr_range(start
+j
,max
)].index
;
608 struct cxr_loop
*new_loop
= cxr_ab_empty(&mesh
->loops
);
610 new_loop
->poly_left
= nface_id
;
611 new_loop
->poly_right
= -1;
612 new_loop
->index
= i0
;
613 new_loop
->edge_index
= 0;
614 v2_zero(new_loop
->uv
);
616 v3_add( new_face
->center
, vertices
[new_loop
->index
], new_face
->center
);
618 v3_divs( new_face
->center
, new_face
->loop_total
, new_face
->center
);
620 struct cxr_loop
*lp0
= cxr_ab_ptr( &mesh
->loops
, new_face
->loop_start
),
621 *lp1
= cxr_ab_ptr( &mesh
->loops
, new_face
->loop_start
+1 ),
622 *lp2
= cxr_ab_ptr( &mesh
->loops
, new_face
->loop_start
+2 );
624 tri_normal( vertices
[lp0
->index
], vertices
[lp1
->index
], vertices
[lp2
->index
], new_face
->normal
);
626 return cxr_ab_ptr(&mesh
->polys
, nface_id
);
629 // Get the 'next' mesh island
631 // Returns NULL if there is only one island
632 static struct cxr_mesh
*cxr_pull_island(struct cxr_mesh
*mesh
)
634 free(cxr_mesh_link_loops(mesh
));
636 int *island_current
= malloc(mesh
->polys
.count
*sizeof(int)),
641 island_current
[0] = 0;
644 last_count
= island_len
;
646 for( int i
=0; i
<island_len
; i
++ )
648 struct cxr_polygon
*poly
= cxr_ab_ptr(&mesh
->polys
,island_current
[i
]);
650 for( int j
=0; j
<poly
->loop_total
; j
++ )
652 struct cxr_loop
*loop
= cxr_ab_ptr(&mesh
->loops
, poly
->loop_start
+j
);
654 if( loop
->poly_right
!= -1 )
656 int face_present
= 0;
658 for( int k
=0; k
<island_len
; k
++ )
660 if( island_current
[k
] == loop
->poly_right
)
669 island_current
[ island_len
++ ] = loop
->poly_right
;
675 if( island_len
> last_count
)
676 goto IL_ISLAND_REPEAT
;
678 if( island_len
== mesh
->polys
.count
)
680 free( island_current
);
684 for( int i
=0; i
<island_len
; i
++ )
686 struct cxr_polygon
*poly
= cxr_ab_ptr(&mesh
->polys
, island_current
[i
]);
687 loop_count
+= poly
->loop_total
;
690 struct cxr_mesh
*newmesh
= cxr_alloc_mesh( mesh
->edges
.count
, loop_count
, island_len
);
692 for( int i
=0; i
<island_len
; i
++ )
694 struct cxr_polygon
*src
= cxr_ab_ptr(&mesh
->polys
, island_current
[i
]);
695 struct cxr_polygon
*dst
= cxr_ab_ptr(&newmesh
->polys
, i
);
698 dst
->loop_start
= newmesh
->loops
.count
;
700 for( int j
=0; j
<src
->loop_total
; j
++ )
702 struct cxr_loop
*lsrc
= cxr_ab_ptr(&mesh
->loops
, src
->loop_start
+j
),
703 *ldst
= cxr_ab_ptr(&newmesh
->loops
, dst
->loop_start
+j
);
707 ldst
->poly_right
= -1;
710 newmesh
->loops
.count
+= src
->loop_total
;
711 src
->loop_total
= -1;
714 newmesh
->polys
.count
= island_len
;
715 newmesh
->edges
.count
= mesh
->edges
.count
;
716 memcpy(cxr_ab_ptr(&newmesh
->edges
,0), cxr_ab_ptr(&mesh
->edges
,0), mesh
->edges
.count
*sizeof(struct cxr_edge
));
718 cxr_mesh_clean_faces(mesh
);
719 cxr_mesh_clean_edges(mesh
);
720 cxr_mesh_clean_edges(newmesh
);
721 free( island_current
);
726 // Return best availible solid from mesh, and patch existing mesh to fill the gap
729 // Returns NULL if shape is already convex or empty
730 // Destroys edge data!
731 static struct cxr_mesh
*cxr_pull_best_solid(
732 struct cxr_mesh
*mesh
,
733 struct cxr_auto_buffer
*vert_buffer
,
734 int preserve_hot_edges
,
737 v3f
*vertices
= cxr_ab_ptr( vert_buffer
, 0 );
739 i32
*polygon_edge_map
= cxr_mesh_link_loops(mesh
);
741 for( int i
=0; i
<mesh
->edges
.count
*2; i
++ )
742 if( polygon_edge_map
[i
] == -1 )
744 cxr_log( "non-manifold edges are in the mesh; implicit internal geometry does not have full support\n" );
745 free(polygon_edge_map
);
749 int *vertex_tagged
= malloc( vert_buffer
->count
*sizeof(int) );
750 int *edge_tagged
= malloc( mesh
->edges
.count
*sizeof(int) );
752 for( int i
=0; i
<mesh
->edges
.count
; i
++ )
754 struct cxr_polygon
*polya
= cxr_ab_ptr(&mesh
->polys
, polygon_edge_map
[i
*2+0]),
755 *polyb
= cxr_ab_ptr(&mesh
->polys
, polygon_edge_map
[i
*2+1]);
757 normal_to_plane(polyb
->normal
, polyb
->center
, planeb
);
760 for( int j
=0; j
<polya
->loop_total
; j
++ )
762 struct cxr_loop
*loop
= cxr_ab_ptr(&mesh
->loops
, polya
->loop_start
+j
);
763 if( plane_polarity( planeb
, vertices
[loop
->index
] ) > 0.001 ||
764 v3_dot(polya
->normal
,polyb
->normal
) > 0.98500 )
772 // Tag 'reflex' vertices
773 int *connected_planes
= malloc(mesh
->polys
.count
*sizeof(int));
775 for( int i
=0; i
<vert_buffer
->count
; i
++ )
779 int num_connected
= 0;
780 // Create a list of polys that ref this vert
781 for( int j
=0; j
<mesh
->polys
.count
; j
++ )
783 struct cxr_polygon
*poly
= cxr_ab_ptr(&mesh
->polys
,j
);
784 for( int k
=0; k
<poly
->loop_total
; k
++ )
786 struct cxr_loop
*loop
= cxr_ab_ptr(&mesh
->loops
,poly
->loop_start
+k
);
787 if( loop
->index
== i
)
789 connected_planes
[num_connected
++] = j
;
794 // Check all combinations for a similar normal
795 for( int j
=0; j
<num_connected
-1; j
++ )
797 for( int k
=j
+1; k
<num_connected
; k
++ )
799 struct cxr_polygon
*polyj
= cxr_ab_ptr(&mesh
->polys
,connected_planes
[j
]);
800 struct cxr_polygon
*polyk
= cxr_ab_ptr(&mesh
->polys
,connected_planes
[k
]);
802 if( v3_dot(polyj
->normal
, polyk
->normal
) > 0.98500 )
807 // Check if all connected planes not are:
808 // - bounded by other planes
811 for( int j
=0; j
<num_connected
; j
++ )
812 for( int k
=j
+1; k
<num_connected
; k
++ )
814 struct cxr_polygon
*jpoly
= cxr_ab_ptr(&mesh
->polys
, connected_planes
[j
]),
815 *kpoly
= cxr_ab_ptr(&mesh
->polys
, connected_planes
[k
]);
817 normal_to_plane( kpoly
->normal
, kpoly
->center
, plane
);
818 for( int l
=0; l
<jpoly
->loop_total
; l
++ )
820 struct cxr_loop
*loop
= cxr_ab_ptr(&mesh
->loops
, jpoly
->loop_start
+l
);
821 if( plane_polarity( plane
, vertices
[loop
->index
] ) > 0.001 )
826 goto IL_TAG_NEXT_VERT
;
827 IL_TAG_VERT
: vertex_tagged
[i
] = 1;
831 free( connected_planes
);
833 // Connect all marked verts that share an edge
834 // - We must take care not to completely isolate
835 // a polygon with marked edges all around it
837 int *hot_edge
= malloc(mesh
->edges
.count
*sizeof(int));
838 for( int i
=0; i
< mesh
->edges
.count
; i
++ )
841 for( int i
=0; i
<mesh
->polys
.count
; i
++ )
843 struct cxr_polygon
*poly
= cxr_ab_ptr(&mesh
->polys
,i
);
847 for( int j
=0; j
<poly
->loop_total
; j
++ )
849 struct cxr_loop
*loop
= cxr_ab_ptr(&mesh
->loops
, poly
->loop_start
+j
);
851 if( !edge_tagged
[ loop
->edge_index
] )
853 if( not_tagged
== -1 )
854 not_tagged
= loop
->edge_index
;
856 goto IL_SKIP_NO_HOT_EDGE
;
860 if( not_tagged
!= -1 )
861 hot_edge
[not_tagged
]=1;
863 IL_SKIP_NO_HOT_EDGE
:;
866 // Connect edges that have verts tagged, but is not a hot edge
867 for( int i
=0; i
<mesh
->edges
.count
; i
++ )
869 if( hot_edge
[i
] && preserve_hot_edges
) continue;
871 struct cxr_edge
*edge
= cxr_ab_ptr(&mesh
->edges
,i
);
872 if( vertex_tagged
[edge
->i0
] && vertex_tagged
[edge
->i1
] )
877 for( int i=0; i<vertex_count; i++ )
878 if( vertex_tagged[i] )
879 cxr_debug_box( vertices[i], 0.03, (v4f){0.0,0.0,0.0,1.0});
881 for( int i=0; i < mesh->edges.count; i++ )
883 struct cxr_edge *edge = cxr_ab_ptr( &mesh->edges, i );
885 cxr_debug_line( vertices[ edge->i0 ], vertices[ edge->i1 ], (v4f){0.0,0.0,0.0,1.0});
888 cxr_debug_line( vertices[ edge->i0 ], vertices[ edge->i1 ], (v4f){0.0,1.0,1.0,1.0});
893 int *faces_tagged
= malloc(mesh
->polys
.count
*sizeof(int));
894 for( int i
=0; i
<mesh
->polys
.count
; i
++ )
895 faces_tagged
[i
] = -1;
897 int *solid_buffer
= malloc( mesh
->polys
.count
*sizeof(int) );
898 int solid_buffer_len
= 0;
901 int start
,count
,edge_count
;
904 *candidates
= malloc( mesh
->polys
.count
*sizeof(struct csolid
) );
905 int candidate_count
= 0;
907 for( int i
=0; i
<mesh
->polys
.count
; i
++ )
909 if( faces_tagged
[i
] != -1 ) continue;
912 int *solid
= &solid_buffer
[ solid_buffer_len
];
915 solid
[solid_len
++] = i
;
917 int search_start
= 0;
919 // Iterative search that connects regions of planes governed by rules:
920 // - edge can add other face if the edge has less than two reflexes
921 // - the face can no longer be used in future searches
926 for( int j
=search_start
; j
<solid_len
; j
++ )
928 struct cxr_polygon
*poly
= cxr_ab_ptr(&mesh
->polys
, solid
[j
]);
930 for( int k
=0; k
<poly
->loop_total
; k
++ )
932 struct cxr_loop
*loop
= cxr_ab_ptr(&mesh
->loops
, poly
->loop_start
+k
);
933 struct cxr_edge
*edge
= cxr_ab_ptr(&mesh
->edges
, loop
->edge_index
);
935 if( faces_tagged
[ loop
->poly_right
] == -1 )
937 if( !edge_tagged
[loop
->edge_index
] )
939 // Need to look ahead 1 step to make sure he does not want
940 // to add any more planes that are coplanar with some of
941 // our existing group
943 // TODO: is this unused due to hotedge improvements? leaving for safety...
945 struct cxr_polygon
*poly_to_add
= cxr_ab_ptr(&mesh
->polys
, loop
->poly_right
);
946 for( int l
=0; l
< poly_to_add
->loop_total
; l
++ )
948 struct cxr_loop
*loop1
= cxr_ab_ptr(&mesh
->loops
, poly_to_add
->loop_start
+l
);
949 struct cxr_polygon
*future_face
= cxr_ab_ptr(&mesh
->polys
, loop1
->poly_right
);
951 if( edge_tagged
[ loop1
->edge_index
] || loop1
->poly_right
== loop
->poly_right
)
952 goto IL_SKIP_SIMILAR_PLANES
;
954 for( int m
=0; m
<solid_len
; m
++ )
955 if( solid
[m
] == loop1
->poly_right
)
956 goto IL_SKIP_SIMILAR_PLANES
;
958 for( int m
=0; m
<solid_len
; m
++ )
960 struct cxr_polygon
*polym
= cxr_ab_ptr(&mesh
->polys
,solid
[m
]);
961 if( v3_dot( polym
->normal
, future_face
->normal
) > 0.98500 )
962 goto IL_SKIP_PLANE_ADD
;
965 IL_SKIP_SIMILAR_PLANES
:;
968 // This plane passed all checks so we can add it to the current solid
970 solid
[ solid_len
++ ] = loop
->poly_right
;
971 faces_tagged
[ loop
->poly_right
] = i
;
979 search_start
= solid_len
;
981 goto IL_SEARCH_CONTINUE
;
984 struct csolid
*csolid
= &candidates
[candidate_count
++];
985 csolid
->start
= solid_buffer_len
;
986 csolid
->count
= solid_len
;
987 csolid
->edge_count
= 0;
989 v3_zero( csolid
->center
);
990 for( int j
=0; j
<solid_len
; j
++ )
992 struct cxr_polygon
*polyj
= cxr_ab_ptr(&mesh
->polys
, solid
[j
]);
993 v3_add( polyj
->center
, csolid
->center
, csolid
->center
);
994 csolid
->edge_count
+= polyj
->loop_total
;
996 v3_divs( csolid
->center
, solid_len
, csolid
->center
);
998 solid_buffer_len
+= solid_len
;
1001 // Create all candidates who have one or less non-manifolds edges
1002 // Loop each candidate, determine the manifold, and pick the best one
1004 struct csolid
*best_solid
= NULL
;
1005 int fewest_manifold_splits
= INT32_MAX
;
1007 struct cxr_loop
*best_manifold
= malloc( mesh
->loops
.count
*sizeof(struct cxr_loop
) );
1008 int *best_manifold_splits
= malloc( mesh
->loops
.count
*sizeof(int) );
1009 int best_manifold_len
= 0;
1010 int max_solid_faces
= 0;
1012 int *edge_list
= malloc( mesh
->edges
.count
*sizeof(int) );
1013 int *edge_lefts
= malloc( mesh
->edges
.count
*sizeof(int) );
1014 struct cxr_loop
*manifold
= malloc(mesh
->edges
.count
*2*sizeof(struct cxr_loop
));
1015 int *splits
= malloc(mesh
->edges
.count
*2*sizeof(int));
1017 for( int i
=0; i
<candidate_count
; i
++ )
1019 struct csolid
*solid
= &candidates
[i
];
1020 max_solid_faces
= cxr_max(max_solid_faces
,solid
->count
);
1022 if( solid
->count
<= 2 )
1025 int init_reverse
= 0;
1026 int unique_edge_count
= 0;
1028 for( int j
=0; j
<solid
->count
; j
++ )
1030 struct cxr_polygon
*poly
= cxr_ab_ptr(&mesh
->polys
, solid_buffer
[solid
->start
+j
]);
1032 for( int k
=0; k
<poly
->loop_total
; k
++ )
1034 struct cxr_loop
*loop
= cxr_ab_ptr(&mesh
->loops
, poly
->loop_start
+k
);
1036 for( int l
=0; l
<unique_edge_count
; l
++ )
1037 if( edge_list
[l
] == loop
->edge_index
)
1038 goto IL_EDGE_ALREADY_PRESENT
;
1040 // Check if right edge references a polygon that is not
1041 // present inside the current solid candidate
1042 for( int l
=0; l
<solid
->count
; l
++ )
1043 if( loop
->poly_right
== solid_buffer
[solid
->start
+l
] )
1044 goto IL_EDGE_ALREADY_PRESENT
;
1046 edge_list
[ unique_edge_count
] = loop
->edge_index
;
1047 edge_lefts
[ unique_edge_count
] = loop
->poly_left
;
1049 if( unique_edge_count
== 0 )
1051 struct cxr_edge
*edgeptr
= cxr_ab_ptr(&mesh
->edges
, loop
->edge_index
);
1052 if( edgeptr
->i1
== loop
->index
)
1056 unique_edge_count
++;
1057 IL_EDGE_ALREADY_PRESENT
:;
1061 // This solid is already fully connected
1062 if( unique_edge_count
== 0 )
1065 // Link edges together to create new manifold
1066 // Corners are created when two edges share a polygon face
1067 // This way we can split it into regions
1069 for( int j
=0; j
<vert_buffer
->count
; j
++ )
1070 vertex_tagged
[j
] = -1;
1072 // Start with a loop edge which was tagged
1073 struct cxr_edge
*current
= cxr_ab_ptr(&mesh
->edges
, edge_list
[0]);
1075 int endpt
= (!init_reverse
)? current
->i0
: current
->i1
,
1077 curface
= edge_lefts
[0];
1079 int manifold_len
= 0;
1080 int split_count
= 0;
1082 IL_MANIFOLD_CONTINUE
:
1083 for( int j
=0; j
<unique_edge_count
; j
++ )
1085 struct cxr_edge
*other
= cxr_ab_ptr(&mesh
->edges
, edge_list
[j
]);
1086 if( other
== current
)
1089 if( other
->i0
== endpt
|| other
->i1
== endpt
)
1094 if( other
->i0
== endpt
) endpt
= current
->i1
;
1095 else endpt
= current
->i0
;
1097 if( curface
==edge_lefts
[j
] )
1099 splits
[ manifold_len
] = 1;
1103 splits
[ manifold_len
] = 0;
1105 // Append to intermidiary manifold
1106 manifold
[ manifold_len
].edge_index
= edge_list
[j
];
1107 manifold
[ manifold_len
].poly_left
= edge_lefts
[j
];
1108 manifold
[ manifold_len
].index
= lastpt
;
1109 manifold
[ manifold_len
].poly_right
=
1110 polygon_edge_map
[ edge_list
[j
]*2 ] == edge_lefts
[j
]?
1111 polygon_edge_map
[ edge_list
[j
]*2+1 ]:
1112 polygon_edge_map
[ edge_list
[j
]*2+0 ];
1115 curface
= edge_lefts
[j
];
1117 if(endpt
== start
) goto IL_MANIFOLD_COMPLETE
;
1118 goto IL_MANIFOLD_CONTINUE
;
1121 cxr_log( "Failed to link manifold, count: %d\n", manifold_len
);
1123 for( int j
=0; j
<solid
->count
; j
++ )
1125 cxr_log( "p%d\n", solid_buffer
[solid
->start
+j
] );
1126 struct cxr_polygon
*poly
= cxr_ab_ptr(&mesh
->polys
, solid_buffer
[solid
->start
+j
]);
1127 cxr_debug_poly( mesh
, poly
, vertices
, (v4f
){0.2,0.0,0.0,1.0} );
1130 for( int j
=0; j
<unique_edge_count
; j
++ )
1132 struct cxr_edge
*uedge
= cxr_ab_ptr(&mesh
->edges
, edge_list
[j
]);
1133 cxr_debug_line(vertices
[uedge
->i0
],vertices
[uedge
->i1
],(v4f
){0.4,0.0,0.0,1.0});
1136 for( int j
=0; j
<manifold_len
-1; j
++ )
1138 struct cxr_loop
*lp0
= &manifold
[j
],
1139 *lp1
= &manifold
[cxr_range(j
+1,manifold_len
)];
1141 cxr_debug_line(vertices
[lp0
->index
],vertices
[lp1
->index
], colour_error
);
1144 cxr_debug_mesh( mesh
, vertices
, (v4f
){0.0,0.0,0.0, 0.9} );
1145 *error
= CXR_ERROR_BAD_MANIFOLD
;
1152 free(vertex_tagged
);
1157 free(best_manifold
);
1158 free(best_manifold_splits
);
1159 free(polygon_edge_map
);
1162 IL_MANIFOLD_COMPLETE
:;
1164 if( manifold_len
< unique_edge_count
)
1168 if( split_count
< fewest_manifold_splits
)
1170 fewest_manifold_splits
= split_count
;
1173 for( int j
=0; j
<manifold_len
; j
++ )
1175 best_manifold
[j
] = manifold
[j
];
1176 best_manifold_splits
[j
] = splits
[j
];
1178 best_manifold_len
= manifold_len
;
1188 if( max_solid_faces
< 2 )
1190 *error
= CXR_ERROR_NO_SOLIDS
;
1192 free(vertex_tagged
);
1197 free(best_manifold
);
1198 free(best_manifold_splits
);
1199 free(polygon_edge_map
);
1203 if( best_solid
!= NULL
)
1205 struct cxr_mesh
*pullmesh
=
1206 cxr_alloc_mesh( best_solid
->edge_count
, best_solid
->edge_count
, best_solid
->count
);
1208 // Add existing faces to pullsolid, and delete from main mesh
1209 for( int i
=0; i
<best_solid
->count
; i
++ )
1211 int nface_id
= pullmesh
->polys
.count
;
1213 struct cxr_polygon
*exist_face
= cxr_ab_ptr(&mesh
->polys
, solid_buffer
[best_solid
->start
+i
]);
1214 struct cxr_polygon
*new_face
= cxr_ab_empty(&pullmesh
->polys
);
1216 *new_face
= *exist_face
;
1217 new_face
->loop_start
= pullmesh
->loops
.count
;
1219 for( int j
=0; j
<exist_face
->loop_total
; j
++ )
1221 struct cxr_loop
*exist_loop
= cxr_ab_ptr(&mesh
->loops
, exist_face
->loop_start
+j
);
1222 struct cxr_loop
*new_loop
= cxr_ab_empty(&pullmesh
->loops
);
1224 new_loop
->index
= exist_loop
->index
;
1225 new_loop
->poly_left
= nface_id
;
1226 new_loop
->poly_right
= -1;
1227 new_loop
->edge_index
= 0;
1228 v2_copy( exist_loop
->uv
, new_loop
->uv
);
1231 exist_face
->loop_total
= -1;
1234 // Split manifold up by unique planes if it has more than 1
1235 // otherwise, just use that face
1237 // TODO: Need to build new manifold in sections, stably
1238 // currently there is an unsupported case where the manifold splits
1239 // are on located on an implicit face, causing 1-length manifolds.
1242 int pullmesh_new_start
= pullmesh
->polys
.count
;
1244 if( fewest_manifold_splits
!= 0 )
1246 #if CXR_MANIFOLD_DEBUG
1247 for( int i
=0; i
<best_manifold_len
; i
++ )
1250 i1
= cxr_range(i
+1,best_manifold_len
);
1252 cxr_debug_line( vertices
[best_manifold
[i0
].index
], vertices
[best_manifold
[i1
].index
], colour_error
);
1253 if( best_manifold_splits
[i
] )
1254 cxr_debug_box( vertices
[best_manifold
[i0
].index
], 0.04, colour_success
);
1258 // This is a really strange observation, however it *seems* to apply to the kinds
1259 // of geometry we are dealing with. If the split count is odd, the manifold can be
1260 // created easily, no folding required.
1262 // When it is even, it appears that internal implicit geometry is required, so we
1263 // need to fold the loops we create. Its really weird, but for some reason works on
1264 // the geometry rules we've defined.
1265 // TODO: Find a well defined rule here.
1267 int collapse_used_segments
= (u32
)fewest_manifold_splits
& 0x1? 0: 1;
1269 IL_MANIFOLD_BUILD_REPEAT
:
1271 for( int j
=0; j
<best_manifold_len
; j
++ )
1273 if( best_manifold_splits
[j
] )
1275 struct cxr_loop
*loop
= &best_manifold
[j
];
1277 for( int k
=1; k
<best_manifold_len
; k
++ )
1279 int index1
= cxr_range(j
+k
,best_manifold_len
);
1280 struct cxr_loop
*loop1
= &best_manifold
[index1
];
1282 if( best_manifold_splits
[index1
] )
1289 if( new_polys
> best_manifold_len
)
1291 cxr_log( "Programming error: Too many new polys!\n" );
1295 cxr_create_poly( pullmesh
, vertices
, best_manifold
, k
+1, j
, best_manifold_len
);
1297 // Remove new section from manifold
1298 if( collapse_used_segments
)
1300 best_manifold_splits
[j
] = 0;
1301 best_manifold_splits
[index1
] = 0;
1303 int new_length
= (best_manifold_len
-(k
-1));
1305 struct cxr_loop
*new_manifold
= malloc( new_length
*sizeof(struct cxr_loop
) );
1306 int *new_manifold_splits
= malloc( new_length
*sizeof(int) );
1308 for( int l
=0; l
<new_length
; l
++ )
1310 int i_src
= cxr_range( j
+k
+l
, best_manifold_len
);
1311 new_manifold
[l
] = best_manifold
[i_src
];
1312 new_manifold_splits
[l
] = best_manifold_splits
[i_src
];
1315 free( best_manifold
);
1316 free( best_manifold_splits
);
1317 best_manifold
= new_manifold
;
1318 best_manifold_splits
= new_manifold_splits
;
1320 best_manifold_len
= new_length
;
1322 goto IL_MANIFOLD_BUILD_REPEAT
;
1332 if( best_manifold_len
&& collapse_used_segments
)
1334 cxr_create_poly( pullmesh
, vertices
, best_manifold
, best_manifold_len
, 0, best_manifold_len
);
1340 cxr_create_poly( pullmesh
, vertices
, best_manifold
, best_manifold_len
, 0, best_manifold_len
);
1344 // vert_buffer may be reallocated by the next section of code,
1345 // force a NULLref on vertices to catch any errors
1348 // Implicit geometry reconstruction
1349 // If there's 3 or more planes, collide them together to see if any new
1350 // vertices need to be created on the mesh
1351 if( new_polys
>= 3 )
1353 for( int i
=0; i
<new_polys
-2; i
++ )
1355 for( int j
=i
+1; j
<new_polys
-1; j
++ )
1357 for( int k
=j
+1; k
<new_polys
; k
++ )
1359 struct cxr_polygon
*ptri
= cxr_ab_ptr( &pullmesh
->polys
, pullmesh_new_start
+i
),
1360 *ptrj
= cxr_ab_ptr( &pullmesh
->polys
, pullmesh_new_start
+j
),
1361 *ptrk
= cxr_ab_ptr( &pullmesh
->polys
, pullmesh_new_start
+k
);
1363 v4f planei
, planej
, planek
;
1364 normal_to_plane(ptri
->normal
,ptri
->center
,planei
);
1365 normal_to_plane(ptrj
->normal
,ptrj
->center
,planej
);
1366 normal_to_plane(ptrk
->normal
,ptrk
->center
,planek
);
1370 if( plane_intersect(planei
,planej
,planek
,intersect
) )
1372 // cxr_debug_box( intersect, 0.05, colour_error );
1374 // Make sure this point is within the convex region, otherwise treat
1375 // it as a degenerate case
1377 int point_valid
= 1;
1378 for( int l
=0; l
<pullmesh
->polys
.count
; l
++ )
1380 struct cxr_polygon
*ptrl
= cxr_ab_ptr(&pullmesh
->polys
,l
);
1383 normal_to_plane(ptrl
->normal
, ptrl
->center
, planel
);
1385 if( plane_polarity( planel
, intersect
) > 0.01 )
1387 cxr_log( "degen vert, planes %d, %d, %d [max:%d]\n", i
,j
,k
, new_polys
);
1388 *error
= CXR_ERROR_DEGEN_IMPLICIT
;
1390 cxr_debug_poly( pullmesh
, ptri
, cxr_ab_ptr(vert_buffer
,0), colours_random
[3] );
1391 cxr_debug_poly( pullmesh
, ptrj
, cxr_ab_ptr(vert_buffer
,0), colours_random
[1] );
1392 cxr_debug_poly( pullmesh
, ptrk
, cxr_ab_ptr(vert_buffer
,0), colours_random
[2] );
1399 if( !point_valid
) continue;
1401 // Extend faces to include this point
1402 int nvertid
= vert_buffer
->count
;
1403 cxr_ab_push( vert_buffer
, intersect
);
1405 ptrj
->loop_start
+= 1;
1406 ptrk
->loop_start
+= 2;
1408 cxr_ab_reserve(&pullmesh
->loops
, 3);
1409 struct cxr_loop
*lloopi
= cxr_ab_empty_at(&pullmesh
->loops
, ptri
->loop_start
+ptri
->loop_total
),
1410 *lloopj
= cxr_ab_empty_at(&pullmesh
->loops
, ptrj
->loop_start
+ptrj
->loop_total
),
1411 *lloopk
= cxr_ab_empty_at(&pullmesh
->loops
, ptrk
->loop_start
+ptrk
->loop_total
);
1413 lloopi
->index
= nvertid
;
1414 lloopj
->index
= nvertid
;
1415 lloopk
->index
= nvertid
;
1416 lloopi
->edge_index
= 0; lloopj
->edge_index
= 0; lloopk
->edge_index
= 0;
1417 lloopi
->poly_left
= pullmesh_new_start
+i
;
1418 lloopj
->poly_left
= pullmesh_new_start
+j
;
1419 lloopk
->poly_left
= pullmesh_new_start
+k
;
1420 lloopi
->poly_right
= -1; lloopj
->poly_right
= -1; lloopk
->poly_right
= -1;
1422 v2_zero(lloopi
->uv
);
1423 v2_zero(lloopj
->uv
);
1424 v2_zero(lloopk
->uv
);
1426 ptri
->loop_total
++;
1427 ptrj
->loop_total
++;
1428 ptrk
->loop_total
++;
1430 // Adjust centers of faces
1431 v3_lerp( ptri
->center
, intersect
, 1.0/(double)ptri
->loop_total
, ptri
->center
);
1432 v3_lerp( ptrj
->center
, intersect
, 1.0/(double)ptrj
->loop_total
, ptrj
->center
);
1433 v3_lerp( ptrk
->center
, intersect
, 1.0/(double)ptrk
->loop_total
, ptrk
->center
);
1440 // Copy faces from pullsolid into orig mesh
1442 for( int i
=0; i
<new_polys
; i
++ )
1444 int rface_id
= mesh
->polys
.count
;
1446 struct cxr_polygon
*pface
= cxr_ab_ptr(&pullmesh
->polys
,pullmesh_new_start
+i
);
1447 struct cxr_polygon
*rip_face
= cxr_ab_empty(&mesh
->polys
);
1449 rip_face
->loop_start
= mesh
->loops
.count
;
1450 rip_face
->loop_total
= pface
->loop_total
;
1451 rip_face
->material_id
= -1;
1453 for( int j
=0; j
<rip_face
->loop_total
; j
++ )
1455 struct cxr_loop
*ploop
= cxr_ab_ptr(&pullmesh
->loops
, pface
->loop_start
+pface
->loop_total
-j
-1),
1456 *rloop
= cxr_ab_empty(&mesh
->loops
);
1458 rloop
->index
= ploop
->index
;
1459 rloop
->poly_left
= rface_id
;
1460 rloop
->poly_right
= -1;
1461 rloop
->edge_index
= 0;
1462 v2_copy( ploop
->uv
, rloop
->uv
);
1465 v3_copy( pface
->center
, rip_face
->center
);
1466 v3_negate( pface
->normal
, rip_face
->normal
);
1469 cxr_mesh_clean_faces( mesh
);
1470 cxr_mesh_clean_faces( pullmesh
);
1471 cxr_mesh_clean_edges( mesh
);
1472 cxr_mesh_clean_edges( pullmesh
);
1475 free(vertex_tagged
);
1480 free(best_manifold
);
1481 free(best_manifold_splits
);
1482 free(polygon_edge_map
);
1488 free(vertex_tagged
);
1493 free(best_manifold
);
1494 free(best_manifold_splits
);
1495 free(polygon_edge_map
);
1500 static struct cxr_mesh
*cxr_to_internal_format(struct cxr_input_mesh
*src
, struct cxr_auto_buffer
*abverts
)
1502 // Split mesh into islands
1503 struct cxr_mesh
*mesh
= cxr_alloc_mesh( src
->edge_count
, src
->loop_count
, src
->poly_count
);
1504 cxr_ab_init( abverts
, sizeof(v3f
), src
->vertex_count
);
1506 // Copy input data into working mesh
1507 memcpy( cxr_ab_ptr( &mesh
->edges
, 0 ), src
->edges
, src
->edge_count
*sizeof(struct cxr_edge
));
1508 memcpy( cxr_ab_ptr( &mesh
->polys
, 0 ), src
->polys
, src
->poly_count
*sizeof(struct cxr_polygon
));
1509 memcpy( cxr_ab_ptr( abverts
, 0 ), src
->vertices
, src
->vertex_count
*sizeof(v3f
));
1510 mesh
->edges
.count
= src
->edge_count
;
1511 mesh
->loops
.count
= src
->loop_count
;
1512 mesh
->polys
.count
= src
->poly_count
;
1514 for( int i
=0; i
<src
->loop_count
; i
++ )
1516 struct cxr_loop
*lp
= cxr_ab_ptr(&mesh
->loops
,i
);
1517 lp
->index
= src
->loops
[i
].index
;
1518 lp
->edge_index
= src
->loops
[i
].edge_index
;
1519 v2_copy( src
->loops
[i
].uv
, lp
->uv
);
1522 abverts
->count
= src
->vertex_count
;
1527 // Find farthest dot product along direction
1528 static double support_distance( v3f verts
[3], v3f dir
, double coef
)
1532 coef
* v3_dot( verts
[0], dir
),
1535 coef
* v3_dot( verts
[1], dir
),
1536 coef
* v3_dot( verts
[2], dir
)
1542 static void cxr_calculate_axis(
1543 struct cxr_texinfo
*transform
,
1549 v2f tT
, bT
; // Tangent/bitangent pairs for UV space and world
1552 v2_sub( uvs
[0], uvs
[1], tT
);
1553 v2_sub( uvs
[2], uvs
[1], bT
);
1554 v3_sub( verts
[0], verts
[1], tW
);
1555 v3_sub( verts
[2], verts
[1], bW
);
1557 // Use arbitrary projection if there is no UV
1558 if( v2_length( tT
) < 0.0001 || v2_length( bT
) < 0.0001 )
1560 v3f uaxis
, normal
, vaxis
;
1562 v3_copy( tW
, uaxis
);
1563 v3_normalize( uaxis
);
1565 v3_cross( tW
, bW
, normal
);
1566 v3_cross( normal
, uaxis
, vaxis
);
1567 v3_normalize( vaxis
);
1569 v3_copy( uaxis
, transform
->uaxis
);
1570 v3_copy( vaxis
, transform
->vaxis
);
1571 v2_zero( transform
->offset
);
1573 v2_div( (v2f
){128.0, 128.0}, texture_res
, transform
->scale
);
1577 // Detect if UV is reversed
1578 double winding
= v2_cross( tT
, bT
) >= 0.0f
? 1.0f
: -1.0f
;
1580 // UV projection reference
1582 v2_muls((v2f
){1,0}, winding
, vX
);
1583 v2_muls((v2f
){0,1}, winding
, vY
);
1585 // Reproject reference into world space, including skew
1588 v3_muls( tW
, v2_cross(vX
,bT
) / v2_cross(bT
,tT
), uaxis1
);
1589 v3_muladds( uaxis1
, bW
, v2_cross(vX
, tT
) / v2_cross(tT
,bT
), uaxis1
);
1591 v3_muls( tW
, v2_cross(vY
,bT
) / v2_cross(bT
,tT
), vaxis1
);
1592 v3_muladds( vaxis1
, bW
, v2_cross(vY
,tT
) / v2_cross(tT
,bT
), vaxis1
);
1594 v3_normalize( uaxis1
);
1595 v3_normalize( vaxis1
);
1597 // Apply source transform to axis (yes, they also need to be swapped)
1598 v3f norm
, uaxis
, vaxis
;
1600 v3_cross( bW
, tW
, norm
);
1602 v3_cross( vaxis1
, norm
, uaxis
);
1603 v3_cross( uaxis1
, norm
, vaxis
);
1606 v2f uvmin
, uvmax
, uvdelta
;
1607 v2_minv( uvs
[0], uvs
[1], uvmin
);
1608 v2_minv( uvmin
, uvs
[2], uvmin
);
1609 v2_maxv( uvs
[0], uvs
[1], uvmax
);
1610 v2_maxv( uvmax
, uvs
[2], uvmax
);
1612 v2_sub( uvmax
, uvmin
, uvdelta
);
1615 v2f uvminw
, uvmaxw
, uvdeltaw
;
1616 uvminw
[0] = -support_distance( verts
, uaxis
, -1.0f
);
1617 uvmaxw
[0] = support_distance( verts
, uaxis
, 1.0f
);
1618 uvminw
[1] = -support_distance( verts
, vaxis
, -1.0f
);
1619 uvmaxw
[1] = support_distance( verts
, vaxis
, 1.0f
);
1621 v2_sub( uvmaxw
, uvminw
, uvdeltaw
);
1625 v2_div( uvdeltaw
, uvdelta
, uv_scale
);
1626 v2_div( uv_scale
, texture_res
, uv_scale
);
1628 // Find offset via 'natural' point
1629 v2f target_uv
, natural_uv
, tex_offset
;
1630 v2_mul( uvs
[0], texture_res
, target_uv
);
1632 natural_uv
[0] = v3_dot( uaxis
, verts
[0] );
1633 natural_uv
[1] = -v3_dot( vaxis
, verts
[0] );
1634 v2_div( natural_uv
, uv_scale
, natural_uv
);
1636 tex_offset
[0] = target_uv
[0]-natural_uv
[0];
1637 tex_offset
[1] = -(target_uv
[1]-natural_uv
[1]);
1639 // Copy everything into output
1640 v3_copy( uaxis
, transform
->uaxis
);
1641 v3_copy( vaxis
, transform
->vaxis
);
1642 v2_copy( tex_offset
, transform
->offset
);
1643 v2_copy( uv_scale
, transform
->scale
);
1646 CXR_API
struct cxr_input_mesh
*cxr_decompose(struct cxr_input_mesh
*src
)
1648 #ifdef CXR_DEBUG_WRITE_MESH
1649 FILE *yeet
= fopen( "/home/harry/Documents/blender_addons_remote/addons/convexer/solid.h", "w" );
1651 fprintf( yeet
, "v3f test_verts[] = {\n" );
1652 for( int i
=0; i
<src
->vertex_count
; i
++ )
1654 fprintf( yeet
, " { %f, %f, %f },\n",
1655 src
->vertices
[i
][0],
1656 src
->vertices
[i
][1],
1657 src
->vertices
[i
][2] );
1659 fprintf( yeet
, "};\n" );
1661 fprintf( yeet
, "struct cxr_input_loop test_loops[] = {\n" );
1662 for( int i
=0; i
<src
->loop_count
; i
++ )
1664 fprintf( yeet
, " {%d, %d},\n",
1665 src
->loops
[i
].index
,
1666 src
->loops
[i
].edge_index
);
1668 fprintf( yeet
, "};\n" );
1670 fprintf( yeet
, "struct cxr_polygon test_polys[] = {\n" );
1671 for( int i
=0; i
<src
->poly_count
; i
++ )
1673 fprintf( yeet
, " {%d, %d, {%f, %f, %f}, {%f, %f, %f}},\n",
1674 src
->polys
[i
].loop_start
,
1675 src
->polys
[i
].loop_total
,
1676 src
->polys
[i
].normal
[0],
1677 src
->polys
[i
].normal
[1],
1678 src
->polys
[i
].normal
[2],
1679 src
->polys
[i
].center
[0],
1680 src
->polys
[i
].center
[1],
1681 src
->polys
[i
].center
[2] );
1683 fprintf( yeet
, "};\n" );
1685 fprintf( yeet
, "struct cxr_edge test_edges[] = {\n" );
1686 for( int i
=0; i
<src
->edge_count
; i
++ )
1688 fprintf( yeet
, " {%d, %d},\n",
1693 fprintf( yeet
, "};\n" );
1695 fprintf( yeet
, "struct cxr_input_mesh test_mesh = {\n" );
1696 fprintf( yeet
, " .vertices = test_verts,\n" );
1697 fprintf( yeet
, " .loops = test_loops,\n" );
1698 fprintf( yeet
, " .edges = test_edges,\n" );
1699 fprintf( yeet
, " .polys = test_polys,\n" );
1700 fprintf( yeet
, " .poly_count=%d,\n", src
->poly_count
);
1701 fprintf( yeet
, " .vertex_count=%d,\n", src
->vertex_count
);
1702 fprintf( yeet
, " .edge_count=%d,\n",src
->edge_count
);
1703 fprintf( yeet
, " .loop_count=%d\n", src
->loop_count
);
1704 fprintf( yeet
, "};\n" );
1709 struct cxr_auto_buffer abverts
;
1710 struct cxr_mesh
*main_mesh
= cxr_to_internal_format( src
, &abverts
);
1714 struct cxr_auto_buffer solids
;
1715 cxr_ab_init( &solids
, sizeof(struct cxr_mesh
*), 2 );
1717 // TODO: Preprocessor stages
1718 // - Split mesh up into islands before doing anything here
1719 // - Snap vertices to grid (0.25u) ?
1722 struct cxr_mesh
*res
= cxr_pull_best_solid( main_mesh
, &abverts
, 0, &error
);
1725 cxr_ab_push( &solids
, &res
);
1732 // If no solids error we can rety while preserving 'hot' edges
1734 if( error
& CXR_ERROR_NO_SOLIDS
)
1737 res
= cxr_pull_best_solid(main_mesh
, &abverts
, 1, &error
);
1739 if( res
) cxr_ab_push( &solids
, &res
);
1751 cxr_ab_push( &solids
, &main_mesh
);
1755 for( int i
=0; i
<solids
.count
; i
++ )
1757 struct cxr_mesh
**mptr
= cxr_ab_ptr(&solids
,i
);
1758 cxr_debug_mesh( *mptr
, cxr_ab_ptr(&abverts
,0), colours_random
[cxr_range(i
,8)] );
1762 for( int i
=0; i
<solids
.count
; i
++ )
1764 struct cxr_mesh
**mptr
= cxr_ab_ptr(&solids
,i
);
1765 cxr_free_mesh( *mptr
);
1768 cxr_ab_free( &abverts
);
1769 cxr_ab_free( &solids
);
1774 CXR_API i32
cxr_convert_mesh_to_vmf(struct cxr_input_mesh
*src
, struct cxr_vdf
*output
)
1776 // Split mesh into islands
1777 struct cxr_auto_buffer abverts
;
1778 struct cxr_mesh
*main_mesh
= cxr_to_internal_format(src
, &abverts
);
1784 struct cxr_mesh
*pmesh
;
1785 int is_displacement
;
1788 struct cxr_auto_buffer solids
;
1789 cxr_ab_init( &solids
, sizeof(struct solidinf
), 2 );
1791 // TODO: Preprocessor stages
1792 // - Split mesh up into islands before doing anything here (DONE)
1793 // - Snap vertices to grid (0.25u) ?
1795 // Preprocessor 1: Island seperation
1800 struct cxr_mesh
*res
= cxr_pull_island( main_mesh
);
1803 cxr_ab_push( &solids
, &(struct solidinf
){ res
, 0 });
1807 cxr_ab_push( &solids
, &(struct solidinf
){main_mesh
,0} );
1809 // Preprocessor 2: Displacement break-out
1812 // Preprocessor 3: Breakup non-convex shapes into sub-solids
1814 int sources_count
= solids
.count
;
1816 for( int i
=0; i
<sources_count
; i
++ )
1818 struct solidinf pinf
= *(struct solidinf
*)cxr_ab_ptr(&solids
, i
);
1820 if( pinf
.is_displacement
)
1821 // TODO: write displacements here...
1826 struct cxr_mesh
*res
= cxr_pull_best_solid( pinf
.pmesh
, &abverts
, 0, &error
);
1830 cxr_ab_push( &solids
, &(struct solidinf
){res
,0} );
1838 // If no solids error we can rety while preserving 'hot' edges
1840 if( error
& CXR_ERROR_NO_SOLIDS
)
1843 res
= cxr_pull_best_solid(pinf
.pmesh
, &abverts
, 1, &error
);
1845 if( res
) cxr_ab_push( &solids
, &(struct solidinf
){res
,0} );
1857 if( cxr_settings
.debug
)
1859 for( int i
=0; i
<solids
.count
; i
++ )
1861 struct solidinf
*solid
= cxr_ab_ptr(&solids
,i
);
1862 cxr_debug_mesh( solid
->pmesh
, cxr_ab_ptr(&abverts
,0), colours_random
[cxr_range(i
,8)] );
1866 // Turn all those solids into VMF brushes
1867 // --------------------------------------
1868 for( int i
=0; i
<solids
.count
; i
++ )
1870 struct solidinf
*solid
= cxr_ab_ptr(&solids
,i
);
1872 if( solid
->is_displacement
) continue;
1874 cxr_vdf_node( output
, "solid" );
1875 cxr_vdf_ki32( output
, "id", ++ cxr_context
.brush_count
);
1877 for( int j
=0; j
<solid
->pmesh
->polys
.count
; j
++ )
1879 struct cxr_polygon
*poly
= cxr_ab_ptr( &solid
->pmesh
->polys
, j
);
1880 struct cxr_loop
*ploops
= cxr_ab_ptr(&solid
->pmesh
->loops
, poly
->loop_start
);
1881 struct cxr_material
*matptr
=
1882 poly
->material_id
< 0 || src
->material_count
== 0?
1884 &src
->materials
[ poly
->material_id
];
1886 cxr_vdf_node( output
, "side" );
1887 cxr_vdf_ki32( output
, "id", ++ cxr_context
.face_count
);
1889 v3f verts
[3]; v2f uvs
[3];
1891 v3_muls( cxr_ab_ptr(&abverts
, ploops
[0].index
), cxr_context
.scale_factor
, verts
[0] );
1892 v3_muls( cxr_ab_ptr(&abverts
, ploops
[1].index
), cxr_context
.scale_factor
, verts
[1] );
1893 v3_muls( cxr_ab_ptr(&abverts
, ploops
[2].index
), cxr_context
.scale_factor
, verts
[2] );
1894 verts
[0][2] += cxr_context
.offset_z
;
1895 verts
[1][2] += cxr_context
.offset_z
;
1896 verts
[2][2] += cxr_context
.offset_z
;
1898 v2_copy( ploops
[0].uv
, uvs
[0] );
1899 v2_copy( ploops
[1].uv
, uvs
[1] );
1900 v2_copy( ploops
[2].uv
, uvs
[2] );
1902 cxr_vdf_plane( output
, "plane", verts
[2], verts
[1], verts
[0] );
1903 cxr_vdf_kv( output
, "material", matptr
->vmt_path
);
1905 struct cxr_texinfo trans
;
1906 cxr_calculate_axis(&trans
, verts
, uvs
, (double[2]){ matptr
->res
[0], matptr
->res
[1] });
1908 cxr_vdf_kaxis(output
, "uaxis", trans
.uaxis
, trans
.offset
[0], trans
.scale
[0]);
1909 cxr_vdf_kaxis(output
, "vaxis", trans
.vaxis
, trans
.offset
[1], trans
.scale
[1]);
1911 cxr_vdf_kdouble(output
, "rotation", 0.0 );
1912 cxr_vdf_ki32(output
, "lightmapscale", cxr_settings
.lightmap_scale
);
1913 cxr_vdf_ki32(output
, "smoothing_groups", 0);
1915 cxr_vdf_edon( output
);
1918 cxr_vdf_node(output
, "editor");
1919 cxr_vdf_colour255(output
,"color", colours_random
[cxr_range(cxr_context
.brush_count
,8)]);
1920 cxr_vdf_ki32(output
,"visgroupshown",1);
1921 cxr_vdf_ki32(output
,"visgroupautoshown",1);
1922 cxr_vdf_edon(output
);
1924 cxr_vdf_edon( output
);
1927 for( int i
=0; i
<solids
.count
; i
++ )
1929 struct solidinf
*solid
= cxr_ab_ptr(&solids
,i
);
1930 cxr_free_mesh( solid
->pmesh
);
1933 cxr_ab_free( &abverts
);
1934 cxr_ab_free( &solids
);
1939 CXR_API
void cxr_set_log_function( void (*func
)(const char *str
) )
1941 cxr_log_func
= func
;
1944 CXR_API
void cxr_set_line_function( void (*func
)(v3f p0
, v3f p1
, v4f colour
) )
1946 cxr_line_func
= func
;
1949 CXR_API
void cxr_settings_update( struct cxr_settings
*settings
)
1951 cxr_settings
= *settings
;
1954 // Valve copyright stuff probably maybe
1955 // whatever, my previous copyright decleration ends here
1956 // ----------------------------------------------------------
1958 #define HEADER_LUMPS 64
1959 #define LUMP_WORLDLIGHTS 54
1961 #pragma pack(push,1)
1970 int fileofs
, filelen
;
1975 lumps
[ HEADER_LUMPS
];
1985 float shadow_cast_offset
[3];
1993 float constant_attn
;
1995 float quadratic_attn
;
2002 // Utility for patching BSP tools to remove -1 distance lights (we set them
2003 // like that, because we want these lights to go away)
2005 // Yes, there is no way to do this in hammer
2006 // Yes, the distance KV is unused but still gets compiled to this lump
2007 // No, Entities only compile will not do this for you
2009 CXR_API
int cxr_lightpatch_bsp( const char *path
)
2011 printf( "Lightpatch: %s\n", path
);
2013 FILE *fp
= fopen( path
, "r+b" );
2017 cxr_log( "Could not open BSP file for editing (r+b)\n" );
2022 struct header header
;
2023 fread( &header
, sizeof(struct header
), 1, fp
);
2024 struct lump
*lump
= &header
.lumps
[ LUMP_WORLDLIGHTS
];
2026 // Read worldlight array
2027 struct worldlight
*lights
= malloc( lump
->filelen
);
2028 fseek( fp
, lump
->fileofs
, SEEK_SET
);
2029 fread( lights
, lump
->filelen
, 1, fp
);
2031 // Remove all marked lights
2032 int light_count
= lump
->filelen
/ sizeof(struct worldlight
);
2035 for( int i
= 0; i
< light_count
; i
++ )
2036 if( lights
[i
].radius
>= 0.0f
)
2037 lights
[new_count
++] = lights
[i
];
2039 lump
->filelen
= new_count
*sizeof(struct worldlight
);
2042 fseek( fp
, lump
->fileofs
, SEEK_SET
);
2043 fwrite( lights
, lump
->filelen
, 1, fp
);
2044 fseek( fp
, 0, SEEK_SET
);
2045 fwrite( &header
, sizeof(struct header
), 1, fp
);
2046 cxr_log( "removed %d marked lights\n", light_count
-new_count
);