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

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