[Bf-blender-cvs] [9c4b18597d2] newboolean: Most regression tests now pass.
Howard Trickey
noreply at git.blender.org
Mon Dec 2 15:05:32 CET 2019
Commit: 9c4b18597d25c6cf69fce026ce3309f8a088e951
Author: Howard Trickey
Date: Mon Oct 28 07:47:51 2019 -0400
Branches: newboolean
https://developer.blender.org/rB9c4b18597d25c6cf69fce026ce3309f8a088e951
Most regression tests now pass.
Put in option checkbox in UI so can choose old or new method.
===================================================================
M source/blender/bmesh/tools/bmesh_boolean.c
M source/blender/editors/mesh/editmesh_intersect.c
===================================================================
diff --git a/source/blender/bmesh/tools/bmesh_boolean.c b/source/blender/bmesh/tools/bmesh_boolean.c
index c494305d0f4..0f79b3a76d6 100644
--- a/source/blender/bmesh/tools/bmesh_boolean.c
+++ b/source/blender/bmesh/tools/bmesh_boolean.c
@@ -51,6 +51,15 @@
* faster-lookup versions (hash tables, kd-trees, bvh structures) and will parallelize.
*/
+/* A set of integers. TODO: faster structure. */
+typedef struct IntSet {
+ LinkNode *list;
+} IntSet;
+
+typedef struct IntSetIterator {
+ LinkNode *cur;
+} IntSetIterator;
+
/* A set of integers, where each member gets an index
* that can be used to access the member.
* TODO: faster structure for lookup.
@@ -146,6 +155,19 @@ typedef struct MeshDelete {
int totface;
} MeshDelete;
+/* MeshChange holds all of the information needed to transform
+ * an IMesh into the desired result: vertex merges, adds, deletes,
+ * and which edges are to be tagged to mark intersection edges.
+ */
+typedef struct MeshChange {
+ MeshAdd add;
+ MeshDelete delete;
+ IntIntMap vert_merge_map;
+ IntSet intersection_edges;
+ IntSet face_flip;
+ bool use_face_kill_loose;
+} MeshChange;
+
/* A MeshPart is a subset of the geometry of an IndexMesh,
* with some possible additional geometry.
* The indices refer to vertex, edges, and faces in the IndexMesh
@@ -237,8 +259,11 @@ ATTU static void dump_partpartintersect(const PartPartIntersect *ppi, const char
ATTU static void dump_meshadd(const MeshAdd *ma, const char *label);
ATTU static void dump_meshdelete(const MeshDelete *meshdelete, const char *label);
ATTU static void dump_intintmap(const IntIntMap *map, const char *label, const char *prefix);
+ATTU static void dump_intset(const IntSet *set, const char *label, const char *prefix);
+ATTU static void dump_meshchange(const MeshChange *change, const char *label);
ATTU static void dump_cdt_input(const CDT_input *cdt, const char *label);
ATTU static void dump_cdt_result(const CDT_result *cdt, const char *label, const char *prefix);
+ATTU static void dump_bm(struct BMesh *bm, const char *msg);
#endif
/* Forward declarations of some static functions. */
@@ -253,6 +278,7 @@ static NewVert *meshadd_get_newvert(const MeshAdd *meshadd, int v);
static NewEdge *meshadd_get_newedge(const MeshAdd *meshadd, int e);
static NewFace *meshadd_get_newface(const MeshAdd *meshadd, int f);
static int meshadd_facelen(const MeshAdd *meshadd, int f);
+static void meshadd_get_face_no(const MeshAdd *meshadd, int f, double *r_no);
static int meshadd_face_vert(const MeshAdd *meshadd, int f, int index);
static void meshadd_get_vert_co(const MeshAdd *meshadd, int v, float *r_coords);
static void meshadd_get_edge_verts(const MeshAdd *meshadd, int e, int *r_v1, int *r_v2);
@@ -261,16 +287,64 @@ static bool meshdelete_find_edge(MeshDelete *meshdelete, int e);
static bool meshdelete_find_face(MeshDelete *meshdelete, int f);
static int find_edge_by_verts_in_meshadd(const MeshAdd *meshadd, int v1, int v2);
+/** Intset functions */
+
+static void init_intset(IntSet *inset)
+{
+ inset->list = NULL;
+}
+
+static bool find_in_intset(const IntSet *set, int value)
+{
+ LinkNode *ln;
+
+ for (ln = set->list; ln; ln = ln->next) {
+ if (POINTER_AS_INT(ln->link) == value) {
+ return true;
+ }
+ }
+ return false;
+}
+
+static void add_to_intset(BoolState *bs, IntSet *set, int value)
+{
+ if (!find_in_intset(set, value)) {
+ BLI_linklist_prepend_arena(&set->list, POINTER_FROM_INT(value), bs->mem_arena);
+ }
+}
+
+/** IntSetIterator functions. */
+
+static void intset_iter_init(IntSetIterator *iter, const IntSet *set)
+{
+ iter->cur = set->list;
+}
+
+static bool intset_iter_done(IntSetIterator *iter)
+{
+ return iter->cur == NULL;
+}
+
+static void intset_iter_step(IntSetIterator *iter)
+{
+ iter->cur = iter->cur->next;
+}
+
+static int intset_iter_value(IntSetIterator *iter)
+{
+ return POINTER_AS_INT(iter->cur->link);
+}
+
/** IndexedIntSet functions. */
-static void init_intset(IndexedIntSet *intset)
+static void init_indexedintset(IndexedIntSet *intset)
{
intset->listhead.list = NULL;
intset->listhead.last_node = NULL;
intset->size = 0;
}
-static int add_int_to_intset(BoolState *bs, IndexedIntSet *intset, int value)
+static int add_int_to_indexedintset(BoolState *bs, IndexedIntSet *intset, int value)
{
int index;
@@ -283,7 +357,7 @@ static int add_int_to_intset(BoolState *bs, IndexedIntSet *intset, int value)
return index;
}
-static bool find_in_intset(const IndexedIntSet *intset, int value)
+static bool find_in_indexedintset(const IndexedIntSet *intset, int value)
{
LinkNode *ln;
@@ -295,7 +369,7 @@ static bool find_in_intset(const IndexedIntSet *intset, int value)
return false;
}
-static int intset_get_value_by_index(const IndexedIntSet *intset, int index)
+static int indexedintset_get_value_by_index(const IndexedIntSet *intset, int index)
{
LinkNode *ln;
int i;
@@ -312,7 +386,7 @@ static int intset_get_value_by_index(const IndexedIntSet *intset, int index)
return POINTER_AS_INT(ln->link);
}
-static int intset_get_index_for_value(const IndexedIntSet *intset, int value)
+static int indexedintset_get_index_for_value(const IndexedIntSet *intset, int value)
{
return BLI_linklist_index(intset->listhead.list, POINTER_FROM_INT(value));
}
@@ -833,6 +907,17 @@ static int imesh_facelen(const IMesh *im, int f)
return ans;
}
+static void imesh_get_face_no(const IMesh *im, int f, double *r_no)
+{
+ if (im->bm) {
+ BMFace *bmf = BM_face_at_index(im->bm, f);
+ copy_v3db_v3fl(r_no, bmf->no);
+ }
+ else {
+ ; /* TODO */
+ }
+}
+
static int imesh_face_vert(const IMesh *im, int f, int index)
{
int i;
@@ -995,6 +1080,57 @@ static void imesh_get_face_plane(const IMesh *im, int f, double r_plane[4])
}
}
+static void imesh_calc_point_in_face(IMesh *im, int f, double co[3])
+{
+ if (im->bm) {
+ float fco[3];
+ BMFace *bmf = BM_face_at_index(im->bm, f);
+ BM_face_calc_point_in_face(bmf, fco);
+ copy_v3db_v3fl(co, fco);
+ }
+ else {
+ ; /* TODO */
+ }
+}
+
+/* Return a tesselation of f into triangles.
+ * There will always be flen - 2 triangles where f is f's face length.
+ * Caller must supply array of size (flen - 2) * 3 ints.
+ * Return will be triples of indices of the vertices around f.
+ */
+static void imesh_face_calc_tesselation(IMesh *im, int f, int (*r_index)[3])
+{
+ if (im->bm) {
+ BMFace *bmf = BM_face_at_index(im->bm, f);
+ BMLoop **loops = BLI_array_alloca(loops, bmf->len);
+ /* OK to use argument use_fixed_quad == true: don't need convex quads. */
+ BM_face_calc_tessellation(bmf, true, loops, (uint (*)[3])r_index);
+ /* Need orientation of triangles to match that of face. Because of using
+ * use_fix_quads == true, we know that we only might have a problem here
+ * for polygons with more than 4 sides. */
+ if (bmf->len > 4) {
+ float tri0_no[3];
+ BMVert *v0, *v1, *v2;
+ v0 = loops[r_index[0][0]]->v;
+ v1 = loops[r_index[0][1]]->v;
+ v2 = loops[r_index[0][2]]->v;
+ normal_tri_v3(tri0_no, v0->co, v1->co, v2->co);
+ if (dot_v3v3(tri0_no, bmf->no) < 0.0f) {
+ /* Need to reverse winding order for all triangles in tesselation. */
+ int i, tmp;
+ for (i = 0; i < bmf->len - 2; i++) {
+ tmp = r_index[i][1];
+ r_index[i][1] = r_index[i][2];
+ r_index[i][2] = tmp;
+ }
+ }
+ }
+ }
+ else {
+ ; /* TODO */
+ }
+}
+
static int imesh_test_face(const IMesh *im, int (*test_fn)(void *, void *), void *user_data, int f)
{
if (im->bm) {
@@ -1021,10 +1157,7 @@ static int resolve_merge(int v, const IntIntMap *vert_merge_map)
return vmapped;
}
-static void apply_meshadd_to_bmesh(BMesh *bm,
- const MeshAdd *meshadd,
- MeshDelete *meshdelete,
- const IntIntMap *vert_merge_map)
+static void apply_meshchange_to_bmesh(BMesh *bm, MeshChange *change)
{
int bm_tot_v, bm_tot_e, bm_tot_f, tot_new_v, tot_new_e, tot_new_f;
int i, v, e, f, v1, v2;
@@ -1037,8 +1170,13 @@ static void apply_meshadd_to_bmesh(BMesh *bm,
BMEdge **new_bmes, **face_bmes;
BMEdge *bme, *bme_eg;
BMFace *bmf, *bmf_eg;
+ MeshAdd *meshadd = &change->add;
+ MeshDelete *meshdelete = &change->delete;
+ IntIntMap *vert_merge_map = &change->vert_merge_map;
+ IntSet *intersection_edges = &change->intersection_edges;
+ IntSetIterator is_iter;
#ifdef BOOLDEBUG
- int dbg_level = 1;
+ int dbg_level = 0;
#endif
#ifdef BOOLDEBUG
@@ -1109,6 +1247,9 @@ static void apply_meshadd_to_bmesh(BMesh *bm,
}
BLI_assert(bmv2 != NULL);
bme = BM_edge_create(bm, bmv1, bmv2, bme_eg, BM_CREATE_NO_DOUBLE);
+ if (bme_eg) {
+ BM_elem_select_copy(bm, bme, bme_eg);
+ }
#ifdef BOOLDEBUG
if (dbg_level > 0) {
printf("created BMEdge for new edge %d, v1=%d, v2=%d, bmv1=%p, bmv2=%p\n",
@@ -1170,6 +1311,12 @@ static void apply_meshadd_to_bmesh(BMesh *bm,
face_bmes[i] = bme;
}
bmf = BM_face_create(bm, face_bmvs, face_bmes, facelen, bmf_eg, 0);
+ if (bmf_eg) {
+ BM_elem_select_copy(bm, bmf, bmf_eg);
+ }
+ if (find_in_intset(&change->face_flip, f)) {
+ BM_face_normal_flip(bm, bmf);
+ }
#ifdef BOOLDEBUG
if (dbg_level > 0) {
printf("created BMFace for new face %d\n", f);
@@ -1180,12 +1327,39 @@ static void apply_meshadd_to_bmesh(BMesh *bm,
}
}
- /* Delete the geometry that has been rebuilt. */
- /* For now, no verts will be delete */
+ /* Some original faces need their normals flipped. */
+ intset_iter_init(&is_iter, &change->face_flip);
+ for (; !intset_iter_done(&is_iter); intset_iter_step(&is_iter)) {
+ f = intset_iter_value(&is_iter);
+ if (f < bm_tot_f) {
+ bmf = bm->ftable[f];
+ BM_face_normal_flip(bm, bmf);
+ }
+ }
+
+ /* Need to tag the intersection edges. */
+ intset_iter_init(&is_iter, intersection_edges);
+ for ( ; !intset_iter_done(&is_iter); intset_iter_step(&is_iter)) {
+ int e = intset_iter_value(&is_iter);
+ if (e < bm_tot_e) {
+ bme = bm->etable[e];
+ }
+ else {
+ bme = new_bmes[e - meshadd->eindex_start];
+
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list