Как я могу оптимизировать свою логику движения AABB (используя AABBSWEEP + RaycastBlocks) в воксельном двигателе, чтобы ⇐ C++

[Anonymous]

Я строю игру на основе вокселей и использую компонент движения на основе AABB. Основная функция aabbsweep вызывает мою функцию RaycastBlocks несколько раз в тройном вложенном цикле, чтобы собрать блоки для проверки столкновений. По словам моего Profiler, он занимает ~ 70% игры. Развертка AABB используется для применения скорости к коллайдеру моей сущности, а затем изменить его в качестве ответа на столкновение, чтобы произойти скольжение. Моя цель - снизить использование процессора при сохранении точности столкновения. MAX_TRIES в raycastblocks - это просто защита от бесконечных циклов, если что -то пойдет не так. Существуют ли известные методы для более эффективных проверок на столкновениях вокселей (например, алгоритмы обхода вокселей, такие как аманатиды и WOO, пространственное разделение или иерархии ограничивающего объема)? Где я могу кэшировать результаты или уменьшить количество вызовов? Любые советы по минимизации вставки тяжелых наборов или тройных вложенных петлей особенно полезны. Я предоставил заполнителю включить для краткости. Любая обратная связь по реорганизации кода, улучшению алгоритма, или лучшие передовые практики для столкновения на основе вокселей.

Код: Выделить всё

bool CJABGWorld::AABBSweep(SHitResult& result, const SAABB_CollisionShape& shape,
const EngineMath::SVector3f& position,
const EngineMath::SVector3f& offset,
const SCollisionChannelTracker& channels)
{
// Profile the entire function
CProfiler::ScopedSection entireSweepSection(g_profiler, "CJABGWorld::AABBSweep", false); //62% of the entire tick

EngineMath::SVector3f min = position + shape.Pivot - shape.Size;
EngineMath::SVector3f max = position + shape.Pivot + shape.Size;

// 1) Gather possible blocks
std::unordered_set possible_blocks;
possible_blocks.reserve(100);
{
CProfiler::ScopedSection gatherBlocksSection(g_profiler, "CJABGWorld::AABBSweep::GatherBlocks", false); //21% of the entire tick

// Precompute integer bounds just once
const int xMin = static_cast(std::floor(min.x)) - 1;
const int xMax = static_cast(std::ceil(max.x))  + 1;
const int yMin = static_cast(std::floor(min.y)) - 1;
const int yMax = static_cast(std::ceil(max.y))  + 1;
const int zMin = static_cast(std::floor(min.z)) - 1;
const int zMax = static_cast(std::ceil(max.z))  + 1;

// (Optional) Pre-reserve if you can guess an upper bound
// You won't know exactly how many will be inserted,
// but picking something big reduces rehashes:
// possible_blocks.reserve((xMax - xMin + 1) *
//                        (yMax - yMin + 1) *
//                        (zMax - zMin + 1) * someFactor);

for (int x = xMin; x GetChunk(pos.first.y);

if (!chunk || !part)
{
collision_shape = &normal_box;
}
else
{
const SBlockInfo& info = chunk->GetVoxelComponent()->GetBlock(pos.second.x, pos.second.y, pos.second.z);
const CBlock* block_pointer = info.GetBlock();
if(channels.ContainsChannel((int)block_pointer->GetCollisionChannel()))
collision_shape = block_pointer->GetCollisionShape(&info);
}

if (collision_shape)
{
any_collision |= CollisionHelper::ResolveDynamicSweepForAABB(*collision_shape, block, shape, position, new_offset);
if (glm::length(new_offset) < 1e-5f)
break;
}
}
}

if(!any_collision)
return false;

// 4) Build the SHitResult
result.Normal = (new_offset - offset) / glm::abs(offset);
for (int i = 0; i < 3; ++i)
result.Normal[i] = glm::isnan(result.Normal[i]) ? 0.0f : result.Normal[i];

float magnitude = glm::length(result.Normal);
result.Position = position + new_offset;
result.Delta = 1.0f - magnitude;
result.Normal /= (magnitude >  0.0f ? magnitude : 1.0f);

return true;
}

struct SHitResult
{
EngineMath::SVector3f Position;
EngineMath::SVector3f Normal;
float Delta;
float HitFarDelta;
class CNode* HitNode;
};

struct SAABB_CollisionShape
{
SAABB_CollisionShape(const EngineMath::SVector3f& min, const EngineMath::SVector3f& max, bool change_internal_variables = false)
{
if(change_internal_variables)
{
Pivot = min;
Size = max;
return;
}
Pivot = (min + max) * 0.5f;
Size = (max - min) * 0.5f;
}

SAABB_CollisionShape()
{
Pivot = EngineMath::SVector3f(0);
Size = EngineMath::SVector3f(0);
}

EngineMath::SVector3f Pivot;
EngineMath::SVector3f Size;
};

void CJABGWorld::RayCastBlocks(const EngineMath::SVector3f& linetrace_position,
const EngineMath::SVector3f& linetrace_offset,
std::unordered_set& blocks) const
{
EngineMath::SVector3i mapPos;
EngineMath::SVector3f direction;
EngineMath::SVector3f delta;
float maxLenght;
EngineMath::SVector3i step;
EngineMath::SVector3f distance;
LineTracePrep(linetrace_position, linetrace_offset, mapPos, direction, delta, maxLenght, step, distance);

float lenght = 0;
int max_tries = 5000;
while (lenght < maxLenght && max_tries >= 0)
{
blocks.insert(mapPos);
// pick next axis
if (distance.x < distance.y && distance.x < distance.z)
{
mapPos.x += step.x;
lenght = distance.x;
distance.x += delta.x;
}
else if (distance.y < distance.z)
{
mapPos.y += step.y;
lenght = distance.y;
distance.y += delta.y;
}
else
{
mapPos.z += step.z;
lenght = distance.z;
distance.z += delta.z;
}
--max_tries;
}
}
#include "CollisionHelper.h"

#include 
#include 
#include 
#include 

#include "Engine/CollisionLogic/3DCollision/ColliderEntity/CAABBColliderEntity.h"

bool CollisionHelper::LinetraceAgainstAABB(SHitResult& result, const SAABB_CollisionShape& shape,
const EngineMath::SVector3f& aabb_position, const EngineMath::SVector3f& linetrace_position,
const EngineMath::SVector3f& linetrace_offset, int calls)
{
constexpr float epsilon2 = 1e-4f;

const EngineMath::SVector3f aabbMin = aabb_position + shape.Pivot - shape.Size;
const EngineMath::SVector3f aabbMax = aabb_position + shape.Pivot + shape.Size;

EngineMath::SVector3f NearUndiv = aabbMax - linetrace_position;
EngineMath::SVector3f FarUndiv = aabbMin - linetrace_position;

const EngineMath::SVector3f invDir = 1.f / linetrace_offset;

EngineMath::SVector3f Near = NearUndiv * invDir;
EngineMath::SVector3f Far = FarUndiv * invDir;

if (Near.x > Far.x) std::swap(Near.x, Far.x);
if (Near.y > Far.y) std::swap(Near.y, Far.y);
if (Near.z > Far.z) std::swap(Near.z, Far.z);

result.Delta = std::max(std::max(Near.x, Near.y), Near.z);
result.HitFarDelta = std::min(std::min(Far.x, Far.y), Far.z);

if (result.HitFarDelta  result.HitFarDelta) return false;
if (result.Delta < 0 || result.Delta > 1) return false;

result.HitFarDelta = std::min(1.f, result.HitFarDelta);

result.Position = linetrace_position + linetrace_offset * result.Delta;

bool NormalX = std::abs(result.Delta - Near.x) < epsilon2;
bool NormalY = std::abs(result.Delta - Near.y) < epsilon2;
bool NormalZ = std::abs(result.Delta - Near.z) < epsilon2;

if (NormalX &&  NormalZ)
{
return false;
}

if (NormalX)
{
result.Normal = EngineMath::SVector3f{-glm::sign(linetrace_offset.x), 0, 0};
return true;
}
if (NormalY)
{
result.Normal = EngineMath::SVector3f{0, -glm::sign(linetrace_offset.y), 0};
return true;
}
if (NormalZ)
{
result.Normal = EngineMath::SVector3f{0, 0, -glm::sign(linetrace_offset.z)};
return true;
}

return true;
}

bool CollisionHelper::SweepAABBAgainstAABB(SHitResult& result, const SAABB_CollisionShape& static_shape, const EngineMath::SVector3f& static_position, const SAABB_CollisionShape& dynamic_shape, const EngineMath::SVector3f& dynamic_position, const EngineMath::SVector3f& offset)
{
const EngineMath::SVector3f aabbMin = static_position + static_shape.Pivot - static_shape.Size;
const EngineMath::SVector3f aabbMax = static_position + static_shape.Pivot + static_shape.Size;

const EngineMath::SVector3f dyn_aabbMin = dynamic_position + dynamic_shape.Pivot - dynamic_shape.Size;
const EngineMath::SVector3f dyn_aabbMax = dynamic_position + dynamic_shape.Pivot + dynamic_shape.Size;

SAABB_CollisionShape temp_shape(static_shape.Pivot, static_shape.Size+dynamic_shape.Size, true);
if(LinetraceAgainstAABB(result, temp_shape, static_position, dynamic_shape.Pivot + dynamic_position, offset))
{
return true;
}
return false;
}

bool CollisionHelper::ResolveDynamicSweepForAABB(
const SAABB_CollisionShape& static_shape,
const EngineMath::SVector3f& static_position,
const SAABB_CollisionShape& dynamic_shape,
const EngineMath::SVector3f& dynamic_position,
EngineMath::SVector3f& dynamic_velocity)
{
SHitResult result;
if (SweepAABBAgainstAABB(result, static_shape, static_position, dynamic_shape, dynamic_position, dynamic_velocity))
{
float dot = glm::dot(dynamic_velocity, result.Normal);
if (dot < 0)
{
// Adjust the dynamic velocity to prevent penetration
// Remove the component of velocity that would cause penetration
dynamic_velocity = dynamic_velocity - result.Normal * dot * (1.0f - result.Delta);

//dynamic_velocity *= 0.99;
}
return true;
}
return false;
}

ECollisionShapeIntersection CollisionHelper::AABBInstersectsAABB(const SAABB_CollisionShape& shape1, const EngineMath::SVector3f& position1, const SAABB_CollisionShape& shape2, const EngineMath::SVector3f& position2)
{
EngineMath::SVector3f otherPosition = shape1.Pivot + position1;
EngineMath::SVector3f otherSize = shape1.Size;
EngineMath::SVector3f selfPosition = shape2.Pivot + position2;
EngineMath::SVector3f selfSize = shape2.Size;

EngineMath::SVector3f delta = otherPosition - selfPosition;
EngineMath::SVector3f intersection = glm::abs(delta) - (otherSize + selfSize);

if (intersection.x >= 0 || intersection.y >= 0 || intersection.z >= 0) return ECollisionShapeIntersection::NotIntersected;

if (intersection.x GetCollider()->SweepColliderAgainstTheWorld(result, offset, params))
{
offset += result.Normal * glm::abs(offset) * (1.f - result.Delta + 10e-3f);
for(int i = 0; i < 3; ++i)
offset[i] = glm::isnan(offset[i]) ? 0 : offset[i];
return true;
}
return false;
}

Я попытался максимизировать производительность, оставив некоторое пространство для неупорядоченного набора и сварки некоторых кубиков в более крупное, но мне еще предстоит найти какой -либо алгоритм, который еще не замедляет игру.

Подробнее здесь: https://stackoverflow.com/questions/794 ... locks-in-a