[Bf-blender-cvs] [c2d65e37eb7] newboolean: The tri-tri intersection code partially hooked up.
Howard Trickey
noreply at git.blender.org
Tue Sep 3 05:18:54 CEST 2019
Commit: c2d65e37eb7944e2a054969b9874b579a9e8c958
Author: Howard Trickey
Date: Sat Aug 31 19:59:07 2019 -0400
Branches: newboolean
https://developer.blender.org/rBc2d65e37eb7944e2a054969b9874b579a9e8c958
The tri-tri intersection code partially hooked up.
===================================================================
M source/blender/blenlib/BLI_math_base.h
M source/blender/blenlib/BLI_math_vector.h
M source/blender/blenlib/intern/math_base_inline.c
M source/blender/blenlib/intern/math_vector_inline.c
M source/blender/bmesh/tools/bmesh_boolean.c
===================================================================
diff --git a/source/blender/blenlib/BLI_math_base.h b/source/blender/blenlib/BLI_math_base.h
index 2695fe1da2d..4ac966be83d 100644
--- a/source/blender/blenlib/BLI_math_base.h
+++ b/source/blender/blenlib/BLI_math_base.h
@@ -139,6 +139,7 @@ MINLINE float clamp_f(float value, float min, float max);
MINLINE size_t clamp_z(size_t value, size_t min, size_t max);
MINLINE int compare_ff(float a, float b, const float max_diff);
+MINLINE int compare_dd(double a, double b, const double max_diff);
MINLINE int compare_ff_relative(float a, float b, const float max_diff, const int max_ulps);
MINLINE float signf(float f);
diff --git a/source/blender/blenlib/BLI_math_vector.h b/source/blender/blenlib/BLI_math_vector.h
index aa3c7194d36..af732dccb61 100644
--- a/source/blender/blenlib/BLI_math_vector.h
+++ b/source/blender/blenlib/BLI_math_vector.h
@@ -341,6 +341,9 @@ MINLINE bool compare_v2v2(const float a[2],
MINLINE bool compare_v3v3(const float a[3],
const float b[3],
const float limit) ATTR_WARN_UNUSED_RESULT;
+MINLINE bool compare_v3v3_db(const double a[3],
+ const double b[3],
+ const double limit) ATTR_WARN_UNUSED_RESULT;
MINLINE bool compare_v4v4(const float a[4],
const float b[4],
const float limit) ATTR_WARN_UNUSED_RESULT;
diff --git a/source/blender/blenlib/intern/math_base_inline.c b/source/blender/blenlib/intern/math_base_inline.c
index 47327a878d4..6863d9225bc 100644
--- a/source/blender/blenlib/intern/math_base_inline.c
+++ b/source/blender/blenlib/intern/math_base_inline.c
@@ -447,6 +447,11 @@ MINLINE int compare_ff(float a, float b, const float max_diff)
return fabsf(a - b) <= max_diff;
}
+MINLINE int compare_dd(double a, double b, const double max_diff)
+{
+ return fabs(a - b) <= max_diff;
+}
+
/**
* Almost-equal for IEEE floats, using their integer representation
* (mixing ULP and absolute difference methods).
diff --git a/source/blender/blenlib/intern/math_vector_inline.c b/source/blender/blenlib/intern/math_vector_inline.c
index 44d92f03ad8..a543b42b1bd 100644
--- a/source/blender/blenlib/intern/math_vector_inline.c
+++ b/source/blender/blenlib/intern/math_vector_inline.c
@@ -1297,6 +1297,12 @@ MINLINE bool compare_v3v3(const float v1[3], const float v2[3], const float limi
compare_ff(v1[2], v2[2], limit));
}
+MINLINE bool compare_v3v3_db(const double v1[3], const double v2[3], const double limit)
+{
+ return (compare_dd(v1[0], v2[0], limit) && compare_dd(v1[1], v2[1], limit) &&
+ compare_dd(v1[2], v2[2], limit));
+}
+
MINLINE bool compare_v4v4(const float v1[4], const float v2[4], const float limit)
{
return (compare_ff(v1[0], v2[0], limit) && compare_ff(v1[1], v2[1], limit) &&
diff --git a/source/blender/bmesh/tools/bmesh_boolean.c b/source/blender/bmesh/tools/bmesh_boolean.c
index 1b16bf62b89..289ef499d8c 100644
--- a/source/blender/bmesh/tools/bmesh_boolean.c
+++ b/source/blender/bmesh/tools/bmesh_boolean.c
@@ -65,9 +65,12 @@ typedef struct IMesh {
struct Mesh *me;
} IMesh;
-/* A MeshPart is a subset of the geometry of an IndexMesh.
+/* 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 (which will be known by context).
+ * 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,
@@ -75,12 +78,16 @@ typedef struct IMesh {
* 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) */
+ 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. */
+ IMesh *im; /* The underlying IMesh */
+ LinkNode *im_verts; /* Links are ints (vert indices in im). */
+ LinkNode *im_edges; /* Links are ints (edge indices in im). */
+ LinkNode *im_faces; /* Links are ints (face indices in im). */
+ LinkNode *new_verts; /* Links are pointers to float[3]. */
+ LinkNode *new_edges; /* Links are pointer to IntPair. */
+ LinkNode *new_faces; /* Links are pointers to list of int. */
} MeshPart;
/* A MeshPartSet set is a set of MeshParts.
@@ -225,6 +232,16 @@ static int imesh_totvert(const IMesh *im)
}
}
+static int imesh_totedge(const IMesh *im)
+{
+ if (im->bm) {
+ return im->bm->totedge;
+ }
+ else {
+ return 0; /* TODO */
+ }
+}
+
static int imesh_totface(const IMesh *im)
{
if (im->bm) {
@@ -251,7 +268,7 @@ static int imesh_facelen(const IMesh *im, int f)
return ans;
}
-static int imesh_face_vert(IMesh *im, int f, int index)
+static int imesh_face_vert(const IMesh *im, int f, int index)
{
int i;
int ans = -1;
@@ -290,6 +307,23 @@ static void imesh_get_vert_co(const IMesh *im, int v, float *r_coords)
}
}
+static void imesh_get_vert_co_db(const IMesh *im, int v, double *r_coords)
+{
+ if (im->bm) {
+ BMVert *bmv = BM_vert_at_index(im->bm, v);
+ if (bmv) {
+ copy_v3db_v3fl(r_coords, bmv->co);
+ return;
+ }
+ else {
+ zero_v3_db(r_coords);
+ }
+ }
+ else {
+ ; /* TODO */
+ }
+}
+
static void imesh_get_face_plane(const IMesh *im, int f, double r_plane[4])
{
double plane_co[3];
@@ -507,14 +541,10 @@ static void calc_partset_bb_eps(BoolState *bs, MeshPartSet *partset, double eps)
/** MeshPart functions. */
-static void init_meshpart(MeshPart *part)
+static void init_meshpart(BoolState *bs, MeshPart *part)
{
- zero_v4_db(part->plane);
- zero_v3_db(part->bbmin);
- zero_v3_db(part->bbmax);
- part->verts = NULL;
- part->edges = NULL;
- part->faces = NULL;
+ memset(part, 0, sizeof(*part));
+ part->im = &bs->im;
}
static MeshPart *copy_part(BoolState *bs, const MeshPart *part)
@@ -527,25 +557,76 @@ static MeshPart *copy_part(BoolState *bs, const MeshPart *part)
copy_v3_v3_db(copy->bbmin, part->bbmin);
copy_v3_v3_db(copy->bbmax, part->bbmax);
- /* All links in lists are ints, so can use shallow copy. */
- copy->verts = linklist_shallow_copy_arena(part->verts, arena);
- copy->edges = linklist_shallow_copy_arena(part->edges, arena);
- copy->faces = linklist_shallow_copy_arena(part->faces, arena);
+ copy->im = part->im;
+
+ /* All links in lists are ints, or can be shared, so can use shallow copy. */
+ copy->im_verts = linklist_shallow_copy_arena(part->im_verts, arena);
+ copy->im_edges = linklist_shallow_copy_arena(part->im_edges, arena);
+ copy->im_faces = linklist_shallow_copy_arena(part->im_faces, arena);
+ copy->new_verts = linklist_shallow_copy_arena(part->new_verts, arena);
+ copy->new_edges = linklist_shallow_copy_arena(part->new_edges, arena);
+ copy->new_faces = linklist_shallow_copy_arena(part->new_faces, arena);
return copy;
}
+static int part_totvert(const MeshPart *part)
+{
+ return BLI_linklist_count(part->im_verts) + BLI_linklist_count(part->new_verts);
+}
+
+static int part_totedge(const MeshPart *part)
+{
+ return BLI_linklist_count(part->im_edges) + BLI_linklist_count(part->new_edges);
+}
+
static int part_totface(const MeshPart *part)
{
- return BLI_linklist_count(part->faces);
+ return BLI_linklist_count(part->im_faces) + BLI_linklist_count(part->new_faces);
}
+/*
+ * Return the index in MeshPart space of the index'th face in part.
+ * "MeshPart space" means that if the f returned is in the range of
+ * face indices in the underlying IMesh, then it represents the face
+ * in the IMesh. If f is greater than or equal to that, then it represents
+ * the face that is (f - im's totf)th in the new_faces list.
+ */
static int part_face(const MeshPart *part, int index)
{
- LinkNode *ln = BLI_linklist_find(part->faces, index);
+ LinkNode *ln;
+
+ ln = BLI_linklist_find(part->im_faces, index);
if (ln) {
return POINTER_AS_INT(ln->link);
}
- return -1;
+ index -= BLI_linklist_count(part->im_faces);
+ return imesh_totface(part->im) + index;
+}
+
+/* Like part_face, but for vertices. */
+static int part_vert(const MeshPart *part, int index)
+{
+ LinkNode *ln;
+
+ ln = BLI_linklist_find(part->im_verts, index);
+ if (ln) {
+ return POINTER_AS_INT(ln->link);
+ }
+ index -= BLI_linklist_count(part->im_verts);
+ return imesh_totvert(part->im) + index;
+}
+
+/* Like part_face, but for edges. */
+static int part_edge(const MeshPart *part, int index)
+{
+ LinkNode *ln;
+
+ ln = BLI_linklist_find(part->im_edges, index);
+ if (ln) {
+ return POINTER_AS_INT(ln->link);
+ }
+ index -= BLI_linklist_count(part->im_edges);
+ return imesh_totedge(part->im) + index;
}
/* Fill part->bbmin and part->bbmax with the axis-aligned bounding box
@@ -558,23 +639,18 @@ static void calc_part_bb_eps(BoolState *bs, MeshPart *part, double eps)
LinkNode *ln;
int v, e, f, i, flen, j;
- if (part->verts == NULL && part->edges == NULL && part->faces == NULL) {
- zero_v3_db(part->bbmin);
- zero_v3_db(part->bbmax);
- return;
- }
- copy_v3_db(part->bbmin, FLT_MAX);
- copy_v3_db(part->bbmax, -FLT_MAX);
- for (ln = part->verts; ln; ln = ln->next) {
+ copy_v3_db(part->bbmin, DBL_MAX);
+ copy_v3_db(part->bbmax, -DBL_MAX);
+ for (ln = part->im_verts; ln; ln = ln->next) {
v = POINTER_AS_INT(ln->link);
bb_update(part->bbmin, part->bbmax, v, im);
}
- for (ln = part->edges; ln; ln = ln->next) {
+ for (ln = part->im_edges; ln; ln = ln->next) {
e = POINTER_AS_INT(ln->link);
/* TODO: handle edge verts */
printf("calc_part_bb_eps plea
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list