bmo_connect_pair.cc File Reference

#include "MEM_guardedalloc.h"
#include "BLI_heap_simple.h"
#include "BLI_math_matrix.h"
#include "BLI_math_vector.h"
#include "BLI_utildefines.h"
#include "bmesh.hh"
#include "intern/bmesh_operators_private.hh"
#include "BLI_mempool.h"

Go to the source code of this file.

Classes
struct	PathContext
struct	PathLink
struct	PathLinkState
struct	MinDistDir

Macros
#define	CONNECT_EPS   0.0001f
#define	VERT_OUT   1
#define	VERT_EXCLUDE   2
#define	FACE_EXCLUDE   2
#define	ELE_TOUCHED   4
#define	FACE_WALK_TEST(f)    (CHECK_TYPE_INLINE(f, BMFace *), BMO_face_flag_test(pc->bm_bmoflag, f, FACE_EXCLUDE) == 0)
#define	VERT_WALK_TEST(v)    (CHECK_TYPE_INLINE(v, BMVert *), BMO_vert_flag_test(pc->bm_bmoflag, v, VERT_EXCLUDE) == 0)
#define	ELE_TOUCH_MARK(e)
#define	ELE_TOUCH_TEST_VERT(v)   BMO_vert_flag_test(pc->bm_bmoflag, v, ELE_TOUCHED)
#define	ELE_TOUCH_TEST_EDGE(e)   BMO_edge_flag_test(pc->bm_bmoflag, e, ELE_TOUCHED)

Functions
static int	state_isect_co_pair (const PathContext *pc, const float co_a[3], const float co_b[3])
static int	state_isect_co_exact (const PathContext *pc, const float co[3])
static float	state_calc_co_pair_fac (const PathContext *pc, const float co_a[3], const float co_b[3])
static void	state_calc_co_pair (const PathContext *pc, const float co_a[3], const float co_b[3], float r_co[3])
static bool	state_link_find (const PathLinkState *state, BMElem *ele)
static void	state_link_add (PathContext *pc, PathLinkState *state, BMElem *ele, BMElem *ele_from)
static PathLinkState *	state_dupe_add (PathLinkState *state, const PathLinkState *state_orig)
static PathLinkState *	state_link_add_test (PathContext *pc, PathLinkState *state, const PathLinkState *state_orig, BMElem *ele, BMElem *ele_from)
static PathLinkState *	state_step__face_edges (PathContext *pc, PathLinkState *state, const PathLinkState *state_orig, BMLoop *l_iter, BMLoop *l_last, MinDistDir *mddir)
static PathLinkState *	state_step__face_verts (PathContext *pc, PathLinkState *state, const PathLinkState *state_orig, BMLoop *l_iter, BMLoop *l_last, MinDistDir *mddir)
static bool	state_step (PathContext *pc, PathLinkState *state)
static void	bm_vert_pair_to_matrix (BMVert *v_pair[2], float r_unit_mat[3][3])
void	bmo_connect_vert_pair_exec (BMesh *bm, BMOperator *op)

Min Dist Dir Utilities
Simply getting the closest intersecting vert/edge is not good enough. see #43792 we need to get the closest in both directions since the absolute closest may be a dead-end. Logic is simple: First intersection, store the direction. Successive intersections will update the first distance if its aligned with the first hit. otherwise update the opposite distance. Caller stores best outcome in both directions.
#define	MIN_DIST_DIR_INIT
static int	min_dist_dir_test (MinDistDir *mddir, const float dist_dir[3], const float dist_sq)
static void	min_dist_dir_update (MinDistDir *dist, const float dist_dir[3])

Detailed Description

Connect vertex pair across multiple faces (splits faces).

Definition in file bmo_connect_pair.cc.

Macro Definition Documentation

CONNECT_EPS

#define CONNECT_EPS   0.0001f

Method for connecting across many faces.

• use the line between both verts and their normal average to construct a matrix.
• using the matrix, we can find all intersecting verts/edges.
• walk the connected data and find the shortest path.
  • store a heap of paths which are being scanned (PathContext.states).
  • continuously search the shortest path in the heap.
  • never step over the same element twice (tag elements as ELE_TOUCHED). this avoids going into an eternal loop if there are many possible branches (see #45582).
  • when running into a branch, create a new PathLinkState state and add to the heap.
  • when the target is reached, finish - since none of the other paths can be shorter than the one just found.
• if the connection can't be found - fail.
• with the connection found, split all edges tagging verts (or tag verts that sit on the intersection).
• run the standard connect operator.

Definition at line 43 of file bmo_connect_pair.cc.

Referenced by state_isect_co_exact(), and state_isect_co_pair().

ELE_TOUCH_MARK

#define ELE_TOUCH_MARK

(

e

)

Value:

  { \
    CHECK_TYPE_ANY(e, BMVert *, BMEdge *, BMElem *, BMElemF *); \
    BMO_elem_flag_enable(pc->bm_bmoflag, (BMElemF *)e, ELE_TOUCHED); \
  } \
  ((void)0)

Definition at line 63 of file bmo_connect_pair.cc.

Referenced by state_link_add().

ELE_TOUCH_TEST_EDGE

#define ELE_TOUCH_TEST_EDGE

(

e

)

BMO_edge_flag_test(pc->bm_bmoflag, e, ELE_TOUCHED)

Definition at line 73 of file bmo_connect_pair.cc.

Referenced by state_step__face_edges().

ELE_TOUCH_TEST_VERT

#define ELE_TOUCH_TEST_VERT

(

v

)

BMO_vert_flag_test(pc->bm_bmoflag, v, ELE_TOUCHED)

Definition at line 70 of file bmo_connect_pair.cc.

Referenced by state_step(), and state_step__face_verts().

ELE_TOUCHED

#define ELE_TOUCHED   4

Definition at line 51 of file bmo_connect_pair.cc.

FACE_EXCLUDE

#define FACE_EXCLUDE   2

Definition at line 48 of file bmo_connect_pair.cc.

Referenced by bmo_connect_vert_pair_exec().

FACE_WALK_TEST

#define FACE_WALK_TEST

(

f

)

(CHECK_TYPE_INLINE(f, BMFace *), BMO_face_flag_test(pc->bm_bmoflag, f, FACE_EXCLUDE) == 0)

Definition at line 53 of file bmo_connect_pair.cc.

Referenced by state_step(), state_step__face_edges(), and state_step__face_verts().

MIN_DIST_DIR_INIT

#define MIN_DIST_DIR_INIT

Value:

  { \
    { \
      FLT_MAX, FLT_MAX \
    } \
  }

Definition at line 133 of file bmo_connect_pair.cc.

Referenced by state_step().

VERT_EXCLUDE

#define VERT_EXCLUDE   2

Definition at line 45 of file bmo_connect_pair.cc.

Referenced by bmo_connect_vert_pair_exec().

VERT_OUT

#define VERT_OUT   1

Definition at line 44 of file bmo_connect_pair.cc.

Referenced by bmo_connect_vert_pair_exec().

VERT_WALK_TEST

#define VERT_WALK_TEST

(

v

)

(CHECK_TYPE_INLINE(v, BMVert *), BMO_vert_flag_test(pc->bm_bmoflag, v, VERT_EXCLUDE) == 0)

Definition at line 55 of file bmo_connect_pair.cc.

Referenced by state_step().

Function Documentation

bm_vert_pair_to_matrix()

static void bm_vert_pair_to_matrix ( BMVert * v_pair[2], float r_unit_mat[3][3] )

static

Get a orientation matrix from 2 vertices.

Definition at line 486 of file bmo_connect_pair.cc.

References add_v3_v3v3(), BM_ITER_ELEM, BM_LOOPS_OF_VERT, copy_v3_v3(), cross_v3_v3v3(), dot_v3v3(), eps, BMLoop::f, FLT_MAX, invert_m3(), l, negate_v3(), BMFace::no, nor, normalize_v3(), ortho_v3_v3(), project_plane_normalized_v3_v3v3(), sub_v3_v3v3(), unit_m3(), UNLIKELY, and zero_v2().

Referenced by bmo_connect_vert_pair_exec().

bmo_connect_vert_pair_exec()

void bmo_connect_vert_pair_exec	(	BMesh *	bm,
		BMOperator *	op )

Definition at line 588 of file bmo_connect_pair.cc.

References PathContext::axis_sep, BLI_assert, BLI_heapsimple_clear(), BLI_heapsimple_free(), BLI_heapsimple_insert(), BLI_heapsimple_is_empty(), BLI_heapsimple_len(), BLI_heapsimple_new(), BLI_heapsimple_pop_min(), BLI_mempool_create(), BLI_mempool_destroy(), BLI_MEMPOOL_NOP, bm, PathContext::bm_bmoflag, BM_EDGE, BM_edge_split(), BM_elem_index_get, BM_FACE, BM_VERT, bm_vert_pair_to_matrix(), BMO_op_exec(), BMO_op_finish(), BMO_op_initf(), BMO_slot_buffer_flag_enable(), BMO_slot_copy, BMO_slot_get(), BMO_vert_flag_enable, BMVert::co, BMOpSlot::data, dot_m3_v3_row_x(), e, PathLink::ele, FACE_EXCLUDE, BMElem::head, BMHeader::htype, BMOpSlot::len, PathLinkState::link_last, PathContext::link_pool, PathContext::matrix, MEM_callocN, MEM_freeN(), PathLink::next, op_sub(), BMOpSlot::p, printf, BMOperator::slots_in, state, state_calc_co_pair_fac(), state_link_add(), state_step(), PathContext::states, v, PathContext::v_pair, VERT_EXCLUDE, and VERT_OUT.

min_dist_dir_test()

static int min_dist_dir_test ( MinDistDir * mddir, const float dist_dir[3], const float dist_sq )

static

Definition at line 140 of file bmo_connect_pair.cc.

References MinDistDir::dir, MinDistDir::dist_min, dot_v3v3(), and FLT_MAX.

Referenced by state_step__face_edges(), and state_step__face_verts().

min_dist_dir_update()

static void min_dist_dir_update ( MinDistDir * dist, const float dist_dir[3] )

static

Definition at line 160 of file bmo_connect_pair.cc.

References copy_v3_v3(), MinDistDir::dir, MinDistDir::dist_min, and FLT_MAX.

Referenced by state_step__face_edges(), and state_step__face_verts().

state_calc_co_pair()

static void state_calc_co_pair ( const PathContext * pc, const float co_a[3], const float co_b[3], float r_co[3] )

static

Definition at line 201 of file bmo_connect_pair.cc.

References interp_v3_v3v3(), and state_calc_co_pair_fac().

Referenced by state_link_add(), and state_step__face_edges().

state_calc_co_pair_fac()

static float state_calc_co_pair_fac ( const PathContext * pc, const float co_a[3], const float co_b[3] )

static

Definition at line 189 of file bmo_connect_pair.cc.

References PathContext::axis_sep, dot_m3_v3_row_x(), fabsf, and PathContext::matrix.

Referenced by bmo_connect_vert_pair_exec(), and state_calc_co_pair().

state_dupe_add()

static PathLinkState * state_dupe_add ( PathLinkState * state, const PathLinkState * state_orig )

static

Definition at line 291 of file bmo_connect_pair.cc.

References MEM_mallocN, and state.

Referenced by state_link_add_test().

state_isect_co_exact()

static int state_isect_co_exact ( const PathContext * pc, const float co[3] )

static

Definition at line 183 of file bmo_connect_pair.cc.

References PathContext::axis_sep, CONNECT_EPS, diff(), dot_m3_v3_row_x(), fabsf, and PathContext::matrix.

Referenced by state_step(), and state_step__face_verts().

state_isect_co_pair()

static int state_isect_co_pair ( const PathContext * pc, const float co_a[3], const float co_b[3] )

static

Definition at line 169 of file bmo_connect_pair.cc.

References PathContext::axis_sep, CONNECT_EPS, dot_m3_v3_row_x(), fabsf, and PathContext::matrix.

Referenced by state_step__face_edges().

state_link_add()

static void state_link_add ( PathContext * pc, PathLinkState * state, BMElem * ele, BMElem * ele_from )

static

Definition at line 230 of file bmo_connect_pair.cc.

References BLI_assert, BLI_mempool_alloc(), BM_EDGE, BM_elem_index_get, BM_FACE, BM_VERT, copy_v3_v3(), PathLink::ele, PathLink::ele_from, ELE_TOUCH_MARK, BMElem::head, BMHeader::htype, len_v3v3(), PathContext::link_pool, PathLink::next, printf, state, state_calc_co_pair(), and state_link_find().

Referenced by bmo_connect_vert_pair_exec(), and state_link_add_test().

state_link_add_test()

static PathLinkState * state_link_add_test ( PathContext * pc, PathLinkState * state, const PathLinkState * state_orig, BMElem * ele, BMElem * ele_from )

static

Definition at line 298 of file bmo_connect_pair.cc.

References BLI_heapsimple_insert(), PathLinkState::link_last, state, state_dupe_add(), state_link_add(), and PathContext::states.

Referenced by state_step(), state_step__face_edges(), and state_step__face_verts().

state_link_find()

static bool state_link_find ( const PathLinkState * state, BMElem * ele )

static

Ideally we wouldn't need this and for most cases we don't. But when a face has vertices that are on the boundary more than once this becomes tricky.

Definition at line 215 of file bmo_connect_pair.cc.

References BLI_assert, BM_EDGE, BM_FACE, BM_VERT, PathLink::ele, ELEM, BMElem::head, BMHeader::htype, PathLink::next, and state.

Referenced by state_link_add().

state_step()

static bool state_step ( PathContext * pc, PathLinkState * state )

static

Definition at line 414 of file bmo_connect_pair.cc.

References BLI_assert, BM_EDGE, BM_edge_other_vert(), BM_EDGES_OF_VERT, BM_ITER_ELEM, BM_LOOPS_OF_EDGE, BM_LOOPS_OF_VERT, BM_VERT, BMVert::co, e, ELE_TOUCH_TEST_VERT, BMLoop::f, FACE_WALK_TEST, BMElem::head, BMHeader::htype, BMFace::len, PathLinkState::link_last, MIN_DIST_DIR_INIT, BMLoop::next, BMLoop::prev, state, state_isect_co_exact(), state_link_add_test(), state_step__face_edges(), state_step__face_verts(), v, and VERT_WALK_TEST.

Referenced by bmo_connect_vert_pair_exec().

state_step__face_edges()

static PathLinkState * state_step__face_edges ( PathContext * pc, PathLinkState * state, const PathLinkState * state_orig, BMLoop * l_iter, BMLoop * l_last, MinDistDir * mddir )

static

Definition at line 320 of file bmo_connect_pair.cc.

References BMVert::co, PathLinkState::co_prev, MinDistDir::dist_min, BMLoop::e, ELE_TOUCH_TEST_EDGE, BMLoop::f, FACE_WALK_TEST, len_squared_v3(), min_dist_dir_test(), min_dist_dir_update(), BMLoop::next, state, state_calc_co_pair(), state_isect_co_pair(), state_link_add_test(), sub_v3_v3v3(), and BMLoop::v.

Referenced by state_step().

state_step__face_verts()

static PathLinkState * state_step__face_verts ( PathContext * pc, PathLinkState * state, const PathLinkState * state_orig, BMLoop * l_iter, BMLoop * l_last, MinDistDir * mddir )

static

Definition at line 369 of file bmo_connect_pair.cc.

References BMVert::co, PathLinkState::co_prev, MinDistDir::dist_min, ELE_TOUCH_TEST_VERT, BMLoop::f, FACE_WALK_TEST, len_squared_v3(), min_dist_dir_test(), min_dist_dir_update(), BMLoop::next, state, state_isect_co_exact(), state_link_add_test(), sub_v3_v3v3(), and BMLoop::v.

Referenced by state_step().