projects / convexer.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
history | raw | HEAD
first windows distributions
[convexer.git] / cxr / cxr.h
1 /*
2 CONVEXER v0.95
3
4 A GNU/Linux-first Source1 Hammer replacement
5 built with Blender, for mapmakers
6
7 Copyright (C) 2022 Harry Godden (hgn)
8
9 LICENSE: GPLv3.0, please see COPYING and LICENSE for more information
10
11 Features:
12 - Brush decomposition into convex pieces for well defined geometry
13 - Freely form displacements without limits
14 - Build your entire map in Blender
15 - Compile models and model groups easily
16 - It runs at an ok speed!
17 - Light patch BSP files; remove unwanted realtime effects
18 - Bestest VTF compressor (thanks to Richgel999 and stb)
19 - Pack content automatically
20
21 Program structure:
22
23 File/folder Lang Purpose
24
25 __init__.py Python Blender plugin interface
26
27 cxr/
28 cxr.h C Heavy lifting; brush decomp, mesh processing
29 cxr_math.h C Vector maths and other handy things
30 cxr_mem.h C Automatic resizing buffers
31 libcxr.c C Compile as SO
32
33 nbvtf/
34 nbvtf.h C VTF processing interface
35 librgcx.h C++ Rich Geldreich's DXT1/DXT5 compressors
36 stb/ C Sean Barrets image I/O
37
38
39 HEADER
40 MACROS
41 STD INCLUDE
42 TYPEDEFS
43 INCLUDE
44 STRUCTURE DEFS
45
46 API
47
48 IMPLEMENTATION
49 */
50
51 #define CXR_API
52 #define CXR_EPSILON 0.001
53 #define CXR_PLANE_SIMILARITY_MAX 0.998
54 #define CXR_BIG_NUMBER 1e300
55 #define CXR_INTERIOR_ANGLE_MAX 0.998
56
57 #ifdef CXR_SO
58 #define CXR_IMPLEMENTATION
59 #endif
60
61 #include <stdio.h>
62 #include <math.h>
63 #include <stdint.h>
64 #include <stdarg.h>
65 #include <stdlib.h>
66 #include <string.h>
67
68 typedef uint8_t u8;
69 typedef uint16_t u16;
70 typedef uint32_t u32;
71 typedef uint64_t u64;
72 typedef int8_t i8;
73 typedef int16_t i16;
74 typedef int32_t i32;
75 typedef int64_t i64;
76
77 typedef unsigned int uint;
78
79 typedef double v2f[2];
80 typedef double v3f[3];
81 typedef double v4f[4];
82 typedef v3f m3x3f[3];
83 typedef v3f m4x3f[4];
84 typedef v3f boxf[2];
85
86 #include "cxr_math.h"
87 #include "cxr_mem.h"
88
89 typedef struct cxr_world cxr_world;
90 typedef struct cxr_solid cxr_solid;
91
92 typedef struct cxr_mesh cxr_mesh;
93 typedef struct cxr_edge cxr_edge;
94 typedef struct cxr_polygon cxr_polygon;
95 typedef struct cxr_static_mesh cxr_static_mesh;
96 typedef struct cxr_loop cxr_loop;
97 typedef struct cxr_static_loop cxr_static_loop;
98 typedef struct cxr_material cxr_material;
99 typedef struct cxr_tri_mesh cxr_tri_mesh;
100
101 #ifdef CXR_VALVE_MAP_FILE
102 typedef struct cxr_vdf cxr_vdf;
103 typedef struct cxr_texinfo cxr_texinfo;
104 typedef struct cxr_visgroup cxr_visgroup;
105 typedef struct cxr_vmf_context cxr_vmf_context;
106 #endif /* CXR_VALVE_MAP_FILE */
107
108 /*
109 * Public API
110 */
111
112 /* Main convexer algorithms */
113 /* Convex decomp from mesh */
114 CXR_API cxr_world *cxr_decompose( cxr_static_mesh *src, i32 *perrcode );
115 CXR_API void cxr_free_world( cxr_world *world );
116 CXR_API cxr_tri_mesh *cxr_world_preview( cxr_world *world );
117 CXR_API void cxr_free_tri_mesh( cxr_tri_mesh *mesh );
118
119 #ifdef CXR_VALVE_MAP_FILE
120 /* VMF interface */
121 CXR_API void cxr_begin_vmf( cxr_vmf_context *ctx, cxr_vdf *vdf );
122 CXR_API void cxr_vmf_begin_entities( cxr_vmf_context *ctx, cxr_vdf *vdf );
123 CXR_API void cxr_push_world_vmf(
124 cxr_world *world, cxr_vmf_context *ctx, cxr_vdf *vdf);
125 CXR_API void cxr_end_vmf( cxr_vmf_context *ctx, cxr_vdf *vdf );
126
127 /* VDF interface */
128 CXR_API cxr_vdf *cxr_vdf_open( const char *path );
129 CXR_API void cxr_vdf_close( cxr_vdf *vdf );
130 CXR_API void cxr_vdf_put( cxr_vdf *vdf, const char *str );
131 CXR_API void cxr_vdf_node( cxr_vdf *vdf, const char *str );
132 CXR_API void cxr_vdf_edon( cxr_vdf *vdf );
133 CXR_API void cxr_vdf_kv( cxr_vdf *vdf, const char *strk, const char *strv );
134
135 /* Other tools */
136 CXR_API int cxr_lightpatch_bsp( const char *path );
137 #endif /* CXR_VALVE_MAP_FILE */
138
139 #ifdef CXR_DEBUG
140 /* Debugging */
141 CXR_API void cxr_set_log_function( void (*func)(const char *str) );
142 CXR_API void cxr_set_line_function( void (*func)(v3f p0, v3f p1, v4f colour) );
143 CXR_API void cxr_write_test_data( cxr_static_mesh *src );
144 #endif /* CXR_DEBUG */
145
146 struct cxr_static_mesh
147 {
148 v3f *vertices;
149
150 struct cxr_edge
151 {
152 i32 i0, i1;
153 i32 freestyle, sharp;
154 }
155 *edges;
156
157 struct cxr_static_loop
158 {
159 i32 index,
160 edge_index;
161 v2f uv;
162 }
163 *loops;
164
165 struct cxr_polygon
166 {
167 i32 loop_start, loop_total;
168 v3f normal;
169 v3f center;
170 i32 material_id; /* -1: interior material (nodraw) */
171 }
172 *polys;
173
174 struct cxr_material
175 {
176 i32 res[2];
177 char *name;
178 }
179 *materials;
180
181 i32 poly_count,
182 vertex_count,
183 edge_count,
184 loop_count,
185 material_count;
186 };
187
188 struct cxr_loop
189 {
190 i32 poly_left,
191 poly_right,
192 edge_index,
193 index;
194 v2f uv;
195 };
196
197 struct cxr_solid
198 {
199 cxr_mesh *pmesh;
200 int displacement,
201 invalid;
202 };
203
204 struct cxr_world
205 {
206 cxr_abuffer abverts,
207 absolids;
208
209 cxr_material *materials;
210 int material_count;
211 };
212
213 struct cxr_mesh
214 {
215 struct cxr_abuffer
216 abedges,
217 abloops,
218 abpolys,
219
220 *p_abverts; /* This data is stored externally because the data is often
221 shared between solids. */
222
223 /* Valid when update() is called on this mesh,
224 * Invalid when data is appended to them */
225 struct cxr_edge *edges;
226 struct cxr_polygon *polys;
227 struct cxr_loop *loops;
228 };
229
230 /* Simple mesh type mainly for debugging */
231 struct cxr_tri_mesh
232 {
233 v3f *vertices;
234 v4f *colours;
235 i32 *indices,
236 indices_count,
237 vertex_count;
238 };
239
240 #ifdef CXR_VALVE_MAP_FILE
241 struct cxr_texinfo
242 {
243 v3f uaxis, vaxis;
244 v2f offset, scale;
245 double winding;
246 };
247
248 struct cxr_visgroup
249 {
250 const char *name;
251 };
252
253 /*
254 * Simplified VDF writing interface. No allocations or nodes, just write to file
255 */
256 struct cxr_vdf
257 {
258 FILE *fp;
259 i32 level;
260 };
261
262 struct cxr_vmf_context
263 {
264 /* File info */
265 i32 mapversion;
266 const char *skyname,
267 *detailvbsp,
268 *detailmaterial;
269
270 cxr_visgroup *visgroups;
271 i32 visgroup_count;
272
273 /* Transform settings */
274 double scale;
275 v3f offset;
276 i32 lightmap_scale,
277 visgroupid;
278
279 /* Current stats */
280 i32 brush_count,
281 entity_count,
282 face_count;
283 };
284 #endif /* CXR_VALVE_MAP_FILE */
285
286 enum cxr_soliderr
287 {
288 k_soliderr_none = 0,
289 k_soliderr_non_manifold,
290 k_soliderr_bad_manifold,
291 k_soliderr_no_solids,
292 k_soliderr_degenerate_implicit,
293 k_soliderr_non_coplanar_vertices,
294 k_soliderr_non_convex_poly,
295 k_soliderr_bad_result,
296 k_soliderr_invalid_input
297 };
298
299 /*
300 * Implementation
301 * -----------------------------------------------------------------------------
302 */
303 #ifdef CXR_IMPLEMENTATION
304 #ifdef CXR_SO
305 const char *cxr_build_time = __DATE__ " @" __TIME__;
306 #endif
307
308 #if _WIN32 || _WIN64
309 #if _WIN64
310 #else
311 #warning 32 bit is not supported in blender 3.0
312 #endif
313 #endif
314
315 static void (*cxr_log_func)(const char *str);
316 static void (*cxr_line_func)( v3f p0, v3f p1, v4f colour );
317
318 static int cxr_range(int x, int bound)
319 {
320 if( x < 0 )
321 x += bound * (x/bound + 1);
322
323 return x % bound;
324 }
325
326 /*
327 * This should be called after appending any data to those buffers
328 */
329 static void cxr_mesh_update( cxr_mesh *mesh )
330 {
331 mesh->edges = cxr_ab_ptr(&mesh->abedges, 0);
332 mesh->polys = cxr_ab_ptr(&mesh->abpolys, 0);
333 mesh->loops = cxr_ab_ptr(&mesh->abloops, 0);
334 }
335
336 static v4f colours_random[] =
337 {
338 { 0.863, 0.078, 0.235, 0.4 },
339 { 0.000, 0.980, 0.604, 0.4 },
340 { 0.118, 0.565, 1.000, 0.4 },
341 { 0.855, 0.439, 0.839, 0.4 },
342 { 0.824, 0.412, 0.118, 0.4 },
343 { 0.125, 0.698, 0.667, 0.4 },
344 { 0.541, 0.169, 0.886, 0.4 },
345 { 1.000, 0.843, 0.000, 0.4 }
346 };
347
348 static v4f colours_solids[] =
349 {
350 { 100, 143, 255, 200 },
351 { 120, 94, 240, 200 },
352 { 220, 38, 127, 200 },
353 { 254, 97, 0, 200 },
354 { 255, 176, 0, 200 }
355 };
356
357 static v4f colour_entity = { 37, 241, 122, 255 };
358 static v4f colour_displacement_solid = { 146, 146, 146, 120 };
359 static v4f colour_error = { 1.0f, 0.0f, 0.0f, 1.0f };
360 static v4f colour_face_graph = { 1.0f, 1.0f, 1.0f, 0.03f };
361 static v4f colour_success = { 0.0f, 1.0f, 0.0f, 1.0f };
362
363 static void value_random(int n, v4f colour)
364 {
365 double val = cxr_range(n,8);
366 val /= 16.0;
367 val += 0.75;
368
369 v3_muls( colour, val, colour );
370 }
371
372 static void colour_random_brush(int n, v4f colour)
373 {
374 #if 1
375 int value_n = n / 5;
376 int colour_n = cxr_range( n, 5 );
377 v4_muls( colours_solids[ colour_n ], 1.0/255.0, colour );
378 value_random( value_n, colour );
379 #else
380 int colour_n = cxr_range( n, 8 );
381 v4_copy( colours_random[ colour_n ], colour );
382 #endif
383 }
384
385 /*
386 * Debugging and diagnostic utilities
387 * -----------------------------------------------------------------------------
388 */
389
390 #ifdef CXR_DEBUG
391
392 static void cxr_log( const char *fmt, ... )
393 {
394 char buf[512];
395
396 va_list args;
397 va_start( args, fmt );
398 vsnprintf( buf, sizeof(buf)-1, fmt, args );
399 va_end(args);
400
401 if( cxr_log_func )
402 cxr_log_func( buf );
403
404 fputs(buf,stdout);
405 }
406
407 static void cxr_debug_line( v3f p0, v3f p1, v4f colour )
408 {
409 if( cxr_line_func )
410 cxr_line_func( p0, p1, colour );
411 }
412
413 static void cxr_debug_box( v3f p0, double sz, v4f colour )
414 {
415 v3f a,b,c,d,
416 a1,b1,c1,d1;
417 v3_add(p0, (v3f){-sz,-sz,-sz}, a);
418 v3_add(p0, (v3f){-sz, sz,-sz}, b);
419 v3_add(p0, (v3f){ sz, sz,-sz}, c);
420 v3_add(p0, (v3f){ sz,-sz,-sz}, d);
421 v3_add(p0, (v3f){-sz,-sz,sz}, a1);
422 v3_add(p0, (v3f){-sz, sz,sz}, b1);
423 v3_add(p0, (v3f){ sz, sz,sz}, c1);
424 v3_add(p0, (v3f){ sz,-sz,sz}, d1);
425
426 cxr_debug_line( a,b, colour );
427 cxr_debug_line( b,c, colour );
428 cxr_debug_line( c,d, colour );
429 cxr_debug_line( d,a, colour );
430 cxr_debug_line( a1,b1, colour );
431 cxr_debug_line( b1,c1, colour );
432 cxr_debug_line( c1,d1, colour );
433 cxr_debug_line( d1,a1, colour );
434 cxr_debug_line( a,a1, colour );
435 cxr_debug_line( b,b1, colour );
436 cxr_debug_line( c,c1, colour );
437 cxr_debug_line( d,d1, colour );
438 }
439
440 /*
441 * Draw arrow with the tips oriented along normal
442 */
443 static void cxr_debug_arrow( v3f p0, v3f p1, v3f normal, double sz, v4f colour )
444 {
445 v3f dir, tan, p2, p3;
446 v3_sub(p1,p0,dir);
447 v3_normalize(dir);
448
449 v3_cross(dir,normal,tan);
450 v3_muladds( p1,dir, -sz, p2 );
451 v3_muladds( p2,tan,sz,p3 );
452 cxr_debug_line( p1, p3, colour );
453 v3_muladds( p2,tan,-sz,p3 );
454 cxr_debug_line( p1, p3, colour );
455 cxr_debug_line( p0, p1, colour );
456 }
457
458 /*
459 * Draw arrows CCW around polygon, draw normal vector from center
460 */
461 static void cxr_debug_poly( cxr_mesh *mesh, cxr_polygon *poly, v4f colour )
462 {
463 v3f *verts = cxr_ab_ptr( mesh->p_abverts, 0 );
464
465 for( int i=0; i<poly->loop_total; i++ )
466 {
467 int lp0 = poly->loop_start+i,
468 lp1 = poly->loop_start+cxr_range(i+1,poly->loop_total);
469
470 int i0 = mesh->loops[ lp0 ].index,
471 i1 = mesh->loops[ lp1 ].index;
472
473 v3f p0, p1;
474
475 v3_lerp( verts[i0], poly->center, 0.0075, p0 );
476 v3_lerp( verts[i1], poly->center, 0.0075, p1 );
477 v3_muladds( p0, poly->normal, 0.01, p0 );
478 v3_muladds( p1, poly->normal, 0.01, p1 );
479
480 cxr_debug_arrow( p0, p1, poly->normal, 0.05, colour );
481 }
482
483 v3f nrm0;
484 v3_muladds( poly->center, poly->normal, 0.3, nrm0 );
485
486 cxr_debug_line( poly->center, nrm0, colour );
487 }
488
489 static void cxr_debug_mesh(cxr_mesh *mesh, v4f colour )
490 {
491 for( int i=0; i<mesh->abpolys.count; i++ )
492 {
493 cxr_polygon *poly = &mesh->polys[i];
494 cxr_debug_poly( mesh, poly, colour );
495 }
496 }
497
498 CXR_API void cxr_write_test_data( cxr_static_mesh *src )
499 {
500 FILE *fp = fopen(
501 "/home/harry/Documents/blender_addons_remote/addons/convexer/cxr/solid.h",
502 "w" );
503
504 fprintf( fp, "v3f test_verts[] = {\n" );
505 for( int i=0; i<src->vertex_count; i ++ )
506 {
507 fprintf( fp, " { %f, %f, %f },\n",
508 src->vertices[i][0],
509 src->vertices[i][1],
510 src->vertices[i][2] );
511 }
512 fprintf( fp, "};\n" );
513
514 fprintf( fp, "cxr_static_loop test_loops[] = {\n" );
515 for( int i=0; i<src->loop_count; i ++ )
516 {
517 fprintf( fp, " {%d, %d},\n",
518 src->loops[i].index,
519 src->loops[i].edge_index);
520 }
521 fprintf( fp, "};\n" );
522
523 fprintf( fp, "cxr_polygon test_polys[] = {\n" );
524 for( int i=0; i <src->poly_count; i++ )
525 {
526 fprintf( fp, " {%d, %d, {%f, %f, %f}, {%f, %f, %f}},\n",
527 src->polys[i].loop_start,
528 src->polys[i].loop_total,
529 src->polys[i].normal[0],
530 src->polys[i].normal[1],
531 src->polys[i].normal[2],
532 src->polys[i].center[0],
533 src->polys[i].center[1],
534 src->polys[i].center[2] );
535 }
536 fprintf( fp, "};\n" );
537
538 fprintf( fp, "cxr_edge test_edges[] = {\n" );
539 for( int i=0; i<src->edge_count; i++ )
540 {
541 fprintf( fp, " {%d, %d, %d, %d},\n",
542 src->edges[i].i0,
543 src->edges[i].i1,
544 src->edges[i].freestyle,
545 src->edges[i].sharp
546 );
547 }
548 fprintf( fp, "};\n" );
549
550 fprintf( fp, "cxr_static_mesh test_mesh = {\n" );
551 fprintf( fp, " .vertices = test_verts,\n" );
552 fprintf( fp, " .loops = test_loops,\n" );
553 fprintf( fp, " .edges = test_edges,\n" );
554 fprintf( fp, " .polys = test_polys,\n" );
555 fprintf( fp, " .poly_count=%d,\n", src->poly_count );
556 fprintf( fp, " .vertex_count=%d,\n", src->vertex_count );
557 fprintf( fp, " .edge_count=%d,\n",src->edge_count );
558 fprintf( fp, " .loop_count=%d\n", src->loop_count );
559 fprintf( fp, "};\n" );
560
561 fclose( fp );
562 }
563
564 CXR_API void cxr_set_log_function( void (*func)(const char *str) )
565 {
566 cxr_log_func = func;
567 }
568
569 CXR_API void cxr_set_line_function( void (*func)(v3f p0, v3f p1, v4f colour) )
570 {
571 cxr_line_func = func;
572 }
573
574 #endif /* CXR_DEBUG */
575
576
577 /*
578 * abverts is a pointer to an existing vertex buffer
579 */
580 static cxr_mesh *cxr_alloc_mesh( int edge_count, int loop_count, int poly_count,
581 cxr_abuffer *abverts
582 ){
583 cxr_mesh *mesh = malloc(sizeof(cxr_mesh));
584 cxr_ab_init(&mesh->abedges, sizeof(cxr_edge), edge_count);
585 cxr_ab_init(&mesh->abloops, sizeof(cxr_loop), loop_count);
586 cxr_ab_init(&mesh->abpolys, sizeof(cxr_polygon), poly_count);
587 mesh->p_abverts = abverts;
588
589 cxr_mesh_update( mesh );
590
591 return mesh;
592 }
593
594 static void cxr_free_mesh( cxr_mesh *mesh )
595 {
596 cxr_ab_free(&mesh->abedges);
597 cxr_ab_free(&mesh->abloops);
598 cxr_ab_free(&mesh->abpolys);
599 free(mesh);
600 }
601
602 /*
603 * Rebuilds edge data for mesh (useful to get rid of orphaned edges)
604 */
605 static void cxr_mesh_clean_edges( cxr_mesh *mesh )
606 {
607 cxr_abuffer new_edges;
608 cxr_ab_init( &new_edges, sizeof(cxr_edge), mesh->abedges.count );
609
610 for( int i=0; i<mesh->abpolys.count; i++ )
611 {
612 cxr_polygon *poly = &mesh->polys[i];
613 for( int j=0; j<poly->loop_total; j++ )
614 {
615 cxr_loop
616 *lp0 = &mesh->loops[poly->loop_start+j],
617 *lp1 = &mesh->loops[poly->loop_start+cxr_range(j+1,poly->loop_total)];
618
619 int i0 = cxr_min(lp0->index, lp1->index),
620 i1 = cxr_max(lp0->index, lp1->index);
621
622 /* Check if edge exists before adding */
623 for( int k=0; k<new_edges.count; k++ )
624 {
625 cxr_edge *edge = cxr_ab_ptr(&new_edges,k);
626
627 if( edge->i0 == i0 && edge->i1 == i1 )
628 {
629 lp0->edge_index = k;
630 goto IL_EDGE_CREATED;
631 }
632 }
633
634 int orig_edge_id = lp0->edge_index;
635 lp0->edge_index = new_edges.count;
636
637 cxr_edge edge = { i0, i1 };
638
639 /*
640 * Copy extra information from original edges
641 */
642
643 if( orig_edge_id < mesh->abedges.count )
644 {
645 cxr_edge *orig_edge = &mesh->edges[ orig_edge_id ];
646 edge.freestyle = orig_edge->freestyle;
647 edge.sharp = orig_edge->sharp;
648 }
649 else
650 {
651 edge.freestyle = 0;
652 edge.sharp = 0;
653 }
654
655 cxr_ab_push( &new_edges, &edge );
656
657 IL_EDGE_CREATED:;
658 }
659 }
660
661 cxr_ab_free( &mesh->abedges );
662 mesh->abedges = new_edges;
663
664 cxr_mesh_update( mesh );
665 }
666
667 /*
668 * Remove 0-length faces from mesh (we mark them light that for deletion
669 * Remove all unused loops as a result of removing those faces
670 */
671 static void cxr_mesh_clean_faces( cxr_mesh *mesh )
672 {
673 cxr_abuffer loops_new;
674 cxr_ab_init( &loops_new, sizeof(cxr_loop), mesh->abloops.count );
675
676 int new_length=0;
677 for( int i=0; i<mesh->abpolys.count; i++ )
678 {
679 cxr_polygon *src = &mesh->polys[i],
680 *dst = &mesh->polys[new_length];
681
682 if( src->loop_total > 0 )
683 {
684 int src_start = src->loop_start,
685 src_total = src->loop_total;
686
687 *dst = *src;
688 dst->loop_start = loops_new.count;
689
690 for( int j=0; j<src_total; j++ )
691 {
692 cxr_loop *loop = &mesh->loops[src_start+j],
693 *ldst = cxr_ab_ptr(&loops_new,dst->loop_start+j);
694 *ldst = *loop;
695 ldst->poly_left = new_length;
696 }
697
698 loops_new.count += src_total;
699 new_length ++;
700 }
701 }
702
703 cxr_ab_free( &mesh->abloops );
704 mesh->abloops = loops_new;
705 mesh->abpolys.count = new_length;
706
707 cxr_mesh_update( mesh );
708 }
709
710 /*
711 * Links loop's poly_left and poly_right
712 * Does not support more than 2 polys to one edge
713 *
714 * Returns 0 if there is non-manifold geomtry (aka: not watertight)
715 */
716 static int cxr_mesh_link_loops( cxr_mesh *mesh )
717 {
718 i32 *polygon_edge_map = malloc(mesh->abedges.count*2 *sizeof(i32));
719
720 for( int i = 0; i < mesh->abedges.count*2; i ++ )
721 polygon_edge_map[i] = -1;
722
723 for( int i = 0; i < mesh->abpolys.count; i ++ )
724 {
725 cxr_polygon *poly = &mesh->polys[i];
726
727 for( int j = 0; j < poly->loop_total; j ++ )
728 {
729 cxr_loop *loop = &mesh->loops[ poly->loop_start+j ];
730 loop->poly_left = i;
731
732 for( int k = 0; k < 2; k ++ )
733 {
734 i32 *edge = &polygon_edge_map[loop->edge_index*2+k];
735
736 if( *edge == -1 )
737 {
738 *edge = i;
739 goto next;
740 }
741 }
742
743 /* Overflowed edge mapping... Duplicated faces. */
744 free( polygon_edge_map );
745 return 0;
746
747 next:;
748 }
749 }
750 for( int i = 0; i < mesh->abpolys.count; i ++ )
751 {
752 cxr_polygon *poly = &mesh->polys[i];
753
754 for( int j = 0; j < poly->loop_total; j ++ )
755 {
756 cxr_loop *loop = &mesh->loops[ poly->loop_start+j ];
757
758 i32 *face_map = &polygon_edge_map[ loop->edge_index*2 ];
759
760 if( face_map[0] == loop->poly_left ) loop->poly_right = face_map[1];
761 else loop->poly_right = face_map[0];
762 }
763 }
764
765
766 for( int i=0; i<mesh->abedges.count*2; i++ )
767 {
768 if( polygon_edge_map[i] == -1 )
769 {
770 free( polygon_edge_map );
771 return 0;
772 }
773 }
774
775 free( polygon_edge_map );
776 return 1;
777 }
778
779 /*
780 * Create new empty polygon with known loop count
781 * Must be filled and completed by the following functions!
782 */
783 static int cxr_create_poly( cxr_mesh *mesh, int loop_count )
784 {
785 v3f *verts = cxr_ab_ptr( mesh->p_abverts, 0 );
786
787 if( loop_count < 3 )
788 {
789 #ifdef CXR_DEBUG
790 cxr_log( "tried to add new poly with length %d!\n", loop_count );
791 #endif
792 return 0;
793 }
794
795 cxr_ab_reserve( &mesh->abpolys, 1 );
796 cxr_ab_reserve( &mesh->abloops, loop_count );
797 cxr_mesh_update( mesh );
798
799 cxr_polygon *poly = &mesh->polys[ mesh->abpolys.count ];
800
801 poly->loop_start = mesh->abloops.count;
802 poly->loop_total = 0;
803 poly->material_id = -1;
804 v3_zero( poly->center );
805
806 return 1;
807 }
808
809 /*
810 * Add one index to the polygon created by the above function
811 */
812 static void cxr_poly_push_index( cxr_mesh *mesh, int id )
813 {
814 v3f *verts = cxr_ab_ptr( mesh->p_abverts, 0 );
815
816 int nface_id = mesh->abpolys.count;
817 cxr_polygon *poly = &mesh->polys[ nface_id ];
818
819 cxr_loop *new_loop = &mesh->loops[ poly->loop_start + poly->loop_total ];
820
821 new_loop->poly_left = nface_id;
822 new_loop->poly_right = -1;
823 new_loop->index = id;
824 new_loop->edge_index = 0;
825 v2_zero(new_loop->uv);
826
827 v3_add( poly->center, verts[new_loop->index], poly->center );
828
829 poly->loop_total ++;
830 mesh->abloops.count ++;
831 }
832
833 /*
834 * Finalize and commit polygon into mesh
835 */
836 static void cxr_poly_finish( cxr_mesh *mesh )
837 {
838 v3f *verts = cxr_ab_ptr( mesh->p_abverts, 0 );
839
840 int nface_id = mesh->abpolys.count;
841 cxr_polygon *poly = &mesh->polys[nface_id];
842
843 /* Average center and calc normal */
844
845 v3_divs( poly->center, poly->loop_total, poly->center );
846 cxr_loop *lp0 = &mesh->loops[ poly->loop_start],
847 *lp1 = &mesh->loops[ poly->loop_start+1 ],
848 *lp2 = &mesh->loops[ poly->loop_start+2 ];
849
850 tri_normal(
851 verts[lp0->index], verts[lp1->index], verts[lp2->index], poly->normal);
852
853 mesh->abpolys.count ++;
854 }
855
856 /*
857 * Extract the next island from mesh
858 *
859 * Returns NULL if mesh is one contigous object
860 */
861 static cxr_mesh *cxr_pull_island( cxr_mesh *mesh )
862 {
863 cxr_mesh_link_loops(mesh);
864
865 int *island_current = malloc(mesh->abpolys.count*sizeof(int)),
866 island_len = 1,
867 loop_count = 0,
868 last_count;
869
870 island_current[0] = 0;
871
872 island_grow:
873 last_count = island_len;
874
875 for( int i=0; i<island_len; i++ )
876 {
877 cxr_polygon *poly = &mesh->polys[ island_current[i] ];
878
879 for( int j=0; j<poly->loop_total; j++ )
880 {
881 cxr_loop *loop = &mesh->loops[ poly->loop_start+j ];
882
883 if( loop->poly_right != -1 )
884 {
885 int face_present = 0;
886
887 for( int k=0; k<island_len; k++ )
888 {
889 if( island_current[k] == loop->poly_right )
890 {
891 face_present = 1;
892 break;
893 }
894 }
895
896 if( !face_present )
897 island_current[ island_len ++ ] = loop->poly_right;
898 }
899 }
900 }
901
902 if( island_len > last_count )
903 goto island_grow;
904
905 /* Check for complete object */
906 if( island_len == mesh->abpolys.count )
907 {
908 free( island_current );
909 return NULL;
910 }
911
912 for( int i=0; i<island_len; i++ )
913 {
914 cxr_polygon *poly = &mesh->polys[ island_current[i] ];
915 loop_count += poly->loop_total;
916 }
917
918 /* Create and update meshes */
919 cxr_mesh *newmesh = cxr_alloc_mesh( mesh->abedges.count,
920 loop_count,
921 island_len,
922 mesh->p_abverts );
923
924 for( int i=0; i<island_len; i++ )
925 {
926 cxr_polygon *src = &mesh->polys[ island_current[i] ];
927 cxr_polygon *dst = cxr_ab_ptr(&newmesh->abpolys, i);
928
929 *dst = *src;
930 dst->loop_start = newmesh->abloops.count;
931
932 for( int j=0; j<src->loop_total; j++ )
933 {
934 cxr_loop
935 *lsrc = &mesh->loops[ src->loop_start+j ],
936 *ldst = cxr_ab_ptr(&newmesh->abloops, dst->loop_start+j);
937
938 *ldst = *lsrc;
939 ldst->poly_left = i;
940 ldst->poly_right = -1;
941 }
942
943 newmesh->abloops.count += src->loop_total;
944 src->loop_total = -1;
945 }
946
947 newmesh->abpolys.count = island_len;
948 newmesh->abedges.count = mesh->abedges.count;
949 memcpy( cxr_ab_ptr(&newmesh->abedges,0),
950 mesh->edges,
951 mesh->abedges.count * sizeof(cxr_edge));
952
953 cxr_mesh_clean_faces(mesh);
954 cxr_mesh_clean_edges(mesh);
955 cxr_mesh_clean_edges(newmesh);
956
957 free( island_current );
958 return newmesh;
959 }
960
961 /*
962 * Invalid solid is when there are vertices that are coplanar to a face, but are
963 * outside the polygons edges.
964 */
965 static int cxr_valid_solid( cxr_mesh *mesh, int *solid, int len )
966 {
967 v3f *verts = cxr_ab_ptr(mesh->p_abverts, 0);
968
969 for( int i=0; i<len; i++ )
970 {
971 cxr_polygon *polyi = &mesh->polys[ solid[i] ];
972
973 v4f plane;
974 normal_to_plane(polyi->normal, polyi->center, plane);
975
976 for( int j=0; j<len; j++ )
977 {
978 if( i==j ) continue;
979
980 cxr_polygon *polyj = &mesh->polys[ solid[j] ];
981
982 for( int k=0; k<polyj->loop_total; k++ )
983 {
984 cxr_loop *lpj = &mesh->loops[ polyj->loop_start+k ];
985
986 /* Test if the vertex is not referenced by the polygon */
987 for( int l=0; l<polyi->loop_total; l++ )
988 {
989 cxr_loop *lpi = &mesh->loops[ polyi->loop_start+l ];
990
991 if( lpi->index == lpj->index )
992 goto skip_vertex;
993 }
994
995 if( fabs(plane_polarity(plane, verts[lpj->index])) < 0.001 )
996 return 0;
997
998 skip_vertex:;
999 }
1000 }
1001 }
1002
1003 return 1;
1004 }
1005
1006 /*
1007 * Use when iterating the loops array, to get a unique set of edges
1008 * Better than using the edges array and doing many more checks
1009 */
1010 static int cxr_loop_unique_edge( cxr_loop *lp )
1011 {
1012 if( lp->poly_left > lp->poly_right )
1013 return 0;
1014
1015 return 1;
1016 }
1017
1018 /*
1019 * Identify edges in the mesh where the two connected face's normals
1020 * are opposing eachother (or close to identical)
1021 */
1022 static int *cxr_mesh_reflex_edges( cxr_mesh *mesh )
1023 {
1024 v3f *verts = cxr_ab_ptr( mesh->p_abverts, 0 );
1025 int *edge_tagged = malloc( mesh->abedges.count * sizeof(int) );
1026
1027 for( int i=0; i<mesh->abloops.count; i++ )
1028 {
1029 cxr_loop *lp = &mesh->loops[i];
1030 if( !cxr_loop_unique_edge( lp ) ) continue;
1031
1032 edge_tagged[lp->edge_index] = 0;
1033
1034 cxr_polygon *polya = &mesh->polys[ lp->poly_left ],
1035 *polyb = &mesh->polys[ lp->poly_right ];
1036
1037 v4f planeb;
1038 normal_to_plane(polyb->normal, polyb->center, planeb);
1039
1040 for( int j=0; j<polya->loop_total; j++ )
1041 {
1042 cxr_loop *lp1 = &mesh->loops[ polya->loop_start+j ];
1043
1044 if(( plane_polarity( planeb, verts[lp1->index] ) > 0.001 ) ||
1045 ( v3_dot(polya->normal,polyb->normal) > CXR_PLANE_SIMILARITY_MAX ))
1046 {
1047 edge_tagged[lp->edge_index] = 1;
1048 break;
1049 }
1050 }
1051 }
1052
1053 return edge_tagged;
1054 }
1055
1056 /*
1057 * Same logic as above function except it will apply it to each vertex
1058 */
1059 static int *cxr_mesh_reflex_vertices( cxr_mesh *mesh )
1060 {
1061 v3f *verts = cxr_ab_ptr( mesh->p_abverts, 0 );
1062
1063 int *vertex_tagged = malloc( mesh->p_abverts->count*sizeof(int) );
1064 int *connected_planes = malloc( mesh->abpolys.count*sizeof(int) );
1065
1066 for( int i=0; i<mesh->p_abverts->count; i++ )
1067 {
1068 vertex_tagged[i]=0;
1069 int num_connected = 0;
1070
1071 /* Create a list of polygons that refer to this vertex */
1072 for( int j=0; j<mesh->abpolys.count; j++ )
1073 {
1074 cxr_polygon *poly = &mesh->polys[j];
1075 for( int k=0; k<poly->loop_total; k++ )
1076 {
1077 cxr_loop *loop = &mesh->loops[poly->loop_start+k];
1078 if( loop->index == i )
1079 {
1080 connected_planes[num_connected ++] = j;
1081 break;
1082 }
1083 }
1084 }
1085
1086 /* Check all combinations for a similar normal */
1087 for( int j=0; j<num_connected-1; j++ )
1088 {
1089 for( int k=j+1; k<num_connected; k++ )
1090 {
1091 cxr_polygon *polyj = &mesh->polys[connected_planes[j]],
1092 *polyk = &mesh->polys[connected_planes[k]];
1093
1094 if( v3_dot(polyj->normal,polyk->normal) > CXR_PLANE_SIMILARITY_MAX )
1095 goto tag_vert;
1096 }
1097 }
1098
1099 /*
1100 * Check if all connected planes either:
1101 * - Bound this vert
1102 * - Coplanar with it
1103 */
1104 for( int j=0; j<num_connected; j++ )
1105 {
1106 for( int k=j+1; k<num_connected; k++ )
1107 {
1108 cxr_polygon *jpoly = &mesh->polys[ connected_planes[j] ],
1109 *kpoly = &mesh->polys[ connected_planes[k] ];
1110
1111 v4f plane;
1112 normal_to_plane( kpoly->normal, kpoly->center, plane );
1113 for( int l=0; l<jpoly->loop_total; l++ )
1114 {
1115 cxr_loop *lp = &mesh->loops[ jpoly->loop_start+l ];
1116
1117 if( plane_polarity( plane, verts[lp->index] ) > 0.001 )
1118 goto tag_vert;
1119 }
1120 }
1121 }
1122
1123 continue;
1124 tag_vert:
1125 vertex_tagged[i] = 1;
1126 }
1127
1128 free( connected_planes );
1129 return vertex_tagged;
1130 }
1131
1132 /*
1133 * Detect if potential future edges create a collision with any of the
1134 * existing edges in the mesh
1135 */
1136 static int cxr_solid_overlap( cxr_mesh *mesh,
1137 cxr_polygon *pa,
1138 cxr_polygon *pb,
1139 int common_edge_index
1140 ){
1141 v3f *verts = cxr_ab_ptr( mesh->p_abverts, 0 );
1142 cxr_edge *common_edge = &mesh->edges[common_edge_index];
1143
1144 int unique_a = pa->loop_total-2,
1145 unique_b = pb->loop_total-2;
1146
1147 int *unique_verts = malloc( (unique_a+unique_b)*sizeof(int) );
1148 int unique_total = 0;
1149
1150 for( int j=0; j<2; j++ )
1151 {
1152 cxr_polygon *poly = (cxr_polygon *[2]){pa,pb}[j];
1153
1154 for( int i=0; i<poly->loop_total; i++ )
1155 {
1156 cxr_loop *lp = &mesh->loops[poly->loop_start+i];
1157
1158 if( lp->index == common_edge->i0 || lp->index == common_edge->i1 )
1159 continue;
1160
1161 unique_verts[ unique_total ++ ] = lp->index;
1162 }
1163 }
1164
1165 v3f ca, cb;
1166
1167 for( int i=0; i<unique_a; i++ )
1168 {
1169 for( int j=unique_a; j<unique_total; j++ )
1170 {
1171 int i0 = unique_verts[i],
1172 i1 = unique_verts[j];
1173
1174 for( int k=0; k<mesh->abedges.count; k++ )
1175 {
1176 cxr_edge *edge = &mesh->edges[k];
1177
1178 if( edge->i0 == i0 || edge->i0 == i1 ||
1179 edge->i1 == i0 || edge->i1 == i1 ) continue;
1180
1181 double *a0 = verts[i0],
1182 *a1 = verts[i1],
1183 *b0 = verts[edge->i0],
1184 *b1 = verts[edge->i1];
1185
1186 double dist = segment_segment_dist( a0, a1, b0, b1, ca, cb );
1187
1188 if( dist < 0.025 )
1189 {
1190 free( unique_verts );
1191 return 1;
1192 }
1193 }
1194 }
1195 }
1196
1197 free( unique_verts );
1198 return 0;
1199 }
1200
1201 /*
1202 * Creates the 'maximal' solid that originates from this faceid
1203 *
1204 * Returns the number of faces used
1205 */
1206 static int cxr_buildsolid(
1207 cxr_mesh *mesh,
1208 int faceid,
1209 int *solid,
1210 int *reflex_edges,
1211 int *faces_tagged )
1212 {
1213 faces_tagged[faceid] = faceid;
1214
1215 int solid_len = 0;
1216 solid[solid_len++] = faceid;
1217
1218 int search_start = 0;
1219
1220 search_iterate:;
1221
1222 int changed = 0;
1223 for( int j=search_start; j<solid_len; j++ )
1224 {
1225 cxr_polygon *poly = &mesh->polys[ solid[j] ];
1226
1227 for( int k=0; k<poly->loop_total; k++ )
1228 {
1229 cxr_loop *loop = &mesh->loops[ poly->loop_start+k ];
1230 cxr_edge *edge = &mesh->edges[ loop->edge_index ];
1231
1232 if( faces_tagged[ loop->poly_right ] == -1 )
1233 {
1234 if( !reflex_edges[loop->edge_index] )
1235 {
1236 /* Check for dodgy edges */
1237 cxr_polygon *newpoly = &mesh->polys[loop->poly_right];
1238
1239 if( cxr_solid_overlap(mesh,poly,newpoly,loop->edge_index))
1240 goto skip_plane;
1241
1242 /* Looking ahead by one step gives us an early out for invalid
1243 * configurations. This might just all be handled by the new
1244 * edge overlap detector, though.
1245 */
1246 for( int l=0; l < newpoly->loop_total; l++ )
1247 {
1248 cxr_loop *lp1 = &mesh->loops[ newpoly->loop_start+l ];
1249 cxr_polygon *future_face = &mesh->polys[ lp1->poly_right ];
1250
1251 if( reflex_edges[ lp1->edge_index ]
1252 || lp1->poly_right == loop->poly_right )
1253 goto dont_check;
1254
1255 for( int m=0; m<solid_len; m++ )
1256 if( solid[m] == lp1->poly_right )
1257 goto dont_check;
1258
1259 for( int m=0; m<solid_len; m++ )
1260 {
1261 cxr_polygon *polym = &mesh->polys[solid[m]];
1262 double pdist = v3_dot( polym->normal,future_face->normal);
1263
1264 if( pdist > CXR_PLANE_SIMILARITY_MAX )
1265 goto dont_check;
1266 }
1267
1268 dont_check:;
1269 }
1270
1271 /* Check for vertices in the new polygon that exist on a current
1272 * plane. This condition is invalid */
1273 solid[ solid_len ] = loop->poly_right;
1274
1275 if( cxr_valid_solid(mesh,solid,solid_len+1 ) )
1276 {
1277 faces_tagged[ loop->poly_right ] = faceid;
1278 changed = 1;
1279 solid_len ++;
1280 }
1281 }
1282
1283 skip_plane:;
1284 }
1285 }
1286 }
1287 search_start = solid_len;
1288 if(changed)
1289 goto search_iterate;
1290
1291 return solid_len;
1292 }
1293
1294 struct csolid
1295 {
1296 int start, count, edge_count;
1297 v3f center;
1298 };
1299
1300 struct temp_manifold
1301 {
1302 struct manifold_loop
1303 {
1304 cxr_loop loop;
1305 int split;
1306 }
1307 *loops;
1308
1309 int loop_count,
1310 split_count;
1311
1312 enum manifold_status
1313 {
1314 k_manifold_err,
1315 k_manifold_none,
1316 k_manifold_fragmented,
1317 k_manifold_complete,
1318 }
1319 status;
1320 };
1321
1322 /*
1323 * Create polygon from entire manifold structure.
1324 *
1325 * Must be completely co-planar
1326 */
1327 static void cxr_create_poly_full( cxr_mesh *mesh, struct temp_manifold *src )
1328 {
1329 if( cxr_create_poly( mesh, src->loop_count ) )
1330 {
1331 for( int l=0; l<src->loop_count; l++ )
1332 cxr_poly_push_index( mesh, src->loops[ l ].loop.index);
1333
1334 cxr_poly_finish( mesh );
1335 }
1336 }
1337
1338 /*
1339 * Links up all edges into a potential new manifold
1340 *
1341 * The return status can be:
1342 * (err): Critical programming error
1343 * none: No manifold to create
1344 * fragmented: Multiple sections exist, not just one
1345 * complete: Optimial manifold was created
1346 */
1347 static void cxr_link_manifold(
1348 cxr_mesh *mesh,
1349 struct csolid *solid,
1350 int *solid_buffer,
1351 struct temp_manifold *manifold
1352 ){
1353 cxr_loop **edge_list = malloc( sizeof(*edge_list) * solid->edge_count );
1354 int *temp_solid = malloc( solid->count *sizeof(int) );
1355 int temp_solid_len = 0;
1356
1357 int init_reverse = 0;
1358 int unique_edge_count = 0;
1359
1360 /* Try remove splitting faces first */
1361 {
1362 int split_total = 0;
1363 for( int j=0; j<solid->count; j++ )
1364 {
1365 cxr_polygon *poly = &mesh->polys[ solid_buffer[solid->start+j] ];
1366 int interior_count = 0;
1367
1368 for( int k=0; k<poly->loop_total; k++ )
1369 {
1370 cxr_loop *loop = &mesh->loops[ poly->loop_start+k ];
1371
1372 for( int l=0; l<solid->count; l++ )
1373 if( loop->poly_right == solid_buffer[solid->start+l] )
1374 {
1375 interior_count ++;
1376 goto next;
1377 }
1378
1379 next:;
1380 }
1381
1382 if( interior_count < poly->loop_total-1 )
1383 {
1384 split_total ++;
1385 continue;
1386 }
1387
1388 temp_solid[ temp_solid_len ++ ] = solid_buffer[solid->start+j];
1389 }
1390
1391 if( temp_solid_len < 3 || (split_total & 0x2) /* unkown reasons */ )
1392 {
1393 }
1394 else
1395 {
1396 /* Overwrite original solid */
1397 for( int j=0; j<temp_solid_len; j++ )
1398 solid_buffer[ solid->start+j ] = temp_solid[ j ];
1399
1400 solid->count = temp_solid_len;
1401 }
1402
1403 free( temp_solid );
1404 }
1405
1406 for( int j=0; j<solid->count; j++ )
1407 {
1408 cxr_polygon *poly = &mesh->polys[ solid_buffer[solid->start+j] ];
1409
1410 /* when discarding, if a face has only one loop that points outwards,
1411 * we keep it */
1412
1413
1414 for( int k=0; k<poly->loop_total; k++ )
1415 {
1416 cxr_loop *loop = &mesh->loops[ poly->loop_start+k ];
1417
1418 for( int l=0; l<unique_edge_count; l++ )
1419 if( edge_list[l]->edge_index == loop->edge_index )
1420 goto skip_edge;
1421
1422 for( int l=0; l<solid->count; l++ )
1423 if( loop->poly_right == solid_buffer[solid->start+l] )
1424 goto skip_edge;
1425
1426 edge_list[ unique_edge_count ] = loop;
1427
1428 if( unique_edge_count == 0 )
1429 {
1430 cxr_edge *edgeptr = &mesh->edges[ loop->edge_index ];
1431 if( edgeptr->i1 == loop->index )
1432 init_reverse = 1;
1433 }
1434
1435 unique_edge_count ++;
1436 skip_edge:;
1437 }
1438 }
1439
1440 if( unique_edge_count == 0 )
1441 {
1442 free( edge_list );
1443 manifold->status = k_manifold_none;
1444 return;
1445 }
1446
1447 /* Link edges together to form manifold */
1448 manifold->loops = malloc( solid->edge_count*sizeof(struct manifold_loop));
1449 manifold->split_count = 0;
1450 manifold->loop_count = 0;
1451
1452 cxr_edge *current = &mesh->edges[ edge_list[0]->edge_index ];
1453
1454 int endpt = (!init_reverse)? current->i0: current->i1,
1455 start = endpt,
1456 curface = edge_list[0]->poly_left;
1457
1458 manifold_continue:
1459 for( int j=0; j<unique_edge_count; j++ )
1460 {
1461 cxr_edge *other = &mesh->edges[ edge_list[j]->edge_index ];
1462 if( other == current )
1463 continue;
1464
1465 if( other->i0 == endpt || other->i1 == endpt )
1466 {
1467 current = other;
1468 int lastpt = endpt;
1469
1470 if( other->i0 == endpt ) endpt = current->i1;
1471 else endpt = current->i0;
1472
1473 struct manifold_loop *ml = &manifold->loops[ manifold->loop_count ++ ];
1474
1475 if( curface==edge_list[j]->poly_left )
1476 {
1477 ml->split = 1;
1478 manifold->split_count ++;
1479 }
1480 else
1481 ml->split = 0;
1482
1483 ml->loop.edge_index = edge_list[j]->edge_index;
1484 ml->loop.poly_left = edge_list[j]->poly_left;
1485 ml->loop.index = lastpt;
1486 ml->loop.poly_right = edge_list[j]->poly_right;
1487
1488 curface = edge_list[j]->poly_left;
1489
1490 if(endpt == start)
1491 {
1492 if( manifold->loop_count < unique_edge_count )
1493 manifold->status = k_manifold_fragmented;
1494 else
1495 manifold->status = k_manifold_complete;
1496
1497 goto manifold_complete;
1498 }
1499
1500 goto manifold_continue;
1501 }
1502 }
1503
1504 /* Incomplete links */
1505 manifold->status = k_manifold_err;
1506
1507 manifold_complete:
1508
1509 free( edge_list );
1510 return;
1511 }
1512
1513 /*
1514 * Reconstruct implied internal geometry where the manifold doesn't have
1515 * enough information (vertices) to create a full result.
1516 */
1517 static int cxr_build_implicit_geo( cxr_mesh *mesh, int new_polys, int start )
1518 {
1519 for( int i=0; i<new_polys-2; i++ )
1520 {
1521 for( int j=i+1; j<new_polys-1; j++ )
1522 {
1523 for( int k=j+1; k<new_polys; k++ )
1524 {
1525 cxr_polygon *ptri = &mesh->polys[ start+i ],
1526 *ptrj = &mesh->polys[ start+j ],
1527 *ptrk = &mesh->polys[ start+k ];
1528
1529 v4f planei, planej, planek;
1530 normal_to_plane(ptri->normal,ptri->center,planei);
1531 normal_to_plane(ptrj->normal,ptrj->center,planej);
1532 normal_to_plane(ptrk->normal,ptrk->center,planek);
1533
1534 v3f intersect;
1535
1536 if( plane_intersect(planei,planej,planek,intersect) )
1537 {
1538 /* Make sure the point is inside the convex region */
1539
1540 int point_valid = 1;
1541 for( int l=0; l<mesh->abpolys.count; l++ )
1542 {
1543 cxr_polygon *ptrl = &mesh->polys[l];
1544 v4f planel;
1545
1546 normal_to_plane(ptrl->normal, ptrl->center, planel);
1547
1548 if( plane_polarity( planel, intersect ) > 0.01 )
1549 {
1550 #ifdef CXR_DEBUG
1551 cxr_log( "degen vert, planes %d, %d, %d [max:%d]\n",
1552 i,j,k, new_polys );
1553
1554 cxr_debug_poly( mesh, ptri, colours_random[3] );
1555 cxr_debug_poly( mesh, ptrj, colours_random[1] );
1556 cxr_debug_poly( mesh, ptrk, colours_random[2] );
1557 #endif
1558
1559 return 0;
1560 }
1561 }
1562
1563 /* Extend faces to include this vert */
1564
1565 int nvertid = mesh->p_abverts->count;
1566 cxr_ab_push( mesh->p_abverts, intersect );
1567
1568 ptrj->loop_start += 1;
1569 ptrk->loop_start += 2;
1570
1571 cxr_ab_reserve( &mesh->abloops, 3);
1572
1573 int newi = ptri->loop_start+ptri->loop_total,
1574 newj = ptrj->loop_start+ptrj->loop_total,
1575 newk = ptrk->loop_start+ptrk->loop_total;
1576
1577 cxr_loop
1578 *lloopi = cxr_ab_empty_at(&mesh->abloops, newi),
1579 *lloopj = cxr_ab_empty_at(&mesh->abloops, newj),
1580 *lloopk = cxr_ab_empty_at(&mesh->abloops, newk);
1581
1582 lloopi->index = nvertid;
1583 lloopi->edge_index = 0;
1584 lloopi->poly_left = start + i;
1585 lloopi->poly_right = -1;
1586
1587 lloopj->index = nvertid;
1588 lloopj->poly_left = start + j;
1589 lloopj->edge_index = 0;
1590 lloopj->poly_right = -1;
1591
1592 lloopk->index = nvertid;
1593 lloopk->edge_index = 0;
1594 lloopk->poly_left = start + k;
1595 lloopk->poly_right = -1;
1596
1597 v2_zero(lloopi->uv);
1598 v2_zero(lloopj->uv);
1599 v2_zero(lloopk->uv);
1600
1601 ptri->loop_total ++;
1602 ptrj->loop_total ++;
1603 ptrk->loop_total ++;
1604
1605 double qi = 1.0/(double)ptri->loop_total,
1606 qj = 1.0/(double)ptrj->loop_total,
1607 qk = 1.0/(double)ptrk->loop_total;
1608
1609 /* Adjust centers of faces */
1610 v3_lerp( ptri->center, intersect, qi, ptri->center );
1611 v3_lerp( ptrj->center, intersect, qj, ptrj->center );
1612 v3_lerp( ptrk->center, intersect, qk, ptrk->center );
1613 }
1614 }
1615 }
1616 }
1617
1618 return 1;
1619 }
1620
1621 static int cxr_reflex_err( cxr_mesh *mesh )
1622 {
1623 int error = 0;
1624 int *reflex_check = cxr_mesh_reflex_edges( mesh );
1625
1626 v3f *temp = cxr_ab_ptr(mesh->p_abverts, 0);
1627
1628 for( int i=0; i<mesh->abedges.count; i++ )
1629 {
1630 if( reflex_check[i] )
1631 {
1632 cxr_debug_line( temp[mesh->edges[i].i0],
1633 temp[mesh->edges[i].i1],
1634 colour_error );
1635 error ++;
1636 }
1637 }
1638
1639 free( reflex_check );
1640 return error;
1641 }
1642
1643 static int cxr_non_manifold_err( cxr_mesh *mesh )
1644 {
1645 if( !cxr_mesh_link_loops(mesh) )
1646 {
1647 #ifdef CXR_DEBUG
1648 cxr_log( "non-manifold edges are in the mesh: "
1649 "implicit internal geometry does not have full support\n" );
1650
1651 v3f *verts = cxr_ab_ptr( mesh->p_abverts, 0 );
1652
1653 for( int i=0; i<mesh->abloops.count; i++ )
1654 {
1655 cxr_loop *lp = &mesh->loops[i];
1656 cxr_edge *edge = &mesh->edges[lp->edge_index];
1657 cxr_debug_line( verts[edge->i0], verts[edge->i1], colours_random[1] );
1658
1659 if( lp->poly_left == -1 || lp->poly_right == -1 )
1660 {
1661 cxr_debug_line( verts[edge->i0], verts[edge->i1], colour_error );
1662 }
1663 }
1664 #endif
1665 return 1;
1666 }
1667
1668 return 0;
1669 }
1670
1671 /*
1672 * Convexer's main algorithm
1673 *
1674 * Return the best availible convex solid from mesh, and patch the existing mesh
1675 * to fill the gap where the new mesh left it.
1676 *
1677 * Returns NULL if shape is already convex or empty.
1678 * This function will not preserve edge data such as freestyle, sharp etc.
1679 */
1680 static cxr_mesh *cxr_pull_best_solid(
1681 cxr_mesh *mesh,
1682 int preserve_more_edges,
1683 enum cxr_soliderr *err )
1684 {
1685 *err = k_soliderr_none;
1686
1687 if( cxr_non_manifold_err( mesh ) )
1688 {
1689 *err = k_soliderr_non_manifold;
1690 return NULL;
1691 }
1692
1693 int *edge_tagged = cxr_mesh_reflex_edges( mesh );
1694 int *vertex_tagged = cxr_mesh_reflex_vertices( mesh );
1695
1696 /*
1697 * Connect all marked vertices that share an edge
1698 */
1699
1700 int *edge_important = malloc(mesh->abedges.count*sizeof(int));
1701 for( int i=0; i< mesh->abedges.count; i++ )
1702 edge_important[i] = 0;
1703
1704 for( int i=0; i<mesh->abpolys.count; i ++ )
1705 {
1706 cxr_polygon *poly = &mesh->polys[i];
1707 int not_tagged = -1,
1708 tag_count = 0;
1709
1710 for( int j=0; j<poly->loop_total; j++ )
1711 {
1712 cxr_loop *loop = &mesh->loops[ poly->loop_start+j ];
1713
1714 if( !edge_tagged[ loop->edge_index ] )
1715 {
1716 if( not_tagged == -1 )
1717 not_tagged = loop->edge_index;
1718 else
1719 goto edge_unimportant;
1720 }
1721 }
1722
1723 if( not_tagged != -1 )
1724 edge_important[not_tagged]=1;
1725
1726 edge_unimportant:;
1727 }
1728
1729 /*
1730 * Connect edges where both vertices are reflex, only if we are not
1731 * preserving them
1732 */
1733 for( int i=0; i<mesh->abedges.count; i ++ )
1734 {
1735 if( edge_important[i] && preserve_more_edges ) continue;
1736
1737 cxr_edge *edge = &mesh->edges[i];
1738 if( vertex_tagged[edge->i0] && vertex_tagged[edge->i1] )
1739 edge_tagged[i] = 1;
1740 }
1741
1742 free( edge_important );
1743
1744 int *faces_tagged = malloc(mesh->abpolys.count*sizeof(int));
1745 for( int i=0; i<mesh->abpolys.count; i++ )
1746 faces_tagged[i] = -1;
1747
1748 struct csolid *candidates;
1749 int *solid_buffer = malloc( mesh->abpolys.count*sizeof(int) ),
1750 solid_buffer_len = 0,
1751 candidate_count = 0;
1752
1753 candidates = malloc( mesh->abpolys.count *sizeof(struct csolid) );
1754
1755 /*
1756 * Create a valid, non-overlapping solid for every face present in the mesh
1757 */
1758 for( int i=0; i<mesh->abpolys.count; i++ )
1759 {
1760 if( faces_tagged[i] != -1 ) continue;
1761 faces_tagged[i] = i;
1762
1763 int *solid = &solid_buffer[ solid_buffer_len ];
1764 int len = cxr_buildsolid( mesh, i, solid, edge_tagged, faces_tagged );
1765
1766 /* add entry */
1767 struct csolid *csolid = &candidates[candidate_count ++];
1768 csolid->start = solid_buffer_len;
1769 csolid->count = len;
1770 csolid->edge_count = 0;
1771
1772 v3_zero( csolid->center );
1773 for( int j=0; j<len; j++ )
1774 {
1775 cxr_polygon *polyj = &mesh->polys[ solid[j] ];
1776 v3_add( polyj->center, csolid->center, csolid->center );
1777 csolid->edge_count += polyj->loop_total;
1778 }
1779 v3_divs( csolid->center, len, csolid->center );
1780 solid_buffer_len += len;
1781 }
1782
1783 free( edge_tagged );
1784 free( vertex_tagged );
1785 free( faces_tagged );
1786
1787 /*
1788 * Choosing the best solid: most defined manifold
1789 */
1790 struct csolid *best_solid = NULL;
1791 int fewest_manifold_splits = INT32_MAX;
1792
1793 struct temp_manifold best_manifold = { .loops = NULL, .loop_count = 0 };
1794 int max_solid_faces = 0;
1795
1796 for( int i=0; i<candidate_count; i++ )
1797 {
1798 struct csolid *solid = &candidates[i];
1799 max_solid_faces = cxr_max(max_solid_faces,solid->count);
1800
1801 if( solid->count <= 2 )
1802 continue;
1803
1804 struct temp_manifold manifold;
1805 cxr_link_manifold( mesh, solid, solid_buffer, &manifold);
1806
1807 if( manifold.status == k_manifold_err )
1808 {
1809 *err = k_soliderr_bad_manifold;
1810
1811 free(solid_buffer);
1812 free(candidates);
1813 free(manifold.loops);
1814 free(best_manifold.loops);
1815 return NULL;
1816 }
1817
1818 if( manifold.status == k_manifold_complete )
1819 {
1820 if( manifold.split_count < fewest_manifold_splits )
1821 {
1822 fewest_manifold_splits = manifold.split_count;
1823 best_solid = solid;
1824
1825 free( best_manifold.loops );
1826 best_manifold = manifold;
1827 continue;
1828 }
1829 }
1830
1831 if( manifold.status != k_manifold_none )
1832 free( manifold.loops );
1833 }
1834
1835 if( max_solid_faces < 2 )
1836 {
1837 *err = k_soliderr_no_solids;
1838 free(solid_buffer);
1839 free(candidates);
1840 free(best_manifold.loops);
1841 return NULL;
1842 }
1843
1844 if( best_solid != NULL )
1845 {
1846 cxr_mesh *pullmesh = cxr_alloc_mesh( best_solid->edge_count,
1847 best_solid->edge_count,
1848 best_solid->count,
1849 mesh->p_abverts );
1850
1851 for( int i=0; i<best_solid->count; i++ )
1852 {
1853 int nface_id = pullmesh->abpolys.count;
1854 int exist_plane_id = solid_buffer[best_solid->start+i];
1855
1856 cxr_polygon *exist_face = &mesh->polys[ exist_plane_id ],
1857 *new_face = cxr_ab_empty( &pullmesh->abpolys );
1858
1859 *new_face = *exist_face;
1860 new_face->loop_start = pullmesh->abloops.count;
1861
1862 for( int j=0; j<exist_face->loop_total; j++ )
1863 {
1864 cxr_loop *exist_loop = &mesh->loops[ exist_face->loop_start+j ],
1865 *new_loop = cxr_ab_empty(&pullmesh->abloops);
1866
1867 new_loop->index = exist_loop->index;
1868 new_loop->poly_left = nface_id;
1869 new_loop->poly_right = -1;
1870 new_loop->edge_index = 0;
1871 v2_copy( exist_loop->uv, new_loop->uv );
1872 }
1873
1874 exist_face->loop_total = -1;
1875 }
1876
1877 int new_polys = 0;
1878 int pullmesh_new_start = pullmesh->abpolys.count;
1879
1880 if( fewest_manifold_splits != 0 )
1881 {
1882 /* Unusual observation:
1883 * If the split count is odd, the manifold can be created easily
1884 *
1885 * If it is even, implicit internal geometry is needed to be
1886 * constructed. So the manifold gets folded as we create it segment
1887 * by segment.
1888 *
1889 * I'm not sure if this is a well defined rule of geometry, but seems
1890 * to apply to the data we care about.
1891 */
1892 int collapse_used_segments = (u32)fewest_manifold_splits & 0x1? 0: 1;
1893
1894 manifold_repeat:
1895
1896 for( int j=0; j < best_manifold.loop_count; j++ )
1897 {
1898 if( !best_manifold.loops[j].split ) continue;
1899
1900 cxr_loop *loop = &best_manifold.loops[j].loop;
1901
1902 for( int k=1; k< best_manifold.loop_count; k++ )
1903 {
1904 int index1 = cxr_range(j+k, best_manifold.loop_count );
1905 cxr_loop *loop1 = &best_manifold.loops[index1].loop;
1906
1907 if( best_manifold.loops[index1].split )
1908 {
1909 if( k==1 )
1910 break;
1911
1912 new_polys ++;
1913
1914 if( new_polys > best_manifold.loop_count )
1915 {
1916 #ifdef CXR_DEBUG
1917 cxr_log( "Programming error: Too many new polys!\n" );
1918 #endif
1919 exit(1);
1920 }
1921
1922 if( cxr_create_poly( pullmesh, k+1 ) )
1923 {
1924 for( int l=0; l<k+1; l++ )
1925 {
1926 int i0 = cxr_range(j+l, best_manifold.loop_count ),
1927 index = best_manifold.loops[ i0 ].loop.index;
1928
1929 cxr_poly_push_index( pullmesh, index );
1930 }
1931 cxr_poly_finish( pullmesh );
1932 }
1933
1934 /* Collapse down manifold */
1935 if( collapse_used_segments )
1936 {
1937 best_manifold.loops[j].split = 0;
1938 best_manifold.loops[index1].split = 0;
1939
1940 int new_length = (best_manifold.loop_count-(k-1));
1941
1942 struct temp_manifold new_manifold = {
1943 .loop_count = new_length
1944 };
1945 new_manifold.loops =
1946 malloc( new_length*sizeof(*new_manifold.loops) );
1947
1948 for( int l=0; l<new_length; l ++ )
1949 {
1950 int i_src = cxr_range( j+k+l, best_manifold.loop_count);
1951 new_manifold.loops[l] = best_manifold.loops[i_src];
1952 }
1953
1954 free( best_manifold.loops );
1955 best_manifold = new_manifold;
1956
1957 goto manifold_repeat;
1958 }
1959
1960 j=j+k-1;
1961 break;
1962 }
1963 }
1964 }
1965
1966 if( best_manifold.loop_count && collapse_used_segments )
1967 {
1968 cxr_create_poly_full( pullmesh, &best_manifold );
1969 new_polys ++;
1970 }
1971 }
1972 else
1973 {
1974 cxr_create_poly_full( pullmesh, &best_manifold );
1975 new_polys = 1;
1976 }
1977
1978 if( new_polys >= 3 )
1979 {
1980 if( !cxr_build_implicit_geo( pullmesh, new_polys, pullmesh_new_start ))
1981 {
1982 free(solid_buffer);
1983 free(candidates);
1984 free(best_manifold.loops);
1985
1986 cxr_free_mesh( pullmesh );
1987 *err = k_soliderr_degenerate_implicit;
1988 return NULL;
1989 }
1990 }
1991
1992 /*
1993 * Copy faces from the pullmesh into original, to patch up where there
1994 * would be gaps created
1995 */
1996 for( int i=0; i<new_polys; i++ )
1997 {
1998 int rface_id = mesh->abpolys.count;
1999 cxr_polygon *pface = &pullmesh->polys[pullmesh_new_start+i],
2000 *rip_face = cxr_ab_empty(&mesh->abpolys);
2001
2002 rip_face->loop_start = mesh->abloops.count;
2003 rip_face->loop_total = pface->loop_total;
2004 rip_face->material_id = -1;
2005
2006 for( int j=0; j<rip_face->loop_total; j++ )
2007 {
2008 cxr_loop *ploop =
2009 &pullmesh->loops[ pface->loop_start+pface->loop_total-j-1 ],
2010 *rloop = cxr_ab_empty(&mesh->abloops);
2011
2012 rloop->index = ploop->index;
2013 rloop->poly_left = rface_id;
2014 rloop->poly_right = -1;
2015 rloop->edge_index = 0;
2016 v2_copy( ploop->uv, rloop->uv );
2017 }
2018
2019 v3_copy( pface->center, rip_face->center );
2020 v3_negate( pface->normal, rip_face->normal );
2021 }
2022
2023 cxr_mesh_update( mesh );
2024 cxr_mesh_update( pullmesh );
2025
2026 cxr_mesh_clean_faces( mesh );
2027 cxr_mesh_clean_edges( mesh );
2028 cxr_mesh_clean_faces( pullmesh );
2029 cxr_mesh_clean_edges( pullmesh );
2030
2031 free(solid_buffer);
2032 free(candidates);
2033 free(best_manifold.loops);
2034
2035 /*
2036 * Do final checks on the mesh to make sure we diddn't introduce any
2037 * errors
2038 */
2039 if( cxr_non_manifold_err( pullmesh ) || cxr_reflex_err( pullmesh ) )
2040 {
2041 *err = k_soliderr_bad_result;
2042 return NULL;
2043 }
2044
2045 return pullmesh;
2046 }
2047
2048 free(solid_buffer);
2049 free(candidates);
2050 free(best_manifold.loops);
2051
2052 if( cxr_non_manifold_err( mesh ) || cxr_reflex_err( mesh ) )
2053 *err = k_soliderr_bad_result;
2054
2055 return NULL;
2056 }
2057
2058 /*
2059 * Convert from the format we recieve from blender into our internal format
2060 * with auto buffers.
2061 */
2062 static cxr_mesh *cxr_to_internal_format(
2063 cxr_static_mesh *src,
2064 cxr_abuffer *abverts
2065 ){
2066 cxr_mesh *mesh = cxr_alloc_mesh( src->edge_count, src->loop_count,
2067 src->poly_count, abverts );
2068
2069 cxr_ab_init( abverts, sizeof(v3f), src->vertex_count );
2070
2071 memcpy( mesh->abedges.arr, src->edges, src->edge_count*sizeof(cxr_edge));
2072 memcpy( mesh->abpolys.arr, src->polys, src->poly_count*sizeof(cxr_polygon));
2073 memcpy( abverts->arr, src->vertices, src->vertex_count*sizeof(v3f));
2074 mesh->abedges.count = src->edge_count;
2075 mesh->abloops.count = src->loop_count;
2076 mesh->abpolys.count = src->poly_count;
2077
2078 cxr_mesh_update( mesh );
2079
2080 for( int i=0; i<src->loop_count; i++ )
2081 {
2082 cxr_loop *lp = &mesh->loops[i];
2083
2084 lp->index = src->loops[i].index;
2085 lp->edge_index = src->loops[i].edge_index;
2086 v2_copy( src->loops[i].uv, lp->uv );
2087 }
2088
2089 abverts->count = src->vertex_count;
2090 return mesh;
2091 }
2092
2093 static int cxr_poly_convex( cxr_mesh *mesh, cxr_polygon *poly )
2094 {
2095 v3f *verts = cxr_ab_ptr( mesh->p_abverts, 0 );
2096
2097 for( int i=0; i<poly->loop_total; i++ )
2098 {
2099 int li0 = poly->loop_start + i,
2100 li1 = poly->loop_start + cxr_range( i+1, poly->loop_total ),
2101 li2 = poly->loop_start + cxr_range( i+2, poly->loop_total );
2102 int i0 = mesh->loops[li0].index,
2103 i1 = mesh->loops[li1].index,
2104 i2 = mesh->loops[li2].index;
2105
2106 v3f v0, v1, c;
2107
2108 v3_sub( verts[i1], verts[i0], v0 );
2109 v3_sub( verts[i2], verts[i1], v1 );
2110
2111 v3_cross( v0, v1, c );
2112 if( v3_dot( c, poly->normal ) <= 0.0 )
2113 {
2114 #if CXR_DEBUG
2115 cxr_debug_line( verts[i0], verts[i1], colour_error );
2116 cxr_debug_box( verts[i1], 0.1, colour_error );
2117 cxr_debug_line( verts[i1], verts[i2], colour_error );
2118 cxr_debug_line( verts[i1], poly->center, colour_error );
2119 #endif
2120 return 0;
2121 }
2122 }
2123
2124 return 1;
2125 }
2126
2127 static int cxr_solid_checkerr( cxr_mesh *mesh )
2128 {
2129 v3f *verts = cxr_ab_ptr( mesh->p_abverts, 0 );
2130 int err_count = 0;
2131
2132 for( int i=0; i<mesh->abpolys.count; i++ )
2133 {
2134 int plane_err = 0;
2135
2136 cxr_polygon *poly = &mesh->polys[i];
2137 v4f plane;
2138
2139 normal_to_plane( poly->normal, poly->center, plane );
2140
2141 for( int j=0; j<poly->loop_total; j++ )
2142 {
2143 cxr_loop *loop = &mesh->loops[ poly->loop_start+j ];
2144 double *vert = verts[ loop->index ];
2145
2146 if( fabs(plane_polarity(plane,vert)) > 0.0025 )
2147 {
2148 err_count ++;
2149 plane_err ++;
2150
2151 v3f ref;
2152 plane_project_point( plane, vert, ref );
2153
2154 #ifdef CXR_DEBUG
2155 cxr_debug_line( ref, vert, colour_error );
2156 cxr_debug_box( vert, 0.1, colour_error );
2157 #endif
2158 }
2159 }
2160
2161 #ifdef CXR_DEBUG
2162 if( plane_err )
2163 cxr_debug_poly( mesh, poly, colour_error );
2164 #endif
2165 }
2166
2167 return err_count;
2168 }
2169
2170 CXR_API void cxr_free_world( cxr_world *world )
2171 {
2172 for( int i=0; i<world->absolids.count; i++ )
2173 {
2174 cxr_solid *solid = cxr_ab_ptr( &world->absolids, i );
2175 cxr_free_mesh( solid->pmesh );
2176 }
2177
2178 cxr_ab_free( &world->abverts );
2179 cxr_ab_free( &world->absolids );
2180
2181 if( world->materials )
2182 {
2183 for( int i=0; i<world->material_count; i++ )
2184 free( world->materials[i].name );
2185
2186 free( world->materials );
2187 }
2188 free( world );
2189 }
2190
2191 CXR_API cxr_tri_mesh *cxr_world_preview( cxr_world *world )
2192 {
2193 cxr_tri_mesh *out = malloc( sizeof(cxr_tri_mesh) );
2194 out->vertex_count = 0;
2195 out->indices_count = 0;
2196
2197 for( int i=0; i<world->absolids.count; i++ )
2198 {
2199 cxr_solid *solid = cxr_ab_ptr( &world->absolids, i );
2200 cxr_mesh *mesh = solid->pmesh;
2201
2202 for( int j=0; j<mesh->abpolys.count; j ++ )
2203 {
2204 cxr_polygon *poly = &mesh->polys[j];
2205
2206 out->vertex_count += poly->loop_total * 3; /* Polygon, edge strip */
2207 out->indices_count += (poly->loop_total -2) * 3; /* Polygon */
2208 out->indices_count += poly->loop_total * 2 * 3; /* Edge strip */
2209 }
2210 }
2211
2212 out->colours = malloc( sizeof(v4f)*out->vertex_count );
2213 out->vertices = malloc( sizeof(v3f)*out->vertex_count );
2214 out->indices = malloc( sizeof(i32)*out->indices_count );
2215
2216 v3f *overts = out->vertices;
2217 v4f *colours = out->colours;
2218 i32 *indices = out->indices;
2219
2220 int vi = 0,
2221 ii = 0;
2222
2223 for( int i=0; i<world->absolids.count; i++ )
2224 {
2225 cxr_solid *solid = cxr_ab_ptr( &world->absolids, i );
2226 cxr_mesh *mesh = solid->pmesh;
2227
2228 v3f *verts = cxr_ab_ptr( mesh->p_abverts, 0 );
2229 v4f colour;
2230
2231 colour_random_brush( i, colour );
2232
2233 for( int j=0; j<mesh->abpolys.count; j ++ )
2234 {
2235 cxr_polygon *poly = &mesh->polys[j];
2236
2237 int istart = vi;
2238
2239 for( int k=0; k<poly->loop_total-2; k++ )
2240 {
2241 int i0 = 0,
2242 i1 = (k+1)*3,
2243 i2 = (k+2)*3;
2244
2245 indices[ ii ++ ] = istart+i0;
2246 indices[ ii ++ ] = istart+i1;
2247 indices[ ii ++ ] = istart+i2;
2248 }
2249
2250 for( int k=0; k<poly->loop_total; k++ )
2251 {
2252 cxr_loop *lp = &mesh->loops[poly->loop_start+k];
2253
2254 int i0r = k*3+1,
2255 i1r = cxr_range(k+1,poly->loop_total)*3+1,
2256 i0i = k*3+2,
2257 i1i = cxr_range(k+1,poly->loop_total)*3+2;
2258
2259 indices[ ii ++ ] = istart+i0i;
2260 indices[ ii ++ ] = istart+i1i;
2261 indices[ ii ++ ] = istart+i1r;
2262
2263 indices[ ii ++ ] = istart+i0i;
2264 indices[ ii ++ ] = istart+i1r;
2265 indices[ ii ++ ] = istart+i0r;
2266
2267 /* Main */
2268 v3_muladds( verts[lp->index], poly->normal, 0.02, overts[vi] );
2269 v4_copy( colour, colours[ vi ] );
2270 vi ++;
2271
2272 /* Trim */
2273 v3f inner;
2274 v3_lerp( verts[lp->index], poly->center, 0.2, inner );
2275 v3_muladds( inner, poly->normal, 0.015, overts[ vi ] );
2276 v4_copy( colour, colours[ vi ] );
2277 v4_copy( (v4f){ 0.0, 0.0, 0.0, 0.0 }, colours[vi] );
2278 vi ++;
2279
2280 v3_muladds(verts[lp->index], poly->normal, 0.0, overts[ vi ] );
2281 v4_copy( colour, colours[ vi ] );
2282 v4_copy( (v4f){ 1.0, 1.0, 1.0, 0.125 }, colours[vi] );
2283 vi ++;
2284 }
2285 }
2286 }
2287
2288 return out;
2289 }
2290
2291 CXR_API void cxr_free_tri_mesh( cxr_tri_mesh *mesh )
2292 {
2293 free( mesh->colours );
2294 free( mesh->indices );
2295 free( mesh->vertices );
2296 free( mesh );
2297 }
2298
2299 CXR_API cxr_world *cxr_decompose( cxr_static_mesh *src, i32 *perrcode )
2300 {
2301 /* Make sure data is in the mesh and isn't empty */
2302 if( !src->edge_count || !src->loop_count || !src->poly_count )
2303 {
2304 cxr_log( "Error %d\n", k_soliderr_invalid_input );
2305 if( perrcode )
2306 *perrcode = k_soliderr_invalid_input;
2307
2308 return NULL;
2309 }
2310
2311 u32 error = 0x00;
2312 cxr_world *world = malloc( sizeof(*world) );
2313
2314 /* Copy data to internal formats */
2315 cxr_mesh *main_mesh = cxr_to_internal_format( src, &world->abverts );
2316 cxr_ab_init( &world->absolids, sizeof(cxr_solid), 2 );
2317
2318 if( src->material_count )
2319 {
2320 size_t dsize = sizeof(cxr_material) * src->material_count;
2321 world->materials = malloc( dsize );
2322 memcpy( world->materials, src->materials, dsize );
2323
2324 for( int i=0; i<src->material_count; i++ )
2325 {
2326 world->materials[i].name = malloc(strlen(src->materials[i].name) +1);
2327 strcpy( world->materials[i].name, src->materials[i].name );
2328 }
2329 world->material_count = src->material_count;
2330 }
2331 else world->materials = NULL;
2332
2333 int invalid_count = 0;
2334
2335 /*
2336 * Preprocessor 1: Island seperation
2337 */
2338 while(1)
2339 {
2340 cxr_mesh *res = cxr_pull_island( main_mesh );
2341 if( res )
2342 {
2343 cxr_ab_push( &world->absolids, &(cxr_solid){ res, 0, 0 });
2344 }
2345 else break;
2346 }
2347 cxr_ab_push( &world->absolids, &(cxr_solid){ main_mesh, 0, 0 } );
2348
2349 /*
2350 * Preprocessor 2: Displacement processing & error checks
2351 */
2352 for( int i=0; i<world->absolids.count; i++ )
2353 {
2354 cxr_solid *pinf = cxr_ab_ptr(&world->absolids,i);
2355
2356 for( int j=0; j<pinf->pmesh->abpolys.count; j++ )
2357 {
2358 cxr_polygon *poly = &pinf->pmesh->polys[ j ];
2359
2360 for( int k=0; k<poly->loop_total; k++ )
2361 {
2362 cxr_loop *lp = &pinf->pmesh->loops[ poly->loop_start+k ];
2363 cxr_edge *edge = &pinf->pmesh->edges[ lp->edge_index ];
2364
2365 if( edge->freestyle )
2366 goto displacement;
2367 }
2368
2369 if( !cxr_poly_convex( pinf->pmesh, poly ) )
2370 {
2371 pinf->invalid = 1;
2372 invalid_count ++;
2373 error = k_soliderr_non_convex_poly;
2374 }
2375 }
2376
2377 if( cxr_solid_checkerr( pinf->pmesh ) )
2378 {
2379 pinf->invalid = 1;
2380 invalid_count ++;
2381 error = k_soliderr_non_coplanar_vertices;
2382 }
2383
2384 continue;
2385
2386 displacement:
2387 pinf->displacement = 1;
2388 }
2389
2390 /*
2391 * Main convex decomp algorithm
2392 */
2393 int sources_count = world->absolids.count;
2394
2395 if( invalid_count )
2396 goto decomp_failed;
2397
2398 for( int i=0; i<sources_count; i++ )
2399 {
2400 cxr_solid pinf = *(cxr_solid *)cxr_ab_ptr(&world->absolids, i);
2401
2402 if( pinf.displacement || pinf.invalid )
2403 continue;
2404
2405 while(1)
2406 {
2407 cxr_mesh *res = cxr_pull_best_solid( pinf.pmesh, 0, &error );
2408
2409 if( res )
2410 {
2411 cxr_ab_push( &world->absolids, &(cxr_solid){ res, 0, 0 } );
2412 }
2413 else
2414 {
2415 if( error == k_soliderr_no_solids )
2416 {
2417 /* Retry if non-critical error, with extra edges */
2418 res = cxr_pull_best_solid(pinf.pmesh, 1, &error);
2419
2420 if( res )
2421 cxr_ab_push( &world->absolids, &(cxr_solid){ res, 0, 0 } );
2422 else
2423 goto decomp_failed;
2424 }
2425 else
2426 if( error )
2427 goto decomp_failed;
2428 else
2429 break;
2430 }
2431 }
2432 }
2433
2434 return world;
2435
2436 decomp_failed:
2437 cxr_log( "Error %d\n", error );
2438 cxr_free_world( world );
2439
2440 if( perrcode )
2441 *perrcode = error;
2442
2443 return NULL;
2444 }
2445
2446 /*
2447 * format specific functions: vdf, vmf, (v)bsp
2448 * ----------------------------------------------------------------------------
2449 */
2450 #ifdef CXR_VALVE_MAP_FILE
2451
2452 CXR_API cxr_vdf *cxr_vdf_open(const char *path)
2453 {
2454 cxr_vdf *vdf = malloc(sizeof(cxr_vdf));
2455
2456 vdf->level = 0;
2457 vdf->fp = fopen( path, "w" );
2458
2459 if( !vdf->fp )
2460 {
2461 free( vdf );
2462 return NULL;
2463 }
2464
2465 return vdf;
2466 }
2467
2468 CXR_API void cxr_vdf_close(cxr_vdf *vdf)
2469 {
2470 fclose( vdf->fp );
2471 free( vdf );
2472 }
2473
2474 CXR_API void cxr_vdf_put(cxr_vdf *vdf, const char *str)
2475 {
2476 for( int i=0; i<vdf->level; i++ )
2477 fputs( " ", vdf->fp );
2478
2479 fputs( str, vdf->fp );
2480 }
2481
2482 static void cxr_vdf_printf( cxr_vdf *vdf, const char *fmt, ... )
2483 {
2484 cxr_vdf_put(vdf,"");
2485
2486 va_list args;
2487 va_start( args, fmt );
2488 vfprintf( vdf->fp, fmt, args );
2489 va_end(args);
2490 }
2491
2492 CXR_API void cxr_vdf_node(cxr_vdf *vdf, const char *str)
2493 {
2494 cxr_vdf_put( vdf, str );
2495 putc( (u8)'\n', vdf->fp );
2496 cxr_vdf_put( vdf, "{\n" );
2497
2498 vdf->level ++;
2499 }
2500
2501 CXR_API void cxr_vdf_edon( cxr_vdf *vdf )
2502 {
2503 vdf->level --;
2504 cxr_vdf_put( vdf, "}\n" );
2505 }
2506
2507 CXR_API void cxr_vdf_kv( cxr_vdf *vdf, const char *strk, const char *strv )
2508 {
2509 cxr_vdf_printf( vdf, "\"%s\" \"%s\"\n", strk, strv );
2510 }
2511
2512 /*
2513 * Data-type specific Keyvalues
2514 */
2515 static void cxr_vdf_ki32( cxr_vdf *vdf, const char *strk, i32 val )
2516 {
2517 cxr_vdf_printf( vdf, "\"%s\" \"%d\"\n", strk, val );
2518 }
2519
2520 static void cxr_vdf_kdouble( cxr_vdf *vdf, const char *strk, double val )
2521 {
2522 cxr_vdf_printf( vdf, "\"%s\" \"%f\"\n", strk, val );
2523 }
2524
2525 static void cxr_vdf_kaxis( cxr_vdf *vdf, const char *strk,
2526 v3f normal, double offset, double scale
2527 ){
2528 cxr_vdf_printf( vdf, "\"%s\" \"[%f %f %f %f] %f\"\n",
2529 strk, normal[0], normal[1],normal[2], offset, scale );
2530 }
2531
2532 static void cxr_vdf_kv3f( cxr_vdf *vdf, const char *strk, v3f v )
2533 {
2534 cxr_vdf_printf( vdf, "\"%s\" \"[%f %f %f]\"\n", strk, v[0], v[1], v[2] );
2535 }
2536
2537 static void cxr_vdf_karrdouble( cxr_vdf *vdf, const char *strk,
2538 int id, double *doubles, int count
2539 ){
2540 cxr_vdf_put(vdf,"");
2541 fprintf( vdf->fp, "\"%s%d\" \"", strk, id );
2542 for( int i=0; i<count; i++ )
2543 {
2544 if( i == count-1 ) fprintf( vdf->fp, "%f", doubles[i] );
2545 else fprintf( vdf->fp, "%f ", doubles[i] );
2546 }
2547 fprintf( vdf->fp, "\"\n" );
2548 }
2549
2550 static void cxr_vdf_karrv3f( cxr_vdf *vdf, const char *strk,
2551 int id, v3f *vecs, int count
2552 ){
2553 cxr_vdf_put(vdf,"");
2554 fprintf( vdf->fp, "\"%s%d\" \"", strk, id );
2555 for( int i=0; i<count; i++ )
2556 {
2557 const char *format = i == count-1? "%f %f %f": "%f %f %f ";
2558 fprintf( vdf->fp, format, vecs[i][0], vecs[i][1], vecs[i][2] );
2559 }
2560 fprintf( vdf->fp, "\"\n" );
2561 }
2562
2563 static void cxr_vdf_plane( cxr_vdf *vdf, const char *strk, v3f a, v3f b, v3f c )
2564 {
2565 cxr_vdf_printf( vdf, "\"%s\" \"(%f %f %f) (%f %f %f) (%f %f %f)\"\n",
2566 strk, a[0], a[1], a[2], b[0], b[1], b[2], c[0], c[1], c[2] );
2567 }
2568
2569 static void cxr_vdf_colour255(cxr_vdf *vdf, const char *strk, v4f colour)
2570 {
2571 v4f scale;
2572 v4_muls( colour, 255.0, scale );
2573 cxr_vdf_printf( vdf, "\"%s\" \"%d %d %d %d\"\n",
2574 strk,(int)scale[0], (int)scale[1], (int)scale[2], (int)scale[3]);
2575 }
2576
2577 static struct cxr_material cxr_nodraw =
2578 {
2579 .res = { 512, 512 },
2580 .name = "tools/toolsnodraw"
2581 };
2582
2583 /*
2584 * Find most extreme point along a given direction
2585 */
2586 static double support_distance( v3f verts[3], v3f dir, double coef )
2587 {
2588 return cxr_maxf
2589 (
2590 coef * v3_dot( verts[0], dir ),
2591 cxr_maxf
2592 (
2593 coef * v3_dot( verts[1], dir ),
2594 coef * v3_dot( verts[2], dir )
2595 )
2596 );
2597 }
2598
2599 /*
2600 * Convert regular UV'd triangle int Source's u/vaxis vectors
2601 *
2602 * This supports affine move, scale, rotation, parallel skewing
2603 */
2604 static void cxr_calculate_axis( cxr_texinfo *transform, v3f verts[3],
2605 v2f uvs[3], v2f texture_res
2606 ){
2607 v2f tT, bT; /* Tangent/bitangent pairs for UV space and world */
2608 v3f tW, bW;
2609
2610 v2_sub( uvs[0], uvs[1], tT );
2611 v2_sub( uvs[2], uvs[1], bT );
2612 v3_sub( verts[0], verts[1], tW );
2613 v3_sub( verts[2], verts[1], bW );
2614
2615 /* Use arbitrary projection if there is no UV */
2616 if( v2_length( tT ) < 0.0001 || v2_length( bT ) < 0.0001 )
2617 {
2618 v3f uaxis, normal, vaxis;
2619
2620 v3_copy( tW, uaxis );
2621 v3_normalize( uaxis );
2622
2623 v3_cross( tW, bW, normal );
2624 v3_cross( normal, uaxis, vaxis );
2625 v3_normalize( vaxis );
2626
2627 v3_copy( uaxis, transform->uaxis );
2628 v3_copy( vaxis, transform->vaxis );
2629 v2_zero( transform->offset );
2630
2631 v2_div( (v2f){128.0, 128.0}, texture_res, transform->scale );
2632 transform->winding = 1.0;
2633 return;
2634 }
2635
2636 /* Detect if UV is reversed */
2637 double winding = v2_cross( tT, bT ) >= 0.0f? 1.0f: -1.0f;
2638
2639 /* UV projection reference */
2640 v2f vY, vX;
2641 v2_muls((v2f){1,0}, winding, vX);
2642 v2_muls((v2f){0,1}, winding, vY);
2643
2644 /* Reproject reference into world space, including skew */
2645 v3f uaxis1, vaxis1;
2646
2647 v3_muls( tW, v2_cross(vX,bT) / v2_cross(bT,tT), uaxis1 );
2648 v3_muladds( uaxis1, bW, v2_cross(vX, tT) / v2_cross(tT,bT), uaxis1 );
2649
2650 v3_muls( tW, v2_cross(vY,bT) / v2_cross(bT,tT), vaxis1 );
2651 v3_muladds( vaxis1, bW, v2_cross(vY,tT) / v2_cross(tT,bT), vaxis1 );
2652
2653 v3_normalize( uaxis1 );
2654 v3_normalize( vaxis1 );
2655
2656 /* Apply source transform to axis (yes, they also need to be swapped) */
2657 v3f norm, uaxis, vaxis;
2658
2659 v3_cross( bW, tW, norm );
2660 v3_normalize(norm);
2661 v3_cross( vaxis1, norm, uaxis );
2662 v3_cross( uaxis1, norm, vaxis );
2663
2664 /* real UV scale */
2665 v2f uvmin, uvmax, uvdelta;
2666 v2_minv( uvs[0], uvs[1], uvmin );
2667 v2_minv( uvmin, uvs[2], uvmin );
2668 v2_maxv( uvs[0], uvs[1], uvmax );
2669 v2_maxv( uvmax, uvs[2], uvmax );
2670
2671 v2_sub( uvmax, uvmin, uvdelta );
2672
2673 /* world-uv scale */
2674 v2f uvminw, uvmaxw, uvdeltaw;
2675 uvminw[0] = -support_distance( verts, uaxis, -1.0f );
2676 uvmaxw[0] = support_distance( verts, uaxis, 1.0f );
2677 uvminw[1] = -support_distance( verts, vaxis, -1.0f );
2678 uvmaxw[1] = support_distance( verts, vaxis, 1.0f );
2679
2680 v2_sub( uvmaxw, uvminw, uvdeltaw );
2681
2682 /* VMf uv scale */
2683 v2f uv_scale;
2684 v2_div( uvdeltaw, uvdelta, uv_scale );
2685 v2_div( uv_scale, texture_res, uv_scale );
2686
2687 /* Find offset via 'natural' point */
2688 v2f target_uv, natural_uv, tex_offset;
2689 v2_mul( uvs[0], texture_res, target_uv );
2690
2691 natural_uv[0] = v3_dot( uaxis, verts[0] );
2692 natural_uv[1] = -v3_dot( vaxis, verts[0] );
2693 v2_div( natural_uv, uv_scale, natural_uv );
2694
2695 tex_offset[0] = target_uv[0]-natural_uv[0];
2696 tex_offset[1] = -(target_uv[1]-natural_uv[1]);
2697
2698 /* Copy everything into output */
2699 v3_copy( uaxis, transform->uaxis );
2700 v3_copy( vaxis, transform->vaxis );
2701 v2_copy( tex_offset, transform->offset );
2702 v2_copy( uv_scale, transform->scale );
2703 transform->winding = winding;
2704 }
2705
2706 /*
2707 * Get the maximal direction of a vector, while also ignoring an axis
2708 * specified
2709 */
2710 static int cxr_cardinal( v3f a, int ignore )
2711 {
2712 int component = 0;
2713 double component_max = -CXR_BIG_NUMBER;
2714
2715 for( int i=0; i<3; i++ )
2716 {
2717 if( i == ignore ) continue;
2718
2719 if( fabs(a[i]) > component_max )
2720 {
2721 component_max = fabs(a[i]);
2722 component = i;
2723 }
2724 }
2725 double d = a[component] >= 0.0? 1.0: -1.0;
2726 v3_zero( a );
2727 a[component] = d;
2728
2729 return component;
2730 }
2731
2732 /*
2733 * Convert contiguous mesh to displacement patch
2734 */
2735 static int cxr_write_disp( cxr_mesh *mesh, cxr_world *world,
2736 cxr_vmf_context *ctx, cxr_vdf *output
2737 ){
2738 v3f *verts = cxr_ab_ptr( mesh->p_abverts, 0 );
2739
2740 struct vertinfo
2741 {
2742 int con_start, con_count;
2743 int boundary,
2744 used,
2745 search,
2746 corner;
2747
2748 double alpha;
2749 }
2750 *vertinfo = malloc( sizeof(struct vertinfo)*mesh->p_abverts->count );
2751 int *graph = malloc( sizeof(int) * mesh->abedges.count*2 );
2752
2753 int con_pos = 0;
2754 for( int i=0; i<mesh->p_abverts->count; i++ )
2755 {
2756 struct vertinfo *info = &vertinfo[i];
2757 info->con_start = con_pos;
2758 info->con_count = 0;
2759 info->boundary = 0;
2760 info->corner = 0;
2761 info->used = 0;
2762 info->search = 0;
2763 info->alpha = 0.0;
2764
2765 for( int j=0; j<mesh->abedges.count; j++ )
2766 {
2767 cxr_edge *edge = &mesh->edges[j];
2768
2769 if( edge->i0 == i || edge->i1 == i )
2770 {
2771 graph[ con_pos ++ ] = edge->i0 == i? edge->i1: edge->i0;
2772 info->con_count ++;
2773
2774 if( edge->freestyle )
2775 info->boundary = 1;
2776 }
2777 }
2778 }
2779
2780 v3f refv, refu, refn;
2781 v3_zero(refv); v3_zero(refu); v3_zero(refn);
2782
2783 /*
2784 * Approximately match the area of the result brush faces to the actual
2785 * area.
2786 *
2787 * Necessary for accuracy and even lightmap texel allocation
2788 */
2789
2790 double uv_area = 0.0, face_area = 0.0, sf;
2791 v2f uvboundmin, uvboundmax;
2792 v3f faceboundmin, faceboundmax;
2793 v2f uv_center;
2794 v3f face_center;
2795
2796 v2_fill( uvboundmin, CXR_BIG_NUMBER );
2797 v2_fill( uvboundmax, -CXR_BIG_NUMBER );
2798 v3_fill( faceboundmin, CXR_BIG_NUMBER );
2799 v3_fill( faceboundmax, -CXR_BIG_NUMBER );
2800
2801 for( int i=0; i<mesh->abpolys.count; i++ )
2802 {
2803 cxr_polygon *poly = &mesh->polys[i];
2804
2805 for( int j=0; j<poly->loop_total; j++ )
2806 {
2807 cxr_loop *lp0 = &mesh->loops[ poly->loop_start+j ];
2808 v2_minv( lp0->uv, uvboundmin, uvboundmin);
2809 v2_maxv( lp0->uv, uvboundmax, uvboundmax);
2810 v3_minv( verts[lp0->index], faceboundmin, faceboundmin );
2811 v3_maxv( verts[lp0->index], faceboundmax, faceboundmax );
2812 }
2813
2814 for( int j=0; j<poly->loop_total-2; j++ )
2815 {
2816 cxr_loop *lp0 = &mesh->loops[poly->loop_start],
2817 *lp1 = &mesh->loops[poly->loop_start+j+1],
2818 *lp2 = &mesh->loops[poly->loop_start+j+2];
2819
2820 v3f va, vb, orth;
2821 v3_sub( verts[lp1->index], verts[lp0->index], va );
2822 v3_sub( verts[lp2->index], verts[lp0->index], vb );
2823 v3_cross( va, vb, orth );
2824
2825 face_area += v3_length( orth ) / 2.0;
2826
2827 v2f uva, uvb;
2828 v2_sub( lp1->uv, lp0->uv, uva );
2829 v2_sub( lp2->uv, lp0->uv, uvb );
2830
2831 uv_area += fabs(v2_cross( uva, uvb )) / 2.0;
2832 }
2833 }
2834
2835 v3_add( faceboundmax, faceboundmin, face_center );
2836 v3_muls( face_center, 0.5, face_center );
2837 v2_add( uvboundmin, uvboundmax, uv_center );
2838 v2_muls( uv_center, 0.5, uv_center );
2839
2840 sf = sqrt( face_area / uv_area );
2841 int corner_count = 0;
2842
2843 /*
2844 * Vertex classification
2845 * boundary vertices: they exist on a freestyle edge
2846 * corners: only connected to other boundaries
2847 */
2848 for( int i=0; i<mesh->p_abverts->count; i++ )
2849 {
2850 struct vertinfo *info = &vertinfo[i];
2851 if( !info->boundary ) continue;
2852
2853 int count = 0,
2854 non_manifold = 1;
2855
2856 for( int j=0; j<info->con_count; j++ )
2857 {
2858 int con = graph[info->con_start+j];
2859
2860 if( vertinfo[con].boundary )
2861 count ++;
2862 else
2863 non_manifold = 0;
2864 }
2865
2866 if( count > 2 || non_manifold )
2867 {
2868 info->corner = 1;
2869 corner_count ++;
2870 }
2871 }
2872
2873 /*
2874 * TODO(harry): This currently only supports power 2 displacements
2875 * its quite straightforward to upgrade it.
2876 *
2877 * TODO(harry): Error checking is needed here for bad input data
2878 */
2879
2880 int dispedge[17];
2881 v2f corner_uvs[4];
2882 int dispedge_count;
2883 int disp_count = 0;
2884
2885 for( int i=0; i<mesh->abpolys.count; i++ )
2886 {
2887 cxr_polygon *basepoly = &mesh->polys[i];
2888
2889 for( int h=0; h<basepoly->loop_total; h ++ )
2890 {
2891 int i0 = h,
2892 i1 = cxr_range(h+1,basepoly->loop_total);
2893
2894 cxr_loop *l0 = &mesh->loops[ basepoly->loop_start+i0 ],
2895 *l1 = &mesh->loops[ basepoly->loop_start+i1 ];
2896 struct vertinfo *info = &vertinfo[ l0->index ];
2897
2898 if( !info->corner )
2899 continue;
2900
2901 int corner_count = 1;
2902
2903 cxr_material *matptr =
2904 basepoly->material_id < 0 || !world->materials?
2905 &cxr_nodraw:
2906 &world->materials[ basepoly->material_id ];
2907
2908 dispedge_count = 2;
2909 dispedge[0] = l0->index;
2910 dispedge[1] = l1->index;
2911 v2_copy( l0->uv, corner_uvs[0] );
2912
2913 /* Consume (use) face from orignal mesh */
2914 basepoly->loop_total = -1;
2915
2916 while( dispedge_count < 17 )
2917 {
2918 struct vertinfo *edge_head =
2919 &vertinfo[dispedge[dispedge_count-1]];
2920
2921 int newvert = 0;
2922
2923 if( edge_head->corner )
2924 {
2925 /* Find polygon that has edge C-1 -> C */
2926 for( int j=0; j<mesh->abpolys.count && !newvert; j++ )
2927 {
2928 cxr_polygon *poly = &mesh->polys[j];
2929
2930 for( int k=0; k<poly->loop_total; k ++ )
2931 {
2932 int i0 = k,
2933 i1 = cxr_range(k+1,poly->loop_total);
2934
2935 cxr_loop *l0 = &mesh->loops[ poly->loop_start+i0 ],
2936 *l1 = &mesh->loops[ poly->loop_start+i1 ];
2937
2938 if( l0->index == dispedge[dispedge_count-2] &&
2939 l1->index == dispedge[dispedge_count-1] )
2940 {
2941 /* Take the next edge */
2942 v2_copy( l1->uv, corner_uvs[corner_count ++] );
2943
2944 int i2 = cxr_range(i1+1,poly->loop_total);
2945 cxr_loop *l2 = &mesh->loops[ poly->loop_start+i2 ];
2946
2947 dispedge[dispedge_count ++] = l2->index;
2948 newvert = 1;
2949 poly->loop_total = -1;
2950 break;
2951 }
2952 }
2953 }
2954 }
2955 else
2956 {
2957 for( int j=0; j<edge_head->con_count; j++ )
2958 {
2959 int con = graph[edge_head->con_start+j];
2960
2961 if( con == -1 )
2962 continue;
2963
2964 if( dispedge_count > 1 )
2965 if( con == dispedge[dispedge_count-2] )
2966 continue;
2967
2968 struct vertinfo *coninfo = &vertinfo[con];
2969
2970 if( !coninfo->boundary )
2971 continue;
2972
2973 dispedge[ dispedge_count ++ ] = con;
2974 newvert = 1;
2975
2976 break;
2977 }
2978 }
2979
2980 if( !newvert )
2981 {
2982 free( graph );
2983 free( vertinfo );
2984 return 0;
2985 }
2986 }
2987
2988 /* All edges collected */
2989
2990 v2f va, vb;
2991 v2_sub( corner_uvs[1], corner_uvs[0], va );
2992 v2_sub( corner_uvs[2], corner_uvs[0], vb );
2993
2994 /* Connect up the grid
2995 *
2996 * 0 1 2 3 4
2997 * 15 a b c d
2998 * 14 e f g h
2999 * 13 i j k l
3000 * 12 m n o p
3001 *
3002 * Example: a := common unused vertex that is connected to
3003 * by 1 and 15. Or y-1, and x-1 on the grid.
3004 * g := c and f common vert ^
3005 */
3006
3007 int grid[25];
3008
3009 for( int j=0; j<5; j++ ) grid[j] = dispedge[j];
3010 for( int j=1; j<5; j++ ) grid[j*5+4] = dispedge[j+4];
3011 for( int j=0; j<4; j++ ) grid[4*5+3-j] = dispedge[j+9];
3012 for( int j=1; j<4; j++ ) grid[j*5] = dispedge[16-j];
3013
3014 /* Fill in grid */
3015 for( int j=1; j<4; j++ )
3016 {
3017 for( int k=1; k<4; k++ )
3018 {
3019 int s0 = grid[(j-1)*5+k],
3020 s1 = grid[j*5+k-1];
3021
3022 struct vertinfo *va = &vertinfo[s0],
3023 *vb = &vertinfo[s1];
3024
3025 /* Find common non-used vertex */
3026 for( int l=0; l<va->con_count; l ++ )
3027 {
3028 for( int m=0; m<vb->con_count; m ++ )
3029 {
3030 int cona = graph[va->con_start+l],
3031 conb = graph[vb->con_start+m];
3032
3033 if( cona == conb )
3034 {
3035 if( vertinfo[cona].used || vertinfo[cona].boundary )
3036 continue;
3037
3038 grid[ j*5+k ] = cona;
3039 vertinfo[cona].used = 1;
3040
3041 goto next_cell;
3042 }
3043 }
3044 }
3045
3046 free( graph );
3047 free( vertinfo );
3048 return 0;
3049
3050 next_cell:;
3051 }
3052 }
3053
3054 /*
3055 * Create V reference based on first displacement.
3056 * TODO(harry): This is not the moststable selection method!
3057 * faces can come in any order, so the first disp will of
3058 * course always vary. Additionaly the triangle can be oriented
3059 * differently.
3060 *
3061 * Improvement can be made by selecting a first disp/triangle
3062 * based on deterministic factors.
3063 */
3064 if( disp_count == 0 )
3065 {
3066 cxr_texinfo tx;
3067 v3f tri_ref[3];
3068 v3_copy( verts[dispedge[0]], tri_ref[0] );
3069 v3_copy( verts[dispedge[4]], tri_ref[1] );
3070 v3_copy( verts[dispedge[8]], tri_ref[2] );
3071 cxr_calculate_axis( &tx, tri_ref, corner_uvs, (v2f){512,512} );
3072
3073 v3_muls( tx.vaxis, -1.0, refv );
3074 int v_cardinal = cxr_cardinal( refv, -1 );
3075
3076 v3_cross( tx.vaxis, tx.uaxis, refn );
3077 v3_muls( refn, -tx.winding, refn );
3078
3079 /* Computing new reference vectors */
3080 int n1_cardinal = cxr_cardinal( refn, v_cardinal );
3081
3082 int u_cardinal = 0;
3083
3084 for( int j=0; j<2; j++ )
3085 if( u_cardinal == n1_cardinal || u_cardinal == v_cardinal )
3086 u_cardinal ++;
3087
3088 v3_zero(refu);
3089 refu[u_cardinal] = tx.uaxis[u_cardinal] > 0.0? 1.0: -1.0;
3090
3091 v3f p0, pv, pu, pn;
3092
3093 v3_copy( face_center, p0 );
3094 v3_muladds( face_center, refn, 1.5, pn );
3095 v3_muladds( face_center, refv, 1.5, pv );
3096 v3_muladds( face_center, refu, 1.5, pu );
3097
3098 v3_muladds( face_center, refn, 2.0, face_center );
3099 }
3100
3101 /* Create world coordinates */
3102 v3f world_corners[8];
3103 v2f world_uv[4];
3104
3105 for( int j=0; j<4; j++ )
3106 {
3107 v2f local_uv;
3108 v2_sub( corner_uvs[j], uv_center, local_uv );
3109 v2_copy( corner_uvs[j], world_uv[j] );
3110 v2_muls( local_uv, sf, local_uv );
3111
3112 v3_muls( refu, local_uv[0], world_corners[j] );
3113 v3_muladds( world_corners[j],refv,local_uv[1],world_corners[j] );
3114 v3_add( face_center, world_corners[j], world_corners[j] );
3115 }
3116
3117 double *colour = colours_random[cxr_range(disp_count,8)];
3118
3119 for( int j=0; j<4; j++ )
3120 v3_muladds( world_corners[j], refn, -1.0, world_corners[j+4] );
3121
3122 /* Apply world transform */
3123 for( int j=0; j<8; j++ )
3124 {
3125 double *p0 = world_corners[j];
3126 v3_muls( p0, ctx->scale, p0 );
3127 v3_add( p0, ctx->offset, p0 );
3128 }
3129
3130 cxr_texinfo texinfo_shared;
3131 cxr_calculate_axis( &texinfo_shared, world_corners, world_uv,
3132 (v2f){ matptr->res[0], matptr->res[1] } );
3133
3134 /* Write brush */
3135 cxr_vdf_node( output, "solid" );
3136 cxr_vdf_ki32( output, "id", ++ ctx->brush_count );
3137
3138 int sides[6][3] =
3139 {{ 0, 1, 2 },
3140 { 4, 6, 5 },
3141 { 4, 1, 0 },
3142 { 7, 0, 3 },
3143 { 6, 2, 1 },
3144 { 6, 3, 2 }};
3145
3146 v3f normals[25];
3147 double distances[25];
3148
3149 v3f lside0, lside1, lref, vdelta, vworld;
3150 double tx, ty;
3151
3152 for( int j=0; j<5; j++ )
3153 {
3154 ty = (double)j/(double)(5-1);
3155
3156 v3_lerp( world_corners[0], world_corners[3], ty, lside0 );
3157 v3_lerp( world_corners[1], world_corners[2], ty, lside1 );
3158
3159 for( int k=0; k<5; k++ )
3160 {
3161 int index = j*5+k;
3162
3163 tx = (double)k/(double)(5-1);
3164 v3_lerp( lside0, lside1, tx, lref );
3165 v3_muls( verts[grid[index]], ctx->scale, vworld );
3166 v3_add( ctx->offset, vworld, vworld );
3167
3168 v3_sub( vworld, lref, vdelta );
3169 v3_copy( vdelta, normals[index] );
3170 v3_normalize( normals[index] );
3171 distances[index] = v3_dot( vdelta, normals[index] );
3172 }
3173 }
3174
3175 for( int j=0; j<6; j++ )
3176 {
3177 int *side = sides[j];
3178
3179 cxr_vdf_node( output, "side" );
3180 cxr_vdf_ki32( output, "id", ++ ctx->face_count );
3181 cxr_vdf_plane( output, "plane", world_corners[side[2]],
3182 world_corners[side[1]],
3183 world_corners[side[0]] );
3184
3185 cxr_vdf_kv( output, "material", matptr->name );
3186 cxr_vdf_kaxis( output, "uaxis",
3187 texinfo_shared.uaxis,
3188 texinfo_shared.offset[0],
3189 texinfo_shared.scale[0] );
3190 cxr_vdf_kaxis( output, "vaxis",
3191 texinfo_shared.vaxis,
3192 texinfo_shared.offset[1],
3193 texinfo_shared.scale[1] );
3194
3195 cxr_vdf_kdouble( output, "rotation", 0.0 );
3196 cxr_vdf_ki32( output, "lightmapscale", ctx->lightmap_scale);
3197 cxr_vdf_ki32( output, "smoothing_groups", 0 );
3198
3199 if( j == 0 )
3200 {
3201 cxr_vdf_node( output, "dispinfo" );
3202 cxr_vdf_ki32( output, "power", 2 );
3203 cxr_vdf_kv3f( output, "startposition", world_corners[0] );
3204 cxr_vdf_ki32( output, "flags", 0 );
3205 cxr_vdf_kdouble( output, "elevation", 0.0 );
3206 cxr_vdf_ki32( output, "subdiv", 0 );
3207
3208 cxr_vdf_node( output, "normals" );
3209 for( int k=0; k<5; k++ )
3210 cxr_vdf_karrv3f( output, "row", k, &normals[k*5], 5 );
3211 cxr_vdf_edon( output );
3212
3213 cxr_vdf_node( output, "distances" );
3214 for( int k=0; k<5; k++ )
3215 cxr_vdf_karrdouble( output, "row", k, &distances[k*5], 5 );
3216 cxr_vdf_edon( output );
3217
3218 /*
3219 * TODO: This might be needed for the compilers. Opens fine in
3220 * hammer
3221 */
3222
3223 /*
3224 cxr_vdf_node( output, "offsets" );
3225 for( int k=0; k<5; k++ )
3226 cxr_vdf_printf( output,
3227 "\"row%d\" \"0 0 0 0 0 0 0 0 0 0 0 0 0 0 0\"\n", k );
3228 cxr_vdf_edon( output );
3229
3230 cxr_vdf_node( output, "offset_normals" );
3231 for( int k=0; k<5; k++ )
3232 cxr_vdf_printf( output,
3233 "\"row%d\" \"0 0 1 0 0 1 0 0 1 0 0 1 0 0 1\"\n", k );
3234 cxr_vdf_edon( output );
3235
3236 cxr_vdf_node( output, "alphas" );
3237 for( int k=0; k<5; k++ )
3238 cxr_vdf_printf( output, "\"row%d\" \"0 0 0 0 0\"\n", k );
3239 cxr_vdf_edon( output );
3240
3241 cxr_vdf_node( output, "triangle_tags" );
3242 for( int k=0; k<5-1; k++ )
3243 cxr_vdf_printf( output,
3244 "\"row%d\" \"9 9 9 9 9 9 9 9\"\n", k );
3245 cxr_vdf_edon( output );
3246
3247 cxr_vdf_node( output, "allowed_verts" );
3248 cxr_vdf_printf( output,
3249 "\"10\" \"-1 -1 -1 -1 -1 -1 -1 -1 -1 -1\"\n" );
3250 cxr_vdf_edon( output );
3251 */
3252
3253 cxr_vdf_edon( output );
3254 }
3255
3256 cxr_vdf_edon( output );
3257 }
3258
3259 cxr_vdf_node( output, "editor");
3260 cxr_vdf_colour255( output, "color",
3261 colours_random[cxr_range(ctx->brush_count,8)]);
3262
3263 cxr_vdf_ki32( output, "visgroupid", ctx->visgroupid );
3264 cxr_vdf_ki32( output, "visgroupshown",1);
3265 cxr_vdf_ki32( output, "visgroupautoshown",1);
3266 cxr_vdf_edon( output );
3267
3268 cxr_vdf_edon( output );
3269 disp_count ++;
3270 }
3271 }
3272
3273 free( graph );
3274 free( vertinfo );
3275
3276 return 1;
3277 }
3278
3279 /*
3280 * Write header information for a vmf to vdf
3281 */
3282 CXR_API void cxr_begin_vmf( cxr_vmf_context *ctx, cxr_vdf *output )
3283 {
3284 cxr_vdf_node( output, "versioninfo" );
3285 cxr_vdf_ki32( output, "editorversion", 400 );
3286 cxr_vdf_ki32( output, "editorbuild", 8456 );
3287 cxr_vdf_ki32( output, "mapversion", ctx->mapversion );
3288 cxr_vdf_ki32( output, "formatversion", 100 );
3289 cxr_vdf_ki32( output, "prefab", 0 );
3290 cxr_vdf_edon( output );
3291
3292 cxr_vdf_node( output, "visgroups" );
3293
3294 for( int i=0; i<ctx->visgroup_count; i++ )
3295 {
3296 cxr_vdf_node( output, "visgroup" );
3297 cxr_vdf_kv( output, "name", ctx->visgroups[i].name );
3298 cxr_vdf_ki32( output, "visgroupid", i+1 );
3299 cxr_vdf_edon( output );
3300 }
3301
3302 cxr_vdf_edon( output );
3303
3304 cxr_vdf_node( output, "viewsettings" );
3305 cxr_vdf_ki32( output, "bSnapToGrid", 1 );
3306 cxr_vdf_ki32( output, "bShowGrid", 1 );
3307 cxr_vdf_ki32( output, "bShowLogicalGrid", 0 );
3308 cxr_vdf_ki32( output, "nGridSpacing", 64 );
3309 cxr_vdf_ki32( output, "bShow3DGrid", 0 );
3310 cxr_vdf_edon( output );
3311
3312 cxr_vdf_node( output, "world" );
3313 cxr_vdf_ki32( output, "id", 1 );
3314 cxr_vdf_ki32( output, "mapversion", 1 ); /* ?? */
3315 cxr_vdf_kv( output, "classname", "worldspawn" );
3316 cxr_vdf_kv( output, "skyname", ctx->skyname );
3317 cxr_vdf_ki32( output, "maxpropscreenwidth", -1 );
3318 cxr_vdf_kv( output, "detailvbsp", ctx->detailvbsp );
3319 cxr_vdf_kv( output, "detailmaterial", ctx->detailmaterial );
3320 }
3321
3322 /* Fairly useless but might need in the future */
3323 CXR_API void cxr_vmf_begin_entities( cxr_vmf_context *ctx, cxr_vdf *vdf )
3324 {
3325 cxr_vdf_edon( vdf );
3326 }
3327
3328 CXR_API void cxr_end_vmf( cxr_vmf_context *ctx, cxr_vdf *vdf )
3329 {
3330 }
3331
3332 /*
3333 * Write solids (and displacements) to VMF file
3334 */
3335 CXR_API void cxr_push_world_vmf( cxr_world *world, cxr_vmf_context *ctx,
3336 cxr_vdf *output
3337 ){
3338 v3f *verts = cxr_ab_ptr( &world->abverts, 0 );
3339
3340 /* Write all solids as VMF brushes */
3341 for( int i=0; i<world->absolids.count; i++ )
3342 {
3343 cxr_solid *solid = cxr_ab_ptr(&world->absolids,i);
3344
3345 if( solid->displacement )
3346 {
3347 if( !cxr_write_disp( solid->pmesh, world, ctx, output ) )
3348 {
3349 cxr_log( "Warning: Invalid displacement\n" );
3350 }
3351 continue;
3352 }
3353
3354 cxr_vdf_node( output, "solid" );
3355 cxr_vdf_ki32( output, "id", ++ ctx->brush_count );
3356
3357 for( int j=0; j<solid->pmesh->abpolys.count; j++ )
3358 {
3359 cxr_polygon *poly = &solid->pmesh->polys[j];
3360 cxr_loop *ploops = &solid->pmesh->loops[poly->loop_start];
3361
3362 cxr_material *matptr =
3363 poly->material_id < 0 || !world->materials?
3364 &cxr_nodraw:
3365 &world->materials[ poly->material_id ];
3366
3367 cxr_vdf_node( output, "side" );
3368 cxr_vdf_ki32( output, "id", ++ ctx->face_count );
3369
3370 v3f tri[3]; v2f uvs[3];
3371
3372 int i0 = ploops[0].index,
3373 i1 = ploops[1].index,
3374 i2 = ploops[2].index;
3375
3376 v3_muls( verts[i0], ctx->scale, tri[0] );
3377 v3_muls( verts[i1], ctx->scale, tri[1] );
3378 v3_muls( verts[i2], ctx->scale, tri[2] );
3379
3380 v3_add( ctx->offset, tri[0], tri[0] );
3381 v3_add( ctx->offset, tri[1], tri[1] );
3382 v3_add( ctx->offset, tri[2], tri[2] );
3383
3384 v2_copy( ploops[0].uv, uvs[0] );
3385 v2_copy( ploops[1].uv, uvs[1] );
3386 v2_copy( ploops[2].uv, uvs[2] );
3387
3388 cxr_vdf_plane( output, "plane", tri[2], tri[1], tri[0] );
3389 cxr_vdf_kv( output, "material", matptr->name );
3390
3391 cxr_texinfo tx;
3392 cxr_calculate_axis( &tx, tri, uvs,
3393 (double[2]){ matptr->res[0], matptr->res[1] });
3394
3395 cxr_vdf_kaxis( output, "uaxis", tx.uaxis, tx.offset[0], tx.scale[0]);
3396 cxr_vdf_kaxis( output, "vaxis", tx.vaxis, tx.offset[1], tx.scale[1]);
3397
3398 cxr_vdf_kdouble( output, "rotation", 0.0 );
3399 cxr_vdf_ki32( output, "lightmapscale", ctx->lightmap_scale );
3400 cxr_vdf_ki32( output, "smoothing_groups", 0);
3401
3402 cxr_vdf_edon( output );
3403 }
3404
3405 cxr_vdf_node( output, "editor" );
3406 cxr_vdf_colour255( output, "color",
3407 colours_random[cxr_range(ctx->brush_count,8)]);
3408
3409 cxr_vdf_ki32( output, "visgroupid", ctx->visgroupid );
3410 cxr_vdf_ki32( output, "visgroupshown", 1 );
3411 cxr_vdf_ki32( output, "visgroupautoshown", 1 );
3412 cxr_vdf_edon( output );
3413
3414 cxr_vdf_edon( output );
3415 }
3416 }
3417
3418 /*
3419 * Valve Source SDK 2015 CS:GO
3420 */
3421 #define HEADER_LUMPS 64
3422 #define LUMP_WORLDLIGHTS 54
3423
3424 #pragma pack(push,1)
3425
3426 struct header
3427 {
3428 int ident;
3429 int version;
3430
3431 struct lump
3432 {
3433 int fileofs, filelen;
3434 int version;
3435
3436 char fourCC[4];
3437 }
3438 lumps[ HEADER_LUMPS ];
3439
3440 int mapRevision;
3441 };
3442
3443 struct worldlight
3444 {
3445 float origin[3];
3446 float intensity[3];
3447 float normal[3];
3448 float shadow_cast_offset[3];
3449 int cluster;
3450 int type;
3451 int style;
3452 float stopdot;
3453 float stopdot2;
3454 float exponent;
3455 float radius;
3456 float constant_attn;
3457 float linear_attn;
3458 float quadratic_attn;
3459 int flags;
3460 int texinfo;
3461 int owner;
3462 };
3463 #pragma pack(pop)
3464
3465 /*
3466 * Utility for patching BSP tools to remove -1 distance lights (we set them
3467 * like that, because we want these lights to go away)
3468 *
3469 * Yes, there is no way to do this in hammer
3470 * Yes, the distance KV is unused but still gets compiled to this lump
3471 * No, Entities only compile will not do this for you
3472 */
3473 CXR_API int cxr_lightpatch_bsp( const char *path )
3474 {
3475 printf( "Lightpatch: %s\n", path );
3476
3477 FILE *fp = fopen( path, "r+b" );
3478
3479 if( !fp )
3480 {
3481 #ifdef CXR_DEBUG
3482 cxr_log( "Could not open BSP file for editing (r+b)\n" );
3483 #endif
3484 return 0;
3485 }
3486
3487 /* Read bsp */
3488 struct header header;
3489 fread( &header, sizeof(struct header), 1, fp );
3490 struct lump *lump = &header.lumps[ LUMP_WORLDLIGHTS ];
3491
3492 /* Read worldlight array */
3493 struct worldlight *lights = malloc( lump->filelen );
3494 fseek( fp, lump->fileofs, SEEK_SET );
3495 fread( lights, lump->filelen, 1, fp );
3496
3497 /* Remove all marked lights */
3498 int light_count = lump->filelen / sizeof(struct worldlight);
3499 int new_count = 0;
3500
3501 for( int i = 0; i < light_count; i ++ )
3502 if( lights[i].radius >= 0.0f )
3503 lights[new_count++] = lights[i];
3504
3505 lump->filelen = new_count*sizeof(struct worldlight);
3506
3507 /* Write changes back to file */
3508 fseek( fp, lump->fileofs, SEEK_SET );
3509 fwrite( lights, lump->filelen, 1, fp );
3510 fseek( fp, 0, SEEK_SET );
3511 fwrite( &header, sizeof(struct header), 1, fp );
3512
3513 #ifdef CXR_DEBUG
3514 cxr_log( "removed %d marked lights\n", light_count-new_count );
3515 #endif
3516
3517 fclose( fp );
3518 free( lights );
3519
3520 return 1;
3521 }
3522 #endif /* CXR_VALVE_MAP_FILE */
3523 #endif /* CXR_IMPLEMENTATION */
Simple convex decomp library and source map exporter from blender.