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