git.mutantstargoat.com Git - meshfrac/blob - src/frac.c

   1 #include <stdlib.h>
   2 #include <string.h>
   3 #include <assert.h>
   4 #include "frac.h"
   5 #include "dynarr.h"
   6
   7 static void destroy_cell(struct frac_cell *cell);
   8 static int build_cell(struct fracture *frac, int cellidx);
   9
  10 int frac_init(struct fracture *frac)
  11 {
  12         frac->mesh = 0;
  13
  14         if(!(frac->cells = dynarr_alloc(0, sizeof *frac->cells))) {
  15                 return -1;
  16         }
  17         return 0;
  18 }
  19
  20 void frac_destroy(struct fracture *frac)
  21 {
  22         int i, num;
  23
  24         if(!frac) return;
  25
  26         if(frac->cells) {
  27                 num = dynarr_size(frac->cells);
  28                 for(i=0; i<num; i++) {
  29                         destroy_cell(frac->cells + i);
  30                 }
  31                 dynarr_free(frac->cells);
  32         }
  33 }
  34
  35 static int init_cell(struct frac_cell *cell)
  36 {
  37         memset(cell, 0, sizeof *cell);
  38         if(!(cell->mesh = cmesh_alloc())) {
  39                 return -1;
  40         }
  41         return 0;
  42 }
  43
  44 static void destroy_cell(struct frac_cell *cell)
  45 {
  46         if(!cell) return;
  47         free(cell->polys);
  48         cmesh_free(cell->mesh);
  49 }
  50
  51 void frac_mesh(struct fracture *frac, const struct cmesh *m)
  52 {
  53         frac->mesh = (struct cmesh*)m;
  54 }
  55
  56 int frac_point(struct fracture *frac, float x, float y, float z)
  57 {
  58         struct frac_cell cell;
  59         struct frac_cell *tmp;
  60
  61         init_cell(&cell);
  62         cgm_vcons(&cell.pt, x, y, z);
  63         if(!(tmp = dynarr_push(frac->cells, &cell))) {
  64                 destroy_cell(&cell);
  65                 return -1;
  66         }
  67         frac->cells = tmp;
  68         return 0;
  69 }
  70
  71 int frac_num_cells(struct fracture *frac)
  72 {
  73         return dynarr_size(frac->cells);
  74 }
  75
  76 /* --- step 1: generate a bunch of points (or let the user add them manually) */
  77
  78 int frac_gen_points(struct fracture *frac, int num)
  79 {
  80         int i;
  81         float x, y, z;
  82         cgm_vec3 bbmin, bbmax, delta;
  83
  84         if(!frac || !frac->mesh) return -1;
  85         if(!cmesh_poly_count(frac->mesh)) {
  86                 return -1;
  87         }
  88
  89         cmesh_aabbox(frac->mesh, &bbmin, &bbmax);
  90         delta = bbmax;
  91         cgm_vsub(&delta, &bbmin);
  92
  93         for(i=0; i<num; i++) {
  94                 x = (float)rand() / RAND_MAX * delta.x + bbmin.x;
  95                 y = (float)rand() / RAND_MAX * delta.y + bbmin.y;
  96                 z = (float)rand() / RAND_MAX * delta.z + bbmin.z;
  97
  98                 if(frac_point(frac, x, y, z) == -1) {
  99                         return -1;
 100                 }
 101         }
 102         return 0;
 103 }
 104
 105
 106 /* --- step 2: construct voronoi cells bounded by planes */
 107
 108 int frac_build_cells(struct fracture *frac)
 109 {
 110         int i;
 111
 112         for(i=0; i<dynarr_size(frac->cells); i++) {
 113                 if(build_cell(frac, i) == -1) {
 114                         return -1;
 115                 }
 116         }
 117
 118         return 0;
 119 }
 120
 121 static int build_cell(struct fracture *frac, int cellidx)
 122 {
 123         int i, j, num, clipres;
 124         int *valid_planes;
 125         struct plane plane;
 126         struct frac_cell *cell = frac->cells + cellidx;
 127         struct poly poly, clipped, *polys, *pptr;
 128         float bsize;
 129
 130         if(!(polys = dynarr_alloc(0, sizeof *polys))) {
 131                 return -1;
 132         }
 133
 134         cmesh_bsphere(frac->mesh, 0, &bsize);
 135         bsize *= 2;
 136
 137         num = dynarr_size(frac->cells);
 138         for(i=0; i<num; i++) {
 139                 if(i == cellidx) continue;
 140                 midplane(&plane, &cell->pt, &frac->cells[i].pt);
 141                 plane_poly(&plane, &poly, bsize);
 142                 if(!(pptr = dynarr_push(polys, &poly))) {
 143                         return -1;
 144                 }
 145                 polys = pptr;
 146         }
 147
 148         num = dynarr_size(polys);
 149         valid_planes = alloca(num * sizeof *valid_planes);
 150         memset(valid_planes, 0xff, num * sizeof *valid_planes);
 151
 152         /* clip all planes against each other to end up with a convex cell */
 153         cell->num_polys = num;
 154         for(i=0; i<num; i++) {
 155                 for(j=0; j<num; j++) {
 156                         if(i == j || !valid_planes[j]) {
 157                                 continue;
 158                         }
 159
 160                         /* clip plane polygon i with plane j */
 161                         poly_plane(polys + j, &plane);
 162                         init_poly(&clipped);
 163                         if((clipres = clip_poly(&clipped, polys + i, &plane)) < 0) {
 164                                 /* completely clipped, mark it for removal */
 165                                 valid_planes[i] = 0;
 166                                 cell->num_polys--;
 167                                 destroy_poly(&clipped);
 168                                 break;
 169                         }
 170                         destroy_poly(polys + i);
 171                         polys[i] = clipped;
 172                 }
 173         }
 174
 175         if(!(cell->polys = malloc(cell->num_polys * sizeof *cell->polys))) {
 176                 return -1;
 177         }
 178         pptr = cell->polys;
 179         for(i=0; i<num; i++) {
 180                 if(valid_planes[i]) {
 181                         assert(pptr - cell->polys < cell->num_polys);
 182                         *pptr++ = polys[i];
 183                 } else {
 184                         destroy_poly(polys + i);
 185                 }
 186         }
 187         dynarr_free(polys);
 188         return 0;
 189 }
 190
 191 static int mesh_poly(struct poly *poly, const struct cmesh *mesh, int faceidx)
 192 {
 193         int i, vsz, nsz, uvsz;
 194         struct vertex vert, *tmpvert;
 195         const float *varr, *narr, *uvarr;
 196         unsigned int vidx;
 197
 198         if(init_poly(poly) == -1) {
 199                 return -1;
 200         }
 201
 202         varr = cmesh_attrib_ro(mesh, CMESH_ATTR_VERTEX);
 203         narr = cmesh_attrib_ro(mesh, CMESH_ATTR_NORMAL);
 204         uvarr = cmesh_attrib_ro(mesh, CMESH_ATTR_TEXCOORD);
 205         vsz = cmesh_attrib_nelem(mesh, CMESH_ATTR_VERTEX);
 206         nsz = cmesh_attrib_nelem(mesh, CMESH_ATTR_NORMAL);
 207         uvsz = cmesh_attrib_nelem(mesh, CMESH_ATTR_TEXCOORD);
 208
 209         for(i=0; i<3; i++) {
 210                 if(cmesh_indexed(mesh)) {
 211                         vidx = cmesh_index_ro(mesh)[faceidx * 3 + i];
 212                 } else {
 213                         vidx = faceidx * 3 + i;
 214                 }
 215                 vert.pos.x = varr[vidx * vsz];
 216                 vert.pos.y = varr[vidx * vsz + 1];
 217                 vert.pos.z = varr[vidx * vsz + 2];
 218                 vert.norm.x = narr[vidx * nsz];
 219                 vert.norm.y = narr[vidx * nsz + 1];
 220                 vert.norm.z = narr[vidx * nsz + 2];
 221                 vert.uv.x = uvarr[vidx * uvsz];
 222                 vert.uv.y = uvarr[vidx * uvsz + 1];
 223
 224                 if(!(tmpvert = dynarr_push(poly->verts, &vert))) {
 225                         destroy_poly(poly);
 226                         return -1;
 227                 }
 228                 poly->verts = tmpvert;
 229         }
 230         return 0;
 231 }
 232
 233 #define ADD_VERTEX(mesh, vert) \
 234         do { \
 235                 cmesh_normal(mesh, (vert)->norm.x, (vert)->norm.y, (vert)->norm.z); \
 236                 cmesh_texcoord(mesh, (vert)->uv.x, (vert)->uv.y, 0); \
 237                 if(cmesh_vertex(mesh, (vert)->pos.x, (vert)->pos.y, (vert)->pos.z) == -1) { \
 238                         fprintf(stderr, "SKATA\n"); \
 239                         abort(); \
 240                 } \
 241         } while(0)
 242
 243 static int build_cell_shell(struct cmesh *mesh, const struct cmesh *orig,
 244                 struct frac_cell *cell)
 245 {
 246         int i, j, nfaces, clipres;
 247         struct plane plane;
 248         struct poly poly, clipped, wallclipped;
 249         struct vertex *vert;
 250         int *delwall;
 251         struct plane *cplanes;
 252
 253         /* array for marking wall polygons for deletion when they get clipped entirely */
 254         delwall = alloca(cell->num_polys * sizeof *delwall);
 255         memset(delwall, 0, cell->num_polys * sizeof *delwall);
 256
 257         /* array for pre-constructing the voronoi clipping planes */
 258         cplanes = alloca(cell->num_polys * sizeof *cplanes);
 259         for(i=0; i<cell->num_polys; i++) {
 260                 poly_plane(cell->polys + i, cplanes + i);
 261         }
 262
 263         nfaces = cmesh_poly_count(orig);
 264         for(i=0; i<nfaces; i++) {
 265                 if(mesh_poly(&poly, orig, i) == -1) {
 266                         cmesh_destroy(mesh);
 267                         return -1;
 268                 }
 269
 270                 for(j=0; j<cell->num_polys; j++) {
 271                         init_poly(&clipped);
 272                         if((clipres = clip_poly(&clipped, &poly, cplanes + j)) < 0) {
 273                                 destroy_poly(&clipped);
 274                                 break;
 275                         }
 276
 277                         /* if the plane clipped the polygon, and the two polygons intersect
 278                          * within their bounds, also clip the cell polygon by the original
 279                          * mesh polygon.
 280                          *
 281                          * TODO clipping with the polygon's plane is incorrect, and will lead
 282                          * to gaps in the cell walls when the surface is concave. We'll need
 283                          * to clip by the polygon itself, which can make the wall polygon
 284                          * concave, and will need to be split into multiple convex ones.
 285                          */
 286                         if(clipres == 0 && poly_poly(&poly, cell->polys + j)) {
 287                                 poly_plane(&poly, &plane);
 288                                 init_poly(&wallclipped);
 289
 290                                 if((clipres = clip_poly(&wallclipped, cell->polys + j, &plane)) < 0) {
 291                                         /* mark for deletion */
 292                                         delwall[j] = 1;
 293                                 } else if(clipres == 0) {
 294                                         destroy_poly(cell->polys + j);
 295                                         cell->polys[j] = wallclipped;
 296                                 } else {
 297                                         destroy_poly(&wallclipped);
 298                                 }
 299                         }
 300
 301                         destroy_poly(&poly);
 302                         poly = clipped;
 303                 }
 304
 305                 if(j < cell->num_polys) {
 306                         continue;
 307                 }
 308
 309                 vert = poly.verts + 1;
 310                 for(j=0; j<dynarr_size(poly.verts)-2; j++) {
 311                         ADD_VERTEX(mesh, poly.verts);
 312                         ADD_VERTEX(mesh, vert); vert++;
 313                         ADD_VERTEX(mesh, vert);
 314                 }
 315                 destroy_poly(&poly);
 316         }
 317
 318         /* remove deleted wall polygons */
 319         for(i=0; i<cell->num_polys; i++) {
 320                 if(delwall[i]) {
 321                         struct poly tmp = cell->polys[i];
 322                         cell->polys[i] = cell->polys[--cell->num_polys];
 323                         destroy_poly(&tmp);
 324                 }
 325         }
 326
 327         /* add wall polygons to the mesh */
 328         for(i=0; i<cell->num_polys; i++) {
 329                 vert = cell->polys[i].verts + 1;
 330                 for(j=0; j<dynarr_size(cell->polys[i].verts)-2; j++) {
 331                         ADD_VERTEX(mesh, cell->polys[i].verts);
 332                         ADD_VERTEX(mesh, vert); vert++;
 333                         ADD_VERTEX(mesh, vert);
 334                 }
 335         }
 336
 337         return 0;
 338 }
 339
 340 int frac_build_shell(struct fracture *frac)
 341 {
 342         int i, num_cells;
 343
 344         num_cells = dynarr_size(frac->cells);
 345         for(i=0; i<num_cells; i++) {
 346                 if(build_cell_shell(frac->cells[i].mesh, frac->mesh, frac->cells + i) == -1) {
 347                         return -1;
 348                 }
 349         }
 350
 351         return 0;
 352 }
 353
 354 int frac_build_walls(struct fracture *frac)
 355 {
 356         return -1;
 357 }
 358
 359 int frac_build(struct fracture *frac)
 360 {
 361         if(frac_build_cells(frac) == -1) {
 362                 return -1;
 363         }
 364         if(frac_build_shell(frac) == -1) {
 365                 return -1;
 366         }
 367         if(frac_build_walls(frac) == -1) {
 368                 return -1;
 369         }
 370         return 0;
 371 }