+ if((pidx = choose_poly(polyarr, num_polys)) == -1) {
+ return 0;
+ }
+ sp = polyarr + pidx;
+
+ negplane.x = sp->plane.x;
+ negplane.y = sp->plane.y;
+ negplane.z = sp->plane.z;
+ negplane.nx = -sp->plane.nx;
+ negplane.ny = -sp->plane.ny;
+ negplane.nz = -sp->plane.nz;
+
+ if(!(front_polys = dynarr_alloc(0, sizeof *front_polys)) ||
+ !(back_polys = dynarr_alloc(0, sizeof *back_polys))) {
+ fprintf(stderr, "build_tree: failed to allocate front/back polygon arrays\n");
+ dynarr_free(front_polys);
+ return 0;
+ }
+
+ for(i=0; i<num_polys; i++) {
+ if(i == pidx) continue;
+
+ vnum = polyarr[i].vcount;
+
+ if(vnum * 2 > max_clipped_vnum) {
+ /* resize clipped polygon buffers if necessary */
+ max_clipped_vnum = vnum * 2;
+ if(!(v = realloc(clipped, max_clipped_vnum * sizeof *clipped))) {
+ fprintf(stderr, "build_tree: failed to reallocate clipped polygon buffer\n");
+ goto fail;
+ }
+ clipped = v;
+ if(!(v = realloc(clipped_neg, max_clipped_vnum * sizeof *clipped))) {
+ fprintf(stderr, "build_tree: failed to reallocate clipped polygon buffer\n");
+ goto fail;
+ }
+ clipped_neg = v;
+ }
+
+ v = polyarr[i].verts;
+
+ clipres = clip_poly(clipped, &clipped_vnum, v, vnum, &sp->plane);
+ clipres_neg = clip_poly(clipped_neg, &clipped_neg_vnum, v, vnum, &negplane);
+
+ /* detect edge cases where due to floating point imprecision, clipping
+ * by the positive plane clips the polygon, but clipping by the negative
+ * plane doesn't. If that happens, consider the polygon completely on
+ * the side indicated by -clipres_neg
+ */
+ if(clipres == 0 && clipres_neg != 0) {
+ clipres = -clipres_neg;
+ }
+
+ if(clipres > 0) {
+ /* polygon completely in the positive subspace */
+ if(!(tmp = dynarr_push(front_polys, polyarr + i))) {
+ fprintf(stderr, "build_tree: failed to reallocate polygon array\n");
+ goto fail;
+ }
+ front_polys = tmp;
+
+ } else if(clipres < 0) {
+ /* polygon completely in the negative subspace */
+ if(!(tmp = dynarr_push(back_polys, polyarr + i))) {
+ fprintf(stderr, "build_tree: failed to reallocate polygon array\n");
+ goto fail;
+ }
+ back_polys = tmp;
+
+ } else {
+ /* polygon is straddling the plane */
+ struct bsppoly poly;
+ poly.plane = polyarr[i].plane;
+
+ if(init_poly_noplane(&poly, clipped, clipped_vnum) == -1) {
+ goto fail;
+ }
+ if(!(tmp = dynarr_push(front_polys, &poly))) {
+ fprintf(stderr, "build_tree: failed to reallocate polygon array\n");
+ free(poly.verts);
+ goto fail;
+ }
+ front_polys = tmp;
+
+ if(init_poly_noplane(&poly, clipped_neg, clipped_neg_vnum) == -1) {
+ goto fail;
+ }
+ if(!(tmp = dynarr_push(back_polys, &poly))) {
+ fprintf(stderr, "build_tree: failed to reallocate polygon array\n");
+ free(poly.verts);
+ goto fail;
+ }
+ back_polys = tmp;
+
+ /* we allocated new sub-polygons, so we need to free the original vertex array */
+ free(polyarr[i].verts);
+ }