diff options
-rw-r--r-- | source/blender/io/alembic/exporter/abc_hierarchy_iterator.cc | 11 | ||||
-rw-r--r-- | source/blender/io/alembic/exporter/abc_hierarchy_iterator.h | 4 | ||||
-rw-r--r-- | source/blender/io/common/CMakeLists.txt | 5 | ||||
-rw-r--r-- | source/blender/io/common/IO_abstract_hierarchy_iterator.h | 47 | ||||
-rw-r--r-- | source/blender/io/common/IO_dupli_persistent_id.hh | 61 | ||||
-rw-r--r-- | source/blender/io/common/intern/abstract_hierarchy_iterator.cc | 72 | ||||
-rw-r--r-- | source/blender/io/common/intern/dupli_parent_finder.cc | 104 | ||||
-rw-r--r-- | source/blender/io/common/intern/dupli_parent_finder.hh | 62 | ||||
-rw-r--r-- | source/blender/io/common/intern/dupli_persistent_id.cc | 144 | ||||
-rw-r--r-- | source/blender/io/common/intern/object_identifier.cc | 116 | ||||
-rw-r--r-- | tests/gtests/usd/CMakeLists.txt | 1 | ||||
-rw-r--r-- | tests/gtests/usd/object_identifier_test.cc | 203 | ||||
-rw-r--r-- | tests/python/alembic_tests.py | 57 |
13 files changed, 835 insertions, 52 deletions
diff --git a/source/blender/io/alembic/exporter/abc_hierarchy_iterator.cc b/source/blender/io/alembic/exporter/abc_hierarchy_iterator.cc index 90004c0e85b..c83eaf3eede 100644 --- a/source/blender/io/alembic/exporter/abc_hierarchy_iterator.cc +++ b/source/blender/io/alembic/exporter/abc_hierarchy_iterator.cc @@ -107,20 +107,23 @@ AbstractHierarchyIterator::ExportGraph::key_type ABCHierarchyIterator:: determine_graph_index_object(const HierarchyContext *context) { if (params_.flatten_hierarchy) { - return std::make_pair(nullptr, nullptr); + return ObjectIdentifier::for_graph_root(); } return AbstractHierarchyIterator::determine_graph_index_object(context); } AbstractHierarchyIterator::ExportGraph::key_type ABCHierarchyIterator::determine_graph_index_dupli( - const HierarchyContext *context, const std::set<Object *> &dupli_set) + const HierarchyContext *context, + const DupliObject *dupli_object, + const DupliParentFinder &dupli_parent_finder) { if (params_.flatten_hierarchy) { - return std::make_pair(nullptr, nullptr); + return ObjectIdentifier::for_graph_root(); } - return AbstractHierarchyIterator::determine_graph_index_dupli(context, dupli_set); + return AbstractHierarchyIterator::determine_graph_index_dupli( + context, dupli_object, dupli_parent_finder); } Alembic::Abc::OObject ABCHierarchyIterator::get_alembic_parent( diff --git a/source/blender/io/alembic/exporter/abc_hierarchy_iterator.h b/source/blender/io/alembic/exporter/abc_hierarchy_iterator.h index edcb31806ba..3fe2d2c43d2 100644 --- a/source/blender/io/alembic/exporter/abc_hierarchy_iterator.h +++ b/source/blender/io/alembic/exporter/abc_hierarchy_iterator.h @@ -67,7 +67,9 @@ class ABCHierarchyIterator : public AbstractHierarchyIterator { virtual ExportGraph::key_type determine_graph_index_object( const HierarchyContext *context) override; virtual AbstractHierarchyIterator::ExportGraph::key_type determine_graph_index_dupli( - const HierarchyContext *context, const std::set<Object *> &dupli_set) override; + const HierarchyContext *context, + const DupliObject *dupli_object, + const DupliParentFinder &dupli_parent_finder) override; virtual AbstractHierarchyWriter *create_transform_writer( const HierarchyContext *context) override; diff --git a/source/blender/io/common/CMakeLists.txt b/source/blender/io/common/CMakeLists.txt index 4ed6f12762e..d2be4bbb58f 100644 --- a/source/blender/io/common/CMakeLists.txt +++ b/source/blender/io/common/CMakeLists.txt @@ -31,8 +31,13 @@ set(INC_SYS set(SRC intern/abstract_hierarchy_iterator.cc + intern/object_identifier.cc + intern/dupli_parent_finder.cc + intern/dupli_persistent_id.cc IO_abstract_hierarchy_iterator.h + IO_dupli_persistent_id.hh + intern/dupli_parent_finder.hh ) set(LIB diff --git a/source/blender/io/common/IO_abstract_hierarchy_iterator.h b/source/blender/io/common/IO_abstract_hierarchy_iterator.h index 5f84fd48b71..2669f137fd4 100644 --- a/source/blender/io/common/IO_abstract_hierarchy_iterator.h +++ b/source/blender/io/common/IO_abstract_hierarchy_iterator.h @@ -36,6 +36,8 @@ #ifndef __ABSTRACT_HIERARCHY_ITERATOR_H__ #define __ABSTRACT_HIERARCHY_ITERATOR_H__ +#include "IO_dupli_persistent_id.hh" + #include <map> #include <set> #include <string> @@ -52,6 +54,7 @@ namespace blender { namespace io { class AbstractHierarchyWriter; +class DupliParentFinder; /* HierarchyContext structs are created by the AbstractHierarchyIterator. Each HierarchyContext * struct contains everything necessary to export a single object to a file. */ @@ -60,6 +63,7 @@ struct HierarchyContext { Object *object; /* Evaluated object. */ Object *export_parent; Object *duplicator; + PersistentID persistent_id; float matrix_world[4][4]; std::string export_name; @@ -161,6 +165,35 @@ class EnsuredWriter { AbstractHierarchyWriter *operator->(); }; +/* Unique identifier for a (potentially duplicated) object. + * + * Instances of this class serve as key in the export graph of the + * AbstractHierarchyIterator. */ +class ObjectIdentifier { + public: + Object *object; + Object *duplicated_by; /* nullptr for real objects. */ + PersistentID persistent_id; + + protected: + ObjectIdentifier(Object *object, Object *duplicated_by, const PersistentID &persistent_id); + + public: + ObjectIdentifier(const ObjectIdentifier &other); + ~ObjectIdentifier(); + + static ObjectIdentifier for_graph_root(); + static ObjectIdentifier for_real_object(Object *object); + static ObjectIdentifier for_hierarchy_context(const HierarchyContext *context); + static ObjectIdentifier for_duplicated_object(const DupliObject *dupli_object, + Object *duplicated_by); + + bool is_root() const; +}; + +bool operator<(const ObjectIdentifier &obj_ident_a, const ObjectIdentifier &obj_ident_b); +bool operator==(const ObjectIdentifier &obj_ident_a, const ObjectIdentifier &obj_ident_b); + /* AbstractHierarchyIterator iterates over objects in a dependency graph, and constructs export * writers. These writers are then called to perform the actual writing to a USD or Alembic file. * @@ -172,14 +205,10 @@ class AbstractHierarchyIterator { public: /* Mapping from export path to writer. */ typedef std::map<std::string, AbstractHierarchyWriter *> WriterMap; - /* Pair of a (potentially duplicated) object and its duplicator (or nullptr). - * This is typically used to store a pair of HierarchyContext::object and - * HierarchyContext::duplicator. */ - typedef std::pair<Object *, Object *> DupliAndDuplicator; /* All the children of some object, as per the export hierarchy. */ typedef std::set<HierarchyContext *> ExportChildren; /* Mapping from an object and its duplicator to the object's export-children. */ - typedef std::map<DupliAndDuplicator, ExportChildren> ExportGraph; + typedef std::map<ObjectIdentifier, ExportChildren> ExportGraph; /* Mapping from ID to its export path. This is used for instancing; given an * instanced datablock, the export path of the original can be looked up. */ typedef std::map<ID *, std::string> ExportPathMap; @@ -237,7 +266,7 @@ class AbstractHierarchyIterator { void visit_object(Object *object, Object *export_parent, bool weak_export); void visit_dupli_object(DupliObject *dupli_object, Object *duplicator, - const std::set<Object *> &dupli_set); + const DupliParentFinder &dupli_parent_finder); void context_update_for_graph_index(HierarchyContext *context, const ExportGraph::key_type &graph_index) const; @@ -291,8 +320,10 @@ class AbstractHierarchyIterator { virtual bool should_visit_dupli_object(const DupliObject *dupli_object) const; virtual ExportGraph::key_type determine_graph_index_object(const HierarchyContext *context); - virtual ExportGraph::key_type determine_graph_index_dupli(const HierarchyContext *context, - const std::set<Object *> &dupli_set); + virtual ExportGraph::key_type determine_graph_index_dupli( + const HierarchyContext *context, + const DupliObject *dupli_object, + const DupliParentFinder &dupli_parent_finder); /* These functions should create an AbstractHierarchyWriter subclass instance, or return * nullptr if the object or its data should not be exported. Returning a nullptr for diff --git a/source/blender/io/common/IO_dupli_persistent_id.hh b/source/blender/io/common/IO_dupli_persistent_id.hh new file mode 100644 index 00000000000..dc70c1cdf31 --- /dev/null +++ b/source/blender/io/common/IO_dupli_persistent_id.hh @@ -0,0 +1,61 @@ +/* + * 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) 2020 Blender Foundation. + * All rights reserved. + */ +#ifndef __IO_COMMON_DUPLI_PERSISTENT_ID_H__ +#define __IO_COMMON_DUPLI_PERSISTENT_ID_H__ + +#include "BKE_duplilist.h" + +#include "DNA_object_types.h" /* For MAX_DUPLI_RECUR */ + +#include <array> +#include <optional> +#include <ostream> + +namespace blender::io { + +/* Wrapper for DupliObject::persistent_id that can act as a map key. */ +class PersistentID { + protected: + constexpr static int array_length_ = MAX_DUPLI_RECUR; + typedef std::array<int, array_length_> PIDArray; + PIDArray persistent_id_; + + explicit PersistentID(const PIDArray &persistent_id_values); + + public: + PersistentID(); + explicit PersistentID(const DupliObject *dupli_ob); + + /* Return true iff the persistent IDs are the same, ignoring the first digit. */ + bool is_from_same_instancer_as(const PersistentID &other) const; + + /* Construct the persistent ID of this instance's instancer. */ + PersistentID instancer_pid() const; + + friend bool operator==(const PersistentID &persistent_id_a, const PersistentID &persistent_id_b); + friend bool operator<(const PersistentID &persistent_id_a, const PersistentID &persistent_id_b); + friend std::ostream &operator<<(std::ostream &os, const PersistentID &persistent_id); + + private: + void copy_values_from(const PIDArray &persistent_id_values); +}; + +} // namespace blender::io + +#endif // __IO_COMMON_DUPLI_PARENT_FINDER_H__ diff --git a/source/blender/io/common/intern/abstract_hierarchy_iterator.cc b/source/blender/io/common/intern/abstract_hierarchy_iterator.cc index 1d67792053a..c8d916c0950 100644 --- a/source/blender/io/common/intern/abstract_hierarchy_iterator.cc +++ b/source/blender/io/common/intern/abstract_hierarchy_iterator.cc @@ -17,6 +17,7 @@ * All rights reserved. */ #include "IO_abstract_hierarchy_iterator.h" +#include "dupli_parent_finder.hh" #include <iostream> #include <limits.h> @@ -200,9 +201,9 @@ void AbstractHierarchyIterator::debug_print_export_graph(const ExportGraph &grap { size_t total_graph_size = 0; for (const ExportGraph::value_type &map_iter : graph) { - const DupliAndDuplicator &parent_info = map_iter.first; - Object *const export_parent = parent_info.first; - Object *const duplicator = parent_info.second; + const ObjectIdentifier &parent_info = map_iter.first; + const Object *const export_parent = parent_info.object; + const Object *const duplicator = parent_info.duplicated_by; if (duplicator != nullptr) { printf(" DU %s (as dupped by %s):\n", @@ -257,22 +258,21 @@ void AbstractHierarchyIterator::export_graph_construct() // Export the duplicated objects instanced by this object. ListBase *lb = object_duplilist(depsgraph_, scene, object); if (lb) { - // Construct the set of duplicated objects, so that later we can determine whether a parent - // is also duplicated itself. - std::set<Object *> dupli_set; + DupliParentFinder dupli_parent_finder; + LISTBASE_FOREACH (DupliObject *, dupli_object, lb) { + PersistentID persistent_id(dupli_object); if (!should_visit_dupli_object(dupli_object)) { continue; } - dupli_set.insert(dupli_object->ob); + dupli_parent_finder.insert(dupli_object); } LISTBASE_FOREACH (DupliObject *, dupli_object, lb) { if (!should_visit_dupli_object(dupli_object)) { continue; } - - visit_dupli_object(dupli_object, object, dupli_set); + visit_dupli_object(dupli_object, object, dupli_parent_finder); } } @@ -291,29 +291,30 @@ void AbstractHierarchyIterator::connect_loose_objects() for (const ExportGraph::value_type &map_iter : export_graph_) { for (const HierarchyContext *child : map_iter.second) { // An object that is marked as a child of another object is not considered 'loose'. - loose_objects_graph.erase(std::make_pair(child->object, child->duplicator)); + ObjectIdentifier child_oid = ObjectIdentifier::for_hierarchy_context(child); + loose_objects_graph.erase(child_oid); } } // The root of the hierarchy is always found, so it's never considered 'loose'. - loose_objects_graph.erase(std::make_pair(nullptr, nullptr)); + loose_objects_graph.erase(ObjectIdentifier::for_graph_root()); // Iterate over the loose objects and connect them to their export parent. for (const ExportGraph::value_type &map_iter : loose_objects_graph) { - const DupliAndDuplicator &export_info = map_iter.first; - Object *object = export_info.first; + const ObjectIdentifier &graph_key = map_iter.first; + Object *object = graph_key.object; while (true) { // Loose objects will all be real objects, as duplicated objects always have // their duplicator or other exported duplicated object as ancestor. ExportGraph::iterator found_parent_iter = export_graph_.find( - std::make_pair(object->parent, nullptr)); + ObjectIdentifier::for_real_object(object->parent)); visit_object(object, object->parent, true); if (found_parent_iter != export_graph_.end()) { break; } // 'object->parent' will never be nullptr here, as the export graph contains the - // tuple <nullptr, nullptr> as root and thus will cause a break. + // root as nullptr and thus will cause a break above. BLI_assert(object->parent != nullptr); object = object->parent; @@ -326,10 +327,8 @@ static bool remove_weak_subtrees(const HierarchyContext *context, const AbstractHierarchyIterator::ExportGraph &input_graph) { bool all_is_weak = context != nullptr && context->weak_export; - Object *object = context != nullptr ? context->object : nullptr; - Object *duplicator = context != nullptr ? context->duplicator : nullptr; + const ObjectIdentifier map_key = ObjectIdentifier::for_hierarchy_context(context); - const AbstractHierarchyIterator::DupliAndDuplicator map_key = std::make_pair(object, duplicator); AbstractHierarchyIterator::ExportGraph::const_iterator child_iterator; child_iterator = input_graph.find(map_key); @@ -399,7 +398,7 @@ void AbstractHierarchyIterator::visit_object(Object *object, // check on whether an object is part of the export, rather than having to check all objects in // the map. Note that it's not possible to simply search for (object->parent, nullptr), as the // object's parent in Blender may not be the same as its export-parent. - ExportGraph::key_type object_key = std::make_pair(object, nullptr); + ExportGraph::key_type object_key = ObjectIdentifier::for_real_object(object); if (export_graph_.find(object_key) == export_graph_.end()) { export_graph_[object_key] = ExportChildren(); } @@ -408,16 +407,17 @@ void AbstractHierarchyIterator::visit_object(Object *object, AbstractHierarchyIterator::ExportGraph::key_type AbstractHierarchyIterator:: determine_graph_index_object(const HierarchyContext *context) { - return std::make_pair(context->export_parent, nullptr); + return ObjectIdentifier::for_real_object(context->export_parent); } void AbstractHierarchyIterator::visit_dupli_object(DupliObject *dupli_object, Object *duplicator, - const std::set<Object *> &dupli_set) + const DupliParentFinder &dupli_parent_finder) { HierarchyContext *context = new HierarchyContext(); context->object = dupli_object->ob; context->duplicator = duplicator; + context->persistent_id = PersistentID(dupli_object); context->weak_export = false; context->export_path = ""; context->original_export_path = ""; @@ -429,36 +429,34 @@ void AbstractHierarchyIterator::visit_dupli_object(DupliObject *dupli_object, // Construct export name for the dupli-instance. std::stringstream suffix_stream; suffix_stream << std::hex; - for (int i = 0; i < MAX_DUPLI_RECUR && dupli_object->persistent_id[i] != INT_MAX; i++) { - suffix_stream << "-" << dupli_object->persistent_id[i]; - } + suffix_stream << "-" << context->persistent_id; context->export_name = make_valid_name(get_object_name(context->object) + suffix_stream.str()); - ExportGraph::key_type graph_index = determine_graph_index_dupli(context, dupli_set); + ExportGraph::key_type graph_index = determine_graph_index_dupli( + context, dupli_object, dupli_parent_finder); context_update_for_graph_index(context, graph_index); + export_graph_[graph_index].insert(context); } AbstractHierarchyIterator::ExportGraph::key_type AbstractHierarchyIterator:: determine_graph_index_dupli(const HierarchyContext *context, - const std::set<Object *> &dupli_set) + const DupliObject *dupli_object, + const DupliParentFinder &dupli_parent_finder) { - /* If the dupli-object's parent is also instanced by this object, use that as the - * export parent. Otherwise use the dupli-parent as export parent. */ + const DupliObject *dupli_parent = dupli_parent_finder.find_suitable_export_parent(dupli_object); - Object *parent = context->object->parent; - if (parent != nullptr && dupli_set.find(parent) != dupli_set.end()) { - // The parent object is part of the duplicated collection. - return std::make_pair(parent, context->duplicator); + if (dupli_parent != nullptr) { + return ObjectIdentifier::for_duplicated_object(dupli_parent, context->duplicator); } - return std::make_pair(context->duplicator, nullptr); + return ObjectIdentifier::for_real_object(context->duplicator); } void AbstractHierarchyIterator::context_update_for_graph_index( HierarchyContext *context, const ExportGraph::key_type &graph_index) const { // Update the HierarchyContext so that it is consistent with the graph index. - context->export_parent = graph_index.first; + context->export_parent = graph_index.object; if (context->export_parent != context->object->parent) { /* The parent object in Blender is NOT used as the export parent. This means * that the world transform of this object can be influenced by objects that @@ -470,11 +468,7 @@ void AbstractHierarchyIterator::context_update_for_graph_index( AbstractHierarchyIterator::ExportChildren &AbstractHierarchyIterator::graph_children( const HierarchyContext *context) { - if (context == nullptr) { - return export_graph_[std::make_pair(nullptr, nullptr)]; - } - - return export_graph_[std::make_pair(context->object, context->duplicator)]; + return export_graph_[ObjectIdentifier::for_hierarchy_context(context)]; } void AbstractHierarchyIterator::determine_export_paths(const HierarchyContext *parent_context) diff --git a/source/blender/io/common/intern/dupli_parent_finder.cc b/source/blender/io/common/intern/dupli_parent_finder.cc new file mode 100644 index 00000000000..73e33eff164 --- /dev/null +++ b/source/blender/io/common/intern/dupli_parent_finder.cc @@ -0,0 +1,104 @@ +/* + * 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) 2020 Blender Foundation. + * All rights reserved. + */ + +#include "dupli_parent_finder.hh" + +#include "BLI_utildefines.h" + +#include <iostream> + +namespace blender::io { + +DupliParentFinder::DupliParentFinder() +{ +} + +DupliParentFinder::~DupliParentFinder() +{ +} + +void DupliParentFinder::insert(const DupliObject *dupli_ob) +{ + dupli_set_.insert(dupli_ob->ob); + + PersistentID dupli_pid(dupli_ob); + pid_to_dupli_[dupli_pid] = dupli_ob; + instancer_pid_to_duplis_[dupli_pid.instancer_pid()].insert(dupli_ob); +} + +bool DupliParentFinder::is_duplicated(const Object *object) const +{ + return dupli_set_.find(object) != dupli_set_.end(); +} + +const DupliObject *DupliParentFinder::find_suitable_export_parent( + const DupliObject *dupli_ob) const +{ + if (dupli_ob->ob->parent != nullptr) { + const DupliObject *parent = find_duplicated_parent(dupli_ob); + if (parent != nullptr) { + return parent; + } + } + + return find_instancer(dupli_ob); +} + +const DupliObject *DupliParentFinder::find_duplicated_parent(const DupliObject *dupli_ob) const +{ + const PersistentID dupli_pid(dupli_ob); + PersistentID parent_pid = dupli_pid.instancer_pid(); + + const Object *parent_ob = dupli_ob->ob->parent; + BLI_assert(parent_ob != nullptr); + + InstancerPIDToDuplisMap::const_iterator found = instancer_pid_to_duplis_.find(parent_pid); + if (found == instancer_pid_to_duplis_.end()) { + /* Unexpected, as there should be at least one entry here, for the dupli_ob itself. */ + return nullptr; + } + + for (const DupliObject *potential_parent_dupli : found->second) { + if (potential_parent_dupli->ob != parent_ob) { + continue; + } + + PersistentID potential_parent_pid(potential_parent_dupli); + if (potential_parent_pid.is_from_same_instancer_as(dupli_pid)) { + return potential_parent_dupli; + } + } + return nullptr; +} + +const DupliObject *DupliParentFinder::find_instancer(const DupliObject *dupli_ob) const +{ + PersistentID dupli_pid(dupli_ob); + PersistentID parent_pid = dupli_pid.instancer_pid(); + + PIDToDupliMap::const_iterator found = pid_to_dupli_.find(parent_pid); + if (found == pid_to_dupli_.end()) { + return nullptr; + } + + const DupliObject *instancer_dupli = found->second; + return instancer_dupli; +} + +} // namespace blender::io diff --git a/source/blender/io/common/intern/dupli_parent_finder.hh b/source/blender/io/common/intern/dupli_parent_finder.hh new file mode 100644 index 00000000000..e7e628665ee --- /dev/null +++ b/source/blender/io/common/intern/dupli_parent_finder.hh @@ -0,0 +1,62 @@ +/* + * 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) 2020 Blender Foundation. + * All rights reserved. + */ +#ifndef __IO_COMMON_DUPLI_PARENT_FINDER_H__ +#define __IO_COMMON_DUPLI_PARENT_FINDER_H__ + +#include "IO_dupli_persistent_id.hh" + +#include "BKE_duplilist.h" + +#include <map> +#include <set> + +namespace blender::io { + +/* Find relations between duplicated objects. This class should be instanced for a single real + * object, and fed its dupli-objects. */ +class DupliParentFinder final { + private: + /* To check whether an Object * is instanced by this duplicator. */ + std::set<const Object *> dupli_set_; + + /* To find the DupliObject given its Persistent ID. */ + typedef std::map<const PersistentID, const DupliObject *> PIDToDupliMap; + PIDToDupliMap pid_to_dupli_; + + /* Mapping from instancer PID to duplis instanced by it. */ + typedef std::map<const PersistentID, std::set<const DupliObject *>> InstancerPIDToDuplisMap; + InstancerPIDToDuplisMap instancer_pid_to_duplis_; + + public: + DupliParentFinder(); + ~DupliParentFinder(); + + void insert(const DupliObject *dupli_ob); + + bool is_duplicated(const Object *object) const; + const DupliObject *find_suitable_export_parent(const DupliObject *dupli_ob) const; + + private: + const DupliObject *find_duplicated_parent(const DupliObject *dupli_ob) const; + const DupliObject *find_instancer(const DupliObject *dupli_ob) const; +}; + +} // namespace blender::io + +#endif
\ No newline at end of file diff --git a/source/blender/io/common/intern/dupli_persistent_id.cc b/source/blender/io/common/intern/dupli_persistent_id.cc new file mode 100644 index 00000000000..8563fd5cea6 --- /dev/null +++ b/source/blender/io/common/intern/dupli_persistent_id.cc @@ -0,0 +1,144 @@ +/* + * 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) 2020 Blender Foundation. + * All rights reserved. + */ + +#include "dupli_parent_finder.hh" + +#include <climits> +#include <cstring> +#include <ostream> + +namespace blender::io { + +PersistentID::PersistentID() +{ + persistent_id_[0] = INT_MAX; +} + +PersistentID::PersistentID(const DupliObject *dupli_ob) +{ + for (int index = 0; index < array_length_; ++index) { + persistent_id_[index] = dupli_ob->persistent_id[index]; + } +} + +PersistentID::PersistentID(const PIDArray &persistent_id_values) +{ + persistent_id_ = persistent_id_values; +} + +bool PersistentID::is_from_same_instancer_as(const PersistentID &other) const +{ + if (persistent_id_[0] == INT_MAX || other.persistent_id_[0] == INT_MAX) { + /* Either one or the other is not instanced at all, so definitely not from the same instancer. + */ + return false; + } + + /* Start at index 1 to skip the first digit. */ + for (int index = 1; index < array_length_; ++index) { + const int pid_digit_a = persistent_id_[index]; + const int pid_digit_b = other.persistent_id_[index]; + + if (pid_digit_a != pid_digit_b) { + return false; + } + + if (pid_digit_a == INT_MAX) { + /* Both persistent IDs were identical so far, and this marks the end of the useful data. */ + break; + } + } + return true; +} + +PersistentID PersistentID::instancer_pid() const +{ + if (persistent_id_[0] == INT_MAX) { + return PersistentID(); + } + + /* Left-shift the entire PID by 1. */ + PIDArray new_pid_values; + int index; + for (index = 0; index < array_length_ - 1; ++index) { + new_pid_values[index] = persistent_id_[index + 1]; + } + new_pid_values[index] = INT_MAX; + + return PersistentID(new_pid_values); +} + +bool operator<(const PersistentID &persistent_id_a, const PersistentID &persistent_id_b) +{ + const PersistentID::PIDArray &pid_a = persistent_id_a.persistent_id_; + const PersistentID::PIDArray &pid_b = persistent_id_b.persistent_id_; + + for (int index = 0; index < PersistentID::array_length_; ++index) { + const int pid_digit_a = pid_a[index]; + const int pid_digit_b = pid_b[index]; + + if (pid_digit_a != pid_digit_b) { + return pid_digit_a < pid_digit_b; + } + + if (pid_a[index] == INT_MAX) { + break; + } + } + /* Both Persistent IDs were equal, so not less-than. */ + return false; +} + +bool operator==(const PersistentID &persistent_id_a, const PersistentID &persistent_id_b) +{ + const PersistentID::PIDArray &pid_a = persistent_id_a.persistent_id_; + const PersistentID::PIDArray &pid_b = persistent_id_b.persistent_id_; + + for (int index = 0; index < PersistentID::array_length_; ++index) { + const int pid_digit_a = pid_a[index]; + const int pid_digit_b = pid_b[index]; + + if (pid_digit_a != pid_digit_b) { + return false; + } + + if (pid_a[index] == INT_MAX) { + break; + } + } + return true; +} + +std::ostream &operator<<(std::ostream &os, const PersistentID &persistent_id) +{ + if (persistent_id.persistent_id_[0] == INT_MAX) { + return os; + } + + const PersistentID::PIDArray &pid_array = persistent_id.persistent_id_; + for (int index = 0; index < PersistentID::array_length_ && pid_array[index] < INT_MAX; ++index) { + if (index > 0) { + os << "-"; + } + os << pid_array[index]; + } + return os; +} + +} // namespace blender::io diff --git a/source/blender/io/common/intern/object_identifier.cc b/source/blender/io/common/intern/object_identifier.cc new file mode 100644 index 00000000000..696bc5d2c34 --- /dev/null +++ b/source/blender/io/common/intern/object_identifier.cc @@ -0,0 +1,116 @@ +/* + * 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 "BKE_duplilist.h" + +extern "C" { +#include <limits.h> /* For INT_MAX. */ +} +#include <cstring> +#include <sstream> + +namespace blender { +namespace io { + +ObjectIdentifier::ObjectIdentifier(Object *object, + Object *duplicated_by, + const PersistentID &persistent_id) + : object(object), duplicated_by(duplicated_by), persistent_id(persistent_id) +{ +} + +ObjectIdentifier::ObjectIdentifier(const ObjectIdentifier &other) + : object(other.object), duplicated_by(other.duplicated_by), persistent_id(other.persistent_id) +{ +} + +ObjectIdentifier::~ObjectIdentifier() +{ +} + +ObjectIdentifier ObjectIdentifier::for_real_object(Object *object) +{ + return ObjectIdentifier(object, nullptr, PersistentID()); +} + +ObjectIdentifier ObjectIdentifier::for_hierarchy_context(const HierarchyContext *context) +{ + if (context == nullptr) { + return for_graph_root(); + } + if (context->duplicator != nullptr) { + return ObjectIdentifier(context->object, context->duplicator, context->persistent_id); + } + return for_real_object(context->object); +} + +ObjectIdentifier ObjectIdentifier::for_duplicated_object(const DupliObject *dupli_object, + Object *duplicated_by) +{ + return ObjectIdentifier(dupli_object->ob, duplicated_by, PersistentID(dupli_object)); +} + +ObjectIdentifier ObjectIdentifier::for_graph_root() +{ + return ObjectIdentifier(nullptr, nullptr, PersistentID()); +} + +bool ObjectIdentifier::is_root() const +{ + return object == nullptr; +} + +bool operator<(const ObjectIdentifier &obj_ident_a, const ObjectIdentifier &obj_ident_b) +{ + if (obj_ident_a.object != obj_ident_b.object) { + return obj_ident_a.object < obj_ident_b.object; + } + + if (obj_ident_a.duplicated_by != obj_ident_b.duplicated_by) { + return obj_ident_a.duplicated_by < obj_ident_b.duplicated_by; + } + + if (obj_ident_a.duplicated_by == nullptr) { + /* Both are real objects, no need to check the persistent ID. */ + return false; + } + + /* Same object, both are duplicated, use the persistent IDs to determine order. */ + return obj_ident_a.persistent_id < obj_ident_b.persistent_id; +} + +bool operator==(const ObjectIdentifier &obj_ident_a, const ObjectIdentifier &obj_ident_b) +{ + if (obj_ident_a.object != obj_ident_b.object) { + return false; + } + if (obj_ident_a.duplicated_by != obj_ident_b.duplicated_by) { + return false; + } + if (obj_ident_a.duplicated_by == nullptr) { + return true; + } + + /* Same object, both are duplicated, use the persistent IDs to determine equality. */ + return obj_ident_a.persistent_id == obj_ident_b.persistent_id; +} + +} // namespace io +} // namespace blender 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 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 |