[Bf-blender-cvs] [3d50e475f87] newboolean: Initial files for start of new Boolean immplentation.
Howard Trickey
noreply at git.blender.org
Wed Aug 14 15:03:55 CEST 2019
Commit: 3d50e475f874f1f37d2eb36f5e2ac5cdc23bedd2
Author: Howard Trickey
Date: Wed Aug 14 09:01:23 2019 -0400
Branches: newboolean
https://developer.blender.org/rB3d50e475f874f1f37d2eb36f5e2ac5cdc23bedd2
Initial files for start of new Boolean immplentation.
For development, will keep old code around bmesh_intersect.c,
and put new code in bmesh_boolean.c. Eventually, former can be
deleted. But for now, have the intersect/boolean tools pick
new code vs old via an 'experimental' flag in user options.
Nothing works yet, but have started on code for doing intersects
on coplanar faces.
===================================================================
M source/blender/bmesh/CMakeLists.txt
A source/blender/bmesh/tools/bmesh_boolean.c
A source/blender/bmesh/tools/bmesh_boolean.h
M source/blender/editors/mesh/editmesh_intersect.c
===================================================================
diff --git a/source/blender/bmesh/CMakeLists.txt b/source/blender/bmesh/CMakeLists.txt
index f5095ca2b5f..2d728a4b985 100644
--- a/source/blender/bmesh/CMakeLists.txt
+++ b/source/blender/bmesh/CMakeLists.txt
@@ -133,6 +133,8 @@ set(SRC
tools/bmesh_bevel.h
tools/bmesh_bisect_plane.c
tools/bmesh_bisect_plane.h
+ tools/bmesh_boolean.c
+ tools/bmesh_boolean.h
tools/bmesh_decimate.h
tools/bmesh_decimate_collapse.c
tools/bmesh_decimate_dissolve.c
diff --git a/source/blender/bmesh/tools/bmesh_boolean.c b/source/blender/bmesh/tools/bmesh_boolean.c
new file mode 100644
index 00000000000..9286184360f
--- /dev/null
+++ b/source/blender/bmesh/tools/bmesh_boolean.c
@@ -0,0 +1,404 @@
+/*
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+/** \file
+ * \ingroup bmesh
+ *
+ * Cut meshes along intersections.
+ *
+ * Boolean-like modeling operation (without calculating inside/outside).
+ *
+ * Supported:
+ * - Concave faces.
+ * - Non-planar faces.
+ * - Custom-data (UV's etc).
+ *
+ * Unsupported:
+ * - Intersecting between different meshes.
+ * - No support for holes (cutting a hole into a single face).
+ */
+
+#include "MEM_guardedalloc.h"
+
+#include "BLI_math.h"
+#include "BLI_delaunay_2d.h"
+#include "BLI_utildefines.h"
+#include "BLI_memarena.h"
+#include "BLI_alloca.h"
+
+#include "BLI_linklist.h"
+
+#include "bmesh.h"
+#include "intern/bmesh_private.h"
+
+#include "bmesh_boolean.h" /* own include */
+
+#include "BLI_strict_flags.h"
+
+/* A cluster is a set of coplanar faces (within eps) */
+typedef struct Cluster {
+ float plane[4]; /* first 3 are normal, 4th is signed distance to plane */
+ LinkNode *faces; /* list where links are BMFace* */
+} Cluster;
+
+/* A cluster set is a set of Clusters.
+ * 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 BoolState {
+ MemArena *mem_arena;
+ BLI_mempool *listpool;
+ BMesh *bm;
+ int boolean_mode;
+ float eps;
+ int (*test_fn)(BMFace *f, void *user_data);
+ void *test_fn_user_data;
+} BoolState;
+
+#define BOOLDEBUG
+#ifdef BOOLDEBUG
+/* For Debugging. */
+# define CO3(v) (v)->co[0], (v)->co[1], (v)->co[2]
+# define F2(v) (v)[0], (v)[1]
+# define F3(v) (v)[0], (v)[1], (v)[2]
+# 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);
+#endif
+
+/* Make clusterset by empty. */
+static void init_clusterset(ClusterSet *clusterset)
+{
+ clusterset->clusters = NULL;
+}
+
+/* Fill r_plane with the 4d representation of f's plane. */
+static inline void fill_face_plane(float r_plane[4], BMFace *f)
+{
+ plane_from_point_normal_v3(r_plane, f->l_first->v->co, f->no);
+}
+
+/* Return true if a_plane and b_plane are the same plane, to within eps. */
+static bool planes_are_coplanar(const float a_plane[4], const float b_plane[4], float eps)
+{
+ if (fabsf(a_plane[3] - b_plane[3]) > eps) {
+ return false;
+ }
+ 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])
+{
+ LinkNode *ln;
+
+ 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;
+ }
+ }
+ return NULL;
+}
+
+/* Add face f to cluster. */
+static void add_face_to_cluster(BoolState *bs, Cluster *cluster, BMFace *f)
+{
+ BLI_linklist_prepend_arena(&cluster->faces, 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])
+{
+ Cluster *new_cluster;
+
+ 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);
+}
+
+/* Add face f to a cluster in clusterset with the same face, else a new cluster for f */
+static void add_face_to_clusterset(BoolState *bs, ClusterSet *clusterset, BMFace *f)
+{
+ Cluster *matching_cluster;
+ float face_plane[4];
+
+ fill_face_plane(face_plane, f);
+ matching_cluster = find_cluster_for_plane(bs, clusterset, face_plane);
+ if (matching_cluster) {
+ add_face_to_cluster(bs, matching_cluster, f);
+ }
+ else {
+ add_new_cluster_to_clusterset(bs, clusterset, f, face_plane);
+ }
+}
+
+/* Fill clusterset with clusters for mesh faces, putting them into
+ * clusterset_a or clusterset_b as bs->test_fn returns 1 or 0.
+ */
+static void find_clusters(BoolState *bs, ClusterSet *clusterset_a, ClusterSet *clusterset_b)
+{
+ BMesh *bm = bs->bm;
+ BMFace *f;
+ BMIter iter;
+ int testval;
+
+ if (clusterset_a) {
+ init_clusterset(clusterset_a);
+ }
+ if (clusterset_b) {
+ init_clusterset(clusterset_b);
+ }
+ BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) {
+ testval = bs->test_fn(f, bs->test_fn_user_data);
+ if (testval == 1 && clusterset_a) {
+ add_face_to_clusterset(bs, clusterset_a, f);
+ }
+ else if (testval == 0 && clusterset_b) {
+ add_face_to_clusterset(bs, clusterset_b, f);
+ }
+ }
+}
+
+/*
+ * Intersect all of the faces, assumed to be BMFaces in bs->bm.
+ * The faces are assumed to lie in the same plane, given by the plane arg.
+ * Original faces may be deleted and replaced with one or more newly built ones.
+ * Some BMVerts may be merged (one will be used as representative).
+ */
+static void intersect_planar_geometry(BoolState *bs,
+ const float plane[4],
+ BMFace **faces,
+ int faces_len)
+{
+ CDT_input in;
+ CDT_result *out;
+ int nverts, nfaceverts;
+ LinkNode *ln;
+ LinkNode *vertlist = NULL;
+ BMFace *f;
+ BMVert *v;
+ BMIter iter;
+ float mat_2d[3][3];
+ float xy[2];
+ int i, faces_index, vert_coords_index, faces_table_index, v_index;
+
+ nverts = 0;
+ nfaceverts = 0;
+ for (i = 0; i < faces_len; i++) {
+ f = faces[i];
+ BM_ITER_ELEM (v, &iter, f, BM_VERTS_OF_FACE) {
+ nfaceverts++;
+ /* TODO: faster lookup structure to hold verts and their indices */
+ if (BLI_linklist_index(vertlist, v) == -1) {
+ BLI_linklist_prepend_arena(&vertlist, v, bs->mem_arena);
+ nverts++;
+ }
+ }
+ }
+ in.verts_len = nverts;
+ in.edges_len = 0;
+ in.faces_len = faces_len;
+ in.vert_coords = BLI_array_alloca(in.vert_coords, (size_t)nverts);
+ in.edges = NULL;
+ in.faces = BLI_array_alloca(in.faces, (size_t)nfaceverts);
+ in.faces_start_table = BLI_array_alloca(in.faces_start_table, (size_t)faces_len);
+ in.faces_len_table = BLI_array_alloca(in.faces_len_table, (size_t)faces_len);
+ in.epsilon = bs->eps;
+
+ axis_dominant_v3_to_m3(mat_2d, plane);
+ vert_coords_index = 0;
+ for (ln = vertlist; ln; ln = ln->next) {
+ v = (BMVert *)ln->link;
+ mul_v2_m3v3(xy, mat_2d, v->co);
+ copy_v2_v2(in.vert_coords[vert_coords_index], xy);
+ vert_coords_index++;
+ }
+
+ faces_index = 0;
+ faces_table_index = 0;
+ for (i = 0; i < faces_len; i++) {
+ f = faces[i];
+ BLI_assert(faces_table_index < faces_len);
+ in.faces_start_table[faces_table_index] = faces_index;
+ BM_ITER_ELEM (v, &iter, f, BM_VERTS_OF_FACE) {
+ v_index = BLI_linklist_index(vertlist, v);
+ BLI_assert(v_index >= 0 && v_index < nverts);
+ in.faces[faces_index] = v_index;
+ faces_index++;
+ }
+ in.faces_len_table[faces_table_index] = faces_index - in.faces_start_table[faces_table_index];
+ faces_table_index++;
+ }
+
+ printf("cdt input:\n");
+ printf("verts_len=%d, edges_len=%d, faces_len=%d\n", in.verts_len, in.edges_len, in.faces_len);
+ printf("vert_coord: ");
+ for (i = 0; i < in.verts_len; i++) {
+ printf("(%.3f,%.3f) ", F2(in.vert_coords[i]));
+ }
+ printf("\nfaces: ");
+ for (i = 0; i < in.faces_start_table[in.faces_len - 1] + in.faces_len_table[in.faces_len -1]; i++) {
+ printf("%d ", in.faces[i]);
+ }
+ printf("\nfaces_start_table: ");
+ for (i = 0; i < in.faces_len; i++) {
+ printf("%d ", in.faces_start_table[i]);
+ }
+ printf("\nfaces_len_table: ");
+ for (i = 0; i < in.faces_len; i++) {
+ printf("%d ", in.faces_len_table[i]);
+ }
+ printf("\n");
+
+ out = BLI_delaunay_2d_cdt_calc(&in, CDT_CONSTRAINTS_VALID_BMESH);
+
+ printf("out stats: verts_len=%d, edges_len=%d, faces_len=%d\n",
+ out->verts_len,
+ out->edges_len,
+ out->faces_len);
+}
+
+static void intersect_clusters(BoolState *bs, Cluster *cla, Cluster *clb)
+{
+ BMFace **faces, **fp;
+ int i, totfaces;
+ LinkNode *ln;
+ Cluster *cl;
+ Cluster *clab[2] = {cla, clb};
+
+ totfaces = 0;
+ for (i = 0; i < 2; i++) {
+ cl = clab[i];
+ if (cl) {
+ totfaces += BLI_linklist_count(cl-
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list