[Bf-blender-cvs] [c58ce6b] bmesh-boolean-experiment: Use modified approach for selecting vertices to connect islands
Campbell Barton
noreply at git.blender.org
Thu Dec 10 09:48:43 CET 2015
Commit: c58ce6b70ceaad1c3a08d242a2484ec1bc475a94
Author: Campbell Barton
Date: Thu Dec 10 19:28:13 2015 +1100
Branches: bmesh-boolean-experiment
https://developer.blender.org/rBc58ce6b70ceaad1c3a08d242a2484ec1bc475a94
Use modified approach for selecting vertices to connect islands
Cast 2d rays instead of using a kdtree.
This is mostly finished now, just need to improve memory handling and minor cleanup.
===================================================================
M source/blender/bmesh/intern/bmesh_polygon_edgenet.c
===================================================================
diff --git a/source/blender/bmesh/intern/bmesh_polygon_edgenet.c b/source/blender/bmesh/intern/bmesh_polygon_edgenet.c
index 6df89ec..729b0b3 100644
--- a/source/blender/bmesh/intern/bmesh_polygon_edgenet.c
+++ b/source/blender/bmesh/intern/bmesh_polygon_edgenet.c
@@ -35,7 +35,6 @@
#include "BLI_linklist_stack.h"
#include "BLI_sort.h"
#include "BLI_sort_utils.h"
-#include "BLI_kdtree.h"
#include "BLI_kdopbvh.h"
#include "BKE_customdata.h"
@@ -599,25 +598,43 @@ bool BM_face_split_edgenet(
*
* \{ */
-/* Check new links intersect any existing edges
- * in fact for *many* cases this isn't needed at all, however its needed to guarantee non overlapping output. */
-#define USE_ISECT_TEST
-#ifdef USE_ISECT_TEST
-# define USE_ISECT_BVH
-#endif
-
-#ifdef USE_ISECT_TEST
#define VERT_IS_VALID BM_ELEM_INTERNAL_TAG
-#endif
/* can be X or Y */
-#define SORT_AXIS 1
+#define SORT_AXIS 0
+
-BLI_INLINE bool edge_isect_verts_check_2d(
- const BMEdge *e, const BMVert *v_a, const BMVert *v_b)
+/* todo, make a version that doesnt use line intersection and calculates the values directly */
+static bool isect_ray_seg_v2(
+ const float p1[3], const float d[3],
+ const float v0[3], const float v1[3],
+ float *r_lambda, float *r_u)
{
- return ((isect_seg_seg_v2_simple(v_a->co, v_b->co, e->v1->co, e->v2->co) == true) &&
- ((e->v1 != v_a) && (e->v2 != v_a) && (e->v1 != v_b) && (e->v2 != v_b)));
+ float v0_local[2], v1_local[2];
+ sub_v2_v2v2(v0_local, v0, p1);
+ sub_v2_v2v2(v1_local, v1, p1);
+
+ float zero[2] = {0};
+
+ float co_isect[2];
+ if (isect_line_line_v2_point(zero, d, v0_local, v1_local, co_isect) == ISECT_LINE_LINE_CROSS) {
+ const float t = dot_v2v2(d, co_isect);
+ if (t >= 0.0f) {
+ const float u = line_point_factor_v2(co_isect, v0_local, v1_local);
+ if (u >= 0.0 && u <= 1.0f) {
+ if (r_lambda) {
+ *r_lambda = t;
+ }
+
+ if (r_u) {
+ *r_u = u;
+ }
+
+ return true;
+ }
+ }
+ }
+ return false;
}
BLI_INLINE bool edge_isect_verts_point_2d(
@@ -662,88 +679,72 @@ static int group_min_cmp_fn(const void *p1, const void *p2)
else return 0;
}
-struct EdgeGroupIsland_KDTreeTest {
- unsigned int vert_range[2];
- BMVert **vert_arr;
-
- /* for each search */
- struct {
- float value;
-#ifdef USE_ISECT_TEST
- const BMEdge *e_lasthit;
- const BMVert *v_origin;
-#endif
- } search;
-};
+struct Edges_VertVert_BVHTreeTest {
+ float dist_orig;
+ BMEdge **edge_arr;
-#ifdef USE_ISECT_TEST
-BLI_INLINE bool kdtree_edge_isect_cb_test(struct EdgeGroupIsland_KDTreeTest *island_test, int index)
-{
- return ((BM_elem_flag_test(island_test->vert_arr[index], VERT_IS_VALID)) &&
- ((island_test->search.e_lasthit == NULL) ||
- /* avoid re-selecting points which */
- edge_isect_verts_check_2d(
- island_test->search.e_lasthit,
- island_test->search.v_origin, island_test->vert_arr[index]) == false)
- );
-}
-#endif
+ BMVert *v_origin;
+ BMVert *v_other;
-static int kdtree_find_exclude_range_prev_cb(void *user_data, int index, const float co[3], float dist_sq)
-{
- UNUSED_VARS(co, dist_sq);
- struct EdgeGroupIsland_KDTreeTest *island_test = user_data;
- return ((index < (int)island_test->vert_range[0] || index >= (int)island_test->vert_range[1]) &&
- /* allow equality to support degenerate cases (when they're equal) */
- (island_test->vert_arr[index]->co[SORT_AXIS] <= island_test->search.value)
-#ifdef USE_ISECT_TEST
- &&
- kdtree_edge_isect_cb_test(island_test, index)
-#endif
- );
-}
+ const unsigned int *vert_range;
+};
-static int kdtree_find_exclude_range_next_cb(void *user_data, int index, const float co[3], float dist_sq)
-{
- UNUSED_VARS(co, dist_sq);
- struct EdgeGroupIsland_KDTreeTest *island_test = user_data;
- return ((index < (int)island_test->vert_range[0] || index >= (int)island_test->vert_range[1]) &&
- /* allow equality to support degenerate cases (when they're equal) */
- (island_test->vert_arr[index]->co[SORT_AXIS] >= island_test->search.value)
-#ifdef USE_ISECT_TEST
- &&
- kdtree_edge_isect_cb_test(island_test, index)
-#endif
- );
-}
+struct Edges_VertRay_BVHTreeTest {
+ BMEdge **edge_arr;
-#ifdef USE_ISECT_TEST
+ BMVert *v_origin;
-#ifdef USE_ISECT_BVH
-struct Edges_BVHTreeTest {
- float dist_orig;
- BMEdge **edge_arr;
- BMVert *v_origin, *v_other;
+ const unsigned int *vert_range;
};
-static void bvhtree_test_edges_isect_2d_cb(
+static void bvhtree_test_edges_isect_2d_vert_cb(
void *user_data, int index, const BVHTreeRay *UNUSED(ray), BVHTreeRayHit *hit)
{
- struct Edges_BVHTreeTest *data = user_data;
- float isect[2];
+ struct Edges_VertVert_BVHTreeTest *data = user_data;
+ const BMEdge *e = data->edge_arr[index];
+ const int v1_index = BM_elem_index_get(e->v1);
+ float co_isect[2];
- if (edge_isect_verts_point_2d(data->edge_arr[index], data->v_origin, data->v_other, isect)) {
- const float t = line_point_factor_v2(isect, data->v_origin->co, data->v_other->co);
+ if (edge_isect_verts_point_2d(e, data->v_origin, data->v_other, co_isect)) {
+ const float t = line_point_factor_v2(co_isect, data->v_origin->co, data->v_other->co);
const float dist_new = data->dist_orig * t;
/* avoid float precision issues, possible this is greater */
if (LIKELY(dist_new < hit->dist)) {
- hit->dist = dist_new;
- hit->index = index;
- printf("We found hit\n!");
+ /* v1/v2 will both be in the same group */
+ if (v1_index < (int)data->vert_range[0] ||
+ v1_index >= (int)data->vert_range[1])
+ {
+ hit->dist = dist_new;
+ hit->index = index;
+ }
+ }
+ }
+}
+
+static void bvhtree_test_edges_isect_2d_ray_cb(
+ void *user_data, int index, const BVHTreeRay *ray, BVHTreeRayHit *hit)
+{
+ struct Edges_VertRay_BVHTreeTest *data = user_data;
+ const BMEdge *e = data->edge_arr[index];
+
+ /* direction is normalized, so this will be the distance */
+ float dist_new;
+ if (isect_ray_seg_v2(data->v_origin->co, ray->direction, e->v1->co, e->v2->co, &dist_new, NULL)) {
+ /* avoid float precision issues, possible this is greater */
+ if (LIKELY(dist_new < hit->dist)) {
+ if (e->v1 != data->v_origin && e->v2 != data->v_origin) {
+ const int v1_index = BM_elem_index_get(e->v1);
+ /* v1/v2 will both be in the same group */
+ if (v1_index < (int)data->vert_range[0] ||
+ v1_index >= (int)data->vert_range[1])
+ {
+ hit->dist = dist_new;
+ hit->index = index;
+ }
+ }
}
}
}
-#endif /* USE_ISECT_BVH */
/**
* Store values for:
@@ -751,28 +752,23 @@ static void bvhtree_test_edges_isect_2d_cb(
* - #test_edges_isect_2d
* ... which don't change each call.
*/
-struct FindConnectionArgs {
- const KDTree *kdtree;
-#ifdef USE_ISECT_BVH
+struct EdgeGroup_FindConnection_Args {
BVHTree *bvhtree;
-#endif
- struct EdgeGroupIsland_KDTreeTest *island_test;
BMEdge **edge_arr;
unsigned int edge_arr_len;
-#ifdef USE_ISECT_TEST
BMEdge **edge_arr_new;
unsigned int edge_arr_new_len;
-#endif
+
+ const unsigned int *vert_range;
};
-static int test_edges_isect_2d(
- const struct FindConnectionArgs *args,
- BMVert *v_origin, BMVert *v_other,
- bool *r_is_connection)
+static BMEdge *test_edges_isect_2d_vert(
+ const struct EdgeGroup_FindConnection_Args *args,
+ BMVert *v_origin, BMVert *v_other)
{
int index;
-#ifdef USE_ISECT_BVH
+
BVHTreeRayHit hit = {0};
float dir[3];
@@ -781,113 +777,168 @@ static int test_edges_isect_2d(
hit.index = -1;
hit.dist = normalize_v2(dir);
- struct Edges_BVHTreeTest user_data = {0};
+ struct Edges_VertVert_BVHTreeTest user_data = {0};
user_data.dist_orig = hit.dist;
user_data.edge_arr = args->edge_arr;
user_data.v_origin = v_origin;
user_data.v_other = v_other;
+ user_data.vert_range = args->vert_range;
- index = BLI_bvhtree_ray_cast(
+ index = BLI_bvhtree_ray_cast_ex(
args->bvhtree, v_origin->co, dir, 0.0f, &hit,
- bvhtree_test_edges_isect_2d_cb, &user_data);
-#else
- index = -1;
- for (unsigned int i = 0; i < args->edge_arr_len; i++) {
- if (UNLIKELY(edge_isect_verts_check_2d(args->edge_arr[i], v_origin, v_other))) {
- index = (int)i;
- break;
+ bvhtree_test_edges_isect_2d_vert_cb, &user_data, 0);
+
+ BMEdge *e_hit = (index != -1) ? args->edge_arr[index] : NULL;
+
+ /* first check existing connections (no spatial optimization here since we're continually adding). */
+ if (LIKELY(index == -1)) {
+ float t_best = 1.0f;
+ for (unsigned int i = 0; i < args->edge_arr_new_len; i++) {
+ float co_isect[2];
+ if (UNLIKELY(edge_isect_verts_point_2d(args->edge_arr_new[i], v_origin, v_other, co_isect))) {
+ const float t_test = line_point_factor_v2(co_isect, v_origin->co, v_other->co);
+ if (t_test < t_best) {
+ t_best = t_test;
+
+ e_hit = args->edge_arr_new[i];
+ }
+ }
}
}
-#endif
- *r_is_connection = false;
+ return e_hit;
+}
+
+/**
+ * Similar to #test_edges_isect_2d_vert but we're casting into a direction,
+ * (not to a vertex)
+ */
+static BMEdge *test_edges_isect_2d_ray(
+ const struct EdgeGroup_FindConnection_Args *args,
+ BMVert *v_origin, const float dir[3])
+{
+ int index;
+ BVHTreeRayHit hit = {0};
+
+ BLI_ASSERT_UNIT_V2(dir);
+
+ hit.index = -1;
+ hit.dist = FLT_MAX;
+
+ struct Edges_VertRay_BVHTreeTest user_data = {0};
+ user_data.edge_arr = args->edge_arr;
+ user_data.v_origin = v_origin;
+ user_data.vert_range = args->vert_range;
+
+ index = BLI_bvhtree_ray_cast_ex(
+ args->bvhtree, v_origin->co, dir, 0.0f, &hit,
+ bvhtree_test_edges_isect_2d_ray_cb, &user_data, 0);
+
+ BMEdge *e_hit = (index != -1) ? args->edge_arr[index] : NULL;
/* first check existing connections (no spatial optimization here since we're continually adding). */
- if (index == -1) {
+ if (LIKELY(index != -1)) {
for (unsigned int i = 0; i < args->edge_arr_new_len; i++) {
- if (UNLIKELY(edge_isect_verts_check_2d(args->edge_arr_new[i], v_origin, v_other))) {
- index = (int)i;
- *r_is_connection = true;
- break;
+ BMEdge *e = args->edge_arr_new[i];
+ float dist_new;
+ if (isect_ray_seg_v2(v_orig
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list