Unreal Engine Bounding 26 DOP, Implements discrete oriented polytopes (DOP for short). Is an extension of bounding box, box has 6 directions and represents 6 distances, 26 DOP has 26 directions and represents 26 distances in those directions . Has similar API as UE4's FSphere, FBox and FBoxSphereBounds.

Bounding26Dop.cpp

#include "Bounding26Dop.h"

#include "Math/UnrealMathUtility.h"
#include "Containers/UnrealString.h"
#include "Logging/LogMacros.h"
#include "Engine/Polys.h"
#include "DrawDebugHelpers.h"
#include "GenericPlatform/GenericPlatformMath.h"
#include "Async/ParallelFor.h"
#include "Serialization/StructuredArchiveFormatter.h"
#include "Serialization/StructuredArchive.h"
#include "Engine/StaticMesh.h"

enum class ESplitPolygonResult
{
	Coplanar = 0, // Polygon wasn't split, but is coplanar with plane
	Front = 1, // Polygon wasn't split, but is entirely in front of plane
	Back = 2, // Polygon wasn't split, but is entirely in back of plane
	Split = 3, // Polygon was split into two new editor polygons
};

// Based on UE4's FPoly::SplitWithPlaneFast() from Polygon.cpp
template<typename TElementType, typename TAllocator>
ESplitPolygonResult SplitPolygonByPlane(const TArray<TElementType, TAllocator>& InPoly, const FPlane& Plane, TArray<TElementType, TAllocator>& OutFrontPoly)
{
	FMemMark MemMark(FMemStack::Get());

	enum class EPlaneClassification : uint8
	{
		V_FRONT = 0,
		V_BACK = 1
	};

	EPlaneClassification Status, PrevStatus;
	EPlaneClassification* VertStatus = new(FMemStack::Get()) EPlaneClassification[InPoly.Num()];
	bool Front = false, Back = false;

	EPlaneClassification* StatusPtr = &VertStatus[0];
	for (int32 i = 0; i < InPoly.Num(); i++)
	{
		const float Dist = Plane.PlaneDot(InPoly[i]);
		if (Dist >= 0.f)
		{
			*StatusPtr++ = EPlaneClassification::V_FRONT;
			if (Dist > +THRESH_SPLIT_POLY_WITH_PLANE)
				Front = true;
		}
		else
		{
			*StatusPtr++ = EPlaneClassification::V_BACK;
			if (Dist < -THRESH_SPLIT_POLY_WITH_PLANE)
				Back = true;
		}
	}
	ESplitPolygonResult Result;
	if (!Front)
	{
		if (Back) Result = ESplitPolygonResult::Back;
		else       Result = ESplitPolygonResult::Coplanar;
	}
	else if (!Back)
	{
		Result = ESplitPolygonResult::Front;
	}
	else
	{
		// Some vertices are front and some are at back of plane, this means this polygon will be split by plane
		Result = ESplitPolygonResult::Split;

		const FVector* V = InPoly.GetData();
		const FVector* W = V + InPoly.Num() - 1;
		StatusPtr = &VertStatus[0];
		PrevStatus = VertStatus[InPoly.Num() - 1];

		for (int32 i = 0; i < InPoly.Num(); i++)
		{
			Status = *StatusPtr++;
			if (Status != PrevStatus) // Is line crossing plane ?
			{
				const FVector& Intersection = FMath::LinePlaneIntersection(*W, *V, Plane);
				new(OutFrontPoly) FVector(Intersection);
				if (PrevStatus != EPlaneClassification::V_FRONT)
				{
					new(OutFrontPoly) FVector(*V);
				}
			}
			else if (Status == EPlaneClassification::V_FRONT)
			{
				new(OutFrontPoly) FVector(*V);
			}

			PrevStatus = Status;
			W = V++;
		}
	}

	MemMark.Pop();

	return Result;
}

// Based on UE4's GenerateKDopAsSimpleCollision() from GeomFitUtils.cpp
void FBounding26Dop::CalculatePolygons(TArray<FBounding26Dop::FPolygon>& OutPolygons) const
{
	for (uint8 i = 0; i < DirectionsCounts; ++i)
	{
		FBounding26Dop::FPolygon* polygon = new(OutPolygons) FBounding26Dop::FPolygon();
		{
			FVector base, axisX, axisY;
			base = FKDopDirections::KDopDir26[i] * Distances[i];
			FKDopDirections::KDopDir26[i].FindBestAxisVectors(axisX, axisY);
			new(polygon->Vertices) FVector(base + axisX * HALF_WORLD_MAX + axisY * HALF_WORLD_MAX);
			new(polygon->Vertices) FVector(base + axisX * HALF_WORLD_MAX - axisY * HALF_WORLD_MAX);
			new(polygon->Vertices) FVector(base - axisX * HALF_WORLD_MAX - axisY * HALF_WORLD_MAX);
			new(polygon->Vertices) FVector(base - axisX * HALF_WORLD_MAX + axisY * HALF_WORLD_MAX);
		}

		for (uint8 j = 0; j < DirectionsCounts; ++j)
		{
			if (i != j)
			{
				const FPlane splitPlane(FKDopDirections::KDopDir26[j] * Distances[j], -FKDopDirections::KDopDir26[j]);
				FBounding26Dop::FPolygon Front;
				switch (SplitPolygonByPlane(polygon->Vertices, splitPlane, Front.Vertices))
				{
				case ESplitPolygonResult::Back:
					polygon->Vertices.Empty();
					break;
				case ESplitPolygonResult::Split:
					*polygon = Front;
					break;
					//case ESplitType::Front:
					//case ESplitType::Coplanar:
				default:
					break;
				}

				if (polygon->Vertices.Num() < 1)
				{
					break;
				}
			}
		}

		if (polygon->Vertices.Num() < 3)
		{
			// If poly resulted in no verts, remove from array
			OutPolygons.RemoveAt(OutPolygons.Num() - 1);
		}
	}
}

// Based on UE4's GenerateKDopAsSimpleCollision() from GeomFitUtils.cpp
void FBounding26Dop::CalculateVertices(TArray<FVector>& OutVertices) const
{
	TArray<FVector> array1;
	TArray<FVector> array2;
	TArray<FVector>* workingPolygon = &array1;
	TArray<FVector>* splitResultFront = &array2;
	for (uint8 i = 0; i < DirectionsCounts; ++i)
	{
		{
			workingPolygon->Reset();
			FVector base, axisX, axisY;
			base = FKDopDirections::KDopDir26[i] * Distances[i];
			FKDopDirections::KDopDir26[i].FindBestAxisVectors(axisX, axisY);
			new(*workingPolygon) FVector(base + axisX * HALF_WORLD_MAX + axisY * HALF_WORLD_MAX);
			new(*workingPolygon) FVector(base + axisX * HALF_WORLD_MAX - axisY * HALF_WORLD_MAX);
			new(*workingPolygon) FVector(base - axisX * HALF_WORLD_MAX - axisY * HALF_WORLD_MAX);
			new(*workingPolygon) FVector(base - axisX * HALF_WORLD_MAX + axisY * HALF_WORLD_MAX);
		}

		for (uint8 j = 0; j < DirectionsCounts; ++j)
		{
			if (i != j)
			{
				const FPlane splitPlane(FKDopDirections::KDopDir26[j] * Distances[j], -FKDopDirections::KDopDir26[j]);
				switch (SplitPolygonByPlane(*workingPolygon, splitPlane, *splitResultFront))
				{
				case ESplitPolygonResult::Back:
					workingPolygon->Reset();
					break;
				case ESplitPolygonResult::Split:
					::Swap(workingPolygon, splitResultFront);
					splitResultFront->Reset();
					break;
					//case ESplitType::Front:
					//case ESplitType::Coplanar:
				default:
					break;
				}

				if (workingPolygon->Num() < 3)
				{
					break;
				}
			}
		}

		if (workingPolygon->Num() >= 3)
		{
			OutVertices.Append(*workingPolygon);
		}
	}
}

void operator<<(FStructuredArchive::FSlot Slot, FBounding26Dop& Self)
{
	FStructuredArchive::FRecord Record = Slot.EnterRecord();
	Record << SA_VALUE(TEXT("IsValid"), Self.IsValid);

	int32 num = Self.DirectionsCounts;
	FStructuredArchiveArray Array = Record.EnterArray(SA_FIELD_NAME(TEXT("Distances")), num);
	for (int32 j = 0; j < Self.DirectionsCounts; j++)
	{
		FStructuredArchiveRecord RowRecord = Array.EnterElement().EnterRecord();
		RowRecord << SA_VALUE(TEXT("Distance"), Self.Distances[j]);
	}
}

bool FBounding26Dop::Serialize(FStructuredArchive::FSlot Slot)
{
	Slot << *this;
	return true;
}

FArchive& operator<<(FArchive& Ar, FBounding26Dop& Self)
{
	if (Ar.IsLoading())
	{
		uint8 serializedByte = 0;
		Ar.SerializeBits(&serializedByte, 1);
		Self.IsValid = serializedByte > 0;
	}
	else
	{
		uint8 serializeByte = Self.IsValid;
		Ar.SerializeBits(&serializeByte, 1);
	}

	for (uint8 j = 0; j < Self.DirectionsCounts; ++j)
	{
		Ar << Self.Distances[j];
	}

	return Ar;
}

bool FBounding26Dop::Serialize(FArchive& Ar)
{
	Ar << *this;
	return true;
}

void FBounding26Dop::EncompassPointsInternal(const TArray<FVector>& InPoints)
{
	if (InPoints.Num() == 0) return;

	int32 CurrentIndex = InPoints.Num() - 1;

	if (!IsValid)
	{
		EncompassPointInternal(InPoints[CurrentIndex]);
		--CurrentIndex;
	}

	if (InPoints.Num() < 10)
	{
		while (CurrentIndex >= 0)
		{
			for (uint8 j = 0; j < DirectionsCounts; ++j)
			{
				const float dist = FVector::DotProduct(InPoints[CurrentIndex], FKDopDirections::KDopDir26[j]);
				Distances[j] = FMath::Max(dist, Distances[j]);
			}

			--CurrentIndex;
		}
	}
	else
	{
		ParallelFor(DirectionsCounts, [&, CurrentIndex](int32 j) mutable
		{
			while (CurrentIndex >= 0)
			{
				const float dist = FVector::DotProduct(InPoints[CurrentIndex], FKDopDirections::KDopDir26[j]);
				Distances[j] = FMath::Max(dist, Distances[j]);
				--CurrentIndex;
			}
		});
	}
}

void FBounding26Dop::Encompass(UStaticMesh* StaticMesh)
{
	if (
		ensure(::IsValid(StaticMesh)) &&
		ensure(StaticMesh->bAllowCPUAccess) &&
		ensure(StaticMesh->RenderData.IsValid())
	) {
		Encompass(StaticMesh->RenderData.Get());
	}
}

void FBounding26Dop::Encompass(FStaticMeshRenderData* RenderData) 
{
	if (
		ensure(RenderData != nullptr) &&
		ensure(RenderData->LODResources.IsValidIndex(0))
	) {
		Encompass(RenderData->LODResources[0]);
	}
}

void FBounding26Dop::Encompass(const FStaticMeshLODResources& StaticMeshLODResources) 
{
	for (uint32 i = 0; i < StaticMeshLODResources.VertexBuffers.PositionVertexBuffer.GetNumVertices(); ++i)
	{
		const FVector& vertex = StaticMeshLODResources.VertexBuffers.PositionVertexBuffer.VertexPosition(i);
		Encompass(vertex);
	}
}

void FBounding26Dop::DrawDebugLines(UWorld* World, const FMatrix& LocalToWorld, FColor const& Color, bool bPersistentLines /*= false*/, float LifeTime /*= -1.f*/, uint8 DepthPriority /*= 0*/, float Thickness /*= 0.f*/)
{
	TArray<FPolygon> polygons;
	CalculatePolygons(polygons);
	for (const FPolygon& poly : polygons)
	{
		for (int32 i = 0; i < poly.Vertices.Num(); ++i)
		{
			FVector start = poly.Vertices[i];
			FVector end = poly.Vertices[(i + 1) % poly.Vertices.Num()];
			start = LocalToWorld.TransformPosition(start);
			end = LocalToWorld.TransformPosition(end);
			DrawDebugLine(World, start, end, Color, bPersistentLines, LifeTime, DepthPriority, Thickness);
		}
	}

	ExecuteTests();
}

void FBounding26Dop::ExecuteTests()
{
	TSet<FVector> allPoints;

	TArray<FPolygon> polygons;
	CalculatePolygons(polygons);
	for (const FPolygon& poly : polygons)
	{
		if (ensure(poly.Vertices.Num() >= 2))
		{
			allPoints.Append(poly.Vertices);
		}
	}

	TArray<FVector> vertices;
	CalculateVertices(vertices);
	for (int32 i = 0; i < vertices.Num(); ++i)
	{
		FVector v = vertices[i];
		ensure(allPoints.Contains(v));
	}

	FBox b1 = CalculateBoundingBox();
	FBox b2 = CalculateBoundingBox(FMatrix::Identity);
	ensure((b1.Max - b2.Max).Size() < 0.1f);
	ensure((b1.Min - b2.Min).Size() < 0.1f);
}

IMPLEMENT_STRUCT(Bounding26Dop);

Bounding26Dop.h

#pragma once

#include "CoreMinimal.h"
#include "CoreTypes.h"
#include "Math/Vector.h"
#include "Math/Sphere.h"
#include "Math/Box.h"
#include "UObject/Class.h"

#if CPP


namespace FKDopDirections
{
	constexpr const float RCP_SQRT2 = 0.70710678118654752440084436210485f;
	constexpr const float RCP_SQRT3 = 0.57735026918962576450914878050196f;

	const FVector KDopDir10X[10] =
	{
		FVector(1.f, 0.f, 0.f),
		FVector(-1.f, 0.f, 0.f),
		FVector(0.f, 1.f, 0.f),
		FVector(0.f,-1.f, 0.f),
		FVector(0.f, 0.f, 1.f),
		FVector(0.f, 0.f,-1.f),
		FVector(0.f, RCP_SQRT2,  RCP_SQRT2),
		FVector(0.f,-RCP_SQRT2, -RCP_SQRT2),
		FVector(0.f, RCP_SQRT2, -RCP_SQRT2),
		FVector(0.f,-RCP_SQRT2,  RCP_SQRT2)
	};

	const FVector KDopDir10Y[10] =
	{
		FVector(1.f, 0.f, 0.f),
		FVector(-1.f, 0.f, 0.f),
		FVector(0.f, 1.f, 0.f),
		FVector(0.f,-1.f, 0.f),
		FVector(0.f, 0.f, 1.f),
		FVector(0.f, 0.f,-1.f),
		FVector(RCP_SQRT2, 0.f,  RCP_SQRT2),
		FVector(-RCP_SQRT2, 0.f, -RCP_SQRT2),
		FVector(RCP_SQRT2, 0.f, -RCP_SQRT2),
		FVector(-RCP_SQRT2, 0.f,  RCP_SQRT2)
	};

	const FVector KDopDir10Z[10] =
	{
		FVector(1.f, 0.f, 0.f),
		FVector(-1.f, 0.f, 0.f),
		FVector(0.f, 1.f, 0.f),
		FVector(0.f,-1.f, 0.f),
		FVector(0.f, 0.f, 1.f),
		FVector(0.f, 0.f,-1.f),
		FVector(RCP_SQRT2,  RCP_SQRT2, 0.f),
		FVector(-RCP_SQRT2, -RCP_SQRT2, 0.f),
		FVector(RCP_SQRT2, -RCP_SQRT2, 0.f),
		FVector(-RCP_SQRT2,  RCP_SQRT2, 0.f)
	};

	const FVector KDopDir18[18] =
	{
		FVector(1.f, 0.f, 0.f),
		FVector(-1.f, 0.f, 0.f),
		FVector(0.f, 1.f, 0.f),
		FVector(0.f,-1.f, 0.f),
		FVector(0.f, 0.f, 1.f),
		FVector(0.f, 0.f,-1.f),
		FVector(0.f, RCP_SQRT2,  RCP_SQRT2),
		FVector(0.f,-RCP_SQRT2, -RCP_SQRT2),
		FVector(0.f, RCP_SQRT2, -RCP_SQRT2),
		FVector(0.f,-RCP_SQRT2,  RCP_SQRT2),
		FVector(RCP_SQRT2, 0.f,  RCP_SQRT2),
		FVector(-RCP_SQRT2, 0.f, -RCP_SQRT2),
		FVector(RCP_SQRT2, 0.f, -RCP_SQRT2),
		FVector(-RCP_SQRT2, 0.f,  RCP_SQRT2),
		FVector(RCP_SQRT2,  RCP_SQRT2, 0.f),
		FVector(-RCP_SQRT2, -RCP_SQRT2, 0.f),
		FVector(RCP_SQRT2, -RCP_SQRT2, 0.f),
		FVector(-RCP_SQRT2,  RCP_SQRT2, 0.f)
	};

	const FVector KDopDir26[26] =
	{
		FVector(1.f, 0.f, 0.f),
		FVector(-1.f, 0.f, 0.f),
		FVector(0.f, 1.f, 0.f),
		FVector(0.f,-1.f, 0.f),
		FVector(0.f, 0.f, 1.f),
		FVector(0.f, 0.f,-1.f),
		FVector(0.f, RCP_SQRT2,  RCP_SQRT2),
		FVector(0.f,-RCP_SQRT2, -RCP_SQRT2),
		FVector(0.f, RCP_SQRT2, -RCP_SQRT2),
		FVector(0.f,-RCP_SQRT2,  RCP_SQRT2),
		FVector(RCP_SQRT2, 0.f,  RCP_SQRT2),
		FVector(-RCP_SQRT2, 0.f, -RCP_SQRT2),
		FVector(RCP_SQRT2, 0.f, -RCP_SQRT2),
		FVector(-RCP_SQRT2, 0.f,  RCP_SQRT2),
		FVector(RCP_SQRT2,  RCP_SQRT2, 0.f),
		FVector(-RCP_SQRT2, -RCP_SQRT2, 0.f),
		FVector(RCP_SQRT2, -RCP_SQRT2, 0.f),
		FVector(-RCP_SQRT2,  RCP_SQRT2, 0.f),
		FVector(RCP_SQRT3,  RCP_SQRT3,  RCP_SQRT3),
		FVector(RCP_SQRT3,  RCP_SQRT3, -RCP_SQRT3),
		FVector(RCP_SQRT3, -RCP_SQRT3,  RCP_SQRT3),
		FVector(RCP_SQRT3, -RCP_SQRT3, -RCP_SQRT3),
		FVector(-RCP_SQRT3,  RCP_SQRT3,  RCP_SQRT3),
		FVector(-RCP_SQRT3,  RCP_SQRT3, -RCP_SQRT3),
		FVector(-RCP_SQRT3, -RCP_SQRT3,  RCP_SQRT3),
		FVector(-RCP_SQRT3, -RCP_SQRT3, -RCP_SQRT3),
	};
};

/**
 * Implements discrete oriented polytopes (DOP for short)
 * Is an extension of bounding box, box has 6 sides and represents 6 distances, 26 DOP has 26 sides and represents 26 distances
 * Has similar API as UE4's FSphere, FBox and FBoxSphereBounds
 */
struct UTILS_API FBounding26Dop
{

public:

	/** Holds a flag indicating whether this 26 DOP is valid. */
	bool IsValid;

	/** K count, K number */
	static constexpr const uint8 DirectionsCounts = 26;
	
	/** Distances from center to side for each direction. */
	float Distances[DirectionsCounts];

public:

	/** 
	 * Default constructor (no initialization)
	 */ 
	FBounding26Dop() { }

	/**
	 * Creates and initializes a new bounding volume
	 * Initializes to default values
	 * Marks this volume as invalid
	 * 
	 * @param EForceInit Force Init Enum.
	 */
	explicit FBounding26Dop(EForceInit)
	{
		Init();
	}

	/**
	 * Creates and initializes a new 26 DOP from the given set of points.
	 *
	 * @param Points Array of Points to create for the bounding volume.
	 * @param Count The number of points.
	 */
	FBounding26Dop(const FVector* Points, int32 Count)
	{
		Init();
		Encompass(TArray<FVector>(Points, Count));
	}

	/**
	 * Creates and initializes a new 26 DOP from an array of points.
	 *
	 * @param Points Array of Points to create for the bounding volume.
	 */
	FBounding26Dop(const TArray<FVector>& Points)
	{
		Init();
		Encompass(Points);
	}

	/**
	 * Initializes to default values
	 * Marks this volume as invalid
	 */
	void Init()
	{
		for (int32 j = 0; j < DirectionsCounts; j++)
		{
			Distances[j] = TNumericLimits<float>::Min();
		}

		IsValid = false;
	}

	/**
	 * Initializes to default values
	 * Marks this volume as invalid
	 */
	void Reset()
	{
		Init();
	}

public: // calculate bounding volumes or vertices from this

	struct FPolygon
	{
		typedef TArray<FVector, TInlineAllocator<5>> VerticesArrayType;
		VerticesArrayType Vertices;

		void Reset()
		{
			Vertices.Reset();
		}
	};

	/**
	 * Calculates polygons that represent sides of this bounding volume
	 */ 
	void CalculatePolygons(TArray<FPolygon>& OutPolygons) const;
	
	/**
	 * Calculates most extreme vertices (points)
	 * May return duplicates, some vertices may come from more polygons
	 * Faster than CalculatePolygons
	 */
	void CalculateVertices(TArray<FVector>& OutVertices) const;

	/**
	 * Calculates this bounding volume transformed by provided matrix
	 */
	FBounding26Dop TransformBy(const FMatrix& AdjustPoints) const
	{
		TArray<FVector> points;
		CalculateVertices(points);
		for (int32 i = 0; i < points.Num(); ++i)
		{
			points[i] = AdjustPoints.TransformPosition(points[i]);
		}

		return FBounding26Dop(points);
	}

	/**
	 * Calculates a bounding box that encapsulates this bounding volume
	 */
	FBox CalculateBoundingBox() const
	{
		if (!IsValid)
		{
			FBox result(ForceInitToZero);
			result.IsValid = false;
			return MoveTemp(result);
		}

		//[0] FVector(1.f, 0.f, 0.f),
		//[1] FVector(-1.f, 0.f, 0.f),
		//[2] FVector(0.f, 1.f, 0.f),
		//[3] FVector(0.f,-1.f, 0.f),
		//[4] FVector(0.f, 0.f, 1.f),
		//[5] FVector(0.f, 0.f,-1.f),

		return FBox(
			FVector(-Distances[1], -Distances[3], -Distances[5]), // min
			FVector(Distances[0], Distances[2], Distances[4]) // max
		);
	}

	/**
	 * Calculates a bounding box that encapsulates this bounding volume transformed by provided matrix
	 */
	FBox CalculateBoundingBox(const FMatrix& AdjustPoints) const
	{
		if (!IsValid)
		{
			FBox result(ForceInitToZero);
			result.IsValid = false;
			return MoveTemp(result);
		}

		TArray<FVector> points;
		CalculateVertices(points);
		for (int32 i = 0; i < points.Num(); ++i)
		{
			points[i] = AdjustPoints.TransformPosition(points[i]);
		}

		return FBox(points);
	}

	/**
	 * Calculates a bounding sphere that encapsulates this bounding volume
	 */
	FSphere CalculateBoundingSphere() const
	{
		if (!IsValid)
		{
			return FSphere(ForceInitToZero);
		}

		const FBox box = CalculateBoundingBox();
		FSphere sphere((box.Min + box.Max) / 2, 0);

		TArray<FVector> points;
		CalculateVertices(points);
		for (int32 i = 0; i < points.Num(); ++i)
		{
			const float Dist = FVector::DistSquared(points[i], sphere.Center);
			if (Dist > sphere.W)
			{
				sphere.W = Dist;
			}
		}

		sphere.W = FMath::Sqrt(sphere.W) * 1.001f;
		return MoveTemp(sphere);
	}
	
	/**
	 * Calculates a bounding sphere that encapsulates this bounding volume transformed by provided matrix
	 */
	FSphere CalculateBoundingSphere(const FMatrix& AdjustPoints) const
	{
		if (!IsValid)
		{
			return FSphere(ForceInitToZero);
		}

		TArray<FVector> points;
		CalculateVertices(points);
		
		FBox box;
		box.IsValid = false;
		for (int32 i = 0; i < points.Num(); ++i)
		{
			points[i] = AdjustPoints.TransformPosition(points[i]);
			box += points[i];
		}

		FSphere sphere((box.Min + box.Max) / 2, 0);
		for (int32 i = 0; i < points.Num(); ++i)
		{
			const float Dist = FVector::DistSquared(points[i], sphere.Center);
			if (Dist > sphere.W)
			{
				sphere.W = Dist;
			}
		}

		sphere.W = FMath::Sqrt(sphere.W) * 1.001f;
		return MoveTemp(sphere);
	}

public: // equality

	/**
	 * Check whether two bounding 26 dops are the same within specified tolerance.
	 *
	 * @param Other The other bounding 26 dop.
	 * @param Tolerance Error Tolerance.
	 * @return true if bounding 26 dops are equal within specified tolerance, otherwise false.
	 */
	bool Equals(const FBounding26Dop& Other, float Tolerance = KINDA_SMALL_NUMBER) const
	{
		for (uint8 j = 0; j < DirectionsCounts; ++j)
		{
			if (FMath::Abs(Distances[j] - Other.Distances[j]) > Tolerance)
			{
				return false;
			}
		}

		return true;
	}

	/**
	 * Compares two bounding 26 dops for equality.
	 *
	 * @return true if the bounding 26 dops are equal, false otherwise.
	 */
	bool operator==(const FBounding26Dop& Other) const
	{
		return Equals(Other);
	}

	/**
	 * Compares two bounding 26 dops for inequality.
	 *
	 * @return true if the bounding 26 dops are not equal, false otherwise.
	 */
	bool operator!=(const FBounding26Dop& Other) const
	{
		return !Equals(Other);
	}

public: // Serializers

	/**
	 * Serializes the given 26 DOP from or into the specified archive.
	 *
	 * @param Ar The archive to serialize from or into.
	 * @param Other The 26 DOP to serialize.
	 * @return The archive.
	 */
	friend FArchive& operator<<(FArchive& Ar, FBounding26Dop& Self);
	bool Serialize(FArchive& Ar);

	friend void operator<<(FStructuredArchive::FSlot Slot, FBounding26Dop& Self);
	bool Serialize(FStructuredArchive::FSlot Slot);
	
private:

	/**
	 * For private use only, does not set IsValid
	 */
	void EncompassPointsInternal(const TArray<FVector>& InPoints);

	/** 
	 * For private use only, does not set IsValid
	 */
	void EncompassPointInternal(const FVector& Point)
	{
		if (LIKELY(IsValid))
		{
			for (uint8 j = 0; j < DirectionsCounts; ++j)
			{
				const float dist = FVector::DotProduct(Point, FKDopDirections::KDopDir26[j]);
				Distances[j] = FMath::Max(dist, Distances[j]);
			}
		}
		else
		{
			for (uint8 j = 0; j < DirectionsCounts; ++j)
			{
				const float dist = FVector::DotProduct(Point, FKDopDirections::KDopDir26[j]);
				Distances[j] = dist;
			}

			IsValid = true;
		}
	}

public: // encompass various other types and optionally transform them by FMatrix beforehand

	void Encompass(const FVector& Point)
	{
		EncompassPointInternal(Point);
	}

	void Encompass(const FSphere& Other)
	{
		for (uint8 i = 0; i < DirectionsCounts; ++i)
		{
			const float dist = Other.W + FVector::DotProduct(Other.Center, FKDopDirections::KDopDir26[i]);
			Distances[i] = IsValid ? FMath::Max(dist, Distances[i]) : dist;
		}

		IsValid = true;
	}

	void Encompass(const FSphere& Other, const FMatrix& AdjustPoints)
	{
		const FVector center = AdjustPoints.TransformPosition(Other.Center);
		const float radius = Other.W * AdjustPoints.GetScaleVector().GetMax();

		for (uint8 i = 0; i < DirectionsCounts; ++i)
		{
			const float dist = radius + FVector::DotProduct(center, FKDopDirections::KDopDir26[i]);
			Distances[i] = IsValid ? FMath::Max(dist, Distances[i]) : dist;
		}

		IsValid = true;
	}

	void Encompass(const FBox& Other)
	{
		if (!Other.IsValid) return;

		const FVector boxCorners[8] =
		{
			Other.Max,
			FVector(Other.Max.X, Other.Max.Y, Other.Min.Z),
			FVector(Other.Max.X, Other.Min.Y, Other.Max.Z),
			FVector(Other.Max.X, Other.Min.Y, Other.Min.Z),
			FVector(Other.Min.X, Other.Max.Y, Other.Max.Z),
			FVector(Other.Min.X, Other.Max.Y, Other.Min.Z),
			FVector(Other.Min.X, Other.Min.Y, Other.Max.Z),
			Other.Min,
		};

		for (uint8 i = 0; i < 8; ++i)
		{
			EncompassPointInternal(boxCorners[i]);
		}
	}

	void Encompass(const FBox& Other, const FMatrix& AdjustPoints)
	{
		if (!Other.IsValid) return;

		const FVector boxCorners[8] =
		{
			Other.Max,
			FVector(Other.Max.X, Other.Max.Y, Other.Min.Z),
			FVector(Other.Max.X, Other.Min.Y, Other.Max.Z),
			FVector(Other.Max.X, Other.Min.Y, Other.Min.Z),
			FVector(Other.Min.X, Other.Max.Y, Other.Max.Z),
			FVector(Other.Min.X, Other.Max.Y, Other.Min.Z),
			FVector(Other.Min.X, Other.Min.Y, Other.Max.Z),
			Other.Min,
		};

		for (uint8 i = 0; i < 8; ++i)
		{
			EncompassPointInternal(AdjustPoints.TransformPosition(boxCorners[i]));
		}
	}

	void Encompass(const FBoxSphereBounds& Other)
	{
		const FVector boxCorners[8] =
		{
			Other.BoxExtent,
			FVector(Other.BoxExtent.X, Other.BoxExtent.Y, -Other.BoxExtent.Z),
			FVector(Other.BoxExtent.X, -Other.BoxExtent.Y, Other.BoxExtent.Z),
			FVector(Other.BoxExtent.X, -Other.BoxExtent.Y, -Other.BoxExtent.Z),
			FVector(-Other.BoxExtent.X, Other.BoxExtent.Y, Other.BoxExtent.Z),
			FVector(-Other.BoxExtent.X, Other.BoxExtent.Y, -Other.BoxExtent.Z),
			FVector(-Other.BoxExtent.X, -Other.BoxExtent.Y, Other.BoxExtent.Z),
			-Other.BoxExtent,
		};

		for (uint8 i = 0; i < 8; ++i)
		{
			EncompassPointInternal(Other.Origin + boxCorners[i]);
		}
	}

	void Encompass(const FBoxSphereBounds& Other, const FMatrix& AdjustPoints)
	{
		const FVector boxCorners[8] =
		{
			Other.BoxExtent,
			FVector(Other.BoxExtent.X, Other.BoxExtent.Y, -Other.BoxExtent.Z),
			FVector(Other.BoxExtent.X, -Other.BoxExtent.Y, Other.BoxExtent.Z),
			FVector(Other.BoxExtent.X, -Other.BoxExtent.Y, -Other.BoxExtent.Z),
			FVector(-Other.BoxExtent.X, Other.BoxExtent.Y, Other.BoxExtent.Z),
			FVector(-Other.BoxExtent.X, Other.BoxExtent.Y, -Other.BoxExtent.Z),
			FVector(-Other.BoxExtent.X, -Other.BoxExtent.Y, Other.BoxExtent.Z),
			-Other.BoxExtent,
		};

		for (uint8 i = 0; i < 8; ++i)
		{
			EncompassPointInternal(AdjustPoints.TransformPosition(Other.Origin + boxCorners[i]));
		}
	}

	void Encompass(const FBounding26Dop& Other)
	{
		if (!Other.IsValid) return;

		for (uint8 i = 0; i < DirectionsCounts; ++i)
		{
			Distances[i] = IsValid ? FMath::Max(Distances[i], Other.Distances[i]) : Other.Distances[i];
		}

		IsValid = true;
	}

	void Encompass(const FBounding26Dop& Other, const FMatrix& AdjustPoints)
	{
		if (!Other.IsValid) return;

		TArray<FVector> points;
		Other.CalculateVertices(points);

		for (int32 i = 0; i < points.Num(); ++i)
		{
			points[i] = AdjustPoints.TransformPosition(points[i]);
		}

		EncompassPointsInternal(points);
	}

	void Encompass(const TArray<FVector>& InPoints)
	{
		if (InPoints.Num() == 0) return;

		EncompassPointsInternal(InPoints);
	}

public: // encompass mesh

	void Encompass(class UStaticMesh* StaticMesh);
	void Encompass(class FStaticMeshRenderData* RenderData);
	void Encompass(const struct FStaticMeshLODResources& StaticMeshLODResources);

public: // convenience += operators

	FBounding26Dop& operator+=(const FVector& Other)
	{
		Encompass(Other);
		return *this;
	}
	
	FBounding26Dop& operator+=(const FSphere& Other)
	{
		Encompass(Other);
		return *this;
	}

	FBounding26Dop& operator+=(const FBox& Other)
	{
		Encompass(Other);
		return *this;
	}

	FBounding26Dop& operator+=(const FBoxSphereBounds& Other)
	{
		Encompass(Other);
		return *this;
	}

	FBounding26Dop& operator+=(const FBounding26Dop& Other)
	{
		Encompass(Other);
		return *this;
	}

	FBounding26Dop& operator+=(const TArray<FVector>& Other)
	{
		Encompass(Other);
		return *this;
	}

	FBounding26Dop& operator+=(UStaticMesh* Other)
	{
		Encompass(Other);
		return *this;
	}

	FBounding26Dop& operator+=(FStaticMeshRenderData* Other)
	{
		Encompass(Other);
		return *this;
	}

	FBounding26Dop& operator+=(const FStaticMeshLODResources& Other)
	{
		Encompass(Other);
		return *this;
	}

public: // convenience + operators

	FBounding26Dop operator+(const FVector& Other)
	{
		FBounding26Dop result(*this);
		result.Encompass(Other);
		return result;
	}

	FBounding26Dop operator+(const FSphere& Other)
	{
		FBounding26Dop result(*this);
		result.Encompass(Other);
		return result;
	}

	FBounding26Dop operator+(const FBox& Other)
	{
		FBounding26Dop result(*this);
		result.Encompass(Other);
		return result;
	}

	FBounding26Dop operator+(const FBoxSphereBounds& Other)
	{
		FBounding26Dop result(*this);
		result.Encompass(Other);
		return result;
	}

	FBounding26Dop operator+(const FBounding26Dop& Other)
	{
		FBounding26Dop result(*this);
		result.Encompass(Other);
		return result;
	}

	FBounding26Dop operator+(const TArray<FVector>& Other)
	{
		FBounding26Dop result(*this);
		result.Encompass(Other);
		return result;
	}

	FBounding26Dop operator+(UStaticMesh* Other)
	{
		FBounding26Dop result(*this);
		result.Encompass(Other);
		return result;
	}

	FBounding26Dop operator+(FStaticMeshRenderData* Other)
	{
		FBounding26Dop result(*this);
		result.Encompass(Other);
		return result;
	}

	FBounding26Dop operator+(const FStaticMeshLODResources& Other)
	{
		FBounding26Dop result(*this);
		result.Encompass(Other);
		return result;
	}

public: // debug

	void DrawDebugLines(UWorld* World, const FMatrix& LocalToWorld, FColor const& Color, bool bPersistentLines = false, float LifeTime = -1.f, uint8 DepthPriority = 0, float Thickness = 0.f);
	
	void ExecuteTests();

};


#else


USTRUCT(immutable, noexport, BlueprintType)
struct FBounding26Dop
{
	UPROPERTY(EditAnywhere, BlueprintReadWrite, SaveGame)
	bool IsValid;
	UPROPERTY(EditAnywhere, BlueprintReadWrite, SaveGame)
	float D0;
	UPROPERTY(EditAnywhere, BlueprintReadWrite, SaveGame)
	float D1;
	UPROPERTY(EditAnywhere, BlueprintReadWrite, SaveGame)
	float D2;
	UPROPERTY(EditAnywhere, BlueprintReadWrite, SaveGame)
	float D3;
	UPROPERTY(EditAnywhere, BlueprintReadWrite, SaveGame)
	float D4;
	UPROPERTY(EditAnywhere, BlueprintReadWrite, SaveGame)
	float D5;
	UPROPERTY(EditAnywhere, BlueprintReadWrite, SaveGame)
	float D6;
	UPROPERTY(EditAnywhere, BlueprintReadWrite, SaveGame)
	float D7;
	UPROPERTY(EditAnywhere, BlueprintReadWrite, SaveGame)
	float D8;
	UPROPERTY(EditAnywhere, BlueprintReadWrite, SaveGame)
	float D9;
	UPROPERTY(EditAnywhere, BlueprintReadWrite, SaveGame)
	float D10;
	UPROPERTY(EditAnywhere, BlueprintReadWrite, SaveGame)
	float D11;
	UPROPERTY(EditAnywhere, BlueprintReadWrite, SaveGame)
	float D12;
	UPROPERTY(EditAnywhere, BlueprintReadWrite, SaveGame)
	float D13;
	UPROPERTY(EditAnywhere, BlueprintReadWrite, SaveGame)
	float D14;
	UPROPERTY(EditAnywhere, BlueprintReadWrite, SaveGame)
	float D15;
	UPROPERTY(EditAnywhere, BlueprintReadWrite, SaveGame)
	float D16;
	UPROPERTY(EditAnywhere, BlueprintReadWrite, SaveGame)
	float D17;
	UPROPERTY(EditAnywhere, BlueprintReadWrite, SaveGame)
	float D18;
	UPROPERTY(EditAnywhere, BlueprintReadWrite, SaveGame)
	float D19;
	UPROPERTY(EditAnywhere, BlueprintReadWrite, SaveGame)
	float D20;
	UPROPERTY(EditAnywhere, BlueprintReadWrite, SaveGame)
	float D21;
	UPROPERTY(EditAnywhere, BlueprintReadWrite, SaveGame)
	float D22;
	UPROPERTY(EditAnywhere, BlueprintReadWrite, SaveGame)
	float D23;
	UPROPERTY(EditAnywhere, BlueprintReadWrite, SaveGame)
	float D24;
	UPROPERTY(EditAnywhere, BlueprintReadWrite, SaveGame)
	float D25;
};


#endif


struct FBounding26Dop;
template<> struct TBaseStructure<FBounding26Dop>
{
	COREUOBJECT_API static UScriptStruct* Get();
};

template<>
struct TStructOpsTypeTraits<FBounding26Dop> : public TStructOpsTypeTraitsBase2<FBounding26Dop>
{
	enum 
	{
		WithIdenticalViaEquality = true, // struct can be compared via its operator==.  This should be mutually exclusive with WithIdentical.
		WithNoInitConstructor = true, // struct has a constructor which takes an EForceInit parameter which will force the constructor to perform initialization, where the default constructor performs 'uninitialization'.
		WithZeroConstructor = true, // struct can be constructed as a valid object by filling its memory footprint with zeroes.
		WithStructuredSerializer = true, // struct has a Serialize function for serializing its state to an FStructuredArchive.
		WithSerializer = true, // struct has a Serialize function for serializing its state to an FArchive.
	};
};