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
34 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_PLANE_SIMILARITY_MAX 0.999
63 #define CXR_BIG_NUMBER 1e300
64 #define CXR_INTERIOR_ANGLE_MAX 0.998
66 #define CXR_DIRTY_OPTIMISATION 1
67 #define CXR_DEBUG_WRITE_MESH 1
68 #define CXR_DEBUG_ALLOCATORS 1
69 #define CXR_MANIFOLD_DEBUG 0
71 #define CXR_ERROR_DEGEN_IMPLICIT 0x1
72 #define CXR_ERROR_BAD_MANIFOLD 0x2
73 #define CXR_ERROR_NO_SOLIDS 0x4
79 // ============================================
81 static v4f colours_random
[] =
83 { 0.863, 0.078, 0.235, 0.4 },
84 { 0.000, 0.980, 0.604, 0.4 },
85 { 0.118, 0.565, 1.000, 0.4 },
86 { 0.855, 0.439, 0.839, 0.4 },
87 { 0.824, 0.412, 0.118, 0.4 },
88 { 0.125, 0.698, 0.667, 0.4 },
89 { 0.541, 0.169, 0.886, 0.4 },
90 { 1.000, 0.843, 0.000, 0.4 }
93 static int cxr_range(int x
, int bound
)
96 x
+= bound
* (x
/bound
+ 1);
101 struct cxr_input_mesh
112 struct cxr_input_loop
122 i32 loop_start
, loop_total
;
125 i32 material_id
; // -1: interior material
132 const char *vmt_path
;
159 struct cxr_auto_buffer
172 // simple VDF writing interface
179 static struct cxr_settings
188 .lightmap_scale
= 12,
190 .light_scale
= 1.0/5.0
193 static struct cxr_context
206 .scale_factor
= 32.0,
210 static struct cxr_material cxr_nodraw
= {
212 .vmt_path
= "tools/toolsnodraw"
215 // Debugging callbacks
216 // =============================================================================
218 static v4f colour_error
= { 1.0f
, 0.0f
, 0.0f
, 1.0f
};
219 static v4f colour_face_graph
= { 1.0f
, 1.0f
, 1.0f
, 0.03f
};
220 static v4f colour_success
= { 0.0f
, 1.0f
, 0.0f
, 1.0f
};
222 static void (*cxr_log_func
)(const char *str
);
223 static void (*cxr_line_func
)( v3f p0
, v3f p1
, v4f colour
);
225 static void cxr_log( const char *fmt
, ... )
230 va_start( args
, fmt
);
231 vsnprintf( buf
, sizeof(buf
)-1, fmt
, args
);
240 static void cxr_debug_line( v3f p0
, v3f p1
, v4f colour
)
243 cxr_line_func( p0
, p1
, colour
);
246 static void cxr_debug_box( v3f p0
, double sz
, v4f colour
)
250 v3_add(p0
, (v3f
){-sz
,-sz
,-sz
}, a
);
251 v3_add(p0
, (v3f
){-sz
, sz
,-sz
}, b
);
252 v3_add(p0
, (v3f
){ sz
, sz
,-sz
}, c
);
253 v3_add(p0
, (v3f
){ sz
,-sz
,-sz
}, d
);
254 v3_add(p0
, (v3f
){-sz
,-sz
,sz
}, a1
);
255 v3_add(p0
, (v3f
){-sz
, sz
,sz
}, b1
);
256 v3_add(p0
, (v3f
){ sz
, sz
,sz
}, c1
);
257 v3_add(p0
, (v3f
){ sz
,-sz
,sz
}, d1
);
259 cxr_debug_line( a
,b
, colour
);
260 cxr_debug_line( b
,c
, colour
);
261 cxr_debug_line( c
,d
, colour
);
262 cxr_debug_line( d
,a
, colour
);
263 cxr_debug_line( a1
,b1
, colour
);
264 cxr_debug_line( b1
,c1
, colour
);
265 cxr_debug_line( c1
,d1
, colour
);
266 cxr_debug_line( d1
,a1
, colour
);
267 cxr_debug_line( a
,a1
, colour
);
268 cxr_debug_line( b
,b1
, colour
);
269 cxr_debug_line( c
,c1
, colour
);
270 cxr_debug_line( d
,d1
, colour
);
273 static void cxr_debug_arrow( v3f p0
, v3f p1
, v3f normal
, double sz
, v4f colour
)
275 v3f dir
, tan
, p2
, p3
;
279 v3_cross(dir
,normal
,tan
);
280 v3_muladds( p1
,dir
, -sz
, p2
);
281 v3_muladds( p2
,tan
,sz
,p3
);
282 cxr_debug_line( p1
, p3
, colour
);
283 v3_muladds( p2
,tan
,-sz
,p3
);
284 cxr_debug_line( p1
, p3
, colour
);
285 cxr_debug_line( p0
, p1
, colour
);
289 // =========================================================================
291 CXR_API
void cxr_context_reset(void)
293 cxr_context
.brush_count
= 0;
294 cxr_context
.entity_count
= 0;
295 cxr_context
.face_count
= 0;
296 cxr_context
.offset_z
= 0.0;
297 cxr_context
.scale_factor
= 32.0;
300 CXR_API
void cxr_set_offset(double offset
)
302 cxr_context
.offset_z
= offset
;
305 CXR_API
void cxr_set_scale_factor(double scale
)
307 cxr_context
.scale_factor
= scale
;
310 CXR_API
struct cxr_vdf
*cxr_vdf_open(const char *path
)
312 struct cxr_vdf
*vdf
= malloc(sizeof(struct cxr_vdf
));
315 vdf
->fp
= fopen( path
, "w" );
326 CXR_API
void cxr_vdf_close(struct cxr_vdf
*vdf
)
331 CXR_API
void cxr_vdf_put(struct cxr_vdf
*vdf
, const char *str
)
333 for( int i
=0; i
<vdf
->level
; i
++ )
334 fputs( " ", vdf
->fp
);
336 fputs( str
, vdf
->fp
);
339 static void cxr_vdf_printf( struct cxr_vdf
*vdf
, const char *fmt
, ... )
344 va_start( args
, fmt
);
345 vfprintf( vdf
->fp
, fmt
, args
);
349 CXR_API
void cxr_vdf_node(struct cxr_vdf
*vdf
, const char *str
)
351 cxr_vdf_put( vdf
, str
);
352 putc( (u8
)'\n', vdf
->fp
);
353 cxr_vdf_put( vdf
, "{\n" );
358 CXR_API
void cxr_vdf_edon(struct cxr_vdf
*vdf
)
361 cxr_vdf_put( vdf
, "}\n" );
364 CXR_API
void cxr_vdf_kv(struct cxr_vdf
*vdf
, const char *strk
, const char *strv
)
366 cxr_vdf_printf( vdf
, "\"%s\" \"%s\"\n", strk
, strv
);
369 static void cxr_vdf_ki32(struct cxr_vdf
*vdf
, const char *strk
, i32 val
)
371 cxr_vdf_printf( vdf
, "\"%s\" \"%d\"\n", strk
, val
);
373 static void cxr_vdf_kdouble(struct cxr_vdf
*vdf
, const char *strk
, double val
)
375 cxr_vdf_printf( vdf
, "\"%s\" \"%f\"\n", strk
, val
);
377 static void cxr_vdf_kaxis(struct cxr_vdf
*vdf
, const char *strk
, v3f normal
, double offset
, double scale
)
379 cxr_vdf_printf( vdf
, "\"%s\" \"[%f %f %f %f] %f\"\n", strk
, normal
[0],normal
[1],normal
[2],offset
,scale
);
381 static void cxr_vdf_kv3f(struct cxr_vdf
*vdf
, const char *strk
, v3f v
)
383 cxr_vdf_printf( vdf
, "\"%s\" \"[%f %f %f]\"\n", strk
, v
[0], v
[1], v
[2] );
385 static void cxr_vdf_karrdouble(struct cxr_vdf
*vdf
, const char *strk
, int id
, double *doubles
, int count
)
388 fprintf( vdf
->fp
, "\"%s%d\" \"", strk
, id
);
389 for( int i
=0; i
<count
; i
++ )
391 if( i
== count
-1 ) fprintf( vdf
->fp
, "%f", doubles
[i
] );
392 else fprintf( vdf
->fp
, "%f ", doubles
[i
] );
394 fprintf( vdf
->fp
, "\"\n" );
396 static void cxr_vdf_karrv3f(struct cxr_vdf
*vdf
, const char *strk
, int id
, v3f
*vecs
, int count
)
399 fprintf( vdf
->fp
, "\"%s%d\" \"", strk
, id
);
400 for( int i
=0; i
<count
; i
++ )
402 if( i
== count
-1 ) fprintf( vdf
->fp
, "%f %f %f", vecs
[i
][0], vecs
[i
][1], vecs
[i
][2] );
403 else fprintf( vdf
->fp
, "%f %f %f ", vecs
[i
][0], vecs
[i
][1], vecs
[i
][2] );
405 fprintf( vdf
->fp
, "\"\n" );
407 static void cxr_vdf_plane(struct cxr_vdf
*vdf
, const char *strk
, v3f a
, v3f b
, v3f c
)
409 cxr_vdf_printf( vdf
, "\"%s\" \"(%f %f %f) (%f %f %f) (%f %f %f)\"\n",
410 strk
, a
[0], a
[1], a
[2], b
[0], b
[1], b
[2], c
[0], c
[1], c
[2] );
412 static void cxr_vdf_colour255(struct cxr_vdf
*vdf
, const char *strk
, v4f colour
)
415 v4_muls( colour
, 255.0, scale
);
416 cxr_vdf_printf( vdf
, "\"%s\" \"%d %d %d %d\"\n",strk
,(int)scale
[0], (int)scale
[1], (int)scale
[2], (int)scale
[3]);
420 // =========================================================================
422 static void cxr_debug_poly(struct cxr_mesh
*mesh
, struct cxr_polygon
*poly
, v3f
*verts
, v4f colour
)
424 for( int i
=0; i
<poly
->loop_total
; i
++ )
426 struct cxr_loop
*loop0
= cxr_ab_ptr(&mesh
->loops
,poly
->loop_start
+i
),
427 *loop1
= cxr_ab_ptr(&mesh
->loops
,poly
->loop_start
+cxr_range(i
+1,poly
->loop_total
));
431 v3_lerp( verts
[loop0
->index
], poly
->center
, 0.02, p0
);
432 v3_lerp( verts
[loop1
->index
], poly
->center
, 0.02, p1
);
434 cxr_debug_arrow( p0
, p1
, poly
->normal
, 0.05, colour
);
438 v3_muladds( poly
->center
, poly
->normal
, 0.3, nrm0
);
440 cxr_debug_line( poly
->center
, nrm0
, colour
);
443 static void cxr_debug_mesh(struct cxr_mesh
*mesh
, v3f
*verts
, v4f colour
)
445 for( int i
=0; i
<mesh
->polys
.count
; i
++ )
447 struct cxr_polygon
*poly
= cxr_ab_ptr(&mesh
->polys
,i
);
448 cxr_debug_poly( mesh
, poly
, verts
, colour
);
452 static struct cxr_mesh
*cxr_alloc_mesh(int edge_count
, int loop_count
, int poly_count
)
454 struct cxr_mesh
*mesh
= malloc(sizeof(struct cxr_mesh
));
455 cxr_ab_init(&mesh
->edges
, sizeof(struct cxr_edge
), edge_count
);
456 cxr_ab_init(&mesh
->loops
, sizeof(struct cxr_loop
), loop_count
);
457 cxr_ab_init(&mesh
->polys
, sizeof(struct cxr_polygon
), poly_count
);
461 static void cxr_free_mesh(struct cxr_mesh
*mesh
)
463 cxr_ab_free(&mesh
->edges
);
464 cxr_ab_free(&mesh
->loops
);
465 cxr_ab_free(&mesh
->polys
);
469 // Rebuilds edge data and reallocates
471 static void cxr_mesh_clean_edges(struct cxr_mesh
*mesh
)
473 struct cxr_auto_buffer new_edges
;
474 cxr_ab_init( &new_edges
, sizeof(struct cxr_edge
), mesh
->edges
.count
);
476 for( int i
=0; i
<mesh
->polys
.count
; i
++ )
478 struct cxr_polygon
*poly
= cxr_ab_ptr(&mesh
->polys
,i
);
479 for( int j
=0; j
<poly
->loop_total
; j
++ )
482 *lp0
= cxr_ab_ptr(&mesh
->loops
,poly
->loop_start
+j
),
483 *lp1
= cxr_ab_ptr(&mesh
->loops
,poly
->loop_start
+cxr_range(j
+1,poly
->loop_total
));
485 int i0
= cxr_min(lp0
->index
, lp1
->index
),
486 i1
= cxr_max(lp0
->index
, lp1
->index
);
488 // See if edge exists before adding it
489 for( int k
=0; k
<new_edges
.count
; k
++ )
491 struct cxr_edge
*edge
= cxr_ab_ptr(&new_edges
,k
);
493 if( edge
->i0
== i0
&& edge
->i1
== i1
)
496 goto IL_EDGE_CREATED
;
500 int orig_edge_id
= lp0
->edge_index
;
501 lp0
->edge_index
= new_edges
.count
;
503 struct cxr_edge edge
= { i0
, i1
};
505 // Copy extra information (sharp,freestyle.. etc) here!
507 if( orig_edge_id
< mesh
->edges
.count
)
509 struct cxr_edge
*orig_edge
= cxr_ab_ptr( &mesh
->edges
, orig_edge_id
);
510 edge
.freestyle
= orig_edge
->freestyle
;
518 cxr_ab_push( &new_edges
, &edge
);
524 cxr_ab_free( &mesh
->edges
);
525 mesh
->edges
= new_edges
;
528 // Remove 0-length faces from mesh and correct loops
530 static void cxr_mesh_clean_faces(struct cxr_mesh
*mesh
)
532 struct cxr_auto_buffer loops_new
;
533 cxr_ab_init( &loops_new
, sizeof(struct cxr_loop
), mesh
->loops
.count
);
536 for( int i
=0; i
<mesh
->polys
.count
; i
++ )
538 struct cxr_polygon
*src
= cxr_ab_ptr(&mesh
->polys
,i
),
539 *dst
= cxr_ab_ptr(&mesh
->polys
,new_length
);
541 if( src
->loop_total
> 0 )
543 int src_start
= src
->loop_start
,
544 src_total
= src
->loop_total
;
547 dst
->loop_start
= loops_new
.count
;
549 for( int j
=0; j
<src_total
; j
++ )
551 struct cxr_loop
*loop
= cxr_ab_ptr(&mesh
->loops
,src_start
+j
),
552 *ldst
= cxr_ab_ptr(&loops_new
,dst
->loop_start
+j
);
554 ldst
->poly_left
= new_length
;
557 loops_new
.count
+= src_total
;
562 cxr_ab_free( &mesh
->loops
);
563 mesh
->loops
= loops_new
;
564 mesh
->polys
.count
= new_length
;
567 static i32
*cxr_mesh_link_loops(struct cxr_mesh
*mesh
)
569 i32
*polygon_edge_map
= malloc(mesh
->edges
.count
*2 *sizeof(i32
));
571 for( int i
= 0; i
< mesh
->edges
.count
*2; i
++ )
572 polygon_edge_map
[i
] = -1;
574 for( int i
= 0; i
< mesh
->polys
.count
; i
++ )
576 struct cxr_polygon
*poly
= cxr_ab_ptr(&mesh
->polys
, i
);
578 for( int j
= 0; j
< poly
->loop_total
; j
++ )
580 struct cxr_loop
*loop
= cxr_ab_ptr(&mesh
->loops
, poly
->loop_start
+j
);
583 for( int k
= 0; k
< 2; k
++ )
585 i32
*edge
= &polygon_edge_map
[loop
->edge_index
*2+k
];
595 for( int i
= 0; i
< mesh
->polys
.count
; i
++ )
597 struct cxr_polygon
*poly
= cxr_ab_ptr(&mesh
->polys
,i
);
599 for( int j
= 0; j
< poly
->loop_total
; j
++ )
601 struct cxr_loop
*loop
= cxr_ab_ptr(&mesh
->loops
,poly
->loop_start
+j
);
603 i32
*face_map
= &polygon_edge_map
[loop
->edge_index
*2];
605 if( face_map
[0] == loop
->poly_left
) loop
->poly_right
= face_map
[1];
606 else loop
->poly_right
= face_map
[0];
610 return polygon_edge_map
;
613 // Add polygon to mesh based on loop array
614 static struct cxr_polygon
*cxr_create_poly( struct cxr_mesh
*mesh
, v3f
*vertices
, struct cxr_loop poly
[],
615 int len
, int start
, int max
)
619 cxr_log( "tried to add new poly with length %d!\n", len
);
623 for( int j
=0; j
<len
; j
++ )
625 int i0
= poly
[j
].index
,
626 i1
= poly
[cxr_range(j
+1,len
)].index
;
627 cxr_debug_line( vertices
[i0
], vertices
[i1
], colour_error
);
634 int nface_id
= mesh
->polys
.count
;
635 struct cxr_polygon
*new_face
= cxr_ab_empty(&mesh
->polys
);
637 new_face
->loop_start
= mesh
->loops
.count
;
638 new_face
->loop_total
= len
;
639 new_face
->material_id
= -1;
641 // Calculate normal and center
642 v3_zero( new_face
->center
);
644 for( int j
=0; j
<len
; j
++ )
646 int i0
= poly
[cxr_range(start
+j
,max
)].index
;
647 struct cxr_loop
*new_loop
= cxr_ab_empty(&mesh
->loops
);
649 new_loop
->poly_left
= nface_id
;
650 new_loop
->poly_right
= -1;
651 new_loop
->index
= i0
;
652 new_loop
->edge_index
= 0;
653 v2_zero(new_loop
->uv
);
655 v3_add( new_face
->center
, vertices
[new_loop
->index
], new_face
->center
);
657 v3_divs( new_face
->center
, new_face
->loop_total
, new_face
->center
);
659 struct cxr_loop
*lp0
= cxr_ab_ptr( &mesh
->loops
, new_face
->loop_start
),
660 *lp1
= cxr_ab_ptr( &mesh
->loops
, new_face
->loop_start
+1 ),
661 *lp2
= cxr_ab_ptr( &mesh
->loops
, new_face
->loop_start
+2 );
663 tri_normal( vertices
[lp0
->index
], vertices
[lp1
->index
], vertices
[lp2
->index
], new_face
->normal
);
665 return cxr_ab_ptr(&mesh
->polys
, nface_id
);
668 // Get the 'next' mesh island
670 // Returns NULL if there is only one island
671 static struct cxr_mesh
*cxr_pull_island(struct cxr_mesh
*mesh
)
673 free(cxr_mesh_link_loops(mesh
));
675 int *island_current
= malloc(mesh
->polys
.count
*sizeof(int)),
680 island_current
[0] = 0;
683 last_count
= island_len
;
685 for( int i
=0; i
<island_len
; i
++ )
687 struct cxr_polygon
*poly
= cxr_ab_ptr(&mesh
->polys
,island_current
[i
]);
689 for( int j
=0; j
<poly
->loop_total
; j
++ )
691 struct cxr_loop
*loop
= cxr_ab_ptr(&mesh
->loops
, poly
->loop_start
+j
);
693 if( loop
->poly_right
!= -1 )
695 int face_present
= 0;
697 for( int k
=0; k
<island_len
; k
++ )
699 if( island_current
[k
] == loop
->poly_right
)
708 island_current
[ island_len
++ ] = loop
->poly_right
;
714 if( island_len
> last_count
)
715 goto IL_ISLAND_REPEAT
;
717 if( island_len
== mesh
->polys
.count
)
719 free( island_current
);
723 for( int i
=0; i
<island_len
; i
++ )
725 struct cxr_polygon
*poly
= cxr_ab_ptr(&mesh
->polys
, island_current
[i
]);
726 loop_count
+= poly
->loop_total
;
729 struct cxr_mesh
*newmesh
= cxr_alloc_mesh( mesh
->edges
.count
, loop_count
, island_len
);
731 for( int i
=0; i
<island_len
; i
++ )
733 struct cxr_polygon
*src
= cxr_ab_ptr(&mesh
->polys
, island_current
[i
]);
734 struct cxr_polygon
*dst
= cxr_ab_ptr(&newmesh
->polys
, i
);
737 dst
->loop_start
= newmesh
->loops
.count
;
739 for( int j
=0; j
<src
->loop_total
; j
++ )
741 struct cxr_loop
*lsrc
= cxr_ab_ptr(&mesh
->loops
, src
->loop_start
+j
),
742 *ldst
= cxr_ab_ptr(&newmesh
->loops
, dst
->loop_start
+j
);
746 ldst
->poly_right
= -1;
749 newmesh
->loops
.count
+= src
->loop_total
;
750 src
->loop_total
= -1;
753 newmesh
->polys
.count
= island_len
;
754 newmesh
->edges
.count
= mesh
->edges
.count
;
755 memcpy(cxr_ab_ptr(&newmesh
->edges
,0), cxr_ab_ptr(&mesh
->edges
,0), mesh
->edges
.count
*sizeof(struct cxr_edge
));
757 cxr_mesh_clean_faces(mesh
);
758 cxr_mesh_clean_edges(mesh
);
759 cxr_mesh_clean_edges(newmesh
);
760 free( island_current
);
765 // Return best availible solid from mesh, and patch existing mesh to fill the gap
768 // Returns NULL if shape is already convex or empty
769 // Destroys edge data!
770 static struct cxr_mesh
*cxr_pull_best_solid(
771 struct cxr_mesh
*mesh
,
772 struct cxr_auto_buffer
*vert_buffer
,
773 int preserve_hot_edges
,
776 v3f
*vertices
= cxr_ab_ptr( vert_buffer
, 0 );
778 i32
*polygon_edge_map
= cxr_mesh_link_loops(mesh
);
780 for( int i
=0; i
<mesh
->edges
.count
*2; i
++ )
781 if( polygon_edge_map
[i
] == -1 )
783 cxr_log( "non-manifold edges are in the mesh; implicit internal geometry does not have full support\n" );
784 free(polygon_edge_map
);
788 int *vertex_tagged
= malloc( vert_buffer
->count
*sizeof(int) );
789 int *edge_tagged
= malloc( mesh
->edges
.count
*sizeof(int) );
791 for( int i
=0; i
<mesh
->edges
.count
; i
++ )
793 struct cxr_polygon
*polya
= cxr_ab_ptr(&mesh
->polys
, polygon_edge_map
[i
*2+0]),
794 *polyb
= cxr_ab_ptr(&mesh
->polys
, polygon_edge_map
[i
*2+1]);
796 normal_to_plane(polyb
->normal
, polyb
->center
, planeb
);
799 for( int j
=0; j
<polya
->loop_total
; j
++ )
801 struct cxr_loop
*loop
= cxr_ab_ptr(&mesh
->loops
, polya
->loop_start
+j
);
802 if( plane_polarity( planeb
, vertices
[loop
->index
] ) > 0.000025 ||
803 v3_dot(polya
->normal
,polyb
->normal
) > CXR_PLANE_SIMILARITY_MAX
)
811 // Tag 'reflex' vertices
812 int *connected_planes
= malloc(mesh
->polys
.count
*sizeof(int));
814 for( int i
=0; i
<vert_buffer
->count
; i
++ )
818 int num_connected
= 0;
819 // Create a list of polys that ref this vert
820 for( int j
=0; j
<mesh
->polys
.count
; j
++ )
822 struct cxr_polygon
*poly
= cxr_ab_ptr(&mesh
->polys
,j
);
823 for( int k
=0; k
<poly
->loop_total
; k
++ )
825 struct cxr_loop
*loop
= cxr_ab_ptr(&mesh
->loops
,poly
->loop_start
+k
);
826 if( loop
->index
== i
)
828 connected_planes
[num_connected
++] = j
;
833 // Check all combinations for a similar normal
834 for( int j
=0; j
<num_connected
-1; j
++ )
836 for( int k
=j
+1; k
<num_connected
; k
++ )
838 struct cxr_polygon
*polyj
= cxr_ab_ptr(&mesh
->polys
,connected_planes
[j
]);
839 struct cxr_polygon
*polyk
= cxr_ab_ptr(&mesh
->polys
,connected_planes
[k
]);
841 if( v3_dot(polyj
->normal
, polyk
->normal
) > CXR_PLANE_SIMILARITY_MAX
)
846 // Check if all connected planes not are:
847 // - bounded by other planes
850 for( int j
=0; j
<num_connected
; j
++ )
851 for( int k
=j
+1; k
<num_connected
; k
++ )
853 struct cxr_polygon
*jpoly
= cxr_ab_ptr(&mesh
->polys
, connected_planes
[j
]),
854 *kpoly
= cxr_ab_ptr(&mesh
->polys
, connected_planes
[k
]);
856 normal_to_plane( kpoly
->normal
, kpoly
->center
, plane
);
857 for( int l
=0; l
<jpoly
->loop_total
; l
++ )
859 struct cxr_loop
*loop
= cxr_ab_ptr(&mesh
->loops
, jpoly
->loop_start
+l
);
860 if( plane_polarity( plane
, vertices
[loop
->index
] ) > 0.001 )
865 goto IL_TAG_NEXT_VERT
;
866 IL_TAG_VERT
: vertex_tagged
[i
] = 1;
870 free( connected_planes
);
872 // Connect all marked verts that share an edge
873 // - We must take care not to completely isolate
874 // a polygon with marked edges all around it
876 int *hot_edge
= malloc(mesh
->edges
.count
*sizeof(int));
877 for( int i
=0; i
< mesh
->edges
.count
; i
++ )
880 for( int i
=0; i
<mesh
->polys
.count
; i
++ )
882 struct cxr_polygon
*poly
= cxr_ab_ptr(&mesh
->polys
,i
);
886 for( int j
=0; j
<poly
->loop_total
; j
++ )
888 struct cxr_loop
*loop
= cxr_ab_ptr(&mesh
->loops
, poly
->loop_start
+j
);
890 if( !edge_tagged
[ loop
->edge_index
] )
892 if( not_tagged
== -1 )
893 not_tagged
= loop
->edge_index
;
895 goto IL_SKIP_NO_HOT_EDGE
;
899 if( not_tagged
!= -1 )
900 hot_edge
[not_tagged
]=1;
902 IL_SKIP_NO_HOT_EDGE
:;
905 // Connect edges that have verts tagged, but is not a hot edge
906 for( int i
=0; i
<mesh
->edges
.count
; i
++ )
908 if( hot_edge
[i
] && preserve_hot_edges
) continue;
910 struct cxr_edge
*edge
= cxr_ab_ptr(&mesh
->edges
,i
);
911 if( vertex_tagged
[edge
->i0
] && vertex_tagged
[edge
->i1
] )
916 for( int i=0; i<vertex_count; i++ )
917 if( vertex_tagged[i] )
918 cxr_debug_box( vertices[i], 0.03, (v4f){0.0,0.0,0.0,1.0});
920 for( int i=0; i < mesh->edges.count; i++ )
922 struct cxr_edge *edge = cxr_ab_ptr( &mesh->edges, i );
924 cxr_debug_line( vertices[ edge->i0 ], vertices[ edge->i1 ], (v4f){0.0,0.0,0.0,1.0});
927 cxr_debug_line( vertices[ edge->i0 ], vertices[ edge->i1 ], (v4f){0.0,1.0,1.0,1.0});
932 int *faces_tagged
= malloc(mesh
->polys
.count
*sizeof(int));
933 for( int i
=0; i
<mesh
->polys
.count
; i
++ )
934 faces_tagged
[i
] = -1;
936 int *solid_buffer
= malloc( mesh
->polys
.count
*sizeof(int) );
937 int solid_buffer_len
= 0;
940 int start
,count
,edge_count
;
943 *candidates
= malloc( mesh
->polys
.count
*sizeof(struct csolid
) );
944 int candidate_count
= 0;
946 for( int i
=0; i
<mesh
->polys
.count
; i
++ )
948 if( faces_tagged
[i
] != -1 ) continue;
951 int *solid
= &solid_buffer
[ solid_buffer_len
];
954 solid
[solid_len
++] = i
;
956 int search_start
= 0;
958 // Iterative search that connects regions of planes governed by rules:
959 // - edge can add other face if the edge has less than two reflexes
960 // - the face can no longer be used in future searches
965 for( int j
=search_start
; j
<solid_len
; j
++ )
967 struct cxr_polygon
*poly
= cxr_ab_ptr(&mesh
->polys
, solid
[j
]);
969 for( int k
=0; k
<poly
->loop_total
; k
++ )
971 struct cxr_loop
*loop
= cxr_ab_ptr(&mesh
->loops
, poly
->loop_start
+k
);
972 struct cxr_edge
*edge
= cxr_ab_ptr(&mesh
->edges
, loop
->edge_index
);
974 if( faces_tagged
[ loop
->poly_right
] == -1 )
976 if( !edge_tagged
[loop
->edge_index
] )
978 // Need to look ahead 1 step to make sure he does not want
979 // to add any more planes that are coplanar with some of
980 // our existing group
982 // TODO: is this unused due to hotedge improvements? leaving for safety...
984 struct cxr_polygon
*poly_to_add
= cxr_ab_ptr(&mesh
->polys
, loop
->poly_right
);
985 for( int l
=0; l
< poly_to_add
->loop_total
; l
++ )
987 struct cxr_loop
*loop1
= cxr_ab_ptr(&mesh
->loops
, poly_to_add
->loop_start
+l
);
988 struct cxr_polygon
*future_face
= cxr_ab_ptr(&mesh
->polys
, loop1
->poly_right
);
990 if( edge_tagged
[ loop1
->edge_index
] || loop1
->poly_right
== loop
->poly_right
)
991 goto IL_SKIP_SIMILAR_PLANES
;
993 for( int m
=0; m
<solid_len
; m
++ )
994 if( solid
[m
] == loop1
->poly_right
)
995 goto IL_SKIP_SIMILAR_PLANES
;
997 for( int m
=0; m
<solid_len
; m
++ )
999 struct cxr_polygon
*polym
= cxr_ab_ptr(&mesh
->polys
,solid
[m
]);
1000 if( v3_dot( polym
->normal
,future_face
->normal
) > CXR_PLANE_SIMILARITY_MAX
)
1001 goto IL_SKIP_PLANE_ADD
;
1004 IL_SKIP_SIMILAR_PLANES
:;
1007 // This plane passed all checks so we can add it to the current solid
1009 solid
[ solid_len
++ ] = loop
->poly_right
;
1010 faces_tagged
[ loop
->poly_right
] = i
;
1018 search_start
= solid_len
;
1020 goto IL_SEARCH_CONTINUE
;
1023 struct csolid
*csolid
= &candidates
[candidate_count
++];
1024 csolid
->start
= solid_buffer_len
;
1025 csolid
->count
= solid_len
;
1026 csolid
->edge_count
= 0;
1028 v3_zero( csolid
->center
);
1029 for( int j
=0; j
<solid_len
; j
++ )
1031 struct cxr_polygon
*polyj
= cxr_ab_ptr(&mesh
->polys
, solid
[j
]);
1032 v3_add( polyj
->center
, csolid
->center
, csolid
->center
);
1033 csolid
->edge_count
+= polyj
->loop_total
;
1035 v3_divs( csolid
->center
, solid_len
, csolid
->center
);
1037 solid_buffer_len
+= solid_len
;
1040 // Create all candidates who have one or less non-manifolds edges
1041 // Loop each candidate, determine the manifold, and pick the best one
1043 struct csolid
*best_solid
= NULL
;
1044 int fewest_manifold_splits
= INT32_MAX
;
1046 struct cxr_loop
*best_manifold
= malloc( mesh
->loops
.count
*sizeof(struct cxr_loop
) );
1047 int *best_manifold_splits
= malloc( mesh
->loops
.count
*sizeof(int) );
1048 int best_manifold_len
= 0;
1049 int max_solid_faces
= 0;
1051 int *edge_list
= malloc( mesh
->edges
.count
*sizeof(int) );
1052 int *edge_lefts
= malloc( mesh
->edges
.count
*sizeof(int) );
1053 struct cxr_loop
*manifold
= malloc(mesh
->edges
.count
*2*sizeof(struct cxr_loop
));
1054 int *splits
= malloc(mesh
->edges
.count
*2*sizeof(int));
1056 for( int i
=0; i
<candidate_count
; i
++ )
1058 struct csolid
*solid
= &candidates
[i
];
1059 max_solid_faces
= cxr_max(max_solid_faces
,solid
->count
);
1061 if( solid
->count
<= 2 )
1064 int init_reverse
= 0;
1065 int unique_edge_count
= 0;
1067 for( int j
=0; j
<solid
->count
; j
++ )
1069 struct cxr_polygon
*poly
= cxr_ab_ptr(&mesh
->polys
, solid_buffer
[solid
->start
+j
]);
1071 for( int k
=0; k
<poly
->loop_total
; k
++ )
1073 struct cxr_loop
*loop
= cxr_ab_ptr(&mesh
->loops
, poly
->loop_start
+k
);
1075 for( int l
=0; l
<unique_edge_count
; l
++ )
1076 if( edge_list
[l
] == loop
->edge_index
)
1077 goto IL_EDGE_ALREADY_PRESENT
;
1079 // Check if right edge references a polygon that is not
1080 // present inside the current solid candidate
1081 for( int l
=0; l
<solid
->count
; l
++ )
1082 if( loop
->poly_right
== solid_buffer
[solid
->start
+l
] )
1083 goto IL_EDGE_ALREADY_PRESENT
;
1085 edge_list
[ unique_edge_count
] = loop
->edge_index
;
1086 edge_lefts
[ unique_edge_count
] = loop
->poly_left
;
1088 if( unique_edge_count
== 0 )
1090 struct cxr_edge
*edgeptr
= cxr_ab_ptr(&mesh
->edges
, loop
->edge_index
);
1091 if( edgeptr
->i1
== loop
->index
)
1095 unique_edge_count
++;
1096 IL_EDGE_ALREADY_PRESENT
:;
1100 // This solid is already fully connected
1101 if( unique_edge_count
== 0 )
1104 // Link edges together to create new manifold
1105 // Corners are created when two edges share a polygon face
1106 // This way we can split it into regions
1108 for( int j
=0; j
<vert_buffer
->count
; j
++ )
1109 vertex_tagged
[j
] = -1;
1111 // Start with a loop edge which was tagged
1112 struct cxr_edge
*current
= cxr_ab_ptr(&mesh
->edges
, edge_list
[0]);
1114 int endpt
= (!init_reverse
)? current
->i0
: current
->i1
,
1116 curface
= edge_lefts
[0];
1118 int manifold_len
= 0;
1119 int split_count
= 0;
1121 IL_MANIFOLD_CONTINUE
:
1122 for( int j
=0; j
<unique_edge_count
; j
++ )
1124 struct cxr_edge
*other
= cxr_ab_ptr(&mesh
->edges
, edge_list
[j
]);
1125 if( other
== current
)
1128 if( other
->i0
== endpt
|| other
->i1
== endpt
)
1133 if( other
->i0
== endpt
) endpt
= current
->i1
;
1134 else endpt
= current
->i0
;
1136 if( curface
==edge_lefts
[j
] )
1138 splits
[ manifold_len
] = 1;
1142 splits
[ manifold_len
] = 0;
1144 // Append to intermidiary manifold
1145 manifold
[ manifold_len
].edge_index
= edge_list
[j
];
1146 manifold
[ manifold_len
].poly_left
= edge_lefts
[j
];
1147 manifold
[ manifold_len
].index
= lastpt
;
1148 manifold
[ manifold_len
].poly_right
=
1149 polygon_edge_map
[ edge_list
[j
]*2 ] == edge_lefts
[j
]?
1150 polygon_edge_map
[ edge_list
[j
]*2+1 ]:
1151 polygon_edge_map
[ edge_list
[j
]*2+0 ];
1154 curface
= edge_lefts
[j
];
1156 if(endpt
== start
) goto IL_MANIFOLD_COMPLETE
;
1157 goto IL_MANIFOLD_CONTINUE
;
1160 cxr_log( "Failed to link manifold, count: %d\n", manifold_len
);
1162 for( int j
=0; j
<solid
->count
; j
++ )
1164 cxr_log( "p%d\n", solid_buffer
[solid
->start
+j
] );
1165 struct cxr_polygon
*poly
= cxr_ab_ptr(&mesh
->polys
, solid_buffer
[solid
->start
+j
]);
1166 cxr_debug_poly( mesh
, poly
, vertices
, (v4f
){0.2,0.0,0.0,1.0} );
1169 for( int j
=0; j
<unique_edge_count
; j
++ )
1171 struct cxr_edge
*uedge
= cxr_ab_ptr(&mesh
->edges
, edge_list
[j
]);
1172 cxr_debug_line(vertices
[uedge
->i0
],vertices
[uedge
->i1
],(v4f
){0.4,0.0,0.0,1.0});
1175 for( int j
=0; j
<manifold_len
-1; j
++ )
1177 struct cxr_loop
*lp0
= &manifold
[j
],
1178 *lp1
= &manifold
[cxr_range(j
+1,manifold_len
)];
1180 cxr_debug_line(vertices
[lp0
->index
],vertices
[lp1
->index
], colour_error
);
1183 cxr_debug_mesh( mesh
, vertices
, (v4f
){0.0,0.0,0.0, 0.9} );
1184 *error
= CXR_ERROR_BAD_MANIFOLD
;
1191 free(vertex_tagged
);
1196 free(best_manifold
);
1197 free(best_manifold_splits
);
1198 free(polygon_edge_map
);
1201 IL_MANIFOLD_COMPLETE
:;
1203 if( manifold_len
< unique_edge_count
)
1207 if( split_count
< fewest_manifold_splits
)
1209 fewest_manifold_splits
= split_count
;
1212 for( int j
=0; j
<manifold_len
; j
++ )
1214 best_manifold
[j
] = manifold
[j
];
1215 best_manifold_splits
[j
] = splits
[j
];
1217 best_manifold_len
= manifold_len
;
1227 if( max_solid_faces
< 2 )
1229 *error
= CXR_ERROR_NO_SOLIDS
;
1231 free(vertex_tagged
);
1236 free(best_manifold
);
1237 free(best_manifold_splits
);
1238 free(polygon_edge_map
);
1242 if( best_solid
!= NULL
)
1244 struct cxr_mesh
*pullmesh
=
1245 cxr_alloc_mesh( best_solid
->edge_count
, best_solid
->edge_count
, best_solid
->count
);
1247 // Add existing faces to pullsolid, and delete from main mesh
1248 for( int i
=0; i
<best_solid
->count
; i
++ )
1250 int nface_id
= pullmesh
->polys
.count
;
1252 struct cxr_polygon
*exist_face
= cxr_ab_ptr(&mesh
->polys
, solid_buffer
[best_solid
->start
+i
]);
1253 struct cxr_polygon
*new_face
= cxr_ab_empty(&pullmesh
->polys
);
1255 *new_face
= *exist_face
;
1256 new_face
->loop_start
= pullmesh
->loops
.count
;
1258 for( int j
=0; j
<exist_face
->loop_total
; j
++ )
1260 struct cxr_loop
*exist_loop
= cxr_ab_ptr(&mesh
->loops
, exist_face
->loop_start
+j
);
1261 struct cxr_loop
*new_loop
= cxr_ab_empty(&pullmesh
->loops
);
1263 new_loop
->index
= exist_loop
->index
;
1264 new_loop
->poly_left
= nface_id
;
1265 new_loop
->poly_right
= -1;
1266 new_loop
->edge_index
= 0;
1267 v2_copy( exist_loop
->uv
, new_loop
->uv
);
1270 exist_face
->loop_total
= -1;
1273 // Split manifold up by unique planes if it has more than 1
1274 // otherwise, just use that face
1276 // TODO: Need to build new manifold in sections, stably
1277 // currently there is an unsupported case where the manifold splits
1278 // are on located on an implicit face, causing 1-length manifolds.
1281 int pullmesh_new_start
= pullmesh
->polys
.count
;
1283 if( fewest_manifold_splits
!= 0 )
1285 #if CXR_MANIFOLD_DEBUG
1286 for( int i
=0; i
<best_manifold_len
; i
++ )
1289 i1
= cxr_range(i
+1,best_manifold_len
);
1291 cxr_debug_line( vertices
[best_manifold
[i0
].index
], vertices
[best_manifold
[i1
].index
], colour_error
);
1292 if( best_manifold_splits
[i
] )
1293 cxr_debug_box( vertices
[best_manifold
[i0
].index
], 0.04, colour_success
);
1297 // This is a really strange observation, however it *seems* to apply to the kinds
1298 // of geometry we are dealing with. If the split count is odd, the manifold can be
1299 // created easily, no folding required.
1301 // When it is even, it appears that internal implicit geometry is required, so we
1302 // need to fold the loops we create. Its really weird, but for some reason works on
1303 // the geometry rules we've defined.
1304 // TODO: Find a well defined rule here.
1306 int collapse_used_segments
= (u32
)fewest_manifold_splits
& 0x1? 0: 1;
1308 IL_MANIFOLD_BUILD_REPEAT
:
1310 for( int j
=0; j
<best_manifold_len
; j
++ )
1312 if( best_manifold_splits
[j
] )
1314 struct cxr_loop
*loop
= &best_manifold
[j
];
1316 for( int k
=1; k
<best_manifold_len
; k
++ )
1318 int index1
= cxr_range(j
+k
,best_manifold_len
);
1319 struct cxr_loop
*loop1
= &best_manifold
[index1
];
1321 if( best_manifold_splits
[index1
] )
1328 if( new_polys
> best_manifold_len
)
1330 cxr_log( "Programming error: Too many new polys!\n" );
1334 cxr_create_poly( pullmesh
, vertices
, best_manifold
, k
+1, j
, best_manifold_len
);
1336 // Remove new section from manifold
1337 if( collapse_used_segments
)
1339 best_manifold_splits
[j
] = 0;
1340 best_manifold_splits
[index1
] = 0;
1342 int new_length
= (best_manifold_len
-(k
-1));
1344 struct cxr_loop
*new_manifold
= malloc( new_length
*sizeof(struct cxr_loop
) );
1345 int *new_manifold_splits
= malloc( new_length
*sizeof(int) );
1347 for( int l
=0; l
<new_length
; l
++ )
1349 int i_src
= cxr_range( j
+k
+l
, best_manifold_len
);
1350 new_manifold
[l
] = best_manifold
[i_src
];
1351 new_manifold_splits
[l
] = best_manifold_splits
[i_src
];
1354 free( best_manifold
);
1355 free( best_manifold_splits
);
1356 best_manifold
= new_manifold
;
1357 best_manifold_splits
= new_manifold_splits
;
1359 best_manifold_len
= new_length
;
1361 goto IL_MANIFOLD_BUILD_REPEAT
;
1371 if( best_manifold_len
&& collapse_used_segments
)
1373 cxr_create_poly( pullmesh
, vertices
, best_manifold
, best_manifold_len
, 0, best_manifold_len
);
1379 cxr_create_poly( pullmesh
, vertices
, best_manifold
, best_manifold_len
, 0, best_manifold_len
);
1383 // vert_buffer may be reallocated by the next section of code,
1384 // force a NULLref on vertices to catch any errors
1387 // Implicit geometry reconstruction
1388 // If there's 3 or more planes, collide them together to see if any new
1389 // vertices need to be created on the mesh
1390 if( new_polys
>= 3 )
1392 for( int i
=0; i
<new_polys
-2; i
++ )
1394 for( int j
=i
+1; j
<new_polys
-1; j
++ )
1396 for( int k
=j
+1; k
<new_polys
; k
++ )
1398 struct cxr_polygon
*ptri
= cxr_ab_ptr( &pullmesh
->polys
, pullmesh_new_start
+i
),
1399 *ptrj
= cxr_ab_ptr( &pullmesh
->polys
, pullmesh_new_start
+j
),
1400 *ptrk
= cxr_ab_ptr( &pullmesh
->polys
, pullmesh_new_start
+k
);
1402 v4f planei
, planej
, planek
;
1403 normal_to_plane(ptri
->normal
,ptri
->center
,planei
);
1404 normal_to_plane(ptrj
->normal
,ptrj
->center
,planej
);
1405 normal_to_plane(ptrk
->normal
,ptrk
->center
,planek
);
1409 if( plane_intersect(planei
,planej
,planek
,intersect
) )
1411 // cxr_debug_box( intersect, 0.05, colour_error );
1413 // Make sure this point is within the convex region, otherwise treat
1414 // it as a degenerate case
1416 int point_valid
= 1;
1417 for( int l
=0; l
<pullmesh
->polys
.count
; l
++ )
1419 struct cxr_polygon
*ptrl
= cxr_ab_ptr(&pullmesh
->polys
,l
);
1422 normal_to_plane(ptrl
->normal
, ptrl
->center
, planel
);
1424 if( plane_polarity( planel
, intersect
) > 0.01 )
1426 cxr_log( "degen vert, planes %d, %d, %d [max:%d]\n", i
,j
,k
, new_polys
);
1427 *error
= CXR_ERROR_DEGEN_IMPLICIT
;
1429 cxr_debug_poly( pullmesh
, ptri
, cxr_ab_ptr(vert_buffer
,0), colours_random
[3] );
1430 cxr_debug_poly( pullmesh
, ptrj
, cxr_ab_ptr(vert_buffer
,0), colours_random
[1] );
1431 cxr_debug_poly( pullmesh
, ptrk
, cxr_ab_ptr(vert_buffer
,0), colours_random
[2] );
1438 if( !point_valid
) continue;
1440 // Extend faces to include this point
1441 int nvertid
= vert_buffer
->count
;
1442 cxr_ab_push( vert_buffer
, intersect
);
1444 ptrj
->loop_start
+= 1;
1445 ptrk
->loop_start
+= 2;
1447 cxr_ab_reserve(&pullmesh
->loops
, 3);
1448 struct cxr_loop
*lloopi
= cxr_ab_empty_at(&pullmesh
->loops
, ptri
->loop_start
+ptri
->loop_total
),
1449 *lloopj
= cxr_ab_empty_at(&pullmesh
->loops
, ptrj
->loop_start
+ptrj
->loop_total
),
1450 *lloopk
= cxr_ab_empty_at(&pullmesh
->loops
, ptrk
->loop_start
+ptrk
->loop_total
);
1452 lloopi
->index
= nvertid
;
1453 lloopj
->index
= nvertid
;
1454 lloopk
->index
= nvertid
;
1455 lloopi
->edge_index
= 0; lloopj
->edge_index
= 0; lloopk
->edge_index
= 0;
1456 lloopi
->poly_left
= pullmesh_new_start
+i
;
1457 lloopj
->poly_left
= pullmesh_new_start
+j
;
1458 lloopk
->poly_left
= pullmesh_new_start
+k
;
1459 lloopi
->poly_right
= -1; lloopj
->poly_right
= -1; lloopk
->poly_right
= -1;
1461 v2_zero(lloopi
->uv
);
1462 v2_zero(lloopj
->uv
);
1463 v2_zero(lloopk
->uv
);
1465 ptri
->loop_total
++;
1466 ptrj
->loop_total
++;
1467 ptrk
->loop_total
++;
1469 // Adjust centers of faces
1470 v3_lerp( ptri
->center
, intersect
, 1.0/(double)ptri
->loop_total
, ptri
->center
);
1471 v3_lerp( ptrj
->center
, intersect
, 1.0/(double)ptrj
->loop_total
, ptrj
->center
);
1472 v3_lerp( ptrk
->center
, intersect
, 1.0/(double)ptrk
->loop_total
, ptrk
->center
);
1479 // Copy faces from pullsolid into orig mesh
1481 for( int i
=0; i
<new_polys
; i
++ )
1483 int rface_id
= mesh
->polys
.count
;
1485 struct cxr_polygon
*pface
= cxr_ab_ptr(&pullmesh
->polys
,pullmesh_new_start
+i
);
1486 struct cxr_polygon
*rip_face
= cxr_ab_empty(&mesh
->polys
);
1488 rip_face
->loop_start
= mesh
->loops
.count
;
1489 rip_face
->loop_total
= pface
->loop_total
;
1490 rip_face
->material_id
= -1;
1492 for( int j
=0; j
<rip_face
->loop_total
; j
++ )
1494 struct cxr_loop
*ploop
= cxr_ab_ptr(&pullmesh
->loops
, pface
->loop_start
+pface
->loop_total
-j
-1),
1495 *rloop
= cxr_ab_empty(&mesh
->loops
);
1497 rloop
->index
= ploop
->index
;
1498 rloop
->poly_left
= rface_id
;
1499 rloop
->poly_right
= -1;
1500 rloop
->edge_index
= 0;
1501 v2_copy( ploop
->uv
, rloop
->uv
);
1504 v3_copy( pface
->center
, rip_face
->center
);
1505 v3_negate( pface
->normal
, rip_face
->normal
);
1508 cxr_mesh_clean_faces( mesh
);
1509 cxr_mesh_clean_faces( pullmesh
);
1510 cxr_mesh_clean_edges( mesh
);
1511 cxr_mesh_clean_edges( pullmesh
);
1514 free(vertex_tagged
);
1519 free(best_manifold
);
1520 free(best_manifold_splits
);
1521 free(polygon_edge_map
);
1527 free(vertex_tagged
);
1532 free(best_manifold
);
1533 free(best_manifold_splits
);
1534 free(polygon_edge_map
);
1539 static struct cxr_mesh
*cxr_to_internal_format(struct cxr_input_mesh
*src
, struct cxr_auto_buffer
*abverts
)
1541 // Split mesh into islands
1542 struct cxr_mesh
*mesh
= cxr_alloc_mesh( src
->edge_count
, src
->loop_count
, src
->poly_count
);
1543 cxr_ab_init( abverts
, sizeof(v3f
), src
->vertex_count
);
1545 // Copy input data into working mesh
1546 memcpy( cxr_ab_ptr( &mesh
->edges
, 0 ), src
->edges
, src
->edge_count
*sizeof(struct cxr_edge
));
1547 memcpy( cxr_ab_ptr( &mesh
->polys
, 0 ), src
->polys
, src
->poly_count
*sizeof(struct cxr_polygon
));
1548 memcpy( cxr_ab_ptr( abverts
, 0 ), src
->vertices
, src
->vertex_count
*sizeof(v3f
));
1549 mesh
->edges
.count
= src
->edge_count
;
1550 mesh
->loops
.count
= src
->loop_count
;
1551 mesh
->polys
.count
= src
->poly_count
;
1553 for( int i
=0; i
<src
->loop_count
; i
++ )
1555 struct cxr_loop
*lp
= cxr_ab_ptr(&mesh
->loops
,i
);
1556 lp
->index
= src
->loops
[i
].index
;
1557 lp
->edge_index
= src
->loops
[i
].edge_index
;
1558 v2_copy( src
->loops
[i
].uv
, lp
->uv
);
1561 abverts
->count
= src
->vertex_count
;
1566 // Find farthest dot product along direction
1567 static double support_distance( v3f verts
[3], v3f dir
, double coef
)
1571 coef
* v3_dot( verts
[0], dir
),
1574 coef
* v3_dot( verts
[1], dir
),
1575 coef
* v3_dot( verts
[2], dir
)
1581 static void cxr_calculate_axis(
1582 struct cxr_texinfo
*transform
,
1588 v2f tT
, bT
; // Tangent/bitangent pairs for UV space and world
1591 v2_sub( uvs
[0], uvs
[1], tT
);
1592 v2_sub( uvs
[2], uvs
[1], bT
);
1593 v3_sub( verts
[0], verts
[1], tW
);
1594 v3_sub( verts
[2], verts
[1], bW
);
1596 // Use arbitrary projection if there is no UV
1597 if( v2_length( tT
) < 0.0001 || v2_length( bT
) < 0.0001 )
1599 v3f uaxis
, normal
, vaxis
;
1601 v3_copy( tW
, uaxis
);
1602 v3_normalize( uaxis
);
1604 v3_cross( tW
, bW
, normal
);
1605 v3_cross( normal
, uaxis
, vaxis
);
1606 v3_normalize( vaxis
);
1608 v3_copy( uaxis
, transform
->uaxis
);
1609 v3_copy( vaxis
, transform
->vaxis
);
1610 v2_zero( transform
->offset
);
1612 v2_div( (v2f
){128.0, 128.0}, texture_res
, transform
->scale
);
1613 transform
->winding
= 1.0;
1617 // Detect if UV is reversed
1618 double winding
= v2_cross( tT
, bT
) >= 0.0f
? 1.0f
: -1.0f
;
1620 // UV projection reference
1622 v2_muls((v2f
){1,0}, winding
, vX
);
1623 v2_muls((v2f
){0,1}, winding
, vY
);
1625 // Reproject reference into world space, including skew
1628 v3_muls( tW
, v2_cross(vX
,bT
) / v2_cross(bT
,tT
), uaxis1
);
1629 v3_muladds( uaxis1
, bW
, v2_cross(vX
, tT
) / v2_cross(tT
,bT
), uaxis1
);
1631 v3_muls( tW
, v2_cross(vY
,bT
) / v2_cross(bT
,tT
), vaxis1
);
1632 v3_muladds( vaxis1
, bW
, v2_cross(vY
,tT
) / v2_cross(tT
,bT
), vaxis1
);
1634 v3_normalize( uaxis1
);
1635 v3_normalize( vaxis1
);
1637 // Apply source transform to axis (yes, they also need to be swapped)
1638 v3f norm
, uaxis
, vaxis
;
1640 v3_cross( bW
, tW
, norm
);
1642 v3_cross( vaxis1
, norm
, uaxis
);
1643 v3_cross( uaxis1
, norm
, vaxis
);
1646 v2f uvmin
, uvmax
, uvdelta
;
1647 v2_minv( uvs
[0], uvs
[1], uvmin
);
1648 v2_minv( uvmin
, uvs
[2], uvmin
);
1649 v2_maxv( uvs
[0], uvs
[1], uvmax
);
1650 v2_maxv( uvmax
, uvs
[2], uvmax
);
1652 v2_sub( uvmax
, uvmin
, uvdelta
);
1655 v2f uvminw
, uvmaxw
, uvdeltaw
;
1656 uvminw
[0] = -support_distance( verts
, uaxis
, -1.0f
);
1657 uvmaxw
[0] = support_distance( verts
, uaxis
, 1.0f
);
1658 uvminw
[1] = -support_distance( verts
, vaxis
, -1.0f
);
1659 uvmaxw
[1] = support_distance( verts
, vaxis
, 1.0f
);
1661 v2_sub( uvmaxw
, uvminw
, uvdeltaw
);
1665 v2_div( uvdeltaw
, uvdelta
, uv_scale
);
1666 v2_div( uv_scale
, texture_res
, uv_scale
);
1668 // Find offset via 'natural' point
1669 v2f target_uv
, natural_uv
, tex_offset
;
1670 v2_mul( uvs
[0], texture_res
, target_uv
);
1672 natural_uv
[0] = v3_dot( uaxis
, verts
[0] );
1673 natural_uv
[1] = -v3_dot( vaxis
, verts
[0] );
1674 v2_div( natural_uv
, uv_scale
, natural_uv
);
1676 tex_offset
[0] = target_uv
[0]-natural_uv
[0];
1677 tex_offset
[1] = -(target_uv
[1]-natural_uv
[1]);
1679 // Copy everything into output
1680 v3_copy( uaxis
, transform
->uaxis
);
1681 v3_copy( vaxis
, transform
->vaxis
);
1682 v2_copy( tex_offset
, transform
->offset
);
1683 v2_copy( uv_scale
, transform
->scale
);
1684 transform
->winding
= winding
;
1687 CXR_API
struct cxr_input_mesh
*cxr_decompose(struct cxr_input_mesh
*src
)
1689 #ifdef CXR_DEBUG_WRITE_MESH
1690 FILE *yeet
= fopen( "/home/harry/Documents/blender_addons_remote/addons/convexer/solid.h", "w" );
1692 fprintf( yeet
, "v3f test_verts[] = {\n" );
1693 for( int i
=0; i
<src
->vertex_count
; i
++ )
1695 fprintf( yeet
, " { %f, %f, %f },\n",
1696 src
->vertices
[i
][0],
1697 src
->vertices
[i
][1],
1698 src
->vertices
[i
][2] );
1700 fprintf( yeet
, "};\n" );
1702 fprintf( yeet
, "struct cxr_input_loop test_loops[] = {\n" );
1703 for( int i
=0; i
<src
->loop_count
; i
++ )
1705 fprintf( yeet
, " {%d, %d},\n",
1706 src
->loops
[i
].index
,
1707 src
->loops
[i
].edge_index
);
1709 fprintf( yeet
, "};\n" );
1711 fprintf( yeet
, "struct cxr_polygon test_polys[] = {\n" );
1712 for( int i
=0; i
<src
->poly_count
; i
++ )
1714 fprintf( yeet
, " {%d, %d, {%f, %f, %f}, {%f, %f, %f}},\n",
1715 src
->polys
[i
].loop_start
,
1716 src
->polys
[i
].loop_total
,
1717 src
->polys
[i
].normal
[0],
1718 src
->polys
[i
].normal
[1],
1719 src
->polys
[i
].normal
[2],
1720 src
->polys
[i
].center
[0],
1721 src
->polys
[i
].center
[1],
1722 src
->polys
[i
].center
[2] );
1724 fprintf( yeet
, "};\n" );
1726 fprintf( yeet
, "struct cxr_edge test_edges[] = {\n" );
1727 for( int i
=0; i
<src
->edge_count
; i
++ )
1729 fprintf( yeet
, " {%d, %d},\n",
1734 fprintf( yeet
, "};\n" );
1736 fprintf( yeet
, "struct cxr_input_mesh test_mesh = {\n" );
1737 fprintf( yeet
, " .vertices = test_verts,\n" );
1738 fprintf( yeet
, " .loops = test_loops,\n" );
1739 fprintf( yeet
, " .edges = test_edges,\n" );
1740 fprintf( yeet
, " .polys = test_polys,\n" );
1741 fprintf( yeet
, " .poly_count=%d,\n", src
->poly_count
);
1742 fprintf( yeet
, " .vertex_count=%d,\n", src
->vertex_count
);
1743 fprintf( yeet
, " .edge_count=%d,\n",src
->edge_count
);
1744 fprintf( yeet
, " .loop_count=%d\n", src
->loop_count
);
1745 fprintf( yeet
, "};\n" );
1750 struct cxr_auto_buffer abverts
;
1751 struct cxr_mesh
*main_mesh
= cxr_to_internal_format( src
, &abverts
);
1755 struct cxr_auto_buffer solids
;
1756 cxr_ab_init( &solids
, sizeof(struct cxr_mesh
*), 2 );
1758 // TODO: Preprocessor stages
1759 // - Split mesh up into islands before doing anything here
1760 // - Snap vertices to grid (0.25u) ?
1763 struct cxr_mesh
*res
= cxr_pull_best_solid( main_mesh
, &abverts
, 0, &error
);
1766 cxr_ab_push( &solids
, &res
);
1773 // If no solids error we can rety while preserving 'hot' edges
1775 if( error
& CXR_ERROR_NO_SOLIDS
)
1778 res
= cxr_pull_best_solid(main_mesh
, &abverts
, 1, &error
);
1780 if( res
) cxr_ab_push( &solids
, &res
);
1792 cxr_ab_push( &solids
, &main_mesh
);
1796 for( int i
=0; i
<solids
.count
; i
++ )
1798 struct cxr_mesh
**mptr
= cxr_ab_ptr(&solids
,i
);
1799 cxr_debug_mesh( *mptr
, cxr_ab_ptr(&abverts
,0), colours_random
[cxr_range(i
,8)] );
1803 for( int i
=0; i
<solids
.count
; i
++ )
1805 struct cxr_mesh
**mptr
= cxr_ab_ptr(&solids
,i
);
1806 cxr_free_mesh( *mptr
);
1809 cxr_ab_free( &abverts
);
1810 cxr_ab_free( &solids
);
1815 static int cxr_cardinal( v3f a
, int ignore
)
1818 double component_max
= -CXR_BIG_NUMBER
;
1820 for( int i
=0; i
<3; i
++ )
1822 if( i
== ignore
) continue;
1824 if( fabs(a
[i
]) > component_max
)
1826 component_max
= fabs(a
[i
]);
1830 double d
= a
[component
] >= 0.0? 1.0: -1.0;
1837 // Convert contiguous mesh to patch of displacments
1839 static void cxr_write_disp(struct cxr_mesh
*mesh
, struct cxr_input_mesh
*inputmesh
,
1840 struct cxr_vdf
*output
,
1841 struct cxr_auto_buffer
*abverts
)
1843 // Create a graph which maps vertices by their connections
1846 int con_start
, con_count
; // Index into the connection graph
1854 *vertinfo
= malloc( sizeof(struct vertinfo
)*abverts
->count
);
1855 int *graph
= malloc( sizeof(int) * mesh
->edges
.count
*2 );
1858 for( int i
=0; i
<abverts
->count
; i
++ )
1860 struct vertinfo
*info
= &vertinfo
[i
];
1861 info
->con_start
= con_pos
;
1862 info
->con_count
= 0;
1869 for( int j
=0; j
<mesh
->edges
.count
; j
++ )
1871 struct cxr_edge
*edge
= cxr_ab_ptr(&mesh
->edges
,j
);
1873 if( edge
->i0
== i
|| edge
->i1
== i
)
1875 graph
[ con_pos
++ ] = edge
->i0
== i
? edge
->i1
: edge
->i0
;
1878 if( edge
->freestyle
)
1884 // Find best normal for brush patch. VBSP uses the original brush
1885 // as reference for decal projection.
1887 // These are clamped to be cardinal directions as to make the VMF somewhat
1890 v3f avg_normal
, refv
, refu
, refn
;
1891 v3_zero(refv
); v3_zero(refu
); v3_zero(refn
);
1893 for( int i
=0; i
<mesh
->polys
.count
; i
++ )
1895 struct cxr_polygon
*poly
= cxr_ab_ptr( &mesh
->polys
, i
);
1896 v3_add( poly
->normal
, avg_normal
, avg_normal
);
1898 v3_divs( avg_normal
, mesh
->polys
.count
, avg_normal
);
1899 v3_normalize( avg_normal
); // TODO: This can be zero length. Should add a safety check
1900 // normalize function that checks for small length before
1901 // carrying out, otherwise we get inf/nan values...
1902 int n_cardinal
= cxr_cardinal( avg_normal
, -1 );
1904 // Approximately matching the area of the result brush faces to the actual area
1905 // this is to assign a 'best guess' amount of lightmap texels.
1907 double uv_area
= 0.0, face_area
= 0.0, sf
;
1908 v2f uvboundmin
, uvboundmax
;
1909 v3f faceboundmin
, faceboundmax
;
1913 v2_fill( uvboundmin
, CXR_BIG_NUMBER
);
1914 v2_fill( uvboundmax
, -CXR_BIG_NUMBER
);
1915 v3_fill( faceboundmin
, CXR_BIG_NUMBER
);
1916 v3_fill( faceboundmax
, -CXR_BIG_NUMBER
);
1918 for( int i
=0; i
<mesh
->polys
.count
; i
++ )
1920 struct cxr_polygon
*poly
= cxr_ab_ptr( &mesh
->polys
, i
);
1922 for( int j
=0; j
<poly
->loop_total
; j
++ )
1924 struct cxr_loop
*lp0
= cxr_ab_ptr(&mesh
->loops
, poly
->loop_start
+j
);
1925 v2_minv( lp0
->uv
, uvboundmin
, uvboundmin
);
1926 v2_maxv( lp0
->uv
, uvboundmax
, uvboundmax
);
1927 v3_minv( cxr_ab_ptr(abverts
,lp0
->index
), faceboundmin
, faceboundmin
);
1928 v3_maxv( cxr_ab_ptr(abverts
,lp0
->index
), faceboundmax
, faceboundmax
);
1931 for( int j
=0; j
<poly
->loop_total
-2; j
++ )
1933 struct cxr_loop
*lp0
= cxr_ab_ptr(&mesh
->loops
, poly
->loop_start
),
1934 *lp1
= cxr_ab_ptr(&mesh
->loops
, poly
->loop_start
+j
+1),
1935 *lp2
= cxr_ab_ptr(&mesh
->loops
, poly
->loop_start
+j
+2);
1937 v3_sub( cxr_ab_ptr(abverts
,lp1
->index
), cxr_ab_ptr(abverts
,lp0
->index
), va
);
1938 v3_sub( cxr_ab_ptr(abverts
,lp2
->index
), cxr_ab_ptr(abverts
,lp0
->index
), vb
);
1939 v3_cross( va
, vb
, orth
);
1941 face_area
+= v3_length( orth
) / 2.0;
1944 v2_sub( lp1
->uv
, lp0
->uv
, uva
);
1945 v2_sub( lp2
->uv
, lp0
->uv
, uvb
);
1947 uv_area
+= fabs(v2_cross( uva
, uvb
)) / 2.0;
1951 v3_add( faceboundmax
, faceboundmin
, face_center
);
1952 v3_muls( face_center
, 0.5, face_center
);
1953 v2_add( uvboundmin
, uvboundmax
, uv_center
);
1954 v2_muls( uv_center
, 0.5, uv_center
);
1956 sf
= sqrt( face_area
/ uv_area
);
1957 int corner_count
= 0;
1959 // Vertex classification
1960 for( int i
=0; i
<abverts
->count
; i
++ )
1962 struct vertinfo
*info
= &vertinfo
[i
];
1963 if( !info
->boundary
) continue;
1968 for( int j
=0; j
<info
->con_count
; j
++ )
1970 int con
= graph
[info
->con_start
+j
];
1972 if( vertinfo
[con
].boundary
)
1977 if( count
> 2 || non_manifold
)
1982 //cxr_debug_box( cxr_ab_ptr(abverts,i), 0.1, colour_success );
1991 for( int i
=0; i
<mesh
->polys
.count
; i
++ )
1993 struct cxr_polygon
*basepoly
= cxr_ab_ptr(&mesh
->polys
,i
);
1995 for( int h
=0; h
<basepoly
->loop_total
; h
++ )
1998 i1
= cxr_range(h
+1,basepoly
->loop_total
);
2000 struct cxr_loop
*l0
= cxr_ab_ptr(&mesh
->loops
, basepoly
->loop_start
+i0
),
2001 *l1
= cxr_ab_ptr(&mesh
->loops
, basepoly
->loop_start
+i1
);
2002 struct vertinfo
*info
= &vertinfo
[ l0
->index
];
2006 int corner_count
= 1;
2008 struct cxr_material
*matptr
=
2009 basepoly
->material_id
< 0 || inputmesh
->material_count
== 0?
2011 &inputmesh
->materials
[ basepoly
->material_id
];
2014 dispedge
[0] = l0
->index
;
2015 dispedge
[1] = l1
->index
;
2016 v2_copy( l0
->uv
, corner_uvs
[0] );
2018 // Consume (remove) faces we use for corners
2019 basepoly
->loop_total
= -1;
2021 //cxr_debug_box( cxr_ab_ptr(abverts,l0->index),0.08,(v4f){0.0,0.0,1.0,1.0});
2024 // --------------------
2026 while( dispedge_count
< 17 )
2028 struct vertinfo
*edge_head
= &vertinfo
[dispedge
[dispedge_count
-1]];
2031 if( edge_head
->corner
)
2033 // Find a polygon that has the edge C-1 -> C
2034 for( int j
=0; j
<mesh
->polys
.count
&& !newvert
; j
++ )
2036 struct cxr_polygon
*poly
= cxr_ab_ptr(&mesh
->polys
,j
);
2038 for( int k
=0; k
<poly
->loop_total
; k
++ )
2041 i1
= cxr_range(k
+1,poly
->loop_total
);
2043 struct cxr_loop
*l0
= cxr_ab_ptr(&mesh
->loops
, poly
->loop_start
+i0
),
2044 *l1
= cxr_ab_ptr(&mesh
->loops
, poly
->loop_start
+i1
);
2046 if( l0
->index
== dispedge
[dispedge_count
-2] &&
2047 l1
->index
== dispedge
[dispedge_count
-1] )
2049 // Take the vertex after that edge
2050 v2_copy( l1
->uv
, corner_uvs
[corner_count
++] );
2052 int i2
= cxr_range(i1
+1,poly
->loop_total
);
2053 struct cxr_loop
*l2
= cxr_ab_ptr(&mesh
->loops
, poly
->loop_start
+i2
);
2055 dispedge
[dispedge_count
++] = l2
->index
;
2057 poly
->loop_total
= -1;
2065 for( int j
=0; j
<edge_head
->con_count
; j
++ )
2067 int con
= graph
[edge_head
->con_start
+j
];
2072 if( dispedge_count
> 1 )
2073 if( con
== dispedge
[dispedge_count
-2] )
2076 struct vertinfo
*coninfo
= &vertinfo
[con
];
2078 if( !coninfo
->boundary
)
2082 cxr_debug_arrow( cxr_ab_ptr(abverts,dispedge[dispedge_count-1]),
2083 cxr_ab_ptr(abverts,con),
2089 dispedge
[ dispedge_count
++ ] = con
;
2098 cxr_debug_box(cxr_ab_ptr(abverts
,dispedge
[dispedge_count
-1]), 0.1, colour_error
);
2103 // --------------------
2107 v2_sub( corner_uvs
[1], corner_uvs
[0], va
);
2108 v2_sub( corner_uvs
[2], corner_uvs
[0], vb
);
2110 // Connect up the grid
2118 // Example: a := common unused vertex that is connected to
2119 // by 1 and 15. Or y-1, and x-1 on the grid.
2120 // g := c and f common vert ^
2124 for( int j
=0; j
<5; j
++ ) grid
[j
] = dispedge
[j
];
2125 for( int j
=1; j
<5; j
++ ) grid
[j
*5+4] = dispedge
[j
+4];
2126 for( int j
=0; j
<4; j
++ ) grid
[4*5+3-j
] = dispedge
[j
+9];
2127 for( int j
=1; j
<4; j
++ ) grid
[j
*5] = dispedge
[16-j
];
2130 for( int j
=1; j
<4; j
++ )
2132 for( int k
=1; k
<4; k
++ )
2134 int s0
= grid
[(j
-1)*5+k
],
2137 struct vertinfo
*va
= &vertinfo
[s0
],
2138 *vb
= &vertinfo
[s1
];
2140 // Find a common vertex between s0 and s1
2142 for( int l
=0; l
<va
->con_count
; l
++ )
2144 for( int m
=0; m
<vb
->con_count
; m
++ )
2146 int cona
= graph
[va
->con_start
+l
],
2147 conb
= graph
[vb
->con_start
+m
];
2151 if( vertinfo
[cona
].used
|| vertinfo
[cona
].boundary
)
2154 grid
[ j
*5+k
] = cona
;
2155 vertinfo
[cona
].used
= 1;
2157 goto IL_MATCHED_DISP_INTERIOR_VERT
;
2162 // Broken displacement
2163 cxr_log( "Broken displacement!\n" );
2168 IL_MATCHED_DISP_INTERIOR_VERT
:;
2172 // Create brush vertices based on UV map
2174 // Create V reference based on first displacement.
2175 // TODO: This is not the moststable selection method!
2176 // faces can come in any order, so the first disp will of course
2177 // always vary. Additionaly the triangle can be oriented differently.
2179 // Improvement can be made by selecting a first disp/triangle based
2180 // on deterministic factors.
2182 if( disp_count
== 0 )
2184 struct cxr_texinfo tx
;
2186 v3_copy( cxr_ab_ptr(abverts
,dispedge
[0]), tri_ref
[0] );
2187 v3_copy( cxr_ab_ptr(abverts
,dispedge
[4]), tri_ref
[1] );
2188 v3_copy( cxr_ab_ptr(abverts
,dispedge
[8]), tri_ref
[2] );
2189 cxr_calculate_axis( &tx
, tri_ref
, corner_uvs
, (v2f
){512,512} );
2191 v3_muls( tx
.vaxis
, -1.0, refv
);
2192 int v_cardinal
= cxr_cardinal( refv
, -1 );
2194 v3_cross( tx
.vaxis
, tx
.uaxis
, refn
);
2195 v3_muls( refn
, -tx
.winding
, refn
);
2197 int n1_cardinal
= cxr_cardinal( refn
, v_cardinal
);
2199 //v3_copy( avg_normal, refn );
2201 if( u_cardinal
== n1_cardinal
|| u_cardinal
== v_cardinal
) u_cardinal
++;
2202 if( u_cardinal
== n1_cardinal
|| u_cardinal
== v_cardinal
) u_cardinal
++;
2205 refu
[u_cardinal
] = tx
.uaxis
[u_cardinal
] > 0.0? 1.0: -1.0;
2209 v3_copy( face_center
, p0
);
2210 v3_muladds( face_center
, refn
, 1.5, pn
);
2211 v3_muladds( face_center
, refv
, 1.5, pv
);
2212 v3_muladds( face_center
, refu
, 1.5, pu
);
2214 if( cxr_settings
.debug
)
2216 cxr_debug_line( p0
, pn
, (v4f
){0.0,0.0,1.0,1.0});
2217 cxr_debug_line( p0
, pv
, (v4f
){0.0,1.0,0.0,1.0});
2218 cxr_debug_line( p0
, pu
, (v4f
){1.0,0.0,0.0,1.0});
2219 cxr_debug_line( tri_ref
[0], tri_ref
[1], (v4f
){1.0,1.0,1.0,1.0} );
2220 cxr_debug_line( tri_ref
[1], tri_ref
[2], (v4f
){1.0,1.0,1.0,1.0} );
2221 cxr_debug_line( tri_ref
[2], tri_ref
[0], (v4f
){1.0,1.0,1.0,1.0} );
2225 // Create world cordinates
2226 v3f world_corners
[8];
2229 for( int j
=0; j
<4; j
++ )
2232 v2_sub( corner_uvs
[j
], uv_center
, local_uv
);
2233 v2_copy( corner_uvs
[j
], world_uv
[j
] );
2234 v2_muls( local_uv
, sf
, local_uv
);
2236 v3_muls( refu
, local_uv
[0], world_corners
[j
] );
2237 v3_muladds( world_corners
[j
], refv
, local_uv
[1], world_corners
[j
] );
2238 v3_add( face_center
, world_corners
[j
], world_corners
[j
] );
2241 double *colour
= colours_random
[cxr_range(disp_count
,8)];
2243 for( int j
=0; j
<4; j
++ )
2244 v3_muladds( world_corners
[j
], refn
, -1.0, world_corners
[j
+4] );
2246 if( cxr_settings
.debug
)
2248 cxr_debug_arrow( world_corners
[0], world_corners
[1], avg_normal
, 0.1, colour
);
2249 cxr_debug_arrow( world_corners
[1], world_corners
[2], avg_normal
, 0.1, colour
);
2250 cxr_debug_arrow( world_corners
[2], world_corners
[3], avg_normal
, 0.1, colour
);
2251 cxr_debug_arrow( world_corners
[3], world_corners
[0], avg_normal
, 0.1, colour
);
2255 cxr_debug_arrow( world_corners[0+4], world_corners[1+4], avg_normal, 0.1, colour );
2256 cxr_debug_arrow( world_corners[1+4], world_corners[2+4], avg_normal, 0.1, colour );
2257 cxr_debug_arrow( world_corners[2+4], world_corners[3+4], avg_normal, 0.1, colour );
2258 cxr_debug_arrow( world_corners[3+4], world_corners[0+4], avg_normal, 0.1, colour );
2261 // Apply world transform
2262 for( int j
=0; j
<8; j
++ )
2264 v3_muls( world_corners
[j
], cxr_context
.scale_factor
, world_corners
[j
] );
2265 world_corners
[j
][2] += cxr_context
.offset_z
;
2268 struct cxr_texinfo texinfo_shared
;
2269 cxr_calculate_axis( &texinfo_shared
, world_corners
, world_uv
,
2270 (v2f
){ matptr
->res
[0], matptr
->res
[1] } );
2273 cxr_vdf_node( output
, "solid" );
2274 cxr_vdf_ki32( output
, "id", ++ cxr_context
.brush_count
);
2285 double distances
[25];
2287 v3f lside0
, lside1
, lref
, vdelta
, vworld
;
2290 for( int j
=0; j
<5; j
++ )
2292 ty
= (double)j
/(double)(5-1);
2294 v3_lerp( world_corners
[0], world_corners
[3], ty
, lside0
);
2295 v3_lerp( world_corners
[1], world_corners
[2], ty
, lside1
);
2297 for( int k
=0; k
<5; k
++ )
2301 tx
= (double)k
/(double)(5-1);
2302 v3_lerp( lside0
, lside1
, tx
, lref
);
2303 v3_muls( cxr_ab_ptr(abverts
, grid
[index
]), cxr_context
.scale_factor
, vworld
);
2304 vworld
[2] += cxr_context
.offset_z
;
2306 v3_sub( vworld
, lref
, vdelta
);
2307 v3_copy( vdelta
, normals
[index
] );
2308 v3_normalize( normals
[index
] );
2309 distances
[index
] = v3_dot( vdelta
, normals
[index
] );
2313 for( int j
=0; j
<6; j
++ )
2315 int *side
= sides
[j
];
2317 cxr_vdf_node( output
, "side" );
2318 cxr_vdf_ki32( output
, "id", ++ cxr_context
.face_count
);
2319 cxr_vdf_plane( output
, "plane", world_corners
[side
[2]],
2320 world_corners
[side
[1]],
2321 world_corners
[side
[0]] );
2323 cxr_vdf_kv( output
, "material", matptr
->vmt_path
);
2325 cxr_vdf_kaxis( output
, "uaxis",
2326 texinfo_shared
.uaxis
,
2327 texinfo_shared
.offset
[0],
2328 texinfo_shared
.scale
[0] );
2329 cxr_vdf_kaxis( output
, "vaxis",
2330 texinfo_shared
.vaxis
,
2331 texinfo_shared
.offset
[1],
2332 texinfo_shared
.scale
[1] );
2334 cxr_vdf_kdouble( output
, "rotation", 0.0 );
2335 cxr_vdf_ki32( output
, "lightmapscale", cxr_settings
.lightmap_scale
);
2336 cxr_vdf_ki32( output
, "smoothing_groups", 0 );
2340 cxr_vdf_node( output
, "dispinfo" );
2341 cxr_vdf_ki32( output
, "power", 2 );
2342 cxr_vdf_kv3f( output
, "startposition", world_corners
[0] );
2343 cxr_vdf_ki32( output
, "flags", 0 );
2344 cxr_vdf_kdouble( output
, "elevation", 0.0 );
2345 cxr_vdf_ki32( output
, "subdiv", 0 );
2347 cxr_vdf_node( output
, "normals" );
2348 for( int k
=0; k
<5; k
++ )
2349 cxr_vdf_karrv3f( output
, "row", k
, &normals
[k
*5], 5 );
2350 cxr_vdf_edon( output
);
2352 cxr_vdf_node( output
, "distances" );
2353 for( int k
=0; k
<5; k
++ )
2354 cxr_vdf_karrdouble( output
, "row", k
, &distances
[k
*5], 5 );
2355 cxr_vdf_edon( output
);
2357 // TODO: This might be needed for compiling...
2359 cxr_vdf_node( output, "offsets" );
2360 for( int k=0; k<5; k++ )
2361 cxr_vdf_printf( output, "\"row%d\" \"0 0 0 0 0 0 0 0 0 0 0 0 0 0 0\"\n", k );
2362 cxr_vdf_edon( output );
2364 cxr_vdf_node( output, "offset_normals" );
2365 for( int k=0; k<5; k++ )
2366 cxr_vdf_printf( output, "\"row%d\" \"0 0 1 0 0 1 0 0 1 0 0 1 0 0 1\"\n", k );
2367 cxr_vdf_edon( output );
2369 cxr_vdf_node( output, "alphas" );
2370 for( int k=0; k<5; k++ )
2371 cxr_vdf_printf( output, "\"row%d\" \"0 0 0 0 0\"\n", k );
2372 cxr_vdf_edon( output );
2374 cxr_vdf_node( output, "triangle_tags" );
2375 for( int k=0; k<5-1; k++ )
2376 cxr_vdf_printf( output, "\"row%d\" \"9 9 9 9 9 9 9 9\"\n", k );
2377 cxr_vdf_edon( output );
2379 cxr_vdf_node( output, "allowed_verts" );
2380 cxr_vdf_printf( output, "\"10\" \"-1 -1 -1 -1 -1 -1 -1 -1 -1 -1\"\n" );
2381 cxr_vdf_edon( output );
2383 cxr_vdf_edon( output
);
2386 cxr_vdf_edon( output
);
2389 cxr_vdf_node(output
, "editor");
2390 cxr_vdf_colour255(output
,"color", colours_random
[cxr_range(cxr_context
.brush_count
,8)]);
2391 cxr_vdf_ki32(output
,"visgroupshown",1);
2392 cxr_vdf_ki32(output
,"visgroupautoshown",1);
2393 cxr_vdf_edon(output
);
2395 cxr_vdf_edon( output
);
2404 for( int i
=0; i
<abverts
->count
; i
++ )
2406 struct vertinfo
*info
= &vertinfo
[i
];
2407 if( info
->boundary
|| info
->used
)
2410 // Gather all vertices in this displacement
2419 int new_front_start
= poolcount
;
2421 for( int j
=0; j
<front_count
; j
++ )
2423 struct vertinfo
*frontvert
= &vertinfo
[pool
[front_start
+j
]];
2425 for( int k
=0; k
<frontvert
->con_count
; k
++ )
2427 int conid
= graph
[frontvert
->con_start
+k
];
2428 struct vertinfo
*con
= &vertinfo
[conid
];
2430 if( frontvert
->boundary
&& !con
->boundary
)
2436 if( poolcount
== 25 )
2437 goto IL_DISP_ERROR_COUNT
;
2440 pool
[ poolcount
++ ] = conid
;
2444 if( poolcount
> new_front_start
)
2446 front_start
= new_front_start
;
2447 front_count
= poolcount
-front_start
;
2449 goto IL_GATHER_LOOP
;
2452 if( poolcount
!= 25 )
2454 IL_DISP_ERROR_COUNT
:
2455 for( int i
=0; i
<poolcount
; i
++ )
2456 cxr_debug_box( cxr_ab_ptr(abverts
,pool
[i
]), 0.02, colour_error
);
2461 cxr_log("Invalid displacement (>25 verts)\n");
2466 int corner_count
= 0;
2467 struct cxr_loop
*cornerloops
[4];
2469 // Find corners, and get their loops (for uvs)
2470 // note: the mesh must be split where there is texture seams
2471 // so that two different uv'd loops cant ref the same vertex
2473 for( int j
=0; j
<poolcount
; j
++ )
2475 if( vertinfo
[pool
[j
]].corner
)
2477 if( corner_count
== 4 )
2483 corners
[corner_count
] = j
;
2485 // find loop that includes this vert
2486 for( int k
=0; k
<mesh
->loops
.count
; k
++ )
2488 struct cxr_loop
*lp
= cxr_ab_ptr(&mesh
->loops
,k
);
2489 if( lp
->index
== pool
[j
] )
2491 cornerloops
[corner_count
] = lp
;
2500 if( corner_count
!=4 )
2504 cxr_log( "Invalid displacement (!=4 corners)\n" );
2508 int pivot
= corners
[0];
2516 CXR_API i32
cxr_convert_mesh_to_vmf(struct cxr_input_mesh
*src
, struct cxr_vdf
*output
)
2518 // Split mesh into islands
2519 struct cxr_auto_buffer abverts
;
2520 struct cxr_mesh
*main_mesh
= cxr_to_internal_format(src
, &abverts
);
2526 struct cxr_mesh
*pmesh
;
2527 int is_displacement
;
2530 struct cxr_auto_buffer solids
;
2531 cxr_ab_init( &solids
, sizeof(struct solidinf
), 2 );
2533 // TODO: Preprocessor stages
2534 // - Split mesh up into islands before doing anything here (DONE)
2535 // - Snap vertices to grid (0.25u) ?
2537 // Preprocessor 1: Island seperation
2542 struct cxr_mesh
*res
= cxr_pull_island( main_mesh
);
2545 cxr_ab_push( &solids
, &(struct solidinf
){ res
, 0 });
2549 cxr_ab_push( &solids
, &(struct solidinf
){main_mesh
,0} );
2551 // Preprocessor 2: Displacement break-out
2553 for( int i
=0; i
<solids
.count
; i
++ )
2555 struct solidinf
*pinf
= cxr_ab_ptr(&solids
,i
);
2557 for( int j
=0; j
<pinf
->pmesh
->polys
.count
; j
++ )
2559 struct cxr_polygon
*poly
= cxr_ab_ptr( &pinf
->pmesh
->polys
, j
);
2561 for( int k
=0; k
<poly
->loop_total
; k
++ )
2563 struct cxr_loop
*lp
= cxr_ab_ptr( &pinf
->pmesh
->loops
, poly
->loop_start
+k
);
2564 struct cxr_edge
*edge
= cxr_ab_ptr( &pinf
->pmesh
->edges
, lp
->edge_index
);
2566 if( edge
->freestyle
)
2567 goto IL_SOLID_IS_DISPLACEMENT
;
2572 IL_SOLID_IS_DISPLACEMENT
:;
2574 pinf
->is_displacement
= 1;
2575 cxr_write_disp( pinf
->pmesh
, src
, output
, &abverts
);
2578 // Preprocessor 3: Breakup non-convex shapes into sub-solids
2580 int sources_count
= solids
.count
;
2582 for( int i
=0; i
<sources_count
; i
++ )
2584 struct solidinf pinf
= *(struct solidinf
*)cxr_ab_ptr(&solids
, i
);
2586 if( pinf
.is_displacement
)
2591 struct cxr_mesh
*res
= cxr_pull_best_solid( pinf
.pmesh
, &abverts
, 0, &error
);
2595 cxr_ab_push( &solids
, &(struct solidinf
){res
,0} );
2603 // If no solids error we can rety while preserving 'hot' edges
2605 if( error
& CXR_ERROR_NO_SOLIDS
)
2608 res
= cxr_pull_best_solid(pinf
.pmesh
, &abverts
, 1, &error
);
2610 if( res
) cxr_ab_push( &solids
, &(struct solidinf
){res
,0} );
2624 if( cxr_settings
.debug
)
2626 for( int i
=0; i
<solids
.count
; i
++ )
2628 struct solidinf
*solid
= cxr_ab_ptr(&solids
,i
);
2630 if( !solid
->is_displacement
)
2631 cxr_debug_mesh( solid
->pmesh
, cxr_ab_ptr(&abverts
,0), colours_random
[cxr_range(i
,8)] );
2635 // Turn all those solids into VMF brushes
2636 // --------------------------------------
2637 for( int i
=0; i
<solids
.count
; i
++ )
2639 struct solidinf
*solid
= cxr_ab_ptr(&solids
,i
);
2641 if( solid
->is_displacement
) continue;
2643 cxr_vdf_node( output
, "solid" );
2644 cxr_vdf_ki32( output
, "id", ++ cxr_context
.brush_count
);
2646 for( int j
=0; j
<solid
->pmesh
->polys
.count
; j
++ )
2648 struct cxr_polygon
*poly
= cxr_ab_ptr( &solid
->pmesh
->polys
, j
);
2649 struct cxr_loop
*ploops
= cxr_ab_ptr(&solid
->pmesh
->loops
, poly
->loop_start
);
2650 struct cxr_material
*matptr
=
2651 poly
->material_id
< 0 || src
->material_count
== 0?
2653 &src
->materials
[ poly
->material_id
];
2655 cxr_vdf_node( output
, "side" );
2656 cxr_vdf_ki32( output
, "id", ++ cxr_context
.face_count
);
2658 v3f verts
[3]; v2f uvs
[3];
2660 v3_muls( cxr_ab_ptr(&abverts
, ploops
[0].index
), cxr_context
.scale_factor
, verts
[0] );
2661 v3_muls( cxr_ab_ptr(&abverts
, ploops
[1].index
), cxr_context
.scale_factor
, verts
[1] );
2662 v3_muls( cxr_ab_ptr(&abverts
, ploops
[2].index
), cxr_context
.scale_factor
, verts
[2] );
2663 verts
[0][2] += cxr_context
.offset_z
;
2664 verts
[1][2] += cxr_context
.offset_z
;
2665 verts
[2][2] += cxr_context
.offset_z
;
2667 v2_copy( ploops
[0].uv
, uvs
[0] );
2668 v2_copy( ploops
[1].uv
, uvs
[1] );
2669 v2_copy( ploops
[2].uv
, uvs
[2] );
2671 cxr_vdf_plane( output
, "plane", verts
[2], verts
[1], verts
[0] );
2672 cxr_vdf_kv( output
, "material", matptr
->vmt_path
);
2674 struct cxr_texinfo trans
;
2675 cxr_calculate_axis(&trans
, verts
, uvs
, (double[2]){ matptr
->res
[0], matptr
->res
[1] });
2677 cxr_vdf_kaxis(output
, "uaxis", trans
.uaxis
, trans
.offset
[0], trans
.scale
[0]);
2678 cxr_vdf_kaxis(output
, "vaxis", trans
.vaxis
, trans
.offset
[1], trans
.scale
[1]);
2680 cxr_vdf_kdouble(output
, "rotation", 0.0 );
2681 cxr_vdf_ki32(output
, "lightmapscale", cxr_settings
.lightmap_scale
);
2682 cxr_vdf_ki32(output
, "smoothing_groups", 0);
2684 cxr_vdf_edon( output
);
2687 cxr_vdf_node(output
, "editor");
2688 cxr_vdf_colour255(output
,"color", colours_random
[cxr_range(cxr_context
.brush_count
,8)]);
2689 cxr_vdf_ki32(output
,"visgroupshown",1);
2690 cxr_vdf_ki32(output
,"visgroupautoshown",1);
2691 cxr_vdf_edon(output
);
2693 cxr_vdf_edon( output
);
2696 for( int i
=0; i
<solids
.count
; i
++ )
2698 struct solidinf
*solid
= cxr_ab_ptr(&solids
,i
);
2699 cxr_free_mesh( solid
->pmesh
);
2702 cxr_ab_free( &abverts
);
2703 cxr_ab_free( &solids
);
2708 CXR_API
void cxr_set_log_function( void (*func
)(const char *str
) )
2710 cxr_log_func
= func
;
2713 CXR_API
void cxr_set_line_function( void (*func
)(v3f p0
, v3f p1
, v4f colour
) )
2715 cxr_line_func
= func
;
2718 CXR_API
void cxr_settings_update( struct cxr_settings
*settings
)
2720 cxr_settings
= *settings
;
2723 // Valve copyright stuff probably maybe
2724 // whatever, my previous copyright decleration ends here
2725 // ----------------------------------------------------------
2727 #define HEADER_LUMPS 64
2728 #define LUMP_WORLDLIGHTS 54
2730 #pragma pack(push,1)
2739 int fileofs
, filelen
;
2744 lumps
[ HEADER_LUMPS
];
2754 float shadow_cast_offset
[3];
2762 float constant_attn
;
2764 float quadratic_attn
;
2771 // Utility for patching BSP tools to remove -1 distance lights (we set them
2772 // like that, because we want these lights to go away)
2774 // Yes, there is no way to do this in hammer
2775 // Yes, the distance KV is unused but still gets compiled to this lump
2776 // No, Entities only compile will not do this for you
2778 CXR_API
int cxr_lightpatch_bsp( const char *path
)
2780 printf( "Lightpatch: %s\n", path
);
2782 FILE *fp
= fopen( path
, "r+b" );
2786 cxr_log( "Could not open BSP file for editing (r+b)\n" );
2791 struct header header
;
2792 fread( &header
, sizeof(struct header
), 1, fp
);
2793 struct lump
*lump
= &header
.lumps
[ LUMP_WORLDLIGHTS
];
2795 // Read worldlight array
2796 struct worldlight
*lights
= malloc( lump
->filelen
);
2797 fseek( fp
, lump
->fileofs
, SEEK_SET
);
2798 fread( lights
, lump
->filelen
, 1, fp
);
2800 // Remove all marked lights
2801 int light_count
= lump
->filelen
/ sizeof(struct worldlight
);
2804 for( int i
= 0; i
< light_count
; i
++ )
2805 if( lights
[i
].radius
>= 0.0f
)
2806 lights
[new_count
++] = lights
[i
];
2808 lump
->filelen
= new_count
*sizeof(struct worldlight
);
2811 fseek( fp
, lump
->fileofs
, SEEK_SET
);
2812 fwrite( lights
, lump
->filelen
, 1, fp
);
2813 fseek( fp
, 0, SEEK_SET
);
2814 fwrite( &header
, sizeof(struct header
), 1, fp
);
2815 cxr_log( "removed %d marked lights\n", light_count
-new_count
);