projects / convexer.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
history | raw | HEAD
yet more stability improvements
[convexer.git] / src / convexer.c
1 /*
2 CONVEXER v0.8
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 - Light patch BSP files; remove unwanted realtime effects
15 - Fastest VTF compressor (thanks to Richgel999 and stb)
16
17 To come:
18 - high quality level overviews automatically for CS:GO (csRadar)
19
20 Program structure:
21
22 File/folder Lang Purpose
23 src/
24 __init__.py Python Blender plugin interface
25 convexer.c C Heavy lifting; brush decomp, mesh processing
26 cxr_math.h C Vector maths and other handy things
27 cxr_mem.h C Automatic resizing buffers
28 nbvtf/
29 nbvtf.h C VTF processing interface
30 librgcx.h C++ Rich Geldreich's DXT1/DXT5 compressors
31 stb/ C Sean Barrets image I/O
32 */
33
34 const char *cxr_build_time = __DATE__ " @" __TIME__;
35
36 #include <stdio.h>
37 #include <math.h>
38 #include <stdint.h>
39 #include <stdarg.h>
40 #include <stdlib.h>
41 #include <string.h>
42
43 typedef uint8_t u8;
44 typedef uint16_t u16;
45 typedef uint32_t u32;
46 typedef uint64_t u64;
47 typedef int8_t i8;
48 typedef int16_t i16;
49 typedef int32_t i32;
50 typedef int64_t i64;
51
52 typedef unsigned int uint;
53
54 typedef double v2f[2];
55 typedef double v3f[3];
56 typedef double v4f[4];
57 typedef v3f m3x3f[3];
58 typedef v3f m4x3f[4];
59 typedef v3f boxf[2];
60
61 #define CXR_EPSILON 0.001
62 #define CXR_PLANE_SIMILARITY_MAX 0.998
63 #define CXR_BIG_NUMBER 1e300
64 #define CXR_INTERIOR_ANGLE_MAX 0.998
65 #define CXR_API
66 #define CXR_DIRTY_OPTIMISATION 1
67 #define CXR_DEBUG_WRITE_MESH 1
68 #define CXR_DEBUG_ALLOCATORS 1
69 #define CXR_MANIFOLD_DEBUG 0
70
71 #define CXR_ERROR_DEGEN_IMPLICIT 0x1
72 #define CXR_ERROR_BAD_MANIFOLD 0x2
73 #define CXR_ERROR_NO_SOLIDS 0x4
74
75 #include "cxr_math.h"
76 #include "cxr_mem.h"
77
78 // Utility
79 // ============================================
80
81 static v4f colours_random[] =
82 {
83 { 0.863, 0.078, 0.235, 0.4 },
84 { 0.000, 0.980, 0.604, 0.4 },
85 { 0.118, 0.565, 1.000, 0.4 },
86 { 0.855, 0.439, 0.839, 0.4 },
87 { 0.824, 0.412, 0.118, 0.4 },
88 { 0.125, 0.698, 0.667, 0.4 },
89 { 0.541, 0.169, 0.886, 0.4 },
90 { 1.000, 0.843, 0.000, 0.4 }
91 };
92
93 static int cxr_range(int x, int bound)
94 {
95 if( x < 0 )
96 x += bound * (x/bound + 1);
97
98 return x % bound;
99 }
100
101 struct cxr_input_mesh
102 {
103 v3f *vertices;
104
105 struct cxr_edge
106 {
107 i32 i0, i1;
108 i32 freestyle;
109 }
110 *edges;
111
112 struct cxr_input_loop
113 {
114 i32 index,
115 edge_index;
116 v2f uv;
117 }
118 *loops;
119
120 struct cxr_polygon
121 {
122 i32 loop_start, loop_total;
123 v3f normal;
124 v3f center;
125 i32 material_id; // -1: interior material
126 }
127 *polys;
128
129 struct cxr_material
130 {
131 i32 res[2];
132 const char *vmt_path;
133 }
134 *materials;
135
136 i32 poly_count,
137 vertex_count,
138 edge_count,
139 loop_count,
140 material_count;
141 };
142
143 struct cxr_loop
144 {
145 i32 poly_left,
146 poly_right,
147 edge_index,
148 index;
149 v2f uv;
150 };
151
152 struct cxr_solid
153 {
154 i32 *polygons;
155 };
156
157 struct cxr_mesh
158 {
159 struct cxr_auto_buffer
160 edges,
161 loops,
162 polys;
163 };
164
165 struct cxr_texinfo
166 {
167 v3f uaxis, vaxis;
168 v2f offset, scale;
169 double winding;
170 };
171
172 // simple VDF writing interface
173 struct cxr_vdf
174 {
175 FILE *fp;
176 i32 level;
177 };
178
179 static struct cxr_settings
180 {
181 i32 debug,
182 lightmap_scale;
183
184 double light_scale;
185 }
186 cxr_settings = {
187 .debug = 0,
188 .lightmap_scale = 12,
189
190 .light_scale = 1.0/5.0
191 };
192
193 static struct cxr_context
194 {
195 i32 brush_count,
196 entity_count,
197 face_count;
198
199 double scale_factor;
200 double offset_z;
201 }
202 cxr_context = {
203 .brush_count = 0,
204 .entity_count = 0,
205 .face_count = 0,
206 .scale_factor = 32.0,
207 .offset_z = 0.0
208 };
209
210 static struct cxr_material cxr_nodraw = {
211 .res = { 512, 512 },
212 .vmt_path = "tools/toolsnodraw"
213 };
214
215 // Debugging callbacks
216 // =============================================================================
217
218 static v4f colour_error = { 1.0f, 0.0f, 0.0f, 1.0f };
219 static v4f colour_face_graph = { 1.0f, 1.0f, 1.0f, 0.03f };
220 static v4f colour_success = { 0.0f, 1.0f, 0.0f, 1.0f };
221
222 static void (*cxr_log_func)(const char *str);
223 static void (*cxr_line_func)( v3f p0, v3f p1, v4f colour );
224
225 static void cxr_log( const char *fmt, ... )
226 {
227 char buf[512];
228
229 va_list args;
230 va_start( args, fmt );
231 vsnprintf( buf, sizeof(buf)-1, fmt, args );
232 va_end(args);
233
234 if( cxr_log_func )
235 cxr_log_func( buf );
236
237 fputs(buf,stdout);
238 }
239
240 static void cxr_debug_line( v3f p0, v3f p1, v4f colour )
241 {
242 if( cxr_line_func )
243 cxr_line_func( p0, p1, colour );
244 }
245
246 static void cxr_debug_box( v3f p0, double sz, v4f colour )
247 {
248 v3f a,b,c,d,
249 a1,b1,c1,d1;
250 v3_add(p0, (v3f){-sz,-sz,-sz}, a);
251 v3_add(p0, (v3f){-sz, sz,-sz}, b);
252 v3_add(p0, (v3f){ sz, sz,-sz}, c);
253 v3_add(p0, (v3f){ sz,-sz,-sz}, d);
254 v3_add(p0, (v3f){-sz,-sz,sz}, a1);
255 v3_add(p0, (v3f){-sz, sz,sz}, b1);
256 v3_add(p0, (v3f){ sz, sz,sz}, c1);
257 v3_add(p0, (v3f){ sz,-sz,sz}, d1);
258
259 cxr_debug_line( a,b, colour );
260 cxr_debug_line( b,c, colour );
261 cxr_debug_line( c,d, colour );
262 cxr_debug_line( d,a, colour );
263 cxr_debug_line( a1,b1, colour );
264 cxr_debug_line( b1,c1, colour );
265 cxr_debug_line( c1,d1, colour );
266 cxr_debug_line( d1,a1, colour );
267 cxr_debug_line( a,a1, colour );
268 cxr_debug_line( b,b1, colour );
269 cxr_debug_line( c,c1, colour );
270 cxr_debug_line( d,d1, colour );
271 }
272
273 static void cxr_debug_arrow( v3f p0, v3f p1, v3f normal, double sz, v4f colour )
274 {
275 v3f dir, tan, p2, p3;
276 v3_sub(p1,p0,dir);
277 v3_normalize(dir);
278
279 v3_cross(dir,normal,tan);
280 v3_muladds( p1,dir, -sz, p2 );
281 v3_muladds( p2,tan,sz,p3 );
282 cxr_debug_line( p1, p3, colour );
283 v3_muladds( p2,tan,-sz,p3 );
284 cxr_debug_line( p1, p3, colour );
285 cxr_debug_line( p0, p1, colour );
286 }
287
288 // Public API
289 // =========================================================================
290
291 CXR_API void cxr_context_reset(void)
292 {
293 cxr_context.brush_count = 0;
294 cxr_context.entity_count = 0;
295 cxr_context.face_count = 0;
296 cxr_context.offset_z = 0.0;
297 cxr_context.scale_factor = 32.0;
298 }
299
300 CXR_API void cxr_set_offset(double offset)
301 {
302 cxr_context.offset_z = offset;
303 }
304
305 CXR_API void cxr_set_scale_factor(double scale)
306 {
307 cxr_context.scale_factor = scale;
308 }
309
310 CXR_API struct cxr_vdf *cxr_vdf_open(const char *path)
311 {
312 struct cxr_vdf *vdf = malloc(sizeof(struct cxr_vdf));
313
314 vdf->level = 0;
315 vdf->fp = fopen( path, "w" );
316
317 if( !vdf->fp )
318 {
319 free( vdf );
320 return NULL;
321 }
322
323 return vdf;
324 }
325
326 CXR_API void cxr_vdf_close(struct cxr_vdf *vdf)
327 {
328 fclose( vdf->fp );
329 }
330
331 CXR_API void cxr_vdf_put(struct cxr_vdf *vdf, const char *str)
332 {
333 for( int i=0; i<vdf->level; i++ )
334 fputs( " ", vdf->fp );
335
336 fputs( str, vdf->fp );
337 }
338
339 static void cxr_vdf_printf( struct cxr_vdf *vdf, const char *fmt, ... )
340 {
341 cxr_vdf_put(vdf,"");
342
343 va_list args;
344 va_start( args, fmt );
345 vfprintf( vdf->fp, fmt, args );
346 va_end(args);
347 }
348
349 CXR_API void cxr_vdf_node(struct cxr_vdf *vdf, const char *str)
350 {
351 cxr_vdf_put( vdf, str );
352 putc( (u8)'\n', vdf->fp );
353 cxr_vdf_put( vdf, "{\n" );
354
355 vdf->level ++;
356 }
357
358 CXR_API void cxr_vdf_edon(struct cxr_vdf *vdf)
359 {
360 vdf->level --;
361 cxr_vdf_put( vdf, "}\n" );
362 }
363
364 CXR_API void cxr_vdf_kv(struct cxr_vdf *vdf, const char *strk, const char *strv)
365 {
366 cxr_vdf_printf( vdf, "\"%s\" \"%s\"\n", strk, strv );
367 }
368
369 static void cxr_vdf_ki32(struct cxr_vdf *vdf, const char *strk, i32 val)
370 {
371 cxr_vdf_printf( vdf, "\"%s\" \"%d\"\n", strk, val );
372 }
373 static void cxr_vdf_kdouble(struct cxr_vdf *vdf, const char *strk, double val)
374 {
375 cxr_vdf_printf( vdf, "\"%s\" \"%f\"\n", strk, val );
376 }
377 static void cxr_vdf_kaxis(struct cxr_vdf *vdf, const char *strk, v3f normal, double offset, double scale)
378 {
379 cxr_vdf_printf( vdf, "\"%s\" \"[%f %f %f %f] %f\"\n", strk, normal[0],normal[1],normal[2],offset,scale );
380 }
381 static void cxr_vdf_kv3f(struct cxr_vdf *vdf, const char *strk, v3f v)
382 {
383 cxr_vdf_printf( vdf, "\"%s\" \"[%f %f %f]\"\n", strk, v[0], v[1], v[2] );
384 }
385 static void cxr_vdf_karrdouble(struct cxr_vdf *vdf, const char *strk, int id, double *doubles, int count)
386 {
387 cxr_vdf_put(vdf,"");
388 fprintf( vdf->fp, "\"%s%d\" \"", strk, id );
389 for( int i=0; i<count; i++ )
390 {
391 if( i == count-1 ) fprintf( vdf->fp, "%f", doubles[i] );
392 else fprintf( vdf->fp, "%f ", doubles[i] );
393 }
394 fprintf( vdf->fp, "\"\n" );
395 }
396 static void cxr_vdf_karrv3f(struct cxr_vdf *vdf, const char *strk, int id, v3f *vecs, int count)
397 {
398 cxr_vdf_put(vdf,"");
399 fprintf( vdf->fp, "\"%s%d\" \"", strk, id );
400 for( int i=0; i<count; i++ )
401 {
402 if( i == count-1 ) fprintf( vdf->fp, "%f %f %f", vecs[i][0], vecs[i][1], vecs[i][2] );
403 else fprintf( vdf->fp, "%f %f %f ", vecs[i][0], vecs[i][1], vecs[i][2] );
404 }
405 fprintf( vdf->fp, "\"\n" );
406 }
407 static void cxr_vdf_plane(struct cxr_vdf *vdf, const char *strk, v3f a, v3f b, v3f c )
408 {
409 cxr_vdf_printf( vdf, "\"%s\" \"(%f %f %f) (%f %f %f) (%f %f %f)\"\n",
410 strk, a[0], a[1], a[2], b[0], b[1], b[2], c[0], c[1], c[2] );
411 }
412 static void cxr_vdf_colour255(struct cxr_vdf *vdf, const char *strk, v4f colour)
413 {
414 v4f scale;
415 v4_muls( colour, 255.0, scale );
416 cxr_vdf_printf( vdf, "\"%s\" \"%d %d %d %d\"\n",strk,(int)scale[0], (int)scale[1], (int)scale[2], (int)scale[3]);
417 }
418
419 // Public API
420 // =========================================================================
421
422 static void cxr_debug_poly(struct cxr_mesh *mesh, struct cxr_polygon *poly, v3f *verts, v4f colour )
423 {
424 for( int i=0; i<poly->loop_total; i++ )
425 {
426 struct cxr_loop *loop0 = cxr_ab_ptr(&mesh->loops,poly->loop_start+i),
427 *loop1 = cxr_ab_ptr(&mesh->loops,poly->loop_start+cxr_range(i+1,poly->loop_total));
428
429 v3f p0, p1;
430
431 v3_lerp( verts[loop0->index], poly->center, 0.02, p0 );
432 v3_lerp( verts[loop1->index], poly->center, 0.02, p1 );
433
434 cxr_debug_arrow( p0, p1, poly->normal, 0.05, colour );
435 }
436
437 v3f nrm0;
438 v3_muladds( poly->center, poly->normal, 0.3, nrm0 );
439
440 cxr_debug_line( poly->center, nrm0, colour );
441 }
442
443 static void cxr_debug_mesh(struct cxr_mesh *mesh, v3f *verts, v4f colour )
444 {
445 for( int i=0; i<mesh->polys.count; i++ )
446 {
447 struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys,i);
448 cxr_debug_poly( mesh, poly, verts, colour );
449 }
450 }
451
452 static struct cxr_mesh *cxr_alloc_mesh(int edge_count, int loop_count, int poly_count )
453 {
454 struct cxr_mesh *mesh = malloc(sizeof(struct cxr_mesh));
455 cxr_ab_init(&mesh->edges, sizeof(struct cxr_edge), edge_count);
456 cxr_ab_init(&mesh->loops, sizeof(struct cxr_loop), loop_count);
457 cxr_ab_init(&mesh->polys, sizeof(struct cxr_polygon), poly_count);
458 return mesh;
459 }
460
461 static void cxr_free_mesh(struct cxr_mesh *mesh)
462 {
463 cxr_ab_free(&mesh->edges);
464 cxr_ab_free(&mesh->loops);
465 cxr_ab_free(&mesh->polys);
466 free(mesh);
467 }
468
469 // Rebuilds edge data and reallocates
470 //
471 static void cxr_mesh_clean_edges(struct cxr_mesh *mesh)
472 {
473 struct cxr_auto_buffer new_edges;
474 cxr_ab_init( &new_edges, sizeof(struct cxr_edge), mesh->edges.count );
475
476 for( int i=0; i<mesh->polys.count; i++ )
477 {
478 struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys,i);
479 for( int j=0; j<poly->loop_total; j++ )
480 {
481 struct cxr_loop
482 *lp0 = cxr_ab_ptr(&mesh->loops,poly->loop_start+j),
483 *lp1 = cxr_ab_ptr(&mesh->loops,poly->loop_start+cxr_range(j+1,poly->loop_total));
484
485 int i0 = cxr_min(lp0->index, lp1->index),
486 i1 = cxr_max(lp0->index, lp1->index);
487
488 // See if edge exists before adding it
489 for( int k=0; k<new_edges.count; k++ )
490 {
491 struct cxr_edge *edge = cxr_ab_ptr(&new_edges,k);
492
493 if( edge->i0 == i0 && edge->i1 == i1 )
494 {
495 lp0->edge_index = k;
496 goto IL_EDGE_CREATED;
497 }
498 }
499
500 int orig_edge_id = lp0->edge_index;
501 lp0->edge_index = new_edges.count;
502
503 struct cxr_edge edge = { i0, i1 };
504 // --- ! ---
505 // Copy extra information (sharp,freestyle.. etc) here!
506
507 if( orig_edge_id < mesh->edges.count )
508 {
509 struct cxr_edge *orig_edge = cxr_ab_ptr( &mesh->edges, orig_edge_id );
510 edge.freestyle = orig_edge->freestyle;
511 }
512 else
513 {
514 edge.freestyle = 0;
515 }
516
517 // --- ! ---
518 cxr_ab_push( &new_edges, &edge );
519
520 IL_EDGE_CREATED:;
521 }
522 }
523
524 cxr_ab_free( &mesh->edges );
525 mesh->edges = new_edges;
526 }
527
528 // Remove 0-length faces from mesh and correct loops
529 //
530 static void cxr_mesh_clean_faces(struct cxr_mesh *mesh)
531 {
532 struct cxr_auto_buffer loops_new;
533 cxr_ab_init( &loops_new, sizeof(struct cxr_loop), mesh->loops.count );
534
535 int new_length=0;
536 for( int i=0; i<mesh->polys.count; i++ )
537 {
538 struct cxr_polygon *src = cxr_ab_ptr(&mesh->polys,i),
539 *dst = cxr_ab_ptr(&mesh->polys,new_length);
540
541 if( src->loop_total > 0 )
542 {
543 int src_start = src->loop_start,
544 src_total = src->loop_total;
545
546 *dst = *src;
547 dst->loop_start = loops_new.count;
548
549 for( int j=0; j<src_total; j++ )
550 {
551 struct cxr_loop *loop = cxr_ab_ptr(&mesh->loops,src_start+j),
552 *ldst = cxr_ab_ptr(&loops_new,dst->loop_start+j);
553 *ldst = *loop;
554 ldst->poly_left = new_length;
555 }
556
557 loops_new.count += src_total;
558 new_length ++;
559 }
560 }
561
562 cxr_ab_free( &mesh->loops );
563 mesh->loops = loops_new;
564 mesh->polys.count = new_length;
565 }
566
567 static i32 *cxr_mesh_link_loops(struct cxr_mesh *mesh)
568 {
569 i32 *polygon_edge_map = malloc(mesh->edges.count*2 *sizeof(i32));
570
571 for( int i = 0; i < mesh->edges.count*2; i ++ )
572 polygon_edge_map[i] = -1;
573
574 for( int i = 0; i < mesh->polys.count; i ++ )
575 {
576 struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys, i);
577
578 for( int j = 0; j < poly->loop_total; j ++ )
579 {
580 struct cxr_loop *loop = cxr_ab_ptr(&mesh->loops, poly->loop_start+j);
581 loop->poly_left = i;
582
583 for( int k = 0; k < 2; k ++ )
584 {
585 i32 *edge = &polygon_edge_map[loop->edge_index*2+k];
586
587 if( *edge == -1 )
588 {
589 *edge = i;
590 break;
591 }
592 }
593 }
594 }
595 for( int i = 0; i < mesh->polys.count; i ++ )
596 {
597 struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys,i);
598
599 for( int j = 0; j < poly->loop_total; j ++ )
600 {
601 struct cxr_loop *loop = cxr_ab_ptr(&mesh->loops,poly->loop_start+j);
602
603 i32 *face_map = &polygon_edge_map[loop->edge_index*2];
604
605 if( face_map[0] == loop->poly_left ) loop->poly_right = face_map[1];
606 else loop->poly_right = face_map[0];
607 }
608 }
609
610 return polygon_edge_map;
611 }
612
613 // Add polygon to mesh based on loop array
614 static struct cxr_polygon *cxr_create_poly( struct cxr_mesh *mesh, v3f *vertices, struct cxr_loop poly[],
615 int len, int start, int max )
616 {
617 if( len < 3 )
618 {
619 cxr_log( "tried to add new poly with length %d!\n", len );
620
621 if( len >= 2 )
622 {
623 for( int j=0; j<len; j++ )
624 {
625 int i0 = poly[j].index,
626 i1 = poly[cxr_range(j+1,len)].index;
627 cxr_debug_line( vertices[i0], vertices[i1], colour_error );
628 }
629 }
630
631 return NULL;
632 }
633
634 int nface_id = mesh->polys.count;
635 struct cxr_polygon *new_face = cxr_ab_empty(&mesh->polys);
636
637 new_face->loop_start = mesh->loops.count;
638 new_face->loop_total = len;
639 new_face->material_id = -1;
640
641 // Calculate normal and center
642 v3_zero( new_face->center );
643
644 for( int j=0; j<len; j++ )
645 {
646 int i0 = poly[cxr_range(start+j,max)].index;
647 struct cxr_loop *new_loop = cxr_ab_empty(&mesh->loops);
648
649 new_loop->poly_left = nface_id;
650 new_loop->poly_right = -1;
651 new_loop->index = i0;
652 new_loop->edge_index = 0;
653 v2_zero(new_loop->uv);
654
655 v3_add( new_face->center, vertices[new_loop->index], new_face->center );
656 }
657 v3_divs( new_face->center, new_face->loop_total, new_face->center );
658
659 struct cxr_loop *lp0 = cxr_ab_ptr( &mesh->loops, new_face->loop_start ),
660 *lp1 = cxr_ab_ptr( &mesh->loops, new_face->loop_start+1 ),
661 *lp2 = cxr_ab_ptr( &mesh->loops, new_face->loop_start+2 );
662
663 tri_normal( vertices[lp0->index], vertices[lp1->index], vertices[lp2->index], new_face->normal );
664
665 return cxr_ab_ptr(&mesh->polys, nface_id);
666 }
667
668 // Get the 'next' mesh island
669 //
670 // Returns NULL if there is only one island
671 static struct cxr_mesh *cxr_pull_island(struct cxr_mesh *mesh)
672 {
673 free(cxr_mesh_link_loops(mesh));
674
675 int *island_current = malloc(mesh->polys.count*sizeof(int)),
676 island_len = 1,
677 loop_count = 0,
678 last_count;
679
680 island_current[0] = 0;
681
682 IL_ISLAND_REPEAT:
683 last_count = island_len;
684
685 for( int i=0; i<island_len; i++ )
686 {
687 struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys,island_current[i]);
688
689 for( int j=0; j<poly->loop_total; j++ )
690 {
691 struct cxr_loop *loop = cxr_ab_ptr(&mesh->loops, poly->loop_start+j);
692
693 if( loop->poly_right != -1 )
694 {
695 int face_present = 0;
696
697 for( int k=0; k<island_len; k++ )
698 {
699 if( island_current[k] == loop->poly_right )
700 {
701 face_present = 1;
702 break;
703 }
704 }
705
706 if( !face_present )
707 {
708 island_current[ island_len ++ ] = loop->poly_right;
709 }
710 }
711 }
712 }
713
714 if( island_len > last_count )
715 goto IL_ISLAND_REPEAT;
716
717 if( island_len == mesh->polys.count )
718 {
719 free( island_current );
720 return NULL;
721 }
722
723 for( int i=0; i<island_len; i++ )
724 {
725 struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys, island_current[i]);
726 loop_count += poly->loop_total;
727 }
728
729 struct cxr_mesh *newmesh = cxr_alloc_mesh( mesh->edges.count, loop_count, island_len );
730
731 for( int i=0; i<island_len; i++ )
732 {
733 struct cxr_polygon *src = cxr_ab_ptr(&mesh->polys, island_current[i]);
734 struct cxr_polygon *dst = cxr_ab_ptr(&newmesh->polys, i);
735
736 *dst = *src;
737 dst->loop_start = newmesh->loops.count;
738
739 for( int j=0; j<src->loop_total; j++ )
740 {
741 struct cxr_loop *lsrc = cxr_ab_ptr(&mesh->loops, src->loop_start+j),
742 *ldst = cxr_ab_ptr(&newmesh->loops, dst->loop_start+j);
743
744 *ldst = *lsrc;
745 ldst->poly_left = i;
746 ldst->poly_right = -1;
747 }
748
749 newmesh->loops.count += src->loop_total;
750 src->loop_total = -1;
751 }
752
753 newmesh->polys.count = island_len;
754 newmesh->edges.count = mesh->edges.count;
755 memcpy(cxr_ab_ptr(&newmesh->edges,0), cxr_ab_ptr(&mesh->edges,0), mesh->edges.count*sizeof(struct cxr_edge));
756
757 cxr_mesh_clean_faces(mesh);
758 cxr_mesh_clean_edges(mesh);
759 cxr_mesh_clean_edges(newmesh);
760 free( island_current );
761
762 return newmesh;
763 }
764
765 // Does some checks to determine if solid is valid or not
766 static int cxr_valid_solid( struct cxr_mesh *mesh, struct cxr_auto_buffer *abverts, int *solid, int len )
767 {
768 // Invalid 1: Similar normals
769 // Invalid 2: Co-planar point, that is not referenced by the polygon.
770 //
771 for( int i=0; i<len; i++ )
772 {
773 struct cxr_polygon *polyi = cxr_ab_ptr(&mesh->polys,solid[i]);
774
775 v4f plane;
776 normal_to_plane(polyi->normal, polyi->center, plane);
777
778 for( int j=0; j<len; j++ )
779 {
780 if( i==j ) continue;
781
782 struct cxr_polygon *polyj = cxr_ab_ptr(&mesh->polys,solid[j]);
783
784 for( int k=0; k<polyj->loop_total; k++ )
785 {
786 struct cxr_loop *lpj = cxr_ab_ptr(&mesh->loops, polyj->loop_start+k);
787
788 // Make sure this point isnt in our original poly
789 for( int l=0; l<polyi->loop_total; l++ )
790 {
791 struct cxr_loop *lpi = cxr_ab_ptr(&mesh->loops, polyi->loop_start+l);
792 if( lpi->index == lpj->index )
793 goto IL_SKIP_VERTEX;
794 }
795
796 if( fabs(plane_polarity(plane,cxr_ab_ptr(abverts,lpj->index))) < 0.001 )
797 return 0;
798
799 IL_SKIP_VERTEX:;
800 }
801 }
802 }
803
804 return 1;
805 }
806
807 // Return best availible solid from mesh, and patch existing mesh to fill the gap
808 // creted by it.
809 //
810 // Returns NULL if shape is already convex or empty
811 // Destroys edge data!
812 static struct cxr_mesh *cxr_pull_best_solid(
813 struct cxr_mesh *mesh,
814 struct cxr_auto_buffer *vert_buffer,
815 int preserve_hot_edges,
816 u32 *error )
817 {
818 v3f *vertices = cxr_ab_ptr( vert_buffer, 0 );
819
820 i32 *polygon_edge_map = cxr_mesh_link_loops(mesh);
821
822 for( int i=0; i<mesh->edges.count*2; i++ )
823 if( polygon_edge_map[i] == -1 )
824 {
825 cxr_log( "non-manifold edges are in the mesh; implicit internal geometry does not have full support\n" );
826 free(polygon_edge_map);
827 return NULL;
828 }
829
830 int *vertex_tagged = malloc( vert_buffer->count*sizeof(int) );
831 int *edge_tagged = malloc( mesh->edges.count*sizeof(int) );
832
833 for( int i=0; i<mesh->edges.count; i++ )
834 {
835 struct cxr_polygon *polya = cxr_ab_ptr(&mesh->polys, polygon_edge_map[i*2+0]),
836 *polyb = cxr_ab_ptr(&mesh->polys, polygon_edge_map[i*2+1]);
837 v4f planeb;
838 normal_to_plane(polyb->normal, polyb->center, planeb);
839
840 edge_tagged[i] = 0;
841 for( int j=0; j<polya->loop_total; j++ )
842 {
843 struct cxr_loop *loop = cxr_ab_ptr(&mesh->loops, polya->loop_start+j);
844 if( plane_polarity( planeb, vertices[loop->index] ) > 0.001 ||
845 v3_dot(polya->normal,polyb->normal) > CXR_PLANE_SIMILARITY_MAX )
846 {
847 edge_tagged[i] = 1;
848 break;
849 }
850 }
851 }
852
853 // Tag 'reflex' vertices
854 int *connected_planes = malloc(mesh->polys.count*sizeof(int));
855
856 for( int i=0; i<vert_buffer->count; i++ )
857 {
858 vertex_tagged[i]=0;
859
860 int num_connected = 0;
861 // Create a list of polys that ref this vert
862 for( int j=0; j<mesh->polys.count; j++ )
863 {
864 struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys,j);
865 for( int k=0; k<poly->loop_total; k++ )
866 {
867 struct cxr_loop *loop = cxr_ab_ptr(&mesh->loops,poly->loop_start+k);
868 if( loop->index == i )
869 {
870 connected_planes[num_connected ++] = j;
871 break;
872 }
873 }
874 }
875 // Check all combinations for a similar normal
876 for( int j=0; j<num_connected-1; j++ )
877 {
878 for( int k=j+1; k<num_connected; k++ )
879 {
880 struct cxr_polygon *polyj = cxr_ab_ptr(&mesh->polys,connected_planes[j]);
881 struct cxr_polygon *polyk = cxr_ab_ptr(&mesh->polys,connected_planes[k]);
882
883 if( v3_dot(polyj->normal, polyk->normal) > CXR_PLANE_SIMILARITY_MAX )
884 goto IL_TAG_VERT;
885 }
886 }
887
888 // Check if all connected planes not are:
889 // - bounded by other planes
890 // - or coplanar
891
892 for( int j=0; j<num_connected; j++ )
893 for( int k=j+1; k<num_connected; k++ )
894 {
895 struct cxr_polygon *jpoly = cxr_ab_ptr(&mesh->polys, connected_planes[j]),
896 *kpoly = cxr_ab_ptr(&mesh->polys, connected_planes[k]);
897 v4f plane;
898 normal_to_plane( kpoly->normal, kpoly->center, plane );
899 for( int l=0; l<jpoly->loop_total; l++ )
900 {
901 struct cxr_loop *loop = cxr_ab_ptr(&mesh->loops, jpoly->loop_start+l);
902 if( plane_polarity( plane, vertices[loop->index] ) > 0.001 )
903 goto IL_TAG_VERT;
904 }
905 }
906
907 goto IL_TAG_NEXT_VERT;
908 IL_TAG_VERT: vertex_tagged[i] = 1;
909 IL_TAG_NEXT_VERT:;
910 }
911
912 free( connected_planes );
913
914 // Connect all marked verts that share an edge
915 // - We must take care not to completely isolate
916 // a polygon with marked edges all around it
917
918 int *hot_edge = malloc(mesh->edges.count*sizeof(int));
919 for( int i=0; i< mesh->edges.count; i++ )
920 hot_edge[i] = 0;
921
922 for( int i=0; i<mesh->polys.count; i ++ )
923 {
924 struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys,i);
925 int not_tagged = -1,
926 tag_count = 0;
927
928 for( int j=0; j<poly->loop_total; j++ )
929 {
930 struct cxr_loop *loop = cxr_ab_ptr(&mesh->loops, poly->loop_start+j);
931
932 if( !edge_tagged[ loop->edge_index ] )
933 {
934 if( not_tagged == -1 )
935 not_tagged = loop->edge_index;
936 else
937 goto IL_SKIP_NO_HOT_EDGE;
938 }
939 }
940
941 if( not_tagged != -1 )
942 hot_edge[not_tagged]=1;
943
944 IL_SKIP_NO_HOT_EDGE:;
945 }
946
947 // Connect edges that have verts tagged, but is not a hot edge
948 for( int i=0; i<mesh->edges.count; i ++ )
949 {
950 if( hot_edge[i] && preserve_hot_edges ) continue;
951
952 struct cxr_edge *edge = cxr_ab_ptr(&mesh->edges,i);
953 if( vertex_tagged[edge->i0] && vertex_tagged[edge->i1] )
954 edge_tagged[i] = 1;
955 }
956
957 #if 0
958 for( int i=0; i<vert_buffer->count; i++ )
959 if( vertex_tagged[i] )
960 cxr_debug_box( vertices[i], 0.03, (v4f){0.0,0.0,0.0,1.0});
961
962 for( int i=0; i < mesh->edges.count; i++ )
963 {
964 struct cxr_edge *edge = cxr_ab_ptr( &mesh->edges, i );
965 if( edge_tagged[i] )
966 cxr_debug_line( vertices[ edge->i0 ], vertices[ edge->i1 ], (v4f){0.0,0.0,0.0,1.0});
967
968 if( hot_edge[i] )
969 cxr_debug_line( vertices[ edge->i0 ], vertices[ edge->i1 ], (v4f){0.0,1.0,1.0,1.0});
970 }
971 #endif
972
973 // count regions
974 int *faces_tagged = malloc(mesh->polys.count*sizeof(int));
975 for( int i=0; i<mesh->polys.count; i++ )
976 faces_tagged[i] = -1;
977
978 int *solid_buffer = malloc( mesh->polys.count*sizeof(int) );
979 int solid_buffer_len = 0;
980 struct csolid
981 {
982 int start,count,edge_count;
983 v3f center;
984 }
985 *candidates = malloc( mesh->polys.count *sizeof(struct csolid) );
986 int candidate_count = 0;
987
988 struct tedge
989 {
990 int i0, i1;
991 }
992 *edge_references = malloc( mesh->edges.count *sizeof(struct tedge) );
993
994 for( int i=0; i<mesh->polys.count; i++ )
995 {
996 if( faces_tagged[i] != -1 ) continue;
997 faces_tagged[i] = i;
998
999 int *solid = &solid_buffer[ solid_buffer_len ];
1000 int solid_len = 0;
1001
1002 solid[solid_len++] = i;
1003
1004 int search_start = 0;
1005
1006 // Iterative search that connects regions of planes governed by rules:
1007 // - edge can add other face if the edge has less than two reflexes
1008 // - the face can no longer be used in future searches
1009
1010 IL_SEARCH_CONTINUE:;
1011
1012 int changed = 0;
1013 for( int j=search_start; j<solid_len; j++ )
1014 {
1015 struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys, solid[j]);
1016
1017 for( int k=0; k<poly->loop_total; k++ )
1018 {
1019 struct cxr_loop *loop = cxr_ab_ptr(&mesh->loops, poly->loop_start+k);
1020 struct cxr_edge *edge = cxr_ab_ptr(&mesh->edges, loop->edge_index );
1021
1022 if( faces_tagged[ loop->poly_right ] == -1 )
1023 {
1024 if( !edge_tagged[loop->edge_index] )
1025 {
1026 // TODO(harry):
1027 //
1028 // Need to look ahead 1 step to make sure he does not want
1029 // to add any more planes that are coplanar with some of
1030 // our existing group
1031 //
1032 // This can sort out SOME invalid configs, but not all.
1033 // It would be nice to find a more robust clustering algorithm for this.
1034 //
1035
1036 struct cxr_polygon *poly_to_add = cxr_ab_ptr(&mesh->polys, loop->poly_right );
1037 for( int l=0; l < poly_to_add->loop_total; l++ )
1038 {
1039 struct cxr_loop *loop1 = cxr_ab_ptr(&mesh->loops, poly_to_add->loop_start+l );
1040 struct cxr_polygon *future_face = cxr_ab_ptr(&mesh->polys, loop1->poly_right );
1041
1042 if( edge_tagged[ loop1->edge_index ] || loop1->poly_right == loop->poly_right )
1043 goto IL_SKIP_SIMILAR_PLANES;
1044
1045 for( int m=0; m<solid_len; m++ )
1046 if( solid[m] == loop1->poly_right )
1047 goto IL_SKIP_SIMILAR_PLANES;
1048
1049 for( int m=0; m<solid_len; m++ )
1050 {
1051 struct cxr_polygon *polym = cxr_ab_ptr(&mesh->polys,solid[m]);
1052 if( v3_dot( polym->normal,future_face->normal) > CXR_PLANE_SIMILARITY_MAX)
1053 goto IL_SKIP_PLANE_ADD;
1054 }
1055
1056 IL_SKIP_SIMILAR_PLANES:;
1057 }
1058
1059 // Check for vertices in the new poly that exist on a current plane.
1060 // this condition is an invalid configuration and should not be added.
1061
1062 solid[ solid_len ] = loop->poly_right;
1063
1064 if( cxr_valid_solid(mesh,vert_buffer,solid,solid_len+1 ) )
1065 {
1066 faces_tagged[ loop->poly_right ] = i;
1067 changed = 1;
1068 solid_len ++;
1069 }
1070 }
1071
1072 IL_SKIP_PLANE_ADD:;
1073 }
1074 }
1075 }
1076 search_start = solid_len;
1077 if(changed)
1078 goto IL_SEARCH_CONTINUE;
1079
1080 // The current method can create some invalid configurations
1081 // filter those out that dont work and un-tag the faces
1082 for( int j=0; j<solid_len-1; j++ )
1083 {
1084 for( int k=j+1; k<solid_len; k++ )
1085 {
1086 struct cxr_polygon *polyj = cxr_ab_ptr(&mesh->polys, solid[j]),
1087 *polyk = cxr_ab_ptr(&mesh->polys, solid[k]);
1088
1089 if( v3_dot( polyj->normal, polyk->normal ) > CXR_PLANE_SIMILARITY_MAX )
1090 {
1091 for( int l=0; l<solid_len; l++ )
1092 faces_tagged[ solid[l] ] = -1;
1093
1094 goto IL_CANCEL_SOLID;
1095 }
1096 }
1097 }
1098
1099 // Add entry
1100 struct csolid *csolid = &candidates[candidate_count ++];
1101 csolid->start = solid_buffer_len;
1102 csolid->count = solid_len;
1103 csolid->edge_count = 0;
1104
1105 v3_zero( csolid->center );
1106 for( int j=0; j<solid_len; j++ )
1107 {
1108 struct cxr_polygon *polyj = cxr_ab_ptr(&mesh->polys, solid[j]);
1109 v3_add( polyj->center, csolid->center, csolid->center );
1110 csolid->edge_count += polyj->loop_total;
1111 }
1112 v3_divs( csolid->center, solid_len, csolid->center );
1113
1114 solid_buffer_len += solid_len;
1115
1116 IL_CANCEL_SOLID:;
1117 }
1118
1119 free( edge_references );
1120
1121 // Create all candidates who have one or less non-manifolds edges
1122 // Loop each candidate, determine the manifold, and pick the best one
1123
1124 struct csolid *best_solid = NULL;
1125 int fewest_manifold_splits = INT32_MAX;
1126
1127 struct cxr_loop *best_manifold = malloc( mesh->loops.count *sizeof(struct cxr_loop) );
1128 int *best_manifold_splits = malloc( mesh->loops.count *sizeof(int) );
1129 int best_manifold_len = 0;
1130 int max_solid_faces = 0;
1131
1132 int *edge_list = malloc( mesh->edges.count *sizeof(int) );
1133 int *edge_lefts = malloc( mesh->edges.count *sizeof(int) );
1134 struct cxr_loop *manifold = malloc(mesh->edges.count*2*sizeof(struct cxr_loop));
1135 int *splits = malloc(mesh->edges.count*2*sizeof(int));
1136
1137 for( int i=0; i<candidate_count; i++ )
1138 {
1139 struct csolid *solid = &candidates[i];
1140 max_solid_faces = cxr_max(max_solid_faces,solid->count);
1141
1142 if( solid->count <= 2 )
1143 continue;
1144
1145 int init_reverse = 0;
1146 int unique_edge_count = 0;
1147
1148 for( int j=0; j<solid->count; j++ )
1149 {
1150 struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys, solid_buffer[solid->start+j]);
1151
1152 for( int k=0; k<poly->loop_total; k++ )
1153 {
1154 struct cxr_loop *loop = cxr_ab_ptr(&mesh->loops, poly->loop_start+k);
1155
1156 for( int l=0; l<unique_edge_count; l++ )
1157 if( edge_list[l] == loop->edge_index )
1158 goto IL_EDGE_ALREADY_PRESENT;
1159
1160 // Check if right edge references a polygon that is not
1161 // present inside the current solid candidate
1162 for( int l=0; l<solid->count; l++ )
1163 if( loop->poly_right == solid_buffer[solid->start+l] )
1164 goto IL_EDGE_ALREADY_PRESENT;
1165
1166 edge_list[ unique_edge_count ] = loop->edge_index;
1167 edge_lefts[ unique_edge_count ] = loop->poly_left;
1168
1169 if( unique_edge_count == 0 )
1170 {
1171 struct cxr_edge *edgeptr = cxr_ab_ptr(&mesh->edges, loop->edge_index);
1172 if( edgeptr->i1 == loop->index )
1173 init_reverse = 1;
1174 }
1175
1176 unique_edge_count ++;
1177 IL_EDGE_ALREADY_PRESENT:;
1178 }
1179 }
1180
1181 // This solid is already fully connected
1182 if( unique_edge_count == 0 )
1183 continue;
1184
1185 // Link edges together to create new manifold
1186 // Corners are created when two edges share a polygon face
1187 // This way we can split it into regions
1188
1189 for( int j=0; j<vert_buffer->count; j++ )
1190 vertex_tagged[j] = -1;
1191
1192 // Start with a loop edge which was tagged
1193 struct cxr_edge *current = cxr_ab_ptr(&mesh->edges, edge_list[0]);
1194
1195 int endpt = (!init_reverse)? current->i0: current->i1,
1196 start = endpt,
1197 curface = edge_lefts[0];
1198
1199 int manifold_len = 0;
1200 int split_count = 0;
1201
1202 IL_MANIFOLD_CONTINUE:
1203 for( int j=0; j<unique_edge_count; j++ )
1204 {
1205 struct cxr_edge *other = cxr_ab_ptr(&mesh->edges, edge_list[j]);
1206 if( other == current )
1207 continue;
1208
1209 if( other->i0 == endpt || other->i1 == endpt )
1210 {
1211 current = other;
1212 int lastpt = endpt;
1213
1214 if( other->i0 == endpt ) endpt = current->i1;
1215 else endpt = current->i0;
1216
1217 if( curface==edge_lefts[j] )
1218 {
1219 splits[ manifold_len ] = 1;
1220 split_count ++;
1221 }
1222 else
1223 splits[ manifold_len ] = 0;
1224
1225 // Append to intermidiary manifold
1226 manifold[ manifold_len ].edge_index = edge_list[j];
1227 manifold[ manifold_len ].poly_left = edge_lefts[j];
1228 manifold[ manifold_len ].index = lastpt;
1229 manifold[ manifold_len ].poly_right =
1230 polygon_edge_map[ edge_list[j]*2 ] == edge_lefts[j]?
1231 polygon_edge_map[ edge_list[j]*2+1 ]:
1232 polygon_edge_map[ edge_list[j]*2+0 ];
1233 manifold_len ++;
1234
1235 curface = edge_lefts[j];
1236
1237 if(endpt == start) goto IL_MANIFOLD_COMPLETE;
1238 goto IL_MANIFOLD_CONTINUE;
1239 }
1240 }
1241 cxr_log( "Failed to link manifold, count: %d\n", manifold_len );
1242
1243 for( int j=0; j<solid->count; j++ )
1244 {
1245 cxr_log( "p%d\n", solid_buffer[solid->start+j] );
1246 struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys, solid_buffer[solid->start+j]);
1247 cxr_debug_poly( mesh, poly, vertices, (v4f){0.2,0.0,0.0,1.0} );
1248 }
1249
1250 for( int j=0; j<unique_edge_count; j++ )
1251 {
1252 struct cxr_edge *uedge = cxr_ab_ptr(&mesh->edges, edge_list[j]);
1253 cxr_debug_line(vertices[uedge->i0],vertices[uedge->i1],(v4f){0.4,0.0,0.0,1.0});
1254 }
1255
1256 for( int j=0; j<manifold_len-1; j++ )
1257 {
1258 struct cxr_loop *lp0 = &manifold[j],
1259 *lp1 = &manifold[cxr_range(j+1,manifold_len)];
1260
1261 cxr_debug_line(vertices[lp0->index],vertices[lp1->index], colour_error );
1262 }
1263
1264 cxr_debug_mesh( mesh, vertices, (v4f){0.0,0.0,0.0, 0.9} );
1265 *error = CXR_ERROR_BAD_MANIFOLD;
1266
1267 free(edge_list);
1268 free(edge_lefts);
1269 free(manifold);
1270 free(splits);
1271 free(edge_tagged);
1272 free(vertex_tagged);
1273 free(hot_edge);
1274 free(faces_tagged);
1275 free(solid_buffer);
1276 free(candidates);
1277 free(best_manifold);
1278 free(best_manifold_splits);
1279 free(polygon_edge_map);
1280 return NULL;
1281
1282 IL_MANIFOLD_COMPLETE:;
1283
1284 if( manifold_len < unique_edge_count )
1285 continue;
1286 else
1287 {
1288 if( split_count < fewest_manifold_splits )
1289 {
1290 fewest_manifold_splits = split_count;
1291 best_solid = solid;
1292
1293 for( int j=0; j<manifold_len; j++ )
1294 {
1295 best_manifold[j] = manifold[j];
1296 best_manifold_splits[j] = splits[j];
1297 }
1298 best_manifold_len = manifold_len;
1299 }
1300 }
1301 }
1302
1303 free(edge_list);
1304 free(edge_lefts);
1305 free(manifold);
1306 free(splits);
1307
1308 if( max_solid_faces < 2 )
1309 {
1310 *error = CXR_ERROR_NO_SOLIDS;
1311 free(edge_tagged);
1312 free(vertex_tagged);
1313 free(hot_edge);
1314 free(faces_tagged);
1315 free(solid_buffer);
1316 free(candidates);
1317 free(best_manifold);
1318 free(best_manifold_splits);
1319 free(polygon_edge_map);
1320 return NULL;
1321 }
1322
1323 if( best_solid != NULL )
1324 {
1325 struct cxr_mesh *pullmesh =
1326 cxr_alloc_mesh( best_solid->edge_count, best_solid->edge_count, best_solid->count );
1327
1328 // Add existing faces to pullsolid, and delete from main mesh
1329 for( int i=0; i<best_solid->count; i++ )
1330 {
1331 int nface_id = pullmesh->polys.count;
1332
1333 struct cxr_polygon *exist_face = cxr_ab_ptr(&mesh->polys, solid_buffer[best_solid->start+i]);
1334 struct cxr_polygon *new_face = cxr_ab_empty(&pullmesh->polys);
1335
1336 *new_face = *exist_face;
1337 new_face->loop_start = pullmesh->loops.count;
1338
1339 for( int j=0; j<exist_face->loop_total; j++ )
1340 {
1341 struct cxr_loop *exist_loop = cxr_ab_ptr(&mesh->loops, exist_face->loop_start+j);
1342 struct cxr_loop *new_loop = cxr_ab_empty(&pullmesh->loops);
1343
1344 new_loop->index = exist_loop->index;
1345 new_loop->poly_left = nface_id;
1346 new_loop->poly_right = -1;
1347 new_loop->edge_index = 0;
1348 v2_copy( exist_loop->uv, new_loop->uv );
1349 }
1350
1351 exist_face->loop_total = -1;
1352 }
1353
1354 int new_polys = 0;
1355 int pullmesh_new_start = pullmesh->polys.count;
1356
1357 if( fewest_manifold_splits != 0 )
1358 {
1359 #if CXR_MANIFOLD_DEBUG
1360 for( int i=0; i<best_manifold_len; i++ )
1361 {
1362 int i0 = i,
1363 i1 = cxr_range(i+1,best_manifold_len);
1364
1365 cxr_debug_line( vertices[best_manifold[i0].index], vertices[best_manifold[i1].index], colour_error );
1366 if( best_manifold_splits[i] )
1367 cxr_debug_box( vertices[best_manifold[i0].index], 0.04, colour_success );
1368 }
1369 #endif
1370
1371 // This is a really strange observation, however it *seems* to apply to the kinds
1372 // of geometry we are dealing with. If the split count is odd, the manifold can be
1373 // created easily, no folding required.
1374 //
1375 // When it is even, it appears that internal implicit geometry is required, so we
1376 // need to fold the loops we create. Its really weird, but for some reason works on
1377 // the geometry rules we've defined.
1378 // TODO(harry): Find a well defined rule here.
1379
1380 int collapse_used_segments = (u32)fewest_manifold_splits & 0x1? 0: 1;
1381
1382 IL_MANIFOLD_BUILD_REPEAT:
1383
1384 for( int j=0; j<best_manifold_len; j++ )
1385 {
1386 if( best_manifold_splits[j] )
1387 {
1388 struct cxr_loop *loop = &best_manifold[j];
1389
1390 for( int k=1; k<best_manifold_len; k++ )
1391 {
1392 int index1 = cxr_range(j+k,best_manifold_len);
1393 struct cxr_loop *loop1 = &best_manifold[index1];
1394
1395 if( best_manifold_splits[index1] )
1396 {
1397 if( k==1 )
1398 break;
1399
1400 new_polys ++;
1401
1402 if( new_polys > best_manifold_len )
1403 {
1404 cxr_log( "Programming error: Too many new polys!\n" );
1405 exit(1);
1406 }
1407
1408 cxr_create_poly( pullmesh, vertices, best_manifold, k+1, j, best_manifold_len );
1409
1410 // Remove new section from manifold
1411 if( collapse_used_segments )
1412 {
1413 best_manifold_splits[j] = 0;
1414 best_manifold_splits[index1] = 0;
1415
1416 int new_length = (best_manifold_len-(k-1));
1417
1418 struct cxr_loop *new_manifold = malloc( new_length*sizeof(struct cxr_loop) );
1419 int *new_manifold_splits = malloc( new_length*sizeof(int) );
1420
1421 for( int l=0; l<new_length; l ++ )
1422 {
1423 int i_src = cxr_range( j+k+l, best_manifold_len );
1424 new_manifold[l] = best_manifold[i_src];
1425 new_manifold_splits[l] = best_manifold_splits[i_src];
1426 }
1427
1428 free( best_manifold );
1429 free( best_manifold_splits );
1430 best_manifold = new_manifold;
1431 best_manifold_splits = new_manifold_splits;
1432
1433 best_manifold_len = new_length;
1434
1435 goto IL_MANIFOLD_BUILD_REPEAT;
1436 }
1437
1438 j=j+k-1;
1439 break;
1440 }
1441 }
1442 }
1443 }
1444
1445 if( best_manifold_len && collapse_used_segments )
1446 {
1447 cxr_create_poly( pullmesh, vertices, best_manifold, best_manifold_len, 0, best_manifold_len );
1448 new_polys ++;
1449 }
1450 }
1451 else
1452 {
1453 cxr_create_poly( pullmesh, vertices, best_manifold, best_manifold_len, 0, best_manifold_len );
1454 new_polys = 1;
1455 }
1456
1457 // vert_buffer may be reallocated by the next section of code,
1458 // force a NULLref on vertices to catch any errors
1459 vertices = NULL;
1460
1461 // Implicit geometry reconstruction
1462 // If there's 3 or more planes, collide them together to see if any new
1463 // vertices need to be created on the mesh
1464 if( new_polys >= 3 )
1465 {
1466 for( int i=0; i<new_polys-2; i++ )
1467 {
1468 for( int j=i+1; j<new_polys-1; j++ )
1469 {
1470 for( int k=j+1; k<new_polys; k++ )
1471 {
1472 struct cxr_polygon *ptri = cxr_ab_ptr( &pullmesh->polys, pullmesh_new_start+i ),
1473 *ptrj = cxr_ab_ptr( &pullmesh->polys, pullmesh_new_start+j ),
1474 *ptrk = cxr_ab_ptr( &pullmesh->polys, pullmesh_new_start+k );
1475
1476 v4f planei, planej, planek;
1477 normal_to_plane(ptri->normal,ptri->center,planei);
1478 normal_to_plane(ptrj->normal,ptrj->center,planej);
1479 normal_to_plane(ptrk->normal,ptrk->center,planek);
1480
1481 v3f intersect;
1482
1483 if( plane_intersect(planei,planej,planek,intersect) )
1484 {
1485 // cxr_debug_box( intersect, 0.05, colour_error );
1486
1487 // Make sure this point is within the convex region, otherwise treat
1488 // it as a degenerate case
1489
1490 int point_valid = 1;
1491 for( int l=0; l<pullmesh->polys.count; l++ )
1492 {
1493 struct cxr_polygon *ptrl = cxr_ab_ptr(&pullmesh->polys,l);
1494 v4f planel;
1495
1496 normal_to_plane(ptrl->normal, ptrl->center, planel);
1497
1498 if( plane_polarity( planel, intersect ) > 0.01 )
1499 {
1500 cxr_log( "degen vert, planes %d, %d, %d [max:%d]\n", i,j,k, new_polys );
1501 *error = CXR_ERROR_DEGEN_IMPLICIT;
1502
1503 cxr_debug_poly( pullmesh, ptri, cxr_ab_ptr(vert_buffer,0), colours_random[3] );
1504 cxr_debug_poly( pullmesh, ptrj, cxr_ab_ptr(vert_buffer,0), colours_random[1] );
1505 cxr_debug_poly( pullmesh, ptrk, cxr_ab_ptr(vert_buffer,0), colours_random[2] );
1506
1507 point_valid = 0;
1508 break;
1509 }
1510 }
1511
1512 if( !point_valid ) continue;
1513
1514 // Extend faces to include this point
1515 int nvertid = vert_buffer->count;
1516 cxr_ab_push( vert_buffer, intersect );
1517
1518 ptrj->loop_start += 1;
1519 ptrk->loop_start += 2;
1520
1521 cxr_ab_reserve(&pullmesh->loops, 3);
1522 struct cxr_loop *lloopi = cxr_ab_empty_at(&pullmesh->loops, ptri->loop_start+ptri->loop_total),
1523 *lloopj = cxr_ab_empty_at(&pullmesh->loops, ptrj->loop_start+ptrj->loop_total),
1524 *lloopk = cxr_ab_empty_at(&pullmesh->loops, ptrk->loop_start+ptrk->loop_total);
1525
1526 lloopi->index = nvertid;
1527 lloopj->index = nvertid;
1528 lloopk->index = nvertid;
1529 lloopi->edge_index = 0; lloopj->edge_index = 0; lloopk->edge_index = 0;
1530 lloopi->poly_left = pullmesh_new_start+i;
1531 lloopj->poly_left = pullmesh_new_start+j;
1532 lloopk->poly_left = pullmesh_new_start+k;
1533 lloopi->poly_right = -1; lloopj->poly_right = -1; lloopk->poly_right = -1;
1534
1535 v2_zero(lloopi->uv);
1536 v2_zero(lloopj->uv);
1537 v2_zero(lloopk->uv);
1538
1539 ptri->loop_total ++;
1540 ptrj->loop_total ++;
1541 ptrk->loop_total ++;
1542
1543 // Adjust centers of faces
1544 v3_lerp( ptri->center, intersect, 1.0/(double)ptri->loop_total, ptri->center );
1545 v3_lerp( ptrj->center, intersect, 1.0/(double)ptrj->loop_total, ptrj->center );
1546 v3_lerp( ptrk->center, intersect, 1.0/(double)ptrk->loop_total, ptrk->center );
1547 }
1548 }
1549 }
1550 }
1551 }
1552
1553 // Copy faces from pullsolid into orig mesh
1554
1555 for( int i=0; i<new_polys; i++ )
1556 {
1557 int rface_id = mesh->polys.count;
1558
1559 struct cxr_polygon *pface = cxr_ab_ptr(&pullmesh->polys,pullmesh_new_start+i);
1560 struct cxr_polygon *rip_face = cxr_ab_empty(&mesh->polys);
1561
1562 rip_face->loop_start = mesh->loops.count;
1563 rip_face->loop_total = pface->loop_total;
1564 rip_face->material_id = -1;
1565
1566 for( int j=0; j<rip_face->loop_total; j++ )
1567 {
1568 struct cxr_loop *ploop = cxr_ab_ptr(&pullmesh->loops, pface->loop_start+pface->loop_total-j-1),
1569 *rloop = cxr_ab_empty(&mesh->loops);
1570
1571 rloop->index = ploop->index;
1572 rloop->poly_left = rface_id;
1573 rloop->poly_right = -1;
1574 rloop->edge_index = 0;
1575 v2_copy( ploop->uv, rloop->uv );
1576 }
1577
1578 v3_copy( pface->center, rip_face->center );
1579 v3_negate( pface->normal, rip_face->normal );
1580 }
1581
1582 cxr_mesh_clean_faces( mesh );
1583 cxr_mesh_clean_faces( pullmesh );
1584 cxr_mesh_clean_edges( mesh );
1585 cxr_mesh_clean_edges( pullmesh );
1586
1587 free(edge_tagged);
1588 free(vertex_tagged);
1589 free(hot_edge);
1590 free(faces_tagged);
1591 free(solid_buffer);
1592 free(candidates);
1593 free(best_manifold);
1594 free(best_manifold_splits);
1595 free(polygon_edge_map);
1596
1597 return pullmesh;
1598 }
1599
1600 free(edge_tagged);
1601 free(vertex_tagged);
1602 free(hot_edge);
1603 free(faces_tagged);
1604 free(solid_buffer);
1605 free(candidates);
1606 free(best_manifold);
1607 free(best_manifold_splits);
1608 free(polygon_edge_map);
1609
1610 return NULL;
1611 }
1612
1613 static struct cxr_mesh *cxr_to_internal_format(struct cxr_input_mesh *src, struct cxr_auto_buffer *abverts)
1614 {
1615 // Split mesh into islands
1616 struct cxr_mesh *mesh = cxr_alloc_mesh( src->edge_count, src->loop_count, src->poly_count );
1617 cxr_ab_init( abverts, sizeof(v3f), src->vertex_count );
1618
1619 // Copy input data into working mesh
1620 memcpy( cxr_ab_ptr( &mesh->edges, 0 ), src->edges, src->edge_count*sizeof(struct cxr_edge));
1621 memcpy( cxr_ab_ptr( &mesh->polys, 0 ), src->polys, src->poly_count*sizeof(struct cxr_polygon));
1622 memcpy( cxr_ab_ptr( abverts, 0 ), src->vertices, src->vertex_count*sizeof(v3f));
1623 mesh->edges.count = src->edge_count;
1624 mesh->loops.count = src->loop_count;
1625 mesh->polys.count = src->poly_count;
1626
1627 for( int i=0; i<src->loop_count; i++ )
1628 {
1629 struct cxr_loop *lp = cxr_ab_ptr(&mesh->loops,i);
1630 lp->index = src->loops[i].index;
1631 lp->edge_index = src->loops[i].edge_index;
1632 v2_copy( src->loops[i].uv, lp->uv );
1633 }
1634
1635 abverts->count = src->vertex_count;
1636
1637 return mesh;
1638 }
1639
1640 // Find farthest dot product along direction
1641 static double support_distance( v3f verts[3], v3f dir, double coef )
1642 {
1643 return cxr_maxf
1644 (
1645 coef * v3_dot( verts[0], dir ),
1646 cxr_maxf
1647 (
1648 coef * v3_dot( verts[1], dir ),
1649 coef * v3_dot( verts[2], dir )
1650 )
1651 );
1652 }
1653
1654 // Main function
1655 static void cxr_calculate_axis(
1656 struct cxr_texinfo *transform,
1657 v3f verts[3],
1658 v2f uvs[3],
1659 v2f texture_res
1660 )
1661 {
1662 v2f tT, bT; // Tangent/bitangent pairs for UV space and world
1663 v3f tW, bW;
1664
1665 v2_sub( uvs[0], uvs[1], tT );
1666 v2_sub( uvs[2], uvs[1], bT );
1667 v3_sub( verts[0], verts[1], tW );
1668 v3_sub( verts[2], verts[1], bW );
1669
1670 // Use arbitrary projection if there is no UV
1671 if( v2_length( tT ) < 0.0001 || v2_length( bT ) < 0.0001 )
1672 {
1673 v3f uaxis, normal, vaxis;
1674
1675 v3_copy( tW, uaxis );
1676 v3_normalize( uaxis );
1677
1678 v3_cross( tW, bW, normal );
1679 v3_cross( normal, uaxis, vaxis );
1680 v3_normalize( vaxis );
1681
1682 v3_copy( uaxis, transform->uaxis );
1683 v3_copy( vaxis, transform->vaxis );
1684 v2_zero( transform->offset );
1685
1686 v2_div( (v2f){128.0, 128.0}, texture_res, transform->scale );
1687 transform->winding = 1.0;
1688 return;
1689 }
1690
1691 // Detect if UV is reversed
1692 double winding = v2_cross( tT, bT ) >= 0.0f? 1.0f: -1.0f;
1693
1694 // UV projection reference
1695 v2f vY, vX;
1696 v2_muls((v2f){1,0}, winding, vX);
1697 v2_muls((v2f){0,1}, winding, vY);
1698
1699 // Reproject reference into world space, including skew
1700 v3f uaxis1, vaxis1;
1701
1702 v3_muls( tW, v2_cross(vX,bT) / v2_cross(bT,tT), uaxis1 );
1703 v3_muladds( uaxis1, bW, v2_cross(vX, tT) / v2_cross(tT,bT), uaxis1 );
1704
1705 v3_muls( tW, v2_cross(vY,bT) / v2_cross(bT,tT), vaxis1 );
1706 v3_muladds( vaxis1, bW, v2_cross(vY,tT) / v2_cross(tT,bT), vaxis1 );
1707
1708 v3_normalize( uaxis1 );
1709 v3_normalize( vaxis1 );
1710
1711 // Apply source transform to axis (yes, they also need to be swapped)
1712 v3f norm, uaxis, vaxis;
1713
1714 v3_cross( bW, tW, norm );
1715 v3_normalize(norm);
1716 v3_cross( vaxis1, norm, uaxis );
1717 v3_cross( uaxis1, norm, vaxis );
1718
1719 // real UV scale
1720 v2f uvmin, uvmax, uvdelta;
1721 v2_minv( uvs[0], uvs[1], uvmin );
1722 v2_minv( uvmin, uvs[2], uvmin );
1723 v2_maxv( uvs[0], uvs[1], uvmax );
1724 v2_maxv( uvmax, uvs[2], uvmax );
1725
1726 v2_sub( uvmax, uvmin, uvdelta );
1727
1728 // world-uv scale
1729 v2f uvminw, uvmaxw, uvdeltaw;
1730 uvminw[0] = -support_distance( verts, uaxis, -1.0f );
1731 uvmaxw[0] = support_distance( verts, uaxis, 1.0f );
1732 uvminw[1] = -support_distance( verts, vaxis, -1.0f );
1733 uvmaxw[1] = support_distance( verts, vaxis, 1.0f );
1734
1735 v2_sub( uvmaxw, uvminw, uvdeltaw );
1736
1737 // VMf uv scale
1738 v2f uv_scale;
1739 v2_div( uvdeltaw, uvdelta, uv_scale );
1740 v2_div( uv_scale, texture_res, uv_scale );
1741
1742 // Find offset via 'natural' point
1743 v2f target_uv, natural_uv, tex_offset;
1744 v2_mul( uvs[0], texture_res, target_uv );
1745
1746 natural_uv[0] = v3_dot( uaxis, verts[0] );
1747 natural_uv[1] = -v3_dot( vaxis, verts[0] );
1748 v2_div( natural_uv, uv_scale, natural_uv );
1749
1750 tex_offset[0] = target_uv[0]-natural_uv[0];
1751 tex_offset[1] = -(target_uv[1]-natural_uv[1]);
1752
1753 // Copy everything into output
1754 v3_copy( uaxis, transform->uaxis );
1755 v3_copy( vaxis, transform->vaxis );
1756 v2_copy( tex_offset, transform->offset );
1757 v2_copy( uv_scale, transform->scale );
1758 transform->winding = winding;
1759 }
1760
1761 CXR_API struct cxr_input_mesh *cxr_decompose(struct cxr_input_mesh *src)
1762 {
1763 #ifdef CXR_DEBUG_WRITE_MESH
1764 FILE *yeet = fopen( "/home/harry/Documents/blender_addons_remote/addons/convexer/solid.h", "w" );
1765
1766 fprintf( yeet, "v3f test_verts[] = {\n" );
1767 for( int i=0; i<src->vertex_count; i ++ )
1768 {
1769 fprintf( yeet, " { %f, %f, %f },\n",
1770 src->vertices[i][0],
1771 src->vertices[i][1],
1772 src->vertices[i][2] );
1773 }
1774 fprintf( yeet, "};\n" );
1775
1776 fprintf( yeet, "struct cxr_input_loop test_loops[] = {\n" );
1777 for( int i=0; i<src->loop_count; i ++ )
1778 {
1779 fprintf( yeet, " {%d, %d},\n",
1780 src->loops[i].index,
1781 src->loops[i].edge_index);
1782 }
1783 fprintf( yeet, "};\n" );
1784
1785 fprintf( yeet, "struct cxr_polygon test_polys[] = {\n" );
1786 for( int i=0; i <src->poly_count; i++ )
1787 {
1788 fprintf( yeet, " {%d, %d, {%f, %f, %f}, {%f, %f, %f}},\n",
1789 src->polys[i].loop_start,
1790 src->polys[i].loop_total,
1791 src->polys[i].normal[0],
1792 src->polys[i].normal[1],
1793 src->polys[i].normal[2],
1794 src->polys[i].center[0],
1795 src->polys[i].center[1],
1796 src->polys[i].center[2] );
1797 }
1798 fprintf( yeet, "};\n" );
1799
1800 fprintf( yeet, "struct cxr_edge test_edges[] = {\n" );
1801 for( int i=0; i<src->edge_count; i++ )
1802 {
1803 fprintf( yeet, " {%d, %d},\n",
1804 src->edges[i].i0,
1805 src->edges[i].i1
1806 );
1807 }
1808 fprintf( yeet, "};\n" );
1809
1810 fprintf( yeet, "struct cxr_input_mesh test_mesh = {\n" );
1811 fprintf( yeet, " .vertices = test_verts,\n" );
1812 fprintf( yeet, " .loops = test_loops,\n" );
1813 fprintf( yeet, " .edges = test_edges,\n" );
1814 fprintf( yeet, " .polys = test_polys,\n" );
1815 fprintf( yeet, " .poly_count=%d,\n", src->poly_count );
1816 fprintf( yeet, " .vertex_count=%d,\n", src->vertex_count );
1817 fprintf( yeet, " .edge_count=%d,\n",src->edge_count );
1818 fprintf( yeet, " .loop_count=%d\n", src->loop_count );
1819 fprintf( yeet, "};\n" );
1820
1821 fclose( yeet );
1822 #endif
1823
1824 struct cxr_auto_buffer abverts;
1825 struct cxr_mesh *main_mesh = cxr_to_internal_format( src, &abverts );
1826
1827 u32 error = 0x00;
1828
1829 struct cxr_auto_buffer solids;
1830 cxr_ab_init( &solids, sizeof(struct cxr_mesh *), 2 );
1831
1832 while(1)
1833 {
1834 struct cxr_mesh *res = cxr_pull_best_solid( main_mesh, &abverts, 0, &error );
1835 if( res )
1836 {
1837 cxr_ab_push( &solids, &res );
1838 if( error ) break;
1839 }
1840 else
1841 {
1842 if( error )
1843 {
1844 // If no solids error we can rety while preserving 'hot' edges
1845
1846 if( error & CXR_ERROR_NO_SOLIDS )
1847 {
1848 error = 0x00;
1849 res = cxr_pull_best_solid(main_mesh, &abverts, 1, &error);
1850
1851 if( res ) cxr_ab_push( &solids, &res );
1852 else break;
1853
1854 if( error ) break;
1855 }
1856 else break;
1857 }
1858 else
1859 break;
1860 }
1861 }
1862
1863 cxr_ab_push( &solids, &main_mesh );
1864
1865 if( !error )
1866 {
1867 for( int i=0; i<solids.count; i++ )
1868 {
1869 struct cxr_mesh **mptr = cxr_ab_ptr(&solids,i);
1870 cxr_debug_mesh( *mptr, cxr_ab_ptr(&abverts,0), colours_random[cxr_range(i,8)] );
1871 }
1872 }
1873
1874 for( int i=0; i<solids.count; i++ )
1875 {
1876 struct cxr_mesh **mptr = cxr_ab_ptr(&solids,i);
1877 cxr_free_mesh( *mptr );
1878 }
1879
1880 cxr_ab_free( &abverts );
1881 cxr_ab_free( &solids );
1882
1883 return NULL;
1884 }
1885
1886 static int cxr_cardinal( v3f a, int ignore )
1887 {
1888 int component = 0;
1889 double component_max = -CXR_BIG_NUMBER;
1890
1891 for( int i=0; i<3; i++ )
1892 {
1893 if( i == ignore ) continue;
1894
1895 if( fabs(a[i]) > component_max )
1896 {
1897 component_max = fabs(a[i]);
1898 component = i;
1899 }
1900 }
1901 double d = a[component] >= 0.0? 1.0: -1.0;
1902 v3_zero( a );
1903 a[component] = d;
1904
1905 return component;
1906 }
1907
1908 // Convert contiguous mesh to patch of displacments
1909 //
1910 static void cxr_write_disp(struct cxr_mesh *mesh, struct cxr_input_mesh *inputmesh,
1911 struct cxr_vdf *output,
1912 struct cxr_auto_buffer *abverts)
1913 {
1914 // Create a graph which maps vertices by their connections
1915 struct vertinfo
1916 {
1917 int con_start, con_count; // Index into the connection graph
1918 int boundary,
1919 used,
1920 search,
1921 corner;
1922
1923 double alpha;
1924 }
1925 *vertinfo = malloc( sizeof(struct vertinfo)*abverts->count );
1926 int *graph = malloc( sizeof(int) * mesh->edges.count*2 );
1927
1928 int con_pos = 0;
1929 for( int i=0; i<abverts->count; i++ )
1930 {
1931 struct vertinfo *info = &vertinfo[i];
1932 info->con_start = con_pos;
1933 info->con_count = 0;
1934 info->boundary = 0;
1935 info->corner = 0;
1936 info->used = 0;
1937 info->search = 0;
1938 info->alpha = 0.0;
1939
1940 for( int j=0; j<mesh->edges.count; j++ )
1941 {
1942 struct cxr_edge *edge = cxr_ab_ptr(&mesh->edges,j);
1943
1944 if( edge->i0 == i || edge->i1 == i )
1945 {
1946 graph[ con_pos ++ ] = edge->i0 == i? edge->i1: edge->i0;
1947 info->con_count ++;
1948
1949 if( edge->freestyle )
1950 info->boundary = 1;
1951 }
1952 }
1953 }
1954
1955 // Find best normal for brush patch. VBSP uses the original brush
1956 // as reference for decal projection.
1957 //
1958 // These are clamped to be cardinal directions as to make the VMF somewhat
1959 // human editable.
1960
1961 v3f avg_normal, refv, refu, refn;
1962 v3_zero(refv); v3_zero(refu); v3_zero(refn);
1963
1964 for( int i=0; i<mesh->polys.count; i++ )
1965 {
1966 struct cxr_polygon *poly = cxr_ab_ptr( &mesh->polys, i );
1967 v3_add( poly->normal, avg_normal, avg_normal );
1968 }
1969 v3_divs( avg_normal, mesh->polys.count, avg_normal );
1970 v3_normalize( avg_normal ); // TODO(harry): This can be zero length. Should add a safety check
1971 // normalize function that checks for small length before
1972 // carrying out, otherwise we get inf/nan values...
1973
1974 int n_cardinal = cxr_cardinal( avg_normal, -1 );
1975
1976 // Approximately matching the area of the result brush faces to the actual area
1977 // this is to assign a 'best guess' amount of lightmap texels.
1978 //
1979 double uv_area = 0.0, face_area = 0.0, sf;
1980 v2f uvboundmin, uvboundmax;
1981 v3f faceboundmin, faceboundmax;
1982 v2f uv_center;
1983 v3f face_center;
1984
1985 v2_fill( uvboundmin, CXR_BIG_NUMBER );
1986 v2_fill( uvboundmax, -CXR_BIG_NUMBER );
1987 v3_fill( faceboundmin, CXR_BIG_NUMBER );
1988 v3_fill( faceboundmax, -CXR_BIG_NUMBER );
1989
1990 for( int i=0; i<mesh->polys.count; i++ )
1991 {
1992 struct cxr_polygon *poly = cxr_ab_ptr( &mesh->polys, i );
1993
1994 for( int j=0; j<poly->loop_total; j++ )
1995 {
1996 struct cxr_loop *lp0 = cxr_ab_ptr(&mesh->loops, poly->loop_start+j);
1997 v2_minv( lp0->uv, uvboundmin, uvboundmin);
1998 v2_maxv( lp0->uv, uvboundmax, uvboundmax);
1999 v3_minv( cxr_ab_ptr(abverts,lp0->index), faceboundmin, faceboundmin );
2000 v3_maxv( cxr_ab_ptr(abverts,lp0->index), faceboundmax, faceboundmax );
2001 }
2002
2003 for( int j=0; j<poly->loop_total-2; j++ )
2004 {
2005 struct cxr_loop *lp0 = cxr_ab_ptr(&mesh->loops, poly->loop_start),
2006 *lp1 = cxr_ab_ptr(&mesh->loops, poly->loop_start+j+1),
2007 *lp2 = cxr_ab_ptr(&mesh->loops, poly->loop_start+j+2);
2008 v3f va, vb, orth;
2009 v3_sub( cxr_ab_ptr(abverts,lp1->index), cxr_ab_ptr(abverts,lp0->index), va );
2010 v3_sub( cxr_ab_ptr(abverts,lp2->index), cxr_ab_ptr(abverts,lp0->index), vb );
2011 v3_cross( va, vb, orth );
2012
2013 face_area += v3_length( orth ) / 2.0;
2014
2015 v2f uva, uvb;
2016 v2_sub( lp1->uv, lp0->uv, uva );
2017 v2_sub( lp2->uv, lp0->uv, uvb );
2018
2019 uv_area += fabs(v2_cross( uva, uvb )) / 2.0;
2020 }
2021 }
2022
2023 v3_add( faceboundmax, faceboundmin, face_center );
2024 v3_muls( face_center, 0.5, face_center );
2025 v2_add( uvboundmin, uvboundmax, uv_center );
2026 v2_muls( uv_center, 0.5, uv_center );
2027
2028 sf = sqrt( face_area / uv_area );
2029 int corner_count = 0;
2030
2031 // Vertex classification
2032 for( int i=0; i<abverts->count; i++ )
2033 {
2034 struct vertinfo *info = &vertinfo[i];
2035 if( !info->boundary ) continue;
2036
2037 int count = 0,
2038 non_manifold = 1;
2039
2040 for( int j=0; j<info->con_count; j++ )
2041 {
2042 int con = graph[info->con_start+j];
2043
2044 if( vertinfo[con].boundary )
2045 count ++;
2046 else
2047 non_manifold = 0;
2048 }
2049 if( count > 2 || non_manifold )
2050 {
2051 info->corner = 1;
2052 corner_count ++;
2053
2054 //cxr_debug_box( cxr_ab_ptr(abverts,i), 0.1, colour_success );
2055 }
2056 }
2057
2058 // TODO(harry): This currently only supports power 2 displacements
2059 // its quite straightforward to upgrade it.
2060 //
2061 int dispedge[16];
2062 v2f corner_uvs[4];
2063 int dispedge_count;
2064 int disp_count = 0;
2065
2066 for( int i=0; i<mesh->polys.count; i++ )
2067 {
2068 struct cxr_polygon *basepoly = cxr_ab_ptr(&mesh->polys,i);
2069
2070 for( int h=0; h<basepoly->loop_total; h ++ )
2071 {
2072 int i0 = h,
2073 i1 = cxr_range(h+1,basepoly->loop_total);
2074
2075 struct cxr_loop *l0 = cxr_ab_ptr(&mesh->loops, basepoly->loop_start+i0),
2076 *l1 = cxr_ab_ptr(&mesh->loops, basepoly->loop_start+i1);
2077 struct vertinfo *info = &vertinfo[ l0->index ];
2078
2079 if( info->corner )
2080 {
2081 int corner_count = 1;
2082
2083 struct cxr_material *matptr =
2084 basepoly->material_id < 0 || inputmesh->material_count == 0?
2085 &cxr_nodraw:
2086 &inputmesh->materials[ basepoly->material_id ];
2087
2088 dispedge_count = 2;
2089 dispedge[0] = l0->index;
2090 dispedge[1] = l1->index;
2091 v2_copy( l0->uv, corner_uvs[0] );
2092
2093 // Consume (remove) faces we use for corners
2094 basepoly->loop_total = -1;
2095
2096 //cxr_debug_box( cxr_ab_ptr(abverts,l0->index),0.08,(v4f){0.0,0.0,1.0,1.0});
2097
2098 // Collect edges
2099 // --------------------
2100
2101 while( dispedge_count < 17 )
2102 {
2103 struct vertinfo *edge_head = &vertinfo[dispedge[dispedge_count-1]];
2104 int newvert = 0;
2105
2106 if( edge_head->corner )
2107 {
2108 // Find a polygon that has the edge C-1 -> C
2109 for( int j=0; j<mesh->polys.count && !newvert; j++ )
2110 {
2111 struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys,j);
2112
2113 for( int k=0; k<poly->loop_total; k ++ )
2114 {
2115 int i0 = k,
2116 i1 = cxr_range(k+1,poly->loop_total);
2117
2118 struct cxr_loop *l0 = cxr_ab_ptr(&mesh->loops, poly->loop_start+i0),
2119 *l1 = cxr_ab_ptr(&mesh->loops, poly->loop_start+i1);
2120
2121 if( l0->index == dispedge[dispedge_count-2] &&
2122 l1->index == dispedge[dispedge_count-1] )
2123 {
2124 // Take the vertex after that edge
2125 v2_copy( l1->uv, corner_uvs[corner_count ++] );
2126
2127 int i2 = cxr_range(i1+1,poly->loop_total);
2128 struct cxr_loop *l2 = cxr_ab_ptr(&mesh->loops, poly->loop_start+i2);
2129
2130 dispedge[dispedge_count ++] = l2->index;
2131 newvert = 1;
2132 poly->loop_total = -1;
2133 break;
2134 }
2135 }
2136 }
2137 }
2138 else
2139 {
2140 for( int j=0; j<edge_head->con_count; j++ )
2141 {
2142 int con = graph[edge_head->con_start+j];
2143
2144 if( con == -1 )
2145 continue;
2146
2147 if( dispedge_count > 1 )
2148 if( con == dispedge[dispedge_count-2] )
2149 continue;
2150
2151 struct vertinfo *coninfo = &vertinfo[con];
2152
2153 if( !coninfo->boundary )
2154 continue;
2155
2156 /*
2157 cxr_debug_arrow( cxr_ab_ptr(abverts,dispedge[dispedge_count-1]),
2158 cxr_ab_ptr(abverts,con),
2159 (v3f){0,0,1},
2160 0.1,
2161 colour_success );
2162 */
2163
2164 dispedge[ dispedge_count ++ ] = con;
2165 newvert = 1;
2166
2167 break;
2168 }
2169 }
2170
2171 if( !newvert )
2172 {
2173 cxr_debug_box(cxr_ab_ptr(abverts,dispedge[dispedge_count-1]), 0.1, colour_error);
2174 break;
2175 }
2176 }
2177
2178 // --------------------
2179 // Edges collected
2180
2181 v2f va, vb;
2182 v2_sub( corner_uvs[1], corner_uvs[0], va );
2183 v2_sub( corner_uvs[2], corner_uvs[0], vb );
2184
2185 // Connect up the grid
2186 //
2187 // 0 1 2 3 4
2188 // 15 a b c d
2189 // 14 e f g h
2190 // 13 i j k l
2191 // 12 m n o p
2192 //
2193 // Example: a := common unused vertex that is connected to
2194 // by 1 and 15. Or y-1, and x-1 on the grid.
2195 // g := c and f common vert ^
2196 //
2197 int grid[25];
2198
2199 for( int j=0; j<5; j++ ) grid[j] = dispedge[j];
2200 for( int j=1; j<5; j++ ) grid[j*5+4] = dispedge[j+4];
2201 for( int j=0; j<4; j++ ) grid[4*5+3-j] = dispedge[j+9];
2202 for( int j=1; j<4; j++ ) grid[j*5] = dispedge[16-j];
2203
2204 // Grid fill
2205 for( int j=1; j<4; j++ )
2206 {
2207 for( int k=1; k<4; k++ )
2208 {
2209 int s0 = grid[(j-1)*5+k],
2210 s1 = grid[j*5+k-1];
2211
2212 struct vertinfo *va = &vertinfo[s0],
2213 *vb = &vertinfo[s1];
2214
2215 // Find a common vertex between s0 and s1
2216
2217 for( int l=0; l<va->con_count; l ++ )
2218 {
2219 for( int m=0; m<vb->con_count; m ++ )
2220 {
2221 int cona = graph[va->con_start+l],
2222 conb = graph[vb->con_start+m];
2223
2224 if( cona == conb )
2225 {
2226 if( vertinfo[cona].used || vertinfo[cona].boundary )
2227 continue;
2228
2229 grid[ j*5+k ] = cona;
2230 vertinfo[cona].used = 1;
2231
2232 goto IL_MATCHED_DISP_INTERIOR_VERT;
2233 }
2234 }
2235 }
2236
2237 // Broken displacement
2238 cxr_log( "Broken displacement!\n" );
2239 free( graph );
2240 free( vertinfo );
2241 return;
2242
2243 IL_MATCHED_DISP_INTERIOR_VERT:;
2244 }
2245 }
2246
2247 // Create brush vertices based on UV map
2248
2249 // Create V reference based on first displacement.
2250 // TODO(harry): This is not the moststable selection method!
2251 // faces can come in any order, so the first disp will of course
2252 // always vary. Additionaly the triangle can be oriented differently.
2253 //
2254 // Improvement can be made by selecting a first disp/triangle based
2255 // on deterministic factors.
2256 //
2257 if( disp_count == 0 )
2258 {
2259 struct cxr_texinfo tx;
2260 v3f tri_ref[3];
2261 v3_copy( cxr_ab_ptr(abverts,dispedge[0]), tri_ref[0] );
2262 v3_copy( cxr_ab_ptr(abverts,dispedge[4]), tri_ref[1] );
2263 v3_copy( cxr_ab_ptr(abverts,dispedge[8]), tri_ref[2] );
2264 cxr_calculate_axis( &tx, tri_ref, corner_uvs, (v2f){512,512} );
2265
2266 v3_muls( tx.vaxis, -1.0, refv );
2267 int v_cardinal = cxr_cardinal( refv, -1 );
2268
2269 v3_cross( tx.vaxis, tx.uaxis, refn );
2270 v3_muls( refn, -tx.winding, refn );
2271
2272 int n1_cardinal = cxr_cardinal( refn, v_cardinal );
2273
2274 //v3_copy( avg_normal, refn );
2275 int u_cardinal = 0;
2276 if( u_cardinal == n1_cardinal || u_cardinal == v_cardinal ) u_cardinal ++;
2277 if( u_cardinal == n1_cardinal || u_cardinal == v_cardinal ) u_cardinal ++;
2278
2279 v3_zero(refu);
2280 refu[u_cardinal] = tx.uaxis[u_cardinal] > 0.0? 1.0: -1.0;
2281
2282 v3f p0, pv, pu, pn;
2283
2284 v3_copy( face_center, p0 );
2285 v3_muladds( face_center, refn, 1.5, pn );
2286 v3_muladds( face_center, refv, 1.5, pv );
2287 v3_muladds( face_center, refu, 1.5, pu );
2288
2289 if( cxr_settings.debug )
2290 {
2291 cxr_debug_line( p0, pn, (v4f){0.0,0.0,1.0,1.0});
2292 cxr_debug_line( p0, pv, (v4f){0.0,1.0,0.0,1.0});
2293 cxr_debug_line( p0, pu, (v4f){1.0,0.0,0.0,1.0});
2294 cxr_debug_line( tri_ref[0], tri_ref[1], (v4f){1.0,1.0,1.0,1.0} );
2295 cxr_debug_line( tri_ref[1], tri_ref[2], (v4f){1.0,1.0,1.0,1.0} );
2296 cxr_debug_line( tri_ref[2], tri_ref[0], (v4f){1.0,1.0,1.0,1.0} );
2297 }
2298 }
2299
2300 // Create world cordinates
2301 v3f world_corners[8];
2302 v2f world_uv[4];
2303
2304 for( int j=0; j<4; j++ )
2305 {
2306 v2f local_uv;
2307 v2_sub( corner_uvs[j], uv_center, local_uv );
2308 v2_copy( corner_uvs[j], world_uv[j] );
2309 v2_muls( local_uv, sf, local_uv );
2310
2311 v3_muls( refu, local_uv[0], world_corners[j] );
2312 v3_muladds( world_corners[j], refv, local_uv[1], world_corners[j] );
2313 v3_add( face_center, world_corners[j], world_corners[j] );
2314 }
2315
2316 double *colour = colours_random[cxr_range(disp_count,8)];
2317
2318 for( int j=0; j<4; j++ )
2319 v3_muladds( world_corners[j], refn, -1.0, world_corners[j+4] );
2320
2321 if( cxr_settings.debug )
2322 {
2323 cxr_debug_arrow( world_corners[0], world_corners[1], avg_normal, 0.1, colour );
2324 cxr_debug_arrow( world_corners[1], world_corners[2], avg_normal, 0.1, colour );
2325 cxr_debug_arrow( world_corners[2], world_corners[3], avg_normal, 0.1, colour );
2326 cxr_debug_arrow( world_corners[3], world_corners[0], avg_normal, 0.1, colour );
2327 }
2328
2329 /*
2330 cxr_debug_arrow( world_corners[0+4], world_corners[1+4], avg_normal, 0.1, colour );
2331 cxr_debug_arrow( world_corners[1+4], world_corners[2+4], avg_normal, 0.1, colour );
2332 cxr_debug_arrow( world_corners[2+4], world_corners[3+4], avg_normal, 0.1, colour );
2333 cxr_debug_arrow( world_corners[3+4], world_corners[0+4], avg_normal, 0.1, colour );
2334 */
2335
2336 // Apply world transform
2337 for( int j=0; j<8; j++ )
2338 {
2339 v3_muls( world_corners[j], cxr_context.scale_factor, world_corners[j] );
2340 world_corners[j][2] += cxr_context.offset_z;
2341 }
2342
2343 struct cxr_texinfo texinfo_shared;
2344 cxr_calculate_axis( &texinfo_shared, world_corners, world_uv,
2345 (v2f){ matptr->res[0], matptr->res[1] } );
2346
2347 // Write brush
2348 cxr_vdf_node( output, "solid" );
2349 cxr_vdf_ki32( output, "id", ++ cxr_context.brush_count );
2350
2351 int sides[6][3] =
2352 {{ 0, 1, 2 },
2353 { 4, 6, 5 },
2354 { 4, 1, 0 },
2355 { 7, 0, 3 },
2356 { 6, 2, 1 },
2357 { 6, 3, 2 }};
2358
2359 v3f normals[25];
2360 double distances[25];
2361
2362 v3f lside0, lside1, lref, vdelta, vworld;
2363 double tx, ty;
2364
2365 for( int j=0; j<5; j++ )
2366 {
2367 ty = (double)j/(double)(5-1);
2368
2369 v3_lerp( world_corners[0], world_corners[3], ty, lside0 );
2370 v3_lerp( world_corners[1], world_corners[2], ty, lside1 );
2371
2372 for( int k=0; k<5; k++ )
2373 {
2374 int index = j*5+k;
2375
2376 tx = (double)k/(double)(5-1);
2377 v3_lerp( lside0, lside1, tx, lref );
2378 v3_muls( cxr_ab_ptr(abverts, grid[index]), cxr_context.scale_factor, vworld );
2379 vworld[2] += cxr_context.offset_z;
2380
2381 v3_sub( vworld, lref, vdelta );
2382 v3_copy( vdelta, normals[index] );
2383 v3_normalize( normals[index] );
2384 distances[index] = v3_dot( vdelta, normals[index] );
2385 }
2386 }
2387
2388 for( int j=0; j<6; j++ )
2389 {
2390 int *side = sides[j];
2391
2392 cxr_vdf_node( output, "side" );
2393 cxr_vdf_ki32( output, "id", ++ cxr_context.face_count );
2394 cxr_vdf_plane( output, "plane", world_corners[side[2]],
2395 world_corners[side[1]],
2396 world_corners[side[0]] );
2397
2398 cxr_vdf_kv( output, "material", matptr->vmt_path );
2399
2400 cxr_vdf_kaxis( output, "uaxis",
2401 texinfo_shared.uaxis,
2402 texinfo_shared.offset[0],
2403 texinfo_shared.scale[0] );
2404 cxr_vdf_kaxis( output, "vaxis",
2405 texinfo_shared.vaxis,
2406 texinfo_shared.offset[1],
2407 texinfo_shared.scale[1] );
2408
2409 cxr_vdf_kdouble( output, "rotation", 0.0 );
2410 cxr_vdf_ki32( output, "lightmapscale", cxr_settings.lightmap_scale );
2411 cxr_vdf_ki32( output, "smoothing_groups", 0 );
2412
2413 if( j == 0 )
2414 {
2415 cxr_vdf_node( output, "dispinfo" );
2416 cxr_vdf_ki32( output, "power", 2 );
2417 cxr_vdf_kv3f( output, "startposition", world_corners[0] );
2418 cxr_vdf_ki32( output, "flags", 0 );
2419 cxr_vdf_kdouble( output, "elevation", 0.0 );
2420 cxr_vdf_ki32( output, "subdiv", 0 );
2421
2422 cxr_vdf_node( output, "normals" );
2423 for( int k=0; k<5; k++ )
2424 cxr_vdf_karrv3f( output, "row", k, &normals[k*5], 5 );
2425 cxr_vdf_edon( output );
2426
2427 cxr_vdf_node( output, "distances" );
2428 for( int k=0; k<5; k++ )
2429 cxr_vdf_karrdouble( output, "row", k, &distances[k*5], 5 );
2430 cxr_vdf_edon( output );
2431
2432 // TODO: This might be needed for compiling...
2433 /*
2434 cxr_vdf_node( output, "offsets" );
2435 for( int k=0; k<5; k++ )
2436 cxr_vdf_printf( output, "\"row%d\" \"0 0 0 0 0 0 0 0 0 0 0 0 0 0 0\"\n", k );
2437 cxr_vdf_edon( output );
2438
2439 cxr_vdf_node( output, "offset_normals" );
2440 for( int k=0; k<5; k++ )
2441 cxr_vdf_printf( output, "\"row%d\" \"0 0 1 0 0 1 0 0 1 0 0 1 0 0 1\"\n", k );
2442 cxr_vdf_edon( output );
2443
2444 cxr_vdf_node( output, "alphas" );
2445 for( int k=0; k<5; k++ )
2446 cxr_vdf_printf( output, "\"row%d\" \"0 0 0 0 0\"\n", k );
2447 cxr_vdf_edon( output );
2448
2449 cxr_vdf_node( output, "triangle_tags" );
2450 for( int k=0; k<5-1; k++ )
2451 cxr_vdf_printf( output, "\"row%d\" \"9 9 9 9 9 9 9 9\"\n", k );
2452 cxr_vdf_edon( output );
2453
2454 cxr_vdf_node( output, "allowed_verts" );
2455 cxr_vdf_printf( output, "\"10\" \"-1 -1 -1 -1 -1 -1 -1 -1 -1 -1\"\n" );
2456 cxr_vdf_edon( output );
2457 */
2458 cxr_vdf_edon( output );
2459 }
2460
2461 cxr_vdf_edon( output );
2462 }
2463
2464 cxr_vdf_node(output, "editor");
2465 cxr_vdf_colour255(output,"color", colours_random[cxr_range(cxr_context.brush_count,8)]);
2466 cxr_vdf_ki32(output,"visgroupshown",1);
2467 cxr_vdf_ki32(output,"visgroupautoshown",1);
2468 cxr_vdf_edon(output);
2469
2470 cxr_vdf_edon( output );
2471 disp_count ++;
2472 }
2473 }
2474 }
2475
2476 // Main loop
2477 #if 0
2478 int pool[25];
2479 for( int i=0; i<abverts->count; i++ )
2480 {
2481 struct vertinfo *info = &vertinfo[i];
2482 if( info->boundary || info->used )
2483 continue;
2484
2485 // Gather all vertices in this displacement
2486 int poolcount = 1,
2487 front_start = 0,
2488 front_count = 1;
2489 pool[0] = i;
2490 info->used = 1;
2491
2492 IL_GATHER_LOOP:;
2493
2494 int new_front_start = poolcount;
2495
2496 for( int j=0; j<front_count; j++ )
2497 {
2498 struct vertinfo *frontvert = &vertinfo[pool[front_start+j]];
2499
2500 for( int k=0; k<frontvert->con_count; k++ )
2501 {
2502 int conid = graph[frontvert->con_start+k];
2503 struct vertinfo *con = &vertinfo[conid];
2504
2505 if( frontvert->boundary && !con->boundary )
2506 continue;
2507
2508 if( con->used )
2509 continue;
2510
2511 if( poolcount == 25 )
2512 goto IL_DISP_ERROR_COUNT;
2513
2514 con->used = 1;
2515 pool[ poolcount ++ ] = conid;
2516 }
2517 }
2518
2519 if( poolcount > new_front_start )
2520 {
2521 front_start = new_front_start;
2522 front_count = poolcount-front_start;
2523
2524 goto IL_GATHER_LOOP;
2525 }
2526
2527 if( poolcount != 25 )
2528 {
2529 IL_DISP_ERROR_COUNT:
2530 for( int i=0; i<poolcount; i++ )
2531 cxr_debug_box( cxr_ab_ptr(abverts,pool[i]), 0.02, colour_error );
2532
2533 free(graph);
2534 free(vertinfo);
2535
2536 cxr_log("Invalid displacement (>25 verts)\n");
2537 return;
2538 }
2539
2540 int corners[4];
2541 int corner_count = 0;
2542 struct cxr_loop *cornerloops[4];
2543
2544 // Find corners, and get their loops (for uvs)
2545 // note: the mesh must be split where there is texture seams
2546 // so that two different uv'd loops cant ref the same vertex
2547 //
2548 for( int j=0; j<poolcount; j++ )
2549 {
2550 if( vertinfo[pool[j]].corner )
2551 {
2552 if( corner_count == 4 )
2553 {
2554 corner_count = -1;
2555 break;
2556 }
2557
2558 corners[corner_count] = j;
2559
2560 // find loop that includes this vert
2561 for( int k=0; k<mesh->loops.count; k++ )
2562 {
2563 struct cxr_loop *lp = cxr_ab_ptr(&mesh->loops,k);
2564 if( lp->index == pool[j] )
2565 {
2566 cornerloops[corner_count] = lp;
2567 break;
2568 }
2569 }
2570
2571 corner_count ++;
2572 }
2573 }
2574
2575 if( corner_count !=4 )
2576 {
2577 free(graph);
2578 free(vertinfo);
2579 cxr_log( "Invalid displacement (!=4 corners)\n" );
2580 return;
2581 }
2582
2583 int pivot = corners[0];
2584 }
2585 #endif
2586
2587 free( graph );
2588 free( vertinfo );
2589 }
2590
2591 static int cxr_solid_checkerr(struct cxr_mesh *mesh, struct cxr_auto_buffer *abverts )
2592 {
2593 int err_count = 0;
2594
2595 for( int i=0; i<mesh->polys.count; i++ )
2596 {
2597 int plane_err = 0;
2598
2599 struct cxr_polygon *poly = cxr_ab_ptr(&mesh->polys,i);
2600 v4f plane;
2601
2602 normal_to_plane( poly->normal, poly->center, plane );
2603
2604 for( int j=0; j<poly->loop_total; j++ )
2605 {
2606 struct cxr_loop *loop = cxr_ab_ptr(&mesh->loops, poly->loop_start+j);
2607 double *vert = cxr_ab_ptr(abverts,loop->index);
2608
2609 if( fabs(plane_polarity(plane,vert)) > 0.0025 )
2610 {
2611 err_count ++;
2612 plane_err ++;
2613
2614 v3f ref;
2615 plane_project_point( plane, vert, ref );
2616
2617 cxr_debug_line( ref, vert, colour_error );
2618 cxr_debug_box( vert, 0.1, colour_error );
2619 }
2620 }
2621
2622 if( plane_err )
2623 cxr_debug_poly( mesh, poly, cxr_ab_ptr(abverts,0), colour_error );
2624 }
2625
2626 return err_count;
2627 }
2628
2629 CXR_API i32 cxr_convert_mesh_to_vmf(struct cxr_input_mesh *src, struct cxr_vdf *output)
2630 {
2631 // Split mesh into islands
2632 struct cxr_auto_buffer abverts;
2633 struct cxr_mesh *main_mesh = cxr_to_internal_format(src, &abverts);
2634
2635 u32 error = 0x00;
2636 int invalid_count = 0;
2637
2638 struct solidinf
2639 {
2640 struct cxr_mesh *pmesh;
2641 int is_displacement, invalid;
2642 };
2643
2644 struct cxr_auto_buffer solids;
2645 cxr_ab_init( &solids, sizeof(struct solidinf), 2 );
2646
2647 // Preprocessor 1: Island seperation
2648 // ---------------
2649
2650 while(1)
2651 {
2652 struct cxr_mesh *res = cxr_pull_island( main_mesh );
2653 if( res )
2654 {
2655 cxr_ab_push( &solids, &(struct solidinf){ res, 0 });
2656 }
2657 else break;
2658 }
2659 cxr_ab_push( &solids, &(struct solidinf){main_mesh,0} );
2660
2661 // Preprocessor 2: Displacement break-out and error checking
2662 // ---------------
2663 for( int i=0; i<solids.count; i++ )
2664 {
2665 struct solidinf *pinf = cxr_ab_ptr(&solids,i);
2666
2667 for( int j=0; j<pinf->pmesh->polys.count; j++ )
2668 {
2669 struct cxr_polygon *poly = cxr_ab_ptr( &pinf->pmesh->polys, j );
2670
2671 for( int k=0; k<poly->loop_total; k++ )
2672 {
2673 struct cxr_loop *lp = cxr_ab_ptr( &pinf->pmesh->loops, poly->loop_start+k );
2674 struct cxr_edge *edge = cxr_ab_ptr( &pinf->pmesh->edges, lp->edge_index );
2675
2676 if( edge->freestyle )
2677 goto IL_SOLID_IS_DISPLACEMENT;
2678 }
2679 }
2680
2681 if( cxr_solid_checkerr( pinf->pmesh, &abverts ) )
2682 {
2683 pinf->invalid = 1;
2684 invalid_count ++;
2685 }
2686
2687 continue;
2688 IL_SOLID_IS_DISPLACEMENT:;
2689
2690 pinf->is_displacement = 1;
2691 cxr_write_disp( pinf->pmesh, src, output, &abverts );
2692 }
2693
2694 // Preprocessor 3: Breakup non-convex shapes into sub-solids
2695 // ---------------
2696 int sources_count = solids.count;
2697
2698 for( int i=0; i<sources_count; i++ )
2699 {
2700 struct solidinf pinf = *(struct solidinf *)cxr_ab_ptr(&solids, i);
2701
2702 if( pinf.is_displacement || pinf.invalid )
2703 continue;
2704
2705 while(1)
2706 {
2707 struct cxr_mesh *res = cxr_pull_best_solid( pinf.pmesh, &abverts, 0, &error );
2708
2709 if( res )
2710 {
2711 cxr_ab_push( &solids, &(struct solidinf){res,0} );
2712 if( error )
2713 break;
2714 }
2715 else
2716 {
2717 if( error )
2718 {
2719 // If no solids error we can rety while preserving 'hot' edges
2720
2721 if( error & CXR_ERROR_NO_SOLIDS )
2722 {
2723 error = 0x00;
2724 res = cxr_pull_best_solid(pinf.pmesh, &abverts, 1, &error);
2725
2726 if( res ) cxr_ab_push( &solids, &(struct solidinf){res,0} );
2727 else break;
2728
2729 if( error ) break;
2730 }
2731 else
2732 break;
2733 }
2734 else
2735 break;
2736 }
2737 }
2738 }
2739
2740 if( cxr_settings.debug )
2741 {
2742 for( int i=0; i<solids.count; i++ )
2743 {
2744 struct solidinf *solid = cxr_ab_ptr(&solids,i);
2745
2746 if( !solid->is_displacement )
2747 cxr_debug_mesh( solid->pmesh, cxr_ab_ptr(&abverts,0), colours_random[cxr_range(i,8)] );
2748 }
2749 }
2750
2751 if( error )
2752 {
2753 for( int i=0; i<solids.count; i++ )
2754 {
2755 struct solidinf *solid = cxr_ab_ptr(&solids,i);
2756 cxr_free_mesh( solid->pmesh );
2757 }
2758
2759 cxr_ab_free( &abverts );
2760 cxr_ab_free( &solids );
2761 return error;
2762 }
2763
2764 // Turn all those solids into VMF brushes
2765 // --------------------------------------
2766 for( int i=0; i<solids.count; i++ )
2767 {
2768 struct solidinf *solid = cxr_ab_ptr(&solids,i);
2769
2770 if( solid->is_displacement ) continue;
2771
2772 cxr_vdf_node( output, "solid" );
2773 cxr_vdf_ki32( output, "id", ++ cxr_context.brush_count );
2774
2775 for( int j=0; j<solid->pmesh->polys.count; j++ )
2776 {
2777 struct cxr_polygon *poly = cxr_ab_ptr( &solid->pmesh->polys, j );
2778 struct cxr_loop *ploops = cxr_ab_ptr(&solid->pmesh->loops, poly->loop_start);
2779 struct cxr_material *matptr =
2780 poly->material_id < 0 || src->material_count == 0?
2781 &cxr_nodraw:
2782 &src->materials[ poly->material_id ];
2783
2784 cxr_vdf_node( output, "side" );
2785 cxr_vdf_ki32( output, "id", ++ cxr_context.face_count );
2786
2787 v3f verts[3]; v2f uvs[3];
2788
2789 v3_muls( cxr_ab_ptr(&abverts, ploops[0].index), cxr_context.scale_factor, verts[0] );
2790 v3_muls( cxr_ab_ptr(&abverts, ploops[1].index), cxr_context.scale_factor, verts[1] );
2791 v3_muls( cxr_ab_ptr(&abverts, ploops[2].index), cxr_context.scale_factor, verts[2] );
2792 verts[0][2] += cxr_context.offset_z;
2793 verts[1][2] += cxr_context.offset_z;
2794 verts[2][2] += cxr_context.offset_z;
2795
2796 v2_copy( ploops[0].uv, uvs[0] );
2797 v2_copy( ploops[1].uv, uvs[1] );
2798 v2_copy( ploops[2].uv, uvs[2] );
2799
2800 cxr_vdf_plane( output, "plane", verts[2], verts[1], verts[0] );
2801 cxr_vdf_kv( output, "material", matptr->vmt_path );
2802
2803 struct cxr_texinfo trans;
2804 cxr_calculate_axis(&trans, verts, uvs, (double[2]){ matptr->res[0], matptr->res[1] });
2805
2806 cxr_vdf_kaxis(output, "uaxis", trans.uaxis, trans.offset[0], trans.scale[0]);
2807 cxr_vdf_kaxis(output, "vaxis", trans.vaxis, trans.offset[1], trans.scale[1]);
2808
2809 cxr_vdf_kdouble(output, "rotation", 0.0 );
2810 cxr_vdf_ki32(output, "lightmapscale", cxr_settings.lightmap_scale );
2811 cxr_vdf_ki32(output, "smoothing_groups", 0);
2812
2813 cxr_vdf_edon( output );
2814 }
2815
2816 cxr_vdf_node(output, "editor");
2817 cxr_vdf_colour255(output,"color", colours_random[cxr_range(cxr_context.brush_count,8)]);
2818 cxr_vdf_ki32(output,"visgroupshown",1);
2819 cxr_vdf_ki32(output,"visgroupautoshown",1);
2820 cxr_vdf_edon(output);
2821
2822 cxr_vdf_edon( output );
2823 }
2824
2825 for( int i=0; i<solids.count; i++ )
2826 {
2827 struct solidinf *solid = cxr_ab_ptr(&solids,i);
2828 cxr_free_mesh( solid->pmesh );
2829 }
2830
2831 cxr_ab_free( &abverts );
2832 cxr_ab_free( &solids );
2833 return 0;
2834 }
2835
2836
2837 CXR_API void cxr_set_log_function( void (*func)(const char *str) )
2838 {
2839 cxr_log_func = func;
2840 }
2841
2842 CXR_API void cxr_set_line_function( void (*func)(v3f p0, v3f p1, v4f colour) )
2843 {
2844 cxr_line_func = func;
2845 }
2846
2847 CXR_API void cxr_settings_update( struct cxr_settings *settings )
2848 {
2849 cxr_settings = *settings;
2850 }
2851
2852 // Valve copyright stuff probably maybe
2853 // whatever, my previous copyright decleration ends here
2854 // ----------------------------------------------------------
2855
2856 #define HEADER_LUMPS 64
2857 #define LUMP_WORLDLIGHTS 54
2858
2859 #pragma pack(push,1)
2860
2861 struct header
2862 {
2863 int ident;
2864 int version;
2865
2866 struct lump
2867 {
2868 int fileofs, filelen;
2869 int version;
2870
2871 char fourCC[4];
2872 }
2873 lumps[ HEADER_LUMPS ];
2874
2875 int mapRevision;
2876 };
2877
2878 struct worldlight
2879 {
2880 float origin[3];
2881 float intensity[3];
2882 float normal[3];
2883 float shadow_cast_offset[3];
2884 int cluster;
2885 int type;
2886 int style;
2887 float stopdot;
2888 float stopdot2;
2889 float exponent;
2890 float radius;
2891 float constant_attn;
2892 float linear_attn;
2893 float quadratic_attn;
2894 int flags;
2895 int texinfo;
2896 int owner;
2897 };
2898 #pragma pack(pop)
2899
2900 // Utility for patching BSP tools to remove -1 distance lights (we set them
2901 // like that, because we want these lights to go away)
2902 //
2903 // Yes, there is no way to do this in hammer
2904 // Yes, the distance KV is unused but still gets compiled to this lump
2905 // No, Entities only compile will not do this for you
2906 //
2907 CXR_API int cxr_lightpatch_bsp( const char *path )
2908 {
2909 printf( "Lightpatch: %s\n", path );
2910
2911 FILE *fp = fopen( path, "r+b" );
2912
2913 if( !fp )
2914 {
2915 cxr_log( "Could not open BSP file for editing (r+b)\n" );
2916 return 0;
2917 }
2918
2919 // Read bsp
2920 struct header header;
2921 fread( &header, sizeof(struct header), 1, fp );
2922 struct lump *lump = &header.lumps[ LUMP_WORLDLIGHTS ];
2923
2924 // Read worldlight array
2925 struct worldlight *lights = malloc( lump->filelen );
2926 fseek( fp, lump->fileofs, SEEK_SET );
2927 fread( lights, lump->filelen, 1, fp );
2928
2929 // Remove all marked lights
2930 int light_count = lump->filelen / sizeof(struct worldlight);
2931 int new_count = 0;
2932
2933 for( int i = 0; i < light_count; i ++ )
2934 if( lights[i].radius >= 0.0f )
2935 lights[new_count++] = lights[i];
2936
2937 lump->filelen = new_count*sizeof(struct worldlight);
2938
2939 // Write changes
2940 fseek( fp, lump->fileofs, SEEK_SET );
2941 fwrite( lights, lump->filelen, 1, fp );
2942 fseek( fp, 0, SEEK_SET );
2943 fwrite( &header, sizeof(struct header), 1, fp );
2944 cxr_log( "removed %d marked lights\n", light_count-new_count );
2945
2946 fclose( fp );
2947 free( lights );
2948
2949 return 1;
2950 }
Simple convex decomp library and source map exporter from blender.