[Bf-blender-cvs] [e6d947f] master: BMesh Intersect: use flags to keep track of verts
Campbell Barton
noreply at git.blender.org
Wed Jun 29 08:15:35 CEST 2016
Commit: e6d947f037d341fc1f84fb422b2cada8bd6f5d0a
Author: Campbell Barton
Date: Wed Jun 29 16:09:58 2016 +1000
Branches: master
https://developer.blender.org/rBe6d947f037d341fc1f84fb422b2cada8bd6f5d0a
BMesh Intersect: use flags to keep track of verts
For simple cases bitmasks were OK, but didnt work for vert/edge, vert/edge tests.
Tag verts instead, makes logic easier to follow and gives minor speedup.
===================================================================
M source/blender/bmesh/intern/bmesh_private.h
M source/blender/bmesh/tools/bmesh_intersect.c
===================================================================
diff --git a/source/blender/bmesh/intern/bmesh_private.h b/source/blender/bmesh/intern/bmesh_private.h
index 9b3a147..d8d297c 100644
--- a/source/blender/bmesh/intern/bmesh_private.h
+++ b/source/blender/bmesh/intern/bmesh_private.h
@@ -67,12 +67,13 @@ enum {
_FLAG_MV = (1 << 1), /* make face, vertex */
_FLAG_OVERLAP = (1 << 2), /* general overlap flag */
_FLAG_WALK = (1 << 3), /* general walk flag (keep clean) */
+ _FLAG_WALK_ALT = (1 << 4), /* same as _FLAG_WALK, for when a second tag is needed */
_FLAG_ELEM_CHECK = (1 << 7), /* reserved for bmesh_elem_check */
};
#define BM_ELEM_API_FLAG_ENABLE(element, f) { ((element)->head.api_flag |= (f)); } (void)0
-#define BM_ELEM_API_FLAG_DISABLE(element, f) { ((element)->head.api_flag &= ~(f)); } (void)0
+#define BM_ELEM_API_FLAG_DISABLE(element, f) { ((element)->head.api_flag &= (unsigned char)~(f)); } (void)0
#define BM_ELEM_API_FLAG_TEST(element, f) ((element)->head.api_flag & (f))
#define BM_ELEM_API_FLAG_CLEAR(element) { ((element)->head.api_flag = 0); } (void)0
diff --git a/source/blender/bmesh/tools/bmesh_intersect.c b/source/blender/bmesh/tools/bmesh_intersect.c
index bd6a68f..58234dd 100644
--- a/source/blender/bmesh/tools/bmesh_intersect.c
+++ b/source/blender/bmesh/tools/bmesh_intersect.c
@@ -53,6 +53,8 @@
#include "BLI_buffer.h"
#include "bmesh.h"
+#include "intern/bmesh_private.h"
+
#include "bmesh_intersect.h" /* own include */
#include "tools/bmesh_edgesplit.h"
@@ -87,18 +89,6 @@
// #define USE_DUMP
-/* use only for small arrays */
-BLI_INLINE bool array_contains_pointer(const void **arr, unsigned int arr_len, const void *item)
-{
- BLI_assert(arr_len < 3);
- for (unsigned int i = 0; i < arr_len; i++) {
- if (arr[i] == item) {
- return true;
- }
- }
- return false;
-}
-
static void tri_v3_scale(
float v1[3], float v2[3], float v3[3],
const float t)
@@ -547,9 +537,6 @@ static void bm_isect_tri_tri(
const float *f_b_cos[3] = {UNPACK3_EX(, fv_b, ->co)};
float f_a_nor[3];
float f_b_nor[3];
- /* track vertices which have been added to 'iv_ls_a' & 'iv_ls_b' */
- int a_mask = 0;
- int b_mask = 0;
unsigned int i;
@@ -569,24 +556,22 @@ static void bm_isect_tri_tri(
STACK_INIT(iv_ls_a, ARRAY_SIZE(iv_ls_a));
STACK_INIT(iv_ls_b, ARRAY_SIZE(iv_ls_b));
- /* don't test, but we must be sure not to add doubles (assert instead). */
-#ifndef NDEBUG
-# define STACK_PUSH_NOTEST(arr, ele) \
- { \
- BLI_assert(BLI_array_findindex(arr, STACK_SIZE(arr), &(ele)) == -1); \
- STACK_PUSH(arr, ele); \
+#define VERT_VISIT_A _FLAG_WALK
+#define VERT_VISIT_B _FLAG_WALK_ALT
+
+#define STACK_PUSH_TEST_A(ele) \
+ if (BM_ELEM_API_FLAG_TEST(ele, VERT_VISIT_A) == 0) { \
+ BM_ELEM_API_FLAG_ENABLE(ele, VERT_VISIT_A); \
+ STACK_PUSH(iv_ls_a, ele); \
} ((void)0)
-#else
-# define STACK_PUSH_NOTEST STACK_PUSH
-#endif
- /* warning, this seems like it might be inefficent,
- * however there will be <3 items in this case. */
-# define STACK_PUSH_TEST(arr, ele, arr_offset) \
- if (!array_contains_pointer((const void **)(&(arr)[arr_offset]), STACK_SIZE(arr) - (arr_offset), (void *)ele)) { \
- STACK_PUSH(arr, ele); \
+#define STACK_PUSH_TEST_B(ele) \
+ if (BM_ELEM_API_FLAG_TEST(ele, VERT_VISIT_B) == 0) { \
+ BM_ELEM_API_FLAG_ENABLE(ele, VERT_VISIT_B); \
+ STACK_PUSH(iv_ls_b, ele); \
} ((void)0)
+
/* vert-vert
* --------- */
{
@@ -598,22 +583,18 @@ static void bm_isect_tri_tri(
unsigned int i_b;
for (i_b = 0; i_b < 3; i_b++) {
if (len_squared_v3v3(fv_a[i_a]->co, fv_b[i_b]->co) <= s->epsilon.eps2x_sq) {
- if (!((1 << i_a) & a_mask)) {
- STACK_PUSH_NOTEST(iv_ls_a, fv_a[i_a]);
- a_mask |= (1 << i_a);
#ifdef USE_DUMP
+ if (BM_ELEM_API_FLAG_TEST(fv_a[i_a], VERT_VISIT) == 0) {
printf(" ('VERT-VERT-A') %d, %d),\n",
i_a, BM_elem_index_get(fv_a[i_a]));
-#endif
}
- if (!((1 << i_b) & b_mask)) {
- STACK_PUSH_NOTEST(iv_ls_b, fv_b[i_b]);
- b_mask |= (1 << i_b);
-#ifdef USE_DUMP
+ if (BM_ELEM_API_FLAG_TEST(fv_b[i_b], VERT_VISIT) == 0) {
printf(" ('VERT-VERT-B') %d, %d),\n",
i_b, BM_elem_index_get(fv_b[i_b]));
-#endif
}
+#endif
+ STACK_PUSH_TEST_A(fv_a[i_a]);
+ STACK_PUSH_TEST_B(fv_b[i_b]);
}
}
}
@@ -624,22 +605,25 @@ static void bm_isect_tri_tri(
{
unsigned int i_a;
for (i_a = 0; i_a < 3; i_a++) {
- if (!((1 << i_a) & a_mask)) {
+ if (BM_ELEM_API_FLAG_TEST(fv_a[i_a], VERT_VISIT_A) == 0) {
unsigned int i_b_e0;
for (i_b_e0 = 0; i_b_e0 < 3; i_b_e0++) {
unsigned int i_b_e1 = (i_b_e0 + 1) % 3;
- float fac;
- if (((1 << i_b_e0) | (1 << i_b_e1)) & b_mask)
+
+ if (BM_ELEM_API_FLAG_TEST(fv_b[i_b_e0], VERT_VISIT_B) ||
+ BM_ELEM_API_FLAG_TEST(fv_b[i_b_e1], VERT_VISIT_B))
+ {
continue;
- fac = line_point_factor_v3(fv_a[i_a]->co, fv_b[i_b_e0]->co, fv_b[i_b_e1]->co);
+ }
+
+ const float fac = line_point_factor_v3(fv_a[i_a]->co, fv_b[i_b_e0]->co, fv_b[i_b_e1]->co);
if ((fac > 0.0f - s->epsilon.eps) && (fac < 1.0f + s->epsilon.eps)) {
float ix[3];
interp_v3_v3v3(ix, fv_b[i_b_e0]->co, fv_b[i_b_e1]->co, fac);
if (len_squared_v3v3(ix, fv_a[i_a]->co) <= s->epsilon.eps2x_sq) {
BMEdge *e;
- STACK_PUSH_NOTEST(iv_ls_b, fv_a[i_a]);
- // STACK_PUSH_NOTEST(iv_ls_a, fv_a[i_a]);
- a_mask |= (1 << i_a);
+ STACK_PUSH_TEST_B(fv_a[i_a]);
+ // STACK_PUSH_TEST_A(fv_a[i_a]);
e = BM_edge_exists(fv_b[i_b_e0], fv_b[i_b_e1]);
#ifdef USE_DUMP
printf(" ('VERT-EDGE-A', %d, %d),\n",
@@ -662,22 +646,25 @@ static void bm_isect_tri_tri(
{
unsigned int i_b;
for (i_b = 0; i_b < 3; i_b++) {
- if (!((1 << i_b) & b_mask)) {
+ if (BM_ELEM_API_FLAG_TEST(fv_b[i_b], VERT_VISIT_B) == 0) {
unsigned int i_a_e0;
for (i_a_e0 = 0; i_a_e0 < 3; i_a_e0++) {
unsigned int i_a_e1 = (i_a_e0 + 1) % 3;
- float fac;
- if (((1 << i_a_e0) | (1 << i_a_e1)) & a_mask)
+
+ if (BM_ELEM_API_FLAG_TEST(fv_a[i_a_e0], VERT_VISIT_A) ||
+ BM_ELEM_API_FLAG_TEST(fv_a[i_a_e1], VERT_VISIT_A))
+ {
continue;
- fac = line_point_factor_v3(fv_b[i_b]->co, fv_a[i_a_e0]->co, fv_a[i_a_e1]->co);
+ }
+
+ const float fac = line_point_factor_v3(fv_b[i_b]->co, fv_a[i_a_e0]->co, fv_a[i_a_e1]->co);
if ((fac > 0.0f - s->epsilon.eps) && (fac < 1.0f + s->epsilon.eps)) {
float ix[3];
interp_v3_v3v3(ix, fv_a[i_a_e0]->co, fv_a[i_a_e1]->co, fac);
if (len_squared_v3v3(ix, fv_b[i_b]->co) <= s->epsilon.eps2x_sq) {
BMEdge *e;
- STACK_PUSH_NOTEST(iv_ls_a, fv_b[i_b]);
+ STACK_PUSH_TEST_A(fv_b[i_b]);
// STACK_PUSH_NOTEST(iv_ls_b, fv_b[i_b]);
- b_mask |= (1 << i_b);
e = BM_edge_exists(fv_a[i_a_e0], fv_a[i_a_e1]);
#ifdef USE_DUMP
printf(" ('VERT-EDGE-B', %d, %d),\n",
@@ -711,14 +698,15 @@ static void bm_isect_tri_tri(
// second check for verts intersecting the triangle
for (i_a = 0; i_a < 3; i_a++) {
- float ix[3];
- if ((1 << i_a) & a_mask)
+ if (BM_ELEM_API_FLAG_TEST(fv_a[i_a], VERT_VISIT_A)) {
continue;
+ }
+
+ float ix[3];
if (isect_point_tri_v3(fv_a[i_a]->co, UNPACK3(t_scale), ix)) {
if (len_squared_v3v3(ix, fv_a[i_a]->co) <= s->epsilon.eps2x_sq) {
- STACK_PUSH_NOTEST(iv_ls_a, fv_a[i_a]);
- STACK_PUSH_NOTEST(iv_ls_b, fv_a[i_a]);
- a_mask |= (1 << i_a);
+ STACK_PUSH_TEST_A(fv_a[i_a]);
+ STACK_PUSH_TEST_B(fv_a[i_a]);
#ifdef USE_DUMP
printf(" 'VERT TRI-A',\n");
#endif
@@ -737,15 +725,15 @@ static void bm_isect_tri_tri(
tri_v3_scale(UNPACK3(t_scale), 1.0f - s->epsilon.eps2x);
for (i_b = 0; i_b < 3; i_b++) {
- float ix[3];
- if ((1 << i_b) & b_mask)
+ if (BM_ELEM_API_FLAG_TEST(fv_b[i_b], VERT_VISIT_B)) {
continue;
+ }
+ float ix[3];
if (isect_point_tri_v3(fv_b[i_b]->co, UNPACK3(t_scale), ix)) {
if (len_squared_v3v3(ix, fv_b[i_b]->co) <= s->epsilon.eps2x_sq) {
- STACK_PUSH_NOTEST(iv_ls_a, fv_b[i_b]);
- STACK_PUSH_NOTEST(iv_ls_b, fv_b[i_b]);
- b_mask |= (1 << i_b);
+ STACK_PUSH_TEST_A(fv_b[i_b]);
+ STACK_PUSH_TEST_B(fv_b[i_b]);
#ifdef USE_DUMP
printf(" 'VERT TRI-B',\n");
#endif
@@ -760,7 +748,7 @@ static void bm_isect_tri_tri(
#ifdef USE_DUMP
printf("# OVERLAP\n");
#endif
- return;
+ goto finally;
}
normal_tri_v3(f_a_nor, UNPACK3(f_a_cos));
@@ -769,44 +757,42 @@ static void bm_isect_tri_tri(
/* edge-tri & edge-edge
* -------------------- */
{
- /**
- * Note that its possible to add the same vertex multiple times
- * with near degenerate faces (or a large epsilon).
- *
- * For this reason we have #STACK_PUSH_TEST macro which only adds vertices that aren't already added.
- * Since we know none of the vertices from #bm_isect_edge_tri, the check can be offset.
- */
-
- const unsigned int iv_ls_a_offset = STACK_SIZE(iv_ls_a);
- const unsigned int iv_ls_b_offset = STACK_SIZE(iv_ls_b);
-
- unsigned int i_e0;
- for (i_e0 = 0; i_e0 < 3; i_e0++) {
- unsigned int i_e1 = (i_e0 + 1) % 3;
+ for (unsigned int i_a_e0 = 0; i_a_e0 < 3; i_a_e0++) {
+ unsigned int i_a_e1 = (i_a_e0 + 1) % 3;
enum ISectType side;
BMVert *iv;
- if (((1 << i_e0) | (1 << i_e1)) & a_mask)
+
+ if (BM_ELEM_API_FLAG_TEST(fv_a[i_a_e0], VERT_VISIT_A) ||
+ BM_ELEM_API_FLAG_TEST(fv_a[i_a_e1], VERT_VISIT_A))
+ {
continue;
- iv = bm_isect_edge_tri(s, fv_a[i_e0], fv_a[i_e1], fv_b, b_index, f_b_cos, f_b_nor, &side);
+ }
+
+ iv = bm_isect_edge_tri(s, fv_a[i_a_e0], fv_a[i_a_e1], fv_b, b_index, f_b_cos, f_b_nor, &side);
if (iv) {
- STACK_PUSH_TEST(iv_ls_a, iv, iv_ls_a_offset);
- STACK_PUSH_TEST(iv_ls_b, iv, iv_ls_b_offset);
+ STACK_PUSH_TEST_A(iv);
+ STACK_PUSH_TEST_B(iv);
#ifdef USE_DUMP
printf(" ('EDGE-TRI-A', %d),\n", side);
#endif
}
}
- for (i_e0 = 0; i_e0 < 3; i_e0++) {
- unsigned int i_e1 = (i_e0 + 1) % 3;
+ for (unsigned int i_b_e0 = 0; i_b_e0 < 3; i_b_e0++) {
+ unsigned int i_b_e1 = (i_b_e0 + 1) % 3;
enum ISectType side;
BMVert *iv;
- if (((1 << i_e0) | (1 << i_e1)) & b_mask)
+
+ if (BM_ELEM_API_FLAG_TEST(fv_b[i_b_e0], VERT_VISIT
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list