[Bf-blender-cvs] [085a1e9f2f6] newboolean: Self Intersection working again with abstract IMesh.
Howard Trickey
noreply at git.blender.org
Tue Aug 27 14:23:32 CEST 2019
Commit: 085a1e9f2f614c010693e0e111a51c68649a0834
Author: Howard Trickey
Date: Mon Aug 26 21:09:40 2019 -0600
Branches: newboolean
https://developer.blender.org/rB085a1e9f2f614c010693e0e111a51c68649a0834
Self Intersection working again with abstract IMesh.
Still have to delete affected faces.
Still have to do intersections with non-coplanar parts.
===================================================================
M source/blender/bmesh/tools/bmesh_boolean.c
===================================================================
diff --git a/source/blender/bmesh/tools/bmesh_boolean.c b/source/blender/bmesh/tools/bmesh_boolean.c
index f48f5e9fa8c..a01b270a227 100644
--- a/source/blender/bmesh/tools/bmesh_boolean.c
+++ b/source/blender/bmesh/tools/bmesh_boolean.c
@@ -30,6 +30,7 @@
#include "MEM_guardedalloc.h"
#include "BLI_alloca.h"
+#include "BLI_array.h"
#include "BLI_delaunay_2d.h"
#include "BLI_linklist.h"
#include "BLI_math.h"
@@ -75,6 +76,8 @@ typedef struct IMesh {
*/
typedef struct MeshPart {
float plane[4]; /* first 3 are normal, 4th is signed distance to plane */
+ float bbmin[3]; /* bounding box min, with eps padding */
+ float bbmax[3]; /* bounding box max, with eps padding */
LinkNode *verts; /* links are ints (vert indices) */
LinkNode *edges; /* links are ints (edge indices) */
LinkNode *faces; /* links are ints (face indices) */
@@ -86,8 +89,11 @@ typedef struct MeshPart {
* TODO: faster structure for looking up by plane.
*/
typedef struct MeshPartSet {
+ float bbmin[3];
+ float bbmax[3];
LinkNode *meshparts; /* links are MeshParts* */
int tot_part;
+ const char *label; /* for debugging */
} MeshPartSet;
/* A set of integers, where each member gets an index
@@ -122,6 +128,12 @@ typedef struct IntPair {
int second;
} IntPair;
+typedef struct IntIntMapIterator {
+ const IntIntMap *map;
+ LinkNode *curlink;
+ IntPair *keyvalue;
+} IntIntMapIterator;
+
/* A result of intersectings parts of an implict IMesh.
* Designed so that can combine these in pairs, eventually ending up
* with a single IntersectOutput that can be turned into an edit on the
@@ -169,7 +181,7 @@ typedef struct BoolState {
} BoolState;
/* test_fn results used to distinguish parts of mesh */
-enum { TEST_B = -1, TEST_NONE = 0, TEST_A = 1, TEST_ALL = 2 };
+enum { TEST_NONE = -1, TEST_B = 0, TEST_A = 1, TEST_ALL = 2 };
#define BOOLDEBUG
#ifdef BOOLDEBUG
@@ -180,12 +192,19 @@ enum { TEST_B = -1, TEST_NONE = 0, TEST_A = 1, TEST_ALL = 2 };
# define F4(v) (v)[0], (v)[1], (v)[2], (v)[3]
# define BMI(e) BM_elem_index_get(e)
-static void dump_part(MeshPart *part, const char *label);
-static void dump_partset(MeshPartSet *pset, const char *label);
+static void dump_part(const MeshPart *part, const char *label);
+static void dump_partset(const MeshPartSet *pset);
+static void dump_isect_out(const IntersectOutput *io, const char *label);
+static void dump_intintmap(const IntIntMap *map, const char *label, const char *prefix);
#endif
+/* Forward declarations of some static functions. */
static CDT_result *copy_cdt_result(BoolState *bs, const CDT_result *res);
static int min_int_in_array(int *array, int len);
+static LinkNode *linklist_shallow_copy_arena(LinkNode *list, struct MemArena *arena);
+static void calc_part_bb_eps(BoolState *bs, MeshPart *part, float eps);
+static float *coordset_coord(const IndexedCoordSet *coordset, int index);
+static bool find_in_intintmap(const IntIntMap *map, int key, int *r_val);
/** IMesh functions. */
@@ -297,12 +316,143 @@ static int imesh_test_face(const IMesh *im, int (*test_fn)(void *, void *), void
}
}
+static void apply_isect_out_to_bmesh(BMesh *bm, const IntersectOutput *isect_out)
+{
+ int bm_tot_v, tot_new_v, tot_new_e, i, j, v1, v2, v1_out, v2_out;
+ int tot_new_f, fstart, flen, v, v_out;
+ BMVert **new_bmvs, *bmv, *bmv1, *bmv2;
+ BMFace *bmf;
+ float *co;
+ LinkNode *ln, *ln_map;
+ CDT_result *cdt;
+ IntIntMap *vmap;
+ BMVert **vv = NULL;
+ BLI_array_staticdeclare(vv, BM_DEFAULT_NGON_STACK_SIZE);
+
+ printf("\n\nAPPLY_ISECT_OUT_TO_BMESH\n\n");
+ /* Create the new BMVerts. */
+ bm_tot_v = bm->totvert;
+ tot_new_v = isect_out->new_verts.size;
+ if (tot_new_v > 0) {
+ new_bmvs = BLI_array_alloca(new_bmvs, tot_new_v);
+ for (i = 0; i < tot_new_v; i++) {
+ co = coordset_coord(&isect_out->new_verts, bm_tot_v + i);
+ /* TODO: use an example vert if there is one */
+ new_bmvs[i] = BM_vert_create(bm, co, NULL, 0);
+ printf("new_bmv[%d]=%p, at (%.3f,%.3f,%.3f)\n", i, new_bmvs[i], F3(co));
+ }
+ }
+
+ /* Adding verts has made the vertex table dirty.
+ * It is probably still ok, but just in case...
+ * TODO: find a way to avoid regenerating this table, maybe.
+ */
+ BM_mesh_elem_table_ensure(bm, BM_VERT);
+
+ /* Now create edges and faces from each cdt_output */
+ for (ln = isect_out->cdt_outputs.list, ln_map = isect_out->vertmaps.list; ln;
+ ln = ln->next, ln_map = ln_map->next) {
+ printf("\napply cdt output\n");
+ cdt = (CDT_result *)ln->link;
+ vmap = (IntIntMap *)ln_map->link;
+ tot_new_e = cdt->edges_len;
+ for (i = 0; i < tot_new_e; i++) {
+ v1 = cdt->edges[i][0];
+ v2 = cdt->edges[i][1];
+ if (!find_in_intintmap(vmap, v1, &v1_out)) {
+ printf("whoops, v1 map entry missing\n");
+ BLI_assert(false);
+ v1_out = v1;
+ }
+ if (!find_in_intintmap(vmap, v2, &v2_out)) {
+ printf("whoops, v2 map entry missing\n");
+ BLI_assert(false);
+ v2_out = v2;
+ }
+ printf("make edge %d %d\n", v1_out, v2_out);
+ if (v1_out < bm_tot_v) {
+
+ bmv1 = BM_vert_at_index(bm, v1_out);
+ }
+ else {
+ BLI_assert(v1_out - bm_tot_v < tot_new_v);
+ bmv1 = new_bmvs[v1_out - bm_tot_v];
+ }
+ if (v2_out < bm_tot_v) {
+ bmv2 = BM_vert_at_index(bm, v2_out);
+ }
+ else {
+ BLI_assert(v2_out - bm_tot_v < tot_new_v);
+ bmv2 = new_bmvs[v2_out - bm_tot_v];
+ }
+ /* TODO: use an example, if there is one. */
+ BM_edge_create(bm, bmv1, bmv2, NULL, BM_CREATE_NO_DOUBLE);
+ }
+ tot_new_f = cdt->faces_len;
+ for (i = 0; i < tot_new_f; i++) {
+ printf("make face ");
+ fstart = cdt->faces_start_table[i];
+ flen = cdt->faces_len_table[i];
+ BLI_array_clear(vv);
+ for (j = 0; j < flen; j++) {
+ v = cdt->faces[fstart + j];
+ if (!find_in_intintmap(vmap, v, &v_out)) {
+ printf("whoops, face v map entry missing\n");
+ BLI_assert(false);
+ v_out = v;
+ }
+ printf(" %d", v_out);
+ if (v_out < bm_tot_v) {
+ bmv = BM_vert_at_index(bm, v_out);
+ }
+ else {
+ BLI_assert(v_out - bm_tot_v < tot_new_v);
+ bmv = new_bmvs[v_out - bm_tot_v];
+ }
+ BLI_array_append(vv, bmv);
+ }
+ printf("\n");
+ /* TODO: use example */
+ bmf = BM_face_create_verts(bm, vv, flen, NULL, BM_CREATE_NOP, false);
+ }
+ }
+ BLI_array_free(vv);
+}
+
+static void apply_isect_out_to_imesh(IMesh *im, const IntersectOutput *isect_out)
+{
+ if (isect_out == NULL) {
+ return;
+ }
+ if (im->bm) {
+ apply_isect_out_to_bmesh(im->bm, isect_out);
+ }
+ else {
+ /* TODO */
+ }
+}
+
+static void bb_update(float bbmin[3], float bbmax[3], int v, const IMesh *im)
+{
+ int i;
+ float vco[3];
+
+ imesh_get_vert_co(im, v, vco);
+ for (i = 0; i < 3; i++) {
+ bbmin[i] = min_ff(vco[i], bbmin[i]);
+ bbmax[i] = max_ff(vco[i], bbmax[i]);
+ }
+}
+
/** MeshPartSet functions. */
-static void init_meshpartset(MeshPartSet *partset)
+static void init_meshpartset(MeshPartSet *partset, const char *label)
{
partset->meshparts = NULL;
partset->tot_part = 0;
+ zero_v3(partset->bbmin);
+ zero_v3(partset->bbmax);
+ partset->label = label;
}
static void add_part_to_partset(BoolState *bs, MeshPartSet *partset, MeshPart *part)
@@ -311,7 +461,7 @@ static void add_part_to_partset(BoolState *bs, MeshPartSet *partset, MeshPart *p
partset->tot_part++;
}
-static MeshPart *partset_part(MeshPartSet *partset, int index)
+static MeshPart *partset_part(const MeshPartSet *partset, int index)
{
LinkNode *ln = BLI_linklist_find(partset->meshparts, index);
if (ln) {
@@ -320,22 +470,70 @@ static MeshPart *partset_part(MeshPartSet *partset, int index)
return NULL;
}
+/* Fill in partset->bbmin and partset->bbmax with axis aligned bounding box
+ * for the partset.
+ * Also calculates bbmin and bbmax for each part.
+ * Add epsilon buffer on all sides.
+ */
+static void calc_partset_bb_eps(BoolState *bs, MeshPartSet *partset, float eps)
+{
+ LinkNode *ln;
+ MeshPart *part;
+ int i;
+
+ if (partset->meshparts == NULL) {
+ zero_v3(partset->bbmin);
+ zero_v3(partset->bbmax);
+ return;
+ }
+ copy_v3_fl(partset->bbmin, FLT_MAX);
+ copy_v3_fl(partset->bbmax, -FLT_MAX);
+ for (ln = partset->meshparts; ln; ln = ln->next) {
+ part = (MeshPart *)ln->link;
+ calc_part_bb_eps(bs, part, eps);
+ for (i = 0; i < 3; i++) {
+ partset->bbmin[i] = min_ff(partset->bbmin[i], part->bbmin[i]);
+ partset->bbmax[i] = max_ff(partset->bbmax[i], part->bbmax[i]);
+ }
+ }
+ /* eps padding was already added in calc_part_bb_eps. */
+}
+
/** MeshPart functions. */
static void init_meshpart(MeshPart *part)
{
zero_v4(part->plane);
+ zero_v3(part->bbmin);
+ zero_v3(part->bbmax);
part->verts = NULL;
part->edges = NULL;
part->faces = NULL;
}
-static int part_totface(MeshPart *part)
+static MeshPart *copy_part(BoolState *bs, const MeshPart *part)
+{
+ MeshPart *copy;
+ MemArena *arena = bs->mem_arena;
+
+ copy = BLI_memarena_alloc(bs->mem_arena, sizeof(*copy));
+ copy_v4_v4(copy->plane, part->plane);
+ copy_v3_v3(copy->bbmin, part->bbmin);
+ copy_v3_v3(copy->bbmax, part->bbmax);
+
+ /* All links in lists are ints, so can use shallow copy. */
+ copy->verts = linklist_shallow_copy_arena(part->verts, arena);
+ copy->edges = linklist_shallow_copy_arena(part->edges, arena);
+ copy->faces = linklist_shallow_copy_arena(part->faces, arena);
+ return copy;
+}
+
+static int part_totface(const MeshPart *part)
{
return BLI_linklist_count(part->faces);
}
-static int part_face(MeshPart *part, int index)
+static int part_face(const MeshPart *part, int index)
{
LinkNode *ln = BLI_linklist_find(part->faces, index);
if (ln) {
@@ -344,9 +542,54 @@ static int part_face(MeshPart *part, int index)
return -1;
}
-static bool parts_may_intersect(MeshPart *part1, MeshPart *part2)
+/* Fill part->bbmin and part->bbmax with the axis-aligned bounding box
+ * for the part.
+ * Add an epsilon buffer on all sides.
+ */
+static void cal
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list