BoundingSphere.cpp

Go to the documentation of this file.

#include "Engine/Math/BoundingSphere.h"
 
#include <stdexcept>
#include <glm/gtx/norm.hpp>
 
#include "Engine/Logging/TracyMacros.hpp"
 
namespace Math {
    void BoundingSphere::calculate(Ecs::BoundingSphere& sphere, const std::vector<glm::vec3>& pointsToFit) {
        if (pointsToFit.empty()) {
            sphere.center = glm::vec3(0.0f);
            sphere.radius = 0.0f;
            return;
        }
 
        TRACY_ZONE_SCOPED_NAMED("Calculate Bounds");
        
        // Find most separated points along each axis
        glm::vec3 minX, maxX, minY, maxY, minZ, maxZ;
        minX = maxX = minY = maxY = minZ = maxZ = pointsToFit[0];
 
        for (const auto& point : pointsToFit) {
            if (point.x < minX.x) minX = point;
            if (point.x > maxX.x) maxX = point;
            if (point.y < minY.y) minY = point;
            if (point.y > maxY.y) maxY = point;
            if (point.z < minZ.z) minZ = point;
            if (point.z > maxZ.z) maxZ = point;
        }
 
        float distX = glm::distance2(minX, maxX);
        float distY = glm::distance2(minY, maxY);
        float distZ = glm::distance2(minZ, maxZ);
 
        glm::vec3 p1, p2;
        if (distX > distY && distX > distZ) {
            p1 = minX;
            p2 = maxX;
        } else if (distY > distZ) {
            p1 = minY;
            p2 = maxY;
        } else {
            p1 = minZ;
            p2 = maxZ;
        }
 
        // Initial sphere
        glm::vec3 center = (p1 + p2) * 0.5f;
        float radius = glm::distance(center, p2);
 
        // Expand to include all points using Ritter's algorithm
        {
            TRACY_ZONE_SCOPED_NAMED("Expand bounds to include all points");
 
            // First pass: find the point farthest from current center
            float maxDistSq = 0.0f;
            glm::vec3 farthestPoint = center;
 
            for (const auto& point : pointsToFit) {
                glm::vec3 diff = point - center;
                float distSq = glm::dot(diff, diff);
 
                if (distSq > maxDistSq) {
                    maxDistSq = distSq;
                    farthestPoint = point;
                }
            }
 
            // If we found a point outside the sphere, expand the sphere
            if (maxDistSq > radius * radius) {
                float dist = glm::sqrt(maxDistSq);
                float newRadius = (radius + dist) * 0.5f;
                center += (farthestPoint - center) * ((dist - radius) / dist);
                radius = newRadius;
 
                // Second pass: expand again to ensure all points are included
                maxDistSq = 0.0f;
                for (const auto& point : pointsToFit) {
                    glm::vec3 diff = point - center;
                    float distSq = glm::dot(diff, diff);
 
                    if (distSq > maxDistSq) {
                        maxDistSq = distSq;
                        farthestPoint = point;
                    }
                }
 
                if (maxDistSq > radius * radius) {
                    float dist = glm::sqrt(maxDistSq);
                    float newRadius = (radius + dist) * 0.5f;
                    center += (farthestPoint - center) * ((dist - radius) / dist);
                    radius = newRadius;
                }
            }
        }
 
        sphere.center = center;
        sphere.radius = radius;
    }
}