Why are GUIDs not globally unique?

Helper

On 18/08/2017 at 04:25, xxxxxxxx wrote:

Hi Martin, first and foremost thansk for your patience.

This week has been busy not to have been cope with reordering my findings in a short time and I also wanted to extend my research to reduce the "corner case" risk.

Cinema 4D API offers basically two means to uniquely identify objects: BaseObject::GetGUID() and BaseList2D::GetMarker() which respectively access the object's unique ID and object's GeMarker.

The intent of my research has been to demonstrate that GUID(s) is indeed a reliable way to track objects in Cinema across different user interaction scenarios and aided by GeMarker(s) they offer a complete way to track objects uniquely around Cinema.

Scanning a very simple scene and printing the IDs and GeMarkers info belonging to the objects present provides the following table:

===================================================================================================  
  [ { GeMarker CRC /  GetMarkerStampEx  } |     GetGUID        ]                                     
  [ { 000459316928 / 0014570499 # 07496 }                      ] TraversalTest01.c4d  
  [ { 003110699520 / 0014622782 # 07807 } | 0x739249CE036A085C ][0]Cube.A : Cube, 5159-0/0/0/0-0/1  
  [ { 000611561600 / 0002058671 # 09006 } | 0x4B1F714B50E82730 ][0][C]Cube.A : Polygon, 5100-0/0/0/0-1/1  
  [ { 003620385536 / 0063246992 # 13019 } | 0x29738F0DAFFED8E7 ][1]+Sphere.A : Sphere, 5160-0/0/0/0-0/1  
  [ { 002984169472 / 0002058671 # 09014 } | 0x51A98A6F2EF6E7EF ][1]+[C]Sphere.A : Polygon, 5100-0/0/0/0-1/1  
  [ { 003436609536 / 0002058671 # 09023 } | 0xD1A95C51EE8F50E6 ][1]+[C][D]Sphere.A : Polygon, 5100-0/0/0/0-1/1  
  [ { 000174035360 / 0088455968 # 08560 } | 0x05B40FA55FC2F5DF ][2]++Bulge : Bulge, 5129-0/0/0/0-0/1  
  [ { 003097937408 / 0063290296 # 13696 } | 0x4EE5F93031C05A1A ][0]Sphere.C : Sphere, 5160-0/0/0/0-0/1  
  [ { 002138721536 / 0002058672 # 09030 } | 0x51A98A6F2EF6E7EF ][0][C]Sphere.C : Polygon, 5100-0/0/0/0-1/1  
  [ { 003100995840 / 0014593669 # 07682 } | 0x2879AC49124B66C3 ][1]+Cube.C : Cube, 5159-0/0/0/0-0/1  
  [ { 000041026420 / 0002058672 # 09039 } | 0x4B1F714B50E82730 ][1]+[C]Cube.C : Polygon, 5100-0/0/0/0-1/1  
  [ { 002939917824 / 0014594104 # 07733 } | 0x06B497DDDB536CC5 ][0]Cube.D : Cube, 5159-0/0/0/0-0/1  
  [ { 002548005888 / 0002058672 # 09047 } | 0x646E97C2D42A60BE ][0][C]Cube.D : Polygon, 5100-0/0/0/0-1/1  
  [ { 001481651072 / 0002058672 # 09085 } | 0xE46E41FC1453D7B7 ][0][C][D]Cube.D : Polygon, 5100-0/0/0/0-1/1  
  [ { 000965783296 / 0088388848 # 08324 } | 0x062A5B18C994B055 ][1]+Bend : Bend, 5128-0/0/0/0-0/1  
  [ { 004036197120 / 0014594509 # 07747 } | 0x42F618087566F85F ][1]+Cube.E : Cube, 5159-0/0/0/0-0/1  
  [ { 001382765824 / 0002058672 # 09055 } | 0x646E97C2D42A60BE ][1]+[C]Cube.E : Polygon, 5100-0/0/0/0-1/1  
  [ { 002404496384 / 0002058672 # 09078 } | 0xE46E41FC1453D7B7 ][1]+[C][D]Cube.E : Polygon, 5100-0/0/0/0-1/1  
  [ { 002284037888 / 0088342184 # 08167 } | 0x7E14190FED9A5DE4 ][2]++Twist : Twist, 5134-0/0/0/0-0/1  
  [ { 001033116672 / 0014594922 # 07761 } | 0x1ACC3DCCC83D6EE4 ][2]++Cube.F : Cube, 5159-0/0/0/0-0/1  
  [ { 001744077952 / 0002058672 # 09063 } | 0x4B1F714B50E82730 ][2]++[C]Cube.F : Polygon, 5100-0/0/0/0-1/1  
  [ { 002722147328 / 0002058672 # 09071 } | 0xCB1FA77590919039 ][2]++[C][D]Cube.F : Polygon, 5100-0/0/0/0-1/1

In the table above the info after GUID is as follows: [ n]+++[C][D]<name> : <type name>, <type>-<other status flags>

[n]: n equals the nesting level in the hierarchy;
+++: graphical representation of the nesting level;
[C][D]: C refers to a cache object, D refers to a deform cache object;
<name>: refers to the object name;
<type name>: refers to the object's type name;
<type>: refers to the object type ID;
<other status flags>: other flags.
In order to validate the GUID and GeMarker generation mechanism and verify how it reacts upon scene modification a few interaction scenarios have been run (in cascade) on a simple test scene with identification data printed at each step.

The test scenes are available here:

ObjectsIdentification_SimpleTests.c4d[URL-REMOVED]
ObjectsIdentification_MographTests.c4d[URL-REMOVED]
ObjectsIdentification_ParticlesTests.c4d[URL-REMOVED]
The complete logs of the tests run are available here (the MoGraph and CA tests include examples scene took from the Content Browser) :
ObjectsIdentification_SimpleTests.txt[URL-REMOVED]
ObjectsIdentification_MographTests.txt[URL-REMOVED]
ObjectsIdentification_ParticlesTests.txt[URL-REMOVED]
ObjectsIdentification_CATests.txt[URL-REMOVED]
_ NOTE: The value for GeMarker is obtained by computing the CRC32 based on the values returned by GeMarker::GetMemory()._

...
    bl->GetMarker().GetMemory(data, size);
    const UInt32 crc32 = ZipFile::CalcCRC32(data, size);
    markerString = String::FloatToString(Float32(crc32), 12, 0)
...

_ NOTE: The value for the GUID is obtained by using String::HexToString conversion on the returned value from GetGUID. Although the value returned looks like a memory address it is not._

...
    const UInt64 guid = obj->GetGUID();  
  const String guidString = String::HexToString(guid);
...

Opening the file TraversalTest_01.c4d leads to the following results:

all GeMarker(s) (as well as the GetMarkerStampEx value pair(s)) belonging to generators are unique;
all GeMarker(s) belonging to caches (standard and deform) are unique;
all GUID(s) belonging to generators are unique;
all GUID(s) belonging to caches (standard and deform) with equal number of points and polygons are equal but different from their generator's GUID;
equal GUID(s) belonging to cache objects (sharing same number of points/polygons) are different from the GUID(s) of the deform cache objects (which are equal as well).

Rendering View (Ctrl-R) leads to the following results:
_ NOTE: _During a rendering process only object caches representing the final geometry of the objects are provided in the VolumeData() instance which means the ID data is extracted from the objects actually used by the Renderer.
To retrieve the initial generators it's required to implement a recursive function using BaseObject::GetCacheParent() to iterate up to the parent generator. Objects listed as "CacheP" are the root-cache parent of a cache object.

all GeMarker(s) belonging to caches (standard and deform) found in the VolumeData instance are equal to those in the source scene;
all GeMarker(s) belonging to generators (parents of the caches found in the VolumeData) are equal to those in the source scene;
all GUID(s) belonging to generators and caches (standard and deform) found in the VolumeData instance are equal to those in the source scene;

_
_
Rendering via IRR (Alt-R) leads to the following results:
NOTE: During a rendering process only object caches representing the final geometry of the objects are provided in the VolumeData() instance which means the ID data is extracted from the objects actually used by the Renderer.
_To retrieve the initial generators it's required to implement a recursive function using BaseObject::GetCacheParent() to iterate up to the parent generator. _ Objects listed as "CacheP" are the root-cache parent of a cache object.
IRR clones the active scene to run the interactive rendering in a separate thread and leave Cinema 4D free to interact with the user.

all GeMarker(s) belonging to caches (standard and deform) found in the VolumeData instance are new and unique;
all GeMarker(s) belonging to generators (parents of the caches found in the VolumeData) are equal to those in the source scene;
all GUID(s) belonging to generator and caches (standard and deform) found in the VolumeData instance are equal to those in the source scene;

Rendering in PV (Ctrl-R) leads to the following results:
_ NOTE: During a rendering process only object caches representing the final geometry of the objects are provided in the VolumeData() instance which means the ID data is extracted from the objects actually used by the Renderer. _
_To retrieve the initial generators it's required to implement a recursive function using BaseObject::GetCacheParent() to iterate up to the parent generator. _ Objects listed as "CacheP" are the root-cache parent of a cache object.
Render to PV clones the active scene to run the rendering in a separate thread and leave Cinema 4D free to interact with the user.

all GeMarker(s) belonging to caches (standard and deform) found in the VolumeData instance are new and unique;
all GeMarker(s) belonging to generators (parents of the caches found in the VolumeData) are equal to those in the source scene;
all GUID(s) belonging to generator and caches (standard and deform) are new and unique;

Cloning the scene (via simple Python script) leads to the following results:

all GeMarker(s) belonging to cloned generators are new and unique;
all GeMarker(s) belonging to cloned caches (standard and deform) are new and unique;
all GUID(s) belonging to cloned generators are new and unique;
all GUID(s) belonging to cloned caches (standard and deform) with equal number of points and polygons are equal in the cloned scene and are also equal to the corresponding ones in the source scene.

_
_
Copy &pasting active document's objects into a new document leads to the same results brought by Cloning the scene;

Swapping from cloned scene to source scene leads to the following results:

all GeMarker(s) belonging to generators are unchanged;
all GeMarker(s) belonging to caches (standard and deform) are new and unique (because caches are regenerated during document swapping);
all GUID(s) belonging to generators are unchanged (even the object affected by the change);
all GUID(s) belonging to caches (standard and deform) are unchanged.
all GUID(s) belonging to caches (standard and deform) with equal number of points and polygons are equal.

Changing a parameter affecting geometry representation (Fillet "ON" in Cube.C) leads to the following results:

all GeMarker(s) belonging to generators are unchanged;
GeMarker(s) belonging to unmodified caches (standard and deform) are unchanged;
GeMarker(s) belonging to modified caches (standard and deform) are new and unique;
all the GUID(s) belonging to generators are unchanged (even the object affected by the change);
GUID(s) belonging to unmodified caches (standard and deform) are unchanged;
all GUID(s) belonging to caches (standard and deform) with equal number of points and polygons are equal;
GUID(s) belonging to modified caches (standard and deform) are new and unique.

Undoing the parameter change affecting geometry representation leads to the following results:

all GeMarker(s) belonging to generators are unchanged;
GeMarker(s) belonging to unmodified caches (standard and deform) are unchanged;
GeMarker(s) belonging to modified caches (standard and deform) are new and unique;
all the GUID(s) belonging to generators are unchanged (even the object affected by the change);
GUID(s) belonging to unmodified caches (standard and deform) are unchanged;
GUID(s) belonging to modified caches (standard and deform) are new and unique.

Saving the scene (overwriting existing file) leads to the following results:

all GeMarker(s) are unchanged;
all GUID(s) are unchanged;
Closing Cinema 4D and opening the overwritten scene leads to the following results:
all GeMarker(s) belonging to generators are unchanged;
all GeMarker(s) belonging to caches (standard and deform) are new and unique;
all the GUID(s) belonging to generators and caches (standard and deform) are unchanged.

Saving the scene to a new file leads to the following results:

all GeMarker(s) are unchanged;
all GUID(s) are unchanged;

Closing Cinema 4D and opening the new saved scene leads to the following results:

all GeMarker(s) belonging to generators are unchanged;
all GeMarker(s) belonging to caches (standard and deform) are new and unique;
all the GUID(s) belonging to generators and caches (standard and deform) are unchanged.

Re-opening the initial scene leads to the following results:

all GeMarker(s) belonging to generators are unchanged;
all GeMarker(s) belonging to caches (standard and deform) are new and unique;
all the GUID(s) belonging to generators and caches (standard and deform) are unchanged.

In the end:

Using GUID(s) to identify objects across multiple scenes in Cinema 4D has proven to be efficient and effective. It should be noted that the tracking should not occur on cache level (where multiple objects can share the same GUID) but on generator level. All the tests conducted so far have shown no corner case where GUID(s) are failing.
When rendering instead is taken into consideration, GeMarker(s) are the way to go since GeMarker was designed exactly to identify Cinema4D objects in a non GUI context. A few distinctions should take place depending on the different rendering scenarios:
* if rendering is delivered in viewport ("Render View" / Ctrl-R) the scene is not cloned and all the GUID(s)/GeMarker(s) found in the VolumeData are exactly matching those used in the "source" scene;
* if rendering is delivered via IRR ("Interactive Region Render" / Alt-R) the scene is cloned and whilst GeMarker(s) for cache are regenerated, all GUID(s) and GeMarker(s) for generators are retained;
* if rendering is delivered via PV ("Render to Picture Viewer" / Shift-R) the scene is cloned and only GeMarker(s) for generators are retained. It should be also noted that GUID(s) and GeMarker(s) used in the rendering cloned scene are consistent across time which means that a particle or a mograph instance created in a specific frame retains the ID (both GUID and GeMarker) assigned for the whole lifespan of the item.
It's recommended, in the end, to rely on GUID(s) to identify objects whilst, when rendering takes place, it's recommended to use GeMarker(s) which has proven to be the only way to uniquely identify objects across both the "source scene" and the actually data used in rendering process.

Looking forward your thought or comments (or even better corner case), give best.
Riccardo

[URL-REMOVED] @maxon: This section contained a non-resolving link which has been removed.

Helper

On 18/08/2017 at 05:30, xxxxxxxx wrote:

Wow, thanks Riccardo! Please pin this topic somewhere.

Helper

On 18/08/2017 at 06:23, xxxxxxxx wrote:

Actually the plan is to add the info to the SDK docs.

Helper

On 18/08/2017 at 06:49, xxxxxxxx wrote:

Hi Riccardo,

thank you for your extensive research.

Unfortunately, your findings confirm my own research:

GUIDs are not unique as duplicated of the same GUID can appear in caches
GeMarker change when the generator updates objects. Thus loosing tracking between different render calls

Objects that are repesented in the scene work fine. Unfortunately, a typical Cinema 4D scene's geometry that needs to be rendered is mostly found in caches and deform caches. Generators and deformers cannot be rendered directly.

The generated geometry cannot be reliably tracked/identified. Identical GUIDs are used for different objects in caches. GeMarker change when the geometry is changed.

Generators should make use of unique IPs so that objects can be reliably tracked across different frames. Unfortunately, for example the Subdivsion Object does not generate IPs for its generated objects in the Cache. Putting a hierarchy of objects into a Subdivision object has two results: all objects are marked as control object. Control objects themselves indicate that they are not to be used directly but that they generate the data that should be used. Typically, this data is found in the cache of the object itself. The Subdivision Object exhibits different behaviour. All the generated geometry is put in it's own cache, regardless where the control object for that geometry. This way, there is no reliable way to deduct the control object that originally was responsible for creating the data.

The problem I have is not getting to the actual geometry to render but to keep track of which object generated what and to only update the changes. With rendering times of a few milliseconds it ridiculous to spend dozens of secoonds or even a few minutes to prepare the frame.

In conclusion: Ultimately, GUIDs and GeMarker can be used to differentiate between objects. Identification is not possible though. Also, UniqueIPs - a proposed method to track/identify genearated objects during animation - is not consistenly used by generators.

The same GUID is used for different objects in caches. Visible geometry for many scenes can be found exclusively in caches.
GeMarker changes when the geometry for generated objects change, making it impossible to identify the object between two consecutive renderings.
Cloning documents changes GeMarkers. Cloning is happening frequently when rendering.
The proposed mmethod to track generated object by using their UniqueIP fails as generators like the Subdivision Object does not assign UniqueIPs

BTW: I need to identify objects not only between consecutive renderings but I also track changes "LIVE" to immediately update the realtime rendering. I am not using VolumeData in the VideoPost Plugin for this very reason.

I am using Hierarchy class derived classes to traverse the scene and also handle instances myself.

Here is a scene that is showing some of the duplicate GUID problems and also shows how Subdivision Object is handling caches and UniqueIPs differently: https://drive.google.com/file/d/0BwFHFNK-2yFAMGpIVkRodDlxbzg/view?usp=sharing

Image of resulting test-rendering here: https://drive.google.com/file/d/0BwFHFNK-2yFAcjFlaGJ1NG5wb28/view?usp=sharing

Edit: Here is my log of the scene: https://drive.google.com/file/d/0BwFHFNK-2yFAUVhtU2ZOT21LV1E/view?usp=sharing
For IP I print the cache parent ID and the IP. ID in general is the assigned ID I created. (cached) has a CacheParent is not part of the scene the user sees in the object manager.

I am having troubles with identification in this scene mostly due to the nesting of instances and putting everything into a Subdivision Object. One Holder_01 "instance of an instance of an instance" and a couple of Holder_02 objects are eluding my efforts to identify them.

Thanks,
Martin

BTW: I am out of the office next week. So I will not be able to respond in a timely fashion.

Helper

On 18/08/2017 at 14:06, xxxxxxxx wrote:

Martin, attach few expression tags and you will get always changing addresses/pointers of objects. Same object remains untouched, but you make a mouse click and it changes and it will report to dirty flags, and most likely to ID assigning staff that you must remove/add things (not just update them slightly). Welcome to Cinema 4D >:E :))
Let's ask Maxon to solve this ID issue and update the API for recent couple of major Cinema versions.

Helper

On 18/08/2017 at 15:56, xxxxxxxx wrote:

i also would like is to be able to identify objects by using an unique object id.
as stated here BaseObject.GetGUID() is not unique (?)
and even if it is, there is no method to get the BaseObject if you just have the GUID.
(is there one?)

btw it would be nice if it wouldnt be just an in-memory id,
but would stay the same when quitting the app and reopening the file.

ps if you str() an object you get
<c4d.BaseObject object called 'Null/Null' with ID 5140 at 0x1412bd6d0>
is this hex address usable for indentification?

Helper

On 28/08/2017 at 01:31, xxxxxxxx wrote:

I have found that the best way to identify an object that is not in a cache is to use AddUniqueID(). This should be serialized to the file as well. It has been working fine for me.

If you don't care about changed IDs with cloned scenes or re-created objects, you can always use GeMarker().

My problem is that I actually have scenes where ALL visible geometry is exclusively coming from object caches. This is where my approaches start to fall appart. Most of the time I can rely on FindUniqueID() of the CacheParent() and the UniqueIP() to reconstruct a unique identification. Unfortunately, this breaks with ojects like the subdivision surface object who do not assign uniqueIPs and also do not make the generator source objects identifiable.

@zeorge: having the GUID, traversing the document to get the BaseObject should not be that time consuming. Even with several thousand objects.

Helper

On 28/08/2017 at 03:56, xxxxxxxx wrote:

If I may drop some insight here on why GUIDs might not always be unique: It's likely due to the use of crc32. In scenes with many objects, especially many generators used, there will be collisions.

I ended up calculating GUIDs myself, only using UniqueIPs, hasing them with xxHash (https://github.com/Cyan4973/xxHash), fixing some of the obvious shortcomings by adding dummy IPs for generators - or something like that, it's been a while.

Works pretty well for uniqely identifying objects across frames of an animation - unfortunately it's useless for identifying objects across insertions/deletions in the scene.

Originally posted by xxxxxxxx

Actually the plan is to add the info to the SDK docs.

Please add "not using crc32" to said plan.

Helper

On 28/08/2017 at 04:29, xxxxxxxx wrote:

From what I've experienced, the identical GUIDs were not due to hash clashing but actually objects that where generated from the same source object, thus being "identical" to them. Unfortunately, that makes it impossible to identify the generated objects

I also use hashing throughout my parsing and use 64-bit SipHash (https://131002.net/siphash/).

Helper

On 01/09/2017 at 09:44, xxxxxxxx wrote:

Thanks both Yves and Martin for keeping your insights to come.

@fused: actually we internally use CRC64 which make the chance to get GUID collisions really unlikely; the reason because there might be equal GUIDs in the scene is mostly related to how GUIDs are currently generated.
@assoc: to reduce (not to exclude) the chance to avoid GUIDs duplication you can enumerate you objects in the scene by setting their IP (BaseObject::SetUniqueIP()) using something like:

  
const Bool SetObjectsIP(BaseObject *op)  
{  
  Int32 ipnum = 1;  
  while (op)  
  {  
      if (!SetObjectsIP(op->GetDown()))  
          return false;  
  
      op->SetUniqueIP(ipnum++);  
  
      op = op->GetNext();  
  }  
  
  return true;  
}

As I've described in my previous post, we are aware of the fact that caches might end up in sharing the same UID, and we are also aware that unique identification is a pretty relevant topic for interactive rendering purposes. That said I'll try to rise up in the future an internal discussion on the topic to see if and how the desired behavior could be addressed.

Best, Riccardo.

Helper

On 04/09/2017 at 00:13, xxxxxxxx wrote:

Thanks Ricardo.

Yes, using SetUniqueIP() is what I would expect to be used by generators that have several objects in their caches. As I am parsing the scene - not generating objects myself - I have no influence how other generators are handling UniqueIPs.

In this regard, I noticed that the Subdivision object does not use UniqueIPs. So I am having a hard time to identify the generated objects between scene changes because they don't have UniqueIPs. So I was trying to use their GUID as fallback but then noticed that the Subdivision object had objects with the same GUID in its cache as well. The GeMarker unfortunately does not help either as it changes frequently.

So I have this case where all methods of the SDK to identify generated objects in a cache fails.

Thanks,
Martin