#include "BLI_heap.h"
#include "BLI_math.h"
#include "BLI_polyfill_2d_beautify.h"
#include "MEM_guardedalloc.h"
#include "bmesh.h"
#include "bmesh_beautify.h"

Classes
struct	EdRotState

Macros
#define	EDGE_ORD(v0, v1)

Typedefs
typedef struct EdRotState	EdRotState

Functions
static GSet *	erot_gset_new (void)

static void	erot_state_ex (const BMEdge *e, int v_index[2], int f_index[2])

static void	erot_state_current (const BMEdge e, EdRotState e_state)

static void	erot_state_alternate (const BMEdge e, EdRotState e_state)

static float	bm_edge_calc_rotate_beauty__area (const float v1[3], const float v2[3], const float v3[3], const float v4[3], const bool lock_degenerate)

static float	bm_edge_calc_rotate_beauty__angle (const float v1[3], const float v2[3], const float v3[3], const float v4[3])

float	BM_verts_calc_rotate_beauty (const BMVert v1, const BMVert v2, const BMVert v3, const BMVert v4, const short flag, const short method)

static float	bm_edge_calc_rotate_beauty (const BMEdge *e, const short flag, const short method)

BLI_INLINE bool	edge_in_array (const BMEdge e, const BMEdge *edge_array, const int edge_array_len)

static void	bm_edge_update_beauty_cost_single (BMEdge e, Heap eheap, HeapNode eheap_table, GSet edge_state_arr, const BMEdge **edge_array, const int edge_array_len, const short flag, const short method)

static void	bm_edge_update_beauty_cost (BMEdge e, Heap eheap, HeapNode eheap_table, GSet edge_state_arr, const BMEdge **edge_array, const int edge_array_len, const short flag, const short method)

void	BM_mesh_beautify_fill (BMesh bm, BMEdge *edge_array, const int edge_array_len, const short flag, const short method, const short oflag_edge, const short oflag_face)

Detailed Description

Beautify the mesh by rotating edges between triangles to more attractive positions until no more rotations can be made.

In principle this is very simple however there is the possibility of going into an eternal loop where edges keep rotating. To avoid this - each edge stores a set of it previous states so as not to rotate back.

TODO

Take face normals into account.

Definition in file bmesh_beautify.c.

Macro Definition Documentation

◆ EDGE_ORD

#define EDGE_ORD	(	v0,
		v1
	)

Value:

  if (v0 > v1) { \
    SWAP(int, v0, v1); \
  } \
  (void)0

Definition at line 104 of file bmesh_beautify.c.

Typedef Documentation

◆ EdRotState

typedef struct EdRotState EdRotState

Function Documentation

◆ bm_edge_calc_rotate_beauty()

static float bm_edge_calc_rotate_beauty	(	const BMEdge *	e,
		const short	flag,
		const short	method
	)

static

Definition at line 277 of file bmesh_beautify.c.

References BM_verts_calc_rotate_beauty(), e, v1, and v2.

Referenced by bm_edge_update_beauty_cost_single(), and BM_mesh_beautify_fill().

◆ bm_edge_calc_rotate_beauty__angle()

static float bm_edge_calc_rotate_beauty__angle	(	const float	v1[3],
		const float	v2[3],
		const float	v3[3],
		const float	v4[3]
	)

static

Definition at line 210 of file bmesh_beautify.c.

References angle_normalized_v3v3(), normal_tri_v3(), v1, and v2.

Referenced by BM_verts_calc_rotate_beauty().

◆ bm_edge_calc_rotate_beauty__area()

static float bm_edge_calc_rotate_beauty__area	(	const float	v1[3],
		const float	v2[3],
		const float	v3[3],
		const float	v4[3],
		const bool	lock_degenerate
	)

static

Check if input faces are already flipped. Logic for 'signum_i' addition is:

Accept:

(1, 1) or (-1, -1): same side (common case).
(-1/1, 0): one degenerate, OK since we may rotate into a valid state.

Ignore:

(-1, 1): opposite winding, ignore.
( 0, 0): both degenerate, ignore.

Note: The cross product is divided by 'no_scale' so the rotation calculation is scale independent.

Important to lock degenerate here, since the triangle pars will be projected into different 2D spaces. Allowing to rotate out of a degenerate state can flip the faces (when performed iteratively).

Definition at line 141 of file bmesh_beautify.c.

References add_v3_v3v3(), axis_dominant_v3_to_m3(), BLI_assert, BLI_polyfill_beautify_quad_rotate_calc_ex(), cross_tri_v2(), cross_tri_v3(), e, ELEM, eps, mul_v2_m3v3(), normalize_v3(), NULL, signum_i_ex(), UNLIKELY, v1, and v2.

Referenced by BM_verts_calc_rotate_beauty().

◆ bm_edge_update_beauty_cost()

static void bm_edge_update_beauty_cost	(	BMEdge *	e,
		Heap *	eheap,
		HeapNode **	eheap_table,
		GSet **	edge_state_arr,
		const BMEdge **	edge_array,
		const int	edge_array_len,
		const short	flag,
		const short	method
	)

static

Definition at line 345 of file bmesh_beautify.c.

References BLI_assert, BM_edge_face_count_is_equal, bm_edge_update_beauty_cost_single(), BMVert::e, and e.

Referenced by BM_mesh_beautify_fill().

◆ bm_edge_update_beauty_cost_single()

static void bm_edge_update_beauty_cost_single	(	BMEdge *	e,
		Heap *	eheap,
		HeapNode **	eheap_table,
		GSet **	edge_state_arr,
		const BMEdge **	edge_array,
		const int	edge_array_len,
		const short	flag,
		const short	method
	)

static

Definition at line 298 of file bmesh_beautify.c.

References BLI_assert, BLI_gset_haskey(), BLI_heap_insert(), BLI_heap_remove(), bm_edge_calc_rotate_beauty(), BM_edge_is_manifold(), BM_elem_index_get, e, edge_in_array(), erot_state_alternate(), and NULL.

Referenced by bm_edge_update_beauty_cost().

◆ BM_mesh_beautify_fill()

void BM_mesh_beautify_fill	(	BMesh *	bm,
		BMEdge **	edge_array,
		const int	edge_array_len,
		const short	flag,
		const short	method,
		const short	oflag_edge,
		const short	oflag_face
	)