skin_tool.cpp 28 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848
  1. /**************************************************************************/
  2. /* skin_tool.cpp */
  3. /**************************************************************************/
  4. /* This file is part of: */
  5. /* GODOT ENGINE */
  6. /* https://godotengine.org */
  7. /**************************************************************************/
  8. /* Copyright (c) 2014-present Godot Engine contributors (see AUTHORS.md). */
  9. /* Copyright (c) 2007-2014 Juan Linietsky, Ariel Manzur. */
  10. /* */
  11. /* Permission is hereby granted, free of charge, to any person obtaining */
  12. /* a copy of this software and associated documentation files (the */
  13. /* "Software"), to deal in the Software without restriction, including */
  14. /* without limitation the rights to use, copy, modify, merge, publish, */
  15. /* distribute, sublicense, and/or sell copies of the Software, and to */
  16. /* permit persons to whom the Software is furnished to do so, subject to */
  17. /* the following conditions: */
  18. /* */
  19. /* The above copyright notice and this permission notice shall be */
  20. /* included in all copies or substantial portions of the Software. */
  21. /* */
  22. /* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */
  23. /* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */
  24. /* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. */
  25. /* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */
  26. /* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */
  27. /* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */
  28. /* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */
  29. /**************************************************************************/
  30. #include "skin_tool.h"
  31. SkinNodeIndex SkinTool::_find_highest_node(Vector<Ref<GLTFNode>> &r_nodes, const Vector<GLTFNodeIndex> &p_subset) {
  32. int highest = -1;
  33. SkinNodeIndex best_node = -1;
  34. for (int i = 0; i < p_subset.size(); ++i) {
  35. const SkinNodeIndex node_i = p_subset[i];
  36. const Ref<GLTFNode> node = r_nodes[node_i];
  37. if (highest == -1 || node->height < highest) {
  38. highest = node->height;
  39. best_node = node_i;
  40. }
  41. }
  42. return best_node;
  43. }
  44. bool SkinTool::_capture_nodes_in_skin(const Vector<Ref<GLTFNode>> &nodes, Ref<GLTFSkin> p_skin, const SkinNodeIndex p_node_index) {
  45. bool found_joint = false;
  46. Ref<GLTFNode> current_node = nodes[p_node_index];
  47. for (int i = 0; i < current_node->children.size(); ++i) {
  48. found_joint |= _capture_nodes_in_skin(nodes, p_skin, current_node->children[i]);
  49. }
  50. if (found_joint) {
  51. // Mark it if we happen to find another skins joint...
  52. if (current_node->joint && !p_skin->joints.has(p_node_index)) {
  53. p_skin->joints.push_back(p_node_index);
  54. } else if (!p_skin->non_joints.has(p_node_index)) {
  55. p_skin->non_joints.push_back(p_node_index);
  56. }
  57. }
  58. if (p_skin->joints.find(p_node_index) > 0) {
  59. return true;
  60. }
  61. return false;
  62. }
  63. void SkinTool::_capture_nodes_for_multirooted_skin(Vector<Ref<GLTFNode>> &r_nodes, Ref<GLTFSkin> p_skin) {
  64. DisjointSet<SkinNodeIndex> disjoint_set;
  65. for (int i = 0; i < p_skin->joints.size(); ++i) {
  66. const SkinNodeIndex node_index = p_skin->joints[i];
  67. const SkinNodeIndex parent = r_nodes[node_index]->parent;
  68. disjoint_set.insert(node_index);
  69. if (p_skin->joints.has(parent)) {
  70. disjoint_set.create_union(parent, node_index);
  71. }
  72. }
  73. Vector<SkinNodeIndex> roots;
  74. disjoint_set.get_representatives(roots);
  75. if (roots.size() <= 1) {
  76. return;
  77. }
  78. int maxHeight = -1;
  79. // Determine the max height rooted tree
  80. for (int i = 0; i < roots.size(); ++i) {
  81. const SkinNodeIndex root = roots[i];
  82. if (maxHeight == -1 || r_nodes[root]->height < maxHeight) {
  83. maxHeight = r_nodes[root]->height;
  84. }
  85. }
  86. // Go up the tree till all of the multiple roots of the skin are at the same hierarchy level.
  87. // This sucks, but 99% of all game engines (not just Godot) would have this same issue.
  88. for (int i = 0; i < roots.size(); ++i) {
  89. SkinNodeIndex current_node = roots[i];
  90. while (r_nodes[current_node]->height > maxHeight) {
  91. SkinNodeIndex parent = r_nodes[current_node]->parent;
  92. if (r_nodes[parent]->joint && !p_skin->joints.has(parent)) {
  93. p_skin->joints.push_back(parent);
  94. } else if (!p_skin->non_joints.has(parent)) {
  95. p_skin->non_joints.push_back(parent);
  96. }
  97. current_node = parent;
  98. }
  99. // replace the roots
  100. roots.write[i] = current_node;
  101. }
  102. // Climb up the tree until they all have the same parent
  103. bool all_same;
  104. do {
  105. all_same = true;
  106. const SkinNodeIndex first_parent = r_nodes[roots[0]]->parent;
  107. for (int i = 1; i < roots.size(); ++i) {
  108. all_same &= (first_parent == r_nodes[roots[i]]->parent);
  109. }
  110. if (!all_same) {
  111. for (int i = 0; i < roots.size(); ++i) {
  112. const SkinNodeIndex current_node = roots[i];
  113. const SkinNodeIndex parent = r_nodes[current_node]->parent;
  114. if (r_nodes[parent]->joint && !p_skin->joints.has(parent)) {
  115. p_skin->joints.push_back(parent);
  116. } else if (!p_skin->non_joints.has(parent)) {
  117. p_skin->non_joints.push_back(parent);
  118. }
  119. roots.write[i] = parent;
  120. }
  121. }
  122. } while (!all_same);
  123. }
  124. Error SkinTool::_expand_skin(Vector<Ref<GLTFNode>> &r_nodes, Ref<GLTFSkin> p_skin) {
  125. _capture_nodes_for_multirooted_skin(r_nodes, p_skin);
  126. // Grab all nodes that lay in between skin joints/nodes
  127. DisjointSet<GLTFNodeIndex> disjoint_set;
  128. Vector<SkinNodeIndex> all_skin_nodes;
  129. all_skin_nodes.append_array(p_skin->joints);
  130. all_skin_nodes.append_array(p_skin->non_joints);
  131. for (int i = 0; i < all_skin_nodes.size(); ++i) {
  132. const SkinNodeIndex node_index = all_skin_nodes[i];
  133. const SkinNodeIndex parent = r_nodes[node_index]->parent;
  134. disjoint_set.insert(node_index);
  135. if (all_skin_nodes.has(parent)) {
  136. disjoint_set.create_union(parent, node_index);
  137. }
  138. }
  139. Vector<SkinNodeIndex> out_owners;
  140. disjoint_set.get_representatives(out_owners);
  141. Vector<SkinNodeIndex> out_roots;
  142. for (int i = 0; i < out_owners.size(); ++i) {
  143. Vector<SkinNodeIndex> set;
  144. disjoint_set.get_members(set, out_owners[i]);
  145. const SkinNodeIndex root = _find_highest_node(r_nodes, set);
  146. ERR_FAIL_COND_V(root < 0, FAILED);
  147. out_roots.push_back(root);
  148. }
  149. out_roots.sort();
  150. for (int i = 0; i < out_roots.size(); ++i) {
  151. _capture_nodes_in_skin(r_nodes, p_skin, out_roots[i]);
  152. }
  153. p_skin->roots = out_roots;
  154. return OK;
  155. }
  156. Error SkinTool::_verify_skin(Vector<Ref<GLTFNode>> &r_nodes, Ref<GLTFSkin> p_skin) {
  157. // This may seem duplicated from expand_skins, but this is really a sanity check! (so it kinda is)
  158. // In case additional interpolating logic is added to the skins, this will help ensure that you
  159. // do not cause it to self implode into a fiery blaze
  160. // We are going to re-calculate the root nodes and compare them to the ones saved in the skin,
  161. // then ensure the multiple trees (if they exist) are on the same sublevel
  162. // Grab all nodes that lay in between skin joints/nodes
  163. DisjointSet<GLTFNodeIndex> disjoint_set;
  164. Vector<SkinNodeIndex> all_skin_nodes;
  165. all_skin_nodes.append_array(p_skin->joints);
  166. all_skin_nodes.append_array(p_skin->non_joints);
  167. for (int i = 0; i < all_skin_nodes.size(); ++i) {
  168. const SkinNodeIndex node_index = all_skin_nodes[i];
  169. const SkinNodeIndex parent = r_nodes[node_index]->parent;
  170. disjoint_set.insert(node_index);
  171. if (all_skin_nodes.has(parent)) {
  172. disjoint_set.create_union(parent, node_index);
  173. }
  174. }
  175. Vector<SkinNodeIndex> out_owners;
  176. disjoint_set.get_representatives(out_owners);
  177. Vector<SkinNodeIndex> out_roots;
  178. for (int i = 0; i < out_owners.size(); ++i) {
  179. Vector<SkinNodeIndex> set;
  180. disjoint_set.get_members(set, out_owners[i]);
  181. const SkinNodeIndex root = _find_highest_node(r_nodes, set);
  182. ERR_FAIL_COND_V(root < 0, FAILED);
  183. out_roots.push_back(root);
  184. }
  185. out_roots.sort();
  186. ERR_FAIL_COND_V(out_roots.is_empty(), FAILED);
  187. // Make sure the roots are the exact same (they better be)
  188. ERR_FAIL_COND_V(out_roots.size() != p_skin->roots.size(), FAILED);
  189. for (int i = 0; i < out_roots.size(); ++i) {
  190. ERR_FAIL_COND_V(out_roots[i] != p_skin->roots[i], FAILED);
  191. }
  192. // Single rooted skin? Perfectly ok!
  193. if (out_roots.size() == 1) {
  194. return OK;
  195. }
  196. // Make sure all parents of a multi-rooted skin are the SAME
  197. const SkinNodeIndex parent = r_nodes[out_roots[0]]->parent;
  198. for (int i = 1; i < out_roots.size(); ++i) {
  199. if (r_nodes[out_roots[i]]->parent != parent) {
  200. return FAILED;
  201. }
  202. }
  203. return OK;
  204. }
  205. void SkinTool::_recurse_children(
  206. Vector<Ref<GLTFNode>> &nodes,
  207. const SkinNodeIndex p_node_index,
  208. RBSet<GLTFNodeIndex> &p_all_skin_nodes,
  209. HashSet<GLTFNodeIndex> &p_child_visited_set) {
  210. if (p_child_visited_set.has(p_node_index)) {
  211. return;
  212. }
  213. p_child_visited_set.insert(p_node_index);
  214. Ref<GLTFNode> current_node = nodes[p_node_index];
  215. for (int i = 0; i < current_node->children.size(); ++i) {
  216. _recurse_children(nodes, current_node->children[i], p_all_skin_nodes, p_child_visited_set);
  217. }
  218. // Continue to use 'current_node' for clarity and direct access.
  219. if (current_node->skin < 0 || current_node->mesh < 0 || !current_node->children.is_empty()) {
  220. p_all_skin_nodes.insert(p_node_index);
  221. }
  222. }
  223. void SkinTool::_check_if_parent_needs_to_become_joint(const Vector<Ref<GLTFNode>> &p_all_nodes, const Vector<GLTFNodeIndex> &p_skeleton_node_indices, const Ref<GLTFNode> &p_gltf_node, Vector<GLTFNodeIndex> &r_non_joint_indices) {
  224. const GLTFNodeIndex parent_index = p_gltf_node->parent;
  225. if (parent_index >= 0) {
  226. const Ref<GLTFNode> &parent = p_all_nodes[parent_index];
  227. if (!parent->joint && p_skeleton_node_indices.has(parent_index) && !r_non_joint_indices.has(parent_index)) {
  228. _check_if_parent_needs_to_become_joint(p_all_nodes, p_skeleton_node_indices, parent, r_non_joint_indices);
  229. r_non_joint_indices.push_back(parent_index);
  230. }
  231. }
  232. }
  233. Error SkinTool::_determine_skeletons(
  234. Vector<Ref<GLTFSkin>> &skins,
  235. Vector<Ref<GLTFNode>> &nodes,
  236. Vector<Ref<GLTFSkeleton>> &skeletons,
  237. const Vector<GLTFNodeIndex> &p_single_skeleton_roots,
  238. bool p_turn_non_joint_descendants_into_bones) {
  239. if (!p_single_skeleton_roots.is_empty()) {
  240. Ref<GLTFSkin> skin;
  241. skin.instantiate();
  242. skin->set_name("godot_single_skeleton_root");
  243. for (GLTFNodeIndex i = 0; i < p_single_skeleton_roots.size(); i++) {
  244. skin->joints.push_back(p_single_skeleton_roots[i]);
  245. }
  246. skins.push_back(skin);
  247. }
  248. // Using a disjoint set, we are going to potentially combine all skins that are actually branches
  249. // of a main skeleton, or treat skins defining the same set of nodes as ONE skeleton.
  250. // This is another unclear issue caused by the current glTF specification.
  251. DisjointSet<GLTFNodeIndex> skeleton_sets;
  252. for (GLTFSkinIndex skin_i = 0; skin_i < skins.size(); ++skin_i) {
  253. const Ref<GLTFSkin> skin = skins[skin_i];
  254. ERR_CONTINUE(skin.is_null());
  255. HashSet<GLTFNodeIndex> child_visited_set;
  256. RBSet<GLTFNodeIndex> all_skin_nodes;
  257. for (int i = 0; i < skin->joints.size(); ++i) {
  258. all_skin_nodes.insert(skin->joints[i]);
  259. SkinTool::_recurse_children(nodes, skin->joints[i], all_skin_nodes, child_visited_set);
  260. }
  261. for (int i = 0; i < skin->non_joints.size(); ++i) {
  262. all_skin_nodes.insert(skin->non_joints[i]);
  263. SkinTool::_recurse_children(nodes, skin->non_joints[i], all_skin_nodes, child_visited_set);
  264. }
  265. for (GLTFNodeIndex node_index : all_skin_nodes) {
  266. const GLTFNodeIndex parent = nodes[node_index]->parent;
  267. skeleton_sets.insert(node_index);
  268. if (all_skin_nodes.has(parent)) {
  269. skeleton_sets.create_union(parent, node_index);
  270. }
  271. }
  272. // We are going to connect the separate skin subtrees in each skin together
  273. // so that the final roots are entire sets of valid skin trees
  274. for (int i = 1; i < skin->roots.size(); ++i) {
  275. skeleton_sets.create_union(skin->roots[0], skin->roots[i]);
  276. }
  277. }
  278. { // attempt to joint all touching subsets (siblings/parent are part of another skin)
  279. Vector<SkinNodeIndex> groups_representatives;
  280. skeleton_sets.get_representatives(groups_representatives);
  281. Vector<SkinNodeIndex> highest_group_members;
  282. Vector<Vector<SkinNodeIndex>> groups;
  283. for (int i = 0; i < groups_representatives.size(); ++i) {
  284. Vector<SkinNodeIndex> group;
  285. skeleton_sets.get_members(group, groups_representatives[i]);
  286. highest_group_members.push_back(SkinTool::_find_highest_node(nodes, group));
  287. groups.push_back(group);
  288. }
  289. for (int i = 0; i < highest_group_members.size(); ++i) {
  290. const SkinNodeIndex node_i = highest_group_members[i];
  291. // Attach any siblings together (this needs to be done n^2/2 times)
  292. for (int j = i + 1; j < highest_group_members.size(); ++j) {
  293. const SkinNodeIndex node_j = highest_group_members[j];
  294. // Even if they are siblings under the root! :)
  295. if (nodes[node_i]->parent == nodes[node_j]->parent) {
  296. skeleton_sets.create_union(node_i, node_j);
  297. }
  298. }
  299. // Attach any parenting going on together (we need to do this n^2 times)
  300. const SkinNodeIndex node_i_parent = nodes[node_i]->parent;
  301. if (node_i_parent >= 0) {
  302. for (int j = 0; j < groups.size() && i != j; ++j) {
  303. const Vector<SkinNodeIndex> &group = groups[j];
  304. if (group.has(node_i_parent)) {
  305. const SkinNodeIndex node_j = highest_group_members[j];
  306. skeleton_sets.create_union(node_i, node_j);
  307. }
  308. }
  309. }
  310. }
  311. }
  312. // At this point, the skeleton groups should be finalized
  313. Vector<SkinNodeIndex> skeleton_owners;
  314. skeleton_sets.get_representatives(skeleton_owners);
  315. // Mark all the skins actual skeletons, after we have merged them
  316. for (SkinSkeletonIndex skel_i = 0; skel_i < skeleton_owners.size(); ++skel_i) {
  317. const SkinNodeIndex skeleton_owner = skeleton_owners[skel_i];
  318. Ref<GLTFSkeleton> skeleton;
  319. skeleton.instantiate();
  320. Vector<SkinNodeIndex> skeleton_nodes;
  321. skeleton_sets.get_members(skeleton_nodes, skeleton_owner);
  322. for (GLTFSkinIndex skin_i = 0; skin_i < skins.size(); ++skin_i) {
  323. Ref<GLTFSkin> skin = skins.write[skin_i];
  324. // If any of the skeletons nodes exist in a skin, that skin now maps to the skeleton
  325. for (int i = 0; i < skeleton_nodes.size(); ++i) {
  326. SkinNodeIndex skel_node_i = skeleton_nodes[i];
  327. if (skin->joints.has(skel_node_i) || skin->non_joints.has(skel_node_i)) {
  328. skin->skeleton = skel_i;
  329. continue;
  330. }
  331. }
  332. }
  333. // The nodes placed into `non_joints` will be passed to `_reparent_non_joint_skeleton_subtrees`
  334. // which will add them to the skeleton and set `node->joint` to true.
  335. Vector<SkinNodeIndex> non_joints;
  336. for (int i = 0; i < skeleton_nodes.size(); ++i) {
  337. const SkinNodeIndex node_i = skeleton_nodes[i];
  338. Ref<GLTFNode> node = nodes[node_i];
  339. if (node->joint) {
  340. if (!p_turn_non_joint_descendants_into_bones) {
  341. // If a joint node has non-joint parents, we need to make them joints as well.
  342. // For example, if A/B/C/D, and A/B and D are joints, then we need to make C a joint as well.
  343. // This is required to handle the "skinD" example in `Animation_Skin_09.gltf` from the glTF-Asset-Generator:
  344. // https://github.com/KhronosGroup/glTF-Asset-Generator/blob/master/Output/Positive/Animation_Skin
  345. _check_if_parent_needs_to_become_joint(nodes, skeleton_nodes, node, non_joints);
  346. }
  347. skeleton->joints.push_back(node_i);
  348. } else if (p_turn_non_joint_descendants_into_bones) {
  349. non_joints.push_back(node_i);
  350. }
  351. }
  352. skeletons.push_back(skeleton);
  353. SkinTool::_reparent_non_joint_skeleton_subtrees(nodes, skeletons.write[skel_i], non_joints);
  354. }
  355. for (SkinSkeletonIndex skel_i = 0; skel_i < skeletons.size(); ++skel_i) {
  356. Ref<GLTFSkeleton> skeleton = skeletons.write[skel_i];
  357. for (int i = 0; i < skeleton->joints.size(); ++i) {
  358. const SkinNodeIndex node_i = skeleton->joints[i];
  359. Ref<GLTFNode> node = nodes[node_i];
  360. ERR_FAIL_COND_V(!node->joint, ERR_PARSE_ERROR);
  361. ERR_FAIL_COND_V(node->skeleton >= 0, ERR_PARSE_ERROR);
  362. node->skeleton = skel_i;
  363. }
  364. ERR_FAIL_COND_V(SkinTool::_determine_skeleton_roots(nodes, skeletons, skel_i), ERR_PARSE_ERROR);
  365. }
  366. return OK;
  367. }
  368. Error SkinTool::_reparent_non_joint_skeleton_subtrees(
  369. Vector<Ref<GLTFNode>> &nodes,
  370. Ref<GLTFSkeleton> p_skeleton,
  371. const Vector<SkinNodeIndex> &p_non_joints) {
  372. DisjointSet<GLTFNodeIndex> subtree_set;
  373. // Populate the disjoint set with ONLY non joints that are in the skeleton hierarchy (non_joints vector)
  374. // This way we can find any joints that lie in between joints, as the current glTF specification
  375. // mentions nothing about non-joints being in between joints of the same skin. Hopefully one day we
  376. // can remove this code.
  377. // skinD depicted here explains this issue:
  378. // https://github.com/KhronosGroup/glTF-Asset-Generator/blob/master/Output/Positive/Animation_Skin
  379. for (int i = 0; i < p_non_joints.size(); ++i) {
  380. const SkinNodeIndex node_i = p_non_joints[i];
  381. subtree_set.insert(node_i);
  382. const SkinNodeIndex parent_i = nodes[node_i]->parent;
  383. if (parent_i >= 0 && p_non_joints.has(parent_i) && !nodes[parent_i]->joint) {
  384. subtree_set.create_union(parent_i, node_i);
  385. }
  386. }
  387. // Find all the non joint subtrees and re-parent them to a new "fake" joint
  388. Vector<SkinNodeIndex> non_joint_subtree_roots;
  389. subtree_set.get_representatives(non_joint_subtree_roots);
  390. for (int root_i = 0; root_i < non_joint_subtree_roots.size(); ++root_i) {
  391. const SkinNodeIndex subtree_root = non_joint_subtree_roots[root_i];
  392. Vector<SkinNodeIndex> subtree_nodes;
  393. subtree_set.get_members(subtree_nodes, subtree_root);
  394. for (int subtree_i = 0; subtree_i < subtree_nodes.size(); ++subtree_i) {
  395. Ref<GLTFNode> node = nodes[subtree_nodes[subtree_i]];
  396. node->joint = true;
  397. // Add the joint to the skeletons joints
  398. p_skeleton->joints.push_back(subtree_nodes[subtree_i]);
  399. }
  400. }
  401. return OK;
  402. }
  403. Error SkinTool::_determine_skeleton_roots(
  404. Vector<Ref<GLTFNode>> &nodes,
  405. Vector<Ref<GLTFSkeleton>> &skeletons,
  406. const SkinSkeletonIndex p_skel_i) {
  407. DisjointSet<GLTFNodeIndex> disjoint_set;
  408. for (SkinNodeIndex i = 0; i < nodes.size(); ++i) {
  409. const Ref<GLTFNode> node = nodes[i];
  410. if (node->skeleton != p_skel_i) {
  411. continue;
  412. }
  413. disjoint_set.insert(i);
  414. if (node->parent >= 0 && nodes[node->parent]->skeleton == p_skel_i) {
  415. disjoint_set.create_union(node->parent, i);
  416. }
  417. }
  418. Ref<GLTFSkeleton> skeleton = skeletons.write[p_skel_i];
  419. Vector<SkinNodeIndex> representatives;
  420. disjoint_set.get_representatives(representatives);
  421. Vector<SkinNodeIndex> roots;
  422. for (int i = 0; i < representatives.size(); ++i) {
  423. Vector<SkinNodeIndex> set;
  424. disjoint_set.get_members(set, representatives[i]);
  425. const SkinNodeIndex root = _find_highest_node(nodes, set);
  426. ERR_FAIL_COND_V(root < 0, FAILED);
  427. roots.push_back(root);
  428. }
  429. roots.sort();
  430. skeleton->roots = roots;
  431. if (roots.is_empty()) {
  432. return FAILED;
  433. } else if (roots.size() == 1) {
  434. return OK;
  435. }
  436. // Check that the subtrees have the same parent root
  437. const SkinNodeIndex parent = nodes[roots[0]]->parent;
  438. for (int i = 1; i < roots.size(); ++i) {
  439. if (nodes[roots[i]]->parent != parent) {
  440. return FAILED;
  441. }
  442. }
  443. return OK;
  444. }
  445. Error SkinTool::_create_skeletons(
  446. HashSet<String> &unique_names,
  447. Vector<Ref<GLTFSkin>> &skins,
  448. Vector<Ref<GLTFNode>> &nodes,
  449. HashMap<ObjectID, GLTFSkeletonIndex> &skeleton3d_to_gltf_skeleton,
  450. Vector<Ref<GLTFSkeleton>> &skeletons,
  451. HashMap<GLTFNodeIndex, Node *> &scene_nodes,
  452. int p_naming_version) {
  453. // This is the syntax to duplicate a Godot HashSet.
  454. HashSet<String> unique_node_names(unique_names);
  455. for (SkinSkeletonIndex skel_i = 0; skel_i < skeletons.size(); ++skel_i) {
  456. Ref<GLTFSkeleton> gltf_skeleton = skeletons.write[skel_i];
  457. HashSet<String> skel_unique_names(unique_node_names);
  458. Skeleton3D *skeleton = memnew(Skeleton3D);
  459. gltf_skeleton->godot_skeleton = skeleton;
  460. skeleton3d_to_gltf_skeleton[skeleton->get_instance_id()] = skel_i;
  461. // Make a unique name, no gltf node represents this skeleton
  462. skeleton->set_name("Skeleton3D");
  463. List<GLTFNodeIndex> bones;
  464. for (int i = 0; i < gltf_skeleton->roots.size(); ++i) {
  465. bones.push_back(gltf_skeleton->roots[i]);
  466. }
  467. // Make the skeleton creation deterministic by going through the roots in
  468. // a sorted order, and DEPTH FIRST
  469. bones.sort();
  470. while (!bones.is_empty()) {
  471. const SkinNodeIndex node_i = bones.front()->get();
  472. bones.pop_front();
  473. Ref<GLTFNode> node = nodes[node_i];
  474. ERR_FAIL_COND_V(node->skeleton != skel_i, FAILED);
  475. { // Add all child nodes to the stack (deterministically)
  476. Vector<SkinNodeIndex> child_nodes;
  477. for (int i = 0; i < node->children.size(); ++i) {
  478. const SkinNodeIndex child_i = node->children[i];
  479. if (nodes[child_i]->skeleton == skel_i) {
  480. child_nodes.push_back(child_i);
  481. }
  482. }
  483. // Depth first insertion
  484. child_nodes.sort();
  485. for (int i = child_nodes.size() - 1; i >= 0; --i) {
  486. bones.push_front(child_nodes[i]);
  487. }
  488. }
  489. const int bone_index = skeleton->get_bone_count();
  490. if (node->get_name().is_empty()) {
  491. node->set_name("bone");
  492. }
  493. if (p_naming_version < 2) {
  494. node->set_name(_gen_unique_bone_name(unique_names, node->get_name()));
  495. } else {
  496. // Make sure the bone name is unique in the skeleton and unique compared
  497. // to scene nodes, but bone names may be duplicated between skeletons.
  498. // Example: Two skeletons with a "Head" bone should not have one become "Head_2".
  499. const String unique_bone_name = _gen_unique_bone_name(skel_unique_names, node->get_name());
  500. unique_names.insert(unique_bone_name);
  501. node->set_name(unique_bone_name);
  502. }
  503. skeleton->add_bone(node->get_name());
  504. Transform3D rest_transform = node->get_additional_data("GODOT_rest_transform");
  505. skeleton->set_bone_rest(bone_index, rest_transform);
  506. skeleton->set_bone_pose_position(bone_index, node->transform.origin);
  507. skeleton->set_bone_pose_rotation(bone_index, node->transform.basis.get_rotation_quaternion());
  508. skeleton->set_bone_pose_scale(bone_index, node->transform.basis.get_scale());
  509. // Store bone-level GLTF extras in skeleton per bone meta.
  510. if (node->has_meta("extras")) {
  511. skeleton->set_bone_meta(bone_index, "extras", node->get_meta("extras"));
  512. }
  513. if (node->parent >= 0 && nodes[node->parent]->skeleton == skel_i) {
  514. const int bone_parent = skeleton->find_bone(nodes[node->parent]->get_name());
  515. ERR_FAIL_COND_V(bone_parent < 0, FAILED);
  516. skeleton->set_bone_parent(bone_index, skeleton->find_bone(nodes[node->parent]->get_name()));
  517. }
  518. scene_nodes.insert(node_i, skeleton);
  519. }
  520. }
  521. ERR_FAIL_COND_V(_map_skin_joints_indices_to_skeleton_bone_indices(skins, skeletons, nodes), ERR_PARSE_ERROR);
  522. return OK;
  523. }
  524. Error SkinTool::_map_skin_joints_indices_to_skeleton_bone_indices(
  525. Vector<Ref<GLTFSkin>> &skins,
  526. Vector<Ref<GLTFSkeleton>> &skeletons,
  527. Vector<Ref<GLTFNode>> &nodes) {
  528. for (GLTFSkinIndex skin_i = 0; skin_i < skins.size(); ++skin_i) {
  529. Ref<GLTFSkin> skin = skins.write[skin_i];
  530. ERR_CONTINUE(skin.is_null());
  531. Ref<GLTFSkeleton> skeleton = skeletons[skin->skeleton];
  532. for (int joint_index = 0; joint_index < skin->joints_original.size(); ++joint_index) {
  533. const SkinNodeIndex node_i = skin->joints_original[joint_index];
  534. const Ref<GLTFNode> node = nodes[node_i];
  535. const int bone_index = skeleton->godot_skeleton->find_bone(node->get_name());
  536. ERR_FAIL_COND_V(bone_index < 0, FAILED);
  537. skin->joint_i_to_bone_i.insert(joint_index, bone_index);
  538. }
  539. }
  540. return OK;
  541. }
  542. Error SkinTool::_create_skins(Vector<Ref<GLTFSkin>> &skins, Vector<Ref<GLTFNode>> &nodes, bool use_named_skin_binds, HashSet<String> &unique_names) {
  543. for (GLTFSkinIndex skin_i = 0; skin_i < skins.size(); ++skin_i) {
  544. Ref<GLTFSkin> gltf_skin = skins.write[skin_i];
  545. ERR_CONTINUE(gltf_skin.is_null());
  546. Ref<Skin> skin;
  547. skin.instantiate();
  548. // Some skins don't have IBM's! What absolute monsters!
  549. const bool has_ibms = !gltf_skin->inverse_binds.is_empty();
  550. for (int joint_i = 0; joint_i < gltf_skin->joints_original.size(); ++joint_i) {
  551. SkinNodeIndex node = gltf_skin->joints_original[joint_i];
  552. String bone_name = nodes[node]->get_name();
  553. Transform3D xform;
  554. if (has_ibms) {
  555. xform = gltf_skin->inverse_binds[joint_i];
  556. }
  557. if (use_named_skin_binds) {
  558. skin->add_named_bind(bone_name, xform);
  559. } else {
  560. int32_t bone_i = gltf_skin->joint_i_to_bone_i[joint_i];
  561. skin->add_bind(bone_i, xform);
  562. }
  563. }
  564. gltf_skin->godot_skin = skin;
  565. }
  566. // Purge the duplicates!
  567. _remove_duplicate_skins(skins);
  568. // Create unique names now, after removing duplicates
  569. for (GLTFSkinIndex skin_i = 0; skin_i < skins.size(); ++skin_i) {
  570. ERR_CONTINUE(skins.get(skin_i).is_null());
  571. Ref<Skin> skin = skins.write[skin_i]->godot_skin;
  572. ERR_CONTINUE(skin.is_null());
  573. if (skin->get_name().is_empty()) {
  574. // Make a unique name, no node represents this skin
  575. skin->set_name(_gen_unique_name(unique_names, "Skin"));
  576. }
  577. }
  578. return OK;
  579. }
  580. // FIXME: Duplicated from FBXDocument, very similar code in GLTFDocument too,
  581. // and even below in this class for bone names.
  582. String SkinTool::_gen_unique_name(HashSet<String> &unique_names, const String &p_name) {
  583. const String s_name = p_name.validate_node_name();
  584. String u_name;
  585. int index = 1;
  586. while (true) {
  587. u_name = s_name;
  588. if (index > 1) {
  589. u_name += itos(index);
  590. }
  591. if (!unique_names.has(u_name)) {
  592. break;
  593. }
  594. index++;
  595. }
  596. unique_names.insert(u_name);
  597. return u_name;
  598. }
  599. bool SkinTool::_skins_are_same(const Ref<Skin> p_skin_a, const Ref<Skin> p_skin_b) {
  600. if (p_skin_a->get_bind_count() != p_skin_b->get_bind_count()) {
  601. return false;
  602. }
  603. for (int i = 0; i < p_skin_a->get_bind_count(); ++i) {
  604. if (p_skin_a->get_bind_bone(i) != p_skin_b->get_bind_bone(i)) {
  605. return false;
  606. }
  607. if (p_skin_a->get_bind_name(i) != p_skin_b->get_bind_name(i)) {
  608. return false;
  609. }
  610. Transform3D a_xform = p_skin_a->get_bind_pose(i);
  611. Transform3D b_xform = p_skin_b->get_bind_pose(i);
  612. if (a_xform != b_xform) {
  613. return false;
  614. }
  615. }
  616. return true;
  617. }
  618. void SkinTool::_remove_duplicate_skins(Vector<Ref<GLTFSkin>> &r_skins) {
  619. for (int i = 0; i < r_skins.size(); ++i) {
  620. for (int j = i + 1; j < r_skins.size(); ++j) {
  621. const Ref<Skin> skin_i = r_skins[i]->godot_skin;
  622. const Ref<Skin> skin_j = r_skins[j]->godot_skin;
  623. if (_skins_are_same(skin_i, skin_j)) {
  624. // replace it and delete the old
  625. r_skins.write[j]->godot_skin = skin_i;
  626. }
  627. }
  628. }
  629. }
  630. String SkinTool::_gen_unique_bone_name(HashSet<String> &r_unique_names, const String &p_name) {
  631. String s_name = _sanitize_bone_name(p_name);
  632. if (s_name.is_empty()) {
  633. s_name = "bone";
  634. }
  635. String u_name;
  636. int index = 1;
  637. while (true) {
  638. u_name = s_name;
  639. if (index > 1) {
  640. u_name += "_" + itos(index);
  641. }
  642. if (!r_unique_names.has(u_name)) {
  643. break;
  644. }
  645. index++;
  646. }
  647. r_unique_names.insert(u_name);
  648. return u_name;
  649. }
  650. Error SkinTool::_asset_parse_skins(
  651. const Vector<SkinNodeIndex> &input_skin_indices,
  652. const Vector<Ref<GLTFSkin>> &input_skins,
  653. const Vector<Ref<GLTFNode>> &input_nodes,
  654. Vector<SkinNodeIndex> &output_skin_indices,
  655. Vector<Ref<GLTFSkin>> &output_skins,
  656. HashMap<GLTFNodeIndex, bool> &joint_mapping) {
  657. output_skin_indices.clear();
  658. output_skins.clear();
  659. joint_mapping.clear();
  660. for (int i = 0; i < input_skin_indices.size(); ++i) {
  661. SkinNodeIndex skin_index = input_skin_indices[i];
  662. if (skin_index >= 0 && skin_index < input_skins.size()) {
  663. output_skin_indices.push_back(skin_index);
  664. output_skins.push_back(input_skins[skin_index]);
  665. Ref<GLTFSkin> skin = input_skins[skin_index];
  666. Vector<SkinNodeIndex> skin_joints = skin->get_joints();
  667. for (int j = 0; j < skin_joints.size(); ++j) {
  668. SkinNodeIndex joint_index = skin_joints[j];
  669. joint_mapping[joint_index] = true;
  670. }
  671. }
  672. }
  673. return OK;
  674. }
  675. String SkinTool::_sanitize_bone_name(const String &p_name) {
  676. String bone_name = p_name;
  677. bone_name = bone_name.replace_chars(":/", '_');
  678. return bone_name;
  679. }