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 - It runs at an ok speed!
15 - Light patch BSP files; remove unwanted realtime effects
16 - Fastest VTF compressor (thanks to Richgel999 and stb)
20 File/folder Lang Purpose
22 __init__.py Python Blender plugin interface
23 convexer.c C Heavy lifting; brush decomp, mesh processing
24 cxr_math.h C Vector maths and other handy things
25 cxr_mem.h C Automatic resizing buffers
27 nbvtf.h C VTF processing interface
28 librgcx.h C++ Rich Geldreich's DXT1/DXT5 compressors
29 stb/ C Sean Barrets image I/O
32 const char *cxr_build_time
= __DATE__
" @" __TIME__
;
50 typedef unsigned int uint
;
52 typedef double v2f
[2];
53 typedef double v3f
[3];
54 typedef double v4f
[4];
59 #define CXR_EPSILON 0.001
60 #define CXR_PLANE_SIMILARITY_MAX 0.998
61 #define CXR_BIG_NUMBER 1e300
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
76 static v4f colours_random
[] =
78 { 0.863, 0.078, 0.235, 0.4 },
79 { 0.000, 0.980, 0.604, 0.4 },
80 { 0.118, 0.565, 1.000, 0.4 },
81 { 0.855, 0.439, 0.839, 0.4 },
82 { 0.824, 0.412, 0.118, 0.4 },
83 { 0.125, 0.698, 0.667, 0.4 },
84 { 0.541, 0.169, 0.886, 0.4 },
85 { 1.000, 0.843, 0.000, 0.4 }
88 static int cxr_range(int x
, int bound
)
91 x
+= bound
* (x
/bound
+ 1);
96 typedef struct cxr_edge cxr_edge
;
97 typedef struct cxr_input_mesh cxr_input_mesh
;
98 typedef struct cxr_input_loop cxr_input_loop
;
99 typedef struct cxr_polygon cxr_polygon
;
100 typedef struct cxr_material cxr_material
;
101 typedef struct cxr_loop cxr_loop
;
102 typedef struct cxr_solid cxr_solid
;
103 typedef struct cxr_mesh cxr_mesh
;
104 typedef struct cxr_texinfo cxr_texinfo
;
105 typedef struct cxr_vdf cxr_vdf
;
107 struct cxr_input_mesh
118 struct cxr_input_loop
128 i32 loop_start
, loop_total
;
131 i32 material_id
; /* -1: interior material (nodraw) */
138 const char *vmt_path
;
170 *p_abverts
; /* This data is stored externally because the data is often
171 shared between solids. */
173 /* Valid when update() is called on this mesh,
174 * Invalid when data is appended to them */
175 struct cxr_edge
*edges
;
176 struct cxr_polygon
*polys
;
177 struct cxr_loop
*loops
;
188 * Simplified VDF writing interface. No allocations or nodes, just write to file
196 static struct cxr_settings
205 .lightmap_scale
= 12,
207 .light_scale
= 1.0/5.0
210 static struct cxr_context
223 .scale_factor
= 32.0,
227 static struct cxr_material cxr_nodraw
= {
229 .vmt_path
= "tools/toolsnodraw"
233 * This should be called after appending any data to those buffers
235 static void cxr_mesh_update( cxr_mesh
*mesh
)
237 mesh
->edges
= cxr_ab_ptr(&mesh
->abedges
, 0);
238 mesh
->polys
= cxr_ab_ptr(&mesh
->abpolys
, 0);
239 mesh
->loops
= cxr_ab_ptr(&mesh
->abloops
, 0);
242 static v4f colour_error
= { 1.0f
, 0.0f
, 0.0f
, 1.0f
};
243 static v4f colour_face_graph
= { 1.0f
, 1.0f
, 1.0f
, 0.03f
};
244 static v4f colour_success
= { 0.0f
, 1.0f
, 0.0f
, 1.0f
};
246 static void (*cxr_log_func
)(const char *str
);
247 static void (*cxr_line_func
)( v3f p0
, v3f p1
, v4f colour
);
249 static void cxr_log( const char *fmt
, ... )
254 va_start( args
, fmt
);
255 vsnprintf( buf
, sizeof(buf
)-1, fmt
, args
);
270 * Breaks up geometry into solid pieces
271 * Turns marked mesh segments into displacements
273 CXR_API i32
cxr_convert_mesh_to_vmf(cxr_input_mesh
*src
, cxr_vdf
*output
);
275 /* Context management */
276 CXR_API
void cxr_context_reset(void);
277 CXR_API
void cxr_set_offset(double offset
);
278 CXR_API
void cxr_set_scale_factor(double scale
);
279 CXR_API
void cxr_settings_update( struct cxr_settings
*settings
);
282 CXR_API cxr_vdf
*cxr_vdf_open(const char *path
);
283 CXR_API
void cxr_vdf_close(cxr_vdf
*vdf
);
284 CXR_API
void cxr_vdf_put(cxr_vdf
*vdf
, const char *str
);
285 CXR_API
void cxr_vdf_node(cxr_vdf
*vdf
, const char *str
);
286 CXR_API
void cxr_vdf_edon( cxr_vdf
*vdf
);
287 CXR_API
void cxr_vdf_kv( cxr_vdf
*vdf
, const char *strk
, const char *strv
);
290 CXR_API
void cxr_set_log_function( void (*func
)(const char *str
) );
291 CXR_API
void cxr_set_line_function( void (*func
)(v3f p0
, v3f p1
, v4f colour
) );
292 CXR_API cxr_input_mesh
*cxr_write_test_data( cxr_input_mesh
*src
);
295 CXR_API
int cxr_lightpatch_bsp( const char *path
);
301 CXR_API
void cxr_context_reset(void)
303 cxr_context
.brush_count
= 0;
304 cxr_context
.entity_count
= 0;
305 cxr_context
.face_count
= 0;
306 cxr_context
.offset_z
= 0.0;
307 cxr_context
.scale_factor
= 32.0;
310 CXR_API
void cxr_set_offset(double offset
)
312 cxr_context
.offset_z
= offset
;
315 CXR_API
void cxr_set_scale_factor(double scale
)
317 cxr_context
.scale_factor
= scale
;
320 CXR_API cxr_vdf
*cxr_vdf_open(const char *path
)
322 cxr_vdf
*vdf
= malloc(sizeof(cxr_vdf
));
325 vdf
->fp
= fopen( path
, "w" );
336 CXR_API
void cxr_vdf_close(cxr_vdf
*vdf
)
342 CXR_API
void cxr_vdf_put(cxr_vdf
*vdf
, const char *str
)
344 for( int i
=0; i
<vdf
->level
; i
++ )
345 fputs( " ", vdf
->fp
);
347 fputs( str
, vdf
->fp
);
350 static void cxr_vdf_printf( cxr_vdf
*vdf
, const char *fmt
, ... )
355 va_start( args
, fmt
);
356 vfprintf( vdf
->fp
, fmt
, args
);
360 CXR_API
void cxr_vdf_node(cxr_vdf
*vdf
, const char *str
)
362 cxr_vdf_put( vdf
, str
);
363 putc( (u8
)'\n', vdf
->fp
);
364 cxr_vdf_put( vdf
, "{\n" );
369 CXR_API
void cxr_vdf_edon( cxr_vdf
*vdf
)
372 cxr_vdf_put( vdf
, "}\n" );
375 CXR_API
void cxr_vdf_kv( cxr_vdf
*vdf
, const char *strk
, const char *strv
)
377 cxr_vdf_printf( vdf
, "\"%s\" \"%s\"\n", strk
, strv
);
381 * Data-type specific Keyvalues
383 static void cxr_vdf_ki32( cxr_vdf
*vdf
, const char *strk
, i32 val
)
385 cxr_vdf_printf( vdf
, "\"%s\" \"%d\"\n", strk
, val
);
388 static void cxr_vdf_kdouble( cxr_vdf
*vdf
, const char *strk
, double val
)
390 cxr_vdf_printf( vdf
, "\"%s\" \"%f\"\n", strk
, val
);
393 static void cxr_vdf_kaxis( cxr_vdf
*vdf
, const char *strk
,
394 v3f normal
, double offset
, double scale
396 cxr_vdf_printf( vdf
, "\"%s\" \"[%f %f %f %f] %f\"\n",
397 strk
, normal
[0], normal
[1],normal
[2], offset
, scale
);
400 static void cxr_vdf_kv3f( cxr_vdf
*vdf
, const char *strk
, v3f v
)
402 cxr_vdf_printf( vdf
, "\"%s\" \"[%f %f %f]\"\n", strk
, v
[0], v
[1], v
[2] );
405 static void cxr_vdf_karrdouble( cxr_vdf
*vdf
, const char *strk
,
406 int id
, double *doubles
, int count
409 fprintf( vdf
->fp
, "\"%s%d\" \"", strk
, id
);
410 for( int i
=0; i
<count
; i
++ )
412 if( i
== count
-1 ) fprintf( vdf
->fp
, "%f", doubles
[i
] );
413 else fprintf( vdf
->fp
, "%f ", doubles
[i
] );
415 fprintf( vdf
->fp
, "\"\n" );
418 static void cxr_vdf_karrv3f( cxr_vdf
*vdf
, const char *strk
,
419 int id
, v3f
*vecs
, int count
422 fprintf( vdf
->fp
, "\"%s%d\" \"", strk
, id
);
423 for( int i
=0; i
<count
; i
++ )
425 const char *format
= i
== count
-1? "%f %f %f": "%f %f %f ";
426 fprintf( vdf
->fp
, format
, vecs
[i
][0], vecs
[i
][1], vecs
[i
][2] );
428 fprintf( vdf
->fp
, "\"\n" );
431 static void cxr_vdf_plane( cxr_vdf
*vdf
, const char *strk
, v3f a
, v3f b
, v3f c
)
433 cxr_vdf_printf( vdf
, "\"%s\" \"(%f %f %f) (%f %f %f) (%f %f %f)\"\n",
434 strk
, a
[0], a
[1], a
[2], b
[0], b
[1], b
[2], c
[0], c
[1], c
[2] );
437 static void cxr_vdf_colour255(cxr_vdf
*vdf
, const char *strk
, v4f colour
)
440 v4_muls( colour
, 255.0, scale
);
441 cxr_vdf_printf( vdf
, "\"%s\" \"%d %d %d %d\"\n",
442 strk
,(int)scale
[0], (int)scale
[1], (int)scale
[2], (int)scale
[3]);
446 * Debugging line drawing
448 static void cxr_debug_line( v3f p0
, v3f p1
, v4f colour
)
451 cxr_line_func( p0
, p1
, colour
);
454 static void cxr_debug_box( v3f p0
, double sz
, v4f colour
)
458 v3_add(p0
, (v3f
){-sz
,-sz
,-sz
}, a
);
459 v3_add(p0
, (v3f
){-sz
, sz
,-sz
}, b
);
460 v3_add(p0
, (v3f
){ sz
, sz
,-sz
}, c
);
461 v3_add(p0
, (v3f
){ sz
,-sz
,-sz
}, d
);
462 v3_add(p0
, (v3f
){-sz
,-sz
,sz
}, a1
);
463 v3_add(p0
, (v3f
){-sz
, sz
,sz
}, b1
);
464 v3_add(p0
, (v3f
){ sz
, sz
,sz
}, c1
);
465 v3_add(p0
, (v3f
){ sz
,-sz
,sz
}, d1
);
467 cxr_debug_line( a
,b
, colour
);
468 cxr_debug_line( b
,c
, colour
);
469 cxr_debug_line( c
,d
, colour
);
470 cxr_debug_line( d
,a
, colour
);
471 cxr_debug_line( a1
,b1
, colour
);
472 cxr_debug_line( b1
,c1
, colour
);
473 cxr_debug_line( c1
,d1
, colour
);
474 cxr_debug_line( d1
,a1
, colour
);
475 cxr_debug_line( a
,a1
, colour
);
476 cxr_debug_line( b
,b1
, colour
);
477 cxr_debug_line( c
,c1
, colour
);
478 cxr_debug_line( d
,d1
, colour
);
482 * Draw arrow with the tips oriented along normal
484 static void cxr_debug_arrow( v3f p0
, v3f p1
, v3f normal
, double sz
, v4f colour
)
486 v3f dir
, tan
, p2
, p3
;
490 v3_cross(dir
,normal
,tan
);
491 v3_muladds( p1
,dir
, -sz
, p2
);
492 v3_muladds( p2
,tan
,sz
,p3
);
493 cxr_debug_line( p1
, p3
, colour
);
494 v3_muladds( p2
,tan
,-sz
,p3
);
495 cxr_debug_line( p1
, p3
, colour
);
496 cxr_debug_line( p0
, p1
, colour
);
500 * Draw arrows CCW around polygon, draw normal vector from center
502 static void cxr_debug_poly( cxr_mesh
*mesh
, cxr_polygon
*poly
, v4f colour
)
504 v3f
*verts
= cxr_ab_ptr( mesh
->p_abverts
, 0 );
506 for( int i
=0; i
<poly
->loop_total
; i
++ )
508 int lp0
= poly
->loop_start
+i
,
509 lp1
= poly
->loop_start
+cxr_range(i
+1,poly
->loop_total
);
511 int i0
= mesh
->loops
[ lp0
].index
,
512 i1
= mesh
->loops
[ lp1
].index
;
516 v3_lerp( verts
[i0
], poly
->center
, 0.02, p0
);
517 v3_lerp( verts
[i1
], poly
->center
, 0.02, p1
);
519 cxr_debug_arrow( p0
, p1
, poly
->normal
, 0.05, colour
);
523 v3_muladds( poly
->center
, poly
->normal
, 0.3, nrm0
);
525 cxr_debug_line( poly
->center
, nrm0
, colour
);
528 static void cxr_debug_mesh(cxr_mesh
*mesh
, v4f colour
)
530 for( int i
=0; i
<mesh
->abpolys
.count
; i
++ )
532 cxr_polygon
*poly
= &mesh
->polys
[i
];
533 cxr_debug_poly( mesh
, poly
, colour
);
538 * abverts is a pointer to an existing vertex buffer
540 static cxr_mesh
*cxr_alloc_mesh( int edge_count
, int loop_count
, int poly_count
,
543 cxr_mesh
*mesh
= malloc(sizeof(cxr_mesh
));
544 cxr_ab_init(&mesh
->abedges
, sizeof(cxr_edge
), edge_count
);
545 cxr_ab_init(&mesh
->abloops
, sizeof(cxr_loop
), loop_count
);
546 cxr_ab_init(&mesh
->abpolys
, sizeof(cxr_polygon
), poly_count
);
547 mesh
->p_abverts
= abverts
;
549 cxr_mesh_update( mesh
);
554 static void cxr_free_mesh( cxr_mesh
*mesh
)
556 cxr_ab_free(&mesh
->abedges
);
557 cxr_ab_free(&mesh
->abloops
);
558 cxr_ab_free(&mesh
->abpolys
);
563 * Rebuilds edge data for mesh (useful to get rid of orphaned edges)
565 static void cxr_mesh_clean_edges( cxr_mesh
*mesh
)
567 cxr_abuffer new_edges
;
568 cxr_ab_init( &new_edges
, sizeof(cxr_edge
), mesh
->abedges
.count
);
570 for( int i
=0; i
<mesh
->abpolys
.count
; i
++ )
572 cxr_polygon
*poly
= &mesh
->polys
[i
];
573 for( int j
=0; j
<poly
->loop_total
; j
++ )
576 *lp0
= &mesh
->loops
[poly
->loop_start
+j
],
577 *lp1
= &mesh
->loops
[poly
->loop_start
+cxr_range(j
+1,poly
->loop_total
)];
579 int i0
= cxr_min(lp0
->index
, lp1
->index
),
580 i1
= cxr_max(lp0
->index
, lp1
->index
);
582 /* Check if edge exists before adding */
583 for( int k
=0; k
<new_edges
.count
; k
++ )
585 cxr_edge
*edge
= cxr_ab_ptr(&new_edges
,k
);
587 if( edge
->i0
== i0
&& edge
->i1
== i1
)
590 goto IL_EDGE_CREATED
;
594 int orig_edge_id
= lp0
->edge_index
;
595 lp0
->edge_index
= new_edges
.count
;
597 cxr_edge edge
= { i0
, i1
};
600 * Copy extra information from original edges
603 if( orig_edge_id
< mesh
->abedges
.count
)
605 cxr_edge
*orig_edge
= &mesh
->edges
[ orig_edge_id
];
606 edge
.freestyle
= orig_edge
->freestyle
;
613 cxr_ab_push( &new_edges
, &edge
);
619 cxr_ab_free( &mesh
->abedges
);
620 mesh
->abedges
= new_edges
;
622 cxr_mesh_update( mesh
);
626 * Remove 0-length faces from mesh (we mark them light that for deletion
627 * Remove all unused loops as a result of removing those faces
629 static void cxr_mesh_clean_faces( cxr_mesh
*mesh
)
631 cxr_abuffer loops_new
;
632 cxr_ab_init( &loops_new
, sizeof(cxr_loop
), mesh
->abloops
.count
);
635 for( int i
=0; i
<mesh
->abpolys
.count
; i
++ )
637 cxr_polygon
*src
= &mesh
->polys
[i
],
638 *dst
= &mesh
->polys
[new_length
];
640 if( src
->loop_total
> 0 )
642 int src_start
= src
->loop_start
,
643 src_total
= src
->loop_total
;
646 dst
->loop_start
= loops_new
.count
;
648 for( int j
=0; j
<src_total
; j
++ )
650 cxr_loop
*loop
= &mesh
->loops
[src_start
+j
],
651 *ldst
= cxr_ab_ptr(&loops_new
,dst
->loop_start
+j
);
653 ldst
->poly_left
= new_length
;
656 loops_new
.count
+= src_total
;
661 cxr_ab_free( &mesh
->abloops
);
662 mesh
->abloops
= loops_new
;
663 mesh
->abpolys
.count
= new_length
;
665 cxr_mesh_update( mesh
);
669 * Links loop's poly_left and poly_right
670 * Does not support more than 2 polys to one edge
672 * Returns 0 if there is non-manifold geomtry (aka: not watertight)
674 static int cxr_mesh_link_loops( cxr_mesh
*mesh
)
676 i32
*polygon_edge_map
= malloc(mesh
->abedges
.count
*2 *sizeof(i32
));
678 for( int i
= 0; i
< mesh
->abedges
.count
*2; i
++ )
679 polygon_edge_map
[i
] = -1;
681 for( int i
= 0; i
< mesh
->abpolys
.count
; i
++ )
683 cxr_polygon
*poly
= &mesh
->polys
[i
];
685 for( int j
= 0; j
< poly
->loop_total
; j
++ )
687 cxr_loop
*loop
= &mesh
->loops
[ poly
->loop_start
+j
];
690 for( int k
= 0; k
< 2; k
++ )
692 i32
*edge
= &polygon_edge_map
[loop
->edge_index
*2+k
];
702 for( int i
= 0; i
< mesh
->abpolys
.count
; i
++ )
704 cxr_polygon
*poly
= &mesh
->polys
[i
];
706 for( int j
= 0; j
< poly
->loop_total
; j
++ )
708 cxr_loop
*loop
= &mesh
->loops
[ poly
->loop_start
+j
];
710 i32
*face_map
= &polygon_edge_map
[ loop
->edge_index
*2 ];
712 if( face_map
[0] == loop
->poly_left
) loop
->poly_right
= face_map
[1];
713 else loop
->poly_right
= face_map
[0];
718 for( int i
=0; i
<mesh
->abedges
.count
*2; i
++ )
720 if( polygon_edge_map
[i
] == -1 )
722 free( polygon_edge_map
);
727 free( polygon_edge_map
);
732 * Create new empty polygon with known loop count
733 * Must be filled and completed by the following functions!
735 static int cxr_create_poly( cxr_mesh
*mesh
, int loop_count
)
737 v3f
*verts
= cxr_ab_ptr( mesh
->p_abverts
, 0 );
741 cxr_log( "tried to add new poly with length %d!\n", loop_count
);
745 cxr_ab_reserve( &mesh
->abpolys
, 1 );
746 cxr_ab_reserve( &mesh
->abloops
, loop_count
);
747 cxr_mesh_update( mesh
);
749 cxr_polygon
*poly
= &mesh
->polys
[ mesh
->abpolys
.count
];
751 poly
->loop_start
= mesh
->abloops
.count
;
752 poly
->loop_total
= 0;
753 poly
->material_id
= -1;
754 v3_zero( poly
->center
);
760 * Add one index to the polygon created by the above function
762 static void cxr_poly_push_index( cxr_mesh
*mesh
, int id
)
764 v3f
*verts
= cxr_ab_ptr( mesh
->p_abverts
, 0 );
766 int nface_id
= mesh
->abpolys
.count
;
767 cxr_polygon
*poly
= &mesh
->polys
[ nface_id
];
769 cxr_loop
*new_loop
= &mesh
->loops
[ poly
->loop_start
+ poly
->loop_total
];
771 new_loop
->poly_left
= nface_id
;
772 new_loop
->poly_right
= -1;
773 new_loop
->index
= id
;
774 new_loop
->edge_index
= 0;
775 v2_zero(new_loop
->uv
);
777 v3_add( poly
->center
, verts
[new_loop
->index
], poly
->center
);
780 mesh
->abloops
.count
++;
784 * Finalize and commit polygon into mesh
786 static void cxr_poly_finish( cxr_mesh
*mesh
)
788 v3f
*verts
= cxr_ab_ptr( mesh
->p_abverts
, 0 );
790 int nface_id
= mesh
->abpolys
.count
;
791 cxr_polygon
*poly
= &mesh
->polys
[nface_id
];
793 /* Average center and calc normal */
795 v3_divs( poly
->center
, poly
->loop_total
, poly
->center
);
796 cxr_loop
*lp0
= &mesh
->loops
[ poly
->loop_start
],
797 *lp1
= &mesh
->loops
[ poly
->loop_start
+1 ],
798 *lp2
= &mesh
->loops
[ poly
->loop_start
+2 ];
801 verts
[lp0
->index
], verts
[lp1
->index
], verts
[lp2
->index
], poly
->normal
);
803 mesh
->abpolys
.count
++;
807 * Extract the next island from mesh
809 * Returns NULL if mesh is one contigous object
811 static cxr_mesh
*cxr_pull_island( cxr_mesh
*mesh
)
813 cxr_mesh_link_loops(mesh
);
815 int *island_current
= malloc(mesh
->abpolys
.count
*sizeof(int)),
820 island_current
[0] = 0;
823 last_count
= island_len
;
825 for( int i
=0; i
<island_len
; i
++ )
827 cxr_polygon
*poly
= &mesh
->polys
[ island_current
[i
] ];
829 for( int j
=0; j
<poly
->loop_total
; j
++ )
831 cxr_loop
*loop
= &mesh
->loops
[ poly
->loop_start
+j
];
833 if( loop
->poly_right
!= -1 )
835 int face_present
= 0;
837 for( int k
=0; k
<island_len
; k
++ )
839 if( island_current
[k
] == loop
->poly_right
)
847 island_current
[ island_len
++ ] = loop
->poly_right
;
852 if( island_len
> last_count
)
855 /* Check for complete object */
856 if( island_len
== mesh
->abpolys
.count
)
858 free( island_current
);
862 for( int i
=0; i
<island_len
; i
++ )
864 cxr_polygon
*poly
= &mesh
->polys
[ island_current
[i
] ];
865 loop_count
+= poly
->loop_total
;
868 /* Create and update meshes */
869 cxr_mesh
*newmesh
= cxr_alloc_mesh( mesh
->abedges
.count
,
874 for( int i
=0; i
<island_len
; i
++ )
876 cxr_polygon
*src
= &mesh
->polys
[ island_current
[i
] ];
877 cxr_polygon
*dst
= cxr_ab_ptr(&newmesh
->abpolys
, i
);
880 dst
->loop_start
= newmesh
->abloops
.count
;
882 for( int j
=0; j
<src
->loop_total
; j
++ )
885 *lsrc
= &mesh
->loops
[ src
->loop_start
+j
],
886 *ldst
= cxr_ab_ptr(&newmesh
->abloops
, dst
->loop_start
+j
);
890 ldst
->poly_right
= -1;
893 newmesh
->abloops
.count
+= src
->loop_total
;
894 src
->loop_total
= -1;
897 newmesh
->abpolys
.count
= island_len
;
898 newmesh
->abedges
.count
= mesh
->abedges
.count
;
899 memcpy( cxr_ab_ptr(&newmesh
->abedges
,0),
901 mesh
->abedges
.count
* sizeof(cxr_edge
));
903 cxr_mesh_clean_faces(mesh
);
904 cxr_mesh_clean_edges(mesh
);
905 cxr_mesh_clean_edges(newmesh
);
907 free( island_current
);
912 * Invalid solid is when there are vertices that are coplanar to a face, but are
913 * outside the polygons edges.
915 static int cxr_valid_solid( cxr_mesh
*mesh
, int *solid
, int len
)
917 v3f
*verts
= cxr_ab_ptr(mesh
->p_abverts
, 0);
919 for( int i
=0; i
<len
; i
++ )
921 cxr_polygon
*polyi
= &mesh
->polys
[ solid
[i
] ];
924 normal_to_plane(polyi
->normal
, polyi
->center
, plane
);
926 for( int j
=0; j
<len
; j
++ )
930 cxr_polygon
*polyj
= &mesh
->polys
[ solid
[j
] ];
932 for( int k
=0; k
<polyj
->loop_total
; k
++ )
934 cxr_loop
*lpj
= &mesh
->loops
[ polyj
->loop_start
+k
];
936 /* Test if the vertex is not referenced by the polygon */
937 for( int l
=0; l
<polyi
->loop_total
; l
++ )
939 cxr_loop
*lpi
= &mesh
->loops
[ polyi
->loop_start
+l
];
941 if( lpi
->index
== lpj
->index
)
945 if( fabs(plane_polarity(plane
, verts
[lpj
->index
])) < 0.001 )
957 * Use when iterating the loops array, to get a unique set of edges
958 * Better than using the edges array and doing many more checks
960 static int cxr_loop_unique_edge( cxr_loop
*lp
)
962 if( lp
->poly_left
> lp
->poly_right
)
969 * Identify edges in the mesh where the two connected face's normals
970 * are opposing eachother (or close to identical)
972 static int *cxr_mesh_reflex_edges( cxr_mesh
*mesh
)
974 v3f
*verts
= cxr_ab_ptr( mesh
->p_abverts
, 0 );
975 int *edge_tagged
= malloc( mesh
->abedges
.count
* sizeof(int) );
977 for( int i
=0; i
<mesh
->abloops
.count
; i
++ )
979 cxr_loop
*lp
= &mesh
->loops
[i
];
980 if( !cxr_loop_unique_edge( lp
) ) continue;
982 edge_tagged
[lp
->edge_index
] = 0;
984 cxr_polygon
*polya
= &mesh
->polys
[ lp
->poly_left
],
985 *polyb
= &mesh
->polys
[ lp
->poly_right
];
988 normal_to_plane(polyb
->normal
, polyb
->center
, planeb
);
990 for( int j
=0; j
<polya
->loop_total
; j
++ )
992 cxr_loop
*lp1
= &mesh
->loops
[ polya
->loop_start
+j
];
994 if(( plane_polarity( planeb
, verts
[lp1
->index
] ) > 0.001 ) ||
995 ( v3_dot(polya
->normal
,polyb
->normal
) > CXR_PLANE_SIMILARITY_MAX
))
997 edge_tagged
[lp
->edge_index
] = 1;
1007 * Same logic as above function except it will apply it to each vertex
1009 static int *cxr_mesh_reflex_vertices( cxr_mesh
*mesh
)
1011 v3f
*verts
= cxr_ab_ptr( mesh
->p_abverts
, 0 );
1013 int *vertex_tagged
= malloc( mesh
->p_abverts
->count
*sizeof(int) );
1014 int *connected_planes
= malloc( mesh
->abpolys
.count
*sizeof(int) );
1016 for( int i
=0; i
<mesh
->p_abverts
->count
; i
++ )
1019 int num_connected
= 0;
1021 /* Create a list of polygons that refer to this vertex */
1022 for( int j
=0; j
<mesh
->abpolys
.count
; j
++ )
1024 cxr_polygon
*poly
= &mesh
->polys
[j
];
1025 for( int k
=0; k
<poly
->loop_total
; k
++ )
1027 cxr_loop
*loop
= &mesh
->loops
[poly
->loop_start
+k
];
1028 if( loop
->index
== i
)
1030 connected_planes
[num_connected
++] = j
;
1036 /* Check all combinations for a similar normal */
1037 for( int j
=0; j
<num_connected
-1; j
++ )
1039 for( int k
=j
+1; k
<num_connected
; k
++ )
1041 cxr_polygon
*polyj
= &mesh
->polys
[connected_planes
[j
]],
1042 *polyk
= &mesh
->polys
[connected_planes
[k
]];
1044 if( v3_dot(polyj
->normal
,polyk
->normal
) > CXR_PLANE_SIMILARITY_MAX
)
1050 * Check if all connected planes either:
1052 * - Coplanar with it
1054 for( int j
=0; j
<num_connected
; j
++ )
1056 for( int k
=j
+1; k
<num_connected
; k
++ )
1058 cxr_polygon
*jpoly
= &mesh
->polys
[ connected_planes
[j
] ],
1059 *kpoly
= &mesh
->polys
[ connected_planes
[k
] ];
1062 normal_to_plane( kpoly
->normal
, kpoly
->center
, plane
);
1063 for( int l
=0; l
<jpoly
->loop_total
; l
++ )
1065 cxr_loop
*lp
= &mesh
->loops
[ jpoly
->loop_start
+l
];
1067 if( plane_polarity( plane
, verts
[lp
->index
] ) > 0.001 )
1075 vertex_tagged
[i
] = 1;
1078 free( connected_planes
);
1079 return vertex_tagged
;
1083 * Detect if potential future edges create a collision with any of the
1084 * existing edges in the mesh
1086 static int cxr_solid_overlap( cxr_mesh
*mesh
,
1089 int common_edge_index
,
1092 v3f
*verts
= cxr_ab_ptr( mesh
->p_abverts
, 0 );
1093 cxr_edge
*common_edge
= &mesh
->edges
[common_edge_index
];
1095 int unique_a
= pa
->loop_total
-2,
1096 unique_b
= pb
->loop_total
-2;
1098 int *unique_verts
= malloc( (unique_a
+unique_b
)*sizeof(int) );
1099 int unique_total
= 0;
1101 for( int j
=0; j
<2; j
++ )
1103 cxr_polygon
*poly
= (cxr_polygon
*[2]){pa
,pb
}[j
];
1105 for( int i
=0; i
<poly
->loop_total
; i
++ )
1107 cxr_loop
*lp
= &mesh
->loops
[poly
->loop_start
+i
];
1109 if( lp
->index
== common_edge
->i0
|| lp
->index
== common_edge
->i1
)
1112 unique_verts
[ unique_total
++ ] = lp
->index
;
1118 for( int i
=0; i
<unique_a
; i
++ )
1120 for( int j
=unique_a
; j
<unique_total
; j
++ )
1122 int i0
= unique_verts
[i
],
1123 i1
= unique_verts
[j
];
1126 cxr_debug_line( verts
[i0
], verts
[i1
], colours_random
[2] );
1128 for( int k
=0; k
<mesh
->abedges
.count
; k
++ )
1130 cxr_edge
*edge
= &mesh
->edges
[k
];
1132 if( edge
->i0
== i0
|| edge
->i0
== i1
||
1133 edge
->i1
== i0
|| edge
->i1
== i1
) continue;
1135 double *a0
= verts
[i0
],
1137 *b0
= verts
[edge
->i0
],
1138 *b1
= verts
[edge
->i1
];
1140 double dist
= segment_segment_dist( a0
, a1
, b0
, b1
, ca
, cb
);
1146 cxr_debug_box( ca
, 0.025, colour_error
);
1147 cxr_debug_box( cb
, 0.025, colour_error
);
1148 cxr_debug_line( a0
, a1
, colour_error
);
1149 cxr_debug_line( b0
, b1
, colour_error
);
1155 free( unique_verts
);
1165 cxr_debug_line( verts
[mesh
->edges
[common_edge_index
].i0
],
1166 verts
[mesh
->edges
[common_edge_index
].i1
],
1170 free( unique_verts
);
1175 * Creates the 'maximal' solid that originates from this faceid
1177 * Returns the number of faces used
1179 static int cxr_buildsolid(
1186 faces_tagged
[faceid
] = faceid
;
1189 solid
[solid_len
++] = faceid
;
1191 int search_start
= 0;
1196 for( int j
=search_start
; j
<solid_len
; j
++ )
1198 cxr_polygon
*poly
= &mesh
->polys
[ solid
[j
] ];
1200 for( int k
=0; k
<poly
->loop_total
; k
++ )
1202 cxr_loop
*loop
= &mesh
->loops
[ poly
->loop_start
+k
];
1203 cxr_edge
*edge
= &mesh
->edges
[ loop
->edge_index
];
1205 if( faces_tagged
[ loop
->poly_right
] == -1 )
1207 if( !reflex_edges
[loop
->edge_index
] )
1209 /* Check for dodgy edges */
1210 cxr_polygon
*newpoly
= &mesh
->polys
[loop
->poly_right
];
1212 if( cxr_solid_overlap(mesh
,poly
,newpoly
,loop
->edge_index
,0))
1215 /* Looking ahead by one step gives us an early out for invalid
1216 * configurations. This might just all be handled by the new
1217 * edge overlap detector, though.
1219 for( int l
=0; l
< newpoly
->loop_total
; l
++ )
1221 cxr_loop
*lp1
= &mesh
->loops
[ newpoly
->loop_start
+l
];
1222 cxr_polygon
*future_face
= &mesh
->polys
[ lp1
->poly_right
];
1224 if( reflex_edges
[ lp1
->edge_index
]
1225 || lp1
->poly_right
== loop
->poly_right
)
1228 for( int m
=0; m
<solid_len
; m
++ )
1229 if( solid
[m
] == lp1
->poly_right
)
1232 for( int m
=0; m
<solid_len
; m
++ )
1234 cxr_polygon
*polym
= &mesh
->polys
[solid
[m
]];
1235 double pdist
= v3_dot( polym
->normal
,future_face
->normal
);
1237 if( pdist
> CXR_PLANE_SIMILARITY_MAX
)
1244 /* Check for vertices in the new polygon that exist on a current
1245 * plane. This condition is invalid */
1246 solid
[ solid_len
] = loop
->poly_right
;
1248 if( cxr_valid_solid(mesh
,solid
,solid_len
+1 ) )
1250 faces_tagged
[ loop
->poly_right
] = faceid
;
1260 search_start
= solid_len
;
1262 goto search_iterate
;
1269 int start
, count
, edge_count
;
1273 struct temp_manifold
1275 struct manifold_loop
1285 enum manifold_status
1289 k_manifold_fragmented
,
1290 k_manifold_complete
,
1296 * Create polygon from entire manifold structure.
1298 * Must be completely co-planar
1300 static void cxr_create_poly_full( cxr_mesh
*mesh
, struct temp_manifold
*src
)
1302 if( cxr_create_poly( mesh
, src
->loop_count
) )
1304 for( int l
=0; l
<src
->loop_count
; l
++ )
1305 cxr_poly_push_index( mesh
, src
->loops
[ l
].loop
.index
);
1307 cxr_poly_finish( mesh
);
1312 * Links up all edges into a potential new manifold
1314 * The return status can be:
1315 * (err): Critical programming error
1316 * none: No manifold to create
1317 * fragmented: Multiple sections exist, not just one
1318 * complete: Optimial manifold was created
1320 static void cxr_link_manifold(
1322 struct csolid
*solid
,
1324 struct temp_manifold
*manifold
1327 cxr_loop
**edge_list
= malloc( sizeof(*edge_list
) * solid
->edge_count
);
1329 int init_reverse
= 0;
1330 int unique_edge_count
= 0;
1332 /* Gather list of unique edges */
1334 for( int j
=0; j
<solid
->count
; j
++ )
1336 cxr_polygon
*poly
= &mesh
->polys
[ solid_buffer
[solid
->start
+j
] ];
1338 for( int k
=0; k
<poly
->loop_total
; k
++ )
1340 cxr_loop
*loop
= &mesh
->loops
[ poly
->loop_start
+k
];
1342 for( int l
=0; l
<unique_edge_count
; l
++ )
1343 if( edge_list
[l
]->edge_index
== loop
->edge_index
)
1346 for( int l
=0; l
<solid
->count
; l
++ )
1347 if( loop
->poly_right
== solid_buffer
[solid
->start
+l
] )
1350 edge_list
[ unique_edge_count
] = loop
;
1352 if( unique_edge_count
== 0 )
1354 cxr_edge
*edgeptr
= &mesh
->edges
[ loop
->edge_index
];
1355 if( edgeptr
->i1
== loop
->index
)
1359 unique_edge_count
++;
1364 if( unique_edge_count
== 0 )
1367 manifold
->status
= k_manifold_none
;
1371 /* Link edges together to form manifold */
1372 manifold
->loops
= malloc( solid
->edge_count
*sizeof(struct manifold_loop
));
1373 manifold
->split_count
= 0;
1374 manifold
->loop_count
= 0;
1376 cxr_edge
*current
= &mesh
->edges
[ edge_list
[0]->edge_index
];
1378 int endpt
= (!init_reverse
)? current
->i0
: current
->i1
,
1380 curface
= edge_list
[0]->poly_left
;
1383 for( int j
=0; j
<unique_edge_count
; j
++ )
1385 cxr_edge
*other
= &mesh
->edges
[ edge_list
[j
]->edge_index
];
1386 if( other
== current
)
1389 if( other
->i0
== endpt
|| other
->i1
== endpt
)
1394 if( other
->i0
== endpt
) endpt
= current
->i1
;
1395 else endpt
= current
->i0
;
1397 struct manifold_loop
*ml
= &manifold
->loops
[ manifold
->loop_count
++ ];
1399 if( curface
==edge_list
[j
]->poly_left
)
1402 manifold
->split_count
++;
1407 ml
->loop
.edge_index
= edge_list
[j
]->edge_index
;
1408 ml
->loop
.poly_left
= edge_list
[j
]->poly_left
;
1409 ml
->loop
.index
= lastpt
;
1410 ml
->loop
.poly_right
= edge_list
[j
]->poly_right
;
1412 curface
= edge_list
[j
]->poly_left
;
1416 if( manifold
->loop_count
< unique_edge_count
)
1417 manifold
->status
= k_manifold_fragmented
;
1419 manifold
->status
= k_manifold_complete
;
1421 goto manifold_complete
;
1424 goto manifold_continue
;
1428 /* Incomplete links */
1429 manifold
->status
= k_manifold_err
;
1438 * Reconstruct implied internal geometry where the manifold doesn't have
1439 * enough information (vertices) to create a full result.
1441 static int cxr_build_implicit_geo( cxr_mesh
*mesh
, int new_polys
, int start
)
1443 for( int i
=0; i
<new_polys
-2; i
++ )
1445 for( int j
=i
+1; j
<new_polys
-1; j
++ )
1447 for( int k
=j
+1; k
<new_polys
; k
++ )
1449 cxr_polygon
*ptri
= &mesh
->polys
[ start
+i
],
1450 *ptrj
= &mesh
->polys
[ start
+j
],
1451 *ptrk
= &mesh
->polys
[ start
+k
];
1453 v4f planei
, planej
, planek
;
1454 normal_to_plane(ptri
->normal
,ptri
->center
,planei
);
1455 normal_to_plane(ptrj
->normal
,ptrj
->center
,planej
);
1456 normal_to_plane(ptrk
->normal
,ptrk
->center
,planek
);
1460 if( plane_intersect(planei
,planej
,planek
,intersect
) )
1462 /* Make sure the point is inside the convex region */
1464 int point_valid
= 1;
1465 for( int l
=0; l
<mesh
->abpolys
.count
; l
++ )
1467 cxr_polygon
*ptrl
= &mesh
->polys
[l
];
1470 normal_to_plane(ptrl
->normal
, ptrl
->center
, planel
);
1472 if( plane_polarity( planel
, intersect
) > 0.01 )
1474 cxr_log( "degen vert, planes %d, %d, %d [max:%d]\n",
1477 cxr_debug_poly( mesh
, ptri
, colours_random
[3] );
1478 cxr_debug_poly( mesh
, ptrj
, colours_random
[1] );
1479 cxr_debug_poly( mesh
, ptrk
, colours_random
[2] );
1485 /* Extend faces to include this vert */
1487 int nvertid
= mesh
->p_abverts
->count
;
1488 cxr_ab_push( mesh
->p_abverts
, intersect
);
1490 ptrj
->loop_start
+= 1;
1491 ptrk
->loop_start
+= 2;
1493 cxr_ab_reserve( &mesh
->abloops
, 3);
1495 int newi
= ptri
->loop_start
+ptri
->loop_total
,
1496 newj
= ptrj
->loop_start
+ptrj
->loop_total
,
1497 newk
= ptrk
->loop_start
+ptrk
->loop_total
;
1500 *lloopi
= cxr_ab_empty_at(&mesh
->abloops
, newi
),
1501 *lloopj
= cxr_ab_empty_at(&mesh
->abloops
, newj
),
1502 *lloopk
= cxr_ab_empty_at(&mesh
->abloops
, newk
);
1504 lloopi
->index
= nvertid
;
1505 lloopi
->edge_index
= 0;
1506 lloopi
->poly_left
= start
+ i
;
1507 lloopi
->poly_right
= -1;
1509 lloopj
->index
= nvertid
;
1510 lloopj
->poly_left
= start
+ j
;
1511 lloopj
->edge_index
= 0;
1512 lloopj
->poly_right
= -1;
1514 lloopk
->index
= nvertid
;
1515 lloopk
->edge_index
= 0;
1516 lloopk
->poly_left
= start
+ k
;
1517 lloopk
->poly_right
= -1;
1519 v2_zero(lloopi
->uv
);
1520 v2_zero(lloopj
->uv
);
1521 v2_zero(lloopk
->uv
);
1523 ptri
->loop_total
++;
1524 ptrj
->loop_total
++;
1525 ptrk
->loop_total
++;
1527 double qi
= 1.0/(double)ptri
->loop_total
,
1528 qj
= 1.0/(double)ptrj
->loop_total
,
1529 qk
= 1.0/(double)ptrk
->loop_total
;
1531 /* Adjust centers of faces */
1532 v3_lerp( ptri
->center
, intersect
, qi
, ptri
->center
);
1533 v3_lerp( ptrj
->center
, intersect
, qj
, ptrj
->center
);
1534 v3_lerp( ptrk
->center
, intersect
, qk
, ptrk
->center
);
1544 * Convexer's main algorithm
1546 * Return the best availible convex solid from mesh, and patch the existing mesh
1547 * to fill the gap where the new mesh left it.
1549 * Returns NULL if shape is already convex or empty.
1550 * This function will not preserve edge data such as freestyle, sharp etc.
1552 static cxr_mesh
*cxr_pull_best_solid(
1554 int preserve_more_edges
,
1557 if( !cxr_mesh_link_loops(mesh
) )
1559 cxr_log( "non-manifold edges are in the mesh: "
1560 "implicit internal geometry does not have full support\n" );
1565 int *edge_tagged
= cxr_mesh_reflex_edges( mesh
);
1566 int *vertex_tagged
= cxr_mesh_reflex_vertices( mesh
);
1569 * Connect all marked vertices that share an edge
1572 int *edge_important
= malloc(mesh
->abedges
.count
*sizeof(int));
1573 for( int i
=0; i
< mesh
->abedges
.count
; i
++ )
1574 edge_important
[i
] = 0;
1576 for( int i
=0; i
<mesh
->abpolys
.count
; i
++ )
1578 cxr_polygon
*poly
= &mesh
->polys
[i
];
1579 int not_tagged
= -1,
1582 for( int j
=0; j
<poly
->loop_total
; j
++ )
1584 cxr_loop
*loop
= &mesh
->loops
[ poly
->loop_start
+j
];
1586 if( !edge_tagged
[ loop
->edge_index
] )
1588 if( not_tagged
== -1 )
1589 not_tagged
= loop
->edge_index
;
1591 goto edge_unimportant
;
1595 if( not_tagged
!= -1 )
1596 edge_important
[not_tagged
]=1;
1602 * Connect edges where both vertices are reflex, only if we are not
1605 for( int i
=0; i
<mesh
->abedges
.count
; i
++ )
1607 if( edge_important
[i
] && preserve_more_edges
) continue;
1609 cxr_edge
*edge
= &mesh
->edges
[i
];
1610 if( vertex_tagged
[edge
->i0
] && vertex_tagged
[edge
->i1
] )
1614 free( edge_important
);
1616 int *faces_tagged
= malloc(mesh
->abpolys
.count
*sizeof(int));
1617 for( int i
=0; i
<mesh
->abpolys
.count
; i
++ )
1618 faces_tagged
[i
] = -1;
1620 struct csolid
*candidates
;
1621 int *solid_buffer
= malloc( mesh
->abpolys
.count
*sizeof(int) ),
1622 solid_buffer_len
= 0,
1623 candidate_count
= 0;
1625 candidates
= malloc( mesh
->abpolys
.count
*sizeof(struct csolid
) );
1628 * Create a valid, non-overlapping solid for every face present in the mesh
1630 for( int i
=0; i
<mesh
->abpolys
.count
; i
++ )
1632 if( faces_tagged
[i
] != -1 ) continue;
1633 faces_tagged
[i
] = i
;
1635 int *solid
= &solid_buffer
[ solid_buffer_len
];
1636 int len
= cxr_buildsolid( mesh
, i
, solid
, edge_tagged
, faces_tagged
);
1639 struct csolid
*csolid
= &candidates
[candidate_count
++];
1640 csolid
->start
= solid_buffer_len
;
1641 csolid
->count
= len
;
1642 csolid
->edge_count
= 0;
1644 v3_zero( csolid
->center
);
1645 for( int j
=0; j
<len
; j
++ )
1647 cxr_polygon
*polyj
= &mesh
->polys
[ solid
[j
] ];
1648 v3_add( polyj
->center
, csolid
->center
, csolid
->center
);
1649 csolid
->edge_count
+= polyj
->loop_total
;
1651 v3_divs( csolid
->center
, len
, csolid
->center
);
1652 solid_buffer_len
+= len
;
1655 free( edge_tagged
);
1656 free( vertex_tagged
);
1657 free( faces_tagged
);
1660 * Choosing the best solid: most defined manifold
1662 struct csolid
*best_solid
= NULL
;
1663 int fewest_manifold_splits
= INT32_MAX
;
1665 struct temp_manifold best_manifold
= { .loops
= NULL
, .loop_count
= 0 };
1666 int max_solid_faces
= 0;
1668 for( int i
=0; i
<candidate_count
; i
++ )
1670 struct csolid
*solid
= &candidates
[i
];
1671 max_solid_faces
= cxr_max(max_solid_faces
,solid
->count
);
1673 if( solid
->count
<= 2 )
1676 struct temp_manifold manifold
;
1677 cxr_link_manifold( mesh
, solid
, solid_buffer
, &manifold
);
1679 if( manifold
.status
== k_manifold_err
)
1681 *error
= CXR_ERROR_BAD_MANIFOLD
;
1684 free(manifold
.loops
);
1685 free(best_manifold
.loops
);
1689 if( manifold
.status
== k_manifold_complete
)
1691 if( manifold
.split_count
< fewest_manifold_splits
)
1693 fewest_manifold_splits
= manifold
.split_count
;
1696 free( best_manifold
.loops
);
1697 best_manifold
= manifold
;
1702 if( manifold
.status
!= k_manifold_none
)
1703 free( manifold
.loops
);
1706 if( max_solid_faces
< 2 )
1708 *error
= CXR_ERROR_NO_SOLIDS
;
1711 free(best_manifold
.loops
);
1715 if( best_solid
!= NULL
)
1717 cxr_mesh
*pullmesh
= cxr_alloc_mesh( best_solid
->edge_count
,
1718 best_solid
->edge_count
,
1722 for( int i
=0; i
<best_solid
->count
; i
++ )
1724 int nface_id
= pullmesh
->abpolys
.count
;
1725 int exist_plane_id
= solid_buffer
[best_solid
->start
+i
];
1727 cxr_polygon
*exist_face
= &mesh
->polys
[ exist_plane_id
],
1728 *new_face
= cxr_ab_empty( &pullmesh
->abpolys
);
1730 *new_face
= *exist_face
;
1731 new_face
->loop_start
= pullmesh
->abloops
.count
;
1733 for( int j
=0; j
<exist_face
->loop_total
; j
++ )
1735 cxr_loop
*exist_loop
= &mesh
->loops
[ exist_face
->loop_start
+j
],
1736 *new_loop
= cxr_ab_empty(&pullmesh
->abloops
);
1738 new_loop
->index
= exist_loop
->index
;
1739 new_loop
->poly_left
= nface_id
;
1740 new_loop
->poly_right
= -1;
1741 new_loop
->edge_index
= 0;
1742 v2_copy( exist_loop
->uv
, new_loop
->uv
);
1745 exist_face
->loop_total
= -1;
1749 int pullmesh_new_start
= pullmesh
->abpolys
.count
;
1751 if( fewest_manifold_splits
!= 0 )
1753 /* Unusual observation:
1754 * If the split count is odd, the manifold can be created easily
1756 * If it is even, implicit internal geometry is needed to be
1757 * constructed. So the manifold gets folded as we create it segment
1760 * I'm not sure if this is a well defined rule of geometry, but seems
1761 * to apply to the data we care about.
1763 int collapse_used_segments
= (u32
)fewest_manifold_splits
& 0x1? 0: 1;
1767 for( int j
=0; j
< best_manifold
.loop_count
; j
++ )
1769 if( !best_manifold
.loops
[j
].split
) continue;
1771 cxr_loop
*loop
= &best_manifold
.loops
[j
].loop
;
1773 for( int k
=1; k
< best_manifold
.loop_count
; k
++ )
1775 int index1
= cxr_range(j
+k
, best_manifold
.loop_count
);
1776 cxr_loop
*loop1
= &best_manifold
.loops
[index1
].loop
;
1778 if( best_manifold
.loops
[index1
].split
)
1785 if( new_polys
> best_manifold
.loop_count
)
1787 cxr_log( "Programming error: Too many new polys!\n" );
1791 if( cxr_create_poly( pullmesh
, k
+1 ) )
1793 for( int l
=0; l
<k
+1; l
++ )
1795 int i0
= cxr_range(j
+l
, best_manifold
.loop_count
),
1796 index
= best_manifold
.loops
[ i0
].loop
.index
;
1798 cxr_poly_push_index( pullmesh
, index
);
1800 cxr_poly_finish( pullmesh
);
1803 /* Collapse down manifold */
1804 if( collapse_used_segments
)
1806 best_manifold
.loops
[j
].split
= 0;
1807 best_manifold
.loops
[index1
].split
= 0;
1809 int new_length
= (best_manifold
.loop_count
-(k
-1));
1811 struct temp_manifold new_manifold
= {
1812 .loop_count
= new_length
1814 new_manifold
.loops
=
1815 malloc( new_length
*sizeof(*new_manifold
.loops
) );
1817 for( int l
=0; l
<new_length
; l
++ )
1819 int i_src
= cxr_range( j
+k
+l
, best_manifold
.loop_count
);
1820 new_manifold
.loops
[l
] = best_manifold
.loops
[i_src
];
1823 free( best_manifold
.loops
);
1824 best_manifold
= new_manifold
;
1826 goto manifold_repeat
;
1835 if( best_manifold
.loop_count
&& collapse_used_segments
)
1837 cxr_create_poly_full( pullmesh
, &best_manifold
);
1843 cxr_create_poly_full( pullmesh
, &best_manifold
);
1847 if( new_polys
>= 3 )
1849 if( !cxr_build_implicit_geo( pullmesh
, new_polys
, pullmesh_new_start
))
1853 free(best_manifold
.loops
);
1855 cxr_free_mesh( pullmesh
);
1856 *error
= CXR_ERROR_DEGEN_IMPLICIT
;
1862 * Copy faces from the pullmesh into original, to patch up where there
1863 * would be gaps created
1865 for( int i
=0; i
<new_polys
; i
++ )
1867 int rface_id
= mesh
->abpolys
.count
;
1868 cxr_polygon
*pface
= &pullmesh
->polys
[pullmesh_new_start
+i
],
1869 *rip_face
= cxr_ab_empty(&mesh
->abpolys
);
1871 rip_face
->loop_start
= mesh
->abloops
.count
;
1872 rip_face
->loop_total
= pface
->loop_total
;
1873 rip_face
->material_id
= -1;
1875 for( int j
=0; j
<rip_face
->loop_total
; j
++ )
1878 &pullmesh
->loops
[ pface
->loop_start
+pface
->loop_total
-j
-1 ],
1879 *rloop
= cxr_ab_empty(&mesh
->abloops
);
1881 rloop
->index
= ploop
->index
;
1882 rloop
->poly_left
= rface_id
;
1883 rloop
->poly_right
= -1;
1884 rloop
->edge_index
= 0;
1885 v2_copy( ploop
->uv
, rloop
->uv
);
1888 v3_copy( pface
->center
, rip_face
->center
);
1889 v3_negate( pface
->normal
, rip_face
->normal
);
1892 cxr_mesh_update( mesh
);
1893 cxr_mesh_update( pullmesh
);
1895 cxr_mesh_clean_faces( mesh
);
1896 cxr_mesh_clean_edges( mesh
);
1897 cxr_mesh_clean_faces( pullmesh
);
1898 cxr_mesh_clean_edges( pullmesh
);
1902 free(best_manifold
.loops
);
1909 free(best_manifold
.loops
);
1915 * Convert from the format we recieve from blender into our internal format
1916 * with auto buffers.
1918 static cxr_mesh
*cxr_to_internal_format(
1919 cxr_input_mesh
*src
,
1920 cxr_abuffer
*abverts
1922 cxr_mesh
*mesh
= cxr_alloc_mesh( src
->edge_count
, src
->loop_count
,
1923 src
->poly_count
, abverts
);
1925 cxr_ab_init( abverts
, sizeof(v3f
), src
->vertex_count
);
1927 memcpy( mesh
->abedges
.arr
, src
->edges
, src
->edge_count
*sizeof(cxr_edge
));
1928 memcpy( mesh
->abpolys
.arr
, src
->polys
, src
->poly_count
*sizeof(cxr_polygon
));
1929 memcpy( abverts
->arr
, src
->vertices
, src
->vertex_count
*sizeof(v3f
));
1930 mesh
->abedges
.count
= src
->edge_count
;
1931 mesh
->abloops
.count
= src
->loop_count
;
1932 mesh
->abpolys
.count
= src
->poly_count
;
1934 cxr_mesh_update( mesh
);
1936 for( int i
=0; i
<src
->loop_count
; i
++ )
1938 cxr_loop
*lp
= &mesh
->loops
[i
];
1940 lp
->index
= src
->loops
[i
].index
;
1941 lp
->edge_index
= src
->loops
[i
].edge_index
;
1942 v2_copy( src
->loops
[i
].uv
, lp
->uv
);
1945 abverts
->count
= src
->vertex_count
;
1950 * Find most extreme point along a given direction
1952 static double support_distance( v3f verts
[3], v3f dir
, double coef
)
1956 coef
* v3_dot( verts
[0], dir
),
1959 coef
* v3_dot( verts
[1], dir
),
1960 coef
* v3_dot( verts
[2], dir
)
1966 * Convert regular UV'd triangle int Source's u/vaxis vectors
1968 * This supports affine move, scale, rotation, parallel skewing
1970 static void cxr_calculate_axis( cxr_texinfo
*transform
, v3f verts
[3],
1971 v2f uvs
[3], v2f texture_res
1973 v2f tT
, bT
; /* Tangent/bitangent pairs for UV space and world */
1976 v2_sub( uvs
[0], uvs
[1], tT
);
1977 v2_sub( uvs
[2], uvs
[1], bT
);
1978 v3_sub( verts
[0], verts
[1], tW
);
1979 v3_sub( verts
[2], verts
[1], bW
);
1981 /* Use arbitrary projection if there is no UV */
1982 if( v2_length( tT
) < 0.0001 || v2_length( bT
) < 0.0001 )
1984 v3f uaxis
, normal
, vaxis
;
1986 v3_copy( tW
, uaxis
);
1987 v3_normalize( uaxis
);
1989 v3_cross( tW
, bW
, normal
);
1990 v3_cross( normal
, uaxis
, vaxis
);
1991 v3_normalize( vaxis
);
1993 v3_copy( uaxis
, transform
->uaxis
);
1994 v3_copy( vaxis
, transform
->vaxis
);
1995 v2_zero( transform
->offset
);
1997 v2_div( (v2f
){128.0, 128.0}, texture_res
, transform
->scale
);
1998 transform
->winding
= 1.0;
2002 /* Detect if UV is reversed */
2003 double winding
= v2_cross( tT
, bT
) >= 0.0f
? 1.0f
: -1.0f
;
2005 /* UV projection reference */
2007 v2_muls((v2f
){1,0}, winding
, vX
);
2008 v2_muls((v2f
){0,1}, winding
, vY
);
2010 /* Reproject reference into world space, including skew */
2013 v3_muls( tW
, v2_cross(vX
,bT
) / v2_cross(bT
,tT
), uaxis1
);
2014 v3_muladds( uaxis1
, bW
, v2_cross(vX
, tT
) / v2_cross(tT
,bT
), uaxis1
);
2016 v3_muls( tW
, v2_cross(vY
,bT
) / v2_cross(bT
,tT
), vaxis1
);
2017 v3_muladds( vaxis1
, bW
, v2_cross(vY
,tT
) / v2_cross(tT
,bT
), vaxis1
);
2019 v3_normalize( uaxis1
);
2020 v3_normalize( vaxis1
);
2022 /* Apply source transform to axis (yes, they also need to be swapped) */
2023 v3f norm
, uaxis
, vaxis
;
2025 v3_cross( bW
, tW
, norm
);
2027 v3_cross( vaxis1
, norm
, uaxis
);
2028 v3_cross( uaxis1
, norm
, vaxis
);
2031 v2f uvmin
, uvmax
, uvdelta
;
2032 v2_minv( uvs
[0], uvs
[1], uvmin
);
2033 v2_minv( uvmin
, uvs
[2], uvmin
);
2034 v2_maxv( uvs
[0], uvs
[1], uvmax
);
2035 v2_maxv( uvmax
, uvs
[2], uvmax
);
2037 v2_sub( uvmax
, uvmin
, uvdelta
);
2039 /* world-uv scale */
2040 v2f uvminw
, uvmaxw
, uvdeltaw
;
2041 uvminw
[0] = -support_distance( verts
, uaxis
, -1.0f
);
2042 uvmaxw
[0] = support_distance( verts
, uaxis
, 1.0f
);
2043 uvminw
[1] = -support_distance( verts
, vaxis
, -1.0f
);
2044 uvmaxw
[1] = support_distance( verts
, vaxis
, 1.0f
);
2046 v2_sub( uvmaxw
, uvminw
, uvdeltaw
);
2050 v2_div( uvdeltaw
, uvdelta
, uv_scale
);
2051 v2_div( uv_scale
, texture_res
, uv_scale
);
2053 /* Find offset via 'natural' point */
2054 v2f target_uv
, natural_uv
, tex_offset
;
2055 v2_mul( uvs
[0], texture_res
, target_uv
);
2057 natural_uv
[0] = v3_dot( uaxis
, verts
[0] );
2058 natural_uv
[1] = -v3_dot( vaxis
, verts
[0] );
2059 v2_div( natural_uv
, uv_scale
, natural_uv
);
2061 tex_offset
[0] = target_uv
[0]-natural_uv
[0];
2062 tex_offset
[1] = -(target_uv
[1]-natural_uv
[1]);
2064 /* Copy everything into output */
2065 v3_copy( uaxis
, transform
->uaxis
);
2066 v3_copy( vaxis
, transform
->vaxis
);
2067 v2_copy( tex_offset
, transform
->offset
);
2068 v2_copy( uv_scale
, transform
->scale
);
2069 transform
->winding
= winding
;
2072 CXR_API cxr_input_mesh
*cxr_write_test_data( cxr_input_mesh
*src
)
2075 "/home/harry/Documents/blender_addons_remote/addons/convexer/src/solid.h",
2078 fprintf( fp
, "v3f test_verts[] = {\n" );
2079 for( int i
=0; i
<src
->vertex_count
; i
++ )
2081 fprintf( fp
, " { %f, %f, %f },\n",
2082 src
->vertices
[i
][0],
2083 src
->vertices
[i
][1],
2084 src
->vertices
[i
][2] );
2086 fprintf( fp
, "};\n" );
2088 fprintf( fp
, "struct cxr_input_loop test_loops[] = {\n" );
2089 for( int i
=0; i
<src
->loop_count
; i
++ )
2091 fprintf( fp
, " {%d, %d},\n",
2092 src
->loops
[i
].index
,
2093 src
->loops
[i
].edge_index
);
2095 fprintf( fp
, "};\n" );
2097 fprintf( fp
, "struct cxr_polygon test_polys[] = {\n" );
2098 for( int i
=0; i
<src
->poly_count
; i
++ )
2100 fprintf( fp
, " {%d, %d, {%f, %f, %f}, {%f, %f, %f}},\n",
2101 src
->polys
[i
].loop_start
,
2102 src
->polys
[i
].loop_total
,
2103 src
->polys
[i
].normal
[0],
2104 src
->polys
[i
].normal
[1],
2105 src
->polys
[i
].normal
[2],
2106 src
->polys
[i
].center
[0],
2107 src
->polys
[i
].center
[1],
2108 src
->polys
[i
].center
[2] );
2110 fprintf( fp
, "};\n" );
2112 fprintf( fp
, "struct cxr_edge test_edges[] = {\n" );
2113 for( int i
=0; i
<src
->edge_count
; i
++ )
2115 fprintf( fp
, " {%d, %d, %d},\n",
2118 src
->edges
[i
].freestyle
2121 fprintf( fp
, "};\n" );
2123 fprintf( fp
, "struct cxr_input_mesh test_mesh = {\n" );
2124 fprintf( fp
, " .vertices = test_verts,\n" );
2125 fprintf( fp
, " .loops = test_loops,\n" );
2126 fprintf( fp
, " .edges = test_edges,\n" );
2127 fprintf( fp
, " .polys = test_polys,\n" );
2128 fprintf( fp
, " .poly_count=%d,\n", src
->poly_count
);
2129 fprintf( fp
, " .vertex_count=%d,\n", src
->vertex_count
);
2130 fprintf( fp
, " .edge_count=%d,\n",src
->edge_count
);
2131 fprintf( fp
, " .loop_count=%d\n", src
->loop_count
);
2132 fprintf( fp
, "};\n" );
2139 static int cxr_cardinal( v3f a
, int ignore
)
2142 double component_max
= -CXR_BIG_NUMBER
;
2144 for( int i
=0; i
<3; i
++ )
2146 if( i
== ignore
) continue;
2148 if( fabs(a
[i
]) > component_max
)
2150 component_max
= fabs(a
[i
]);
2154 double d
= a
[component
] >= 0.0? 1.0: -1.0;
2162 * Convert contiguous mesh to displacement patch
2164 static void cxr_write_disp( cxr_mesh
*mesh
, cxr_input_mesh
*inputmesh
,
2167 v3f
*verts
= cxr_ab_ptr( mesh
->p_abverts
, 0 );
2171 int con_start
, con_count
;
2179 *vertinfo
= malloc( sizeof(struct vertinfo
)*mesh
->p_abverts
->count
);
2180 int *graph
= malloc( sizeof(int) * mesh
->abedges
.count
*2 );
2183 for( int i
=0; i
<mesh
->p_abverts
->count
; i
++ )
2185 struct vertinfo
*info
= &vertinfo
[i
];
2186 info
->con_start
= con_pos
;
2187 info
->con_count
= 0;
2194 for( int j
=0; j
<mesh
->abedges
.count
; j
++ )
2196 cxr_edge
*edge
= &mesh
->edges
[j
];
2198 if( edge
->i0
== i
|| edge
->i1
== i
)
2200 graph
[ con_pos
++ ] = edge
->i0
== i
? edge
->i1
: edge
->i0
;
2203 if( edge
->freestyle
)
2210 * Find best normal for brush patch. VBSP uses the original brush as an
2211 * reference for decal projection in-game
2214 v3f avg_normal
, refv
, refu
, refn
;
2215 v3_zero(refv
); v3_zero(refu
); v3_zero(refn
);
2217 for( int i
=0; i
<mesh
->abpolys
.count
; i
++ )
2219 cxr_polygon
*poly
= &mesh
->polys
[i
];
2220 v3_add( poly
->normal
, avg_normal
, avg_normal
);
2222 v3_divs( avg_normal
, mesh
->abpolys
.count
, avg_normal
);
2224 if( v3_length( avg_normal
) <= 1e-6 )
2225 v3_copy( (v3f
){ 0.0, 0.0, 1.0 }, avg_normal
);
2227 v3_normalize( avg_normal
);
2230 * Approximately match the area of the result brush faces to the actual
2233 * Necessary for accuracy and even lightmap texel allocation
2236 double uv_area
= 0.0, face_area
= 0.0, sf
;
2237 v2f uvboundmin
, uvboundmax
;
2238 v3f faceboundmin
, faceboundmax
;
2242 v2_fill( uvboundmin
, CXR_BIG_NUMBER
);
2243 v2_fill( uvboundmax
, -CXR_BIG_NUMBER
);
2244 v3_fill( faceboundmin
, CXR_BIG_NUMBER
);
2245 v3_fill( faceboundmax
, -CXR_BIG_NUMBER
);
2247 for( int i
=0; i
<mesh
->abpolys
.count
; i
++ )
2249 cxr_polygon
*poly
= &mesh
->polys
[i
];
2251 for( int j
=0; j
<poly
->loop_total
; j
++ )
2253 cxr_loop
*lp0
= &mesh
->loops
[ poly
->loop_start
+j
];
2254 v2_minv( lp0
->uv
, uvboundmin
, uvboundmin
);
2255 v2_maxv( lp0
->uv
, uvboundmax
, uvboundmax
);
2256 v3_minv( verts
[lp0
->index
], faceboundmin
, faceboundmin
);
2257 v3_maxv( verts
[lp0
->index
], faceboundmax
, faceboundmax
);
2260 for( int j
=0; j
<poly
->loop_total
-2; j
++ )
2262 cxr_loop
*lp0
= &mesh
->loops
[poly
->loop_start
],
2263 *lp1
= &mesh
->loops
[poly
->loop_start
+j
+1],
2264 *lp2
= &mesh
->loops
[poly
->loop_start
+j
+2];
2267 v3_sub( verts
[lp1
->index
], verts
[lp0
->index
], va
);
2268 v3_sub( verts
[lp2
->index
], verts
[lp0
->index
], vb
);
2269 v3_cross( va
, vb
, orth
);
2271 face_area
+= v3_length( orth
) / 2.0;
2274 v2_sub( lp1
->uv
, lp0
->uv
, uva
);
2275 v2_sub( lp2
->uv
, lp0
->uv
, uvb
);
2277 uv_area
+= fabs(v2_cross( uva
, uvb
)) / 2.0;
2281 v3_add( faceboundmax
, faceboundmin
, face_center
);
2282 v3_muls( face_center
, 0.5, face_center
);
2283 v2_add( uvboundmin
, uvboundmax
, uv_center
);
2284 v2_muls( uv_center
, 0.5, uv_center
);
2286 sf
= sqrt( face_area
/ uv_area
);
2287 int corner_count
= 0;
2290 * Vertex classification
2291 * boundary vertices: they exist on a freestyle edge
2292 * corners: only connected to other boundaries
2294 for( int i
=0; i
<mesh
->p_abverts
->count
; i
++ )
2296 struct vertinfo
*info
= &vertinfo
[i
];
2297 if( !info
->boundary
) continue;
2302 for( int j
=0; j
<info
->con_count
; j
++ )
2304 int con
= graph
[info
->con_start
+j
];
2306 if( vertinfo
[con
].boundary
)
2312 if( count
> 2 || non_manifold
)
2320 * TODO(harry): This currently only supports power 2 displacements
2321 * its quite straightforward to upgrade it.
2323 * TODO(harry): Error checking is needed here for bad input data
2331 for( int i
=0; i
<mesh
->abpolys
.count
; i
++ )
2333 cxr_polygon
*basepoly
= &mesh
->polys
[i
];
2335 for( int h
=0; h
<basepoly
->loop_total
; h
++ )
2338 i1
= cxr_range(h
+1,basepoly
->loop_total
);
2340 cxr_loop
*l0
= &mesh
->loops
[ basepoly
->loop_start
+i0
],
2341 *l1
= &mesh
->loops
[ basepoly
->loop_start
+i1
];
2342 struct vertinfo
*info
= &vertinfo
[ l0
->index
];
2347 int corner_count
= 1;
2349 cxr_material
*matptr
=
2350 basepoly
->material_id
< 0 || inputmesh
->material_count
== 0?
2352 &inputmesh
->materials
[ basepoly
->material_id
];
2355 dispedge
[0] = l0
->index
;
2356 dispedge
[1] = l1
->index
;
2357 v2_copy( l0
->uv
, corner_uvs
[0] );
2359 /* Consume (use) face from orignal mesh */
2360 basepoly
->loop_total
= -1;
2362 while( dispedge_count
< 17 )
2364 struct vertinfo
*edge_head
=
2365 &vertinfo
[dispedge
[dispedge_count
-1]];
2369 if( edge_head
->corner
)
2371 /* Find polygon that has edge C-1 -> C */
2372 for( int j
=0; j
<mesh
->abpolys
.count
&& !newvert
; j
++ )
2374 cxr_polygon
*poly
= &mesh
->polys
[j
];
2376 for( int k
=0; k
<poly
->loop_total
; k
++ )
2379 i1
= cxr_range(k
+1,poly
->loop_total
);
2381 cxr_loop
*l0
= &mesh
->loops
[ poly
->loop_start
+i0
],
2382 *l1
= &mesh
->loops
[ poly
->loop_start
+i1
];
2384 if( l0
->index
== dispedge
[dispedge_count
-2] &&
2385 l1
->index
== dispedge
[dispedge_count
-1] )
2387 /* Take the next edge */
2388 v2_copy( l1
->uv
, corner_uvs
[corner_count
++] );
2390 int i2
= cxr_range(i1
+1,poly
->loop_total
);
2391 cxr_loop
*l2
= &mesh
->loops
[ poly
->loop_start
+i2
];
2393 dispedge
[dispedge_count
++] = l2
->index
;
2395 poly
->loop_total
= -1;
2403 for( int j
=0; j
<edge_head
->con_count
; j
++ )
2405 int con
= graph
[edge_head
->con_start
+j
];
2410 if( dispedge_count
> 1 )
2411 if( con
== dispedge
[dispedge_count
-2] )
2414 struct vertinfo
*coninfo
= &vertinfo
[con
];
2416 if( !coninfo
->boundary
)
2419 dispedge
[ dispedge_count
++ ] = con
;
2428 cxr_debug_box( verts
[dispedge
[dispedge_count
-1]], 0.1,
2434 /* All edges collected */
2437 v2_sub( corner_uvs
[1], corner_uvs
[0], va
);
2438 v2_sub( corner_uvs
[2], corner_uvs
[0], vb
);
2440 /* Connect up the grid
2448 * Example: a := common unused vertex that is connected to
2449 * by 1 and 15. Or y-1, and x-1 on the grid.
2450 * g := c and f common vert ^
2455 for( int j
=0; j
<5; j
++ ) grid
[j
] = dispedge
[j
];
2456 for( int j
=1; j
<5; j
++ ) grid
[j
*5+4] = dispedge
[j
+4];
2457 for( int j
=0; j
<4; j
++ ) grid
[4*5+3-j
] = dispedge
[j
+9];
2458 for( int j
=1; j
<4; j
++ ) grid
[j
*5] = dispedge
[16-j
];
2461 for( int j
=1; j
<4; j
++ )
2463 for( int k
=1; k
<4; k
++ )
2465 int s0
= grid
[(j
-1)*5+k
],
2468 struct vertinfo
*va
= &vertinfo
[s0
],
2469 *vb
= &vertinfo
[s1
];
2471 /* Find common non-used vertex */
2472 for( int l
=0; l
<va
->con_count
; l
++ )
2474 for( int m
=0; m
<vb
->con_count
; m
++ )
2476 int cona
= graph
[va
->con_start
+l
],
2477 conb
= graph
[vb
->con_start
+m
];
2481 if( vertinfo
[cona
].used
|| vertinfo
[cona
].boundary
)
2484 grid
[ j
*5+k
] = cona
;
2485 vertinfo
[cona
].used
= 1;
2492 cxr_log( "Broken displacement!\n" );
2502 * Create V reference based on first displacement.
2503 * TODO(harry): This is not the moststable selection method!
2504 * faces can come in any order, so the first disp will of
2505 * course always vary. Additionaly the triangle can be oriented
2508 * Improvement can be made by selecting a first disp/triangle
2509 * based on deterministic factors.
2511 if( disp_count
== 0 )
2515 v3_copy( verts
[dispedge
[0]], tri_ref
[0] );
2516 v3_copy( verts
[dispedge
[4]], tri_ref
[1] );
2517 v3_copy( verts
[dispedge
[8]], tri_ref
[2] );
2518 cxr_calculate_axis( &tx
, tri_ref
, corner_uvs
, (v2f
){512,512} );
2520 v3_muls( tx
.vaxis
, -1.0, refv
);
2521 int v_cardinal
= cxr_cardinal( refv
, -1 );
2523 v3_cross( tx
.vaxis
, tx
.uaxis
, refn
);
2524 v3_muls( refn
, -tx
.winding
, refn
);
2526 /* Computing new reference vectors */
2527 int n1_cardinal
= cxr_cardinal( refn
, v_cardinal
);
2531 for( int j
=0; j
<2; j
++ )
2532 if( u_cardinal
== n1_cardinal
|| u_cardinal
== v_cardinal
)
2536 refu
[u_cardinal
] = tx
.uaxis
[u_cardinal
] > 0.0? 1.0: -1.0;
2540 v3_copy( face_center
, p0
);
2541 v3_muladds( face_center
, refn
, 1.5, pn
);
2542 v3_muladds( face_center
, refv
, 1.5, pv
);
2543 v3_muladds( face_center
, refu
, 1.5, pu
);
2545 /* Draw reference vectors */
2546 if( cxr_settings
.debug
)
2548 cxr_debug_line( p0
, pn
, (v4f
){0.0,0.0,1.0,1.0});
2549 cxr_debug_line( p0
, pv
, (v4f
){0.0,1.0,0.0,1.0});
2550 cxr_debug_line( p0
, pu
, (v4f
){1.0,0.0,0.0,1.0});
2551 cxr_debug_line(tri_ref
[0],tri_ref
[1],(v4f
){1.0,1.0,1.0,1.0});
2552 cxr_debug_line(tri_ref
[1],tri_ref
[2],(v4f
){1.0,1.0,1.0,1.0});
2553 cxr_debug_line(tri_ref
[2],tri_ref
[0],(v4f
){1.0,1.0,1.0,1.0});
2557 /* Create world coordinates */
2558 v3f world_corners
[8];
2561 for( int j
=0; j
<4; j
++ )
2564 v2_sub( corner_uvs
[j
], uv_center
, local_uv
);
2565 v2_copy( corner_uvs
[j
], world_uv
[j
] );
2566 v2_muls( local_uv
, sf
, local_uv
);
2568 v3_muls( refu
, local_uv
[0], world_corners
[j
] );
2569 v3_muladds( world_corners
[j
],refv
,local_uv
[1],world_corners
[j
] );
2570 v3_add( face_center
, world_corners
[j
], world_corners
[j
] );
2573 double *colour
= colours_random
[cxr_range(disp_count
,8)];
2575 for( int j
=0; j
<4; j
++ )
2576 v3_muladds( world_corners
[j
], refn
, -1.0, world_corners
[j
+4] );
2578 if( cxr_settings
.debug
)
2580 for( int j
=0; j
<4; j
++ )
2582 double *p0
= world_corners
[j
],
2583 *p1
= world_corners
[cxr_range(j
+1,4)];
2585 cxr_debug_arrow( p0
, p1
, avg_normal
, 0.1, colour
);
2589 /* Apply world transform */
2590 for( int j
=0; j
<8; j
++ )
2592 double *p0
= world_corners
[j
];
2593 v3_muls( p0
, cxr_context
.scale_factor
, p0
);
2595 p0
[2] += cxr_context
.offset_z
;
2598 cxr_texinfo texinfo_shared
;
2599 cxr_calculate_axis( &texinfo_shared
, world_corners
, world_uv
,
2600 (v2f
){ matptr
->res
[0], matptr
->res
[1] } );
2603 cxr_vdf_node( output
, "solid" );
2604 cxr_vdf_ki32( output
, "id", ++ cxr_context
.brush_count
);
2615 double distances
[25];
2617 v3f lside0
, lside1
, lref
, vdelta
, vworld
;
2620 for( int j
=0; j
<5; j
++ )
2622 ty
= (double)j
/(double)(5-1);
2624 v3_lerp( world_corners
[0], world_corners
[3], ty
, lside0
);
2625 v3_lerp( world_corners
[1], world_corners
[2], ty
, lside1
);
2627 for( int k
=0; k
<5; k
++ )
2631 tx
= (double)k
/(double)(5-1);
2632 v3_lerp( lside0
, lside1
, tx
, lref
);
2633 v3_muls( verts
[grid
[index
]], cxr_context
.scale_factor
, vworld
);
2634 vworld
[2] += cxr_context
.offset_z
;
2636 v3_sub( vworld
, lref
, vdelta
);
2637 v3_copy( vdelta
, normals
[index
] );
2638 v3_normalize( normals
[index
] );
2639 distances
[index
] = v3_dot( vdelta
, normals
[index
] );
2643 for( int j
=0; j
<6; j
++ )
2645 int *side
= sides
[j
];
2647 cxr_vdf_node( output
, "side" );
2648 cxr_vdf_ki32( output
, "id", ++ cxr_context
.face_count
);
2649 cxr_vdf_plane( output
, "plane", world_corners
[side
[2]],
2650 world_corners
[side
[1]],
2651 world_corners
[side
[0]] );
2653 cxr_vdf_kv( output
, "material", matptr
->vmt_path
);
2655 cxr_vdf_kaxis( output
, "uaxis",
2656 texinfo_shared
.uaxis
,
2657 texinfo_shared
.offset
[0],
2658 texinfo_shared
.scale
[0] );
2659 cxr_vdf_kaxis( output
, "vaxis",
2660 texinfo_shared
.vaxis
,
2661 texinfo_shared
.offset
[1],
2662 texinfo_shared
.scale
[1] );
2664 cxr_vdf_kdouble( output
, "rotation", 0.0 );
2665 cxr_vdf_ki32( output
, "lightmapscale", cxr_settings
.lightmap_scale
);
2666 cxr_vdf_ki32( output
, "smoothing_groups", 0 );
2670 cxr_vdf_node( output
, "dispinfo" );
2671 cxr_vdf_ki32( output
, "power", 2 );
2672 cxr_vdf_kv3f( output
, "startposition", world_corners
[0] );
2673 cxr_vdf_ki32( output
, "flags", 0 );
2674 cxr_vdf_kdouble( output
, "elevation", 0.0 );
2675 cxr_vdf_ki32( output
, "subdiv", 0 );
2677 cxr_vdf_node( output
, "normals" );
2678 for( int k
=0; k
<5; k
++ )
2679 cxr_vdf_karrv3f( output
, "row", k
, &normals
[k
*5], 5 );
2680 cxr_vdf_edon( output
);
2682 cxr_vdf_node( output
, "distances" );
2683 for( int k
=0; k
<5; k
++ )
2684 cxr_vdf_karrdouble( output
, "row", k
, &distances
[k
*5], 5 );
2685 cxr_vdf_edon( output
);
2688 * TODO: This might be needed for the compilers. Opens fine in
2693 cxr_vdf_node( output, "offsets" );
2694 for( int k=0; k<5; k++ )
2695 cxr_vdf_printf( output,
2696 "\"row%d\" \"0 0 0 0 0 0 0 0 0 0 0 0 0 0 0\"\n", k );
2697 cxr_vdf_edon( output );
2699 cxr_vdf_node( output, "offset_normals" );
2700 for( int k=0; k<5; k++ )
2701 cxr_vdf_printf( output,
2702 "\"row%d\" \"0 0 1 0 0 1 0 0 1 0 0 1 0 0 1\"\n", k );
2703 cxr_vdf_edon( output );
2705 cxr_vdf_node( output, "alphas" );
2706 for( int k=0; k<5; k++ )
2707 cxr_vdf_printf( output, "\"row%d\" \"0 0 0 0 0\"\n", k );
2708 cxr_vdf_edon( output );
2710 cxr_vdf_node( output, "triangle_tags" );
2711 for( int k=0; k<5-1; k++ )
2712 cxr_vdf_printf( output,
2713 "\"row%d\" \"9 9 9 9 9 9 9 9\"\n", k );
2714 cxr_vdf_edon( output );
2716 cxr_vdf_node( output, "allowed_verts" );
2717 cxr_vdf_printf( output,
2718 "\"10\" \"-1 -1 -1 -1 -1 -1 -1 -1 -1 -1\"\n" );
2719 cxr_vdf_edon( output );
2722 cxr_vdf_edon( output
);
2725 cxr_vdf_edon( output
);
2728 cxr_vdf_node( output
, "editor");
2729 cxr_vdf_colour255( output
, "color",
2730 colours_random
[cxr_range(cxr_context
.brush_count
,8)]);
2732 cxr_vdf_ki32( output
, "visgroupshown",1);
2733 cxr_vdf_ki32( output
, "visgroupautoshown",1);
2734 cxr_vdf_edon( output
);
2736 cxr_vdf_edon( output
);
2745 static int cxr_solid_checkerr( cxr_mesh
*mesh
)
2747 v3f
*verts
= cxr_ab_ptr( mesh
->p_abverts
, 0 );
2750 for( int i
=0; i
<mesh
->abpolys
.count
; i
++ )
2754 cxr_polygon
*poly
= &mesh
->polys
[i
];
2757 normal_to_plane( poly
->normal
, poly
->center
, plane
);
2759 for( int j
=0; j
<poly
->loop_total
; j
++ )
2761 cxr_loop
*loop
= &mesh
->loops
[ poly
->loop_start
+j
];
2762 double *vert
= verts
[ loop
->index
];
2764 if( fabs(plane_polarity(plane
,vert
)) > 0.0025 )
2770 plane_project_point( plane
, vert
, ref
);
2772 cxr_debug_line( ref
, vert
, colour_error
);
2773 cxr_debug_box( vert
, 0.1, colour_error
);
2778 cxr_debug_poly( mesh
, poly
, colour_error
);
2784 CXR_API i32
cxr_convert_mesh_to_vmf(cxr_input_mesh
*src
, cxr_vdf
*output
)
2786 cxr_abuffer abverts
;
2787 cxr_mesh
*main_mesh
= cxr_to_internal_format(src
, &abverts
);
2790 int invalid_count
= 0;
2795 int is_displacement
, invalid
;
2799 cxr_ab_init( &solids
, sizeof(struct solidinf
), 2 );
2802 * Preprocessor 1: Island seperation
2806 cxr_mesh
*res
= cxr_pull_island( main_mesh
);
2809 cxr_ab_push( &solids
, &(struct solidinf
){ res
, 0 });
2813 cxr_ab_push( &solids
, &(struct solidinf
){main_mesh
,0} );
2816 * Preprocessor 2: Displacement processing & error checks
2818 for( int i
=0; i
<solids
.count
; i
++ )
2820 struct solidinf
*pinf
= cxr_ab_ptr(&solids
,i
);
2822 for( int j
=0; j
<pinf
->pmesh
->abpolys
.count
; j
++ )
2824 cxr_polygon
*poly
= &pinf
->pmesh
->polys
[ j
];
2826 for( int k
=0; k
<poly
->loop_total
; k
++ )
2828 cxr_loop
*lp
= &pinf
->pmesh
->loops
[ poly
->loop_start
+k
];
2829 cxr_edge
*edge
= &pinf
->pmesh
->edges
[ lp
->edge_index
];
2831 if( edge
->freestyle
)
2832 goto IL_SOLID_IS_DISPLACEMENT
;
2836 if( cxr_solid_checkerr( pinf
->pmesh
) )
2843 IL_SOLID_IS_DISPLACEMENT
:;
2845 pinf
->is_displacement
= 1;
2846 cxr_write_disp( pinf
->pmesh
, src
, output
);
2850 * Main convex decomp algorithm
2852 int sources_count
= solids
.count
;
2854 for( int i
=0; i
<sources_count
; i
++ )
2856 struct solidinf pinf
= *(struct solidinf
*)cxr_ab_ptr(&solids
, i
);
2858 if( pinf
.is_displacement
|| pinf
.invalid
)
2863 cxr_mesh
*res
= cxr_pull_best_solid( pinf
.pmesh
, 0, &error
);
2867 cxr_ab_push( &solids
, &(struct solidinf
){res
,0} );
2875 /* Retry if non-critical error, with extra edges */
2877 if( error
& CXR_ERROR_NO_SOLIDS
)
2880 res
= cxr_pull_best_solid(pinf
.pmesh
, 1, &error
);
2882 if( res
) cxr_ab_push( &solids
, &(struct solidinf
){res
,0} );
2896 if( cxr_settings
.debug
)
2898 for( int i
=0; i
<solids
.count
; i
++ )
2900 struct solidinf
*solid
= cxr_ab_ptr(&solids
,i
);
2902 if( !solid
->is_displacement
)
2903 cxr_debug_mesh( solid
->pmesh
, colours_random
[cxr_range(i
,8)] );
2909 for( int i
=0; i
<solids
.count
; i
++ )
2911 struct solidinf
*solid
= cxr_ab_ptr(&solids
,i
);
2912 cxr_free_mesh( solid
->pmesh
);
2915 cxr_ab_free( &abverts
);
2916 cxr_ab_free( &solids
);
2920 /* Write all solids as VMF brushes */
2921 for( int i
=0; i
<solids
.count
; i
++ )
2923 struct solidinf
*solid
= cxr_ab_ptr(&solids
,i
);
2925 if( solid
->is_displacement
) continue;
2927 cxr_vdf_node( output
, "solid" );
2928 cxr_vdf_ki32( output
, "id", ++ cxr_context
.brush_count
);
2930 for( int j
=0; j
<solid
->pmesh
->abpolys
.count
; j
++ )
2932 cxr_polygon
*poly
= &solid
->pmesh
->polys
[j
];
2933 cxr_loop
*ploops
= &solid
->pmesh
->loops
[poly
->loop_start
];
2935 cxr_material
*matptr
=
2936 poly
->material_id
< 0 || src
->material_count
== 0?
2938 &src
->materials
[ poly
->material_id
];
2940 cxr_vdf_node( output
, "side" );
2941 cxr_vdf_ki32( output
, "id", ++ cxr_context
.face_count
);
2943 v3f verts
[3]; v2f uvs
[3];
2945 int i0
= ploops
[0].index
,
2946 i1
= ploops
[1].index
,
2947 i2
= ploops
[2].index
;
2949 v3_muls( cxr_ab_ptr(&abverts
,i0
), cxr_context
.scale_factor
, verts
[0] );
2950 v3_muls( cxr_ab_ptr(&abverts
,i1
), cxr_context
.scale_factor
, verts
[1] );
2951 v3_muls( cxr_ab_ptr(&abverts
,i2
), cxr_context
.scale_factor
, verts
[2] );
2953 verts
[0][2] += cxr_context
.offset_z
;
2954 verts
[1][2] += cxr_context
.offset_z
;
2955 verts
[2][2] += cxr_context
.offset_z
;
2957 v2_copy( ploops
[0].uv
, uvs
[0] );
2958 v2_copy( ploops
[1].uv
, uvs
[1] );
2959 v2_copy( ploops
[2].uv
, uvs
[2] );
2961 cxr_vdf_plane( output
, "plane", verts
[2], verts
[1], verts
[0] );
2962 cxr_vdf_kv( output
, "material", matptr
->vmt_path
);
2965 cxr_calculate_axis( &tx
, verts
, uvs
,
2966 (double[2]){ matptr
->res
[0], matptr
->res
[1] });
2968 cxr_vdf_kaxis( output
, "uaxis", tx
.uaxis
, tx
.offset
[0], tx
.scale
[0]);
2969 cxr_vdf_kaxis( output
, "vaxis", tx
.vaxis
, tx
.offset
[1], tx
.scale
[1]);
2971 cxr_vdf_kdouble( output
, "rotation", 0.0 );
2972 cxr_vdf_ki32( output
, "lightmapscale", cxr_settings
.lightmap_scale
);
2973 cxr_vdf_ki32( output
, "smoothing_groups", 0);
2975 cxr_vdf_edon( output
);
2978 cxr_vdf_node( output
, "editor" );
2979 cxr_vdf_colour255( output
, "color",
2980 colours_random
[cxr_range(cxr_context
.brush_count
,8)]);
2982 cxr_vdf_ki32( output
, "visgroupshown", 1 );
2983 cxr_vdf_ki32( output
, "visgroupautoshown", 1 );
2984 cxr_vdf_edon( output
);
2986 cxr_vdf_edon( output
);
2989 for( int i
=0; i
<solids
.count
; i
++ )
2991 struct solidinf
*solid
= cxr_ab_ptr(&solids
,i
);
2992 cxr_free_mesh( solid
->pmesh
);
2995 cxr_ab_free( &abverts
);
2996 cxr_ab_free( &solids
);
3001 CXR_API
void cxr_set_log_function( void (*func
)(const char *str
) )
3003 cxr_log_func
= func
;
3006 CXR_API
void cxr_set_line_function( void (*func
)(v3f p0
, v3f p1
, v4f colour
) )
3008 cxr_line_func
= func
;
3011 CXR_API
void cxr_settings_update( struct cxr_settings
*settings
)
3013 cxr_settings
= *settings
;
3017 * Valve Source SDK 2015 CS:GO
3019 #define HEADER_LUMPS 64
3020 #define LUMP_WORLDLIGHTS 54
3022 #pragma pack(push,1)
3031 int fileofs
, filelen
;
3036 lumps
[ HEADER_LUMPS
];
3046 float shadow_cast_offset
[3];
3054 float constant_attn
;
3056 float quadratic_attn
;
3064 * Utility for patching BSP tools to remove -1 distance lights (we set them
3065 * like that, because we want these lights to go away)
3067 * Yes, there is no way to do this in hammer
3068 * Yes, the distance KV is unused but still gets compiled to this lump
3069 * No, Entities only compile will not do this for you
3071 CXR_API
int cxr_lightpatch_bsp( const char *path
)
3073 printf( "Lightpatch: %s\n", path
);
3075 FILE *fp
= fopen( path
, "r+b" );
3079 cxr_log( "Could not open BSP file for editing (r+b)\n" );
3084 struct header header
;
3085 fread( &header
, sizeof(struct header
), 1, fp
);
3086 struct lump
*lump
= &header
.lumps
[ LUMP_WORLDLIGHTS
];
3088 /* Read worldlight array */
3089 struct worldlight
*lights
= malloc( lump
->filelen
);
3090 fseek( fp
, lump
->fileofs
, SEEK_SET
);
3091 fread( lights
, lump
->filelen
, 1, fp
);
3093 /* Remove all marked lights */
3094 int light_count
= lump
->filelen
/ sizeof(struct worldlight
);
3097 for( int i
= 0; i
< light_count
; i
++ )
3098 if( lights
[i
].radius
>= 0.0f
)
3099 lights
[new_count
++] = lights
[i
];
3101 lump
->filelen
= new_count
*sizeof(struct worldlight
);
3103 /* Write changes back to file */
3104 fseek( fp
, lump
->fileofs
, SEEK_SET
);
3105 fwrite( lights
, lump
->filelen
, 1, fp
);
3106 fseek( fp
, 0, SEEK_SET
);
3107 fwrite( &header
, sizeof(struct header
), 1, fp
);
3108 cxr_log( "removed %d marked lights\n", light_count
-new_count
);