Blender  V3.3
Classes | Macros | Typedefs | Functions
bmo_connect_pair.c File Reference
#include "MEM_guardedalloc.h"
#include "BLI_heap_simple.h"
#include "BLI_math.h"
#include "BLI_utildefines.h"
#include "bmesh.h"
#include "intern/bmesh_operators_private.h"
#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)
 

Typedefs

typedef struct PathContext PathContext
 
typedef struct PathLink PathLink
 
typedef struct PathLinkState PathLinkState
 

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 PathLinkStatestate_dupe_add (PathLinkState *state, const PathLinkState *state_orig)
 
static PathLinkStatestate_link_add_test (PathContext *pc, PathLinkState *state, const PathLinkState *state_orig, BMElem *ele, BMElem *ele_from)
 
static PathLinkStatestate_step__face_edges (PathContext *pc, PathLinkState *state, const PathLinkState *state_orig, BMLoop *l_iter, BMLoop *l_last, MinDistDir *mddir)
 
static PathLinkStatestate_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 Util

Simply getting the closest intersecting vert/edge is not good enough. see T43792 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
 
typedef struct MinDistDir MinDistDir
 
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.c.

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 T45582).
    • 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 40 of file bmo_connect_pair.c.

◆ 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)
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
#define ELE_TOUCHED
SyclQueue void void size_t num_bytes void

Definition at line 60 of file bmo_connect_pair.c.

◆ ELE_TOUCH_TEST_EDGE

#define ELE_TOUCH_TEST_EDGE (   e)    BMO_edge_flag_test(pc->bm_bmoflag, e, ELE_TOUCHED)

Definition at line 70 of file bmo_connect_pair.c.

◆ ELE_TOUCH_TEST_VERT

#define ELE_TOUCH_TEST_VERT (   v)    BMO_vert_flag_test(pc->bm_bmoflag, v, ELE_TOUCHED)

Definition at line 67 of file bmo_connect_pair.c.

◆ ELE_TOUCHED

#define ELE_TOUCHED   4

Definition at line 48 of file bmo_connect_pair.c.

◆ FACE_EXCLUDE

#define FACE_EXCLUDE   2

Definition at line 45 of file bmo_connect_pair.c.

◆ 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 50 of file bmo_connect_pair.c.

◆ MIN_DIST_DIR_INIT

#define MIN_DIST_DIR_INIT
Value:
{ \
{ \
FLT_MAX, FLT_MAX \
} \
}

Definition at line 130 of file bmo_connect_pair.c.

◆ VERT_EXCLUDE

#define VERT_EXCLUDE   2

Definition at line 42 of file bmo_connect_pair.c.

◆ VERT_OUT

#define VERT_OUT   1

Definition at line 41 of file bmo_connect_pair.c.

◆ 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 52 of file bmo_connect_pair.c.

Typedef Documentation

◆ MinDistDir

typedef struct MinDistDir MinDistDir

◆ PathContext

typedef struct PathContext PathContext

◆ PathLink

typedef struct PathLink PathLink

Single linked list where each item contains state and points to previous path item.

◆ PathLinkState

typedef struct PathLinkState PathLinkState

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

◆ bmo_connect_vert_pair_exec()

void bmo_connect_vert_pair_exec ( BMesh bm,
BMOperator op 
)

◆ min_dist_dir_test()

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

◆ min_dist_dir_update()

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

◆ 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 198 of file bmo_connect_pair.c.

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

◆ state_dupe_add()

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

Definition at line 288 of file bmo_connect_pair.c.

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

◆ state_isect_co_pair()

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

◆ state_link_add()

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

◆ state_link_add_test()

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

◆ 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 212 of file bmo_connect_pair.c.

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

◆ 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

◆ 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