1//
2// Redistribution and use in source and binary forms, with or without
3// modification, are permitted provided that the following conditions
4// are met:
5// * Redistributions of source code must retain the above copyright
6// notice, this list of conditions and the following disclaimer.
7// * Redistributions in binary form must reproduce the above copyright
8// notice, this list of conditions and the following disclaimer in the
9// documentation and/or other materials provided with the distribution.
10// * Neither the name of NVIDIA CORPORATION nor the names of its
11// contributors may be used to endorse or promote products derived
12// from this software without specific prior written permission.
13//
14// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS ''AS IS'' AND ANY
15// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
17// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
18// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
19// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
20// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
21// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
22// OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
24// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25//
26// Copyright (c) 2008-2021 NVIDIA Corporation. All rights reserved.
27// Copyright (c) 2004-2008 AGEIA Technologies, Inc. All rights reserved.
28// Copyright (c) 2001-2004 NovodeX AG. All rights reserved.
29
30
31#ifndef PX_PHYSICS_SCP_CONSTRAINT_GROUP_NODE
32#define PX_PHYSICS_SCP_CONSTRAINT_GROUP_NODE
33
34#include "ScConstraintProjectionTree.h"
35#include "PsUtilities.h" // for Ps::to8()
36
37namespace physx
38{
39namespace Sc
40{
41 class ConstraintSim;
42 class BodySim;
43 class ConstraintProjectionManager;
44
45 // A 'simulation island' of constraints. Created by a union-find algorithm every time a new constraint is added to any of the involved bodies.
46 struct ConstraintGroupNode : public Ps::UserAllocated
47 {
48 enum StateFlags
49 {
50 eDISCOVERED = 1 << 0, // Used during projection tree generation to mark processed nodes.
51 eIN_PROJECTION_PASS_LIST = 1 << 1, // Temporarily used to avoid duplicate entries in the list of nodes that should project the pose after the solver
52 ePENDING_TREE_UPDATE = 1 << 2, // Marks the constraint groups that need their projection trees updated. Must only be set on the root group node.
53 eNEXT_FREE_SHIFT = 3,
54 eNEXT_FREE = 1 << eNEXT_FREE_SHIFT
55 };
56
57 // these flags should give a rough hint how many projecting constraints to expect in the constraint group. This will be used for
58 // load balancing when running projection in parallel. The intervals were chosen somewhat arbitrarily but the general motivation was
59 // to cover very simple constraint setups, simple ragdolls, complex ragdolls and very complex projection setups. Note that the load
60 // balancing is not waterproof since at the end it is the projection shader from the external constraint implementer (for example, a joint)
61 // which decides based on some thresholds whether projection runs or not.
62 enum ProjectionCountHintFlags
63 {
64 e1_TO_4 = eNEXT_FREE,
65 e5_TO_16 = eNEXT_FREE << 1,
66 e17_TO_64 = eNEXT_FREE << 2,
67 e65_TO_INF = eNEXT_FREE << 3,
68 eCLEAR_MASK = ~(0xffffffff << eNEXT_FREE_SHIFT)
69 };
70
71 ConstraintGroupNode(BodySim& b);
72 ~ConstraintGroupNode()
73 {
74 PX_ASSERT(!readFlag(ePENDING_TREE_UPDATE));
75 PX_ASSERT(projectionFirstRoot == NULL);
76 }
77
78 PX_FORCE_INLINE void raiseFlag(StateFlags f) { flags |= f; }
79 PX_FORCE_INLINE void clearFlag(StateFlags f) { flags &= ~f; }
80 PX_FORCE_INLINE bool readFlag(StateFlags f) const { return (flags & f) != 0; }
81 PX_FORCE_INLINE PxU32 getProjectionCountHint() const;
82 PX_FORCE_INLINE void setProjectionCountHint(PxU32 constraintsToProjectCount);
83
84 ConstraintGroupNode& getRoot();
85
86 PX_FORCE_INLINE void buildProjectionTrees(); //build the projection trees for a constraint group.
87 void markForProjectionTreeRebuild(ConstraintProjectionManager&);
88 PX_FORCE_INLINE void purgeProjectionTrees();
89 PX_FORCE_INLINE bool hasProjectionTreeRoot() { return projectionFirstRoot != NULL; }
90 PX_FORCE_INLINE void setProjectionTreeRoot(ConstraintGroupNode* root) { projectionFirstRoot = root; }
91
92 void initProjectionData(ConstraintGroupNode* parent, ConstraintSim* c);
93 void clearProjectionData();
94
95 static void projectPose(ConstraintGroupNode& root, Ps::Array<BodySim*>& projectedBodies);
96
97
98 BodySim* body; //the owner body of this node
99
100 //tree for union/find:
101 ConstraintGroupNode* parent;
102 ConstraintGroupNode* tail; //only valid if this is root of group, points to LList tail node.
103 PxU32 rank; //rank counter for union/find. Initially zero. Is number of hops from root to furthest leaf in tree. This is just a hint to create more balanced trees.
104
105 //linked list for traversal:
106 ConstraintGroupNode* next; //next in list, NULL at tail.
107
108 //projection tree information
109 ConstraintGroupNode* projectionFirstRoot; //pointer to first projection tree root node. Only set for constraint group roots
110 ConstraintGroupNode* projectionNextRoot; //pointer to next projection root node. Only set for constraint group roots
111 //a constraint group can consist of multiple projection trees if kinematics are involved! Because a kinematic doesn't split
112 //the constraint group as a static anchor does.
113 ConstraintGroupNode* projectionParent; //node to project to
114 ConstraintGroupNode* projectionFirstChild; //first node which gets projected to this one
115 ConstraintGroupNode* projectionNextSibling; //the next sibling which gets projected to the same node as this one. NULL if projectionParent is NULL.
116 ConstraintSim* projectionConstraint; //the constraint to project (constraint to projection parent)
117
118 private:
119 PxU8 flags;
120 };
121
122} // namespace Sc
123
124
125PX_FORCE_INLINE PxU32 Sc::ConstraintGroupNode::getProjectionCountHint() const
126{
127 // return the mean of the upper and lower bound
128
129 if (flags & ConstraintGroupNode::e65_TO_INF)
130 return 128;
131 else if (flags & ConstraintGroupNode::e17_TO_64)
132 return 40;
133 else if (flags & ConstraintGroupNode::e5_TO_16)
134 return 10;
135 else if (flags & ConstraintGroupNode::e1_TO_4)
136 return 2;
137
138 return 0;
139}
140
141
142PX_FORCE_INLINE void Sc::ConstraintGroupNode::setProjectionCountHint(PxU32 constraintsToProjectCount)
143{
144 PxU8 tmpFlags = flags;
145 tmpFlags &= PxU8(ConstraintGroupNode::eCLEAR_MASK);
146
147 if (constraintsToProjectCount >= 65)
148 tmpFlags |= ConstraintGroupNode::e65_TO_INF;
149 else if (constraintsToProjectCount >= 17)
150 tmpFlags |= ConstraintGroupNode::e17_TO_64;
151 else if (constraintsToProjectCount >= 5)
152 tmpFlags |= ConstraintGroupNode::e5_TO_16;
153 else if (constraintsToProjectCount >= 1)
154 tmpFlags |= ConstraintGroupNode::e1_TO_4;
155
156 flags = tmpFlags;
157}
158
159
160PX_FORCE_INLINE void Sc::ConstraintGroupNode::buildProjectionTrees()
161{
162 PX_ASSERT(this == parent); // Only call for group roots
163 PX_ASSERT(!hasProjectionTreeRoot());
164
165 ConstraintProjectionTree::buildProjectionTrees(root&: *this);
166}
167
168
169PX_FORCE_INLINE void Sc::ConstraintGroupNode::purgeProjectionTrees()
170{
171 PX_ASSERT(this == parent); // Only call for group roots
172 PX_ASSERT(hasProjectionTreeRoot());
173 ConstraintProjectionTree::purgeProjectionTrees(root&: *this);
174}
175
176}
177
178#endif
179

source code of qtquick3dphysics/src/3rdparty/PhysX/source/simulationcontroller/src/ScConstraintGroupNode.h