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

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