path: root/source/blender/bmesh/tools/bmesh_path_region.c

/*
 * ***** BEGIN GPL LICENSE BLOCK *****
 *
 * 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.
 *
 * ***** END GPL LICENSE BLOCK *****
 */

/** \file blender/bmesh/tools/bmesh_path_region.c
 *  \ingroup bmesh
 *
 * Find the region defined by the path(s) between 2 elements.
 * (path isn't ordered).
 */

#include "MEM_guardedalloc.h"

#include "BLI_math.h"
#include "BLI_linklist.h"
#include "BLI_utildefines_stack.h"
#include "BLI_alloca.h"

#include "bmesh.h"
#include "bmesh_path_region.h"  /* own include */


/**
 * Special handling of vertices with 2 edges
 * (act as if the edge-chain is a single edge).
 *
 * \note Regarding manifold edge stepping: #BM_vert_is_edge_pair_manifold usage.
 * Logic to skip a chain of vertices is not applied at boundaries because it gives
 * strange behavior from a user perspective especially with boundary quads, see: T52701
 *
 * Restrict walking over a vertex chain to cases where the edges share the same faces.
 * This is more typical of what a user would consider a vertex chain.
 */
#define USE_EDGE_CHAIN


#ifdef USE_EDGE_CHAIN
/**
 * Takes a vertex with 2 edge users and assigns the vertices at each end-point,
 *
 * \return Success when \a v_end_pair values are set or false if the edges loop back on themselves.
 */
static bool bm_vert_pair_ends(BMVert *v_pivot, BMVert *v_end_pair[2])
{
	BMEdge *e = v_pivot->e;
	int j = 0;
	do {
		BMEdge *e_chain = e;
		BMVert *v_other = BM_edge_other_vert(e_chain, v_pivot);
		while (BM_vert_is_edge_pair_manifold(v_other)) {
			BMEdge *e_chain_next = BM_DISK_EDGE_NEXT(e_chain, v_other);
			BLI_assert(BM_DISK_EDGE_NEXT(e_chain_next, v_other) == e_chain);
			v_other = BM_edge_other_vert(e_chain_next, v_other);
			if (v_other == v_pivot) {
				return false;
			}
			e_chain = e_chain_next;
		}
		v_end_pair[j++] = v_other;
	} while ((e = BM_DISK_EDGE_NEXT(e, v_pivot)) != v_pivot->e);

	BLI_assert(j == 2);
	return true;
}
#endif  /* USE_EDGE_CHAIN */


/** \name Vertex in Region Checks
 * \{ */

static bool bm_vert_region_test(BMVert *v, int * const depths[2], const int pass)
{
	const int index = BM_elem_index_get(v);
	return (((depths[0][index] != -1) && (depths[1][index] != -1)) && \
	        ((depths[0][index]        +   depths[1][index]) < pass));
}

#ifdef USE_EDGE_CHAIN
static bool bm_vert_region_test_chain(BMVert *v, int * const depths[2], const int pass)
{
	BMVert *v_end_pair[2];
	if (bm_vert_region_test(v, depths, pass)) {
		return true;
	}
	else if (BM_vert_is_edge_pair_manifold(v) &&
	         bm_vert_pair_ends(v, v_end_pair) &&
	         bm_vert_region_test(v_end_pair[0], depths, pass) &&
	         bm_vert_region_test(v_end_pair[1], depths, pass))
	{
		return true;
	}

	return false;
}
#else
static bool bm_vert_region_test_chain(BMVert *v, int * const depths[2], const int pass)
{
	return bm_vert_region_test(v, depths, pass);
}
#endif

/** \} */


/**
 * Main logic for calculating region between 2 elements.
 *
 * This method works walking (breadth first) over all vertices,
 * keeping track of topological distance from the source.
 *
 * This is done in both directions, after that each vertices 'depth' is added to check
 * if its less than the number of passes needed to complete the search.
 * When it is, we know the path is one of possible paths that have the minimum topological distance.
 *
 * \note Only verts without BM_ELEM_TAG will be walked over.
 */
static LinkNode *mesh_calc_path_region_elem(
        BMesh *bm,
        BMElem *ele_src, BMElem *ele_dst,
        const char path_htype)
{
	int      ele_verts_len[2];
	BMVert **ele_verts[2];

	/* Get vertices from any `ele_src/ele_dst` elements. */
	for (int side = 0; side < 2; side++) {
		BMElem *ele = side ? ele_dst : ele_src;
		int j = 0;

		if (ele->head.htype == BM_FACE) {
			BMFace *f = (BMFace *)ele;
			ele_verts[side] = BLI_array_alloca(ele_verts[side], f->len);

			BMLoop *l_first, *l_iter;
			l_iter = l_first = BM_FACE_FIRST_LOOP(f);
			do {
				ele_verts[side][j++] = l_iter->v;
			} while ((l_iter = l_iter->next) != l_first);
		}
		else if (ele->head.htype == BM_EDGE) {
			BMEdge *e = (BMEdge *)ele;
			ele_verts[side] = BLI_array_alloca(ele_verts[side], 2);

			ele_verts[side][j++] = e->v1;
			ele_verts[side][j++] = e->v2;
		}
		else if (ele->head.htype == BM_VERT) {
			BMVert *v = (BMVert *)ele;
			ele_verts[side] = BLI_array_alloca(ele_verts[side], 1);

			ele_verts[side][j++] = v;
		}
		else {
			BLI_assert(0);
		}
		ele_verts_len[side] = j;
	}

	int *depths[2] = {NULL};
	int pass = 0;

	BMVert **stack       = MEM_mallocN(sizeof(*stack)       * bm->totvert, __func__);
	BMVert **stack_other = MEM_mallocN(sizeof(*stack_other) * bm->totvert, __func__);

	STACK_DECLARE(stack);
	STACK_INIT(stack, bm->totvert);

	STACK_DECLARE(stack_other);
	STACK_INIT(stack_other, bm->totvert);

	BM_mesh_elem_index_ensure(bm, BM_VERT);

	/* After exhausting all possible elements, we should have found all elements on the 'side_other'.
	 * otherwise, exit early. */
	bool found_all = false;

	for (int side = 0; side < 2; side++) {
		const int side_other = !side;

		/* initialize depths to -1 (un-touched), fill in with the depth as we walk over the edges. */
		depths[side] = MEM_mallocN(sizeof(*depths[side]) * bm->totvert, __func__);
		copy_vn_i(depths[side], bm->totvert, -1);

		/* needed for second side */
		STACK_CLEAR(stack);
		STACK_CLEAR(stack_other);

		for (int i = 0; i < ele_verts_len[side]; i++) {
			BMVert *v = ele_verts[side][i];
			depths[side][BM_elem_index_get(v)] = 0;
			if (v->e && !BM_elem_flag_test(v, BM_ELEM_TAG)) {
				STACK_PUSH(stack, v);
			}
		}

#ifdef USE_EDGE_CHAIN
		/* Expand initial state to end-point vertices when they only have 2x edges,
		 * this prevents odd behavior when source or destination are in the middle of a long chain of edges. */
		if (ELEM(path_htype, BM_VERT, BM_EDGE)) {
			for (int i = 0; i < ele_verts_len[side]; i++) {
				BMVert *v = ele_verts[side][i];
				BMVert *v_end_pair[2];
				if (BM_vert_is_edge_pair_manifold(v) && bm_vert_pair_ends(v, v_end_pair)) {
					for (int j = 0; j < 2; j++) {
						const int v_end_index = BM_elem_index_get(v_end_pair[j]);
						if (depths[side][v_end_index] == -1) {
							depths[side][v_end_index] = 0;
							if (!BM_elem_flag_test(v_end_pair[j], BM_ELEM_TAG)) {
								STACK_PUSH(stack, v_end_pair[j]);
							}
						}
					}
				}
			}
		}
#endif  /* USE_EDGE_CHAIN */

		/* Keep walking over connected geometry until we find all the vertices in `ele_verts[side_other]`,
		 * or exit the loop when theres no connection. */
		found_all = false;
		for (pass = 1; (STACK_SIZE(stack) != 0); pass++) {
			while (STACK_SIZE(stack) != 0) {
				BMVert *v_a = STACK_POP(stack);
				// const int v_a_index = BM_elem_index_get(v_a);  /* only for assert */
				BMEdge *e = v_a->e;

				do {
					BMVert *v_b = BM_edge_other_vert(e, v_a);
					int v_b_index = BM_elem_index_get(v_b);
					if (depths[side][v_b_index] == -1) {

#ifdef USE_EDGE_CHAIN
						/* Walk along the chain, fill in values until we reach a vertex with 3+ edges. */
						{
							BMEdge *e_chain = e;
							while (BM_vert_is_edge_pair_manifold(v_b) &&
							       ((depths[side][v_b_index] == -1)))
							{
								depths[side][v_b_index] = pass;

								BMEdge *e_chain_next = BM_DISK_EDGE_NEXT(e_chain, v_b);
								BLI_assert(BM_DISK_EDGE_NEXT(e_chain_next, v_b) == e_chain);
								v_b = BM_edge_other_vert(e_chain_next, v_b);
								v_b_index = BM_elem_index_get(v_b);
								e_chain = e_chain_next;
							}
						}
#endif  /* USE_EDGE_CHAIN */

						/* Add the other vertex to the stack, to be traversed in the next pass. */
						if (depths[side][v_b_index] == -1) {
#ifdef USE_EDGE_CHAIN
							BLI_assert(!BM_vert_is_edge_pair_manifold(v_b));
#endif
							BLI_assert(pass == depths[side][BM_elem_index_get(v_a)] + 1);
							depths[side][v_b_index] = pass;
							if (!BM_elem_flag_test(v_b, BM_ELEM_TAG)) {
								STACK_PUSH(stack_other, v_b);
							}
						}
					}
				} while ((e = BM_DISK_EDGE_NEXT(e, v_a)) != v_a->e);
			}

			/* Stop searching once theres none left.
			 * Note that this looks in-efficient, however until the target elements reached,
			 * it will exit immediately.
			 * After that, it takes as many passes as the element has edges to finish off. */
			found_all = true;
			for (int i = 0; i < ele_verts_len[side_other]; i++) {
				if (depths[side][BM_elem_index_get(ele_verts[side_other][i])] == -1) {
					found_all = false;
					break;
				}
			}
			if (found_all == true) {
				pass++;
				break;
			}

			STACK_SWAP(stack, stack_other);
		}

		/* if we have nothing left, and didn't find all elements on the other side,
		 * exit early and don't continue */
		if (found_all == false) {
			break;
		}
	}

	MEM_freeN(stack);
	MEM_freeN(stack_other);


	/* Now we have depths recorded from both sides,
	 * select elements that use tagged verts. */
	LinkNode *path = NULL;

	if (found_all == false) {
		/* fail! (do nothing) */
	}
	else if (path_htype == BM_FACE) {
		BMIter fiter;
		BMFace *f;

		BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) {
			if (!BM_elem_flag_test(f, BM_ELEM_TAG)) {
				/* check all verts in face are tagged */
				BMLoop *l_first, *l_iter;
				l_iter = l_first = BM_FACE_FIRST_LOOP(f);
				bool ok = true;
#if 0
				do {
					if (!bm_vert_region_test_chain(l_iter->v, depths, pass)) {
						ok = false;
						break;
					}
				} while ((l_iter = l_iter->next) != l_first);
#else
				/* Allowing a single failure on a face gives fewer 'gaps'.
				 * While correct, in practice they're often part of what a user would consider the 'region'. */
				int ok_tests = f->len > 3 ? 1 : 0;  /* how many times we may fail */
				do {
					if (!bm_vert_region_test_chain(l_iter->v, depths, pass)) {
						if (ok_tests == 0) {
							ok = false;
							break;
						}
						ok_tests--;
					}
				} while ((l_iter = l_iter->next) != l_first);
#endif

				if (ok) {
					BLI_linklist_prepend(&path, f);
				}
			}
		}
	}
	else if (path_htype == BM_EDGE) {
		BMIter eiter;
		BMEdge *e;

		BM_ITER_MESH (e, &eiter, bm, BM_EDGES_OF_MESH) {
			if (!BM_elem_flag_test(e, BM_ELEM_TAG)) {
				/* check all verts in edge are tagged */
				bool ok = true;
				for (int j = 0; j < 2; j++) {
					if (!bm_vert_region_test_chain(*((&e->v1) + j), depths, pass)) {
						ok = false;
						break;
					}
				}

				if (ok) {
					BLI_linklist_prepend(&path, e);
				}
			}
		}
	}
	else if (path_htype == BM_VERT) {
		BMIter viter;
		BMVert *v;

		BM_ITER_MESH (v, &viter, bm, BM_VERTS_OF_MESH) {
			if (bm_vert_region_test_chain(v, depths, pass)) {
				BLI_linklist_prepend(&path, v);
			}
		}
	}


	for (int side = 0; side < 2; side++) {
		if (depths[side]) {
			MEM_freeN(depths[side]);
		}
	}

	return path;
}

#undef USE_EDGE_CHAIN


/** \name Main Functions (exposed externally).
 * \{ */

LinkNode *BM_mesh_calc_path_region_vert(
        BMesh *bm, BMElem *ele_src, BMElem *ele_dst,
        bool (*filter_fn)(BMVert *, void *user_data), void *user_data)
{
	LinkNode *path = NULL;
	/* BM_ELEM_TAG flag is used to store visited verts */
	BMVert *v;
	BMIter viter;
	int i;

	BM_ITER_MESH_INDEX (v, &viter, bm, BM_VERTS_OF_MESH, i) {
		BM_elem_flag_set(v, BM_ELEM_TAG, !filter_fn(v, user_data));
		BM_elem_index_set(v, i); /* set_inline */
	}
	bm->elem_index_dirty &= ~BM_VERT;

	path = mesh_calc_path_region_elem(bm, ele_src, ele_dst, BM_VERT);

	return path;
}

LinkNode *BM_mesh_calc_path_region_edge(
        BMesh *bm, BMElem *ele_src, BMElem *ele_dst,
        bool (*filter_fn)(BMEdge *, void *user_data), void *user_data)
{
	LinkNode *path = NULL;
	/* BM_ELEM_TAG flag is used to store visited verts */
	BMEdge *e;
	BMIter eiter;
	int i;

	/* flush flag to verts */
	BM_mesh_elem_hflag_enable_all(bm, BM_VERT, BM_ELEM_TAG, false);

	BM_ITER_MESH_INDEX (e, &eiter, bm, BM_EDGES_OF_MESH, i) {
		bool test;
		BM_elem_flag_set(e, BM_ELEM_TAG, test = !filter_fn(e, user_data));

		/* flush tag to verts */
		if (test == false) {
			for (int j = 0; j < 2; j++) {
				BM_elem_flag_disable(*((&e->v1) + j), BM_ELEM_TAG);
			}
		}
	}

	path = mesh_calc_path_region_elem(bm, ele_src, ele_dst, BM_EDGE);

	return path;
}

LinkNode *BM_mesh_calc_path_region_face(
        BMesh *bm, BMElem *ele_src, BMElem *ele_dst,
        bool (*filter_fn)(BMFace *, void *user_data), void *user_data)
{
	LinkNode *path = NULL;
	/* BM_ELEM_TAG flag is used to store visited verts */
	BMFace *f;
	BMIter fiter;
	int i;

	/* flush flag to verts */
	BM_mesh_elem_hflag_enable_all(bm, BM_VERT, BM_ELEM_TAG, false);

	BM_ITER_MESH_INDEX (f, &fiter, bm, BM_FACES_OF_MESH, i) {
		bool test;
		BM_elem_flag_set(f, BM_ELEM_TAG, test = !filter_fn(f, user_data));

		/* flush tag to verts */
		if (test == false) {
			BMLoop *l_first, *l_iter;
			l_iter = l_first = BM_FACE_FIRST_LOOP(f);
			do {
				BM_elem_flag_disable(l_iter->v, BM_ELEM_TAG);
			} while ((l_iter = l_iter->next) != l_first);
		}
	}

	path = mesh_calc_path_region_elem(bm, ele_src, ele_dst, BM_FACE);

	return path;
}

/** \} */