I’m building a voxel-based game and use an AABB-based movement component. The core function AABBSweep calls my RayCastBlocks function multiple times in a triple nested loop to gather blocks for collision checks. According to my profiler, it’s taking ~70% of the game tick. The AABB sweep is used to apply velocity to my entity's collider and then change it as a collision response so sliding can happen.
Below is a stripped-down version of my code, focusing on AABBSweep, RayCastBlocks, and the helper function LineTracePrep. My goal is to reduce CPU usage while preserving collision accuracy. The max_tries in RayCastBlocks is just a safeguard against infinite loops if something goes wrong.
Question:
What can I do to speed up or refactor this approach so I’m not paying such a high performance cost every frame? Are there known techniques for more efficient voxel collision checks (e.g., voxel traversal algorithms like Amanatides & Woo, spatial partitioning, or bounding volume hierarchies)? Where might I cache results or reduce the number of calls? Any tips on minimizing heavy set insertions or triple nested loops are especially helpful.
Below is the relevant code, which should compile if you have the necessary math/vector libraries. I’ve provided placeholder includes for brevity. Any feedback on reanizing the code, improving the algorithm, or standard best practices for voxel-based collision is greatly appreciated.
tick time at the time of the profiler snapshot I took: 3.81ms
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<EngineMath::SVector3i, EngineMath::SVector3iHash> 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<int>(std::floor(min.x)) - 1;
const int xMax = static_cast<int>(std::ceil(max.x)) + 1;
const int yMin = static_cast<int>(std::floor(min.y)) - 1;
const int yMax = static_cast<int>(std::ceil(max.y)) + 1;
const int zMin = static_cast<int>(std::floor(min.z)) - 1;
const int zMax = static_cast<int>(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 <= xMax; ++x)
{
for (int y = yMin; y <= yMax; ++y)
{
for (int z = zMin; z <= zMax; ++z)
{
RayCastBlocks({ static_cast<float>(x),
static_cast<float>(y),
static_cast<float>(z) },
offset,
possible_blocks);
}
}
}
}
// 3) Collision resolution
bool any_collision = false;
EngineMath::SVector3f new_offset = offset;
const SAABB_CollisionShape normal_box({0, 0, 0}, {1, 1, 1});
{
CProfiler::ScopedSection collisionSection(g_profiler, "CJABGWorld::AABBSweep::Collisions", false);//20% of the entire tick
for (auto& pair : possible_blocks)
{
const EngineMath::SVector3i& block = pair;
auto pos = m_manager->GetLocal(block.x, block.y, block.z);
ZSharedPointer<CChunkPart> part = m_manager->GetChunkPart(pos.first.x, pos.first.z);
CChunk* chunk = nullptr;
const SAABB_CollisionShape* collision_shape = nullptr;
if (part)
chunk = part->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<EngineMath::SVector3i, EngineMath::SVector3iHash>& 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 <iostream>
#include <string>
#include <algorithm>
#include <glm/gtx/string_cast.hpp>
#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 <= 0 || result.Delta > 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 <= -2*selfSize.x && intersection.y <= -2 * selfSize.y && intersection.z <= -2 * selfSize.z) return ECollisionShapeIntersection::FullyIntersected;
if (intersection.x < 0 && intersection.y < 0 && intersection.z < 0) return ECollisionShapeIntersection::PartiallyIntesected;
return ECollisionShapeIntersection::NotIntersected;
}
namespace EngineMath
{
typedef glm::vec3 SVector3f;
struct SVector3iHash {
size_t operator()(const SVector3i& v) const {
// A simple hash function combining the hash values of x, y, and z
return std::hash<int>()(v.x*73856093) ^ std::hash<int>()(v.y*19349663) ^ std::hash<int>()(v.z*83492791);
}
};
}
How am I using the logic from above? In the case below, SweepColliderAgainstTheWorld is just a wrapper for AABBSweep with some virtuals attached to it.
bool CJABGMovementComponent::SweepEntity(SHitResult& result, EngineMath::SVector3f& offset, const SCollisionChannelTracker& params)
{
if(m_owningPuppet->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;
}
I have tried to maximize the performance by reserving some space for the unordered set and by welding some cubes into a bigger one, but I have yet to find just any algorithm that doesn't slow the game even further.
Usage example of collisionhelper:
#include <iostream>
#include "CollisionHelper.h"
#include <glm/gtx/string_cast.hpp>
int main() {
SAABB_CollisionShape traceShape({0.0f, 0.0f, 0.0f}, {1.0f, 1.0f, 1.0f});
EngineMath::SVector3f aabbPos{0.0f, 0.0f, 0.0f};
EngineMath::SVector3f traceStart{-2.0f, 0.0f, 0.0f};
EngineMath::SVector3f traceOffset{3.0f, 0.0f, 0.0f};
SHitResult traceResult;
bool hitLine = CollisionHelper::LinetraceAgainstAABB(traceResult, traceShape, aabbPos, traceStart, traceOffset, 0);
if (hitLine) {
std::cout << "Linetrace hit at: " << glm::to_string(traceResult.Position) << "\n";
std::cout << "Hit normal: " << glm::to_string(traceResult.Normal) << "\n";
} else {
std::cout << "Linetrace did not hit.\n";
}
SAABB_CollisionShape staticShape({0.0f, 0.0f, 0.0f}, {1.0f, 1.0f, 1.0f});
SAABB_CollisionShape dynamicShape({0.0f, 0.0f, 0.0f}, {0.5f, 0.5f, 0.5f});
EngineMath::SVector3f staticPos{0.0f, 0.0f, 0.0f};
EngineMath::SVector3f dynamicPos{-2.0f, 0.0f, 0.0f};
EngineMath::SVector3f dynamicVel{3.0f, 0.0f, 0.0f};
bool sweepHit = CollisionHelper::ResolveDynamicSweepForAABB(staticShape, staticPos, dynamicShape, dynamicPos, dynamicVel);
if (sweepHit) {
std::cout << "Collision detected during dynamic sweep. Adjusted velocity: " << glm::to_string(dynamicVel) << "\n";
} else {
std::cout << "No collision detected during dynamic sweep.\n";
}
return 0;
}