diff options
Diffstat (limited to 'source/blender/io/common/intern')
5 files changed, 488 insertions, 45 deletions
diff --git a/source/blender/io/common/intern/abstract_hierarchy_iterator.cc b/source/blender/io/common/intern/abstract_hierarchy_iterator.cc index dce6b8e178b..3622c1eb7cd 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", @@ -217,7 +218,7 @@ void AbstractHierarchyIterator::debug_print_export_graph(const ExportGraph &grap for (HierarchyContext *child_ctx : map_iter.second) { if (child_ctx->duplicator == nullptr) { printf(" - %s%s%s\n", - child_ctx->object->id.name + 2, + child_ctx->export_name.c_str(), child_ctx->weak_export ? " (weak)" : "", child_ctx->original_export_path.empty() ? "" : @@ -225,7 +226,7 @@ void AbstractHierarchyIterator::debug_print_export_graph(const ExportGraph &grap } else { printf(" - %s (dup by %s%s) %s\n", - child_ctx->object->id.name + 2, + child_ctx->export_name.c_str(), child_ctx->duplicator->id.name + 2, child_ctx->weak_export ? ", weak" : "", child_ctx->original_export_path.empty() ? @@ -234,7 +235,7 @@ void AbstractHierarchyIterator::debug_print_export_graph(const ExportGraph &grap } } } - printf(" (Total graph size: %zu objects\n", total_graph_size); + printf(" (Total graph size: %zu objects)\n", total_graph_size); } void AbstractHierarchyIterator::export_graph_construct() @@ -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 = ""; @@ -427,38 +427,36 @@ void AbstractHierarchyIterator::visit_dupli_object(DupliObject *dupli_object, copy_m4_m4(context->matrix_world, dupli_object->mat); // 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]; - } - context->export_name = make_valid_name(get_object_name(context->object) + suffix_stream.str()); + std::stringstream export_name_stream; + export_name_stream << get_object_name(context->object) << "-" + << context->persistent_id.as_object_name_suffix(); + context->export_name = make_valid_name(export_name_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..b40cd83ef44 --- /dev/null +++ b/source/blender/io/common/intern/dupli_persistent_id.cc @@ -0,0 +1,167 @@ +/* + * 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> +#include <sstream> + +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); +} + +std::string PersistentID::as_object_name_suffix() const +{ + std::stringstream stream; + + /* Find one past the last index. */ + int index; + for (index = 0; index < array_length_ && persistent_id_[index] < INT_MAX; ++index) { + ; + } + + /* Iterate backward to construct the string. */ + --index; + for (; index >= 0; --index) { + stream << persistent_id_[index]; + if (index > 0) { + stream << "-"; + } + } + + return stream.str(); +} + +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 |