Main Page Class List Class Members

NvBlastFamilyGraph.h
Go to the documentation of this file.
1 // This code contains NVIDIA Confidential Information and is disclosed to you
2 // under a form of NVIDIA software license agreement provided separately to you.
3 //
4 // Notice
5 // NVIDIA Corporation and its licensors retain all intellectual property and
6 // proprietary rights in and to this software and related documentation and
7 // any modifications thereto. Any use, reproduction, disclosure, or
8 // distribution of this software and related documentation without an express
9 // license agreement from NVIDIA Corporation is strictly prohibited.
10 //
11 // ALL NVIDIA DESIGN SPECIFICATIONS, CODE ARE PROVIDED "AS IS.". NVIDIA MAKES
12 // NO WARRANTIES, EXPRESSED, IMPLIED, STATUTORY, OR OTHERWISE WITH RESPECT TO
13 // THE MATERIALS, AND EXPRESSLY DISCLAIMS ALL IMPLIED WARRANTIES OF NONINFRINGEMENT,
14 // MERCHANTABILITY, AND FITNESS FOR A PARTICULAR PURPOSE.
15 //
16 // Information and code furnished is believed to be accurate and reliable.
17 // However, NVIDIA Corporation assumes no responsibility for the consequences of use of such
18 // information or for any infringement of patents or other rights of third parties that may
19 // result from its use. No license is granted by implication or otherwise under any patent
20 // or patent rights of NVIDIA Corporation. Details are subject to change without notice.
21 // This code supersedes and replaces all information previously supplied.
22 // NVIDIA Corporation products are not authorized for use as critical
23 // components in life support devices or systems without express written approval of
24 // NVIDIA Corporation.
25 //
26 // Copyright (c) 2016-2020 NVIDIA Corporation. All rights reserved.
27
28
29 #ifndef NVBLASTFAMILYGRAPH_H
30 #define NVBLASTFAMILYGRAPH_H
31
32
33 #include "NvBlastSupportGraph.h"
34 #include "NvBlastFixedArray.h"
35 #include "NvBlastFixedBitmap.h"
36 #include "NvBlastFixedBoolArray.h"
37 #include "NvBlastMath.h"
38 #include "NvBlastFixedPriorityQueue.h"
39 #include "NvBlastMemory.h"
40
41
42 namespace Nv
43 {
44 namespace Blast
45 {
46
47
48 typedef uint32_t NodeIndex;
49 typedef NodeIndex IslandId;
50 typedef uint32_t ActorIndex;
51
58 class FamilyGraph
59 {
60 public:
61
63
69 FamilyGraph(const SupportGraph* graph);
70
71
80 static size_t requiredMemorySize(uint32_t nodeCount, uint32_t bondCount)
81 {
82 return fillMemory(nullptr, nodeCount, bondCount);
83 }
84
85
87
94 void initialize(ActorIndex actorIndex, const SupportGraph* graph);
95
104 bool notifyEdgeRemoved(ActorIndex actorIndex, NodeIndex node0, NodeIndex node1, const SupportGraph* graph);
105 bool notifyEdgeRemoved(ActorIndex actorIndex, NodeIndex node0, NodeIndex node1, uint32_t bondIndex, const SupportGraph* graph);
106
107 bool notifyNodeRemoved(ActorIndex actorIndex, NodeIndex nodeIndex, const SupportGraph* graph);
108
119 uint32_t findIslands(ActorIndex actorIndex, void* scratch, const SupportGraph* graph);
120
128 static size_t findIslandsRequiredScratch(uint32_t graphNodeCount);
129
130
132
139 NvBlastBlockData(IslandId, m_islandIdsOffset, getIslandIds);
140
144 NvBlastBlockData(NodeIndex, m_dirtyNodeLinksOffset, getDirtyNodeLinks);
145
149 NvBlastBlockData(uint32_t, m_firstDirtyNodeIndicesOffset, getFirstDirtyNodeIndices);
150
154 NvBlastBlockData(NodeIndex, m_fastRouteOffset, getFastRoute);
155
159 NvBlastBlockData(uint32_t, m_hopCountsOffset, getHopCounts);
160
164 NvBlastBlockData(FixedBoolArray, m_isEdgeRemovedOffset, getIsEdgeRemoved);
165
169 NvBlastBlockData(FixedBoolArray, m_isNodeInDirtyListOffset, getIsNodeInDirtyList);
170
171
173
174 uint32_t getEdgesCount(const SupportGraph* graph) const;
175 bool hasEdge(NodeIndex node0, NodeIndex node1, const SupportGraph* graph) const;
176 bool canFindRoot(NodeIndex startNode, NodeIndex targetNode, FixedArray<NodeIndex>* visitedNodes, const SupportGraph* graph);
177
178
179 private:
180
181 FamilyGraph& operator = (const FamilyGraph&);
182
184
188 struct TraversalState
189 {
190 NodeIndex mNodeIndex;
191 uint32_t mCurrentIndex;
192 uint32_t mPrevIndex;
193 uint32_t mDepth;
194
195 TraversalState()
196 {
197 }
198
199 TraversalState(NodeIndex nodeIndex, uint32_t currentIndex, uint32_t prevIndex, uint32_t depth) :
200 mNodeIndex(nodeIndex), mCurrentIndex(currentIndex), mPrevIndex(prevIndex), mDepth(depth)
201 {
202 }
203 };
204
208 struct QueueElement
209 {
210 TraversalState* mState;
211 uint32_t mHopCount;
212
213 QueueElement()
214 {
215 }
216
217 QueueElement(TraversalState* state, uint32_t hopCount) : mState(state), mHopCount(hopCount)
218 {
219 }
220 };
221
225 struct NodeComparator
226 {
227 NodeComparator()
228 {
229 }
230
231 bool operator() (const QueueElement& node0, const QueueElement& node1) const
232 {
233 return node0.mHopCount < node1.mHopCount;
234 }
235 private:
236 NodeComparator& operator = (const NodeComparator&);
237 };
238
242 typedef FixedPriorityQueue<QueueElement, NodeComparator> NodePriorityQueue;
243
244
246
257 static size_t fillMemory(FamilyGraph* familyGraph, uint32_t nodeCount, uint32_t bondCount);
258
262 bool findRoute(NodeIndex startNode, NodeIndex targetNode, IslandId islandId, FixedArray<TraversalState>* visitedNodes, FixedBitmap* isNodeWitness, NodePriorityQueue* priorityQueue, const SupportGraph* graph);
263
267 bool tryFastPath(NodeIndex startNode, NodeIndex targetNode, IslandId islandId, FixedArray<TraversalState>* visitedNodes, FixedBitmap* isNodeWitness, const SupportGraph* graph);
268
274 void unwindRoute(uint32_t traversalIndex, NodeIndex lastNode, uint32_t hopCount, IslandId id, FixedArray<TraversalState>* visitedNodes);
275
279 void addToDirtyNodeList(ActorIndex actorIndex, NodeIndex node);
280
284 NodeIndex getAdjacentNode(uint32_t adjacencyIndex, const SupportGraph* graph) const
285 {
286 const uint32_t bondIndex = graph->getAdjacentBondIndices()[adjacencyIndex];
287 return getIsEdgeRemoved()->test(bondIndex) ? invalidIndex<uint32_t>() : graph->getAdjacentNodeIndices()[adjacencyIndex];
288 }
289
290 };
291
292
293 } // namespace Blast
294 } // namespace Nv
295
296
297 #endif // ifndef NVBLASTFAMILYGRAPH_H
Nv::Blast::FamilyGraph::notifyEdgeRemoved
bool notifyEdgeRemoved(ActorIndex actorIndex, NodeIndex node0, NodeIndex node1, const SupportGraph *graph)
Nv::Blast::FixedBoolArray
Definition: NvBlastFixedBoolArray.h:63
Nv::Blast::FamilyGraph
Definition: NvBlastFamilyGraph.h:58
Nv::Blast::FamilyGraph::findIslands
uint32_t findIslands(ActorIndex actorIndex, void *scratch, const SupportGraph *graph)
Nv::Blast::SupportGraph
Definition: NvBlastSupportGraph.h:76
Nv::Blast::FamilyGraph::findIslandsRequiredScratch
static size_t findIslandsRequiredScratch(uint32_t graphNodeCount)
Nv::Blast::FixedPriorityQueue
Definition: NvBlastFixedPriorityQueue.h:73
NvBlastMath.h
NvBlastSupportGraph.h
Nv::Blast::FamilyGraph::NvBlastBlockData
NvBlastBlockData(IslandId, m_islandIdsOffset, getIslandIds)
Nv::Blast::FixedArray
Definition: NvBlastFixedArray.h:64
NvBlastFixedPriorityQueue.h
Nv::Blast::FamilyGraph::getEdgesCount
uint32_t getEdgesCount(const SupportGraph *graph) const
Nv::Blast::FamilyGraph::FamilyGraph
FamilyGraph(const SupportGraph *graph)
Nv::Blast::NodeIndex
uint32_t NodeIndex
Definition: NvBlastFamilyGraph.h:48
NvBlastMemory.h
Nv::Blast::FamilyGraph::initialize
void initialize(ActorIndex actorIndex, const SupportGraph *graph)
Nv::Blast::FixedBitmap
Definition: NvBlastFixedBitmap.h:63
Nv::Blast::FamilyGraph::notifyNodeRemoved
bool notifyNodeRemoved(ActorIndex actorIndex, NodeIndex nodeIndex, const SupportGraph *graph)
Nv::Blast::IslandId
NodeIndex IslandId
Definition: NvBlastFamilyGraph.h:49
Nv::Blast::FamilyGraph::hasEdge
bool hasEdge(NodeIndex node0, NodeIndex node1, const SupportGraph *graph) const
Nv::Blast::FamilyGraph::requiredMemorySize
static size_t requiredMemorySize(uint32_t nodeCount, uint32_t bondCount)
Definition: NvBlastFamilyGraph.h:80
NvBlastFixedBitmap.h
NvBlastFixedBoolArray.h
NvBlastFixedArray.h
Nv
Definition: NvBlastArray.h:37
Nv::Blast::ActorIndex
uint32_t ActorIndex
Definition: NvBlastFamilyGraph.h:50
Nv::Blast::FamilyGraph::canFindRoot
bool canFindRoot(NodeIndex startNode, NodeIndex targetNode, FixedArray< NodeIndex > *visitedNodes, const SupportGraph *graph)