[Bf-blender-cvs] [05f15a3fd70] newboolean: Better modeling of outputs of individual intersections.
Howard Trickey
noreply at git.blender.org
Thu Aug 22 18:06:19 CEST 2019
Commit: 05f15a3fd704e79671b1bd58575897a3c4c67150
Author: Howard Trickey
Date: Thu Aug 22 12:04:08 2019 -0400
Branches: newboolean
https://developer.blender.org/rB05f15a3fd704e79671b1bd58575897a3c4c67150
Better modeling of outputs of individual intersections.
With new IntersectOutput structure, can see all the algorithms
needed to get from a union of individual IntersectOutputs to
an edit to a Mesh.
===================================================================
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 9b02cb9f4d4..f48f5e9fa8c 100644
--- a/source/blender/bmesh/tools/bmesh_boolean.c
+++ b/source/blender/bmesh/tools/bmesh_boolean.c
@@ -17,18 +17,14 @@
/** \file
* \ingroup bmesh
*
- * Cut meshes along intersections.
- *
- * Boolean-like modeling operation (without calculating inside/outside).
+ * Cut meshes along intersections and boolean operations on the intersections.
*
* Supported:
* - Concave faces.
* - Non-planar faces.
+ * - Coplanar intersections
* - 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"
@@ -47,6 +43,11 @@
#include "BLI_strict_flags.h"
+/* 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 Mesh Interface.
* This would be an abstract interface in C++,
* but similate that effect in C.
@@ -85,7 +86,7 @@ typedef struct MeshPart {
* TODO: faster structure for looking up by plane.
*/
typedef struct MeshPartSet {
- LinkNode *meshparts; /* list where links are MeshParts* */
+ LinkNode *meshparts; /* links are MeshParts* */
int tot_part;
} MeshPartSet;
@@ -94,19 +95,68 @@ typedef struct MeshPartSet {
* TODO: faster structure for lookup.
*/
typedef struct IndexedIntSet {
- LinkNodePair listhead;
+ LinkNodePair listhead; /* links are ints */
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.
+/* A set of 3d coords, where each member gets an index
+ * that can be used to access the member.
+ * Comparisons for equality will be fuzzy (within epsilon).
+ * TODO: faster structure for lookup.
+ */
+typedef struct IndexedCoordSet {
+ LinkNodePair listhead; /* Links are pointers to 3 floats, allocated from arena. */
+ int index_offset; /* "index" of an element will be position in above list plus offset. */
+ int size;
+} IndexedCoordSet;
+
+/* 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;
+
+/* A result of intersectings parts of an implict IMesh.
+ * Designed so that can combine these in pairs, eventually ending up
+ * with a single IntersectOutput that can be turned into an edit on the
+ * underlying original IMesh.
*/
typedef struct IntersectOutput {
- CDT_result *cdt_result;
- float mat_2d_inv[3][3];
- float z_for_inverse;
+ /* All the individual CDT_results. Links are CDT_result pointers. */
+ LinkNodePair cdt_outputs;
+
+ /* Parallel to cdt_outputs list. The corresponding map link is
+ * a pointer to an IntInt map, where the key is a vert index in the
+ * output vert space of the CDT_result, and the value is a vert index
+ * in the original IMesh, or, if greater than orig_mesh_verts_tot,
+ * then an index in new_verts.
+ * Links are pointers to IntIntMap, allocated from arena.
+ */
+ LinkNodePair vertmaps;
+
+ /* Set of new vertices (not in original mesh) in resulting intersection.
+ * They get an index in the range from orig_mesh_verts_tot to that
+ * number plus the size of new_verts - 1.
+ * This should be a de-duplicated set of coordinates.
+ */
+ IndexedCoordSet new_verts;
+
+ /* A map recording which verts in the original mesh get merged to
+ * other verts in that mesh.
+ * If there is an entry for an index v (< orig_mesh_verts_tot), then
+ * v is merged to the value of the map at v.
+ * Otherwise v is not merged to anything.
+ */
+ IntIntMap merge_to;
+
+ /* Number of verts in the original IMesh that this is based on. */
+ int orig_mesh_verts_tot;
} IntersectOutput;
typedef struct BoolState {
@@ -134,6 +184,11 @@ static void dump_part(MeshPart *part, const char *label);
static void dump_partset(MeshPartSet *pset, const char *label);
#endif
+static CDT_result *copy_cdt_result(BoolState *bs, const CDT_result *res);
+static int min_int_in_array(int *array, int len);
+
+/** IMesh functions. */
+
static void init_imesh_from_bmesh(IMesh *im, BMesh *bm)
{
im->bm = bm;
@@ -141,6 +196,16 @@ static void init_imesh_from_bmesh(IMesh *im, BMesh *bm)
BM_mesh_elem_table_ensure(bm, BM_VERT | BM_EDGE | BM_FACE);
}
+static int imesh_totvert(const IMesh *im)
+{
+ if (im->bm) {
+ return im->bm->totvert;
+ }
+ else {
+ return 0; /* TODO */
+ }
+}
+
static int imesh_totface(const IMesh *im)
{
if (im->bm) {
@@ -232,21 +297,7 @@ static int imesh_test_face(const IMesh *im, int (*test_fn)(void *, void *), void
}
}
-
-#if 0
-/**
- * Make ngon from verts alone.
- * Use facerep as example for attributes of new face.
- * TODO: make this an similar bev_create_ngon in bmesh_bevel.c into a BMesh utility.
- */
-static BMFace *bool_create_ngon(BMesh *bm, BMVert **vert_arr, const int vert_len, BMFace *facerep)
-{
- BMFace *f;
-
- f = BM_face_create_verts(bm, vert_arr, vert_len, facerep, BM_CREATE_NOP, true);
- return f;
-}
-#endif
+/** MeshPartSet functions. */
static void init_meshpartset(MeshPartSet *partset)
{
@@ -269,6 +320,8 @@ static MeshPart *partset_part(MeshPartSet *partset, int index)
return NULL;
}
+/** MeshPart functions. */
+
static void init_meshpart(MeshPart *part)
{
zero_v4(part->plane);
@@ -332,7 +385,9 @@ static void add_face_to_part(BoolState *bs, MeshPart *meshpart, int f)
BLI_linklist_prepend_arena(&meshpart->faces, POINTER_FROM_INT(f), bs->mem_arena);
}
-static void init_indexed_intset(IndexedIntSet *intset)
+/** IndexedIntSet functions. */
+
+static void init_intset(IndexedIntSet *intset)
{
intset->listhead.list = NULL;
intset->listhead.last_node = NULL;
@@ -374,9 +429,147 @@ static int intset_get_index_for_value(const IndexedIntSet *intset, int value)
return BLI_linklist_index(intset->listhead.list, POINTER_FROM_INT(value));
}
-#define COPY_ARRAY_TO_ARENA(dst, src, len, arena) { \
- dst = BLI_memarena_alloc(arena, len); \
- memmove(dst, src, len); \
+/** IndexedCoordSet functions. */
+
+static void init_coordset(IndexedCoordSet *coordset, int index_offset)
+{
+ coordset->listhead.list = NULL;
+ coordset->listhead.last_node = NULL;
+ coordset->index_offset = index_offset;
+ coordset->size = 0;
+}
+
+static int add_to_coordset(BoolState *bs,
+ IndexedCoordSet *coordset,
+ const float p[3],
+ bool do_dup_check)
+{
+ LinkNode *ln;
+ float *q;
+ int i;
+ int index = -1;
+
+ if (do_dup_check) {
+ i = coordset->index_offset;
+ for (ln = coordset->listhead.list; ln; ln = ln->next) {
+ q = (float *)ln->link;
+ /* Note: compare_v3v3 checks if all three coords are within (<=) eps of each other. */
+ if (compare_v3v3(p, q, bs->eps)) {
+ index = i;
+ break;
+ }
+ i++;
+ }
+ if (index != -1) {
+ return index;
+ }
+ }
+ q = BLI_memarena_alloc(bs->mem_arena, 3 * sizeof(float));
+ copy_v3_v3(q, p);
+ BLI_linklist_append_arena(&coordset->listhead, q, bs->mem_arena);
+ index = coordset->index_offset + coordset->size;
+ coordset->size++;
+ return index;
+}
+
+/** IntIntMap functions. */
+
+static void init_intintmap(IntIntMap *intintmap)
+{
+ intintmap->listhead.list = NULL;
+ intintmap->listhead.last_node = NULL;
+}
+
+static void add_to_intintmap(BoolState *bs, IntIntMap *map, int key, int val)
+{
+ IntPair *keyvalpair;
+
+ keyvalpair = BLI_memarena_alloc(bs->mem_arena, sizeof(*keyvalpair));
+ keyvalpair->first = key;
+ keyvalpair->second = val;
+ BLI_linklist_append_arena(&map->listhead, keyvalpair, bs->mem_arena);
+}
+
+/** IntersectOutput functions. */
+
+static void init_isect_out(BoolState *bs, IntersectOutput *isect_out)
+{
+ isect_out->orig_mesh_verts_tot = imesh_totvert(&bs->im);
+ isect_out->cdt_outputs.list = NULL;
+ isect_out->cdt_outputs.last_node = NULL;
+
+ isect_out->vertmaps.list = NULL;
+ isect_out->vertmaps.last_node = NULL;
+
+ init_coordset(&isect_out->new_verts, isect_out->orig_mesh_verts_tot);
+
+ init_intintmap(&isect_out->merge_to);
+}
+
+static void isect_add_cdt_result(BoolState *bs, IntersectOutput *isect_out, CDT_result *res)
+{
+ BLI_linklist_append_arena(&isect_out->cdt_outputs, res, bs->mem_arena);
+}
+
+static IntIntMap *isect_add_vertmap(BoolState *bs, IntersectOutput *isect_out)
+{
+ IntIntMap *ans;
+
+ ans = BLI_memarena_alloc(bs->mem_arena, sizeof(*ans));
+ init_intintmap(ans);
+ BLI_linklist_append_arena(&isect_out->vertmaps, ans, bs->mem_arena);
+ return ans;
+}
+
+static IntersectOutput *isect_out_from_cdt(BoolState *bs,
+ const CDT_result *cout,
+ const float rot_inv[3][3],
+ const float z_for_inverse)
+{
+ IntersectOutput *isect_out;
+ CDT_result *cout_copy;
+ int out_v, in_v, start, new_v;
+ IntIntMap *vmap;
+ float p[3], q[3];
+
+ isect_out = BLI_memarena_alloc(bs->mem_arena, sizeof(*isect_out));
+ init_isect_out(bs, isect_out);
+
+ /* Need to copy cdt result to arena because caller will soon call BLI_delaunay_2d_cdt_free(cout).
+ */
+ cout_copy = copy_cdt_result(bs, cout);
+ isect_add_cdt_result(bs, isect_out, cout_copy);
+
+ vmap = isect_add_vertmap(bs, isect_out);
+
+ for (out_v = 0; out_v < cout->verts_len; out_v++) {
+ if (cout->verts_orig_len_table[out_v] > 0) {
+ /* out_v maps to an original vertex. */
+ start = cout->verts_orig_start_table[out_v];
+ /* Choose min index in orig list, to make for a stable algorithm. */
+ in_v = min_int_in_array(&cout->verts_orig[start], cout->verts_orig_len_table[out_v]);
+ add_to_intint
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list