Commit: c593855b29f7abd0c4f6e54a5b48900987738ee4
Author: Campbell Barton
Date: Fri Dec 11 11:47:54 2015 +1100
Branches: master
https://developer.blender.org/rBc593855b29f7abd0c4f6e54a5b48900987738ee4
BMesh: hole support for intersect tool
Support cutting many outlines into a single face (creating edges between
isolated regions).
===================================================================
M source/blender/bmesh/intern/bmesh_polygon_edgenet.c
M source/blender/bmesh/intern/bmesh_polygon_edgenet.h
M source/blender/bmesh/tools/bmesh_intersect.c
M source/blender/bmesh/tools/bmesh_intersect.h
M source/blender/editors/mesh/editmesh_intersect.c
===================================================================
diff --git a/source/blender/bmesh/intern/bmesh_polygon_edgenet.c
b/source/blender/bmesh/intern/bmesh_polygon_edgenet.c
index 1241614..3d54db1 100644
--- a/source/blender/bmesh/intern/bmesh_polygon_edgenet.c
+++ b/source/blender/bmesh/intern/bmesh_polygon_edgenet.c
@@ -29,11 +29,14 @@
#include "MEM_guardedalloc.h"
#include "BLI_math.h"
+#include "BLI_memarena.h"
#include "BLI_array.h"
#include "BLI_alloca.h"
#include "BLI_stackdefines.h"
#include "BLI_linklist_stack.h"
+#include "BLI_sort.h"
#include "BLI_sort_utils.h"
+#include "BLI_kdopbvh.h"
#include "BKE_customdata.h"
@@ -580,3 +583,652 @@ bool BM_face_split_edgenet(
#undef EDGE_NET
/** \} */
+
+
+/* -------------------------------------------------------------------- */
+/* Face Split Edge-Net Connect Islands */
+
+/** \name BM_face_split_edgenet_connect_islands and helper functions.
+ *
+ * Connect isolated mesh 'islands' so they form legal regions from which we
can create faces.
+ *
+ * Intended to be used as a pre-processing step for #BM_face_split_edgenet.
+ *
+ * \warning Currently this risks running out of stack memory (#alloca),
+ * likely we'll pass in a memory arena (cleared each use) eventually.
+ *
+ * \{ */
+
+#define VERT_IS_VALID BM_ELEM_INTERNAL_TAG
+
+/* can be X or Y */
+#define SORT_AXIS 0
+
+BLI_INLINE bool edge_isect_verts_point_2d(
+ const BMEdge *e, const BMVert *v_a, const BMVert *v_b,
+ float r_isect[2])
+{
+ return ((isect_seg_seg_v2_point(v_a->co, v_b->co, e->v1->co, e->v2->co,
r_isect) == 1) &&
+ ((e->v1 != v_a) && (e->v2 != v_a) && (e->v1 != v_b) && (e->v2
!= v_b)));
+}
+
+/**
+ * Represents isolated edge-links,
+ * each island owns contiguous slices of the vert array.
+ * (edges remain in `edge_links`).
+ */
+struct EdgeGroupIsland {
+ LinkNode edge_links; /* keep first */
+ unsigned int vert_len, edge_len;
+
+ /* Set the following vars once we have >1 groups */
+
+ /* when when an edge in a previous group connects to this one,
+ * so theres no need to create one pointing back. */
+ unsigned int has_prev_edge : 1;
+
+ /* verts in the group which has the lowest & highest values,
+ * the lower vertex is connected to the first edge */
+ struct {
+ BMVert *min, *max;
+ } vert_span;
+};
+
+static int group_min_cmp_fn(const void *p1, const void *p2)
+{
+ const struct EdgeGroupIsland *g1 = *(struct EdgeGroupIsland **)p1;
+ const struct EdgeGroupIsland *g2 = *(struct EdgeGroupIsland **)p2;
+ const float f1 = g1->vert_span.min->co[SORT_AXIS];
+ const float f2 = g2->vert_span.min->co[SORT_AXIS];
+
+ if (f1 < f2) return -1;
+ if (f1 > f2) return 1;
+ else return 0;
+}
+
+struct Edges_VertVert_BVHTreeTest {
+ float dist_orig;
+ BMEdge **edge_arr;
+
+ BMVert *v_origin;
+ BMVert *v_other;
+
+ const unsigned int *vert_range;
+};
+
+struct Edges_VertRay_BVHTreeTest {
+ BMEdge **edge_arr;
+
+ BMVert *v_origin;
+
+ const unsigned int *vert_range;
+};
+
+static void bvhtree_test_edges_isect_2d_vert_cb(
+ void *user_data, int index, const BVHTreeRay *UNUSED(ray),
BVHTreeRayHit *hit)
+{
+ 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(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)) {
+ /* 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;
+ }
+ }
+ }
+ }
+}
+
+/**
+ * Store values for:
+ * - #bm_face_split_edgenet_find_connection
+ * - #test_edges_isect_2d
+ * ... which don't change each call.
+ */
+struct EdgeGroup_FindConnection_Args {
+ BVHTree *bvhtree;
+ BMEdge **edge_arr;
+ unsigned int edge_arr_len;
+
+ BMEdge **edge_arr_new;
+ unsigned int edge_arr_new_len;
+
+ const unsigned int *vert_range;
+};
+
+static BMEdge *test_edges_isect_2d_vert(
+ const struct EdgeGroup_FindConnection_Args *args,
+ BMVert *v_origin, BMVert *v_other)
+{
+ int index;
+
+ BVHTreeRayHit hit = {0};
+ float dir[3];
+
+ sub_v2_v2v2(dir, v_other->co, v_origin->co);
+ dir[2] = 0.0f;
+ hit.index = -1;
+ hit.dist = normalize_v2(dir);
+
+ 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_ex(
+ args->bvhtree, v_origin->co, dir, 0.0f, &hit,
+ bvhtree_test_edges_isect_2d_vert_cb, &user_data, 0);
+
+ BMEdge *e_hit = (index != -1) ? args->edge_arr[index] : NULL;
+
+ /* 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];
+ }
+ }
+ }
+ }
+
+ 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;
+
+ /* check existing connections (no spatial optimization here since we're
continually adding). */
+ if (LIKELY(index != -1)) {
+ for (unsigned int i = 0; i < args->edge_arr_new_len; i++) {
+ BMEdge *e = args->edge_arr_new[i];
+ float dist_new;
+ if (isect_ray_seg_v2(v_origin->co, dir, e->v1->co,
e->v2->co, &dist_new, NULL)) {
+ if (e->v1 != v_origin && e->v2 != v_origin) {
+ /* avoid float precision issues,
possible this is greater */
+ if (LIKELY(dist_new < hit.dist)) {
+ hit.dist = dist_new;
+
+ e_hit = args->edge_arr_new[i];
+ }
+ }
+ }
+ }
+ }
+
+ return e_hit;
+}
+
+static int bm_face_split_edgenet_find_connection(
+ const struct EdgeGroup_FindConnection_Args *args,
+ BMVert *v_origin,
+ /* false = negative, true = positive */
+ bool direction_sign)
+{
+ /**
+ * Method for finding connection is as follows:
+ *
+ * - Cast a ray along either the positive or negative directions.
+ * - Take the hit-edge, and cast rays to their vertices checking those
rays don't intersect a closer edge.
+ * - Keep taking the hit-edge and testing its verts until a vertex is
found which isn't blocked by an edge.
+ *
+ * \note It's possible none of the verts can be accessed (with
self-intersecting lines).
+ * In that case theres no right answer (without subdividing edges),
+ * so return a fall-back vertex in that case.
+ */
+
+ const float dir[3] = {[SORT_AXIS] = direction_sign ? 1.0 : -1.0f};
+ BMEdge *e_hit = test_edges_isect_2d_ray(args, v_origin, dir);
+ BMVert *v_other = NULL;
+
+ if (e_hit) {
+ BMVert *v_other_fallback = NULL;
+
+ BLI_SMALLSTACK_DECLARE(vert_search, BMVert *);
+
+ /* ensure we never add verts multiple times (not all that
likely - but possible) */
+ BLI_SMALLSTACK_DECLARE(vert_blacklist, BMVert *);
+
+ do {
+ BMVert *v_pair[2];
+ /* ensure the closest vertex is popped back off the
stack first */
+ if (len_squared_v2v2(v_origin->co, e_hit->v1->co) >
+ len_squared_v2v2(v_origin->co, e_hit->v2->co))
+ {
+ ARRAY_SET_ITEMS(v_pair, e_hit->v1, e_hit->v2);
+ }
+ else {
+ ARRAY_SET_ITEMS(v_pair, e_hit->v2, e_hit->v1);
+ }
+
+ for (int j = 0; j < 2; j++) {
+ BMVert *v_iter = v_pair[j];
+ if (BM_elem_flag_test(v_iter, VERT_IS_VALID)) {
+ if (direction_sign ?
(v_iter->co[SORT_AXIS] >= v_origin->co[SORT_AXIS]) :
+
(v_iter->co[SORT_AXIS] <= v_origin->co[SORT_AXIS]))
+ {
+
BLI_SMALLSTACK_PUSH(vert_search, v_iter);
+
BLI_SMALLSTACK_PUSH(vert_blacklist, v_iter);
+ BM_elem_flag_disable(v_iter,
VERT_IS_VALID);
+ }
+ }
+ }
+ v_other_fallback = v_other;
+
+ } while ((v_other = BLI_SMALLSTACK_POP(vert_search)) &&
+ (e_hit = test_edges_isect_2d_vert(args, v_origin,
v_other)));
+
+ if (v_other == NULL) {
+ printf("Using fallback\n");
+ v_other = v_other_fallback;
+ }
+
+ /* reset the blacklist flag, for future use */
+ BMVert *v;
+ while ((v = BLI_SMALLSTACK_POP(vert_blacklist))) {
+ BM_elem_flag_enable(v, VERT_IS_VALID);
+ }
+ }
+
+ /* if we reach this line, v_other is either the best vertex or its NULL
*/
+ return v_othe
@@ Diff output truncated at 10240 characters. @@
_______________________________________________
Bf-blender-cvs mailing list
[email protected]
http://lists.blender.org/mailman/listinfo/bf-blender-cvs
