#include <algorithm>
#include "MEM_guardedalloc.h"
#include "atomic_ops.h"
#include "BLI_array.hh"
#include "BLI_bitmap.h"
#include "BLI_function_ref.hh"
#include "BLI_math_geom.h"
#include "BLI_math_vector.h"
#include "BLI_task.hh"
#include "BLI_utildefines.h"
#include "BKE_customdata.hh"
#include "BKE_mesh.hh"
#include "BKE_mesh_mapping.hh"
#include "BLI_memarena.h"
#include "BLI_strict_flags.h"

Namespaces
namespace	blender
namespace	blender::bke
namespace	blender::bke::mesh

Functions
static Array< int >	blender::bke::mesh::create_reverse_offsets (const Span< int > indices, const int items_num)
static void	blender::bke::mesh::sort_small_groups (const OffsetIndices< int > groups, const int grain_size, MutableSpan< int > indices)
static Array< int >	blender::bke::mesh::reverse_indices_in_groups (const Span< int > group_indices, const OffsetIndices< int > offsets)
static void	blender::bke::mesh::reverse_group_indices_in_groups (const OffsetIndices< int > groups, const Span< int > group_to_elem, const OffsetIndices< int > offsets, MutableSpan< int > results)
static GroupedSpan< int >	blender::bke::mesh::gather_groups (const Span< int > group_indices, const int groups_num, Array< int > &r_offsets, Array< int > &r_indices)
Array< int >	blender::bke::mesh::build_corner_to_face_map (OffsetIndices< int > faces)
GroupedSpan< int >	blender::bke::mesh::build_vert_to_edge_map (Span< int2 > edges, int verts_num, Array< int > &r_offsets, Array< int > &r_indices)
void	blender::bke::mesh::build_vert_to_face_indices (OffsetIndices< int > faces, Span< int > corner_verts, OffsetIndices< int > offsets, MutableSpan< int > face_indices)
GroupedSpan< int >	blender::bke::mesh::build_vert_to_face_map (OffsetIndices< int > faces, Span< int > corner_verts, int verts_num, Array< int > &r_offsets, Array< int > &r_indices)
Array< int >	blender::bke::mesh::build_vert_to_corner_indices (Span< int > corner_verts, OffsetIndices< int > offsets)
GroupedSpan< int >	blender::bke::mesh::build_vert_to_corner_map (Span< int > corner_verts, int verts_num, Array< int > &r_offsets, Array< int > &r_indices)
GroupedSpan< int >	blender::bke::mesh::build_edge_to_corner_map (Span< int > corner_edges, int edges_num, Array< int > &r_offsets, Array< int > &r_indices)
GroupedSpan< int >	blender::bke::mesh::build_edge_to_face_map (OffsetIndices< int > faces, Span< int > corner_edges, int edges_num, Array< int > &r_offsets, Array< int > &r_indices)
Mesh Connectivity Mapping
UvVertMap *	BKE_mesh_uv_vert_map_create (blender::OffsetIndices< int > faces, blender::Span< int > corner_verts, blender::Span< blender::float2 > uv_map, int verts_num, const blender::float2 &limit, bool use_winding)
UvMapVert *	BKE_mesh_uv_vert_map_get_vert (UvVertMap *vmap, uint v)
void	BKE_mesh_uv_vert_map_free (UvVertMap *vmap)
void	BKE_mesh_vert_corner_tri_map_create (MeshElemMap r_map, int r_mem, const int totvert, const blender::int3 corner_tris, const int tris_num, const int corner_verts, const int)
void	BKE_mesh_origindex_map_create (MeshElemMap r_map, int r_mem, const int totsource, const int *final_origindex, const int totfinal)
void	BKE_mesh_origindex_map_create_corner_tri (MeshElemMap r_map, int r_mem, const blender::OffsetIndices< int > faces, const int *corner_tri_faces, const int corner_tris_num)

Mesh loops/face islands.
Used currently for UVs and 'smooth groups'.
#define	MISLAND_DEFAULT_BUFSIZE 64
using	MeshRemap_CheckIslandBoundary
static void	face_edge_loop_islands_calc_bitflags_exclude_at_boundary (const int *face_groups, const blender::Span< int > faces_from_item, const int face_group_id, const int face_group_id_overflowed, int &r_bit_face_group_mask)
static void	face_edge_loop_islands_calc (const int totedge, const int totvert, const blender::OffsetIndices< int > faces, const blender::Span< int > corner_edges, const blender::Span< int > corner_verts, blender::GroupedSpan< int > edge_face_map, blender::GroupedSpan< int > vert_face_map, const bool use_bitflags, const bool use_boundary_vertices_for_bitflags, MeshRemap_CheckIslandBoundary edge_boundary_check, int *r_face_groups, int r_totgroup, BLI_bitmap *r_edge_boundaries, int r_totedgeboundaries)
static int *	mesh_calc_smoothgroups (const int edges_num, const int verts_num, const blender::OffsetIndices< int > faces, const blender::Span< int > corner_edges, const blender::Span< int > corner_verts, const blender::Span< bool > sharp_edges, const blender::Span< bool > sharp_faces, int *r_totgroup, const bool use_bitflags, const bool use_boundary_vertices_for_bitflags)
int *	BKE_mesh_calc_smoothgroups (int edges_num, const blender::OffsetIndices< int > faces, const blender::Span< int > corner_edges, const blender::Span< bool > sharp_edges, const blender::Span< bool > sharp_faces, int *r_totgroup)
int *	BKE_mesh_calc_smoothgroups_bitflags (int edges_num, int verts_num, const blender::OffsetIndices< int > faces, const blender::Span< int > corner_edges, const blender::Span< int > corner_verts, const blender::Span< bool > sharp_edges, const blender::Span< bool > sharp_faces, const bool use_boundary_vertices_for_bitflags, int *r_totgroup)
void	BKE_mesh_loop_islands_init (MeshIslandStore *island_store, const short item_type, const int items_num, const short island_type, const short innercut_type)
void	BKE_mesh_loop_islands_clear (MeshIslandStore *island_store)
void	BKE_mesh_loop_islands_free (MeshIslandStore *island_store)
void	BKE_mesh_loop_islands_add (MeshIslandStore island_store, const int item_num, const int items_indices, const int num_island_items, int island_item_indices, const int num_innercut_items, int innercut_item_indices)
static bool	mesh_calc_islands_loop_face_uv (const int totedge, const blender::Span< bool > uv_seams, const blender::OffsetIndices< int > faces, const blender::Span< int > corner_edges, MeshIslandStore *r_island_store)
bool	BKE_mesh_calc_islands_loop_face_edgeseam (const blender::Span< blender::float3 > vert_positions, const blender::Span< blender::int2 > edges, const blender::Span< bool > uv_seams, const blender::OffsetIndices< int > faces, const blender::Span< int >, const blender::Span< int > corner_edges, MeshIslandStore *r_island_store)

Detailed Description

Functions for accessing mesh connectivity data. eg: faces connected to verts, UVs connected to verts.

Definition in file mesh_mapping.cc.

Macro Definition Documentation

◆ MISLAND_DEFAULT_BUFSIZE

#define MISLAND_DEFAULT_BUFSIZE 64

Definition at line 774 of file mesh_mapping.cc.

Referenced by BKE_mesh_loop_islands_init().

Typedef Documentation

◆ MeshRemap_CheckIslandBoundary

using MeshRemap_CheckIslandBoundary

Initial value:

 
blender::FunctionRef<bool(int face_index,
                          int corner,
                          int edge_index,
                          int edge_user_count,
                          const blender::Span<int> edge_face_map_elem)>

Callback deciding whether the given face/loop/edge define an island boundary or not.

Definition at line 437 of file mesh_mapping.cc.

Function Documentation

◆ BKE_mesh_calc_islands_loop_face_edgeseam()

bool BKE_mesh_calc_islands_loop_face_edgeseam	(	blender::Span< blender::float3 >	vert_positions,
		blender::Span< blender::int2 >	edges,
		blender::Span< bool >	uv_seams,
		blender::OffsetIndices< int >	faces,
		blender::Span< int >	corner_verts,
		blender::Span< int >	corner_edges,
		MeshIslandStore *	r_island_store )

Calculate 'generic' UV islands, i.e. based only on actual geometry data (edge seams), not some UV layers coordinates.

Parameters

uv_seams Optional (possibly empty) span.

Definition at line 1022 of file mesh_mapping.cc.

References faces, mesh_calc_islands_loop_face_uv(), blender::Span< T >::size(), and UNUSED_VARS.

Referenced by data_transfer_get_loop_islands_generator().

◆ BKE_mesh_calc_smoothgroups()

int * BKE_mesh_calc_smoothgroups	(	int	edges_num,
		blender::OffsetIndices< int >	faces,
		blender::Span< int >	corner_edges,
		blender::Span< bool >	sharp_edges,
		blender::Span< bool >	sharp_faces,
		int *	r_totgroup )

Calculate smooth groups from sharp edges, using increasing numbers as identifier for each group.

Parameters

sharp_edges	Optional (possibly empty) span.
sharp_faces	Optional (possibly empty) span.
r_totgroup	The total number of groups, 1 or more.

Returns: Face aligned array of group index values, starting at 1 (0 being used as 'invalid' flag). Note that it's the callers responsibility to MEM_freeN the returned array.

Definition at line 741 of file mesh_mapping.cc.

References faces, and mesh_calc_smoothgroups().

Referenced by blender::io::obj::OBJMesh::calc_smooth_groups().

◆ BKE_mesh_calc_smoothgroups_bitflags()

int * BKE_mesh_calc_smoothgroups_bitflags	(	int	edges_num,
		int	verts_num,
		blender::OffsetIndices< int >	faces,
		blender::Span< int >	corner_edges,
		blender::Span< int >	corner_verts,
		blender::Span< bool >	sharp_edges,
		blender::Span< bool >	sharp_faces,
		bool	use_boundary_vertices_for_bitflags,
		int *	r_totgroup )

Same as BKE_mesh_calc_smoothgroups, but use bit-flags instead of increasing numbers for each group.

This means that the same value (bit) can be re-used for different groups, as long as they are not neighbors. Values of each group are always powers of two.

By default, only groups that share a same sharp edge are considered neighbors, and therefore prevented to use the same bit-flag value.

If #use_boundary_vertices_for_bitflags is set to true, then groups are also considered neighbors (and therefore cannot have the same bit-flag value) if they share a single vertex, even if they have no common edge. This behavior seems to be required by some DCCs to recompute correct normals, see e.g. #104434. It will however make it much more likely to run out of available bits with certain types of topology (e.g. large fans of sharp faces).

Parameters

sharp_edges	Optional (possibly empty) span.
sharp_faces	Optional (possibly empty) span.
r_totgroup	The total number of groups, 1 or more.

Returns: Face aligned array of group bit-flags values (i.e. always powers of 2), starting at 1 (0 being used as 'invalid' flag). Note that it's the callers responsibility to MEM_freeN the returned array.

Definition at line 752 of file mesh_mapping.cc.

References faces, and mesh_calc_smoothgroups().

Referenced by blender::io::obj::OBJMesh::calc_smooth_groups().

◆ BKE_mesh_loop_islands_add()

void BKE_mesh_loop_islands_add	(	MeshIslandStore *	island_store,
		const int	item_num,
		const int *	items_indices,
		const int	num_island_items,
		int *	island_item_indices,
		const int	num_innercut_items,
		int *	innercut_item_indices )

Definition at line 838 of file mesh_mapping.cc.

References BLI_memarena_alloc(), MeshElemMap::count, i, MeshElemMap::indices, MeshIslandStore::innercuts, MeshIslandStore::islands, MeshIslandStore::islands_num, MeshIslandStore::islands_num_alloc, MeshIslandStore::items_to_islands, MeshIslandStore::mem, and UNLIKELY.

Referenced by mesh_calc_islands_loop_face_uv().

◆ BKE_mesh_loop_islands_clear()

void BKE_mesh_loop_islands_clear ( MeshIslandStore * island_store )

Definition at line 810 of file mesh_mapping.cc.

References BLI_memarena_clear(), MeshIslandStore::innercut_type, MeshIslandStore::innercuts, MeshIslandStore::island_type, MeshIslandStore::islands, MeshIslandStore::islands_num, MeshIslandStore::islands_num_alloc, MeshIslandStore::item_type, MeshIslandStore::items_to_islands, MeshIslandStore::items_to_islands_num, MeshIslandStore::mem, and MISLAND_TYPE_NONE.

Referenced by mesh_calc_islands_loop_face_uv().

◆ BKE_mesh_loop_islands_free()

void BKE_mesh_loop_islands_free ( MeshIslandStore * island_store )

Definition at line 830 of file mesh_mapping.cc.

References BLI_memarena_free(), and MeshIslandStore::mem.

Referenced by BKE_mesh_remap_calc_loops_from_mesh().

◆ BKE_mesh_loop_islands_init()

void BKE_mesh_loop_islands_init	(	MeshIslandStore *	island_store,
		const short	item_type,
		const int	items_num,
		const short	island_type,
		const short	innercut_type )

◆ BKE_mesh_origindex_map_create()

void BKE_mesh_origindex_map_create	(	MeshElemMap **	r_map,
		int **	r_mem,
		int	totsource,
		const int *	final_origindex,
		int	totfinal )

This function creates a map so the source-data (vert/edge/loop/face) can loop over the destination data (using the destination arrays origindex).

This has the advantage that it can operate on any data-types.

Parameters

totsource	The total number of elements that final_origindex points to.
totfinal	The size of final_origindex
final_origindex	The size of the final array.

Note: totsource could be faces_num, totfinal could be tottessface and final_origindex its ORIGINDEX custom-data. This would allow a face to loop over its tessfaces.

Definition at line 195 of file mesh_mapping.cc.

References BLI_assert, MeshElemMap::count, i, indices, MeshElemMap::indices, MEM_calloc_arrayN(), MEM_malloc_arrayN(), and ORIGINDEX_NONE.

◆ BKE_mesh_origindex_map_create_corner_tri()

void BKE_mesh_origindex_map_create_corner_tri	(	MeshElemMap **	r_map,
		int **	r_mem,
		blender::OffsetIndices< int >	faces,
		const int *	corner_tri_faces,
		int	corner_tris_num )

A version of BKE_mesh_origindex_map_create that takes a corner tri array. Making a face -> corner tri map.

Definition at line 236 of file mesh_mapping.cc.

References MeshElemMap::count, blender::bke::mesh::face_triangles_num(), faces, i, indices, MeshElemMap::indices, MEM_calloc_arrayN(), MEM_malloc_arrayN(), and size().

Referenced by BKE_mesh_remap_calc_loops_from_mesh().

◆ BKE_mesh_uv_vert_map_create()

UvVertMap * BKE_mesh_uv_vert_map_create	(	blender::OffsetIndices< int >	faces,
		blender::Span< int >	corner_verts,
		blender::Span< blender::float2 >	uv_map,
		int	verts_num,
		const blender::float2 &	limit,
		bool	use_winding )

Definition at line 37 of file mesh_mapping.cc.

References BKE_mesh_uv_vert_map_free(), UvVertMap::buf, faces, MEM_calloc_arrayN(), MEM_callocN(), blender::threading::parallel_for(), and UvVertMap::vert.

Referenced by blender::bke::subdiv::precalc_uv_layer().

◆ BKE_mesh_uv_vert_map_free()

void BKE_mesh_uv_vert_map_free ( UvVertMap * vmap )

Definition at line 140 of file mesh_mapping.cc.

References UvVertMap::buf, MEM_freeN(), and UvVertMap::vert.

Referenced by BKE_mesh_uv_vert_map_create(), BM_uv_vert_map_create(), and blender::bke::subdiv::precalc_uv_layer().

◆ BKE_mesh_uv_vert_map_get_vert()

UvMapVert * BKE_mesh_uv_vert_map_get_vert	(	UvVertMap *	vmap,
		uint	v )

Definition at line 135 of file mesh_mapping.cc.

References v, and UvVertMap::vert.

Referenced by blender::bke::subdiv::precalc_uv_layer().

◆ BKE_mesh_vert_corner_tri_map_create()

void BKE_mesh_vert_corner_tri_map_create	(	MeshElemMap **	r_map,
		int **	r_mem,
		int	totvert,
		const blender::int3 *	corner_tris,
		int	tris_num,
		const int *	corner_verts,
		int	corners_num )

Generates a map where the key is the edge and the value is a list of corner_tris that use that edge. The lists are allocated from one memory pool.

Definition at line 153 of file mesh_mapping.cc.

References MeshElemMap::count, i, indices, MeshElemMap::indices, MEM_calloc_arrayN(), and MEM_malloc_arrayN().

Referenced by dynamicPaint_createUVSurface().

◆ face_edge_loop_islands_calc()

void face_edge_loop_islands_calc	(	const int	totedge,
		const int	totvert,
		const blender::OffsetIndices< int >	faces,
		const blender::Span< int >	corner_edges,
		const blender::Span< int >	corner_verts,
		blender::GroupedSpan< int >	edge_face_map,
		blender::GroupedSpan< int >	vert_face_map,
		const bool	use_bitflags,
		const bool	use_boundary_vertices_for_bitflags,
		MeshRemap_CheckIslandBoundary	edge_boundary_check,
		int **	r_face_groups,
		int *	r_totgroup,
		BLI_bitmap **	r_edge_boundaries,
		int *	r_totedgeboundaries )

static

ABOUT #use_boundary_vertices_for_bitflags:

Also exclude bits used in other groups sharing the same boundary vertex, i.e. if one edge around the vertex of the current corner is a boundary edge.

NOTE: The reason for this requirement is not very clear. Bit-flags groups are only handled here for I/O purposes, Blender itself does not have this feature. Main external apps heavily relying on these bit-flags groups for their smooth shading computation seem to generate invalid results when two different groups share the same bits, and are connected by a vertex only (i.e. have no edge in common). See #104434.

The downside of also considering boundary vertex-only neighbor faces is that it becomes much more likely to run out of bits, e.g. in a case of a fan with many faces/edges around a same vertex, each in their own face group...

Definition at line 478 of file mesh_mapping.cc.

References BLI_assert, BLI_BITMAP_ENABLE, BLI_BITMAP_NEW, BLI_BITMAP_TEST, blender::bke::mesh::build_edge_to_face_map(), blender::bke::mesh::build_vert_to_face_map(), blender::Span< T >::data(), ELEM, face_edge_loop_islands_calc_bitflags_exclude_at_boundary(), faces, i, blender::offset_indices::GroupedSpan< T >::is_empty(), MEM_calloc_arrayN(), MEM_freeN(), MEM_malloc_arrayN(), printf, blender::Span< T >::size(), and UNLIKELY.

Referenced by mesh_calc_islands_loop_face_uv(), and mesh_calc_smoothgroups().

◆ face_edge_loop_islands_calc_bitflags_exclude_at_boundary()

void face_edge_loop_islands_calc_bitflags_exclude_at_boundary	(	const int *	face_groups,
		const blender::Span< int >	faces_from_item,
		const int	face_group_id,
		const int	face_group_id_overflowed,
		int &	r_bit_face_group_mask )

static

Definition at line 444 of file mesh_mapping.cc.

References ELEM.

Referenced by face_edge_loop_islands_calc().

◆ mesh_calc_islands_loop_face_uv()

bool mesh_calc_islands_loop_face_uv	(	const int	totedge,
		const blender::Span< bool >	uv_seams,
		const blender::OffsetIndices< int >	faces,
		const blender::Span< int >	corner_edges,
		MeshIslandStore *	r_island_store )

static

Definition at line 889 of file mesh_mapping.cc.

References BKE_mesh_loop_islands_add(), BKE_mesh_loop_islands_clear(), BKE_mesh_loop_islands_init(), BLI_BITMAP_TEST, blender::bke::mesh::build_edge_to_face_map(), face_edge_loop_islands_calc(), faces, blender::Span< T >::is_empty(), MEM_freeN(), MEM_malloc_arrayN(), MISLAND_TYPE_EDGE, MISLAND_TYPE_LOOP, MISLAND_TYPE_POLY, and blender::Span< T >::size().

Referenced by BKE_mesh_calc_islands_loop_face_edgeseam().

◆ mesh_calc_smoothgroups()

int * mesh_calc_smoothgroups	(	const int	edges_num,
		const int	verts_num,
		const blender::OffsetIndices< int >	faces,
		const blender::Span< int >	corner_edges,
		const blender::Span< int >	corner_verts,
		const blender::Span< bool >	sharp_edges,
		const blender::Span< bool >	sharp_faces,
		int *	r_totgroup,
		const bool	use_bitflags,
		const bool	use_boundary_vertices_for_bitflags )

static

Definition at line 690 of file mesh_mapping.cc.

References face_edge_loop_islands_calc(), faces, i, and blender::Span< T >::is_empty().

Referenced by BKE_mesh_calc_smoothgroups(), and BKE_mesh_calc_smoothgroups_bitflags().

Namespaces

Functions

Mesh loops/face islands.

Detailed Description

Macro Definition Documentation

◆ MISLAND_DEFAULT_BUFSIZE

Typedef Documentation

◆ MeshRemap_CheckIslandBoundary

Function Documentation

◆ BKE_mesh_calc_islands_loop_face_edgeseam()

◆ BKE_mesh_calc_smoothgroups()

◆ BKE_mesh_calc_smoothgroups_bitflags()

◆ BKE_mesh_loop_islands_add()

◆ BKE_mesh_loop_islands_clear()

◆ BKE_mesh_loop_islands_free()

◆ BKE_mesh_loop_islands_init()

◆ BKE_mesh_origindex_map_create()

◆ BKE_mesh_origindex_map_create_corner_tri()

◆ BKE_mesh_uv_vert_map_create()

◆ BKE_mesh_uv_vert_map_free()

◆ BKE_mesh_uv_vert_map_get_vert()

◆ BKE_mesh_vert_corner_tri_map_create()

◆ face_edge_loop_islands_calc()

◆ face_edge_loop_islands_calc_bitflags_exclude_at_boundary()

◆ mesh_calc_islands_loop_face_uv()

◆ mesh_calc_smoothgroups()