#include <algorithm>
#include "MEM_guardedalloc.h"
#include "atomic_ops.h"
#include "BLI_array.hh"
#include "BLI_bitmap.h"
#include "BLI_buffer.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 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 (const blender::OffsetIndices< int > faces, const bool hide_poly, const bool select_poly, const int corner_verts, const float(mloopuv)[2], uint totvert, const float limit[2], const bool selected, const 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 bool uv_seams, const blender::OffsetIndices< int > faces, const int corner_verts, const int corner_edges, const int corners_num, const float(luvs)[2], MeshIslandStore *r_island_store)
bool	BKE_mesh_calc_islands_loop_face_edgeseam (const float(vert_positions)[3], const int totvert, const blender::int2 edges, const int totedge, const bool uv_seams, const blender::OffsetIndices< int > faces, const int corner_verts, const int corner_edges, const int corners_num, MeshIslandStore r_island_store)
bool	BKE_mesh_calc_islands_loop_face_uvmap (float(vert_positions)[3], const int totvert, blender::int2 edges, const int totedge, const bool uv_seams, const blender::OffsetIndices< int > faces, const int corner_verts, const int corner_edges, const int corners_num, const float(luvs)[2], 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 811 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 474 of file mesh_mapping.cc.

Function Documentation

◆ BKE_mesh_calc_islands_loop_face_edgeseam()

bool BKE_mesh_calc_islands_loop_face_edgeseam	(	const float(*)	vert_positions[3],
		int	totvert,
		const blender::int2 *	edges,
		int	totedge,
		const bool *	uv_seams,
		blender::OffsetIndices< int >	faces,
		const int *	corner_verts,
		const int *	corner_edges,
		int	corners_num,
		MeshIslandStore *	r_island_store )

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

Definition at line 1097 of file mesh_mapping.cc.

References faces, mesh_calc_islands_loop_face_uv(), and UNUSED_VARS.

Referenced by data_transfer_get_loop_islands_generator().

◆ BKE_mesh_calc_islands_loop_face_uvmap()

bool BKE_mesh_calc_islands_loop_face_uvmap	(	float(*)	vert_positions[3],
		int	totvert,
		blender::int2 *	edges,
		int	totedge,
		const bool *	uv_seams,
		blender::OffsetIndices< int >	faces,
		const int *	corner_verts,
		const int *	corner_edges,
		int	corners_num,
		const float(*)	luvs[2],
		MeshIslandStore *	r_island_store )

Calculate UV islands.

Note: If no UV layer is passed, we only consider edges tagged as seams as UV boundaries. This has the advantages of simplicity, and being valid/common to all UV maps. However, it means actual UV islands without matching UV seams will not be handled correctly. If a valid UV layer is passed as luvs parameter, UV coordinates are also used to detect islands boundaries.; All this could be optimized. Not sure it would be worth the more complex code, though, those loops are supposed to be really quick to do.

Definition at line 1113 of file mesh_mapping.cc.

References BLI_assert, faces, mesh_calc_islands_loop_face_uv(), and UNUSED_VARS.

◆ 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 778 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 789 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 875 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 847 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 867 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 232 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 273 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	(	const blender::OffsetIndices< int >	faces,
		const bool *	hide_poly,
		const bool *	select_poly,
		const int *	corner_verts,
		const float(*)	mloopuv[2],
		uint	totvert,
		const float	limit[2],
		const bool	selected,
		const bool	use_winding )

Definition at line 38 of file mesh_mapping.cc.

References BKE_mesh_uv_vert_map_free(), BLI_buffer_declare_static, BLI_buffer_free, BLI_BUFFER_NOP, BLI_buffer_reinit_data, UvVertMap::buf, copy_v2_v2(), cross_poly_v2(), fabsf, UvMapVert::face_index, faces, i, UvMapVert::loop_of_face_index, MEM_calloc_arrayN(), MEM_callocN(), MEM_freeN(), next, UvMapVert::next, UvMapVert::separate, blender::IndexRange::size(), size(), sub_v2_v2v2(), v, and UvVertMap::vert.

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

◆ BKE_mesh_uv_vert_map_free()

void BKE_mesh_uv_vert_map_free ( UvVertMap * vmap )

Definition at line 177 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(), blender::bke::subdiv::precalc_uv_layer(), and ss_sync_from_uv().

◆ BKE_mesh_uv_vert_map_get_vert()

UvMapVert * BKE_mesh_uv_vert_map_get_vert	(	UvVertMap *	vmap,
		uint	v )

Definition at line 172 of file mesh_mapping.cc.

References v, and UvVertMap::vert.

Referenced by get_face_uv_map_vert(), blender::bke::subdiv::precalc_uv_layer(), and ss_sync_from_uv().

◆ 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 190 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 515 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 481 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 bool *	uv_seams,
		const blender::OffsetIndices< int >	faces,
		const int *	corner_verts,
		const int *	corner_edges,
		const int	corners_num,
		const float(*)	luvs[2],
		MeshIslandStore *	r_island_store )

static

◆ 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 727 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_islands_loop_face_uvmap()

◆ 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()