IO: Fix bug exporting dupli parent/child relations

Exporting a scene to USD or Alembic would fail when there are multiple
duplicates of parent & child objects, duplicated by the same object. For
example, this happens when such a hierarchy of objects is contained in a
collection, and that collection is instanced multiple times by mesh
vertices. The problem here is that the 'parent' pointer of each
duplicated object points to the real parent; Blender would not figure
out properly which duplicated parent should be used.

This is now resolved by keeping track of the persistent ID of each
duplicated instance, which makes it possible to reconstruct the
parent-child relations of duplicated objects. This does use up some
memory for each dupli, so it could be heavy to export a Spring scene
(with all the pebbles and leaves), but it's only a small addition on top
of the USD/Alembic writer objects that have to be created anyway. At
least with this patch, they're created correctly.

Code-wise, the following changes are made:

- The export graph (that maps export parent to its export children) used
  to have as its key (Object, Duplicator). This is insufficient to
  correctly distinguish between multiple duplis of the same object by
  the same duplicator, so this is now extended to (Object, Duplicator,
  Persistent ID). To make this possible, new classes `ObjectIdentifier`
  and `PersistentID` are introduced.
- Finding the parent of a duplicated object is done via its persistent
  ID. In Python notation, the code first tries to find the parent
  instance where `child_persistent_id[1:] == parent_persistent_id[1:]`.
  If that fails, the dupli with persistent ID `child_persistent_id[1:]`
  is used as parent.

Reviewed By: sergey

Differential Revision: https://developer.blender.org/D8233

2 files changed, 204 insertions, 0 deletions

diff --git a/tests/gtests/usd/CMakeLists.txt b/tests/gtests/usd/CMakeLists.txt
index d2bfe5e1306..0caa2fac155 100644
--- a/tests/gtests/usd/CMakeLists.txt
+++ b/tests/gtests/usd/CMakeLists.txt
@@ -67,6 +67,7 @@ get_property(BLENDER_SORTED_LIBS GLOBAL PROPERTY BLENDER_SORTED_LIBS_PROP)
 set(SRC
   abstract_hierarchy_iterator_test.cc
   hierarchy_context_order_test.cc
+  object_identifier_test.cc
 )
 
 # TODO(Sybren): re-enable this unit test.
diff --git a/tests/gtests/usd/object_identifier_test.cc b/tests/gtests/usd/object_identifier_test.cc
new file mode 100644
index 00000000000..a914ec7e89d
--- /dev/null
+++ b/tests/gtests/usd/object_identifier_test.cc
@@ -0,0 +1,203 @@
+/*
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * The Original Code is Copyright (C) 2019 Blender Foundation.
+ * All rights reserved.
+ */
+#include "IO_abstract_hierarchy_iterator.h"
+
+#include "testing/testing.h"
+
+#include "BLI_utildefines.h"
+
+#include <climits>
+
+namespace blender {
+namespace io {
+
+namespace {
+
+/* Return object pointer for use in tests. This makes it possible to reliably test for
+ * order/equality functions while using hard-coded values for simplicity. */
+Object *fake_pointer(int value)
+{
+  return static_cast<Object *>(POINTER_FROM_INT(value));
+}
+
+/* PersistentID subclass for use in tests, making it easier to construct test values. */
+class TestPersistentID : public PersistentID {
+ public:
+  TestPersistentID(int value0, int value1)
+  {
+    persistent_id_[0] = value0;
+    persistent_id_[1] = value1;
+    persistent_id_[2] = INT_MAX;
+  }
+  explicit TestPersistentID(int value0) : TestPersistentID(value0, INT_MAX)
+  {
+  }
+};
+
+/* ObjectIdentifier subclass for use in tests, making it easier to construct test values. */
+class TestObjectIdentifier : public ObjectIdentifier {
+ public:
+  TestObjectIdentifier(Object *object, Object *duplicated_by, const PersistentID &persistent_id)
+      : ObjectIdentifier(object, duplicated_by, persistent_id)
+  {
+  }
+};
+
+}  // namespace
+
+class ObjectIdentifierOrderTest : public testing::Test {
+};
+
+TEST_F(ObjectIdentifierOrderTest, graph_root)
+{
+  ObjectIdentifier id_root_1 = ObjectIdentifier::for_graph_root();
+  ObjectIdentifier id_root_2 = ObjectIdentifier::for_graph_root();
+  EXPECT_TRUE(id_root_1 == id_root_2);
+  EXPECT_FALSE(id_root_1 < id_root_2);
+  EXPECT_FALSE(id_root_2 < id_root_1);
+
+  ObjectIdentifier id_a = ObjectIdentifier::for_real_object(fake_pointer(1));
+  EXPECT_FALSE(id_root_1 == id_a);
+  EXPECT_TRUE(id_root_1 < id_a);
+  EXPECT_FALSE(id_a < id_root_1);
+
+  ObjectIdentifier id_accidental_root = ObjectIdentifier::for_real_object(nullptr);
+  EXPECT_TRUE(id_root_1 == id_accidental_root);
+  EXPECT_FALSE(id_root_1 < id_accidental_root);
+  EXPECT_FALSE(id_accidental_root < id_root_1);
+}
+
+TEST_F(ObjectIdentifierOrderTest, real_objects)
+{
+  ObjectIdentifier id_a = ObjectIdentifier::for_real_object(fake_pointer(1));
+  ObjectIdentifier id_b = ObjectIdentifier::for_real_object(fake_pointer(2));
+  EXPECT_FALSE(id_a == id_b);
+  EXPECT_TRUE(id_a < id_b);
+}
+
+TEST_F(ObjectIdentifierOrderTest, duplicated_objects)
+{
+  ObjectIdentifier id_real_a = ObjectIdentifier::for_real_object(fake_pointer(1));
+  TestObjectIdentifier id_dupli_a(fake_pointer(1), fake_pointer(2), TestPersistentID(0));
+  TestObjectIdentifier id_dupli_b(fake_pointer(1), fake_pointer(3), TestPersistentID(0));
+  TestObjectIdentifier id_different_dupli_b(fake_pointer(1), fake_pointer(3), TestPersistentID(1));
+
+  EXPECT_FALSE(id_real_a == id_dupli_a);
+  EXPECT_FALSE(id_dupli_a == id_dupli_b);
+  EXPECT_TRUE(id_real_a < id_dupli_a);
+  EXPECT_TRUE(id_real_a < id_dupli_b);
+  EXPECT_TRUE(id_dupli_a < id_dupli_b);
+  EXPECT_TRUE(id_dupli_a < id_different_dupli_b);
+
+  EXPECT_FALSE(id_dupli_b == id_different_dupli_b);
+  EXPECT_FALSE(id_dupli_a == id_different_dupli_b);
+  EXPECT_TRUE(id_dupli_b < id_different_dupli_b);
+  EXPECT_FALSE(id_different_dupli_b < id_dupli_b);
+}
+
+TEST_F(ObjectIdentifierOrderTest, behaviour_as_map_keys)
+{
+  ObjectIdentifier id_root = ObjectIdentifier::for_graph_root();
+  ObjectIdentifier id_another_root = ObjectIdentifier::for_graph_root();
+  ObjectIdentifier id_real_a = ObjectIdentifier::for_real_object(fake_pointer(1));
+  TestObjectIdentifier id_dupli_a(fake_pointer(1), fake_pointer(2), TestPersistentID(0));
+  TestObjectIdentifier id_dupli_b(fake_pointer(1), fake_pointer(3), TestPersistentID(0));
+  AbstractHierarchyIterator::ExportGraph graph;
+
+  /* This inserts the keys with default values. */
+  graph[id_root];
+  graph[id_real_a];
+  graph[id_dupli_a];
+  graph[id_dupli_b];
+  graph[id_another_root];
+
+  EXPECT_EQ(4, graph.size());
+
+  graph.erase(id_another_root);
+  EXPECT_EQ(3, graph.size());
+
+  TestObjectIdentifier id_another_dupli_b(fake_pointer(1), fake_pointer(3), TestPersistentID(0));
+  graph.erase(id_another_dupli_b);
+  EXPECT_EQ(2, graph.size());
+}
+
+TEST_F(ObjectIdentifierOrderTest, map_copy_and_update)
+{
+  ObjectIdentifier id_root = ObjectIdentifier::for_graph_root();
+  ObjectIdentifier id_real_a = ObjectIdentifier::for_real_object(fake_pointer(1));
+  TestObjectIdentifier id_dupli_a(fake_pointer(1), fake_pointer(2), TestPersistentID(0));
+  TestObjectIdentifier id_dupli_b(fake_pointer(1), fake_pointer(3), TestPersistentID(0));
+  TestObjectIdentifier id_dupli_c(fake_pointer(1), fake_pointer(3), TestPersistentID(1));
+  AbstractHierarchyIterator::ExportGraph graph;
+
+  /* This inserts the keys with default values. */
+  graph[id_root];
+  graph[id_real_a];
+  graph[id_dupli_a];
+  graph[id_dupli_b];
+  graph[id_dupli_c];
+  EXPECT_EQ(5, graph.size());
+
+  AbstractHierarchyIterator::ExportGraph graph_copy = graph;
+  EXPECT_EQ(5, graph_copy.size());
+
+  // Updating a value in a copy should not update the original.
+  HierarchyContext ctx1;
+  HierarchyContext ctx2;
+  ctx1.object = fake_pointer(1);
+  ctx2.object = fake_pointer(2);
+
+  graph_copy[id_root].insert(&ctx1);
+  EXPECT_EQ(0, graph[id_root].size());
+
+  // Deleting a key in the copy should not update the original.
+  graph_copy.erase(id_dupli_c);
+  EXPECT_EQ(4, graph_copy.size());
+  EXPECT_EQ(5, graph.size());
+}
+
+class PersistentIDTest : public testing::Test {
+};
+
+TEST_F(PersistentIDTest, is_from_same_instancer)
+{
+  PersistentID child_id_a = TestPersistentID(42, 327);
+  PersistentID child_id_b = TestPersistentID(17, 327);
+  PersistentID child_id_c = TestPersistentID(17);
+
+  EXPECT_TRUE(child_id_a.is_from_same_instancer_as(child_id_b));
+  EXPECT_FALSE(child_id_a.is_from_same_instancer_as(child_id_c));
+}
+
+TEST_F(PersistentIDTest, instancer_id)
+{
+  PersistentID child_id = TestPersistentID(42, 327);
+
+  PersistentID expect_instancer_id = TestPersistentID(327);
+  EXPECT_EQ(expect_instancer_id, child_id.instancer_pid());
+
+  PersistentID empty_id;
+  EXPECT_EQ(empty_id, child_id.instancer_pid().instancer_pid());
+
+  EXPECT_LT(child_id, expect_instancer_id);
+  EXPECT_LT(expect_instancer_id, empty_id);
+}
+
+}  // namespace io
+}  // namespace blender