Blender V5.3
geometry_compare.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
8
9#include <algorithm>
10#include <iostream>
11#include <numeric>
12
13#include "BLI_array.hh"
14#include "BLI_math_base_c.hh"
15#include "BLI_ordered_edge.hh"
16#include "BLI_span.hh"
17
19#include "BKE_attribute.hh"
20#include "BKE_grease_pencil.hh"
21#include "BKE_mesh.hh"
22#include "BKE_mesh_mapping.hh"
23
25
26#include "CLG_log.h"
27
28#include "DNA_curve_types.h"
29#include "DNA_lattice_types.h"
30
32
33static CLG_LogRef LOG = {"geometry.compare"};
34
35enum class GeoMismatch : int8_t {
36 NumPoints, /* The number of points is different. */
37 NumEdges, /* The number of edges is different. */
38 NumCorners, /* The number of corners is different. */
39 NumFaces, /* The number of faces is different. */
40 NumCurves, /* The number of curves is different. */
41 PointAttributes, /* Some values of the point attributes are different. */
42 EdgeAttributes, /* Some values of the edge attributes are different. */
43 CornerAttributes, /* Some values of the corner attributes are different. */
44 FaceAttributes, /* Some values of the face attributes are different. */
45 CurveAttributes, /* Some values of the curve attributes are different. */
46 LayerAttributes, /* Some values of the Grease Pencil layer attributes are different. */
47 EdgeTopology, /* The edge topology is different. */
48 FaceTopology, /* The face topology is different. */
49 CurveTopology, /* The curve topology is different. */
50 Attributes, /* The sets of attribute ids are different. */
51 AttributeTypes, /* Some attributes with the same name have different types. */
52 Indices, /* The geometries are the same up to a change of indices. */
53 NumLayers, /* The number of Grease Pencil layers is different. */
54 NumFrames, /* The number of Grease Pencil frames on some layer is different. */
55 LayerOrder, /* The Grease Pencil layer order is different. */
56 Frames, /* The Grease Pencil keyframes on some layer are different. */
57};
58
59const char *mismatch_to_string(const GeoMismatch &mismatch)
60{
61 switch (mismatch) {
63 return "The number of points is different";
65 return "The number of edges is different";
67 return "The number of corners is different";
69 return "The number of faces is different";
71 return "The number of curves is different";
73 return "Some values of the point attributes are different";
75 return "Some values of the edge attributes are different";
77 return "Some values of the corner attributes are different";
79 return "Some values of the face attributes are different";
81 return "Some values of the curve attributes are different";
83 return "Some values of the layer attributes are different";
85 return "The edge topology is different";
87 return "The face topology is different";
89 return "The curve topology is different";
91 return "The sets of attribute ids are different";
93 return "Some attributes with the same name have different types";
95 return "The geometries are the same up to a change of indices";
97 return "The number of Grease Pencil layers is different";
99 return "The number of Grease Pencil frames on some layer is different";
101 return "The Grease Pencil layer order is different";
103 return "The Grease Pencil keyframes on some layer are different";
104 }
106 return "";
107}
108
110 private:
111 void calculate_inverse_map(const Span<int> map, MutableSpan<int> inverted_map)
112 {
113 for (const int i : map.index_range()) {
114 inverted_map[map[i]] = i;
115 }
116 }
117
118 public:
125
126 IndexMapping(const int64_t domain_size)
127 {
128 to_sorted1 = Array<int>(domain_size);
129 to_sorted2 = Array<int>(domain_size);
130 from_sorted1 = Array<int>(domain_size);
131 from_sorted2 = Array<int>(domain_size);
132 set_ids = Array<int>(domain_size);
133 set_sizes = Array<int>(domain_size);
134 std::iota(from_sorted1.begin(), from_sorted1.end(), 0);
135 std::iota(from_sorted2.begin(), from_sorted2.end(), 0);
136 std::iota(to_sorted1.begin(), to_sorted1.end(), 0);
137 std::iota(to_sorted2.begin(), to_sorted2.end(), 0);
138 set_ids.fill(0);
140 }
141
146 {
147 calculate_inverse_map(from_sorted1, to_sorted1);
148 calculate_inverse_map(from_sorted2, to_sorted2);
149 }
150};
151
155template<typename T> static void sort_indices(MutableSpan<int> indices, const Span<T> values)
156{
157 std::stable_sort(indices.begin(), indices.end(), [&](const int i1, const int i2) {
158 return values[i1] < values[i2];
159 });
160}
161
166 const Span<int> values,
167 const Span<int> values_to_sorted,
168 const Span<int> set_ids)
169{
170 std::stable_sort(indices.begin(), indices.end(), [&](int i1, int i2) {
171 return set_ids[values_to_sorted[values[i1]]] < set_ids[values_to_sorted[values[i2]]];
172 });
173}
174
175/* Sort the elements in each set based on the attribute values. */
176template<typename T>
177static void sort_per_set_based_on_attributes(const Span<int> set_sizes,
178 MutableSpan<int> sorted_to_domain1,
179 MutableSpan<int> sorted_to_domain2,
180 const Span<T> values1,
181 const Span<T> values2)
182{
183 int i = 0;
184 while (i < set_sizes.size()) {
185 const int set_size = set_sizes[i];
186 if (set_size == 1) {
187 /* No need to sort anymore. */
188 i += 1;
189 continue;
190 }
191
192 sort_indices(sorted_to_domain1.slice(IndexRange(i, set_size)), values1);
193 sort_indices(sorted_to_domain2.slice(IndexRange(i, set_size)), values2);
194 i += set_size;
195 }
196}
197
198/* Sort the elements in each set based on the set ids of the values. */
199static void sort_per_set_with_id_maps(const Span<int> set_sizes,
200 const Span<int> values1,
201 const Span<int> values2,
202 const Span<int> values1_to_sorted,
203 const Span<int> values2_to_sorted,
204 const Span<int> value_set_ids,
205 MutableSpan<int> sorted_to_domain1,
206 MutableSpan<int> sorted_to_domain2)
207{
208 int i = 0;
209 while (i < sorted_to_domain1.size()) {
210 const int set_size = set_sizes[i];
211 if (set_size == 1) {
212 /* No need to sort anymore. */
213 i += 1;
214 continue;
215 }
216
217 sort_indices_with_id_maps(sorted_to_domain1.slice(IndexRange(i, set_size)),
218 values1,
219 values1_to_sorted,
220 value_set_ids);
221 sort_indices_with_id_maps(sorted_to_domain2.slice(IndexRange(i, set_size)),
222 values2,
223 values2_to_sorted,
224 value_set_ids);
225 i += set_size;
226 }
227}
228
233template<typename T>
234static bool values_different(const T value1, const T value2, const float threshold)
235{
236 if constexpr (std::is_same_v<T, float>) {
237 return compare_threshold_relative(value1, value2, threshold);
238 }
239 else {
240 return value1 != value2;
241 }
242}
243
249template<typename T>
250static bool update_set_ids(StringRef name,
251 MutableSpan<int> set_ids,
252 const Span<T> values1,
253 const Span<T> values2,
254 const Span<int> sorted_to_values1,
255 const Span<int> sorted_to_values2,
256 const float threshold)
257{
258 /* Due to the way the sorting works, there could be a slightly bigger difference. */
259 const float value_threshold = 5 * threshold;
260 if (set_ids.is_empty()) {
261 return true;
262 }
263 T previous = values1[0];
264 int set_id = 0;
265 for (const int i : values1.index_range()) {
266 const T value1 = values1[sorted_to_values1[i]];
267 const T value2 = values2[sorted_to_values2[i]];
268 if (values_different(value1, value2, value_threshold)) {
269 /* They should be the same after sorting. */
270 std::cout << "Attribute different: " << name << "\n";
271 std::cout << " 1: " << value1 << "\n";
272 std::cout << " 2: " << value2 << "\n";
273 return false;
274 }
275 if ((values_different(previous, value1, value_threshold) &&
276 values_different(previous, value2, value_threshold)) ||
277 set_ids[i] == i)
278 {
279 /* Different value, or this was already a different set. */
280 set_id = i;
281 previous = value1;
282 }
283 set_ids[i] = set_id;
284 }
285
286 return true;
287}
288
295 const Span<int> domain_to_values1,
296 const Span<int> domain_to_values2,
297 const Span<int> values1_to_sorted,
298 const Span<int> values2_to_sorted,
299 const Span<int> value_set_ids,
300 const Span<int> sorted_to_domain1,
301 const Span<int> sorted_to_domain2)
302{
303 if (set_ids.is_empty()) {
304 return true;
305 }
306 int previous = value_set_ids[values1_to_sorted[domain_to_values1[sorted_to_domain1[0]]]];
307 int set_id = 0;
308 for (const int i : sorted_to_domain1.index_range()) {
309 const int value_id1 =
310 value_set_ids[values1_to_sorted[domain_to_values1[sorted_to_domain1[i]]]];
311 const int value_id2 =
312 value_set_ids[values2_to_sorted[domain_to_values2[sorted_to_domain2[i]]]];
313 if (value_id1 != value_id2) {
314 /* They should be the same after sorting. */
315 return false;
316 }
317 if (value_id1 != previous || set_ids[i] == i) {
318 /* Different value, or this was already a different set. */
319 set_id = i;
320 previous = value_id1;
321 }
322 set_ids[i] = set_id;
323 }
324
325 return true;
326}
327
331static void update_set_sizes(const Span<int> set_ids, MutableSpan<int> set_sizes)
332{
333 int i = set_ids.size() - 1;
334 while (i >= 0) {
335 /* The id of a set is the index of its first element, so the size can be computed as the index
336 * of the last element minus the id (== index of first element) + 1. */
337 int set_size = i - set_ids[i] + 1;
338 /* Set the set size for each element in the set. */
339 for (int k = i - set_size + 1; k <= i; k++) {
340 set_sizes[k] = set_size;
341 }
342 i -= set_size;
343 }
344}
345
346static void edges_from_vert_sets(const Span<int2> edges,
347 const Span<int> verts_to_sorted,
348 const Span<int> vert_set_ids,
350{
351 for (const int i : r_edges.index_range()) {
352 const int2 e = edges[i];
353 r_edges[i] = OrderedEdge(vert_set_ids[verts_to_sorted[e.x]],
354 vert_set_ids[verts_to_sorted[e.y]]);
355 }
356}
357
361static bool sort_edges(const Span<int2> edges1,
362 const Span<int2> edges2,
363 const IndexMapping &verts,
364 IndexMapping &edges)
365{
366 /* Need `NoInitialization()` because OrderedEdge is not default constructible. */
367 Array<OrderedEdge> ordered_edges1(edges1.size(), NoInitialization());
368 Array<OrderedEdge> ordered_edges2(edges2.size(), NoInitialization());
369 edges_from_vert_sets(edges1, verts.to_sorted1, verts.set_ids, ordered_edges1);
370 edges_from_vert_sets(edges2, verts.to_sorted2, verts.set_ids, ordered_edges2);
372 edges.from_sorted1,
373 edges.from_sorted2,
374 ordered_edges1.as_span(),
375 ordered_edges2.as_span());
376 const bool edges_match = update_set_ids("ORDERED_EDGES",
377 edges.set_ids,
378 ordered_edges1.as_span(),
379 ordered_edges2.as_span(),
380 edges.from_sorted1,
381 edges.from_sorted2,
382 0);
383 if (!edges_match) {
384 return false;
385 }
386 update_set_sizes(edges.set_ids, edges.set_sizes);
387 return true;
388}
389
393static bool sort_corners_based_on_domain(const Span<int> corner_domain1,
394 const Span<int> corner_domain2,
395 const IndexMapping &domain,
396 IndexMapping &corners)
397{
398 sort_per_set_with_id_maps(corners.set_sizes,
399 corner_domain1,
400 corner_domain2,
401 domain.to_sorted1,
402 domain.to_sorted2,
403 domain.set_ids,
404 corners.from_sorted1,
405 corners.from_sorted2);
406 const bool corners_line_up = update_set_ids_with_id_maps(corners.set_ids,
407 corner_domain1,
408 corner_domain2,
409 domain.to_sorted1,
410 domain.to_sorted2,
411 domain.set_ids,
412 corners.from_sorted1,
413 corners.from_sorted2);
414 if (!corners_line_up) {
415 return false;
416 }
417 update_set_sizes(corners.set_ids, corners.set_sizes);
418 return true;
419}
420
421static void calc_smallest_corner_ids(const Span<int> face_offsets,
422 const Span<int> corners_to_sorted,
423 const Span<int> corner_set_ids,
424 MutableSpan<int> smallest_corner_ids)
425{
426 for (const int face_i : smallest_corner_ids.index_range()) {
427 const int face_start = face_offsets[face_i];
428 const int face_end = face_offsets[face_i + 1];
429 int smallest = corner_set_ids[corners_to_sorted[face_start]];
430 const IndexRange corners = IndexRange(face_start, face_end - face_start);
431 for (const int corner_i : corners.drop_front(1)) {
432 const int corner_id = corner_set_ids[corners_to_sorted[corner_i]];
433 smallest = std::min(corner_id, smallest);
434 }
435 smallest_corner_ids[face_i] = smallest;
436 }
437}
438
442static bool sort_faces_based_on_corners(const IndexMapping &corners,
443 const Span<int> face_offsets1,
444 const Span<int> face_offsets2,
445 IndexMapping &faces)
446{
447 /* The smallest corner set id, per face. */
448 Array<int> smallest_corner_ids1(faces.from_sorted1.size());
449 Array<int> smallest_corner_ids2(faces.from_sorted2.size());
451 face_offsets1, corners.to_sorted1, corners.set_ids, smallest_corner_ids1);
453 face_offsets2, corners.to_sorted2, corners.set_ids, smallest_corner_ids2);
455 faces.from_sorted1,
456 faces.from_sorted2,
457 smallest_corner_ids1.as_span(),
458 smallest_corner_ids2.as_span());
459 const bool faces_line_up = update_set_ids("CORNER_IDS",
460 faces.set_ids,
461 smallest_corner_ids1.as_span(),
462 smallest_corner_ids2.as_span(),
463 faces.from_sorted1,
464 faces.from_sorted2,
465 0);
466 if (!faces_line_up) {
467 return false;
468 }
469 update_set_sizes(faces.set_ids, faces.set_sizes);
470 return true;
471}
472
480static bool ignored_attribute(const StringRef name)
481{
482 return attribute_name_is_anonymous(name) || name.startswith(".pn.") ||
483 ELEM(name, ".uv_select_vert", ".uv_select_edge", ".uv_select_face");
484}
485
492static std::optional<GeoMismatch> verify_attributes_compatible(
493 const AttributeAccessor &attributes1, const AttributeAccessor &attributes2)
494{
495 Set<StringRefNull> names_1 = attributes1.all_names();
496 Set<StringRefNull> names_2 = attributes2.all_names();
499
500 if (names_1 != names_2) {
501 std::string mismatched_names;
502 for (const StringRefNull name : names_1) {
503 if (!names_2.contains(name)) {
504 if (!mismatched_names.empty()) {
505 mismatched_names.append(", ");
506 }
507 mismatched_names.append(name);
508 }
509 }
510 for (const StringRefNull name : names_2) {
511 if (!names_1.contains(name)) {
512 if (!mismatched_names.empty()) {
513 mismatched_names.append(", ");
514 }
515 mismatched_names.append(name);
516 }
517 }
518 CLOG_WARN(&LOG, "Attribute names not the same: %s", mismatched_names.c_str());
520 }
521 for (const StringRef name : names_1) {
522 GAttributeReader reader1 = attributes1.lookup(name);
523 GAttributeReader reader2 = attributes2.lookup(name);
524 if (!reader1 || !reader2) {
525 /* Necessary because of previous disabled return. */
526 continue;
527 }
528 if (reader1.domain != reader2.domain || reader1.varray.type() != reader2.varray.type()) {
530 }
531 }
532 return std::nullopt;
533}
534
542 int num;
543};
544
545static std::optional<AttributeComponents> get_attribute_components(const AttrType type)
546{
547 switch (type) {
548 case AttrType::Bool:
549 case AttrType::Int8:
550 case AttrType::Int32:
551 return AttributeComponents{false, 1};
554 return AttributeComponents{false, 2};
556 return AttributeComponents{false, 4};
557 case AttrType::Float:
558 return AttributeComponents{true, 1};
559 case AttrType::Float2:
560 return AttributeComponents{true, 2};
561 case AttrType::Float3:
562 return AttributeComponents{true, 3};
563 case AttrType::Float4:
566 return AttributeComponents{true, 4};
568 return AttributeComponents{true, 16};
569 case AttrType::String:
570 return std::nullopt;
571 }
573 return std::nullopt;
574}
575
576template<typename T, typename ComponentT>
577static void gather_component(const GSpan values,
578 const int components_num,
579 const int component,
581{
582 const T *data = static_cast<const T *>(values.data());
583 for (const int i : dst.index_range()) {
584 dst[i] = ComponentT(data[i * components_num + component]);
585 }
586}
587
589template<typename Fn> static void to_static_int_component_type(const AttrType type, Fn &&fn)
590{
591 switch (type) {
592 case AttrType::Bool:
593 fn.template operator()<bool>();
594 break;
595 case AttrType::Int8:
596 fn.template operator()<int8_t>();
597 break;
599 fn.template operator()<int16_t>();
600 break;
601 case AttrType::Int32:
603 fn.template operator()<int>();
604 break;
606 fn.template operator()<uint8_t>();
607 break;
608 default:
610 break;
611 }
612}
613
614template<typename T>
615static bool sort_using_values(const StringRef name,
616 const Span<T> values1,
617 const Span<T> values2,
618 const float threshold,
619 IndexMapping &maps)
620{
622 maps.set_sizes, maps.from_sorted1, maps.from_sorted2, values1, values2);
623 if (!update_set_ids(
624 name, maps.set_ids, values1, values2, maps.from_sorted1, maps.from_sorted2, threshold))
625 {
626 return false;
627 }
629 return true;
630}
631
652
658static std::optional<GeoMismatch> sort_domain_using_attributes(
659 const AttributeAccessor &attributes1,
660 const AttributeAccessor &attributes2,
661 const AttrDomain domain,
662 const Span<StringRef> excluded_attributes,
663 IndexMapping &maps,
664 const float threshold)
665{
666
667 /* We only need the ids from one geometry, since we know they have the same attributes. */
668 Set<StringRefNull> names = attributes1.all_names();
669 for (const StringRef name : excluded_attributes) {
670 names.remove_as(name);
671 }
673
674 for (const StringRef name : names) {
675 GAttributeReader reader1 = attributes1.lookup(name);
676 GAttributeReader reader2 = attributes2.lookup(name);
677
678 if (reader1.domain != domain) {
679 /* We only look at attributes of the given domain. */
680 continue;
681 }
682
683 const AttrType type = cpp_type_to_attribute_type(reader1.varray.type());
684 const std::optional<AttributeComponents> components = get_attribute_components(type);
685 if (!components) {
686 continue;
687 }
688
689 const GVArraySpan values1(reader1.varray);
690 const GVArraySpan values2(reader2.varray);
691
692 /* Because sorting of vectors is not very stable, we do a separate sort per component,
693 * re-computing the set ids each time. */
694 if (components->is_float) {
695 Array<float> component1(values1.size());
696 Array<float> component2(values2.size());
697 for (const int component : IndexRange(components->num)) {
698 gather_component<float>(values1, components->num, component, component1.as_mutable_span());
699 gather_component<float>(values2, components->num, component, component2.as_mutable_span());
700 if (!sort_using_values(name, component1.as_span(), component2.as_span(), threshold, maps))
701 {
702 return attribute_mismatch_for_domain(domain);
703 }
704 }
705 }
706 else {
707 Array<int> component1(values1.size());
708 Array<int> component2(values2.size());
709 for (const int component : IndexRange(components->num)) {
710 to_static_int_component_type(type, [&]<typename T>() {
711 gather_component<T>(values1, components->num, component, component1.as_mutable_span());
712 gather_component<T>(values2, components->num, component, component2.as_mutable_span());
713 });
714 if (!sort_using_values(name, component1.as_span(), component2.as_span(), threshold, maps))
715 {
716 return attribute_mismatch_for_domain(domain);
717 }
718 }
719 }
720 }
721 return std::nullopt;
722}
723
724/* When all checks are done, it's possible that some set sizes are still not one e.g, when you have
725 * two loose verts at the same position they are indistinguishable. This makes all the set ID's one
726 * by choosing a match. If possible, the match is chosen such that they have the same unsorted
727 * index.
728 */
729static void make_set_sizes_one(IndexMapping &indices)
730{
731 for (const int sorted_i : indices.set_sizes.index_range()) {
732 if (indices.set_sizes[sorted_i] == 1) {
733 continue;
734 }
735 int match = sorted_i;
736 for (const int other_index :
737 IndexRange(indices.set_ids[sorted_i], indices.set_sizes[sorted_i]))
738 {
739 if (indices.from_sorted1[sorted_i] == indices.from_sorted2[other_index]) {
740 match = other_index;
741 break;
742 }
743 }
744 std::swap(indices.from_sorted2[sorted_i], indices.from_sorted2[match]);
745 for (const int other_set_i :
746 IndexRange(indices.set_ids[sorted_i], indices.set_sizes[sorted_i]))
747 {
748 /* New first element, since this one is now in a new set. */
749 indices.set_ids[other_set_i] = sorted_i + 1;
750 indices.set_sizes[other_set_i] -= 1;
751 }
752 indices.set_ids[sorted_i] = sorted_i;
753 indices.set_sizes[sorted_i] = 1;
754 }
755}
756
757static bool all_set_sizes_one(const Span<int> set_sizes)
758{
759 for (const int size : set_sizes) {
760 if (size != 1) {
761 return false;
762 }
763 }
764 return true;
765}
766
779static std::optional<GeoMismatch> construct_vert_mapping(const Mesh &mesh1,
780 const Mesh &mesh2,
781 IndexMapping &verts,
782 IndexMapping &edges)
783{
784 if (all_set_sizes_one(verts.set_sizes)) {
785 /* The vertices are already in one-to-one correspondence. */
786 return std::nullopt;
787 }
788
789 /* Since we are not yet able to distinguish all vertices based on their attributes alone, we
790 * need to use the edge topology. */
791 Array<int> vert_to_edge_offsets1;
792 Array<int> vert_to_edge_indices1;
793 const GroupedSpan<int> vert_to_edge_map1 = mesh::build_vert_to_edge_map(
794 mesh1.edges(), mesh1.verts_num, vert_to_edge_offsets1, vert_to_edge_indices1);
795 Array<int> vert_to_edge_offsets2;
796 Array<int> vert_to_edge_indices2;
797 const GroupedSpan<int> vert_to_edge_map2 = mesh::build_vert_to_edge_map(
798 mesh2.edges(), mesh2.verts_num, vert_to_edge_offsets2, vert_to_edge_indices2);
799
800 for (const int sorted_i : verts.from_sorted1.index_range()) {
801 const int vert1 = verts.from_sorted1[sorted_i];
802 Vector<int> matching_verts;
803 const Span<int> edges1 = vert_to_edge_map1[vert1];
804 /* Try to find all matching vertices. We know that it will be in the same vertex set, if it
805 * exists. */
806 for (const int index_in_set : IndexRange(verts.set_sizes[sorted_i])) {
807 /* The set id is the index of its first element. */
808 const int vert2 = verts.from_sorted2[verts.set_ids[sorted_i] + index_in_set];
809 const Span<int> edges2 = vert_to_edge_map2[vert2];
810 if (edges1.size() != edges2.size()) {
811 continue;
812 }
813 bool vert_matches = true;
814 for (const int edge1 : edges1) {
815 bool found_matching_edge = false;
816 for (const int edge2 : edges2) {
817 if (edges.set_ids[edges.to_sorted1[edge1]] == edges.set_ids[edges.to_sorted2[edge2]]) {
818 found_matching_edge = true;
819 break;
820 }
821 }
822 if (!found_matching_edge) {
823 vert_matches = false;
824 break;
825 }
826 }
827 if (vert_matches) {
828 matching_verts.append(index_in_set);
829 }
830 }
831
832 if (matching_verts.is_empty()) {
834 }
835
836 /* Update the maps. */
837
838 /* In principle, we should make sure that there is exactly one matching vertex. If the mesh is
839 * of good enough quality, that will always be the case. In other cases we just assume that any
840 * choice will be valid. Otherwise, the logic becomes a lot more difficult. Because we want to
841 * test for mesh equality as well, we try to pick the matching vert with the same index. */
842 int index_in_set = matching_verts.first();
843 for (const int other_index_in_set : matching_verts) {
844 const int other_sorted_index = verts.set_ids[sorted_i] + other_index_in_set;
845 if (verts.from_sorted1[sorted_i] == verts.from_sorted2[other_sorted_index]) {
846 index_in_set = other_index_in_set;
847 break;
848 }
849 }
850 std::swap(verts.from_sorted2[sorted_i],
851 verts.from_sorted2[verts.set_ids[sorted_i] + index_in_set]);
852 for (const int other_set_i : IndexRange(verts.set_ids[sorted_i], verts.set_sizes[sorted_i])) {
853 /* New first element, since this one is now in a new set. */
854 verts.set_ids[other_set_i] = sorted_i + 1;
855 verts.set_sizes[other_set_i] -= 1;
856 }
857 verts.set_ids[sorted_i] = sorted_i;
858 verts.set_sizes[sorted_i] = 1;
859 }
860
862
864
865 /* The bijective mapping is now given by composing `verts.to_sorted1` with `verts.from_sorted2`,
866 * or vice versa. Since we don't actually need the mapping (we just care that it exists), we
867 * don't construct it here. */
868
869 return std::nullopt;
870}
871
872std::optional<GeoMismatch> compare_meshes(const Mesh &mesh1,
873 const Mesh &mesh2,
874 const float threshold)
875{
876
877 /* These will be assumed implicitly later on. */
878 if (mesh1.verts_num != mesh2.verts_num) {
880 }
881 if (mesh1.edges_num != mesh2.edges_num) {
883 }
884 if (mesh1.corners_num != mesh2.corners_num) {
886 }
887 if (mesh1.faces_num != mesh2.faces_num) {
889 }
890
891 std::optional<GeoMismatch> mismatch = {};
892
893 const AttributeAccessor mesh1_attributes = mesh1.attributes();
894 const AttributeAccessor mesh2_attributes = mesh2.attributes();
895 mismatch = verify_attributes_compatible(mesh1_attributes, mesh2_attributes);
896 if (mismatch) {
897 return mismatch;
898 }
899
900 IndexMapping verts(mesh1.verts_num);
902 mesh1_attributes, mesh2_attributes, AttrDomain::Point, {}, verts, threshold);
903 if (mismatch) {
904 return mismatch;
905 }
906
907 /* We need the maps going the other way as well. */
909
910 IndexMapping edges(mesh1.edges_num);
911 if (!sort_edges(mesh1.edges(), mesh2.edges(), verts, edges)) {
913 }
914
916 mesh1_attributes, mesh2_attributes, AttrDomain::Edge, {".edge_verts"}, edges, threshold);
917 if (mismatch) {
918 return mismatch;
919 };
920
921 /* We need the maps going the other way as well. */
923
924 IndexMapping corners(mesh1.corners_num);
925 if (!sort_corners_based_on_domain(mesh1.corner_verts(), mesh2.corner_verts(), verts, corners)) {
927 }
928
929 if (!sort_corners_based_on_domain(mesh1.corner_edges(), mesh2.corner_edges(), edges, corners)) {
931 }
932
933 mismatch = sort_domain_using_attributes(mesh1_attributes,
934 mesh2_attributes,
936 {".corner_vert", ".corner_edge"},
937 corners,
938 threshold);
939 if (mismatch) {
940 return mismatch;
941 };
942
943 /* We need the maps going the other way as well. */
944 corners.recalculate_inverse_maps();
945
946 IndexMapping faces(mesh1.faces_num);
947 if (!sort_faces_based_on_corners(corners, mesh1.face_offsets(), mesh2.face_offsets(), faces)) {
949 }
950
952 mesh1_attributes, mesh2_attributes, AttrDomain::Face, {}, faces, threshold);
953 if (mismatch) {
954 return mismatch;
955 };
956
957 mismatch = construct_vert_mapping(mesh1, mesh2, verts, edges);
958 if (mismatch) {
959 return mismatch;
960 }
961
962 /* Now we double check that the other topology maps agree with this vertex mapping. */
963
964 if (!sort_edges(mesh1.edges(), mesh2.edges(), verts, edges)) {
966 }
967
968 make_set_sizes_one(edges);
969
971
972 if (!sort_corners_based_on_domain(mesh1.corner_verts(), mesh2.corner_verts(), verts, corners)) {
974 }
975
976 if (!sort_corners_based_on_domain(mesh1.corner_edges(), mesh2.corner_edges(), edges, corners)) {
978 }
979
980 make_set_sizes_one(corners);
981
982 corners.recalculate_inverse_maps();
983
984 if (!sort_faces_based_on_corners(corners, mesh1.face_offsets(), mesh2.face_offsets(), faces)) {
986 }
987
988 make_set_sizes_one(faces);
989
990 /* The meshes are isomorphic, we now just need to determine if they are equal i.e., the indices
991 * are the same. */
992 for (const int sorted_i : verts.from_sorted1.index_range()) {
993 if (verts.from_sorted1[sorted_i] != verts.from_sorted2[sorted_i]) {
995 }
996 }
997 /* Skip the test for edges, since a lot of tests actually have different edge indices.
998 * TODO: remove this once those tests have been updated. */
999 for (const int sorted_i : corners.from_sorted1.index_range()) {
1000 if (corners.from_sorted1[sorted_i] != corners.from_sorted2[sorted_i]) {
1001 return GeoMismatch::Indices;
1002 }
1003 }
1004 for (const int sorted_i : faces.from_sorted1.index_range()) {
1005 if (faces.from_sorted1[sorted_i] != faces.from_sorted2[sorted_i]) {
1006 return GeoMismatch::Indices;
1007 }
1008 }
1009
1010 /* No mismatches found. */
1011 return std::nullopt;
1012}
1013
1017static bool sort_curves(const OffsetIndices<int> offset_indices1,
1018 const OffsetIndices<int> offset_indices2,
1020{
1021 Array<int> curve_point_counts1(offset_indices1.size());
1022 Array<int> curve_point_counts2(offset_indices2.size());
1024 offset_indices1, offset_indices1.index_range(), curve_point_counts1.as_mutable_span());
1026 offset_indices2, offset_indices2.index_range(), curve_point_counts2.as_mutable_span());
1028 curves.from_sorted1,
1029 curves.from_sorted2,
1030 curve_point_counts1.as_span(),
1031 curve_point_counts2.as_span());
1032 const bool curves_sizes_match = update_set_ids("CURVE_IDS",
1033 curves.set_ids,
1034 curve_point_counts1.as_span(),
1035 curve_point_counts2.as_span(),
1036 curves.from_sorted1,
1037 curves.from_sorted2,
1038 0);
1039 if (!curves_sizes_match) {
1040 return false;
1041 }
1042 update_set_sizes(curves.set_ids, curves.set_sizes);
1043 return true;
1044}
1045
1046std::optional<GeoMismatch> compare_curves(const CurvesGeometry &curves1,
1047 const CurvesGeometry &curves2,
1048 const float threshold)
1049{
1050 /* These will be assumed implicitly later on. */
1051 if (curves1.points_num() != curves2.points_num()) {
1053 }
1054 if (curves1.curves_num() != curves2.curves_num()) {
1056 }
1057
1058 std::optional<GeoMismatch> mismatch = {};
1059
1060 const AttributeAccessor curves1_attributes = curves1.attributes();
1061 const AttributeAccessor curves2_attributes = curves2.attributes();
1062 mismatch = verify_attributes_compatible(curves1_attributes, curves2_attributes);
1063 if (mismatch) {
1064 return mismatch;
1065 }
1066
1067 IndexMapping points(curves1.points_num());
1069 curves1_attributes, curves2_attributes, AttrDomain::Point, {}, points, threshold);
1070 if (mismatch) {
1071 return mismatch;
1072 }
1073
1074 IndexMapping curves(curves1.curves_num());
1075 if (!sort_curves(curves1.offsets(), curves2.offsets(), curves)) {
1077 }
1078
1080 curves1_attributes, curves2_attributes, AttrDomain::Curve, {}, curves, threshold);
1081 if (mismatch) {
1082 return mismatch;
1083 }
1084
1085 for (const int sorted_i : points.from_sorted1.index_range()) {
1086 if (points.from_sorted1[sorted_i] != points.from_sorted2[sorted_i]) {
1087 return GeoMismatch::Indices;
1088 }
1089 }
1090
1091 for (const int sorted_i : curves.from_sorted1.index_range()) {
1092 if (curves.from_sorted1[sorted_i] != curves.from_sorted2[sorted_i]) {
1093 return GeoMismatch::Indices;
1094 }
1095 }
1096
1097 /* No mismatches found. */
1098 return std::nullopt;
1099}
1100
1101std::optional<GeoMismatch> compare_lattices(const Lattice &lattice1,
1102 const Lattice &lattice2,
1103 float threshold)
1104{
1105 if (lattice1.pntsu != lattice2.pntsu) {
1107 }
1108 if (lattice1.pntsv != lattice2.pntsv) {
1110 }
1111 if (lattice1.pntsw != lattice2.pntsw) {
1113 }
1114
1115 const int num_points = lattice1.pntsu * lattice1.pntsv * lattice1.pntsw;
1116 const Span<BPoint> bpoints1 = {lattice1.def, num_points};
1117 const Span<BPoint> bpoints2 = {lattice2.def, num_points};
1118 for (const int i : IndexRange(num_points)) {
1119 const float3 co1 = bpoints1[i].vec;
1120 const float3 co2 = bpoints2[i].vec;
1121 for (const int component : IndexRange(3)) {
1122 if (values_different(co1[component], co2[component], threshold)) {
1124 }
1125 }
1126 }
1127
1128 /* No mismatches found. */
1129 return std::nullopt;
1130}
1131
1132static std::optional<GeoMismatch> compare_grease_pencil_layer(const GreasePencil &grease_pencil_1,
1133 const GreasePencil &grease_pencil_2,
1134 const greasepencil::Layer &layer_1,
1135 const greasepencil::Layer &layer_2,
1136 const float threshold)
1137{
1138 if (layer_1.name() != layer_2.name()) {
1140 }
1141 if (layer_1.frames().size() != layer_2.frames().size()) {
1143 }
1144
1145 const Span<greasepencil::FramesMapKeyT> sorted_keys_1 = layer_1.sorted_keys();
1146 const Span<greasepencil::FramesMapKeyT> sorted_keys_2 = layer_2.sorted_keys();
1147 for (const int i : sorted_keys_1.index_range()) {
1148 if (sorted_keys_1[i] != sorted_keys_2[i]) {
1149 return GeoMismatch::Frames;
1150 }
1151 }
1152
1153 std::optional<GeoMismatch> mismatch = {};
1154 for (const greasepencil::FramesMapKeyT key : layer_1.frames().keys()) {
1155 const GreasePencilFrame *frame_1 = layer_1.frame_at(key);
1156 const GreasePencilFrame *frame_2 = layer_2.frame_at(key);
1157 if ((frame_1 == nullptr) != (frame_2 == nullptr)) {
1158 return GeoMismatch::Frames;
1159 }
1160 if (frame_1 == nullptr) {
1161 continue;
1162 }
1163 const bke::greasepencil::Drawing *drawing_1 = grease_pencil_1.get_drawing_at(layer_1, key);
1164 const bke::greasepencil::Drawing *drawing_2 = grease_pencil_2.get_drawing_at(layer_2, key);
1165 if ((drawing_1 == nullptr) != (drawing_2 == nullptr)) {
1166 return GeoMismatch::Frames;
1167 }
1168 if (drawing_1 == nullptr) {
1169 continue;
1170 }
1171
1172 mismatch = compare_curves(drawing_1->strokes(), drawing_2->strokes(), threshold);
1173 if (mismatch) {
1174 return mismatch;
1175 }
1176 }
1177
1178 /* No mismatches found. */
1179 return std::nullopt;
1180}
1181
1182std::optional<GeoMismatch> compare_grease_pencil(const GreasePencil &grease_pencil_1,
1183 const GreasePencil &grease_pencil_2,
1184 const float threshold)
1185{
1186 const Span<const greasepencil::Layer *> layers_1 = grease_pencil_1.layers();
1187 const Span<const greasepencil::Layer *> layers_2 = grease_pencil_2.layers();
1188 if (layers_1.size() != layers_2.size()) {
1190 }
1191
1192 std::optional<GeoMismatch> mismatch = {};
1193
1194 const AttributeAccessor grease_pencil_1_attributes = grease_pencil_1.attributes();
1195 const AttributeAccessor grease_pencil_2_attributes = grease_pencil_2.attributes();
1196 mismatch = verify_attributes_compatible(grease_pencil_1_attributes, grease_pencil_2_attributes);
1197 if (mismatch) {
1198 return mismatch;
1199 }
1200
1201 IndexMapping layers(layers_1.size());
1202 mismatch = sort_domain_using_attributes(grease_pencil_1_attributes,
1203 grease_pencil_2_attributes,
1205 {},
1206 layers,
1207 threshold);
1208 if (mismatch) {
1209 return mismatch;
1210 }
1211
1212 for (const int sorted_i : layers.from_sorted1.index_range()) {
1213 if (layers.from_sorted1[sorted_i] != layers.from_sorted2[sorted_i]) {
1214 /* Layers are out of order. */
1216 }
1217 }
1218
1219 for (const int layer : layers_1.index_range()) {
1220 mismatch = compare_grease_pencil_layer(
1221 grease_pencil_1, grease_pencil_2, *layers_1[layer], *layers_2[layer], threshold);
1222 if (mismatch) {
1223 return mismatch;
1224 }
1225 }
1226
1227 /* No mismatches found. */
1228 return std::nullopt;
1229}
1230
1231} // namespace blender::bke::compare_geometry
Low-level operations for grease pencil.
#define CLOG_WARN(clg_ref,...)
Definition CLG_log.h:189
#define BLI_assert_unreachable()
#define ELEM(...)
int64_t size() const
Definition BLI_array.hh:267
Span< T > as_span() const
Definition BLI_array.hh:254
MutableSpan< T > as_mutable_span()
Definition BLI_array.hh:259
const T * end() const
Definition BLI_array.hh:336
IndexRange index_range() const
Definition BLI_array.hh:371
void fill(const T &value) const
Definition BLI_array.hh:283
const T * begin() const
Definition BLI_array.hh:332
const void * data() const
int64_t size() const
constexpr IndexRange()=default
constexpr int64_t size() const
Definition BLI_span.hh:499
constexpr MutableSpan slice(const int64_t start, const int64_t size) const
Definition BLI_span.hh:579
constexpr bool is_empty() const
Definition BLI_span.hh:515
constexpr T * end() const
Definition BLI_span.hh:554
constexpr T * begin() const
Definition BLI_span.hh:550
constexpr IndexRange index_range() const
Definition BLI_span.hh:676
bool remove_as(const ForwardKey &key)
Definition BLI_set.hh:408
bool contains(const Key &key) const
Definition BLI_set.hh:310
int64_t remove_if(Predicate &&predicate)
Definition BLI_set.hh:534
constexpr int64_t size() const
Definition BLI_span.hh:256
constexpr IndexRange index_range() const
Definition BLI_span.hh:405
void append(const T &value)
bool is_empty() const
const T & first() const
Set< StringRefNull > all_names() const
GAttributeReader lookup(const StringRef name) const
AttributeAccessor attributes() const
const bke::CurvesGeometry & strokes() const
const Map< FramesMapKeyT, GreasePencilFrame > & frames() const
const GreasePencilFrame * frame_at(const int frame_number) const
Span< FramesMapKeyT > sorted_keys() const
constexpr bool startswith(StringRef prefix) const
#define layer
#define T
static bool sort_curves(const OffsetIndices< int > offset_indices1, const OffsetIndices< int > offset_indices2, IndexMapping &curves)
std::optional< GeoMismatch > 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...
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 bool ignored_attribute(const StringRef name)
static bool sort_using_values(const StringRef name, const Span< T > values1, const Span< T > values2, const float threshold, IndexMapping &maps)
static void edges_from_vert_sets(const Span< int2 > edges, const Span< int > verts_to_sorted, const Span< int > vert_set_ids, MutableSpan< OrderedEdge > r_edges)
static std::optional< GeoMismatch > verify_attributes_compatible(const AttributeAccessor &attributes1, const AttributeAccessor &attributes2)
static void to_static_int_component_type(const AttrType type, Fn &&fn)
static bool sort_corners_based_on_domain(const Span< int > corner_domain1, const Span< int > corner_domain2, const IndexMapping &domain, IndexMapping &corners)
static void make_set_sizes_one(IndexMapping &indices)
static void update_set_sizes(const Span< int > set_ids, MutableSpan< int > set_sizes)
static bool sort_edges(const Span< int2 > edges1, const Span< int2 > edges2, const IndexMapping &verts, IndexMapping &edges)
static void gather_component(const GSpan values, const int components_num, const int component, MutableSpan< ComponentT > dst)
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 update_set_ids(StringRef name, MutableSpan< int > set_ids, const Span< T > values1, const Span< T > values2, const Span< int > sorted_to_values1, const Span< int > sorted_to_values2, const float threshold)
static bool all_set_sizes_one(const Span< int > set_sizes)
static std::optional< GeoMismatch > compare_grease_pencil_layer(const GreasePencil &grease_pencil_1, const GreasePencil &grease_pencil_2, const greasepencil::Layer &layer_1, const greasepencil::Layer &layer_2, const float threshold)
static std::optional< GeoMismatch > construct_vert_mapping(const Mesh &mesh1, const Mesh &mesh2, IndexMapping &verts, IndexMapping &edges)
std::optional< GeoMismatch > compare_grease_pencil(const GreasePencil &grease_pencil_1, const GreasePencil &grease_pencil_2, float threshold)
Checks if two Grease Pencil geometries are different, returning the type of mismatch if any.
std::optional< GeoMismatch > compare_curves(const CurvesGeometry &curves1, const CurvesGeometry &curves2, float threshold)
Checks if the two curves geometries are different, returning the type of mismatch if any....
static std::optional< GeoMismatch > sort_domain_using_attributes(const AttributeAccessor &attributes1, const AttributeAccessor &attributes2, const AttrDomain domain, const Span< StringRef > excluded_attributes, IndexMapping &maps, const float threshold)
static bool values_different(const T value1, const T value2, const float threshold)
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)
static GeoMismatch attribute_mismatch_for_domain(const AttrDomain domain)
static void sort_indices(MutableSpan< int > indices, const Span< T > values)
static std::optional< AttributeComponents > get_attribute_components(const AttrType type)
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)
static bool sort_faces_based_on_corners(const IndexMapping &corners, const Span< int > face_offsets1, const Span< int > face_offsets2, IndexMapping &faces)
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)
const char * mismatch_to_string(const GeoMismatch &mismatch)
std::optional< GeoMismatch > compare_lattices(const Lattice &lattice1, const Lattice &lattice2, float threshold)
Checks if the two lattices are different, returning the type of mismatch if any.
GroupedSpan< int > build_vert_to_edge_map(Span< int2 > edges, int verts_num, Array< int > &r_offsets, Array< int > &r_indices)
bool attribute_name_is_anonymous(const StringRef name)
AttrType cpp_type_to_attribute_type(const CPPType &type)
void copy_group_sizes(OffsetIndices< int > offsets, const IndexMask &mask, MutableSpan< int > sizes)
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
__int64 int64_t
Definition BKE_text.h:90
MINLINE bool compare_threshold_relative(float value1, float value2, float thresh)
VecBase< int32_t, 2 > int2
BMesh const char void * data
unsigned char uint8_t
Definition BKE_text.h:79
VecBase< float, 3 > float3
ATTR_WARN_UNUSED_RESULT const BMVert const BMEdge * e
signed char int8_t
Definition BKE_text.h:76
signed short int16_t
Definition BKE_text.h:77
struct BPoint * def
OrderedEdge(const int v1, const int v2)