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