Commit: 71953aec1a5c47018253736f68f6c8ca2e3aafa4
Author: Howard Trickey
Date: Tue Aug 20 07:00:22 2019 -0400
Branches: newboolean
https://developer.blender.org/rB71953aec1a5c47018253736f68f6c8ca2e3aafa4
Refactor to use abstract mesh interface.
If use abstract mesh interface instead of BMesh then there is hope
that modifier can avoid need to convert to/from BMesh.
===================================================================
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 203a1d10cca..9b02cb9f4d4 100644
--- a/source/blender/bmesh/tools/bmesh_boolean.c
+++ b/source/blender/bmesh/tools/bmesh_boolean.c
@@ -40,7 +40,6 @@
#include "BLI_memarena.h"
#include "BLI_utildefines.h"
-
#include "bmesh.h"
#include "intern/bmesh_private.h"
@@ -48,31 +47,80 @@
#include "BLI_strict_flags.h"
-/* A cluster is a set of coplanar faces (within eps) */
-typedef struct Cluster {
+/* A Mesh Interface.
+ * This would be an abstract interface in C++,
+ * but similate that effect in C.
+ * Idea is to write the rest of the code so that
+ * it will work with either Mesh or BMesh as the
+ * concrete representation.
+ * Thus, editmesh and modifier can use the same
+ * code but without need to convert to BMesh (or Mesh).
+ *
+ * Exactly one of bm and me should be non-null.
+ */
+typedef struct IMesh {
+ BMesh *bm;
+ struct Mesh *me;
+} IMesh;
+
+/* A MeshPart is a subset of the geometry of an IndexMesh.
+ * The indices refer to vertex, edges, and faces in the IndexMesh
+ * that this part is based on (which will be known by context).
+ * Unlike for IndexMesh, the edges implied by faces need not be explicitly
+ * represented here.
+ * Commonly a MeshPart will contain geometry that shares a plane,
+ * and when that is so, the plane member says which plane,
+ * TODO: faster structure for looking up verts, edges, faces.
+ */
+typedef struct MeshPart {
float plane[4]; /* first 3 are normal, 4th is signed distance to plane */
- LinkNode *faces; /* list where links are BMFace* */
-} Cluster;
+ LinkNode *verts; /* links are ints (vert indices) */
+ LinkNode *edges; /* links are ints (edge indices) */
+ LinkNode *faces; /* links are ints (face indices) */
+} MeshPart;
-/* A cluster set is a set of Clusters.
+/* A MeshPartSet set is a set of MeshParts.
* For any two distinct elements of the set, either they are not
* coplanar or if they are, they are known not to intersect.
* TODO: faster structure for looking up by plane.
*/
-typedef struct ClusterSet {
- LinkNode *clusters; /* list where links are Cluster* */
-} ClusterSet;
+typedef struct MeshPartSet {
+ LinkNode *meshparts; /* list where links are MeshParts* */
+ int tot_part;
+} MeshPartSet;
+
+/* A set of integers, where each member gets an index
+ * that can be used to access the member.
+ * TODO: faster structure for lookup.
+ */
+typedef struct IndexedIntSet {
+ LinkNodePair listhead;
+ int size;
+} IndexedIntSet;
+
+/* A result of intersectings parts.
+ * The coordinates in the cdt_result should be turned
+ * back into 3d coords by multplying them by mat_2d_inv,
+ * after putting z_for_inverse into the 3rd component.
+ */
+typedef struct IntersectOutput {
+ CDT_result *cdt_result;
+ float mat_2d_inv[3][3];
+ float z_for_inverse;
+} IntersectOutput;
typedef struct BoolState {
MemArena *mem_arena;
- BLI_mempool *listpool;
- BMesh *bm;
+ IMesh im;
int boolean_mode;
float eps;
- int (*test_fn)(BMFace *f, void *user_data);
+ int (*test_fn)(void *elem, void *user_data);
void *test_fn_user_data;
} BoolState;
+/* test_fn results used to distinguish parts of mesh */
+enum { TEST_B = -1, TEST_NONE = 0, TEST_A = 1, TEST_ALL = 2 };
+
#define BOOLDEBUG
#ifdef BOOLDEBUG
/* For Debugging. */
@@ -82,10 +130,110 @@ typedef struct BoolState {
# define F4(v) (v)[0], (v)[1], (v)[2], (v)[3]
# define BMI(e) BM_elem_index_get(e)
-static void dump_cluster(Cluster *cl, const char *label);
-static void dump_clusterset(ClusterSet *clset, const char *label);
+static void dump_part(MeshPart *part, const char *label);
+static void dump_partset(MeshPartSet *pset, const char *label);
#endif
+static void init_imesh_from_bmesh(IMesh *im, BMesh *bm)
+{
+ im->bm = bm;
+ im->me = NULL;
+ BM_mesh_elem_table_ensure(bm, BM_VERT | BM_EDGE | BM_FACE);
+}
+
+static int imesh_totface(const IMesh *im)
+{
+ if (im->bm) {
+ return im->bm->totface;
+ }
+ else {
+ return 0; /* TODO */
+ }
+}
+
+static int imesh_facelen(const IMesh *im, int f)
+{
+ int ans = 0;
+
+ if (im->bm) {
+ BMFace *bmf = BM_face_at_index(im->bm, f);
+ if (bmf) {
+ ans = bmf->len;
+ }
+ }
+ else {
+ ; /* TODO */
+ }
+ return ans;
+}
+
+static int imesh_face_vert(IMesh *im, int f, int index)
+{
+ int i;
+ int ans = -1;
+
+ if (im->bm) {
+ BMFace *bmf = BM_face_at_index(im->bm, f);
+ if (bmf) {
+ BMLoop *l = bmf->l_first;
+ for (i = 0; i < index; i++) {
+ l = l->next;
+ }
+ BMVert *bmv = l->v;
+ ans = BM_elem_index_get(bmv);
+ }
+ }
+ else {
+ ; /* TODO */
+ }
+ return ans;
+}
+
+static void imesh_get_vert_co(const IMesh *im, int v, float *r_coords)
+{
+ if (im->bm) {
+ BMVert *bmv = BM_vert_at_index(im->bm, v);
+ if (bmv) {
+ copy_v3_v3(r_coords, bmv->co);
+ return;
+ }
+ else {
+ zero_v3(r_coords);
+ }
+ }
+ else {
+ ; /* TODO */
+ }
+}
+
+static void imesh_get_face_plane(const IMesh *im, int f, float r_plane[4])
+{
+ zero_v4(r_plane);
+ if (im->bm) {
+ BMFace *bmf = BM_face_at_index(im->bm, f);
+ if (bmf) {
+ plane_from_point_normal_v3(r_plane, bmf->l_first->v->co, bmf->no);
+ }
+ }
+}
+
+static int imesh_test_face(const IMesh *im, int (*test_fn)(void *, void *),
void *user_data, int f)
+{
+ if (im->bm) {
+ BMFace *bmf = BM_face_at_index(im->bm, f);
+ if (bmf) {
+ return test_fn(bmf, user_data);
+ }
+ return 0;
+ }
+ else {
+ /* TODO */
+ return 0;
+ }
+}
+
+
+#if 0
/**
* Make ngon from verts alone.
* Use facerep as example for attributes of new face.
@@ -98,17 +246,54 @@ static BMFace *bool_create_ngon(BMesh *bm, BMVert
**vert_arr, const int vert_len
f = BM_face_create_verts(bm, vert_arr, vert_len, facerep, BM_CREATE_NOP,
true);
return f;
}
+#endif
-/* Make clusterset by empty. */
-static void init_clusterset(ClusterSet *clusterset)
+static void init_meshpartset(MeshPartSet *partset)
{
- clusterset->clusters = NULL;
+ partset->meshparts = NULL;
+ partset->tot_part = 0;
}
-/* Fill r_plane with the 4d representation of f's plane. */
-static inline void fill_face_plane(float r_plane[4], BMFace *f)
+static void add_part_to_partset(BoolState *bs, MeshPartSet *partset, MeshPart
*part)
{
- plane_from_point_normal_v3(r_plane, f->l_first->v->co, f->no);
+ BLI_linklist_prepend_arena(&partset->meshparts, part, bs->mem_arena);
+ partset->tot_part++;
+}
+
+static MeshPart *partset_part(MeshPartSet *partset, int index)
+{
+ LinkNode *ln = BLI_linklist_find(partset->meshparts, index);
+ if (ln) {
+ return (MeshPart *)ln->link;
+ }
+ return NULL;
+}
+
+static void init_meshpart(MeshPart *part)
+{
+ zero_v4(part->plane);
+ part->verts = NULL;
+ part->edges = NULL;
+ part->faces = NULL;
+}
+
+static int part_totface(MeshPart *part)
+{
+ return BLI_linklist_count(part->faces);
+}
+
+static int part_face(MeshPart *part, int index)
+{
+ LinkNode *ln = BLI_linklist_find(part->faces, index);
+ if (ln) {
+ return POINTER_AS_INT(ln->link);
+ }
+ return -1;
+}
+
+static bool parts_may_intersect(MeshPart *part1, MeshPart *part2)
+{
+ return (part1 && part2); /* Placeholder test, uses args */
}
/* Return true if a_plane and b_plane are the same plane, to within eps. */
@@ -120,169 +305,281 @@ static bool planes_are_coplanar(const float a_plane[4],
const float b_plane[4],
return fabsf(dot_v3v3(a_plane, b_plane) - 1.0f) <= eps;
}
-/* Return the cluster in clusterset for plane face_plane, if it exists, else
NULL. */
-static Cluster *find_cluster_for_plane(BoolState *bs,
- ClusterSet *clusterset,
- const float face_plane[4])
+/* Return the MeshPart in partset for plane.
+ * If none exists, make a new one for the plane and add
+ * it to partset.
+ */
+static MeshPart *find_part_for_plane(BoolState *bs, MeshPartSet *partset,
const float plane[4])
{
LinkNode *ln;
+ MeshPart *new_part;
- for (ln = clusterset->clusters; ln; ln = ln->next) {
- Cluster *cl = (Cluster *)ln->link;
- if (planes_are_coplanar(face_plane, cl->plane, bs->eps)) {
- return cl;
+ for (ln = partset->meshparts; ln; ln = ln->next) {
+ MeshPart *p = (MeshPart *)ln->link;
+ if (planes_are_coplanar(plane, p->plane, bs->eps)) {
+ return p;
}
}
- return NULL;
+ new_part = BLI_memarena_alloc(bs->mem_arena, sizeof(MeshPart));
+ init_meshpart(new_part);
+ copy_v4_v4(new_part->plane, plane);
+ add_part_to_partset(bs, partset, new_part);
+ return new_part;
}
-/* Add face f to cluster. */
-static void add_face_to_cluster(BoolState *bs, Cluster *cluster, BMFace *f)
+static void add_face_to_part(BoolState *bs, MeshPart *meshpart, int f)
{
- BLI_linklist_prepend_arena(&cluster->faces, f, bs->mem_arena);
+ BLI_linklist_prepend_arena(&meshpart->faces, POINTER_FROM_INT(f),
bs->mem_arena);
}
-/* Make a new cluster containing face f, then add it to clusterset. */
-static void add_new_cluster_to_clusterset(BoolState *bs,
- ClusterSet *clusterset,
- BMFace *f,
- const float plane[4])
+static void init_indexed_intset(IndexedIntSet *intset)
{
- Cluster *new_cluster;
+ intset->listhead.list = NULL;
+ intset->listhead.last_node = NULL;
+ intset->size = 0;
+}
- new_cluster = BLI_memarena_alloc(bs->mem_arena, sizeof(Cluster));
- copy_v4_v4(new_cluster->plane, plane);
- new_cluster->faces = NULL;
- BLI_linklist_prepend_arena(&new_cluster->faces, f, bs->mem_arena);
- BLI_linklist_prepend_arena(&clusterset->clusters, new_cluster,
bs->mem_arena);
+static int add_int_to_intset(BoolState *bs, IndexedIntSet *intset, int value)
+{
+ int index;
+
+ index = BLI_linklist_index(intset->listhead.list, POINTER_FROM_INT(value));
+ if (index == -1) {
+ BLI_linklist_append_arena(&intset->listhead, POINTER_FROM_INT(value),
bs->mem_arena);
+ index = intset->size;
+ intset->size++;
+ }
+ return index;
}
-/* Add face f to a cluster in clusterset with the same face, else a new
cluster for f */
-static void add_
@@ Diff output truncated at 10240 characters. @@
_______________________________________________
Bf-blender-cvs mailing list
Bf-blender-cvs@blender.org
https://lists.blender.org/mailman/listinfo/bf-blender-cvs
