From: John Tsiombikas <nuclear@member.fsf.org>
Date: Wed, 8 Feb 2023 20:22:29 +0000 (+0200)
Subject: almost there...
X-Git-Url: http://git.mutantstargoat.com/user/nuclear/?p=meshfrac;a=commitdiff_plain;h=f1410762198ad4b0ca8c0b47bd484ff2d3e09ddd

almost there...
---

diff --git a/src/frac.c b/src/frac.c
index 048b8a0..a6ce0a8 100644
--- 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
--- 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
--- 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_ */