dali-scene3d/public-api/loader/scene-definition.cpp

   1 /*
   2  * Copyright (c) 2022 Samsung Electronics Co., Ltd.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  * http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  *
  16  */
  17
  18 // EXTERNAL
  19 #include "dali/devel-api/common/map-wrapper.h"
  20 #include "dali/public-api/animation/constraints.h"
  21
  22 // INTERNAL
  23 #include "dali-scene3d/internal/graphics/builtin-shader-extern-gen.h"
  24 #include "dali-scene3d/public-api/loader/blend-shape-details.h"
  25 #include "dali-scene3d/public-api/loader/scene-definition.h"
  26 #include "dali-scene3d/public-api/loader/skinning-details.h"
  27 #include "dali-scene3d/public-api/loader/utils.h"
  28
  29 //#define DEBUG_SCENE_DEFINITION
  30 //#define DEBUG_JOINTS
  31
  32 #if defined(DEBUG_SCENE_DEFINITION) || defined(DEBUG_JOINTS)
  33 #define DEBUG_ONLY(x) x
  34 #else
  35 #define DEBUG_ONLY(x)
  36 #endif
  37
  38 #define LOGD(x) DEBUG_ONLY(printf x; printf("\n"); fflush(stdout))
  39
  40 namespace Dali
  41 {
  42 namespace Scene3D
  43 {
  44 namespace Loader
  45 {
  46 namespace
  47 {
  48 const char* JOINT_MATRIX{"jointMatrix"};
  49
  50 const std::map<Property::Type, Constraint (*)(Actor&, Property::Index)> sConstraintFactory = {
  51   {Property::Type::BOOLEAN,
  52    [](Actor& a, Property::Index i) {
  53      return Constraint::New<bool>(a, i, [](bool& current, const PropertyInputContainer& inputs) {
  54        current = inputs[0]->GetBoolean();
  55      });
  56    }},
  57   {Property::Type::INTEGER,
  58    [](Actor& a, Property::Index i) {
  59      return Constraint::New<int>(a, i, [](int& current, const PropertyInputContainer& inputs) {
  60        current = inputs[0]->GetInteger();
  61      });
  62    }},
  63   {Property::Type::FLOAT,
  64    [](Actor& a, Property::Index i) {
  65      return Constraint::New<float>(a, i, EqualToConstraint());
  66    }},
  67   {Property::Type::VECTOR2,
  68    [](Actor& a, Property::Index i) {
  69      return Constraint::New<Vector2>(a, i, EqualToConstraint());
  70    }},
  71   {Property::Type::VECTOR3,
  72    [](Actor& a, Property::Index i) {
  73      return Constraint::New<Vector3>(a, i, EqualToConstraint());
  74    }},
  75   {Property::Type::VECTOR4,
  76    [](Actor& a, Property::Index i) {
  77      return Constraint::New<Vector4>(a, i, EqualToConstraint());
  78    }},
  79   {Property::Type::MATRIX,
  80    [](Actor& a, Property::Index i) {
  81      return Constraint::New<Matrix>(a, i, EqualToConstraint());
  82    }},
  83   {Property::Type::MATRIX3,
  84    [](Actor& a, Property::Index i) {
  85      return Constraint::New<Matrix3>(a, i, EqualToConstraint());
  86    }},
  87   {Property::Type::ROTATION,
  88    [](Actor& a, Property::Index i) {
  89      return Constraint::New<Quaternion>(a, i, EqualToConstraint());
  90    }},
  91 };
  92
  93 struct ResourceReflector : IResourceReflector
  94 {
  95   Index* iMesh   = nullptr;
  96   Index* iShader = nullptr;
  97
  98   void Reflect(ResourceType::Value type, Index& id)
  99   {
 100     switch(type)
 101     {
 102       case ResourceType::Shader:
 103         DALI_ASSERT_ALWAYS(!iShader && "Shader index already assigned!");
 104         iShader = &id;
 105         break;
 106
 107       case ResourceType::Mesh:
 108         DALI_ASSERT_ALWAYS(!iMesh && "Mesh index already assigned!");
 109         iMesh = &id;
 110         break;
 111
 112       default: // Other resource types are not relevant to the problem at hand.
 113         break;
 114     }
 115   }
 116 };
 117
 118 #ifdef DEBUG_JOINTS
 119
 120 Shader sJointDebugShader;
 121 int    sNumScenes = 0;
 122
 123 void EnsureJointDebugShaderCreated()
 124 {
 125   if(0 == sNumScenes)
 126   {
 127     sJointDebugShader = Shader::New(SHADER_SCENE3D_JOINT_DEBUG_VERT, SHADER_SCENE3D_JOINT_DEBUG_FRAG);
 128   }
 129   ++sNumScenes;
 130 }
 131
 132 void AddJointDebugVisual(Actor aJoint)
 133 {
 134   Property::Map attribs;
 135   attribs["aPosition"] = Property::Type::VECTOR3;
 136   attribs["aColor"]    = Property::Type::FLOAT;
 137
 138   PropertyBuffer vbo = PropertyBuffer::New(attribs);
 139
 140   struct Vertex
 141   {
 142     Vector3 pos;
 143     float   color;
 144   } vertices[] = {
 145     {Vector3::ZERO, .999f + .999f * 256.f + .999f * 256.f * 256.f},
 146     {Vector3::XAXIS, .999f},
 147     {Vector3::YAXIS, .999f * 256.f},
 148     {Vector3::ZAXIS, .999f * 256.f * 256.f},
 149   };
 150
 151   vbo.SetData(&vertices, std::extent<decltype(vertices)>::value);
 152
 153   uint16_t indices[] = {0, 1, 0, 2, 0, 3};
 154
 155   Geometry geo = Geometry::New();
 156   geo.AddVertexBuffer(vbo);
 157   geo.SetIndexBuffer(indices, std::extent<decltype(indices)>::value);
 158   geo.SetType(Geometry::LINES);
 159
 160   Renderer r = Renderer::New(geo, sJointDebugShader);
 161   aJoint.AddRenderer(r);
 162
 163   aJoint.SetVisible(true);
 164 }
 165 #endif //DEBUG_JOINTS
 166
 167 class ActorCreatorVisitor : public NodeDefinition::IVisitor
 168 {
 169 public:
 170   ActorCreatorVisitor(NodeDefinition::CreateParams& params)
 171   : mCreationContext(params)
 172   {
 173   }
 174
 175   void Start(NodeDefinition& n)
 176   {
 177     mCreationContext.mXforms.modelStack.Push(n.GetLocalSpace());
 178
 179     Actor a = n.CreateActor(mCreationContext);
 180     if(!mActorStack.empty())
 181     {
 182       mActorStack.back().Add(a);
 183     }
 184     else
 185     {
 186       mRoot = a;
 187     }
 188     mActorStack.push_back(a);
 189   }
 190
 191   void Finish(NodeDefinition& n)
 192   {
 193     mActorStack.pop_back();
 194     mCreationContext.mXforms.modelStack.Pop();
 195   }
 196
 197   Actor GetRoot() const
 198   {
 199     return mRoot;
 200   }
 201
 202 private:
 203   NodeDefinition::CreateParams& mCreationContext;
 204   std::vector<Actor>            mActorStack;
 205   Actor                         mRoot;
 206 };
 207
 208 bool IsAncestor(const SceneDefinition& scene, Index ancestor, Index node, Index rootHint = INVALID_INDEX)
 209 {
 210   bool isAncestor = false;
 211   while(node != rootHint && !isAncestor)
 212   {
 213     node       = scene.GetNode(node)->mParentIdx;
 214     isAncestor = ancestor == node;
 215   }
 216   return isAncestor;
 217 }
 218
 219 void InsertUniqueSorted(std::vector<Index>& data, Index value)
 220 {
 221   auto iInsert = std::lower_bound(data.begin(), data.end(), value);
 222   if(iInsert == data.end() || *iInsert != value)
 223   {
 224     data.insert(iInsert, value);
 225   }
 226 }
 227
 228 void RemoveFromSorted(std::vector<Index>& data, Index value)
 229 {
 230   auto iRemove = std::lower_bound(data.begin(), data.end(), value);
 231   if(iRemove != data.end() && *iRemove == value)
 232   {
 233     data.erase(iRemove);
 234   }
 235 }
 236
 237 Property::Index ConfigureJointMatrix(Actor actor, Actor ancestor, Property::Index propJointMatrix)
 238 {
 239   Actor parent = actor.GetParent();
 240   if(parent != ancestor)
 241   {
 242     propJointMatrix = ConfigureJointMatrix(parent, ancestor, propJointMatrix);
 243   }
 244
 245   auto myPropJointMatrix = actor.GetPropertyIndex(JOINT_MATRIX);
 246   if(myPropJointMatrix == Property::INVALID_INDEX)
 247   {
 248     myPropJointMatrix     = actor.RegisterProperty(JOINT_MATRIX, Matrix{false});
 249     Constraint constraint = Constraint::New<Matrix>(actor, propJointMatrix, [](Matrix& output, const PropertyInputContainer& inputs) {
 250       Matrix jointMatrix{false};
 251       jointMatrix.SetTransformComponents(Vector3::ONE, inputs[0]->GetQuaternion(), inputs[1]->GetVector3());
 252
 253       Matrix::Multiply(output, jointMatrix, inputs[2]->GetMatrix());
 254     });
 255     constraint.AddSource(Source{actor, Actor::Property::ORIENTATION});
 256     constraint.AddSource(Source{actor, Actor::Property::POSITION});
 257     constraint.AddSource(Source{parent, propJointMatrix});
 258     constraint.Apply();
 259   }
 260
 261   return myPropJointMatrix;
 262 }
 263
 264 void SortAndDeduplicateSkinningRequests(std::vector<SkinningShaderConfigurationRequest>& requests)
 265 {
 266   // Sort requests by shaders.
 267   std::sort(requests.begin(), requests.end());
 268
 269   // Remove duplicates.
 270   auto   i           = requests.begin();
 271   auto   iEnd        = requests.end();
 272   Shader s           = i->mShader;
 273   Index  skeletonIdx = i->mSkeletonIdx;
 274   ++i;
 275   do
 276   {
 277     // Multiple identical shader instances are removed.
 278     while(i != iEnd && i->mShader == s)
 279     {
 280       // Cannot have multiple skeletons input to the same shader.
 281       // NOTE: DliModel now makes sure this doesn't happen.
 282       DALI_ASSERT_ALWAYS(i->mSkeletonIdx == skeletonIdx &&
 283                          "Skinning shader must not be shared between different skeletons.");
 284
 285       i->mShader = Shader();
 286       ++i;
 287     }
 288
 289     if(i == iEnd)
 290     {
 291       break;
 292     }
 293     s           = i->mShader;
 294     skeletonIdx = i->mSkeletonIdx;
 295     ++i;
 296   } while(true);
 297
 298   requests.erase(std::remove_if(requests.begin(), requests.end(), [](const SkinningShaderConfigurationRequest& sscr) {
 299                    return !sscr.mShader;
 300                  }),
 301                  requests.end());
 302 }
 303
 304 void ConfigureBoneMatrix(const Matrix& ibm, Actor joint, Shader& shader, Index& boneIdx)
 305 {
 306   // Register bone transform on shader.
 307   char propertyNameBuffer[32];
 308   snprintf(propertyNameBuffer, sizeof(propertyNameBuffer), "%s[%d]", Skinning::BONE_UNIFORM_NAME, boneIdx);
 309   DALI_ASSERT_DEBUG(shader.GetPropertyIndex(propertyNameBuffer) == Property::INVALID_INDEX);
 310   auto propBoneXform = shader.RegisterProperty(propertyNameBuffer, Matrix{false});
 311
 312   // Constrain bone matrix to joint transform.
 313   Constraint constraint = Constraint::New<Matrix>(shader, propBoneXform, [ibm](Matrix& output, const PropertyInputContainer& inputs) {
 314     Matrix::Multiply(output, ibm, inputs[0]->GetMatrix());
 315   });
 316
 317   auto propJointMatrix = joint.GetPropertyIndex(JOINT_MATRIX);
 318   constraint.AddSource(Source{joint, propJointMatrix});
 319   constraint.Apply();
 320
 321   ++boneIdx;
 322 }
 323
 324 template<class Visitor, class SceneDefinition>
 325 void VisitInternal(Index iNode, const Customization::Choices& choices, Visitor& v, SceneDefinition& sd)
 326 {
 327   auto& node = *sd.GetNode(iNode);
 328   v.Start(node);
 329
 330   if(node.mCustomization)
 331   {
 332     if(!node.mChildren.empty())
 333     {
 334       auto  choice = choices.Get(node.mCustomization->mTag);
 335       Index i      = std::min(choice != Customization::NONE ? choice : 0, static_cast<Index>(node.mChildren.size() - 1));
 336       sd.Visit(node.mChildren[i], choices, v);
 337     }
 338   }
 339   else
 340   {
 341     for(auto i : node.mChildren)
 342     {
 343       sd.Visit(i, choices, v);
 344     }
 345   }
 346
 347   v.Finish(node);
 348 }
 349
 350 } // namespace
 351
 352 SceneDefinition::SceneDefinition()
 353 {
 354   mNodes.reserve(128);
 355
 356 #ifdef DEBUG_JOINTS
 357   EnsureJointDebugShaderCreated();
 358 #endif
 359 }
 360
 361 SceneDefinition::SceneDefinition(SceneDefinition&& other)
 362 : mNodes(std::move(other.mNodes)),
 363   mRootNodeIds(std::move(other.mRootNodeIds))
 364 {
 365 #ifdef DEBUG_JOINTS
 366   EnsureJointDebugShaderCreated();
 367 #endif
 368 }
 369
 370 SceneDefinition::~SceneDefinition()
 371 {
 372 #ifdef DEBUG_JOINTS
 373   --sNumScenes;
 374   if(sNumScenes == 0)
 375   {
 376     sJointDebugShader = Shader();
 377   }
 378 #endif
 379 }
 380
 381 uint32_t Dali::Scene3D::Loader::SceneDefinition::AddRootNode(Index iNode)
 382 {
 383   if(iNode < mNodes.size())
 384   {
 385     uint32_t result = mRootNodeIds.size();
 386     mRootNodeIds.push_back(iNode);
 387     return result;
 388   }
 389   else
 390   {
 391     ExceptionFlinger(ASSERT_LOCATION) << "Failed to add new root with node " << iNode << " -- index out of bounds.";
 392     return -1;
 393   }
 394 }
 395
 396 const std::vector<Index>& SceneDefinition::GetRoots() const
 397 {
 398   return mRootNodeIds;
 399 }
 400
 401 void SceneDefinition::RemoveRootNode(Index iRoot)
 402 {
 403   if(iRoot < mRootNodeIds.size())
 404   {
 405     mRootNodeIds.erase(mRootNodeIds.begin() + iRoot);
 406   }
 407   else
 408   {
 409     ExceptionFlinger(ASSERT_LOCATION) << "Failed to remove root " << iRoot << " -- index out of bounds.";
 410   }
 411 }
 412
 413 uint32_t SceneDefinition::GetNodeCount() const
 414 {
 415   return mNodes.size();
 416 }
 417
 418 const NodeDefinition* SceneDefinition::GetNode(Index iNode) const
 419 {
 420   return mNodes[iNode].get();
 421 }
 422
 423 NodeDefinition* SceneDefinition::GetNode(Index iNode)
 424 {
 425   if(iNode != Scene3D::Loader::INVALID_INDEX && iNode < mNodes.size())
 426   {
 427     return mNodes[iNode].get();
 428   }
 429   return nullptr;
 430 }
 431
 432 void SceneDefinition::Visit(Index iNode, const Customization::Choices& choices, NodeDefinition::IVisitor& v)
 433 {
 434   VisitInternal(iNode, choices, v, *this);
 435 }
 436
 437 void SceneDefinition::Visit(Index iNode, const Customization::Choices& choices, NodeDefinition::IConstVisitor& v) const
 438 {
 439   VisitInternal(iNode, choices, v, *this);
 440 }
 441
 442 void SceneDefinition::CountResourceRefs(Index iNode, const Customization::Choices& choices, ResourceRefCounts& refCounts) const
 443 {
 444   struct RefCounter : IResourceReceiver
 445   {
 446     ResourceRefCounts* refCounts;
 447
 448     void Register(ResourceType::Value type, Index id)
 449     {
 450       ++(*refCounts)[type][id];
 451     }
 452   };
 453
 454   struct : NodeDefinition::IConstVisitor
 455   {
 456     RefCounter counter;
 457
 458     void Start(const NodeDefinition& n)
 459     {
 460       for(auto& renderable : n.mRenderables)
 461       {
 462         renderable->RegisterResources(counter);
 463       }
 464     }
 465
 466     void Finish(const NodeDefinition& n)
 467     {
 468     }
 469
 470   } refCounterVisitor;
 471   refCounterVisitor.counter.refCounts = &refCounts;
 472
 473   Visit(iNode, choices, refCounterVisitor);
 474 }
 475
 476 Actor SceneDefinition::CreateNodes(Index iNode, const Customization::Choices& choices, NodeDefinition::CreateParams& params)
 477 {
 478   ActorCreatorVisitor actorCreatorVisitor(params);
 479
 480   Visit(iNode, choices, actorCreatorVisitor);
 481
 482   return actorCreatorVisitor.GetRoot();
 483 }
 484
 485 void SceneDefinition::GetCustomizationOptions(const Customization::Choices& choices,
 486                                               Customization::Map&           outCustomizationOptions,
 487                                               Customization::Choices*       outMissingChoices) const
 488 {
 489   struct : NodeDefinition::IConstVisitor
 490   {
 491     const Customization::Choices* choices;        // choices that we know about.
 492     Customization::Map*           options;        // tags are registered here. NO OWNERSHIP.
 493     Customization::Choices*       missingChoices; // tags will be registered with the default 0. NO OWNERSHIP.
 494
 495     void Start(const NodeDefinition& n)
 496     {
 497       if(n.mCustomization)
 498       {
 499         const std::string& tag = n.mCustomization->mTag;
 500         if(missingChoices != nullptr && choices->Get(tag) == Customization::NONE)
 501         {
 502           missingChoices->Set(tag, 0);
 503         }
 504
 505         auto customization = options->Get(tag);
 506         if(!customization)
 507         {
 508           customization = options->Set(tag, {});
 509         }
 510         customization->nodes.push_back(n.mName);
 511         customization->numOptions = std::max(customization->numOptions,
 512                                              static_cast<uint32_t>(n.mChildren.size()));
 513       }
 514     }
 515
 516     void Finish(const NodeDefinition& n)
 517     {
 518     }
 519
 520   } customizationRegistrationVisitor;
 521   customizationRegistrationVisitor.choices        = &choices;
 522   customizationRegistrationVisitor.options        = &outCustomizationOptions;
 523   customizationRegistrationVisitor.missingChoices = outMissingChoices;
 524
 525   for(auto i : mRootNodeIds)
 526   {
 527     Visit(i, choices, customizationRegistrationVisitor);
 528   }
 529 }
 530
 531 NodeDefinition* SceneDefinition::AddNode(std::unique_ptr<NodeDefinition>&& nodeDef)
 532 {
 533   // add next index (to which we're about to push) as a child to the designated parent, if any.
 534   if(nodeDef->mParentIdx != INVALID_INDEX)
 535   {
 536     mNodes[nodeDef->mParentIdx]->mChildren.push_back(mNodes.size());
 537   }
 538
 539   mNodes.push_back(std::move(nodeDef));
 540
 541   return mNodes.back().get();
 542 }
 543
 544 bool SceneDefinition::ReparentNode(const std::string& name, const std::string& newParentName, Index siblingOrder)
 545 {
 546   LOGD(("reparenting %s to %s @ %d", name.c_str(), newParentName.c_str(), siblingOrder));
 547
 548   std::unique_ptr<NodeDefinition>* nodePtr      = nullptr;
 549   std::unique_ptr<NodeDefinition>* newParentPtr = nullptr;
 550   if(!FindNode(name, &nodePtr) || !FindNode(newParentName, &newParentPtr))
 551   {
 552     return false;
 553   }
 554
 555   auto& node  = *nodePtr;
 556   auto  iNode = std::distance(mNodes.data(), nodePtr);
 557
 558   DEBUG_ONLY(auto dumpNode = [](NodeDefinition const& n) {
 559     std::ostringstream stream;
 560     stream << n.mName << " (" << n.mParentIdx << "):";
 561     for(auto i : n.mChildren)
 562     {
 563       stream << i << ", ";
 564     }
 565     LOGD(("%s", stream.str().c_str()));
 566   };)
 567
 568   // Remove node from children of previous parent (if any).
 569   if(node->mParentIdx != INVALID_INDEX)
 570   {
 571     LOGD(("old parent:"));
 572     DEBUG_ONLY(dumpNode(*mNodes[node->mParentIdx]);)
 573
 574     auto& children = mNodes[node->mParentIdx]->mChildren;
 575     children.erase(std::remove(children.begin(), children.end(), iNode), children.end());
 576
 577     DEBUG_ONLY(dumpNode(*mNodes[node->mParentIdx]);)
 578   }
 579
 580   // Register node to new parent.
 581   LOGD(("new parent:"));
 582   DEBUG_ONLY(dumpNode(**newParentPtr);)
 583   auto& children = (*newParentPtr)->mChildren;
 584   if(siblingOrder > children.size())
 585   {
 586     siblingOrder = children.size();
 587   }
 588   children.insert(children.begin() + siblingOrder, 1, iNode);
 589   DEBUG_ONLY(dumpNode(**newParentPtr);)
 590
 591   // Update parent index.
 592   LOGD(("node:"));
 593   DEBUG_ONLY(dumpNode(*node);)
 594   auto iParent     = std::distance(mNodes.data(), newParentPtr);
 595   node->mParentIdx = iParent;
 596   DEBUG_ONLY(dumpNode(*node);)
 597   return true;
 598 }
 599
 600 bool SceneDefinition::RemoveNode(const std::string& name)
 601 {
 602   std::unique_ptr<NodeDefinition>* node = nullptr;
 603   if(!FindNode(name, &node))
 604   {
 605     return false;
 606   }
 607
 608   // Reset node def pointers recursively.
 609   auto&                                                 thisNodes = mNodes;
 610   unsigned int                                          numReset  = 0;
 611   std::function<void(std::unique_ptr<NodeDefinition>&)> resetFn =
 612     [&thisNodes, &resetFn, &numReset](std::unique_ptr<NodeDefinition>& nd) {
 613       LOGD(("resetting %d", &nd - thisNodes.data()));
 614       for(auto i : nd->mChildren)
 615       {
 616         resetFn(thisNodes[i]);
 617       }
 618       nd.reset();
 619       ++numReset;
 620     };
 621
 622   resetFn(*node);
 623
 624   // Gather indices of dead nodes into a vector which we sort on insertion.
 625   std::vector<Index> offsets;
 626   offsets.reserve(numReset);
 627   for(auto& n : mNodes)
 628   {
 629     if(!n)
 630     {
 631       offsets.push_back(std::distance(mNodes.data(), &n));
 632     }
 633   }
 634
 635   // Erase dead nodes as they don't have to be processed anymore.
 636   mNodes.erase(std::remove(mNodes.begin(), mNodes.end(), decltype(mNodes)::value_type()), mNodes.end());
 637
 638   // Offset all indices (parent and child) by the index they'd sort into in offsets.
 639   enum
 640   {
 641     INDEX_FOR_REMOVAL = INVALID_INDEX
 642   };
 643   auto offsetter = [&offsets](Index& i) {
 644     auto iFind = std::lower_bound(offsets.begin(), offsets.end(), i);
 645     if(iFind != offsets.end() && *iFind == i)
 646     {
 647       LOGD(("marking %d for removal.", i));
 648       i = INDEX_FOR_REMOVAL;
 649       return false;
 650     }
 651     else
 652     {
 653       auto distance = std::distance(offsets.begin(), iFind);
 654       if(distance > 0)
 655       {
 656         LOGD(("offsetting %d by %d.", i, distance));
 657         i -= distance;
 658       }
 659       return true;
 660     }
 661   };
 662
 663   for(auto& nd : mNodes)
 664   {
 665     bool parentOffsetResult = offsetter(nd->mParentIdx);
 666     DALI_ASSERT_ALWAYS(parentOffsetResult); // since nodes were recursively removed, we should not be finding invalid parents at this point.
 667
 668     auto& children = nd->mChildren;
 669     for(auto i0 = children.begin(), i1 = children.end(); i0 != i1; ++i0)
 670     {
 671       offsetter(*i0);
 672     }
 673
 674     children.erase(std::remove(children.begin(), children.end(), INDEX_FOR_REMOVAL), children.end());
 675   }
 676
 677   return true;
 678 }
 679
 680 void SceneDefinition::GetNodeModelStack(Index index, MatrixStack& model) const
 681 {
 682   auto&                    thisNodes  = mNodes;
 683   std::function<void(int)> buildStack = [&model, &thisNodes, &buildStack](int i) {
 684     auto node = thisNodes[i].get();
 685     if(node->mParentIdx != INVALID_INDEX)
 686     {
 687       buildStack(node->mParentIdx);
 688     }
 689     model.Push(node->GetLocalSpace());
 690   };
 691   buildStack(index);
 692 }
 693
 694 NodeDefinition* SceneDefinition::FindNode(const std::string& name, Index* outIndex)
 695 {
 696   auto iBegin = mNodes.begin();
 697   auto iEnd   = mNodes.end();
 698   auto iFind  = std::find_if(iBegin, iEnd, [&name](const std::unique_ptr<NodeDefinition>& nd) {
 699     return nd->mName == name;
 700   });
 701
 702   auto result = iFind != iEnd ? iFind->get() : nullptr;
 703   if(result && outIndex)
 704   {
 705     *outIndex = std::distance(iBegin, iFind);
 706   }
 707   return result;
 708 }
 709
 710 const NodeDefinition* SceneDefinition::FindNode(const std::string& name, Index* outIndex) const
 711 {
 712   auto iBegin = mNodes.begin();
 713   auto iEnd   = mNodes.end();
 714   auto iFind  = std::find_if(iBegin, iEnd, [&name](const std::unique_ptr<NodeDefinition>& nd) {
 715     return nd->mName == name;
 716   });
 717
 718   auto result = iFind != iEnd ? iFind->get() : nullptr;
 719   if(result && outIndex)
 720   {
 721     *outIndex = std::distance(iBegin, iFind);
 722   }
 723   return result;
 724 }
 725
 726 Index SceneDefinition::FindNodeIndex(const NodeDefinition& node) const
 727 {
 728   auto iBegin = mNodes.begin();
 729   auto iEnd   = mNodes.end();
 730   auto iFind  = std::find_if(iBegin, iEnd, [&node](const std::unique_ptr<NodeDefinition>& n) {
 731     return n.get() == &node;
 732   });
 733   return iFind != iEnd ? std::distance(iBegin, iFind) : INVALID_INDEX;
 734 }
 735
 736 void SceneDefinition::FindNodes(NodePredicate predicate, NodeConsumer consumer, unsigned int limit)
 737 {
 738   unsigned int n = 0;
 739   for(auto& defp : mNodes)
 740   {
 741     if(predicate(*defp))
 742     {
 743       consumer(*defp);
 744       ++n;
 745       if(n == limit)
 746       {
 747         break;
 748       }
 749     }
 750   }
 751 }
 752
 753 void SceneDefinition::FindNodes(NodePredicate predicate, ConstNodeConsumer consumer, unsigned int limit) const
 754 {
 755   unsigned int n = 0;
 756   for(auto& defp : mNodes)
 757   {
 758     if(predicate(*defp))
 759     {
 760       consumer(*defp);
 761       ++n;
 762       if(n == limit)
 763       {
 764         break;
 765       }
 766     }
 767   }
 768 }
 769
 770 void SceneDefinition::ApplyConstraints(Actor&                           root,
 771                                        std::vector<ConstraintRequest>&& constrainables,
 772                                        StringCallback                   onError) const
 773 {
 774   for(auto& cr : constrainables)
 775   {
 776     auto&           nodeDef    = mNodes[cr.mConstraint->mSourceIdx];
 777     auto            sourceName = nodeDef->mName.c_str();
 778     Property::Index iTarget    = cr.mTarget.GetPropertyIndex(cr.mConstraint->mProperty);
 779     if(iTarget != Property::INVALID_INDEX)
 780     {
 781       auto propertyType = cr.mTarget.GetPropertyType(iTarget);
 782       auto iFind        = sConstraintFactory.find(propertyType);
 783       if(iFind == sConstraintFactory.end())
 784       {
 785         onError(FormatString("node '%s': Property '%s' has unsupported type '%s'; ignored.",
 786                              sourceName,
 787                              cr.mConstraint->mProperty.c_str(),
 788                              PropertyTypes::GetName(propertyType)));
 789         continue;
 790       }
 791
 792       Constraint constraint = iFind->second(cr.mTarget, iTarget);
 793
 794       Actor source = root.FindChildByName(nodeDef->mName);
 795       if(!source)
 796       {
 797         auto targetName = cr.mTarget.GetProperty(Actor::Property::NAME).Get<std::string>();
 798         onError(FormatString("node '%s': Failed to locate constraint source %s@%s; ignored.",
 799                              sourceName,
 800                              cr.mConstraint->mProperty.c_str(),
 801                              targetName.c_str()));
 802         continue;
 803       }
 804       else if(source == cr.mTarget)
 805       {
 806         onError(FormatString("node '%s': Cyclic constraint definition for property '%s'; ignored.",
 807                              sourceName,
 808                              cr.mConstraint->mProperty.c_str()));
 809         continue;
 810       }
 811
 812       Property::Index iSource = source.GetPropertyIndex(cr.mConstraint->mProperty);
 813       constraint.AddSource(Source{source, iSource});
 814       constraint.Apply();
 815     }
 816     else
 817     {
 818       auto targetName = cr.mTarget.GetProperty(Actor::Property::NAME).Get<std::string>();
 819       onError(FormatString("node '%s': Failed to create constraint for property %s@%s; ignored.",
 820                            sourceName,
 821                            cr.mConstraint->mProperty.c_str(),
 822                            targetName.c_str()));
 823     }
 824   }
 825 }
 826
 827 void SceneDefinition::ConfigureSkeletonJoints(uint32_t iRoot, const SkeletonDefinition::Vector& skeletons, Actor root) const
 828 {
 829   // 1, For each skeleton, for each joint, walk upwards until we reach mNodes[iRoot]. If we do, record +1
 830   // to the refcount of each node we have visited, in our temporary registry. Those with refcount 1
 831   // are the leaves, while the most descendant node with the highest refcount is the root of the skeleton.
 832   std::map<Index, std::vector<Index>> rootsJoints;
 833   std::vector<Index>                  path;
 834   path.reserve(16);
 835   for(auto& s : skeletons)
 836   {
 837     std::map<uint32_t, uint32_t> jointRefs;
 838     for(auto& j : s.mJoints)
 839     {
 840       auto nodeIdx = j.mNodeIdx;
 841       do // Traverse upwards and record each node we have visited until we reach the scene root.
 842       {
 843         path.push_back(nodeIdx);
 844         if(nodeIdx == iRoot)
 845         {
 846           break;
 847         }
 848         auto node = GetNode(nodeIdx);
 849         nodeIdx   = node->mParentIdx;
 850       } while(nodeIdx != INVALID_INDEX);
 851
 852       if(nodeIdx == iRoot) // If the joint is in the correct scene, increment the reference count for all visited nodes.
 853       {
 854         for(auto i : path)
 855         {
 856           ++jointRefs[i];
 857         }
 858       }
 859
 860       path.clear();
 861     }
 862
 863     // Only record the skeleton if we have encountered the root of the current scene.
 864     if(jointRefs.empty())
 865     {
 866       continue;
 867     }
 868
 869     Index    root   = s.mRootNodeIdx;
 870     uint32_t maxRef = 0;
 871     auto     iFind  = jointRefs.find(root);
 872     if(iFind != jointRefs.end())
 873     {
 874       maxRef = iFind->second;
 875     }
 876
 877     std::vector<Index> joints;
 878     for(auto& j : jointRefs) // NOTE: jointRefs are sorted, so joints will also be.
 879     {
 880       // The most descendant node with the highest ref count is the root of the skeleton.
 881       if(j.second > maxRef || (j.second == maxRef && IsAncestor(*this, root, j.first, iRoot)))
 882       {
 883         maxRef = j.second;
 884
 885         RemoveFromSorted(joints, root);
 886         root = j.first;
 887       }
 888       else if(j.second == 1) // This one's a leaf.
 889       {
 890         InsertUniqueSorted(joints, j.first);
 891       }
 892     }
 893
 894     // Merge skeletons that share the same root.
 895     auto& finalJoints = rootsJoints[root];
 896     for(auto j : joints)
 897     {
 898       if(std::find_if(finalJoints.begin(), finalJoints.end(), [this, j, root](Index jj) {
 899            return IsAncestor(*this, j, jj, root);
 900          }) != finalJoints.end())
 901       {
 902         continue; // if the joint is found to be an ancestor of another joint already registered, move on.
 903       }
 904
 905       auto i = j;
 906       while(i != root) // See if the current joint is a better leaf, i.e. descended from another leaf - which we'll then remove.
 907       {
 908         auto node = GetNode(i);
 909         i         = node->mParentIdx;
 910
 911         RemoveFromSorted(finalJoints, i);
 912       }
 913
 914       InsertUniqueSorted(finalJoints, j);
 915     }
 916   }
 917
 918   // 2, Merge records where one root joint is descendant of another. Handle leaf node changes - remove previous
 919   // leaf nodes that now have descendants, and add new ones.
 920   auto iRoots    = rootsJoints.begin();
 921   auto iRootsEnd = rootsJoints.end();
 922   while(iRoots != iRootsEnd)
 923   {
 924     auto i      = iRoots->first;
 925     bool merged = false;
 926     while(i != iRoot) // Starting with the root joint of the skeleton, traverse upwards.
 927     {
 928       auto node = GetNode(i);
 929       i         = node->mParentIdx;
 930
 931       auto iFind = rootsJoints.find(i);
 932       if(iFind != rootsJoints.end()) // Check if we've reached the root of another skeleton.
 933       {
 934         // Now find out which leaf of iFind is an ancestor, if any.
 935         auto iFindLeaf = std::find_if(iFind->second.begin(), iFind->second.end(), [this, iRoots, iFind](Index j) {
 936           return IsAncestor(*this, j, iRoots->first, iFind->first);
 937         });
 938         if(iFindLeaf != iFind->second.end())
 939         {
 940           iFind->second.erase(iFindLeaf); // Will no longer be a leaf -- remove it.
 941         }
 942
 943         // Merge iRoots with iFind
 944         auto& targetJoints = iFind->second;
 945         if(iRoots->second.empty()) // The root is a leaf.
 946         {
 947           InsertUniqueSorted(targetJoints, iRoots->first);
 948         }
 949         else
 950           for(auto j : iRoots->second)
 951           {
 952             InsertUniqueSorted(targetJoints, j);
 953           }
 954
 955         merged = true;
 956         break; // Traverse no more
 957       }
 958     }
 959
 960     iRoots = merged ? rootsJoints.erase(iRoots) : std::next(iRoots);
 961   }
 962
 963   // 3, For each root, register joint matrices and constraints
 964   for(const auto& r : rootsJoints)
 965   {
 966     auto node      = GetNode(r.first);
 967     auto rootJoint = root.FindChildByName(node->mName);
 968     DALI_ASSERT_ALWAYS(!!rootJoint);
 969
 970     DALI_ASSERT_DEBUG(rootJoint.GetPropertyIndex(JOINT_MATRIX) == Property::INVALID_INDEX);
 971     auto       propJointMatrix = rootJoint.RegisterProperty(JOINT_MATRIX, Matrix{false});
 972     Constraint constraint      = Constraint::New<Matrix>(rootJoint, propJointMatrix, [](Matrix& output, const PropertyInputContainer& inputs) {
 973       output.SetTransformComponents(Vector3::ONE, inputs[0]->GetQuaternion(), inputs[1]->GetVector3());
 974     });
 975     constraint.AddSource(Source(rootJoint, Actor::Property::ORIENTATION));
 976     constraint.AddSource(Source(rootJoint, Actor::Property::POSITION));
 977     constraint.Apply();
 978
 979     for(const auto j : r.second)
 980     {
 981       node       = GetNode(j);
 982       auto joint = rootJoint.FindChildByName(node->mName);
 983       ConfigureJointMatrix(joint, rootJoint, propJointMatrix);
 984     }
 985   }
 986 }
 987
 988 void SceneDefinition::EnsureUniqueSkinningShaderInstances(ResourceBundle& resources) const
 989 {
 990   std::map<Index, std::map<Index, std::vector<Index*>>> skinningShaderUsers;
 991   for(auto& node : mNodes)
 992   {
 993     for(auto& renderable : node->mRenderables)
 994     {
 995       ResourceReflector reflector;
 996       renderable->ReflectResources(reflector);
 997
 998       if(reflector.iMesh)
 999       {
1000         const auto& mesh = resources.mMeshes[*reflector.iMesh].first;
1001         if(mesh.IsSkinned())
1002         {
1003           skinningShaderUsers[*reflector.iShader][mesh.mSkeletonIdx].push_back(reflector.iShader);
1004         }
1005       }
1006     }
1007   }
1008
1009   // For each shader, and each skeleton using the same shader as the first skeleton,
1010   // update the shader references (from nodes with skinned meshes) with a new copy of
1011   // the shader definition from the node using the first skeleton.
1012   for(auto& users : skinningShaderUsers)
1013   {
1014     auto& skeletons    = users.second;
1015     auto  iterSkeleton = skeletons.begin();
1016     // skipping the first skeleton.
1017     ++iterSkeleton;
1018
1019     resources.mShaders.reserve(resources.mShaders.size() + std::distance(iterSkeleton, skeletons.end()));
1020     const ShaderDefinition& shaderDef = resources.mShaders[users.first].first;
1021
1022     while(iterSkeleton != skeletons.end())
1023     {
1024       Index iShader = resources.mShaders.size();
1025       resources.mShaders.push_back({shaderDef, Shader()});
1026
1027       for(auto& i : iterSkeleton->second)
1028       {
1029         *i = iShader;
1030       }
1031       ++iterSkeleton;
1032     }
1033   }
1034 }
1035
1036 void SceneDefinition::ConfigureSkinningShaders(const ResourceBundle&                             resources,
1037                                                Actor                                             rootActor,
1038                                                std::vector<SkinningShaderConfigurationRequest>&& requests) const
1039 {
1040   if(requests.empty())
1041   {
1042     return;
1043   }
1044
1045   SortAndDeduplicateSkinningRequests(requests);
1046
1047   for(auto& request : requests)
1048   {
1049     auto& skeleton = resources.mSkeletons[request.mSkeletonIdx];
1050     if(skeleton.mJoints.empty())
1051     {
1052       LOGD(("Skeleton %d has no joints.", request.mSkeletonIdx));
1053       continue;
1054     }
1055
1056     Index boneIdx = 0;
1057     for(auto& joint : skeleton.mJoints)
1058     {
1059       auto  node  = GetNode(joint.mNodeIdx);
1060       Actor actor = rootActor.FindChildByName(node->mName);
1061       ConfigureBoneMatrix(joint.mInverseBindMatrix, actor, request.mShader, boneIdx);
1062     }
1063   }
1064 }
1065
1066 bool SceneDefinition::ConfigureBlendshapeShaders(const ResourceBundle&                               resources,
1067                                                  Actor                                               rootActor,
1068                                                  std::vector<BlendshapeShaderConfigurationRequest>&& requests,
1069                                                  StringCallback                                      onError) const
1070 {
1071   if(requests.empty())
1072   {
1073     return true;
1074   }
1075
1076   // Sort requests by shaders.
1077   std::sort(requests.begin(), requests.end());
1078
1079   // Remove duplicates.
1080   auto   i    = requests.begin();
1081   auto   iEnd = requests.end();
1082   Shader s    = i->mShader;
1083   ++i;
1084   do
1085   {
1086     // Multiple identical shader instances are removed.
1087     while(i != iEnd && i->mShader == s)
1088     {
1089       i->mShader = Shader();
1090       ++i;
1091     }
1092
1093     if(i == iEnd)
1094     {
1095       break;
1096     }
1097     s = i->mShader;
1098     ++i;
1099   } while(true);
1100
1101   // Configure the rest.
1102   bool ok = true;
1103
1104   for(auto& i : requests)
1105   {
1106     Index iNode;
1107     if(FindNode(i.mNodeName, &iNode))
1108     {
1109       const auto& node = GetNode(iNode);
1110
1111       const auto& mesh = resources.mMeshes[i.mMeshIdx];
1112
1113       if(mesh.first.HasBlendShapes())
1114       {
1115         Actor actor = rootActor.FindChildByName(node->mName);
1116
1117         // Sets the property to be animated.
1118         BlendShapes::ConfigureProperties(mesh, i.mShader, actor);
1119       }
1120     }
1121   }
1122
1123   return ok;
1124 }
1125
1126 void SceneDefinition::EnsureUniqueBlendShapeShaderInstances(ResourceBundle& resources) const
1127 {
1128   std::map<Index, std::map<std::string, std::vector<Index*>>> blendShapeShaderUsers;
1129   for(auto& node : mNodes)
1130   {
1131     for(auto& renderable : node->mRenderables)
1132     {
1133       ResourceReflector reflector;
1134       renderable->ReflectResources(reflector);
1135
1136       if(reflector.iMesh)
1137       {
1138         const auto& mesh = resources.mMeshes[*reflector.iMesh].first;
1139         if(mesh.HasBlendShapes())
1140         {
1141           blendShapeShaderUsers[*reflector.iShader][node->mName].push_back(reflector.iShader);
1142         }
1143       }
1144     }
1145   }
1146
1147   for(auto& users : blendShapeShaderUsers)
1148   {
1149     resources.mShaders.reserve(resources.mShaders.size() + users.second.size() - 1u);
1150     const ShaderDefinition& shaderDef = resources.mShaders[users.first].first;
1151
1152     auto nodesIt    = users.second.begin();
1153     auto nodesEndIt = users.second.end();
1154     // skipping the first node.
1155     ++nodesIt;
1156     while(nodesIt != nodesEndIt)
1157     {
1158       Index iShader = resources.mShaders.size();
1159       resources.mShaders.push_back({shaderDef, Shader()});
1160
1161       auto& nodes = *nodesIt;
1162       for(auto& shader : nodes.second)
1163       {
1164         *shader = iShader;
1165       }
1166       ++nodesIt;
1167     }
1168   }
1169 }
1170
1171 SceneDefinition& SceneDefinition::operator=(SceneDefinition&& other)
1172 {
1173   SceneDefinition temp(std::move(other));
1174   std::swap(mNodes, temp.mNodes);
1175   std::swap(mRootNodeIds, temp.mRootNodeIds);
1176   return *this;
1177 }
1178
1179 bool SceneDefinition::FindNode(const std::string& name, std::unique_ptr<NodeDefinition>** result)
1180 {
1181   // We're searching from the end assuming a higher probability of operations targeting
1182   // recently added nodes. (conf.: root, which is immovable, cannot be removed, and was
1183   // the first to be added, is index 0.)
1184   auto iFind = std::find_if(mNodes.rbegin(), mNodes.rend(), [&name](const std::unique_ptr<NodeDefinition>& nd) {
1185                  return nd->mName == name;
1186                }).base();
1187
1188   const bool success = iFind != mNodes.begin();
1189   if(success && result)
1190   {
1191     --iFind;
1192     *result = &*iFind;
1193   }
1194
1195   return success;
1196 }
1197
1198 } // namespace Loader
1199 } // namespace Scene3D
1200 } // namespace Dali