[Bf-blender-cvs] [e4b24e6e0cd] newboolean: All tri-tri non-coplanar tests work.

[Howard Trickey]

Commit: e4b24e6e0cd20a30b0cc3722be1b7628072f4f8d
Author: Howard Trickey
Date:   Mon Oct 7 06:51:17 2019 -0400
Branches: newboolean
https://developer.blender.org/rBe4b24e6e0cd20a30b0cc3722be1b7628072f4f8d

All tri-tri non-coplanar tests work.

===================================================================

A	source/blender/bmesh/tools/bmesh_boolean.c
A	source/blender/bmesh/tools/bmesh_boolean.h

===================================================================

diff --git a/source/blender/bmesh/tools/bmesh_boolean.c b/source/blender/bmesh/tools/bmesh_boolean.c
new file mode 100644
index 00000000000..151626f8bcd
--- /dev/null
+++ b/source/blender/bmesh/tools/bmesh_boolean.c
@@ -0,0 +1,3345 @@
+/*
+ * 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 and boolean operations on the intersections.
+ *
+ * Supported:
+ * - Concave faces.
+ * - Non-planar faces.
+ * - Coplanar intersections
+ * - Custom-data (UV's etc).
+ *
+ */
+
+#include "MEM_guardedalloc.h"
+
+#include "BLI_alloca.h"
+#include "BLI_bitmap.h"
+#include "BLI_delaunay_2d.h"
+#include "BLI_linklist.h"
+#include "BLI_math.h"
+#include "BLI_memarena.h"
+#include "BLI_utildefines.h"
+
+#include "bmesh.h"
+#include "intern/bmesh_private.h"
+
+#include "bmesh_boolean.h" /* own include */
+
+#include "BLI_strict_flags.h"
+
+#define BOOLDEBUG
+
+/* NOTE: Work in progress. Initial implementation using slow data structures and algorithms
+ * just to get the correct calculations down. After that, will replace data structures with
+ * faster-lookup versions (hash tables, kd-trees, bvh structures) and will parallelize.
+ */
+
+/* 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; /* links are ints */
+  int size;
+} IndexedIntSet;
+
+/* A map from int -> int.
+ * TODO: faster structure for lookup.
+ */
+typedef struct IntIntMap {
+  LinkNodePair listhead; /* Links are pointers to IntPair, allocated from arena. */
+} IntIntMap;
+
+typedef struct IntPair {
+  int first;
+  int second;
+} IntPair;
+
+typedef struct IntIntMapIterator {
+  const IntIntMap *map;
+  LinkNode *curlink;
+  IntPair *keyvalue;
+} IntIntMapIterator;
+
+/* 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;
+
+/* MeshAdd holds an incremental addition to an IMesh.
+ * New verts, edges, and faces are given indices starting
+ * beyond those of the underlying IMesh, and that new
+ * geometry is stored here. For edges and faces, the
+ * indices used can be either from the IMesh or from the
+ * new geometry stored here.
+ * Sometimes the new geometric elements are based on
+ * an example element in the underlying IMesh (the example
+ * will be used to copy attributes).
+ * So we store examples here too.
+ */
+typedef struct MeshAdd {
+  LinkNodePair verts; /* Links are NewVerts. */
+  LinkNodePair edges; /* Links are NewEdges. */
+  LinkNodePair faces; /* Links are NewFaces. */
+  int vindex_start;   /* Add this to position in verts to get index of new vert. */
+  int eindex_start;   /* Add this to position in edges to get index of new edge. */
+  int findex_start;   /* Add this to position in faces to get index of new face. */
+  IMesh *im;          /* Underlying IMesh. */
+} MeshAdd;
+
+typedef struct NewVert {
+  float co[3];
+  int example; /* If not -1, example vert in IMesh. */
+} NewVert;
+
+typedef struct NewEdge {
+  int v1;
+  int v2;
+  int example; /* If not -1, example edge in IMesh. */
+} NewEdge;
+
+typedef struct NewFace {
+  IntPair *vert_edge_pairs; /* Array of len (vert, edge) pairs. */
+  int len;
+  int example; /* If not -1, example face in IMesh. */
+} NewFace;
+
+/* MeshDelete holds an incremental deletion to an IMesh.
+ * It records the indices of the edges and faces that need
+ * to be deleted. (As of now, we don't have to delete verts
+ * except those that recorded separately as merges.)
+ */
+typedef struct MeshDelete {
+  BLI_bitmap *vert_bmap;
+  BLI_bitmap *edge_bmap;
+  BLI_bitmap *face_bmap;
+  int totvert;
+  int totedge;
+  int totface;
+} MeshDelete;
+
+/* 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
+ * that this part is based on,
+ * or, if the indices are larger than the total in the IndexMesh,
+ * then it is in extra geometry incrementally added.
+ * 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 {
+  double plane[4]; /* First 3 are normal, 4th is signed distance to plane. */
+  double bbmin[3]; /* Bounding box min, with eps padding. */
+  double 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). */
+} MeshPart;
+
+/* 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 MeshPartSet {
+  double bbmin[3];
+  double bbmax[3];
+  LinkNode *meshparts; /* links are MeshParts* */
+  int tot_part;
+  const char *label; /* for debugging */
+} MeshPartSet;
+
+/* An IMeshPlus is an IMesh plus a MeshAdd.
+ * If the element indices are in range for the IMesh, then functions
+ * access those, else they access the MeshAdd.
+ */
+typedef struct IMeshPlus {
+  IMesh *im;
+  MeshAdd *meshadd;
+} IMeshPlus;
+
+/* Result of intersecting two MeshParts.
+ * This only need identify the thngs that probably intersect,
+ * as the actual intersections will be done later, when
+ * parts are self-intersected. Dedup will handle any problems.
+ * It is not necessary to include verts that are part of included
+ * edges, nor edges that are part of included faces.
+ */
+typedef struct PartPartIntersect {
+  LinkNodePair verts; /* Links are vert indices. */
+  LinkNodePair edges; /* Links are edge indices. */
+  LinkNodePair faces; /* Links are face indices. */
+  int a_index;
+  int b_index;
+} PartPartIntersect;
+
+typedef struct BoolState {
+  MemArena *mem_arena;
+  IMesh im;
+  int boolean_mode;
+  double eps;
+  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_NONE = -1, TEST_B = 0, TEST_A = 1, TEST_ALL = 2 };
+
+/* Decoration to shut up gnu 'unused function' warning. */
+#ifdef __GNUC__
+#  define ATTU __attribute__((unused))
+#else
+#  define ATTU
+#endif
+
+#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)
+
+ATTU static void dump_part(const MeshPart *part, const char *label);
+ATTU static void dump_partset(const MeshPartSet *pset);
+ATTU static void dump_partpartintersect(const PartPartIntersect *ppi, const char *label);
+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_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);
+#endif
+
+/* Forward declarations of some static functions. */
+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, double eps);
+static bool find_in_intintmap(const IntIntMap *map, int key, int *r_val);
+static int meshadd_totvert(const MeshAdd *meshadd);
+static int meshadd_totedge(const MeshAdd *meshadd);
+static int meshadd_totface(const MeshAdd *meshadd);
+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 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);
+static bool meshdelete_find_vert(MeshDelete *meshdelete, int v);
+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);
+
+/** IndexedIntSet functions. */
+
+static void init_intset(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)
+{
+  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

@@ Diff output truncated at 10240 characters. @@