izzy/UnrealEngineUWP
0
0
Fork 0
mirror of https://github.com/izzy2lost/UnrealEngineUWP.git synced 2026-03-26 18:15:20 -07:00
Code Issues Packages Projects Releases Wiki Activity
Files
4.23-uwp
UnrealEngineUWP/Engine/Source/Runtime/NavigationSystem/Private/NavMesh/RecastNavMeshGenerator.cpp

5169 lines
168 KiB
C++
Raw Permalink Blame History

// Copyright 1998-2019 Epic Games, Inc. All Rights Reserved.
#include "NavMesh/RecastNavMeshGenerator.h"
#include "AI/Navigation/NavRelevantInterface.h"
#include "Components/PrimitiveComponent.h"
#include "HAL/FileManager.h"
#include "Misc/Paths.h"
#include "Serialization/MemoryWriter.h"
#include "EngineGlobals.h"
#include "GameFramework/PlayerController.h"
#include "Engine/Engine.h"
#include "NavigationSystem.h"
#include "FramePro/FrameProProfiler.h"
#if WITH_RECAST
#if WITH_PHYSX
#include "PhysXPublic.h"
#endif
#include "NavMesh/PImplRecastNavMesh.h"
// recast includes
#include "Detour/DetourNavMeshBuilder.h"
#include "DetourTileCache/DetourTileCacheBuilder.h"
#include "NavMesh/RecastHelpers.h"
#include "NavAreas/NavArea_LowHeight.h"
#include "AI/NavigationSystemHelpers.h"
#include "VisualLogger/VisualLoggerTypes.h"
#include "PhysicsEngine/ConvexElem.h"
#include "PhysicsEngine/BodySetup.h"
#ifndef OUTPUT_NAV_TILE_LAYER_COMPRESSION_DATA
#define OUTPUT_NAV_TILE_LAYER_COMPRESSION_DATA 0
#endif
#ifndef FAVOR_NAV_COMPRESSION_SPEED
#define FAVOR_NAV_COMPRESSION_SPEED 1
#endif
#define SEAMLESS_REBUILDING_ENABLED 1
#define GENERATE_SEGMENT_LINKS 1
#define GENERATE_CLUSTER_LINKS 1
#define SHOW_NAV_EXPORT_PREVIEW 0
#define TEXT_WEAKOBJ_NAME(obj) (obj.IsValid(false) ? *obj->GetName() : (obj.IsValid(false, true)) ? TEXT("MT-Unreachable") : TEXT("INVALID"))
struct dtTileCacheAlloc;
FORCEINLINE bool DoesBoxContainOrOverlapVector(const FBox& BigBox, const FVector& In)
{
return (In.X >= BigBox.Min.X) && (In.X <= BigBox.Max.X)
&& (In.Y >= BigBox.Min.Y) && (In.Y <= BigBox.Max.Y)
&& (In.Z >= BigBox.Min.Z) && (In.Z <= BigBox.Max.Z);
}
/** main difference between this and FBox::ContainsBox is that this returns true also when edges overlap */
FORCEINLINE bool DoesBoxContainBox(const FBox& BigBox, const FBox& SmallBox)
{
return DoesBoxContainOrOverlapVector(BigBox, SmallBox.Min) && DoesBoxContainOrOverlapVector(BigBox, SmallBox.Max);
}
int32 GetTilesCountHelper(const dtNavMesh* DetourMesh)
{
int32 NumTiles = 0;
if (DetourMesh)
{
for (int32 i = 0; i < DetourMesh->getMaxTiles(); i++)
{
const dtMeshTile* TileData = DetourMesh->getTile(i);
if (TileData && TileData->header && TileData->dataSize > 0)
{
NumTiles++;
}
}
}
return NumTiles;
}
/**
* Exports geometry to OBJ file. Can be used to verify NavMesh generation in RecastDemo app
* @param FileName - full name of OBJ file with extension
* @param GeomVerts - list of vertices
* @param GeomFaces - list of triangles (3 vert indices for each)
*/
static void ExportGeomToOBJFile(const FString& InFileName, const TNavStatArray<float>& GeomCoords, const TNavStatArray<int32>& GeomFaces, const FString& AdditionalData)
{
#define USE_COMPRESSION 0
#if ALLOW_DEBUG_FILES
SCOPE_CYCLE_COUNTER(STAT_Navigation_TileGeometryExportToObjAsync);
FString FileName = InFileName;
#if USE_COMPRESSION
FileName += TEXT("z");
struct FDataChunk
{
TArray<uint8> UncompressedBuffer;
TArray<uint8> CompressedBuffer;
void CompressBuffer()
{
const int32 HeaderSize = sizeof(int32);
const int32 UncompressedSize = UncompressedBuffer.Num();
CompressedBuffer.Init(0, HeaderSize + FMath::Trunc(1.1f * UncompressedSize));
int32 CompressedSize = CompressedBuffer.Num() - HeaderSize;
uint8* DestBuffer = CompressedBuffer.GetData();
FMemory::Memcpy(DestBuffer, &UncompressedSize, HeaderSize);
DestBuffer += HeaderSize;
FCompression::CompressMemory(NAME_Zlib, (void*)DestBuffer, CompressedSize, (void*)UncompressedBuffer.GetData(), UncompressedSize, COMPRESS_BiasMemory);
CompressedBuffer.SetNum(CompressedSize + HeaderSize, false);
}
};
FDataChunk AllDataChunks[3];
const int32 NumberOfChunks = sizeof(AllDataChunks) / sizeof(FDataChunk);
{
FMemoryWriter ArWriter(AllDataChunks[0].UncompressedBuffer);
for (int32 i = 0; i < GeomCoords.Num(); i += 3)
{
FVector Vertex(GeomCoords[i + 0], GeomCoords[i + 1], GeomCoords[i + 2]);
ArWriter << Vertex;
}
}
{
FMemoryWriter ArWriter(AllDataChunks[1].UncompressedBuffer);
for (int32 i = 0; i < GeomFaces.Num(); i += 3)
{
FVector Face(GeomFaces[i + 0] + 1, GeomFaces[i + 1] + 1, GeomFaces[i + 2] + 1);
ArWriter << Face;
}
}
{
auto AnsiAdditionalData = StringCast<ANSICHAR>(*AdditionalData);
FMemoryWriter ArWriter(AllDataChunks[2].UncompressedBuffer);
ArWriter.Serialize((ANSICHAR*)AnsiAdditionalData.Get(), AnsiAdditionalData.Length());
}
FArchive* FileAr = IFileManager::Get().CreateDebugFileWriter(*FileName);
if (FileAr != NULL)
{
for (int32 Index = 0; Index < NumberOfChunks; ++Index)
{
AllDataChunks[Index].CompressBuffer();
int32 BufferSize = AllDataChunks[Index].CompressedBuffer.Num();
FileAr->Serialize(&BufferSize, sizeof(int32));
FileAr->Serialize((void*)AllDataChunks[Index].CompressedBuffer.GetData(), AllDataChunks[Index].CompressedBuffer.Num());
}
UE_LOG(LogNavigation, Error, TEXT("UncompressedBuffer size:: %d "), AllDataChunks[0].UncompressedBuffer.Num() + AllDataChunks[1].UncompressedBuffer.Num() + AllDataChunks[2].UncompressedBuffer.Num());
FileAr->Close();
}
#else
FArchive* FileAr = IFileManager::Get().CreateDebugFileWriter(*FileName);
if (FileAr != NULL)
{
for (int32 Index = 0; Index < GeomCoords.Num(); Index += 3)
{
FString LineToSave = FString::Printf(TEXT("v %f %f %f\n"), GeomCoords[Index + 0], GeomCoords[Index + 1], GeomCoords[Index + 2]);
auto AnsiLineToSave = StringCast<ANSICHAR>(*LineToSave);
FileAr->Serialize((ANSICHAR*)AnsiLineToSave.Get(), AnsiLineToSave.Length());
}
for (int32 Index = 0; Index < GeomFaces.Num(); Index += 3)
{
FString LineToSave = FString::Printf(TEXT("f %d %d %d\n"), GeomFaces[Index + 0] + 1, GeomFaces[Index + 1] + 1, GeomFaces[Index + 2] + 1);
auto AnsiLineToSave = StringCast<ANSICHAR>(*LineToSave);
FileAr->Serialize((ANSICHAR*)AnsiLineToSave.Get(), AnsiLineToSave.Length());
}
auto AnsiAdditionalData = StringCast<ANSICHAR>(*AdditionalData);
FileAr->Serialize((ANSICHAR*)AnsiAdditionalData.Get(), AnsiAdditionalData.Length());
FileAr->Close();
}
#endif
#undef USE_COMPRESSION
#endif
}
//----------------------------------------------------------------------//
//
//
struct FRecastGeometryExport : public FNavigableGeometryExport
{
FRecastGeometryExport(FNavigationRelevantData& InData) : Data(&InData)
{
Data->Bounds = FBox(ForceInit);
}
FNavigationRelevantData* Data;
TNavStatArray<float> VertexBuffer;
TNavStatArray<int32> IndexBuffer;
FWalkableSlopeOverride SlopeOverride;
#if WITH_PHYSX
virtual void ExportPxTriMesh16Bit(physx::PxTriangleMesh const * const TriMesh, const FTransform& LocalToWorld) override;
virtual void ExportPxTriMesh32Bit(physx::PxTriangleMesh const * const TriMesh, const FTransform& LocalToWorld) override;
virtual void ExportPxConvexMesh(physx::PxConvexMesh const * const ConvexMesh, const FTransform& LocalToWorld) override;
virtual void ExportPxHeightField(physx::PxHeightField const * const HeightField, const FTransform& LocalToWorld) override;
#endif // WITH_PHYSX
virtual void ExportHeightFieldSlice(const FNavHeightfieldSamples& PrefetchedHeightfieldSamples, const int32 NumRows, const int32 NumCols, const FTransform& LocalToWorld, const FBox& SliceBox) override;
virtual void ExportCustomMesh(const FVector* InVertices, int32 NumVerts, const int32* InIndices, int32 NumIndices, const FTransform& LocalToWorld) override;
virtual void ExportRigidBodySetup(UBodySetup& BodySetup, const FTransform& LocalToWorld) override;
virtual void AddNavModifiers(const FCompositeNavModifier& Modifiers) override;
virtual void SetNavDataPerInstanceTransformDelegate(const FNavDataPerInstanceTransformDelegate& InDelegate) override;
};
FRecastVoxelCache::FRecastVoxelCache(const uint8* Memory)
{
uint8* BytesArr = (uint8*)Memory;
if (Memory)
{
NumTiles = *((int32*)BytesArr); BytesArr += sizeof(int32);
Tiles = (FTileInfo*)BytesArr;
}
else
{
NumTiles = 0;
}
FTileInfo* iTile = Tiles;
for (int i = 0; i < NumTiles; i++)
{
iTile = (FTileInfo*)BytesArr; BytesArr += sizeof(FTileInfo);
if (iTile->NumSpans)
{
iTile->SpanData = (rcSpanCache*)BytesArr; BytesArr += sizeof(rcSpanCache) * iTile->NumSpans;
}
else
{
iTile->SpanData = 0;
}
iTile->NextTile = (FTileInfo*)BytesArr;
}
if (NumTiles > 0)
{
iTile->NextTile = 0;
}
else
{
Tiles = 0;
}
}
FRecastGeometryCache::FRecastGeometryCache(const uint8* Memory)
{
Header = *((FHeader*)Memory);
Verts = (float*)(Memory + sizeof(FRecastGeometryCache));
Indices = (int32*)(Memory + sizeof(FRecastGeometryCache) + (sizeof(float) * Header.NumVerts * 3));
}
namespace RecastGeometryExport {
static UWorld* FindEditorWorld()
{
if (GEngine)
{
for (const FWorldContext& Context : GEngine->GetWorldContexts())
{
if (Context.WorldType == EWorldType::Editor)
{
return Context.World();
}
}
}
return NULL;
}
static void StoreCollisionCache(FRecastGeometryExport& GeomExport)
{
const int32 NumFaces = GeomExport.IndexBuffer.Num() / 3;
const int32 NumVerts = GeomExport.VertexBuffer.Num() / 3;
if (NumFaces == 0 || NumVerts == 0)
{
GeomExport.Data->CollisionData.Empty();
return;
}
FRecastGeometryCache::FHeader HeaderInfo;
HeaderInfo.NumFaces = NumFaces;
HeaderInfo.NumVerts = NumVerts;
HeaderInfo.SlopeOverride = GeomExport.SlopeOverride;
// allocate memory
const int32 HeaderSize = sizeof(FRecastGeometryCache);
const int32 CoordsSize = sizeof(float) * 3 * NumVerts;
const int32 IndicesSize = sizeof(int32) * 3 * NumFaces;
const int32 CacheSize = HeaderSize + CoordsSize + IndicesSize;
HeaderInfo.Validation.DataSize = CacheSize;
// empty + add combo to allocate exact amount (without any overhead/slack)
GeomExport.Data->CollisionData.Empty(CacheSize);
GeomExport.Data->CollisionData.AddUninitialized(CacheSize);
// store collisions
uint8* RawMemory = GeomExport.Data->CollisionData.GetData();
FRecastGeometryCache* CacheMemory = (FRecastGeometryCache*)RawMemory;
CacheMemory->Header = HeaderInfo;
CacheMemory->Verts = 0;
CacheMemory->Indices = 0;
FMemory::Memcpy(RawMemory + HeaderSize, GeomExport.VertexBuffer.GetData(), CoordsSize);
FMemory::Memcpy(RawMemory + HeaderSize + CoordsSize, GeomExport.IndexBuffer.GetData(), IndicesSize);
}
#if WITH_PHYSX
/** exports PxConvexMesh as trimesh */
void ExportPxConvexMesh(PxConvexMesh const * const ConvexMesh, const FTransform& LocalToWorld,
TNavStatArray<float>& VertexBuffer, TNavStatArray<int32>& IndexBuffer,
FBox& UnrealBounds)
{
// after FKConvexElem::AddCachedSolidConvexGeom
if(ConvexMesh == NULL)
{
return;
}
int32 StartVertOffset = VertexBuffer.Num() / 3;
const bool bNegX = LocalToWorld.GetDeterminant() < 0;
// get PhysX data
const PxVec3* PVertices = ConvexMesh->getVertices();
const PxU8* PIndexBuffer = ConvexMesh->getIndexBuffer();
const PxU32 NbPolygons = ConvexMesh->getNbPolygons();
#if SHOW_NAV_EXPORT_PREVIEW
UWorld* DebugWorld = FindEditorWorld();
#endif // SHOW_NAV_EXPORT_PREVIEW
for(PxU32 i = 0; i < NbPolygons; ++i)
{
PxHullPolygon Data;
bool bStatus = ConvexMesh->getPolygonData(i, Data);
check(bStatus);
const PxU8* indices = PIndexBuffer + Data.mIndexBase;
// add vertices
for(PxU32 j = 0; j < Data.mNbVerts; ++j)
{
const int32 VertIndex = indices[j];
const FVector UnrealCoords = LocalToWorld.TransformPosition( P2UVector(PVertices[VertIndex]) );
UnrealBounds += UnrealCoords;
VertexBuffer.Add(UnrealCoords.X);
VertexBuffer.Add(UnrealCoords.Y);
VertexBuffer.Add(UnrealCoords.Z);
}
// Add indices
const PxU32 nbTris = Data.mNbVerts - 2;
for(PxU32 j = 0; j < nbTris; ++j)
{
IndexBuffer.Add(StartVertOffset + 0 );
IndexBuffer.Add(StartVertOffset + j + 2);
IndexBuffer.Add(StartVertOffset + j + 1);
#if SHOW_NAV_EXPORT_PREVIEW
if (DebugWorld)
{
FVector V0(VertexBuffer[(StartVertOffset + 0) * 3+0], VertexBuffer[(StartVertOffset + 0) * 3+1], VertexBuffer[(StartVertOffset + 0) * 3+2]);
FVector V1(VertexBuffer[(StartVertOffset + j + 2) * 3+0], VertexBuffer[(StartVertOffset + j + 2) * 3+1], VertexBuffer[(StartVertOffset + j + 2) * 3+2]);
FVector V2(VertexBuffer[(StartVertOffset + j + 1) * 3+0], VertexBuffer[(StartVertOffset + j + 1) * 3+1], VertexBuffer[(StartVertOffset + j + 1) * 3+2]);
DrawDebugLine(DebugWorld, V0, V1, bNegX ? FColor::Red : FColor::Blue, true);
DrawDebugLine(DebugWorld, V1, V2, bNegX ? FColor::Red : FColor::Blue, true);
DrawDebugLine(DebugWorld, V2, V0, bNegX ? FColor::Red : FColor::Blue, true);
}
#endif // SHOW_NAV_EXPORT_PREVIEW
}
StartVertOffset += Data.mNbVerts;
}
}
template<typename TIndicesType>
FORCEINLINE_DEBUGGABLE void ExportPxTriMesh(PxTriangleMesh const * const TriMesh, const FTransform& LocalToWorld,
TNavStatArray<float>& VertexBuffer, TNavStatArray<int32>& IndexBuffer,
FBox& UnrealBounds)
{
if (TriMesh == NULL)
{
return;
}
int32 VertOffset = VertexBuffer.Num() / 3;
const PxVec3* PVerts = TriMesh->getVertices();
const PxU32 NumTris = TriMesh->getNbTriangles();
const TIndicesType* Indices = (TIndicesType*)TriMesh->getTriangles();;
VertexBuffer.Reserve(VertexBuffer.Num() + NumTris*3);
IndexBuffer.Reserve(IndexBuffer.Num() + NumTris*3);
const bool bFlipCullMode = (LocalToWorld.GetDeterminant() < 0.f);
const int32 IndexOrder[3] = { bFlipCullMode ? 0 : 2, 1, bFlipCullMode ? 2 : 0 };
#if SHOW_NAV_EXPORT_PREVIEW
UWorld* DebugWorld = FindEditorWorld();
#endif // SHOW_NAV_EXPORT_PREVIEW
for(PxU32 TriIdx = 0; TriIdx < NumTris; ++TriIdx)
{
for (int32 i = 0; i < 3; i++)
{
const FVector UnrealCoords = LocalToWorld.TransformPosition(P2UVector(PVerts[Indices[i]]));
UnrealBounds += UnrealCoords;
VertexBuffer.Add(UnrealCoords.X);
VertexBuffer.Add(UnrealCoords.Y);
VertexBuffer.Add(UnrealCoords.Z);
}
Indices += 3;
IndexBuffer.Add(VertOffset + IndexOrder[0]);
IndexBuffer.Add(VertOffset + IndexOrder[1]);
IndexBuffer.Add(VertOffset + IndexOrder[2]);
#if SHOW_NAV_EXPORT_PREVIEW
if (DebugWorld)
{
FVector V0(VertexBuffer[(VertOffset + IndexOrder[0]) * 3+0], VertexBuffer[(VertOffset + IndexOrder[0]) * 3+1], VertexBuffer[(VertOffset + IndexOrder[0]) * 3+2]);
FVector V1(VertexBuffer[(VertOffset + IndexOrder[1]) * 3+0], VertexBuffer[(VertOffset + IndexOrder[1]) * 3+1], VertexBuffer[(VertOffset + IndexOrder[1]) * 3+2]);
FVector V2(VertexBuffer[(VertOffset + IndexOrder[2]) * 3+0], VertexBuffer[(VertOffset + IndexOrder[2]) * 3+1], VertexBuffer[(VertOffset + IndexOrder[2]) * 3+2]);
DrawDebugLine(DebugWorld, V0, V1, bFlipCullMode ? FColor::Red : FColor::Blue, true);
DrawDebugLine(DebugWorld, V1, V2, bFlipCullMode ? FColor::Red : FColor::Blue, true);
DrawDebugLine(DebugWorld, V2, V0, bFlipCullMode ? FColor::Red : FColor::Blue, true);
}
#endif // SHOW_NAV_EXPORT_PREVIEW
VertOffset += 3;
}
}
void ExportPxHeightField(PxHeightField const * const HeightField, const FTransform& LocalToWorld
, TNavStatArray<float>& VertexBuffer, TNavStatArray<int32>& IndexBuffer
, FBox& UnrealBounds)
{
if (HeightField == NULL)
{
return;
}
QUICK_SCOPE_CYCLE_COUNTER(STAT_NavMesh_ExportPxHeightField);
const int32 NumRows = HeightField->getNbRows();
const int32 NumCols = HeightField->getNbColumns();
const int32 VertexCount = NumRows * NumCols;
// Unfortunately we have to use PxHeightField::saveCells instead PxHeightField::getHeight here
// because current PxHeightField interface does not provide an access to a triangle material index by HF 2D coordinates
// PxHeightField::getTriangleMaterialIndex uses some internal adressing which does not match HF 2D coordinates
TArray<PxHeightFieldSample> HFSamples;
HFSamples.SetNumUninitialized(VertexCount);
{
QUICK_SCOPE_CYCLE_COUNTER(STAT_NavMesh_ExportPxHeightField_saveCells);
HeightField->saveCells(HFSamples.GetData(), VertexCount*HFSamples.GetTypeSize());
}
//
const int32 VertOffset = VertexBuffer.Num() / 3;
const int32 NumQuads = (NumRows - 1)*(NumCols - 1);
VertexBuffer.Reserve(VertexBuffer.Num() + VertexCount * 3);
IndexBuffer.Reserve(IndexBuffer.Num() + NumQuads * 6);
const bool bMirrored = (LocalToWorld.GetDeterminant() < 0.f);
for (int32 Y = 0; Y < NumRows; Y++)
{
for (int32 X = 0; X < NumCols; X++)
{
const int32 SampleIdx = (bMirrored ? X : (NumCols - X - 1))*NumCols + Y;
const PxHeightFieldSample& Sample = HFSamples[SampleIdx];
const FVector UnrealCoords = LocalToWorld.TransformPosition(FVector(X, Y, Sample.height));
UnrealBounds += UnrealCoords;
VertexBuffer.Add(UnrealCoords.X);
VertexBuffer.Add(UnrealCoords.Y);
VertexBuffer.Add(UnrealCoords.Z);
}
}
for (int32 Y = 0; Y < NumRows - 1; Y++)
{
for (int32 X = 0; X < NumCols - 1; X++)
{
const int32 SampleIdx = (bMirrored ? X : (NumCols - X - 1 - 1))*NumCols + Y;
const PxHeightFieldSample& Sample = HFSamples[SampleIdx];
const bool bIsHole = (Sample.materialIndex0 == PxHeightFieldMaterial::eHOLE);
if (bIsHole)
{
continue;
}
const int32 I00 = X + 0 + (Y + 0)*NumCols;
int32 I01 = X + 0 + (Y + 1)*NumCols;
int32 I10 = X + 1 + (Y + 0)*NumCols;
const int32 I11 = X + 1 + (Y + 1)*NumCols;
if (bMirrored)
{
Swap(I01, I10);
}
IndexBuffer.Add(VertOffset + I00);
IndexBuffer.Add(VertOffset + I11);
IndexBuffer.Add(VertOffset + I10);
IndexBuffer.Add(VertOffset + I00);
IndexBuffer.Add(VertOffset + I01);
IndexBuffer.Add(VertOffset + I11);
}
}
}
#endif // WITH_PHYSX
void ExportHeightFieldSlice(const FNavHeightfieldSamples& PrefetchedHeightfieldSamples, const int32 NumRows, const int32 NumCols, const FTransform& LocalToWorld
, TNavStatArray<float>& VertexBuffer, TNavStatArray<int32>& IndexBuffer, const FBox& SliceBox
, FBox& UnrealBounds)
{
QUICK_SCOPE_CYCLE_COUNTER(STAT_NavMesh_ExportHeightFieldSlice);
#if WITH_PHYSX
static const uint32 SizeOfPx = sizeof(physx::PxI16);
static const uint32 SizeOfHeight = PrefetchedHeightfieldSamples.Heights.GetTypeSize();
ensure(SizeOfPx == SizeOfHeight);
#endif // WITH_PHYSX
// calculate the actual start and number of columns we want
const FBox LocalBox = SliceBox.TransformBy(LocalToWorld.Inverse());
const bool bMirrored = (LocalToWorld.GetDeterminant() < 0.f);
const int32 MinX = FMath::Clamp(FMath::FloorToInt(LocalBox.Min.X) - 1, 0, NumCols);
const int32 MinY = FMath::Clamp(FMath::FloorToInt(LocalBox.Min.Y) - 1, 0, NumRows);
const int32 MaxX = FMath::Clamp(FMath::CeilToInt(LocalBox.Max.X) + 1, 0, NumCols);
const int32 MaxY = FMath::Clamp(FMath::CeilToInt(LocalBox.Max.Y) + 1, 0, NumRows);
const int32 SizeX = MaxX - MinX;
const int32 SizeY = MaxY - MinY;
if (SizeX <= 0 || SizeY <= 0)
{
// slice is outside bounds, skip
return;
}
const int32 VertOffset = VertexBuffer.Num() / 3;
const int32 NumVerts = SizeX * SizeY;
const int32 NumQuads = (SizeX - 1) * (SizeY - 1);
{
QUICK_SCOPE_CYCLE_COUNTER(STAT_RecastGeometryExport_AllocatingMemory);
VertexBuffer.Reserve(VertexBuffer.Num() + NumVerts * 3);
IndexBuffer.Reserve(IndexBuffer.Num() + NumQuads * 3 * 2);
}
for (int32 IdxY = 0; IdxY < SizeY; IdxY++)
{
for (int32 IdxX = 0; IdxX < SizeX; IdxX++)
{
const int32 CoordX = IdxX + MinX;
const int32 CoordY = IdxY + MinY;
const int32 SampleIdx = ((bMirrored ? CoordX : (NumCols - CoordX - 1)) * NumCols) + CoordY;
const FVector UnrealCoords = LocalToWorld.TransformPosition(FVector(CoordX, CoordY, PrefetchedHeightfieldSamples.Heights[SampleIdx]));
VertexBuffer.Add(UnrealCoords.X);
VertexBuffer.Add(UnrealCoords.Y);
VertexBuffer.Add(UnrealCoords.Z);
}
}
for (int32 IdxY = 0; IdxY < SizeY - 1; IdxY++)
{
for (int32 IdxX = 0; IdxX < SizeX - 1; IdxX++)
{
const int32 CoordX = IdxX + MinX;
const int32 CoordY = IdxY + MinY;
const int32 SampleIdx = ((bMirrored ? CoordX : (NumCols - CoordX - 1)) * NumCols) + CoordY;
const bool bIsHole = PrefetchedHeightfieldSamples.Holes[SampleIdx];
if (bIsHole)
{
continue;
}
const int32 I00 = (IdxX + 0) + (IdxY + 0)*SizeX;
int32 I01 = (IdxX + 0) + (IdxY + 1)*SizeX;
int32 I10 = (IdxX + 1) + (IdxY + 0)*SizeX;
const int32 I11 = (IdxX + 1) + (IdxY + 1)*SizeX;
if (bMirrored)
{
Swap(I01, I10);
}
IndexBuffer.Add(VertOffset + I00);
IndexBuffer.Add(VertOffset + I11);
IndexBuffer.Add(VertOffset + I10);
IndexBuffer.Add(VertOffset + I00);
IndexBuffer.Add(VertOffset + I01);
IndexBuffer.Add(VertOffset + I11);
}
}
}
void ExportCustomMesh(const FVector* InVertices, int32 NumVerts, const int32* InIndices, int32 NumIndices, const FTransform& LocalToWorld,
TNavStatArray<float>& VertexBuffer, TNavStatArray<int32>& IndexBuffer, FBox& UnrealBounds)
{
if (NumVerts <= 0 || NumIndices <= 0)
{
return;
}
int32 VertOffset = VertexBuffer.Num() / 3;
VertexBuffer.Reserve(VertexBuffer.Num() + NumVerts*3);
IndexBuffer.Reserve(IndexBuffer.Num() + NumIndices);
const bool bFlipCullMode = (LocalToWorld.GetDeterminant() < 0.f);
const int32 IndexOrder[3] = { bFlipCullMode ? 2 : 0, 1, bFlipCullMode ? 0 : 2 };
#if SHOW_NAV_EXPORT_PREVIEW
UWorld* DebugWorld = FindEditorWorld();
#endif // SHOW_NAV_EXPORT_PREVIEW
// Add vertices
for (int32 i = 0; i < NumVerts; ++i)
{
const FVector UnrealCoords = LocalToWorld.TransformPosition(InVertices[i]);
UnrealBounds += UnrealCoords;
VertexBuffer.Add(UnrealCoords.X);
VertexBuffer.Add(UnrealCoords.Y);
VertexBuffer.Add(UnrealCoords.Z);
}
// Add indices
for (int32 i = 0; i < NumIndices; i += 3)
{
IndexBuffer.Add(InIndices[i + IndexOrder[0]] + VertOffset);
IndexBuffer.Add(InIndices[i + IndexOrder[1]] + VertOffset);
IndexBuffer.Add(InIndices[i + IndexOrder[2]] + VertOffset);
#if SHOW_NAV_EXPORT_PREVIEW
if (DebugWorld)
{
FVector V0(VertexBuffer[(VertOffset + InIndices[i + IndexOrder[0]]) * 3+0], VertexBuffer[(VertOffset + InIndices[i + IndexOrder[0]]) * 3+1], VertexBuffer[(VertOffset + InIndices[i + IndexOrder[0]]) * 3+2]);
FVector V1(VertexBuffer[(VertOffset + InIndices[i + IndexOrder[1]]) * 3+0], VertexBuffer[(VertOffset + InIndices[i + IndexOrder[1]]) * 3+1], VertexBuffer[(VertOffset + InIndices[i + IndexOrder[1]]) * 3+2]);
FVector V2(VertexBuffer[(VertOffset + InIndices[i + IndexOrder[2]]) * 3+0], VertexBuffer[(VertOffset + InIndices[i + IndexOrder[2]]) * 3+1], VertexBuffer[(VertOffset + InIndices[i + IndexOrder[2]]) * 3+2]);
DrawDebugLine(DebugWorld, V0, V1, bFlipCullMode ? FColor::Red : FColor::Blue, true);
DrawDebugLine(DebugWorld, V1, V2, bFlipCullMode ? FColor::Red : FColor::Blue, true);
DrawDebugLine(DebugWorld, V2, V0, bFlipCullMode ? FColor::Red : FColor::Blue, true);
}
#endif // SHOW_NAV_EXPORT_PREVIEW
}
}
template<typename OtherAllocator>
FORCEINLINE_DEBUGGABLE void AddFacesToRecast(TArray<FVector, OtherAllocator>& InVerts, TArray<int32, OtherAllocator>& InFaces,
TNavStatArray<float>& OutVerts, TNavStatArray<int32>& OutIndices, FBox& UnrealBounds)
{
// Add indices
int32 StartVertOffset = OutVerts.Num();
if (StartVertOffset > 0)
{
const int32 FirstIndex = OutIndices.AddUninitialized(InFaces.Num());
for (int32 Idx=0; Idx < InFaces.Num(); ++Idx)
{
OutIndices[FirstIndex + Idx] = InFaces[Idx]+StartVertOffset;
}
}
else
{
OutIndices.Append(InFaces);
}
// Add vertices
for (int32 i = 0; i < InVerts.Num(); i++)
{
const FVector& RecastCoords = InVerts[i];
OutVerts.Add(RecastCoords.X);
OutVerts.Add(RecastCoords.Y);
OutVerts.Add(RecastCoords.Z);
UnrealBounds += Recast2UnrealPoint(RecastCoords);
}
}
FORCEINLINE_DEBUGGABLE void ExportRigidBodyConvexElements(UBodySetup& BodySetup, TNavStatArray<float>& VertexBuffer, TNavStatArray<int32>& IndexBuffer,
TNavStatArray<int32>& ShapeBuffer, FBox& UnrealBounds, const FTransform& LocalToWorld)
{
#if WITH_PHYSX
const int32 ConvexCount = BodySetup.AggGeom.ConvexElems.Num();
FKConvexElem const * ConvexElem = BodySetup.AggGeom.ConvexElems.GetData();
const FTransform NegXScale(FQuat::Identity, FVector::ZeroVector, FVector(-1, 1, 1));
for(int32 i=0; i< ConvexCount; ++i, ++ConvexElem)
{
// Store index of first vertex in shape buffer
ShapeBuffer.Add(VertexBuffer.Num() / 3);
// Get verts/triangles from this hull.
if (!ConvexElem->GetConvexMesh() && ConvexElem->GetMirroredConvexMesh())
{
// If there is only a NegX mesh (e.g. a mirrored volume), use it
ExportPxConvexMesh(ConvexElem->GetMirroredConvexMesh(), NegXScale * LocalToWorld, VertexBuffer, IndexBuffer, UnrealBounds);
}
else
{
// Otherwise use the regular mesh in the case that both exist
ExportPxConvexMesh(ConvexElem->GetConvexMesh(), LocalToWorld, VertexBuffer, IndexBuffer, UnrealBounds);
}
}
#endif // WITH_PHYSX
}
FORCEINLINE_DEBUGGABLE void ExportRigidBodyTriMesh(UBodySetup& BodySetup, TNavStatArray<float>& VertexBuffer, TNavStatArray<int32>& IndexBuffer,
FBox& UnrealBounds, const FTransform& LocalToWorld)
{
#if WITH_PHYSX
if (BodySetup.GetCollisionTraceFlag() == CTF_UseComplexAsSimple)
{
for(PxTriangleMesh* TriMesh : BodySetup.TriMeshes)
{
if (TriMesh->getTriangleMeshFlags() & PxTriangleMeshFlag::e16_BIT_INDICES)
{
ExportPxTriMesh<PxU16>(TriMesh, LocalToWorld, VertexBuffer, IndexBuffer, UnrealBounds);
}
else
{
ExportPxTriMesh<PxU32>(TriMesh, LocalToWorld, VertexBuffer, IndexBuffer, UnrealBounds);
}
}
}
#endif // WITH_PHYSX
}
void ExportRigidBodyBoxElements(const FKAggregateGeom& AggGeom, TNavStatArray<float>& VertexBuffer, TNavStatArray<int32>& IndexBuffer,
TNavStatArray<int32>& ShapeBuffer, FBox& UnrealBounds, const FTransform& LocalToWorld, const int32 NumExistingVerts = 0)
{
for (int32 i = 0; i < AggGeom.BoxElems.Num(); i++)
{
const FKBoxElem& BoxInfo = AggGeom.BoxElems[i];
const FMatrix ElemTM = BoxInfo.GetTransform().ToMatrixWithScale() * LocalToWorld.ToMatrixWithScale();
const FVector Extent(BoxInfo.X * 0.5f, BoxInfo.Y * 0.5f, BoxInfo.Z * 0.5f);
const int32 VertBase = NumExistingVerts + (VertexBuffer.Num() / 3);
// Store index of first vertex in shape buffer
ShapeBuffer.Add(VertBase);
// add box vertices
FVector UnrealVerts[] = {
ElemTM.TransformPosition(FVector(-Extent.X, -Extent.Y, Extent.Z)),
ElemTM.TransformPosition(FVector( Extent.X, -Extent.Y, Extent.Z)),
ElemTM.TransformPosition(FVector(-Extent.X, -Extent.Y, -Extent.Z)),
ElemTM.TransformPosition(FVector( Extent.X, -Extent.Y, -Extent.Z)),
ElemTM.TransformPosition(FVector(-Extent.X, Extent.Y, Extent.Z)),
ElemTM.TransformPosition(FVector( Extent.X, Extent.Y, Extent.Z)),
ElemTM.TransformPosition(FVector(-Extent.X, Extent.Y, -Extent.Z)),
ElemTM.TransformPosition(FVector( Extent.X, Extent.Y, -Extent.Z))
};
for (int32 iv = 0; iv < ARRAY_COUNT(UnrealVerts); iv++)
{
UnrealBounds += UnrealVerts[iv];
VertexBuffer.Add(UnrealVerts[iv].X);
VertexBuffer.Add(UnrealVerts[iv].Y);
VertexBuffer.Add(UnrealVerts[iv].Z);
}
IndexBuffer.Add(VertBase + 3); IndexBuffer.Add(VertBase + 2); IndexBuffer.Add(VertBase + 0);
IndexBuffer.Add(VertBase + 3); IndexBuffer.Add(VertBase + 0); IndexBuffer.Add(VertBase + 1);
IndexBuffer.Add(VertBase + 7); IndexBuffer.Add(VertBase + 3); IndexBuffer.Add(VertBase + 1);
IndexBuffer.Add(VertBase + 7); IndexBuffer.Add(VertBase + 1); IndexBuffer.Add(VertBase + 5);
IndexBuffer.Add(VertBase + 6); IndexBuffer.Add(VertBase + 7); IndexBuffer.Add(VertBase + 5);
IndexBuffer.Add(VertBase + 6); IndexBuffer.Add(VertBase + 5); IndexBuffer.Add(VertBase + 4);
IndexBuffer.Add(VertBase + 2); IndexBuffer.Add(VertBase + 6); IndexBuffer.Add(VertBase + 4);
IndexBuffer.Add(VertBase + 2); IndexBuffer.Add(VertBase + 4); IndexBuffer.Add(VertBase + 0);
IndexBuffer.Add(VertBase + 1); IndexBuffer.Add(VertBase + 0); IndexBuffer.Add(VertBase + 4);
IndexBuffer.Add(VertBase + 1); IndexBuffer.Add(VertBase + 4); IndexBuffer.Add(VertBase + 5);
IndexBuffer.Add(VertBase + 7); IndexBuffer.Add(VertBase + 6); IndexBuffer.Add(VertBase + 2);
IndexBuffer.Add(VertBase + 7); IndexBuffer.Add(VertBase + 2); IndexBuffer.Add(VertBase + 3);
}
}
void ExportRigidBodySphylElements(const FKAggregateGeom& AggGeom, TNavStatArray<float>& VertexBuffer, TNavStatArray<int32>& IndexBuffer,
TNavStatArray<int32>& ShapeBuffer, FBox& UnrealBounds, const FTransform& LocalToWorld, const int32 NumExistingVerts = 0)
{
TArray<FVector> ArcVerts;
for (int32 i = 0; i < AggGeom.SphylElems.Num(); i++)
{
const FKSphylElem& SphylInfo = AggGeom.SphylElems[i];
const FMatrix ElemTM = SphylInfo.GetTransform().ToMatrixWithScale() * LocalToWorld.ToMatrixWithScale();
const int32 VertBase = NumExistingVerts + (VertexBuffer.Num() / 3);
// Store index of first vertex in shape buffer
ShapeBuffer.Add(VertBase);
const int32 NumSides = 16;
const int32 NumRings = (NumSides/2) + 1;
// The first/last arc are on top of each other.
const int32 NumVerts = (NumSides+1) * (NumRings+1);
ArcVerts.Reset();
ArcVerts.AddZeroed(NumRings+1);
for (int32 RingIdx=0; RingIdx<NumRings+1; RingIdx++)
{
float Angle;
float ZOffset;
if (RingIdx <= NumSides/4)
{
Angle = ((float)RingIdx/(NumRings-1)) * PI;
ZOffset = 0.5 * SphylInfo.Length;
}
else
{
Angle = ((float)(RingIdx-1)/(NumRings-1)) * PI;
ZOffset = -0.5 * SphylInfo.Length;
}
// Note- unit sphere, so position always has mag of one. We can just use it for normal!
FVector SpherePos;
SpherePos.X = 0.0f;
SpherePos.Y = SphylInfo.Radius * FMath::Sin(Angle);
SpherePos.Z = SphylInfo.Radius * FMath::Cos(Angle);
ArcVerts[RingIdx] = SpherePos + FVector(0,0,ZOffset);
}
// Then rotate this arc NumSides+1 times.
for (int32 SideIdx=0; SideIdx<NumSides+1; SideIdx++)
{
const FRotator ArcRotator(0, 360.f * ((float)SideIdx/NumSides), 0);
const FRotationMatrix ArcRot( ArcRotator );
const FMatrix ArcTM = ArcRot * ElemTM;
for(int32 VertIdx=0; VertIdx<NumRings+1; VertIdx++)
{
const FVector UnrealVert = ArcTM.TransformPosition(ArcVerts[VertIdx]);
UnrealBounds += UnrealVert;
VertexBuffer.Add(UnrealVert.X);
VertexBuffer.Add(UnrealVert.Y);
VertexBuffer.Add(UnrealVert.Z);
}
}
// Add all of the triangles to the mesh.
for (int32 SideIdx=0; SideIdx<NumSides; SideIdx++)
{
const int32 a0start = VertBase + ((SideIdx+0) * (NumRings+1));
const int32 a1start = VertBase + ((SideIdx+1) * (NumRings+1));
for (int32 RingIdx=0; RingIdx<NumRings; RingIdx++)
{
IndexBuffer.Add(a0start + RingIdx + 0); IndexBuffer.Add(a1start + RingIdx + 0); IndexBuffer.Add(a0start + RingIdx + 1);
IndexBuffer.Add(a1start + RingIdx + 0); IndexBuffer.Add(a1start + RingIdx + 1); IndexBuffer.Add(a0start + RingIdx + 1);
}
}
}
}
void ExportRigidBodySphereElements(const FKAggregateGeom& AggGeom, TNavStatArray<float>& VertexBuffer, TNavStatArray<int32>& IndexBuffer,
TNavStatArray<int32>& ShapeBuffer, FBox& UnrealBounds, const FTransform& LocalToWorld, const int32 NumExistingVerts = 0)
{
TArray<FVector> ArcVerts;
for (int32 i = 0; i < AggGeom.SphereElems.Num(); i++)
{
const FKSphereElem& SphereInfo = AggGeom.SphereElems[i];
const FMatrix ElemTM = SphereInfo.GetTransform().ToMatrixWithScale() * LocalToWorld.ToMatrixWithScale();
const int32 VertBase = NumExistingVerts + (VertexBuffer.Num() / 3);
// Store index of first vertex in shape buffer
ShapeBuffer.Add(VertBase);
const int32 NumSides = 16;
const int32 NumRings = (NumSides/2) + 1;
// The first/last arc are on top of each other.
const int32 NumVerts = (NumSides+1) * (NumRings+1);
ArcVerts.Reset();
ArcVerts.AddZeroed(NumRings+1);
for (int32 RingIdx=0; RingIdx<NumRings+1; RingIdx++)
{
float Angle = ((float)RingIdx/NumRings) * PI;
// Note- unit sphere, so position always has mag of one. We can just use it for normal!
FVector& ArcVert = ArcVerts[RingIdx];
ArcVert.X = 0.0f;
ArcVert.Y = SphereInfo.Radius * FMath::Sin(Angle);
ArcVert.Z = SphereInfo.Radius * FMath::Cos(Angle);
}
// Then rotate this arc NumSides+1 times.
for (int32 SideIdx=0; SideIdx<NumSides+1; SideIdx++)
{
const FRotator ArcRotator(0, 360.f * ((float)SideIdx/NumSides), 0);
const FRotationMatrix ArcRot( ArcRotator );
const FMatrix ArcTM = ArcRot * ElemTM;
for(int32 VertIdx=0; VertIdx<NumRings+1; VertIdx++)
{
const FVector UnrealVert = ArcTM.TransformPosition(ArcVerts[VertIdx]);
UnrealBounds += UnrealVert;
VertexBuffer.Add(UnrealVert.X);
VertexBuffer.Add(UnrealVert.Y);
VertexBuffer.Add(UnrealVert.Z);
}
}
// Add all of the triangles to the mesh.
for (int32 SideIdx=0; SideIdx<NumSides; SideIdx++)
{
const int32 a0start = VertBase + ((SideIdx+0) * (NumRings+1));
const int32 a1start = VertBase + ((SideIdx+1) * (NumRings+1));
for (int32 RingIdx=0; RingIdx<NumRings; RingIdx++)
{
IndexBuffer.Add(a0start + RingIdx + 0); IndexBuffer.Add(a1start + RingIdx + 0); IndexBuffer.Add(a0start + RingIdx + 1);
IndexBuffer.Add(a1start + RingIdx + 0); IndexBuffer.Add(a1start + RingIdx + 1); IndexBuffer.Add(a0start + RingIdx + 1);
}
}
}
}
FORCEINLINE_DEBUGGABLE void ExportRigidBodySetup(UBodySetup& BodySetup, TNavStatArray<float>& VertexBuffer, TNavStatArray<int32>& IndexBuffer,
FBox& UnrealBounds, const FTransform& LocalToWorld)
{
// Make sure meshes are created before we try and export them
BodySetup.CreatePhysicsMeshes();
static TNavStatArray<int32> TemporaryShapeBuffer;
ExportRigidBodyTriMesh(BodySetup, VertexBuffer, IndexBuffer, UnrealBounds, LocalToWorld);
ExportRigidBodyConvexElements(BodySetup, VertexBuffer, IndexBuffer, TemporaryShapeBuffer, UnrealBounds, LocalToWorld);
ExportRigidBodyBoxElements(BodySetup.AggGeom, VertexBuffer, IndexBuffer, TemporaryShapeBuffer, UnrealBounds, LocalToWorld);
ExportRigidBodySphylElements(BodySetup.AggGeom, VertexBuffer, IndexBuffer, TemporaryShapeBuffer, UnrealBounds, LocalToWorld);
ExportRigidBodySphereElements(BodySetup.AggGeom, VertexBuffer, IndexBuffer, TemporaryShapeBuffer, UnrealBounds, LocalToWorld);
TemporaryShapeBuffer.Reset();
}
FORCEINLINE_DEBUGGABLE void ExportComponent(UActorComponent* Component, FRecastGeometryExport& GeomExport, const FBox* ClipBounds=NULL)
{
#if WITH_PHYSX
bool bHasData = false;
UPrimitiveComponent* PrimComp = Cast<UPrimitiveComponent>(Component);
if (PrimComp && PrimComp->IsNavigationRelevant() && (PrimComp->HasCustomNavigableGeometry() != EHasCustomNavigableGeometry::DontExport))
{
if ((PrimComp->HasCustomNavigableGeometry() != EHasCustomNavigableGeometry::Type::No) && !PrimComp->DoCustomNavigableGeometryExport(GeomExport))
{
bHasData = true;
}
UBodySetup* BodySetup = PrimComp->GetBodySetup();
if (BodySetup)
{
if (!bHasData)
{
ExportRigidBodySetup(*BodySetup, GeomExport.VertexBuffer, GeomExport.IndexBuffer, GeomExport.Data->Bounds, PrimComp->GetComponentTransform());
bHasData = true;
}
GeomExport.SlopeOverride = BodySetup->WalkableSlopeOverride;
}
}
#endif // WITH_PHYSX
}
FORCEINLINE void TransformVertexSoupToRecast(const TArray<FVector>& VertexSoup, TNavStatArray<FVector>& Verts, TNavStatArray<int32>& Faces)
{
if (VertexSoup.Num() == 0)
{
return;
}
check(VertexSoup.Num() % 3 == 0);
const int32 StaticFacesCount = VertexSoup.Num() / 3;
int32 VertsCount = Verts.Num();
const FVector* Vertex = VertexSoup.GetData();
for (int32 k = 0; k < StaticFacesCount; ++k, Vertex += 3)
{
Verts.Add(Unreal2RecastPoint(Vertex[0]));
Verts.Add(Unreal2RecastPoint(Vertex[1]));
Verts.Add(Unreal2RecastPoint(Vertex[2]));
Faces.Add(VertsCount + 2);
Faces.Add(VertsCount + 1);
Faces.Add(VertsCount + 0);
VertsCount += 3;
}
}
FORCEINLINE void CovertCoordDataToRecast(TNavStatArray<float>& Coords)
{
float* CoordPtr = Coords.GetData();
const int32 MaxIt = Coords.Num() / 3;
for (int32 i = 0; i < MaxIt; i++)
{
CoordPtr[0] = -CoordPtr[0];
const float TmpV = -CoordPtr[1];
CoordPtr[1] = CoordPtr[2];
CoordPtr[2] = TmpV;
CoordPtr += 3;
}
}
void ExportVertexSoup(const TArray<FVector>& VertexSoup, TNavStatArray<float>& VertexBuffer, TNavStatArray<int32>& IndexBuffer, FBox& UnrealBounds)
{
if (VertexSoup.Num())
{
check(VertexSoup.Num() % 3 == 0);
int32 VertBase = VertexBuffer.Num() / 3;
VertexBuffer.Reserve(VertexSoup.Num() * 3);
IndexBuffer.Reserve(VertexSoup.Num() / 3);
const int32 NumVerts = VertexSoup.Num();
for (int32 i = 0; i < NumVerts; i++)
{
const FVector& UnrealCoords = VertexSoup[i];
UnrealBounds += UnrealCoords;
const FVector RecastCoords = Unreal2RecastPoint(UnrealCoords);
VertexBuffer.Add(RecastCoords.X);
VertexBuffer.Add(RecastCoords.Y);
VertexBuffer.Add(RecastCoords.Z);
}
const int32 NumFaces = VertexSoup.Num() / 3;
for (int32 i = 0; i < NumFaces; i++)
{
IndexBuffer.Add(VertBase + 2);
IndexBuffer.Add(VertBase + 1);
IndexBuffer.Add(VertBase + 0);
VertBase += 3;
}
}
}
} // namespace RecastGeometryExport
#if WITH_PHYSX
void FRecastGeometryExport::ExportPxTriMesh16Bit(physx::PxTriangleMesh const * const TriMesh, const FTransform& LocalToWorld)
{
RecastGeometryExport::ExportPxTriMesh<PxU16>(TriMesh, LocalToWorld, VertexBuffer, IndexBuffer, Data->Bounds);
}
void FRecastGeometryExport::ExportPxTriMesh32Bit(physx::PxTriangleMesh const * const TriMesh, const FTransform& LocalToWorld)
{
RecastGeometryExport::ExportPxTriMesh<PxU32>(TriMesh, LocalToWorld, VertexBuffer, IndexBuffer, Data->Bounds);
}
void FRecastGeometryExport::ExportPxConvexMesh(physx::PxConvexMesh const * const ConvexMesh, const FTransform& LocalToWorld)
{
RecastGeometryExport::ExportPxConvexMesh(ConvexMesh, LocalToWorld, VertexBuffer, IndexBuffer, Data->Bounds);
}
void FRecastGeometryExport::ExportPxHeightField(physx::PxHeightField const * const HeightField, const FTransform& LocalToWorld)
{
RecastGeometryExport::ExportPxHeightField(HeightField, LocalToWorld, VertexBuffer, IndexBuffer, Data->Bounds);
}
#endif // WITH_PHYSX
void FRecastGeometryExport::ExportHeightFieldSlice(const FNavHeightfieldSamples& PrefetchedHeightfieldSamples, const int32 NumRows, const int32 NumCols, const FTransform& LocalToWorld, const FBox& SliceBox)
{
RecastGeometryExport::ExportHeightFieldSlice(PrefetchedHeightfieldSamples, NumRows, NumCols, LocalToWorld, VertexBuffer, IndexBuffer, SliceBox, Data->Bounds);
}
void FRecastGeometryExport::ExportCustomMesh(const FVector* InVertices, int32 NumVerts, const int32* InIndices, int32 NumIndices, const FTransform& LocalToWorld)
{
RecastGeometryExport::ExportCustomMesh(InVertices, NumVerts, InIndices, NumIndices, LocalToWorld, VertexBuffer, IndexBuffer, Data->Bounds);
}
void FRecastGeometryExport::ExportRigidBodySetup(UBodySetup& BodySetup, const FTransform& LocalToWorld)
{
RecastGeometryExport::ExportRigidBodySetup(BodySetup, VertexBuffer, IndexBuffer, Data->Bounds, LocalToWorld);
}
void FRecastGeometryExport::AddNavModifiers(const FCompositeNavModifier& Modifiers)
{
Data->Modifiers.Add(Modifiers);
}
void FRecastGeometryExport::SetNavDataPerInstanceTransformDelegate(const FNavDataPerInstanceTransformDelegate& InDelegate)
{
Data->NavDataPerInstanceTransformDelegate = InDelegate;
}
static void PartialTransformConvexHull(FConvexNavAreaData& ConvexData, const FTransform& LocalToWorld)
{
FVector ScaleXY = LocalToWorld.GetScale3D().GetAbs();
ScaleXY.Z = 1.f;
FVector TranslationXY = LocalToWorld.GetLocation();
TranslationXY.Z = 0.f;
for (FVector& Point : ConvexData.Points)
{
Point = Point*ScaleXY + TranslationXY;
}
ConvexData.MaxZ+= LocalToWorld.GetLocation().Z;
ConvexData.MinZ+= LocalToWorld.GetLocation().Z;
}
FORCEINLINE void GrowConvexHull(const float ExpandBy, const TArray<FVector>& Verts, TArray<FVector>& OutResult)
{
if (Verts.Num() < 3)
{
return;
}
struct FSimpleLine
{
FVector P1, P2;
FSimpleLine() {}
FSimpleLine(FVector Point1, FVector Point2)
: P1(Point1), P2(Point2)
{
}
static FVector Intersection(const FSimpleLine& Line1, const FSimpleLine& Line2)
{
const float A1 = Line1.P2.X - Line1.P1.X;
const float B1 = Line2.P1.X - Line2.P2.X;
const float C1 = Line2.P1.X - Line1.P1.X;
const float A2 = Line1.P2.Y - Line1.P1.Y;
const float B2 = Line2.P1.Y - Line2.P2.Y;
const float C2 = Line2.P1.Y - Line1.P1.Y;
const float Denominator = A2*B1 - A1*B2;
if (Denominator != 0)
{
const float t = (B1*C2 - B2*C1) / Denominator;
return Line1.P1 + t * (Line1.P2 - Line1.P1);
}
return FVector::ZeroVector;
}
};
TArray<FVector> AllVerts(Verts);
AllVerts.Add(Verts[0]);
AllVerts.Add(Verts[1]);
const int32 VertsCount = AllVerts.Num();
const FQuat Rotation90(FVector(0, 0, 1), FMath::DegreesToRadians(90));
float RotationAngle = MAX_FLT;
for (int32 Index = 0; Index < VertsCount - 2; ++Index)
{
const FVector& V1 = AllVerts[Index + 0];
const FVector& V2 = AllVerts[Index + 1];
const FVector& V3 = AllVerts[Index + 2];
const FVector V01 = (V1 - V2).GetSafeNormal();
const FVector V12 = (V2 - V3).GetSafeNormal();
const FVector NV1 = Rotation90.RotateVector(V01);
const float d = FVector::DotProduct(NV1, V12);
if (d < 0)
{
// CW
RotationAngle = -90;
break;
}
else if (d > 0)
{
//CCW
RotationAngle = 90;
break;
}
}
// check if we detected CW or CCW direction
if (RotationAngle >= BIG_NUMBER)
{
return;
}
const float ExpansionThreshold = 2 * ExpandBy;
const float ExpansionThresholdSQ = ExpansionThreshold * ExpansionThreshold;
const FQuat Rotation(FVector(0, 0, 1), FMath::DegreesToRadians(RotationAngle));
FSimpleLine PreviousLine;
OutResult.Reserve(Verts.Num());
for (int32 Index = 0; Index < VertsCount-2; ++Index)
{
const FVector& V1 = AllVerts[Index + 0];
const FVector& V2 = AllVerts[Index + 1];
const FVector& V3 = AllVerts[Index + 2];
FSimpleLine Line1;
if (Index > 0)
{
Line1 = PreviousLine;
}
else
{
const FVector V01 = (V1 - V2).GetSafeNormal();
const FVector N1 = Rotation.RotateVector(V01).GetSafeNormal();
const FVector MoveDir1 = N1 * ExpandBy;
Line1 = FSimpleLine(V1 + MoveDir1, V2 + MoveDir1);
}
const FVector V12 = (V2 - V3).GetSafeNormal();
const FVector N2 = Rotation.RotateVector(V12).GetSafeNormal();
const FVector MoveDir2 = N2 * ExpandBy;
const FSimpleLine Line2(V2 + MoveDir2, V3 + MoveDir2);
const FVector NewPoint = FSimpleLine::Intersection(Line1, Line2);
if (NewPoint == FVector::ZeroVector)
{
// both lines are parallel so just move our point by expansion distance
OutResult.Add(V2 + MoveDir2);
}
else
{
const FVector VectorToNewPoint = NewPoint - V2;
const float DistToNewVector = VectorToNewPoint.SizeSquared2D();
if (DistToNewVector > ExpansionThresholdSQ)
{
//clamp our point to not move to far from original location
const FVector HelpPos = V2 + VectorToNewPoint.GetSafeNormal2D() * ExpandBy * 1.4142;
OutResult.Add(HelpPos);
}
else
{
OutResult.Add(NewPoint);
}
}
PreviousLine = Line2;
}
}
//----------------------------------------------------------------------//
struct FOffMeshData
{
TArray<dtOffMeshLinkCreateParams> LinkParams;
const TMap<const UClass*, int32>* AreaClassToIdMap;
const ARecastNavMesh::FNavPolyFlags* FlagsPerArea;
FOffMeshData() : AreaClassToIdMap(NULL), FlagsPerArea(NULL) {}
FORCEINLINE void Reserve(const uint32 ElementsCount)
{
LinkParams.Reserve(ElementsCount);
}
void AddLinks(const TArray<FNavigationLink>& Links, const FTransform& LocalToWorld, int32 AgentIndex, float DefaultSnapHeight)
{
for (int32 LinkIndex = 0; LinkIndex < Links.Num(); ++LinkIndex)
{
const FNavigationLink& Link = Links[LinkIndex];
if (!Link.SupportedAgents.Contains(AgentIndex))
{
continue;
}
dtOffMeshLinkCreateParams NewInfo;
FMemory::Memzero(NewInfo);
// not doing anything to link's points order - should be already ordered properly by link processor
StoreUnrealPoint(NewInfo.vertsA0, LocalToWorld.TransformPosition(Link.Left));
StoreUnrealPoint(NewInfo.vertsB0, LocalToWorld.TransformPosition(Link.Right));
NewInfo.type = DT_OFFMESH_CON_POINT |
(Link.Direction == ENavLinkDirection::BothWays ? DT_OFFMESH_CON_BIDIR : 0) |
(Link.bSnapToCheapestArea ? DT_OFFMESH_CON_CHEAPAREA : 0);
NewInfo.snapRadius = Link.SnapRadius;
NewInfo.snapHeight = Link.bUseSnapHeight ? Link.SnapHeight : DefaultSnapHeight;
NewInfo.userID = Link.UserId;
UClass* AreaClass = Link.GetAreaClass();
const int32* AreaID = AreaClassToIdMap->Find(AreaClass);
if (AreaID != NULL)
{
NewInfo.area = *AreaID;
NewInfo.polyFlag = FlagsPerArea[*AreaID];
}
else
{
UE_LOG(LogNavigation, Warning, TEXT("FRecastTileGenerator: Trying to use undefined area class while defining Off-Mesh links! (%s)"), *GetNameSafe(AreaClass));
}
// snap area is currently not supported for regular (point-point) offmesh links
LinkParams.Add(NewInfo);
}
}
void AddSegmentLinks(const TArray<FNavigationSegmentLink>& Links, const FTransform& LocalToWorld, int32 AgentIndex, float DefaultSnapHeight)
{
for (int32 LinkIndex = 0; LinkIndex < Links.Num(); ++LinkIndex)
{
const FNavigationSegmentLink& Link = Links[LinkIndex];
if (!Link.SupportedAgents.Contains(AgentIndex))
{
continue;
}
dtOffMeshLinkCreateParams NewInfo;
FMemory::Memzero(NewInfo);
// not doing anything to link's points order - should be already ordered properly by link processor
StoreUnrealPoint(NewInfo.vertsA0, LocalToWorld.TransformPosition(Link.LeftStart));
StoreUnrealPoint(NewInfo.vertsA1, LocalToWorld.TransformPosition(Link.LeftEnd));
StoreUnrealPoint(NewInfo.vertsB0, LocalToWorld.TransformPosition(Link.RightStart));
StoreUnrealPoint(NewInfo.vertsB1, LocalToWorld.TransformPosition(Link.RightEnd));
NewInfo.type = DT_OFFMESH_CON_SEGMENT | (Link.Direction == ENavLinkDirection::BothWays ? DT_OFFMESH_CON_BIDIR : 0);
NewInfo.snapRadius = Link.SnapRadius;
NewInfo.snapHeight = Link.bUseSnapHeight ? Link.SnapHeight : DefaultSnapHeight;
NewInfo.userID = Link.UserId;
UClass* AreaClass = Link.GetAreaClass();
const int32* AreaID = AreaClassToIdMap->Find(AreaClass);
if (AreaID != NULL)
{
NewInfo.area = *AreaID;
NewInfo.polyFlag = FlagsPerArea[*AreaID];
}
else
{
UE_LOG(LogNavigation, Warning, TEXT("FRecastTileGenerator: Trying to use undefined area class while defining Off-Mesh links! (%s)"), *GetNameSafe(AreaClass));
}
LinkParams.Add(NewInfo);
}
}
protected:
void StoreUnrealPoint(float* dest, const FVector& UnrealPt)
{
const FVector RecastPt = Unreal2RecastPoint(UnrealPt);
dest[0] = RecastPt.X;
dest[1] = RecastPt.Y;
dest[2] = RecastPt.Z;
}
};
//----------------------------------------------------------------------//
// FNavMeshBuildContext
// A navmesh building reporting helper
//----------------------------------------------------------------------//
class FNavMeshBuildContext : public rcContext, public dtTileCacheLogContext
{
public:
FNavMeshBuildContext()
: rcContext(true)
{
}
protected:
/// Logs a message.
/// @param[in] category The category of the message.
/// @param[in] msg The formatted message.
/// @param[in] len The length of the formatted message.
virtual void doLog(const rcLogCategory category, const char* Msg, const int32 /*len*/)
{
switch (category)
{
case RC_LOG_ERROR:
UE_LOG(LogNavigation, Error, TEXT("Recast: %s"), ANSI_TO_TCHAR( Msg ) );
break;
case RC_LOG_WARNING:
UE_LOG(LogNavigation, Log, TEXT("Recast: %s"), ANSI_TO_TCHAR( Msg ) );
break;
default:
UE_LOG(LogNavigation, Verbose, TEXT("Recast: %s"), ANSI_TO_TCHAR( Msg ) );
break;
}
}
virtual void doDtLog(const char* Msg, const int32 /*len*/)
{
UE_LOG(LogNavigation, Error, TEXT("Recast: %s"), ANSI_TO_TCHAR(Msg));
}
};
//----------------------------------------------------------------------//
struct FTileCacheCompressor : public dtTileCacheCompressor
{
struct FCompressedCacheHeader
{
int32 UncompressedSize;
};
virtual int32 maxCompressedSize(const int32 bufferSize)
{
return FMath::TruncToInt(bufferSize * 1.1f) + sizeof(FCompressedCacheHeader);
}
virtual dtStatus compress(const uint8* buffer, const int32 bufferSize,
uint8* compressed, const int32 maxCompressedSize, int32* compressedSize)
{
const int32 HeaderSize = sizeof(FCompressedCacheHeader);
FCompressedCacheHeader DataHeader;
DataHeader.UncompressedSize = bufferSize;
FMemory::Memcpy((void*)compressed, &DataHeader, HeaderSize);
uint8* DataPtr = compressed + HeaderSize;
int32 DataSize = maxCompressedSize - HeaderSize;
FCompression::CompressMemory(NAME_Zlib, (void*)DataPtr, DataSize, (const void*)buffer, bufferSize, COMPRESS_BiasMemory);
*compressedSize = DataSize + HeaderSize;
return DT_SUCCESS;
}
virtual dtStatus decompress(const uint8* compressed, const int32 compressedSize,
uint8* buffer, const int32 maxBufferSize, int32* bufferSize)
{
const int32 HeaderSize = sizeof(FCompressedCacheHeader);
FCompressedCacheHeader DataHeader;
FMemory::Memcpy(&DataHeader, (void*)compressed, HeaderSize);
const uint8* DataPtr = compressed + HeaderSize;
const int32 DataSize = compressedSize - HeaderSize;
FCompression::UncompressMemory(NAME_Zlib, (void*)buffer, DataHeader.UncompressedSize, (const void*)DataPtr, DataSize);
*bufferSize = DataHeader.UncompressedSize;
return DT_SUCCESS;
}
};
struct FTileCacheAllocator : public dtTileCacheAlloc
{
virtual void reset()
{
check(0 && "dtTileCacheAlloc.reset() is not supported!");
}
virtual void* alloc(const int32 Size)
{
return dtAlloc(Size, DT_ALLOC_TEMP);
}
virtual void free(void* Data)
{
dtFree(Data);
}
};
//----------------------------------------------------------------------//
// FVoxelCacheRasterizeContext
//----------------------------------------------------------------------//
struct FVoxelCacheRasterizeContext
{
FVoxelCacheRasterizeContext()
{
RasterizeHF = NULL;
}
~FVoxelCacheRasterizeContext()
{
rcFreeHeightField(RasterizeHF);
RasterizeHF = 0;
}
void Create(int32 FieldSize, float CellSize, float CellHeight)
{
if (RasterizeHF == NULL)
{
const float DummyBounds[3] = { 0 };
RasterizeHF = rcAllocHeightfield();
rcCreateHeightfield(NULL, *RasterizeHF, FieldSize, FieldSize, DummyBounds, DummyBounds, CellSize, CellHeight);
}
}
void Reset()
{
rcResetHeightfield(*RasterizeHF);
}
void SetupForTile(const float* TileBMin, const float* TileBMax, const float RasterizationPadding)
{
Reset();
rcVcopy(RasterizeHF->bmin, TileBMin);
rcVcopy(RasterizeHF->bmax, TileBMax);
RasterizeHF->bmin[0] -= RasterizationPadding;
RasterizeHF->bmin[2] -= RasterizationPadding;
RasterizeHF->bmax[0] += RasterizationPadding;
RasterizeHF->bmax[2] += RasterizationPadding;
}
rcHeightfield* RasterizeHF;
};
static FVoxelCacheRasterizeContext VoxelCacheContext;
uint32 GetTileCacheSizeHelper(TArray<FNavMeshTileData>& CompressedTiles)
{
uint32 TotalMemory = 0;
for (int32 i = 0; i < CompressedTiles.Num(); i++)
{
TotalMemory += CompressedTiles[i].DataSize;
}
return TotalMemory;
}
static FBox CalculateTileBounds(int32 X, int32 Y, const FVector& RcNavMeshOrigin, const FBox& TotalNavBounds, float TileSizeInWorldUnits)
{
FBox TileBox(
RcNavMeshOrigin + (FVector(X + 0, 0, Y + 0) * TileSizeInWorldUnits),
RcNavMeshOrigin + (FVector(X + 1, 0, Y + 1) * TileSizeInWorldUnits)
);
TileBox = Recast2UnrealBox(TileBox);
TileBox.Min.Z = TotalNavBounds.Min.Z;
TileBox.Max.Z = TotalNavBounds.Max.Z;
// unreal coord space
return TileBox;
}
//----------------------------------------------------------------------//
// FRecastTileGenerator
//----------------------------------------------------------------------//
FRecastTileGenerator::FRecastTileGenerator(FRecastNavMeshGenerator& ParentGenerator, const FIntPoint& Location)
{
bSucceeded = false;
bUpdateGeometry = true;
bHasLowAreaModifiers = false;
TileX = Location.X;
TileY = Location.Y;
TileConfig = ParentGenerator.GetConfig();
Version = ParentGenerator.GetVersion();
AdditionalCachedData = ParentGenerator.GetAdditionalCachedData();
ParentGeneratorWeakPtr = ParentGenerator.AsShared();
#if TIME_SLICE_NAV_REGEN
bDoneAsyncDataGathering = false;
bDoneRegenerateCompressedLayers = false;
bDoneWork = false;
#endif
}
FRecastTileGenerator::~FRecastTileGenerator()
{
}
void FRecastTileGenerator::Setup(const FRecastNavMeshGenerator& ParentGenerator, const TArray<FBox>& DirtyAreas)
{
const FVector RcNavMeshOrigin = ParentGenerator.GetRcNavMeshOrigin();
const FBox NavTotalBounds = ParentGenerator.GetTotalBounds();
const float TileCellSize = (TileConfig.tileSize * TileConfig.cs);
NavDataConfig = ParentGenerator.GetOwner()->GetConfig();
TileBB = CalculateTileBounds(TileX, TileY, RcNavMeshOrigin, NavTotalBounds, TileCellSize);
TileBBExpandedForAgent = TileBB.ExpandBy(NavDataConfig.AgentRadius * 2 + TileConfig.cs);
const FBox RCBox = Unreal2RecastBox(TileBB);
rcVcopy(TileConfig.bmin, &RCBox.Min.X);
rcVcopy(TileConfig.bmax, &RCBox.Max.X);
// from passed in boxes pick the ones overlapping with tile bounds
bFullyEncapsulatedByInclusionBounds = true;
const TNavStatArray<FBox>& ParentBounds = ParentGenerator.GetInclusionBounds();
if (ParentBounds.Num() > 0)
{
bFullyEncapsulatedByInclusionBounds = false;
InclusionBounds.Reserve(ParentBounds.Num());
for (const FBox& Bounds : ParentBounds)
{
if (Bounds.Intersect(TileBB))
{
InclusionBounds.Add(Bounds);
bFullyEncapsulatedByInclusionBounds = DoesBoxContainBox(Bounds, TileBB);
}
}
}
const bool bGeometryChanged = (DirtyAreas.Num() == 0);
if (!bGeometryChanged)
{
// Get compressed tile cache layers if they exist for this location
CompressedLayers = ParentGenerator.GetOwner()->GetTileCacheLayers(TileX, TileY);
for (FNavMeshTileData& LayerData : CompressedLayers)
{
// we don't want to modify shared state inside async task, so make sure we are unique owner
LayerData.MakeUnique();
}
}
// We have to regenerate layers data in case geometry is changed or tile cache is missing
bRegenerateCompressedLayers = (bGeometryChanged || CompressedLayers.Num() == 0);
// Gather geometry for tile if it inside navigable bounds
if (InclusionBounds.Num())
{
if (!bRegenerateCompressedLayers)
{
// Mark layers that needs to be updated
DirtyLayers.Init(false, CompressedLayers.Num());
for (const FNavMeshTileData& LayerData : CompressedLayers)
{
for (FBox DirtyBox : DirtyAreas)
{
if (DirtyBox.Intersect(LayerData.LayerBBox))
{
DirtyLayers[LayerData.LayerIndex] = true;
}
}
}
}
if (ParentGenerator.GatherGeometryOnGameThread())
{
GatherGeometry(ParentGenerator, bRegenerateCompressedLayers);
}
else
{
PrepareGeometrySources(ParentGenerator, bRegenerateCompressedLayers);
}
}
//
UsedMemoryOnStartup = GetUsedMemCount() + sizeof(FRecastTileGenerator);
}
bool FRecastTileGenerator::HasDataToBuild() const
{
return
CompressedLayers.Num()
|| Modifiers.Num()
|| OffmeshLinks.Num()
|| RawGeometry.Num()
|| (InclusionBounds.Num() && NavigationRelevantData.Num() > 0);
}
ETimeSliceWorkResult FRecastTileGenerator::DoWork()
{
TSharedPtr<FNavDataGenerator, ESPMode::ThreadSafe> ParentGenerator = ParentGeneratorWeakPtr.Pin();
ETimeSliceWorkResult TimeSliceWorkResult = ETimeSliceWorkResult::Succeeded;
if (ParentGenerator.IsValid())
{
if (InclusionBounds.Num()
#if TIME_SLICE_NAV_REGEN
&& !bDoneAsyncDataGathering
#endif
)
{
DoAsyncGeometryGathering();
}
TimeSliceWorkResult = GenerateTile();
//bSucceeded is set false in the constructor anyway
bSucceeded = (TimeSliceWorkResult == ETimeSliceWorkResult::Succeeded);
}
#if TIME_SLICE_NAV_REGEN
if (TimeSliceWorkResult != ETimeSliceWorkResult::CallAgain)
#endif
{
DumpAsyncData();
if (!bSucceeded)
{
TimeSliceWorkResult = ETimeSliceWorkResult::Failed;
}
#if TIME_SLICE_NAV_REGEN
bDoneWork = true;
#endif
}
return TimeSliceWorkResult;
}
void FRecastTileGenerator::DumpAsyncData()
{
RawGeometry.Empty();
Modifiers.Empty();
OffmeshLinks.Empty();
NavigationRelevantData.Empty();
NavOctree = nullptr;
}
void FRecastTileGenerator::DoAsyncGeometryGathering()
{
QUICK_SCOPE_CYCLE_COUNTER(STAT_RecastNavMeshGenerator_PrepareGeometrySources);
#if TIME_SLICE_NAV_REGEN
bDoneAsyncDataGathering = true;
#endif
for (auto& ElementData : NavigationRelevantData)
{
if (ElementData->GetOwner() == nullptr)
{
UE_LOG(LogNavigation, Warning, TEXT("DoAsyncGeometryGathering: skipping an element with no longer valid Owner"));
continue;
}
bool bDumpGeometryData = false;
if (ElementData->IsPendingLazyGeometryGathering() && ElementData->SupportsGatheringGeometrySlices())
{
QUICK_SCOPE_CYCLE_COUNTER(STAT_RecastNavMeshGenerator_LandscapeSlicesExporting);
FRecastGeometryExport GeomExport(*ElementData);
INavRelevantInterface* NavRelevant = Cast<INavRelevantInterface>(ElementData->GetOwner());
if(NavRelevant)
{
NavRelevant->PrepareGeometryExportSync();
// adding a small bump to avoid special case of zero-expansion when tile bounds
// overlap landscape's tile bounds
NavRelevant->GatherGeometrySlice(GeomExport, TileBBExpandedForAgent);
RecastGeometryExport::CovertCoordDataToRecast(GeomExport.VertexBuffer);
RecastGeometryExport::StoreCollisionCache(GeomExport);
bDumpGeometryData = true;
}
else
{
UE_LOG(LogNavigation, Error, TEXT("DoAsyncGeometryGathering: got an invalid NavRelevant instance!"));
}
}
if (ElementData->IsPendingLazyGeometryGathering() || ElementData->IsPendingLazyModifiersGathering())
{
NavOctree->DemandLazyDataGathering(*ElementData);
}
const bool bExportGeometry = bUpdateGeometry && ElementData->HasGeometry();
if (bExportGeometry)
{
if (ARecastNavMesh::IsVoxelCacheEnabled())
{
TNavStatArray<rcSpanCache> SpanData;
rcSpanCache* CachedVoxels = 0;
int32 NumCachedVoxels = 0;
DECLARE_SCOPE_CYCLE_COUNTER(TEXT("Rasterization: prepare voxel cache"), Stat_RecastRasterCachePrep, STATGROUP_Navigation);
if (!HasVoxelCache(ElementData->VoxelData, CachedVoxels, NumCachedVoxels))
{
// rasterize
PrepareVoxelCache(ElementData->CollisionData, SpanData);
CachedVoxels = SpanData.GetData();
NumCachedVoxels = SpanData.Num();
// encode
const int32 PrevElementMemory = ElementData->GetAllocatedSize();
FNavigationRelevantData* ModData = (FNavigationRelevantData*)&ElementData;
AddVoxelCache(ModData->VoxelData, CachedVoxels, NumCachedVoxels);
const int32 NewElementMemory = ElementData->GetAllocatedSize();
const int32 ElementMemoryDelta = NewElementMemory - PrevElementMemory;
INC_MEMORY_STAT_BY(STAT_Navigation_CollisionTreeMemory, ElementMemoryDelta);
}
}
else
{
ValidateAndAppendGeometry(ElementData);
}
if (bDumpGeometryData)
{
const_cast<FNavigationRelevantData&>(*ElementData).CollisionData.Empty();
}
}
const FCompositeNavModifier ModifierInstance = ElementData->Modifiers.HasMetaAreas() ? ElementData->Modifiers.GetInstantiatedMetaModifier(&NavDataConfig, ElementData->SourceObject) : ElementData->Modifiers;
if (ModifierInstance.IsEmpty() == false)
{
AppendModifier(ModifierInstance, ElementData->NavDataPerInstanceTransformDelegate);
}
}
}
void FRecastTileGenerator::PrepareGeometrySources(const FRecastNavMeshGenerator& ParentGenerator, bool bGeometryChanged)
{
QUICK_SCOPE_CYCLE_COUNTER(STAT_RecastNavMeshGenerator_PrepareGeometrySources);
UNavigationSystemV1* NavSys = FNavigationSystem::GetCurrent<UNavigationSystemV1>(ParentGenerator.GetWorld());
FNavigationOctree* NavOctreeInstance = NavSys ? NavSys->GetMutableNavOctree() : nullptr;
check(NavOctreeInstance);
NavigationRelevantData.Reset();
NavOctree = NavOctreeInstance->AsShared();
bUpdateGeometry = bGeometryChanged;
for (FNavigationOctree::TConstElementBoxIterator<FNavigationOctree::DefaultStackAllocator> It(*NavOctreeInstance, ParentGenerator.GrowBoundingBox(TileBB, /*bIncludeAgentHeight*/ false));
It.HasPendingElements();
It.Advance())
{
const FNavigationOctreeElement& Element = It.GetCurrentElement();
const bool bShouldUse = Element.ShouldUseGeometry(NavDataConfig);
if (bShouldUse)
{
const bool bExportGeometry = bGeometryChanged && (Element.Data->HasGeometry() || Element.Data->IsPendingLazyGeometryGathering());
if (bExportGeometry
|| (Element.Data->IsPendingLazyModifiersGathering() || Element.Data->Modifiers.HasMetaAreas() == true || Element.Data->Modifiers.IsEmpty() == false))
{
NavigationRelevantData.Add(Element.Data);
}
}
}
}
void FRecastTileGenerator::GatherGeometry(const FRecastNavMeshGenerator& ParentGenerator, bool bGeometryChanged)
{
QUICK_SCOPE_CYCLE_COUNTER(STAT_RecastNavMeshGenerator_GatherGeometry);
UNavigationSystemV1* NavSys = FNavigationSystem::GetCurrent<UNavigationSystemV1>(ParentGenerator.GetWorld());
FNavigationOctree* NavigationOctree = NavSys ? NavSys->GetMutableNavOctree() : nullptr;
if (NavigationOctree == nullptr)
{
return;
}
const FNavDataConfig& OwnerNavDataConfig = ParentGenerator.GetOwner()->GetConfig();
for (FNavigationOctree::TConstElementBoxIterator<FNavigationOctree::DefaultStackAllocator> It(*NavigationOctree, ParentGenerator.GrowBoundingBox(TileBB, /*bIncludeAgentHeight*/ false));
It.HasPendingElements();
It.Advance())
{
const FNavigationOctreeElement& Element = It.GetCurrentElement();
const bool bShouldUse = Element.ShouldUseGeometry(OwnerNavDataConfig);
if (bShouldUse)
{
bool bDumpGeometryData = false;
if (Element.Data->IsPendingLazyGeometryGathering() || Element.Data->IsPendingLazyModifiersGathering())
{
const bool bSupportsSlices = Element.Data->SupportsGatheringGeometrySlices();
if (bSupportsSlices == false || Element.Data->IsPendingLazyModifiersGathering() == true)
{
QUICK_SCOPE_CYCLE_COUNTER(STAT_RecastNavMeshGenerator_LazyGeometryExport);
NavigationOctree->DemandLazyDataGathering(Element);
}
if (bSupportsSlices == true)
{
QUICK_SCOPE_CYCLE_COUNTER(STAT_RecastNavMeshGenerator_LandscapeSlicesExporting);
FRecastGeometryExport GeomExport(const_cast<FNavigationRelevantData&>(*Element.Data));
INavRelevantInterface* NavRelevant = const_cast<INavRelevantInterface*>(Cast<const INavRelevantInterface>(Element.GetOwner()));
if (NavRelevant)
{
NavRelevant->PrepareGeometryExportSync();
// adding a small bump to avoid special case of zero-expansion when tile bounds
// overlap landscape's tile bounds
NavRelevant->GatherGeometrySlice(GeomExport, TileBBExpandedForAgent);
RecastGeometryExport::CovertCoordDataToRecast(GeomExport.VertexBuffer);
RecastGeometryExport::StoreCollisionCache(GeomExport);
bDumpGeometryData = true;
}
else
{
UE_LOG(LogNavigation, Error, TEXT("GatherGeometry: got an invalid NavRelevant instance!"));
}
}
}
const bool bExportGeometry = bGeometryChanged && Element.Data->HasGeometry();
if (bExportGeometry)
{
if (ARecastNavMesh::IsVoxelCacheEnabled())
{
TNavStatArray<rcSpanCache> SpanData;
rcSpanCache* CachedVoxels = 0;
int32 NumCachedVoxels = 0;
DECLARE_SCOPE_CYCLE_COUNTER(TEXT("Rasterization: prepare voxel cache"), Stat_RecastRasterCachePrep, STATGROUP_Navigation);
if (!HasVoxelCache(Element.Data->VoxelData, CachedVoxels, NumCachedVoxels))
{
// rasterize
PrepareVoxelCache(Element.Data->CollisionData, SpanData);
CachedVoxels = SpanData.GetData();
NumCachedVoxels = SpanData.Num();
// encode
const int32 PrevElementMemory = Element.Data->GetAllocatedSize();
FNavigationRelevantData* ModData = (FNavigationRelevantData*)&Element.Data;
AddVoxelCache(ModData->VoxelData, CachedVoxels, NumCachedVoxels);
const int32 NewElementMemory = Element.Data->GetAllocatedSize();
const int32 ElementMemoryDelta = NewElementMemory - PrevElementMemory;
INC_MEMORY_STAT_BY(STAT_Navigation_CollisionTreeMemory, ElementMemoryDelta);
}
}
else
{
ValidateAndAppendGeometry(Element.Data);
}
if (bDumpGeometryData)
{
const_cast<FNavigationRelevantData&>(*Element.Data).CollisionData.Empty();
}
}
const FCompositeNavModifier ModifierInstance = Element.GetModifierForAgent(&OwnerNavDataConfig);
if (ModifierInstance.IsEmpty() == false)
{
AppendModifier(ModifierInstance, Element.Data->NavDataPerInstanceTransformDelegate);
}
}
}
}
void FRecastTileGenerator::ApplyVoxelFilter(rcHeightfield* HF, float WalkableRadius)
{
SCOPE_CYCLE_COUNTER(STAT_Navigation_TileVoxelFilteringAsync);
if (HF != NULL)
{
const int32 Width = HF->width;
const int32 Height = HF->height;
const float CellSize = HF->cs;
const float CellHeight = HF->ch;
const float BottomX = HF->bmin[0];
const float BottomZ = HF->bmin[1];
const float BottomY = HF->bmin[2];
const int32 SpansCount = Width*Height;
// we need to expand considered bounding boxes so that
// it doesn't create "fake cliffs"
const float ExpandBBBy = WalkableRadius*CellSize;
const FBox* BBox = InclusionBounds.GetData();
// optimized common case of single box
if (InclusionBounds.Num() == 1)
{
const FBox BB = BBox->ExpandBy(ExpandBBBy);
rcSpan** Span = HF->spans;
for (int32 y = 0; y < Height; ++y)
{
for (int32 x = 0; x < Width; ++x)
{
const float SpanX = -(BottomX + x * CellSize);
const float SpanY = -(BottomY + y * CellSize);
// mark all spans outside of InclusionBounds as unwalkable
for (rcSpan* s = *Span; s; s = s->next)
{
if (s->data.area == RC_WALKABLE_AREA)
{
const float SpanMin = CellHeight * s->data.smin + BottomZ;
const float SpanMax = CellHeight * s->data.smax + BottomZ;
const FVector SpanMinV(SpanX-CellSize, SpanY-CellSize, SpanMin);
const FVector SpanMaxV(SpanX, SpanY, SpanMax);
if (BB.IsInside(SpanMinV) == false && BB.IsInside(SpanMaxV) == false)
{
s->data.area = RC_NULL_AREA;
}
}
}
++Span;
}
}
}
else
{
TArray<FBox> Bounds;
Bounds.Reserve(InclusionBounds.Num());
for (int32 i = 0; i < InclusionBounds.Num(); ++i, ++BBox)
{
Bounds.Add(BBox->ExpandBy(ExpandBBBy));
}
const int32 BoundsCount = Bounds.Num();
rcSpan** Span = HF->spans;
for (int32 y = 0; y < Height; ++y)
{
for (int32 x = 0; x < Width; ++x)
{
const float SpanX = -(BottomX + x * CellSize);
const float SpanY = -(BottomY + y * CellSize);
// mark all spans outside of InclusionBounds as unwalkable
for (rcSpan* s = *Span; s; s = s->next)
{
if (s->data.area == RC_WALKABLE_AREA)
{
const float SpanMin = CellHeight * s->data.smin + BottomZ;
const float SpanMax = CellHeight * s->data.smax + BottomZ;
const FVector SpanMinV(SpanX-CellSize, SpanY-CellSize, SpanMin);
const FVector SpanMaxV(SpanX, SpanY, SpanMax);
bool bIsInsideAnyBB = false;
const FBox* BB = Bounds.GetData();
for (int32 BoundIndex = 0; BoundIndex < BoundsCount; ++BoundIndex, ++BB)
{
if (BB->IsInside(SpanMinV) || BB->IsInside(SpanMaxV))
{
bIsInsideAnyBB = true;
break;
}
}
if (bIsInsideAnyBB == false)
{
s->data.area = RC_NULL_AREA;
}
}
}
++Span;
}
}
}
}
}
void FRecastTileGenerator::PrepareVoxelCache(const TNavStatArray<uint8>& RawCollisionCache, TNavStatArray<rcSpanCache>& SpanData)
{
// tile's geometry: voxel cache (only for synchronous rebuilds)
const int32 WalkableClimbVX = TileConfig.walkableClimb;
const float WalkableSlopeCos = FMath::Cos(FMath::DegreesToRadians(TileConfig.walkableSlopeAngle));
const float RasterizationPadding = TileConfig.borderSize * TileConfig.cs;
FRecastGeometryCache CachedCollisions(RawCollisionCache.GetData());
VoxelCacheContext.SetupForTile(TileConfig.bmin, TileConfig.bmax, RasterizationPadding);
float SlopeCosPerActor = WalkableSlopeCos;
CachedCollisions.Header.SlopeOverride.ModifyWalkableFloorZ(SlopeCosPerActor);
// rasterize triangle soup
TNavStatArray<uint8> TriAreas;
TriAreas.AddZeroed(CachedCollisions.Header.NumFaces);
rcMarkWalkableTrianglesCos(0, SlopeCosPerActor,
CachedCollisions.Verts, CachedCollisions.Header.NumVerts,
CachedCollisions.Indices, CachedCollisions.Header.NumFaces,
TriAreas.GetData());
rcRasterizeTriangles(0, CachedCollisions.Verts, CachedCollisions.Header.NumVerts,
CachedCollisions.Indices, TriAreas.GetData(), CachedCollisions.Header.NumFaces,
*VoxelCacheContext.RasterizeHF, WalkableClimbVX);
const int32 NumSpans = rcCountSpans(0, *VoxelCacheContext.RasterizeHF);
if (NumSpans > 0)
{
SpanData.AddZeroed(NumSpans);
rcCacheSpans(0, *VoxelCacheContext.RasterizeHF, SpanData.GetData());
}
}
bool FRecastTileGenerator::HasVoxelCache(const TNavStatArray<uint8>& RawVoxelCache, rcSpanCache*& CachedVoxels, int32& NumCachedVoxels) const
{
FRecastVoxelCache VoxelCache(RawVoxelCache.GetData());
for (FRecastVoxelCache::FTileInfo* iTile = VoxelCache.Tiles; iTile; iTile = iTile->NextTile)
{
if (iTile->TileX == TileX && iTile->TileY == TileY)
{
CachedVoxels = iTile->SpanData;
NumCachedVoxels = iTile->NumSpans;
return true;
}
}
return false;
}
void FRecastTileGenerator::AddVoxelCache(TNavStatArray<uint8>& RawVoxelCache, const rcSpanCache* CachedVoxels, const int32 NumCachedVoxels) const
{
if (RawVoxelCache.Num() == 0)
{
RawVoxelCache.AddZeroed(sizeof(int32));
}
int32* NumTiles = (int32*)RawVoxelCache.GetData();
*NumTiles = *NumTiles + 1;
const int32 NewCacheIdx = RawVoxelCache.Num();
const int32 HeaderSize = sizeof(FRecastVoxelCache::FTileInfo);
const int32 VoxelsSize = sizeof(rcSpanCache) * NumCachedVoxels;
const int32 EntrySize = HeaderSize + VoxelsSize;
RawVoxelCache.AddZeroed(EntrySize);
FRecastVoxelCache::FTileInfo* TileInfo = (FRecastVoxelCache::FTileInfo*)(RawVoxelCache.GetData() + NewCacheIdx);
TileInfo->TileX = TileX;
TileInfo->TileY = TileY;
TileInfo->NumSpans = NumCachedVoxels;
FMemory::Memcpy(RawVoxelCache.GetData() + NewCacheIdx + HeaderSize, CachedVoxels, VoxelsSize);
}
void FRecastTileGenerator::AppendModifier(const FCompositeNavModifier& Modifier, const FNavDataPerInstanceTransformDelegate& InTransformsDelegate)
{
// append all offmesh links (not included in compress layers)
OffmeshLinks.Append(Modifier.GetSimpleLinks());
// evaluate custom links
const FCustomLinkNavModifier* LinkModifier = Modifier.GetCustomLinks().GetData();
for (int32 i = 0; i < Modifier.GetCustomLinks().Num(); i++, LinkModifier++)
{
FSimpleLinkNavModifier SimpleLinkCollection(UNavLinkDefinition::GetLinksDefinition(LinkModifier->GetNavLinkClass()), LinkModifier->LocalToWorld);
OffmeshLinks.Add(SimpleLinkCollection);
}
if (Modifier.GetAreas().Num() == 0)
{
return;
}
bHasLowAreaModifiers = bHasLowAreaModifiers || Modifier.HasLowAreaModifiers();
FRecastAreaNavModifierElement ModifierElement;
// Gather per instance transforms if any
if (InTransformsDelegate.IsBound())
{
InTransformsDelegate.Execute(TileBBExpandedForAgent, ModifierElement.PerInstanceTransform);
// skip this modifier in case there is no instances for this tile
if (ModifierElement.PerInstanceTransform.Num() == 0)
{
return;
}
}
ModifierElement.Areas = Modifier.GetAreas();
Modifiers.Add(MoveTemp(ModifierElement));
}
void FRecastTileGenerator::ValidateAndAppendGeometry(TSharedRef<FNavigationRelevantData, ESPMode::ThreadSafe> ElementData)
{
const FNavigationRelevantData& DataRef = ElementData.Get();
if (DataRef.IsCollisionDataValid())
{
AppendGeometry(DataRef.CollisionData, DataRef.NavDataPerInstanceTransformDelegate);
}
}
void FRecastTileGenerator::AppendGeometry(const TNavStatArray<uint8>& RawCollisionCache, const FNavDataPerInstanceTransformDelegate& InTransformsDelegate)
{
if (RawCollisionCache.Num() == 0)
{
return;
}
FRecastRawGeometryElement GeometryElement;
FRecastGeometryCache CollisionCache(RawCollisionCache.GetData());
// Gather per instance transforms
if (InTransformsDelegate.IsBound())
{
InTransformsDelegate.Execute(TileBBExpandedForAgent, GeometryElement.PerInstanceTransform);
if (GeometryElement.PerInstanceTransform.Num() == 0)
{
return;
}
}
const int32 NumCoords = CollisionCache.Header.NumVerts * 3;
const int32 NumIndices = CollisionCache.Header.NumFaces * 3;
if (NumIndices > 0)
{
GeometryElement.GeomCoords.SetNumUninitialized(NumCoords);
GeometryElement.GeomIndices.SetNumUninitialized(NumIndices);
FMemory::Memcpy(GeometryElement.GeomCoords.GetData(), CollisionCache.Verts, sizeof(float) * NumCoords);
FMemory::Memcpy(GeometryElement.GeomIndices.GetData(), CollisionCache.Indices, sizeof(int32) * NumIndices);
RawGeometry.Add(MoveTemp(GeometryElement));
}
}
ETimeSliceWorkResult FRecastTileGenerator::GenerateTile()
{
ETimeSliceWorkResult TimeSliceWorkResult = ETimeSliceWorkResult::Succeeded;
FNavMeshBuildContext BuildContext;
if (bRegenerateCompressedLayers
#if TIME_SLICE_NAV_REGEN
&& !bDoneRegenerateCompressedLayers
#endif
)
{
CompressedLayers.Reset();
const bool bSuccess = GenerateCompressedLayers(BuildContext);
#if TIME_SLICE_NAV_REGEN
bDoneRegenerateCompressedLayers = true;
#endif
if (bSuccess)
{
// Mark all layers as dirty
DirtyLayers.Init(true, CompressedLayers.Num());
#if TIME_SLICE_NAV_REGEN
TimeSliceWorkResult = ETimeSliceWorkResult::CallAgain;
#else
TimeSliceWorkResult = ETimeSliceWorkResult::Succeeded;
#endif
}
else
{
TimeSliceWorkResult = ETimeSliceWorkResult::Failed;
}
}
if (TimeSliceWorkResult == ETimeSliceWorkResult::Succeeded)
{
const bool bSuccess = GenerateNavigationData(BuildContext);
if (!bSuccess)
{
TimeSliceWorkResult = ETimeSliceWorkResult::Failed;
}
}
// it's possible to have valid generation with empty resulting tile (no navigable geometry in tile)
return TimeSliceWorkResult;
}
struct FTileRasterizationContext
{
FTileRasterizationContext() : SolidHF(0), LayerSet(0), CompactHF(0)
{
}
~FTileRasterizationContext()
{
rcFreeHeightField(SolidHF);
rcFreeHeightfieldLayerSet(LayerSet);
rcFreeCompactHeightfield(CompactHF);
}
struct rcHeightfield* SolidHF;
struct rcHeightfieldLayerSet* LayerSet;
struct rcCompactHeightfield* CompactHF;
TArray<FNavMeshTileData> Layers;
};
static void RasterizeGeometry(
FNavMeshBuildContext& BuildContext, const FRecastBuildConfig& TileConfig,
const TArray<float>& Coords, const TArray<int32>& Indices, FTileRasterizationContext& RasterContext)
{
const int32 NumFaces = Indices.Num() / 3;
const int32 NumVerts = Coords.Num() / 3;
TNavStatArray<uint8> TriAreas;
TriAreas.Reserve(NumFaces);
TriAreas.AddZeroed(NumFaces);
rcMarkWalkableTriangles(&BuildContext, TileConfig.walkableSlopeAngle,
Coords.GetData(), NumVerts, Indices.GetData(), NumFaces,
TriAreas.GetData());
rcRasterizeTriangles(&BuildContext,
Coords.GetData(), NumVerts,
Indices.GetData(), TriAreas.GetData(), NumFaces,
*RasterContext.SolidHF, TileConfig.walkableClimb);
}
static void RasterizeGeometry(
FNavMeshBuildContext& BuildContext,const FRecastBuildConfig& TileConfig,
const TArray<float>& Coords, const TArray<int32>& Indices, const FTransform& LocalToWorld, FTileRasterizationContext& RasterContext)
{
TArray<float> WorldRecastCoords;
WorldRecastCoords.SetNumUninitialized(Coords.Num());
FMatrix LocalToRecastWorld = LocalToWorld.ToMatrixWithScale()*Unreal2RecastMatrix();
// Convert geometry to recast world space
for (int32 i = 0; i < Coords.Num(); i+=3)
{
// collision cache stores coordinates in recast space, convert them to unreal and transform to recast world space
FVector WorldRecastCoord = LocalToRecastWorld.TransformPosition(Recast2UnrealPoint(&Coords[i]));
WorldRecastCoords[i+0] = WorldRecastCoord.X;
WorldRecastCoords[i+1] = WorldRecastCoord.Y;
WorldRecastCoords[i+2] = WorldRecastCoord.Z;
}
RasterizeGeometry(BuildContext, TileConfig, WorldRecastCoords, Indices, RasterContext);
}
bool FRecastTileGenerator::GenerateCompressedLayers(FNavMeshBuildContext& BuildContext)
{
SCOPE_CYCLE_COUNTER(STAT_Navigation_RecastBuildCompressedLayers);
TileConfig.width = TileConfig.tileSize + TileConfig.borderSize*2;
TileConfig.height = TileConfig.tileSize + TileConfig.borderSize*2;
const float BBoxPadding = TileConfig.borderSize * TileConfig.cs;
TileConfig.bmin[0] -= BBoxPadding;
TileConfig.bmin[2] -= BBoxPadding;
TileConfig.bmax[0] += BBoxPadding;
TileConfig.bmax[2] += BBoxPadding;
BuildContext.log(RC_LOG_PROGRESS, "GenerateCompressedLayers:");
BuildContext.log(RC_LOG_PROGRESS, " - %d x %d cells", TileConfig.width, TileConfig.height);
FTileRasterizationContext RasterContext;
const bool bHasGeometry = RawGeometry.Num() > 0;
// Allocate voxel heightfield where we rasterize our input data to.
if (bHasGeometry)
{
{
SCOPE_CYCLE_COUNTER(STAT_Navigation_RecastCreateHeightField);
RasterContext.SolidHF = rcAllocHeightfield();
if (RasterContext.SolidHF == NULL)
{
BuildContext.log(RC_LOG_ERROR, "GenerateCompressedLayers: Out of memory 'SolidHF'.");
return false;
}
if (!rcCreateHeightfield(&BuildContext, *RasterContext.SolidHF, TileConfig.width, TileConfig.height, TileConfig.bmin, TileConfig.bmax, TileConfig.cs, TileConfig.ch))
{
BuildContext.log(RC_LOG_ERROR, "GenerateCompressedLayers: Could not create solid heightfield.");
return false;
}
}
{
// Rasterize geometry
SCOPE_CYCLE_COUNTER(STAT_Navigation_RecastRasterizeTriangles)
for (const FRecastRawGeometryElement& Element : RawGeometry)
{
for (const FTransform& InstanceTransform : Element.PerInstanceTransform)
{
RasterizeGeometry(BuildContext, TileConfig, Element.GeomCoords, Element.GeomIndices, InstanceTransform, RasterContext);
}
if (Element.PerInstanceTransform.Num() == 0)
{
RasterizeGeometry(BuildContext, TileConfig, Element.GeomCoords, Element.GeomIndices, RasterContext);
}
}
}
}
if (!RasterContext.SolidHF || RasterContext.SolidHF->pools == 0)
{
BuildContext.log(RC_LOG_WARNING, "GenerateCompressedLayers: empty tile - aborting");
return true;
}
// Reject voxels outside generation boundaries
if (TileConfig.bPerformVoxelFiltering && !bFullyEncapsulatedByInclusionBounds)
{
SCOPE_CYCLE_COUNTER(STAT_Navigation_RecastVoxelFilter)
ApplyVoxelFilter(RasterContext.SolidHF, TileConfig.walkableRadius);
}
// TileConfig.walkableHeight is set to 1 when marking low spans, calculate real value for filtering
const int32 FilterWalkableHeight = FMath::CeilToInt(TileConfig.AgentHeight / TileConfig.ch);
{
SCOPE_CYCLE_COUNTER(STAT_Navigation_RecastFilter)
// Once all geometry is rasterized, we do initial pass of filtering to
// remove unwanted overhangs caused by the conservative rasterization
// as well as filter spans where the character cannot possibly stand.
rcFilterLowHangingWalkableObstacles(&BuildContext, TileConfig.walkableClimb, *RasterContext.SolidHF);
rcFilterLedgeSpans(&BuildContext, TileConfig.walkableHeight, TileConfig.walkableClimb, *RasterContext.SolidHF);
if (!TileConfig.bMarkLowHeightAreas)
{
rcFilterWalkableLowHeightSpans(&BuildContext, TileConfig.walkableHeight, *RasterContext.SolidHF);
}
else if (TileConfig.bFilterLowSpanFromTileCache)
{
// TODO: investigate if creating detailed 2D map from active modifiers is cheap enough
// for now, switch on presence of those modifiers, will save memory as long as they are sparse (should be)
if (TileConfig.bFilterLowSpanSequences && bHasLowAreaModifiers)
{
rcFilterWalkableLowHeightSpansSequences(&BuildContext, FilterWalkableHeight, *RasterContext.SolidHF);
}
else
{
rcFilterWalkableLowHeightSpans(&BuildContext, FilterWalkableHeight, *RasterContext.SolidHF);
}
}
}
{
SCOPE_CYCLE_COUNTER(STAT_Navigation_RecastBuildCompactHeightField);
// Compact the heightfield so that it is faster to handle from now on.
// This will result more cache coherent data as well as the neighbors
// between walkable cells will be calculated.
RasterContext.CompactHF = rcAllocCompactHeightfield();
if (RasterContext.CompactHF == NULL)
{
BuildContext.log(RC_LOG_ERROR, "GenerateCompressedLayers: Out of memory 'CompactHF'.");
return false;
}
if (!rcBuildCompactHeightfield(&BuildContext, TileConfig.walkableHeight, TileConfig.walkableClimb, *RasterContext.SolidHF, *RasterContext.CompactHF))
{
const int SpanCount = rcGetHeightFieldSpanCount(&BuildContext, *RasterContext.SolidHF);
if (SpanCount > 0)
{
BuildContext.log(RC_LOG_ERROR, "GenerateCompressedLayers: Could not build compact data.");
}
// else there's just no spans to walk on (no spans at all or too small/sparse)
else
{
BuildContext.log(RC_LOG_WARNING, "GenerateCompressedLayers: no walkable spans - aborting");
}
return false;
}
}
{
SCOPE_CYCLE_COUNTER(STAT_Navigation_RecastErodeWalkable);
if (TileConfig.walkableRadius > RECAST_VERY_SMALL_AGENT_RADIUS)
{
uint8 FilterFlags = 0;
if (TileConfig.bFilterLowSpanSequences)
{
FilterFlags = RC_LOW_FILTER_POST_PROCESS | (TileConfig.bFilterLowSpanFromTileCache ? 0 : RC_LOW_FILTER_SEED_SPANS);
}
const bool bEroded = TileConfig.bMarkLowHeightAreas ?
rcErodeWalkableAndLowAreas(&BuildContext, TileConfig.walkableRadius, FilterWalkableHeight, RECAST_LOW_AREA, FilterFlags, *RasterContext.CompactHF) :
rcErodeWalkableArea(&BuildContext, TileConfig.walkableRadius, *RasterContext.CompactHF);
if (!bEroded)
{
BuildContext.log(RC_LOG_ERROR, "GenerateCompressedLayers: Could not erode.");
return false;
}
}
else if (TileConfig.bMarkLowHeightAreas)
{
rcMarkLowAreas(&BuildContext, FilterWalkableHeight, RECAST_LOW_AREA, *RasterContext.CompactHF);
}
}
// Build layers
{
SCOPE_CYCLE_COUNTER(STAT_Navigation_RecastBuildLayers);
RasterContext.LayerSet = rcAllocHeightfieldLayerSet();
if (RasterContext.LayerSet == NULL)
{
BuildContext.log(RC_LOG_ERROR, "GenerateCompressedLayers: Out of memory 'LayerSet'.");
return false;
}
if (TileConfig.regionPartitioning == RC_REGION_MONOTONE)
{
if (!rcBuildHeightfieldLayersMonotone(&BuildContext, *RasterContext.CompactHF, TileConfig.borderSize, TileConfig.walkableHeight, *RasterContext.LayerSet))
{
BuildContext.log(RC_LOG_ERROR, "GenerateCompressedLayers: Could not build heightfield layers.");
return 0;
}
}
else if (TileConfig.regionPartitioning == RC_REGION_WATERSHED)
{
if (!rcBuildDistanceField(&BuildContext, *RasterContext.CompactHF))
{
BuildContext.log(RC_LOG_ERROR, "GenerateCompressedLayers: Could not build distance field.");
return 0;
}
if (!rcBuildHeightfieldLayers(&BuildContext, *RasterContext.CompactHF, TileConfig.borderSize, TileConfig.walkableHeight, *RasterContext.LayerSet))
{
BuildContext.log(RC_LOG_ERROR, "GenerateCompressedLayers: Could not build heightfield layers.");
return 0;
}
}
else
{
if (!rcBuildHeightfieldLayersChunky(&BuildContext, *RasterContext.CompactHF, TileConfig.borderSize, TileConfig.walkableHeight, TileConfig.regionChunkSize, *RasterContext.LayerSet))
{
BuildContext.log(RC_LOG_ERROR, "GenerateCompressedLayers: Could not build heightfield layers.");
return 0;
}
}
}
{
SCOPE_CYCLE_COUNTER(STAT_Navigation_RecastBuildTileCache);
const int32 NumLayers = RasterContext.LayerSet->nlayers;
// use this to expand vertically layer's bounds
// this is needed to allow off-mesh connections that are not quite
// touching tile layer still connect with it.
const float StepHeights = TileConfig.AgentMaxClimb;
FTileCacheCompressor TileCompressor;
for (int32 i = 0; i < NumLayers; i++)
{
const rcHeightfieldLayer* layer = &RasterContext.LayerSet->layers[i];
// Store header
dtTileCacheLayerHeader header;
header.magic = DT_TILECACHE_MAGIC;
header.version = DT_TILECACHE_VERSION;
// Tile layer location in the navmesh.
header.tx = TileX;
header.ty = TileY;
header.tlayer = i;
dtVcopy(header.bmin, layer->bmin);
dtVcopy(header.bmax, layer->bmax);
// Tile info.
header.width = (unsigned short)layer->width;
header.height = (unsigned short)layer->height;
header.minx = (unsigned short)layer->minx;
header.maxx = (unsigned short)layer->maxx;
header.miny = (unsigned short)layer->miny;
header.maxy = (unsigned short)layer->maxy;
header.hmin = (unsigned short)layer->hmin;
header.hmax = (unsigned short)layer->hmax;
// Layer bounds in unreal coords
FBox LayerBBox = Recast2UnrealBox(header.bmin, header.bmax);
LayerBBox.Min.Z -= StepHeights;
LayerBBox.Max.Z += StepHeights;
// Compress tile layer
uint8* TileData = NULL;
int32 TileDataSize = 0;
const dtStatus status = dtBuildTileCacheLayer(&TileCompressor, &header, layer->heights, layer->areas, layer->cons, &TileData, &TileDataSize);
if (dtStatusFailed(status))
{
dtFree(TileData);
BuildContext.log(RC_LOG_ERROR, "GenerateCompressedLayers: failed to build layer.");
return false;
}
#if !UE_BUILD_SHIPPING && OUTPUT_NAV_TILE_LAYER_COMPRESSION_DATA
else
{
const int gridSize = (int)header.width * (int)header.height;
const int bufferSize = gridSize * 4;
FPlatformMisc::CustomNamedStat("NavTileLayerUncompSize", static_cast<float>(bufferSize), "NavMesh", "Bytes");
FPlatformMisc::CustomNamedStat("NavTileLayerCompSize", static_cast<float>(TileDataSize), "NavMesh", "Bytes");
}
#endif
// copy compressed data to new buffer in rasterization context
// (TileData allocates a lots of space, but only first TileDataSize bytes hold compressed data)
uint8* CompressedData = (uint8*)dtAlloc(TileDataSize * sizeof(uint8), DT_ALLOC_PERM);
if (CompressedData == NULL)
{
dtFree(TileData);
BuildContext.log(RC_LOG_ERROR, "GenerateCompressedLayers: Out of memory 'CompressedData'.");
return false;
}
FMemory::Memcpy(CompressedData, TileData, TileDataSize);
RasterContext.Layers.Add(FNavMeshTileData(CompressedData, TileDataSize, i, LayerBBox));
dtFree(TileData);
const int32 UncompressedSize = ((sizeof(dtTileCacheLayerHeader)+3) & ~3) + (3 * header.width * header.height);
const float Inv1kB = 1.0f / 1024.0f;
BuildContext.log(RC_LOG_PROGRESS, ">> Cache[%d,%d:%d] = %.2fkB (full:%.2fkB rate:%.2f%%)", TileX, TileY, i,
TileDataSize * Inv1kB, UncompressedSize * Inv1kB, 1.0f * TileDataSize / UncompressedSize);
}
}
// Transfer final data
CompressedLayers = RasterContext.Layers;
return true;
}
struct FTileGenerationContext
{
FTileGenerationContext(dtTileCacheAlloc* MyAllocator) :
Allocator(MyAllocator), Layer(0), DistanceField(0), ContourSet(0), ClusterSet(0), PolyMesh(0), DetailMesh(0)
{
}
~FTileGenerationContext()
{
ResetIntermediateData();
}
void ResetIntermediateData()
{
dtFreeTileCacheLayer(Allocator, Layer);
Layer = 0;
dtFreeTileCacheDistanceField(Allocator, DistanceField);
DistanceField = 0;
dtFreeTileCacheContourSet(Allocator, ContourSet);
ContourSet = 0;
dtFreeTileCacheClusterSet(Allocator, ClusterSet);
ClusterSet = 0;
dtFreeTileCachePolyMesh(Allocator, PolyMesh);
PolyMesh = 0;
dtFreeTileCachePolyMeshDetail(Allocator, DetailMesh);
DetailMesh = 0;
// don't clear NavigationData here!
}
struct dtTileCacheAlloc* Allocator;
struct dtTileCacheLayer* Layer;
struct dtTileCacheDistanceField* DistanceField;
struct dtTileCacheContourSet* ContourSet;
struct dtTileCacheClusterSet* ClusterSet;
struct dtTileCachePolyMesh* PolyMesh;
struct dtTileCachePolyMeshDetail* DetailMesh;
TArray<FNavMeshTileData> NavigationData;
};
bool FRecastTileGenerator::GenerateNavigationData(FNavMeshBuildContext& BuildContext)
{
SCOPE_CYCLE_COUNTER(STAT_Navigation_RecastBuildNavigation);
FTileCacheAllocator MyAllocator;
FTileCacheCompressor TileCompressor;
FTileGenerationContext GenerationContext(&MyAllocator);
GenerationContext.NavigationData.Reserve(CompressedLayers.Num());
dtStatus status = DT_SUCCESS;
for (int32 iLayer = 0; iLayer < CompressedLayers.Num(); iLayer++)
{
if (DirtyLayers[iLayer] == false || !CompressedLayers[iLayer].IsValid())
{
// skip layers not marked for rebuild
continue;
}
FNavMeshTileData& CompressedData = CompressedLayers[iLayer];
const dtTileCacheLayerHeader* TileHeader = (const dtTileCacheLayerHeader*)CompressedData.GetData();
GenerationContext.ResetIntermediateData();
// Decompress tile layer data.
status = dtDecompressTileCacheLayer(&MyAllocator, &TileCompressor, (unsigned char*)CompressedData.GetData(), CompressedData.DataSize, &GenerationContext.Layer);
if (dtStatusFailed(status))
{
BuildContext.log(RC_LOG_ERROR, "GenerateNavigationData: failed to decompress layer.");
return false;
}
// Rasterize obstacles.
MarkDynamicAreas(*GenerationContext.Layer);
{
SCOPE_CYCLE_COUNTER(STAT_Navigation_RecastBuildRegions)
// Build regions
if (TileConfig.TileCachePartitionType == RC_REGION_MONOTONE)
{
status = dtBuildTileCacheRegionsMonotone(&MyAllocator, TileConfig.minRegionArea, TileConfig.mergeRegionArea, *GenerationContext.Layer);
}
else if (TileConfig.TileCachePartitionType == RC_REGION_WATERSHED)
{
GenerationContext.DistanceField = dtAllocTileCacheDistanceField(&MyAllocator);
if (GenerationContext.DistanceField == NULL)
{
BuildContext.log(RC_LOG_ERROR, "GenerateNavigationData: Out of memory 'DistanceField'.");
return false;
}
status = dtBuildTileCacheDistanceField(&MyAllocator, *GenerationContext.Layer, *GenerationContext.DistanceField);
if (dtStatusFailed(status))
{
BuildContext.log(RC_LOG_ERROR, "GenerateNavigationData: Failed to build distance field.");
return false;
}
status = dtBuildTileCacheRegions(&MyAllocator, TileConfig.minRegionArea, TileConfig.mergeRegionArea, *GenerationContext.Layer, *GenerationContext.DistanceField);
}
else
{
status = dtBuildTileCacheRegionsChunky(&MyAllocator, TileConfig.minRegionArea, TileConfig.mergeRegionArea, *GenerationContext.Layer, TileConfig.TileCacheChunkSize);
}
if (dtStatusFailed(status))
{
BuildContext.log(RC_LOG_ERROR, "GenerateNavigationData: Failed to build regions.");
return false;
}
// skip empty layer
if (GenerationContext.Layer->regCount <= 0)
{
continue;
}
}
{
SCOPE_CYCLE_COUNTER(STAT_Navigation_RecastBuildContours);
// Build contour set
GenerationContext.ContourSet = dtAllocTileCacheContourSet(&MyAllocator);
if (GenerationContext.ContourSet == NULL)
{
BuildContext.log(RC_LOG_ERROR, "GenerateNavigationData: Out of memory 'ContourSet'.");
return false;
}
GenerationContext.ClusterSet = dtAllocTileCacheClusterSet(&MyAllocator);
if (GenerationContext.ClusterSet == NULL)
{
BuildContext.log(RC_LOG_ERROR, "GenerateNavigationData: Out of memory 'ClusterSet'.");
return false;
}
status = dtBuildTileCacheContours(&MyAllocator, *GenerationContext.Layer,
TileConfig.walkableClimb, TileConfig.maxSimplificationError, TileConfig.cs, TileConfig.ch,
*GenerationContext.ContourSet, *GenerationContext.ClusterSet);
if (dtStatusFailed(status))
{
BuildContext.log(RC_LOG_ERROR, "GenerateNavigationData: Failed to generate contour set (0x%08X).", status);
return false;
}
// skip empty layer, sometimes there are regions assigned but all flagged as empty (id=0)
if (GenerationContext.ContourSet->nconts <= 0)
{
continue;
}
}
{
SCOPE_CYCLE_COUNTER(STAT_Navigation_RecastBuildPolyMesh);
// Build poly mesh
GenerationContext.PolyMesh = dtAllocTileCachePolyMesh(&MyAllocator);
if (GenerationContext.PolyMesh == NULL)
{
BuildContext.log(RC_LOG_ERROR, "GenerateNavigationData: Out of memory 'PolyMesh'.");
return false;
}
status = dtBuildTileCachePolyMesh(&MyAllocator, &BuildContext, *GenerationContext.ContourSet, *GenerationContext.PolyMesh);
if (dtStatusFailed(status))
{
BuildContext.log(RC_LOG_ERROR, "GenerateNavigationData: Failed to generate poly mesh.");
return false;
}
status = dtBuildTileCacheClusters(&MyAllocator, *GenerationContext.ClusterSet, *GenerationContext.PolyMesh);
if (dtStatusFailed(status))
{
BuildContext.log(RC_LOG_ERROR, "GenerateNavigationData: Failed to update cluster set.");
return false;
}
}
// Build detail mesh
if (TileConfig.bGenerateDetailedMesh)
{
SCOPE_CYCLE_COUNTER(STAT_Navigation_RecastBuildPolyDetail);
// Build detail mesh.
GenerationContext.DetailMesh = dtAllocTileCachePolyMeshDetail(&MyAllocator);
if (GenerationContext.DetailMesh == NULL)
{
BuildContext.log(RC_LOG_ERROR, "GenerateNavigationData: Out of memory 'DetailMesh'.");
return false;
}
status = dtBuildTileCachePolyMeshDetail(&MyAllocator, TileConfig.cs, TileConfig.ch, TileConfig.detailSampleDist, TileConfig.detailSampleMaxError,
*GenerationContext.Layer, *GenerationContext.PolyMesh, *GenerationContext.DetailMesh);
if (dtStatusFailed(status))
{
BuildContext.log(RC_LOG_ERROR, "GenerateNavigationData: Failed to generate poly detail mesh.");
return false;
}
}
unsigned char* NavData = 0;
int32 NavDataSize = 0;
if (TileConfig.maxVertsPerPoly <= DT_VERTS_PER_POLYGON &&
GenerationContext.PolyMesh->npolys > 0 && GenerationContext.PolyMesh->nverts > 0)
{
ensure(GenerationContext.PolyMesh->npolys <= TileConfig.MaxPolysPerTile && "Polys per Tile limit exceeded!");
if (GenerationContext.PolyMesh->nverts >= 0xffff)
{
// The vertex indices are ushorts, and cannot point to more than 0xffff vertices.
BuildContext.log(RC_LOG_ERROR, "Too many vertices per tile %d (max: %d).", GenerationContext.PolyMesh->nverts, 0xffff);
return false;
}
// if we didn't fail already then it's high time we created data for off-mesh links
FOffMeshData OffMeshData;
if (OffmeshLinks.Num() > 0)
{
SCOPE_CYCLE_COUNTER(STAT_Navigation_RecastGatherOffMeshData);
OffMeshData.Reserve(OffmeshLinks.Num());
OffMeshData.AreaClassToIdMap = &AdditionalCachedData.AreaClassToIdMap;
OffMeshData.FlagsPerArea = AdditionalCachedData.FlagsPerOffMeshLinkArea;
const FSimpleLinkNavModifier* LinkModifier = OffmeshLinks.GetData();
const float DefaultSnapHeight = TileConfig.walkableClimb * TileConfig.ch;
for (int32 LinkModifierIndex = 0; LinkModifierIndex < OffmeshLinks.Num(); ++LinkModifierIndex, ++LinkModifier)
{
OffMeshData.AddLinks(LinkModifier->Links, LinkModifier->LocalToWorld, TileConfig.AgentIndex, DefaultSnapHeight);
#if GENERATE_SEGMENT_LINKS
OffMeshData.AddSegmentLinks(LinkModifier->SegmentLinks, LinkModifier->LocalToWorld, TileConfig.AgentIndex, DefaultSnapHeight);
#endif // GENERATE_SEGMENT_LINKS
}
}
// fill flags, or else detour won't be able to find polygons
// Update poly flags from areas.
for (int32 i = 0; i < GenerationContext.PolyMesh->npolys; i++)
{
GenerationContext.PolyMesh->flags[i] = AdditionalCachedData.FlagsPerArea[GenerationContext.PolyMesh->areas[i]];
}
dtNavMeshCreateParams Params;
memset(&Params, 0, sizeof(Params));
Params.verts = GenerationContext.PolyMesh->verts;
Params.vertCount = GenerationContext.PolyMesh->nverts;
Params.polys = GenerationContext.PolyMesh->polys;
Params.polyAreas = GenerationContext.PolyMesh->areas;
Params.polyFlags = GenerationContext.PolyMesh->flags;
Params.polyCount = GenerationContext.PolyMesh->npolys;
Params.nvp = GenerationContext.PolyMesh->nvp;
if (TileConfig.bGenerateDetailedMesh)
{
Params.detailMeshes = GenerationContext.DetailMesh->meshes;
Params.detailVerts = GenerationContext.DetailMesh->verts;
Params.detailVertsCount = GenerationContext.DetailMesh->nverts;
Params.detailTris = GenerationContext.DetailMesh->tris;
Params.detailTriCount = GenerationContext.DetailMesh->ntris;
}
Params.offMeshCons = OffMeshData.LinkParams.GetData();
Params.offMeshConCount = OffMeshData.LinkParams.Num();
Params.walkableHeight = TileConfig.AgentHeight;
Params.walkableRadius = TileConfig.AgentRadius;
Params.walkableClimb = TileConfig.AgentMaxClimb;
Params.tileX = TileX;
Params.tileY = TileY;
Params.tileLayer = iLayer;
rcVcopy(Params.bmin, GenerationContext.Layer->header->bmin);
rcVcopy(Params.bmax, GenerationContext.Layer->header->bmax);
Params.cs = TileConfig.cs;
Params.ch = TileConfig.ch;
Params.buildBvTree = TileConfig.bGenerateBVTree;
#if GENERATE_CLUSTER_LINKS
Params.clusterCount = GenerationContext.ClusterSet->nclusters;
Params.polyClusters = GenerationContext.ClusterSet->polyMap;
#endif
SCOPE_CYCLE_COUNTER(STAT_Navigation_RecastCreateNavMeshData);
if (!dtCreateNavMeshData(&Params, &NavData, &NavDataSize))
{
BuildContext.log(RC_LOG_ERROR, "Could not build Detour navmesh.");
return false;
}
}
GenerationContext.NavigationData.Add(FNavMeshTileData(NavData, NavDataSize, iLayer, CompressedData.LayerBBox));
const float ModkB = 1.0f / 1024.0f;
BuildContext.log(RC_LOG_PROGRESS, ">> Layer[%d] = Verts(%d) Polys(%d) Memory(%.2fkB) Cache(%.2fkB)",
iLayer, GenerationContext.PolyMesh->nverts, GenerationContext.PolyMesh->npolys,
GenerationContext.NavigationData.Last().DataSize * ModkB, CompressedLayers[iLayer].DataSize * ModkB);
}
// prepare navigation data of actually rebuild layers for transfer
NavigationData = GenerationContext.NavigationData;
return true;
}
void FRecastTileGenerator::MarkDynamicAreas(dtTileCacheLayer& Layer)
{
SCOPE_CYCLE_COUNTER(STAT_Navigation_RecastMarkAreas);
if (Modifiers.Num())
{
if (AdditionalCachedData.bUseSortFunction && AdditionalCachedData.ActorOwner && Modifiers.Num() > 1)
{
AdditionalCachedData.ActorOwner->SortAreasForGenerator(Modifiers);
}
// 1: if navmesh is using low areas, apply only low area replacements
if (TileConfig.bMarkLowHeightAreas)
{
const int32 LowAreaId = RECAST_LOW_AREA;
for (int32 ModIdx = 0; ModIdx < Modifiers.Num(); ModIdx++)
{
FRecastAreaNavModifierElement& Element = Modifiers[ModIdx];
for (int32 AreaIdx = Element.Areas.Num() - 1; AreaIdx >= 0; AreaIdx--)
{
const FAreaNavModifier& AreaMod = Element.Areas[AreaIdx];
if (AreaMod.GetApplyMode() == ENavigationAreaMode::ApplyInLowPass ||
AreaMod.GetApplyMode() == ENavigationAreaMode::ReplaceInLowPass)
{
const int32* AreaIDPtr = AdditionalCachedData.AreaClassToIdMap.Find(AreaMod.GetAreaClass());
// replace area will be fixed as LowAreaId during this pass, regardless settings in area modifier
const int32* ReplaceAreaIDPtr = (AreaMod.GetApplyMode() == ENavigationAreaMode::ReplaceInLowPass) ? &LowAreaId : nullptr;
if (AreaIDPtr != nullptr)
{
for (const FTransform& LocalToWorld : Element.PerInstanceTransform)
{
MarkDynamicArea(AreaMod, LocalToWorld, Layer, *AreaIDPtr, ReplaceAreaIDPtr);
}
if (Element.PerInstanceTransform.Num() == 0)
{
MarkDynamicArea(AreaMod, FTransform::Identity, Layer, *AreaIDPtr, ReplaceAreaIDPtr);
}
}
}
}
}
// 2. remove all low area marking
dtReplaceArea(Layer, RECAST_NULL_AREA, RECAST_LOW_AREA);
}
// 3. apply remaining modifiers
for (const FRecastAreaNavModifierElement& Element : Modifiers)
{
for (const FAreaNavModifier& Area : Element.Areas)
{
if (Area.GetApplyMode() == ENavigationAreaMode::ApplyInLowPass || Area.GetApplyMode() == ENavigationAreaMode::ReplaceInLowPass)
{
continue;
}
const int32* AreaIDPtr = AdditionalCachedData.AreaClassToIdMap.Find(Area.GetAreaClass());
const int32* ReplaceIDPtr = (Area.GetApplyMode() == ENavigationAreaMode::Replace) && Area.GetAreaClassToReplace() ?
AdditionalCachedData.AreaClassToIdMap.Find(Area.GetAreaClassToReplace()) : nullptr;
if (AreaIDPtr)
{
for (const FTransform& LocalToWorld : Element.PerInstanceTransform)
{
MarkDynamicArea(Area, LocalToWorld, Layer, *AreaIDPtr, ReplaceIDPtr);
}
if (Element.PerInstanceTransform.Num() == 0)
{
MarkDynamicArea(Area, FTransform::Identity, Layer, *AreaIDPtr, ReplaceIDPtr);
}
}
}
}
}
else
{
if (TileConfig.bMarkLowHeightAreas)
{
dtReplaceArea(Layer, RECAST_NULL_AREA, RECAST_LOW_AREA);
}
}
}
void FRecastTileGenerator::MarkDynamicArea(const FAreaNavModifier& Modifier, const FTransform& LocalToWorld, dtTileCacheLayer& Layer)
{
const int32* AreaIDPtr = AdditionalCachedData.AreaClassToIdMap.Find(Modifier.GetAreaClass());
const int32* ReplaceIDPtr = Modifier.GetAreaClassToReplace() ? AdditionalCachedData.AreaClassToIdMap.Find(Modifier.GetAreaClassToReplace()) : nullptr;
if (AreaIDPtr)
{
MarkDynamicArea(Modifier, LocalToWorld, Layer, *AreaIDPtr, ReplaceIDPtr);
}
}
void FRecastTileGenerator::MarkDynamicArea(const FAreaNavModifier& Modifier, const FTransform& LocalToWorld, dtTileCacheLayer& Layer, const int32 AreaID, const int32* ReplaceIDPtr)
{
const float ExpandBy = TileConfig.AgentRadius;
// Expand by 1 cell height up and down to cover for voxel grid inaccuracy
const float OffsetZMax = TileConfig.ch;
const float OffsetZMin = TileConfig.ch + (Modifier.ShouldIncludeAgentHeight() ? TileConfig.AgentHeight : 0.0f);
// Check whether modifier affects this layer
const FBox LayerUnrealBounds = Recast2UnrealBox(Layer.header->bmin, Layer.header->bmax);
FBox ModifierBounds = Modifier.GetBounds().TransformBy(LocalToWorld);
ModifierBounds.Min -= FVector(ExpandBy, ExpandBy, OffsetZMin);
ModifierBounds.Max += FVector(ExpandBy, ExpandBy, OffsetZMax);
if (!LayerUnrealBounds.Intersect(ModifierBounds))
{
return;
}
const float* LayerRecastOrig = Layer.header->bmin;
switch (Modifier.GetShapeType())
{
case ENavigationShapeType::Cylinder:
{
FCylinderNavAreaData CylinderData;
Modifier.GetCylinder(CylinderData);
// Only scaling and translation
FVector Scale3D = LocalToWorld.GetScale3D().GetAbs();
CylinderData.Height *= Scale3D.Z;
CylinderData.Radius *= FMath::Max(Scale3D.X, Scale3D.Y);
CylinderData.Origin = LocalToWorld.TransformPosition(CylinderData.Origin);
const float OffsetZMid = (OffsetZMax - OffsetZMin) * 0.5f;
CylinderData.Origin.Z += OffsetZMid;
CylinderData.Height += FMath::Abs(OffsetZMid) * 2.f;
CylinderData.Radius += ExpandBy;
FVector RecastPos = Unreal2RecastPoint(CylinderData.Origin);
if (ReplaceIDPtr)
{
dtReplaceCylinderArea(Layer, LayerRecastOrig, TileConfig.cs, TileConfig.ch,
&(RecastPos.X), CylinderData.Radius, CylinderData.Height, AreaID, *ReplaceIDPtr);
}
else
{
dtMarkCylinderArea(Layer, LayerRecastOrig, TileConfig.cs, TileConfig.ch,
&(RecastPos.X), CylinderData.Radius, CylinderData.Height, AreaID);
}
}
break;
case ENavigationShapeType::Box:
{
FBoxNavAreaData BoxData;
Modifier.GetBox(BoxData);
FBox WorldBox = FBox::BuildAABB(BoxData.Origin, BoxData.Extent).TransformBy(LocalToWorld);
WorldBox = WorldBox.ExpandBy(FVector(ExpandBy, ExpandBy, 0));
WorldBox.Min.Z -= OffsetZMin;
WorldBox.Max.Z += OffsetZMax;
FBox RacastBox = Unreal2RecastBox(WorldBox);
FVector RecastPos;
FVector RecastExtent;
RacastBox.GetCenterAndExtents(RecastPos, RecastExtent);
if (ReplaceIDPtr)
{
dtReplaceBoxArea(Layer, LayerRecastOrig, TileConfig.cs, TileConfig.ch,
&(RecastPos.X), &(RecastExtent.X), AreaID, *ReplaceIDPtr);
}
else
{
dtMarkBoxArea(Layer, LayerRecastOrig, TileConfig.cs, TileConfig.ch,
&(RecastPos.X), &(RecastExtent.X), AreaID);
}
}
break;
case ENavigationShapeType::Convex:
{
FConvexNavAreaData ConvexData;
Modifier.GetConvex(ConvexData);
// Only scaling and translation
PartialTransformConvexHull(ConvexData, LocalToWorld);
TArray<FVector> ConvexVerts;
GrowConvexHull(ExpandBy, ConvexData.Points, ConvexVerts);
ConvexData.MinZ -= OffsetZMin;
ConvexData.MaxZ += OffsetZMax;
if (ConvexVerts.Num())
{
TArray<float> ConvexCoords;
ConvexCoords.AddZeroed(ConvexVerts.Num() * 3);
float* ItCoord = ConvexCoords.GetData();
for (int32 i = 0; i < ConvexVerts.Num(); i++)
{
const FVector RecastV = Unreal2RecastPoint(ConvexVerts[i]);
*ItCoord = RecastV.X; ItCoord++;
*ItCoord = RecastV.Y; ItCoord++;
*ItCoord = RecastV.Z; ItCoord++;
}
if (ReplaceIDPtr)
{
dtReplaceConvexArea(Layer, LayerRecastOrig, TileConfig.cs, TileConfig.ch,
ConvexCoords.GetData(), ConvexVerts.Num(), ConvexData.MinZ, ConvexData.MaxZ, AreaID, *ReplaceIDPtr);
}
else
{
dtMarkConvexArea(Layer, LayerRecastOrig, TileConfig.cs, TileConfig.ch,
ConvexCoords.GetData(), ConvexVerts.Num(), ConvexData.MinZ, ConvexData.MaxZ, AreaID);
}
}
}
break;
default: break;
}
}
uint32 FRecastTileGenerator::GetUsedMemCount() const
{
uint32 TotalMemory = 0;
TotalMemory += InclusionBounds.GetAllocatedSize();
TotalMemory += Modifiers.GetAllocatedSize();
TotalMemory += OffmeshLinks.GetAllocatedSize();
TotalMemory += RawGeometry.GetAllocatedSize();
for (const FRecastRawGeometryElement& Element : RawGeometry)
{
TotalMemory += Element.GeomCoords.GetAllocatedSize();
TotalMemory += Element.GeomIndices.GetAllocatedSize();
TotalMemory += Element.PerInstanceTransform.GetAllocatedSize();
}
for (const FRecastAreaNavModifierElement& Element : Modifiers)
{
TotalMemory += Element.Areas.GetAllocatedSize();
TotalMemory += Element.PerInstanceTransform.GetAllocatedSize();
}
const FSimpleLinkNavModifier* SimpleLink = OffmeshLinks.GetData();
for (int32 Index = 0; Index < OffmeshLinks.Num(); ++Index, ++SimpleLink)
{
TotalMemory += SimpleLink->Links.GetAllocatedSize();
}
TotalMemory += CompressedLayers.GetAllocatedSize();
for (int32 i = 0; i < CompressedLayers.Num(); i++)
{
TotalMemory += CompressedLayers[i].DataSize;
}
TotalMemory += NavigationData.GetAllocatedSize();
for (int32 i = 0; i < NavigationData.Num(); i++)
{
TotalMemory += NavigationData[i].DataSize;
}
return TotalMemory;
}
void FRecastTileGenerator::AddReferencedObjects(FReferenceCollector& Collector)
{
for (auto& RelevantData : NavigationRelevantData)
{
UObject* Owner = RelevantData->GetOwner();
if (Owner)
{
Collector.AddReferencedObject(Owner);
}
}
}
FString FRecastTileGenerator::GetReferencerName() const
{
return TEXT("FRecastTileGenerator");
}
static int32 CaclulateMaxTilesCount(const TNavStatArray<FBox>& NavigableAreas, float TileSizeinWorldUnits, float AvgLayersPerGridCell)
{
int32 GridCellsCount = 0;
for (FBox AreaBounds : NavigableAreas)
{
// TODO: need more precise calculation, currently we don't take into account that volumes can be overlapped
FBox RCBox = Unreal2RecastBox(AreaBounds);
int32 XSize = FMath::CeilToInt(RCBox.GetSize().X/TileSizeinWorldUnits) + 1;
int32 YSize = FMath::CeilToInt(RCBox.GetSize().Z/TileSizeinWorldUnits) + 1;
GridCellsCount+= (XSize*YSize);
}
return FMath::CeilToInt(GridCellsCount * AvgLayersPerGridCell);
}
// Whether navmesh is static, does not support rebuild from geometry
static bool IsGameStaticNavMesh(ARecastNavMesh* InNavMesh)
{
return (InNavMesh->GetWorld()->IsGameWorld() && InNavMesh->GetRuntimeGenerationMode() != ERuntimeGenerationType::Dynamic);
}
//----------------------------------------------------------------------//
// FRecastNavMeshGenerator
//----------------------------------------------------------------------//
FRecastNavMeshGenerator::FRecastNavMeshGenerator(ARecastNavMesh& InDestNavMesh)
: NumActiveTiles(0)
, MaxTileGeneratorTasks(1)
, AvgLayersPerTile(8.0f)
, DestNavMesh(&InDestNavMesh)
, bInitialized(false)
, bRestrictBuildingToActiveTiles(false)
, Version(0)
{
#if TIME_SLICE_NAV_REGEN
TimeSliceDuration = 0.0025;
#endif
INC_DWORD_STAT_BY(STAT_NavigationMemory, sizeof(*this));
Init();
int32 MaxTiles = 0;
int32 MaxPolysPerTile = 0;
// recreate navmesh if no data was loaded, or when loaded data doesn't match current grid layout
bool bRecreateNavmesh = true;
if (DestNavMesh->HasValidNavmesh())
{
const bool bGameStaticNavMesh = IsGameStaticNavMesh(DestNavMesh);
const dtNavMeshParams* SavedNavParams = DestNavMesh->GetRecastNavMeshImpl()->DetourNavMesh->getParams();
if (SavedNavParams)
{
if (bGameStaticNavMesh)
{
bRecreateNavmesh = false;
MaxTiles = SavedNavParams->maxTiles;
MaxPolysPerTile = SavedNavParams->maxPolys;
}
else
{
const float TileDim = Config.tileSize * Config.cs;
if (SavedNavParams->tileHeight == TileDim && SavedNavParams->tileWidth == TileDim)
{
const FVector Orig = Recast2UnrealPoint(SavedNavParams->orig);
const FVector OrigError(FMath::Fmod(Orig.X, TileDim), FMath::Fmod(Orig.Y, TileDim), FMath::Fmod(Orig.Z, TileDim));
if (OrigError.IsNearlyZero())
{
bRecreateNavmesh = false;
}
else
{
UE_LOG(LogNavigation, Warning, TEXT("Recreating dtNavMesh instance due to saved navmesh origin (%s, usually the RecastNavMesh location) not being aligned with tile size (%d uu) ")
, *Orig.ToString(), int(TileDim));
}
}
// if new navmesh needs more tiles, force recreating
if (!bRecreateNavmesh)
{
CalcNavMeshProperties(MaxTiles, MaxPolysPerTile);
if (FMath::Log2(MaxTiles) != FMath::Log2(SavedNavParams->maxTiles))
{
bRecreateNavmesh = true;
UE_LOG(LogNavigation, Warning, TEXT("Recreating dtNavMesh instance due mismatch in number of bytes required to store serialized maxTiles (%d, %d bits) vs calculated maxtiles (%d, %d bits)")
, SavedNavParams->maxTiles, FMath::CeilToInt(FMath::Log2(SavedNavParams->maxTiles))
, MaxTiles, FMath::CeilToInt(FMath::Log2(MaxTiles)));
}
}
}
};
}
if (bRecreateNavmesh)
{
// recreate navmesh from scratch if no data was loaded
ConstructTiledNavMesh();
// mark all the areas we need to update, which is the whole (known) navigable space if not restricted to active tiles
const UNavigationSystemV1* NavSys = FNavigationSystem::GetCurrent<UNavigationSystemV1>(GetWorld());
if (NavSys)
{
bRestrictBuildingToActiveTiles = NavSys->IsActiveTilesGenerationEnabled();
}
MarkNavBoundsDirty();
}
else
{
// otherwise just update generator params
Config.MaxPolysPerTile = MaxPolysPerTile;
NumActiveTiles = GetTilesCountHelper(DestNavMesh->GetRecastNavMeshImpl()->DetourNavMesh);
}
}
FRecastNavMeshGenerator::~FRecastNavMeshGenerator()
{
DEC_DWORD_STAT_BY( STAT_NavigationMemory, sizeof(*this) );
}
void FRecastNavMeshGenerator::ConfigureBuildProperties(FRecastBuildConfig& OutConfig)
{
// @TODO those variables should be tweakable per navmesh actor
const float CellSize = DestNavMesh->CellSize;
const float CellHeight = DestNavMesh->CellHeight;
const float AgentHeight = DestNavMesh->AgentHeight;
const float MaxAgentHeight = DestNavMesh->AgentMaxHeight;
const float AgentMaxSlope = DestNavMesh->AgentMaxSlope;
const float AgentMaxClimb = DestNavMesh->AgentMaxStepHeight;
const float AgentRadius = DestNavMesh->AgentRadius;
OutConfig.Reset();
OutConfig.cs = CellSize;
OutConfig.ch = CellHeight;
OutConfig.walkableSlopeAngle = AgentMaxSlope;
OutConfig.walkableHeight = (int32)ceilf(AgentHeight / CellHeight);
OutConfig.walkableClimb = (int32)ceilf(AgentMaxClimb / CellHeight);
const float WalkableRadius = FMath::CeilToFloat(AgentRadius / CellSize);
OutConfig.walkableRadius = WalkableRadius;
// store original sizes
OutConfig.AgentHeight = AgentHeight;
OutConfig.AgentMaxClimb = AgentMaxClimb;
OutConfig.AgentRadius = AgentRadius;
OutConfig.borderSize = WalkableRadius + 3;
OutConfig.maxEdgeLen = (int32)(1200.0f / CellSize);
OutConfig.maxSimplificationError = 1.3f;
// hardcoded, but can be overridden by RecastNavMesh params later
OutConfig.minRegionArea = (int32)rcSqr(0);
OutConfig.mergeRegionArea = (int32)rcSqr(20.f);
OutConfig.maxVertsPerPoly = (int32)MAX_VERTS_PER_POLY;
OutConfig.detailSampleDist = 600.0f;
OutConfig.detailSampleMaxError = 1.0f;
OutConfig.PolyMaxHeight = (int32)ceilf(MaxAgentHeight / CellHeight);
OutConfig.minRegionArea = (int32)rcSqr(DestNavMesh->MinRegionArea / CellSize);
OutConfig.mergeRegionArea = (int32)rcSqr(DestNavMesh->MergeRegionSize / CellSize);
OutConfig.maxSimplificationError = DestNavMesh->MaxSimplificationError;
OutConfig.bPerformVoxelFiltering = DestNavMesh->bPerformVoxelFiltering;
OutConfig.bMarkLowHeightAreas = DestNavMesh->bMarkLowHeightAreas;
OutConfig.bFilterLowSpanSequences = DestNavMesh->bFilterLowSpanSequences;
OutConfig.bFilterLowSpanFromTileCache = DestNavMesh->bFilterLowSpanFromTileCache;
if (DestNavMesh->bMarkLowHeightAreas)
{
OutConfig.walkableHeight = 1;
}
const UNavigationSystemV1* NavSys = FNavigationSystem::GetCurrent<UNavigationSystemV1>(GetWorld());
OutConfig.AgentIndex = NavSys->GetSupportedAgentIndex(DestNavMesh);
OutConfig.tileSize = FMath::TruncToInt(DestNavMesh->TileSizeUU / CellSize);
OutConfig.regionChunkSize = OutConfig.tileSize / DestNavMesh->LayerChunkSplits;
OutConfig.TileCacheChunkSize = OutConfig.tileSize / DestNavMesh->RegionChunkSplits;
OutConfig.regionPartitioning = DestNavMesh->LayerPartitioning;
OutConfig.TileCachePartitionType = DestNavMesh->RegionPartitioning;
}
void FRecastNavMeshGenerator::Init()
{
check(DestNavMesh);
ConfigureBuildProperties(Config);
BBoxGrowth = FVector(2.0f * Config.borderSize * Config.cs);
RcNavMeshOrigin = Unreal2RecastPoint(DestNavMesh->NavMeshOriginOffset);
AdditionalCachedData = FRecastNavMeshCachedData::Construct(DestNavMesh);
if (Config.MaxPolysPerTile <= 0 && DestNavMesh->HasValidNavmesh())
{
const dtNavMeshParams* SavedNavParams = DestNavMesh->GetRecastNavMeshImpl()->DetourNavMesh->getParams();
if (SavedNavParams)
{
Config.MaxPolysPerTile = SavedNavParams->maxPolys;
}
}
UpdateNavigationBounds();
/** setup maximum number of active tile generator*/
const int32 NumberOfWorkerThreads = FTaskGraphInterface::Get().GetNumWorkerThreads();
MaxTileGeneratorTasks = FMath::Min(FMath::Max(NumberOfWorkerThreads * 2, 1), GetOwner() ? GetOwner()->GetMaxSimultaneousTileGenerationJobsCount() : INT_MAX);
UE_LOG(LogNavigation, Log, TEXT("Using max of %d workers to build navigation."), MaxTileGeneratorTasks);
NumActiveTiles = 0;
// prepare voxel cache if needed
if (ARecastNavMesh::IsVoxelCacheEnabled())
{
VoxelCacheContext.Create(Config.tileSize + Config.borderSize * 2, Config.cs, Config.ch);
}
bInitialized = true;
}
void FRecastNavMeshGenerator::UpdateNavigationBounds()
{
const UNavigationSystemV1* NavSys = FNavigationSystem::GetCurrent<UNavigationSystemV1>(GetWorld());
if (NavSys)
{
if (NavSys->ShouldGenerateNavigationEverywhere() == false)
{
FBox BoundsSum(ForceInit);
if (DestNavMesh)
{
TArray<FBox> SupportedBounds;
NavSys->GetNavigationBoundsForNavData(*DestNavMesh, SupportedBounds);
InclusionBounds.Reset(SupportedBounds.Num());
for (const FBox& Box : SupportedBounds)
{
InclusionBounds.Add(Box);
BoundsSum += Box;
}
}
TotalNavBounds = BoundsSum;
}
else
{
InclusionBounds.Reset(1);
TotalNavBounds = NavSys->GetWorldBounds();
if (!TotalNavBounds.IsValid)
{
InclusionBounds.Add(TotalNavBounds);
}
}
}
else
{
TotalNavBounds = FBox(ForceInit);
}
}
bool FRecastNavMeshGenerator::ConstructTiledNavMesh()
{
bool bSuccess = false;
// There is should not be any active build tasks
CancelBuild();
// create new Detour navmesh instance
dtNavMesh* DetourMesh = dtAllocNavMesh();
if (DetourMesh)
{
++Version;
dtNavMeshParams TiledMeshParameters;
FMemory::Memzero(TiledMeshParameters);
rcVcopy(TiledMeshParameters.orig, &RcNavMeshOrigin.X);
TiledMeshParameters.tileWidth = Config.tileSize * Config.cs;
TiledMeshParameters.tileHeight = Config.tileSize * Config.cs;
CalcNavMeshProperties(TiledMeshParameters.maxTiles, TiledMeshParameters.maxPolys);
Config.MaxPolysPerTile = TiledMeshParameters.maxPolys;
if (TiledMeshParameters.maxTiles == 0)
{
UE_LOG(LogNavigation, Warning, TEXT("ConstructTiledNavMesh: Failed to create navmesh of size 0."));
bSuccess = false;
}
else
{
const dtStatus status = DetourMesh->init(&TiledMeshParameters);
if (dtStatusFailed(status))
{
UE_LOG(LogNavigation, Warning, TEXT("ConstructTiledNavMesh: Could not init navmesh."));
bSuccess = false;
}
else
{
bSuccess = true;
NumActiveTiles = GetTilesCountHelper(DetourMesh);
DestNavMesh->GetRecastNavMeshImpl()->SetRecastMesh(DetourMesh);
}
}
if (bSuccess == false)
{
dtFreeNavMesh(DetourMesh);
}
}
else
{
UE_LOG(LogNavigation, Warning, TEXT("ConstructTiledNavMesh: Could not allocate navmesh.") );
bSuccess = false;
}
return bSuccess;
}
void FRecastNavMeshGenerator::CalcPolyRefBits(ARecastNavMesh* NavMeshOwner, int32& MaxTileBits, int32& MaxPolyBits)
{
static const int32 TotalBits = (sizeof(dtPolyRef) * 8);
#if USE_64BIT_ADDRESS
MaxTileBits = NavMeshOwner ? FMath::CeilToFloat(FMath::Log2(NavMeshOwner->GetTileNumberHardLimit())) : 20;
MaxPolyBits = FMath::Min<int32>(32, (TotalBits - DT_MIN_SALT_BITS) - MaxTileBits);
#else
MaxTileBits = 14;
MaxPolyBits = (TotalBits - DT_MIN_SALT_BITS) - MaxTileBits;
#endif//USE_64BIT_ADDRESS
}
void FRecastNavMeshGenerator::CalcNavMeshProperties(int32& MaxTiles, int32& MaxPolys)
{
int32 MaxTileBits = -1;
int32 MaxPolyBits = -1;
// limit max amount of tiles
CalcPolyRefBits(DestNavMesh, MaxTileBits, MaxPolyBits);
const int32 MaxTilesFromMask = (1 << MaxTileBits);
int32 MaxRequestedTiles = 0;
if (DestNavMesh->IsResizable())
{
MaxRequestedTiles = CaclulateMaxTilesCount(InclusionBounds, Config.tileSize * Config.cs, AvgLayersPerTile);
}
else
{
MaxRequestedTiles = DestNavMesh->TilePoolSize;
}
if (MaxRequestedTiles < 0 || MaxRequestedTiles > MaxTilesFromMask)
{
UE_LOG(LogNavigation, Error, TEXT("Navmesh bounds are too large! Limiting requested tiles count (%d) to: (%d)"), MaxRequestedTiles, MaxTilesFromMask);
MaxRequestedTiles = MaxTilesFromMask;
}
// Max tiles and max polys affect how the tile IDs are calculated.
// There are (sizeof(dtPolyRef)*8 - DT_MIN_SALT_BITS) bits available for
// identifying a tile and a polygon.
#if USE_64BIT_ADDRESS
MaxPolys = (MaxPolyBits >= 32) ? INT_MAX : (1 << MaxPolyBits);
#else
MaxPolys = 1 << ((sizeof(dtPolyRef) * 8 - DT_MIN_SALT_BITS) - MaxTileBits);
#endif // USE_64BIT_ADDRESS
MaxTiles = MaxRequestedTiles;
}
bool FRecastNavMeshGenerator::RebuildAll()
{
DestNavMesh->UpdateNavVersion();
// Recreate recast navmesh
DestNavMesh->GetRecastNavMeshImpl()->ReleaseDetourNavMesh();
RcNavMeshOrigin = Unreal2RecastPoint(DestNavMesh->NavMeshOriginOffset);
ConstructTiledNavMesh();
if (MarkNavBoundsDirty() == false)
{
// There are no navigation bounds to build, probably navmesh was resized and we just need to update debug draw
DestNavMesh->RequestDrawingUpdate();
}
return true;
}
void FRecastNavMeshGenerator::EnsureBuildCompletion()
{
const bool bHadTasks = GetNumRemaningBuildTasks() > 0;
const bool bDoAsyncDataGathering = (GatherGeometryOnGameThread() == false);
do
{
const int32 NumTasksToProcess = (bDoAsyncDataGathering ? 1 : MaxTileGeneratorTasks) - RunningDirtyTiles.Num();
ProcessTileTasks(NumTasksToProcess);
// Block until tasks are finished
for (FRunningTileElement& Element : RunningDirtyTiles)
{
Element.AsyncTask->EnsureCompletion();
}
}
while (GetNumRemaningBuildTasks() > 0);
// Update navmesh drawing only if we had something to build
if (bHadTasks)
{
DestNavMesh->RequestDrawingUpdate();
}
}
void FRecastNavMeshGenerator::CancelBuild()
{
DiscardCurrentBuildingTasks();
#if WITH_EDITOR
RecentlyBuiltTiles.Empty();
#endif//WITH_EDITOR
}
void FRecastNavMeshGenerator::TickAsyncBuild(float DeltaSeconds)
{
bool bRequestDrawingUpdate = false;
#if WITH_EDITOR
// Remove expired tiles
{
const double Timestamp = FPlatformTime::Seconds();
const int32 NumPreRemove = RecentlyBuiltTiles.Num();
RecentlyBuiltTiles.RemoveAllSwap([&](const FTileTimestamp& Tile) { return (Timestamp - Tile.Timestamp) > 0.5; });
const int32 NumPostRemove = RecentlyBuiltTiles.Num();
bRequestDrawingUpdate = (NumPreRemove != NumPostRemove);
}
#endif//WITH_EDITOR
// Submit async tile build tasks in case we have dirty tiles and have room for them
const UNavigationSystemV1* NavSys = FNavigationSystem::GetCurrent<UNavigationSystemV1>(GetWorld());
check(NavSys);
const int32 NumRunningTasks = NavSys->GetNumRunningBuildTasks();
// this is a temp solution to enforce only one worker thread if GatherGeometryOnGameThread == false
// due to missing safety features
const bool bDoAsyncDataGathering = GatherGeometryOnGameThread() == false;
const int32 NumTasksToSubmit = (bDoAsyncDataGathering ? 1 : MaxTileGeneratorTasks) - NumRunningTasks;
TArray<uint32> UpdatedTileIndices = ProcessTileTasks(NumTasksToSubmit);
if (UpdatedTileIndices.Num() > 0)
{
// Invalidate active paths that go through regenerated tiles
DestNavMesh->OnNavMeshTilesUpdated(UpdatedTileIndices);
bRequestDrawingUpdate = true;
#if WITH_EDITOR
// Store completed tiles with timestamps to have ability to distinguish during debug draw
const double Timestamp = FPlatformTime::Seconds();
RecentlyBuiltTiles.Reserve(RecentlyBuiltTiles.Num() + UpdatedTileIndices.Num());
for (uint32 TiledIdx : UpdatedTileIndices)
{
FTileTimestamp TileTimestamp;
TileTimestamp.TileIdx = TiledIdx;
TileTimestamp.Timestamp = Timestamp;
RecentlyBuiltTiles.Add(TileTimestamp);
}
#endif//WITH_EDITOR
}
if (bRequestDrawingUpdate)
{
DestNavMesh->RequestDrawingUpdate();
}
}
void FRecastNavMeshGenerator::OnNavigationBoundsChanged()
{
UpdateNavigationBounds();
dtNavMesh* DetourMesh = DestNavMesh->GetRecastNavMeshImpl()->GetRecastMesh();
if (!IsGameStaticNavMesh(DestNavMesh) && DestNavMesh->IsResizable() && DetourMesh)
{
// Check whether Navmesh size needs to be changed
int32 MaxRequestedTiles = CaclulateMaxTilesCount(InclusionBounds, Config.tileSize * Config.cs, AvgLayersPerTile);
if (DetourMesh->getMaxTiles() != MaxRequestedTiles)
{
// Destroy current NavMesh
DestNavMesh->GetRecastNavMeshImpl()->SetRecastMesh(nullptr);
// if there are any valid bounds recreate detour navmesh instance
// and mark all bounds as dirty
if (InclusionBounds.Num() > 0)
{
TArray<FNavigationDirtyArea> AsDirtyAreas;
AsDirtyAreas.Reserve(InclusionBounds.Num());
for (const FBox& BBox : InclusionBounds)
{
AsDirtyAreas.Add(FNavigationDirtyArea(BBox, ENavigationDirtyFlag::NavigationBounds));
}
RebuildDirtyAreas(AsDirtyAreas);
}
}
}
}
void FRecastNavMeshGenerator::RebuildDirtyAreas(const TArray<FNavigationDirtyArea>& InDirtyAreas)
{
dtNavMesh* DetourMesh = DestNavMesh->GetRecastNavMeshImpl()->GetRecastMesh();
if (DetourMesh == nullptr)
{
ConstructTiledNavMesh();
}
MarkDirtyTiles(InDirtyAreas);
}
void FRecastNavMeshGenerator::OnAreaAdded(const UClass* AreaClass, int32 AreaID)
{
AdditionalCachedData.OnAreaAdded(AreaClass, AreaID);
}
int32 FRecastNavMeshGenerator::FindInclusionBoundEncapsulatingBox(const FBox& Box) const
{
for (int32 Index = 0; Index < InclusionBounds.Num(); ++Index)
{
if (DoesBoxContainBox(InclusionBounds[Index], Box))
{
return Index;
}
}
return INDEX_NONE;
}
void FRecastNavMeshGenerator::RestrictBuildingToActiveTiles(bool InRestrictBuildingToActiveTiles)
{
if (bRestrictBuildingToActiveTiles != InRestrictBuildingToActiveTiles)
{
bRestrictBuildingToActiveTiles = InRestrictBuildingToActiveTiles;
if (InRestrictBuildingToActiveTiles)
{
// gather non-empty tiles and add them to ActiveTiles
const dtNavMesh* DetourMesh = DestNavMesh->GetRecastNavMeshImpl()->GetRecastMesh();
if (DetourMesh != nullptr && DetourMesh->isEmpty() == false)
{
ActiveTiles.Reset();
int32 TileCount = DetourMesh->getMaxTiles();
for (int32 TileIndex = 0; TileIndex < TileCount; ++TileIndex)
{
const dtMeshTile* Tile = DetourMesh->getTile(TileIndex);
if (Tile != nullptr && Tile->header != nullptr && Tile->header->polyCount > 0)
{
ActiveTiles.AddUnique(FIntPoint(Tile->header->x, Tile->header->y));
}
}
}
}
}
}
bool FRecastNavMeshGenerator::IsInActiveSet(const FIntPoint& Tile) const
{
// @TODO checking if given tile is in active tiles needs to be faster
return bRestrictBuildingToActiveTiles == false || ActiveTiles.Find(Tile) != INDEX_NONE;
}
//@TODO Investigate removing from RunningDirtyTiles here too (or atleast not using the results in any way)
void FRecastNavMeshGenerator::RemoveTiles(const TArray<FIntPoint>& Tiles)
{
for (const FIntPoint& TileXY : Tiles)
{
RemoveTileLayers(TileXY.X, TileXY.Y);
if (PendingDirtyTiles.Num() > 0)
{
FPendingTileElement DirtyTile;
DirtyTile.Coord = TileXY;
PendingDirtyTiles.Remove(DirtyTile);
}
#if TIME_SLICE_NAV_REGEN
if (TileGeneratorSync.Get())
{
if (TileGeneratorSync->GetTileX() == TileXY.X && TileGeneratorSync->GetTileY() == TileXY.Y)
{
TileGeneratorSync.Reset();
}
}
#endif
}
}
void FRecastNavMeshGenerator::ReAddTiles(const TArray<FIntPoint>& Tiles)
{
static const FVector Expansion(1, 1, BIG_NUMBER);
// a little trick here - adding a dirty area so that navmesh building figures it out on its own
dtNavMesh* DetourMesh = DestNavMesh->GetRecastNavMeshImpl()->GetRecastMesh();
const dtNavMeshParams* SavedNavParams = DestNavMesh->GetRecastNavMeshImpl()->DetourNavMesh->getParams();
const float TileDim = Config.tileSize * Config.cs;
TSet<FPendingTileElement> DirtyTiles;
// @note we act on assumption all items in Tiles are unique
for (const FIntPoint& TileCoords : Tiles)
{
FPendingTileElement Element;
Element.Coord = TileCoords;
Element.bRebuildGeometry = true;
DirtyTiles.Add(Element);
}
int32 NumTilesMarked = DirtyTiles.Num();
// Merge all pending tiles into one container
for (const FPendingTileElement& Element : PendingDirtyTiles)
{
FPendingTileElement* ExistingElement = DirtyTiles.Find(Element);
if (ExistingElement)
{
ExistingElement->bRebuildGeometry |= Element.bRebuildGeometry;
// Append area bounds to existing list
if (ExistingElement->bRebuildGeometry == false)
{
ExistingElement->DirtyAreas.Append(Element.DirtyAreas);
}
else
{
ExistingElement->DirtyAreas.Empty();
}
}
else
{
DirtyTiles.Add(Element);
}
}
// Dump results into array
PendingDirtyTiles.Empty(DirtyTiles.Num());
for (const FPendingTileElement& Element : DirtyTiles)
{
PendingDirtyTiles.Add(Element);
}
// Sort tiles by proximity to players
if (NumTilesMarked > 0)
{
SortPendingBuildTiles();
}
/*TArray<FNavigationDirtyArea> DirtyAreasContainer;
DirtyAreasContainer.Reserve(Tiles.Num());
TSet<FPendingTileElement> DirtyTiles;
for (const FIntPoint& TileCoords : Tiles)
{
const FVector TileCenter = Recast2UnrealPoint(SavedNavParams->orig) + FVector(TileDim * float(TileCoords.X), TileDim * float(TileCoords.Y), 0);
FNavigationDirtyArea DirtyArea(FBox(TileCenter - Expansion, TileCenter - 1), ENavigationDirtyFlag::All);
DirtyAreasContainer.Add(DirtyArea);
}
MarkDirtyTiles(DirtyAreasContainer);*/
}
namespace RecastTileVersionHelper
{
inline uint32 GetUpdatedTileId(dtPolyRef& TileRef, dtNavMesh* DetourMesh)
{
uint32 DecodedTileId = 0, DecodedPolyId = 0, DecodedSaltId = 0;
DetourMesh->decodePolyId(TileRef, DecodedSaltId, DecodedTileId, DecodedPolyId);
DecodedSaltId = (DecodedSaltId + 1) & ((1 << DetourMesh->getSaltBits()) - 1);
if (DecodedSaltId == 0)
{
DecodedSaltId++;
}
TileRef = DetourMesh->encodePolyId(DecodedSaltId, DecodedTileId, DecodedPolyId);
return DecodedTileId;
}
}
TArray<uint32> FRecastNavMeshGenerator::RemoveTileLayers(const int32 TileX, const int32 TileY, TMap<int32, dtPolyRef>* OldLayerTileIdMap)
{
dtNavMesh* DetourMesh = DestNavMesh->GetRecastNavMeshImpl()->GetRecastMesh();
TArray<uint32> UpdatedIndices;
if (DetourMesh != nullptr && DetourMesh->isEmpty() == false)
{
const int32 NumLayers = DetourMesh->getTileCountAt(TileX, TileY);
if (NumLayers > 0)
{
TArray<dtMeshTile*> Tiles;
Tiles.AddZeroed(NumLayers);
DetourMesh->getTilesAt(TileX, TileY, (const dtMeshTile**)Tiles.GetData(), NumLayers);
for (int32 i = 0; i < NumLayers; i++)
{
const int32 LayerIndex = Tiles[i]->header->layer;
dtPolyRef TileRef = DetourMesh->getTileRef(Tiles[i]);
NumActiveTiles--;
UE_LOG(LogNavigation, Log, TEXT("%s> Tile (%d,%d:%d), removing TileRef: 0x%X (active:%d)"),
*DestNavMesh->GetName(), TileX, TileY, LayerIndex, TileRef, NumActiveTiles);
DetourMesh->removeTile(TileRef, nullptr, nullptr);
uint32 TileId = RecastTileVersionHelper::GetUpdatedTileId(TileRef, DetourMesh);
UpdatedIndices.AddUnique(TileId);
if (OldLayerTileIdMap)
{
OldLayerTileIdMap->Add(LayerIndex, TileRef);
}
}
}
// Remove compressed tile cache layers
DestNavMesh->RemoveTileCacheLayers(TileX, TileY);
}
return UpdatedIndices;
}
TArray<uint32> FRecastNavMeshGenerator::AddGeneratedTiles(FRecastTileGenerator& TileGenerator)
{
SCOPE_CYCLE_COUNTER(STAT_Navigation_RecastAddGeneratedTiles);
TMap<int32, dtPolyRef> OldLayerTileIdMap;
TArray<uint32> ResultTileIndices;
const int32 TileX = TileGenerator.GetTileX();
const int32 TileY = TileGenerator.GetTileY();
if (TileGenerator.IsFullyRegenerated())
{
// remove all layers
ResultTileIndices = RemoveTileLayers(TileX, TileY, &OldLayerTileIdMap);
}
dtNavMesh* DetourMesh = DestNavMesh->GetRecastNavMeshImpl()->GetRecastMesh();
const int32 FirstDirtyTileIndex = TileGenerator.GetDirtyLayersMask().Find(true);
if (DetourMesh != nullptr
// no longer testing this here, we can live with a stray unwanted tile here
// and there. It will be removed the next time around the invokers get
// updated
// && IsInActiveSet(FIntPoint(TileX, TileY))
&& FirstDirtyTileIndex != INDEX_NONE)
{
TArray<FNavMeshTileData> TileLayers = TileGenerator.GetNavigationData();
ResultTileIndices.Reserve(TileLayers.Num());
struct FLayerIndexFinder
{
int32 LayerIndex;
explicit FLayerIndexFinder(const int32 InLayerIndex) : LayerIndex(InLayerIndex) {}
bool operator()(const FNavMeshTileData& LayerData) const
{
return LayerData.LayerIndex == LayerIndex;
}
};
for (int32 LayerIndex = FirstDirtyTileIndex; LayerIndex < TileGenerator.GetDirtyLayersMask().Num(); ++LayerIndex)
{
if (TileGenerator.IsLayerChanged(LayerIndex))
{
dtTileRef OldTileRef = DetourMesh->getTileRefAt(TileX, TileY, LayerIndex);
const int32 LayerDataIndex = TileLayers.IndexOfByPredicate(FLayerIndexFinder(LayerIndex));
if (LayerDataIndex != INDEX_NONE)
{
FNavMeshTileData& LayerData = TileLayers[LayerDataIndex];
if (OldTileRef)
{
QUICK_SCOPE_CYCLE_COUNTER(STAT_NavMesh_RemoveOldTIle);
NumActiveTiles--;
UE_LOG(LogNavigation, Log, TEXT("%s> Tile (%d,%d:%d), removing TileRef: 0x%X (active:%d)"),
*DestNavMesh->GetName(), TileX, TileY, LayerIndex, OldTileRef, NumActiveTiles);
DetourMesh->removeTile(OldTileRef, nullptr, nullptr);
const uint32 TileId = RecastTileVersionHelper::GetUpdatedTileId(OldTileRef, DetourMesh);
ResultTileIndices.AddUnique(TileId);
}
else
{
OldTileRef = OldLayerTileIdMap.FindRef(LayerIndex);
}
if (LayerData.IsValid())
{
bool bRejectNavmesh = false;
dtTileRef ResultTileRef = 0;
dtStatus status = 0;
{
QUICK_SCOPE_CYCLE_COUNTER(STAT_NavMesh_AddTileToDetourMesh);
// let navmesh know it's tile generator who owns the data
status = DetourMesh->addTile(LayerData.GetData(), LayerData.DataSize, DT_TILE_FREE_DATA, OldTileRef, &ResultTileRef);
// if tile index was already taken by other layer try adding it on first free entry (salt was already updated by whatever took that spot)
if (dtStatusFailed(status) && dtStatusDetail(status, DT_OUT_OF_MEMORY) && OldTileRef)
{
OldTileRef = 0;
status = DetourMesh->addTile(LayerData.GetData(), LayerData.DataSize, DT_TILE_FREE_DATA, OldTileRef, &ResultTileRef);
}
}
if (dtStatusFailed(status))
{
if (dtStatusDetail(status, DT_OUT_OF_MEMORY))
{
UE_LOG(LogNavigation, Error, TEXT("%s> Tile (%d,%d:%d), tile limit reached!! (%d)"),
*DestNavMesh->GetName(), TileX, TileY, LayerIndex, DetourMesh->getMaxTiles());
}
}
else
{
ResultTileIndices.AddUnique(DetourMesh->decodePolyIdTile(ResultTileRef));
NumActiveTiles++;
UE_LOG(LogNavigation, Log, TEXT("%s> Tile (%d,%d:%d), added TileRef: 0x%X (active:%d)"),
*DestNavMesh->GetName(), TileX, TileY, LayerIndex, ResultTileRef, NumActiveTiles);
{
QUICK_SCOPE_CYCLE_COUNTER(STAT_NavMesh_ReleaseTileLayers);
// NavMesh took the ownership of generated data, so we don't need to deallocate it
uint8* ReleasedData = LayerData.Release();
}
}
}
}
else
{
// remove the layer since it ended up empty
DetourMesh->removeTile(OldTileRef, nullptr, nullptr);
const uint32 TileId = RecastTileVersionHelper::GetUpdatedTileId(OldTileRef, DetourMesh);
ResultTileIndices.AddUnique(TileId);
}
}
}
}
return ResultTileIndices;
}
void FRecastNavMeshGenerator::DiscardCurrentBuildingTasks()
{
PendingDirtyTiles.Empty();
for (FRunningTileElement& Element : RunningDirtyTiles)
{
if (Element.AsyncTask)
{
Element.AsyncTask->EnsureCompletion();
delete Element.AsyncTask;
Element.AsyncTask = nullptr;
}
}
#if TIME_SLICE_NAV_REGEN
TileGeneratorSync.Reset();
#endif
RunningDirtyTiles.Empty();
}
bool FRecastNavMeshGenerator::HasDirtyTiles() const
{
return (PendingDirtyTiles.Num() > 0
|| RunningDirtyTiles.Num() > 0
#if TIME_SLICE_NAV_REGEN
|| TileGeneratorSync.Get() != nullptr
#endif
);
}
FBox FRecastNavMeshGenerator::GrowBoundingBox(const FBox& BBox, bool bIncludeAgentHeight) const
{
const FVector BBoxGrowOffsetMin = FVector(0, 0, bIncludeAgentHeight ? Config.AgentHeight : 0.0f);
return FBox(BBox.Min - BBoxGrowth - BBoxGrowOffsetMin, BBox.Max + BBoxGrowth);
}
static bool IntersectBounds(const FBox& TestBox, const TNavStatArray<FBox>& Bounds)
{
for (const FBox& Box : Bounds)
{
if (Box.Intersect(TestBox))
{
return true;
}
}
return false;
}
namespace
{
FBox CalculateBoxIntersection(const FBox& BoxA, const FBox& BoxB)
{
// assumes boxes overlap
ensure(BoxA.Intersect(BoxB));
return FBox(FVector(FMath::Max(BoxA.Min.X, BoxB.Min.X)
, FMath::Max(BoxA.Min.Y, BoxB.Min.Y)
, FMath::Max(BoxA.Min.Z, BoxB.Min.Z))
, FVector(FMath::Min(BoxA.Max.X, BoxB.Max.X)
, FMath::Min(BoxA.Max.Y, BoxB.Max.Y)
, FMath::Min(BoxA.Max.Z, BoxB.Max.Z))
);
}
}
bool FRecastNavMeshGenerator::HasDirtyTiles(const FBox& AreaBounds) const
{
if (HasDirtyTiles() == false)
{
return false;
}
bool bRetDirty = false;
const float TileSizeInWorldUnits = Config.tileSize * Config.cs;
const FRcTileBox TileBox(AreaBounds, RcNavMeshOrigin, TileSizeInWorldUnits);
for (int32 Index = 0; bRetDirty == false && Index < PendingDirtyTiles.Num(); ++Index)
{
bRetDirty = TileBox.Contains(PendingDirtyTiles[Index].Coord);
}
for (int32 Index = 0; bRetDirty == false && Index < RunningDirtyTiles.Num(); ++Index)
{
bRetDirty = TileBox.Contains(RunningDirtyTiles[Index].Coord);
}
return bRetDirty;
}
int32 FRecastNavMeshGenerator::GetDirtyTilesCount(const FBox& AreaBounds) const
{
const float TileSizeInWorldUnits = Config.tileSize * Config.cs;
const FRcTileBox TileBox(AreaBounds, RcNavMeshOrigin, TileSizeInWorldUnits);
int32 DirtyPendingCount = 0;
for (const FPendingTileElement& PendingElement : PendingDirtyTiles)
{
DirtyPendingCount += TileBox.Contains(PendingElement.Coord) ? 1 : 0;
}
int32 RunningCount = 0;
for (const FRunningTileElement& RunningElement : RunningDirtyTiles)
{
RunningCount += TileBox.Contains(RunningElement.Coord) ? 1 : 0;
}
return DirtyPendingCount + RunningCount;
}
bool FRecastNavMeshGenerator::MarkNavBoundsDirty()
{
// if rebuilding all no point in keeping "old" invalidated areas
TArray<FNavigationDirtyArea> DirtyAreas;
for (FBox AreaBounds : InclusionBounds)
{
FNavigationDirtyArea DirtyArea(AreaBounds, ENavigationDirtyFlag::All | ENavigationDirtyFlag::NavigationBounds);
DirtyAreas.Add(DirtyArea);
}
if (DirtyAreas.Num())
{
MarkDirtyTiles(DirtyAreas);
return true;
}
return false;
}
void FRecastNavMeshGenerator::MarkDirtyTiles(const TArray<FNavigationDirtyArea>& DirtyAreas)
{
QUICK_SCOPE_CYCLE_COUNTER(STAT_RecastNavMeshGenerator_MarkDirtyTiles);
check(bInitialized);
const float TileSizeInWorldUnits = Config.tileSize * Config.cs;
check(TileSizeInWorldUnits > 0);
const bool bGameStaticNavMesh = IsGameStaticNavMesh(DestNavMesh);
// find all tiles that need regeneration
TSet<FPendingTileElement> DirtyTiles;
for (const FNavigationDirtyArea& DirtyArea : DirtyAreas)
{
// Static navmeshes accept only area modifiers updates
if (bGameStaticNavMesh && (!DirtyArea.HasFlag(ENavigationDirtyFlag::DynamicModifier) || DirtyArea.HasFlag(ENavigationDirtyFlag::NavigationBounds)))
{
continue;
}
bool bDoTileInclusionTest = false;
FBox AdjustedAreaBounds = DirtyArea.Bounds;
// if it's not expanding the navigatble area
if (DirtyArea.HasFlag(ENavigationDirtyFlag::NavigationBounds) == false)
{
// and is outside of current bounds
if (GetTotalBounds().Intersect(DirtyArea.Bounds) == false)
{
// skip it
continue;
}
const FBox CutDownArea = CalculateBoxIntersection(GetTotalBounds(), DirtyArea.Bounds);
AdjustedAreaBounds = GrowBoundingBox(CutDownArea, DirtyArea.HasFlag(ENavigationDirtyFlag::UseAgentHeight));
// @TODO this and the following test share some work in common
if (IntersectBounds(AdjustedAreaBounds, InclusionBounds) == false)
{
continue;
}
// check if any of inclusion volumes encapsulates this box
// using CutDownArea not AdjustedAreaBounds since if the area is on the border of navigable space
// then FindInclusionBoundEncapsulatingBox can produce false negative
bDoTileInclusionTest = (FindInclusionBoundEncapsulatingBox(CutDownArea) == INDEX_NONE);
}
const FRcTileBox TileBox(AdjustedAreaBounds, RcNavMeshOrigin, TileSizeInWorldUnits);
for (int32 TileY = TileBox.YMin; TileY <= TileBox.YMax; ++TileY)
{
for (int32 TileX = TileBox.XMin; TileX <= TileBox.XMax; ++TileX)
{
if (IsInActiveSet(FIntPoint(TileX, TileY)) == false)
{
continue;
}
if (bDoTileInclusionTest == true && DirtyArea.HasFlag(ENavigationDirtyFlag::NavigationBounds) == false)
{
const FBox TileBounds = CalculateTileBounds(TileX, TileY, RcNavMeshOrigin, TotalNavBounds, TileSizeInWorldUnits);
// do per tile check since we can have lots of tiles inbetween navigable bounds volumes
if (IntersectBounds(TileBounds, InclusionBounds) == false)
{
// Skip this tile
continue;
}
}
FPendingTileElement Element;
Element.Coord = FIntPoint(TileX, TileY);
Element.bRebuildGeometry = DirtyArea.HasFlag(ENavigationDirtyFlag::Geometry) || DirtyArea.HasFlag(ENavigationDirtyFlag::NavigationBounds);
if (Element.bRebuildGeometry == false)
{
Element.DirtyAreas.Add(AdjustedAreaBounds);
}
FPendingTileElement* ExistingElement = DirtyTiles.Find(Element);
if (ExistingElement)
{
ExistingElement->bRebuildGeometry|= Element.bRebuildGeometry;
// Append area bounds to existing list
if (ExistingElement->bRebuildGeometry == false)
{
ExistingElement->DirtyAreas.Append(Element.DirtyAreas);
}
else
{
ExistingElement->DirtyAreas.Empty();
}
}
else
{
DirtyTiles.Add(Element);
}
}
}
}
int32 NumTilesMarked = DirtyTiles.Num();
// Merge all pending tiles into one container
for (const FPendingTileElement& Element : PendingDirtyTiles)
{
FPendingTileElement* ExistingElement = DirtyTiles.Find(Element);
if (ExistingElement)
{
ExistingElement->bRebuildGeometry|= Element.bRebuildGeometry;
// Append area bounds to existing list
if (ExistingElement->bRebuildGeometry == false)
{
ExistingElement->DirtyAreas.Append(Element.DirtyAreas);
}
else
{
ExistingElement->DirtyAreas.Empty();
}
}
else
{
DirtyTiles.Add(Element);
}
}
// Dump results into array
PendingDirtyTiles.Empty(DirtyTiles.Num());
for(const FPendingTileElement& Element : DirtyTiles)
{
PendingDirtyTiles.Add(Element);
}
// Sort tiles by proximity to players
if (NumTilesMarked > 0)
{
SortPendingBuildTiles();
}
}
void FRecastNavMeshGenerator::SortPendingBuildTiles()
{
TArray<FVector2D> SeedLocations;
UWorld* CurWorld = GetWorld();
if (CurWorld == nullptr)
{
return;
}
// Collect players positions
for (FConstPlayerControllerIterator PlayerIt = CurWorld->GetPlayerControllerIterator(); PlayerIt; ++PlayerIt)
{
APlayerController* PC = PlayerIt->Get();
if (PC && PC->GetPawn() != NULL)
{
const FVector2D SeedLoc(PC->GetPawn()->GetActorLocation());
SeedLocations.Add(SeedLoc);
}
}
if (SeedLocations.Num() == 0)
{
// Use navmesh origin for sorting
SeedLocations.Add(FVector2D::ZeroVector);
}
if (SeedLocations.Num() > 0)
{
const float TileSizeInWorldUnits = Config.tileSize * Config.cs;
// Calculate shortest distances between tiles and players
for (FPendingTileElement& Element : PendingDirtyTiles)
{
const FBox TileBox = CalculateTileBounds(Element.Coord.X, Element.Coord.Y, FVector::ZeroVector, TotalNavBounds, TileSizeInWorldUnits);
FVector2D TileCenter2D = FVector2D(TileBox.GetCenter());
for (FVector2D SeedLocation : SeedLocations)
{
const float DistSq = FVector2D::DistSquared(TileCenter2D, SeedLocation);
if (DistSq < Element.SeedDistance)
{
Element.SeedDistance = DistSq;
}
}
}
// nearest tiles should be at the end of the list
PendingDirtyTiles.Sort();
}
}
TSharedRef<FRecastTileGenerator> FRecastNavMeshGenerator::CreateTileGenerator(const FIntPoint& Coord, const TArray<FBox>& DirtyAreas)
{
TSharedRef<FRecastTileGenerator> TileGenerator = MakeShareable(new FRecastTileGenerator(*this, Coord));
TileGenerator->Setup(*this, DirtyAreas);
return TileGenerator;
}
void FRecastNavMeshGenerator::RemoveLayers(const FIntPoint& Tile, TArray<uint32>& UpdatedTiles)
{
// If there is nothing to generate remove all tiles from navmesh at specified grid coordinates
UpdatedTiles.Append(
RemoveTileLayers(Tile.X, Tile.Y)
);
DestNavMesh->MarkEmptyTileCacheLayers(Tile.X, Tile.Y);
}
#if RECAST_ASYNC_REBUILDING
TArray<uint32> FRecastNavMeshGenerator::ProcessTileTasksAsync(const int32 NumTasksToProcess)
{
QUICK_SCOPE_CYCLE_COUNTER(STAT_RecastNavMeshGenerator_ProcessTileTasksAsync);
TArray<uint32> UpdatedTiles;
const bool bGameStaticNavMesh = IsGameStaticNavMesh(DestNavMesh);
int32 NumProcessedTasks = 0;
// Submit pending tile elements
for (int32 ElementIdx = PendingDirtyTiles.Num()-1; ElementIdx >= 0 && NumProcessedTasks < NumTasksToProcess; ElementIdx--)
{
QUICK_SCOPE_CYCLE_COUNTER(STAT_RecastNavMeshGenerator_ProcessTileTasks_NewTasks);
FPendingTileElement& PendingElement = PendingDirtyTiles[ElementIdx];
FRunningTileElement RunningElement(PendingElement.Coord);
// Make sure that we are not submitting generator for grid cell that is currently being regenerated
if (!RunningDirtyTiles.Contains(RunningElement))
{
// Spawn async task
TUniquePtr<FRecastTileGeneratorTask> TileTask = MakeUnique<FRecastTileGeneratorTask>(CreateTileGenerator(PendingElement.Coord, PendingElement.DirtyAreas));
// Start it in background in case it has something to build
if (TileTask->GetTask().TileGenerator->HasDataToBuild())
{
RunningElement.AsyncTask = TileTask.Release();
RunningElement.AsyncTask->StartBackgroundTask();
RunningDirtyTiles.Add(RunningElement);
}
else if (!bGameStaticNavMesh)
{
RemoveLayers(PendingElement.Coord, UpdatedTiles);
}
// Remove submitted element from pending list
PendingDirtyTiles.RemoveAt(ElementIdx, 1, /*bAllowShrinking=*/false);
NumProcessedTasks++;
}
}
// Release memory, list could be quite big after map load
if (NumProcessedTasks > 0 && PendingDirtyTiles.Num() == 0)
{
PendingDirtyTiles.Empty(32);
}
// Collect completed tasks and apply generated data to navmesh
for (int32 Idx = RunningDirtyTiles.Num() - 1; Idx >=0; --Idx)
{
QUICK_SCOPE_CYCLE_COUNTER(STAT_RecastNavMeshGenerator_ProcessTileTasks_FinishedTasks);
FRunningTileElement& Element = RunningDirtyTiles[Idx];
check(Element.AsyncTask);
if (Element.AsyncTask->IsDone())
{
// Add generated tiles to navmesh
if (!Element.bShouldDiscard)
{
FRecastTileGenerator& TileGenerator = *(Element.AsyncTask->GetTask().TileGenerator);
TArray<uint32> UpdatedTileIndices = AddGeneratedTiles(TileGenerator);
UpdatedTiles.Append(UpdatedTileIndices);
// Store compressed tile cache layers so it can be reused later
if (TileGenerator.GetCompressedLayers().Num())
{
QUICK_SCOPE_CYCLE_COUNTER(STAT_RecastNavMeshGenerator_StoringCompressedLayers);
DestNavMesh->AddTileCacheLayers(Element.Coord.X, Element.Coord.Y, TileGenerator.GetCompressedLayers());
}
else
{
DestNavMesh->MarkEmptyTileCacheLayers(Element.Coord.X, Element.Coord.Y);
}
}
{
QUICK_SCOPE_CYCLE_COUNTER(STAT_RecastNavMeshGenerator_TileGeneratorRemoval);
// Destroy tile generator task
delete Element.AsyncTask;
Element.AsyncTask = nullptr;
// Remove completed tile element from a list of running tasks
RunningDirtyTiles.RemoveAtSwap(Idx, 1, false);
}
}
}
return UpdatedTiles;
}
#endif
#if TIME_SLICE_NAV_REGEN
bool FRecastNavMeshGenerator::IsTimeSliceDurationExceeded(const double StartTime) const
{
const double CurTime = FPlatformTime::Seconds();
return CurTime - StartTime >= TimeSliceDuration;
}
#endif
#if !RECAST_ASYNC_REBUILDING
TArray<uint32> FRecastNavMeshGenerator::ProcessTileTasksSync(const int32 NumTasksToProcess)
{
QUICK_SCOPE_CYCLE_COUNTER(STAT_RecastNavMeshGenerator_ProcessTileTasksSync);
TArray<uint32> UpdatedTiles;
const bool bGameStaticNavMesh = IsGameStaticNavMesh(DestNavMesh);
#if TIME_SLICE_NAV_REGEN
const double StartTime = FPlatformTime::Seconds();
//if we are time slice processing a tile (ie we have already done some processing on this tile last frame)
bool bIsTimeSliceProcessingTile = TileGeneratorSync.Get() != nullptr;
#endif
int32 NumProcessedTasks = 0;
//if bIsTimeSliceProcessingTile is true then this will be the Idx of the next Element to process not the Idx of TileGeneratorSync
int32 ElementIdx = PendingDirtyTiles.Num() - 1;
if ((ElementIdx >= 0
&& NumProcessedTasks < NumTasksToProcess)
#if TIME_SLICE_NAV_REGEN
|| bIsTimeSliceProcessingTile
#endif
)
{
// Submit pending tile elements
while (true)
{
QUICK_SCOPE_CYCLE_COUNTER(STAT_RecastNavMeshGenerator_ProcessTileTasks_NewTasks);
FIntPoint TileLocation;
//this will only be set up when bIsTimeSliceProcessingTile == false,
//its currently not needed at other times.
TArray<FBox> DirtyAreas;
#if TIME_SLICE_NAV_REGEN
if (bIsTimeSliceProcessingTile)
{
TileLocation.X = TileGeneratorSync->GetTileX();
TileLocation.Y = TileGeneratorSync->GetTileY();
}
else
#endif //TIME_SLICE_NAV_REGEN
{
FPendingTileElement& PendingElement = PendingDirtyTiles[ElementIdx];
TileLocation.X = PendingElement.Coord.X;
TileLocation.Y = PendingElement.Coord.Y;
DirtyAreas = MoveTemp(PendingElement.DirtyAreas);
// Remove submitted element from pending list, this simplifies time sliced tile processing
PendingDirtyTiles.RemoveAt(ElementIdx);
// Release memory, list could be quite big after map load
if (PendingDirtyTiles.Num() == 0)
{
PendingDirtyTiles.Empty(32);
}
//see definition of bIsTimeSliceProcessingTile
ensureMsgf(TileGeneratorSync.Get() == nullptr, TEXT("TileGeneratorSync should be NULL if we aren't currently time slicing this tile"));
TileGeneratorSync = CreateTileGenerator(TileLocation, DirtyAreas);
#if TIME_SLICE_NAV_REGEN
if (IsTimeSliceDurationExceeded(StartTime))
{
break;
}
#endif //TIME_SLICE_NAV_REGEN
}
FRecastTileGenerator& TileGeneratorRef = *TileGeneratorSync.Get();
ensureMsgf(TileGeneratorRef.GetTileX() == TileLocation.X && TileGeneratorRef.GetTileY() == TileLocation.Y,
TEXT("X Loc Mismatch between TileGeneratorRef and PendingElement"));
if (TileGeneratorRef.HasDataToBuild())
{
#if TIME_SLICE_NAV_REGEN
bool bContinueTimeSliceProcessing = true;
ETimeSliceWorkResult TimeSliceWorkResult = ETimeSliceWorkResult::CallAgain;
if (!TileGeneratorRef.HasDoneWork())
{
while (TimeSliceWorkResult == ETimeSliceWorkResult::CallAgain && bContinueTimeSliceProcessing)
{
TimeSliceWorkResult = TileGeneratorRef.DoWork();
bContinueTimeSliceProcessing = !IsTimeSliceDurationExceeded(StartTime);
}
if (!bContinueTimeSliceProcessing)
{
break;
}
}
#else //TIME_SLICE_NAV_REGEN
TileGeneratorRef.DoWork();
#endif //TIME_SLICE_NAV_REGEN
//@TODO Investigate preventing further processing of tiles when generation has failed
const TArray<uint32> UpdatedTileIndices = AddGeneratedTiles(TileGeneratorRef);
UpdatedTiles.Append(UpdatedTileIndices);
// Store compressed tile cache layers so it can be reused later
if (TileGeneratorRef.GetCompressedLayers().Num())
{
QUICK_SCOPE_CYCLE_COUNTER(STAT_RecastNavMeshGenerator_StoringCompressedLayers);
DestNavMesh->AddTileCacheLayers(TileLocation.X, TileLocation.Y, TileGeneratorRef.GetCompressedLayers());
}
else
{
DestNavMesh->MarkEmptyTileCacheLayers(TileLocation.X, TileLocation.Y);
}
}
else if (!bGameStaticNavMesh)
{
RemoveLayers(TileLocation, UpdatedTiles);
}
TileGeneratorSync = nullptr;
NumProcessedTasks++;
#if TIME_SLICE_NAV_REGEN
//only subtract from the ElementIdx if we aren't time slice Processing this tile (ie the tile hasn't already had some
//processing done on it last frame)
if (!bIsTimeSliceProcessingTile)
{
--ElementIdx;
}
bIsTimeSliceProcessingTile = false;
#else //TIME_SLICE_NAV_REGEN
--ElementIdx;
#endif //TIME_SLICE_NAV_REGEN
if (NumProcessedTasks >= NumTasksToProcess || ElementIdx < 0)
{
break;
}
#if TIME_SLICE_NAV_REGEN
else
{
//only perform the time slice check if we are going to iterate again
if (IsTimeSliceDurationExceeded(StartTime))
{
break;
}
}
#endif //TIME_SLICE_NAV_REGEN
}
}
return UpdatedTiles;
}
#endif
TArray<uint32> FRecastNavMeshGenerator::ProcessTileTasks(const int32 NumTasksToProcess)
{
const bool bHasTasksAtStart = GetNumRemaningBuildTasks() > 0;
#if RECAST_ASYNC_REBUILDING
TArray<uint32> UpdatedTiles = ProcessTileTasksAsync(NumTasksToProcess);
#else
TArray<uint32> UpdatedTiles = ProcessTileTasksSync(NumTasksToProcess);
#endif
// Notify owner in case all tasks has been completed
const bool bHasTasksAtEnd = GetNumRemaningBuildTasks() > 0;
if (bHasTasksAtStart && !bHasTasksAtEnd)
{
DestNavMesh->OnNavMeshGenerationFinished();
}
#if !UE_BUILD_SHIPPING && OUTPUT_NAV_TILE_LAYER_COMPRESSION_DATA && FRAMEPRO_ENABLED
//only do this if framepro is recording as its an expensive operation
if (FFrameProProfiler::IsFrameProRecording())
{
int32 TileCacheSize = DestNavMesh->GetCompressedTileCacheSize();
FPlatformMisc::CustomNamedStat("TotalTileCacheSize", static_cast<float>(TileCacheSize), "NavMesh", "Bytes");
}
#endif
return UpdatedTiles;
}
void FRecastNavMeshGenerator::ExportComponentGeometry(UActorComponent* Component, FNavigationRelevantData& Data)
{
FRecastGeometryExport GeomExport(Data);
RecastGeometryExport::ExportComponent(Component, GeomExport);
RecastGeometryExport::CovertCoordDataToRecast(GeomExport.VertexBuffer);
RecastGeometryExport::StoreCollisionCache(GeomExport);
}
void FRecastNavMeshGenerator::ExportVertexSoupGeometry(const TArray<FVector>& Verts, FNavigationRelevantData& Data)
{
FRecastGeometryExport GeomExport(Data);
RecastGeometryExport::ExportVertexSoup(Verts, GeomExport.VertexBuffer, GeomExport.IndexBuffer, GeomExport.Data->Bounds);
RecastGeometryExport::StoreCollisionCache(GeomExport);
}
void FRecastNavMeshGenerator::ExportRigidBodyGeometry(UBodySetup& BodySetup, TNavStatArray<FVector>& OutVertexBuffer, TNavStatArray<int32>& OutIndexBuffer, const FTransform& LocalToWorld)
{
TNavStatArray<float> VertCoords;
FBox TempBounds;
RecastGeometryExport::ExportRigidBodySetup(BodySetup, VertCoords, OutIndexBuffer, TempBounds, LocalToWorld);
OutVertexBuffer.Reserve(OutVertexBuffer.Num() + (VertCoords.Num() / 3));
for (int32 i = 0; i < VertCoords.Num(); i += 3)
{
OutVertexBuffer.Add(FVector(VertCoords[i + 0], VertCoords[i + 1], VertCoords[i + 2]));
}
}
void FRecastNavMeshGenerator::ExportRigidBodyGeometry(UBodySetup& BodySetup, TNavStatArray<FVector>& OutTriMeshVertexBuffer, TNavStatArray<int32>& OutTriMeshIndexBuffer
, TNavStatArray<FVector>& OutConvexVertexBuffer, TNavStatArray<int32>& OutConvexIndexBuffer, TNavStatArray<int32>& OutShapeBuffer
, const FTransform& LocalToWorld)
{
BodySetup.CreatePhysicsMeshes();
TNavStatArray<float> VertCoords;
FBox TempBounds;
VertCoords.Reset();
RecastGeometryExport::ExportRigidBodyTriMesh(BodySetup, VertCoords, OutTriMeshIndexBuffer, TempBounds, LocalToWorld);
OutTriMeshVertexBuffer.Reserve(OutTriMeshVertexBuffer.Num() + (VertCoords.Num() / 3));
for (int32 i = 0; i < VertCoords.Num(); i += 3)
{
OutTriMeshVertexBuffer.Add(FVector(VertCoords[i + 0], VertCoords[i + 1], VertCoords[i + 2]));
}
const int32 NumExistingVerts = OutConvexVertexBuffer.Num();
VertCoords.Reset();
RecastGeometryExport::ExportRigidBodyConvexElements(BodySetup, VertCoords, OutConvexIndexBuffer, OutShapeBuffer, TempBounds, LocalToWorld);
RecastGeometryExport::ExportRigidBodyBoxElements(BodySetup.AggGeom, VertCoords, OutConvexIndexBuffer, OutShapeBuffer, TempBounds, LocalToWorld, NumExistingVerts);
RecastGeometryExport::ExportRigidBodySphylElements(BodySetup.AggGeom, VertCoords, OutConvexIndexBuffer, OutShapeBuffer, TempBounds, LocalToWorld, NumExistingVerts);
RecastGeometryExport::ExportRigidBodySphereElements(BodySetup.AggGeom, VertCoords, OutConvexIndexBuffer, OutShapeBuffer, TempBounds, LocalToWorld, NumExistingVerts);
OutConvexVertexBuffer.Reserve(OutConvexVertexBuffer.Num() + (VertCoords.Num() / 3));
for (int32 i = 0; i < VertCoords.Num(); i += 3)
{
OutConvexVertexBuffer.Add(FVector(VertCoords[i + 0], VertCoords[i + 1], VertCoords[i + 2]));
}
}
void FRecastNavMeshGenerator::ExportAggregatedGeometry(const FKAggregateGeom& AggGeom, TNavStatArray<FVector>& OutConvexVertexBuffer, TNavStatArray<int32>& OutConvexIndexBuffer, TNavStatArray<int32>& OutShapeBuffer, const FTransform& LocalToWorld)
{
TNavStatArray<float> VertCoords;
FBox TempBounds;
const int32 NumExistingVerts = OutConvexVertexBuffer.Num();
// convex and tri mesh are NOT supported, since they require BodySetup.CreatePhysicsMeshes() call
// only simple shapes
RecastGeometryExport::ExportRigidBodyBoxElements(AggGeom, VertCoords, OutConvexIndexBuffer, OutShapeBuffer, TempBounds, LocalToWorld, NumExistingVerts);
RecastGeometryExport::ExportRigidBodySphylElements(AggGeom, VertCoords, OutConvexIndexBuffer, OutShapeBuffer, TempBounds, LocalToWorld, NumExistingVerts);
RecastGeometryExport::ExportRigidBodySphereElements(AggGeom, VertCoords, OutConvexIndexBuffer, OutShapeBuffer, TempBounds, LocalToWorld, NumExistingVerts);
OutConvexVertexBuffer.Reserve(OutConvexVertexBuffer.Num() + (VertCoords.Num() / 3));
for (int32 i = 0; i < VertCoords.Num(); i += 3)
{
OutConvexVertexBuffer.Add(FVector(VertCoords[i + 0], VertCoords[i + 1], VertCoords[i + 2]));
}
}
bool FRecastNavMeshGenerator::IsBuildInProgress(bool bCheckDirtyToo) const
{
return RunningDirtyTiles.Num()
|| (bCheckDirtyToo && PendingDirtyTiles.Num())
#if TIME_SLICE_NAV_REGEN
|| TileGeneratorSync.Get()
#endif
;
}
int32 FRecastNavMeshGenerator::GetNumRemaningBuildTasks() const
{
return RunningDirtyTiles.Num()
+ PendingDirtyTiles.Num()
#if TIME_SLICE_NAV_REGEN
+ (TileGeneratorSync.Get() ? 1 : 0)
#endif
;
}
int32 FRecastNavMeshGenerator::GetNumRunningBuildTasks() const
{
return RunningDirtyTiles.Num()
#if TIME_SLICE_NAV_REGEN
+ (TileGeneratorSync.Get() ? 1 : 0)
#endif
;
}
bool FRecastNavMeshGenerator::GatherGeometryOnGameThread() const
{
return DestNavMesh == nullptr || DestNavMesh->ShouldGatherDataOnGameThread() == true;
}
bool FRecastNavMeshGenerator::IsTileChanged(int32 TileIdx) const
{
#if WITH_EDITOR
// Check recently built tiles
if (TileIdx > 0)
{
FTileTimestamp TileTimestamp;
TileTimestamp.TileIdx = static_cast<uint32>(TileIdx);
if (RecentlyBuiltTiles.Contains(TileTimestamp))
{
return true;
}
}
#endif//WITH_EDITOR
return false;
}
uint32 FRecastNavMeshGenerator::LogMemUsed() const
{
UE_LOG(LogNavigation, Display, TEXT(" FRecastNavMeshGenerator: self %d"), sizeof(FRecastNavMeshGenerator));
uint32 GeneratorsMem = 0;
for (const FRunningTileElement& Element : RunningDirtyTiles)
{
GeneratorsMem += Element.AsyncTask->GetTask().TileGenerator->UsedMemoryOnStartup;
#if TIME_SLICE_NAV_REGEN
GeneratorsMem += TileGeneratorSync->UsedMemoryOnStartup;
#endif
}
UE_LOG(LogNavigation, Display, TEXT(" FRecastNavMeshGenerator: Total Generator\'s size %u, count %d"), GeneratorsMem, RunningDirtyTiles.Num());
return GeneratorsMem + sizeof(FRecastNavMeshGenerator) + PendingDirtyTiles.GetAllocatedSize() + RunningDirtyTiles.GetAllocatedSize();
}
#if !(UE_BUILD_SHIPPING || UE_BUILD_TEST) && ENABLE_VISUAL_LOG
void FRecastNavMeshGenerator::GrabDebugSnapshot(struct FVisualLogEntry* Snapshot, const FBox& BoundingBox, const FName& CategoryName, ELogVerbosity::Type LogVerbosity) const
{
const UNavigationSystemV1* NavSys = FNavigationSystem::GetCurrent<UNavigationSystemV1>(GetWorld());
const FNavigationOctree* NavOctree = NavSys ? NavSys->GetNavOctree() : NULL;
if (Snapshot == nullptr)
{
return;
}
if (NavOctree == NULL)
{
UE_LOG(LogNavigation, Error, TEXT("Failed to vlog navigation data due to %s being NULL"), NavSys == NULL ? TEXT("NavigationSystem") : TEXT("NavOctree"));
return;
}
ELogVerbosity::Type NavAreaVerbosity = FMath::Clamp(ELogVerbosity::Type(LogVerbosity + 1), ELogVerbosity::NoLogging, ELogVerbosity::VeryVerbose);
for (int32 Index = 0; Index < NavSys->NavDataSet.Num(); ++Index)
{
TArray<FVector> CoordBuffer;
TArray<int32> Indices;
TNavStatArray<FVector> Faces;
const ARecastNavMesh* NavData = Cast<const ARecastNavMesh>(NavSys->NavDataSet[Index]);
if (NavData)
{
for (FNavigationOctree::TConstElementBoxIterator<FNavigationOctree::DefaultStackAllocator> It(*NavOctree, BoundingBox);
It.HasPendingElements();
It.Advance())
{
const FNavigationOctreeElement& Element = It.GetCurrentElement();
const bool bExportGeometry = Element.Data->HasGeometry() && Element.ShouldUseGeometry(DestNavMesh->GetConfig());
if (bExportGeometry && Element.Data->CollisionData.Num())
{
FRecastGeometryCache CachedGeometry(Element.Data->CollisionData.GetData());
const uint32 NumVerts = CachedGeometry.Header.NumVerts;
CoordBuffer.Reset(NumVerts);
for (uint32 VertIdx = 0; VertIdx < NumVerts * 3; VertIdx += 3)
{
CoordBuffer.Add(Recast2UnrealPoint(&CachedGeometry.Verts[VertIdx]));
}
const uint32 NumIndices = CachedGeometry.Header.NumFaces * 3;
Indices.SetNum(NumIndices, false);
for (uint32 IndicesIdx = 0; IndicesIdx < NumIndices; ++IndicesIdx)
{
Indices[IndicesIdx] = CachedGeometry.Indices[IndicesIdx];
}
Snapshot->AddElement(CoordBuffer, Indices, CategoryName, LogVerbosity, FColorList::LightGrey.WithAlpha(255));
}
else
{
TArray<FVector> Verts;
const TArray<FAreaNavModifier>& AreaMods = Element.Data->Modifiers.GetAreas();
for (int32 i = 0; i < AreaMods.Num(); i++)
{
if (AreaMods[i].GetShapeType() == ENavigationShapeType::Unknown)
{
continue;
}
const uint8 AreaId = NavData->GetAreaID(AreaMods[i].GetAreaClass());
const UClass* AreaClass = NavData->GetAreaClass(AreaId);
const UNavArea* DefArea = AreaClass ? ((UClass*)AreaClass)->GetDefaultObject<UNavArea>() : NULL;
const FColor PolygonColor = AreaClass != FNavigationSystem::GetDefaultWalkableArea() ? (DefArea ? DefArea->DrawColor : NavData->GetConfig().Color) : FColorList::Cyan;
if (AreaMods[i].GetShapeType() == ENavigationShapeType::Box)
{
FBoxNavAreaData Box;
AreaMods[i].GetBox(Box);
Snapshot->AddElement(FBox::BuildAABB(Box.Origin, Box.Extent), FMatrix::Identity, CategoryName, NavAreaVerbosity, PolygonColor.WithAlpha(255));
}
else if (AreaMods[i].GetShapeType() == ENavigationShapeType::Cylinder)
{
FCylinderNavAreaData Cylinder;
AreaMods[i].GetCylinder(Cylinder);
Snapshot->AddElement(Cylinder.Origin, Cylinder.Origin + FVector(0, 0, Cylinder.Height), Cylinder.Radius, CategoryName, NavAreaVerbosity, PolygonColor.WithAlpha(255));
}
else
{
FConvexNavAreaData Convex;
AreaMods[i].GetConvex(Convex);
Verts.Reset();
GrowConvexHull(NavData->AgentRadius, Convex.Points, Verts);
Snapshot->AddElement(
Verts,
Convex.MinZ - NavData->CellHeight,
Convex.MaxZ + NavData->CellHeight,
CategoryName, NavAreaVerbosity, PolygonColor.WithAlpha(255));
}
}
}
}
}
}
}
#endif
#if !(UE_BUILD_SHIPPING || UE_BUILD_TEST) && ENABLE_VISUAL_LOG
void FRecastNavMeshGenerator::ExportNavigationData(const FString& FileName) const
{
const UNavigationSystemV1* NavSys = FNavigationSystem::GetCurrent<UNavigationSystemV1>(GetWorld());
const FNavigationOctree* NavOctree = NavSys ? NavSys->GetNavOctree() : NULL;
if (NavOctree == NULL)
{
UE_LOG(LogNavigation, Error, TEXT("Failed to export navigation data due to %s being NULL"), NavSys == NULL ? TEXT("NavigationSystem") : TEXT("NavOctree"));
return;
}
const double StartExportTime = FPlatformTime::Seconds();
FString CurrentTimeStr = FDateTime::Now().ToString();
for (int32 Index = 0; Index < NavSys->NavDataSet.Num(); ++Index)
{
// feed data from octtree and mark for rebuild
TNavStatArray<float> CoordBuffer;
TNavStatArray<int32> IndexBuffer;
const ARecastNavMesh* NavData = Cast<const ARecastNavMesh>(NavSys->NavDataSet[Index]);
if (NavData)
{
struct FAreaExportData
{
FConvexNavAreaData Convex;
uint8 AreaId;
};
TArray<FAreaExportData> AreaExport;
for(FNavigationOctree::TConstElementBoxIterator<FNavigationOctree::DefaultStackAllocator> It(*NavOctree, TotalNavBounds);
It.HasPendingElements();
It.Advance())
{
const FNavigationOctreeElement& Element = It.GetCurrentElement();
const bool bExportGeometry = Element.Data->HasGeometry() && Element.ShouldUseGeometry(DestNavMesh->GetConfig());
if (bExportGeometry && Element.Data->CollisionData.Num())
{
FRecastGeometryCache CachedGeometry(Element.Data->CollisionData.GetData());
IndexBuffer.Reserve( IndexBuffer.Num() + (CachedGeometry.Header.NumFaces * 3 ));
CoordBuffer.Reserve( CoordBuffer.Num() + (CachedGeometry.Header.NumVerts * 3 ));
for (int32 i = 0; i < CachedGeometry.Header.NumFaces * 3; i++)
{
IndexBuffer.Add(CachedGeometry.Indices[i] + CoordBuffer.Num() / 3);
}
for (int32 i = 0; i < CachedGeometry.Header.NumVerts * 3; i++)
{
CoordBuffer.Add(CachedGeometry.Verts[i]);
}
}
else
{
const TArray<FAreaNavModifier>& AreaMods = Element.Data->Modifiers.GetAreas();
for (int32 i = 0; i < AreaMods.Num(); i++)
{
FAreaExportData ExportInfo;
ExportInfo.AreaId = NavData->GetAreaID(AreaMods[i].GetAreaClass());
if (AreaMods[i].GetShapeType() == ENavigationShapeType::Convex)
{
AreaMods[i].GetConvex(ExportInfo.Convex);
TArray<FVector> ConvexVerts;
GrowConvexHull(NavData->AgentRadius, ExportInfo.Convex.Points, ConvexVerts);
ExportInfo.Convex.MinZ -= NavData->CellHeight;
ExportInfo.Convex.MaxZ += NavData->CellHeight;
ExportInfo.Convex.Points = ConvexVerts;
AreaExport.Add(ExportInfo);
}
}
}
}
UWorld* NavigationWorld = GetWorld();
for (int32 LevelIndex = 0; LevelIndex < NavigationWorld->GetNumLevels(); ++LevelIndex)
{
const ULevel* const Level = NavigationWorld->GetLevel(LevelIndex);
if (Level == NULL)
{
continue;
}
const TArray<FVector>* LevelGeom = Level->GetStaticNavigableGeometry();
if (LevelGeom != NULL && LevelGeom->Num() > 0)
{
TNavStatArray<FVector> Verts;
TNavStatArray<int32> Faces;
// For every ULevel in World take its pre-generated static geometry vertex soup
RecastGeometryExport::TransformVertexSoupToRecast(*LevelGeom, Verts, Faces);
IndexBuffer.Reserve( IndexBuffer.Num() + Faces.Num() );
CoordBuffer.Reserve( CoordBuffer.Num() + Verts.Num() * 3);
for (int32 i = 0; i < Faces.Num(); i++)
{
IndexBuffer.Add(Faces[i] + CoordBuffer.Num() / 3);
}
for (int32 i = 0; i < Verts.Num(); i++)
{
CoordBuffer.Add(Verts[i].X);
CoordBuffer.Add(Verts[i].Y);
CoordBuffer.Add(Verts[i].Z);
}
}
}
FString AreaExportStr;
for (int32 i = 0; i < AreaExport.Num(); i++)
{
const FAreaExportData& ExportInfo = AreaExport[i];
AreaExportStr += FString::Printf(TEXT("\nAE %d %d %f %f\n"),
ExportInfo.AreaId, ExportInfo.Convex.Points.Num(), ExportInfo.Convex.MinZ, ExportInfo.Convex.MaxZ);
for (int32 iv = 0; iv < ExportInfo.Convex.Points.Num(); iv++)
{
FVector Pt = Unreal2RecastPoint(ExportInfo.Convex.Points[iv]);
AreaExportStr += FString::Printf(TEXT("Av %f %f %f\n"), Pt.X, Pt.Y, Pt.Z);
}
}
FString AdditionalData;
if (AreaExport.Num())
{
AdditionalData += "# Area export\n";
AdditionalData += AreaExportStr;
AdditionalData += "\n";
}
AdditionalData += "# RecastDemo specific data\n";
#if 0
// use this bounds to have accurate navigation data bounds
const FVector Center = Unreal2RecastPoint(NavData->GetBounds().GetCenter());
FVector Extent = FVector(NavData->GetBounds().GetExtent());
Extent = FVector(Extent.X, Extent.Z, Extent.Y);
#else
// this bounds match navigation bounds from level
FBox RCNavBounds = Unreal2RecastBox(TotalNavBounds);
const FVector Center = RCNavBounds.GetCenter();
const FVector Extent = RCNavBounds.GetExtent();
#endif
const FBox Box = FBox::BuildAABB(Center, Extent);
AdditionalData += FString::Printf(
TEXT("rd_bbox %7.7f %7.7f %7.7f %7.7f %7.7f %7.7f\n"),
Box.Min.X, Box.Min.Y, Box.Min.Z,
Box.Max.X, Box.Max.Y, Box.Max.Z
);
const FRecastNavMeshGenerator* CurrentGen = static_cast<const FRecastNavMeshGenerator*>(NavData->GetGenerator());
check(CurrentGen);
AdditionalData += FString::Printf(TEXT("# AgentHeight\n"));
AdditionalData += FString::Printf(TEXT("rd_agh %5.5f\n"), CurrentGen->Config.AgentHeight);
AdditionalData += FString::Printf(TEXT("# AgentRadius\n"));
AdditionalData += FString::Printf(TEXT("rd_agr %5.5f\n"), CurrentGen->Config.AgentRadius);
AdditionalData += FString::Printf(TEXT("# Cell Size\n"));
AdditionalData += FString::Printf(TEXT("rd_cs %5.5f\n"), CurrentGen->Config.cs);
AdditionalData += FString::Printf(TEXT("# Cell Height\n"));
AdditionalData += FString::Printf(TEXT("rd_ch %5.5f\n"), CurrentGen->Config.ch);
AdditionalData += FString::Printf(TEXT("# Agent max climb\n"));
AdditionalData += FString::Printf(TEXT("rd_amc %d\n"), (int)CurrentGen->Config.AgentMaxClimb);
AdditionalData += FString::Printf(TEXT("# Agent max slope\n"));
AdditionalData += FString::Printf(TEXT("rd_ams %5.5f\n"), CurrentGen->Config.walkableSlopeAngle);
AdditionalData += FString::Printf(TEXT("# Region min size\n"));
AdditionalData += FString::Printf(TEXT("rd_rmis %d\n"), (uint32)FMath::Sqrt(CurrentGen->Config.minRegionArea));
AdditionalData += FString::Printf(TEXT("# Region merge size\n"));
AdditionalData += FString::Printf(TEXT("rd_rmas %d\n"), (uint32)FMath::Sqrt(CurrentGen->Config.mergeRegionArea));
AdditionalData += FString::Printf(TEXT("# Max edge len\n"));
AdditionalData += FString::Printf(TEXT("rd_mel %d\n"), CurrentGen->Config.maxEdgeLen);
AdditionalData += FString::Printf(TEXT("# Perform Voxel Filtering\n"));
AdditionalData += FString::Printf(TEXT("rd_pvf %d\n"), CurrentGen->Config.bPerformVoxelFiltering);
AdditionalData += FString::Printf(TEXT("# Generate Detailed Mesh\n"));
AdditionalData += FString::Printf(TEXT("rd_gdm %d\n"), CurrentGen->Config.bGenerateDetailedMesh);
AdditionalData += FString::Printf(TEXT("# MaxPolysPerTile\n"));
AdditionalData += FString::Printf(TEXT("rd_mppt %d\n"), CurrentGen->Config.MaxPolysPerTile);
AdditionalData += FString::Printf(TEXT("# maxVertsPerPoly\n"));
AdditionalData += FString::Printf(TEXT("rd_mvpp %d\n"), CurrentGen->Config.maxVertsPerPoly);
AdditionalData += FString::Printf(TEXT("# Tile size\n"));
AdditionalData += FString::Printf(TEXT("rd_ts %d\n"), CurrentGen->Config.tileSize);
AdditionalData += FString::Printf(TEXT("\n"));
const FString FilePathName = FileName + FString::Printf(TEXT("_NavDataSet%d_%s.obj"), Index, *CurrentTimeStr) ;
ExportGeomToOBJFile(FilePathName, CoordBuffer, IndexBuffer, AdditionalData);
}
}
UE_LOG(LogNavigation, Log, TEXT("ExportNavigation time: %.3f sec ."), FPlatformTime::Seconds() - StartExportTime);
}
#endif
static class FNavigationGeomExec : private FSelfRegisteringExec
{
public:
/** Console commands, see embeded usage statement **/
virtual bool Exec( UWorld* InWorld, const TCHAR* Cmd, FOutputDevice& Ar ) override
{
#if ALLOW_DEBUG_FILES && !(UE_BUILD_SHIPPING || UE_BUILD_TEST)
bool bCorrectCmd = FParse::Command(&Cmd, TEXT("ExportNavigation"));
if (bCorrectCmd && !InWorld)
{
UE_LOG(LogNavigation, Error, TEXT("Failed to export navigation data due to missing UWorld"));
}
else if (InWorld && bCorrectCmd)
{
UNavigationSystemV1* NavSys = FNavigationSystem::GetCurrent<UNavigationSystemV1>(InWorld);
if (NavSys)
{
const ANavigationData* NavData = NavSys->GetDefaultNavDataInstance();
if (NavData)
{
if (const FNavDataGenerator* Generator = NavData->GetGenerator())
{
const FString Name = NavData->GetName();
Generator->ExportNavigationData( FString::Printf( TEXT("%s/%s"), *FPaths::ProjectSavedDir(), *Name ));
return true;
}
else
{
UE_LOG(LogNavigation, Error, TEXT("Failed to export navigation data due to missing generator"));
}
}
else
{
UE_LOG(LogNavigation, Error, TEXT("Failed to export navigation data due to navigation data"));
}
}
else
{
UE_LOG(LogNavigation, Error, TEXT("Failed to export navigation data due to missing navigation system"));
}
}
#endif // ALLOW_DEBUG_FILES && WITH_EDITOR
return false;
}
} NavigationGeomExec;
#endif // WITH_RECAST
Reference in New Issue View Git Blame Copy Permalink