diff options
| author | Bryan Galdrikian <[email protected]> | 2017-02-21 12:07:59 -0800 |
|---|---|---|
| committer | Bryan Galdrikian <[email protected]> | 2017-02-21 12:07:59 -0800 |
| commit | 446ce137c6823ba9eff273bdafdaf266287c7c98 (patch) | |
| tree | d20aab3e2ed08d7b3ca71c2f40db6a93ea00c459 /NvBlast/sdk/lowlevel/source | |
| download | blast-1.0.0-beta.tar.xz blast-1.0.0-beta.zip | |
first commitv1.0.0-beta
Diffstat (limited to 'NvBlast/sdk/lowlevel/source')
| -rw-r--r-- | NvBlast/sdk/lowlevel/source/NvBlastActor.cpp | 1316 | ||||
| -rw-r--r-- | NvBlast/sdk/lowlevel/source/NvBlastActor.h | 732 | ||||
| -rw-r--r-- | NvBlast/sdk/lowlevel/source/NvBlastActorSerializationBlock.cpp | 575 | ||||
| -rw-r--r-- | NvBlast/sdk/lowlevel/source/NvBlastActorSerializationBlock.h | 151 | ||||
| -rw-r--r-- | NvBlast/sdk/lowlevel/source/NvBlastAsset.cpp | 931 | ||||
| -rw-r--r-- | NvBlast/sdk/lowlevel/source/NvBlastAsset.h | 294 | ||||
| -rw-r--r-- | NvBlast/sdk/lowlevel/source/NvBlastAssetHelper.cpp | 183 | ||||
| -rw-r--r-- | NvBlast/sdk/lowlevel/source/NvBlastChunkHierarchy.h | 232 | ||||
| -rw-r--r-- | NvBlast/sdk/lowlevel/source/NvBlastFamily.cpp | 295 | ||||
| -rw-r--r-- | NvBlast/sdk/lowlevel/source/NvBlastFamily.h | 238 | ||||
| -rw-r--r-- | NvBlast/sdk/lowlevel/source/NvBlastFamilyGraph.cpp | 629 | ||||
| -rw-r--r-- | NvBlast/sdk/lowlevel/source/NvBlastFamilyGraph.h | 280 | ||||
| -rw-r--r-- | NvBlast/sdk/lowlevel/source/NvBlastSupportGraph.h | 134 |
13 files changed, 5990 insertions, 0 deletions
diff --git a/NvBlast/sdk/lowlevel/source/NvBlastActor.cpp b/NvBlast/sdk/lowlevel/source/NvBlastActor.cpp new file mode 100644 index 0000000..b93c47a --- /dev/null +++ b/NvBlast/sdk/lowlevel/source/NvBlastActor.cpp @@ -0,0 +1,1316 @@ +/* +* Copyright (c) 2016-2017, NVIDIA CORPORATION. All rights reserved. +* +* NVIDIA CORPORATION and its licensors retain all intellectual property +* and proprietary rights in and to this software, related documentation +* and any modifications thereto. Any use, reproduction, disclosure or +* distribution of this software and related documentation without an express +* license agreement from NVIDIA CORPORATION is strictly prohibited. +*/ + +#include "NvBlastActor.h" +#include "NvBlastFamilyGraph.h" +#include "NvBlastChunkHierarchy.h" +#include "NvBlastIndexFns.h" +#include "NvBlastDLink.h" +#include "NvBlastGeometry.h" +#include "NvBlastTime.h" +#include <float.h> +#include <algorithm> + + +namespace Nv +{ +namespace Blast +{ + +//////// Local helper functions //////// + +#if NVBLAST_CHECK_PARAMS +/** +Helper function to validate fracture buffer values being meaningful. +*/ +static inline bool isValid(const NvBlastFractureBuffers* buffers) +{ + if (buffers->chunkFractureCount != 0 && buffers->chunkFractures == nullptr) + return false; + + if (buffers->bondFractureCount != 0 && buffers->bondFractures == nullptr) + return false; + + return true; +} +#endif + +//////// Actor static methods //////// + +size_t Actor::createRequiredScratch(const NvBlastFamily* family) +{ +#if NVBLAST_CHECK_PARAMS + if (family == nullptr || reinterpret_cast<const FamilyHeader*>(family)->m_asset == nullptr) + { + NVBLAST_ALWAYS_ASSERT(); + return 0; + } +#endif + + const Asset& solverAsset = *reinterpret_cast<const FamilyHeader*>(family)->m_asset; + return FamilyGraph::findIslandsRequiredScratch(solverAsset.m_graph.m_nodeCount); +} + + +Actor* Actor::create(NvBlastFamily* family, const NvBlastActorDesc* desc, void* scratch, NvBlastLog logFn) +{ + NVBLAST_CHECK(family != nullptr, logFn, "Actor::create: NULL family pointer input.", return nullptr); + NVBLAST_CHECK(reinterpret_cast<FamilyHeader*>(family)->m_asset != nullptr, logFn, "Actor::create: family has NULL asset.", return nullptr); + NVBLAST_CHECK(reinterpret_cast<FamilyHeader*>(family)->m_asset->m_graph.m_nodeCount != 0, logFn, "Actor::create: family's asset has no support chunks.", return nullptr); + NVBLAST_CHECK(desc != nullptr, logFn, "Actor::create: NULL desc pointer input.", return nullptr); + NVBLAST_CHECK(scratch != nullptr, logFn, "Actor::create: NULL scratch input.", return nullptr); + + FamilyHeader* header = reinterpret_cast<FamilyHeader*>(family); + + if (header->m_actorCount > 0) + { + NVBLAST_LOG_ERROR(logFn, "Actor::create: input family is not empty."); + return nullptr; + } + + const Asset& solverAsset = *static_cast<const Asset*>(header->m_asset); + const Nv::Blast::SupportGraph& graph = solverAsset.m_graph; + + // Lower support chunk healths - initialize + float* lowerSupportChunkHealths = header->getLowerSupportChunkHealths(); + if (desc->initialSupportChunkHealths != nullptr) // Health array given + { + const uint32_t* supportChunkIndices = graph.getChunkIndices(); + for (uint32_t supportChunkNum = 0; supportChunkNum < graph.m_nodeCount; ++supportChunkNum) + { + const float initialHealth = desc->initialSupportChunkHealths[supportChunkNum]; + for (Asset::DepthFirstIt i(solverAsset, supportChunkIndices[supportChunkNum]); (bool)i; ++i) + { + lowerSupportChunkHealths[solverAsset.getContiguousLowerSupportIndex((uint32_t)i)] = initialHealth; + } + } + } + else // Use uniform initialization + { + const uint32_t lowerSupportChunkCount = solverAsset.getLowerSupportChunkCount(); + for (uint32_t i = 0; i < lowerSupportChunkCount; ++i) + { + lowerSupportChunkHealths[i] = desc->uniformInitialLowerSupportChunkHealth; + } + } + + // Bond healths - initialize + const uint32_t bondCount = solverAsset.getBondCount(); + float* bondHealths = header->getBondHealths(); + if (desc->initialBondHealths != nullptr) // Health array given + { + memcpy(bondHealths, desc->initialBondHealths, bondCount * sizeof(float)); + } + else // Use uniform initialization + { + for (uint32_t bondNum = 0; bondNum < bondCount; ++bondNum) + { + bondHealths[bondNum] = desc->uniformInitialBondHealth; + } + } + + // Get first actor - NOTE: we don't send an event for this! May need to do so for consistency. + Actor* actor = header->borrowActor(0); // Using actor[0] + + // Fill in actor fields + actor->m_firstGraphNodeIndex = 0; + actor->m_graphNodeCount = graph.m_nodeCount; + actor->m_leafChunkCount = solverAsset.m_leafChunkCount; + + // Graph node index links - initialize to chain + uint32_t* graphNodeLinks = header->getGraphNodeIndexLinks(); + for (uint32_t i = 0; i < graph.m_nodeCount - 1; ++i) + { + graphNodeLinks[i] = i + 1; + } + graphNodeLinks[graph.m_nodeCount - 1] = invalidIndex<uint32_t>(); + + // Update visible chunks (we assume that all chunks belong to one actor at the beginning) + actor->updateVisibleChunksFromGraphNodes(); + + // Initialize instance graph with this actor + header->getFamilyGraph()->initialize(actor->getIndex(), &graph); + + // Call findIslands to set up the internal instance graph data + header->getFamilyGraph()->findIslands(actor->getIndex(), scratch, &graph); + + return actor; +} + + +//////// Actor member methods //////// + +uint32_t Actor::damageBond(uint32_t nodeIndex0, uint32_t nodeIndex1, float healthDamage) +{ + const uint32_t bondIndex = getGraph()->findBond(nodeIndex0, nodeIndex1); + damageBond(nodeIndex0, nodeIndex1, bondIndex, healthDamage); + return bondIndex; +} + + +void Actor::damageBond(uint32_t nodeIndex0, uint32_t nodeIndex1, uint32_t bondIndex, float healthDamage) +{ + if (bondIndex == invalidIndex<uint32_t>()) + { + NVBLAST_ALWAYS_ASSERT(); + return; + } + + float* bondHealths = getBondHealths(); + if (bondHealths[bondIndex] > 0 && healthDamage > 0.0f) + { + // Subtract health + bondHealths[bondIndex] -= healthDamage; + + // Was removed? + if (bondHealths[bondIndex] <= 0) + { + // Notify graph that bond was removed + getFamilyGraph()->notifyEdgeRemoved(getIndex(), nodeIndex0, nodeIndex1, bondIndex, getGraph()); + bondHealths[bondIndex] = 0; // Doing this for single-actor serialization consistency; should not actually be necessary + } + } +} + + +uint32_t Actor::damageBond(const NvBlastBondFractureData& cmd) +{ + NVBLAST_ASSERT(!isInvalidIndex(cmd.nodeIndex1)); + return damageBond(cmd.nodeIndex0, cmd.nodeIndex1, cmd.health); +} + + +void Actor::generateFracture(NvBlastFractureBuffers* commandBuffers, const NvBlastDamageProgram& program, const NvBlastProgramParams* programParams, + NvBlastLog logFn, NvBlastTimers* timers) const +{ + NVBLAST_CHECK(commandBuffers != nullptr, logFn, "Actor::generateFracture: NULL commandBuffers pointer input.", return); + NVBLAST_CHECK(isValid(commandBuffers), logFn, "NvBlastActorGenerateFracture: commandBuffers memory is NULL but size is > 0.", + commandBuffers->bondFractureCount = 0; commandBuffers->chunkFractureCount = 0; return); + +#if NVBLAST_CHECK_PARAMS + if (commandBuffers->bondFractureCount == 0 && commandBuffers->chunkFractureCount == 0) + { + NVBLAST_LOG_WARNING(logFn, "NvBlastActorGenerateFracture: commandBuffers do not provide any space."); + return; + } +#endif + +#if NV_PROFILE + Time time; +#else + NV_UNUSED(timers); +#endif + + const SupportGraph* graph = getGraph(); + + const uint32_t graphNodeCount = getGraphNodeCount(); + if (graphNodeCount > 1 && program.graphShaderFunction != nullptr) + { + const NvBlastGraphShaderActor shaderActor = { + getFirstGraphNodeIndex(), + getGraphNodeIndexLinks(), + graph->getChunkIndices(), + graph->getAdjacencyPartition(), + graph->getAdjacentNodeIndices(), + graph->getAdjacentBondIndices(), + getBonds(), + getBondHealths() + }; + + program.graphShaderFunction(commandBuffers, &shaderActor, programParams); + } + else if (graphNodeCount <= 1 && program.subgraphShaderFunction != nullptr) + { + const NvBlastSubgraphShaderActor shaderActor = { + // The conditional (visible vs. support chunk) is needed because we allow single-child chunk chains + // This makes it possible that an actor with a single support chunk will have a different visible chunk (ancestor of the support chunk) + graphNodeCount == 1 ? graph->getChunkIndices()[getFirstGraphNodeIndex()] : getFirstVisibleChunkIndex(), + getChunks() + }; + + program.subgraphShaderFunction(commandBuffers, &shaderActor, programParams); + } + else + { + commandBuffers->bondFractureCount = 0; + commandBuffers->chunkFractureCount = 0; + } + +#if NV_PROFILE + if (timers != nullptr) + { + timers->material += time.getElapsedTicks(); + } +#endif +} + + +void Actor::fractureSubSupportNoEvents(uint32_t chunkIndex, uint32_t suboffset, float healthDamage, float* chunkHealths, const NvBlastChunk* chunks) +{ + const NvBlastChunk& chunk = chunks[chunkIndex]; + uint32_t numChildren = chunk.childIndexStop - chunk.firstChildIndex; + + if (numChildren > 0) + { + healthDamage /= numChildren; + for (uint32_t childIndex = chunk.firstChildIndex; childIndex < chunk.childIndexStop; childIndex++) + { + float& health = chunkHealths[childIndex - suboffset]; + if (health > 0.0f) + { + float remainingDamage = healthDamage - health; + health -= healthDamage; + + NVBLAST_ASSERT(chunks[childIndex].parentChunkIndex == chunkIndex); + + if (health <= 0.0f && remainingDamage > 0.0f) + { + fractureSubSupportNoEvents(childIndex, suboffset, remainingDamage, chunkHealths, chunks); + } + } + } + } +} + + +void Actor::fractureSubSupport(uint32_t chunkIndex, uint32_t suboffset, float healthDamage, float* chunkHealths, const NvBlastChunk* chunks, NvBlastChunkFractureData* outBuffer, uint32_t* currentIndex, const uint32_t maxCount) +{ + const NvBlastChunk& chunk = chunks[chunkIndex]; + uint32_t numChildren = chunk.childIndexStop - chunk.firstChildIndex; + + if (numChildren > 0) + { + healthDamage /= numChildren; + for (uint32_t childIndex = chunk.firstChildIndex; childIndex < chunk.childIndexStop; childIndex++) + { + float& health = chunkHealths[childIndex - suboffset]; + if (health > 0.0f) + { + float remainingDamage = healthDamage - health; + health -= healthDamage; + + NVBLAST_ASSERT(chunks[childIndex].parentChunkIndex == chunkIndex); + + if (*currentIndex < maxCount) + { + NvBlastChunkFractureData& event = outBuffer[*currentIndex]; + event.userdata = chunks[childIndex].userData; + event.chunkIndex = childIndex; + event.health = health; + } + (*currentIndex)++; + + if (health <= 0.0f && remainingDamage > 0.0f) + { + fractureSubSupport(childIndex, suboffset, remainingDamage, chunkHealths, chunks, outBuffer, currentIndex, maxCount); + } + } + } + } + +} + + +void Actor::fractureNoEvents(uint32_t chunkFractureCount, const NvBlastChunkFractureData* chunkFractures) +{ + const Asset& asset = *getAsset(); + const SupportGraph& graph = *getGraph(); + const uint32_t* graphAdjacencyPartition = graph.getAdjacencyPartition(); + const uint32_t* graphAdjacentNodeIndices = graph.getAdjacentNodeIndices(); + float* bondHealths = getBondHealths(); + float* chunkHealths = getLowerSupportChunkHealths(); + float* subChunkHealths = getSubsupportChunkHealths(); + const NvBlastChunk* chunks = getChunks(); + + for (uint32_t i = 0; i < chunkFractureCount; ++i) + { + const NvBlastChunkFractureData& command = chunkFractures[i]; + const uint32_t chunkIndex = command.chunkIndex; + const uint32_t chunkHealthIndex = asset.getContiguousLowerSupportIndex(chunkIndex); + NVBLAST_ASSERT(!isInvalidIndex(chunkHealthIndex)); + if (isInvalidIndex(chunkHealthIndex)) + { + continue; + } + float& health = chunkHealths[chunkHealthIndex]; + if (health > 0.0f && command.health > 0.0f) + { + const uint32_t nodeIndex = asset.getChunkToGraphNodeMap()[chunkIndex]; + if (getGraphNodeCount() > 1 && !isInvalidIndex(nodeIndex)) + { + for (uint32_t adjacentIndex = graphAdjacencyPartition[nodeIndex]; adjacentIndex < graphAdjacencyPartition[nodeIndex + 1]; adjacentIndex++) + { + + const uint32_t bondIndex = graph.findBond(nodeIndex, graphAdjacentNodeIndices[adjacentIndex]); + NVBLAST_ASSERT(!isInvalidIndex(bondIndex)); + if (bondHealths[bondIndex] > 0.0f) + { + bondHealths[bondIndex] = 0.0f; + } + } + getFamilyGraph()->notifyNodeRemoved(getIndex(), nodeIndex, &graph); + } + + health -= command.health; + + const float remainingDamage = -health; + + if (remainingDamage > 0.0f) // node chunk has been damaged beyond its health + { + uint32_t firstSubOffset = getFirstSubsupportChunkIndex(); + fractureSubSupportNoEvents(chunkIndex, firstSubOffset, remainingDamage, subChunkHealths, chunks); + } + } + } +} + + +void Actor::fractureWithEvents(uint32_t chunkFractureCount, const NvBlastChunkFractureData* commands, NvBlastChunkFractureData* events, uint32_t eventsSize, uint32_t* count) +{ + const Asset& asset = *getAsset(); + const SupportGraph& graph = *getGraph(); + const uint32_t* graphAdjacencyPartition = graph.getAdjacencyPartition(); + const uint32_t* graphAdjacentNodeIndices = graph.getAdjacentNodeIndices(); + float* bondHealths = getBondHealths(); + float* chunkHealths = getLowerSupportChunkHealths(); + float* subChunkHealths = getSubsupportChunkHealths(); + const NvBlastChunk* chunks = getChunks(); + + for (uint32_t i = 0; i < chunkFractureCount; ++i) + { + const NvBlastChunkFractureData& command = commands[i]; + const uint32_t chunkIndex = command.chunkIndex; + const uint32_t chunkHealthIndex = asset.getContiguousLowerSupportIndex(chunkIndex); + NVBLAST_ASSERT(!isInvalidIndex(chunkHealthIndex)); + if (isInvalidIndex(chunkHealthIndex)) + { + continue; + } + float& health = chunkHealths[chunkHealthIndex]; + if (health > 0.0f && command.health > 0.0f) + { + const uint32_t nodeIndex = asset.getChunkToGraphNodeMap()[chunkIndex]; + if (getGraphNodeCount() > 1 && !isInvalidIndex(nodeIndex)) + { + for (uint32_t adjacentIndex = graphAdjacencyPartition[nodeIndex]; adjacentIndex < graphAdjacencyPartition[nodeIndex + 1]; adjacentIndex++) + { + const uint32_t bondIndex = graph.findBond(nodeIndex, graphAdjacentNodeIndices[adjacentIndex]); + NVBLAST_ASSERT(!isInvalidIndex(bondIndex)); + if (bondHealths[bondIndex] > 0.0f) + { + bondHealths[bondIndex] = 0.0f; + } + } + getFamilyGraph()->notifyNodeRemoved(getIndex(), nodeIndex, &graph); + } + + health -= command.health; + + if (*count < eventsSize) + { + NvBlastChunkFractureData& outEvent = events[*count]; + outEvent.userdata = chunks[chunkIndex].userData; + outEvent.chunkIndex = chunkIndex; + outEvent.health = health; + } + (*count)++; + + const float remainingDamage = -health; + + if (remainingDamage > 0.0f) // node chunk has been damaged beyond its health + { + uint32_t firstSubOffset = getFirstSubsupportChunkIndex(); + fractureSubSupport(chunkIndex, firstSubOffset, remainingDamage, subChunkHealths, chunks, events, count, eventsSize); + } + } + } +} + + +void Actor::fractureInPlaceEvents(uint32_t chunkFractureCount, NvBlastChunkFractureData* inoutbuffer, uint32_t eventsSize, uint32_t* count) +{ + const Asset& asset = *getAsset(); + const SupportGraph& graph = *getGraph(); + const uint32_t* graphAdjacencyPartition = graph.getAdjacencyPartition(); + const uint32_t* graphAdjacentNodeIndices = graph.getAdjacentNodeIndices(); + float* bondHealths = getBondHealths(); + float* chunkHealths = getLowerSupportChunkHealths(); + float* subChunkHealths = getSubsupportChunkHealths(); + const NvBlastChunk* chunks = getChunks(); + + // + // First level Chunk Fractures + // + + for (uint32_t i = 0; i < chunkFractureCount; ++i) + { + const NvBlastChunkFractureData& command = inoutbuffer[i]; + const uint32_t chunkIndex = command.chunkIndex; + const uint32_t chunkHealthIndex = asset.getContiguousLowerSupportIndex(chunkIndex); + NVBLAST_ASSERT(!isInvalidIndex(chunkHealthIndex)); + if (isInvalidIndex(chunkHealthIndex)) + { + continue; + } + float& health = chunkHealths[chunkHealthIndex]; + if (health > 0.0f && command.health > 0.0f) + { + const uint32_t nodeIndex = asset.getChunkToGraphNodeMap()[chunkIndex]; + if (getGraphNodeCount() > 1 && !isInvalidIndex(nodeIndex)) + { + for (uint32_t adjacentIndex = graphAdjacencyPartition[nodeIndex]; adjacentIndex < graphAdjacencyPartition[nodeIndex + 1]; adjacentIndex++) + { + const uint32_t bondIndex = graph.findBond(nodeIndex, graphAdjacentNodeIndices[adjacentIndex]); + NVBLAST_ASSERT(!isInvalidIndex(bondIndex)); + if (bondHealths[bondIndex] > 0.0f) + { + bondHealths[bondIndex] = 0.0f; + } + } + getFamilyGraph()->notifyNodeRemoved(getIndex(), nodeIndex, &graph); + } + + health -= command.health; + + NvBlastChunkFractureData& outEvent = inoutbuffer[(*count)++]; + outEvent.userdata = chunks[chunkIndex].userData; + outEvent.chunkIndex = chunkIndex; + outEvent.health = health; + } + } + + // + // Hierarchical Chunk Fractures + // + + uint32_t commandedChunkFractures = *count; + + for (uint32_t i = 0; i < commandedChunkFractures; ++i) + { + NvBlastChunkFractureData& event = inoutbuffer[i]; + const uint32_t chunkIndex = event.chunkIndex; + + const float remainingDamage = -event.health; + if (remainingDamage > 0.0f) // node chunk has been damaged beyond its health + { + uint32_t firstSubOffset = getFirstSubsupportChunkIndex(); + fractureSubSupport(chunkIndex, firstSubOffset, remainingDamage, subChunkHealths, chunks, inoutbuffer, count, eventsSize); + } + } +} + + +void Actor::applyFracture(NvBlastFractureBuffers* eventBuffers, const NvBlastFractureBuffers* commands, NvBlastLog logFn, NvBlastTimers* timers) +{ + NVBLAST_CHECK(commands != nullptr, logFn, "Actor::applyFracture: NULL commands pointer input.", return); + NVBLAST_CHECK(isValid(commands), logFn, "Actor::applyFracture: commands memory is NULL but size is > 0.", return); + NVBLAST_CHECK(eventBuffers == nullptr || isValid(eventBuffers), logFn, "NvBlastActorApplyFracture: eventBuffers memory is NULL but size is > 0.", + eventBuffers->bondFractureCount = 0; eventBuffers->chunkFractureCount = 0; return); + +#if NVBLAST_CHECK_PARAMS + if (eventBuffers != nullptr && eventBuffers->bondFractureCount == 0 && eventBuffers->chunkFractureCount == 0) + { + NVBLAST_LOG_WARNING(logFn, "NvBlastActorApplyFracture: eventBuffers do not provide any space."); + return; + } +#endif + +#if NV_PROFILE + Time time; +#else + NV_UNUSED(timers); +#endif + + // + // Chunk Fracture + // + + if (eventBuffers == nullptr || eventBuffers->chunkFractures == nullptr) + { + // immediate hierarchical fracture + fractureNoEvents(commands->chunkFractureCount, commands->chunkFractures); + } + else if (eventBuffers->chunkFractures != commands->chunkFractures) + { + // immediate hierarchical fracture + uint32_t count = 0; + fractureWithEvents(commands->chunkFractureCount, commands->chunkFractures, eventBuffers->chunkFractures, eventBuffers->chunkFractureCount, &count); + + if (count > eventBuffers->chunkFractureCount) + { + NVBLAST_LOG_WARNING(logFn, "NvBlastActorApplyFracture: eventBuffers too small. Chunk events were lost."); + } + else + { + eventBuffers->chunkFractureCount = count; + } + } + else if (eventBuffers->chunkFractures == commands->chunkFractures) + { + // compacting first + uint32_t count = 0; + fractureInPlaceEvents(commands->chunkFractureCount, commands->chunkFractures, eventBuffers->chunkFractureCount, &count); + + if (count > eventBuffers->chunkFractureCount) + { + NVBLAST_LOG_WARNING(logFn, "NvBlastActorApplyFracture: eventBuffers too small. Chunk events were lost."); + } + else + { + eventBuffers->chunkFractureCount = count; + } + } + + // + // Bond Fracture + // + + uint32_t outCount = 0; + const uint32_t eventBufferSize = eventBuffers ? eventBuffers->bondFractureCount : 0; + + NvBlastBond* bonds = getBonds(); + float* bondHealths = getBondHealths(); + for (uint32_t i = 0; i < commands->bondFractureCount; ++i) + { + const NvBlastBondFractureData& frac = commands->bondFractures[i]; + + const uint32_t bondIndex = damageBond(frac.nodeIndex0, frac.nodeIndex1, frac.health); + + if (!isInvalidIndex(bondIndex)) + { + if (eventBuffers && eventBuffers->bondFractures) + { + if (outCount < eventBufferSize) + { + NvBlastBondFractureData& outEvent = eventBuffers->bondFractures[outCount]; + outEvent.userdata = bonds[bondIndex].userData; + outEvent.nodeIndex0 = frac.nodeIndex0; + outEvent.nodeIndex1 = frac.nodeIndex1; + outEvent.health = bondHealths[bondIndex]; + } + } + outCount++; + } + } + + if (eventBuffers && eventBuffers->bondFractures) + { + if (outCount > eventBufferSize) + { + NVBLAST_LOG_WARNING(logFn, "NvBlastActorApplyFracture: eventBuffers too small. Bond events were lost."); + } + else + { + eventBuffers->bondFractureCount = outCount; + } + } + +#if NV_PROFILE + if (timers != nullptr) + { + timers->fracture += time.getElapsedTicks(); + } +#endif + +} + + +size_t Actor::splitRequiredScratch() const +{ + return FamilyGraph::findIslandsRequiredScratch(getGraph()->m_nodeCount); +} + + +uint32_t Actor::split(NvBlastActorSplitEvent* result, uint32_t newActorsMaxCount, void* scratch, NvBlastLog logFn, NvBlastTimers* timers) +{ + NVBLAST_CHECK(result != nullptr, logFn, "Actor::split: NULL result pointer input.", return 0); + NVBLAST_CHECK(newActorsMaxCount > 0 && result->newActors != nullptr, logFn, "NvBlastActorSplit: no space for results provided.", return 0); + NVBLAST_CHECK(scratch != nullptr, logFn, "Actor::split: NULL scratch pointer input.", return 0); + +#if NV_PROFILE + Time time; +#else + NV_UNUSED(timers); +#endif + + Actor** newActors = reinterpret_cast<Actor**>(result->newActors); + + uint32_t actorsCount = 0; + + if (getGraphNodeCount() <= 1) + { + uint32_t chunkHealthIndex = isSingleSupportChunk() ? getIndex() : getFirstVisibleChunkIndex() - getFirstSubsupportChunkIndex() + getGraph()->m_nodeCount; + + float* chunkHealths = getLowerSupportChunkHealths(); + if (chunkHealths[chunkHealthIndex] <= 0.0f) + { + actorsCount = partitionSingleLowerSupportChunk(newActors, newActorsMaxCount, logFn); + + for (uint32_t i = 0; i < actorsCount; ++i) + { + Actor* newActor = newActors[i]; + uint32_t firstVisible = newActor->getFirstVisibleChunkIndex(); + uint32_t firstSub = newActor->getFirstSubsupportChunkIndex(); + uint32_t nodeCount = newActor->getGraph()->m_nodeCount; + uint32_t newActorIndex = newActor->getIndex(); + uint32_t healthIndex = newActor->isSubSupportChunk() ? firstVisible - firstSub + nodeCount : newActorIndex; + + if (chunkHealths[healthIndex] <= 0.0f) + { + uint32_t brittleActors = newActors[i]->partitionSingleLowerSupportChunk(&newActors[actorsCount], newActorsMaxCount - actorsCount, logFn); + actorsCount += brittleActors; + + if (brittleActors > 0) + { + actorsCount--; + newActors[i] = newActors[actorsCount]; + i--; + } + } + } + } + + +#if NV_PROFILE + if (timers != nullptr) + { + timers->partition += time.getElapsedTicks(); + } +#endif + } + else + { + findIslands(scratch); + +#if NV_PROFILE + if (timers != nullptr) + { + timers->island += time.getElapsedTicks(); + } +#endif + + actorsCount = partitionMultipleGraphNodes(newActors, newActorsMaxCount, logFn); + + if (actorsCount > 1) + { +#if NV_PROFILE + if (timers != nullptr) + { + timers->partition += time.getElapsedTicks(); + } +#endif + + // Recalculate visible chunk lists if the graph nodes have been redistributed + for (uint32_t i = 0; i < actorsCount; ++i) + { + newActors[i]->updateVisibleChunksFromGraphNodes(); + } + +#if NV_PROFILE + if (timers != nullptr) + { + timers->visibility += time.getElapsedTicks(); + } +#endif + + for (uint32_t i = 0; i < actorsCount; ++i) + { + Actor* newActor = newActors[i]; + float* chunkHealths = newActor->getLowerSupportChunkHealths(); + uint32_t firstVisible = newActor->getFirstVisibleChunkIndex(); + uint32_t firstSub = newActor->getFirstSubsupportChunkIndex(); + uint32_t nodeCount = newActor->getGraph()->m_nodeCount; + uint32_t newActorIndex = newActor->getIndex(); + uint32_t healthIndex = newActor->isSubSupportChunk() ? firstVisible - firstSub + nodeCount : newActorIndex; + + if (newActors[i]->getGraphNodeCount() <= 1) + { + // this relies on visibility updated, subsupport actors only have m_firstVisibleChunkIndex to identify the chunk + if (chunkHealths[healthIndex] <= 0.0f) + { + uint32_t brittleActors = newActors[i]->partitionSingleLowerSupportChunk(&newActors[actorsCount], newActorsMaxCount - actorsCount, logFn); + actorsCount += brittleActors; + + if (brittleActors > 0) + { + actorsCount--; + newActors[i] = newActors[actorsCount]; + i--; + } + } + } + } + +#if NV_PROFILE + if (timers != nullptr) + { + timers->partition += time.getElapsedTicks(); + } +#endif + } + else + { + actorsCount = 0; + } + } + + result->deletedActor = actorsCount == 0 ? nullptr : this; + + return actorsCount; +} + + +uint32_t Actor::findIslands(void* scratch) +{ + return getFamilyHeader()->getFamilyGraph()->findIslands(getIndex(), scratch, &getAsset()->m_graph); +} + + +uint32_t Actor::partitionMultipleGraphNodes(Actor** newActors, uint32_t newActorsSize, NvBlastLog logFn) +{ + NVBLAST_ASSERT(newActorsSize == 0 || newActors != nullptr); + + // Check for single subsupport chunk, no partitioning + if (m_graphNodeCount <= 1) + { + NVBLAST_LOG_WARNING(logFn, "Nv::Blast::Actor::partitionMultipleGraphNodes: actor is a single lower-support chunk, and cannot be partitioned by this function."); + return 0; + } + + FamilyHeader* header = getFamilyHeader(); + NVBLAST_ASSERT(header != nullptr); // If m_actorEntryDataIndex is valid, this should be too + + // Get the links for the graph nodes + uint32_t* graphNodeIndexLinks = header->getGraphNodeIndexLinks(); + + // Get the graph chunk indices and leaf chunk counts + const Asset* asset = getAsset(); + const uint32_t* graphChunkIndices = asset->m_graph.getChunkIndices(); + const uint32_t* subtreeLeafChunkCounts = asset->getSubtreeLeafChunkCounts(); + + // Distribute graph nodes to new actors + uint32_t newActorCount = 0; + const uint32_t thisActorIndex = getIndex(); + m_leafChunkCount = 0; + const uint32_t* islandIDs = header->getFamilyGraph()->getIslandIds(); + uint32_t lastGraphNodeIndex = invalidIndex<uint32_t>(); + uint32_t nextGraphNodeIndex = invalidIndex<uint32_t>(); + bool overflow = false; + for (uint32_t graphNodeIndex = m_firstGraphNodeIndex; !isInvalidIndex(graphNodeIndex); graphNodeIndex = nextGraphNodeIndex) + { + nextGraphNodeIndex = graphNodeIndexLinks[graphNodeIndex]; + const uint32_t islandID = islandIDs[graphNodeIndex]; + + if (islandID == thisActorIndex) + { + m_leafChunkCount += subtreeLeafChunkCounts[graphChunkIndices[graphNodeIndex]]; + lastGraphNodeIndex = graphNodeIndex; + continue; // Leave the chunk in this actor + } + + // Remove link from this actor + if (isInvalidIndex(lastGraphNodeIndex)) + { + m_firstGraphNodeIndex = nextGraphNodeIndex; + } + else + { + graphNodeIndexLinks[lastGraphNodeIndex] = nextGraphNodeIndex; + } + graphNodeIndexLinks[graphNodeIndex] = invalidIndex<uint32_t>(); + --m_graphNodeCount; + + // See if the chunk had been removed + if (islandID == invalidIndex<uint32_t>()) + { + continue; + } + + // Get new actor if the islandID is valid + Actor* newActor = header->borrowActor(islandID); + + // Check new actor to see if we're adding the first chunk + if (isInvalidIndex(newActor->m_firstGraphNodeIndex)) + { + // See if we can fit it in the output list + if (newActorCount < newActorsSize) + { + newActors[newActorCount++] = newActor; + } + else + { + overflow = true; + } + } + + // Put link in new actor + graphNodeIndexLinks[graphNodeIndex] = newActor->m_firstGraphNodeIndex; + newActor->m_firstGraphNodeIndex = graphNodeIndex; + ++newActor->m_graphNodeCount; + // Add to the actor's leaf chunk count + newActor->m_leafChunkCount += subtreeLeafChunkCounts[graphChunkIndices[graphNodeIndex]]; + } + + if (m_graphNodeCount > 0) + { + // There are still chunks in this actor. See if we can fit this in the output list. + if (newActorCount < newActorsSize) + { + newActors[newActorCount++] = this; + } + else + { + overflow = true; + } + } + else + { + // No more chunks; release this actor. + release(); + } + + if (overflow) + { + NVBLAST_LOG_WARNING(logFn, "Nv::Blast::Actor::partitionMultipleGraphNodes: input newActors array could not hold all actors generated."); + } + + return newActorCount; +} + + +uint32_t Actor::partitionSingleLowerSupportChunk(Actor** newActors, uint32_t newActorsSize, NvBlastLog logFn) +{ + NVBLAST_ASSERT(newActorsSize == 0 || newActors != nullptr); + + // Ensure this is a single subsupport chunk, no partitioning + if (m_graphNodeCount > 1) + { + NVBLAST_LOG_WARNING(logFn, "Nv::Blast::Actor::partitionSingleLowerSupportChunk: actor is not a single lower-support chunk, and cannot be partitioned by this function."); + return 0; + } + + FamilyHeader* header = getFamilyHeader(); + + // The conditional (visible vs. support chunk) is needed because we allow single-child chunk chains + // This makes it possible that an actor with a single support chunk will have a different visible chunk (ancestor of the support chunk) + const uint32_t chunkIndex = m_graphNodeCount == 0 ? m_firstVisibleChunkIndex : getGraph()->getChunkIndices()[m_firstGraphNodeIndex]; + NVBLAST_ASSERT(isInvalidIndex(header->getVisibleChunkIndexLinks()[chunkIndex].m_adj[1])); + + const NvBlastChunk& chunk = header->m_asset->getChunks()[chunkIndex]; + uint32_t childCount = chunk.childIndexStop - chunk.firstChildIndex; + + // Warn if we cannot fit all child chunks in the output list + if (childCount > newActorsSize) + { + NVBLAST_LOG_WARNING(logFn, "Nv::Blast::Actor::partitionSingleLowerSupportChunk: input newActors array will not hold all actors generated."); + childCount = newActorsSize; + } + + // Return if no chunks will be created. + if (childCount == 0) + { + return 0; + } + + // Activate a new actor for every child chunk + const Asset* asset = getAsset(); + const NvBlastChunk* chunks = asset->getChunks(); + const uint32_t firstChildIndex = chunks[chunkIndex].firstChildIndex; + for (uint32_t i = 0; i < childCount; ++i) + { + const uint32_t childIndex = firstChildIndex + i; + NVBLAST_ASSERT(childIndex >= asset->m_firstSubsupportChunkIndex); + const uint32_t actorIndex = asset->m_graph.m_nodeCount + (childIndex - asset->m_firstSubsupportChunkIndex); + NVBLAST_ASSERT(!header->isActorActive(actorIndex)); + newActors[i] = header->borrowActor(actorIndex); + newActors[i]->m_firstVisibleChunkIndex = childIndex; + newActors[i]->m_visibleChunkCount = 1; + newActors[i]->m_leafChunkCount = asset->getSubtreeLeafChunkCounts()[childIndex]; + } + + // Release this actor + release(); + + return childCount; +} + + +void Actor::updateVisibleChunksFromGraphNodes() +{ + // Only apply this to upper-support chunk actors + if (m_graphNodeCount == 0) + { + return; + } + + const Asset* asset = getAsset(); + + const uint32_t thisActorIndex = getIndex(); + + // Get various arrays + FamilyHeader* header = getFamilyHeader(); + Actor* actors = header->getActors(); + IndexDLink<uint32_t>* visibleChunkIndexLinks = header->getVisibleChunkIndexLinks(); + uint32_t* chunkActorIndices = header->getChunkActorIndices(); + const Nv::Blast::SupportGraph& graph = asset->m_graph; + const uint32_t* graphChunkIndices = graph.getChunkIndices(); + const NvBlastChunk* chunks = asset->getChunks(); + const uint32_t upperSupportChunkCount = asset->getUpperSupportChunkCount(); + + // Iterate over all graph nodes and update visible chunk list + const uint32_t* graphNodeIndexLinks = header->getGraphNodeIndexLinks(); + for (uint32_t graphNodeIndex = m_firstGraphNodeIndex; !isInvalidIndex(graphNodeIndex); graphNodeIndex = graphNodeIndexLinks[graphNodeIndex]) + { + updateVisibleChunksFromSupportChunk<Actor>(actors, visibleChunkIndexLinks, chunkActorIndices, thisActorIndex, graphChunkIndices[graphNodeIndex], chunks, upperSupportChunkCount); + } +} + +} // namespace Blast +} // namespace Nv + + +// API implementation + +extern "C" +{ + +NvBlastActor* NvBlastFamilyCreateFirstActor(NvBlastFamily* family, const NvBlastActorDesc* desc, void* scratch, NvBlastLog logFn) +{ + NVBLAST_CHECK(family != nullptr, logFn, "NvBlastFamilyCreateFirstActor: NULL family input.", return nullptr); + NVBLAST_CHECK(desc != nullptr, logFn, "NvBlastFamilyCreateFirstActor: NULL desc input.", return nullptr); + NVBLAST_CHECK(scratch != nullptr, logFn, "NvBlastFamilyCreateFirstActor: NULL scratch input.", return nullptr); + + return Nv::Blast::Actor::create(family, desc, scratch, logFn); +} + + +size_t NvBlastFamilyGetRequiredScratchForCreateFirstActor(const NvBlastFamily* family, NvBlastLog logFn) +{ + NVBLAST_CHECK(family != nullptr, logFn, "NvBlastFamilyGetRequiredScratchForCreateFirstActor: NULL family input.", return 0); + NVBLAST_CHECK(reinterpret_cast<const Nv::Blast::FamilyHeader*>(family)->m_asset != nullptr, + logFn, "NvBlastFamilyGetRequiredScratchForCreateFirstActor: family has NULL asset.", return 0); + + return Nv::Blast::Actor::createRequiredScratch(family); +} + + +bool NvBlastActorDeactivate(NvBlastActor* actor, NvBlastLog logFn) +{ + NVBLAST_CHECK(actor != nullptr, logFn, "NvBlastActorDeactivate: NULL actor input.", return false); + + Nv::Blast::Actor& a = *static_cast<Nv::Blast::Actor*>(actor); + + if (!a.isActive()) + { + NVBLAST_LOG_WARNING(logFn, "NvBlastActorDeactivate: inactive actor input."); + } + + return a.release(); +} + + +uint32_t NvBlastActorGetVisibleChunkCount(const NvBlastActor* actor, NvBlastLog logFn) +{ + NVBLAST_CHECK(actor != nullptr, logFn, "NvBlastActorGetVisibleChunkCount: NULL actor input.", return 0); + + const Nv::Blast::Actor& a = *static_cast<const Nv::Blast::Actor*>(actor); + + if (!a.isActive()) + { + NVBLAST_LOG_ERROR(logFn, "NvBlastActorGetVisibleChunkCount: inactive actor input."); + return 0; + } + + return a.getVisibleChunkCount(); +} + + +uint32_t NvBlastActorGetVisibleChunkIndices(uint32_t* visibleChunkIndices, uint32_t visibleChunkIndicesSize, const NvBlastActor* actor, NvBlastLog logFn) +{ + NVBLAST_CHECK(visibleChunkIndices != nullptr, logFn, "NvBlastActorGetVisibleChunkIndices: NULL visibleChunkIndices pointer input.", return 0); + NVBLAST_CHECK(actor != nullptr, logFn, "NvBlastActorGetVisibleChunkIndices: NULL actor pointer input.", return 0); + + const Nv::Blast::Actor& a = *static_cast<const Nv::Blast::Actor*>(actor); + + if (!a.isActive()) + { + NVBLAST_LOG_ERROR(logFn, "NvBlastActorGetVisibleChunkIndices: inactive actor pointer input."); + return 0; + } + + // Iterate through visible chunk list and write to supplied array + uint32_t indexCount = 0; + for (Nv::Blast::Actor::VisibleChunkIt i = a; indexCount < visibleChunkIndicesSize && (bool)i; ++i) + { + visibleChunkIndices[indexCount++] = (uint32_t)i; + } + + return indexCount; +} + + +uint32_t NvBlastActorGetGraphNodeCount(const NvBlastActor* actor, NvBlastLog logFn) +{ + NVBLAST_CHECK(actor != nullptr, logFn, "NvBlastActorGetGraphNodeCount: NULL actor pointer input.", return 0); + + const Nv::Blast::Actor& a = *static_cast<const Nv::Blast::Actor*>(actor); + + if (!a.isActive()) + { + NVBLAST_LOG_ERROR(logFn, "NvBlastActorGetGraphNodeCount: inactive actor pointer input."); + return 0; + } + + return a.getGraphNodeCount(); +} + + +uint32_t NvBlastActorGetGraphNodeIndices(uint32_t* graphNodeIndices, uint32_t graphNodeIndicesSize, const NvBlastActor* actor, NvBlastLog logFn) +{ + NVBLAST_CHECK(graphNodeIndices != nullptr, logFn, "NvBlastActorGetGraphNodeIndices: NULL graphNodeIndices pointer input.", return 0); + NVBLAST_CHECK(actor != nullptr, logFn, "NvBlastActorGetGraphNodeIndices: NULL actor pointer input.", return 0); + + const Nv::Blast::Actor& a = *static_cast<const Nv::Blast::Actor*>(actor); + + if (!a.isActive()) + { + NVBLAST_LOG_ERROR(logFn, "NvBlastActorGetGraphNodeIndices: inactive actor pointer input."); + return 0; + } + + // Iterate through graph node list and write to supplied array + uint32_t indexCount = 0; + for (Nv::Blast::Actor::GraphNodeIt i = a; indexCount < graphNodeIndicesSize && (bool)i; ++i) + { + graphNodeIndices[indexCount++] = (uint32_t)i; + } + + return indexCount; +} + + +const float* NvBlastActorGetBondHealths(const NvBlastActor* actor, NvBlastLog logFn) +{ + NVBLAST_CHECK(actor != nullptr, logFn, "NvBlastActorGetBondHealths: NULL actor pointer input.", return nullptr); + + const Nv::Blast::Actor& a = *static_cast<const Nv::Blast::Actor*>(actor); + + if (!a.isActive()) + { + NVBLAST_LOG_ERROR(logFn, "NvBlastActorGetBondHealths: inactive actor pointer input."); + return nullptr; + } + + return a.getFamilyHeader()->getBondHealths(); +} + + +NvBlastFamily* NvBlastActorGetFamily(const NvBlastActor* actor, NvBlastLog logFn) +{ + NVBLAST_CHECK(actor != nullptr, logFn, "NvBlastActorGetFamily: NULL actor pointer input.", return nullptr); + + const Nv::Blast::Actor& a = *static_cast<const Nv::Blast::Actor*>(actor); + + if (!a.isActive()) + { + NVBLAST_LOG_ERROR(logFn, "NvBlastActorGetFamily: inactive actor pointer input."); + return nullptr; + } + + return reinterpret_cast<NvBlastFamily*>(a.getFamilyHeader()); +} + + +uint32_t NvBlastActorGetIndex(const NvBlastActor* actor, NvBlastLog logFn) +{ + NVBLAST_CHECK(actor != nullptr, logFn, "NvBlastActorGetIndex: NULL actor pointer input.", return Nv::Blast::invalidIndex<uint32_t>()); + + const Nv::Blast::Actor& a = *static_cast<const Nv::Blast::Actor*>(actor); + + if (!a.isActive()) + { + NVBLAST_LOG_ERROR(logFn, "NvBlastActorGetIndex: actor is not active."); + return Nv::Blast::invalidIndex<uint32_t>(); + } + + return a.getIndex(); +} + + +void NvBlastActorGenerateFracture +( + NvBlastFractureBuffers* commandBuffers, + const NvBlastActor* actor, + const NvBlastDamageProgram program, + const NvBlastProgramParams* programParams, + NvBlastLog logFn, + NvBlastTimers* timers +) +{ + NVBLAST_CHECK(commandBuffers != nullptr, logFn, "NvBlastActorGenerateFracture: NULL commandBuffers pointer input.", return); + NVBLAST_CHECK(actor != nullptr, logFn, "NvBlastActorGenerateFracture: NULL actor pointer input.", return); + + const Nv::Blast::Actor& a = *static_cast<const Nv::Blast::Actor*>(actor); + + if (!a.isActive()) + { + NVBLAST_LOG_ERROR(logFn, "NvBlastActorGenerateFracture: actor is not active."); + commandBuffers->bondFractureCount = 0; + commandBuffers->chunkFractureCount = 0; + return; + } + + a.generateFracture(commandBuffers, program, programParams, logFn, timers); +} + + +void NvBlastActorApplyFracture +( + NvBlastFractureBuffers* eventBuffers, + NvBlastActor* actor, + const NvBlastFractureBuffers* commands, + NvBlastLog logFn, + NvBlastTimers* timers +) +{ + NVBLAST_CHECK(actor != nullptr, logFn, "NvBlastActorApplyFracture: NULL actor pointer input.", return); + NVBLAST_CHECK(commands != nullptr, logFn, "NvBlastActorApplyFracture: NULL commands pointer input.", return); + NVBLAST_CHECK(Nv::Blast::isValid(commands), logFn, "NvBlastActorApplyFracture: commands memory is NULL but size is > 0.", return); + + Nv::Blast::Actor& a = *static_cast<Nv::Blast::Actor*>(actor); + + if (!a.isActive()) + { + NVBLAST_LOG_ERROR(logFn, "NvBlastActorApplyFracture: actor is not active."); + if (eventBuffers != nullptr) + { + eventBuffers->bondFractureCount = 0; + eventBuffers->chunkFractureCount = 0; + } + return; + } + + a.applyFracture(eventBuffers, commands, logFn, timers); +} + + +size_t NvBlastActorGetRequiredScratchForSplit(const NvBlastActor* actor, NvBlastLog logFn) +{ + NVBLAST_CHECK(actor != nullptr, logFn, "NvBlastActorGetRequiredScratchForSplit: NULL actor input.", return 0); + + const Nv::Blast::Actor& a = *static_cast<const Nv::Blast::Actor*>(actor); + + if (!a.isActive()) + { + NVBLAST_LOG_ERROR(logFn, "NvBlastActorGetRequiredScratchForSplit: actor is not active."); + return 0; + } + + return a.splitRequiredScratch(); +} + + +uint32_t NvBlastActorGetMaxActorCountForSplit(const NvBlastActor* actor, NvBlastLog logFn) +{ + NVBLAST_CHECK(actor != nullptr, logFn, "NvBlastActorGetMaxActorCountForSplit: NULL actor input.", return 0); + + const Nv::Blast::Actor& a = *static_cast<const Nv::Blast::Actor*>(actor); + + if (!a.isActive()) + { + NVBLAST_LOG_ERROR(logFn, "NvBlastActorGetMaxActorCountForSplit: actor is not active."); + return 0; + } + + return a.getLeafChunkCount() + 1; // GWD-167 workaround (+1) +} + + +uint32_t NvBlastActorSplit +( + NvBlastActorSplitEvent* result, + NvBlastActor* actor, + uint32_t newActorsMaxCount, + void* scratch, + NvBlastLog logFn, + NvBlastTimers* timers +) +{ + NVBLAST_CHECK(result != nullptr, logFn, "NvBlastActorSplit: NULL result pointer input.", return 0); + NVBLAST_CHECK(newActorsMaxCount > 0 && result->newActors != nullptr, logFn, "NvBlastActorSplit: no space for results provided.", return 0); + NVBLAST_CHECK(actor != nullptr, logFn, "NvBlastActorSplit: NULL actor pointer input.", return 0); + NVBLAST_CHECK(scratch != nullptr, logFn, "NvBlastActorSplit: NULL scratch pointer input.", return 0); + + Nv::Blast::Actor& a = *static_cast<Nv::Blast::Actor*>(actor); + + if (!a.isActive()) + { + NVBLAST_LOG_ERROR(logFn, "NvBlastActorGetIndex: actor is not active."); + return 0; + } + + return a.split(result, newActorsMaxCount, scratch, logFn, timers); +} + + +bool NvBlastActorCanFracture(const NvBlastActor* actor, NvBlastLog logFn) +{ + NVBLAST_CHECK(actor != nullptr, logFn, "NvBlastActorCanFracture: NULL actor input.", return false); + + const Nv::Blast::Actor& a = *static_cast<const Nv::Blast::Actor*>(actor); + + if (!a.isActive()) + { + NVBLAST_LOG_ERROR(logFn, "NvBlastActorCanFracture: actor is not active."); + return false; + } + + bool canFracture = true; + + uint32_t graphNodeCount = a.getGraphNodeCount(); + if (graphNodeCount < 2) + { + uint32_t chunkHealthIndex = graphNodeCount == 0 ? + a.getFirstVisibleChunkIndex() - a.getFirstSubsupportChunkIndex() + a.getGraph()->m_nodeCount : + a.getFirstGraphNodeIndex(); + canFracture = (a.getLowerSupportChunkHealths()[chunkHealthIndex] > 0.0f); + } + + return canFracture; +} + + +} // extern "C" + + +// deprecated API, still used in tests +uint32_t NvBlastActorClosestChunk(const float point[4], const NvBlastActor* actor, NvBlastLog logFn) +{ + const Nv::Blast::Actor& a = *static_cast<const Nv::Blast::Actor*>(actor); + + if (a.isSubSupportChunk()) + { + NVBLAST_LOG_WARNING(logFn, "NvBlastActorClosestChunk: not a graph actor."); + return Nv::Blast::invalidIndex<uint32_t>(); + } + + uint32_t closestNode = Nv::Blast::findNodeByPositionLinked( + point, + a.getFirstGraphNodeIndex(), + a.getFamilyHeader()->getGraphNodeIndexLinks(), + a.getAsset()->m_graph.getAdjacencyPartition(), + a.getAsset()->m_graph.getAdjacentNodeIndices(), + a.getAsset()->m_graph.getAdjacentBondIndices(), + a.getAsset()->getBonds(), + a.getFamilyHeader()->getBondHealths() + ); + + return a.getAsset()->m_graph.getChunkIndices()[closestNode]; +} diff --git a/NvBlast/sdk/lowlevel/source/NvBlastActor.h b/NvBlast/sdk/lowlevel/source/NvBlastActor.h new file mode 100644 index 0000000..42879e7 --- /dev/null +++ b/NvBlast/sdk/lowlevel/source/NvBlastActor.h @@ -0,0 +1,732 @@ +/* +* Copyright (c) 2016-2017, NVIDIA CORPORATION. All rights reserved. +* +* NVIDIA CORPORATION and its licensors retain all intellectual property +* and proprietary rights in and to this software, related documentation +* and any modifications thereto. Any use, reproduction, disclosure or +* distribution of this software and related documentation without an express +* license agreement from NVIDIA CORPORATION is strictly prohibited. +*/ + +#ifndef NVBLASTACTOR_H +#define NVBLASTACTOR_H + + +#include "NvBlastAsset.h" +#include "NvBlastDLink.h" +#include "NvBlastIteratorBase.h" +#include "NvBlastSupportGraph.h" + +#include <cstring> + + +namespace Nv +{ +namespace Blast +{ + +// Forward declarations +class FamilyGraph; +struct FamilyHeader; + +/** +Internal implementation of solver actor. + +These objects are stored within the family in a single array. A pointer to a Actor class will be given +to the user through the NvBlastActor opaque type. +*/ +class Actor : public NvBlastActor +{ + friend struct FamilyHeader; + + friend void updateVisibleChunksFromSupportChunk<>(Actor*, IndexDLink<uint32_t>*, uint32_t*, uint32_t, uint32_t, const NvBlastChunk*, uint32_t); + +public: + Actor() : m_familyOffset(0), m_firstVisibleChunkIndex(UINT32_MAX), m_visibleChunkCount(0), m_firstGraphNodeIndex(UINT32_MAX), m_graphNodeCount(0), m_leafChunkCount(0) {} + + //////// Accessors //////// + + /** + Find the family (see FamilyHeader) that this actor belongs to. + + \return a pointer to the FamilyHeader for this actor. + */ + FamilyHeader* getFamilyHeader() const; + + /** + Utility to get the asset this actor is associated with, through its family. + + \return the asset associated with this actor. + */ + const Asset* getAsset() const; + + /** + Since this object is not deleted (unless the family is deleted), we use m_familyOffset + to determine if the actor is valid, or "active." When no actors in an instance return isActive(), + it should be safe to delete the family. + + \return true iff this actor is valid for use (active). + */ + bool isActive() const; + + /** + Whether or not this actor represents a subsupport chunk. If the actor contains a subsupport chunk, then it can have only that chunk. + + \return true iff this actor contains a chunk which is a descendant of a support chunk. + */ + bool isSubSupportChunk() const; + + /** + Whether or not this actor represents a single support chunk. If the actor contains a single support chunk, it can have no other + chunks associated with it. + + \return true iff this actor contains exactly one support chunk. + */ + bool isSingleSupportChunk() const; + + /** + Utility to calculate actor index. + + \return the index of this actor in the FamilyHeader's getActors() array. + */ + uint32_t getIndex() const; + + /** + The number of visible chunks. This is calculated from updateVisibleChunksFromGraphNodes(). + See also getFirstVisibleChunkIndex. + + \return the number of chunks in the actor's visible chunk index list. + */ + uint32_t getVisibleChunkCount() const; + + /** + Access to visible chunk linked list for this actor. The index returned is that of a link in the FamilyHeader's getVisibleChunkIndexLinks(). + + \return the index of the head of the visible chunk linked list. + */ + uint32_t getFirstVisibleChunkIndex() const; + + /** + The number of graph nodes, corresponding to support chunks, for this actor. + See also getFirstGraphNodeIndex. + + \return the number of graph nodes in the actor's graph node index list. + */ + uint32_t getGraphNodeCount() const; + + /** + The number of leaf chunks for this actor. + + \return number of leaf chunks for this actor. + */ + uint32_t getLeafChunkCount() const; + + /** + Access to graph node linked list for this actor. The index returned is that of a link in the FamilyHeader's getGraphNodeIndexLinks(). + + \return the index of the head of the graph node linked list. + */ + uint32_t getFirstGraphNodeIndex() const; + + /** + Access to the index of the first subsupport chunk. + + \return the index of the first subsupport chunk. + */ + uint32_t getFirstSubsupportChunkIndex() const; + + /** + Access to the support graph. + + \return the support graph associated with this actor. + */ + const SupportGraph* getGraph() const; + + /** + Access the instance graph for islands searching. + + Return the dynamic data generated for the support graph. (See FamilyGraph.) + This is used to store current connectivity information based upon bond and chunk healths, as well as cached intermediate data for faster incremental updates. + */ + FamilyGraph* getFamilyGraph() const; + + /** + Access to the chunks, of type NvBlastChunk. + + \return an array of size m_chunkCount. + */ + NvBlastChunk* getChunks() const; + + /** + Access to the bonds, of type NvBlastBond. + + \return an array of size m_bondCount. + */ + NvBlastBond* getBonds() const; + + /** + Access to the health for each support chunk and subsupport chunk, of type float. + + Use getAsset()->getContiguousLowerSupportIndex() to map lower-support chunk indices into the range of indices valid for this array. + + \return a float array of chunk healths. + */ + float* getLowerSupportChunkHealths() const; + + /** + Access to the start of the subsupport chunk health array. + + \return the array of health values associated with all descendants of support chunks. + */ + float* getSubsupportChunkHealths() const; + + /** + Bond health for the interfaces between two chunks, of type float. Since the bond is shared by two chunks, the same bond health is used for chunk[i] -> chunk[j] as for chunk[j] -> chunk[i]. + + \return the array of healths associated with all bonds in the support graph. + */ + float* getBondHealths() const; + + /** + Graph node index links, of type uint32_t. The successor to index[i] is m_graphNodeIndexLinksOffset[i]. A value of invalidIndex<uint32_t>() indicates no successor. + + getGraphNodeIndexLinks returns an array of size m_asset->m_graphNodeCount. + */ + const uint32_t* getGraphNodeIndexLinks() const; + + + //////// Iterators //////// + + /** + Visible chunk iterator. Usage: + + Given a solver actor a, + + for (Actor::VisibleChunkIt i = a; (bool)i; ++i) + { + uint32_t visibleChunkIndex = (uint32_t)i; + + // visibleChunkIndex references the asset index list + } + + */ + class VisibleChunkIt : public DListIt<uint32_t> + { + public: + /** Constructed from an actor. */ + VisibleChunkIt(const Actor& actor); + }; + + /** + Graph node iterator. Usage: + + Given a solver actor a, + + for (Actor::GraphNodeIt i = a; (bool)i; ++i) + { + uint32_t graphNodeIndex = (uint32_t)i; + + // graphNodeIndex references the asset's graph node index list + } + + */ + class GraphNodeIt : public LListIt<uint32_t> + { + public: + /** Constructed from an actor. */ + GraphNodeIt(const Actor& actor); + }; + + + //////// Operations //////// + + /** + Create an actor from a descriptor (creates a family). This actor will represent an unfractured instance of the asset. + The asset must be in a valid state, for example each chunk hierarchy in it must contain at least one support chunk (a single + support chunk in a hierarchy corresponds to the root chunk). This will always be the case for assets created by NvBlastCreateAsset. + + \param[in] family Family in which to create a new actor. The family must be valid and have no other actors in it. (See createFamily.) + \param[in] desc Actor initialization data, must be a valid pointer. + \param[in] scratch User-supplied scratch memory of size createRequiredScratch(desc) bytes. + \param[in] logFn User-supplied message function (see NvBlastLog definition). May be NULL. + + \return the new actor if the input is valid (by the conditions described above), NULL otherwise. + */ + static Actor* create(NvBlastFamily* family, const NvBlastActorDesc* desc, void* scratch, NvBlastLog logFn); + + /** + Returns the size of the scratch space (in bytes) required to be passed into the create function, based upon + the family that will be passed to the create function. + + \param[in] family The family being instanced. + + \return the number of bytes required. + */ + static size_t createRequiredScratch(const NvBlastFamily* family); + + /** + Deserialize a single Actor from a buffer. An actor family must given, into which + the actor will be inserted if it is compatible. That is, it must not share any chunks or internal + IDs with the actors already present in the block. + + \param[in] family Family in which to deserialize the actor. + \param[in] buffer Buffer containing the serialized actor data. + \param[in] logFn User-supplied message function (see NvBlastLog definition). May be NULL. + + \return the deserialized actor if successful, NULL otherwise. + */ + static Actor* deserialize(NvBlastFamily* family, const void* buffer, NvBlastLog logFn); + + /** + Serialize actor into single-actor buffer. + + \param[out] buffer User-supplied buffer, must be at least of size given by NvBlastActorGetSerializationSize(actor). + \param[in] bufferSize The size of the user-supplied buffer. The buffer size must be less than 4GB. If NvBlastActorGetSerializationSize(actor) >= 4GB, this actor cannot be serialized with this method. + \param[in] logFn User-supplied message function (see NvBlastLog definition). May be NULL. + + \return the number of bytes written to the buffer, or 0 if there is an error (such as an under-sized buffer). + */ + uint32_t serialize(void* buffer, uint32_t bufferSize, NvBlastLog logFn) const; + + /** + Calculate the space required to serialize this actor. + + \param[in] logFn User-supplied message function (see NvBlastLog definition). May be NULL. + + \return the required buffer size in bytes. + */ + uint32_t serializationRequiredStorage(NvBlastLog logFn) const; + + /** + Release this actor's association with a family, if any. This actor should be considered deleted + after this function is called. + + \return true if release was successful (actor was active). + */ + bool release(); + + + //////// Damage and fracturing methods //////// + + /** + Damage bond between two chunks by health amount (instance graph also will be notified in case bond is broken after). + */ + uint32_t damageBond(uint32_t nodeIndex0, uint32_t nodeIndex1, float healthDamage); + + /** + TODO: document + */ + void damageBond(uint32_t nodeIndex0, uint32_t nodeIndex1, uint32_t bondIndex, float healthDamage); + + /** + TODO: document + */ + uint32_t damageBond(const NvBlastBondFractureData& cmd); + + /** + See NvBlastActorGenerateFracture + */ + void generateFracture(NvBlastFractureBuffers* commandBuffers, const NvBlastDamageProgram& program, const NvBlastProgramParams* programParams, NvBlastLog logFn, NvBlastTimers* timers) const; + + /** + Hierarchically distribute damage to child chunks. + + \param chunkIndex asset chunk index to hierarchically damage + \param suboffset index of the first sub-support health + \param healthDamage damage strength to apply + \param chunkHealths instance chunk healths + \param chunks asset chunk collection + */ + void fractureSubSupportNoEvents(uint32_t chunkIndex, uint32_t suboffset, float healthDamage, float* chunkHealths, const NvBlastChunk* chunks); + + /** + Hierarchically distribute damage to child chunks, recording a fracture event for each health damage applied. + + If outBuffer is too small, events are dropped but the chunks are still damaged. + + \param chunkIndex asset chunk index to hierarchically damage + \param suboffset index of the first sub-support health + \param healthDamage damage strength to apply + \param chunkHealths instance chunk healths + \param chunks asset chunk collection + \param outBuffer target buffer for fracture events + \param currentIndex current position in outBuffer - returns the number of damaged chunks + \param maxCount capacity of outBuffer + */ + void fractureSubSupport(uint32_t chunkIndex, uint32_t suboffset, float healthDamage, float* chunkHealths, const NvBlastChunk* chunks, NvBlastChunkFractureData* outBuffer, uint32_t* currentIndex, const uint32_t maxCount); + + /** + Apply chunk fracture commands hierarchically. + + \param chunkFractureCount number of chunk fracture commands to apply + \param chunkFractures array of chunk fracture commands + */ + void fractureNoEvents(uint32_t chunkFractureCount, const NvBlastChunkFractureData* chunkFractures); + + /** + Apply chunk fracture commands hierarchically, recording a fracture event for each health damage applied. + + If events array is too small, events are dropped but the chunks are still damaged. + + \param chunkFractureCount number of chunk fracture commands to apply + \param commands array of chunk fracture commands + \param events target buffer for fracture events + \param eventsSize number of available entries in 'events' + \param count returns the number of damaged chunks + */ + void fractureWithEvents(uint32_t chunkFractureCount, const NvBlastChunkFractureData* commands, NvBlastChunkFractureData* events, uint32_t eventsSize, uint32_t* count); + + /** + Apply chunk fracture commands hierarchically, recording a fracture event for each health damage applied. + + In-Place version: fracture commands are replaced by fracture events. + + If inoutbuffer array is too small, events are dropped but the chunks are still damaged. + + \param chunkFractureCount number of chunk fracture commands to apply + \param inoutbuffer array of chunk fracture commands to be replaced by events + \param eventsSize number of available entries in inoutbuffer + \param count returns the number of damaged chunks + */ + void fractureInPlaceEvents(uint32_t chunkFractureCount, NvBlastChunkFractureData* inoutbuffer, uint32_t eventsSize, uint32_t* count); + + /** + See NvBlastActorApplyFracture + */ + void applyFracture(NvBlastFractureBuffers* eventBuffers, const NvBlastFractureBuffers* commands, NvBlastLog logFn, NvBlastTimers* timers); + + /** + The scratch space required to call the findIslands function, or the split function, in bytes. + + \return the number of bytes required. + */ + size_t splitRequiredScratch() const; + + /** + See NvBlastActorSplit + */ + uint32_t split(NvBlastActorSplitEvent* result, uint32_t newActorsMaxCount, void* scratch, NvBlastLog logFn, NvBlastTimers* timers); + + /** + Perform islands search. Bonds which are broken when their health values drop to zero (or below) may lead + to new islands of chunks which need to be split into new actors. This function labels all nodes in the instance + graph (see FamilyGraph) with a unique index per island that may be used as actor indices for new islands. + + \param[in] scratch User-supplied scratch memory of size splitRequiredScratch(). + + \return the number of new islands found. + */ + uint32_t findIslands(void* scratch); + + /** + Partition this actor into smaller pieces. + + If this actor represents a single support or subsupport chunk, then after this operation + this actor will released if child chunks are created (see Return value), and its pointer no longer valid for use (unless it appears in the newActors list). + + This function will not split a leaf chunk actor. In that case, the actor is not destroyed and this function returns 0. + + \param[in] newActors user-supplied array of actor pointers to hold the actors generated from this partitioning. + This array must be of size equal to the number of leaf chunks in the asset, to guarantee + that all actors are reported. (See AssetDataHeader::m_leafChunkCount.) + \param[in] newActorsSize The size of the user-supplied newActors array. + \param[in] logFn User-supplied message function (see NvBlastLog definition). May be NULL. + + \return the number of new actors created. If greater than newActorsSize, some actors are not reported in the newActors array. + */ + uint32_t partition(Actor** newActors, uint32_t newActorsSize, NvBlastLog logFn); + + /** + Recalculate the visible chunk list for this actor based upon it graph node list (does not modify subsupport chunk actors) + */ + void updateVisibleChunksFromGraphNodes(); + + /** + Partition this actor into smaller pieces if it is a single lower-support chunk actor. Use this function on single support or sub-support chunks. + + After this operation, if successful (child chunks created, see Return value), this actor will released, and its pointer no longer valid for use. + + This function will not split a leaf chunk actor. In that case, the actor is not destroyed and this function returns 0. + + \param[in] newActors User-supplied array of actor pointers to hold the actors generated from this partitioning. Note: this actor will be released. + This array must be of size equal to the lower-support chunk's child count, to guarantee that all actors are reported. + \param[in] newActorsSize The size of the user-supplied newActors array. + \param[in] logFn User-supplied message function (see NvBlastLog definition). May be NULL. + + \return the number of new actors created. + */ + uint32_t partitionSingleLowerSupportChunk(Actor** newActors, uint32_t newActorsSize, NvBlastLog logFn); + + /** + Partition this actor into smaller pieces. Use this function if this actor contains more than one support chunk. + + After this operation, if successful, this actor will released, and its pointer no longer valid for use (unless it appears in the newActors list). + + \param[in] newActors User-supplied array of actor pointers to hold the actors generated from this partitioning. Note: this actor will not be released, + but will hold a subset of the graph nodes that it had before the function was called. + This array must be of size equal to the number of graph nodes in the asset, to guarantee + that all actors are reported. + \param[in] newActorsSize The size of the user-supplied newActors array. + \param[in] logFn User-supplied message function (see NvBlastLog definition). May be NULL. + + \return the number of new actors created. + */ + uint32_t partitionMultipleGraphNodes(Actor** newActors, uint32_t newActorsSize, NvBlastLog logFn); + +private: + + //////// Data //////// + + /** + Offset to block of memory which holds the data associated with all actors in this actor's lineage. + This offset is positive. The block address is this object's pointer _minus_ the m_familyOffset. + This value is initialized to 0, which denotes an invalid actor. Actors should be obtained through + the FamilyHeader::borrowActor API, which will create a valid offset, and + the FamilyHeader::returnActor API, which will zero the offset. + */ + uint32_t m_familyOffset; + + /** + The index of the head of a doubly-linked list of visible chunk indices. If m_firstVisibleChunkIndex == invalidIndex<uint32_t>(), + then there are no visible chunks. + */ + uint32_t m_firstVisibleChunkIndex; + + /** + The number of elements in the visible chunk list. + */ + uint32_t m_visibleChunkCount; + + /** + The index of the head of a singly-linked list of graph node indices. If m_firstGraphNodeIndex == invalidIndex<uint32_t>(), + then there are no graph nodes. + */ + uint32_t m_firstGraphNodeIndex; + + /** + The number of elements in the graph node list. + */ + uint32_t m_graphNodeCount; + + /** + The number of leaf chunks in this actor. + */ + uint32_t m_leafChunkCount; +}; + +} // namespace Blast +} // namespace Nv + + +#include "NvBlastFamily.h" + + +namespace Nv +{ +namespace Blast +{ + +//////// Actor inline methods //////// + +NV_INLINE FamilyHeader* Actor::getFamilyHeader() const +{ + NVBLAST_ASSERT(isActive()); + return (FamilyHeader*)((uintptr_t)this - (uintptr_t)m_familyOffset); +} + + +NV_INLINE const Asset* Actor::getAsset() const +{ + return getFamilyHeader()->m_asset; +} + + +NV_INLINE bool Actor::isActive() const +{ + return m_familyOffset != 0; +} + + +NV_INLINE bool Actor::isSubSupportChunk() const +{ + return m_graphNodeCount == 0; +} + + +NV_INLINE bool Actor::isSingleSupportChunk() const +{ + return m_graphNodeCount == 1; +} + + +NV_INLINE uint32_t Actor::getIndex() const +{ + NVBLAST_ASSERT(isActive()); + const FamilyHeader* header = getFamilyHeader(); + NVBLAST_ASSERT(header != nullptr); + const size_t index = this - header->getActors(); + NVBLAST_ASSERT(index <= UINT32_MAX); + return (uint32_t)index; +} + + +NV_INLINE uint32_t Actor::getVisibleChunkCount() const +{ + return m_visibleChunkCount; +} + + +NV_INLINE uint32_t Actor::getFirstVisibleChunkIndex() const +{ + return m_firstVisibleChunkIndex; +} + + +NV_INLINE uint32_t Actor::getGraphNodeCount() const +{ + return m_graphNodeCount; +} + + +NV_INLINE uint32_t Actor::getLeafChunkCount() const +{ + return m_leafChunkCount; +} + + +NV_INLINE uint32_t Actor::getFirstGraphNodeIndex() const +{ + return m_firstGraphNodeIndex; +} + +NV_INLINE uint32_t Actor::getFirstSubsupportChunkIndex() const +{ + return getAsset()->m_firstSubsupportChunkIndex; +} + +NV_INLINE const SupportGraph* Actor::getGraph() const +{ + return &getAsset()->m_graph; +} + +NV_INLINE FamilyGraph* Actor::getFamilyGraph() const +{ + return getFamilyHeader()->getFamilyGraph(); +} + +NV_INLINE NvBlastChunk* Actor::getChunks() const +{ + return getAsset()->getChunks(); +} + +NV_INLINE NvBlastBond* Actor::getBonds() const +{ + return getAsset()->getBonds(); +} + +NV_INLINE float* Actor::getLowerSupportChunkHealths() const +{ + return getFamilyHeader()->getLowerSupportChunkHealths(); +} + +NV_INLINE float* Actor::getSubsupportChunkHealths() const +{ + return getFamilyHeader()->getSubsupportChunkHealths(); +} + +NV_INLINE float* Actor::getBondHealths() const +{ + return getFamilyHeader()->getBondHealths(); +} + +NV_INLINE const uint32_t* Actor::getGraphNodeIndexLinks() const +{ + return getFamilyHeader()->getGraphNodeIndexLinks(); +} + + +NV_INLINE bool Actor::release() +{ + // Do nothing if this actor is not currently active. + if (!isActive()) + { + return false; + } + + FamilyHeader* header = getFamilyHeader(); + + // Clear the graph node list + uint32_t* graphNodeIndexLinks = getFamilyHeader()->getGraphNodeIndexLinks(); + while (!isInvalidIndex(m_firstGraphNodeIndex)) + { + const uint32_t graphNodeIndex = m_firstGraphNodeIndex; + m_firstGraphNodeIndex = graphNodeIndexLinks[m_firstGraphNodeIndex]; + graphNodeIndexLinks[graphNodeIndex] = invalidIndex<uint32_t>(); + --m_graphNodeCount; + } + NVBLAST_ASSERT(m_graphNodeCount == 0); + + const Asset* asset = getAsset(); + + // Clear the visible chunk list + IndexDLink<uint32_t>* visibleChunkIndexLinks = header->getVisibleChunkIndexLinks(); + uint32_t* chunkActorIndices = header->getChunkActorIndices(); + while (!isInvalidIndex(m_firstVisibleChunkIndex)) + { + // Descendants of the visible actor may be accessed again if the actor is deserialized. Clear subtree. + for (Asset::DepthFirstIt i(*asset, m_firstVisibleChunkIndex, true); (bool)i; ++i) + { + chunkActorIndices[(uint32_t)i] = invalidIndex<uint32_t>(); + } + IndexDList<uint32_t>().removeListHead(m_firstVisibleChunkIndex, visibleChunkIndexLinks); + --m_visibleChunkCount; + } + NVBLAST_ASSERT(m_visibleChunkCount == 0); + + // Clear the leaf chunk count + m_leafChunkCount = 0; + + // This invalidates the actor and decrements the reference count + header->returnActor(*this); + + return true; +} + + +NV_INLINE uint32_t Actor::partition(Actor** newActors, uint32_t newActorsSize, NvBlastLog logFn) +{ + NVBLAST_CHECK(newActorsSize == 0 || newActors != nullptr, logFn, "Nv::Blast::Actor::partition: NULL newActors pointer array input with non-zero newActorCount.", return 0); + + // Call one of two partition functions depending on the actor's support status + return m_graphNodeCount <= 1 ? + partitionSingleLowerSupportChunk(newActors, newActorsSize, logFn) : // This actor will partition into subsupport chunks + partitionMultipleGraphNodes(newActors, newActorsSize, logFn); // This actor will partition into support chunks +} + + +//////// Actor::VisibleChunkIt inline methods //////// + +NV_INLINE Actor::VisibleChunkIt::VisibleChunkIt(const Actor& actor) : DListIt<uint32_t>(actor.m_firstVisibleChunkIndex, actor.getFamilyHeader()->getVisibleChunkIndexLinks()) +{ +} + + +//////// Actor::GraphNodeIt inline methods //////// + +NV_INLINE Actor::GraphNodeIt::GraphNodeIt(const Actor& actor) : LListIt<uint32_t>(actor.m_firstGraphNodeIndex, actor.getFamilyHeader()->getGraphNodeIndexLinks()) +{ +} + +} // namespace Blast +} // namespace Nv + + +/** +Returns the closest chunk asset index for a supported actor. +Helper functions still used in tests. +Has become obsolete with introduction of chunkMap and its inverse. +*/ +uint32_t NvBlastActorClosestChunk(const float point[4], const NvBlastActor* actor, NvBlastLog logFn); + + +#endif // ifndef NVBLASTACTOR_H diff --git a/NvBlast/sdk/lowlevel/source/NvBlastActorSerializationBlock.cpp b/NvBlast/sdk/lowlevel/source/NvBlastActorSerializationBlock.cpp new file mode 100644 index 0000000..e496a69 --- /dev/null +++ b/NvBlast/sdk/lowlevel/source/NvBlastActorSerializationBlock.cpp @@ -0,0 +1,575 @@ +/* +* Copyright (c) 2016-2017, NVIDIA CORPORATION. All rights reserved. +* +* NVIDIA CORPORATION and its licensors retain all intellectual property +* and proprietary rights in and to this software, related documentation +* and any modifications thereto. Any use, reproduction, disclosure or +* distribution of this software and related documentation without an express +* license agreement from NVIDIA CORPORATION is strictly prohibited. +*/ + + +#include "NvBlastActor.h" +#include "NvBlastActorSerializationBlock.h" +#include "NvBlastFamilyGraph.h" + +#include <algorithm> + + +namespace Nv +{ +namespace Blast +{ + +//////// Actor static methods for serialization //////// + +Actor* Actor::deserialize(NvBlastFamily* family, const void* buffer, NvBlastLog logFn) +{ + NVBLAST_CHECK(family != nullptr, logFn, "Actor::deserialize: NULL family pointer input.", return nullptr); + + const ActorSerializationHeader* serHeader = reinterpret_cast<const ActorSerializationHeader*>(buffer); + if (serHeader->m_formatVersion != ActorSerializationFormat::Current) + { + NVBLAST_LOG_ERROR(logFn, "Actor::deserialize: wrong data format. Serialization data must be converted to current version."); + return nullptr; + } + + FamilyHeader* header = reinterpret_cast<FamilyHeader*>(family); + const Asset* asset = header->m_asset; + const Nv::Blast::SupportGraph& graph = asset->m_graph; + const uint32_t* graphChunkIndices = graph.getChunkIndices(); + const uint32_t* graphAdjacencyPartition = graph.getAdjacencyPartition(); + const uint32_t* graphAdjacentNodeIndices = graph.getAdjacentNodeIndices(); + const uint32_t* graphAdjacentBondIndices = graph.getAdjacentBondIndices(); + + Actor* actor = nullptr; + const uint32_t actorIndex = serHeader->m_index; + + if (serHeader->m_index < header->getActorBufferSize()) + { + if (!header->getActors()[actorIndex].isActive()) + { + actor = header->borrowActor(serHeader->m_index); + } + } + + if (actor == nullptr) + { + NVBLAST_LOG_ERROR(logFn, "Actor::deserialize: invalid actor index in serialized data. Actor not created."); + return nullptr; + } + + // Commonly used data + uint32_t* chunkActorIndices = header->getChunkActorIndices(); + FamilyGraph* familyGraph = header->getFamilyGraph(); + +#if NVBLAST_CHECK_PARAMS + { + const uint32_t* serVisibleChunkIndices = serHeader->getVisibleChunkIndices(); + for (uint32_t i = 0; i < serHeader->m_visibleChunkCount; ++i) + { + const uint32_t visibleChunkIndex = serVisibleChunkIndices[i]; + if (!isInvalidIndex(chunkActorIndices[visibleChunkIndex])) + { + NVBLAST_LOG_ERROR(logFn, "Actor::deserialize: visible chunk already has an actor in family. Actor not created."); + header->returnActor(*actor); + return nullptr; + } + } + } +#endif + + // Visible chunk indices and chunk actor indices + { + // Add visible chunks, set chunk subtree ownership + const uint32_t* serVisibleChunkIndices = serHeader->getVisibleChunkIndices(); + IndexDLink<uint32_t>* visibleChunkIndexLinks = header->getVisibleChunkIndexLinks(); + for (uint32_t i = serHeader->m_visibleChunkCount; i--;) // Reverse-order, so the resulting linked list is in the original order + { + const uint32_t visibleChunkIndex = serVisibleChunkIndices[i]; + NVBLAST_ASSERT(isInvalidIndex(visibleChunkIndexLinks[visibleChunkIndex].m_adj[0]) && isInvalidIndex(visibleChunkIndexLinks[visibleChunkIndex].m_adj[1])); + IndexDList<uint32_t>().insertListHead(actor->m_firstVisibleChunkIndex, visibleChunkIndexLinks, visibleChunkIndex); + for (Asset::DepthFirstIt j(*asset, visibleChunkIndex, true); (bool)j; ++j) + { + NVBLAST_ASSERT(isInvalidIndex(chunkActorIndices[(uint32_t)j])); + chunkActorIndices[(uint32_t)j] = actorIndex; + } + } + actor->m_visibleChunkCount = serHeader->m_visibleChunkCount; + } + + // Graph node indices, leaf chunk count, and and island IDs + { + // Add graph nodes + const uint32_t* serGraphNodeIndices = serHeader->getGraphNodeIndices(); + uint32_t* graphNodeIndexLinks = header->getGraphNodeIndexLinks(); + uint32_t* islandIDs = familyGraph->getIslandIds(); + for (uint32_t i = serHeader->m_graphNodeCount; i--;) // Reverse-order, so the resulting linked list is in the original order + { + const uint32_t graphNodeIndex = serGraphNodeIndices[i]; + NVBLAST_ASSERT(isInvalidIndex(graphNodeIndexLinks[graphNodeIndex])); + graphNodeIndexLinks[graphNodeIndex] = actor->m_firstGraphNodeIndex; + actor->m_firstGraphNodeIndex = graphNodeIndex; + islandIDs[graphNodeIndex] = actorIndex; + } + actor->m_graphNodeCount = serHeader->m_graphNodeCount; + actor->m_leafChunkCount = serHeader->m_leafChunkCount; + } + + // Lower support chunk healths + { + const float* serLowerSupportChunkHealths = serHeader->getLowerSupportChunkHealths(); + float* subsupportHealths = header->getSubsupportChunkHealths(); + const uint32_t subsupportChunkCount = asset->getUpperSupportChunkCount(); + if (actor->m_graphNodeCount > 0) + { + uint32_t serLowerSupportChunkCount = 0; + float* graphNodeHealths = header->getLowerSupportChunkHealths(); + for (Nv::Blast::Actor::GraphNodeIt i = *actor; (bool)i; ++i) + { + const uint32_t graphNodeIndex = (uint32_t)i; + graphNodeHealths[graphNodeIndex] = serLowerSupportChunkHealths[serLowerSupportChunkCount++]; + const uint32_t supportChunkIndex = graphChunkIndices[graphNodeIndex]; + Asset::DepthFirstIt j(*asset, supportChunkIndex); + NVBLAST_ASSERT((bool)j); + ++j; // Skip first (support) chunk, it's already been handled + for (; (bool)j; ++j) + { + subsupportHealths[(uint32_t)j] = serLowerSupportChunkHealths[serLowerSupportChunkCount++]; + } + } + } + else // Single subsupport chunk + if (!isInvalidIndex(actor->m_firstVisibleChunkIndex)) + { + NVBLAST_ASSERT(actor->m_firstVisibleChunkIndex >= subsupportChunkCount); + subsupportHealths[actor->m_firstVisibleChunkIndex - subsupportChunkCount] = *serLowerSupportChunkHealths; + } + } + + // Bond healths + uint32_t serBondCount = 0; + { + const float* serBondHealths = serHeader->getBondHealths(); + float* bondHealths = header->getBondHealths(); + for (Nv::Blast::Actor::GraphNodeIt i = *actor; (bool)i; ++i) + { + const uint32_t graphNodeIndex = (uint32_t)i; + for (uint32_t adjacentIndex = graphAdjacencyPartition[graphNodeIndex]; adjacentIndex < graphAdjacencyPartition[graphNodeIndex + 1]; ++adjacentIndex) + { + const uint32_t adjacentNodeIndex = graphAdjacentNodeIndices[adjacentIndex]; + if (adjacentNodeIndex > graphNodeIndex) // So as not to double-count + { + // Only count if the adjacent node belongs to this actor + const uint32_t adjacentChunkIndex = graphChunkIndices[adjacentNodeIndex]; + if (chunkActorIndices[adjacentChunkIndex] == actorIndex) + { + const uint32_t adjacentBondIndex = graphAdjacentBondIndices[adjacentIndex]; + bondHealths[adjacentBondIndex] = serBondHealths[serBondCount++]; + } + } + } + } + } + + // Fast routes + { + const uint32_t* serFastRoute = serHeader->getFastRoute(); + uint32_t* fastRoute = header->getFamilyGraph()->getFastRoute(); + for (Nv::Blast::Actor::GraphNodeIt i = *actor; (bool)i; ++i) + { + fastRoute[(uint32_t)i] = *serFastRoute++; + } + } + + // Hop counts + { + const uint32_t* serHopCounts = serHeader->getHopCounts(); + uint32_t* hopCounts = header->getFamilyGraph()->getHopCounts(); + for (Nv::Blast::Actor::GraphNodeIt i = *actor; (bool)i; ++i) + { + hopCounts[(uint32_t)i] = *serHopCounts++; + } + } + + // Edge removed array + if (serBondCount > 0) + { + uint32_t serBondIndex = 0; + const FixedBoolArray* serEdgeRemovedArray = serHeader->getEdgeRemovedArray(); + FixedBoolArray* edgeRemovedArray = familyGraph->getIsEdgeRemoved(); + for (Nv::Blast::Actor::GraphNodeIt i = *actor; (bool)i; ++i) + { + const uint32_t graphNodeIndex = (uint32_t)i; + for (uint32_t adjacentIndex = graphAdjacencyPartition[graphNodeIndex]; adjacentIndex < graphAdjacencyPartition[graphNodeIndex + 1]; ++adjacentIndex) + { + const uint32_t adjacentNodeIndex = graphAdjacentNodeIndices[adjacentIndex]; + if (adjacentNodeIndex > graphNodeIndex) // So as not to double-count + { + // Only count if the adjacent node belongs to this actor + const uint32_t adjacentChunkIndex = graphChunkIndices[adjacentNodeIndex]; + if (chunkActorIndices[adjacentChunkIndex] == actorIndex) + { + if (!serEdgeRemovedArray->test(serBondIndex)) + { + const uint32_t adjacentBondIndex = graphAdjacentBondIndices[adjacentIndex]; + edgeRemovedArray->reset(adjacentBondIndex); + } + ++serBondIndex; + } + } + } + } + } + + return actor; +} + + +//////// Actor member methods for serialization //////// + +uint32_t Actor::serialize(void* buffer, uint32_t bufferSize, NvBlastLog logFn) const +{ + // Set up pointers and such + const Asset* asset = getAsset(); + const Nv::Blast::SupportGraph& graph = asset->m_graph; + const uint32_t* graphChunkIndices = graph.getChunkIndices(); + const uint32_t* graphAdjacencyPartition = graph.getAdjacencyPartition(); + const uint32_t* graphAdjacentNodeIndices = graph.getAdjacentNodeIndices(); + const uint32_t* graphAdjacentBondIndices = graph.getAdjacentBondIndices(); + const FamilyHeader* header = getFamilyHeader(); + const uint32_t* chunkActorIndices = header->getChunkActorIndices(); + const uint32_t thisActorIndex = getIndex(); + + // Make sure there are no dirty nodes + if (m_graphNodeCount) + { + const uint32_t* firstDirtyNodeIndices = header->getFamilyGraph()->getFirstDirtyNodeIndices(); + if (!isInvalidIndex(firstDirtyNodeIndices[thisActorIndex])) + { + NVBLAST_LOG_ERROR(logFn, "Nv::Blast::Actor::serialize: instance graph has dirty nodes. Call Nv::Blast::Actor::findIslands before serializing."); + return 0; + } + } + + uint64_t offset = 0; + + // Header + ActorSerializationHeader* serHeader = reinterpret_cast<ActorSerializationHeader*>(buffer); + offset = align16(sizeof(ActorSerializationHeader)); + if (offset > bufferSize) + { + return 0; // Buffer size insufficient + } + serHeader->m_formatVersion = ActorSerializationFormat::Current; + serHeader->m_size = 0; // Will be updated below + serHeader->m_index = thisActorIndex; + serHeader->m_visibleChunkCount = m_visibleChunkCount; + serHeader->m_graphNodeCount = m_graphNodeCount; + serHeader->m_leafChunkCount = m_leafChunkCount; + + // Visible chunk indices + { + serHeader->m_visibleChunkIndicesOffset = (uint32_t)offset; + offset = align16(offset + m_visibleChunkCount*sizeof(uint32_t)); + if (offset > bufferSize) + { + NVBLAST_LOG_ERROR(logFn, "Nv::Blast::Actor::Actor::serialize: buffer size exceeded."); + return 0; // Buffer size insufficient + } + uint32_t* serVisibleChunkIndices = serHeader->getVisibleChunkIndices(); + uint32_t serVisibleChunkCount = 0; + for (Nv::Blast::Actor::VisibleChunkIt i = *this; (bool)i; ++i) + { + NVBLAST_ASSERT(serVisibleChunkCount < m_visibleChunkCount); + serVisibleChunkIndices[serVisibleChunkCount++] = (uint32_t)i; + } + NVBLAST_ASSERT(serVisibleChunkCount == m_visibleChunkCount); + } + + // Graph node indices + { + serHeader->m_graphNodeIndicesOffset = (uint32_t)offset; + offset = align16(offset + m_graphNodeCount*sizeof(uint32_t)); + if (offset > bufferSize) + { + NVBLAST_LOG_ERROR(logFn, "Nv::Blast::Actor::serialize: buffer size exceeded."); + return 0; // Buffer size insufficient + } + uint32_t* serGraphNodeIndices = serHeader->getGraphNodeIndices(); + uint32_t serGraphNodeCount = 0; + for (Nv::Blast::Actor::GraphNodeIt i = *this; (bool)i; ++i) + { + NVBLAST_ASSERT(serGraphNodeCount < m_graphNodeCount); + serGraphNodeIndices[serGraphNodeCount++] = (uint32_t)i; + } + NVBLAST_ASSERT(serGraphNodeCount == m_graphNodeCount); + } + + // Lower support chunk healths + { + serHeader->m_lowerSupportChunkHealthsOffset = (uint32_t)offset; + float* serLowerSupportChunkHealths = serHeader->getLowerSupportChunkHealths(); + const float* subsupportHealths = header->getSubsupportChunkHealths(); + const uint32_t subsupportChunkCount = asset->getUpperSupportChunkCount(); + if (m_graphNodeCount > 0) + { + uint32_t serLowerSupportChunkCount = 0; + const float* graphNodeHealths = header->getLowerSupportChunkHealths(); + for (Nv::Blast::Actor::GraphNodeIt i = *this; (bool)i; ++i) + { + const uint32_t graphNodeIndex = (uint32_t)i; + serLowerSupportChunkHealths[serLowerSupportChunkCount++] = graphNodeHealths[graphNodeIndex]; + offset += sizeof(float); + const uint32_t supportChunkIndex = graphChunkIndices[graphNodeIndex]; + Asset::DepthFirstIt j(*asset, supportChunkIndex); + NVBLAST_ASSERT((bool)j); + ++j; // Skip first (support) chunk, it's already been handled + for (; (bool)j; ++j) + { + if (offset >= bufferSize) + { + NVBLAST_LOG_ERROR(logFn, "Nv::Blast::Actor::serialize: buffer size exceeded."); + return 0; // Buffer size insufficient + } + serLowerSupportChunkHealths[serLowerSupportChunkCount++] = subsupportHealths[(uint32_t)j - subsupportChunkCount]; + offset += sizeof(float); + } + } + } + else // Single subsupport chunk + if (!isInvalidIndex(m_firstVisibleChunkIndex)) + { + NVBLAST_ASSERT(m_firstVisibleChunkIndex >= subsupportChunkCount); + if (offset >= bufferSize) + { + NVBLAST_LOG_ERROR(logFn, "Nv::Blast::Actor::serialize: buffer size exceeded."); + return 0; // Buffer size insufficient + } + *serLowerSupportChunkHealths = subsupportHealths[m_firstVisibleChunkIndex - subsupportChunkCount]; + offset += sizeof(float); + } + } + offset = align16(offset); + + // Bond healths + uint32_t serBondCount = 0; + { + serHeader->m_bondHealthsOffset = (uint32_t)offset; + float* serBondHealths = serHeader->getBondHealths(); + const float* bondHealths = header->getBondHealths(); + for (Nv::Blast::Actor::GraphNodeIt i = *this; (bool)i; ++i) + { + const uint32_t graphNodeIndex = (uint32_t)i; + for (uint32_t adjacentIndex = graphAdjacencyPartition[graphNodeIndex]; adjacentIndex < graphAdjacencyPartition[graphNodeIndex + 1]; ++adjacentIndex) + { + const uint32_t adjacentNodeIndex = graphAdjacentNodeIndices[adjacentIndex]; + if (adjacentNodeIndex > graphNodeIndex) // So as not to double-count + { + // Only count if the adjacent node belongs to this actor + const uint32_t adjacentChunkIndex = graphChunkIndices[adjacentNodeIndex]; + if (chunkActorIndices[adjacentChunkIndex] == thisActorIndex) + { + if (offset >= bufferSize) + { + NVBLAST_LOG_ERROR(logFn, "Nv::Blast::Actor::serialize: buffer size exceeded."); + return 0; // Buffer size insufficient + } + const uint32_t adjacentBondIndex = graphAdjacentBondIndices[adjacentIndex]; + serBondHealths[serBondCount++] = bondHealths[adjacentBondIndex]; + offset += sizeof(float); + } + } + } + } + } + offset = align16(offset); + + // Fast routes + { + serHeader->m_fastRouteOffset = (uint32_t)offset; + offset = align16(offset + m_graphNodeCount*sizeof(uint32_t)); + if (offset > bufferSize) + { + NVBLAST_LOG_ERROR(logFn, "Nv::Blast::Actor::serialize: buffer size exceeded."); + return 0; // Buffer size insufficient + } + uint32_t* serFastRoute = serHeader->getFastRoute(); + const uint32_t* fastRoute = header->getFamilyGraph()->getFastRoute(); + for (Nv::Blast::Actor::GraphNodeIt i = *this; (bool)i; ++i) + { + *serFastRoute++ = fastRoute[(uint32_t)i]; + } + } + + // Hop counts + { + serHeader->m_hopCountsOffset = (uint32_t)offset; + offset = align16(offset + m_graphNodeCount*sizeof(uint32_t)); + if (offset > bufferSize) + { + NVBLAST_LOG_ERROR(logFn, "Nv::Blast::Actor::serialize: buffer size exceeded."); + return 0; // Buffer size insufficient + } + uint32_t* serHopCounts = serHeader->getHopCounts(); + const uint32_t* hopCounts = header->getFamilyGraph()->getHopCounts(); + for (Nv::Blast::Actor::GraphNodeIt i = *this; (bool)i; ++i) + { + *serHopCounts++ = hopCounts[(uint32_t)i]; + } + } + + // Edge removed array + if (serBondCount > 0) + { + serHeader->m_edgeRemovedArrayOffset = (uint32_t)offset; + offset = align16(offset + FixedBoolArray::requiredMemorySize(serBondCount)); + if (offset > bufferSize) + { + NVBLAST_LOG_ERROR(logFn, "Nv::Blast::Actor::serialize: buffer size exceeded."); + return 0; // Buffer size insufficient + } + uint32_t serBondIndex = 0; + FixedBoolArray* serEdgeRemovedArray = serHeader->getEdgeRemovedArray(); + new (serEdgeRemovedArray)FixedBoolArray(serBondCount); + serEdgeRemovedArray->fill(); // Reset bits as we find bonds + const FixedBoolArray* edgeRemovedArray = header->getFamilyGraph()->getIsEdgeRemoved(); + for (Nv::Blast::Actor::GraphNodeIt i = *this; (bool)i; ++i) + { + const uint32_t graphNodeIndex = (uint32_t)i; + for (uint32_t adjacentIndex = graphAdjacencyPartition[graphNodeIndex]; adjacentIndex < graphAdjacencyPartition[graphNodeIndex + 1]; ++adjacentIndex) + { + const uint32_t adjacentNodeIndex = graphAdjacentNodeIndices[adjacentIndex]; + if (adjacentNodeIndex > graphNodeIndex) // So as not to double-count + { + // Only count if the adjacent node belongs to this actor + const uint32_t adjacentChunkIndex = graphChunkIndices[adjacentNodeIndex]; + if (chunkActorIndices[adjacentChunkIndex] == thisActorIndex) + { + const uint32_t adjacentBondIndex = graphAdjacentBondIndices[adjacentIndex]; + if (!edgeRemovedArray->test(adjacentBondIndex)) + { + serEdgeRemovedArray->reset(serBondIndex); + } + ++serBondIndex; + } + } + } + } + } + + // Finally record size + serHeader->m_size = static_cast<uint32_t>(offset); + + return serHeader->m_size; +} + + +uint32_t Actor::serializationRequiredStorage(NvBlastLog logFn) const +{ + const Asset* asset = getAsset(); + const Nv::Blast::SupportGraph& graph = asset->m_graph; + const uint32_t* graphChunkIndices = graph.getChunkIndices(); + const uint32_t* graphAdjacencyPartition = graph.getAdjacencyPartition(); + const uint32_t* graphAdjacentNodeIndices = graph.getAdjacentNodeIndices(); + const uint32_t* graphNodeIndexLinks = getFamilyHeader()->getGraphNodeIndexLinks(); + const uint32_t* chunkActorIndices = getFamilyHeader()->getChunkActorIndices(); + const uint32_t thisActorIndex = getIndex(); + + // Lower-support chunk count and bond counts for this actor need to be calculated. Iterate over all support chunks to count these. + uint32_t lowerSupportChunkCount = 0; + uint32_t bondCount = 0; + if (m_graphNodeCount > 0) + { + for (uint32_t graphNodeIndex = m_firstGraphNodeIndex; !isInvalidIndex(graphNodeIndex); graphNodeIndex = graphNodeIndexLinks[graphNodeIndex]) + { + // Update bond count + const uint32_t supportChunkIndex = graphChunkIndices[graphNodeIndex]; + for (uint32_t adjacentIndex = graphAdjacencyPartition[graphNodeIndex]; adjacentIndex < graphAdjacencyPartition[graphNodeIndex + 1]; ++adjacentIndex) + { + const uint32_t adjacentNodeIndex = graphAdjacentNodeIndices[adjacentIndex]; + if (adjacentNodeIndex > graphNodeIndex) // So as not to double-count + { + // Only count if the adjacent node belongs to this actor + const uint32_t adjacentChunkIndex = graphChunkIndices[adjacentNodeIndex]; + if (chunkActorIndices[adjacentChunkIndex] == thisActorIndex) + { + ++bondCount; + } + } + } + + // Update lower-support chunk count + for (Asset::DepthFirstIt i(*asset, supportChunkIndex); (bool)i; ++i) + { + ++lowerSupportChunkCount; + } + } + } + else // Subsupport chunk + { + ++lowerSupportChunkCount; + } + + const uint64_t dataSize = getActorSerializationSize(m_visibleChunkCount, lowerSupportChunkCount, m_graphNodeCount, bondCount); + + if (dataSize > UINT32_MAX) + { + NVBLAST_LOG_WARNING(logFn, "Nv::Blast::Actor::serializationRequiredStorage: Serialization block size exceeds 4GB. Returning 0.\n"); + return 0; + } + + return static_cast<uint32_t>(dataSize); +} + +} // namespace Blast +} // namespace Nv + + +// API implementation + +extern "C" +{ + +uint32_t NvBlastActorGetSerializationSize(const NvBlastActor* actor, NvBlastLog logFn) +{ + NVBLAST_CHECK(actor != nullptr, logFn, "NvBlastActorGetSerializationSize: NULL actor pointer input.", return 0); + + const Nv::Blast::Actor& a = *static_cast<const Nv::Blast::Actor*>(actor); + + if (!a.isActive()) + { + NVBLAST_LOG_ERROR(logFn, "NvBlastActorGetSerializationSize: inactive actor pointer input."); + return 0; + } + + return a.serializationRequiredStorage(logFn); +} + + +uint32_t NvBlastActorSerialize(void* buffer, uint32_t bufferSize, const NvBlastActor* actor, NvBlastLog logFn) +{ + NVBLAST_CHECK(buffer != nullptr, logFn, "NvBlastActorSerialize: NULL buffer pointer input.", return 0); + NVBLAST_CHECK(actor != nullptr, logFn, "NvBlastActorSerialize: NULL actor pointer input.", return 0); + + const Nv::Blast::Actor& a = *static_cast<const Nv::Blast::Actor*>(actor); + + if (!a.isActive()) + { + NVBLAST_LOG_ERROR(logFn, "NvBlastActorSerialize: inactive actor pointer input."); + return 0; + } + + return a.serialize(buffer, bufferSize, logFn); +} + + +NvBlastActor* NvBlastFamilyDeserializeActor(NvBlastFamily* family, const void* buffer, NvBlastLog logFn) +{ + NVBLAST_CHECK(family != nullptr, logFn, "NvBlastFamilyDeserializeActor: NULL family input. No actor deserialized.", return nullptr); + NVBLAST_CHECK(buffer != nullptr, logFn, "NvBlastFamilyDeserializeActor: NULL buffer pointer input. No actor deserialized.", return nullptr); + + return Nv::Blast::Actor::deserialize(family, buffer, logFn); +} + +} // extern "C" diff --git a/NvBlast/sdk/lowlevel/source/NvBlastActorSerializationBlock.h b/NvBlast/sdk/lowlevel/source/NvBlastActorSerializationBlock.h new file mode 100644 index 0000000..1388a74 --- /dev/null +++ b/NvBlast/sdk/lowlevel/source/NvBlastActorSerializationBlock.h @@ -0,0 +1,151 @@ +/* +* Copyright (c) 2016-2017, NVIDIA CORPORATION. All rights reserved. +* +* NVIDIA CORPORATION and its licensors retain all intellectual property +* and proprietary rights in and to this software, related documentation +* and any modifications thereto. Any use, reproduction, disclosure or +* distribution of this software and related documentation without an express +* license agreement from NVIDIA CORPORATION is strictly prohibited. +*/ + +#ifndef NVBLASTACTORSERIALIZATIONBLOCK_H +#define NVBLASTACTORSERIALIZATIONBLOCK_H + + +#include "NvBlastFixedBoolArray.h" + + +namespace Nv +{ +namespace Blast +{ + +/** +Struct-enum which keeps track of the actor serialization format. +*/ +struct ActorSerializationFormat +{ + enum Version + { + /** Initial version */ + Initial, + + // New formats must come before Count. They should be given descriptive names with more information in comments. + + /** The number of serialization formats. */ + Count, + + /** The current version. This should always be Count-1 */ + Current = Count - 1 + }; +}; + + +/** +Data header at the beginning of a NvBlastActor serialization block + +The block address may be cast to a valid ActorSerializationHeader pointer. + +Serialization state is only valid if partition has been called since the last call to findIslands(). +*/ +struct ActorSerializationHeader +{ + /** + A number which is incremented every time the data layout changes. + */ + uint32_t m_formatVersion; + + /** + The size of the serialization block, including this header. + + Memory sizes are restricted to 32-bit representable values. + */ + uint32_t m_size; + + /** + The index of the actor within its family. + */ + uint32_t m_index; + + /** + The number of elements in the visible chunk indices list. + */ + uint32_t m_visibleChunkCount; + + /** + The number of elements in the graph node indices list. + */ + uint32_t m_graphNodeCount; + + /** + The number of leaf chunks in this actor. + */ + uint32_t m_leafChunkCount; + + /** + Visible chunk indices, of type uint32_t. + */ + NvBlastBlockArrayData(uint32_t, m_visibleChunkIndicesOffset, getVisibleChunkIndices, m_visibleChunkCount); + + /** + Graph node indices, of type uint32_t. + */ + NvBlastBlockArrayData(uint32_t, m_graphNodeIndicesOffset, getGraphNodeIndices, m_graphNodeCount); + + /** + Healths for lower support chunks in this actor, in breadth-first order from the support chunks associated with the graph nodes. Type float. + */ + NvBlastBlockData(float, m_lowerSupportChunkHealthsOffset, getLowerSupportChunkHealths); + + /** + Healths for bonds associated with support chunks in this actor, in order of graph adjacency from associated graph nodes, i < j only. Type float. + */ + NvBlastBlockData(float, m_bondHealthsOffset, getBondHealths); + + /** + Fast route in instance graph calculated for each graph node in this actor, of type uint32_t. + */ + NvBlastBlockArrayData(uint32_t, m_fastRouteOffset, getFastRoute, m_graphNodeCount); + + /** + Hop counts in instance graph calculated for each graph node in this actor, of type uint32_t. + */ + NvBlastBlockArrayData(uint32_t, m_hopCountsOffset, getHopCounts, m_graphNodeCount); + + /** + "Edge removed" bits for bonds associated with support chunks in this actor, in order of graph adjacency from associated graph nodes, i < j only. Type FixedBoolArray. + */ + NvBlastBlockData(FixedBoolArray, m_edgeRemovedArrayOffset, getEdgeRemovedArray); +}; + + +//////// Global functions //////// + +/** +A buffer size sufficient to serialize an actor with a given visible chunk count, lower support chunk count, graph node count, and bond count. + +\param[in] visibleChunkCount The number of visible chunks +\param[in] lowerSupportChunkCount The number of lower-support chunks in the asset. +\param[in] graphNodeCount The number of graph nodes in the asset. +\param[in] bondCount The number of graph bonds in the asset. + +\return the required buffer size in bytes. +*/ +NV_INLINE size_t getActorSerializationSize(uint32_t visibleChunkCount, uint32_t lowerSupportChunkCount, uint32_t graphNodeCount, uint32_t bondCount) +{ + // Family offsets + const size_t visibleChunkIndicesOffset = align16(sizeof(ActorSerializationHeader)); // size = visibleChunkCount*sizeof(uint32_t) + const size_t graphNodeIndicesOffset = align16(visibleChunkIndicesOffset + visibleChunkCount*sizeof(uint32_t)); // size = graphNodeCount*sizeof(uint32_t) + const size_t lowerSupportHealthsOffset = align16(graphNodeIndicesOffset + graphNodeCount*sizeof(uint32_t)); // size = lowerSupportChunkCount*sizeof(float) + const size_t bondHealthsOffset = align16(lowerSupportHealthsOffset + lowerSupportChunkCount*sizeof(float)); // size = bondCount*sizeof(float) + const size_t fastRouteOffset = align16(bondHealthsOffset + bondCount*sizeof(float)); // size = graphNodeCount*sizeof(uint32_t) + const size_t hopCountsOffset = align16(fastRouteOffset + graphNodeCount*sizeof(uint32_t)); // size = graphNodeCount*sizeof(uint32_t) + const size_t edgeRemovedArrayOffset = align16(hopCountsOffset + graphNodeCount*sizeof(uint32_t)); // size = 0 or FixedBoolArray::requiredMemorySize(bondCount) + return align16(edgeRemovedArrayOffset + (bondCount == 0 ? 0 : FixedBoolArray::requiredMemorySize(bondCount))); +} + +} // namespace Blast +} // namespace Nv + + +#endif // ifndef NVBLASTACTORSERIALIZATIONBLOCK_H diff --git a/NvBlast/sdk/lowlevel/source/NvBlastAsset.cpp b/NvBlast/sdk/lowlevel/source/NvBlastAsset.cpp new file mode 100644 index 0000000..29fc6b0 --- /dev/null +++ b/NvBlast/sdk/lowlevel/source/NvBlastAsset.cpp @@ -0,0 +1,931 @@ +/* +* Copyright (c) 2016-2017, NVIDIA CORPORATION. All rights reserved. +* +* NVIDIA CORPORATION and its licensors retain all intellectual property +* and proprietary rights in and to this software, related documentation +* and any modifications thereto. Any use, reproduction, disclosure or +* distribution of this software and related documentation without an express +* license agreement from NVIDIA CORPORATION is strictly prohibited. +*/ + +#include "NvBlastAssert.h" +#include "NvBlastAsset.h" +#include "NvBlastActor.h" +#include "NvBlastMath.h" +#include "NvBlastPreprocessorInternal.h" +#include "NvBlastIndexFns.h" +#include "NvBlastActorSerializationBlock.h" +#include "NvBlastMemory.h" + +#include <algorithm> + + +namespace Nv +{ +namespace Blast +{ + + +//////// Local helper functions //////// + + +/** +Helper function to validate the input parameters for NvBlastCreateAsset. See NvBlastCreateAsset for parameter definitions. +*/ +static bool solverAssetBuildValidateInput(void* mem, const NvBlastAssetDesc* desc, void* scratch, NvBlastLog logFn) +{ + if (mem == nullptr) + { + NVBLAST_LOG_ERROR(logFn, "AssetBuildValidateInput: NULL mem pointer input."); + return false; + } + + if (desc == nullptr) + { + NVBLAST_LOG_ERROR(logFn, "AssetBuildValidateInput: NULL desc pointer input."); + return false; + } + + if (desc->chunkCount == 0) + { + NVBLAST_LOG_ERROR(logFn, "AssetBuildValidateInput: Zero chunk count not allowed."); + return false; + } + + if (desc->chunkDescs == nullptr) + { + NVBLAST_LOG_ERROR(logFn, "AssetBuildValidateInput: NULL chunkDescs pointer input."); + return false; + } + + if (desc->bondCount != 0 && desc->bondDescs == nullptr) + { + NVBLAST_LOG_ERROR(logFn, "AssetBuildValidateInput: bondCount non-zero but NULL bondDescs pointer input."); + return false; + } + + if (scratch == nullptr) + { + NVBLAST_LOG_ERROR(logFn, "AssetBuildValidateInput: NULL scratch pointer input."); + return false; + } + + return true; +} + + +struct AssetDataOffsets +{ + size_t m_chunks; + size_t m_bonds; + size_t m_subtreeLeafChunkCounts; + size_t m_supportChunkIndices; + size_t m_chunkToGraphNodeMap; + size_t m_graphAdjacencyPartition; + size_t m_graphAdjacentNodeIndices; + size_t m_graphAdjacentBondIndices; +}; + + +static size_t createAssetDataOffsets(AssetDataOffsets& offsets, uint32_t chunkCount, uint32_t graphNodeCount, uint32_t bondCount) +{ + NvBlastCreateOffsetStart(sizeof(Asset)); + NvBlastCreateOffsetAlign16(offsets.m_chunks, chunkCount * sizeof(NvBlastChunk)); + NvBlastCreateOffsetAlign16(offsets.m_bonds, bondCount * sizeof(NvBlastBond)); + NvBlastCreateOffsetAlign16(offsets.m_subtreeLeafChunkCounts, chunkCount * sizeof(uint32_t)); + NvBlastCreateOffsetAlign16(offsets.m_supportChunkIndices, graphNodeCount * sizeof(uint32_t)); + NvBlastCreateOffsetAlign16(offsets.m_chunkToGraphNodeMap, chunkCount * sizeof(uint32_t)); + NvBlastCreateOffsetAlign16(offsets.m_graphAdjacencyPartition, (graphNodeCount + 1) * sizeof(uint32_t)); + NvBlastCreateOffsetAlign16(offsets.m_graphAdjacentNodeIndices, (2 * bondCount) * sizeof(uint32_t)); + NvBlastCreateOffsetAlign16(offsets.m_graphAdjacentBondIndices, (2 * bondCount) * sizeof(uint32_t)); + return NvBlastCreateOffsetEndAlign16(); +} + + +Asset* initializeAsset(void* mem, NvBlastID id, uint32_t chunkCount, uint32_t graphNodeCount, uint32_t leafChunkCount, uint32_t firstSubsupportChunkIndex, uint32_t bondCount, NvBlastLog logFn) +{ + // Data offsets + AssetDataOffsets offsets; + const size_t dataSize = createAssetDataOffsets(offsets, chunkCount, graphNodeCount, bondCount); + + // Restricting our data size to < 4GB so that we may use uint32_t offsets + if (dataSize > (size_t)UINT32_MAX) + { + NVBLAST_LOG_ERROR(logFn, "Nv::Blast::allocateAsset: Asset data size will exceed 4GB. Instance not created.\n"); + return nullptr; + } + + // Zero memory and cast to Asset + Asset* asset = reinterpret_cast<Asset*>(memset(mem, 0, dataSize)); + + // Fill in fields + const size_t graphOffset = NV_OFFSET_OF(Asset, m_graph); + asset->m_header.dataType = NvBlastDataBlock::AssetDataBlock; + asset->m_header.formatVersion = NvBlastAssetDataFormat::Current; + asset->m_header.size = (uint32_t)dataSize; + asset->m_header.reserved = 0; + asset->m_ID = id; + asset->m_chunkCount = chunkCount; + asset->m_graph.m_nodeCount = graphNodeCount; + asset->m_graph.m_chunkIndicesOffset = (uint32_t)(offsets.m_supportChunkIndices - graphOffset); + asset->m_graph.m_adjacencyPartitionOffset = (uint32_t)(offsets.m_graphAdjacencyPartition - graphOffset); + asset->m_graph.m_adjacentNodeIndicesOffset = (uint32_t)(offsets.m_graphAdjacentNodeIndices - graphOffset); + asset->m_graph.m_adjacentBondIndicesOffset = (uint32_t)(offsets.m_graphAdjacentBondIndices - graphOffset); + asset->m_leafChunkCount = leafChunkCount; + asset->m_firstSubsupportChunkIndex = firstSubsupportChunkIndex; + asset->m_bondCount = bondCount; + asset->m_chunksOffset = (uint32_t)offsets.m_chunks; + asset->m_bondsOffset = (uint32_t)offsets.m_bonds; + asset->m_subtreeLeafChunkCountsOffset = (uint32_t)offsets.m_subtreeLeafChunkCounts; + asset->m_chunkToGraphNodeMapOffset = (uint32_t)offsets.m_chunkToGraphNodeMap; + + // Ensure Bonds remain aligned + NV_COMPILE_TIME_ASSERT((sizeof(NvBlastBond) & 0xf) == 0); + + // Ensure Bonds are aligned - note, this requires that the block be aligned + NVBLAST_ASSERT((uintptr_t(asset->getBonds()) & 0xf) == 0); + + return asset; +} + + +/** +Tests for a loop in a digraph starting at a given graph vertex. + +Using the implied digraph given by the chunkDescs' parentChunkIndex fields, the graph is walked from the chunk descriptor chunkDescs[chunkIndex], +to determine if that walk leads to a loop. + +Input: +chunkDescs - the chunk descriptors +chunkIndex - the index of the starting chunk descriptor + +Return: +true if a loop is found, false otherwise. +*/ +NV_INLINE bool testForLoop(const NvBlastChunkDesc* chunkDescs, uint32_t chunkIndex) +{ + NVBLAST_ASSERT(!isInvalidIndex(chunkIndex)); + + uint32_t chunkIndex1 = chunkDescs[chunkIndex].parentChunkIndex; + if (isInvalidIndex(chunkIndex1)) + { + return false; + } + + uint32_t chunkIndex2 = chunkDescs[chunkIndex1].parentChunkIndex; + if (isInvalidIndex(chunkIndex2)) + { + return false; + } + + do + { + // advance index 1 + chunkIndex1 = chunkDescs[chunkIndex1].parentChunkIndex; // No need to check for termination here. index 2 would find it first. + + // advance index 2 twice and check for incidence with index 1 as well as termination + if ((chunkIndex2 = chunkDescs[chunkIndex2].parentChunkIndex) == chunkIndex1) + { + return true; + } + if (isInvalidIndex(chunkIndex2)) + { + return false; + } + if ((chunkIndex2 = chunkDescs[chunkIndex2].parentChunkIndex) == chunkIndex1) + { + return true; + } + } while (!isInvalidIndex(chunkIndex2)); + + return false; +} + + +/** +Tests a set of chunk descriptors to see if the implied hierarchy describes valid trees. + +A single tree implies that only one of the chunkDescs has an invalid (invalidIndex<uint32_t>()) parentChunkIndex, and all other +chunks are descendents of that chunk. Passed set of chunk is checked to contain one or more single trees. + +Input: +chunkCount - the number of chunk descriptors +chunkDescs - an array of chunk descriptors of length chunkCount +logFn - message function (see NvBlastLog definition). + +Return: +true if the descriptors imply a valid trees, false otherwise. +*/ +static bool testForValidTrees(uint32_t chunkCount, const NvBlastChunkDesc* chunkDescs, NvBlastLog logFn) +{ + for (uint32_t i = 0; i < chunkCount; ++i) + { + // Ensure there are no loops + if (testForLoop(chunkDescs, i)) + { + NVBLAST_LOG_WARNING(logFn, "testForValidTrees: loop found. Asset will not be created."); + return false; + } + } + + return true; +} + + +/** +Struct to hold chunk indices and bond index for sorting + +Utility struct used by NvBlastCreateAsset in order to arrange bond data in a lookup table, and also to easily identify redundant input. +*/ +struct BondSortData +{ + BondSortData(uint32_t c0, uint32_t c1, uint32_t b) : m_c0(c0), m_c1(c1), m_b(b) {} + + uint32_t m_c0; + uint32_t m_c1; + uint32_t m_b; +}; + + +/** +Functional class for sorting a list of BondSortData +*/ +class BondsOrdered +{ +public: + bool operator () (const BondSortData& bond0, const BondSortData& bond1) const + { + return (bond0.m_c0 != bond1.m_c0) ? (bond0.m_c0 < bond1.m_c0) : (bond0.m_c1 < bond1.m_c1); + } +}; + + +//////// Asset static functions //////// + +size_t Asset::getMemorySize(const NvBlastAssetDesc* desc) +{ + NVBLAST_ASSERT(desc != nullptr); + + // Count graph nodes + uint32_t graphNodeCount = 0; + for (uint32_t i = 0; i < desc->chunkCount; ++i) + { + graphNodeCount += (uint32_t)((desc->chunkDescs[i].flags & NvBlastChunkDesc::SupportFlag) != 0); + } + + AssetDataOffsets offsets; + return createAssetDataOffsets(offsets, desc->chunkCount, graphNodeCount, desc->bondCount); +} + + +size_t Asset::createRequiredScratch(const NvBlastAssetDesc* desc) +{ +#if NVBLAST_CHECK_PARAMS + if (desc == nullptr) + { + NVBLAST_ALWAYS_ASSERT(); + return 0; + } +#endif + + // Aligned and padded + return 16 + + align16(desc->chunkCount*sizeof(char)) + + align16(desc->chunkCount*sizeof(uint32_t)) + + align16(2 * desc->bondCount*sizeof(Nv::Blast::BondSortData)) + + align16(desc->bondCount*sizeof(uint32_t)); +} + + +Asset* Asset::create(void* mem, const NvBlastAssetDesc* desc, void* scratch, NvBlastLog logFn) +{ +#if NVBLAST_CHECK_PARAMS + if (!solverAssetBuildValidateInput(mem, desc, scratch, logFn)) + { + return nullptr; + } +#else + NV_UNUSED(solverAssetBuildValidateInput); +#endif + + NVBLAST_CHECK((reinterpret_cast<uintptr_t>(mem) & 0xF) == 0, logFn, "NvBlastCreateAsset: mem pointer not 16-byte aligned.", return nullptr); + + // Make sure we have valid trees before proceeding + if (!testForValidTrees(desc->chunkCount, desc->chunkDescs, logFn)) + { + return nullptr; + } + + scratch = (void*)align16((size_t)scratch); // Bump to 16-byte alignment (see padding in NvBlastGetRequiredScratchForCreateAsset) + + // reserve chunkAnnotation on scratch + char* chunkAnnotation = reinterpret_cast<char*>(scratch); scratch = Nv::Blast::pointerOffset(scratch, align16(desc->chunkCount)); + + // test for coverage, chunkAnnotation will be filled there. + uint32_t leafChunkCount; + uint32_t supportChunkCount; + if (!ensureExactSupportCoverage(supportChunkCount, leafChunkCount, chunkAnnotation, desc->chunkCount, const_cast<NvBlastChunkDesc*>(desc->chunkDescs), true, logFn)) + { + return nullptr; + } + + // test for valid chunk order + if (!testForValidChunkOrder(desc->chunkCount, desc->chunkDescs, chunkAnnotation, scratch)) + { + NVBLAST_LOG_ERROR(logFn, "NvBlastCreateAsset: chunks order is invalid. Asset will not be created. Use Asset helper functions such as NvBlastBuildAssetDescChunkReorderMap to fix descriptor order."); + return nullptr; + } + + // Find first subsupport chunk + uint32_t firstSubsupportChunkIndex = desc->chunkCount; // Set value to chunk count if no subsupport chunks are found + for (uint32_t i = 0; i < desc->chunkCount; ++i) + { + if ((chunkAnnotation[i] & ChunkAnnotation::UpperSupport) == 0) + { + firstSubsupportChunkIndex = i; + break; + } + } + + // Create map from global indices to graph node indices and initialize to invalid values + uint32_t* graphNodeIndexMap = (uint32_t*)scratch; scratch = Nv::Blast::pointerOffset(scratch, align16(desc->chunkCount * sizeof(uint32_t))); + memset(graphNodeIndexMap, 0xFF, desc->chunkCount*sizeof(uint32_t)); + + // Fill graphNodeIndexMap + uint32_t graphNodeCount = 0; + for (uint32_t i = 0; i < desc->chunkCount; ++i) + { + if ((chunkAnnotation[i] & ChunkAnnotation::Support) != 0) + { + graphNodeIndexMap[i] = graphNodeCount++; + } + } + NVBLAST_ASSERT(graphNodeCount == supportChunkCount); + + // Scratch array for bond sorting, of size 2*desc->bondCount + Nv::Blast::BondSortData* bondSortArray = (Nv::Blast::BondSortData*)scratch; scratch = Nv::Blast::pointerOffset(scratch, align16(2 * desc->bondCount*sizeof(Nv::Blast::BondSortData))); + + // Bond remapping array of size desc->bondCount + uint32_t* bondMap = (uint32_t*)scratch; + memset(bondMap, 0xFF, desc->bondCount*sizeof(uint32_t)); + + // Eliminate bad or redundant bonds, finding actual bond count + uint32_t bondCount = 0; + if (desc->bondCount > 0) + { + // Check for duplicates from input data as well as non-support chunk indices. All such bonds must be removed. + bool invalidFound = false; + bool duplicateFound = false; + bool nonSupportFound = false; + + // Construct temp array of chunk index pairs and bond indices. This array is symmetrized to hold the reversed chunk indices as well. + uint32_t bondSortArraySize = 0; + Nv::Blast::BondSortData* t = bondSortArray; + for (uint32_t i = 0; i < desc->bondCount; ++i) + { + const NvBlastBondDesc& bondDesc = desc->bondDescs[i]; + const uint32_t chunkIndex0 = bondDesc.chunkIndices[0]; + const uint32_t chunkIndex1 = bondDesc.chunkIndices[1]; + + if (chunkIndex0 >= desc->chunkCount || chunkIndex1 >= desc->chunkCount || chunkIndex0 == chunkIndex1) + { + invalidFound = true; + continue; + } + + const uint32_t graphIndex0 = graphNodeIndexMap[chunkIndex0]; + const uint32_t graphIndex1 = graphNodeIndexMap[chunkIndex1]; + if (Nv::Blast::isInvalidIndex(graphIndex0) || Nv::Blast::isInvalidIndex(graphIndex1)) + { + nonSupportFound = true; + continue; + } + + t[bondSortArraySize++] = Nv::Blast::BondSortData(graphIndex0, graphIndex1, i); + t[bondSortArraySize++] = Nv::Blast::BondSortData(graphIndex1, graphIndex0, i); + } + + // Sort the temp array + std::sort(bondSortArray, bondSortArray + bondSortArraySize, Nv::Blast::BondsOrdered()); + + uint32_t symmetrizedBondCount = 0; + for (uint32_t i = 0; i < bondSortArraySize; ++i) + { + const bool duplicate = i > 0 && bondSortArray[i].m_c0 == bondSortArray[i - 1].m_c0 && bondSortArray[i].m_c1 == bondSortArray[i - 1].m_c1; // Since the array is sorted, uniqueness may be tested by only considering the previous element + duplicateFound = duplicateFound || duplicate; + if (!duplicate) + { // Keep this bond + if (symmetrizedBondCount != i) + { + bondSortArray[symmetrizedBondCount] = bondSortArray[i]; // Compact array if we've dropped bonds + } + ++symmetrizedBondCount; + } + } + NVBLAST_ASSERT((symmetrizedBondCount & 1) == 0); // Because we symmetrized, there should be an even number + + bondCount = symmetrizedBondCount / 2; + + // Report warnings + if (invalidFound) + { + NVBLAST_LOG_WARNING(logFn, "NvBlastCreateAsset: Invalid bonds found (non-existent or same chunks referenced) and removed from asset."); + } + if (duplicateFound) + { + NVBLAST_LOG_WARNING(logFn, "NvBlastCreateAsset: Duplicate bonds found and removed from asset."); + } + if (nonSupportFound) + { + NVBLAST_LOG_WARNING(logFn, "NvBlastCreateAsset: Bonds referencing non-support chunks found and removed from asset."); + } + } + + // Allocate memory for asset + NvBlastID id; + memset(&id, 0, sizeof(NvBlastID)); // To do - create an actual id + Nv::Blast::Asset* asset = initializeAsset(mem, id, desc->chunkCount, supportChunkCount, leafChunkCount, firstSubsupportChunkIndex, bondCount, logFn); + + // Asset data pointers + Nv::Blast::SupportGraph& graph = asset->m_graph; + NvBlastChunk* chunks = asset->getChunks(); + NvBlastBond* bonds = asset->getBonds(); + uint32_t* subtreeLeafChunkCounts = asset->getSubtreeLeafChunkCounts(); + + // Create chunks + uint32_t* graphChunkIndices = graph.getChunkIndices(); + for (uint32_t i = 0; i < desc->chunkCount; ++i) + { + const NvBlastChunkDesc& chunkDesc = desc->chunkDescs[i]; + const uint32_t newChunkIndex = i; + NvBlastChunk& assetChunk = chunks[newChunkIndex]; + memcpy(assetChunk.centroid, chunkDesc.centroid, 3 * sizeof(float)); + assetChunk.volume = chunkDesc.volume; + assetChunk.parentChunkIndex = Nv::Blast::isInvalidIndex(chunkDesc.parentChunkIndex) ? chunkDesc.parentChunkIndex : chunkDesc.parentChunkIndex; + assetChunk.firstChildIndex = Nv::Blast::invalidIndex<uint32_t>(); // Will be filled in below + assetChunk.childIndexStop = assetChunk.firstChildIndex; + assetChunk.userData = chunkDesc.userData; + if (!Nv::Blast::isInvalidIndex(graphNodeIndexMap[newChunkIndex])) + { + graphChunkIndices[graphNodeIndexMap[newChunkIndex]] = newChunkIndex; + } + } + + // Copy chunkToGraphNodeMap + memcpy(asset->getChunkToGraphNodeMap(), graphNodeIndexMap, desc->chunkCount * sizeof(uint32_t)); + + // Count chunk children + for (uint32_t i = 0; i < desc->chunkCount; ++i) + { + const uint32_t parentChunkIndex = chunks[i].parentChunkIndex; + if (!Nv::Blast::isInvalidIndex(parentChunkIndex)) + { + if (chunks[parentChunkIndex].childIndexStop == chunks[parentChunkIndex].firstChildIndex) + { + chunks[parentChunkIndex].childIndexStop = chunks[parentChunkIndex].firstChildIndex = i; + } + ++chunks[parentChunkIndex].childIndexStop; + } + } + + // Create bonds + uint32_t* graphAdjacencyPartition = graph.getAdjacencyPartition(); + uint32_t* graphAdjacentNodeIndices = graph.getAdjacentNodeIndices(); + uint32_t* graphAdjacentBondIndices = graph.getAdjacentBondIndices(); + if (bondCount > 0) + { + // Create the lookup table from the sorted array + Nv::Blast::createIndexStartLookup<uint32_t>(graphAdjacencyPartition, 0, graphNodeCount - 1, &bondSortArray->m_c0, 2 * bondCount, sizeof(Nv::Blast::BondSortData)); + + // Write the adjacent chunk and bond index data + uint32_t bondIndex = 0; + for (uint32_t i = 0; i < 2 * bondCount; ++i) + { + const Nv::Blast::BondSortData& bondSortData = bondSortArray[i]; + graphAdjacentNodeIndices[i] = bondSortData.m_c1; + const uint32_t oldBondIndex = bondSortData.m_b; + const NvBlastBondDesc& bondDesc = desc->bondDescs[oldBondIndex]; + if (Nv::Blast::isInvalidIndex(bondMap[oldBondIndex])) + { + bonds[bondIndex] = bondDesc.bond; + // Our convention is that the bond normal points away from the lower-indexed chunk, towards the higher-indexed chunk. + // If our new (graph node) indexing would reverse this direction from the bond descriptor's indexing, we must flip the nomral. + const bool nodeIndicesOrdered = bondSortData.m_c0 < bondSortData.m_c1; + const bool descNodeIndicesOrdered = bondDesc.chunkIndices[0] < bondDesc.chunkIndices[1]; + if (descNodeIndicesOrdered && !nodeIndicesOrdered) + { + float* normal = bonds[bondIndex].normal; + normal[0] = -normal[0]; + normal[1] = -normal[1]; + normal[2] = -normal[2]; + } + bondMap[oldBondIndex] = bondIndex++; + } + graphAdjacentBondIndices[i] = bondMap[oldBondIndex]; + } + } + else + { + // No bonds - zero out all partition elements (including last one, to give zero size for adjacent data arrays) + memset(graphAdjacencyPartition, 0, (graphNodeCount + 1)*sizeof(uint32_t)); + } + + // Count subtree leaf chunks + memset(subtreeLeafChunkCounts, 0, desc->chunkCount*sizeof(uint32_t)); + uint32_t* breadthFirstChunkIndices = graphNodeIndexMap; // Reusing graphNodeIndexMap ... graphNodeIndexMap may no longer be used + for (uint32_t startChunkIndex = 0; startChunkIndex < desc->chunkCount; ++startChunkIndex) + { + if (!Nv::Blast::isInvalidIndex(chunks[startChunkIndex].parentChunkIndex)) + { + break; // Only iterate through root chunks at this level + } + const uint32_t enumeratedChunkCount = enumerateChunkHierarchyBreadthFirst(breadthFirstChunkIndices, desc->chunkCount, chunks, startChunkIndex, false); + for (uint32_t chunkNum = enumeratedChunkCount; chunkNum--;) + { + const uint32_t chunkIndex = breadthFirstChunkIndices[chunkNum]; + const NvBlastChunk& chunk = chunks[chunkIndex]; + if (chunk.childIndexStop <= chunk.firstChildIndex) + { + subtreeLeafChunkCounts[chunkIndex] = 1; + } + NVBLAST_ASSERT(!isInvalidIndex(chunk.parentChunkIndex)); // Parent index is valid because root chunk is not included in this list (because of 'false' passed into enumerateChunkHierarchyBreadthFirst, above) + subtreeLeafChunkCounts[chunk.parentChunkIndex] += subtreeLeafChunkCounts[chunkIndex]; + } + } + + return asset; +} + + +bool Asset::ensureExactSupportCoverage(uint32_t& supportChunkCount, uint32_t& leafChunkCount, char* chunkAnnotation, uint32_t chunkCount, NvBlastChunkDesc* chunkDescs, bool testOnly, NvBlastLog logFn) +{ + // Clear leafChunkCount + leafChunkCount = 0; + + memset(chunkAnnotation, 0, chunkCount); + + // Walk up the hierarchy from all chunks and mark all parents + for (uint32_t i = 0; i < chunkCount; ++i) + { + if (chunkAnnotation[i] & Asset::ChunkAnnotation::Parent) + { + continue; + } + uint32_t chunkIndex = i; + while (!isInvalidIndex(chunkIndex = chunkDescs[chunkIndex].parentChunkIndex)) + { + chunkAnnotation[chunkIndex] = Asset::ChunkAnnotation::Parent; // Note as non-leaf + } + } + + // Walk up the hierarchy from all leaves (counting them with leafChunkCount) and keep track of the support chunks found on each chain + // Exactly one support chunk should be found on each walk. Remove all but the highest support markings if more than one are found. + bool redundantCoverage = false; + bool insufficientCoverage = false; + for (uint32_t i = 0; i < chunkCount; ++i) + { + if (chunkAnnotation[i] & Asset::ChunkAnnotation::Parent) + { + continue; + } + ++leafChunkCount; + uint32_t supportChunkIndex; + supportChunkIndex = invalidIndex<uint32_t>(); + uint32_t chunkIndex = i; + bool doneWithChain = false; + do + { + if (chunkDescs[chunkIndex].flags & NvBlastChunkDesc::SupportFlag) + { + if (chunkAnnotation[chunkIndex] & Asset::ChunkAnnotation::Support) + { + // We've already been up this chain and marked this as support, so we have unique coverage already + doneWithChain = true; + } + chunkAnnotation[chunkIndex] |= Asset::ChunkAnnotation::Support; // Note as support + if (!isInvalidIndex(supportChunkIndex)) + { + if (testOnly) + { + return false; + } + redundantCoverage = true; + chunkAnnotation[supportChunkIndex] &= ~Asset::ChunkAnnotation::Support; // Remove support marking + do // Run up the hierarchy from supportChunkIndex to chunkIndex and remove the supersupport markings + { + supportChunkIndex = chunkDescs[supportChunkIndex].parentChunkIndex; + chunkAnnotation[supportChunkIndex] &= ~Asset::ChunkAnnotation::SuperSupport; // Remove supersupport marking + } while (supportChunkIndex != chunkIndex); + } + supportChunkIndex = chunkIndex; + } + else + if (!isInvalidIndex(supportChunkIndex)) + { + chunkAnnotation[chunkIndex] |= Asset::ChunkAnnotation::SuperSupport; // Not a support chunk and we've already found a support chunk, so this is super-support + } + } while (!doneWithChain && !isInvalidIndex(chunkIndex = chunkDescs[chunkIndex].parentChunkIndex)); + if (isInvalidIndex(supportChunkIndex)) + { + if (testOnly) + { + return false; + } + insufficientCoverage = true; + } + } + + if (redundantCoverage) + { + NVBLAST_LOG_INFO(logFn, "NvBlastCreateAsset: some leaf-to-root chains had more than one support chunk. Some support chunks removed."); + } + + if (insufficientCoverage) + { + // If coverage was insufficient, then walk up the hierarchy again and mark all chunks that have a support descendant. + // This will allow us to place support chunks at the highest possible level to obtain coverage. + for (uint32_t i = 0; i < chunkCount; ++i) + { + if (chunkAnnotation[i] & Asset::ChunkAnnotation::Parent) + { + continue; + } + bool supportFound = false; + uint32_t chunkIndex = i; + do + { + if (chunkAnnotation[chunkIndex] & Asset::ChunkAnnotation::Support) + { + supportFound = true; + } + else + if (supportFound) + { + chunkAnnotation[chunkIndex] |= Asset::ChunkAnnotation::SuperSupport; // Note that a descendant has support + } + } while (!isInvalidIndex(chunkIndex = chunkDescs[chunkIndex].parentChunkIndex)); + } + + // Now walk up the hierarchy from each leaf one more time, and make sure there is coverage + for (uint32_t i = 0; i < chunkCount; ++i) + { + if (chunkAnnotation[i] & Asset::ChunkAnnotation::Parent) + { + continue; + } + uint32_t previousChunkIndex; + previousChunkIndex = invalidIndex<uint32_t>(); + uint32_t chunkIndex = i; + for (;;) + { + if (chunkAnnotation[chunkIndex] & Asset::ChunkAnnotation::Support) + { + break; // There is support along this chain + } + if (chunkAnnotation[chunkIndex] & Asset::ChunkAnnotation::SuperSupport) + { + NVBLAST_ASSERT(!isInvalidIndex(previousChunkIndex)); // This should be impossible + chunkAnnotation[previousChunkIndex] |= Asset::ChunkAnnotation::Support; // There is no support along this chain, and this is the highest place where we can put support + break; + } + previousChunkIndex = chunkIndex; + chunkIndex = chunkDescs[chunkIndex].parentChunkIndex; + if (isInvalidIndex(chunkIndex)) + { + chunkAnnotation[previousChunkIndex] |= Asset::ChunkAnnotation::Support; // There was no support found anywhere in the hierarchy, so we add it at the root + break; + } + } + } + + NVBLAST_LOG_INFO(logFn, "NvBlastCreateAsset: some leaf-to-root chains had no support chunks. Support chunks added."); + } + + // Apply changes and count the number of support chunks + supportChunkCount = 0; + for (uint32_t i = 0; i < chunkCount; ++i) + { + const bool wasSupport = (chunkDescs[i].flags & NvBlastChunkDesc::SupportFlag) != 0; + const bool nowSupport = (chunkAnnotation[i] & Asset::ChunkAnnotation::Support) != 0; + if (wasSupport != nowSupport) + { + chunkDescs[i].flags ^= NvBlastChunkDesc::SupportFlag; + } + if ((chunkDescs[i].flags & NvBlastChunkDesc::SupportFlag) != 0) + { + ++supportChunkCount; + } + } + + return !redundantCoverage && !insufficientCoverage; +} + + +bool Asset::testForValidChunkOrder(uint32_t chunkCount, const NvBlastChunkDesc* chunkDescs, const char* chunkAnnotation, void* scratch) +{ + char* chunkMarks = static_cast<char*>(memset(scratch, 0, chunkCount)); + + uint32_t currentParentChunkIndex = invalidIndex<uint32_t>(); + for (uint32_t i = 0; i < chunkCount; ++i) + { + const uint32_t parentChunkIndex = chunkDescs[i].parentChunkIndex; + if (parentChunkIndex != currentParentChunkIndex) + { + if (!Nv::Blast::isInvalidIndex(currentParentChunkIndex)) + { + chunkMarks[currentParentChunkIndex] = 1; + } + currentParentChunkIndex = parentChunkIndex; + if (Nv::Blast::isInvalidIndex(currentParentChunkIndex)) + { + return false; + } + else if (chunkMarks[currentParentChunkIndex] != 0) + { + return false; + } + } + + if (i < chunkCount - 1) + { + const bool upperSupport0 = (chunkAnnotation[i] & ChunkAnnotation::UpperSupport) != 0; + const bool upperSupport1 = (chunkAnnotation[i + 1] & ChunkAnnotation::UpperSupport) != 0; + + if (!upperSupport0 && upperSupport1) + { + return false; + } + } + } + + return true; +} + +} // namespace Blast +} // namespace Nv + + +// API implementation + +extern "C" +{ + +size_t NvBlastGetRequiredScratchForCreateAsset(const NvBlastAssetDesc* desc, NvBlastLog logFn) +{ + NVBLAST_CHECK(desc != nullptr, logFn, "NvBlastGetRequiredScratchForCreateAsset: NULL desc pointer input.", return 0); + + return Nv::Blast::Asset::createRequiredScratch(desc); +} + + +size_t NvBlastGetAssetMemorySize(const NvBlastAssetDesc* desc, NvBlastLog logFn) +{ + NVBLAST_CHECK(desc != nullptr, logFn, "NvBlastGetAssetMemorySize: NULL desc input.", return 0); + + return Nv::Blast::Asset::getMemorySize(desc); +} + + +NvBlastAsset* NvBlastCreateAsset(void* mem, const NvBlastAssetDesc* desc, void* scratch, NvBlastLog logFn) +{ + return Nv::Blast::Asset::create(mem, desc, scratch, logFn); +} + + +size_t NvBlastAssetGetFamilyMemorySize(const NvBlastAsset* asset, NvBlastLog logFn) +{ + NVBLAST_CHECK(asset != nullptr, logFn, "NvBlastAssetGetFamilyMemorySize: NULL asset pointer input.", return 0); + + return Nv::Blast::getFamilyMemorySize(reinterpret_cast<const Nv::Blast::Asset*>(asset)); +} + + +NvBlastID NvBlastAssetGetID(const NvBlastAsset* asset, NvBlastLog logFn) +{ + NVBLAST_CHECK(asset != nullptr, logFn, "NvBlastAssetGetID: NULL asset pointer input.", NvBlastID zero; memset(&zero, 0, sizeof(NvBlastID)); return zero); + + return ((Nv::Blast::Asset*)asset)->m_ID; +} + + +bool NvBlastAssetSetID(NvBlastAsset* asset, const NvBlastID* id, NvBlastLog logFn) +{ + NVBLAST_CHECK(asset != nullptr, logFn, "NvBlastAssetSetID: NULL asset pointer input.", return false); + NVBLAST_CHECK(id != nullptr, logFn, "NvBlastAssetSetID: NULL id pointer input.", return false); + + ((Nv::Blast::Asset*)asset)->m_ID = *id; + + return true; +} + + +uint32_t NvBlastAssetGetFormatVersion(const NvBlastAsset* asset, NvBlastLog logFn) +{ + NVBLAST_CHECK(asset != nullptr, logFn, "NvBlastAssetGetFormatVersion: NULL asset input.", return UINT32_MAX); + + return ((Nv::Blast::Asset*)asset)->m_header.formatVersion; +} + + +uint32_t NvBlastAssetGetSize(const NvBlastAsset* asset, NvBlastLog logFn) +{ + NVBLAST_CHECK(asset != nullptr, logFn, "NvBlastAssetGetSize: NULL asset input.", return 0); + + return ((Nv::Blast::Asset*)asset)->m_header.size; +} + + +uint32_t NvBlastAssetGetChunkCount(const NvBlastAsset* asset, NvBlastLog logFn) +{ + NVBLAST_CHECK(asset != nullptr, logFn, "NvBlastAssetGetChunkCount: NULL asset input.", return 0); + + return ((Nv::Blast::Asset*)asset)->m_chunkCount; +} + + +uint32_t NvBlastAssetGetLeafChunkCount(const NvBlastAsset* asset, NvBlastLog logFn) +{ + NVBLAST_CHECK(asset != nullptr, logFn, "NvBlastAssetGetLeafChunkCount: NULL asset input.", return 0); + + return ((Nv::Blast::Asset*)asset)->m_leafChunkCount; +} + + +uint32_t NvBlastAssetGetFirstSubsupportChunkIndex(const NvBlastAsset* asset, NvBlastLog logFn) +{ + NVBLAST_CHECK(asset != nullptr, logFn, "NvBlastAssetGetFirstSubsupportChunkIndex: NULL asset input.", return 0); + + return ((Nv::Blast::Asset*)asset)->m_firstSubsupportChunkIndex; +} + + +uint32_t NvBlastAssetGetBondCount(const NvBlastAsset* asset, NvBlastLog logFn) +{ + NVBLAST_CHECK(asset != nullptr, logFn, "NvBlastAssetGetBondCount: NULL asset input.", return 0); + + return ((Nv::Blast::Asset*)asset)->m_bondCount; +} + + +const NvBlastSupportGraph NvBlastAssetGetSupportGraph(const NvBlastAsset* asset, NvBlastLog logFn) +{ + NVBLAST_CHECK(asset != nullptr, logFn, "NvBlastAssetGetSupportGraph: NULL asset input.", + NvBlastSupportGraph blank; blank.nodeCount = 0; blank.chunkIndices = blank.adjacencyPartition = blank.adjacentNodeIndices = blank.adjacentBondIndices = nullptr; return blank); + + const Nv::Blast::SupportGraph& supportGraph = static_cast<const Nv::Blast::Asset*>(asset)->m_graph; + + NvBlastSupportGraph graph; + graph.nodeCount = supportGraph.m_nodeCount; + graph.chunkIndices = supportGraph.getChunkIndices(); + graph.adjacencyPartition = supportGraph.getAdjacencyPartition(); + graph.adjacentNodeIndices = supportGraph.getAdjacentNodeIndices(); + graph.adjacentBondIndices = supportGraph.getAdjacentBondIndices(); + + return graph; +} + + +const uint32_t* NvBlastAssetGetChunkToGraphNodeMap(const NvBlastAsset* asset, NvBlastLog logFn) +{ + NVBLAST_CHECK(asset != nullptr, logFn, "NvBlastAssetGetChunkToGraphNodeMap: NULL asset input.", return nullptr); + + return static_cast<const Nv::Blast::Asset*>(asset)->getChunkToGraphNodeMap(); +} + + +const NvBlastChunk* NvBlastAssetGetChunks(const NvBlastAsset* asset, NvBlastLog logFn) +{ + NVBLAST_CHECK(asset != nullptr, logFn, "NvBlastAssetGetChunks: NULL asset input.", return 0); + + return ((Nv::Blast::Asset*)asset)->getChunks(); +} + + +const NvBlastBond* NvBlastAssetGetBonds(const NvBlastAsset* asset, NvBlastLog logFn) +{ + NVBLAST_CHECK(asset != nullptr, logFn, "NvBlastAssetGetBonds: NULL asset input.", return 0); + + return ((Nv::Blast::Asset*)asset)->getBonds(); +} + + +uint32_t NvBlastAssetGetActorSerializationSizeUpperBound(const NvBlastAsset* asset, NvBlastLog logFn) +{ + NVBLAST_CHECK(asset != nullptr, logFn, "NvBlastAssetGetActorSerializationSizeUpperBound: NULL asset input.", return 0); + + const Nv::Blast::Asset& solverAsset = *(const Nv::Blast::Asset*)asset; + const uint32_t graphNodeCount = solverAsset.m_graph.m_nodeCount; + + // Calculate serialization size for an actor with all graph nodes (and therefore all bonds), and somehow with all graph nodes visible (after all, this is an upper bound). + const uint64_t upperBound = Nv::Blast::getActorSerializationSize(graphNodeCount, solverAsset.getLowerSupportChunkCount(), graphNodeCount, solverAsset.getBondCount()); + + if (upperBound > UINT32_MAX) + { + NVBLAST_LOG_WARNING(logFn, "NvBlastAssetGetActorSerializationSizeUpperBound: Serialization block size exceeds 4GB. Returning 0.\n"); + return 0; + } + + return static_cast<uint32_t>(upperBound); +} + +} // extern "C" diff --git a/NvBlast/sdk/lowlevel/source/NvBlastAsset.h b/NvBlast/sdk/lowlevel/source/NvBlastAsset.h new file mode 100644 index 0000000..30e8161 --- /dev/null +++ b/NvBlast/sdk/lowlevel/source/NvBlastAsset.h @@ -0,0 +1,294 @@ +/* +* Copyright (c) 2016-2017, NVIDIA CORPORATION. All rights reserved. +* +* NVIDIA CORPORATION and its licensors retain all intellectual property +* and proprietary rights in and to this software, related documentation +* and any modifications thereto. Any use, reproduction, disclosure or +* distribution of this software and related documentation without an express +* license agreement from NVIDIA CORPORATION is strictly prohibited. +*/ + +#ifndef NVBLASTASSET_H +#define NVBLASTASSET_H + + +#include "NvBlastSupportGraph.h" +#include "NvBlast.h" +#include "NvBlastAssert.h" +#include "NvBlastIndexFns.h" +#include "NvBlastChunkHierarchy.h" + + +namespace Nv +{ +namespace Blast +{ + +class Asset : public NvBlastAsset +{ +public: + + /** + Struct-enum which is used to mark chunk descriptors when building an asset. + */ + struct ChunkAnnotation + { + enum Enum + { + Parent = (1 << 0), + Support = (1 << 1), + SuperSupport = (1 << 2), + + // Combinations + UpperSupport = Support | SuperSupport + }; + }; + + + /** + Create an asset from a descriptor. + + \param[in] mem Pointer to block of memory of at least the size given by getMemorySize(desc). Must be 16-byte aligned. + \param[in] desc Asset descriptor (see NvBlastAssetDesc). + \param[in] scratch User-supplied scratch memory of size createRequiredScratch(desc) bytes. + \param[in] logFn User-supplied message function (see NvBlastLog definition). May be NULL. + + \return the pointer to the new asset, or nullptr if unsuccessful. + */ + static Asset* create(void* mem, const NvBlastAssetDesc* desc, void* scratch, NvBlastLog logFn); + + /** + Returns the number of bytes of memory that an asset created using the given descriptor will require. A pointer + to a block of memory of at least this size must be passed in as the mem argument of create. + + \param[in] desc The asset descriptor that will be passed into NvBlastCreateAsset. + */ + static size_t getMemorySize(const NvBlastAssetDesc* desc); + + /** + Returns the size of the scratch space (in bytes) required to be passed into the create function, based upon + the input descriptor that will be passed to the create function. + + \param[in] desc The descriptor that will be passed to the create function. + + \return the number of bytes required. + */ + static size_t createRequiredScratch(const NvBlastAssetDesc* desc); + + + /** + Returns the number of upper-support chunks in this asset.. + + \return the number of upper-support chunks. + */ + uint32_t getUpperSupportChunkCount() const; + + /** + Returns the number of lower-support chunks in this asset. This is the required actor buffer size for a Actor family. + + \return the number of lower-support chunks. + */ + uint32_t getLowerSupportChunkCount() const; + + /** + Returns the number of bonds in this asset's support graph. + + \return the number of bonds in this asset's support graph. + */ + uint32_t getBondCount() const; + + /** + Returns the number of separate chunk hierarchies in the asset. This will be the initial number of visible chunks in an actor instanced from this asset. + + \return the number of separate chunk hierarchies in the asset. + */ + uint32_t getHierarchyCount() const; + + /** + Maps all lower-support chunk indices to a contiguous range [0, getLowerSupportChunkCount()). + + \param[in] chunkIndex Asset chunk index. + + \return an index in the range [0, getLowerSupportChunkCount()) if it is a lower-support chunk, invalidIndex<uint32_t>() otherwise. + */ + uint32_t getContiguousLowerSupportIndex(uint32_t chunkIndex) const; + + + // Static functions + + /** + Function to ensure support coverage of chunks. + + Support chunks (marked in the NvBlastChunkDesc struct) must provide full coverage over the asset. + This means that from any leaf chunk to the root node, exactly one chunk must be support. If this condition + is not met, the actual support chunks will be adjusted accordingly. + + Chunk order depends on support coverage, so this function should be called before chunk reordering. + + \param[out] supportChunkCount The number of support chunks. NOTE - this value is not meaninful if testOnly = true and the return value is false. + \param[out] leafChunkCount The number of leaf chunks. NOTE - this value is not meaninful if testOnly = true and the return value is false. + \param[out] chunkAnnotation User-supplied char array of size chunkCount. NOTE - these values are not meaninful if testOnly = true and the return value is false. + \param[in] chunkCount The number of chunk descriptors. + \param[in] chunkDescs Array of chunk descriptors of size chunkCount. It will be updated accordingly. + \param[in] testOnly If true, this function early-outs if support coverage is not exact. If false, exact coverage is ensured by possibly modifying chunkDescs' flags. + \param[in] logFn User-supplied message function (see NvBlastLog definition). May be NULL. + + \return true iff coverage was already exact. + */ + static bool ensureExactSupportCoverage(uint32_t& supportChunkCount, uint32_t& leafChunkCount, char* chunkAnnotation, uint32_t chunkCount, NvBlastChunkDesc* chunkDescs, bool testOnly, NvBlastLog logFn); + + /** + Tests a set of chunk descriptors to see if chunks are in valid chunk order. + + Chunk order conditions checked: + 1. 'all chunks with same parent index should go in a row'. + 2. 'root chunks should go first'. + 3. 'upper-support chunks should come before subsupport chunks'. + + \param[in] chunkCount The number of chunk descriptors. + \param[in] chunkDescs An array of chunk descriptors of length chunkCount. + \param[in] chunkAnnotation Annotation generated from ensureExactSupportCoverage (see ensureExactSupportCoverage). + \param[in] scratch User-supplied scratch memory of chunkCount bytes. + + \return true if the descriptors meet the ordering conditions, false otherwise. + */ + static bool testForValidChunkOrder(uint32_t chunkCount, const NvBlastChunkDesc* chunkDescs, const char* chunkAnnotation, void* scratch); + + + //////// Data //////// + + /** + Asset data block header. + */ + NvBlastDataBlock m_header; + + /** + ID for this asset. + */ + NvBlastID m_ID; + + /** + The total number of chunks in the asset, support and non-support. + */ + uint32_t m_chunkCount; + + /** + The support graph. + */ + SupportGraph m_graph; + + /** + The number of leaf chunks in the asset. + */ + uint32_t m_leafChunkCount; + + /** + Chunks are sorted such that subsupport chunks come last. This is the first subsupport chunk index. Equals m_chunkCount if there are no subsupport chunks. + */ + uint32_t m_firstSubsupportChunkIndex; + + /** + The number of bonds in the asset. + */ + uint32_t m_bondCount; + + /** + Chunks, of type NvBlastChunk. + + getChunks returns an array of size m_chunkCount. + */ + NvBlastBlockArrayData(NvBlastChunk, m_chunksOffset, getChunks, m_chunkCount); + + /** + Array of bond data for the interfaces between two chunks. Since the bond is shared by two chunks, the same + bond data is used for chunk[i] -> chunk[j] as for chunk[j] -> chunk[i]. + The size of the array is m_graph.adjacencyPartition[m_graph.m_nodeCount]/2. + See NvBlastBond. + + getBonds returns an array of size m_bondCount. + */ + NvBlastBlockArrayData(NvBlastBond, m_bondsOffset, getBonds, m_bondCount); + + /** + Caching the number of leaf chunks descended from each chunk (including the chunk itself). + This data parallels the Chunks array, and is an array of the same size. + + getSubtreeLeafChunkCount returns a uint32_t array of size m_chunkCount. + */ + NvBlastBlockArrayData(uint32_t, m_subtreeLeafChunkCountsOffset, getSubtreeLeafChunkCounts, m_chunkCount); + + /** + Mapping from chunk index to graph node index (inverse of m_graph.getChunkIndices(). + + getChunkToGraphNodeMap returns a uint32_t array of size m_chunkCount. + */ + NvBlastBlockArrayData(uint32_t, m_chunkToGraphNodeMapOffset, getChunkToGraphNodeMap, m_chunkCount); + + + //////// Iterators //////// + + /** + Chunk hierarchy depth-first iterator. Traverses subtree with root given by startChunkIndex. + If upperSupportOnly == true, then the iterator will not traverse subsuppport chunks. + */ + class DepthFirstIt : public ChunkDepthFirstIt + { + public: + /** Constructed from an asset. */ + DepthFirstIt(const Asset& asset, uint32_t startChunkIndex, bool upperSupportOnly = false) : + ChunkDepthFirstIt(asset.getChunks(), startChunkIndex, upperSupportOnly ? asset.getUpperSupportChunkCount() : asset.m_chunkCount) {} + }; +}; + + +//////// Asset inline member functions //////// + +NV_INLINE uint32_t Asset::getUpperSupportChunkCount() const +{ + return m_firstSubsupportChunkIndex; +} + + +NV_INLINE uint32_t Asset::getLowerSupportChunkCount() const +{ + return m_graph.m_nodeCount + (m_chunkCount - m_firstSubsupportChunkIndex); +} + + +NV_INLINE uint32_t Asset::getBondCount() const +{ + NVBLAST_ASSERT((m_graph.getAdjacencyPartition()[m_graph.m_nodeCount] & 1) == 0); // The bidirectional graph data should have an even number of edges + return m_graph.getAdjacencyPartition()[m_graph.m_nodeCount] / 2; // Directional bonds, divide by two +} + + +NV_INLINE uint32_t Asset::getHierarchyCount() const +{ + const NvBlastChunk* chunks = getChunks(); + for (uint32_t i = 0; i < m_chunkCount; ++i) + { + if (!isInvalidIndex(chunks[i].parentChunkIndex)) + { + return i; + } + } + return m_chunkCount; +} + + +NV_INLINE uint32_t Asset::getContiguousLowerSupportIndex(uint32_t chunkIndex) const +{ + NVBLAST_ASSERT(chunkIndex < m_chunkCount); + + return chunkIndex < m_firstSubsupportChunkIndex ? getChunkToGraphNodeMap()[chunkIndex] : (chunkIndex - m_firstSubsupportChunkIndex + m_graph.m_nodeCount); +} + + +//JDM: Expose this so serialization layer can use it. +NVBLAST_API Asset* initializeAsset(void* mem, NvBlastID id, uint32_t chunkCount, uint32_t graphNodeCount, uint32_t leafChunkCount, uint32_t firstSubsupportChunkIndex, uint32_t bondCount, NvBlastLog logFn); + +} // namespace Blast +} // namespace Nv + + +#endif // ifndef NVBLASTASSET_H diff --git a/NvBlast/sdk/lowlevel/source/NvBlastAssetHelper.cpp b/NvBlast/sdk/lowlevel/source/NvBlastAssetHelper.cpp new file mode 100644 index 0000000..0d6c5d2 --- /dev/null +++ b/NvBlast/sdk/lowlevel/source/NvBlastAssetHelper.cpp @@ -0,0 +1,183 @@ +/* +* Copyright (c) 2016-2017, NVIDIA CORPORATION. All rights reserved. +* +* NVIDIA CORPORATION and its licensors retain all intellectual property +* and proprietary rights in and to this software, related documentation +* and any modifications thereto. Any use, reproduction, disclosure or +* distribution of this software and related documentation without an express +* license agreement from NVIDIA CORPORATION is strictly prohibited. +*/ + +#include "NvBlastAsset.h" +#include "NvBlastIndexFns.h" +#include "NvBlastAssert.h" +#include "NvBlastMemory.h" + +#include <algorithm> + + +namespace Nv +{ +namespace Blast +{ + +/** +Class to hold chunk descriptor and annotation context for sorting a list of indices +*/ +class ChunksOrdered +{ +public: + ChunksOrdered(const NvBlastChunkDesc* descs, const char* annotation) : m_descs(descs), m_annotation(annotation) {} + + bool operator () (uint32_t i0, uint32_t i1) const + { + const bool upperSupport0 = (m_annotation[i0] & Asset::ChunkAnnotation::UpperSupport) != 0; + const bool upperSupport1 = (m_annotation[i1] & Asset::ChunkAnnotation::UpperSupport) != 0; + + if (upperSupport0 != upperSupport1) + { + return upperSupport0; // If one is uppersupport and one is subsupport, uppersupport should come first + } + + // Parent chunk index (+1 so that UINT32_MAX becomes the lowest value) + const uint32_t p0 = m_descs[i0].parentChunkIndex + 1; + const uint32_t p1 = m_descs[i1].parentChunkIndex + 1; + + return p0 < p1; // With the same support relationship, order by parent index + } + +private: + const NvBlastChunkDesc* m_descs; + const char* m_annotation; +}; + +} // namespace Blast +} // namespace Nv + + +using namespace Nv::Blast; + +extern "C" +{ + +bool NvBlastBuildAssetDescChunkReorderMap(uint32_t* chunkReorderMap, const NvBlastChunkDesc* chunkDescs, uint32_t chunkCount, void* scratch, NvBlastLog logFn) +{ + NVBLAST_CHECK(chunkCount == 0 || chunkDescs != nullptr, logFn, "NvBlastBuildAssetDescChunkReorderMap: NULL chunkDescs input with non-zero chunkCount", return false); + NVBLAST_CHECK(chunkReorderMap == nullptr || chunkCount != 0, logFn, "NvBlastBuildAssetDescChunkReorderMap: NULL chunkReorderMap input with non-zero chunkCount", return false); + NVBLAST_CHECK(chunkCount == 0 || scratch != nullptr, logFn, "NvBlastBuildAssetDescChunkReorderMap: NULL scratch input with non-zero chunkCount", return false); + + uint32_t* chunkMap = static_cast<uint32_t*>(scratch); scratch = pointerOffset(scratch, chunkCount * sizeof(uint32_t)); + char* chunkAnnotation = static_cast<char*>(scratch); scratch = pointerOffset(scratch, chunkCount * sizeof(char)); + + uint32_t supportChunkCount; + uint32_t leafChunkCount; + if (!Asset::ensureExactSupportCoverage(supportChunkCount, leafChunkCount, chunkAnnotation, chunkCount, const_cast<NvBlastChunkDesc*>(chunkDescs), true, logFn)) + { + NVBLAST_LOG_ERROR(logFn, "NvBlastBuildAssetDescChunkReorderMap: chunk descriptors did not have exact coverage, map could not be built. Use NvBlastEnsureAssetExactSupportCoverage to fix descriptors."); + return false; + } + + // check order for fast out (identity map) + if (Asset::testForValidChunkOrder(chunkCount, chunkDescs, chunkAnnotation, scratch)) + { + for (uint32_t i = 0; i < chunkCount; ++i) + { + chunkReorderMap[i] = i; + } + + return true; + } + + for (uint32_t i = 0; i < chunkCount; ++i) + { + chunkMap[i] = i; + } + std::sort(chunkMap, chunkMap + chunkCount, ChunksOrdered(chunkDescs, chunkAnnotation)); + + invertMap(chunkReorderMap, chunkMap, chunkCount); + + return false; +} + + +void NvBlastApplyAssetDescChunkReorderMap +( + NvBlastChunkDesc* reorderedChunkDescs, + const NvBlastChunkDesc* chunkDescs, + uint32_t chunkCount, + NvBlastBondDesc* bondDescs, + uint32_t bondCount, + const uint32_t* chunkReorderMap, + NvBlastLog logFn +) +{ + NVBLAST_CHECK(chunkCount == 0 || chunkDescs != nullptr, logFn, "NvBlastApplyAssetDescChunkReorderMap: NULL chunkDescs input with non-zero chunkCount", return); + NVBLAST_CHECK(reorderedChunkDescs == nullptr || chunkCount != 0, logFn, "NvBlastApplyAssetDescChunkReorderMap: NULL reorderedChunkDescs input with non-zero chunkCount", return); + NVBLAST_CHECK(chunkReorderMap == nullptr || chunkCount != 0, logFn, "NvBlastApplyAssetDescChunkReorderMap: NULL chunkReorderMap input with non-zero chunkCount", return); + NVBLAST_CHECK(bondCount == 0 || bondDescs != nullptr, logFn, "NvBlastApplyAssetDescChunkReorderMap: NULL bondDescs input with non-zero bondCount", return); + NVBLAST_CHECK(bondDescs == nullptr || chunkReorderMap != nullptr, logFn, "NvBlastApplyAssetDescChunkReorderMap: NULL bondDescs input with NULL chunkReorderMap", return); + + // Copy chunk descs + if (reorderedChunkDescs) + { + for (uint32_t i = 0; i < chunkCount; ++i) + { + reorderedChunkDescs[chunkReorderMap[i]] = chunkDescs[i]; + uint32_t& parentIndex = reorderedChunkDescs[chunkReorderMap[i]].parentChunkIndex; + if (parentIndex < chunkCount) + { + parentIndex = chunkReorderMap[parentIndex]; // If the parent index is valid, remap it too to reflect the new order + } + } + } + + if (bondDescs) + { + for (uint32_t i = 0; i < bondCount; ++i) + { + for (int j = 0; j < 2; ++j) + { + uint32_t& index = bondDescs[i].chunkIndices[j]; + if (index < chunkCount) + { + index = chunkReorderMap[index]; + } + } + } + } +} + + +void NvBlastApplyAssetDescChunkReorderMapInplace(NvBlastChunkDesc* chunkDescs, uint32_t chunkCount, NvBlastBondDesc* bondDescs, uint32_t bondCount, const uint32_t* chunkReorderMap, void* scratch, NvBlastLog logFn) +{ + NVBLAST_CHECK(chunkCount == 0 || chunkDescs != nullptr, logFn, "NvBlastApplyAssetDescChunkReorderMapInplace: NULL chunkDescs input with non-zero chunkCount", return); + NVBLAST_CHECK(chunkCount == 0 || scratch != nullptr, logFn, "NvBlastApplyAssetDescChunkReorderMapInplace: NULL scratch input with non-zero chunkCount", return); + + NvBlastChunkDesc* chunksTemp = static_cast<NvBlastChunkDesc*>(scratch); + memcpy(chunksTemp, chunkDescs, sizeof(NvBlastChunkDesc) * chunkCount); + NvBlastApplyAssetDescChunkReorderMap(chunkDescs, chunksTemp, chunkCount, bondDescs, bondCount, chunkReorderMap, logFn); +} + + +bool NvBlastReorderAssetDescChunks(NvBlastChunkDesc* chunkDescs, uint32_t chunkCount, NvBlastBondDesc* bondDescs, uint32_t bondCount, uint32_t* chunkReorderMap, void* scratch, NvBlastLog logFn) +{ + if (!NvBlastBuildAssetDescChunkReorderMap(chunkReorderMap, chunkDescs, chunkCount, scratch, logFn)) + { + NvBlastApplyAssetDescChunkReorderMapInplace(chunkDescs, chunkCount, bondDescs, bondCount, chunkReorderMap, scratch, logFn); + return false; + } + return true; +} + + +bool NvBlastEnsureAssetExactSupportCoverage(NvBlastChunkDesc* chunkDescs, uint32_t chunkCount, void* scratch, NvBlastLog logFn) +{ + NVBLAST_CHECK(chunkCount == 0 || chunkDescs != nullptr, logFn, "NvBlastEnsureAssetExactSupportCoverage: NULL chunkDescs input with non-zero chunkCount", return false); + NVBLAST_CHECK(chunkCount == 0 || scratch != nullptr, logFn, "NvBlastEnsureAssetExactSupportCoverage: NULL scratch input with non-zero chunkCount", return false); + + uint32_t supportChunkCount; + uint32_t leafChunkCount; + return Asset::ensureExactSupportCoverage(supportChunkCount, leafChunkCount, static_cast<char*>(scratch), chunkCount, chunkDescs, false, logFn); +} + +} // extern "C" diff --git a/NvBlast/sdk/lowlevel/source/NvBlastChunkHierarchy.h b/NvBlast/sdk/lowlevel/source/NvBlastChunkHierarchy.h new file mode 100644 index 0000000..e7e05c6 --- /dev/null +++ b/NvBlast/sdk/lowlevel/source/NvBlastChunkHierarchy.h @@ -0,0 +1,232 @@ +/* +* Copyright (c) 2016-2017, NVIDIA CORPORATION. All rights reserved. +* +* NVIDIA CORPORATION and its licensors retain all intellectual property +* and proprietary rights in and to this software, related documentation +* and any modifications thereto. Any use, reproduction, disclosure or +* distribution of this software and related documentation without an express +* license agreement from NVIDIA CORPORATION is strictly prohibited. +*/ + +#ifndef NVBLASTCHUNKHIERARCHY_H +#define NVBLASTCHUNKHIERARCHY_H + + +#include "NvBlastIndexFns.h" +#include "NvBlastDLink.h" +#include "NvBlast.h" +#include "NvBlastAssert.h" +#include "NvBlastIteratorBase.h" + + +namespace Nv +{ +namespace Blast +{ + +/** +Chunk hierarchy depth-first iterator. Traverses subtree with root given by startChunkIndex. +Will not traverse chunks with index at or beyond chunkIndexLimit. +*/ +class ChunkDepthFirstIt : public IteratorBase<uint32_t> +{ +public: + /** Constructed from a chunk array. */ + ChunkDepthFirstIt(const NvBlastChunk* chunks, uint32_t startChunkIndex, uint32_t chunkIndexLimit) : + IteratorBase<uint32_t>(startChunkIndex), m_chunks(chunks), m_stop(startChunkIndex), m_limit(chunkIndexLimit) + { + if (m_curr >= m_limit) + { + m_curr = invalidIndex<uint32_t>(); + } + } + + /** Pre-increment. Only use if valid() == true. */ + uint32_t operator ++ () + { + NVBLAST_ASSERT(!isInvalidIndex(m_curr)); + const NvBlastChunk* chunk = m_chunks + m_curr; + if (chunk->childIndexStop > chunk->firstChildIndex && chunk->firstChildIndex < m_limit) + { + m_curr = chunk->firstChildIndex; + } + else + { + for (;;) + { + if (m_curr == m_stop) + { + m_curr = invalidIndex<uint32_t>(); + break; + } + NVBLAST_ASSERT(!isInvalidIndex(chunk->parentChunkIndex)); // This should not be possible with this search + const NvBlastChunk* parentChunk = m_chunks + chunk->parentChunkIndex; + if (++m_curr < parentChunk->childIndexStop) + { + break; // Sibling chunk is valid, that's the next chunk + } + m_curr = chunk->parentChunkIndex; + chunk = parentChunk; + } + } + return m_curr; + } + +private: + const NvBlastChunk* m_chunks; + uint32_t m_stop; + uint32_t m_limit; +}; + + +/** +Enumerates chunk indices in a subtree with root given by chunkIndex, in breadth-first order. +Will not traverse chunks with index at or beyond chunkIndexLimit. +Returns the number of indices written to the chunkIndex array +*/ +NV_INLINE uint32_t enumerateChunkHierarchyBreadthFirst +( +uint32_t* chunkIndices, +uint32_t chunkIndicesSize, +const NvBlastChunk* chunks, +uint32_t chunkIndex, +bool includeRoot = true, +uint32_t chunkIndexLimit = invalidIndex<uint32_t>() +) +{ + if (chunkIndicesSize == 0) + { + return 0; + } + uint32_t chunkIndexCount = 0; + bool rootHandled = false; + if (includeRoot) + { + chunkIndices[chunkIndexCount++] = chunkIndex; + rootHandled = true; + } + for (uint32_t curr = 0; !rootHandled || curr < chunkIndexCount;) + { + const NvBlastChunk& chunk = chunks[rootHandled ? chunkIndices[curr] : chunkIndex]; + if (chunk.firstChildIndex < chunkIndexLimit) + { + const uint32_t childIndexStop = chunk.childIndexStop < chunkIndexLimit ? chunk.childIndexStop : chunkIndexLimit; + const uint32_t childIndexBufferStop = chunk.firstChildIndex + (chunkIndicesSize - chunkIndexCount); + const uint32_t stop = childIndexStop < childIndexBufferStop ? childIndexStop : childIndexBufferStop; + for (uint32_t childIndex = chunk.firstChildIndex; childIndex < stop; ++childIndex) + { + chunkIndices[chunkIndexCount++] = childIndex; + } + } + if (rootHandled) + { + ++curr; + } + rootHandled = true; + } + return chunkIndexCount; +} + + +/** +VisibilityRep must have m_firstVisibleChunkIndex and m_visibleChunkCount fields +*/ +template<class VisibilityRep> +void updateVisibleChunksFromSupportChunk +( +VisibilityRep* actors, +IndexDLink<uint32_t>* visibleChunkIndexLinks, +uint32_t* chunkActorIndices, +uint32_t actorIndex, +uint32_t supportChunkIndex, +const NvBlastChunk* chunks, +uint32_t upperSupportChunkCount +) +{ + uint32_t chunkIndex = supportChunkIndex; + uint32_t chunkActorIndex = chunkActorIndices[supportChunkIndex]; + uint32_t newChunkActorIndex = actorIndex; + VisibilityRep& thisActor = actors[actorIndex]; + + do + { + if (chunkActorIndex == newChunkActorIndex) + { + break; // Nothing to do + } + + const uint32_t parentChunkIndex = chunks[chunkIndex].parentChunkIndex; + const uint32_t parentChunkActorIndex = parentChunkIndex != invalidIndex<uint32_t>() ? chunkActorIndices[parentChunkIndex] : invalidIndex<uint32_t>(); + const bool chunkVisible = chunkActorIndex != parentChunkActorIndex; + + // If the chunk is visible, it needs to be removed from its old actor's visibility list + if (chunkVisible && !isInvalidIndex(chunkActorIndex)) + { + VisibilityRep& chunkActor = actors[chunkActorIndex]; + IndexDList<uint32_t>().removeFromList(chunkActor.m_firstVisibleChunkIndex, visibleChunkIndexLinks, chunkIndex); + --chunkActor.m_visibleChunkCount; + } + + // Now update the chunk's actor index + const uint32_t oldChunkActorIndex = chunkActorIndices[chunkIndex]; + chunkActorIndices[chunkIndex] = newChunkActorIndex; + if (newChunkActorIndex != invalidIndex<uint32_t>() && parentChunkActorIndex != newChunkActorIndex) + { + // The chunk is now visible. Add it to this actor's visibility list + IndexDList<uint32_t>().insertListHead(thisActor.m_firstVisibleChunkIndex, visibleChunkIndexLinks, chunkIndex); + ++thisActor.m_visibleChunkCount; + // Remove its children from this actor's visibility list + if (actorIndex != oldChunkActorIndex) + { + const NvBlastChunk& chunk = chunks[chunkIndex]; + if (chunk.firstChildIndex < upperSupportChunkCount) // Only need to deal with upper-support children + { + for (uint32_t childChunkIndex = chunk.firstChildIndex; childChunkIndex < chunk.childIndexStop; ++childChunkIndex) + { + if (chunkActorIndices[childChunkIndex] == actorIndex) + { + IndexDList<uint32_t>().removeFromList(thisActor.m_firstVisibleChunkIndex, visibleChunkIndexLinks, childChunkIndex); + --thisActor.m_visibleChunkCount; + } + } + } + } + } + + if (parentChunkIndex != invalidIndex<uint32_t>()) + { + // If all of its siblings have the same index, then the parent will too. Otherwise, the parent will have an invalid index and its children will be visible + const NvBlastChunk& parentChunk = chunks[parentChunkIndex]; + bool uniform = true; + for (uint32_t childChunkIndex = parentChunk.firstChildIndex; uniform && childChunkIndex < parentChunk.childIndexStop; ++childChunkIndex) + { + uniform = (newChunkActorIndex == chunkActorIndices[childChunkIndex]); + } + if (!uniform) + { + newChunkActorIndex = invalidIndex<uint32_t>(); + for (uint32_t childChunkIndex = parentChunk.firstChildIndex; childChunkIndex < parentChunk.childIndexStop; ++childChunkIndex) + { + const uint32_t childChunkActorIndex = chunkActorIndices[childChunkIndex]; + if (childChunkActorIndex != invalidIndex<uint32_t>() && childChunkActorIndex == parentChunkActorIndex) + { + // The child was invisible. Add it to its actor's visibility list + VisibilityRep& childChunkActor = actors[childChunkActorIndex]; + IndexDList<uint32_t>().insertListHead(childChunkActor.m_firstVisibleChunkIndex, visibleChunkIndexLinks, childChunkIndex); + ++childChunkActor.m_visibleChunkCount; + } + } + } + } + + // Climb the hierarchy + chunkIndex = parentChunkIndex; + chunkActorIndex = parentChunkActorIndex; + } while (chunkIndex != invalidIndex<uint32_t>()); +} + +} // namespace Blast +} // namespace Nv + + +#endif // ifndef NVBLASTCHUNKHIERARCHY_H diff --git a/NvBlast/sdk/lowlevel/source/NvBlastFamily.cpp b/NvBlast/sdk/lowlevel/source/NvBlastFamily.cpp new file mode 100644 index 0000000..1f517b1 --- /dev/null +++ b/NvBlast/sdk/lowlevel/source/NvBlastFamily.cpp @@ -0,0 +1,295 @@ +/* +* Copyright (c) 2016-2017, NVIDIA CORPORATION. All rights reserved. +* +* NVIDIA CORPORATION and its licensors retain all intellectual property +* and proprietary rights in and to this software, related documentation +* and any modifications thereto. Any use, reproduction, disclosure or +* distribution of this software and related documentation without an express +* license agreement from NVIDIA CORPORATION is strictly prohibited. +*/ + + +#include "NvBlastFamily.h" +#include "NvBlastFamilyGraph.h" +#include "NvBlastIndexFns.h" + +#include <new> + +namespace Nv +{ +namespace Blast +{ + +//////// Global functions //////// + +struct FamilyDataOffsets +{ + size_t m_actors; + size_t m_visibleChunkIndexLinks; + size_t m_chunkActorIndices; + size_t m_graphNodeIndexLinks; + size_t m_lowerSupportChunkHealths; + size_t m_graphBondHealths; + size_t m_familyGraph; +}; + + +static size_t createFamilyDataOffsets(FamilyDataOffsets& offsets, const Asset* asset) +{ + const Nv::Blast::SupportGraph& graph = asset->m_graph; + + NvBlastCreateOffsetStart(sizeof(FamilyHeader)); + NvBlastCreateOffsetAlign16(offsets.m_actors, asset->getLowerSupportChunkCount() * sizeof(Actor)); + NvBlastCreateOffsetAlign16(offsets.m_visibleChunkIndexLinks, asset->m_chunkCount * sizeof(IndexDLink<uint32_t>)); + NvBlastCreateOffsetAlign16(offsets.m_chunkActorIndices, asset->getUpperSupportChunkCount() * sizeof(uint32_t)); + NvBlastCreateOffsetAlign16(offsets.m_graphNodeIndexLinks, graph.m_nodeCount * sizeof(uint32_t)); + NvBlastCreateOffsetAlign16(offsets.m_lowerSupportChunkHealths, asset->getLowerSupportChunkCount() * sizeof(float)); + NvBlastCreateOffsetAlign16(offsets.m_graphBondHealths, asset->getBondCount() * sizeof(float)); + NvBlastCreateOffsetAlign16(offsets.m_familyGraph, static_cast<size_t>(FamilyGraph::requiredMemorySize(graph.m_nodeCount, asset->getBondCount()))); + return NvBlastCreateOffsetEndAlign16(); +} + + +size_t getFamilyMemorySize(const Asset* asset) +{ +#if NVBLAST_CHECK_PARAMS + if (asset == nullptr) + { + NVBLAST_ALWAYS_ASSERT(); + return 0; + } +#endif + + FamilyDataOffsets offsets; + return createFamilyDataOffsets(offsets, asset); +} + + +NvBlastFamily* createFamily(void* mem, const NvBlastAsset* asset, NvBlastLog logFn) +{ + NVBLAST_CHECK(mem != nullptr, logFn, "createFamily: NULL mem pointer input.", return nullptr); + NVBLAST_CHECK(asset != nullptr, logFn, "createFamily: NULL asset pointer input.", return nullptr); + + NVBLAST_CHECK((reinterpret_cast<uintptr_t>(mem) & 0xF) == 0, logFn, "createFamily: mem pointer not 16-byte aligned.", return nullptr); + + const Asset& solverAsset = *static_cast<const Asset*>(asset); + + if (solverAsset.m_chunkCount == 0) + { + NVBLAST_LOG_ERROR(logFn, "createFamily: Asset has no chunks. Family not created.\n"); + return nullptr; + } + + const Nv::Blast::SupportGraph& graph = solverAsset.m_graph; + + const uint32_t bondCount = solverAsset.getBondCount(); + + // We need to keep this many actor representations around for our island indexing scheme. + const uint32_t lowerSupportChunkCount = solverAsset.getLowerSupportChunkCount(); + + // We need this many chunk actor indices. + const uint32_t upperSupportChunkCount = solverAsset.getUpperSupportChunkCount(); + + // Family offsets + FamilyDataOffsets offsets; + const size_t dataSize = createFamilyDataOffsets(offsets, &solverAsset); + + // Restricting our data size to < 4GB so that we may use uint32_t offsets + if (dataSize > (size_t)UINT32_MAX) + { + NVBLAST_LOG_ERROR(logFn, "Nv::Blast::Actor::instanceAllocate: Instance data block size will exceed 4GB. Instance not created.\n"); + return nullptr; + } + + // Allocate family + NvBlastFamily* family = (NvBlastFamily*)mem; + + // Fill in family header + FamilyHeader* header = (FamilyHeader*)family; + header->dataType = NvBlastDataBlock::FamilyDataBlock; + header->formatVersion = NvBlastFamilyDataFormat::Current; + header->size = (uint32_t)dataSize; + header->m_assetID = solverAsset.m_ID; + header->m_actorCount = 0; + header->m_actorsOffset = (uint32_t)offsets.m_actors; + header->m_visibleChunkIndexLinksOffset = (uint32_t)offsets.m_visibleChunkIndexLinks; + header->m_chunkActorIndicesOffset = (uint32_t)offsets.m_chunkActorIndices; + header->m_graphNodeIndexLinksOffset = (uint32_t)offsets.m_graphNodeIndexLinks; + header->m_lowerSupportChunkHealthsOffset = (uint32_t)offsets.m_lowerSupportChunkHealths; + header->m_graphBondHealthsOffset = (uint32_t)offsets.m_graphBondHealths; + header->m_familyGraphOffset = (uint32_t)offsets.m_familyGraph; + + // Runtime data + header->m_asset = &solverAsset; // NOTE: this should be resolved from m_assetID + + // Initialize family header data: + + // Actors - initialize to defaults, with zero offset value (indicating inactive state) + Actor* actors = header->getActors(); // This will get the subsupport actors too + for (uint32_t i = 0; i < lowerSupportChunkCount; ++i) + { + new (actors + i) Actor(); + } + + // Visible chunk index links - initialize to solitary links (0xFFFFFFFF fields) + memset(header->getVisibleChunkIndexLinks(), 0xFF, solverAsset.m_chunkCount*sizeof(IndexDLink<uint32_t>)); + + // Chunk actor IDs - initialize to invalid (0xFFFFFFFF) + memset(header->getChunkActorIndices(), 0xFF, upperSupportChunkCount*sizeof(uint32_t)); + + // Graph node index links - initialize to solitary links + memset(header->getGraphNodeIndexLinks(), 0xFF, graph.m_nodeCount*sizeof(uint32_t)); + + // Healths are initialized to 0 + memset(header->getLowerSupportChunkHealths(), 0, lowerSupportChunkCount*sizeof(float)); + memset(header->getBondHealths(), 0, bondCount*sizeof(float)); + + // FamilyGraph ctor + new (header->getFamilyGraph()) FamilyGraph(&graph); + + return family; +} + +} // namespace Blast +} // namespace Nv + + +// API implementation + +extern "C" +{ + +NvBlastFamily* NvBlastAssetCreateFamily(void* mem, const NvBlastAsset* asset, NvBlastLog logFn) +{ + return Nv::Blast::createFamily(mem, asset, logFn); +} + + +uint32_t NvBlastFamilyGetFormatVersion(const NvBlastFamily* family, NvBlastLog logFn) +{ + NVBLAST_CHECK(family != nullptr, logFn, "NvBlastFamilyGetFormatVersion: NULL family pointer input.", return UINT32_MAX); + return reinterpret_cast<const Nv::Blast::FamilyHeader*>(family)->formatVersion; +} + + +void NvBlastFamilySetAsset(NvBlastFamily* family, const NvBlastAsset* asset, NvBlastLog logFn) +{ + NVBLAST_CHECK(family != nullptr, logFn, "NvBlastFamilySetAsset: NULL family pointer input.", return); + NVBLAST_CHECK(asset != nullptr, logFn, "NvBlastFamilySetAsset: NULL asset pointer input.", return); + + Nv::Blast::FamilyHeader* header = reinterpret_cast<Nv::Blast::FamilyHeader*>(family); + const Nv::Blast::Asset* solverAsset = reinterpret_cast<const Nv::Blast::Asset*>(asset); + + if (memcmp(&header->m_assetID, &solverAsset->m_ID, sizeof(NvBlastID))) + { + NVBLAST_LOG_ERROR(logFn, "NvBlastFamilySetAsset: wrong asset. Passed asset ID doesn't match family asset ID."); + return; + } + + header->m_asset = solverAsset; +} + + +uint32_t NvBlastFamilyGetSize(const NvBlastFamily* family, NvBlastLog logFn) +{ + NVBLAST_CHECK(family != nullptr, logFn, "NvBlastFamilyGetSize: NULL family pointer input.", return 0); + return reinterpret_cast<const Nv::Blast::FamilyHeader*>(family)->size; +} + + +NvBlastID NvBlastFamilyGetAssetID(const NvBlastFamily* family, NvBlastLog logFn) +{ + NVBLAST_CHECK(family != nullptr, logFn, "NvBlastFamilyGetAssetID: NULL family pointer input.", return NvBlastID()); + return reinterpret_cast<const Nv::Blast::FamilyHeader*>(family)->m_assetID; +} + + +uint32_t NvBlastFamilyGetActorCount(const NvBlastFamily* family, NvBlastLog logFn) +{ + NVBLAST_CHECK(family != nullptr, logFn, "NvBlastFamilyGetActorCount: NULL family pointer input.", return 0); + + const Nv::Blast::FamilyHeader* header = reinterpret_cast<const Nv::Blast::FamilyHeader*>(family); + + if (header->formatVersion != NvBlastFamilyDataFormat::Current) + { + NVBLAST_LOG_ERROR(logFn, "NvBlastFamilyGetActorCount: wrong family format. Family must be converted to current version."); + return 0; + } + + return header->m_actorCount; +} + + +uint32_t NvBlastFamilyGetActors(NvBlastActor** actors, uint32_t actorsSize, const NvBlastFamily* family, NvBlastLog logFn) +{ + NVBLAST_CHECK(actors != nullptr, logFn, "NvBlastFamilyGetActors: NULL actors pointer input.", return 0); + NVBLAST_CHECK(family != nullptr, logFn, "NvBlastFamilyGetActors: NULL family pointer input.", return 0); + + const Nv::Blast::FamilyHeader* header = reinterpret_cast<const Nv::Blast::FamilyHeader*>(family); + + if (header->formatVersion != NvBlastFamilyDataFormat::Current) + { + NVBLAST_LOG_ERROR(logFn, "NvBlastFamilyGetActors: wrong family format. Family must be converted to current version."); + return 0; + } + + // Iterate through active actors and write to supplied array + const uint32_t familyActorCount = header->getActorBufferSize(); + Nv::Blast::Actor* familyActor = header->getActors(); + uint32_t actorCount = 0; + for (uint32_t i = 0; actorCount < actorsSize && i < familyActorCount; ++i, ++familyActor) + { + if (familyActor->isActive()) + { + actors[actorCount++] = familyActor; + } + } + + return actorCount; +} + + +NvBlastActor* NvBlastFamilyGetChunkActor(const NvBlastFamily* family, uint32_t chunkIndex, NvBlastLog logFn) +{ + NVBLAST_CHECK(family != nullptr, logFn, "NvBlastFamilyGetChunkActor: NULL family pointer input.", return nullptr); + + const Nv::Blast::FamilyHeader* header = reinterpret_cast<const Nv::Blast::FamilyHeader*>(family); + + NVBLAST_CHECK(header->m_asset != nullptr, logFn, "NvBlastFamilyGetChunkActor: NvBlastFamily has null asset set.", return nullptr); + + const Nv::Blast::Asset& solverAsset = *static_cast<const Nv::Blast::Asset*>(header->m_asset); + NVBLAST_CHECK(chunkIndex < solverAsset.m_chunkCount, logFn, "NvBlastFamilyGetChunkActor: bad value of chunkIndex for the given family's asset.", return nullptr); + + // get actorIndex from chunkIndex + uint32_t actorIndex; + if (chunkIndex < solverAsset.getUpperSupportChunkCount()) + { + actorIndex = header->getChunkActorIndices()[chunkIndex]; + } + else + { + actorIndex = chunkIndex - (solverAsset.getUpperSupportChunkCount() - solverAsset.m_graph.m_nodeCount); + } + + // get actor from actorIndex + if (!Nv::Blast::isInvalidIndex(actorIndex)) + { + NVBLAST_ASSERT(actorIndex < header->getActorBufferSize()); + Nv::Blast::Actor* actor = &header->getActors()[actorIndex]; + if (actor->isActive()) + { + return actor; + } + } + return nullptr; +} + + +uint32_t NvBlastFamilyGetMaxActorCount(const NvBlastFamily* family, NvBlastLog logFn) +{ + NVBLAST_CHECK(family != nullptr, logFn, "NvBlastFamilyGetMaxActorCount: NULL family pointer input.", return 0); + const Nv::Blast::FamilyHeader* header = reinterpret_cast<const Nv::Blast::FamilyHeader*>(family); + return header->getActorBufferSize(); +} + +} // extern "C" diff --git a/NvBlast/sdk/lowlevel/source/NvBlastFamily.h b/NvBlast/sdk/lowlevel/source/NvBlastFamily.h new file mode 100644 index 0000000..d1cb069 --- /dev/null +++ b/NvBlast/sdk/lowlevel/source/NvBlastFamily.h @@ -0,0 +1,238 @@ +/* +* Copyright (c) 2016-2017, NVIDIA CORPORATION. All rights reserved. +* +* NVIDIA CORPORATION and its licensors retain all intellectual property +* and proprietary rights in and to this software, related documentation +* and any modifications thereto. Any use, reproduction, disclosure or +* distribution of this software and related documentation without an express +* license agreement from NVIDIA CORPORATION is strictly prohibited. +*/ + +#ifndef NVBLASTFAMILY_H +#define NVBLASTFAMILY_H + + +#include "NvBlastPreprocessorInternal.h" +#include "NvBlastAsset.h" +#include "NvBlastPreprocessor.h" +#include "NvBlastDLink.h" +#include "NvBlastAtomic.h" +#include "NvBlastMemory.h" + +#include <cstring> + + +struct NvBlastAsset; + + +namespace Nv +{ +namespace Blast +{ + +// Forward declarations +class FamilyGraph; +class Actor; +class Asset; + + +/** +Data header at the beginning of every NvBlastActor family + +The block address may be cast to a valid FamilyHeader pointer. +*/ +struct FamilyHeader : public NvBlastDataBlock +{ + /** + The ID for the asset. This will be resolved into a pointer in the runtime data. + */ + NvBlastID m_assetID; + + /** + Actors, of type Actor. + + Actors with support chunks will use this array in the range [0, m_asset->m_graphNodeCount), + while subsupport actors will be placed in the range [m_asset->m_graphNodeCount, getActorBufferSize()). + */ + NvBlastBlockArrayData(Actor, m_actorsOffset, getActors, m_asset->m_graph.m_nodeCount); + + /** + Visible chunk index links, of type IndexDLink<uint32_t>. + + getVisibleChunkIndexLinks returns an array of size m_asset->m_chunkCount of IndexDLink<uint32_t> (see IndexDLink). + */ + NvBlastBlockArrayData(IndexDLink<uint32_t>, m_visibleChunkIndexLinksOffset, getVisibleChunkIndexLinks, m_asset->m_chunkCount); + + /** + Chunk actor IDs, of type uint32_t. These correspond to the ID of the actor which owns each chunk. A value of invalidIndex<uint32_t>() indicates no owner. + + getChunkActorIndices returns an array of size m_asset->m_firstSubsupportChunkIndex. + */ + NvBlastBlockArrayData(uint32_t, m_chunkActorIndicesOffset, getChunkActorIndices, m_asset->m_firstSubsupportChunkIndex); + + /** + Graph node index links, of type uint32_t. The successor to index[i] is m_graphNodeIndexLinksOffset[i]. A value of invalidIndex<uint32_t>() indicates no successor. + + getGraphNodeIndexLinks returns an array of size m_asset->m_graphNodeCount. + */ + NvBlastBlockArrayData(uint32_t, m_graphNodeIndexLinksOffset, getGraphNodeIndexLinks, m_asset->m_graph.m_nodeCount); + + /** + Health for each support chunk and subsupport chunk, of type float. + + To access support chunks, use the corresponding graph node index in the array returned by getLowerSupportChunkHealths. + + To access subsupport chunk healths, use getSubsupportChunkHealths (see documentation for details). + */ + NvBlastBlockArrayData(float, m_lowerSupportChunkHealthsOffset, getLowerSupportChunkHealths, m_asset->getLowerSupportChunkCount()); + + /** + Utility function to get the start of the subsupport chunk health array. + + To access a subsupport chunk health indexed by i, use getSubsupportChunkHealths()[i - m_asset->m_firstSubsupportChunkIndex] + + \return the array of health values associated with all descendants of support chunks. + */ + float* getSubsupportChunkHealths() const + { + NVBLAST_ASSERT(m_asset != nullptr); + return (float*)((uintptr_t)this + m_lowerSupportChunkHealthsOffset) + m_asset->m_graph.m_nodeCount; + } + + /** + Bond health for the interfaces between two chunks, of type float. Since the bond is shared by two chunks, the same bond health is used for chunk[i] -> chunk[j] as for chunk[j] -> chunk[i]. + + getBondHealths returns the array of healths associated with all bonds in the support graph. + */ + NvBlastBlockArrayData(float, m_graphBondHealthsOffset, getBondHealths, m_asset->getBondCount()); + + /** + The instance graph for islands searching, of type FamilyGraph. + + Return the dynamic data generated for the support graph. (See FamilyGraph.) + This is used to store current connectivity information based upon bond and chunk healths, as well as cached intermediate data for faster incremental updates. + */ + NvBlastBlockData(FamilyGraph, m_familyGraphOffset, getFamilyGraph); + + + //////// Runtime data //////// + + /** + The number of actors using this block. + */ + volatile uint32_t m_actorCount; + + /** + The asset corresponding to all actors in this family. + This is runtime data and will be resolved from m_assetID. + */ + union + { + const Asset* m_asset; + uint64_t m_runtimePlaceholder; // Make sure we reserve enough room for an 8-byte pointer + }; + + + //////// Functions //////// + + /** + Gets an actor from the actor array and validates it if it is not already valid. This increments the actor reference count. + + \param[in] index The index of the actor to borrow. Must be in the range [0, getActorBufferSize()). + + \return A pointer to the indexed Actor. + */ + Actor* borrowActor(uint32_t index); + + /** + Invalidates the actor if it is not already invalid. This decrements the actor reference count, but does not free this block when the count goes to zero. + + \param[in] actor The actor to invalidate. + */ + void returnActor(Actor& actor); + + /** + Returns the total number of actors in the Actor buffer, active and inactive. + + \return the number of Actors in the actor buffer. See borrowActor. + */ + uint32_t getActorBufferSize() const; + + /** + Returns a value to indicate whether or not the Actor with the given index is valid for use (active). + + \return true iff the indexed actor is active. + */ + bool isActorActive(uint32_t index) const; +}; + +} // namespace Blast +} // namespace Nv + + +#include "NvBlastActor.h" + + +namespace Nv +{ +namespace Blast +{ + +//////// FamilyHeader inline methods //////// + +NV_INLINE Actor* FamilyHeader::borrowActor(uint32_t index) +{ + NVBLAST_ASSERT(index < getActorBufferSize()); + Actor& actor = getActors()[index]; + if (actor.m_familyOffset == 0) + { + const uintptr_t offset = (uintptr_t)&actor - (uintptr_t)this; + NVBLAST_ASSERT(offset <= UINT32_MAX); + actor.m_familyOffset = (uint32_t)offset; + atomicIncrement(reinterpret_cast<volatile int32_t*>(&m_actorCount)); + } + return &actor; +} + + +NV_INLINE void FamilyHeader::returnActor(Actor& actor) +{ + if (actor.m_familyOffset != 0) + { + actor.m_familyOffset = 0; + // The actor count should be positive since this actor was valid. Check to be safe. + NVBLAST_ASSERT(m_actorCount > 0); + atomicDecrement(reinterpret_cast<volatile int32_t*>(&m_actorCount)); + } +} + + +NV_INLINE uint32_t FamilyHeader::getActorBufferSize() const +{ + NVBLAST_ASSERT(m_asset); + return m_asset->getLowerSupportChunkCount(); +} + + +NV_INLINE bool FamilyHeader::isActorActive(uint32_t index) const +{ + NVBLAST_ASSERT(index < getActorBufferSize()); + return getActors()[index].m_familyOffset != 0; +} + + +//////// Global functions //////// + +/** +Returns the number of bytes of memory that a family created using the given asset will require. A pointer +to a block of memory of at least this size must be passed in as the mem argument of createFamily. + +\param[in] asset The asset that will be passed into NvBlastAssetCreateFamily. +*/ +size_t getFamilyMemorySize(const Asset* asset); + +} // namespace Blast +} // namespace Nv + + +#endif // ifndef NVBLASTFAMILY_H diff --git a/NvBlast/sdk/lowlevel/source/NvBlastFamilyGraph.cpp b/NvBlast/sdk/lowlevel/source/NvBlastFamilyGraph.cpp new file mode 100644 index 0000000..08ed83d --- /dev/null +++ b/NvBlast/sdk/lowlevel/source/NvBlastFamilyGraph.cpp @@ -0,0 +1,629 @@ +/* +* Copyright (c) 2016-2017, NVIDIA CORPORATION. All rights reserved. +* +* NVIDIA CORPORATION and its licensors retain all intellectual property +* and proprietary rights in and to this software, related documentation +* and any modifications thereto. Any use, reproduction, disclosure or +* distribution of this software and related documentation without an express +* license agreement from NVIDIA CORPORATION is strictly prohibited. +*/ + +#include "NvBlastFamilyGraph.h" + +#include "NvBlastAssert.h" + +#include <vector> +#include <stack> + +#define SANITY_CHECKS 0 + +namespace Nv +{ +namespace Blast +{ + + +size_t FamilyGraph::fillMemory(FamilyGraph* familyGraph, uint32_t nodeCount, uint32_t bondCount) +{ + // calculate all offsets, and dataSize as a result + NvBlastCreateOffsetStart(sizeof(FamilyGraph)); + const size_t NvBlastCreateOffsetAlign16(dirtyNodeLinksOffset, sizeof(NodeIndex) * nodeCount); + const size_t NvBlastCreateOffsetAlign16(firstDirtyNodeIndicesOffset, sizeof(uint32_t) * nodeCount); + const size_t NvBlastCreateOffsetAlign16(islandIdsOffset, sizeof(IslandId) * nodeCount); + const size_t NvBlastCreateOffsetAlign16(fastRouteOffset, sizeof(NodeIndex) * nodeCount); + const size_t NvBlastCreateOffsetAlign16(hopCountsOffset, sizeof(uint32_t) * nodeCount); + const size_t NvBlastCreateOffsetAlign16(isEdgeRemovedOffset, FixedBoolArray::requiredMemorySize(bondCount)); + const size_t NvBlastCreateOffsetAlign16(isNodeInDirtyListOffset, FixedBoolArray::requiredMemorySize(nodeCount)); + const size_t dataSize = NvBlastCreateOffsetEndAlign16(); + + // fill only if familyGraph was passed (otherwise we just used this function to get dataSize) + if (familyGraph) + { + familyGraph->m_dirtyNodeLinksOffset = static_cast<uint32_t>(dirtyNodeLinksOffset); + familyGraph->m_firstDirtyNodeIndicesOffset = static_cast<uint32_t>(firstDirtyNodeIndicesOffset); + familyGraph->m_islandIdsOffset = static_cast<uint32_t>(islandIdsOffset); + familyGraph->m_fastRouteOffset = static_cast<uint32_t>(fastRouteOffset); + familyGraph->m_hopCountsOffset = static_cast<uint32_t>(hopCountsOffset); + familyGraph->m_isEdgeRemovedOffset = static_cast<uint32_t>(isEdgeRemovedOffset); + familyGraph->m_isNodeInDirtyListOffset = static_cast<uint32_t>(isNodeInDirtyListOffset); + + new (familyGraph->getIsEdgeRemoved())FixedBoolArray(bondCount); + new (familyGraph->getIsNodeInDirtyList())FixedBoolArray(nodeCount); + } + + return dataSize; +} + + +FamilyGraph::FamilyGraph(const SupportGraph* graph) +{ + // fill memory with all internal data + // we need chunks count for size calculation + const uint32_t nodeCount = graph->m_nodeCount; + const uint32_t bondCount = graph->getAdjacencyPartition()[nodeCount] / 2; + + fillMemory(this, nodeCount, bondCount); + + // fill arrays with invalid indices / max value (0xFFFFFFFF) + memset(getIslandIds(), 0xFF, nodeCount*sizeof(uint32_t)); + memset(getFastRoute(), 0xFF, nodeCount*sizeof(uint32_t)); + memset(getHopCounts(), 0xFF, nodeCount*sizeof(uint32_t)); // Initializing to large value + memset(getDirtyNodeLinks(), 0xFF, nodeCount*sizeof(uint32_t)); // No dirty list initially + memset(getFirstDirtyNodeIndices(), 0xFF, nodeCount*sizeof(uint32_t)); + + getIsNodeInDirtyList()->clear(); + getIsEdgeRemoved()->fill(); +} + + +/** +Graph initialization, reset all internal data to initial state. Marks all nodes dirty for this actor. +First island search probably would be the longest one, as it has to traverse whole graph and set all the optimization stuff like fastRoute and hopCounts for all nodes. +*/ +void FamilyGraph::initialize(ActorIndex actorIndex, const SupportGraph* graph) +{ + // used internal data pointers + NodeIndex* dirtyNodeLinks = getDirtyNodeLinks(); + uint32_t* firstDirtyNodeIndices = getFirstDirtyNodeIndices(); + + // link dirty nodes + for (NodeIndex node = 1; node < graph->m_nodeCount; node++) + { + dirtyNodeLinks[node-1] = node; + } + firstDirtyNodeIndices[actorIndex] = 0; + + getIsNodeInDirtyList()->fill(); + getIsEdgeRemoved()->clear(); +} + + +void FamilyGraph::addToDirtyNodeList(ActorIndex actorIndex, NodeIndex node) +{ + // used internal data pointers + FixedBoolArray* isNodeInDirtyList = getIsNodeInDirtyList(); + NodeIndex* dirtyNodeLinks = getDirtyNodeLinks(); + uint32_t* firstDirtyNodeIndices = getFirstDirtyNodeIndices(); + + // check for bitmap first for avoid O(n) list search + if (isNodeInDirtyList->test(node)) + return; + + // add node to dirty node list head + dirtyNodeLinks[node] = firstDirtyNodeIndices[actorIndex]; + firstDirtyNodeIndices[actorIndex] = node; + isNodeInDirtyList->set(node); +} + + +/** +Removes fast routes and marks involved nodes as dirty +*/ +bool FamilyGraph::notifyEdgeRemoved(ActorIndex actorIndex, NodeIndex node0, NodeIndex node1, const SupportGraph* graph) +{ + NVBLAST_ASSERT(node0 < graph->m_nodeCount); + NVBLAST_ASSERT(node1 < graph->m_nodeCount); + + // used internal data pointers + NodeIndex* fastRoute = getFastRoute(); + const uint32_t* adjacencyPartition = graph->getAdjacencyPartition(); + const uint32_t* adjacentBondIndices = graph->getAdjacentBondIndices(); + + // search for bond + for (uint32_t adjacencyIndex = adjacencyPartition[node0]; adjacencyIndex < adjacencyPartition[node0 + 1]; adjacencyIndex++) + { + if (getAdjacentNode(adjacencyIndex, graph) == node1) + { + // found bond + const uint32_t bondIndex = adjacentBondIndices[adjacencyIndex]; + + // remove bond + getIsEdgeRemoved()->set(bondIndex); + + // broke fast route if it goes through this edge: + if (fastRoute[node0] == node1) + fastRoute[node0] = invalidIndex<uint32_t>(); + if (fastRoute[node1] == node0) + fastRoute[node1] = invalidIndex<uint32_t>(); + + // mark nodes dirty (add to list if doesn't exist) + addToDirtyNodeList(actorIndex, node0); + addToDirtyNodeList(actorIndex, node1); + + // we don't expect to be more than one bond between 2 nodes + return true; + } + } + + return false; +} + +bool FamilyGraph::notifyEdgeRemoved(ActorIndex actorIndex, NodeIndex node0, NodeIndex node1, uint32_t bondIndex, const SupportGraph* graph) +{ + NV_UNUSED(graph); + NVBLAST_ASSERT(node0 < graph->m_nodeCount); + NVBLAST_ASSERT(node1 < graph->m_nodeCount); + + getIsEdgeRemoved()->set(bondIndex); + + + NodeIndex* fastRoute = getFastRoute(); + + // broke fast route if it goes through this edge: + if (fastRoute[node0] == node1) + fastRoute[node0] = invalidIndex<uint32_t>(); + if (fastRoute[node1] == node0) + fastRoute[node1] = invalidIndex<uint32_t>(); + + // mark nodes dirty (add to list if doesn't exist) + addToDirtyNodeList(actorIndex, node0); + addToDirtyNodeList(actorIndex, node1); + + return true; +} + +bool FamilyGraph::notifyNodeRemoved(ActorIndex actorIndex, NodeIndex nodeIndex, const SupportGraph* graph) +{ + NVBLAST_ASSERT(nodeIndex < graph->m_nodeCount); + + // used internal data pointers + NodeIndex* fastRoute = getFastRoute(); + const uint32_t* adjacencyPartition = graph->getAdjacencyPartition(); + const uint32_t* adjacentBondIndices = graph->getAdjacentBondIndices(); + + // remove all edges leaving this node + for (uint32_t adjacencyIndex = adjacencyPartition[nodeIndex]; adjacencyIndex < adjacencyPartition[nodeIndex + 1]; adjacencyIndex++) + { + const uint32_t adjacentNodeIndex = getAdjacentNode(adjacencyIndex, graph); + if (!isInvalidIndex(adjacentNodeIndex)) + { + const uint32_t bondIndex = adjacentBondIndices[adjacencyIndex]; + getIsEdgeRemoved()->set(bondIndex); + + if (fastRoute[adjacentNodeIndex] == nodeIndex) + fastRoute[adjacentNodeIndex] = invalidIndex<uint32_t>(); + if (fastRoute[nodeIndex] == adjacentNodeIndex) + fastRoute[nodeIndex] = invalidIndex<uint32_t>(); + + addToDirtyNodeList(actorIndex, adjacentNodeIndex); + } + } + addToDirtyNodeList(actorIndex, nodeIndex); + + // ignore this node in partition (only needed for "chunk deleted from graph") + // getIslandIds()[nodeIndex] = invalidIndex<uint32_t>(); + + return true; +} + +void FamilyGraph::unwindRoute(uint32_t traversalIndex, NodeIndex lastNode, uint32_t hopCount, IslandId id, FixedArray<TraversalState>* visitedNodes) +{ + // used internal data pointers + IslandId* islandIds = getIslandIds(); + NodeIndex* fastRoute = getFastRoute(); + uint32_t* hopCounts = getHopCounts(); + + uint32_t currIndex = traversalIndex; + uint32_t hc = hopCount + 1; //Add on 1 for the hop to the witness/root node. + do + { + TraversalState& state = visitedNodes->at(currIndex); + hopCounts[state.mNodeIndex] = hc++; + islandIds[state.mNodeIndex] = id; + fastRoute[state.mNodeIndex] = lastNode; + currIndex = state.mPrevIndex; + lastNode = state.mNodeIndex; + } + while(currIndex != invalidIndex<uint32_t>()); +} + + +bool FamilyGraph::tryFastPath(NodeIndex startNode, NodeIndex targetNode, IslandId islandId, FixedArray<TraversalState>* visitedNodes, FixedBitmap* isNodeWitness, const SupportGraph* graph) +{ + NV_UNUSED(graph); + + // used internal data pointers + IslandId* islandIds = getIslandIds(); + NodeIndex* fastRoute = getFastRoute(); + + // prepare for iterating path + NodeIndex currentNode = startNode; + uint32_t visitedNotesInitialSize = visitedNodes->size(); + uint32_t depth = 0; + + bool found = false; + do + { + // witness ? + if (isNodeWitness->test(currentNode)) + { + // Already visited and not tagged with invalid island == a witness! + found = islandIds[currentNode] != invalidIndex<uint32_t>(); + break; + } + + // reached targetNode ? + if (currentNode == targetNode) + { + found = true; + break; + } + + TraversalState state(currentNode, visitedNodes->size(), visitedNodes->size() - 1, depth++); + visitedNodes->pushBack(state); + + NVBLAST_ASSERT(isInvalidIndex(fastRoute[currentNode]) || hasEdge(currentNode, fastRoute[currentNode], graph)); + + islandIds[currentNode] = invalidIndex<uint32_t>(); + isNodeWitness->set(currentNode); + + currentNode = fastRoute[currentNode]; + } while (currentNode != invalidIndex<uint32_t>()); + + for (uint32_t a = visitedNotesInitialSize; a < visitedNodes->size(); ++a) + { + TraversalState& state = visitedNodes->at(a); + islandIds[state.mNodeIndex] = islandId; + } + + // if fast path failed we have to remove all isWitness marks on visited nodes and nodes from visited list + if (!found) + { + for (uint32_t a = visitedNotesInitialSize; a < visitedNodes->size(); ++a) + { + TraversalState& state = visitedNodes->at(a); + isNodeWitness->reset(state.mNodeIndex); + } + + visitedNodes->forceSize_Unsafe(visitedNotesInitialSize); + } + + return found; +} + + +bool FamilyGraph::findRoute(NodeIndex startNode, NodeIndex targetNode, IslandId islandId, FixedArray<TraversalState>* visitedNodes, FixedBitmap* isNodeWitness, NodePriorityQueue* priorityQueue, const SupportGraph* graph) +{ + // used internal data pointers + IslandId* islandIds = getIslandIds(); + NodeIndex* fastRoute = getFastRoute(); + uint32_t* hopCounts = getHopCounts(); + const uint32_t* adjacencyPartition = graph->getAdjacencyPartition(); + + // Firstly, traverse the fast path and tag up witnesses. TryFastPath can fail. In that case, no witnesses are left but this node is permitted to report + // that it is still part of the island. Whichever node lost its fast path will be tagged as dirty and will be responsible for recovering the fast path + // and tagging up the visited nodes + if (fastRoute[startNode] != invalidIndex<uint32_t>()) + { + if (tryFastPath(startNode, targetNode, islandId, visitedNodes, isNodeWitness, graph)) + return true; + } + + // If we got here, there was no fast path. Therefore, we need to fall back on searching for the root node. This is optimized by using "hop counts". + // These are per-node counts that indicate the expected number of hops from this node to the root node. These are lazily evaluated and updated + // as new edges are formed or when traversals occur to re-establish islands. As a result, they may be inaccurate but they still serve the purpose + // of guiding our search to minimize the chances of us doing an exhaustive search to find the root node. + islandIds[startNode] = invalidIndex<uint32_t>(); + TraversalState startTraversal(startNode, visitedNodes->size(), invalidIndex<uint32_t>(), 0); + isNodeWitness->set(startNode); + QueueElement element(&visitedNodes->pushBack(startTraversal), hopCounts[startNode]); + priorityQueue->push(element); + + do + { + QueueElement currentQE = priorityQueue->pop(); + + TraversalState& currentState = *currentQE.mState; + NodeIndex& currentNode = currentState.mNodeIndex; + + // iterate all edges of currentNode + for (uint32_t adjacencyIndex = adjacencyPartition[currentNode]; adjacencyIndex < adjacencyPartition[currentNode + 1]; adjacencyIndex++) + { + NodeIndex nextIndex = getAdjacentNode(adjacencyIndex, graph); + + if (nextIndex != invalidIndex<uint32_t>()) + { + if (nextIndex == targetNode) + { + // targetNode found! + unwindRoute(currentState.mCurrentIndex, nextIndex, 0, islandId, visitedNodes); + return true; + } + + if (isNodeWitness->test(nextIndex)) + { + // We already visited this node. This means that it's either in the priority queue already or we + // visited in on a previous pass. If it was visited on a previous pass, then it already knows what island it's in. + // We now need to test the island id to find out if this node knows the root. + // If it has a valid root id, that id *is* our new root. We can guesstimate our hop count based on the node's properties + + IslandId visitedIslandId = islandIds[nextIndex]; + if (visitedIslandId != invalidIndex<uint32_t>()) + { + // If we get here, we must have found a node that knows a route to our root node. It must not be a different island + // because that would caused me to have been visited already because totally separate islands trigger a full traversal on + // the orphaned side. + NVBLAST_ASSERT(visitedIslandId == islandId); + unwindRoute(currentState.mCurrentIndex, nextIndex, hopCounts[nextIndex], islandId, visitedNodes); + return true; + } + } + else + { + // This node has not been visited yet, so we need to push it into the stack and continue traversing + TraversalState state(nextIndex, visitedNodes->size(), currentState.mCurrentIndex, currentState.mDepth + 1); + QueueElement qe(&visitedNodes->pushBack(state), hopCounts[nextIndex]); + priorityQueue->push(qe); + isNodeWitness->set(nextIndex); + NVBLAST_ASSERT(islandIds[nextIndex] == islandId); + islandIds[nextIndex] = invalidIndex<uint32_t>(); //Flag as invalid island until we know whether we can find root or an island id. + } + } + } + } while (priorityQueue->size()); + + return false; +} + + +size_t FamilyGraph::findIslandsRequiredScratch(uint32_t graphNodeCount) +{ + const size_t visitedNodesSize = align16(FixedArray<TraversalState>::requiredMemorySize(graphNodeCount)); + const size_t isNodeWitnessSize = align16(FixedBitmap::requiredMemorySize(graphNodeCount)); + const size_t priorityQueueSize = align16(NodePriorityQueue::requiredMemorySize(graphNodeCount)); + + // Aligned and padded + return 16 + visitedNodesSize + + isNodeWitnessSize + + priorityQueueSize; +} + + +uint32_t FamilyGraph::findIslands(ActorIndex actorIndex, void* scratch, const SupportGraph* graph) +{ + // check if we have at least 1 dirty node for this actor before proceeding + uint32_t* firstDirtyNodeIndices = getFirstDirtyNodeIndices(); + if (isInvalidIndex(firstDirtyNodeIndices[actorIndex])) + return 0; + + // used internal data pointers + IslandId* islandIds = getIslandIds(); + NodeIndex* fastRoute = getFastRoute(); + uint32_t* hopCounts = getHopCounts(); + NodeIndex* dirtyNodeLinks = getDirtyNodeLinks(); + FixedBoolArray* isNodeInDirtyList = getIsNodeInDirtyList(); + + // prepare intermediate data on scratch + scratch = (void*)align16((size_t)scratch); // Bump to 16-byte alignment (see padding in findIslandsRequiredScratch) + const uint32_t nodeCount = graph->m_nodeCount; + + FixedArray<TraversalState>* visitedNodes = new (scratch)FixedArray<TraversalState>(); + scratch = pointerOffset(scratch, align16(FixedArray<TraversalState>::requiredMemorySize(nodeCount))); + + FixedBitmap* isNodeWitness = new (scratch)FixedBitmap(nodeCount); + scratch = pointerOffset(scratch, align16(FixedBitmap::requiredMemorySize(nodeCount))); + + NodePriorityQueue* priorityQueue = new (scratch)NodePriorityQueue(); + scratch = pointerOffset(scratch, align16(NodePriorityQueue::requiredMemorySize(nodeCount))); + + // reset nodes visited bitmap + isNodeWitness->clear(); + + uint32_t newIslandsCount = 0; + + while (!isInvalidIndex(firstDirtyNodeIndices[actorIndex])) + { + // Pop head off of dirty node's list + const NodeIndex dirtyNode = firstDirtyNodeIndices[actorIndex]; + firstDirtyNodeIndices[actorIndex] = dirtyNodeLinks[dirtyNode]; + dirtyNodeLinks[dirtyNode] = invalidIndex<uint32_t>(); + NVBLAST_ASSERT(isNodeInDirtyList->test(dirtyNode)); + isNodeInDirtyList->reset(dirtyNode); + + // clear PriorityQueue + priorityQueue->clear(); + + // if we already visited this node before in this loop it's not dirty anymore + if (isNodeWitness->test(dirtyNode)) + continue; + + NodeIndex& islandRootNode = islandIds[dirtyNode]; + IslandId islandId = islandRootNode; // the same in this implementation + + // if this node is island root node we don't need to do anything + if (islandRootNode == dirtyNode) + continue; + + // clear visited notes list (to fill during traverse) + visitedNodes->clear(); + + // try finding island root node from this dirtyNode + if (findRoute(dirtyNode, islandRootNode, islandId, visitedNodes, isNodeWitness, priorityQueue, graph)) + { + // We found the root node so let's let every visited node know that we found its root + // and we can also update our hop counts because we recorded how many hops it took to reach this + // node + + // We already filled in the path to the root/witness with accurate hop counts. Now we just need to fill in the estimates + // for the remaining nodes and re-define their islandIds. We approximate their path to the root by just routing them through + // the route we already found. + + // This loop works because visitedNodes are recorded in the order they were visited and we already filled in the critical path + // so the remainder of the paths will just fork from that path. + for (uint32_t b = 0; b < visitedNodes->size(); ++b) + { + TraversalState& state = visitedNodes->at(b); + if (isInvalidIndex(islandIds[state.mNodeIndex])) + { + hopCounts[state.mNodeIndex] = hopCounts[visitedNodes->at(state.mPrevIndex).mNodeIndex] + 1; + fastRoute[state.mNodeIndex] = visitedNodes->at(state.mPrevIndex).mNodeIndex; + islandIds[state.mNodeIndex] = islandId; + } + } + } + else + { + // NEW ISLAND BORN! + + // If I traversed and could not find the root node, then I have established a new island. In this island, I am the root node + // and I will point all my nodes towards me. Furthermore, I have established how many steps it took to reach all nodes in my island + + // OK. We need to separate the islands. We have a list of nodes that are part of the new island (visitedNodes) and we know that the + // first node in that list is the root node. + +#if SANITY_CHECKS + NVBLAST_ASSERT(!canFindRoot(dirtyNode, islandRootNode, NULL)); +#endif + + IslandId newIsland = dirtyNode; + newIslandsCount++; + + hopCounts[dirtyNode] = 0; + fastRoute[dirtyNode] = invalidIndex<uint32_t>(); + islandIds[dirtyNode] = newIsland; + + for (uint32_t a = 1; a < visitedNodes->size(); ++a) + { + NodeIndex visitedNode = visitedNodes->at(a).mNodeIndex; + hopCounts[visitedNode] = visitedNodes->at(a).mDepth; //How many hops to root + fastRoute[visitedNode] = visitedNodes->at(visitedNodes->at(a).mPrevIndex).mNodeIndex; + islandIds[visitedNode] = newIsland; + } + } + } + + // all dirty nodes processed + return newIslandsCount; +} + + +/** +!!! Debug/Test function. +Function to check that root between nodes exists. +*/ +bool FamilyGraph::canFindRoot(NodeIndex startNode, NodeIndex targetNode, FixedArray<NodeIndex>* visitedNodes, const SupportGraph* graph) +{ + if (visitedNodes) + visitedNodes->pushBack(startNode); + + if (startNode == targetNode) + return true; + + std::vector<bool> visitedState; + visitedState.resize(graph->m_nodeCount); + for (uint32_t i = 0; i < graph->m_nodeCount; i++) + visitedState[i] = false; + + std::stack<NodeIndex> stack; + + stack.push(startNode); + visitedState[startNode] = true; + + const uint32_t* adjacencyPartition = graph->getAdjacencyPartition(); + do + { + NodeIndex currentNode = stack.top(); + stack.pop(); + + for (uint32_t adjacencyIndex = adjacencyPartition[currentNode]; adjacencyIndex < adjacencyPartition[currentNode + 1]; adjacencyIndex++) + { + NodeIndex nextNode = getAdjacentNode(adjacencyIndex, graph); + + if (isInvalidIndex(nextNode)) + continue; + + if (!visitedState[nextNode]) + { + if (nextNode == targetNode) + { + return true; + } + + visitedState[nextNode] = true; + stack.push(nextNode); + + if (visitedNodes) + visitedNodes->pushBack(nextNode); + } + } + + } while (!stack.empty()); + + return false; +} + + +/** +!!! Debug/Test function. +Function to check if edge exists. +*/ +bool FamilyGraph::hasEdge(NodeIndex node0, NodeIndex node1, const SupportGraph* graph) const +{ + const uint32_t* adjacencyPartition = graph->getAdjacencyPartition(); + uint32_t edges = 0; + for (uint32_t adjacencyIndex = adjacencyPartition[node0]; adjacencyIndex < adjacencyPartition[node0 + 1]; adjacencyIndex++) + { + if (getAdjacentNode(adjacencyIndex, graph) == node1) + { + edges++; + break; + } + } + for (uint32_t adjacencyIndex = adjacencyPartition[node1]; adjacencyIndex < adjacencyPartition[node1 + 1]; adjacencyIndex++) + { + if (getAdjacentNode(adjacencyIndex, graph) == node0) + { + edges++; + break; + } + } + return edges > 0; +} + + +/** +!!! Debug/Test function. +Function to calculate and return edges count +*/ +uint32_t FamilyGraph::getEdgesCount(const SupportGraph* graph) const +{ + const uint32_t* adjacencyPartition = graph->getAdjacencyPartition(); + uint32_t edges = 0; + for (NodeIndex n = 0; n < graph->m_nodeCount; n++) + { + for (uint32_t adjacencyIndex = adjacencyPartition[n]; adjacencyIndex < adjacencyPartition[n + 1]; adjacencyIndex++) + { + if (getAdjacentNode(adjacencyIndex, graph) != invalidIndex<uint32_t>()) + edges++; + } + } + NVBLAST_ASSERT(edges % 2 == 0); + return edges / 2; +} + + + + +} // namespace Nv +} // namespace Blast + diff --git a/NvBlast/sdk/lowlevel/source/NvBlastFamilyGraph.h b/NvBlast/sdk/lowlevel/source/NvBlastFamilyGraph.h new file mode 100644 index 0000000..9fa331a --- /dev/null +++ b/NvBlast/sdk/lowlevel/source/NvBlastFamilyGraph.h @@ -0,0 +1,280 @@ +/* +* Copyright (c) 2016-2017, NVIDIA CORPORATION. All rights reserved. +* +* NVIDIA CORPORATION and its licensors retain all intellectual property +* and proprietary rights in and to this software, related documentation +* and any modifications thereto. Any use, reproduction, disclosure or +* distribution of this software and related documentation without an express +* license agreement from NVIDIA CORPORATION is strictly prohibited. +*/ + +#ifndef NVBLASTFAMILYGRAPH_H +#define NVBLASTFAMILYGRAPH_H + + +#include "NvBlastSupportGraph.h" +#include "NvBlastFixedArray.h" +#include "NvBlastFixedBitmap.h" +#include "NvBlastFixedBoolArray.h" +#include "NvBlastMath.h" +#include "NvBlastFixedPriorityQueue.h" +#include "NvBlastPreprocessorInternal.h" +#include "NvBlastMemory.h" + + +namespace Nv +{ +namespace Blast +{ + + +typedef uint32_t NodeIndex; +typedef NodeIndex IslandId; +typedef uint32_t ActorIndex; + +/** +Internal implementation of family graph stored on the family. + +It processes full NvBlastSupportGraph graph, stores additional information used for faster islands finding, +keeps and provides access to current islandId for every node. +*/ +class FamilyGraph +{ +public: + + //////// ctor //////// + + /** + Constructor. family graph is meant to be placed (with placement new) on family memory. + + \param[in] graph The graph to instance (see SupportGraph) + */ + FamilyGraph(const SupportGraph* graph); + + + /** + Returns memory needed for this class (see fillMemory). + + \param[in] nodeCount The number of nodes in the graph. + \param[in] bondCount The number of bonds in the graph. + + \return the number of bytes required. + */ + static size_t requiredMemorySize(uint32_t nodeCount, uint32_t bondCount) + { + return fillMemory(nullptr, nodeCount, bondCount); + } + + + //////// API //////// + + /** + Function to initialize graph (all nodes added to dirty list for this actor) + + \param[in] actorIndex The index of the actor to initialize graph with. Must be in the range [0, m_nodeCount). + \param[in] graph The static graph data for this family. + */ + void initialize(ActorIndex actorIndex, const SupportGraph* graph); + + /** + Function to notify graph about removed edges. These nodes will be added to dirty list for this actor. Returns true if bond as removed. + + \param[in] actorIndex The index of the actor from which the edge is removed. Must be in the range [0, m_nodeCount). + \param[in] node0 The index of the first node of removed edge. Must be in the range [0, m_nodeCount). + \param[in] node1 The index of the second node of removed edge. Must be in the range [0, m_nodeCount). + \param[in] graph The static graph data for this family. + */ + bool notifyEdgeRemoved(ActorIndex actorIndex, NodeIndex node0, NodeIndex node1, const SupportGraph* graph); + bool notifyEdgeRemoved(ActorIndex actorIndex, NodeIndex node0, NodeIndex node1, uint32_t bondIndex, const SupportGraph* graph); + + bool notifyNodeRemoved(ActorIndex actorIndex, NodeIndex nodeIndex, const SupportGraph* graph); + + /** + Function to find new islands by examining dirty nodes associated with this actor (they can be associated with actor if + notifyEdgeRemoved() were previously called for it. + + \param[in] actorIndex The index of the actor on which graph part (edges + nodes) findIslands will be performed. Must be in the range [0, m_nodeCount). + \param[in] scratch User-supplied scratch memory of size findIslandsRequiredScratch(graphNodeCount) bytes. + \param[in] graph The static graph data for this family. + + \return the number of new islands found. + */ + uint32_t findIslands(ActorIndex actorIndex, void* scratch, const SupportGraph* graph); + + /** + The scratch space required to call the findIslands function, in bytes. + + \param[in] graphNodeCount The number of nodes in the graph. + + \return the number of bytes required. + */ + static size_t findIslandsRequiredScratch(uint32_t graphNodeCount); + + + //////// data getters //////// + + /** + Utility function to get the start of the island ids array. This is an array of size nodeCount. + Every islandId == NodeIndex of root node in this island, it is set for every Node. + + \return the array of island ids. + */ + NvBlastBlockData(IslandId, m_islandIdsOffset, getIslandIds); + + /** + Utility function to get the start of the dirty node links array. This is an array of size nodeCount. + */ + NvBlastBlockData(NodeIndex, m_dirtyNodeLinksOffset, getDirtyNodeLinks); + + /** + Utility function to get the start of the first dirty node indices array. This is an array of size nodeCount. + */ + NvBlastBlockData(uint32_t, m_firstDirtyNodeIndicesOffset, getFirstDirtyNodeIndices); + + /** + Utility function to get the start of the fast route array. This is an array of size nodeCount. + */ + NvBlastBlockData(NodeIndex, m_fastRouteOffset, getFastRoute); + + /** + Utility function to get the start of the hop counts array. This is an array of size nodeCount. + */ + NvBlastBlockData(uint32_t, m_hopCountsOffset, getHopCounts); + + /** + Utility function to get the pointer of the is edge removed bitmap. This is an bitmap of size bondCount. + */ + NvBlastBlockData(FixedBoolArray, m_isEdgeRemovedOffset, getIsEdgeRemoved); + + /** + Utility function to get the pointer of the is node in dirty list bitmap. This is an bitmap of size nodeCount. + */ + NvBlastBlockData(FixedBoolArray, m_isNodeInDirtyListOffset, getIsNodeInDirtyList); + + + //////// Debug/Test //////// + + uint32_t getEdgesCount(const SupportGraph* graph) const; + bool hasEdge(NodeIndex node0, NodeIndex node1, const SupportGraph* graph) const; + bool canFindRoot(NodeIndex startNode, NodeIndex targetNode, FixedArray<NodeIndex>* visitedNodes, const SupportGraph* graph); + + +private: + + FamilyGraph& operator = (const FamilyGraph&); + + //////// internal types //////// + + /** + Used to represent current graph traverse state. + */ + struct TraversalState + { + NodeIndex mNodeIndex; + uint32_t mCurrentIndex; + uint32_t mPrevIndex; + uint32_t mDepth; + + TraversalState() + { + } + + TraversalState(NodeIndex nodeIndex, uint32_t currentIndex, uint32_t prevIndex, uint32_t depth) : + mNodeIndex(nodeIndex), mCurrentIndex(currentIndex), mPrevIndex(prevIndex), mDepth(depth) + { + } + }; + + /** + Queue element for graph traversal with priority queue. + */ + struct QueueElement + { + TraversalState* mState; + uint32_t mHopCount; + + QueueElement() + { + } + + QueueElement(TraversalState* state, uint32_t hopCount) : mState(state), mHopCount(hopCount) + { + } + }; + + /** + Queue comparator for graph traversal with priority queue. + */ + struct NodeComparator + { + NodeComparator() + { + } + + bool operator() (const QueueElement& node0, const QueueElement& node1) const + { + return node0.mHopCount < node1.mHopCount; + } + private: + NodeComparator& operator = (const NodeComparator&); + }; + + /** + PriorityQueue for graph traversal. Queue element with smallest hopCounts will be always on top. + */ + typedef FixedPriorityQueue<QueueElement, NodeComparator> NodePriorityQueue; + + + //////// internal operations //////// + + /** + Function calculate needed memory and feel it if familyGraph is passed. FamilyGraph is designed to use + memory right after itself. So it should be initialized with placement new operation on memory of memoryNeeded() size. + + \param[in] familyGraph The pointer to actual FamilyGraph instance which will be filled. Can be nullptr, function will only return required bytes and do nothing. + \param[in] nodeCount The number of nodes in the graph. + \param[in] bondCount The number of bonds in the graph. + + \return the number of bytes required or filled + */ + static size_t fillMemory(FamilyGraph* familyGraph, uint32_t nodeCount, uint32_t bondCount); + + /** + Function to find route from on node to another. It uses fastPath first as optimization and then if it fails it performs brute-force traverse (with hop count heuristic) + */ + bool findRoute(NodeIndex startNode, NodeIndex targetNode, IslandId islandId, FixedArray<TraversalState>* visitedNodes, FixedBitmap* isNodeWitness, NodePriorityQueue* priorityQueue, const SupportGraph* graph); + + /** + Function to try finding targetNode (from startNode) with getFastRoute(). + */ + bool tryFastPath(NodeIndex startNode, NodeIndex targetNode, IslandId islandId, FixedArray<TraversalState>* visitedNodes, FixedBitmap* isNodeWitness, const SupportGraph* graph); + + /** + Function to unwind route upon successful finding of root node or witness. + We have found either a witness *or* the root node with this traversal. In the event of finding the root node, hopCount will be 0. In the event of finding + a witness, hopCount will be the hopCount that witness reported as being the distance to the root. + */ + void unwindRoute(uint32_t traversalIndex, NodeIndex lastNode, uint32_t hopCount, IslandId id, FixedArray<TraversalState>* visitedNodes); + + /** + Function to add node to dirty node list associated with actor. + */ + void addToDirtyNodeList(ActorIndex actorIndex, NodeIndex node); + + /** + Function used to get adjacentNode using index from adjacencyPartition with check for bondHealths (if it's not removed already) + */ + NodeIndex getAdjacentNode(uint32_t adjacencyIndex, const SupportGraph* graph) const + { + const uint32_t bondIndex = graph->getAdjacentBondIndices()[adjacencyIndex]; + return getIsEdgeRemoved()->test(bondIndex) ? invalidIndex<uint32_t>() : graph->getAdjacentNodeIndices()[adjacencyIndex]; + } + +}; + + +} // namespace Blast +} // namespace Nv + + +#endif // ifndef NVBLASTFAMILYGRAPH_H diff --git a/NvBlast/sdk/lowlevel/source/NvBlastSupportGraph.h b/NvBlast/sdk/lowlevel/source/NvBlastSupportGraph.h new file mode 100644 index 0000000..9ee3fc9 --- /dev/null +++ b/NvBlast/sdk/lowlevel/source/NvBlastSupportGraph.h @@ -0,0 +1,134 @@ +/* +* Copyright (c) 2016-2017, NVIDIA CORPORATION. All rights reserved. +* +* NVIDIA CORPORATION and its licensors retain all intellectual property +* and proprietary rights in and to this software, related documentation +* and any modifications thereto. Any use, reproduction, disclosure or +* distribution of this software and related documentation without an express +* license agreement from NVIDIA CORPORATION is strictly prohibited. +*/ + +#ifndef NVBLASTSUPPORTGRAPH_H +#define NVBLASTSUPPORTGRAPH_H + + +#include "NvBlastIndexFns.h" +#include "NvBlastPreprocessorInternal.h" +#include "NvBlastMemory.h" + +namespace Nv +{ +namespace Blast +{ + +/** +Describes the connectivity between support chunks via bonds. + +Vertices in the support graph are termed "nodes," and represent particular chunks (NvBlastChunk) in an NvBlastAsset. +The indexing for nodes is not the same as that for chunks. Only some chunks are represented by nodes in the graph, +and these chunks are called "support chunks." + +Adjacent node indices and adjacent bond indices are stored for each node, and therefore each bond is represented twice in this graph, +going from node[i] -> node[j] and from node[j] -> node[i]. Therefore the size of the getAdjacentNodeIndices() and getAdjacentBondIndices() +arrays are twice the number of bonds stored in the corresponding NvBlastAsset. + +The graph is used as follows. Given a SupportGraph "graph" and node index i, (0 <= i < graph.nodeCount), one may find all +adjacent bonds and nodes using: + + const uint32_t* adjacencyPartition = graph.getAdjacencyPartition(); + const uint32_t* adjacentNodeIndices = graph.getAdjacentNodeIndices(); + const uint32_t* adjacentBondIndices = graph.getAdjacentBondIndices(); + + // adj is the lookup value in adjacentNodeIndices and graph.getAdjacentBondIndices() + for (uint32_t adj = adjacencyPartition[i]; adj < adjacencyPartition[i+1]; ++adj) + { + // An adjacent node: + uint32_t adjacentNodeIndex = adjacentNodeIndices[adj]; + + // The corresponding bond (that connects node index i with node indexed adjacentNodeIndex: + uint32_t adjacentBondIndex = adjacentBondIndices[adj]; + } + +For a graph node with index i, the corresponding asset chunk index is found using graph.getChunkIndices()[i]. The reverse mapping +(obtaining a graph node index from an asset chunk index) can be done using the + + NvBlastAssetGetChunkToGraphNodeMap(asset, logFn); + +function. See the documentation for its use. The returned "node index" for a non-support chunk is the invalid value 0xFFFFFFFF. +*/ +struct SupportGraph +{ + /** + Total number of nodes in the support graph. + */ + uint32_t m_nodeCount; + + /** + Indices of chunks represented by the nodes. + + getChunkIndices returns an array of size m_nodeCount. + */ + NvBlastBlockArrayData(uint32_t, m_chunkIndicesOffset, getChunkIndices, m_nodeCount); + + /** + Adjacency lookup table, of type uint32_t. + + Partitions both the getAdjacentNodeIndices() and the getAdjacentBondIndices() arrays into subsets corresponding to each node. + The size of this array is nodeCount+1. + For 0 <= i < nodeCount, getAdjacencyPartition()[i] is the index of the first element in getAdjacentNodeIndices() (or getAdjacentBondIndices()) for nodes adjacent to the node with index i. + getAdjacencyPartition()[nodeCount] is the size of the getAdjacentNodeIndices() and getAdjacentBondIndices() arrays. + This allows one to easily count the number of nodes adjacent to a node with index i, using getAdjacencyPartition()[i+1] - getAdjacencyPartition()[i]. + + getAdjacencyPartition returns an array of size m_nodeCount + 1. + */ + NvBlastBlockArrayData(uint32_t, m_adjacencyPartitionOffset, getAdjacencyPartition, m_nodeCount + 1); + + /** + Array of uint32_t composed of subarrays holding the indices of nodes adjacent to a given node. The subarrays may be accessed through the getAdjacencyPartition() array. + + getAdjacentNodeIndices returns an array of size getAdjacencyPartition()[m_nodeCount]. + */ + NvBlastBlockArrayData(uint32_t, m_adjacentNodeIndicesOffset, getAdjacentNodeIndices, getAdjacencyPartition()[m_nodeCount]); + + /** + Array of uint32_t composed of subarrays holding the indices of bonds (NvBlastBond) for a given node. The subarrays may be accessed through the getAdjacencyPartition() array. + + getAdjacentBondIndices returns an array of size getAdjacencyPartition()[m_nodeCount]. + */ + NvBlastBlockArrayData(uint32_t, m_adjacentBondIndicesOffset, getAdjacentBondIndices, getAdjacencyPartition()[m_nodeCount]); + + /** + Finds the bond between two given graph nodes (if it exists) and returns the bond index. + If no bond exists, returns invalidIndex<uint32_t>(). + + \return the index of the bond between the given nodes. + */ + uint32_t findBond(uint32_t nodeIndex0, uint32_t nodeIndex1) const; +}; + + +//////// SupportGraph inline member functions //////// + +NV_INLINE uint32_t SupportGraph::findBond(uint32_t nodeIndex0, uint32_t nodeIndex1) const +{ + const uint32_t* adjacencyPartition = getAdjacencyPartition(); + const uint32_t* adjacentNodeIndices = getAdjacentNodeIndices(); + const uint32_t* adjacentBondIndices = getAdjacentBondIndices(); + + // Iterate through all neighbors of nodeIndex0 chunk + for (uint32_t i = adjacencyPartition[nodeIndex0]; i < adjacencyPartition[nodeIndex0 + 1]; i++) + { + if (adjacentNodeIndices[i] == nodeIndex1) + { + return adjacentBondIndices[i]; + } + } + + return invalidIndex<uint32_t>(); +} + +} // namespace Blast +} // namespace Nv + + +#endif // ifndef NVBLASTSUPPORTGRAPH_H |