[Bf-blender-cvs] [61ae6611035] newboolean: Merge branch 'master' into newboolean.
Howard Trickey
noreply at git.blender.org
Sun Jun 7 00:35:58 CEST 2020
Commit: 61ae661103597f5877461eb1695ee86cfd0e4fce
Author: Howard Trickey
Date: Sat Jun 6 18:31:12 2020 -0400
Branches: newboolean
https://developer.blender.org/rB61ae661103597f5877461eb1695ee86cfd0e4fce
Merge branch 'master' into newboolean.
===================================================================
===================================================================
diff --cc source/blender/bmesh/tools/bmesh_boolean.c
index bc95444178b,00000000000..74d390fcabe
mode 100644,000000..100644
--- a/source/blender/bmesh/tools/bmesh_boolean.c
+++ b/source/blender/bmesh/tools/bmesh_boolean.c
@@@ -1,4649 -1,0 +1,4649 @@@
+/*
+ * 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_edgehash.h"
+#include "BLI_kdopbvh.h"
+#include "BLI_kdtree.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
+// #define PERFDEBUG
+
+/* 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.
+ */
+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).
+ *
+ * Some data structures to make for efficient search
+ * are also included in this structure.
+ *
+ * Exactly one of bm and me should be non-null.
+ */
+typedef struct IMesh {
+ BMesh *bm;
+ struct Mesh *me;
+ KDTree_3d *co_tree;
+} IMesh;
+
+/* Structs to hold verts, edges, and faces to be added to 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. */
+ IntSet *other_examples; /* rest of faces in IMesh that are originals for this face */
+} NewFace;
+
+/* 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 {
+ NewVert **verts;
+ NewEdge **edges;
+ NewFace **faces;
+ uint vert_reserved;
+ uint edge_reserved;
+ uint face_reserved;
+ EdgeHash *edge_hash;
+ int totvert;
+ int totedge;
+ int totface;
+ 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;
+
+/* 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;
+
+/* 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
+ * 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.
+ */
+typedef struct MeshPartSet {
+ double bbmin[3];
+ double bbmax[3];
+ MeshPart **meshparts;
+ int tot_part;
+ int reserve; /* number of allocated slots in meshparts; may exceed 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;
+
+/* Bit to set in face_side per face flag inside BoolState. */
+#define SIDE_A 1
+#define SIDE_B 2
+#define BOTH_SIDES_OPP_NORMALS 4
+
+typedef struct BoolState {
+ MemArena *mem_arena;
+ IMesh im;
+ double eps;
+ uchar *face_side;
+} BoolState;
+
+/* 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_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);
+ATTU bool analyze_bmesh_for_boolean(BMesh *bm, bool verbose, int side, uchar *face_side);
+#endif
+
+#ifdef PERFDEBUG
+ATTU static void perfdata_init(void);
+ATTU static void incperfcount(int countnum);
+ATTU static void doperfmax(int maxnum, int val);
+ATTU static void dump_perfdata(void);
+#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 *
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list