// Copyright Epic Games, Inc. All Rights Reserved. #include "BSPOps.h" #include "EngineDefines.h" #include "Model.h" #include "Materials/Material.h" #include "Engine/BrushBuilder.h" #include "Editor/EditorEngine.h" #include "Components/BrushComponent.h" #include "GameFramework/Volume.h" DEFINE_LOG_CATEGORY_STATIC(LogBSPOps, Log, All); /** Errors encountered in Csg operation. */ int32 FBSPOps::GErrors = 0; bool FBSPOps::GFastRebuild = false; FBspPointsGrid* FBspPointsGrid::GBspPoints = nullptr; FBspPointsGrid* FBspPointsGrid::GBspVectors = nullptr; static void TagReferencedNodes(UModel* Model, int32* NodeRef, int32* PolyRef, int32 iNode) { FBspNode& Node = Model->Nodes[iNode]; NodeRef[iNode] = 0; PolyRef[Node.iSurf] = 0; if (Node.iFront != INDEX_NONE) TagReferencedNodes(Model, NodeRef, PolyRef, Node.iFront); if (Node.iBack != INDEX_NONE) TagReferencedNodes(Model, NodeRef, PolyRef, Node.iBack); if (Node.iPlane != INDEX_NONE) TagReferencedNodes(Model, NodeRef, PolyRef, Node.iPlane); } // // Update a bounding volume by expanding it to enclose a list of polys. // static void UpdateBoundWithPolys(FBox& Bound, FPoly** PolyList, int32 nPolys) { for (int32 i = 0; i < nPolys; i++) for (int32 j = 0; j < PolyList[i]->Vertices.Num(); j++) Bound += PolyList[i]->Vertices[j]; } // // Update a convolution hull with a list of polys. // static void UpdateConvolutionWithPolys(UModel* Model, int32 iNode, FPoly** PolyList, int32 nPolys) { FBox Box(ForceInit); FBspNode& Node = Model->Nodes[iNode]; Node.iCollisionBound = Model->LeafHulls.Num(); for (int32 i = 0; i < nPolys; i++) { if (PolyList[i]->iBrushPoly != INDEX_NONE) { int32 j; for (j = 0; j < i; j++) if (PolyList[j]->iBrushPoly == PolyList[i]->iBrushPoly) break; if (j >= i) Model->LeafHulls.Add(PolyList[i]->iBrushPoly); } for (int32 j = 0; j < PolyList[i]->Vertices.Num(); j++) Box += PolyList[i]->Vertices[j]; } Model->LeafHulls.Add(INDEX_NONE); // Add bounds. Model->LeafHulls.Add(*(int32*)&Box.Min.X); Model->LeafHulls.Add(*(int32*)&Box.Min.Y); Model->LeafHulls.Add(*(int32*)&Box.Min.Z); Model->LeafHulls.Add(*(int32*)&Box.Max.X); Model->LeafHulls.Add(*(int32*)&Box.Max.Y); Model->LeafHulls.Add(*(int32*)&Box.Max.Z); } // // Cut a partitioning poly by a list of polys, and add the resulting inside pieces to the // front list and back list. // static void SplitPartitioner( UModel* Model, FPoly** PolyList, FPoly** FrontList, FPoly** BackList, int32 n, int32 nPolys, int32& nFront, int32& nBack, FPoly InfiniteEdPoly, TArray& AllocatedFPolys) { FPoly FrontPoly, BackPoly; while (n < nPolys) { FPoly* Poly = PolyList[n]; switch (InfiniteEdPoly.SplitWithPlane(Poly->Vertices[0], Poly->Normal, &FrontPoly, &BackPoly, 0)) { case SP_Coplanar: // May occasionally happen. // UE_LOG(LogBSPOps, Log, TEXT("FilterBound: Got inficoplanar") ); break; case SP_Front: // Shouldn't happen if hull is correct. // UE_LOG(LogBSPOps, Log, TEXT("FilterBound: Got infifront") ); return; case SP_Split: InfiniteEdPoly = BackPoly; break; case SP_Back: break; } n++; } FPoly* New = new FPoly; *New = InfiniteEdPoly; New->Reverse(); New->iBrushPoly |= 0x40000000; FrontList[nFront++] = New; AllocatedFPolys.Add(New); New = new FPoly; *New = InfiniteEdPoly; BackList[nBack++] = New; AllocatedFPolys.Add(New); } // // Build an FPoly representing an "infinite" plane (which exceeds the maximum // dimensions of the world in all directions) for a particular Bsp node. // FPoly FBSPOps::BuildInfiniteFPoly(UModel* Model, int32 iNode) { FBspNode& Node = Model->Nodes[iNode]; FBspSurf& Poly = Model->Surfs[Node.iSurf]; FVector Base = Poly.Plane * Poly.Plane.W; FVector Normal = Poly.Plane; FVector Axis1, Axis2; // Find two non-problematic axis vectors. Normal.FindBestAxisVectors(Axis1, Axis2); // Set up the FPoly. FPoly EdPoly; EdPoly.Init(); EdPoly.Normal = Normal; EdPoly.Base = Base; new (EdPoly.Vertices) FVector(Base + Axis1 * WORLD_MAX + Axis2 * WORLD_MAX); new (EdPoly.Vertices) FVector(Base - Axis1 * WORLD_MAX + Axis2 * WORLD_MAX); new (EdPoly.Vertices) FVector(Base - Axis1 * WORLD_MAX - Axis2 * WORLD_MAX); new (EdPoly.Vertices) FVector(Base + Axis1 * WORLD_MAX - Axis2 * WORLD_MAX); return EdPoly; } // // Recursively filter a set of polys defining a convex hull down the Bsp, // splitting it into two halves at each node and adding in the appropriate // face polys at splits. // static void FilterBound( UModel* Model, FBox* ParentBound, int32 iNode, FPoly** PolyList, int32 nPolys, int32 Outside) { FMemMark Mark(FMemStack::Get()); FBspNode& Node = Model->Nodes[iNode]; FBspSurf& Surf = Model->Surfs[Node.iSurf]; FVector Base = Surf.Plane * Surf.Plane.W; FVector& Normal = Model->Vectors[Surf.vNormal]; FBox Bound(ForceInit); Bound.Min.X = Bound.Min.Y = Bound.Min.Z = +WORLD_MAX; Bound.Max.X = Bound.Max.Y = Bound.Max.Z = -WORLD_MAX; // Split bound into front half and back half. FPoly** FrontList = new (FMemStack::Get(), nPolys * 2 + 16) FPoly*; int32 nFront = 0; FPoly** BackList = new (FMemStack::Get(), nPolys * 2 + 16) FPoly*; int32 nBack = 0; // Keeping track of allocated FPoly structures to delete later on. TArray AllocatedFPolys; FPoly* FrontPoly = new FPoly; FPoly* BackPoly = new FPoly; // Keep track of allocations. AllocatedFPolys.Add(FrontPoly); AllocatedFPolys.Add(BackPoly); for (int32 i = 0; i < nPolys; i++) { FPoly* Poly = PolyList[i]; switch (Poly->SplitWithPlane(Base, Normal, FrontPoly, BackPoly, 0)) { case SP_Coplanar: // UE_LOG(LogBSPOps, Log, TEXT("FilterBound: Got coplanar") ); FrontList[nFront++] = Poly; BackList[nBack++] = Poly; break; case SP_Front: FrontList[nFront++] = Poly; break; case SP_Back: BackList[nBack++] = Poly; break; case SP_Split: FrontList[nFront++] = FrontPoly; BackList[nBack++] = BackPoly; FrontPoly = new FPoly; BackPoly = new FPoly; // Keep track of allocations. AllocatedFPolys.Add(FrontPoly); AllocatedFPolys.Add(BackPoly); break; default: UE_LOG(LogBSPOps, Fatal, TEXT("FZoneFilter::FilterToLeaf: Unknown split code")); } } if (nFront && nBack) { // Add partitioner plane to front and back. FPoly InfiniteEdPoly = FBSPOps::BuildInfiniteFPoly(Model, iNode); InfiniteEdPoly.iBrushPoly = iNode; SplitPartitioner(Model, PolyList, FrontList, BackList, 0, nPolys, nFront, nBack, InfiniteEdPoly, AllocatedFPolys); } else { // if( !nFront ) UE_LOG(LogBSPOps, Log, TEXT("FilterBound: Empty fronthull") ); // if( !nBack ) UE_LOG(LogBSPOps, Log, TEXT("FilterBound: Empty backhull") ); } // Recursively update all our childrens' bounding volumes. if (nFront > 0) { if (Node.iFront != INDEX_NONE) FilterBound(Model, &Bound, Node.iFront, FrontList, nFront, Outside || Node.IsCsg()); else if (Outside || Node.IsCsg()) UpdateBoundWithPolys(Bound, FrontList, nFront); else UpdateConvolutionWithPolys(Model, iNode, FrontList, nFront); } if (nBack > 0) { if (Node.iBack != INDEX_NONE) FilterBound(Model, &Bound, Node.iBack, BackList, nBack, Outside && !Node.IsCsg()); else if (Outside && !Node.IsCsg()) UpdateBoundWithPolys(Bound, BackList, nBack); else UpdateConvolutionWithPolys(Model, iNode, BackList, nBack); } // Update parent bound to enclose this bound. if (ParentBound) *ParentBound += Bound; // Delete FPolys allocated above. We cannot use FMemStack::Get() for FPoly as the array data FPoly contains will be allocated in regular memory. for (int32 i = 0; i < AllocatedFPolys.Num(); i++) { FPoly* AllocatedFPoly = AllocatedFPolys[i]; delete AllocatedFPoly; } Mark.Pop(); } /*----------------------------------------------------------------------------- Bsp Splitting. -----------------------------------------------------------------------------*/ // // Find the best splitting polygon within a pool of polygons, and return its // index (into the PolyList array). // static FPoly* FindBestSplit( int32 NumPolys, FPoly** PolyList, FBSPOps::EBspOptimization Opt, int32 Balance, int32 InPortalBias) { check(NumPolys > 0); // No need to test if only one poly. if (NumPolys == 1) return PolyList[0]; FPoly *Poly, *Best = NULL; float Score, BestScore; int32 i, Index, j, Inc; int32 Splits, Front, Back, Coplanar, AllSemiSolids; // PortalBias -- added by Legend on 4/12/2000 float PortalBias = InPortalBias / 100.0f; Balance &= 0xFF; // keep only the low byte to recover "Balance" // UE_LOG(LogBSPOps, Log, TEXT("Balance=%d PortalBias=%f"), Balance, PortalBias ); if (Opt == FBSPOps::BSP_Optimal) Inc = 1; // Test lots of nodes. else if (Opt == FBSPOps::BSP_Good) Inc = FMath::Max(1, NumPolys / 20); // Test 20 nodes. else /* BSP_Lame */ Inc = FMath::Max(1, NumPolys / 4); // Test 4 nodes. // See if there are any non-semisolid polygons here. for (i = 0; i < NumPolys; i++) if (!(PolyList[i]->PolyFlags & PF_AddLast)) break; AllSemiSolids = (i >= NumPolys); // Search through all polygons in the pool and find: // A. The number of splits each poly would make. // B. The number of front and back nodes the polygon would create. // C. Number of coplanars. BestScore = 0; for (i = 0; i < NumPolys; i += Inc) { Splits = Front = Back = Coplanar = 0; Index = i - 1; do { Index++; Poly = PolyList[Index]; } while (Index < (i + Inc) && Index < NumPolys && ((Poly->PolyFlags & PF_AddLast) && !(Poly->PolyFlags & PF_Portal)) && !AllSemiSolids); if (Index >= i + Inc || Index >= NumPolys) continue; for (j = 0; j < NumPolys; j += Inc) if (j != Index) { FPoly* OtherPoly = PolyList[j]; switch (OtherPoly->SplitWithPlaneFast(FPlane(Poly->Vertices[0], Poly->Normal), NULL, NULL)) { case SP_Coplanar: Coplanar++; break; case SP_Front: Front++; break; case SP_Back: Back++; break; case SP_Split: // Disfavor splitting polys that are zone portals. if (!(OtherPoly->PolyFlags & PF_Portal)) Splits++; else Splits += 16; break; } } // added by Legend 1/31/1999 // Score optimization: minimize cuts vs. balance tree (as specified in BSP Rebuilder dialog) Score = (100.0 - float(Balance)) * Splits + float(Balance) * FMath::Abs(Front - Back); if (Poly->PolyFlags & PF_Portal) { // PortalBias -- added by Legend on 4/12/2000 // // PortalBias enables level designers to control the effect of Portals on the BSP. // This effect can range from 0.0 (ignore portals), to 1.0 (portals cut everything). // // In builds prior to this (since the 221 build dating back to 1/31/1999) the bias // has been 1.0 causing the portals to cut the BSP in ways that will potentially // degrade level performance, and increase the BSP complexity. // // By setting the bias to a value between 0.3 and 0.7 the positive effects of // the portals are preserved without giving them unreasonable priority in the BSP. // // Portals should be weighted high enough in the BSP to separate major parts of the // level from each other (pushing entire rooms down the branches of the BSP), but // should not be so high that portals cut through adjacent geometry in a way that // increases complexity of the room being (typically, accidentally) cut. // Score -= (100.0 - float(Balance)) * Splits * PortalBias; // ignore PortalBias of the split polys -- bias toward portal selection for cutting planes! } // UE_LOG(LogBSPOps, Log, " %4d: Score = %f (Front = %4d, Back = %4d, Splits = %4d, Flags = %08X)", Index, Score, Front, Back, Splits, Poly->PolyFlags ); //LEC if (Score < BestScore || !Best) { Best = Poly; BestScore = Score; } } check(Best); return Best; } // // Pick a splitter poly then split a pool of polygons into front and back polygons and // recurse. // // iParent = Parent Bsp node, or INDEX_NONE if this is the root node. // IsFront = 1 if this is the front node of iParent, 0 of back (undefined if iParent==INDEX_NONE) // void FBSPOps::SplitPolyList( UModel* Model, int32 iParent, ENodePlace NodePlace, int32 NumPolys, FPoly** PolyList, EBspOptimization Opt, int32 Balance, int32 PortalBias, int32 RebuildSimplePolys) { FMemMark Mark(FMemStack::Get()); // Keeping track of allocated FPoly structures to delete later on. TArray AllocatedFPolys; // To account for big EdPolys split up. int32 NumPolysToAlloc = NumPolys + 8 + NumPolys / 4; int32 NumFront = 0; FPoly** FrontList = new (FMemStack::Get(), NumPolysToAlloc) FPoly*; int32 NumBack = 0; FPoly** BackList = new (FMemStack::Get(), NumPolysToAlloc) FPoly*; FPoly* SplitPoly = FindBestSplit(NumPolys, PolyList, Opt, Balance, PortalBias); // Add the splitter poly to the Bsp with either a new BspSurf or an existing one. if (RebuildSimplePolys) { SplitPoly->iLinkSurf = Model->Surfs.Num(); } int32 iOurNode = bspAddNode(Model, iParent, NodePlace, 0, SplitPoly); int32 iPlaneNode = iOurNode; // Now divide all polygons in the pool into (A) polygons that are // in front of Poly, and (B) polygons that are in back of Poly. // Coplanar polys are inserted immediately, before recursing. // If any polygons are split by Poly, we ignrore the original poly, // split it into two polys, and add two new polys to the pool. FPoly* FrontEdPoly = new FPoly; FPoly* BackEdPoly = new FPoly; // Keep track of allocations. AllocatedFPolys.Add(FrontEdPoly); AllocatedFPolys.Add(BackEdPoly); for (int32 i = 0; i < NumPolys; i++) { FPoly* EdPoly = PolyList[i]; if (EdPoly == SplitPoly) { continue; } switch (EdPoly->SplitWithPlane(SplitPoly->Vertices[0], SplitPoly->Normal, FrontEdPoly, BackEdPoly, 0)) { case SP_Coplanar: if (RebuildSimplePolys) { EdPoly->iLinkSurf = Model->Surfs.Num() - 1; } iPlaneNode = bspAddNode(Model, iPlaneNode, NODE_Plane, 0, EdPoly); break; case SP_Front: FrontList[NumFront++] = PolyList[i]; break; case SP_Back: BackList[NumBack++] = PolyList[i]; break; case SP_Split: // Create front & back nodes. FrontList[NumFront++] = FrontEdPoly; BackList[NumBack++] = BackEdPoly; FrontEdPoly = new FPoly; BackEdPoly = new FPoly; // Keep track of allocations. AllocatedFPolys.Add(FrontEdPoly); AllocatedFPolys.Add(BackEdPoly); break; } } // Recursively split the front and back pools. if (NumFront > 0) SplitPolyList(Model, iOurNode, NODE_Front, NumFront, FrontList, Opt, Balance, PortalBias, RebuildSimplePolys); if (NumBack > 0) SplitPolyList(Model, iOurNode, NODE_Back, NumBack, BackList, Opt, Balance, PortalBias, RebuildSimplePolys); // Delete FPolys allocated above. We cannot use FMemStack::Get() for FPoly as the array data FPoly contains will be allocated in regular memory. for (int32 i = 0; i < AllocatedFPolys.Num(); i++) { FPoly* AllocatedFPoly = AllocatedFPolys[i]; delete AllocatedFPoly; } Mark.Pop(); } /** Prepare a moving brush. */ void FBSPOps::csgPrepMovingBrush(ABrush* Actor) { check(Actor); // UE_LOG(LogBSPOps, Log, TEXT("Preparing brush %s"), *Actor->GetName() ); // moved here so that we can easily debug when an actor has lost parts of its brush check(Actor->GetBrushComponent()); check(Actor->Brush); check(Actor->Brush->RootOutside); RebuildBrush(Actor->Brush); // Make sure simplified collision is up to date. Actor->GetBrushComponent()->BuildSimpleBrushCollision(); Actor->RebuildNavigationData(); } /** * Duplicates the specified brush and makes it into a CSG-able level brush. * @return The new brush, or NULL if the original was empty. */ void FBSPOps::csgCopyBrush(ABrush* Dest, ABrush* Src, uint32 PolyFlags, EObjectFlags ResFlags, bool bNeedsPrep, bool bCopyPosRotScale, bool bAllowEmpty) { check(Src); check(Src->GetBrushComponent()); check(Src->Brush); // Handle empty brush. if (!bAllowEmpty && !Src->Brush->Polys->Element.Num()) { Dest->Brush = NULL; Dest->GetBrushComponent()->Brush = NULL; return; } // Duplicate the brush and its polys. Dest->PolyFlags = PolyFlags; Dest->Brush = NewObject(Dest, NAME_None, ResFlags); Dest->Brush->Initialize(nullptr, Src->Brush->RootOutside); Dest->Brush->Polys = NewObject(Dest->Brush, NAME_None, ResFlags); Dest->Brush->Polys->Element = Src->Brush->Polys->Element; Dest->GetBrushComponent()->Brush = Dest->Brush; if (Src->BrushBuilder != nullptr) { Dest->BrushBuilder = DuplicateObject(Src->BrushBuilder, Dest); } // Update poly textures. for (int32 i = 0; i < Dest->Brush->Polys->Element.Num(); i++) { Dest->Brush->Polys->Element[i].iBrushPoly = INDEX_NONE; } // Copy positioning, and build bounding box. if (bCopyPosRotScale) { Dest->CopyPosRotScaleFrom(Src); } // If it's a moving brush, prep it. if (bNeedsPrep) { csgPrepMovingBrush(Dest); } } /** * Adds a brush to the list of CSG brushes in the level, using a CSG operation. * * @return A newly-created copy of the brush. */ ABrush* FBSPOps::csgAddOperation(ABrush* Actor, uint32 PolyFlags, EBrushType BrushType) { check(Actor); check(Actor->GetBrushComponent()); check(Actor->Brush); check(Actor->Brush->Polys); check(Actor->GetWorld()); // Can't do this if brush has no polys. if (!Actor->Brush->Polys->Element.Num()) return NULL; // Spawn a new actor for the brush. ABrush* Result = Actor->GetWorld()->SpawnBrush(); Result->SetNotForClientOrServer(); // Duplicate the brush. csgCopyBrush( Result, Actor, PolyFlags, RF_Transactional, 0, true); check(Result->Brush); if (Result->GetBrushBuilder()) { FActorLabelUtilities::SetActorLabelUnique(Result, FText::Format(NSLOCTEXT("BSPBrushOps", "BrushName", "{0} Brush"), FText::FromString(Result->GetBrushBuilder()->GetClass()->GetDescription())).ToString()); } // Assign the default material to the brush's polys. for (int32 i = 0; i < Result->Brush->Polys->Element.Num(); i++) { FPoly& CurrentPoly = Result->Brush->Polys->Element[i]; if (!CurrentPoly.Material) { CurrentPoly.Material = UMaterial::GetDefaultMaterial(MD_Surface); } } // Set add-info. Result->BrushType = BrushType; Result->ReregisterAllComponents(); return Result; } /** Add a new point to the model (preventing duplicates) and return its index. */ static int32 AddThing(TArray& Vectors, FVector& V, float Thresh, int32 Check) { if (Check) { // See if this is very close to an existing point/vector. for (int32 i = 0; i < Vectors.Num(); i++) { const FVector& TableVect = Vectors[i]; float Temp = (V.X - TableVect.X); if ((Temp > -Thresh) && (Temp < Thresh)) { Temp = (V.Y - TableVect.Y); if ((Temp > -Thresh) && (Temp < Thresh)) { Temp = (V.Z - TableVect.Z); if ((Temp > -Thresh) && (Temp < Thresh)) { // Found nearly-matching vector. return i; } } } } } return Vectors.Add(V); } /** Add a new vector to the model, merging near-duplicates, and return its index. */ int32 FBSPOps::bspAddVector(UModel* Model, FVector* V, bool Exact) { const float Thresh = Exact ? THRESH_NORMALS_ARE_SAME : THRESH_VECTORS_ARE_NEAR; if (FBspPointsGrid::GBspVectors) { // If a points grid has been built for quick vector lookup, use that instead of doing a linear search const int32 NextIndex = Model->Vectors.Num(); const int32 ReturnedIndex = FBspPointsGrid::GBspVectors->FindOrAddPoint(*V, NextIndex, Thresh); if (ReturnedIndex == NextIndex) { Model->Vectors.Add(*V); } return ReturnedIndex; } return AddThing( Model->Vectors, *V, Exact ? THRESH_NORMALS_ARE_SAME : THRESH_VECTORS_ARE_NEAR, 1); } /** Add a new point to the model, merging near-duplicates, and return its index. */ int32 FBSPOps::bspAddPoint(UModel* Model, FVector* V, bool Exact) { const float Thresh = Exact ? THRESH_POINTS_ARE_SAME : THRESH_POINTS_ARE_NEAR; if (FBspPointsGrid::GBspPoints) { // If a points grid has been built for quick point lookup, use that instead of doing a linear search const int32 NextIndex = Model->Points.Num(); // Always look for points with a low threshold; a generous threshold can result in 'leaks' in the BSP and unwanted polys being generated const int32 ReturnedIndex = FBspPointsGrid::GBspPoints->FindOrAddPoint(*V, NextIndex, THRESH_POINTS_ARE_SAME); if (ReturnedIndex == NextIndex) { Model->Points.Add(*V); } return ReturnedIndex; } // Try to find a match quickly from the Bsp. This finds all potential matches // except for any dissociated from nodes/surfaces during a rebuild. FVector Temp; int32 pVertex; float NearestDist = Model->FindNearestVertex(*V, Temp, Thresh, pVertex); if ((NearestDist >= 0.0) && (NearestDist <= Thresh)) { // Found an existing point. return pVertex; } else { // No match found; add it slowly to find duplicates. return AddThing(Model->Points, *V, Thresh, !GFastRebuild); } } /** * Builds Bsp from the editor polygon set (EdPolys) of a model. * * Opt = Bsp optimization, BSP_Lame (fast), BSP_Good (medium), BSP_Optimal (slow) * Balance = 0-100, 0=only worry about minimizing splits, 100=only balance tree. */ void FBSPOps::bspBuild(UModel* Model, enum EBspOptimization Opt, int32 Balance, int32 PortalBias, int32 RebuildSimplePolys, int32 iNode) { int32 OriginalPolys = Model->Polys->Element.Num(); // Empty the model's tables. if (RebuildSimplePolys == 1) { // Empty everything but polys. Model->EmptyModel(1, 0); } else if (RebuildSimplePolys == 0) { // Empty node vertices. for (int32 i = 0; i < Model->Nodes.Num(); i++) Model->Nodes[i].NumVertices = 0; // Refresh the Bsp. bspRefresh(Model, 1); // Empty nodes. Model->EmptyModel(0, 0); } if (Model->Polys->Element.Num()) { // Allocate polygon pool. FMemMark Mark(FMemStack::Get()); FPoly** PolyList = new (FMemStack::Get(), Model->Polys->Element.Num()) FPoly*; // Add all FPolys to active list. for (int32 i = 0; i < Model->Polys->Element.Num(); i++) if (Model->Polys->Element[i].Vertices.Num()) PolyList[i] = &Model->Polys->Element[i]; // Now split the entire Bsp by splitting the list of all polygons. SplitPolyList( Model, INDEX_NONE, NODE_Root, Model->Polys->Element.Num(), PolyList, Opt, Balance, PortalBias, RebuildSimplePolys); // Now build the bounding boxes for all nodes. if (RebuildSimplePolys == 0) { // Remove unreferenced things. bspRefresh(Model, 1); // Rebuild all bounding boxes. bspBuildBounds(Model); } Mark.Pop(); } // UE_LOG(LogBSPOps, Log, TEXT("bspBuild built %i convex polys into %i nodes"), OriginalPolys, Model->Nodes.Num() ); } /** * If the Bsp's point and vector tables are nearly full, reorder them and delete unused ones. */ void FBSPOps::bspRefresh(UModel* Model, bool NoRemapSurfs) { FMemStack& MemStack = FMemStack::Get(); FMemMark Mark(MemStack); int32 NumNodes = Model->Nodes.Num(); int32 NumSurfs = Model->Surfs.Num(); int32 NumVectors = Model->Vectors.Num(); int32 NumPoints = Model->Points.Num(); // Remove unreferenced Bsp surfs. int32* PolyRef; if (NoRemapSurfs) { PolyRef = NewZeroed(MemStack, NumSurfs); } else { PolyRef = NewOned(MemStack, NumSurfs); } int32* NodeRef = NewOned(MemStack, NumNodes); if (NumNodes > 0) { TagReferencedNodes(Model, NodeRef, PolyRef, 0); } // Remap Bsp surfs. { int32 n = 0; for (int32 i = 0; i < NumSurfs; i++) { if (PolyRef[i] != INDEX_NONE) { Model->Surfs[n] = Model->Surfs[i]; PolyRef[i] = n++; } } // UE_LOG(LogBSPOps, Log, TEXT("Polys: %i -> %i"), NumSurfs, n ); Model->Surfs.RemoveAt(n, NumSurfs - n); NumSurfs = n; } // Remap Bsp nodes. { int32 n = 0; for (int32 i = 0; i < NumNodes; i++) { if (NodeRef[i] != INDEX_NONE) { Model->Nodes[n] = Model->Nodes[i]; NodeRef[i] = n++; } } // UE_LOG(LogBSPOps, Log, TEXT("Nodes: %i -> %i"), NumNodes, n ); Model->Nodes.RemoveAt(n, NumNodes - n); NumNodes = n; } // Update Bsp nodes. for (int32 i = 0; i < NumNodes; i++) { FBspNode* Node = &Model->Nodes[i]; Node->iSurf = PolyRef[Node->iSurf]; if (Node->iFront != INDEX_NONE) Node->iFront = NodeRef[Node->iFront]; if (Node->iBack != INDEX_NONE) Node->iBack = NodeRef[Node->iBack]; if (Node->iPlane != INDEX_NONE) Node->iPlane = NodeRef[Node->iPlane]; } // Remove unreferenced points and vectors. int32* VectorRef = NewOned(MemStack, NumVectors); int32* PointRef = NewOned(MemStack, NumPoints); // Check Bsp surfs. TArray VertexRef; for (int32 i = 0; i < NumSurfs; i++) { FBspSurf* Surf = &Model->Surfs[i]; VectorRef[Surf->vNormal] = 0; VectorRef[Surf->vTextureU] = 0; VectorRef[Surf->vTextureV] = 0; PointRef[Surf->pBase] = 0; } // Check Bsp nodes. for (int32 i = 0; i < NumNodes; i++) { // Tag all points used by nodes. FBspNode* Node = &Model->Nodes[i]; FVert* VertPool = &Model->Verts[Node->iVertPool]; for (int B = 0; B < Node->NumVertices; B++) { PointRef[VertPool->pVertex] = 0; VertPool++; } } // Remap points. { int32 n = 0; for (int32 i = 0; i < NumPoints; i++) if (PointRef[i] != INDEX_NONE) { Model->Points[n] = Model->Points[i]; PointRef[i] = n++; } // UE_LOG(LogBSPOps, Log, TEXT("Points: %i -> %i"), NumPoints, n ); Model->Points.RemoveAt(n, NumPoints - n); NumPoints = n; } // Remap vectors. { int32 n = 0; for (int32 i = 0; i < NumVectors; i++) if (VectorRef[i] != INDEX_NONE) { Model->Vectors[n] = Model->Vectors[i]; VectorRef[i] = n++; } // UE_LOG(LogBSPOps, Log, TEXT("Vectors: %i -> %i"), NumVectors, n ); Model->Vectors.RemoveAt(n, NumVectors - n); NumVectors = n; } // Update Bsp surfs. for (int32 i = 0; i < NumSurfs; i++) { FBspSurf* Surf = &Model->Surfs[i]; Surf->vNormal = VectorRef[Surf->vNormal]; Surf->vTextureU = VectorRef[Surf->vTextureU]; Surf->vTextureV = VectorRef[Surf->vTextureV]; Surf->pBase = PointRef[Surf->pBase]; } // Update Bsp nodes. for (int32 i = 0; i < NumNodes; i++) { FBspNode* Node = &Model->Nodes[i]; FVert* VertPool = &Model->Verts[Node->iVertPool]; for (int B = 0; B < Node->NumVertices; B++) { VertPool->pVertex = PointRef[VertPool->pVertex]; VertPool++; } } // Shrink the objects. Model->ShrinkModel(); Mark.Pop(); } // Build bounding volumes for all Bsp nodes. The bounding volume of the node // completely encloses the "outside" space occupied by the nodes. Note that // this is not the same as representing the bounding volume of all of the // polygons within the node. // // We start with a practically-infinite cube and filter it down the Bsp, // whittling it away until all of its convex volume fragments land in leaves. void FBSPOps::bspBuildBounds(UModel* Model) { if (Model->Nodes.Num() == 0) return; FPoly Polys[6], *PolyList[6]; for (int32 i = 0; i < 6; i++) { PolyList[i] = &Polys[i]; PolyList[i]->Init(); PolyList[i]->iBrushPoly = INDEX_NONE; } new (Polys[0].Vertices) FVector(-HALF_WORLD_MAX, -HALF_WORLD_MAX, HALF_WORLD_MAX); new (Polys[0].Vertices) FVector(HALF_WORLD_MAX, -HALF_WORLD_MAX, HALF_WORLD_MAX); new (Polys[0].Vertices) FVector(HALF_WORLD_MAX, HALF_WORLD_MAX, HALF_WORLD_MAX); new (Polys[0].Vertices) FVector(-HALF_WORLD_MAX, HALF_WORLD_MAX, HALF_WORLD_MAX); Polys[0].Normal = FVector(0.000000, 0.000000, 1.000000); Polys[0].Base = Polys[0].Vertices[0]; new (Polys[1].Vertices) FVector(-HALF_WORLD_MAX, HALF_WORLD_MAX, -HALF_WORLD_MAX); new (Polys[1].Vertices) FVector(HALF_WORLD_MAX, HALF_WORLD_MAX, -HALF_WORLD_MAX); new (Polys[1].Vertices) FVector(HALF_WORLD_MAX, -HALF_WORLD_MAX, -HALF_WORLD_MAX); new (Polys[1].Vertices) FVector(-HALF_WORLD_MAX, -HALF_WORLD_MAX, -HALF_WORLD_MAX); Polys[1].Normal = FVector(0.000000, 0.000000, -1.000000); Polys[1].Base = Polys[1].Vertices[0]; new (Polys[2].Vertices) FVector(-HALF_WORLD_MAX, HALF_WORLD_MAX, -HALF_WORLD_MAX); new (Polys[2].Vertices) FVector(-HALF_WORLD_MAX, HALF_WORLD_MAX, HALF_WORLD_MAX); new (Polys[2].Vertices) FVector(HALF_WORLD_MAX, HALF_WORLD_MAX, HALF_WORLD_MAX); new (Polys[2].Vertices) FVector(HALF_WORLD_MAX, HALF_WORLD_MAX, -HALF_WORLD_MAX); Polys[2].Normal = FVector(0.000000, 1.000000, 0.000000); Polys[2].Base = Polys[2].Vertices[0]; new (Polys[3].Vertices) FVector(HALF_WORLD_MAX, -HALF_WORLD_MAX, -HALF_WORLD_MAX); new (Polys[3].Vertices) FVector(HALF_WORLD_MAX, -HALF_WORLD_MAX, HALF_WORLD_MAX); new (Polys[3].Vertices) FVector(-HALF_WORLD_MAX, -HALF_WORLD_MAX, HALF_WORLD_MAX); new (Polys[3].Vertices) FVector(-HALF_WORLD_MAX, -HALF_WORLD_MAX, -HALF_WORLD_MAX); Polys[3].Normal = FVector(0.000000, -1.000000, 0.000000); Polys[3].Base = Polys[3].Vertices[0]; new (Polys[4].Vertices) FVector(HALF_WORLD_MAX, HALF_WORLD_MAX, -HALF_WORLD_MAX); new (Polys[4].Vertices) FVector(HALF_WORLD_MAX, HALF_WORLD_MAX, HALF_WORLD_MAX); new (Polys[4].Vertices) FVector(HALF_WORLD_MAX, -HALF_WORLD_MAX, HALF_WORLD_MAX); new (Polys[4].Vertices) FVector(HALF_WORLD_MAX, -HALF_WORLD_MAX, -HALF_WORLD_MAX); Polys[4].Normal = FVector(1.000000, 0.000000, 0.000000); Polys[4].Base = Polys[4].Vertices[0]; new (Polys[5].Vertices) FVector(-HALF_WORLD_MAX, -HALF_WORLD_MAX, -HALF_WORLD_MAX); new (Polys[5].Vertices) FVector(-HALF_WORLD_MAX, -HALF_WORLD_MAX, HALF_WORLD_MAX); new (Polys[5].Vertices) FVector(-HALF_WORLD_MAX, HALF_WORLD_MAX, HALF_WORLD_MAX); new (Polys[5].Vertices) FVector(-HALF_WORLD_MAX, HALF_WORLD_MAX, -HALF_WORLD_MAX); Polys[5].Normal = FVector(-1.000000, 0.000000, 0.000000); Polys[5].Base = Polys[5].Vertices[0]; // Empty hulls. Model->LeafHulls.Empty(); for (int32 i = 0; i < Model->Nodes.Num(); i++) Model->Nodes[i].iCollisionBound = INDEX_NONE; FilterBound(Model, NULL, 0, PolyList, 6, Model->RootOutside); // UE_LOG(LogBSPOps, Log, TEXT("bspBuildBounds: Generated %i hulls"), Model->LeafHulls.Num() ); } /** * Validate a brush, and set iLinks on all EdPolys to index of the * first identical EdPoly in the list, or its index if it's the first. * Not transactional. */ void FBSPOps::bspValidateBrush(UModel* Brush, bool ForceValidate, bool DoStatusUpdate) { check(Brush != nullptr); Brush->Modify(); if (ForceValidate || !Brush->Linked) { Brush->Linked = 1; for (int32 i = 0; i < Brush->Polys->Element.Num(); i++) { Brush->Polys->Element[i].iLink = i; } int32 n = 0; for (int32 i = 0; i < Brush->Polys->Element.Num(); i++) { FPoly* EdPoly = &Brush->Polys->Element[i]; if (EdPoly->iLink == i) { for (int32 j = i + 1; j < Brush->Polys->Element.Num(); j++) { FPoly* OtherPoly = &Brush->Polys->Element[j]; if (OtherPoly->iLink == j && OtherPoly->Material == EdPoly->Material && OtherPoly->TextureU == EdPoly->TextureU && OtherPoly->TextureV == EdPoly->TextureV && OtherPoly->PolyFlags == EdPoly->PolyFlags && (OtherPoly->Normal | EdPoly->Normal) > 0.9999) { float Dist = FVector::PointPlaneDist(OtherPoly->Vertices[0], EdPoly->Vertices[0], EdPoly->Normal); if (Dist > -0.001 && Dist < 0.001) { OtherPoly->iLink = i; n++; } } } } } // UE_LOG(LogBSPOps, Log, TEXT("BspValidateBrush linked %i of %i polys"), n, Brush->Polys->Element.Num() ); } // Build bounds. Brush->BuildBound(); } void FBSPOps::bspUnlinkPolys(UModel* Brush) { Brush->Modify(); Brush->Linked = 1; for (int32 i = 0; i < Brush->Polys->Element.Num(); i++) { Brush->Polys->Element[i].iLink = i; } } // Add an editor polygon to the Bsp, and also stick a reference to it // in the editor polygon's BspNodes list. If the editor polygon has more sides // than the Bsp will allow, split it up into several sub-polygons. // // Returns: Index to newly-created node of Bsp. If several nodes were created because // of split polys, returns the parent (highest one up in the Bsp). int32 FBSPOps::bspAddNode(UModel* Model, int32 iParent, ENodePlace NodePlace, uint32 NodeFlags, FPoly* EdPoly) { if (NodePlace == NODE_Plane) { // Make sure coplanars are added at the end of the coplanar list so that // we don't insert NF_IsNew nodes with non NF_IsNew coplanar children. while (Model->Nodes[iParent].iPlane != INDEX_NONE) { iParent = Model->Nodes[iParent].iPlane; } } FBspSurf* Surf = NULL; if (EdPoly->iLinkSurf == Model->Surfs.Num()) { int32 NewIndex = Model->Surfs.AddZeroed(); Surf = &Model->Surfs[NewIndex]; // This node has a new polygon being added by bspBrushCSG; must set its properties here. Surf->pBase = bspAddPoint(Model, &EdPoly->Base, 1); Surf->vNormal = bspAddVector(Model, &EdPoly->Normal, 1); Surf->vTextureU = bspAddVector(Model, &EdPoly->TextureU, 0); Surf->vTextureV = bspAddVector(Model, &EdPoly->TextureV, 0); Surf->Material = EdPoly->Material; Surf->Actor = NULL; Surf->PolyFlags = EdPoly->PolyFlags & ~PF_NoAddToBSP; Surf->LightMapScale = EdPoly->LightMapScale; // Find the LightmassPrimitiveSettings in the UModel... int32 FoundLightmassIndex = INDEX_NONE; if (Model->LightmassSettings.Find(EdPoly->LightmassSettings, FoundLightmassIndex) == false) { FoundLightmassIndex = Model->LightmassSettings.Add(EdPoly->LightmassSettings); } Surf->iLightmassIndex = FoundLightmassIndex; Surf->Actor = EdPoly->Actor; Surf->iBrushPoly = EdPoly->iBrushPoly; if (EdPoly->Actor) { Surf->bHiddenEdTemporary = EdPoly->Actor->IsTemporarilyHiddenInEditor(); Surf->bHiddenEdLevel = EdPoly->Actor->bHiddenEdLevel; Surf->bHiddenEdLayer = EdPoly->Actor->bHiddenEdLayer; } Surf->Plane = FPlane(EdPoly->Vertices[0], EdPoly->Normal); } else { check(EdPoly->iLinkSurf != INDEX_NONE); check(EdPoly->iLinkSurf < Model->Surfs.Num()); Surf = &Model->Surfs[EdPoly->iLinkSurf]; } // Set NodeFlags. if (Surf->PolyFlags & PF_NotSolid) NodeFlags |= NF_NotCsg; if (Surf->PolyFlags & (PF_Invisible | PF_Portal)) NodeFlags |= NF_NotVisBlocking; if (EdPoly->Vertices.Num() > FBspNode::MAX_NODE_VERTICES) { // Split up into two coplanar sub-polygons (one with MAX_NODE_VERTICES vertices and // one with all the remaining vertices) and recursively add them. // EdPoly1 is just the first MAX_NODE_VERTICES from EdPoly. FMemMark Mark(FMemStack::Get()); FPoly* EdPoly1 = new FPoly; *EdPoly1 = *EdPoly; EdPoly1->Vertices.RemoveAt(FBspNode::MAX_NODE_VERTICES, EdPoly->Vertices.Num() - FBspNode::MAX_NODE_VERTICES); // EdPoly2 is the first vertex from EdPoly, and the last EdPoly->Vertices.Num() - MAX_NODE_VERTICES + 1. FPoly* EdPoly2 = new FPoly; *EdPoly2 = *EdPoly; EdPoly2->Vertices.RemoveAt(1, FBspNode::MAX_NODE_VERTICES - 2); int32 iNode = bspAddNode(Model, iParent, NodePlace, NodeFlags, EdPoly1); // Add this poly first. bspAddNode(Model, iNode, NODE_Plane, NodeFlags, EdPoly2); // Then add other (may be bigger). delete EdPoly1; delete EdPoly2; Mark.Pop(); return iNode; // Return coplanar "parent" node (not coplanar child) } else { // Add node. int32 iNode = Model->Nodes.AddZeroed(); FBspNode& Node = Model->Nodes[iNode]; // Tell transaction tracking system that parent is about to be modified. FBspNode* Parent = NULL; if (NodePlace != NODE_Root) Parent = &Model->Nodes[iParent]; // Set node properties. Node.iSurf = EdPoly->iLinkSurf; Node.NodeFlags = NodeFlags; Node.iCollisionBound = INDEX_NONE; Node.Plane = FPlane(EdPoly->Vertices[0], EdPoly->Normal); Node.iVertPool = Model->Verts.AddUninitialized(EdPoly->Vertices.Num()); Node.iFront = INDEX_NONE; Node.iBack = INDEX_NONE; Node.iPlane = INDEX_NONE; if (NodePlace == NODE_Root) { Node.iLeaf[0] = INDEX_NONE; Node.iLeaf[1] = INDEX_NONE; Node.iZone[0] = 0; Node.iZone[1] = 0; } else if (NodePlace == NODE_Front || NodePlace == NODE_Back) { int32 ZoneFront = NodePlace == NODE_Front; Node.iLeaf[0] = Parent->iLeaf[ZoneFront]; Node.iLeaf[1] = Parent->iLeaf[ZoneFront]; Node.iZone[0] = Parent->iZone[ZoneFront]; Node.iZone[1] = Parent->iZone[ZoneFront]; } else { int32 IsFlipped = (Node.Plane | Parent->Plane) < 0.0; Node.iLeaf[0] = Parent->iLeaf[IsFlipped]; Node.iLeaf[1] = Parent->iLeaf[1 - IsFlipped]; Node.iZone[0] = Parent->iZone[IsFlipped]; Node.iZone[1] = Parent->iZone[1 - IsFlipped]; } // Link parent to this node. if (NodePlace == NODE_Front) { Parent->iFront = iNode; } else if (NodePlace == NODE_Back) { Parent->iBack = iNode; } else if (NodePlace == NODE_Plane) { Parent->iPlane = iNode; } // Add all points to point table, merging nearly-overlapping polygon points // with other points in the poly to prevent criscrossing vertices from // being generated. // Must maintain Node->NumVertices on the fly so that bspAddPoint is always // called with the Bsp in a clean state. Node.NumVertices = 0; FVert* VertPool = &Model->Verts[Node.iVertPool]; for (uint8 i = 0; i < EdPoly->Vertices.Num(); i++) { int32 pVertex = bspAddPoint(Model, &EdPoly->Vertices[i], 0); if (Node.NumVertices == 0 || VertPool[Node.NumVertices - 1].pVertex != pVertex) { VertPool[Node.NumVertices].iSide = INDEX_NONE; VertPool[Node.NumVertices].pVertex = pVertex; Node.NumVertices++; } } if (Node.NumVertices >= 2 && VertPool[0].pVertex == VertPool[Node.NumVertices - 1].pVertex) { Node.NumVertices--; } if (Node.NumVertices < 3) { GErrors++; // UE_LOG(LogBSPOps, Warning, TEXT("bspAddNode: Infinitesimal polygon %i (%i)"), Node.NumVertices, EdPoly->Vertices.Num() ); Node.NumVertices = 0; } return iNode; } } /** * Rebuild some brush internals */ void FBSPOps::RebuildBrush(UModel* Brush) { Brush->Modify(); Brush->EmptyModel(1, 0); // Build bounding box. Brush->BuildBound(); // Build BSP for the brush. bspBuild(Brush, BSP_Good, 15, 70, 1, 0); bspRefresh(Brush, 1); bspBuildBounds(Brush); } /** * Rotates the specified brush's vertices. */ void FBSPOps::RotateBrushVerts(ABrush* Brush, const FRotator& Rotation, bool bClearComponents) { if (Brush->GetBrushComponent()->Brush && Brush->GetBrushComponent()->Brush->Polys) { for (int32 poly = 0; poly < Brush->GetBrushComponent()->Brush->Polys->Element.Num(); poly++) { FPoly* Poly = &(Brush->GetBrushComponent()->Brush->Polys->Element[poly]); // Rotate the vertices. const FRotationMatrix RotMatrix(Rotation); for (int32 vertex = 0; vertex < Poly->Vertices.Num(); vertex++) { Poly->Vertices[vertex] = Brush->GetPivotOffset() + RotMatrix.TransformVector(Poly->Vertices[vertex] - Brush->GetPivotOffset()); } Poly->Base = Brush->GetPivotOffset() + RotMatrix.TransformVector(Poly->Base - Brush->GetPivotOffset()); // Rotate the texture vectors. Poly->TextureU = RotMatrix.TransformVector(Poly->TextureU); Poly->TextureV = RotMatrix.TransformVector(Poly->TextureV); // Recalc the normal for the poly. Poly->Normal = FVector::ZeroVector; Poly->Finalize(Brush, 0); } Brush->GetBrushComponent()->Brush->BuildBound(); if (!Brush->IsStaticBrush()) { csgPrepMovingBrush(Brush); } if (bClearComponents) { Brush->ReregisterAllComponents(); } } } void FBSPOps::HandleVolumeShapeChanged(AVolume& Volume) { // The default physics volume doesn't have an associated UModel, so we need to handle that case gracefully. if (Volume.Brush) { FBSPOps::csgPrepMovingBrush(&Volume); } } void FBspPointsGrid::Clear(int32 InitialSize) { GridMap.Empty(InitialSize); } // Given a grid index in one axis, a real position on the grid and a threshold radius, // return either: // - the additional grid index it can overlap in that axis, or // - the original grid index if there is no overlap. static FORCEINLINE int32 GetAdjacentIndexIfOverlapping(int32 GridIndex, float GridPos, float GridThreshold) { if (GridPos - GridIndex < GridThreshold) { return GridIndex - 1; } else if (1.0f - (GridPos - GridIndex) < GridThreshold) { return GridIndex + 1; } else { return GridIndex; } } int32 FBspPointsGrid::FindOrAddPoint(const FVector& Point, int32 Index, float PointThreshold) { // Offset applied to the grid coordinates so aligned vertices (the normal case) don't overlap several grid items (taking into account the threshold) const float GridOffset = 0.12345f; const float AdjustedPointX = Point.X - GridOffset; const float AdjustedPointY = Point.Y - GridOffset; const float AdjustedPointZ = Point.Z - GridOffset; const float GridX = AdjustedPointX * OneOverGranularity; const float GridY = AdjustedPointY * OneOverGranularity; const float GridZ = AdjustedPointZ * OneOverGranularity; // Get the grid indices corresponding to the point coordinates const int32 GridIndexX = FMath::FloorToInt(GridX); const int32 GridIndexY = FMath::FloorToInt(GridY); const int32 GridIndexZ = FMath::FloorToInt(GridZ); // Find grid item in map FBspPointsGridItem& GridItem = GridMap.FindOrAdd(FBspPointsKey(GridIndexX, GridIndexY, GridIndexZ)); // Iterate through grid item points and return a point if it's close to the threshold const float PointThresholdSquared = PointThreshold * PointThreshold; for (const FBspIndexedPoint& IndexedPoint: GridItem.IndexedPoints) { if (FVector::DistSquared(IndexedPoint.Point, Point) <= PointThresholdSquared) { return IndexedPoint.Index; } } // Otherwise, the point is new: add it to the grid item. GridItem.IndexedPoints.Emplace(Point, Index); // The grid has a maximum threshold of a certain radius. If the point is near the edge of a grid cube, it may overlap into other items. // Add it to all grid items it can be seen from. const float GridThreshold = Threshold * OneOverGranularity; const int32 NeighbourX = GetAdjacentIndexIfOverlapping(GridIndexX, GridX, GridThreshold); const int32 NeighbourY = GetAdjacentIndexIfOverlapping(GridIndexY, GridY, GridThreshold); const int32 NeighbourZ = GetAdjacentIndexIfOverlapping(GridIndexZ, GridZ, GridThreshold); const bool bOverlapsInX = (NeighbourX != GridIndexX); const bool bOverlapsInY = (NeighbourY != GridIndexY); const bool bOverlapsInZ = (NeighbourZ != GridIndexZ); if (bOverlapsInX) { GridMap.FindOrAdd(FBspPointsKey(NeighbourX, GridIndexY, GridIndexZ)).IndexedPoints.Emplace(Point, Index); if (bOverlapsInY) { GridMap.FindOrAdd(FBspPointsKey(NeighbourX, NeighbourY, GridIndexZ)).IndexedPoints.Emplace(Point, Index); if (bOverlapsInZ) { GridMap.FindOrAdd(FBspPointsKey(NeighbourX, NeighbourY, NeighbourZ)).IndexedPoints.Emplace(Point, Index); } } else if (bOverlapsInZ) { GridMap.FindOrAdd(FBspPointsKey(NeighbourX, GridIndexY, NeighbourZ)).IndexedPoints.Emplace(Point, Index); } } else { if (bOverlapsInY) { GridMap.FindOrAdd(FBspPointsKey(GridIndexX, NeighbourY, GridIndexZ)).IndexedPoints.Emplace(Point, Index); if (bOverlapsInZ) { GridMap.FindOrAdd(FBspPointsKey(GridIndexX, NeighbourY, NeighbourZ)).IndexedPoints.Emplace(Point, Index); } } else if (bOverlapsInZ) { GridMap.FindOrAdd(FBspPointsKey(GridIndexX, GridIndexY, NeighbourZ)).IndexedPoints.Emplace(Point, Index); } } return Index; }