almost there...

diff --git a/src/frac.c b/src/frac.c
index 048b8a0..a6ce0a8 100644 (file)
--- a/src/frac.c
+++ b/src/frac.c
@@ -241,12 +241,24 @@ static int mesh_poly(struct poly *poly, const struct cmesh *mesh, int faceidx)
        } while(0)
 
 static int build_cell_shell(struct cmesh *mesh, const struct cmesh *orig,
-               const struct frac_cell *cell)
+               struct frac_cell *cell)
 {
-       int i, j, k, nfaces, clipres;
+       int i, j, nfaces, clipres;
        struct plane plane;
-       struct poly poly, clipped;
+       struct poly poly, clipped, wallclipped;
        struct vertex *vert;
+       int *delwall;
+       struct plane *cplanes;
+
+       /* array for marking wall polygons for deletion when they get clipped entirely */
+       delwall = alloca(cell->num_polys * sizeof *delwall);
+       memset(delwall, 0, cell->num_polys * sizeof *delwall);
+
+       /* array for pre-constructing the voronoi clipping planes */
+       cplanes = alloca(cell->num_polys * sizeof *cplanes);
+       for(i=0; i<cell->num_polys; i++) {
+               poly_plane(cell->polys + i, cplanes + i);
+       }
 
        nfaces = cmesh_poly_count(orig);
        for(i=0; i<nfaces; i++) {
@@ -256,13 +268,36 @@ static int build_cell_shell(struct cmesh *mesh, const struct cmesh *orig,
                }
 
                for(j=0; j<cell->num_polys; j++) {
-                       poly_plane(cell->polys + j, &plane);
-
                        init_poly(&clipped);
-                       if((clipres = clip_poly(&clipped, &poly, &plane)) < 0) {
+                       if((clipres = clip_poly(&clipped, &poly, cplanes + j)) < 0) {
                                destroy_poly(&clipped);
                                break;
                        }
+
+                       /* if the plane clipped the polygon, and the two polygons intersect
+                        * within their bounds, also clip the cell polygon by the original
+                        * mesh polygon.
+                        *
+                        * TODO clipping with the polygon's plane is incorrect, and will lead
+                        * to gaps in the cell walls when the surface is concave. We'll need
+                        * to clip by the polygon itself, which can make the wall polygon
+                        * concave, and will need to be split into multiple convex ones.
+                        */
+                       if(clipres == 0 && poly_poly(&poly, cell->polys + j)) {
+                               poly_plane(&poly, &plane);
+                               init_poly(&wallclipped);
+
+                               if((clipres = clip_poly(&wallclipped, cell->polys + j, &plane)) < 0) {
+                                       /* mark for deletion */
+                                       delwall[j] = 1;
+                               } else if(clipres == 0) {
+                                       destroy_poly(cell->polys + j);
+                                       cell->polys[j] = wallclipped;
+                               } else {
+                                       destroy_poly(&wallclipped);
+                               }
+                       }
+
                        destroy_poly(&poly);
                        poly = clipped;
                }
@@ -272,13 +307,33 @@ static int build_cell_shell(struct cmesh *mesh, const struct cmesh *orig,
                }
 
                vert = poly.verts + 1;
-               for(k=0; k<dynarr_size(poly.verts)-2; k++) {
+               for(j=0; j<dynarr_size(poly.verts)-2; j++) {
                        ADD_VERTEX(mesh, poly.verts);
                        ADD_VERTEX(mesh, vert); vert++;
                        ADD_VERTEX(mesh, vert);
                }
                destroy_poly(&poly);
        }
+
+       /* remove deleted wall polygons */
+       for(i=0; i<cell->num_polys; i++) {
+               if(delwall[i]) {
+                       struct poly tmp = cell->polys[i];
+                       cell->polys[i] = cell->polys[--cell->num_polys];
+                       destroy_poly(&tmp);
+               }
+       }
+
+       /* add wall polygons to the mesh */
+       for(i=0; i<cell->num_polys; i++) {
+               vert = cell->polys[i].verts + 1;
+               for(j=0; j<dynarr_size(cell->polys[i].verts)-2; j++) {
+                       ADD_VERTEX(mesh, cell->polys[i].verts);
+                       ADD_VERTEX(mesh, vert); vert++;
+                       ADD_VERTEX(mesh, vert);
+               }
+       }
+
        return 0;
 }
 

diff --git a/src/geom.c b/src/geom.c
index 67c3c31..25c4d0a 100644 (file)
--- a/src/geom.c
+++ b/src/geom.c
@@ -223,3 +223,35 @@ int clip_poly(struct poly *pout, const struct poly *pin, const struct plane *pla
        return edges_clipped > 0 ? 0 : 1;
 
 }
+
+int poly_poly(const struct poly *p1, const struct poly *p2)
+{
+       int i, vnum1, vnum2;
+       float t;
+       cgm_ray ray;
+
+       vnum1 = dynarr_size(p1->verts);
+       vnum2 = dynarr_size(p2->verts);
+
+       for(i=0; i<vnum1; i++) {
+               ray.origin = p1->verts[i].pos;
+               ray.dir = p1->verts[(i + 1) & vnum1].pos;
+               cgm_vsub(&ray.dir, &ray.origin);
+
+               if((t = ray_poly(&ray, p2)) >= 0.0f && t <= 1.0f) {
+                       return 1;
+               }
+       }
+
+       for(i=0; i<vnum2; i++) {
+               ray.origin = p2->verts[i].pos;
+               ray.dir = p2->verts[(i + 1) & vnum2].pos;
+               cgm_vsub(&ray.dir, &ray.origin);
+
+               if((t = ray_poly(&ray, p1)) >= 0.0f && t <= 1.0f) {
+                       return 1;
+               }
+       }
+
+       return 0;
+}

diff --git a/src/geom.h b/src/geom.h
index 19c10ff..a66d163 100644 (file)
--- a/src/geom.h
+++ b/src/geom.h
@@ -31,4 +31,6 @@ int init_poly(struct poly *p);
 void destroy_poly(struct poly *p);
 int clip_poly(struct poly *pout, const struct poly *pin, const struct plane *plane);
 
+int poly_poly(const struct poly *p1, const struct poly *p2);
+
 #endif /* GEOM_H_ */