#include <algorithm>
#include "MEM_guardedalloc.h"
#include "BLI_heap.h"
#include "BLI_math_base.h"
#include "BLI_math_geom.h"
#include "BLI_math_rotation.h"
#include "BLI_math_vector.h"
#include "BKE_customdata.hh"
#include "bmesh.hh"
#include "intern/bmesh_operators_private.hh"

Classes
struct	JoinEdgesState
struct	JoinEdgesNeighborItem
struct	JoinEdgesNeighborInfo

Macros
#define	ASSERT_VALID_ERROR_METRIC(val)
#define	FACE_OUT (1 << 0)
#define	FACE_INPUT (1 << 2)

Functions
static float	quad_calc_error (const float v1[3], const float v2[3], const float v3[3], const float v4[3])
static void	bm_edge_to_quad_verts (const BMEdge e, const BMVert r_v_quad[4])
static void	add_without_duplicates (JoinEdgesNeighborInfo &neighbor_info, BMEdge e, BMLoop l)
static void	add_neighbors (JoinEdgesNeighborInfo &neighbor_info, BMLoop *l_in_quad)
static void	rotate_to_plane (const JoinEdgesState &s, const BMVert quad_verts[4], const BMLoop l_shared, const float plane_normal[3], float r_quad_coordinates[4][3])
static float	compute_alignment (const JoinEdgesState &s, const float quad_a_vecs[4][3], const BMVert quad_b_verts[4], const BMLoop l_shared, const float plane_normal[3])
static void	reprioritize_join (JoinEdgesState &s, BMEdge e_merge, BMLoop l_shared, float neighbor_quad_vecs[4][3], const float neighbor_quad_error, const float neighbor_quad_normal[3])
static void	reprioritize_face_neighbors (JoinEdgesState &s, BMFace *f, float f_error)
static BMFace *	bm_faces_join_pair_by_edge (BMesh bm, BMEdge e)
void	bmo_join_triangles_exec (BMesh bm, BMOperator op)
Delimit processing
static bool	bm_edge_is_contiguous_loop_cd_all (const BMEdge e, const DelimitData_CD delimit_data)
static bool	bm_edge_delimit_cdata (CustomData ldata, eCustomDataType type, DelimitData_CD r_delim_cd)
static DelimitData	bm_edge_delmimit_data_from_op (BMesh bm, BMOperator op)
static bool	bm_edge_is_delimit (const BMEdge e, const DelimitData delimit_data)

Variables
constexpr float	maximum_improvement = 0.99f

Detailed Description

Convert triangle to quads.

TODO

convert triangles to any sided faces, not just quads.

Definition in file bmo_join_triangles.cc.

Macro Definition Documentation

◆ ASSERT_VALID_ERROR_METRIC

#define ASSERT_VALID_ERROR_METRIC ( val )

Value:

BLI_assert(isfinite(val) && (val) >= 0 && (val) <= 2 * M_PI)

BLI_assert

#define BLI_assert(a)

Definition BLI_assert.h:46

M_PI

#define M_PI

Definition BLI_math_constants.h:21

Used to keep track of our math for the error values and ensure it's not getting out of control.

Definition at line 33 of file bmo_join_triangles.cc.

Referenced by compute_alignment(), quad_calc_error(), and reprioritize_join().

◆ FACE_INPUT

#define FACE_INPUT (1 << 2)

Definition at line 82 of file bmo_join_triangles.cc.

Referenced by bmo_join_triangles_exec().

◆ FACE_OUT

#define FACE_OUT (1 << 0)

Definition at line 81 of file bmo_join_triangles.cc.

Function Documentation

◆ add_neighbors()

void add_neighbors	(	JoinEdgesNeighborInfo &	neighbor_info,
		BMLoop *	l_in_quad )

static

Add the neighboring edges of a given loop to the merge_edges and shared_loops arrays.

Parameters

merge_edges	the array of mergeable edges to add to.
shared_loops	the array to shared loops to add to.
count	the number of items currently in each array.
l_in_quad	The loop to add the neighboring edges of, if they check out.

Definition at line 517 of file bmo_join_triangles.cc.

References add_without_duplicates(), ARRAY_SIZE, BLI_assert, BM_edge_is_manifold(), BMLoop::e, BMLoop::f, i, JoinEdgesNeighborInfo::items_num, BMFace::len, BMLoop::next, BMLoop::prev, and BMLoop::radial_next.

Referenced by reprioritize_face_neighbors().

◆ add_without_duplicates()

void add_without_duplicates	(	JoinEdgesNeighborInfo &	neighbor_info,
		BMEdge *	e,
		BMLoop *	l )

static

Adds edges and loops to an array of neighbors, but won't add duplicates a second time.

This function is necessary because otherwise the 3rd edge attached to a 3-pole at the corner of a freshly merged quad might be seen as a neighbor of both the quad edges it touches, (depending on the triangulation), and might get double the improvement it deserves.

Parameters

merge_edges	the array to add the merge edges to
shared_loops	the array to add the shared loops to
count	the number of items currently in each array.
e	The new merge edge to add to the array, if it's not a duplicate.
l	The new shared loop to add to the array, if the edge isn't a duplicate

Definition at line 489 of file bmo_join_triangles.cc.

References ARRAY_SIZE, BLI_assert, e, JoinEdgesNeighborItem::e, JoinEdgesNeighborInfo::items, JoinEdgesNeighborInfo::items_num, JoinEdgesNeighborItem::l, and l.

Referenced by add_neighbors().

◆ bm_edge_delimit_cdata()

bool bm_edge_delimit_cdata	(	CustomData *	ldata,
		eCustomDataType	type,
		DelimitData_CD *	r_delim_cd )

static

Looks up delimit data from custom data. Used to delimit by color or UV.

Definition at line 315 of file bmo_join_triangles.cc.

References CustomData_get_n_offset(), CustomData_number_of_layers(), and CustomData_sizeof().

Referenced by bm_edge_delmimit_data_from_op().

◆ bm_edge_delmimit_data_from_op()

DelimitData bm_edge_delmimit_data_from_op	(	BMesh *	bm,
		BMOperator *	op )

static

Setup the delimit data from the parameters provided to the operator.

Parameters

bm	The mesh to provide UV or color data.
op	The operator to provide the parameters.

Definition at line 333 of file bmo_join_triangles.cc.

References bm, bm_edge_delimit_cdata(), BMO_slot_bool_get(), BMO_slot_float_get(), CD_PROP_BYTE_COLOR, CD_PROP_FLOAT2, cosf, DEG2RADF, and BMOperator::slots_in.

Referenced by bmo_join_triangles_exec().

◆ bm_edge_is_contiguous_loop_cd_all()

bool bm_edge_is_contiguous_loop_cd_all	(	const BMEdge *	e,
		const DelimitData_CD *	delimit_data )

static

Determines if the loop custom-data is contiguous.

Definition at line 300 of file bmo_join_triangles.cc.

References BM_edge_is_contiguous_loop_cd(), and e.

Referenced by bm_edge_is_delimit().

◆ bm_edge_is_delimit()

bool bm_edge_is_delimit	(	const BMEdge *	e,
		const DelimitData *	delimit_data )

static

Computes if an edge is a delimit edge, therefore should not be considered for merging.

Parameters

e	the edge to check
delimit_data	the delimit configuration

Returns: true, if the edge is a delimit edge.

Definition at line 385 of file bmo_join_triangles.cc.

References angle(), angle_normalized_v3v3(), BM_edge_is_contiguous(), bm_edge_is_contiguous_loop_cd_all(), bm_edge_to_quad_verts(), BM_elem_flag_test, BM_ELEM_SEAM, BM_ELEM_SMOOTH, dot_v3v3(), e, fabsf, i, is_quad_flip_v3(), M_PI_2, BMFace::mat_nr, BMFace::no, normalize_v3(), sub_v3_v3v3(), and verts.

Referenced by bmo_join_triangles_exec().

◆ bm_edge_to_quad_verts()

void bm_edge_to_quad_verts	(	const BMEdge *	e,
		const BMVert *	r_v_quad[4] )

static

Get the corners of the quad that would result after an edge merge.

Parameters

e	An edge to be merged. It must be manifold and have triangles on either side.
r_v_quad	An array of vertices to return the corners.

Definition at line 256 of file bmo_join_triangles.cc.

References BLI_assert, BM_edge_is_manifold(), and e.

Referenced by bm_edge_is_delimit(), bmo_join_triangles_exec(), and reprioritize_join().

◆ bm_faces_join_pair_by_edge()

BMFace * bm_faces_join_pair_by_edge	(	BMesh *	bm,
		BMEdge *	e )

static

Given a manifold edge, join the triangles on either side to form a quad.

Parameters

s	State information about the join_triangles process
e	the edge to merge. It must be manifold.

Returns: the face that resulted, or nullptr if the merge was rejected.

Definition at line 924 of file bmo_join_triangles.cc.

References AT, BLI_assert, BLI_assert_msg, bm, BM_edge_is_manifold(), BM_faces_join_pair(), e, BMLoop::f, l_b, and BMFace::len.

Referenced by bmo_join_triangles_exec().

◆ bmo_join_triangles_exec()

void bmo_join_triangles_exec	(	BMesh *	bm,
		BMOperator *	op )

Given a mesh, convert triangles to quads.

Definition at line 967 of file bmo_join_triangles.cc.

References BLI_assert, BLI_heap_free(), BLI_heap_insert(), BLI_heap_is_empty(), BLI_heap_new(), BLI_heap_pop_min(), BLI_heap_top_value(), bm, bm_edge_delmimit_data_from_op(), BM_edge_face_pair(), bm_edge_is_delimit(), bm_edge_to_quad_verts(), BM_EDGES_OF_MESH, BM_elem_index_set, BM_FACE, BM_face_as_array_vert_quad(), bm_faces_join_pair_by_edge(), BM_FACES_OF_MESH, BM_ITER_MESH, BM_ITER_MESH_INDEX, BMO_face_flag_disable, BMO_face_flag_enable, BMO_face_flag_test, BMO_ITER, BMO_slot_bool_get(), BMO_slot_buffer_from_enabled_flag(), BMO_slot_float_get(), BMO_slot_int_get(), e, JoinEdgesState::edge_queue, JoinEdgesState::edge_queue_nodes, FACE_INPUT, FACE_OUT, i, BMFace::len, maximum_improvement, MEM_freeN(), MEM_malloc_arrayN(), quad_calc_error(), reprioritize_face_neighbors(), JoinEdgesState::select_tris_only, BMOperator::slots_in, BMOperator::slots_out, JoinEdgesState::topo_influnce, and JoinEdgesState::use_topo_influence.

◆ compute_alignment()

float compute_alignment	(	const JoinEdgesState &	s,
		const float	quad_a_vecs[4][3],
		const BMVert *	quad_b_verts[4],
		const BMLoop *	l_shared,
		const float	plane_normal[3] )

static

Given a pair of quads, compute how well aligned they are.

Computes a float, indicating alignment.

regular grids of squares have pairs with alignments near 1.
regular grids of parallelograms also have pairs with alignments near 1.
mismatched combinations of squares, diamonds, parallelograms, trapezoids, etc have alignments near 0.
however, pairs of quads which lie in perpendicular or opposite-facing planes can still have good alignments. In other words, pairs of quads which share an edge that defines a sharp corner on a mesh can still have good alignment, if the quads flow over the corner in a natural way. The sharp corner alone is not a penalty.

Parameters

s	State information about the join_triangles process.
quad_a_vecs	an array of four unit vectors. These are not the coordinates of the four vertices of quad_a. Instead, They are four unit vectors, aligned parallel to the respective edge loop of quad_a.
quad_b_verts	an array of four vertices, giving the four corners of quad_b.
l_shared	a loop known to be one of the common manifold loops that is shared between the two quads. This is used as a 'hinge' to flatten the two quads into the same plane as much as possible.
plane_normal	The normal vector of quad_a.

Returns: the computed alignment

Note: Since we test quad A against up to eight other quads, we precompute and pass in the quad_a_vecs, instead of starting with verts, and having to recompute the same numbers eight different times. That is why the quad_a_vecs and quad_b_verts have different type definitions.

Definition at line 642 of file bmo_join_triangles.cc.

References angle_normalized_v3v3(), ARRAY_SIZE, ASSERT_VALID_ERROR_METRIC, copy_v3_v3(), error(), fabsf, i, M_PI, normalize_v3(), rotate_to_plane(), and sub_v3_v3v3().

Referenced by reprioritize_join().

◆ quad_calc_error()

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

static

Computes error of a proposed merge quad. Quads with the lowest error are merged first.

A quad that is a flat plane has lower error.

A quad with four corners that are all right angles has lower error. Note parallelograms are higher error than squares or rectangles.

A quad that is concave has higher error.

Parameters

v1,v2,v3,v4 The four corner coordinates of the quad.

Returns: The computed error associated with the quad.

Definition at line 171 of file bmo_join_triangles.cc.

References angle_normalized_v3v3(), area_tri_v3(), ASSERT_VALID_ERROR_METRIC, compare_v3v3(), diff(), error(), fabsf, M_PI, M_PI_2, max_ff(), min_ff(), normal_tri_v3(), normalize_v3(), sub_v3_v3v3(), and v2.

Referenced by bmo_join_triangles_exec().

◆ reprioritize_face_neighbors()

void reprioritize_face_neighbors	(	JoinEdgesState &	s,
		BMFace *	f,
		float	f_error )

static

Given a face, find merge_edges which are being considered for merge and improve them

Parameters

s	State information about the join_triangles process.
f	A quad.
f_error	The current error of the face.

Definition at line 872 of file bmo_join_triangles.cc.

References add_neighbors(), ARRAY_SIZE, BLI_assert, BM_face_as_array_loop_quad(), BMVert::co, JoinEdgesNeighborItem::e, i, JoinEdgesNeighborInfo::items, JoinEdgesNeighborInfo::items_num, JoinEdgesNeighborItem::l, BMFace::len, BMFace::no, normalize_v3(), reprioritize_join(), sub_v3_v3v3(), BMLoop::v, and v.

Referenced by bmo_join_triangles_exec().

◆ reprioritize_join()

void reprioritize_join	(	JoinEdgesState &	s,
		BMEdge *	e_merge,
		BMLoop *	l_shared,
		float	neighbor_quad_vecs[4][3],
		const float	neighbor_quad_error,
		const float	neighbor_quad_normal[3] )

static

Lowers the error of an edge because of its proximity to a known good quad.

This function is the core of the entire topology_influence algorithm.

This function allows an existing, good quad to influence the topology around it. This means a quad with a higher error can end up preferred - when it creates better topology - even though there might be an alternate quad with lower numerical error.

This algorithm reduces the error of a given edge based on three factors:

The error of the neighboring quad. The better the neighbor quad, the more the impact.
The alignment of the proposed new quad the existing quad. Grids of rectangles or trapezoids improve well. Trapezoids and diamonds are left alone.
topology_influence. The higher the operator parameter is set, the more the impact. To help counteract the alignment penalty, topology_influence is permitted to exceed 100%.

Because of the reduction due to misalignment, this will reduce the error of an edge, to be closer to the error of the known good quad, and increase its changes of being merged sooner. However, some of the edge's error always remains - it never is made equal to the lower error from the good face. This means the influence of an exceptionally good quad will fade away with each successive, neighbor, instead of affecting the entire mesh. This is desirable.

Parameters

s	State information about the join_triangles process
e_merge	the edge to improve
l_shared	the edge that is common between the two faces
neighbor_quad_vecs	four unit vectors, aligned to the four loops around the good quad
neighbor_quad_error	the error of the neighbor quad
neighbor_quad_normal	the normal vector of the good quad

Definition at line 759 of file bmo_join_triangles.cc.

References ASSERT_VALID_ERROR_METRIC, BLI_assert, BLI_heap_node_value(), BLI_heap_node_value_update(), bm_edge_to_quad_verts(), BM_elem_index_get, BMO_face_flag_enable, compute_alignment(), JoinEdgesState::edge_queue, JoinEdgesState::edge_queue_nodes, BMLoop::f, FACE_OUT, BMEdge::l, maximum_improvement, printf, BMLoop::radial_next, and JoinEdgesState::topo_influnce.

Referenced by reprioritize_face_neighbors().

◆ rotate_to_plane()

void rotate_to_plane	(	const JoinEdgesState &	s,
		const BMVert *	quad_verts[4],
		const BMLoop *	l_shared,
		const float	plane_normal[3],
		float	r_quad_coordinates[4][3] )

static

Compute the coordinates of a quad that would result from an edge join, if that quad was rotated into the same plane as the existing quad next to it.

Parameters

s	State information about the join_triangles process
quad_verts	Four vertices of a quad, which has l_shared as one of its edges
l_shared	the 'hinge' loop, shared with the neighbor, that lies in the plane.
plane_normal	The normal vector of the plane to rotate the quad to lie aligned with
r_quad_coordinates	An array of coordinates to return the four corrected vertex locations

Definition at line 565 of file bmo_join_triangles.cc.

References add_v3_v3(), angle(), angle_signed_on_axis_v3v3_v3(), BMVert::co, copy_v3_v3(), ELEM, i, BMLoop::next, normal_quad_v3(), normalize_v3(), printf, RAD2DEGF, rotate_normalized_v3_v3v3fl(), sub_v3_v3v3(), UNUSED_VARS, and BMLoop::v.

Referenced by compute_alignment().

Variable Documentation

◆ maximum_improvement

float maximum_improvement = 0.99f

constexpr

Improvement ranges from 0..1. Never improve fully, limit at 99% improvement.

If you allow 100% improvement around an existing quad, then all the quad's neighbors end up improved to the with the exact same value. When this occurs, the relative quality of the edges is lost. Keeping 1% of the original error is enough to maintain relative sorting.

Definition at line 92 of file bmo_join_triangles.cc.

Referenced by bmo_join_triangles_exec(), and reprioritize_join().

Classes

Macros

Functions

Variables

Detailed Description

Macro Definition Documentation

◆ ASSERT_VALID_ERROR_METRIC

◆ FACE_INPUT

◆ FACE_OUT

Function Documentation

◆ add_neighbors()

◆ add_without_duplicates()

◆ bm_edge_delimit_cdata()

◆ bm_edge_delmimit_data_from_op()

◆ bm_edge_is_contiguous_loop_cd_all()

◆ bm_edge_is_delimit()

◆ bm_edge_to_quad_verts()

◆ bm_faces_join_pair_by_edge()

◆ bmo_join_triangles_exec()

◆ compute_alignment()

◆ quad_calc_error()

◆ reprioritize_face_neighbors()

◆ reprioritize_join()

◆ rotate_to_plane()

Variable Documentation

◆ maximum_improvement