From 9f4fc41dc5d857e3c7c3500fc71953e54d780a39 Mon Sep 17 00:00:00 2001 From: Bryan Galdrikian Date: Tue, 17 Sep 2019 09:16:55 -0700 Subject: * NvBlastAsset::testForValidChunkOrder (used when creating an NvBlastAsset) is now more strict, requiring parent chunk descriptors to come before their children. It is still less strict than the order created by NvBlastBuildAssetDescChunkReorderMap. * Added FractureTool::setApproximateBonding function. Signals the tool to create bonds by proximity instead of just using cut plane data. * Chunks which have been merged using the uniteChunks function may be merged again * Restored chunk volume calculation * NvBlastBuildAssetDescChunkReorderMap failure cases fixed. --- .../include/NvBlastExtAuthoringFractureTool.h | 14 ++- .../authoring/source/NvBlastExtAuthoring.cpp | 29 +++-- .../NvBlastExtAuthoringBondGeneratorImpl.cpp | 20 +-- .../source/NvBlastExtAuthoringFractureToolImpl.cpp | 76 +++++++++-- .../source/NvBlastExtAuthoringFractureToolImpl.h | 2 + .../source/NvBlastExtAuthoringInternalCommon.h | 42 +++++++ sdk/lowlevel/include/NvBlast.h | 2 +- sdk/lowlevel/source/NvBlastAsset.cpp | 78 ++++++------ sdk/lowlevel/source/NvBlastAsset.h | 31 ++--- sdk/lowlevel/source/NvBlastAssetHelper.cpp | 139 +++++++++++++++------ 10 files changed, 307 insertions(+), 126 deletions(-) (limited to 'sdk') diff --git a/sdk/extensions/authoring/include/NvBlastExtAuthoringFractureTool.h b/sdk/extensions/authoring/include/NvBlastExtAuthoringFractureTool.h index 55b15f5..0798f95 100755 --- a/sdk/extensions/authoring/include/NvBlastExtAuthoringFractureTool.h +++ b/sdk/extensions/authoring/include/NvBlastExtAuthoringFractureTool.h @@ -48,8 +48,8 @@ struct ChunkInfo { enum ChunkFlags { - NO_FLAGS = 0, - CREATED_BY_ISLAND_DETECTOR = 1 + NO_FLAGS = 0, + APPROXIMATE_BONDING = 1 // Created by island splitting or chunk merge, etc. and should check for inexact bonds }; Mesh* meshData; @@ -512,7 +512,15 @@ class FractureTool const NvcVec2i* adjChunks, uint32_t adjChunksSize, bool removeOriginalChunks = false) = 0; - /** + /** + Set the APPROXIMATE_BONDING flag in the chunk's ChunkInfo + \param[in] chunkIndex chunk index - use getChunkIndex(ID) + \param[in] useApproximateBonding value of flag to set + \return true if the chunk ID is found, false otherwise + */ + virtual bool setApproximateBonding(uint32_t chunkIndex, bool useApproximateBonding) = 0; + + /** Rescale interior uv coordinates of given chunk to fit square of given size. \param[in] side Size of square side \param[in] chunkId Chunk ID for which UVs should be scaled. diff --git a/sdk/extensions/authoring/source/NvBlastExtAuthoring.cpp b/sdk/extensions/authoring/source/NvBlastExtAuthoring.cpp index a0e6fc2..b26eee3 100755 --- a/sdk/extensions/authoring/source/NvBlastExtAuthoring.cpp +++ b/sdk/extensions/authoring/source/NvBlastExtAuthoring.cpp @@ -40,6 +40,7 @@ #include "NvBlastExtAuthoringBondGeneratorImpl.h" #include "NvBlastExtAuthoringCollisionBuilderImpl.h" #include "NvBlastExtAuthoringCutoutImpl.h" +#include "NvBlastExtAuthoringInternalCommon.h" #include "NvBlastPxSharedHelpers.h" #include @@ -381,21 +382,19 @@ AuthoringResult* NvBlastExtAuthoringProcessFracture(FractureTool& fTool, BlastBo buildPhysicsChunks(collisionBuilder, aResult, collisionParam); // set NvBlastChunk volume from Px geometry - //for (uint32_t i = 0; i < chunkCount; i++) - //{ - // float totalVolume = 0.f; - // for (uint32_t k = 0; k < aResult.physicsChunks[i].subchunkCount; k++) - // { - // const auto& subChunk = aResult.physicsSubchunks[aResult.physicsChunks[i].firstSubchunkIndex + k]; - // physx::PxVec3 localCenterOfMass; physx::PxMat33 intertia; float mass; - // subChunk.geometry.convexMesh->getMassInformation(mass, intertia, localCenterOfMass); - // const physx::PxVec3 scale = subChunk.geometry.scale.scale; - // mass *= scale.x * scale.y * scale.z; - // totalVolume += mass / 1.0f; // unit density - // } - - // aResult.chunkDescs[i].volume = totalVolume; - //} + for (uint32_t i = 0; i < chunkCount; i++) + { + float totalVolume = 0.f; + for (uint32_t k = aResult.collisionHullOffset[i]; k < aResult.collisionHullOffset[i+1]; k++) + { + const CollisionHull* hull = aResult.collisionHull[k]; + if (hull) + { + totalVolume += calculateCollisionHullVolume(*hull); + } + } + aResult.chunkDescs[i].volume = totalVolume; + } // build and serialize ExtPhysicsAsset NvBlastAssetDesc descriptor; diff --git a/sdk/extensions/authoring/source/NvBlastExtAuthoringBondGeneratorImpl.cpp b/sdk/extensions/authoring/source/NvBlastExtAuthoringBondGeneratorImpl.cpp index bda11e9..1fc61c2 100755 --- a/sdk/extensions/authoring/source/NvBlastExtAuthoringBondGeneratorImpl.cpp +++ b/sdk/extensions/authoring/source/NvBlastExtAuthoringBondGeneratorImpl.cpp @@ -1091,15 +1091,15 @@ int32_t BlastBondGeneratorImpl::buildDescFromInternalFracture(FractureTool* tool } - bool hasCreatedByIslands = false; + bool hasApproximateBonding = false; for (uint32_t i = 1; i < chunkCount; ++i) { NvBlastChunkDesc& desc = resultChunkDescriptors[i]; - desc.userData = i; + desc.userData = tool->getChunkId(i); desc.parentChunkIndex = tool->getChunkIndex(tool->getChunkInfo(i).parent); desc.flags = NvBlastChunkDesc::NoFlags; - hasCreatedByIslands |= (tool->getChunkInfo(i).flags & ChunkInfo::CREATED_BY_ISLAND_DETECTOR); + hasApproximateBonding |= !!(tool->getChunkInfo(i).flags & ChunkInfo::APPROXIMATE_BONDING); if (chunkIsSupport[i]) { desc.flags = NvBlastChunkDesc::SupportFlag; @@ -1246,7 +1246,7 @@ int32_t BlastBondGeneratorImpl::buildDescFromInternalFracture(FractureTool* tool } } - if (hasCreatedByIslands) + if (hasApproximateBonding) { std::vector chunkTriangles; std::vector chunkTrianglesOffsets; @@ -1262,6 +1262,7 @@ int32_t BlastBondGeneratorImpl::buildDescFromInternalFracture(FractureTool* tool pairsAlreadyCreated.insert(pr); } + const float EXPANSION = 0.01f; chunkTrianglesOffsets.push_back(0); for (uint32_t i = 0; i < chunkCount; ++i) @@ -1273,18 +1274,19 @@ int32_t BlastBondGeneratorImpl::buildDescFromInternalFracture(FractureTool* tool { chunkTriangles.push_back(trianglesBuffer[i].get()[k]); - chunkTriangles.back().a.p = - (chunkTriangles.back().a.p - centroid) * SCALE_FACTOR + centroid; // inflate mesh a bit to find - } + // inflate mesh a bit + chunkTriangles.back().a.p = chunkTriangles.back().a.p + (chunkTriangles.back().a.p - centroid) * EXPANSION; + chunkTriangles.back().b.p = chunkTriangles.back().b.p + (chunkTriangles.back().b.p - centroid) * EXPANSION; + chunkTriangles.back().c.p = chunkTriangles.back().c.p + (chunkTriangles.back().c.p - centroid) * EXPANSION; + } chunkTrianglesOffsets.push_back(chunkTriangles.size()); } NvBlastBondDesc* adsc; - BondGenerationConfig cfg; cfg.bondMode = BondGenerationConfig::AVERAGE; - cfg.maxSeparation = 0.01f; + cfg.maxSeparation = EXPANSION; uint32_t nbListSize = createFullBondListAveraged(chunkCount, chunkTrianglesOffsets.data(), chunkTriangles.data(), nullptr, diff --git a/sdk/extensions/authoring/source/NvBlastExtAuthoringFractureToolImpl.cpp b/sdk/extensions/authoring/source/NvBlastExtAuthoringFractureToolImpl.cpp index e4cc86f..a5cd4c1 100755 --- a/sdk/extensions/authoring/source/NvBlastExtAuthoringFractureToolImpl.cpp +++ b/sdk/extensions/authoring/source/NvBlastExtAuthoringFractureToolImpl.cpp @@ -1628,6 +1628,7 @@ bool FractureToolImpl::deleteChunkSubhierarchy(int32_t chunkId, bool deleteRoot std::swap(mChunkData.back(), mChunkData[m]); mChunkData.pop_back(); } + markLeaves(); return chunkToDelete.size() > 0; } @@ -1688,7 +1689,10 @@ void FractureToolImpl::finalizeFracturing() std::swap(mChunkData[badOnes[i]], mChunkData.back()); mChunkData.pop_back(); } - fitAllUvToRect(1.0f, newChunkMask); + if (!mChunkPostprocessors.empty()) // Failsafe to prevent infinite loop (leading to stack overflow) + { + fitAllUvToRect(1.0f, newChunkMask); + } } uint32_t FractureToolImpl::getChunkCount() const @@ -1750,13 +1754,26 @@ uint32_t FractureToolImpl::updateBaseMesh(int32_t chunkIndex, Triangle* output) float getVolume(std::vector& triangles) { + if (triangles.size() == 0) + { + return 0.0f; + } + + // Find an approximate centroid for a more accurate calculation + NvcVec3 centroid = { 0.0f, 0.0f, 0.0f }; + for (size_t i = 0; i < triangles.size(); ++i) + { + centroid = centroid + triangles[i].a.p + triangles[i].b.p + triangles[i].c.p; + } + centroid = centroid / (3 * triangles.size()); + float volume = 0.0f; - for (uint32_t i = 0; i < triangles.size(); ++i) + for (size_t i = 0; i < triangles.size(); ++i) { - NvcVec3& a = triangles[i].a.p; - NvcVec3& b = triangles[i].b.p; - NvcVec3& c = triangles[i].c.p; + const NvcVec3 a = triangles[i].a.p - centroid; + const NvcVec3 b = triangles[i].b.p - centroid; + const NvcVec3 c = triangles[i].c.p - centroid; volume += (a.x * b.y * c.z - a.x * b.z * c.y - a.y * b.x * c.z + a.y * b.z * c.x + a.z * b.x * c.y - a.z * b.y * c.x); } @@ -1988,19 +2005,19 @@ int32_t FractureToolImpl::islandDetectionAndRemoving(int32_t chunkId, bool creat } else { - mChunkData[chunkIndex].isLeaf = false; deleteChunkSubhierarchy(chunkId); for (int32_t i = 0; i < cComp; ++i) { uint32_t nc = createNewChunk(chunkId); mChunkData[nc].isLeaf = true; - mChunkData[nc].flags = ChunkInfo::CREATED_BY_ISLAND_DETECTOR; + mChunkData[nc].flags = ChunkInfo::APPROXIMATE_BONDING; mChunkData[nc].meshData = new MeshImpl(compVertices[i].data(), compEdges[i].data(), compFacets[i].data(), static_cast(compVertices[i].size()), static_cast(compEdges[i].size()), static_cast(compFacets[i].size())); } - } + mChunkData[chunkIndex].isLeaf = false; + } return cComp; } return 0; @@ -2110,7 +2127,12 @@ uint32_t FractureToolImpl::stretchGroup(const std::vector& grp, std::v } offsetEdges = nEdges.size(); offsetVertices = nVertices.size(); - } + + if (mChunkData[grp[i]].flags & ChunkInfo::APPROXIMATE_BONDING) + { + mChunkData[newChunkIndex].flags |= ChunkInfo::APPROXIMATE_BONDING; + } + } std::vector finalFacets; std::set hasCutting; for (uint32_t i = 0; i < nFacets.size(); ++i) @@ -2129,6 +2151,7 @@ uint32_t FractureToolImpl::stretchGroup(const std::vector& grp, std::v mChunkData[newChunkIndex].meshData = new MeshImpl(nVertices.data(), nEdges.data(), finalFacets.data(), static_cast(nVertices.size()), static_cast(nEdges.size()), static_cast(finalFacets.size())); + return newChunkIndex; } @@ -2254,6 +2277,22 @@ void FractureToolImpl::fitAllUvToRect(float side, std::set& mask) } } +void FractureToolImpl::markLeaves() +{ + for (ChunkInfo& info : mChunkData) + { + info.isLeaf = true; + } + + for (ChunkInfo& info : mChunkData) + { + const int32_t index = getChunkIndex(info.parent); + if (index >= 0) + { + mChunkData[index].isLeaf = false; + } + } +} void FractureToolImpl::rebuildAdjGraph(const std::vector& chunks, const NvcVec2i* adjChunks, uint32_t adjChunksSize, std::vector >& chunkGraph) @@ -2570,5 +2609,24 @@ void FractureToolImpl::uniteChunks(uint32_t threshold, uint32_t targetClusterSiz } } +bool FractureToolImpl::setApproximateBonding(uint32_t chunkIndex, bool useApproximateBonding) +{ + if ((size_t)chunkIndex >= mChunkData.size()) + { + return false; + } + + if (useApproximateBonding) + { + mChunkData[chunkIndex].flags |= (uint32_t)ChunkInfo::APPROXIMATE_BONDING; + } + else + { + mChunkData[chunkIndex].flags &= ~(uint32_t)ChunkInfo::APPROXIMATE_BONDING; + } + + return true; +} + } // namespace Blast } // namespace Nv diff --git a/sdk/extensions/authoring/source/NvBlastExtAuthoringFractureToolImpl.h b/sdk/extensions/authoring/source/NvBlastExtAuthoringFractureToolImpl.h index 9e4d41e..153e43c 100755 --- a/sdk/extensions/authoring/source/NvBlastExtAuthoringFractureToolImpl.h +++ b/sdk/extensions/authoring/source/NvBlastExtAuthoringFractureToolImpl.h @@ -380,6 +380,7 @@ public: const NvcVec2i* adjChunks, uint32_t adjChunksSize, bool removeOriginalChunks = false) override; + bool setApproximateBonding(uint32_t chunkId, bool useApproximateBonding) override; /** Rescale interior uv coordinates of given chunk to fit square of given size. @@ -403,6 +404,7 @@ private: void rebuildAdjGraph(const std::vector& chunksToRebuild, const NvcVec2i* adjChunks, uint32_t adjChunksSize, std::vector >& chunkGraph); void fitAllUvToRect(float side, std::set& mask); + void markLeaves(); /** Returns newly created chunk index in mChunkData. diff --git a/sdk/extensions/authoringCommon/source/NvBlastExtAuthoringInternalCommon.h b/sdk/extensions/authoringCommon/source/NvBlastExtAuthoringInternalCommon.h index 4a0fbd0..79bbe3a 100644 --- a/sdk/extensions/authoringCommon/source/NvBlastExtAuthoringInternalCommon.h +++ b/sdk/extensions/authoringCommon/source/NvBlastExtAuthoringInternalCommon.h @@ -29,6 +29,7 @@ #ifndef NVBLASTINTERNALCOMMON_H #define NVBLASTINTERNALCOMMON_H #include "NvBlastExtAuthoringTypes.h" +#include "NvBlastPxSharedHelpers.h" #include #include #include @@ -275,6 +276,47 @@ struct VrtPositionComparator }; }; + +NV_INLINE float calculateCollisionHullVolume(const CollisionHull& hull) +{ + if (hull.pointsCount == 0) + { + return 0.0f; + } + + // Find an approximate centroid for a more accurate calculation + NvcVec3 centroid = { 0.0f, 0.0f, 0.0f }; + for (uint32_t i = 0; i < hull.pointsCount; ++i) + { + centroid = centroid + hull.points[i]; + } + centroid = centroid / hull.pointsCount; + + float volume = 0.0f; + + for (uint32_t i = 0; i < hull.polygonDataCount; ++i) + { + const HullPolygon& poly = hull.polygonData[i]; + if (poly.vertexCount < 3) + { + continue; + } + const uint32_t i0 = hull.indices[poly.indexBase]; + uint32_t i1 = hull.indices[poly.indexBase + 1]; + for (uint32_t j = 2; j < poly.vertexCount; ++j) + { + const uint32_t i2 = hull.indices[poly.indexBase + j]; + const NvcVec3 a = hull.points[i0] - centroid; + const NvcVec3 b = hull.points[i1] - centroid; + const NvcVec3 c = hull.points[i2] - centroid; + volume += + (a.x * b.y * c.z - a.x * b.z * c.y - a.y * b.x * c.z + a.y * b.z * c.x + a.z * b.x * c.y - a.z * b.y * c.x); + i1 = i2; + } + } + return (1.0f / 6.0f) * std::abs(volume); +} + } // namespace Blast } // namespace Nv diff --git a/sdk/lowlevel/include/NvBlast.h b/sdk/lowlevel/include/NvBlast.h index 4b777cb..22d7253 100755 --- a/sdk/lowlevel/include/NvBlast.h +++ b/sdk/lowlevel/include/NvBlast.h @@ -325,7 +325,7 @@ Iff chunks are already ordered correctly, function returns 'true' and identity c \param[out] chunkReorderMap User-supplied map of size chunkCount to fill. For every chunk index this array will contain new chunk position (index). \param[in] chunkDescs Array of chunk descriptors of size chunkCount. \param[in] chunkCount The number of chunk descriptors. -\param[in] scratch User-supplied scratch storage, must point to 2 * chunkCount * sizeof(uint32_t) valid bytes of memory. +\param[in] scratch User-supplied scratch storage, must point to 3 * chunkCount * sizeof(uint32_t) valid bytes of memory. \param[in] logFn User-supplied message function (see NvBlastLog definition). May be NULL. \return true iff the chunks did not require reordering (chunkReorderMap is the identity map). diff --git a/sdk/lowlevel/source/NvBlastAsset.cpp b/sdk/lowlevel/source/NvBlastAsset.cpp index c82fa29..553599d 100755 --- a/sdk/lowlevel/source/NvBlastAsset.cpp +++ b/sdk/lowlevel/source/NvBlastAsset.cpp @@ -777,42 +777,48 @@ bool Asset::ensureExactSupportCoverage(uint32_t& supportChunkCount, uint32_t& le bool Asset::testForValidChunkOrder(uint32_t chunkCount, const NvBlastChunkDesc* chunkDescs, const char* chunkAnnotation, void* scratch) { - char* chunkMarks = static_cast(memset(scratch, 0, chunkCount)); - - uint32_t currentParentChunkIndex = invalidIndex(); - for (uint32_t i = 0; i < chunkCount; ++i) - { - const uint32_t parentChunkIndex = chunkDescs[i].parentChunkIndex; - if (parentChunkIndex != currentParentChunkIndex) - { - if (!isInvalidIndex(currentParentChunkIndex)) - { - chunkMarks[currentParentChunkIndex] = 1; - } - currentParentChunkIndex = parentChunkIndex; - if (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; + char* chunkMarks = static_cast(memset(scratch, 0, chunkCount)); + + uint32_t currentParentChunkIndex = invalidIndex(); + for (uint32_t i = 0; i < chunkCount; ++i) + { + const uint32_t parentChunkIndex = chunkDescs[i].parentChunkIndex; + + if (!isInvalidIndex(parentChunkIndex) && parentChunkIndex >= i) // 'chunks should come after their parents' + { + return false; + } + + if (parentChunkIndex != currentParentChunkIndex) + { + if (!isInvalidIndex(currentParentChunkIndex)) + { + chunkMarks[currentParentChunkIndex] = 1; + } + currentParentChunkIndex = parentChunkIndex; + if (isInvalidIndex(currentParentChunkIndex)) // 'root chunks should go first' + { + return false; + } + else if (chunkMarks[currentParentChunkIndex] != 0) // 'all chunks with same parent index should go in a row' + { + 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) // 'upper-support chunks should come before subsupport chunks' + { + return false; + } + } + } + + return true; } } // namespace Blast diff --git a/sdk/lowlevel/source/NvBlastAsset.h b/sdk/lowlevel/source/NvBlastAsset.h index 7113517..8ed3c57 100755 --- a/sdk/lowlevel/source/NvBlastAsset.h +++ b/sdk/lowlevel/source/NvBlastAsset.h @@ -156,21 +156,22 @@ public: 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); + 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. 'chunks should come after their parents'. + 3. 'root chunks should go first'. + 4. '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 //////// diff --git a/sdk/lowlevel/source/NvBlastAssetHelper.cpp b/sdk/lowlevel/source/NvBlastAssetHelper.cpp index 1c8b7bd..9930bad 100755 --- a/sdk/lowlevel/source/NvBlastAssetHelper.cpp +++ b/sdk/lowlevel/source/NvBlastAssetHelper.cpp @@ -47,28 +47,49 @@ Class to hold chunk descriptor and annotation context for sorting a list of indi 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 - } + ChunksOrdered(const NvBlastChunkDesc* descs, const char* annotation) + : m_descs(descs), m_annotation(annotation), m_chunkMap(nullptr), m_chunkInvMap(nullptr) {} + + // Map and inverse to apply to chunk descs + bool setMap(const uint32_t* map, const uint32_t* inv) + { + if ((map == nullptr) != (inv == nullptr)) + { + return false; + } + m_chunkMap = map; + m_chunkInvMap = inv; + return true; + } + + bool operator () (uint32_t ii0, uint32_t ii1) const + { + const uint32_t i0 = m_chunkMap ? m_chunkMap[ii0] : ii0; + const uint32_t i1 = m_chunkMap ? m_chunkMap[ii1] : ii1; + + 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 + } + + const uint32_t p0 = m_descs[i0].parentChunkIndex; + const uint32_t p1 = m_descs[i1].parentChunkIndex; + + // Parent chunk index (+1 so that UINT32_MAX becomes the lowest value) + const uint32_t pp0 = 1 + (m_chunkInvMap && !isInvalidIndex(p0) ? m_chunkInvMap[p0] : p0); + const uint32_t pp1 = 1 + (m_chunkInvMap && !isInvalidIndex(p1) ? m_chunkInvMap[p1] : p1); + + return pp0 < pp1; // With the same support relationship, order by parent index + } private: - const NvBlastChunkDesc* m_descs; - const char* m_annotation; + const NvBlastChunkDesc* m_descs; + const char* m_annotation; + const uint32_t* m_chunkMap; + const uint32_t* m_chunkInvMap; }; } // namespace Blast @@ -86,6 +107,7 @@ bool NvBlastBuildAssetDescChunkReorderMap(uint32_t* chunkReorderMap, const NvBla NVBLASTLL_CHECK(chunkReorderMap == nullptr || chunkCount != 0, logFn, "NvBlastBuildAssetDescChunkReorderMap: NULL chunkReorderMap input with non-zero chunkCount", return false); NVBLASTLL_CHECK(chunkCount == 0 || scratch != nullptr, logFn, "NvBlastBuildAssetDescChunkReorderMap: NULL scratch input with non-zero chunkCount", return false); + uint32_t* composedMap = static_cast(scratch); scratch = pointerOffset(scratch, chunkCount * sizeof(uint32_t)); uint32_t* chunkMap = static_cast(scratch); scratch = pointerOffset(scratch, chunkCount * sizeof(uint32_t)); char* chunkAnnotation = static_cast(scratch); scratch = pointerOffset(scratch, chunkCount * sizeof(char)); @@ -97,24 +119,65 @@ bool NvBlastBuildAssetDescChunkReorderMap(uint32_t* chunkReorderMap, const NvBla 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); + // Initialize composedMap and its inverse to identity + for (uint32_t i = 0; i < chunkCount; ++i) + { + composedMap[i] = i; + chunkReorderMap[i] = i; + } + + // Create a chunk ordering operator using the composedMap + ChunksOrdered chunksOrdered(chunkDescs, chunkAnnotation); + chunksOrdered.setMap(composedMap, chunkReorderMap); + + // Check initial order + bool ordered = true; + if (chunkCount > 1) + { + for (uint32_t i = chunkCount - 1; ordered && i--;) + { + ordered = !chunksOrdered(i + 1, i); + } + } + if (ordered) + { + return true; // Initially ordered, return true + } + + NVBLAST_ASSERT(chunkCount > 1); + + // Max depth is bounded by chunkCount, so that is the vound on the number of iterations + uint32_t iter = chunkCount; + do + { + // Reorder based on current composed map + for (uint32_t i = 0; i < chunkCount; ++i) + { + chunkMap[i] = i; + } + std::stable_sort(chunkMap, chunkMap + chunkCount, chunksOrdered); + + // Fold chunkMap into composedMap + for (uint32_t i = 0; i < chunkCount; ++i) + { + chunkMap[i] = composedMap[chunkMap[i]]; + } + for (uint32_t i = 0; i < chunkCount; ++i) + { + composedMap[i] = chunkMap[i]; + chunkMap[i] = i; + } + invertMap(chunkReorderMap, composedMap, chunkCount); + + // Check order + ordered = true; + for (uint32_t i = chunkCount - 1; ordered && i--;) + { + ordered = !chunksOrdered(i + 1, i); + } + } while (!ordered && iter--); + + NVBLAST_ASSERT(ordered); return false; } -- cgit v1.2.3