Differential D8691 Diff 28089 source/blender/bmesh/tools/bmesh_intersect.c

Changeset View

Standalone View

source/blender/bmesh/tools/bmesh_intersect.c

Show All 26 Lines
* - Custom-data (UV's etc).		* - Custom-data (UV's etc).
*		*
* Unsupported:		* Unsupported:
* - Intersecting between different meshes.		* - Intersecting between different meshes.
* - No support for holes (cutting a hole into a single face).		* - No support for holes (cutting a hole into a single face).
*/		*/

#include "MEM_guardedalloc.h"		#include "MEM_guardedalloc.h"
		#include <CLG_log.h>

#include "BLI_alloca.h"		#include "BLI_alloca.h"
#include "BLI_math.h"		#include "BLI_math.h"
#include "BLI_memarena.h"		#include "BLI_memarena.h"
#include "BLI_sort_utils.h"		#include "BLI_sort_utils.h"
#include "BLI_utildefines.h"		#include "BLI_utildefines.h"

#include "BLI_linklist_stack.h"		#include "BLI_linklist_stack.h"
Show All 29 Lines
#define USE_NET_ISLAND_CONNECT		#define USE_NET_ISLAND_CONNECT

/* strict asserts that may fail in practice (handy for debugging cases which should succeed) */		/* strict asserts that may fail in practice (handy for debugging cases which should succeed) */
// #define USE_PARANOID		// #define USE_PARANOID
/* use accelerated overlap check */		/* use accelerated overlap check */
#define USE_BVH		#define USE_BVH

// #define USE_DUMP		// #define USE_DUMP
		#ifdef USE_DUMP
		static CLG_LogRef LOG = {"bmesh.bmesh_intersect"};
		# define CLOG_BMESH_INTERSECT(level, ...) CLOG_VERBOSE(&LOG, level, __VA_ARGS__)
		#else
		# define CLOG_BMESH_INTERSECT(level, ...) \
		do { \
		} while (0)
		#endif // USE_DUMP

static void tri_v3_scale(float v1[3], float v2[3], float v3[3], const float t)		static void tri_v3_scale(float v1[3], float v2[3], float v3[3], const float t)
{		{
float p[3];		float p[3];

mid_v3_v3v3v3(p, v1, v2, v3);		mid_v3_v3v3v3(p, v1, v2, v3);

interp_v3_v3v3(v1, p, v1, t);		interp_v3_v3v3(v1, p, v1, t);
▲ Show 20 Lines • Show All 140 Lines • ▼ Show 20 Lines	static void face_edges_split(BMesh *bm,
LinkNode *node;		LinkNode *node;
BLI_assert(f->head.htype == BM_FACE);		BLI_assert(f->head.htype == BM_FACE);

for (i = 0, node = e_ls_base->list; i < e_ls_base->list_len; i++, node = node->next) {		for (i = 0, node = e_ls_base->list; i < e_ls_base->list_len; i++, node = node->next) {
edge_arr[i] = node->link;		edge_arr[i] = node->link;
}		}
BLI_assert(node == NULL);		BLI_assert(node == NULL);

# ifdef USE_DUMP		CLOG_BMESH_INTERSECT(0, "# %d %u", BM_elem_index_get(f), e_ls_base->list_len);
printf("# %s: %d %u\n", __func__, BM_elem_index_get(f), e_ls_base->list_len);
# endif

# ifdef USE_NET_ISLAND_CONNECT		# ifdef USE_NET_ISLAND_CONNECT
if (use_island_connect) {		if (use_island_connect) {
uint edge_arr_holes_len;		uint edge_arr_holes_len;
BMEdge **edge_arr_holes;		BMEdge **edge_arr_holes;
if (BM_face_split_edgenet_connect_islands(bm,		if (BM_face_split_edgenet_connect_islands(bm,
f,		f,
edge_arr,		edge_arr,
▲ Show 20 Lines • Show All 162 Lines • ▼ Show 20 Lines
#undef KEY_EDGE_TRI_ORDER		#undef KEY_EDGE_TRI_ORDER

for (i = 0; i < ARRAY_SIZE(k_arr); i++) {		for (i = 0; i < ARRAY_SIZE(k_arr); i++) {
BMVert *iv;		BMVert *iv;

iv = BLI_ghash_lookup(s->edgetri_cache, k_arr[i]);		iv = BLI_ghash_lookup(s->edgetri_cache, k_arr[i]);

if (iv) {		if (iv) {
#ifdef USE_DUMP		CLOG_BMESH_INTERSECT(1, "# cache hit (%d, %d, %d, %d)", UNPACK4(k_arr[i]));
printf("# cache hit (%d, %d, %d, %d)\n", UNPACK4(k_arr[i]));
#endif
*r_side = (enum ISectType)i;		*r_side = (enum ISectType)i;
return iv;		return iv;
}		}
}		}

*r_side = intersect_line_tri(e_v0->co, e_v1->co, t_cos, t_nor, ix, &s->epsilon);		*r_side = intersect_line_tri(e_v0->co, e_v1->co, t_cos, t_nor, ix, &s->epsilon);
if (*r_side != IX_NONE) {		if (*r_side != IX_NONE) {
BMVert *iv;		BMVert *iv;
BMEdge *e;		BMEdge *e;
#ifdef USE_DUMP		CLOG_BMESH_INTERSECT(1, "# new vertex (%.6f, %.6f, %.6f) %d", UNPACK3(ix), *r_side);
printf("# new vertex (%.6f, %.6f, %.6f) %d\n", UNPACK3(ix), *r_side);
#endif

#ifdef USE_PARANOID		#ifdef USE_PARANOID
BLI_assert(len_squared_v3v3(ix, e_v0->co) > s->epsilon.eps_sq);		BLI_assert(len_squared_v3v3(ix, e_v0->co) > s->epsilon.eps_sq);
BLI_assert(len_squared_v3v3(ix, e_v1->co) > s->epsilon.eps_sq);		BLI_assert(len_squared_v3v3(ix, e_v1->co) > s->epsilon.eps_sq);
BLI_assert(len_squared_v3v3(ix, t[0]->co) > s->epsilon.eps_sq);		BLI_assert(len_squared_v3v3(ix, t[0]->co) > s->epsilon.eps_sq);
BLI_assert(len_squared_v3v3(ix, t[1]->co) > s->epsilon.eps_sq);		BLI_assert(len_squared_v3v3(ix, t[1]->co) > s->epsilon.eps_sq);
BLI_assert(len_squared_v3v3(ix, t[2]->co) > s->epsilon.eps_sq);		BLI_assert(len_squared_v3v3(ix, t[2]->co) > s->epsilon.eps_sq);
#endif		#endif
iv = BM_vert_create(bm, ix, NULL, 0);		iv = BM_vert_create(bm, ix, NULL, 0);

e = BM_edge_exists(e_v0, e_v1);		e = BM_edge_exists(e_v0, e_v1);
if (e) {		if (e) {
#ifdef USE_DUMP		CLOG_BMESH_INTERSECT(2, "# adding to edge %d", BM_elem_index_get(e));
printf("# adding to edge %d\n", BM_elem_index_get(e));
#endif
edge_verts_add(s, e, iv, false);		edge_verts_add(s, e, iv, false);
}		}
else {		else {
#ifdef USE_DISSOLVE		#ifdef USE_DISSOLVE
vert_dissolve_add(s, iv);		vert_dissolve_add(s, iv);
#endif		#endif
}		}

▲ Show 20 Lines • Show All 108 Lines • ▼ Show 20 Lines	* --------- */
/* first check in any verts are touching		/* first check in any verts are touching
* (any case where we wont create new verts)		* (any case where we wont create new verts)
*/		*/
uint i_a;		uint i_a;
for (i_a = 0; i_a < 3; i_a++) {		for (i_a = 0; i_a < 3; i_a++) {
uint i_b;		uint i_b;
for (i_b = 0; i_b < 3; 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 (len_squared_v3v3(fv_a[i_a]->co, fv_b[i_b]->co) <= s->epsilon.eps2x_sq) {
#ifdef USE_DUMP
if (BM_ELEM_API_FLAG_TEST(fv_a[i_a], VERT_VISIT_A) == 0) {		if (BM_ELEM_API_FLAG_TEST(fv_a[i_a], VERT_VISIT_A) == 0) {
printf(" ('VERT-VERT-A') %u, %d),\n", i_a, BM_elem_index_get(fv_a[i_a]));		CLOG_BMESH_INTERSECT(
		10, " ('VERT-VERT-A') %u, %d),", i_a, BM_elem_index_get(fv_a[i_a]));
}		}
if (BM_ELEM_API_FLAG_TEST(fv_b[i_b], VERT_VISIT_B) == 0) {		if (BM_ELEM_API_FLAG_TEST(fv_b[i_b], VERT_VISIT_B) == 0) {
printf(" ('VERT-VERT-B') %u, %d),\n", i_b, BM_elem_index_get(fv_b[i_b]));		CLOG_BMESH_INTERSECT(
		10, " ('VERT-VERT-B') %u, %d),", i_b, BM_elem_index_get(fv_b[i_b]));
}		}
#endif
STACK_PUSH_TEST_A(fv_a[i_a]);		STACK_PUSH_TEST_A(fv_a[i_a]);
STACK_PUSH_TEST_B(fv_b[i_b]);		STACK_PUSH_TEST_B(fv_b[i_b]);
}		}
}		}
}		}
}		}

/* vert-edge		/* vert-edge
Show All 16 Lines	for (i_a = 0; i_a < 3; i_a++) {
if ((fac > 0.0f - s->epsilon.eps) && (fac < 1.0f + s->epsilon.eps)) {		if ((fac > 0.0f - s->epsilon.eps) && (fac < 1.0f + s->epsilon.eps)) {
float ix[3];		float ix[3];
interp_v3_v3v3(ix, fv_b[i_b_e0]->co, fv_b[i_b_e1]->co, fac);		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) {		if (len_squared_v3v3(ix, fv_a[i_a]->co) <= s->epsilon.eps2x_sq) {
BMEdge *e;		BMEdge *e;
STACK_PUSH_TEST_B(fv_a[i_a]);		STACK_PUSH_TEST_B(fv_a[i_a]);
// STACK_PUSH_TEST_A(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]);		e = BM_edge_exists(fv_b[i_b_e0], fv_b[i_b_e1]);
#ifdef USE_DUMP		CLOG_BMESH_INTERSECT(15,
printf(" ('VERT-EDGE-A', %d, %d),\n",		" ('VERT-EDGE-A', %d, %d),",
BM_elem_index_get(fv_b[i_b_e0]),		BM_elem_index_get(fv_b[i_b_e0]),
BM_elem_index_get(fv_b[i_b_e1]));		BM_elem_index_get(fv_b[i_b_e1]));
#endif
if (e) {		if (e) {
#ifdef USE_DUMP		CLOG_BMESH_INTERSECT(15, "# adding to edge %d", BM_elem_index_get(e));
printf("# adding to edge %d\n", BM_elem_index_get(e));
#endif
edge_verts_add(s, e, fv_a[i_a], true);		edge_verts_add(s, e, fv_a[i_a], true);
}		}
break;		break;
}		}
}		}
}		}
}		}
}		}
Show All 17 Lines	for (i_b = 0; i_b < 3; i_b++) {
if ((fac > 0.0f - s->epsilon.eps) && (fac < 1.0f + s->epsilon.eps)) {		if ((fac > 0.0f - s->epsilon.eps) && (fac < 1.0f + s->epsilon.eps)) {
float ix[3];		float ix[3];
interp_v3_v3v3(ix, fv_a[i_a_e0]->co, fv_a[i_a_e1]->co, fac);		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) {		if (len_squared_v3v3(ix, fv_b[i_b]->co) <= s->epsilon.eps2x_sq) {
BMEdge *e;		BMEdge *e;
STACK_PUSH_TEST_A(fv_b[i_b]);		STACK_PUSH_TEST_A(fv_b[i_b]);
// STACK_PUSH_NOTEST(iv_ls_b, fv_b[i_b]);		// STACK_PUSH_NOTEST(iv_ls_b, fv_b[i_b]);
e = BM_edge_exists(fv_a[i_a_e0], fv_a[i_a_e1]);		e = BM_edge_exists(fv_a[i_a_e0], fv_a[i_a_e1]);
#ifdef USE_DUMP		CLOG_BMESH_INTERSECT(15,
printf(" ('VERT-EDGE-B', %d, %d),\n",		" ('VERT-EDGE-B', %d, %d),",
BM_elem_index_get(fv_a[i_a_e0]),		BM_elem_index_get(fv_a[i_a_e0]),
BM_elem_index_get(fv_a[i_a_e1]));		BM_elem_index_get(fv_a[i_a_e1]));
#endif
if (e) {		if (e) {
#ifdef USE_DUMP		CLOG_BMESH_INTERSECT(15, "# adding to edge %d", BM_elem_index_get(e));
printf("# adding to edge %d\n", BM_elem_index_get(e));
#endif
edge_verts_add(s, e, fv_b[i_b], true);		edge_verts_add(s, e, fv_b[i_b], true);
}		}
break;		break;
}		}
}		}
}		}
}		}
}		}
Show All 17 Lines	for (i_a = 0; i_a < 3; i_a++) {
continue;		continue;
}		}

float ix[3];		float ix[3];
if (isect_point_tri_v3(fv_a[i_a]->co, UNPACK3(t_scale), ix)) {		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) {		if (len_squared_v3v3(ix, fv_a[i_a]->co) <= s->epsilon.eps2x_sq) {
STACK_PUSH_TEST_A(fv_a[i_a]);		STACK_PUSH_TEST_A(fv_a[i_a]);
STACK_PUSH_TEST_B(fv_a[i_a]);		STACK_PUSH_TEST_B(fv_a[i_a]);
#ifdef USE_DUMP		CLOG_BMESH_INTERSECT(6, " 'VERT TRI-A',");
printf(" 'VERT TRI-A',\n");
#endif
}		}
}		}
}		}
}		}

{		{
float t_scale[3][3];		float t_scale[3][3];
uint i_b;		uint i_b;

copy_v3_v3(t_scale[0], fv_a[0]->co);		copy_v3_v3(t_scale[0], fv_a[0]->co);
copy_v3_v3(t_scale[1], fv_a[1]->co);		copy_v3_v3(t_scale[1], fv_a[1]->co);
copy_v3_v3(t_scale[2], fv_a[2]->co);		copy_v3_v3(t_scale[2], fv_a[2]->co);
tri_v3_scale(UNPACK3(t_scale), 1.0f - s->epsilon.eps2x);		tri_v3_scale(UNPACK3(t_scale), 1.0f - s->epsilon.eps2x);

for (i_b = 0; i_b < 3; i_b++) {		for (i_b = 0; i_b < 3; i_b++) {
if (BM_ELEM_API_FLAG_TEST(fv_b[i_b], VERT_VISIT_B)) {		if (BM_ELEM_API_FLAG_TEST(fv_b[i_b], VERT_VISIT_B)) {
continue;		continue;
}		}

float ix[3];		float ix[3];
if (isect_point_tri_v3(fv_b[i_b]->co, UNPACK3(t_scale), ix)) {		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) {		if (len_squared_v3v3(ix, fv_b[i_b]->co) <= s->epsilon.eps2x_sq) {
STACK_PUSH_TEST_A(fv_b[i_b]);		STACK_PUSH_TEST_A(fv_b[i_b]);
STACK_PUSH_TEST_B(fv_b[i_b]);		STACK_PUSH_TEST_B(fv_b[i_b]);
#ifdef USE_DUMP		CLOG_BMESH_INTERSECT(6, " 'VERT TRI-B',");
printf(" 'VERT TRI-B',\n");
#endif
}		}
}		}
}		}
}		}

if ((STACK_SIZE(iv_ls_a) >= 3) && (STACK_SIZE(iv_ls_b) >= 3)) {		if ((STACK_SIZE(iv_ls_a) >= 3) && (STACK_SIZE(iv_ls_b) >= 3)) {
#ifdef USE_DUMP		CLOG_BMESH_INTERSECT(6, "# OVERLAP");
printf("# OVERLAP\n");
#endif
goto finally;		goto finally;
}		}

normal_tri_v3(f_a_nor, UNPACK3(f_a_cos));		normal_tri_v3(f_a_nor, UNPACK3(f_a_cos));
normal_tri_v3(f_b_nor, UNPACK3(f_b_cos));		normal_tri_v3(f_b_nor, UNPACK3(f_b_cos));

/* edge-tri & edge-edge		/* edge-tri & edge-edge
* -------------------- */		* -------------------- */
{		{
for (uint i_a_e0 = 0; i_a_e0 < 3; i_a_e0++) {		for (uint i_a_e0 = 0; i_a_e0 < 3; i_a_e0++) {
uint i_a_e1 = (i_a_e0 + 1) % 3;		uint i_a_e1 = (i_a_e0 + 1) % 3;
enum ISectType side;		enum ISectType side;
BMVert *iv;		BMVert *iv;

if (BM_ELEM_API_FLAG_TEST(fv_a[i_a_e0], VERT_VISIT_A) \|\|		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)) {		BM_ELEM_API_FLAG_TEST(fv_a[i_a_e1], VERT_VISIT_A)) {
continue;		continue;
}		}

iv = bm_isect_edge_tri(		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);		s, fv_a[i_a_e0], fv_a[i_a_e1], fv_b, b_index, f_b_cos, f_b_nor, &side);
if (iv) {		if (iv) {
STACK_PUSH_TEST_A(iv);		STACK_PUSH_TEST_A(iv);
STACK_PUSH_TEST_B(iv);		STACK_PUSH_TEST_B(iv);
#ifdef USE_DUMP		CLOG_BMESH_INTERSECT(6, " ('EDGE-TRI-A', %d),", side);
printf(" ('EDGE-TRI-A', %d),\n", side);
#endif
}		}
}		}

for (uint i_b_e0 = 0; i_b_e0 < 3; i_b_e0++) {		for (uint i_b_e0 = 0; i_b_e0 < 3; i_b_e0++) {
uint i_b_e1 = (i_b_e0 + 1) % 3;		uint i_b_e1 = (i_b_e0 + 1) % 3;
enum ISectType side;		enum ISectType side;
BMVert *iv;		BMVert *iv;

if (BM_ELEM_API_FLAG_TEST(fv_b[i_b_e0], VERT_VISIT_B) \|\|		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)) {		BM_ELEM_API_FLAG_TEST(fv_b[i_b_e1], VERT_VISIT_B)) {
continue;		continue;
}		}

iv = bm_isect_edge_tri(		iv = bm_isect_edge_tri(
s, fv_b[i_b_e0], fv_b[i_b_e1], fv_a, a_index, f_a_cos, f_a_nor, &side);		s, fv_b[i_b_e0], fv_b[i_b_e1], fv_a, a_index, f_a_cos, f_a_nor, &side);
if (iv) {		if (iv) {
STACK_PUSH_TEST_A(iv);		STACK_PUSH_TEST_A(iv);
STACK_PUSH_TEST_B(iv);		STACK_PUSH_TEST_B(iv);
#ifdef USE_DUMP		CLOG_BMESH_INTERSECT(6, " ('EDGE-TRI-B', %d),", side);
printf(" ('EDGE-TRI-B', %d),\n", side);
#endif
}		}
}		}
}		}

{		{
for (i = 0; i < 2; i++) {		for (i = 0; i < 2; i++) {
BMVert **ie_vs;		BMVert **ie_vs;
BMFace *f;		BMFace *f;
▲ Show 20 Lines • Show All 76 Lines • ▼ Show 20 Lines	static void raycast_callback(void *userdata,
if (		if (
# ifdef USE_KDOPBVH_WATERTIGHT		# ifdef USE_KDOPBVH_WATERTIGHT
isect_ray_tri_watertight_v3(ray->origin, &isect_precalc_x, v0, v1, v2, &dist, NULL)		isect_ray_tri_watertight_v3(ray->origin, &isect_precalc_x, v0, v1, v2, &dist, NULL)
# else		# else
isect_ray_tri_epsilon_v3(ray->origin, ray->direction, v0, v1, v2, &dist, NULL, FLT_EPSILON)		isect_ray_tri_epsilon_v3(ray->origin, ray->direction, v0, v1, v2, &dist, NULL, FLT_EPSILON)
# endif		# endif
) {		) {
if (dist >= 0.0f) {		if (dist >= 0.0f) {
# ifdef USE_DUMP
printf("%s:\n", __func__);
print_v3(" origin", ray->origin);		print_v3(" origin", ray->origin);
print_v3(" direction", ray->direction);		print_v3(" direction", ray->direction);
printf(" dist %f\n", dist);		CLOG_BMESH_INTERSECT(0, " dist %f", dist);
print_v3(" v0", v0);		print_v3(" v0", v0);
print_v3(" v1", v1);		print_v3(" v1", v1);
print_v3(" v2", v2);		print_v3(" v2", v2);
# endif

# ifdef USE_DUMP		CLOG_BMESH_INTERSECT(0, "Adding depth %f", dist);
printf("%s: Adding depth %f\n", __func__, dist);
# endif
BLI_buffer_append(raycast_data->z_buffer, float, dist);		BLI_buffer_append(raycast_data->z_buffer, float, dist);
}		}
}		}
}		}

static int isect_bvhtree_point_v3(BVHTree tree, const float *looptris, const float co[3])		static int isect_bvhtree_point_v3(BVHTree tree, const float *looptris, const float co[3])
{		{
BLI_buffer_declare_static(float, z_buffer, BLI_BUFFER_NOP, 64);		BLI_buffer_declare_static(float, z_buffer, BLI_BUFFER_NOP, 64);
Show All 9 Lines	static int isect_bvhtree_point_v3(BVHTree tree, const float *looptris, const float co[3])
* This is to make it so kd-tree believes we didn't intersect anything and		* This is to make it so kd-tree believes we didn't intersect anything and
* keeps calling the intersect callback.		* keeps calling the intersect callback.
*/		*/
hit.index = -1;		hit.index = -1;
hit.dist = BVH_RAYCAST_DIST_MAX;		hit.dist = BVH_RAYCAST_DIST_MAX;

BLI_bvhtree_ray_cast(tree, co, dir, 0.0f, &hit, raycast_callback, &raycast_data);		BLI_bvhtree_ray_cast(tree, co, dir, 0.0f, &hit, raycast_callback, &raycast_data);

# ifdef USE_DUMP		CLOG_BMESH_INTERSECT(0, "Total intersections: %zu", z_buffer.count);
printf("%s: Total intersections: %zu\n", __func__, z_buffer.count);
# endif

int num_isect;		int num_isect;

if (z_buffer.count == 0) {		if (z_buffer.count == 0) {
num_isect = 0;		num_isect = 0;
}		}
else if (z_buffer.count == 1) {		else if (z_buffer.count == 1) {
num_isect = 1;		num_isect = 1;
▲ Show 20 Lines • Show All 103 Lines • ▼ Show 20 Lines
#ifdef USE_DISSOLVE		#ifdef USE_DISSOLVE
if (use_dissolve) {		if (use_dissolve) {
BM_mesh_elem_hflag_disable_all(bm, BM_EDGE \| BM_VERT, BM_ELEM_TAG, false);		BM_mesh_elem_hflag_disable_all(bm, BM_EDGE \| BM_VERT, BM_ELEM_TAG, false);
}		}
#else		#else
UNUSED_VARS(use_dissolve);		UNUSED_VARS(use_dissolve);
#endif		#endif

#ifdef USE_DUMP		CLOG_BMESH_INTERSECT(0, "data = [");
printf("data = [\n");
#endif

if (boolean_mode != BMESH_ISECT_BOOLEAN_NONE) {		if (boolean_mode != BMESH_ISECT_BOOLEAN_NONE) {
/* keep original geometrty for raycast callbacks */		/* keep original geometrty for raycast callbacks */
float **cos;		float **cos;
int i, j;		int i, j;

cos = MEM_mallocN((size_t)looptris_tot * sizeof(looptri_coords) 3, __func__);		cos = MEM_mallocN((size_t)looptris_tot * sizeof(looptri_coords) 3, __func__);
for (i = 0, j = 0; i < looptris_tot; i++) {		for (i = 0, j = 0; i < looptris_tot; i++) {
▲ Show 20 Lines • Show All 57 Lines • ▼ Show 20 Lines	# ifdef DEBUG
}		}
# endif		# endif
overlap = BLI_bvhtree_overlap_ex(tree_b, tree_a, &tree_overlap_tot, NULL, NULL, 0, flag);		overlap = BLI_bvhtree_overlap_ex(tree_b, tree_a, &tree_overlap_tot, NULL, NULL, 0, flag);

if (overlap) {		if (overlap) {
uint i;		uint i;

for (i = 0; i < tree_overlap_tot; i++) {		for (i = 0; i < tree_overlap_tot; i++) {
# ifdef USE_DUMP		CLOG_BMESH_INTERSECT(0, " ((%d, %d), (", overlap[i].indexA, overlap[i].indexB);
printf(" ((%d, %d), (\n", overlap[i].indexA, overlap[i].indexB);
# endif
bm_isect_tri_tri(&s,		bm_isect_tri_tri(&s,
overlap[i].indexA,		overlap[i].indexA,
overlap[i].indexB,		overlap[i].indexB,
looptris[overlap[i].indexA],		looptris[overlap[i].indexA],
looptris[overlap[i].indexB],		looptris[overlap[i].indexB],
isect_tri_tri_no_shared);		isect_tri_tri_no_shared);
# ifdef USE_DUMP		CLOG_BMESH_INTERSECT(0, ")),");
printf(")),\n");
# endif
}		}
MEM_freeN(overlap);		MEM_freeN(overlap);
}		}

if (boolean_mode == BMESH_ISECT_BOOLEAN_NONE) {		if (boolean_mode == BMESH_ISECT_BOOLEAN_NONE) {
/* no booleans, just free immediate */		/* no booleans, just free immediate */
BLI_bvhtree_free(tree_a);		BLI_bvhtree_free(tree_a);
if (tree_a != tree_b) {		if (tree_a != tree_b) {
Show All 14 Lines	for (i_a = 0; i_a < looptris_tot; i_a++) {
}		}
}		}
else {		else {
if ((t_a != t_b) && !ELEM(-1, t_a, t_b)) {		if ((t_a != t_b) && !ELEM(-1, t_a, t_b)) {
continue;		continue;
}		}
}		}

# ifdef USE_DUMP		CLOG_BMESH_INTERSECT(0, " ((%d, %d), (", i_a, i_b);
printf(" ((%d, %d), (", i_a, i_b);
# endif
bm_isect_tri_tri(&s, i_a, i_b, looptris[i_a], looptris[i_b], isect_tri_tri_no_shared);		bm_isect_tri_tri(&s, i_a, i_b, looptris[i_a], looptris[i_b], isect_tri_tri_no_shared);
# ifdef USE_DUMP		CLOG_BMESH_INTERSECT(0, ")),");
printf(")),\n");
# endif
}		}
}		}
}		}
#endif /* USE_BVH */		#endif /* USE_BVH */

#ifdef USE_DUMP		CLOG_BMESH_INTERSECT(0, "]");
printf("]\n");
#endif

/* --------- */		/* --------- */

#ifdef USE_SPLICE		#ifdef USE_SPLICE
{		{
GHashIterator gh_iter;		GHashIterator gh_iter;

GHASH_ITER (gh_iter, s.edge_verts) {		GHASH_ITER (gh_iter, s.edge_verts) {
Show All 10 Lines	GHASH_ITER (gh_iter, s.edge_verts) {
/* direction is arbitrary, could be swapped */		/* direction is arbitrary, could be swapped */
v_start = e->v1;		v_start = e->v1;
v_end = e->v2;		v_end = e->v2;

if (v_ls_base->list_len > 1) {		if (v_ls_base->list_len > 1) {
edge_verts_sort(v_start->co, v_ls_base);		edge_verts_sort(v_start->co, v_ls_base);
}		}

# ifdef USE_DUMP		CLOG_BMESH_INTERSECT(
printf("# SPLITTING EDGE: %d, %u\n", BM_elem_index_get(e), v_ls_base->list_len);		0, "# SPLITTING EDGE: %d, %u", BM_elem_index_get(e), v_ls_base->list_len);
# endif
/* intersect */		/* intersect */
is_wire = BLI_gset_haskey(s.wire_edges, e);		is_wire = BLI_gset_haskey(s.wire_edges, e);

# ifdef USE_PARANOID		# ifdef USE_PARANOID
for (node = v_ls_base->list; node; node = node->next) {		for (node = v_ls_base->list; node; node = node->next) {
BMVert *_v = node->link;		BMVert *_v = node->link;
BLI_assert(len_squared_v3v3(_v->co, e->v1->co) > s.epsilon.eps_sq);		BLI_assert(len_squared_v3v3(_v->co, e->v1->co) > s.epsilon.eps_sq);
BLI_assert(len_squared_v3v3(_v->co, e->v2->co) > s.epsilon.eps_sq);		BLI_assert(len_squared_v3v3(_v->co, e->v2->co) > s.epsilon.eps_sq);
▲ Show 20 Lines • Show All 83 Lines • ▼ Show 20 Lines	for (node = s.vert_dissolve; node; node = node->next) {
}		}
else if ((!BM_elem_flag_test(v_a, BM_ELEM_TAG)) && (!BM_elem_flag_test(v_b, BM_ELEM_TAG))) {		else if ((!BM_elem_flag_test(v_a, BM_ELEM_TAG)) && (!BM_elem_flag_test(v_b, BM_ELEM_TAG))) {
/* simple case, single edge spans face */		/* simple case, single edge spans face */
BMVert **splice_pair;		BMVert **splice_pair;
BM_elem_flag_enable(e_pair[1], BM_ELEM_TAG);		BM_elem_flag_enable(e_pair[1], BM_ELEM_TAG);
splice_pair = STACK_PUSH_RET(splice_ls);		splice_pair = STACK_PUSH_RET(splice_ls);
splice_pair[0] = v;		splice_pair[0] = v;
splice_pair[1] = v_b;		splice_pair[1] = v_b;
# ifdef USE_DUMP		CLOG_BMESH_INTERSECT(0, "# Simple Case!");
printf("# Simple Case!\n");
# endif
}		}
else {		else {
# ifdef USE_PARANOID		# ifdef USE_PARANOID
BMEdge *e_keep;		BMEdge *e_keep;
# endif		# endif
BMEdge *e;		BMEdge *e;
BMEdge *e_step;		BMEdge *e_step;
BMVert *v_step;		BMVert *v_step;
Show All 36 Lines	# endif

e_next = bm_vert_other_edge(v_next, e_step);		e_next = bm_vert_other_edge(v_next, e_step);
e_step = e_next;		e_step = e_next;
v_step = v_next;		v_step = v_next;
BM_elem_flag_enable(e_step, BM_ELEM_TAG);		BM_elem_flag_enable(e_step, BM_ELEM_TAG);
# ifdef USE_PARANOID		# ifdef USE_PARANOID
BLI_assert(e_step != e_keep);		BLI_assert(e_step != e_keep);
# endif		# endif
# ifdef USE_DUMP		CLOG_BMESH_INTERSECT(0, "# walk step %p %p", e_next, v_next);
printf("# walk step %p %p\n", e_next, v_next);
# endif
}		}
# ifdef USE_PARANOID		# ifdef USE_PARANOID
BLI_assert(BM_elem_flag_test(e_keep, BM_ELEM_TAG) == 0);		BLI_assert(BM_elem_flag_test(e_keep, BM_ELEM_TAG) == 0);
# endif		# endif
}		}
}		}

/* Remove edges! */		/* Remove edges! */
▲ Show 20 Lines • Show All 169 Lines • ▼ Show 20 Lines	struct LoopFilterWrap user_data_wrap = {
.test_fn = test_fn,		.test_fn = test_fn,
.user_data = user_data,		.user_data = user_data,
};		};

groups_array = MEM_mallocN(sizeof(groups_array) (size_t)bm->totface, __func__);		groups_array = MEM_mallocN(sizeof(groups_array) (size_t)bm->totface, __func__);
group_tot = BM_mesh_calc_face_groups(		group_tot = BM_mesh_calc_face_groups(
bm, groups_array, &group_index, bm_loop_filter_fn, &user_data_wrap, 0, BM_EDGE);		bm, groups_array, &group_index, bm_loop_filter_fn, &user_data_wrap, 0, BM_EDGE);

#ifdef USE_DUMP		CLOG_BMESH_INTERSECT(0, "Total face-groups: %d", group_tot);
printf("%s: Total face-groups: %d\n", __func__, group_tot);
#endif

/* Check if island is inside/outside */		/* Check if island is inside/outside */
for (i = 0; i < group_tot; i++) {		for (i = 0; i < group_tot; i++) {
int fg = group_index[i][0];		int fg = group_index[i][0];
int fg_end = group_index[i][1] + fg;		int fg_end = group_index[i][1] + fg;
bool do_remove, do_flip;		bool do_remove, do_flip;

{		{
▲ Show 20 Lines • Show All 116 Lines • Show Last 20 Lines