#include <cstdlib>
#include <cstring>
#include "BLI_listbase.h"
#include "BLI_utildefines.h"
#include "bmesh.hh"
#include "bmesh_walkers_private.hh"

Functions
void *	BMW_begin (BMWalker walker, void start)

void	BMW_init (BMWalker walker, BMesh bm, int type, short mask_vert, short mask_edge, short mask_face, BMWFlag flag, int layer)
	Init Walker.

void	BMW_end (BMWalker *walker)
	End Walker.

void *	BMW_step (BMWalker *walker)
	Step Walker.

int	BMW_current_depth (BMWalker *walker)
	Walker Current Depth.

void *	BMW_walk (BMWalker *walker)
	Main Walking Function.

void *	BMW_current_state (BMWalker *walker)
	Current Walker State.

void	BMW_state_remove (BMWalker *walker)
	Remove Current Walker State.

void *	BMW_state_add (BMWalker *walker)
	Add a new Walker State.

void	BMW_reset (BMWalker *walker)
	Reset Walker.

Detailed Description

BMesh Walker API.

NOTE(@joeedh): Details on design.

Original design: walkers directly emulation recursive functions. functions save their state onto a BMWalker.worklist, and also add new states to implement recursive or looping behavior. Generally only one state push per call with a specific state is desired.

basic design pattern: the walker step function goes through its list of possible choices for recursion, and recurses (by pushing a new state) using the first non-visited one. This choice is the flagged as visited using the GHash. Each step may push multiple new states onto the BMWalker.worklist at once.

Walkers use tool flags, not header flags.
Walkers now use GHash for storing visited elements, rather than stealing flags. GHash can be rewritten to be faster if necessary, in the far future :) .
tools should ALWAYS have necessary error handling for if walkers fail.

Definition in file bmesh_walkers.cc.

Function Documentation

◆ BMW_begin()

void * BMW_begin	(	BMWalker *	walker,
		void *	start )

Definition at line 40 of file bmesh_walkers.cc.

References BMWalker::begin, BMWalker::begin_htype, BLI_assert, BMW_current_state(), and BMWalker::step.

Referenced by BM_mesh_decimate_unsubdivide_ex(), bmo_collapse_exec(), bmo_collapsecon_do_layer(), bmo_dissolve_faces_exec(), check_hole_in_region(), edgering_select(), view3d_preselect_mesh_edgering_update_edges_from_edge(), walker_deselect_nth(), walker_select(), and walker_select_count().

◆ BMW_current_depth()

int BMW_current_depth ( BMWalker * walker )

Walker Current Depth.

Returns the current depth of the walker.

Definition at line 123 of file bmesh_walkers.cc.

References BMWalker::depth.

Referenced by BM_mesh_decimate_unsubdivide_ex(), and walker_deselect_nth().

◆ BMW_current_state()

void * BMW_current_state ( BMWalker * walker )

Current Walker State.

Returns the first state from the walker state worklist. This state is the next in the worklist for processing.

Definition at line 141 of file bmesh_walkers.cc.

References BMWalker::depth, BMwGenericWalker::depth, ListBase::first, and BMWalker::states.

Referenced by BMW_begin(), bmw_ConnectedVertexWalker_yield(), bmw_EdgeboundaryWalker_yield(), bmw_EdgeLoopWalker_begin(), bmw_EdgeLoopWalker_yield(), bmw_EdgeringWalker_begin(), bmw_EdgeringWalker_yield(), bmw_FaceLoopWalker_begin(), bmw_FaceLoopWalker_yield(), bmw_FaceShellWalker_yield(), bmw_IslandboundWalker_step(), bmw_IslandboundWalker_yield(), bmw_IslandWalker_yield(), bmw_LoopShellWalker_yield(), bmw_LoopShellWireWalker_yield(), bmw_NonManifoldedgeWalker_yield(), BMW_reset(), BMW_state_remove(), bmw_UVEdgeWalker_yield(), bmw_VertShellWalker_yield(), and BMW_walk().

◆ BMW_end()

void BMW_end ( struct BMWalker * walker )

End Walker.

Frees a walker's worklist.

Definition at line 107 of file bmesh_walkers.cc.

References BLI_gset_free(), BLI_mempool_destroy(), BMWalker::visit_set, BMWalker::visit_set_alt, and BMWalker::worklist.

Referenced by BM_mesh_decimate_unsubdivide_ex(), bmo_collapse_exec(), bmo_collapsecon_do_layer(), bmo_dissolve_faces_exec(), check_hole_in_region(), edbm_select_linked_exec(), edbm_select_linked_pick_ex(), edgering_select(), view3d_preselect_mesh_edgering_update_edges_from_edge(), walker_deselect_nth(), walker_select(), and walker_select_count().

◆ BMW_init()

void BMW_init	(	struct BMWalker *	walker,
		BMesh *	bm,
		int	type,
		short	mask_vert,
		short	mask_edge,
		short	mask_face,
		BMWFlag	flag,
		int	layer )

Init Walker.

Allocates and returns a new mesh walker of a given type. The elements visited are filtered by the bitmask 'searchmask'.

Definition at line 49 of file bmesh_walkers.cc.

References BMWalker::begin, BMWalker::begin_htype, BLI_assert, BLI_gset_ptr_new(), BLI_listbase_clear(), BLI_mempool_create(), BLI_MEMPOOL_NOP, bm, BMWalker::bm, BM_EDGE, BM_FACE, BM_VERT, bm_walker_types, BMW_CUSTOM, BMW_MAXWALKERS, BMWalker::flag, flag, BMWalker::layer, BMWalker::mask_edge, BMWalker::mask_face, BMWalker::mask_vert, BMWalker::order, BMWalker::states, BMWalker::step, BMWalker::structsize, UNLIKELY, BMWalker::valid_mask, BMWalker::visit_set, BMWalker::visit_set_alt, BMWalker::worklist, and BMWalker::yield.

Referenced by BM_mesh_decimate_unsubdivide_ex(), bmo_collapse_exec(), bmo_collapsecon_do_layer(), bmo_dissolve_faces_exec(), check_hole_in_region(), edbm_select_linked_exec(), edbm_select_linked_pick_ex(), edgering_select(), view3d_preselect_mesh_edgering_update_edges_from_edge(), walker_deselect_nth(), walker_select(), and walker_select_count().

◆ BMW_reset()

void BMW_reset ( BMWalker * walker )

Reset Walker.

Frees all states from the worklist, resetting the walker for reuse in a new walk.

Definition at line 187 of file bmesh_walkers.cc.

References BLI_gset_clear(), BMW_current_state(), BMW_state_remove(), BMWalker::depth, BMWalker::visit_set, and BMWalker::visit_set_alt.

◆ BMW_state_add()

void * BMW_state_add ( BMWalker * walker )

Add a new Walker State.

Allocate a new empty state and put it on the worklist. A pointer to the new state is returned so that the caller can fill in the state data. The new state will be inserted at the front for depth-first walks, and at the end for breadth-first walks.

Definition at line 168 of file bmesh_walkers.cc.

References BLI_addhead(), BLI_addtail(), BLI_assert, BLI_mempool_alloc(), BMW_BREADTH_FIRST, BMW_DEPTH_FIRST, BMWalker::depth, BMwGenericWalker::depth, BMWalker::order, BMWalker::states, and BMWalker::worklist.