Classes
class	IndexMapping

Enumerations
enum class	MeshMismatch : int8_t { NumVerts , NumEdges , NumCorners , NumFaces , VertexAttributes , EdgeAttributes , CornerAttributes , FaceAttributes , EdgeTopology , FaceTopology , Attributes , AttributeTypes , Indices }

Functions
const char *	mismatch_to_string (const MeshMismatch &mismatch)

std::optional< MeshMismatch >	compare_meshes (const Mesh &mesh1, const Mesh &mesh2, float threshold)
	Checks if the two meshes are different, returning the type of mismatch if any. Changes in index order are detected, but treated as a mismatch.

template<typename T >
static void	sort_indices (MutableSpan< int > indices, const Span< T > values, const int component_i)

static void	sort_indices_with_id_maps (MutableSpan< int > indices, const Span< int > values, const Span< int > values_to_sorted, const Span< int > set_ids)

template<typename T >
static void	sort_per_set_based_on_attributes (const Span< int > set_sizes, MutableSpan< int > sorted_to_domain1, MutableSpan< int > sorted_to_domain2, const Span< T > values1, const Span< T > values2, const int component_i)

static void	sort_per_set_with_id_maps (const Span< int > set_sizes, const Span< int > values1, const Span< int > values2, const Span< int > values1_to_sorted, const Span< int > values2_to_sorted, const Span< int > value_set_ids, MutableSpan< int > sorted_to_domain1, MutableSpan< int > sorted_to_domain2)

template<typename T >
static bool	values_different (const T value1, const T value2, const float threshold, const int component_i)

template<typename T >
static bool	update_set_ids (MutableSpan< int > set_ids, const Span< T > values1, const Span< T > values2, const Span< int > sorted_to_values1, MutableSpan< int > sorted_to_values2, const float threshold, const int component_i)

static bool	update_set_ids_with_id_maps (MutableSpan< int > set_ids, const Span< int > domain_to_values1, const Span< int > domain_to_values2, const Span< int > values1_to_sorted, const Span< int > values2_to_sorted, const Span< int > value_set_ids, const Span< int > sorted_to_domain1, const Span< int > sorted_to_domain2)

static void	update_set_sizes (const Span< int > set_ids, MutableSpan< int > set_sizes)

static void	edges_from_vertex_sets (const Span< int2 > edges, const Span< int > verts_to_sorted, const Span< int > vertex_set_ids, MutableSpan< OrderedEdge > r_edges)

static bool	sort_edges (const Span< int2 > edges1, const Span< int2 > edges2, const IndexMapping &verts, IndexMapping &edges)

static bool	sort_corners_based_on_domain (const Span< int > corner_domain1, const Span< int > corner_domain2, const IndexMapping &domain, IndexMapping &corners)

static void	calc_smallest_corner_ids (const Span< int > face_offsets, const Span< int > corners_to_sorted, const Span< int > corner_set_ids, MutableSpan< int > smallest_corner_ids)

static bool	sort_faces_based_on_corners (const IndexMapping &corners, const Span< int > face_offsets1, const Span< int > face_offsets2, IndexMapping &faces)

static bool	ignored_attribute (const StringRef id)

static std::optional< MeshMismatch >	verify_attributes_compatible (const AttributeAccessor &mesh1_attributes, const AttributeAccessor &mesh2_attributes)

static std::optional< MeshMismatch >	sort_domain_using_attributes (const AttributeAccessor &mesh1_attributes, const AttributeAccessor &mesh2_attributes, const AttrDomain domain, const Span< StringRef > excluded_attributes, IndexMapping &maps, const float threshold)

static void	make_set_sizes_one (IndexMapping &indices)

static bool	all_set_sizes_one (const Span< int > set_sizes)

static std::optional< MeshMismatch >	construct_vertex_mapping (const Mesh &mesh1, const Mesh &mesh2, IndexMapping &verts, IndexMapping &edges)

Enumeration Type Documentation

◆ MeshMismatch

enum class blender::bke::compare_meshes::MeshMismatch : int8_t

strong

Enumerator
NumVerts
NumEdges
NumCorners
NumFaces
VertexAttributes
EdgeAttributes
CornerAttributes
FaceAttributes
EdgeTopology
FaceTopology
Attributes
AttributeTypes
Indices

Definition at line 19 of file mesh_compare.cc.

Function Documentation

◆ all_set_sizes_one()

static bool blender::bke::compare_meshes::all_set_sizes_one ( const Span< int > set_sizes )

static

Definition at line 666 of file mesh_compare.cc.

References all_set_sizes_one().

Referenced by all_set_sizes_one(), and construct_vertex_mapping().

◆ calc_smallest_corner_ids()

static void blender::bke::compare_meshes::calc_smallest_corner_ids	(	const Span< int >	face_offsets,
		const Span< int >	corners_to_sorted,
		const Span< int >	corner_set_ids,
		MutableSpan< int >	smallest_corner_ids )

static

Definition at line 436 of file mesh_compare.cc.

References calc_smallest_corner_ids(), and blender::MutableSpan< T >::index_range().

Referenced by calc_smallest_corner_ids(), and sort_faces_based_on_corners().

◆ compare_meshes()

std::optional< MeshMismatch > blender::bke::compare_meshes::compare_meshes	(	const Mesh &	mesh1,
		const Mesh &	mesh2,
		float	threshold )

Checks if the two meshes are different, returning the type of mismatch if any. Changes in index order are detected, but treated as a mismatch.

Instead of just blindly comparing the two meshes, the code tries to determine if they are isomorphic. Two meshes are considered isomorphic, if, for each domain, there is a bijection between the two meshes such that the bijections preserve connectivity.

In general, determining if two graphs are isomorphic is a very difficult problem (no polynomial time algorithm is known). Because we have more information than just connectivity (attributes), we can compute it in a more reasonable time in most cases.

Returns: The type of mismatch that was detected, if there is any.

Definition at line 781 of file mesh_compare.cc.

References Geometry::attributes, compare_meshes(), construct_vertex_mapping(), Mesh::corners_num, Mesh::edges_num, faces, Mesh::faces_num, make_set_sizes_one(), sort_corners_based_on_domain(), sort_domain_using_attributes(), sort_edges(), sort_faces_based_on_corners(), verify_attributes_compatible(), verts, and Mesh::verts_num.

Referenced by compare_meshes().

◆ construct_vertex_mapping()

static std::optional< MeshMismatch > blender::bke::compare_meshes::construct_vertex_mapping	(	const Mesh &	mesh1,
		const Mesh &	mesh2,
		IndexMapping &	verts,
		IndexMapping &	edges )

static

Tries to construct a (bijective) mapping from the vertices of the first mesh to the vertices of the second mesh, such that:

Edge topology is preserved under this mapping, i.e. if v_1 and v_2 are on an edge in mesh1 then f(v_1) and f(v_2) are on an edge in mesh2.
Face topology is preserved under this mapping, i.e. if v_1, ..., v_n form a face in mesh1, then f(v_1), ..., f(v_n) form a face in mesh2.
The mapping preserves all vertex attributes, i.e. if attr is some vertex attribute on mesh1, then for every vertex v of mesh1, attr(v) = attr(f(v)).

Returns: the type of mismatch that occurred if the mapping couldn't be constructed.

Definition at line 688 of file mesh_compare.cc.

References all_set_sizes_one(), blender::Vector< T, InlineBufferCapacity, Allocator >::append(), BLI_assert, construct_vertex_mapping(), blender::Vector< T, InlineBufferCapacity, Allocator >::first(), blender::Vector< T, InlineBufferCapacity, Allocator >::is_empty(), blender::Span< T >::size(), verts, and Mesh::verts_num.

Referenced by compare_meshes(), and construct_vertex_mapping().

◆ edges_from_vertex_sets()

static void blender::bke::compare_meshes::edges_from_vertex_sets	(	const Span< int2 >	edges,
		const Span< int >	verts_to_sorted,
		const Span< int >	vertex_set_ids,
		MutableSpan< OrderedEdge >	r_edges )

static

Definition at line 360 of file mesh_compare.cc.

References e, edges_from_vertex_sets(), and blender::MutableSpan< T >::index_range().

Referenced by edges_from_vertex_sets(), and sort_edges().

◆ ignored_attribute()

static bool blender::bke::compare_meshes::ignored_attribute ( const StringRef id )

static

Definition at line 498 of file mesh_compare.cc.

References blender::bke::attribute_name_is_anonymous(), and ignored_attribute().

Referenced by ignored_attribute(), sort_domain_using_attributes(), and verify_attributes_compatible().

◆ make_set_sizes_one()

static void blender::bke::compare_meshes::make_set_sizes_one ( IndexMapping & indices )

static

Definition at line 638 of file mesh_compare.cc.

References make_set_sizes_one().

Referenced by compare_meshes(), and make_set_sizes_one().

◆ mismatch_to_string()

const char * blender::bke::compare_meshes::mismatch_to_string ( const MeshMismatch & mismatch )

Convert the mismatch to a human-readable string for display.

Definition at line 35 of file mesh_compare.cc.

References Attributes, AttributeTypes, BLI_assert_unreachable, CornerAttributes, EdgeAttributes, EdgeTopology, FaceAttributes, FaceTopology, Indices, NumCorners, NumEdges, NumFaces, NumVerts, and VertexAttributes.

◆ sort_corners_based_on_domain()

static bool blender::bke::compare_meshes::sort_corners_based_on_domain	(	const Span< int >	corner_domain1,
		const Span< int >	corner_domain2,
		const IndexMapping &	domain,
		IndexMapping &	corners )

static

Sort the corners based on the sorted vertex/edge set ids.

Definition at line 408 of file mesh_compare.cc.

References sort_corners_based_on_domain(), sort_per_set_with_id_maps(), update_set_ids_with_id_maps(), and update_set_sizes().

Referenced by compare_meshes(), and sort_corners_based_on_domain().

◆ sort_domain_using_attributes()

static std::optional< MeshMismatch > blender::bke::compare_meshes::sort_domain_using_attributes	(	const AttributeAccessor &	mesh1_attributes,
		const AttributeAccessor &	mesh2_attributes,
		const AttrDomain	domain,
		const Span< StringRef >	excluded_attributes,
		IndexMapping &	maps,
		const float	threshold )

static

Sort the domain using all the attributes on that domain except the ones in excluded_attributes

Returns: A mismatch if one of the attributes has different values between the two meshes.

Definition at line 541 of file mesh_compare.cc.

References blender::bke::AttributeAccessor::all_ids(), BLI_assert_unreachable, blender::bke::AttributeAccessor::contains(), blender::bke::GAttributeReader::domain, ignored_attribute(), blender::bke::AttributeAccessor::lookup(), blender::Set< Key, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, Allocator >::remove_as(), blender::Set< Key, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, Allocator >::remove_if(), sort_domain_using_attributes(), sort_per_set_based_on_attributes(), blender::GVArrayCommon::type(), update_set_ids(), update_set_sizes(), and blender::bke::GAttributeReader::varray.

Referenced by compare_meshes(), and sort_domain_using_attributes().

◆ sort_edges()

static bool blender::bke::compare_meshes::sort_edges	(	const Span< int2 >	edges1,
		const Span< int2 >	edges2,
		const IndexMapping &	verts,
		IndexMapping &	edges )

static

Sort the edges based on the sorted vertex set ids.

Definition at line 375 of file mesh_compare.cc.

References blender::Array< T, InlineBufferCapacity, Allocator >::as_span(), edges_from_vertex_sets(), blender::Span< T >::size(), sort_edges(), sort_per_set_based_on_attributes(), update_set_ids(), update_set_sizes(), and verts.

Referenced by compare_meshes(), and sort_edges().

◆ sort_faces_based_on_corners()

static bool blender::bke::compare_meshes::sort_faces_based_on_corners	(	const IndexMapping &	corners,
		const Span< int >	face_offsets1,
		const Span< int >	face_offsets2,
		IndexMapping &	faces )

static

Sort the faces using the sorted corner set ids.

Definition at line 459 of file mesh_compare.cc.

References blender::Array< T, InlineBufferCapacity, Allocator >::as_span(), calc_smallest_corner_ids(), sort_faces_based_on_corners(), sort_per_set_based_on_attributes(), update_set_ids(), and update_set_sizes().

Referenced by compare_meshes(), and sort_faces_based_on_corners().

◆ sort_indices()

template<typename T >

static void blender::bke::compare_meshes::sort_indices	(	MutableSpan< int >	indices,
		const Span< T >	values,
		const int	component_i )

static

Sort the indices using the values. For vectors of floats, the sorting happens based on the given component.

Definition at line 117 of file mesh_compare.cc.

References BLI_assert_unreachable, and blender::is_same_any_v.

Referenced by sort_per_set_based_on_attributes().

◆ sort_indices_with_id_maps()

static void blender::bke::compare_meshes::sort_indices_with_id_maps	(	MutableSpan< int >	indices,
		const Span< int >	values,
		const Span< int >	values_to_sorted,
		const Span< int >	set_ids )

static

Sort the indices using the set ids of the values.

Definition at line 163 of file mesh_compare.cc.

References sort_indices_with_id_maps().

Referenced by sort_indices_with_id_maps(), and sort_per_set_with_id_maps().

◆ sort_per_set_based_on_attributes()

template<typename T >

static void blender::bke::compare_meshes::sort_per_set_based_on_attributes	(	const Span< int >	set_sizes,
		MutableSpan< int >	sorted_to_domain1,
		MutableSpan< int >	sorted_to_domain2,
		const Span< T >	values1,
		const Span< T >	values2,
		const int	component_i )

static

Definition at line 175 of file mesh_compare.cc.

References blender::Span< T >::size(), blender::MutableSpan< T >::slice(), sort_indices(), and sort_per_set_based_on_attributes().

Referenced by sort_domain_using_attributes(), sort_edges(), sort_faces_based_on_corners(), and sort_per_set_based_on_attributes().

◆ sort_per_set_with_id_maps()

static void blender::bke::compare_meshes::sort_per_set_with_id_maps	(	const Span< int >	set_sizes,
		const Span< int >	values1,
		const Span< int >	values2,
		const Span< int >	values1_to_sorted,
		const Span< int >	values2_to_sorted,
		const Span< int >	value_set_ids,
		MutableSpan< int >	sorted_to_domain1,
		MutableSpan< int >	sorted_to_domain2 )

static

Definition at line 198 of file mesh_compare.cc.

References blender::MutableSpan< T >::size(), blender::MutableSpan< T >::slice(), sort_indices_with_id_maps(), and sort_per_set_with_id_maps().

Referenced by sort_corners_based_on_domain(), and sort_per_set_with_id_maps().

◆ update_set_ids()

template<typename T >

static bool blender::bke::compare_meshes::update_set_ids	(	MutableSpan< int >	set_ids,
		const Span< T >	values1,
		const Span< T >	values2,
		const Span< int >	sorted_to_values1,
		MutableSpan< int >	sorted_to_values2,
		const float	threshold,
		const int	component_i )

static

Split the sets into smaller sets based on the sorted attribute values.

Returns: false if the attributes don't line up.

Definition at line 267 of file mesh_compare.cc.

References blender::Span< T >::index_range(), blender::MutableSpan< T >::is_empty(), update_set_ids(), and values_different().

Referenced by sort_domain_using_attributes(), sort_edges(), sort_faces_based_on_corners(), and update_set_ids().

◆ update_set_ids_with_id_maps()

static bool blender::bke::compare_meshes::update_set_ids_with_id_maps	(	MutableSpan< int >	set_ids,
		const Span< int >	domain_to_values1,
		const Span< int >	domain_to_values2,
		const Span< int >	values1_to_sorted,
		const Span< int >	values2_to_sorted,
		const Span< int >	value_set_ids,
		const Span< int >	sorted_to_domain1,
		const Span< int >	sorted_to_domain2 )

static

Split the sets into smaller sets based on the set ids of the sorted values.

Returns: false if the attributes don't line up.

Definition at line 308 of file mesh_compare.cc.

References blender::Span< T >::index_range(), blender::MutableSpan< T >::is_empty(), and update_set_ids_with_id_maps().

Referenced by sort_corners_based_on_domain(), and update_set_ids_with_id_maps().

◆ update_set_sizes()

static void blender::bke::compare_meshes::update_set_sizes	(	const Span< int >	set_ids,
		MutableSpan< int >	set_sizes )

static

Update set sizes, using the updated set ids.

Definition at line 345 of file mesh_compare.cc.

References blender::Span< T >::size(), and update_set_sizes().

Referenced by sort_corners_based_on_domain(), sort_domain_using_attributes(), sort_edges(), sort_faces_based_on_corners(), and update_set_sizes().

◆ values_different()

template<typename T >

static bool blender::bke::compare_meshes::values_different	(	const T	value1,
		const T	value2,
		const float	threshold,
		const int	component_i )

static

Checks if the two values are different. For float types, the equality is checked based on a threshold.

Definition at line 233 of file mesh_compare.cc.

References BLI_assert_unreachable, compare_threshold_relative(), and values_different().

Referenced by update_set_ids(), and values_different().

◆ verify_attributes_compatible()

static std::optional< MeshMismatch > blender::bke::compare_meshes::verify_attributes_compatible	(	const AttributeAccessor &	mesh1_attributes,
		const AttributeAccessor &	mesh2_attributes )

static

Verify that both meshes have the same attributes:

Same names
Same domains
Same types

Definition at line 510 of file mesh_compare.cc.

References blender::bke::AttributeAccessor::all_ids(), blender::bke::GAttributeReader::domain, ignored_attribute(), blender::bke::AttributeAccessor::lookup(), blender::Set< Key, InlineBufferCapacity, ProbingStrategy, Hash, IsEqual, Slot, Allocator >::remove_if(), blender::GVArrayCommon::type(), blender::bke::GAttributeReader::varray, and verify_attributes_compatible().

Referenced by compare_meshes(), and verify_attributes_compatible().

Classes

Enumerations

Functions

Enumeration Type Documentation

◆ MeshMismatch

Function Documentation

◆ all_set_sizes_one()

◆ calc_smallest_corner_ids()

◆ compare_meshes()

◆ construct_vertex_mapping()

◆ edges_from_vertex_sets()

◆ ignored_attribute()

◆ make_set_sizes_one()

◆ mismatch_to_string()

◆ sort_corners_based_on_domain()

◆ sort_domain_using_attributes()

◆ sort_edges()

◆ sort_faces_based_on_corners()

◆ sort_indices()

◆ sort_indices_with_id_maps()

◆ sort_per_set_based_on_attributes()

◆ sort_per_set_with_id_maps()

◆ update_set_ids()

◆ update_set_ids_with_id_maps()

◆ update_set_sizes()

◆ values_different()

◆ verify_attributes_compatible()