[Bf-blender-cvs] [15483ba26d7] newboolean: First tri-tri test works.
Howard Trickey
noreply at git.blender.org
Sun Sep 8 12:47:02 CEST 2019
Commit: 15483ba26d77706928a7ed9b2dbaaa7d176edb26
Author: Howard Trickey
Date: Sun Sep 8 16:03:17 2019 +0530
Branches: newboolean
https://developer.blender.org/rB15483ba26d77706928a7ed9b2dbaaa7d176edb26
First tri-tri test works.
===================================================================
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 92b8d03f733..27cab28425c 100644
--- a/source/blender/bmesh/tools/bmesh_boolean.c
+++ b/source/blender/bmesh/tools/bmesh_boolean.c
@@ -30,7 +30,7 @@
#include "MEM_guardedalloc.h"
#include "BLI_alloca.h"
-#include "BLI_array.h"
+#include "BLI_bitmap.h"
#include "BLI_delaunay_2d.h"
#include "BLI_linklist.h"
#include "BLI_math.h"
@@ -42,7 +42,7 @@
#include "bmesh_boolean.h" /* own include */
-//#include "BLI_strict_flags.h"
+#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
@@ -58,17 +58,6 @@ typedef struct IndexedIntSet {
int size;
} IndexedIntSet;
-/* 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.
*/
@@ -141,6 +130,20 @@ typedef struct NewFace {
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
@@ -231,6 +234,7 @@ 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);
@@ -240,8 +244,20 @@ ATTU static void dump_cdt_result(const CDT_result *cdt, const char *label, const
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 float *coordset_coord(const IndexedCoordSet *coordset, int index);
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_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. */
@@ -287,67 +303,6 @@ static int intset_get_index_for_value(const IndexedIntSet *intset, int value)
return BLI_linklist_index(intset->listhead.list, POINTER_FROM_INT(value));
}
-/** IndexedCoordSet functions. */
-
-/* Indices in IndexedCoordSets start at index_offset. */
-
-ATTU 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;
-}
-
-ATTU 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;
- float feps = (float)bs->eps;
-
- 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, feps)) {
- 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;
-}
-
-ATTU static float *coordset_coord(const IndexedCoordSet *coordset, int index)
-{
- int i;
-
- i = index - coordset->index_offset;
- if (i < 0 || i >= coordset->size) {
- return NULL;
- }
- LinkNode *ln = BLI_linklist_find(coordset->listhead.list, i);
- if (ln) {
- return (float *)(ln->link);
- }
- return NULL;
-}
-
/** IntIntMap functions. */
static void init_intintmap(IntIntMap *intintmap)
@@ -1042,30 +997,49 @@ static int imesh_test_face(const IMesh *im, int (*test_fn)(void *, void *), void
}
}
-#if 0
-static void apply_isect_out_to_bmesh(BMesh *bm, const IntersectOutput *isect_out)
-{
- int bm_tot_v, tot_new_v, tot_new_e, i, j, v1, v2, v1_out, v2_out;
- int tot_new_f, fstart, flen, v, v_out;
- BMVert **new_bmvs, *bmv, *bmv1, *bmv2;
- float *co;
- LinkNode *ln, *ln_map;
- CDT_result *cdt;
- IntIntMap *vmap;
- BMVert **vv = NULL;
- BLI_array_staticdeclare(vv, BM_DEFAULT_NGON_STACK_SIZE);
-
- printf("\n\nAPPLY_ISECT_OUT_TO_BMESH\n\n");
- /* Create the new BMVerts. */
+static int resolve_merge(int v, const IntIntMap *vert_merge_map)
+{
+ int vmapped = v;
+ int target;
+
+ while (find_in_intintmap(vert_merge_map, vmapped, &target)) {
+ vmapped = target;
+ }
+ return vmapped;
+}
+
+static void apply_meshadd_to_bmesh(BMesh *bm,
+ const MeshAdd *meshadd,
+ MeshDelete *meshdelete,
+ const IntIntMap *vert_merge_map)
+{
+ int bm_tot_v, bm_tot_e, bm_tot_f, tot_new_v, tot_new_e, tot_new_f;
+ int i, v, e, f, v1, v2;
+ int facelen, max_facelen;
+ NewVert *newvert;
+ NewEdge *newedge;
+ NewFace *newface;
+ BMVert **new_bmvs, **face_bmvs;
+ BMVert *bmv, *bmv1, *bmv2;
+ BMEdge **new_bmes, **face_bmes;
+ BMEdge *bme, *bme_eg;
+ BMFace *bmf, *bmf_eg;
+
+ printf("\n\nAPPLY_MESHADD_TO_BMESH\n\n");
+
+ /* Create new BMVerts. */
bm_tot_v = bm->totvert;
- tot_new_v = isect_out->new_verts.size;
+ tot_new_v = meshadd_totvert(meshadd);
if (tot_new_v > 0) {
new_bmvs = BLI_array_alloca(new_bmvs, (size_t)tot_new_v);
- for (i = 0; i < tot_new_v; i++) {
- co = coordset_coord(&isect_out->new_verts, bm_tot_v + i);
- /* TODO: use an example vert if there is one */
- new_bmvs[i] = BM_vert_create(bm, co, NULL, 0);
- printf("new_bmv[%d]=%p, at (%.3f,%.3f,%.3f)\n", i, new_bmvs[i], F3(co));
+ for (v = meshadd->vindex_start; v < meshadd->vindex_start + tot_new_v; v++) {
+ newvert = meshadd_get_newvert(meshadd, v);
+ if (newvert->example != -1) {
+ printf("implement using example to create BMVert\n");
+ }
+ BLI_assert(newvert != NULL);
+ bmv = BM_vert_create(bm, newvert->co, NULL, 0);
+ new_bmvs[v - meshadd->vindex_start] = bmv;
}
}
@@ -1075,94 +1049,120 @@ static void apply_isect_out_to_bmesh(BMesh *bm, const IntersectOutput *isect_out
*/
BM_mesh_elem_table_ensure(bm, BM_VERT);
- /* Now create edges and faces from each cdt_output */
- for (ln = isect_out->cdt_outputs.list, ln_map = isect_out->vertmaps.list; ln;
- ln = ln->next, ln_map = ln_map->next) {
- printf("\napply cdt output\n");
- cdt = (CDT_result *)ln->link;
- vmap = (IntIntMap *)ln_map->link;
- tot_new_e = cdt->edges_len;
- for (i = 0; i < tot_new_e; i++) {
- v1 = cdt->edges[i][0];
- v2 = cdt->edges[i][1];
- if (!find_in_intintmap(vmap, v1, &v1_out)) {
- printf("whoops, v1 map entry missing\n");
- BLI_assert(false);
- v1_out = v1;
+ /* Now the edges. */
+ bm_tot_e = bm->totedge;
+ tot_new_e = meshadd_totedge(meshadd);
+ if (tot_new_e > 0) {
+ new_bmes = BLI_array_alloca(new_bmes, (size_t)tot_new_e);
+ for (e = meshadd->eindex_start; e < meshadd->eindex_start + tot_new_e; e++) {
+ newedge = meshadd_get_newedge(meshadd, e);
+ BLI_assert(newedge != NULL);
+ if (newedge->example != -1) {
+ /* Not really supposed to access bm->etable directly but even
+ * though it may be technically dirty, all of the example indices
+ * will still be OK. */
+ bme_eg = bm->etable[newedge->example];
}
- if (!find_in_intintmap(vmap, v2, &v2_out)) {
- printf("whoops, v2 map entry missing\n");
- BLI_assert(false);
- v2_out = v2;
+ else {
+ bme_eg = NULL;
}
- printf("make edge %d %d\n", v1_out, v2_out);
- if (v1_out < bm_tot_v) {
-
- bmv1 = BM_vert_at_index(bm, v1_out);
+ v1 = newedge->v1;
+ v2 = newedge->v2;
+ if (v1 < bm_tot_v) {
+ v1 = resolve_merge(v1, vert_merge_map);
+ bmv1 = BM_vert_at_index(bm, v1);
+ }
+ else
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list