blender
/
blender
129
398
Fork 572
Code Issues 6.2k Pull Requests 747 Projects 19 Wiki Activity

BMesh: New tool `BM_mesh_intersect_edges` 

Along with the new utility `BM_vert_weld_linked_wire_edges_into_linked_faces`
This commit is contained in:
Germano Cavalcante 2019-09-12 13:28:53 -03:00
parent f9ef59ccc8
commit ca5e1615a1
5 changed files with 972 additions and 8 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

8
source/blender/blenlib/BLI_math_geom.h
View File

@ -311,7 +311,13 @@ bool isect_line_line_strict_v3(const float v1[3],
const float v4[3],
float vi[3],
float *r_lambda);
bool isect_ray_ray_epsilon_v3(const float ray_origin_a[3],
const float ray_direction_a[3],
const float ray_origin_b[3],
const float ray_direction_b[3],
const float epsilon,
float *r_lambda_a,
float *r_lambda_b);
bool isect_ray_ray_v3(const float ray_origin_a[3],
const float ray_direction_a[3],
const float ray_origin_b[3],

32
source/blender/blenlib/intern/math_geom.c
View File

@ -3057,19 +3057,21 @@ bool isect_line_line_strict_v3(const float v1[3],
*
* \note Neither directions need to be normalized.
*/
bool isect_ray_ray_v3(const float ray_origin_a[3],
const float ray_direction_a[3],
const float ray_origin_b[3],
const float ray_direction_b[3],
float *r_lambda_a,
float *r_lambda_b)
bool isect_ray_ray_epsilon_v3(const float ray_origin_a[3],
const float ray_direction_a[3],
const float ray_origin_b[3],
const float ray_direction_b[3],
const float epsilon,
float *r_lambda_a,
float *r_lambda_b)
{
BLI_assert(r_lambda_a || r_lambda_b);
float n[3];
cross_v3_v3v3(n, ray_direction_b, ray_direction_a);
const float nlen = len_squared_v3(n);
if (UNLIKELY(nlen == 0.0f)) {
/* `nlen` is the the square of the area formed by the two vectors. */
if (UNLIKELY(nlen < epsilon)) {
/* The lines are parallel. */
return false;
}
@ -3091,6 +3093,22 @@ bool isect_ray_ray_v3(const float ray_origin_a[3],
return true;
}
bool isect_ray_ray_v3(const float ray_origin_a[3],
const float ray_direction_a[3],
const float ray_origin_b[3],
const float ray_direction_b[3],
float *r_lambda_a,
float *r_lambda_b)
{
return isect_ray_ray_epsilon_v3(ray_origin_a,
ray_direction_a,
ray_origin_b,
ray_direction_b,
FLT_MIN,
r_lambda_a,
r_lambda_b);
}
bool isect_aabb_aabb_v3(const float min1[3],
const float max1[3],
const float min2[3],

2
source/blender/bmesh/CMakeLists.txt
View File

@ -143,6 +143,8 @@ set(SRC
tools/bmesh_edgesplit.h
tools/bmesh_intersect.c
tools/bmesh_intersect.h
tools/bmesh_intersect_edges.c
tools/bmesh_intersect_edges.h
tools/bmesh_path.c
tools/bmesh_path.h
tools/bmesh_path_region.c

909
source/blender/bmesh/tools/bmesh_intersect_edges.c Normal file
View File

@ -0,0 +1,909 @@
/*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* as published by the Free Software Foundation; either version 2
* of the License, or (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software Foundation,
* Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
*
* The Original Code is Copyright (C) 2019 Blender Foundation.
* All rights reserved.
*/
/** \file
* \ingroup bmesh
*/
#include "MEM_guardedalloc.h"
#include "BLI_math.h"
#include "BLI_sort.h"
#include "BLI_stack.h"
#include "BKE_bvhutils.h"
#include "bmesh.h"
#include "bmesh_intersect_edges.h" /* own include */
#define KDOP_AXIS_LEN 14
/* -------------------------------------------------------------------- */
/** \name Weld Linked Wire Edges into Linked Faces
*
* Used with the merge vertices option.
* \{ */
/* Callbacks for `BM_vert_pair_shared_face_cb` */
struct EDBMSplitBestFaceData {
BMEdge **edgenet;
int edgenet_len;
/**
* Track the range of vertices in edgenet along the faces normal,
* find the lowest since it's most likely to be most co-planar with the face.
*/
float best_face_range_on_normal_axis;
BMFace *r_best_face;
};
static bool bm_vert_pair_share_best_splittable_face_cb(BMFace *f,
BMLoop *l_a,
BMLoop *l_b,
void *userdata)
{
struct EDBMSplitBestFaceData *data = userdata;
float no[3];
copy_v3_v3(no, f->no);
float min = dot_v3v3(l_a->v->co, no);
float max = dot_v3v3(l_b->v->co, no);
if (min > max) {
SWAP(float, min, max);
}
BMVert *v_test = l_b->v;
BMEdge **e_iter = &data->edgenet[0];
int verts_len = data->edgenet_len - 1;
for (int i = verts_len; i--; e_iter++) {
v_test = BM_edge_other_vert(*e_iter, v_test);
if (!BM_face_point_inside_test(f, v_test->co)) {
return false;
}
float dot = dot_v3v3(v_test->co, no);
if (dot < min) {
min = dot;
}
if (dot > max) {
max = dot;
}
}
const float test_face_range_on_normal_axis = max - min;
if (test_face_range_on_normal_axis < data->best_face_range_on_normal_axis) {
data->best_face_range_on_normal_axis = test_face_range_on_normal_axis;
data->r_best_face = f;
}
return false;
}
/* find the best splittable face between the two vertices. */
static bool bm_vert_pair_share_splittable_face_cb(BMFace *UNUSED(f),
BMLoop *l_a,
BMLoop *l_b,
void *userdata)
{
float(*data)[3] = userdata;
float *v_a_co = data[0];
float *v_a_b_dir = data[1];
float lambda;
if (isect_ray_seg_v3(v_a_co, v_a_b_dir, l_a->prev->v->co, l_a->next->v->co, &lambda)) {
if (IN_RANGE(lambda, 0.0f, 1.0f)) {
return true;
}
else if (isect_ray_seg_v3(v_a_co, v_a_b_dir, l_b->prev->v->co, l_b->next->v->co, &lambda)) {
return IN_RANGE(lambda, 0.0f, 1.0f);
}
}
return false;
}
void BM_vert_weld_linked_wire_edges_into_linked_faces(
BMesh *bm, BMVert *v, const float epsilon, BMEdge **r_edgenet[], int *r_edgenet_alloc_len)
{
BMEdge **edgenet = *r_edgenet;
int edgenet_alloc_len = *r_edgenet_alloc_len;
BMIter iter;
BMEdge *e;
BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) {
int edgenet_len = 0;
BMVert *v_other = v;
while (BM_edge_is_wire(e)) {
if (edgenet_alloc_len == edgenet_len) {
edgenet_alloc_len = (edgenet_alloc_len + 1) * 2;
edgenet = MEM_reallocN(edgenet, (edgenet_alloc_len) * sizeof(*edgenet));
}
edgenet[edgenet_len++] = e;
v_other = BM_edge_other_vert(e, v_other);
if (v_other == v) {
/* Endless loop. */
break;
}
BMEdge *e_next = BM_DISK_EDGE_NEXT(e, v_other);
if (e_next == e) {
/* Vert is wire_endpoint. */
edgenet_len = 0;
break;
}
BMEdge *e_test = e_next;
while ((e_test = BM_DISK_EDGE_NEXT(e_test, v_other)) != e) {
if (e_test->l) {
/* Vert is linked to a face. */
goto l_break;
}
}
e = e_next;
}
BMLoop *dummy;
BMFace *best_face;
l_break:
if (edgenet_len == 0) {
/* Nothing to do. */
continue;
}
if (edgenet_len == 1) {
float data[2][3];
copy_v3_v3(data[0], v_other->co);
sub_v3_v3v3(data[1], v->co, data[0]);
best_face = BM_vert_pair_shared_face_cb(
v_other, v, true, bm_vert_pair_share_splittable_face_cb, &data, &dummy, &dummy);
}
else {
struct EDBMSplitBestFaceData data = {
.edgenet = edgenet,
.edgenet_len = edgenet_len,
.best_face_range_on_normal_axis = FLT_MAX,
.r_best_face = NULL,
};
BM_vert_pair_shared_face_cb(
v_other, v, true, bm_vert_pair_share_best_splittable_face_cb, &data, &dummy, &dummy);
if (data.r_best_face) {
float no[3], min = FLT_MAX, max = -FLT_MAX;
copy_v3_v3(no, data.r_best_face->no);
BMVert *v_test;
BMIter f_iter;
BM_ITER_ELEM (v_test, &f_iter, data.r_best_face, BM_VERTS_OF_FACE) {
float dot = dot_v3v3(v_test->co, no);
if (dot < min) {
min = dot;
}
if (dot > max) {
max = dot;
}
}
float range = max - min + 2 * epsilon;
if (range < data.best_face_range_on_normal_axis) {
data.r_best_face = NULL;
}
}
best_face = data.r_best_face;
}
if (best_face) {
BM_face_split_edgenet(bm, best_face, edgenet, edgenet_len, NULL, NULL);
}
}
*r_edgenet = edgenet;
*r_edgenet_alloc_len = edgenet_alloc_len;
}
/** \} */
/* -------------------------------------------------------------------- */
/** \name Auto-Merge & Split Selection
*
* Used after transform operations.
* \{ */
struct EDBMSplitElem {
union {
BMElem *elem;
BMVert *vert;
struct {
BMEdge *edge;
float lambda;
};
};
};
/* -------------------------------------------------------------------- */
/* Overlap Callbacks */
struct EDBMSplitData {
BMesh *bm;
BLI_Stack *pair_stack;
int cut_edges_a_len;
int cut_edges_b_len;
float dist_sq;
float dist_sq_sq;
};
/* Utils */
static void bm_vert_pair_elem_setup_ex(BMVert *v,
float edge_index,
struct EDBMSplitElem *r_pair_elem)
{
BLI_assert(v->head.index == -1);
v->head.index = edge_index;
r_pair_elem->vert = v;
}
static void bm_edge_pair_elem_setup(BMEdge *e,
float lambda,
int *r_data_cut_edges_len,
struct EDBMSplitElem *r_pair_elem)
{
r_pair_elem->edge = e;
r_pair_elem->lambda = lambda;
e->head.index++;
/* Obs: Check Multithread. */
if (BM_elem_flag_test(e, BM_ELEM_TAG)) {
BM_elem_flag_disable(e, BM_ELEM_TAG);
(*r_data_cut_edges_len)++;
}
}
/* Util for Vert x Edge and Edge x Edge callbacks */
static bool bm_vertxedge_isect_impl_ex(BMVert *v,
BMEdge *e,
int edge_index,
float co[3],
float dir[3],
float lambda,
float data_dist_sq,
int *data_cut_edges_len,
struct EDBMSplitElem r_pair[2])
{
BLI_assert(v->head.index == -1);
BMVert *e_v;
float dist_sq_vert_factor;
if (lambda < 0.5f) {
e_v = e->v1;
dist_sq_vert_factor = lambda;
}
else {
e_v = e->v2;
dist_sq_vert_factor = 1.0f - lambda;
}
if (v != e_v) {
CLAMP(lambda, 0.0f, 1.0f);
float near[3];
madd_v3_v3v3fl(near, co, dir, lambda);
float dist_sq = len_squared_v3v3(v->co, near);
if (dist_sq < data_dist_sq) {
float dist_sq_vert = SQUARE(dist_sq_vert_factor) * len_squared_v3(dir);
if (dist_sq_vert < data_dist_sq) {
if (e_v->head.index != -1) {
/* Vertex already has an intersection. */
return false;
}
bm_vert_pair_elem_setup_ex(e_v, -2, &r_pair[1]);
}
else {
bm_edge_pair_elem_setup(e, lambda, data_cut_edges_len, &r_pair[1]);
}
bm_vert_pair_elem_setup_ex(v, edge_index, &r_pair[0]);
return true;
}
}
return false;
}
/* Vertex x Vertex Callback */
static bool bm_vertxvert_isect_cb(void *userdata, int index_a, int index_b, int UNUSED(thread))
{
struct EDBMSplitData *data = userdata;
BMVert *v_a = BM_vert_at_index(data->bm, index_a);
BMVert *v_b = BM_vert_at_index(data->bm, index_b);
struct EDBMSplitElem *pair = BLI_stack_push_r(data->pair_stack);
BLI_assert(v_a->head.index == -1);
/* Set index -2 for sure that it will not repeat keys in `targetmap`. */
bm_vert_pair_elem_setup_ex(v_a, -2, &pair[0]);
bm_vert_pair_elem_setup_ex(v_b, -1, &pair[1]);
return true;
}
/* Vertex x Edge and Edge x Vertex Callbacks */
static int bm_vertxedge_isect_impl(BMesh *bm,
int vert_index,
int edge_index,
float data_dist_sq,
int *data_cut_edges_len,
struct EDBMSplitElem r_pair[2])
{
BMVert *v = BM_vert_at_index(bm, vert_index);
BMEdge *e = BM_edge_at_index(bm, edge_index);
if (v->head.index != -1) {
/* Only one vertex per edge. */
return false;
}
float co[3], dir[3], lambda;
copy_v3_v3(co, e->v1->co);
sub_v3_v3v3(dir, e->v2->co, co);
lambda = ray_point_factor_v3_ex(v->co, co, dir, 0.0f, -1.0f);
return bm_vertxedge_isect_impl_ex(
v, e, edge_index, co, dir, lambda, data_dist_sq, data_cut_edges_len, r_pair);
}
static bool bm_vertxedge_isect_cb(void *userdata, int index_a, int index_b, int UNUSED(thread))
{
struct EDBMSplitData *data = userdata;
struct EDBMSplitElem pair_tmp[2];
if (bm_vertxedge_isect_impl(
data->bm, index_a, index_b, data->dist_sq, &data->cut_edges_b_len, pair_tmp)) {
struct EDBMSplitElem *pair = BLI_stack_push_r(data->pair_stack);
pair[0] = pair_tmp[0];
pair[1] = pair_tmp[1];
return true;
}
return false;
}
static bool bm_edgexvert_isect_cb(void *userdata, int index_a, int index_b, int UNUSED(thread))
{
struct EDBMSplitData *data = userdata;
struct EDBMSplitElem pair_tmp[2];
if (bm_vertxedge_isect_impl(
data->bm, index_b, index_a, data->dist_sq, &data->cut_edges_a_len, pair_tmp)) {
struct EDBMSplitElem *pair = BLI_stack_push_r(data->pair_stack);
pair[0] = pair_tmp[1];
pair[1] = pair_tmp[0];
return true;
}
return false;
}
/* Edge x Edge Callbacks */
static void bm_edgexedge_isect_impl(struct EDBMSplitData *data,
int index_a,
int index_b,
BMEdge *e_a,
BMEdge *e_b,
float co_a[3],
float dir_a[3],
float co_b[3],
float dir_b[3],
float lambda_a,
float lambda_b)
{
float dist_sq_va_factor, dist_sq_vb_factor;
BMVert *e_a_v, *e_b_v;
if (lambda_a < 0.5f) {
e_a_v = e_a->v1;
dist_sq_va_factor = lambda_a;
}
else {
e_a_v = e_a->v2;
dist_sq_va_factor = 1.0f - lambda_a;
}
if (lambda_b < 0.5f) {
e_b_v = e_b->v1;
dist_sq_vb_factor = lambda_b;
}
else {
e_b_v = e_b->v2;
dist_sq_vb_factor = 1.0f - lambda_b;
}
if (e_a_v != e_b_v) {
CLAMP(lambda_a, 0.0f, 1.0f);
CLAMP(lambda_b, 0.0f, 1.0f);
float near_a[3], near_b[3];
madd_v3_v3v3fl(near_a, co_a, dir_a, lambda_a);
madd_v3_v3v3fl(near_b, co_b, dir_b, lambda_b);
float dist_sq = len_squared_v3v3(near_a, near_b);
if (dist_sq < data->dist_sq) {
struct EDBMSplitElem pair_tmp[2];
float dist_sq_va = SQUARE(dist_sq_va_factor) * len_squared_v3(dir_a);
float dist_sq_vb = SQUARE(dist_sq_vb_factor) * len_squared_v3(dir_b);
if (dist_sq_va < data->dist_sq) {
if (e_a_v->head.index != -1) {
/* Only one vertex per edge. */
return;
}
bm_vert_pair_elem_setup_ex(e_a_v, index_b, &pair_tmp[0]);
}
if (dist_sq_vb < data->dist_sq) {
if (e_b_v->head.index != -1) {
/* Only one vertex per edge. */
return;
}
bm_vert_pair_elem_setup_ex(e_b_v, index_a, &pair_tmp[1]);
}
else {
bm_edge_pair_elem_setup(e_b, lambda_b, &data->cut_edges_b_len, &pair_tmp[1]);
}
/* Don't setup edges before a return. */
if (dist_sq_va >= data->dist_sq) {
bm_edge_pair_elem_setup(e_a, lambda_a, &data->cut_edges_a_len, &pair_tmp[0]);
}
struct EDBMSplitElem *pair = BLI_stack_push_r(data->pair_stack);
pair[0] = pair_tmp[0];
pair[1] = pair_tmp[1];
}
}
}
static bool bm_edgexedge_isect_cb(void *userdata, int index_a, int index_b, int UNUSED(thread))
{
bool ret = false;
struct EDBMSplitData *data = userdata;
BMEdge *e_a = BM_edge_at_index(data->bm, index_a);
BMEdge *e_b = BM_edge_at_index(data->bm, index_b);
float co_a[3], dir_a[3], co_b[3], dir_b[3];
copy_v3_v3(co_a, e_a->v1->co);
sub_v3_v3v3(dir_a, e_a->v2->co, co_a);
copy_v3_v3(co_b, e_b->v1->co);
sub_v3_v3v3(dir_b, e_b->v2->co, co_b);
float lambda_a, lambda_b;
/* Using with dist^4 as `epsilon` is not the best solution, but it fits in most cases. */
if (isect_ray_ray_epsilon_v3(co_a, dir_a, co_b, dir_b, data->dist_sq_sq, &lambda_a, &lambda_b)) {
if (ELEM(index_b, e_a->v1->head.index, e_a->v2->head.index) ||
ELEM(index_a, e_b->v1->head.index, e_b->v2->head.index)) {
return ret;
}
/* Edge x Edge returns always false. */
bm_edgexedge_isect_impl(
data, index_a, index_b, e_a, e_b, co_a, dir_a, co_b, dir_b, lambda_a, lambda_b);
}
else {
/* Parallel */
struct EDBMSplitElem pair_tmp[2];
float vec[3], len_sq_a, len_sq_b, lambda;
sub_v3_v3v3(vec, co_b, co_a);
len_sq_a = len_squared_v3(dir_a);
len_sq_b = len_squared_v3(dir_b);
if (!ELEM(e_b->v1, e_a->v1, e_a->v2) && e_b->v1->head.index == -1) {
lambda = dot_v3v3(vec, dir_a) / len_sq_a;
if (bm_vertxedge_isect_impl_ex(e_b->v1,
e_a,
index_a,
co_a,
dir_a,
lambda,
data->dist_sq,
&data->cut_edges_a_len,
pair_tmp)) {
struct EDBMSplitElem *pair = BLI_stack_push_r(data->pair_stack);
pair[0] = pair_tmp[1];
pair[1] = pair_tmp[0];
ret |= true;
}
}
if (!ELEM(e_a->v1, e_b->v1, e_b->v2) && e_a->v1->head.index == -1) {
lambda = -dot_v3v3(vec, dir_b) / len_sq_b;
if (bm_vertxedge_isect_impl_ex(e_a->v1,
e_b,
index_b,
co_b,
dir_b,
lambda,
data->dist_sq,
&data->cut_edges_b_len,
pair_tmp)) {
struct EDBMSplitElem *pair = BLI_stack_push_r(data->pair_stack);
pair[0] = pair_tmp[0];
pair[1] = pair_tmp[1];
ret |= true;
}
}
add_v3_v3(vec, dir_b);
if (!ELEM(e_b->v2, e_a->v1, e_a->v2) && e_b->v2->head.index == -1) {
lambda = dot_v3v3(vec, dir_a) / len_sq_a;
if (bm_vertxedge_isect_impl_ex(e_b->v2,
e_a,
index_a,
co_a,
dir_a,
lambda,
data->dist_sq,
&data->cut_edges_a_len,
pair_tmp)) {
struct EDBMSplitElem *pair = BLI_stack_push_r(data->pair_stack);
pair[0] = pair_tmp[1];
pair[1] = pair_tmp[0];
ret |= true;
}
}
sub_v3_v3(vec, dir_a);
if (!ELEM(e_a->v2, e_b->v1, e_b->v2) && e_a->v2->head.index == -1) {
lambda = 1.0f - dot_v3v3(vec, dir_b) / len_sq_b;
if (bm_vertxedge_isect_impl_ex(e_a->v2,
e_b,
index_b,
co_b,
dir_b,
lambda,
data->dist_sq,
&data->cut_edges_b_len,
pair_tmp)) {
struct EDBMSplitElem *pair = BLI_stack_push_r(data->pair_stack);
pair[0] = pair_tmp[0];
pair[1] = pair_tmp[1];
ret |= true;
}
}
}
return ret;
}
/* -------------------------------------------------------------------- */
/* BVHTree Overlap Function */
static void bvhtree_overlap_thread_safe(const BVHTree *tree1,
const BVHTree *tree2,
BVHTree_OverlapCallback callback,
void *userdata)
{
BLI_bvhtree_overlap_ex(tree1, tree2, NULL, callback, userdata, BVH_OVERLAP_BREAK_ON_FIRST);
}
/* -------------------------------------------------------------------- */
/* Callbacks for `BLI_qsort_r` */
static int sort_cmp_by_lambda_a_cb(const void *index1_v, const void *index2_v, void *keys_v)
{
const struct EDBMSplitElem(*pair_array)[2] = keys_v;
const int index1 = *(int *)index1_v;
const int index2 = *(int *)index2_v;
if (pair_array[index1][0].lambda > pair_array[index2][0].lambda) {
return 1;
}
else {
return -1;
}
}
static int sort_cmp_by_lambda_b_cb(const void *index1_v, const void *index2_v, void *keys_v)
{
const struct EDBMSplitElem(*pair_array)[2] = keys_v;
const int index1 = *(int *)index1_v;
const int index2 = *(int *)index2_v;
if (pair_array[index1][1].lambda > pair_array[index2][1].lambda) {
return 1;
}
else {
return -1;
}
}
/* -------------------------------------------------------------------- */
/* Main API */
bool BM_mesh_intersect_edges(BMesh *bm, const char hflag, const float dist, GHash *r_targetmap)
{
bool ok = false;
BMIter iter;
BMVert *v;
BMEdge *e;
int i;
/* Store all intersections in this array. */
struct EDBMSplitElem(*pair_iter)[2], (*pair_array)[2] = NULL;
BLI_Stack *pair_stack = BLI_stack_new(sizeof(*pair_array), __func__);
int pair_len = 0;
float dist_sq = SQUARE(dist);
struct EDBMSplitData data = {
.bm = bm,
.pair_stack = pair_stack,
.cut_edges_a_len = 0,
.cut_edges_b_len = 0,
.dist_sq = dist_sq,
.dist_sq_sq = SQUARE(dist_sq),
};
/* tag and count the verts to be tested. */
int verts_act_len = 0, verts_remain_len = 0;
int loose_verts_act_len = 0, loose_verts_remain_len = 0;
BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
if (BM_elem_flag_test(v, hflag)) {
BM_elem_flag_enable(v, BM_ELEM_TAG);
v->head.index = -1;
verts_act_len++;
if (!v->e) {
loose_verts_act_len++;
}
}
else {
BM_elem_flag_disable(v, BM_ELEM_TAG);
if (!BM_elem_flag_test(v, BM_ELEM_HIDDEN)) {
v->head.index = -1;
verts_remain_len++;
if (!v->e) {
loose_verts_remain_len++;
}
}
}
}
bm->elem_index_dirty |= BM_VERT;
/* Start the creation of BVHTrees. */
BVHTree *tree_loose_verts_act = NULL, *tree_loose_verts_remain = NULL;
if (loose_verts_act_len) {
tree_loose_verts_act = BLI_bvhtree_new(loose_verts_act_len, dist, 2, KDOP_AXIS_LEN);
}
if (loose_verts_remain_len) {
tree_loose_verts_remain = BLI_bvhtree_new(loose_verts_remain_len, 0.0f, 2, KDOP_AXIS_LEN);
}
if (tree_loose_verts_act || tree_loose_verts_remain) {
BM_ITER_MESH_INDEX (v, &iter, bm, BM_VERTS_OF_MESH, i) {
if (BM_elem_flag_test(v, BM_ELEM_TAG)) {
if (tree_loose_verts_act && !v->e) {
BLI_bvhtree_insert(tree_loose_verts_act, i, v->co, 1);
}
}
else if (tree_loose_verts_remain && !v->e && !BM_elem_flag_test(v, BM_ELEM_HIDDEN)) {
BLI_bvhtree_insert(tree_loose_verts_remain, i, v->co, 1);
}
}
if (tree_loose_verts_act) {
BLI_bvhtree_balance(tree_loose_verts_act);
}
if (tree_loose_verts_remain) {
BLI_bvhtree_balance(tree_loose_verts_remain);
}
if (tree_loose_verts_act && tree_loose_verts_remain) {
/* First pair search. */
bvhtree_overlap_thread_safe(
tree_loose_verts_act, tree_loose_verts_remain, bm_vertxvert_isect_cb, &data);
}
}
/* Tag and count the edges. */
int edges_act_len = 0, edges_remain_len = 0;
BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
if (BM_elem_flag_test(e->v1, BM_ELEM_TAG) || BM_elem_flag_test(e->v2, BM_ELEM_TAG)) {
BM_elem_flag_enable(e, BM_ELEM_TAG);
edges_act_len++;
}
else {
BM_elem_flag_disable(e, BM_ELEM_TAG);
if (!BM_elem_flag_test(e, BM_ELEM_HIDDEN)) {
edges_remain_len++;
}
}
}
if (edges_remain_len) {
BVHTree *tree_edges_act = NULL, *tree_edges_remain = NULL;
tree_edges_remain = BLI_bvhtree_new(edges_remain_len, 0.0f, 2, KDOP_AXIS_LEN);
if (edges_act_len) {
tree_edges_act = BLI_bvhtree_new(edges_act_len, dist, 2, KDOP_AXIS_LEN);
}
BM_ITER_MESH_INDEX (e, &iter, bm, BM_EDGES_OF_MESH, i) {
float co[2][3];
if (BM_elem_flag_test(e, BM_ELEM_TAG)) {
if (tree_edges_act) {
e->head.index = 0;
copy_v3_v3(co[0], e->v1->co);
copy_v3_v3(co[1], e->v2->co);
BLI_bvhtree_insert(tree_edges_act, i, co[0], 2);
}
}
else if (!BM_elem_flag_test(e, BM_ELEM_HIDDEN)) {
/* Tag used in the overlap callbacks. */
BM_elem_flag_enable(e, BM_ELEM_TAG);
e->head.index = 0;
copy_v3_v3(co[0], e->v1->co);
copy_v3_v3(co[1], e->v2->co);
BLI_bvhtree_insert(tree_edges_remain, i, co[0], 2);
}
}
/* Use `e->head.index` to count intersections. */
bm->elem_index_dirty |= BM_EDGE;
BLI_bvhtree_balance(tree_edges_remain);
if (tree_edges_act) {
BLI_bvhtree_balance(tree_edges_act);
}
if (tree_edges_act) {
/* Edge x Edge */
bvhtree_overlap_thread_safe(tree_edges_act, tree_edges_remain, bm_edgexedge_isect_cb, &data);
if (tree_loose_verts_remain) {
/* Edge x Vert */
bvhtree_overlap_thread_safe(
tree_edges_act, tree_loose_verts_remain, bm_edgexvert_isect_cb, &data);
}
BLI_bvhtree_free(tree_edges_act);
}
if (tree_loose_verts_act) {
/* Vert x Edge */
bvhtree_overlap_thread_safe(
tree_loose_verts_act, tree_edges_remain, bm_vertxedge_isect_cb, &data);
}
BLI_bvhtree_free(tree_edges_remain);
pair_len = BLI_stack_count(pair_stack);
if (pair_len) {
pair_array = MEM_mallocN(sizeof(*pair_array) * pair_len, __func__);
BLI_stack_pop_n_reverse(pair_stack, pair_array, pair_len);
/* Map intersections per edge. */
union {
struct {
int cuts_len;
int cuts_index[];
};
int as_int[0];
} * e_map_iter, *e_map;
size_t e_map_size = (max_ii(data.cut_edges_a_len, data.cut_edges_b_len) * sizeof(*e_map)) +
(pair_len * sizeof(*(e_map->cuts_index)));
e_map = MEM_mallocN(e_map_size, __func__);
/* Convert every pair to Vert x Vert. */
for (int pair = 0; pair < 2; pair++) {
int map_len = 0;
pair_iter = &pair_array[0];
for (i = 0; i < pair_len; i++, pair_iter++) {
if ((*pair_iter)[pair].elem->head.htype != BM_EDGE) {
/* Take the opportunity to set all vert indices to -1 again. */
(*pair_iter)[pair].elem->head.index = -1;
continue;
}
e = (*pair_iter)[pair].edge;
if (!BM_elem_flag_test(e, BM_ELEM_TAG)) {
BM_elem_flag_enable(e, BM_ELEM_TAG);
int e_cuts_len = e->head.index;
e_map_iter = (void *)&e_map->as_int[map_len];
e_map_iter->cuts_len = e_cuts_len;
e_map_iter->cuts_index[0] = i;
/* Use `e->head.index` to indicate which slot to fill with the `cut` index. */
e->head.index = map_len + 1;
map_len += 1 + e_cuts_len;
}
else {
e_map->as_int[++e->head.index] = i;
}
}
/* Split Edges A to set all Vert x Edge. */
for (i = 0; i < map_len;
e_map_iter = (void *)&e_map->as_int[i], i += 1 + e_map_iter->cuts_len) {
/* sort by lambda. */
BLI_qsort_r(e_map_iter->cuts_index,
e_map_iter->cuts_len,
sizeof(*(e_map->cuts_index)),
pair == 0 ? sort_cmp_by_lambda_a_cb : sort_cmp_by_lambda_b_cb,
pair_array);
float lambda, lambda_prev = 0.0f;
for (int j = 0; j < e_map_iter->cuts_len; j++) {
struct EDBMSplitElem *pair_elem = &pair_array[e_map_iter->cuts_index[j]][pair];
lambda = (pair_elem->lambda - lambda_prev) / (1.0f - lambda_prev);
lambda_prev = pair_elem->lambda;
e = pair_elem->edge;
BMVert *v_new = BM_edge_split(bm, e, e->v1, NULL, lambda);
v_new->head.index = -1;
pair_elem->vert = v_new;
}
}
}
MEM_freeN(e_map);
}
}
BLI_bvhtree_free(tree_loose_verts_act);
BLI_bvhtree_free(tree_loose_verts_remain);
if (r_targetmap) {
if (pair_array == NULL) {
pair_len = BLI_stack_count(pair_stack);
if (pair_len) {
pair_array = MEM_mallocN(sizeof(*pair_array) * pair_len, __func__);
BLI_stack_pop_n_reverse(pair_stack, pair_array, pair_len);
}
}
if (pair_array) {
/* Organize the vertices in the order they will be merged. */
pair_iter = &pair_array[0];
for (i = 0; i < pair_len; i++, pair_iter++) {
BLI_assert((*pair_iter)[0].elem->head.htype == BM_VERT);
BLI_assert((*pair_iter)[1].elem->head.htype == BM_VERT);
BLI_assert((*pair_iter)[0].elem != (*pair_iter)[1].elem);
BLI_ghash_insert(r_targetmap, (*pair_iter)[0].vert, (*pair_iter)[1].vert);
}
ok = true;
}
}
BLI_stack_free(pair_stack);
if (pair_array) {
MEM_freeN(pair_array);
}
return ok;
}
/** \} */

29
source/blender/bmesh/tools/bmesh_intersect_edges.h Normal file
View File

@ -0,0 +1,29 @@
/*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* as published by the Free Software Foundation; either version 2
* of the License, or (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software Foundation,
* Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
*/
/** \file
* \ingroup bmesh
*/
#ifndef __BMESH_INTERSECT_EDGES_H__
#define __BMESH_INTERSECT_EDGES_H__
void BM_vert_weld_linked_wire_edges_into_linked_faces(
BMesh *bm, BMVert *v, const float epsilon, BMEdge **r_edgenet[], int *r_edgenet_alloc_len);
bool BM_mesh_intersect_edges(BMesh *bm, const char hflag, const float dist, GHash *r_targetmap);
#endif /* __BMESH_INTERSECT_EDGES_H__ */