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

1 files changed, 57 insertions, 0 deletions

diff --git a/tests/python/alembic_tests.py b/tests/python/alembic_tests.py
index 5f8113729c3..4d7ae97b327 100644
--- a/tests/python/alembic_tests.py
+++ b/tests/python/alembic_tests.py
@@ -243,6 +243,63 @@ class DupliGroupExportTest(AbstractAlembicTest):
              2.0, 3.0, 0.0, 1.0]
         )
 
+    @with_tempdir
+    def test_multiple_duplicated_hierarchies(self, tempdir: pathlib.Path):
+        abc = tempdir / "multiple-duplicated-hierarchies.abc"
+        script = "import bpy; bpy.ops.wm.alembic_export(filepath='%s', start=1, end=1)" % abc.as_posix()
+        self.run_blender('multiple-duplicated-hierarchies.blend', script)
+
+        # This is the expected hierarchy:
+        # ABC
+        #  `--Triangle
+        #      |--Triangle
+        #      |--Empty-1
+        #      |    `--Pole-0-1
+        #      |        |--Pole
+        #      |        `--Block-1-1
+        #      |            `--Block
+        #      |--Empty
+        #      |    `--Pole-0
+        #      |        |--Pole
+        #      |        `--Block-1
+        #      |            `--Block
+        #      |--Empty-2
+        #      |    `--Pole-0-2
+        #      |        |--Pole
+        #      |        `--Block-1-2
+        #      |            `--Block
+        #      `--Empty-0
+        #          `--Pole-0-0
+        #              |--Pole
+        #              `--Block-1-0
+        #                  `--Block
+
+        # Now check the resulting Alembic file.
+        xform = self.abcprop(abc, '/Triangle/Empty-1/Pole-0-1/Block-1-1/.xform')
+        self.assertEqual(1, xform['.inherits'])
+        self.assertAlmostEqualFloatArray(
+            xform['.vals'],
+            [1.0, 0.0, 0.0, 0.0,
+             0.0, 1.0, 0.0, 0.0,
+             0.0, 0.0, 1.0, 0.0,
+             0.0, 2.0, 0.0, 1.0]
+        )
+
+        # If the property can be gotten, the hierarchy is okay. No need to actually check each xform.
+        self.abcprop(abc, '/Triangle/.xform')
+        self.abcprop(abc, '/Triangle/Empty-1/.xform')
+        self.abcprop(abc, '/Triangle/Empty-1/Pole-0-1/.xform')
+        self.abcprop(abc, '/Triangle/Empty-1/Pole-0-1/Block-1-1/.xform')
+        self.abcprop(abc, '/Triangle/Empty/.xform')
+        self.abcprop(abc, '/Triangle/Empty/Pole-0/.xform')
+        self.abcprop(abc, '/Triangle/Empty/Pole-0/Block-1/.xform')
+        self.abcprop(abc, '/Triangle/Empty-2/.xform')
+        self.abcprop(abc, '/Triangle/Empty-2/Pole-0-2/.xform')
+        self.abcprop(abc, '/Triangle/Empty-2/Pole-0-2/Block-1-2/.xform')
+        self.abcprop(abc, '/Triangle/Empty-0/.xform')
+        self.abcprop(abc, '/Triangle/Empty-0/Pole-0-0/.xform')
+        self.abcprop(abc, '/Triangle/Empty-0/Pole-0-0/Block-1-0/.xform')
+
 
 class CurveExportTest(AbstractAlembicTest):
     @with_tempdir