1 //
2 // Copyright 2016 Pixar
3 //
4 // Licensed under the Apache License, Version 2.0 (the "Apache License")
5 // with the following modification; you may not use this file except in
6 // compliance with the Apache License and the following modification to it:
7 // Section 6. Trademarks. is deleted and replaced with:
8 //
9 // 6. Trademarks. This License does not grant permission to use the trade
10 // names, trademarks, service marks, or product names of the Licensor
11 // and its affiliates, except as required to comply with Section 4(c) of
12 // the License and to reproduce the content of the NOTICE file.
13 //
14 // You may obtain a copy of the Apache License at
15 //
16 // http://www.apache.org/licenses/LICENSE-2.0
17 //
18 // Unless required by applicable law or agreed to in writing, software
19 // distributed under the Apache License with the above modification is
20 // distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
21 // KIND, either express or implied. See the Apache License for the specific
22 // language governing permissions and limitations under the Apache License.
23 //
24 #include "pxr/usd/usdSkel/topology.h"
25
26 #include "pxr/base/trace/trace.h"
27
28 #include <unordered_map>
29
30
31 PXR_NAMESPACE_OPEN_SCOPE
32
33 namespace {
34
35
36 using _PathIndexMap = std::unordered_map<SdfPath,int,SdfPath::Hash>;
37
38
39 int
_GetParentIndex(const _PathIndexMap & pathMap,const SdfPath & path)40 _GetParentIndex(const _PathIndexMap& pathMap, const SdfPath& path)
41 {
42 if (path.IsPrimPath()) {
43 // Recurse over all ancestor paths, not just the direct parent.
44 // For instance, if the map includes only paths 'a' and 'a/b/c',
45 // 'a' will be treated as the parent of 'a/b/c'.
46 const auto range = path.GetAncestorsRange();
47 auto it = range.begin();
48 for (++it; it != range.end(); ++it) {
49 const auto mapIt = pathMap.find(*it);
50 if (mapIt != pathMap.end()) {
51 return mapIt->second;
52 }
53 }
54 }
55 return -1;
56 }
57
58
59 VtIntArray
_ComputeParentIndicesFromPaths(TfSpan<const SdfPath> paths)60 _ComputeParentIndicesFromPaths(TfSpan<const SdfPath> paths)
61 {
62 TRACE_FUNCTION();
63
64 _PathIndexMap pathMap;
65 for (size_t i = 0; i < paths.size(); ++i) {
66 pathMap[paths[i]] = static_cast<int>(i);
67 }
68
69 VtIntArray parentIndices;
70 parentIndices.assign(paths.size(), -1);
71
72 const auto parentIndicesSpan = TfMakeSpan(parentIndices);
73 for (size_t i = 0; i < paths.size(); ++i) {
74 parentIndicesSpan[i] = _GetParentIndex(pathMap, paths[i]);
75 }
76 return parentIndices;
77 }
78
79
80 VtIntArray
_ComputeParentIndicesFromTokens(TfSpan<const TfToken> tokens)81 _ComputeParentIndicesFromTokens(TfSpan<const TfToken> tokens)
82 {
83 // Convert tokens to paths.
84 SdfPathVector paths(tokens.size());
85 for (size_t i = 0; i < tokens.size(); ++i) {
86 paths[i] = SdfPath(tokens[i].GetString());
87 }
88 return _ComputeParentIndicesFromPaths(paths);
89 }
90
91
92 } // namespace
93
94
95 /// TODO: It's convenient to provide this constructor, but
96 /// do we require any common methods to handle the token->path
97 /// conversion?
UsdSkelTopology(TfSpan<const TfToken> paths)98 UsdSkelTopology::UsdSkelTopology(TfSpan<const TfToken> paths)
99 : UsdSkelTopology(_ComputeParentIndicesFromTokens(paths))
100 {}
101
102
UsdSkelTopology(TfSpan<const SdfPath> paths)103 UsdSkelTopology::UsdSkelTopology(TfSpan<const SdfPath> paths)
104 : UsdSkelTopology(_ComputeParentIndicesFromPaths(paths))
105 {}
106
107
UsdSkelTopology(const VtIntArray & parentIndices)108 UsdSkelTopology::UsdSkelTopology(const VtIntArray& parentIndices)
109 : _parentIndices(parentIndices)
110 {}
111
112
113 bool
Validate(std::string * reason) const114 UsdSkelTopology::Validate(std::string* reason) const
115 {
116 TRACE_FUNCTION();
117
118 for (size_t i = 0; i < size(); ++i) {
119 const int parent = _parentIndices[i];
120 if (parent >= 0) {
121 if (ARCH_UNLIKELY(static_cast<size_t>(parent) >= i)) {
122 if (static_cast<size_t>(parent) == i) {
123 if (reason) {
124 *reason = TfStringPrintf(
125 "Joint %zu has itself as its parent.", i);
126 }
127 return false;
128 }
129
130 if (reason) {
131 *reason = TfStringPrintf(
132 "Joint %zu has mis-ordered parent %d. Joints are "
133 "expected to be ordered with parent joints always "
134 "coming before children.", i, parent);
135
136 // XXX: Note that this ordering restriction is a schema
137 // requirement primarily because it simplifies hierarchy
138 // evaluation (see UsdSkelConcatJointTransforms)
139 // But a nice side effect for validation purposes is that
140 // it also ensures that topology is non-cyclic.
141 }
142 return false;
143 }
144 }
145 }
146 return true;
147 }
148
149
150 bool
operator ==(const UsdSkelTopology & o) const151 UsdSkelTopology::operator==(const UsdSkelTopology& o) const
152 {
153 return _parentIndices == o._parentIndices;
154 }
155
156
157 PXR_NAMESPACE_CLOSE_SCOPE
158